Debian Codegraph @

README

raw
1 nsync is a C library that exports various synchronization primitives:
2 locks
3 condition variables
4 run-once initialization
5 waitable counter (useful for barriers)
6 waitable bit (useful for cancellation, or other conditions)
7
8 It is not an offical Google product.
9
10 nsync may be desirable in place of pthread primitives in some cases:
11 - nsync locks are reader-writer locks (but are as efficient as mutexes).
12 - nsync locks and condition variables occupy only two words each.
13 - nsync works on Unix-like systems and Windows. It should be portable to
14 other platforms straightforwardly.
15 - nsync provides conditional critical sections. These fill the same role
16 as condition variables, but are usually easier to use, and in most common
17 cases are comparable in speed. They can be easier to use in two ways:
18 - it's not necessary to surround the "wait" operation in a while loop;
19 instead the condition is passed to the call as a function and arbitrary
20 pointer argument.
21 - it's not necessary to wake or signal explicitly when the condition(s)
22 become true; they are checked automatically.
23 The primary downsides are:
24 - they are not available in most other common synchronization APIs, and so
25 they may be unfamiliar (even though they date back to the 1960s), and
26 - if threads routinely wait on many distinct, false conditions
27 associated with the same lock, they may be slower than condition variables.
28 In this case, clients can use condition variables in the normal way;
29 conditional critical sections and condition variables can be used with
30 the same lock.
31 - nsync waits can be cancelled via an object passed to the wait calls, unlike
32 the pthread model in which threads are cancelled. This difference can be
33 useful if the computation needs multiple threads, or if cancellation affects
34 only sub-operations within a larger operation by the thread.
35 See the section "Extensions to locks and condition variables" below.
36
37 Portability
38 ===========
39 The library is intended to be portable, and to be compilable on a system with
40 only a C90 compiler, assuming atomic operations are available from the
41 compiler, operating system, or assembler routines. It is able to use C11 or
42 C++11 atomic operations if they are available.
43 It can be compiled with a C++ compiler, and in its own C++ name space, if
44 desired, though no attempt has been made to present a class-based interface.
45
46 Building
47 ========
48 The builds/ directory may already contain a subdirectory that
49 matches your platform. For example, if you're on an x86_64,
50 running Linux, using gcc, you might pick "x86_64.linux.gcc".
51
52 If there is an appropriate subdirectory, in that subdirectory type:
53 make depend test
54 which will calculate dependencies, build the library and its tests, and then
55 run them. (On Windows, using Visual Studio ("x86_64.win32.msvc")
56 use "nmake" instead of "make".)
57
58 If there is no suitable subdirectory, on most Unix-like systems you can create
59 one with
60 tools/mkmakefile.sh
61
62 The main reason it might fail is if it cannot find a suitable implementation of
63 atomic operations on the platform. Atomic operations may be provided by
64 - compiler-dependent interfaces (currently, gcc and clang)
65 These are auto detected by mkmakefile.sh.
66 - language-specific standards (currently, C11 and C++11)
67 Selected in mkmakefile.sh via "-atomic c11" or "-atomic c++11".
68 - operating system-dependent libraries (e.g., NetBSD, MacOS, Windows)
69 Selected in mkmakefile.sh via "-atomic os".
70 - architecture-dependent libraries (e.g., x86_64, x86_32, aarch64,
71 arm, mips, alpha)
72 Selected in mkmakefile.sh via "-atomic asm"; file should be
73 named platforms/<architecture>/src/nsync_atm_<architecture>.[csS]
74 to be found by mkmakefile.sh.
75 If none of these match your platform, you may need to provide
76 an assembly language implementation.
77
78 Other possible issues:
79 - Some platforms put clock_gettime() in the realtime library.
80 Give "-lrt" to mkmakefile.sh.
81 - The version identifier of "clang" can vary by installation,
82 and so it may not be identified if invoked as "cc".
83 Give "-cc clang" to mkmakefile.sh, if clang is not detected automatically.
84 - Some CPU architectures have many variants, making it
85 difficult to rely on a single identifier.
86 Give "-arch <architecture>" to mkmakefile.sh to specify
87 a particular string.
88
89 mkmakefile.sh recognises a couple of special cases:
90 - MacOS doesn't provide clock_gettime(); a compatibility routine
91 is found in platform/posix/src/clock_gettime.c
92 See builds/x86_64.macos.clang/Makefile
93 - OpenBSD and Irix do not provide thread-local storage, which is accommodated
94 by adding -I../../platform/gcc_no_tls to the include path.
95 See, for example, builds/x86_64.openbsd.gcc/Makefile.
96
97 Further customization is possible by editing the Makefile, directly.
98 For Unix-like systems is typically only a few lines long.
99 For example, compare
100 builds/x86_64.linux.g++/Makefile
101 with
102 builds/x86_64.linux.gcc/Makefile
103 to see how to compile the entire library in C++, rather than C.
104
105 CMake
106 -----
107
108 CMake can also be used to build:
109
110 $ mkdir out
111 $ cd out/
112 $ cmake ..
113 $ make
114 $ make install
115
116 The C library will be called libnsync and C++ is libnsync_cpp.
117
118 Tests can be disabled with the CMake option: -DNSYNC_ENABLE_TESTS=0.
119 To build shared libraries instead of static use: -DBUILD_SHARED_LIBS=ON.
120
121 CMake version >= 3.0 is strongly recommended.
122
123 Code structure
124 ==============
125 public/ Public header files for library.
126 builds/*/ Platform-dependent build directories, each with Makefile.
127 internal/ Platform-independent library source code, and Makefile fragment.
128 platform/*/ Platform-dependent source code.
129 testing/ Platform-independent testing source code is in "testing".
130 tools/ Optional tools that can be used to create Makefile
131 dependencies and run tests.
132
133 Where possible, the code avoids conditional compilation (#if, etc.),
134 to avoid becoming a mess of C-preprocessor directives.
135 The platform-dependent Makefiles set the appropriate include
136 paths and specify platform-dependent modules where needed.
137
138 The build directories of the various platforms are kept separate to allow
139 multiple platforms to be accommodated in one shared file system.
140
141 Differences from pthread locks and condition variables
142 ======================================================
143
144 Conditional critical sections
145 -----------------------------
146 Consider the following use of a condition variable:
147 /* variable declarations */
148 nsync_mu mu = NSYNC_MU_INIT; /* protects i */
149 int i = 1;
150 nsync_cv cv = NSYNC_CV_INIT; /* signalled when i reaches 0 */
151
152 ...
153
154 /* Waiter */
155 nsync_mu_lock (&mu);
156 while (i != 0) {
157 nsync_cv_wait (&cv, &mu);
158 }
159 /* i is zero ... */
160 nsync_mu_unlock (&mu);
161
162 ...
163
164 /* Decrementer */
165 nsync_mu_lock (&mu)
166 i--;
167 if (i == 0) {
168 nsync_cv_broadcast (&cv);
169 }
170 nsync_mu_unlock (&mu);
171
172 With conditional critical sections, the equivalent is:
173 /* variable declarations */
174 nsync_mu mu = NSYNC_MU_INIT; /* protects i */
175 int i = 1;
176
177 /* Condition */
178 int int_is_zero (void *v) {
179 return (*(int *)v == 0);
180 }
181
182 ...
183
184 /* Waiter */
185 nsync_mu_lock (&mu);
186 nsync_mu_wait (&mu, &int_is_zero, &i)
187 /* i is zero ... */
188 nsync_mu_unlock (&mu);
189
190 ...
191
192 /* Decrementer */
193 nsync_mu_lock (&mu)
194 i--;
195 nsync_mu_unlock (&mu);
196
197 For the cost of writing a function that evaluates the desired
198 condition, the waiter's while-loop, and the decrementer's
199 signalling are handled by the implementation.
200
201 In most cases, this makes code easier to write and debug.
202
203 The primary cost is that the implementation must check whether any waiters'
204 conditions have become true when releasing the lock. This cost becomes most
205 noticable when threads wait on many distinct, false conditions. In such cases,
206 some or all of the conditions can be converted to use condition variables and
207 explicit signalling.
208
209 C++ users may be tempted to wrap this functionality in a way that uses
210 lambda expressions for the conditions. This will work, but may be less
211 efficient, because C++ does not provide a means to detect whether two lambda
212 expressions evaluate the same function. This may force the implementation to
213 evaluate the same false condition many more times than it otherwise might.
214
215 Reader/writer locks
216 -------------------
217 There is no particular reason why a reader/writer lock need be
218 significantly slower than a simple mutex. In both cases, the lock can be
219 acquired or released with a single atomic read-modify-write sequence.
220 Thus, the type nsync_mu is a reader/writer lock. Locks with reader-sections
221 can be used with condition variables and conditional critical sections
222 without affecting correctness.
223
224 Cancellation
225 ------------
226 The pthread API allows the cancellation of individual threads,
227 and once a thread has been cancelled, it is expected to terminate soon. This
228 can work well in some cases, but may not be convenient if an activity is
229 associated with many threads, or if threads routinely act on behalf of multiple
230 activities.
231
232 In nsync, cancellation involves an object separate from the thread, called an
233 nsync_note. An nsync_note is conceptually a boolean that makes a single
234 transition from false to true: it starts off "unnotified", can be notified:
235 - by an explicit nsync_note_notify() call,
236 - due to a timeout, or
237 - due to the transition of an optional parent nsync_note.
238 So, for example, in a network server, a request with a deadline
239 might have an nsync_note associated with it. Activities associated with
240 that request might each have a child nsync_note, possibly with shorter
241 deadlines. A cancellation request from the original caller
242 might cancel the parent, which would cancel all the children.
243
244 The calls nsync_cv_wait_with_deadline() and nsync_mu_wait_with_deadline() take
245 both a deadline and a pointer to an nsync_note, and will wake when the awaited
246 condition becomes true, when the deadline (if any) expires, or when the
247 nsync_note becomes notified. The return value indicates which of these
248 occurred.