Line data Source code
1 : #include "fd_alloc.h"
2 : #include "fd_alloc_cfg.h"
3 : #include "../sanitize/fd_sanitize.h"
4 :
5 : /* Note: this will still compile on platforms without FD_HAS_ATOMIC. It
6 : should only be used single threaded in those use cases. (The code
7 : does imitate at a very low level the operations required by
8 : FD_HAS_ATOMIC but this is to minimize amount of code differences to
9 : test.) */
10 :
11 : /* If FD_ALLOC_STYLE is non-zero, this will clear any padding needed to
12 : align a user allocation. This is not strictly necessary and can slow
13 : down fd_alloc_malloc. But it does make diagnostics like
14 : fd_alloc_fprintf more accurate. */
15 :
16 : #ifndef FD_ALLOC_STYLE
17 : #define FD_ALLOC_STYLE 0
18 : #endif
19 :
20 : /* sizeclass APIs *****************************************************/
21 :
22 : /* fd_alloc_preferred_sizeclass returns the tightest fitting sizeclass
23 : for the given footprint. The caller promises there is at least one
24 : possible size class (i.e. that footprint is in
25 : [0,FD_ALLOC_FOOTPRINT_SMALL_THRESH]). The return will be in
26 : [0,FD_ALLOC_SIZECLASS_CNT). */
27 :
28 : static inline ulong
29 655887 : fd_alloc_preferred_sizeclass( ulong footprint ) {
30 655887 : ulong l = 0UL;
31 655887 : ulong h = FD_ALLOC_SIZECLASS_CNT-1UL;
32 :
33 : /* Fixed count loop without early exit to make it easy for compiler to
34 : unroll and nominally eliminate all branches for fast, highly
35 : deterministic performance with no consumption of BTB resources.
36 : FIXME: check the compiler is doing the right thing here with
37 : unrolling and branch elimination. */
38 :
39 4591209 : for( ulong r=0UL; r<FD_ALLOC_SIZECLASS_ITER_MAX; r++ ) {
40 :
41 : /* At this point sizeclasses in [0,l) are known to be inadequate and
42 : sizeclasses in [h,SIZECLASS_CNT) are known to be suitable.
43 : Sizeclasses in [l,h) have not been tested. */
44 :
45 3935322 : ulong m = (l+h)>>1; /* Note: no overflow for reasonable sizeclass_cnt and l<=m<=h */
46 3935322 : int c = (((ulong)fd_alloc_sizeclass_cfg[ m ].block_footprint)>=footprint);
47 3935322 : l = fd_ulong_if( c, l, m+1UL ); /* cmov */
48 3935322 : h = fd_ulong_if( c, m, h ); /* cmov */
49 :
50 3935322 : }
51 :
52 655887 : return h;
53 655887 : }
54 :
55 : /* fd_alloc_block_set *************************************************/
56 :
57 : /* A fd_alloc_block_set specifies a set of blocks in a superblock. */
58 :
59 : #define SET_NAME fd_alloc_block_set
60 : #define SET_TYPE ulong
61 : #define SET_MAX 64
62 : #include "../tmpl/fd_smallset.c"
63 :
64 : /* fd_alloc_block_set_all returns the set { 0,1,2, ... block_cnt-1 }.
65 : Assumes block_cnt is in [0,64]. */
66 :
67 : FD_FN_CONST static inline fd_alloc_block_set_t
68 623874 : fd_alloc_block_set_all( ulong block_cnt ) {
69 623874 : return (((ulong)(block_cnt<=63UL)) << (block_cnt & 63UL)) - 1UL; /* Handle wide shifts */
70 623874 : }
71 :
72 : /* fd_alloc_block_set_{add,sub}_then_fetch inserts / removes blocks to /
73 : from block set pointed to by set. The caller promises that blocks
74 : are not / are already in the block set. This operation is a compiler
75 : fence. Further, if FD_HAS_ATOMIC, this operation is done atomically.
76 : Returns the value of the block_set just after the operation. Note:
77 : atomic add/sub has slightly better asm on x86 than atomic or/and/nand
78 : (compiler quality issue, not an architecture issue) and generates the
79 : same results provided the caller promises are met. */
80 :
81 : #if FD_HAS_ATOMIC
82 :
83 : static inline fd_alloc_block_set_t
84 : fd_alloc_block_set_add_then_fetch( fd_alloc_block_set_t * _set,
85 652641 : fd_alloc_block_set_t blocks ) {
86 652641 : FD_COMPILER_MFENCE();
87 652641 : fd_alloc_block_set_t ret = FD_ATOMIC_ADD_AND_FETCH( _set, blocks );
88 652641 : FD_COMPILER_MFENCE();
89 652641 : return ret;
90 652641 : }
91 :
92 : static inline fd_alloc_block_set_t
93 : fd_alloc_block_set_sub_then_fetch( fd_alloc_block_set_t * _set,
94 658185 : fd_alloc_block_set_t blocks ) {
95 658185 : FD_COMPILER_MFENCE();
96 658185 : fd_alloc_block_set_t ret = FD_ATOMIC_SUB_AND_FETCH( _set, blocks );
97 658185 : FD_COMPILER_MFENCE();
98 658185 : return ret;
99 658185 : }
100 :
101 : #else
102 :
103 : static inline fd_alloc_block_set_t
104 : fd_alloc_block_set_add_then_fetch( fd_alloc_block_set_t * _set,
105 : fd_alloc_block_set_t blocks ) {
106 : FD_COMPILER_MFENCE();
107 : fd_alloc_block_set_t ret = (*_set) + blocks;
108 : *_set = ret;
109 : FD_COMPILER_MFENCE();
110 : return ret;
111 : }
112 :
113 : static inline fd_alloc_block_set_t
114 : fd_alloc_block_set_sub_then_fetch( fd_alloc_block_set_t * _set,
115 : fd_alloc_block_set_t blocks ) {
116 : FD_COMPILER_MFENCE();
117 : fd_alloc_block_set_t ret = (*_set) - blocks;
118 : *_set = ret;
119 : FD_COMPILER_MFENCE();
120 : return ret;
121 : }
122 :
123 : #endif
124 :
125 : /* fd_alloc_hdr_t *****************************************************/
126 :
127 : /* A fd_alloc_hdr_t is a small header prepended to an allocation that
128 : describes how to free the allocation. */
129 :
130 : typedef uint fd_alloc_hdr_t;
131 :
132 : /* FD_ALLOC_HDR_TYPE_* enumerate fd_alloc_hdr_t types */
133 :
134 650949 : #define FD_ALLOC_HDR_TYPE_USER_SMALL (0) /* This is a (small) user alloc contained in a superblock */
135 5403 : #define FD_ALLOC_HDR_TYPE_USER_LARGE (1) /* This is a (large) user alloc contained in a workspace partition */
136 7236 : #define FD_ALLOC_HDR_TYPE_NEST_SUPERBLOCK (2) /* This is a superblock contained in a (larger) superblock */
137 1755 : #define FD_ALLOC_HDR_TYPE_ROOT_SUPERBLOCK (3) /* This is a superblock contained in a workspace partition */
138 :
139 : /* fd_alloc_hdr packs a (type,idx,off) tuple into a fd_alloc_hdr_t.
140 : fd_alloc_hdr_{type,idx,off} unpack the corresponding field from a
141 : fd_alloc_hdr_t. */
142 :
143 : FD_FN_CONST static inline fd_alloc_hdr_t
144 : fd_alloc_hdr( int type, /* FD_ALLOC_HDR_TYPE_USER_SMALL or FD_ALLOC_HDR_TYPE_NEST_SUPERBLOCK */
145 : ulong idx, /* in [0,64), containing superblock block block_idx */
146 658185 : ulong off ) { /* in [0,2^26), aligned 4, byte offset of alloc/superblock in containing superblock */
147 658185 : return (fd_alloc_hdr_t)((off<<6) | (idx<<2) | (ulong)type);
148 658185 : }
149 :
150 0 : FD_FN_CONST static inline int fd_alloc_hdr_type( fd_alloc_hdr_t hdr ) { return (int) ( hdr & 3U); } /* FD_ALLOC_HDR_TYPE */
151 652641 : FD_FN_CONST static inline ulong fd_alloc_hdr_idx ( fd_alloc_hdr_t hdr ) { return (ulong)((hdr>>2) & 63U); } /* in [0,64) */
152 652641 : FD_FN_CONST static inline ulong fd_alloc_hdr_off ( fd_alloc_hdr_t hdr ) { return (ulong)((hdr>>8) << 2); } /* in [0,2^26), aligned 4 */
153 :
154 : /* FD_ALLOC_HDR_{USER_LARGE,ROOT_SUPERBLOCK} allocations do not need the
155 : fd_alloc_hdr_t idx and off fields. These fields are replaced by
156 : magic numbers to help with various allocation diagnostics. */
157 :
158 5403 : #define FD_ALLOC_HDR_USER_LARGE (0xfdac5e70U | (uint)FD_ALLOC_HDR_TYPE_USER_LARGE )
159 1755 : #define FD_ALLOC_HDR_ROOT_SUPERBLOCK (0xfda70010U | (uint)FD_ALLOC_HDR_TYPE_ROOT_SUPERBLOCK)
160 :
161 : /* fd_alloc_hdr_load loads the header for the allocation whose first
162 : byte is at laddr in the caller's address space. The header will be
163 : observed at some point of time between when this call was made and
164 : returned. This implies that the allocation at laddr must be valid at
165 : least until the caller stops using the hdr.
166 :
167 : fd_alloc_hdr_store stores a fd_alloc_hdr_t to the
168 : sizeof(fd_alloc_hdr_t) bytes immediately preceding the byte pointed
169 : to by laddr in the caller's address space. The caller promises that
170 : these bytes are somewhere within the containing block or wksp
171 : allocation.
172 :
173 : Note that superblocks are aligned FD_ALLOC_SUPERBLOCK_ALIGN.
174 : Further, to support superblock nesting, the blocks in a superblock
175 : are similarly aligned. As such, fd_alloc_hdr_t (which need an
176 : alignment less than this) are guaranteed to be loaded/stored at
177 : alignof(fd_alloc_hdr_t) aligned locations. */
178 :
179 : FD_FN_PURE static inline fd_alloc_hdr_t
180 650904 : fd_alloc_hdr_load( void const * laddr ) { /* Aligned at least alignof(fd_alloc_hdr_t) */
181 650904 : return *(fd_alloc_hdr_t const *)((ulong)laddr - sizeof(fd_alloc_hdr_t));
182 650904 : }
183 :
184 : static inline void *
185 : fd_alloc_hdr_store( void * laddr, /* Aligned at least alignof(fd_alloc_hdr_t) */
186 656352 : fd_alloc_hdr_t hdr ) {
187 656352 : *(fd_alloc_hdr_t *)((ulong)laddr - sizeof(fd_alloc_hdr_t)) = hdr;
188 656352 : return laddr;
189 656352 : }
190 :
191 : /* fd_alloc_superblock ************************************************/
192 :
193 : struct __attribute__((aligned(FD_ALLOC_SUPERBLOCK_ALIGN))) fd_alloc_superblock {
194 : fd_alloc_hdr_t hdr; /* ==FD_ALLOC_HDR_ROOT_SUPERBLOCK or (FD_ALLOC_HDR_TYPE_NEST_SUPERBLOCK,idx,off) */
195 : ushort sizeclass; /* superblock sizeclass, in [0,FD_ALLOC_SIZECLASS_CNT) */
196 : uchar block_cnt; /* ==fd_alloc_sizeclass_cfg[ sizeclass ].block_cnt */
197 : uchar cgroup_mask; /* ==fd_alloc_sizeclass_cfg[ sizeclass ].cgroup_mask */
198 : fd_alloc_block_set_t free_blocks; /* which blocks in this superblock are free */
199 : ulong next_gaddr; /* if on the inactive superblock stack, next inactive superblock or NULL, ignored o.w. */
200 :
201 : /* TODO: consider making a ulong bit-packed tuple for
202 : (sizeclass,block_cnt,cgroup_mask) and adding a cgroup_hint to it? */
203 :
204 : /* Storage for blocks follows */
205 : };
206 :
207 : typedef struct fd_alloc_superblock fd_alloc_superblock_t;
208 :
209 : /* fd_alloc ***********************************************************/
210 :
211 : /* fd_alloc_vgaddr_t provides APIs for versioned gaddrs used in an
212 : fd_alloc_t's sizeclass inactive stack. */
213 :
214 : #define VOFF_NAME fd_alloc_vgaddr
215 : #define VOFF_TYPE ulong
216 701034 : #define VOFF_VER_WIDTH 17
217 : #include "../tmpl/fd_voff.c"
218 :
219 : /* fd_alloc_private_active_slot returns a pointer to the location in the
220 : caller's address space where the gaddr of the active superblock for
221 : (sizeclass,cgroup) is stored. Assumes alloc is a non-NULL pointer in
222 : the caller's address space to the fd_alloc (not a join handle). */
223 :
224 : FD_FN_CONST static inline ulong *
225 : fd_alloc_private_active_slot( fd_alloc_t * alloc,
226 : ulong sizeclass,
227 835488 : ulong cgroup ) {
228 835488 : return alloc->active_slot + sizeclass + FD_ALLOC_SIZECLASS_MAX*cgroup;
229 835488 : }
230 :
231 : /* fd_alloc_private_active_slot_replace replaces the value currently in
232 : the slot pointed to by active_slot with new_superblock_gaddr and
233 : returns the superblock_gaddr previously in there. This is a compiler
234 : fence. If FD_HAS_ATOMIC, this will be done atomically. */
235 :
236 : static inline ulong
237 : fd_alloc_private_active_slot_replace( ulong * _active_slot,
238 1380033 : ulong new_superblock_gaddr ) {
239 1380033 : FD_COMPILER_MFENCE();
240 1380033 : # if FD_HAS_ATOMIC
241 1380033 : ulong old_superblock_gaddr = FD_ATOMIC_XCHG( _active_slot, new_superblock_gaddr );
242 : # else
243 : ulong old_superblock_gaddr = *_active_slot;
244 : *_active_slot = new_superblock_gaddr;
245 : # endif
246 1380033 : FD_COMPILER_MFENCE();
247 1380033 : return old_superblock_gaddr;
248 1380033 : }
249 :
250 : /* fd_alloc_private_inactive_stack_push pushes the superblock at the
251 : workspace global address superblock_gaddr in workspace wksp onto the
252 : stack _inactive_stack. This is a compiler fence. If FD_HAS_ATOMIC,
253 : this will be done atomically. */
254 :
255 : static inline void
256 : fd_alloc_private_inactive_stack_push( fd_alloc_vgaddr_t * _inactive_stack,
257 : fd_wksp_t * wksp,
258 40134 : ulong superblock_gaddr ) {
259 40134 : fd_alloc_superblock_t * superblock = (fd_alloc_superblock_t *)fd_wksp_laddr_fast( wksp, superblock_gaddr );
260 :
261 40134 : for(;;) {
262 :
263 : /* Read the top of the inactive stack. */
264 :
265 40134 : FD_COMPILER_MFENCE();
266 40134 : fd_alloc_vgaddr_t old = *_inactive_stack;
267 40134 : FD_COMPILER_MFENCE();
268 :
269 40134 : ulong top_ver = fd_alloc_vgaddr_ver( old );
270 40134 : ulong top_gaddr = fd_alloc_vgaddr_off( old ) << FD_ALLOC_SUPERBLOCK_LG_ALIGN;
271 :
272 : /* Try to push the top of the inactive stack */
273 :
274 40134 : fd_alloc_vgaddr_t new = fd_alloc_vgaddr( top_ver+1UL, superblock_gaddr >> FD_ALLOC_SUPERBLOCK_LG_ALIGN );
275 :
276 40134 : FD_COMPILER_MFENCE();
277 40134 : superblock->next_gaddr = top_gaddr;
278 40134 : FD_COMPILER_MFENCE();
279 :
280 40134 : # if FD_HAS_ATOMIC
281 40134 : if( FD_LIKELY( FD_ATOMIC_CAS( _inactive_stack, old, new )==old ) ) break;
282 : # else
283 : if( FD_LIKELY( (*_inactive_stack)==old ) ) { *_inactive_stack = new; break; }
284 : # endif
285 :
286 : /* Hmmm ... that failed ... try again */
287 :
288 0 : FD_SPIN_PAUSE();
289 0 : }
290 :
291 40134 : FD_COMPILER_MFENCE();
292 40134 : }
293 :
294 : /* fd_alloc_private_inactive_stack_pop pops the superblock off the top
295 : of the stack _inactive_stack. Returns the non-zero wksp superblock
296 : gaddr of the popped stack top on success or 0 on failure (i.e.
297 : _inactive_stack at some point in time between which this was called
298 : and this returned). This is a compiler fence. If FD_HAS_ATOMIC,
299 : this will be done atomically. */
300 :
301 : #if FD_HAS_DEEPASAN
302 : FD_FN_NO_ASAN static
303 : #else
304 : static inline
305 : #endif
306 : ulong
307 : fd_alloc_private_inactive_stack_pop( fd_alloc_vgaddr_t * _inactive_stack,
308 205593 : fd_wksp_t * wksp ) {
309 205593 : ulong top_gaddr;
310 :
311 205593 : for(;;) {
312 :
313 : /* Read the top of the inactive stack. Return if the inactive stack
314 : is empty. */
315 :
316 205593 : FD_COMPILER_MFENCE();
317 205593 : fd_alloc_vgaddr_t old = *_inactive_stack;
318 205593 : FD_COMPILER_MFENCE();
319 :
320 205593 : /**/ top_gaddr = fd_alloc_vgaddr_off( old ) << FD_ALLOC_SUPERBLOCK_LG_ALIGN;
321 205593 : ulong top_ver = fd_alloc_vgaddr_ver( old );
322 205593 : if( FD_UNLIKELY( !top_gaddr ) ) break;
323 :
324 : /* Try to pop the top of the inactive stack. */
325 :
326 40134 : fd_alloc_superblock_t * top = (fd_alloc_superblock_t *)fd_wksp_laddr_fast( wksp, top_gaddr );
327 :
328 : /* Note: under concurrent FD_HAS_DEEPASAN operation, another thread
329 : could pop and free the inactive superblock at the top and free it
330 : (thus poisoning top) after our top read above and before our
331 : next_gaddr read below. This could trigger a spurious asan
332 : failure (that, in normal operation, would have been failed and
333 : retried via the CAS below). Hence the noasan above. */
334 :
335 40134 : FD_COMPILER_MFENCE();
336 40134 : ulong next_gaddr = top->next_gaddr;
337 40134 : FD_COMPILER_MFENCE();
338 :
339 40134 : fd_alloc_vgaddr_t new = fd_alloc_vgaddr( top_ver+1UL, next_gaddr >> FD_ALLOC_SUPERBLOCK_LG_ALIGN );
340 :
341 40134 : # if FD_HAS_ATOMIC
342 40134 : if( FD_LIKELY( FD_ATOMIC_CAS( _inactive_stack, old, new )==old ) ) break;
343 : # else
344 : if( FD_LIKELY( (*_inactive_stack)==old ) ) { *_inactive_stack = new; break; }
345 : # endif
346 :
347 : /* Hmmm ... that failed ... try again */
348 :
349 0 : FD_SPIN_PAUSE();
350 0 : }
351 :
352 205593 : FD_COMPILER_MFENCE();
353 :
354 205593 : return top_gaddr;
355 205593 : }
356 :
357 : /* fd_alloc_private_alloc will allocate a sizeclass sized block from
358 : the given alloc with the concurrency hint cgroup_hint. On success,
359 : returns the superblock that contains the allocated block in the
360 : caller's address space and *_block_idx will hold the index of the
361 : allocated block. On failure, returns NULL and *_block_idx is
362 : unchanged. */
363 :
364 : static fd_alloc_superblock_t *
365 : fd_alloc_private_alloc( fd_alloc_t * alloc,
366 : fd_wksp_t * wksp,
367 : ulong sizeclass,
368 : ulong cgroup_hint,
369 : ulong * _block_idx );
370 :
371 : /* fd_alloc_private_free frees (superblock,block_idx). Assumes join is a
372 : current local join to an allocator, superblock points in the caller's
373 : address space to a valid superblock from this allocator, and
374 : block_idx a valid block index for this superblock that is currently
375 : allocated. */
376 :
377 : static void
378 : fd_alloc_private_free( fd_alloc_t * join,
379 : fd_alloc_superblock_t * superblock,
380 : ulong block_idx );
381 :
382 : /* Constructors *******************************************************/
383 :
384 : ulong
385 2586 : fd_alloc_align( void ) {
386 2586 : return alignof(fd_alloc_t);
387 2586 : }
388 :
389 : ulong
390 549 : fd_alloc_footprint( void ) {
391 549 : return sizeof(fd_alloc_t);
392 549 : }
393 :
394 : void *
395 : fd_alloc_new( void * shmem,
396 168 : ulong tag ) {
397 :
398 168 : if( FD_UNLIKELY( !shmem ) ) {
399 3 : FD_LOG_WARNING(( "NULL shmem" ));
400 3 : return NULL;
401 3 : }
402 :
403 165 : if( FD_UNLIKELY( !fd_ulong_is_aligned( (ulong)shmem, alignof(fd_alloc_t) ) ) ) {
404 3 : FD_LOG_WARNING(( "misaligned shmem" ));
405 3 : return NULL;
406 3 : }
407 :
408 162 : fd_wksp_t * wksp = fd_wksp_containing( shmem );
409 162 : if( FD_UNLIKELY( !wksp ) ) {
410 3 : FD_LOG_WARNING(( "shmem must be in a workspace" ));
411 3 : return NULL;
412 3 : }
413 :
414 159 : if( FD_UNLIKELY( fd_wksp_gaddr_hi( wksp ) > (1UL<<(fd_alloc_vgaddr_OFF_WIDTH + FD_ALLOC_SUPERBLOCK_LG_ALIGN)) ) ) {
415 0 : FD_LOG_WARNING(( "wksp too large for current fd_alloc implementation" ));
416 0 : return NULL;
417 0 : }
418 :
419 159 : if( FD_UNLIKELY( !tag ) ) {
420 3 : FD_LOG_WARNING(( "bad tag" ));
421 3 : return NULL;
422 3 : }
423 :
424 156 : fd_alloc_t * alloc = (fd_alloc_t *)shmem;
425 156 : memset( alloc, 0, sizeof(fd_alloc_t) );
426 :
427 156 : alloc->wksp_off = (ulong)alloc - (ulong)wksp;
428 156 : alloc->tag = tag;
429 :
430 156 : FD_COMPILER_MFENCE();
431 156 : alloc->magic = FD_ALLOC_MAGIC;
432 156 : FD_COMPILER_MFENCE();
433 :
434 156 : return shmem;
435 159 : }
436 :
437 : fd_alloc_t *
438 : fd_alloc_join( void * shalloc,
439 495 : ulong cgroup_hint ) {
440 495 : fd_alloc_t * alloc = shalloc;
441 :
442 495 : if( FD_UNLIKELY( !alloc ) ) {
443 3 : FD_LOG_WARNING(( "NULL shalloc" ));
444 3 : return NULL;
445 3 : }
446 :
447 492 : if( FD_UNLIKELY( !fd_ulong_is_aligned( (ulong)alloc, alignof(fd_alloc_t) ) ) ) {
448 3 : FD_LOG_WARNING(( "misaligned shalloc" ));
449 3 : return NULL;
450 3 : }
451 :
452 489 : if( FD_UNLIKELY( alloc->magic!=FD_ALLOC_MAGIC ) ) {
453 9 : FD_LOG_WARNING(( "bad magic" ));
454 9 : return NULL;
455 9 : }
456 :
457 480 : return fd_alloc_join_cgroup_hint_set( alloc, cgroup_hint );
458 489 : }
459 :
460 : void *
461 192 : fd_alloc_leave( fd_alloc_t * join ) {
462 :
463 192 : if( FD_UNLIKELY( !join ) ) {
464 3 : FD_LOG_WARNING(( "NULL join" ));
465 3 : return NULL;
466 3 : }
467 :
468 189 : return fd_alloc_private_join_alloc( join );
469 192 : }
470 :
471 : void *
472 : fd_alloc_private_delete( void * shalloc,
473 159 : int level ) {
474 :
475 159 : if( FD_UNLIKELY( !shalloc ) ) {
476 3 : FD_LOG_WARNING(( "NULL shalloc" ));
477 3 : return NULL;
478 3 : }
479 :
480 156 : if( FD_UNLIKELY( !fd_ulong_is_aligned( (ulong)shalloc, alignof(fd_alloc_t) ) ) ) {
481 3 : FD_LOG_WARNING(( "misaligned shalloc" ));
482 3 : return NULL;
483 3 : }
484 :
485 153 : fd_alloc_t * alloc = (fd_alloc_t *)shalloc;
486 :
487 153 : if( FD_UNLIKELY( alloc->magic!=FD_ALLOC_MAGIC ) ) {
488 3 : FD_LOG_WARNING(( "bad magic" ));
489 3 : return NULL;
490 3 : }
491 :
492 150 : FD_COMPILER_MFENCE();
493 150 : alloc->magic = 0UL;
494 150 : FD_COMPILER_MFENCE();
495 :
496 150 : fd_wksp_t * wksp = fd_alloc_private_wksp( alloc );
497 :
498 150 : if( level<=0 ) { /* no wksp cleanup */
499 :
500 : /* nothing to do */
501 :
502 150 : } else if( level<=1 ) { /* quick wksp cleanup */
503 :
504 : /* For each sizeclass, make all active superblocks inactive and then
505 : delete all inactive superblocks. This will not cleanup any
506 : superblocks that are fully allocated (and thus out of circulation
507 : for malloc) or any large allocations as a quick wksp cleanup
508 : assumes the application freed all outstanding allocations before
509 : calling this. */
510 :
511 9300 : for( ulong sizeclass=0UL; sizeclass<FD_ALLOC_SIZECLASS_CNT; sizeclass++ ) {
512 9150 : fd_alloc_vgaddr_t * _inactive_stack = alloc->inactive_stack + sizeclass;
513 :
514 9150 : ulong cgroup_cnt = (ulong)fd_alloc_sizeclass_cfg[ sizeclass ].cgroup_mask + 1UL;
515 36450 : for( ulong cgroup_idx=0UL; cgroup_idx<cgroup_cnt; cgroup_idx++ ) {
516 27300 : ulong superblock_gaddr =
517 27300 : fd_alloc_private_active_slot_replace( fd_alloc_private_active_slot( alloc, sizeclass, cgroup_idx ), 0UL );
518 27300 : if( FD_UNLIKELY( superblock_gaddr ) ) fd_alloc_private_inactive_stack_push( _inactive_stack, wksp, superblock_gaddr );
519 27300 : }
520 :
521 10302 : for(;;) {
522 10302 : ulong superblock_gaddr = fd_alloc_private_inactive_stack_pop( _inactive_stack, wksp );
523 10302 : if( FD_LIKELY( !superblock_gaddr ) ) break;
524 1152 : fd_alloc_superblock_t * superblock = (fd_alloc_superblock_t *)fd_wksp_laddr_fast( wksp, superblock_gaddr );
525 :
526 1152 : fd_alloc_hdr_t hdr = superblock->hdr;
527 1152 : if( FD_UNLIKELY( hdr==FD_ALLOC_HDR_ROOT_SUPERBLOCK ) ) fd_wksp_free( wksp, superblock_gaddr );
528 954 : else {
529 954 : fd_alloc_superblock_t * parent_superblock = (fd_alloc_superblock_t *)((ulong)superblock - fd_alloc_hdr_off( hdr ));
530 954 : ulong parent_block_idx = fd_alloc_hdr_idx( hdr );
531 954 : fd_alloc_private_free( alloc, parent_superblock, parent_block_idx );
532 954 : }
533 1152 : }
534 9150 : }
535 :
536 150 : } else { /* deep wksp cleanup (level>1) */
537 :
538 : /* A deep wksp cleanup will free all wksp allocations that match the
539 : alloc's tag. */
540 :
541 0 : fd_wksp_tag_free( wksp, &alloc->tag, 1UL );
542 :
543 0 : }
544 :
545 150 : return shalloc;
546 153 : }
547 :
548 159 : void * fd_alloc_delete( void * shalloc ) { return fd_alloc_private_delete( shalloc, 1 ); }
549 :
550 : static fd_alloc_superblock_t *
551 : fd_alloc_private_alloc( fd_alloc_t * alloc,
552 : fd_wksp_t * wksp,
553 : ulong sizeclass,
554 : ulong cgroup_hint,
555 672927 : ulong * _block_idx ) {
556 :
557 672927 : ulong cgroup_mask = (ulong)fd_alloc_sizeclass_cfg[ sizeclass ].cgroup_mask;
558 :
559 672927 : ulong cgroup = cgroup_hint & cgroup_mask;
560 :
561 : /* Try to get exclusive access to the preferred active superblock
562 : for (sizeclass,cgroup). Note that all active superblocks have at
563 : least one free block. We do a test-and-test-and-set style to avoid
564 : an atomic operation if there currently isn't an active superblock
565 : for (sizeclass,cgroup). */
566 :
567 672927 : ulong * active_slot = fd_alloc_private_active_slot( alloc, sizeclass, cgroup );
568 :
569 672927 : ulong superblock_gaddr = *active_slot;
570 :
571 672927 : if( FD_LIKELY( superblock_gaddr ) ) superblock_gaddr = fd_alloc_private_active_slot_replace( active_slot, 0UL );
572 :
573 : /* At this point, if superblock_gaddr is non-zero, we have exclusive
574 : access to the superblock and only we can allocate blocks from it.
575 : (Other threads could free blocks to it concurrently though.)
576 :
577 : If superblock_gaddr is zero, there was no preferred active
578 : superblock for (sizeclass,cgroup) when we looked. So, we try to
579 : pop the inactive superblock stack for this sizeclass. Note that
580 : all inactive superblocks also have at least one free block.
581 :
582 : If that fails, we try to allocate a new superblock to hold this
583 : allocation. If we are able to do so, obviously the new superblock
584 : will have at least one free block for this allocation. (Yes,
585 : malloc calls itself recursively. The base case is root superblock
586 : allocation from the underlying workspace.)
587 :
588 : If that fails, we are in trouble and fail (we are either out of
589 : memory or have too much wksp fragmentation). */
590 :
591 672927 : if( FD_UNLIKELY( !superblock_gaddr ) ) {
592 :
593 52356 : superblock_gaddr = fd_alloc_private_inactive_stack_pop( alloc->inactive_stack + sizeclass, wksp );
594 :
595 52356 : if( FD_UNLIKELY( !superblock_gaddr ) ) {
596 :
597 23733 : fd_alloc_superblock_t * superblock;
598 23733 : fd_alloc_hdr_t hdr;
599 :
600 23733 : ulong parent_sizeclass = (ulong)fd_alloc_sizeclass_cfg[ sizeclass ].parent_sizeclass;
601 :
602 23733 : if( FD_LIKELY( parent_sizeclass<FD_ALLOC_SIZECLASS_CNT ) ) {
603 :
604 17040 : ulong parent_idx;
605 17040 : fd_alloc_superblock_t * parent_superblock =
606 17040 : fd_alloc_private_alloc( alloc, wksp, parent_sizeclass, cgroup_hint, &parent_idx );
607 17040 : if( FD_UNLIKELY( !parent_superblock ) ) return NULL;
608 :
609 7236 : ulong parent_off = sizeof(fd_alloc_superblock_t)
610 7236 : + parent_idx*(ulong)fd_alloc_sizeclass_cfg[ parent_sizeclass ].block_footprint;
611 :
612 7236 : superblock = (fd_alloc_superblock_t *)((ulong)parent_superblock + parent_off);
613 7236 : hdr = fd_alloc_hdr( FD_ALLOC_HDR_TYPE_NEST_SUPERBLOCK, parent_idx, parent_off );
614 :
615 : # if FD_HAS_DEEPASAN
616 : /* At this point, the block containing the nested superblock is
617 : poisoned. Unpoison the header region. Note that blocks are
618 : aligned FD_ALLOC_SUPERBLOCK_ALIGN, FD_ALLOC_SUPERBLOCK_ALIGN
619 : is at least FD_ASAN_ALIGN and sizeof(fd_alloc_superblock_t)
620 : is a FD_ALLOC_SUPERBLOCK_ALIGN multiple. */
621 : fd_asan_unpoison( superblock, sizeof(fd_alloc_superblock_t) );
622 : # endif
623 :
624 7236 : superblock_gaddr = fd_wksp_gaddr_fast( wksp, superblock );
625 :
626 7236 : } else {
627 :
628 6693 : superblock_gaddr = fd_wksp_alloc( wksp, FD_ALLOC_SUPERBLOCK_ALIGN, FD_ALLOC_ROOT_SUPERBLOCK_FOOTPRINT, alloc->tag );
629 6693 : if( FD_UNLIKELY( !superblock_gaddr ) ) return NULL;
630 :
631 1755 : superblock = (fd_alloc_superblock_t *)fd_wksp_laddr_fast( wksp, superblock_gaddr );
632 1755 : hdr = FD_ALLOC_HDR_ROOT_SUPERBLOCK;
633 :
634 : # if FD_HAS_DEEPASAN
635 : /* At this point, the entire root superblock is unpoisoned.
636 : Poison the superblock block (keeping the header unpoisoned).
637 : See note above regarding alignments. */
638 : fd_asan_poison( superblock+1, FD_ALLOC_ROOT_SUPERBLOCK_FOOTPRINT - sizeof(fd_alloc_superblock_t) );
639 : # endif
640 :
641 1755 : }
642 :
643 8991 : ulong block_cnt = (ulong)fd_alloc_sizeclass_cfg[ sizeclass ].block_cnt;
644 :
645 8991 : superblock->hdr = hdr;
646 8991 : superblock->sizeclass = (ushort)sizeclass;
647 8991 : superblock->block_cnt = (uchar)block_cnt;
648 8991 : superblock->cgroup_mask = (uchar)cgroup_mask;
649 8991 : superblock->free_blocks = fd_alloc_block_set_all( block_cnt );
650 8991 : superblock->next_gaddr = 0UL;
651 :
652 8991 : }
653 52356 : }
654 :
655 : /* At this point, we have a superblock with space for at least one
656 : allocation and only we can allocate blocks from it. Other threads
657 : could free blocks in this superblock concurrently though. As such,
658 : we can non-atomically find a set bit in free_blocks (there will be
659 : at least one and no other thread will clear it behind our back) but
660 : we must atomically clear the bit we found so we don't mess up the
661 : other bits that might be concurrently set by free. */
662 :
663 658185 : fd_alloc_superblock_t * superblock = (fd_alloc_superblock_t *)fd_wksp_laddr_fast( wksp, superblock_gaddr );
664 :
665 658185 : fd_alloc_block_set_t * _free_blocks = &superblock->free_blocks;
666 :
667 658185 : FD_COMPILER_MFENCE();
668 658185 : fd_alloc_block_set_t free_blocks_before = *_free_blocks;
669 658185 : FD_COMPILER_MFENCE();
670 :
671 658185 : ulong block_idx = (ulong)fd_alloc_block_set_first( free_blocks_before );
672 :
673 658185 : fd_alloc_block_set_t free_blocks_after = fd_alloc_block_set_sub_then_fetch( _free_blocks, fd_alloc_block_set_ele( block_idx ) );
674 :
675 : /* At this point, we've allocated block block_idx from the superblock
676 : and free_blocks_after gives the set of free blocks in the
677 : superblock immediately after the allocation occurred. */
678 :
679 658185 : if( FD_LIKELY( free_blocks_after ) ) {
680 :
681 : /* At this point, we know the superblock has at least one
682 : allocated block in it (the one we just allocated) and one free
683 : block in it. And this will hold true until we put this
684 : superblock back into circulation. Specifically, nobody can free
685 : the block we just allocated until we return to tell them about it
686 : and nobody can allocate any remaining free blocks until we get
687 : this superblock back into circulation. To get this superblock
688 : back into circulation, we make it the active superblock for
689 : (sizeclass,cgroup). */
690 :
691 595935 : ulong displaced_superblock_gaddr = fd_alloc_private_active_slot_replace( active_slot, superblock_gaddr );
692 :
693 : /* And if this displaced a previously active superblock (e.g.
694 : another thread made a different superblock the active one while
695 : we were doing the above), we add the displaced superblock to the
696 : sizeclass's inactive superblocks. Note that any such displaced
697 : superblock also has at least one free block in it (the active
698 : superblock always has at least one free block) that nobody can
699 : allocate from as, at this point, it is not in circulation. Thus,
700 : pushing it onto the superblock's inactive stack will preserve the
701 : invariant that all inactive superblocks have at least one free
702 : block. */
703 :
704 595935 : if( FD_UNLIKELY( displaced_superblock_gaddr ) )
705 0 : fd_alloc_private_inactive_stack_push( alloc->inactive_stack + sizeclass, wksp, displaced_superblock_gaddr );
706 :
707 595935 : } //else {
708 :
709 : /* The superblock had no more free blocks immediately after the
710 : allocation occurred. We should not make put this superblock into
711 : circulation as it would break the invariants that all superblocks
712 : in circulation have at least one free block.
713 :
714 : And, as this superblock had no free blocks, we don't need to
715 : track the superblock anyway as malloc can't use the superblock
716 : until some of the blocks in it have been freed. As such, this
717 : superblock will not be used in a malloc until after the next call
718 : to free on a block in this superblock returns this superblock to
719 : circulation. Note that this superblock will have at least one
720 : allocated block until after this function returns (the block we
721 : just allocated) and thus cannot ever be considered as a deletion
722 : candidate until after this function returns and this allocation
723 : is freed.
724 :
725 : As discussed in free below, we could update a superblock cgroup
726 : hint here (such that the when the superblock goes back into
727 : circulation, it will be put into circulation as the active
728 : superblock for this cgroup to encourage for additional mallocs
729 : from this thread for good spatial locality). This doesn't need
730 : to be atomic. Even though a concurrent free on another thread
731 : might get this into superblock into circulation before this
732 : executes (and thus also have other mallocs occurred that changed
733 : the active_hint), it doesn't matter. So long as the hint is a
734 : sane value at all points in time, free will work fine. */
735 :
736 : //}
737 :
738 658185 : *_block_idx = block_idx;
739 658185 : return superblock;
740 672927 : }
741 :
742 : static void
743 : fd_alloc_private_free( fd_alloc_t * join,
744 : fd_alloc_superblock_t * superblock,
745 652641 : ulong block_idx ) {
746 :
747 : /* These reads and the ASAN poisoning must be before the free because
748 : block could potentially be reused by other threads the moment it is
749 : marked as free. */
750 :
751 652641 : ulong sizeclass = (ulong)superblock->sizeclass;
752 652641 : ulong block_cnt = (ulong)superblock->block_cnt;
753 652641 : ulong cgroup_mask = (ulong)superblock->cgroup_mask;
754 :
755 : # if FD_HAS_DEEPASAN /* Poison the block we are about to free */
756 : ulong block_footprint = (ulong)fd_alloc_sizeclass_cfg[ sizeclass ].block_footprint;
757 : ulong block_laddr = (ulong)superblock + sizeof(fd_alloc_superblock_t) + block_idx*block_footprint;
758 : fd_asan_poison( (void *)block_laddr, block_footprint );
759 : # endif
760 :
761 652641 : fd_alloc_block_set_t * _free_blocks = &superblock->free_blocks;
762 :
763 652641 : fd_alloc_block_set_t block = fd_alloc_block_set_ele( block_idx );
764 :
765 652641 : fd_alloc_block_set_t free_blocks_after = fd_alloc_block_set_add_then_fetch( _free_blocks, block );
766 :
767 : /* At this point, superblock is no longer safe to read and
768 : free_blocks_after is the set of free blocks just after the free. */
769 :
770 652641 : if( FD_UNLIKELY( free_blocks_after==block ) ) {
771 :
772 : /* The superblock containing this block had no free blocks
773 : immediately before we freed the allocation. Thus, at this point,
774 : nobody can allocate any blocks from this superblock (the
775 : superblock is neither an active superblock nor on the inactive
776 : stack as per the note in malloc above) and we need to get the
777 : superblock back into circulation for reuse. It is okay if other
778 : threads concurrently free other blocks in this superblock while
779 : we are doing this (they know the superblock is either in
780 : circulation or is being put into circulation).
781 :
782 : Since there is at least one free block in the superblock and
783 : nobody can allocate from it until it is circulation, putting it
784 : into circulation preserves the invariant that all superblocks in
785 : circulation have at least one free block.
786 :
787 : We have a bunch of options for putting this superblock back into
788 : circulation:
789 :
790 : - By pushing it onto the inactive stack
791 : - By making it the active superblock of the caller's cgroup
792 : - By making it the active superblock of the cgroup that most did
793 : the most recent malloc from it.
794 : - By making it the active superblock based on explicitly provided
795 : hint.
796 : - ...
797 :
798 : The first option is simplest to implement and balanced between
799 : common use cases single threaded, malloc/free pairs have thread
800 : affinity, and pipelined use cases. (E.g. single threaded will
801 : take an extra time to hop from inactive and active and potential
802 : has slightly worse overallocation, similar story for paired.
803 : Cache affinity in these two cases might be slightly degraded from
804 : empty superblocks hopping between concurrency groups via the
805 : inactive stack, pipelined naturally gets the page back to the
806 : malloc-ing thread albeit with a brief hop through the inactive
807 : stack though).
808 :
809 : The second option is about as simple and optimizes the single
810 : threaded and paired use cases as this thread is also likely the
811 : same thread that malloc'd this. Pipelined is marginally worse as
812 : the superblock will have to take two hops before it gets reused
813 : again (from the free-ing thread active superblock to the inactive
814 : stack to the malloc-ing active superblock).
815 :
816 : The third and fourth options can simultaneously get all options
817 : optimized but they require extra plumbing (either under the hood
818 : as per the note in malloc above or from the caller to get the
819 : extra context).
820 :
821 : Currently we do the second option for simplicity and optimal
822 : behaviors in the single threaded and paired use cases. (The
823 : fourth option is possible via the user changing the join's
824 : cgroup_hint to match the thread of the original allocator.) */
825 :
826 62097 : fd_alloc_t * alloc = fd_alloc_private_join_alloc( join );
827 62097 : fd_wksp_t * wksp = fd_alloc_private_wksp( alloc );
828 :
829 62097 : ulong cgroup = fd_alloc_join_cgroup_hint( join ) & cgroup_mask;
830 :
831 62097 : ulong * _active_slot = fd_alloc_private_active_slot( alloc, sizeclass, cgroup );
832 :
833 62097 : ulong displaced_superblock_gaddr = fd_alloc_private_active_slot_replace( _active_slot, fd_wksp_gaddr_fast( wksp, superblock ) );
834 :
835 : /* If this displaced an already active superblock, we need to push
836 : the displaced superblock onto the inactive stack (note that the
837 : superblock cannot be the same as the currently active superblock
838 : because the superblock was not in circulation before). */
839 :
840 62097 : if( FD_UNLIKELY( displaced_superblock_gaddr ) )
841 37023 : fd_alloc_private_inactive_stack_push( alloc->inactive_stack + sizeclass, wksp, displaced_superblock_gaddr );
842 :
843 62097 : return;
844 :
845 62097 : }
846 :
847 590544 : ulong all_blocks = fd_alloc_block_set_all( block_cnt );
848 :
849 590544 : if( FD_LIKELY( free_blocks_after!=all_blocks ) ) return;
850 :
851 : /* None of the blocks were in use after the above free. We might
852 : consider freeing it to reclaim space for other sizeclasses or
853 : large allocations. But we don't mind having a few totally empty
854 : superblocks in circulation for a sizeclass as this prevents
855 : things like:
856 :
857 : addr = malloc(sz);
858 : free(addr);
859 : addr = malloc(sz);
860 : free(addr)
861 : ...
862 : addr = malloc(sz);
863 : free(addr)
864 :
865 : from repeatedly needing to invoke malloc recursively to recreate
866 : superblock hierarchies that were prematurely freed.
867 :
868 : Regardless, since this superblock is in circulation, we can't be
869 : sure it is safe to delete because something might be malloc-ing
870 : from it concurrently. Thus, we are going to keep this superblock
871 : in circulation as is.
872 :
873 : But, since we know we have at least 1 completely empty superblock
874 : in circulation now, to prevent the unbounded accumulation of
875 : completely empty superblocks, we will try to get an inactive
876 : superblock and, if that is empty, delete that.
877 :
878 : This is pretty tricky as it is possible other threads are
879 : concurrently trying to pop the inactive stack to do a malloc. If
880 : we actually unmapped the memory here, such a thread could seg
881 : fault if it stalls after it reads the top of the stack but before
882 : it queries the top for the next_gaddr (and we'd have to use
883 : another strategy). But that is not an issue here as the
884 : underlying wksp memory is still mapped post-deletion regardless.
885 :
886 : Likewise, though the post deletion top->next_gaddr read will get a
887 : stale value in this scenario, it will highly likely not be injected
888 : into the inactive_stack because the CAS will detect that
889 : inactive_stack top has changed and fail.
890 :
891 : And, lastly, we version the inactive_stack top such that, even if
892 : somehow we had a thread stall in pop after reading top->next_gaddr
893 : / other threads do other operations that ultimately keep top the
894 : same change the value of top->next_gaddr / stalled thread resumes,
895 : the version number on the stalled thread will be wrong cause the
896 : CAS to fail. (There is a theoretical risk of version number reuse
897 : but the version number is wide enough to make that risk zero on any
898 : practical timescale.) */
899 :
900 93462 : fd_alloc_t * alloc = fd_alloc_private_join_alloc( join );
901 :
902 93462 : fd_wksp_t * wksp = fd_alloc_private_wksp( alloc );
903 :
904 93462 : fd_alloc_vgaddr_t * _inactive_stack = alloc->inactive_stack + sizeclass;
905 :
906 93462 : ulong deletion_candidate_gaddr = fd_alloc_private_inactive_stack_pop( _inactive_stack, wksp );
907 93462 : if( FD_LIKELY( !deletion_candidate_gaddr ) ) return; /* no deletion candidate, unclear branch prob */
908 :
909 9564 : fd_alloc_superblock_t * deletion_candidate = (fd_alloc_superblock_t *)fd_wksp_laddr_fast( wksp, deletion_candidate_gaddr );
910 :
911 9564 : if( FD_LIKELY( deletion_candidate->free_blocks!=all_blocks ) ) { /* deletion candidate not empty -> return to circulation */
912 1920 : fd_alloc_private_inactive_stack_push( _inactive_stack, wksp, deletion_candidate_gaddr );
913 1920 : return;
914 1920 : }
915 :
916 7644 : fd_alloc_hdr_t hdr = deletion_candidate->hdr;
917 7644 : if( FD_LIKELY( hdr!=FD_ALLOC_HDR_ROOT_SUPERBLOCK ) ) { /* empty deletion candidate in a parent superblock, free from parent */
918 6111 : fd_alloc_private_free( join, (fd_alloc_superblock_t *)((ulong)deletion_candidate - fd_alloc_hdr_off( hdr )),
919 6111 : fd_alloc_hdr_idx( hdr ) );
920 6111 : return;
921 6111 : }
922 :
923 : # if FD_HAS_DEEPASAN
924 : /* At this point, just the header of the root superblock to delete
925 : is unpoisoned. Since fd_wksp_free will poison the entire root
926 : superblock anyway, we don't need to do anything here. */
927 : # endif
928 :
929 1533 : fd_wksp_free( wksp, deletion_candidate_gaddr ); /* empty deletion candidate wksp allocated, free from wksp */
930 1533 : }
931 :
932 : void *
933 : fd_alloc_malloc_at_least( fd_alloc_t * join,
934 : ulong align,
935 : ulong sz,
936 661326 : ulong * _max ) {
937 :
938 : /* Handle default align, NULL alloc, 0 size, non-power-of-two align,
939 : unreasonably large sz and NULL _max. footprint has room for a
940 : fd_alloc_hdr_t, sz bytes and enough padding to allow for the
941 : alignment of superblock blocks / wksp allocations is at least
942 : alignof(fd_alloc_hdr_t). */
943 :
944 661326 : if( FD_UNLIKELY( !_max ) ) return NULL;
945 :
946 661326 : fd_alloc_t * alloc = fd_alloc_private_join_alloc( join );
947 :
948 661326 : align = fd_ulong_if( !align, FD_ALLOC_MALLOC_ALIGN_DEFAULT, align );
949 :
950 661326 : ulong footprint = sz + fd_ulong_max( align, sizeof(fd_alloc_hdr_t) );
951 :
952 661326 : if( FD_UNLIKELY( (!alloc) | (!fd_ulong_is_pow2( align )) | (!sz) | (footprint<=sz) ) ) {
953 36 : *_max = 0UL;
954 36 : return NULL;
955 36 : }
956 :
957 661290 : fd_wksp_t * wksp = fd_alloc_private_wksp( alloc );
958 :
959 : /* At this point, alloc is non-NULL and backed by wksp, align is a
960 : power-of-2, footprint is a reasonable non-zero value. If this is a
961 : large user allocation, allocate it directly from the underlying
962 : workspace. */
963 :
964 661290 : if( FD_UNLIKELY( footprint > FD_ALLOC_FOOTPRINT_SMALL_THRESH ) ) {
965 5403 : ulong part_gaddr_lo;
966 5403 : ulong part_gaddr_hi;
967 5403 : if( FD_UNLIKELY( !fd_wksp_alloc_at_least( wksp, alignof(fd_alloc_hdr_t), footprint, alloc->tag,
968 5403 : &part_gaddr_lo, &part_gaddr_hi ) ) ) {
969 0 : *_max = 0UL;
970 0 : return NULL;
971 0 : }
972 :
973 : /* Carve the requested allocation out of the newly allocated
974 : partition, prepending the allocation header for use by free. If
975 : we are running under the address sanitizer, note that
976 : fd_wksp_alloc_at_least already unpoisoned this partition. If we
977 : are running under the memory sanitizer, we mark the returned
978 : region as uninitialized. */
979 :
980 5403 : ulong part_laddr = (ulong)fd_wksp_laddr_fast( wksp, part_gaddr_lo );
981 5403 : ulong part_footprint = part_gaddr_hi - part_gaddr_lo;
982 :
983 5403 : ulong alloc_laddr = fd_ulong_align_up( part_laddr + sizeof(fd_alloc_hdr_t), align );
984 5403 : ulong asz = alloc_laddr - part_laddr;
985 :
986 : # if FD_ALLOC_STYLE==1 /* clear all align padding */
987 : if( asz > sizeof(fd_alloc_hdr_t) ) memset( (void *)part_laddr, 0, asz - sizeof(fd_alloc_hdr_t) );
988 : # else /* partially clear align padding to improve diagnostics */
989 5403 : *(uint *)part_laddr = 0U;
990 5403 : # endif
991 :
992 5403 : *_max = part_footprint - asz;
993 5403 : return fd_msan_poison( fd_alloc_hdr_store( (void *)alloc_laddr, FD_ALLOC_HDR_USER_LARGE ), *_max );
994 5403 : }
995 :
996 : /* At this point, this is a small user allocation. Determine the
997 : preferred sizeclass and cgroup_hint and then allocate a suitable
998 : block. */
999 :
1000 655887 : ulong sizeclass = fd_alloc_preferred_sizeclass( footprint );
1001 655887 : ulong cgroup_hint = fd_alloc_join_cgroup_hint( join );
1002 :
1003 655887 : ulong block_idx;
1004 655887 : fd_alloc_superblock_t * superblock = fd_alloc_private_alloc( alloc, wksp, sizeclass, cgroup_hint, &block_idx );
1005 655887 : if( FD_UNLIKELY( !superblock ) ) {
1006 4938 : *_max = 0UL;
1007 4938 : return NULL;
1008 4938 : }
1009 :
1010 : /* Carve the requested allocation out of the newly allocated block,
1011 : prepending the allocation header for use by free. If we are
1012 : running under the address sanitizer, we unpoison the block (see
1013 : note above about asan alignment). If we are running under the
1014 : memory sanitizer, we mark the returned region as uninitialized. */
1015 :
1016 650949 : ulong block_footprint = (ulong)fd_alloc_sizeclass_cfg[ sizeclass ].block_footprint;
1017 650949 : ulong block_laddr = (ulong)superblock + sizeof(fd_alloc_superblock_t) + block_idx*block_footprint;
1018 :
1019 : # if FD_HAS_DEEPASAN
1020 : fd_asan_unpoison( (void *)block_laddr, block_footprint );
1021 : # endif
1022 :
1023 650949 : ulong alloc_laddr = fd_ulong_align_up( block_laddr + sizeof(fd_alloc_hdr_t), align );
1024 650949 : ulong asz = alloc_laddr - block_laddr;
1025 :
1026 : # if FD_ALLOC_STYLE==1 /* clear all align padding */
1027 : if( asz > sizeof(fd_alloc_hdr_t) ) memset( (void *)block_laddr, 0, asz - sizeof(fd_alloc_hdr_t) );
1028 : # else /* partially clear align padding to improve diagnostics */
1029 650949 : *(fd_alloc_hdr_t *)block_laddr = 0U;
1030 650949 : # endif
1031 :
1032 650949 : fd_alloc_hdr_t hdr = fd_alloc_hdr( FD_ALLOC_HDR_TYPE_USER_SMALL, block_idx, alloc_laddr - (ulong)superblock );
1033 :
1034 650949 : *_max = block_footprint - asz;
1035 650949 : return fd_msan_poison( fd_alloc_hdr_store( (void *)alloc_laddr, hdr ), *_max );
1036 655887 : }
1037 :
1038 : void
1039 : fd_alloc_free( fd_alloc_t * join,
1040 650919 : void * laddr ) {
1041 :
1042 : /* Handle NULL alloc and/or NULL laddr */
1043 :
1044 650919 : fd_alloc_t * alloc = fd_alloc_private_join_alloc( join );
1045 650919 : if( FD_UNLIKELY( (!alloc) | (!laddr) ) ) return;
1046 :
1047 : /* At this point, we have a valid join and a pointer to the first byte
1048 : of an allocation done by it. Load the allocation header. If the
1049 : header indicates this is a large allocation, free it from the
1050 : underlying wksp (note that fd_wksp_free_laddr works for any byte
1051 : within the wksp allocation ... thus we don't have to apply a header
1052 : offset and thus can reuse the header idx and off for data integrity
1053 : checks). Otherwise (i.e. the header indicates this allocation is a
1054 : block in a superblock), free it from the containing superblock. */
1055 :
1056 650904 : fd_alloc_hdr_t hdr = fd_alloc_hdr_load( laddr );
1057 :
1058 650904 : if( FD_UNLIKELY( hdr==FD_ALLOC_HDR_USER_LARGE ) ) {
1059 5361 : fd_wksp_t * wksp = fd_alloc_private_wksp( alloc );
1060 :
1061 : # if FD_HAS_DEEPASAN
1062 : /* Note that fd_wksp_free will poison the partition on our behalf so
1063 : we don't have anything to do here. */
1064 : # endif
1065 :
1066 5361 : fd_wksp_free( wksp, fd_wksp_gaddr_fast( wksp, laddr ) );
1067 5361 : return;
1068 5361 : }
1069 :
1070 645543 : fd_alloc_private_free( join, (fd_alloc_superblock_t *)((ulong)laddr - fd_alloc_hdr_off( hdr )), fd_alloc_hdr_idx( hdr ) );
1071 645543 : }
1072 :
1073 : void
1074 399 : fd_alloc_compact( fd_alloc_t * join ) {
1075 :
1076 399 : fd_alloc_t * alloc = fd_alloc_private_join_alloc( join );
1077 399 : if( FD_UNLIKELY( !alloc ) ) {
1078 0 : FD_LOG_WARNING(( "bad join" ));
1079 0 : return;
1080 0 : }
1081 :
1082 399 : fd_wksp_t * wksp = fd_alloc_private_wksp( alloc );
1083 :
1084 : /* We scan each sizeclass (in monotonically increasing order) for
1085 : completely empty superblocks that thus can be freed. This has the
1086 : pleasant side effect that, as smaller empty superblocks get freed,
1087 : larger superblocks in which they are nested could become completely
1088 : empty. At the end of compaction, if no other operations are
1089 : running concurrently, any remaining superblocks should contain at
1090 : least one user small allocation somewhere in them. */
1091 :
1092 24738 : for( ulong sizeclass=0UL; sizeclass<FD_ALLOC_SIZECLASS_CNT; sizeclass++ ) {
1093 24339 : fd_alloc_block_set_t all_blocks = fd_alloc_block_set_all( (ulong)fd_alloc_sizeclass_cfg[ sizeclass ].block_cnt );
1094 24339 : ulong cgroup_cnt = (ulong)fd_alloc_sizeclass_cfg[ sizeclass ].cgroup_mask + 1UL;
1095 24339 : fd_alloc_vgaddr_t * _inactive_stack = alloc->inactive_stack + sizeclass;
1096 :
1097 : /* For each active superblock in this sizeclass */
1098 :
1099 96957 : for( ulong cgroup_idx=0UL; cgroup_idx<cgroup_cnt; cgroup_idx++ ) {
1100 72618 : ulong * _active_slot = fd_alloc_private_active_slot( alloc, sizeclass, cgroup_idx );
1101 :
1102 72618 : ulong superblock_gaddr = fd_alloc_private_active_slot_replace( _active_slot, 0UL );
1103 72618 : if( !superblock_gaddr ) continue; /* application dependent branch prob */
1104 1551 : fd_alloc_superblock_t * superblock = (fd_alloc_superblock_t *)fd_wksp_laddr_fast( wksp, superblock_gaddr );
1105 :
1106 : /* At this point, we have atomically acquired the cgroup_idx's
1107 : active superblock and it has at least one free block. If this
1108 : superblock is empty, we push it onto the inactive stack (for
1109 : freeing below). Otherwise, we put the superblock back into
1110 : circulation (we know from the above it still has at least one
1111 : free block, preserving the invariant). This might displace a
1112 : superblock that another thread made active behind our back. We
1113 : push any such superblock block onto the inactive stack (it also
1114 : will have at least one free block for the same reasons). */
1115 :
1116 1551 : if( superblock->free_blocks==all_blocks ) { /* application dependent branch prob */
1117 39 : fd_alloc_private_inactive_stack_push( _inactive_stack, wksp, superblock_gaddr );
1118 1512 : } else {
1119 1512 : ulong displaced_superblock_gaddr = fd_alloc_private_active_slot_replace( _active_slot, superblock_gaddr );
1120 1512 : if( FD_UNLIKELY( displaced_superblock_gaddr ) )
1121 0 : fd_alloc_private_inactive_stack_push( _inactive_stack, wksp, displaced_superblock_gaddr );
1122 1512 : }
1123 1551 : }
1124 :
1125 : /* Drain the inactive stack for this sizeclass. All empty
1126 : superblocks found are freed. All other superblocks will be
1127 : pushed onto a local stack (every one will have at least one free
1128 : block). After the inactive stack drain, we drain the local stack
1129 : back into the inactive stack to get all these remaining
1130 : superblocks back into circulation (also safe for the same
1131 : reasons) and with same relative ordering (nice but not required).
1132 : We technically don't need to use a lockfree push / pop for the
1133 : local stack but no sense in implementing a second version for
1134 : this mostly diagnostic / teardown oriented use case. */
1135 :
1136 24339 : fd_alloc_vgaddr_t _local_stack[1];
1137 :
1138 24339 : *_local_stack = fd_alloc_vgaddr( 0UL, 0UL );
1139 :
1140 24756 : for(;;) {
1141 24756 : ulong superblock_gaddr = fd_alloc_private_inactive_stack_pop( _inactive_stack, wksp );
1142 24756 : if( !superblock_gaddr ) break; /* application dependent branch prob */
1143 417 : fd_alloc_superblock_t * superblock = (fd_alloc_superblock_t *)fd_wksp_laddr_fast( wksp, superblock_gaddr );
1144 :
1145 417 : if( superblock->free_blocks==all_blocks ) { /* if superblock is empty, free it, application dependent branch prob */
1146 :
1147 39 : fd_alloc_hdr_t hdr = superblock->hdr;
1148 39 : if( FD_LIKELY( hdr!=FD_ALLOC_HDR_ROOT_SUPERBLOCK ) ) { /* empty superblock in a parent superblock, free from parent */
1149 33 : fd_alloc_private_free( join, (fd_alloc_superblock_t *)((ulong)superblock - fd_alloc_hdr_off( hdr )),
1150 33 : fd_alloc_hdr_idx( hdr ) );
1151 33 : } else {
1152 6 : fd_wksp_free( wksp, superblock_gaddr ); /* empty superblock wksp allocated, free from wksp */
1153 6 : }
1154 :
1155 378 : } else {
1156 :
1157 378 : fd_alloc_private_inactive_stack_push( _local_stack, wksp, superblock_gaddr );
1158 :
1159 378 : }
1160 417 : }
1161 :
1162 24717 : for(;;) {
1163 24717 : ulong superblock_gaddr = fd_alloc_private_inactive_stack_pop( _local_stack, wksp );
1164 24717 : if( !superblock_gaddr ) break; /* application dependent branch prob */
1165 378 : fd_alloc_private_inactive_stack_push( _inactive_stack, wksp, superblock_gaddr );
1166 378 : }
1167 24339 : }
1168 399 : }
1169 :
1170 : int
1171 204 : fd_alloc_is_empty( fd_alloc_t * join ) {
1172 204 : fd_alloc_t * alloc = fd_alloc_private_join_alloc( join );
1173 204 : if( FD_UNLIKELY( !alloc ) ) return 0;
1174 :
1175 : /* Compact out any preallocated memory from the wksp */
1176 :
1177 204 : fd_alloc_compact( join );
1178 :
1179 : /* At this point, if there are no user allocations, there should be no
1180 : wksp partitions tagged with the allocator's tag (except, maybe, the
1181 : partition that holds the fd_alloc state, if the creator used the
1182 : same tag there). So we compute the number of partitions used by
1183 : the alloc's tag and deduct if necessary the partition used to hold
1184 : the fd_alloc's metadata. */
1185 :
1186 204 : fd_wksp_t * wksp = fd_alloc_private_wksp( alloc );
1187 :
1188 204 : fd_wksp_usage_t usage[1];
1189 204 : fd_wksp_usage( wksp, &alloc->tag, 1UL, usage );
1190 :
1191 204 : usage->used_cnt -= (ulong)(fd_wksp_tag( wksp, fd_wksp_gaddr_fast( wksp, alloc ) )==alloc->tag);
1192 :
1193 204 : return !usage->used_cnt;
1194 204 : }
1195 :
1196 : /* fd_alloc_fprintf pretty prints comprehensive details about the state
1197 : of the allocator to stream. Returns the number of characters printed
1198 : to stream (saturated to INT_MAX).
1199 :
1200 : IMPORTANT SAFETY TIP! If FD_ALLOC_STYLE==0 or if called while
1201 : concurrent operations are in progress, this can spuriously report
1202 : errors (due to alignment padding containing stale fd_alloc_hdr_t or
1203 : from concurrent operations changing allocations while they are being
1204 : analyzed by the below).
1205 :
1206 : IMPORTANT SAFETY TIP! fd_alloc_fprintf can generate ASAN errors if
1207 : run concurrently under ASAN because concurrent operations might
1208 : poison regions of the wksp as they are being analyzed by the below.
1209 : Hence the below functions are marked as FD_FN_NO_ASAN. Similar
1210 : considerations for FD_FN_NO_MSAN. */
1211 :
1212 : #include <stdio.h>
1213 : #include "../wksp/fd_wksp_private.h"
1214 :
1215 : FD_FN_NO_ASAN FD_FN_NO_MSAN static fd_alloc_hdr_t
1216 0 : fd_alloc_hdr_load_no_san( void const * laddr ) {
1217 0 : return *(fd_alloc_hdr_t const *)((ulong)laddr - sizeof(fd_alloc_hdr_t));
1218 0 : }
1219 :
1220 : FD_FN_NO_ASAN FD_FN_NO_MSAN static ulong
1221 : fd_alloc_private_superblock_fprintf( FILE * stream, /* Stream to fprintf */
1222 : fd_wksp_t const * wksp,
1223 : ulong superblock_gaddr, /* Superblock to fprintf */
1224 : ulong parent_gaddr_lo, /* wksp region that contains this superblock */
1225 : ulong parent_gaddr_hi,
1226 : int recurse, /* Should this recurse into nested superblocks */
1227 : ulong indent_cnt, /* How much to indent */
1228 0 : ulong * ctr ) {
1229 :
1230 0 : ulong cnt = 0UL;
1231 :
1232 0 : # define EMIT( f ) do { \
1233 0 : for( ulong _rem=indent_cnt; _rem; _rem-- ) fputc( ' ', stream ); \
1234 0 : cnt += (ulong)fd_int_max( (f), 0 ) + indent_cnt; \
1235 0 : } while(0)
1236 :
1237 0 : # define SB_TEST( c ) \
1238 0 : do { if( FD_UNLIKELY( !(c) ) ) { EMIT( fprintf( stream, "unexpected: %s failed\n", #c ) ); ctr[0]++; return cnt; } } while(0)
1239 :
1240 : /* validate the superblock header */
1241 :
1242 0 : fd_alloc_superblock_t const * parent;
1243 0 : if( !parent_gaddr_lo ) {
1244 0 : parent = NULL;
1245 0 : parent_gaddr_lo = superblock_gaddr;
1246 0 : } else {
1247 0 : parent = (fd_alloc_superblock_t const *)fd_wksp_laddr_fast( wksp, parent_gaddr_lo );
1248 0 : }
1249 :
1250 0 : SB_TEST( parent_gaddr_lo<=superblock_gaddr ); /* safe to read superblock header */
1251 0 : SB_TEST( (superblock_gaddr+sizeof(fd_alloc_superblock_t))<=parent_gaddr_hi ); /* " */
1252 0 : SB_TEST( fd_ulong_is_aligned( superblock_gaddr, FD_ALLOC_SUPERBLOCK_ALIGN ) ); /* " */
1253 :
1254 0 : fd_alloc_superblock_t const * superblock = (fd_alloc_superblock_t const *)fd_wksp_laddr_fast( wksp, superblock_gaddr );
1255 :
1256 0 : ulong sizeclass = (ulong)superblock->sizeclass;
1257 0 : ulong block_cnt = (ulong)superblock->block_cnt;
1258 0 : ulong cgroup_mask = (ulong)superblock->cgroup_mask;
1259 0 : fd_alloc_block_set_t free_blocks = superblock->free_blocks;
1260 0 : ulong next_gaddr = superblock->next_gaddr;
1261 :
1262 0 : SB_TEST( sizeclass < FD_ALLOC_SIZECLASS_CNT ); /* valid sizeclass */
1263 0 : SB_TEST( block_cnt ==(ulong)fd_alloc_sizeclass_cfg[ sizeclass ].block_cnt ); /* block_cnt matches sizeclass */
1264 0 : SB_TEST( cgroup_mask==(ulong)fd_alloc_sizeclass_cfg[ sizeclass ].cgroup_mask ); /* cgroup_mask matches sizeclass */
1265 0 : SB_TEST( free_blocks==(free_blocks & fd_alloc_block_set_all( block_cnt )) ); /* no spurious bits set */
1266 0 : SB_TEST( fd_ulong_is_aligned( next_gaddr, FD_ALLOC_SUPERBLOCK_ALIGN ) ); /* aligned gaddr or NULL gaddr */
1267 :
1268 0 : ulong block_footprint = (ulong)fd_alloc_sizeclass_cfg[ sizeclass ].block_footprint;
1269 0 : ulong superblock_footprint = sizeof(fd_alloc_superblock_t) + block_cnt*block_footprint;
1270 :
1271 0 : SB_TEST( (superblock_gaddr + superblock_footprint)<=parent_gaddr_hi ); /* safe to read superblock body */
1272 :
1273 : /* validate the superblock nesting */
1274 :
1275 0 : ulong parent_sizeclass;
1276 :
1277 0 : if( !parent ) {
1278 :
1279 0 : parent_sizeclass = FD_ALLOC_SIZECLASS_CNT;
1280 :
1281 0 : SB_TEST( superblock->hdr==FD_ALLOC_HDR_ROOT_SUPERBLOCK ); /* root superblock */
1282 :
1283 0 : } else {
1284 :
1285 0 : parent_sizeclass = (ulong)parent->sizeclass;
1286 :
1287 0 : ulong parent_block_footprint = (ulong)fd_alloc_sizeclass_cfg[ parent_sizeclass ].block_footprint;
1288 :
1289 0 : fd_alloc_hdr_t hdr = superblock->hdr;
1290 0 : int type = fd_alloc_hdr_type( hdr );
1291 0 : ulong idx = fd_alloc_hdr_idx ( hdr );
1292 0 : ulong off = fd_alloc_hdr_off ( hdr );
1293 :
1294 0 : SB_TEST( type==FD_ALLOC_HDR_TYPE_NEST_SUPERBLOCK ); /* nested superblock */
1295 0 : SB_TEST( idx < (ulong)fd_alloc_sizeclass_cfg[ parent_sizeclass ].block_cnt ); /* valid index */
1296 0 : SB_TEST( off == sizeof(fd_alloc_superblock_t) + idx*parent_block_footprint ); /* valid offset */
1297 0 : SB_TEST( off == ((ulong)superblock - (ulong)parent) ); /* " */
1298 :
1299 0 : }
1300 :
1301 0 : SB_TEST( parent_sizeclass==(ulong)fd_alloc_sizeclass_cfg[ sizeclass ].parent_sizeclass ); /* valid parent sizeclass */
1302 :
1303 0 : EMIT( fprintf( stream, "%s superblock at [%013lx,%013lx)\n",
1304 0 : parent ? "nested" : "root", superblock_gaddr, superblock_gaddr + superblock_footprint ) );
1305 :
1306 0 : indent_cnt += 2UL;
1307 :
1308 0 : EMIT( fprintf( stream, "sizeclass %3lu (cgroup_cnt %2lu block_cnt %2lu block_footprint %lu)\n",
1309 0 : sizeclass, cgroup_mask+1UL, block_cnt, block_footprint ) );
1310 :
1311 0 : ulong free_cnt = (ulong)fd_ulong_popcnt( free_blocks );
1312 :
1313 0 : EMIT( fprintf( stream, "free_blocks %013lx next_gaddr %013lx (free_cnt %2lu used_cnt %2lu)\n",
1314 0 : free_blocks, next_gaddr, free_cnt, block_cnt - free_cnt ) );
1315 :
1316 : /* iterate over all used blocks in the superblock */
1317 :
1318 0 : for( ulong block_idx=0UL; block_idx<block_cnt; block_idx++ ) {
1319 0 : if( fd_alloc_block_set_test( free_blocks, block_idx ) ) continue;
1320 :
1321 : /* At this point, the block block_idx is in use and should either
1322 : contain a child superblock or a USER_SMALL allocation. Test if
1323 : the block is a child superblock (note that will recursively test
1324 : the contents of the child if so). If not, search the block for a
1325 : valid fd_alloc_hdr_t (there should be at least one ... if more
1326 : than one, the later ones are probably user data that accidentally
1327 : matched a header). */
1328 :
1329 0 : ulong block_gaddr_lo = superblock_gaddr + sizeof(fd_alloc_superblock_t) + block_idx*block_footprint;
1330 0 : ulong block_gaddr_hi = block_gaddr_lo + block_footprint;
1331 :
1332 0 : fd_alloc_hdr_t hdr = fd_alloc_hdr_load_no_san( fd_wksp_laddr_fast( wksp, block_gaddr_lo + sizeof(fd_alloc_hdr_t) ) );
1333 :
1334 0 : if( hdr==fd_alloc_hdr( FD_ALLOC_HDR_TYPE_NEST_SUPERBLOCK, block_idx, block_gaddr_lo - superblock_gaddr ) ) {
1335 :
1336 0 : EMIT( fprintf( stream, "block %2lu [%013lx,%013lx): nested superblock\n", block_idx, block_gaddr_lo, block_gaddr_hi ) );
1337 :
1338 0 : if( recurse ) cnt += fd_alloc_private_superblock_fprintf( stream, wksp, block_gaddr_lo,
1339 0 : superblock_gaddr, superblock_gaddr + superblock_footprint,
1340 0 : recurse, indent_cnt+2UL, ctr );
1341 :
1342 0 : } else {
1343 :
1344 0 : ulong align = 1UL;
1345 0 : ulong align_stop = block_footprint - sizeof(fd_alloc_hdr_t); /* Note: block_footprint > sizeof(fd_alloc_hdr_t) */
1346 :
1347 0 : for(;;) {
1348 :
1349 0 : if( FD_UNLIKELY( align>=align_stop ) ) {
1350 0 : EMIT( fprintf( stream, "block %2lu [%013lx,%013lx): alloc header not found\n",
1351 0 : block_idx, block_gaddr_lo, block_gaddr_hi ) );
1352 0 : ctr[0]++;
1353 0 : break;
1354 0 : }
1355 :
1356 0 : ulong alloc_gaddr = fd_ulong_align_up( block_gaddr_lo + sizeof(fd_alloc_hdr_t), align );
1357 :
1358 0 : fd_alloc_hdr_t hdr = fd_alloc_hdr_load_no_san( fd_wksp_laddr_fast( wksp, alloc_gaddr ) );
1359 :
1360 0 : if( FD_LIKELY( hdr==fd_alloc_hdr( FD_ALLOC_HDR_TYPE_USER_SMALL, block_idx, alloc_gaddr - superblock_gaddr ) ) ) {
1361 0 : ulong alloc_max = block_gaddr_hi - alloc_gaddr;
1362 0 : EMIT( fprintf( stream, "block %2lu [%013lx,%013lx): small user allocation (gaddr %013lx max %lu)\n",
1363 0 : block_idx, block_gaddr_lo, block_gaddr_hi, alloc_gaddr, alloc_max ));
1364 0 : ctr[1]++;
1365 0 : break;
1366 0 : }
1367 :
1368 0 : align <<= 1;
1369 0 : }
1370 :
1371 0 : }
1372 0 : }
1373 :
1374 0 : # undef SB_TEST
1375 0 : # undef EMIT
1376 :
1377 0 : return cnt;
1378 0 : }
1379 :
1380 : FD_FN_NO_ASAN FD_FN_NO_MSAN int
1381 : fd_alloc_fprintf( fd_alloc_t * join,
1382 3 : FILE * stream ) {
1383 3 : if( FD_UNLIKELY( !stream ) ) return 0; /* NULL stream, can't print anything */
1384 :
1385 3 : ulong cnt = 0UL;
1386 :
1387 12 : # define EMIT(x) do { cnt += (ulong)fd_int_max( (x), 0 ); } while(0)
1388 :
1389 3 : ulong ctr[6];
1390 3 : ctr[0] = 0UL; /* errors detected */
1391 3 : ctr[1] = 0UL; /* small alloc found */
1392 3 : ctr[2] = 0UL; /* wksp partitions used */
1393 3 : ctr[3] = 0UL; /* wksp bytes used */
1394 3 : ctr[4] = 0UL; /* wksp partitions used for large alloc */
1395 3 : ctr[5] = 0UL; /* wksp bytes used for large alloc */
1396 :
1397 3 : fd_alloc_t * alloc = fd_alloc_private_join_alloc( join );
1398 3 : ulong cgroup_hint = fd_alloc_join_cgroup_hint ( join );
1399 :
1400 3 : if( FD_UNLIKELY( !alloc ) ) { /* NULL join passed */
1401 :
1402 0 : EMIT( fprintf( stream, "alloc: gaddr -, join_cgroup_hint %lu, magic 0x0 (bad)\n", cgroup_hint ) );
1403 0 : ctr[0]++;
1404 :
1405 3 : } else { /* Normal join */
1406 :
1407 3 : fd_wksp_t * wksp = fd_alloc_private_wksp( alloc );
1408 :
1409 3 : ulong wksp_gaddr_lo = wksp->gaddr_lo;
1410 3 : ulong wksp_gaddr_hi = wksp->gaddr_hi;
1411 :
1412 : /* Print the summary header */
1413 :
1414 3 : EMIT( fprintf( stream, "alloc: wksp %s gaddr %013lx, join_cgroup_hint %lu, magic 0x%lx (%s)\n",
1415 3 : wksp->name, fd_wksp_gaddr_fast( wksp, alloc ), cgroup_hint,
1416 3 : alloc->magic, alloc->magic==FD_ALLOC_MAGIC ? "good" : "bad" ) );
1417 3 : if( FD_UNLIKELY( alloc->magic!=FD_ALLOC_MAGIC ) ) ctr[0]++;
1418 :
1419 : /* Print known details about each sizeclass */
1420 :
1421 3 : ulong block_footprint = 0UL;
1422 186 : for( ulong sizeclass=0UL; sizeclass<FD_ALLOC_SIZECLASS_CNT; sizeclass++ ) {
1423 183 : ulong block_footprint_prev = block_footprint;
1424 183 : /**/ block_footprint = (ulong)fd_alloc_sizeclass_cfg[ sizeclass ].block_footprint;
1425 :
1426 183 : ulong parent_sizeclass = (ulong)fd_alloc_sizeclass_cfg[ sizeclass ].parent_sizeclass;
1427 183 : ulong block_cnt = (ulong)fd_alloc_sizeclass_cfg[ sizeclass ].block_cnt;
1428 183 : ulong cgroup_cnt = (ulong)fd_alloc_sizeclass_cfg[ sizeclass ].cgroup_mask + 1UL;
1429 :
1430 183 : fd_alloc_vgaddr_t inactive_stack = alloc->inactive_stack[ sizeclass ];
1431 :
1432 183 : ulong inactive_stack_ver = fd_alloc_vgaddr_ver( inactive_stack );
1433 183 : ulong inactive_stack_gaddr = fd_alloc_vgaddr_off( inactive_stack ) << FD_ALLOC_SUPERBLOCK_LG_ALIGN;
1434 :
1435 : /* Omit sizeclasses that have no superblocks in circulation */
1436 :
1437 183 : int do_print = !!inactive_stack_gaddr;
1438 183 : if( !do_print ) {
1439 729 : for( ulong cgroup_idx=0UL; cgroup_idx<cgroup_cnt; cgroup_idx++ ) {
1440 546 : if( *fd_alloc_private_active_slot( alloc, sizeclass, cgroup_idx ) ) {
1441 0 : do_print = 1;
1442 0 : break;
1443 0 : }
1444 546 : }
1445 183 : if( !do_print ) continue;
1446 183 : }
1447 :
1448 : /* Print size class header */
1449 :
1450 0 : EMIT( fprintf( stream,
1451 0 : " sizeclass %3lu: parent_sizeclass %3lu, cgroup_cnt %2lu, block_cnt %2lu, footprint (%lu,%lu]\n",
1452 0 : sizeclass, parent_sizeclass, cgroup_cnt, block_cnt, block_footprint_prev, block_footprint ) );
1453 :
1454 : /* Print inactive stack top */
1455 :
1456 0 : EMIT( fprintf( stream, " inactive_stack: gaddr %013lx, version %lu\n", inactive_stack_gaddr, inactive_stack_ver ) );
1457 :
1458 : /* Print active superblocks */
1459 :
1460 0 : ulong superblock_gaddr;
1461 :
1462 0 : for( ulong cgroup_idx=0UL; cgroup_idx<cgroup_cnt; cgroup_idx++ ) {
1463 0 : superblock_gaddr = *fd_alloc_private_active_slot( alloc, sizeclass, cgroup_idx );
1464 0 : if( !superblock_gaddr ) continue;
1465 0 : ulong next_gaddr = ((fd_alloc_superblock_t const *)fd_wksp_laddr_fast( wksp, superblock_gaddr))->next_gaddr;
1466 0 : EMIT( fprintf( stream, " superblock %013lx: next %013lx (ignored), active (cgroup_idx %2lu)\n",
1467 0 : superblock_gaddr, next_gaddr, cgroup_idx ) );
1468 0 : }
1469 :
1470 : /* Print leading inactive superblocks (best effort) */
1471 :
1472 0 : superblock_gaddr = inactive_stack_gaddr;
1473 0 : for( ulong rem=1024UL; rem; rem-- ) {
1474 0 : if( !( (wksp_gaddr_lo<=superblock_gaddr) & (superblock_gaddr<wksp_gaddr_hi) &
1475 0 : fd_ulong_is_aligned( superblock_gaddr, FD_ALLOC_SUPERBLOCK_ALIGN ) ) ) {
1476 0 : if( FD_UNLIKELY( superblock_gaddr ) ) {
1477 0 : EMIT( fprintf( stream, " inactive stack likely modified by a concurrent operation\n" ) );
1478 0 : ctr[0]++;
1479 0 : }
1480 0 : break;
1481 0 : }
1482 0 : ulong next_gaddr = ((fd_alloc_superblock_t const *)fd_wksp_laddr_fast( wksp, superblock_gaddr))->next_gaddr;
1483 0 : EMIT( fprintf( stream, " superblock %013lx: next %013lx, inactive\n", superblock_gaddr, next_gaddr ) );
1484 0 : superblock_gaddr = next_gaddr;
1485 0 : }
1486 0 : }
1487 :
1488 : /* Scan the wksp partition table for partitions that match this
1489 : allocation tag. We do this in a brute force way that is not algo
1490 : efficient to avoid taking a lock. */
1491 :
1492 3 : ulong alloc_gaddr_lo = fd_wksp_gaddr_fast( wksp, alloc );
1493 3 : ulong alloc_gaddr_hi = alloc_gaddr_lo + FD_ALLOC_FOOTPRINT;
1494 3 : ulong alloc_tag = alloc->tag;
1495 :
1496 3 : ulong part_max = wksp->part_max;
1497 3 : fd_wksp_private_pinfo_t * pinfo = fd_wksp_private_pinfo( wksp );
1498 :
1499 49107 : for( ulong part_idx=0UL; part_idx<part_max; part_idx++ ) {
1500 49104 : if( pinfo[ part_idx ].tag!=alloc_tag ) continue; /* skip ones that don't match */
1501 :
1502 0 : ulong part_gaddr_lo = pinfo[ part_idx ].gaddr_lo;
1503 0 : ulong part_gaddr_hi = pinfo[ part_idx ].gaddr_hi;
1504 0 : if( FD_UNLIKELY( !((wksp_gaddr_lo<=part_gaddr_lo) & (part_gaddr_lo<part_gaddr_hi) & (part_gaddr_hi<=wksp_gaddr_hi)) ) ) {
1505 0 : EMIT( fprintf( stream, " partition [%013lx,%013lx): invalid\n", part_gaddr_lo, part_gaddr_hi ) );
1506 0 : ctr[0]++;
1507 0 : continue;
1508 0 : }
1509 :
1510 0 : ulong part_footprint = part_gaddr_hi - part_gaddr_lo;
1511 :
1512 0 : if( FD_UNLIKELY( (part_gaddr_lo<=alloc_gaddr_lo) & (alloc_gaddr_hi<=part_gaddr_hi) ) ) { /* Partition metadata */
1513 0 : EMIT( fprintf( stream, " partition [%013lx,%013lx): metadata\n", part_gaddr_lo, part_gaddr_hi ) );
1514 0 : ctr[2] += 1UL;
1515 0 : ctr[3] += part_footprint;
1516 0 : continue;
1517 0 : }
1518 :
1519 0 : if( FD_UNLIKELY( !fd_ulong_is_aligned( part_gaddr_lo, alignof(fd_alloc_hdr_t) ) ) ) {
1520 0 : EMIT( fprintf( stream, " partition [%013lx,%013lx): misaligned\n", part_gaddr_lo, part_gaddr_hi ) );
1521 0 : ctr[0]++;
1522 0 : continue;
1523 0 : }
1524 :
1525 0 : if( FD_UNLIKELY( part_footprint <= FD_ALLOC_FOOTPRINT_SMALL_THRESH ) ) {
1526 0 : EMIT( fprintf( stream, " partition [%013lx,%013lx): runt fd_alloc partition\n", part_gaddr_lo, part_gaddr_hi ) );
1527 0 : ctr[0]++;
1528 0 : continue;
1529 0 : }
1530 :
1531 0 : fd_alloc_hdr_t hdr = fd_alloc_hdr_load_no_san( fd_wksp_laddr_fast( wksp, part_gaddr_lo + sizeof(fd_alloc_hdr_t) ) );
1532 :
1533 0 : if( FD_LIKELY( (hdr ==FD_ALLOC_HDR_ROOT_SUPERBLOCK ) &
1534 0 : (part_footprint==FD_ALLOC_ROOT_SUPERBLOCK_FOOTPRINT ) &
1535 0 : (fd_ulong_is_aligned( part_gaddr_lo, FD_ALLOC_SUPERBLOCK_ALIGN )) ) ) {
1536 :
1537 0 : EMIT( fprintf( stream, " partition [%013lx,%013lx): root superblock\n", part_gaddr_lo, part_gaddr_hi ) );
1538 0 : ctr[2]++;
1539 0 : ctr[3] += part_footprint;
1540 :
1541 0 : cnt += fd_alloc_private_superblock_fprintf( stream, wksp, part_gaddr_lo, 0UL, part_gaddr_hi,
1542 0 : 1 /*recurse*/, 4UL /*indent*/, ctr );
1543 :
1544 0 : } else {
1545 :
1546 : /* Search the partition for a USER_LARGE fd_alloc_hdr_t. There
1547 : will be at least one if the partition contains a USER_LARGE
1548 : allocation (if more than one ... the later ones are probably
1549 : user data that looked like a valid hdr). It is theoretically
1550 : possible for junk in an overaligned alloc to accidentally
1551 : look like a header (in which case, this logic will compute
1552 : the wrong location / max for the user large allocation. This
1553 : can be avoided by clearing the alignment padding in
1554 : fd_alloc_malloc_at_least. Once we have a plausible location
1555 : for the user's large alloc, we can compute bounds to how
1556 : large a size was used. We use the upper bound the size
1557 : estimate for simplicity (it would take a lot more space and
1558 : time overhead in normal operation to track the exact size and
1559 : alignment requested explicitly). */
1560 :
1561 0 : ulong align = 1UL;
1562 0 : ulong align_stop = part_footprint - sizeof(fd_alloc_hdr_t);
1563 :
1564 0 : for(;;) {
1565 :
1566 0 : if( FD_UNLIKELY( align>=align_stop ) ) {
1567 0 : EMIT( fprintf( stream, " partition [%013lx,%013lx): alloc header not found\n", part_gaddr_lo, part_gaddr_hi ) );
1568 0 : ctr[0]++;
1569 0 : break;
1570 0 : }
1571 :
1572 0 : ulong alloc_gaddr = fd_ulong_align_up( part_gaddr_lo + sizeof(fd_alloc_hdr_t), align );
1573 :
1574 0 : fd_alloc_hdr_t hdr = fd_alloc_hdr_load_no_san( fd_wksp_laddr_fast( wksp, alloc_gaddr ) );
1575 :
1576 0 : if( FD_LIKELY( hdr==FD_ALLOC_HDR_USER_LARGE ) ) {
1577 0 : ulong alloc_max = part_gaddr_hi - alloc_gaddr;
1578 0 : EMIT( fprintf( stream, " partition [%013lx,%013lx): large user allocation (gaddr %013lx max %lu)\n",
1579 0 : part_gaddr_lo, part_gaddr_hi, alloc_gaddr, alloc_max ));
1580 0 : ctr[2]++;
1581 0 : ctr[3] += part_footprint;
1582 0 : ctr[4] += 1UL;
1583 0 : ctr[5] += part_footprint;
1584 0 : break;
1585 0 : }
1586 :
1587 0 : align <<= 1;
1588 0 : }
1589 :
1590 0 : }
1591 0 : }
1592 3 : }
1593 :
1594 : /* Print summary statistics */
1595 :
1596 3 : EMIT( fprintf( stream,
1597 3 : " summary\n"
1598 3 : " errors detected %21lu%s\n"
1599 3 : " small alloc cnt %21lu\n"
1600 3 : " wksp part used %21lu\n"
1601 3 : " wksp byte used %21lu\n"
1602 3 : " large alloc part used %21lu\n"
1603 3 : " large alloc byte used %21lu\n",
1604 3 : ctr[0], ctr[0] ? " (highly likely spurious if running concurrent and/or with dirty align padding)" : "",
1605 3 : ctr[1], ctr[2], ctr[3], ctr[4], ctr[5] ) );
1606 :
1607 3 : # undef EMIT
1608 :
1609 : return (int)fd_ulong_min( cnt, (ulong)INT_MAX );
1610 3 : }
|
