Line data Source code
1 : #ifndef HEADER_fd_src_choreo_rotor_fd_rotor_h
2 : #define HEADER_fd_src_choreo_rotor_fd_rotor_h
3 :
4 : #include "../../disco/fd_disco_base.h"
5 : #include "../../disco/shred/fd_fec_set.h"
6 : #include "../votor/ag_votor_base.h"
7 : #include "../fd_choreo_base.h"
8 :
9 : struct fd_mr20 {
10 : uchar uc[ FD_SHRED_MERKLE_NODE_SZ ];
11 : };
12 : typedef struct fd_mr20 fd_mr20_t;
13 :
14 : typedef fd_hash_t fd_mr32_t;
15 :
16 : /* FD_ROTOR_BLK_VERSION_{NUM,DEN} is the number of blk versions rotor
17 : holds per slot of its window, as the fraction NUM/DEN (2.5). With
18 : 20% of stake malicious and equivocating AG_EQVOC_BLOCK_HASH_MAX
19 : versions of each of its slots, the expected count is 2.2 per slot,
20 : 2.5 leaves headroom for the variance of the leader schedule (see
21 : store_fec_max in src/app/firedancer/topology.c, which sizes Store
22 : with the same factor). */
23 :
24 0 : #define FD_ROTOR_BLK_VERSION_NUM (5UL)
25 0 : #define FD_ROTOR_BLK_VERSION_DEN (2UL)
26 :
27 : /* fd_rotor_blk_max returns the number of blks a rotor with a window of
28 : slot_max slots holds, ie. ceil( slot_max*NUM/DEN ). */
29 :
30 : FD_FN_CONST static inline ulong
31 0 : fd_rotor_blk_max( ulong slot_max ) {
32 0 : return ( slot_max*FD_ROTOR_BLK_VERSION_NUM + FD_ROTOR_BLK_VERSION_DEN-1UL ) / FD_ROTOR_BLK_VERSION_DEN;
33 0 : }
34 :
35 : typedef struct fd_rotor_blk fd_rotor_blk_t;
36 :
37 : struct fd_rotor_fec {
38 : fd_mr20_t key;
39 : fd_mr32_t mr32;
40 : uint fec_idx;
41 : ulong slot;
42 : uint rcvd;
43 : uchar complete : 1;
44 : uchar data_complete : 1;
45 : uchar is_leader : 1;
46 : uchar notarized : 1;
47 : ulong next;
48 : ulong prev;
49 : uint data_rcvd; /* shred tile masks at first completion: bit j set if the data shred with in-type index j was received (vs recovered) */
50 : uint parity_rcvd; /* ... if the parity shred with in-type index j was received */
51 : uint repair_rcvd; /* ... if the data shred with in-type index j arrived by repair */
52 :
53 : int final_src; /* FD_EVENT_BLOCK_RECEIVED_FEC_SETS_FINAL_SHRED_SOURCE_* of the last data shred received before it completed, 0 if none */
54 : long first_ts; /* when its first shred arrived, 0 if none yet */
55 : long cmpl_ts; /* when it first completed, 0 if not yet */
56 : };
57 : typedef struct fd_rotor_fec fd_rotor_fec_t;
58 : FD_STATIC_ASSERT( sizeof(fd_rotor_fec_t)==120UL, fd_rotor_fec );
59 :
60 : #define POOL_NAME fd_rotor_fec_pool
61 0 : #define POOL_T fd_rotor_fec_t
62 : #include "../../util/tmpl/fd_pool.c"
63 :
64 : #define MAP_NAME fd_rotor_fec_map
65 0 : #define MAP_ELE_T fd_rotor_fec_t
66 : #define MAP_KEY_T fd_mr20_t
67 0 : #define MAP_KEY key
68 0 : #define MAP_KEY_EQ(k0,k1) (!memcmp((k0),(k1),sizeof(fd_mr20_t)))
69 0 : #define MAP_KEY_HASH(key,seed) fd_ulong_hash((seed)^FD_LOAD(ulong,(key)->uc))
70 : #define MAP_OPTIMIZE_RANDOM_ACCESS_REMOVAL 1
71 : #include "../../util/tmpl/fd_map_chain.c"
72 :
73 : struct fd_rotor_blk {
74 : ulong slot;
75 : fd_mr32_t dmr;
76 : ulong prev;
77 : ulong next;
78 :
79 : /* blks form a left-child, right-sibling tree at root. */
80 :
81 : ulong parent; /* blk_pool idx of the parent blk, null if not linked */
82 : ulong child; /* blk_pool idx of the first child */
83 : ulong sibling; /* blk_pool idx of the next child of the same parent */
84 :
85 : uint cmpl_fec_cnt; /* FEC set count of the slot, 0 if not yet known */
86 : uint rcvd_fec_cnt; /* one past the highest FEC set received, there can be gaps below */
87 : uint buff_fec_cnt; /* FEC sets [0,buff_fec_cnt) are complete */
88 : uint cons_fec_cnt; /* FEC sets [0,cons_fec_cnt) are consumed by replay, 0 until the parent is consumed in full */
89 : uint wait_fec_cnt; /* FEC sets [0,wait_fec_cnt) are complete or have a repair req waiting, kept by the tile */
90 :
91 : ulong parent_slot;
92 : fd_mr32_t parent_blk_mr;
93 : ulong orphan_next; /* orphan_map chain, while the blk waits for the blk named by parent_blk_mr */
94 : ulong orphan_prev;
95 :
96 : /* repair, the treap is the blk's role in its slot_meta */
97 :
98 : uchar in_blk_treap : 1; /* in its role's treap */
99 : uchar eager : 1; /* the slot's eager blk, and may be repaired by position */
100 : uchar meta_req : 1; /* tile: a META req was made */
101 : uchar highest_req : 1; /* tile: a HIGHEST req was made */
102 : uchar orphan_req : 1; /* tile: an ORPHAN req was made */
103 :
104 : ulong * fecs; /* fec_pool idx of each FEC set, null if none, fec_blk_max of them */
105 :
106 : long rcvd_fec_ts; /* when rcvd_fec_cnt last grew */
107 : struct {
108 : ulong parent;
109 : ulong left;
110 : ulong right;
111 : ulong prio; /* seeded once at pool creation */
112 : } treap;
113 :
114 : struct {
115 : uchar cancelled_reason; /* FD_EVENT_BLOCK_RECEIVED_CANCELLED_REASON_*, 0 if never cancelled */
116 : uchar reported; /* given to the report callback, at completion or when freed */
117 : long cancelled_ts; /* when cancelled_reason was first set, 0 if never cancelled */
118 : uint last_cmpl_fec_idx; /* fec_set_idx of the FEC set that most recently completed, UINT_MAX if none */
119 : long last_shred_ts; /* when the blk became contiguous through a FEC set completion, 0 if it has not */
120 : uint turbine_shred_cnt; /* turbine data and coding shreds of its FEC sets, as counted by the shred tile */
121 : uint repair_shred_cnt; /* repair shreds of its FEC sets, as counted by the shred tile */
122 : uint recovered_shred_cnt; /* shreds of its FEC sets recovered from coding shreds */
123 :
124 : /* tile: sent requests, by FD_ROTOR_SERDE_TAG_*, a FEC set req counts once per shred asked for */
125 :
126 : uint req_window_cnt;
127 : uint req_highest_cnt;
128 : uint req_orphan_cnt;
129 : uint req_shred_bid_cnt;
130 : uint req_parent_cnt;
131 : uint req_fec_root_cnt;
132 : long first_req_ts; /* tile: when the first req of any kind was sent, 0 if none */
133 :
134 : /* tile: verified responses to its pending requests */
135 :
136 : uint shred_res_cnt; /* repair shreds matched to a pending window or ShredForBlockId req */
137 : uint parent_res_cnt; /* ParentAndFecCount responses */
138 : uint fec_root_res_cnt; /* FecRoot responses */
139 : long last_shred_res_ts; /* when the last matched repair shred arrived, 0 if none */
140 : long first_meta_res_ts; /* when the first ParentAndFecCount or FecRoot response arrived, 0 if none */
141 : } telemetry;
142 : };
143 : typedef struct fd_rotor_blk fd_rotor_blk_t;
144 :
145 : /* blk_map is keyed by slot and holds every blk of a slot. */
146 :
147 : #define POOL_NAME fd_rotor_blk_pool
148 0 : #define POOL_T fd_rotor_blk_t
149 : #include "../../util/tmpl/fd_pool.c"
150 :
151 : #define MAP_NAME fd_rotor_blk_map
152 0 : #define MAP_ELE_T fd_rotor_blk_t
153 0 : #define MAP_KEY slot
154 : #define MAP_MULTI 1
155 : #define MAP_OPTIMIZE_RANDOM_ACCESS_REMOVAL 1
156 : #include "../../util/tmpl/fd_map_chain.c"
157 :
158 : /* orphan_map is keyed by parent_blk_mr and holds every unlinked blk
159 : that names a parent, ie. parent==null && parent_blk_mr!=hash_null,
160 : except the root blk. The blk named may not be held yet, be held
161 : under a different dmr (an eager blk) or never come. The key is the
162 : dmr alone, the parent slot is checked when linking.
163 :
164 : Each call site of add/remove should gate on the blk's state before
165 : its transition, the root blk is never in the map: it keeps the
166 : parent_blk_mr it was received with, but waits for nothing. */
167 :
168 : #define MAP_NAME fd_rotor_orphan_map
169 0 : #define MAP_ELE_T fd_rotor_blk_t
170 : #define MAP_KEY_T fd_mr32_t
171 0 : #define MAP_KEY parent_blk_mr
172 0 : #define MAP_NEXT orphan_next
173 0 : #define MAP_PREV orphan_prev
174 0 : #define MAP_KEY_EQ(k0,k1) (!memcmp((k0),(k1),sizeof(fd_mr32_t)))
175 0 : #define MAP_KEY_HASH(key,seed) fd_ulong_hash((seed)^FD_LOAD(ulong,(key)->uc))
176 : #define MAP_MULTI 1
177 : #define MAP_OPTIMIZE_RANDOM_ACCESS_REMOVAL 1
178 : #include "../../util/tmpl/fd_map_chain.c"
179 :
180 : #define TREAP_NAME fd_rotor_treap
181 : #define TREAP_T fd_rotor_blk_t
182 : #define TREAP_QUERY_T ulong
183 : #define TREAP_CMP(q,e) ((int)((q)>(e)->slot) - (int)((q)<(e)->slot))
184 0 : #define TREAP_LT(e0,e1) ((e0)->slot<(e1)->slot || ((e0)->slot==(e1)->slot && (e0)<(e1)))
185 0 : #define TREAP_PARENT treap.parent
186 0 : #define TREAP_LEFT treap.left
187 0 : #define TREAP_RIGHT treap.right
188 0 : #define TREAP_PRIO treap.prio
189 : #include "../../util/tmpl/fd_treap.c"
190 :
191 : /* slot_meta is a circular buffer. */
192 :
193 : struct fd_rotor_slot_meta {
194 : ulong slot; /* ULONG_MAX if none */
195 : ulong eager; /* blk_pool idx of the eager blk, null if none */
196 : ulong notar; /* blk_pool idx of the first notar or stronger blk, null if none */
197 : ulong final; /* blk_pool idx of the finalized blk, null if none */
198 : uint invalidated : 1; /* leader misbehaved: equivocated, conflicting parents, bad block header, etc. */
199 : uint skipped : 1; /* the slot is finalized as skipped */
200 : uint leader : 1; /* we are the slot's leader */
201 : };
202 : typedef struct fd_rotor_slot_meta fd_rotor_slot_meta_t;
203 :
204 : struct fd_rotor_deque {
205 : uint blk_idx;
206 : uint fec_idx;
207 : };
208 : typedef struct fd_rotor_deque fd_rotor_deque_t;
209 :
210 : #define DEQUE_NAME fd_rotor_deque
211 0 : #define DEQUE_T fd_rotor_deque_t
212 : #include "../../util/tmpl/fd_deque_dynamic.c"
213 :
214 : typedef void (* fd_rotor_report_fn_t)( void * ctx, struct fd_rotor_blk const * blk );
215 :
216 : struct fd_rotor {
217 : ulong root;
218 : fd_rotor_blk_t * root_blk; /* the root's blk, NULL if not held */
219 : ulong catchup_slot;
220 : int reconsume; /* replay sent a MISSING_FEC: the next FEC pushed onto reasm_deque goes with its ancestry from the root */
221 : ulong slot_max;
222 : ulong fec_blk_max; /* FEC sets per blk */
223 :
224 : fd_rotor_slot_meta_t * slot_meta; /* indexed by slot % slot_max */
225 : fd_rotor_blk_t * blk_pool;
226 : fd_rotor_blk_map_t * blk_map;
227 : fd_rotor_orphan_map_t * orphan_map;
228 : fd_rotor_fec_t * fec_pool;
229 : fd_rotor_fec_map_t * fec_map;
230 : fd_rotor_deque_t * reasm_deque;
231 : fd_rotor_treap_t * eager_treap; /* a blk is in its role's treap iff in_blk_treap */
232 : fd_rotor_treap_t * notar_treap;
233 : fd_rotor_treap_t * final_treap;
234 :
235 : struct {
236 : fd_rotor_report_fn_t report; /* called once per blk, when it completes or when it is freed incomplete, NULL disables */
237 : void * ctx;
238 : } telemetry;
239 : };
240 : typedef struct fd_rotor fd_rotor_t;
241 :
242 : FD_PROTOTYPES_BEGIN
243 :
244 : FD_FN_CONST ulong
245 : fd_rotor_align( void );
246 :
247 : FD_FN_CONST ulong
248 : fd_rotor_footprint( ulong slot_max,
249 : ulong fec_max,
250 : ulong fec_blk_max );
251 :
252 : void *
253 : fd_rotor_new( void * shmem,
254 : ulong slot_max,
255 : ulong fec_max,
256 : ulong fec_blk_max,
257 : ulong seed );
258 :
259 : fd_rotor_t *
260 : fd_rotor_join( void * shrotor );
261 :
262 : void *
263 : fd_rotor_leave( fd_rotor_t const * rotor );
264 :
265 : void *
266 : fd_rotor_delete( void * shrotor );
267 :
268 : void
269 : fd_rotor_init( fd_rotor_t * rotor,
270 : ulong root,
271 : fd_mr32_t const * root_blk_mr,
272 : fd_rotor_report_fn_t report,
273 : void * report_ctx );
274 :
275 : void
276 : fd_rotor_fini( fd_rotor_t * rotor );
277 :
278 : /* replay_slot REPLAY_SIG_SLOT_DEAD
279 :
280 : replay rejected the blk, prune it so it is never redelivered, and if
281 : it was the eager blk invalidate the slot so turbine can't rebuild it. */
282 :
283 : void
284 : fd_rotor_blk_dead( fd_rotor_t * rotor,
285 : ulong slot,
286 : fd_mr32_t const * blk_mr );
287 :
288 : /* votor_out FD_VOTOR_SIG_CERTED FINAL, FAST_FINAL
289 : votor_out FD_VOTOR_SIG_QUORUM IMPLICITLY_FINALIZED
290 :
291 : frees the slot's competing blks, creates the blk if we don't have it
292 : yet. */
293 :
294 : fd_rotor_blk_t *
295 : fd_rotor_blk_finalized( fd_rotor_t * rotor,
296 : ulong slot,
297 : fd_mr32_t const * blk_mr,
298 : long ts );
299 :
300 : /* votor_out FD_VOTOR_SIG_CERTED NOTAR
301 : votor_out FD_VOTOR_SIG_REPAIR
302 :
303 : creates a blk to repair by blk id, NULL if we have it or the slot is
304 : settled. */
305 :
306 : fd_rotor_blk_t *
307 : fd_rotor_blk_notarized( fd_rotor_t * rotor,
308 : ulong slot,
309 : fd_mr32_t const * blk_mr );
310 :
311 : /* net_repair ParentAndFecSetCount response
312 :
313 : after its proof verifies against the blk id. the FEC set count is now
314 : trusted, creates the parent blk if we don't have it. counts the
315 : response, arriving at ts, in the blk's telemetry. */
316 :
317 : fd_rotor_blk_t *
318 : fd_rotor_blk_parented( fd_rotor_t * rotor,
319 : ulong slot,
320 : fd_mr32_t const * blk_mr,
321 : ulong parent_slot,
322 : fd_mr32_t const * parent_blk_mr,
323 : uint fec_set_cnt,
324 : long ts );
325 :
326 : /* votor_out FD_VOTOR_SIG_CERTED
327 : votor_out FD_VOTOR_SIG_REPAIR
328 :
329 : before the cert is handled. seeds an empty eager blk for every slot
330 : up to the cert as if turbine showed its first shred, assumes no
331 : skips, skipped slots are pruned by finality later. */
332 :
333 : void
334 : fd_rotor_slot_catchup( fd_rotor_t * rotor,
335 : ulong slot );
336 :
337 : /* shred_out SHRED_SIG_FEC_COMPLETE
338 : shred_out SHRED_SIG_FEC_COMPLETE_LEADER
339 : shred_out SHRED_SIG_FEC_COMPLETE_AGAIN
340 :
341 : the shred tile already inserted the FEC set into the store. computes
342 : the eager blk's dmr once it has every FEC set, our leader FECs go to
343 : the head of the reasm deque. {turbine,repair,recovered}_cnt
344 : are the FEC set's shred counts from the shred tile, added to the
345 : telemetry of each blk holding the FEC set on its first completion.
346 : {data,parity,repair}_rcvd are its received-shred masks from the
347 : shred tile, kept on the FEC set from its first completion. */
348 :
349 : fd_rotor_fec_t *
350 : fd_rotor_fec_complete( fd_rotor_t * rotor,
351 : fd_shred_t const * last_shred,
352 : fd_mr32_t const * fec_mr,
353 : int is_leader,
354 : uint turbine_cnt,
355 : uint repair_cnt,
356 : uint recovered_cnt,
357 : uint data_rcvd,
358 : uint parity_rcvd,
359 : uint repair_rcvd,
360 : long ts );
361 :
362 : /* shred_out SHRED_SIG_FEC_EVICTED
363 :
364 : the resolver dropped an incomplete FEC set, so ask for every shred
365 : again. */
366 :
367 : void
368 : fd_rotor_fec_evicted( fd_rotor_t * rotor,
369 : ulong slot,
370 : uint fec_set_idx,
371 : fd_mr20_t const * fec_mr );
372 :
373 : /* net_repair FecSetRoot response
374 :
375 : after its proof verifies against the blk id. fec_mr is the proven
376 : 20-byte prefix, the FEC set's shreds can be asked for by blk id now.
377 : counts the response, arriving at ts, in the blk's telemetry. */
378 :
379 : fd_rotor_fec_t *
380 : fd_rotor_fec_notarized( fd_rotor_t * rotor,
381 : ulong slot,
382 : fd_mr32_t const * blk_mr,
383 : uint fec_set_idx,
384 : fd_mr20_t const * fec_mr,
385 : long ts );
386 :
387 : /* replay_slot REPLAY_SIG_ROOT_ADVANCED
388 :
389 : wait for replay's signal to advance root because of redelivery
390 : nonsense. TODO remove this. */
391 :
392 : void
393 : fd_rotor_root_advanced( fd_rotor_t * rotor,
394 : ulong slot,
395 : fd_mr32_t const * blk_mr );
396 :
397 : /* shred_out SHRED_SIG_SRC_* data shreds
398 :
399 : special handling for idx 0 and the last shred idx. also called by
400 : fd_rotor_fec_complete. src is the FD_EVENT_BLOCK_RECEIVED_FEC_SETS_
401 : FINAL_SHRED_SOURCE_* the shred arrived by, it becomes the FEC set's
402 : final_src until the set completes, 0 leaves final_src alone (eg. a
403 : reconstructed shred). */
404 :
405 : void
406 : fd_rotor_shred_insert( fd_rotor_t * rotor,
407 : fd_shred_t const * shred,
408 : fd_mr32_t const * fec_mr,
409 : int src,
410 : long ts );
411 :
412 : /* shred_out SHRED_SIG_RESULT_EQVOC
413 :
414 : also called internally on a bad block header or conflicting
415 : parents. the eager blk is never repaired again, the slot is only
416 : reachable by blk id. reason is the eager blk's block_received
417 : cancelled_reason, ts its cancelled_time. */
418 :
419 : void
420 : fd_rotor_slot_invalidated( fd_rotor_t * rotor,
421 : ulong slot,
422 : int reason,
423 : long ts );
424 :
425 : /* slot must be the root or in the window after it, slots congruent mod
426 : slot_max share an entry, which is reset for slot first. */
427 :
428 : fd_rotor_slot_meta_t *
429 : fd_rotor_slot_meta( fd_rotor_t * rotor,
430 : ulong slot );
431 :
432 : /* votor_out FD_VOTOR_SIG_QUORUM IMPLICITLY_SKIPPED
433 :
434 : SKIP-FINAL, a finalized descendant declares this slot skipped. frees
435 : the slot's blks, a skip cert alone is not final. */
436 :
437 : void
438 : fd_rotor_slot_skipped( fd_rotor_t * rotor,
439 : ulong slot );
440 :
441 : FD_PROTOTYPES_END
442 :
443 : #endif /* HEADER_fd_src_choreo_rotor_fd_rotor_h */
|
