Line data Source code
1 : #include "fd_ghost.h"
2 :
3 : #define LOGGING 0
4 :
5 : void *
6 57 : fd_ghost_new( void * shmem, ulong ele_max, ulong seed ) {
7 :
8 57 : if( FD_UNLIKELY( !shmem ) ) {
9 0 : FD_LOG_WARNING(( "NULL mem" ));
10 0 : return NULL;
11 0 : }
12 :
13 57 : if( FD_UNLIKELY( !fd_ulong_is_aligned( (ulong)shmem, fd_ghost_align() ) ) ) {
14 0 : FD_LOG_WARNING(( "misaligned mem" ));
15 0 : return NULL;
16 0 : }
17 :
18 57 : ulong footprint = fd_ghost_footprint( ele_max );
19 57 : if( FD_UNLIKELY( !footprint ) ) {
20 0 : FD_LOG_WARNING(( "bad ele_max (%lu)", ele_max ));
21 0 : return NULL;
22 0 : }
23 :
24 57 : fd_wksp_t * wksp = fd_wksp_containing( shmem );
25 57 : if( FD_UNLIKELY( !wksp ) ) {
26 0 : FD_LOG_WARNING(( "shmem must be part of a workspace" ));
27 0 : return NULL;
28 0 : }
29 :
30 57 : fd_memset( shmem, 0, footprint );
31 :
32 57 : int elg_max = fd_ulong_find_msb( fd_ulong_pow2_up( ele_max ) );
33 :
34 57 : FD_SCRATCH_ALLOC_INIT( l, shmem );
35 57 : fd_ghost_t * ghost = FD_SCRATCH_ALLOC_APPEND( l, fd_ghost_align(), sizeof( fd_ghost_t ) );
36 57 : void * pool = FD_SCRATCH_ALLOC_APPEND( l, fd_ghost_pool_align(), fd_ghost_pool_footprint ( ele_max ) );
37 57 : void * hash = FD_SCRATCH_ALLOC_APPEND( l, fd_ghost_hash_map_align(), fd_ghost_hash_map_footprint( ele_max ) );
38 57 : void * slot = FD_SCRATCH_ALLOC_APPEND( l, fd_ghost_slot_map_align(), fd_ghost_slot_map_footprint( ele_max ) );
39 57 : void * dup = FD_SCRATCH_ALLOC_APPEND( l, fd_dup_seen_map_align(), fd_dup_seen_map_footprint ( elg_max ) );
40 57 : FD_TEST( FD_SCRATCH_ALLOC_FINI( l, fd_ghost_align() ) == (ulong)shmem + footprint );
41 :
42 57 : ghost->pool_gaddr = fd_wksp_gaddr_fast( wksp, fd_ghost_pool_join ( fd_ghost_pool_new ( pool, ele_max ) ) );
43 57 : ghost->hash_map_gaddr = fd_wksp_gaddr_fast( wksp, fd_ghost_hash_map_join( fd_ghost_hash_map_new( hash, ele_max, seed ) ) );
44 57 : ghost->slot_map_gaddr = fd_wksp_gaddr_fast( wksp, fd_ghost_slot_map_join( fd_ghost_slot_map_new( slot, ele_max, seed ) ) );
45 57 : ghost->dup_map_gaddr = fd_wksp_gaddr_fast( wksp, fd_dup_seen_map_join ( fd_dup_seen_map_new ( dup, elg_max ) ) );
46 :
47 57 : ghost->ghost_gaddr = fd_wksp_gaddr_fast( wksp, ghost );
48 57 : ghost->seed = seed;
49 57 : ghost->root = fd_ghost_pool_idx_null( fd_ghost_pool( ghost ) );
50 :
51 57 : FD_COMPILER_MFENCE();
52 57 : FD_VOLATILE( ghost->magic ) = FD_GHOST_MAGIC;
53 57 : FD_COMPILER_MFENCE();
54 :
55 57 : return shmem;
56 57 : }
57 :
58 : fd_ghost_t *
59 57 : fd_ghost_join( void * shghost ) {
60 57 : fd_ghost_t * ghost = (fd_ghost_t *)shghost;
61 :
62 57 : if( FD_UNLIKELY( !ghost ) ) {
63 0 : FD_LOG_WARNING(( "NULL ghost" ));
64 0 : return NULL;
65 0 : }
66 :
67 57 : 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 57 : fd_wksp_t * wksp = fd_wksp_containing( ghost );
73 57 : if( FD_UNLIKELY( !wksp ) ) {
74 0 : FD_LOG_WARNING(( "ghost must be part of a workspace" ));
75 0 : return NULL;
76 0 : }
77 :
78 57 : if( FD_UNLIKELY( ghost->magic!=FD_GHOST_MAGIC ) ) {
79 0 : FD_LOG_WARNING(( "bad magic" ));
80 0 : return NULL;
81 0 : }
82 :
83 57 : return ghost;
84 57 : }
85 :
86 : void *
87 6 : fd_ghost_leave( fd_ghost_t const * ghost ) {
88 :
89 6 : if( FD_UNLIKELY( !ghost ) ) {
90 0 : FD_LOG_WARNING(( "NULL ghost" ));
91 0 : return NULL;
92 0 : }
93 :
94 6 : return (void *)ghost;
95 6 : }
96 :
97 : void *
98 6 : fd_ghost_delete( void * ghost ) {
99 :
100 6 : if( FD_UNLIKELY( !ghost ) ) {
101 0 : FD_LOG_WARNING(( "NULL ghost" ));
102 0 : return NULL;
103 0 : }
104 :
105 6 : 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 6 : return ghost;
111 6 : }
112 :
113 : /* Inserts element into the hash-keyed map. If there isn't already a
114 : block executed for the same slot, insert into the slot-keyed map. */
115 : static void
116 339 : maps_insert( fd_ghost_t * ghost, fd_ghost_ele_t * ele ) {
117 339 : fd_ghost_hash_map_t * maph = fd_ghost_hash_map( ghost );
118 339 : fd_ghost_slot_map_t * maps = fd_ghost_slot_map( ghost );
119 339 : fd_ghost_ele_t * pool = fd_ghost_pool( ghost );
120 339 : ulong null = fd_ghost_pool_idx_null( pool );
121 :
122 339 : fd_ghost_hash_map_ele_insert( maph, ele, pool );
123 339 : fd_ghost_ele_t * ele_slot = fd_ghost_slot_map_ele_query( maps, &ele->slot, NULL, pool );
124 339 : if( FD_LIKELY( !ele_slot ) ) {
125 321 : fd_ghost_slot_map_ele_insert( maps, ele, pool ); /* cannot fail */
126 321 : } else {
127 : /* If the slot is already in the map, then we have a duplicate */
128 21 : while( FD_UNLIKELY( ele_slot->eqvoc != null ) ) {
129 3 : ele_slot = fd_ghost_pool_ele( pool, ele_slot->eqvoc );
130 3 : }
131 18 : ele_slot->eqvoc = fd_ghost_pool_idx( pool, ele );
132 18 : }
133 339 : }
134 :
135 : /* Removes all occurrences of `hash` from the maps. */
136 : static fd_ghost_ele_t *
137 63 : maps_remove( fd_ghost_t * ghost, fd_hash_t * hash ) {
138 63 : fd_ghost_hash_map_t * maph = fd_ghost_hash_map( ghost );
139 63 : fd_ghost_slot_map_t * maps = fd_ghost_slot_map( ghost );
140 63 : fd_ghost_ele_t * pool = fd_ghost_pool( ghost );
141 :
142 63 : fd_ghost_ele_t * ele = fd_ghost_hash_map_ele_remove( maph, hash, NULL, pool );
143 63 : if( FD_LIKELY( ele ) ) {
144 63 : fd_ghost_ele_t * eles = fd_ghost_slot_map_ele_query( maps, &ele->slot, NULL, pool );
145 63 : if( FD_LIKELY( eles && memcmp( &ele->key, hash, sizeof(fd_hash_t) ) == 0 ) ) {
146 63 : fd_ghost_slot_map_ele_remove( maps, &ele->slot, NULL, pool );
147 63 : }
148 63 : }
149 63 : return ele;
150 63 : }
151 :
152 : void
153 57 : fd_ghost_init( fd_ghost_t * ghost, ulong root_slot, fd_hash_t * hash ) {
154 :
155 57 : if( FD_UNLIKELY( !ghost ) ) {
156 0 : FD_LOG_WARNING(( "NULL ghost" ));
157 0 : return;
158 0 : }
159 :
160 57 : if( FD_UNLIKELY( root_slot == FD_SLOT_NULL ) ) {
161 0 : FD_LOG_WARNING(( "NULL root" ));
162 0 : return;
163 0 : }
164 :
165 57 : fd_ghost_ele_t * pool = fd_ghost_pool( ghost );
166 57 : ulong null = fd_ghost_pool_idx_null( pool );
167 :
168 57 : if( FD_UNLIKELY( ghost->root != null ) ) {
169 0 : FD_LOG_WARNING(( "ghost already initialized" ));
170 0 : return;
171 0 : }
172 :
173 : /* Initialize the root ele from a pool element. */
174 :
175 57 : fd_ghost_ele_t * root = fd_ghost_pool_ele_acquire( pool );
176 57 : root->key = *hash;
177 57 : root->slot = root_slot;
178 57 : root->next = null;
179 57 : root->nexts = null;
180 57 : root->eqvoc = null;
181 57 : root->parent = null;
182 57 : root->child = null;
183 57 : root->sibling = null;
184 57 : root->weight = 0;
185 57 : root->replay_stake = 0;
186 57 : root->gossip_stake = 0;
187 57 : root->rooted_stake = 0;
188 57 : root->valid = 1;
189 :
190 : /* Insert the root and record the root ele's pool idx. */
191 :
192 57 : maps_insert( ghost, root ); /* cannot fail */
193 57 : ghost->root = fd_ghost_pool_idx( pool, root );
194 :
195 : /* Sanity checks. */
196 :
197 57 : FD_TEST( fd_ghost_root( ghost ) );
198 57 : FD_TEST( fd_ghost_root( ghost ) == fd_ghost_query( ghost, hash ) );
199 57 : FD_TEST( fd_ghost_root( ghost )->slot == root_slot );
200 :
201 57 : return;
202 57 : }
203 :
204 : int
205 102 : fd_ghost_verify( fd_ghost_t const * ghost ) {
206 102 : if( FD_UNLIKELY( !ghost ) ) {
207 0 : FD_LOG_WARNING(( "NULL ghost" ));
208 0 : return -1;
209 0 : }
210 :
211 102 : if( FD_UNLIKELY( !fd_ulong_is_aligned( (ulong)ghost, fd_ghost_align() ) ) ) {
212 0 : FD_LOG_WARNING(( "misaligned ghost" ));
213 0 : return -1;
214 0 : }
215 :
216 102 : fd_wksp_t * wksp = fd_wksp_containing( ghost );
217 102 : if( FD_UNLIKELY( !wksp ) ) {
218 0 : FD_LOG_WARNING(( "ghost must be part of a workspace" ));
219 0 : return -1;
220 0 : }
221 :
222 102 : if( FD_UNLIKELY( ghost->magic!=FD_GHOST_MAGIC ) ) {
223 0 : FD_LOG_WARNING(( "bad magic" ));
224 0 : return -1;
225 0 : }
226 :
227 102 : fd_ghost_ele_t const * pool = fd_ghost_pool_const( ghost );
228 102 : ulong null = fd_ghost_pool_idx_null( pool );
229 102 : fd_ghost_hash_map_t const * maph = fd_ghost_hash_map_const( ghost );
230 :
231 : /* Check every ele that exists in pool exists in map. */
232 :
233 102 : if( fd_ghost_hash_map_verify( maph, fd_ghost_pool_max( pool ), pool ) ) return -1;
234 :
235 : /* Check every ele's weight is >= sum of children's weights. */
236 :
237 102 : fd_ghost_ele_t const * parent = fd_ghost_root_const( ghost );
238 207 : while( FD_LIKELY( parent ) ) {
239 105 : ulong weight = 0;
240 105 : fd_ghost_ele_t const * child = fd_ghost_child_const( ghost, parent );
241 171 : while( FD_LIKELY( child && child->sibling != null ) ) {
242 66 : weight += child->weight;
243 66 : child = fd_ghost_sibling_const( ghost, child );
244 66 : }
245 105 : # if FD_GHOST_USE_HANDHOLDING
246 105 : FD_TEST( parent->weight >= weight );
247 105 : # endif
248 105 : parent = fd_ghost_pool_ele_const( pool, parent->next );
249 105 : }
250 :
251 102 : return 0;
252 102 : }
253 :
254 : static void
255 45 : fd_ghost_mark_valid( fd_ghost_t * ghost, fd_hash_t const * bid ) {
256 45 : fd_ghost_ele_t * ele = fd_ghost_query( ghost, bid );
257 45 : if( FD_LIKELY( ele ) ) ele->valid = 1;
258 45 : }
259 :
260 : static void
261 18 : fd_ghost_mark_invalid( fd_ghost_t * ghost, ulong slot, ulong total_stake ) {
262 18 : fd_ghost_ele_t * pool = fd_ghost_pool( ghost );
263 18 : ulong null = fd_ghost_pool_idx_null( pool );
264 18 : fd_hash_t const * hash = fd_ghost_hash( ghost, slot );
265 18 : FD_TEST( hash ); /* mark_invalid should never get called on a non-existing slot */
266 :
267 18 : fd_ghost_ele_t * ele = fd_ghost_query( ghost, hash );
268 18 : if( FD_LIKELY( ele && !is_duplicate_confirmed( ghost, &ele->key, total_stake ) ) ) ele->valid = 0;
269 18 : while( FD_UNLIKELY( ele->eqvoc != null ) ) {
270 0 : fd_ghost_ele_t * eqvoc = fd_ghost_pool_ele( pool, ele->eqvoc );
271 0 : if( FD_LIKELY( !is_duplicate_confirmed( ghost, &eqvoc->key, total_stake ) ) ) eqvoc->valid = 0;
272 0 : ele = eqvoc;
273 0 : }
274 18 : }
275 :
276 : fd_ghost_ele_t *
277 282 : fd_ghost_insert( fd_ghost_t * ghost, fd_hash_t const * parent_hash, ulong slot, fd_hash_t const * hash, ulong total_stake ) {
278 : # if LOGGING
279 : FD_LOG_INFO(( "[%s] slot: %lu, %s. parent: %s.", __func__, slot, FD_BASE58_ENC_32_ALLOCA(hash), FD_BASE58_ENC_32_ALLOCA(parent_hash) ));
280 : # endif
281 :
282 282 : # if FD_GHOST_USE_HANDHOLDING
283 282 : FD_TEST( ghost->magic == FD_GHOST_MAGIC );
284 282 : # endif
285 :
286 282 : fd_ghost_ele_t * pool = fd_ghost_pool( ghost );
287 282 : ulong null = fd_ghost_pool_idx_null( pool );
288 282 : fd_ghost_ele_t * parent = fd_ghost_query( ghost, parent_hash );
289 282 : fd_ghost_ele_t const * root = fd_ghost_root( ghost );
290 :
291 282 : # if FD_GHOST_USE_HANDHOLDING
292 282 : if( FD_UNLIKELY( fd_ghost_query( ghost, hash ) ) ) { FD_LOG_WARNING(( "[%s] hash %s already in ghost.", __func__, FD_BASE58_ENC_32_ALLOCA(hash) )); return NULL; }
293 282 : if( FD_UNLIKELY( !parent ) ) { FD_LOG_WARNING(( "[%s] missing `parent_id` %s for (%s, %lu)", __func__, FD_BASE58_ENC_32_ALLOCA(parent_hash), FD_BASE58_ENC_32_ALLOCA(hash), slot )); return NULL; }
294 282 : if( FD_UNLIKELY( !fd_ghost_pool_free( pool ) ) ) { FD_LOG_WARNING(( "[%s] ghost full.", __func__ )); return NULL; }
295 282 : if( FD_UNLIKELY( slot <= root->slot ) ) { FD_LOG_WARNING(( "[%s] slot %lu <= root %lu", __func__, slot, root->slot )); return NULL; }
296 282 : # endif
297 :
298 282 : fd_ghost_ele_t * ele = fd_ghost_pool_ele_acquire( pool );
299 282 : ele->key = *hash;
300 282 : ele->slot = slot;
301 282 : ele->eqvoc = null;
302 282 : ele->next = null;
303 282 : ele->nexts = null;
304 282 : ele->parent = null;
305 282 : ele->child = null;
306 282 : ele->sibling = null;
307 282 : ele->weight = 0;
308 282 : ele->replay_stake = 0;
309 282 : ele->gossip_stake = 0;
310 282 : ele->rooted_stake = 0;
311 282 : ele->valid = 1;
312 282 : ele->parent = fd_ghost_pool_idx( pool, parent );
313 282 : if( FD_LIKELY( parent->child == null ) ) {
314 201 : parent->child = fd_ghost_pool_idx( pool, ele ); /* left-child */
315 201 : } else {
316 81 : fd_ghost_ele_t * curr = fd_ghost_pool_ele( pool, parent->child );
317 81 : while( curr->sibling != null ) curr = fd_ghost_pool_ele( pool, curr->sibling );
318 81 : curr->sibling = fd_ghost_pool_idx( pool, ele ); /* right-sibling */
319 81 : }
320 282 : maps_insert( ghost, ele );
321 :
322 : /* Checks if block has a duplicate message, but the message arrived
323 : before the block was added to ghost. */
324 :
325 282 : if( FD_UNLIKELY( fd_dup_seen_map_query( fd_ghost_dup_map( ghost ), slot, NULL ) ) ) {
326 3 : fd_ghost_mark_invalid( ghost, slot, total_stake );
327 3 : }
328 282 : return ele;
329 282 : }
330 :
331 : fd_ghost_ele_t const *
332 57 : fd_ghost_head( fd_ghost_t const * ghost, fd_ghost_ele_t const * root ) {
333 :
334 57 : # if FD_GHOST_USE_HANDHOLDING
335 57 : FD_TEST( ghost->magic == FD_GHOST_MAGIC );
336 57 : FD_TEST( root );
337 57 : # endif
338 :
339 57 : if( FD_UNLIKELY( !root->valid ) ) return NULL; /* no valid ghost heads */
340 :
341 57 : fd_ghost_ele_t const * pool = fd_ghost_pool_const( ghost );
342 57 : fd_ghost_ele_t const * head = root;
343 57 : ulong null = fd_ghost_pool_idx_null( pool );
344 :
345 174 : while( FD_LIKELY( head->child != null ) ) {
346 132 : int valid_child = 0; /* at least one child is valid */
347 132 : fd_ghost_ele_t const * child = fd_ghost_child_const( ghost, head );
348 291 : while( FD_LIKELY( child ) ) { /* greedily pick the heaviest valid child */
349 159 : if( FD_LIKELY( child->valid ) ) {
350 141 : if( FD_LIKELY( !valid_child ) ) { /* this is the first valid child, so progress the head */
351 117 : head = child;
352 117 : valid_child = 1;
353 117 : }
354 141 : head = fd_ptr_if(
355 141 : fd_int_if(
356 141 : child->weight == head->weight, /* if the weights are equal */
357 141 : child->slot < head->slot, /* then tie-break by lower slot number */
358 141 : child->weight > head->weight ), /* else return heavier */
359 141 : child, head );
360 141 : }
361 159 : child = fd_ghost_sibling_const( ghost, child );
362 159 : }
363 132 : if( FD_UNLIKELY( !valid_child ) ) break; /* no children are valid, so short-circuit traversal */
364 132 : }
365 57 : return head;
366 57 : }
367 :
368 : void
369 168 : fd_ghost_replay_vote( fd_ghost_t * ghost, fd_voter_t * voter, fd_hash_t const * hash ) {
370 168 : fd_ghost_ele_t * pool = fd_ghost_pool( ghost );
371 168 : fd_vote_record_t vote = voter->replay_vote;
372 168 : fd_ghost_ele_t const * root = fd_ghost_root( ghost );
373 168 : fd_ghost_ele_t const * vote_ele = fd_ghost_query_const( ghost, hash );
374 168 : ulong slot = vote_ele->slot;
375 :
376 : # if LOGGING
377 : FD_LOG_INFO(( "[%s] voter: %s slot_hash: (%s, %lu) last: %lu", __func__, FD_BASE58_ENC_32_ALLOCA(&voter->key), FD_BASE58_ENC_32_ALLOCA(hash), slot, vote.slot ));
378 : # endif
379 :
380 : /* Short-circuit if the vote slot is older than the root. */
381 :
382 168 : if( FD_UNLIKELY( slot < root->slot ) ) return;
383 :
384 : /* Short-circuit if the vote is unchanged. It's possible that voter is
385 : switching from A to A', which should be a slashable offense. */
386 :
387 168 : if( FD_UNLIKELY( memcmp( &vote.hash, hash, sizeof(fd_hash_t) ) == 0 ) ) return;
388 :
389 : /* TODO add logic that only the least bank hash is kept if the same
390 : voter votes for the same slot multiple times. */
391 :
392 : /* Short-circuit if this vote slot < the last vote slot we processed
393 : for this voter. The order we replay forks is non-deterministic due
394 : to network propagation variance, so it is possible we are see an
395 : older vote after a newer vote (relative to the slot in which the
396 : vote actually landed).
397 :
398 : For example, 3-4 and 5-6 fork from 2, we might see the vote for 5
399 : in block 6 then the vote for 3 in block 4. We ignore the vote for 3
400 : in block 4 if we already processed the vote for 5 in block 6. */
401 :
402 168 : if( FD_UNLIKELY( vote.slot != FD_SLOT_NULL && slot < vote.slot ) ) return;
403 :
404 : /* LMD-rule: subtract the voter's stake from the ghost ele
405 : corresponding to their previous vote slot. If the voter's previous
406 : vote slot is not in ghost than we have either not processed
407 : this voter previously or their previous vote slot was already
408 : pruned (because we published a new root). */
409 :
410 168 : fd_ghost_ele_t * prev = fd_ghost_query( ghost, &vote.hash );
411 168 : if( FD_LIKELY( prev && vote.slot != FD_SLOT_NULL ) ) { /* no previous vote or pruned */
412 : # if LOGGING
413 : FD_LOG_INFO(( "[%s] subtracting (%s, %lu, %lu, %s)", __func__, FD_BASE58_ENC_32_ALLOCA( &voter->key ), voter->stake, vote.slot, FD_BASE58_ENC_32_ALLOCA( &vote.hash ) ));
414 : # endif
415 27 : int cf = __builtin_usubl_overflow( prev->replay_stake, voter->stake, &prev->replay_stake );
416 27 : if( FD_UNLIKELY( cf ) ) FD_LOG_CRIT(( "[%s] sub overflow. prev->replay_stake %lu voter->stake %lu", __func__, prev->replay_stake, voter->stake ));
417 27 : fd_ghost_ele_t * ancestor = prev;
418 99 : while( FD_LIKELY( ancestor ) ) {
419 72 : cf = __builtin_usubl_overflow( ancestor->weight, voter->stake, &ancestor->weight );
420 72 : if( FD_UNLIKELY( cf ) ) FD_LOG_CRIT(( "[%s] sub overflow. ancestor->weight %lu latest_vote->stake %lu", __func__, ancestor->weight, voter->stake ));
421 72 : ancestor = fd_ghost_pool_ele( pool, ancestor->parent );
422 72 : }
423 27 : }
424 :
425 : /* Add voter's stake to the ghost ele 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, this
428 : vote is switched from a previous vote that was on a missing ele
429 : (pruned), or the regular case */
430 :
431 168 : fd_ghost_ele_t * curr = fd_ghost_query( ghost, hash );
432 168 : if( FD_UNLIKELY( !curr ) ) FD_LOG_CRIT(( "corrupt ghost" ));
433 :
434 : # if LOGGING
435 : FD_LOG_INFO(( "[%s] adding (%s, %lu, %lu)", __func__, FD_BASE58_ENC_32_ALLOCA( &voter->key ), voter->stake, slot ));
436 : # endif
437 168 : int cf = __builtin_uaddl_overflow( curr->replay_stake, voter->stake, &curr->replay_stake );
438 168 : if( FD_UNLIKELY( cf ) ) FD_LOG_ERR(( "[%s] add overflow. ele->stake %lu latest_vote->stake %lu", __func__, curr->replay_stake, voter->stake ));
439 168 : fd_ghost_ele_t * ancestor = curr;
440 708 : while( FD_LIKELY( ancestor ) ) {
441 540 : int cf = __builtin_uaddl_overflow( ancestor->weight, voter->stake, &ancestor->weight );
442 540 : if( FD_UNLIKELY( cf ) ) FD_LOG_ERR(( "[%s] add overflow. ancestor->weight %lu latest_vote->stake %lu", __func__, ancestor->weight, voter->stake ));
443 540 : ancestor = fd_ghost_parent( ghost, ancestor );
444 540 : }
445 168 : voter->replay_vote.slot = slot; /* update the cached replay vote slot on voter */
446 168 : voter->replay_vote.hash = *hash; /* update the cached replay vote hash on voter */
447 168 : }
448 :
449 : void
450 : fd_ghost_gossip_vote( FD_PARAM_UNUSED fd_ghost_t * ghost,
451 : FD_PARAM_UNUSED fd_voter_t * voter,
452 0 : FD_PARAM_UNUSED ulong slot ) {
453 0 : FD_LOG_ERR(( "unimplemented" ));
454 0 : }
455 :
456 : void
457 3 : fd_ghost_rooted_vote( fd_ghost_t * ghost, fd_voter_t * voter, ulong root ) {
458 : # if LOGGING
459 : FD_LOG_INFO(( "[%s] root %lu, pubkey %s, stake %lu", __func__, root, FD_BASE58_ENC_32_ALLOCA(&voter->key), voter->stake ));
460 : # endif
461 :
462 : /* It is invariant that the voter's root is found in ghost (as long as
463 : voter's root >= our root ). This is because voter's root is sourced
464 : from their vote state, so it must be on the fork we're replaying
465 : and we must have already inserted their root slot into ghost. */
466 :
467 3 : fd_ghost_ele_t * ele = fd_ghost_query( ghost, fd_ghost_hash( ghost, root ) );
468 3 : # if FD_GHOST_USE_HANDHOLDING
469 3 : if( FD_UNLIKELY( !ele ) ) FD_LOG_CRIT(( "[%s] missing voter %s's root %lu.", __func__, FD_BASE58_ENC_32_ALLOCA(&voter->key), root ));
470 3 : # endif
471 :
472 : /* Add to the rooted stake. */
473 :
474 3 : ele->rooted_stake += voter->stake;
475 3 : }
476 :
477 : fd_ghost_ele_t const *
478 12 : fd_ghost_publish( fd_ghost_t * ghost, fd_hash_t const * hash ) {
479 12 : fd_ghost_ele_t * pool = fd_ghost_pool( ghost );
480 12 : ulong null = fd_ghost_pool_idx_null( pool );
481 12 : fd_ghost_ele_t * oldr = fd_ghost_root( ghost );
482 12 : fd_ghost_ele_t * newr = fd_ghost_query( ghost, hash );
483 :
484 12 : # if FD_GHOST_USE_HANDHOLDING
485 12 : if( FD_UNLIKELY( !newr ) ) { FD_LOG_WARNING(( "[%s] publish hash %s not found", __func__, FD_BASE58_ENC_32_ALLOCA(hash) )); return NULL; }
486 12 : if( FD_UNLIKELY( newr->slot <= oldr->slot ) ) { FD_LOG_WARNING(( "[%s] publish slot %lu <= root %lu.", __func__, newr->slot, oldr->slot )); return NULL; }
487 12 : if( FD_UNLIKELY( !fd_ghost_is_ancestor( ghost, &oldr->key, &newr->key ) ) ) { FD_LOG_WARNING(( "[%s] publish slot %lu not ancestor %lu.", __func__, newr->slot, oldr->slot )); return NULL; }
488 12 : # endif
489 :
490 : /* First, remove the previous root, and add it to the prune list. In
491 : this context, head is the list head (not to be confused with the
492 : ghost head.) */
493 :
494 12 : fd_ghost_ele_t * head = maps_remove( ghost, &oldr->key );
495 12 : fd_ghost_ele_t * tail = head;
496 :
497 : /* Second, BFS down the tree, pruning all of root's ancestors and also
498 : any descendants of those ancestors. */
499 :
500 12 : head->next = null;
501 75 : while( FD_LIKELY( head ) ) {
502 63 : fd_ghost_ele_t * child = fd_ghost_pool_ele( pool, head->child );
503 126 : while( FD_LIKELY( child ) ) { /* iterate over children */
504 63 : if( FD_LIKELY( child != newr ) ) { /* stop at new root */
505 51 : tail->next = fd_ghost_pool_idx( pool, maps_remove( ghost, &child->key ) ); /* remove ele from map to reuse `.next` */
506 51 : tail = fd_ghost_pool_ele( pool, tail->next ); /* push onto prune queue (so descendants can be pruned) */
507 51 : tail->next = fd_ghost_pool_idx_null( pool );
508 51 : }
509 63 : child = fd_ghost_pool_ele( pool, child->sibling ); /* next sibling */
510 63 : }
511 63 : fd_ghost_ele_t * next = fd_ghost_pool_ele( pool, head->next ); /* pop prune queue head */
512 63 : fd_ghost_pool_ele_release( pool, head ); /* free prune queue head */
513 63 : head = next; /* move prune queue head forward */
514 63 : }
515 12 : newr->parent = null; /* unlink old root*/
516 12 : ghost->root = fd_ghost_pool_idx( pool, newr ); /* replace with new root */
517 12 : return newr;
518 12 : }
519 :
520 : fd_ghost_ele_t const *
521 84 : fd_ghost_gca( fd_ghost_t const * ghost, fd_hash_t const * hash1, fd_hash_t const * hash2 ) {
522 84 : fd_ghost_ele_t const * pool = fd_ghost_pool_const( ghost );
523 84 : fd_ghost_ele_t const * ele1 = fd_ghost_query_const( ghost, hash1 );
524 84 : fd_ghost_ele_t const * ele2 = fd_ghost_query_const( ghost, hash2 );
525 :
526 84 : # if FD_GHOST_USE_HANDHOLDING
527 84 : if( FD_UNLIKELY( !ele1 ) ) { FD_LOG_WARNING(( "hash1 %s missing", FD_BASE58_ENC_32_ALLOCA(hash1) )); return NULL; }
528 84 : if( FD_UNLIKELY( !ele2 ) ) { FD_LOG_WARNING(( "hash2 %s missing", FD_BASE58_ENC_32_ALLOCA(hash2) )); return NULL; }
529 84 : # endif
530 :
531 : /* Find the greatest common ancestor. */
532 :
533 234 : while( FD_LIKELY( ele1 && ele2 ) ) {
534 234 : if( FD_UNLIKELY( memcmp( &ele1->key, &ele2->key, sizeof(fd_hash_t) ) == 0 ) ) return ele1;
535 150 : if( ele1->slot > ele2->slot ) ele1 = fd_ghost_pool_ele_const( pool, ele1->parent );
536 126 : else ele2 = fd_ghost_pool_ele_const( pool, ele2->parent );
537 150 : }
538 0 : FD_LOG_CRIT(( "invariant violation" )); /* unreachable */
539 0 : }
540 :
541 : int
542 12 : fd_ghost_is_ancestor( fd_ghost_t const * ghost, fd_hash_t const * ancestor, fd_hash_t const * hash ) {
543 12 : fd_ghost_ele_t const * root = fd_ghost_root_const ( ghost );
544 12 : fd_ghost_ele_t const * curr = fd_ghost_query_const( ghost, hash );
545 12 : fd_ghost_ele_t const * anc = fd_ghost_query_const( ghost, ancestor );
546 :
547 12 : if( FD_UNLIKELY( !anc ) ) {
548 : # if LOGGING
549 : FD_LOG_NOTICE(( "[%s] ancestor %s missing", __func__, FD_BASE58_ENC_32_ALLOCA(ancestor) ));
550 : # endif
551 0 : return 0;
552 0 : }
553 :
554 12 : # if FD_GHOST_USE_HANDHOLDING
555 12 : if( FD_UNLIKELY( anc->slot < root->slot ) ) { FD_LOG_WARNING(( "[%s] ancestor %lu too old. root %lu.", __func__, anc->slot, root->slot )); return 0; }
556 12 : if( FD_UNLIKELY( !curr ) ) { FD_LOG_WARNING(( "[%s] hash %s not in ghost.", __func__, FD_BASE58_ENC_32_ALLOCA(hash) )); return 0; }
557 12 : # endif
558 :
559 : /* Look for `ancestor` in the fork ancestry.
560 :
561 : Stop looking when there is either no ancestry remaining or there is
562 : no reason to look further because we've searched past the
563 : `ancestor`. */
564 :
565 30 : while( FD_LIKELY( curr && curr->slot >= anc->slot ) ) {
566 30 : if( FD_UNLIKELY( memcmp( &curr->key, &anc->key, sizeof(fd_hash_t) ) == 0 ) ) return 1; /* optimize for depth > 1 */
567 18 : curr = fd_ghost_pool_ele_const( fd_ghost_pool_const( ghost ), curr->parent );
568 18 : }
569 0 : return 0; /* not found */
570 12 : }
571 :
572 : int
573 0 : fd_ghost_invalid( fd_ghost_t const * ghost, fd_ghost_ele_t const * ele ) {
574 0 : fd_ghost_ele_t const * anc = ele;
575 0 : while( FD_LIKELY( anc ) ) {
576 0 : if( FD_UNLIKELY( ( !anc->valid ) ) ) return 1;
577 0 : anc = fd_ghost_parent_const( ghost, anc );
578 0 : }
579 0 : return 0;
580 0 : }
581 :
582 :
583 : void
584 12 : process_duplicate_confirmed( fd_ghost_t * ghost, fd_hash_t const * hash, ulong slot ) {
585 12 : fd_ghost_ele_t const * confirmed = fd_ghost_query( ghost, hash );
586 12 : fd_ghost_ele_t const * current = fd_ghost_query( ghost, fd_ghost_hash( ghost, slot ) );
587 12 : if( FD_UNLIKELY( !confirmed ) ) {
588 0 : FD_LOG_WARNING(( "[%s] duplicate confirmed slot %lu, %s not in ghost. Need to repair & replay. ", __func__, slot, FD_BASE58_ENC_32_ALLOCA(hash) ) );
589 0 : return;
590 0 : }
591 12 : if( FD_UNLIKELY( !current ) ) FD_LOG_ERR(( "[%s] slot %lu doesn't exist in ghost, but we're processing a duplicate confirmed signal for it.", __func__, slot ));
592 :
593 57 : while( current != NULL ) {
594 45 : fd_ghost_mark_valid( ghost, ¤t->key );
595 45 : current = fd_ghost_parent_const( ghost, current );
596 45 : }
597 12 : }
598 :
599 : void
600 18 : process_duplicate( fd_ghost_t * ghost, ulong slot, ulong total_stake ) {
601 18 : fd_dup_seen_t * dup_map = fd_ghost_dup_map( ghost );
602 18 : fd_dup_seen_map_insert( dup_map, slot );
603 :
604 18 : if( fd_ghost_hash( ghost, slot ) ) {
605 : /* slot is already replayed, so we can immediately mark invalid */
606 15 : FD_LOG_WARNING(( "[%s] duplicate message for slot %lu, marking invalid", __func__, slot ));
607 15 : fd_ghost_mark_invalid( ghost, slot, total_stake );
608 15 : return;
609 15 : }
610 18 : }
611 :
612 : #include <stdio.h>
613 :
614 : static void
615 396 : print( fd_ghost_t const * ghost, fd_ghost_ele_t const * ele, int space, const char * prefix, ulong total ) {
616 396 : fd_ghost_ele_t const * pool = fd_ghost_pool_const( ghost );
617 :
618 396 : if( ele == NULL ) return;
619 :
620 396 : if( space > 0 ) printf( "\n" );
621 3156 : for( int i = 0; i < space; i++ )
622 2760 : printf( " " );
623 396 : if( FD_UNLIKELY( ele->weight > 100 ) ) {
624 15 : }
625 396 : if( FD_UNLIKELY( total == 0 ) ) {
626 21 : printf( "%s%lu (%lu)", prefix, ele->slot, ele->weight );
627 375 : } else {
628 375 : double pct = ( (double)ele->weight / (double)total ) * 100;
629 375 : if( FD_UNLIKELY( pct < 0.99 )) {
630 168 : printf( "%s%lu (%.0lf%%, %lu)", prefix, ele->slot, pct, ele->weight );
631 207 : } else {
632 207 : printf( "%s%lu (%.0lf%%)", prefix, ele->slot, pct );
633 207 : }
634 375 : }
635 :
636 396 : fd_ghost_ele_t const * curr = fd_ghost_pool_ele_const( pool, ele->child );
637 396 : char new_prefix[1024]; /* FIXME size this correctly */
638 729 : while( curr ) {
639 333 : if( fd_ghost_pool_ele_const( pool, curr->sibling ) ) {
640 105 : sprintf( new_prefix, "├── " ); /* branch indicating more siblings follow */
641 105 : print( ghost, curr, space + 4, new_prefix, total );
642 228 : } else {
643 228 : sprintf( new_prefix, "└── " ); /* end branch */
644 228 : print( ghost, curr, space + 4, new_prefix, total );
645 228 : }
646 333 : curr = fd_ghost_pool_ele_const( pool, curr->sibling );
647 333 : }
648 396 : }
649 :
650 : void
651 63 : fd_ghost_print( fd_ghost_t const * ghost, ulong total_stake, fd_ghost_ele_t const * ele ) {
652 63 : FD_LOG_NOTICE( ( "\n\n[Ghost]" ) );
653 63 : print( ghost, ele, 0, "", total_stake );
654 : printf( "\n\n" );
655 63 : }
|
