Line data Source code
1 : #include "../../ballet/shred/fd_shred.h"
2 : #include "fd_fec_set.h"
3 : #include "../../ballet/sha512/fd_sha512.h"
4 : #include "../../ballet/sha256/fd_sha256.h"
5 : #include "../../ballet/reedsol/fd_reedsol.h"
6 : #include "../metrics/fd_metrics.h"
7 : #include "fd_fec_resolver.h"
8 : #include "fd_fec_samp.h"
9 :
10 :
11 : typedef struct __attribute__((packed)) {
12 : ulong slot;
13 : uint fec_idx;
14 : } slot_fec_pair_t;
15 :
16 : struct __attribute__((aligned(32UL))) set_ctx {
17 : /* The Merkle root. This is the only unique unforgeable identifier of
18 : the FEC set. */
19 : fd_bmtree_node_t root;
20 :
21 : /* The leader's signature of the root of the Merkle tree of the shreds
22 : in this FEC set. If the leader has sent multiple signatures, this
23 : is the first valid one we received. */
24 : fd_ed25519_sig_t sig;
25 :
26 : union {
27 : /* When allocated, it's in a map_chain by the root and a treap
28 : by (shred, FEC set idx). When it's not allocated, it is either
29 : in the free list or the completed list. Both of those slists use
30 : free_next. */
31 : struct {
32 : uint map_next;
33 : uint map_prev;
34 : uint treap_parent;
35 : uint treap_left;
36 : uint treap_right;
37 : uint treap_prio;
38 : };
39 : struct {
40 : uint free_next;
41 : };
42 : };
43 :
44 : ulong slot;
45 : uint fec_set_idx;
46 :
47 : uchar data_variant;
48 : uchar parity_variant;
49 :
50 : /* equivoc is set to 1 if at any moment there is a context in the
51 : map/treap with the same (slot, fec_set_idx) as this one */
52 : uchar equivoc;
53 :
54 : ulong total_rx_shred_cnt;
55 :
56 : fd_fec_set_t * set;
57 :
58 : union {
59 : fd_bmtree_commit_t tree[1];
60 : uchar _footprint[ FD_BMTREE_COMMIT_FOOTPRINT( FD_SHRED_MERKLE_LAYER_CNT ) ] __attribute__((aligned(FD_BMTREE_COMMIT_ALIGN)));
61 : };
62 : };
63 : typedef struct set_ctx set_ctx_t;
64 :
65 : #define MAP_NAME ctx_map
66 9144 : #define MAP_KEY root
67 : #define MAP_KEY_T fd_bmtree_node_t
68 5573 : #define MAP_IDX_T uint
69 9144 : #define MAP_NEXT map_next
70 4573 : #define MAP_PREV map_prev
71 4571 : #define MAP_ELE_T set_ctx_t
72 0 : #define MAP_KEY_EQ(k0,k1) (!memcmp( (k0)->hash, (k1)->hash, 32UL ))
73 9144 : #define MAP_KEY_HASH(key,s) (fd_hash( s, key->hash, 32UL ))
74 : #define MAP_OPTIMIZE_RANDOM_ACCESS_REMOVAL 1
75 : #include "../../util/tmpl/fd_map_chain.c"
76 :
77 :
78 : #define SLIST_NAME ctx_list
79 : #define SLIST_ELE_T set_ctx_t
80 9144 : #define SLIST_IDX_T uint
81 66429 : #define SLIST_NEXT free_next
82 : #include "../../util/tmpl/fd_slist.c"
83 :
84 :
85 : static inline int
86 : slot_fec_pair_compare( slot_fec_pair_t const * q,
87 141754 : set_ctx_t const * e ) {
88 : /* It seems like
89 : return (int)( q->slot!=e->slot ?
90 : q->slot - e->slot :
91 : q->fec_idx - e->fec_set_idx );
92 : should work, but I am concerned about overflow since this is all
93 : attacker controlled input. */
94 141754 : if( FD_LIKELY( q->slot !=e->slot ) ) return fd_int_if( q->slot <e->slot, -1, 1 );
95 141754 : if( FD_LIKELY( q->fec_idx!=e->fec_set_idx ) ) return fd_int_if( q->fec_idx<e->fec_set_idx, -1, 1 );
96 141752 : return 0;
97 141754 : }
98 :
99 : #define TREAP_NAME ctx_treap
100 : #define TREAP_T set_ctx_t
101 18291 : #define TREAP_IDX_T uint
102 9147 : #define TREAP_PARENT treap_parent
103 150899 : #define TREAP_LEFT treap_left
104 150898 : #define TREAP_RIGHT treap_right
105 52701 : #define TREAP_PRIO treap_prio
106 1 : #define TREAP_LT(e0,e1) (((e0)->slot < (e1)->slot) | ( ((e0)->slot==(e1)->slot) & ((e0)->fec_set_idx < (e1)->fec_set_idx)))
107 : #define TREAP_QUERY_T slot_fec_pair_t const *
108 141754 : #define TREAP_CMP(q,e) slot_fec_pair_compare( (q), (e) )
109 : #include "../../util/tmpl/fd_treap.c"
110 :
111 :
112 :
113 : /* Once we're done with a FEC set, it goes into a map_chain and heap,
114 : both keyed by (slot, FEC set idx). */
115 :
116 : struct done_ele {
117 : slot_fec_pair_t key;
118 : uint heap_left; /* also used by pool when not allocated */
119 : uint heap_right;
120 : uint map_next;
121 : uint map_prev;
122 : /* Ideally here we'd store the Merkle root of the one we completed,
123 : but there are two problems with that. First of all, the shreds
124 : don't contain the Merkle root, which means we have to derive it
125 : with a bunch of mildly expensive hashing (about 1us per shred).
126 : Second of all, the Merkle root is relatively large (32 bytes).
127 :
128 : Thankfully, we have a key advantage that we can leverage.
129 : Equivocation detection can be probabilistic. It's not that big of
130 : a deal to reject a shred with IGNORED instead of EQUIVOC as long as
131 : some firedancer node picks up that it is equivoc and produces the
132 : proof. This suggests some kind of validator-specific sampling
133 : solution. The code is factored nicely to be able to iterate on the
134 : sampling in the future. */
135 : fd_fec_samp_t fec_sample[1];
136 : /* Low 56 bits of fd_tickcount() at which this FEC set completed.
137 : Elapsed ticks are computed modulo 2^56, retaining full tick
138 : precision for intervals shorter than 2^56 ticks (about 278 days at
139 : 3 GHz). */
140 : ulong complete_ts : 56;
141 : uchar post_done_turbine_rem; /* decremented after done, but initally set to the number of repair shreds that
142 : contributed to the FEC set. We receive up to 32 unique repair shreds per FEC,
143 : so this number begins maximum at 32. We decrement this as we receive turbine
144 : shreds post-completion, and by proxy measure how eagerly we repaired for
145 : this FEC set. */
146 : };
147 : typedef struct done_ele done_ele_t;
148 : FD_STATIC_ASSERT( sizeof(done_ele_t)==40UL, done_ele_t );
149 : #define SIG_HASH_EQUIVOC UINT_MAX
150 :
151 : #define MAP_NAME done_map
152 4572 : #define MAP_KEY key
153 : #define MAP_KEY_T slot_fec_pair_t
154 307368 : #define MAP_IDX_T uint
155 5066 : #define MAP_NEXT map_next
156 4587 : #define MAP_PREV map_prev
157 0 : #define MAP_ELE_T done_ele_t
158 495 : #define MAP_KEY_EQ(k0,k1) ( ((k0)->slot==(k1)->slot) & ((k0)->fec_idx==(k1)->fec_idx) )
159 155468 : #define MAP_KEY_HASH(key,s) ((fd_ulong_hash( (key)->slot ^ (s) ) ^ fd_uint_hash( (key)->fec_idx ^ (uint)(s>>19) )))
160 : #define MAP_OPTIMIZE_RANDOM_ACCESS_REMOVAL 1
161 : #include "../../util/tmpl/fd_map_chain.c"
162 :
163 : #define HEAP_NAME done_heap
164 4572 : #define HEAP_IDX_T uint
165 9763 : #define HEAP_LEFT heap_left
166 9763 : #define HEAP_RIGHT heap_right
167 : #define HEAP_T done_ele_t
168 5191 : #define HEAP_LT(e0,e1) (((e0)->key.slot < (e1)->key.slot) | \
169 5191 : ( ((e0)->key.slot==(e1)->key.slot) & ((e0)->key.fec_idx < (e1)->key.fec_idx)))
170 : #include "../../util/tmpl/fd_heap.c"
171 :
172 : #define POOL_NAME done_pool
173 2014 : #define POOL_T done_ele_t
174 : #define POOL_IDX_T uint
175 256883 : #define POOL_NEXT heap_left
176 : #include "../../util/tmpl/fd_pool.c"
177 :
178 : struct __attribute__((aligned(FD_FEC_RESOLVER_ALIGN))) fd_fec_resolver {
179 : /* depth stores the number of FEC sets this resolver can track
180 : simultaneously. done_depth stores the depth of the done tcache,
181 : i.e. the number of done FEC set keys that this resolver remembers.
182 : partial_depth stores the minimum size of the free FEC set list.
183 : completed_depth stores the size of the completed FEC set list. */
184 : ulong depth;
185 : ulong partial_depth;
186 : ulong complete_depth;
187 : ulong done_depth;
188 :
189 : /* upper bound on the slot range above the root slot */
190 : ulong slot_max;
191 :
192 : /* expected_shred_version: discard all shreds with a shred version
193 : other than the specified value */
194 : ushort expected_shred_version;
195 :
196 : /* Test/fuzz mode: bypass Merkle+Ed25519 verification in add_shred. */
197 : uchar bypass_verify;
198 :
199 : /* ctx_pool: A flat array (not an fd_pool) of the set_ctx_t
200 : structures used to back ctx_map, ctx_treap, and the ctx
201 : freelists. */
202 : set_ctx_t * ctx_pool;
203 :
204 : /* ctx_map: A map (using fd_map_chain) from Merkle roots to
205 : the context object with its relevant data for in progress FEC sets.
206 : This map contains at most `depth` elements at any time. */
207 : ctx_map_t * ctx_map;
208 :
209 : /* ctx_treap: A treap (using fd_treap) of the context objects for in
210 : progress FEC sets. They are sorted by (slot, FEC index) from
211 : smallest to largest. In the case of equivocation, multiple
212 : elements with the same key may be present, with no particular
213 : ordering between them. */
214 : ctx_treap_t ctx_treap[1];
215 :
216 : /* free_list and complete_list are slists (using fd_slist)
217 : of FEC set contexts that are not in ctx_map. See the long comment
218 : in the header for why there are two. In order to satisfy the
219 : invariants, technically we only need to store the FEC set memory,
220 : not the full context, but it's not that big of a difference
221 : (especially if partial_depth and complete_depth are small), and it
222 : simplifies memory management.
223 :
224 : Invariant: at every entry and exit to fd_fec_resolver_add_shred:
225 : - free_list has between partial_depth and partial_depth+depth
226 : elements.
227 : - complete_list has complete_depth elements
228 : (all these counts are inclusive). */
229 : ctx_list_t free_list[1];
230 : ctx_list_t complete_list[1];
231 :
232 : /* free_list_cnt: The number of items in free_list. */
233 : ulong free_list_cnt;
234 :
235 : /* completion_lag_hist: histogram of how much earlier repair made a
236 : FEC set complete. Completion needs any FD_FEC_SHRED_CNT shreds, so
237 : a set that completed with R repair shreds would have needed R more
238 : turbine arrivals to get there on turbine alone.
239 :
240 : Best effort approximation. It counts turbine *arrivals*, not
241 : distinct shred indices -- the per-set bitmaps are released at
242 : completion. */
243 : fd_histf_t completion_lag_hist[1];
244 :
245 : /* done_pool: A pool (this time using fd_pool) of the done_ele_t
246 : elements that back done_map and done_heap. Invariant: each element
247 : is either (i) released and in the pool, or (ii) in both the
248 : done_map and done_heap. */
249 : done_ele_t * done_pool;
250 :
251 : /* done_map: A map (using fd_map_chain) mapping (slot, fec_idx) to an
252 : element of done_pool. Even in the presence of equivocation, a
253 : specific (slot, fec_idx) tuple occurs at most once in the map,
254 : and the FEC sample is likely set to force_match. In the presence
255 : of equivocation, the right shreds are probably being delivered
256 : using repair, which will bypass reading the done_map, so it doesn't
257 : really matter. */
258 : done_map_t * done_map;
259 :
260 : /* done_heap: A min heap (using fd_heap) based on (slot, fec_idx) used
261 : to stop tracking done elements older than slot_old, and for
262 : eviction in the unlikely case that we run out of elements in the
263 : done_map. */
264 : done_heap_t done_heap[1];
265 :
266 : /* slot_old: slot_old is the lowest slot for which shreds will be
267 : accepted. That is any shred with slot<slot_old is rejected by
268 : add_shred with IGNORED. slot_old can only increase. */
269 : ulong slot_old;
270 :
271 : /* seed: done_map uses seed to compute a hash of the FEC set */
272 : ulong seed;
273 :
274 : /* sha512 and reedsol are used for calculations while adding a shred.
275 : Their state outside a call to add_shred is indeterminate. */
276 : fd_sha512_t sha512[1];
277 : fd_reedsol_t reedsol[1];
278 :
279 : /* ed25519_cache: per leader pubkey precomputation for verifying the
280 : FEC set signatures. A leader signs every set of its slots, so
281 : the few keys active at once repeat for hundreds of sets. */
282 : fd_ed25519_cache_t * ed25519_cache;
283 :
284 : /* The footprint for the objects follows the struct and is in the same
285 : order as the pointers, namely:
286 : ctx_pool
287 : ctx_map
288 : done_pool
289 : done_map
290 : ed25519_cache */
291 : };
292 :
293 : #define ED25519_CACHE_ENT_CNT (16UL)
294 :
295 : typedef struct fd_fec_resolver fd_fec_resolver_t;
296 :
297 : FD_FN_PURE ulong
298 : fd_fec_resolver_footprint( ulong depth,
299 : ulong partial_depth,
300 : ulong complete_depth,
301 1007 : ulong done_depth ) {
302 1007 : if( FD_UNLIKELY( (depth==0UL) | (partial_depth==0UL) | (complete_depth==0UL) | (done_depth==0UL) ) ) return 0UL;
303 1007 : if( FD_UNLIKELY( (depth>UINT_MAX) | (partial_depth>UINT_MAX) | (complete_depth>UINT_MAX) ) ) return 0UL;
304 :
305 1007 : ulong depth_sum = depth + partial_depth + complete_depth;
306 1007 : if( FD_UNLIKELY( depth_sum>=UINT_MAX ) ) return 0UL;
307 :
308 1007 : ulong ctx_chain_cnt = ctx_map_chain_cnt_est ( depth );
309 1007 : ulong done_chain_cnt = done_map_chain_cnt_est( done_depth );
310 :
311 1007 : ulong layout = FD_LAYOUT_INIT;
312 1007 : layout = FD_LAYOUT_APPEND( layout, FD_FEC_RESOLVER_ALIGN, sizeof(fd_fec_resolver_t) );
313 1007 : layout = FD_LAYOUT_APPEND( layout, alignof(set_ctx_t), sizeof(set_ctx_t)*depth_sum );
314 1007 : layout = FD_LAYOUT_APPEND( layout, ctx_map_align(), ctx_map_footprint ( ctx_chain_cnt ) );
315 1007 : layout = FD_LAYOUT_APPEND( layout, done_pool_align(), done_pool_footprint( done_depth ) );
316 1007 : layout = FD_LAYOUT_APPEND( layout, done_map_align(), done_map_footprint ( done_chain_cnt ) );
317 1007 : layout = FD_LAYOUT_APPEND( layout, fd_ed25519_cache_align(), fd_ed25519_cache_footprint( ED25519_CACHE_ENT_CNT ) );
318 :
319 1007 : return FD_LAYOUT_FINI( layout, FD_FEC_RESOLVER_ALIGN );
320 1007 : }
321 :
322 1002 : FD_FN_CONST ulong fd_fec_resolver_align( void ) { return FD_FEC_RESOLVER_ALIGN; }
323 :
324 : fd_histf_t const *
325 0 : fd_fec_resolver_completion_lag_hist( fd_fec_resolver_t const * resolver ) {
326 0 : return resolver->completion_lag_hist;
327 0 : }
328 :
329 :
330 : void *
331 : fd_fec_resolver_new( void * shmem,
332 : ulong depth,
333 : ulong partial_depth,
334 : ulong complete_depth,
335 : ulong done_depth,
336 : ulong slot_max,
337 : fd_fec_set_t * sets,
338 1001 : ulong seed ) {
339 1001 : if( FD_UNLIKELY( (depth==0UL) | (partial_depth==0UL) | (complete_depth==0UL) | (done_depth==0UL) ) ) return NULL;
340 1001 : if( FD_UNLIKELY( (depth>UINT_MAX) | (partial_depth>UINT_MAX) | (complete_depth>UINT_MAX) ) ) return NULL;
341 :
342 1001 : ulong depth_sum = depth + partial_depth + complete_depth;
343 1001 : if( FD_UNLIKELY( depth_sum>=UINT_MAX ) ) return NULL;
344 :
345 1001 : ulong ctx_chain_cnt = ctx_map_chain_cnt_est ( depth );
346 1001 : ulong done_chain_cnt = done_map_chain_cnt_est( done_depth );
347 :
348 : /* round( 2^64 * ... */
349 1001 : ulong seed0 = fd_ulong_hash( seed + 7640891576956012809UL ); /* sqrt(2)-1 */
350 1001 : ulong seed1 = fd_ulong_hash( seed + 13503953896175478587UL ); /* sqrt(3)-1 */
351 1001 : ulong seed2 = fd_ulong_hash( seed + 4354685564936845356UL ); /* sqrt(5)-2 */
352 1001 : ulong seed3 = fd_ulong_hash( seed + 11912009170470909682UL ); /* sqrt(7)-2 */
353 1001 : ulong seed4 = fd_ulong_hash( seed + 5883258537300569243UL ); /* sqrt(11)-3 */
354 :
355 1001 : FD_SCRATCH_ALLOC_INIT( l, shmem );
356 1001 : void * self = FD_SCRATCH_ALLOC_APPEND( l, FD_FEC_RESOLVER_ALIGN, sizeof(fd_fec_resolver_t) );
357 1001 : void * _ctx_pool = FD_SCRATCH_ALLOC_APPEND( l, alignof(set_ctx_t), sizeof(set_ctx_t)*depth_sum );
358 1001 : void * _ctx_map = FD_SCRATCH_ALLOC_APPEND( l, ctx_map_align(), ctx_map_footprint ( ctx_chain_cnt ) );
359 1001 : void * _done_pool = FD_SCRATCH_ALLOC_APPEND( l, done_pool_align(), done_pool_footprint( done_depth ) );
360 1001 : void * _done_map = FD_SCRATCH_ALLOC_APPEND( l, done_map_align(), done_map_footprint ( done_chain_cnt ) );
361 1001 : void * _ed_cache = FD_SCRATCH_ALLOC_APPEND( l, fd_ed25519_cache_align(), fd_ed25519_cache_footprint( ED25519_CACHE_ENT_CNT ) );
362 1001 : FD_SCRATCH_ALLOC_FINI( l, FD_FEC_RESOLVER_ALIGN );
363 :
364 1001 : fd_fec_resolver_t * resolver = (fd_fec_resolver_t *)self;
365 1001 : void * _ctx_treap = resolver->ctx_treap;
366 1001 : void * _free_list = resolver->free_list;
367 1001 : void * _complete_list = resolver->complete_list;
368 1001 : void * _done_heap = resolver->done_heap;
369 :
370 1001 : if( FD_UNLIKELY( !ctx_map_new ( _ctx_map, ctx_chain_cnt, seed0 ) ) ) { FD_LOG_WARNING(( "ctx_map_new fail" )); return NULL; }
371 1001 : if( FD_UNLIKELY( !ctx_treap_new ( _ctx_treap, depth_sum ) ) ) { FD_LOG_WARNING(( "ctx_treap_new fail" )); return NULL; }
372 1001 : if( FD_UNLIKELY( !ctx_list_new ( _free_list ) ) ) { FD_LOG_WARNING(( "ctx_list_new fail" )); return NULL; }
373 1001 : if( FD_UNLIKELY( !ctx_list_new ( _complete_list ) ) ) { FD_LOG_WARNING(( "ctx_list_new fail" )); return NULL; }
374 1001 : if( FD_UNLIKELY( !done_pool_new ( _done_pool, done_depth ) ) ) { FD_LOG_WARNING(( "done_pool_new fail" )); return NULL; }
375 1001 : if( FD_UNLIKELY( !done_map_new ( _done_map, done_chain_cnt, seed1 ) ) ) { FD_LOG_WARNING(( "done_map_new fail" )); return NULL; }
376 1001 : if( FD_UNLIKELY( !done_heap_new ( _done_heap, done_depth ) ) ) { FD_LOG_WARNING(( "done_heap_new fail" )); return NULL; }
377 1001 : if( FD_UNLIKELY( !fd_ed25519_cache_new( _ed_cache, ED25519_CACHE_ENT_CNT, seed4 ) ) ) { FD_LOG_WARNING(( "ed25519_cache_new fail" )); return NULL; }
378 :
379 1001 : fd_histf_join( fd_metrics_histf_new_ns( resolver->completion_lag_hist, FD_MHIST_EDGES_NS( SHRED, REPAIR_LEAD_DELAY_NANOS ) ) );
380 :
381 1001 : set_ctx_t * ctx_pool = (set_ctx_t *)_ctx_pool;
382 1001 : fd_memset( ctx_pool, '\0', sizeof(set_ctx_t)*depth_sum );
383 49216 : for( ulong i=0UL; i<depth_sum; i++ ) ctx_pool[i].set = sets + i;
384 1001 : ctx_treap_seed( ctx_pool, depth_sum, seed2 );
385 :
386 : /* Initialize all the lists */
387 1001 : ctx_list_t * free_list = ctx_list_join( _free_list ); FD_TEST( free_list ==resolver->free_list );
388 1001 : ctx_list_t * complete_list = ctx_list_join( _complete_list ); FD_TEST( complete_list==resolver->complete_list );
389 :
390 41138 : for( ulong i=0UL; i<depth+partial_depth; i++ ) { ctx_list_idx_push_tail( free_list, i, ctx_pool ); }
391 9043 : for( ulong i=depth+partial_depth; i<depth_sum; i++ ) { ctx_list_idx_push_tail( complete_list, i, ctx_pool ); }
392 1001 : ctx_list_leave( complete_list );
393 1001 : ctx_list_leave( free_list );
394 :
395 1001 : fd_sha512_new( resolver->sha512 );
396 :
397 1001 : resolver->depth = depth;
398 1001 : resolver->partial_depth = partial_depth;
399 1001 : resolver->complete_depth = complete_depth;
400 1001 : resolver->done_depth = done_depth;
401 1001 : resolver->slot_max = slot_max;
402 1001 : resolver->expected_shred_version = 0;
403 1001 : resolver->bypass_verify = 0;
404 1001 : resolver->free_list_cnt = depth+partial_depth;
405 1001 : resolver->slot_old = 0UL;
406 1001 : resolver->seed = seed3;
407 1001 : return shmem;
408 1001 : }
409 :
410 : fd_fec_resolver_t *
411 1006 : fd_fec_resolver_join( void * shmem ) {
412 1006 : fd_fec_resolver_t * resolver = (fd_fec_resolver_t *)shmem;
413 1006 : ulong depth = resolver->depth;
414 1006 : ulong partial_depth = resolver->partial_depth;
415 1006 : ulong complete_depth = resolver->complete_depth;
416 1006 : ulong done_depth = resolver->done_depth;
417 :
418 1006 : ulong depth_sum = depth + partial_depth + complete_depth;
419 1006 : if( FD_UNLIKELY( depth_sum>=UINT_MAX ) ) return NULL;
420 :
421 1006 : ulong ctx_chain_cnt = ctx_map_chain_cnt_est ( depth );
422 1006 : ulong done_chain_cnt = done_map_chain_cnt_est( done_depth );
423 :
424 1006 : FD_SCRATCH_ALLOC_INIT( l, shmem );
425 1006 : /* self */ FD_SCRATCH_ALLOC_APPEND( l, FD_FEC_RESOLVER_ALIGN, sizeof(fd_fec_resolver_t) );
426 1006 : void * _ctx_pool = FD_SCRATCH_ALLOC_APPEND( l, alignof(set_ctx_t), sizeof(set_ctx_t)*depth_sum );
427 1006 : void * _ctx_map = FD_SCRATCH_ALLOC_APPEND( l, ctx_map_align(), ctx_map_footprint ( ctx_chain_cnt ) );
428 1006 : void * _done_pool = FD_SCRATCH_ALLOC_APPEND( l, done_pool_align(), done_pool_footprint( done_depth ) );
429 1006 : void * _done_map = FD_SCRATCH_ALLOC_APPEND( l, done_map_align(), done_map_footprint ( done_chain_cnt ) );
430 1006 : void * _ed_cache = FD_SCRATCH_ALLOC_APPEND( l, fd_ed25519_cache_align(), fd_ed25519_cache_footprint( ED25519_CACHE_ENT_CNT ) );
431 1006 : FD_SCRATCH_ALLOC_FINI( l, FD_FEC_RESOLVER_ALIGN );
432 :
433 1006 : resolver->ctx_pool = (set_ctx_t *)_ctx_pool;
434 1006 : resolver->ctx_map = ctx_map_join ( _ctx_map ); if( FD_UNLIKELY( !resolver->ctx_map ) ) return NULL;
435 1006 : resolver->done_pool = done_pool_join ( _done_pool ); if( FD_UNLIKELY( !resolver->done_pool ) ) return NULL;
436 1006 : resolver->done_map = done_map_join ( _done_map ); if( FD_UNLIKELY( !resolver->done_map ) ) return NULL;
437 1006 : resolver->ed25519_cache = fd_ed25519_cache_join( _ed_cache ); if( FD_UNLIKELY( !resolver->ed25519_cache ) ) return NULL;
438 1006 : if( FD_UNLIKELY( ctx_treap_join( resolver->ctx_treap )!= resolver->ctx_treap ) ) return NULL;
439 1006 : if( FD_UNLIKELY( ctx_list_join ( resolver->free_list )!= resolver->free_list ) ) return NULL;
440 1006 : if( FD_UNLIKELY( ctx_list_join ( resolver->complete_list )!= resolver->complete_list ) ) return NULL;
441 1006 : if( FD_UNLIKELY( done_heap_join( resolver->done_heap )!= resolver->done_heap ) ) return NULL;
442 1006 : if( FD_UNLIKELY( fd_sha512_join( resolver->sha512 )!= resolver->sha512 ) ) return NULL;
443 :
444 1006 : return resolver;
445 1006 : }
446 :
447 : void
448 : fd_fec_resolver_set_shred_version( fd_fec_resolver_t * resolver,
449 1006 : ushort expected_shred_version ) {
450 1006 : resolver->expected_shred_version = expected_shred_version;
451 1006 : }
452 :
453 : void
454 : fd_fec_resolver_set_bypass_verify( fd_fec_resolver_t * resolver,
455 1007 : int bypass_verify ) {
456 1007 : resolver->bypass_verify = (uchar)!!bypass_verify;
457 1007 : }
458 :
459 : void
460 : fd_fec_resolver_advance_slot_old( fd_fec_resolver_t * resolver,
461 1007 : ulong slot_old ) {
462 1007 : if( FD_UNLIKELY( slot_old <= resolver->slot_old ) ) return;
463 1007 : resolver->slot_old = slot_old;
464 :
465 : /* Remove from done map */
466 1007 : done_heap_t * done_heap = resolver->done_heap;
467 1007 : done_map_t * done_map = resolver->done_map;
468 1007 : done_ele_t * done_pool = resolver->done_pool;
469 :
470 1007 : while( done_heap_ele_cnt( done_heap ) ) {
471 0 : done_ele_t * min_ele = done_heap_ele_peek_min( done_heap, done_pool );
472 0 : if( FD_UNLIKELY( min_ele->key.slot>=slot_old ) ) break;
473 0 : done_map_ele_remove_fast( done_map, min_ele, done_pool );
474 0 : done_heap_idx_remove_min( done_heap, done_pool );
475 0 : done_pool_ele_release ( done_pool, min_ele );
476 0 : }
477 :
478 : /* Remove from in progress map */
479 1007 : ctx_map_t * ctx_map = resolver->ctx_map;
480 1007 : ctx_treap_t * ctx_treap = resolver->ctx_treap;
481 1007 : set_ctx_t * ctx_pool = resolver->ctx_pool;
482 1007 : ctx_list_t * free_list = resolver->free_list;
483 :
484 1007 : ctx_treap_fwd_iter_t next;
485 1007 : for( ctx_treap_fwd_iter_t iter=ctx_treap_fwd_iter_init( ctx_treap, ctx_pool ); !ctx_treap_fwd_iter_done( iter ); iter=next ) {
486 0 : next = ctx_treap_fwd_iter_next( iter, ctx_pool );
487 0 : set_ctx_t * min_ele = ctx_treap_fwd_iter_ele( iter, ctx_pool );
488 0 : if( FD_UNLIKELY( min_ele->slot>=slot_old ) ) break;
489 :
490 0 : ctx_treap_ele_remove ( ctx_treap, min_ele, ctx_pool );
491 0 : ctx_map_ele_remove_fast( ctx_map, min_ele, ctx_pool );
492 0 : ctx_list_ele_push_head ( free_list, min_ele, ctx_pool );
493 0 : resolver->free_list_cnt++;
494 0 : }
495 1007 : }
496 :
497 : static inline void
498 : ensure_done_pool_free( done_ele_t * done_pool,
499 : done_heap_t * done_heap,
500 4572 : done_map_t * done_map ) {
501 4572 : if( FD_UNLIKELY( !done_pool_free( done_pool ) ) ) {
502 : /* Done map is full, so we'll forget about the oldest slot */
503 0 : ulong worst_idx = done_heap_idx_peek_min( done_heap );
504 0 : FD_TEST( worst_idx!=done_heap_idx_null() ); /* Done pool can't be empty and full at the same time */
505 0 : done_heap_idx_remove_min( done_heap, done_pool );
506 0 : done_map_idx_remove_fast( done_map, worst_idx, done_pool );
507 0 : done_pool_idx_release( done_pool, worst_idx );
508 : /* Now it's not empty */
509 0 : }
510 4572 : }
511 :
512 :
513 : int
514 : fd_fec_resolver_add_shred( fd_fec_resolver_t * resolver,
515 : fd_shred_t const * shred,
516 : ulong shred_sz,
517 : ulong max_shred_idx,
518 : uint source,
519 : uchar const * leader_pubkey,
520 : fd_fec_set_t const * * out_fec_set,
521 : fd_shred_t const * * out_shred,
522 : fd_bmtree_node_t * out_merkle_root,
523 146325 : fd_fec_resolver_spilled_t * out_spilled ) {
524 146325 : FD_TEST( source<=FD_FEC_RESOLVER_SHRED_SRC_BAD_REPAIR );
525 :
526 : /* Unpack variables */
527 146325 : ulong partial_depth = resolver->partial_depth;
528 :
529 146325 : ctx_list_t * free_list = resolver->free_list;
530 146325 : ctx_list_t * complete_list = resolver->complete_list;
531 146325 : ctx_map_t * ctx_map = resolver->ctx_map;
532 146325 : ctx_treap_t * ctx_treap = resolver->ctx_treap;
533 146325 : set_ctx_t * ctx_pool = resolver->ctx_pool;
534 146325 : done_map_t * done_map = resolver->done_map;
535 146325 : done_ele_t * done_pool = resolver->done_pool;
536 146325 : done_heap_t * done_heap = resolver->done_heap;
537 :
538 146325 : fd_reedsol_t * reedsol = resolver->reedsol;
539 146325 : fd_sha512_t * sha512 = resolver->sha512;
540 :
541 : /* Invariants:
542 : * each set_ctx_t is in exactly one of ctx_map, freelist, or
543 : complete_list */
544 :
545 : /* Is this shred for a slot we've already rooted or otherwise don't
546 : care about? */
547 146325 : if( FD_UNLIKELY( shred->slot<resolver->slot_old ) ) return FD_FEC_RESOLVER_SHRED_IGNORED;
548 146325 : if( FD_UNLIKELY( resolver->slot_max && shred->slot>=resolver->slot_old+resolver->slot_max ) ) return FD_FEC_RESOLVER_SHRED_IGNORED;
549 :
550 : /* Do a bunch of quick validity checks */
551 146325 : if( FD_UNLIKELY( shred->version!=resolver->expected_shred_version ) ) return FD_FEC_RESOLVER_SHRED_REJECTED;
552 146325 : if( FD_UNLIKELY( shred_sz<fd_shred_sz( shred ) ) ) return FD_FEC_RESOLVER_SHRED_REJECTED;
553 146325 : if( FD_UNLIKELY( shred->idx>=max_shred_idx ) ) return FD_FEC_RESOLVER_SHRED_REJECTED;
554 146325 : if( FD_UNLIKELY( shred->fec_set_idx>max_shred_idx-FD_FEC_SHRED_CNT ) ) return FD_FEC_RESOLVER_SHRED_REJECTED;
555 146325 : if( FD_UNLIKELY( shred->idx-shred->fec_set_idx>=FD_FEC_SHRED_CNT ) ) return FD_FEC_RESOLVER_SHRED_REJECTED;
556 146325 : if( FD_UNLIKELY( shred->fec_set_idx%FD_FEC_SHRED_CNT!=0UL ) ) return FD_FEC_RESOLVER_SHRED_REJECTED;
557 :
558 146325 : uchar variant = shred->variant;
559 146325 : uchar shred_type = fd_shred_type( variant );
560 :
561 146325 : int is_data_shred = fd_shred_is_data( shred_type );
562 :
563 146325 : if( !is_data_shred ) { /* Roughly 50/50 branch */
564 0 : if( FD_UNLIKELY( (shred->code.data_cnt!=FD_FEC_SHRED_CNT) | (shred->code.code_cnt!=FD_FEC_SHRED_CNT) ) )
565 0 : return FD_FEC_RESOLVER_SHRED_REJECTED;
566 0 : if( FD_UNLIKELY( shred->code.idx>=FD_FEC_SHRED_CNT ) ) return FD_FEC_RESOLVER_SHRED_REJECTED;
567 0 : if( FD_UNLIKELY( shred->code.idx!=shred->idx%FD_FEC_SHRED_CNT ) ) return FD_FEC_RESOLVER_SHRED_REJECTED;
568 : /* We want to ignore parity shreds corresponding to data shreds for
569 : which the parent slot is something we've already pruned (see
570 : below), but the parent offset is only a field in data shreds. We
571 : could do it at reconstruction time, but then there's not a good
572 : return code. It would be like a FEC_FATAL_REJECT, but returning
573 : IGNORED. So instead we just snoop into the parity data and pick
574 : out the parent_off. If all data shreds have the same value for
575 : parent_off, then all parity shreds will have that same value at
576 : the corresponding bytes. If the data shreds have different
577 : values, this comparison is non-sensical, but we'll reject the FEC
578 : set later. */
579 0 : ushort parent_off = FD_LOAD( ushort, fd_shred_code_payload( shred )+0x53UL-0x40UL );
580 0 : if( FD_UNLIKELY( shred->slot-parent_off<resolver->slot_old ) ) return FD_FEC_RESOLVER_SHRED_IGNORED;
581 146325 : } else {
582 : /* if the shred's parent is for a slot we've already pruned, ignore it. */
583 146325 : if( FD_UNLIKELY( shred->slot-shred->data.parent_off<resolver->slot_old ) ) return FD_FEC_RESOLVER_SHRED_IGNORED;
584 :
585 : /* if it has slot complete, it must be the last one in the FEC. */
586 146325 : if( FD_UNLIKELY( (shred->data.flags & FD_SHRED_DATA_FLAG_SLOT_COMPLETE) && ((1UL+shred->idx) % FD_FEC_SHRED_CNT) ) ) {
587 0 : return FD_FEC_RESOLVER_SHRED_REJECTED;
588 0 : }
589 :
590 : /* if it has data complete, it must be the last data shred in the FEC set
591 : https://github.com/anza-xyz/agave/blob/v4.3.0-beta.0/ledger/src/shred/filter.rs#L346-L354 */
592 146325 : if( FD_UNLIKELY( ( shred->data.flags & FD_SHRED_DATA_FLAG_DATA_COMPLETE ) &&
593 146325 : ( shred->idx != ( shred->fec_set_idx + ( FD_FEC_SHRED_CNT - 1UL ) ) ) ) ) {
594 0 : return FD_FEC_RESOLVER_SHRED_REJECTED;
595 0 : }
596 146325 : }
597 :
598 146325 : if( FD_UNLIKELY( !fd_shred_is_chained( shred_type ) ) ) {
599 : /* Reject any legacy and unchained shreds */
600 0 : return FD_FEC_RESOLVER_SHRED_REJECTED;
601 0 : }
602 :
603 : /* For the purposes of the shred header, tree_depth means the number
604 : of nodes, counting the leaf but excluding the root. For bmtree,
605 : depth means the number of layers, which counts both. */
606 146325 : ulong tree_depth = fd_shred_merkle_cnt( variant ); /* In [0, 15] */
607 :
608 : /* in_type_idx is between [0, code.data_cnt) or [0, code.code_cnt),
609 : where data_cnt <= FD_FEC_SHRED_CNT and code_cnt <= FD_FEC_SHRED_CNT
610 : On the other hand, shred_idx, goes from [0, code.data_cnt +
611 : code.code_cnt), with all the data shreds having
612 : shred_idx < code.data_cnt and all the parity shreds having
613 : shred_idx >= code.data_cnt. */
614 146325 : ulong in_type_idx = fd_ulong_if( is_data_shred, shred->idx - shred->fec_set_idx, shred->code.idx );
615 146325 : ulong shred_idx = fd_ulong_if( is_data_shred, in_type_idx, in_type_idx + shred->code.data_cnt );
616 :
617 146325 : if( FD_UNLIKELY( ( shred->fec_set_idx % FD_FEC_SHRED_CNT ) != 0UL ) ) return FD_FEC_RESOLVER_SHRED_REJECTED;
618 146325 : if( FD_UNLIKELY( in_type_idx >= FD_FEC_SHRED_CNT ) ) return FD_FEC_RESOLVER_SHRED_REJECTED;
619 :
620 : /* This, combined with the check on shred->code.data_cnt implies that
621 : shred_idx is in [0, 2*FD_FEC_SHRED_CNT). */
622 :
623 146325 : if( FD_UNLIKELY( tree_depth!=FD_SHRED_MERKLE_LAYER_CNT-1UL ) ) return FD_FEC_RESOLVER_SHRED_REJECTED;
624 :
625 : /* Now we're done with all the simple, quick checks */
626 146325 : int is_repair = source==FD_FEC_RESOLVER_SHRED_SRC_REPAIR && is_data_shred;
627 :
628 146325 : set_ctx_t * ctx = NULL;
629 :
630 : /* If we detect a different Merkle root for the same (slot, FEC set
631 : idx), it means either the shred is invalid, or the leader is
632 : equivocating. We can't tell which without verifying the shred
633 : though. */
634 146325 : int equivoc_or_invalid = 0;
635 :
636 146325 : slot_fec_pair_t const slot_fec_pair[1] = {{ .slot = shred->slot, .fec_idx = shred->fec_set_idx }};
637 :
638 : /* If it's from Turbine, we'll first check if we've already completed
639 : the FEC set (likely case) or another FEC set for the same (slot,
640 : FEC set idx) pair (unlikely case). Either case will lead to
641 : rejecting the shred, but possibly later via the equivoc_or_invalid
642 : if we need to validate it. */
643 146326 : if( FD_LIKELY( !is_repair ) ) {
644 : /* Most likely, it's just done. */
645 146326 : done_ele_t * done_ele = done_map_ele_query( done_map, slot_fec_pair, NULL, done_pool );
646 146326 : if( FD_LIKELY( done_ele ) ) {
647 0 : if( FD_LIKELY( fd_fec_samp_matches( done_ele->fec_sample, resolver->seed, shred ) ) ) {
648 0 : if( FD_UNLIKELY( (source==FD_FEC_RESOLVER_SHRED_SRC_TURBINE) & (done_ele->post_done_turbine_rem>0L) ) ) {
649 : /* Turbine has now supplied as many shreds for this set as
650 : repair contributed, so this is approx. when the set would
651 : have completed on turbine alone. */
652 0 : done_ele->post_done_turbine_rem--;
653 0 : if( FD_UNLIKELY( done_ele->post_done_turbine_rem==0 ) ) {
654 0 : ulong lag = ((ulong)fd_tickcount() - (ulong)done_ele->complete_ts) & ((1UL<<56)-1UL);
655 0 : fd_histf_sample( resolver->completion_lag_hist, lag );
656 0 : }
657 0 : }
658 0 : return FD_FEC_RESOLVER_SHRED_IGNORED;
659 0 : }
660 :
661 0 : equivoc_or_invalid = 1;
662 0 : }
663 : /* There could be 0, 1, or >1 contexts in the treap with this (slot,
664 : FEC set index). If there are >1, this sets ctx to an arbitrary
665 : one, which may or may not have the Merkle root that matches this
666 : shred. Regardless, we'll reject it with equivoc_or_invalid. */
667 146326 : ctx = ctx_treap_ele_query( ctx_treap, slot_fec_pair, ctx_pool );
668 146326 : if( FD_LIKELY( ctx ) ) equivoc_or_invalid |= ctx->equivoc;
669 146326 : }
670 :
671 :
672 146325 : ulong reedsol_protected_sz = 1115UL + FD_SHRED_DATA_HEADER_SZ - FD_SHRED_SIGNATURE_SZ - FD_SHRED_MERKLE_NODE_SZ*tree_depth
673 146325 : - FD_SHRED_MERKLE_ROOT_SZ*fd_shred_is_chained ( shred_type )
674 146325 : - FD_SHRED_SIGNATURE_SZ *fd_shred_is_resigned( shred_type); /* In [743, 1139] conservatively*/
675 146325 : ulong data_merkle_protected_sz = reedsol_protected_sz + FD_SHRED_MERKLE_ROOT_SZ*fd_shred_is_chained( shred_type );
676 146325 : ulong parity_merkle_protected_sz = reedsol_protected_sz + FD_SHRED_MERKLE_ROOT_SZ*fd_shred_is_chained( shred_type )
677 146325 : + FD_SHRED_CODE_HEADER_SZ - FD_ED25519_SIG_SZ;
678 146325 : ulong merkle_protected_sz = fd_ulong_if( is_data_shred, data_merkle_protected_sz, parity_merkle_protected_sz );
679 :
680 146325 : fd_bmtree_node_t leaf[1];
681 :
682 146325 : fd_bmtree_hash_leaf( leaf, (uchar const *)shred + sizeof(fd_ed25519_sig_t), merkle_protected_sz, FD_BMTREE_LONG_PREFIX_SZ );
683 :
684 :
685 146325 : if( FD_UNLIKELY( is_repair ) ) {
686 : /* If it's coming from repair, we're willing to do the work to
687 : compute the Merkle root and lookup the ctx by Merkle root. */
688 0 : fd_bmtree_node_t _root[1];
689 0 : fd_bmtree_node_t * root = fd_bmtree_from_proof( leaf, shred_idx, _root, (uchar const *)fd_shred_merkle_nodes( shred ),
690 0 : tree_depth, FD_SHRED_MERKLE_NODE_SZ, FD_BMTREE_LONG_PREFIX_SZ );
691 :
692 0 : ctx = ctx_map_ele_query( ctx_map, root, NULL, ctx_pool );
693 0 : }
694 :
695 146325 : if( FD_UNLIKELY( !ctx ) ) { /* This is the first shred in the FEC set */
696 :
697 4572 : if( FD_UNLIKELY( resolver->free_list_cnt<=partial_depth ) ) {
698 : /* Packet loss is really high and we have a lot of in-progress FEC
699 : sets that we haven't been able to finish. Evict the context
700 : with the highest (slot, FEC idx). This is the one that is the
701 : farthest away from what we're currently replaying, which means
702 : we have the longest time to request it via repair if we
703 : actually need it. This also handles the case where a leader
704 : sends some shreds from their slots that are far in the future
705 : in this epoch. */
706 0 : set_ctx_t * victim_ctx = ctx_treap_rev_iter_ele( ctx_treap_rev_iter_init( ctx_treap, ctx_pool ), ctx_pool );
707 :
708 0 : if( FD_LIKELY( out_spilled ) ) {
709 0 : out_spilled->slot = victim_ctx->slot;
710 0 : out_spilled->fec_set_idx = victim_ctx->fec_set_idx;
711 0 : *out_spilled->merkle_root = victim_ctx->root;
712 0 : }
713 :
714 : /* Remove from treap and map, then add to free_list */
715 0 : ctx_treap_ele_remove ( ctx_treap, victim_ctx, ctx_pool );
716 0 : ctx_map_ele_remove_fast( ctx_map, victim_ctx, ctx_pool );
717 :
718 0 : ctx_list_ele_push_tail ( free_list, victim_ctx, ctx_pool );
719 0 : resolver->free_list_cnt++;
720 :
721 0 : FD_MCNT_INC( SHRED, FEC_INCOMPLETE_EVICTED, 1UL );
722 0 : }
723 : /* Now we know |free_list|>partial_depth */
724 :
725 4572 : ctx = ctx_list_ele_pop_head( free_list, ctx_pool );
726 4572 : resolver->free_list_cnt--;
727 :
728 : /* Now we need to derive the root of the Merkle tree and verify the
729 : signature to prevent a DOS attack just by sending lots of invalid
730 : shreds. If this shred came from repair, we're redoing
731 : computation, but the code is gross otherwise. */
732 4572 : fd_bmtree_commit_t * tree;
733 4572 : tree = fd_bmtree_commit_init( ctx->_footprint, FD_SHRED_MERKLE_NODE_SZ, FD_BMTREE_LONG_PREFIX_SZ, FD_SHRED_MERKLE_LAYER_CNT );
734 4572 : FD_TEST( tree==ctx->tree );
735 :
736 4572 : fd_bmtree_node_t _root[1] = {0};
737 :
738 4572 : fd_shred_merkle_t const * proof = fd_shred_merkle_nodes( shred );
739 4572 : int rv = fd_bmtree_commitp_insert_with_proof( tree, shred_idx, leaf, (uchar const *)proof, tree_depth, _root );
740 4572 : if( FD_UNLIKELY( !rv ) ) {
741 0 : ctx_list_ele_push_head( free_list, ctx, ctx_pool );
742 0 : resolver->free_list_cnt++;
743 0 : FD_MCNT_INC( SHRED, INITIAL_REJECTED, 1UL );
744 0 : return FD_FEC_RESOLVER_SHRED_REJECTED;
745 0 : }
746 :
747 4572 : if( FD_LIKELY( !resolver->bypass_verify ) ) {
748 0 : if( FD_UNLIKELY( FD_ED25519_SUCCESS != fd_ed25519_verify_cached( _root->hash, 32UL, shred->signature, leader_pubkey, sha512, resolver->ed25519_cache ) ) ) {
749 0 : ctx_list_ele_push_head( free_list, ctx, ctx_pool );
750 0 : resolver->free_list_cnt++;
751 0 : FD_MCNT_INC( SHRED, INITIAL_REJECTED, 1UL );
752 0 : return FD_FEC_RESOLVER_SHRED_REJECTED;
753 0 : }
754 0 : }
755 :
756 : /* Copy the merkle root into the output arg. */
757 4573 : if( FD_LIKELY( out_merkle_root ) ) memcpy( out_merkle_root, _root, sizeof(fd_bmtree_node_t) );
758 :
759 4572 : if( FD_UNLIKELY( equivoc_or_invalid ) ) {
760 : /* It wasn't invalid, so it must be equivoc. As a reminder, this
761 : is the case where is_repair==0, we had the (slot, FEC set idx)
762 : in the done_map, and this shred didn't match the FEC sample. */
763 0 : ctx_list_ele_push_head( free_list, ctx, ctx_pool );
764 0 : resolver->free_list_cnt++;
765 : /* We want to record that we've sigverified the shred somewhere so
766 : that if an attacker sends it to us again, we don't have to
767 : verify it again. We do that by inserting it into the done_map
768 : with force_match. */
769 0 : done_ele_t * done = done_map_ele_query( done_map, slot_fec_pair, NULL, done_pool );
770 0 : if( FD_LIKELY( done ) ) fd_fec_samp_set_force_match( done->fec_sample );
771 0 : else {
772 : /* This case can't happen right now, but keep it in case some
773 : code gets added that could evict from the done_map between
774 : the !is_repair query and here. */
775 0 : ensure_done_pool_free( done_pool, done_heap, done_map );
776 :
777 0 : done = done_pool_ele_acquire( done_pool );
778 :
779 0 : done->key.slot = shred->slot;
780 0 : done->key.fec_idx = shred->fec_set_idx;
781 0 : done->complete_ts = 0UL;
782 0 : done->post_done_turbine_rem = 0U;
783 0 : fd_fec_samp_set_force_match( done->fec_sample );
784 :
785 0 : done_heap_ele_insert( done_heap, done, done_pool );
786 0 : done_map_ele_insert ( done_map, done, done_pool );
787 0 : }
788 :
789 0 : return FD_FEC_RESOLVER_SHRED_EQUIVOC;
790 0 : }
791 : /* Do we already have something in the treap for the same (slot, FEC
792 : idx) of this shred? If so, mark this one and the old one as
793 : equivocating. If we have multiple, marking the old one will be a
794 : no-op, which means we don't care which one query returns. */
795 4572 : uchar equivoc = 0;
796 4572 : set_ctx_t * equivoc_ctx = ctx_treap_ele_query( ctx_treap, slot_fec_pair, ctx_pool );
797 4572 : if( FD_UNLIKELY( equivoc_ctx ) ) {
798 0 : equivoc_ctx->equivoc = 1;
799 0 : equivoc = 1;
800 0 : }
801 :
802 : /* This seems like a legitimate FEC set, so we populate the rest of
803 : the fields, then add it to the map and treap. */
804 4572 : memcpy( ctx->sig, shred->signature, 64UL );
805 4572 : ctx->slot = shred->slot;
806 4572 : ctx->fec_set_idx = shred->fec_set_idx;
807 4572 : ctx->data_variant = fd_uchar_if( is_data_shred, variant, fd_shred_variant( fd_shred_swap_type( shred_type ), (uchar)tree_depth ) );
808 4572 : ctx->parity_variant = fd_uchar_if( !is_data_shred, variant, fd_shred_variant( fd_shred_swap_type( shred_type ), (uchar)tree_depth ) );
809 4572 : ctx->equivoc = equivoc;
810 4572 : ctx->total_rx_shred_cnt = 0UL;
811 4572 : ctx->root = *_root;
812 :
813 : /* Reset the FEC set */
814 4572 : ctx->set->data_shred_rcvd = 0U;
815 4572 : ctx->set->parity_shred_rcvd = 0U;
816 4572 : ctx->set->turbine_shred_rcvd = 0UL;
817 4572 : ctx->set->repair_shred_rcvd = 0UL;
818 :
819 4572 : ctx_map_ele_insert ( ctx_map, ctx, ctx_pool );
820 4572 : ctx_treap_ele_insert( ctx_treap, ctx, ctx_pool );
821 :
822 141753 : } else {
823 : /* This is not the first shred in the set */
824 :
825 : /* Verify that the shred's slot and fec_set_idx match the context
826 : established by the first shred. */
827 141753 : if( FD_UNLIKELY( shred->slot!=ctx->slot || shred->fec_set_idx!=ctx->fec_set_idx ) ) {
828 0 : return FD_FEC_RESOLVER_SHRED_REJECTED;
829 0 : }
830 :
831 : /* First ensure that all the shreds in the FEC set have consistent
832 : variants. They all must have the same tree_depth and the same
833 : chained/not chained, resigned/not resigned bits. */
834 141753 : if( FD_UNLIKELY( variant!=fd_uchar_if( is_data_shred, ctx->data_variant, ctx->parity_variant ) ) ) {
835 0 : return FD_FEC_RESOLVER_SHRED_REJECTED;
836 0 : }
837 :
838 141753 : int matching_root = 1;
839 141753 : fd_bmtree_node_t _root[1];
840 141753 : int matching_sig = fd_memeq( ctx->sig, shred->signature, 64UL );
841 141760 : if( FD_UNLIKELY( resolver->bypass_verify ) ) {
842 141760 : *_root = ctx->root;
843 141760 : matching_sig = 1;
844 >1844*10^16 : } else {
845 >1844*10^16 : fd_shred_merkle_t const * proof = fd_shred_merkle_nodes( shred );
846 >1844*10^16 : int rv = fd_bmtree_commitp_insert_with_proof( ctx->tree, shred_idx, leaf, (uchar const *)proof, tree_depth, _root );
847 >1844*10^16 : if( FD_UNLIKELY( !rv ) ) {
848 : /* This means we've gotten a shred with a different Merkle root
849 : than ctx. This can only happen in the Turbine case, because
850 : otherwise ctx comes from the Merkle-root keyed map. We need
851 : to check the signature before we know if it's EQUIVOC or
852 : REJECTED. */
853 0 : fd_bmtree_node_t * root = fd_bmtree_from_proof( leaf, shred_idx, _root, (uchar const *)fd_shred_merkle_nodes( shred ),
854 0 : tree_depth, FD_SHRED_MERKLE_NODE_SZ, FD_BMTREE_LONG_PREFIX_SZ );
855 0 : (void)root; /* it has to be ==_root. If it were going to fail,
856 : it would have happened earlier. */
857 0 : matching_root = 0;
858 0 : }
859 >1844*10^16 : }
860 :
861 141753 : if( FD_UNLIKELY( !(matching_root & matching_sig ) ) ) {
862 : /* There are a few things that could be going on here.
863 : 1. A malicious validator could be producing an alternative
864 : signature for the same Merkle root
865 : 2. A malicious validator could be equivocating (valid
866 : signature, different Merkle root)
867 : 3. Someone could be sending us a shred from a FEC set the
868 : leader previously signed, but with a clobbered signature
869 : 4. Someone could be sending us total junk.
870 : Note: if bypass_verify is true, this branch can't be taken. */
871 0 : if( FD_UNLIKELY( FD_ED25519_SUCCESS != fd_ed25519_verify_cached( _root->hash, 32UL, shred->signature, leader_pubkey, sha512, resolver->ed25519_cache ) ) ) {
872 : /* Case 3 or 4, reject it */
873 0 : return FD_FEC_RESOLVER_SHRED_REJECTED;
874 0 : }
875 0 : }
876 :
877 141760 : if( FD_LIKELY( out_merkle_root ) ) *out_merkle_root = *_root;
878 :
879 141753 : if( FD_UNLIKELY( (!matching_root) | equivoc_or_invalid ) ) {
880 : /* Case 2, or other equivocation. Store it as equivocating and then reject it. */
881 0 : done_ele_t * done = done_map_ele_query( done_map, slot_fec_pair, NULL, done_pool );
882 0 : if( FD_LIKELY( done ) ) fd_fec_samp_set_force_match( done->fec_sample );
883 0 : else {
884 0 : ensure_done_pool_free( done_pool, done_heap, done_map );
885 :
886 0 : done = done_pool_ele_acquire( done_pool );
887 :
888 0 : done->key.slot = shred->slot;
889 0 : done->key.fec_idx = shred->fec_set_idx;
890 0 : done->complete_ts = 0UL;
891 0 : done->post_done_turbine_rem = 0U;
892 0 : fd_fec_samp_set_force_match( done->fec_sample );
893 :
894 0 : done_heap_ele_insert( done_heap, done, done_pool );
895 0 : done_map_ele_insert ( done_map, done, done_pool );
896 0 : }
897 0 : return FD_FEC_RESOLVER_SHRED_EQUIVOC;
898 0 : }
899 : /* Otherwise, this must be case 1, which is fine */
900 :
901 : /* Check to make sure this is not a duplicate */
902 : /* We need to make sure that if repair evicted this set and is
903 : re-repairing it, we aren't ignoring its shreds, which would keep
904 : the set from ever completing. In the old days, we would return
905 : IGNORED earlier for non-repair shreds, but in order to determine
906 : if we already have the shred (and so should IGNORE it), we need
907 : to make sure we have the right ctx, and we don't have a way to
908 : map shred ctx precisely without deriving the Merkle root, so that
909 : doesn't make sense anymore. */
910 141753 : int shred_dup = !!(fd_uint_if( is_data_shred, ctx->set->data_shred_rcvd, ctx->set->parity_shred_rcvd ) & (1U << in_type_idx));
911 :
912 141753 : if( FD_UNLIKELY( shred_dup ) ) {
913 0 : *out_shred = is_data_shred ? ctx->set->data_shreds[ in_type_idx ].s : ctx->set->parity_shreds[ in_type_idx ].s;
914 0 : return fd_int_if( is_repair, FD_FEC_RESOLVER_SHRED_DUPLICATE, FD_FEC_RESOLVER_SHRED_IGNORED );
915 0 : }
916 141753 : }
917 :
918 : /* At this point, the shred has passed Merkle validation and is new.
919 : We also know that ctx is a pointer to the set_ctx_t where this
920 : shred belongs. */
921 :
922 : /* Copy the shred to memory the FEC resolver owns */
923 >1844*10^16 : uchar * dst = is_data_shred ? ctx->set->data_shreds[ in_type_idx ].b : ctx->set->parity_shreds[ in_type_idx ].b;
924 146325 : fd_memcpy( dst, shred, fd_shred_sz( shred ) );
925 :
926 : /* Resigned shreds are relayed with a zero retransmitter signature:
927 : nothing verifies it (verify_retransmitter_signature never activated
928 : and is superseded by Alpenglow) */
929 146325 : if( FD_UNLIKELY( fd_shred_is_resigned( shred_type ) ) ) {
930 0 : memset( dst + fd_shred_retransmitter_sig_off( (fd_shred_t *)dst ), 0, 64UL );
931 0 : }
932 :
933 146325 : ctx->set->data_shred_rcvd |= (uint)(!!is_data_shred)<<in_type_idx;
934 146325 : ctx->set->parity_shred_rcvd |= (uint)( !is_data_shred)<<in_type_idx;
935 146325 : ulong shred_bit = 1UL<<shred_idx;
936 146328 : if( source==FD_FEC_RESOLVER_SHRED_SRC_TURBINE ) ctx->set->turbine_shred_rcvd |= shred_bit;
937 >1844*10^16 : else ctx->set->repair_shred_rcvd |= shred_bit;
938 146325 : ctx->total_rx_shred_cnt++;
939 :
940 146325 : *out_shred = (fd_shred_t const *)dst;
941 :
942 : /* Do we have enough to begin reconstruction? */
943 146325 : if( FD_LIKELY( ctx->total_rx_shred_cnt < FD_FEC_SHRED_CNT ) ) return FD_FEC_RESOLVER_SHRED_OKAY;
944 :
945 : /* At this point, the FEC set is either valid or permanently invalid,
946 : so we can consider it done either way. */
947 :
948 4569 : done_ele_t * done = NULL;
949 :
950 : /* If it's already in the done map, we don't need to re-insert it.
951 : It's not very clear what we should do if it's for a different FEC
952 : set, but this can only happen the second insert was a repair shred,
953 : and in that case, it gets bypassed anyway, so it doesn't really
954 : matter. We'll just keep the existing value in that case. */
955 4569 : slot_fec_pair_t done_key[1] = {{ .slot = ctx->slot, .fec_idx = ctx->fec_set_idx }};
956 4572 : if( FD_LIKELY( !done_map_ele_query( done_map, done_key, NULL, done_pool ) ) ) {
957 4572 : ensure_done_pool_free( done_pool, done_heap, done_map );
958 :
959 4572 : done = done_pool_ele_acquire( done_pool );
960 :
961 4572 : done->key.slot = ctx->slot;
962 4572 : done->key.fec_idx = ctx->fec_set_idx;
963 4572 : done->complete_ts = (ulong)fd_tickcount() & ((1UL<<56)-1UL);
964 4572 : done->post_done_turbine_rem = (uchar)fd_ulong_popcnt( ctx->set->repair_shred_rcvd );
965 :
966 4572 : if( FD_LIKELY( !!ctx->set->repair_shred_rcvd ) ) {
967 0 : FD_MCNT_INC( SHRED, REPAIR_COMPLETION_ASSISTED, 1UL );
968 0 : }
969 : /* We need to finish the reedsol_recover and inserting all the
970 : missing shreds into the tree before we can properly
971 : derive this, so for now, we'll set it as force match. If we hit
972 : one of the FEC_FATAL_REJECTED cases below, which is extremely
973 : rare, we'll end up rejecting all Turbine shreds for this (slot,
974 : FEC set idx). That's not ideal, but the block is going to get
975 : skipped unless the leader equivocates. */
976 4572 : fd_fec_samp_set_force_match( done->fec_sample );
977 :
978 4572 : done_heap_ele_insert( done_heap, done, done_pool );
979 4572 : done_map_ele_insert ( done_map, done, done_pool );
980 4572 : }
981 :
982 :
983 4569 : ctx_map_ele_remove_fast( ctx_map, ctx, ctx_pool );
984 4569 : ctx_treap_ele_remove ( ctx_treap, ctx, ctx_pool );
985 : /* At this point, ctx is not in any of the data structures, so we need
986 : to be sure to add it to one of the lists before exiting. */
987 :
988 4569 : fd_fec_set_t * set = ctx->set;
989 4569 : fd_bmtree_commit_t * tree = ctx->tree;
990 :
991 4569 : reedsol = fd_reedsol_recover_init( (void*)reedsol, reedsol_protected_sz );
992 150834 : for( ulong i=0UL; i<FD_FEC_SHRED_CNT; i++ ) {
993 146265 : uchar * rs_payload = set->data_shreds[ i ].b + sizeof(fd_ed25519_sig_t);
994 146273 : if( set->data_shred_rcvd&(1U<<i) ) fd_reedsol_recover_add_rcvd_shred ( reedsol, 1, rs_payload );
995 >1844*10^16 : else fd_reedsol_recover_add_erased_shred( reedsol, 1, rs_payload );
996 146265 : }
997 150848 : for( ulong i=0UL; i<FD_FEC_SHRED_CNT; i++ ) {
998 146279 : uchar * rs_payload = set->parity_shreds[ i ].b + FD_SHRED_CODE_HEADER_SZ;
999 146279 : if( set->parity_shred_rcvd&(1U<<i) ) fd_reedsol_recover_add_rcvd_shred ( reedsol, 0, rs_payload );
1000 146279 : else fd_reedsol_recover_add_erased_shred( reedsol, 0, rs_payload );
1001 146279 : }
1002 :
1003 4569 : if( FD_UNLIKELY( FD_REEDSOL_SUCCESS != fd_reedsol_recover_fini( reedsol ) ) ) {
1004 : /* Exactly FD_FEC_SHRED_CNT shreds are present. Any such subset
1005 : defines a codeword, so recovery cannot detect an inconsistent
1006 : FEC set here. A malicious leader's inconsistent shreds are caught
1007 : by checking the recovered shreds against the signed Merkle root
1008 : below. */
1009 0 : ctx_list_ele_push_tail( free_list, ctx, ctx_pool );
1010 0 : resolver->free_list_cnt++;
1011 0 : FD_MCNT_INC( SHRED, FEC_FATAL_REJECTED, 1UL );
1012 0 : return FD_FEC_RESOLVER_SHRED_REJECTED;
1013 0 : }
1014 :
1015 4569 : uchar const * chained_root = fd_ptr_if( fd_shred_is_chained( shred_type ), (uchar *)shred+fd_shred_chain_off( variant ), NULL );
1016 :
1017 : /* Populate the recovered shreds' headers and hash their leaves in
1018 : sha256 batches. As in the shredder, the leaf prefix sits in the
1019 : unwritten signature tail; the signature is copied in afterwards. */
1020 4569 : ulong const prefix_off = sizeof(fd_ed25519_sig_t)-FD_BMTREE_LONG_PREFIX_SZ;
1021 4569 : fd_bmtree_node_t leaves[ 2UL*FD_FEC_SHRED_CNT ];
1022 4569 : uchar batch_mem[ FD_SHA256_BATCH_FOOTPRINT ] __attribute__((aligned(FD_SHA256_BATCH_ALIGN)));
1023 4569 : fd_sha256_batch_t * batch = fd_sha256_batch_init( batch_mem );
1024 :
1025 150873 : for( ulong i=0UL; i<FD_FEC_SHRED_CNT; i++ ) {
1026 146304 : if( !(set->data_shred_rcvd&(1U<<i)) ) {
1027 0 : if( FD_LIKELY( fd_shred_is_chained( shred_type ) ) ) {
1028 0 : fd_memcpy( set->data_shreds[i].b+fd_shred_chain_off( ctx->data_variant ), chained_root, FD_SHRED_MERKLE_ROOT_SZ );
1029 0 : }
1030 0 : if( FD_LIKELY( !resolver->bypass_verify ) ) {
1031 0 : fd_memcpy( set->data_shreds[i].b+prefix_off, fd_bmtree_leaf_prefix, FD_BMTREE_LONG_PREFIX_SZ );
1032 0 : fd_sha256_batch_add( batch, set->data_shreds[i].b+prefix_off, data_merkle_protected_sz+FD_BMTREE_LONG_PREFIX_SZ, leaves[ i ].hash );
1033 0 : }
1034 0 : }
1035 146304 : }
1036 :
1037 150787 : for( ulong i=0UL; i<FD_FEC_SHRED_CNT; i++ ) {
1038 146218 : if( !(set->parity_shred_rcvd&(1U<<i)) ) {
1039 146218 : fd_shred_t * p_shred = set->parity_shreds[i].s; /* We can't parse because we haven't populated the header */
1040 146218 : p_shred->variant = ctx->parity_variant;
1041 146218 : p_shred->slot = shred->slot;
1042 146218 : p_shred->idx = (uint)(i + ctx->fec_set_idx);
1043 146218 : p_shred->version = shred->version;
1044 146218 : p_shred->fec_set_idx = (uint)ctx->fec_set_idx;
1045 146218 : p_shred->code.data_cnt = (ushort)FD_FEC_SHRED_CNT;
1046 146218 : p_shred->code.code_cnt = (ushort)FD_FEC_SHRED_CNT;
1047 146218 : p_shred->code.idx = (ushort)i;
1048 :
1049 146218 : if( FD_LIKELY( fd_shred_is_chained( shred_type ) ) ) {
1050 146216 : fd_memcpy( set->parity_shreds[i].b+fd_shred_chain_off( ctx->parity_variant ), chained_root, FD_SHRED_MERKLE_ROOT_SZ );
1051 146216 : }
1052 146218 : if( FD_LIKELY( !resolver->bypass_verify ) ) {
1053 0 : fd_memcpy( set->parity_shreds[i].b+prefix_off, fd_bmtree_leaf_prefix, FD_BMTREE_LONG_PREFIX_SZ );
1054 0 : fd_sha256_batch_add( batch, set->parity_shreds[i].b+prefix_off, parity_merkle_protected_sz+FD_BMTREE_LONG_PREFIX_SZ, leaves[ FD_FEC_SHRED_CNT+i ].hash );
1055 0 : }
1056 146218 : }
1057 146218 : }
1058 4569 : fd_sha256_batch_fini( batch );
1059 :
1060 : /* Copy the signatures in, then insert the leaves in the same order */
1061 150873 : for( ulong i=0UL; i<FD_FEC_SHRED_CNT; i++ ) {
1062 146304 : if( !(set->data_shred_rcvd&(1U<<i)) ) {
1063 0 : fd_memcpy( set->data_shreds[i].b, shred, sizeof(fd_ed25519_sig_t) );
1064 0 : if( FD_LIKELY( !resolver->bypass_verify ) ) {
1065 0 : if( FD_UNLIKELY( !fd_bmtree_commitp_insert_with_proof( tree, i, leaves+i, NULL, 0, NULL ) ) ) {
1066 0 : ctx_list_ele_push_tail( free_list, ctx, ctx_pool );
1067 0 : resolver->free_list_cnt++;
1068 0 : FD_MCNT_INC( SHRED, FEC_FATAL_REJECTED, 1UL );
1069 0 : return FD_FEC_RESOLVER_SHRED_REJECTED;
1070 0 : }
1071 0 : }
1072 0 : }
1073 146304 : }
1074 :
1075 150758 : for( ulong i=0UL; i<FD_FEC_SHRED_CNT; i++ ) {
1076 146190 : if( !(set->parity_shred_rcvd&(1U<<i)) ) {
1077 146190 : fd_memcpy( set->parity_shreds[i].s->signature, shred->signature, sizeof(fd_ed25519_sig_t) );
1078 146190 : if( FD_LIKELY( !resolver->bypass_verify ) ) {
1079 0 : if( FD_UNLIKELY( !fd_bmtree_commitp_insert_with_proof( tree, FD_FEC_SHRED_CNT + i, leaves+FD_FEC_SHRED_CNT+i, NULL, 0, NULL ) ) ) {
1080 0 : ctx_list_ele_push_tail( free_list, ctx, ctx_pool );
1081 0 : resolver->free_list_cnt++;
1082 0 : FD_MCNT_INC( SHRED, FEC_FATAL_REJECTED, 1UL );
1083 0 : return FD_FEC_RESOLVER_SHRED_REJECTED;
1084 0 : }
1085 0 : }
1086 146190 : }
1087 146189 : }
1088 :
1089 : /* Check that the whole Merkle tree is consistent. */
1090 4569 : if( FD_UNLIKELY( !resolver->bypass_verify && !fd_bmtree_commitp_fini( tree, FD_FEC_SHRED_CNT + FD_FEC_SHRED_CNT ) ) ) {
1091 0 : ctx_list_ele_push_tail( free_list, ctx, ctx_pool );
1092 0 : resolver->free_list_cnt++;
1093 0 : FD_MCNT_INC( SHRED, FEC_FATAL_REJECTED, 1UL );
1094 0 : return FD_FEC_RESOLVER_SHRED_REJECTED;
1095 0 : }
1096 :
1097 : /* We now have fully populated the bmtree, so we can derive the
1098 : fec_sample. */
1099 4569 : if( FD_LIKELY( done && !resolver->bypass_verify ) ) fd_fec_samp_derive( done->fec_sample, resolver->seed, ctx->slot, ctx->fec_set_idx, ctx->sig, &ctx->root, tree );
1100 :
1101 : /* Check that all the fields that are supposed to be consistent across
1102 : an FEC set actually are. */
1103 4569 : fd_shred_t const * base_data_shred = fd_shred_parse( set->data_shreds [ 0 ].b, FD_SHRED_MIN_SZ, max_shred_idx );
1104 4569 : fd_shred_t const * base_parity_shred = fd_shred_parse( set->parity_shreds[ 0 ].b, FD_SHRED_MAX_SZ, max_shred_idx );
1105 4569 : int reject = (!base_data_shred) | (!base_parity_shred);
1106 :
1107 : /* Check idx of base shreds */
1108 4571 : reject = reject || ((base_data_shred->idx!=ctx->fec_set_idx) | (base_parity_shred->idx!=ctx->fec_set_idx) |
1109 4571 : (base_data_shred->data.flags & FD_SHRED_DATA_FLAG_DATA_COMPLETE));
1110 :
1111 146265 : for( ulong i=1UL; (!reject) & (i<FD_FEC_SHRED_CNT); i++ ) {
1112 : /* Technically, we only need to re-parse the ones we recovered with
1113 : Reedsol, but parsing is pretty cheap and the rest of the
1114 : validation we need to do on all of them. */
1115 141696 : fd_shred_t const * parsed = fd_shred_parse( set->data_shreds[ i ].b, FD_SHRED_MIN_SZ, max_shred_idx );
1116 141696 : if( FD_UNLIKELY( !parsed ) ) { reject = 1; break; }
1117 141696 : reject |= parsed->variant != base_data_shred->variant;
1118 141696 : reject |= parsed->slot != base_data_shred->slot;
1119 141696 : reject |= parsed->version != base_data_shred->version;
1120 141696 : reject |= parsed->fec_set_idx != base_data_shred->fec_set_idx;
1121 141696 : reject |= parsed->data.parent_off != base_data_shred->data.parent_off;
1122 141696 : reject |= parsed->idx != (uint)(ctx->fec_set_idx+i);
1123 141696 : reject |= (i!=FD_FEC_SHRED_CNT-1UL) && (parsed->data.flags & FD_SHRED_DATA_FLAG_DATA_COMPLETE);
1124 :
1125 141696 : reject |= fd_shred_is_chained( fd_shred_type( parsed->variant ) ) &&
1126 141696 : !fd_memeq( (uchar *)parsed +fd_shred_chain_off( parsed->variant ),
1127 141688 : (uchar *)base_data_shred+fd_shred_chain_off( base_data_shred->variant ), FD_SHRED_MERKLE_ROOT_SZ );
1128 141696 : }
1129 :
1130 150839 : for( ulong i=0UL; (!reject) & (i<FD_FEC_SHRED_CNT); i++ ) {
1131 146270 : fd_shred_t const * parsed = fd_shred_parse( set->parity_shreds[ i ].b, FD_SHRED_MAX_SZ, max_shred_idx );
1132 146270 : if( FD_UNLIKELY( !parsed ) ) { reject = 1; break; }
1133 146270 : reject |= fd_shred_type( parsed->variant ) != fd_shred_swap_type( fd_shred_type( base_data_shred->variant ) );
1134 146270 : reject |= fd_shred_merkle_cnt( parsed->variant ) != fd_shred_merkle_cnt( base_data_shred->variant );
1135 146270 : reject |= parsed->slot != base_data_shred->slot;
1136 146270 : reject |= parsed->version != base_data_shred->version;
1137 146270 : reject |= parsed->fec_set_idx != base_data_shred->fec_set_idx;
1138 146270 : reject |= parsed->idx != (uint)(ctx->fec_set_idx+i);
1139 146270 : reject |= parsed->code.data_cnt != base_parity_shred->code.data_cnt;
1140 146270 : reject |= parsed->code.code_cnt != base_parity_shred->code.code_cnt;
1141 146270 : reject |= parsed->code.idx != (ushort)i;
1142 :
1143 146270 : reject |= fd_shred_is_chained( fd_shred_type( parsed->variant ) ) &&
1144 146270 : !fd_memeq( (uchar *)parsed +fd_shred_chain_off( parsed->variant ),
1145 146267 : (uchar *)base_data_shred+fd_shred_chain_off( base_data_shred->variant ), FD_SHRED_MERKLE_ROOT_SZ );
1146 146270 : }
1147 4569 : if( FD_UNLIKELY( reject ) ) {
1148 0 : ctx_list_ele_push_tail( free_list, ctx, ctx_pool );
1149 0 : resolver->free_list_cnt++;
1150 0 : FD_MCNT_INC( SHRED, FEC_FATAL_REJECTED, 1UL );
1151 0 : return FD_FEC_RESOLVER_SHRED_REJECTED;
1152 0 : }
1153 :
1154 :
1155 : /* Populate missing Merkle proofs */
1156 150852 : for( ulong i=0UL; i<FD_FEC_SHRED_CNT; i++ ) if( !( set->data_shred_rcvd&(1U<<i) ) )
1157 0 : fd_bmtree_get_proof( tree, set->data_shreds[i].b + fd_shred_merkle_off( set->data_shreds[i].s ), i );
1158 :
1159 150837 : for( ulong i=0UL; i<FD_FEC_SHRED_CNT; i++ ) if( !( set->parity_shred_rcvd&(1U<<i) ) )
1160 146267 : fd_bmtree_get_proof( tree, set->parity_shreds[i].b + fd_shred_merkle_off( set->parity_shreds[i].s ), FD_FEC_SHRED_CNT+i );
1161 :
1162 : /* Zero retransmitter signature on the recovered shreds too */
1163 4569 : if( FD_UNLIKELY( fd_shred_is_resigned( shred_type ) ) ) {
1164 0 : for( ulong i=0UL; i<FD_FEC_SHRED_CNT; i++ ) if( !( set->data_shred_rcvd&(1U<<i) ) )
1165 0 : memset( set->data_shreds[i].b + fd_shred_retransmitter_sig_off( set->data_shreds[i].s ), 0, 64UL );
1166 :
1167 0 : for( ulong i=0UL; i<FD_FEC_SHRED_CNT; i++ ) if( !( set->parity_shred_rcvd&(1U<<i) ) )
1168 0 : memset( set->parity_shreds[i].b + fd_shred_retransmitter_sig_off( set->parity_shreds[i].s ), 0, 64UL );
1169 0 : }
1170 :
1171 : /* Finally... A valid FEC set. Forward it along. */
1172 4569 : ctx_list_ele_push_tail( complete_list, ctx, ctx_pool );
1173 4569 : ctx_list_idx_push_tail( free_list, ctx_list_idx_pop_head( complete_list, ctx_pool ), ctx_pool );
1174 4569 : resolver->free_list_cnt++;
1175 :
1176 4569 : *out_fec_set = set;
1177 :
1178 4569 : return FD_FEC_RESOLVER_SHRED_COMPLETES;
1179 4569 : }
1180 :
1181 :
1182 0 : void * fd_fec_resolver_leave( fd_fec_resolver_t * resolver ) {
1183 0 : fd_ed25519_cache_leave( resolver->ed25519_cache );
1184 0 : fd_sha512_leave ( resolver->sha512 );
1185 0 : done_heap_leave ( resolver->done_heap );
1186 0 : ctx_list_leave ( resolver->complete_list );
1187 0 : ctx_list_leave ( resolver->free_list );
1188 0 : ctx_treap_leave ( resolver->ctx_treap );
1189 0 : done_map_leave ( resolver->done_map );
1190 0 : done_pool_leave ( resolver->done_pool );
1191 0 : ctx_map_leave ( resolver->ctx_map );
1192 :
1193 0 : return (void *)resolver;
1194 0 : }
1195 :
1196 0 : void * fd_fec_resolver_delete( void * shmem ) {
1197 0 : fd_fec_resolver_t * resolver = (fd_fec_resolver_t *)shmem;
1198 0 : ulong depth = resolver->depth;
1199 0 : ulong partial_depth = resolver->partial_depth;
1200 0 : ulong complete_depth = resolver->complete_depth;
1201 0 : ulong done_depth = resolver->done_depth;
1202 :
1203 0 : ulong depth_sum = depth + partial_depth + complete_depth;
1204 0 : ulong ctx_chain_cnt = ctx_map_chain_cnt_est ( depth );
1205 0 : ulong done_chain_cnt = done_map_chain_cnt_est( done_depth );
1206 :
1207 0 : FD_SCRATCH_ALLOC_INIT( l, shmem );
1208 0 : /* self */ FD_SCRATCH_ALLOC_APPEND( l, FD_FEC_RESOLVER_ALIGN, sizeof(fd_fec_resolver_t) );
1209 0 : /* _ctx_pool */ FD_SCRATCH_ALLOC_APPEND( l, alignof(set_ctx_t), sizeof(set_ctx_t)*depth_sum );
1210 0 : void * _ctx_map = FD_SCRATCH_ALLOC_APPEND( l, ctx_map_align(), ctx_map_footprint ( ctx_chain_cnt ) );
1211 0 : void * _done_pool = FD_SCRATCH_ALLOC_APPEND( l, done_pool_align(), done_pool_footprint( done_depth ) );
1212 0 : void * _done_map = FD_SCRATCH_ALLOC_APPEND( l, done_map_align(), done_map_footprint ( done_chain_cnt ) );
1213 0 : void * _ed_cache = FD_SCRATCH_ALLOC_APPEND( l, fd_ed25519_cache_align(), fd_ed25519_cache_footprint( ED25519_CACHE_ENT_CNT ) );
1214 0 : FD_SCRATCH_ALLOC_FINI( l, FD_FEC_RESOLVER_ALIGN );
1215 :
1216 0 : fd_ed25519_cache_delete( _ed_cache );
1217 0 : fd_sha512_delete ( resolver->sha512 );
1218 0 : done_heap_delete ( resolver->done_heap );
1219 0 : done_map_delete ( _done_map );
1220 0 : done_pool_delete ( _done_pool );
1221 0 : ctx_list_delete ( resolver->complete_list );
1222 0 : ctx_list_delete ( resolver->free_list );
1223 0 : ctx_treap_delete ( resolver->ctx_treap );
1224 0 : ctx_map_delete ( _ctx_map );
1225 :
1226 0 : return shmem;
1227 0 : }
|
