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