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