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