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. seed
136 : is an arbitrary ulong used to seed various data structures. It
137 : should be set to a validator independent value.
138 :
139 : On success, the FEC resolver will be initialized with an expected
140 : shred version of 0, which causes it to reject all shreds, and a
141 : slot_old of slot 0, which causes it to ignore no shreds.
142 :
143 : Returns shmem on success and NULL on failure (logs details). */
144 : void *
145 : fd_fec_resolver_new( void * shmem,
146 : fd_fec_resolver_sign_fn * signer,
147 : void * sign_ctx,
148 : ulong depth,
149 : ulong partial_depth,
150 : ulong complete_depth,
151 : ulong done_depth,
152 : fd_fec_set_t * sets,
153 : ulong seed );
154 :
155 : fd_fec_resolver_t * fd_fec_resolver_join( void * shmem );
156 :
157 : /* fd_fec_resolver_set_shred_version updates the expected shred version
158 : to the value provided in expected_shred_version. resolver must be a
159 : valid local join. add_shred will reject any future shreds with a
160 : shred version other than the new expected shred version. Setting
161 : expected_shred_version to 0 causes the FEC resolver to reject all
162 : future shreds. This function will not immediately trigger the FEC
163 : resolver to discard any previously accepted shreds, but changing the
164 : expected shred version will make it impossible to complete any FEC
165 : sets that are in progress prior to the call. */
166 : void
167 : fd_fec_resolver_set_shred_version( fd_fec_resolver_t * resolver,
168 : ushort expected_shred_version );
169 :
170 : /* fd_fec_resolver_set_bypass_verify configures whether Merkle proof and
171 : leader signature verification are bypassed in add_shred. This is
172 : intended for test and fuzz harnesses that focus on parser/replay
173 : behavior and do not carry enough context to validate signatures.
174 : Production call sites should leave this disabled. */
175 : void
176 : fd_fec_resolver_set_bypass_verify( fd_fec_resolver_t * resolver,
177 : int bypass_verify );
178 :
179 : /* fd_fec_resolver_set_discard_unexpected_data_complete_shreds updates
180 : the activation slot used by the FEC resolver for the
181 : discard_unexpected_data_complete_shreds feature. */
182 : void
183 : fd_fec_resolver_set_discard_unexpected_data_complete_shreds( fd_fec_resolver_t * resolver,
184 : ulong activation_slot );
185 :
186 : /* fd_fec_resolver_advance_slot_old advances slot_old, discarding any
187 : in progress FEC sets with a slot strictly less than slot_old.
188 : Additionally, causes the FEC resolver to ignore any future shreds
189 : with a slot older than the new value of slot_old. slot_old increases
190 : monotonically, which means that a call to advance_slot_old with a
191 : lower value of slot_old is a no-op. */
192 : void
193 : fd_fec_resolver_advance_slot_old( fd_fec_resolver_t * resolver,
194 : ulong slot_old );
195 :
196 :
197 : /* Keep in sync with metrics.xml */
198 0 : #define FD_FEC_RESOLVER_SHRED_EQUIVOC (-4)
199 108 : #define FD_FEC_RESOLVER_SHRED_REJECTED (-3)
200 654 : #define FD_FEC_RESOLVER_SHRED_IGNORED (-2)
201 249 : #define FD_FEC_RESOLVER_SHRED_DUPLICATE (-1)
202 7194 : #define FD_FEC_RESOLVER_SHRED_OKAY ( 0)
203 219 : #define FD_FEC_RESOLVER_SHRED_COMPLETES ( 1)
204 :
205 : /* Return values + RETVAL_OFF are in [0, RETVAL_CNT) */
206 : #define FD_FEC_RESOLVER_ADD_SHRED_RETVAL_CNT 6
207 0 : #define FD_FEC_RESOLVER_ADD_SHRED_RETVAL_OFF 4
208 :
209 : struct fd_fec_resolver_spilled {
210 : ulong slot;
211 : uint fec_set_idx;
212 : fd_bmtree_node_t merkle_root[1];
213 : };
214 : typedef struct fd_fec_resolver_spilled fd_fec_resolver_spilled_t;
215 :
216 : /* fd_fec_resolver_add_shred notifies the FEC resolver of a newly
217 : received shred. The FEC resolver validates the shred and copies it
218 : into its own storage. resolver is a local join of an FEC resolver.
219 : shred is a pointer to the new shred that should be added. The shred
220 : must have passed the shred parsing validation. shred_sz is the size
221 : of the shred in bytes. max_shred_idx is the exclusive upper
222 : bound for shred indices in shred->slot (it changes with the
223 : reduce_slot_time feature gates, SIMD-525): the FEC resolver
224 : rejects any shred with an index >= max_shred_idx, or that is part
225 : of an FEC set whose highest shred index would reach the bound. If
226 : is_repair is non-zero, some validity checks will be omitted, as
227 : detailed below. leader_pubkey must be a pointer to the first byte
228 : of the public identity key of the validator that was leader during
229 : slot shred->slot.
230 :
231 : On success ie. SHRED_{OKAY,COMPLETES}, a pointer to a copy of shred
232 : will be written to the location pointed to by out_shred.
233 : Additionally, on SHRED_COMPLETES a pointer to the fd_fec_set_t
234 : structure representing the FEC set of which the shred is a part will
235 : be written to out_fec_set. See the long explanation above about the
236 : lifetimes of these pointers. Finally, on success the merkle root of
237 : the shred (reconstructed from the merkle proof) will be written to
238 : out_merkle_root. Unlike out_{fec_set,shred}, caller owns and
239 : provides the memory for out_merkle_root. If the out_merkle_root
240 : pointer is NULL, the argument will be ignored and merkle root will
241 : not be written.
242 :
243 : If the shred is validly signed but has a Merkle root that differs
244 : from the Merkle root of a previously received shred with the same
245 : values for slot and FEC index, and is_repair is zero, the shred may
246 : be rejected with return value SHRED_EQUIVOC. In general (other than
247 : if done_depth is too small), the FEC resolver will return
248 : SHRED_EQUIVOC for the first equivocating shred with that slot and FEC
249 : index and SHRED_IGNORED for any subsequent ones. Additionally, the
250 : FEC resolver has a limited memory and uses a probabilistic scheme
251 : with (per-validator independent) probability 2^-31 of returning
252 : SHRED_IGNORED instead of SHRED_EQUIVOC, which is why equivocation
253 : detection cannot be guaranteed. Note that these checks are bypassed
254 : if is_repair is non-zero. Similar to SHRED_{OKAY,COMPLETES},
255 : out_merkle_root will be populated on SHRED_EQUIVOC if non-NULL. Note
256 : that there are forms of equivocation not covered by this strict
257 : check.
258 :
259 : If the shred has the same slot, shred index, and signature as a shred
260 : that has already been successfully completed in a FEC by the FEC
261 : resolver, or if the shred is for a slot older than slot_old, returns
262 : SHRED_IGNORED and does not write to out_{fec_set,shred,merkle_root}.
263 : Note that "successfully completed in a FEC by the FEC resolver" above
264 : includes shreds that are reconstructed when returning
265 : SHRED_COMPLETES, so for example, after returning SHRED_COMPLETES for
266 : a FEC set, adding any shred for that FEC set will return
267 : SHRED_IGNORED, even if that particular shred hadn't been received.
268 :
269 : However, if the shred is part of an in progress FEC set but has
270 : already been received, FEC resolver returns SHRED_DUPLICATE and
271 : populates out_merkle_root if it is non-NULL. out_shred will be
272 : populated similarly to when returning SHRED_OKAY.
273 :
274 : If the shred fails validation for any other reason, returns
275 : SHRED_REJECTED and does not write to out_{fec_set,shred}. If
276 : non-NULL, the contents pointed to by out_merkle_root may be
277 : clobbered.
278 :
279 : Note that only light validation is performed when returning
280 : SHRED_IGNORED, so a shred that is actually invalid but meets the
281 : criteria for SHRED_IGNORED may be considered SHRED_IGNORED instead of
282 : SHRED_REJECTED.
283 :
284 : This function returns SHRED_COMPLETES when the received shred
285 : completes the FEC set. In this case, the function populates any
286 : missing shreds in the FEC set stored in out_fec_set.
287 :
288 : Regardless of success/failure, if an in progress FEC set was evicted
289 : from the current map during this add_shred call, and the
290 : out_spilled_fec_set pointer is not NULL, the metadata of the evicted
291 : FEC set will be written to out_spilled_fec_set. The FEC set metadata
292 : consists of the slot, FEC set index, and the Merkle root of the
293 : evicted FEC set. Similar to out_merkle_root, the caller owns and
294 : provides the memory for out_spilled_fec_set. If
295 : out_spilled_fec_set is NULL, the evicted FEC set metadata will not be
296 : written even if an in progress FEC set was evicted. */
297 :
298 : int
299 : fd_fec_resolver_add_shred( fd_fec_resolver_t * resolver,
300 : fd_shred_t const * shred,
301 : ulong shred_sz,
302 : ulong max_shred_idx,
303 : int is_repair,
304 : uchar const * leader_pubkey,
305 : fd_fec_set_t const * * out_fec_set,
306 : fd_shred_t const * * out_shred,
307 : fd_bmtree_node_t * out_merkle_root,
308 : fd_fec_resolver_spilled_t * out_spilled_fec_set );
309 :
310 :
311 : void * fd_fec_resolver_leave( fd_fec_resolver_t * resolver );
312 : void * fd_fec_resolver_delete( void * shmem );
313 :
314 : FD_PROTOTYPES_END
315 : #endif /* HEADER_fd_src_disco_shred_fd_fec_resolver_h */
|
