Line data Source code
1 : #ifndef HEADER_fd_src_discof_repair_fd_fec_chainer_h
2 : #define HEADER_fd_src_discof_repair_fd_fec_chainer_h
3 :
4 : /* FEC chainer is an API for "chaining" FEC sets as they are received
5 : asynchronously out-of-order over the network (via Turbine and
6 : Repair). The chainer both validates and reorders those FEC sets, and
7 : delivers them in-order to the calling application.
8 :
9 : Every FEC set has a parent (the immediately preceding FEC set in the
10 : slot or parent slot) and children (immediately succeeding FEC set(s)
11 : for the same slot or child slots). Because of forks, FEC sets can
12 : have multiple children, but this will only be true across slots (ie.
13 : the parent and child must be different slots). The chainer treats
14 : forks as "concurrent" with no particular order, so the calling
15 : application will receive forking FEC sets in the order in which the
16 : chainer is able to chain them.
17 :
18 : There is a protocol violation called equivocation (also known as
19 : "duplicates") that breaks the invariant that forks must be across
20 : slots. For example, equivocation can result in observing two or more
21 : child FEC sets for a given parent FEC set in the same slot.
22 : Equivocation can also result in other anomalies such as keying
23 : collisions (this is detailed later in the documentation). The
24 : chainer makes a best-effort attempt to detect and error on
25 : equivocation. Examples include checking merkle roots chain correctly
26 : and checking FEC sets are unique. Not all cases of equivocation can
27 : be detected by the chainer however, as not all the necessary
28 : information is yet available at this stage in the validator pipeline.
29 : Ultimately, if there is equivocation, it is the responsibility of the
30 : consensus module to handle it. */
31 :
32 : #include "../../ballet/shred/fd_shred.h"
33 :
34 : /* FD_FEC_CHAINER_USE_HANDHOLDING: Define this to non-zero at compile time
35 : to turn on additional runtime checks and logging. */
36 :
37 : #ifndef FD_FEC_CHAINER_USE_HANDHOLDING
38 : #define FD_FEC_CHAINER_USE_HANDHOLDING 1
39 : #endif
40 :
41 0 : #define FD_FEC_CHAINER_SUCCESS ( 0)
42 0 : #define FD_FEC_CHAINER_ERR_UNIQUE (-1) /* key uniqueness conflict */
43 0 : #define FD_FEC_CHAINER_ERR_MERKLE (-2) /* chained merkle root conflict */
44 :
45 : /* fd_fec_chainer is a tree-like structure backed by three maps. At any
46 : given point in time, an element (FEC set) in the chainer is in one of
47 : three possible positions with respect to the tree: a non-leaf, leaf,
48 : or not connected. This corresponds to the ancestry, frontier, or
49 : orphaned maps, respectively. Therefore, a given element will always
50 : be present in exactly one of these maps, depending on where (and
51 : whether) it currently is in the tree.
52 :
53 : KEYING
54 :
55 : The chainer keys FEC sets by concatenating the slot with fec_set_idx.
56 : This uniquely identifies a FEC set in most cases. It is possible to
57 : receive over the network two or more different FEC sets with the same
58 : slot and fec_set_idx due to equivocation as mentioned earlier. In
59 : general, the chainer expects the caller to handle equivocation and
60 : assumes unique FEC sets will have unique keys (handholding is
61 : available to verify this).
62 :
63 : The map key is an encoding of the slot and fec_set_idx which uniquely
64 : keys every FEC set. The 32 msb of the key are the 32 lsb of the slot
65 : and the 32 lsb of the key are the fec_set_idx, except when the FEC
66 : set is the last one for the slot, in which case the 32 lsb are set to
67 : UINT_MAX. By setting fec_set_idx to UINT_MAX, the chainer can easily
68 : query for the last FEC set in any given slot
69 :
70 : A useful property of the keying scheme above is a FEC set can infer
71 : the key of its immediate child by adding data_cnt to its fec_set_idx.
72 : For example, a FEC set for slot 0, fec_set_idx 0, data_cnt 32 knows
73 : its child key is slot 0, fec_set_idx 32. The last FEC set in the slot
74 : is special because the child(s) FEC set will have a different slot
75 : number, so we know the fec_set_idx will be zero.
76 :
77 : There is one exception to this keying scheme. When the FEC set is
78 : the last one in the slot, an extra insertion to the parent_map is
79 : done. In the standard procedure, the second to last fec will create
80 : the (n-1, n) entry, and the following child slot will create a
81 : (UINT_MAX, 0) entry. Thus we insert an extra entry (n, UINT_MAX) in
82 : the parent_map to connect the chain. This double insertion is only
83 : done for the parent_map - the pool_ele will have an element with key
84 : slot | fec_set_idx, not UINT_MAX.
85 :
86 : Visually, the parent_map / elements looks like this:
87 :
88 : - Arrows denote a child->parent entry in the parent_map.
89 :
90 : parent_map | pool_ele (slot, fec_set_idx, completes)
91 : ──────────────────────────────────────────────────────────────────────────────────────────────────
92 : (slot, 0) | (slot, 0, 0)
93 : ▲ |
94 : | |
95 : (slot, 32) | (slot, 32, 0)
96 : ▲ |
97 : | |
98 : (slot, 64) <-- (slot, UINT_MAX) | (slot, 64, 1)
99 : ▲ |
100 : | |
101 : (slot + 1, 0) | (slot + 1, 0, 0)
102 : ▲ |
103 : | |
104 : (slot + 1, 32) | (slot + 1, 32, 0)
105 : ▲ |
106 : | |
107 : (slot + 1, 64) ◄── (slot + 1, UINT_MAX) | (slot + 1, 64, 1)
108 : ▲ |
109 : | ... |
110 :
111 : Thus we will have double entries for the last FEC set in a slot in
112 : the parent map, but only one entry in the ancestry/orphan/frontier
113 : pool. This means if we want to query for the last FEC set in a slot,
114 : we need to query the parent_map twice - once with the fec_set_idx set
115 : to UINT_MAX and once with the parent_key of the result.
116 :
117 : INSERTING
118 :
119 : When inserting a new FEC set, the chainer first checks whether the
120 : parent is a FEC set already in the frontier map. This indicates that
121 : the new FEC set directly chains off the frontier. If it does, the
122 : parent FEC set is removed, and the new FEC set is inserted into the
123 : frontier map. This is the common case because we expect FEC sets to
124 : chain linearly the vast majority (ie. not start new forks), so the
125 : new FEC set is simply "advancing" the frontier. The parent FEC set
126 : is also added to the ancestry map, so that every leaf can trace back
127 : to the root.
128 :
129 : If the FEC set's parent is not already in the frontier, the chainer
130 : checks the ancestry map next. If the parent is in the ancestry map,
131 : the chainer knows that this FEC set is starting a new fork, because
132 : it is part of the tree (the ancestry) but not one of the leaves (the
133 : frontier). In this case, the new FEC set is simply inserted into the
134 : frontier map, and now the frontier has an additional fork (leaf).
135 :
136 : Lastly, if the FEC set's parent is not in the ancestry map, the
137 : chainer knows that this FEC set is orphaned. It is inserted into the
138 : orphaned map for later retry of tree insertion when its ancestors
139 : have been inserted.
140 :
141 : Here are some more important details on forks. Note a FEC set can
142 : only start a new fork when it is across a slot boundary (different
143 : slot than its parent). It is invalid for two FEC sets to chain off
144 : the same parent FEC within the same slot - this would imply there are
145 : two FECs keyed by the (same slot, fec_set_idx) combination, which as
146 : detailed earlier, is equivocation. Therefore, only the first FEC set
147 : in a slot can start a fork from the last FEC set in a parent slot. We
148 : know a FEC set is the first one in a slot when the fec_set_idx is 0,
149 : and we know it is the last one when the last shred in the FEC set has
150 : the SLOT_COMPLETE flag set.
151 :
152 : QUERYING
153 :
154 : The chainer can fast O(1) query any FEC set using the key. As
155 : mentioned earlier, any FEC set except the last one in a slot can
156 : derive its direct child's key and therefore query for it.
157 :
158 : For the special case of the first FEC set in a slot, the chainer can
159 : derive the parent key by subtracting the parent_off from the slot and
160 : querying for (slot, UINT_MAX).
161 :
162 : CHAINING
163 :
164 : As mentioned in the top-level documentation, the purpose of the
165 : chainer is to chain FEC sets. On insertion, the chainer will attempt
166 : to chain as many FEC sets as possible to the frontier. The chainer
167 : does this by conducting a BFS from the just-inserted FEC set, looking
168 : for parents and orphans to traverse. See `chain` in the .c file for
169 : the implementation. */
170 :
171 : typedef struct fd_fec_chainer fd_fec_chainer_t; /* forward decl */
172 :
173 : struct fd_fec_ele {
174 : ulong key; /* map key */
175 : ulong next; /* reserved for use by fd_pool and fd_map_chain */
176 :
177 : ulong slot;
178 : uint fec_set_idx;
179 : ushort data_cnt;
180 : int data_complete;
181 : int slot_complete;
182 : ushort parent_off;
183 : uchar merkle_root[FD_SHRED_MERKLE_ROOT_SZ];
184 : uchar chained_merkle_root[FD_SHRED_MERKLE_ROOT_SZ];
185 : };
186 : typedef struct fd_fec_ele fd_fec_ele_t;
187 :
188 : #define POOL_NAME fd_fec_pool
189 0 : #define POOL_T fd_fec_ele_t
190 : #include "../../util/tmpl/fd_pool.c"
191 :
192 : #define MAP_NAME fd_fec_ancestry
193 : #define MAP_ELE_T fd_fec_ele_t
194 : #include "../../util/tmpl/fd_map_chain.c"
195 :
196 : #define MAP_NAME fd_fec_frontier
197 : #define MAP_ELE_T fd_fec_ele_t
198 : #include "../../util/tmpl/fd_map_chain.c"
199 :
200 : #define MAP_NAME fd_fec_orphaned
201 : #define MAP_ELE_T fd_fec_ele_t
202 : #include "../../util/tmpl/fd_map_chain.c"
203 :
204 : struct fd_fec_parent {
205 : ulong key;
206 : ulong parent_key;
207 : };
208 : typedef struct fd_fec_parent fd_fec_parent_t;
209 :
210 : /* There are no FEC sets for the genesis block, so (0, 0) represents the
211 : NULL map key. */
212 :
213 : #define MAP_NAME fd_fec_parents
214 0 : #define MAP_T fd_fec_parent_t
215 : #define MAP_MEMOIZE 0
216 : #include "../../util/tmpl/fd_map_dynamic.c"
217 :
218 : #define FD_FEC_CHILDREN_MAX (64) /* TODO size this more reasonably */
219 : FD_STATIC_ASSERT( FD_FEC_CHILDREN_MAX % 64 == 0, FD_FEC_CHILDREN_MAX must be a multiple of 64 bits per word );
220 :
221 : #define SET_NAME fd_slot_child_offs
222 : #define SET_MAX FD_FEC_CHILDREN_MAX
223 : #include "../../util/tmpl/fd_set.c"
224 :
225 : /* FIXME consider alternate pooled tree-like representation eg. fd_ghost
226 : maybe the ghost generic in tmpl? */
227 :
228 : struct fd_fec_children {
229 : ulong slot;
230 : fd_slot_child_offs_t child_offs[FD_FEC_CHILDREN_MAX / 64];
231 : };
232 : typedef struct fd_fec_children fd_fec_children_t;
233 :
234 : #define MAP_NAME fd_fec_children
235 0 : #define MAP_T fd_fec_children_t
236 0 : #define MAP_KEY slot
237 : #define MAP_MEMOIZE 0
238 : #include "../../util/tmpl/fd_map_dynamic.c"
239 :
240 : #define DEQUE_NAME fd_fec_queue
241 0 : #define DEQUE_T ulong
242 : #include "../../util/tmpl/fd_deque_dynamic.c"
243 :
244 : struct fd_fec_out {
245 : ulong slot;
246 : ushort parent_off;
247 : uint fec_set_idx;
248 : ushort data_cnt;
249 : int data_complete;
250 : int slot_complete;
251 : int err;
252 : };
253 : typedef struct fd_fec_out fd_fec_out_t;
254 :
255 : #define DEQUE_NAME fd_fec_out
256 0 : #define DEQUE_T fd_fec_out_t
257 : #include "../../util/tmpl/fd_deque_dynamic.c"
258 :
259 : /* TODO deque probably not needed if reuse ele->next. */
260 :
261 : struct __attribute__((aligned(128UL))) fd_fec_chainer {
262 : fd_fec_ancestry_t * ancestry; /* map of key->fec. non-leaves of FEC tree */
263 : fd_fec_frontier_t * frontier; /* map of key->fec. leaves */
264 : fd_fec_orphaned_t * orphaned; /* map of key->fec. FECs not yet inserted to tree */
265 : fd_fec_ele_t * pool; /* pool of FEC nodes backing the above maps / tree */
266 : fd_fec_parent_t * parents; /* map of key->parent_key for fast O(1) querying */
267 : fd_fec_children_t * children; /* map of slot->child_offs for fast O(1) querying */
268 : ulong * queue; /* queue of FEC keys for BFS chaining */
269 : fd_fec_out_t * out; /* queue of FEC keys to deliver to application */
270 : };
271 :
272 : FD_PROTOTYPES_BEGIN
273 :
274 : /* Constructors */
275 :
276 : /* fd_fec_chainer_{align,footprint} return the required alignment and
277 : footprint of a memory region suitable for use as chainer with up to
278 : fec_max elements and slot_max slots. */
279 :
280 : FD_FN_CONST static inline ulong
281 0 : fd_fec_chainer_align( void ) {
282 0 : return alignof(fd_fec_chainer_t);
283 0 : }
284 :
285 : FD_FN_CONST static inline ulong
286 0 : fd_fec_chainer_footprint( ulong fec_max ) {
287 0 : int lg_fec_max = fd_ulong_find_msb( fd_ulong_pow2_up( fec_max ) );
288 0 : return FD_LAYOUT_FINI(
289 0 : FD_LAYOUT_APPEND(
290 0 : FD_LAYOUT_APPEND(
291 0 : FD_LAYOUT_APPEND(
292 0 : FD_LAYOUT_APPEND(
293 0 : FD_LAYOUT_APPEND(
294 0 : FD_LAYOUT_APPEND(
295 0 : FD_LAYOUT_APPEND(
296 0 : FD_LAYOUT_APPEND(
297 0 : FD_LAYOUT_APPEND(
298 0 : FD_LAYOUT_INIT,
299 0 : alignof(fd_fec_chainer_t), sizeof(fd_fec_chainer_t) ),
300 0 : fd_fec_ancestry_align(), fd_fec_ancestry_footprint( fec_max ) ),
301 0 : fd_fec_frontier_align(), fd_fec_frontier_footprint( fec_max ) ),
302 0 : fd_fec_orphaned_align(), fd_fec_orphaned_footprint( fec_max ) ),
303 0 : fd_fec_pool_align(), fd_fec_pool_footprint( fec_max ) ),
304 0 : fd_fec_parents_align(), fd_fec_parents_footprint( lg_fec_max ) ),
305 0 : fd_fec_children_align(), fd_fec_children_footprint( lg_fec_max ) ),
306 0 : fd_fec_queue_align(), fd_fec_queue_footprint( fec_max ) ),
307 0 : fd_fec_out_align(), fd_fec_out_footprint( fec_max ) ),
308 0 : fd_fec_chainer_align() );
309 0 : }
310 :
311 : /* fd_fec_chainer_new formats an unused memory region for use as a
312 : chainer. mem is a non-NULL pointer to this region in the local
313 : address space with the required footprint and alignment. */
314 :
315 : void *
316 : fd_fec_chainer_new( void * shmem, ulong fec_max, ulong seed );
317 :
318 : /* fd_fec_chainer_join joins the caller to the chainer. chainer points
319 : to the first byte of the memory region backing the chainer in the
320 : caller's address space.
321 :
322 : Returns a pointer in the local address space to chainer on
323 : success. */
324 :
325 : fd_fec_chainer_t *
326 : fd_fec_chainer_join( void * chainer );
327 :
328 : /* fd_fec_chainer_leave leaves a current local join. Returns a pointer
329 : to the underlying shared memory region on success and NULL on failure
330 : (logs details). Reasons for failure include chainer is NULL. */
331 :
332 : void *
333 : fd_fec_chainer_leave( fd_fec_chainer_t * chainer );
334 :
335 : /* fd_fec_chainer_delete unformats a memory region used as a chainer.
336 : Assumes only the nobody is joined to the region. Returns a pointer
337 : to the underlying shared memory region or NULL if used obviously in
338 : error (e.g. chainer is obviously not a chainer ... logs details).
339 : The ownership of the memory region is transferred to the caller. */
340 :
341 : void *
342 : fd_fec_chainer_delete( void * chainer );
343 :
344 : fd_fec_ele_t *
345 : fd_fec_chainer_init( fd_fec_chainer_t * chainer, ulong slot, uchar merkle_root[static FD_SHRED_MERKLE_ROOT_SZ] );
346 :
347 : FD_FN_PURE fd_fec_ele_t *
348 : fd_fec_chainer_query( fd_fec_chainer_t * chainer, ulong slot, uint fec_set_idx );
349 :
350 : /* fd_fec_chainer inserts a new FEC set into chainer. Returns the newly
351 : inserted fd_fec_ele_t, NULL on error. Inserting this FEC set may
352 : result in one or more FEC sets being ready for in-order delivery.
353 : Caller can consume these FEC sets via the deque in chainer->out.
354 :
355 : See top-level documentation for further details on insertion. */
356 :
357 : fd_fec_ele_t *
358 : fd_fec_chainer_insert( fd_fec_chainer_t * chainer,
359 : ulong slot,
360 : uint fec_set_idx,
361 : ushort data_cnt,
362 : int data_complete,
363 : int slot_complete,
364 : ushort parent_off,
365 : uchar const merkle_root[static FD_SHRED_MERKLE_ROOT_SZ],
366 : uchar const chained_merkle_root[static FD_SHRED_MERKLE_ROOT_SZ] );
367 :
368 : FD_PROTOTYPES_END
369 :
370 : #endif /* HEADER_fd_src_discof_repair_fd_fec_chainer_h */
|
