Line data Source code
1 : /* Generate prototypes, inlines and/or implementations for concurrent
2 : persistent shared element pools. A pool can hold a practically
3 : unbounded number of elements. Acquiring an element from and
4 : releasing an element to a pool are typically fast O(1) time.
5 : Requires small O(1) space per element.
6 :
7 : The current implementation is based on a lockfree stack. Acquire and
8 : release are done via atomic compare-and-swap of the stack top. As
9 : such, concurrent usage requires FD_HAS_ATOMIC support (this can still
10 : be used on platforms without FD_HAS_ATOMIC but it will not be safe
11 : for concurrent usage). Stack top versioning is used to handle ABA.
12 : Versioning has been tweaked to support locked pool operations like
13 : initialization (and thus this can also be used without changes as a
14 : more conventional spin lock based concurrent stack). Unsurprisingly,
15 : the current implementation is equally usable as a concurrent element
16 : stack (though the implementation may be changed in the future to
17 : better support ultra high contention ultra high concurrency ala
18 : fd_alloc).
19 :
20 : The current implementation is optimized for pools with a moderate
21 : number of reasonably localized users (e.g. a handful of cores and
22 : memory on the same NUMA node). Various operations are slightly more
23 : optimal when the size of a pool element is an integer power of 2.
24 : Operations do much internal integrity checking / bounds checking for
25 : use in high reliability / high security environments.
26 :
27 : This API is designed for tight and flexible composition with treaps,
28 : heaps, lists, maps, etc. Further, a pool can be persisted beyond the
29 : lifetime of the creating process, be used inter-process, be relocated
30 : in memory, be naively serialized/deserialized, be moved between
31 : hosts, use index compression for cache and memory bandwidth
32 : efficiency, etc.
33 :
34 : Typical usage:
35 :
36 : struct myele {
37 : ulong next; // Technically "POOL_IDX_T POOL_NEXT" (default is ulong next), managed by the mypool when in the mypool
38 :
39 : ... next can be located arbitrarily in the element and can be
40 : ... reused for other purposes when the element is not in a
41 : ... mypool. elements are all located in a linear array element
42 : ... store whose lifetime is at least that of the mypool.
43 :
44 : };
45 :
46 : typedef struct myele myele_t;
47 :
48 : #define POOL_NAME mypool
49 : #define POOL_ELE_T myele_t
50 : #include "tmpl/fd_pool_para.c"
51 :
52 : will declare the following APIs as a header only style library in the
53 : compilation unit:
54 :
55 : // A mypool_t is a stack declaration friendly quasi-opaque handle
56 : // used to describe a join to a mypool. E.g. it is fine to do
57 : // "mypool_t join[1];" to allocate a mypool_t but the contents
58 : // should be used directly.
59 :
60 : typedef struct mypool_private mypool_t;
61 :
62 : // Constructors
63 :
64 : // mypool_ele_max_max returns the maximum element store capacity
65 : // compatible with a mypool.
66 :
67 : ulong mypool_ele_max_max( void );
68 :
69 : // mypool_{align,footprint} returns the alignment and footprint
70 : // needed for a memory region to be used as a mypool. align will
71 : // be an integer power-of-two and footprint will be a multiple of
72 : // align.
73 : //
74 : // mypool_new formats a memory region with the appropriate
75 : // alignment and footprint into a mypool. shmem points in the
76 : // caller's address space of the memory region to format. Returns
77 : // shmem on success (mypool has ownership of the memory region) and
78 : // NULL on failure (no changes, logs details). Caller is not
79 : // joined on return. The mypool will be empty and unlocked.
80 : //
81 : // mypool_join joins a mypool. ljoin points to a mypool_t
82 : // compatible memory region in the caller's address space used to
83 : // hold info about the local join, shpool points in the caller's
84 : // address space to the memory region containing the mypool, shele
85 : // points in the caller's address space to mypool's element store,
86 : // and ele_max is the element store's capacity. Returns a handle
87 : // to the caller's local join on success (join has ownership of the
88 : // ljoin region) and NULL on failure (no changes, logs details).
89 : //
90 : // mypool_leave leaves a mypool. join points to a current local
91 : // join. Returns the memory used for the local join (caller has
92 : // ownership on return and caller is no longer joined) on success
93 : // and NULL on failure (no changes, logs details). Use the join
94 : // accessors before leaving to get shpool, shele and ele_max used
95 : // by the join if needed.
96 : //
97 : // mypool_delete unformats a memory region used as a mypool.
98 : // Assumes shpool points in the caller's address space to the
99 : // memory region containing the mypool and that there are no
100 : // current joins globally. Returns shpool on success (caller has
101 : // ownership of the memory region and any elements still in the
102 : // mypool are acquired by the caller) and NULL on failure (no
103 : // changes, logs details).
104 :
105 : ulong mypool_align ( void );
106 : ulong mypool_footprint( void );
107 : void * mypool_new ( void * shmem );
108 : mypool_t * mypool_join ( void * ljoin, void * shpool, void * shele, ulong ele_max );
109 : void * mypool_leave ( mypool_t * join );
110 : void * mypool_delete ( void * shpool );
111 :
112 : // mypool_{shpool,shele,ele_max} return join details. Assumes join
113 : // is a current local join. mypool_{shpool_const,shele_const} are
114 : // const correct versions. The lifetime of the returned pointers
115 : // is the lifetime of the join.
116 :
117 : void const * mypool_shpool_const( mypool_t const * join );
118 : void const * mypool_shele_const ( mypool_t const * join );
119 : ulong mypool_ele_max ( mypool_t const * join );
120 :
121 : void * mypool_shpool( mypool_t * join );
122 : void * mypool_shele ( mypool_t * join );
123 :
124 : // mypool_idx_null returns the element store index used to
125 : // represent null for a mypool.
126 : //
127 : // mypool_idx_is_null returns 1 if an element store index is the
128 : // null index value and 0 otherwise.
129 : //
130 : // mypool_idx returns the element store index for the element
131 : // pointed to by ele in the caller's address space. Assumes join
132 : // is a current local join. If ele is NULL or not into the element
133 : // store, returns the element store null index.
134 : //
135 : // mypool_ele returns a pointer in the caller's address space to
136 : // the element whose element store index is ele_idx. If ele_idx is
137 : // the null value or invalid, returns NULL. mypool_ele_const is a
138 : // const correct version.
139 : //
140 : // These are usually not needed but allow translating pointers to
141 : // element store elements from one address space to another.
142 :
143 : ulong mypool_idx_null ( void );
144 : int mypool_idx_is_null( ulong idx );
145 : ulong mypool_idx ( mypool_t const * join, myele_t const * ele );
146 :
147 : myele_t const * mypool_ele_const( mypool_t const * join, ulong ele_idx );
148 : myele_t * mypool_ele ( mypool_t * join, ulong ele_idx );
149 :
150 : // mypool_peek returns a pointer in the local address space to the
151 : // next element to acquire from the mypool or NULL if the mypool
152 : // was empty at some point during the call. mypool_peek_const is a
153 : // const correct version. Because of concurrent operations, unless
154 : // the caller is holding a lock on the mypool, this may not be the
155 : // actual element the caller will acquire next from the mypool.
156 :
157 : myele_t const * mypool_peek_const( mypool_t const * join );
158 : myele_t * mypool_peek ( mypool_t * join );
159 :
160 : // mypool_acquire acquires an element from a mypool. Assumes join
161 : // is a current local join. If the mypool is empty or an error
162 : // occurs, returns sentinel (arbitrary). A non-zero / zero value
163 : // for blocking indicates locked operations on the mypool are / are
164 : // not allowed to block the caller. If opt_err is not NULL, on
165 : // return, *_opt_err will indicate FD_POOL_SUCCESS (zero) or an
166 : // FD_POOL_ERR code (negative). On success, the returned value
167 : // will be a pointer in the caller's address space to the element
168 : // store element acquired from the mypool. On failure for any
169 : // reason, the value returned will be sentinel and the mypool will
170 : // be unchanged. Reasons for failure:
171 : //
172 : // FD_POOL_ERR_EMPTY: the mypool contained no elements at some
173 : // point during the call.
174 : //
175 : // FD_POOL_ERR_AGAIN: the mypool was locked at some point during
176 : // the call. Never returned for a blocking call (but then locking
177 : // operations can then potentially block the caller indefinitely).
178 : //
179 : // FD_POOL_ERR_CORRUPT: memory corruption was detected during the
180 : // call.
181 :
182 : myele_t * mypool_acquire( mypool_t * join, myele_t * sentinel, int blocking, int * _opt_err );
183 :
184 : // mypool_release releases an element to a mypoool. Assumes join
185 : // is a current local join, ele is a pointer in the caller's
186 : // address space to the element, and the element is currently not
187 : // in the mypool. Returns FD_POOL_SUCCESS (zero) on success (the
188 : // element will be in the mypool on return) and an FD_POOL_ERR code
189 : // (negative) on failure (the element will not be in the mypool on
190 : // return). Reasons for failure:
191 : //
192 : // FD_POOL_ERR_INVAL: ele does not point to an element in mypool's
193 : // element store.
194 : //
195 : // FD_POOL_ERR_AGAIN: the mypool was locked at some point during
196 : // the call. Never returned for a blocking call (but locking
197 : // operations can then potentially block the caller indefinitely).
198 : //
199 : // FD_POOL_ERR_CORRUPT: memory corruption was detected during the
200 : // call.
201 :
202 : int mypool_release( mypool_t * join, myele_t * ele, int blocking );
203 :
204 : // mypool_is_locked returns whether or not a mypool is locked.
205 : // Assumes join is a current local join.
206 :
207 : int mypool_is_locked( mypool_t const * join );
208 :
209 : // mypool_lock will lock a mypool (e.g. pausing concurrent acquire
210 : // / release operations). A non-zero / zero value for blocking
211 : // indicates the call should / should not wait to lock the mypool
212 : // if it is currently locked. Returns FD_POOL_SUCCESS on success
213 : // (caller has the lock on return) and FD_POOL_ERR_AGAIN on failure
214 : // (pool was already locked at some point during the call). AGAIN
215 : // is never returned if blocking is requested. Assumes join is a
216 : // current local join.
217 :
218 : int mypool_lock( mypool_t * join, int blocking );
219 :
220 : // mypool_unlock will unlock a mypool (e.g. resuming concurrent
221 : // acquire / release operations). Assumes join is a current local
222 : // join and the caller has a lock on mypool. Guaranteed to
223 : // succeed.
224 :
225 : void mypool_unlock( mypool_t * join );
226 :
227 : // mypool_reset resets the mypool. On return, it will hold all but
228 : // the leading sentinel_cnt elements in the element store (e.g.
229 : // initialization after creation) in ascending order. If
230 : // sentinel_cnt is greater than or equal to the element store
231 : // capacity, the mypool will be empty on return. Thus, on return,
232 : // if sentinel_cnt is zero, every element in the element store will
233 : // be in the mypool and, if sentinel_cnt is ele_max or greater
234 : // (e.g. ULONG_MAX), every element will be removed from the mypool.
235 : // Assumes join is a current local join and the mypool is locked or
236 : // otherwise idle.
237 :
238 : void mypool_reset( mypool_t * join, ulong sentinel_cnt );
239 :
240 : // mypool_verify returns FD_POOL_SUCCESS if join appears to be
241 : // current local join to a valid mypool and FD_POOL_ERR_CORRUPT
242 : // otherwise (logs details). Assumes join is a current local join
243 : // and the mypool is locked or otherwise idle.
244 :
245 : int mypool_verify( mypool_t const * join );
246 :
247 : // mypool_strerror converts an FD_POOL_SUCCESS / FD_POOL_ERR code
248 : // into a human readable cstr. The lifetime of the returned
249 : // pointer is infinite. The returned pointer is always to a
250 : // non-NULL cstr.
251 :
252 : char const * mypool_strerror( int err );
253 :
254 : Do this as often as desired in a compilation unit to get different
255 : types of concurrent pools. Options exist for generating library
256 : header prototypes and/or library implementations for concurrent pools
257 : usable across multiple compilation units. Additional options exist
258 : to use index compression, configuring versioning, etc. */
259 :
260 : /* POOL_NAME gives the API prefix to use for pool */
261 :
262 : #ifndef POOL_NAME
263 : #error "Define POOL_NAME"
264 : #endif
265 :
266 : /* POOL_ELE_T is the pool element type. */
267 :
268 : #ifndef POOL_ELE_T
269 : #error "Define POOL_ELE_T"
270 : #endif
271 :
272 : /* POOL_IDX_T is the type used for the next field in the POOL_ELE_T.
273 : Should be a primitive unsigned integer type. Defaults to ulong. A
274 : pool can't use element stores with a capacity that can't be
275 : represented by a POOL_IDX_T. (E.g. if ushort, the maximum capacity
276 : pool compatible element store is 65535 elements.) */
277 :
278 : #ifndef POOL_IDX_T
279 : #define POOL_IDX_T ulong
280 : #endif
281 :
282 : /* POOL_NEXT is the POOL_ELE_T next field */
283 :
284 : #ifndef POOL_NEXT
285 899166 : #define POOL_NEXT next
286 : #endif
287 :
288 : /* POOL_ALIGN gives the alignment required for the pool shared memory.
289 : Default is 128 for double cache line alignment. Should be at least
290 : ulong alignment. */
291 :
292 : #ifndef POOL_ALIGN
293 : #define POOL_ALIGN (128UL)
294 : #endif
295 :
296 : /* POOL_IDX_WIDTH gives the number of bits in a ulong to reserve for
297 : encoding the element store index in a versioned index. Element store
298 : capacity should be representable in this width. Default is 43 bits
299 : (e.g. enough to support a ~1 PiB element store of 128 byte elements).
300 : The versioning width will be 64-POOL_IDX_WIDTH. Since the least
301 : significant bit of the version is used to indicate global locking,
302 : versioning width should be at least 2 and ideally as large as
303 : possible. With the 43 default, version numbers will not be reused
304 : until 2^20 individual operations have been done. */
305 :
306 : #ifndef POOL_IDX_WIDTH
307 1119760493 : #define POOL_IDX_WIDTH (43)
308 : #endif
309 :
310 : /* POOL_MAGIC is the magic number to use for the structure to aid in
311 : persistent and or IPC usage. */
312 :
313 : #ifndef POOL_MAGIC
314 72 : #define POOL_MAGIC (0xf17eda2c37c90010UL) /* firedancer cpool version 0 */
315 : #endif
316 :
317 : /* POOL_IMPL_STYLE controls what to generate:
318 : 0 - local use only
319 : 1 - library header declaration
320 : 2 - library implementation */
321 :
322 : #ifndef POOL_IMPL_STYLE
323 : #define POOL_IMPL_STYLE 0
324 : #endif
325 :
326 : /* Common pool error codes (FIXME: probably should get around to making
327 : unified error codes and string handling across all util at least so
328 : we don't have to do this in the generator itself) */
329 :
330 246834364 : #define FD_POOL_SUCCESS ( 0)
331 780 : #define FD_POOL_ERR_INVAL (-1)
332 6 : #define FD_POOL_ERR_AGAIN (-2)
333 13132557 : #define FD_POOL_ERR_CORRUPT (-3)
334 193465731 : #define FD_POOL_ERR_EMPTY (-4)
335 : //#define FD_POOL_ERR_FULL (-5)
336 : //#define FD_POOL_ERR_KEY (-6)
337 :
338 : /* Implementation *****************************************************/
339 :
340 825702589 : #define POOL_VER_WIDTH (64-POOL_IDX_WIDTH)
341 :
342 : #if POOL_IMPL_STYLE==0 /* local use only */
343 : #define POOL_STATIC FD_FN_UNUSED static
344 : #else /* library header and/or implementation */
345 : #define POOL_STATIC
346 : #endif
347 :
348 944315719 : #define POOL_(n) FD_EXPAND_THEN_CONCAT3(POOL_NAME,_,n)
349 :
350 : #if POOL_IMPL_STYLE!=2 /* need header */
351 :
352 : #include "../bits/fd_bits.h"
353 :
354 : struct __attribute__((aligned(POOL_ALIGN))) POOL_(shmem_private) {
355 :
356 : /* Note: there is no free count because that that isn't precisely
357 : knowable in a portable concurrent data structure. (Not enough bits
358 : to squeeze into ver_top for large pools, requiring 128-bit wide
359 : ver_top would limit supported targets, etc). */
360 :
361 : ulong magic; /* == POOL_MAGIC */
362 : ulong ver_top; /* Versioned index of the free stack top, top is in [0,ele_max) (not-empty) or is idx_null (empty) */
363 : };
364 :
365 : typedef struct POOL_(shmem_private) POOL_(shmem_t);
366 :
367 : struct POOL_(private) {
368 : POOL_(shmem_t) * pool; /* Pool location in the local address space */
369 : POOL_ELE_T * ele; /* Element store location in the local address space, NULL okay if ele_max==0 */
370 : ulong ele_max; /* Element store capacity, in [0,ele_max_max] */
371 : };
372 :
373 : typedef struct POOL_(private) POOL_(t);
374 :
375 : FD_PROTOTYPES_BEGIN
376 :
377 : /* pool_private_vidx pack ver and idx into a versioned idx. ver is
378 : masked to fit into POOL_VER_WIDTH bits. idx is assumed in
379 : [0,ele_max_max].
380 :
381 : pool_private_vidx_{ver,idx} extract the {version,index} from a
382 : versioned index and will fit into {POOL_VER_WIDTH,POOL_IDX_WIDTH}
383 : bits. */
384 :
385 53368916 : FD_FN_CONST static inline ulong POOL_(private_vidx)( ulong ver, ulong idx ) { return (ver<<POOL_IDX_WIDTH) | idx; }
386 :
387 246834575 : FD_FN_CONST static inline ulong POOL_(private_vidx_ver)( ulong ver_idx ) { return ver_idx >> POOL_IDX_WIDTH; }
388 271894499 : FD_FN_CONST static inline ulong POOL_(private_vidx_idx)( ulong ver_idx ) { return (ver_idx << POOL_VER_WIDTH) >> POOL_VER_WIDTH; }
389 :
390 : /* pool_private_{cidx,idx} compress/decompress a 64-bit in-register
391 : index to/from its in-memory representation. */
392 :
393 34762210 : FD_FN_CONST static inline POOL_IDX_T POOL_(private_cidx)( ulong idx ) { return (POOL_IDX_T) idx; }
394 31408861 : FD_FN_CONST static inline ulong POOL_(private_idx) ( ulong cidx ) { return (ulong) cidx; }
395 :
396 : /* pool_private_cas does a ulong FD_ATOMIC_CAS when FD_HAS_ATOMIC
397 : support is available and emulates it when not. Similarly for
398 : pool_private_fetch_and_or. When emulated, the pool will not be safe
399 : to use concurrently (but will still work). */
400 :
401 : static inline ulong
402 : POOL_(private_cas)( ulong volatile * p,
403 : ulong c,
404 53368757 : ulong s ) {
405 53368757 : ulong o;
406 53368757 : FD_COMPILER_MFENCE();
407 53368757 : # if FD_HAS_ATOMIC
408 53368757 : o = FD_ATOMIC_CAS( p, c, s );
409 : # else
410 : o = *p;
411 : *p = fd_ulong_if( o==c, s, o );
412 : # endif
413 53368757 : FD_COMPILER_MFENCE();
414 53368757 : return o;
415 53368757 : }
416 :
417 : static inline ulong
418 : POOL_(private_fetch_and_or)( ulong volatile * p,
419 3 : ulong b ) {
420 3 : ulong x;
421 3 : FD_COMPILER_MFENCE();
422 3 : # if FD_HAS_ATOMIC
423 3 : x = FD_ATOMIC_FETCH_AND_OR( p, b );
424 : # else
425 : x = *p;
426 : *p = x | b;
427 : # endif
428 3 : FD_COMPILER_MFENCE();
429 3 : return x;
430 3 : }
431 :
432 237 : FD_FN_CONST static inline ulong POOL_(ele_max_max)( void ) { return (ulong)(POOL_IDX_T)(ULONG_MAX >> POOL_VER_WIDTH); }
433 :
434 681 : FD_FN_CONST static inline ulong POOL_(align) ( void ) { return alignof(POOL_(shmem_t)); }
435 189 : FD_FN_CONST static inline ulong POOL_(footprint)( void ) { return sizeof (POOL_(shmem_t)); }
436 :
437 18 : FD_FN_PURE static inline void const * POOL_(shpool_const)( POOL_(t) const * join ) { return join->pool; }
438 36 : FD_FN_PURE static inline void const * POOL_(shele_const) ( POOL_(t) const * join ) { return join->ele; }
439 5819184 : FD_FN_PURE static inline ulong POOL_(ele_max) ( POOL_(t) const * join ) { return join->ele_max; }
440 :
441 3 : FD_FN_PURE static inline void * POOL_(shpool)( POOL_(t) * join ) { return join->pool; }
442 11319921 : FD_FN_PURE static inline void * POOL_(shele) ( POOL_(t) * join ) { return join->ele; }
443 :
444 281913354 : FD_FN_CONST static inline ulong POOL_(idx_null)( void ) { return (ulong)(POOL_IDX_T)(ULONG_MAX >> POOL_VER_WIDTH); }
445 280985948 : FD_FN_CONST static inline int POOL_(idx_is_null)( ulong idx ) { return idx==POOL_(idx_null)(); }
446 :
447 : FD_FN_PURE static inline ulong
448 : POOL_(idx)( POOL_(t) const * join,
449 16972065 : POOL_ELE_T const * ele ) {
450 16972065 : ulong ele_idx = (ulong)(ele - join->ele);
451 16972065 : return ele_idx<join->ele_max ? ele_idx : POOL_(idx_null)();
452 16972065 : }
453 :
454 : FD_FN_PURE static inline POOL_ELE_T const *
455 : POOL_(ele_const)( POOL_(t) const * join,
456 3078 : ulong ele_idx ) {
457 3078 : POOL_ELE_T const * ele = join->ele;
458 3078 : return (ele_idx < join->ele_max) ? (ele + ele_idx) : NULL;
459 3078 : }
460 :
461 : FD_FN_PURE static inline POOL_ELE_T *
462 : POOL_(ele)( POOL_(t) * join,
463 389251 : ulong ele_idx ) {
464 389251 : POOL_ELE_T * ele = join->ele;
465 389251 : return (ele_idx < join->ele_max) ? (ele + ele_idx) : NULL;
466 389251 : }
467 :
468 : static inline POOL_ELE_T const *
469 30 : POOL_(peek_const)( POOL_(t) const * join ) {
470 30 : POOL_(shmem_t) const * pool = join->pool;
471 30 : POOL_ELE_T const * ele = join->ele;
472 30 : ulong ele_max = join->ele_max;
473 30 : FD_COMPILER_MFENCE();
474 30 : ulong ver_top = pool->ver_top;
475 30 : FD_COMPILER_MFENCE();
476 30 : ulong ele_idx = POOL_(private_vidx_idx)( ver_top );
477 30 : return (ele_idx<ele_max) ? ele + ele_idx : NULL;
478 30 : }
479 :
480 15 : static inline POOL_ELE_T * POOL_(peek)( POOL_(t) * join ) { return (POOL_ELE_T *)POOL_(peek_const)( join ); }
481 :
482 : static inline int
483 9 : POOL_(is_locked)( POOL_(t) const * join ) {
484 9 : POOL_(shmem_t) const * pool = join->pool;
485 9 : FD_COMPILER_MFENCE();
486 9 : ulong ver_top = pool->ver_top;
487 9 : FD_COMPILER_MFENCE();
488 9 : return (int)(POOL_(private_vidx_ver)( ver_top ) & 1UL);
489 9 : }
490 :
491 : static inline void
492 3 : POOL_(unlock)( POOL_(t) * join ) {
493 3 : POOL_(shmem_t) * pool = join->pool;
494 3 : FD_COMPILER_MFENCE();
495 3 : pool->ver_top += 1UL<<POOL_IDX_WIDTH;
496 3 : FD_COMPILER_MFENCE();
497 3 : }
498 :
499 : POOL_STATIC void * POOL_(new) ( void * shmem );
500 : POOL_STATIC POOL_(t) * POOL_(join) ( void * ljoin, void * shpool, void * shele, ulong ele_max );
501 : POOL_STATIC void * POOL_(leave) ( POOL_(t) * join );
502 : POOL_STATIC void * POOL_(delete)( void * shpool );
503 :
504 : POOL_STATIC POOL_ELE_T * POOL_(acquire)( POOL_(t) * join, POOL_ELE_T * sentinel, int blocking, int * _opt_err );
505 :
506 : POOL_STATIC int POOL_(release)( POOL_(t) * join, POOL_ELE_T * ele, int blocking );
507 :
508 : POOL_STATIC int POOL_(is_empty)( POOL_(t) * join );
509 :
510 : POOL_STATIC int POOL_(lock)( POOL_(t) * join, int blocking );
511 :
512 : POOL_STATIC void POOL_(reset)( POOL_(t) * join, ulong sentinel_cnt );
513 :
514 : POOL_STATIC int POOL_(verify)( POOL_(t) const * join );
515 :
516 : POOL_STATIC FD_FN_CONST char const * POOL_(strerror)( int err );
517 :
518 : FD_PROTOTYPES_END
519 :
520 : #endif
521 :
522 : #if POOL_IMPL_STYLE!=1 /* need implementations (assumes header already included) */
523 :
524 : #include "../log/fd_log.h" /* used by constructors and verify (FIXME: Consider making a compile time option) */
525 :
526 : POOL_STATIC void *
527 84 : POOL_(new)( void * shmem ) {
528 84 : POOL_(shmem_t) * pool = (POOL_(shmem_t) *)shmem;
529 :
530 84 : if( FD_UNLIKELY( !pool ) ) {
531 3 : FD_LOG_WARNING(( "NULL shmem" ));
532 3 : return NULL;
533 3 : }
534 :
535 81 : if( FD_UNLIKELY( !fd_ulong_is_aligned( (ulong)pool, POOL_(align)() ) ) ) {
536 3 : FD_LOG_WARNING(( "misaligned shmem" ));
537 3 : return NULL;
538 3 : }
539 :
540 78 : pool->ver_top = POOL_(private_vidx)( 0UL, POOL_(idx_null)() );
541 :
542 78 : FD_COMPILER_MFENCE();
543 78 : pool->magic = POOL_MAGIC;
544 78 : FD_COMPILER_MFENCE();
545 :
546 78 : return (void *)pool;
547 81 : }
548 :
549 : POOL_STATIC POOL_(t) *
550 : POOL_(join)( void * ljoin,
551 : void * shpool,
552 : void * shele,
553 174 : ulong ele_max ) {
554 174 : POOL_(t) * join = (POOL_(t) *)ljoin;
555 174 : POOL_(shmem_t) * pool = (POOL_(shmem_t) *)shpool;
556 174 : POOL_ELE_T * ele = (POOL_ELE_T *)shele;
557 :
558 174 : if( FD_UNLIKELY( !join ) ) {
559 3 : FD_LOG_WARNING(( "NULL ljoin" ));
560 3 : return NULL;
561 3 : }
562 :
563 171 : if( FD_UNLIKELY( !fd_ulong_is_aligned( (ulong)join, alignof(POOL_(t)) ) ) ) {
564 3 : FD_LOG_WARNING(( "misaligned ljoin" ));
565 3 : return NULL;
566 3 : }
567 :
568 168 : if( FD_UNLIKELY( !pool ) ) {
569 3 : FD_LOG_WARNING(( "NULL shpool" ));
570 3 : return NULL;
571 3 : }
572 :
573 165 : if( FD_UNLIKELY( !fd_ulong_is_aligned( (ulong)pool, POOL_(align)() ) ) ) {
574 3 : FD_LOG_WARNING(( "misaligned shpool" ));
575 3 : return NULL;
576 3 : }
577 :
578 162 : if( FD_UNLIKELY( pool->magic!=POOL_MAGIC ) ) {
579 3 : FD_LOG_WARNING(( "bad magic" ));
580 3 : return NULL;
581 3 : }
582 :
583 159 : if( FD_UNLIKELY( (!ele) & (!!ele_max) ) ) {
584 3 : FD_LOG_WARNING(( "NULL shele" ));
585 3 : return NULL;
586 3 : }
587 :
588 156 : if( FD_UNLIKELY( !fd_ulong_is_aligned( (ulong)ele, alignof(POOL_ELE_T) ) ) ) {
589 3 : FD_LOG_WARNING(( "misaligned shele" ));
590 3 : return NULL;
591 3 : }
592 :
593 153 : if( FD_UNLIKELY( ele_max>POOL_(ele_max_max)() ) ) {
594 6 : FD_LOG_WARNING(( "bad ele_max" ));
595 6 : return NULL;
596 6 : }
597 :
598 147 : join->pool = pool;
599 147 : join->ele = ele;
600 147 : join->ele_max = ele_max;
601 :
602 147 : return join;
603 153 : }
604 :
605 : POOL_STATIC void *
606 18 : POOL_(leave)( POOL_(t) * join ) {
607 :
608 18 : if( FD_UNLIKELY( !join ) ) {
609 3 : FD_LOG_WARNING(( "NULL join" ));
610 3 : return NULL;
611 3 : }
612 :
613 15 : return (void *)join;
614 18 : }
615 :
616 : POOL_STATIC void *
617 18 : POOL_(delete)( void * shpool ) {
618 18 : POOL_(shmem_t) * pool = (POOL_(shmem_t) *)shpool;
619 :
620 18 : if( FD_UNLIKELY( !pool) ) {
621 3 : FD_LOG_WARNING(( "NULL shpool" ));
622 3 : return NULL;
623 3 : }
624 :
625 15 : if( FD_UNLIKELY( !fd_ulong_is_aligned( (ulong)pool, POOL_(align)() ) ) ) {
626 3 : FD_LOG_WARNING(( "misaligned shpool" ));
627 3 : return NULL;
628 3 : }
629 :
630 12 : if( FD_UNLIKELY( pool->magic!=POOL_MAGIC ) ) {
631 3 : FD_LOG_WARNING(( "bad magic" ));
632 3 : return NULL;
633 3 : }
634 :
635 9 : FD_COMPILER_MFENCE();
636 9 : pool->magic = 0UL;
637 9 : FD_COMPILER_MFENCE();
638 :
639 9 : return (void *)pool;
640 12 : }
641 :
642 : POOL_STATIC POOL_ELE_T *
643 : POOL_(acquire)( POOL_(t) * join,
644 : POOL_ELE_T * sentinel,
645 : int blocking,
646 221725611 : int * _opt_err ) {
647 221725611 : POOL_ELE_T * ele0 = join->ele;
648 221725611 : ulong ele_max = join->ele_max;
649 221725611 : ulong volatile * _v = (ulong volatile *)&join->pool->ver_top;
650 :
651 221725611 : POOL_ELE_T * ele = sentinel;
652 221725611 : int err = FD_POOL_SUCCESS;
653 :
654 221725611 : FD_COMPILER_MFENCE();
655 :
656 221725792 : for(;;) {
657 221725792 : ulong ver_top = *_v;
658 :
659 221725792 : ulong ver = POOL_(private_vidx_ver)( ver_top );
660 221725792 : ulong ele_idx = POOL_(private_vidx_idx)( ver_top );
661 :
662 221725792 : if( FD_LIKELY( !(ver & 1UL) ) ) { /* opt for unlocked */
663 :
664 221725792 : if( FD_UNLIKELY( POOL_(idx_is_null)( ele_idx ) ) ) { /* opt for not empty */
665 193465728 : err = FD_POOL_ERR_EMPTY;
666 193465728 : break;
667 193465728 : }
668 :
669 28260064 : if( FD_UNLIKELY( ele_idx>=ele_max ) ) { /* opt for not corrupt */
670 0 : err = FD_POOL_ERR_CORRUPT;
671 0 : break;
672 0 : }
673 :
674 28260064 : ulong ele_nxt = POOL_(private_idx)( ele0[ ele_idx ].POOL_NEXT );
675 :
676 28260064 : if( FD_UNLIKELY( (ele_nxt>=ele_max) & (!POOL_(idx_is_null)( ele_nxt )) ) ) { /* ele_nxt is invalid, opt for valid */
677 : /* It is possible that another thread acquired ele_idx and
678 : repurposed ele_idx's POOL_NEXT (storing something in it that
679 : isn't a valid pool value) between when we read ver_top and
680 : when we read ele_idx's POOL_NEXT above. If so, the pool
681 : version would be changed from what we read above. We thus
682 : only signal ERR_CORRUPT if the version number hasn't changed
683 : since we read it. */
684 :
685 0 : if( FD_UNLIKELY( POOL_(private_vidx_ver)( *_v )==ver ) ) {
686 0 : err = FD_POOL_ERR_CORRUPT;
687 0 : break;
688 0 : }
689 28260064 : } else { /* ele_nxt is valid */
690 28260064 : ulong new_ver_top = POOL_(private_vidx)( ver+2UL, ele_nxt );
691 :
692 28260064 : if( FD_LIKELY( POOL_(private_cas)( _v, ver_top, new_ver_top )==ver_top ) ) { /* opt for low contention */
693 28259883 : ele = ele0 + ele_idx;
694 28259883 : break;
695 28259883 : }
696 28260064 : }
697 28260064 : } else if( FD_UNLIKELY( !blocking ) ) { /* opt for blocking */
698 :
699 0 : err = FD_POOL_ERR_AGAIN;
700 0 : break; /* opt for blocking */
701 :
702 0 : }
703 :
704 181 : FD_SPIN_PAUSE();
705 181 : }
706 :
707 221725611 : FD_COMPILER_MFENCE();
708 :
709 221725611 : fd_int_store_if( !!_opt_err, _opt_err, err );
710 : #ifdef POOL_MARK_NOT_IN_POOL
711 216260442 : if( ele != sentinel ) POOL_MARK_NOT_IN_POOL( ele );
712 : #endif
713 221725611 : return ele;
714 221725611 : }
715 :
716 : POOL_STATIC int
717 : POOL_(release)( POOL_(t) * join,
718 : POOL_ELE_T * ele,
719 25109470 : int blocking ) {
720 25109470 : ulong ele_max = join->ele_max;
721 25109470 : ulong volatile * _v = (ulong volatile *)&join->pool->ver_top;
722 :
723 25109470 : ulong ele_idx = (ulong)(ele - join->ele);
724 25109470 : if( FD_UNLIKELY( ele_idx>=ele_max ) ) return FD_POOL_ERR_INVAL; /* opt for valid call */
725 :
726 : #ifdef POOL_MARK_IN_POOL
727 19945230 : POOL_MARK_IN_POOL( ele );
728 19945230 : #endif
729 :
730 25108693 : int err = FD_POOL_SUCCESS;
731 :
732 25108693 : FD_COMPILER_MFENCE();
733 :
734 25108693 : for(;;) {
735 25108693 : ulong ver_top = *_v;
736 :
737 25108693 : ulong ver = POOL_(private_vidx_ver)( ver_top );
738 25108693 : ulong ele_nxt = POOL_(private_vidx_idx)( ver_top );
739 :
740 25108693 : if( FD_LIKELY( !(ver & 1UL) ) ) { /* opt for unlocked */
741 :
742 25108693 : if( FD_UNLIKELY( (ele_nxt>=ele_max) & (!POOL_(idx_is_null)( ele_nxt )) ) ) { /* opt for not corrupt */
743 0 : err = FD_POOL_ERR_CORRUPT;
744 0 : break;
745 0 : }
746 :
747 25108693 : ele->POOL_NEXT = POOL_(private_cidx)( ele_nxt );
748 :
749 25108693 : ulong new_ver_top = POOL_(private_vidx)( ver+2UL, ele_idx );
750 :
751 25108693 : if( FD_LIKELY( POOL_(private_cas)( _v, ver_top, new_ver_top )==ver_top ) ) break; /* opt for low contention */
752 :
753 25108693 : } else if( FD_UNLIKELY( !blocking ) ) { /* opt for blocking */
754 :
755 0 : err = FD_POOL_ERR_AGAIN;
756 0 : break;
757 :
758 0 : }
759 :
760 0 : FD_SPIN_PAUSE();
761 0 : }
762 :
763 25108693 : FD_COMPILER_MFENCE();
764 :
765 5163463 : return err;
766 25109470 : }
767 :
768 : POOL_STATIC int
769 25059918 : POOL_(is_empty)( POOL_(t) * join ) {
770 25059918 : ulong ver_top = join->pool->ver_top;
771 25059918 : ulong ele_idx = POOL_(private_vidx_idx)( ver_top );
772 25059918 : return POOL_(idx_is_null)( ele_idx );
773 25059918 : }
774 :
775 : POOL_STATIC int
776 : POOL_(lock)( POOL_(t) * join,
777 6 : int blocking ) {
778 6 : ulong volatile * _v = (ulong volatile *)&join->pool->ver_top;
779 :
780 6 : int err = FD_POOL_SUCCESS;
781 :
782 6 : FD_COMPILER_MFENCE();
783 :
784 6 : for(;;) {
785 :
786 : /* use a test-and-test-and-set style for reduced contention */
787 :
788 6 : ulong ver_top = *_v;
789 6 : if( FD_LIKELY( !(ver_top & (1UL<<POOL_IDX_WIDTH)) ) ) { /* opt for low contention */
790 3 : ver_top = POOL_(private_fetch_and_or)( _v, 1UL<<POOL_IDX_WIDTH );
791 3 : if( FD_LIKELY( !(ver_top & (1UL<<POOL_IDX_WIDTH)) ) ) break; /* opt for low contention */
792 3 : }
793 :
794 3 : if( FD_UNLIKELY( !blocking ) ) { /* opt for blocking */
795 3 : err = FD_POOL_ERR_AGAIN;
796 3 : break;
797 3 : }
798 :
799 0 : FD_SPIN_PAUSE();
800 0 : }
801 :
802 6 : FD_COMPILER_MFENCE();
803 :
804 6 : return err;
805 6 : }
806 :
807 : POOL_STATIC void
808 : POOL_(reset)( POOL_(t) * join,
809 81 : ulong sentinel_cnt ) {
810 81 : POOL_(shmem_t) * pool = join->pool;
811 81 : POOL_ELE_T * ele = join->ele;
812 81 : ulong ele_max = join->ele_max;
813 :
814 : /* Insert all but the leading sentinel_cnt elements in increasing
815 : order */
816 :
817 81 : ulong ele_top;
818 :
819 81 : if( FD_UNLIKELY( sentinel_cnt>=ele_max ) ) ele_top = POOL_(idx_null)(); /* All items are sentinels */
820 63 : else { /* Note: ele_max at least 1 here */
821 63 : ele_top = sentinel_cnt;
822 9653517 : for( ulong ele_idx=ele_top; ele_idx<(ele_max-1UL); ele_idx++ ) {
823 : #ifdef POOL_MARK_IN_POOL
824 8065989 : POOL_MARK_IN_POOL( &ele[ ele_idx ] );
825 : #endif
826 9653454 : ele[ ele_idx ].POOL_NEXT = POOL_(private_cidx)( ele_idx+1UL );
827 9653454 : }
828 : #ifdef POOL_MARK_IN_POOL
829 27 : POOL_MARK_IN_POOL( &ele[ ele_max-1UL ] );
830 : #endif
831 63 : ele[ ele_max-1UL ].POOL_NEXT = POOL_(private_cidx)( POOL_(idx_null)() );
832 63 : }
833 :
834 81 : ulong ver_top = pool->ver_top;
835 81 : ulong ver = POOL_(private_vidx_ver)( ver_top );
836 81 : pool->ver_top = POOL_(private_vidx)( ver, ele_top );
837 81 : }
838 :
839 : POOL_STATIC int
840 51 : POOL_(verify)( POOL_(t) const * join ) {
841 :
842 3149256 : # define POOL_TEST(c) do { \
843 3149256 : if( FD_UNLIKELY( !(c) ) ) { FD_LOG_WARNING(( "FAIL: %s", #c )); return FD_POOL_ERR_CORRUPT; } \
844 3149256 : } while(0)
845 :
846 : /* Validate join */
847 :
848 51 : POOL_TEST( join );
849 51 : POOL_TEST( fd_ulong_is_aligned( (ulong)join, alignof(POOL_(t)) ) );
850 :
851 51 : POOL_(shmem_t) const * pool = join->pool;
852 51 : POOL_ELE_T const * ele = join->ele;
853 51 : ulong ele_max = join->ele_max;
854 :
855 51 : POOL_TEST( pool );
856 51 : POOL_TEST( fd_ulong_is_aligned( (ulong)pool, POOL_(align)() ) );
857 :
858 51 : POOL_TEST( (!!ele)| (!ele_max) );
859 51 : POOL_TEST( fd_ulong_is_aligned( (ulong)ele, alignof(POOL_ELE_T) ) );
860 :
861 51 : POOL_TEST( ele_max<=POOL_(ele_max_max)() );
862 :
863 : /* Validate pool metadata */
864 :
865 51 : ulong magic = pool->magic;
866 51 : ulong ver_top = pool->ver_top;
867 :
868 : /* version arbitrary as far as verify is concerned */
869 51 : ulong ele_idx = POOL_(private_vidx_idx)( ver_top );
870 :
871 51 : POOL_TEST( magic==POOL_MAGIC );
872 :
873 : /* Validate pool elements */
874 :
875 51 : ulong ele_rem = ele_max;
876 3148848 : while( ele_idx<ele_max ) {
877 3148797 : POOL_TEST( ele_rem ); ele_rem--; /* no cycles */
878 3148797 : ele_idx = POOL_(private_idx)( ele[ ele_idx ].POOL_NEXT );
879 3148797 : }
880 :
881 51 : POOL_TEST( POOL_(idx_is_null)( ele_idx ) );
882 :
883 51 : # undef POOL_TEST
884 :
885 51 : return FD_POOL_SUCCESS;
886 51 : }
887 :
888 : POOL_STATIC char const *
889 18 : POOL_(strerror)( int err ) {
890 18 : switch( err ) {
891 3 : case FD_POOL_SUCCESS: return "success";
892 3 : case FD_POOL_ERR_INVAL: return "bad input";
893 3 : case FD_POOL_ERR_AGAIN: return "try again";
894 3 : case FD_POOL_ERR_CORRUPT: return "corruption detected";
895 3 : case FD_POOL_ERR_EMPTY: return "pool empty";
896 3 : default: break;
897 18 : }
898 3 : return "unknown";
899 18 : }
900 :
901 : #endif
902 :
903 : #undef POOL_
904 : #undef POOL_STATIC
905 : #undef POOL_VER_WIDTH
906 :
907 : #undef POOL_IMPL_STYLE
908 : #undef POOL_MAGIC
909 : #undef POOL_IDX_WIDTH
910 : #undef POOL_ALIGN
911 : #undef POOL_NEXT
912 : #undef POOL_IDX_T
913 : #undef POOL_ELE_T
914 : #undef POOL_NAME
|
