nsync

nsync is a C library that exports various synchronization primitives: locks condition variables run-once initialization waitable counter (useful for barriers) waitable bit (useful for cancellation, or other conditions)

It is not an offical Google product.

nsync may be desirable in place of pthread primitives in some cases:

• nsync locks are reader-writer locks (but are as efficient as mutexes).
• nsync locks and condition variables occupy only two words each.
• nsync works on Unix-like systems and Windows. It should be portable to other platforms straightforwardly.
• nsync provides conditional critical sections. These fill the same role as condition variables, but are usually easier to use, and in most common cases are comparable in speed. They can be easier to use in two ways:
  • it's not necessary to surround the "wait" operation in a while loop; instead the condition is passed to the call as a function and arbitrary pointer argument.
  • it's not necessary to wake or signal explicitly when the condition(s) become true; they are checked automatically. The primary downsides are:
  • they are not available in most other common synchronization APIs, and so they may be unfamiliar (even though they date back to the 1960s), and
  • if threads routinely wait on many distinct, false conditions associated with the same lock, they may be slower than condition variables. In this case, clients can use condition variables in the normal way; conditional critical sections and condition variables can be used with the same lock.
• nsync waits can be cancelled via an object passed to the wait calls, unlike the pthread model in which threads are cancelled. This difference can be useful if the computation needs multiple threads, or if cancellation affects only sub-operations within a larger operation by the thread. See the section "Extensions to locks and condition variables" below.

Portability

The library is intended to be portable, and to be compilable on a system with only a C90 compiler, assuming atomic operations are available from the compiler, operating system, or assembler routines. It is able to use C11 or C++11 atomic operations if they are available. It can be compiled with a C++ compiler, and in its own C++ name space, if desired, though no attempt has been made to present a class-based interface.

Building

The builds/ directory may already contain a subdirectory that matches your platform. For example, if you're on an x86_64, running Linux, using gcc, you might pick "x86_64.linux.gcc".

If there is an appropriate subdirectory, in that subdirectory type: make depend test which will calculate dependencies, build the library and its tests, and then run them. (On Windows, using Visual Studio ("x86_64.win32.msvc") use "nmake" instead of "make".)

If there is no suitable subdirectory, on most Unix-like systems you can create one with tools/mkmakefile.sh

The main reason it might fail is if it cannot find a suitable implementation of atomic operations on the platform. Atomic operations may be provided by

• compiler-dependent interfaces (currently, gcc and clang) These are auto detected by mkmakefile.sh.
• language-specific standards (currently, C11 and C++11) Selected in mkmakefile.sh via "-atomic c11" or "-atomic c++11".
• operating system-dependent libraries (e.g., NetBSD, MacOS, Windows) Selected in mkmakefile.sh via "-atomic os".
• architecture-dependent libraries (e.g., x86_64, x86_32, aarch64, arm, mips, alpha) Selected in mkmakefile.sh via "-atomic asm"; file should be named platforms//src/nsync_atm_.[csS] to be found by mkmakefile.sh. If none of these match your platform, you may need to provide an assembly language implementation.

Other possible issues:

• Some platforms put clock_gettime() in the realtime library. Give "-lrt" to mkmakefile.sh.
• The version identifier of "clang" can vary by installation, and so it may not be identified if invoked as "cc". Give "-cc clang" to mkmakefile.sh, if clang is not detected automatically.
• Some CPU architectures have many variants, making it difficult to rely on a single identifier. Give "-arch " to mkmakefile.sh to specify a particular string.

mkmakefile.sh recognises a couple of special cases:

• MacOS doesn't provide clock_gettime(); a compatibility routine is found in platform/posix/src/clock_gettime.c See builds/x86_64.macos.clang/Makefile
• OpenBSD and Irix do not provide thread-local storage, which is accommodated by adding -I../../platform/gcc_no_tls to the include path. See, for example, builds/x86_64.openbsd.gcc/Makefile.

Further customization is possible by editing the Makefile, directly. For Unix-like systems is typically only a few lines long. For example, compare builds/x86_64.linux.g++/Makefile with builds/x86_64.linux.gcc/Makefile to see how to compile the entire library in C++, rather than C.

CMake

CMake can also be used to build:

