Thread-efficient nonce generations I need to create unique nonces for cryptographic purposes in a library that I am writing.  If the nonces ever fail to be unique, the consequences may be up to and including remote execution of arbitrary code (by means of allowing injection of untrusted input into an unmarshalling operation).

While my particular application does not need to be thread-safe yet, I want the code to be thread-safe so that it can work in multithreaded applications without modification.  I also want it to be fairly efficient – more so than (say) using a global lock for every operation.

The code has not (yet) been tested, mostly because I have no idea how to write a test case for multi-threaded (and mostly lock-free) code.  It makes the assumption that all thread-local storage is initialized to zero when a new thread is created – otherwise, it will fail miserably.

The header file nonce.h:

#ifndef NONCE_H_INCLUDED
#define NONCE_H_INCLUDED NONCE_H_INCLUDED
#pragma once
#ifdef __cplusplus
extern "C" {
#elif 0
}
#endif

typedef struct {
   char nonce[12];
} nonce;

nonce generate_new_nonce(void);

#if 0
{
#elif defined __cplusplus
}
#endif // defined __cplusplus

#endif // !defined NONCE_H_INCLUDED


And the implementation file nonce.c:

#include "nonce.h"
#include &lt;stdint.h&gt;
#include &lt;stdlib.h&gt;
#include &lt;string.h&gt;
#define STATIC_ASSERT(x)                                \
   (0*sizeof(struct {                                   \
      int static_assertion_failed : 1 - 2*((int)!(x)); \
      int dummy: 31;                                    \
   }))

static __thread uint32_t local_counter;
static __thread uint64_t local_snapshot;
static uint64_t global_counter;
static uintptr_t lock;

static uint64_t get_new_snapshot(void);

#ifdef __cplusplus
extern "C"
#endif
nonce generate_new_nonce(void) {
   STATIC_ASSERT(sizeof(local_counter) == 4);
   STATIC_ASSERT(sizeof(local_snapshot) == 8);
   STATIC_ASSERT(sizeof(global_counter) == 8);
   nonce retval;
   if (0 == local_counter) {
      local_snapshot = get_new_snapshot();
   }
   memcpy(retval.nonce, &amp;local_counter, sizeof local_counter);
   memcpy(retval.nonce + 4, &amp;local_snapshot, sizeof local_snapshot);
   local_counter += 1;
   return retval;
}

static uint64_t get_new_snapshot(void) {
   while(__sync_lock_test_and_set(&amp;lock, 1)) {}
   const uint64_t retval = global_counter;
   global_counter++;
   if (global_counter == 0) {
      /* Wraparound */
      abort();
   }
   __sync_lock_release(&amp;lock);
   return retval;
}
If all you do in your lock is global_counter++ you may as well make it a c++11 atomic, and just write local_counter = global_counter++.

Or, using what you've used so far, local_counter = __sync_fetch_and_add(&amp;global_counter,1)

You may drop the wraparound check. You can increment once per nanosecond and it'd flip in a few hundred years.

After all that's been said in the comments I'm pretty much convinced there are no simple (read: 3 lines of code) solutions given 4g threads will get created and we have only 32 bit atomics.

There are 3 valid solutions:


Stay with the mutex. I guess if you're spending the time to create a thread, it's not the end of the world to lock a mutex once per the thread's lifetime.
Reuse those threads so you never get to 4g. Maybe you can not coz your client's app created them?
Reuse the nonce ranges. Having so many threads means most of them exit way before they consume the 64bit range per 32bit snapshot.
Now, you can have a destructor on the TLS entry of the snapshot. Lookup pthread_key_create.
You can use this destructor to push the current snapshot and counter into a lock free stack and pop them out in get_new_snapshot.
You can init that array/stack with 1000 nonce ranges (999,0), (998,0),... (0,0)
The first thread would pop (0,0). When it exits it'd push back whatever it got to. Say (0,122283).
If a thread ever consumes it's 64bit range of nonces (if your app runs for a millennia) it can pop another range.
You can pre-allocate a stack large enough for as many concurrent threads as you like. If it's ever consumed default to dynamically allocating more ranges. But this would would probably never get executed.


I can give more detail about a pre-allocated lock free stack, if you like.