Line data Source code
1 : #include "fd_ghost.h"
2 :
3 : #define POOL_NAME blk_pool
4 162 : #define POOL_T fd_ghost_blk_t
5 : #include "../../util/tmpl/fd_pool.c"
6 :
7 : #define MAP_NAME blk_map
8 : #define MAP_ELE_T fd_ghost_blk_t
9 1377 : #define MAP_KEY id
10 : #define MAP_KEY_T fd_hash_t
11 23025 : #define MAP_KEY_EQ(k0,k1) (!memcmp((k0),(k1), sizeof(fd_hash_t)))
12 24546 : #define MAP_KEY_HASH(key,seed) (fd_hash((seed),(key),sizeof(fd_hash_t)))
13 3726 : #define MAP_NEXT next
14 : #include "../../util/tmpl/fd_map_chain.c"
15 :
16 : #define POOL_NAME vtr_pool
17 162 : #define POOL_T fd_ghost_vtr_t
18 : #include "../../util/tmpl/fd_pool.c"
19 :
20 : #define MAP_NAME vtr_map
21 6 : #define MAP_ELE_T fd_ghost_vtr_t
22 1689 : #define MAP_KEY addr
23 : #define MAP_KEY_T fd_pubkey_t
24 20928 : #define MAP_KEY_EQ(k0,k1) (!memcmp((k0),(k1), sizeof(fd_pubkey_t)))
25 23256 : #define MAP_KEY_HASH(key,seed) (fd_hash((seed),(key),sizeof(fd_pubkey_t)))
26 3741 : #define MAP_PREV map.prev
27 4755 : #define MAP_NEXT map.next
28 : #define MAP_OPTIMIZE_RANDOM_ACCESS_REMOVAL 1
29 : #include "../../util/tmpl/fd_map_chain.c"
30 :
31 : #define DLIST_NAME vtr_dlist
32 : #define DLIST_ELE_T fd_ghost_vtr_t
33 41211 : #define DLIST_PREV dlist.prev
34 41217 : #define DLIST_NEXT dlist.next
35 : #include "../../util/tmpl/fd_dlist.c"
36 :
37 : /* fd_ghost_t is the top-level structure that holds the root of the
38 : tree, as well as the memory pools and map structures for tracking
39 : ghost eles and votes.
40 :
41 : These structures are bump-allocated and laid out contiguously in
42 : memory from the fd_ghost_t * pointer which points to the beginning of
43 : the memory region.
44 :
45 : --------------------------- <- fd_ghost_t *
46 : | fd_ghost_t |
47 : ---------------------------
48 : | blk_pool |
49 : ---------------------------
50 : | blk_map |
51 : ---------------------------
52 : | vtr_pool |
53 : ---------------------------
54 : | vtr_map |
55 : ---------------------------
56 : | vtr_dlist for blk[0] |
57 : | vtr_dlist for blk[1] |
58 : | ... |
59 : | vtr_dlist for blk[N-1] |
60 : --------------------------- */
61 :
62 : struct __attribute__((aligned(128UL))) fd_ghost {
63 : ulong root; /* pool idx of the root tree element */
64 : ulong wksp_gaddr; /* wksp gaddr of fd_ghost in the backing wksp */
65 : ulong blk_pool_gaddr; /* memory offset of the blk_pool */
66 : ulong blk_map_gaddr; /* memory offset of the blk_map */
67 : ulong vtr_pool_gaddr; /* memory offset of the vtr_pool */
68 : ulong vtr_map_gaddr; /* memory offset of the vtr_map */
69 : ulong width; /* incrementally updated width of the fork tree */
70 : };
71 :
72 : typedef fd_ghost_blk_t blk_pool_t;
73 : typedef fd_ghost_vtr_t vtr_pool_t;
74 :
75 : /* wksp returns the local join to the wksp backing the
76 : ghost. The lifetime of the returned pointer is at least as
77 : long as the lifetime of the local join. Assumes ghost is a
78 : current local join. */
79 :
80 : FD_FN_PURE static inline fd_wksp_t *
81 629622 : wksp( fd_ghost_t const * ghost ) {
82 629622 : return (fd_wksp_t *)( ((ulong)ghost) - ghost->wksp_gaddr );
83 629622 : }
84 :
85 : static inline blk_pool_t *
86 471954 : blk_pool( fd_ghost_t * ghost ) {
87 471954 : return (blk_pool_t *)fd_wksp_laddr_fast( wksp( ghost ), ghost->blk_pool_gaddr );
88 471954 : }
89 :
90 : static inline blk_pool_t const *
91 2772 : blk_pool_const( fd_ghost_t const * ghost ) {
92 2772 : return (blk_pool_t const *)fd_wksp_laddr_fast( wksp( ghost ), ghost->blk_pool_gaddr );
93 2772 : }
94 :
95 : static inline blk_map_t *
96 24189 : blk_map( fd_ghost_t * ghost ) {
97 24189 : return (blk_map_t *)fd_wksp_laddr_fast( wksp( ghost ), ghost->blk_map_gaddr );
98 24189 : }
99 :
100 : static inline vtr_pool_t *
101 66201 : vtr_pool( fd_ghost_t * ghost ) {
102 66201 : return (vtr_pool_t *)fd_wksp_laddr_fast( wksp( ghost ), ghost->vtr_pool_gaddr );
103 66201 : }
104 :
105 : static inline vtr_map_t *
106 23256 : vtr_map( fd_ghost_t * ghost ) {
107 23256 : return (vtr_map_t *)fd_wksp_laddr_fast( wksp( ghost ), ghost->vtr_map_gaddr );
108 23256 : }
109 :
110 : /* blk_vtr_dlist returns the local join to blk's vtr_dlist — the list of
111 : vtrs whose prev_block_id == blk->id. Each block slot is bound (by
112 : gaddr) to a dlist once in fd_ghost_new, so this is gaddr-safe across
113 : relocation / separate local joins. */
114 :
115 : static inline vtr_dlist_t *
116 41250 : blk_vtr_dlist( fd_ghost_t * ghost, fd_ghost_blk_t const * blk ) {
117 41250 : return (vtr_dlist_t *)fd_wksp_laddr_fast( wksp( ghost ), blk->vtr_dlist_gaddr );
118 41250 : }
119 :
120 : ulong
121 981 : fd_ghost_align( void ) {
122 981 : return alignof(fd_ghost_t);
123 981 : }
124 :
125 : ulong
126 : fd_ghost_footprint( ulong blk_max,
127 204 : ulong vtr_max ) {
128 204 : blk_max = fd_ulong_pow2_up( blk_max );
129 204 : vtr_max = fd_ulong_pow2_up( vtr_max ) * 2; /* epoch boundary overlap — old epoch vtrs parked on live blocks while new epoch voters acquire */
130 204 : ulong blk_chain_cnt = blk_map_chain_cnt_est( blk_max );
131 204 : ulong vtr_chain_cnt = vtr_map_chain_cnt_est( vtr_max );
132 204 : return FD_LAYOUT_FINI(
133 204 : FD_LAYOUT_APPEND(
134 204 : FD_LAYOUT_APPEND(
135 204 : FD_LAYOUT_APPEND(
136 204 : FD_LAYOUT_APPEND(
137 204 : FD_LAYOUT_APPEND(
138 204 : FD_LAYOUT_APPEND(
139 204 : FD_LAYOUT_INIT,
140 204 : alignof(fd_ghost_t), sizeof(fd_ghost_t) ),
141 204 : blk_pool_align(), blk_pool_footprint( blk_max ) ),
142 204 : blk_map_align(), blk_map_footprint ( blk_chain_cnt ) ),
143 204 : vtr_pool_align(), vtr_pool_footprint( vtr_max ) ),
144 204 : vtr_map_align(), vtr_map_footprint ( vtr_chain_cnt ) ),
145 204 : vtr_dlist_align(), vtr_dlist_footprint() * blk_max ),
146 204 : fd_ghost_align() );
147 204 : }
148 :
149 : void *
150 : fd_ghost_new( void * shmem,
151 : ulong blk_max,
152 : ulong vtr_max,
153 81 : ulong seed ) {
154 :
155 81 : if( FD_UNLIKELY( !shmem ) ) {
156 0 : FD_LOG_WARNING(( "NULL mem" ));
157 0 : return NULL;
158 0 : }
159 :
160 81 : if( FD_UNLIKELY( !fd_ulong_is_aligned( (ulong)shmem, fd_ghost_align() ) ) ) {
161 0 : FD_LOG_WARNING(( "misaligned mem" ));
162 0 : return NULL;
163 0 : }
164 :
165 81 : ulong footprint = fd_ghost_footprint( blk_max, vtr_max );
166 :
167 81 : blk_max = fd_ulong_pow2_up( blk_max );
168 81 : vtr_max = fd_ulong_pow2_up( vtr_max ) * 2; /* epoch boundary overlap */
169 81 : if( FD_UNLIKELY( !footprint ) ) {
170 0 : FD_LOG_WARNING(( "bad blk_max (%lu)", blk_max ));
171 0 : return NULL;
172 0 : }
173 :
174 81 : fd_wksp_t * wksp = fd_wksp_containing( shmem );
175 81 : if( FD_UNLIKELY( !wksp ) ) {
176 0 : FD_LOG_WARNING(( "shmem must be part of a workspace" ));
177 0 : return NULL;
178 0 : }
179 :
180 81 : fd_memset( shmem, 0, footprint );
181 :
182 81 : ulong blk_chain_cnt = blk_map_chain_cnt_est( blk_max );
183 81 : ulong vtr_chain_cnt = vtr_map_chain_cnt_est( vtr_max );
184 :
185 81 : FD_SCRATCH_ALLOC_INIT( l, shmem );
186 81 : fd_ghost_t * ghost = FD_SCRATCH_ALLOC_APPEND( l, alignof(fd_ghost_t), sizeof(fd_ghost_t) );
187 81 : void * blk_pool = FD_SCRATCH_ALLOC_APPEND( l, blk_pool_align(), blk_pool_footprint( blk_max ) );
188 81 : void * blk_map = FD_SCRATCH_ALLOC_APPEND( l, blk_map_align(), blk_map_footprint ( blk_chain_cnt ) );
189 81 : void * vtr_pool = FD_SCRATCH_ALLOC_APPEND( l, vtr_pool_align(), vtr_pool_footprint( vtr_max ) );
190 81 : void * vtr_map = FD_SCRATCH_ALLOC_APPEND( l, vtr_map_align(), vtr_map_footprint ( vtr_chain_cnt ) );
191 81 : void * vtr_dlist = FD_SCRATCH_ALLOC_APPEND( l, vtr_dlist_align(), vtr_dlist_footprint() * blk_max );
192 81 : FD_TEST( FD_SCRATCH_ALLOC_FINI( l, fd_ghost_align() ) == (ulong)shmem + footprint );
193 :
194 81 : ghost->root = ULONG_MAX;
195 81 : ghost->wksp_gaddr = fd_wksp_gaddr_fast( wksp, ghost );
196 81 : ghost->blk_pool_gaddr = fd_wksp_gaddr_fast( wksp, blk_pool_join( blk_pool_new ( blk_pool, blk_max ) ) );
197 81 : ghost->blk_map_gaddr = fd_wksp_gaddr_fast( wksp, blk_map_join ( blk_map_new ( blk_map, blk_chain_cnt, seed ) ) );
198 81 : ghost->vtr_pool_gaddr = fd_wksp_gaddr_fast( wksp, vtr_pool_join( vtr_pool_new ( vtr_pool, vtr_max ) ) );
199 81 : ghost->vtr_map_gaddr = fd_wksp_gaddr_fast( wksp, vtr_map_join ( vtr_map_new ( vtr_map, vtr_chain_cnt, seed ) ) );
200 :
201 : /* Format one vtr_dlist per block slot and bind it (by gaddr) to its
202 : pool element. The binding is permanent: acquire/release in
203 : insert()/fd_ghost_publish never changes blk->vtr_dlist_gaddr, and
204 : fd_ghost_publish drains a pruned block's dlist (leaving it empty)
205 : before releasing the slot, so a re-acquired block always starts with
206 : a clean list. */
207 :
208 81 : blk_pool_t * bp = (blk_pool_t *)fd_wksp_laddr_fast( wksp, ghost->blk_pool_gaddr ); /* blk_pool() accessor is shadowed by the local here */
209 5433 : for( ulong i=0UL; i<blk_max; i++ ) {
210 5352 : void * dl = vtr_dlist_join( vtr_dlist_new( (uchar *)vtr_dlist + i*vtr_dlist_footprint() ) );
211 5352 : blk_pool_ele( bp, i )->vtr_dlist_gaddr = fd_wksp_gaddr_fast( wksp, dl );
212 5352 : }
213 :
214 81 : return shmem;
215 81 : }
216 :
217 : fd_ghost_t *
218 81 : fd_ghost_join( void * shghost ) {
219 81 : fd_ghost_t * ghost = (fd_ghost_t *)shghost;
220 :
221 81 : if( FD_UNLIKELY( !ghost ) ) {
222 0 : FD_LOG_WARNING(( "NULL ghost" ));
223 0 : return NULL;
224 0 : }
225 :
226 81 : if( FD_UNLIKELY( !fd_ulong_is_aligned((ulong)ghost, fd_ghost_align() ) ) ) {
227 0 : FD_LOG_WARNING(( "misaligned ghost" ));
228 0 : return NULL;
229 0 : }
230 :
231 81 : return ghost;
232 81 : }
233 :
234 : void *
235 39 : fd_ghost_leave( fd_ghost_t const * ghost ) {
236 :
237 39 : if( FD_UNLIKELY( !ghost ) ) {
238 0 : FD_LOG_WARNING(( "NULL ghost" ));
239 0 : return NULL;
240 0 : }
241 :
242 39 : return (void *)ghost;
243 39 : }
244 :
245 : void *
246 39 : fd_ghost_delete( void * ghost ) {
247 :
248 39 : if( FD_UNLIKELY( !ghost ) ) {
249 0 : FD_LOG_WARNING(( "NULL ghost" ));
250 0 : return NULL;
251 0 : }
252 :
253 39 : if( FD_UNLIKELY( !fd_ulong_is_aligned((ulong)ghost, fd_ghost_align() ) ) ) {
254 0 : FD_LOG_WARNING(( "misaligned ghost" ));
255 0 : return NULL;
256 0 : }
257 :
258 39 : return ghost;
259 39 : }
260 :
261 : fd_ghost_blk_t *
262 51642 : fd_ghost_root( fd_ghost_t * ghost ) {
263 51642 : return blk_pool_ele( blk_pool( ghost ), ghost->root );
264 51642 : }
265 :
266 : fd_ghost_blk_t *
267 12 : fd_ghost_parent( fd_ghost_t * ghost, fd_ghost_blk_t * blk ) {
268 12 : return blk_pool_ele( blk_pool( ghost ), blk->parent );
269 12 : }
270 :
271 : fd_ghost_blk_t *
272 : fd_ghost_query( fd_ghost_t * ghost,
273 924 : fd_hash_t const * block_id ) {
274 924 : return blk_map_ele_query( blk_map( ghost ), block_id, NULL, blk_pool( ghost ) );
275 924 : }
276 :
277 : fd_ghost_blk_t *
278 : fd_ghost_best( fd_ghost_t * ghost,
279 321 : fd_ghost_blk_t * root ) {
280 321 : blk_pool_t * pool = blk_pool( ghost );
281 321 : ulong null = blk_pool_idx_null( pool );
282 321 : fd_ghost_blk_t * best = root;
283 2868 : while( FD_LIKELY( best->child != null ) ) {
284 2553 : int valid = 0; /* at least one child is valid */
285 2553 : fd_ghost_blk_t * child = blk_pool_ele( pool, best->child );
286 5127 : while( FD_LIKELY( child ) ) { /* greedily pick the heaviest valid child */
287 2574 : if( FD_LIKELY( child->valid ) ) {
288 2562 : if( FD_LIKELY( !valid ) ) { /* this is the first valid child, so progress the head */
289 2547 : best = child;
290 2547 : valid = 1;
291 2547 : }
292 :
293 : /* When stake is equal, tie-break by lower slot. Two valid
294 : children with equal stake and equal slot (ie. equivocating
295 : blocks) cannot occur: equivocating blocks are marked valid=0,
296 : so at most one of them would be valid unless multiple blocks
297 : for that slot are duplicate confirmed, which is a consensus
298 : invariant violation. */
299 :
300 2562 : best = fd_ptr_if(
301 2562 : fd_int_if(
302 2562 : child->stake == best->stake, /* if the weights are equal */
303 2562 : child->slot < best->slot, /* then tie-break by lower slot number */
304 2562 : child->stake > best->stake ), /* else return heavier */
305 2562 : child, best );
306 2562 : }
307 2574 : child = blk_pool_ele( pool, child->sibling );
308 2574 : }
309 2553 : if( FD_UNLIKELY( !valid ) ) break; /* no children are valid, so short-circuit traversal */
310 2553 : }
311 321 : return best;
312 321 : }
313 :
314 : fd_ghost_blk_t *
315 : fd_ghost_deepest( fd_ghost_t * ghost,
316 18 : fd_ghost_blk_t * root ) {
317 18 : blk_pool_t * pool = blk_pool( ghost );
318 18 : ulong null = blk_pool_idx_null( pool );
319 18 : fd_ghost_blk_t * head = blk_map_ele_remove( blk_map( ghost ), &root->id, NULL, pool ); /* remove ele from map to reuse `.next` */
320 18 : fd_ghost_blk_t * tail = head;
321 18 : fd_ghost_blk_t * prev = NULL;
322 :
323 : /* Below is a level-order traversal (BFS), returning the last leaf
324 : which is guaranteed to return an element of the max depth.
325 :
326 : It temporarily removes elements of the map when pushing onto the
327 : BFS queue to reuse the .next pointer and then inserts back into
328 : the map on queue pop. */
329 :
330 18 : head->next = null;
331 99 : while( FD_LIKELY( head ) ) {
332 81 : fd_ghost_blk_t const * child = blk_pool_ele( pool, head->child );
333 144 : while( FD_LIKELY( child ) ) {
334 63 : FD_TEST( blk_map_ele_remove( blk_map( ghost ), &child->id, NULL, pool ) ); /* in the tree so must be in the map */
335 63 : tail->next = blk_pool_idx( pool, child );
336 63 : tail = blk_pool_ele( pool, tail->next );
337 63 : tail->next = blk_pool_idx_null( pool );
338 63 : child = blk_pool_ele( pool, child->sibling ); /* next sibling */
339 63 : }
340 81 : fd_ghost_blk_t * next = blk_pool_ele( pool, head->next ); /* pop prune queue head */
341 81 : blk_map_ele_insert( blk_map( ghost ), head, pool ); /* re-insert head into map */
342 81 : prev = head;
343 81 : head = next;
344 81 : }
345 18 : return prev;
346 18 : }
347 :
348 22035 : #define PREDICATE_ANCESTOR( predicate ) do { \
349 22035 : fd_ghost_blk_t * ancestor = descendant; \
350 48969 : while( FD_LIKELY( ancestor ) ) { \
351 48465 : if( FD_LIKELY( predicate ) ) return ancestor; \
352 48465 : ancestor = blk_pool_ele( blk_pool( ghost ), ancestor->parent ); \
353 26934 : } \
354 22035 : return NULL; \
355 22035 : } while(0)
356 :
357 : fd_ghost_blk_t *
358 : fd_ghost_ancestor( fd_ghost_t * ghost,
359 : fd_ghost_blk_t * descendant,
360 252 : fd_hash_t const * ancestor_id ) {
361 252 : PREDICATE_ANCESTOR( 0==memcmp( &ancestor->id, ancestor_id, sizeof(fd_hash_t) ) );
362 252 : }
363 :
364 : fd_ghost_blk_t *
365 : fd_ghost_slot_ancestor( fd_ghost_t * ghost,
366 : fd_ghost_blk_t * descendant,
367 21525 : ulong slot ) {
368 21525 : PREDICATE_ANCESTOR( ancestor->slot == slot );
369 21525 : }
370 :
371 : fd_ghost_blk_t *
372 : fd_ghost_invalid_ancestor( fd_ghost_t * ghost,
373 258 : fd_ghost_blk_t * descendant ) {
374 258 : PREDICATE_ANCESTOR( !ancestor->valid );
375 258 : }
376 :
377 : static fd_ghost_blk_t *
378 : insert( fd_ghost_t * ghost,
379 : ulong slot,
380 708 : fd_hash_t const * block_id ) {
381 708 : fd_ghost_blk_t * pool = blk_pool( ghost );
382 708 : ulong null = blk_pool_idx_null( pool );
383 708 : fd_ghost_blk_t * blk = blk_map_ele_query( blk_map( ghost ), block_id, NULL, pool );
384 :
385 708 : FD_TEST( !blk ); /* duplicate insert */
386 708 : FD_TEST( blk_pool_free( pool ) ); /* ghost full */
387 :
388 708 : blk = blk_pool_ele_acquire( pool );
389 708 : blk->id = *block_id;
390 708 : blk->slot = slot;
391 708 : blk->next = null;
392 708 : blk->parent = null;
393 708 : blk->child = null;
394 708 : blk->sibling = null;
395 708 : blk->stake = 0;
396 708 : blk->total_stake = 0;
397 708 : blk->valid = 1;
398 708 : blk_map_ele_insert( blk_map( ghost ), blk, pool );
399 708 : return blk;
400 708 : }
401 :
402 : fd_ghost_blk_t *
403 : fd_ghost_init( fd_ghost_t * ghost,
404 : ulong slot,
405 81 : fd_hash_t const * block_id ) {
406 81 : fd_ghost_blk_t * blk = insert( ghost, slot, block_id );
407 81 : ghost->root = blk_pool_idx( blk_pool( ghost ), blk );
408 81 : ghost->width = 1;
409 81 : return blk;
410 81 : }
411 :
412 : fd_ghost_blk_t *
413 : fd_ghost_insert( fd_ghost_t * ghost,
414 : ulong slot,
415 : fd_hash_t const * block_id,
416 627 : fd_hash_t const * parent_block_id ) {
417 627 : fd_ghost_blk_t * blk = insert( ghost, slot, block_id );
418 627 : fd_ghost_blk_t * pool = blk_pool( ghost );
419 627 : ulong null = blk_pool_idx_null( pool );
420 627 : fd_ghost_blk_t * parent = blk_map_ele_query( blk_map( ghost ), parent_block_id, NULL, pool );
421 627 : FD_TEST( parent ); /* parent must exist be in ghost */
422 627 : blk->parent = blk_pool_idx( pool, parent );
423 627 : if( FD_LIKELY( parent->child == null ) ) {
424 543 : parent->child = blk_pool_idx( pool, blk ); /* left-child */
425 543 : } else {
426 84 : fd_ghost_blk_t * sibling = blk_pool_ele( pool, parent->child );
427 93 : while( sibling->sibling != null ) sibling = blk_pool_ele( pool, sibling->sibling );
428 84 : sibling->sibling = blk_pool_idx( pool, blk ); /* right-sibling */
429 84 : ghost->width++;
430 84 : }
431 :
432 627 : return blk;
433 627 : }
434 :
435 : int
436 : fd_ghost_count_vote( fd_ghost_t * ghost,
437 : fd_ghost_blk_t * blk,
438 : fd_pubkey_t const * vote_acc,
439 : ulong stake,
440 21558 : ulong slot ) {
441 :
442 21558 : fd_ghost_blk_t const * root = fd_ghost_root( ghost );
443 21558 : fd_ghost_vtr_t * vtr = vtr_map_ele_query( vtr_map( ghost ), vote_acc, NULL, vtr_pool( ghost ) );
444 :
445 21558 : if( FD_UNLIKELY( slot==ULONG_MAX ) ) return FD_GHOST_ERR_NOT_VOTED;
446 21558 : if( FD_UNLIKELY( slot< root->slot ) ) return FD_GHOST_ERR_VOTE_TOO_OLD;
447 :
448 21558 : if( FD_UNLIKELY( !vtr ) ) {
449 :
450 : /* This vote account address has not previously voted, so add it to
451 : the map of voters. */
452 :
453 1683 : vtr = vtr_pool_ele_acquire( vtr_pool( ghost ) );
454 1683 : vtr->addr = *vote_acc;
455 1683 : vtr_map_ele_insert( vtr_map( ghost ), vtr, vtr_pool( ghost ) );
456 :
457 19875 : } else {
458 :
459 : /* Only process the vote if it is not the same as the previous vote
460 : and also that the vote slot is most recent. It's possible for
461 : ghost to process votes out of order because votes happen in
462 : replay order which is concurrent across different forks.
463 :
464 : For example, if a voter votes for 3 then switches to 5, we might
465 : observe the vote for 5 before the vote for 3. */
466 :
467 19875 : if( FD_UNLIKELY( !( slot > vtr->prev_slot ) ) ) return FD_GHOST_ERR_ALREADY_VOTED;
468 :
469 : /* The voter is switching off their previous vote. Remove the vtr
470 : from the previous block's dlist; it is re-pushed onto the new
471 : block's dlist below. By the dlist invariant, a vtr that is still
472 : in the vtr_map has not had its previous block pruned, so prev is
473 : non-NULL. */
474 :
475 19764 : fd_ghost_blk_t * prev = blk_map_ele_query( blk_map( ghost ), &vtr->prev_block_id, NULL, blk_pool( ghost ) );
476 19764 : if( FD_LIKELY( prev ) ) vtr_dlist_ele_remove( blk_vtr_dlist( ghost, prev ), vtr, vtr_pool( ghost ) );
477 :
478 : /* LMD-rule: subtract the voter's stake from the entire fork they
479 : previously voted for. */
480 :
481 : /* TODO can optimize this if they're voting for the same fork */
482 :
483 19764 : fd_ghost_blk_t * ancestor = prev;
484 192510 : while( FD_LIKELY( ancestor ) ) {
485 172746 : int cf = __builtin_usubl_overflow( ancestor->stake, vtr->prev_stake, &ancestor->stake );
486 172746 : if( FD_UNLIKELY( cf ) ) {
487 0 : FD_BASE58_ENCODE_32_BYTES( ancestor->id.key, ancestor_id_b58 );
488 0 : FD_LOG_CRIT(( "[%s] overflow (after): %lu. subtracted: %lu. (slot %lu, block_id: %s)", __func__, ancestor->stake, vtr->prev_stake, ancestor->slot, ancestor_id_b58 ));
489 0 : }
490 172746 : ancestor = blk_pool_ele( blk_pool( ghost ), ancestor->parent );
491 172746 : }
492 19764 : }
493 :
494 : /* Park the vtr on the dlist of the block it is now voting for, so that
495 : it is released back to the vtr_pool when that block is pruned. */
496 :
497 21447 : vtr_dlist_ele_push_tail( blk_vtr_dlist( ghost, blk ), vtr, vtr_pool( ghost ) );
498 :
499 : /* Add voter's stake to the entire fork they are voting for. Propagate
500 : the vote stake up the ancestry. We do this for all cases we exited
501 : above: this vote is the first vote we've seen from a pubkey, this
502 : vote is switched from a previous vote that was on a missing ele
503 : (pruned), or the regular case. */
504 :
505 21447 : fd_ghost_blk_t * ancestor = blk;
506 215799 : while( FD_LIKELY( ancestor ) ) {
507 194352 : int cf = __builtin_uaddl_overflow( ancestor->stake, stake, &ancestor->stake );
508 194352 : if( FD_UNLIKELY( cf ) ) {
509 0 : FD_BASE58_ENCODE_32_BYTES( ancestor->id.key, ancestor_id_b58 );
510 0 : FD_LOG_CRIT(( "[%s] overflow (after): %lu. added: %lu. (slot %lu, block_id: %s)", __func__, ancestor->stake, stake, ancestor->slot, ancestor_id_b58 ));
511 0 : }
512 194352 : ancestor = blk_pool_ele( blk_pool( ghost ), ancestor->parent );
513 194352 : }
514 21447 : vtr->prev_stake = stake;
515 21447 : vtr->prev_slot = slot;
516 21447 : vtr->prev_block_id = blk->id;
517 21447 : return FD_GHOST_SUCCESS;
518 21447 : }
519 :
520 : void
521 : fd_ghost_publish( fd_ghost_t * ghost,
522 9 : fd_ghost_blk_t * newr ) {
523 :
524 9 : fd_ghost_blk_t * pool = blk_pool( ghost );
525 9 : ulong null = blk_pool_idx_null( pool );
526 9 : fd_ghost_blk_t * oldr = fd_ghost_root( ghost );
527 :
528 9 : if( FD_UNLIKELY( oldr==newr ) ) return;
529 :
530 : /* First, remove the previous root, and add it to the prune list. In
531 : this context, head is the list head (not to be confused with the
532 : ghost head.) */
533 :
534 9 : fd_ghost_blk_t * head = blk_map_ele_remove( blk_map( ghost ), &oldr->id, NULL, pool ); /* remove ele from map to reuse `.next` */
535 9 : fd_ghost_blk_t * tail = head;
536 :
537 : /* Second, BFS down the tree, pruning all of root's ancestors and also
538 : any descendants of those ancestors.
539 :
540 : oldr
541 : |
542 : X
543 : / \
544 : newr Y
545 : |
546 : Z
547 :
548 : ...
549 :
550 : newr
551 :
552 : BFS starts with oldr. Its child is X. X != newr, so X gets
553 : enqueued. oldr is released. Next head = X. X's children are newr
554 : and Y. newr is skipped. Y gets enqueued. X is released. Next
555 : head = Y. Y's child Z gets enqueued. Y released. Z released.
556 : Queue is empty, loop ends.
557 :
558 : oldr
559 : / \
560 : A newr
561 : / \
562 : B C
563 :
564 : ...
565 :
566 : newr
567 : / \
568 : B C
569 :
570 :
571 : The BFS starts with oldr. Its children are A and newr. A gets
572 : enqueued for pruning. newr is skipped (line 374). Then oldr is
573 : released. Next, head = A. A has no children. A is released.
574 : Queue is empty, loop ends. */
575 :
576 9 : head->next = null;
577 48 : while( FD_LIKELY( head ) ) {
578 39 : fd_ghost_blk_t * child = blk_pool_ele( blk_pool( ghost ), head->child );
579 78 : while( FD_LIKELY( child ) ) { /* iterate over children */
580 39 : if( FD_LIKELY( child != newr ) ) { /* stop at new root */
581 30 : tail->next = blk_map_idx_remove( blk_map( ghost ), &child->id, null, pool ); /* remove ele from map to reuse `.next` */
582 30 : FD_BASE58_ENCODE_32_BYTES( child->id.key, block_id_cstr );
583 30 : tail = blk_pool_ele( blk_pool( ghost ), tail->next ); /* push onto prune queue (so descendants can be pruned) */
584 30 : tail->next = blk_pool_idx_null( blk_pool( ghost ) );
585 30 : }
586 39 : child = blk_pool_ele( blk_pool( ghost ), child->sibling ); /* next sibling */
587 39 : ghost->width -= !!child; /* has a sibling == a fork to be pruned */
588 39 : }
589 39 : fd_ghost_blk_t * next = blk_pool_ele( blk_pool( ghost ), head->next ); /* pop prune queue head */
590 :
591 : /* Release every vtr parked on this pruned block's dlist back to the
592 : vtr_pool. Their previous stake lived on this pruned subtree (which
593 : is being discarded along with the block), so there is nothing to
594 : unwind; if those voters vote again on a surviving block,
595 : fd_ghost_count_vote acquires a fresh vtr. This is what bounds the
596 : vtr_pool to the set of voters on the live tree. */
597 :
598 39 : vtr_dlist_t * dlist = blk_vtr_dlist( ghost, head );
599 45 : while( FD_LIKELY( !vtr_dlist_is_empty( dlist, vtr_pool( ghost ) ) ) ) {
600 6 : fd_ghost_vtr_t * vtr = vtr_dlist_ele_pop_head( dlist, vtr_pool( ghost ) );
601 6 : vtr_map_ele_remove_fast( vtr_map( ghost ), vtr, vtr_pool( ghost ) );
602 6 : vtr_pool_ele_release( vtr_pool( ghost ), vtr );
603 6 : }
604 :
605 39 : blk_pool_ele_release( blk_pool( ghost ), head ); /* free prune queue head */
606 39 : head = next; /* move prune queue head forward */
607 39 : }
608 9 : newr->parent = null; /* unlink old root */
609 9 : ghost->root = blk_pool_idx( blk_pool( ghost ), newr ); /* replace with new root */
610 9 : }
611 :
612 : /* mark_invalid marks the entire subtree beginning from root as invalid.
613 : Implementation is iterative pre-order traversal using O(1) space. */
614 :
615 : static void
616 : mark_invalid( fd_ghost_t * ghost,
617 27 : fd_ghost_blk_t * root ) {
618 27 : fd_ghost_blk_t * pool = blk_pool( ghost );
619 27 : fd_ghost_blk_t * curr = root;
620 :
621 : /* Loop invariant: curr has not been visited.
622 :
623 : Before: curr = root, which has not been visited. Trivially true.
624 :
625 : After: curr is set to either a child (step 2) or a right sibling of
626 : an ancestor found during backtracking (step 3). Preorder visits
627 : parents before children and left before right, so neither has been
628 : visited yet. If backtracking reaches root (step 4), loop exits. */
629 :
630 39 : for(;;) {
631 :
632 : /* 1. Visit: mark the current curr invalid. */
633 :
634 39 : curr->valid = 0;
635 :
636 : /* 2. Descend: if the curr has a child, pivot to it. */
637 :
638 39 : fd_ghost_blk_t * child = blk_pool_ele( pool, curr->child );
639 39 : if( FD_LIKELY( child ) ) { curr = child; continue; }
640 :
641 : /* 3. Backtrack: if the curr is a leaf, traverse up until we find an
642 : ancestor with a right sibling, then pivot to that sibling. */
643 :
644 39 : while( FD_LIKELY( curr!=root ) ) {
645 12 : fd_ghost_blk_t * sibling = blk_pool_ele( pool, curr->sibling );
646 12 : if( FD_LIKELY( sibling ) ) { curr = sibling; break; }
647 12 : curr = blk_pool_ele( pool, curr->parent );
648 12 : }
649 :
650 : /* 4. Terminate: if we backtrack all the way to root, the traversal
651 : is complete. */
652 :
653 27 : if( FD_UNLIKELY( curr==root ) ) break;
654 27 : }
655 27 : }
656 :
657 : void
658 : fd_ghost_confirm( fd_ghost_t * ghost,
659 9 : fd_hash_t const * confirmed_block_id ) {
660 9 : fd_ghost_blk_t * pool = blk_pool( ghost );
661 9 : fd_ghost_blk_t * blk = blk_map_ele_query( blk_map( ghost ), confirmed_block_id, NULL, pool );
662 9 : if( FD_UNLIKELY( !blk ) ) return;
663 :
664 : /* Mark the confirmed block and its ancestors as valid, short-
665 : circuiting at the first ancestor that is already valid. */
666 :
667 9 : fd_ghost_blk_t * anc = blk;
668 12 : while( FD_LIKELY( anc ) ) {
669 12 : if( FD_LIKELY( anc->valid ) ) break;
670 3 : anc->valid = 1;
671 3 : anc = blk_pool_ele( pool, anc->parent );
672 3 : }
673 9 : }
674 :
675 : void
676 : fd_ghost_eqvoc( fd_ghost_t * ghost,
677 27 : fd_hash_t const * block_id ) {
678 27 : fd_ghost_blk_t * pool = blk_pool( ghost );
679 27 : fd_ghost_blk_t * blk = blk_map_ele_query( blk_map( ghost ), block_id, NULL, pool );
680 27 : if( FD_UNLIKELY( !blk ) ) return;
681 27 : mark_invalid( ghost, blk );
682 27 : }
683 :
684 : ulong
685 294 : fd_ghost_width( fd_ghost_t * ghost ) {
686 294 : return ghost->width;
687 294 : }
688 :
689 : fd_ghost_blk_t *
690 : fd_ghost_blk_map_remove( fd_ghost_t * ghost,
691 588 : fd_ghost_blk_t * blk ) {
692 588 : return blk_map_ele_remove( blk_map( ghost ), &blk->id, NULL, blk_pool( ghost ) );
693 588 : }
694 :
695 : void
696 : fd_ghost_blk_map_insert( fd_ghost_t * ghost,
697 588 : fd_ghost_blk_t * blk ) {
698 588 : blk_map_ele_insert( blk_map( ghost ), blk, blk_pool( ghost ) );
699 588 : }
700 :
701 : fd_ghost_blk_t *
702 : fd_ghost_blk_child( fd_ghost_t * ghost,
703 564 : fd_ghost_blk_t * blk ) {
704 564 : return blk_pool_ele( blk_pool( ghost ), blk->child );
705 564 : }
706 :
707 : fd_ghost_blk_t *
708 : fd_ghost_blk_sibling( fd_ghost_t * ghost,
709 543 : fd_ghost_blk_t * blk ) {
710 543 : return blk_pool_ele( blk_pool( ghost ), blk->sibling );
711 543 : }
712 :
713 : fd_ghost_blk_t *
714 : fd_ghost_blk_next( fd_ghost_t * ghost,
715 588 : fd_ghost_blk_t * blk ) {
716 588 : return blk_pool_ele( blk_pool( ghost ), blk->next );
717 588 : }
718 :
719 : ulong
720 : fd_ghost_blk_idx( fd_ghost_t * ghost,
721 537 : fd_ghost_blk_t * blk ) {
722 537 : return blk_pool_idx( blk_pool( ghost ), blk );
723 537 : }
724 :
725 : ulong
726 51 : fd_ghost_blk_idx_null( fd_ghost_t * ghost ) {
727 51 : return blk_pool_idx_null( blk_pool( ghost ) );
728 51 : }
729 :
730 : int
731 45 : fd_ghost_verify( fd_ghost_t * ghost ) {
732 45 : if( FD_UNLIKELY( !ghost ) ) {
733 0 : FD_LOG_WARNING(( "NULL ghost" ));
734 0 : return -1;
735 0 : }
736 :
737 45 : if( FD_UNLIKELY( !fd_ulong_is_aligned( (ulong)ghost, fd_ghost_align() ) ) ) {
738 0 : FD_LOG_WARNING(( "misaligned ghost" ));
739 0 : return -1;
740 0 : }
741 :
742 45 : fd_wksp_t * wksp = fd_wksp_containing( ghost );
743 45 : if( FD_UNLIKELY( !wksp ) ) {
744 0 : FD_LOG_WARNING(( "ghost must be part of a workspace" ));
745 0 : return -1;
746 0 : }
747 :
748 45 : fd_ghost_blk_t const * pool = blk_pool( ghost );
749 :
750 : /* Check every ele that exists in pool exists in map. */
751 :
752 45 : if( blk_map_verify( blk_map( ghost ), blk_pool_max( pool ), pool ) ) return -1;
753 :
754 45 : return 0;
755 45 : }
756 :
757 : #include <stdio.h>
758 : #include <string.h>
759 :
760 : #define BUF_MAX 4096
761 : #define DEPTH_MAX 512
762 :
763 : static void
764 : to_cstr( fd_ghost_t const * ghost,
765 : fd_ghost_blk_t const * ele,
766 : ulong total_stake,
767 : int space,
768 : const char * prefix,
769 : char * cstr,
770 : ulong len,
771 : ulong * off,
772 2772 : ulong depth ) {
773 2772 : if( FD_UNLIKELY( depth>DEPTH_MAX ) ) return;
774 :
775 2772 : fd_ghost_blk_t const * pool = blk_pool_const( ghost );
776 2772 : int n;
777 :
778 2772 : if( FD_UNLIKELY( ele == NULL ) ) return;
779 :
780 2772 : if( FD_LIKELY( space > 0 ) && *off < len ) {
781 2478 : cstr[(*off)++] = '\n';
782 2478 : }
783 :
784 84084 : for( int i = 0; i < space && *off < len; i++ ) {
785 81312 : cstr[(*off)++] = ' ';
786 81312 : }
787 :
788 2772 : if( FD_UNLIKELY( ele->stake > 100 ) ) {
789 2478 : }
790 :
791 2772 : if( FD_UNLIKELY( total_stake == 0 ) ) {
792 0 : if( *off < len ) {
793 0 : n = snprintf( cstr + *off, len - *off, "%s%lu (%lu)", prefix, ele->slot, ele->stake );
794 0 : if( FD_UNLIKELY( n < 0 )) FD_LOG_CRIT(( "snprintf: %d", n ));
795 0 : *off += (ulong)n;
796 0 : }
797 2772 : } else {
798 2772 : double pct = ( (double)ele->stake / (double)total_stake ) * 100;
799 2772 : if( FD_UNLIKELY( pct < 0.99 ) ) {
800 294 : if( *off < len ) {
801 294 : n = snprintf( cstr + *off, len - *off, "%s%lu (%.0lf%%, %lu)", prefix, ele->slot, pct, ele->stake );
802 294 : if( FD_UNLIKELY( n < 0 )) FD_LOG_CRIT(( "snprintf: %d", n ));
803 294 : *off += (ulong)n;
804 294 : }
805 2478 : } else {
806 2478 : if( *off < len ) {
807 2478 : n = snprintf( cstr + *off, len - *off, "%s%lu (%.0lf%%)", prefix, ele->slot, pct );
808 2478 : if( FD_UNLIKELY( n < 0 )) FD_LOG_CRIT(( "snprintf: %d", n ));
809 2478 : *off += (ulong)n;
810 2478 : }
811 2478 : }
812 2772 : }
813 :
814 2772 : fd_ghost_blk_t const * curr = blk_pool_ele_const( pool, ele->child );
815 :
816 5250 : while( curr ) {
817 2478 : char const * next_prefix = blk_pool_ele_const( pool, curr->sibling ) ? "├── " : "└── ";
818 2478 : to_cstr( ghost, curr, total_stake, space + 4, next_prefix, cstr, len, off, depth + 1 ); /* TODO remove recursion */
819 2478 : curr = blk_pool_ele_const( pool, curr->sibling );
820 2478 : }
821 2772 : }
822 :
823 : char *
824 : fd_ghost_to_cstr( fd_ghost_t const * ghost,
825 : fd_ghost_blk_t const * root,
826 : char * cstr,
827 : ulong cstr_max,
828 294 : ulong * cstr_len ) {
829 :
830 294 : ulong off = 0;
831 :
832 294 : int n = snprintf( cstr + off, cstr_max - off, "[Ghost]\n\n" );
833 294 : if( FD_UNLIKELY( n < 0 )) FD_LOG_CRIT(( "snprintf: %d", n ));
834 294 : off += (ulong)n;
835 :
836 294 : to_cstr( ghost, root, root->total_stake, 0, "", cstr, cstr_max, &off, 0 );
837 :
838 294 : if( off < cstr_max ) {
839 294 : n = snprintf( cstr + off, cstr_max - off, "\n\n" );
840 294 : if( FD_UNLIKELY( n < 0 )) FD_LOG_CRIT(( "snprintf: %d", n ));
841 294 : off += (ulong)n;
842 294 : }
843 :
844 294 : cstr[fd_ulong_min( off++, cstr_max - 1 )] = '\0';
845 294 : *cstr_len = fd_ulong_min( off, cstr_max );
846 294 : return cstr;
847 294 : }
|
