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