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 "fd_fec_set.h"
4 : #include "../../ballet/bmtree/fd_bmtree.h"
5 : #include "../../ballet/ed25519/fd_ed25519.h"
6 :
7 : /* This header defines several methods for building and validating FEC
8 : sets from received shreds. It's designed just for use by the shred
9 : tile, which is why it's in disco/shred.
10 :
11 : The primary complication in the interface comes from lifetimes.
12 : Buffers returned by the networking layer are typically ephemeral and
13 : we need to hold onto the data until we've finished the FEC set, so we
14 : need at least one memcpy. Once we complete the FEC set, the result
15 : needs to go out on an mcache/dcache pair and on the network, which
16 : also have different lifetime requirements. The FEC resolver goes out
17 : of its way to use memory in a way that doesn't require a second
18 : memcpy once the FEC set is complete. To that end, the FEC resolver
19 : makes two promises:
20 : 1. Once memory has been used for a specific FEC set, it will not be
21 : reused for a different FEC set until at least partial_depth other
22 : distinct FEC sets have been returned in the out_fec_set field of
23 : fd_fec_resolver_add_shred.
24 : 2. Once a FEC set is complete (specified with COMPLETES), the
25 : associated memory will not be reused for a different FEC set until
26 : at least complete_depth other distinct FEC sets have been returned
27 : from calls to fd_fec_resolver_add_shred that return
28 : SHRED_COMPLETES.
29 :
30 : This is implemented using a freelist with an insertion point in the
31 : middle (which can also be seen as two chained freelists):
32 : ------------------------
33 : | In progress FEC |--------- if completed -
34 : | sets (<=depth) | |
35 : | |--- if spilled ---- |
36 : ------------------------ | |
37 : ^ | |
38 : | V |
39 : -------- | |
40 : | | - | V
41 : | Free | \ | |
42 : | | >=partial_depth | |
43 : | FEC | / | |
44 : | sets | | | |
45 : | | _ | |
46 : -------- V |
47 : ^ ^ | |
48 : | |------<---------------<----------| |
49 : | |
50 : -------- |
51 : | | - |
52 : | Comp | \ |
53 : |leted | complete_depth |
54 : | | / V
55 : | FEC | | |
56 : | sets | | |
57 : | | - |
58 : -------- |
59 : ^ |
60 : |-------------------<----------------------
61 :
62 : When a shred arrives for a new FEC set, we pull an entry from the
63 : head of the free FEC set queue. If that would result in more than
64 : depth sets in progress, we spill the oldest in progress set, and
65 : insert it at the tail of the free set queue. When we complete a set,
66 : we remove it from the in progress set, add it to the tail of the
67 : completed FEC set queue, and move one element from the head of the
68 : completed queue to the tail of the free queue.
69 :
70 : Since the completed queue only advances when an FEC set is completed,
71 : any complete FEC set stays in that queue for at least complete_depth
72 : completions.
73 :
74 : It might seems like this system is overkill and one combined longer
75 : freelist would suffice, but that's incorrect. Consider the following
76 : scenario: Suppose we've just completed FEC set A, so we return it
77 : with COMPLETES and then we put it at the end of the free list. Now
78 : we receive a shred for a new FEC set, so we take memory from the head
79 : of the free list. That happens many times, but we never receive
80 : enough shreds for any FEC set to complete one. Eventually, we churn
81 : through the whole singular freelist with spilling until the memory we
82 : used for A gets to the head of the freelist. Finally we receive
83 : enough shreds to complete the FEC set, so we return A with COMPLETES.
84 : Thus, from the perspective of a consumer that only cares about
85 : completed FEC sets, we've returned the same piece of memory twice in
86 : a row.
87 :
88 : While done_depth is independent of all these, it's worth including a
89 : note about it here too. Once we return with COMPLETES, we don't want
90 : to process that FEC set again, which means we need some memory of FEC
91 : sets that have been processed. Obviously, this memory has to be
92 : finite, so we retain the FEC sets with the highest (slot, FEC set
93 : index). In normal use, it would be rare to fill this data structure,
94 : but in a DoS attack, this policy makes the attack more difficult. */
95 :
96 : /* Forward declare opaque handle. It has a lot of types we don't
97 : necessarily want to bring into the includer */
98 0 : #define FD_FEC_RESOLVER_ALIGN (128UL)
99 : struct fd_fec_resolver;
100 : typedef struct fd_fec_resolver fd_fec_resolver_t;
101 :
102 :
103 : /* fd_fec_resolver_sign_fn: used to sign shreds that require a
104 : retransmitter signature. */
105 : typedef void (fd_fec_resolver_sign_fn)( void * ctx, uchar * sig, uchar const * merkle_root );
106 :
107 : FD_PROTOTYPES_BEGIN
108 : /* fd_fec_resolver_footprint returns the required footprint (in bytes as
109 : always) required to create an FEC set resolver that can keep track of
110 : `depth` in progress FEC sets, will not reuse FEC sets for at least
111 : partial_depth shreds or for at least complete_depth complete FEC sets
112 : (see above for more information). Additionally, the FEC resolver
113 : remembers done_depth FEC sets to recognize duplicates vs. new FEC
114 : sets. All depths must positive.
115 :
116 : fd_fec_resolver_alignment returns the required alignment of a region
117 : of memory for it to be used as a FEC resolver. */
118 : FD_FN_PURE ulong fd_fec_resolver_footprint( ulong depth, ulong partial_depth, ulong complete_depth, ulong done_depth );
119 : FD_FN_CONST ulong fd_fec_resolver_align ( void );
120 :
121 : /* fd_fec_resolver_new formats a region of memory as a FEC resolver.
122 : shmem must have the required alignment and footprint. signer is a
123 : function pointer used to sign any shreds that require a retransmitter
124 : signature, and sign_ctx is an opaque pointer passed as the first
125 : argument to the function. It is okay to pass NULL for signer, in
126 : which case, retransmission signatures will just be zeroed and
127 : sign_ctx will be ignored. depth, partial_depth, complete_depth, and
128 : done_depth are as defined above and must be positive. The sum of
129 : depth, partial_depth, and complete_depth must be less than UINT_MAX.
130 : sets is a pointer to the first of depth+partial_depth+complete_depth
131 : FEC sets that this resolver will take ownership of. The FEC resolver
132 : retains a write interest in these FEC sets and the shreds they point
133 : to until the resolver is deleted. These FEC sets and the memory for
134 : the shreds they point to are the only values that will be returned in
135 : the out_shred and out_fec_set output parameters of add_shred. The
136 : FEC resolver will also reject any shred that seems to be part of a
137 : block containing more than max_shred_idx data or parity shreds.
138 : Since shred_idx is a uint, it doesn't really make sense to have
139 : max_shred_idx > UINT_MAX, and max_shred_idx==0 rejects all shreds.
140 : seed is an arbitrary ulong used to seed various data structures. It
141 : should be set to a validator independent value.
142 :
143 : On success, the FEC resolver will be initialized with an expected
144 : shred version of 0, which causes it to reject all shreds, and a
145 : slot_old of slot 0, which causes it to ignore no shreds.
146 :
147 : Returns shmem on success and NULL on failure (logs details). */
148 : void *
149 : fd_fec_resolver_new( void * shmem,
150 : fd_fec_resolver_sign_fn * signer,
151 : void * sign_ctx,
152 : ulong depth,
153 : ulong partial_depth,
154 : ulong complete_depth,
155 : ulong done_depth,
156 : fd_fec_set_t * sets,
157 : ulong max_shred_idx,
158 : ulong seed );
159 :
160 : fd_fec_resolver_t * fd_fec_resolver_join( void * shmem );
161 :
162 : /* fd_fec_resolver_set_shred_version updates the expected shred version
163 : to the value provided in expected_shred_version. resolver must be a
164 : valid local join. add_shred will reject any future shreds with a
165 : shred version other than the new expected shred version. Setting
166 : expected_shred_version to 0 causes the FEC resolver to reject all
167 : future shreds. This function will not immediately trigger the FEC
168 : resolver to discard any previously accepted shreds, but changing the
169 : expected shred version will make it impossible to complete any FEC
170 : sets that are in progress prior to the call. */
171 : void
172 : fd_fec_resolver_set_shred_version( fd_fec_resolver_t * resolver,
173 : ushort expected_shred_version );
174 :
175 : /* fd_fec_resolver_set_discard_unexpected_data_complete_shreds updates
176 : the activation slot used by the FEC resolver for the
177 : discard_unexpected_data_complete_shreds feature. */
178 : void
179 : fd_fec_resolver_set_discard_unexpected_data_complete_shreds( fd_fec_resolver_t * resolver,
180 : ulong activation_slot );
181 :
182 : /* fd_fec_resolver_advance_slot_old advances slot_old, discarding any
183 : in progress FEC sets with a slot strictly less than slot_old.
184 : Additionally, causes the FEC resolver to ignore any future shreds
185 : with a slot older than the new value of slot_old. slot_old increases
186 : monotonically, which means that a call to advance_slot_old with a
187 : lower value of slot_old is a no-op. */
188 : void
189 : fd_fec_resolver_advance_slot_old( fd_fec_resolver_t * resolver,
190 : ulong slot_old );
191 :
192 :
193 : /* Keep in sync with metrics.xml */
194 552 : #define FD_FEC_RESOLVER_SHRED_EQUIVOC (-4)
195 123 : #define FD_FEC_RESOLVER_SHRED_REJECTED (-3)
196 654 : #define FD_FEC_RESOLVER_SHRED_IGNORED (-2)
197 249 : #define FD_FEC_RESOLVER_SHRED_DUPLICATE (-1)
198 7194 : #define FD_FEC_RESOLVER_SHRED_OKAY ( 0)
199 219 : #define FD_FEC_RESOLVER_SHRED_COMPLETES ( 1)
200 :
201 : /* Return values + RETVAL_OFF are in [0, RETVAL_CNT) */
202 : #define FD_FEC_RESOLVER_ADD_SHRED_RETVAL_CNT 6
203 0 : #define FD_FEC_RESOLVER_ADD_SHRED_RETVAL_OFF 4
204 :
205 : struct fd_fec_resolver_spilled {
206 : ulong slot;
207 : uint fec_set_idx;
208 : fd_bmtree_node_t merkle_root[1];
209 : };
210 : typedef struct fd_fec_resolver_spilled fd_fec_resolver_spilled_t;
211 :
212 : /* fd_fec_resolver_add_shred notifies the FEC resolver of a newly
213 : received shred. The FEC resolver validates the shred and copies it
214 : into its own storage. resolver is a local join of an FEC resolver.
215 : shred is a pointer to the new shred that should be added. The shred
216 : must have passed the shred parsing validation. shred_sz is the size
217 : of the shred in bytes. If is_repair is non-zero, some validity
218 : checks will be omitted, as detailed below. leader_pubkey must be a
219 : pointer to the first byte of the public identity key of the validator
220 : that was leader during slot shred->slot.
221 :
222 : On success ie. SHRED_{OKAY,COMPLETES}, a pointer to the fd_fec_set_t
223 : structure representing the FEC set of which the shred is a part will
224 : be written to out_fec_set. Additionally, on success a pointer to a
225 : copy of shred will be written to the location pointed to by
226 : out_shred. See the long explanation above about the lifetimes of
227 : these pointers. Finally, on success the merkle root of the shred
228 : (reconstructed from the merkle proof) will be written to
229 : out_merkle_root. Unlike out_{fec_set,shred}, caller owns and
230 : provides the memory for out_merkle_root. If the out_merkle_root
231 : pointer is NULL, the argument will be ignored and merkle root will
232 : not be written.
233 :
234 : If the shred's Merkle root differs from the Merkle root of a
235 : previously received shred with the same values for slot and FEC
236 : index, and is_repair is zero, the shred may be rejected with return
237 : value SHRED_EQUIVOC. The FEC resolver has a limited memory, which is
238 : why equivocation detection cannot be guaranteed. Note that these
239 : checks are bypassed if is_repair is non-zero.
240 :
241 : If the shred has the same slot, shred index, and signature as a shred
242 : that has already been successfully completed in a FEC by the FEC
243 : resolver, or if the shred is for a slot older than slot_old, returns
244 : SHRED_IGNORED and does not write to out_{fec_set,shred,merkle_root}.
245 : Note that "successfully completed in a FEC by the FEC resolver" above
246 : includes shreds that are reconstructed when returning
247 : SHRED_COMPLETES, so for example, after returning SHRED_COMPLETES for
248 : a FEC set, adding any shred for that FEC set will return
249 : SHRED_IGNORED, even if that particular shred hadn't been received.
250 :
251 : However, if the shred is part of an in progress FEC set but has
252 : already been received, FEC resolver returns SHRED_DUPLICATE and
253 : populates out_merkle_root if it is non-NULL.
254 :
255 : If the shred fails validation for any other reason, returns
256 : SHRED_REJECTED and does not write to out_{fec_set,shred,merkle_root}.
257 :
258 : Note that only light validation is performed on a duplicate shred, so
259 : a shred that is actually invalid but looks like a duplicate of a
260 : previously received valid shred may be considered SHRED_IGNORED
261 : instead of SHRED_REJECTED.
262 :
263 : This function returns SHRED_COMPLETES when the received shred
264 : completes the FEC set. In this case, the function populates any
265 : missing shreds in the FEC set stored in out_fec_set.
266 :
267 : Regardless of success/failure, if an in progress FEC set was evicted
268 : from the current map during this add_shred call, and the
269 : out_spilled_fec_set pointer is not NULL, the metadata of the evicted
270 : FEC set will be written to out_spilled_fec_set. The FEC set metadata
271 : consists of the slot, FEC set index, and the Merkle root of the
272 : evicted FEC set. Similar to out_merkle_root, the caller owns and
273 : provides the memory for out_spilled_fec_set. If
274 : out_spilled_fec_set is NULL, the evicted FEC set metadata will not be
275 : written even if an in progress FEC set was evicted. */
276 :
277 : int
278 : fd_fec_resolver_add_shred( fd_fec_resolver_t * resolver,
279 : fd_shred_t const * shred,
280 : ulong shred_sz,
281 : int is_repair,
282 : uchar const * leader_pubkey,
283 : fd_fec_set_t const * * out_fec_set,
284 : fd_shred_t const * * out_shred,
285 : fd_bmtree_node_t * out_merkle_root,
286 : fd_fec_resolver_spilled_t * out_spilled_fec_set );
287 :
288 :
289 : void * fd_fec_resolver_leave( fd_fec_resolver_t * resolver );
290 : void * fd_fec_resolver_delete( void * shmem );
291 :
292 : FD_PROTOTYPES_END
293 : #endif /* HEADER_fd_src_disco_shred_fd_fec_resolver_h */
|
