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 ) ) { FD_LOG_WARNING(( "[%s] hash %s already in ghost", __func__, FD_BASE58_ENC_32_ALLOCA( block_id ) )); return NULL; }
235 0 : if( FD_UNLIKELY( !pool_free( pool ) ) ) { FD_LOG_WARNING(( "[%s] ghost full", __func__ )); return NULL; }
236 0 : # endif
237 :
238 0 : blk = pool_ele_acquire( pool );
239 0 : blk->id = *block_id;
240 0 : blk->slot = slot;
241 0 : blk->next = null;
242 0 : blk->parent = null;
243 0 : blk->child = null;
244 0 : blk->sibling = null;
245 0 : blk->stake = 0;
246 0 : blk->total_stake = 0;
247 0 : blk->eqvoc = 0;
248 0 : blk->conf = 0;
249 0 : blk->valid = 1;
250 0 : blk_map_ele_insert( ghost->blk_map, blk, pool );
251 :
252 0 : if( FD_UNLIKELY( !parent_block_id ) ) {
253 0 : ghost->root = pool_idx( pool, blk );
254 0 : return blk;
255 0 : }
256 :
257 0 : fd_ghost_blk_t * parent = blk_map_ele_query( ghost->blk_map, parent_block_id, NULL, pool );
258 0 : FD_TEST( parent ); /* parent must exist if this is not the first insertion */
259 0 : blk->parent = pool_idx( pool, parent );
260 0 : if( FD_LIKELY( parent->child == null ) ) {
261 0 : parent->child = pool_idx( pool, blk ); /* left-child */
262 0 : } else {
263 0 : fd_ghost_blk_t * sibling = pool_ele( pool, parent->child );
264 0 : while( sibling->sibling != null ) sibling = pool_ele( pool, sibling->sibling );
265 0 : sibling->sibling = pool_idx( pool, blk ); /* right-sibling */
266 0 : }
267 :
268 0 : return blk;
269 0 : }
270 :
271 : void
272 : fd_ghost_count_vote( fd_ghost_t * ghost,
273 : fd_ghost_blk_t * blk,
274 : fd_pubkey_t const * vote_acc,
275 : ulong stake,
276 0 : ulong slot ) {
277 :
278 0 : fd_ghost_blk_t const * root = fd_ghost_root( ghost );
279 0 : fd_ghost_blk_t * pool = ghost->pool;
280 0 : fd_ghost_vtr_t * vtr = vtr_map_query( ghost->vtr_map, *vote_acc, NULL );
281 :
282 0 : if( FD_UNLIKELY( slot == ULONG_MAX ) ) return; /* hasn't voted */
283 0 : if( FD_UNLIKELY( slot < root->slot ) ) return; /* vote older than root */
284 :
285 0 : if( FD_UNLIKELY( !vtr ) ) vtr = vtr_map_insert( ghost->vtr_map, *vote_acc );
286 0 : else {
287 :
288 : /* Only process the vote if it is not the same as the previous vote
289 : and also that the vote slot is most recent. It's possible for
290 : ghost to process votes out of order because votes happen in
291 : replay order which is concurrent across different forks.
292 :
293 : For example, if a voter votes for 3 then switches to 5, we might
294 : observe the vote for 5 before the vote for 3. */
295 :
296 0 : if( FD_UNLIKELY( !( slot > vtr->prev_slot ) ) ) return;
297 :
298 : /* LMD-rule: subtract the voter's stake from the entire fork they
299 : previously voted for. */
300 :
301 : /* TODO can optimize this if they're voting for the same fork */
302 :
303 0 : fd_ghost_blk_t * ancestor = blk_map_ele_query( ghost->blk_map, &vtr->prev_block_id, NULL, pool );
304 0 : while( FD_LIKELY( ancestor ) ) {
305 0 : int cf = __builtin_usubl_overflow( ancestor->stake, vtr->prev_stake, &ancestor->stake );
306 0 : if( FD_UNLIKELY( cf ) ) FD_LOG_CRIT(( "[%s] overflow: %lu - %lu. (slot %lu, block_id: %s)", __func__, ancestor->stake, vtr->prev_stake, ancestor->slot, FD_BASE58_ENC_32_ALLOCA( &ancestor->id ) ));
307 0 : ancestor = pool_ele( pool, ancestor->parent );
308 0 : }
309 0 : }
310 :
311 : /* Add voter's stake to the entire fork they are voting for. Propagate
312 : the vote stake up the ancestry. We do this for all cases we exited
313 : above: this vote is the first vote we've seen from a pubkey, this
314 : vote is switched from a previous vote that was on a missing ele
315 : (pruned), or the regular case. */
316 :
317 0 : fd_ghost_blk_t * ancestor = blk;
318 0 : while( FD_LIKELY( ancestor ) ) {
319 0 : int cf = __builtin_uaddl_overflow( ancestor->stake, stake, &ancestor->stake );
320 0 : if( FD_UNLIKELY( cf ) ) FD_LOG_CRIT(( "[%s] overflow: %lu + %lu. (slot %lu, block_id: %s)", __func__, ancestor->stake, stake, ancestor->slot, FD_BASE58_ENC_32_ALLOCA( &ancestor->id ) ));
321 0 : ancestor = pool_ele( ghost->pool, ancestor->parent );
322 0 : }
323 0 : vtr->prev_block_id = blk->id;
324 0 : vtr->prev_stake = stake;
325 0 : }
326 :
327 : void
328 : fd_ghost_publish( fd_ghost_t * ghost,
329 0 : fd_ghost_blk_t * newr ) {
330 :
331 0 : fd_ghost_blk_t * pool = ghost->pool;
332 0 : ulong null = pool_idx_null( pool );
333 0 : fd_ghost_blk_t * oldr = fd_ghost_root( ghost );
334 :
335 0 : if( FD_UNLIKELY( oldr==newr ) ) return;
336 :
337 : /* First, remove the previous root, and add it to the prune list. In
338 : this context, head is the list head (not to be confused with the
339 : ghost head.) */
340 :
341 0 : fd_ghost_blk_t * head = blk_map_ele_remove( ghost->blk_map, &oldr->id, NULL, pool ); /* remove ele from map to reuse `.next` */
342 0 : fd_ghost_blk_t * tail = head;
343 :
344 : /* Second, BFS down the tree, pruning all of root's ancestors and also
345 : any descendants of those ancestors. */
346 :
347 0 : head->next = null;
348 0 : while( FD_LIKELY( head ) ) {
349 0 : fd_ghost_blk_t * child = pool_ele( pool, head->child );
350 0 : while( FD_LIKELY( child ) ) { /* iterate over children */
351 0 : if( FD_LIKELY( child != newr ) ) { /* stop at new root */
352 0 : tail->next = blk_map_idx_remove( ghost->blk_map, &child->id, null, pool ); /* remove ele from map to reuse `.next` */
353 0 : tail = pool_ele( pool, tail->next ); /* push onto prune queue (so descendants can be pruned) */
354 0 : tail->next = pool_idx_null( pool );
355 0 : }
356 0 : child = pool_ele( pool, child->sibling ); /* next sibling */
357 0 : }
358 0 : fd_ghost_blk_t * next = pool_ele( pool, head->next ); /* pop prune queue head */
359 0 : pool_ele_release( pool, head ); /* free prune queue head */
360 0 : head = next; /* move prune queue head forward */
361 0 : }
362 0 : newr->parent = null; /* unlink old root */
363 0 : ghost->root = pool_idx( pool, newr ); /* replace with new root */
364 0 : }
365 :
366 : int
367 0 : fd_ghost_verify( fd_ghost_t * ghost ) {
368 0 : if( FD_UNLIKELY( !ghost ) ) {
369 0 : FD_LOG_WARNING(( "NULL ghost" ));
370 0 : return -1;
371 0 : }
372 :
373 0 : if( FD_UNLIKELY( !fd_ulong_is_aligned( (ulong)ghost, fd_ghost_align() ) ) ) {
374 0 : FD_LOG_WARNING(( "misaligned ghost" ));
375 0 : return -1;
376 0 : }
377 :
378 0 : fd_wksp_t * wksp = fd_wksp_containing( ghost );
379 0 : if( FD_UNLIKELY( !wksp ) ) {
380 0 : FD_LOG_WARNING(( "ghost must be part of a workspace" ));
381 0 : return -1;
382 0 : }
383 :
384 0 : fd_ghost_blk_t const * pool = ghost->pool;
385 0 : ulong null = pool_idx_null( pool );
386 :
387 : /* Check every ele that exists in pool exists in map. */
388 :
389 0 : if( blk_map_verify( ghost->blk_map, pool_max( pool ), pool ) ) return -1;
390 :
391 : /* Check every ele's stake is >= sum of children's stakes. */
392 :
393 0 : fd_ghost_blk_t const * parent = fd_ghost_root( ghost );
394 0 : while( FD_LIKELY( parent ) ) {
395 0 : ulong weight = 0;
396 0 : fd_ghost_blk_t const * child = pool_ele( ghost->pool, parent->child );
397 0 : while( FD_LIKELY( child && child->sibling != null ) ) {
398 0 : weight += child->stake;
399 0 : child = pool_ele( ghost->pool, child->sibling );
400 0 : }
401 0 : # if FD_GHOST_USE_HANDHOLDING
402 0 : FD_TEST( parent->stake >= weight );
403 0 : # endif
404 0 : parent = pool_ele_const( pool, parent->next );
405 0 : }
406 :
407 0 : return 0;
408 0 : }
409 :
410 : #include <stdio.h>
411 :
412 : static void
413 0 : print( fd_ghost_t const * ghost, fd_ghost_blk_t const * ele, ulong total_stake, int space, const char * prefix ) {
414 0 : fd_ghost_blk_t const * pool = ghost->pool;
415 :
416 0 : if( FD_UNLIKELY( ele == NULL ) ) return;
417 :
418 0 : if( FD_LIKELY( space > 0 ) ) printf( "\n" );
419 0 : for( int i = 0; i < space; i++ )
420 0 : printf( " " );
421 0 : if( FD_UNLIKELY( ele->stake > 100 ) ) {
422 0 : }
423 0 : if( FD_UNLIKELY( total_stake == 0 ) ) {
424 0 : printf( "%s%lu (%lu)", prefix, ele->slot, ele->stake );
425 0 : } else {
426 0 : double pct = ( (double)ele->stake / (double)total_stake ) * 100;
427 0 : if( FD_UNLIKELY( pct < 0.99 )) {
428 0 : printf( "%s%lu (%.0lf%%, %lu)", prefix, ele->slot, pct, ele->stake );
429 0 : } else {
430 0 : printf( "%s%lu (%.0lf%%)", prefix, ele->slot, pct );
431 0 : }
432 0 : }
433 :
434 0 : fd_ghost_blk_t const * curr = pool_ele_const( pool, ele->child );
435 0 : char new_prefix[1024]; /* FIXME size this correctly */
436 0 : while( curr ) {
437 0 : if( FD_UNLIKELY( pool_ele_const( pool, curr->sibling ) ) ) {
438 0 : sprintf( new_prefix, "├── " ); /* branch indicating more siblings follow */
439 0 : print( ghost, curr, total_stake, space + 4, new_prefix );
440 0 : } else {
441 0 : sprintf( new_prefix, "└── " ); /* end branch */
442 0 : print( ghost, curr, total_stake, space + 4, new_prefix );
443 0 : }
444 0 : curr = pool_ele_const( pool, curr->sibling );
445 0 : }
446 0 : }
447 :
448 : void
449 : fd_ghost_print( fd_ghost_t const * ghost,
450 0 : fd_ghost_blk_t const * root ) {
451 0 : FD_LOG_NOTICE( ( "\n\n[Ghost]" ) );
452 0 : print( ghost, root, root->total_stake, 0, "" );
453 : printf( "\n\n" );
454 0 : }
|
