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 initalized" ));
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 uninitalized 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_UNLIKELY( parent->weight < children_weight ) ) {
215 0 : FD_LOG_WARNING(( "[%s] invariant violation. %lu's weight: %lu < children's weight: %lu", __func__, parent->slot, parent->weight, children_weight ));
216 0 : return -1;
217 0 : }
218 0 : parent = fd_ghost_node_pool_ele_const( node_pool, parent->next );
219 0 : }
220 :
221 0 : return 0;
222 0 : }
223 :
224 : fd_ghost_node_t *
225 0 : fd_ghost_insert( fd_ghost_t * ghost, ulong parent_slot, ulong slot ) {
226 0 : VER_INC;
227 :
228 0 : FD_LOG_DEBUG(( "[%s] slot: %lu. parent: %lu.", __func__, slot, parent_slot ));
229 :
230 0 : #if FD_GHOST_USE_HANDHOLDING
231 0 : FD_TEST( ghost->magic == FD_GHOST_MAGIC );
232 0 : #endif
233 :
234 0 : fd_ghost_node_map_t * node_map = fd_ghost_node_map( ghost );
235 0 : fd_ghost_node_t * node_pool = fd_ghost_node_pool( ghost );
236 :
237 0 : ulong null_idx = fd_ghost_node_pool_idx_null( node_pool );
238 0 : fd_ghost_node_t * parent_ele = fd_ghost_node_map_ele_query( node_map, &parent_slot, NULL, node_pool );
239 0 : ulong parent_idx = fd_ghost_node_pool_idx( node_pool, parent_ele );
240 0 : fd_ghost_node_t const * root = fd_ghost_root( ghost );
241 :
242 0 : #if FD_GHOST_USE_HANDHOLDING
243 0 : if( FD_UNLIKELY( fd_ghost_query( ghost, slot ) ) ) { /* slot already in ghost */
244 0 : FD_LOG_WARNING(( "[%s] slot %lu already in ghost.", __func__, slot ));
245 0 : return NULL;
246 0 : }
247 :
248 0 : if( FD_UNLIKELY( !parent_ele ) ) { /* parent_slot not in ghost */
249 0 : FD_LOG_WARNING(( "[%s] missing `parent_slot` %lu.", __func__, parent_slot ));
250 0 : return NULL;
251 0 : }
252 :
253 0 : if( FD_UNLIKELY( !fd_ghost_node_pool_free( node_pool ) ) ) { /* ghost full */
254 0 : FD_LOG_WARNING(( "[%s] ghost full.", __func__ ));
255 0 : return NULL;
256 0 : }
257 :
258 0 : if( FD_UNLIKELY( slot <= root->slot ) ) { /* slot must > root */
259 0 : FD_LOG_WARNING(( "[%s] slot %lu <= root %lu", __func__, slot, root->slot ));
260 0 : return NULL;
261 0 : }
262 0 : #endif
263 :
264 0 : fd_ghost_node_t * node_ele = fd_ghost_node_pool_ele_acquire( node_pool );
265 0 : ulong node_idx = fd_ghost_node_pool_idx( node_pool, node_ele );
266 :
267 0 : memset( node_ele, 0, sizeof(fd_ghost_node_t) );
268 0 : node_ele->slot = slot;
269 0 : node_ele->next = null_idx;
270 0 : node_ele->valid = 1;
271 0 : node_ele->parent_idx = null_idx;
272 0 : node_ele->child_idx = null_idx;
273 0 : node_ele->sibling_idx = null_idx;
274 :
275 : /* Insert into the map for O(1) random access. */
276 :
277 0 : fd_ghost_node_map_ele_insert( node_map, node_ele, node_pool ); /* cannot fail */
278 :
279 : /* Link node->parent. */
280 :
281 0 : node_ele->parent_idx = parent_idx;
282 :
283 : /* Link parent->node and sibling->node. */
284 :
285 0 : if( FD_LIKELY( parent_ele->child_idx == null_idx ) ) {
286 :
287 : /* No children yet so set as left-most child. */
288 :
289 0 : parent_ele->child_idx = node_idx;
290 :
291 0 : } else {
292 :
293 : /* Already have children so iterate to right-most sibling. */
294 :
295 0 : fd_ghost_node_t * curr = fd_ghost_node_pool_ele( node_pool, parent_ele->child_idx );
296 0 : while( curr->sibling_idx != null_idx ) {
297 0 : curr = fd_ghost_node_pool_ele( node_pool, curr->sibling_idx );
298 0 : }
299 :
300 : /* Link to right-most sibling. */
301 :
302 0 : curr->sibling_idx = node_idx;
303 0 : }
304 :
305 : /* Return newly-created node. */
306 :
307 0 : return node_ele;
308 0 : }
309 :
310 : fd_ghost_node_t const *
311 0 : fd_ghost_head( fd_ghost_t const * ghost, fd_ghost_node_t const * node ) {
312 0 : #if FD_GHOST_USE_HANDHOLDING
313 0 : FD_TEST( ghost->magic == FD_GHOST_MAGIC );
314 0 : FD_TEST( node );
315 0 : #endif
316 :
317 0 : fd_ghost_node_t const * node_pool = fd_ghost_node_pool_const( ghost );
318 0 : fd_ghost_node_t const * head = node;
319 0 : ulong null_idx = fd_ghost_node_pool_idx_null( node_pool );
320 :
321 0 : while( head->child_idx != null_idx ) {
322 0 : head = fd_ghost_node_pool_ele_const( node_pool, head->child_idx );
323 0 : fd_ghost_node_t const * curr = head;
324 0 : while( curr ) {
325 :
326 0 : head = fd_ptr_if(
327 0 : fd_int_if(
328 : /* if the weights are equal... */
329 :
330 0 : curr->weight == head->weight,
331 :
332 : /* ...tie-break by slot number */
333 :
334 0 : curr->slot < head->slot,
335 :
336 : /* otherwise return curr if curr > head */
337 :
338 0 : curr->weight > head->weight ),
339 0 : curr, head );
340 :
341 0 : curr = fd_ghost_node_pool_ele_const( node_pool, curr->sibling_idx );
342 0 : }
343 0 : }
344 0 : return head;
345 0 : }
346 :
347 : void
348 0 : fd_ghost_replay_vote( fd_ghost_t * ghost, fd_voter_t * voter, ulong slot ) {
349 0 : VER_INC;
350 :
351 0 : FD_LOG_DEBUG(( "[%s] slot %lu, pubkey %s, stake %lu", __func__, slot, FD_BASE58_ENC_32_ALLOCA( &voter->key ), voter->stake ));
352 :
353 0 : fd_ghost_node_map_t * node_map = fd_ghost_node_map( ghost );
354 0 : fd_ghost_node_t * node_pool = fd_ghost_node_pool( ghost );
355 0 : ulong vote = voter->replay_vote;
356 0 : fd_ghost_node_t const * root = fd_ghost_root( ghost );
357 :
358 0 : #if FD_GHOST_USE_HANDHOLDING
359 0 : if( FD_UNLIKELY( slot < root->slot ) ) FD_LOG_ERR(( "[%s] illegal argument. vote slot: %lu, root: %lu", __func__, slot, root->slot ));
360 0 : #endif
361 :
362 0 : do {
363 : /* LMD-rule: subtract the voter's stake from previous vote. There
364 : are several cases where we skip this subtraction. */
365 :
366 : /* Case 1: It's the first vote we have seen from this pubkey. */
367 :
368 0 : if( FD_UNLIKELY( vote == FD_SLOT_NULL ) ) break;
369 :
370 : /* Case 2: Return early if the vote slot <= the voter's last tower
371 : vote. It is important that the vote slots are monotonically
372 : increasing, because the order we receive blocks is
373 : non-deterministic (due to network propagation variance), so we
374 : may process forks in a different order from the sender of this
375 : vote.
376 :
377 : For example, if a validator votes on A then switches to B, we
378 : might instead process B then A. In this case, the validator's
379 : tower on B would contain a strictly higher vote slot than A (due
380 : to lockout), so we would observe while processing A, that the
381 : vote slot < the last vote slot we have saved for that validator.
382 : */
383 :
384 0 : if( FD_UNLIKELY( slot <= vote ) ) return;
385 :
386 : /* Case 3: Previous vote slot was pruned when the SMR moved. */
387 :
388 0 : if( FD_UNLIKELY( vote < root->slot ) ) break;
389 :
390 : /* Case 4: When a node has been stuck on a minority fork for a
391 : while, and we end up pruning that fork when we update the SMR.
392 : In this case, we need to re-add their stake to the fork they are
393 : now voting for. In this case, it's possible that the previously
394 : saved vote slot is > than our root, but has been pruned. */
395 :
396 0 : fd_ghost_node_t * node = fd_ghost_node_map_ele_query( node_map, &vote, NULL, node_pool );
397 0 : if( FD_UNLIKELY( !node ) ){
398 0 : FD_LOG_WARNING(( "missing/pruned ghost node for previous vote %lu; now voting for slot %lu", vote, slot ));
399 0 : break;
400 0 : }
401 :
402 : /* Do stake subtraction */
403 :
404 0 : FD_LOG_DEBUG(( "[%s] removing (%s, %lu, %lu)", __func__, FD_BASE58_ENC_32_ALLOCA( &voter->key ), voter->stake, vote ));
405 :
406 0 : #if FD_GHOST_USE_HANDHOLDING
407 0 : int cf = __builtin_usubl_overflow( node->replay_stake, voter->stake, &node->replay_stake );
408 0 : if( FD_UNLIKELY( cf ) ) FD_LOG_ERR(( "[%s] sub overflow. node stake %lu voter stake %lu", __func__, node->replay_stake, voter->stake ));
409 : #else
410 : node->replay_stake -= voter->stake;
411 : #endif
412 :
413 0 : fd_ghost_node_t * ancestor = node;
414 0 : while( ancestor ) {
415 0 : cf = __builtin_usubl_overflow( ancestor->weight, voter->stake, &ancestor->weight );
416 0 : #if FD_GHOST_USE_HANDHOLDING
417 0 : if( FD_UNLIKELY( cf ) ) FD_LOG_ERR(( "[%s] sub overflow. ancestor->weight %lu latest_vote->stake %lu", __func__, ancestor->weight, voter->stake ));
418 : #else
419 : ancestor_weight -= voter->stake;
420 : #endif
421 0 : ancestor = fd_ghost_node_pool_ele( node_pool, ancestor->parent_idx );
422 0 : }
423 0 : } while ( 0 );
424 :
425 : /* Add voter's stake to the ghost node keyed by `slot`. Propagate the
426 : vote stake up the ancestry. We do this for all cases we exited
427 : above: this vote is the first vote we've seen from a pubkey,
428 : this vote is switched from a previous vote that was on a missing
429 : node (pruned), or the regular case */
430 :
431 0 : FD_LOG_DEBUG(( "[%s] adding (%s, %lu, %lu)", __func__, FD_BASE58_ENC_32_ALLOCA( &voter->key ), voter->stake, slot ));
432 :
433 0 : fd_ghost_node_t * node = fd_ghost_node_map_ele_query( node_map, &slot, NULL, node_pool );
434 0 : #if FD_GHOST_USE_HANDHOLDING
435 0 : if( FD_UNLIKELY( !node ) ) FD_LOG_ERR(( "missing ghost node" )); /* slot must be in ghost. */
436 0 : #endif
437 :
438 0 : #if FD_GHOST_USE_HANDHOLDING
439 0 : int cf = __builtin_uaddl_overflow( node->replay_stake, voter->stake, &node->replay_stake );
440 0 : if( FD_UNLIKELY( cf ) ) FD_LOG_ERR(( "[%s] add overflow. node->stake %lu latest_vote->stake %lu", __func__, node->replay_stake, voter->stake ));
441 : #else
442 : node->replay_stake += voter->stake;
443 : #endif
444 :
445 0 : fd_ghost_node_t * ancestor = node;
446 0 : while( ancestor ) {
447 0 : #if FD_GHOST_USE_HANDHOLDING
448 0 : int cf = __builtin_uaddl_overflow( ancestor->weight, voter->stake, &ancestor->weight );
449 0 : if( FD_UNLIKELY( cf ) ) FD_LOG_ERR(( "[%s] add overflow. ancestor->weight %lu latest_vote->stake %lu", __func__, ancestor->weight, voter->stake ));
450 : #else
451 : ancestor_weight += voter->stake;
452 : #endif
453 0 : ancestor = fd_ghost_node_pool_ele( node_pool, ancestor->parent_idx );
454 0 : }
455 :
456 0 : voter->replay_vote = slot; /* update the cached replay vote slot on voter */
457 0 : }
458 :
459 : void
460 : fd_ghost_gossip_vote( FD_PARAM_UNUSED fd_ghost_t * ghost,
461 : FD_PARAM_UNUSED fd_voter_t * voter,
462 0 : FD_PARAM_UNUSED ulong slot ) {
463 0 : FD_LOG_ERR(( "unimplemented" ));
464 0 : }
465 :
466 : void
467 0 : fd_ghost_rooted_vote( fd_ghost_t * ghost, fd_voter_t * voter, ulong root ) {
468 0 : VER_INC;
469 :
470 0 : FD_LOG_DEBUG(( "[%s] root %lu, pubkey %s, stake %lu", __func__, root, FD_BASE58_ENC_32_ALLOCA(&voter->key), voter->stake ));
471 :
472 0 : fd_ghost_node_map_t * node_map = fd_ghost_node_map( ghost );
473 0 : fd_ghost_node_t * node_pool = fd_ghost_node_pool( ghost );
474 0 : fd_ghost_node_t const * root_node = fd_ghost_root( ghost );
475 :
476 0 : #if FD_GHOST_USE_HANDHOLDING
477 0 : if( FD_UNLIKELY( root < root_node->slot ) ) {
478 0 : FD_LOG_ERR(( "caller must only insert vote slots >= ghost root. vote: %lu, root: %lu", root, root_node->slot ));
479 0 : }
480 0 : #endif
481 :
482 : /* It is invariant that the voter's root is found in ghost (as long as
483 : voter's root >= our root ). This is because voter's root is sourced
484 : from their vote state, so it must be on the fork we're replaying
485 : and we must have already inserted their root slot into ghost. */
486 :
487 0 : fd_ghost_node_t * node = fd_ghost_node_map_ele_query( node_map, &root, NULL, node_pool );
488 0 : #if FD_GHOST_USE_HANDHOLDING
489 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 ));
490 0 : #endif
491 :
492 : /* Add to the rooted stake. */
493 :
494 0 : node->rooted_stake += voter->stake;
495 0 : }
496 :
497 : fd_ghost_node_t const *
498 0 : fd_ghost_publish( fd_ghost_t * ghost, ulong slot ) {
499 0 : FD_LOG_NOTICE(( "[%s] slot %lu", __func__, slot ));
500 0 : VER_INC;
501 :
502 0 : fd_ghost_node_map_t * node_map = fd_ghost_node_map( ghost );
503 0 : fd_ghost_node_t * node_pool = fd_ghost_node_pool( ghost );
504 0 : fd_ghost_node_t const * root_node = fd_ghost_root( ghost );
505 0 : ulong null_idx = fd_ghost_node_pool_idx_null( node_pool );
506 :
507 0 : #if FD_GHOST_USE_HANDHOLDING
508 0 : if( FD_UNLIKELY( slot < root_node->slot ) ) {
509 0 : FD_LOG_WARNING(( "[fd_ghost_publish] trying to publish slot %lu older than ghost->root %lu.",
510 0 : slot,
511 0 : root_node->slot ));
512 0 : return NULL;
513 0 : }
514 0 : if( FD_UNLIKELY( slot == root_node->slot ) ) {
515 0 : FD_LOG_WARNING(( "[fd_ghost_publish] publishing same slot %lu as ghost->root %lu.",
516 0 : slot,
517 0 : root_node->slot ));
518 0 : return NULL;
519 0 : }
520 0 : #endif
521 :
522 : // new root
523 0 : fd_ghost_node_t * root = fd_ghost_node_map_ele_query( node_map,
524 0 : &slot,
525 0 : NULL,
526 0 : node_pool );
527 :
528 0 : #if FD_GHOST_USE_HANDHOLDING
529 0 : if( FD_UNLIKELY( !root ) ) {
530 0 : FD_LOG_ERR(( "[fd_ghost_publish] publish slot %lu not found in ghost", slot ));
531 0 : }
532 :
533 0 : #endif
534 :
535 : /* First, remove the previous root, and add it to the prune list.
536 :
537 : In this context, head is the list head (not to be confused with the
538 : ghost head.) */
539 :
540 0 : fd_ghost_node_t * head = fd_ghost_node_map_ele_remove( node_map,
541 0 : &root_node->slot,
542 0 : NULL,
543 0 : node_pool );
544 0 : head->next = fd_ghost_node_pool_idx_null( node_pool );
545 0 : fd_ghost_node_t * tail = head;
546 :
547 : /* Second, BFS down the tree, adding nodes to the prune queue except
548 : for the new root.
549 :
550 : Loop invariant: the old root must be in new root's ancestry. */
551 :
552 0 : while( head ) {
553 0 : fd_ghost_node_t * child = fd_ghost_node_pool_ele( node_pool, head->child_idx );
554 :
555 0 : while( FD_LIKELY( child ) ) {
556 :
557 : /* Do not prune the new root. */
558 :
559 0 : if( FD_LIKELY( child != root ) ) {
560 :
561 : /* Remove the child from the map and push the child onto the list. */
562 :
563 0 : tail->next = fd_ghost_node_map_idx_remove( node_map,
564 0 : &child->slot,
565 0 : fd_ghost_node_pool_idx_null( node_pool ),
566 0 : node_pool );
567 0 : #if FD_GHOST_USE_HANDHOLDING
568 0 : if( FD_UNLIKELY( tail->next == fd_ghost_node_pool_idx_null( node_pool ) ) ) {
569 0 : FD_LOG_ERR(( "Failed to remove child. Child must exist given the while condition. "
570 0 : "Possible memory corruption or data race." ));
571 0 : }
572 0 : #endif
573 0 : tail = fd_ghost_node_pool_ele( node_pool, tail->next );
574 0 : tail->next = fd_ghost_node_pool_idx_null( node_pool );
575 0 : }
576 :
577 0 : child = fd_ghost_node_pool_ele( node_pool, child->sibling_idx );
578 0 : }
579 :
580 : /* Free the head, and move the head pointer forward. */
581 :
582 0 : fd_ghost_node_t * next = fd_ghost_node_pool_ele( node_pool, head->next );
583 0 : fd_ghost_node_pool_ele_release( node_pool, head );
584 0 : head = next;
585 0 : }
586 :
587 : /* Unlink the root and set the new root. */
588 :
589 0 : root->parent_idx = null_idx;
590 0 : ghost->root_idx = fd_ghost_node_map_idx_query( node_map, &slot, null_idx, node_pool );
591 :
592 0 : return root;
593 0 : }
594 :
595 : fd_ghost_node_t const *
596 0 : fd_ghost_gca( fd_ghost_t const * ghost, ulong slot1, ulong slot2 ) {
597 0 : fd_ghost_node_t const * node_pool = fd_ghost_node_pool_const( ghost );
598 0 : fd_ghost_node_t const * node1 = fd_ghost_query( ghost, slot1 );
599 0 : fd_ghost_node_t const * node2 = fd_ghost_query( ghost, slot2 );
600 :
601 0 : #if FD_GHOST_USE_HANDHOLDING
602 0 : if( FD_UNLIKELY( !node1 ) ) {
603 0 : FD_LOG_WARNING(( "slot1 %lu is missing from ghost", slot1 ));
604 0 : return NULL;
605 0 : }
606 :
607 0 : if( FD_UNLIKELY( !node2 ) ) {
608 0 : FD_LOG_WARNING(( "slot2 %lu is missing from ghost", slot2 ));
609 0 : return NULL;
610 0 : }
611 0 : #endif
612 :
613 : /* Find the greatest common ancestor. */
614 :
615 0 : while( node1 && node2 ) {
616 0 : if( FD_UNLIKELY( node1->slot == node2->slot ) ) return node1;
617 0 : if( node1->slot > node2->slot ) {
618 0 : node1 = fd_ghost_node_pool_ele_const( node_pool, node1->parent_idx );
619 0 : } else {
620 0 : node2 = fd_ghost_node_pool_ele_const( node_pool, node2->parent_idx );
621 0 : }
622 0 : }
623 :
624 0 : FD_LOG_ERR(( "Unable to find GCA. Is this a valid ghost?" ));
625 0 : }
626 :
627 : int
628 0 : fd_ghost_is_ancestor( fd_ghost_t const * ghost, ulong ancestor, ulong slot ) {
629 0 : fd_ghost_node_t const * root = fd_ghost_root( ghost );
630 0 : fd_ghost_node_t const * curr = fd_ghost_query( ghost, slot );
631 :
632 0 : #if FD_GHOST_USE_HANDHOLDING
633 0 : if( FD_UNLIKELY( ancestor < root->slot ) ) {
634 0 : FD_LOG_WARNING(( "[%s] ancestor %lu too old. root %lu.", __func__, ancestor, root->slot ));
635 0 : return 0;
636 0 : }
637 :
638 0 : if( FD_UNLIKELY( !curr ) ) {
639 0 : FD_LOG_WARNING(( "[%s] slot %lu not in ghost.", __func__, slot ));
640 0 : return 0;
641 0 : }
642 0 : #endif
643 :
644 : /* Look for `ancestor` in the fork ancestry.
645 :
646 : Stop looking when there is either no ancestry remaining or there is
647 : no reason to look further because we've searched past the
648 : `ancestor`. */
649 :
650 0 : while( FD_LIKELY( curr && curr->slot >= ancestor ) ) {
651 0 : if( FD_UNLIKELY( curr->slot == ancestor ) ) return 1; /* optimize for depth > 1 */
652 0 : curr = fd_ghost_node_pool_ele_const( fd_ghost_node_pool_const( ghost ), curr->parent_idx );
653 0 : }
654 0 : return 0; /* not found */
655 0 : }
656 :
657 : #include <stdio.h>
658 :
659 : static void
660 0 : print( fd_ghost_t const * ghost, fd_ghost_node_t const * node, int space, const char * prefix, ulong total ) {
661 0 : fd_ghost_node_t const * node_pool = fd_ghost_node_pool_const( ghost );
662 :
663 0 : if( node == NULL ) return;
664 :
665 0 : if( space > 0 ) printf( "\n" );
666 0 : for( int i = 0; i < space; i++ )
667 0 : printf( " " );
668 0 : if( FD_UNLIKELY( node->weight > 100 ) ) {
669 0 : }
670 0 : if( FD_UNLIKELY( total == 0 ) ) {
671 0 : printf( "%s%lu (%lu)", prefix, node->slot, node->weight );
672 0 : } else {
673 0 : double pct = ( (double)node->weight / (double)total ) * 100;
674 0 : if( FD_UNLIKELY( pct < 0.99 )) {
675 0 : printf( "%s%lu (%.0lf%%, %lu)", prefix, node->slot, pct, node->weight );
676 0 : } else {
677 0 : printf( "%s%lu (%.0lf%%)", prefix, node->slot, pct );
678 0 : }
679 0 : }
680 :
681 0 : fd_ghost_node_t const * curr = fd_ghost_node_pool_ele_const( node_pool, node->child_idx );
682 0 : char new_prefix[1024]; /* FIXME size this correctly */
683 0 : while( curr ) {
684 0 : if( fd_ghost_node_pool_ele_const( node_pool, curr->sibling_idx ) ) {
685 0 : sprintf( new_prefix, "├── " ); /* branch indicating more siblings follow */
686 0 : print( ghost, curr, space + 4, new_prefix, total );
687 0 : } else {
688 0 : sprintf( new_prefix, "└── " ); /* end branch */
689 0 : print( ghost, curr, space + 4, new_prefix, total );
690 0 : }
691 0 : curr = fd_ghost_node_pool_ele_const( node_pool, curr->sibling_idx );
692 0 : }
693 0 : }
694 :
695 : void
696 0 : fd_ghost_print( fd_ghost_t const * ghost, fd_epoch_t const * epoch, fd_ghost_node_t const * node ) {
697 0 : FD_LOG_NOTICE( ( "\n\n[Ghost]" ) );
698 0 : print( ghost, node, 0, "", epoch->total_stake );
699 0 : printf( "\n\n" );
700 0 : }
|
