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