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