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