Line data Source code
1 : #include "fd_groove_data.h"
2 :
3 : /* fd_groove_data_private_active_displace lockfree atomically sets the
4 : active superblock for (szc,cgroup) to the superblock at offset
5 : superblock_off and returns the offset of the previously active
6 : superblock. Offsets are relative to volume0.
7 :
8 : Assumes active_slot points in the caller's address space to the
9 : active superblock offset for (szc,cgroup). If superblock_off is
10 : non-zero, further assumes the input superblock is for sizeclass szc,
11 : has at least one free block and is not in circulation (i.e. neither
12 : in any active slot nor on any inactive stack such that nobody can
13 : concurrently allocate from it).
14 :
15 : If this returns zero, there was no active superblock for (szc,cgroup)
16 : just before it was set to the input superblock.
17 :
18 : If this returns non-zero, the output superblock was the previously
19 : active superblock. The output superblock will have at least one free
20 : block (and possibly growing over time to all blocks free due to
21 : concurrent frees) and will not be in circulation.
22 :
23 : If superblock_off is non-zero, the input superblock will be in
24 : circulation as the active superblock for (szc,cgroup) on return.
25 :
26 : If superblock_off is zero, there will be no active superblock for
27 : (szc,cgroup) on return.
28 :
29 : This is a compiler fence. */
30 :
31 : static inline ulong
32 : fd_groove_data_private_active_displace( ulong volatile * _active_slot,
33 : fd_groove_volume_t * volume0,
34 3242331 : ulong superblock_off ) {
35 3242331 : (void)volume0;
36 3242331 : FD_COMPILER_MFENCE();
37 3242331 : # if FD_HAS_ATOMIC
38 3242331 : superblock_off = FD_ATOMIC_XCHG( _active_slot, superblock_off );
39 : # else
40 : ulong old = *_active_slot;
41 : *_active_slot = superblock_off;
42 : superblock_off = old;
43 : # endif
44 3242331 : FD_COMPILER_MFENCE();
45 3242331 : return superblock_off;
46 3242331 : }
47 :
48 : /* fd_groove_data_private_inactive_push does a lockfree atomic push of
49 : the superblock at superblock_off relative to volume0 onto the given
50 : inactive stack. Assumes all inputs are valid, the inactive stack and
51 : superblock have the same sizeclass, the superblock is not in
52 : circulation, and superblock contains at least one free block. On
53 : return, superblock will be the top of the inactive stack. This is a
54 : compiler fence. */
55 :
56 : static inline void
57 : fd_groove_data_private_inactive_push( ulong volatile * _inactive_stack,
58 : fd_groove_volume_t * volume0,
59 1020489 : ulong superblock_off ) {
60 1020489 : FD_COMPILER_MFENCE();
61 :
62 1020489 : fd_groove_data_hdr_t * superblock = (fd_groove_data_hdr_t *)(((ulong)volume0) + superblock_off);
63 :
64 1020489 : for(;;) {
65 1020489 : ulong ver_off = *_inactive_stack;
66 :
67 1020489 : ulong ver = ver_off & (FD_GROOVE_BLOCK_FOOTPRINT-1UL);
68 1020489 : ulong next_off = ver_off & ~(FD_GROOVE_BLOCK_FOOTPRINT-1UL);
69 :
70 1020489 : superblock->info = next_off;
71 :
72 1020489 : ulong next_ver = (ver+1UL) & (FD_GROOVE_BLOCK_FOOTPRINT-1UL);
73 :
74 1020489 : # if FD_HAS_ATOMIC
75 1020489 : ulong old = FD_ATOMIC_CAS( _inactive_stack, ver_off, next_ver | superblock_off );
76 : # else
77 : ulong old = *_inactive_stack;
78 : *_inactive_stack = fd_ulong_if( old==ver_off, next_ver | superblock_off, old );
79 : # endif
80 :
81 1020489 : if( FD_LIKELY( old==ver_off ) ) break;
82 :
83 0 : FD_SPIN_PAUSE();
84 0 : }
85 :
86 1020489 : FD_COMPILER_MFENCE();
87 1020489 : }
88 :
89 : /* fd_groove_data_private_inactive_pop does a lockfree atomic pop of the
90 : given inactive stack. Assumes all inputs are valid. Returns the
91 : offset relative to volume0 of the superblock. The superblock will be
92 : for the same sizeclass as the inactive stack, will not be in
93 : circulation and will have at least 1 block free. If the stack was
94 : empty when observed, returns 0. This is a compiler fence. */
95 :
96 : static inline ulong
97 : fd_groove_data_private_inactive_pop( ulong volatile * _inactive_stack,
98 1028541 : fd_groove_volume_t * volume0 ) {
99 :
100 1028541 : ulong off;
101 :
102 1028541 : FD_COMPILER_MFENCE();
103 :
104 1028541 : for(;;) {
105 1028541 : ulong ver_off = *_inactive_stack;
106 :
107 1028541 : ulong ver = ver_off & (FD_GROOVE_BLOCK_FOOTPRINT-1UL);
108 1028541 : /**/ off = ver_off & ~(FD_GROOVE_BLOCK_FOOTPRINT-1UL);
109 :
110 1028541 : if( FD_UNLIKELY( !off ) ) break;
111 :
112 1013592 : fd_groove_data_hdr_t * superblock = (fd_groove_data_hdr_t *)(((ulong)volume0) + off);
113 :
114 1013592 : ulong next_ver = (ver+1UL) & (FD_GROOVE_BLOCK_FOOTPRINT-1UL);
115 1013592 : ulong next_off = superblock->info;
116 :
117 1013592 : # if FD_HAS_ATOMIC
118 1013592 : ulong old = FD_ATOMIC_CAS( _inactive_stack, ver_off, next_ver | next_off );
119 : # else
120 : ulong old = *_inactive_stack;
121 : *_inactive_stack = fd_ulong_if( old==ver_off, next_ver | next_off, old );
122 : # endif
123 :
124 1013592 : if( FD_LIKELY( old==ver_off ) ) break;
125 :
126 0 : FD_SPIN_PAUSE();
127 0 : }
128 :
129 1028541 : FD_COMPILER_MFENCE();
130 :
131 1028541 : return off;
132 1028541 : }
133 :
134 : void *
135 9 : fd_groove_data_new( void * shmem ) {
136 9 : fd_groove_data_shmem_t * shdata = (fd_groove_data_shmem_t *)shmem;
137 :
138 9 : if( FD_UNLIKELY( !shdata ) ) {
139 3 : FD_LOG_WARNING(( "NULL shmem" ));
140 3 : return NULL;
141 3 : }
142 :
143 6 : if( FD_UNLIKELY( !fd_ulong_is_aligned( (ulong)shdata, fd_groove_data_align() ) ) ) {
144 3 : FD_LOG_WARNING(( "misaligned shmem" ));
145 3 : return NULL;
146 3 : }
147 :
148 3 : ulong footprint = fd_groove_data_footprint();
149 :
150 3 : if( FD_UNLIKELY( !footprint ) ) { /* currently not possible */
151 0 : FD_LOG_WARNING(( "bad configuration" ));
152 0 : return NULL;
153 0 : }
154 :
155 3 : memset( shdata, 0, footprint );
156 :
157 3 : if( FD_UNLIKELY( !fd_groove_volume_pool_new( shdata->volume_pool ) ) ) return NULL; /* logs details (currently not possible) */
158 :
159 3 : FD_COMPILER_MFENCE();
160 3 : shdata->magic = FD_GROOVE_DATA_MAGIC;
161 3 : FD_COMPILER_MFENCE();
162 :
163 3 : return shmem;
164 3 : }
165 :
166 : fd_groove_data_t *
167 : fd_groove_data_join( void * ljoin,
168 : void * shdata,
169 : void * volume0,
170 : ulong volume_max,
171 30 : ulong cgroup_hint ) {
172 30 : volume_max = fd_ulong_if( !!volume_max, volume_max, fd_groove_volume_pool_ele_max_max() );
173 :
174 30 : fd_groove_data_t * join = (fd_groove_data_t *)ljoin;
175 30 : fd_groove_data_shmem_t * data = (fd_groove_data_shmem_t *)shdata;
176 :
177 30 : if( FD_UNLIKELY( !join ) ) {
178 3 : FD_LOG_WARNING(( "NULL ljoin" ));
179 3 : return NULL;
180 3 : }
181 :
182 27 : if( FD_UNLIKELY( !fd_ulong_is_aligned( (ulong)join, alignof(fd_groove_data_t) ) ) ) {
183 3 : FD_LOG_WARNING(( "misaligned ljoin" ));
184 3 : return NULL;
185 3 : }
186 :
187 24 : if( FD_UNLIKELY( !data ) ) {
188 3 : FD_LOG_WARNING(( "NULL shdata" ));
189 3 : return NULL;
190 3 : }
191 :
192 21 : if( FD_UNLIKELY( !fd_ulong_is_aligned( (ulong)data, fd_groove_data_align() ) ) ) {
193 3 : FD_LOG_WARNING(( "misaligned shdata" ));
194 3 : return NULL;
195 3 : }
196 :
197 18 : if( FD_UNLIKELY( data->magic!=FD_GROOVE_DATA_MAGIC ) ) {
198 3 : FD_LOG_WARNING(( "bad magic" ));
199 3 : return NULL;
200 3 : }
201 :
202 15 : if( FD_UNLIKELY( !volume0 ) ) {
203 3 : FD_LOG_WARNING(( "NULL volume0" ));
204 3 : return NULL;
205 3 : }
206 :
207 12 : if( FD_UNLIKELY( !fd_ulong_is_aligned( (ulong)volume0, alignof(fd_groove_volume_t) ) ) ) {
208 3 : FD_LOG_WARNING(( "misaligned volume0" ));
209 3 : return NULL;
210 3 : }
211 :
212 9 : if( FD_UNLIKELY( !fd_groove_volume_pool_join( join->volume_pool, data->volume_pool, volume0, volume_max ) ) ) /* logs details */
213 3 : return NULL;
214 :
215 6 : join->active_slot = data->active_slot;
216 6 : join->inactive_stack = data->inactive_stack;
217 6 : join->cgroup_hint = cgroup_hint;
218 :
219 6 : return join;
220 9 : }
221 :
222 : void *
223 9 : fd_groove_data_leave( fd_groove_data_t * join ) {
224 9 : if( FD_UNLIKELY( !join ) ) {
225 3 : FD_LOG_WARNING(( "NULL join" ));
226 3 : return NULL;
227 3 : }
228 :
229 6 : if( FD_UNLIKELY( !fd_groove_volume_pool_leave( join->volume_pool ) ) ) { /* currently not possible */
230 0 : FD_LOG_WARNING(( "fd_groove_volume_pool_leave failed" ));
231 0 : return NULL;
232 0 : }
233 :
234 6 : return join;
235 6 : }
236 :
237 : void *
238 12 : fd_groove_data_delete( void * shdata ) {
239 12 : fd_groove_data_shmem_t * data = (fd_groove_data_shmem_t *)shdata;
240 :
241 12 : if( FD_UNLIKELY( !data ) ) {
242 3 : FD_LOG_WARNING(( "NULL shdata" ));
243 3 : return NULL;
244 3 : }
245 :
246 9 : if( FD_UNLIKELY( !fd_ulong_is_aligned( (ulong)data, fd_groove_data_align() ) ) ) {
247 3 : FD_LOG_WARNING(( "misaligned shdata" ));
248 3 : return NULL;
249 3 : }
250 :
251 6 : if( FD_UNLIKELY( data->magic!=FD_GROOVE_DATA_MAGIC ) ) {
252 3 : FD_LOG_WARNING(( "bad magic" ));
253 3 : return NULL;
254 3 : }
255 :
256 3 : FD_COMPILER_MFENCE();
257 3 : data->magic = 0UL;
258 3 : FD_COMPILER_MFENCE();
259 :
260 3 : return shdata;
261 6 : }
262 :
263 : /* FIXME: ideally would update the free_objs bit field after writing
264 : an alloc / superblock data hdr to give non-invasive concurrent
265 : real-time inspection / diagnostics a strong guarantee all objects
266 : marked as allocated have valid data hdrs. */
267 :
268 : static int
269 : fd_groove_data_private_alloc_obj( fd_groove_data_t * data,
270 : ulong obj_szc,
271 : ulong * _obj_off,
272 2121675 : ulong * _obj_idx ) {
273 :
274 2121675 : fd_groove_volume_t * _volume0 = (fd_groove_volume_t *)fd_groove_data_volume0( data );
275 :
276 2121675 : # if FD_GROOVE_PARANOID
277 2121675 : fd_groove_volume_t * _volume1 = (fd_groove_volume_t *)fd_groove_data_volume1( data );
278 2121675 : # endif
279 :
280 2121675 : ulong obj_cnt = (ulong)fd_groove_data_szc_cfg[ obj_szc ].obj_cnt;
281 2121675 : ulong obj_footprint = (ulong)fd_groove_data_szc_cfg[ obj_szc ].obj_footprint;
282 2121675 : ulong cgroup_mask = (ulong)fd_groove_data_szc_cfg[ obj_szc ].cgroup_mask;
283 2121675 : ulong parent_szc = (ulong)fd_groove_data_szc_cfg[ obj_szc ].parent_szc;
284 :
285 : /* At this point, we are allocating an object from a sizeclass obj_szc
286 : superblock. Get the locations of the active slot and inactive
287 : stack for this sizeclass and our concurrency group. */
288 :
289 2121675 : ulong cgroup = data->cgroup_hint & cgroup_mask;
290 :
291 2121675 : ulong volatile * _active_slot = data->active_slot + obj_szc + FD_GROOVE_DATA_SZC_CNT*cgroup;
292 2121675 : ulong volatile * _inactive_stack = data->inactive_stack + obj_szc;
293 :
294 2121675 : ulong superblock_off;
295 :
296 : /* Try to get exclusive access to the active superblock. Note that
297 : active superblocks have at least one free obj. We do this
298 : test-and-test-and-set style to avoid atomic operations if there is
299 : no current active_superblock for this cgroup. */
300 :
301 2121675 : FD_COMPILER_MFENCE();
302 2121675 : superblock_off = *_active_slot;
303 2121675 : FD_COMPILER_MFENCE();
304 :
305 2121675 : if( FD_LIKELY( superblock_off ) ) superblock_off = fd_groove_data_private_active_displace( _active_slot, _volume0, 0UL );
306 :
307 2121675 : if( FD_UNLIKELY( !superblock_off ) ) {
308 :
309 : /* At this point, there was no active superblock for our cgroup when
310 : we observed it. Try to pop the inactive superblock stack for
311 : this sizeclass instead. Note that inactive superblocks also have
312 : at least one free obj. */
313 :
314 996180 : superblock_off = fd_groove_data_private_inactive_pop( _inactive_stack, _volume0 );
315 :
316 996180 : if( FD_UNLIKELY( !superblock_off ) ) {
317 :
318 : /* At this point, there were no inactive superblocks for this
319 : sizeclass when we observed the inactive stack. Try to create a
320 : new superblock for this sizeclass */
321 :
322 14376 : ulong parent_idx = 0UL; /* reduce risk of uninitialized variable false positives from code analysis tools */
323 :
324 14376 : if( FD_UNLIKELY( parent_szc==FD_GROOVE_DATA_SZC_CNT ) ) { /* Acquire a volume to use for the new superblock */
325 :
326 6 : fd_groove_volume_t * _volume = fd_groove_volume_pool_acquire( data->volume_pool );
327 6 : if( FD_UNLIKELY( !_volume ) ) return FD_GROOVE_ERR_FULL;
328 :
329 3 : # if FD_GROOVE_PARANOID
330 3 : ulong volume_off = (ulong)_volume - (ulong)_volume0;
331 :
332 3 : if( FD_UNLIKELY( !( (_volume0<=_volume) & (_volume<_volume1) &
333 3 : fd_ulong_is_aligned( volume_off, FD_GROOVE_VOLUME_FOOTPRINT ) ) ) ) {
334 0 : FD_LOG_WARNING(( "volume not at a valid groove data local address" ));
335 0 : return FD_GROOVE_ERR_CORRUPT;
336 0 : }
337 :
338 3 : if( FD_UNLIKELY( !( (_volume->magic ==~FD_GROOVE_VOLUME_MAGIC ) &
339 3 : (_volume->idx*FD_GROOVE_VOLUME_FOOTPRINT==volume_off ) &
340 3 : (_volume->info_sz <=FD_GROOVE_VOLUME_INFO_MAX) ) ) ) {
341 0 : FD_LOG_WARNING(( "unexpected volume header" ));
342 0 : return FD_GROOVE_ERR_CORRUPT;
343 0 : }
344 3 : # endif
345 :
346 3 : FD_COMPILER_MFENCE();
347 3 : _volume->magic = FD_GROOVE_VOLUME_MAGIC; /* mark volume as potentially containing groove data allocations */
348 3 : FD_COMPILER_MFENCE();
349 :
350 : //parent_idx = 0UL; /* See note above about initialization */
351 3 : superblock_off = (ulong)_volume->data - (ulong)_volume0;
352 :
353 14370 : } else { /* Acquire a parent_szc object to use for the new superblock */
354 :
355 14370 : int err = fd_groove_data_private_alloc_obj( data, parent_szc, &superblock_off, &parent_idx ); /* logs details */
356 14370 : if( FD_UNLIKELY( err ) ) return err;
357 :
358 14370 : }
359 :
360 14340 : ulong superblock_align = FD_GROOVE_DATA_HDR_ALIGN;
361 14340 : ulong superblock_sz = FD_GROOVE_BLOCK_FOOTPRINT - FD_GROOVE_DATA_HDR_FOOTPRINT + obj_footprint*obj_cnt;
362 :
363 14340 : fd_groove_data_hdr_t * _superblock_hdr = (fd_groove_data_hdr_t *)(((ulong)_volume0) + superblock_off);
364 :
365 14340 : # if FD_GROOVE_PARANOID
366 14340 : if( FD_UNLIKELY( !( ((ulong)_volume0<(ulong)_superblock_hdr) & ((ulong)_superblock_hdr<(ulong)_volume1) &
367 14340 : fd_ulong_is_aligned( (ulong)_superblock_hdr, FD_GROOVE_BLOCK_ALIGN ) ) ) ) {
368 0 : FD_LOG_WARNING(( "superblock not at a valid groove data local address" ));
369 0 : return FD_GROOVE_ERR_CORRUPT;
370 0 : }
371 14340 : # endif
372 :
373 14340 : *_superblock_hdr = fd_groove_data_hdr( FD_GROOVE_DATA_HDR_TYPE_SUPERBLOCK, parent_idx, obj_szc,
374 14340 : superblock_align, fd_ulong_min( superblock_sz, (1UL<<25)-1UL ), 0UL /* no next */ );
375 14340 : *(ulong *)(_superblock_hdr+1) = (1UL<<obj_cnt)-1UL; /* mark all objects in superblock as free */
376 14340 : }
377 996180 : }
378 :
379 : /* At this point, we have exclusive access to the superblock, there is
380 : at least one free block in it and only we can allocate blocks from
381 : it. (Other threads could free blocks to it concurrently though.)
382 : Allocate a free block. If there were more free blocks, put the
383 : superblock back into circulation as the active superblock for our
384 : cgroup. Otherwise, free will put in back into circulation when the
385 : application frees a block in it. See fd_alloc.c for details. */
386 :
387 2121639 : fd_groove_data_hdr_t * _superblock_hdr = (fd_groove_data_hdr_t *)(((ulong)_volume0) + superblock_off);
388 :
389 2121639 : ulong volatile * _free_objs = (ulong volatile *)(_superblock_hdr+1);
390 :
391 2121639 : # if FD_GROOVE_PARANOID
392 2121639 : if( FD_UNLIKELY( !( ((ulong)_volume0<(ulong)_superblock_hdr) & ((ulong)_superblock_hdr<(ulong)_volume1) &
393 2121639 : fd_ulong_is_aligned( (ulong)_superblock_hdr, FD_GROOVE_BLOCK_ALIGN ) ) ) ) {
394 0 : FD_LOG_WARNING(( "superblock not at a valid groove data local address" ));
395 0 : return FD_GROOVE_ERR_CORRUPT;
396 0 : }
397 :
398 2121639 : fd_groove_data_hdr_t superblock_hdr = *_superblock_hdr;
399 :
400 2121639 : ulong superblock_type = fd_groove_data_hdr_type( superblock_hdr );
401 2121639 : ulong superblock_szc = fd_groove_data_hdr_szc ( superblock_hdr );
402 :
403 2121639 : if( FD_UNLIKELY( !((superblock_type==FD_GROOVE_DATA_HDR_TYPE_SUPERBLOCK) & (superblock_szc==obj_szc)) ) ) {
404 0 : FD_LOG_WARNING(( "unexpected superblock header" ));
405 0 : return FD_GROOVE_ERR_CORRUPT;
406 0 : }
407 2121639 : # endif
408 :
409 2121639 : FD_COMPILER_MFENCE();
410 2121639 : ulong free_objs = *_free_objs;
411 2121639 : FD_COMPILER_MFENCE();
412 :
413 2121639 : # if FD_GROOVE_PARANOID
414 2121639 : if( FD_UNLIKELY( (!free_objs) | (!!fd_ulong_shift_right( free_objs, (int)obj_cnt )) ) ) {
415 0 : FD_LOG_WARNING(( "%s", (!free_objs) ? "full superblock in circulation" : "invalid free_objs bit field" ));
416 0 : return FD_GROOVE_ERR_CORRUPT;
417 0 : }
418 2121639 : # endif
419 :
420 2121639 : ulong obj = fd_ulong_lsb( free_objs );
421 :
422 2121639 : FD_COMPILER_MFENCE();
423 2121639 : # if FD_HAS_ATOMIC
424 2121639 : free_objs = FD_ATOMIC_FETCH_AND_SUB( _free_objs, obj ); /* Marginally better asm than FETCH_AND_AND */
425 : # else
426 : free_objs = *_free_objs;
427 : *_free_objs = free_objs & ~obj;
428 : # endif
429 2121639 : FD_COMPILER_MFENCE();
430 :
431 2121639 : # if FD_GROOVE_PARANOID
432 2121639 : if( FD_UNLIKELY( (!free_objs) | (!!fd_ulong_shift_right( free_objs, (int)obj_cnt )) ) ) {
433 0 : FD_LOG_WARNING(( "%s", (!free_objs) ? "full superblock in circulation" : "invalid free_objs bit field" ));
434 0 : return FD_GROOVE_ERR_CORRUPT;
435 0 : }
436 2121639 : # endif
437 :
438 2121639 : if( FD_LIKELY( free_objs!=obj ) ) {
439 218265 : ulong displaced_superblock_off = fd_groove_data_private_active_displace( _active_slot, _volume0, superblock_off );
440 218265 : if( FD_UNLIKELY( displaced_superblock_off ) )
441 0 : fd_groove_data_private_inactive_push( _inactive_stack, _volume0, displaced_superblock_off );
442 218265 : }
443 :
444 : /* At this point, we've allocated the object */
445 :
446 2121639 : ulong obj_idx = (ulong)fd_ulong_find_lsb( obj );
447 :
448 2121639 : *_obj_off = superblock_off + FD_GROOVE_BLOCK_FOOTPRINT + obj_idx*obj_footprint;
449 2121639 : *_obj_idx = obj_idx;
450 2121639 : return FD_GROOVE_SUCCESS;
451 2121639 : }
452 :
453 : void *
454 : fd_groove_data_alloc( fd_groove_data_t * data,
455 : ulong align,
456 : ulong sz,
457 : ulong tag,
458 2107329 : int * _err ) {
459 :
460 2107329 : int stack_err[1];
461 2107329 : if( !_err ) _err = stack_err;
462 :
463 : /* Check input args */
464 :
465 2107329 : if( FD_UNLIKELY( !data ) ) {
466 6 : FD_LOG_WARNING(( "NULL data" ));
467 6 : *_err = FD_GROOVE_ERR_INVAL;
468 6 : return NULL;
469 6 : }
470 :
471 2107323 : align = fd_ulong_if( !!align, align, FD_GROOVE_DATA_ALLOC_ALIGN_DEFAULT );
472 2107323 : if( FD_UNLIKELY( !(fd_ulong_is_pow2( align ) & (align<=FD_GROOVE_DATA_ALLOC_ALIGN_MAX)) ) ) {
473 12 : FD_LOG_WARNING(( "bad align" ));
474 12 : *_err = FD_GROOVE_ERR_INVAL;
475 12 : return NULL;
476 12 : }
477 :
478 2107311 : ulong off_obj = fd_ulong_align_up( FD_GROOVE_DATA_HDR_FOOTPRINT, align );
479 2107311 : ulong footprint = fd_ulong_align_up( off_obj+sz, FD_GROOVE_BLOCK_ALIGN );
480 :
481 2107311 : if( FD_UNLIKELY( !((sz<footprint) & (footprint<=FD_GROOVE_DATA_ALLOC_FOOTPRINT_MAX)) ) ) {
482 6 : FD_LOG_WARNING(( "bad sz/align" ));
483 6 : *_err = FD_GROOVE_ERR_INVAL;
484 6 : return NULL;
485 6 : }
486 :
487 : /* Acquire an object from the tightest suitable sizeclass */
488 :
489 2107305 : ulong obj_szc = fd_groove_data_szc( footprint );
490 :
491 2107305 : ulong obj_off;
492 2107305 : ulong obj_idx;
493 2107305 : int err = fd_groove_data_private_alloc_obj( data, obj_szc, &obj_off, &obj_idx ); /* logs details */
494 2107305 : if( FD_UNLIKELY( err ) ) {
495 3 : *_err = err;
496 3 : return NULL;
497 3 : }
498 :
499 : /* Carve an allocation into it. */
500 :
501 2107302 : fd_groove_data_hdr_t * obj_hdr = (fd_groove_data_hdr_t *)((ulong)fd_groove_volume_pool_shele( data->volume_pool ) + obj_off);
502 :
503 2107302 : *obj_hdr = fd_groove_data_hdr( FD_GROOVE_DATA_HDR_TYPE_ALLOC, obj_idx, obj_szc, align, sz, tag );
504 :
505 2107302 : *_err = FD_GROOVE_SUCCESS;
506 2107302 : return (void *)((ulong)obj_hdr + off_obj);
507 2107305 : }
508 :
509 : int
510 : fd_groove_data_private_free( fd_groove_data_t * data,
511 : void * _obj,
512 2109834 : ulong exp_type ) {
513 :
514 : # if !FD_GROOVE_PARANOID
515 : (void)exp_type; /* Suppress unused warning if running without paranoia */
516 : # endif
517 :
518 2109834 : if( FD_UNLIKELY( !data ) ) {
519 3 : FD_LOG_WARNING(( "NULL data" ));
520 3 : return FD_GROOVE_ERR_INVAL;
521 3 : }
522 :
523 2109831 : if( FD_UNLIKELY( !_obj ) ) return FD_GROOVE_ERR_INVAL;
524 :
525 2109828 : fd_groove_data_hdr_t * _obj_hdr = fd_groove_data_object_hdr( _obj );
526 :
527 2109828 : fd_groove_volume_t * _volume0 = (fd_groove_volume_t *)fd_groove_data_volume0( data );
528 :
529 2109828 : # if FD_GROOVE_PARANOID
530 2109828 : fd_groove_volume_t * _volume1 = (fd_groove_volume_t *)fd_groove_data_volume1( data );
531 2109828 : if( FD_UNLIKELY( !( ((ulong)_volume0<=(ulong)_obj_hdr ) &
532 2109828 : ((ulong)_obj_hdr< (ulong)_volume1 ) &
533 2109828 : (fd_ulong_is_aligned( (ulong)_obj_hdr, FD_GROOVE_BLOCK_ALIGN )) ) ) ) {
534 0 : FD_LOG_WARNING(( "object not at a valid groove data local address" ));
535 0 : return FD_GROOVE_ERR_INVAL;
536 0 : }
537 2109828 : # endif
538 :
539 2109828 : fd_groove_data_hdr_t obj_hdr = *_obj_hdr;
540 :
541 2109828 : ulong obj_type = fd_groove_data_hdr_type( obj_hdr );
542 2109828 : ulong obj_idx = fd_groove_data_hdr_idx ( obj_hdr );
543 2109828 : ulong obj_szc = fd_groove_data_hdr_szc ( obj_hdr );
544 :
545 2109828 : #if FD_GROOVE_PARANOID
546 2109828 : if( FD_UNLIKELY( !((obj_type==exp_type) & (obj_szc<FD_GROOVE_DATA_SZC_CNT)) ) ) {
547 0 : FD_LOG_WARNING(( "object does not appear to be a groove data %s",
548 0 : exp_type==FD_GROOVE_DATA_HDR_TYPE_ALLOC ? "alloc" : "superblock" ));
549 0 : return FD_GROOVE_ERR_INVAL;
550 0 : }
551 2109828 : # endif
552 :
553 2109828 : obj_szc = fd_ulong_if( obj_type==FD_GROOVE_DATA_HDR_TYPE_ALLOC, obj_szc,
554 2109828 : (ulong)fd_groove_data_szc_cfg[ obj_szc ].parent_szc );
555 2109828 : ulong obj_cnt = (ulong)fd_groove_data_szc_cfg[ obj_szc ].obj_cnt;
556 2109828 : # if FD_GROOVE_PARANOID
557 2109828 : ulong obj_footprint = (ulong)fd_groove_data_szc_cfg[ obj_szc ].obj_footprint;
558 :
559 2109828 : ulong req_align = fd_groove_data_hdr_align( obj_hdr );
560 2109828 : ulong req_sz = fd_groove_data_hdr_sz ( obj_hdr );
561 2109828 : ulong req_footprint =
562 2109828 : fd_ulong_align_up( fd_ulong_align_up( FD_GROOVE_DATA_HDR_FOOTPRINT, req_align ) + req_sz, FD_GROOVE_BLOCK_ALIGN );
563 :
564 2109828 : if( FD_UNLIKELY( !( (obj_idx<obj_cnt ) &
565 2109828 : (fd_ulong_is_pow2( req_align ) ) &
566 2109828 : (req_align<=FD_GROOVE_BLOCK_ALIGN) &
567 2109828 : (req_footprint<=obj_footprint ) ) ) ) {
568 0 : FD_LOG_WARNING(( "object does not appear to be a groove data %s",
569 0 : exp_type==FD_GROOVE_DATA_HDR_TYPE_ALLOC ? "alloc" : "superblock" ));
570 0 : return FD_GROOVE_ERR_INVAL;
571 0 : }
572 2109828 : # endif
573 :
574 : /* At this point, we appear to have a valid allocated object. Mark
575 : the object as not valid and then free it.
576 :
577 : Note: marking the object as dead is optional. It is mostly a hint
578 : for diagnostics and for handholding as groove data users shouldn't
579 : be calling free on it again and alloc doesn't care about the state
580 : unallocated object memory. Most useful, marking the object as dead
581 : can detect double free scenarios.
582 :
583 : The below implementation is not robust against _concurrent_ double
584 : frees. Would probably have to use something like ATOMIC_CAS
585 : semantics on the object header bits to insure nobody freed the
586 : object behind our back. And since the free bit field update isn't
587 : atomic with marking the object as dead, would probably need further
588 : to do something like mark the object as freeing then update bit
589 : field and then mark object as dead, etc. */
590 :
591 2109828 : fd_groove_data_hdr_t * _superblock_hdr = fd_groove_data_superblock_hdr( _obj, obj_szc, obj_idx );
592 :
593 2109828 : ulong volatile * _free_objs = (ulong volatile *)(_superblock_hdr+1);
594 :
595 2109828 : ulong free_objs;
596 :
597 2109828 : ulong obj = 1UL << obj_idx;
598 :
599 2109828 : # if FD_GROOVE_PARANOID
600 2109828 : if( FD_UNLIKELY( !( ((ulong)_volume0<(ulong)_superblock_hdr) & ((ulong)_superblock_hdr<(ulong)_obj_hdr) &
601 2109828 : fd_ulong_is_aligned( (ulong)_superblock_hdr, FD_GROOVE_BLOCK_ALIGN ) ) ) ) {
602 0 : FD_LOG_WARNING(( "superblock not at a valid groove data local address" ));
603 0 : return FD_GROOVE_ERR_INVAL;
604 0 : }
605 :
606 2109828 : fd_groove_data_hdr_t superblock_hdr = *_superblock_hdr;
607 :
608 2109828 : ulong superblock_type = fd_groove_data_hdr_type( superblock_hdr );
609 2109828 : ulong superblock_szc = fd_groove_data_hdr_szc ( superblock_hdr );
610 :
611 2109828 : if( FD_UNLIKELY( !((superblock_type==FD_GROOVE_DATA_HDR_TYPE_SUPERBLOCK) & (superblock_szc==obj_szc)) ) ) {
612 0 : FD_LOG_WARNING(( "unexpected superblock header" ));
613 0 : return FD_GROOVE_ERR_INVAL;
614 0 : }
615 :
616 2109828 : FD_COMPILER_MFENCE();
617 2109828 : free_objs = *_free_objs;
618 2109828 : FD_COMPILER_MFENCE();
619 :
620 2109828 : if( FD_UNLIKELY( (free_objs & obj) | fd_ulong_shift_right( free_objs, (int)obj_cnt ) ) ) {
621 0 : FD_LOG_WARNING(( "%s", (free_objs & obj) ? "possible concurrent double free" : "invalid free_objs bit field" ));
622 0 : return FD_GROOVE_ERR_INVAL;
623 0 : }
624 :
625 2109828 : FD_COMPILER_MFENCE();
626 2109828 : _obj_hdr->bits = 0UL; /* sets object type to an invalid value */
627 2109828 : FD_COMPILER_MFENCE();
628 2109828 : # endif
629 :
630 2109828 : FD_COMPILER_MFENCE();
631 2109828 : # if FD_HAS_ATOMIC
632 2109828 : free_objs = FD_ATOMIC_FETCH_AND_ADD( _free_objs, obj ); /* Marginally better asm than FETCH_AND_OR */
633 : # else
634 : free_objs = *_free_objs;
635 : *_free_objs = free_objs | obj;
636 : # endif
637 2109828 : FD_COMPILER_MFENCE();
638 :
639 2109828 : # if FD_GROOVE_PARANOID
640 2109828 : if( FD_UNLIKELY( (free_objs & obj) | fd_ulong_shift_right( free_objs, (int)obj_cnt ) ) ) {
641 0 : FD_LOG_WARNING(( "%s", (free_objs & obj) ? "possible concurrent double free" : "invalid free_objs bit field" ));
642 0 : return FD_GROOVE_ERR_CORRUPT;
643 0 : }
644 2109828 : # endif
645 :
646 : /* At this point, we've freed the object. We might need to get the
647 : object's superblock back into circulation and/or free up excess
648 : empty superblocks for this sizeclass. */
649 :
650 2109828 : ulong free_cnt = (ulong)fd_ulong_popcnt( free_objs );
651 :
652 2109828 : if( FD_UNLIKELY( !free_cnt ) ) {
653 :
654 : /* At this point, the superblock was full before we freed it and
655 : thus not in circulation for use by fd_alloc. We need to get the
656 : superblock back into circulation. There are options for this
657 : with various subtle tradeoffs. See fd_alloc.c for details.
658 : (FIXME: amongst then, consider using allocation cgroup instead of
659 : the groove data instance's cgroup?) */
660 :
661 1898571 : ulong cgroup = fd_groove_data_cgroup_hint( data ) & (ulong)fd_groove_data_szc_cfg[ obj_szc ].cgroup_mask;
662 :
663 1898571 : ulong displaced_superblock_off =
664 1898571 : fd_groove_data_private_active_displace( data->active_slot + obj_szc + FD_GROOVE_DATA_SZC_CNT*cgroup,
665 1898571 : _volume0, (ulong)_superblock_hdr - (ulong)_volume0 );
666 :
667 1898571 : if( FD_UNLIKELY( displaced_superblock_off ) )
668 991227 : fd_groove_data_private_inactive_push( data->inactive_stack + obj_szc, _volume0, displaced_superblock_off );
669 :
670 1898571 : } else if( FD_UNLIKELY( (free_cnt+1UL)==obj_cnt ) ) {
671 :
672 : /* At this point, the superblock was completely empty after we freed
673 : from it, hence it is still in circulation. If there is also a
674 : completely empty superblock on top of the inactive stack, we free
675 : that one for general reuse. This is more subtle than it looks,
676 : see fd_alloc.c for details. */
677 :
678 32361 : ulong volatile * _inactive_stack = data->inactive_stack + obj_szc;
679 :
680 32361 : ulong superblock_off = fd_groove_data_private_inactive_pop( _inactive_stack, _volume0 );
681 :
682 32361 : if( FD_LIKELY( superblock_off ) ) {
683 :
684 31788 : _superblock_hdr = (fd_groove_data_hdr_t *)((ulong)_volume0 + superblock_off);
685 :
686 31788 : _free_objs = (ulong volatile *)(_superblock_hdr+1);
687 :
688 31788 : # if FD_GROOVE_PARANOID
689 31788 : if( FD_UNLIKELY( !( ((ulong)_volume0<(ulong)_superblock_hdr) & ((ulong)_superblock_hdr<(ulong)_volume1) &
690 31788 : fd_ulong_is_aligned( (ulong)_superblock_hdr, FD_GROOVE_BLOCK_ALIGN ) ) ) ) {
691 0 : FD_LOG_WARNING(( "superblock not at a valid groove data local address" ));
692 0 : return FD_GROOVE_ERR_CORRUPT;
693 0 : }
694 :
695 31788 : superblock_type = fd_groove_data_hdr_type( superblock_hdr );
696 31788 : superblock_szc = fd_groove_data_hdr_szc ( superblock_hdr );
697 :
698 31788 : if( FD_UNLIKELY( !((superblock_type==FD_GROOVE_DATA_HDR_TYPE_SUPERBLOCK) & (superblock_szc==obj_szc)) ) ) {
699 0 : FD_LOG_WARNING(( "unexpected superblock header" ));
700 0 : return FD_GROOVE_ERR_CORRUPT;
701 0 : }
702 31788 : # endif
703 :
704 31788 : FD_COMPILER_MFENCE();
705 31788 : free_objs = *_free_objs;
706 31788 : FD_COMPILER_MFENCE();
707 :
708 31788 : # if FD_GROOVE_PARANOID
709 31788 : if( FD_UNLIKELY( fd_ulong_shift_right( free_objs, (int)obj_cnt ) ) ) {
710 0 : FD_LOG_WARNING(( "invalid free_objs bit field" ));
711 0 : return FD_GROOVE_ERR_CORRUPT;
712 0 : }
713 31788 : # endif
714 :
715 31788 : free_cnt = (ulong)fd_ulong_popcnt( free_objs );
716 :
717 31788 : if( FD_LIKELY( free_cnt<obj_cnt ) ) { /* inactive top was not completely empty, return to circulation */
718 :
719 29262 : fd_groove_data_private_inactive_push( _inactive_stack, _volume0, superblock_off );
720 :
721 29262 : } else if( FD_LIKELY( obj_szc<(FD_GROOVE_DATA_SZC_CNT-1UL) ) ) { /* completely empty and should free from parent sb */
722 :
723 2526 : int err = fd_groove_data_private_free( data, _superblock_hdr+1, FD_GROOVE_DATA_HDR_TYPE_SUPERBLOCK ); /* offset the hdr */
724 2526 : if( FD_UNLIKELY( err ) ) {
725 0 : FD_LOG_WARNING(( "superblock free failed (%i-%s)", err, fd_groove_strerror( err ) ));
726 0 : return FD_GROOVE_ERR_CORRUPT;
727 0 : }
728 :
729 2526 : } else { /* completely empty and should free parent volume */
730 :
731 0 : ulong volume_off = superblock_off - FD_GROOVE_BLOCK_FOOTPRINT;
732 :
733 0 : fd_groove_volume_t * _volume = (fd_groove_volume_t *)((ulong)_volume0 + volume_off);
734 :
735 0 : # if FD_GROOVE_PARANOID
736 0 : if( FD_UNLIKELY( !( (_volume0<=_volume) & (_volume<_volume1) &
737 0 : fd_ulong_is_aligned( volume_off, FD_GROOVE_VOLUME_FOOTPRINT ) ) ) ) {
738 0 : FD_LOG_WARNING(( "volume not at a valid groove data local address" ));
739 0 : return FD_GROOVE_ERR_CORRUPT;
740 0 : }
741 :
742 0 : if( FD_UNLIKELY( !( (_volume->magic ==FD_GROOVE_VOLUME_MAGIC ) &
743 0 : (_volume->idx*FD_GROOVE_VOLUME_FOOTPRINT==volume_off ) &
744 0 : (_volume->info_sz <=FD_GROOVE_VOLUME_INFO_MAX) ) ) ) {
745 0 : FD_LOG_WARNING(( "unexpected volume header" ));
746 0 : return FD_GROOVE_ERR_CORRUPT;
747 0 : }
748 0 : # endif
749 :
750 0 : FD_COMPILER_MFENCE();
751 0 : _volume->magic = ~FD_GROOVE_VOLUME_MAGIC; /* mark volume as containing no groove data allocations */
752 0 : FD_COMPILER_MFENCE();
753 :
754 0 : fd_groove_volume_pool_release( data->volume_pool, _volume );
755 :
756 0 : }
757 31788 : }
758 32361 : }
759 :
760 2109828 : return FD_GROOVE_SUCCESS;
761 2109828 : }
762 :
763 619491 : #define TEST(c) do { \
764 619491 : if( FD_UNLIKELY( !(c) ) ) { FD_LOG_WARNING(( "FAIL: %s", #c )); return FD_GROOVE_ERR_CORRUPT; } \
765 619491 : } while(0)
766 :
767 : /* fd_groove_data_private_verify_superblock verifies the location
768 : superblock_off (relative to _volume0) seems to contain a valid
769 : superblock. groove data is located in the caller's address space at
770 : [_volume0,_volume1). exp_szc gives the expected sizeclass for the
771 : superblock. If in_circulation is non-zero, the superblock is known
772 : to be in circulation (i.e. contains at least one free object / is
773 : either any active or an inactive superblock / is available to alloc
774 : for allocation). Assumes _volume0, _volume1, exp_szc and the
775 : sizeclass configuration are valid. */
776 :
777 : static int
778 : fd_groove_data_private_verify_superblock( ulong superblock_off,
779 : ulong exp_szc,
780 : int in_circulation,
781 : int verify_descendents,
782 : fd_groove_volume_t const * _volume0,
783 32169 : fd_groove_volume_t const * _volume1 ) {
784 :
785 : /* Verify superblock_off */
786 :
787 32169 : fd_groove_data_hdr_t const * _superblock_hdr = (fd_groove_data_hdr_t const *)(((ulong)_volume0) + superblock_off);
788 :
789 32169 : TEST( ((ulong)_volume0<(ulong)_superblock_hdr) & ((ulong)_superblock_hdr<(ulong)_volume1) );
790 32169 : TEST( fd_ulong_is_aligned( (ulong)_superblock_hdr, FD_GROOVE_BLOCK_ALIGN ) );
791 :
792 : /* Verify superblock header */
793 :
794 32169 : fd_groove_data_hdr_t hdr = *_superblock_hdr;
795 :
796 32169 : TEST( fd_groove_data_hdr_type( hdr )==FD_GROOVE_DATA_HDR_TYPE_SUPERBLOCK );
797 :
798 32169 : ulong szc = fd_groove_data_hdr_szc( hdr );
799 :
800 32169 : TEST( szc==exp_szc );
801 :
802 32169 : ulong obj_cnt = (ulong)fd_groove_data_szc_cfg[ szc ].obj_cnt;
803 32169 : ulong obj_footprint = (ulong)fd_groove_data_szc_cfg[ szc ].obj_footprint;
804 32169 : ulong parent_szc = (ulong)fd_groove_data_szc_cfg[ szc ].parent_szc;
805 :
806 32169 : ulong parent_obj_idx = fd_groove_data_hdr_idx( hdr );
807 32169 : ulong parent_obj_cnt = (parent_szc<FD_GROOVE_DATA_SZC_CNT) ? (ulong)fd_groove_data_szc_cfg[ parent_szc ].obj_cnt : 1UL;
808 : //ulong parent_obj_footprint = (parent_szc<FD_GROOVE_DATA_SZC_CNT) ? (ulong)fd_groove_data_szc_cfg[ parent_szc ].obj_footprint :
809 : // (FD_GROOVE_VOLUME_DATA_MAX - FD_GROOVE_BLOCK_FOOTPRINT);
810 :
811 32169 : TEST( parent_obj_idx < parent_obj_cnt );
812 :
813 32169 : TEST( fd_groove_data_hdr_align( hdr )==FD_GROOVE_DATA_HDR_ALIGN );
814 32169 : TEST( fd_groove_data_hdr_sz ( hdr )==
815 32169 : fd_ulong_min( FD_GROOVE_BLOCK_FOOTPRINT - FD_GROOVE_DATA_HDR_FOOTPRINT + obj_cnt*obj_footprint, (1UL<<25)-1UL ) );
816 :
817 32169 : ulong free_objs = *(ulong const *)(_superblock_hdr+1);
818 :
819 32169 : TEST( !fd_ulong_shift_right( free_objs, (int)obj_cnt ) ); /* valid free obj bit field */
820 32169 : if( in_circulation ) TEST( !!free_objs ); /* at least 1 free obj for superblocks in circulation */
821 :
822 : /* Verify superblock object headers */
823 :
824 32169 : ulong rem_objs = free_objs ^ fd_ulong_mask_lsb( (int)obj_cnt );
825 76578 : while( rem_objs ) {
826 44409 : ulong _idx = (ulong)fd_ulong_find_lsb( rem_objs );
827 :
828 44409 : ulong child_obj_off = superblock_off + FD_GROOVE_BLOCK_FOOTPRINT + _idx*obj_footprint;
829 :
830 44409 : fd_groove_data_hdr_t obj_hdr = *(fd_groove_data_hdr_t const *)((ulong)_volume0 + child_obj_off);
831 :
832 44409 : ulong obj_type = fd_groove_data_hdr_type( obj_hdr );
833 44409 : ulong obj_idx = fd_groove_data_hdr_idx ( obj_hdr );
834 44409 : ulong obj_szc = fd_groove_data_hdr_szc ( obj_hdr );
835 :
836 44409 : TEST( (obj_type==FD_GROOVE_DATA_HDR_TYPE_ALLOC) | (obj_type==FD_GROOVE_DATA_HDR_TYPE_SUPERBLOCK) );
837 44409 : TEST( obj_idx==_idx );
838 44409 : TEST( obj_szc< FD_GROOVE_DATA_SZC_CNT );
839 :
840 44409 : TEST( fd_ulong_if( obj_type==FD_GROOVE_DATA_HDR_TYPE_ALLOC,
841 44409 : obj_szc, (ulong)fd_groove_data_szc_cfg[ obj_szc ].parent_szc )==szc );
842 :
843 44409 : ulong req_align = fd_groove_data_hdr_align( obj_hdr );
844 44409 : ulong req_sz = fd_groove_data_hdr_sz ( obj_hdr );
845 : //ulong req_info = fd_groove_data_hdr_info ( obj_hdr );
846 :
847 44409 : ulong req_footprint =
848 44409 : fd_ulong_align_up( fd_ulong_align_up( FD_GROOVE_DATA_HDR_FOOTPRINT, req_align ) + req_sz, FD_GROOVE_BLOCK_ALIGN );
849 :
850 44409 : TEST( fd_ulong_is_pow2( req_align ) );
851 44409 : TEST( req_align <=FD_GROOVE_BLOCK_ALIGN );
852 44409 : TEST( req_footprint<=obj_footprint );
853 :
854 : /* Note that recursion depth is bounded due to the finite number of
855 : sizeclasses and the validation above the children are respecting
856 : the szc hierarchy above. */
857 :
858 44409 : if( (!!verify_descendents) & (obj_type==FD_GROOVE_DATA_HDR_TYPE_SUPERBLOCK) ) /* verify superblock descendents */
859 23910 : TEST( !fd_groove_data_private_verify_superblock( child_obj_off, obj_szc, 0 /* don't know if in circulation */,
860 44409 : verify_descendents, _volume0, _volume1 ) );
861 :
862 44409 : rem_objs = fd_ulong_pop_lsb( rem_objs );
863 44409 : }
864 :
865 32169 : return FD_GROOVE_SUCCESS;
866 32169 : }
867 :
868 : int
869 15 : fd_groove_data_verify( fd_groove_data_t const * data ) {
870 :
871 : /* Verify join */
872 :
873 15 : TEST( data );
874 15 : TEST( fd_ulong_is_aligned( (ulong)data, alignof(fd_groove_data_t) ) );
875 :
876 15 : fd_groove_volume_pool_t const * pool = data->volume_pool;
877 15 : ulong const * active_slot = data->active_slot;
878 15 : ulong const * inactive_stack = data->inactive_stack;
879 : /* cgroup_hint is arbitrary */
880 :
881 : /* Verify volume pool */
882 :
883 15 : TEST( !fd_groove_volume_pool_verify( pool ) );
884 :
885 15 : fd_groove_volume_pool_shmem_t const * shpool = (fd_groove_volume_pool_shmem_t const *)fd_groove_volume_pool_shpool_const( pool );
886 :
887 15 : fd_groove_volume_t const * _volume0 = (fd_groove_volume_t const *)fd_groove_volume_pool_shele_const ( pool );
888 15 : ulong volume_max = fd_groove_volume_pool_ele_max ( pool );
889 15 : fd_groove_volume_t const * _volume1 = _volume0 + volume_max;
890 :
891 15 : TEST( (!!_volume0) | (!volume_max) );
892 15 : TEST( _volume0<=_volume1 );
893 15 : TEST( fd_ulong_is_aligned( (ulong)_volume0, FD_GROOVE_VOLUME_ALIGN ) );
894 :
895 15 : ulong volume_idx = fd_groove_volume_pool_private_vidx_idx( shpool->ver_top );
896 15 : while( volume_idx<volume_max ) { /* note: cyclic check already done by volume_pool_verify above */
897 0 : TEST( _volume0[ volume_idx ].magic==~FD_GROOVE_VOLUME_MAGIC );
898 0 : TEST( _volume0[ volume_idx ].idx ==volume_idx );
899 0 : volume_idx = fd_groove_volume_pool_private_idx( _volume0[ volume_idx ].next );
900 0 : }
901 :
902 : /* Verify data shmem */
903 :
904 15 : fd_groove_data_shmem_t const * shdata = (fd_groove_data_shmem_t const *)fd_groove_data_shdata_const( data );
905 :
906 15 : TEST( fd_ulong_is_aligned( (ulong)shdata, fd_groove_data_align() ) );
907 :
908 15 : TEST( shdata->magic ==FD_GROOVE_DATA_MAGIC );
909 15 : TEST( shdata->volume_pool ==shpool );
910 15 : TEST( shdata->active_slot ==active_slot );
911 15 : TEST( shdata->inactive_stack==inactive_stack );
912 :
913 : /* Verify sizeclass configuration */
914 :
915 495 : for( ulong szc_idx=0UL; szc_idx<FD_GROOVE_DATA_SZC_CNT; szc_idx++ ) {
916 480 : ulong obj_cnt = (ulong)fd_groove_data_szc_cfg[ szc_idx ].obj_cnt;
917 480 : ulong obj_footprint = (ulong)fd_groove_data_szc_cfg[ szc_idx ].obj_footprint;
918 480 : ulong cgroup_mask = (ulong)fd_groove_data_szc_cfg[ szc_idx ].cgroup_mask;
919 480 : ulong parent_szc = (ulong)fd_groove_data_szc_cfg[ szc_idx ].parent_szc;
920 :
921 480 : ulong cgroup_cnt = cgroup_mask + 1UL;
922 :
923 480 : ulong superblock_footprint = FD_GROOVE_BLOCK_FOOTPRINT + obj_cnt*obj_footprint;
924 :
925 480 : ulong parent_obj_footprint = (parent_szc<FD_GROOVE_DATA_SZC_CNT) ?
926 465 : (ulong)fd_groove_data_szc_cfg[ parent_szc ].obj_footprint : (FD_GROOVE_VOLUME_DATA_MAX - FD_GROOVE_BLOCK_FOOTPRINT);
927 :
928 480 : TEST( (1UL<=obj_cnt) & (obj_cnt<=64UL) );
929 480 : TEST( fd_ulong_is_aligned( obj_footprint, FD_GROOVE_BLOCK_FOOTPRINT ) );
930 480 : TEST( fd_ulong_is_pow2( cgroup_cnt ) );
931 480 : TEST( parent_szc<=FD_GROOVE_DATA_SZC_CNT );
932 480 : TEST( superblock_footprint <= parent_obj_footprint );
933 480 : }
934 :
935 : /* Verify all active superblocks */
936 :
937 495 : for( ulong szc_idx=0UL; szc_idx<FD_GROOVE_DATA_SZC_CNT; szc_idx++ ) {
938 480 : ulong cgroup_cnt = (ulong)fd_groove_data_szc_cfg[ szc_idx ].cgroup_mask + 1UL;
939 12165 : for( ulong cgroup_idx=0UL; cgroup_idx<cgroup_cnt; cgroup_idx++ ) {
940 11685 : ulong superblock_off = active_slot[ szc_idx + FD_GROOVE_DATA_SZC_CNT*cgroup_idx ];
941 11685 : if( !superblock_off ) continue;
942 :
943 159 : TEST( !fd_groove_data_private_verify_superblock( superblock_off, szc_idx, 1 /* is in circulation */,
944 159 : 0 /* don't verify children */, _volume0, _volume1 ) );
945 159 : fd_groove_data_hdr_t hdr = *(fd_groove_data_hdr_t const *)(((ulong)_volume0) + superblock_off);
946 159 : TEST( fd_groove_data_hdr_szc( hdr )==szc_idx );
947 159 : }
948 480 : }
949 :
950 : /* Verify all inactive superblocks for sizeclass szc_idx */
951 :
952 495 : for( ulong szc_idx=0UL; szc_idx<FD_GROOVE_DATA_SZC_CNT; szc_idx++ ) {
953 480 : ulong superblock_off = inactive_stack[ szc_idx ] & ~(FD_GROOVE_BLOCK_FOOTPRINT-1UL);
954 480 : ulong rem = volume_max*FD_GROOVE_VOLUME_FOOTPRINT / (2UL*FD_GROOVE_BLOCK_FOOTPRINT); /* FIXME: tighter bound? */
955 8574 : while( superblock_off ) {
956 8094 : FD_TEST( rem ); rem--; /* avoid cycles */
957 :
958 8094 : TEST( !fd_groove_data_private_verify_superblock( superblock_off, szc_idx, 1 /* is in circulation */,
959 8094 : 0 /* don't verify children */, _volume0, _volume1 ) );
960 8094 : fd_groove_data_hdr_t hdr = *(fd_groove_data_hdr_t const *)(((ulong)_volume0) + superblock_off);
961 8094 : TEST( fd_groove_data_hdr_szc( hdr )==szc_idx );
962 :
963 8094 : superblock_off = fd_groove_data_hdr_info( hdr );
964 8094 : }
965 480 : }
966 :
967 15 : return FD_GROOVE_SUCCESS;
968 15 : }
969 :
970 : int
971 : fd_groove_data_volume_verify( fd_groove_data_t const * data,
972 6 : fd_groove_volume_t const * _volume ) {
973 :
974 6 : TEST( data );
975 :
976 6 : fd_groove_volume_t const * _volume0 = (fd_groove_volume_t const *)fd_groove_data_volume0_const( data );
977 6 : fd_groove_volume_t const * _volume1 = (fd_groove_volume_t const *)fd_groove_data_volume1_const( data );
978 :
979 6 : ulong volume_off = (ulong)_volume - (ulong)_volume0;
980 :
981 6 : TEST( (_volume0<=_volume) & (_volume<_volume1) );
982 6 : TEST( fd_ulong_is_aligned( volume_off, FD_GROOVE_VOLUME_FOOTPRINT ) );
983 :
984 6 : ulong magic = _volume->magic;
985 6 : ulong idx = _volume->idx;
986 6 : ulong info_sz = _volume->info_sz;
987 :
988 6 : TEST( (magic==FD_GROOVE_VOLUME_MAGIC) | (magic==~FD_GROOVE_VOLUME_MAGIC) );
989 6 : TEST( idx*FD_GROOVE_VOLUME_FOOTPRINT==volume_off );
990 6 : TEST( info_sz <=FD_GROOVE_VOLUME_INFO_MAX );
991 :
992 6 : if( magic==FD_GROOVE_VOLUME_MAGIC ) {
993 6 : ulong superblock_off = volume_off + FD_GROOVE_BLOCK_FOOTPRINT;
994 6 : ulong superblock_szc = FD_GROOVE_DATA_SZC_CNT-1UL;
995 6 : TEST( !fd_groove_data_private_verify_superblock( superblock_off, superblock_szc, 0 /* don't know if in circulation */,
996 6 : 1 /* verify children */, _volume0, _volume1 ) );
997 6 : }
998 :
999 6 : return FD_GROOVE_SUCCESS;
1000 6 : }
1001 :
1002 : #undef TEST
|
