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 : int err;
327 0 : fd_groove_volume_t * _volume = fd_groove_volume_pool_acquire( data->volume_pool, NULL, 1 /* blocking */, &err );
328 :
329 0 : if( FD_UNLIKELY( !_volume ) ) {
330 0 : if( FD_UNLIKELY( err!=FD_POOL_ERR_EMPTY ) ) {
331 0 : FD_LOG_WARNING(( "fd_groove_volume_pool_acquire failed (%i-%s)", err, fd_groove_volume_pool_strerror( err ) ));
332 0 : return FD_GROOVE_ERR_CORRUPT;
333 0 : }
334 0 : return FD_GROOVE_ERR_FULL;
335 0 : }
336 :
337 0 : # if FD_GROOVE_PARANOID
338 0 : ulong volume_off = (ulong)_volume - (ulong)_volume0;
339 :
340 0 : if( FD_UNLIKELY( !( (_volume0<=_volume) & (_volume<_volume1) &
341 0 : fd_ulong_is_aligned( volume_off, FD_GROOVE_VOLUME_FOOTPRINT ) ) ) ) {
342 0 : FD_LOG_WARNING(( "volume not at a valid groove data local address" ));
343 0 : return FD_GROOVE_ERR_CORRUPT;
344 0 : }
345 :
346 0 : if( FD_UNLIKELY( !( (_volume->magic ==~FD_GROOVE_VOLUME_MAGIC ) &
347 0 : (_volume->idx*FD_GROOVE_VOLUME_FOOTPRINT==volume_off ) &
348 0 : (_volume->info_sz <=FD_GROOVE_VOLUME_INFO_MAX) ) ) ) {
349 0 : FD_LOG_WARNING(( "unexpected volume header" ));
350 0 : return FD_GROOVE_ERR_CORRUPT;
351 0 : }
352 0 : # endif
353 :
354 0 : FD_COMPILER_MFENCE();
355 0 : _volume->magic = FD_GROOVE_VOLUME_MAGIC; /* mark volume as potentially containing groove data allocations */
356 0 : FD_COMPILER_MFENCE();
357 :
358 : //parent_idx = 0UL; /* See note above about initialization */
359 0 : superblock_off = (ulong)_volume->data - (ulong)_volume0;
360 :
361 0 : } else { /* Acquire a parent_szc object to use for the new superblock */
362 :
363 0 : int err = fd_groove_data_private_alloc_obj( data, parent_szc, &superblock_off, &parent_idx ); /* logs details */
364 0 : if( FD_UNLIKELY( err ) ) return err;
365 :
366 0 : }
367 :
368 0 : ulong superblock_align = FD_GROOVE_DATA_HDR_ALIGN;
369 0 : ulong superblock_sz = FD_GROOVE_BLOCK_FOOTPRINT - FD_GROOVE_DATA_HDR_FOOTPRINT + obj_footprint*obj_cnt;
370 :
371 0 : fd_groove_data_hdr_t * _superblock_hdr = (fd_groove_data_hdr_t *)(((ulong)_volume0) + superblock_off);
372 :
373 0 : # if FD_GROOVE_PARANOID
374 0 : if( FD_UNLIKELY( !( ((ulong)_volume0<(ulong)_superblock_hdr) & ((ulong)_superblock_hdr<(ulong)_volume1) &
375 0 : fd_ulong_is_aligned( (ulong)_superblock_hdr, FD_GROOVE_BLOCK_ALIGN ) ) ) ) {
376 0 : FD_LOG_WARNING(( "superblock not at a valid groove data local address" ));
377 0 : return FD_GROOVE_ERR_CORRUPT;
378 0 : }
379 0 : # endif
380 :
381 0 : *_superblock_hdr = fd_groove_data_hdr( FD_GROOVE_DATA_HDR_TYPE_SUPERBLOCK, parent_idx, obj_szc,
382 0 : superblock_align, fd_ulong_min( superblock_sz, (1UL<<25)-1UL ), 0UL /* no next */ );
383 0 : *(ulong *)(_superblock_hdr+1) = (1UL<<obj_cnt)-1UL; /* mark all objects in superblock as free */
384 0 : }
385 0 : }
386 :
387 : /* At this point, we have exclusive access to the superblock, there is
388 : at least one free block in it and only we can allocate blocks from
389 : it. (Other threads could free blocks to it concurrently though.)
390 : Allocate a free block. If there were more free blocks, put the
391 : superblock back into circulation as the active superblock for our
392 : cgroup. Otherwise, free will put in back into circulation when the
393 : application frees a block in it. See fd_alloc.c for details. */
394 :
395 0 : fd_groove_data_hdr_t * _superblock_hdr = (fd_groove_data_hdr_t *)(((ulong)_volume0) + superblock_off);
396 :
397 0 : ulong volatile * _free_objs = (ulong volatile *)(_superblock_hdr+1);
398 :
399 0 : # if FD_GROOVE_PARANOID
400 0 : if( FD_UNLIKELY( !( ((ulong)_volume0<(ulong)_superblock_hdr) & ((ulong)_superblock_hdr<(ulong)_volume1) &
401 0 : fd_ulong_is_aligned( (ulong)_superblock_hdr, FD_GROOVE_BLOCK_ALIGN ) ) ) ) {
402 0 : FD_LOG_WARNING(( "superblock not at a valid groove data local address" ));
403 0 : return FD_GROOVE_ERR_CORRUPT;
404 0 : }
405 :
406 0 : fd_groove_data_hdr_t superblock_hdr = *_superblock_hdr;
407 :
408 0 : ulong superblock_type = fd_groove_data_hdr_type( superblock_hdr );
409 0 : ulong superblock_szc = fd_groove_data_hdr_szc ( superblock_hdr );
410 :
411 0 : if( FD_UNLIKELY( !((superblock_type==FD_GROOVE_DATA_HDR_TYPE_SUPERBLOCK) & (superblock_szc==obj_szc)) ) ) {
412 0 : FD_LOG_WARNING(( "unexpected superblock header" ));
413 0 : return FD_GROOVE_ERR_CORRUPT;
414 0 : }
415 0 : # endif
416 :
417 0 : FD_COMPILER_MFENCE();
418 0 : ulong free_objs = *_free_objs;
419 0 : FD_COMPILER_MFENCE();
420 :
421 0 : # if FD_GROOVE_PARANOID
422 0 : if( FD_UNLIKELY( (!free_objs) | (!!fd_ulong_shift_right( free_objs, (int)obj_cnt )) ) ) {
423 0 : FD_LOG_WARNING(( "%s", (!free_objs) ? "full superblock in circulation" : "invalid free_objs bit field" ));
424 0 : return FD_GROOVE_ERR_CORRUPT;
425 0 : }
426 0 : # endif
427 :
428 0 : ulong obj = fd_ulong_lsb( free_objs );
429 :
430 0 : FD_COMPILER_MFENCE();
431 0 : # if FD_HAS_ATOMIC
432 0 : free_objs = FD_ATOMIC_FETCH_AND_SUB( _free_objs, obj ); /* Marginally better asm than FETCH_AND_AND */
433 : # else
434 : free_objs = *_free_objs;
435 : *_free_objs = free_objs & ~obj;
436 : # endif
437 0 : FD_COMPILER_MFENCE();
438 :
439 0 : # if FD_GROOVE_PARANOID
440 0 : if( FD_UNLIKELY( (!free_objs) | (!!fd_ulong_shift_right( free_objs, (int)obj_cnt )) ) ) {
441 0 : FD_LOG_WARNING(( "%s", (!free_objs) ? "full superblock in circulation" : "invalid free_objs bit field" ));
442 0 : return FD_GROOVE_ERR_CORRUPT;
443 0 : }
444 0 : # endif
445 :
446 0 : if( FD_LIKELY( free_objs!=obj ) ) {
447 0 : ulong displaced_superblock_off = fd_groove_data_private_active_displace( _active_slot, _volume0, superblock_off );
448 0 : if( FD_UNLIKELY( displaced_superblock_off ) )
449 0 : fd_groove_data_private_inactive_push( _inactive_stack, _volume0, displaced_superblock_off );
450 0 : }
451 :
452 : /* At this point, we've allocated the object */
453 :
454 0 : ulong obj_idx = (ulong)fd_ulong_find_lsb( obj );
455 :
456 0 : *_obj_off = superblock_off + FD_GROOVE_BLOCK_FOOTPRINT + obj_idx*obj_footprint;
457 0 : *_obj_idx = obj_idx;
458 0 : return FD_GROOVE_SUCCESS;
459 0 : }
460 :
461 : void *
462 : fd_groove_data_alloc( fd_groove_data_t * data,
463 : ulong align,
464 : ulong sz,
465 : ulong tag,
466 0 : int * _err ) {
467 :
468 0 : int stack_err[1];
469 0 : if( !_err ) _err = stack_err;
470 :
471 : /* Check input args */
472 :
473 0 : if( FD_UNLIKELY( !data ) ) {
474 0 : FD_LOG_WARNING(( "NULL data" ));
475 0 : *_err = FD_GROOVE_ERR_INVAL;
476 0 : return NULL;
477 0 : }
478 :
479 0 : align = fd_ulong_if( !!align, align, FD_GROOVE_DATA_ALLOC_ALIGN_DEFAULT );
480 0 : if( FD_UNLIKELY( !(fd_ulong_is_pow2( align ) & (align<=FD_GROOVE_DATA_ALLOC_ALIGN_MAX)) ) ) {
481 0 : FD_LOG_WARNING(( "bad align" ));
482 0 : *_err = FD_GROOVE_ERR_INVAL;
483 0 : return NULL;
484 0 : }
485 :
486 0 : ulong off_obj = fd_ulong_align_up( FD_GROOVE_DATA_HDR_FOOTPRINT, align );
487 0 : ulong footprint = fd_ulong_align_up( off_obj+sz, FD_GROOVE_BLOCK_ALIGN );
488 :
489 0 : if( FD_UNLIKELY( !((sz<footprint) & (footprint<=FD_GROOVE_DATA_ALLOC_FOOTPRINT_MAX)) ) ) {
490 0 : FD_LOG_WARNING(( "bad sz/align" ));
491 0 : *_err = FD_GROOVE_ERR_INVAL;
492 0 : return NULL;
493 0 : }
494 :
495 : /* Acquire an object from the tightest suitable sizeclass */
496 :
497 0 : ulong obj_szc = fd_groove_data_szc( footprint );
498 :
499 0 : ulong obj_off;
500 0 : ulong obj_idx;
501 0 : int err = fd_groove_data_private_alloc_obj( data, obj_szc, &obj_off, &obj_idx ); /* logs details */
502 0 : if( FD_UNLIKELY( err ) ) {
503 0 : *_err = err;
504 0 : return NULL;
505 0 : }
506 :
507 : /* Carve an allocation into it. */
508 :
509 0 : fd_groove_data_hdr_t * obj_hdr = (fd_groove_data_hdr_t *)((ulong)fd_groove_volume_pool_shele( data->volume_pool ) + obj_off);
510 :
511 0 : *obj_hdr = fd_groove_data_hdr( FD_GROOVE_DATA_HDR_TYPE_ALLOC, obj_idx, obj_szc, align, sz, tag );
512 :
513 0 : *_err = FD_GROOVE_SUCCESS;
514 0 : return (void *)((ulong)obj_hdr + off_obj);
515 0 : }
516 :
517 : int
518 : fd_groove_data_private_free( fd_groove_data_t * data,
519 : void * _obj,
520 0 : ulong exp_type ) {
521 :
522 : # if !FD_GROOVE_PARANOID
523 : (void)exp_type; /* Suppress unused warning if running without paranoia */
524 : # endif
525 :
526 0 : if( FD_UNLIKELY( !data ) ) {
527 0 : FD_LOG_WARNING(( "NULL data" ));
528 0 : return FD_GROOVE_ERR_INVAL;
529 0 : }
530 :
531 0 : if( FD_UNLIKELY( !_obj ) ) return FD_GROOVE_ERR_INVAL;
532 :
533 0 : fd_groove_data_hdr_t * _obj_hdr = fd_groove_data_object_hdr( _obj );
534 :
535 0 : fd_groove_volume_t * _volume0 = (fd_groove_volume_t *)fd_groove_data_volume0( data );
536 :
537 0 : # if FD_GROOVE_PARANOID
538 0 : fd_groove_volume_t * _volume1 = (fd_groove_volume_t *)fd_groove_data_volume1( data );
539 0 : if( FD_UNLIKELY( !( ((ulong)_volume0<=(ulong)_obj_hdr ) &
540 0 : ((ulong)_obj_hdr< (ulong)_volume1 ) &
541 0 : (fd_ulong_is_aligned( (ulong)_obj_hdr, FD_GROOVE_BLOCK_ALIGN )) ) ) ) {
542 0 : FD_LOG_WARNING(( "object not at a valid groove data local address" ));
543 0 : return FD_GROOVE_ERR_INVAL;
544 0 : }
545 0 : # endif
546 :
547 0 : fd_groove_data_hdr_t obj_hdr = *_obj_hdr;
548 :
549 0 : ulong obj_type = fd_groove_data_hdr_type( obj_hdr );
550 0 : ulong obj_idx = fd_groove_data_hdr_idx ( obj_hdr );
551 0 : ulong obj_szc = fd_groove_data_hdr_szc ( obj_hdr );
552 :
553 0 : #if FD_GROOVE_PARANOID
554 0 : if( FD_UNLIKELY( !((obj_type==exp_type) & (obj_szc<FD_GROOVE_DATA_SZC_CNT)) ) ) {
555 0 : FD_LOG_WARNING(( "object does not appear to be a groove data %s",
556 0 : exp_type==FD_GROOVE_DATA_HDR_TYPE_ALLOC ? "alloc" : "superblock" ));
557 0 : return FD_GROOVE_ERR_INVAL;
558 0 : }
559 0 : # endif
560 :
561 0 : obj_szc = fd_ulong_if( obj_type==FD_GROOVE_DATA_HDR_TYPE_ALLOC, obj_szc,
562 0 : (ulong)fd_groove_data_szc_cfg[ obj_szc ].parent_szc );
563 0 : ulong obj_cnt = (ulong)fd_groove_data_szc_cfg[ obj_szc ].obj_cnt;
564 0 : # if FD_GROOVE_PARANOID
565 0 : ulong obj_footprint = (ulong)fd_groove_data_szc_cfg[ obj_szc ].obj_footprint;
566 :
567 0 : ulong req_align = fd_groove_data_hdr_align( obj_hdr );
568 0 : ulong req_sz = fd_groove_data_hdr_sz ( obj_hdr );
569 0 : ulong req_footprint =
570 0 : fd_ulong_align_up( fd_ulong_align_up( FD_GROOVE_DATA_HDR_FOOTPRINT, req_align ) + req_sz, FD_GROOVE_BLOCK_ALIGN );
571 :
572 0 : if( FD_UNLIKELY( !( (obj_idx<obj_cnt ) &
573 0 : (fd_ulong_is_pow2( req_align ) ) &
574 0 : (req_align<=FD_GROOVE_BLOCK_ALIGN) &
575 0 : (req_footprint<=obj_footprint ) ) ) ) {
576 0 : FD_LOG_WARNING(( "object does not appear to be a groove data %s",
577 0 : exp_type==FD_GROOVE_DATA_HDR_TYPE_ALLOC ? "alloc" : "superblock" ));
578 0 : return FD_GROOVE_ERR_INVAL;
579 0 : }
580 0 : # endif
581 :
582 : /* At this point, we appear to have a valid allocated object. Mark
583 : the object as not valid and then free it.
584 :
585 : Note: marking the object as dead is optional. It is mostly a hint
586 : for diagnostics and for handholding as groove data users shouldn't
587 : be calling free on it again and alloc doesn't care about the state
588 : unallocated object memory. Most useful, marking the object as dead
589 : can detect double free scenarios.
590 :
591 : The below implementation is not robust against _concurrent_ double
592 : frees. Would probably have to use something like ATOMIC_CAS
593 : semantics on the object header bits to insure nobody freed the
594 : object behind our back. And since the free bit field update isn't
595 : atomic with marking the object as dead, would probably need further
596 : to do something like mark the object as freeing then update bit
597 : field and then mark object as dead, etc. */
598 :
599 0 : fd_groove_data_hdr_t * _superblock_hdr = fd_groove_data_superblock_hdr( _obj, obj_szc, obj_idx );
600 :
601 0 : ulong volatile * _free_objs = (ulong volatile *)(_superblock_hdr+1);
602 :
603 0 : ulong free_objs;
604 :
605 0 : ulong obj = 1UL << obj_idx;
606 :
607 0 : # if FD_GROOVE_PARANOID
608 0 : if( FD_UNLIKELY( !( ((ulong)_volume0<(ulong)_superblock_hdr) & ((ulong)_superblock_hdr<(ulong)_obj_hdr) &
609 0 : fd_ulong_is_aligned( (ulong)_superblock_hdr, FD_GROOVE_BLOCK_ALIGN ) ) ) ) {
610 0 : FD_LOG_WARNING(( "superblock not at a valid groove data local address" ));
611 0 : return FD_GROOVE_ERR_INVAL;
612 0 : }
613 :
614 0 : fd_groove_data_hdr_t superblock_hdr = *_superblock_hdr;
615 :
616 0 : ulong superblock_type = fd_groove_data_hdr_type( superblock_hdr );
617 0 : ulong superblock_szc = fd_groove_data_hdr_szc ( superblock_hdr );
618 :
619 0 : if( FD_UNLIKELY( !((superblock_type==FD_GROOVE_DATA_HDR_TYPE_SUPERBLOCK) & (superblock_szc==obj_szc)) ) ) {
620 0 : FD_LOG_WARNING(( "unexpected superblock header" ));
621 0 : return FD_GROOVE_ERR_INVAL;
622 0 : }
623 :
624 0 : FD_COMPILER_MFENCE();
625 0 : free_objs = *_free_objs;
626 0 : FD_COMPILER_MFENCE();
627 :
628 0 : if( FD_UNLIKELY( (free_objs & obj) | fd_ulong_shift_right( free_objs, (int)obj_cnt ) ) ) {
629 0 : FD_LOG_WARNING(( "%s", (free_objs & obj) ? "possible concurrent double free" : "invalid free_objs bit field" ));
630 0 : return FD_GROOVE_ERR_INVAL;
631 0 : }
632 :
633 0 : FD_COMPILER_MFENCE();
634 0 : _obj_hdr->bits = 0UL; /* sets object type to an invalid value */
635 0 : FD_COMPILER_MFENCE();
636 0 : # endif
637 :
638 0 : FD_COMPILER_MFENCE();
639 0 : # if FD_HAS_ATOMIC
640 0 : free_objs = FD_ATOMIC_FETCH_AND_ADD( _free_objs, obj ); /* Marginally better asm than FETCH_AND_OR */
641 : # else
642 : free_objs = *_free_objs;
643 : *_free_objs = free_objs | obj;
644 : # endif
645 0 : FD_COMPILER_MFENCE();
646 :
647 0 : # if FD_GROOVE_PARANOID
648 0 : if( FD_UNLIKELY( (free_objs & obj) | fd_ulong_shift_right( free_objs, (int)obj_cnt ) ) ) {
649 0 : FD_LOG_WARNING(( "%s", (free_objs & obj) ? "possible concurrent double free" : "invalid free_objs bit field" ));
650 0 : return FD_GROOVE_ERR_CORRUPT;
651 0 : }
652 0 : # endif
653 :
654 : /* At this point, we've freed the object. We might need to get the
655 : object's superblock back into circulation and/or free up excess
656 : empty superblocks for this sizeclass. */
657 :
658 0 : ulong free_cnt = (ulong)fd_ulong_popcnt( free_objs );
659 :
660 0 : if( FD_UNLIKELY( !free_cnt ) ) {
661 :
662 : /* At this point, the superblock was full before we freed it and
663 : thus not in circulation for use by fd_alloc. We need to get the
664 : superblock back into circulation. There are options for this
665 : with various subtle tradeoffs. See fd_alloc.c for details.
666 : (FIXME: amongst then, consider using allocation cgroup instead of
667 : the groove data instance's cgroup?) */
668 :
669 0 : ulong cgroup = fd_groove_data_cgroup_hint( data ) & (ulong)fd_groove_data_szc_cfg[ obj_szc ].cgroup_mask;
670 :
671 0 : ulong displaced_superblock_off =
672 0 : fd_groove_data_private_active_displace( data->active_slot + obj_szc + FD_GROOVE_DATA_SZC_CNT*cgroup,
673 0 : _volume0, (ulong)_superblock_hdr - (ulong)_volume0 );
674 :
675 0 : if( FD_UNLIKELY( displaced_superblock_off ) )
676 0 : fd_groove_data_private_inactive_push( data->inactive_stack + obj_szc, _volume0, displaced_superblock_off );
677 :
678 0 : } else if( FD_UNLIKELY( (free_cnt+1UL)==obj_cnt ) ) {
679 :
680 : /* At this point, the superblock was completely empty after we freed
681 : from it, hence it is still in circulation. If there is also a
682 : completely empty superblock on top of the inactive stack, we free
683 : that one for general reuse. This is more subtle than it looks,
684 : see fd_alloc.c for details. */
685 :
686 0 : ulong volatile * _inactive_stack = data->inactive_stack + obj_szc;
687 :
688 0 : ulong superblock_off = fd_groove_data_private_inactive_pop( _inactive_stack, _volume0 );
689 :
690 0 : if( FD_LIKELY( superblock_off ) ) {
691 :
692 0 : _superblock_hdr = (fd_groove_data_hdr_t *)((ulong)_volume0 + superblock_off);
693 :
694 0 : _free_objs = (ulong volatile *)(_superblock_hdr+1);
695 :
696 0 : # if FD_GROOVE_PARANOID
697 0 : if( FD_UNLIKELY( !( ((ulong)_volume0<(ulong)_superblock_hdr) & ((ulong)_superblock_hdr<(ulong)_volume1) &
698 0 : fd_ulong_is_aligned( (ulong)_superblock_hdr, FD_GROOVE_BLOCK_ALIGN ) ) ) ) {
699 0 : FD_LOG_WARNING(( "superblock not at a valid groove data local address" ));
700 0 : return FD_GROOVE_ERR_CORRUPT;
701 0 : }
702 :
703 0 : superblock_type = fd_groove_data_hdr_type( superblock_hdr );
704 0 : superblock_szc = fd_groove_data_hdr_szc ( superblock_hdr );
705 :
706 0 : if( FD_UNLIKELY( !((superblock_type==FD_GROOVE_DATA_HDR_TYPE_SUPERBLOCK) & (superblock_szc==obj_szc)) ) ) {
707 0 : FD_LOG_WARNING(( "unexpected superblock header" ));
708 0 : return FD_GROOVE_ERR_CORRUPT;
709 0 : }
710 0 : # endif
711 :
712 0 : FD_COMPILER_MFENCE();
713 0 : free_objs = *_free_objs;
714 0 : FD_COMPILER_MFENCE();
715 :
716 0 : # if FD_GROOVE_PARANOID
717 0 : if( FD_UNLIKELY( fd_ulong_shift_right( free_objs, (int)obj_cnt ) ) ) {
718 0 : FD_LOG_WARNING(( "invalid free_objs bit field" ));
719 0 : return FD_GROOVE_ERR_CORRUPT;
720 0 : }
721 0 : # endif
722 :
723 0 : free_cnt = (ulong)fd_ulong_popcnt( free_objs );
724 :
725 0 : if( FD_LIKELY( free_cnt<obj_cnt ) ) { /* inactive top was not completely empty, return to circulation */
726 :
727 0 : fd_groove_data_private_inactive_push( _inactive_stack, _volume0, superblock_off );
728 :
729 0 : } else if( FD_LIKELY( obj_szc<(FD_GROOVE_DATA_SZC_CNT-1UL) ) ) { /* completely empty and should free from parent sb */
730 :
731 0 : int err = fd_groove_data_private_free( data, _superblock_hdr+1, FD_GROOVE_DATA_HDR_TYPE_SUPERBLOCK ); /* offset the hdr */
732 0 : if( FD_UNLIKELY( err ) ) {
733 0 : FD_LOG_WARNING(( "superblock free failed (%i-%s)", err, fd_groove_strerror( err ) ));
734 0 : return FD_GROOVE_ERR_CORRUPT;
735 0 : }
736 :
737 0 : } else { /* completely empty and should free parent volume */
738 :
739 0 : ulong volume_off = superblock_off - FD_GROOVE_BLOCK_FOOTPRINT;
740 :
741 0 : fd_groove_volume_t * _volume = (fd_groove_volume_t *)((ulong)_volume0 + volume_off);
742 :
743 0 : # if FD_GROOVE_PARANOID
744 0 : if( FD_UNLIKELY( !( (_volume0<=_volume) & (_volume<_volume1) &
745 0 : fd_ulong_is_aligned( volume_off, FD_GROOVE_VOLUME_FOOTPRINT ) ) ) ) {
746 0 : FD_LOG_WARNING(( "volume not at a valid groove data local address" ));
747 0 : return FD_GROOVE_ERR_CORRUPT;
748 0 : }
749 :
750 0 : if( FD_UNLIKELY( !( (_volume->magic ==FD_GROOVE_VOLUME_MAGIC ) &
751 0 : (_volume->idx*FD_GROOVE_VOLUME_FOOTPRINT==volume_off ) &
752 0 : (_volume->info_sz <=FD_GROOVE_VOLUME_INFO_MAX) ) ) ) {
753 0 : FD_LOG_WARNING(( "unexpected volume header" ));
754 0 : return FD_GROOVE_ERR_CORRUPT;
755 0 : }
756 0 : # endif
757 :
758 0 : FD_COMPILER_MFENCE();
759 0 : _volume->magic = ~FD_GROOVE_VOLUME_MAGIC; /* mark volume as containing no groove data allocations */
760 0 : FD_COMPILER_MFENCE();
761 :
762 0 : int err = fd_groove_volume_pool_release( data->volume_pool, _volume, 1 /* blocking */ );
763 0 : if( FD_UNLIKELY( err ) ) {
764 0 : FD_LOG_WARNING(( "fd_groove_volume_pool_release failed (%i-%s)", err, fd_groove_volume_pool_strerror( err ) ));
765 0 : return FD_GROOVE_ERR_CORRUPT;
766 0 : }
767 :
768 0 : }
769 0 : }
770 0 : }
771 :
772 0 : return FD_GROOVE_SUCCESS;
773 0 : }
774 :
775 0 : #define TEST(c) do { \
776 0 : if( FD_UNLIKELY( !(c) ) ) { FD_LOG_WARNING(( "FAIL: %s", #c )); return FD_GROOVE_ERR_CORRUPT; } \
777 0 : } while(0)
778 :
779 : /* fd_groove_data_private_verify_superblock verifies the location
780 : superblock_off (relative to _volume0) seems to contain a valid
781 : superblock. groove data is located in the caller's address space at
782 : [_volume0,_volume1). exp_szc gives the expected sizeclass for the
783 : superblock. If in_circulation is non-zero, the superblock is known
784 : to be in circulation (i.e. contains at least one free object / is
785 : either any active or an inactive superblock / is available to alloc
786 : for allocation). Assumes _volume0, _volume1, exp_szc and the
787 : sizeclass configuration are valid. */
788 :
789 : static int
790 : fd_groove_data_private_verify_superblock( ulong superblock_off,
791 : ulong exp_szc,
792 : int in_circulation,
793 : int verify_descendents,
794 : fd_groove_volume_t const * _volume0,
795 0 : fd_groove_volume_t const * _volume1 ) {
796 :
797 : /* Verify superblock_off */
798 :
799 0 : fd_groove_data_hdr_t const * _superblock_hdr = (fd_groove_data_hdr_t const *)(((ulong)_volume0) + superblock_off);
800 :
801 0 : TEST( ((ulong)_volume0<(ulong)_superblock_hdr) & ((ulong)_superblock_hdr<(ulong)_volume1) );
802 0 : TEST( fd_ulong_is_aligned( (ulong)_superblock_hdr, FD_GROOVE_BLOCK_ALIGN ) );
803 :
804 : /* Verify superblock header */
805 :
806 0 : fd_groove_data_hdr_t hdr = *_superblock_hdr;
807 :
808 0 : TEST( fd_groove_data_hdr_type( hdr )==FD_GROOVE_DATA_HDR_TYPE_SUPERBLOCK );
809 :
810 0 : ulong szc = fd_groove_data_hdr_szc( hdr );
811 :
812 0 : TEST( szc==exp_szc );
813 :
814 0 : ulong obj_cnt = (ulong)fd_groove_data_szc_cfg[ szc ].obj_cnt;
815 0 : ulong obj_footprint = (ulong)fd_groove_data_szc_cfg[ szc ].obj_footprint;
816 0 : ulong parent_szc = (ulong)fd_groove_data_szc_cfg[ szc ].parent_szc;
817 :
818 0 : ulong parent_obj_idx = fd_groove_data_hdr_idx( hdr );
819 0 : ulong parent_obj_cnt = (parent_szc<FD_GROOVE_DATA_SZC_CNT) ? (ulong)fd_groove_data_szc_cfg[ parent_szc ].obj_cnt : 1UL;
820 : //ulong parent_obj_footprint = (parent_szc<FD_GROOVE_DATA_SZC_CNT) ? (ulong)fd_groove_data_szc_cfg[ parent_szc ].obj_footprint :
821 : // (FD_GROOVE_VOLUME_DATA_MAX - FD_GROOVE_BLOCK_FOOTPRINT);
822 :
823 0 : TEST( parent_obj_idx < parent_obj_cnt );
824 :
825 0 : TEST( fd_groove_data_hdr_align( hdr )==FD_GROOVE_DATA_HDR_ALIGN );
826 0 : TEST( fd_groove_data_hdr_sz ( hdr )==
827 0 : fd_ulong_min( FD_GROOVE_BLOCK_FOOTPRINT - FD_GROOVE_DATA_HDR_FOOTPRINT + obj_cnt*obj_footprint, (1UL<<25)-1UL ) );
828 :
829 0 : ulong free_objs = *(ulong const *)(_superblock_hdr+1);
830 :
831 0 : TEST( !fd_ulong_shift_right( free_objs, (int)obj_cnt ) ); /* valid free obj bit field */
832 0 : if( in_circulation ) TEST( !!free_objs ); /* at least 1 free obj for superblocks in circulation */
833 :
834 : /* Verify superblock object headers */
835 :
836 0 : ulong rem_objs = free_objs ^ fd_ulong_mask_lsb( (int)obj_cnt );
837 0 : while( rem_objs ) {
838 0 : ulong _idx = (ulong)fd_ulong_find_lsb( rem_objs );
839 :
840 0 : ulong child_obj_off = superblock_off + FD_GROOVE_BLOCK_FOOTPRINT + _idx*obj_footprint;
841 :
842 0 : fd_groove_data_hdr_t obj_hdr = *(fd_groove_data_hdr_t const *)((ulong)_volume0 + child_obj_off);
843 :
844 0 : ulong obj_type = fd_groove_data_hdr_type( obj_hdr );
845 0 : ulong obj_idx = fd_groove_data_hdr_idx ( obj_hdr );
846 0 : ulong obj_szc = fd_groove_data_hdr_szc ( obj_hdr );
847 :
848 0 : TEST( (obj_type==FD_GROOVE_DATA_HDR_TYPE_ALLOC) | (obj_type==FD_GROOVE_DATA_HDR_TYPE_SUPERBLOCK) );
849 0 : TEST( obj_idx==_idx );
850 0 : TEST( obj_szc< FD_GROOVE_DATA_SZC_CNT );
851 :
852 0 : TEST( fd_ulong_if( obj_type==FD_GROOVE_DATA_HDR_TYPE_ALLOC,
853 0 : obj_szc, (ulong)fd_groove_data_szc_cfg[ obj_szc ].parent_szc )==szc );
854 :
855 0 : ulong req_align = fd_groove_data_hdr_align( obj_hdr );
856 0 : ulong req_sz = fd_groove_data_hdr_sz ( obj_hdr );
857 : //ulong req_info = fd_groove_data_hdr_info ( obj_hdr );
858 :
859 0 : ulong req_footprint =
860 0 : fd_ulong_align_up( fd_ulong_align_up( FD_GROOVE_DATA_HDR_FOOTPRINT, req_align ) + req_sz, FD_GROOVE_BLOCK_ALIGN );
861 :
862 0 : TEST( fd_ulong_is_pow2( req_align ) );
863 0 : TEST( req_align <=FD_GROOVE_BLOCK_ALIGN );
864 0 : TEST( req_footprint<=obj_footprint );
865 :
866 : /* Note that recursion depth is bounded due to the finite number of
867 : sizeclasses and the validation above the children are respecting
868 : the szc hierarchy above. */
869 :
870 0 : if( (!!verify_descendents) & (obj_type==FD_GROOVE_DATA_HDR_TYPE_SUPERBLOCK) ) /* verify superblock descendents */
871 0 : TEST( !fd_groove_data_private_verify_superblock( child_obj_off, obj_szc, 0 /* don't know if in circulation */,
872 0 : verify_descendents, _volume0, _volume1 ) );
873 :
874 0 : rem_objs = fd_ulong_pop_lsb( rem_objs );
875 0 : }
876 :
877 0 : return FD_GROOVE_SUCCESS;
878 0 : }
879 :
880 : int
881 0 : fd_groove_data_verify( fd_groove_data_t const * data ) {
882 :
883 : /* Verify join */
884 :
885 0 : TEST( data );
886 0 : TEST( fd_ulong_is_aligned( (ulong)data, alignof(fd_groove_data_t) ) );
887 :
888 0 : fd_groove_volume_pool_t const * pool = data->volume_pool;
889 0 : ulong const * active_slot = data->active_slot;
890 0 : ulong const * inactive_stack = data->inactive_stack;
891 : /* cgroup_hint is arbitrary */
892 :
893 : /* Verify volume pool */
894 :
895 0 : TEST( !fd_groove_volume_pool_verify( pool ) );
896 :
897 0 : fd_groove_volume_pool_shmem_t const * shpool = (fd_groove_volume_pool_shmem_t const *)fd_groove_volume_pool_shpool_const( pool );
898 :
899 0 : fd_groove_volume_t const * _volume0 = (fd_groove_volume_t const *)fd_groove_volume_pool_shele_const ( pool );
900 0 : ulong volume_max = fd_groove_volume_pool_ele_max ( pool );
901 0 : fd_groove_volume_t const * _volume1 = _volume0 + volume_max;
902 :
903 0 : TEST( (!!_volume0) | (!volume_max) );
904 0 : TEST( _volume0<=_volume1 );
905 0 : TEST( fd_ulong_is_aligned( (ulong)_volume0, FD_GROOVE_VOLUME_ALIGN ) );
906 :
907 0 : ulong volume_idx = fd_groove_volume_pool_private_vidx_idx( shpool->ver_top );
908 0 : while( volume_idx<volume_max ) { /* note: cyclic check already done by volume_pool_verify above */
909 0 : TEST( _volume0[ volume_idx ].magic==~FD_GROOVE_VOLUME_MAGIC );
910 0 : TEST( _volume0[ volume_idx ].idx ==volume_idx );
911 0 : volume_idx = fd_groove_volume_pool_private_idx( _volume0[ volume_idx ].next );
912 0 : }
913 :
914 : /* Verify data shmem */
915 :
916 0 : fd_groove_data_shmem_t const * shdata = (fd_groove_data_shmem_t const *)fd_groove_data_shdata_const( data );
917 :
918 0 : TEST( fd_ulong_is_aligned( (ulong)shdata, fd_groove_data_align() ) );
919 :
920 0 : TEST( shdata->magic ==FD_GROOVE_DATA_MAGIC );
921 0 : TEST( shdata->volume_pool ==shpool );
922 0 : TEST( shdata->active_slot ==active_slot );
923 0 : TEST( shdata->inactive_stack==inactive_stack );
924 :
925 : /* Verify sizeclass configuration */
926 :
927 0 : for( ulong szc_idx=0UL; szc_idx<FD_GROOVE_DATA_SZC_CNT; szc_idx++ ) {
928 0 : ulong obj_cnt = (ulong)fd_groove_data_szc_cfg[ szc_idx ].obj_cnt;
929 0 : ulong obj_footprint = (ulong)fd_groove_data_szc_cfg[ szc_idx ].obj_footprint;
930 0 : ulong cgroup_mask = (ulong)fd_groove_data_szc_cfg[ szc_idx ].cgroup_mask;
931 0 : ulong parent_szc = (ulong)fd_groove_data_szc_cfg[ szc_idx ].parent_szc;
932 :
933 0 : ulong cgroup_cnt = cgroup_mask + 1UL;
934 :
935 0 : ulong superblock_footprint = FD_GROOVE_BLOCK_FOOTPRINT + obj_cnt*obj_footprint;
936 :
937 0 : ulong parent_obj_footprint = (parent_szc<FD_GROOVE_DATA_SZC_CNT) ?
938 0 : (ulong)fd_groove_data_szc_cfg[ parent_szc ].obj_footprint : (FD_GROOVE_VOLUME_DATA_MAX - FD_GROOVE_BLOCK_FOOTPRINT);
939 :
940 0 : TEST( (1UL<=obj_cnt) & (obj_cnt<=64UL) );
941 0 : TEST( fd_ulong_is_aligned( obj_footprint, FD_GROOVE_BLOCK_FOOTPRINT ) );
942 0 : TEST( fd_ulong_is_pow2( cgroup_cnt ) );
943 0 : TEST( parent_szc<=FD_GROOVE_DATA_SZC_CNT );
944 0 : TEST( superblock_footprint <= parent_obj_footprint );
945 0 : }
946 :
947 : /* Verify all active superblocks */
948 :
949 0 : for( ulong szc_idx=0UL; szc_idx<FD_GROOVE_DATA_SZC_CNT; szc_idx++ ) {
950 0 : ulong cgroup_cnt = (ulong)fd_groove_data_szc_cfg[ szc_idx ].cgroup_mask + 1UL;
951 0 : for( ulong cgroup_idx=0UL; cgroup_idx<cgroup_cnt; cgroup_idx++ ) {
952 0 : ulong superblock_off = active_slot[ szc_idx + FD_GROOVE_DATA_SZC_CNT*cgroup_idx ];
953 0 : if( !superblock_off ) continue;
954 :
955 0 : TEST( !fd_groove_data_private_verify_superblock( superblock_off, szc_idx, 1 /* is in circulation */,
956 0 : 0 /* don't verify children */, _volume0, _volume1 ) );
957 0 : fd_groove_data_hdr_t hdr = *(fd_groove_data_hdr_t const *)(((ulong)_volume0) + superblock_off);
958 0 : TEST( fd_groove_data_hdr_szc( hdr )==szc_idx );
959 0 : }
960 0 : }
961 :
962 : /* Verify all inactive superblocks for sizeclass szc_idx */
963 :
964 0 : for( ulong szc_idx=0UL; szc_idx<FD_GROOVE_DATA_SZC_CNT; szc_idx++ ) {
965 0 : ulong superblock_off = inactive_stack[ szc_idx ] & ~(FD_GROOVE_BLOCK_FOOTPRINT-1UL);
966 0 : ulong rem = volume_max*FD_GROOVE_VOLUME_FOOTPRINT / (2UL*FD_GROOVE_BLOCK_FOOTPRINT); /* FIXME: tighter bound? */
967 0 : while( superblock_off ) {
968 0 : FD_TEST( rem ); rem--; /* avoid cycles */
969 :
970 0 : TEST( !fd_groove_data_private_verify_superblock( superblock_off, szc_idx, 1 /* is in circulation */,
971 0 : 0 /* don't verify children */, _volume0, _volume1 ) );
972 0 : fd_groove_data_hdr_t hdr = *(fd_groove_data_hdr_t const *)(((ulong)_volume0) + superblock_off);
973 0 : TEST( fd_groove_data_hdr_szc( hdr )==szc_idx );
974 :
975 0 : superblock_off = fd_groove_data_hdr_info( hdr );
976 0 : }
977 0 : }
978 :
979 0 : return FD_GROOVE_SUCCESS;
980 0 : }
981 :
982 : int
983 : fd_groove_data_volume_verify( fd_groove_data_t const * data,
984 0 : fd_groove_volume_t const * _volume ) {
985 :
986 0 : TEST( data );
987 :
988 0 : fd_groove_volume_t const * _volume0 = (fd_groove_volume_t const *)fd_groove_data_volume0_const( data );
989 0 : fd_groove_volume_t const * _volume1 = (fd_groove_volume_t const *)fd_groove_data_volume1_const( data );
990 :
991 0 : ulong volume_off = (ulong)_volume - (ulong)_volume0;
992 :
993 0 : TEST( (_volume0<=_volume) & (_volume<_volume1) );
994 0 : TEST( fd_ulong_is_aligned( volume_off, FD_GROOVE_VOLUME_FOOTPRINT ) );
995 :
996 0 : ulong magic = _volume->magic;
997 0 : ulong idx = _volume->idx;
998 0 : ulong info_sz = _volume->info_sz;
999 :
1000 0 : TEST( (magic==FD_GROOVE_VOLUME_MAGIC) | (magic==~FD_GROOVE_VOLUME_MAGIC) );
1001 0 : TEST( idx*FD_GROOVE_VOLUME_FOOTPRINT==volume_off );
1002 0 : TEST( info_sz <=FD_GROOVE_VOLUME_INFO_MAX );
1003 :
1004 0 : if( magic==FD_GROOVE_VOLUME_MAGIC ) {
1005 0 : ulong superblock_off = volume_off + FD_GROOVE_BLOCK_FOOTPRINT;
1006 0 : ulong superblock_szc = FD_GROOVE_DATA_SZC_CNT-1UL;
1007 0 : TEST( !fd_groove_data_private_verify_superblock( superblock_off, superblock_szc, 0 /* don't know if in circulation */,
1008 0 : 1 /* verify children */, _volume0, _volume1 ) );
1009 0 : }
1010 :
1011 0 : return FD_GROOVE_SUCCESS;
1012 0 : }
1013 :
1014 : #undef TEST
|
