Line data Source code
1 : #include <stdio.h>
2 : #include <string.h>
3 :
4 : #include "fd_tower.h"
5 : #include "../../flamenco/txn/fd_txn_generate.h"
6 : #include "../../flamenco/runtime/fd_system_ids.h"
7 : #include "../../flamenco/runtime/program/vote/fd_vote_state_versioned.h"
8 :
9 : /* Pool and map_chain for fd_tower_blk_t. */
10 :
11 : #define POOL_NAME blk_pool
12 108 : #define POOL_T fd_tower_blk_t
13 : #include "../../util/tmpl/fd_pool.c"
14 :
15 : #define MAP_NAME blk_map
16 3 : #define MAP_ELE_T fd_tower_blk_t
17 : #define MAP_KEY_T ulong
18 279 : #define MAP_KEY slot
19 2928 : #define MAP_KEY_EQ(k0,k1) (*(k0)==*(k1))
20 2571 : #define MAP_KEY_HASH(key,seed) ((*(key))^(seed))
21 : #define MAP_OPTIMIZE_RANDOM_ACCESS_REMOVAL 1
22 : #include "../../util/tmpl/fd_map_chain.c"
23 :
24 : /* lockout_interval tracks a map of lockout intervals.
25 :
26 : We need to track a list of lockout intervals per validator per slot.
27 : Intervals are inclusive. Example:
28 :
29 : After executing slot 33, validator A votes for slot 32, has a tower
30 :
31 : vote | confirmation count | lockout interval
32 : ----- | -------------------|------------------
33 : 32 | 1 | [32, 33]
34 : 2 | 3 | [2, 6]
35 : 1 | 4 | [1, 9]
36 :
37 : The lockout interval is the interval of slots that the validator is
38 : locked out from voting for if they want to switch off that vote. For
39 : example if validator A wants to switch off fork 1, they have to wait
40 : until slot 9.
41 :
42 : Agave tracks a similar structure.
43 :
44 : key: for an interval [vote, vote+lockout] for validator A,
45 : it is stored like:
46 : vote+lockout -> (vote, validator A) -> (2, validator B) -> (any other vote, any other validator)
47 :
48 : Since a validator can have up to 31 entries in the tower, and we have
49 : a max_vote_accounts, we can pool the interval objects to be
50 : 31*max_vote_accounts entries PER bank / executed slot. We can also
51 : string all the intervals of the same bank together as a linkedlist. */
52 :
53 : struct lockout_interval {
54 : ulong key; /* vote_slot (32 bits) | expiration_slot (32 bits) ie. vote_slot + (1 << confirmation count) */
55 : ulong next; /* reserved for fd_map_chain and fd_pool */
56 : fd_hash_t addr; /* vote account address */
57 : ulong start; /* For normal entries: start of interval (vote slot).
58 : For sentinel entries (key has expiration_slot==0):
59 : the interval_end value this sentinel indexes.
60 : Multiple sentinels can exist per slot (one per
61 : unique interval_end), all sharing key (slot, 0)
62 : via MAP_MULTI. */
63 : };
64 : typedef struct lockout_interval lockout_interval_t;
65 :
66 : #define MAP_NAME lockout_interval_map
67 207 : #define MAP_ELE_T lockout_interval_t
68 : #define MAP_MULTI 1
69 279 : #define MAP_KEY key
70 690 : #define MAP_NEXT next
71 : #include "../../util/tmpl/fd_map_chain.c"
72 :
73 : #define POOL_NAME lockout_interval_pool
74 108 : #define POOL_T lockout_interval_t
75 1700835 : #define POOL_NEXT next
76 : #include "../../util/tmpl/fd_pool.c"
77 :
78 : FD_FN_PURE static inline ulong
79 825 : lockout_interval_key( ulong fork_slot, ulong end_interval ) {
80 825 : return (fork_slot << 32) | end_interval;
81 825 : }
82 :
83 0 : #define THRESHOLD_DEPTH (8)
84 0 : #define THRESHOLD_RATIO (2.0 / 3.0)
85 : #define SWITCH_RATIO (0.38)
86 :
87 : ulong
88 477 : fd_tower_align( void ) {
89 477 : return 128UL;
90 477 : }
91 :
92 : ulong
93 : fd_tower_footprint( ulong blk_max,
94 99 : ulong vtr_max ) {
95 99 : ulong lck_interval_max = fd_ulong_pow2_up( FD_TOWER_LOCKOS_MAX*blk_max*vtr_max );
96 99 : ulong lck_pool_max = fd_ulong_pow2_up( 2UL * lck_interval_max );
97 :
98 99 : ulong stk_vtr_chain_cnt = fd_tower_stakes_vtr_map_chain_cnt_est( vtr_max * blk_max );
99 99 : int stk_lg_slot_cnt = fd_ulong_find_msb( fd_ulong_pow2_up( blk_max ) ) + 1;
100 :
101 99 : ulong l = FD_LAYOUT_INIT;
102 99 : l = FD_LAYOUT_APPEND( l, 128UL, sizeof(fd_tower_t) );
103 99 : l = FD_LAYOUT_APPEND( l, fd_tower_vote_align(), fd_tower_vote_footprint() );
104 99 : l = FD_LAYOUT_APPEND( l, blk_pool_align(), blk_pool_footprint ( blk_max ) );
105 99 : l = FD_LAYOUT_APPEND( l, blk_map_align(), blk_map_footprint ( blk_map_chain_cnt_est( blk_max ) ) );
106 99 : l = FD_LAYOUT_APPEND( l, fd_tower_vtr_align(), fd_tower_vtr_footprint ( vtr_max ) );
107 981 : for( ulong i = 0; i < vtr_max; i++ ) {
108 882 : l = FD_LAYOUT_APPEND( l, fd_tower_vote_align(), fd_tower_vote_footprint() );
109 882 : }
110 : /* lockos */
111 99 : l = FD_LAYOUT_APPEND( l, lockout_interval_pool_align(), lockout_interval_pool_footprint( lck_pool_max ) );
112 99 : l = FD_LAYOUT_APPEND( l, lockout_interval_map_align(), lockout_interval_map_footprint ( lck_pool_max ) );
113 : /* stakes */
114 99 : l = FD_LAYOUT_APPEND( l, fd_tower_stakes_vtr_map_align(), fd_tower_stakes_vtr_map_footprint ( stk_vtr_chain_cnt ) );
115 99 : l = FD_LAYOUT_APPEND( l, fd_tower_stakes_vtr_pool_align(), fd_tower_stakes_vtr_pool_footprint( vtr_max * blk_max ) );
116 99 : l = FD_LAYOUT_APPEND( l, fd_tower_stakes_slot_align(), fd_tower_stakes_slot_footprint( stk_lg_slot_cnt ) );
117 99 : l = FD_LAYOUT_APPEND( l, fd_used_acc_scratch_align(), fd_used_acc_scratch_footprint( vtr_max * blk_max ) );
118 99 : return FD_LAYOUT_FINI( l, fd_tower_align() );
119 99 : }
120 :
121 : void *
122 : fd_tower_new( void * shmem,
123 : ulong blk_max,
124 : ulong vtr_max,
125 54 : ulong seed ) {
126 :
127 54 : if( FD_UNLIKELY( !shmem ) ) {
128 0 : FD_LOG_WARNING(( "NULL mem" ));
129 0 : return NULL;
130 0 : }
131 :
132 54 : if( FD_UNLIKELY( !fd_ulong_is_aligned( (ulong)shmem, fd_tower_align() ) ) ) {
133 0 : FD_LOG_WARNING(( "misaligned mem" ));
134 0 : return NULL;
135 0 : }
136 :
137 54 : ulong footprint = fd_tower_footprint( blk_max, vtr_max );
138 54 : if( FD_UNLIKELY( !footprint ) ) {
139 0 : FD_LOG_WARNING(( "bad blk_max (%lu) or vtr_max (%lu)", blk_max, vtr_max ));
140 0 : return NULL;
141 0 : }
142 :
143 54 : fd_memset( shmem, 0, footprint );
144 :
145 54 : ulong lck_interval_max = fd_ulong_pow2_up( FD_TOWER_LOCKOS_MAX*blk_max*vtr_max );
146 54 : ulong lck_pool_max = fd_ulong_pow2_up( 2UL * lck_interval_max );
147 :
148 54 : ulong stk_vtr_chain_cnt = fd_tower_stakes_vtr_map_chain_cnt_est( vtr_max * blk_max );
149 54 : int stk_lg_slot_cnt = fd_ulong_find_msb( fd_ulong_pow2_up( blk_max ) ) + 1;
150 :
151 54 : FD_SCRATCH_ALLOC_INIT( l, shmem );
152 54 : fd_tower_t * tower = FD_SCRATCH_ALLOC_APPEND( l, 128UL, sizeof(fd_tower_t) );
153 54 : void * votes = FD_SCRATCH_ALLOC_APPEND( l, fd_tower_vote_align(), fd_tower_vote_footprint() );
154 54 : void * blk_pool = FD_SCRATCH_ALLOC_APPEND( l, blk_pool_align(), blk_pool_footprint ( blk_max ) );
155 54 : void * blk_map = FD_SCRATCH_ALLOC_APPEND( l, blk_map_align(), blk_map_footprint ( blk_map_chain_cnt_est( blk_max ) ) );
156 54 : void * vtrs = FD_SCRATCH_ALLOC_APPEND( l, fd_tower_vtr_align(), fd_tower_vtr_footprint ( vtr_max ) );
157 54 : void * towers[ vtr_max ];
158 504 : for( ulong i = 0; i < vtr_max; i++ ) {
159 450 : towers[i] = FD_SCRATCH_ALLOC_APPEND( l, fd_tower_vote_align(), fd_tower_vote_footprint() );
160 450 : }
161 54 : void * lck_pool_mem = FD_SCRATCH_ALLOC_APPEND( l, lockout_interval_pool_align(), lockout_interval_pool_footprint( lck_pool_max ) );
162 54 : void * lck_map_mem = FD_SCRATCH_ALLOC_APPEND( l, lockout_interval_map_align(), lockout_interval_map_footprint ( lck_pool_max ) );
163 54 : void * stk_vtr_map = FD_SCRATCH_ALLOC_APPEND( l, fd_tower_stakes_vtr_map_align(), fd_tower_stakes_vtr_map_footprint ( stk_vtr_chain_cnt ) );
164 54 : void * stk_vtr_pool = FD_SCRATCH_ALLOC_APPEND( l, fd_tower_stakes_vtr_pool_align(), fd_tower_stakes_vtr_pool_footprint( vtr_max * blk_max ) );
165 54 : void * stk_slot_map = FD_SCRATCH_ALLOC_APPEND( l, fd_tower_stakes_slot_align(), fd_tower_stakes_slot_footprint( stk_lg_slot_cnt ) );
166 54 : void * stk_used_acc = FD_SCRATCH_ALLOC_APPEND( l, fd_used_acc_scratch_align(), fd_used_acc_scratch_footprint( vtr_max * blk_max ) );
167 54 : FD_TEST( FD_SCRATCH_ALLOC_FINI( l, fd_tower_align() ) == (ulong)shmem + footprint );
168 :
169 54 : tower->root = ULONG_MAX;
170 54 : tower->blk_max = blk_max;
171 54 : tower->vtr_max = vtr_max;
172 54 : tower->votes = fd_tower_vote_new( votes );
173 54 : tower->blk_pool = blk_pool_new( blk_pool, blk_max );
174 54 : tower->blk_map = blk_map_new( blk_map, blk_map_chain_cnt_est( blk_max ), seed );
175 54 : tower->vtrs = fd_tower_vtr_new( vtrs, vtr_max );
176 504 : for( ulong i = 0; i < vtr_max; i++ ) {
177 450 : fd_tower_vtr_join( tower->vtrs )[i].votes = fd_tower_vote_new( towers[i] );
178 450 : }
179 :
180 54 : tower->lck_pool = lockout_interval_pool_new( lck_pool_mem, lck_pool_max );
181 54 : tower->lck_map = lockout_interval_map_new ( lck_map_mem, lck_pool_max, seed );
182 54 : tower->stk_vtr_map = fd_tower_stakes_vtr_map_new ( stk_vtr_map, stk_vtr_chain_cnt, seed );
183 54 : tower->stk_vtr_pool = fd_tower_stakes_vtr_pool_new( stk_vtr_pool, vtr_max * blk_max );
184 54 : tower->stk_slot_map = fd_tower_stakes_slot_new ( stk_slot_map, stk_lg_slot_cnt, seed );
185 54 : tower->stk_used_acc = fd_used_acc_scratch_new ( stk_used_acc, vtr_max * blk_max );
186 :
187 54 : return shmem;
188 54 : }
189 :
190 : fd_tower_t *
191 54 : fd_tower_join( void * shtower ) {
192 54 : fd_tower_t * tower = (fd_tower_t *)shtower;
193 :
194 54 : if( FD_UNLIKELY( !tower ) ) {
195 0 : FD_LOG_WARNING(( "NULL tower" ));
196 0 : return NULL;
197 0 : }
198 :
199 54 : if( FD_UNLIKELY( !fd_ulong_is_aligned( (ulong)tower, fd_tower_align() ) ) ) {
200 0 : FD_LOG_WARNING(( "misaligned tower" ));
201 0 : return NULL;
202 0 : }
203 :
204 54 : tower->votes = fd_tower_vote_join( tower->votes );
205 54 : tower->blk_pool = blk_pool_join ( tower->blk_pool );
206 54 : tower->blk_map = blk_map_join ( tower->blk_map );
207 54 : tower->vtrs = fd_tower_vtr_join ( tower->vtrs );
208 504 : for( ulong i = 0; i < tower->vtr_max; i++ ) {
209 450 : tower->vtrs[i].votes = fd_tower_vote_join( tower->vtrs[i].votes );
210 450 : }
211 54 : tower->lck_pool = lockout_interval_pool_join( tower->lck_pool );
212 54 : tower->lck_map = lockout_interval_map_join ( tower->lck_map );
213 54 : tower->stk_vtr_map = fd_tower_stakes_vtr_map_join ( tower->stk_vtr_map );
214 54 : tower->stk_vtr_pool = fd_tower_stakes_vtr_pool_join( tower->stk_vtr_pool );
215 54 : tower->stk_slot_map = fd_tower_stakes_slot_join ( tower->stk_slot_map );
216 54 : tower->stk_used_acc = fd_used_acc_scratch_join ( tower->stk_used_acc );
217 :
218 54 : return tower;
219 54 : }
220 :
221 : void *
222 18 : fd_tower_leave( fd_tower_t const * tower ) {
223 :
224 18 : if( FD_UNLIKELY( !tower ) ) {
225 0 : FD_LOG_WARNING(( "NULL tower" ));
226 0 : return NULL;
227 0 : }
228 :
229 18 : return (void *)tower;
230 18 : }
231 :
232 : void *
233 18 : fd_tower_delete( void * shtower ) {
234 :
235 18 : if( FD_UNLIKELY( !shtower ) ) {
236 0 : FD_LOG_WARNING(( "NULL tower" ));
237 0 : return NULL;
238 0 : }
239 :
240 18 : if( FD_UNLIKELY( !fd_ulong_is_aligned( (ulong)shtower, fd_tower_align() ) ) ) {
241 0 : FD_LOG_WARNING(( "misaligned tower" ));
242 0 : return NULL;
243 0 : }
244 :
245 18 : return shtower;
246 18 : }
247 :
248 : /* expiration calculates the expiration slot of vote given a slot and
249 : confirmation count. */
250 :
251 : static inline ulong
252 270 : expiration_slot( fd_tower_vote_t const * vote ) {
253 270 : ulong lockout = 1UL << vote->conf;
254 270 : return vote->slot + lockout;
255 270 : }
256 :
257 : /* simulate_vote simulates voting for slot, popping all votes from the
258 : top that would be consecutively expired by voting for slot. */
259 :
260 : static ulong
261 : simulate_vote( fd_tower_vote_t const * votes,
262 297 : ulong slot ) {
263 297 : ulong cnt = fd_tower_vote_cnt( votes );
264 315 : while( cnt ) {
265 270 : fd_tower_vote_t const * top_vote = fd_tower_vote_peek_index_const( votes, cnt - 1 );
266 270 : if( FD_LIKELY( expiration_slot( top_vote ) >= slot ) ) break; /* expire only if consecutive */
267 18 : cnt--;
268 18 : }
269 297 : return cnt;
270 297 : }
271 :
272 : /* push_vote pushes a new vote for slot onto the tower. Pops and
273 : returns the new root (bottom of the tower) if it reaches max lockout
274 : as a result of the new vote. Otherwise, returns ULONG_MAX.
275 :
276 : Max lockout is equivalent to 1 << FD_TOWER_VOTE_MAX + 1 (which
277 : implies confirmation count is FD_TOWER_VOTE_MAX + 1). As a result,
278 : fd_tower_vote also maintains the invariant that the tower contains at
279 : most FD_TOWER_VOTE_MAX votes, because (in addition to vote expiry)
280 : there will always be a pop before reaching FD_TOWER_VOTE_MAX + 1. */
281 :
282 : static ulong
283 : push_vote( fd_tower_t * tower,
284 291 : ulong slot ) {
285 :
286 : /* Sanity check: slot should always be greater than previous vote slot in tower. */
287 :
288 291 : fd_tower_vote_t const * vote = fd_tower_vote_peek_tail_const( tower->votes );
289 291 : if( FD_UNLIKELY( vote && slot <= vote->slot ) ) FD_LOG_CRIT(( "[%s] slot %lu <= vote->slot %lu", __func__, slot, vote->slot ));
290 :
291 : /* Use simulate_vote to determine how many expired votes to pop. */
292 :
293 291 : ulong cnt = simulate_vote( tower->votes, slot );
294 :
295 : /* Pop everything that got expired. */
296 :
297 306 : while( FD_LIKELY( fd_tower_vote_cnt( tower->votes ) > cnt ) ) {
298 15 : fd_tower_vote_pop_tail( tower->votes );
299 15 : }
300 :
301 : /* If the tower is still full after expiring, then pop and return the
302 : bottom vote slot as the new root because this vote has incremented
303 : it to max lockout. Otherwise this is a no-op and there is no new
304 : root (ULONG_MAX). */
305 :
306 291 : ulong root = ULONG_MAX;
307 291 : if( FD_LIKELY( fd_tower_vote_full( tower->votes ) ) ) { /* optimize for full tower */
308 3 : root = fd_tower_vote_pop_head( tower->votes ).slot;
309 3 : }
310 :
311 : /* Increment confirmations (double lockouts) for consecutive
312 : confirmations in prior votes. */
313 :
314 291 : ulong prev_conf = 0;
315 291 : for( fd_tower_vote_iter_t iter = fd_tower_vote_iter_init_rev( tower->votes );
316 3321 : !fd_tower_vote_iter_done_rev( tower->votes, iter );
317 3033 : iter = fd_tower_vote_iter_prev ( tower->votes, iter ) ) {
318 3033 : fd_tower_vote_t * vote = fd_tower_vote_iter_ele( tower->votes, iter );
319 3033 : if( FD_UNLIKELY( vote->conf != ++prev_conf ) ) break;
320 3030 : vote->conf++;
321 3030 : }
322 :
323 : /* Add the new vote to the tower. */
324 :
325 291 : fd_tower_vote_push_tail( tower->votes, (fd_tower_vote_t){ .slot = slot, .conf = 1 } );
326 :
327 : /* Return the new root (FD_SLOT_NULL if there is none). */
328 :
329 291 : return root;
330 291 : }
331 :
332 : /* lockout_check checks if we are locked out from voting for slot.
333 : Returns 1 if we can vote for slot without violating lockout, 0
334 : otherwise.
335 :
336 : After voting for a slot n, we are locked out for 2^k slots, where k
337 : is the confirmation count of that vote. Once locked out, we cannot
338 : vote for a different fork until that previously-voted fork expires at
339 : slot n+2^k. This implies the earliest slot in which we can switch
340 : from the previously-voted fork is (n+2^k)+1. We use `ghost` to
341 : determine whether `slot` is on the same or different fork as previous
342 : vote slots.
343 :
344 : In the case of the tower, every vote has its own expiration slot
345 : depending on confirmations. The confirmation count is the max number
346 : of consecutive votes that have been pushed on top of the vote, and
347 : not necessarily its current height in the tower.
348 :
349 : For example, the following is a diagram of a tower pushing and
350 : popping with each vote:
351 :
352 :
353 : slot | confirmation count
354 : -----|-------------------
355 : 4 | 1 <- vote
356 : 3 | 2
357 : 2 | 3
358 : 1 | 4
359 :
360 :
361 : slot | confirmation count
362 : -----|-------------------
363 : 9 | 1 <- vote
364 : 2 | 3
365 : 1 | 4
366 :
367 :
368 : slot | confirmation count
369 : -----|-------------------
370 : 10 | 1 <- vote
371 : 9 | 2
372 : 2 | 3
373 : 1 | 4
374 :
375 :
376 : slot | confirmation count
377 : -----|-------------------
378 : 11 | 1 <- vote
379 : 10 | 2
380 : 9 | 3
381 : 2 | 4
382 : 1 | 5
383 :
384 :
385 : slot | confirmation count
386 : -----|-------------------
387 : 18 | 1 <- vote
388 : 2 | 4
389 : 1 | 5
390 :
391 :
392 : In the final tower, note the gap in confirmation counts between slot
393 : 18 and slot 2, even though slot 18 is directly above slot 2. */
394 :
395 : static int
396 : lockout_check( fd_tower_t * tower,
397 3 : ulong slot ) {
398 :
399 : /* Mirrors Agave's Tower::is_recent(): reject slot if it is not strictly
400 : newer than our last vote (non-empty tower) or our root (empty tower,
401 : e.g. snapshot boot).
402 : https://github.com/anza-xyz/agave/blob/v4.0.0-alpha.0/core/src/consensus.rs#L825-L836 */
403 3 : if( FD_UNLIKELY( fd_tower_vote_empty( tower->votes ) ) )
404 0 : return tower->root==ULONG_MAX || slot>tower->root;
405 3 : if( FD_UNLIKELY( slot<=fd_tower_vote_peek_tail_const( tower->votes )->slot ) ) return 0;
406 :
407 : /* Simulate a vote to pop off all the votes that would be expired by
408 : voting for slot. Then check if the newly top-of-tower vote is on
409 : the same fork as slot (if so this implies we can vote for it). */
410 :
411 3 : ulong cnt = simulate_vote( tower->votes, slot ); /* pop off votes that would be expired */
412 3 : if( FD_UNLIKELY( !cnt ) ) return 1; /* tower is empty after popping expired votes */
413 :
414 3 : fd_tower_vote_t const * vote = fd_tower_vote_peek_index_const( tower->votes, cnt - 1 ); /* newly top-of-tower */
415 3 : int lockout = fd_tower_blocks_is_slot_descendant( tower, vote->slot, slot ); /* check if on same fork */
416 3 : return lockout;
417 3 : }
418 :
419 : /* switch_check checks if we can switch to the fork of `slot`. Returns
420 : 1 if we can switch, 0 otherwise. Assumes tower is non-empty.
421 :
422 : There are two forks of interest: our last vote fork ("vote fork") and
423 : the fork we want to switch to ("switch fork"). The switch fork is on
424 : the fork of `slot`.
425 :
426 : In order to switch, SWITCH_RATIO of stake must have voted for
427 : a slot that satisfies the following conditions: the
428 : GCA(slot, last_vote) is an ancestor of the switch_slot
429 :
430 : Recall from the lockout check a validator is locked out from voting
431 : for our last vote slot when their last vote slot is on a different
432 : fork, and that vote's expiration slot > our last vote slot.
433 :
434 : The following pseudocode describes the algorithm:
435 :
436 : ```
437 : for every fork f in the fork tree, take the most recently executed
438 : slot `s` (the leaf of the fork).
439 :
440 : Take the greatest common ancestor of the `s` and the our last vote
441 : slot. If the switch_slot is a descendant of this GCA, then votes for
442 : `s` can count towards the switch threshold.
443 :
444 : query banks(`s`) for vote accounts in `s`
445 : for all vote accounts v in `s`
446 : if v's locked out[1] from voting for our latest vote slot
447 : add v's stake to switch stake
448 :
449 : return switch stake >= total_stake * SWITCH_RATIO
450 : ```
451 :
452 : The switch check is used to safeguard optimistic confirmation.
453 : Specifically: optimistic confirmation pct + SWITCH_RATIO >= 1. */
454 :
455 : static int
456 : is_purged( fd_tower_t * tower,
457 543 : fd_ghost_blk_t * blk ) {
458 543 : fd_tower_blk_t * tower_blk = fd_tower_blocks_query( tower, blk->slot );
459 543 : return tower_blk->confirmed && memcmp( &tower_blk->confirmed_block_id, &blk->id, sizeof(fd_hash_t) );
460 543 : }
461 :
462 : static int
463 : switch_check( fd_tower_t * tower,
464 : fd_ghost_t * ghost,
465 : ulong total_stake,
466 51 : ulong switch_slot ) {
467 :
468 51 : lockout_interval_map_t * lck_map = tower->lck_map;
469 51 : lockout_interval_t * lck_pool = tower->lck_pool;
470 :
471 51 : ulong switch_stake = 0;
472 51 : ulong vote_slot = fd_tower_vote_peek_tail_const( tower->votes )->slot;
473 51 : ulong root_slot = tower->root;
474 :
475 51 : ulong null = fd_ghost_blk_idx_null( ghost );
476 51 : fd_ghost_blk_t * head = fd_ghost_blk_map_remove( ghost, fd_ghost_root( ghost ) );
477 51 : fd_ghost_blk_t * tail = head;
478 51 : head->next = null;
479 :
480 591 : while( FD_LIKELY( head ) ) {
481 564 : fd_ghost_blk_t * blk = head; /* guaranteed to not be purged */
482 :
483 : /* Because agave has particular behavior where if they replay a
484 : equivocating version of a slot and then the correct version, the
485 : original version and all of it's children get purged from all
486 : structures. None of the nodes on this subtree can be considered
487 : for the switch proof. Note that this means as we BFS, a node
488 : can be considered a "valid leaf" if either it has no children,
489 : or if all of it's children are purged/superseded slots. We
490 : detect this by comparing against tower_blocks confirmed. */
491 :
492 564 : int is_valid_leaf = 1;
493 564 : fd_ghost_blk_t * child = fd_ghost_blk_child( ghost, head );
494 1107 : while( FD_LIKELY( child ) ) {
495 543 : if( FD_LIKELY( !is_purged( tower, child ) ) ) {
496 537 : fd_ghost_blk_map_remove( ghost, child );
497 537 : tail->next = fd_ghost_blk_idx( ghost, child );
498 537 : tail = child;
499 537 : tail->next = null;
500 537 : is_valid_leaf = 0;
501 537 : }
502 543 : child = fd_ghost_blk_sibling( ghost, child );
503 543 : }
504 :
505 564 : head = fd_ghost_blk_next( ghost, blk ); /* pop queue head */
506 564 : fd_ghost_blk_map_insert( ghost, blk ); /* re-insert into map */
507 :
508 564 : if( FD_UNLIKELY( !is_valid_leaf ) ) continue; /* not a real candidate */
509 :
510 147 : ulong candidate_slot = blk->slot;
511 147 : ulong lca = fd_tower_blocks_lowest_common_ancestor( tower, candidate_slot, vote_slot );
512 147 : if( FD_UNLIKELY( candidate_slot == vote_slot ) ) continue;
513 132 : if( FD_UNLIKELY( lca==ULONG_MAX ) ) continue; /* unlikely but this leaf is an already pruned minority fork */
514 :
515 132 : if( FD_UNLIKELY( fd_tower_blocks_is_slot_descendant( tower, lca, switch_slot ) ) ) {
516 :
517 : /* This candidate slot may be considered for the switch proof, if
518 : it passes the following conditions:
519 :
520 : https://github.com/anza-xyz/agave/blob/c7b97bc77addacf03b229c51b47c18650d909576/core/src/consensus.rs#L1117
521 :
522 : Now for this candidate slot, look at the lockouts that were
523 : created at the time that we processed the bank for this
524 : candidate slot. */
525 :
526 111 : ulong sentinel_key = lockout_interval_key( candidate_slot, 0 );
527 111 : for( lockout_interval_t const * sentinel = lockout_interval_map_ele_query_const( lck_map, &sentinel_key, NULL, lck_pool );
528 120 : sentinel;
529 111 : sentinel = lockout_interval_map_ele_next_const( sentinel, NULL, lck_pool ) ) {
530 33 : ulong interval_end = sentinel->start;
531 33 : ulong key = lockout_interval_key( candidate_slot, interval_end );
532 :
533 : /* Intervals are keyed by the end of the interval. If the end of
534 : the interval is < the last vote slot, then these vote
535 : accounts with this particular lockout are NOT locked out from
536 : voting for the last vote slot, which means we can skip this
537 : set of intervals. */
538 :
539 33 : if( FD_LIKELY( interval_end < vote_slot ) ) continue;
540 :
541 : /* At this point we can actually query for the intervals by
542 : end interval to get the vote accounts. */
543 :
544 27 : for( lockout_interval_t const * interval = lockout_interval_map_ele_query_const( lck_map, &key, NULL, lck_pool );
545 39 : interval;
546 36 : interval = lockout_interval_map_ele_next_const( interval, NULL, lck_pool ) ) {
547 36 : ulong interval_slot = interval->start;
548 36 : fd_hash_t const * vote_acc = &interval->addr;
549 :
550 36 : if( FD_UNLIKELY( !fd_tower_blocks_is_slot_descendant( tower, interval_slot, vote_slot ) && interval_slot > root_slot ) ) {
551 33 : fd_tower_stakes_vtr_xid_t key = { .addr = *vote_acc, .slot = switch_slot };
552 33 : fd_tower_stakes_vtr_t const * voter_stake = fd_tower_stakes_vtr_map_ele_query_const( tower->stk_vtr_map, &key, NULL, tower->stk_vtr_pool );
553 :
554 : /* Vote account could have been closed on the switch fork,
555 : and therefore not in the tower stakes map. In this case
556 : just count the vote stake as 0 and skip this voter.
557 : matches Agave. */
558 33 : if( FD_UNLIKELY( !voter_stake ) ) continue;
559 33 : ulong voter_idx = fd_tower_stakes_vtr_pool_idx( tower->stk_vtr_pool, voter_stake );
560 33 : if( FD_UNLIKELY( fd_used_acc_scratch_test( tower->stk_used_acc, voter_idx ) ) ) continue; /* exclude already counted voters */
561 33 : fd_used_acc_scratch_insert( tower->stk_used_acc, voter_idx );
562 33 : switch_stake += voter_stake->stake;
563 33 : if( FD_LIKELY( (double)switch_stake / (double)total_stake > SWITCH_RATIO ) ) {
564 24 : fd_used_acc_scratch_null( tower->stk_used_acc );
565 24 : FD_LOG_DEBUG(( "[%s] vote_slot: %lu. switch_slot: %lu. pct: %.0lf%%", __func__, vote_slot, switch_slot, (double)switch_stake / (double)total_stake * 100.0 ));
566 48 : while( FD_LIKELY( head ) ) { /* cleanup: re-insert remaining BFS queue into map */
567 24 : fd_ghost_blk_t * next = fd_ghost_blk_next( ghost, head );
568 24 : fd_ghost_blk_map_insert( ghost, head );
569 24 : head = next;
570 24 : }
571 24 : return 1;
572 24 : }
573 33 : }
574 36 : }
575 27 : }
576 111 : }
577 132 : }
578 27 : fd_used_acc_scratch_null( tower->stk_used_acc );
579 27 : FD_LOG_DEBUG(( "[%s] vote_slot: %lu. switch_slot: %lu. pct: %.0lf%%", __func__, vote_slot, switch_slot, (double)switch_stake / (double)total_stake * 100.0 ));
580 27 : return 0;
581 51 : }
582 :
583 : /* threshold_check checks if we pass the threshold required to vote for
584 : `slot`. Returns 1 if we pass the threshold check, 0 otherwise.
585 :
586 : The following psuedocode describes the algorithm:
587 :
588 : ```
589 : simulate that we have voted for `slot`
590 :
591 : for all vote accounts in the current epoch
592 :
593 : simulate that the vote account has voted for `slot`
594 :
595 : pop all votes expired by that simulated vote
596 :
597 : if the validator's latest tower vote after expiry >= our threshold
598 : slot ie. our vote from THRESHOLD_DEPTH back also after simulating,
599 : then add validator's stake to threshold_stake.
600 :
601 : return threshold_stake >= FD_TOWER_THRESHOLD_RATIO
602 : ```
603 :
604 : The threshold check simulates voting for the current slot to expire
605 : stale votes. This is to prevent validators that haven't voted in a
606 : long time from counting towards the threshold stake. */
607 :
608 : static int
609 : threshold_check( fd_tower_t const * tower,
610 : fd_tower_vtr_t const * accts,
611 : ulong total_stake,
612 0 : ulong slot ) {
613 :
614 : /* First, simulate a vote on our tower, popping off everything that
615 : would be expired by voting for slot. */
616 :
617 0 : ulong cnt = simulate_vote( tower->votes, slot );
618 :
619 : /* We can always vote if our tower is not at least THRESHOLD_DEPTH
620 : deep after simulating. */
621 :
622 0 : if( FD_UNLIKELY( cnt < THRESHOLD_DEPTH ) ) return 1;
623 :
624 : /* Get the vote slot from THRESHOLD_DEPTH back. Note THRESHOLD_DEPTH
625 : is the 8th index back _including_ the simulated vote at index 0. */
626 :
627 0 : ulong threshold_slot = fd_tower_vote_peek_index_const( tower->votes, cnt - THRESHOLD_DEPTH )->slot;
628 0 : ulong threshold_stake = 0;
629 0 : for( fd_tower_vtr_iter_t iter = fd_tower_vtr_iter_init( accts );
630 0 : !fd_tower_vtr_iter_done( accts, iter );
631 0 : iter = fd_tower_vtr_iter_next( accts, iter ) ) {
632 0 : fd_tower_vtr_t const * acct = fd_tower_vtr_iter_ele_const( accts, iter );
633 :
634 0 : ulong cnt = simulate_vote( acct->votes, slot ); /* expire votes */
635 0 : if( FD_UNLIKELY( !cnt ) ) continue; /* no votes left after expiry */
636 :
637 : /* Count their stake towards the threshold check if their prev vote
638 : slot >= our threshold slot.
639 :
640 : We know their prev vote slot is definitely on the same fork as
641 : our threshold slot, because these towers are sourced from vote
642 : _accounts_, not vote _transactions_ and the Vote Program
643 : validates that all slots in the vote account's tower exist on the
644 : current fork.
645 :
646 : Therefore, if their prev vote slot >= our threshold slot, we know
647 : that vote must be for the threshold slot itself or one of
648 : threshold slot's descendants. */
649 :
650 0 : ulong vote_slot = fd_tower_vote_peek_index_const( acct->votes, cnt - 1 )->slot;
651 0 : if( FD_LIKELY( vote_slot >= threshold_slot ) ) threshold_stake += acct->stake;
652 0 : }
653 :
654 0 : double threshold_pct = (double)threshold_stake / (double)total_stake;
655 0 : int threshold = threshold_pct > THRESHOLD_RATIO;
656 0 : if( FD_UNLIKELY( !threshold ) ) FD_LOG_DEBUG(( "[%s] vote_slot: %lu. threshold_slot: %lu. pct: %.0lf%%.", __func__, fd_tower_vote_peek_tail_const( tower->votes )->slot, threshold_slot, threshold_pct * 100.0 ));
657 0 : return threshold;
658 0 : }
659 :
660 : static int
661 : propagated_check( fd_tower_t * tower,
662 0 : ulong slot ) {
663 :
664 0 : fd_tower_blk_t * blk = fd_tower_blocks_query( tower, slot );
665 0 : FD_TEST( blk );
666 :
667 0 : if( FD_LIKELY( blk->leader ) ) return 1; /* can always vote for slot in which we're leader */
668 0 : if( FD_LIKELY( blk->prev_leader_slot==ULONG_MAX ) ) return 1; /* haven't been leader yet */
669 :
670 0 : fd_tower_blk_t * prev_leader_blk = fd_tower_blocks_query( tower, blk->prev_leader_slot );
671 0 : if( FD_LIKELY( !prev_leader_blk ) ) return 1; /* already pruned / rooted */
672 :
673 0 : return prev_leader_blk->propagated;
674 0 : }
675 :
676 : uchar
677 : fd_tower_vote_and_reset( fd_tower_t * tower,
678 : fd_ghost_t * ghost,
679 : fd_votes_t * votes FD_PARAM_UNUSED,
680 : ulong * reset_slot,
681 : fd_hash_t * reset_block_id,
682 : ulong * vote_slot,
683 : fd_hash_t * vote_block_id,
684 : fd_hash_t * vote_bank_hash,
685 : ulong * root_slot,
686 6 : fd_hash_t * root_block_id ) {
687 :
688 6 : uchar flags = 0;
689 6 : fd_ghost_blk_t const * best_blk = fd_ghost_best( ghost, fd_ghost_root( ghost ) );
690 6 : fd_ghost_blk_t const * reset_blk = NULL;
691 6 : fd_ghost_blk_t const * vote_blk = NULL;
692 :
693 : /* Case 0: if we haven't voted yet then there are two subcases where
694 : we short-circuit. */
695 :
696 : /* Case 0a: on boot, tower->root is set to the snapshot slot before
697 : any votes are recorded. In this case, lockout_check returns 0 for
698 : slot <= root, preventing a vote on the snapshot slot itself. */
699 :
700 : /* TODO refactor: 0a is a tile-concern not logic-concern */
701 :
702 6 : if( FD_UNLIKELY( fd_tower_vote_empty( tower->votes ) && !lockout_check( tower, best_blk->slot ) ) ) {
703 0 : FD_BASE58_ENCODE_32_BYTES( best_blk->id.uc, best_blk_id );
704 0 : FD_LOG_DEBUG(( "[%s] case 0a: not recent (slot %lu <= root %lu). reset_blk: (%lu, %s). vote_blk: (NULL)", __func__, best_blk->slot, tower->root, best_blk->slot, best_blk_id ));
705 0 : *reset_slot = best_blk->slot;
706 0 : *reset_block_id = best_blk->id;
707 0 : *vote_slot = ULONG_MAX;
708 0 : *vote_block_id = (fd_hash_t){0};
709 0 : *root_slot = ULONG_MAX;
710 0 : *root_block_id = (fd_hash_t){0};
711 0 : return flags;
712 0 : }
713 :
714 : /* Case 0b: if we haven't voted yet then we can always vote and reset
715 : to ghost_best. */
716 :
717 6 : if( FD_UNLIKELY( fd_tower_vote_empty( tower->votes ) ) ) {
718 0 : FD_BASE58_ENCODE_32_BYTES( best_blk->id.uc, best_blk_id );
719 0 : FD_LOG_DEBUG(( "[%s] case 0b: empty tower. reset_blk: (%lu, %s). vote_blk: (%lu, %s)", __func__, best_blk->slot, best_blk_id, best_blk->slot, best_blk_id ));
720 0 : fd_tower_blk_t * tower_blk = fd_tower_blocks_query( tower, best_blk->slot );
721 0 : tower_blk->voted = 1;
722 0 : tower_blk->voted_block_id = best_blk->id;
723 0 : *reset_slot = best_blk->slot;
724 0 : *reset_block_id = best_blk->id;
725 0 : *vote_slot = best_blk->slot;
726 0 : *vote_block_id = best_blk->id;
727 0 : *vote_bank_hash = tower_blk->bank_hash;
728 0 : *root_slot = push_vote( tower, best_blk->slot );
729 0 : *root_block_id = ( fd_hash_t ){ 0 };
730 0 : return flags;
731 0 : }
732 :
733 6 : ulong prev_vote_slot = fd_tower_vote_peek_tail_const( tower->votes )->slot;
734 6 : fd_tower_blk_t * prev_vote_fork = fd_tower_blocks_query( tower, prev_vote_slot ); /* must exist */
735 :
736 6 : fd_hash_t * prev_vote_block_id = &prev_vote_fork->voted_block_id;
737 6 : fd_ghost_blk_t * prev_vote_blk = fd_ghost_query( ghost, prev_vote_block_id );
738 :
739 : /* Case 1: if any ancestor of our prev vote (including prev vote
740 : itself) is an unconfirmed duplicate, then our prev vote was on a
741 : duplicate fork.
742 :
743 : There are three subcases to check. */
744 :
745 6 : int invalid_ancestor = !!fd_ghost_invalid_ancestor( ghost, prev_vote_blk );
746 :
747 : /* Case 1a: ghost_best is an ancestor of prev vote. This means
748 : ghost_best is rolling back to an ancestor that precedes the
749 : duplicate ancestor on the same fork as our prev vote. In this
750 : case, we can't vote on our ancestor, but we do reset to that
751 : ancestor.
752 :
753 : https://github.com/anza-xyz/agave/blob/v2.3.7/core/src/consensus.rs#L1016-L1019 */
754 :
755 6 : int ancestor_rollback = prev_vote_blk != best_blk && !!fd_ghost_ancestor( ghost, prev_vote_blk, &best_blk->id );
756 :
757 : /* Case 1b: ghost_best is not an ancestor, but prev_vote is a
758 : duplicate and we've confirmed its duplicate sibling. In this
759 : case, we allow switching to ghost_best without a switch proof.
760 :
761 : Example: slot 5 is a duplicate. We first receive, replay and
762 : vote for block 5, so that is our prev vote. We later receive
763 : block 5' and observe that it is duplicate confirmed. ghost_best
764 : now returns block 5' and we both vote and reset to block 5'
765 : regardless of the switch check.
766 :
767 : https://github.com/anza-xyz/agave/blob/v2.3.7/core/src/consensus.rs#L1021-L1024 */
768 :
769 6 : int sibling_confirmed = prev_vote_fork->confirmed && 0!=memcmp( &prev_vote_fork->voted_block_id, &prev_vote_fork->confirmed_block_id, sizeof(fd_hash_t) );
770 :
771 6 : if( FD_UNLIKELY( invalid_ancestor && ancestor_rollback ) ) {
772 0 : flags = fd_uchar_set_bit( flags, FD_TOWER_FLAG_ANCESTOR_ROLLBACK );
773 0 : reset_blk = best_blk;
774 0 : FD_BASE58_ENCODE_32_BYTES( reset_blk->id.uc, reset_blk_id );
775 0 : FD_LOG_DEBUG(( "[%s] case 1a: ancestor rollback. prev_vote_slot: %lu. reset_blk: (%lu, %s). vote_blk: (NULL)", __func__, prev_vote_slot, reset_blk->slot, reset_blk_id ));
776 :
777 6 : } else if( FD_UNLIKELY( invalid_ancestor && sibling_confirmed ) ) {
778 0 : flags = fd_uchar_set_bit( flags, FD_TOWER_FLAG_SIBLING_CONFIRMED );
779 0 : reset_blk = best_blk;
780 0 : vote_blk = best_blk;
781 0 : FD_BASE58_ENCODE_32_BYTES( reset_blk->id.uc, reset_blk_id );
782 0 : FD_BASE58_ENCODE_32_BYTES( vote_blk->id.uc, vote_blk_id );
783 0 : FD_LOG_DEBUG(( "[%s] case 1b: sibling confirmed. prev_vote_slot: %lu. reset_blk: (%lu, %s). vote_blk: (%lu, %s)", __func__, prev_vote_slot, reset_blk->slot, reset_blk_id, vote_blk->slot, vote_blk_id ));
784 0 : }
785 :
786 : /* Case 2: if our prev vote slot is an ancestor of the best slot, then
787 : they are on the same fork and we can both reset to it. We can also
788 : vote for it if we pass the can_vote checks.
789 :
790 : https://github.com/anza-xyz/agave/blob/v2.3.7/core/src/consensus.rs#L1057 */
791 :
792 6 : else if( FD_LIKELY( best_blk->slot == prev_vote_slot || fd_tower_blocks_is_slot_ancestor( tower, best_blk->slot, prev_vote_slot ) ) ) {
793 0 : flags = fd_uchar_set_bit( flags, FD_TOWER_FLAG_SAME_FORK );
794 0 : reset_blk = best_blk;
795 0 : vote_blk = best_blk;
796 0 : FD_BASE58_ENCODE_32_BYTES( reset_blk->id.uc, reset_blk_id );
797 0 : FD_BASE58_ENCODE_32_BYTES( vote_blk->id.uc, vote_blk_id );
798 0 : FD_LOG_DEBUG(( "[%s] case 2: same fork. prev_vote_slot: %lu. reset_blk: (%lu, %s). vote_blk: (%lu, %s)", __func__, prev_vote_slot, reset_blk->slot, reset_blk_id, vote_blk->slot, vote_blk_id ));
799 0 : }
800 :
801 : /* Case 3: if our prev vote is not an ancestor of the best block, then
802 : it is on a different fork. If we pass the switch check, we can
803 : reset to it. If we additionally pass the lockout check, we can
804 : also vote for it.
805 :
806 : https://github.com/anza-xyz/agave/blob/v2.3.7/core/src/consensus.rs#L1208-L1215
807 :
808 : Note also Agave uses the best blk's total stake for checking the
809 : threshold.
810 :
811 : https://github.com/anza-xyz/agave/blob/v2.3.7/core/src/consensus/fork_choice.rs#L443-L445 */
812 :
813 6 : else if( FD_LIKELY( switch_check( tower, ghost, best_blk->total_stake, best_blk->slot ) ) ) {
814 3 : flags = fd_uchar_set_bit( flags, FD_TOWER_FLAG_SWITCH_PASS );
815 3 : reset_blk = best_blk;
816 3 : vote_blk = best_blk;
817 3 : FD_BASE58_ENCODE_32_BYTES( reset_blk->id.uc, reset_blk_id );
818 3 : FD_BASE58_ENCODE_32_BYTES( vote_blk->id.uc, vote_blk_id );
819 3 : FD_LOG_DEBUG(( "[%s] case 3: switch pass. prev_vote_slot: %lu. reset_blk: (%lu, %s). vote_blk: (%lu, %s)", __func__, prev_vote_slot, reset_blk->slot, reset_blk_id, vote_blk->slot, vote_blk_id ));
820 3 : }
821 :
822 : /* Case 4: same as case 3 but we didn't pass the switch check. In
823 : this case we reset to either ghost_best or ghost_deepest beginning
824 : from our prev vote blk.
825 :
826 : We must reset to a block beginning from our prev vote fork to
827 : ensure votes get a chance to propagate. Because in order for votes
828 : to land, someone needs to build a block on that fork.
829 :
830 : We reset to ghost_best or ghost_deepest depending on whether our
831 : prev vote is valid. When it's invalid we use ghost_deepest instead
832 : of ghost_best, because ghost_best won't be able to return a valid
833 : block beginning from our prev_vote because by definition the entire
834 : subtree will be invalid.
835 :
836 : When our prev vote fork is not a duplicate, we want to propagate
837 : votes that might allow others to switch to our fork. In addition,
838 : if our prev vote fork is a duplicate, we want to propagate votes
839 : that might "duplicate confirm" that block (reach 52% of stake).
840 :
841 : See top-level documentation in fd_tower.h for more details on vote
842 : propagation. */
843 :
844 3 : else {
845 :
846 : /* Case 4a: failed switch check and last vote slot has an invalid
847 : ancestor.
848 :
849 : https://github.com/anza-xyz/agave/blob/v2.3.7/core/src/consensus/heaviest_subtree_fork_choice.rs#L1187 */
850 :
851 3 : if( FD_UNLIKELY( invalid_ancestor ) ) {
852 3 : flags = fd_uchar_set_bit( flags, FD_TOWER_FLAG_SWITCH_FAIL );
853 3 : reset_blk = fd_ghost_deepest( ghost, prev_vote_blk );
854 3 : FD_BASE58_ENCODE_32_BYTES( reset_blk->id.uc, reset_blk_id );
855 3 : FD_LOG_DEBUG(( "[%s] case 4a: switch fail, invalid ancestor. prev_vote_slot: %lu. reset_blk: (%lu, %s). vote_blk: (NULL)", __func__, prev_vote_slot, reset_blk->slot, reset_blk_id ));
856 3 : }
857 :
858 : /* Case 4b: failed switch check (no invalid ancestor).
859 :
860 : https://github.com/anza-xyz/agave/blob/v2.3.7/core/src/consensus/fork_choice.rs#L200 */
861 :
862 0 : else {
863 0 : flags = fd_uchar_set_bit( flags, FD_TOWER_FLAG_SWITCH_FAIL );
864 0 : reset_blk = fd_ghost_best( ghost, prev_vote_blk );
865 0 : FD_BASE58_ENCODE_32_BYTES( reset_blk->id.uc, reset_blk_id );
866 0 : FD_LOG_DEBUG(( "[%s] case 4b: switch fail, no invalid ancestor. prev_vote_slot: %lu. reset_blk: (%lu, %s). vote_blk: (NULL)", __func__, prev_vote_slot, reset_blk->slot, reset_blk_id ));
867 0 : }
868 3 : }
869 :
870 : /* If there is a block to vote for, there are a few additional checks
871 : to make sure we can actually vote for it.
872 :
873 : Specifically, we need to make sure we're not locked out, pass the
874 : threshold check and that our previous leader block has propagated
875 : (reached the prop threshold according to fd_votes).
876 :
877 : https://github.com/firedancer-io/agave/blob/master/core/src/consensus/fork_choice.rs#L382-L385
878 :
879 : Agave uses the total stake on the fork being threshold checked
880 : (vote_blk) for determining whether it meets the stake threshold. */
881 :
882 6 : if( FD_LIKELY( vote_blk ) ) {
883 3 : if ( FD_UNLIKELY( !lockout_check( tower, vote_blk->slot ) ) ) {
884 3 : FD_BASE58_ENCODE_32_BYTES( vote_blk->id.uc, vote_blk_id );
885 3 : FD_LOG_DEBUG(( "[%s] lockout check failed. prev_vote_slot: %lu. vote_blk: (%lu, %s)", __func__, prev_vote_slot, vote_blk->slot, vote_blk_id ));
886 3 : flags = fd_uchar_set_bit( flags, FD_TOWER_FLAG_LOCKOUT_FAIL );
887 3 : vote_blk = NULL;
888 3 : }
889 0 : else if( FD_UNLIKELY( !threshold_check( tower, tower->vtrs, vote_blk->total_stake, vote_blk->slot ) ) ) {
890 0 : FD_BASE58_ENCODE_32_BYTES( vote_blk->id.uc, vote_blk_id );
891 0 : FD_LOG_DEBUG(( "[%s] threshold check failed. prev_vote_slot: %lu. vote_blk: (%lu, %s)", __func__, prev_vote_slot, vote_blk->slot, vote_blk_id ));
892 0 : flags = fd_uchar_set_bit( flags, FD_TOWER_FLAG_THRESHOLD_FAIL );
893 0 : vote_blk = NULL;
894 0 : }
895 0 : else if( FD_UNLIKELY( !propagated_check( tower, vote_blk->slot ) ) ) {
896 0 : FD_BASE58_ENCODE_32_BYTES( vote_blk->id.uc, vote_blk_id );
897 0 : FD_LOG_DEBUG(( "[%s] propagated check failed. prev_vote_slot: %lu. vote_blk: (%lu, %s)", __func__, prev_vote_slot, vote_blk->slot, vote_blk_id ));
898 0 : flags = fd_uchar_set_bit( flags, FD_TOWER_FLAG_PROPAGATED_FAIL );
899 0 : vote_blk = NULL;
900 0 : }
901 3 : }
902 :
903 6 : FD_TEST( reset_blk ); /* always a reset_blk */
904 6 : *reset_slot = reset_blk->slot;
905 6 : *reset_block_id = reset_blk->id;
906 6 : *vote_slot = ULONG_MAX;
907 6 : *vote_block_id = (fd_hash_t){0};
908 6 : *vote_bank_hash = (fd_hash_t){0};
909 6 : *root_slot = ULONG_MAX;
910 6 : *root_block_id = (fd_hash_t){0};
911 :
912 : /* Finally, if our vote passed all the checks, we actually push the
913 : vote onto the tower. */
914 :
915 6 : if( FD_LIKELY( vote_blk ) ) {
916 0 : *vote_slot = vote_blk->slot;
917 0 : *vote_block_id = vote_blk->id;
918 0 : *root_slot = push_vote( tower, vote_blk->slot );
919 :
920 : /* Query our tower fork for this slot we're voting for. Note this
921 : can never be NULL because we record tower forks as we replay, and
922 : we should never be voting on something we haven't replayed. */
923 :
924 0 : fd_tower_blk_t * fork = fd_tower_blocks_query( tower, vote_blk->slot );
925 0 : fork->voted = 1;
926 0 : fork->voted_block_id = vote_blk->id;
927 0 : *vote_bank_hash = fork->bank_hash;
928 :
929 : /* Query the root slot's block id from tower forks. This block id
930 : may not necessarily be confirmed, because confirmation requires
931 : votes on the block itself (vs. block and its descendants).
932 :
933 : So if we have a confirmed block id, we return that. Otherwise
934 : we return our own vote block id for that slot, which we assume
935 : is the cluster converged on by the time we're rooting it.
936 :
937 : The only way it is possible for us to root the wrong version of
938 : a block (ie. not the one the cluster confirmed) is if there is
939 : mass equivocation (>2/3 of threshold check stake has voted for
940 : two versions of a block). This exceeds the equivocation safety
941 : threshold and we would eventually detect this via a bank hash
942 : mismatch and error out. */
943 :
944 0 : if( FD_LIKELY( *root_slot!=ULONG_MAX ) ) {
945 0 : fd_tower_blk_t * root_fork = fd_tower_blocks_query( tower, *root_slot );
946 0 : *root_block_id = *fd_ptr_if( root_fork->confirmed, &root_fork->confirmed_block_id, &root_fork->voted_block_id );
947 0 : }
948 0 : }
949 :
950 6 : FD_BASE58_ENCODE_32_BYTES( reset_block_id->uc, reset_block_id_b58 );
951 6 : FD_BASE58_ENCODE_32_BYTES( vote_block_id->uc, vote_block_id_b58 );
952 6 : FD_BASE58_ENCODE_32_BYTES( root_block_id->uc, root_block_id_b58 );
953 6 : FD_LOG_DEBUG(( "[%s] flags: %d. reset_slot: %lu (%s). vote_slot: %lu (%s). root_slot: %lu (%s).", __func__, flags, *reset_slot, reset_block_id_b58, *vote_slot, vote_block_id_b58, *root_slot, root_block_id_b58 ));
954 6 : return flags;
955 6 : }
956 :
957 : /* fd_tower_reconcile reconciles our local tower with our on-chain tower
958 : (stored inside our vote account). This function is important in two
959 : contexts:
960 :
961 : ON BOOT
962 :
963 : When Firedancer boots up its local tower contains no votes, only a
964 : root slot set to the snapshot slot. It needs to restore its "latest"
965 : tower votes and root as of its previous run. This information is
966 : stored on-chain itself, in a vote account, and Firedancer updates
967 : vote account states during catchup by replaying blocks since the
968 : snapshot. Firedancer reconciles its local tower with the on-chain
969 : one every time it replays a block, and will by definition have its
970 : "latest" tower once it has caught up.
971 :
972 : Note that it is possible Firedancer had voted for a minority fork in
973 : the previous run. In this case, its true "latest" tower contains
974 : votes for slots that were pruned by the time of this boot. In theory
975 : TowerBFT stipulates that lockout can be up to 2^32 slots, but in
976 : practice slots are pruned once they fall out of the slot hash history
977 : limit, because they can no longer be canonically verified on-chain.
978 : Therefore, Firedancer can safely ignore slots that are pruned and
979 : restore its latest tower on the majority fork as of boot time.
980 :
981 : HIGH-AVAILABILITY SETUP
982 :
983 : A typical validator setup involves two nodes, a primary and a backup.
984 : The primary is a valid fee payer, and the one landing votes recording
985 : the latest state of its tower on-chain. The two nodes' towers will
986 : usually be identical but occassionally diverge when one node votes
987 : for slots that the other one doesn't. This usually happens when
988 : there are multiple forks.
989 :
990 : This becomes a problem, because the primary's tower may contain votes
991 : the backup doesn't have and/or vice versa. The primary's tower is
992 : the canonical one, since it's the one recorded on-chain, so reconcile
993 : is a no-op on the primary.
994 :
995 : On the backup, reconcile is more involved. Because what's on-chain
996 : is the primary's tower, there may be slots the backup never actually
997 : voted for. When the backup node reads back the on-chain tower, some
998 : metadata, namely `voted` and `voted_block_id`, will be missing from
999 : its fd_tower instance.
1000 :
1001 : fd_tower_reconcile assumes that if a tower has been recorded on-chain
1002 : then it is safe to assume the vote account registered with the
1003 : currently running Firedancer has in fact at some point voted for the
1004 : slots in that tower.
1005 :
1006 : In case the instance is the backup, it updates the local tower votes,
1007 : root, and metadata structures accordingly with this assumption namely
1008 : by inserting voted_block_id for votes that the backup didn't actually
1009 : vote for but can safely assume the primary did.
1010 :
1011 : This affects the Tower voting rules (see fd_tower_vote_and_reset) in
1012 : that the voted_block_id is used for certain vote and reset decisions.
1013 :
1014 : There are some corner cases to consider related to equivocation:
1015 :
1016 : 2
1017 : / \
1018 : 3 3' (confirmed)
1019 :
1020 : Assume 3 and 3' are alternate blocks for the same slot (3) and have
1021 : different block ids. 3' is the block that eventually gets confirmed.
1022 : Let's consider a scenario in which the primary votes for "3" and the
1023 : backup misses the vote for "3". fd_tower_reconcile needs to backfill
1024 : the voted_block_id for "3" on the backup. However, it's unclear
1025 : whether that vote is for 3 (unconfirmed) or 3' (confirmed), because
1026 : all the on-chain tower contains is the slot "3" (with no block_id).
1027 : How does the backup figure out the voted_block_id?
1028 :
1029 : It turns out it doesn't really matter either way, the backup can just
1030 : backfill with whichever block_id it happened to replay (we know the
1031 : backup has to have replayed either 3 or 3' in order to observe an
1032 : on-chain tower containing 3 in the first place):
1033 :
1034 : If the primary voted for 3 and the backup backfills with 3', we know
1035 : the primary will eventually switch to the DC block (3') via repair.
1036 : So backfilling with 3' is ok because the primary will converge to it.
1037 :
1038 : If the primary voted for 3' and the backup backfills with 3, then the
1039 : backup will similarly eventually switch to the DC block via repair.
1040 : Indeed, it will "freebie" switch in fd_tower_vote_and_reset ie. case
1041 : 1b: "sibling confirmed". Thus, the backup will converge to 3'. */
1042 :
1043 : void
1044 : fd_tower_reconcile( fd_tower_t * tower,
1045 : fd_tower_vote_t * onchain_votes,
1046 30 : ulong onchain_root ) {
1047 :
1048 30 : fd_tower_vote_t * local_votes = tower->votes;
1049 30 : ulong local_root = tower->root;
1050 :
1051 30 : ulong local_vote = fd_tower_vote_empty( local_votes ) ? ULONG_MAX : fd_tower_vote_peek_tail_const( local_votes )->slot;
1052 30 : ulong onchain_vote = fd_tower_vote_empty( onchain_votes ) ? ULONG_MAX : fd_tower_vote_peek_tail_const( onchain_votes )->slot;
1053 :
1054 : /* Cases:
1055 :
1056 : Agave checks Option<onchain_vote> <= Option<local_vote>. Breakdown of Ord<Option<Slot>>:
1057 :
1058 : None, None => True
1059 : None, Some => True
1060 : Some, None => False
1061 : Some, Some => onchain_vote <= local_vote */
1062 :
1063 30 : if( FD_LIKELY( onchain_vote==ULONG_MAX || /* None, None or None, Some */
1064 30 : ( local_vote !=ULONG_MAX && onchain_vote<=local_vote ) /* Some, Some */ ) ) return;
1065 :
1066 : /* On-chain tower is newer, so sync our local tower to the on-chain tower. */
1067 :
1068 24 : FD_LOG_NOTICE(( "[%s] overwriting local tower (last: %lu, root: %lu) with onchain tower (last: %lu, root: %lu)", __func__, local_vote, local_root, onchain_vote, onchain_root ));
1069 :
1070 24 : FD_TEST( local_root!=ULONG_MAX ); /* local root should always be set before fd_tower_reconcile */
1071 24 : if( FD_LIKELY( onchain_root==ULONG_MAX || local_root > onchain_root ) ) {
1072 :
1073 : /* Local root is larger than on-chain root. Overwrite on-chain root
1074 : with local root (this is just a copy, not writing to accdb). */
1075 :
1076 3 : FD_LOG_DEBUG(( "[%s] local_root %lu > onchain_root %lu", __func__, local_root, onchain_root ));
1077 3 : onchain_root = local_root;
1078 :
1079 : /* Drop on-chain votes <= local root. */
1080 :
1081 12 : while( FD_LIKELY( !fd_tower_vote_empty( onchain_votes ) ) ) {
1082 12 : fd_tower_vote_t const * vote = fd_tower_vote_peek_head_const( onchain_votes );
1083 12 : if( FD_LIKELY( vote->slot > local_root ) ) break;
1084 9 : FD_LOG_DEBUG(( "[%s] dropping on-chain vote for slot %lu since it's <= local root %lu", __func__, vote->slot, local_root ));
1085 9 : fd_tower_vote_pop_head( onchain_votes );
1086 9 : }
1087 :
1088 : /* TODO add sanity-check that onchain_root is an ancestor of the
1089 : first vote's ancestor at this point. */
1090 3 : }
1091 :
1092 24 : for( fd_tower_vote_iter_t iter = fd_tower_vote_iter_init( tower->votes );
1093 66 : !fd_tower_vote_iter_done( tower->votes, iter );
1094 42 : iter = fd_tower_vote_iter_next( tower->votes, iter ) ) {
1095 42 : fd_tower_vote_t const * vote = fd_tower_vote_iter_ele_const( tower->votes, iter );
1096 42 : fd_tower_blk_t * tower_blk = fd_tower_blocks_query( tower, vote->slot );
1097 42 : FD_TEST( tower_blk ); /* must exist if it's in our tower */
1098 42 : tower_blk->voted = 0;
1099 42 : }
1100 :
1101 : /* Need to overwrite tower->root with onchain_root, so first clear out
1102 : any intermediate slots between them. */
1103 :
1104 30 : for( ulong slot = tower->root; slot < onchain_root; slot++ ) {
1105 6 : fd_tower_blocks_remove( tower, slot );
1106 6 : fd_tower_lockos_remove( tower, slot );
1107 6 : fd_tower_stakes_remove( tower, slot );
1108 6 : }
1109 :
1110 : /* Overwrite the root. No-op if local_root > onchain_root. */
1111 :
1112 24 : tower->root = onchain_root;
1113 :
1114 : /* Clear out all local_votes. */
1115 :
1116 24 : fd_tower_vote_remove_all( tower->votes );
1117 :
1118 : /* Replace them with onchain_votes. */
1119 :
1120 24 : for( fd_tower_vote_iter_t iter = fd_tower_vote_iter_init( onchain_votes );
1121 96 : !fd_tower_vote_iter_done( onchain_votes, iter );
1122 72 : iter = fd_tower_vote_iter_next( onchain_votes, iter ) ) {
1123 72 : fd_tower_vote_t const * vote = fd_tower_vote_iter_ele_const( onchain_votes, iter );
1124 72 : fd_tower_vote_push_tail( tower->votes, *vote );
1125 :
1126 : /* Additionally, backfill voted_block_id for the slots we didn't
1127 : actually vote for. This is intentionally always using the latest
1128 : replayed_block_id if we overwrote it with a second replay. */
1129 :
1130 72 : fd_tower_blk_t * tower_blk = fd_tower_blocks_query( tower, vote->slot );
1131 72 : FD_TEST( tower_blk ); /* must exist because
1132 : 1. all on-chain votes > root slot
1133 : 2. all on-chain votes <= replay slot */
1134 72 : if( FD_UNLIKELY( !tower_blk->voted ) ) {
1135 72 : tower_blk->voted = 1;
1136 72 : tower_blk->voted_block_id = tower_blk->replayed_block_id;
1137 72 : }
1138 72 : }
1139 24 : }
1140 :
1141 : void
1142 : fd_tower_from_vote_acc( fd_tower_vote_t * votes,
1143 : ulong * root,
1144 : uchar const * data,
1145 147 : ulong data_sz ) {
1146 147 : fd_vote_acc_desc_t desc[1];
1147 147 : if( FD_UNLIKELY( !fd_vote_acc_desc( desc, data, data_sz ) ) ) {
1148 0 : *root = ULONG_MAX;
1149 0 : return;
1150 0 : }
1151 147 : *root = desc->root_slot;
1152 474 : for( ulong i=0UL; i<desc->vote_cnt; i++ ) {
1153 327 : fd_tower_vote_t vote = {0};
1154 327 : switch( desc->kind ) {
1155 93 : case FD_VOTE_ACC_V2: {
1156 93 : fd_vote_acc_vote_v2_t const * v = fd_vote_acc_desc_vote( desc, data, i );
1157 93 : vote.slot = v->slot;
1158 93 : vote.conf = v->conf;
1159 93 : break;
1160 0 : }
1161 234 : case FD_VOTE_ACC_V3:
1162 234 : case FD_VOTE_ACC_V4: {
1163 234 : fd_vote_acc_vote_t const * v = fd_vote_acc_desc_vote( desc, data, i );
1164 234 : vote.slot = v->slot;
1165 234 : vote.conf = v->conf;
1166 234 : break;
1167 234 : }
1168 327 : }
1169 327 : fd_tower_vote_push_tail( votes, vote );
1170 327 : }
1171 147 : }
1172 :
1173 : ulong
1174 : fd_tower_with_lat_from_vote_acc( fd_vote_acc_vote_t tower[ static FD_TOWER_VOTE_MAX ],
1175 : uchar const * data,
1176 0 : ulong data_sz ) {
1177 0 : fd_vote_acc_desc_t desc[1];
1178 0 : if( FD_UNLIKELY( !fd_vote_acc_desc( desc, data, data_sz ) ) ) return 0UL;
1179 0 : FD_DCHECK_CRIT( desc->vote_cnt <= FD_TOWER_VOTE_MAX, "invalid vote account" );
1180 0 : switch( desc->kind ) {
1181 0 : case FD_VOTE_ACC_V2: {
1182 0 : for( ulong i=0UL; i<desc->vote_cnt; i++ ) {
1183 0 : fd_vote_acc_vote_v2_t const * v = fd_vote_acc_desc_vote( desc, data, i );
1184 0 : tower[ i ] = (fd_vote_acc_vote_t){
1185 0 : .slot = v->slot,
1186 0 : .conf = v->conf,
1187 0 : .latency = UCHAR_MAX
1188 0 : };
1189 0 : }
1190 0 : break;
1191 0 : }
1192 0 : case FD_VOTE_ACC_V3:
1193 0 : case FD_VOTE_ACC_V4:
1194 0 : fd_memcpy( tower, fd_vote_acc_desc_vote( desc, data, 0UL ), desc->vote_cnt * sizeof(fd_vote_acc_vote_t) );
1195 0 : break;
1196 0 : }
1197 0 : return desc->vote_cnt;
1198 0 : }
1199 :
1200 : void
1201 : fd_tower_to_vote_txn( fd_tower_t const * tower,
1202 : fd_hash_t const * bank_hash,
1203 : fd_hash_t const * block_id,
1204 : fd_hash_t const * recent_blockhash,
1205 : fd_pubkey_t const * validator_identity,
1206 : fd_pubkey_t const * vote_authority,
1207 : fd_pubkey_t const * vote_acc,
1208 3 : fd_txn_p_t * vote_txn ) {
1209 :
1210 3 : FD_TEST( fd_tower_vote_cnt( tower->votes )<=FD_TOWER_VOTE_MAX );
1211 3 : fd_compact_tower_sync_serde_t tower_sync_serde = {
1212 3 : .root = fd_ulong_if( tower->root == ULONG_MAX, 0UL, tower->root ),
1213 3 : .lockouts_cnt = (ushort)fd_tower_vote_cnt( tower->votes ),
1214 : /* .lockouts populated below */
1215 3 : .hash = *bank_hash,
1216 3 : .timestamp_option = 1,
1217 3 : .timestamp = fd_log_wallclock() / (long)1e9, /* seconds */
1218 3 : .block_id = *block_id
1219 3 : };
1220 :
1221 3 : ulong i = 0UL;
1222 3 : ulong prev = tower_sync_serde.root;
1223 3 : for( fd_tower_vote_iter_t iter = fd_tower_vote_iter_init( tower->votes );
1224 96 : !fd_tower_vote_iter_done( tower->votes, iter );
1225 93 : iter = fd_tower_vote_iter_next( tower->votes, iter ) ) {
1226 93 : fd_tower_vote_t const * vote = fd_tower_vote_iter_ele_const( tower->votes, iter );
1227 93 : tower_sync_serde.lockouts[i].offset = vote->slot - prev;
1228 93 : tower_sync_serde.lockouts[i].confirmation_count = (uchar)vote->conf;
1229 93 : prev = vote->slot;
1230 93 : i++;
1231 93 : }
1232 :
1233 3 : uchar * txn_out = vote_txn->payload;
1234 3 : uchar * txn_meta_out = vote_txn->_;
1235 :
1236 3 : int same_addr = !memcmp( validator_identity, vote_authority, sizeof(fd_pubkey_t) );
1237 3 : if( FD_LIKELY( same_addr ) ) {
1238 :
1239 : /* 0: validator identity
1240 : 1: vote account address
1241 : 2: vote program */
1242 :
1243 3 : fd_txn_accounts_t votes;
1244 3 : votes.signature_cnt = 1;
1245 3 : votes.readonly_signed_cnt = 0;
1246 3 : votes.readonly_unsigned_cnt = 1;
1247 3 : votes.acct_cnt = 3;
1248 3 : votes.signers_w = validator_identity;
1249 3 : votes.signers_r = NULL;
1250 3 : votes.non_signers_w = vote_acc;
1251 3 : votes.non_signers_r = &fd_solana_vote_program_id;
1252 3 : FD_TEST( fd_txn_base_generate( txn_meta_out, txn_out, votes.signature_cnt, &votes, recent_blockhash->uc ) );
1253 :
1254 3 : } else {
1255 :
1256 : /* 0: validator identity
1257 : 1: vote authority
1258 : 2: vote account address
1259 : 3: vote program */
1260 :
1261 0 : fd_txn_accounts_t votes;
1262 0 : votes.signature_cnt = 2;
1263 0 : votes.readonly_signed_cnt = 1;
1264 0 : votes.readonly_unsigned_cnt = 1;
1265 0 : votes.acct_cnt = 4;
1266 0 : votes.signers_w = validator_identity;
1267 0 : votes.signers_r = vote_authority;
1268 0 : votes.non_signers_w = vote_acc;
1269 0 : votes.non_signers_r = &fd_solana_vote_program_id;
1270 0 : FD_TEST( fd_txn_base_generate( txn_meta_out, txn_out, votes.signature_cnt, &votes, recent_blockhash->uc ) );
1271 0 : }
1272 :
1273 : /* Add the vote instruction to the transaction. */
1274 :
1275 3 : uchar vote_ix_buf[FD_TXN_MTU];
1276 3 : ulong vote_ix_sz = 0;
1277 3 : FD_STORE( uint, vote_ix_buf, FD_VOTE_IX_KIND_TOWER_SYNC );
1278 3 : FD_TEST( 0==fd_compact_tower_sync_ser( &tower_sync_serde, vote_ix_buf + sizeof(uint), FD_TXN_MTU - sizeof(uint), &vote_ix_sz ) ); // cannot fail if fd_tower_vote_cnt( tower->votes ) <= FD_TOWER_VOTE_MAX
1279 3 : vote_ix_sz += sizeof(uint);
1280 3 : uchar program_id;
1281 3 : uchar ix_accs[2];
1282 3 : if( FD_LIKELY( same_addr ) ) {
1283 3 : ix_accs[0] = 1; /* vote account address */
1284 3 : ix_accs[1] = 0; /* vote authority */
1285 3 : program_id = 2; /* vote program */
1286 3 : } else {
1287 0 : ix_accs[0] = 2; /* vote account address */
1288 0 : ix_accs[1] = 1; /* vote authority */
1289 0 : program_id = 3; /* vote program */
1290 0 : }
1291 3 : vote_txn->payload_sz = fd_txn_add_instr( txn_meta_out, txn_out, program_id, ix_accs, 2, vote_ix_buf, vote_ix_sz );
1292 3 : }
1293 :
1294 : int
1295 0 : fd_tower_verify( fd_tower_t const * tower ) {
1296 0 : if( FD_UNLIKELY( fd_tower_vote_cnt( tower->votes )>=FD_TOWER_VOTE_MAX ) ) {
1297 0 : FD_LOG_WARNING(( "[%s] invariant violation: cnt %lu >= FD_TOWER_VOTE_MAX %lu", __func__, fd_tower_vote_cnt( tower->votes ), (ulong)FD_TOWER_VOTE_MAX ));
1298 0 : return -1;
1299 0 : }
1300 :
1301 0 : fd_tower_vote_t const * prev = NULL;
1302 0 : for( fd_tower_vote_iter_t iter = fd_tower_vote_iter_init( tower->votes );
1303 0 : !fd_tower_vote_iter_done( tower->votes, iter );
1304 0 : iter = fd_tower_vote_iter_next( tower->votes, iter ) ) {
1305 0 : fd_tower_vote_t const * vote = fd_tower_vote_iter_ele_const( tower->votes, iter );
1306 0 : if( FD_UNLIKELY( prev && ( vote->slot < prev->slot || vote->conf < prev->conf ) ) ) {
1307 0 : FD_LOG_WARNING(( "[%s] invariant violation: vote (slot:%lu conf:%lu) prev (slot:%lu conf:%lu)", __func__, vote->slot, vote->conf, prev->slot, prev->conf ));
1308 0 : return -1;
1309 0 : }
1310 0 : prev = vote;
1311 0 : }
1312 0 : return 0;
1313 0 : }
1314 :
1315 : static void
1316 0 : to_cstr( fd_tower_t const * tower, char * s, ulong len ) {
1317 0 : ulong root = tower->root;
1318 0 : ulong off = 0;
1319 0 : int n;
1320 :
1321 0 : n = snprintf( s + off, len - off, "[Tower]\n\n" );
1322 0 : if( FD_UNLIKELY( n < 0 )) FD_LOG_CRIT(( "snprintf: %d", n ));
1323 0 : off += (ulong)n;
1324 :
1325 0 : if( FD_UNLIKELY( fd_tower_vote_empty( tower->votes ) ) ) return;
1326 :
1327 0 : ulong max_slot = 0;
1328 :
1329 : /* Determine spacing. */
1330 :
1331 0 : for( fd_tower_vote_iter_t iter = fd_tower_vote_iter_init_rev( tower->votes );
1332 0 : !fd_tower_vote_iter_done_rev( tower->votes, iter );
1333 0 : iter = fd_tower_vote_iter_prev ( tower->votes, iter ) ) {
1334 0 : max_slot = fd_ulong_max( max_slot, fd_tower_vote_iter_ele_const( tower->votes, iter )->slot );
1335 0 : }
1336 :
1337 : /* Calculate the number of digits in the maximum slot value. */
1338 :
1339 :
1340 0 : int digit_cnt = (int)fd_ulong_base10_dig_cnt( max_slot );
1341 :
1342 : /* Print the column headers. */
1343 :
1344 0 : if( off < len ) {
1345 0 : n = snprintf( s + off, len - off, "slot%*s | %s\n", digit_cnt - (int)strlen("slot"), "", "confirmation count" );
1346 0 : if( FD_UNLIKELY( n < 0 )) FD_LOG_CRIT(( "snprintf: %d", n ));
1347 0 : off += (ulong)n;
1348 0 : }
1349 :
1350 : /* Print the divider line. */
1351 :
1352 0 : for( int i = 0; i < digit_cnt && off < len; i++ ) {
1353 0 : s[off++] = '-';
1354 0 : }
1355 0 : if( off < len ) {
1356 0 : n = snprintf( s + off, len - off, " | " );
1357 0 : if( FD_UNLIKELY( n < 0 )) FD_LOG_CRIT(( "snprintf: %d", n ));
1358 0 : off += (ulong)n;
1359 0 : }
1360 0 : for( ulong i = 0; i < strlen( "confirmation count" ) && off < len; i++ ) {
1361 0 : s[off++] = '-';
1362 0 : }
1363 0 : if( off < len ) {
1364 0 : s[off++] = '\n';
1365 0 : }
1366 :
1367 : /* Print each vote as a table. */
1368 :
1369 0 : for( fd_tower_vote_iter_t iter = fd_tower_vote_iter_init_rev( tower->votes );
1370 0 : !fd_tower_vote_iter_done_rev( tower->votes, iter );
1371 0 : iter = fd_tower_vote_iter_prev ( tower->votes, iter ) ) {
1372 0 : fd_tower_vote_t const * vote = fd_tower_vote_iter_ele_const( tower->votes, iter );
1373 0 : if( off < len ) {
1374 0 : n = snprintf( s + off, len - off, "%*lu | %lu\n", digit_cnt, vote->slot, vote->conf );
1375 0 : if( FD_UNLIKELY( n < 0 )) FD_LOG_CRIT(( "snprintf: %d", n ));
1376 0 : off += (ulong)n;
1377 0 : }
1378 0 : }
1379 :
1380 0 : if( FD_UNLIKELY( root == ULONG_MAX ) ) {
1381 0 : if( off < len ) {
1382 0 : n = snprintf( s + off, len - off, "%*s | root\n", digit_cnt, "NULL" );
1383 0 : if( FD_UNLIKELY( n < 0 )) FD_LOG_CRIT(( "snprintf: %d", n ));
1384 0 : off += (ulong)n;
1385 0 : }
1386 0 : } else {
1387 0 : if( off < len ) {
1388 0 : n = snprintf( s + off, len - off, "%*lu | root\n", digit_cnt, root );
1389 0 : if( FD_UNLIKELY( n < 0 )) FD_LOG_CRIT(( "snprintf: %d", n ));
1390 0 : off += (ulong)n;
1391 0 : }
1392 0 : }
1393 :
1394 : /* Ensure null termination */
1395 0 : if( off < len ) {
1396 0 : s[off] = '\0';
1397 0 : } else {
1398 0 : s[len - 1] = '\0';
1399 0 : }
1400 0 : }
1401 :
1402 : char *
1403 : fd_tower_to_cstr( fd_tower_t const * tower,
1404 0 : char * cstr ) {
1405 0 : to_cstr( tower, cstr, FD_TOWER_CSTR_MIN );
1406 0 : return cstr;
1407 0 : }
1408 :
1409 : void
1410 : fd_tower_count_vote( fd_tower_t * tower,
1411 : fd_pubkey_t const * vote_acc,
1412 : ulong stake,
1413 : uchar const * data,
1414 9 : ulong data_sz ) {
1415 9 : fd_tower_vtr_t * vtr = fd_tower_vtr_push_tail_nocopy( tower->vtrs );
1416 9 : vtr->vote_acc = *vote_acc;
1417 9 : vtr->stake = stake;
1418 9 : fd_tower_vote_remove_all( vtr->votes );
1419 9 : fd_tower_from_vote_acc( vtr->votes, &vtr->root, data, data_sz );
1420 9 : }
1421 :
1422 : /* Block functions ********************************************************/
1423 :
1424 : static int
1425 : is_ancestor( fd_tower_t * tower,
1426 : ulong slot,
1427 177 : ulong ancestor_slot ) {
1428 177 : fd_tower_blk_t * anc = blk_map_ele_query( tower->blk_map, &slot, NULL, tower->blk_pool );
1429 639 : while( FD_LIKELY( anc ) ) {
1430 573 : if( FD_LIKELY( anc->parent_slot == ancestor_slot ) ) return 1;
1431 462 : anc = anc->parent_slot == ULONG_MAX ? NULL : blk_map_ele_query( tower->blk_map, &anc->parent_slot, NULL, tower->blk_pool );
1432 462 : }
1433 66 : return 0;
1434 177 : }
1435 :
1436 : int
1437 : fd_tower_blocks_is_slot_ancestor( fd_tower_t * tower,
1438 : ulong descendant_slot,
1439 6 : ulong ancestor_slot ) {
1440 6 : return is_ancestor( tower, descendant_slot, ancestor_slot );
1441 6 : }
1442 :
1443 : int
1444 : fd_tower_blocks_is_slot_descendant( fd_tower_t * tower,
1445 : ulong ancestor_slot,
1446 171 : ulong descendant_slot ) {
1447 171 : return is_ancestor( tower, descendant_slot, ancestor_slot );
1448 171 : }
1449 :
1450 : ulong
1451 : fd_tower_blocks_lowest_common_ancestor( fd_tower_t * tower,
1452 : ulong slot1,
1453 147 : ulong slot2 ) {
1454 :
1455 147 : fd_tower_blk_t * fork1 = blk_map_ele_query( tower->blk_map, &slot1, NULL, tower->blk_pool );
1456 147 : fd_tower_blk_t * fork2 = blk_map_ele_query( tower->blk_map, &slot2, NULL, tower->blk_pool );
1457 :
1458 147 : if( FD_UNLIKELY( !fork1 )) FD_LOG_CRIT(( "slot1 %lu not found", slot1 ));
1459 147 : if( FD_UNLIKELY( !fork2 )) FD_LOG_CRIT(( "slot2 %lu not found", slot2 ));
1460 :
1461 864 : while( FD_LIKELY( fork1 && fork2 ) ) {
1462 864 : if( FD_UNLIKELY( fork1->slot == fork2->slot ) ) return fork1->slot;
1463 717 : if( fork1->slot > fork2->slot ) fork1 = blk_map_ele_query( tower->blk_map, &fork1->parent_slot, NULL, tower->blk_pool );
1464 453 : else fork2 = blk_map_ele_query( tower->blk_map, &fork2->parent_slot, NULL, tower->blk_pool );
1465 717 : }
1466 :
1467 0 : return ULONG_MAX;
1468 147 : }
1469 :
1470 : fd_hash_t const *
1471 : fd_tower_blocks_canonical_block_id( fd_tower_t * tower,
1472 0 : ulong slot ) {
1473 0 : fd_tower_blk_t * blk = blk_map_ele_query( tower->blk_map, &slot, NULL, tower->blk_pool );
1474 0 : if( FD_UNLIKELY( !blk ) ) return NULL;
1475 0 : if ( FD_LIKELY( blk->confirmed ) ) return &blk->confirmed_block_id;
1476 0 : else if( FD_LIKELY( blk->voted ) ) return &blk->voted_block_id;
1477 0 : else return &blk->replayed_block_id;
1478 0 : }
1479 :
1480 : fd_tower_blk_t *
1481 702 : fd_tower_blocks_query( fd_tower_t * tower, ulong slot ) {
1482 702 : return blk_map_ele_query( tower->blk_map, &slot, NULL, tower->blk_pool );
1483 702 : }
1484 :
1485 : fd_tower_blk_t *
1486 : fd_tower_blocks_insert( fd_tower_t * tower,
1487 : ulong slot,
1488 276 : ulong parent_slot ) {
1489 276 : FD_TEST( blk_pool_free( tower->blk_pool ) );
1490 276 : fd_tower_blk_t * blk = blk_pool_ele_acquire( tower->blk_pool );
1491 :
1492 276 : memset( blk, 0, sizeof(fd_tower_blk_t) );
1493 276 : blk->parent_slot = parent_slot;
1494 276 : blk->slot = slot;
1495 276 : blk->prev_leader_slot = ULONG_MAX;
1496 276 : blk_map_ele_insert( tower->blk_map, blk, tower->blk_pool );
1497 276 : return blk;
1498 276 : }
1499 :
1500 : void
1501 : fd_tower_blocks_remove( fd_tower_t * tower,
1502 6 : ulong slot ) {
1503 6 : fd_tower_blk_t * blk = blk_map_ele_query( tower->blk_map, &slot, NULL, tower->blk_pool );
1504 6 : if( FD_LIKELY( blk ) ) {
1505 3 : blk_map_ele_remove_fast( tower->blk_map, blk, tower->blk_pool );
1506 3 : blk_pool_ele_release( tower->blk_pool, blk );
1507 3 : }
1508 6 : }
1509 :
1510 : /* Lockos implementation */
1511 :
1512 : void
1513 : fd_tower_lockos_insert( fd_tower_t * tower,
1514 : ulong slot,
1515 : fd_hash_t const * addr,
1516 144 : fd_tower_vote_t * votes ) {
1517 :
1518 144 : lockout_interval_map_t * lck_map = tower->lck_map;
1519 144 : lockout_interval_t * lck_pool = tower->lck_pool;
1520 :
1521 144 : for( fd_tower_vote_iter_t iter = fd_tower_vote_iter_init( votes );
1522 288 : !fd_tower_vote_iter_done( votes, iter );
1523 144 : iter = fd_tower_vote_iter_next( votes, iter ) ) {
1524 144 : fd_tower_vote_t const * vote = fd_tower_vote_iter_ele_const( votes, iter );
1525 144 : ulong interval_start = vote->slot;
1526 144 : ulong interval_end = vote->slot + ( 1UL << vote->conf );
1527 144 : ulong key = lockout_interval_key( slot, interval_end );
1528 :
1529 144 : if( !lockout_interval_map_ele_query( lck_map, &key, NULL, lck_pool ) ) {
1530 : /* Insert sentinel for pruning. key = fork_slot | 0, start = interval_end. */
1531 135 : ulong sentinel_key = lockout_interval_key( slot, 0 );
1532 135 : FD_TEST( lockout_interval_pool_free( lck_pool ) );
1533 135 : lockout_interval_t * sentinel = lockout_interval_pool_ele_acquire( lck_pool );
1534 135 : sentinel->key = sentinel_key;
1535 135 : sentinel->start = interval_end;
1536 135 : lockout_interval_map_ele_insert( lck_map, sentinel, lck_pool );
1537 135 : }
1538 :
1539 144 : FD_TEST( lockout_interval_pool_free( lck_pool ) );
1540 144 : lockout_interval_t * interval = lockout_interval_pool_ele_acquire( lck_pool );
1541 144 : interval->key = key;
1542 144 : interval->addr = *addr;
1543 144 : interval->start = interval_start;
1544 144 : FD_TEST( lockout_interval_map_ele_insert( lck_map, interval, lck_pool ) );
1545 144 : }
1546 144 : }
1547 :
1548 : void
1549 : fd_tower_lockos_remove( fd_tower_t * tower,
1550 18 : ulong slot ) {
1551 :
1552 18 : lockout_interval_map_t * lck_map = tower->lck_map;
1553 18 : lockout_interval_t * lck_pool = tower->lck_pool;
1554 :
1555 18 : ulong sentinel_key = lockout_interval_key( slot, 0 );
1556 18 : for( lockout_interval_t * sentinel = lockout_interval_map_ele_remove( lck_map, &sentinel_key, NULL, lck_pool );
1557 120 : sentinel;
1558 102 : sentinel = lockout_interval_map_ele_remove( lck_map, &sentinel_key, NULL, lck_pool ) ) {
1559 102 : ulong interval_end = sentinel->start;
1560 102 : lockout_interval_pool_ele_release( lck_pool, sentinel );
1561 :
1562 102 : ulong key = lockout_interval_key( slot, interval_end );
1563 102 : for( lockout_interval_t * itrvl = lockout_interval_map_ele_remove( lck_map, &key, NULL, lck_pool );
1564 204 : itrvl;
1565 102 : itrvl = lockout_interval_map_ele_remove( lck_map, &key, NULL, lck_pool ) ) {
1566 102 : lockout_interval_pool_ele_release( lck_pool, itrvl );
1567 102 : }
1568 102 : }
1569 18 : }
|
