Line data Source code
1 : #ifndef HEADER_fd_src_disco_shred_fd_fec_resolver_h 2 : #define HEADER_fd_src_disco_shred_fd_fec_resolver_h 3 : #include "../../ballet/shred/fd_fec_set.h" 4 : 5 : /* This header defines several methods for building and validating FEC 6 : sets from received shreds. It's designed just for use by the shred 7 : tile, which is why it's in disco/shred. 8 : 9 : The primary complication in the interface comes from lifetimes. 10 : Buffers returned by the networking layer are typically ephemeral and 11 : we need to hold onto the data until we've finished the FEC set, so we 12 : need at least one memcpy. Once we complete the FEC set, the result 13 : needs to go out on an mcache/dcache pair and on the network, which 14 : also have different lifetime requirements. The FEC resolver goes out 15 : of its way to use memory in a way that doesn't require a second 16 : memcpy once the FEC set is complete. To that end, the FEC resolver 17 : makes two promises: 18 : 1. Once memory has been used for a specific FEC set, it will not be 19 : reused for a different FEC set until at least partial_depth other 20 : distinct FEC sets have been returned in the out_fec_set field of 21 : fd_fec_resolver_add_shred. 22 : 2. Once a FEC set is complete (specified with COMPLETES), the 23 : associated memory will not be reused for a different FEC set until 24 : at least complete_depth other distinct FEC sets have been returned 25 : from calls to fd_fec_resolver_add_shred that return 26 : SHRED_COMPLETES. 27 : 28 : This is implemented using a freelist with an insertion point in the 29 : middle (which can also be seen as two chained freelists): 30 : ------------------------ 31 : | In progress FEC |--------- if completed - 32 : | sets (<=depth) | | 33 : | |--- if spilled ---- | 34 : ------------------------ | | 35 : ^ | | 36 : | V | 37 : -------- | | 38 : | | - | V 39 : | Free | \ | | 40 : | | >=partial_depth | | 41 : | FEC | / | | 42 : | sets | | | | 43 : | | _ | | 44 : -------- V | 45 : ^ ^ | | 46 : | |------<---------------<----------| | 47 : | | 48 : -------- | 49 : | | - | 50 : | Comp | \ | 51 : |leted | complete_depth | 52 : | | / V 53 : | FEC | | | 54 : | sets | | | 55 : | | - | 56 : -------- | 57 : ^ | 58 : |-------------------<---------------------- 59 : 60 : When a shred arrives for a new FEC set, we pull an entry from the 61 : head of the free FEC set queue. If that would result in more than 62 : depth sets in progress, we spill the oldest in progress set, and 63 : insert it at the tail of the free set queue. When we complete a set, 64 : we remove it from the in progress set, add it to the tail of the 65 : completed FEC set queue, and move one element from the head of the 66 : completed queue to the tail of the free queue. 67 : 68 : Since the completed queue only advances when an FEC set is completed, 69 : any complete FEC set stays in that queue for at least complete_depth 70 : completions. 71 : 72 : It might seems like this system is overkill and one combined longer 73 : freelist would suffice, but that's incorrect. Consider the following 74 : scenario: Suppose we've just completed FEC set A, so we return it 75 : with COMPLETES and then we put it at the end of the free list. Now 76 : we receive a shred for a new FEC set, so we take memory from the head 77 : of the free list. That happens many times, but we never receive 78 : enough shreds for any FEC set to complete one. Eventually, we churn 79 : through the whole singular freelist with spilling until the memory we 80 : used for A gets to the head of the freelist. Finally we receive 81 : enough shreds to complete the FEC set, so we return A with COMPLETES. 82 : Thus, from the perspective of a consumer that only cares about 83 : completed FEC sets, we've returned the same piece of memory twice in 84 : a row. */ 85 : 86 : /* Forward declare opaque handle. It has a lot of types we don't 87 : necessarily want to bring into the includer */ 88 6 : #define FD_FEC_RESOLVER_ALIGN (128UL) 89 : struct fd_fec_resolver; 90 : typedef struct fd_fec_resolver fd_fec_resolver_t; 91 : 92 : /* fd_fec_resolver_sign_fn: used to sign shreds that require a 93 : retransmitter signature. */ 94 : typedef void (fd_fec_resolver_sign_fn)( void * ctx, uchar * sig, uchar const * merkle_root ); 95 : 96 : FD_PROTOTYPES_BEGIN 97 : /* fd_fec_resolver_footprint returns the required footprint (in bytes as 98 : always) required to create an FEC set resolver that can keep track of 99 : `depth` in progress FEC sets, will not reuse FEC sets for at least 100 : partial_depth shreds or for at least complete_depth complete FEC sets 101 : (see above for more information). Additionally, the FEC resolver 102 : remembers done_depth FEC sets to recognize duplicates vs. new FEC 103 : sets. All depths must positive. 104 : 105 : fd_fec_resolver_alignment returns the required alignment of a region 106 : of memory for it to be used as a FEC resolver. */ 107 : ulong fd_fec_resolver_footprint( ulong depth, ulong partial_depth, ulong complete_depth, ulong done_depth ); 108 : ulong fd_fec_resolver_align ( void ); 109 : 110 : /* fd_fec_resolver_new formats a region of memory as a FEC resolver. 111 : shmem must have the required alignment and footprint. signer is a 112 : function pointer used to sign any shreds that require a retransmitter 113 : signature, and sign_ctx is an opaque pointer passed as the first 114 : argument to the function. It is okay to pass NULL for signer, in 115 : which case, retransmission signatures will just be zeroed and 116 : sign_ctx will be ignored. depth, partial_depth, complete_depth, and 117 : done_depth are as defined above and must be positive. sets is a 118 : pointer to the first of depth+partial_depth+complete_depth FEC sets 119 : that this resolver will take ownership of. The FEC resolver retains 120 : a write interest in these FEC sets and the shreds they point to until 121 : the resolver is deleted. These FEC sets and the memory for the 122 : shreds they point to are the only values that will be returned in the 123 : output parameters of _add_shred. The FEC resolver will reject any 124 : shreds with a shred version that does not match the value provided 125 : for expected_shred_version. Shred versions are always non-zero, so 126 : expected_shred_version must be non-zero. The FEC resolver will also 127 : reject any shred that seems to be part of a block containing more 128 : than max_shred_idx data or parity shreds. Since shred_idx is a uint, 129 : it doesn't really make sense to have max_shred_idx > UINT_MAX, and 130 : max_shred_idx==0 rejects all shreds. Returns shmem on success and 131 : NULL on failure (logs details). */ 132 : void * 133 : fd_fec_resolver_new( void * shmem, 134 : fd_fec_resolver_sign_fn * signer, 135 : void * sign_ctx, 136 : ulong depth, 137 : ulong partial_depth, 138 : ulong complete_depth, 139 : ulong done_depth, 140 : fd_fec_set_t * sets, 141 : ushort expected_shred_version, 142 : ulong max_shred_idx ); 143 : 144 : fd_fec_resolver_t * fd_fec_resolver_join( void * shmem ); 145 : 146 27 : #define FD_FEC_RESOLVER_SHRED_REJECTED (-2) 147 1104 : #define FD_FEC_RESOLVER_SHRED_IGNORED (-1) 148 2832 : #define FD_FEC_RESOLVER_SHRED_OKAY ( 0) 149 90 : #define FD_FEC_RESOLVER_SHRED_COMPLETES ( 1) 150 : 151 : /* Return values + RETVAL_OFF are in [0, RETVAL_CNT) */ 152 : #define FD_FEC_RESOLVER_ADD_SHRED_RETVAL_CNT 4 153 0 : #define FD_FEC_RESOLVER_ADD_SHRED_RETVAL_OFF 2 154 : 155 : 156 : 157 : /* fd_fec_resolver_add_shred notifies the FEC resolver of a newly 158 : received shred. The FEC resolver validates the shred and copies it 159 : into its own storage. resolver is a local join of an FEC resolver. 160 : shred is a pointer to the new shred that should be added. shred_sz 161 : is the size of the shred in bytes. 162 : 163 : On success (SHRED_OKAY or SHRED_COMPLETES), a pointer to the 164 : fd_fec_set_t structure representing the FEC set of which the shred is 165 : a part will be written to out_fec_set. Additionally, on success a 166 : pointer to a copy of shred will be written to the location pointed to 167 : by out_shred. See the long explanation above about the lifetimes of 168 : these pointers. 169 : 170 : If the shred fails validation for any reason, SHRED_REJECTED will be 171 : returned and nothing will be written to out_fec_set or out_shred. 172 : If the shred is a duplicate of a shred that has already been 173 : received, SHRED_IGNORED will be returned, and nothing will be written 174 : to out_fec_set or out_shred. Note that only light validation is 175 : performed on a duplicate shred, so a shred that is actually invalid 176 : but looks like a duplicate of a previously received valid shred may 177 : be considered SHRED_IGNORED instead of SHRED_REJECTED. 178 : 179 : This function returns SHRED_COMPLETES when the received shred is the 180 : last one and completes the FEC set. In this case, the function 181 : populates any missing shreds in the FEC set stored in out_fec_set. */ 182 : int fd_fec_resolver_add_shred( fd_fec_resolver_t * resolver, 183 : fd_shred_t const * shred, 184 : ulong shred_sz, 185 : uchar const * leader_pubkey, 186 : fd_fec_set_t const * * out_fec_set, 187 : fd_shred_t const * * out_shred ); 188 : 189 : void * fd_fec_resolver_leave( fd_fec_resolver_t * resolver ); 190 : void * fd_fec_resolver_delete( void * shmem ); 191 : 192 : FD_PROTOTYPES_END 193 : #endif /* HEADER_fd_src_disco_shred_fd_fec_resolver_h */
