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/reedsol/fd_reedsol.h"
5 : #include "../metrics/fd_metrics.h"
6 : #include "fd_fec_resolver.h"
7 :
8 : typedef union {
9 : fd_ed25519_sig_t u;
10 : ulong l;
11 : } wrapped_sig_t;
12 :
13 : typedef struct __attribute__((packed)) {
14 : ulong slot;
15 : uint fec_idx;
16 : } slot_fec_pair_t;
17 :
18 : struct __attribute__((aligned(32UL))) set_ctx {
19 : /* The leader's signature of the root of the Merkle tree of the shreds
20 : in this FEC set. */
21 : wrapped_sig_t sig;
22 :
23 : union {
24 : /* When allocated, it's in a map_chain by signature and a treap
25 : by (shred, FEC set idx). When it's not allocated, it is either
26 : in the free list or the completed list. Both of those slists use
27 : free_next. */
28 : struct {
29 : uint map_next;
30 : uint map_prev;
31 : uint treap_parent;
32 : uint treap_left;
33 : uint treap_right;
34 : uint treap_prio;
35 : };
36 : struct {
37 : uint free_next;
38 : };
39 : };
40 :
41 : ulong slot;
42 : uint fec_set_idx;
43 :
44 : uchar data_variant;
45 : uchar parity_variant;
46 :
47 : ulong total_rx_shred_cnt;
48 :
49 : fd_fec_set_t * set;
50 :
51 : fd_bmtree_node_t root;
52 : /* If this FEC set has resigned shreds, this is our signature of the
53 : root of the Merkle tree */
54 : wrapped_sig_t retransmitter_sig;
55 :
56 : union {
57 : fd_bmtree_commit_t tree[1];
58 : uchar _footprint[ FD_BMTREE_COMMIT_FOOTPRINT( FD_SHRED_MERKLE_LAYER_CNT ) ] __attribute__((aligned(FD_BMTREE_COMMIT_ALIGN)));
59 : };
60 : };
61 : typedef struct set_ctx set_ctx_t;
62 :
63 : #define MAP_NAME ctx_map
64 513 : #define MAP_KEY sig
65 : #define MAP_KEY_T wrapped_sig_t
66 16743 : #define MAP_IDX_T uint
67 3801 : #define MAP_NEXT map_next
68 2436 : #define MAP_PREV map_prev
69 252 : #define MAP_ELE_T set_ctx_t
70 8628 : #define MAP_KEY_EQ(k0,k1) (!memcmp( (k0)->u, (k1)->u, FD_ED25519_SIG_SZ ))
71 8736 : #define MAP_KEY_HASH(key,s) (fd_ulong_hash( (key)->l ^ (s) ))
72 : #define MAP_OPTIMIZE_RANDOM_ACCESS_REMOVAL 1
73 : #include "../../util/tmpl/fd_map_chain.c"
74 :
75 :
76 : #define SLIST_NAME ctx_list
77 : #define SLIST_ELE_T set_ctx_t
78 486 : #define SLIST_IDX_T uint
79 1107 : #define SLIST_NEXT free_next
80 : #include "../../util/tmpl/fd_slist.c"
81 :
82 :
83 : static inline int
84 : slot_fec_pair_compare( slot_fec_pair_t const * q,
85 48 : set_ctx_t const * e ) {
86 : /* It seems like
87 : return (int)( q->slot!=e->slot ?
88 : q->slot - e->slot :
89 : q->fec_idx - e->fec_set_idx );
90 : should work, but I am concerned about overflow since this is all
91 : attacker controlled input. */
92 48 : if( FD_LIKELY( q->slot !=e->slot ) ) return fd_int_if( q->slot <e->slot, -1, 1 );
93 48 : if( FD_LIKELY( q->fec_idx!=e->fec_set_idx ) ) return fd_int_if( q->fec_idx<e->fec_set_idx, -1, 1 );
94 0 : return 0;
95 48 : }
96 :
97 : #define TREAP_NAME ctx_treap
98 : #define TREAP_T set_ctx_t
99 1083 : #define TREAP_IDX_T uint
100 582 : #define TREAP_PARENT treap_parent
101 588 : #define TREAP_LEFT treap_left
102 618 : #define TREAP_RIGHT treap_right
103 483 : #define TREAP_PRIO treap_prio
104 69 : #define TREAP_LT(e0,e1) (((e0)->slot < (e1)->slot) | ( ((e0)->slot==(e1)->slot) & ((e0)->fec_set_idx < (e1)->fec_set_idx)))
105 : #define TREAP_QUERY_T slot_fec_pair_t const *
106 48 : #define TREAP_CMP(q,e) slot_fec_pair_compare( (q), (e) )
107 : #include "../../util/tmpl/fd_treap.c"
108 :
109 :
110 :
111 : /* Once we're done with a FEC set, it goes into a map_chain and heap,
112 : both keyed by (slot, FEC set idx). */
113 :
114 : struct done_ele {
115 : slot_fec_pair_t key;
116 : uint heap_left; /* also used by pool when not allocated */
117 : uint heap_right;
118 : uint map_next;
119 : uint map_prev;
120 : /* In order to save space in the done_map and make this struct 32
121 : bytes, we store a 32 bit validator-specific hash of the shred
122 : signature. If a malicious leader equivocates and produces two FEC
123 : sets which have the same hash for us, a task which takes a decent
124 : but doable amount of effort, the only impact is that we would
125 : reject the shreds with SHRED_IGNORED instead of SHRED_EQUIVOC,
126 : which is not a big deal. It's documented that SHRED_EQUIVOC
127 : detection is on a best-effort basis. If we detect an equivocation
128 : for this (slot, FEC set idx), sig_hash gets set to
129 : SIG_HASH_EQUIVOC, and we start returning SHRED_IGNORED for any
130 : non-repair shred for that (slot, FEC set idx). */
131 : uint sig_hash;
132 : };
133 : typedef struct done_ele done_ele_t;
134 : FD_STATIC_ASSERT( sizeof(done_ele_t)==32UL, done_ele_t );
135 0 : #define SIG_HASH_EQUIVOC UINT_MAX
136 :
137 : #define MAP_NAME done_map
138 300 : #define MAP_KEY key
139 : #define MAP_KEY_T slot_fec_pair_t
140 2268 : #define MAP_IDX_T uint
141 1161 : #define MAP_NEXT map_next
142 642 : #define MAP_PREV map_prev
143 141 : #define MAP_ELE_T done_ele_t
144 1080 : #define MAP_KEY_EQ(k0,k1) ( ((k0)->slot==(k1)->slot) & ((k0)->fec_idx==(k1)->fec_idx) )
145 1308 : #define MAP_KEY_HASH(key,s) ((fd_ulong_hash( (key)->slot ^ (s) ) ^ fd_uint_hash( (key)->fec_idx ^ (uint)(s>>19) )))
146 : #define MAP_OPTIMIZE_RANDOM_ACCESS_REMOVAL 1
147 : #include "../../util/tmpl/fd_map_chain.c"
148 :
149 : #define HEAP_NAME done_heap
150 360 : #define HEAP_IDX_T uint
151 774 : #define HEAP_LEFT heap_left
152 774 : #define HEAP_RIGHT heap_right
153 : #define HEAP_T done_ele_t
154 414 : #define HEAP_LT(e0,e1) (((e0)->key.slot < (e1)->key.slot) | \
155 414 : ( ((e0)->key.slot==(e1)->key.slot) & ((e0)->key.fec_idx < (e1)->key.fec_idx)))
156 : #include "../../util/tmpl/fd_heap.c"
157 :
158 : #define POOL_NAME done_pool
159 87 : #define POOL_T done_ele_t
160 : #define POOL_IDX_T uint
161 465 : #define POOL_NEXT heap_left
162 : #include "../../util/tmpl/fd_pool.c"
163 :
164 : struct __attribute__((aligned(FD_FEC_RESOLVER_ALIGN))) fd_fec_resolver {
165 : /* depth stores the number of FEC sets this resolver can track
166 : simultaneously. done_depth stores the depth of the done tcache,
167 : i.e. the number of done FEC set keys that this resolver remembers.
168 : partial_depth stores the minimum size of the free FEC set list.
169 : completed_depth stores the size of the completed FEC set list. */
170 : ulong depth;
171 : ulong partial_depth;
172 : ulong complete_depth;
173 : ulong done_depth;
174 :
175 : /* expected_shred_version: discard all shreds with a shred version
176 : other than the specified value */
177 : ushort expected_shred_version;
178 :
179 : /* Test/fuzz mode: bypass Merkle+Ed25519 verification in add_shred. */
180 : uchar bypass_verify;
181 :
182 : /* ctx_pool: A flat array (not an fd_pool) of the set_ctx_t
183 : structures used to back ctx_map, ctx_treap, and the ctx
184 : freelists. */
185 : set_ctx_t * ctx_pool;
186 :
187 : /* ctx_map: A map (using fd_map_chain) from signatures to
188 : the context object with its relevant data for in progress FEC sets.
189 : This map contains at most `depth` elements at any time. */
190 : ctx_map_t * ctx_map;
191 :
192 : /* ctx_treap: A treap (using fd_treap) of the context objects for in
193 : progress FEC sets. They are sorted by (slot, FEC index) from
194 : smallest to largest. In the case of equivocation, multiple
195 : elements with the same key may be present, with no particular
196 : ordering between them. */
197 : ctx_treap_t ctx_treap[1];
198 :
199 : /* free_list and complete_list are slists (using fd_slist)
200 : of FEC set contexts that are not in ctx_map. See the long comment
201 : in the header for why there are two. In order to satisfy the
202 : invariants, technically we only need to store the FEC set memory,
203 : not the full context, but it's not that big of a difference
204 : (especially if partial_depth and complete_depth are small), and it
205 : simplifies memory management.
206 :
207 : Invariant: at every entry and exit to fd_fec_resolver_add_shred:
208 : - free_list has between partial_depth and partial_depth+depth
209 : elements.
210 : - complete_list has complete_depth elements
211 : (all these counts are inclusive). */
212 : ctx_list_t free_list[1];
213 : ctx_list_t complete_list[1];
214 :
215 : /* free_list_cnt: The number of items in free_list. */
216 : ulong free_list_cnt;
217 :
218 : /* done_pool: A pool (this time using fd_pool) of the done_ele_t
219 : elements that back done_map and done_heap. Invariant: each element
220 : is either (i) released and in the pool, or (ii) in both the
221 : done_map and done_heap. */
222 : done_ele_t * done_pool;
223 :
224 : /* done_map: A map (using fd_map_chain) mapping (slot, fec_idx) to an
225 : element of done_pool. Even in the presence of equivocation, a
226 : specific (slot, fec_idx) tuple occurs at most once in the map,
227 : and it's arbitrary which version is represented by sig_hash. In
228 : the presence of equivocation, the right shreds are probably being
229 : delivered using repair, which will bypass reading the sig_hash
230 : field, so it doesn't really matter. */
231 : done_map_t * done_map;
232 :
233 : /* done_heap: A min heap (using fd_heap) based on (slot, fec_idx) used
234 : to stop tracking done elements older than slot_old, and for
235 : eviction in the unlikely case that we run out of elements in the
236 : done_map. */
237 : done_heap_t done_heap[1];
238 :
239 : /* signer is used to sign shreds that require a retransmitter
240 : signature. sign_ctx is provided as the first argument to the
241 : function. */
242 : fd_fec_resolver_sign_fn * signer;
243 : void * sign_ctx;
244 :
245 : /* slot_old: slot_old is the lowest slot for which shreds will be
246 : accepted. That is any shred with slot<slot_old is rejected by
247 : add_shred with IGNORED. slot_old can only increase. */
248 : ulong slot_old;
249 :
250 : /* seed: done_map uses seed to compute a 32-bute hash of the FEC set's
251 : signature. */
252 : ulong seed;
253 :
254 : /* sha512 and reedsol are used for calculations while adding a shred.
255 : Their state outside a call to add_shred is indeterminate. */
256 : fd_sha512_t sha512[1];
257 : fd_reedsol_t reedsol[1];
258 :
259 : /* The footprint for the objects follows the struct and is in the same
260 : order as the pointers, namely:
261 : ctx_pool
262 : ctx_map
263 : done_pool
264 : done_map */
265 : };
266 :
267 : typedef struct fd_fec_resolver fd_fec_resolver_t;
268 :
269 : FD_FN_PURE ulong
270 : fd_fec_resolver_footprint( ulong depth,
271 : ulong partial_depth,
272 : ulong complete_depth,
273 3 : ulong done_depth ) {
274 3 : if( FD_UNLIKELY( (depth==0UL) | (partial_depth==0UL) | (complete_depth==0UL) | (done_depth==0UL) ) ) return 0UL;
275 3 : if( FD_UNLIKELY( (depth>UINT_MAX) | (partial_depth>UINT_MAX) | (complete_depth>UINT_MAX) ) ) return 0UL;
276 :
277 3 : ulong depth_sum = depth + partial_depth + complete_depth;
278 3 : if( FD_UNLIKELY( depth_sum>=UINT_MAX ) ) return 0UL;
279 :
280 3 : ulong ctx_chain_cnt = ctx_map_chain_cnt_est ( depth );
281 3 : ulong done_chain_cnt = done_map_chain_cnt_est( done_depth );
282 :
283 3 : ulong layout = FD_LAYOUT_INIT;
284 3 : layout = FD_LAYOUT_APPEND( layout, FD_FEC_RESOLVER_ALIGN, sizeof(fd_fec_resolver_t) );
285 3 : layout = FD_LAYOUT_APPEND( layout, alignof(set_ctx_t), sizeof(set_ctx_t)*depth_sum );
286 3 : layout = FD_LAYOUT_APPEND( layout, ctx_map_align(), ctx_map_footprint ( ctx_chain_cnt ) );
287 3 : layout = FD_LAYOUT_APPEND( layout, done_pool_align(), done_pool_footprint( done_depth ) );
288 3 : layout = FD_LAYOUT_APPEND( layout, done_map_align(), done_map_footprint ( done_chain_cnt ) );
289 :
290 3 : return FD_LAYOUT_FINI( layout, FD_FEC_RESOLVER_ALIGN );
291 3 : }
292 :
293 0 : FD_FN_CONST ulong fd_fec_resolver_align( void ) { return FD_FEC_RESOLVER_ALIGN; }
294 :
295 :
296 : void *
297 : fd_fec_resolver_new( void * shmem,
298 : fd_fec_resolver_sign_fn * signer,
299 : void * sign_ctx,
300 : ulong depth,
301 : ulong partial_depth,
302 : ulong complete_depth,
303 : ulong done_depth,
304 : fd_fec_set_t * sets,
305 33 : ulong seed ) {
306 33 : if( FD_UNLIKELY( (depth==0UL) | (partial_depth==0UL) | (complete_depth==0UL) | (done_depth==0UL) ) ) return NULL;
307 33 : if( FD_UNLIKELY( (depth>UINT_MAX) | (partial_depth>UINT_MAX) | (complete_depth>UINT_MAX) ) ) return NULL;
308 :
309 33 : ulong depth_sum = depth + partial_depth + complete_depth;
310 33 : if( FD_UNLIKELY( depth_sum>=UINT_MAX ) ) return NULL;
311 :
312 33 : ulong ctx_chain_cnt = ctx_map_chain_cnt_est ( depth );
313 33 : ulong done_chain_cnt = done_map_chain_cnt_est( done_depth );
314 :
315 : /* round( 2^64 * ... */
316 33 : ulong seed0 = fd_ulong_hash( seed + 7640891576956012809UL ); /* sqrt(2)-1 */
317 33 : ulong seed1 = fd_ulong_hash( seed + 13503953896175478587UL ); /* sqrt(3)-1 */
318 33 : ulong seed2 = fd_ulong_hash( seed + 4354685564936845356UL ); /* sqrt(5)-2 */
319 33 : ulong seed3 = fd_ulong_hash( seed + 11912009170470909682UL ); /* sqrt(7)-2 */
320 :
321 33 : FD_SCRATCH_ALLOC_INIT( l, shmem );
322 33 : void * self = FD_SCRATCH_ALLOC_APPEND( l, FD_FEC_RESOLVER_ALIGN, sizeof(fd_fec_resolver_t) );
323 33 : void * _ctx_pool = FD_SCRATCH_ALLOC_APPEND( l, alignof(set_ctx_t), sizeof(set_ctx_t)*depth_sum );
324 33 : void * _ctx_map = FD_SCRATCH_ALLOC_APPEND( l, ctx_map_align(), ctx_map_footprint ( ctx_chain_cnt ) );
325 33 : void * _done_pool = FD_SCRATCH_ALLOC_APPEND( l, done_pool_align(), done_pool_footprint( done_depth ) );
326 33 : void * _done_map = FD_SCRATCH_ALLOC_APPEND( l, done_map_align(), done_map_footprint ( done_chain_cnt ) );
327 33 : FD_SCRATCH_ALLOC_FINI( l, FD_FEC_RESOLVER_ALIGN );
328 :
329 33 : fd_fec_resolver_t * resolver = (fd_fec_resolver_t *)self;
330 33 : void * _ctx_treap = resolver->ctx_treap;
331 33 : void * _free_list = resolver->free_list;
332 33 : void * _complete_list = resolver->complete_list;
333 33 : void * _done_heap = resolver->done_heap;
334 :
335 33 : if( FD_UNLIKELY( !ctx_map_new ( _ctx_map, ctx_chain_cnt, seed0 ) ) ) { FD_LOG_WARNING(( "ctx_map_new fail" )); return NULL; }
336 33 : if( FD_UNLIKELY( !ctx_treap_new( _ctx_treap, depth_sum ) ) ) { FD_LOG_WARNING(( "ctx_treap_new fail" )); return NULL; }
337 33 : if( FD_UNLIKELY( !ctx_list_new ( _free_list ) ) ) { FD_LOG_WARNING(( "ctx_list_new fail" )); return NULL; }
338 33 : if( FD_UNLIKELY( !ctx_list_new ( _complete_list ) ) ) { FD_LOG_WARNING(( "ctx_list_new fail" )); return NULL; }
339 33 : if( FD_UNLIKELY( !done_pool_new( _done_pool, done_depth ) ) ) { FD_LOG_WARNING(( "done_pool_new fail" )); return NULL; }
340 33 : if( FD_UNLIKELY( !done_map_new ( _done_map, done_chain_cnt, seed1 ) ) ) { FD_LOG_WARNING(( "done_map_new fail" )); return NULL; }
341 33 : if( FD_UNLIKELY( !done_heap_new( _done_heap, done_depth ) ) ) { FD_LOG_WARNING(( "done_heap_new fail" )); return NULL; }
342 :
343 33 : set_ctx_t * ctx_pool = (set_ctx_t *)_ctx_pool;
344 33 : fd_memset( ctx_pool, '\0', sizeof(set_ctx_t)*depth_sum );
345 186 : for( ulong i=0UL; i<depth_sum; i++ ) ctx_pool[i].set = sets + i;
346 33 : ctx_treap_seed( ctx_pool, depth_sum, seed2 );
347 :
348 : /* Initialize all the lists */
349 33 : ctx_list_t * free_list = ctx_list_join( _free_list ); FD_TEST( free_list ==resolver->free_list );
350 33 : ctx_list_t * complete_list = ctx_list_join( _complete_list ); FD_TEST( complete_list==resolver->complete_list );
351 :
352 141 : for( ulong i=0UL; i<depth+partial_depth; i++ ) { ctx_list_idx_push_tail( free_list, i, ctx_pool ); }
353 78 : for( ulong i=depth+partial_depth; i<depth_sum; i++ ) { ctx_list_idx_push_tail( complete_list, i, ctx_pool ); }
354 33 : ctx_list_leave( complete_list );
355 33 : ctx_list_leave( free_list );
356 :
357 33 : fd_sha512_new( resolver->sha512 );
358 :
359 33 : resolver->depth = depth;
360 33 : resolver->partial_depth = partial_depth;
361 33 : resolver->complete_depth = complete_depth;
362 33 : resolver->done_depth = done_depth;
363 33 : resolver->expected_shred_version = 0;
364 33 : resolver->bypass_verify = 0;
365 33 : resolver->free_list_cnt = depth+partial_depth;
366 33 : resolver->signer = signer;
367 33 : resolver->sign_ctx = sign_ctx;
368 33 : resolver->slot_old = 0UL;
369 33 : resolver->seed = seed3;
370 33 : return shmem;
371 33 : }
372 :
373 : fd_fec_resolver_t *
374 33 : fd_fec_resolver_join( void * shmem ) {
375 33 : fd_fec_resolver_t * resolver = (fd_fec_resolver_t *)shmem;
376 33 : ulong depth = resolver->depth;
377 33 : ulong partial_depth = resolver->partial_depth;
378 33 : ulong complete_depth = resolver->complete_depth;
379 33 : ulong done_depth = resolver->done_depth;
380 :
381 33 : ulong depth_sum = depth + partial_depth + complete_depth;
382 33 : if( FD_UNLIKELY( depth_sum>=UINT_MAX ) ) return NULL;
383 :
384 33 : ulong ctx_chain_cnt = ctx_map_chain_cnt_est ( depth );
385 33 : ulong done_chain_cnt = done_map_chain_cnt_est( done_depth );
386 :
387 33 : FD_SCRATCH_ALLOC_INIT( l, shmem );
388 33 : /* self */ FD_SCRATCH_ALLOC_APPEND( l, FD_FEC_RESOLVER_ALIGN, sizeof(fd_fec_resolver_t) );
389 33 : void * _ctx_pool = FD_SCRATCH_ALLOC_APPEND( l, alignof(set_ctx_t), sizeof(set_ctx_t)*depth_sum );
390 33 : void * _ctx_map = FD_SCRATCH_ALLOC_APPEND( l, ctx_map_align(), ctx_map_footprint ( ctx_chain_cnt ) );
391 33 : void * _done_pool = FD_SCRATCH_ALLOC_APPEND( l, done_pool_align(), done_pool_footprint( done_depth ) );
392 33 : void * _done_map = FD_SCRATCH_ALLOC_APPEND( l, done_map_align(), done_map_footprint ( done_chain_cnt ) );
393 33 : FD_SCRATCH_ALLOC_FINI( l, FD_FEC_RESOLVER_ALIGN );
394 :
395 33 : resolver->ctx_pool = (set_ctx_t *)_ctx_pool;
396 33 : resolver->ctx_map = ctx_map_join ( _ctx_map ); if( FD_UNLIKELY( !resolver->ctx_map ) ) return NULL;
397 33 : resolver->done_pool = done_pool_join( _done_pool ); if( FD_UNLIKELY( !resolver->done_pool ) ) return NULL;
398 33 : resolver->done_map = done_map_join ( _done_map ); if( FD_UNLIKELY( !resolver->done_map ) ) return NULL;
399 33 : if( FD_UNLIKELY( ctx_treap_join( resolver->ctx_treap )!= resolver->ctx_treap ) ) return NULL;
400 33 : if( FD_UNLIKELY( ctx_list_join ( resolver->free_list )!= resolver->free_list ) ) return NULL;
401 33 : if( FD_UNLIKELY( ctx_list_join ( resolver->complete_list )!= resolver->complete_list ) ) return NULL;
402 33 : if( FD_UNLIKELY( done_heap_join( resolver->done_heap )!= resolver->done_heap ) ) return NULL;
403 33 : if( FD_UNLIKELY( fd_sha512_join( resolver->sha512 )!= resolver->sha512 ) ) return NULL;
404 :
405 33 : return resolver;
406 33 : }
407 :
408 : void
409 : fd_fec_resolver_set_shred_version( fd_fec_resolver_t * resolver,
410 33 : ushort expected_shred_version ) {
411 33 : resolver->expected_shred_version = expected_shred_version;
412 33 : }
413 :
414 : void
415 : fd_fec_resolver_set_bypass_verify( fd_fec_resolver_t * resolver,
416 0 : int bypass_verify ) {
417 0 : resolver->bypass_verify = (uchar)!!bypass_verify;
418 0 : }
419 :
420 : void
421 : fd_fec_resolver_advance_slot_old( fd_fec_resolver_t * resolver,
422 3 : ulong slot_old ) {
423 3 : if( FD_UNLIKELY( slot_old <= resolver->slot_old ) ) return;
424 3 : resolver->slot_old = slot_old;
425 :
426 : /* Remove from done map */
427 3 : done_heap_t * done_heap = resolver->done_heap;
428 3 : done_map_t * done_map = resolver->done_map;
429 3 : done_ele_t * done_pool = resolver->done_pool;
430 :
431 6 : while( done_heap_ele_cnt( done_heap ) ) {
432 3 : done_ele_t * min_ele = done_heap_ele_peek_min( done_heap, done_pool );
433 3 : if( FD_UNLIKELY( min_ele->key.slot>=slot_old ) ) break;
434 3 : done_map_ele_remove_fast( done_map, min_ele, done_pool );
435 3 : done_heap_idx_remove_min( done_heap, done_pool );
436 3 : done_pool_ele_release ( done_pool, min_ele );
437 3 : }
438 :
439 : /* Remove from in progress map */
440 3 : ctx_map_t * ctx_map = resolver->ctx_map;
441 3 : ctx_treap_t * ctx_treap = resolver->ctx_treap;
442 3 : set_ctx_t * ctx_pool = resolver->ctx_pool;
443 3 : ctx_list_t * free_list = resolver->free_list;
444 :
445 3 : ctx_treap_fwd_iter_t next;
446 6 : for( ctx_treap_fwd_iter_t iter=ctx_treap_fwd_iter_init( ctx_treap, ctx_pool ); !ctx_treap_fwd_iter_done( iter ); iter=next ) {
447 3 : next = ctx_treap_fwd_iter_next( iter, ctx_pool );
448 3 : set_ctx_t * min_ele = ctx_treap_fwd_iter_ele( iter, ctx_pool );
449 3 : if( FD_UNLIKELY( min_ele->slot>=slot_old ) ) break;
450 :
451 3 : ctx_treap_ele_remove ( ctx_treap, min_ele, ctx_pool );
452 3 : ctx_map_ele_remove_fast( ctx_map, min_ele, ctx_pool );
453 3 : ctx_list_ele_push_head ( free_list, min_ele, ctx_pool );
454 3 : resolver->free_list_cnt++;
455 3 : }
456 3 : }
457 :
458 : static inline void
459 : ensure_done_pool_free( done_ele_t * done_pool,
460 : done_heap_t * done_heap,
461 219 : done_map_t * done_map ) {
462 219 : if( FD_UNLIKELY( !done_pool_free( done_pool ) ) ) {
463 : /* Done map is full, so we'll forget about the oldest slot */
464 138 : ulong worst_idx = done_heap_idx_peek_min( done_heap );
465 138 : FD_TEST( worst_idx!=done_heap_idx_null() ); /* Done pool can't be empty and full at the same time */
466 138 : done_heap_idx_remove_min( done_heap, done_pool );
467 138 : done_map_idx_remove_fast( done_map, worst_idx, done_pool );
468 138 : done_pool_idx_release( done_pool, worst_idx );
469 : /* Now it's not empty */
470 138 : }
471 219 : }
472 :
473 :
474 : int
475 : fd_fec_resolver_add_shred( fd_fec_resolver_t * resolver,
476 : fd_shred_t const * shred,
477 : ulong shred_sz,
478 : ulong max_shred_idx,
479 : uint source,
480 : uchar const * leader_pubkey,
481 : fd_fec_set_t const * * out_fec_set,
482 : fd_shred_t const * * out_shred,
483 : fd_bmtree_node_t * out_merkle_root,
484 8448 : fd_fec_resolver_spilled_t * out_spilled ) {
485 8448 : FD_TEST( source<=FD_FEC_RESOLVER_SHRED_SRC_BAD_REPAIR );
486 8448 : int is_repair = source==FD_FEC_RESOLVER_SHRED_SRC_REPAIR;
487 :
488 : /* Unpack variables */
489 8448 : ulong partial_depth = resolver->partial_depth;
490 :
491 8448 : ctx_list_t * free_list = resolver->free_list;
492 8448 : ctx_list_t * complete_list = resolver->complete_list;
493 8448 : ctx_map_t * ctx_map = resolver->ctx_map;
494 8448 : ctx_treap_t * ctx_treap = resolver->ctx_treap;
495 8448 : set_ctx_t * ctx_pool = resolver->ctx_pool;
496 8448 : done_map_t * done_map = resolver->done_map;
497 8448 : done_ele_t * done_pool = resolver->done_pool;
498 8448 : done_heap_t * done_heap = resolver->done_heap;
499 :
500 8448 : fd_reedsol_t * reedsol = resolver->reedsol;
501 8448 : fd_sha512_t * sha512 = resolver->sha512;
502 :
503 : /* Invariants:
504 : * each set_ctx_t is in exactly one of ctx_map, freelist, or
505 : complete_list */
506 :
507 : /* Is this shred for a slot we've already rooted or otherwise don't
508 : care about? */
509 8448 : if( FD_UNLIKELY( shred->slot<resolver->slot_old ) ) return FD_FEC_RESOLVER_SHRED_IGNORED;
510 :
511 : /* Do a bunch of quick validity checks */
512 8346 : if( FD_UNLIKELY( shred->version!=resolver->expected_shred_version ) ) return FD_FEC_RESOLVER_SHRED_REJECTED;
513 8319 : if( FD_UNLIKELY( shred_sz<fd_shred_sz( shred ) ) ) return FD_FEC_RESOLVER_SHRED_REJECTED;
514 8319 : if( FD_UNLIKELY( shred->idx>=max_shred_idx ) ) return FD_FEC_RESOLVER_SHRED_REJECTED;
515 8319 : if( FD_UNLIKELY( shred->fec_set_idx>max_shred_idx-FD_FEC_SHRED_CNT ) ) return FD_FEC_RESOLVER_SHRED_REJECTED;
516 8319 : if( FD_UNLIKELY( shred->idx-shred->fec_set_idx>=FD_FEC_SHRED_CNT ) ) return FD_FEC_RESOLVER_SHRED_REJECTED;
517 8319 : if( FD_UNLIKELY( shred->fec_set_idx%FD_FEC_SHRED_CNT!=0UL ) ) return FD_FEC_RESOLVER_SHRED_REJECTED;
518 :
519 8226 : uchar variant = shred->variant;
520 8226 : uchar shred_type = fd_shred_type( variant );
521 :
522 8226 : int is_data_shred = fd_shred_is_data( shred_type );
523 :
524 8226 : if( !is_data_shred ) { /* Roughly 50/50 branch */
525 4350 : if( FD_UNLIKELY( (shred->code.data_cnt!=FD_FEC_SHRED_CNT) | (shred->code.code_cnt!=FD_FEC_SHRED_CNT) ) )
526 3 : return FD_FEC_RESOLVER_SHRED_REJECTED;
527 4347 : if( FD_UNLIKELY( shred->code.idx>=FD_FEC_SHRED_CNT ) ) return FD_FEC_RESOLVER_SHRED_REJECTED;
528 4347 : if( FD_UNLIKELY( shred->code.idx!=shred->idx%FD_FEC_SHRED_CNT ) ) return FD_FEC_RESOLVER_SHRED_REJECTED;
529 4347 : } else {
530 : /* if the shred's parent is for a slot we've already pruned, ignore it. */
531 3876 : if( FD_UNLIKELY( shred->slot-shred->data.parent_off<resolver->slot_old ) ) return FD_FEC_RESOLVER_SHRED_IGNORED;
532 :
533 : /* if it has slot complete, it must be the last one in the FEC. */
534 3876 : if( FD_UNLIKELY( (shred->data.flags & FD_SHRED_DATA_FLAG_SLOT_COMPLETE) && ((1UL+shred->idx) % FD_FEC_SHRED_CNT) ) ) {
535 0 : return FD_FEC_RESOLVER_SHRED_REJECTED;
536 0 : }
537 :
538 : /* if it has data complete, it must be the last data shred in the FEC set
539 : https://github.com/anza-xyz/agave/blob/v4.3.0-beta.0/ledger/src/shred/filter.rs#L346-L354 */
540 3876 : if( FD_UNLIKELY( ( shred->data.flags & FD_SHRED_DATA_FLAG_DATA_COMPLETE ) &&
541 3876 : ( shred->idx != ( shred->fec_set_idx + ( FD_FEC_SHRED_CNT - 1UL ) ) ) ) ) {
542 0 : return FD_FEC_RESOLVER_SHRED_REJECTED;
543 0 : }
544 3876 : }
545 :
546 8223 : if( FD_UNLIKELY( (shred_type==FD_SHRED_TYPE_LEGACY_DATA) | (shred_type==FD_SHRED_TYPE_LEGACY_CODE) ) ) {
547 : /* Reject any legacy shreds */
548 0 : return FD_FEC_RESOLVER_SHRED_REJECTED;
549 0 : }
550 :
551 :
552 8223 : wrapped_sig_t const * w_sig = (wrapped_sig_t const *)shred->signature;
553 :
554 : /* Is this FEC set in progress? */
555 8223 : set_ctx_t * ctx = ctx_map_ele_query( ctx_map, w_sig, NULL, ctx_pool );
556 :
557 : /* If we detect a different signature for the same (slot, FEC set
558 : idx), it means either the shred is invalid, or the leader is
559 : equivocating. We can't tell which without verifying the shred
560 : though. */
561 8223 : int equivoc_or_invalid = 0;
562 :
563 : /* If it's not in progress and it's repair, we will allocate a context
564 : for it, assuming all the other checks pass. If it's from Turbine,
565 : we'll be a little more skeptical about it: if we've already seen a
566 : FEC set for that same (slot, FEC set idx) pair, then we won't take
567 : it, either rejecting it here, or setting equivoc_or_invalid to
568 : reject it later. */
569 8223 : if( FD_UNLIKELY( (ctx==NULL) & (!is_repair) ) ) {
570 : /* Most likely, it's just done. */
571 789 : slot_fec_pair_t slot_fec_pair[1] = {{ .slot = shred->slot, .fec_idx = shred->fec_set_idx }};
572 789 : done_ele_t * done_ele = done_map_ele_query( done_map, slot_fec_pair, NULL, done_pool );
573 789 : if( FD_LIKELY( done_ele ) ) {
574 552 : ulong sig_hash = fd_hash( resolver->seed, w_sig, sizeof(wrapped_sig_t) );
575 : /* It's possible (with probability 2^-32, about 1/year at current
576 : rates) for fd_hash to return SIG_HASH_EQUIVOC. In this case,
577 : we may miss an equivocation and just always return
578 : SHRED_IGNORED for subsequent Turbine shreds for that FEC set.
579 : Because the hash is validator specific, it just means we'll
580 : rely on another node to produce the equivocation proof, and
581 : we'll act as if we hadn't seen the equivocating shreds. */
582 552 : if( FD_LIKELY( ((uint)sig_hash==done_ele->sig_hash) | (done_ele->sig_hash==SIG_HASH_EQUIVOC) ) ) return FD_FEC_RESOLVER_SHRED_IGNORED;
583 0 : equivoc_or_invalid = 1;
584 0 : }
585 :
586 : /* If it's not done, then check for the unlikely case we have it
587 : in progress with a different signature. */
588 237 : if( FD_UNLIKELY( ctx_treap_ele_query_const( ctx_treap, slot_fec_pair, ctx_pool ) ) ) equivoc_or_invalid = 1;
589 237 : }
590 :
591 : /* If we've made it here, then we'll keep this shred as long as
592 : it is valid. */
593 :
594 7671 : fd_bmtree_node_t leaf[1];
595 :
596 : /* For the purposes of the shred header, tree_depth means the number
597 : of nodes, counting the leaf but excluding the root. For bmtree,
598 : depth means the number of layers, which counts both. */
599 7671 : ulong tree_depth = fd_shred_merkle_cnt( variant ); /* In [0, 15] */
600 7671 : ulong reedsol_protected_sz = 1115UL + FD_SHRED_DATA_HEADER_SZ - FD_SHRED_SIGNATURE_SZ - FD_SHRED_MERKLE_NODE_SZ*tree_depth
601 7671 : - FD_SHRED_MERKLE_ROOT_SZ*fd_shred_is_chained ( shred_type )
602 7671 : - FD_SHRED_SIGNATURE_SZ *fd_shred_is_resigned( shred_type); /* In [743, 1139] conservatively*/
603 7671 : ulong data_merkle_protected_sz = reedsol_protected_sz + FD_SHRED_MERKLE_ROOT_SZ*fd_shred_is_chained( shred_type );
604 7671 : ulong parity_merkle_protected_sz = reedsol_protected_sz + FD_SHRED_MERKLE_ROOT_SZ*fd_shred_is_chained( shred_type )
605 7671 : + FD_SHRED_CODE_HEADER_SZ - FD_ED25519_SIG_SZ;
606 7671 : ulong merkle_protected_sz = fd_ulong_if( is_data_shred, data_merkle_protected_sz, parity_merkle_protected_sz );
607 :
608 7671 : fd_bmtree_hash_leaf( leaf, (uchar const *)shred + sizeof(fd_ed25519_sig_t), merkle_protected_sz, FD_BMTREE_LONG_PREFIX_SZ );
609 :
610 : /* in_type_idx is between [0, code.data_cnt) or [0, code.code_cnt),
611 : where data_cnt <= FD_FEC_SHRED_CNT and code_cnt <= FD_FEC_SHRED_CNT
612 : On the other hand, shred_idx, goes from [0, code.data_cnt +
613 : code.code_cnt), with all the data shreds having
614 : shred_idx < code.data_cnt and all the parity shreds having
615 : shred_idx >= code.data_cnt. */
616 7671 : ulong in_type_idx = fd_ulong_if( is_data_shred, shred->idx - shred->fec_set_idx, shred->code.idx );
617 7671 : ulong shred_idx = fd_ulong_if( is_data_shred, in_type_idx, in_type_idx + shred->code.data_cnt );
618 :
619 7671 : if( FD_UNLIKELY( ( shred->fec_set_idx % FD_FEC_SHRED_CNT ) != 0UL ) ) return FD_FEC_RESOLVER_SHRED_REJECTED;
620 7671 : if( FD_UNLIKELY( in_type_idx >= FD_FEC_SHRED_CNT ) ) return FD_FEC_RESOLVER_SHRED_REJECTED;
621 :
622 : /* This, combined with the check on shred->code.data_cnt implies that
623 : shred_idx is in [0, 2*FD_FEC_SHRED_CNT). */
624 :
625 7671 : if( FD_UNLIKELY( tree_depth!=FD_SHRED_MERKLE_LAYER_CNT-1UL ) ) return FD_FEC_RESOLVER_SHRED_REJECTED;
626 :
627 7671 : if( FD_UNLIKELY( !ctx ) ) { /* This is the first shred in the FEC set */
628 :
629 264 : if( FD_UNLIKELY( resolver->free_list_cnt<=partial_depth ) ) {
630 : /* Packet loss is really high and we have a lot of in-progress FEC
631 : sets that we haven't been able to finish. Evict the context
632 : with the highest (slot, FEC idx). This is the one that is the
633 : farthest away from what we're currently replaying, which means
634 : we have the longest time to request it via repair if we
635 : actually need it. This also handles the case where a leader
636 : sends some shreds from their slots that are far in the future
637 : in this epoch. */
638 30 : set_ctx_t * victim_ctx = ctx_treap_rev_iter_ele( ctx_treap_rev_iter_init( ctx_treap, ctx_pool ), ctx_pool );
639 :
640 30 : if( FD_LIKELY( out_spilled ) ) {
641 6 : out_spilled->slot = victim_ctx->slot;
642 6 : out_spilled->fec_set_idx = victim_ctx->fec_set_idx;
643 6 : *out_spilled->merkle_root = victim_ctx->root;
644 6 : }
645 :
646 : /* Remove from treap and map, then add to free_list */
647 30 : ctx_treap_ele_remove ( ctx_treap, victim_ctx, ctx_pool );
648 30 : ctx_map_ele_remove_fast( ctx_map, victim_ctx, ctx_pool );
649 :
650 30 : ctx_list_ele_push_tail ( free_list, victim_ctx, ctx_pool );
651 30 : resolver->free_list_cnt++;
652 :
653 30 : FD_MCNT_INC( SHRED, FEC_SPILLED, 1UL );
654 30 : }
655 : /* Now we know |free_list|>partial_depth */
656 :
657 264 : ctx = ctx_list_ele_pop_head( free_list, ctx_pool );
658 264 : resolver->free_list_cnt--;
659 :
660 : /* Now we need to derive the root of the Merkle tree and verify the
661 : signature to prevent a DOS attack just by sending lots of invalid
662 : shreds. */
663 264 : fd_bmtree_commit_t * tree;
664 264 : tree = fd_bmtree_commit_init( ctx->_footprint, FD_SHRED_MERKLE_NODE_SZ, FD_BMTREE_LONG_PREFIX_SZ, FD_SHRED_MERKLE_LAYER_CNT );
665 264 : FD_TEST( tree==ctx->tree );
666 :
667 264 : fd_bmtree_node_t _root[1] = {0};
668 264 : if( FD_LIKELY( !resolver->bypass_verify ) ) {
669 264 : fd_shred_merkle_t const * proof = fd_shred_merkle_nodes( shred );
670 264 : int rv = fd_bmtree_commitp_insert_with_proof( tree, shred_idx, leaf, (uchar const *)proof, tree_depth, _root );
671 264 : if( FD_UNLIKELY( !rv ) ) {
672 0 : ctx_list_ele_push_head( free_list, ctx, ctx_pool );
673 0 : resolver->free_list_cnt++;
674 0 : FD_MCNT_INC( SHRED, SHRED_INITIAL_REJECTED, 1UL );
675 0 : return FD_FEC_RESOLVER_SHRED_REJECTED;
676 0 : }
677 :
678 264 : if( FD_UNLIKELY( FD_ED25519_SUCCESS != fd_ed25519_verify( _root->hash, 32UL, shred->signature, leader_pubkey, sha512 ) ) ) {
679 0 : ctx_list_ele_push_head( free_list, ctx, ctx_pool );
680 0 : resolver->free_list_cnt++;
681 0 : FD_MCNT_INC( SHRED, SHRED_INITIAL_REJECTED, 1UL );
682 0 : return FD_FEC_RESOLVER_SHRED_REJECTED;
683 0 : }
684 264 : }
685 :
686 : /* Copy the merkle root into the output arg. */
687 264 : if( FD_LIKELY( out_merkle_root ) ) memcpy( out_merkle_root, _root, sizeof(fd_bmtree_node_t) );
688 :
689 264 : if( FD_UNLIKELY( equivoc_or_invalid ) ) {
690 : /* It wasn't invalid, so it must be equivoc */
691 0 : ctx_list_ele_push_head( free_list, ctx, ctx_pool );
692 0 : resolver->free_list_cnt++;
693 : /* We want to record that we've sigverified the shred somewhere so
694 : that if an attacker sends it to us again, we don't have to
695 : verify it again. We do that by inserting it into the done_map
696 : with SIG_HASH_EQUIVOC. */
697 0 : slot_fec_pair_t slot_fec_pair[1] = {{ .slot = shred->slot, .fec_idx = shred->fec_set_idx }};
698 0 : done_ele_t * done = done_map_ele_query( done_map, slot_fec_pair, NULL, done_pool );
699 0 : if( FD_LIKELY( done ) ) done->sig_hash = SIG_HASH_EQUIVOC;
700 0 : else {
701 0 : ensure_done_pool_free( done_pool, done_heap, done_map );
702 :
703 0 : done = done_pool_ele_acquire( done_pool );
704 :
705 0 : done->key.slot = shred->slot;
706 0 : done->key.fec_idx = shred->fec_set_idx;
707 0 : done->sig_hash = SIG_HASH_EQUIVOC;
708 :
709 0 : done_heap_ele_insert( done_heap, done, done_pool );
710 0 : done_map_ele_insert ( done_map, done, done_pool );
711 0 : }
712 :
713 0 : return FD_FEC_RESOLVER_SHRED_EQUIVOC;
714 0 : }
715 :
716 : /* This seems like a legitimate FEC set, so we populate the rest of
717 : the fields, then add it to the map and treap. */
718 264 : ctx->sig = *w_sig;
719 264 : ctx->slot = shred->slot;
720 264 : ctx->fec_set_idx = shred->fec_set_idx;
721 264 : ctx->data_variant = fd_uchar_if( is_data_shred, variant, fd_shred_variant( fd_shred_swap_type( shred_type ), (uchar)tree_depth ) );
722 264 : ctx->parity_variant = fd_uchar_if( !is_data_shred, variant, fd_shred_variant( fd_shred_swap_type( shred_type ), (uchar)tree_depth ) );
723 264 : ctx->total_rx_shred_cnt = 0UL;
724 264 : ctx->root = *_root;
725 :
726 264 : if( FD_UNLIKELY( fd_shred_is_resigned( shred_type ) & !!(resolver->signer) ) ) {
727 3 : resolver->signer( resolver->sign_ctx, ctx->retransmitter_sig.u, _root->hash );
728 261 : } else {
729 261 : fd_memset( ctx->retransmitter_sig.u, 0, 64UL );
730 261 : }
731 :
732 : /* Reset the FEC set */
733 264 : ctx->set->data_shred_rcvd = 0U;
734 264 : ctx->set->parity_shred_rcvd = 0U;
735 264 : ctx->set->turbine_shred_rcvd = 0UL;
736 264 : ctx->set->repair_shred_rcvd = 0UL;
737 :
738 264 : ctx_map_ele_insert ( ctx_map, ctx, ctx_pool );
739 264 : ctx_treap_ele_insert( ctx_treap, ctx, ctx_pool );
740 :
741 7407 : } else {
742 : /* This is not the first shred in the set */
743 :
744 : /* Verify that the shred's slot and fec_set_idx match the context
745 : established by the first shred. */
746 7407 : if( FD_UNLIKELY( shred->slot!=ctx->slot || shred->fec_set_idx!=ctx->fec_set_idx ) ) {
747 0 : return FD_FEC_RESOLVER_SHRED_REJECTED;
748 0 : }
749 :
750 : /* First ensure that all the shreds in the FEC set have consistent
751 : variants. They all must have the same tree_depth and the same
752 : chained/not chained, resigned/not resigned bits. */
753 7407 : if( FD_UNLIKELY( variant!=fd_uchar_if( is_data_shred, ctx->data_variant, ctx->parity_variant ) ) ) {
754 0 : return FD_FEC_RESOLVER_SHRED_REJECTED;
755 0 : }
756 :
757 7407 : if( FD_UNLIKELY( resolver->bypass_verify ) ) {
758 0 : if( FD_LIKELY( out_merkle_root ) ) *out_merkle_root = ctx->root;
759 7407 : } else {
760 7407 : fd_shred_merkle_t const * proof = fd_shred_merkle_nodes( shred );
761 7407 : int rv = fd_bmtree_commitp_insert_with_proof( ctx->tree, shred_idx, leaf, (uchar const *)proof, tree_depth, out_merkle_root );
762 7407 : if( !rv ) return FD_FEC_RESOLVER_SHRED_REJECTED;
763 7407 : }
764 :
765 : /* Check to make sure this is not a duplicate */
766 7398 : int shred_dup = !!(fd_uint_if( is_data_shred, ctx->set->data_shred_rcvd, ctx->set->parity_shred_rcvd ) & (1U << in_type_idx));
767 7398 : if( FD_UNLIKELY( shred_dup ) ) {
768 249 : *out_shred = is_data_shred ? ctx->set->data_shreds[ in_type_idx ].s : ctx->set->parity_shreds[ in_type_idx ].s;
769 249 : return FD_FEC_RESOLVER_SHRED_DUPLICATE;
770 249 : }
771 7398 : }
772 :
773 : /* At this point, the shred has passed Merkle validation and is new.
774 : We also know that ctx is a pointer to the set_ctx_t where this
775 : shred belongs. */
776 :
777 : /* Copy the shred to memory the FEC resolver owns */
778 7413 : uchar * dst = is_data_shred ? ctx->set->data_shreds[ in_type_idx ].b : ctx->set->parity_shreds[ in_type_idx ].b;
779 7413 : fd_memcpy( dst, shred, fd_shred_sz( shred ) );
780 :
781 : /* If the shred needs a retransmitter signature, set it */
782 7413 : if( FD_UNLIKELY( fd_shred_is_resigned( shred_type ) ) ) {
783 672 : memcpy( dst + fd_shred_retransmitter_sig_off( (fd_shred_t *)dst ), ctx->retransmitter_sig.u, 64UL );
784 672 : }
785 :
786 7413 : ctx->set->data_shred_rcvd |= (uint)(!!is_data_shred)<<in_type_idx;
787 7413 : ctx->set->parity_shred_rcvd |= (uint)( !is_data_shred)<<in_type_idx;
788 7413 : ulong shred_bit = 1UL<<shred_idx;
789 7413 : if( source==FD_FEC_RESOLVER_SHRED_SRC_TURBINE ) ctx->set->turbine_shred_rcvd |= shred_bit;
790 555 : else ctx->set->repair_shred_rcvd |= shred_bit;
791 7413 : ctx->total_rx_shred_cnt++;
792 :
793 7413 : *out_shred = (fd_shred_t const *)dst;
794 :
795 : /* Do we have enough to begin reconstruction? */
796 7413 : if( FD_LIKELY( ctx->total_rx_shred_cnt < FD_FEC_SHRED_CNT ) ) return FD_FEC_RESOLVER_SHRED_OKAY;
797 :
798 : /* At this point, the FEC set is either valid or permanently invalid,
799 : so we can consider it done either way. */
800 :
801 219 : done_ele_t * done = NULL;
802 219 : ensure_done_pool_free( done_pool, done_heap, done_map );
803 :
804 : /* If it's already in the done map, we don't need to re-insert it.
805 : It's not very clear what we should do if the sig_hashes differ, but
806 : this can only happen the second insert was a repair shred, and in
807 : that case, it gets bypassed anyway, so it doesn't really matter.
808 : We'll just keep the existing value in that case. */
809 219 : slot_fec_pair_t done_key[1] = {{ .slot = ctx->slot, .fec_idx = ctx->fec_set_idx }};
810 219 : if( FD_LIKELY( !done_map_ele_query( done_map, done_key, NULL, done_pool ) ) ) {
811 219 : done = done_pool_ele_acquire( done_pool );
812 :
813 219 : done->key.slot = ctx->slot;
814 219 : done->key.fec_idx = ctx->fec_set_idx;
815 219 : done->sig_hash = (uint)fd_hash( resolver->seed, w_sig, sizeof(wrapped_sig_t) );
816 :
817 219 : done_heap_ele_insert( done_heap, done, done_pool );
818 219 : done_map_ele_insert ( done_map, done, done_pool );
819 219 : }
820 :
821 :
822 219 : ctx_map_ele_remove_fast( ctx_map, ctx, ctx_pool );
823 219 : ctx_treap_ele_remove ( ctx_treap, ctx, ctx_pool );
824 : /* At this point, ctx is not in any of the data structures, so we need
825 : to be sure to add it to one of the lists before exiting. */
826 :
827 219 : fd_fec_set_t * set = ctx->set;
828 219 : fd_bmtree_commit_t * tree = ctx->tree;
829 :
830 219 : reedsol = fd_reedsol_recover_init( (void*)reedsol, reedsol_protected_sz );
831 7227 : for( ulong i=0UL; i<FD_FEC_SHRED_CNT; i++ ) {
832 7008 : uchar * rs_payload = set->data_shreds[ i ].b + sizeof(fd_ed25519_sig_t);
833 7008 : if( set->data_shred_rcvd&(1U<<i) ) fd_reedsol_recover_add_rcvd_shred ( reedsol, 1, rs_payload );
834 3615 : else fd_reedsol_recover_add_erased_shred( reedsol, 1, rs_payload );
835 7008 : }
836 7227 : for( ulong i=0UL; i<FD_FEC_SHRED_CNT; i++ ) {
837 7008 : uchar * rs_payload = set->parity_shreds[ i ].b + FD_SHRED_CODE_HEADER_SZ;
838 7008 : if( set->parity_shred_rcvd&(1U<<i) ) fd_reedsol_recover_add_rcvd_shred ( reedsol, 0, rs_payload );
839 3393 : else fd_reedsol_recover_add_erased_shred( reedsol, 0, rs_payload );
840 7008 : }
841 :
842 219 : if( FD_UNLIKELY( FD_REEDSOL_SUCCESS != fd_reedsol_recover_fini( reedsol ) ) ) {
843 : /* A few lines up, we already checked to make sure it wasn't the
844 : insufficient case, so it must be the inconsistent case. That
845 : means the leader signed a shred with invalid Reed-Solomon FEC
846 : set. This shouldn't happen in practice, but we need to handle it
847 : for the malicious leader case. This should probably be a
848 : slash-able offense. */
849 0 : ctx_list_ele_push_tail( free_list, ctx, ctx_pool );
850 0 : resolver->free_list_cnt++;
851 0 : FD_MCNT_INC( SHRED, FEC_FATAL_REJECTED, 1UL );
852 0 : return FD_FEC_RESOLVER_SHRED_REJECTED;
853 0 : }
854 :
855 219 : uchar const * chained_root = fd_ptr_if( fd_shred_is_chained( shred_type ), (uchar *)shred+fd_shred_chain_off( variant ), NULL );
856 :
857 : /* Iterate over recovered shreds, add them to the Merkle tree,
858 : populate headers and signatures. */
859 7227 : for( ulong i=0UL; i<FD_FEC_SHRED_CNT; i++ ) {
860 7008 : if( !(set->data_shred_rcvd&(1U<<i)) ) {
861 3615 : fd_memcpy( set->data_shreds[i].b, shred, sizeof(fd_ed25519_sig_t) );
862 3615 : if( FD_LIKELY( fd_shred_is_chained( shred_type ) ) ) {
863 3615 : fd_memcpy( set->data_shreds[i].b+fd_shred_chain_off( ctx->data_variant ), chained_root, FD_SHRED_MERKLE_ROOT_SZ );
864 3615 : }
865 3615 : if( FD_LIKELY( !resolver->bypass_verify ) ) {
866 3615 : fd_bmtree_hash_leaf( leaf, set->data_shreds[i].b+sizeof(fd_ed25519_sig_t), data_merkle_protected_sz, FD_BMTREE_LONG_PREFIX_SZ );
867 3615 : if( FD_UNLIKELY( !fd_bmtree_commitp_insert_with_proof( tree, i, leaf, NULL, 0, NULL ) ) ) {
868 0 : ctx_list_ele_push_tail( free_list, ctx, ctx_pool );
869 0 : resolver->free_list_cnt++;
870 0 : FD_MCNT_INC( SHRED, FEC_FATAL_REJECTED, 1UL );
871 0 : return FD_FEC_RESOLVER_SHRED_REJECTED;
872 0 : }
873 3615 : }
874 3615 : }
875 7008 : }
876 :
877 7227 : for( ulong i=0UL; i<FD_FEC_SHRED_CNT; i++ ) {
878 7008 : if( !(set->parity_shred_rcvd&(1U<<i)) ) {
879 3393 : fd_shred_t * p_shred = set->parity_shreds[i].s; /* We can't parse because we haven't populated the header */
880 3393 : fd_memcpy( p_shred->signature, shred->signature, sizeof(fd_ed25519_sig_t) );
881 3393 : p_shred->variant = ctx->parity_variant;
882 3393 : p_shred->slot = shred->slot;
883 3393 : p_shred->idx = (uint)(i + ctx->fec_set_idx);
884 3393 : p_shred->version = shred->version;
885 3393 : p_shred->fec_set_idx = (uint)ctx->fec_set_idx;
886 3393 : p_shred->code.data_cnt = (ushort)FD_FEC_SHRED_CNT;
887 3393 : p_shred->code.code_cnt = (ushort)FD_FEC_SHRED_CNT;
888 3393 : p_shred->code.idx = (ushort)i;
889 :
890 3393 : if( FD_LIKELY( fd_shred_is_chained( shred_type ) ) ) {
891 3393 : fd_memcpy( set->parity_shreds[i].b+fd_shred_chain_off( ctx->parity_variant ), chained_root, FD_SHRED_MERKLE_ROOT_SZ );
892 3393 : }
893 :
894 3393 : if( FD_LIKELY( !resolver->bypass_verify ) ) {
895 3393 : fd_bmtree_hash_leaf( leaf, set->parity_shreds[i].b+sizeof(fd_ed25519_sig_t), parity_merkle_protected_sz, FD_BMTREE_LONG_PREFIX_SZ );
896 3393 : if( FD_UNLIKELY( !fd_bmtree_commitp_insert_with_proof( tree, FD_FEC_SHRED_CNT + i, leaf, NULL, 0, NULL ) ) ) {
897 0 : ctx_list_ele_push_tail( free_list, ctx, ctx_pool );
898 0 : resolver->free_list_cnt++;
899 0 : FD_MCNT_INC( SHRED, FEC_FATAL_REJECTED, 1UL );
900 0 : return FD_FEC_RESOLVER_SHRED_REJECTED;
901 0 : }
902 3393 : }
903 3393 : }
904 7008 : }
905 :
906 : /* Check that the whole Merkle tree is consistent. */
907 219 : if( FD_UNLIKELY( !resolver->bypass_verify && !fd_bmtree_commitp_fini( tree, FD_FEC_SHRED_CNT + FD_FEC_SHRED_CNT ) ) ) {
908 0 : ctx_list_ele_push_tail( free_list, ctx, ctx_pool );
909 0 : resolver->free_list_cnt++;
910 0 : FD_MCNT_INC( SHRED, FEC_FATAL_REJECTED, 1UL );
911 0 : return FD_FEC_RESOLVER_SHRED_REJECTED;
912 0 : }
913 :
914 : /* Check that all the fields that are supposed to be consistent across
915 : an FEC set actually are. */
916 219 : fd_shred_t const * base_data_shred = fd_shred_parse( set->data_shreds [ 0 ].b, FD_SHRED_MIN_SZ, max_shred_idx );
917 219 : fd_shred_t const * base_parity_shred = fd_shred_parse( set->parity_shreds[ 0 ].b, FD_SHRED_MAX_SZ, max_shred_idx );
918 219 : int reject = (!base_data_shred) | (!base_parity_shred);
919 :
920 : /* Check idx of base shreds */
921 219 : reject = reject || ((base_data_shred->idx!=ctx->fec_set_idx) | (base_parity_shred->idx!=ctx->fec_set_idx) |
922 219 : (base_data_shred->data.flags & FD_SHRED_DATA_FLAG_DATA_COMPLETE));
923 :
924 7008 : for( ulong i=1UL; (!reject) & (i<FD_FEC_SHRED_CNT); i++ ) {
925 : /* Technically, we only need to re-parse the ones we recovered with
926 : Reedsol, but parsing is pretty cheap and the rest of the
927 : validation we need to do on all of them. */
928 6789 : fd_shred_t const * parsed = fd_shred_parse( set->data_shreds[ i ].b, FD_SHRED_MIN_SZ, max_shred_idx );
929 6789 : if( FD_UNLIKELY( !parsed ) ) { reject = 1; break; }
930 6789 : reject |= parsed->variant != base_data_shred->variant;
931 6789 : reject |= parsed->slot != base_data_shred->slot;
932 6789 : reject |= parsed->version != base_data_shred->version;
933 6789 : reject |= parsed->fec_set_idx != base_data_shred->fec_set_idx;
934 6789 : reject |= parsed->data.parent_off != base_data_shred->data.parent_off;
935 6789 : reject |= parsed->idx != (uint)(ctx->fec_set_idx+i);
936 6789 : reject |= (i!=FD_FEC_SHRED_CNT-1UL) && (parsed->data.flags & FD_SHRED_DATA_FLAG_DATA_COMPLETE);
937 :
938 6789 : reject |= fd_shred_is_chained( fd_shred_type( parsed->variant ) ) &&
939 6789 : !fd_memeq( (uchar *)parsed +fd_shred_chain_off( parsed->variant ),
940 6789 : (uchar *)base_data_shred+fd_shred_chain_off( base_data_shred->variant ), FD_SHRED_MERKLE_ROOT_SZ );
941 6789 : }
942 :
943 7227 : for( ulong i=0UL; (!reject) & (i<FD_FEC_SHRED_CNT); i++ ) {
944 7008 : fd_shred_t const * parsed = fd_shred_parse( set->parity_shreds[ i ].b, FD_SHRED_MAX_SZ, max_shred_idx );
945 7008 : if( FD_UNLIKELY( !parsed ) ) { reject = 1; break; }
946 7008 : reject |= fd_shred_type( parsed->variant ) != fd_shred_swap_type( fd_shred_type( base_data_shred->variant ) );
947 7008 : reject |= fd_shred_merkle_cnt( parsed->variant ) != fd_shred_merkle_cnt( base_data_shred->variant );
948 7008 : reject |= parsed->slot != base_data_shred->slot;
949 7008 : reject |= parsed->version != base_data_shred->version;
950 7008 : reject |= parsed->fec_set_idx != base_data_shred->fec_set_idx;
951 7008 : reject |= parsed->idx != (uint)(ctx->fec_set_idx+i);
952 7008 : reject |= parsed->code.data_cnt != base_parity_shred->code.data_cnt;
953 7008 : reject |= parsed->code.code_cnt != base_parity_shred->code.code_cnt;
954 7008 : reject |= parsed->code.idx != (ushort)i;
955 :
956 7008 : reject |= fd_shred_is_chained( fd_shred_type( parsed->variant ) ) &&
957 7008 : !fd_memeq( (uchar *)parsed +fd_shred_chain_off( parsed->variant ),
958 7008 : (uchar *)base_data_shred+fd_shred_chain_off( base_data_shred->variant ), FD_SHRED_MERKLE_ROOT_SZ );
959 7008 : }
960 219 : if( FD_UNLIKELY( reject ) ) {
961 0 : ctx_list_ele_push_tail( free_list, ctx, ctx_pool );
962 0 : resolver->free_list_cnt++;
963 0 : FD_MCNT_INC( SHRED, FEC_FATAL_REJECTED, 1UL );
964 0 : return FD_FEC_RESOLVER_SHRED_REJECTED;
965 0 : }
966 :
967 : /* Populate missing Merkle proofs */
968 7227 : for( ulong i=0UL; i<FD_FEC_SHRED_CNT; i++ ) if( !( set->data_shred_rcvd&(1U<<i) ) )
969 3615 : fd_bmtree_get_proof( tree, set->data_shreds[i].b + fd_shred_merkle_off( set->data_shreds[i].s ), i );
970 :
971 7227 : for( ulong i=0UL; i<FD_FEC_SHRED_CNT; i++ ) if( !( set->parity_shred_rcvd&(1U<<i) ) )
972 3393 : fd_bmtree_get_proof( tree, set->parity_shreds[i].b + fd_shred_merkle_off( set->parity_shreds[i].s ), FD_FEC_SHRED_CNT+i );
973 :
974 : /* Set the retransmitter signature for shreds that need one */
975 219 : if( FD_UNLIKELY( fd_shred_is_resigned( shred_type ) ) ) {
976 693 : for( ulong i=0UL; i<FD_FEC_SHRED_CNT; i++ ) if( !( set->data_shred_rcvd&(1U<<i) ) )
977 372 : memcpy( set->data_shreds[i].b + fd_shred_retransmitter_sig_off( set->data_shreds[i].s ), ctx->retransmitter_sig.u, 64UL );
978 :
979 693 : for( ulong i=0UL; i<FD_FEC_SHRED_CNT; i++ ) if( !( set->parity_shred_rcvd&(1U<<i) ) )
980 300 : memcpy( set->parity_shreds[i].b + fd_shred_retransmitter_sig_off( set->parity_shreds[i].s ), ctx->retransmitter_sig.u, 64UL );
981 21 : }
982 :
983 : /* Finally... A valid FEC set. Forward it along. */
984 219 : ctx_list_ele_push_tail( complete_list, ctx, ctx_pool );
985 219 : ctx_list_idx_push_tail( free_list, ctx_list_idx_pop_head( complete_list, ctx_pool ), ctx_pool );
986 219 : resolver->free_list_cnt++;
987 :
988 219 : *out_fec_set = set;
989 :
990 219 : return FD_FEC_RESOLVER_SHRED_COMPLETES;
991 219 : }
992 :
993 :
994 21 : void * fd_fec_resolver_leave( fd_fec_resolver_t * resolver ) {
995 21 : fd_sha512_leave( resolver->sha512 );
996 21 : done_heap_leave( resolver->done_heap );
997 21 : ctx_list_leave ( resolver->complete_list );
998 21 : ctx_list_leave ( resolver->free_list );
999 21 : ctx_treap_leave( resolver->ctx_treap );
1000 21 : done_map_leave ( resolver->done_map );
1001 21 : done_pool_leave( resolver->done_pool );
1002 21 : ctx_map_leave ( resolver->ctx_map );
1003 :
1004 21 : return (void *)resolver;
1005 21 : }
1006 :
1007 21 : void * fd_fec_resolver_delete( void * shmem ) {
1008 21 : fd_fec_resolver_t * resolver = (fd_fec_resolver_t *)shmem;
1009 21 : ulong depth = resolver->depth;
1010 21 : ulong partial_depth = resolver->partial_depth;
1011 21 : ulong complete_depth = resolver->complete_depth;
1012 21 : ulong done_depth = resolver->done_depth;
1013 :
1014 21 : ulong depth_sum = depth + partial_depth + complete_depth;
1015 21 : ulong ctx_chain_cnt = ctx_map_chain_cnt_est ( depth );
1016 21 : ulong done_chain_cnt = done_map_chain_cnt_est( done_depth );
1017 :
1018 21 : FD_SCRATCH_ALLOC_INIT( l, shmem );
1019 21 : /* self */ FD_SCRATCH_ALLOC_APPEND( l, FD_FEC_RESOLVER_ALIGN, sizeof(fd_fec_resolver_t) );
1020 21 : /* _ctx_pool */ FD_SCRATCH_ALLOC_APPEND( l, alignof(set_ctx_t), sizeof(set_ctx_t)*depth_sum );
1021 21 : void * _ctx_map = FD_SCRATCH_ALLOC_APPEND( l, ctx_map_align(), ctx_map_footprint ( ctx_chain_cnt ) );
1022 21 : void * _done_pool = FD_SCRATCH_ALLOC_APPEND( l, done_pool_align(), done_pool_footprint( done_depth ) );
1023 21 : void * _done_map = FD_SCRATCH_ALLOC_APPEND( l, done_map_align(), done_map_footprint ( done_chain_cnt ) );
1024 21 : FD_SCRATCH_ALLOC_FINI( l, FD_FEC_RESOLVER_ALIGN );
1025 :
1026 21 : fd_sha512_delete( resolver->sha512 );
1027 21 : done_heap_delete( resolver->done_heap );
1028 21 : done_map_delete ( _done_map );
1029 21 : done_pool_delete( _done_pool );
1030 21 : ctx_list_delete ( resolver->complete_list );
1031 21 : ctx_list_delete ( resolver->free_list );
1032 21 : ctx_treap_delete( resolver->ctx_treap );
1033 21 : ctx_map_delete ( _ctx_map );
1034 :
1035 21 : return shmem;
1036 21 : }
|
