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