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