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