Line data Source code
1 : #ifndef HEADER_fd_src_discof_chainer_fd_chainer_h
2 : #define HEADER_fd_src_discof_chainer_fd_chainer_h
3 :
4 : /* Fec chainer is an API for reassembling shreds and FECs into slots.
5 : It maintains 2 levels of granularity:
6 :
7 : FECs, and SLOTVs (short for "slot versions"). SLOTVs are keyed by
8 : slot in a MAP_MULTI: the several versions of a slot chain off the
9 : same slot key and are distinguished by their block_id. FECs are
10 : keyed by their unique merkle root, and can be shared by multiple
11 : slotvs.
12 :
13 : The block_id for the turbine version is all-zero until finalization,
14 : after which point it will be impossible to distinguish from other
15 : versions. Thus, it is marked with a `turbine` flag (prevents extra
16 : trailing turbine shreds from creating unbounded slotv contexts).
17 : notar-fallback / SafeToNotar versions carry a real block_id from
18 : their cert.
19 :
20 : Under alpenglow, we can simplify equivocation handling. As turbine
21 : shreds arrive, each (slot, fec_set_idx) only accepts shreds of the
22 : first-seen root. Any shred with a different root is dropped.
23 :
24 : When a notar-fallback cert or a SafeToNotar is received for a
25 : block_id of a slot we don't have yet, we can add additional versions.
26 : No correct node ever stores more than 7 distinct blocks per slot
27 : (Corollary 50).
28 :
29 : A cert or SafeToNotar should trigger getParentandFecCount requests.
30 : The response should trigger getSliceHash (2.8, Definition 19)
31 : requests. Extra versions of a FEC set only exists once a getFecRoot
32 : response creates the sentinel with that root. Equivocating FEC shreds
33 : are accepted iff the sentinel already exists. If the sentinel does
34 : not exist, the FEC shreds are dropped. This way -- turbine shreds are
35 : accepted without concern for whether the FEC sets belong to the "same
36 : slot", but votor-driven events guarantee repair of shreds that
37 : verifiably belong to the same slot.
38 :
39 : Note that in the uncommon but not impossible case where we may be
40 : taking a long to complete a block, we may receive a votor event for
41 : an honest slot that we are still in the process of receiving from
42 : turbine. Since we can't compute the block_id for a slot still
43 : incomplete from turbine, we would create a redundant SLOTV entry for,
44 : logically, the same slot. In effect, this would generate an extra
45 : getParentAndFecCount request and getFecRoot requests, but since we
46 : already have most of the data for the slot, we can avoid
47 : re-requesting the shreds. This case should be rare enough that the
48 : redundancy is worth the simplicity.
49 :
50 : When that happens the turbine version is ABANDONED: arriving shreds
51 : are still accepted and fill the FECs, but it never delivers to
52 : replay, never finalizes a block_id, and is dropped from the repair
53 : worklists. Were it to keep delivering, and its block_id to finalize
54 : to the same block a votor version is repairing, replay would
55 : materialize two banks for the same {slot, block_id} (see
56 : fd_rotor_tile.h). An abandoned slotv is pruned with its slot at
57 : publish. Note that replay can handle two fully-delivered slots, so
58 : whether we should maintain this abandon state is debatable. But
59 : logically we want to only deliver verified blocks to replay if
60 : we have something verifiable available.
61 :
62 : *Parent Discovery*
63 :
64 : The trickiness with chaining is that there's 3 different sources of
65 : parent information. Shreds contain parent_off field, which may or may
66 : not be removed in the future. The block header contains the initial
67 : replay parent_slot, and there can be an updateParent marker anywhere
68 : in the middle of the block.
69 :
70 : In the case where we are disconnected momentarily, or we are catching
71 : up, we won't ever receive shreds for the original parent slot, only
72 : for the updated parent slot. We currently assume parent_off will
73 : update with the parentUpdate marker.
74 : */
75 :
76 : #include "../../disco/fd_disco_base.h"
77 : #include "../../disco/shred/fd_fec_set.h"
78 : #include "../../disco/store/fd_store.h"
79 :
80 96 : #define FD_CHAINER_MAGIC (0xf17eda2ce7c4a112UL) /* firedancer chainer v1 */
81 :
82 417 : #define FD_CHAINER_SLOT_VER_MAX 7 /* see Corollary 50 */
83 :
84 : FD_STATIC_ASSERT( FD_FEC_SHRED_CNT==32UL, fd_chainer_fec_bitmap );
85 :
86 : struct fd_chainer_fec {
87 : fd_hash_t merkle_root; /* key */
88 : uint slot; /* slot this FEC belongs to */
89 : uint data_idxs; /* received data shreds in this FEC */
90 : uint next; /* reserved by pool and map_chain */
91 : uint prev; /* reserved by map_chain (doubly-linked chains) */
92 : uint fec_set_idx : 28; /* position within the slot (multiple of FD_FEC_SHRED_CNT) */
93 : uint complete : 1; /* set is reconstructable and may be delivered */
94 : uint slot_complete: 1;
95 : uint data_complete: 1;
96 : uint is_leader : 1;
97 : };
98 : typedef struct fd_chainer_fec fd_chainer_fec_t;
99 : FD_STATIC_ASSERT( sizeof(fd_chainer_fec_t)==52UL, fd_chainer_fec );
100 :
101 : #define POOL_NAME fd_fec_pool
102 192 : #define POOL_T fd_chainer_fec_t
103 : #define POOL_IDX_T uint
104 : #include "../../util/tmpl/fd_pool.c"
105 :
106 : #define MAP_NAME fd_fec_map
107 309 : #define MAP_ELE_T fd_chainer_fec_t
108 543696 : #define MAP_IDX_T uint
109 816 : #define MAP_KEY merkle_root
110 : #define MAP_KEY_T fd_hash_t
111 259152 : #define MAP_KEY_EQ(k0,k1) (!memcmp( (k0)->uc, (k1)->uc, sizeof(fd_hash_t) ))
112 485841 : #define MAP_KEY_HASH(key,seed) ( (seed) ^ fd_ulong_load_8( (key)->uc ) )
113 : #define MAP_OPTIMIZE_RANDOM_ACCESS_REMOVAL 1
114 : #include "../../util/tmpl/fd_map_chain.c"
115 :
116 34482 : #define AG_UNKNOWN_SLOT ULONG_MAX
117 : struct fd_chainer_slotv {
118 : ulong slot; /* MAP_MULTI key */
119 : ulong next; /* reserved by pool and map_chain */
120 : ulong prev; /* reserved by map_chain */
121 :
122 : uchar turbine; /* 1 for the slotv created through turbine */
123 : uchar abandoned; /* 1 once a votor-driven version of the slot was
124 : created while this (turbine) version's block_id
125 : was still unknown: keeps accepting shred/FEC
126 : bookkeeping but never delivers, never finalizes
127 : a block_id, and stays off the repair worklists.
128 : See the header comment above. */
129 : fd_hash_t block_id;
130 : uint complete_idx;
131 : uint buffered_idx; /* idx of highest buffered shred */
132 : uint buffered_fec_idx; /* last shred idx of highest buffered FEC set we have received completion for */
133 :
134 : ulong parent_slot; /* AG_UNKNOWN_SLOT if unknown */
135 : fd_hash_t parent_block_id; /* block_id of the parent slot */
136 : uint parent_slot_batch; /* fec_idx of the last known parent_slot information.
137 : before FLH is activated, can only be 0 or UINT_MAX. After FLH
138 : is activated, can be 0 or UINT_MAX or a multiple of FD_FEC_SHRED_CNT,
139 : and can only update to a non-zero fec_idx value once. */
140 :
141 : /* delivery to replay */
142 : uchar connected; /* ancestor chain reaches the root */
143 : uint delivered_idx; /* last shred idx of highest fec_set_idx contiguously delivered to replay, UINT_MAX = none */
144 :
145 : /* repair worklist. While an slotv has un-requested work it is
146 : tracked by a worklist element (fd_chainer_work) in the repair and/or
147 : orphan treap. highest_requested stays on the slotv: the work ele
148 : is freed whenever the slotv leaves both treaps and recreated on
149 : re-add, so keeping the high-water mark here preserves it across
150 : those cycles. */
151 : uint highest_requested; /* highest idx we've issued a repair request for, UINT_MAX = none */
152 : };
153 : typedef struct fd_chainer_slotv fd_chainer_slotv_t;
154 :
155 : #define POOL_NAME fd_slotv_pool
156 192 : #define POOL_T fd_chainer_slotv_t
157 : #include "../../util/tmpl/fd_pool.c"
158 :
159 : #define MAP_NAME fd_slotv_map
160 345651 : #define MAP_ELE_T fd_chainer_slotv_t
161 24702 : #define MAP_KEY slot
162 : #define MAP_MULTI 1 /* several versions of a slot share the slot key */
163 : #define MAP_OPTIMIZE_RANDOM_ACCESS_REMOVAL 1 /* remove a specific version, not an arbitrary slot match */
164 : #include "../../util/tmpl/fd_map_chain.c"
165 :
166 : /* fd_chainer_work is a worklist element: the repair (shred-fill) and
167 : orphan (ancestry) treaps are built from these. An ele exists only
168 : while its slotv is in at least one treap; it is created on the first
169 : add and freed once removed from both. */
170 :
171 : struct fd_chainer_work {
172 : ulong slotv_idx; /* fd_slotv_pool idx */
173 : ulong slot;
174 : ulong next; /* reserved by pool and map_chain */
175 : ulong prev; /* reserved by map_chain */
176 : uchar in_repair; /* 1 if currently in the repair (shred-fill) treap */
177 : uchar in_orphan; /* 1 if currently in the orphan (ancestry) treap */
178 : struct { ulong parent, left, right, next, prev, prio; } repair;
179 : struct { ulong parent, left, right, next, prev, prio; } orphan;
180 : };
181 : typedef struct fd_chainer_work fd_chainer_work_t;
182 :
183 : #define POOL_NAME fd_work_pool
184 192 : #define POOL_T fd_chainer_work_t
185 : #include "../../util/tmpl/fd_pool.c"
186 :
187 : /* keyed by slotv_idx (unique per shadowed slotv) */
188 : #define MAP_NAME fd_work_map
189 285 : #define MAP_ELE_T fd_chainer_work_t
190 624 : #define MAP_KEY slotv_idx
191 : #define MAP_OPTIMIZE_RANDOM_ACCESS_REMOVAL 1
192 : #include "../../util/tmpl/fd_map_chain.c"
193 :
194 : /* Repair worklist: eles ordered by slot, iterated min-first so repair
195 : proceeds from the root forward. */
196 : #define TREAP_NAME fd_work_repair
197 : #define TREAP_T fd_chainer_work_t
198 : #define TREAP_QUERY_T ulong
199 : #define TREAP_CMP(q,e) ( ((q)>(e)->slot) - ((q)<(e)->slot) )
200 288 : #define TREAP_LT(e0,e1) ( (e0)->slot < (e1)->slot )
201 3105 : #define TREAP_IDX_T ulong
202 : #define TREAP_OPTIMIZE_ITERATION 1
203 12058 : #define TREAP_PARENT repair.parent
204 12139 : #define TREAP_LEFT repair.left
205 11916 : #define TREAP_RIGHT repair.right
206 2718 : #define TREAP_NEXT repair.next
207 624 : #define TREAP_PREV repair.prev
208 32179 : #define TREAP_PRIO repair.prio
209 : #include "../../util/tmpl/fd_treap.c"
210 :
211 : /* Orphan worklist: eles whose slotv's immediate parent is not yet
212 : present, or parent_slot is not known. An ele leaves this treap once
213 : its parent slotv exists. */
214 : #define TREAP_NAME fd_work_orphan
215 : #define TREAP_T fd_chainer_work_t
216 : #define TREAP_QUERY_T ulong
217 : #define TREAP_CMP(q,e) ( ((q)>(e)->slot) - ((q)<(e)->slot) )
218 160 : #define TREAP_LT(e0,e1) ( (e0)->slot < (e1)->slot )
219 3189 : #define TREAP_IDX_T ulong
220 : #define TREAP_OPTIMIZE_ITERATION 1
221 1034 : #define TREAP_PARENT orphan.parent
222 998 : #define TREAP_LEFT orphan.left
223 881 : #define TREAP_RIGHT orphan.right
224 900 : #define TREAP_NEXT orphan.next
225 630 : #define TREAP_PREV orphan.prev
226 32153 : #define TREAP_PRIO orphan.prio
227 : #include "../../util/tmpl/fd_treap.c"
228 :
229 : #define DEQUE_NAME bfs
230 786 : #define DEQUE_T ulong
231 : #include "../../util/tmpl/fd_deque_dynamic.c"
232 :
233 : struct out_ele {
234 : uint slotv_idx; /* slotv pool idx */
235 : uint fec_idx; /* fd_fec_pool idx */
236 : };
237 : typedef struct out_ele out_ele_t;
238 :
239 : /* out_queue holds pool indices of FECs that have been delivered
240 : (contiguous from root and connected) and are awaiting publish to
241 : replay by the repair tile. Sized to the max number of FECs. Since
242 : out_ele maintains pool indices, the out_queue must be drained between
243 : any chainer call that can modify the pool. */
244 :
245 : #define DEQUE_NAME out_queue
246 540 : #define DEQUE_T out_ele_t
247 : #include "../../util/tmpl/fd_deque_dynamic.c"
248 :
249 : struct fd_chainer {
250 : ulong root; /* root slot, ULONG_MAX if unset */
251 : ulong highest_repaired; /* max slot ever marked fully_delivered (contiguous-from-root repaired tip) */
252 : ulong wksp_gaddr; /* wksp gaddr of fd_chainer in the backing wksp, non-zero gaddr */
253 :
254 : fd_chainer_fec_t * fec_pool;
255 : fd_fec_map_t * fec_map;
256 :
257 : fd_chainer_slotv_t * slotv_pool;
258 : fd_slotv_map_t * slotv_map;
259 : uint * fec_tbl; /* fec_tbl[ slotv_idx*fec_blk_max + k ] = fd_fec_pool idx of the FEC
260 : that slotv owns at FEC set k, UINT_MAX if none */
261 : ulong fec_blk_max; /* max FEC sets per block (max_shreds_per_block/FD_FEC_SHRED_CNT) */
262 :
263 : /* Repair worklists */
264 : fd_chainer_work_t * work_pool;
265 : fd_work_map_t * work_map;
266 : fd_work_repair_t * repair_treap;
267 : fd_work_orphan_t * orphan_treap;
268 :
269 : ulong * bfs; /* bfs queue */
270 : out_ele_t * out_queue; /* delivered FEC pool idxs awaiting publish to replay */
271 :
272 : ulong magic; /* ==FD_CHAINER_MAGIC */
273 : };
274 : typedef struct fd_chainer fd_chainer_t;
275 :
276 : FD_PROTOTYPES_BEGIN
277 :
278 : FD_FN_CONST static inline ulong
279 12144 : fd_chainer_align( void ) {
280 12144 : return fd_ulong_max( alignof(fd_chainer_t), 128UL );
281 12144 : }
282 :
283 : /* fd_chainer_footprint returns the footprint for ele_max slots, each
284 : with up to FD_CHAINER_SLOT_VER_MAX versions of up to
285 : max_shreds_per_block data shreds (FD_SHRED_BLK_MAX in production,
286 : larger under bench limits). Returns 0 if max_shreds_per_block is not
287 : a positive multiple of FD_FEC_SHRED_CNT, exceeds the 28-bit
288 : fec_set_idx, or asks for more FEC elements than the uint pool and map
289 : indices can address. */
290 :
291 : FD_FN_CONST static inline ulong
292 : fd_chainer_footprint( ulong ele_max,
293 213 : ulong max_shreds_per_block ) {
294 213 : if( FD_UNLIKELY( !max_shreds_per_block || max_shreds_per_block%FD_FEC_SHRED_CNT || max_shreds_per_block>FD_SHRED_BLK_MAX_RAISED ) ) return 0UL;
295 204 : ulong blk_max = ele_max * FD_CHAINER_SLOT_VER_MAX;
296 204 : ulong fec_blk_max = max_shreds_per_block / FD_FEC_SHRED_CNT;
297 204 : ulong fec_max = blk_max * fec_blk_max;
298 204 : if( FD_UNLIKELY( !fd_fec_pool_footprint( fec_max ) ) ) return 0UL;
299 201 : ulong fec_chain_cnt = fd_fec_map_chain_cnt_est( fec_max );
300 201 : ulong blk_chain_cnt = fd_slotv_map_chain_cnt_est( blk_max );
301 201 : return FD_LAYOUT_FINI(
302 204 : FD_LAYOUT_APPEND(
303 204 : FD_LAYOUT_APPEND(
304 204 : FD_LAYOUT_APPEND(
305 204 : FD_LAYOUT_APPEND(
306 204 : FD_LAYOUT_APPEND(
307 204 : FD_LAYOUT_APPEND(
308 204 : FD_LAYOUT_APPEND(
309 204 : FD_LAYOUT_APPEND(
310 204 : FD_LAYOUT_APPEND(
311 204 : FD_LAYOUT_APPEND(
312 204 : FD_LAYOUT_APPEND(
313 204 : FD_LAYOUT_APPEND(
314 204 : FD_LAYOUT_INIT,
315 204 : alignof(fd_chainer_t), sizeof(fd_chainer_t) ),
316 204 : fd_fec_pool_align(), fd_fec_pool_footprint ( fec_max ) ),
317 204 : fd_fec_map_align(), fd_fec_map_footprint ( fec_chain_cnt ) ),
318 204 : fd_slotv_pool_align(), fd_slotv_pool_footprint ( blk_max ) ),
319 204 : alignof(uint), fec_max*sizeof(uint) ), /* fec_tbl */
320 204 : fd_slotv_map_align(), fd_slotv_map_footprint ( blk_chain_cnt ) ),
321 204 : fd_work_pool_align(), fd_work_pool_footprint ( blk_max ) ),
322 204 : fd_work_map_align(), fd_work_map_footprint ( blk_chain_cnt ) ),
323 204 : fd_work_repair_align(), fd_work_repair_footprint ( blk_max ) ),
324 204 : fd_work_orphan_align(), fd_work_orphan_footprint ( blk_max ) ),
325 204 : bfs_align(), bfs_footprint ( blk_max ) ),
326 204 : out_queue_align(), out_queue_footprint ( fec_max ) ),
327 204 : fd_chainer_align() );
328 204 : }
329 :
330 : void *
331 : fd_chainer_new( void * shmem,
332 : ulong ele_max,
333 : ulong max_shreds_per_block,
334 : ulong seed );
335 :
336 : fd_chainer_t *
337 : fd_chainer_join( void * chainer );
338 :
339 : FD_FN_PURE static inline fd_wksp_t *
340 0 : fd_chainer_wksp( fd_chainer_t * chainer ) {
341 0 : return (fd_wksp_t *)( ( (ulong)chainer ) - chainer->wksp_gaddr );
342 0 : }
343 :
344 : /* fd_chainer_highest_repaired_slot returns the highest slot on the
345 : contiguously-repaired chain from root (the analog of
346 : fd_forest_highest_repaired_slot) */
347 :
348 : FD_FN_PURE static inline ulong
349 30 : fd_chainer_highest_repaired_slot( fd_chainer_t const * chainer ) {
350 30 : return chainer->highest_repaired;
351 30 : }
352 :
353 : int
354 : fd_chainer_verify( fd_chainer_t const * chainer );
355 :
356 : void
357 : fd_chainer_init( fd_chainer_t * chainer,
358 : ulong slot,
359 : fd_hash_t const * block_id );
360 :
361 : /* fd_chainer_shred_insert inserts a shred into the chainer. If the
362 : parent_slot is provided, parent_block_id must also be provided.
363 : Otherwise caller should pass AG_UNKNOWN_SLOT for parent_slot.
364 :
365 : The shred may be rejected. */
366 :
367 : void
368 : fd_chainer_shred_insert( fd_chainer_t * chainer,
369 : ulong slot,
370 : uint shred_idx,
371 : int slot_complete,
372 : fd_hash_t const * mr,
373 : ulong parent_slot,
374 : fd_hash_t const * parent_block_id );
375 :
376 : /* fd_chainer_fec_complete returns 0 if the FEC was accepted, 1 if
377 : rejected (unauthorized equivocating root, or fec_set_idx beyond
378 : max_shreds_per_block). */
379 :
380 : int
381 : fd_chainer_fec_complete( fd_chainer_t * chainer,
382 : ulong slot,
383 : uint fec_set_idx,
384 : int slot_complete,
385 : int data_complete,
386 : int is_leader,
387 : fd_hash_t * mr );
388 :
389 : /* fd_chainer_fec_evicted clears out the received shreds for a given
390 : FEC set, and also updates shred tracking for slots that have this FEC
391 : root. */
392 :
393 : void
394 : fd_chainer_fec_evicted( fd_chainer_t * chainer,
395 : ulong slot,
396 : uint fec_set_idx,
397 : fd_hash_t * merkle_root );
398 :
399 :
400 : void
401 : fd_chainer_verified_block_insert( fd_chainer_t * chainer,
402 : ulong slot,
403 : fd_hash_t block_id );
404 :
405 : /* fd_chainer_verified_parent_fec_count is chainer's entrypoint for
406 : updating information on what a slots fec set count, parent slot, and
407 : parent block id are. This mirrors the Alpenglow repair type
408 : getParentAndFecSetCount. The information should be verified before
409 : calling this function; chainer does no verification. Will CRIT if
410 : {slot, block_id} does not exist in the chainer yet, otherwise creates
411 : {parent, p_bid} slotv if it doesn't exist yet, and returns parent
412 : slotv. May return NULL if the parent slotv is on a dead fork. */
413 :
414 : fd_chainer_slotv_t *
415 : fd_chainer_verified_parent_fec_count( fd_chainer_t * chainer,
416 : ulong slot,
417 : fd_hash_t * block_id,
418 : uint fec_set_cnt,
419 : ulong parent_slot,
420 : fd_hash_t * parent_block_id );
421 :
422 : /* fd_chainer_verified_hash_insert is chainer's entrypoint for updating
423 : information on what a slotv's FEC root is. This mirrors the Alpenglow
424 : repair type getFecSetRoot. The information should be verified before
425 : calling this function; chainer does no verification. Will CRIT if
426 : {slot, block_id} does not exist in the chainer yet, otherwise creates
427 : the FEC entry if it doesn't exist yet and updates bookkeeping. */
428 :
429 : void
430 : fd_chainer_verified_hash_insert( fd_chainer_t * chainer,
431 : ulong slot,
432 : fd_hash_t * block_id,
433 : uint fec_set_idx,
434 : fd_hash_t * mr );
435 :
436 : /* fd_chainer_fec_query returns the FEC that the version of slot
437 : identified by block_id owns at fec_set_idx, or NULL. */
438 :
439 : fd_chainer_fec_t *
440 : fd_chainer_fec_query( fd_chainer_t * chainer,
441 : ulong slot,
442 : uint fec_set_idx,
443 : fd_hash_t const * block_id );
444 :
445 : /* fd_chainer_shred_test returns 1 if slotv has data shred shred_idx --
446 : i.e. it owns the FEC at shred_idx's position and that FEC's presence
447 : bitmap has the shred. The per-shred bitmap lives on the (shared) FEC,
448 : so this indexes slotv's fec_tbl row then tests fd_chainer_fec.data_idxs.
449 : Returns 0 for shred_idx at or beyond max_shreds_per_block. */
450 :
451 : int
452 : fd_chainer_shred_test( fd_chainer_t * chainer,
453 : fd_chainer_slotv_t const * slotv,
454 : uint shred_idx );
455 :
456 : /* fd_chainer_publish advances the root to slot. block_id identifies
457 : which version of slot is being rooted; every other version of it is
458 : pruned along with the slots below. Pass NULL (or a block_id no
459 : version matches) to keep all versions of slot. If store is non-NULL,
460 : each pruned FEC set is removed from it (rotor is the store
461 : publisher).
462 :
463 : IMPORTANT! The out_queue must be drained before calling this
464 : function, else there could be stale references to pruned slotvs. */
465 :
466 : void
467 : fd_chainer_publish( fd_chainer_t * chainer,
468 : ulong slot,
469 : fd_hash_t const * block_id,
470 : fd_store_t * store );
471 :
472 : static inline fd_chainer_slotv_t *
473 : fd_chainer_slot_version_query( fd_chainer_t * chainer,
474 : ulong slot,
475 3798 : fd_hash_t const * block_id ) {
476 3798 : fd_chainer_slotv_t * slotv_pool = chainer->slotv_pool;
477 3798 : fd_slotv_map_t * slotv_map = chainer->slotv_map;
478 3798 : for( ulong idx = fd_slotv_map_idx_query_const( slotv_map, &slot, ULONG_MAX, slotv_pool );
479 6762 : idx != ULONG_MAX;
480 6603 : idx = fd_slotv_map_idx_next_const( idx, ULONG_MAX, slotv_pool ) ) {
481 6603 : fd_chainer_slotv_t * slotv = fd_slotv_pool_ele( slotv_pool, idx );
482 6603 : if( FD_UNLIKELY( fd_hash_eq( &slotv->block_id, block_id ) ) ) return slotv;
483 6603 : }
484 159 : return NULL;
485 3798 : }
486 :
487 : /* fd_chainer_slotv_fecs returns slotv's row of chainer->fec_tbl:
488 : fecs[ k ] is the fd_fec_pool idx of the FEC slotv owns at FEC set k
489 : (shred position k*FD_FEC_SHRED_CNT), UINT_MAX if none, for k in
490 : [0,chainer->fec_blk_max). */
491 :
492 : FD_FN_PURE static inline uint *
493 : fd_chainer_slotv_fecs( fd_chainer_t const * chainer,
494 525687 : fd_chainer_slotv_t const * slotv ) {
495 525687 : return chainer->fec_tbl + fd_slotv_pool_idx( chainer->slotv_pool, slotv )*chainer->fec_blk_max;
496 525687 : }
497 :
498 : /* fd_chainer_slot_query returns any version of slot, or NULL if the slot
499 : has no versions in the chainer. */
500 :
501 : static inline fd_chainer_slotv_t *
502 224676 : fd_chainer_slot_query( fd_chainer_t * chainer, ulong slot ) {
503 224676 : fd_chainer_slotv_t * slotv_pool = chainer->slotv_pool;
504 224676 : fd_slotv_map_t * slotv_map = chainer->slotv_map;
505 224676 : ulong idx = fd_slotv_map_idx_query_const( slotv_map, &slot, ULONG_MAX, slotv_pool );
506 224676 : return idx==ULONG_MAX ? NULL : fd_slotv_pool_ele( slotv_pool, idx );
507 224676 : }
508 :
509 : /* fd_chainer_{repair,orphan}_{add,remove} add/removes an slotv from the
510 : repair/orphan worklist treap. Idempotent. _add is called by the
511 : chainer whenever new requestable work appears (slotv created,
512 : complete_idx learned, new sentinel); _remove is called by the repair
513 : walk once the slotv has been fully requested. */
514 :
515 : void
516 : fd_chainer_repair_add( fd_chainer_t * chainer,
517 : fd_chainer_slotv_t * slotv );
518 :
519 : void
520 : fd_chainer_repair_remove( fd_chainer_t * chainer,
521 : fd_chainer_slotv_t * slotv );
522 :
523 : void
524 : fd_chainer_orphan_add( fd_chainer_t * chainer,
525 : fd_chainer_slotv_t * slotv );
526 :
527 : void
528 : fd_chainer_orphan_remove( fd_chainer_t * chainer,
529 : fd_chainer_slotv_t * slotv );
530 :
531 : /* fd_chainer_{repair,orphan}_iter_{init,next} iterate the repair /
532 : orphan worklist in slot order. iter is an opaque index and
533 : fd_chainer_work_iter_done is true once the walk is exhausted.
534 : fd_chainer_work_iter_ele returns the slotv the current element of
535 : either list shadows. Fetch next before removing the current slotv
536 : from the list. */
537 :
538 : ulong
539 : fd_chainer_repair_iter_init( fd_chainer_t * chainer );
540 :
541 : ulong
542 : fd_chainer_repair_iter_next( fd_chainer_t * chainer,
543 : ulong iter );
544 :
545 : ulong
546 : fd_chainer_orphan_iter_init( fd_chainer_t * chainer );
547 :
548 : ulong
549 : fd_chainer_orphan_iter_next( fd_chainer_t * chainer,
550 : ulong iter );
551 :
552 : int
553 : fd_chainer_work_iter_done( ulong iter );
554 :
555 : fd_chainer_slotv_t *
556 : fd_chainer_work_iter_ele( fd_chainer_t * chainer,
557 : ulong iter );
558 :
559 : /* fd_chainer_in_{repair,orphan} report whether slotv is currently in the
560 : repair/orphan worklist. */
561 :
562 : int
563 : fd_chainer_in_repair( fd_chainer_t * chainer,
564 : fd_chainer_slotv_t const * slotv );
565 :
566 : int
567 : fd_chainer_in_orphan( fd_chainer_t * chainer,
568 : fd_chainer_slotv_t const * slotv );
569 :
570 : void
571 : fd_chainer_print( fd_chainer_t * chainer );
572 :
573 : FD_PROTOTYPES_END
574 :
575 : #endif /* HEADER_fd_src_discof_chainer_fd_chainer_h */
|
