Line data Source code
1 : #include "fd_alloc.h"
2 : #include "fd_alloc_cfg.h"
3 : #include "../sanitize/fd_asan.h"
4 : #include "../sanitize/fd_msan.h"
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 : /* sizeclass APIs *****************************************************/
12 :
13 : /* fd_alloc_preferred_sizeclass returns the tightest fitting sizeclass
14 : for the given footprint. The caller promises there is at least one
15 : possible size class (i.e. that footprint is in
16 : [0,FD_ALLOC_FOOTPRINT_SMALL_THRESH]. The return will be in
17 : [0,FD_ALLOC_SIZECLASS_CNT). */
18 :
19 : FD_STATIC_ASSERT( 64UL<FD_ALLOC_SIZECLASS_CNT && FD_ALLOC_SIZECLASS_CNT<=128UL, limits );
20 :
21 : static inline ulong
22 3898758 : fd_alloc_preferred_sizeclass( ulong footprint ) {
23 3898758 : ulong l = 0UL;
24 3898758 : ulong h = FD_ALLOC_SIZECLASS_CNT-1UL;
25 :
26 : /* Fixed count loop without early exit to make it easy for compiler to
27 : unroll and nominally eliminate all branches for fast, highly
28 : deterministic performance with no consumption of BTB resources.
29 : Note that 7 assumes 64<=FD_ALLOC_SIZECLASS_CNT-1<128. FIXME: check
30 : the compiler is doing the right thing here with unrolling and
31 : branch elimination. */
32 :
33 31190064 : for( ulong r=0UL; r<7UL; r++ ) {
34 :
35 : /* At this point sizeclasses<l are known to be inadequate and
36 : sizeclasses>=h are known to be suitable. Sizeclasses in [l,h)
37 : have not been tested. */
38 :
39 27291306 : ulong m = (l+h)>>1; /* Note: no overflow for reasonable sizeclass_cnt and l<=m<=h */
40 27291306 : int c = (((ulong)fd_alloc_sizeclass_cfg[ m ].block_footprint)>=footprint);
41 27291306 : l = fd_ulong_if( c, l, m+1UL ); /* cmov */
42 27291306 : h = fd_ulong_if( c, m, h ); /* cmov */
43 27291306 : }
44 :
45 3898758 : return h;
46 3898758 : }
47 :
48 : /* fd_alloc_preferred_sizeclass_cgroup returns preferred sizeclass
49 : concurrency group for a join with the given cgroup_idx. The caller
50 : promises sizeclass is in [0,FD_ALLOC_SIZECLASS_CNT). */
51 :
52 : static inline ulong
53 : fd_alloc_preferred_sizeclass_cgroup( ulong sizeclass,
54 4128591 : ulong cgroup_idx ) {
55 4128591 : return cgroup_idx & (ulong)fd_alloc_sizeclass_cfg[ sizeclass ].cgroup_mask;
56 4128591 : }
57 :
58 : /* fd_alloc_block_set *************************************************/
59 :
60 : /* A fd_alloc_block_set specifies a set of blocks in a superblock. */
61 :
62 : #define SET_NAME fd_alloc_block_set
63 : #define SET_TYPE ulong
64 : #define SET_MAX 64
65 : #include "../tmpl/fd_smallset.c"
66 :
67 : /* fd_alloc_block_set_{add,sub} inserts / removes blocks to / from
68 : block set pointed to by set. The caller promises that blocks are not
69 : / are already in the block set. This operation is a compiler fence.
70 : Further, if FD_HAS_ATOMIC, this operation is done atomically.
71 : Returns the value of the block_set just before the operation. Note:
72 : atomic add/sub has slightly better asm on x86 than atomic or/and/nand
73 : (compiler quality issue, not an architecture issue) and generates the
74 : same results provided the caller promises are met. */
75 :
76 : #if FD_HAS_ATOMIC
77 :
78 : static inline fd_alloc_block_set_t
79 : fd_alloc_block_set_add( fd_alloc_block_set_t * set,
80 3898182 : fd_alloc_block_set_t blocks ) {
81 3898182 : fd_alloc_block_set_t ret;
82 3898182 : FD_COMPILER_MFENCE();
83 3898182 : ret = FD_ATOMIC_FETCH_AND_ADD( set, blocks );
84 3898182 : FD_COMPILER_MFENCE();
85 3898182 : return ret;
86 3898182 : }
87 :
88 : static inline fd_alloc_block_set_t
89 : fd_alloc_block_set_sub( fd_alloc_block_set_t * set,
90 3898758 : fd_alloc_block_set_t blocks ) {
91 3898758 : fd_alloc_block_set_t ret;
92 3898758 : FD_COMPILER_MFENCE();
93 3898758 : ret = FD_ATOMIC_FETCH_AND_SUB( set, blocks );
94 3898758 : FD_COMPILER_MFENCE();
95 3898758 : return ret;
96 3898758 : }
97 :
98 : #else
99 :
100 : static inline fd_alloc_block_set_t
101 : fd_alloc_block_set_add( fd_alloc_block_set_t * set,
102 : fd_alloc_block_set_t blocks ) {
103 : fd_alloc_block_set_t ret;
104 : FD_COMPILER_MFENCE();
105 : ret = FD_VOLATILE_CONST( *set );
106 : FD_VOLATILE( *set ) = ret + blocks;
107 : FD_COMPILER_MFENCE();
108 : return ret;
109 : }
110 :
111 : static inline fd_alloc_block_set_t
112 : fd_alloc_block_set_sub( fd_alloc_block_set_t * set,
113 : fd_alloc_block_set_t blocks ) {
114 : fd_alloc_block_set_t ret;
115 : FD_COMPILER_MFENCE();
116 : ret = FD_VOLATILE_CONST( *set );
117 : FD_VOLATILE( *set ) = ret - blocks;
118 : FD_COMPILER_MFENCE();
119 : return ret;
120 : }
121 :
122 : #endif
123 :
124 : /* fd_alloc_superblock ************************************************/
125 :
126 24573 : #define FD_ALLOC_SUPERBLOCK_ALIGN (16UL) /* Guarantees free_blocks and next_gaddr aligned are on the same cache line */
127 :
128 : struct __attribute__((aligned(FD_ALLOC_SUPERBLOCK_ALIGN))) fd_alloc_superblock {
129 : fd_alloc_block_set_t free_blocks; /* which blocks in this superblock are allocated */
130 : ulong next_gaddr; /* if on the inactive superblock stack, next inactive superblock or NULL, ignored o.w. */
131 : /* FIXME: could put a cgroup hint in the lsb of next gaddr given
132 : it is already aligned 16. */
133 : /* Storage for blocks follows */
134 : };
135 :
136 : typedef struct fd_alloc_superblock fd_alloc_superblock_t;
137 :
138 : /* fd_alloc ***********************************************************/
139 :
140 : /* FD_ALLOC_MAGIC is an ideally unique number that specifies the precise
141 : memory layout of a fd_alloc */
142 :
143 : #if FD_HAS_X86 /* Technically platforms with 16B compare-exchange */
144 :
145 42 : #define FD_ALLOC_MAGIC (0xF17EDA2C37A110C1UL) /* FIRE DANCER ALLOC version 1 */
146 :
147 : #define VOFF_NAME fd_alloc_vgaddr
148 : #define VOFF_TYPE uint128
149 3351624 : #define VOFF_VER_WIDTH 64
150 : #include "../tmpl/fd_voff.c"
151 :
152 : #else /* Platforms without 16B compare-exchange */
153 :
154 : #define FD_ALLOC_MAGIC (0xF17EDA2C37A110C0UL) /* FIRE DANCER ALLOC version 0 */
155 :
156 : /* TODO: Overaligning superblocks on these targets to get a wider
157 : version width */
158 :
159 : #define VOFF_NAME fd_alloc_vgaddr
160 : #define VOFF_TYPE ulong
161 : #define VOFF_VER_WIDTH 4
162 : #include "../tmpl/fd_voff.c"
163 :
164 : #endif
165 :
166 : struct __attribute__((aligned(FD_ALLOC_ALIGN))) fd_alloc {
167 : ulong magic; /* ==FD_ALLOC_MAGIC */
168 : ulong wksp_off; /* Offset of the first byte of this structure from the start of the wksp */
169 : ulong tag; /* tag that will be used by this allocator. Positive. */
170 :
171 : /* Padding to 128 byte alignment here */
172 :
173 : /* active_slot[ sizeclass + FD_ALLOC_SIZECLASS_CNT*cgroup ] is the
174 : gaddr of the active superblock for sizeclass allocations done by a
175 : member of concurrency group cgroup or 0 if there is no active
176 : superblock currently for that sizeclass,cgroup pair.
177 :
178 : inactive_stack[ sizeclass ] is top of inactive stack for sizeclass
179 : or 0 if the stack is empty. This is versioned offset with a 64-bit
180 : version number in the least significant bits and a 64-bit gaddr in
181 : the upper bits. At 64-bits wide, note that version number reuse
182 : will not occur on any human timescales. (FIXME: consider using a
183 : ulong to be more portable to platforms without 128-bit CAS support.
184 : E.g. 20-bit version and a 44-bit gaddr and restricting maximum
185 : supported workspace to ~16 TiB.)
186 :
187 : Note that this is compact but organized such that concurrent
188 : operations from different cgroups are unlikely to create false
189 : sharing. */
190 :
191 : ulong active_slot[ FD_ALLOC_SIZECLASS_CNT*(FD_ALLOC_JOIN_CGROUP_HINT_MAX+1UL) ] __attribute__((aligned(128UL)));
192 :
193 : /* Padding to 128 byte alignment here */
194 :
195 : fd_alloc_vgaddr_t inactive_stack[ FD_ALLOC_SIZECLASS_CNT ] __attribute__((aligned(128UL)));
196 : };
197 :
198 : /* fd_alloc_private_wksp returns the wksp backing alloc. Assumes alloc
199 : is a non-NULL pointer in the caller's address space to the fd_alloc
200 : (not a join handle). */
201 :
202 : FD_FN_PURE static inline fd_wksp_t *
203 5753961 : fd_alloc_private_wksp( fd_alloc_t * alloc ) {
204 5753961 : return (fd_wksp_t *)(((ulong)alloc) - alloc->wksp_off);
205 5753961 : }
206 :
207 : /* fd_alloc_private_active_slot_replace replaces the value currently in
208 : the slot pointed to by active_slot with new_superblock_gaddr and
209 : returns the superblock_gaddr previously in there. This is a compiler
210 : fence. If FD_HAS_ATOMIC, this will be done atomically. */
211 :
212 : static inline ulong
213 : fd_alloc_private_active_slot_replace( ulong * active_slot,
214 8658144 : ulong new_superblock_gaddr ) {
215 8658144 : ulong old_superblock_gaddr;
216 8658144 : FD_COMPILER_MFENCE();
217 8658144 : # if FD_HAS_ATOMIC
218 8658144 : old_superblock_gaddr = FD_ATOMIC_XCHG( active_slot, new_superblock_gaddr );
219 : # else
220 : old_superblock_gaddr = FD_VOLATILE_CONST( *active_slot );
221 : FD_VOLATILE( *active_slot ) = new_superblock_gaddr;
222 : # endif
223 8658144 : FD_COMPILER_MFENCE();
224 8658144 : return old_superblock_gaddr;
225 8658144 : }
226 :
227 : /* fd_alloc_private_inactive_stack_push pushes superblock at the
228 : workspace global address superblock_gaddr in workspace wksp onto the
229 : stack inactive stack. This is a compiler fence. If FD_HAS_ATOMIC,
230 : this will be done atomically. */
231 :
232 : static inline void
233 : fd_alloc_private_inactive_stack_push( fd_alloc_vgaddr_t * inactive_stack,
234 : fd_wksp_t * wksp,
235 154494 : ulong superblock_gaddr ) {
236 154494 : fd_alloc_superblock_t * superblock = (fd_alloc_superblock_t *)fd_wksp_laddr_fast( wksp, superblock_gaddr );
237 :
238 154494 : for(;;) {
239 :
240 : /* Read the top of the inactive stack. */
241 :
242 154494 : fd_alloc_vgaddr_t old;
243 154494 : FD_COMPILER_MFENCE();
244 154494 : old = FD_VOLATILE_CONST( *inactive_stack );
245 154494 : FD_COMPILER_MFENCE();
246 :
247 154494 : ulong top_ver = (ulong)fd_alloc_vgaddr_ver( old );
248 154494 : ulong top_gaddr = (ulong)fd_alloc_vgaddr_off( old );
249 :
250 : /* Try to push the top of the inactive stack */
251 :
252 154494 : fd_alloc_vgaddr_t new = fd_alloc_vgaddr( top_ver+1UL, superblock_gaddr );
253 :
254 154494 : FD_COMPILER_MFENCE();
255 154494 : FD_VOLATILE( superblock->next_gaddr ) = top_gaddr;
256 154494 : FD_COMPILER_MFENCE();
257 :
258 154494 : # if FD_HAS_ATOMIC
259 154494 : if( FD_LIKELY( FD_ATOMIC_CAS( inactive_stack, old, new )==old ) ) break;
260 : # else
261 : if( FD_LIKELY( FD_VOLATILE_CONST( *inactive_stack )==old ) ) { FD_VOLATILE( *inactive_stack ) = new; break; }
262 : # endif
263 :
264 : /* Hmmm ... that failed ... try again */
265 :
266 0 : FD_SPIN_PAUSE();
267 0 : }
268 :
269 154494 : FD_COMPILER_MFENCE();
270 154494 : }
271 :
272 : /* fd_alloc_private_inactive_stack_pop pops superblock off the top of
273 : the inactive stack. Returns the non-zero wksp superblock gaddr of
274 : the popped stack top on success or 0 on failure (i.e. inactive stack
275 : is empty). This is a compiler fence. If FD_HAS_ATOMIC, this will be
276 : done atomically. */
277 :
278 : static inline ulong
279 : fd_alloc_private_inactive_stack_pop( fd_alloc_vgaddr_t * inactive_stack,
280 1160568 : fd_wksp_t * wksp ) {
281 1160568 : ulong top_gaddr;
282 :
283 1160568 : for(;;) {
284 :
285 : /* Read the top of the inactive stack. Return if the inactive stack
286 : is empty. */
287 :
288 1160568 : fd_alloc_vgaddr_t old;
289 1160568 : FD_COMPILER_MFENCE();
290 1160568 : old = FD_VOLATILE_CONST( *inactive_stack );
291 1160568 : FD_COMPILER_MFENCE();
292 :
293 : /**/ top_gaddr = (ulong)fd_alloc_vgaddr_off( old );
294 1160568 : ulong top_ver = (ulong)fd_alloc_vgaddr_ver( old );
295 1160568 : fd_msan_unpoison( &top_gaddr, sizeof( top_gaddr ) );
296 1160568 : if( FD_UNLIKELY( !top_gaddr ) ) break;
297 :
298 : /* Try to pop the top of the inactive stack. */
299 :
300 154470 : fd_alloc_superblock_t * top = (fd_alloc_superblock_t *)fd_wksp_laddr_fast( wksp, top_gaddr );
301 :
302 154470 : ulong next_gaddr;
303 154470 : FD_COMPILER_MFENCE();
304 154470 : next_gaddr = FD_VOLATILE_CONST( top->next_gaddr );
305 154470 : FD_COMPILER_MFENCE();
306 :
307 154470 : fd_alloc_vgaddr_t new = fd_alloc_vgaddr( top_ver+1UL, next_gaddr );
308 :
309 154470 : # if FD_HAS_ATOMIC
310 154470 : if( FD_LIKELY( FD_ATOMIC_CAS( inactive_stack, old, new )==old ) ) break;
311 : # else
312 : if( FD_LIKELY( FD_VOLATILE_CONST( *inactive_stack )==old ) ) { FD_VOLATILE( *inactive_stack ) = new; break; }
313 : # endif
314 :
315 : /* Hmmm ... that failed ... try again */
316 :
317 0 : FD_SPIN_PAUSE();
318 0 : }
319 :
320 1160568 : FD_COMPILER_MFENCE();
321 :
322 1160568 : return top_gaddr;
323 1160568 : }
324 :
325 : /* fd_alloc_hdr_t *****************************************************/
326 :
327 : /* An fd_alloc_hdr_t is a small header prepended to an allocation that
328 : describes the allocation. Because fd_alloc supports arbitrary
329 : allocation alignments, these headers might be stored at unaligned
330 : positions. */
331 :
332 : typedef uint fd_alloc_hdr_t;
333 :
334 : /* FD_ALLOC_HDR_LARGE_* give the fd_alloc_hdr_t used for mallocs done by
335 : the allocator of last resort (i.e. fd_wksp_alloc). The least
336 : significant 7 bits must be FD_ALLOC_SIZECLASS_LARGE so that free can
337 : detect an allocation is done by that allocator. The most significant
338 : 24 bits are a magic number to help with analytics. Bit 7 indicates
339 : whether this allocation is direct user allocation or holds a
340 : superblock that aggregates many small allocations together. */
341 :
342 0 : #define FD_ALLOC_HDR_LARGE_DIRECT ((fd_alloc_hdr_t)(0xFDA11C00U | (fd_alloc_hdr_t)FD_ALLOC_SIZECLASS_LARGE))
343 : #define FD_ALLOC_HDR_LARGE_SUPERBLOCK ((fd_alloc_hdr_t)(0xFDA11C80U | (fd_alloc_hdr_t)FD_ALLOC_SIZECLASS_LARGE))
344 :
345 : /* fd_alloc_hdr_load loads the header for the allocation whose first
346 : byte is at laddr in the caller's address space. The header will be
347 : observed at some point of time between when this call was made and
348 : returned and this implies that the allocation at laddr must be at
349 : least until the caller stops using the header. */
350 :
351 : FD_FN_PURE static inline fd_alloc_hdr_t
352 4260438 : fd_alloc_hdr_load( void const * laddr ) {
353 4260438 : return FD_LOAD( fd_alloc_hdr_t, ((ulong)laddr) - sizeof(fd_alloc_hdr_t) );
354 4260438 : }
355 :
356 : /* fd_alloc_hdr_sizeclass returns the sizeclass of an allocation
357 : described by hdr. This will be in [0,FD_ALLOC_SIZECLASS_CNT) or
358 : FD_ALLOC_SIZECLASS_LARGE. sizeclass==FD_ALLOC_SIZECLASS_LARGE
359 : indicates that the allocation was done via fd_wksp_alloc directly.
360 : Small allocations are clustered into superblocks for performance and
361 : packing efficiency. All allocations in a superblock are from the
362 : same sizeclass. */
363 :
364 4266720 : FD_FN_CONST static inline ulong fd_alloc_hdr_sizeclass( fd_alloc_hdr_t hdr ) { return (ulong)(hdr & 127U); }
365 :
366 : /* fd_alloc_hdr_{superblock,block} return details about a small
367 : allocation whose first byte is at laddr in the caller's address space
368 : and is described by hdr. In particular:
369 :
370 : fd_alloc_hdr_superblock( hdr, laddr ) returns the location in the
371 : caller's address space of the superblock containing the allocation.
372 : The lifetime of a superblock is at least as long as the allocation at
373 : laddr.
374 :
375 : fd_alloc_hdr_block_idx( hdr ) returns the superblock block index of the
376 : block containing the allocation. Note that this will be in:
377 : [0,fd_alloc_sizeclass_block_cnt(sizeclass))
378 : and that:
379 : fd_alloc_sizeclass_block_cnt(sizeclass)<=fd_alloc_block_set_max()<=64. */
380 :
381 : FD_FN_CONST static inline fd_alloc_superblock_t *
382 : fd_alloc_hdr_superblock( fd_alloc_hdr_t hdr,
383 3898920 : void * laddr ) {
384 3898920 : return (fd_alloc_superblock_t *)(((ulong)laddr) - ((ulong)(hdr >> 13)));
385 3898920 : }
386 :
387 3898929 : FD_FN_CONST static inline ulong fd_alloc_hdr_block_idx( fd_alloc_hdr_t hdr ) { return (ulong)((hdr >> 7) & 63U); }
388 :
389 : /* fd_alloc_hdr_is_large returns 1 if hdr is for a large allocation and
390 : 0 if not. fd_alloc_hdr_sizeclass( hdr )==FD_ALLOC_SIZECLASS_LARGE
391 : also works but does not test the magic number in the most significant
392 : bits. */
393 :
394 : FD_FN_CONST static inline int
395 0 : fd_alloc_hdr_is_large( fd_alloc_hdr_t hdr ) {
396 0 : return fd_uint_clear_bit( hdr, 7 )==FD_ALLOC_HDR_LARGE_DIRECT;
397 0 : }
398 :
399 : /* fd_alloc_hdr_large_is_superblock returns 1 if hdr (which is assumed
400 : to be for a large allocation) is for a large allocation that holds a
401 : superblock. */
402 :
403 : FD_FN_CONST static inline int
404 0 : fd_alloc_hdr_large_is_superblock( fd_alloc_hdr_t hdr ) {
405 0 : return fd_uint_extract_bit( hdr, 7 );
406 0 : }
407 :
408 : /* fd_alloc_hdr_store stores a fd_alloc_hdr_t describing a small
409 : sizeclass allocation contained within block of superblock in the
410 : sizeof(fd_alloc_hdr_t) bytes immediately preceding the byte pointed
411 : to by laddr in the caller's address space. The caller promises that
412 : these bytes are somewhere within the block.
413 :
414 : fd_alloc_hdr_store_large similarly stores a fd_alloc_hdr_t describing
415 : a large allocation. */
416 :
417 : static inline void *
418 : fd_alloc_hdr_store( void * laddr,
419 : fd_alloc_superblock_t * superblock,
420 : ulong block_idx,
421 3898758 : ulong sizeclass ) {
422 3898758 : FD_STORE( fd_alloc_hdr_t, ((ulong)laddr) - sizeof(fd_alloc_hdr_t),
423 3898758 : (fd_alloc_hdr_t)( ((((ulong)laddr) - ((ulong)superblock)) << 13) | /* Bits 31:13 - 19 bit: superblock offset */
424 3898758 : (block_idx << 7) | /* Bits 12: 7 - 6 bit: block */
425 3898758 : sizeclass ) ); /* Bits 6: 0 - 7 bit: sizeclass */
426 3898758 : return laddr;
427 3898758 : }
428 :
429 : static inline void *
430 : fd_alloc_hdr_store_large( void * laddr,
431 362277 : int is_superblock ) { /* in [0,1] */
432 362277 : FD_STORE( fd_alloc_hdr_t, ((ulong)laddr) - sizeof(fd_alloc_hdr_t),
433 362277 : FD_ALLOC_HDR_LARGE_DIRECT | (((fd_alloc_hdr_t)is_superblock) << 7) );
434 362277 : return laddr;
435 362277 : }
436 :
437 : /* Misc ***************************************************************/
438 :
439 : /* fd_alloc_private_join_alloc returns the local address of the alloc
440 : for a join. */
441 :
442 : FD_FN_CONST fd_alloc_t *
443 8512656 : fd_alloc_private_join_alloc( fd_alloc_t * join ) {
444 8512656 : return (fd_alloc_t *)(((ulong)join) & ~FD_ALLOC_JOIN_CGROUP_HINT_MAX);
445 8512656 : }
446 :
447 : /* Constructors *******************************************************/
448 :
449 : ulong
450 207 : fd_alloc_align( void ) {
451 207 : return alignof(fd_alloc_t);
452 207 : }
453 :
454 : ulong
455 111 : fd_alloc_footprint( void ) {
456 111 : return sizeof(fd_alloc_t);
457 111 : }
458 :
459 : ulong
460 0 : fd_alloc_superblock_footprint(void){
461 0 : return sizeof(fd_alloc_superblock_t);
462 0 : }
463 :
464 : void *
465 : fd_alloc_new( void * shmem,
466 54 : ulong tag ) {
467 :
468 : /* Check input arguments */
469 :
470 54 : if( FD_UNLIKELY( !shmem ) ) {
471 3 : FD_LOG_WARNING(( "NULL shmem" ));
472 3 : return NULL;
473 3 : }
474 :
475 51 : if( FD_UNLIKELY( !fd_ulong_is_aligned( (ulong)shmem, alignof(fd_alloc_t) ) ) ) {
476 3 : FD_LOG_WARNING(( "misaligned shmem" ));
477 3 : return NULL;
478 3 : }
479 :
480 48 : fd_wksp_t * wksp = fd_wksp_containing( shmem );
481 48 : if( FD_UNLIKELY( !wksp ) ) {
482 3 : FD_LOG_WARNING(( "shmem must be in a workspace" ));
483 3 : return NULL;
484 3 : }
485 :
486 45 : if( FD_UNLIKELY( !tag ) ) {
487 3 : FD_LOG_WARNING(( "bad tag" ));
488 3 : return NULL;
489 3 : }
490 :
491 42 : fd_alloc_t * alloc = (fd_alloc_t *)shmem;
492 42 : fd_memset( alloc, 0, sizeof(fd_alloc_t) );
493 :
494 42 : alloc->wksp_off = (ulong)alloc - (ulong)wksp;
495 42 : alloc->tag = tag;
496 :
497 42 : FD_COMPILER_MFENCE();
498 42 : FD_VOLATILE( alloc->magic ) = FD_ALLOC_MAGIC;
499 42 : FD_COMPILER_MFENCE();
500 :
501 42 : return shmem;
502 45 : }
503 :
504 : fd_alloc_t *
505 : fd_alloc_join( void * shalloc,
506 156 : ulong cgroup_hint ) {
507 156 : fd_alloc_t * alloc = shalloc;
508 :
509 156 : if( FD_UNLIKELY( !alloc ) ) {
510 3 : FD_LOG_WARNING(( "NULL shalloc" ));
511 3 : return NULL;
512 3 : }
513 :
514 153 : if( FD_UNLIKELY( !fd_ulong_is_aligned( (ulong)alloc, alignof(fd_alloc_t) ) ) ) {
515 3 : FD_LOG_WARNING(( "misaligned shalloc" ));
516 3 : return NULL;
517 3 : }
518 :
519 150 : if( FD_UNLIKELY( alloc->magic!=FD_ALLOC_MAGIC ) ) {
520 9 : FD_LOG_WARNING(( "bad magic" ));
521 9 : return NULL;
522 9 : }
523 141 : return fd_alloc_join_cgroup_hint_set( alloc, cgroup_hint );
524 150 : }
525 :
526 : void *
527 69 : fd_alloc_leave( fd_alloc_t * join ) {
528 :
529 69 : if( FD_UNLIKELY( !join ) ) {
530 3 : FD_LOG_WARNING(( "NULL join" ));
531 3 : return NULL;
532 3 : }
533 66 : return fd_alloc_private_join_alloc( join );
534 69 : }
535 :
536 : void *
537 36 : fd_alloc_delete( void * shalloc ) {
538 :
539 36 : if( FD_UNLIKELY( !shalloc ) ) {
540 3 : FD_LOG_WARNING(( "NULL shalloc" ));
541 3 : return NULL;
542 3 : }
543 :
544 33 : if( FD_UNLIKELY( !fd_ulong_is_aligned( (ulong)shalloc, alignof(fd_alloc_t) ) ) ) {
545 3 : FD_LOG_WARNING(( "misaligned shalloc" ));
546 3 : return NULL;
547 3 : }
548 :
549 30 : fd_alloc_t * alloc = (fd_alloc_t *)shalloc;
550 :
551 30 : if( FD_UNLIKELY( alloc->magic!=FD_ALLOC_MAGIC ) ) {
552 3 : FD_LOG_WARNING(( "bad magic" ));
553 3 : return NULL;
554 3 : }
555 :
556 27 : FD_COMPILER_MFENCE();
557 27 : FD_VOLATILE( alloc->magic ) = 0UL;
558 27 : FD_COMPILER_MFENCE();
559 :
560 : /* Clean up as much as we can. For each sizeclass, delete all active
561 : superblocks and all inactive superblocks. We will not be able
562 : cleanup any superblocks that are fully allocated (and any
563 : outstanding large allocations) as we rely on the application to
564 : implicitly track them (because they nominally will eventually call
565 : free on them). So hopefully the application did a good job and
566 : cleaned up all their outstanding stuff before calling delete. */
567 :
568 27 : fd_wksp_t * wksp = fd_alloc_private_wksp( alloc );
569 :
570 3429 : for( ulong sizeclass=0UL; sizeclass<FD_ALLOC_SIZECLASS_CNT; sizeclass++ ) {
571 :
572 3402 : ulong cgroup_cnt = (ulong)fd_alloc_sizeclass_cfg[ sizeclass ].cgroup_mask + 1UL;
573 57834 : for( ulong cgroup_idx=0UL; cgroup_idx<cgroup_cnt; cgroup_idx++ ) {
574 54432 : ulong superblock_gaddr =
575 54432 : fd_alloc_private_active_slot_replace( alloc->active_slot + sizeclass + FD_ALLOC_SIZECLASS_CNT*cgroup_idx, 0UL );
576 54432 : if( FD_UNLIKELY( superblock_gaddr ) )
577 387 : fd_alloc_free( alloc, (fd_alloc_superblock_t *)fd_wksp_laddr_fast( wksp, superblock_gaddr ) );
578 54432 : }
579 :
580 3402 : fd_alloc_vgaddr_t * inactive_stack = alloc->inactive_stack + sizeclass;
581 3417 : for(;;) {
582 3417 : ulong superblock_gaddr = fd_alloc_private_inactive_stack_pop( inactive_stack, wksp );
583 3417 : if( FD_LIKELY( !superblock_gaddr ) ) break;
584 15 : fd_alloc_free( alloc, (fd_alloc_superblock_t *)fd_wksp_laddr_fast( wksp, superblock_gaddr ) );
585 15 : }
586 :
587 3402 : }
588 :
589 27 : return shalloc;
590 30 : }
591 :
592 : fd_wksp_t *
593 42 : fd_alloc_wksp( fd_alloc_t * join ) {
594 42 : return FD_LIKELY( join ) ? fd_alloc_private_wksp( fd_alloc_private_join_alloc( join ) ) : NULL;
595 42 : }
596 :
597 : ulong
598 15 : fd_alloc_tag( fd_alloc_t * join ) {
599 15 : return FD_LIKELY( join ) ? fd_alloc_private_join_alloc( join )->tag : 0UL;
600 15 : }
601 :
602 : static inline void *
603 : fd_alloc_malloc_at_least_impl( fd_alloc_t * join,
604 : ulong align,
605 : ulong sz,
606 4251429 : ulong * max ) {
607 :
608 4251429 : if( FD_UNLIKELY( !max ) ) return NULL;
609 :
610 : /* Handle default align, NULL alloc, 0 size, non-power-of-two align
611 : and unreasonably large sz. footprint has room for fd_alloc_hdr_t,
612 : sz bytes with enough padding to allow for the arbitrary alignment
613 : of blocks in a superblock. Note that footprint is guaranteed not
614 : to overflow if align is a power of 2 as align at most 2^63 and
615 : sizeof is 4 and we abort is align is not a power of 2. So we don't
616 : need to do elaborate overflow checking. */
617 :
618 4251429 : fd_alloc_t * alloc = fd_alloc_private_join_alloc( join );
619 :
620 4251429 : align = fd_ulong_if( !align, FD_ALLOC_MALLOC_ALIGN_DEFAULT, align );
621 :
622 : # if FD_HAS_DEEPASAN
623 : /* The header is prepended and needs to be unpoisoned. Ensure that
624 : there is padding for the alloc_hdr to be properly aligned. We
625 : want to exit silently if the sz passed in is 0. The alignment must be
626 : at least 8. */
627 : ulong fd_alloc_hdr_footprint = fd_ulong_align_up( sizeof(fd_alloc_hdr_t), FD_ASAN_ALIGN );
628 : if( FD_LIKELY(sz && sz < ULONG_MAX) ) {
629 : sz = fd_ulong_align_up( sz, FD_ASAN_ALIGN );
630 : }
631 : align = fd_ulong_if( align < FD_ASAN_ALIGN, FD_ASAN_ALIGN, align );
632 : # else
633 4251429 : ulong fd_alloc_hdr_footprint = sizeof(fd_alloc_hdr_t);
634 4251429 : # endif
635 :
636 4251429 : ulong footprint = sz + fd_alloc_hdr_footprint + align - 1UL;
637 :
638 4251429 : if( FD_UNLIKELY( (!alloc) | (!fd_ulong_is_pow2( align )) | (!sz) | (footprint<=sz) ) ) {
639 66 : *max = 0UL;
640 66 : return NULL;
641 66 : }
642 :
643 4251363 : fd_wksp_t * wksp = fd_alloc_private_wksp( alloc );
644 :
645 : /* At this point, alloc is non-NULL and backed by wksp, align is a
646 : power-of-2, footprint is a reasonable non-zero value. If the
647 : footprint is large, just allocate the memory directly, prepend the
648 : appropriate header and return. TODO: consider clearing alignment
649 : padding for better alloc parameter recovery in diagnostics here? */
650 :
651 4251363 : if( FD_UNLIKELY( footprint > FD_ALLOC_FOOTPRINT_SMALL_THRESH ) ) {
652 :
653 352605 : ulong glo;
654 352605 : ulong ghi;
655 352605 : ulong wksp_gaddr = fd_wksp_alloc_at_least( wksp, 1UL, footprint, alloc->tag, &glo, &ghi );
656 352605 : if( FD_UNLIKELY( !wksp_gaddr ) ) {
657 0 : *max = 0UL;
658 0 : return NULL;
659 0 : }
660 :
661 352605 : ulong alloc_gaddr = fd_ulong_align_up( wksp_gaddr + sizeof(fd_alloc_hdr_t), align );
662 352605 : *max = (ghi - glo) - (alloc_gaddr - wksp_gaddr);
663 352605 : return fd_alloc_hdr_store_large( fd_wksp_laddr_fast( wksp, alloc_gaddr ), 0 /* !sb */ );
664 352605 : }
665 :
666 : /* At this point, the footprint is small. Determine the preferred
667 : sizeclass for this allocation and the preferred active superblock
668 : to use for this sizeclass and join. */
669 :
670 3898758 : ulong sizeclass = fd_alloc_preferred_sizeclass( footprint );
671 3898758 : ulong cgroup = fd_alloc_preferred_sizeclass_cgroup( sizeclass, fd_alloc_join_cgroup_hint( join ) );
672 :
673 3898758 : ulong * active_slot = alloc->active_slot + sizeclass + FD_ALLOC_SIZECLASS_CNT*cgroup;
674 :
675 : /* Try to get exclusive access to the preferred active superblock.
676 : Note that all all active superblocks have at least one free block.
677 :
678 : TODO: consider doing something test-and_test-and-set? E.g.:
679 : superblock_gaddr = FD_VOLATILE_CONST( *active_slot );
680 : if( FD_LIKELY( superblock_gaddr ) ) superblock_gaddr = fd_alloc_replace_active( active_slot, 0UL );
681 : This would avoid an atomic operation if there currently isn't an
682 : active superblock for this sizeclass and cgroup. */
683 :
684 3898758 : ulong superblock_gaddr = fd_alloc_private_active_slot_replace( active_slot, 0UL );
685 :
686 : /* At this point, if superblock_gaddr is non-zero, we have exclusive
687 : access to the superblock and only we can allocate blocks from it.
688 : (Other threads could free blocks to it concurrently though.)
689 :
690 : If superblock_gaddr is zero, there was no preferred active
691 : superblock for this sizeclass,cgroup pair when we looked. So, we
692 : try to pop the inactive superblock stack for this sizeclass. Note
693 : that all inactive superblocks also have at least one free block.
694 :
695 : If that fails, we try to allocate a new superblock to hold this
696 : allocation. If we are able to do so, obviously the new superblock
697 : would have at least one free block for this allocation. (Yes,
698 : malloc calls itself recursively. The base case is the large
699 : allocation above. Note that we expand out the base case explicitly
700 : here so we can distinguish user large allocations from gigantic
701 : superblock allocations in analytics without having to change the
702 : APIs or use the public API as a wrapper.)
703 :
704 : If that fails, we are in trouble and fail (we are either out of
705 : memory or have too much wksp fragmentation). */
706 :
707 3898758 : if( FD_UNLIKELY( !superblock_gaddr ) ) {
708 :
709 146019 : superblock_gaddr = fd_alloc_private_inactive_stack_pop( alloc->inactive_stack + sizeclass, wksp );
710 :
711 146019 : if( FD_UNLIKELY( !superblock_gaddr ) ) {
712 :
713 14901 : fd_alloc_superblock_t * superblock;
714 :
715 14901 : ulong superblock_footprint = (ulong)fd_alloc_sizeclass_cfg[ sizeclass ].superblock_footprint;
716 14901 : if( FD_UNLIKELY( superblock_footprint > FD_ALLOC_FOOTPRINT_SMALL_THRESH ) ) {
717 :
718 9672 : ulong wksp_footprint = superblock_footprint + fd_alloc_hdr_footprint + FD_ALLOC_SUPERBLOCK_ALIGN - 1UL;
719 9672 : ulong wksp_gaddr = fd_wksp_alloc( wksp, 1UL, wksp_footprint, alloc->tag );
720 9672 : if( FD_UNLIKELY( !wksp_gaddr ) ) {
721 0 : *max = 0UL;
722 0 : return NULL;
723 0 : }
724 :
725 9672 : superblock_gaddr = fd_ulong_align_up( wksp_gaddr + fd_alloc_hdr_footprint, FD_ALLOC_SUPERBLOCK_ALIGN );
726 : # if FD_HAS_DEEPASAN
727 : /* At this point, a new superblock is allocated from the wksp and the header
728 : is prepended. The alignment needs to be taken into account: the padding
729 : should also be unpoisoned.
730 :
731 : Due to ASan requiring 8 byte word alignment for poisoning regions, must
732 : guarantee 8 bytes for the header instead of just sizeof(fd_alloc_hdr_t).
733 : We have a worst case padding of 15 bytes. Due to forced alignment in
734 : fd_wksp_alloc of at least 8 bytes, in the worst case we will use 8 bytes
735 : to align up the superblock_gaddr. The remaining 7 padding bytes will be
736 : used to safely allow for the superblock_footprint to be aligned up to
737 : an 8 byte multiple. */
738 : void * unpoison_laddr = fd_wksp_laddr_fast( wksp, superblock_gaddr - fd_alloc_hdr_footprint );
739 : ulong aligned_superblock_footprint = fd_ulong_align_up( superblock_footprint, FD_ASAN_ALIGN );
740 : fd_asan_unpoison( unpoison_laddr, aligned_superblock_footprint + fd_alloc_hdr_footprint );
741 : # endif
742 :
743 9672 : superblock = (fd_alloc_superblock_t *)
744 9672 : fd_alloc_hdr_store_large( fd_wksp_laddr_fast( wksp, superblock_gaddr ), 1 /* sb */ );
745 :
746 9672 : } else {
747 :
748 : /* TODO: consider having user facing API wrap an internal API so
749 : that recursive calls don't have to do redundant error
750 : trapping?
751 :
752 : TODO: consider using at_least semantics to adapt the actual
753 : size of the superblock to the location it is stored
754 : (currently should be irrelevant as the sizeclasses are
755 : designed to tightly nest). */
756 :
757 5229 : superblock = fd_alloc_malloc( join, FD_ALLOC_SUPERBLOCK_ALIGN, superblock_footprint );
758 5229 : if( FD_UNLIKELY( !superblock ) ) {
759 0 : *max = 0UL;
760 0 : return NULL;
761 0 : }
762 5229 : superblock_gaddr = fd_wksp_gaddr_fast( wksp, superblock );
763 :
764 5229 : }
765 :
766 14901 : FD_COMPILER_MFENCE();
767 14901 : FD_VOLATILE( superblock->free_blocks ) = fd_ulong_mask_lsb( (int)(uint)fd_alloc_sizeclass_cfg[ sizeclass ].block_cnt );
768 14901 : FD_VOLATILE( superblock->next_gaddr ) = 0UL;
769 14901 : FD_COMPILER_MFENCE();
770 :
771 14901 : }
772 146019 : }
773 :
774 : /* At this point, we have a superblock with space for at least one
775 : allocation and only we can allocate blocks from it. Other threads
776 : could free blocks in this superblock concurrently though. As such,
777 : we can non-atomically find a set bit in free_blocks (there will be
778 : at least one and no other thread will clear it behind our back) but
779 : we must atomically clear the bit we found so we don't mess up the
780 : other bits that might be concurrently set by free. */
781 :
782 3898758 : fd_alloc_superblock_t * superblock = (fd_alloc_superblock_t *)fd_wksp_laddr_fast( wksp, superblock_gaddr );
783 :
784 3898758 : fd_alloc_block_set_t free_blocks;
785 3898758 : FD_COMPILER_MFENCE();
786 3898758 : free_blocks = FD_VOLATILE_CONST( superblock->free_blocks );
787 3898758 : FD_COMPILER_MFENCE();
788 :
789 3898758 : ulong block_idx = fd_alloc_block_set_first( free_blocks );
790 3898758 : fd_alloc_block_set_t block = fd_alloc_block_set_ele( block_idx );
791 :
792 3898758 : free_blocks = fd_alloc_block_set_sub( &superblock->free_blocks, block );
793 :
794 : /* At this point, free_blocks gives the set of free blocks in the
795 : superblock immediately before the allocation occurred. */
796 :
797 3898758 : if( FD_LIKELY( free_blocks!=block ) ) {
798 :
799 : /* At this point, we know the superblock has at least one
800 : allocated block in it (the one we just allocated) and one free
801 : block in it. And this will hold true until we put this
802 : superblock back into circulation. Specifically, nobody can free
803 : the block we just allocated until we return to tell them about it
804 : and nobody can allocate any remaining free blocks until we get
805 : this superblock back into circulation. To get this superblock
806 : back into circulation, we make it the active superblock for this
807 : sizeclass,cgroup pair. */
808 :
809 3668910 : ulong displaced_superblock_gaddr = fd_alloc_private_active_slot_replace( active_slot, superblock_gaddr );
810 :
811 : /* And if this displaced a previously active superblock (e.g.
812 : another thread made an different superblock the active one while
813 : we were doing the above), we add the displaced superblock to the
814 : sizeclass's inactive superblocks. Note that any such displaced
815 : superblock also has at least one free block in it (the active
816 : superblock always has at least one free block) that nobody can
817 : allocate from as, at this point, it is not in circulation. Thus,
818 : pushing it onto the superblock's inactive stack will preserve the
819 : invariant that all inactive superblocks have at least one free
820 : block. */
821 :
822 3668910 : if( FD_UNLIKELY( displaced_superblock_gaddr ) )
823 0 : fd_alloc_private_inactive_stack_push( alloc->inactive_stack + sizeclass, wksp, displaced_superblock_gaddr );
824 :
825 3668910 : } //else {
826 :
827 : /* The superblock had no more free blocks immediately after the
828 : allocation occurred. We should not make this superblock the
829 : preferred superblock or push it onto the sizeclass's nonfull
830 : superblock stack; it would break the invariants that all
831 : superblocks in circulation for a sizeclass have at least one
832 : free block.
833 :
834 : And, as this superblock had no free blocks, we don't need to
835 : track the superblock anyway as malloc can't use the superblock
836 : until some of the blocks in it have been freed. As such, this
837 : superblock will not be used in a malloc until after the next call
838 : to free on a block in this superblock returns this superblock to
839 : circulation. Note that this superblock will have at least one
840 : allocated block until after this function returns (the block we
841 : just allocated) and thus cannot ever be considered as a deletion
842 : candidate until after this function returns and this allocation
843 : is freed.
844 :
845 : As discussed in free below, we could update a superblock cgroup
846 : hint here (such that the when the superblock goes back into
847 : circulation, it will be put into circulation as the active
848 : superblock for this cgroup to encourage for additional mallocs
849 : from this thread for good spatial locality). This doesn't need
850 : to be atomic. Even though a concurrent free on another thread
851 : might get this into superblock into circulation before this
852 : executes (and thus also have other mallocs occurred that changed
853 : the active_hint), it doesn't matter. So long as the hint is a
854 : sane value at all points in time, free will work fine. */
855 :
856 : //}
857 :
858 : /* Carve the requested allocation out of the newly allocated block,
859 : prepend the allocation header for use by free and return. TODO:
860 : considering clearing alignment padding for better alloc parameter
861 : recovery in diagnostics here? */
862 :
863 3898758 : ulong block_footprint = (ulong)fd_alloc_sizeclass_cfg[ sizeclass ].block_footprint;
864 3898758 : ulong block_laddr = (ulong)superblock + sizeof(fd_alloc_superblock_t) + block_idx*block_footprint;
865 3898758 : ulong alloc_laddr = fd_ulong_align_up( block_laddr + fd_alloc_hdr_footprint, align );
866 :
867 : # if FD_HAS_DEEPASAN
868 : /* The block and the header must be unpoisoned to accomodate the block
869 : footprint. The block footprint is determined by the sizeclass which
870 : provides the minimum size that accomodates the footprint which is the
871 : sz that's passed in, the padded fd_alloc_hdr, and the worst case amount
872 : of alignment bytes. Because sz % FD_ASAN_ALIGN == 0, it is known that
873 : we will have unused bytes at the end of the block since alloc_laddr %
874 : FD_ASAN_ALIGN == 0. To ensure ASAN alignment, the range of bytes used
875 : in the block can be safely rounded down.
876 : */
877 :
878 : void* laddr = (void*)(alloc_laddr - fd_alloc_hdr_footprint);
879 :
880 : ulong block_hi_addr = block_laddr + block_footprint;
881 : ulong block_unpoison_sz = fd_ulong_align_dn( block_hi_addr - alloc_laddr, FD_ASAN_ALIGN );
882 : fd_asan_unpoison( laddr, block_unpoison_sz + fd_alloc_hdr_footprint );
883 : # endif
884 :
885 3898758 : *max = block_footprint - (alloc_laddr - block_laddr);
886 :
887 3898758 : return fd_alloc_hdr_store( (void *)alloc_laddr, superblock, block_idx, sizeclass );
888 3898758 : }
889 :
890 : void *
891 : fd_alloc_malloc_at_least( fd_alloc_t * join,
892 : ulong align,
893 : ulong sz,
894 4251429 : ulong * max ) {
895 4251429 : void * res = fd_alloc_malloc_at_least_impl( join, align, sz, max );
896 4251429 : fd_msan_poison( res, *max );
897 4251429 : return res;
898 4251429 : }
899 :
900 : void
901 : fd_alloc_free( fd_alloc_t * join,
902 4260495 : void * laddr ) {
903 :
904 : /* Handle NULL alloc and/or NULL laddr */
905 :
906 4260495 : fd_alloc_t * alloc = fd_alloc_private_join_alloc( join );
907 4260495 : if( FD_UNLIKELY( (!alloc) | (!laddr) ) ) return;
908 :
909 : /* At this point, we have a non-NULL alloc and a pointer to the first
910 : byte to an allocation done by it. Load the allocation header and
911 : extract the sizeclass. If the sizeclass indicates this is a large
912 : allocation, use fd_wksp_free to free this allocation (note that
913 : fd_wksp_free works for any byte within the wksp allocation). */
914 :
915 4260438 : fd_alloc_hdr_t hdr = fd_alloc_hdr_load( laddr );
916 4260438 : ulong sizeclass = fd_alloc_hdr_sizeclass( hdr );
917 :
918 4260438 : if( FD_UNLIKELY( sizeclass==FD_ALLOC_SIZECLASS_LARGE ) ) {
919 362256 : fd_wksp_t * wksp = fd_alloc_private_wksp( alloc );
920 362256 : fd_wksp_free( wksp, fd_wksp_gaddr_fast( wksp, laddr ) );
921 362256 : return;
922 362256 : }
923 :
924 : /* At this point, we have a small allocation. Determine the
925 : superblock and block index from the header and then free the block. */
926 :
927 3898182 : fd_alloc_superblock_t * superblock = fd_alloc_hdr_superblock( hdr, laddr );
928 3898182 : ulong block_idx = fd_alloc_hdr_block_idx( hdr );
929 3898182 : fd_alloc_block_set_t block = fd_alloc_block_set_ele( block_idx );
930 3898182 : fd_alloc_block_set_t free_blocks = fd_alloc_block_set_add( &superblock->free_blocks, block );
931 :
932 :
933 : # if FD_HAS_DEEPASAN
934 : /* The portion of the block which is used for the header and the allocation
935 : should get poisoned. The alloc's laddr is already at least 8 byte aligned.
936 : The 8 bytes prior to the start of the laddr are used by the fd_alloc_hdr_t.
937 : These should get poisoned as the block is freed again. The region used by
938 : the allocation should also get poisoned: [laddr,block_laddr+block_footprint].
939 : However, we know that the size of the initial allocation was also 8 byte
940 : aligned so we align down the size of the range to poison safely. */
941 : ulong block_footprint = (ulong)fd_alloc_sizeclass_cfg[ sizeclass ].block_footprint;
942 : ulong block_laddr = (ulong)superblock + sizeof(fd_alloc_superblock_t) + block_idx*block_footprint;
943 : ulong block_hi_addr = fd_ulong_align_dn( block_laddr + block_footprint, FD_ASAN_ALIGN );
944 : ulong fd_alloc_hdr_footprint = fd_ulong_align_up( sizeof(fd_alloc_hdr_t), FD_ASAN_ALIGN );
945 : ulong fd_alloc_hdr_laddr = (ulong)laddr - fd_alloc_hdr_footprint;
946 : ulong sz = block_hi_addr - (ulong)laddr + fd_alloc_hdr_footprint;
947 : fd_asan_poison( (void*)fd_alloc_hdr_laddr, sz );
948 : # endif
949 :
950 : /* At this point, free_blocks is the set of free blocks just before
951 : the free. */
952 :
953 3898182 : ulong free_cnt = fd_alloc_block_set_cnt( free_blocks );
954 3898182 : if( FD_UNLIKELY( !free_cnt ) ) {
955 :
956 : /* The superblock containing this block had no free blocks
957 : immediately before we freed the allocation. Thus, at this point,
958 : nobody can allocate any blocks from this superblock (the
959 : superblock is neither an active superblock nor on the inactive
960 : stack as per the note in malloc above) and we need to get the
961 : superblock back into circulation for reuse. It is okay if other
962 : threads concurrently free other blocks in this superblock while
963 : we are doing this (they know the superblock is either in
964 : circulation or is being put into circulation).
965 :
966 : Since there is at least one free block in the superblock and
967 : nobody can allocate from it until it is circulation, putting it
968 : into circulation preserves the invariant that all superblocks in
969 : circulation have at least one free block.
970 :
971 : We have a bunch of options for putting this superblock back into
972 : circulation:
973 :
974 : - By pushing it onto the inactive stack
975 : - By making it the active superblock of the caller's cgroup
976 : - By making it the active superblock of the cgroup that most did
977 : the most recent malloc from it.
978 : - By making it the active superblock based on explicitly provided
979 : hint.
980 : - ...
981 :
982 : The first option is simplest to implement and balanced between
983 : common use cases single threaded, malloc/free pairs have thread
984 : affinity, and pipelined use cases. (E.g. single threaded will
985 : take an extra time to hop from inactive and active and potential
986 : has slightly worse overallocation, similar story for paired.
987 : Cache affinity in these two cases might be slightly degraded from
988 : empty superblocks hopping between concurrency groups via the
989 : inactive stack, pipelined naturally gets the page back to the
990 : malloc-ing thread albeit with a brief hop through the inactive
991 : stack though).
992 :
993 : The second option is about as simple and optimizes the
994 : single/threaded and paired use cases as this thread is also the
995 : thread likely the same thread that malloc'd this. Pipelined is
996 : marginally worse as the superblock will have to take two hops
997 : before it gets reused again (from the free-ing thread active
998 : superblock to the inactive stack to the malloc-ing active
999 : superblock).
1000 :
1001 : The third and fourth options can simultaneously get all options
1002 : optimized but they require extra plumbing (either under the hood
1003 : as per the note in malloc above from to the caller to get the
1004 : extra context).
1005 :
1006 : Currently we do the second option for simplicity and optimal
1007 : behaviors in the single threaded and paired use cases. */
1008 :
1009 229833 : fd_wksp_t * wksp = fd_alloc_private_wksp( alloc );
1010 :
1011 229833 : ulong cgroup = fd_alloc_preferred_sizeclass_cgroup( sizeclass, fd_alloc_join_cgroup_hint( join ) );
1012 229833 : ulong * active_slot = alloc->active_slot + sizeclass + FD_ALLOC_SIZECLASS_CNT*cgroup;
1013 :
1014 229833 : ulong displaced_superblock_gaddr = fd_alloc_private_active_slot_replace( active_slot, fd_wksp_gaddr_fast( wksp, superblock ) );
1015 :
1016 : /* If this displaced an already active superblock, we need to push
1017 : the displaced superblock onto the inactive stack (note that the
1018 : superblock cannot be the same as the currently active superblock
1019 : because the superblock was not in circulation before). */
1020 :
1021 229833 : if( FD_UNLIKELY( displaced_superblock_gaddr ) )
1022 145488 : fd_alloc_private_inactive_stack_push( alloc->inactive_stack + sizeclass, wksp, displaced_superblock_gaddr );
1023 229833 : return;
1024 229833 : }
1025 :
1026 : /* This point, we know the superblock had some free blocks before our
1027 : free and thus is currently in circulation. */
1028 :
1029 3668349 : free_cnt++; /* Number of free blocks immediately after above free */
1030 :
1031 3668349 : ulong block_cnt = (ulong)fd_alloc_sizeclass_cfg[ sizeclass ].block_cnt;
1032 3668349 : if( FD_UNLIKELY( free_cnt==block_cnt ) ) {
1033 :
1034 : /* None of the blocks were in use after the above free. We might
1035 : consider freeing it to reclaim space for other sizeclasses or
1036 : large allocations. But we don't mind having a few totally empty
1037 : superblocks in circulation for a sizeclass as this prevents
1038 : things like:
1039 :
1040 : addr = malloc(sz);
1041 : free(addr);
1042 : addr = malloc(sz);
1043 : free(addr)
1044 : ...
1045 : addr = malloc(sz);
1046 : free(addr)
1047 :
1048 : from repeatedly needing to invoke malloc recursively to recreate
1049 : superblock hierarchies that were prematurely freed.
1050 :
1051 : Regardless, since this superblock is in circulation, we can't be
1052 : sure it is safe to delete because something might be malloc-ing
1053 : from it concurrently. Thus, we are going to keep this superblock
1054 : in circulation as is.
1055 :
1056 : But, since we know we have at least 1 completely empty superblock
1057 : in circulation now, to prevent the unbounded accumulation of
1058 : completely empty superblocks, we will try to get an inactive
1059 : superblock and, if that is empty, delete that.
1060 :
1061 : This is pretty tricky as it is possible other threads are
1062 : concurrently trying to pop the inactive stack to do a malloc. If
1063 : we actually unmapped the memory here, such a thread could seg
1064 : fault if it stalls after it reads the top of the stack but before
1065 : it queries the top for the next_gaddr (and we'd have to use
1066 : another strategy). But that is not an issue here as the
1067 : underlying wksp memory is still mapped post-deletion regardless.
1068 :
1069 : Likewise, though the post deletion top->next_gaddr read will get
1070 : a stale value in this scenario, it highly likely will not be
1071 : injected into the inactive_stack because the CAS will detect that
1072 : inactive_stack top has changed and fail.
1073 :
1074 : And, lastly, we version inactive_stack top such that, even if
1075 : somehow we had a thread stall in pop after reading
1076 : top->next_gaddr / other threads do other operations that
1077 : ultimately keep top the same change the value of top->next_gaddr
1078 : / stalled thread resumes, the version number on the stalled
1079 : thread will be wrong cause the CAS to fail. (There is a
1080 : theoretical risk of version number reuse but the version number
1081 : is wide enough to make that risk zero on any practical
1082 : timescale.) */
1083 :
1084 909828 : fd_wksp_t * wksp = fd_alloc_private_wksp( alloc );
1085 909828 : ulong deletion_candidate_gaddr = fd_alloc_private_inactive_stack_pop( alloc->inactive_stack + sizeclass, wksp );
1086 :
1087 909828 : if( FD_UNLIKELY( !deletion_candidate_gaddr ) ) return; /* No deletion_candidate, unclear branch prob */
1088 :
1089 22581 : fd_alloc_superblock_t * deletion_candidate = (fd_alloc_superblock_t *)fd_wksp_laddr_fast( wksp, deletion_candidate_gaddr );
1090 :
1091 22581 : ulong deletion_candidate_free_blocks;
1092 22581 : FD_COMPILER_MFENCE();
1093 22581 : deletion_candidate_free_blocks = FD_VOLATILE_CONST( deletion_candidate->free_blocks );
1094 22581 : FD_COMPILER_MFENCE();
1095 :
1096 22581 : if( FD_UNLIKELY( fd_alloc_block_set_cnt( deletion_candidate_free_blocks )==block_cnt ) ) /* Candidate empty -> delete it */
1097 14331 : fd_alloc_free( join, deletion_candidate );
1098 8250 : else /* Candidate not empty -> return it to circulation */
1099 8250 : fd_alloc_private_inactive_stack_push( alloc->inactive_stack + sizeclass, wksp, deletion_candidate_gaddr );
1100 :
1101 22581 : return;
1102 909828 : }
1103 3668349 : }
1104 :
1105 : void
1106 399 : fd_alloc_compact( fd_alloc_t * join ) {
1107 399 : fd_alloc_t * alloc = fd_alloc_private_join_alloc( join );
1108 399 : if( FD_UNLIKELY( !alloc ) ) {
1109 0 : FD_LOG_WARNING(( "bad join" ));
1110 0 : return;
1111 0 : }
1112 :
1113 399 : fd_wksp_t * wksp = fd_alloc_private_wksp( alloc );
1114 :
1115 : /* We scan each sizeclass (in monotonically increasing order) for
1116 : completely empty superblocks that thus can be freed. This has the
1117 : pleasant side effect that, as smaller empty superblocks get freed,
1118 : it can potentially allow for any larger superblocks in which they
1119 : are nested to be subsequently freed. If no other operations are
1120 : running concurrently, any remaining gigantic superblocks should
1121 : contain at least one application allocation somewhere in them. */
1122 :
1123 50673 : for( ulong sizeclass=0UL; sizeclass<FD_ALLOC_SIZECLASS_CNT; sizeclass++ ) {
1124 50274 : ulong block_cnt = (ulong)fd_alloc_sizeclass_cfg[ sizeclass ].block_cnt;
1125 50274 : ulong cgroup_cnt = (ulong)fd_alloc_sizeclass_cfg[ sizeclass ].cgroup_mask + 1UL;
1126 50274 : fd_alloc_vgaddr_t * inactive_stack = alloc->inactive_stack + sizeclass;
1127 :
1128 : /* For each active superblock in this sizeclass */
1129 :
1130 854658 : for( ulong cgroup_idx=0UL; cgroup_idx<cgroup_cnt; cgroup_idx++ ) {
1131 804384 : ulong * active_slot = alloc->active_slot + sizeclass + FD_ALLOC_SIZECLASS_CNT*cgroup_idx;
1132 804384 : ulong superblock_gaddr = fd_alloc_private_active_slot_replace( active_slot, 0UL );
1133 804384 : if( !superblock_gaddr ) continue; /* application dependent branch prob */
1134 :
1135 1893 : fd_alloc_superblock_t * superblock = (fd_alloc_superblock_t *)fd_wksp_laddr_fast( wksp, superblock_gaddr );
1136 :
1137 : /* At this point, we have atomically acquired the cgroup_idx's
1138 : active superblock, there is no active superblock for
1139 : cgroup_idx, and it has at least one free block. Since the
1140 : superblock is out of circulation for malloc, nobody will malloc
1141 : anything from this superblock behind our back. And if this
1142 : superblock is completely empty, nobody will call free on any
1143 : blocks in this superblock behind our back. Thus we can free
1144 : this superblock safely.
1145 :
1146 : If there are some blocks still allocated, we put the superblock
1147 : back into circulation (we know from the above it still has at
1148 : least one free block, preserving the invariant). This might
1149 : displace a superblock that another thread made active behind
1150 : our back. We push any such superblock block onto the inactive
1151 : stack (it also will have at least one free block for the same
1152 : reasons). */
1153 :
1154 1893 : if( fd_alloc_block_set_cnt( superblock->free_blocks )==block_cnt ) fd_alloc_free( join, superblock );
1155 1827 : else {
1156 1827 : ulong displaced_superblock_gaddr = fd_alloc_private_active_slot_replace( active_slot, superblock_gaddr );
1157 1827 : if( FD_UNLIKELY( displaced_superblock_gaddr ) )
1158 0 : fd_alloc_private_inactive_stack_push( inactive_stack, wksp, displaced_superblock_gaddr );
1159 1827 : }
1160 1893 : }
1161 :
1162 : /* Drain the inactive stack for this sizeclass. All empty
1163 : superblocks found will be freed (safe for the same reasons as
1164 : above). All remaining superblocks will be pushed onto a local
1165 : stack (and every one will have at least one free block it while
1166 : there for the same reasons). After the inactive stack drain, we
1167 : drain the local stack back into the inactive stack to get all
1168 : these remaining superblocks back into circulation (also safe for
1169 : the same reasons) and with same relative ordering (not required).
1170 : We technically don't need to use a lockfree push / pop for the
1171 : local stack but no sense in implementing a second version for
1172 : this mostly diagnostic / teardown oriented use case. */
1173 :
1174 50274 : fd_alloc_vgaddr_t local_stack[1];
1175 :
1176 50274 : local_stack[0] = fd_alloc_vgaddr( 0UL, 0UL );
1177 :
1178 50652 : for(;;) {
1179 50652 : ulong superblock_gaddr = fd_alloc_private_inactive_stack_pop( inactive_stack, wksp );
1180 50652 : if( !superblock_gaddr ) break; /* application dependent branch prob */
1181 378 : fd_alloc_superblock_t * superblock = (fd_alloc_superblock_t *)fd_wksp_laddr_fast( wksp, superblock_gaddr );
1182 :
1183 378 : if( fd_alloc_block_set_cnt( superblock->free_blocks )==block_cnt ) fd_alloc_free( join, superblock );
1184 378 : else fd_alloc_private_inactive_stack_push( local_stack, wksp, superblock_gaddr );
1185 378 : }
1186 :
1187 50652 : for(;;) {
1188 50652 : ulong superblock_gaddr = fd_alloc_private_inactive_stack_pop( local_stack, wksp );
1189 50652 : if( !superblock_gaddr ) break; /* application dependent branch prob */
1190 :
1191 378 : fd_alloc_private_inactive_stack_push( inactive_stack, wksp, superblock_gaddr );
1192 378 : }
1193 50274 : }
1194 399 : }
1195 :
1196 : #include "../wksp/fd_wksp_private.h"
1197 :
1198 : int
1199 204 : fd_alloc_is_empty( fd_alloc_t * join ) {
1200 204 : fd_alloc_t * alloc = fd_alloc_private_join_alloc( join );
1201 204 : if( FD_UNLIKELY( !alloc ) ) return 0;
1202 :
1203 204 : fd_alloc_compact( join );
1204 :
1205 : /* At this point (assuming no concurrent operations on this alloc),
1206 : all remaining large allocations contain at least one user
1207 : allocation. Thus if there are any large allocs remaining for this
1208 : alloc, we know the alloc is not empty. Since the wksp alloc that
1209 : holds the alloc itself might use the tag the used for large
1210 : allocations, we handle that as well. We do this in a brute force
1211 : way to avoid taking a lock (note that this calculation should
1212 : really only be done as non-performance critical diagnostic and then
1213 : on a quiescent system). */
1214 :
1215 204 : fd_wksp_t * wksp = fd_alloc_private_wksp( alloc );
1216 :
1217 204 : ulong alloc_lo = fd_wksp_gaddr_fast( wksp, alloc );
1218 204 : ulong alloc_hi = alloc_lo + FD_ALLOC_FOOTPRINT;
1219 204 : ulong alloc_tag = alloc->tag;
1220 :
1221 204 : ulong part_max = wksp->part_max;
1222 204 : fd_wksp_private_pinfo_t * pinfo = fd_wksp_private_pinfo( wksp );
1223 :
1224 204 : ulong i;
1225 344316 : for( i=0UL; i<part_max; i++ ) {
1226 344304 : if( FD_LIKELY( pinfo[ i ].tag!=alloc_tag ) ) continue; /* optimize for no leak case */
1227 195 : ulong gaddr_lo = pinfo[ i ].gaddr_lo;
1228 195 : ulong gaddr_hi = pinfo[ i ].gaddr_hi;
1229 195 : if( FD_UNLIKELY( !((gaddr_lo<=alloc_lo) & (alloc_hi<=gaddr_hi)) ) ) break; /* optimize for no leak case */
1230 195 : }
1231 :
1232 204 : return i==part_max;
1233 204 : }
1234 :
1235 : /**********************************************************************/
1236 :
1237 : #include <stdio.h>
1238 :
1239 8178 : #define TRAP(x) do { int _cnt = (x); if( _cnt<0 ) { return _cnt; } cnt += _cnt; } while(0)
1240 :
1241 : /* fd_alloc_superblock_fprintf pretty prints to the given stream
1242 : exhaustive details about the current state of the given superblock in
1243 : wksp at superblock_gaddr. The superblock's parameters are given by
1244 : sizeclass, block_cnt, block_footprint. Diagnostics will be accumulated
1245 : ctr. Returns behavior matches fprintf return behavior (i.e. the
1246 : number of characters output to stream or a negative error code).
1247 : This is meant to be called exclusively from fd_alloc_fprintf and does
1248 : no error trapping of its inputs. */
1249 :
1250 : static int
1251 : fd_alloc_superblock_fprintf( fd_wksp_t * wksp, /* non-NULL */
1252 : ulong superblock_gaddr, /* valid gaddr for wksp */
1253 : ulong sizeclass, /* valid sizeclass */
1254 : ulong block_cnt, /* matches sizeclass cfg */
1255 : ulong block_footprint, /* matches sizeclass cfg */
1256 : FILE * stream, /* non-NULL */
1257 1488 : ulong * ctr ) { /* non-NULL, room for 2 */
1258 1488 : int cnt = 0;
1259 :
1260 : /* Print the block header */
1261 :
1262 1488 : fd_alloc_superblock_t * superblock = fd_wksp_laddr_fast( wksp, superblock_gaddr );
1263 :
1264 1488 : fd_alloc_block_set_t free_blocks = superblock->free_blocks;
1265 :
1266 1488 : ulong msb = fd_ulong_shift_right( free_blocks, (int)block_cnt ); /* Note: block_cnt==64 possible */
1267 1488 : if( FD_UNLIKELY( msb ) ) ctr[0]++;
1268 1488 : TRAP( fprintf( stream, "free_blocks 0x%lx (%s)\n", free_blocks, msb==0UL ? "good" : "bad" ) );
1269 :
1270 : /* For each block */
1271 :
1272 41337 : for( ulong block_idx=0UL; block_idx<block_cnt; block_idx++ ) {
1273 39849 : ulong gaddr_lo = superblock_gaddr + sizeof(fd_alloc_superblock_t) + block_idx*block_footprint;
1274 39849 : ulong gaddr_hi = gaddr_lo + block_footprint;
1275 :
1276 39849 : if( fd_alloc_block_set_test( free_blocks, block_idx ) ) { /* Free block */
1277 :
1278 : //TRAP( fprintf( stream, "\t\t\tblock %2lu: gaddr %s:%lu-%s:%lu, malloc_est -, align_est -, sz_est - (free)\n",
1279 : // block_idx, wksp->name, gaddr_lo, wksp->name, gaddr_hi-1UL ) );
1280 :
1281 39111 : } else { /* Used block */
1282 :
1283 : /* Search the partition for a plausible fd_alloc_hdr_t. This
1284 : process nearly identical to the one described for large
1285 : allocations below. */
1286 :
1287 6282 : for( ulong align_est = 1UL << fd_ulong_find_msb( block_footprint - sizeof(fd_alloc_hdr_t) );;) {
1288 6282 : ulong gaddr_est = fd_ulong_align_up( gaddr_lo + sizeof(fd_alloc_hdr_t), align_est );
1289 6282 : uchar * laddr_est = (uchar *)fd_wksp_laddr_fast( wksp, gaddr_est );
1290 6282 : fd_alloc_hdr_t hdr = FD_LOAD( fd_alloc_hdr_t, laddr_est - sizeof(fd_alloc_hdr_t) );
1291 :
1292 6282 : fd_msan_unpoison( &hdr, sizeof( hdr ) );
1293 6282 : if( fd_alloc_hdr_sizeclass ( hdr ) ==sizeclass &&
1294 6282 : fd_alloc_hdr_block_idx ( hdr ) ==block_idx &&
1295 6282 : fd_alloc_hdr_superblock( hdr, laddr_est )==superblock ) {
1296 738 : ulong sz_est = block_footprint - sizeof(fd_alloc_hdr_t) - align_est + 1UL;
1297 738 : TRAP( fprintf( stream, "\t\t\tblock %2lu: gaddr %s:%lu-%s:%lu, malloc_est %s:%lu, align_est %lu, sz_est %lu\n",
1298 738 : block_idx, wksp->name, gaddr_lo, wksp->name, gaddr_hi-1UL, wksp->name, gaddr_est, align_est, sz_est ) );
1299 738 : ctr[1]++;
1300 738 : break;
1301 738 : }
1302 5544 : fd_msan_poison( &hdr, sizeof( hdr ) );
1303 :
1304 5544 : align_est >>= 1;
1305 5544 : if( FD_UNLIKELY( !align_est ) ) {
1306 0 : TRAP( fprintf( stream, "\t\t\tblock %2lu: gaddr %s:%lu-%s:%lu, malloc_est -, align est -, sz_est - (bad)\n",
1307 0 : block_idx, wksp->name, gaddr_lo, wksp->name, gaddr_hi-1UL ) );
1308 0 : ctr[0]++;
1309 0 : break;
1310 0 : }
1311 5544 : }
1312 738 : }
1313 39849 : }
1314 :
1315 1488 : return cnt;
1316 1488 : }
1317 :
1318 : /* fd_alloc_fprintf pretty prints to the given stream exhaustive details
1319 : about the current state of the fd_alloc corresponding to the current
1320 : local join. As this function is typically for debugging,
1321 : end-of-program diagnostics, etc, this function assumes there are no
1322 : concurrent operations on the fd_alloc while running. Note also it
1323 : might not be able to find all small allocations and determine precise
1324 : details about allocations in general. It will however be able to
1325 : find all large allocations assuming the user tagged the structure
1326 : properly (and that includes finding all the gigantic superblocks in
1327 : which all individual small allocations are contained). Return
1328 : behavior matches fprintf return behavior (i.e. the number of
1329 : characters printed to stream or a negative error code). */
1330 :
1331 : int
1332 : fd_alloc_fprintf( fd_alloc_t * join,
1333 12 : FILE * stream ) {
1334 12 : if( FD_UNLIKELY( !stream ) ) return 0; /* NULL stream, can't print anything */
1335 :
1336 12 : int cnt = 0;
1337 :
1338 12 : ulong ctr[6];
1339 12 : ctr[0] = 0UL; /* errors detected */
1340 12 : ctr[1] = 0UL; /* small alloc found */
1341 12 : ctr[2] = 0UL; /* wksp partitions used */
1342 12 : ctr[3] = 0UL; /* wksp bytes used */
1343 12 : ctr[4] = 0UL; /* wksp partitions used for large alloc */
1344 12 : ctr[5] = 0UL; /* wksp bytes used for large alloc */
1345 :
1346 12 : fd_alloc_t * alloc = fd_alloc_private_join_alloc( join );
1347 12 : ulong cgroup_hint = fd_alloc_join_cgroup_hint ( join );
1348 :
1349 12 : if( FD_UNLIKELY( !alloc ) ) { /* NULL join passed */
1350 :
1351 0 : TRAP( fprintf( stream, "alloc: gaddr -, join_cgroup_hint %lu, magic 0x0 (bad)\n", cgroup_hint ) );
1352 0 : ctr[0]++;
1353 :
1354 12 : } else { /* Normal join */
1355 :
1356 : /* Count the space used by alloc metadata. */
1357 :
1358 12 : ctr[2] += 1UL;
1359 12 : ctr[3] += FD_ALLOC_FOOTPRINT;
1360 :
1361 12 : fd_wksp_t * wksp = fd_alloc_private_wksp( alloc );
1362 :
1363 : /* Print the summary header */
1364 :
1365 12 : TRAP( fprintf( stream, "alloc: gaddr %s:%lu, join_cgroup_hint %lu, magic 0x%lx (%s)\n",
1366 12 : wksp->name, fd_wksp_gaddr_fast( wksp, alloc ), cgroup_hint,
1367 12 : alloc->magic, alloc->magic==FD_ALLOC_MAGIC ? "good" : "bad" ) );
1368 12 : if( FD_UNLIKELY( alloc->magic!=FD_ALLOC_MAGIC ) ) ctr[0]++;
1369 :
1370 : /* Print known details about each sizeclass */
1371 :
1372 12 : ulong block_footprint = 0UL;
1373 1524 : for( ulong sizeclass=0UL; sizeclass<FD_ALLOC_SIZECLASS_CNT; sizeclass++ ) {
1374 1512 : ulong block_footprint_prev = block_footprint;
1375 1512 : /**/ block_footprint = (ulong)fd_alloc_sizeclass_cfg[ sizeclass ].block_footprint;
1376 :
1377 1512 : ulong superblock_footprint = (ulong)fd_alloc_sizeclass_cfg[ sizeclass ].superblock_footprint;
1378 1512 : ulong block_cnt = (ulong)fd_alloc_sizeclass_cfg[ sizeclass ].block_cnt;
1379 1512 : ulong cgroup_cnt = (ulong)fd_alloc_sizeclass_cfg[ sizeclass ].cgroup_mask + 1UL;
1380 :
1381 1512 : fd_alloc_vgaddr_t inactive_stack = alloc->inactive_stack[ sizeclass ];
1382 :
1383 1512 : ulong inactive_stack_ver = (ulong)fd_alloc_vgaddr_ver( inactive_stack );
1384 1512 : ulong inactive_stack_gaddr = (ulong)fd_alloc_vgaddr_off( inactive_stack );
1385 :
1386 : /* Omit sizeclasses that have no superblocks in circulation */
1387 :
1388 1512 : int do_print = !!inactive_stack_gaddr;
1389 1512 : if( !do_print ) {
1390 2076 : for( ulong cgroup_idx=0UL; cgroup_idx<cgroup_cnt; cgroup_idx++ ) {
1391 2040 : if( alloc->active_slot[ sizeclass + FD_ALLOC_SIZECLASS_CNT*cgroup_idx ] ) {
1392 1464 : do_print = 1;
1393 1464 : break;
1394 1464 : }
1395 2040 : }
1396 1500 : if( !do_print ) continue;
1397 1500 : }
1398 :
1399 : /* Print size class header */
1400 :
1401 1476 : TRAP( fprintf( stream,
1402 1476 : "\tsizeclass %lu: superblock_footprint %lu, block_footprint %lu-%lu, block_cnt %lu, cgroup_cnt %lu\n",
1403 1476 : sizeclass, superblock_footprint, block_footprint_prev+1UL, block_footprint, block_cnt, cgroup_cnt ) );
1404 :
1405 : /* Print inactive stack top */
1406 :
1407 1476 : TRAP( fprintf( stream, "\t\tinactive_stack: gaddr %s:%lu, version %lu\n",
1408 1476 : wksp->name, inactive_stack_gaddr, inactive_stack_ver ) );
1409 :
1410 : /* Print active superblock details */
1411 :
1412 1476 : ulong superblock_gaddr;
1413 :
1414 25092 : for( ulong cgroup_idx=0UL; cgroup_idx<cgroup_cnt; cgroup_idx++ ) {
1415 23616 : superblock_gaddr = alloc->active_slot[ sizeclass + FD_ALLOC_SIZECLASS_CNT*cgroup_idx ];
1416 23616 : if( !superblock_gaddr ) {
1417 : //TRAP( fprintf( stream, "\t\tcgroup 2lu active superblock -, next -\n", cgroup_idx ) );
1418 22143 : continue;
1419 22143 : }
1420 1473 : ulong next_gaddr = ((fd_alloc_superblock_t *)fd_wksp_laddr_fast( wksp, superblock_gaddr))->next_gaddr;
1421 1473 : TRAP( fprintf( stream, "\t\tsuperblock: cgroup_idx %lu, gaddr %s:%lu, next %s:%lu (ignored), ",
1422 1473 : cgroup_idx, wksp->name, superblock_gaddr, wksp->name, next_gaddr ) );
1423 1473 : TRAP( fd_alloc_superblock_fprintf( wksp, superblock_gaddr, sizeclass, block_cnt, block_footprint, stream, ctr ) );
1424 1473 : }
1425 :
1426 : /* Print inactive superblock details */
1427 :
1428 1476 : superblock_gaddr = inactive_stack_gaddr;
1429 1491 : while( superblock_gaddr ) {
1430 15 : ulong next_gaddr = ((fd_alloc_superblock_t *)fd_wksp_laddr_fast( wksp, superblock_gaddr))->next_gaddr;
1431 15 : TRAP( fprintf( stream, "\t\tsuperblock: cgroup_idx -, gaddr %s:%lu, next %s:%lu, ",
1432 15 : wksp->name, superblock_gaddr, wksp->name, next_gaddr ) );
1433 15 : TRAP( fd_alloc_superblock_fprintf( wksp, superblock_gaddr, sizeclass, block_cnt, block_footprint, stream, ctr ) );
1434 15 : superblock_gaddr = next_gaddr;
1435 15 : }
1436 1476 : }
1437 :
1438 : /* Scan the wksp partition table for partitions that match this
1439 : allocation tag. Like the is_empty diagnostic, we do this in a
1440 : brute force way that is not algo efficient to avoid taking a
1441 : lock. */
1442 :
1443 12 : ulong wksp_lo = wksp->gaddr_lo;
1444 12 : ulong wksp_hi = wksp->gaddr_hi;
1445 :
1446 12 : ulong alloc_lo = fd_wksp_gaddr_fast( wksp, alloc );
1447 12 : ulong alloc_hi = alloc_lo + FD_ALLOC_FOOTPRINT;
1448 12 : ulong alloc_tag = alloc->tag;
1449 :
1450 12 : ulong part_max = wksp->part_max;
1451 12 : fd_wksp_private_pinfo_t * pinfo = fd_wksp_private_pinfo( wksp );
1452 :
1453 12 : ulong i;
1454 48 : for( i=0UL; i<part_max; i++ ) {
1455 48 : if( pinfo[ i ].tag!=alloc_tag ) continue; /* skip ones that don't match */
1456 12 : ulong gaddr_lo = pinfo[ i ].gaddr_lo;
1457 12 : ulong gaddr_hi = pinfo[ i ].gaddr_hi;
1458 12 : if( FD_UNLIKELY( (wksp_lo<=gaddr_lo) & (gaddr_lo<gaddr_hi) & (gaddr_hi<=wksp_hi) ) ) break; /* malformed */
1459 :
1460 : /* If the user used the same tag for both the alloc metadata and the
1461 : alloc allocations, skip the metadata partition */
1462 :
1463 0 : if( FD_UNLIKELY( (gaddr_lo<=alloc_lo) & (alloc_hi<=gaddr_lo) ) ) continue; /* skip partition containing metadata */
1464 :
1465 0 : ulong part_footprint = gaddr_hi - gaddr_lo;
1466 :
1467 0 : if( FD_UNLIKELY( part_footprint<=sizeof(fd_alloc_hdr_t) ) ) continue; /* skip obviously not an allocation */
1468 :
1469 : /* Search the partition for a plausible fd_alloc_hdr_t. There
1470 : will be at least one if the partition isn't bad. We scan
1471 : potential alignments in reverse order such that noise in the
1472 : alignment padding from older and less aligned large allocs will
1473 : not trigger the detection logic. It is still possible for this
1474 : logic to spuriously fire if the user just happened to have some
1475 : data that looked like a suitable header (hence these are
1476 : estimates). The estimates could be improved if we clear zero
1477 : padding before the headers as noted above at a greater time
1478 : overhead in fd_alloc and scanned alignments forward. Once we
1479 : have a plausible location and alignment, we can compute bounds
1480 : to how large a size was used. We use the upper bound the size
1481 : estimate for simplicity (it would take a lot more space and
1482 : time overhead in normal operation to track this explicitly). */
1483 :
1484 0 : for( ulong align_est = 1UL << fd_ulong_find_msb( part_footprint-sizeof(fd_alloc_hdr_t) );;) {
1485 :
1486 : /* Look at a potential header location */
1487 :
1488 0 : ulong gaddr_est = fd_ulong_align_up( gaddr_lo + sizeof(fd_alloc_hdr_t), align_est );
1489 0 : uchar * laddr_est = (uchar *)fd_wksp_laddr_fast( wksp, gaddr_est );
1490 0 : fd_alloc_hdr_t hdr = FD_LOAD( fd_alloc_hdr_t, laddr_est - sizeof(fd_alloc_hdr_t) );
1491 :
1492 : /* If it matches what a header at this location should be,
1493 : print out the estimated allocation details. */
1494 :
1495 0 : if( fd_alloc_hdr_is_large( hdr ) ) {
1496 0 : int is_superblock = fd_alloc_hdr_large_is_superblock( hdr );
1497 :
1498 0 : ulong sz_est = part_footprint - sizeof(fd_alloc_hdr_t) - align_est + 1UL;
1499 0 : TRAP( fprintf( stream, "\tlarge: gaddr %s:%lu-%s:%lu, malloc_est %s:%lu, align_est %lu, sz_est %lu %s\n",
1500 0 : wksp->name, gaddr_lo, wksp->name, gaddr_hi-1UL, wksp->name, gaddr_est, align_est, sz_est,
1501 0 : is_superblock ? "(superblock)" : "(large)" ) );
1502 0 : ctr[2]++;
1503 0 : ctr[3] += part_footprint;
1504 0 : ctr[4] += fd_ulong_if( is_superblock, 0UL, 1UL );
1505 0 : ctr[5] += fd_ulong_if( is_superblock, 0UL, part_footprint );
1506 :
1507 0 : break;
1508 0 : }
1509 :
1510 : /* Nope ... try the next. If no more potential locations, the
1511 : partition is corrupt. */
1512 :
1513 0 : align_est >>= 1;
1514 0 : if( FD_UNLIKELY( !align_est ) ) {
1515 0 : TRAP( fprintf( stream, "\tlarge: gaddr %s:%lu-%s:%lu, malloc_est -, align_est -, sz_est - (bad)\n",
1516 0 : wksp->name, gaddr_lo, wksp->name, gaddr_hi-1UL ) );
1517 0 : ctr[0]++;
1518 0 : break;
1519 0 : }
1520 0 : }
1521 0 : }
1522 12 : }
1523 :
1524 : /* Print summary statistics */
1525 :
1526 12 : TRAP( fprintf( stream,
1527 12 : "\terrors detected %21lu\n"
1528 12 : "\tsmall alloc found %21lu\n"
1529 12 : "\twksp part cnt %21lu\n"
1530 12 : "\twksp used %21lu\n"
1531 12 : "\tlarge alloc cnt %21lu\n"
1532 12 : "\tlarge alloc wksp used %21lu\n",
1533 12 : ctr[0], ctr[1], ctr[2], ctr[3], ctr[4], ctr[5] ) );
1534 :
1535 12 : return cnt;
1536 12 : }
1537 :
1538 : /* Virtual function table
1539 : TODO type pun functions instead of using virtual wrappers? */
1540 :
1541 : static void *
1542 : fd_alloc_malloc_virtual( void * self,
1543 : ulong align,
1544 0 : ulong sz ) {
1545 0 : return fd_alloc_malloc( (fd_alloc_t *)self, align, sz );
1546 0 : }
1547 :
1548 : static void
1549 : fd_alloc_free_virtual( void * self,
1550 0 : void * addr ) {
1551 0 : fd_alloc_free( (fd_alloc_t *)self, addr );
1552 0 : }
1553 :
1554 : const fd_valloc_vtable_t
1555 : fd_alloc_vtable = {
1556 : .malloc = fd_alloc_malloc_virtual,
1557 : .free = fd_alloc_free_virtual
1558 : };
1559 :
1560 : #undef TRAP
|