$ mkdir out
$ cd out/
$ cmake ..
$ make
$ make install

The C library will be called libnsync and C++ is libnsync_cpp.

Tests can be disabled with the CMake option: -DNSYNC_ENABLE_TESTS=0. To build shared libraries instead of static use: -DBUILD_SHARED_LIBS=ON.

CMake version >= 3.0 is strongly recommended.

Code structure

public/ Public header files for library. builds// Platform-dependent build directories, each with Makefile. internal/ Platform-independent library source code, and Makefile fragment. platform// Platform-dependent source code. testing/ Platform-independent testing source code is in "testing". tools/ Optional tools that can be used to create Makefile dependencies and run tests.

Where possible, the code avoids conditional compilation (#if, etc.), to avoid becoming a mess of C-preprocessor directives. The platform-dependent Makefiles set the appropriate include paths and specify platform-dependent modules where needed.

The build directories of the various platforms are kept separate to allow multiple platforms to be accommodated in one shared file system.

Differences from pthread locks and condition variables

Conditional critical sections

Consider the following use of a condition variable: /* variable declarations / nsync_mu mu = NSYNC_MU_INIT; / protects i / int i = 1; nsync_cv cv = NSYNC_CV_INIT; / signalled when i reaches 0 */

...

/* Waiter */
nsync_mu_lock (&mu);
while (i != 0) {
	nsync_cv_wait (&cv, &mu);
}
/* i is zero ... */
nsync_mu_unlock (&mu);

...

/* Decrementer */
nsync_mu_lock (&mu)
i--;
if (i == 0) {
	nsync_cv_broadcast (&cv);
}
nsync_mu_unlock (&mu);

With conditional critical sections, the equivalent is: /* variable declarations / nsync_mu mu = NSYNC_MU_INIT; / protects i */ int i = 1;

/* Condition */
int int_is_zero (void *v) {
	return (*(int *)v == 0);
}

...

/* Waiter */
nsync_mu_lock (&mu);
nsync_mu_wait (&mu, &int_is_zero, &i)
/* i is zero ... */
nsync_mu_unlock (&mu);

...

/* Decrementer */
nsync_mu_lock (&mu)
i--;
nsync_mu_unlock (&mu);

For the cost of writing a function that evaluates the desired condition, the waiter's while-loop, and the decrementer's signalling are handled by the implementation.

In most cases, this makes code easier to write and debug.

The primary cost is that the implementation must check whether any waiters' conditions have become true when releasing the lock. This cost becomes most noticable when threads wait on many distinct, false conditions. In such cases, some or all of the conditions can be converted to use condition variables and explicit signalling.

C++ users may be tempted to wrap this functionality in a way that uses lambda expressions for the conditions. This will work, but may be less efficient, because C++ does not provide a means to detect whether two lambda expressions evaluate the same function. This may force the implementation to evaluate the same false condition many more times than it otherwise might.

Reader/writer locks

There is no particular reason why a reader/writer lock need be significantly slower than a simple mutex. In both cases, the lock can be acquired or released with a single atomic read-modify-write sequence. Thus, the type nsync_mu is a reader/writer lock. Locks with reader-sections can be used with condition variables and conditional critical sections without affecting correctness.

Cancellation

The pthread API allows the cancellation of individual threads, and once a thread has been cancelled, it is expected to terminate soon. This can work well in some cases, but may not be convenient if an activity is associated with many threads, or if threads routinely act on behalf of multiple activities.

In nsync, cancellation involves an object separate from the thread, called an nsync_note. An nsync_note is conceptually a boolean that makes a single transition from false to true: it starts off "unnotified", can be notified:

• by an explicit nsync_note_notify() call,
• due to a timeout, or
• due to the transition of an optional parent nsync_note. So, for example, in a network server, a request with a deadline might have an nsync_note associated with it. Activities associated with that request might each have a child nsync_note, possibly with shorter deadlines. A cancellation request from the original caller might cancel the parent, which would cancel all the children.

The calls nsync_cv_wait_with_deadline() and nsync_mu_wait_with_deadline() take both a deadline and a pointer to an nsync_note, and will wake when the awaited condition becomes true, when the deadline (if any) expires, or when the nsync_note becomes notified. The return value indicates which of these occurred.