Initialization of CONTEXT in timestamp::context::shared_context() not thread-safe

[tpunder]

The initialization of CONTEXT in shared_context() is not thread-safe. Multiple threads calling shared_context() can end up using an un-initialized CONTEXT before the thread that successfully calls compare_exchange can fully initialize CONTEXT.

uuid/src/timestamp.rs

Lines 372 to 392 in cefc353

	#[cfg(all(any(feature = "v1", feature = "v6"), feature = "std", feature = "rng"))]
	static CONTEXT: Context = Context {
	count: Atomic::new(0),
	};
	#[cfg(all(any(feature = "v1", feature = "v6"), feature = "std", feature = "rng"))]
	static CONTEXT_INITIALIZED: Atomic<bool> = Atomic::new(false);
	#[cfg(all(any(feature = "v1", feature = "v6"), feature = "std", feature = "rng"))]
	pub(crate) fn shared_context() -> &'static Context {
	// If the context is in its initial state then assign it to a random value
	// It doesn't matter if multiple threads observe `false` here and initialize the context
	if CONTEXT_INITIALIZED
	.compare_exchange(false, true, Ordering::Relaxed, Ordering::Relaxed)
	.is_ok()
	{
	CONTEXT.count.store(crate::rng::u16(), Ordering::Release);
	}
	&CONTEXT
	}

Here is an example that demonstrates the problem:

use std::thread;
use uuid::Uuid;

fn main() {
    let threads: Vec<thread::JoinHandle<()>> = (0..10).map(|i| {
        thread::spawn(move || {
            let node_id: [u8; 6] = [ 1, 2, 3, 4, 5, 6 ];
            let uuid = Uuid::now_v6(&node_id);
            let counter = uuid.get_timestamp().unwrap().to_rfc4122().1;
            println!("Hello from thread {i} - uuid: {uuid} - counter: {counter}!");
        })
    }).collect();

    threads.into_iter().for_each(|t| t.join().unwrap() );
}

Here are a few runs from an Macbook Pro M1 (arm64). You can see some of the threads are starting from the un-initialized value of 0 and counting from there before the thread that successfully runs the compare_exchange is able to actually initialized CONTEXT with a random value:

» cargo run
    Finished dev [unoptimized + debuginfo] target(s) in 0.01s
     Running `target/debug/weather`
Hello from thread 2 - uuid: 1eeb8a59-b9dc-66ca-8000-010203040506 - counter: 0!
Hello from thread 1 - uuid: 1eeb8a59-b9dc-6864-8002-010203040506 - counter: 2!
Hello from thread 3 - uuid: 1eeb8a59-b9dc-67c4-8001-010203040506 - counter: 1!
Hello from thread 0 - uuid: 1eeb8a59-b9dc-6968-87f3-010203040506 - counter: 2035!
Hello from thread 4 - uuid: 1eeb8a59-b9dc-6b52-87f4-010203040506 - counter: 2036!
Hello from thread 6 - uuid: 1eeb8a59-b9dc-6b7a-87f5-010203040506 - counter: 2037!
Hello from thread 5 - uuid: 1eeb8a59-b9dc-6c60-87f6-010203040506 - counter: 2038!
Hello from thread 7 - uuid: 1eeb8a59-b9dc-6daa-87f7-010203040506 - counter: 2039!
Hello from thread 8 - uuid: 1eeb8a59-b9dc-6e86-87f8-010203040506 - counter: 2040!
Hello from thread 9 - uuid: 1eeb8a59-b9dc-6f6c-87f9-010203040506 - counter: 2041!

» cargo run
    Finished dev [unoptimized + debuginfo] target(s) in 0.01s
     Running `target/debug/weather`
Hello from thread 2 - uuid: 1eeb8a59-c4ae-617a-8000-010203040506 - counter: 0!
Hello from thread 1 - uuid: 1eeb8a59-c4ae-61c0-8001-010203040506 - counter: 1!
Hello from thread 4 - uuid: 1eeb8a59-c4ae-642c-8002-010203040506 - counter: 2!
Hello from thread 3 - uuid: 1eeb8a59-c4ae-6440-8003-010203040506 - counter: 3!
Hello from thread 5 - uuid: 1eeb8a59-c4ae-64a4-8004-010203040506 - counter: 4!
Hello from thread 0 - uuid: 1eeb8a59-c4ae-65ee-8e52-010203040506 - counter: 3666!
Hello from thread 7 - uuid: 1eeb8a59-c4ae-6936-8e53-010203040506 - counter: 3667!
Hello from thread 6 - uuid: 1eeb8a59-c4ae-6936-8e54-010203040506 - counter: 3668!
Hello from thread 8 - uuid: 1eeb8a59-c4ae-6ada-8e55-010203040506 - counter: 3669!
Hello from thread 9 - uuid: 1eeb8a59-c4ae-6bfc-8e56-010203040506 - counter: 3670!

» cargo run
    Finished dev [unoptimized + debuginfo] target(s) in 0.01s
     Running `target/debug/weather`
Hello from thread 1 - uuid: 1eeb8a59-e1dc-6918-8000-010203040506 - counter: 0!
Hello from thread 2 - uuid: 1eeb8a59-e1dc-6af8-8002-010203040506 - counter: 2!
Hello from thread 4 - uuid: 1eeb8a59-e1dc-6dbe-8003-010203040506 - counter: 3!
Hello from thread 5 - uuid: 1eeb8a59-e1dc-6e2c-8004-010203040506 - counter: 4!
Hello from thread 3 - uuid: 1eeb8a59-e1dc-6af8-8001-010203040506 - counter: 1!
Hello from thread 6 - uuid: 1eeb8a59-e1dd-61ce-8005-010203040506 - counter: 5!
Hello from thread 7 - uuid: 1eeb8a59-e1dd-625a-8006-010203040506 - counter: 6!
Hello from thread 8 - uuid: 1eeb8a59-e1dd-6304-8007-010203040506 - counter: 7!
Hello from thread 0 - uuid: 1eeb8a59-e1dd-6372-a008-010203040506 - counter: 8200!
Hello from thread 9 - uuid: 1eeb8a59-e1dd-639a-a009-010203040506 - counter: 8201!

