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