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