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 0 : ulong superblock_off ) {
35 0 : (void)volume0;
36 0 : FD_COMPILER_MFENCE();
37 0 : # if FD_HAS_ATOMIC
38 0 : 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 0 : FD_COMPILER_MFENCE();
45 0 : return superblock_off;
46 0 : }
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 0 : ulong superblock_off ) {
60 0 : FD_COMPILER_MFENCE();
61 :
62 0 : fd_groove_data_hdr_t * superblock = (fd_groove_data_hdr_t *)(((ulong)volume0) + superblock_off);
63 :
64 0 : for(;;) {
65 0 : ulong ver_off = *_inactive_stack;
66 :
67 0 : ulong ver = ver_off & (FD_GROOVE_BLOCK_FOOTPRINT-1UL);
68 0 : ulong next_off = ver_off & ~(FD_GROOVE_BLOCK_FOOTPRINT-1UL);
69 :
70 0 : superblock->info = next_off;
71 :
72 0 : ulong next_ver = (ver+1UL) & (FD_GROOVE_BLOCK_FOOTPRINT-1UL);
73 :
74 0 : # if FD_HAS_ATOMIC
75 0 : 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 0 : if( FD_LIKELY( old==ver_off ) ) break;
82 :
83 0 : FD_SPIN_PAUSE();
84 0 : }
85 :
86 0 : FD_COMPILER_MFENCE();
87 0 : }
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 0 : fd_groove_volume_t * volume0 ) {
99 :
100 0 : ulong off;
101 :
102 0 : FD_COMPILER_MFENCE();
103 :
104 0 : for(;;) {
105 0 : ulong ver_off = *_inactive_stack;
106 :
107 0 : ulong ver = ver_off & (FD_GROOVE_BLOCK_FOOTPRINT-1UL);
108 0 : /**/ off = ver_off & ~(FD_GROOVE_BLOCK_FOOTPRINT-1UL);
109 :
110 0 : if( FD_UNLIKELY( !off ) ) break;
111 :
112 0 : fd_groove_data_hdr_t * superblock = (fd_groove_data_hdr_t *)(((ulong)volume0) + off);
113 :
114 0 : ulong next_ver = (ver+1UL) & (FD_GROOVE_BLOCK_FOOTPRINT-1UL);
115 0 : ulong next_off = superblock->info;
116 :
117 0 : # if FD_HAS_ATOMIC
118 0 : 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 0 : if( FD_LIKELY( old==ver_off ) ) break;
125 :
126 0 : FD_SPIN_PAUSE();
127 0 : }
128 :
129 0 : FD_COMPILER_MFENCE();
130 :
131 0 : return off;
132 0 : }
133 :
134 : void *
135 0 : fd_groove_data_new( void * shmem ) {
136 0 : fd_groove_data_shmem_t * shdata = (fd_groove_data_shmem_t *)shmem;
137 :
138 0 : if( FD_UNLIKELY( !shdata ) ) {
139 0 : FD_LOG_WARNING(( "NULL shmem" ));
140 0 : return NULL;
141 0 : }
142 :
143 0 : if( FD_UNLIKELY( !fd_ulong_is_aligned( (ulong)shdata, fd_groove_data_align() ) ) ) {
144 0 : FD_LOG_WARNING(( "misaligned shmem" ));
145 0 : return NULL;
146 0 : }
147 :
148 0 : ulong footprint = fd_groove_data_footprint();
149 :
150 0 : if( FD_UNLIKELY( !footprint ) ) { /* currently not possible */
151 0 : FD_LOG_WARNING(( "bad configuration" ));
152 0 : return NULL;
153 0 : }
154 :
155 0 : memset( shdata, 0, footprint );
156 :
157 0 : if( FD_UNLIKELY( !fd_groove_volume_pool_new( shdata->volume_pool ) ) ) return NULL; /* logs details (currently not possible) */
158 :
159 0 : FD_COMPILER_MFENCE();
160 0 : shdata->magic = FD_GROOVE_DATA_MAGIC;
161 0 : FD_COMPILER_MFENCE();
162 :
163 0 : return shmem;
164 0 : }
165 :
166 : fd_groove_data_t *
167 : fd_groove_data_join( void * ljoin,
168 : void * shdata,
169 : void * volume0,
170 : ulong volume_max,
171 0 : ulong cgroup_hint ) {
172 0 : volume_max = fd_ulong_if( !!volume_max, volume_max, fd_groove_volume_pool_ele_max_max() );
173 :
174 0 : fd_groove_data_t * join = (fd_groove_data_t *)ljoin;
175 0 : fd_groove_data_shmem_t * data = (fd_groove_data_shmem_t *)shdata;
176 :
177 0 : if( FD_UNLIKELY( !join ) ) {
178 0 : FD_LOG_WARNING(( "NULL ljoin" ));
179 0 : return NULL;
180 0 : }
181 :
182 0 : if( FD_UNLIKELY( !fd_ulong_is_aligned( (ulong)join, alignof(fd_groove_data_t) ) ) ) {
183 0 : FD_LOG_WARNING(( "misaligned ljoin" ));
184 0 : return NULL;
185 0 : }
186 :
187 0 : if( FD_UNLIKELY( !data ) ) {
188 0 : FD_LOG_WARNING(( "NULL shdata" ));
189 0 : return NULL;
190 0 : }
191 :
192 0 : if( FD_UNLIKELY( !fd_ulong_is_aligned( (ulong)data, fd_groove_data_align() ) ) ) {
193 0 : FD_LOG_WARNING(( "misaligned shdata" ));
194 0 : return NULL;
195 0 : }
196 :
197 0 : if( FD_UNLIKELY( data->magic!=FD_GROOVE_DATA_MAGIC ) ) {
198 0 : FD_LOG_WARNING(( "bad magic" ));
199 0 : return NULL;
200 0 : }
201 :
202 0 : if( FD_UNLIKELY( !volume0 ) ) {
203 0 : FD_LOG_WARNING(( "NULL volume0" ));
204 0 : return NULL;
205 0 : }
206 :
207 0 : if( FD_UNLIKELY( !fd_ulong_is_aligned( (ulong)volume0, alignof(fd_groove_volume_t) ) ) ) {
208 0 : FD_LOG_WARNING(( "misaligned volume0" ));
209 0 : return NULL;
210 0 : }
211 :
212 0 : if( FD_UNLIKELY( !fd_groove_volume_pool_join( join->volume_pool, data->volume_pool, volume0, volume_max ) ) ) /* logs details */
213 0 : return NULL;
214 :
215 0 : join->active_slot = data->active_slot;
216 0 : join->inactive_stack = data->inactive_stack;
217 0 : join->cgroup_hint = cgroup_hint;
218 :
219 0 : return join;
220 0 : }
221 :
222 : void *
223 0 : fd_groove_data_leave( fd_groove_data_t * join ) {
224 0 : if( FD_UNLIKELY( !join ) ) {
225 0 : FD_LOG_WARNING(( "NULL join" ));
226 0 : return NULL;
227 0 : }
228 :
229 0 : 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 0 : return join;
235 0 : }
236 :
237 : void *
238 0 : fd_groove_data_delete( void * shdata ) {
239 0 : fd_groove_data_shmem_t * data = (fd_groove_data_shmem_t *)shdata;
240 :
241 0 : if( FD_UNLIKELY( !data ) ) {
242 0 : FD_LOG_WARNING(( "NULL shdata" ));
243 0 : return NULL;
244 0 : }
245 :
246 0 : if( FD_UNLIKELY( !fd_ulong_is_aligned( (ulong)data, fd_groove_data_align() ) ) ) {
247 0 : FD_LOG_WARNING(( "misaligned shdata" ));
248 0 : return NULL;
249 0 : }
250 :
251 0 : if( FD_UNLIKELY( data->magic!=FD_GROOVE_DATA_MAGIC ) ) {
252 0 : FD_LOG_WARNING(( "bad magic" ));
253 0 : return NULL;
254 0 : }
255 :
256 0 : FD_COMPILER_MFENCE();
257 0 : data->magic = 0UL;
258 0 : FD_COMPILER_MFENCE();
259 :
260 0 : return shdata;
261 0 : }
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 0 : ulong * _obj_idx ) {
273 :
274 0 : fd_groove_volume_t * _volume0 = (fd_groove_volume_t *)fd_groove_data_volume0( data );
275 :
276 0 : # if FD_GROOVE_PARANOID
277 0 : fd_groove_volume_t * _volume1 = (fd_groove_volume_t *)fd_groove_data_volume1( data );
278 0 : # endif
279 :
280 0 : ulong obj_cnt = (ulong)fd_groove_data_szc_cfg[ obj_szc ].obj_cnt;
281 0 : ulong obj_footprint = (ulong)fd_groove_data_szc_cfg[ obj_szc ].obj_footprint;
282 0 : ulong cgroup_mask = (ulong)fd_groove_data_szc_cfg[ obj_szc ].cgroup_mask;
283 0 : 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 0 : ulong cgroup = data->cgroup_hint & cgroup_mask;
290 :
291 0 : ulong volatile * _active_slot = data->active_slot + obj_szc + FD_GROOVE_DATA_SZC_CNT*cgroup;
292 0 : ulong volatile * _inactive_stack = data->inactive_stack + obj_szc;
293 :
294 0 : 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 0 : FD_COMPILER_MFENCE();
302 0 : superblock_off = *_active_slot;
303 0 : FD_COMPILER_MFENCE();
304 :
305 0 : if( FD_LIKELY( superblock_off ) ) superblock_off = fd_groove_data_private_active_displace( _active_slot, _volume0, 0UL );
306 :
307 0 : 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 0 : superblock_off = fd_groove_data_private_inactive_pop( _inactive_stack, _volume0 );
315 :
316 0 : 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 0 : ulong parent_idx = 0UL; /* reduce risk of uninitialized variable false positives from code analysis tools */
323 :
324 0 : if( FD_UNLIKELY( parent_szc==FD_GROOVE_DATA_SZC_CNT ) ) { /* Acquire a volume to use for the new superblock */
325 :
326 0 : fd_groove_volume_t * _volume = fd_groove_volume_pool_acquire( data->volume_pool );
327 0 : if( FD_UNLIKELY( !_volume ) ) return FD_GROOVE_ERR_FULL;
328 :
329 0 : # if FD_GROOVE_PARANOID
330 0 : ulong volume_off = (ulong)_volume - (ulong)_volume0;
331 :
332 0 : if( FD_UNLIKELY( !( (_volume0<=_volume) & (_volume<_volume1) &
333 0 : 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 0 : if( FD_UNLIKELY( !( (_volume->magic ==~FD_GROOVE_VOLUME_MAGIC ) &
339 0 : (_volume->idx*FD_GROOVE_VOLUME_FOOTPRINT==volume_off ) &
340 0 : (_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 0 : # endif
345 :
346 0 : FD_COMPILER_MFENCE();
347 0 : _volume->magic = FD_GROOVE_VOLUME_MAGIC; /* mark volume as potentially containing groove data allocations */
348 0 : FD_COMPILER_MFENCE();
349 :
350 : //parent_idx = 0UL; /* See note above about initialization */
351 0 : superblock_off = (ulong)_volume->data - (ulong)_volume0;
352 :
353 0 : } else { /* Acquire a parent_szc object to use for the new superblock */
354 :
355 0 : int err = fd_groove_data_private_alloc_obj( data, parent_szc, &superblock_off, &parent_idx ); /* logs details */
356 0 : if( FD_UNLIKELY( err ) ) return err;
357 :
358 0 : }
359 :
360 0 : ulong superblock_align = FD_GROOVE_DATA_HDR_ALIGN;
361 0 : ulong superblock_sz = FD_GROOVE_BLOCK_FOOTPRINT - FD_GROOVE_DATA_HDR_FOOTPRINT + obj_footprint*obj_cnt;
362 :
363 0 : fd_groove_data_hdr_t * _superblock_hdr = (fd_groove_data_hdr_t *)(((ulong)_volume0) + superblock_off);
364 :
365 0 : # if FD_GROOVE_PARANOID
366 0 : if( FD_UNLIKELY( !( ((ulong)_volume0<(ulong)_superblock_hdr) & ((ulong)_superblock_hdr<(ulong)_volume1) &
367 0 : 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 0 : # endif
372 :
373 0 : *_superblock_hdr = fd_groove_data_hdr( FD_GROOVE_DATA_HDR_TYPE_SUPERBLOCK, parent_idx, obj_szc,
374 0 : superblock_align, fd_ulong_min( superblock_sz, (1UL<<25)-1UL ), 0UL /* no next */ );
375 0 : *(ulong *)(_superblock_hdr+1) = (1UL<<obj_cnt)-1UL; /* mark all objects in superblock as free */
376 0 : }
377 0 : }
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 0 : fd_groove_data_hdr_t * _superblock_hdr = (fd_groove_data_hdr_t *)(((ulong)_volume0) + superblock_off);
388 :
389 0 : ulong volatile * _free_objs = (ulong volatile *)(_superblock_hdr+1);
390 :
391 0 : # if FD_GROOVE_PARANOID
392 0 : if( FD_UNLIKELY( !( ((ulong)_volume0<(ulong)_superblock_hdr) & ((ulong)_superblock_hdr<(ulong)_volume1) &
393 0 : 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 0 : fd_groove_data_hdr_t superblock_hdr = *_superblock_hdr;
399 :
400 0 : ulong superblock_type = fd_groove_data_hdr_type( superblock_hdr );
401 0 : ulong superblock_szc = fd_groove_data_hdr_szc ( superblock_hdr );
402 :
403 0 : 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 0 : # endif
408 :
409 0 : FD_COMPILER_MFENCE();
410 0 : ulong free_objs = *_free_objs;
411 0 : FD_COMPILER_MFENCE();
412 :
413 0 : # if FD_GROOVE_PARANOID
414 0 : 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 0 : # endif
419 :
420 0 : ulong obj = fd_ulong_lsb( free_objs );
421 :
422 0 : FD_COMPILER_MFENCE();
423 0 : # if FD_HAS_ATOMIC
424 0 : 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 0 : FD_COMPILER_MFENCE();
430 :
431 0 : # if FD_GROOVE_PARANOID
432 0 : 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 0 : # endif
437 :
438 0 : if( FD_LIKELY( free_objs!=obj ) ) {
439 0 : ulong displaced_superblock_off = fd_groove_data_private_active_displace( _active_slot, _volume0, superblock_off );
440 0 : if( FD_UNLIKELY( displaced_superblock_off ) )
441 0 : fd_groove_data_private_inactive_push( _inactive_stack, _volume0, displaced_superblock_off );
442 0 : }
443 :
444 : /* At this point, we've allocated the object */
445 :
446 0 : ulong obj_idx = (ulong)fd_ulong_find_lsb( obj );
447 :
448 0 : *_obj_off = superblock_off + FD_GROOVE_BLOCK_FOOTPRINT + obj_idx*obj_footprint;
449 0 : *_obj_idx = obj_idx;
450 0 : return FD_GROOVE_SUCCESS;
451 0 : }
452 :
453 : void *
454 : fd_groove_data_alloc( fd_groove_data_t * data,
455 : ulong align,
456 : ulong sz,
457 : ulong tag,
458 0 : int * _err ) {
459 :
460 0 : int stack_err[1];
461 0 : if( !_err ) _err = stack_err;
462 :
463 : /* Check input args */
464 :
465 0 : if( FD_UNLIKELY( !data ) ) {
466 0 : FD_LOG_WARNING(( "NULL data" ));
467 0 : *_err = FD_GROOVE_ERR_INVAL;
468 0 : return NULL;
469 0 : }
470 :
471 0 : align = fd_ulong_if( !!align, align, FD_GROOVE_DATA_ALLOC_ALIGN_DEFAULT );
472 0 : if( FD_UNLIKELY( !(fd_ulong_is_pow2( align ) & (align<=FD_GROOVE_DATA_ALLOC_ALIGN_MAX)) ) ) {
473 0 : FD_LOG_WARNING(( "bad align" ));
474 0 : *_err = FD_GROOVE_ERR_INVAL;
475 0 : return NULL;
476 0 : }
477 :
478 0 : ulong off_obj = fd_ulong_align_up( FD_GROOVE_DATA_HDR_FOOTPRINT, align );
479 0 : ulong footprint = fd_ulong_align_up( off_obj+sz, FD_GROOVE_BLOCK_ALIGN );
480 :
481 0 : if( FD_UNLIKELY( !((sz<footprint) & (footprint<=FD_GROOVE_DATA_ALLOC_FOOTPRINT_MAX)) ) ) {
482 0 : FD_LOG_WARNING(( "bad sz/align" ));
483 0 : *_err = FD_GROOVE_ERR_INVAL;
484 0 : return NULL;
485 0 : }
486 :
487 : /* Acquire an object from the tightest suitable sizeclass */
488 :
489 0 : ulong obj_szc = fd_groove_data_szc( footprint );
490 :
491 0 : ulong obj_off;
492 0 : ulong obj_idx;
493 0 : int err = fd_groove_data_private_alloc_obj( data, obj_szc, &obj_off, &obj_idx ); /* logs details */
494 0 : if( FD_UNLIKELY( err ) ) {
495 0 : *_err = err;
496 0 : return NULL;
497 0 : }
498 :
499 : /* Carve an allocation into it. */
500 :
501 0 : 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 0 : *obj_hdr = fd_groove_data_hdr( FD_GROOVE_DATA_HDR_TYPE_ALLOC, obj_idx, obj_szc, align, sz, tag );
504 :
505 0 : *_err = FD_GROOVE_SUCCESS;
506 0 : return (void *)((ulong)obj_hdr + off_obj);
507 0 : }
508 :
509 : int
510 : fd_groove_data_private_free( fd_groove_data_t * data,
511 : void * _obj,
512 0 : ulong exp_type ) {
513 :
514 : # if !FD_GROOVE_PARANOID
515 : (void)exp_type; /* Suppress unused warning if running without paranoia */
516 : # endif
517 :
518 0 : if( FD_UNLIKELY( !data ) ) {
519 0 : FD_LOG_WARNING(( "NULL data" ));
520 0 : return FD_GROOVE_ERR_INVAL;
521 0 : }
522 :
523 0 : if( FD_UNLIKELY( !_obj ) ) return FD_GROOVE_ERR_INVAL;
524 :
525 0 : fd_groove_data_hdr_t * _obj_hdr = fd_groove_data_object_hdr( _obj );
526 :
527 0 : fd_groove_volume_t * _volume0 = (fd_groove_volume_t *)fd_groove_data_volume0( data );
528 :
529 0 : # if FD_GROOVE_PARANOID
530 0 : fd_groove_volume_t * _volume1 = (fd_groove_volume_t *)fd_groove_data_volume1( data );
531 0 : if( FD_UNLIKELY( !( ((ulong)_volume0<=(ulong)_obj_hdr ) &
532 0 : ((ulong)_obj_hdr< (ulong)_volume1 ) &
533 0 : (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 0 : # endif
538 :
539 0 : fd_groove_data_hdr_t obj_hdr = *_obj_hdr;
540 :
541 0 : ulong obj_type = fd_groove_data_hdr_type( obj_hdr );
542 0 : ulong obj_idx = fd_groove_data_hdr_idx ( obj_hdr );
543 0 : ulong obj_szc = fd_groove_data_hdr_szc ( obj_hdr );
544 :
545 0 : #if FD_GROOVE_PARANOID
546 0 : 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 0 : # endif
552 :
553 0 : obj_szc = fd_ulong_if( obj_type==FD_GROOVE_DATA_HDR_TYPE_ALLOC, obj_szc,
554 0 : (ulong)fd_groove_data_szc_cfg[ obj_szc ].parent_szc );
555 0 : ulong obj_cnt = (ulong)fd_groove_data_szc_cfg[ obj_szc ].obj_cnt;
556 0 : # if FD_GROOVE_PARANOID
557 0 : ulong obj_footprint = (ulong)fd_groove_data_szc_cfg[ obj_szc ].obj_footprint;
558 :
559 0 : ulong req_align = fd_groove_data_hdr_align( obj_hdr );
560 0 : ulong req_sz = fd_groove_data_hdr_sz ( obj_hdr );
561 0 : ulong req_footprint =
562 0 : fd_ulong_align_up( fd_ulong_align_up( FD_GROOVE_DATA_HDR_FOOTPRINT, req_align ) + req_sz, FD_GROOVE_BLOCK_ALIGN );
563 :
564 0 : if( FD_UNLIKELY( !( (obj_idx<obj_cnt ) &
565 0 : (fd_ulong_is_pow2( req_align ) ) &
566 0 : (req_align<=FD_GROOVE_BLOCK_ALIGN) &
567 0 : (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 0 : # 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 0 : fd_groove_data_hdr_t * _superblock_hdr = fd_groove_data_superblock_hdr( _obj, obj_szc, obj_idx );
592 :
593 0 : ulong volatile * _free_objs = (ulong volatile *)(_superblock_hdr+1);
594 :
595 0 : ulong free_objs;
596 :
597 0 : ulong obj = 1UL << obj_idx;
598 :
599 0 : # if FD_GROOVE_PARANOID
600 0 : if( FD_UNLIKELY( !( ((ulong)_volume0<(ulong)_superblock_hdr) & ((ulong)_superblock_hdr<(ulong)_obj_hdr) &
601 0 : 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 0 : fd_groove_data_hdr_t superblock_hdr = *_superblock_hdr;
607 :
608 0 : ulong superblock_type = fd_groove_data_hdr_type( superblock_hdr );
609 0 : ulong superblock_szc = fd_groove_data_hdr_szc ( superblock_hdr );
610 :
611 0 : 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 0 : FD_COMPILER_MFENCE();
617 0 : free_objs = *_free_objs;
618 0 : FD_COMPILER_MFENCE();
619 :
620 0 : 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 0 : FD_COMPILER_MFENCE();
626 0 : _obj_hdr->bits = 0UL; /* sets object type to an invalid value */
627 0 : FD_COMPILER_MFENCE();
628 0 : # endif
629 :
630 0 : FD_COMPILER_MFENCE();
631 0 : # if FD_HAS_ATOMIC
632 0 : 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 0 : FD_COMPILER_MFENCE();
638 :
639 0 : # if FD_GROOVE_PARANOID
640 0 : 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 0 : # 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 0 : ulong free_cnt = (ulong)fd_ulong_popcnt( free_objs );
651 :
652 0 : 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 0 : ulong cgroup = fd_groove_data_cgroup_hint( data ) & (ulong)fd_groove_data_szc_cfg[ obj_szc ].cgroup_mask;
662 :
663 0 : ulong displaced_superblock_off =
664 0 : fd_groove_data_private_active_displace( data->active_slot + obj_szc + FD_GROOVE_DATA_SZC_CNT*cgroup,
665 0 : _volume0, (ulong)_superblock_hdr - (ulong)_volume0 );
666 :
667 0 : if( FD_UNLIKELY( displaced_superblock_off ) )
668 0 : fd_groove_data_private_inactive_push( data->inactive_stack + obj_szc, _volume0, displaced_superblock_off );
669 :
670 0 : } 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 0 : ulong volatile * _inactive_stack = data->inactive_stack + obj_szc;
679 :
680 0 : ulong superblock_off = fd_groove_data_private_inactive_pop( _inactive_stack, _volume0 );
681 :
682 0 : if( FD_LIKELY( superblock_off ) ) {
683 :
684 0 : _superblock_hdr = (fd_groove_data_hdr_t *)((ulong)_volume0 + superblock_off);
685 :
686 0 : _free_objs = (ulong volatile *)(_superblock_hdr+1);
687 :
688 0 : # if FD_GROOVE_PARANOID
689 0 : if( FD_UNLIKELY( !( ((ulong)_volume0<(ulong)_superblock_hdr) & ((ulong)_superblock_hdr<(ulong)_volume1) &
690 0 : 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 0 : superblock_type = fd_groove_data_hdr_type( superblock_hdr );
696 0 : superblock_szc = fd_groove_data_hdr_szc ( superblock_hdr );
697 :
698 0 : 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 0 : # endif
703 :
704 0 : FD_COMPILER_MFENCE();
705 0 : free_objs = *_free_objs;
706 0 : FD_COMPILER_MFENCE();
707 :
708 0 : # if FD_GROOVE_PARANOID
709 0 : 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 0 : # endif
714 :
715 0 : free_cnt = (ulong)fd_ulong_popcnt( free_objs );
716 :
717 0 : if( FD_LIKELY( free_cnt<obj_cnt ) ) { /* inactive top was not completely empty, return to circulation */
718 :
719 0 : fd_groove_data_private_inactive_push( _inactive_stack, _volume0, superblock_off );
720 :
721 0 : } else if( FD_LIKELY( obj_szc<(FD_GROOVE_DATA_SZC_CNT-1UL) ) ) { /* completely empty and should free from parent sb */
722 :
723 0 : int err = fd_groove_data_private_free( data, _superblock_hdr+1, FD_GROOVE_DATA_HDR_TYPE_SUPERBLOCK ); /* offset the hdr */
724 0 : 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 0 : } 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 0 : }
758 0 : }
759 :
760 0 : return FD_GROOVE_SUCCESS;
761 0 : }
762 :
763 0 : #define TEST(c) do { \
764 0 : if( FD_UNLIKELY( !(c) ) ) { FD_LOG_WARNING(( "FAIL: %s", #c )); return FD_GROOVE_ERR_CORRUPT; } \
765 0 : } 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 0 : fd_groove_volume_t const * _volume1 ) {
784 :
785 : /* Verify superblock_off */
786 :
787 0 : fd_groove_data_hdr_t const * _superblock_hdr = (fd_groove_data_hdr_t const *)(((ulong)_volume0) + superblock_off);
788 :
789 0 : TEST( ((ulong)_volume0<(ulong)_superblock_hdr) & ((ulong)_superblock_hdr<(ulong)_volume1) );
790 0 : TEST( fd_ulong_is_aligned( (ulong)_superblock_hdr, FD_GROOVE_BLOCK_ALIGN ) );
791 :
792 : /* Verify superblock header */
793 :
794 0 : fd_groove_data_hdr_t hdr = *_superblock_hdr;
795 :
796 0 : TEST( fd_groove_data_hdr_type( hdr )==FD_GROOVE_DATA_HDR_TYPE_SUPERBLOCK );
797 :
798 0 : ulong szc = fd_groove_data_hdr_szc( hdr );
799 :
800 0 : TEST( szc==exp_szc );
801 :
802 0 : ulong obj_cnt = (ulong)fd_groove_data_szc_cfg[ szc ].obj_cnt;
803 0 : ulong obj_footprint = (ulong)fd_groove_data_szc_cfg[ szc ].obj_footprint;
804 0 : ulong parent_szc = (ulong)fd_groove_data_szc_cfg[ szc ].parent_szc;
805 :
806 0 : ulong parent_obj_idx = fd_groove_data_hdr_idx( hdr );
807 0 : 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 0 : TEST( parent_obj_idx < parent_obj_cnt );
812 :
813 0 : TEST( fd_groove_data_hdr_align( hdr )==FD_GROOVE_DATA_HDR_ALIGN );
814 0 : TEST( fd_groove_data_hdr_sz ( hdr )==
815 0 : fd_ulong_min( FD_GROOVE_BLOCK_FOOTPRINT - FD_GROOVE_DATA_HDR_FOOTPRINT + obj_cnt*obj_footprint, (1UL<<25)-1UL ) );
816 :
817 0 : ulong free_objs = *(ulong const *)(_superblock_hdr+1);
818 :
819 0 : TEST( !fd_ulong_shift_right( free_objs, (int)obj_cnt ) ); /* valid free obj bit field */
820 0 : if( in_circulation ) TEST( !!free_objs ); /* at least 1 free obj for superblocks in circulation */
821 :
822 : /* Verify superblock object headers */
823 :
824 0 : ulong rem_objs = free_objs ^ fd_ulong_mask_lsb( (int)obj_cnt );
825 0 : while( rem_objs ) {
826 0 : ulong _idx = (ulong)fd_ulong_find_lsb( rem_objs );
827 :
828 0 : ulong child_obj_off = superblock_off + FD_GROOVE_BLOCK_FOOTPRINT + _idx*obj_footprint;
829 :
830 0 : fd_groove_data_hdr_t obj_hdr = *(fd_groove_data_hdr_t const *)((ulong)_volume0 + child_obj_off);
831 :
832 0 : ulong obj_type = fd_groove_data_hdr_type( obj_hdr );
833 0 : ulong obj_idx = fd_groove_data_hdr_idx ( obj_hdr );
834 0 : ulong obj_szc = fd_groove_data_hdr_szc ( obj_hdr );
835 :
836 0 : TEST( (obj_type==FD_GROOVE_DATA_HDR_TYPE_ALLOC) | (obj_type==FD_GROOVE_DATA_HDR_TYPE_SUPERBLOCK) );
837 0 : TEST( obj_idx==_idx );
838 0 : TEST( obj_szc< FD_GROOVE_DATA_SZC_CNT );
839 :
840 0 : TEST( fd_ulong_if( obj_type==FD_GROOVE_DATA_HDR_TYPE_ALLOC,
841 0 : obj_szc, (ulong)fd_groove_data_szc_cfg[ obj_szc ].parent_szc )==szc );
842 :
843 0 : ulong req_align = fd_groove_data_hdr_align( obj_hdr );
844 0 : ulong req_sz = fd_groove_data_hdr_sz ( obj_hdr );
845 : //ulong req_info = fd_groove_data_hdr_info ( obj_hdr );
846 :
847 0 : ulong req_footprint =
848 0 : fd_ulong_align_up( fd_ulong_align_up( FD_GROOVE_DATA_HDR_FOOTPRINT, req_align ) + req_sz, FD_GROOVE_BLOCK_ALIGN );
849 :
850 0 : TEST( fd_ulong_is_pow2( req_align ) );
851 0 : TEST( req_align <=FD_GROOVE_BLOCK_ALIGN );
852 0 : 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 0 : if( (!!verify_descendents) & (obj_type==FD_GROOVE_DATA_HDR_TYPE_SUPERBLOCK) ) /* verify superblock descendents */
859 0 : TEST( !fd_groove_data_private_verify_superblock( child_obj_off, obj_szc, 0 /* don't know if in circulation */,
860 0 : verify_descendents, _volume0, _volume1 ) );
861 :
862 0 : rem_objs = fd_ulong_pop_lsb( rem_objs );
863 0 : }
864 :
865 0 : return FD_GROOVE_SUCCESS;
866 0 : }
867 :
868 : int
869 0 : fd_groove_data_verify( fd_groove_data_t const * data ) {
870 :
871 : /* Verify join */
872 :
873 0 : TEST( data );
874 0 : TEST( fd_ulong_is_aligned( (ulong)data, alignof(fd_groove_data_t) ) );
875 :
876 0 : fd_groove_volume_pool_t const * pool = data->volume_pool;
877 0 : ulong const * active_slot = data->active_slot;
878 0 : ulong const * inactive_stack = data->inactive_stack;
879 : /* cgroup_hint is arbitrary */
880 :
881 : /* Verify volume pool */
882 :
883 0 : TEST( !fd_groove_volume_pool_verify( pool ) );
884 :
885 0 : fd_groove_volume_pool_shmem_t const * shpool = (fd_groove_volume_pool_shmem_t const *)fd_groove_volume_pool_shpool_const( pool );
886 :
887 0 : fd_groove_volume_t const * _volume0 = (fd_groove_volume_t const *)fd_groove_volume_pool_shele_const ( pool );
888 0 : ulong volume_max = fd_groove_volume_pool_ele_max ( pool );
889 0 : fd_groove_volume_t const * _volume1 = _volume0 + volume_max;
890 :
891 0 : TEST( (!!_volume0) | (!volume_max) );
892 0 : TEST( _volume0<=_volume1 );
893 0 : TEST( fd_ulong_is_aligned( (ulong)_volume0, FD_GROOVE_VOLUME_ALIGN ) );
894 :
895 0 : ulong volume_idx = fd_groove_volume_pool_private_vidx_idx( shpool->ver_top );
896 0 : 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 0 : fd_groove_data_shmem_t const * shdata = (fd_groove_data_shmem_t const *)fd_groove_data_shdata_const( data );
905 :
906 0 : TEST( fd_ulong_is_aligned( (ulong)shdata, fd_groove_data_align() ) );
907 :
908 0 : TEST( shdata->magic ==FD_GROOVE_DATA_MAGIC );
909 0 : TEST( shdata->volume_pool ==shpool );
910 0 : TEST( shdata->active_slot ==active_slot );
911 0 : TEST( shdata->inactive_stack==inactive_stack );
912 :
913 : /* Verify sizeclass configuration */
914 :
915 0 : for( ulong szc_idx=0UL; szc_idx<FD_GROOVE_DATA_SZC_CNT; szc_idx++ ) {
916 0 : ulong obj_cnt = (ulong)fd_groove_data_szc_cfg[ szc_idx ].obj_cnt;
917 0 : ulong obj_footprint = (ulong)fd_groove_data_szc_cfg[ szc_idx ].obj_footprint;
918 0 : ulong cgroup_mask = (ulong)fd_groove_data_szc_cfg[ szc_idx ].cgroup_mask;
919 0 : ulong parent_szc = (ulong)fd_groove_data_szc_cfg[ szc_idx ].parent_szc;
920 :
921 0 : ulong cgroup_cnt = cgroup_mask + 1UL;
922 :
923 0 : ulong superblock_footprint = FD_GROOVE_BLOCK_FOOTPRINT + obj_cnt*obj_footprint;
924 :
925 0 : ulong parent_obj_footprint = (parent_szc<FD_GROOVE_DATA_SZC_CNT) ?
926 0 : (ulong)fd_groove_data_szc_cfg[ parent_szc ].obj_footprint : (FD_GROOVE_VOLUME_DATA_MAX - FD_GROOVE_BLOCK_FOOTPRINT);
927 :
928 0 : TEST( (1UL<=obj_cnt) & (obj_cnt<=64UL) );
929 0 : TEST( fd_ulong_is_aligned( obj_footprint, FD_GROOVE_BLOCK_FOOTPRINT ) );
930 0 : TEST( fd_ulong_is_pow2( cgroup_cnt ) );
931 0 : TEST( parent_szc<=FD_GROOVE_DATA_SZC_CNT );
932 0 : TEST( superblock_footprint <= parent_obj_footprint );
933 0 : }
934 :
935 : /* Verify all active superblocks */
936 :
937 0 : for( ulong szc_idx=0UL; szc_idx<FD_GROOVE_DATA_SZC_CNT; szc_idx++ ) {
938 0 : ulong cgroup_cnt = (ulong)fd_groove_data_szc_cfg[ szc_idx ].cgroup_mask + 1UL;
939 0 : for( ulong cgroup_idx=0UL; cgroup_idx<cgroup_cnt; cgroup_idx++ ) {
940 0 : ulong superblock_off = active_slot[ szc_idx + FD_GROOVE_DATA_SZC_CNT*cgroup_idx ];
941 0 : if( !superblock_off ) continue;
942 :
943 0 : TEST( !fd_groove_data_private_verify_superblock( superblock_off, szc_idx, 1 /* is in circulation */,
944 0 : 0 /* don't verify children */, _volume0, _volume1 ) );
945 0 : fd_groove_data_hdr_t hdr = *(fd_groove_data_hdr_t const *)(((ulong)_volume0) + superblock_off);
946 0 : TEST( fd_groove_data_hdr_szc( hdr )==szc_idx );
947 0 : }
948 0 : }
949 :
950 : /* Verify all inactive superblocks for sizeclass szc_idx */
951 :
952 0 : for( ulong szc_idx=0UL; szc_idx<FD_GROOVE_DATA_SZC_CNT; szc_idx++ ) {
953 0 : ulong superblock_off = inactive_stack[ szc_idx ] & ~(FD_GROOVE_BLOCK_FOOTPRINT-1UL);
954 0 : ulong rem = volume_max*FD_GROOVE_VOLUME_FOOTPRINT / (2UL*FD_GROOVE_BLOCK_FOOTPRINT); /* FIXME: tighter bound? */
955 0 : while( superblock_off ) {
956 0 : FD_TEST( rem ); rem--; /* avoid cycles */
957 :
958 0 : TEST( !fd_groove_data_private_verify_superblock( superblock_off, szc_idx, 1 /* is in circulation */,
959 0 : 0 /* don't verify children */, _volume0, _volume1 ) );
960 0 : fd_groove_data_hdr_t hdr = *(fd_groove_data_hdr_t const *)(((ulong)_volume0) + superblock_off);
961 0 : TEST( fd_groove_data_hdr_szc( hdr )==szc_idx );
962 :
963 0 : superblock_off = fd_groove_data_hdr_info( hdr );
964 0 : }
965 0 : }
966 :
967 0 : return FD_GROOVE_SUCCESS;
968 0 : }
969 :
970 : int
971 : fd_groove_data_volume_verify( fd_groove_data_t const * data,
972 0 : fd_groove_volume_t const * _volume ) {
973 :
974 0 : TEST( data );
975 :
976 0 : fd_groove_volume_t const * _volume0 = (fd_groove_volume_t const *)fd_groove_data_volume0_const( data );
977 0 : fd_groove_volume_t const * _volume1 = (fd_groove_volume_t const *)fd_groove_data_volume1_const( data );
978 :
979 0 : ulong volume_off = (ulong)_volume - (ulong)_volume0;
980 :
981 0 : TEST( (_volume0<=_volume) & (_volume<_volume1) );
982 0 : TEST( fd_ulong_is_aligned( volume_off, FD_GROOVE_VOLUME_FOOTPRINT ) );
983 :
984 0 : ulong magic = _volume->magic;
985 0 : ulong idx = _volume->idx;
986 0 : ulong info_sz = _volume->info_sz;
987 :
988 0 : TEST( (magic==FD_GROOVE_VOLUME_MAGIC) | (magic==~FD_GROOVE_VOLUME_MAGIC) );
989 0 : TEST( idx*FD_GROOVE_VOLUME_FOOTPRINT==volume_off );
990 0 : TEST( info_sz <=FD_GROOVE_VOLUME_INFO_MAX );
991 :
992 0 : if( magic==FD_GROOVE_VOLUME_MAGIC ) {
993 0 : ulong superblock_off = volume_off + FD_GROOVE_BLOCK_FOOTPRINT;
994 0 : ulong superblock_szc = FD_GROOVE_DATA_SZC_CNT-1UL;
995 0 : TEST( !fd_groove_data_private_verify_superblock( superblock_off, superblock_szc, 0 /* don't know if in circulation */,
996 0 : 1 /* verify children */, _volume0, _volume1 ) );
997 0 : }
998 :
999 0 : return FD_GROOVE_SUCCESS;
1000 0 : }
1001 :
1002 : #undef TEST
|
