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 an 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_ele_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 : #define "Define POOL_NAME"
124 : #endif
125 :
126 : /* A POOL_T should be something something reasonable to shallow copy
127 : with the fields described above. */
128 :
129 : #ifndef POOL_T
130 : #define "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 0 : #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 516495 : #define POOL_MAGIC (0xF17EDA2CE7900100UL) /* Firedancer pool ver 0 */
162 : #endif
163 :
164 : /* Implementation *****************************************************/
165 :
166 25077542814 : #define POOL_(n) FD_EXPAND_THEN_CONCAT3(POOL_NAME,_,n)
167 :
168 85745052 : #define POOL_IDX_NULL ((ulong)((POOL_IDX_T)~0UL))
169 :
170 : struct POOL_(private) {
171 :
172 : /* This point is POOL_ALIGN aligned */
173 : ulong magic; /* ==POOL_MAGIC */
174 : ulong max; /* Max elements in pool, in [POOL_SENTINEL,POOL_IDX_NULL] */
175 : ulong free; /* Num elements in pool available, in [0,max] */
176 : ulong free_top; /* Free stack top, POOL_IDX_NULL no elements currently in pool */
177 :
178 : /* Padding to POOL_ALIGN here */
179 :
180 : /* max POOL_T elements here, join points to element 0 */
181 : /* element 0 will be the sentinel if POOL_SENTINEL is true */
182 :
183 : /* Padding to POOL_ALIGN here */
184 : };
185 :
186 : typedef struct POOL_(private) POOL_(private_t);
187 :
188 : FD_PROTOTYPES_BEGIN
189 :
190 : /* Private APIs *******************************************************/
191 :
192 : /* pool_private_meta_footprint returns the number of bytes used by a
193 : pool metadata region */
194 :
195 : FD_FN_CONST static inline ulong
196 10778835471 : POOL_(private_meta_footprint)( void ) {
197 10778835471 : return fd_ulong_align_up( sizeof(POOL_(private_t)), fd_ulong_max( alignof(POOL_T), 128UL ) );
198 10778835471 : }
199 :
200 : /* pool_private_meta returns a pointer in the caller's address space to
201 : a pool metadata region. pool_private_meta_const is a const correct
202 : version. */
203 :
204 : FD_FN_CONST static inline POOL_(private_t) *
205 2285897910 : POOL_(private_meta)( POOL_T * join ) {
206 2285897910 : return (POOL_(private_t) *)(((ulong)join) - POOL_(private_meta_footprint)());
207 2285897910 : }
208 :
209 : FD_FN_CONST static inline POOL_(private_t) const *
210 8490218826 : POOL_(private_meta_const)( POOL_T const * join ) {
211 8490218826 : return (POOL_(private_t) const *)(((ulong)join) - POOL_(private_meta_footprint)());
212 8490218826 : }
213 :
214 : /* Public APIS ********************************************************/
215 :
216 : FD_FN_CONST static inline ulong
217 9 : POOL_(max_for_footprint)( ulong footprint ) {
218 9 : ulong meta_footprint = POOL_(private_meta_footprint)();
219 9 : if( FD_UNLIKELY( footprint <= meta_footprint ) ) return 0UL;
220 9 : return fd_ulong_min( (footprint - meta_footprint) / sizeof(POOL_T), POOL_IDX_NULL );
221 9 : }
222 :
223 : FD_FN_CONST static inline ulong
224 2518731 : POOL_(align)( void ) {
225 2518731 : return fd_ulong_max( alignof(POOL_T), 128UL );
226 2518731 : }
227 :
228 : FD_FN_CONST static inline ulong
229 1251294 : POOL_(footprint)( ulong max ) {
230 : # if POOL_SENTINEL
231 784308 : if( FD_UNLIKELY( !max ) ) return 0UL;
232 784302 : # endif
233 1251288 : ulong align = POOL_(align)();
234 1251288 : ulong meta_footprint = POOL_(private_meta_footprint)(); /* Multiple of align */
235 784302 : ulong data_footprint = fd_ulong_align_up( sizeof(POOL_T)*max, align );
236 1251288 : ulong thresh = fd_ulong_min( (ULONG_MAX - align - meta_footprint + 1UL) / sizeof(POOL_T), POOL_IDX_NULL );
237 784302 : return fd_ulong_if( max > thresh, 0UL, meta_footprint + data_footprint );
238 1251294 : }
239 :
240 : FD_FN_UNUSED static void * /* Work around -Winline */
241 : POOL_(new)( void * shmem,
242 516513 : ulong max ) {
243 :
244 516513 : if( FD_UNLIKELY( !shmem ) ) return NULL;
245 516510 : if( FD_UNLIKELY( !fd_ulong_is_aligned( (ulong)shmem, POOL_(align)() ) ) ) return NULL;
246 516507 : if( FD_UNLIKELY( !POOL_(footprint)( max ) ) ) return NULL;
247 :
248 516498 : POOL_T * join = (POOL_T *)(((ulong)shmem) + POOL_(private_meta_footprint)());
249 516498 : POOL_(private_t) * meta = POOL_(private_meta)( join );
250 :
251 516498 : meta->max = max;
252 516498 : meta->free = max;
253 :
254 516498 : if( FD_UNLIKELY( !max ) ) meta->free_top = POOL_IDX_NULL; /* Not reachable if POOL_SENTINEL set (footprint test above fails) */
255 516495 : else {
256 516495 : meta->free_top = 0UL;
257 272047938 : for( ulong idx=1UL; idx<max; idx++ ) join[ idx-1UL ].POOL_NEXT = (POOL_IDX_T)idx;
258 516495 : join[ max-1UL ].POOL_NEXT = (POOL_IDX_T)POOL_IDX_NULL;
259 :
260 : # if POOL_SENTINEL
261 : meta->free_top = 1UL;
262 : meta->free--;
263 337749 : join[ 0 ].POOL_NEXT = (POOL_IDX_T)POOL_IDX_NULL;
264 : # endif
265 516495 : }
266 :
267 516498 : FD_COMPILER_MFENCE();
268 516498 : FD_VOLATILE( meta->magic ) = (POOL_MAGIC);
269 516498 : FD_COMPILER_MFENCE();
270 :
271 516498 : return shmem;
272 516507 : }
273 :
274 : static inline POOL_T *
275 854784 : POOL_(join)( void * shpool ) {
276 854784 : if( FD_UNLIKELY( !shpool ) ) return NULL;
277 854781 : if( FD_UNLIKELY( !fd_ulong_is_aligned( (ulong)shpool, POOL_(align)() ) ) ) return NULL;
278 :
279 854778 : POOL_T * join = (POOL_T *)(((ulong)shpool) + POOL_(private_meta_footprint)());
280 854778 : POOL_(private_t) * meta = POOL_(private_meta)( join );
281 :
282 854778 : if( FD_UNLIKELY( FD_VOLATILE_CONST( meta->magic )!=(POOL_MAGIC) ) ) return NULL;
283 :
284 854775 : return join;
285 854778 : }
286 :
287 : FD_FN_CONST static inline void *
288 1124577 : POOL_(leave)( POOL_T * join ) {
289 1124577 : if( FD_UNLIKELY( !join ) ) return NULL;
290 48084 : return (void *)(((ulong)join) - POOL_(private_meta_footprint)());
291 1124577 : }
292 :
293 : static inline void *
294 1124574 : POOL_(delete)( void * shpool ) {
295 1124574 : if( FD_UNLIKELY( !shpool ) ) return NULL;
296 48081 : if( FD_UNLIKELY( !fd_ulong_is_aligned( (ulong)shpool, POOL_(align)() ) ) ) return NULL;
297 :
298 48078 : POOL_T * join = (POOL_T *)(((ulong)shpool) + POOL_(private_meta_footprint)());
299 48078 : POOL_(private_t) * meta = POOL_(private_meta)( join );
300 :
301 48078 : if( FD_UNLIKELY( FD_VOLATILE_CONST( meta->magic )!=(POOL_MAGIC) ) ) return NULL;
302 :
303 48075 : FD_COMPILER_MFENCE();
304 48075 : FD_VOLATILE( meta->magic ) = 0UL;
305 48075 : FD_COMPILER_MFENCE();
306 :
307 48075 : return shpool;
308 48078 : }
309 :
310 : /* Special values */
311 :
312 0 : FD_FN_CONST static inline ulong POOL_(idx_null) ( POOL_T const * join ) { (void)join; return POOL_IDX_NULL; }
313 0 : FD_FN_CONST static inline POOL_T * POOL_(ele_null) ( POOL_T * join ) { (void)join; return NULL; }
314 0 : FD_FN_CONST static inline POOL_T const * POOL_(ele_null_const) ( POOL_T const * join ) { (void)join; return NULL; }
315 :
316 : #if POOL_SENTINEL
317 0 : FD_FN_CONST static inline ulong POOL_(idx_sentinel) ( POOL_T const * join ) { (void)join; return 0UL; }
318 337749 : FD_FN_CONST static inline POOL_T * POOL_(ele_sentinel) ( POOL_T * join ) { return join; }
319 3 : FD_FN_CONST static inline POOL_T const * POOL_(ele_sentinel_const)( POOL_T const * join ) { return join; }
320 : #endif
321 :
322 : /* Address space conversion */
323 :
324 : FD_FN_PURE static inline int
325 : POOL_(idx_test)( POOL_T const * join,
326 77652519 : ulong idx ) {
327 77652519 : ulong max = POOL_(private_meta_const)( join )->max;
328 77652519 : return (idx<max) | (idx==POOL_IDX_NULL);
329 77652519 : }
330 :
331 : FD_FN_PURE static inline int
332 : POOL_(ele_test)( POOL_T const * join,
333 7121085684 : POOL_T const * ele ) {
334 7121085684 : ulong max = POOL_(private_meta_const)( join )->max;
335 7121085684 : ulong idx = (ulong)(ele - join);
336 7121085684 : FD_COMPILER_FORGET( idx ); /* prevent compiler from optimizing out alignment test */
337 7121085684 : return (!ele) | ((idx<max) & ((ulong)ele==((ulong)join+(idx*sizeof(POOL_T))))); /* last test checks alignment */
338 7121085684 : }
339 :
340 : FD_FN_CONST static inline ulong
341 : POOL_(idx)( POOL_T const * join,
342 77658543 : POOL_T const * ele ) {
343 77658543 : return ele ? (ulong)(ele-join) : POOL_IDX_NULL;
344 77658543 : }
345 :
346 : FD_FN_CONST static inline POOL_T *
347 : POOL_(ele)( POOL_T * join,
348 2986860 : ulong idx ) {
349 2986860 : return (idx==POOL_IDX_NULL) ? NULL : (join + idx);
350 2986860 : }
351 :
352 : FD_FN_CONST static inline POOL_T const *
353 : POOL_(ele_const)( POOL_T const * join,
354 2986851 : ulong idx ) {
355 2986851 : return (idx==POOL_IDX_NULL) ? NULL : (join + idx);
356 2986851 : }
357 :
358 : /* Accessors */
359 :
360 18 : FD_FN_PURE static inline ulong POOL_(max) ( POOL_T const * join ) { return POOL_(private_meta_const)( join )->max; }
361 672689784 : FD_FN_PURE static inline ulong POOL_(free)( POOL_T const * join ) { return POOL_(private_meta_const)( join )->free; }
362 :
363 : FD_FN_PURE static inline ulong
364 618790821 : POOL_(used)( POOL_T const * join ) {
365 618790821 : POOL_(private_t) const * meta = POOL_(private_meta_const)( join );
366 618790821 : return meta->max - meta->free;
367 618790821 : }
368 :
369 : /* Operations */
370 :
371 : static inline ulong
372 1143791343 : POOL_(idx_acquire)( POOL_T * join ) {
373 1143791343 : POOL_(private_t) * meta = POOL_(private_meta)( join );
374 1143791343 : ulong idx = meta->free_top;
375 1143791343 : meta->free_top = (ulong)join[ idx ].POOL_NEXT;
376 1143791343 : meta->free--;
377 1143791343 : return idx;
378 1143791343 : }
379 :
380 : static inline void
381 : POOL_(idx_release)( POOL_T * join,
382 1140687213 : ulong idx ) {
383 1140687213 : POOL_(private_t) * meta = POOL_(private_meta)( join );
384 1140687213 : join[ idx ].POOL_NEXT = (POOL_IDX_T)meta->free_top;
385 1140687213 : meta->free_top = idx;
386 1140687213 : meta->free++;
387 1140687213 : }
388 :
389 316414017 : static inline POOL_T * POOL_(ele_acquire)( POOL_T * join ) { return join + POOL_(idx_acquire)( join ); }
390 300236571 : static inline void POOL_(ele_release)( POOL_T * join, POOL_T * ele ) { POOL_(idx_release)( join, (ulong)(ele - join) ); }
391 :
392 : /* TODO: consider zeroing out pool mem on new? */
393 :
394 : /* TODO: consider providing element size and alignment as metadata? */
395 :
396 : /* TODO: consider lockfree concurrent version with ABA tagged free_top? */
397 :
398 : /* TODO: consider a verify and rebuild that work via most sig bit of
399 : POOL_NEXT for element marking (the POOL_NEXT field in the structure
400 : would have to become dedicated to the pool though). */
401 :
402 : FD_PROTOTYPES_END
403 :
404 : #undef POOL_IDX_NULL
405 : #undef POOL_
406 :
407 : #undef POOL_MAGIC
408 : #undef POOL_SENTINEL
409 : #undef POOL_IDX_T
410 : #undef POOL_NEXT
411 : #undef POOL_T
412 : #undef POOL_NAME
|
