Line data Source code
1 : #include "fd_ghost.h"
2 : #include "fd_ghost_private.h"
3 :
4 : ulong
5 507 : fd_ghost_align( void ) {
6 507 : return alignof(fd_ghost_t);
7 507 : }
8 :
9 : ulong
10 : fd_ghost_footprint( ulong blk_max,
11 96 : ulong vtr_max ) {
12 96 : ulong blk_chain_cnt = blk_map_chain_cnt_est( blk_max );
13 96 : ulong vtr_chain_cnt = vtr_map_chain_cnt_est( vtr_max );
14 :
15 96 : return FD_LAYOUT_FINI(
16 96 : FD_LAYOUT_APPEND(
17 96 : FD_LAYOUT_APPEND(
18 96 : FD_LAYOUT_APPEND(
19 96 : FD_LAYOUT_APPEND(
20 96 : FD_LAYOUT_APPEND(
21 96 : FD_LAYOUT_INIT,
22 96 : alignof(fd_ghost_t), sizeof(fd_ghost_t) ),
23 96 : blk_pool_align(), blk_pool_footprint( blk_max ) ),
24 96 : blk_map_align(), blk_map_footprint ( blk_chain_cnt ) ),
25 96 : vtr_pool_align(), vtr_pool_footprint( vtr_max ) ),
26 96 : vtr_map_align(), vtr_map_footprint ( vtr_chain_cnt ) ),
27 96 : fd_ghost_align() );
28 96 : }
29 :
30 : void *
31 : fd_ghost_new( void * shmem,
32 : ulong blk_max,
33 : ulong vtr_max,
34 48 : ulong seed ) {
35 :
36 48 : if( FD_UNLIKELY( !shmem ) ) {
37 0 : FD_LOG_WARNING(( "NULL mem" ));
38 0 : return NULL;
39 0 : }
40 :
41 48 : if( FD_UNLIKELY( !fd_ulong_is_aligned( (ulong)shmem, fd_ghost_align() ) ) ) {
42 0 : FD_LOG_WARNING(( "misaligned mem" ));
43 0 : return NULL;
44 0 : }
45 :
46 48 : ulong footprint = fd_ghost_footprint( blk_max, vtr_max );
47 48 : if( FD_UNLIKELY( !footprint ) ) {
48 0 : FD_LOG_WARNING(( "bad blk_max (%lu)", blk_max ));
49 0 : return NULL;
50 0 : }
51 :
52 48 : fd_wksp_t * wksp = fd_wksp_containing( shmem );
53 48 : if( FD_UNLIKELY( !wksp ) ) {
54 0 : FD_LOG_WARNING(( "shmem must be part of a workspace" ));
55 0 : return NULL;
56 0 : }
57 :
58 48 : fd_memset( shmem, 0, footprint );
59 :
60 48 : ulong blk_chain_cnt = blk_map_chain_cnt_est( blk_max );
61 48 : ulong vtr_chain_cnt = vtr_map_chain_cnt_est( vtr_max );
62 :
63 48 : FD_SCRATCH_ALLOC_INIT( l, shmem );
64 48 : fd_ghost_t * ghost = FD_SCRATCH_ALLOC_APPEND( l, alignof(fd_ghost_t), sizeof(fd_ghost_t) );
65 48 : void * blk_pool = FD_SCRATCH_ALLOC_APPEND( l, blk_pool_align(), blk_pool_footprint( blk_max ) );
66 48 : void * blk_map = FD_SCRATCH_ALLOC_APPEND( l, blk_map_align(), blk_map_footprint ( blk_chain_cnt ) );
67 48 : void * vtr_pool = FD_SCRATCH_ALLOC_APPEND( l, vtr_pool_align(), vtr_pool_footprint( vtr_max ) );
68 48 : void * vtr_map = FD_SCRATCH_ALLOC_APPEND( l, vtr_map_align(), vtr_map_footprint ( vtr_chain_cnt ) );
69 48 : FD_TEST( FD_SCRATCH_ALLOC_FINI( l, fd_ghost_align() ) == (ulong)shmem + footprint );
70 :
71 48 : ghost->root = ULONG_MAX;
72 48 : ghost->blk_pool_gaddr = fd_wksp_gaddr_fast( wksp, blk_pool_join( blk_pool_new ( blk_pool, blk_max ) ) );
73 48 : ghost->blk_map_gaddr = fd_wksp_gaddr_fast( wksp, blk_map_join ( blk_map_new ( blk_map, blk_chain_cnt, seed ) ) );
74 48 : ghost->vtr_pool_gaddr = fd_wksp_gaddr_fast( wksp, vtr_pool_join( vtr_pool_new ( vtr_pool, vtr_max ) ) );
75 48 : ghost->vtr_map_gaddr = fd_wksp_gaddr_fast( wksp, vtr_map_join ( vtr_map_new ( vtr_map, vtr_chain_cnt, seed ) ) );
76 :
77 48 : return shmem;
78 48 : }
79 :
80 : fd_ghost_t *
81 48 : fd_ghost_join( void * shghost ) {
82 48 : fd_ghost_t * ghost = (fd_ghost_t *)shghost;
83 :
84 48 : if( FD_UNLIKELY( !ghost ) ) {
85 0 : FD_LOG_WARNING(( "NULL ghost" ));
86 0 : return NULL;
87 0 : }
88 :
89 48 : if( FD_UNLIKELY( !fd_ulong_is_aligned((ulong)ghost, fd_ghost_align() ) ) ) {
90 0 : FD_LOG_WARNING(( "misaligned ghost" ));
91 0 : return NULL;
92 0 : }
93 :
94 48 : return ghost;
95 48 : }
96 :
97 : void *
98 36 : fd_ghost_leave( fd_ghost_t const * ghost ) {
99 :
100 36 : if( FD_UNLIKELY( !ghost ) ) {
101 0 : FD_LOG_WARNING(( "NULL ghost" ));
102 0 : return NULL;
103 0 : }
104 :
105 36 : return (void *)ghost;
106 36 : }
107 :
108 : void *
109 36 : fd_ghost_delete( void * ghost ) {
110 :
111 36 : if( FD_UNLIKELY( !ghost ) ) {
112 0 : FD_LOG_WARNING(( "NULL ghost" ));
113 0 : return NULL;
114 0 : }
115 :
116 36 : if( FD_UNLIKELY( !fd_ulong_is_aligned((ulong)ghost, fd_ghost_align() ) ) ) {
117 0 : FD_LOG_WARNING(( "misaligned ghost" ));
118 0 : return NULL;
119 0 : }
120 :
121 36 : return ghost;
122 36 : }
123 :
124 : fd_ghost_blk_t *
125 93 : fd_ghost_root( fd_ghost_t * ghost ) {
126 93 : return blk_pool_ele( blk_pool( ghost ), ghost->root );
127 93 : }
128 :
129 : fd_ghost_blk_t *
130 0 : fd_ghost_parent( fd_ghost_t * ghost, fd_ghost_blk_t * blk ) {
131 0 : return blk_pool_ele( blk_pool( ghost ), blk->parent );
132 0 : }
133 :
134 : fd_ghost_blk_t *
135 : fd_ghost_query( fd_ghost_t * ghost,
136 201 : fd_hash_t const * block_id ) {
137 201 : return blk_map_ele_query( blk_map( ghost ), block_id, NULL, blk_pool( ghost ) );
138 201 : }
139 :
140 : fd_ghost_blk_t *
141 : fd_ghost_best( fd_ghost_t * ghost,
142 21 : fd_ghost_blk_t * root ) {
143 21 : blk_pool_t * pool = blk_pool( ghost );
144 21 : ulong null = blk_pool_idx_null( pool );
145 21 : fd_ghost_blk_t * best = root;
146 84 : while( FD_LIKELY( best->child != null ) ) {
147 63 : int valid = 0; /* at least one child is valid */
148 63 : fd_ghost_blk_t * child = blk_pool_ele( pool, best->child );
149 141 : while( FD_LIKELY( child ) ) { /* greedily pick the heaviest valid child */
150 78 : if( FD_LIKELY( child->valid ) ) {
151 78 : if( FD_LIKELY( !valid ) ) { /* this is the first valid child, so progress the head */
152 63 : best = child;
153 63 : valid = 1;
154 63 : }
155 :
156 : /* When stake is equal, tie-break by lower slot. Two valid
157 : children with equal stake and equal slot (ie. equivocating
158 : blocks) cannot occur: equivocating blocks are marked valid=0,
159 : so at most one of them would be valid unless multiple blocks
160 : for that slot are duplicate confirmed, which is a consensus
161 : invariant violation. */
162 :
163 78 : best = fd_ptr_if(
164 78 : fd_int_if(
165 78 : child->stake == best->stake, /* if the weights are equal */
166 78 : child->slot < best->slot, /* then tie-break by lower slot number */
167 78 : child->stake > best->stake ), /* else return heavier */
168 78 : child, best );
169 78 : }
170 78 : child = blk_pool_ele( pool, child->sibling );
171 78 : }
172 63 : if( FD_UNLIKELY( !valid ) ) break; /* no children are valid, so short-circuit traversal */
173 63 : }
174 21 : return best;
175 21 : }
176 :
177 : fd_ghost_blk_t *
178 : fd_ghost_deepest( fd_ghost_t * ghost,
179 15 : fd_ghost_blk_t * root ) {
180 15 : blk_pool_t * pool = blk_pool( ghost );
181 15 : ulong null = blk_pool_idx_null( pool );
182 15 : fd_ghost_blk_t * head = blk_map_ele_remove( blk_map( ghost ), &root->id, NULL, pool ); /* remove ele from map to reuse `.next` */
183 15 : fd_ghost_blk_t * tail = head;
184 15 : fd_ghost_blk_t * prev = NULL;
185 :
186 : /* Below is a level-order traversal (BFS), returning the last leaf
187 : which is guaranteed to return an element of the max depth.
188 :
189 : It temporarily removes elements of the map when pushing onto the
190 : BFS queue to reuse the .next pointer and then inserts back into
191 : the map on queue pop. */
192 :
193 15 : head->next = null;
194 93 : while( FD_LIKELY( head ) ) {
195 78 : fd_ghost_blk_t const * child = blk_pool_ele( pool, head->child );
196 141 : while( FD_LIKELY( child ) ) {
197 63 : FD_TEST( blk_map_ele_remove( blk_map( ghost ), &child->id, NULL, pool ) ); /* in the tree so must be in the map */
198 63 : tail->next = blk_pool_idx( pool, child );
199 63 : tail = blk_pool_ele( pool, tail->next );
200 63 : tail->next = blk_pool_idx_null( pool );
201 63 : child = blk_pool_ele( pool, child->sibling ); /* next sibling */
202 63 : }
203 78 : fd_ghost_blk_t * next = blk_pool_ele( pool, head->next ); /* pop prune queue head */
204 78 : blk_map_ele_insert( blk_map( ghost ), head, pool ); /* re-insert head into map */
205 78 : prev = head;
206 78 : head = next;
207 78 : }
208 15 : return prev;
209 15 : }
210 :
211 0 : #define PREDICATE_ANCESTOR( predicate ) do { \
212 0 : fd_ghost_blk_t * ancestor = descendant; \
213 0 : while( FD_LIKELY( ancestor ) ) { \
214 0 : if( FD_LIKELY( predicate ) ) return ancestor; \
215 0 : ancestor = blk_pool_ele( blk_pool( ghost ), ancestor->parent ); \
216 0 : } \
217 0 : return NULL; \
218 0 : } while(0)
219 :
220 : fd_ghost_blk_t *
221 : fd_ghost_ancestor( fd_ghost_t * ghost,
222 : fd_ghost_blk_t * descendant,
223 0 : fd_hash_t const * ancestor_id ) {
224 0 : PREDICATE_ANCESTOR( 0==memcmp( &ancestor->id, ancestor_id, sizeof(fd_hash_t) ) );
225 0 : }
226 :
227 : fd_ghost_blk_t *
228 : fd_ghost_slot_ancestor( fd_ghost_t * ghost,
229 : fd_ghost_blk_t * descendant,
230 0 : ulong slot ) {
231 0 : PREDICATE_ANCESTOR( ancestor->slot == slot );
232 0 : }
233 :
234 : fd_ghost_blk_t *
235 : fd_ghost_invalid_ancestor( fd_ghost_t * ghost,
236 0 : fd_ghost_blk_t * descendant ) {
237 0 : PREDICATE_ANCESTOR( !ancestor->valid );
238 0 : }
239 :
240 : fd_ghost_blk_t *
241 : fd_ghost_insert( fd_ghost_t * ghost,
242 : fd_hash_t const * block_id,
243 : fd_hash_t const * parent_block_id,
244 330 : ulong slot ) {
245 :
246 330 : fd_ghost_blk_t * pool = blk_pool( ghost );
247 330 : ulong null = blk_pool_idx_null( pool );
248 330 : fd_ghost_blk_t * blk = blk_map_ele_query( blk_map( ghost ), block_id, NULL, pool );
249 :
250 330 : FD_TEST( !blk ); /* duplicate insert */
251 330 : FD_TEST( blk_pool_free( pool ) ); /* ghost full */
252 :
253 330 : blk = blk_pool_ele_acquire( pool );
254 330 : blk->id = *block_id;
255 330 : blk->slot = slot;
256 330 : blk->next = null;
257 330 : blk->parent = null;
258 330 : blk->child = null;
259 330 : blk->sibling = null;
260 330 : blk->stake = 0;
261 330 : blk->total_stake = 0;
262 330 : blk->valid = 1;
263 330 : blk_map_ele_insert( blk_map( ghost ), blk, pool );
264 :
265 330 : if( FD_UNLIKELY( !parent_block_id ) ) {
266 48 : ghost->root = blk_pool_idx( pool, blk );
267 48 : ghost->width = 1;
268 48 : return blk;
269 48 : }
270 :
271 282 : fd_ghost_blk_t * parent = blk_map_ele_query( blk_map( ghost ), parent_block_id, NULL, pool );
272 282 : FD_TEST( parent ); /* parent must exist if this is not the first insertion */
273 282 : blk->parent = blk_pool_idx( pool, parent );
274 282 : if( FD_LIKELY( parent->child == null ) ) {
275 213 : parent->child = blk_pool_idx( pool, blk ); /* left-child */
276 213 : } else {
277 69 : fd_ghost_blk_t * sibling = blk_pool_ele( pool, parent->child );
278 75 : while( sibling->sibling != null ) sibling = blk_pool_ele( pool, sibling->sibling );
279 69 : sibling->sibling = blk_pool_idx( pool, blk ); /* right-sibling */
280 69 : ghost->width++;
281 69 : }
282 :
283 282 : return blk;
284 282 : }
285 :
286 : int
287 : fd_ghost_count_vote( fd_ghost_t * ghost,
288 : fd_ghost_blk_t * blk,
289 : fd_pubkey_t const * vote_acc,
290 : ulong stake,
291 18 : ulong slot ) {
292 :
293 18 : fd_ghost_blk_t const * root = fd_ghost_root( ghost );
294 18 : fd_ghost_vtr_t * vtr = vtr_map_ele_query( vtr_map( ghost ), vote_acc, NULL, vtr_pool( ghost ) );
295 :
296 18 : if( FD_UNLIKELY( slot==ULONG_MAX ) ) return FD_GHOST_ERR_NOT_VOTED;
297 18 : if( FD_UNLIKELY( slot< root->slot ) ) return FD_GHOST_ERR_VOTE_TOO_OLD;
298 :
299 18 : if( FD_UNLIKELY( !vtr ) ) {
300 :
301 : /* This vote account address has not previously voted, so add it to
302 : the map of voters. */
303 :
304 9 : vtr = vtr_pool_ele_acquire( vtr_pool( ghost ) );
305 9 : vtr->addr = *vote_acc;
306 9 : vtr_map_ele_insert( vtr_map( ghost ), vtr, vtr_pool( ghost ) );
307 :
308 9 : } else {
309 :
310 : /* Only process the vote if it is not the same as the previous vote
311 : and also that the vote slot is most recent. It's possible for
312 : ghost to process votes out of order because votes happen in
313 : replay order which is concurrent across different forks.
314 :
315 : For example, if a voter votes for 3 then switches to 5, we might
316 : observe the vote for 5 before the vote for 3. */
317 :
318 9 : if( FD_UNLIKELY( !( slot > vtr->prev_slot ) ) ) return FD_GHOST_ERR_ALREADY_VOTED;
319 :
320 : /* LMD-rule: subtract the voter's stake from the entire fork they
321 : previously voted for. */
322 :
323 : /* TODO can optimize this if they're voting for the same fork */
324 :
325 6 : fd_ghost_blk_t * ancestor = blk_map_ele_query( blk_map( ghost ), &vtr->prev_block_id, NULL, blk_pool( ghost ) );
326 24 : while( FD_LIKELY( ancestor ) ) {
327 18 : int cf = __builtin_usubl_overflow( ancestor->stake, vtr->prev_stake, &ancestor->stake );
328 18 : if( FD_UNLIKELY( cf ) ) {
329 0 : FD_BASE58_ENCODE_32_BYTES( ancestor->id.key, ancestor_id_b58 );
330 0 : FD_LOG_CRIT(( "[%s] overflow (after): %lu. subtracted: %lu. (slot %lu, block_id: %s)", __func__, ancestor->stake, vtr->prev_stake, ancestor->slot, ancestor_id_b58 ));
331 0 : }
332 18 : ancestor = blk_pool_ele( blk_pool( ghost ), ancestor->parent );
333 18 : }
334 6 : }
335 :
336 : /* Add voter's stake to the entire fork they are voting for. Propagate
337 : the vote stake up the ancestry. We do this for all cases we exited
338 : above: this vote is the first vote we've seen from a pubkey, this
339 : vote is switched from a previous vote that was on a missing ele
340 : (pruned), or the regular case. */
341 :
342 15 : fd_ghost_blk_t * ancestor = blk;
343 69 : while( FD_LIKELY( ancestor ) ) {
344 54 : int cf = __builtin_uaddl_overflow( ancestor->stake, stake, &ancestor->stake );
345 54 : if( FD_UNLIKELY( cf ) ) {
346 0 : FD_BASE58_ENCODE_32_BYTES( ancestor->id.key, ancestor_id_b58 );
347 0 : FD_LOG_CRIT(( "[%s] overflow (after): %lu. added: %lu. (slot %lu, block_id: %s)", __func__, ancestor->stake, stake, ancestor->slot, ancestor_id_b58 ));
348 0 : }
349 54 : ancestor = blk_pool_ele( blk_pool( ghost ), ancestor->parent );
350 54 : }
351 15 : vtr->prev_block_id = blk->id;
352 15 : vtr->prev_stake = stake;
353 15 : vtr->prev_slot = slot;
354 15 : return FD_GHOST_SUCCESS;
355 15 : }
356 :
357 : void
358 : fd_ghost_publish( fd_ghost_t * ghost,
359 6 : fd_ghost_blk_t * newr ) {
360 :
361 6 : fd_ghost_blk_t * pool = blk_pool( ghost );
362 6 : ulong null = blk_pool_idx_null( pool );
363 6 : fd_ghost_blk_t * oldr = fd_ghost_root( ghost );
364 :
365 6 : if( FD_UNLIKELY( oldr==newr ) ) return;
366 :
367 : /* First, remove the previous root, and add it to the prune list. In
368 : this context, head is the list head (not to be confused with the
369 : ghost head.) */
370 :
371 6 : fd_ghost_blk_t * head = blk_map_ele_remove( blk_map( ghost ), &oldr->id, NULL, pool ); /* remove ele from map to reuse `.next` */
372 6 : fd_ghost_blk_t * tail = head;
373 :
374 : /* Second, BFS down the tree, pruning all of root's ancestors and also
375 : any descendants of those ancestors.
376 :
377 : oldr
378 : |
379 : X
380 : / \
381 : newr Y
382 : |
383 : Z
384 :
385 : ...
386 :
387 : newr
388 :
389 : BFS starts with oldr. Its child is X. X != newr, so X gets
390 : enqueued. oldr is released. Next head = X. X's children are newr
391 : and Y. newr is skipped. Y gets enqueued. X is released. Next
392 : head = Y. Y's child Z gets enqueued. Y released. Z released.
393 : Queue is empty, loop ends.
394 :
395 : oldr
396 : / \
397 : A newr
398 : / \
399 : B C
400 :
401 : ...
402 :
403 : newr
404 : / \
405 : B C
406 :
407 :
408 : The BFS starts with oldr. Its children are A and newr. A gets
409 : enqueued for pruning. newr is skipped (line 374). Then oldr is
410 : released. Next, head = A. A has no children. A is released.
411 : Queue is empty, loop ends. */
412 :
413 6 : head->next = null;
414 33 : while( FD_LIKELY( head ) ) {
415 27 : fd_ghost_blk_t * child = blk_pool_ele( blk_pool( ghost ), head->child );
416 54 : while( FD_LIKELY( child ) ) { /* iterate over children */
417 27 : if( FD_LIKELY( child != newr ) ) { /* stop at new root */
418 21 : tail->next = blk_map_idx_remove( blk_map( ghost ), &child->id, null, pool ); /* remove ele from map to reuse `.next` */
419 21 : FD_BASE58_ENCODE_32_BYTES( child->id.key, block_id_cstr );
420 21 : tail = blk_pool_ele( blk_pool( ghost ), tail->next ); /* push onto prune queue (so descendants can be pruned) */
421 21 : tail->next = blk_pool_idx_null( blk_pool( ghost ) );
422 21 : }
423 27 : child = blk_pool_ele( blk_pool( ghost ), child->sibling ); /* next sibling */
424 27 : ghost->width -= !!child; /* has a sibling == a fork to be pruned */
425 27 : }
426 27 : fd_ghost_blk_t * next = blk_pool_ele( blk_pool( ghost ), head->next ); /* pop prune queue head */
427 27 : blk_pool_ele_release( blk_pool( ghost ), head ); /* free prune queue head */
428 27 : head = next; /* move prune queue head forward */
429 27 : }
430 6 : newr->parent = null; /* unlink old root */
431 6 : ghost->root = blk_pool_idx( blk_pool( ghost ), newr ); /* replace with new root */
432 6 : }
433 :
434 : ulong
435 0 : fd_ghost_width( fd_ghost_t * ghost ) {
436 0 : return ghost->width;
437 0 : }
438 :
439 : fd_ghost_blk_t *
440 : fd_ghost_blk_map_remove( fd_ghost_t * ghost,
441 525 : fd_ghost_blk_t * blk ) {
442 525 : return blk_map_ele_remove( blk_map( ghost ), &blk->id, NULL, blk_pool( ghost ) );
443 525 : }
444 :
445 : void
446 : fd_ghost_blk_map_insert( fd_ghost_t * ghost,
447 525 : fd_ghost_blk_t * blk ) {
448 525 : blk_map_ele_insert( blk_map( ghost ), blk, blk_pool( ghost ) );
449 525 : }
450 :
451 : fd_ghost_blk_t *
452 : fd_ghost_blk_child( fd_ghost_t * ghost,
453 504 : fd_ghost_blk_t * blk ) {
454 504 : return blk_pool_ele( blk_pool( ghost ), blk->child );
455 504 : }
456 :
457 : fd_ghost_blk_t *
458 : fd_ghost_blk_sibling( fd_ghost_t * ghost,
459 489 : fd_ghost_blk_t * blk ) {
460 489 : return blk_pool_ele( blk_pool( ghost ), blk->sibling );
461 489 : }
462 :
463 : fd_ghost_blk_t *
464 : fd_ghost_blk_next( fd_ghost_t * ghost,
465 525 : fd_ghost_blk_t * blk ) {
466 525 : return blk_pool_ele( blk_pool( ghost ), blk->next );
467 525 : }
468 :
469 : ulong
470 : fd_ghost_blk_idx( fd_ghost_t * ghost,
471 483 : fd_ghost_blk_t * blk ) {
472 483 : return blk_pool_idx( blk_pool( ghost ), blk );
473 483 : }
474 :
475 : ulong
476 42 : fd_ghost_blk_idx_null( fd_ghost_t * ghost ) {
477 42 : return blk_pool_idx_null( blk_pool( ghost ) );
478 42 : }
479 :
480 : int
481 39 : fd_ghost_verify( fd_ghost_t * ghost ) {
482 39 : if( FD_UNLIKELY( !ghost ) ) {
483 0 : FD_LOG_WARNING(( "NULL ghost" ));
484 0 : return -1;
485 0 : }
486 :
487 39 : if( FD_UNLIKELY( !fd_ulong_is_aligned( (ulong)ghost, fd_ghost_align() ) ) ) {
488 0 : FD_LOG_WARNING(( "misaligned ghost" ));
489 0 : return -1;
490 0 : }
491 :
492 39 : fd_wksp_t * wksp = fd_wksp_containing( ghost );
493 39 : if( FD_UNLIKELY( !wksp ) ) {
494 0 : FD_LOG_WARNING(( "ghost must be part of a workspace" ));
495 0 : return -1;
496 0 : }
497 :
498 39 : fd_ghost_blk_t const * pool = blk_pool( ghost );
499 :
500 : /* Check every ele that exists in pool exists in map. */
501 :
502 39 : if( blk_map_verify( blk_map( ghost ), blk_pool_max( pool ), pool ) ) return -1;
503 :
504 39 : return 0;
505 39 : }
506 :
507 : #include <stdio.h>
508 : #include <string.h>
509 :
510 : #define BUF_MAX 4096
511 : #define DEPTH_MAX 512
512 :
513 : static void
514 : to_cstr( fd_ghost_t const * ghost,
515 : fd_ghost_blk_t const * ele,
516 : ulong total_stake,
517 : int space,
518 : const char * prefix,
519 : char * cstr,
520 : ulong len,
521 : ulong * off,
522 0 : ulong depth ) {
523 0 : if( FD_UNLIKELY( depth>DEPTH_MAX ) ) return;
524 :
525 0 : fd_ghost_blk_t const * pool = blk_pool_const( ghost );
526 0 : int n;
527 :
528 0 : if( FD_UNLIKELY( ele == NULL ) ) return;
529 :
530 0 : if( FD_LIKELY( space > 0 ) && *off < len ) {
531 0 : cstr[(*off)++] = '\n';
532 0 : }
533 :
534 0 : for( int i = 0; i < space && *off < len; i++ ) {
535 0 : cstr[(*off)++] = ' ';
536 0 : }
537 :
538 0 : if( FD_UNLIKELY( ele->stake > 100 ) ) {
539 0 : }
540 :
541 0 : if( FD_UNLIKELY( total_stake == 0 ) ) {
542 0 : if( *off < len ) {
543 0 : n = snprintf( cstr + *off, len - *off, "%s%lu (%lu)", prefix, ele->slot, ele->stake );
544 0 : if( FD_UNLIKELY( n < 0 )) FD_LOG_CRIT(( "snprintf: %d", n ));
545 0 : *off += (ulong)n;
546 0 : }
547 0 : } else {
548 0 : double pct = ( (double)ele->stake / (double)total_stake ) * 100;
549 0 : if( FD_UNLIKELY( pct < 0.99 ) ) {
550 0 : if( *off < len ) {
551 0 : n = snprintf( cstr + *off, len - *off, "%s%lu (%.0lf%%, %lu)", prefix, ele->slot, pct, ele->stake );
552 0 : if( FD_UNLIKELY( n < 0 )) FD_LOG_CRIT(( "snprintf: %d", n ));
553 0 : *off += (ulong)n;
554 0 : }
555 0 : } else {
556 0 : if( *off < len ) {
557 0 : n = snprintf( cstr + *off, len - *off, "%s%lu (%.0lf%%)", prefix, ele->slot, pct );
558 0 : if( FD_UNLIKELY( n < 0 )) FD_LOG_CRIT(( "snprintf: %d", n ));
559 0 : *off += (ulong)n;
560 0 : }
561 0 : }
562 0 : }
563 :
564 0 : fd_ghost_blk_t const * curr = blk_pool_ele_const( pool, ele->child );
565 :
566 0 : while( curr ) {
567 0 : char const * next_prefix = blk_pool_ele_const( pool, curr->sibling ) ? "├── " : "└── ";
568 0 : to_cstr( ghost, curr, total_stake, space + 4, next_prefix, cstr, len, off, depth + 1 ); /* TODO remove recursion */
569 0 : curr = blk_pool_ele_const( pool, curr->sibling );
570 0 : }
571 0 : }
572 :
573 : char *
574 : fd_ghost_to_cstr( fd_ghost_t const * ghost,
575 : fd_ghost_blk_t const * root,
576 : char * cstr,
577 : ulong cstr_max,
578 0 : ulong * cstr_len ) {
579 :
580 0 : ulong off = 0;
581 :
582 0 : int n = snprintf( cstr + off, cstr_max - off, "[Ghost]\n\n" );
583 0 : if( FD_UNLIKELY( n < 0 )) FD_LOG_CRIT(( "snprintf: %d", n ));
584 0 : off += (ulong)n;
585 :
586 0 : to_cstr( ghost, root, root->total_stake, 0, "", cstr, cstr_max, &off, 0 );
587 :
588 0 : if( off < cstr_max ) {
589 0 : n = snprintf( cstr + off, cstr_max - off, "\n\n" );
590 0 : if( FD_UNLIKELY( n < 0 )) FD_LOG_CRIT(( "snprintf: %d", n ));
591 0 : off += (ulong)n;
592 0 : }
593 :
594 0 : cstr[fd_ulong_min( off++, cstr_max - 1 )] = '\0';
595 0 : *cstr_len = fd_ulong_min( off, cstr_max );
596 0 : return cstr;
597 0 : }
|
