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