Line data Source code
1 : #ifndef HEADER_fd_src_disco_repair_fd_repair_h
2 : #define HEADER_fd_src_disco_repair_fd_repair_h
3 :
4 : /* fd_repair tracks the root and the blocks of the slots after it as
5 : they are received over the network via Turbine and Repair, keeps the
6 : blocks that still need repair for the tile to request, and queues
7 : their FEC sets for replay on the reasm deque.
8 :
9 : A slot can have more than one block (blk). The eager blk is built by
10 : position from every shred of the slot, before its block id is known,
11 : and gets its block id (the double merkle root, dmr) when it
12 : completes. Named blks carry a dmr from a cert, a votor repair event
13 : or a child's block header, and are repaired by that id. When the
14 : eager blk completes with the dmr of a named blk, they are the same
15 : block and are merged.
16 :
17 : Every blk but the root has a parent (the blk its block header names
18 : by parent slot and dmr, known from shred 0 or a ParentAndFecCount
19 : response) and children (the blks linked under it). A blk is linked
20 : under its parent once the parent is held. A named blk creates its
21 : parent if it is missing, an eager blk waits unlinked as an orphan.
22 :
23 : fd_repair always queues a parent before its child: a blk's first FEC
24 : set is queued only after its parent's last (the root counts as
25 : delivered), then its complete FEC sets are queued in index order.
26 : This guarantees that every fork will be delivered in-order, except
27 : that our own leader blk goes to the head of the deque, and so does a
28 : chain that replay asks to be delivered again from the root. Forks
29 : are treated as concurrent, and thus fd_repair only provides a partial
30 : ordering such that it makes no guarantees about the delivery order of
31 : FEC sets across forks, but in general this will be the order in which
32 : they become ready.
33 :
34 : Forks manifest in fd_repair as a blk with more than one child, and
35 : mostly occur across slots due to leader skipping. For example, the
36 : leader for slot 14 forks slot 9 when another leader already built
37 : slot 10 from slot 9, so now the blk of slot 9 has two child blks ie.
38 : the blk of slot 10 and the blk of slot 14.
39 :
40 : There is a protocol violation called equivocation (also known as
41 : "duplicates") that can also cause forks. Unlike skips, equivocation
42 : is not honest behavior and only happens when validators are behaving
43 : maliciously or their software has a bug. Equivocation can result in
44 : two or more blks for the _same_ slot. Moreover, there might be two
45 : FEC sets with the same slot and FEC set index but different payloads.
46 :
47 : fd_repair invalidates the slot when the shreds of the eager blk
48 : conflict (multiple merkle roots for the same FEC set idx, a parent
49 : slot mismatch, a bad block header, or multiple shreds marked
50 : slot_complete), when a proven FEC set root disagrees with it, or when
51 : replay marks it dead. The eager blk is then no longer repaired, no
52 : more of its FEC sets are queued unless it completed first, and the
53 : slot is only reachable by block id. */
54 :
55 : #include "../../disco/fd_disco_base.h"
56 : #include "../../disco/shred/fd_fec_set.h"
57 : #include "../../choreo/votor/fd_votor_base.h"
58 : #include "../../choreo/fd_choreo_base.h"
59 : #include "../../flamenco/alpenglow/fd_block_marker.h"
60 :
61 : struct fd_mr20 {
62 : uchar uc[ 20 ];
63 : };
64 : typedef struct fd_mr20 fd_mr20_t;
65 :
66 : struct fd_mr32 {
67 : uchar uc[ 32 ];
68 : };
69 : typedef struct fd_mr32 fd_mr32_t;
70 :
71 : union fd_mr {
72 : fd_mr20_t mr20;
73 : fd_mr32_t mr32;
74 : };
75 : typedef union fd_mr fd_mr_t;
76 :
77 : typedef struct fd_repair_blk fd_repair_blk_t;
78 :
79 : struct fd_repair_fec {
80 : fd_mr_t mr;
81 : ulong slot;
82 : uint fec_idx;
83 : uint next;
84 : uint prev;
85 : uint data_rcvd; /* bit j set if repair holds data shred j, until it completes. then the shred tile masks: bit j set if the data shred with in-type index j was received (vs recovered) */
86 : uint parity_rcvd; /* ... if the parity shred with in-type index j was received */
87 : uint repair_rcvd; /* ... if the data shred with in-type index j arrived by repair */
88 : uchar fec_complete : 1;
89 : uchar data_complete : 1;
90 : uchar is_leader : 1;
91 : uchar is_notar : 1;
92 :
93 : /* block marker */
94 :
95 : fd_update_parent_t update_parent;
96 :
97 : /* metrics */
98 :
99 : long first_ts; /* when its first shred arrived, 0 if none yet */
100 : long cmpl_ts; /* when it first completed, 0 if not yet */
101 : };
102 : typedef struct fd_repair_fec fd_repair_fec_t;
103 : FD_STATIC_ASSERT( sizeof(fd_repair_fec_t)==128UL, fd_repair_fec );
104 :
105 : #define POOL_NAME fd_repair_fec_pool
106 2016 : #define POOL_T fd_repair_fec_t
107 : #define POOL_IDX_T uint
108 : #include "../../util/tmpl/fd_pool.c"
109 :
110 : #define MAP_NAME fd_repair_fec_map
111 0 : #define MAP_ELE_T fd_repair_fec_t
112 317348 : #define MAP_IDX_T uint
113 : #define MAP_KEY_T fd_mr_t
114 4556 : #define MAP_KEY mr
115 154440 : #define MAP_KEY_EQ(k0,k1) (!memcmp((k0)->mr20.uc,(k1)->mr20.uc,sizeof(fd_mr20_t)))
116 160447 : #define MAP_KEY_HASH(key,seed) fd_ulong_hash((seed)^FD_LOAD(ulong,(key)->mr20.uc))
117 : #define MAP_OPTIMIZE_RANDOM_ACCESS_REMOVAL 1
118 : #include "../../util/tmpl/fd_map_chain.c"
119 :
120 : struct fd_repair_blk {
121 : ulong slot;
122 : fd_mr32_t dmr;
123 :
124 : /* blk_map */
125 :
126 : ulong prev;
127 : ulong next;
128 :
129 : /* blk_orphan_map */
130 :
131 : ulong orphan_prev;
132 : ulong orphan_next;
133 :
134 : /* {eager, notar, final}_treap */
135 :
136 : struct {
137 : ulong parent;
138 : ulong left;
139 : ulong right;
140 : ulong prio; /* seeded once at pool creation */
141 : } treap;
142 :
143 : /* blks form a left-child, right-sibling tree at root. */
144 :
145 : ulong parent; /* blk_pool idx of the parent blk, null if not linked */
146 : ulong child; /* blk_pool idx of the first child */
147 : ulong sibling; /* blk_pool idx of the next child of the same parent */
148 :
149 : uint cmpl_fec_cnt; /* FEC set count of the slot, 0 if not yet known */
150 : uint rcvd_fec_cnt; /* one past the highest FEC set received, there can be gaps below */
151 : uint buff_fec_cnt; /* FEC sets [0,buff_fec_cnt) are complete */
152 : uint cons_fec_cnt; /* FEC sets [init_fec_cnt,cons_fec_cnt) are consumed by replay, init_fec_cnt until the parent is consumed in full */
153 : uint wait_fec_cnt; /* FEC sets [0,wait_fec_cnt) are complete or have a repair req waiting, kept by the tile */
154 : uint init_fec_cnt; /* FEC set of its UpdateParent, replay starts there, 0 if none */
155 :
156 : ulong parent_slot; /* the parent slot, potentially changed during the block by UpdateParent */
157 : fd_mr32_t parent_dmr; /* the parent dmr */
158 : ulong init_parent_slot; /* the initial parent slot before any UpdateParent. */
159 :
160 : /* repair, the treap is the blk's role in its slot_meta */
161 :
162 : uchar eager : 1; /* the slot's eager blk, and may be repaired by position */
163 : uchar meta_req : 1; /* tile: a META req was made */
164 : uchar highest_req : 1; /* tile: a HIGHEST req was made */
165 : uchar orphan_req : 1; /* tile: an ORPHAN req was made */
166 :
167 : ulong * fecs; /* fec_pool idx of each FEC set, null if none, fec_blk_max of them */
168 :
169 : long eager_ts; /* eager_ts + eager_delta signals when to start eagerly repairing */
170 :
171 : struct {
172 : uchar cancelled_reason; /* FD_EVENT_BLOCK_RECEIVED_CANCELLED_REASON_*, 0 if never cancelled */
173 : uchar reported; /* given to the report callback, at completion or when freed */
174 : long cancelled_ts; /* when cancelled_reason was first set, 0 if never cancelled */
175 : uint last_cmpl_fec_idx; /* fec_set_idx of the FEC set that most recently completed, UINT_MAX if none */
176 : long last_shred_ts; /* when the blk became contiguous through a FEC set completion, 0 if it has not */
177 : uint turbine_shred_cnt; /* turbine data and coding shreds of its FEC sets, as counted by the shred tile */
178 : uint repair_shred_cnt; /* repair shreds of its FEC sets, as counted by the shred tile */
179 : uint recovered_shred_cnt; /* shreds of its FEC sets recovered from coding shreds */
180 :
181 : /* tile: sent requests, by FD_REPAIR_SERDE_TAG_*, a FEC set req counts once per shred asked for */
182 :
183 : uint req_window_cnt;
184 : uint req_highest_cnt;
185 : uint req_orphan_cnt;
186 : uint req_shred_bid_cnt;
187 : uint req_parent_cnt;
188 : uint req_fec_root_cnt;
189 : long first_req_ts; /* tile: when the first req of any kind was sent, 0 if none */
190 :
191 : /* tile: verified responses to its pending requests */
192 :
193 : uint shred_res_cnt; /* repair shreds matched to a pending window or ShredForBlockId req */
194 : uint parent_res_cnt; /* ParentAndFecCount responses */
195 : uint fec_root_res_cnt; /* FecRoot responses */
196 : long last_shred_res_ts; /* when the last matched repair shred arrived, 0 if none */
197 : long first_meta_res_ts; /* when the first ParentAndFecCount or FecRoot response arrived, 0 if none */
198 : } telemetry;
199 : };
200 : typedef struct fd_repair_blk fd_repair_blk_t;
201 :
202 : /* blk_map is keyed by slot and holds every blk of a slot. */
203 :
204 : #define POOL_NAME fd_repair_blk_pool
205 2015 : #define POOL_T fd_repair_blk_t
206 : #define POOL_IDX_T uint
207 : #include "../../util/tmpl/fd_pool.c"
208 :
209 : #define MAP_NAME fd_repair_blk_map
210 23773 : #define MAP_ELE_T fd_repair_blk_t
211 2009 : #define MAP_KEY slot
212 : #define MAP_MULTI 1
213 : #define MAP_OPTIMIZE_RANDOM_ACCESS_REMOVAL 1
214 : #include "../../util/tmpl/fd_map_chain.c"
215 :
216 : /* every unlinked blk but the root waits in the orphan map, keyed by
217 : the dmr of the parent it names, null until it names one. */
218 :
219 : #define MAP_NAME fd_repair_blk_orphan_map
220 3010 : #define MAP_ELE_T fd_repair_blk_t
221 : #define MAP_KEY_T fd_mr32_t
222 6020 : #define MAP_KEY parent_dmr
223 6020 : #define MAP_NEXT orphan_next
224 3010 : #define MAP_PREV orphan_prev
225 0 : #define MAP_KEY_EQ(k0,k1) (!memcmp((k0),(k1),sizeof(fd_mr32_t)))
226 7012 : #define MAP_KEY_HASH(key,seed) fd_ulong_hash((seed)^FD_LOAD(ulong,(key)->uc))
227 : #define MAP_MULTI 1
228 : #define MAP_OPTIMIZE_RANDOM_ACCESS_REMOVAL 1
229 : #include "../../util/tmpl/fd_map_chain.c"
230 :
231 : #define TREAP_NAME fd_repair_treap
232 : #define TREAP_T fd_repair_blk_t
233 : #define TREAP_QUERY_T fd_repair_blk_t const *
234 7549 : #define TREAP_CMP(q,e) ((int)((q)->slot>(e)->slot || ((q)->slot==(e)->slot && (q)>(e))) - (int)((q)->slot<(e)->slot || ((q)->slot==(e)->slot && (q)<(e))))
235 0 : #define TREAP_LT(e0,e1) ((e0)->slot<(e1)->slot || ((e0)->slot==(e1)->slot && (e0)<(e1)))
236 3017 : #define TREAP_PARENT treap.parent
237 10566 : #define TREAP_LEFT treap.left
238 10566 : #define TREAP_RIGHT treap.right
239 7089 : #define TREAP_PRIO treap.prio
240 : #include "../../util/tmpl/fd_treap.c"
241 :
242 : /* slot_meta is a circular buffer. */
243 :
244 : struct __attribute__((aligned(32UL))) fd_repair_slot_meta {
245 : ulong slot; /* ULONG_MAX if none */
246 : uint eager_blk_idx; /* blk_pool idx of the eager blk, null if none */
247 : uint notar_blk_idx; /* blk_pool idx of the first notar or stronger blk, null if none */
248 : uint final_blk_idx; /* blk_pool idx of the finalized blk, null if none */
249 : uchar invalidated : 1; /* leader misbehaved: equivocated, conflicting parents, bad block header, etc. */
250 : uchar skipped : 1; /* the slot is finalized as skipped */
251 : uchar leader : 1; /* we are the slot's leader */
252 : };
253 : typedef struct fd_repair_slot_meta fd_repair_slot_meta_t;
254 : FD_STATIC_ASSERT( sizeof(fd_repair_slot_meta_t)==32UL, fd_repair_slot_meta );
255 :
256 : struct fd_repair_deque {
257 : uint blk_idx;
258 : uint fec_idx;
259 : };
260 : typedef struct fd_repair_deque fd_repair_deque_t;
261 :
262 : #define DEQUE_NAME fd_repair_deque
263 4557 : #define DEQUE_T fd_repair_deque_t
264 : #include "../../util/tmpl/fd_deque_dynamic.c"
265 :
266 : typedef void (* fd_repair_report_fn_t)( void * ctx, struct fd_repair_blk const * blk );
267 :
268 : struct fd_repair {
269 : ulong root;
270 : fd_repair_blk_t * root_blk; /* the root's blk, NULL if not held */
271 : ulong catchup_slot;
272 : int reconsume; /* replay sent a MISSING_FEC: the next FEC pushed onto reasm_deque goes with its ancestry from the root */
273 : ulong slot_max;
274 : ulong fec_blk_max; /* FEC sets per blk */
275 :
276 : fd_repair_slot_meta_t * slot_meta; /* indexed by slot % slot_max */
277 : fd_repair_blk_t * blk_pool;
278 : fd_repair_blk_map_t * blk_map;
279 : fd_repair_blk_orphan_map_t * orphan_map;
280 : fd_repair_fec_t * fec_pool;
281 : fd_repair_fec_map_t * fec_map;
282 : fd_repair_deque_t * reasm_deque;
283 : fd_repair_treap_t * eager_treap;
284 : fd_repair_treap_t * notar_treap;
285 : fd_repair_treap_t * final_treap;
286 :
287 : struct {
288 : fd_repair_report_fn_t report; /* called once per blk, when it completes or when it is freed incomplete, NULL disables */
289 : void * ctx;
290 : } telemetry;
291 : };
292 : typedef struct fd_repair fd_repair_t;
293 :
294 : FD_PROTOTYPES_BEGIN
295 :
296 : FD_FN_CONST ulong
297 : fd_repair_align( void );
298 :
299 : FD_FN_CONST ulong
300 : fd_repair_footprint( ulong slot_max,
301 : ulong fec_max,
302 : ulong fec_blk_max );
303 :
304 : void *
305 : fd_repair_new( void * shmem,
306 : ulong slot_max,
307 : ulong fec_max,
308 : ulong fec_blk_max,
309 : ulong seed );
310 :
311 : fd_repair_t *
312 : fd_repair_join( void * shrepair );
313 :
314 : void *
315 : fd_repair_leave( fd_repair_t const * self );
316 :
317 : void *
318 : fd_repair_delete( void * shrepair );
319 :
320 : void
321 : fd_repair_init( fd_repair_t * self,
322 : ulong root,
323 : fd_mr32_t const * root_blk_mr,
324 : fd_repair_report_fn_t report,
325 : void * report_ctx );
326 :
327 : void
328 : fd_repair_fini( fd_repair_t * self );
329 :
330 : /* replay_slot REPLAY_SIG_SLOT_DEAD
331 :
332 : replay rejected the blk. If it was the eager blk the slot is
333 : invalidated so turbine can't rebuild it. We do not prune the blk. If
334 : this blk gets finalized, we want to keep the block data so that if it
335 : gets re-delivered, we can notify replay that it is a finalized block
336 : so replay can detect a hard fork.
337 :
338 : latest_fec_idx is the highest fec_set_idx the dead bank held, not
339 : necessarily the one that failed. UINT_MAX means the death is final
340 : (alpenglow_fast_leader_handover is not active on the dead bank), so
341 : the blk is never exempted as an optimistic prefix. */
342 :
343 : void
344 : fd_repair_blk_dead( fd_repair_t * self,
345 : ulong slot,
346 : fd_mr32_t const * blk_mr,
347 : uint latest_fec_idx );
348 :
349 : /* votor_out FD_VOTOR_SIG_CERTED FINAL, FAST_FINAL
350 : votor_out FD_VOTOR_SIG_QUORUM IMPLICITLY_FINALIZED
351 :
352 : frees the slot's competing blks, creates the blk if we don't have it
353 : yet. */
354 :
355 : fd_repair_blk_t *
356 : fd_repair_blk_finalized( fd_repair_t * self,
357 : ulong slot,
358 : fd_mr32_t const * blk_mr,
359 : long ts );
360 :
361 : /* votor_out FD_VOTOR_SIG_CERTED NOTAR
362 : votor_out FD_VOTOR_SIG_REPAIR
363 :
364 : creates a blk to repair by blk id, NULL if we have it or the slot is
365 : settled. */
366 :
367 : fd_repair_blk_t *
368 : fd_repair_blk_notarized( fd_repair_t * self,
369 : ulong slot,
370 : fd_mr32_t const * blk_mr );
371 :
372 : /* net_repair ParentAndFecSetCount response
373 :
374 : after its proof verifies against the blk id. the FEC set count is now
375 : trusted, creates the parent blk if we don't have it. counts the
376 : response, arriving at ts, in the blk's telemetry. */
377 :
378 : fd_repair_blk_t *
379 : fd_repair_blk_parented( fd_repair_t * self,
380 : ulong slot,
381 : fd_mr32_t const * blk_mr,
382 : ulong parent_slot,
383 : fd_mr32_t const * parent_dmr,
384 : uint fec_set_cnt,
385 : long ts );
386 :
387 : /* votor_out FD_VOTOR_SIG_CERTED
388 : votor_out FD_VOTOR_SIG_REPAIR
389 :
390 : before the cert is handled. seeds an empty eager blk for every slot
391 : up to the cert as if turbine showed its first shred, assumes no
392 : skips, skipped slots are pruned by finality later. */
393 :
394 : void
395 : fd_repair_slot_catchup( fd_repair_t * self,
396 : ulong slot );
397 :
398 : /* shred_out SHRED_SIG_FEC_COMPLETE
399 : shred_out SHRED_SIG_FEC_COMPLETE_LEADER
400 : shred_out SHRED_SIG_FEC_COMPLETE_AGAIN
401 :
402 : the shred tile already inserted the FEC set into the store. computes
403 : the eager blk's dmr once it has every FEC set, our leader FECs go to
404 : the head of the reasm deque. {turbine,repair,recovered}_cnt
405 : are the FEC set's shred counts from the shred tile, added to the
406 : telemetry of each blk holding the FEC set on its first completion.
407 : {data,parity,repair}_rcvd are its received-shred masks from the
408 : shred tile, kept on the FEC set from its first completion. */
409 :
410 : fd_repair_fec_t *
411 : fd_repair_fec_complete( fd_repair_t * self,
412 : fd_shred_t const * last_shred,
413 : fd_mr32_t const * fec_mr,
414 : int is_leader,
415 : uint turbine_cnt,
416 : uint repair_cnt,
417 : uint recovered_cnt,
418 : uint data_rcvd,
419 : uint parity_rcvd,
420 : uint repair_rcvd,
421 : long ts );
422 :
423 : /* shred_out SHRED_SIG_FEC_EVICTED
424 :
425 : the resolver dropped an incomplete FEC set, so ask for every shred
426 : again. */
427 :
428 : void
429 : fd_repair_fec_evicted( fd_repair_t * self,
430 : ulong slot,
431 : uint fec_set_idx,
432 : fd_mr_t const * fec_mr );
433 :
434 : /* net_repair FecSetRoot response
435 :
436 : after its proof verifies against the blk id. fec_mr is the proven
437 : 20-byte prefix, the FEC set's shreds can be asked for by blk id now.
438 : counts the response, arriving at ts, in the blk's telemetry. */
439 :
440 : fd_repair_fec_t *
441 : fd_repair_fec_notarized( fd_repair_t * self,
442 : ulong slot,
443 : fd_mr32_t const * blk_mr,
444 : uint fec_set_idx,
445 : fd_mr_t const * fec_mr,
446 : long ts );
447 :
448 : /* replay_slot REPLAY_SIG_ROOT_ADVANCED
449 :
450 : wait for replay's signal to advance root because of redelivery
451 : nonsense. TODO remove this. */
452 :
453 : void
454 : fd_repair_root_advanced( fd_repair_t * self,
455 : ulong slot,
456 : fd_mr32_t const * blk_mr );
457 :
458 : /* shred_out SHRED_SIG_SRC_* data shreds
459 :
460 : special handling for idx 0 and the last shred idx. also called by
461 : fd_repair_fec_complete. */
462 :
463 : void
464 : fd_repair_shred_insert( fd_repair_t * self,
465 : fd_shred_t const * shred,
466 : fd_mr32_t const * fec_mr,
467 : long ts );
468 :
469 : /* shred_out SHRED_SIG_RESULT_EQVOC
470 :
471 : also called internally on a bad block header or conflicting
472 : parents. the eager blk is never repaired again, the slot is only
473 : reachable by blk id. reason is the eager blk's block_received
474 : cancelled_reason, ts its cancelled_time. */
475 :
476 : void
477 : fd_repair_slot_invalidated( fd_repair_t * self,
478 : ulong slot,
479 : int reason,
480 : long ts );
481 :
482 : /* slot must be the root or in the window after it, slots congruent mod
483 : slot_max share an entry, which is reset for slot first. */
484 :
485 : fd_repair_slot_meta_t *
486 : fd_repair_slot_meta( fd_repair_t * self,
487 : ulong slot );
488 :
489 : /* votor_out FD_VOTOR_SIG_QUORUM IMPLICITLY_SKIPPED
490 :
491 : SKIP-FINAL, a finalized descendant declares this slot skipped. frees
492 : the slot's blks, a skip cert alone is not final. */
493 :
494 : void
495 : fd_repair_slot_skipped( fd_repair_t * self,
496 : ulong slot );
497 :
498 : /* fd_repair_blk_treap_insert queues blk in its role's treap for the
499 : tile to discover its work. Returns 0 if already queued, or blk is an
500 : eager blk that is never repaired. */
501 :
502 : int
503 : fd_repair_blk_treap_insert( fd_repair_t * self,
504 : fd_repair_blk_t * blk );
505 :
506 : FD_PROTOTYPES_END
507 :
508 : #endif /* HEADER_fd_src_disco_repair_fd_repair_h */
|
