Line data Source code
1 : /* Generate prototypes, inlines and/or implementations for concurrent
2 : persistent shared element pools. A pool can hold a practically
3 : unbounded number of elements. Acquiring an element from and
4 : releasing an element to a pool are typically fast O(1) time.
5 : Requires small O(1) space per element.
6 :
7 : The current implementation is based on a lockfree stack. Acquire and
8 : release are done via atomic compare-and-swap of the stack top. As
9 : such, concurrent usage requires FD_HAS_ATOMIC support (this can still
10 : be used on platforms without FD_HAS_ATOMIC but it will not be safe
11 : for concurrent usage). Stack top versioning is used to handle ABA.
12 : Versioning has been been tweaked to support locked pool operations
13 : like initialization (and thus this can also be used without changes
14 : as a more conventional spin lock based concurrent stack).
15 : Unsurprisingly, the current implementation is equally usable as a
16 : concurrent element stack (though the implementation may be changed in
17 : the future to better support ultra high contention ultra high
18 : concurrency ala fd_alloc).
19 :
20 : The current implementation is optimized for pools with a moderate
21 : number of reasonably localized users (e.g. a handful of cores and
22 : memory on the same NUMA node). Various operations are slightly more
23 : optimal when the size of a pool element is an integer power of 2.
24 : Operations do much internal integrity checking / bounds checking for
25 : use in high reliability / high security environments.
26 :
27 : This API is designed for tight and flexible composition with treaps,
28 : heaps, lists, maps, etc. Further, a pool can be persisted beyond the
29 : lifetime of the creating process, be used inter-process, be relocated
30 : in memory, be naively serialized/deserialized, be moved between
31 : hosts, use index compression for cache and memory bandwidth
32 : efficiency, etc.
33 :
34 : Typical usage:
35 :
36 : struct myele {
37 : ulong next; // Technically "POOL_IDX_T POOL_NEXT" (default is ulong next), managed by the mypool when in the mypool
38 :
39 : ... next can be located arbitrarily in the element and can be
40 : ... reused for other purposes when the element is not in a
41 : ... mypool. elements are all located in a linear array element
42 : ... store whose lifetime is at least that of the mypool.
43 :
44 : };
45 :
46 : typedef struct myele myele_t;
47 :
48 : #define POOL_NAME mypool
49 : #define POOL_ELE_T myele_t
50 : #include "tmpl/fd_pool_para.c"
51 :
52 : will declare the following APIs as a header only style library in the
53 : compilation unit:
54 :
55 : // A mypool_t is a stack declaration friendly quasi-opaque handle
56 : // used to describe a join to a mypool. E.g. it is fine to do
57 : // "mypool_t join[1];" to allocate a mypool_t but the contents
58 : // should be used directly.
59 :
60 : typedef struct mypool_private mypool_t;
61 :
62 : // Constructors
63 :
64 : // mypool_ele_max_max returns the maximum element store capacity
65 : // compatible with a mypool.
66 :
67 : ulong mypool_ele_max_max( void );
68 :
69 : // mypool_{align,footprint} returns the alignment and footprint
70 : // needed for a memory region to be used as a mypool. align will
71 : // be an integer power-of-two and footprint will be a multiple of
72 : // align.
73 : //
74 : // mypool_new formats a memory region with the appropriate
75 : // alignment and footprint into a mypool. shmem points in the the
76 : // caller's address space of the memory region to format. Returns
77 : // shmem on success (mypool has ownership of the memory region) and
78 : // NULL on failure (no changes, logs details). Caller is not
79 : // joined on return. The mypool will be empty and unlocked.
80 : //
81 : // mypool_join joins a mypool. ljoin points to a mypool_t
82 : // compatible memory region in the caller's address space used to
83 : // hold info about the local join, shpool points in the caller's
84 : // address space to the memory region containing the mypool, shele
85 : // points in the caller's address space to mypool's element store,
86 : // and ele_max is the element store's capacity. Returns a handle
87 : // to the caller's local join on success (join has ownership of the
88 : // ljoin region) and NULL on failure (no changes, logs details).
89 : //
90 : // mypool_leave leaves a mypool. join points to a current local
91 : // join. Returns the memory used for the local join (caller has
92 : // ownership on return and caller is no longer joined) on success
93 : // and NULL on failure (no changes, logs details). Use the join
94 : // accessors before leaving to get shpool, shele and ele_max used
95 : // by the join if needed.
96 : //
97 : // mypool_delete unformats a memory region used as a mypool.
98 : // Assumes shpool points in the caller's address space to the
99 : // memory region containing the mypool and that there are no
100 : // current joins globally. Returns shpool on success (caller has
101 : // ownership of the memory region and any elements still in the
102 : // mypool are acquired by the caller) and NULL on failure (no
103 : // changes, logs details).
104 :
105 : ulong mypool_align ( void );
106 : ulong mypool_footprint( void );
107 : void * mypool_new ( void * shmem );
108 : mypool_t * mypool_join ( void * ljoin, void * shpool, void * shele, ulong ele_max );
109 : void * mypool_leave ( mypool_t * join );
110 : void * mypool_delete ( void * shpool );
111 :
112 : // mypool_{shpool,shele,ele_max} return join details. Assumes join
113 : // is a current local join. mypool_{shpool_const,shele_const} are
114 : // const correct versions. The lifetime of the returned pointers
115 : // is the lifetime of the join.
116 :
117 : void const * mypool_shpool_const( mypool_t const * join );
118 : void const * mypool_shele_const ( mypool_t const * join );
119 : ulong mypool_ele_max ( mypool_t const * join );
120 :
121 : void * mypool_shpool( mypool_t * join );
122 : void * mypool_shele ( mypool_t * join );
123 :
124 : // mypool_idx_null returns the element store index used to
125 : // represent null for a mypool.
126 : //
127 : // mypool_idx_is_null returns 1 if an element store index is the
128 : // null index value and 0 otherwise.
129 : //
130 : // mypool_idx returns the element store index for the element
131 : // pointed to by ele in the caller's address space. Assumes join
132 : // is a current local join. If ele is NULL or not into the element
133 : // store, returns the element store null index.
134 : //
135 : // mypool_ele returns a pointer in the caller's address space to
136 : // the element whose element store index is ele_idx. If ele_idx is
137 : // the null value or invalid, returns NULL. mypool_ele_const is a
138 : // const correct version.
139 : //
140 : // These are usually not needed but allow translating pointers to
141 : // element store elements from one address space to another.
142 :
143 : ulong mypool_idx_null ( void );
144 : int mypool_idx_is_null( ulong idx );
145 : ulong mypool_idx ( mypool_t const * join, myele_t const * ele );
146 :
147 : myele_t const * mypool_ele_const( mypool_t const * join, ulong ele_idx );
148 : myele_t * mypool_ele ( mypool_t * join, ulong ele_idx );
149 :
150 : // mypool_peek returns a pointer in the local address space to the
151 : // next element to acquire from the mypool or NULL if the mypool
152 : // was empty at some point during the call. mypool_peek_const is a
153 : // const correct version. Because of concurrent operations, unless
154 : // the caller is holding a lock on the mypool, this may not be the
155 : // actual element the caller will acquire next from the mypool.
156 :
157 : myele_t const * mypool_peek_const( mypool_t const * join );
158 : myele_t * mypool_peek ( mypool_t * join );
159 :
160 : // mypool_acquire acquires an element from a mypool. Assumes join
161 : // is a current local join. If the mypool is empty or an error
162 : // occurs, returns sentinel (arbitrary). A non-zero / zero value
163 : // for blocking indicates locked operations on the mypool are / are
164 : // not allowed to block the caller. If opt_err is not NULL, on
165 : // return, *_opt_err will indicate FD_POOL_SUCCESS (zero) or a
166 : // FD_POOL_ERR code (negative). On success, the returned value
167 : // will be a pointer in the caller's address space to the element
168 : // store element acquired from the mypool. On failure for any
169 : // reason, the value returned will be sentinel and the mypool will
170 : // be unchanged. Reasons for failure:
171 : //
172 : // FD_POOL_ERR_EMPTY: the mypool contained no elements at some
173 : // point during the call.
174 : //
175 : // FD_POOL_ERR_AGAIN: the mypool was locked at some point during
176 : // the call. Never returned for a blocking call (but then locking
177 : // operations can then potentially block the caller indefinitely).
178 : //
179 : // FD_POOL_ERR_CORRUPT: memory corruption was detected during the
180 : // call.
181 :
182 : myele_t * mypool_acquire( mypool_t * join, myele_t * sentinel, int blocking, int * _opt_err );
183 :
184 : // mypool_release releases an element to a mypoool. Assumes join
185 : // is a current local join, ele is a pointer in the caller's
186 : // address space to the element, and the element is currently not
187 : // in the mypool. Returns FD_POOL_SUCCESS (zero) on success (the
188 : // element will be in the mypool on return) and a FD_POOL_ERR code
189 : // (negative) on failure (the element will not be in the mypool on
190 : // return). Reasons for failure:
191 : //
192 : // FD_POOL_ERR_INVAL: ele does not point to an element in mypool's
193 : // element store.
194 : //
195 : // FD_POOL_ERR_AGAIN: the mypool was locked at some point during
196 : // the call. Never returned for a blocking call (but locking
197 : // operations can then potentially block the caller indefinitely).
198 : //
199 : // FD_POOL_ERR_CORRUPT: memory corruption was detected during the
200 : // call.
201 :
202 : int mypool_release( mypool_t * join, myele_t * ele, int blocking );
203 :
204 : // mypool_is_locked returns whether or not a mypool is locked.
205 : // Assumes join is a current local join.
206 :
207 : int mypool_is_locked( mypool_t const * join );
208 :
209 : // mypool_lock will lock a mypool (e.g. pausing concurrent acquire
210 : // / release operations). A non-zero / zero value for blocking
211 : // indicates the call should / should not wait to lock the mypool
212 : // if it is currently locked. Returns FD_POOL_SUCCESS on success
213 : // (caller has the lock on return) and FD_POOL_ERR_AGAIN on failure
214 : // (pool was already locked at some point during the call). AGAIN
215 : // is never returned if blocking is requested. Assumes join is a
216 : // current local join.
217 :
218 : int mypool_lock( mypool_t * join, int blocking );
219 :
220 : // mypool_unlock will unlock a mypool (e.g. resuming concurrent
221 : // acquire / release operations). Assumes join is a current local
222 : // join and the caller has a lock on mypool. Guaranteed to
223 : // succeed.
224 :
225 : void mypool_unlock( mypool_t * join );
226 :
227 : // mypool_reset resets the mypool. On return, it will hold all but
228 : // the leading sentinel_cnt elements in the element store (e.g.
229 : // initialization after creation) in ascending order. If
230 : // sentinel_cnt is greater than or equal to the element store
231 : // capacity, the mypool will be empty on return. Thus, on return,
232 : // if sentinel_cnt is zero, every element in the element store will
233 : // be in the mypool and, if sentinel_cnt is ele_max or greater
234 : // (e.g. ULONG_MAX), every element will be removed from the mypool.
235 : // Assumes join is a current local join and the mypool is locked or
236 : // otherwise idle.
237 :
238 : void mypool_reset( mypool_t * join, ulong sentinel_cnt );
239 :
240 : // mypool_verify returns FD_POOL_SUCCESS if join appears to be
241 : // current local join to a valid mypool and FD_POOL_ERR_CORRUPT
242 : // otherwise (logs details). Assumes join is a current local join
243 : // and the mypool is locked or otherwise idle.
244 :
245 : int mypool_verify( mypool_t const * join );
246 :
247 : // mypool_strerror converts an FD_POOL_SUCCESS / FD_POOL_ERR code
248 : // into a human readable cstr. The lifetime of the returned
249 : // pointer is infinite. The returned pointer is always to a
250 : // non-NULL cstr.
251 :
252 : char const * mypool_strerror( int err );
253 :
254 : Do this as often as desired in a compilation unit to get different
255 : types of concurrent pools. Options exist for generating library
256 : header prototypes and/or library implementations for concurrent pools
257 : usable across multiple compilation units. Additional options exist
258 : to use index compression, configuring versioning, etc. */
259 :
260 : /* POOL_NAME gives the API prefix to use for pool */
261 :
262 : #ifndef POOL_NAME
263 : #error "Define POOL_NAME"
264 : #endif
265 :
266 : /* POOL_ELE_T is the pool element type. */
267 :
268 : #ifndef POOL_ELE_T
269 : #error "Define POOL_ELE_T"
270 : #endif
271 :
272 : /* POOL_IDX_T is the type used for the next field in the POOL_ELE_T.
273 : Should be a primitive unsigned integer type. Defaults to ulong. A
274 : pool can't use element stores with a capacity that can't be
275 : represented by a POOL_IDX_T. (E.g. if ushort, the maximum capacity
276 : pool compatible element store is 65535 elements.) */
277 :
278 : #ifndef POOL_IDX_T
279 : #define POOL_IDX_T ulong
280 : #endif
281 :
282 : /* POOL_NEXT is the POOL_ELE_T next field */
283 :
284 : #ifndef POOL_NEXT
285 : #define POOL_NEXT next
286 : #endif
287 :
288 : /* POOL_ALIGN gives the alignment required for the pool shared memory.
289 : Default is 128 for double cache line alignment. Should be at least
290 : ulong alignment. */
291 :
292 : #ifndef POOL_ALIGN
293 : #define POOL_ALIGN (128UL)
294 : #endif
295 :
296 : /* POOL_IDX_WIDTH gives the number of bits in a ulong to reserve for
297 : encoding the element store index in a versioned index. Element store
298 : capacity should be representable in this width. Default is 43 bits
299 : (e.g. enough to support a ~1 PiB element store of 128 byte elements).
300 : The versioning width will be 64-POOL_IDX_WIDTH. Since the least
301 : significant bit of the version is used to indicate global locking,
302 : versioning width should be at least 2 and ideally as large as
303 : possible. With the 43 default, version numbers will not be reused
304 : until 2^20 individual operations have been done. */
305 :
306 : #ifndef POOL_IDX_WIDTH
307 29295030 : #define POOL_IDX_WIDTH (43)
308 : #endif
309 :
310 : /* POOL_MAGIC is the magic number to use for the structure to aid in
311 : persistent and or IPC usage. */
312 :
313 : #ifndef POOL_MAGIC
314 6 : #define POOL_MAGIC (0xf17eda2c37c90010UL) /* firedancer cpool version 0 */
315 : #endif
316 :
317 : /* POOL_IMPL_STYLE controls what to generate:
318 : 0 - local use only
319 : 1 - library header declaration
320 : 2 - library implementation */
321 :
322 : #ifndef POOL_IMPL_STYLE
323 : #define POOL_IMPL_STYLE 0
324 : #endif
325 :
326 : /* Commom pool error codes (FIXME: probably should get around to making
327 : unified error codes and string handling across all util at least so
328 : we don't have to do this in the generator itself) */
329 :
330 7324662 : #define FD_POOL_SUCCESS ( 0)
331 780 : #define FD_POOL_ERR_INVAL (-1)
332 3675 : #define FD_POOL_ERR_AGAIN (-2)
333 3 : #define FD_POOL_ERR_CORRUPT (-3)
334 3672 : #define FD_POOL_ERR_EMPTY (-4)
335 : //#define FD_POOL_ERR_FULL (-5)
336 : //#define FD_POOL_ERR_KEY (-6)
337 :
338 : /* Implementation *****************************************************/
339 :
340 14649366 : #define POOL_VER_WIDTH (64-POOL_IDX_WIDTH)
341 :
342 : #if POOL_IMPL_STYLE==0 /* local use only */
343 : #define POOL_STATIC FD_FN_UNUSED static
344 : #else /* library header and/or implementation */
345 : #define POOL_STATIC
346 : #endif
347 :
348 40292013 : #define POOL_(n) FD_EXPAND_THEN_CONCAT3(POOL_NAME,_,n)
349 :
350 : #if POOL_IMPL_STYLE!=2 /* need header */
351 :
352 : #include "../bits/fd_bits.h"
353 :
354 : struct __attribute__((aligned(POOL_ALIGN))) POOL_(shmem_private) {
355 :
356 : /* Note: there is no free count because that that isn't precisely
357 : knowable in a portable concurrent data structure. (Not enough bits
358 : to squeeze into ver_top for large pools, requiring 128-bit wide
359 : ver_top would limit supported targets, etc). */
360 :
361 : ulong magic; /* == POOL_MAGIC */
362 : ulong ver_top; /* Versioned index of the free stack top, top is in [0,ele_max) (not-empty) or is idx_null (empty) */
363 : };
364 :
365 : typedef struct POOL_(shmem_private) POOL_(shmem_t);
366 :
367 : struct POOL_(private) {
368 : POOL_(shmem_t) * pool; /* Pool location in the local address space */
369 : POOL_ELE_T * ele; /* Element store location in the local address space, NULL okay if ele_max==0 */
370 : ulong ele_max; /* Element store capacity, in [0,ele_max_max] */
371 : };
372 :
373 : typedef struct POOL_(private) POOL_(t);
374 :
375 : FD_PROTOTYPES_BEGIN
376 :
377 : /* pool_private_vidx pack ver and idx into a versioned idx. ver is
378 : masked to fit into POOL_VER_WIDTH bits. idx is assumed in
379 : [0,ele_max_max].
380 :
381 : pool_private_vidx_{ver,idx} extract the {version,index} from a
382 : versioned index and will fit into {POOL_VER_WIDTH,POOL_IDX_WIDTH}
383 : bits. */
384 :
385 7320993 : FD_FN_CONST static inline ulong POOL_(private_vidx)( ulong ver, ulong idx ) { return (ver<<POOL_IDX_WIDTH) | idx; }
386 :
387 7324665 : FD_FN_CONST static inline ulong POOL_(private_vidx_ver)( ulong ver_idx ) { return ver_idx >> POOL_IDX_WIDTH; }
388 7324683 : FD_FN_CONST static inline ulong POOL_(private_vidx_idx)( ulong ver_idx ) { return (ver_idx << POOL_VER_WIDTH) >> POOL_VER_WIDTH; }
389 :
390 : /* pool_private_{cidx,idx} compress/decompress a 64-bit in-register
391 : index to/from its in-memory representation. */
392 :
393 3669699 : FD_FN_CONST static inline POOL_IDX_T POOL_(private_cidx)( ulong idx ) { return (POOL_IDX_T) idx; }
394 3663555 : FD_FN_CONST static inline ulong POOL_(private_idx) ( ulong cidx ) { return (ulong) cidx; }
395 :
396 : /* pool_private_cas does a ulong FD_ATOMIC_CAS when FD_HAS_ATOMIC
397 : support is available and emulates it when not. Similarly for
398 : pool_private_fetch_and_or. When emulated, the pool will not be safe
399 : to use concurrently (but will still work). */
400 :
401 : static inline ulong
402 : POOL_(private_cas)( ulong volatile * p,
403 : ulong c,
404 7320972 : ulong s ) {
405 7320972 : ulong o;
406 7320972 : FD_COMPILER_MFENCE();
407 7320972 : # if FD_HAS_ATOMIC
408 7320972 : o = FD_ATOMIC_CAS( p, c, s );
409 : # else
410 : o = *p;
411 : *p = fd_ulong_if( o==c, s, c );
412 : # endif
413 7320972 : FD_COMPILER_MFENCE();
414 7320972 : return o;
415 7320972 : }
416 :
417 : static inline ulong
418 : POOL_(private_fetch_and_or)( ulong volatile * p,
419 3 : ulong b ) {
420 3 : ulong x;
421 3 : FD_COMPILER_MFENCE();
422 3 : # if FD_HAS_ATOMIC
423 3 : x = FD_ATOMIC_FETCH_AND_OR( p, b );
424 : # else
425 : x = *p;
426 : *p = x | b;
427 : # endif
428 3 : FD_COMPILER_MFENCE();
429 3 : return x;
430 3 : }
431 :
432 0 : FD_FN_CONST static inline ulong POOL_(ele_max_max)( void ) { return (ulong)(POOL_IDX_T)(ULONG_MAX >> POOL_VER_WIDTH); }
433 :
434 0 : FD_FN_CONST static inline ulong POOL_(align) ( void ) { return alignof(POOL_(shmem_t)); }
435 0 : FD_FN_CONST static inline ulong POOL_(footprint)( void ) { return sizeof (POOL_(shmem_t)); }
436 :
437 3 : FD_FN_PURE static inline void const * POOL_(shpool_const)( POOL_(t) const * join ) { return join->pool; }
438 3 : FD_FN_PURE static inline void const * POOL_(shele_const) ( POOL_(t) const * join ) { return join->ele; }
439 3 : FD_FN_PURE static inline ulong POOL_(ele_max) ( POOL_(t) const * join ) { return join->ele_max; }
440 :
441 3 : FD_FN_PURE static inline void * POOL_(shpool)( POOL_(t) * join ) { return join->pool; }
442 6 : FD_FN_PURE static inline void * POOL_(shele) ( POOL_(t) * join ) { return join->ele; }
443 :
444 0 : FD_FN_CONST static inline ulong POOL_(idx_null)( void ) { return (ulong)(POOL_IDX_T)(ULONG_MAX >> POOL_VER_WIDTH); }
445 10988217 : FD_FN_CONST static inline int POOL_(idx_is_null)( ulong idx ) { return idx==POOL_(idx_null)(); }
446 :
447 : FD_FN_PURE static inline ulong
448 : POOL_(idx)( POOL_(t) const * join,
449 18067218 : POOL_ELE_T const * ele ) {
450 18067218 : ulong ele_idx = (ulong)(ele - join->ele);
451 18067218 : return ele_idx<join->ele_max ? ele_idx : POOL_(idx_null)();
452 18067218 : }
453 :
454 : FD_FN_PURE static inline POOL_ELE_T const *
455 : POOL_(ele_const)( POOL_(t) const * join,
456 3078 : ulong ele_idx ) {
457 3078 : POOL_ELE_T const * ele = join->ele;
458 3078 : return (ele_idx < join->ele_max) ? (ele + ele_idx) : NULL;
459 3078 : }
460 :
461 : FD_FN_PURE static inline POOL_ELE_T *
462 : POOL_(ele)( POOL_(t) * join,
463 3078 : ulong ele_idx ) {
464 3078 : POOL_ELE_T * ele = join->ele;
465 3078 : return (ele_idx < join->ele_max) ? (ele + ele_idx) : NULL;
466 3078 : }
467 :
468 : static inline POOL_ELE_T const *
469 30 : POOL_(peek_const)( POOL_(t) const * join ) {
470 30 : POOL_(shmem_t) const * pool = join->pool;
471 30 : POOL_ELE_T const * ele = join->ele;
472 30 : ulong ele_max = join->ele_max;
473 30 : FD_COMPILER_MFENCE();
474 30 : ulong ver_top = pool->ver_top;
475 30 : FD_COMPILER_MFENCE();
476 30 : ulong ele_idx = POOL_(private_vidx_idx)( ver_top );
477 30 : return (ele_idx<ele_max) ? ele + ele_idx : NULL;
478 30 : }
479 :
480 15 : static inline POOL_ELE_T * POOL_(peek)( POOL_(t) * join ) { return (POOL_ELE_T *)POOL_(peek_const)( join ); }
481 :
482 : static inline int
483 9 : POOL_(is_locked)( POOL_(t) const * join ) {
484 9 : POOL_(shmem_t) const * pool = join->pool;
485 9 : FD_COMPILER_MFENCE();
486 9 : ulong ver_top = pool->ver_top;
487 9 : FD_COMPILER_MFENCE();
488 9 : return (int)(POOL_(private_vidx_ver)( ver_top ) & 1UL);
489 9 : }
490 :
491 : static inline void
492 3 : POOL_(unlock)( POOL_(t) * join ) {
493 3 : POOL_(shmem_t) * pool = join->pool;
494 3 : FD_COMPILER_MFENCE();
495 3 : pool->ver_top += 1UL<<POOL_IDX_WIDTH;
496 3 : FD_COMPILER_MFENCE();
497 3 : }
498 :
499 : POOL_STATIC void * POOL_(new) ( void * shmem );
500 : POOL_STATIC POOL_(t) * POOL_(join) ( void * ljoin, void * shpool, void * shele, ulong ele_max );
501 : POOL_STATIC void * POOL_(leave) ( POOL_(t) * join );
502 : POOL_STATIC void * POOL_(delete)( void * shpool );
503 :
504 : POOL_STATIC POOL_ELE_T * POOL_(acquire)( POOL_(t) * join, POOL_ELE_T * sentinel, int blocking, int * _opt_err );
505 :
506 : POOL_STATIC int POOL_(release)( POOL_(t) * join, POOL_ELE_T * ele, int blocking );
507 :
508 : POOL_STATIC int POOL_(lock)( POOL_(t) * join, int blocking );
509 :
510 : POOL_STATIC void POOL_(reset)( POOL_(t) * join, ulong sentinel_cnt );
511 :
512 : POOL_STATIC FD_FN_PURE 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 12 : POOL_(new)( void * shmem ) {
526 12 : POOL_(shmem_t) * pool = (POOL_(shmem_t) *)shmem;
527 :
528 12 : if( FD_UNLIKELY( !pool ) ) {
529 3 : FD_LOG_WARNING(( "NULL shmem" ));
530 3 : return NULL;
531 3 : }
532 :
533 9 : 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 6 : pool->ver_top = POOL_(private_vidx)( 0UL, POOL_(idx_null)() );
539 :
540 6 : FD_COMPILER_MFENCE();
541 6 : pool->magic = POOL_MAGIC;
542 6 : FD_COMPILER_MFENCE();
543 :
544 6 : return (void *)pool;
545 9 : }
546 :
547 : POOL_STATIC POOL_(t) *
548 : POOL_(join)( void * ljoin,
549 : void * shpool,
550 : void * shele,
551 30 : ulong ele_max ) {
552 30 : POOL_(t) * join = (POOL_(t) *)ljoin;
553 30 : POOL_(shmem_t) * pool = (POOL_(shmem_t) *)shpool;
554 30 : POOL_ELE_T * ele = (POOL_ELE_T *)shele;
555 :
556 30 : if( FD_UNLIKELY( !join ) ) {
557 3 : FD_LOG_WARNING(( "NULL ljoin" ));
558 3 : return NULL;
559 3 : }
560 :
561 27 : if( FD_UNLIKELY( !fd_ulong_is_aligned( (ulong)join, alignof(POOL_(t)) ) ) ) {
562 3 : FD_LOG_WARNING(( "misaligned ljoin" ));
563 3 : return NULL;
564 3 : }
565 :
566 24 : if( FD_UNLIKELY( !pool ) ) {
567 3 : FD_LOG_WARNING(( "NULL shpool" ));
568 3 : return NULL;
569 3 : }
570 :
571 21 : if( FD_UNLIKELY( !fd_ulong_is_aligned( (ulong)pool, POOL_(align)() ) ) ) {
572 3 : FD_LOG_WARNING(( "misaligned shpool" ));
573 3 : return NULL;
574 3 : }
575 :
576 18 : if( FD_UNLIKELY( pool->magic!=POOL_MAGIC ) ) {
577 3 : FD_LOG_WARNING(( "bad magic" ));
578 3 : return NULL;
579 3 : }
580 :
581 15 : if( FD_UNLIKELY( (!ele) & (!!ele_max) ) ) {
582 3 : FD_LOG_WARNING(( "NULL shele" ));
583 3 : return NULL;
584 3 : }
585 :
586 12 : if( FD_UNLIKELY( !fd_ulong_is_aligned( (ulong)ele, alignof(POOL_ELE_T) ) ) ) {
587 3 : FD_LOG_WARNING(( "misaligned shele" ));
588 3 : return NULL;
589 3 : }
590 :
591 9 : if( FD_UNLIKELY( ele_max>POOL_(ele_max_max)() ) ) {
592 3 : FD_LOG_WARNING(( "bad ele_max" ));
593 3 : return NULL;
594 3 : }
595 :
596 6 : join->pool = pool;
597 6 : join->ele = ele;
598 6 : join->ele_max = ele_max;
599 :
600 6 : return join;
601 9 : }
602 :
603 : POOL_STATIC void *
604 9 : POOL_(leave)( POOL_(t) * join ) {
605 :
606 9 : if( FD_UNLIKELY( !join ) ) {
607 3 : FD_LOG_WARNING(( "NULL join" ));
608 3 : return NULL;
609 3 : }
610 :
611 6 : return (void *)join;
612 9 : }
613 :
614 : POOL_STATIC void *
615 15 : POOL_(delete)( void * shpool ) {
616 15 : POOL_(shmem_t) * pool = (POOL_(shmem_t) *)shpool;
617 :
618 15 : if( FD_UNLIKELY( !pool) ) {
619 3 : FD_LOG_WARNING(( "NULL shpool" ));
620 3 : return NULL;
621 3 : }
622 :
623 12 : if( FD_UNLIKELY( !fd_ulong_is_aligned( (ulong)pool, POOL_(align)() ) ) ) {
624 3 : FD_LOG_WARNING(( "misaligned shpool" ));
625 3 : return NULL;
626 3 : }
627 :
628 9 : if( FD_UNLIKELY( pool->magic!=POOL_MAGIC ) ) {
629 3 : FD_LOG_WARNING(( "bad magic" ));
630 3 : return NULL;
631 3 : }
632 :
633 6 : FD_COMPILER_MFENCE();
634 6 : pool->magic = 0UL;
635 6 : FD_COMPILER_MFENCE();
636 :
637 6 : return (void *)pool;
638 9 : }
639 :
640 : POOL_STATIC POOL_ELE_T *
641 : POOL_(acquire)( POOL_(t) * join,
642 : POOL_ELE_T * sentinel,
643 : int blocking,
644 3664155 : int * _opt_err ) {
645 3664155 : POOL_ELE_T * ele0 = join->ele;
646 3664155 : ulong ele_max = join->ele_max;
647 3664155 : ulong volatile * _v = (ulong volatile *)&join->pool->ver_top;
648 :
649 3664155 : POOL_ELE_T * ele = sentinel;
650 3664155 : int err = FD_POOL_SUCCESS;
651 :
652 3664155 : FD_COMPILER_MFENCE();
653 :
654 3664155 : for(;;) {
655 3664155 : ulong ver_top = *_v;
656 :
657 3664155 : ulong ver = POOL_(private_vidx_ver)( ver_top );
658 3664155 : ulong ele_idx = POOL_(private_vidx_idx)( ver_top );
659 :
660 3664155 : if( FD_LIKELY( !(ver & 1UL) ) ) { /* opt for unlocked */
661 :
662 3664155 : if( FD_UNLIKELY( POOL_(idx_is_null)( ele_idx ) ) ) { /* opt for not empty */
663 3669 : err = FD_POOL_ERR_EMPTY;
664 3669 : break;
665 3669 : }
666 :
667 3660486 : if( FD_UNLIKELY( ele_idx>=ele_max ) ) { /* opt for not corrupt */
668 0 : err = FD_POOL_ERR_CORRUPT;
669 0 : break;
670 0 : }
671 :
672 3660486 : ulong ele_nxt = POOL_(private_idx)( ele0[ ele_idx ].POOL_NEXT );
673 :
674 3660486 : if( FD_UNLIKELY( (ele_nxt>=ele_max) & (!POOL_(idx_is_null)( ele_nxt )) ) ) { /* opt for not corrupt */
675 0 : err = FD_POOL_ERR_CORRUPT;
676 0 : break;
677 0 : }
678 :
679 3660486 : ulong new_ver_top = POOL_(private_vidx)( ver+2UL, ele_nxt );
680 :
681 3660486 : if( FD_LIKELY( POOL_(private_cas)( _v, ver_top, new_ver_top )==ver_top ) ) { /* opt for low contention */
682 3660486 : ele = ele0 + ele_idx;
683 3660486 : break;
684 3660486 : }
685 :
686 3660486 : } else if( FD_UNLIKELY( !blocking ) ) { /* opt for blocking */
687 :
688 0 : err = FD_POOL_ERR_AGAIN;
689 0 : break; /* opt for blocking */
690 :
691 0 : }
692 :
693 0 : FD_SPIN_PAUSE();
694 0 : }
695 :
696 3664155 : FD_COMPILER_MFENCE();
697 :
698 3664155 : fd_int_store_if( !!_opt_err, _opt_err, err );
699 3664155 : return ele;
700 3664155 : }
701 :
702 : POOL_STATIC int
703 : POOL_(release)( POOL_(t) * join,
704 : POOL_ELE_T * ele,
705 3661263 : int blocking ) {
706 3661263 : ulong ele_max = join->ele_max;
707 3661263 : ulong volatile * _v = (ulong volatile *)&join->pool->ver_top;
708 :
709 3661263 : ulong ele_idx = (ulong)(ele - join->ele);
710 :
711 3661263 : if( FD_UNLIKELY( ele_idx>=ele_max ) ) return FD_POOL_ERR_INVAL; /* opt for valid call */
712 :
713 3660486 : int err = FD_POOL_SUCCESS;
714 :
715 3660486 : FD_COMPILER_MFENCE();
716 :
717 3660486 : for(;;) {
718 3660486 : ulong ver_top = *_v;
719 :
720 3660486 : ulong ver = POOL_(private_vidx_ver)( ver_top );
721 3660486 : ulong ele_nxt = POOL_(private_vidx_idx)( ver_top );
722 :
723 3660486 : if( FD_LIKELY( !(ver & 1UL) ) ) { /* opt for unlocked */
724 :
725 3660486 : if( FD_UNLIKELY( (ele_nxt>=ele_max) & (!POOL_(idx_is_null)( ele_nxt )) ) ) { /* opt for not corrupt */
726 0 : err = FD_POOL_ERR_CORRUPT;
727 0 : break;
728 0 : }
729 :
730 3660486 : ele->POOL_NEXT = POOL_(private_cidx)( ele_nxt );
731 :
732 3660486 : ulong new_ver_top = POOL_(private_vidx)( ver+2UL, ele_idx );
733 :
734 3660486 : if( FD_LIKELY( POOL_(private_cas)( _v, ver_top, new_ver_top )==ver_top ) ) break; /* opt for low contention */
735 :
736 3660486 : } else if( FD_UNLIKELY( !blocking ) ) { /* opt for blocking */
737 :
738 0 : err = FD_POOL_ERR_AGAIN;
739 0 : break;
740 :
741 0 : }
742 :
743 0 : FD_SPIN_PAUSE();
744 0 : }
745 :
746 3660486 : FD_COMPILER_MFENCE();
747 :
748 3660486 : return err;
749 3661263 : }
750 :
751 : POOL_STATIC int
752 : POOL_(lock)( POOL_(t) * join,
753 6 : int blocking ) {
754 6 : ulong volatile * _v = (ulong volatile *)&join->pool->ver_top;
755 :
756 6 : int err = FD_POOL_SUCCESS;
757 :
758 6 : FD_COMPILER_MFENCE();
759 :
760 6 : for(;;) {
761 :
762 : /* use a test-and-test-and-set style for reduced contention */
763 :
764 6 : ulong ver_top = *_v;
765 6 : if( FD_LIKELY( !(ver_top & (1UL<<POOL_IDX_WIDTH)) ) ) { /* opt for low contention */
766 3 : ver_top = POOL_(private_fetch_and_or)( _v, 1UL<<POOL_IDX_WIDTH );
767 3 : if( FD_LIKELY( !(ver_top & (1UL<<POOL_IDX_WIDTH)) ) ) break; /* opt for low contention */
768 3 : }
769 :
770 3 : if( FD_UNLIKELY( !blocking ) ) { /* opt for blocking */
771 3 : err = FD_POOL_ERR_AGAIN;
772 3 : break;
773 3 : }
774 :
775 0 : FD_SPIN_PAUSE();
776 0 : }
777 :
778 6 : FD_COMPILER_MFENCE();
779 :
780 6 : return err;
781 6 : }
782 :
783 : POOL_STATIC void
784 : POOL_(reset)( POOL_(t) * join,
785 15 : ulong sentinel_cnt ) {
786 15 : POOL_(shmem_t) * pool = join->pool;
787 15 : POOL_ELE_T * ele = join->ele;
788 15 : ulong ele_max = join->ele_max;
789 :
790 : /* Insert all but the leading sentinel_cnt elements in increasing
791 : order */
792 :
793 15 : ulong ele_top;
794 :
795 15 : if( FD_UNLIKELY( sentinel_cnt>=ele_max ) ) ele_top = POOL_(idx_null)(); /* All items are sentinels */
796 9 : else { /* Note: ele_max at least 1 here */
797 9 : ele_top = sentinel_cnt;
798 9213 : for( ulong ele_idx=ele_top; ele_idx<(ele_max-1UL); ele_idx++ )
799 9204 : ele[ ele_idx ].POOL_NEXT = POOL_(private_cidx)( ele_idx+1UL );
800 9 : ele[ ele_max-1UL ].POOL_NEXT = POOL_(private_cidx)( POOL_(idx_null)() );
801 9 : }
802 :
803 15 : ulong ver_top = pool->ver_top;
804 15 : ulong ver = POOL_(private_vidx_ver)( ver_top );
805 15 : pool->ver_top = POOL_(private_vidx)( ver, ele_top );
806 15 : }
807 :
808 : POOL_STATIC int
809 12 : POOL_(verify)( POOL_(t) const * join ) {
810 :
811 3177 : # define POOL_TEST(c) do { \
812 3177 : if( FD_UNLIKELY( !(c) ) ) { FD_LOG_WARNING(( "FAIL: %s", #c )); return FD_POOL_ERR_CORRUPT; } \
813 3177 : } while(0)
814 :
815 : /* Validate join */
816 :
817 12 : POOL_TEST( join );
818 12 : POOL_TEST( fd_ulong_is_aligned( (ulong)join, alignof(POOL_(t)) ) );
819 :
820 12 : POOL_(shmem_t) const * pool = join->pool;
821 12 : POOL_ELE_T const * ele = join->ele;
822 12 : ulong ele_max = join->ele_max;
823 :
824 12 : POOL_TEST( pool );
825 12 : POOL_TEST( fd_ulong_is_aligned( (ulong)pool, POOL_(align)() ) );
826 :
827 12 : POOL_TEST( (!!ele)| (!ele_max) );
828 12 : POOL_TEST( fd_ulong_is_aligned( (ulong)ele, alignof(POOL_ELE_T) ) );
829 :
830 12 : POOL_TEST( ele_max<=POOL_(ele_max_max)() );
831 :
832 : /* Validate pool metadata */
833 :
834 12 : ulong magic = pool->magic;
835 12 : ulong ver_top = pool->ver_top;
836 :
837 : /* version arbitrary as far as verify is concerned */
838 12 : ulong ele_idx = POOL_(private_vidx_idx)( ver_top );
839 :
840 12 : POOL_TEST( magic==POOL_MAGIC );
841 :
842 : /* Validate pool elements */
843 :
844 12 : ulong ele_rem = ele_max;
845 3081 : while( ele_idx<ele_max ) {
846 3069 : POOL_TEST( ele_rem ); ele_rem--; /* no cycles */
847 3069 : ele_idx = POOL_(private_idx)( ele[ ele_idx ].POOL_NEXT );
848 3069 : }
849 :
850 12 : POOL_TEST( POOL_(idx_is_null)( ele_idx ) );
851 :
852 12 : # undef POOL_TEST
853 :
854 12 : return FD_POOL_SUCCESS;
855 12 : }
856 :
857 : POOL_STATIC char const *
858 18 : POOL_(strerror)( int err ) {
859 18 : switch( err ) {
860 3 : case FD_POOL_SUCCESS: return "success";
861 3 : case FD_POOL_ERR_INVAL: return "bad input";
862 3 : case FD_POOL_ERR_AGAIN: return "try again";
863 3 : case FD_POOL_ERR_CORRUPT: return "corruption detected";
864 3 : case FD_POOL_ERR_EMPTY: return "pool empty";
865 3 : default: break;
866 18 : }
867 3 : return "unknown";
868 18 : }
869 :
870 : #endif
871 :
872 : #undef POOL_
873 : #undef POOL_STATIC
874 : #undef POOL_VER_WIDTH
875 :
876 : #undef POOL_IMPL_STYLE
877 : #undef POOL_MAGIC
878 : #undef POOL_IDX_WIDTH
879 : #undef POOL_ALIGN
880 : #undef POOL_NEXT
881 : #undef POOL_IDX_T
882 : #undef POOL_ELE_T
883 : #undef POOL_NAME
|
