LCOV - code coverage report
Current view: top level - disco/shred - fd_fec_resolver.c (source / functions) Hit Total Coverage
Test: cov.lcov Lines: 404 468 86.3 %
Date: 2025-07-01 05:00:49 Functions: 9 12 75.0 %

          Line data    Source code
       1             : #include "../../ballet/shred/fd_shred.h"
       2             : #include "../../ballet/shred/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             : 
       9             : typedef union {
      10             :   fd_ed25519_sig_t u;
      11             :   ulong            l;
      12             : } wrapped_sig_t;
      13             : 
      14             : struct set_ctx;
      15             : typedef struct set_ctx set_ctx_t;
      16             : 
      17             : struct __attribute__((aligned(32UL))) set_ctx {
      18             :   wrapped_sig_t         sig;
      19             :   fd_fec_set_t *        set;
      20             :   fd_bmtree_commit_t  * tree;
      21             :   set_ctx_t *           prev;
      22             :   set_ctx_t *           next;
      23             :   ulong                 total_rx_shred_cnt;
      24             :   ulong                 fec_set_idx;
      25             :   /* The shred index of the first parity shred in this FEC set */
      26             :   ulong                 parity_idx0;
      27             :   uchar                 data_variant;
      28             :   uchar                 parity_variant;
      29             :   /* If this FEC set has resigned shreds, this is our signature of the
      30             :      root of the Merkle tree */
      31             :   wrapped_sig_t         retransmitter_sig;
      32             : };
      33             : typedef struct set_ctx set_ctx_t;
      34             : 
      35             : #define DEQUE_NAME freelist
      36         588 : #define DEQUE_T    fd_fec_set_t *
      37             : #include "../../util/tmpl/fd_deque_dynamic.c"
      38             : 
      39             : #define DEQUE_NAME bmtrlist
      40         315 : #define DEQUE_T    void *
      41             : #include "../../util/tmpl/fd_deque_dynamic.c"
      42             : 
      43             : static const wrapped_sig_t null_signature = {{0}};
      44             : 
      45       27891 : #define MAP_KEY               sig
      46       19671 : #define MAP_KEY_T             wrapped_sig_t
      47        8220 : #define MAP_KEY_NULL          null_signature
      48       47856 : #define MAP_KEY_EQUAL(k0,k1)  (!memcmp( (k0).u, (k1).u, FD_ED25519_SIG_SZ ))
      49       29205 : #define MAP_KEY_INVAL(k)      MAP_KEY_EQUAL( k, MAP_KEY_NULL )
      50             : #define MAP_KEY_EQUAL_IS_SLOW 1
      51       19257 : #define MAP_KEY_HASH(key)     ((MAP_HASH_T)fd_ulong_hash( key.l ))
      52             : #define MAP_MEMOIZE           0
      53             : #define MAP_NAME              ctx_map
      54       20088 : #define MAP_T                 set_ctx_t
      55             : /* The prev and next fields of set_ctx_t thread a linked list through
      56             :    the map.  The map can move elements around during a deletion though,
      57             :    so we need to update the links when it does.  Thankfully it gives a
      58             :    perfect hook for doing so. */
      59           6 : #define MAP_MOVE(d,s)   do { \
      60           6 :                           set_ctx_t * _d = &(d); \
      61           6 :                           set_ctx_t * _s = &(s); \
      62           6 :                           _s->prev->next = _d;   \
      63           6 :                           _s->next->prev = _d;   \
      64           6 :                           *_d = *_s;             \
      65           6 :                         } while( 0 )
      66             : #include "../../util/tmpl/fd_map_dynamic.c"
      67             : 
      68             : 
      69             : struct __attribute__((aligned(FD_FEC_RESOLVER_ALIGN))) fd_fec_resolver {
      70             :   /* depth stores the number of FEC sets this resolver can track
      71             :      simultaneously.  done_depth stores the depth of the done tcache,
      72             :      i.e. the number of done FEC set keys that this resolver remembers.
      73             :      partial_depth stores the minimum size of the free FEC set list.
      74             :      completed_depth stores the size of the completed FEC set list. */
      75             :   ulong depth;
      76             :   ulong partial_depth;
      77             :   ulong complete_depth;
      78             :   ulong done_depth;
      79             : 
      80             :   /* expected_shred_version: discard all shreds with a shred version
      81             :      other than the specified value */
      82             :   ushort expected_shred_version;
      83             : 
      84             :   /* curr_map: A map (using fd_map_dynamic) from tags of signatures to
      85             :      the context object with its relevant data.  This map contains at
      86             :      most `depth` elements at any time, but to improve query performance,
      87             :      we size it at 2*depth. */
      88             :   set_ctx_t * curr_map;
      89             : 
      90             :   /* curr_ll_sentinel: The elements of curr_map also make
      91             :      essentially a circular doubly linked list using the next and prev
      92             :      fields.  To simplify the logic, we use a sentinel node that's
      93             :      stored here instead of in the map.  Thus, the head (newest) and the
      94             :      tail (oldest) of the linked list are the next and prev pointers of
      95             :      this context (respectively).  The other fields aren't used. */
      96             :   set_ctx_t curr_ll_sentinel[1];
      97             : 
      98             :   /* done: stores signatures of FEC sets that have recently been
      99             :      completed.  This is like a tcache, but with a non-ulong key and
     100             :      using a linked list instead of a ring buffer. Any new packets
     101             :      matching tags in this set can be ignored.  Since the data structure
     102             :      we need (map with linked list) is very similar to for curr_map, we
     103             :      just use the same fd_map_dynamic instantiation.  Only fields sig,
     104             :      prev, and next are used. */
     105             :   set_ctx_t * done_map;
     106             : 
     107             :   /* done_ll_sentinel: Analogous to curr_ll_sentinel, but for the done
     108             :      map instead of the current map. */
     109             :   set_ctx_t   done_ll_sentinel[1];
     110             : 
     111             :   /* free_list and complete_list are deques (using fd_deque_dynamic)
     112             :      that FEC sets that are not in contexts in curr_map.  Similarly,
     113             :      bmtree_free_list stores footprints for the bmtree objects that are
     114             :      not in contexts in curr_map.  These lists point to objects of
     115             :      indeterminate state and need to be cleared/reset when popped off.
     116             :      Invariant: at every entry and exit to fd_fec_resolver_add_shred:
     117             :      - free_list has between partial_depth and partial_depth+depth
     118             :        elements.
     119             :      - complete_list has complete_depth elements
     120             :      - bmtree_free_list has between 0 and depth elements
     121             :      (all these counts are inclusive). */
     122             :   fd_fec_set_t * * free_list;
     123             :   fd_fec_set_t * * complete_list;
     124             :   void         * * bmtree_free_list;
     125             : 
     126             :   /* signer is used to sign shreds that require a retransmitter
     127             :      signature.  sign_ctx is provided as the first argument to the
     128             :      function. */
     129             :   fd_fec_resolver_sign_fn * signer;
     130             :   void                    * sign_ctx;
     131             : 
     132             :   /* max_shred_idx is the exclusive upper bound for shred indices.  We
     133             :      need to reject any shred with an index >= max_shred_idx, but we
     134             :      also want to reject anything that is part of an FEC set where the
     135             :      highest index of a shred in the FEC set will be >= max_shred_idx.
     136             :      */
     137             :   ulong max_shred_idx;
     138             : 
     139             :   /* sha512 and reedsol are used for calculations while adding a shred.
     140             :      Their state outside a call to add_shred is indeterminate. */
     141             :   fd_sha512_t   sha512[1];
     142             :   fd_reedsol_t  reedsol[1];
     143             : 
     144             :   /* The footprint for the objects follows the struct and is in the same
     145             :      order as the pointers, namely:
     146             :        curr_map map
     147             :        done_map map
     148             :        free_list deque
     149             :        complete_list deque
     150             :        bmtree_free_list deque
     151             :        Actual footprint for bmtrees */
     152             : };
     153             : 
     154             : typedef struct fd_fec_resolver fd_fec_resolver_t;
     155             : 
     156             : FD_FN_PURE ulong
     157             : fd_fec_resolver_footprint( ulong depth,
     158             :                            ulong partial_depth,
     159             :                            ulong complete_depth,
     160           3 :                            ulong done_depth ) {
     161           3 :   if( FD_UNLIKELY( (depth==0UL) | (partial_depth==0UL) | (complete_depth==0UL) | (done_depth==0UL) ) ) return 0UL;
     162           3 :   if( FD_UNLIKELY( (depth>=(1UL<<62)-1UL) | (done_depth>=(1UL<<62)-1UL ) ) ) return 0UL; /* prevent overflow */
     163             : 
     164           3 :   int lg_curr_map_cnt = fd_ulong_find_msb( depth      + 1UL ) + 2; /* See fd_tcache.h for the logic */
     165           3 :   int lg_done_map_cnt = fd_ulong_find_msb( done_depth + 1UL ) + 2; /*  ... behind the + 2. */
     166             : 
     167           3 :   ulong footprint_per_bmtree = fd_bmtree_commit_footprint( FD_SHRED_MERKLE_LAYER_CNT );
     168             : 
     169           3 :   ulong layout = FD_LAYOUT_INIT;
     170           3 :   layout = FD_LAYOUT_APPEND( layout, FD_FEC_RESOLVER_ALIGN,  sizeof(fd_fec_resolver_t)                      );
     171           3 :   layout = FD_LAYOUT_APPEND( layout, ctx_map_align(),        ctx_map_footprint( lg_curr_map_cnt )           );
     172           3 :   layout = FD_LAYOUT_APPEND( layout, ctx_map_align(),        ctx_map_footprint( lg_done_map_cnt )           );
     173           3 :   layout = FD_LAYOUT_APPEND( layout, freelist_align(),       freelist_footprint( depth+partial_depth+1UL )  );
     174           3 :   layout = FD_LAYOUT_APPEND( layout, freelist_align(),       freelist_footprint( complete_depth+1UL  )      );
     175           3 :   layout = FD_LAYOUT_APPEND( layout, bmtrlist_align(),       bmtrlist_footprint( depth+1UL )                );
     176           3 :   layout = FD_LAYOUT_APPEND( layout, FD_BMTREE_COMMIT_ALIGN, depth*footprint_per_bmtree                     );
     177             : 
     178           3 :   return FD_LAYOUT_FINI( layout, FD_FEC_RESOLVER_ALIGN );
     179           3 : }
     180             : 
     181           0 : FD_FN_CONST ulong fd_fec_resolver_align( void ) { return FD_FEC_RESOLVER_ALIGN; }
     182             : 
     183             : 
     184             : void *
     185             : fd_fec_resolver_new( void                    * shmem,
     186             :                      fd_fec_resolver_sign_fn * signer,
     187             :                      void                    * sign_ctx,
     188             :                      ulong                     depth,
     189             :                      ulong                     partial_depth,
     190             :                      ulong                     complete_depth,
     191             :                      ulong                     done_depth,
     192             :                      fd_fec_set_t            * sets,
     193             :                      ushort                    expected_shred_version,
     194         210 :                      ulong                     max_shred_idx ) {
     195         210 :   if( FD_UNLIKELY( (depth==0UL) | (partial_depth==0UL) | (complete_depth==0UL) | (done_depth==0UL) ) ) return NULL;
     196         210 :   if( FD_UNLIKELY( (depth>=(1UL<<62)-1UL) | (done_depth>=(1UL<<62)-1UL ) ) ) return NULL;
     197             : 
     198         210 :   int lg_curr_map_cnt = fd_ulong_find_msb( depth      + 1UL ) + 2;
     199         210 :   int lg_done_map_cnt = fd_ulong_find_msb( done_depth + 1UL ) + 2;
     200             : 
     201         210 :   ulong footprint_per_bmtree = fd_bmtree_commit_footprint( FD_SHRED_MERKLE_LAYER_CNT );
     202             : 
     203         210 :   FD_SCRATCH_ALLOC_INIT( l, shmem );
     204         210 :   void * self        = FD_SCRATCH_ALLOC_APPEND( l, FD_FEC_RESOLVER_ALIGN,  sizeof(fd_fec_resolver_t)                       );
     205         210 :   void * curr        = FD_SCRATCH_ALLOC_APPEND( l, ctx_map_align(),        ctx_map_footprint( lg_curr_map_cnt )            );
     206         210 :   void * done        = FD_SCRATCH_ALLOC_APPEND( l, ctx_map_align(),        ctx_map_footprint( lg_done_map_cnt )            );
     207         210 :   void * free        = FD_SCRATCH_ALLOC_APPEND( l, freelist_align(),       freelist_footprint( depth+partial_depth+1UL )   );
     208         210 :   void * cmplst      = FD_SCRATCH_ALLOC_APPEND( l, freelist_align(),       freelist_footprint( complete_depth+1UL  )       );
     209         210 :   void * bmfree      = FD_SCRATCH_ALLOC_APPEND( l, bmtrlist_align(),       bmtrlist_footprint( depth+1UL )                 );
     210         210 :   void * bmfootprint = FD_SCRATCH_ALLOC_APPEND( l, FD_BMTREE_COMMIT_ALIGN, depth*footprint_per_bmtree                      );
     211         210 :   FD_SCRATCH_ALLOC_FINI( l, FD_FEC_RESOLVER_ALIGN );
     212             : 
     213         210 :   fd_fec_resolver_t * resolver = (fd_fec_resolver_t *)self;
     214             : 
     215         210 :   if( FD_UNLIKELY( !ctx_map_new  ( curr,   lg_curr_map_cnt         )) ) { FD_LOG_WARNING(( "curr map_new failed" )); return NULL; }
     216         210 :   if( FD_UNLIKELY( !ctx_map_new  ( done,   lg_done_map_cnt         )) ) { FD_LOG_WARNING(( "done map_new failed" )); return NULL; }
     217         210 :   if( FD_UNLIKELY( !freelist_new ( free,   depth+partial_depth+1UL )) ) { FD_LOG_WARNING(( "freelist_new failed" )); return NULL; }
     218         210 :   if( FD_UNLIKELY( !freelist_new ( cmplst, complete_depth+1UL      )) ) { FD_LOG_WARNING(( "freelist_new failed" )); return NULL; }
     219         210 :   if( FD_UNLIKELY( !bmtrlist_new ( bmfree, depth                   )) ) { FD_LOG_WARNING(( "bmtrlist_new failed" )); return NULL; }
     220         210 :   if( FD_UNLIKELY( !fd_sha512_new( (void *)resolver->sha512        )) ) { FD_LOG_WARNING(( "sha512_new failed"   )); return NULL; }
     221             : 
     222             :   /* Initialize all the lists */
     223         210 :   fd_fec_set_t * * free_list     = freelist_join( free   );
     224         210 :   fd_fec_set_t * * complete_list = freelist_join( cmplst );
     225         840 :   for( ulong i=0UL;                 i<depth+partial_depth;                i++ ) { freelist_push_tail( free_list,     sets+i ); }
     226         420 :   for( ulong i=depth+partial_depth; i<depth+partial_depth+complete_depth; i++ ) { freelist_push_tail( complete_list, sets+i ); }
     227         210 :   freelist_leave( complete_list );
     228         210 :   freelist_leave( free_list     );
     229             : 
     230         210 :   void * * bmtree_list = bmtrlist_join( bmfree );
     231         630 :   for( ulong i=0UL; i<depth; i++ ) { bmtrlist_push_tail( bmtree_list, (uchar *)bmfootprint + i*footprint_per_bmtree ); }
     232         210 :   bmtrlist_leave( bmtree_list );
     233             : 
     234         210 :   if( FD_UNLIKELY( expected_shred_version==(ushort)0 ) ) { FD_LOG_WARNING(( "expected shred version cannot be 0" )); return NULL; }
     235             : 
     236         210 :   resolver->curr_ll_sentinel->prev = resolver->curr_ll_sentinel;
     237         210 :   resolver->curr_ll_sentinel->next = resolver->curr_ll_sentinel;
     238         210 :   resolver->done_ll_sentinel->prev = resolver->done_ll_sentinel;
     239         210 :   resolver->done_ll_sentinel->next = resolver->done_ll_sentinel;
     240             : 
     241         210 :   resolver->depth                  = depth;
     242         210 :   resolver->partial_depth          = partial_depth;
     243         210 :   resolver->complete_depth         = complete_depth;
     244         210 :   resolver->done_depth             = done_depth;
     245         210 :   resolver->expected_shred_version = expected_shred_version;
     246         210 :   resolver->signer                 = signer;
     247         210 :   resolver->sign_ctx               = sign_ctx;
     248         210 :   resolver->max_shred_idx          = max_shred_idx;
     249         210 :   return shmem;
     250         210 : }
     251             : 
     252             : fd_fec_resolver_t *
     253         210 : fd_fec_resolver_join( void * shmem ) {
     254         210 :   fd_fec_resolver_t * resolver = (fd_fec_resolver_t *)shmem;
     255         210 :   ulong depth          = resolver->depth;
     256         210 :   ulong partial_depth  = resolver->partial_depth;
     257         210 :   ulong complete_depth = resolver->complete_depth;
     258         210 :   ulong done_depth     = resolver->done_depth;
     259             : 
     260         210 :   int lg_curr_map_cnt = fd_ulong_find_msb( depth      + 1UL ) + 2;
     261         210 :   int lg_done_map_cnt = fd_ulong_find_msb( done_depth + 1UL ) + 2;
     262             : 
     263         210 :   FD_SCRATCH_ALLOC_INIT( l, shmem );
     264         210 :   /*     self       */ FD_SCRATCH_ALLOC_APPEND( l, FD_FEC_RESOLVER_ALIGN,  sizeof(fd_fec_resolver_t)                     );
     265         210 :   void * curr        = FD_SCRATCH_ALLOC_APPEND( l, ctx_map_align(),        ctx_map_footprint( lg_curr_map_cnt )          );
     266         210 :   void * done        = FD_SCRATCH_ALLOC_APPEND( l, ctx_map_align(),        ctx_map_footprint( lg_done_map_cnt )          );
     267         210 :   void * free        = FD_SCRATCH_ALLOC_APPEND( l, freelist_align(),       freelist_footprint( depth+partial_depth+1UL ) );
     268         210 :   void * cmplst      = FD_SCRATCH_ALLOC_APPEND( l, freelist_align(),       freelist_footprint( complete_depth+1UL  )     );
     269         210 :   void * bmfree      = FD_SCRATCH_ALLOC_APPEND( l, bmtrlist_align(),       bmtrlist_footprint( depth+1UL )               );
     270         210 :   FD_SCRATCH_ALLOC_FINI( l, FD_FEC_RESOLVER_ALIGN );
     271             : 
     272         210 :   resolver->curr_map         = ctx_map_join  ( curr   ); if( FD_UNLIKELY( !resolver->curr_map         ) ) return NULL;
     273         210 :   resolver->done_map         = ctx_map_join  ( done   ); if( FD_UNLIKELY( !resolver->done_map         ) ) return NULL;
     274         210 :   resolver->free_list        = freelist_join ( free   ); if( FD_UNLIKELY( !resolver->free_list        ) ) return NULL;
     275         210 :   resolver->complete_list    = freelist_join ( cmplst ); if( FD_UNLIKELY( !resolver->complete_list    ) ) return NULL;
     276         210 :   resolver->bmtree_free_list = bmtrlist_join ( bmfree ); if( FD_UNLIKELY( !resolver->bmtree_free_list ) ) return NULL;
     277         210 :   if( FD_UNLIKELY( !fd_sha512_join( resolver->sha512 ) ) ) return NULL;
     278             : 
     279         210 :   return resolver;
     280         210 : }
     281             : 
     282             : /* Two helper functions for working with the linked lists that are
     283             :    threaded through maps.  Use them as follows:
     284             :       ctx_ll_insert( <sentinel corresponding to map>, ctx_map_insert( <map>, key ) );
     285             :       ctx_map_remove( <map>, ctx_ll_remove( <node to remove> ) );
     286             : 
     287             :   */
     288             : /* Removes r from the linked list */
     289             : static set_ctx_t *
     290         390 : ctx_ll_remove( set_ctx_t * r ) {
     291         390 :   r->next->prev = r->prev;
     292         390 :   r->prev->next = r->next;
     293         390 :   r->next = NULL;
     294         390 :   r->prev = NULL;
     295         390 :   return r;
     296         390 : }
     297             : 
     298             : /* Inserts c immediately after p.  Returns c. */
     299             : static set_ctx_t *
     300         621 : ctx_ll_insert( set_ctx_t * p, set_ctx_t * c ) {
     301         621 :   c->next = p->next;
     302         621 :   c->prev = p;
     303         621 :   p->next->prev = c;
     304         621 :   p->next       = c;
     305         621 :   return c;
     306         621 : }
     307             : 
     308             : int fd_fec_resolver_add_shred( fd_fec_resolver_t    * resolver,
     309             :                                fd_shred_t const     * shred,
     310             :                                ulong                  shred_sz,
     311             :                                uchar const          * leader_pubkey,
     312             :                                fd_fec_set_t const * * out_fec_set,
     313             :                                fd_shred_t const   * * out_shred,
     314        9522 :                                fd_bmtree_node_t     * out_merkle_root ) {
     315             :   /* Unpack variables */
     316        9522 :   ulong partial_depth = resolver->partial_depth;
     317        9522 :   ulong done_depth    = resolver->done_depth;
     318             : 
     319        9522 :   fd_fec_set_t * * free_list        = resolver->free_list;
     320        9522 :   fd_fec_set_t * * complete_list    = resolver->complete_list;
     321        9522 :   void         * * bmtree_free_list = resolver->bmtree_free_list;
     322        9522 :   set_ctx_t    *   curr_map         = resolver->curr_map;
     323        9522 :   set_ctx_t    *   done_map         = resolver->done_map;
     324             : 
     325        9522 :   fd_reedsol_t * reedsol       = resolver->reedsol;
     326        9522 :   fd_sha512_t  * sha512        = resolver->sha512;
     327             : 
     328        9522 :   set_ctx_t    * curr_ll_sentinel = resolver->curr_ll_sentinel;
     329        9522 :   set_ctx_t    * done_ll_sentinel = resolver->done_ll_sentinel;
     330             : 
     331             :   /* Invariants:
     332             :       * no key is in both the done map and the current map
     333             :       * each set pointer provided to the new function is in exactly one
     334             :           of curr_map, freelist, or complete_list
     335             :       * bmtree_free_list has exactly partial_depth fewer elements than
     336             :           freelist
     337             :    */
     338        9522 :   wrapped_sig_t * w_sig = (wrapped_sig_t *)shred->signature;
     339             : 
     340             :   /* Immediately reject any shred with a 0 signature. */
     341        9522 :   if( FD_UNLIKELY( ctx_map_key_inval( *w_sig ) ) ) return FD_FEC_RESOLVER_SHRED_REJECTED;
     342             : 
     343             :   /* Are we already done with this FEC set? */
     344        9522 :   int found = !!ctx_map_query( done_map, *w_sig, NULL );
     345             : 
     346        9522 :   if( found )  return FD_FEC_RESOLVER_SHRED_IGNORED; /* With no packet loss, we expect found==1 about 50% of the time */
     347             : 
     348        9081 :   set_ctx_t * ctx = ctx_map_query( curr_map, *w_sig, NULL );
     349             : 
     350        9081 :   fd_bmtree_node_t leaf[1];
     351        9081 :   uchar variant    = shred->variant;
     352        9081 :   uchar shred_type = fd_shred_type( variant );
     353             : 
     354        9081 :   if( FD_UNLIKELY( (shred_type==FD_SHRED_TYPE_LEGACY_DATA) | (shred_type==FD_SHRED_TYPE_LEGACY_CODE) ) ) {
     355             :     /* Reject any legacy shreds */
     356           0 :     return FD_FEC_RESOLVER_SHRED_REJECTED;
     357           0 :   }
     358             : 
     359        9081 :   if( FD_UNLIKELY( shred->version!=resolver->expected_shred_version ) ) return FD_FEC_RESOLVER_SHRED_REJECTED;
     360        9078 :   if( FD_UNLIKELY( shred_sz<fd_shred_sz( shred )                    ) ) return FD_FEC_RESOLVER_SHRED_REJECTED;
     361        9078 :   if( FD_UNLIKELY( shred->idx>=resolver->max_shred_idx              ) ) return FD_FEC_RESOLVER_SHRED_REJECTED;
     362             : 
     363        9066 :   int is_data_shred = fd_shred_is_data( shred_type );
     364             : 
     365        9066 :   if( !is_data_shred ) { /* Roughly 50/50 branch */
     366        4704 :     if( FD_UNLIKELY( (shred->code.data_cnt>FD_REEDSOL_DATA_SHREDS_MAX) | (shred->code.code_cnt>FD_REEDSOL_PARITY_SHREDS_MAX) ) )
     367           3 :       return FD_FEC_RESOLVER_SHRED_REJECTED;
     368        4701 :     if( FD_UNLIKELY( (shred->code.data_cnt==0UL) | (shred->code.code_cnt==0UL)                                               ) )
     369           0 :       return FD_FEC_RESOLVER_SHRED_REJECTED;
     370        4701 :     if( FD_UNLIKELY( (ulong)shred->fec_set_idx+(ulong)shred->code.data_cnt>=resolver->max_shred_idx                          ) )
     371           3 :       return FD_FEC_RESOLVER_SHRED_REJECTED;
     372        4698 :     if( FD_UNLIKELY( (ulong)shred->idx + (ulong)shred->code.code_cnt - (ulong)shred->code.idx>=resolver->max_shred_idx       ) )
     373           3 :       return FD_FEC_RESOLVER_SHRED_REJECTED;
     374        4698 :   }
     375             : 
     376             : 
     377             :   /* For the purposes of the shred header, tree_depth means the number
     378             :      of nodes, counting the leaf but excluding the root.  For bmtree,
     379             :      depth means the number of layers, which counts both. */
     380        9057 :   ulong tree_depth           = fd_shred_merkle_cnt( variant ); /* In [0, 15] */
     381        9057 :   ulong reedsol_protected_sz = 1115UL + FD_SHRED_DATA_HEADER_SZ - FD_SHRED_SIGNATURE_SZ - FD_SHRED_MERKLE_NODE_SZ*tree_depth
     382        9057 :                                       - FD_SHRED_MERKLE_ROOT_SZ*fd_shred_is_chained ( shred_type )
     383        9057 :                                       - FD_SHRED_SIGNATURE_SZ  *fd_shred_is_resigned( shred_type); /* In [743, 1139] conservatively*/
     384        9057 :   ulong data_merkle_protected_sz   = reedsol_protected_sz + FD_SHRED_MERKLE_ROOT_SZ*fd_shred_is_chained ( shred_type );
     385        9057 :   ulong parity_merkle_protected_sz = reedsol_protected_sz + FD_SHRED_MERKLE_ROOT_SZ*fd_shred_is_chained ( shred_type )+FD_SHRED_CODE_HEADER_SZ-FD_ED25519_SIG_SZ;
     386        9057 :   ulong merkle_protected_sz  = fd_ulong_if( is_data_shred, data_merkle_protected_sz, parity_merkle_protected_sz );
     387             : 
     388        9057 :   fd_bmtree_hash_leaf( leaf, (uchar const *)shred + sizeof(fd_ed25519_sig_t), merkle_protected_sz, FD_BMTREE_LONG_PREFIX_SZ );
     389             : 
     390             :   /* in_type_idx is between [0, code.data_cnt) or [0, code.code_cnt),
     391             :      where data_cnt <= FD_REEDSOL_DATA_SHREDS_MAX and code_cnt <=
     392             :      FD_REEDSOL_PARITY_SHREDS_MAX.
     393             :      On the other hand, shred_idx, goes from [0, code.data_cnt +
     394             :      code.code_cnt), with all the data shreds having
     395             :      shred_idx < code.data_cnt and all the parity shreds having
     396             :      shred_idx >= code.data_cnt. */
     397        9057 :   ulong in_type_idx = fd_ulong_if( is_data_shred, shred->idx - shred->fec_set_idx, shred->code.idx );
     398        9057 :   ulong shred_idx   = fd_ulong_if( is_data_shred, in_type_idx, in_type_idx + shred->code.data_cnt  );
     399             : 
     400        9057 :   if( FD_UNLIKELY( in_type_idx >= fd_ulong_if( is_data_shred, FD_REEDSOL_DATA_SHREDS_MAX, FD_REEDSOL_PARITY_SHREDS_MAX ) ) )
     401           0 :     return FD_FEC_RESOLVER_SHRED_REJECTED;
     402             :   /* This, combined with the check on shred->code.data_cnt implies that
     403             :      shred_idx is in [0, DATA_SHREDS_MAX+PARITY_SHREDS_MAX). */
     404             : 
     405        9057 :   if( FD_UNLIKELY( tree_depth>FD_SHRED_MERKLE_LAYER_CNT-1UL             ) ) return FD_FEC_RESOLVER_SHRED_REJECTED;
     406        9057 :   if( FD_UNLIKELY( fd_bmtree_depth( shred_idx+1UL ) > tree_depth+1UL ) ) return FD_FEC_RESOLVER_SHRED_REJECTED;
     407             : 
     408        9057 :   if( FD_UNLIKELY( !ctx ) ) {
     409             :     /* This is the first shred in the FEC set */
     410         315 :     if( FD_UNLIKELY( freelist_cnt( free_list )<=partial_depth ) ) {
     411             :       /* Packet loss is really high and we have a lot of in-progress FEC
     412             :          sets that we haven't been able to finish.  Take the resources
     413             :          (FEC set and bmtree) from the oldest, and send the oldest FEC
     414             :          set to the back of the free list. */
     415          33 :       set_ctx_t * victim_ctx = resolver->curr_ll_sentinel->prev;
     416             : 
     417             :       /* Add this one that we're sacrificing to the done map to
     418             :          prevent the possibility of thrashing. */
     419          33 :       ctx_ll_insert( done_ll_sentinel, ctx_map_insert( done_map, victim_ctx->sig ) );
     420          33 :       if( FD_UNLIKELY( ctx_map_key_cnt( done_map ) > done_depth ) ) ctx_map_remove( done_map, ctx_ll_remove( done_ll_sentinel->prev ) );
     421             : 
     422          33 :       freelist_push_tail( free_list,        victim_ctx->set  );
     423          33 :       bmtrlist_push_tail( bmtree_free_list, victim_ctx->tree );
     424             : 
     425             :       /* Remove from linked list and then from the map */
     426          33 :       ctx_map_remove( curr_map, ctx_ll_remove( victim_ctx ) );
     427             : 
     428          33 :       FD_MCNT_INC( SHRED, FEC_SET_SPILLED, 1UL );
     429          33 :     }
     430             :     /* Now we know |free_list|>partial_depth and |bmtree_free_list|>1 */
     431             : 
     432         315 :     fd_fec_set_t * set_to_use = freelist_pop_head( free_list        );
     433         315 :     void         * bmtree_mem = bmtrlist_pop_head( bmtree_free_list );
     434             : 
     435             :     /* Now we need to derive the root of the Merkle tree and verify the
     436             :        signature to prevent a DOS attack just by sending lots of invalid
     437             :        shreds. */
     438         315 :     fd_bmtree_commit_t * tree;
     439         315 :     tree = fd_bmtree_commit_init( bmtree_mem, FD_SHRED_MERKLE_NODE_SZ, FD_BMTREE_LONG_PREFIX_SZ, FD_SHRED_MERKLE_LAYER_CNT );
     440             : 
     441         315 :     fd_bmtree_node_t _root[1];
     442         315 :     fd_shred_merkle_t const * proof = fd_shred_merkle_nodes( shred );
     443         315 :     int rv = fd_bmtree_commitp_insert_with_proof( tree, shred_idx, leaf, (uchar const *)proof, tree_depth, _root );
     444         315 :     if( FD_UNLIKELY( !rv ) ) {
     445           0 :       freelist_push_head( free_list,        set_to_use );
     446           0 :       bmtrlist_push_head( bmtree_free_list, bmtree_mem );
     447           0 :       FD_MCNT_INC( SHRED, SHRED_REJECTED_INITIAL, 1UL );
     448           0 :       return FD_FEC_RESOLVER_SHRED_REJECTED;
     449           0 :     }
     450             : 
     451         315 :     if( FD_UNLIKELY( FD_ED25519_SUCCESS != fd_ed25519_verify( _root->hash, 32UL, shred->signature, leader_pubkey, sha512 ) ) ) {
     452           0 :       freelist_push_head( free_list,        set_to_use );
     453           0 :       bmtrlist_push_head( bmtree_free_list, bmtree_mem );
     454           0 :       FD_MCNT_INC( SHRED, SHRED_REJECTED_INITIAL, 1UL );
     455           0 :       return FD_FEC_RESOLVER_SHRED_REJECTED;
     456           0 :     }
     457             : 
     458             :     /* Copy the merkle root into the output arg. */
     459         315 :     if( FD_LIKELY( out_merkle_root ) ) memcpy( out_merkle_root, _root, sizeof(fd_bmtree_node_t) );
     460             : 
     461             :     /* This seems like a legitimate FEC set, so we can reserve some
     462             :        resources for it. */
     463         315 :     ctx = ctx_ll_insert( curr_ll_sentinel, ctx_map_insert( curr_map, *w_sig ) );
     464         315 :     ctx->set  = set_to_use;
     465         315 :     ctx->tree = tree;
     466         315 :     ctx->total_rx_shred_cnt = 0UL;
     467         315 :     ctx->data_variant   = fd_uchar_if(  is_data_shred, variant, fd_shred_variant( fd_shred_swap_type( shred_type ), (uchar)tree_depth ) );
     468         315 :     ctx->parity_variant = fd_uchar_if( !is_data_shred, variant, fd_shred_variant( fd_shred_swap_type( shred_type ), (uchar)tree_depth ) );
     469             : 
     470         315 :     if( FD_UNLIKELY( fd_shred_is_resigned( shred_type ) & !!(resolver->signer) ) ) {
     471           3 :       resolver->signer( resolver->sign_ctx, ctx->retransmitter_sig.u, _root->hash );
     472         312 :     } else {
     473         312 :       fd_memset( ctx->retransmitter_sig.u, 0, 64UL );
     474         312 :     }
     475             : 
     476             :     /* Reset the FEC set */
     477         315 :     ctx->set->data_shred_cnt   = SHRED_CNT_NOT_SET;
     478         315 :     ctx->set->parity_shred_cnt = SHRED_CNT_NOT_SET;
     479         315 :     d_rcvd_join( d_rcvd_new( d_rcvd_delete( d_rcvd_leave( ctx->set->data_shred_rcvd   ) ) ) );
     480         315 :     p_rcvd_join( p_rcvd_new( p_rcvd_delete( p_rcvd_leave( ctx->set->parity_shred_rcvd ) ) ) );
     481             : 
     482        8742 :   } else {
     483             :     /* This is not the first shred in the set */
     484             :     /* First, check to make sure this is not a duplicate */
     485        8742 :     int shred_dup = fd_int_if( is_data_shred, d_rcvd_test( ctx->set->data_shred_rcvd,   in_type_idx ),
     486        8742 :                                               p_rcvd_test( ctx->set->parity_shred_rcvd, in_type_idx ) );
     487             : 
     488        8742 :     if( FD_UNLIKELY( shred_dup ) ) return FD_FEC_RESOLVER_SHRED_IGNORED;
     489             : 
     490             :     /* Ensure that all the shreds in the FEC set have consistent
     491             :        variants.  They all must have the same tree_depth and the same
     492             :        chained/not chained, resigned/not resigned bits. */
     493        8529 :     if( FD_UNLIKELY( variant!=fd_uchar_if( is_data_shred, ctx->data_variant, ctx->parity_variant ) ) ) {
     494           0 :       return FD_FEC_RESOLVER_SHRED_REJECTED;
     495           0 :     }
     496             : 
     497        8529 :     fd_shred_merkle_t const * proof = fd_shred_merkle_nodes( shred );
     498        8529 :     int rv = fd_bmtree_commitp_insert_with_proof( ctx->tree, shred_idx, leaf, (uchar const *)proof, tree_depth, NULL );
     499        8529 :     if( !rv ) return FD_FEC_RESOLVER_SHRED_REJECTED;
     500        8529 :   }
     501             : 
     502        8838 :   if( FD_UNLIKELY( (ctx->set->data_shred_cnt==SHRED_CNT_NOT_SET) & (!is_data_shred) ) ) {
     503         291 :     ctx->set->data_shred_cnt   = shred->code.data_cnt;
     504         291 :     ctx->set->parity_shred_cnt = shred->code.code_cnt;
     505         291 :     ctx->parity_idx0           = shred->idx - in_type_idx;
     506         291 :     ctx->fec_set_idx           = shred->fec_set_idx;
     507         291 :   }
     508             : 
     509             :   /* At this point, the shred has passed Merkle validation and is new.
     510             :      We also know that ctx is a pointer to the slot for signature in the
     511             :      current map. */
     512             : 
     513             :   /* Copy the shred to memory the FEC resolver owns */
     514        8838 :   uchar * dst = fd_ptr_if( is_data_shred, ctx->set->data_shreds[ in_type_idx ], ctx->set->parity_shreds[ in_type_idx ] );
     515        8838 :   fd_memcpy( dst, shred, fd_shred_sz( shred ) );
     516             : 
     517             :   /* If the shred needs a retransmitter signature, set it */
     518        8838 :   if( FD_UNLIKELY( fd_shred_is_resigned( shred_type ) ) ) {
     519         729 :     memcpy( dst + fd_shred_retransmitter_sig_off( (fd_shred_t *)dst ), ctx->retransmitter_sig.u, 64UL );
     520         729 :   }
     521             : 
     522        8838 :   d_rcvd_insert_if( ctx->set->data_shred_rcvd,    is_data_shred, in_type_idx );
     523        8838 :   p_rcvd_insert_if( ctx->set->parity_shred_rcvd, !is_data_shred, in_type_idx );
     524        8838 :   ctx->total_rx_shred_cnt++;
     525             : 
     526        8838 :   *out_shred = (fd_shred_t const *)dst;
     527             : 
     528             :   /* Do we have enough to begin reconstruction? */
     529        8838 :   if( FD_LIKELY( ctx->total_rx_shred_cnt < ctx->set->data_shred_cnt ) ) return FD_FEC_RESOLVER_SHRED_OKAY;
     530             : 
     531             :   /* At this point, the FEC set is either valid or permanently invalid,
     532             :      so we can consider it done either way.  First though, since ctx_map_remove
     533             :      can change what's at *ctx, so unpack the values before we do that */
     534         270 :   fd_fec_set_t        * set            = ctx->set;
     535         270 :   fd_bmtree_commit_t  * tree           = ctx->tree;
     536         270 :   ulong                 fec_set_idx    = ctx->fec_set_idx;
     537         270 :   ulong                 parity_idx0    = ctx->parity_idx0;
     538         270 :   wrapped_sig_t         retran_sig     = ctx->retransmitter_sig;
     539         270 :   uchar                 parity_variant = ctx->parity_variant;
     540         270 :   uchar                 data_variant   = ctx->data_variant;
     541             : 
     542         270 :   ctx_ll_insert( done_ll_sentinel, ctx_map_insert( done_map, ctx->sig ) );
     543         270 :   if( FD_UNLIKELY( ctx_map_key_cnt( done_map ) > done_depth ) ) ctx_map_remove( done_map, ctx_ll_remove( done_ll_sentinel->prev ) );
     544             : 
     545         270 :   ctx_map_remove( curr_map, ctx_ll_remove( ctx ) );
     546             : 
     547         270 :   reedsol = fd_reedsol_recover_init( (void*)reedsol, reedsol_protected_sz );
     548        8826 :   for( ulong i=0UL; i<set->data_shred_cnt; i++ ) {
     549        8556 :     uchar * rs_payload = set->data_shreds[ i ] + sizeof(fd_ed25519_sig_t);
     550        8556 :     if( d_rcvd_test( set->data_shred_rcvd, i ) ) fd_reedsol_recover_add_rcvd_shred  ( reedsol, 1, rs_payload );
     551        4416 :     else                                         fd_reedsol_recover_add_erased_shred( reedsol, 1, rs_payload );
     552        8556 :   }
     553        8988 :   for( ulong i=0UL; i<set->parity_shred_cnt; i++ ) {
     554        8718 :     uchar * rs_payload = set->parity_shreds[ i ] + FD_SHRED_CODE_HEADER_SZ;
     555        8718 :     if( p_rcvd_test( set->parity_shred_rcvd, i ) ) fd_reedsol_recover_add_rcvd_shred  ( reedsol, 0, rs_payload );
     556        4254 :     else                                           fd_reedsol_recover_add_erased_shred( reedsol, 0, rs_payload );
     557        8718 :   }
     558             : 
     559         270 :   if( FD_UNLIKELY( FD_REEDSOL_SUCCESS != fd_reedsol_recover_fini( reedsol ) ) ) {
     560             :     /* A few lines up, we already checked to make sure it wasn't the
     561             :        insufficient case, so it must be the inconsistent case.  That
     562             :        means the leader signed a shred with invalid Reed-Solomon FEC
     563             :        set.  This shouldn't happen in practice, but we need to handle it
     564             :        for the malicious leader case.  This should probably be a
     565             :        slash-able offense. */
     566           0 :     freelist_push_tail( free_list,        set  );
     567           0 :     bmtrlist_push_tail( bmtree_free_list, tree );
     568           0 :     FD_MCNT_INC( SHRED, FEC_REJECTED_FATAL, 1UL );
     569           0 :     return FD_FEC_RESOLVER_SHRED_REJECTED;
     570           0 :   }
     571             : 
     572         270 :   uchar const * chained_root = fd_ptr_if( fd_shred_is_chained( shred_type ), (uchar *)shred+fd_shred_chain_off( variant ), NULL );
     573             : 
     574             :   /* Iterate over recovered shreds, add them to the Merkle tree,
     575             :      populate headers and signatures. */
     576        8826 :   for( ulong i=0UL; i<set->data_shred_cnt; i++ ) {
     577        8556 :     if( !d_rcvd_test( set->data_shred_rcvd, i ) ) {
     578        4416 :       fd_memcpy( set->data_shreds[i], shred, sizeof(fd_ed25519_sig_t) );
     579        4416 :       if( FD_LIKELY( fd_shred_is_chained( shred_type ) ) ) {
     580        2997 :         fd_memcpy( set->data_shreds[i]+fd_shred_chain_off( data_variant ), chained_root, FD_SHRED_MERKLE_ROOT_SZ );
     581        2997 :       }
     582        4416 :       fd_bmtree_hash_leaf( leaf, set->data_shreds[i]+sizeof(fd_ed25519_sig_t), data_merkle_protected_sz, FD_BMTREE_LONG_PREFIX_SZ );
     583        4416 :       if( FD_UNLIKELY( !fd_bmtree_commitp_insert_with_proof( tree, i, leaf, NULL, 0, NULL ) ) ) {
     584           0 :         freelist_push_tail( free_list,        set  );
     585           0 :         bmtrlist_push_tail( bmtree_free_list, tree );
     586           0 :         FD_MCNT_INC( SHRED, FEC_REJECTED_FATAL, 1UL );
     587           0 :         return FD_FEC_RESOLVER_SHRED_REJECTED;
     588           0 :       }
     589             : 
     590        4416 :     }
     591        8556 :   }
     592             : 
     593        8988 :   for( ulong i=0UL; i<set->parity_shred_cnt; i++ ) {
     594        8718 :     if( !p_rcvd_test( set->parity_shred_rcvd, i ) ) {
     595        4254 :       fd_shred_t * p_shred = (fd_shred_t *)set->parity_shreds[i]; /* We can't parse because we haven't populated the header */
     596        4254 :       fd_memcpy( p_shred->signature, shred->signature, sizeof(fd_ed25519_sig_t) );
     597        4254 :       p_shred->variant       = parity_variant;
     598        4254 :       p_shred->slot          = shred->slot;
     599        4254 :       p_shred->idx           = (uint)(i + parity_idx0);
     600        4254 :       p_shred->version       = shred->version;
     601        4254 :       p_shred->fec_set_idx   = (uint)fec_set_idx;
     602        4254 :       p_shred->code.data_cnt = (ushort)set->data_shred_cnt;
     603        4254 :       p_shred->code.code_cnt = (ushort)set->parity_shred_cnt;
     604        4254 :       p_shred->code.idx      = (ushort)i;
     605             : 
     606        4254 :       if( FD_LIKELY( fd_shred_is_chained( shred_type ) ) ) {
     607        3162 :         fd_memcpy( set->parity_shreds[i]+fd_shred_chain_off( parity_variant ), chained_root, FD_SHRED_MERKLE_ROOT_SZ );
     608        3162 :       }
     609             : 
     610        4254 :       fd_bmtree_hash_leaf( leaf, set->parity_shreds[i]+ sizeof(fd_ed25519_sig_t), parity_merkle_protected_sz, FD_BMTREE_LONG_PREFIX_SZ );
     611        4254 :       if( FD_UNLIKELY( !fd_bmtree_commitp_insert_with_proof( tree, set->data_shred_cnt + i, leaf, NULL, 0, NULL ) ) ) {
     612           0 :         freelist_push_tail( free_list,        set  );
     613           0 :         bmtrlist_push_tail( bmtree_free_list, tree );
     614           0 :         FD_MCNT_INC( SHRED, FEC_REJECTED_FATAL, 1UL );
     615           0 :         return FD_FEC_RESOLVER_SHRED_REJECTED;
     616           0 :       }
     617        4254 :     }
     618        8718 :   }
     619             : 
     620             :   /* Check that the whole Merkle tree is consistent. */
     621         270 :   if( FD_UNLIKELY( !fd_bmtree_commitp_fini( tree, set->data_shred_cnt + set->parity_shred_cnt ) ) ) {
     622           0 :     freelist_push_tail( free_list,        set  );
     623           0 :     bmtrlist_push_tail( bmtree_free_list, tree );
     624           0 :     FD_MCNT_INC( SHRED, FEC_REJECTED_FATAL, 1UL );
     625           0 :     return FD_FEC_RESOLVER_SHRED_REJECTED;
     626           0 :   }
     627             : 
     628             :   /* Check that all the fields that are supposed to be consistent across
     629             :      an FEC set actually are. */
     630         270 :   fd_shred_t const * base_data_shred   = fd_shred_parse( set->data_shreds  [ 0 ], FD_SHRED_MIN_SZ );
     631         270 :   fd_shred_t const * base_parity_shred = fd_shred_parse( set->parity_shreds[ 0 ], FD_SHRED_MAX_SZ );
     632         270 :   int reject = (!base_data_shred) | (!base_parity_shred);
     633             : 
     634        8556 :   for( ulong i=1UL; (!reject) & (i<set->data_shred_cnt); i++ ) {
     635             :     /* Technically, we only need to re-parse the ones we recovered with
     636             :        Reedsol, but parsing is pretty cheap and the rest of the
     637             :        validation we need to do on all of them. */
     638        8286 :     fd_shred_t const * parsed = fd_shred_parse( set->data_shreds[ i ], FD_SHRED_MIN_SZ );
     639        8286 :     if( FD_UNLIKELY( !parsed ) ) { reject = 1; break; }
     640        8286 :     reject |= parsed->variant         != base_data_shred->variant;
     641        8286 :     reject |= parsed->slot            != base_data_shred->slot;
     642        8286 :     reject |= parsed->version         != base_data_shred->version;
     643        8286 :     reject |= parsed->fec_set_idx     != base_data_shred->fec_set_idx;
     644        8286 :     reject |= parsed->data.parent_off != base_data_shred->data.parent_off;
     645             : 
     646        8286 :     reject |= fd_shred_is_chained( fd_shred_type( parsed->variant ) ) &&
     647        8286 :                 !fd_memeq( (uchar *)parsed         +fd_shred_chain_off( parsed->variant          ),
     648        5817 :                            (uchar *)base_data_shred+fd_shred_chain_off( base_data_shred->variant ), FD_SHRED_MERKLE_ROOT_SZ );
     649        8286 :   }
     650             : 
     651        8988 :   for( ulong i=0UL; (!reject) & (i<set->parity_shred_cnt); i++ ) {
     652        8718 :     fd_shred_t const * parsed = fd_shred_parse( set->parity_shreds[ i ], FD_SHRED_MAX_SZ );
     653        8718 :     if( FD_UNLIKELY( !parsed ) ) { reject = 1; break; }
     654        8718 :     reject |= fd_shred_type( parsed->variant )       != fd_shred_swap_type( fd_shred_type( base_data_shred->variant ) );
     655        8718 :     reject |= fd_shred_merkle_cnt( parsed->variant ) != fd_shred_merkle_cnt( base_data_shred->variant );
     656        8718 :     reject |= parsed->slot                           != base_data_shred->slot;
     657        8718 :     reject |= parsed->version                        != base_data_shred->version;
     658        8718 :     reject |= parsed->fec_set_idx                    != base_data_shred->fec_set_idx;
     659        8718 :     reject |= parsed->code.data_cnt                  != base_parity_shred->code.data_cnt;
     660        8718 :     reject |= parsed->code.code_cnt                  != base_parity_shred->code.code_cnt;
     661        8718 :     reject |= parsed->code.idx                       != (ushort)i;
     662             : 
     663        8718 :     reject |= fd_shred_is_chained( fd_shred_type( parsed->variant ) ) &&
     664        8718 :                 !fd_memeq( (uchar *)parsed         +fd_shred_chain_off( parsed->variant          ),
     665        6174 :                            (uchar *)base_data_shred+fd_shred_chain_off( base_data_shred->variant ), FD_SHRED_MERKLE_ROOT_SZ );
     666        8718 :   }
     667         270 :   if( FD_UNLIKELY( reject ) ) {
     668           0 :     freelist_push_tail( free_list,        set  );
     669           0 :     bmtrlist_push_tail( bmtree_free_list, tree );
     670           0 :     FD_MCNT_INC( SHRED, FEC_REJECTED_FATAL, 1UL );
     671           0 :     return FD_FEC_RESOLVER_SHRED_REJECTED;
     672           0 :   }
     673             : 
     674             :   /* Populate missing Merkle proofs */
     675        8826 :   for( ulong i=0UL; i<set->data_shred_cnt; i++ ) if( !d_rcvd_test( set->data_shred_rcvd, i ) )
     676        4416 :     fd_bmtree_get_proof( tree, set->data_shreds[i]   + fd_shred_merkle_off( (fd_shred_t *)set->data_shreds[i] ), i );
     677             : 
     678        8988 :   for( ulong i=0UL; i<set->parity_shred_cnt; i++ ) if( !p_rcvd_test( set->parity_shred_rcvd, i ) )
     679        4254 :     fd_bmtree_get_proof( tree, set->parity_shreds[i] + fd_shred_merkle_off( (fd_shred_t *)set->parity_shreds[i] ), set->data_shred_cnt+i );
     680             : 
     681             :   /* Set the retransmitter signature for shreds that need one */
     682         270 :   if( FD_UNLIKELY( fd_shred_is_resigned( shred_type ) ) ) {
     683         747 :     for( ulong i=0UL; i<set->data_shred_cnt; i++ ) if( !d_rcvd_test( set->data_shred_rcvd, i ) )
     684         324 :       memcpy( set->data_shreds[i]   + fd_shred_retransmitter_sig_off( (fd_shred_t *)set->data_shreds[i]   ), retran_sig.u, 64UL );
     685             : 
     686         747 :     for( ulong i=0UL; i<set->parity_shred_cnt; i++ ) if( !p_rcvd_test( set->parity_shred_rcvd, i ) )
     687         399 :       memcpy( set->parity_shreds[i] + fd_shred_retransmitter_sig_off( (fd_shred_t *)set->parity_shreds[i] ), retran_sig.u, 64UL );
     688          21 :   }
     689             : 
     690             :   /* Finally... A valid FEC set.  Forward it along. */
     691         270 :   bmtrlist_push_tail( bmtree_free_list, tree );
     692         270 :   freelist_push_tail( complete_list, set );
     693         270 :   freelist_push_tail( free_list, freelist_pop_head( complete_list ) );
     694             : 
     695         270 :   *out_fec_set = set;
     696             : 
     697         270 :   return FD_FEC_RESOLVER_SHRED_COMPLETES;
     698         270 : }
     699             : 
     700             : int
     701             : fd_fec_resolver_done_contains( fd_fec_resolver_t      * resolver,
     702           0 :                                fd_ed25519_sig_t const * signature ) {
     703           0 :   wrapped_sig_t * w_sig = (wrapped_sig_t *)signature;
     704           0 :   if( FD_UNLIKELY( ctx_map_key_inval( *w_sig ) ) ) return 0;
     705           0 :   return !!ctx_map_query( resolver->done_map, *w_sig, NULL );
     706           0 : }
     707             : 
     708             : int
     709             : fd_fec_resolver_shred_query( fd_fec_resolver_t      * resolver,
     710             :                              fd_ed25519_sig_t const * signature,
     711             :                              uint                     shred_idx,
     712           0 :                              uchar                  * out_shred ) {
     713           0 :   wrapped_sig_t * w_sig = (wrapped_sig_t *)signature;
     714           0 :   if( FD_UNLIKELY( ctx_map_key_inval( *w_sig ) ) ) return FD_FEC_RESOLVER_SHRED_REJECTED;
     715             : 
     716           0 :   set_ctx_t * ctx = ctx_map_query( resolver->curr_map, *w_sig, NULL );
     717           0 :   if( FD_UNLIKELY( !ctx ) ) return FD_FEC_RESOLVER_SHRED_REJECTED;
     718             : 
     719           0 :   fd_fec_set_t     * set        = ctx->set;
     720           0 :   fd_shred_t const * data_shred = (fd_shred_t const *)fd_type_pun_const( set->data_shreds[ shred_idx ] );
     721             : 
     722           0 :   ulong sz = fd_ulong_min( fd_shred_sz( data_shred ), FD_SHRED_MIN_SZ );
     723           0 :   fd_memcpy( out_shred, data_shred, sz );
     724           0 :   return FD_FEC_RESOLVER_SHRED_OKAY;
     725           0 : }
     726             : 
     727             : /* TODO code is copy-pasted because this function is intended to be
     728             :    removed as soon as an upgrade to the repair protocol to support
     729             :    requesting coding shreds is made available. */
     730             : 
     731             : int
     732             : fd_fec_resolver_force_complete( fd_fec_resolver_t *   resolver,
     733             :                                 fd_shred_t const *    last_shred,
     734          12 :                                 fd_fec_set_t const ** out_fec_set ) {
     735             : 
     736             :   /* Error if last_shred is obviously invalid... don't even
     737             :      try to process the associated FEC set. */
     738             : 
     739          12 :   ulong idx_in_set = last_shred->idx - last_shred->fec_set_idx;
     740             : 
     741          12 :   if( FD_UNLIKELY( idx_in_set >= FD_REEDSOL_DATA_SHREDS_MAX ) ) return FD_FEC_RESOLVER_SHRED_REJECTED;
     742             : 
     743             :   /* Error if can't find the last_shred's FEC set. */
     744             : 
     745          12 :   wrapped_sig_t * w_sig = (wrapped_sig_t *)last_shred->signature;
     746          12 :   if( FD_UNLIKELY( ctx_map_key_inval( *w_sig ) ) ) return FD_FEC_RESOLVER_SHRED_REJECTED;
     747             : 
     748             :   /* Error if already done. */
     749             : 
     750          12 :   int found = !!ctx_map_query( resolver->done_map, *w_sig, NULL );
     751          12 :   if( found )  return FD_FEC_RESOLVER_SHRED_IGNORED;
     752             : 
     753             :   /* Error if FEC associated with last_shred not found. */
     754             : 
     755          12 :   set_ctx_t * ctx = ctx_map_query( resolver->curr_map, *w_sig, NULL );
     756          12 :   if( FD_UNLIKELY( !ctx ) ) return FD_FEC_RESOLVER_SHRED_REJECTED;
     757             : 
     758             :   /* Error if already received parity shred (cnts are only knowable from
     759             :      receiving a coding shred). */
     760             : 
     761          12 :   if( FD_UNLIKELY( ctx->set->data_shred_cnt   != SHRED_CNT_NOT_SET ) ) return FD_FEC_RESOLVER_SHRED_REJECTED;
     762          12 :   if( FD_UNLIKELY( ctx->set->parity_shred_cnt != SHRED_CNT_NOT_SET ) ) return FD_FEC_RESOLVER_SHRED_REJECTED;
     763             : 
     764             :   /* Error if gaps in receives to last data shred. Implies that the FEC
     765             :      set is still incomplete. */
     766             : 
     767         126 :   for( ulong i=0UL; i<=idx_in_set; i++ ) if( !d_rcvd_test( ctx->set->data_shred_rcvd, i ) ) {
     768           3 :     return FD_FEC_RESOLVER_SHRED_REJECTED;
     769           3 :   }
     770             : 
     771             :   /* Error if last shred is not in fact last shred and FEC resolver has
     772             :      seen a shred with a higher idx. */
     773             : 
     774         117 :   for( ulong i=idx_in_set + 1; i<FD_REEDSOL_DATA_SHREDS_MAX; i++ ) if( d_rcvd_test( ctx->set->data_shred_rcvd, i ) ) {
     775           6 :     return FD_FEC_RESOLVER_SHRED_REJECTED;
     776           6 :   }
     777             : 
     778             :   /* Now we know the caller has provided a FEC set that is not obviously
     779             :      incomplete or invalid, we validate the FEC set itself. */
     780             : 
     781           3 :   fd_shred_t const * base_data_shred = fd_shred_parse( ctx->set->data_shreds[0], FD_SHRED_MIN_SZ );
     782           3 :   int reject = (!base_data_shred);
     783             : 
     784          96 :   for( ulong i=1UL; (!reject) & (i<=idx_in_set); i++ ) {
     785             : 
     786             :     /* casting is safe because these data shreds must have been all rcvd
     787             :        from the network and not recovered. */
     788             : 
     789          93 :     fd_shred_t const * parsed = (fd_shred_t const *)fd_type_pun_const( ctx->set->data_shreds[ i ] );
     790          93 :     if( FD_UNLIKELY( !parsed ) ) { reject = 1; break; }
     791          93 :     reject |= parsed->variant         != base_data_shred->variant;
     792          93 :     reject |= parsed->slot            != base_data_shred->slot;
     793          93 :     reject |= parsed->version         != base_data_shred->version;
     794          93 :     reject |= parsed->fec_set_idx     != base_data_shred->fec_set_idx;
     795          93 :     reject |= parsed->data.parent_off != base_data_shred->data.parent_off;
     796             : 
     797          93 :     reject |= fd_shred_is_chained( fd_shred_type( parsed->variant ) ) &&
     798          93 :                 !fd_memeq( (uchar *)parsed         +fd_shred_chain_off( parsed->variant          ),
     799           0 :                            (uchar *)base_data_shred+fd_shred_chain_off( base_data_shred->variant ), FD_SHRED_MERKLE_ROOT_SZ );
     800          93 :   }
     801             : 
     802           3 :   if( FD_UNLIKELY( reject ) ) {
     803           0 :     freelist_push_tail( resolver->free_list,        ctx->set  );
     804           0 :     bmtrlist_push_tail( resolver->bmtree_free_list, ctx->tree );
     805           0 :     FD_MCNT_INC( SHRED, FEC_REJECTED_FATAL, 1UL );
     806           0 :     return FD_FEC_RESOLVER_SHRED_REJECTED;
     807           0 :   }
     808             : 
     809             :   /* Populate correct shred cnts for post-completion processing, like
     810             :      forwarding to blockstore. */
     811             : 
     812           3 :   ctx->set->data_shred_cnt   = idx_in_set + 1UL;
     813           3 :   ctx->set->parity_shred_cnt = 0UL;
     814             : 
     815             :   /* Don't need to populate merkle proofs or retransmitter signatures
     816             :      because it is by definition the full set of rcvd data shreds. */
     817             : 
     818           3 :   set_ctx_t * done_ll_sentinel = resolver->done_ll_sentinel;
     819           3 :   set_ctx_t * curr_map         = resolver->curr_map;
     820           3 :   set_ctx_t * done_map         = resolver->done_map;
     821           3 :   ulong       done_depth       = resolver->done_depth;
     822             : 
     823           3 :   fd_fec_set_t        * set  = ctx->set;
     824           3 :   fd_bmtree_commit_t  * tree = ctx->tree;
     825             : 
     826           3 :   ctx_ll_insert( done_ll_sentinel, ctx_map_insert( done_map, ctx->sig ) );
     827           3 :   if( FD_UNLIKELY( ctx_map_key_cnt( done_map ) > done_depth ) ) ctx_map_remove( done_map, ctx_ll_remove( done_ll_sentinel->prev ) );
     828           3 :   ctx_map_remove( curr_map, ctx_ll_remove( ctx ) );
     829             : 
     830           3 :   bmtrlist_push_tail( resolver->bmtree_free_list, tree );
     831           3 :   freelist_push_tail( resolver->complete_list, set );
     832           3 :   freelist_push_tail( resolver->free_list, freelist_pop_head( resolver->complete_list ) );
     833             : 
     834           3 :   *out_fec_set = set;
     835             : 
     836           3 :   return FD_FEC_RESOLVER_SHRED_COMPLETES;
     837           3 : }
     838             : 
     839         114 : void * fd_fec_resolver_leave( fd_fec_resolver_t * resolver ) {
     840         114 :   fd_sha512_leave( resolver->sha512           );
     841         114 :   bmtrlist_leave ( resolver->bmtree_free_list );
     842         114 :   freelist_leave ( resolver->complete_list    );
     843         114 :   freelist_leave ( resolver->free_list        );
     844         114 :   ctx_map_leave  ( resolver->done_map         );
     845         114 :   ctx_map_leave  ( resolver->curr_map         );
     846             : 
     847         114 :   return (void *)resolver;
     848         114 : }
     849             : 
     850         114 : void * fd_fec_resolver_delete( void * shmem ) {
     851         114 :   fd_fec_resolver_t * resolver = (fd_fec_resolver_t *)shmem;
     852         114 :   ulong depth          = resolver->depth;
     853         114 :   ulong partial_depth  = resolver->partial_depth;
     854         114 :   ulong complete_depth = resolver->complete_depth;
     855         114 :   ulong done_depth     = resolver->done_depth;
     856             : 
     857         114 :   int lg_curr_map_cnt = fd_ulong_find_msb( depth      + 1UL ) + 2;
     858         114 :   int lg_done_map_cnt = fd_ulong_find_msb( done_depth + 1UL ) + 2;
     859             : 
     860         114 :   FD_SCRATCH_ALLOC_INIT( l, shmem );
     861         114 :   /*     self       */ FD_SCRATCH_ALLOC_APPEND( l, FD_FEC_RESOLVER_ALIGN,  sizeof(fd_fec_resolver_t)                     );
     862         114 :   void * curr        = FD_SCRATCH_ALLOC_APPEND( l, ctx_map_align(),        ctx_map_footprint( lg_curr_map_cnt )          );
     863         114 :   void * done        = FD_SCRATCH_ALLOC_APPEND( l, ctx_map_align(),        ctx_map_footprint( lg_done_map_cnt )          );
     864         114 :   void * free        = FD_SCRATCH_ALLOC_APPEND( l, freelist_align(),       freelist_footprint( depth+partial_depth+1UL ) );
     865         114 :   void * cmplst      = FD_SCRATCH_ALLOC_APPEND( l, freelist_align(),       freelist_footprint( complete_depth+1UL  )     );
     866         114 :   void * bmfree      = FD_SCRATCH_ALLOC_APPEND( l, bmtrlist_align(),       bmtrlist_footprint( depth+1UL )               );
     867         114 :   FD_SCRATCH_ALLOC_FINI( l, FD_FEC_RESOLVER_ALIGN );
     868             : 
     869         114 :   fd_sha512_delete( resolver->sha512 );
     870         114 :   bmtrlist_delete ( bmfree           );
     871         114 :   freelist_delete ( cmplst           );
     872         114 :   freelist_delete ( free             );
     873         114 :   ctx_map_delete  ( done             );
     874         114 :   ctx_map_delete  ( curr             );
     875             : 
     876         114 :   return shmem;
     877         114 : }

Generated by: LCOV version 1.14