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