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 : int err;
327 6 : fd_groove_volume_t * _volume = fd_groove_volume_pool_acquire( data->volume_pool, NULL, 1 /* blocking */, &err );
328 :
329 6 : if( FD_UNLIKELY( !_volume ) ) {
330 3 : 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 3 : return FD_GROOVE_ERR_FULL;
335 3 : }
336 :
337 3 : # if FD_GROOVE_PARANOID
338 3 : ulong volume_off = (ulong)_volume - (ulong)_volume0;
339 :
340 3 : if( FD_UNLIKELY( !( (_volume0<=_volume) & (_volume<_volume1) &
341 3 : 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 3 : if( FD_UNLIKELY( !( (_volume->magic ==~FD_GROOVE_VOLUME_MAGIC ) &
347 3 : (_volume->idx*FD_GROOVE_VOLUME_FOOTPRINT==volume_off ) &
348 3 : (_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 3 : # endif
353 :
354 3 : FD_COMPILER_MFENCE();
355 3 : _volume->magic = FD_GROOVE_VOLUME_MAGIC; /* mark volume as potentially containing groove data allocations */
356 3 : FD_COMPILER_MFENCE();
357 :
358 : //parent_idx = 0UL; /* See note above about initialization */
359 3 : superblock_off = (ulong)_volume->data - (ulong)_volume0;
360 :
361 14370 : } else { /* Acquire a parent_szc object to use for the new superblock */
362 :
363 14370 : int err = fd_groove_data_private_alloc_obj( data, parent_szc, &superblock_off, &parent_idx ); /* logs details */
364 14370 : if( FD_UNLIKELY( err ) ) return err;
365 :
366 14370 : }
367 :
368 14340 : ulong superblock_align = FD_GROOVE_DATA_HDR_ALIGN;
369 14340 : ulong superblock_sz = FD_GROOVE_BLOCK_FOOTPRINT - FD_GROOVE_DATA_HDR_FOOTPRINT + obj_footprint*obj_cnt;
370 :
371 14340 : fd_groove_data_hdr_t * _superblock_hdr = (fd_groove_data_hdr_t *)(((ulong)_volume0) + superblock_off);
372 :
373 14340 : # if FD_GROOVE_PARANOID
374 14340 : if( FD_UNLIKELY( !( ((ulong)_volume0<(ulong)_superblock_hdr) & ((ulong)_superblock_hdr<(ulong)_volume1) &
375 14340 : 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 14340 : # endif
380 :
381 14340 : *_superblock_hdr = fd_groove_data_hdr( FD_GROOVE_DATA_HDR_TYPE_SUPERBLOCK, parent_idx, obj_szc,
382 14340 : superblock_align, fd_ulong_min( superblock_sz, (1UL<<25)-1UL ), 0UL /* no next */ );
383 14340 : *(ulong *)(_superblock_hdr+1) = (1UL<<obj_cnt)-1UL; /* mark all objects in superblock as free */
384 14340 : }
385 996180 : }
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 2121639 : fd_groove_data_hdr_t * _superblock_hdr = (fd_groove_data_hdr_t *)(((ulong)_volume0) + superblock_off);
396 :
397 2121639 : ulong volatile * _free_objs = (ulong volatile *)(_superblock_hdr+1);
398 :
399 2121639 : # if FD_GROOVE_PARANOID
400 2121639 : if( FD_UNLIKELY( !( ((ulong)_volume0<(ulong)_superblock_hdr) & ((ulong)_superblock_hdr<(ulong)_volume1) &
401 2121639 : 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 2121639 : fd_groove_data_hdr_t superblock_hdr = *_superblock_hdr;
407 :
408 2121639 : ulong superblock_type = fd_groove_data_hdr_type( superblock_hdr );
409 2121639 : ulong superblock_szc = fd_groove_data_hdr_szc ( superblock_hdr );
410 :
411 2121639 : 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 2121639 : # endif
416 :
417 2121639 : FD_COMPILER_MFENCE();
418 2121639 : ulong free_objs = *_free_objs;
419 2121639 : FD_COMPILER_MFENCE();
420 :
421 2121639 : # if FD_GROOVE_PARANOID
422 2121639 : 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 2121639 : # endif
427 :
428 2121639 : ulong obj = fd_ulong_lsb( free_objs );
429 :
430 2121639 : FD_COMPILER_MFENCE();
431 2121639 : # if FD_HAS_ATOMIC
432 2121639 : 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 2121639 : FD_COMPILER_MFENCE();
438 :
439 2121639 : # if FD_GROOVE_PARANOID
440 2121639 : 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 2121639 : # endif
445 :
446 2121639 : if( FD_LIKELY( free_objs!=obj ) ) {
447 218265 : ulong displaced_superblock_off = fd_groove_data_private_active_displace( _active_slot, _volume0, superblock_off );
448 218265 : if( FD_UNLIKELY( displaced_superblock_off ) )
449 0 : fd_groove_data_private_inactive_push( _inactive_stack, _volume0, displaced_superblock_off );
450 218265 : }
451 :
452 : /* At this point, we've allocated the object */
453 :
454 2121639 : ulong obj_idx = (ulong)fd_ulong_find_lsb( obj );
455 :
456 2121639 : *_obj_off = superblock_off + FD_GROOVE_BLOCK_FOOTPRINT + obj_idx*obj_footprint;
457 2121639 : *_obj_idx = obj_idx;
458 2121639 : return FD_GROOVE_SUCCESS;
459 2121639 : }
460 :
461 : void *
462 : fd_groove_data_alloc( fd_groove_data_t * data,
463 : ulong align,
464 : ulong sz,
465 : ulong tag,
466 2107329 : int * _err ) {
467 :
468 2107329 : int stack_err[1];
469 2107329 : if( !_err ) _err = stack_err;
470 :
471 : /* Check input args */
472 :
473 2107329 : if( FD_UNLIKELY( !data ) ) {
474 6 : FD_LOG_WARNING(( "NULL data" ));
475 6 : *_err = FD_GROOVE_ERR_INVAL;
476 6 : return NULL;
477 6 : }
478 :
479 2107323 : align = fd_ulong_if( !!align, align, FD_GROOVE_DATA_ALLOC_ALIGN_DEFAULT );
480 2107323 : if( FD_UNLIKELY( !(fd_ulong_is_pow2( align ) & (align<=FD_GROOVE_DATA_ALLOC_ALIGN_MAX)) ) ) {
481 12 : FD_LOG_WARNING(( "bad align" ));
482 12 : *_err = FD_GROOVE_ERR_INVAL;
483 12 : return NULL;
484 12 : }
485 :
486 2107311 : ulong off_obj = fd_ulong_align_up( FD_GROOVE_DATA_HDR_FOOTPRINT, align );
487 2107311 : ulong footprint = fd_ulong_align_up( off_obj+sz, FD_GROOVE_BLOCK_ALIGN );
488 :
489 2107311 : if( FD_UNLIKELY( !((sz<footprint) & (footprint<=FD_GROOVE_DATA_ALLOC_FOOTPRINT_MAX)) ) ) {
490 6 : FD_LOG_WARNING(( "bad sz/align" ));
491 6 : *_err = FD_GROOVE_ERR_INVAL;
492 6 : return NULL;
493 6 : }
494 :
495 : /* Acquire an object from the tightest suitable sizeclass */
496 :
497 2107305 : ulong obj_szc = fd_groove_data_szc( footprint );
498 :
499 2107305 : ulong obj_off;
500 2107305 : ulong obj_idx;
501 2107305 : int err = fd_groove_data_private_alloc_obj( data, obj_szc, &obj_off, &obj_idx ); /* logs details */
502 2107305 : if( FD_UNLIKELY( err ) ) {
503 3 : *_err = err;
504 3 : return NULL;
505 3 : }
506 :
507 : /* Carve an allocation into it. */
508 :
509 2107302 : 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 2107302 : *obj_hdr = fd_groove_data_hdr( FD_GROOVE_DATA_HDR_TYPE_ALLOC, obj_idx, obj_szc, align, sz, tag );
512 :
513 2107302 : *_err = FD_GROOVE_SUCCESS;
514 2107302 : return (void *)((ulong)obj_hdr + off_obj);
515 2107305 : }
516 :
517 : int
518 : fd_groove_data_private_free( fd_groove_data_t * data,
519 : void * _obj,
520 2109834 : ulong exp_type ) {
521 :
522 : # if !FD_GROOVE_PARANOID
523 : (void)exp_type; /* Suppress unused warning if running without paranoia */
524 : # endif
525 :
526 2109834 : if( FD_UNLIKELY( !data ) ) {
527 3 : FD_LOG_WARNING(( "NULL data" ));
528 3 : return FD_GROOVE_ERR_INVAL;
529 3 : }
530 :
531 2109831 : if( FD_UNLIKELY( !_obj ) ) return FD_GROOVE_ERR_INVAL;
532 :
533 2109828 : fd_groove_data_hdr_t * _obj_hdr = fd_groove_data_object_hdr( _obj );
534 :
535 2109828 : fd_groove_volume_t * _volume0 = (fd_groove_volume_t *)fd_groove_data_volume0( data );
536 :
537 2109828 : # if FD_GROOVE_PARANOID
538 2109828 : fd_groove_volume_t * _volume1 = (fd_groove_volume_t *)fd_groove_data_volume1( data );
539 2109828 : if( FD_UNLIKELY( !( ((ulong)_volume0<=(ulong)_obj_hdr ) &
540 2109828 : ((ulong)_obj_hdr< (ulong)_volume1 ) &
541 2109828 : (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 2109828 : # endif
546 :
547 2109828 : fd_groove_data_hdr_t obj_hdr = *_obj_hdr;
548 :
549 2109828 : ulong obj_type = fd_groove_data_hdr_type( obj_hdr );
550 2109828 : ulong obj_idx = fd_groove_data_hdr_idx ( obj_hdr );
551 2109828 : ulong obj_szc = fd_groove_data_hdr_szc ( obj_hdr );
552 :
553 2109828 : #if FD_GROOVE_PARANOID
554 2109828 : 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 2109828 : # endif
560 :
561 2109828 : obj_szc = fd_ulong_if( obj_type==FD_GROOVE_DATA_HDR_TYPE_ALLOC, obj_szc,
562 2109828 : (ulong)fd_groove_data_szc_cfg[ obj_szc ].parent_szc );
563 2109828 : ulong obj_cnt = (ulong)fd_groove_data_szc_cfg[ obj_szc ].obj_cnt;
564 2109828 : # if FD_GROOVE_PARANOID
565 2109828 : ulong obj_footprint = (ulong)fd_groove_data_szc_cfg[ obj_szc ].obj_footprint;
566 :
567 2109828 : ulong req_align = fd_groove_data_hdr_align( obj_hdr );
568 2109828 : ulong req_sz = fd_groove_data_hdr_sz ( obj_hdr );
569 2109828 : ulong req_footprint =
570 2109828 : fd_ulong_align_up( fd_ulong_align_up( FD_GROOVE_DATA_HDR_FOOTPRINT, req_align ) + req_sz, FD_GROOVE_BLOCK_ALIGN );
571 :
572 2109828 : if( FD_UNLIKELY( !( (obj_idx<obj_cnt ) &
573 2109828 : (fd_ulong_is_pow2( req_align ) ) &
574 2109828 : (req_align<=FD_GROOVE_BLOCK_ALIGN) &
575 2109828 : (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 2109828 : # 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 2109828 : fd_groove_data_hdr_t * _superblock_hdr = fd_groove_data_superblock_hdr( _obj, obj_szc, obj_idx );
600 :
601 2109828 : ulong volatile * _free_objs = (ulong volatile *)(_superblock_hdr+1);
602 :
603 2109828 : ulong free_objs;
604 :
605 2109828 : ulong obj = 1UL << obj_idx;
606 :
607 2109828 : # if FD_GROOVE_PARANOID
608 2109828 : if( FD_UNLIKELY( !( ((ulong)_volume0<(ulong)_superblock_hdr) & ((ulong)_superblock_hdr<(ulong)_obj_hdr) &
609 2109828 : 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 2109828 : fd_groove_data_hdr_t superblock_hdr = *_superblock_hdr;
615 :
616 2109828 : ulong superblock_type = fd_groove_data_hdr_type( superblock_hdr );
617 2109828 : ulong superblock_szc = fd_groove_data_hdr_szc ( superblock_hdr );
618 :
619 2109828 : 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 2109828 : FD_COMPILER_MFENCE();
625 2109828 : free_objs = *_free_objs;
626 2109828 : FD_COMPILER_MFENCE();
627 :
628 2109828 : 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 2109828 : FD_COMPILER_MFENCE();
634 2109828 : _obj_hdr->bits = 0UL; /* sets object type to an invalid value */
635 2109828 : FD_COMPILER_MFENCE();
636 2109828 : # endif
637 :
638 2109828 : FD_COMPILER_MFENCE();
639 2109828 : # if FD_HAS_ATOMIC
640 2109828 : 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 2109828 : FD_COMPILER_MFENCE();
646 :
647 2109828 : # if FD_GROOVE_PARANOID
648 2109828 : 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 2109828 : # 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 2109828 : ulong free_cnt = (ulong)fd_ulong_popcnt( free_objs );
659 :
660 2109828 : 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 1898571 : ulong cgroup = fd_groove_data_cgroup_hint( data ) & (ulong)fd_groove_data_szc_cfg[ obj_szc ].cgroup_mask;
670 :
671 1898571 : ulong displaced_superblock_off =
672 1898571 : fd_groove_data_private_active_displace( data->active_slot + obj_szc + FD_GROOVE_DATA_SZC_CNT*cgroup,
673 1898571 : _volume0, (ulong)_superblock_hdr - (ulong)_volume0 );
674 :
675 1898571 : if( FD_UNLIKELY( displaced_superblock_off ) )
676 991227 : fd_groove_data_private_inactive_push( data->inactive_stack + obj_szc, _volume0, displaced_superblock_off );
677 :
678 1898571 : } 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 32361 : ulong volatile * _inactive_stack = data->inactive_stack + obj_szc;
687 :
688 32361 : ulong superblock_off = fd_groove_data_private_inactive_pop( _inactive_stack, _volume0 );
689 :
690 32361 : if( FD_LIKELY( superblock_off ) ) {
691 :
692 31788 : _superblock_hdr = (fd_groove_data_hdr_t *)((ulong)_volume0 + superblock_off);
693 :
694 31788 : _free_objs = (ulong volatile *)(_superblock_hdr+1);
695 :
696 31788 : # if FD_GROOVE_PARANOID
697 31788 : if( FD_UNLIKELY( !( ((ulong)_volume0<(ulong)_superblock_hdr) & ((ulong)_superblock_hdr<(ulong)_volume1) &
698 31788 : 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 31788 : superblock_type = fd_groove_data_hdr_type( superblock_hdr );
704 31788 : superblock_szc = fd_groove_data_hdr_szc ( superblock_hdr );
705 :
706 31788 : 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 31788 : # endif
711 :
712 31788 : FD_COMPILER_MFENCE();
713 31788 : free_objs = *_free_objs;
714 31788 : FD_COMPILER_MFENCE();
715 :
716 31788 : # if FD_GROOVE_PARANOID
717 31788 : 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 31788 : # endif
722 :
723 31788 : free_cnt = (ulong)fd_ulong_popcnt( free_objs );
724 :
725 31788 : if( FD_LIKELY( free_cnt<obj_cnt ) ) { /* inactive top was not completely empty, return to circulation */
726 :
727 29262 : fd_groove_data_private_inactive_push( _inactive_stack, _volume0, superblock_off );
728 :
729 29262 : } else if( FD_LIKELY( obj_szc<(FD_GROOVE_DATA_SZC_CNT-1UL) ) ) { /* completely empty and should free from parent sb */
730 :
731 2526 : int err = fd_groove_data_private_free( data, _superblock_hdr+1, FD_GROOVE_DATA_HDR_TYPE_SUPERBLOCK ); /* offset the hdr */
732 2526 : 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 2526 : } 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 31788 : }
770 32361 : }
771 :
772 2109828 : return FD_GROOVE_SUCCESS;
773 2109828 : }
774 :
775 619491 : #define TEST(c) do { \
776 619491 : if( FD_UNLIKELY( !(c) ) ) { FD_LOG_WARNING(( "FAIL: %s", #c )); return FD_GROOVE_ERR_CORRUPT; } \
777 619491 : } 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 32169 : fd_groove_volume_t const * _volume1 ) {
796 :
797 : /* Verify superblock_off */
798 :
799 32169 : fd_groove_data_hdr_t const * _superblock_hdr = (fd_groove_data_hdr_t const *)(((ulong)_volume0) + superblock_off);
800 :
801 32169 : TEST( ((ulong)_volume0<(ulong)_superblock_hdr) & ((ulong)_superblock_hdr<(ulong)_volume1) );
802 32169 : TEST( fd_ulong_is_aligned( (ulong)_superblock_hdr, FD_GROOVE_BLOCK_ALIGN ) );
803 :
804 : /* Verify superblock header */
805 :
806 32169 : fd_groove_data_hdr_t hdr = *_superblock_hdr;
807 :
808 32169 : TEST( fd_groove_data_hdr_type( hdr )==FD_GROOVE_DATA_HDR_TYPE_SUPERBLOCK );
809 :
810 32169 : ulong szc = fd_groove_data_hdr_szc( hdr );
811 :
812 32169 : TEST( szc==exp_szc );
813 :
814 32169 : ulong obj_cnt = (ulong)fd_groove_data_szc_cfg[ szc ].obj_cnt;
815 32169 : ulong obj_footprint = (ulong)fd_groove_data_szc_cfg[ szc ].obj_footprint;
816 32169 : ulong parent_szc = (ulong)fd_groove_data_szc_cfg[ szc ].parent_szc;
817 :
818 32169 : ulong parent_obj_idx = fd_groove_data_hdr_idx( hdr );
819 32169 : 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 32169 : TEST( parent_obj_idx < parent_obj_cnt );
824 :
825 32169 : TEST( fd_groove_data_hdr_align( hdr )==FD_GROOVE_DATA_HDR_ALIGN );
826 32169 : TEST( fd_groove_data_hdr_sz ( hdr )==
827 32169 : fd_ulong_min( FD_GROOVE_BLOCK_FOOTPRINT - FD_GROOVE_DATA_HDR_FOOTPRINT + obj_cnt*obj_footprint, (1UL<<25)-1UL ) );
828 :
829 32169 : ulong free_objs = *(ulong const *)(_superblock_hdr+1);
830 :
831 32169 : TEST( !fd_ulong_shift_right( free_objs, (int)obj_cnt ) ); /* valid free obj bit field */
832 32169 : if( in_circulation ) TEST( !!free_objs ); /* at least 1 free obj for superblocks in circulation */
833 :
834 : /* Verify superblock object headers */
835 :
836 32169 : ulong rem_objs = free_objs ^ fd_ulong_mask_lsb( (int)obj_cnt );
837 76578 : while( rem_objs ) {
838 44409 : ulong _idx = (ulong)fd_ulong_find_lsb( rem_objs );
839 :
840 44409 : ulong child_obj_off = superblock_off + FD_GROOVE_BLOCK_FOOTPRINT + _idx*obj_footprint;
841 :
842 44409 : fd_groove_data_hdr_t obj_hdr = *(fd_groove_data_hdr_t const *)((ulong)_volume0 + child_obj_off);
843 :
844 44409 : ulong obj_type = fd_groove_data_hdr_type( obj_hdr );
845 44409 : ulong obj_idx = fd_groove_data_hdr_idx ( obj_hdr );
846 44409 : ulong obj_szc = fd_groove_data_hdr_szc ( obj_hdr );
847 :
848 44409 : TEST( (obj_type==FD_GROOVE_DATA_HDR_TYPE_ALLOC) | (obj_type==FD_GROOVE_DATA_HDR_TYPE_SUPERBLOCK) );
849 44409 : TEST( obj_idx==_idx );
850 44409 : TEST( obj_szc< FD_GROOVE_DATA_SZC_CNT );
851 :
852 44409 : TEST( fd_ulong_if( obj_type==FD_GROOVE_DATA_HDR_TYPE_ALLOC,
853 44409 : obj_szc, (ulong)fd_groove_data_szc_cfg[ obj_szc ].parent_szc )==szc );
854 :
855 44409 : ulong req_align = fd_groove_data_hdr_align( obj_hdr );
856 44409 : ulong req_sz = fd_groove_data_hdr_sz ( obj_hdr );
857 : //ulong req_info = fd_groove_data_hdr_info ( obj_hdr );
858 :
859 44409 : ulong req_footprint =
860 44409 : fd_ulong_align_up( fd_ulong_align_up( FD_GROOVE_DATA_HDR_FOOTPRINT, req_align ) + req_sz, FD_GROOVE_BLOCK_ALIGN );
861 :
862 44409 : TEST( fd_ulong_is_pow2( req_align ) );
863 44409 : TEST( req_align <=FD_GROOVE_BLOCK_ALIGN );
864 44409 : 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 44409 : if( (!!verify_descendents) & (obj_type==FD_GROOVE_DATA_HDR_TYPE_SUPERBLOCK) ) /* verify superblock descendents */
871 23910 : TEST( !fd_groove_data_private_verify_superblock( child_obj_off, obj_szc, 0 /* don't know if in circulation */,
872 44409 : verify_descendents, _volume0, _volume1 ) );
873 :
874 44409 : rem_objs = fd_ulong_pop_lsb( rem_objs );
875 44409 : }
876 :
877 32169 : return FD_GROOVE_SUCCESS;
878 32169 : }
879 :
880 : int
881 15 : fd_groove_data_verify( fd_groove_data_t const * data ) {
882 :
883 : /* Verify join */
884 :
885 15 : TEST( data );
886 15 : TEST( fd_ulong_is_aligned( (ulong)data, alignof(fd_groove_data_t) ) );
887 :
888 15 : fd_groove_volume_pool_t const * pool = data->volume_pool;
889 15 : ulong const * active_slot = data->active_slot;
890 15 : ulong const * inactive_stack = data->inactive_stack;
891 : /* cgroup_hint is arbitrary */
892 :
893 : /* Verify volume pool */
894 :
895 15 : TEST( !fd_groove_volume_pool_verify( pool ) );
896 :
897 15 : fd_groove_volume_pool_shmem_t const * shpool = (fd_groove_volume_pool_shmem_t const *)fd_groove_volume_pool_shpool_const( pool );
898 :
899 15 : fd_groove_volume_t const * _volume0 = (fd_groove_volume_t const *)fd_groove_volume_pool_shele_const ( pool );
900 15 : ulong volume_max = fd_groove_volume_pool_ele_max ( pool );
901 15 : fd_groove_volume_t const * _volume1 = _volume0 + volume_max;
902 :
903 15 : TEST( (!!_volume0) | (!volume_max) );
904 15 : TEST( _volume0<=_volume1 );
905 15 : TEST( fd_ulong_is_aligned( (ulong)_volume0, FD_GROOVE_VOLUME_ALIGN ) );
906 :
907 15 : ulong volume_idx = fd_groove_volume_pool_private_vidx_idx( shpool->ver_top );
908 15 : 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 15 : fd_groove_data_shmem_t const * shdata = (fd_groove_data_shmem_t const *)fd_groove_data_shdata_const( data );
917 :
918 15 : TEST( fd_ulong_is_aligned( (ulong)shdata, fd_groove_data_align() ) );
919 :
920 15 : TEST( shdata->magic ==FD_GROOVE_DATA_MAGIC );
921 15 : TEST( shdata->volume_pool ==shpool );
922 15 : TEST( shdata->active_slot ==active_slot );
923 15 : TEST( shdata->inactive_stack==inactive_stack );
924 :
925 : /* Verify sizeclass configuration */
926 :
927 495 : for( ulong szc_idx=0UL; szc_idx<FD_GROOVE_DATA_SZC_CNT; szc_idx++ ) {
928 480 : ulong obj_cnt = (ulong)fd_groove_data_szc_cfg[ szc_idx ].obj_cnt;
929 480 : ulong obj_footprint = (ulong)fd_groove_data_szc_cfg[ szc_idx ].obj_footprint;
930 480 : ulong cgroup_mask = (ulong)fd_groove_data_szc_cfg[ szc_idx ].cgroup_mask;
931 480 : ulong parent_szc = (ulong)fd_groove_data_szc_cfg[ szc_idx ].parent_szc;
932 :
933 480 : ulong cgroup_cnt = cgroup_mask + 1UL;
934 :
935 480 : ulong superblock_footprint = FD_GROOVE_BLOCK_FOOTPRINT + obj_cnt*obj_footprint;
936 :
937 480 : ulong parent_obj_footprint = (parent_szc<FD_GROOVE_DATA_SZC_CNT) ?
938 465 : (ulong)fd_groove_data_szc_cfg[ parent_szc ].obj_footprint : (FD_GROOVE_VOLUME_DATA_MAX - FD_GROOVE_BLOCK_FOOTPRINT);
939 :
940 480 : TEST( (1UL<=obj_cnt) & (obj_cnt<=64UL) );
941 480 : TEST( fd_ulong_is_aligned( obj_footprint, FD_GROOVE_BLOCK_FOOTPRINT ) );
942 480 : TEST( fd_ulong_is_pow2( cgroup_cnt ) );
943 480 : TEST( parent_szc<=FD_GROOVE_DATA_SZC_CNT );
944 480 : TEST( superblock_footprint <= parent_obj_footprint );
945 480 : }
946 :
947 : /* Verify all active superblocks */
948 :
949 495 : for( ulong szc_idx=0UL; szc_idx<FD_GROOVE_DATA_SZC_CNT; szc_idx++ ) {
950 480 : ulong cgroup_cnt = (ulong)fd_groove_data_szc_cfg[ szc_idx ].cgroup_mask + 1UL;
951 12165 : for( ulong cgroup_idx=0UL; cgroup_idx<cgroup_cnt; cgroup_idx++ ) {
952 11685 : ulong superblock_off = active_slot[ szc_idx + FD_GROOVE_DATA_SZC_CNT*cgroup_idx ];
953 11685 : if( !superblock_off ) continue;
954 :
955 159 : TEST( !fd_groove_data_private_verify_superblock( superblock_off, szc_idx, 1 /* is in circulation */,
956 159 : 0 /* don't verify children */, _volume0, _volume1 ) );
957 159 : fd_groove_data_hdr_t hdr = *(fd_groove_data_hdr_t const *)(((ulong)_volume0) + superblock_off);
958 159 : TEST( fd_groove_data_hdr_szc( hdr )==szc_idx );
959 159 : }
960 480 : }
961 :
962 : /* Verify all inactive superblocks for sizeclass szc_idx */
963 :
964 495 : for( ulong szc_idx=0UL; szc_idx<FD_GROOVE_DATA_SZC_CNT; szc_idx++ ) {
965 480 : ulong superblock_off = inactive_stack[ szc_idx ] & ~(FD_GROOVE_BLOCK_FOOTPRINT-1UL);
966 480 : ulong rem = volume_max*FD_GROOVE_VOLUME_FOOTPRINT / (2UL*FD_GROOVE_BLOCK_FOOTPRINT); /* FIXME: tighter bound? */
967 8574 : while( superblock_off ) {
968 8094 : FD_TEST( rem ); rem--; /* avoid cycles */
969 :
970 8094 : TEST( !fd_groove_data_private_verify_superblock( superblock_off, szc_idx, 1 /* is in circulation */,
971 8094 : 0 /* don't verify children */, _volume0, _volume1 ) );
972 8094 : fd_groove_data_hdr_t hdr = *(fd_groove_data_hdr_t const *)(((ulong)_volume0) + superblock_off);
973 8094 : TEST( fd_groove_data_hdr_szc( hdr )==szc_idx );
974 :
975 8094 : superblock_off = fd_groove_data_hdr_info( hdr );
976 8094 : }
977 480 : }
978 :
979 15 : return FD_GROOVE_SUCCESS;
980 15 : }
981 :
982 : int
983 : fd_groove_data_volume_verify( fd_groove_data_t const * data,
984 6 : fd_groove_volume_t const * _volume ) {
985 :
986 6 : TEST( data );
987 :
988 6 : fd_groove_volume_t const * _volume0 = (fd_groove_volume_t const *)fd_groove_data_volume0_const( data );
989 6 : fd_groove_volume_t const * _volume1 = (fd_groove_volume_t const *)fd_groove_data_volume1_const( data );
990 :
991 6 : ulong volume_off = (ulong)_volume - (ulong)_volume0;
992 :
993 6 : TEST( (_volume0<=_volume) & (_volume<_volume1) );
994 6 : TEST( fd_ulong_is_aligned( volume_off, FD_GROOVE_VOLUME_FOOTPRINT ) );
995 :
996 6 : ulong magic = _volume->magic;
997 6 : ulong idx = _volume->idx;
998 6 : ulong info_sz = _volume->info_sz;
999 :
1000 6 : TEST( (magic==FD_GROOVE_VOLUME_MAGIC) | (magic==~FD_GROOVE_VOLUME_MAGIC) );
1001 6 : TEST( idx*FD_GROOVE_VOLUME_FOOTPRINT==volume_off );
1002 6 : TEST( info_sz <=FD_GROOVE_VOLUME_INFO_MAX );
1003 :
1004 6 : if( magic==FD_GROOVE_VOLUME_MAGIC ) {
1005 6 : ulong superblock_off = volume_off + FD_GROOVE_BLOCK_FOOTPRINT;
1006 6 : ulong superblock_szc = FD_GROOVE_DATA_SZC_CNT-1UL;
1007 6 : TEST( !fd_groove_data_private_verify_superblock( superblock_off, superblock_szc, 0 /* don't know if in circulation */,
1008 6 : 1 /* verify children */, _volume0, _volume1 ) );
1009 6 : }
1010 :
1011 6 : return FD_GROOVE_SUCCESS;
1012 6 : }
1013 :
1014 : #undef TEST
|
