Line data Source code
1 : /* Declare API for object pools of bounded run-time maximum size
2 : suitable for non-concurrent high performance persistent IPC usage.
3 : Typical usage:
4 :
5 : struct myele {
6 : ulong next; // Technically POOL_IDX_T POOL_NEXT, can go anywhere in struct,
7 : // can be repurposed while acquired
8 : // will be clobbered while in pool though
9 : ... user data ...
10 : ... structures with power-of-2 sizes have particularly good HPC
11 : ... Feng Shui
12 : }
13 :
14 : typedef struct myele myele_t;
15 :
16 : #define POOL_NAME mypool
17 : #define POOL_T myele_t
18 : #include "tmpl/fd_pool.c"
19 :
20 : This will declare the following static inline APIs as a header only
21 : style library in the compilation unit:
22 :
23 : // align/footprint - Return the alignment/footprint required for a
24 : // memory region to be used as mypool that can hold up to max
25 : // elements. footprint returns 0 if max is invalid (e.g. so large
26 : // that footprint would overflow ULONG_MAX or zero if mypool is
27 : // supposed to have a sentinel).
28 : //
29 : // new - Format a memory region pointed to by shmem into a mypool.
30 : // Assumes shmem points to a region with the required alignment and
31 : // footprint not in use by anything else. Caller is not joined on
32 : // return. Returns shmem on success or NULL on failure (e.g. shmem
33 : // or max are obviously bad).
34 : //
35 : // join - Join a mypool. Assumes shpool points at a memory region
36 : // formatted as a mypool. Returns a pointer in the caller's
37 : // address space to a memory region indexed [0,max) on success and
38 : // NULL on failure (e.g. shmem is obviously bad). THIS IS NOT JUST
39 : // A SIMPLE CAST OF SHPOOL.
40 : //
41 : // leave - Leave a mypool. Assumes join points to a current local
42 : // join. Returns a pointer to the shared memory region the join on
43 : // success and NULL on failure. THIS IS NOT JUST A SIMPLE CAST OF
44 : // JOIN.
45 : //
46 : // delete - Unformat a memory region used as mypool. Assumes
47 : // shpool points to a formatted region with no current / future
48 : // joins. Returns a pointer to the unformatted memory region.
49 :
50 : ulong mypool_align ( void );
51 : ulong mypool_footprint( ulong max );
52 : void * mypool_new ( void * shmem, ulong max );
53 : myele_t * mypool_join ( void * shpool );
54 : void * mypool_leave ( myele_t * join );
55 : void * mypool_delete ( void * shpool );
56 :
57 : // Special values
58 :
59 : // All these assume join is a current local join to a mypool. The
60 : // sentinel APIs are only created if POOL_SENTINEL is requested.
61 :
62 : ulong mypool_idx_null ( myele_t const * join ); // Index of the null element (not accessible)
63 : // infinite lifetime, ==(ulong)(POOL_IDX_T)~0UL
64 : myele_t * mypool_ele_null ( myele_t * join ); // Location of the null element in the caller's address
65 : // space, infinite lifetime, ==NULL
66 : myele_t const * mypool_ele_null_const ( myele_t const * join ); // Const correct version of above
67 :
68 : ulong mypool_idx_sentinel ( myele_t const * join ); // Index of the sentinel element (==0)
69 : // lifetime is the pool lifetime
70 : myele_t * mypool_ele_sentinel ( myele_t * join ); // Location of the sentinel element in the caller's address
71 : // space, lifetime is the join lifetime (==join)
72 : myele_t const * mypool_ele_sentinel_const( myele_t const * join ); // Const correct version of above
73 :
74 : // Address space conversions
75 :
76 : int mypool_idx_test ( myele_t const * join, ulong idx ); // Returns 1 if idx is in [0,max) or is
77 : // mypool_idx_null. Returns zero otherwise.
78 : int mypool_ele_test ( myele_t const * join, myele_t const * ele ); // Returns 1 if ele points to a pool ele or is
79 : // NULL. Returns zero otherwise.
80 :
81 : ulong mypool_idx ( myele_t const * join, myele_t const * ele ); // Returns idx associated with ele
82 : // Assumes mypool_ele_test is 1
83 : myele_t * mypool_ele ( myele_t * join, ulong idx ); // Returns ele associated with idx
84 : // Assumes mypool_idx_test is 1
85 : // Lifetime is the local join
86 : myele_t const * mypool_ele_const( myele_t const * join, ulong idx ); // Const correct version of above
87 :
88 : // Accessors
89 :
90 : ulong mypool_max ( myele_t const * join ); // Max elements in pool in [0,IDX_NULL], [1,IDX_NULL] if POOL_SENTINEL requested
91 : ulong mypool_free( myele_t const * join ); // Number of elements free, in [0,max]
92 : ulong mypool_used( myele_t const * join ); // Number of elements currently in use / acquired, in [0,max], includes sentinel
93 : // if applicable, pool_free + pool_used == pool_max
94 :
95 : // Operations
96 :
97 : ulong mypool_idx_acquire( myele_t * join ); // Acquire an element from pool, assumes at least 1 free
98 : // Returns index of element, in [0,max) and, if applicable, not
99 : // sentinel index. Lifetime is lesser of pool lifetime and
100 : // acquired element is released. Will not return a currently
101 : // acquired element.
102 : void mypool_idx_release( myele_t * join, ulong idx ); // Release an element to pool by element idx, assumes element
103 : // currently acquired (e.g. not null index and, if applicable,
104 : // not sentinel index). Element not acquired on return.
105 :
106 : myele_t * mypool_ele_acquire( myele_t * join ); // Acquire an element from pool, assumes at least 1 free
107 : // Returns a pointer to element in caller's address space, not
108 : // NULL and, if applicable, not sentinel. Lifetime is lesser
109 : // of join lifetime and acquired element is released. Will not
110 : // return a currently acquired element
111 : void mypool_ele_release( myele_t * join, myele_t * ele ); // Release an element to pool by local pointer, assumes element
112 : // currently acquired (e.g. not NULL and, if applicable, not
113 : // sentinel). Element not acquired on return.
114 :
115 : You can do this as often as you like in a compilation unit to get
116 : different types of pools. Since it is all static inline, it is
117 : fine to do this in a header too. Additional options to fine tune
118 : this are detailed below. */
119 :
120 : #include "../bits/fd_bits.h"
121 :
122 : #ifndef POOL_NAME
123 : #error "Define POOL_NAME"
124 : #endif
125 :
126 : /* A POOL_T should be something reasonable to shallow copy
127 : with the fields described above. */
128 :
129 : #ifndef POOL_T
130 : #error "Define POOL_T"
131 : #endif
132 :
133 : /* POOL_NEXT is the name of the field the pool will clobber for
134 : elements currently not allocated. */
135 :
136 : #ifndef POOL_NEXT
137 29195691 : #define POOL_NEXT next
138 : #endif
139 :
140 : /* POOL_IDX_T is the type of the POOL_NEXT field. Should be an unsigned
141 : integer type. The maximum value this type can have is also the
142 : maximum number of elements that can be in a pool. */
143 :
144 : #ifndef POOL_IDX_T
145 : #define POOL_IDX_T ulong
146 : #endif
147 :
148 : /* If POOL_SENTINEL is non-zero, the pool will reserve element idx
149 : 0 as a sentinel element (will be considered as always allocated).
150 : Setting this also implies that the max for a pool should be at least
151 : 1. */
152 :
153 : #ifndef POOL_SENTINEL
154 : #define POOL_SENTINEL 0
155 : #endif
156 :
157 : /* POOL_MAGIC is the magic number that should be used to identify
158 : pools of this type in shared memory. Should be non-zero. */
159 :
160 : #ifndef POOL_MAGIC
161 7629 : #define POOL_MAGIC (0xF17EDA2CE7900100UL) /* Firedancer pool ver 0 */
162 : #endif
163 :
164 : #if FD_TMPL_USE_HANDHOLDING
165 : #include "../log/fd_log.h"
166 : #endif
167 :
168 : /* Implementation *****************************************************/
169 :
170 25855427233 : #define POOL_(n) FD_EXPAND_THEN_CONCAT3(POOL_NAME,_,n)
171 :
172 83692719 : #define POOL_IDX_NULL ((ulong)((POOL_IDX_T)~0UL))
173 :
174 : struct POOL_(private) {
175 :
176 : /* This point is POOL_ALIGN aligned */
177 : ulong magic; /* ==POOL_MAGIC */
178 : ulong max; /* Max elements in pool, in [POOL_SENTINEL,POOL_IDX_NULL] */
179 : ulong free; /* Num elements in pool available, in [0,max] */
180 : ulong free_top; /* Free stack top, POOL_IDX_NULL no elements currently in pool */
181 :
182 : /* Padding to POOL_ALIGN here */
183 :
184 : /* max POOL_T elements here, join points to element 0 */
185 : /* element 0 will be the sentinel if POOL_SENTINEL is true */
186 :
187 : /* Padding to POOL_ALIGN here */
188 : };
189 :
190 : typedef struct POOL_(private) POOL_(private_t);
191 :
192 : FD_PROTOTYPES_BEGIN
193 :
194 : /* Private APIs *******************************************************/
195 :
196 : /* pool_private_meta_footprint returns the number of bytes used by a
197 : pool metadata region */
198 :
199 : FD_FN_CONST static inline ulong
200 10987856177 : POOL_(private_meta_footprint)( void ) {
201 10987856177 : return fd_ulong_align_up( sizeof(POOL_(private_t)), fd_ulong_max( alignof(POOL_T), 128UL ) );
202 10987856177 : }
203 :
204 : /* pool_private_meta returns a pointer in the caller's address space to
205 : a pool metadata region. pool_private_meta_const is a const correct
206 : version. */
207 :
208 : FD_FN_CONST static inline POOL_(private_t) *
209 2312913092 : POOL_(private_meta)( POOL_T * join ) {
210 2312913092 : return (POOL_(private_t) *)(((ulong)join) - POOL_(private_meta_footprint)());
211 2312913092 : }
212 :
213 : FD_FN_CONST static inline POOL_(private_t) const *
214 8674887159 : POOL_(private_meta_const)( POOL_T const * join ) {
215 8674887159 : return (POOL_(private_t) const *)(((ulong)join) - POOL_(private_meta_footprint)());
216 8674887159 : }
217 :
218 : /* Public APIS ********************************************************/
219 :
220 : FD_FN_CONST static inline ulong
221 9 : POOL_(max_for_footprint)( ulong footprint ) {
222 9 : ulong meta_footprint = POOL_(private_meta_footprint)();
223 9 : if( FD_UNLIKELY( footprint <= meta_footprint ) ) return 0UL;
224 9 : return fd_ulong_min( (footprint - meta_footprint) / sizeof(POOL_T), POOL_IDX_NULL );
225 9 : }
226 :
227 : FD_FN_CONST static inline ulong
228 77511 : POOL_(align)( void ) {
229 77511 : return fd_ulong_max( alignof(POOL_T), 128UL );
230 77511 : }
231 :
232 : FD_FN_CONST static inline ulong
233 31638 : POOL_(footprint)( ulong max ) {
234 : # if POOL_SENTINEL
235 45 : if( FD_UNLIKELY( !max ) ) return 0UL;
236 39 : # endif
237 31632 : ulong align = POOL_(align)();
238 31632 : ulong meta_footprint = POOL_(private_meta_footprint)(); /* Multiple of align */
239 39 : ulong data_footprint = fd_ulong_align_up( sizeof(POOL_T)*max, align );
240 31632 : ulong thresh = fd_ulong_min( (ULONG_MAX - align - meta_footprint + 1UL) / sizeof(POOL_T), POOL_IDX_NULL );
241 39 : return fd_ulong_if( max > thresh, 0UL, meta_footprint + data_footprint );
242 31638 : }
243 :
244 : FD_FN_UNUSED static void * /* Work around -Winline */
245 : POOL_(new)( void * shmem,
246 7647 : ulong max ) {
247 :
248 7647 : if( FD_UNLIKELY( !shmem ) ) return NULL;
249 7644 : if( FD_UNLIKELY( !fd_ulong_is_aligned( (ulong)shmem, POOL_(align)() ) ) ) return NULL;
250 7641 : if( FD_UNLIKELY( !POOL_(footprint)( max ) ) ) return NULL;
251 :
252 7632 : POOL_T * join = (POOL_T *)(((ulong)shmem) + POOL_(private_meta_footprint)());
253 7632 : POOL_(private_t) * meta = POOL_(private_meta)( join );
254 :
255 7632 : meta->max = max;
256 7632 : meta->free = max;
257 :
258 7632 : if( FD_UNLIKELY( !max ) ) meta->free_top = POOL_IDX_NULL; /* Not reachable if POOL_SENTINEL set (footprint test above fails) */
259 7626 : else {
260 7626 : meta->free_top = 0UL;
261 5016240 : for( ulong idx=1UL; idx<max; idx++ ) join[ idx-1UL ].POOL_NEXT = (POOL_IDX_T)idx;
262 7626 : join[ max-1UL ].POOL_NEXT = (POOL_IDX_T)POOL_IDX_NULL;
263 :
264 : # if POOL_SENTINEL
265 : meta->free_top = 1UL;
266 : meta->free--;
267 9 : join[ 0 ].POOL_NEXT = (POOL_IDX_T)POOL_IDX_NULL;
268 : # endif
269 7626 : }
270 :
271 7632 : FD_COMPILER_MFENCE();
272 7632 : FD_VOLATILE( meta->magic ) = (POOL_MAGIC);
273 7632 : FD_COMPILER_MFENCE();
274 :
275 7632 : return shmem;
276 7641 : }
277 :
278 : static inline POOL_T *
279 8727 : POOL_(join)( void * shpool ) {
280 8727 : if( FD_UNLIKELY( !shpool ) ) return NULL;
281 8724 : if( FD_UNLIKELY( !fd_ulong_is_aligned( (ulong)shpool, POOL_(align)() ) ) ) return NULL;
282 :
283 8721 : POOL_T * join = (POOL_T *)(((ulong)shpool) + POOL_(private_meta_footprint)());
284 8721 : POOL_(private_t) * meta = POOL_(private_meta)( join );
285 :
286 8721 : if( FD_UNLIKELY( FD_VOLATILE_CONST( meta->magic )!=(POOL_MAGIC) ) ) return NULL;
287 :
288 8718 : return join;
289 8721 : }
290 :
291 : FD_FN_CONST static inline void *
292 4407 : POOL_(leave)( POOL_T * join ) {
293 4407 : if( FD_UNLIKELY( !join ) ) return NULL;
294 4404 : return (void *)(((ulong)join) - POOL_(private_meta_footprint)());
295 4407 : }
296 :
297 : static inline void *
298 3534 : POOL_(delete)( void * shpool ) {
299 3534 : if( FD_UNLIKELY( !shpool ) ) return NULL;
300 3531 : if( FD_UNLIKELY( !fd_ulong_is_aligned( (ulong)shpool, POOL_(align)() ) ) ) return NULL;
301 :
302 3528 : POOL_T * join = (POOL_T *)(((ulong)shpool) + POOL_(private_meta_footprint)());
303 3528 : POOL_(private_t) * meta = POOL_(private_meta)( join );
304 :
305 3528 : if( FD_UNLIKELY( FD_VOLATILE_CONST( meta->magic )!=(POOL_MAGIC) ) ) return NULL;
306 :
307 3525 : FD_COMPILER_MFENCE();
308 3525 : FD_VOLATILE( meta->magic ) = 0UL;
309 3525 : FD_COMPILER_MFENCE();
310 :
311 3525 : return shpool;
312 3528 : }
313 :
314 : /* Special values */
315 :
316 13536 : FD_FN_CONST static inline ulong POOL_(idx_null) ( POOL_T const * join ) { (void)join; return POOL_IDX_NULL; }
317 3 : FD_FN_CONST static inline POOL_T * POOL_(ele_null) ( POOL_T * join ) { (void)join; return NULL; }
318 3 : FD_FN_CONST static inline POOL_T const * POOL_(ele_null_const) ( POOL_T const * join ) { (void)join; return NULL; }
319 :
320 : #if POOL_SENTINEL
321 3 : FD_FN_CONST static inline ulong POOL_(idx_sentinel) ( POOL_T const * join ) { (void)join; return 0UL; }
322 9 : FD_FN_CONST static inline POOL_T * POOL_(ele_sentinel) ( POOL_T * join ) { return join; }
323 3 : FD_FN_CONST static inline POOL_T const * POOL_(ele_sentinel_const)( POOL_T const * join ) { return join; }
324 : #endif
325 :
326 : /* Address space conversion */
327 :
328 : FD_FN_PURE static inline int
329 : POOL_(idx_test)( POOL_T const * join,
330 77652519 : ulong idx ) {
331 77652519 : ulong max = POOL_(private_meta_const)( join )->max;
332 77652519 : return (idx<max) | (idx==POOL_IDX_NULL);
333 77652519 : }
334 :
335 : FD_FN_PURE static inline int
336 : POOL_(ele_test)( POOL_T const * join,
337 6972176703 : POOL_T const * ele ) {
338 6972176703 : ulong max = POOL_(private_meta_const)( join )->max;
339 6972176703 : ulong idx = (ulong)(ele - join);
340 6972176703 : FD_COMPILER_FORGET( idx ); /* prevent compiler from optimizing out alignment test */
341 6972176703 : return (!ele) | ((idx<max) & ((ulong)ele==((ulong)join+(idx*sizeof(POOL_T))))); /* last test checks alignment */
342 6972176703 : }
343 :
344 : FD_FN_CONST static inline ulong
345 : POOL_(idx)( POOL_T const * join,
346 152330382 : POOL_T const * ele ) {
347 : # if FD_TMPL_USE_HANDHOLDING
348 : if( FD_UNLIKELY( !POOL_(ele_test)( join, ele ) ) ) FD_LOG_CRIT(( "no such element" ));
349 : # endif
350 152330382 : return ele ? (ulong)(ele-join) : POOL_IDX_NULL;
351 152330382 : }
352 :
353 : FD_FN_CONST static inline POOL_T *
354 : POOL_(ele)( POOL_T * join,
355 2987238 : ulong idx ) {
356 : # if FD_TMPL_USE_HANDHOLDING
357 : if( FD_UNLIKELY( !POOL_(idx_test)( join, idx ) ) ) FD_LOG_CRIT(( "no such index" ));
358 : # endif
359 2987238 : return (idx==POOL_IDX_NULL) ? NULL : (join + idx);
360 2987238 : }
361 :
362 : FD_FN_CONST static inline POOL_T const *
363 : POOL_(ele_const)( POOL_T const * join,
364 2986866 : ulong idx ) {
365 : # if FD_TMPL_USE_HANDHOLDING
366 : if( FD_UNLIKELY( !POOL_(idx_test)( join, idx ) ) ) FD_LOG_CRIT(( "no such index" ));
367 : # endif
368 2986866 : return (idx==POOL_IDX_NULL) ? NULL : (join + idx);
369 2986866 : }
370 :
371 : /* Accessors */
372 :
373 3958176 : FD_FN_PURE static inline ulong POOL_(max) ( POOL_T const * join ) { return POOL_(private_meta_const)( join )->max; }
374 702308890 : FD_FN_PURE static inline ulong POOL_(free)( POOL_T const * join ) { return POOL_(private_meta_const)( join )->free; }
375 :
376 : FD_FN_PURE static inline ulong
377 918790871 : POOL_(used)( POOL_T const * join ) {
378 918790871 : POOL_(private_t) const * meta = POOL_(private_meta_const)( join );
379 918790871 : return meta->max - meta->free;
380 918790871 : }
381 :
382 : /* Operations */
383 :
384 : static inline ulong
385 1156455196 : POOL_(idx_acquire)( POOL_T * join ) {
386 1156455196 : POOL_(private_t) * meta = POOL_(private_meta)( join );
387 : # if FD_TMPL_USE_HANDHOLDING
388 : if( FD_UNLIKELY( !meta->free ) ) FD_LOG_CRIT(( "pool is full" ));
389 : # endif
390 1156455196 : ulong idx = meta->free_top;
391 1156455196 : meta->free_top = (ulong)join[ idx ].POOL_NEXT;
392 1156455196 : meta->free--;
393 1156455196 : return idx;
394 1156455196 : }
395 :
396 : static inline void
397 : POOL_(idx_release)( POOL_T * join,
398 1156438015 : ulong idx ) {
399 1156438015 : POOL_(private_t) * meta = POOL_(private_meta)( join );
400 : # if FD_TMPL_USE_HANDHOLDING
401 : if( FD_UNLIKELY( (meta->max<=idx) | (idx==POOL_IDX_NULL) ) ) FD_LOG_CRIT(( "invalid index" ));
402 : # if POOL_SENTINEL
403 : if( FD_UNLIKELY( POOL_(idx_sentinel)( join )==idx ) ) FD_LOG_CRIT(( "cannot releaes sentinel" ));
404 : if( FD_UNLIKELY( meta->free>=meta->max-1 ) ) FD_LOG_CRIT(( "pool is empty" ));
405 : # else
406 : if( FD_UNLIKELY( meta->free>=meta->max ) ) FD_LOG_CRIT(( "pool is empty" ));
407 : # endif
408 : # endif
409 1156438015 : join[ idx ].POOL_NEXT = (POOL_IDX_T)meta->free_top;
410 1156438015 : meta->free_top = idx;
411 1156438015 : meta->free++;
412 1156438015 : }
413 :
414 330572611 : static inline POOL_T * POOL_(ele_acquire)( POOL_T * join ) { return join + POOL_(idx_acquire)( join ); }
415 317462599 : static inline void POOL_(ele_release)( POOL_T * join, POOL_T * ele ) { POOL_(idx_release)( join, (ulong)(ele - join) ); }
416 :
417 : /* TODO: consider zeroing out pool mem on new? */
418 :
419 : /* TODO: consider providing element size and alignment as metadata? */
420 :
421 : /* TODO: consider lockfree concurrent version with ABA tagged free_top? */
422 :
423 : /* TODO: consider a verify and rebuild that work via most sig bit of
424 : POOL_NEXT for element marking (the POOL_NEXT field in the structure
425 : would have to become dedicated to the pool though). */
426 :
427 : FD_PROTOTYPES_END
428 :
429 : #undef POOL_IDX_NULL
430 : #undef POOL_
431 :
432 : #undef POOL_MAGIC
433 : #undef POOL_SENTINEL
434 : #undef POOL_IDX_T
435 : #undef POOL_NEXT
436 : #undef POOL_T
437 : #undef POOL_NAME
|