Here are some runs from an Intel Core i7 (x86_64):

$ cargo run
    Finished dev [unoptimized + debuginfo] target(s) in 0.01s
     Running `target/debug/weather`
Hello from thread 3 - uuid: 1eeb8a89-27dc-6f82-8000-010203040506 - counter: 0!
Hello from thread 1 - uuid: 1eeb8a89-27dd-6060-8002-010203040506 - counter: 2!
Hello from thread 0 - uuid: 1eeb8a89-27dc-6f81-8001-010203040506 - counter: 1!
Hello from thread 4 - uuid: 1eeb8a89-27dd-66b4-8003-010203040506 - counter: 3!
Hello from thread 5 - uuid: 1eeb8a89-27dd-6c9b-8004-010203040506 - counter: 4!
Hello from thread 2 - uuid: 1eeb8a89-27de-604a-a68e-010203040506 - counter: 9870!
Hello from thread 7 - uuid: 1eeb8a89-27de-61e2-a68f-010203040506 - counter: 9871!
Hello from thread 6 - uuid: 1eeb8a89-27de-63e0-a690-010203040506 - counter: 9872!
Hello from thread 8 - uuid: 1eeb8a89-27de-6485-a691-010203040506 - counter: 9873!
Hello from thread 9 - uuid: 1eeb8a89-27de-674c-a692-010203040506 - counter: 9874!

$ cargo run
    Finished dev [unoptimized + debuginfo] target(s) in 0.01s
     Running `target/debug/weather`
Hello from thread 2 - uuid: 1eeb8a89-904f-6bd7-8001-010203040506 - counter: 1!
Hello from thread 1 - uuid: 1eeb8a89-904f-6bd5-8000-010203040506 - counter: 0!
Hello from thread 3 - uuid: 1eeb8a89-904f-6be2-8003-010203040506 - counter: 3!
Hello from thread 4 - uuid: 1eeb8a89-904f-6bd5-8002-010203040506 - counter: 2!
Hello from thread 5 - uuid: 1eeb8a89-9050-6809-8004-010203040506 - counter: 4!
Hello from thread 0 - uuid: 1eeb8a89-9050-6b45-b4cd-010203040506 - counter: 13517!
Hello from thread 6 - uuid: 1eeb8a89-9051-6243-b4ce-010203040506 - counter: 13518!
Hello from thread 8 - uuid: 1eeb8a89-9051-648c-b4cf-010203040506 - counter: 13519!
Hello from thread 7 - uuid: 1eeb8a89-9051-651d-b4d0-010203040506 - counter: 13520!
Hello from thread 9 - uuid: 1eeb8a89-9051-67fa-b4d1-010203040506 - counter: 13521!

$ cargo run
    Finished dev [unoptimized + debuginfo] target(s) in 0.01s
     Running `target/debug/weather`
Hello from thread 1 - uuid: 1eeb8a89-ff0e-6a0d-8001-010203040506 - counter: 1!
Hello from thread 2 - uuid: 1eeb8a89-ff0e-6a0d-8002-010203040506 - counter: 2!
Hello from thread 3 - uuid: 1eeb8a89-ff0e-6a0b-8000-010203040506 - counter: 0!
Hello from thread 4 - uuid: 1eeb8a89-ff0f-60ac-8003-010203040506 - counter: 3!
Hello from thread 5 - uuid: 1eeb8a89-ff0f-65aa-8004-010203040506 - counter: 4!
Hello from thread 0 - uuid: 1eeb8a89-ff0f-671d-9d90-010203040506 - counter: 7568!
Hello from thread 6 - uuid: 1eeb8a89-ff0f-6999-9d91-010203040506 - counter: 7569!
Hello from thread 9 - uuid: 1eeb8a89-ff0f-6cc4-9d92-010203040506 - counter: 7570!
Hello from thread 7 - uuid: 1eeb8a89-ff0f-6ddf-9d93-010203040506 - counter: 7571!
Hello from thread 8 - uuid: 1eeb8a89-ff0f-6fdb-9d94-010203040506 - counter: 7572!

[KodrAus]

Thanks for pointing this out @tpunder! I think the important thing is for each UUID generated sequentially within the same timestamp interval (100ns for v1/v6 and 1ms for v7) to get a counter value that is larger than the previous. This is technically breakable under this scheme, but extremely unlikely. For v7 UUIDs it's recommended we randomize the counter each millisecond. I'm not sure if we'll want to do that, but should come up with some scheme to occasionally shuffle the counter.

So I think there is an issue here we need to fix. The solution to it will probably be whatever we come up with for v7 UUIDs using counters.

[KodrAus]

When generating v7 UUIDs, we do by default reset the counter each millisecond. For v6 UUIDs, I think the way this context currently works is still ok given how short the timestamp interval is (100ns rather than 1ms). If we wanted to be extra careful, we could ensure we set a reasonably high bit in the random number we replace the uninitialized context with to guarantee it's larger than any value we would've incremented up to.

I'll take a fresh look through the spec and see if it has any suggestions for counters in v1 or v6 UUIDs we could consider.

[KodrAus]

The spec suggests:

The clock sequence MUST be originally (i.e., once in the lifetime of a system) initialized to a random number to minimize the correlation across systems.

In order to be compliant, we'd probably need to spin when waiting for it to be initialized.