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 : /* Return early if the vote slot <= the voter's last tower vote. It is
363 : important that the vote slots are monotonically increasing, because
364 : the order we receive blocks is non-deterministic (due to network
365 : propagation variance), so we may process forks in a different order
366 : from the sender of this vote.
367 :
368 : For example, if a validator votes on A then switches to B, we might
369 : instead process B then A. In this case, the validator's tower on B
370 : would contain a strictly higher vote slot than A (due to lockout),
371 : so we would observe while processing A, that the vote slot < the
372 : last vote slot we have saved for that validator. */
373 :
374 0 : if( FD_UNLIKELY( vote != FD_SLOT_NULL && slot <= vote ) ) return;
375 :
376 : /* LMD-rule: subtract the voter's stake from previous vote. */
377 :
378 0 : if( FD_LIKELY( vote != FD_SLOT_NULL && vote >= root->slot ) ) {
379 0 : FD_LOG_DEBUG(( "[%s] removing (%s, %lu, %lu)", __func__, FD_BASE58_ENC_32_ALLOCA( &voter->key ), voter->stake, vote ));
380 :
381 0 : fd_ghost_node_t * node = fd_ghost_node_map_ele_query( node_map, &vote, NULL, node_pool );
382 0 : #if FD_GHOST_USE_HANDHOLDING
383 0 : if( FD_UNLIKELY( !node ) ) FD_LOG_ERR(( "missing ghost node" )); /* slot must be in ghost. */
384 0 : #endif
385 :
386 0 : #if FD_GHOST_USE_HANDHOLDING
387 0 : int cf = __builtin_usubl_overflow( node->replay_stake, voter->stake, &node->replay_stake );
388 0 : if( FD_UNLIKELY( cf ) ) FD_LOG_ERR(( "[%s] sub overflow. node stake %lu voter stake %lu", __func__, node->replay_stake, voter->stake ));
389 : #else
390 : node->replay_stake -= voter->stake;
391 : #endif
392 :
393 0 : fd_ghost_node_t * ancestor = node;
394 0 : while( ancestor ) {
395 0 : cf = __builtin_usubl_overflow( ancestor->weight, voter->stake, &ancestor->weight );
396 0 : #if FD_GHOST_USE_HANDHOLDING
397 0 : if( FD_UNLIKELY( cf ) ) FD_LOG_ERR(( "[%s] sub overflow. ancestor->weight %lu latest_vote->stake %lu", __func__, ancestor->weight, voter->stake ));
398 : #else
399 : ancestor_weight -= voter->stake;
400 : #endif
401 0 : ancestor = fd_ghost_node_pool_ele( node_pool, ancestor->parent_idx );
402 0 : }
403 0 : }
404 :
405 : /* Add voter's stake to the ghost node keyed by `slot`. Propagate the
406 : vote stake up the ancestry. */
407 :
408 0 : FD_LOG_DEBUG(( "[%s] adding (%s, %lu, %lu)", __func__, FD_BASE58_ENC_32_ALLOCA( &voter->key ), voter->stake, slot ));
409 :
410 0 : fd_ghost_node_t * node = fd_ghost_node_map_ele_query( node_map, &slot, NULL, node_pool );
411 0 : #if FD_GHOST_USE_HANDHOLDING
412 0 : if( FD_UNLIKELY( !node ) ) FD_LOG_ERR(( "missing ghost node" )); /* slot must be in ghost. */
413 0 : #endif
414 :
415 0 : #if FD_GHOST_USE_HANDHOLDING
416 0 : int cf = __builtin_uaddl_overflow( node->replay_stake, voter->stake, &node->replay_stake );
417 0 : if( FD_UNLIKELY( cf ) ) FD_LOG_ERR(( "[%s] add overflow. node->stake %lu latest_vote->stake %lu", __func__, node->replay_stake, voter->stake ));
418 : #else
419 : node->replay_stake += voter->stake;
420 : #endif
421 :
422 0 : fd_ghost_node_t * ancestor = node;
423 0 : while( ancestor ) {
424 0 : #if FD_GHOST_USE_HANDHOLDING
425 0 : int cf = __builtin_uaddl_overflow( ancestor->weight, voter->stake, &ancestor->weight );
426 0 : if( FD_UNLIKELY( cf ) ) FD_LOG_ERR(( "[%s] add overflow. ancestor->weight %lu latest_vote->stake %lu", __func__, ancestor->weight, voter->stake ));
427 : #else
428 : ancestor_weight += voter->stake;
429 : #endif
430 0 : ancestor = fd_ghost_node_pool_ele( node_pool, ancestor->parent_idx );
431 0 : }
432 :
433 0 : voter->replay_vote = slot; /* update the cached replay vote slot on voter */
434 0 : }
435 :
436 : void
437 : fd_ghost_gossip_vote( FD_PARAM_UNUSED fd_ghost_t * ghost,
438 : FD_PARAM_UNUSED fd_voter_t * voter,
439 0 : FD_PARAM_UNUSED ulong slot ) {
440 0 : FD_LOG_ERR(( "unimplemented" ));
441 0 : }
442 :
443 : void
444 0 : fd_ghost_rooted_vote( fd_ghost_t * ghost, fd_voter_t * voter, ulong root ) {
445 0 : VER_INC;
446 :
447 0 : FD_LOG_DEBUG(( "[%s] root %lu, pubkey %s, stake %lu", __func__, root, FD_BASE58_ENC_32_ALLOCA(&voter->key), voter->stake ));
448 :
449 0 : fd_ghost_node_map_t * node_map = fd_ghost_node_map( ghost );
450 0 : fd_ghost_node_t * node_pool = fd_ghost_node_pool( ghost );
451 0 : fd_ghost_node_t const * root_node = fd_ghost_root( ghost );
452 :
453 0 : #if FD_GHOST_USE_HANDHOLDING
454 0 : if( FD_UNLIKELY( root < root_node->slot ) ) {
455 0 : FD_LOG_ERR(( "caller must only insert vote slots >= ghost root. vote: %lu, root: %lu", root, root_node->slot ));
456 0 : }
457 0 : #endif
458 :
459 : /* It is invariant that the voter's root is found in ghost (as long as
460 : voter's root >= our root ). This is because voter's root is sourced
461 : from their vote state, so it must be on the fork we're replaying
462 : and we must have already inserted their root slot into ghost. */
463 :
464 0 : fd_ghost_node_t * node = fd_ghost_node_map_ele_query( node_map, &root, NULL, node_pool );
465 0 : #if FD_GHOST_USE_HANDHOLDING
466 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 ));
467 0 : #endif
468 :
469 : /* Add to the rooted stake. */
470 :
471 0 : node->rooted_stake += voter->stake;
472 0 : }
473 :
474 : fd_ghost_node_t const *
475 0 : fd_ghost_publish( fd_ghost_t * ghost, ulong slot ) {
476 0 : FD_LOG_NOTICE(( "[%s] slot %lu", __func__, slot ));
477 0 : VER_INC;
478 :
479 0 : fd_ghost_node_map_t * node_map = fd_ghost_node_map( ghost );
480 0 : fd_ghost_node_t * node_pool = fd_ghost_node_pool( ghost );
481 0 : fd_ghost_node_t const * root_node = fd_ghost_root( ghost );
482 0 : ulong null_idx = fd_ghost_node_pool_idx_null( node_pool );
483 :
484 0 : #if FD_GHOST_USE_HANDHOLDING
485 0 : if( FD_UNLIKELY( slot < root_node->slot ) ) {
486 0 : FD_LOG_WARNING(( "[fd_ghost_publish] trying to publish slot %lu older than ghost->root %lu.",
487 0 : slot,
488 0 : root_node->slot ));
489 0 : return NULL;
490 0 : }
491 0 : if( FD_UNLIKELY( slot == root_node->slot ) ) {
492 0 : FD_LOG_WARNING(( "[fd_ghost_publish] publishing same slot %lu as ghost->root %lu.",
493 0 : slot,
494 0 : root_node->slot ));
495 0 : return NULL;
496 0 : }
497 0 : #endif
498 :
499 : // new root
500 0 : fd_ghost_node_t * root = fd_ghost_node_map_ele_query( node_map,
501 0 : &slot,
502 0 : NULL,
503 0 : node_pool );
504 :
505 0 : #if FD_GHOST_USE_HANDHOLDING
506 0 : if( FD_UNLIKELY( !root ) ) {
507 0 : FD_LOG_ERR(( "[fd_ghost_publish] publish slot %lu not found in ghost", slot ));
508 0 : }
509 :
510 0 : #endif
511 :
512 : /* First, remove the previous root, and add it to the prune list.
513 :
514 : In this context, head is the list head (not to be confused with the
515 : ghost head.) */
516 :
517 0 : fd_ghost_node_t * head = fd_ghost_node_map_ele_remove( node_map,
518 0 : &root_node->slot,
519 0 : NULL,
520 0 : node_pool );
521 0 : head->next = fd_ghost_node_pool_idx_null( node_pool );
522 0 : fd_ghost_node_t * tail = head;
523 :
524 : /* Second, BFS down the tree, adding nodes to the prune queue except
525 : for the new root.
526 :
527 : Loop invariant: the old root must be in new root's ancestry. */
528 :
529 0 : while( head ) {
530 0 : fd_ghost_node_t * child = fd_ghost_node_pool_ele( node_pool, head->child_idx );
531 :
532 0 : while( FD_LIKELY( child ) ) {
533 :
534 : /* Do not prune the new root. */
535 :
536 0 : if( FD_LIKELY( child != root ) ) {
537 :
538 : /* Remove the child from the map and push the child onto the list. */
539 :
540 0 : tail->next = fd_ghost_node_map_idx_remove( node_map,
541 0 : &child->slot,
542 0 : fd_ghost_node_pool_idx_null( node_pool ),
543 0 : node_pool );
544 0 : #if FD_GHOST_USE_HANDHOLDING
545 0 : if( FD_UNLIKELY( tail->next == fd_ghost_node_pool_idx_null( node_pool ) ) ) {
546 0 : FD_LOG_ERR(( "Failed to remove child. Child must exist given the while condition. "
547 0 : "Possible memory corruption or data race." ));
548 0 : }
549 0 : #endif
550 0 : tail = fd_ghost_node_pool_ele( node_pool, tail->next );
551 0 : tail->next = fd_ghost_node_pool_idx_null( node_pool );
552 0 : }
553 :
554 0 : child = fd_ghost_node_pool_ele( node_pool, child->sibling_idx );
555 0 : }
556 :
557 : /* Free the head, and move the head pointer forward. */
558 :
559 0 : fd_ghost_node_t * next = fd_ghost_node_pool_ele( node_pool, head->next );
560 0 : fd_ghost_node_pool_ele_release( node_pool, head );
561 0 : head = next;
562 0 : }
563 :
564 : /* Unlink the root and set the new root. */
565 :
566 0 : root->parent_idx = null_idx;
567 0 : ghost->root_idx = fd_ghost_node_map_idx_query( node_map, &slot, null_idx, node_pool );
568 :
569 0 : return root;
570 0 : }
571 :
572 : fd_ghost_node_t const *
573 0 : fd_ghost_gca( fd_ghost_t const * ghost, ulong slot1, ulong slot2 ) {
574 0 : fd_ghost_node_t const * node_pool = fd_ghost_node_pool_const( ghost );
575 0 : fd_ghost_node_t const * node1 = fd_ghost_query( ghost, slot1 );
576 0 : fd_ghost_node_t const * node2 = fd_ghost_query( ghost, slot2 );
577 :
578 0 : #if FD_GHOST_USE_HANDHOLDING
579 0 : if( FD_UNLIKELY( !node1 ) ) {
580 0 : FD_LOG_WARNING(( "slot1 %lu is missing from ghost", slot1 ));
581 0 : return NULL;
582 0 : }
583 :
584 0 : if( FD_UNLIKELY( !node2 ) ) {
585 0 : FD_LOG_WARNING(( "slot2 %lu is missing from ghost", slot2 ));
586 0 : return NULL;
587 0 : }
588 0 : #endif
589 :
590 : /* Find the greatest common ancestor. */
591 :
592 0 : while( node1 && node2 ) {
593 0 : if( FD_UNLIKELY( node1->slot == node2->slot ) ) return node1;
594 0 : if( node1->slot > node2->slot ) {
595 0 : node1 = fd_ghost_node_pool_ele_const( node_pool, node1->parent_idx );
596 0 : } else {
597 0 : node2 = fd_ghost_node_pool_ele_const( node_pool, node2->parent_idx );
598 0 : }
599 0 : }
600 :
601 0 : FD_LOG_ERR(( "Unable to find GCA. Is this a valid ghost?" ));
602 0 : }
603 :
604 : int
605 0 : fd_ghost_is_ancestor( fd_ghost_t const * ghost, ulong ancestor, ulong slot ) {
606 0 : fd_ghost_node_t const * root = fd_ghost_root( ghost );
607 0 : fd_ghost_node_t const * curr = fd_ghost_query( ghost, slot );
608 :
609 0 : #if FD_GHOST_USE_HANDHOLDING
610 0 : if( FD_UNLIKELY( ancestor < root->slot ) ) {
611 0 : FD_LOG_WARNING(( "[%s] ancestor %lu too old. root %lu.", __func__, ancestor, root->slot ));
612 0 : return 0;
613 0 : }
614 :
615 0 : if( FD_UNLIKELY( !curr ) ) {
616 0 : FD_LOG_WARNING(( "[%s] slot %lu not in ghost.", __func__, slot ));
617 0 : return 0;
618 0 : }
619 0 : #endif
620 :
621 : /* Look for `ancestor` in the fork ancestry.
622 :
623 : Stop looking when there is either no ancestry remaining or there is
624 : no reason to look further because we've searched past the
625 : `ancestor`. */
626 :
627 0 : while( FD_LIKELY( curr && curr->slot >= ancestor ) ) {
628 0 : if( FD_UNLIKELY( curr->slot == ancestor ) ) return 1; /* optimize for depth > 1 */
629 0 : curr = fd_ghost_node_pool_ele_const( fd_ghost_node_pool_const( ghost ), curr->parent_idx );
630 0 : }
631 0 : return 0; /* not found */
632 0 : }
633 :
634 : #include <stdio.h>
635 :
636 : static void
637 0 : print( fd_ghost_t const * ghost, fd_ghost_node_t const * node, int space, const char * prefix, ulong total ) {
638 0 : fd_ghost_node_t const * node_pool = fd_ghost_node_pool_const( ghost );
639 :
640 0 : if( node == NULL ) return;
641 :
642 0 : if( space > 0 ) printf( "\n" );
643 0 : for( int i = 0; i < space; i++ )
644 0 : printf( " " );
645 0 : if( FD_UNLIKELY( node->weight > 100 ) ) {
646 0 : }
647 0 : if( FD_UNLIKELY( total == 0 ) ) {
648 0 : printf( "%s%lu (%lu)", prefix, node->slot, node->weight );
649 0 : } else {
650 0 : double pct = ( (double)node->weight / (double)total ) * 100;
651 0 : if( FD_UNLIKELY( pct < 0.99 )) {
652 0 : printf( "%s%lu (%.0lf%%, %lu)", prefix, node->slot, pct, node->weight );
653 0 : } else {
654 0 : printf( "%s%lu (%.0lf%%)", prefix, node->slot, pct );
655 0 : }
656 0 : }
657 :
658 0 : fd_ghost_node_t const * curr = fd_ghost_node_pool_ele_const( node_pool, node->child_idx );
659 0 : char new_prefix[1024]; /* FIXME size this correctly */
660 0 : while( curr ) {
661 0 : if( fd_ghost_node_pool_ele_const( node_pool, curr->sibling_idx ) ) {
662 0 : sprintf( new_prefix, "├── " ); /* branch indicating more siblings follow */
663 0 : print( ghost, curr, space + 4, new_prefix, total );
664 0 : } else {
665 0 : sprintf( new_prefix, "└── " ); /* end branch */
666 0 : print( ghost, curr, space + 4, new_prefix, total );
667 0 : }
668 0 : curr = fd_ghost_node_pool_ele_const( node_pool, curr->sibling_idx );
669 0 : }
670 0 : }
671 :
672 : void
673 0 : fd_ghost_print( fd_ghost_t const * ghost, fd_epoch_t const * epoch, fd_ghost_node_t const * node ) {
674 0 : FD_LOG_NOTICE( ( "\n\n[Ghost]" ) );
675 0 : print( ghost, node, 0, "", epoch->total_stake );
676 0 : printf( "\n\n" );
677 0 : }
|
