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