Line data Source code
1 : #ifndef HEADER_fd_src_choreo_tower_fd_tower_forks_h
2 : #define HEADER_fd_src_choreo_tower_fd_tower_forks_h
3 :
4 : #include "../fd_choreo_base.h"
5 : #include "fd_tower_accts.h"
6 :
7 : /* fd_tower_forks maintains fork information for tower, such as whether
8 : slots are on the same or different forks. Importantly, parentage is
9 : based purely on slot numbers as opposed to block ids, so in cases of
10 : equivocation (duplicate blocks), tower will consider something an
11 : ancestor or descendant even if the block ids do not chain. This is
12 : different from fd_ghost and fd_notar, which both track block ids.
13 :
14 : Instead, fd_tower_forks maintains two block_id fields on every slot.
15 : The first is the block_id that we voted on for that slot. In case of
16 : duplicates, this is the first version of the block we replayed and
17 : voted on. The second is the block_id that was duplicate confirmed
18 : (voted on by >=52% of stake). This may or may not equal the block_id
19 : we voted on. It also may or may not be populated. It is possible
20 : but highly unlikely for confirmed_block_id to never be populated
21 : before the slot is pruned during rooting.
22 :
23 : This behavior intentionally mirrors the Agave logic implemented in
24 : `make_check_switch_threshold_decision`. Essentially, tower is unable
25 : to distinguish duplicates because the vote account format (in which
26 : towers are stored) only stores slot numbers and not block_ids. */
27 :
28 : struct fd_tower_forks {
29 : ulong slot; /* map key */
30 : ulong parent_slot; /* parent slot */
31 : int confirmed; /* whether this slot has been duplicate confirmed */
32 : fd_hash_t confirmed_block_id; /* the block_id that was duplicate confirmed */
33 : int voted; /* whether we voted for this slot yet */
34 : fd_hash_t voted_block_id; /* the block_id we voted on for this slot */
35 : fd_hash_t replayed_block_id; /* the block_id we _first_ replayed for this slot */
36 : ulong bank_idx; /* pool idx of the bank as of this replayed block */
37 : };
38 : typedef struct fd_tower_forks fd_tower_forks_t;
39 :
40 : #define MAP_NAME fd_tower_forks
41 1563 : #define MAP_T fd_tower_forks_t
42 2709 : #define MAP_KEY slot
43 1152 : #define MAP_KEY_NULL ULONG_MAX
44 1557 : #define MAP_KEY_INVAL(key) ((key)==ULONG_MAX)
45 : #define MAP_MEMOIZE 0
46 : #include "../../util/tmpl/fd_map_dynamic.c"
47 :
48 : /* using map chain for ease of threading a linkedlist through the leaves
49 : for fast iteration. (needed for switch check) */
50 : struct fd_tower_leaf {
51 : ulong slot; /* map key */
52 : ulong hash; /* reserved for fd_map_chain and fd_pool */
53 : ulong next; /* next leaf in the linked list */
54 : ulong prev; /* prev leaf in the linked list */
55 : };
56 : typedef struct fd_tower_leaf fd_tower_leaf_t;
57 :
58 : #define MAP_NAME fd_tower_leaves_map
59 : #define MAP_ELE_T fd_tower_leaf_t
60 117 : #define MAP_KEY slot
61 201 : #define MAP_NEXT hash
62 : #include "../../util/tmpl/fd_map_chain.c"
63 :
64 : #define POOL_NAME fd_tower_leaves_pool
65 18 : #define POOL_T fd_tower_leaf_t
66 777 : #define POOL_NEXT hash
67 : #include "../../util/tmpl/fd_pool.c"
68 :
69 : #define DLIST_NAME fd_tower_leaves_dlist
70 : #define DLIST_ELE_T fd_tower_leaf_t
71 : #include "../../util/tmpl/fd_dlist.c"
72 :
73 : /* tower_forks also tracks a map of lockout intervals.
74 : We need to track a list of lockout intervals per validator per slot.
75 : Ex.
76 : After executing slot 33, validator A votes for slot 32, has a tower
77 : vote | confirmation count | lockout interval
78 : ----- | -------------------|------------------
79 : 32 | 1 | [32, 33]
80 : 2 | 3 | [2, 6]
81 : 1 | 4 | [1, 9]
82 :
83 : Thw lockout interval is the interval of slots that the validator is
84 : locked out from voting for if they want to switch off that vote. For
85 : example if validator A wants to switch off fork 1, they have to wait
86 : until slot 9.
87 :
88 : Agave tracks a similar structure.
89 :
90 : key: for an interval [vote, vote+lockout] for validator A,
91 : it is stored like:
92 : vote+lockout -> (vote, validator A) -> (2, validator B) -> (any other vote, any other validator)
93 :
94 : Since a validator can have up to 31 entries in the tower, and we have
95 : a max_vote_accounts, we can pool the interval objects to be
96 : 31*max_vote_accounts entries PER bank / executed slot. We can also
97 : string all the intervals of the same bank together as a linkedlist.
98 : */
99 :
100 : struct fd_lockout_intervals {
101 : ulong key; /* fork_slot << 32 | end_interval */
102 : ulong next; /* reserved for fd_map_chain and fd_pool */
103 : fd_hash_t vote_account_pubkey;
104 : ulong interval_start; /* start of interval, also vote slot */
105 : };
106 : typedef struct fd_lockout_intervals fd_lockout_intervals_t;
107 :
108 : #define MAP_NAME fd_lockout_intervals_map
109 9 : #define MAP_ELE_T fd_lockout_intervals_t
110 : #define MAP_MULTI 1
111 39 : #define MAP_KEY key
112 57 : #define MAP_NEXT next
113 : #include "../../util/tmpl/fd_map_chain.c"
114 :
115 : #define POOL_NAME fd_lockout_intervals_pool
116 18 : #define POOL_T fd_lockout_intervals_t
117 294960 : #define POOL_NEXT next
118 : #include "../../util/tmpl/fd_pool.c"
119 :
120 : struct fd_lockout_slots {
121 : ulong fork_slot;
122 : ulong next; /* reserved for fd_map_chain and fd_pool */
123 : ulong interval_end;
124 : };
125 : typedef struct fd_lockout_slots fd_lockout_slots_t;
126 :
127 : #define MAP_NAME fd_lockout_slots_map
128 6 : #define MAP_ELE_T fd_lockout_slots_t
129 : #define MAP_MULTI 1
130 30 : #define MAP_KEY fork_slot
131 57 : #define MAP_NEXT next
132 : #include "../../util/tmpl/fd_map_chain.c"
133 :
134 : #define POOL_NAME fd_lockout_slots_pool
135 18 : #define POOL_T fd_lockout_slots_t
136 294951 : #define POOL_NEXT next
137 : #include "../../util/tmpl/fd_pool.c"
138 :
139 : static inline ulong
140 69 : fd_lockout_interval_key( ulong fork_slot, ulong end_interval ) {
141 69 : return (fork_slot << 32) | end_interval;
142 69 : }
143 : struct __attribute__((aligned(128UL))) fd_forks {
144 : fd_tower_forks_t * tower_forks;
145 : fd_tower_leaves_map_t * tower_leaves_map;
146 : fd_tower_leaves_dlist_t * tower_leaves_dlist;
147 : fd_tower_leaf_t * tower_leaves_pool;
148 :
149 : fd_lockout_slots_map_t * lockout_slots_map;
150 : fd_lockout_slots_t * lockout_slots_pool;
151 :
152 : fd_lockout_intervals_map_t * lockout_intervals_map;
153 : fd_lockout_intervals_t * lockout_intervals_pool;
154 : };
155 : typedef struct fd_forks fd_forks_t;
156 :
157 : FD_PROTOTYPES_BEGIN
158 :
159 27 : #define FD_LOCKOUT_ENTRY_MAX (31UL) /* should be same as FD_TOWER_VOTE_MAX */
160 :
161 : FD_FN_CONST static inline ulong
162 81 : fd_forks_align( void ) {
163 81 : return alignof(fd_forks_t);
164 81 : }
165 :
166 : FD_FN_CONST static inline ulong
167 18 : fd_forks_footprint( ulong slot_max, ulong voter_max ) {
168 18 : ulong interval_max = fd_ulong_pow2_up( FD_LOCKOUT_ENTRY_MAX*slot_max*voter_max );
169 18 : int lg_slot_max = fd_ulong_find_msb( fd_ulong_pow2_up( slot_max ) ) + 1;
170 18 : return FD_LAYOUT_FINI(
171 18 : FD_LAYOUT_APPEND(
172 18 : FD_LAYOUT_APPEND(
173 18 : FD_LAYOUT_APPEND(
174 18 : FD_LAYOUT_APPEND(
175 18 : FD_LAYOUT_APPEND(
176 18 : FD_LAYOUT_APPEND(
177 18 : FD_LAYOUT_APPEND(
178 18 : FD_LAYOUT_APPEND(
179 18 : FD_LAYOUT_APPEND(
180 18 : FD_LAYOUT_INIT,
181 18 : alignof(fd_forks_t), sizeof(fd_forks_t) ),
182 : /* Fork structures */
183 18 : fd_tower_forks_align(), fd_tower_forks_footprint ( lg_slot_max ) ),
184 18 : fd_tower_leaves_map_align(), fd_tower_leaves_map_footprint ( slot_max ) ),
185 18 : fd_tower_leaves_dlist_align(), fd_tower_leaves_dlist_footprint ( ) ),
186 18 : fd_tower_leaves_pool_align(), fd_tower_leaves_pool_footprint ( slot_max ) ),
187 : /* Lockout interval structures */
188 18 : fd_lockout_slots_map_align(), fd_lockout_slots_map_footprint ( slot_max ) ),
189 18 : fd_lockout_slots_pool_align(), fd_lockout_slots_pool_footprint ( interval_max ) ),
190 18 : fd_lockout_intervals_map_align(), fd_lockout_intervals_map_footprint ( interval_max ) ),
191 18 : fd_lockout_intervals_pool_align(), fd_lockout_intervals_pool_footprint( interval_max ) ),
192 18 : fd_forks_align() );
193 18 : }
194 :
195 : void *
196 : fd_forks_new( void * shmem, ulong slot_max, ulong voter_max );
197 :
198 : fd_forks_t *
199 : fd_forks_join( void * shforks );
200 :
201 : int
202 : fd_forks_is_slot_ancestor( fd_forks_t * forks,
203 : ulong descendant_slot,
204 : ulong ancestor_slot );
205 :
206 : int
207 : fd_forks_is_slot_descendant( fd_forks_t * forks,
208 : ulong ancestor_slot,
209 : ulong descendant_slot );
210 :
211 : /* fd_forks_lowest_common_ancestor returns the lowest common
212 : ancestor of slot1 and slot 2. There is always an LCA in a valid
213 : tower_forks tree (the root). */
214 :
215 : ulong
216 : fd_forks_lowest_common_ancestor( fd_forks_t * forks,
217 : ulong slot1,
218 : ulong slot2 );
219 :
220 : /* fd_forks_canonical_block_id returns what we think to be the
221 : correct block id for a given slot, based on what we've observed.
222 :
223 : We prioritize in-order:
224 : 1. the confirmed block id
225 : 2. our voted block id
226 : 3. replayed block id
227 :
228 : This is the canonical order because it reflects what we think is the
229 : "true" block id given the information we have.
230 :
231 : Agave behaves similarly, except they "purge" their replay bank hash
232 : so they're always comparing the confirmed block id */
233 :
234 : fd_hash_t const *
235 : fd_forks_canonical_block_id( fd_forks_t * forks,
236 : ulong slot );
237 :
238 : fd_tower_forks_t *
239 : fd_forks_insert( fd_forks_t * forks,
240 : ulong slot,
241 : ulong parent_slot );
242 :
243 : fd_tower_forks_t *
244 : fd_forks_confirmed( fd_tower_forks_t * fork,
245 : fd_hash_t const * block_id );
246 :
247 : fd_tower_forks_t *
248 : fd_forks_replayed( fd_forks_t * forks,
249 : fd_tower_forks_t * fork,
250 : ulong bank_idx,
251 : fd_hash_t const * block_id );
252 :
253 : fd_tower_forks_t *
254 : fd_forks_voted( fd_tower_forks_t * fork,
255 : fd_hash_t const * block_id );
256 :
257 : fd_tower_forks_t *
258 : fd_forks_query( fd_forks_t * forks, ulong slot );
259 :
260 : int
261 : fd_forks_remove( fd_forks_t * forks, ulong slot );
262 :
263 : void
264 : fd_forks_lockouts_add( fd_forks_t * forks,
265 : ulong fork_slot,
266 : fd_hash_t const * vote_account_pubkey,
267 : fd_tower_accts_t * acct );
268 :
269 : void
270 : fd_forks_lockouts_clear( fd_forks_t * forks, ulong fork_slot );
271 :
272 : FD_PROTOTYPES_END
273 :
274 : #endif /* HEADER_fd_src_choreo_tower_fd_tower_forks_h */
|
