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 returns NULL
162 : // On success, the returned value will be a pointer in the caller's
163 : // address space to the element store element acquired from the
164 : // mypool. On failure, the value returned will be NULL and the
165 : // mypool will be unchanged. Failure can occur if the mypool
166 : // contained no elements at some point during the call.
167 :
168 : myele_t * mypool_acquire( mypool_t * join );
169 :
170 : // mypool_acquire_nolock does an atomic-unsafe acquire.
171 : // Assumes that the current thread is the only pool user.
172 : // U.B. if other threads access the pool concurrently.
173 :
174 : myele_t * mypool_acquire_nolock( mypool_t * join );
175 :
176 : // mypool_acquire_batch acquires exactly cnt elements from a mypool
177 : // and stores pointers to them in out[0,cnt). Assumes join is a
178 : // current local join and out has room for cnt pointers. cnt==0 is
179 : // a no-op that returns NULL. Elements come from the free stack
180 : // first (LIFO), then, if POOL_LAZY, from the lazy region
181 : // (ascending). On success, returns out. If the pool runs
182 : // short, returns acquired elements to the pool and returns NULL.
183 : //
184 : // Acquired elements are independent: any subset can be handed back
185 : // with mypool_release.
186 :
187 : myele_t ** mypool_acquire_batch( mypool_t * join, ulong cnt, myele_t * out[] );
188 :
189 : // mypool_release releases an element to a mypoool. Assumes join
190 : // is a current local join, ele is a pointer in the caller's
191 : // address space to the element, and the element is currently not
192 : // in the mypool.
193 :
194 : void mypool_release( mypool_t * join, myele_t * ele );
195 :
196 : // mypool_release_chain splices a singly-linked chain of elements
197 : // back into the mypool free stack in a single CAS. head is a
198 : // pointer to the first element of the chain and tail is a pointer
199 : // to the last. The chain must be linked via POOL_NEXT (i.e.
200 : // head->next -> ... -> tail). tail's next pointer will be
201 : // overwritten to point at the current stack top. Assumes join is
202 : // a current local join, head and tail are valid elements in the
203 : // element store, the chain is non-empty, and none of the elements
204 : // are currently in the mypool.
205 :
206 : void mypool_release_chain( mypool_t * join, myele_t * head, myele_t * tail );
207 :
208 : // mypool_is_empty returns 1 if the mypool has no elements available
209 : // for acquire and 0 otherwise. Observation is a point-in-time
210 : // sample; concurrent acquire / release operations may change the
211 : // result immediately after. Assumes join is a current local join.
212 :
213 : int mypool_is_empty( mypool_t * join );
214 :
215 : // mypool_lock will lock a mypool (e.g. pausing concurrent acquire
216 : // / release operations). A non-zero / zero value for blocking
217 : // indicates the call should / should not wait to lock the mypool
218 : // if it is currently locked. Returns FD_POOL_SUCCESS on success
219 : // (caller has the lock on return) and FD_POOL_ERR_AGAIN on failure
220 : // (pool was already locked at some point during the call). AGAIN
221 : // is never returned if blocking is requested. Assumes join is a
222 : // current local join.
223 :
224 : int mypool_lock( mypool_t * join, int blocking );
225 :
226 : // mypool_unlock will unlock a mypool (e.g. resuming concurrent
227 : // acquire / release operations). Assumes join is a current local
228 : // join and the caller has a lock on mypool. Guaranteed to
229 : // succeed.
230 :
231 : void mypool_unlock( mypool_t * join );
232 :
233 : // mypool_reset resets the mypool. On return, it will hold all
234 : // elements in the element store (e.g. initialization after
235 : // creation) in ascending order. Assumes join is a current local
236 : // join and the mypool is locked or otherwise idle.
237 :
238 : void mypool_reset( mypool_t * join );
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 0 : #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 703499 : #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 36 : #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 : /* POOL_LAZY enables lazy initialization for faster startup if defined
327 : to non-zero. Decreases pool_reset cost from O(ele_max) to O(1), at
328 : the cost of more complex allocation logic. */
329 :
330 : #ifndef POOL_LAZY
331 : #define POOL_LAZY 0
332 : #endif
333 :
334 : /* Common pool error codes (FIXME: probably should get around to making
335 : unified error codes and string handling across all util at least so
336 : we don't have to do this in the generator itself) */
337 :
338 0 : #define FD_POOL_SUCCESS ( 0)
339 0 : #define FD_POOL_ERR_AGAIN (-1)
340 0 : #define FD_POOL_ERR_CORRUPT (-2)
341 :
342 : /* Implementation *****************************************************/
343 :
344 3403810 : #define POOL_VER_WIDTH (64-POOL_IDX_WIDTH)
345 :
346 : #if POOL_IMPL_STYLE==0 /* local use only */
347 : #define POOL_STATIC FD_FN_UNUSED static
348 : #else /* library header and/or implementation */
349 : #define POOL_STATIC
350 : #endif
351 :
352 5160455 : #define POOL_(n) FD_EXPAND_THEN_CONCAT3(POOL_NAME,_,n)
353 :
354 : #if POOL_IMPL_STYLE!=2 /* need header */
355 :
356 : #include "../bits/fd_bits.h"
357 :
358 : struct __attribute__((aligned(POOL_ALIGN))) POOL_(shmem_private) {
359 :
360 : /* Note: there is no free count because that that isn't precisely
361 : knowable in a portable concurrent data structure. (Not enough bits
362 : to squeeze into ver_top for large pools, requiring 128-bit wide
363 : ver_top would limit supported targets, etc). */
364 :
365 : ulong magic; /* == POOL_MAGIC */
366 : ulong ver_top; /* Versioned index of the free stack top, top is in [0,ele_max) (not-empty) or is idx_null (empty) */
367 :
368 : # if POOL_LAZY
369 : ulong ver_lazy; /* Versioned index of the lazy init, lazy is in [0,ele_max] (not-empty) or is idx_null (empty) */
370 : # endif
371 :
372 : };
373 :
374 : typedef struct POOL_(shmem_private) POOL_(shmem_t);
375 :
376 : struct POOL_(private) {
377 : POOL_(shmem_t) * pool; /* Pool location in the local address space */
378 : POOL_ELE_T * ele; /* Element store location in the local address space, NULL okay if ele_max==0 */
379 : ulong ele_max; /* Element store capacity, in [0,ele_max_max] */
380 : };
381 :
382 : typedef struct POOL_(private) POOL_(t);
383 :
384 : FD_PROTOTYPES_BEGIN
385 :
386 : /* pool_private_vidx pack ver and idx into a versioned idx. ver is
387 : masked to fit into POOL_VER_WIDTH bits. idx is assumed in
388 : [0,ele_max_max].
389 :
390 : pool_private_vidx_{ver,idx} extract the {version,index} from a
391 : versioned index and will fit into {POOL_VER_WIDTH,POOL_IDX_WIDTH}
392 : bits. */
393 :
394 865328 : FD_FN_CONST static inline ulong POOL_(private_vidx)( ulong ver, ulong idx ) { return (ver<<POOL_IDX_WIDTH) | idx; }
395 :
396 882971 : FD_FN_CONST static inline ulong POOL_(private_vidx_ver)( ulong ver_idx ) { return ver_idx >> POOL_IDX_WIDTH; }
397 881229 : FD_FN_CONST static inline ulong POOL_(private_vidx_idx)( ulong ver_idx ) { return (ver_idx << POOL_VER_WIDTH) >> POOL_VER_WIDTH; }
398 :
399 : /* pool_private_{cidx,idx} compress/decompress a 64-bit in-register
400 : index to/from its in-memory representation. */
401 :
402 440814 : FD_FN_CONST static inline POOL_IDX_T POOL_(private_cidx)( ulong idx ) { return (POOL_IDX_T) idx; }
403 781291 : FD_FN_CONST static inline ulong POOL_(private_idx) ( ulong cidx ) { return (ulong) cidx; }
404 :
405 : /* pool_private_cas does a ulong FD_ATOMIC_CAS when FD_HAS_ATOMIC
406 : support is available and emulates it when not. Similarly for
407 : pool_private_fetch_and_or. When emulated, the pool will not be safe
408 : to use concurrently (but will still work). */
409 :
410 : static inline ulong
411 : POOL_(private_cas)( ulong volatile * p,
412 : ulong c,
413 865475 : ulong s ) {
414 865475 : ulong o;
415 865475 : FD_COMPILER_MFENCE();
416 865475 : # if FD_HAS_ATOMIC
417 865475 : o = FD_ATOMIC_CAS( p, c, s );
418 : # else
419 : o = *p;
420 : *p = fd_ulong_if( o==c, s, o );
421 : # endif
422 865475 : FD_COMPILER_MFENCE();
423 865475 : return o;
424 865475 : }
425 :
426 : static inline ulong
427 : POOL_(private_fetch_and_or)( ulong volatile * p,
428 0 : ulong b ) {
429 0 : ulong x;
430 0 : FD_COMPILER_MFENCE();
431 0 : # if FD_HAS_ATOMIC
432 0 : x = FD_ATOMIC_FETCH_AND_OR( p, b );
433 : # else
434 : x = *p;
435 : *p = x | b;
436 : # endif
437 0 : FD_COMPILER_MFENCE();
438 0 : return x;
439 0 : }
440 :
441 72 : FD_FN_CONST static inline ulong POOL_(ele_max_max)( void ) { return (ulong)(POOL_IDX_T)(ULONG_MAX >> POOL_VER_WIDTH); }
442 :
443 108 : FD_FN_CONST static inline ulong POOL_(align) ( void ) { return alignof(POOL_(shmem_t)); }
444 0 : FD_FN_CONST static inline ulong POOL_(footprint)( void ) { return sizeof (POOL_(shmem_t)); }
445 :
446 0 : FD_FN_PURE static inline void const * POOL_(shpool_const)( POOL_(t) const * join ) { return join->pool; }
447 0 : FD_FN_PURE static inline void const * POOL_(shele_const) ( POOL_(t) const * join ) { return join->ele; }
448 8346 : FD_FN_PURE static inline ulong POOL_(ele_max) ( POOL_(t) const * join ) { return join->ele_max; }
449 :
450 0 : FD_FN_PURE static inline void * POOL_(shpool)( POOL_(t) * join ) { return join->pool; }
451 0 : FD_FN_PURE static inline void * POOL_(shele) ( POOL_(t) * join ) { return join->ele; }
452 :
453 1641280 : FD_FN_CONST static inline ulong POOL_(idx_null)( void ) { return (ulong)(POOL_IDX_T)(ULONG_MAX >> POOL_VER_WIDTH); }
454 1641541 : FD_FN_CONST static inline int POOL_(idx_is_null)( ulong idx ) { return idx==POOL_(idx_null)(); }
455 :
456 : FD_FN_PURE static inline ulong
457 : POOL_(idx)( POOL_(t) const * join,
458 795923 : POOL_ELE_T const * ele ) {
459 795923 : ulong ele_idx = (ulong)(ele - join->ele);
460 >1844*10^16 : return ele_idx<join->ele_max ? ele_idx : POOL_(idx_null)();
461 795923 : }
462 :
463 : FD_FN_PURE static inline POOL_ELE_T const *
464 : POOL_(ele_const)( POOL_(t) const * join,
465 0 : ulong ele_idx ) {
466 0 : POOL_ELE_T const * ele = join->ele;
467 0 : return (ele_idx < join->ele_max) ? (ele + ele_idx) : NULL;
468 0 : }
469 :
470 : FD_FN_PURE static inline POOL_ELE_T *
471 : POOL_(ele)( POOL_(t) * join,
472 504761 : ulong ele_idx ) {
473 504761 : POOL_ELE_T * ele = join->ele;
474 504761 : return (ele_idx < join->ele_max) ? (ele + ele_idx) : NULL;
475 504761 : }
476 :
477 : static inline POOL_ELE_T const *
478 0 : POOL_(peek_const)( POOL_(t) const * join ) {
479 0 : POOL_(shmem_t) const * pool = join->pool;
480 0 : POOL_ELE_T const * ele = join->ele;
481 0 : ulong ele_max = join->ele_max;
482 0 : FD_COMPILER_MFENCE();
483 0 : ulong ver_top = pool->ver_top;
484 0 : # if POOL_LAZY
485 0 : ulong ver_lazy = pool->ver_lazy;
486 0 : # endif
487 0 : FD_COMPILER_MFENCE();
488 0 : ulong ele_idx = POOL_(private_vidx_idx)( ver_top );
489 0 : # if POOL_LAZY
490 0 : if( ele_idx<ele_max ) {
491 0 : return ele + ele_idx;
492 0 : } else {
493 0 : ulong lazy_idx = POOL_(private_vidx_idx)( ver_lazy );
494 0 : return (lazy_idx<ele_max) ? ele + lazy_idx : NULL;
495 0 : }
496 : # else
497 : return (ele_idx<ele_max) ? ele + ele_idx : NULL;
498 : # endif
499 0 : }
500 :
501 0 : static inline POOL_ELE_T * POOL_(peek)( POOL_(t) * join ) { return (POOL_ELE_T *)POOL_(peek_const)( join ); }
502 :
503 : static inline void
504 0 : POOL_(unlock)( POOL_(t) * join ) {
505 0 : POOL_(shmem_t) * pool = join->pool;
506 0 : FD_COMPILER_MFENCE();
507 0 : pool->ver_top += 1UL<<POOL_IDX_WIDTH;
508 0 : # if POOL_LAZY
509 0 : pool->ver_lazy += 1UL<<POOL_IDX_WIDTH;
510 0 : # endif
511 0 : FD_COMPILER_MFENCE();
512 0 : }
513 :
514 : POOL_STATIC void * POOL_(new) ( void * shmem );
515 : POOL_STATIC POOL_(t) * POOL_(join) ( void * ljoin, void * shpool, void * shele, ulong ele_max );
516 : POOL_STATIC void * POOL_(leave) ( POOL_(t) * join );
517 : POOL_STATIC void * POOL_(delete)( void * shpool );
518 :
519 : POOL_STATIC POOL_ELE_T * POOL_(acquire)( POOL_(t) * join );
520 :
521 : POOL_STATIC POOL_ELE_T * POOL_(acquire_nolock)( POOL_(t) * join );
522 :
523 : POOL_STATIC POOL_ELE_T ** POOL_(acquire_batch)( POOL_(t) * join, ulong cnt, POOL_ELE_T * out[] );
524 :
525 : POOL_STATIC void POOL_(release)( POOL_(t) * join, POOL_ELE_T * ele );
526 :
527 : POOL_STATIC void POOL_(release_chain)( POOL_(t) * join, POOL_ELE_T * head, POOL_ELE_T * tail );
528 :
529 : POOL_STATIC int POOL_(is_empty)( POOL_(t) * join );
530 :
531 : POOL_STATIC int POOL_(lock)( POOL_(t) * join, int blocking );
532 :
533 : POOL_STATIC void POOL_(reset)( POOL_(t) * join );
534 :
535 : POOL_STATIC int POOL_(verify)( POOL_(t) const * join );
536 :
537 : POOL_STATIC FD_FN_CONST char const * POOL_(strerror)( int err );
538 :
539 : FD_PROTOTYPES_END
540 :
541 : #endif
542 :
543 : #if POOL_IMPL_STYLE!=1 /* need implementations (assumes header already included) */
544 :
545 : #include "../log/fd_log.h" /* used by constructors and verify (FIXME: Consider making a compile time option) */
546 :
547 : POOL_STATIC void *
548 36 : POOL_(new)( void * shmem ) {
549 36 : POOL_(shmem_t) * pool = (POOL_(shmem_t) *)shmem;
550 :
551 36 : if( FD_UNLIKELY( !pool ) ) {
552 0 : FD_LOG_WARNING(( "NULL shmem" ));
553 0 : return NULL;
554 0 : }
555 :
556 36 : if( FD_UNLIKELY( !fd_ulong_is_aligned( (ulong)pool, POOL_(align)() ) ) ) {
557 0 : FD_LOG_WARNING(( "misaligned shmem" ));
558 0 : return NULL;
559 0 : }
560 :
561 36 : pool->ver_top = POOL_(private_vidx)( 0UL, POOL_(idx_null)() );
562 : # if POOL_LAZY
563 24 : pool->ver_lazy = POOL_(private_vidx)( 0UL, POOL_(idx_null)() );
564 : # endif
565 :
566 36 : FD_COMPILER_MFENCE();
567 36 : pool->magic = POOL_MAGIC;
568 36 : FD_COMPILER_MFENCE();
569 :
570 36 : return (void *)pool;
571 36 : }
572 :
573 : POOL_STATIC POOL_(t) *
574 : POOL_(join)( void * ljoin,
575 : void * shpool,
576 : void * shele,
577 72 : ulong ele_max ) {
578 72 : POOL_(t) * join = (POOL_(t) *)ljoin;
579 72 : POOL_(shmem_t) * pool = (POOL_(shmem_t) *)shpool;
580 72 : POOL_ELE_T * ele = (POOL_ELE_T *)shele;
581 :
582 72 : if( FD_UNLIKELY( !join ) ) {
583 0 : FD_LOG_WARNING(( "NULL ljoin" ));
584 0 : return NULL;
585 0 : }
586 :
587 72 : if( FD_UNLIKELY( !fd_ulong_is_aligned( (ulong)join, alignof(POOL_(t)) ) ) ) {
588 0 : FD_LOG_WARNING(( "misaligned ljoin" ));
589 0 : return NULL;
590 0 : }
591 :
592 72 : if( FD_UNLIKELY( !pool ) ) {
593 0 : FD_LOG_WARNING(( "NULL shpool" ));
594 0 : return NULL;
595 0 : }
596 :
597 72 : if( FD_UNLIKELY( !fd_ulong_is_aligned( (ulong)pool, POOL_(align)() ) ) ) {
598 0 : FD_LOG_WARNING(( "misaligned shpool" ));
599 0 : return NULL;
600 0 : }
601 :
602 72 : if( FD_UNLIKELY( pool->magic!=POOL_MAGIC ) ) {
603 0 : FD_LOG_WARNING(( "bad magic" ));
604 0 : return NULL;
605 0 : }
606 :
607 72 : if( FD_UNLIKELY( (!ele) & (!!ele_max) ) ) {
608 0 : FD_LOG_WARNING(( "NULL shele" ));
609 0 : return NULL;
610 0 : }
611 :
612 72 : if( FD_UNLIKELY( !fd_ulong_is_aligned( (ulong)ele, alignof(POOL_ELE_T) ) ) ) {
613 0 : FD_LOG_WARNING(( "misaligned shele" ));
614 0 : return NULL;
615 0 : }
616 :
617 72 : if( FD_UNLIKELY( ele_max>POOL_(ele_max_max)() ) ) {
618 0 : FD_LOG_WARNING(( "bad ele_max" ));
619 0 : return NULL;
620 0 : }
621 :
622 72 : join->pool = pool;
623 72 : join->ele = ele;
624 72 : join->ele_max = ele_max;
625 :
626 72 : return join;
627 72 : }
628 :
629 : POOL_STATIC void *
630 36 : POOL_(leave)( POOL_(t) * join ) {
631 :
632 36 : if( FD_UNLIKELY( !join ) ) {
633 0 : FD_LOG_WARNING(( "NULL join" ));
634 0 : return NULL;
635 0 : }
636 :
637 36 : return (void *)join;
638 36 : }
639 :
640 : POOL_STATIC void *
641 0 : POOL_(delete)( void * shpool ) {
642 0 : POOL_(shmem_t) * pool = (POOL_(shmem_t) *)shpool;
643 :
644 0 : if( FD_UNLIKELY( !pool) ) {
645 0 : FD_LOG_WARNING(( "NULL shpool" ));
646 0 : return NULL;
647 0 : }
648 :
649 0 : if( FD_UNLIKELY( !fd_ulong_is_aligned( (ulong)pool, POOL_(align)() ) ) ) {
650 0 : FD_LOG_WARNING(( "misaligned shpool" ));
651 0 : return NULL;
652 0 : }
653 :
654 0 : if( FD_UNLIKELY( pool->magic!=POOL_MAGIC ) ) {
655 0 : FD_LOG_WARNING(( "bad magic" ));
656 0 : return NULL;
657 0 : }
658 :
659 0 : FD_COMPILER_MFENCE();
660 0 : pool->magic = 0UL;
661 0 : FD_COMPILER_MFENCE();
662 :
663 0 : return (void *)pool;
664 0 : }
665 :
666 : #if POOL_LAZY
667 :
668 : /* pool_acquire_lazy acquires up to cnt elements from the lazy region in
669 : a single CAS, storing them in out[0,n) in ascending index order.
670 : Returns n in [0,cnt]; n<cnt iff the lazy region ran out. Assumes
671 : cnt>0. */
672 :
673 : static inline ulong
674 : POOL_(acquire_lazy)( POOL_(t) * join,
675 : ulong cnt,
676 6655 : POOL_ELE_T * out[] ) {
677 6655 : POOL_ELE_T * ele0 = join->ele;
678 6655 : ulong ele_max = join->ele_max;
679 6655 : ulong volatile * _l = (ulong volatile *)&join->pool->ver_lazy;
680 :
681 6655 : ulong n = 0UL;
682 :
683 6655 : FD_COMPILER_MFENCE();
684 :
685 6655 : for(;;) {
686 6649 : ulong ver_lazy = *_l;
687 :
688 6649 : ulong ver = POOL_(private_vidx_ver)( ver_lazy );
689 6649 : ulong ele_idx = POOL_(private_vidx_idx)( ver_lazy );
690 :
691 6649 : if( FD_LIKELY( !(ver & 1UL) ) ) { /* opt for unlocked */
692 :
693 6641 : if( FD_UNLIKELY( POOL_(idx_is_null)( ele_idx ) ) ) { /* opt for not empty */
694 0 : break;
695 0 : }
696 :
697 6641 : if( FD_UNLIKELY( ele_idx>=ele_max ) ) {
698 0 : FD_LOG_CRIT(( "corruption detected (ele_idx=%lu ele_max=%lu)", ele_idx, ele_max ));
699 0 : }
700 :
701 6641 : ulong ele_cnt = fd_ulong_min( cnt, ele_max-ele_idx );
702 6641 : ulong ele_nxt = ele_idx+ele_cnt;
703 6641 : if( FD_UNLIKELY( ele_nxt>=ele_max ) ) ele_nxt = POOL_(idx_null)();
704 :
705 6641 : ulong new_ver_lazy = POOL_(private_vidx)( ver+2UL, ele_nxt );
706 6641 : if( FD_LIKELY( POOL_(private_cas)( _l, ver_lazy, new_ver_lazy )==ver_lazy ) ) { /* opt for low contention */
707 13190 : for( ; n<ele_cnt; n++ ) out[ n ] = ele0 + ele_idx + n;
708 6581 : break;
709 6581 : }
710 6641 : }
711 :
712 68 : FD_SPIN_PAUSE();
713 68 : }
714 :
715 6655 : FD_COMPILER_MFENCE();
716 :
717 6655 : return n;
718 6655 : }
719 :
720 : #endif /* POOL_LAZY */
721 :
722 : POOL_STATIC POOL_ELE_T *
723 799793 : POOL_(acquire)( POOL_(t) * join ) {
724 799793 : POOL_ELE_T * ele0 = join->ele;
725 799793 : ulong ele_max = join->ele_max;
726 799793 : ulong volatile * _v = (ulong volatile *)&join->pool->ver_top;
727 :
728 799793 : POOL_ELE_T * ele = NULL;
729 :
730 799793 : FD_COMPILER_MFENCE();
731 :
732 799793 : for(;;) {
733 796665 : ulong ver_top = *_v;
734 :
735 796665 : ulong ver = POOL_(private_vidx_ver)( ver_top );
736 796665 : ulong ele_idx = POOL_(private_vidx_idx)( ver_top );
737 :
738 796665 : if( FD_LIKELY( !(ver & 1UL) ) ) { /* opt for unlocked */
739 :
740 794396 : if( FD_UNLIKELY( POOL_(idx_is_null)( ele_idx ) ) ) { /* opt for not empty */
741 : # if POOL_LAZY
742 6641 : POOL_(acquire_lazy)( join, 1UL, &ele );
743 : # endif
744 6641 : break;
745 6641 : }
746 :
747 787755 : if( FD_UNLIKELY( ele_idx>=ele_max ) ) {
748 0 : FD_LOG_CRIT(( "corruption detected (ele_idx=%lu ele_max=%lu)", ele_idx, ele_max ));
749 0 : }
750 :
751 787755 : ulong ele_nxt = POOL_(private_idx)( ele0[ ele_idx ].POOL_NEXT );
752 :
753 787755 : if( FD_UNLIKELY( (ele_nxt>=ele_max) & (!POOL_(idx_is_null)( ele_nxt )) ) ) { /* ele_nxt is invalid, opt for valid */
754 : /* It is possible that another thread acquired ele_idx and
755 : repurposed ele_idx's POOL_NEXT (storing something in it that
756 : isn't a valid pool value) between when we read ver_top and
757 : when we read ele_idx's POOL_NEXT above. If so, the pool
758 : version would be changed from what we read above. We thus
759 : only signal ERR_CORRUPT if the version number hasn't changed
760 : since we read it. */
761 :
762 0 : FD_HW_MFENCE_LD();
763 0 : if( FD_UNLIKELY( POOL_(private_vidx_ver)( *_v )==ver ) ) {
764 0 : FD_LOG_CRIT(( "corruption detected (ele_nxt=%lu ele_max=%lu)", ele_nxt, ele_max ));
765 0 : }
766 787755 : } else { /* ele_nxt is valid */
767 787755 : ulong new_ver_top = POOL_(private_vidx)( ver+2UL, ele_nxt );
768 :
769 792350 : if( FD_LIKELY( POOL_(private_cas)( _v, ver_top, new_ver_top )==ver_top ) ) { /* opt for low contention */
770 792350 : ele = ele0 + ele_idx;
771 792350 : break;
772 792350 : }
773 787755 : }
774 787755 : }
775 :
776 >1844*10^16 : FD_SPIN_PAUSE();
777 >1844*10^16 : }
778 :
779 799793 : FD_COMPILER_MFENCE();
780 :
781 799793 : return ele;
782 799793 : }
783 :
784 : #if POOL_LAZY
785 :
786 : static inline POOL_ELE_T *
787 0 : POOL_(acquire_lazy_nolock)( POOL_(t) * join ) {
788 0 : POOL_ELE_T * ele0 = join->ele;
789 0 : ulong ele_max = join->ele_max;
790 0 : ulong * _l = &join->pool->ver_lazy;
791 :
792 0 : POOL_ELE_T * ele = NULL;
793 :
794 0 : ulong ver_lazy = *_l;
795 :
796 0 : ulong ver = POOL_(private_vidx_ver)( ver_lazy );
797 0 : ulong ele_idx = POOL_(private_vidx_idx)( ver_lazy );
798 :
799 0 : if( FD_LIKELY( !POOL_(idx_is_null)( ele_idx ) ) ) {
800 0 : if( FD_UNLIKELY( ele_idx>=ele_max ) ) {
801 0 : FD_LOG_CRIT(( "corruption detected (ele_idx=%lu ele_max=%lu)",
802 0 : ele_idx, ele_max ));
803 0 : }
804 :
805 0 : ulong ele_nxt = ele_idx+1UL;
806 0 : if( FD_UNLIKELY( ele_nxt>=ele_max ) ) {
807 0 : ele_nxt = POOL_(idx_null)();
808 0 : }
809 :
810 0 : *_l = POOL_(private_vidx)( ver+2UL, ele_nxt );
811 0 : ele = ele0 + ele_idx;
812 0 : }
813 :
814 0 : return ele;
815 0 : }
816 :
817 : #endif /* POOL_LAZY */
818 :
819 : POOL_STATIC POOL_ELE_T *
820 0 : POOL_(acquire_nolock)( POOL_(t) * join ) {
821 0 : POOL_ELE_T * ele0 = join->ele;
822 0 : ulong ele_max = join->ele_max;
823 0 : ulong * _v = &join->pool->ver_top;
824 :
825 0 : POOL_ELE_T * ele = NULL;
826 :
827 0 : ulong ver_top = *_v;
828 :
829 0 : ulong ver = POOL_(private_vidx_ver)( ver_top );
830 0 : ulong ele_idx = POOL_(private_vidx_idx)( ver_top );
831 :
832 0 : if( FD_UNLIKELY( POOL_(idx_is_null)( ele_idx ) ) ) {
833 0 : # if POOL_LAZY
834 0 : return POOL_(acquire_lazy_nolock)( join );
835 0 : # endif
836 0 : } else {
837 0 : if( FD_UNLIKELY( ele_idx>=ele_max ) ) {
838 0 : FD_LOG_CRIT(( "corruption detected (ele_idx=%lu ele_max=%lu)",
839 0 : ele_idx, ele_max ));
840 0 : }
841 :
842 0 : ulong ele_nxt = POOL_(private_idx)( ele0[ ele_idx ].POOL_NEXT );
843 :
844 0 : if( FD_UNLIKELY( (ele_nxt>=ele_max) & (!POOL_(idx_is_null)( ele_nxt )) ) ) {
845 0 : FD_LOG_CRIT(( "corruption detected (ele_nxt=%lu ele_max=%lu)",
846 0 : ele_nxt, ele_max ));
847 0 : }
848 :
849 0 : *_v = POOL_(private_vidx)( ver+2UL, ele_nxt );
850 0 : ele = ele0 + ele_idx;
851 0 : }
852 :
853 0 : return ele;
854 0 : }
855 :
856 : POOL_STATIC POOL_ELE_T **
857 : POOL_(acquire_batch)( POOL_(t) * join,
858 : ulong cnt,
859 0 : POOL_ELE_T * out[] ) {
860 0 : if( FD_UNLIKELY( !cnt ) ) return NULL;
861 :
862 0 : POOL_ELE_T * ele0 = join->ele;
863 0 : ulong ele_max = join->ele_max;
864 0 : ulong volatile * _v = (ulong volatile *)&join->pool->ver_top;
865 :
866 0 : ulong acq_cnt = 0UL; /* elements acquired so far, in out[0,acq_cnt) */
867 :
868 0 : # if POOL_LAZY
869 0 : int lazy_empty = 0; /* 1 once the lazy region is known empty */
870 : # else
871 : int lazy_empty = 1; /* no lazy region: an empty stack is an empty pool */
872 : # endif
873 :
874 0 : FD_COMPILER_MFENCE();
875 :
876 0 : for(;;) {
877 :
878 : /* Pop up to rem elements off the free stack with one CAS. Exits
879 : with all acquired or with the stack observed empty. */
880 :
881 0 : ulong rem = cnt - acq_cnt;
882 0 : POOL_ELE_T ** dst = out + acq_cnt;
883 :
884 0 : for(;;) {
885 0 : ulong ver_top = *_v;
886 :
887 0 : ulong ver = POOL_(private_vidx_ver)( ver_top );
888 0 : ulong ele_idx = POOL_(private_vidx_idx)( ver_top );
889 :
890 0 : if( FD_LIKELY( !(ver & 1UL) ) ) { /* opt for unlocked */
891 :
892 0 : if( FD_UNLIKELY( POOL_(idx_is_null)( ele_idx ) ) ) break; /* stack empty, opt for not empty */
893 :
894 0 : if( FD_UNLIKELY( ele_idx>=ele_max ) ) {
895 0 : FD_LOG_CRIT(( "corruption detected (ele_idx=%lu ele_max=%lu)", ele_idx, ele_max ));
896 0 : }
897 :
898 : /* Walk up to rem links from the top. ele_nxt becomes the new
899 : top (null if we drained the stack). Another thread may have
900 : acquired an element below us and repurposed its POOL_NEXT,
901 : so links are bounds checked before use and the CAS below
902 : fails if ver_top changed under us. */
903 :
904 0 : ulong n = 0UL;
905 0 : ulong ele_nxt = ele_idx;
906 0 : do {
907 0 : dst[ n++ ] = ele0 + ele_nxt;
908 0 : ele_nxt = POOL_(private_idx)( ele0[ ele_nxt ].POOL_NEXT );
909 0 : } while( FD_LIKELY( (n<rem) & (ele_nxt<ele_max) ) );
910 :
911 0 : if( FD_UNLIKELY( (ele_nxt>=ele_max) & (!POOL_(idx_is_null)( ele_nxt )) ) ) { /* ele_nxt is invalid, opt for valid */
912 :
913 : /* As in acquire: only corruption if the stack did not change */
914 :
915 0 : FD_HW_MFENCE_LD();
916 0 : if( FD_UNLIKELY( POOL_(private_vidx_ver)( *_v )==ver ) ) {
917 0 : FD_LOG_CRIT(( "corruption detected (ele_nxt=%lu ele_max=%lu)", ele_nxt, ele_max ));
918 0 : }
919 0 : } else { /* ele_nxt is valid */
920 0 : ulong new_ver_top = POOL_(private_vidx)( ver+2UL, ele_nxt );
921 :
922 0 : if( FD_LIKELY( POOL_(private_cas)( _v, ver_top, new_ver_top )==ver_top ) ) { /* opt for low contention */
923 0 : acq_cnt += n;
924 0 : break;
925 0 : }
926 0 : }
927 0 : }
928 :
929 0 : FD_SPIN_PAUSE();
930 0 : }
931 :
932 0 : if( FD_LIKELY( acq_cnt==cnt ) ) break;
933 :
934 : /* Stack was just seen empty. If the lazy region was already seen
935 : empty, the pool was empty while we still needed elements. Else
936 : take from the lazy region and, if still short, recheck the stack
937 : once (it may have been refilled meanwhile). */
938 :
939 0 : if( FD_UNLIKELY( lazy_empty ) ) {
940 0 : while( acq_cnt ) POOL_(release)( join, out[ --acq_cnt ] );
941 0 : return NULL;
942 0 : }
943 :
944 0 : # if POOL_LAZY
945 0 : acq_cnt += POOL_(acquire_lazy)( join, cnt-acq_cnt, out+acq_cnt );
946 0 : if( FD_LIKELY( acq_cnt==cnt ) ) break;
947 0 : lazy_empty = 1;
948 0 : # endif
949 0 : }
950 :
951 0 : FD_COMPILER_MFENCE();
952 0 : return out;
953 0 : }
954 :
955 : POOL_STATIC void
956 : POOL_(release)( POOL_(t) * join,
957 0 : POOL_ELE_T * ele ) {
958 0 : ulong ele_max = join->ele_max;
959 0 : ulong volatile * _v = (ulong volatile *)&join->pool->ver_top;
960 :
961 0 : ulong ele_idx = (ulong)(ele - join->ele);
962 0 : if( FD_UNLIKELY( ele_idx>=ele_max ) ) FD_LOG_CRIT(( "corruption detected: ele=%p is not in bounds", (void *)ele ));
963 :
964 0 : FD_COMPILER_MFENCE();
965 :
966 0 : for(;;) {
967 0 : ulong ver_top = *_v;
968 :
969 0 : ulong ver = POOL_(private_vidx_ver)( ver_top );
970 0 : ulong ele_nxt = POOL_(private_vidx_idx)( ver_top );
971 :
972 0 : if( FD_LIKELY( !(ver & 1UL) ) ) { /* opt for unlocked */
973 :
974 0 : if( FD_UNLIKELY( (ele_nxt>=ele_max) & (!POOL_(idx_is_null)( ele_nxt )) ) ) { /* opt for not corrupt */
975 0 : FD_LOG_CRIT(( "corruption detected (ele_nxt=%lu ele_max=%lu)", ele_nxt, ele_max ));
976 0 : }
977 :
978 0 : ele->POOL_NEXT = POOL_(private_cidx)( ele_nxt );
979 :
980 0 : ulong new_ver_top = POOL_(private_vidx)( ver+2UL, ele_idx );
981 :
982 0 : if( FD_LIKELY( POOL_(private_cas)( _v, ver_top, new_ver_top )==ver_top ) ) break; /* opt for low contention */
983 :
984 0 : }
985 :
986 0 : FD_SPIN_PAUSE();
987 0 : }
988 :
989 0 : FD_COMPILER_MFENCE();
990 0 : }
991 :
992 : POOL_STATIC void
993 : POOL_(release_chain)( POOL_(t) * join,
994 : POOL_ELE_T * head,
995 80726 : POOL_ELE_T * tail ) {
996 80726 : ulong ele_max = join->ele_max;
997 80726 : ulong volatile * _v = (ulong volatile *)&join->pool->ver_top;
998 :
999 80726 : ulong head_idx = (ulong)(head - join->ele);
1000 80726 : if( FD_UNLIKELY( head_idx>=ele_max ) ) FD_LOG_CRIT(( "corruption detected: ele=%p is not in bounds", (void *)head ));
1001 :
1002 80726 : ulong tail_idx = (ulong)(tail - join->ele);
1003 80726 : if( FD_UNLIKELY( tail_idx>=ele_max ) ) FD_LOG_CRIT(( "corruption detected: ele=%p is not in bounds", (void *)tail ));
1004 :
1005 80726 : FD_COMPILER_MFENCE();
1006 :
1007 80726 : for(;;) {
1008 80724 : ulong ver_top = *_v;
1009 :
1010 80724 : ulong ver = POOL_(private_vidx_ver)( ver_top );
1011 80724 : ulong ele_nxt = POOL_(private_vidx_idx)( ver_top );
1012 :
1013 80724 : if( FD_LIKELY( !(ver & 1UL) ) ) { /* opt for unlocked */
1014 :
1015 80714 : if( FD_UNLIKELY( (ele_nxt>=ele_max) & (!POOL_(idx_is_null)( ele_nxt )) ) ) { /* opt for not corrupt */
1016 0 : FD_LOG_CRIT(( "corruption detected (ele_nxt=%lu ele_max=%lu)", ele_nxt, ele_max ));
1017 0 : }
1018 :
1019 80714 : tail->POOL_NEXT = POOL_(private_cidx)( ele_nxt );
1020 :
1021 80714 : ulong new_ver_top = POOL_(private_vidx)( ver+2UL, head_idx );
1022 :
1023 80769 : if( FD_LIKELY( POOL_(private_cas)( _v, ver_top, new_ver_top )==ver_top ) ) break; /* opt for low contention */
1024 :
1025 80714 : }
1026 :
1027 >1844*10^16 : FD_SPIN_PAUSE();
1028 >1844*10^16 : }
1029 :
1030 80726 : FD_COMPILER_MFENCE();
1031 80726 : }
1032 :
1033 : POOL_STATIC int
1034 0 : POOL_(is_empty)( POOL_(t) * join ) {
1035 0 : POOL_(shmem_t) const * pool = join->pool;
1036 0 : FD_COMPILER_MFENCE();
1037 0 : ulong ver_top = pool->ver_top;
1038 0 : # if POOL_LAZY
1039 0 : ulong ver_lazy = pool->ver_lazy;
1040 0 : # endif
1041 0 : FD_COMPILER_MFENCE();
1042 :
1043 0 : ulong top_idx = POOL_(private_vidx_idx)( ver_top );
1044 0 : # if POOL_LAZY
1045 0 : ulong ele_max = join->ele_max;
1046 0 : if( FD_LIKELY( top_idx<ele_max ) ) return 0; /* explicit stack non-empty */
1047 0 : ulong lazy_idx = POOL_(private_vidx_idx)( ver_lazy );
1048 0 : return !(lazy_idx<ele_max); /* empty only if lazy also empty */
1049 : # else
1050 : return POOL_(idx_is_null)( top_idx );
1051 : # endif
1052 0 : }
1053 :
1054 : POOL_STATIC int
1055 : POOL_(lock)( POOL_(t) * join,
1056 0 : int blocking ) {
1057 0 : ulong volatile * _v = (ulong volatile *)&join->pool->ver_top;
1058 0 : # if POOL_LAZY
1059 0 : ulong volatile * _l = (ulong volatile *)&join->pool->ver_lazy;
1060 0 : # endif
1061 :
1062 0 : int err = FD_POOL_SUCCESS;
1063 :
1064 0 : FD_COMPILER_MFENCE();
1065 :
1066 0 : ulong ver_top;
1067 0 : for(;;) {
1068 :
1069 : /* use a test-and-test-and-set style for reduced contention */
1070 :
1071 0 : ver_top = *_v;
1072 0 : if( FD_LIKELY( !(ver_top & (1UL<<POOL_IDX_WIDTH)) ) ) { /* opt for low contention */
1073 0 : ver_top = POOL_(private_fetch_and_or)( _v, 1UL<<POOL_IDX_WIDTH );
1074 0 : if( FD_LIKELY( !(ver_top & (1UL<<POOL_IDX_WIDTH)) ) ) break; /* opt for low contention */
1075 0 : }
1076 :
1077 0 : if( FD_UNLIKELY( !blocking ) ) { /* opt for blocking */
1078 0 : err = FD_POOL_ERR_AGAIN;
1079 0 : goto fail;
1080 0 : }
1081 :
1082 0 : FD_SPIN_PAUSE();
1083 0 : }
1084 :
1085 0 : FD_COMPILER_MFENCE();
1086 :
1087 0 : # if POOL_LAZY
1088 :
1089 0 : for(;;) {
1090 :
1091 : /* use a test-and-test-and-set style for reduced contention */
1092 :
1093 0 : ulong ver_lazy = *_l;
1094 0 : if( FD_LIKELY( !(ver_lazy & (1UL<<POOL_IDX_WIDTH)) ) ) { /* opt for low contention */
1095 0 : ver_lazy = POOL_(private_fetch_and_or)( _l, 1UL<<POOL_IDX_WIDTH );
1096 0 : if( FD_LIKELY( !(ver_lazy & (1UL<<POOL_IDX_WIDTH)) ) ) break; /* opt for low contention */
1097 0 : }
1098 :
1099 0 : if( FD_UNLIKELY( !blocking ) ) { /* opt for blocking */
1100 0 : *_v = POOL_(private_vidx)( POOL_(private_vidx_ver)( ver_top )+2UL, POOL_(private_vidx_idx)( ver_top ) ); /* unlock */
1101 0 : err = FD_POOL_ERR_AGAIN;
1102 0 : goto fail;
1103 0 : }
1104 :
1105 0 : FD_SPIN_PAUSE();
1106 0 : }
1107 :
1108 0 : FD_COMPILER_MFENCE();
1109 :
1110 0 : # endif
1111 :
1112 0 : fail:
1113 0 : return err;
1114 0 : }
1115 :
1116 : #if !POOL_LAZY
1117 :
1118 : POOL_STATIC void
1119 12 : POOL_(reset)( POOL_(t) * join ) {
1120 12 : POOL_(shmem_t) * pool = join->pool;
1121 12 : POOL_ELE_T * ele = join->ele;
1122 12 : ulong ele_max = join->ele_max;
1123 :
1124 : /* Insert all elements in increasing order */
1125 :
1126 12 : ulong ele_top = 0UL;
1127 12 : if( FD_UNLIKELY( !ele_max ) ) ele_top = POOL_(idx_null)();
1128 12 : else {
1129 192 : for( ulong ele_idx=ele_top; ele_idx<(ele_max-1UL); ele_idx++ ) {
1130 180 : ele[ ele_idx ].POOL_NEXT = POOL_(private_cidx)( ele_idx+1UL );
1131 180 : }
1132 12 : ele[ ele_max-1UL ].POOL_NEXT = POOL_(private_cidx)( POOL_(idx_null)() );
1133 12 : }
1134 :
1135 12 : ulong ver_top = pool->ver_top;
1136 12 : ulong ver = POOL_(private_vidx_ver)( ver_top );
1137 12 : pool->ver_top = POOL_(private_vidx)( ver, ele_top );
1138 12 : }
1139 :
1140 : #else
1141 :
1142 : POOL_STATIC void
1143 24 : POOL_(reset)( POOL_(t) * join ) {
1144 24 : POOL_(shmem_t) * pool = join->pool;
1145 :
1146 : /* Assign all elements to the bump allocator */
1147 :
1148 24 : ulong ele_top = POOL_(idx_null)();
1149 24 : ulong ele_lazy = 0UL;
1150 :
1151 24 : ulong ver_top = pool->ver_top;
1152 24 : ulong ver_lazy = pool->ver_lazy;
1153 24 : pool->ver_top = POOL_(private_vidx)( POOL_(private_vidx_ver)( ver_top ), ele_top );
1154 24 : pool->ver_lazy = POOL_(private_vidx)( POOL_(private_vidx_ver)( ver_lazy ), ele_lazy );
1155 24 : }
1156 :
1157 : #endif
1158 :
1159 : POOL_STATIC int
1160 0 : POOL_(verify)( POOL_(t) const * join ) {
1161 :
1162 0 : # define POOL_TEST(c) do { \
1163 0 : if( FD_UNLIKELY( !(c) ) ) { FD_LOG_WARNING(( "FAIL: %s", #c )); return FD_POOL_ERR_CORRUPT; } \
1164 0 : } while(0)
1165 :
1166 : /* Validate join */
1167 :
1168 0 : POOL_TEST( join );
1169 0 : POOL_TEST( fd_ulong_is_aligned( (ulong)join, alignof(POOL_(t)) ) );
1170 :
1171 0 : POOL_(shmem_t) const * pool = join->pool;
1172 0 : POOL_ELE_T const * ele = join->ele;
1173 0 : ulong ele_max = join->ele_max;
1174 :
1175 0 : POOL_TEST( pool );
1176 0 : POOL_TEST( fd_ulong_is_aligned( (ulong)pool, POOL_(align)() ) );
1177 :
1178 0 : POOL_TEST( (!!ele)| (!ele_max) );
1179 0 : POOL_TEST( fd_ulong_is_aligned( (ulong)ele, alignof(POOL_ELE_T) ) );
1180 :
1181 0 : POOL_TEST( ele_max<=POOL_(ele_max_max)() );
1182 :
1183 : /* Validate pool metadata */
1184 :
1185 0 : ulong magic = pool->magic;
1186 0 : ulong ver_top = pool->ver_top;
1187 :
1188 : /* version arbitrary as far as verify is concerned */
1189 0 : ulong ele_idx = POOL_(private_vidx_idx)( ver_top );
1190 :
1191 0 : POOL_TEST( magic==POOL_MAGIC );
1192 :
1193 : /* Validate pool elements */
1194 :
1195 0 : ulong ele_rem = ele_max;
1196 0 : while( ele_idx<ele_max ) {
1197 0 : POOL_TEST( ele_rem ); ele_rem--; /* no cycles */
1198 0 : ele_idx = POOL_(private_idx)( ele[ ele_idx ].POOL_NEXT );
1199 0 : }
1200 :
1201 0 : POOL_TEST( POOL_(idx_is_null)( ele_idx ) );
1202 :
1203 0 : # if POOL_LAZY
1204 0 : ulong lazy_idx = POOL_(private_vidx_idx)( pool->ver_lazy );
1205 0 : ulong lazy_free = POOL_(idx_is_null)( lazy_idx ) ? 0UL : (ele_max-lazy_idx);
1206 0 : POOL_TEST( lazy_free<=ele_rem );
1207 0 : # endif
1208 :
1209 0 : # undef POOL_TEST
1210 :
1211 0 : return FD_POOL_SUCCESS;
1212 0 : }
1213 :
1214 : POOL_STATIC char const *
1215 0 : POOL_(strerror)( int err ) {
1216 0 : switch( err ) {
1217 0 : case FD_POOL_SUCCESS: return "success";
1218 0 : case FD_POOL_ERR_AGAIN: return "try again";
1219 0 : case FD_POOL_ERR_CORRUPT: return "corruption detected";
1220 0 : default: break;
1221 0 : }
1222 0 : return "unknown";
1223 0 : }
1224 :
1225 : #endif
1226 :
1227 : #undef POOL_
1228 : #undef POOL_STATIC
1229 : #undef POOL_VER_WIDTH
1230 :
1231 : #undef POOL_LAZY
1232 : #undef POOL_IMPL_STYLE
1233 : #undef POOL_MAGIC
1234 : #undef POOL_IDX_WIDTH
1235 : #undef POOL_ALIGN
1236 : #undef POOL_NEXT
1237 : #undef POOL_IDX_T
1238 : #undef POOL_ELE_T
1239 : #undef POOL_NAME
|
