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 703787 : #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 3425231 : #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 5182630 : #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 871345 : FD_FN_CONST static inline ulong POOL_(private_vidx)( ulong ver, ulong idx ) { return (ver<<POOL_IDX_WIDTH) | idx; }
395 :
396 884479 : FD_FN_CONST static inline ulong POOL_(private_vidx_ver)( ulong ver_idx ) { return ver_idx >> POOL_IDX_WIDTH; }
397 884849 : 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 440732 : FD_FN_CONST static inline POOL_IDX_T POOL_(private_cidx)( ulong idx ) { return (POOL_IDX_T) idx; }
403 782406 : 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 871187 : ulong s ) {
414 871187 : ulong o;
415 871187 : FD_COMPILER_MFENCE();
416 871187 : # if FD_HAS_ATOMIC
417 871187 : o = FD_ATOMIC_CAS( p, c, s );
418 : # else
419 : o = *p;
420 : *p = fd_ulong_if( o==c, s, o );
421 : # endif
422 871187 : FD_COMPILER_MFENCE();
423 871187 : return o;
424 871187 : }
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 8342 : 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 1655461 : FD_FN_CONST static inline ulong POOL_(idx_null)( void ) { return (ulong)(POOL_IDX_T)(ULONG_MAX >> POOL_VER_WIDTH); }
454 1655380 : 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 797559 : POOL_ELE_T const * ele ) {
459 797559 : ulong ele_idx = (ulong)(ele - join->ele);
460 797559 : return ele_idx<join->ele_max ? ele_idx : POOL_(idx_null)();
461 797559 : }
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 440630 : ulong ele_idx ) {
473 440630 : POOL_ELE_T * ele = join->ele;
474 440630 : return (ele_idx < join->ele_max) ? (ele + ele_idx) : NULL;
475 440630 : }
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 10058 : POOL_ELE_T * out[] ) {
677 10058 : POOL_ELE_T * ele0 = join->ele;
678 10058 : ulong ele_max = join->ele_max;
679 10058 : ulong volatile * _l = (ulong volatile *)&join->pool->ver_lazy;
680 :
681 10058 : ulong n = 0UL;
682 :
683 10058 : FD_COMPILER_MFENCE();
684 :
685 10066 : for(;;) {
686 10066 : ulong ver_lazy = *_l;
687 :
688 10066 : ulong ver = POOL_(private_vidx_ver)( ver_lazy );
689 10066 : ulong ele_idx = POOL_(private_vidx_idx)( ver_lazy );
690 :
691 10072 : if( FD_LIKELY( !(ver & 1UL) ) ) { /* opt for unlocked */
692 :
693 10072 : if( FD_UNLIKELY( POOL_(idx_is_null)( ele_idx ) ) ) { /* opt for not empty */
694 0 : break;
695 0 : }
696 :
697 10072 : 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 10072 : ulong ele_cnt = fd_ulong_min( cnt, ele_max-ele_idx );
702 10072 : ulong ele_nxt = ele_idx+ele_cnt;
703 10072 : if( FD_UNLIKELY( ele_nxt>=ele_max ) ) ele_nxt = POOL_(idx_null)();
704 :
705 10072 : ulong new_ver_lazy = POOL_(private_vidx)( ver+2UL, ele_nxt );
706 10072 : if( FD_LIKELY( POOL_(private_cas)( _l, ver_lazy, new_ver_lazy )==ver_lazy ) ) { /* opt for low contention */
707 20020 : for( ; n<ele_cnt; n++ ) out[ n ] = ele0 + ele_idx + n;
708 9996 : break;
709 9996 : }
710 10072 : }
711 :
712 70 : FD_SPIN_PAUSE();
713 70 : }
714 :
715 10058 : FD_COMPILER_MFENCE();
716 :
717 10058 : return n;
718 10058 : }
719 :
720 : #endif /* POOL_LAZY */
721 :
722 : POOL_STATIC POOL_ELE_T *
723 798610 : POOL_(acquire)( POOL_(t) * join ) {
724 798610 : POOL_ELE_T * ele0 = join->ele;
725 798610 : ulong ele_max = join->ele_max;
726 798610 : ulong volatile * _v = (ulong volatile *)&join->pool->ver_top;
727 :
728 798610 : POOL_ELE_T * ele = NULL;
729 :
730 798610 : FD_COMPILER_MFENCE();
731 :
732 798610 : for(;;) {
733 796827 : ulong ver_top = *_v;
734 :
735 796827 : ulong ver = POOL_(private_vidx_ver)( ver_top );
736 796827 : ulong ele_idx = POOL_(private_vidx_idx)( ver_top );
737 :
738 796827 : if( FD_LIKELY( !(ver & 1UL) ) ) { /* opt for unlocked */
739 :
740 794710 : if( FD_UNLIKELY( POOL_(idx_is_null)( ele_idx ) ) ) { /* opt for not empty */
741 : # if POOL_LAZY
742 10054 : POOL_(acquire_lazy)( join, 1UL, &ele );
743 : # endif
744 10054 : break;
745 10054 : }
746 :
747 784656 : 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 784656 : ulong ele_nxt = POOL_(private_idx)( ele0[ ele_idx ].POOL_NEXT );
752 :
753 784656 : 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 : if( FD_UNLIKELY( POOL_(private_vidx_ver)( *_v )==ver ) ) {
763 0 : FD_LOG_CRIT(( "corruption detected (ele_nxt=%lu ele_max=%lu)", ele_nxt, ele_max ));
764 0 : }
765 784656 : } else { /* ele_nxt is valid */
766 784656 : ulong new_ver_top = POOL_(private_vidx)( ver+2UL, ele_nxt );
767 :
768 789163 : if( FD_LIKELY( POOL_(private_cas)( _v, ver_top, new_ver_top )==ver_top ) ) { /* opt for low contention */
769 789163 : ele = ele0 + ele_idx;
770 789163 : break;
771 789163 : }
772 784656 : }
773 784656 : }
774 :
775 >1844*10^16 : FD_SPIN_PAUSE();
776 >1844*10^16 : }
777 :
778 798610 : FD_COMPILER_MFENCE();
779 :
780 798610 : return ele;
781 798610 : }
782 :
783 : #if POOL_LAZY
784 :
785 : static inline POOL_ELE_T *
786 0 : POOL_(acquire_lazy_nolock)( POOL_(t) * join ) {
787 0 : POOL_ELE_T * ele0 = join->ele;
788 0 : ulong ele_max = join->ele_max;
789 0 : ulong * _l = &join->pool->ver_lazy;
790 :
791 0 : POOL_ELE_T * ele = NULL;
792 :
793 0 : ulong ver_lazy = *_l;
794 :
795 0 : ulong ver = POOL_(private_vidx_ver)( ver_lazy );
796 0 : ulong ele_idx = POOL_(private_vidx_idx)( ver_lazy );
797 :
798 0 : if( FD_LIKELY( !POOL_(idx_is_null)( ele_idx ) ) ) {
799 0 : if( FD_UNLIKELY( ele_idx>=ele_max ) ) {
800 0 : FD_LOG_CRIT(( "corruption detected (ele_idx=%lu ele_max=%lu)",
801 0 : ele_idx, ele_max ));
802 0 : }
803 :
804 0 : ulong ele_nxt = ele_idx+1UL;
805 0 : if( FD_UNLIKELY( ele_nxt>=ele_max ) ) {
806 0 : ele_nxt = POOL_(idx_null)();
807 0 : }
808 :
809 0 : *_l = POOL_(private_vidx)( ver+2UL, ele_nxt );
810 0 : ele = ele0 + ele_idx;
811 0 : }
812 :
813 0 : return ele;
814 0 : }
815 :
816 : #endif /* POOL_LAZY */
817 :
818 : POOL_STATIC POOL_ELE_T *
819 0 : POOL_(acquire_nolock)( POOL_(t) * join ) {
820 0 : POOL_ELE_T * ele0 = join->ele;
821 0 : ulong ele_max = join->ele_max;
822 0 : ulong * _v = &join->pool->ver_top;
823 :
824 0 : POOL_ELE_T * ele = NULL;
825 :
826 0 : ulong ver_top = *_v;
827 :
828 0 : ulong ver = POOL_(private_vidx_ver)( ver_top );
829 0 : ulong ele_idx = POOL_(private_vidx_idx)( ver_top );
830 :
831 0 : if( FD_UNLIKELY( POOL_(idx_is_null)( ele_idx ) ) ) {
832 : # if POOL_LAZY
833 0 : return POOL_(acquire_lazy_nolock)( join );
834 : # endif
835 0 : } else {
836 0 : if( FD_UNLIKELY( ele_idx>=ele_max ) ) {
837 0 : FD_LOG_CRIT(( "corruption detected (ele_idx=%lu ele_max=%lu)",
838 0 : ele_idx, ele_max ));
839 0 : }
840 :
841 0 : ulong ele_nxt = POOL_(private_idx)( ele0[ ele_idx ].POOL_NEXT );
842 :
843 0 : if( FD_UNLIKELY( (ele_nxt>=ele_max) & (!POOL_(idx_is_null)( ele_nxt )) ) ) {
844 0 : FD_LOG_CRIT(( "corruption detected (ele_nxt=%lu ele_max=%lu)",
845 0 : ele_nxt, ele_max ));
846 0 : }
847 :
848 0 : *_v = POOL_(private_vidx)( ver+2UL, ele_nxt );
849 0 : ele = ele0 + ele_idx;
850 0 : }
851 :
852 0 : return ele;
853 0 : }
854 :
855 : POOL_STATIC POOL_ELE_T **
856 : POOL_(acquire_batch)( POOL_(t) * join,
857 : ulong cnt,
858 0 : POOL_ELE_T * out[] ) {
859 0 : if( FD_UNLIKELY( !cnt ) ) return NULL;
860 :
861 0 : POOL_ELE_T * ele0 = join->ele;
862 0 : ulong ele_max = join->ele_max;
863 0 : ulong volatile * _v = (ulong volatile *)&join->pool->ver_top;
864 :
865 0 : ulong acq_cnt = 0UL; /* elements acquired so far, in out[0,acq_cnt) */
866 :
867 : # if POOL_LAZY
868 : int lazy_empty = 0; /* 1 once the lazy region is known empty */
869 : # else
870 : int lazy_empty = 1; /* no lazy region: an empty stack is an empty pool */
871 : # endif
872 :
873 0 : FD_COMPILER_MFENCE();
874 :
875 0 : for(;;) {
876 :
877 : /* Pop up to rem elements off the free stack with one CAS. Exits
878 : with all acquired or with the stack observed empty. */
879 :
880 0 : ulong rem = cnt - acq_cnt;
881 0 : POOL_ELE_T ** dst = out + acq_cnt;
882 :
883 0 : for(;;) {
884 0 : ulong ver_top = *_v;
885 :
886 0 : ulong ver = POOL_(private_vidx_ver)( ver_top );
887 0 : ulong ele_idx = POOL_(private_vidx_idx)( ver_top );
888 :
889 0 : if( FD_LIKELY( !(ver & 1UL) ) ) { /* opt for unlocked */
890 :
891 0 : if( FD_UNLIKELY( POOL_(idx_is_null)( ele_idx ) ) ) break; /* stack empty, opt for not empty */
892 :
893 0 : if( FD_UNLIKELY( ele_idx>=ele_max ) ) {
894 0 : FD_LOG_CRIT(( "corruption detected (ele_idx=%lu ele_max=%lu)", ele_idx, ele_max ));
895 0 : }
896 :
897 : /* Walk up to rem links from the top. ele_nxt becomes the new
898 : top (null if we drained the stack). Another thread may have
899 : acquired an element below us and repurposed its POOL_NEXT,
900 : so links are bounds checked before use and the CAS below
901 : fails if ver_top changed under us. */
902 :
903 0 : ulong n = 0UL;
904 0 : ulong ele_nxt = ele_idx;
905 0 : do {
906 0 : dst[ n++ ] = ele0 + ele_nxt;
907 0 : ele_nxt = POOL_(private_idx)( ele0[ ele_nxt ].POOL_NEXT );
908 0 : } while( FD_LIKELY( (n<rem) & (ele_nxt<ele_max) ) );
909 :
910 0 : if( FD_UNLIKELY( (ele_nxt>=ele_max) & (!POOL_(idx_is_null)( ele_nxt )) ) ) { /* ele_nxt is invalid, opt for valid */
911 :
912 : /* As in acquire: only corruption if the stack did not change */
913 :
914 0 : if( FD_UNLIKELY( POOL_(private_vidx_ver)( *_v )==ver ) ) {
915 0 : FD_LOG_CRIT(( "corruption detected (ele_nxt=%lu ele_max=%lu)", ele_nxt, ele_max ));
916 0 : }
917 0 : } else { /* ele_nxt is valid */
918 0 : ulong new_ver_top = POOL_(private_vidx)( ver+2UL, ele_nxt );
919 :
920 0 : if( FD_LIKELY( POOL_(private_cas)( _v, ver_top, new_ver_top )==ver_top ) ) { /* opt for low contention */
921 0 : acq_cnt += n;
922 0 : break;
923 0 : }
924 0 : }
925 0 : }
926 :
927 0 : FD_SPIN_PAUSE();
928 0 : }
929 :
930 0 : if( FD_LIKELY( acq_cnt==cnt ) ) break;
931 :
932 : /* Stack was just seen empty. If the lazy region was already seen
933 : empty, the pool was empty while we still needed elements. Else
934 : take from the lazy region and, if still short, recheck the stack
935 : once (it may have been refilled meanwhile). */
936 :
937 0 : if( FD_UNLIKELY( lazy_empty ) ) {
938 0 : while( acq_cnt ) POOL_(release)( join, out[ --acq_cnt ] );
939 0 : return NULL;
940 0 : }
941 :
942 : # if POOL_LAZY
943 0 : acq_cnt += POOL_(acquire_lazy)( join, cnt-acq_cnt, out+acq_cnt );
944 0 : if( FD_LIKELY( acq_cnt==cnt ) ) break;
945 0 : lazy_empty = 1;
946 0 : # endif
947 0 : }
948 :
949 0 : FD_COMPILER_MFENCE();
950 0 : return out;
951 0 : }
952 :
953 : POOL_STATIC void
954 : POOL_(release)( POOL_(t) * join,
955 0 : POOL_ELE_T * ele ) {
956 0 : ulong ele_max = join->ele_max;
957 0 : ulong volatile * _v = (ulong volatile *)&join->pool->ver_top;
958 :
959 0 : ulong ele_idx = (ulong)(ele - join->ele);
960 0 : if( FD_UNLIKELY( ele_idx>=ele_max ) ) FD_LOG_CRIT(( "corruption detected: ele=%p is not in bounds", (void *)ele ));
961 :
962 0 : FD_COMPILER_MFENCE();
963 :
964 0 : for(;;) {
965 0 : ulong ver_top = *_v;
966 :
967 0 : ulong ver = POOL_(private_vidx_ver)( ver_top );
968 0 : ulong ele_nxt = POOL_(private_vidx_idx)( ver_top );
969 :
970 0 : if( FD_LIKELY( !(ver & 1UL) ) ) { /* opt for unlocked */
971 :
972 0 : if( FD_UNLIKELY( (ele_nxt>=ele_max) & (!POOL_(idx_is_null)( ele_nxt )) ) ) { /* opt for not corrupt */
973 0 : FD_LOG_CRIT(( "corruption detected (ele_nxt=%lu ele_max=%lu)", ele_nxt, ele_max ));
974 0 : }
975 :
976 0 : ele->POOL_NEXT = POOL_(private_cidx)( ele_nxt );
977 :
978 0 : ulong new_ver_top = POOL_(private_vidx)( ver+2UL, ele_idx );
979 :
980 0 : if( FD_LIKELY( POOL_(private_cas)( _v, ver_top, new_ver_top )==ver_top ) ) break; /* opt for low contention */
981 :
982 0 : }
983 :
984 0 : FD_SPIN_PAUSE();
985 0 : }
986 :
987 0 : FD_COMPILER_MFENCE();
988 0 : }
989 :
990 : POOL_STATIC void
991 : POOL_(release_chain)( POOL_(t) * join,
992 : POOL_ELE_T * head,
993 80719 : POOL_ELE_T * tail ) {
994 80719 : ulong ele_max = join->ele_max;
995 80719 : ulong volatile * _v = (ulong volatile *)&join->pool->ver_top;
996 :
997 80719 : ulong head_idx = (ulong)(head - join->ele);
998 80719 : if( FD_UNLIKELY( head_idx>=ele_max ) ) FD_LOG_CRIT(( "corruption detected: ele=%p is not in bounds", (void *)head ));
999 :
1000 80719 : ulong tail_idx = (ulong)(tail - join->ele);
1001 80719 : if( FD_UNLIKELY( tail_idx>=ele_max ) ) FD_LOG_CRIT(( "corruption detected: ele=%p is not in bounds", (void *)tail ));
1002 :
1003 80719 : FD_COMPILER_MFENCE();
1004 :
1005 80722 : for(;;) {
1006 80722 : ulong ver_top = *_v;
1007 :
1008 80722 : ulong ver = POOL_(private_vidx_ver)( ver_top );
1009 80722 : ulong ele_nxt = POOL_(private_vidx_idx)( ver_top );
1010 :
1011 80731 : if( FD_LIKELY( !(ver & 1UL) ) ) { /* opt for unlocked */
1012 :
1013 80731 : if( FD_UNLIKELY( (ele_nxt>=ele_max) & (!POOL_(idx_is_null)( ele_nxt )) ) ) { /* opt for not corrupt */
1014 0 : FD_LOG_CRIT(( "corruption detected (ele_nxt=%lu ele_max=%lu)", ele_nxt, ele_max ));
1015 0 : }
1016 :
1017 80731 : tail->POOL_NEXT = POOL_(private_cidx)( ele_nxt );
1018 :
1019 80731 : ulong new_ver_top = POOL_(private_vidx)( ver+2UL, head_idx );
1020 :
1021 80808 : if( FD_LIKELY( POOL_(private_cas)( _v, ver_top, new_ver_top )==ver_top ) ) break; /* opt for low contention */
1022 :
1023 80731 : }
1024 :
1025 >1844*10^16 : FD_SPIN_PAUSE();
1026 >1844*10^16 : }
1027 :
1028 80719 : FD_COMPILER_MFENCE();
1029 80719 : }
1030 :
1031 : POOL_STATIC int
1032 0 : POOL_(is_empty)( POOL_(t) * join ) {
1033 0 : POOL_(shmem_t) const * pool = join->pool;
1034 0 : FD_COMPILER_MFENCE();
1035 0 : ulong ver_top = pool->ver_top;
1036 : # if POOL_LAZY
1037 : ulong ver_lazy = pool->ver_lazy;
1038 : # endif
1039 0 : FD_COMPILER_MFENCE();
1040 :
1041 0 : ulong top_idx = POOL_(private_vidx_idx)( ver_top );
1042 : # if POOL_LAZY
1043 : ulong ele_max = join->ele_max;
1044 0 : if( FD_LIKELY( top_idx<ele_max ) ) return 0; /* explicit stack non-empty */
1045 0 : ulong lazy_idx = POOL_(private_vidx_idx)( ver_lazy );
1046 0 : return !(lazy_idx<ele_max); /* empty only if lazy also empty */
1047 : # else
1048 0 : return POOL_(idx_is_null)( top_idx );
1049 : # endif
1050 0 : }
1051 :
1052 : POOL_STATIC int
1053 : POOL_(lock)( POOL_(t) * join,
1054 0 : int blocking ) {
1055 0 : ulong volatile * _v = (ulong volatile *)&join->pool->ver_top;
1056 : # if POOL_LAZY
1057 : ulong volatile * _l = (ulong volatile *)&join->pool->ver_lazy;
1058 : # endif
1059 :
1060 0 : int err = FD_POOL_SUCCESS;
1061 :
1062 0 : FD_COMPILER_MFENCE();
1063 :
1064 0 : ulong ver_top;
1065 0 : for(;;) {
1066 :
1067 : /* use a test-and-test-and-set style for reduced contention */
1068 :
1069 0 : ver_top = *_v;
1070 0 : if( FD_LIKELY( !(ver_top & (1UL<<POOL_IDX_WIDTH)) ) ) { /* opt for low contention */
1071 0 : ver_top = POOL_(private_fetch_and_or)( _v, 1UL<<POOL_IDX_WIDTH );
1072 0 : if( FD_LIKELY( !(ver_top & (1UL<<POOL_IDX_WIDTH)) ) ) break; /* opt for low contention */
1073 0 : }
1074 :
1075 0 : if( FD_UNLIKELY( !blocking ) ) { /* opt for blocking */
1076 0 : err = FD_POOL_ERR_AGAIN;
1077 0 : goto fail;
1078 0 : }
1079 :
1080 0 : FD_SPIN_PAUSE();
1081 0 : }
1082 :
1083 0 : FD_COMPILER_MFENCE();
1084 :
1085 : # if POOL_LAZY
1086 :
1087 0 : for(;;) {
1088 :
1089 : /* use a test-and-test-and-set style for reduced contention */
1090 :
1091 0 : ulong ver_lazy = *_l;
1092 0 : if( FD_LIKELY( !(ver_lazy & (1UL<<POOL_IDX_WIDTH)) ) ) { /* opt for low contention */
1093 0 : ver_lazy = POOL_(private_fetch_and_or)( _l, 1UL<<POOL_IDX_WIDTH );
1094 0 : if( FD_LIKELY( !(ver_lazy & (1UL<<POOL_IDX_WIDTH)) ) ) break; /* opt for low contention */
1095 0 : }
1096 :
1097 0 : if( FD_UNLIKELY( !blocking ) ) { /* opt for blocking */
1098 0 : *_v = POOL_(private_vidx)( POOL_(private_vidx_ver)( ver_top )+2UL, POOL_(private_vidx_idx)( ver_top ) ); /* unlock */
1099 0 : err = FD_POOL_ERR_AGAIN;
1100 0 : goto fail;
1101 0 : }
1102 :
1103 0 : FD_SPIN_PAUSE();
1104 0 : }
1105 :
1106 0 : FD_COMPILER_MFENCE();
1107 :
1108 0 : # endif
1109 :
1110 0 : fail:
1111 0 : return err;
1112 0 : }
1113 :
1114 : #if !POOL_LAZY
1115 :
1116 : POOL_STATIC void
1117 12 : POOL_(reset)( POOL_(t) * join ) {
1118 12 : POOL_(shmem_t) * pool = join->pool;
1119 12 : POOL_ELE_T * ele = join->ele;
1120 12 : ulong ele_max = join->ele_max;
1121 :
1122 : /* Insert all elements in increasing order */
1123 :
1124 12 : ulong ele_top = 0UL;
1125 12 : if( FD_UNLIKELY( !ele_max ) ) ele_top = POOL_(idx_null)();
1126 12 : else {
1127 192 : for( ulong ele_idx=ele_top; ele_idx<(ele_max-1UL); ele_idx++ ) {
1128 180 : ele[ ele_idx ].POOL_NEXT = POOL_(private_cidx)( ele_idx+1UL );
1129 180 : }
1130 12 : ele[ ele_max-1UL ].POOL_NEXT = POOL_(private_cidx)( POOL_(idx_null)() );
1131 12 : }
1132 :
1133 12 : ulong ver_top = pool->ver_top;
1134 12 : ulong ver = POOL_(private_vidx_ver)( ver_top );
1135 12 : pool->ver_top = POOL_(private_vidx)( ver, ele_top );
1136 12 : }
1137 :
1138 : #else
1139 :
1140 : POOL_STATIC void
1141 24 : POOL_(reset)( POOL_(t) * join ) {
1142 24 : POOL_(shmem_t) * pool = join->pool;
1143 :
1144 : /* Assign all elements to the bump allocator */
1145 :
1146 24 : ulong ele_top = POOL_(idx_null)();
1147 24 : ulong ele_lazy = 0UL;
1148 :
1149 24 : ulong ver_top = pool->ver_top;
1150 24 : ulong ver_lazy = pool->ver_lazy;
1151 24 : pool->ver_top = POOL_(private_vidx)( POOL_(private_vidx_ver)( ver_top ), ele_top );
1152 24 : pool->ver_lazy = POOL_(private_vidx)( POOL_(private_vidx_ver)( ver_lazy ), ele_lazy );
1153 24 : }
1154 :
1155 : #endif
1156 :
1157 : POOL_STATIC int
1158 0 : POOL_(verify)( POOL_(t) const * join ) {
1159 :
1160 0 : # define POOL_TEST(c) do { \
1161 0 : if( FD_UNLIKELY( !(c) ) ) { FD_LOG_WARNING(( "FAIL: %s", #c )); return FD_POOL_ERR_CORRUPT; } \
1162 0 : } while(0)
1163 :
1164 : /* Validate join */
1165 :
1166 0 : POOL_TEST( join );
1167 0 : POOL_TEST( fd_ulong_is_aligned( (ulong)join, alignof(POOL_(t)) ) );
1168 :
1169 0 : POOL_(shmem_t) const * pool = join->pool;
1170 0 : POOL_ELE_T const * ele = join->ele;
1171 0 : ulong ele_max = join->ele_max;
1172 :
1173 0 : POOL_TEST( pool );
1174 0 : POOL_TEST( fd_ulong_is_aligned( (ulong)pool, POOL_(align)() ) );
1175 :
1176 0 : POOL_TEST( (!!ele)| (!ele_max) );
1177 0 : POOL_TEST( fd_ulong_is_aligned( (ulong)ele, alignof(POOL_ELE_T) ) );
1178 :
1179 0 : POOL_TEST( ele_max<=POOL_(ele_max_max)() );
1180 :
1181 : /* Validate pool metadata */
1182 :
1183 0 : ulong magic = pool->magic;
1184 0 : ulong ver_top = pool->ver_top;
1185 :
1186 : /* version arbitrary as far as verify is concerned */
1187 0 : ulong ele_idx = POOL_(private_vidx_idx)( ver_top );
1188 :
1189 0 : POOL_TEST( magic==POOL_MAGIC );
1190 :
1191 : /* Validate pool elements */
1192 :
1193 0 : ulong ele_rem = ele_max;
1194 0 : while( ele_idx<ele_max ) {
1195 0 : POOL_TEST( ele_rem ); ele_rem--; /* no cycles */
1196 0 : ele_idx = POOL_(private_idx)( ele[ ele_idx ].POOL_NEXT );
1197 0 : }
1198 :
1199 0 : POOL_TEST( POOL_(idx_is_null)( ele_idx ) );
1200 :
1201 : # if POOL_LAZY
1202 0 : ulong lazy_idx = POOL_(private_vidx_idx)( pool->ver_lazy );
1203 0 : ulong lazy_free = POOL_(idx_is_null)( lazy_idx ) ? 0UL : (ele_max-lazy_idx);
1204 0 : POOL_TEST( lazy_free<=ele_rem );
1205 0 : # endif
1206 :
1207 0 : # undef POOL_TEST
1208 :
1209 0 : return FD_POOL_SUCCESS;
1210 0 : }
1211 :
1212 : POOL_STATIC char const *
1213 0 : POOL_(strerror)( int err ) {
1214 0 : switch( err ) {
1215 0 : case FD_POOL_SUCCESS: return "success";
1216 0 : case FD_POOL_ERR_AGAIN: return "try again";
1217 0 : case FD_POOL_ERR_CORRUPT: return "corruption detected";
1218 0 : default: break;
1219 0 : }
1220 0 : return "unknown";
1221 0 : }
1222 :
1223 : #endif
1224 :
1225 : #undef POOL_
1226 : #undef POOL_STATIC
1227 : #undef POOL_VER_WIDTH
1228 :
1229 : #undef POOL_LAZY
1230 : #undef POOL_IMPL_STYLE
1231 : #undef POOL_MAGIC
1232 : #undef POOL_IDX_WIDTH
1233 : #undef POOL_ALIGN
1234 : #undef POOL_NEXT
1235 : #undef POOL_IDX_T
1236 : #undef POOL_ELE_T
1237 : #undef POOL_NAME
|
