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_release releases an element to a mypoool. Assumes join
177 : // is a current local join, ele is a pointer in the caller's
178 : // address space to the element, and the element is currently not
179 : // in the mypool.
180 :
181 : void mypool_release( mypool_t * join, myele_t * ele );
182 :
183 : // mypool_release_chain splices a singly-linked chain of elements
184 : // back into the mypool free stack in a single CAS. head is a
185 : // pointer to the first element of the chain and tail is a pointer
186 : // to the last. The chain must be linked via POOL_NEXT (i.e.
187 : // head->next -> ... -> tail). tail's next pointer will be
188 : // overwritten to point at the current stack top. Assumes join is
189 : // a current local join, head and tail are valid elements in the
190 : // element store, the chain is non-empty, and none of the elements
191 : // are currently in the mypool.
192 :
193 : void mypool_release_chain( mypool_t * join, myele_t * head, myele_t * tail );
194 :
195 : // mypool_is_empty returns 1 if the mypool has no elements available
196 : // for acquire and 0 otherwise. Observation is a point-in-time
197 : // sample; concurrent acquire / release operations may change the
198 : // result immediately after. Assumes join is a current local join.
199 :
200 : int mypool_is_empty( mypool_t * join );
201 :
202 : // mypool_lock will lock a mypool (e.g. pausing concurrent acquire
203 : // / release operations). A non-zero / zero value for blocking
204 : // indicates the call should / should not wait to lock the mypool
205 : // if it is currently locked. Returns FD_POOL_SUCCESS on success
206 : // (caller has the lock on return) and FD_POOL_ERR_AGAIN on failure
207 : // (pool was already locked at some point during the call). AGAIN
208 : // is never returned if blocking is requested. Assumes join is a
209 : // current local join.
210 :
211 : int mypool_lock( mypool_t * join, int blocking );
212 :
213 : // mypool_unlock will unlock a mypool (e.g. resuming concurrent
214 : // acquire / release operations). Assumes join is a current local
215 : // join and the caller has a lock on mypool. Guaranteed to
216 : // succeed.
217 :
218 : void mypool_unlock( mypool_t * join );
219 :
220 : // mypool_reset resets the mypool. On return, it will hold all
221 : // elements in the element store (e.g. initialization after
222 : // creation) in ascending order. Assumes join is a current local
223 : // join and the mypool is locked or otherwise idle.
224 :
225 : void mypool_reset( mypool_t * join );
226 :
227 : // mypool_verify returns FD_POOL_SUCCESS if join appears to be
228 : // current local join to a valid mypool and FD_POOL_ERR_CORRUPT
229 : // otherwise (logs details). Assumes join is a current local join
230 : // and the mypool is locked or otherwise idle.
231 :
232 : int mypool_verify( mypool_t const * join );
233 :
234 : // mypool_strerror converts an FD_POOL_SUCCESS / FD_POOL_ERR code
235 : // into a human readable cstr. The lifetime of the returned
236 : // pointer is infinite. The returned pointer is always to a
237 : // non-NULL cstr.
238 :
239 : char const * mypool_strerror( int err );
240 :
241 : Do this as often as desired in a compilation unit to get different
242 : types of concurrent pools. Options exist for generating library
243 : header prototypes and/or library implementations for concurrent pools
244 : usable across multiple compilation units. Additional options exist
245 : to use index compression, configuring versioning, etc. */
246 :
247 : /* POOL_NAME gives the API prefix to use for pool */
248 :
249 : #ifndef POOL_NAME
250 : #error "Define POOL_NAME"
251 : #endif
252 :
253 : /* POOL_ELE_T is the pool element type. */
254 :
255 : #ifndef POOL_ELE_T
256 : #error "Define POOL_ELE_T"
257 : #endif
258 :
259 : /* POOL_IDX_T is the type used for the next field in the POOL_ELE_T.
260 : Should be a primitive unsigned integer type. Defaults to ulong. A
261 : pool can't use element stores with a capacity that can't be
262 : represented by a POOL_IDX_T. (E.g. if ushort, the maximum capacity
263 : pool compatible element store is 65535 elements.) */
264 :
265 : #ifndef POOL_IDX_T
266 : #define POOL_IDX_T ulong
267 : #endif
268 :
269 : /* POOL_NEXT is the POOL_ELE_T next field */
270 :
271 : #ifndef POOL_NEXT
272 902036 : #define POOL_NEXT next
273 : #endif
274 :
275 : /* POOL_ALIGN gives the alignment required for the pool shared memory.
276 : Default is 128 for double cache line alignment. Should be at least
277 : ulong alignment. */
278 :
279 : #ifndef POOL_ALIGN
280 : #define POOL_ALIGN (128UL)
281 : #endif
282 :
283 : /* POOL_IDX_WIDTH gives the number of bits in a ulong to reserve for
284 : encoding the element store index in a versioned index. Element store
285 : capacity should be representable in this width. Default is 43 bits
286 : (e.g. enough to support a ~1 PiB element store of 128 byte elements).
287 : The versioning width will be 64-POOL_IDX_WIDTH. Since the least
288 : significant bit of the version is used to indicate global locking,
289 : versioning width should be at least 2 and ideally as large as
290 : possible. With the 43 default, version numbers will not be reused
291 : until 2^20 individual operations have been done. */
292 :
293 : #ifndef POOL_IDX_WIDTH
294 40429392 : #define POOL_IDX_WIDTH (43)
295 : #endif
296 :
297 : /* POOL_MAGIC is the magic number to use for the structure to aid in
298 : persistent and or IPC usage. */
299 :
300 : #ifndef POOL_MAGIC
301 12723 : #define POOL_MAGIC (0xf17eda2c37c90010UL) /* firedancer cpool version 0 */
302 : #endif
303 :
304 : /* POOL_IMPL_STYLE controls what to generate:
305 : 0 - local use only
306 : 1 - library header declaration
307 : 2 - library implementation */
308 :
309 : #ifndef POOL_IMPL_STYLE
310 : #define POOL_IMPL_STYLE 0
311 : #endif
312 :
313 : /* POOL_LAZY enables lazy initialization for faster startup if defined
314 : to non-zero. Decreases pool_reset cost from O(ele_max) to O(1), at
315 : the cost of more complex allocation logic. */
316 :
317 : #ifndef POOL_LAZY
318 : #define POOL_LAZY 0
319 : #endif
320 :
321 : /* Common pool error codes (FIXME: probably should get around to making
322 : unified error codes and string handling across all util at least so
323 : we don't have to do this in the generator itself) */
324 :
325 120 : #define FD_POOL_SUCCESS ( 0)
326 6 : #define FD_POOL_ERR_AGAIN (-1)
327 3 : #define FD_POOL_ERR_CORRUPT (-2)
328 :
329 : /* Implementation *****************************************************/
330 :
331 31159576 : #define POOL_VER_WIDTH (64-POOL_IDX_WIDTH)
332 :
333 : #if POOL_IMPL_STYLE==0 /* local use only */
334 : #define POOL_STATIC FD_FN_UNUSED static
335 : #else /* library header and/or implementation */
336 : #define POOL_STATIC
337 : #endif
338 :
339 48302705 : #define POOL_(n) FD_EXPAND_THEN_CONCAT3(POOL_NAME,_,n)
340 :
341 : #if POOL_IMPL_STYLE!=2 /* need header */
342 :
343 : #include "../bits/fd_bits.h"
344 :
345 : struct __attribute__((aligned(POOL_ALIGN))) POOL_(shmem_private) {
346 :
347 : /* Note: there is no free count because that that isn't precisely
348 : knowable in a portable concurrent data structure. (Not enough bits
349 : to squeeze into ver_top for large pools, requiring 128-bit wide
350 : ver_top would limit supported targets, etc). */
351 :
352 : ulong magic; /* == POOL_MAGIC */
353 : ulong ver_top; /* Versioned index of the free stack top, top is in [0,ele_max) (not-empty) or is idx_null (empty) */
354 :
355 : # if POOL_LAZY
356 : ulong ver_lazy; /* Versioned index of the lazy init, lazy is in [0,ele_max] (not-empty) or is idx_null (empty) */
357 : # endif
358 :
359 : };
360 :
361 : typedef struct POOL_(shmem_private) POOL_(shmem_t);
362 :
363 : struct POOL_(private) {
364 : POOL_(shmem_t) * pool; /* Pool location in the local address space */
365 : POOL_ELE_T * ele; /* Element store location in the local address space, NULL okay if ele_max==0 */
366 : ulong ele_max; /* Element store capacity, in [0,ele_max_max] */
367 : };
368 :
369 : typedef struct POOL_(private) POOL_(t);
370 :
371 : FD_PROTOTYPES_BEGIN
372 :
373 : /* pool_private_vidx pack ver and idx into a versioned idx. ver is
374 : masked to fit into POOL_VER_WIDTH bits. idx is assumed in
375 : [0,ele_max_max].
376 :
377 : pool_private_vidx_{ver,idx} extract the {version,index} from a
378 : versioned index and will fit into {POOL_VER_WIDTH,POOL_IDX_WIDTH}
379 : bits. */
380 :
381 8507622 : FD_FN_CONST static inline ulong POOL_(private_vidx)( ulong ver, ulong idx ) { return (ver<<POOL_IDX_WIDTH) | idx; }
382 :
383 9012290 : FD_FN_CONST static inline ulong POOL_(private_vidx_ver)( ulong ver_idx ) { return ver_idx >> POOL_IDX_WIDTH; }
384 8991382 : FD_FN_CONST static inline ulong POOL_(private_vidx_idx)( ulong ver_idx ) { return (ver_idx << POOL_VER_WIDTH) >> POOL_VER_WIDTH; }
385 :
386 : /* pool_private_{cidx,idx} compress/decompress a 64-bit in-register
387 : index to/from its in-memory representation. */
388 :
389 4209744 : FD_FN_CONST static inline POOL_IDX_T POOL_(private_cidx)( ulong idx ) { return (POOL_IDX_T) idx; }
390 4128873 : FD_FN_CONST static inline ulong POOL_(private_idx) ( ulong cidx ) { return (ulong) cidx; }
391 :
392 : /* pool_private_cas does a ulong FD_ATOMIC_CAS when FD_HAS_ATOMIC
393 : support is available and emulates it when not. Similarly for
394 : pool_private_fetch_and_or. When emulated, the pool will not be safe
395 : to use concurrently (but will still work). */
396 :
397 : static inline ulong
398 : POOL_(private_cas)( ulong volatile * p,
399 : ulong c,
400 8462331 : ulong s ) {
401 8462331 : ulong o;
402 8462331 : FD_COMPILER_MFENCE();
403 8462331 : # if FD_HAS_ATOMIC
404 8462331 : o = FD_ATOMIC_CAS( p, c, s );
405 : # else
406 : o = *p;
407 : *p = fd_ulong_if( o==c, s, o );
408 : # endif
409 8462331 : FD_COMPILER_MFENCE();
410 8462331 : return o;
411 8462331 : }
412 :
413 : static inline ulong
414 : POOL_(private_fetch_and_or)( ulong volatile * p,
415 12 : ulong b ) {
416 12 : ulong x;
417 12 : FD_COMPILER_MFENCE();
418 12 : # if FD_HAS_ATOMIC
419 12 : x = FD_ATOMIC_FETCH_AND_OR( p, b );
420 : # else
421 : x = *p;
422 : *p = x | b;
423 : # endif
424 12 : FD_COMPILER_MFENCE();
425 12 : return x;
426 12 : }
427 :
428 25500 : FD_FN_CONST static inline ulong POOL_(ele_max_max)( void ) { return (ulong)(POOL_IDX_T)(ULONG_MAX >> POOL_VER_WIDTH); }
429 :
430 41097 : FD_FN_CONST static inline ulong POOL_(align) ( void ) { return alignof(POOL_(shmem_t)); }
431 864 : FD_FN_CONST static inline ulong POOL_(footprint)( void ) { return sizeof (POOL_(shmem_t)); }
432 :
433 18 : FD_FN_PURE static inline void const * POOL_(shpool_const)( POOL_(t) const * join ) { return join->pool; }
434 36 : FD_FN_PURE static inline void const * POOL_(shele_const) ( POOL_(t) const * join ) { return join->ele; }
435 4987503 : FD_FN_PURE static inline ulong POOL_(ele_max) ( POOL_(t) const * join ) { return join->ele_max; }
436 :
437 3 : FD_FN_PURE static inline void * POOL_(shpool)( POOL_(t) * join ) { return join->pool; }
438 11319921 : FD_FN_PURE static inline void * POOL_(shele) ( POOL_(t) * join ) { return join->ele; }
439 :
440 13151312 : FD_FN_CONST static inline ulong POOL_(idx_null)( void ) { return (ulong)(POOL_IDX_T)(ULONG_MAX >> POOL_VER_WIDTH); }
441 13117504 : FD_FN_CONST static inline int POOL_(idx_is_null)( ulong idx ) { return idx==POOL_(idx_null)(); }
442 :
443 : FD_FN_PURE static inline ulong
444 : POOL_(idx)( POOL_(t) const * join,
445 17204715 : POOL_ELE_T const * ele ) {
446 17204715 : ulong ele_idx = (ulong)(ele - join->ele);
447 17204715 : return ele_idx<join->ele_max ? ele_idx : POOL_(idx_null)();
448 17204715 : }
449 :
450 : FD_FN_PURE static inline POOL_ELE_T const *
451 : POOL_(ele_const)( POOL_(t) const * join,
452 3078 : ulong ele_idx ) {
453 3078 : POOL_ELE_T const * ele = join->ele;
454 3078 : return (ele_idx < join->ele_max) ? (ele + ele_idx) : NULL;
455 3078 : }
456 :
457 : FD_FN_PURE static inline POOL_ELE_T *
458 : POOL_(ele)( POOL_(t) * join,
459 77319 : ulong ele_idx ) {
460 77319 : POOL_ELE_T * ele = join->ele;
461 77319 : return (ele_idx < join->ele_max) ? (ele + ele_idx) : NULL;
462 77319 : }
463 :
464 : static inline POOL_ELE_T const *
465 12 : POOL_(peek_const)( POOL_(t) const * join ) {
466 12 : POOL_(shmem_t) const * pool = join->pool;
467 12 : POOL_ELE_T const * ele = join->ele;
468 12 : ulong ele_max = join->ele_max;
469 12 : FD_COMPILER_MFENCE();
470 12 : ulong ver_top = pool->ver_top;
471 12 : # if POOL_LAZY
472 12 : ulong ver_lazy = pool->ver_lazy;
473 12 : # endif
474 12 : FD_COMPILER_MFENCE();
475 12 : ulong ele_idx = POOL_(private_vidx_idx)( ver_top );
476 12 : # if POOL_LAZY
477 12 : if( ele_idx<ele_max ) {
478 0 : return ele + ele_idx;
479 12 : } else {
480 12 : ulong lazy_idx = POOL_(private_vidx_idx)( ver_lazy );
481 12 : return (lazy_idx<ele_max) ? ele + lazy_idx : NULL;
482 12 : }
483 : # else
484 : return (ele_idx<ele_max) ? ele + ele_idx : NULL;
485 : # endif
486 12 : }
487 :
488 6 : static inline POOL_ELE_T * POOL_(peek)( POOL_(t) * join ) { return (POOL_ELE_T *)POOL_(peek_const)( join ); }
489 :
490 : static inline void
491 6 : POOL_(unlock)( POOL_(t) * join ) {
492 6 : POOL_(shmem_t) * pool = join->pool;
493 6 : FD_COMPILER_MFENCE();
494 6 : pool->ver_top += 1UL<<POOL_IDX_WIDTH;
495 6 : # if POOL_LAZY
496 6 : pool->ver_lazy += 1UL<<POOL_IDX_WIDTH;
497 6 : # endif
498 6 : FD_COMPILER_MFENCE();
499 6 : }
500 :
501 : POOL_STATIC void * POOL_(new) ( void * shmem );
502 : POOL_STATIC POOL_(t) * POOL_(join) ( void * ljoin, void * shpool, void * shele, ulong ele_max );
503 : POOL_STATIC void * POOL_(leave) ( POOL_(t) * join );
504 : POOL_STATIC void * POOL_(delete)( void * shpool );
505 :
506 : POOL_STATIC POOL_ELE_T * POOL_(acquire)( POOL_(t) * join );
507 :
508 : POOL_STATIC POOL_ELE_T * POOL_(acquire_nolock)( POOL_(t) * join );
509 :
510 : POOL_STATIC void POOL_(release)( POOL_(t) * join, POOL_ELE_T * ele );
511 :
512 : POOL_STATIC void POOL_(release_chain)( POOL_(t) * join, POOL_ELE_T * head, POOL_ELE_T * tail );
513 :
514 : POOL_STATIC int POOL_(is_empty)( POOL_(t) * join );
515 :
516 : POOL_STATIC int POOL_(lock)( POOL_(t) * join, int blocking );
517 :
518 : POOL_STATIC void POOL_(reset)( POOL_(t) * join );
519 :
520 : POOL_STATIC int POOL_(verify)( POOL_(t) const * join );
521 :
522 : POOL_STATIC FD_FN_CONST char const * POOL_(strerror)( int err );
523 :
524 : FD_PROTOTYPES_END
525 :
526 : #endif
527 :
528 : #if POOL_IMPL_STYLE!=1 /* need implementations (assumes header already included) */
529 :
530 : #include "../log/fd_log.h" /* used by constructors and verify (FIXME: Consider making a compile time option) */
531 :
532 : POOL_STATIC void *
533 12735 : POOL_(new)( void * shmem ) {
534 12735 : POOL_(shmem_t) * pool = (POOL_(shmem_t) *)shmem;
535 :
536 12735 : if( FD_UNLIKELY( !pool ) ) {
537 3 : FD_LOG_WARNING(( "NULL shmem" ));
538 3 : return NULL;
539 3 : }
540 :
541 12732 : if( FD_UNLIKELY( !fd_ulong_is_aligned( (ulong)pool, POOL_(align)() ) ) ) {
542 3 : FD_LOG_WARNING(( "misaligned shmem" ));
543 3 : return NULL;
544 3 : }
545 :
546 12729 : pool->ver_top = POOL_(private_vidx)( 0UL, POOL_(idx_null)() );
547 : # if POOL_LAZY
548 8313 : pool->ver_lazy = POOL_(private_vidx)( 0UL, POOL_(idx_null)() );
549 : # endif
550 :
551 12729 : FD_COMPILER_MFENCE();
552 12729 : pool->magic = POOL_MAGIC;
553 12729 : FD_COMPILER_MFENCE();
554 :
555 12729 : return (void *)pool;
556 12732 : }
557 :
558 : POOL_STATIC POOL_(t) *
559 : POOL_(join)( void * ljoin,
560 : void * shpool,
561 : void * shele,
562 25380 : ulong ele_max ) {
563 25380 : POOL_(t) * join = (POOL_(t) *)ljoin;
564 25380 : POOL_(shmem_t) * pool = (POOL_(shmem_t) *)shpool;
565 25380 : POOL_ELE_T * ele = (POOL_ELE_T *)shele;
566 :
567 25380 : if( FD_UNLIKELY( !join ) ) {
568 3 : FD_LOG_WARNING(( "NULL ljoin" ));
569 3 : return NULL;
570 3 : }
571 :
572 25377 : if( FD_UNLIKELY( !fd_ulong_is_aligned( (ulong)join, alignof(POOL_(t)) ) ) ) {
573 3 : FD_LOG_WARNING(( "misaligned ljoin" ));
574 3 : return NULL;
575 3 : }
576 :
577 25374 : if( FD_UNLIKELY( !pool ) ) {
578 3 : FD_LOG_WARNING(( "NULL shpool" ));
579 3 : return NULL;
580 3 : }
581 :
582 25371 : if( FD_UNLIKELY( !fd_ulong_is_aligned( (ulong)pool, POOL_(align)() ) ) ) {
583 3 : FD_LOG_WARNING(( "misaligned shpool" ));
584 3 : return NULL;
585 3 : }
586 :
587 25368 : if( FD_UNLIKELY( pool->magic!=POOL_MAGIC ) ) {
588 3 : FD_LOG_WARNING(( "bad magic" ));
589 3 : return NULL;
590 3 : }
591 :
592 25365 : if( FD_UNLIKELY( (!ele) & (!!ele_max) ) ) {
593 3 : FD_LOG_WARNING(( "NULL shele" ));
594 3 : return NULL;
595 3 : }
596 :
597 25362 : if( FD_UNLIKELY( !fd_ulong_is_aligned( (ulong)ele, alignof(POOL_ELE_T) ) ) ) {
598 3 : FD_LOG_WARNING(( "misaligned shele" ));
599 3 : return NULL;
600 3 : }
601 :
602 25359 : if( FD_UNLIKELY( ele_max>POOL_(ele_max_max)() ) ) {
603 6 : FD_LOG_WARNING(( "bad ele_max" ));
604 6 : return NULL;
605 6 : }
606 :
607 25353 : join->pool = pool;
608 25353 : join->ele = ele;
609 25353 : join->ele_max = ele_max;
610 :
611 25353 : return join;
612 25359 : }
613 :
614 : POOL_STATIC void *
615 12627 : POOL_(leave)( POOL_(t) * join ) {
616 :
617 12627 : if( FD_UNLIKELY( !join ) ) {
618 3 : FD_LOG_WARNING(( "NULL join" ));
619 3 : return NULL;
620 3 : }
621 :
622 12624 : return (void *)join;
623 12627 : }
624 :
625 : POOL_STATIC void *
626 18 : POOL_(delete)( void * shpool ) {
627 18 : POOL_(shmem_t) * pool = (POOL_(shmem_t) *)shpool;
628 :
629 18 : if( FD_UNLIKELY( !pool) ) {
630 3 : FD_LOG_WARNING(( "NULL shpool" ));
631 3 : return NULL;
632 3 : }
633 :
634 15 : if( FD_UNLIKELY( !fd_ulong_is_aligned( (ulong)pool, POOL_(align)() ) ) ) {
635 3 : FD_LOG_WARNING(( "misaligned shpool" ));
636 3 : return NULL;
637 3 : }
638 :
639 12 : if( FD_UNLIKELY( pool->magic!=POOL_MAGIC ) ) {
640 3 : FD_LOG_WARNING(( "bad magic" ));
641 3 : return NULL;
642 3 : }
643 :
644 9 : FD_COMPILER_MFENCE();
645 9 : pool->magic = 0UL;
646 9 : FD_COMPILER_MFENCE();
647 :
648 9 : return (void *)pool;
649 12 : }
650 :
651 : #if POOL_LAZY
652 :
653 : static inline POOL_ELE_T *
654 222471 : POOL_(acquire_lazy)( POOL_(t) * join ) {
655 222471 : POOL_ELE_T * ele0 = join->ele;
656 222471 : ulong ele_max = join->ele_max;
657 222471 : ulong volatile * _l = (ulong volatile *)&join->pool->ver_lazy;
658 :
659 222471 : POOL_ELE_T * ele = NULL;
660 :
661 222471 : FD_COMPILER_MFENCE();
662 :
663 222471 : for(;;) {
664 222471 : ulong ver_lazy = *_l;
665 :
666 222471 : ulong ver = POOL_(private_vidx_ver)( ver_lazy );
667 222471 : ulong ele_idx = POOL_(private_vidx_idx)( ver_lazy );
668 :
669 222471 : if( FD_LIKELY( !(ver & 1UL) ) ) { /* opt for unlocked */
670 :
671 222471 : if( FD_UNLIKELY( POOL_(idx_is_null)( ele_idx ) ) ) { /* opt for not empty */
672 0 : break;
673 0 : }
674 :
675 222471 : if( FD_UNLIKELY( ele_idx>=ele_max ) ) {
676 0 : FD_LOG_CRIT(( "corruption detected (ele_idx=%lu ele_max=%lu)", ele_idx, ele_max ));
677 0 : }
678 :
679 222471 : ulong ele_nxt = ele_idx+1UL;
680 222471 : if( FD_UNLIKELY( ele_nxt>=ele_max ) ) ele_nxt = POOL_(idx_null)();
681 :
682 222471 : ulong new_ver_lazy = POOL_(private_vidx)( ver+2UL, ele_nxt );
683 222471 : if( FD_LIKELY( POOL_(private_cas)( _l, ver_lazy, new_ver_lazy )==ver_lazy ) ) { /* opt for low contention */
684 222471 : ele = ele0 + ele_idx;
685 222471 : break;
686 222471 : }
687 222471 : }
688 :
689 0 : FD_SPIN_PAUSE();
690 0 : }
691 :
692 222471 : FD_COMPILER_MFENCE();
693 :
694 222471 : return ele;
695 222471 : }
696 :
697 : #endif /* POOL_LAZY */
698 :
699 : POOL_STATIC POOL_ELE_T *
700 4645450 : POOL_(acquire)( POOL_(t) * join ) {
701 4645450 : POOL_ELE_T * ele0 = join->ele;
702 4645450 : ulong ele_max = join->ele_max;
703 4645450 : ulong volatile * _v = (ulong volatile *)&join->pool->ver_top;
704 :
705 4645450 : POOL_ELE_T * ele = NULL;
706 :
707 4645450 : FD_COMPILER_MFENCE();
708 :
709 4645771 : for(;;) {
710 4645771 : ulong ver_top = *_v;
711 :
712 4645771 : ulong ver = POOL_(private_vidx_ver)( ver_top );
713 4645771 : ulong ele_idx = POOL_(private_vidx_idx)( ver_top );
714 :
715 4645771 : if( FD_LIKELY( !(ver & 1UL) ) ) { /* opt for unlocked */
716 :
717 4645730 : if( FD_UNLIKELY( POOL_(idx_is_null)( ele_idx ) ) ) { /* opt for not empty */
718 : # if POOL_LAZY
719 222471 : return POOL_(acquire_lazy)( join );
720 0 : # endif
721 0 : break;
722 522483 : }
723 :
724 4123247 : if( FD_UNLIKELY( ele_idx>=ele_max ) ) {
725 0 : FD_LOG_CRIT(( "corruption detected (ele_idx=%lu ele_max=%lu)", ele_idx, ele_max ));
726 0 : }
727 :
728 4123247 : ulong ele_nxt = POOL_(private_idx)( ele0[ ele_idx ].POOL_NEXT );
729 :
730 4123247 : if( FD_UNLIKELY( (ele_nxt>=ele_max) & (!POOL_(idx_is_null)( ele_nxt )) ) ) { /* ele_nxt is invalid, opt for valid */
731 : /* It is possible that another thread acquired ele_idx and
732 : repurposed ele_idx's POOL_NEXT (storing something in it that
733 : isn't a valid pool value) between when we read ver_top and
734 : when we read ele_idx's POOL_NEXT above. If so, the pool
735 : version would be changed from what we read above. We thus
736 : only signal ERR_CORRUPT if the version number hasn't changed
737 : since we read it. */
738 :
739 2 : if( FD_UNLIKELY( POOL_(private_vidx_ver)( *_v )==ver ) ) {
740 0 : FD_LOG_CRIT(( "corruption detected (ele_nxt=%lu ele_max=%lu)", ele_nxt, ele_max ));
741 0 : }
742 4123245 : } else { /* ele_nxt is valid */
743 4123245 : ulong new_ver_top = POOL_(private_vidx)( ver+2UL, ele_nxt );
744 :
745 4123245 : if( FD_LIKELY( POOL_(private_cas)( _v, ver_top, new_ver_top )==ver_top ) ) { /* opt for low contention */
746 4123017 : ele = ele0 + ele_idx;
747 4123017 : break;
748 4123017 : }
749 4123245 : }
750 4123247 : }
751 :
752 271 : FD_SPIN_PAUSE();
753 271 : }
754 :
755 4422979 : FD_COMPILER_MFENCE();
756 :
757 4422979 : return ele;
758 4645450 : }
759 :
760 : #if POOL_LAZY
761 :
762 : static inline POOL_ELE_T *
763 3168 : POOL_(acquire_lazy_nolock)( POOL_(t) * join ) {
764 3168 : POOL_ELE_T * ele0 = join->ele;
765 3168 : ulong ele_max = join->ele_max;
766 3168 : ulong * _l = &join->pool->ver_lazy;
767 :
768 3168 : POOL_ELE_T * ele = NULL;
769 :
770 3168 : ulong ver_lazy = *_l;
771 :
772 3168 : ulong ver = POOL_(private_vidx_ver)( ver_lazy );
773 3168 : ulong ele_idx = POOL_(private_vidx_idx)( ver_lazy );
774 :
775 3168 : if( FD_LIKELY( !POOL_(idx_is_null)( ele_idx ) ) ) {
776 3165 : if( FD_UNLIKELY( ele_idx>=ele_max ) ) {
777 0 : FD_LOG_CRIT(( "corruption detected (ele_idx=%lu ele_max=%lu)",
778 0 : ele_idx, ele_max ));
779 0 : }
780 :
781 3165 : ulong ele_nxt = ele_idx+1UL;
782 3165 : if( FD_UNLIKELY( ele_nxt>=ele_max ) ) {
783 6 : ele_nxt = POOL_(idx_null)();
784 6 : }
785 :
786 3165 : *_l = POOL_(private_vidx)( ver+2UL, ele_nxt );
787 3165 : ele = ele0 + ele_idx;
788 3165 : }
789 :
790 3168 : return ele;
791 3168 : }
792 :
793 : #endif /* POOL_LAZY */
794 :
795 : POOL_STATIC POOL_ELE_T *
796 3177 : POOL_(acquire_nolock)( POOL_(t) * join ) {
797 3177 : POOL_ELE_T * ele0 = join->ele;
798 3177 : ulong ele_max = join->ele_max;
799 3177 : ulong * _v = &join->pool->ver_top;
800 :
801 3177 : POOL_ELE_T * ele = NULL;
802 :
803 3177 : ulong ver_top = *_v;
804 :
805 3177 : ulong ver = POOL_(private_vidx_ver)( ver_top );
806 3177 : ulong ele_idx = POOL_(private_vidx_idx)( ver_top );
807 :
808 3177 : if( FD_UNLIKELY( POOL_(idx_is_null)( ele_idx ) ) ) {
809 : # if POOL_LAZY
810 3168 : return POOL_(acquire_lazy_nolock)( join );
811 : # endif
812 3168 : } else {
813 9 : if( FD_UNLIKELY( ele_idx>=ele_max ) ) {
814 0 : FD_LOG_CRIT(( "corruption detected (ele_idx=%lu ele_max=%lu)",
815 0 : ele_idx, ele_max ));
816 0 : }
817 :
818 9 : ulong ele_nxt = POOL_(private_idx)( ele0[ ele_idx ].POOL_NEXT );
819 :
820 9 : if( FD_UNLIKELY( (ele_nxt>=ele_max) & (!POOL_(idx_is_null)( ele_nxt )) ) ) {
821 0 : FD_LOG_CRIT(( "corruption detected (ele_nxt=%lu ele_max=%lu)",
822 0 : ele_nxt, ele_max ));
823 0 : }
824 :
825 9 : *_v = POOL_(private_vidx)( ver+2UL, ele_nxt );
826 9 : ele = ele0 + ele_idx;
827 9 : }
828 :
829 9 : return ele;
830 3177 : }
831 :
832 : POOL_STATIC void
833 : POOL_(release)( POOL_(t) * join,
834 4115199 : POOL_ELE_T * ele ) {
835 4115199 : ulong ele_max = join->ele_max;
836 4115199 : ulong volatile * _v = (ulong volatile *)&join->pool->ver_top;
837 :
838 4115199 : ulong ele_idx = (ulong)(ele - join->ele);
839 4115199 : if( FD_UNLIKELY( ele_idx>=ele_max ) ) FD_LOG_CRIT(( "corruption detected: ele=%p is not in bounds", (void *)ele ));
840 :
841 4115199 : FD_COMPILER_MFENCE();
842 :
843 4115199 : for(;;) {
844 4115199 : ulong ver_top = *_v;
845 :
846 4115199 : ulong ver = POOL_(private_vidx_ver)( ver_top );
847 4115199 : ulong ele_nxt = POOL_(private_vidx_idx)( ver_top );
848 :
849 4115199 : if( FD_LIKELY( !(ver & 1UL) ) ) { /* opt for unlocked */
850 :
851 4115199 : if( FD_UNLIKELY( (ele_nxt>=ele_max) & (!POOL_(idx_is_null)( ele_nxt )) ) ) { /* opt for not corrupt */
852 0 : FD_LOG_CRIT(( "corruption detected (ele_nxt=%lu ele_max=%lu)", ele_nxt, ele_max ));
853 0 : }
854 :
855 4115199 : ele->POOL_NEXT = POOL_(private_cidx)( ele_nxt );
856 :
857 4115199 : ulong new_ver_top = POOL_(private_vidx)( ver+2UL, ele_idx );
858 :
859 4115199 : if( FD_LIKELY( POOL_(private_cas)( _v, ver_top, new_ver_top )==ver_top ) ) break; /* opt for low contention */
860 :
861 4115199 : }
862 :
863 0 : FD_SPIN_PAUSE();
864 0 : }
865 :
866 4115199 : FD_COMPILER_MFENCE();
867 4115199 : }
868 :
869 : POOL_STATIC void
870 : POOL_(release_chain)( POOL_(t) * join,
871 : POOL_ELE_T * head,
872 1461 : POOL_ELE_T * tail ) {
873 1461 : ulong ele_max = join->ele_max;
874 1461 : ulong volatile * _v = (ulong volatile *)&join->pool->ver_top;
875 :
876 1461 : ulong head_idx = (ulong)(head - join->ele);
877 1461 : if( FD_UNLIKELY( head_idx>=ele_max ) ) FD_LOG_CRIT(( "corruption detected: ele=%p is not in bounds", (void *)head ));
878 :
879 1461 : ulong tail_idx = (ulong)(tail - join->ele);
880 1461 : if( FD_UNLIKELY( tail_idx>=ele_max ) ) FD_LOG_CRIT(( "corruption detected: ele=%p is not in bounds", (void *)tail ));
881 :
882 1461 : FD_COMPILER_MFENCE();
883 :
884 1461 : for(;;) {
885 1461 : ulong ver_top = *_v;
886 :
887 1461 : ulong ver = POOL_(private_vidx_ver)( ver_top );
888 1461 : ulong ele_nxt = POOL_(private_vidx_idx)( ver_top );
889 :
890 1461 : if( FD_LIKELY( !(ver & 1UL) ) ) { /* opt for unlocked */
891 :
892 1461 : if( FD_UNLIKELY( (ele_nxt>=ele_max) & (!POOL_(idx_is_null)( ele_nxt )) ) ) { /* opt for not corrupt */
893 0 : FD_LOG_CRIT(( "corruption detected (ele_nxt=%lu ele_max=%lu)", ele_nxt, ele_max ));
894 0 : }
895 :
896 1461 : tail->POOL_NEXT = POOL_(private_cidx)( ele_nxt );
897 :
898 1461 : ulong new_ver_top = POOL_(private_vidx)( ver+2UL, head_idx );
899 :
900 1461 : if( FD_LIKELY( POOL_(private_cas)( _v, ver_top, new_ver_top )==ver_top ) ) break; /* opt for low contention */
901 :
902 1461 : }
903 :
904 0 : FD_SPIN_PAUSE();
905 0 : }
906 :
907 1461 : FD_COMPILER_MFENCE();
908 1461 : }
909 :
910 : POOL_STATIC int
911 0 : POOL_(is_empty)( POOL_(t) * join ) {
912 0 : POOL_(shmem_t) const * pool = join->pool;
913 0 : FD_COMPILER_MFENCE();
914 0 : ulong ver_top = pool->ver_top;
915 : # if POOL_LAZY
916 : ulong ver_lazy = pool->ver_lazy;
917 : # endif
918 0 : FD_COMPILER_MFENCE();
919 :
920 0 : ulong top_idx = POOL_(private_vidx_idx)( ver_top );
921 : # if POOL_LAZY
922 : ulong ele_max = join->ele_max;
923 : if( FD_LIKELY( top_idx<ele_max ) ) return 0; /* explicit stack non-empty */
924 : ulong lazy_idx = POOL_(private_vidx_idx)( ver_lazy );
925 : return !(lazy_idx<ele_max); /* empty only if lazy also empty */
926 : # else
927 0 : return POOL_(idx_is_null)( top_idx );
928 0 : # endif
929 0 : }
930 :
931 : POOL_STATIC int
932 : POOL_(lock)( POOL_(t) * join,
933 9 : int blocking ) {
934 9 : ulong volatile * _v = (ulong volatile *)&join->pool->ver_top;
935 : # if POOL_LAZY
936 : ulong volatile * _l = (ulong volatile *)&join->pool->ver_lazy;
937 : # endif
938 :
939 9 : int err = FD_POOL_SUCCESS;
940 :
941 9 : FD_COMPILER_MFENCE();
942 :
943 9 : ulong ver_top;
944 9 : for(;;) {
945 :
946 : /* use a test-and-test-and-set style for reduced contention */
947 :
948 9 : ver_top = *_v;
949 9 : if( FD_LIKELY( !(ver_top & (1UL<<POOL_IDX_WIDTH)) ) ) { /* opt for low contention */
950 6 : ver_top = POOL_(private_fetch_and_or)( _v, 1UL<<POOL_IDX_WIDTH );
951 6 : if( FD_LIKELY( !(ver_top & (1UL<<POOL_IDX_WIDTH)) ) ) break; /* opt for low contention */
952 6 : }
953 :
954 3 : if( FD_UNLIKELY( !blocking ) ) { /* opt for blocking */
955 3 : err = FD_POOL_ERR_AGAIN;
956 3 : goto fail;
957 3 : }
958 :
959 0 : FD_SPIN_PAUSE();
960 0 : }
961 :
962 6 : FD_COMPILER_MFENCE();
963 :
964 : # if POOL_LAZY
965 :
966 6 : for(;;) {
967 :
968 : /* use a test-and-test-and-set style for reduced contention */
969 :
970 6 : ulong ver_lazy = *_l;
971 6 : if( FD_LIKELY( !(ver_lazy & (1UL<<POOL_IDX_WIDTH)) ) ) { /* opt for low contention */
972 6 : ver_lazy = POOL_(private_fetch_and_or)( _l, 1UL<<POOL_IDX_WIDTH );
973 6 : if( FD_LIKELY( !(ver_lazy & (1UL<<POOL_IDX_WIDTH)) ) ) break; /* opt for low contention */
974 6 : }
975 :
976 0 : if( FD_UNLIKELY( !blocking ) ) { /* opt for blocking */
977 0 : *_v = POOL_(private_vidx)( POOL_(private_vidx_ver)( ver_top )+2UL, POOL_(private_vidx_idx)( ver_top ) ); /* unlock */
978 0 : err = FD_POOL_ERR_AGAIN;
979 0 : goto fail;
980 0 : }
981 :
982 0 : FD_SPIN_PAUSE();
983 0 : }
984 :
985 6 : FD_COMPILER_MFENCE();
986 :
987 6 : # endif
988 :
989 9 : fail:
990 9 : return err;
991 6 : }
992 :
993 : #if !POOL_LAZY
994 :
995 : POOL_STATIC void
996 4413 : POOL_(reset)( POOL_(t) * join ) {
997 4413 : POOL_(shmem_t) * pool = join->pool;
998 4413 : POOL_ELE_T * ele = join->ele;
999 4413 : ulong ele_max = join->ele_max;
1000 :
1001 : /* Insert all elements in increasing order */
1002 :
1003 4413 : ulong ele_top = 0UL;
1004 4413 : if( FD_UNLIKELY( !ele_max ) ) ele_top = POOL_(idx_null)();
1005 4413 : else {
1006 92415 : for( ulong ele_idx=ele_top; ele_idx<(ele_max-1UL); ele_idx++ ) {
1007 88002 : ele[ ele_idx ].POOL_NEXT = POOL_(private_cidx)( ele_idx+1UL );
1008 88002 : }
1009 4413 : ele[ ele_max-1UL ].POOL_NEXT = POOL_(private_cidx)( POOL_(idx_null)() );
1010 4413 : }
1011 :
1012 4413 : ulong ver_top = pool->ver_top;
1013 4413 : ulong ver = POOL_(private_vidx_ver)( ver_top );
1014 4413 : pool->ver_top = POOL_(private_vidx)( ver, ele_top );
1015 4413 : }
1016 :
1017 : #else
1018 :
1019 : POOL_STATIC void
1020 8328 : POOL_(reset)( POOL_(t) * join ) {
1021 8328 : POOL_(shmem_t) * pool = join->pool;
1022 :
1023 : /* Assign all elements to the bump allocator */
1024 :
1025 8328 : ulong ele_top = POOL_(idx_null)();
1026 8328 : ulong ele_lazy = 0UL;
1027 :
1028 8328 : ulong ver_top = pool->ver_top;
1029 8328 : ulong ver_lazy = pool->ver_lazy;
1030 8328 : pool->ver_top = POOL_(private_vidx)( POOL_(private_vidx_ver)( ver_top ), ele_top );
1031 8328 : pool->ver_lazy = POOL_(private_vidx)( POOL_(private_vidx_ver)( ver_lazy ), ele_lazy );
1032 8328 : }
1033 :
1034 : #endif
1035 :
1036 : POOL_STATIC int
1037 108 : POOL_(verify)( POOL_(t) const * join ) {
1038 :
1039 6642 : # define POOL_TEST(c) do { \
1040 6642 : if( FD_UNLIKELY( !(c) ) ) { FD_LOG_WARNING(( "FAIL: %s", #c )); return FD_POOL_ERR_CORRUPT; } \
1041 6642 : } while(0)
1042 :
1043 : /* Validate join */
1044 :
1045 108 : POOL_TEST( join );
1046 108 : POOL_TEST( fd_ulong_is_aligned( (ulong)join, alignof(POOL_(t)) ) );
1047 :
1048 108 : POOL_(shmem_t) const * pool = join->pool;
1049 108 : POOL_ELE_T const * ele = join->ele;
1050 108 : ulong ele_max = join->ele_max;
1051 :
1052 108 : POOL_TEST( pool );
1053 108 : POOL_TEST( fd_ulong_is_aligned( (ulong)pool, POOL_(align)() ) );
1054 :
1055 108 : POOL_TEST( (!!ele)| (!ele_max) );
1056 108 : POOL_TEST( fd_ulong_is_aligned( (ulong)ele, alignof(POOL_ELE_T) ) );
1057 :
1058 108 : POOL_TEST( ele_max<=POOL_(ele_max_max)() );
1059 :
1060 : /* Validate pool metadata */
1061 :
1062 108 : ulong magic = pool->magic;
1063 108 : ulong ver_top = pool->ver_top;
1064 :
1065 : /* version arbitrary as far as verify is concerned */
1066 108 : ulong ele_idx = POOL_(private_vidx_idx)( ver_top );
1067 :
1068 108 : POOL_TEST( magic==POOL_MAGIC );
1069 :
1070 : /* Validate pool elements */
1071 :
1072 108 : ulong ele_rem = ele_max;
1073 5766 : while( ele_idx<ele_max ) {
1074 5658 : POOL_TEST( ele_rem ); ele_rem--; /* no cycles */
1075 5658 : ele_idx = POOL_(private_idx)( ele[ ele_idx ].POOL_NEXT );
1076 5658 : }
1077 :
1078 108 : POOL_TEST( POOL_(idx_is_null)( ele_idx ) );
1079 :
1080 : # if POOL_LAZY
1081 12 : ulong lazy_idx = POOL_(private_vidx_idx)( pool->ver_lazy );
1082 12 : ulong lazy_free = POOL_(idx_is_null)( lazy_idx ) ? 0UL : (ele_max-lazy_idx);
1083 12 : POOL_TEST( lazy_free<=ele_rem );
1084 12 : # endif
1085 :
1086 12 : # undef POOL_TEST
1087 :
1088 108 : return FD_POOL_SUCCESS;
1089 12 : }
1090 :
1091 : POOL_STATIC char const *
1092 12 : POOL_(strerror)( int err ) {
1093 12 : switch( err ) {
1094 3 : case FD_POOL_SUCCESS: return "success";
1095 3 : case FD_POOL_ERR_AGAIN: return "try again";
1096 3 : case FD_POOL_ERR_CORRUPT: return "corruption detected";
1097 3 : default: break;
1098 12 : }
1099 3 : return "unknown";
1100 12 : }
1101 :
1102 : #endif
1103 :
1104 : #undef POOL_
1105 : #undef POOL_STATIC
1106 : #undef POOL_VER_WIDTH
1107 :
1108 : #undef POOL_LAZY
1109 : #undef POOL_IMPL_STYLE
1110 : #undef POOL_MAGIC
1111 : #undef POOL_IDX_WIDTH
1112 : #undef POOL_ALIGN
1113 : #undef POOL_NEXT
1114 : #undef POOL_IDX_T
1115 : #undef POOL_ELE_T
1116 : #undef POOL_NAME
|
