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 been tweaked to support locked pool operations
13 : like initialization (and thus this can also be used without changes
14 : as a more conventional spin lock based concurrent stack).
15 : Unsurprisingly, the current implementation is equally usable as a
16 : concurrent element stack (though the implementation may be changed in
17 : the future to better support ultra high contention ultra high
18 : concurrency ala 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 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 a
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 a 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 29295030 : #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 6 : #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 : /* Commom 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 8523852 : #define FD_POOL_SUCCESS ( 0)
331 780 : #define FD_POOL_ERR_INVAL (-1)
332 3675 : #define FD_POOL_ERR_AGAIN (-2)
333 3 : #define FD_POOL_ERR_CORRUPT (-3)
334 303681 : #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 17047776 : #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 46137543 : #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 8220165 : FD_FN_CONST static inline ulong POOL_(private_vidx)( ulong ver, ulong idx ) { return (ver<<POOL_IDX_WIDTH) | idx; }
386 :
387 8523840 : FD_FN_CONST static inline ulong POOL_(private_vidx_ver)( ulong ver_idx ) { return ver_idx >> POOL_IDX_WIDTH; }
388 8523888 : 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 4119282 : FD_FN_CONST static inline POOL_IDX_T POOL_(private_cidx)( ulong idx ) { return (POOL_IDX_T) idx; }
394 4113138 : 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 8220138 : ulong s ) {
405 8220138 : ulong o;
406 8220138 : FD_COMPILER_MFENCE();
407 8220138 : # if FD_HAS_ATOMIC
408 8220138 : o = FD_ATOMIC_CAS( p, c, s );
409 : # else
410 : o = *p;
411 : *p = fd_ulong_if( o==c, s, c );
412 : # endif
413 8220138 : FD_COMPILER_MFENCE();
414 8220138 : return o;
415 8220138 : }
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 0 : FD_FN_CONST static inline ulong POOL_(ele_max_max)( void ) { return (ulong)(POOL_IDX_T)(ULONG_MAX >> POOL_VER_WIDTH); }
433 :
434 0 : FD_FN_CONST static inline ulong POOL_(align) ( void ) { return alignof(POOL_(shmem_t)); }
435 0 : 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 4981137 : 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 0 : FD_FN_CONST static inline ulong POOL_(idx_null)( void ) { return (ulong)(POOL_IDX_T)(ULONG_MAX >> POOL_VER_WIDTH); }
445 12636990 : 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 18067218 : POOL_ELE_T const * ele ) {
450 18067218 : ulong ele_idx = (ulong)(ele - join->ele);
451 18067218 : return ele_idx<join->ele_max ? ele_idx : POOL_(idx_null)();
452 18067218 : }
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 3078 : ulong ele_idx ) {
464 3078 : POOL_ELE_T * ele = join->ele;
465 3078 : return (ele_idx < join->ele_max) ? (ele + ele_idx) : NULL;
466 3078 : }
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 18 : POOL_(new)( void * shmem ) {
528 18 : POOL_(shmem_t) * pool = (POOL_(shmem_t) *)shmem;
529 :
530 18 : if( FD_UNLIKELY( !pool ) ) {
531 3 : FD_LOG_WARNING(( "NULL shmem" ));
532 3 : return NULL;
533 3 : }
534 :
535 15 : 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 12 : pool->ver_top = POOL_(private_vidx)( 0UL, POOL_(idx_null)() );
541 :
542 12 : FD_COMPILER_MFENCE();
543 12 : pool->magic = POOL_MAGIC;
544 12 : FD_COMPILER_MFENCE();
545 :
546 12 : return (void *)pool;
547 15 : }
548 :
549 : POOL_STATIC POOL_(t) *
550 : POOL_(join)( void * ljoin,
551 : void * shpool,
552 : void * shele,
553 42 : ulong ele_max ) {
554 42 : POOL_(t) * join = (POOL_(t) *)ljoin;
555 42 : POOL_(shmem_t) * pool = (POOL_(shmem_t) *)shpool;
556 42 : POOL_ELE_T * ele = (POOL_ELE_T *)shele;
557 :
558 42 : if( FD_UNLIKELY( !join ) ) {
559 3 : FD_LOG_WARNING(( "NULL ljoin" ));
560 3 : return NULL;
561 3 : }
562 :
563 39 : 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 36 : if( FD_UNLIKELY( !pool ) ) {
569 3 : FD_LOG_WARNING(( "NULL shpool" ));
570 3 : return NULL;
571 3 : }
572 :
573 33 : 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 30 : if( FD_UNLIKELY( pool->magic!=POOL_MAGIC ) ) {
579 3 : FD_LOG_WARNING(( "bad magic" ));
580 3 : return NULL;
581 3 : }
582 :
583 27 : if( FD_UNLIKELY( (!ele) & (!!ele_max) ) ) {
584 3 : FD_LOG_WARNING(( "NULL shele" ));
585 3 : return NULL;
586 3 : }
587 :
588 24 : 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 21 : 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 15 : join->pool = pool;
599 15 : join->ele = ele;
600 15 : join->ele_max = ele_max;
601 :
602 15 : return join;
603 21 : }
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 4413747 : int * _opt_err ) {
647 4413747 : POOL_ELE_T * ele0 = join->ele;
648 4413747 : ulong ele_max = join->ele_max;
649 4413747 : ulong volatile * _v = (ulong volatile *)&join->pool->ver_top;
650 :
651 4413747 : POOL_ELE_T * ele = sentinel;
652 4413747 : int err = FD_POOL_SUCCESS;
653 :
654 4413747 : FD_COMPILER_MFENCE();
655 :
656 4413747 : for(;;) {
657 4413747 : ulong ver_top = *_v;
658 :
659 4413747 : ulong ver = POOL_(private_vidx_ver)( ver_top );
660 4413747 : ulong ele_idx = POOL_(private_vidx_idx)( ver_top );
661 :
662 4413747 : if( FD_LIKELY( !(ver & 1UL) ) ) { /* opt for unlocked */
663 :
664 4413747 : if( FD_UNLIKELY( POOL_(idx_is_null)( ele_idx ) ) ) { /* opt for not empty */
665 303678 : err = FD_POOL_ERR_EMPTY;
666 303678 : break;
667 303678 : }
668 :
669 4110069 : 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 4110069 : ulong ele_nxt = POOL_(private_idx)( ele0[ ele_idx ].POOL_NEXT );
675 :
676 4110069 : if( FD_UNLIKELY( (ele_nxt>=ele_max) & (!POOL_(idx_is_null)( ele_nxt )) ) ) { /* opt for not corrupt */
677 0 : err = FD_POOL_ERR_CORRUPT;
678 0 : break;
679 0 : }
680 :
681 4110069 : ulong new_ver_top = POOL_(private_vidx)( ver+2UL, ele_nxt );
682 :
683 4110069 : if( FD_LIKELY( POOL_(private_cas)( _v, ver_top, new_ver_top )==ver_top ) ) { /* opt for low contention */
684 4110069 : ele = ele0 + ele_idx;
685 4110069 : break;
686 4110069 : }
687 :
688 4110069 : } else if( FD_UNLIKELY( !blocking ) ) { /* opt for blocking */
689 :
690 0 : err = FD_POOL_ERR_AGAIN;
691 0 : break; /* opt for blocking */
692 :
693 0 : }
694 :
695 0 : FD_SPIN_PAUSE();
696 0 : }
697 :
698 4413747 : FD_COMPILER_MFENCE();
699 :
700 4413747 : fd_int_store_if( !!_opt_err, _opt_err, err );
701 4413747 : return ele;
702 4413747 : }
703 :
704 : POOL_STATIC int
705 : POOL_(release)( POOL_(t) * join,
706 : POOL_ELE_T * ele,
707 4110846 : int blocking ) {
708 4110846 : ulong ele_max = join->ele_max;
709 4110846 : ulong volatile * _v = (ulong volatile *)&join->pool->ver_top;
710 :
711 4110846 : ulong ele_idx = (ulong)(ele - join->ele);
712 :
713 4110846 : if( FD_UNLIKELY( ele_idx>=ele_max ) ) return FD_POOL_ERR_INVAL; /* opt for valid call */
714 :
715 4110069 : int err = FD_POOL_SUCCESS;
716 :
717 4110069 : FD_COMPILER_MFENCE();
718 :
719 4110069 : for(;;) {
720 4110069 : ulong ver_top = *_v;
721 :
722 4110069 : ulong ver = POOL_(private_vidx_ver)( ver_top );
723 4110069 : ulong ele_nxt = POOL_(private_vidx_idx)( ver_top );
724 :
725 4110069 : if( FD_LIKELY( !(ver & 1UL) ) ) { /* opt for unlocked */
726 :
727 4110069 : if( FD_UNLIKELY( (ele_nxt>=ele_max) & (!POOL_(idx_is_null)( ele_nxt )) ) ) { /* opt for not corrupt */
728 0 : err = FD_POOL_ERR_CORRUPT;
729 0 : break;
730 0 : }
731 :
732 4110069 : ele->POOL_NEXT = POOL_(private_cidx)( ele_nxt );
733 :
734 4110069 : ulong new_ver_top = POOL_(private_vidx)( ver+2UL, ele_idx );
735 :
736 4110069 : if( FD_LIKELY( POOL_(private_cas)( _v, ver_top, new_ver_top )==ver_top ) ) break; /* opt for low contention */
737 :
738 4110069 : } else if( FD_UNLIKELY( !blocking ) ) { /* opt for blocking */
739 :
740 0 : err = FD_POOL_ERR_AGAIN;
741 0 : break;
742 :
743 0 : }
744 :
745 0 : FD_SPIN_PAUSE();
746 0 : }
747 :
748 4110069 : FD_COMPILER_MFENCE();
749 :
750 4110069 : return err;
751 4110846 : }
752 :
753 : POOL_STATIC int
754 0 : POOL_(is_empty)( POOL_(t) * join ) {
755 0 : ulong ver_top = join->pool->ver_top;
756 0 : ulong ele_idx = POOL_(private_vidx_idx)( ver_top );
757 0 : return POOL_(idx_is_null)( ele_idx );
758 0 : }
759 :
760 : POOL_STATIC int
761 : POOL_(lock)( POOL_(t) * join,
762 6 : int blocking ) {
763 6 : ulong volatile * _v = (ulong volatile *)&join->pool->ver_top;
764 :
765 6 : int err = FD_POOL_SUCCESS;
766 :
767 6 : FD_COMPILER_MFENCE();
768 :
769 6 : for(;;) {
770 :
771 : /* use a test-and-test-and-set style for reduced contention */
772 :
773 6 : ulong ver_top = *_v;
774 6 : if( FD_LIKELY( !(ver_top & (1UL<<POOL_IDX_WIDTH)) ) ) { /* opt for low contention */
775 3 : ver_top = POOL_(private_fetch_and_or)( _v, 1UL<<POOL_IDX_WIDTH );
776 3 : if( FD_LIKELY( !(ver_top & (1UL<<POOL_IDX_WIDTH)) ) ) break; /* opt for low contention */
777 3 : }
778 :
779 3 : if( FD_UNLIKELY( !blocking ) ) { /* opt for blocking */
780 3 : err = FD_POOL_ERR_AGAIN;
781 3 : break;
782 3 : }
783 :
784 0 : FD_SPIN_PAUSE();
785 0 : }
786 :
787 6 : FD_COMPILER_MFENCE();
788 :
789 6 : return err;
790 6 : }
791 :
792 : POOL_STATIC void
793 : POOL_(reset)( POOL_(t) * join,
794 15 : ulong sentinel_cnt ) {
795 15 : POOL_(shmem_t) * pool = join->pool;
796 15 : POOL_ELE_T * ele = join->ele;
797 15 : ulong ele_max = join->ele_max;
798 :
799 : /* Insert all but the leading sentinel_cnt elements in increasing
800 : order */
801 :
802 15 : ulong ele_top;
803 :
804 15 : if( FD_UNLIKELY( sentinel_cnt>=ele_max ) ) ele_top = POOL_(idx_null)(); /* All items are sentinels */
805 9 : else { /* Note: ele_max at least 1 here */
806 9 : ele_top = sentinel_cnt;
807 9213 : for( ulong ele_idx=ele_top; ele_idx<(ele_max-1UL); ele_idx++ )
808 9204 : ele[ ele_idx ].POOL_NEXT = POOL_(private_cidx)( ele_idx+1UL );
809 9 : ele[ ele_max-1UL ].POOL_NEXT = POOL_(private_cidx)( POOL_(idx_null)() );
810 9 : }
811 :
812 15 : ulong ver_top = pool->ver_top;
813 15 : ulong ver = POOL_(private_vidx_ver)( ver_top );
814 15 : pool->ver_top = POOL_(private_vidx)( ver, ele_top );
815 15 : }
816 :
817 : POOL_STATIC int
818 27 : POOL_(verify)( POOL_(t) const * join ) {
819 :
820 3312 : # define POOL_TEST(c) do { \
821 3312 : if( FD_UNLIKELY( !(c) ) ) { FD_LOG_WARNING(( "FAIL: %s", #c )); return FD_POOL_ERR_CORRUPT; } \
822 3312 : } while(0)
823 :
824 : /* Validate join */
825 :
826 27 : POOL_TEST( join );
827 27 : POOL_TEST( fd_ulong_is_aligned( (ulong)join, alignof(POOL_(t)) ) );
828 :
829 27 : POOL_(shmem_t) const * pool = join->pool;
830 27 : POOL_ELE_T const * ele = join->ele;
831 27 : ulong ele_max = join->ele_max;
832 :
833 27 : POOL_TEST( pool );
834 27 : POOL_TEST( fd_ulong_is_aligned( (ulong)pool, POOL_(align)() ) );
835 :
836 27 : POOL_TEST( (!!ele)| (!ele_max) );
837 27 : POOL_TEST( fd_ulong_is_aligned( (ulong)ele, alignof(POOL_ELE_T) ) );
838 :
839 27 : POOL_TEST( ele_max<=POOL_(ele_max_max)() );
840 :
841 : /* Validate pool metadata */
842 :
843 27 : ulong magic = pool->magic;
844 27 : ulong ver_top = pool->ver_top;
845 :
846 : /* version arbitrary as far as verify is concerned */
847 27 : ulong ele_idx = POOL_(private_vidx_idx)( ver_top );
848 :
849 27 : POOL_TEST( magic==POOL_MAGIC );
850 :
851 : /* Validate pool elements */
852 :
853 27 : ulong ele_rem = ele_max;
854 3096 : while( ele_idx<ele_max ) {
855 3069 : POOL_TEST( ele_rem ); ele_rem--; /* no cycles */
856 3069 : ele_idx = POOL_(private_idx)( ele[ ele_idx ].POOL_NEXT );
857 3069 : }
858 :
859 27 : POOL_TEST( POOL_(idx_is_null)( ele_idx ) );
860 :
861 27 : # undef POOL_TEST
862 :
863 27 : return FD_POOL_SUCCESS;
864 27 : }
865 :
866 : POOL_STATIC char const *
867 18 : POOL_(strerror)( int err ) {
868 18 : switch( err ) {
869 3 : case FD_POOL_SUCCESS: return "success";
870 3 : case FD_POOL_ERR_INVAL: return "bad input";
871 3 : case FD_POOL_ERR_AGAIN: return "try again";
872 3 : case FD_POOL_ERR_CORRUPT: return "corruption detected";
873 3 : case FD_POOL_ERR_EMPTY: return "pool empty";
874 3 : default: break;
875 18 : }
876 3 : return "unknown";
877 18 : }
878 :
879 : #endif
880 :
881 : #undef POOL_
882 : #undef POOL_STATIC
883 : #undef POOL_VER_WIDTH
884 :
885 : #undef POOL_IMPL_STYLE
886 : #undef POOL_MAGIC
887 : #undef POOL_IDX_WIDTH
888 : #undef POOL_ALIGN
889 : #undef POOL_NEXT
890 : #undef POOL_IDX_T
891 : #undef POOL_ELE_T
892 : #undef POOL_NAME
|
