Line data Source code
1 : #ifndef HEADER_fd_src_discof_forest_fd_forest_h
2 : #define HEADER_fd_src_discof_forest_fd_forest_h
3 :
4 : /* Forest is an API for repairing blocks as they are discovered from the
5 : cluster via Turbine or Gossip. Shreds (from Turbine) and
6 : confirmations (from Tower) inform forest that slot exists. Repair
7 : ensures that this block is received in its entirety by requesting
8 : repairs for missing shreds for the block.
9 :
10 : Note that forest needs to track the strict subset of shreds that are
11 : known by fec_resolver, store, and reasm. If any of these structures
12 : have evicted shreds, forest needs to clear out the corresponding FEC
13 : sets from forest to be re-requested. It's okay if shreds are evicted
14 : from reasm and we re-request for them and they pass through
15 : fec_resolver again. Although we could be creating duplicate ctxs,
16 : that's fine! We might later on get an evict notice for the second
17 : incomplete ctx but that's okay too!!! just have a bunch of useless
18 : messages that eventually will get ignored when we publish past it!!!!
19 :
20 : Like other fork-aware structures, forest maintains a tree that
21 : records the ancestry of slots. It also maintains references to the
22 : tips of each known fork (the frontier map), and also the latest
23 : slot we finished repairing on each fork (the consumed map). Any slot
24 : that doesn't have a known ancestry connecting it back to the root yet
25 : is part of the orphaned map. And the head of every orphaned tree is
26 : part of the subtrees map. While this seems very verbose, it allows
27 : for fast iteration and lookup of the different types of slots.
28 :
29 : fd_policy makes orphan requests that recover gaps between orphaned
30 : subtrees and the main ancestry tree, and then the forest iterator
31 : suggest repairs to make progress on the tree forwards (using BFS). */
32 :
33 : /* Merkle root tracking.
34 : For each FEC set in the slot, we record the merkle root of the first
35 : shred we receive in `mroots[ fec_set_idx / 32 ]`. Then for any
36 : shred in the same FEC inserted later, the merkle root of the new
37 : shred is compared to the merkle root we have stored.
38 :
39 : If they are the same -> good.
40 : If they are different -> we're going to mark this merkle root as
41 : incorrect. We do this by setting the merkle
42 : root to a null hash for later detection.
43 :
44 : Note we don't verify the chain on each FEC arrival, because we can't
45 : tell whether the CMR of the following FEC is incorrect or if the
46 : current MR we have is incorrect. We can only verify the chain when
47 : we get a confirmation of a block_id.
48 :
49 : Eventually one of two things happen:
50 : 1. We are able to complete the version of the FEC with the merkle root
51 : we have stored. This is the common case, and means we only saw one
52 : version of the merkle root.
53 :
54 : 2. We are not able to complete any version of the FEC.
55 : - Imagine we get shred 0-15 of FEC_A. then get shreds 16-31 of
56 : FEC_B. We would have set the merkle root to the null hash for
57 : that FEC set, but fec_resolver would not be able to complete the
58 : FEC because from a shred index POV, we don't have anything we
59 : need to repair (and we won't be making any new requests for that
60 : FEC set).
61 : It's difficult to differentiate between a slot where we haven't
62 : finished repairing, and a slot we can't repair because the
63 : version we have is a bad version. So merkle chaining
64 : verification can only be performed on slots that have all the
65 : shreds received.
66 :
67 : 3. We receive some shreds for both FEC_A and FEC_B, but get a FEC
68 : completion for FEC_B.
69 : - Could possibly happen during turbine, like we repair some data
70 : shreds from FEC_A, but get a completion for FEC_B through
71 : turbine. At this point we'll take whatever we have completed
72 : first, so overwrite our merkle root entry. It's likely being
73 : overwritten from the null_hash to the FEC_B merkle root.
74 :
75 : So unfortunately...because of case 2, we determine "slot completion"
76 : status when all the shreds in the slot have been received, NOT when
77 : the slot completes with all the FEC completions. We can rely on that
78 : at least some version of all the shreds in the slot will arrive
79 : eventually.
80 :
81 : As soon as we have a confirmed block id, we can verify the slot by
82 : verifying the chain of merkle roots backwards. As the CMRs correctly
83 : chain, the verified status on each FEC set is set. If they don't
84 : chain, we dump & repair that specific FEC set. For example, say the
85 : 2nd & 3rd FEC set is incorrect. In this case, the merkle roots array
86 : and bitset will look like the following after one call of
87 : chain_verify(slot, confirmed_bid):
88 : actual last fec
89 : |
90 : v
91 : merkle_roots [ A, B', C', D, E, F, confirmed_bid] <- confirmed_bid stored for convenience
92 : merkle_verified [ 0, 0, 0, 1, 1, 1, 1 ]
93 :
94 : At this point, C' will be dumped and repaired. Since D is verified,
95 : and the CMR entry contains the correct version of C's merkle root, we
96 : can now verify any shred of FEC set C that arrives and reject if the
97 : merkle root doesn't match the cmr entry in D.
98 :
99 : After C is successfully repaired, the after_fec call in repair_tile
100 : will re-trigger chain_verify on the slot again. After this call of
101 : chain_verify, the merkle roots array and bitset will look like this:
102 :
103 : merkle_roots [ A, B', C, D, E, F, confirmed_bid] <- confirmed_bid stored for convenience
104 : merkle_verified [ 0, 0, 1, 1, 1, 1, 1 ]
105 :
106 : At this point, C is verified, but B' is detected as incorrect. The same
107 : dump and repair process is repeated for B'. Once that after_fec on B
108 : is called, the merkle roots array and bitset will look like this:
109 :
110 : merkle_roots [ A, B, C, D, E, F, confirmed_bid] <- confirmed_bid stored for convenience
111 : merkle_verified [ 1, 1, 1, 1, 1, 1, 1 ]
112 : confirmed = 1
113 :
114 : The chain verify progresses beyond this slot, and the ancestors of
115 : this slots will also be traversed until a confirmed slot is found, or
116 : another incorrect FEC is detected. Note that because earlier
117 : confirmations may have confirmed ancestors, and because there is once
118 : verification "in-progress at all times", confirmation status can look
119 : like:
120 :
121 : slot 1 - slot 2 - slot 3 - slot 4 - slot 5 - slot 6 - slot 7 ....
122 : confirmed: 1 1 0 0 0 1 1
123 :
124 : i.e. there will be up to two contiguous chains of confirmed slots in
125 : the forest, but not more. There can be unconfirmed slots after slot 7.
126 : There may be forks as well, but only one fork can be confirmed.
127 : */
128 :
129 : #include "../../disco/fd_disco_base.h"
130 : #include "../../disco/shred/fd_fec_set.h"
131 :
132 0 : #define FD_FOREST_MAGIC (0xf17eda2ce7b1c0UL) /* firedancer forest version 0 */
133 :
134 : /* Per-block shred idx bitsets are raw ulong words, word_cnt per block,
135 : living in side arrays indexed by pool idx so the per-block shred
136 : bound (shred_max) is a runtime value. idx must be < shred_max. */
137 :
138 : typedef ulong fd_forest_blk_idxs_t;
139 :
140 0 : FD_FN_CONST static inline ulong fd_forest_blk_idxs_word_cnt( ulong shred_max ) { return (shred_max+63UL)>>6; }
141 0 : FD_FN_PURE static inline int fd_forest_blk_idxs_test ( fd_forest_blk_idxs_t const * set, ulong idx ) { return fd_ulong_extract_bit( set[ idx>>6 ], (int)(idx&63UL) ); }
142 0 : static inline void fd_forest_blk_idxs_insert( fd_forest_blk_idxs_t * set, ulong idx ) { set[ idx>>6 ] = fd_ulong_set_bit ( set[ idx>>6 ], (int)(idx&63UL) ); }
143 0 : static inline void fd_forest_blk_idxs_remove( fd_forest_blk_idxs_t * set, ulong idx ) { set[ idx>>6 ] = fd_ulong_clear_bit( set[ idx>>6 ], (int)(idx&63UL) ); }
144 :
145 : FD_FN_PURE static inline ulong
146 0 : fd_forest_blk_idxs_cnt( fd_forest_blk_idxs_t const * set, ulong word_cnt ) {
147 0 : ulong cnt = 0UL;
148 0 : for( ulong i=0UL; i<word_cnt; i++ ) cnt += (ulong)fd_ulong_popcnt( set[ i ] );
149 0 : return cnt;
150 0 : }
151 :
152 : /* fd_forest_blk_idxs_next_unset returns the smallest idx in [lo,hi]
153 : whose bit is clear, or hi+1 if every bit in the range is set. Scans
154 : a word at a time. Assumes lo<=hi and hi<64*word_cnt. */
155 :
156 : FD_FN_PURE static inline ulong
157 0 : fd_forest_blk_idxs_next_unset( fd_forest_blk_idxs_t const * set, ulong lo, ulong hi ) {
158 0 : ulong w = lo>>6;
159 0 : ulong hi_w = hi>>6;
160 0 : ulong bits = ~set[ w ] & (ULONG_MAX<<(lo&63UL));
161 0 : while( !bits && w<hi_w ) bits = ~set[ ++w ];
162 0 : return fd_ulong_min( (w<<6)+(ulong)fd_ulong_find_lsb_w_default( bits, 64 ), hi+1UL );
163 0 : }
164 :
165 : /* Per-FEC merkle roots, shred_max/FD_FEC_SHRED_CNT per block, also in
166 : a side array indexed by pool idx. mr is initialized to null hash,
167 : written to when a shred is received, invalidated to invalid_mr when
168 : multiple versions of the merkle root are detected. */
169 :
170 : struct fd_forest_mr {
171 : fd_hash_t mr;
172 : fd_hash_t cmr;
173 : };
174 : typedef struct fd_forest_mr fd_forest_mr_t;
175 :
176 : /* Per-FEC turbine arrival stamps, shred_max/FD_FEC_SHRED_CNT per block,
177 : also in a side array indexed by pool idx. first is the ms offset
178 : from first_shred_ts at which turbine was first observed reaching the
179 : set. */
180 :
181 : struct fd_forest_recv {
182 : ushort first;
183 : };
184 : typedef struct fd_forest_recv fd_forest_recv_t;
185 :
186 : /* fd_forest_blk_t implements a left-child, right-sibling n-ary
187 : tree. Each ele maintains the `pool` index of its left-most child
188 : (`child_idx`), its immediate-right sibling (`sibling_idx`), and its
189 : parent (`parent_idx`).
190 :
191 : This tree structure is gaddr-safe and supports accesses and
192 : operations from processes with separate local forest joins. */
193 :
194 : struct __attribute__((aligned(128UL))) fd_forest_blk {
195 : ulong slot; /* map key */
196 : ulong parent_slot; /* map key of the parent. invariant: if parent is populated, parent_slot is populated. the converse is not necessarily true. */
197 : ulong next; /* internal use by fd_pool, fd_map_chain */
198 : ulong parent; /* pool idx of the parent in the tree */
199 : ulong child; /* pool idx of the left-child */
200 : ulong sibling; /* pool idx of the right-sibling */
201 :
202 : ulong head; /* reserved by dlist. not all blks will be part of a dlist. */
203 : ulong tail; /* reserved by dlist */
204 :
205 : ulong orphan_seq; /* while an orphan subtree head: liveness token of its one live orphanq entry */
206 :
207 : uint buffered_idx; /* highest contiguous buffered shred idx */
208 : uint complete_idx; /* shred_idx with SLOT_COMPLETE_FLAG ie. last shred idx in the slot */
209 :
210 : /* received data shred idxs, received merkle roots and code shred idxs
211 : and per-FEC turbine arrival stamps are runtime-sized side arrays,
212 : see fd_forest_blk_{idxs,mroots,code,recv} */
213 :
214 : fd_hash_t confirmed_bid; /* confirmed block id - can't be wrapped in the merkle roots struct because we can create sentinel blocks
215 : on confirmation, and don't know the index of the last fec set until we repair the slot.
216 : hash_null if unknown. Otherwise populated by the child slot's CMR on confirmation,
217 : or by a confirmation msg from tower. Has no bearing on if the full slot is correct or not. */
218 : uint lowest_verified_fec; /* lowest fec index that has been verified so far, inclusive. Equivalent to complete_idx / 32UL
219 : if the last merkle root is verified, n if every merkle root after fec set n*32 is verified.
220 : Otherwise, it is UINT_MAX. If non-UINT_MAX, then confirmed_bid must be populated (but not
221 : the vice versa). */
222 :
223 : uchar chain_confirmed; /* 1 if all the FECs the slot have been confirmed via fec_chain_verify, 0 otherwise. Note confirmed_bid
224 : can be populated before this is set to 1. */
225 :
226 : /* Metrics */
227 :
228 : long first_shred_ts; /* tick of first shred rcved in slot != complete_idx */
229 : long last_shred_ts; /* tick at which the slot became fully buffered (buffered_idx==complete_idx) */
230 : long first_req_ts; /* tick of first request sent in slot != complete_idx */
231 : long last_repair_resp_ts;/* tick of the most recent repair response received for this slot */
232 : uint turbine_cnt; /* number of shreds received from turbine */
233 : uint repair_cnt; /* number of data shreds received from repair */
234 : uint recovered_cnt; /* number of shreds recovered from reedsol recovery */
235 :
236 : uint req_window_cnt; /* window (specific-shred) requests sent for this slot */
237 : uint req_highest_cnt; /* highest-window requests sent for this slot */
238 : uint req_orphan_cnt; /* orphan requests sent for this slot */
239 : uint req_retransmit_cnt; /* requests re-sent for this slot after a response timeout */
240 : uint response_cnt; /* repair responses received for this slot */
241 : uchar chain_verify_failed; /* 1 if merkle chain verification flagged this block as the bad one */
242 : };
243 : typedef struct fd_forest_blk fd_forest_blk_t;
244 :
245 : #define POOL_NAME fd_forest_pool
246 0 : #define POOL_T fd_forest_blk_t
247 : #include "../../util/tmpl/fd_pool.c"
248 :
249 : #define MAP_NAME fd_forest_ancestry
250 : #define MAP_ELE_T fd_forest_blk_t
251 0 : #define MAP_KEY slot
252 : #include "../../util/tmpl/fd_map_chain.c"
253 :
254 : #define MAP_NAME fd_forest_frontier
255 : #define MAP_ELE_T fd_forest_blk_t
256 0 : #define MAP_KEY slot
257 : #include "../../util/tmpl/fd_map_chain.c"
258 :
259 : #define MAP_NAME fd_forest_orphaned
260 : #define MAP_ELE_T fd_forest_blk_t
261 0 : #define MAP_KEY slot
262 : #include "../../util/tmpl/fd_map_chain.c"
263 :
264 : #define MAP_NAME fd_forest_subtrees
265 : #define MAP_ELE_T fd_forest_blk_t
266 0 : #define MAP_KEY slot
267 : #include "../../util/tmpl/fd_map_chain.c"
268 :
269 : #define DLIST_NAME fd_forest_subtlist /* thread a dlist through the subtree elements for fast iteration */
270 : #define DLIST_ELE_T fd_forest_blk_t
271 0 : #define DLIST_NEXT head
272 0 : #define DLIST_PREV tail
273 : #include "../../util/tmpl/fd_dlist.c"
274 :
275 : /* Orphan subtree heads scheduled by next orphan-request deadline.
276 : Entries are lazy: a head pushes one entry when it is created and one
277 : each time it is rescheduled; nothing is removed when a head leaves.
278 : Every push tags the entry and the block with the next value of a
279 : monotonic sequence, so an entry is live iff its slot is currently a
280 : subtree head whose orphan_seq matches. At most one entry per head
281 : can be live, hence live entries <= ele_max and a full prq
282 : (2*ele_max) always holds a discardable entry. */
283 :
284 : struct __attribute__((aligned(32UL))) fd_forest_orphan_ent {
285 : long due; /* when the head may next be requested */
286 : ulong slot;
287 : ulong seq; /* liveness token, live iff it matches the head's orphan_seq */
288 : };
289 : typedef struct fd_forest_orphan_ent fd_forest_orphan_ent_t;
290 :
291 : #define PRQ_NAME fd_forest_orphanq
292 0 : #define PRQ_T fd_forest_orphan_ent_t
293 0 : #define PRQ_TIMEOUT due
294 : #include "../../util/tmpl/fd_prq.c"
295 :
296 : /* A reference to a forest element
297 :
298 : The following maps/pools are used to track future requests.
299 :
300 : Requests:
301 : - slots that branch from the main tree (ancestry) that are being
302 : repaired / have yet to be repaired. Maintained in a dlist, where
303 : the head is the current slot being repaired. Any slot in the
304 : requests list must be in ancestry or frontier.
305 :
306 : Orphreqs (orphaned requests):
307 : - slots that branch from the unconnected trees (subtrees/orphans) that are being repaired /
308 : have yet to be repaired. Maintained in a dlist, where the head
309 : is the current orphan request being repaired.
310 :
311 : Note that orphan requests are specifically an optimization from when
312 : we are catching up from very far behind. In the usual case when we
313 : boot and we are catching up from close behind, need orphans is
314 : very fast and has a non-negligible cost on total repair time. But
315 : during special cases where we are catching up from very far behind,
316 : need orphans can take a significant time because orphan requests
317 : cannot be pipelined. In this case, we can use time waiting for
318 : orphan requests to respond to also repair the full slots of these
319 : orphan trees.
320 :
321 : Consumed:
322 : - slots where the entire ancestry up to the root has been completed.
323 : There should be <= num forks elements in the consumed map.
324 : */
325 : struct fd_forest_ref {
326 : ulong idx; /* forest pool idx of the ele this ref refers to */
327 : ulong next; /* reserved by dlist */
328 : ulong prev; /* reserved by dlist */
329 : ulong hash; /* reserved by pool and map_chain */
330 : };
331 : typedef struct fd_forest_ref fd_forest_ref_t;
332 :
333 : #define MAP_NAME fd_forest_requests
334 : #define MAP_ELE_T fd_forest_ref_t
335 0 : #define MAP_KEY idx
336 0 : #define MAP_NEXT hash
337 : #include "../../util/tmpl/fd_map_chain.c"
338 :
339 : #define DLIST_NAME fd_forest_reqslist
340 : #define DLIST_ELE_T fd_forest_ref_t
341 0 : #define DLIST_NEXT next
342 0 : #define DLIST_PREV prev
343 : #include "../../util/tmpl/fd_dlist.c"
344 :
345 : #define POOL_NAME fd_forest_reqspool
346 0 : #define POOL_T fd_forest_ref_t
347 0 : #define POOL_NEXT hash
348 : #include "../../util/tmpl/fd_pool.c"
349 :
350 : /* Below for fast tracking of contiguous completes slots */
351 : #define MAP_NAME fd_forest_consumed
352 : #define MAP_ELE_T fd_forest_ref_t
353 0 : #define MAP_KEY idx
354 0 : #define MAP_NEXT hash
355 : #include "../../util/tmpl/fd_map_chain.c"
356 :
357 : #define DLIST_NAME fd_forest_conslist
358 : #define DLIST_ELE_T fd_forest_ref_t
359 0 : #define DLIST_NEXT next
360 0 : #define DLIST_PREV prev
361 : #include "../../util/tmpl/fd_dlist.c"
362 :
363 : #define POOL_NAME fd_forest_conspool
364 0 : #define POOL_T fd_forest_ref_t
365 0 : #define POOL_NEXT hash
366 : #include "../../util/tmpl/fd_pool.c"
367 :
368 : /* Reuse reqslist for orphan requests list, and share pool */
369 :
370 : /* Internal use only for BFSing */
371 : #define DEQUE_NAME fd_forest_deque
372 0 : #define DEQUE_T ulong
373 : #include "../../util/tmpl/fd_deque_dynamic.c"
374 :
375 :
376 : /* fd_forest_t is the top-level structure that holds the root of
377 : the tree, as well as the memory pools and map structures.
378 :
379 : These structures are bump-allocated and laid out contiguously in
380 : memory from the fd_forest_t * pointer which points to the
381 : beginning of the memory region.
382 :
383 : --------------------- <- fd_forest_t *
384 : | metadata |
385 : |-------------------|
386 : | pool |
387 : |-------------------|
388 : | idxs (per blk) |
389 : |-------------------|
390 : | code (per blk) |
391 : |-------------------|
392 : | mroots (per blk) |
393 : |-------------------|
394 : | recv (per blk) |
395 : |-------------------|
396 : | ancestry |
397 : |-------------------|
398 : | frontier |
399 : |-------------------|
400 : | subtrees |
401 : |-------------------|
402 : | orphaned |
403 : |-------------------|
404 : | requests |
405 : |-------------------|
406 : | reqslist |
407 : |-------------------|
408 : | reqspool |
409 : |-------------------|
410 : | orphreqs |
411 : |-------------------|
412 : | orphlist (reqlist)|
413 : |-------------------|
414 : | consumed |
415 : |-------------------|
416 : | conspool |
417 : |-------------------|
418 : | deque |
419 : ---------------------
420 :
421 : A valid, initialized forest is always non-empty. After
422 : `fd_forest_init` the forest will always have a root ele unless
423 : modified improperly out of forest's API.*/
424 :
425 : struct fd_forest_iter {
426 : ulong ele_idx;
427 : uint shred_idx;
428 : ulong list_gaddr; /* wksp gaddr of the list this iterator corresponds to */
429 : };
430 : typedef struct fd_forest_iter fd_forest_iter_t;
431 : struct __attribute__((aligned(128UL))) fd_forest {
432 : ulong root; /* pool idx of the root */
433 : ulong wksp_gaddr; /* wksp gaddr of fd_forest in the backing wksp, non-zero gaddr */
434 : ulong pool_gaddr; /* wksp gaddr of fd_pool */
435 : ulong shred_max; /* max data shreds per block, bounds shred idxs and fec_set_idxs */
436 : ulong idxs_gaddr; /* wksp gaddr of per-blk data shred idx bitsets, fd_forest_blk_idxs_word_cnt( shred_max ) words each */
437 : ulong code_gaddr; /* wksp gaddr of per-blk code shred idx bitsets */
438 : ulong mroots_gaddr; /* wksp gaddr of per-blk fd_forest_mr_t arrays, shred_max/FD_FEC_SHRED_CNT each */
439 : ulong recv_gaddr; /* wksp gaddr of per-blk fd_forest_recv_t arrays, shred_max/FD_FEC_SHRED_CNT each */
440 : ulong ancestry_gaddr; /* wksp_gaddr of fd_forest_ancestry */
441 : ulong frontier_gaddr; /* leaves that needs repair */
442 : ulong subtrees_gaddr; /* head of orphaned trees */
443 : ulong orphaned_gaddr; /* map of parent_slot to singly-linked list of ele orphaned by that parent slot */
444 :
445 : ulong subtlist_gaddr; /* wksp gaddr of fd_forest_subtlist - linkedlist of subtree elements*/
446 : ulong orphanq_gaddr; /* wksp gaddr of fd_forest_orphanq - orphan heads by request deadline */
447 : ulong orphan_seq_next; /* next orphanq entry liveness token */
448 :
449 : /* Request trackers */
450 :
451 : ulong requests_gaddr; /* map of slot to pool idx of the completed repair frontier */
452 : ulong reqslist_gaddr; /* wksp gaddr of fd_forest_reqslist */
453 : ulong reqspool_gaddr; /* wksp gaddr of fd_forest_reqspool */
454 :
455 : ulong consumed_gaddr; /* wksp gaddr of fd_forest_consumed */
456 : ulong conslist_gaddr; /* wksp gaddr of fd_forest_conslist */
457 : ulong conspool_gaddr; /* wksp gaddr of fd_forest_conspool */
458 :
459 : ulong orphreqs_gaddr; /* wksp gaddr of fd_forest_orphreqs */
460 : ulong orphlist_gaddr; /* wksp gaddr of fd_forest_orphlist */
461 :
462 : fd_forest_iter_t iter; /* requests iterator corresponding to head of requests deque */
463 : fd_forest_iter_t orphiter; /* orphan requests iterator corresponding to head of orphan requests list */
464 :
465 : ulong deque_gaddr; /* wksp gaddr of fd_forest_deque. internal use only for BFSing */
466 : ulong magic; /* ==FD_FOREST_MAGIC */
467 : };
468 : typedef struct fd_forest fd_forest_t;
469 :
470 : FD_PROTOTYPES_BEGIN
471 :
472 : /* Constructors */
473 :
474 : /* fd_forest_{align,footprint} return the required alignment and
475 : footprint of a memory region suitable for use as forest with up to
476 : ele_max eles of up to shred_max data shreds each. */
477 :
478 : FD_FN_CONST static inline ulong
479 0 : fd_forest_align( void ) {
480 0 : return alignof(fd_forest_t);
481 0 : }
482 :
483 : FD_FN_CONST static inline ulong
484 0 : fd_forest_footprint( ulong ele_max, ulong shred_max ) {
485 0 : ulong idxs_sz = ele_max*fd_forest_blk_idxs_word_cnt( shred_max )*sizeof(fd_forest_blk_idxs_t);
486 0 : ulong mroots_sz = ele_max*(shred_max/FD_FEC_SHRED_CNT)*sizeof(fd_forest_mr_t);
487 0 : ulong recv_sz = ele_max*(shred_max/FD_FEC_SHRED_CNT)*sizeof(fd_forest_recv_t);
488 0 : return FD_LAYOUT_FINI(
489 0 : FD_LAYOUT_APPEND(
490 0 : FD_LAYOUT_APPEND(
491 0 : FD_LAYOUT_APPEND(
492 0 : FD_LAYOUT_APPEND(
493 0 : FD_LAYOUT_APPEND(
494 0 : FD_LAYOUT_APPEND(
495 0 : FD_LAYOUT_APPEND(
496 0 : FD_LAYOUT_APPEND(
497 0 : FD_LAYOUT_APPEND(
498 0 : FD_LAYOUT_APPEND(
499 0 : FD_LAYOUT_APPEND(
500 0 : FD_LAYOUT_APPEND(
501 0 : FD_LAYOUT_APPEND(
502 0 : FD_LAYOUT_APPEND(
503 0 : FD_LAYOUT_APPEND(
504 0 : FD_LAYOUT_APPEND(
505 0 : FD_LAYOUT_APPEND(
506 0 : FD_LAYOUT_APPEND(
507 0 : FD_LAYOUT_APPEND(
508 0 : FD_LAYOUT_APPEND(
509 0 : FD_LAYOUT_APPEND(
510 0 : FD_LAYOUT_INIT,
511 0 : alignof(fd_forest_t), sizeof(fd_forest_t) ),
512 0 : fd_forest_pool_align(), fd_forest_pool_footprint ( ele_max ) ),
513 0 : 128UL, idxs_sz ),
514 0 : 128UL, idxs_sz ),
515 0 : 128UL, mroots_sz ),
516 0 : 128UL, recv_sz ),
517 0 : fd_forest_ancestry_align(), fd_forest_ancestry_footprint( ele_max ) ),
518 0 : fd_forest_frontier_align(), fd_forest_frontier_footprint( ele_max ) ),
519 0 : fd_forest_subtrees_align(), fd_forest_subtrees_footprint( ele_max ) ),
520 0 : fd_forest_orphaned_align(), fd_forest_orphaned_footprint( ele_max ) ),
521 0 : fd_forest_subtlist_align(), fd_forest_subtlist_footprint( ) ),
522 0 : fd_forest_orphanq_align(), fd_forest_orphanq_footprint ( 2UL*ele_max ) ),
523 :
524 0 : fd_forest_requests_align(), fd_forest_requests_footprint( ele_max ) ),
525 0 : fd_forest_reqslist_align(), fd_forest_reqslist_footprint( ) ),
526 0 : fd_forest_reqspool_align(), fd_forest_reqspool_footprint( ele_max ) ),
527 0 : fd_forest_consumed_align(), fd_forest_consumed_footprint( ele_max ) ),
528 0 : fd_forest_conslist_align(), fd_forest_conslist_footprint( ) ),
529 0 : fd_forest_conspool_align(), fd_forest_conspool_footprint( ele_max ) ),
530 0 : fd_forest_requests_align(), fd_forest_requests_footprint( ele_max ) ),
531 0 : fd_forest_reqslist_align(), fd_forest_reqslist_footprint( ) ),
532 0 : fd_forest_deque_align(), fd_forest_deque_footprint ( ele_max ) ),
533 0 : fd_forest_align() );
534 0 : }
535 :
536 : /* fd_forest_new formats an unused memory region for use as a
537 : forest. mem is a non-NULL pointer to this region in the local
538 : address space with the required footprint and alignment. ele_max
539 : is a power of 2, shred_max a positive multiple of FD_FEC_SHRED_CNT. */
540 :
541 : void *
542 : fd_forest_new( void * shmem, ulong ele_max, ulong shred_max, ulong seed );
543 :
544 : /* fd_forest_join joins the caller to the forest. forest
545 : points to the first byte of the memory region backing the forest
546 : in the caller's address space. Returns a pointer in the local
547 : address space to forest on success. */
548 :
549 : fd_forest_t *
550 : fd_forest_join( void * forest );
551 :
552 : /* fd_forest_leave leaves a current local join. Returns a pointer
553 : to the underlying shared memory region on success and NULL on failure
554 : (logs details). Reasons for failure include forest is NULL. */
555 :
556 : void *
557 : fd_forest_leave( fd_forest_t const * forest );
558 :
559 : /* fd_forest_delete unformats a memory region used as a
560 : forest. Assumes only the nobody is joined to the region.
561 : Returns a pointer to the underlying shared memory region or NULL if
562 : used obviously in error (e.g. forest is obviously not a
563 : forest ... logs details). The ownership of the memory region is
564 : transferred to the caller. */
565 :
566 : void *
567 : fd_forest_delete( void * forest );
568 :
569 : /* fd_forest_init initializes a forest. Assumes forest
570 : is a valid local join and no one else is joined. root is the initial
571 : root forest will use. This is the snapshot slot if booting from
572 : a snapshot, 0 if the genesis slot.
573 :
574 : In general, this should be called by the same process that formatted
575 : forest's memory, ie. the caller of fd_forest_new. */
576 :
577 : fd_forest_t *
578 : fd_forest_init( fd_forest_t * forest, ulong root );
579 :
580 : /* Accessors */
581 :
582 : /* fd_forest_wksp returns the local join to the wksp backing the
583 : forest. The lifetime of the returned pointer is at least as
584 : long as the lifetime of the local join. Assumes forest is a
585 : current local join. */
586 :
587 : FD_FN_PURE static inline fd_wksp_t *
588 0 : fd_forest_wksp( fd_forest_t const * forest ) {
589 0 : return (fd_wksp_t *)( ( (ulong)forest ) - forest->wksp_gaddr );
590 0 : }
591 :
592 : /* fd_forest_{pool, pool_const} returns a pointer in the caller's address
593 : space to forest's element pool. */
594 :
595 : FD_FN_PURE static inline fd_forest_blk_t *
596 0 : fd_forest_pool( fd_forest_t * forest ) {
597 0 : return fd_wksp_laddr_fast( fd_forest_wksp( forest ), forest->pool_gaddr );
598 0 : }
599 :
600 : FD_FN_PURE static inline fd_forest_blk_t const *
601 0 : fd_forest_pool_const( fd_forest_t const * forest ) {
602 0 : return fd_wksp_laddr_fast( fd_forest_wksp( forest ), forest->pool_gaddr );
603 0 : }
604 :
605 : /* fd_forest_blk_{idxs,code} return blk's data / code shred idx bitset
606 : (fd_forest_blk_idxs_word_cnt( forest->shred_max ) words) and
607 : fd_forest_blk_{mroots,recv} blk's merkle roots / per-FEC turbine
608 : arrival stamps (forest->shred_max / FD_FEC_SHRED_CNT entries each).
609 : blk must be a pool element of forest. */
610 :
611 : FD_FN_PURE static inline fd_forest_blk_idxs_t *
612 0 : fd_forest_blk_idxs( fd_forest_t const * forest, fd_forest_blk_t const * blk ) {
613 0 : fd_forest_blk_idxs_t * idxs = fd_wksp_laddr_fast( fd_forest_wksp( forest ), forest->idxs_gaddr );
614 0 : return idxs + fd_forest_pool_idx( fd_forest_pool_const( forest ), blk )*fd_forest_blk_idxs_word_cnt( forest->shred_max );
615 0 : }
616 :
617 : FD_FN_PURE static inline fd_forest_blk_idxs_t *
618 0 : fd_forest_blk_code( fd_forest_t const * forest, fd_forest_blk_t const * blk ) {
619 0 : fd_forest_blk_idxs_t * code = fd_wksp_laddr_fast( fd_forest_wksp( forest ), forest->code_gaddr );
620 0 : return code + fd_forest_pool_idx( fd_forest_pool_const( forest ), blk )*fd_forest_blk_idxs_word_cnt( forest->shred_max );
621 0 : }
622 :
623 : FD_FN_PURE static inline fd_forest_mr_t *
624 0 : fd_forest_blk_mroots( fd_forest_t const * forest, fd_forest_blk_t const * blk ) {
625 0 : fd_forest_mr_t * mroots = fd_wksp_laddr_fast( fd_forest_wksp( forest ), forest->mroots_gaddr );
626 0 : return mroots + fd_forest_pool_idx( fd_forest_pool_const( forest ), blk )*(forest->shred_max/FD_FEC_SHRED_CNT);
627 0 : }
628 :
629 : FD_FN_PURE static inline fd_forest_recv_t *
630 0 : fd_forest_blk_recv( fd_forest_t const * forest, fd_forest_blk_t const * blk ) {
631 0 : fd_forest_recv_t * recv = fd_wksp_laddr_fast( fd_forest_wksp( forest ), forest->recv_gaddr );
632 0 : return recv + fd_forest_pool_idx( fd_forest_pool_const( forest ), blk )*(forest->shred_max/FD_FEC_SHRED_CNT);
633 0 : }
634 :
635 : /* fd_forest_{ancestry, ancestry_const} returns a pointer in the caller's
636 : address space to forest's ancestry map. */
637 :
638 : FD_FN_PURE static inline fd_forest_ancestry_t *
639 0 : fd_forest_ancestry( fd_forest_t * forest ) {
640 0 : return fd_wksp_laddr_fast( fd_forest_wksp( forest ), forest->ancestry_gaddr );
641 0 : }
642 :
643 : FD_FN_PURE static inline fd_forest_ancestry_t const *
644 0 : fd_forest_ancestry_const( fd_forest_t const * forest ) {
645 0 : return fd_wksp_laddr_fast( fd_forest_wksp( forest ), forest->ancestry_gaddr );
646 0 : }
647 :
648 : /* fd_forest_{frontier, frontier_const} returns a pointer in the caller's
649 : address space to forest's frontier map. */
650 :
651 : FD_FN_PURE static inline fd_forest_frontier_t *
652 0 : fd_forest_frontier( fd_forest_t * forest ) {
653 0 : return fd_wksp_laddr_fast( fd_forest_wksp( forest ), forest->frontier_gaddr );
654 0 : }
655 :
656 : FD_FN_PURE static inline fd_forest_frontier_t const *
657 0 : fd_forest_frontier_const( fd_forest_t const * forest ) {
658 0 : return fd_wksp_laddr_fast( fd_forest_wksp( forest ), forest->frontier_gaddr );
659 0 : }
660 :
661 : /* fd_forest_{subtrees, subtrees_const} returns a pointer in the caller's
662 : address space to forest's subtrees map. */
663 :
664 : FD_FN_PURE static inline fd_forest_subtrees_t *
665 0 : fd_forest_subtrees( fd_forest_t * forest ) {
666 0 : return fd_wksp_laddr_fast( fd_forest_wksp( forest ), forest->subtrees_gaddr );
667 0 : }
668 :
669 : FD_FN_PURE static inline fd_forest_subtrees_t const *
670 0 : fd_forest_subtrees_const( fd_forest_t const * forest ) {
671 0 : return fd_wksp_laddr_fast( fd_forest_wksp( forest ), forest->subtrees_gaddr );
672 0 : }
673 :
674 : /* fd_forest_{subtlist, subtlist_const} returns a pointer in the caller's
675 : address space to forest's subtlist. */
676 :
677 : FD_FN_PURE static inline fd_forest_subtlist_t *
678 0 : fd_forest_subtlist( fd_forest_t * forest ) {
679 0 : return fd_wksp_laddr_fast( fd_forest_wksp( forest ), forest->subtlist_gaddr );
680 0 : }
681 :
682 : FD_FN_PURE static inline fd_forest_subtlist_t const *
683 0 : fd_forest_subtlist_const( fd_forest_t const * forest ) {
684 0 : return fd_wksp_laddr_fast( fd_forest_wksp( forest ), forest->subtlist_gaddr );
685 0 : }
686 :
687 : FD_FN_PURE static inline fd_forest_orphan_ent_t *
688 0 : fd_forest_orphanq( fd_forest_t * forest ) {
689 0 : return fd_wksp_laddr_fast( fd_forest_wksp( forest ), forest->orphanq_gaddr );
690 0 : }
691 :
692 : FD_FN_PURE static inline fd_forest_orphan_ent_t const *
693 0 : fd_forest_orphanq_const( fd_forest_t const * forest ) {
694 0 : return fd_wksp_laddr_fast( fd_forest_wksp( forest ), forest->orphanq_gaddr );
695 0 : }
696 :
697 : /* fd_forest_{orphaned, orphaned_const} returns a pointer in the caller's
698 : address space to forest's orphaned map. */
699 :
700 : FD_FN_PURE static inline fd_forest_orphaned_t *
701 0 : fd_forest_orphaned( fd_forest_t * forest ) {
702 0 : return fd_wksp_laddr_fast( fd_forest_wksp( forest ), forest->orphaned_gaddr );
703 0 : }
704 :
705 : FD_FN_PURE static inline fd_forest_orphaned_t const *
706 0 : fd_forest_orphaned_const( fd_forest_t const * forest ) {
707 0 : return fd_wksp_laddr_fast( fd_forest_wksp( forest ), forest->orphaned_gaddr );
708 0 : }
709 :
710 : /* fd_forest_{consumed, consumed_const} returns a pointer in the caller's
711 : address space to forest's consumed map. */
712 :
713 : FD_FN_PURE static inline fd_forest_consumed_t *
714 0 : fd_forest_consumed( fd_forest_t * forest ) {
715 0 : return fd_wksp_laddr_fast( fd_forest_wksp( forest ), forest->consumed_gaddr );
716 0 : }
717 :
718 : FD_FN_PURE static inline fd_forest_consumed_t const *
719 0 : fd_forest_consumed_const( fd_forest_t const * forest ) {
720 0 : return fd_wksp_laddr_fast( fd_forest_wksp( forest ), forest->consumed_gaddr );
721 0 : }
722 :
723 : /* fd_forest_{conslist, conslist_const} returns a pointer in the caller's
724 : address space to forest's consumed list. */
725 :
726 : FD_FN_PURE static inline fd_forest_conslist_t *
727 0 : fd_forest_conslist( fd_forest_t * forest ) {
728 0 : return fd_wksp_laddr_fast( fd_forest_wksp( forest ), forest->conslist_gaddr );
729 0 : }
730 :
731 : FD_FN_PURE static inline fd_forest_conslist_t const *
732 0 : fd_forest_conslist_const( fd_forest_t const * forest ) {
733 0 : return fd_wksp_laddr_fast( fd_forest_wksp( forest ), forest->conslist_gaddr );
734 0 : }
735 :
736 : /* fd_forest_{conspool, conspool_const} returns a pointer in the caller's
737 : address space to forest's consumed pool. */
738 :
739 : FD_FN_PURE static inline fd_forest_ref_t *
740 0 : fd_forest_conspool( fd_forest_t * forest ) {
741 0 : return fd_wksp_laddr_fast( fd_forest_wksp( forest ), forest->conspool_gaddr );
742 0 : }
743 :
744 : FD_FN_PURE static inline fd_forest_ref_t const *
745 0 : fd_forest_conspool_const( fd_forest_t const * forest ) {
746 0 : return fd_wksp_laddr_fast( fd_forest_wksp( forest ), forest->conspool_gaddr );
747 0 : }
748 :
749 : /* fd_forest_{requests, requests_const} returns a pointer in the caller's
750 : address space to forest's requests map. */
751 :
752 : FD_FN_PURE static inline fd_forest_requests_t *
753 0 : fd_forest_requests( fd_forest_t * forest ) {
754 0 : return fd_wksp_laddr_fast( fd_forest_wksp( forest ), forest->requests_gaddr );
755 0 : }
756 :
757 : FD_FN_PURE static inline fd_forest_requests_t const *
758 0 : fd_forest_requests_const( fd_forest_t const * forest ) {
759 0 : return fd_wksp_laddr_fast( fd_forest_wksp( forest ), forest->requests_gaddr );
760 0 : }
761 :
762 : /* fd_forest_{reqslist, reqslist_const} returns a pointer in the caller's
763 : address space to forest's reqslist. */
764 :
765 : FD_FN_PURE static inline fd_forest_reqslist_t *
766 0 : fd_forest_reqslist( fd_forest_t * forest ) {
767 0 : return fd_wksp_laddr_fast( fd_forest_wksp( forest ), forest->reqslist_gaddr );
768 0 : }
769 :
770 : FD_FN_PURE static inline fd_forest_reqslist_t const *
771 0 : fd_forest_reqslist_const( fd_forest_t const * forest ) {
772 0 : return fd_wksp_laddr_fast( fd_forest_wksp( forest ), forest->reqslist_gaddr );
773 0 : }
774 :
775 : /* fd_forest_{orphreqs, orphanreqs_const} returns a pointer in the caller's
776 : address space to forest's orphanreqs. */
777 :
778 : FD_FN_PURE static inline fd_forest_requests_t *
779 0 : fd_forest_orphreqs( fd_forest_t * forest ) {
780 0 : return fd_wksp_laddr_fast( fd_forest_wksp( forest ), forest->orphreqs_gaddr );
781 0 : }
782 :
783 : FD_FN_PURE static inline fd_forest_requests_t const *
784 0 : fd_forest_orphreqs_const( fd_forest_t const * forest ) {
785 0 : return fd_wksp_laddr_fast( fd_forest_wksp( forest ), forest->orphreqs_gaddr );
786 0 : }
787 :
788 : /* fd_forest_{orphlist, orphanlist_const} returns a pointer in the caller's
789 : address space to forest's orphanlist. */
790 :
791 : FD_FN_PURE static inline fd_forest_reqslist_t *
792 0 : fd_forest_orphlist( fd_forest_t * forest ) {
793 0 : return fd_wksp_laddr_fast( fd_forest_wksp( forest ), forest->orphlist_gaddr );
794 0 : }
795 :
796 : FD_FN_PURE static inline fd_forest_reqslist_t const *
797 0 : fd_forest_orphlist_const( fd_forest_t const * forest ) {
798 0 : return fd_wksp_laddr_fast( fd_forest_wksp( forest ), forest->orphlist_gaddr );
799 0 : }
800 :
801 : /* fd_forest_{reqspool, reqspool_const} returns a pointer in the caller's
802 : address space to forest's reqspool pool. */
803 :
804 : FD_FN_PURE static inline fd_forest_ref_t *
805 0 : fd_forest_reqspool( fd_forest_t * forest ) {
806 0 : return fd_wksp_laddr_fast( fd_forest_wksp( forest ), forest->reqspool_gaddr );
807 0 : }
808 :
809 : FD_FN_PURE static inline fd_forest_ref_t const *
810 0 : fd_forest_reqspool_const( fd_forest_t const * forest ) {
811 0 : return fd_wksp_laddr_fast( fd_forest_wksp( forest ), forest->reqspool_gaddr );
812 0 : }
813 :
814 : /* fd_forest_root_slot returns forest's root slot. Assumes
815 : forest is a current local join. */
816 :
817 : FD_FN_PURE static inline ulong
818 0 : fd_forest_root_slot( fd_forest_t const * forest ) {
819 0 : if( FD_UNLIKELY( forest->root == fd_forest_pool_idx_null( fd_forest_pool_const( forest ) ) )) return ULONG_MAX; /* uninitialized */
820 0 : return fd_forest_pool_ele_const( fd_forest_pool_const( forest ), forest->root )->slot;
821 0 : }
822 :
823 : fd_forest_blk_t *
824 : fd_forest_query( fd_forest_t * forest, ulong slot );
825 :
826 : /* Operations */
827 :
828 : /* fd_forest_blk_insert inserts a new block into the forest. Assumes
829 : slot >= forest->root. blk_insert can also be called to create a
830 : sentinel block, i.e. a placeholder block that we know exists but
831 : don't know the parent slot of. The caller should pass in parent_slot
832 : == ULONG_MAX. In this case, the block inserted will remain an
833 : orphan/subtree at least until the next blk_insert is called with a
834 : different parent_slot, after which point blk_insert will not update
835 : the parent_slot again (shred inserts may still update it, see
836 : fd_forest_data_shred_insert). For non-sentinel blocks, blk insert is
837 : idempotent, and can be called multiple times with the same slot.
838 :
839 : If the forest pool is full at the time of insertion, a block will be
840 : chosen for eviction (see fd_forest.c:evict for more details). If the
841 : caller passes in a non-NULL evicted pointer, the evicted slot will be
842 : stored to the pointer.
843 :
844 : Returns the inserted (or existing) forest ele. NULL if the forest
845 : pool is full and no block could be evicted. */
846 :
847 : fd_forest_blk_t *
848 : fd_forest_blk_insert( fd_forest_t * forest, ulong slot, ulong parent_slot, ulong * evicted );
849 :
850 0 : #define SHRED_SRC_TURBINE 0
851 0 : #define SHRED_SRC_REPAIR 1
852 0 : #define SHRED_SRC_RECOVERED 2
853 : #define SHRED_SRC_LEADER 3
854 :
855 : /* fd_forest_shred_insert inserts a new shred into the forest. Assumes
856 : slot is already in forest, and should typically be preceded by a
857 : fd_forest_blk_insert. Returns the forest ele corresponding to the
858 : shred slot if the shred is accepted, and NULL if the shred is
859 : rejected. A shred can only be rejected if slot is able to verify
860 : that this shred does not belong to the canonical FEC set.
861 :
862 : A possible side effect of data_shred_insert is that it may update the
863 : parent slot of the block IF 1) the inserted shred has a verifiably
864 : correct merkle root, or 2) the shred belongs in fec set 0, and no
865 : other merkle roots has arrived for fec set 0.
866 :
867 : Note this is different from a sentinel block parent update. A
868 : sentinel block will update its parent with the first parent slot it
869 : receives, but it can be later updated with a data_shred_insert. */
870 :
871 : fd_forest_blk_t *
872 : fd_forest_data_shred_insert( fd_forest_t * forest,
873 : ulong slot,
874 : ulong parent_slot,
875 : uint shred_idx,
876 : uint fec_set_idx,
877 : int slot_complete,
878 : int ref_tick,
879 : int src,
880 : fd_hash_t * mr,
881 : fd_hash_t * cmr,
882 : long rx_tick );
883 :
884 : fd_forest_blk_t *
885 : fd_forest_code_shred_insert( fd_forest_t * forest, ulong slot, uint shred_idx, long rx_tick );
886 :
887 : /* fd_forest_fec_insert inserts a new fully completed FEC set into the
888 : forest. Assumes slot is already in forest, and should typically be
889 : called directly after fd_forest_block_insert. Returns the forest ele
890 : corresponding to the shred slot if the FEC was accepted, NULL
891 : otherwise. Like data_shred_insert, this may update the block's
892 : parent slot: a completed FEC set 0 whose merkle root overwrites a
893 : conflicting recorded version re-links the block to the parent named
894 : by the completing shred. */
895 :
896 : fd_forest_blk_t *
897 : fd_forest_fec_insert( fd_forest_t * forest,
898 : ulong slot,
899 : ulong parent_slot,
900 : uint last_shred_idx,
901 : uint fec_set_idx,
902 : int slot_complete,
903 : int ref_tick,
904 : fd_hash_t * mr,
905 : fd_hash_t * cmr,
906 : long rx_tick );
907 :
908 : /* fd_forest_fec_clear clears the FEC set at the given slot and
909 : fec_set_idx.
910 : Can fec_clear break requests frontier invariants? No.
911 :
912 : 2) If slot n is in scope of the forest root, then the shred
913 : delivered to repair will trigger a data_shred_insert call
914 : that does nothing, as repair already has record of that
915 : shred. Eventually the fec_completes or fec_clear msg will be
916 : delivered to repair. fec_insert will do nothing. fec_clear
917 : will remove the idxs for the shreds from the bitset, and
918 : update the buffered_idx. This doesn't matter though! because
919 : we already have moved past slot n on the requests frontier.
920 : No need to request those shreds again.
921 :
922 : Except 2) breaks a bit with in specific leader slot cases. See
923 : fd_forest_fec_clear for more details. */
924 : void
925 : fd_forest_fec_clear( fd_forest_t * forest, ulong slot, uint fec_set_idx, uint max_shred_idx );
926 :
927 : /* fd_forest_fec_chain_verify verifies the chain of merkle roots for a
928 : given block. Should only be called on a block that has all the shreds
929 : received. Returns a pointer to the first slot that does not confirm,
930 : or NULL if the chain is valid. */
931 : fd_forest_blk_t *
932 : fd_forest_fec_chain_verify( fd_forest_t * forest, fd_forest_blk_t * ele, fd_hash_t const * mr );
933 :
934 : void
935 : fd_forest_confirm( fd_forest_t * forest, fd_forest_blk_t * ele, fd_hash_t const * bid );
936 :
937 : /* fd_forest_merkle_last_incorrect_idx returns the highest incorrect FEC
938 : index for a given block. */
939 : static inline uint
940 0 : fd_forest_merkle_last_incorrect_idx( fd_forest_blk_t * ele ) {
941 0 : ulong first_verified_fec = ele->lowest_verified_fec;
942 : /* UNLIKELY because this is being called because we've detected an incorrect FEC */
943 0 : if( FD_UNLIKELY( first_verified_fec == 0 ) ) return UINT_MAX;
944 :
945 0 : uint bad_fec_idx = first_verified_fec == UINT_MAX ? ele->complete_idx / 32UL /* last FEC is wrong */
946 0 : : (uint)first_verified_fec - 1;
947 0 : return bad_fec_idx * 32UL;
948 0 : }
949 :
950 : /* fd_forest_publish publishes slot as the new forest root, setting
951 : the subtree beginning from slot as the new forest tree (ie. slot
952 : and all its descendants). Prunes all eles not in slot's forest.
953 : Assumes slot is present in forest. Returns the new root. */
954 :
955 : fd_forest_blk_t const *
956 : fd_forest_publish( fd_forest_t * forest, ulong slot );
957 :
958 : /* fd_forest_highest_repaired_slot returns the highest child of a fully,
959 : contiguously repaired slot. */
960 : ulong
961 : fd_forest_highest_repaired_slot( fd_forest_t const * forest );
962 :
963 : /* fd_forest_iter_* takes either the standard iterator or the orphan
964 : iterator and returns the next shred to request. The iterator must
965 : one of the two iterators that is owned by the forest.
966 :
967 : The iterator will be in an iter_done state if there are no current
968 : shreds to request.
969 :
970 : The forward forest iterator will visit each shred at most once over
971 : the lifetime of the forest, without revisiting past shreds, so it is
972 : up to the caller to track which shreds will need re-requesting. The
973 : exception to the rule is slots where the slot_complete shred is still
974 : not known - the highest window idx will be requested for that slot,
975 : and the slot will be added to the tail of the requests deque so that
976 : later we may revisit it. As a result, the children of that slot may
977 : also be revisited multiple times.
978 :
979 : Note this case is pretty rare.
980 :
981 : An iterator signifies to the repair tile to request the
982 : highest_window_index when the ele_idx is not null and shred_idx is
983 : UINT_MAX.
984 :
985 : Otherwise, the iterator signifies to the repair tile to request a
986 : regular shred window_idx.
987 :
988 : Invariants for requests map and requests deque:
989 :
990 : There can only be one occurrence of the slot in the requests deque at
991 : any time. Any slot in the requests deque must exist in the requests
992 : map, and vice versa. Any slot in the requests map must also exist in
993 : the forest. During publish the requests map must also be pruned.
994 :
995 : If we are mid-request of a slot that gets pruned, forest will take
996 : responsibility to update the iterator to a valid slot.
997 :
998 : TODO: should this really be an iterator?? or just a _next function? */
999 :
1000 : fd_forest_iter_t *
1001 : fd_forest_iter_next( fd_forest_iter_t * iter, fd_forest_t * forest );
1002 :
1003 : int
1004 : fd_forest_iter_done( fd_forest_iter_t * iter, fd_forest_t * forest );
1005 :
1006 : /* Misc */
1007 :
1008 : /* fd_forest_verify checks the forest is not obviously corrupt.
1009 : Returns 0 if verify succeeds, -1 otherwise. */
1010 :
1011 : int
1012 : fd_forest_verify( fd_forest_t const * forest );
1013 :
1014 : /* fd_forest_print pretty-prints a formatted forest tree. Printing begins
1015 : from `ele` (it will appear as the root in the print output).
1016 :
1017 : The most straightforward and commonly used printing pattern is:
1018 : `fd_forest_print( forest, fd_forest_root( forest ) )`
1019 :
1020 : This would print forest beginning from the root.
1021 :
1022 : Alternatively, caller can print a more localized view, for example
1023 : starting from the grandparent of the most recently executed slot:
1024 :
1025 : ```
1026 : fd_forest_blk_t const * ele = fd_forest_query( slot );
1027 : fd_forest_print( forest, fd_forest_parent( fd_forest_parent( ele ) ) )
1028 : ```
1029 :
1030 : Callers should add null-checks as appropriate in actual usage. */
1031 :
1032 : void
1033 : fd_forest_print( fd_forest_t const * forest );
1034 :
1035 : FD_PROTOTYPES_END
1036 :
1037 : #endif /* HEADER_fd_src_discof_forest_fd_forest_h */
|
