Line data Source code
1 : #include "fd_ghost.h"
2 : #include "stdio.h"
3 : #include <string.h>
4 :
5 : /* clang-format off */
6 :
7 : void *
8 0 : fd_ghost_new( void * shmem, ulong node_max, ulong vote_max, ulong seed ) {
9 :
10 0 : if( FD_UNLIKELY( !shmem ) ) {
11 0 : FD_LOG_WARNING(( "NULL mem" ));
12 0 : return NULL;
13 0 : }
14 :
15 0 : if( FD_UNLIKELY( !fd_ulong_is_aligned((ulong)shmem, fd_ghost_align() ) ) ) {
16 0 : FD_LOG_WARNING(( "misaligned mem" ));
17 0 : return NULL;
18 0 : }
19 :
20 0 : ulong footprint = fd_ghost_footprint( node_max, vote_max );
21 0 : if( FD_UNLIKELY( !footprint ) ) {
22 0 : FD_LOG_WARNING(( "bad node_max (%lu) or vote_max (%lu)", node_max, vote_max ));
23 0 : return NULL;
24 0 : }
25 :
26 0 : fd_memset( shmem, 0, footprint );
27 0 : ulong laddr = (ulong)shmem;
28 0 : fd_ghost_t * ghost = (void *)laddr;
29 0 : laddr += sizeof(fd_ghost_t);
30 :
31 0 : laddr = fd_ulong_align_up( laddr, fd_ghost_node_pool_align() );
32 0 : ghost->node_pool = fd_ghost_node_pool_new( (void *)laddr, node_max );
33 0 : laddr += fd_ghost_node_pool_footprint( node_max );
34 :
35 0 : laddr = fd_ulong_align_up( laddr, fd_ghost_node_map_align() );
36 0 : ghost->node_map = fd_ghost_node_map_new( (void *)laddr, node_max, seed );
37 0 : laddr += fd_ghost_node_map_footprint( node_max );
38 :
39 0 : laddr = fd_ulong_align_up( laddr, fd_ghost_vote_pool_align() );
40 0 : ghost->vote_pool = fd_ghost_vote_pool_new( (void *)laddr, vote_max );
41 0 : laddr += fd_ghost_vote_pool_footprint( vote_max );
42 :
43 0 : laddr = fd_ulong_align_up( laddr, fd_ghost_vote_map_align() );
44 0 : ghost->vote_map = fd_ghost_vote_map_new( (void *)laddr, vote_max, seed );
45 0 : laddr += fd_ghost_vote_map_footprint( vote_max );
46 :
47 0 : laddr = fd_ulong_align_up( laddr, fd_ghost_align() );
48 0 : FD_TEST( laddr == (ulong)shmem + footprint );
49 :
50 0 : return shmem;
51 0 : }
52 :
53 : fd_ghost_t *
54 0 : fd_ghost_join( void * shghost ) {
55 :
56 0 : if( FD_UNLIKELY( !shghost ) ) {
57 0 : FD_LOG_WARNING(( "NULL ghost" ));
58 0 : return NULL;
59 0 : }
60 :
61 0 : if( FD_UNLIKELY( !fd_ulong_is_aligned((ulong)shghost, fd_ghost_align() ) ) ) {
62 0 : FD_LOG_WARNING(( "misaligned ghost" ));
63 0 : return NULL;
64 0 : }
65 :
66 0 : ulong laddr = (ulong)shghost; /* offset from a memory region */
67 0 : fd_ghost_t * ghost = (void *)shghost;
68 0 : laddr += sizeof(fd_ghost_t);
69 :
70 0 : laddr = fd_ulong_align_up( laddr, fd_ghost_node_pool_align() );
71 0 : ghost->node_pool = fd_ghost_node_pool_join( (void *)laddr );
72 0 : ulong node_max = fd_ghost_node_pool_max( ghost->node_pool );
73 0 : laddr += fd_ghost_node_pool_footprint( node_max );
74 :
75 0 : laddr = fd_ulong_align_up( laddr, fd_ghost_node_map_align() );
76 0 : ghost->node_map = fd_ghost_node_map_join( (void *)laddr );
77 0 : laddr += fd_ghost_node_map_footprint( node_max );
78 :
79 0 : laddr = fd_ulong_align_up( laddr, fd_ghost_vote_pool_align() );
80 0 : ghost->vote_pool = fd_ghost_vote_pool_join( (void *)laddr );
81 0 : ulong vote_max = fd_ghost_vote_pool_max( ghost->vote_pool );
82 0 : laddr += fd_ghost_vote_pool_footprint( vote_max );
83 :
84 0 : laddr = fd_ulong_align_up( laddr, fd_ghost_vote_map_align() );
85 0 : ghost->vote_map = fd_ghost_vote_map_join( (void *)laddr );
86 0 : laddr += fd_ghost_vote_map_footprint( vote_max );
87 :
88 0 : laddr = fd_ulong_align_up( laddr, fd_ghost_align() );
89 0 : FD_TEST( laddr == (ulong)shghost + fd_ghost_footprint( node_max, vote_max ));
90 :
91 0 : return ghost;
92 0 : }
93 :
94 : void *
95 0 : fd_ghost_leave( fd_ghost_t const * ghost ) {
96 :
97 0 : if( FD_UNLIKELY( !ghost ) ) {
98 0 : FD_LOG_WARNING(( "NULL ghost" ));
99 0 : return NULL;
100 0 : }
101 :
102 0 : return (void *)ghost;
103 0 : }
104 :
105 : void *
106 0 : fd_ghost_delete( void * ghost ) {
107 :
108 0 : if( FD_UNLIKELY( !ghost ) ) {
109 0 : FD_LOG_WARNING(( "NULL ghost" ));
110 0 : return NULL;
111 0 : }
112 :
113 0 : if( FD_UNLIKELY( !fd_ulong_is_aligned((ulong)ghost, fd_ghost_align() ) ) ) {
114 0 : FD_LOG_WARNING(( "misaligned ghost" ));
115 0 : return NULL;
116 0 : }
117 :
118 0 : return ghost;
119 0 : }
120 :
121 : void
122 0 : fd_ghost_init( fd_ghost_t * ghost, ulong root, ulong total_stake ) {
123 :
124 0 : if( FD_UNLIKELY( !ghost ) ) {
125 0 : FD_LOG_WARNING(( "NULL ghost" ));
126 0 : return;
127 0 : }
128 :
129 0 : if( FD_UNLIKELY( root == FD_SLOT_NULL ) ) {
130 0 : FD_LOG_WARNING(( "NULL slot" ));
131 0 : return;
132 0 : }
133 :
134 0 : if( FD_UNLIKELY( ghost->root ) ) {
135 0 : FD_LOG_WARNING(( "ghost already initialized" ));
136 0 : return;
137 0 : }
138 :
139 0 : fd_ghost_node_t * node = fd_ghost_node_pool_ele_acquire( ghost->node_pool );
140 0 : memset( node, 0, sizeof( fd_ghost_node_t ));
141 0 : node->slot = root;
142 :
143 0 : fd_ghost_node_map_ele_insert( ghost->node_map, node, ghost->node_pool );
144 0 : ghost->root = node;
145 0 : ghost->total_stake = total_stake;
146 :
147 0 : return;
148 0 : }
149 :
150 : /* clang-format on */
151 :
152 : fd_ghost_node_t *
153 0 : fd_ghost_insert( fd_ghost_t * ghost, ulong slot, ulong parent_slot ) {
154 0 : FD_LOG_DEBUG(( "[ghost] node_insert: %lu. parent: %lu.", slot, parent_slot ));
155 :
156 : /* Caller promises slot >= SMR. */
157 :
158 0 : #if FD_GHOST_USE_HANDHOLDING
159 0 : if (FD_UNLIKELY( slot < ghost->root->slot )) {
160 0 : FD_LOG_ERR(( "slot %lu is older than ghost root %lu", slot, ghost->root->slot ));
161 0 : }
162 0 : #endif
163 :
164 : /* Caller promises slot is not already in ghost. */
165 :
166 0 : #if FD_GHOST_USE_HANDHOLDING
167 0 : if( FD_UNLIKELY( fd_ghost_node_map_ele_query( ghost->node_map,
168 0 : &slot,
169 0 : NULL,
170 0 : ghost->node_pool ) ) ) {
171 0 : FD_LOG_ERR(( "slot %lu is already in ghost.", slot ));
172 0 : }
173 0 : #endif
174 :
175 0 : fd_ghost_node_t * parent = fd_ghost_node_map_ele_query( ghost->node_map,
176 0 : &parent_slot,
177 0 : NULL,
178 0 : ghost->node_pool );
179 :
180 : /* Caller promises parent_slot is already in ghost. */
181 :
182 0 : #if FD_GHOST_USE_HANDHOLDING
183 0 : if( FD_UNLIKELY( !fd_ghost_node_map_ele_query( ghost->node_map,
184 0 : &parent_slot,
185 0 : NULL,
186 0 : ghost->node_pool ) ) ) {
187 0 : FD_LOG_ERR(( "[fd_ghost_node_insert] missing parent_slot %lu.", parent_slot ));
188 0 : }
189 0 : #endif
190 :
191 : /* Caller promises node pool has a free element. */
192 :
193 0 : #if FD_GHOST_USE_HANDHOLDING
194 0 : if( FD_UNLIKELY( !fd_ghost_node_pool_free( ghost->node_pool ) ) ) {
195 0 : FD_LOG_ERR(( "[ghost] node_pool full. check pruning logic." ));
196 0 : }
197 0 : #endif
198 :
199 0 : fd_ghost_node_t * node = fd_ghost_node_pool_ele_acquire( ghost->node_pool );
200 0 : memset( node, 0, sizeof( fd_ghost_node_t ) );
201 0 : node->slot = slot;
202 :
203 : /* Insert into the map for O(1) random access. */
204 :
205 0 : fd_ghost_node_map_ele_insert( ghost->node_map, node, ghost->node_pool );
206 :
207 : /* Insert into the ghost tree. */
208 :
209 0 : node->child = NULL;
210 0 : node->sibling = NULL;
211 :
212 :
213 : /* Link node->parent. */
214 :
215 0 : node->parent = parent;
216 :
217 : /* Link parent->node and sibling->node. */
218 :
219 0 : if( FD_LIKELY( !parent->child ) ) {
220 :
221 : /* No siblings, which means no forks. This is the likely case. */
222 :
223 0 : parent->child = node;
224 :
225 0 : } else {
226 :
227 : /* Iterate to right-most sibling. */
228 :
229 0 : fd_ghost_node_t * curr = parent->child;
230 0 : while( curr->sibling ) {
231 0 : curr = curr->sibling;
232 0 : }
233 :
234 : /* Link to right-most sibling. */
235 :
236 0 : curr->sibling = node;
237 0 : }
238 :
239 : /* Return newly-created node. */
240 :
241 0 : return node;
242 0 : }
243 :
244 : fd_ghost_node_t const *
245 0 : fd_ghost_head( fd_ghost_t const * ghost ) {
246 0 : fd_ghost_node_t const * head = ghost->root;
247 0 : while( head->child ) {
248 0 : head = head->child;
249 0 : fd_ghost_node_t const * curr = head;
250 0 : while( curr ) {
251 :
252 : /* clang-format off */
253 :
254 0 : head = fd_ptr_if(
255 0 : fd_int_if(
256 : /* if the weights are equal... */
257 :
258 0 : curr->weight == head->weight,
259 :
260 : /* ...tie-break by slot number */
261 :
262 0 : curr->slot < head->slot,
263 :
264 : /* otherwise return curr if curr > head */
265 :
266 0 : curr->weight > head->weight ),
267 0 : curr, head );
268 :
269 : /* clang-format on */
270 :
271 0 : curr = curr->sibling;
272 0 : }
273 0 : }
274 0 : return head;
275 0 : }
276 :
277 : fd_ghost_node_t const *
278 0 : fd_ghost_replay_vote( fd_ghost_t * ghost, ulong slot, fd_pubkey_t const * pubkey, ulong stake ) {
279 0 : FD_LOG_DEBUG(( "[%s] slot %lu, pubkey %s, stake %lu", __func__, slot, FD_BASE58_ENC_32_ALLOCA( pubkey ), stake ));
280 :
281 0 : #if FD_GHOST_USE_HANDHOLDING
282 0 : if( FD_UNLIKELY( slot < ghost->root->slot ) ) {
283 0 : FD_LOG_ERR(( "caller must only insert vote slots >= ghost root. vote: %lu, root: %lu",
284 0 : slot,
285 0 : ghost->root->slot ));
286 0 : }
287 0 : #endif
288 :
289 0 : fd_ghost_node_t * node = fd_ghost_node_map_ele_query( ghost->node_map,
290 0 : &slot,
291 0 : NULL,
292 0 : ghost->node_pool );
293 :
294 0 : #if FD_GHOST_USE_HANDHOLDING
295 : /* Caller promises node is already in ghost. */
296 0 : if( FD_UNLIKELY( !node ) ) {
297 0 : FD_LOG_ERR(( "missing ghost node" ));
298 0 : }
299 :
300 0 : #endif
301 :
302 : /* Query pubkey's latest vote. */
303 :
304 0 : fd_ghost_vote_t * latest_vote = fd_ghost_vote_map_ele_query( ghost->vote_map,
305 0 : pubkey,
306 0 : NULL,
307 0 : ghost->vote_pool );
308 :
309 0 : if( FD_LIKELY( latest_vote ) ) {
310 :
311 : /* Return if this new vote slot is not > than latest vote. It is
312 : important that the vote slots are monotonically increasing,
313 : because the order we receive blocks is non-deterministic (due to
314 : network propagation variance), so we may process forks in a
315 : different order from the sender of this vote.
316 :
317 : For example, if a validator votes on A then switches to B, we
318 : might instead process B then A. In this case, the validator's
319 : vote account state on B would contain a strictly higher vote slot
320 : than A (due to lockout), so we would observe while processing A,
321 : that the vote slot < the latest vote slot we have saved for that
322 : validator. */
323 :
324 0 : if( FD_UNLIKELY( slot <= latest_vote->slot ) ) return node;
325 :
326 0 : fd_ghost_node_t * node = fd_ghost_node_map_ele_query( ghost->node_map,
327 0 : &latest_vote->slot,
328 0 : NULL,
329 0 : ghost->node_pool );
330 :
331 0 : if( FD_UNLIKELY( !node ) ) {
332 :
333 0 : FD_LOG_NOTICE(( "[ghost] %s's latest vote slot %lu was too old and already pruned.",
334 0 : FD_BASE58_ENC_32_ALLOCA( pubkey ),
335 0 : latest_vote->slot ));
336 :
337 0 : } else {
338 :
339 : /* Subtract pubkey's stake from the prev voted slot hash and propagate. */
340 :
341 0 : FD_LOG_DEBUG(( "[ghost] removing (%s, %lu, %lu)",
342 0 : FD_BASE58_ENC_32_ALLOCA( pubkey ),
343 0 : latest_vote->stake,
344 0 : latest_vote->slot ));
345 :
346 0 : int cf = __builtin_usubl_overflow( node->stake, latest_vote->stake, &node->stake );
347 0 : if( FD_UNLIKELY( cf ) ) {
348 0 : FD_LOG_WARNING(( "[%s] sub overflow. node->stake %lu latest_vote->stake %lu",
349 0 : __func__,
350 0 : node->stake,
351 0 : latest_vote->stake ));
352 0 : node->stake = 0;
353 0 : }
354 0 : fd_ghost_node_t * ancestor = node;
355 0 : while( ancestor->parent ) {
356 0 : int cf = __builtin_usubl_overflow( ancestor->weight,
357 0 : latest_vote->stake,
358 0 : &ancestor->weight );
359 0 : if( FD_UNLIKELY( cf ) ) {
360 0 : FD_LOG_WARNING(( "[%s] sub overflow. ancestor->weight %lu latest_vote->stake %lu",
361 0 : __func__,
362 0 : ancestor->weight,
363 0 : latest_vote->stake ));
364 0 : ancestor->weight = 0;
365 0 : }
366 0 : ancestor = ancestor->parent;
367 0 : }
368 0 : }
369 :
370 0 : } else {
371 :
372 : /* Ghost has not seen this pubkey vote yet, so insert. */
373 :
374 0 : #if FD_GHOST_USE_HANDHOLDING
375 : /* OOM: we've exceeded the max number of voter pubkeys that were
376 : statically allocated. */
377 0 : if( FD_UNLIKELY( !fd_ghost_vote_pool_free( ghost->vote_pool ) ) ) {
378 0 : FD_LOG_ERR(( "[ghost] vote_pool full. check # of validators." ));
379 0 : }
380 0 : #endif
381 :
382 0 : latest_vote = fd_ghost_vote_pool_ele_acquire( ghost->vote_pool );
383 0 : latest_vote->pubkey = *pubkey;
384 0 : latest_vote->slot = slot;
385 0 : latest_vote->stake = stake;
386 0 : fd_ghost_vote_map_ele_insert( ghost->vote_map, latest_vote, ghost->vote_pool );
387 0 : }
388 0 : latest_vote->slot = slot;
389 0 : latest_vote->stake = stake;
390 :
391 : /* Propagate the vote stake up the ancestry, including updating the
392 : head. */
393 :
394 0 : FD_LOG_DEBUG(( "[ghost] adding (%s, %lu, %lu)", FD_BASE58_ENC_32_ALLOCA( pubkey ), stake, latest_vote->slot ));
395 0 : int cf = __builtin_uaddl_overflow( node->stake, latest_vote->stake, &node->stake );
396 0 : if( FD_UNLIKELY( cf ) ) {
397 0 : FD_LOG_ERR(( "[%s] add overflow. node->stake %lu latest_vote->stake %lu",
398 0 : __func__,
399 0 : node->stake,
400 0 : latest_vote->stake ));
401 0 : }
402 0 : fd_ghost_node_t * ancestor = node;
403 0 : while( ancestor->parent ) {
404 0 : int cf = __builtin_uaddl_overflow( ancestor->weight, latest_vote->stake, &ancestor->weight );
405 0 : if( FD_UNLIKELY( cf ) ) {
406 0 : FD_LOG_ERR(( "[%s] add overflow. ancestor->weight %lu latest_vote->stake %lu",
407 0 : __func__,
408 0 : ancestor->weight,
409 0 : latest_vote->stake ));
410 0 : }
411 0 : ancestor = ancestor->parent;
412 0 : }
413 :
414 0 : #if FD_GHOST_USE_HANDHOLDING
415 0 : if( FD_UNLIKELY( node->stake > ghost->total_stake ) ) {
416 0 : FD_LOG_ERR(( "[%s] invariant violation. node->stake > total stake."
417 0 : "slot: %lu, "
418 0 : "node->stake %lu, "
419 0 : "ghost->total_stake %lu",
420 0 : __func__,
421 0 : slot,
422 0 : node->stake,
423 0 : ghost->total_stake ));
424 0 : }
425 0 : #endif
426 :
427 0 : return node;
428 0 : }
429 :
430 : fd_ghost_node_t const *
431 : fd_ghost_gossip_vote( FD_PARAM_UNUSED fd_ghost_t * ghost,
432 : FD_PARAM_UNUSED ulong slot,
433 : FD_PARAM_UNUSED fd_pubkey_t const * pubkey,
434 0 : FD_PARAM_UNUSED ulong stake ) {
435 0 : FD_LOG_ERR(( "unimplemented" ));
436 0 : }
437 :
438 : fd_ghost_node_t const *
439 0 : fd_ghost_rooted_vote( fd_ghost_t * ghost, ulong root, fd_pubkey_t const * pubkey, ulong stake ) {
440 0 : FD_LOG_DEBUG(( "[%s] root %lu, pubkey %s, stake %lu", __func__, root, FD_BASE58_ENC_32_ALLOCA( pubkey ), stake ));
441 :
442 0 : #if FD_GHOST_USE_HANDHOLDING
443 0 : if( FD_UNLIKELY( root < ghost->root->slot ) ) {
444 0 : FD_LOG_ERR(( "caller must only insert vote slots >= ghost root. vote: %lu, root: %lu",
445 0 : root,
446 0 : ghost->root->slot ));
447 0 : }
448 0 : #endif
449 :
450 : /* It is invariant that the voter's root is found in ghost (as long as
451 : voter's root >= our root ). This is because voter's root is sourced
452 : from their vote state, so it must be on the fork we're replaying
453 : and we must have already inserted their root slot into ghost. */
454 :
455 0 : fd_ghost_node_t * node = fd_ghost_node_map_ele_query( ghost->node_map,
456 0 : &root,
457 0 : NULL,
458 0 : ghost->node_pool );
459 :
460 0 : #if FD_GHOST_USE_HANDHOLDING
461 0 : if( FD_UNLIKELY( !node ) ) {
462 0 : FD_LOG_ERR(( "[%s] invariant violation. missing voter %s's root %lu.", __func__, FD_BASE58_ENC_32_ALLOCA( pubkey ), root ));
463 0 : }
464 0 : #endif
465 :
466 : /* Add to the rooted stake. */
467 :
468 0 : node->rooted_stake += stake;
469 0 : return node;
470 0 : }
471 :
472 : fd_ghost_node_t const *
473 0 : fd_ghost_publish( fd_ghost_t * ghost, ulong slot ) {
474 :
475 0 : #if FD_GHOST_USE_HANDHOLDING
476 0 : if( FD_UNLIKELY( slot < ghost->root->slot ) ) {
477 0 : FD_LOG_WARNING(( "[fd_ghost_publish] trying to publish slot %lu older than ghost->root %lu.",
478 0 : slot,
479 0 : ghost->root->slot ));
480 0 : return NULL;
481 0 : }
482 0 : if( FD_UNLIKELY( slot == ghost->root->slot ) ) {
483 0 : FD_LOG_WARNING(( "[fd_ghost_publish] publishing same slot %lu as ghost->root %lu.",
484 0 : slot,
485 0 : ghost->root->slot ));
486 0 : return NULL;
487 0 : }
488 0 : #endif
489 :
490 0 : fd_ghost_node_t * root = fd_ghost_node_map_ele_query( ghost->node_map,
491 0 : &slot,
492 0 : NULL,
493 0 : ghost->node_pool );
494 :
495 0 : #if FD_GHOST_USE_HANDHOLDING
496 0 : if( FD_UNLIKELY( !root ) ) {
497 0 : FD_LOG_ERR(( "[fd_ghost_publish] publish slot %lu not found in ghost", slot ));
498 0 : }
499 :
500 0 : #endif
501 :
502 : /* First, remove the previous root, and add it to the prune list.
503 :
504 : In this context, head is the list head (not to be confused with the
505 : ghost head.) */
506 :
507 0 : fd_ghost_node_t * head = fd_ghost_node_map_ele_remove( ghost->node_map,
508 0 : &ghost->root->slot,
509 0 : NULL,
510 0 : ghost->node_pool );
511 0 : head->next = fd_ghost_node_pool_idx_null( ghost->node_pool );
512 0 : fd_ghost_node_t * tail = head;
513 :
514 : /* Second, BFS down the tree, adding nodes to the prune queue except
515 : for the new root.
516 :
517 : Loop invariant: the old root must be in new root's ancestry. */
518 :
519 0 : while( head ) {
520 0 : fd_ghost_node_t * child = head->child;
521 :
522 0 : while( FD_LIKELY( child ) ) {
523 :
524 : /* Do not prune the new root. */
525 :
526 0 : if( FD_LIKELY( child != root ) ) {
527 :
528 : /* Remove the child from the map and push the child onto the list. */
529 :
530 0 : tail->next = fd_ghost_node_map_idx_remove( ghost->node_map,
531 0 : &child->slot,
532 0 : fd_ghost_node_pool_idx_null( ghost->node_pool ),
533 0 : ghost->node_pool );
534 0 : #if FD_GHOST_USE_HANDHOLDING
535 0 : if( FD_UNLIKELY( tail->next == fd_ghost_node_pool_idx_null( ghost->node_pool ) ) ) {
536 0 : FD_LOG_ERR(( "Failed to remove child. Child must exist given the while condition. "
537 0 : "Possible memory corruption or data race." ));
538 0 : }
539 0 : #endif
540 0 : tail = fd_ghost_node_pool_ele( ghost->node_pool, tail->next );
541 0 : tail->next = fd_ghost_node_pool_idx_null( ghost->node_pool );
542 0 : }
543 :
544 0 : child = child->sibling;
545 0 : }
546 :
547 : /* Free the head, and move the head pointer forward. */
548 :
549 0 : fd_ghost_node_t * next = fd_ghost_node_pool_ele( ghost->node_pool, head->next );
550 0 : fd_ghost_node_pool_ele_release( ghost->node_pool, head );
551 0 : head = next;
552 0 : }
553 :
554 : /* Unlink the root and set the new root. */
555 :
556 0 : root->parent = NULL;
557 0 : ghost->root = root;
558 :
559 0 : return root;
560 0 : }
561 :
562 : fd_ghost_node_t const *
563 0 : fd_ghost_gca( fd_ghost_t const * ghost, ulong slot1, ulong slot2 ) {
564 0 : fd_ghost_node_t const * node1 = fd_ghost_query( ghost, slot1 );
565 0 : fd_ghost_node_t const * node2 = fd_ghost_query( ghost, slot2 );
566 :
567 0 : #if FD_GHOST_USE_HANDHOLDING
568 0 : if( FD_UNLIKELY( !node1 ) ) {
569 0 : FD_LOG_WARNING(( "slot1 %lu is missing from ghost", slot1 ));
570 0 : return NULL;
571 0 : }
572 :
573 0 : if( FD_UNLIKELY( !node2 ) ) {
574 0 : FD_LOG_WARNING(( "slot2 %lu is missing from ghost", slot2 ));
575 0 : return NULL;
576 0 : }
577 0 : #endif
578 :
579 : /* Find the greatest common ancestor. */
580 :
581 0 : while( node1 && node2 ) {
582 0 : if( FD_UNLIKELY( node1->slot == node2->slot ) ) return node1;
583 0 : if( node1->slot > node2->slot ) {
584 0 : node1 = node1->parent;
585 0 : } else {
586 0 : node2 = node2->parent;
587 0 : }
588 0 : }
589 :
590 0 : FD_LOG_ERR(( "Unable to find GCA. Is this a valid ghost?" ));
591 0 : }
592 :
593 : int
594 0 : fd_ghost_is_descendant( fd_ghost_t const * ghost, ulong slot, ulong ancestor_slot ) {
595 0 : fd_ghost_node_t const * ancestor = fd_ghost_query( ghost, slot );
596 0 : #if FD_GHOST_USE_HANDHOLDING
597 :
598 0 : if( FD_UNLIKELY( ancestor_slot < ghost->root->slot ) ) {
599 0 : FD_LOG_ERR(( "[%s] ancestor_slot %lu is older than ghost root %lu.",
600 0 : __func__,
601 0 : ancestor_slot,
602 0 : ghost->root->slot ));
603 0 : }
604 :
605 0 : if( FD_UNLIKELY( !ancestor ) ) {
606 :
607 : /* Slot not found, so we won't find the ancestor. */
608 :
609 0 : FD_LOG_WARNING(( "[%s] unable to find slot %lu in ghost.", __func__, slot ));
610 0 : return 0;
611 0 : }
612 0 : #endif
613 :
614 : /* Look for ancestor_slot in the fork ancestry.
615 :
616 : Stop looking when there is either no ancestry remaining or there is
617 : no reason to look further because we've searched past the
618 : ancestor_slot. */
619 :
620 0 : while( FD_LIKELY( ancestor && ancestor->slot >= ancestor_slot ) ) {
621 0 : if( FD_UNLIKELY( ancestor->slot == ancestor_slot ) ) return 1; /* optimize for not found */
622 0 : ancestor = ancestor->parent;
623 0 : }
624 0 : return 0; /* not found */
625 0 : }
626 :
627 : static void
628 0 : print( fd_ghost_node_t const * node, int space, const char * prefix, ulong total ) {
629 0 : if( node == NULL ) return;
630 :
631 0 : if( space > 0 ) printf( "\n" );
632 0 : for( int i = 0; i < space; i++ )
633 0 : printf( " " );
634 0 : if( FD_UNLIKELY( node->weight > 100 ) ) {
635 0 : }
636 0 : double pct = ( (double)node->weight / (double)total ) * 100;
637 0 : if( FD_UNLIKELY( total == 0 ) ) {
638 0 : printf( "%s%lu (%lu)", prefix, node->slot, node->weight );
639 0 : } else if( FD_UNLIKELY( pct < 0.99 ) ) {
640 0 : printf( "%s%lu (%.0lf%%, %lu)", prefix, node->slot, pct, node->weight );
641 0 : } else {
642 0 : printf( "%s%lu (%.0lf%%)", prefix, node->slot, pct );
643 0 : }
644 :
645 0 : fd_ghost_node_t * curr = node->child;
646 0 : char new_prefix[1024]; /* Large enough to hold the new prefix string */
647 0 : while( curr ) {
648 0 : if( curr->sibling ) {
649 0 : sprintf( new_prefix, "├── " ); /* Branch indicating more siblings follow */
650 0 : print( curr, space + 4, new_prefix, total );
651 0 : } else {
652 0 : sprintf( new_prefix, "└── " ); /* End branch */
653 0 : print( curr, space + 4, new_prefix, total );
654 0 : }
655 0 : curr = curr->sibling;
656 0 : }
657 0 : }
658 :
659 : void
660 0 : fd_ghost_slot_print( fd_ghost_t * ghost, ulong slot, ulong depth ) {
661 0 : fd_ghost_node_t const * node = fd_ghost_query( ghost, slot );
662 0 : if( FD_UNLIKELY( !node ) ) {
663 0 : FD_LOG_WARNING(( "[fd_ghost_print_node] NULL node." ));
664 0 : return;
665 0 : }
666 0 : fd_ghost_node_t const * ancestor = node;
667 0 : for( ulong i = 0; i < depth; i++ ) {
668 0 : if( !ancestor->parent ) break;
669 0 : ancestor = ancestor->parent;
670 0 : }
671 0 : print( ancestor, 0, "", ghost->total_stake );
672 0 : printf( "\n\n" );
673 0 : }
|
