Line data Source code
1 : #include "fd_ghost.h"
2 :
3 : #define POOL_NAME blk_pool
4 114 : #define POOL_T fd_ghost_blk_t
5 : #include "../../util/tmpl/fd_pool.c"
6 :
7 : #define MAP_NAME blk_map
8 : #define MAP_ELE_T fd_ghost_blk_t
9 561 : #define MAP_KEY id
10 : #define MAP_KEY_T fd_hash_t
11 21975 : #define MAP_KEY_EQ(k0,k1) (!memcmp((k0),(k1), sizeof(fd_hash_t)))
12 22626 : #define MAP_KEY_HASH(key,seed) (fd_hash((seed),(key),sizeof(fd_hash_t)))
13 2034 : #define MAP_NEXT next
14 : #include "../../util/tmpl/fd_map_chain.c"
15 :
16 : #define POOL_NAME vtr_pool
17 114 : #define POOL_T fd_ghost_vtr_t
18 : #include "../../util/tmpl/fd_pool.c"
19 :
20 : #define MAP_NAME vtr_map
21 : #define MAP_ELE_T fd_ghost_vtr_t
22 1668 : #define MAP_KEY addr
23 : #define MAP_KEY_T fd_pubkey_t
24 21450 : #define MAP_KEY_EQ(k0,k1) (!memcmp((k0),(k1), sizeof(fd_pubkey_t)))
25 23211 : #define MAP_KEY_HASH(key,seed) (fd_hash((seed),(key),sizeof(fd_pubkey_t)))
26 6267 : #define MAP_NEXT next
27 : #include "../../util/tmpl/fd_map_chain.c"
28 :
29 : /* fd_ghost_t is the top-level structure that holds the root of the
30 : tree, as well as the memory pools and map structures for tracking
31 : ghost eles and votes.
32 :
33 : These structures are bump-allocated and laid out contiguously in
34 : memory from the fd_ghost_t * pointer which points to the beginning of
35 : the memory region.
36 :
37 : ---------------------- <- fd_ghost_t *
38 : | root |
39 : ----------------------
40 : | pool |
41 : ----------------------
42 : | blk_map |
43 : ----------------------
44 : | vtr_map |
45 : ---------------------- */
46 :
47 : struct __attribute__((aligned(128UL))) fd_ghost {
48 : ulong root; /* pool idx of the root tree element */
49 : ulong wksp_gaddr; /* wksp gaddr of fd_ghost in the backing wksp */
50 : ulong blk_pool_gaddr; /* memory offset of the blk_pool */
51 : ulong blk_map_gaddr; /* memory offset of the blk_map */
52 : ulong vtr_pool_gaddr; /* memory offset of the vtr_pool */
53 : ulong vtr_map_gaddr; /* memory offset of the vtr_map */
54 : ulong width; /* incrementally updated width of the fork tree */
55 : };
56 :
57 : typedef fd_ghost_blk_t blk_pool_t;
58 : typedef fd_ghost_vtr_t vtr_pool_t;
59 :
60 : /* wksp returns the local join to the wksp backing the
61 : ghost. The lifetime of the returned pointer is at least as
62 : long as the lifetime of the local join. Assumes ghost is a
63 : current local join. */
64 :
65 : FD_FN_PURE static inline fd_wksp_t *
66 538857 : wksp( fd_ghost_t const * ghost ) {
67 538857 : return (fd_wksp_t *)( ((ulong)ghost) - ghost->wksp_gaddr );
68 538857 : }
69 :
70 : static inline blk_pool_t *
71 465696 : blk_pool( fd_ghost_t * ghost ) {
72 465696 : return (blk_pool_t *)fd_wksp_laddr_fast( wksp( ghost ), ghost->blk_pool_gaddr );
73 465696 : }
74 :
75 : static inline blk_pool_t const *
76 2772 : blk_pool_const( fd_ghost_t const * ghost ) {
77 2772 : return (blk_pool_t const *)fd_wksp_laddr_fast( wksp( ghost ), ghost->blk_pool_gaddr );
78 2772 : }
79 :
80 : static inline blk_map_t *
81 22299 : blk_map( fd_ghost_t * ghost ) {
82 22299 : return (blk_map_t *)fd_wksp_laddr_fast( wksp( ghost ), ghost->blk_map_gaddr );
83 22299 : }
84 :
85 : static inline vtr_pool_t *
86 24879 : vtr_pool( fd_ghost_t * ghost ) {
87 24879 : return (vtr_pool_t *)fd_wksp_laddr_fast( wksp( ghost ), ghost->vtr_pool_gaddr );
88 24879 : }
89 :
90 : static inline vtr_map_t *
91 23211 : vtr_map( fd_ghost_t * ghost ) {
92 23211 : return (vtr_map_t *)fd_wksp_laddr_fast( wksp( ghost ), ghost->vtr_map_gaddr );
93 23211 : }
94 :
95 : ulong
96 672 : fd_ghost_align( void ) {
97 672 : return alignof(fd_ghost_t);
98 672 : }
99 :
100 : ulong
101 : fd_ghost_footprint( ulong blk_max,
102 135 : ulong vtr_max ) {
103 135 : ulong blk_chain_cnt = blk_map_chain_cnt_est( blk_max );
104 135 : ulong vtr_chain_cnt = vtr_map_chain_cnt_est( vtr_max );
105 135 : return FD_LAYOUT_FINI(
106 135 : FD_LAYOUT_APPEND(
107 135 : FD_LAYOUT_APPEND(
108 135 : FD_LAYOUT_APPEND(
109 135 : FD_LAYOUT_APPEND(
110 135 : FD_LAYOUT_APPEND(
111 135 : FD_LAYOUT_INIT,
112 135 : alignof(fd_ghost_t), sizeof(fd_ghost_t) ),
113 135 : blk_pool_align(), blk_pool_footprint( blk_max ) ),
114 135 : blk_map_align(), blk_map_footprint ( blk_chain_cnt ) ),
115 135 : vtr_pool_align(), vtr_pool_footprint( vtr_max ) ),
116 135 : vtr_map_align(), vtr_map_footprint ( vtr_chain_cnt ) ),
117 135 : fd_ghost_align() );
118 135 : }
119 :
120 : void *
121 : fd_ghost_new( void * shmem,
122 : ulong blk_max,
123 : ulong vtr_max,
124 57 : ulong seed ) {
125 :
126 57 : if( FD_UNLIKELY( !shmem ) ) {
127 0 : FD_LOG_WARNING(( "NULL mem" ));
128 0 : return NULL;
129 0 : }
130 :
131 57 : if( FD_UNLIKELY( !fd_ulong_is_aligned( (ulong)shmem, fd_ghost_align() ) ) ) {
132 0 : FD_LOG_WARNING(( "misaligned mem" ));
133 0 : return NULL;
134 0 : }
135 :
136 57 : ulong footprint = fd_ghost_footprint( blk_max, vtr_max );
137 57 : if( FD_UNLIKELY( !footprint ) ) {
138 0 : FD_LOG_WARNING(( "bad blk_max (%lu)", blk_max ));
139 0 : return NULL;
140 0 : }
141 :
142 57 : fd_wksp_t * wksp = fd_wksp_containing( shmem );
143 57 : if( FD_UNLIKELY( !wksp ) ) {
144 0 : FD_LOG_WARNING(( "shmem must be part of a workspace" ));
145 0 : return NULL;
146 0 : }
147 :
148 57 : fd_memset( shmem, 0, footprint );
149 :
150 57 : ulong blk_chain_cnt = blk_map_chain_cnt_est( blk_max );
151 57 : ulong vtr_chain_cnt = vtr_map_chain_cnt_est( vtr_max );
152 :
153 57 : FD_SCRATCH_ALLOC_INIT( l, shmem );
154 57 : fd_ghost_t * ghost = FD_SCRATCH_ALLOC_APPEND( l, alignof(fd_ghost_t), sizeof(fd_ghost_t) );
155 57 : void * blk_pool = FD_SCRATCH_ALLOC_APPEND( l, blk_pool_align(), blk_pool_footprint( blk_max ) );
156 57 : void * blk_map = FD_SCRATCH_ALLOC_APPEND( l, blk_map_align(), blk_map_footprint ( blk_chain_cnt ) );
157 57 : void * vtr_pool = FD_SCRATCH_ALLOC_APPEND( l, vtr_pool_align(), vtr_pool_footprint( vtr_max ) );
158 57 : void * vtr_map = FD_SCRATCH_ALLOC_APPEND( l, vtr_map_align(), vtr_map_footprint ( vtr_chain_cnt ) );
159 57 : FD_TEST( FD_SCRATCH_ALLOC_FINI( l, fd_ghost_align() ) == (ulong)shmem + footprint );
160 :
161 57 : ghost->root = ULONG_MAX;
162 57 : ghost->wksp_gaddr = fd_wksp_gaddr_fast( wksp, ghost );
163 57 : ghost->blk_pool_gaddr = fd_wksp_gaddr_fast( wksp, blk_pool_join( blk_pool_new ( blk_pool, blk_max ) ) );
164 57 : ghost->blk_map_gaddr = fd_wksp_gaddr_fast( wksp, blk_map_join ( blk_map_new ( blk_map, blk_chain_cnt, seed ) ) );
165 57 : ghost->vtr_pool_gaddr = fd_wksp_gaddr_fast( wksp, vtr_pool_join( vtr_pool_new ( vtr_pool, vtr_max ) ) );
166 57 : ghost->vtr_map_gaddr = fd_wksp_gaddr_fast( wksp, vtr_map_join ( vtr_map_new ( vtr_map, vtr_chain_cnt, seed ) ) );
167 :
168 57 : return shmem;
169 57 : }
170 :
171 : fd_ghost_t *
172 57 : fd_ghost_join( void * shghost ) {
173 57 : fd_ghost_t * ghost = (fd_ghost_t *)shghost;
174 :
175 57 : if( FD_UNLIKELY( !ghost ) ) {
176 0 : FD_LOG_WARNING(( "NULL ghost" ));
177 0 : return NULL;
178 0 : }
179 :
180 57 : if( FD_UNLIKELY( !fd_ulong_is_aligned((ulong)ghost, fd_ghost_align() ) ) ) {
181 0 : FD_LOG_WARNING(( "misaligned ghost" ));
182 0 : return NULL;
183 0 : }
184 :
185 57 : return ghost;
186 57 : }
187 :
188 : void *
189 36 : fd_ghost_leave( fd_ghost_t const * ghost ) {
190 :
191 36 : if( FD_UNLIKELY( !ghost ) ) {
192 0 : FD_LOG_WARNING(( "NULL ghost" ));
193 0 : return NULL;
194 0 : }
195 :
196 36 : return (void *)ghost;
197 36 : }
198 :
199 : void *
200 36 : fd_ghost_delete( void * ghost ) {
201 :
202 36 : if( FD_UNLIKELY( !ghost ) ) {
203 0 : FD_LOG_WARNING(( "NULL ghost" ));
204 0 : return NULL;
205 0 : }
206 :
207 36 : if( FD_UNLIKELY( !fd_ulong_is_aligned((ulong)ghost, fd_ghost_align() ) ) ) {
208 0 : FD_LOG_WARNING(( "misaligned ghost" ));
209 0 : return NULL;
210 0 : }
211 :
212 36 : return ghost;
213 36 : }
214 :
215 : fd_ghost_blk_t *
216 51867 : fd_ghost_root( fd_ghost_t * ghost ) {
217 51867 : return blk_pool_ele( blk_pool( ghost ), ghost->root );
218 51867 : }
219 :
220 : fd_ghost_blk_t *
221 12 : fd_ghost_parent( fd_ghost_t * ghost, fd_ghost_blk_t * blk ) {
222 12 : return blk_pool_ele( blk_pool( ghost ), blk->parent );
223 12 : }
224 :
225 : fd_ghost_blk_t *
226 : fd_ghost_query( fd_ghost_t * ghost,
227 891 : fd_hash_t const * block_id ) {
228 891 : return blk_map_ele_query( blk_map( ghost ), block_id, NULL, blk_pool( ghost ) );
229 891 : }
230 :
231 : fd_ghost_blk_t *
232 : fd_ghost_best( fd_ghost_t * ghost,
233 315 : fd_ghost_blk_t * root ) {
234 315 : blk_pool_t * pool = blk_pool( ghost );
235 315 : ulong null = blk_pool_idx_null( pool );
236 315 : fd_ghost_blk_t * best = root;
237 2850 : while( FD_LIKELY( best->child != null ) ) {
238 2541 : int valid = 0; /* at least one child is valid */
239 2541 : fd_ghost_blk_t * child = blk_pool_ele( pool, best->child );
240 5097 : while( FD_LIKELY( child ) ) { /* greedily pick the heaviest valid child */
241 2556 : if( FD_LIKELY( child->valid ) ) {
242 2550 : if( FD_LIKELY( !valid ) ) { /* this is the first valid child, so progress the head */
243 2535 : best = child;
244 2535 : valid = 1;
245 2535 : }
246 :
247 : /* When stake is equal, tie-break by lower slot. Two valid
248 : children with equal stake and equal slot (ie. equivocating
249 : blocks) cannot occur: equivocating blocks are marked valid=0,
250 : so at most one of them would be valid unless multiple blocks
251 : for that slot are duplicate confirmed, which is a consensus
252 : invariant violation. */
253 :
254 2550 : best = fd_ptr_if(
255 2550 : fd_int_if(
256 2550 : child->stake == best->stake, /* if the weights are equal */
257 2550 : child->slot < best->slot, /* then tie-break by lower slot number */
258 2550 : child->stake > best->stake ), /* else return heavier */
259 2550 : child, best );
260 2550 : }
261 2556 : child = blk_pool_ele( pool, child->sibling );
262 2556 : }
263 2541 : if( FD_UNLIKELY( !valid ) ) break; /* no children are valid, so short-circuit traversal */
264 2541 : }
265 315 : return best;
266 315 : }
267 :
268 : fd_ghost_blk_t *
269 : fd_ghost_deepest( fd_ghost_t * ghost,
270 15 : fd_ghost_blk_t * root ) {
271 15 : blk_pool_t * pool = blk_pool( ghost );
272 15 : ulong null = blk_pool_idx_null( pool );
273 15 : fd_ghost_blk_t * head = blk_map_ele_remove( blk_map( ghost ), &root->id, NULL, pool ); /* remove ele from map to reuse `.next` */
274 15 : fd_ghost_blk_t * tail = head;
275 15 : fd_ghost_blk_t * prev = NULL;
276 :
277 : /* Below is a level-order traversal (BFS), returning the last leaf
278 : which is guaranteed to return an element of the max depth.
279 :
280 : It temporarily removes elements of the map when pushing onto the
281 : BFS queue to reuse the .next pointer and then inserts back into
282 : the map on queue pop. */
283 :
284 15 : head->next = null;
285 93 : while( FD_LIKELY( head ) ) {
286 78 : fd_ghost_blk_t const * child = blk_pool_ele( pool, head->child );
287 141 : while( FD_LIKELY( child ) ) {
288 63 : FD_TEST( blk_map_ele_remove( blk_map( ghost ), &child->id, NULL, pool ) ); /* in the tree so must be in the map */
289 63 : tail->next = blk_pool_idx( pool, child );
290 63 : tail = blk_pool_ele( pool, tail->next );
291 63 : tail->next = blk_pool_idx_null( pool );
292 63 : child = blk_pool_ele( pool, child->sibling ); /* next sibling */
293 63 : }
294 78 : fd_ghost_blk_t * next = blk_pool_ele( pool, head->next ); /* pop prune queue head */
295 78 : blk_map_ele_insert( blk_map( ghost ), head, pool ); /* re-insert head into map */
296 78 : prev = head;
297 78 : head = next;
298 78 : }
299 15 : return prev;
300 15 : }
301 :
302 21798 : #define PREDICATE_ANCESTOR( predicate ) do { \
303 21798 : fd_ghost_blk_t * ancestor = descendant; \
304 46332 : while( FD_LIKELY( ancestor ) ) { \
305 46059 : if( FD_LIKELY( predicate ) ) return ancestor; \
306 46059 : ancestor = blk_pool_ele( blk_pool( ghost ), ancestor->parent ); \
307 24534 : } \
308 21798 : return NULL; \
309 21798 : } while(0)
310 :
311 : fd_ghost_blk_t *
312 : fd_ghost_ancestor( fd_ghost_t * ghost,
313 : fd_ghost_blk_t * descendant,
314 0 : fd_hash_t const * ancestor_id ) {
315 0 : PREDICATE_ANCESTOR( 0==memcmp( &ancestor->id, ancestor_id, sizeof(fd_hash_t) ) );
316 0 : }
317 :
318 : fd_ghost_blk_t *
319 : fd_ghost_slot_ancestor( fd_ghost_t * ghost,
320 : fd_ghost_blk_t * descendant,
321 21525 : ulong slot ) {
322 21525 : PREDICATE_ANCESTOR( ancestor->slot == slot );
323 21525 : }
324 :
325 : fd_ghost_blk_t *
326 : fd_ghost_invalid_ancestor( fd_ghost_t * ghost,
327 273 : fd_ghost_blk_t * descendant ) {
328 273 : PREDICATE_ANCESTOR( !ancestor->valid );
329 273 : }
330 :
331 : static fd_ghost_blk_t *
332 : insert( fd_ghost_t * ghost,
333 : ulong slot,
334 483 : fd_hash_t const * block_id ) {
335 483 : fd_ghost_blk_t * pool = blk_pool( ghost );
336 483 : ulong null = blk_pool_idx_null( pool );
337 483 : fd_ghost_blk_t * blk = blk_map_ele_query( blk_map( ghost ), block_id, NULL, pool );
338 :
339 483 : FD_TEST( !blk ); /* duplicate insert */
340 483 : FD_TEST( blk_pool_free( pool ) ); /* ghost full */
341 :
342 483 : blk = blk_pool_ele_acquire( pool );
343 483 : blk->id = *block_id;
344 483 : blk->slot = slot;
345 483 : blk->next = null;
346 483 : blk->parent = null;
347 483 : blk->child = null;
348 483 : blk->sibling = null;
349 483 : blk->stake = 0;
350 483 : blk->total_stake = 0;
351 483 : blk->valid = 1;
352 483 : blk_map_ele_insert( blk_map( ghost ), blk, pool );
353 483 : return blk;
354 483 : }
355 :
356 : fd_ghost_blk_t *
357 : fd_ghost_init( fd_ghost_t * ghost,
358 : ulong slot,
359 57 : fd_hash_t const * block_id ) {
360 57 : fd_ghost_blk_t * blk = insert( ghost, slot, block_id );
361 57 : ghost->root = blk_pool_idx( blk_pool( ghost ), blk );
362 57 : ghost->width = 1;
363 57 : return blk;
364 57 : }
365 :
366 : fd_ghost_blk_t *
367 : fd_ghost_insert( fd_ghost_t * ghost,
368 : ulong slot,
369 : fd_hash_t const * block_id,
370 426 : fd_hash_t const * parent_block_id ) {
371 426 : fd_ghost_blk_t * blk = insert( ghost, slot, block_id );
372 426 : fd_ghost_blk_t * pool = blk_pool( ghost );
373 426 : ulong null = blk_pool_idx_null( pool );
374 426 : fd_ghost_blk_t * parent = blk_map_ele_query( blk_map( ghost ), parent_block_id, NULL, pool );
375 426 : FD_TEST( parent ); /* parent must exist be in ghost */
376 426 : blk->parent = blk_pool_idx( pool, parent );
377 426 : if( FD_LIKELY( parent->child == null ) ) {
378 390 : parent->child = blk_pool_idx( pool, blk ); /* left-child */
379 390 : } else {
380 36 : fd_ghost_blk_t * sibling = blk_pool_ele( pool, parent->child );
381 36 : while( sibling->sibling != null ) sibling = blk_pool_ele( pool, sibling->sibling );
382 36 : sibling->sibling = blk_pool_idx( pool, blk ); /* right-sibling */
383 36 : ghost->width++;
384 36 : }
385 :
386 426 : return blk;
387 426 : }
388 :
389 : int
390 : fd_ghost_count_vote( fd_ghost_t * ghost,
391 : fd_ghost_blk_t * blk,
392 : fd_pubkey_t const * vote_acc,
393 : ulong stake,
394 21543 : ulong slot ) {
395 :
396 21543 : fd_ghost_blk_t const * root = fd_ghost_root( ghost );
397 21543 : fd_ghost_vtr_t * vtr = vtr_map_ele_query( vtr_map( ghost ), vote_acc, NULL, vtr_pool( ghost ) );
398 :
399 21543 : if( FD_UNLIKELY( slot==ULONG_MAX ) ) return FD_GHOST_ERR_NOT_VOTED;
400 21543 : if( FD_UNLIKELY( slot< root->slot ) ) return FD_GHOST_ERR_VOTE_TOO_OLD;
401 :
402 21543 : if( FD_UNLIKELY( !vtr ) ) {
403 :
404 : /* This vote account address has not previously voted, so add it to
405 : the map of voters. */
406 :
407 1668 : vtr = vtr_pool_ele_acquire( vtr_pool( ghost ) );
408 1668 : vtr->addr = *vote_acc;
409 1668 : vtr_map_ele_insert( vtr_map( ghost ), vtr, vtr_pool( ghost ) );
410 :
411 19875 : } else {
412 :
413 : /* Only process the vote if it is not the same as the previous vote
414 : and also that the vote slot is most recent. It's possible for
415 : ghost to process votes out of order because votes happen in
416 : replay order which is concurrent across different forks.
417 :
418 : For example, if a voter votes for 3 then switches to 5, we might
419 : observe the vote for 5 before the vote for 3. */
420 :
421 19875 : if( FD_UNLIKELY( !( slot > vtr->prev_slot ) ) ) return FD_GHOST_ERR_ALREADY_VOTED;
422 :
423 : /* LMD-rule: subtract the voter's stake from the entire fork they
424 : previously voted for. */
425 :
426 : /* TODO can optimize this if they're voting for the same fork */
427 :
428 19764 : fd_ghost_blk_t * ancestor = blk_map_ele_query( blk_map( ghost ), &vtr->prev_block_id, NULL, blk_pool( ghost ) );
429 192510 : while( FD_LIKELY( ancestor ) ) {
430 172746 : int cf = __builtin_usubl_overflow( ancestor->stake, vtr->prev_stake, &ancestor->stake );
431 172746 : if( FD_UNLIKELY( cf ) ) {
432 0 : FD_BASE58_ENCODE_32_BYTES( ancestor->id.key, ancestor_id_b58 );
433 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 ));
434 0 : }
435 172746 : ancestor = blk_pool_ele( blk_pool( ghost ), ancestor->parent );
436 172746 : }
437 19764 : }
438 :
439 : /* Add voter's stake to the entire fork they are voting for. Propagate
440 : the vote stake up the ancestry. We do this for all cases we exited
441 : above: this vote is the first vote we've seen from a pubkey, this
442 : vote is switched from a previous vote that was on a missing ele
443 : (pruned), or the regular case. */
444 :
445 21432 : fd_ghost_blk_t * ancestor = blk;
446 215739 : while( FD_LIKELY( ancestor ) ) {
447 194307 : int cf = __builtin_uaddl_overflow( ancestor->stake, stake, &ancestor->stake );
448 194307 : if( FD_UNLIKELY( cf ) ) {
449 0 : FD_BASE58_ENCODE_32_BYTES( ancestor->id.key, ancestor_id_b58 );
450 0 : FD_LOG_CRIT(( "[%s] overflow (after): %lu. added: %lu. (slot %lu, block_id: %s)", __func__, ancestor->stake, stake, ancestor->slot, ancestor_id_b58 ));
451 0 : }
452 194307 : ancestor = blk_pool_ele( blk_pool( ghost ), ancestor->parent );
453 194307 : }
454 21432 : vtr->prev_block_id = blk->id;
455 21432 : vtr->prev_stake = stake;
456 21432 : vtr->prev_slot = slot;
457 21432 : return FD_GHOST_SUCCESS;
458 21432 : }
459 :
460 : void
461 : fd_ghost_publish( fd_ghost_t * ghost,
462 9 : fd_ghost_blk_t * newr ) {
463 :
464 9 : fd_ghost_blk_t * pool = blk_pool( ghost );
465 9 : ulong null = blk_pool_idx_null( pool );
466 9 : fd_ghost_blk_t * oldr = fd_ghost_root( ghost );
467 :
468 9 : if( FD_UNLIKELY( oldr==newr ) ) return;
469 :
470 : /* First, remove the previous root, and add it to the prune list. In
471 : this context, head is the list head (not to be confused with the
472 : ghost head.) */
473 :
474 6 : fd_ghost_blk_t * head = blk_map_ele_remove( blk_map( ghost ), &oldr->id, NULL, pool ); /* remove ele from map to reuse `.next` */
475 6 : fd_ghost_blk_t * tail = head;
476 :
477 : /* Second, BFS down the tree, pruning all of root's ancestors and also
478 : any descendants of those ancestors.
479 :
480 : oldr
481 : |
482 : X
483 : / \
484 : newr Y
485 : |
486 : Z
487 :
488 : ...
489 :
490 : newr
491 :
492 : BFS starts with oldr. Its child is X. X != newr, so X gets
493 : enqueued. oldr is released. Next head = X. X's children are newr
494 : and Y. newr is skipped. Y gets enqueued. X is released. Next
495 : head = Y. Y's child Z gets enqueued. Y released. Z released.
496 : Queue is empty, loop ends.
497 :
498 : oldr
499 : / \
500 : A newr
501 : / \
502 : B C
503 :
504 : ...
505 :
506 : newr
507 : / \
508 : B C
509 :
510 :
511 : The BFS starts with oldr. Its children are A and newr. A gets
512 : enqueued for pruning. newr is skipped (line 374). Then oldr is
513 : released. Next, head = A. A has no children. A is released.
514 : Queue is empty, loop ends. */
515 :
516 6 : head->next = null;
517 33 : while( FD_LIKELY( head ) ) {
518 27 : fd_ghost_blk_t * child = blk_pool_ele( blk_pool( ghost ), head->child );
519 54 : while( FD_LIKELY( child ) ) { /* iterate over children */
520 27 : if( FD_LIKELY( child != newr ) ) { /* stop at new root */
521 21 : tail->next = blk_map_idx_remove( blk_map( ghost ), &child->id, null, pool ); /* remove ele from map to reuse `.next` */
522 21 : FD_BASE58_ENCODE_32_BYTES( child->id.key, block_id_cstr );
523 21 : tail = blk_pool_ele( blk_pool( ghost ), tail->next ); /* push onto prune queue (so descendants can be pruned) */
524 21 : tail->next = blk_pool_idx_null( blk_pool( ghost ) );
525 21 : }
526 27 : child = blk_pool_ele( blk_pool( ghost ), child->sibling ); /* next sibling */
527 27 : ghost->width -= !!child; /* has a sibling == a fork to be pruned */
528 27 : }
529 27 : fd_ghost_blk_t * next = blk_pool_ele( blk_pool( ghost ), head->next ); /* pop prune queue head */
530 27 : blk_pool_ele_release( blk_pool( ghost ), head ); /* free prune queue head */
531 27 : head = next; /* move prune queue head forward */
532 27 : }
533 6 : newr->parent = null; /* unlink old root */
534 6 : ghost->root = blk_pool_idx( blk_pool( ghost ), newr ); /* replace with new root */
535 6 : }
536 :
537 : /* mark_invalid marks the entire subtree beginning from root as invalid.
538 : Implementation is iterative pre-order traversal using O(1) space. */
539 :
540 : static void
541 : mark_invalid( fd_ghost_t * ghost,
542 21 : fd_ghost_blk_t * root ) {
543 21 : fd_ghost_blk_t * pool = blk_pool( ghost );
544 21 : fd_ghost_blk_t * curr = root;
545 :
546 : /* Loop invariant: curr has not been visited.
547 :
548 : Before: curr = root, which has not been visited. Trivially true.
549 :
550 : After: curr is set to either a child (step 2) or a right sibling of
551 : an ancestor found during backtracking (step 3). Preorder visits
552 : parents before children and left before right, so neither has been
553 : visited yet. If backtracking reaches root (step 4), loop exits. */
554 :
555 21 : for(;;) {
556 :
557 : /* 1. Visit: mark the current curr invalid. */
558 :
559 21 : curr->valid = 0;
560 :
561 : /* 2. Descend: if the curr has a child, pivot to it. */
562 :
563 21 : fd_ghost_blk_t * child = blk_pool_ele( pool, curr->child );
564 21 : if( FD_LIKELY( child ) ) { curr = child; continue; }
565 :
566 : /* 3. Backtrack: if the curr is a leaf, traverse up until we find an
567 : ancestor with a right sibling, then pivot to that sibling. */
568 :
569 21 : while( FD_LIKELY( curr!=root ) ) {
570 0 : fd_ghost_blk_t * sibling = blk_pool_ele( pool, curr->sibling );
571 0 : if( FD_LIKELY( sibling ) ) { curr = sibling; break; }
572 0 : curr = blk_pool_ele( pool, curr->parent );
573 0 : }
574 :
575 : /* 4. Terminate: if we backtrack all the way to root, the traversal
576 : is complete. */
577 :
578 21 : if( FD_UNLIKELY( curr==root ) ) break;
579 21 : }
580 21 : }
581 :
582 : void
583 : fd_ghost_confirm( fd_ghost_t * ghost,
584 9 : fd_hash_t const * confirmed_block_id ) {
585 9 : fd_ghost_blk_t * pool = blk_pool( ghost );
586 9 : fd_ghost_blk_t * blk = blk_map_ele_query( blk_map( ghost ), confirmed_block_id, NULL, pool );
587 9 : if( FD_UNLIKELY( !blk ) ) return;
588 :
589 : /* Mark the confirmed block and its ancestors as valid, short-
590 : circuiting at the first ancestor that is already valid. */
591 :
592 9 : fd_ghost_blk_t * anc = blk;
593 12 : while( FD_LIKELY( anc ) ) {
594 12 : if( FD_LIKELY( anc->valid ) ) break;
595 3 : anc->valid = 1;
596 3 : anc = blk_pool_ele( pool, anc->parent );
597 3 : }
598 9 : }
599 :
600 : void
601 : fd_ghost_eqvoc( fd_ghost_t * ghost,
602 21 : fd_hash_t const * block_id ) {
603 21 : fd_ghost_blk_t * pool = blk_pool( ghost );
604 21 : fd_ghost_blk_t * blk = blk_map_ele_query( blk_map( ghost ), block_id, NULL, pool );
605 21 : if( FD_UNLIKELY( !blk ) ) return;
606 21 : mark_invalid( ghost, blk );
607 21 : }
608 :
609 : ulong
610 294 : fd_ghost_width( fd_ghost_t * ghost ) {
611 294 : return ghost->width;
612 294 : }
613 :
614 : fd_ghost_blk_t *
615 : fd_ghost_blk_map_remove( fd_ghost_t * ghost,
616 0 : fd_ghost_blk_t * blk ) {
617 0 : return blk_map_ele_remove( blk_map( ghost ), &blk->id, NULL, blk_pool( ghost ) );
618 0 : }
619 :
620 : void
621 : fd_ghost_blk_map_insert( fd_ghost_t * ghost,
622 0 : fd_ghost_blk_t * blk ) {
623 0 : blk_map_ele_insert( blk_map( ghost ), blk, blk_pool( ghost ) );
624 0 : }
625 :
626 : fd_ghost_blk_t *
627 : fd_ghost_blk_child( fd_ghost_t * ghost,
628 0 : fd_ghost_blk_t * blk ) {
629 0 : return blk_pool_ele( blk_pool( ghost ), blk->child );
630 0 : }
631 :
632 : fd_ghost_blk_t *
633 : fd_ghost_blk_sibling( fd_ghost_t * ghost,
634 0 : fd_ghost_blk_t * blk ) {
635 0 : return blk_pool_ele( blk_pool( ghost ), blk->sibling );
636 0 : }
637 :
638 : fd_ghost_blk_t *
639 : fd_ghost_blk_next( fd_ghost_t * ghost,
640 0 : fd_ghost_blk_t * blk ) {
641 0 : return blk_pool_ele( blk_pool( ghost ), blk->next );
642 0 : }
643 :
644 : ulong
645 : fd_ghost_blk_idx( fd_ghost_t * ghost,
646 0 : fd_ghost_blk_t * blk ) {
647 0 : return blk_pool_idx( blk_pool( ghost ), blk );
648 0 : }
649 :
650 : ulong
651 0 : fd_ghost_blk_idx_null( fd_ghost_t * ghost ) {
652 0 : return blk_pool_idx_null( blk_pool( ghost ) );
653 0 : }
654 :
655 : int
656 39 : fd_ghost_verify( fd_ghost_t * ghost ) {
657 39 : if( FD_UNLIKELY( !ghost ) ) {
658 0 : FD_LOG_WARNING(( "NULL ghost" ));
659 0 : return -1;
660 0 : }
661 :
662 39 : if( FD_UNLIKELY( !fd_ulong_is_aligned( (ulong)ghost, fd_ghost_align() ) ) ) {
663 0 : FD_LOG_WARNING(( "misaligned ghost" ));
664 0 : return -1;
665 0 : }
666 :
667 39 : fd_wksp_t * wksp = fd_wksp_containing( ghost );
668 39 : if( FD_UNLIKELY( !wksp ) ) {
669 0 : FD_LOG_WARNING(( "ghost must be part of a workspace" ));
670 0 : return -1;
671 0 : }
672 :
673 39 : fd_ghost_blk_t const * pool = blk_pool( ghost );
674 :
675 : /* Check every ele that exists in pool exists in map. */
676 :
677 39 : if( blk_map_verify( blk_map( ghost ), blk_pool_max( pool ), pool ) ) return -1;
678 :
679 39 : return 0;
680 39 : }
681 :
682 : #include <stdio.h>
683 : #include <string.h>
684 :
685 : #define BUF_MAX 4096
686 : #define DEPTH_MAX 512
687 :
688 : static void
689 : to_cstr( fd_ghost_t const * ghost,
690 : fd_ghost_blk_t const * ele,
691 : ulong total_stake,
692 : int space,
693 : const char * prefix,
694 : char * cstr,
695 : ulong len,
696 : ulong * off,
697 2772 : ulong depth ) {
698 2772 : if( FD_UNLIKELY( depth>DEPTH_MAX ) ) return;
699 :
700 2772 : fd_ghost_blk_t const * pool = blk_pool_const( ghost );
701 2772 : int n;
702 :
703 2772 : if( FD_UNLIKELY( ele == NULL ) ) return;
704 :
705 2772 : if( FD_LIKELY( space > 0 ) && *off < len ) {
706 2478 : cstr[(*off)++] = '\n';
707 2478 : }
708 :
709 84084 : for( int i = 0; i < space && *off < len; i++ ) {
710 81312 : cstr[(*off)++] = ' ';
711 81312 : }
712 :
713 2772 : if( FD_UNLIKELY( ele->stake > 100 ) ) {
714 2478 : }
715 :
716 2772 : if( FD_UNLIKELY( total_stake == 0 ) ) {
717 0 : if( *off < len ) {
718 0 : n = snprintf( cstr + *off, len - *off, "%s%lu (%lu)", prefix, ele->slot, ele->stake );
719 0 : if( FD_UNLIKELY( n < 0 )) FD_LOG_CRIT(( "snprintf: %d", n ));
720 0 : *off += (ulong)n;
721 0 : }
722 2772 : } else {
723 2772 : double pct = ( (double)ele->stake / (double)total_stake ) * 100;
724 2772 : if( FD_UNLIKELY( pct < 0.99 ) ) {
725 294 : if( *off < len ) {
726 294 : n = snprintf( cstr + *off, len - *off, "%s%lu (%.0lf%%, %lu)", prefix, ele->slot, pct, ele->stake );
727 294 : if( FD_UNLIKELY( n < 0 )) FD_LOG_CRIT(( "snprintf: %d", n ));
728 294 : *off += (ulong)n;
729 294 : }
730 2478 : } else {
731 2478 : if( *off < len ) {
732 2478 : n = snprintf( cstr + *off, len - *off, "%s%lu (%.0lf%%)", prefix, ele->slot, pct );
733 2478 : if( FD_UNLIKELY( n < 0 )) FD_LOG_CRIT(( "snprintf: %d", n ));
734 2478 : *off += (ulong)n;
735 2478 : }
736 2478 : }
737 2772 : }
738 :
739 2772 : fd_ghost_blk_t const * curr = blk_pool_ele_const( pool, ele->child );
740 :
741 5250 : while( curr ) {
742 2478 : char const * next_prefix = blk_pool_ele_const( pool, curr->sibling ) ? "├── " : "└── ";
743 2478 : to_cstr( ghost, curr, total_stake, space + 4, next_prefix, cstr, len, off, depth + 1 ); /* TODO remove recursion */
744 2478 : curr = blk_pool_ele_const( pool, curr->sibling );
745 2478 : }
746 2772 : }
747 :
748 : char *
749 : fd_ghost_to_cstr( fd_ghost_t const * ghost,
750 : fd_ghost_blk_t const * root,
751 : char * cstr,
752 : ulong cstr_max,
753 294 : ulong * cstr_len ) {
754 :
755 294 : ulong off = 0;
756 :
757 294 : int n = snprintf( cstr + off, cstr_max - off, "[Ghost]\n\n" );
758 294 : if( FD_UNLIKELY( n < 0 )) FD_LOG_CRIT(( "snprintf: %d", n ));
759 294 : off += (ulong)n;
760 :
761 294 : to_cstr( ghost, root, root->total_stake, 0, "", cstr, cstr_max, &off, 0 );
762 :
763 294 : if( off < cstr_max ) {
764 294 : n = snprintf( cstr + off, cstr_max - off, "\n\n" );
765 294 : if( FD_UNLIKELY( n < 0 )) FD_LOG_CRIT(( "snprintf: %d", n ));
766 294 : off += (ulong)n;
767 294 : }
768 :
769 294 : cstr[fd_ulong_min( off++, cstr_max - 1 )] = '\0';
770 294 : *cstr_len = fd_ulong_min( off, cstr_max );
771 294 : return cstr;
772 294 : }
|
