Line data Source code
1 : #include "fd_ghost.h"
2 : #include "fd_ghost_private.h"
3 :
4 : #define LOGGING 0
5 :
6 : ulong
7 0 : fd_ghost_align( void ) {
8 0 : return alignof(fd_ghost_t);
9 0 : }
10 :
11 : ulong
12 : fd_ghost_footprint( ulong blk_max,
13 0 : ulong vtr_max ) {
14 0 : int lg_vtr_max = fd_ulong_find_msb( fd_ulong_pow2_up( vtr_max ) ) + 1;
15 0 : return FD_LAYOUT_FINI(
16 0 : FD_LAYOUT_APPEND(
17 0 : FD_LAYOUT_APPEND(
18 0 : FD_LAYOUT_APPEND(
19 0 : FD_LAYOUT_APPEND(
20 0 : FD_LAYOUT_INIT,
21 0 : alignof(fd_ghost_t), sizeof(fd_ghost_t) ),
22 0 : pool_align(), pool_footprint( blk_max ) ),
23 0 : blk_map_align(), blk_map_footprint( blk_max ) ),
24 0 : vtr_map_align(), vtr_map_footprint( lg_vtr_max ) ),
25 0 : fd_ghost_align() );
26 0 : }
27 :
28 : void *
29 : fd_ghost_new( void * shmem,
30 : ulong blk_max,
31 : ulong vtr_max,
32 0 : ulong seed ) {
33 :
34 0 : if( FD_UNLIKELY( !shmem ) ) {
35 0 : FD_LOG_WARNING(( "NULL mem" ));
36 0 : return NULL;
37 0 : }
38 :
39 0 : if( FD_UNLIKELY( !fd_ulong_is_aligned( (ulong)shmem, fd_ghost_align() ) ) ) {
40 0 : FD_LOG_WARNING(( "misaligned mem" ));
41 0 : return NULL;
42 0 : }
43 :
44 0 : ulong footprint = fd_ghost_footprint( blk_max, vtr_max );
45 0 : if( FD_UNLIKELY( !footprint ) ) {
46 0 : FD_LOG_WARNING(( "bad blk_max (%lu)", blk_max ));
47 0 : return NULL;
48 0 : }
49 :
50 0 : fd_wksp_t * wksp = fd_wksp_containing( shmem );
51 0 : if( FD_UNLIKELY( !wksp ) ) {
52 0 : FD_LOG_WARNING(( "shmem must be part of a workspace" ));
53 0 : return NULL;
54 0 : }
55 :
56 0 : fd_memset( shmem, 0, footprint );
57 :
58 0 : int lg_vtr_max = fd_ulong_find_msb( fd_ulong_pow2_up( FD_VOTER_MAX ) ) + 1;
59 :
60 0 : FD_SCRATCH_ALLOC_INIT( l, shmem );
61 0 : fd_ghost_t * ghost = FD_SCRATCH_ALLOC_APPEND( l, alignof(fd_ghost_t), sizeof(fd_ghost_t) );
62 0 : void * pool = FD_SCRATCH_ALLOC_APPEND( l, pool_align(), pool_footprint( blk_max ) );
63 0 : void * map = FD_SCRATCH_ALLOC_APPEND( l, blk_map_align(), blk_map_footprint( blk_max ) );
64 0 : void * vtr = FD_SCRATCH_ALLOC_APPEND( l, vtr_map_align(), vtr_map_footprint( lg_vtr_max ) );
65 0 : FD_TEST( FD_SCRATCH_ALLOC_FINI( l, fd_ghost_align() ) == (ulong)shmem + footprint );
66 :
67 0 : ghost->pool = pool_new( pool, blk_max );
68 0 : ghost->blk_map = blk_map_new( map, blk_max, seed );
69 0 : ghost->vtr_map = vtr_map_new( vtr, lg_vtr_max, seed+1UL );
70 0 : ghost->root = pool_idx_null( ghost->pool );
71 :
72 0 : return shmem;
73 0 : }
74 :
75 : fd_ghost_t *
76 0 : fd_ghost_join( void * shghost ) {
77 0 : fd_ghost_t * ghost = (fd_ghost_t *)shghost;
78 :
79 0 : if( FD_UNLIKELY( !ghost ) ) {
80 0 : FD_LOG_WARNING(( "NULL ghost" ));
81 0 : return NULL;
82 0 : }
83 :
84 0 : if( FD_UNLIKELY( !fd_ulong_is_aligned((ulong)ghost, fd_ghost_align() ) ) ) {
85 0 : FD_LOG_WARNING(( "misaligned ghost" ));
86 0 : return NULL;
87 0 : }
88 :
89 0 : ghost->pool = pool_join( ghost->pool );
90 0 : ghost->blk_map = blk_map_join( ghost->blk_map );
91 0 : ghost->vtr_map = vtr_map_join( ghost->vtr_map );
92 :
93 0 : return ghost;
94 0 : }
95 :
96 : void *
97 0 : fd_ghost_leave( fd_ghost_t const * ghost ) {
98 :
99 0 : if( FD_UNLIKELY( !ghost ) ) {
100 0 : FD_LOG_WARNING(( "NULL ghost" ));
101 0 : return NULL;
102 0 : }
103 :
104 0 : return (void *)ghost;
105 0 : }
106 :
107 : void *
108 0 : fd_ghost_delete( void * ghost ) {
109 :
110 0 : if( FD_UNLIKELY( !ghost ) ) {
111 0 : FD_LOG_WARNING(( "NULL ghost" ));
112 0 : return NULL;
113 0 : }
114 :
115 0 : if( FD_UNLIKELY( !fd_ulong_is_aligned((ulong)ghost, fd_ghost_align() ) ) ) {
116 0 : FD_LOG_WARNING(( "misaligned ghost" ));
117 0 : return NULL;
118 0 : }
119 :
120 0 : return ghost;
121 0 : }
122 :
123 : fd_ghost_blk_t *
124 0 : fd_ghost_root( fd_ghost_t * ghost ) {
125 0 : return pool_ele( ghost->pool, ghost->root );
126 0 : }
127 :
128 : fd_ghost_blk_t *
129 : fd_ghost_query( fd_ghost_t * ghost,
130 0 : fd_hash_t const * block_id ) {
131 0 : return blk_map_ele_query( ghost->blk_map, block_id, NULL, ghost->pool );
132 0 : }
133 :
134 : fd_ghost_blk_t *
135 : fd_ghost_best( fd_ghost_t * ghost,
136 0 : fd_ghost_blk_t * root ) {
137 0 : fd_ghost_blk_t * pool = ghost->pool;
138 0 : ulong null = pool_idx_null( pool );
139 0 : fd_ghost_blk_t * best = root;
140 0 : while( FD_LIKELY( best->child != null ) ) {
141 0 : int valid = 0; /* at least one child is valid */
142 0 : fd_ghost_blk_t * child = pool_ele( ghost->pool, best->child );
143 0 : while( FD_LIKELY( child ) ) { /* greedily pick the heaviest valid child */
144 0 : if( FD_LIKELY( child->valid ) ) {
145 0 : if( FD_LIKELY( !valid ) ) { /* this is the first valid child, so progress the head */
146 0 : best = child;
147 0 : valid = 1;
148 0 : }
149 0 : best = fd_ptr_if(
150 0 : fd_int_if(
151 0 : child->stake == best->stake, /* if the weights are equal */
152 0 : child->slot < best->slot, /* then tie-break by lower slot number */
153 0 : child->stake > best->stake ), /* else return heavier */
154 0 : child, best );
155 0 : }
156 0 : child = pool_ele( ghost->pool, child->sibling );
157 0 : }
158 0 : if( FD_UNLIKELY( !valid ) ) break; /* no children are valid, so short-circuit traversal */
159 0 : }
160 0 : return best;
161 0 : }
162 :
163 : fd_ghost_blk_t *
164 : fd_ghost_deepest( fd_ghost_t * ghost,
165 0 : fd_ghost_blk_t * root ) {
166 0 : fd_ghost_blk_t * pool = ghost->pool;
167 0 : ulong null = pool_idx_null( pool );
168 0 : fd_ghost_blk_t * head = blk_map_ele_remove( ghost->blk_map, &root->id, NULL, pool ); /* remove ele from map to reuse `.next` */
169 0 : fd_ghost_blk_t * tail = head;
170 :
171 : /* Below is a level-order traversal (BFS), returning the last leaf
172 : which is guaranteed to return an element of the max depth.
173 :
174 : It temporarily removes elements of the map when pushing onto the
175 : BFS queue to reuse the .next pointer and then inserts back into
176 : the map on queue pop. */
177 :
178 0 : head->next = null;
179 0 : while( FD_LIKELY( head ) ) {
180 0 : fd_ghost_blk_t const * child = pool_ele( ghost->pool, head->child );
181 0 : while( FD_LIKELY( child ) ) {
182 0 : tail->next = pool_idx( pool, blk_map_ele_remove( ghost->blk_map, &child->id, NULL, pool ) );
183 0 : tail = pool_ele( pool, tail->next );
184 0 : tail->next = pool_idx_null( pool );
185 0 : child = pool_ele( pool, child->sibling ); /* next sibling */
186 0 : }
187 0 : fd_ghost_blk_t * next = pool_ele( pool, head->next ); /* pop prune queue head */
188 0 : blk_map_ele_insert( ghost->blk_map, head, pool ); /* re-insert head into map */
189 0 : head = next;
190 0 : }
191 0 : return head;
192 0 : }
193 :
194 0 : #define PREDICATE_ANCESTOR( predicate ) do { \
195 0 : fd_ghost_blk_t * ancestor = descendant; \
196 0 : while( FD_LIKELY( ancestor ) ) { \
197 0 : if( FD_LIKELY( predicate ) ) return ancestor; \
198 0 : ancestor = pool_ele( ghost->pool, ancestor->parent ); \
199 0 : } \
200 0 : return NULL; \
201 0 : } while(0)
202 :
203 : fd_ghost_blk_t *
204 : fd_ghost_ancestor( fd_ghost_t * ghost,
205 : fd_ghost_blk_t * descendant,
206 0 : fd_hash_t const * ancestor_id ) {
207 0 : PREDICATE_ANCESTOR( 0==memcmp( &ancestor->id, ancestor_id, sizeof(fd_hash_t) ) );
208 0 : }
209 :
210 : fd_ghost_blk_t *
211 : fd_ghost_slot_ancestor( fd_ghost_t * ghost,
212 : fd_ghost_blk_t * descendant,
213 0 : ulong slot ) {
214 0 : PREDICATE_ANCESTOR( ancestor->slot == slot );
215 0 : }
216 :
217 : fd_ghost_blk_t *
218 : fd_ghost_invalid_ancestor( fd_ghost_t * ghost,
219 0 : fd_ghost_blk_t * descendant ) {
220 0 : PREDICATE_ANCESTOR( !ancestor->valid );
221 0 : }
222 :
223 : fd_ghost_blk_t *
224 : fd_ghost_insert( fd_ghost_t * ghost,
225 : fd_hash_t const * block_id,
226 : fd_hash_t const * parent_block_id,
227 0 : ulong slot ) {
228 :
229 0 : fd_ghost_blk_t * pool = ghost->pool;
230 0 : ulong null = pool_idx_null( pool );
231 0 : fd_ghost_blk_t * blk = blk_map_ele_query( ghost->blk_map, block_id, NULL, pool );
232 :
233 0 : # if FD_GHOST_USE_HANDHOLDING
234 0 : if( FD_UNLIKELY( blk ) ) {
235 0 : FD_BASE58_ENCODE_32_BYTES( block_id->key, block_id_b58 );
236 0 : FD_LOG_WARNING(( "[%s] hash %s already in ghost", __func__, block_id_b58 ));
237 0 : return NULL;
238 0 : }
239 0 : if( FD_UNLIKELY( !pool_free( pool ) ) ) { FD_LOG_WARNING(( "[%s] ghost full", __func__ )); return NULL; }
240 0 : # endif
241 :
242 0 : blk = pool_ele_acquire( pool );
243 0 : blk->id = *block_id;
244 0 : blk->slot = slot;
245 0 : blk->next = null;
246 0 : blk->parent = null;
247 0 : blk->child = null;
248 0 : blk->sibling = null;
249 0 : blk->stake = 0;
250 0 : blk->total_stake = 0;
251 0 : blk->eqvoc = 0;
252 0 : blk->conf = 0;
253 0 : blk->valid = 1;
254 0 : blk_map_ele_insert( ghost->blk_map, blk, pool );
255 :
256 0 : if( FD_UNLIKELY( !parent_block_id ) ) {
257 0 : ghost->root = pool_idx( pool, blk );
258 0 : return blk;
259 0 : }
260 :
261 0 : fd_ghost_blk_t * parent = blk_map_ele_query( ghost->blk_map, parent_block_id, NULL, pool );
262 0 : FD_TEST( parent ); /* parent must exist if this is not the first insertion */
263 0 : blk->parent = pool_idx( pool, parent );
264 0 : if( FD_LIKELY( parent->child == null ) ) {
265 0 : parent->child = pool_idx( pool, blk ); /* left-child */
266 0 : } else {
267 0 : fd_ghost_blk_t * sibling = pool_ele( pool, parent->child );
268 0 : while( sibling->sibling != null ) sibling = pool_ele( pool, sibling->sibling );
269 0 : sibling->sibling = pool_idx( pool, blk ); /* right-sibling */
270 0 : }
271 :
272 0 : return blk;
273 0 : }
274 :
275 : void
276 : fd_ghost_count_vote( fd_ghost_t * ghost,
277 : fd_ghost_blk_t * blk,
278 : fd_pubkey_t const * vote_acc,
279 : ulong stake,
280 0 : ulong slot ) {
281 :
282 0 : fd_ghost_blk_t const * root = fd_ghost_root( ghost );
283 0 : fd_ghost_blk_t * pool = ghost->pool;
284 0 : fd_ghost_vtr_t * vtr = vtr_map_query( ghost->vtr_map, *vote_acc, NULL );
285 :
286 0 : if( FD_UNLIKELY( slot == ULONG_MAX ) ) return; /* hasn't voted */
287 0 : if( FD_UNLIKELY( slot < root->slot ) ) return; /* vote older than root */
288 :
289 0 : if( FD_UNLIKELY( !vtr ) ) vtr = vtr_map_insert( ghost->vtr_map, *vote_acc );
290 0 : else {
291 :
292 : /* Only process the vote if it is not the same as the previous vote
293 : and also that the vote slot is most recent. It's possible for
294 : ghost to process votes out of order because votes happen in
295 : replay order which is concurrent across different forks.
296 :
297 : For example, if a voter votes for 3 then switches to 5, we might
298 : observe the vote for 5 before the vote for 3. */
299 :
300 0 : if( FD_UNLIKELY( !( slot > vtr->prev_slot ) ) ) return;
301 :
302 : /* LMD-rule: subtract the voter's stake from the entire fork they
303 : previously voted for. */
304 :
305 : /* TODO can optimize this if they're voting for the same fork */
306 :
307 0 : fd_ghost_blk_t * ancestor = blk_map_ele_query( ghost->blk_map, &vtr->prev_block_id, NULL, pool );
308 0 : while( FD_LIKELY( ancestor ) ) {
309 0 : int cf = __builtin_usubl_overflow( ancestor->stake, vtr->prev_stake, &ancestor->stake );
310 0 : if( FD_UNLIKELY( cf ) ) {
311 0 : FD_BASE58_ENCODE_32_BYTES( ancestor->id.key, ancestor_id_b58 );
312 0 : FD_LOG_CRIT(( "[%s] overflow: %lu - %lu. (slot %lu, block_id: %s)", __func__, ancestor->stake, vtr->prev_stake, ancestor->slot, ancestor_id_b58 ));
313 0 : }
314 0 : ancestor = pool_ele( pool, ancestor->parent );
315 0 : }
316 0 : }
317 :
318 : /* Add voter's stake to the entire fork they are voting for. Propagate
319 : the vote stake up the ancestry. We do this for all cases we exited
320 : above: this vote is the first vote we've seen from a pubkey, this
321 : vote is switched from a previous vote that was on a missing ele
322 : (pruned), or the regular case. */
323 :
324 0 : fd_ghost_blk_t * ancestor = blk;
325 0 : while( FD_LIKELY( ancestor ) ) {
326 0 : int cf = __builtin_uaddl_overflow( ancestor->stake, stake, &ancestor->stake );
327 0 : if( FD_UNLIKELY( cf ) ) {
328 0 : FD_BASE58_ENCODE_32_BYTES( ancestor->id.key, ancestor_id_b58 );
329 0 : FD_LOG_CRIT(( "[%s] overflow: %lu + %lu. (slot %lu, block_id: %s)", __func__, ancestor->stake, stake, ancestor->slot, ancestor_id_b58 ));
330 0 : }
331 0 : ancestor = pool_ele( ghost->pool, ancestor->parent );
332 0 : }
333 0 : vtr->prev_block_id = blk->id;
334 0 : vtr->prev_stake = stake;
335 0 : }
336 :
337 : void
338 : fd_ghost_publish( fd_ghost_t * ghost,
339 0 : fd_ghost_blk_t * newr ) {
340 :
341 0 : fd_ghost_blk_t * pool = ghost->pool;
342 0 : ulong null = pool_idx_null( pool );
343 0 : fd_ghost_blk_t * oldr = fd_ghost_root( ghost );
344 :
345 0 : if( FD_UNLIKELY( oldr==newr ) ) return;
346 :
347 : /* First, remove the previous root, and add it to the prune list. In
348 : this context, head is the list head (not to be confused with the
349 : ghost head.) */
350 :
351 0 : fd_ghost_blk_t * head = blk_map_ele_remove( ghost->blk_map, &oldr->id, NULL, pool ); /* remove ele from map to reuse `.next` */
352 0 : fd_ghost_blk_t * tail = head;
353 :
354 : /* Second, BFS down the tree, pruning all of root's ancestors and also
355 : any descendants of those ancestors. */
356 :
357 0 : head->next = null;
358 0 : while( FD_LIKELY( head ) ) {
359 0 : fd_ghost_blk_t * child = pool_ele( pool, head->child );
360 0 : while( FD_LIKELY( child ) ) { /* iterate over children */
361 0 : if( FD_LIKELY( child != newr ) ) { /* stop at new root */
362 0 : tail->next = blk_map_idx_remove( ghost->blk_map, &child->id, null, pool ); /* remove ele from map to reuse `.next` */
363 0 : tail = pool_ele( pool, tail->next ); /* push onto prune queue (so descendants can be pruned) */
364 0 : tail->next = pool_idx_null( pool );
365 0 : }
366 0 : child = pool_ele( pool, child->sibling ); /* next sibling */
367 0 : }
368 0 : fd_ghost_blk_t * next = pool_ele( pool, head->next ); /* pop prune queue head */
369 0 : pool_ele_release( pool, head ); /* free prune queue head */
370 0 : head = next; /* move prune queue head forward */
371 0 : }
372 0 : newr->parent = null; /* unlink old root */
373 0 : ghost->root = pool_idx( pool, newr ); /* replace with new root */
374 0 : }
375 :
376 : int
377 0 : fd_ghost_verify( fd_ghost_t * ghost ) {
378 0 : if( FD_UNLIKELY( !ghost ) ) {
379 0 : FD_LOG_WARNING(( "NULL ghost" ));
380 0 : return -1;
381 0 : }
382 :
383 0 : if( FD_UNLIKELY( !fd_ulong_is_aligned( (ulong)ghost, fd_ghost_align() ) ) ) {
384 0 : FD_LOG_WARNING(( "misaligned ghost" ));
385 0 : return -1;
386 0 : }
387 :
388 0 : fd_wksp_t * wksp = fd_wksp_containing( ghost );
389 0 : if( FD_UNLIKELY( !wksp ) ) {
390 0 : FD_LOG_WARNING(( "ghost must be part of a workspace" ));
391 0 : return -1;
392 0 : }
393 :
394 0 : fd_ghost_blk_t const * pool = ghost->pool;
395 0 : ulong null = pool_idx_null( pool );
396 :
397 : /* Check every ele that exists in pool exists in map. */
398 :
399 0 : if( blk_map_verify( ghost->blk_map, pool_max( pool ), pool ) ) return -1;
400 :
401 : /* Check every ele's stake is >= sum of children's stakes. */
402 :
403 0 : fd_ghost_blk_t const * parent = fd_ghost_root( ghost );
404 0 : while( FD_LIKELY( parent ) ) {
405 0 : ulong weight = 0;
406 0 : fd_ghost_blk_t const * child = pool_ele( ghost->pool, parent->child );
407 0 : while( FD_LIKELY( child && child->sibling != null ) ) {
408 0 : weight += child->stake;
409 0 : child = pool_ele( ghost->pool, child->sibling );
410 0 : }
411 0 : # if FD_GHOST_USE_HANDHOLDING
412 0 : FD_TEST( parent->stake >= weight );
413 0 : # endif
414 0 : parent = pool_ele_const( pool, parent->next );
415 0 : }
416 :
417 0 : return 0;
418 0 : }
419 :
420 : #include <stdio.h>
421 :
422 : static void
423 0 : print( fd_ghost_t const * ghost, fd_ghost_blk_t const * ele, ulong total_stake, int space, const char * prefix ) {
424 0 : fd_ghost_blk_t const * pool = ghost->pool;
425 :
426 0 : if( FD_UNLIKELY( ele == NULL ) ) return;
427 :
428 0 : if( FD_LIKELY( space > 0 ) ) printf( "\n" );
429 0 : for( int i = 0; i < space; i++ )
430 0 : printf( " " );
431 0 : if( FD_UNLIKELY( ele->stake > 100 ) ) {
432 0 : }
433 0 : if( FD_UNLIKELY( total_stake == 0 ) ) {
434 0 : printf( "%s%lu (%lu)", prefix, ele->slot, ele->stake );
435 0 : } else {
436 0 : double pct = ( (double)ele->stake / (double)total_stake ) * 100;
437 0 : if( FD_UNLIKELY( pct < 0.99 )) {
438 0 : printf( "%s%lu (%.0lf%%, %lu)", prefix, ele->slot, pct, ele->stake );
439 0 : } else {
440 0 : printf( "%s%lu (%.0lf%%)", prefix, ele->slot, pct );
441 0 : }
442 0 : }
443 :
444 0 : fd_ghost_blk_t const * curr = pool_ele_const( pool, ele->child );
445 0 : char new_prefix[1024]; /* FIXME size this correctly */
446 0 : while( curr ) {
447 0 : if( FD_UNLIKELY( pool_ele_const( pool, curr->sibling ) ) ) {
448 0 : sprintf( new_prefix, "├── " ); /* branch indicating more siblings follow */
449 0 : print( ghost, curr, total_stake, space + 4, new_prefix );
450 0 : } else {
451 0 : sprintf( new_prefix, "└── " ); /* end branch */
452 0 : print( ghost, curr, total_stake, space + 4, new_prefix );
453 0 : }
454 0 : curr = pool_ele_const( pool, curr->sibling );
455 0 : }
456 0 : }
457 :
458 : void
459 : fd_ghost_print( fd_ghost_t const * ghost,
460 0 : fd_ghost_blk_t const * root ) {
461 0 : FD_LOG_NOTICE( ( "\n\n[Ghost]" ) );
462 0 : print( ghost, root, root->total_stake, 0, "" );
463 : printf( "\n\n" );
464 0 : }
|
