Line data Source code
1 : #include "fd_reasm.h"
2 : #include "fd_reasm_private.h"
3 :
4 : #define LOGGING 0
5 :
6 : FD_FN_CONST ulong
7 24 : fd_reasm_align( void ) {
8 24 : return alignof(fd_reasm_t);
9 24 : }
10 :
11 : FD_FN_CONST ulong
12 6 : fd_reasm_footprint( ulong fec_max ) {
13 6 : int lgf_max = fd_ulong_find_msb( fd_ulong_pow2_up( fec_max ) );
14 6 : return FD_LAYOUT_FINI(
15 6 : FD_LAYOUT_APPEND(
16 6 : FD_LAYOUT_APPEND(
17 6 : FD_LAYOUT_APPEND(
18 6 : FD_LAYOUT_APPEND(
19 6 : FD_LAYOUT_APPEND(
20 6 : FD_LAYOUT_APPEND(
21 6 : FD_LAYOUT_APPEND(
22 6 : FD_LAYOUT_APPEND(
23 6 : FD_LAYOUT_APPEND(
24 6 : FD_LAYOUT_APPEND(
25 6 : FD_LAYOUT_INIT,
26 6 : alignof(fd_reasm_t), sizeof(fd_reasm_t) ),
27 6 : pool_align(), pool_footprint ( fec_max ) ),
28 6 : ancestry_align(), ancestry_footprint( fec_max ) ),
29 6 : frontier_align(), frontier_footprint( fec_max ) ),
30 6 : orphaned_align(), orphaned_footprint( fec_max ) ),
31 6 : subtrees_align(), subtrees_footprint( fec_max ) ),
32 6 : bfs_align(), bfs_footprint ( fec_max ) ),
33 6 : out_align(), out_footprint ( fec_max ) ),
34 6 : bid_align(), bid_footprint ( lgf_max ) ),
35 6 : xid_align(), xid_footprint ( lgf_max ) ),
36 6 : fd_reasm_align() );
37 6 : }
38 :
39 : void *
40 : fd_reasm_new( void * shmem,
41 : ulong fec_max,
42 3 : ulong seed ) {
43 :
44 3 : if( FD_UNLIKELY( !shmem ) ) {
45 0 : FD_LOG_WARNING(( "NULL mem" ));
46 0 : return NULL;
47 0 : }
48 :
49 3 : if( FD_UNLIKELY( !fd_ulong_is_aligned( (ulong)shmem, fd_reasm_align() ) ) ) {
50 0 : FD_LOG_WARNING(( "misaligned mem" ));
51 0 : return NULL;
52 0 : }
53 :
54 3 : ulong footprint = fd_reasm_footprint( fec_max );
55 3 : if( FD_UNLIKELY( !footprint ) ) {
56 0 : FD_LOG_WARNING(( "bad fec_max (%lu)", fec_max ));
57 0 : return NULL;
58 0 : }
59 :
60 3 : fd_wksp_t * wksp = fd_wksp_containing( shmem );
61 3 : if( FD_UNLIKELY( !wksp ) ) {
62 0 : FD_LOG_WARNING(( "shmem must be part of a workspace" ));
63 0 : return NULL;
64 0 : }
65 :
66 3 : fd_memset( shmem, 0, footprint );
67 :
68 3 : int lgf_max = fd_ulong_find_msb( fd_ulong_pow2_up( fec_max ) );
69 :
70 3 : fd_reasm_t * reasm;
71 3 : FD_SCRATCH_ALLOC_INIT( l, shmem );
72 3 : reasm = FD_SCRATCH_ALLOC_APPEND( l, alignof(fd_reasm_t), sizeof(fd_reasm_t) );
73 3 : void * pool = FD_SCRATCH_ALLOC_APPEND( l, pool_align(), pool_footprint ( fec_max ) );
74 3 : void * ancestry = FD_SCRATCH_ALLOC_APPEND( l, ancestry_align(), ancestry_footprint( fec_max ) );
75 3 : void * frontier = FD_SCRATCH_ALLOC_APPEND( l, frontier_align(), frontier_footprint( fec_max ) );
76 3 : void * orphaned = FD_SCRATCH_ALLOC_APPEND( l, orphaned_align(), orphaned_footprint( fec_max ) );
77 3 : void * subtrees = FD_SCRATCH_ALLOC_APPEND( l, subtrees_align(), subtrees_footprint( fec_max ) );
78 3 : void * bfs = FD_SCRATCH_ALLOC_APPEND( l, bfs_align(), bfs_footprint ( fec_max ) );
79 3 : void * out = FD_SCRATCH_ALLOC_APPEND( l, out_align(), out_footprint ( fec_max ) );
80 3 : void * bid = FD_SCRATCH_ALLOC_APPEND( l, bid_align(), bid_footprint ( lgf_max ) );
81 3 : void * xid = FD_SCRATCH_ALLOC_APPEND( l, xid_align(), xid_footprint ( lgf_max ) );
82 3 : FD_TEST( FD_SCRATCH_ALLOC_FINI( l, fd_reasm_align() ) == (ulong)shmem + footprint );
83 :
84 3 : reasm->slot0 = ULONG_MAX;
85 3 : reasm->root = pool_idx_null( pool );
86 3 : reasm->pool_gaddr = fd_wksp_gaddr_fast( wksp, pool_join( pool_new( pool, fec_max ) ) );
87 3 : reasm->ancestry = ancestry_new( ancestry, fec_max, seed );
88 3 : reasm->frontier = frontier_new( frontier, fec_max, seed );
89 3 : reasm->orphaned = orphaned_new( orphaned, fec_max, seed );
90 3 : reasm->subtrees = subtrees_new( subtrees, fec_max, seed );
91 3 : /* */ dlist_new ( reasm->_subtrlf );
92 3 : reasm->bfs = bfs_new ( bfs, fec_max );
93 3 : reasm->out = out_new ( out, fec_max );
94 3 : reasm->bid = bid_new ( bid, lgf_max, seed );
95 3 : reasm->xid = xid_new ( xid, lgf_max, seed );
96 :
97 3 : return shmem;
98 3 : }
99 :
100 : fd_reasm_t *
101 3 : fd_reasm_join( void * shreasm ) {
102 3 : fd_reasm_t * reasm = (fd_reasm_t *)shreasm;
103 :
104 3 : if( FD_UNLIKELY( !reasm ) ) {
105 0 : FD_LOG_WARNING(( "NULL reasm" ));
106 0 : return NULL;
107 0 : }
108 : /* pool join handled in fd_reasm_new */
109 3 : reasm->ancestry = ancestry_join( reasm->ancestry );
110 3 : reasm->frontier = frontier_join( reasm->frontier );
111 3 : reasm->orphaned = orphaned_join( reasm->orphaned );
112 3 : reasm->subtrees = subtrees_join( reasm->subtrees );
113 3 : reasm->subtreel = dlist_join ( reasm->_subtrlf );
114 3 : reasm->bfs = bfs_join ( reasm->bfs );
115 3 : reasm->out = out_join ( reasm->out );
116 3 : reasm->bid = bid_join ( reasm->bid );
117 3 : reasm->xid = xid_join ( reasm->xid );
118 :
119 3 : return reasm;
120 3 : }
121 :
122 : void *
123 0 : fd_reasm_leave( fd_reasm_t * reasm ) {
124 :
125 0 : if( FD_UNLIKELY( !reasm ) ) {
126 0 : FD_LOG_WARNING(( "NULL reasm" ));
127 0 : return NULL;
128 0 : }
129 :
130 0 : return (void *)reasm;
131 0 : }
132 :
133 : void *
134 0 : fd_reasm_delete( void * shreasm ) {
135 0 : fd_reasm_t * reasm = (fd_reasm_t *)shreasm;
136 :
137 0 : if( FD_UNLIKELY( !reasm ) ) {
138 0 : FD_LOG_WARNING(( "NULL reasm" ));
139 0 : return NULL;
140 0 : }
141 :
142 0 : if( FD_UNLIKELY( !fd_ulong_is_aligned((ulong)reasm, fd_reasm_align() ) ) ) {
143 0 : FD_LOG_WARNING(( "misaligned reasm" ));
144 0 : return NULL;
145 0 : }
146 :
147 0 : return reasm;
148 0 : }
149 :
150 0 : fd_reasm_fec_t * fd_reasm_root ( fd_reasm_t * reasm ) { return pool_ele ( reasm_pool ( reasm ), reasm->root ); }
151 3 : fd_reasm_fec_t const * fd_reasm_root_const ( fd_reasm_t const * reasm ) { return pool_ele_const( reasm_pool_const( reasm ), reasm->root ); }
152 9 : fd_reasm_fec_t * fd_reasm_parent ( fd_reasm_t * reasm, fd_reasm_fec_t * child ) { return pool_ele ( reasm_pool ( reasm ), child->parent ); }
153 0 : fd_reasm_fec_t const * fd_reasm_parent_const ( fd_reasm_t const * reasm, fd_reasm_fec_t const * child ) { return pool_ele_const( reasm_pool_const( reasm ), child->parent ); }
154 15 : fd_reasm_fec_t * fd_reasm_child ( fd_reasm_t * reasm, fd_reasm_fec_t * parent ) { return pool_ele ( reasm_pool ( reasm ), parent->child ); }
155 21 : fd_reasm_fec_t const * fd_reasm_child_const ( fd_reasm_t const * reasm, fd_reasm_fec_t const * parent ) { return pool_ele_const( reasm_pool_const( reasm ), parent->child ); }
156 6 : fd_reasm_fec_t * fd_reasm_sibling ( fd_reasm_t * reasm, fd_reasm_fec_t * sibling ) { return pool_ele ( reasm_pool ( reasm ), sibling->sibling ); }
157 0 : fd_reasm_fec_t const * fd_reasm_sibling_const( fd_reasm_t const * reasm, fd_reasm_fec_t const * sibling ) { return pool_ele_const( reasm_pool_const( reasm ), sibling->sibling ); }
158 :
159 : ulong
160 0 : fd_reasm_slot0( fd_reasm_t * reasm ) {
161 0 : return reasm->slot0;
162 0 : }
163 :
164 : ulong
165 0 : fd_reasm_free( fd_reasm_t * reasm ) {
166 0 : return pool_free( reasm_pool( reasm ) );
167 0 : }
168 :
169 : fd_reasm_fec_t *
170 0 : fd_reasm_peek( fd_reasm_t * reasm ) {
171 0 : for( out_iter_t iter = out_iter_init( reasm->out );
172 0 : !out_iter_done( reasm->out, iter );
173 0 : iter = out_iter_next( reasm->out, iter ) ) {
174 0 : fd_reasm_fec_t * fec = pool_ele( reasm_pool( reasm ), *out_iter_ele( reasm->out, iter ) );
175 0 : if( FD_LIKELY( !fec->popped && ( !fec->eqvoc || fec->confirmed ) ) ) return fec;
176 0 : }
177 0 : return NULL;
178 0 : }
179 :
180 : fd_reasm_fec_t *
181 0 : fd_reasm_pop( fd_reasm_t * reasm ) {
182 0 : while( FD_LIKELY( !out_empty( reasm->out ) ) ) {
183 0 : fd_reasm_fec_t * fec = pool_ele( reasm_pool( reasm ), out_pop_head( reasm->out ) );
184 0 : if( FD_LIKELY( !fec->popped && ( !fec->eqvoc || fec->confirmed ) ) ) {
185 0 : fec->popped = 1;
186 0 : return fec;
187 0 : }
188 0 : }
189 0 : return NULL;
190 0 : }
191 :
192 : fd_reasm_fec_t *
193 : fd_reasm_query( fd_reasm_t * reasm,
194 93 : fd_hash_t const * merkle_root ) {
195 93 : fd_reasm_fec_t * pool = reasm_pool( reasm );
196 93 : fd_reasm_fec_t * fec = NULL;
197 93 : fec = ancestry_ele_query( reasm->ancestry, merkle_root, NULL, pool );
198 93 : fec = fd_ptr_if( !fec, frontier_ele_query( reasm->frontier, merkle_root, NULL, pool ), fec );
199 93 : fec = fd_ptr_if( !fec, orphaned_ele_query( reasm->orphaned, merkle_root, NULL, pool ), fec );
200 93 : fec = fd_ptr_if( !fec, subtrees_ele_query( reasm->subtrees, merkle_root, NULL, pool ), fec );
201 93 : return fec;
202 93 : }
203 :
204 : void
205 : fd_reasm_confirm( fd_reasm_t * reasm,
206 3 : fd_hash_t * block_id ) {
207 3 : fd_reasm_fec_t * pool = reasm_pool( reasm );
208 3 : fd_reasm_fec_t * fec = ancestry_ele_query( reasm->ancestry, block_id, NULL, pool );
209 3 : fec = fd_ptr_if( !fec, frontier_ele_query( reasm->frontier, block_id, NULL, pool ), fec );
210 :
211 : /* TODO there is a potential optimization where we don't actually need
212 : to confirm every FEC and instead just confirm at the slot-level.
213 : Given roughly ~1k shreds per slot at 32 shreds per FEC, this would
214 : save ~32 loop iterations. Punting given the additional complexity
215 : of bookkeeping and logic this would require. */
216 :
217 12 : while( FD_LIKELY( fec && !fec->confirmed ) ) {
218 9 : fec->confirmed = 1;
219 9 : if( FD_LIKELY( !fec->popped ) ) out_push_head( reasm->out, pool_idx( pool, fec ) );
220 9 : fec = fd_reasm_parent( reasm, fec );
221 9 : }
222 3 : }
223 :
224 : /* This is a gross case reasm needs to handle because Agave currently
225 : does not validate chained merkle roots across slots ie. if a leader
226 : sends a bad chained merkle root on a slot boundary, the cluster
227 : might converge on the leader's block anyways. So we overwrite the
228 : chained merkle root based on the slot and parent_off metadata.
229 : There are two cases: 1. we receive the parent before the child. In
230 : this case we just overwrite the child's CMR. 2. we receive the
231 : child before the parent. In this case every time we receive a new
232 : FEC set we need to check the orphan roots for whether we can link
233 : the orphan to the new FEC via slot metadata, since the chained
234 : merkle root metadata on that orphan root might be wrong. */
235 :
236 : static void
237 : overwrite_invalid_cmr( fd_reasm_t * reasm,
238 39 : fd_reasm_fec_t * child ) {
239 39 : fd_reasm_fec_t * pool = reasm_pool( reasm );
240 39 : if( FD_UNLIKELY( child->fec_set_idx==0 && !fd_reasm_query( reasm, &child->cmr ) ) ) {
241 21 : bid_t * parent_bid = bid_query( reasm->bid, child->slot - child->parent_off, NULL );
242 21 : if( FD_LIKELY( parent_bid ) ) {
243 0 : fd_reasm_fec_t * parent = pool_ele( pool, parent_bid->idx );
244 0 : if( FD_LIKELY( parent ) ) {
245 0 : FD_BASE58_ENCODE_32_BYTES( child->cmr.key, cmr_b58 );
246 0 : FD_BASE58_ENCODE_32_BYTES( parent->key.key, parent_key_b58 );
247 0 : FD_LOG_INFO(( "overwriting invalid cmr for FEC slot: %lu fec_set_idx: %u from %s (CMR) to %s (parent's block id)", child->slot, child->fec_set_idx, cmr_b58, parent_key_b58 ));
248 0 : child->cmr = parent->key; /* use the parent's merkle root */
249 0 : }
250 0 : }
251 21 : }
252 39 : }
253 :
254 : /* Mark the entire subtree beginning from root as equivocating. This is
255 : linear in the number of descendants in the subtree, but amortizes
256 : because we can short-circuit the BFS at nodes that are already marked
257 : equivocating, so each node is visited at most once. */
258 :
259 : static void
260 : eqvoc( fd_reasm_t * reasm,
261 9 : fd_reasm_fec_t * root ) {
262 9 : fd_reasm_fec_t * pool = reasm_pool( reasm );
263 9 : ulong * bfs = reasm->bfs;
264 9 : bfs_push_tail( bfs, pool_idx( pool, root ) );
265 24 : while( FD_LIKELY( !bfs_empty( bfs ) ) ) {
266 15 : fd_reasm_fec_t * descendant = pool_ele( pool, bfs_pop_head( bfs ) );
267 15 : if( FD_LIKELY( descendant->eqvoc ) ) continue;
268 15 : descendant->eqvoc = 1;
269 15 : fd_reasm_fec_t * child = fd_reasm_child( reasm, descendant );
270 21 : while( FD_LIKELY( child ) ) {
271 6 : bfs_push_tail( bfs, pool_idx( pool, child ) );
272 6 : child = fd_reasm_sibling( reasm, child );
273 6 : }
274 15 : }
275 9 : }
276 :
277 : static void
278 : link( fd_reasm_t * reasm,
279 : fd_reasm_fec_t * parent,
280 18 : fd_reasm_fec_t * child ) {
281 18 : fd_reasm_fec_t * pool = reasm_pool( reasm );
282 18 : child->parent = pool_idx( pool, parent );
283 18 : if( FD_LIKELY( parent->child == pool_idx_null( pool ) ) ) {
284 12 : parent->child = pool_idx( pool, child ); /* set as left-child. */
285 12 : } else {
286 6 : fd_reasm_fec_t * sibling = pool_ele( pool, parent->child );
287 6 : while( FD_LIKELY( sibling->sibling != pool_idx_null( pool ) ) ) sibling = pool_ele( pool, sibling->sibling );
288 6 : sibling->sibling = pool_idx( pool, child ); /* set as right-sibling. */
289 6 : }
290 18 : }
291 :
292 : fd_reasm_fec_t *
293 : fd_reasm_insert( fd_reasm_t * reasm,
294 : fd_hash_t const * merkle_root,
295 : fd_hash_t const * chained_merkle_root,
296 : ulong slot,
297 : uint fec_set_idx,
298 : ushort parent_off,
299 : ushort data_cnt,
300 : int data_complete,
301 : int slot_complete,
302 21 : int is_leader ) {
303 :
304 : # if LOGGING
305 : FD_BASE58_ENCODE_32_BYTES( merkle_root->key, merkle_root_b58 );
306 : FD_BASE58_ENCODE_32_BYTES( chained_merkle_root->key, chained_merkle_root_b58 );
307 : FD_LOG_NOTICE(( "inserting (%lu %u) %s %s. %u %d %d", slot, fec_set_idx, merkle_root_b58, chained_merkle_root_b58, data_cnt, data_complete, slot_complete ));
308 : # endif
309 :
310 21 : fd_reasm_fec_t * pool = reasm_pool( reasm );
311 21 : # if FD_REASM_USE_HANDHOLDING
312 21 : FD_TEST( pool_free( pool ) );
313 21 : FD_TEST( !fd_reasm_query( reasm, merkle_root ) );
314 21 : # endif
315 :
316 21 : ulong null = pool_idx_null( pool );
317 21 : ancestry_t * ancestry = reasm->ancestry;
318 21 : frontier_t * frontier = reasm->frontier;
319 21 : orphaned_t * orphaned = reasm->orphaned;
320 21 : subtrees_t * subtrees = reasm->subtrees;
321 21 : dlist_t * dlist = reasm->subtreel;
322 :
323 21 : ulong * bfs = reasm->bfs;
324 21 : ulong * out = reasm->out;
325 :
326 21 : fd_reasm_fec_t * fec = pool_ele_acquire( pool );
327 21 : fec->key = *merkle_root;
328 21 : fec->next = null;
329 21 : fec->parent = null;
330 21 : fec->child = null;
331 21 : fec->sibling = null;
332 21 : fec->slot = slot;
333 21 : fec->parent_off = parent_off;
334 21 : fec->fec_set_idx = fec_set_idx;
335 21 : fec->data_cnt = data_cnt;
336 21 : fec->free = 0;
337 21 : fec->data_complete = data_complete;
338 21 : fec->slot_complete = slot_complete;
339 21 : fec->is_leader = is_leader;
340 21 : fec->eqvoc = 0;
341 21 : fec->confirmed = 0;
342 21 : fec->popped = 0;
343 21 : fec->bank_idx = null;
344 21 : fec->parent_bank_idx = null;
345 21 : fec->bank_seq = null;
346 21 : fec->parent_bank_seq = null;
347 :
348 21 : if( FD_UNLIKELY( !chained_merkle_root ) ) { /* initialize the reasm with the root */
349 3 : FD_TEST( reasm->root==pool_idx_null( pool ) );
350 3 : fec->confirmed = 1;
351 3 : fec->popped = 1;
352 3 : bid_t * bid = bid_insert( reasm->bid, slot );
353 3 : bid->idx = pool_idx( pool, fec );
354 3 : xid_t * xid = xid_insert( reasm->xid, ( slot << 32 ) | fec_set_idx );
355 3 : if( FD_UNLIKELY( !xid ) ) FD_LOG_CRIT(( "xid map full, slot=%lu fec_set_idx=%u", slot, fec_set_idx ));
356 3 : xid->idx = pool_idx( pool, fec );
357 3 : reasm->root = pool_idx( pool, fec );
358 3 : reasm->slot0 = slot;
359 3 : frontier_ele_insert( reasm->frontier, fec, pool );
360 3 : return fec;
361 3 : }
362 :
363 18 : fec->cmr = *chained_merkle_root;
364 18 : FD_TEST( memcmp( &fec->cmr, chained_merkle_root, sizeof(fd_hash_t) ) == 0 );
365 :
366 18 : if( FD_UNLIKELY( slot_complete ) ) {
367 3 : bid_t * bid = bid_query( reasm->bid, slot, NULL );
368 3 : if( FD_UNLIKELY( bid ) ) {
369 0 : fd_reasm_fec_t * orig_fec = pool_ele( pool, bid->idx );
370 0 : FD_BASE58_ENCODE_32_BYTES( orig_fec->key.key, prev_block_id_b58 );
371 0 : FD_BASE58_ENCODE_32_BYTES( fec->key.key, curr_block_id_b58 );
372 0 : FD_LOG_WARNING(( "equivocating block_id for FEC slot: %lu fec_set_idx: %u prev: %s curr: %s", fec->slot, fec->fec_set_idx, prev_block_id_b58, curr_block_id_b58 )); /* it's possible there's equivocation... */
373 3 : } else {
374 3 : bid = bid_insert( reasm->bid, slot );
375 3 : bid->idx = pool_idx( pool, fec );
376 3 : }
377 3 : }
378 :
379 18 : overwrite_invalid_cmr( reasm, fec ); /* case 1: received parent before child */
380 :
381 : /* First, we search for the parent of this new FEC and link if found.
382 : The new FEC set may result in a new leaf or a new orphan tree root
383 : so we need to check that. */
384 :
385 18 : fd_reasm_fec_t * parent = NULL;
386 18 : ulong idx = pool_idx( pool, fec );
387 18 : if( FD_LIKELY ( parent = ancestry_ele_query ( ancestry, &fec->cmr, NULL, pool ) ) ) { /* parent is connected non-leaf */
388 3 : frontier_ele_insert( frontier, fec, pool );
389 3 : out_push_tail ( out, idx );
390 15 : } else if( FD_LIKELY ( parent = frontier_ele_remove( frontier, &fec->cmr, NULL, pool ) ) ) { /* parent is connected leaf */
391 9 : ancestry_ele_insert( ancestry, parent, pool );
392 9 : frontier_ele_insert( frontier, fec, pool );
393 9 : out_push_tail ( out, idx );
394 9 : } else if( FD_LIKELY ( parent = orphaned_ele_query ( orphaned, &fec->cmr, NULL, pool ) ) ) { /* parent is orphaned non-root */
395 0 : orphaned_ele_insert( orphaned, fec, pool );
396 6 : } else if( FD_LIKELY ( parent = subtrees_ele_query ( subtrees, &fec->cmr, NULL, pool ) ) ) { /* parent is orphaned root */
397 0 : orphaned_ele_insert( orphaned, fec, pool );
398 6 : } else { /* parent not found */
399 6 : subtrees_ele_insert( subtrees, fec, pool );
400 6 : dlist_ele_push_tail( dlist, fec, pool );
401 6 : }
402 :
403 18 : if( FD_LIKELY( parent ) ) link( reasm, parent, fec );
404 :
405 : /* Second, we search for children of this new FEC and link them to it.
406 : By definition any children must be orphaned (a child cannot be part
407 : of a connected tree before its parent). Therefore, we only search
408 : through the orphaned subtrees. As part of this operation, we also
409 : coalesce connected orphans into the same tree. This way we only
410 : need to search the orphan tree roots (vs. all orphaned nodes). */
411 :
412 18 : FD_TEST( bfs_empty( bfs ) );
413 18 : for( dlist_iter_t iter = dlist_iter_fwd_init( dlist, pool );
414 39 : !dlist_iter_done ( iter, dlist, pool );
415 21 : iter = dlist_iter_fwd_next( iter, dlist, pool ) ) {
416 21 : bfs_push_tail( bfs, dlist_iter_idx( iter, dlist, pool ) );
417 21 : }
418 39 : while( FD_LIKELY( !bfs_empty( bfs ) ) ) { /* link orphan subtrees to the new FEC */
419 21 : fd_reasm_fec_t * orphan_root = pool_ele( pool, bfs_pop_head( bfs ) );
420 21 : overwrite_invalid_cmr( reasm, orphan_root ); /* case 2: received child before parent */
421 21 : if( FD_LIKELY( orphan_root && 0==memcmp( orphan_root->cmr.uc, fec->key.uc, sizeof(fd_hash_t) ) ) ) { /* this orphan_root is a direct child of fec */
422 6 : link( reasm, fec, orphan_root );
423 6 : subtrees_ele_remove( subtrees, &orphan_root->key, NULL, pool );
424 6 : dlist_ele_remove ( dlist, orphan_root, pool );
425 6 : orphaned_ele_insert( orphaned, orphan_root, pool );
426 6 : }
427 21 : }
428 :
429 : /* Third, we advance the frontier outward beginning from fec as we may
430 : have connected orphaned descendants to fec in the above step. This
431 : does a BFS outward from fec until it reaches leaves, moving fec and
432 : its non-leaf descendants into ancestry and leaves into frontier.
433 :
434 : parent (ancestry) orphan root (subtrees)
435 : | |
436 : fec (frontier) orphan child (orphaned)
437 :
438 : parent
439 : |
440 : fec <- frontier is here
441 : |
442 : orphan root
443 : |
444 : orphan child <- advance to here */
445 :
446 18 : if( FD_LIKELY( frontier_ele_query( frontier, &fec->key, NULL, pool ) ) ) bfs_push_tail( bfs, pool_idx( pool, fec ) );
447 36 : while( FD_LIKELY( !bfs_empty( bfs ) ) ) {
448 18 : fd_reasm_fec_t * parent = pool_ele( pool, bfs_pop_head( bfs ) );
449 18 : fd_reasm_fec_t * child = pool_ele( pool, parent->child );
450 18 : if( FD_LIKELY( child ) ) {
451 3 : frontier_ele_remove( frontier, &parent->key, NULL, pool );
452 3 : ancestry_ele_insert( ancestry, parent, pool );
453 3 : }
454 24 : while( FD_LIKELY( child ) ) {
455 6 : FD_TEST( orphaned_ele_remove( orphaned, &child->key, NULL, pool ) );
456 6 : frontier_ele_insert( frontier, child, pool );
457 6 : bfs_push_tail( bfs, pool_idx( pool, child ) );
458 6 : out_push_tail( out, pool_idx( pool, child ) );
459 6 : child = pool_ele( pool, child->sibling );
460 6 : }
461 18 : }
462 :
463 : /* Fourth, check and handle equivocation. There are two cases.
464 :
465 : 1. we've already seen this FEC's xid (slot, fec_set_idx)
466 : 2. this FEC's parent equivocates. */
467 :
468 18 : xid_t * xid = xid_query( reasm->xid, (slot<<32) | fec_set_idx, NULL );
469 18 : if( FD_LIKELY( !xid ) ) {
470 15 : xid = xid_insert( reasm->xid, ( slot << 32 ) | fec_set_idx );
471 15 : if( FD_UNLIKELY( !xid ) ) FD_LOG_CRIT(( "xid map full, slot=%lu fec_set_idx=%u", slot, fec_set_idx ));
472 15 : xid->idx = pool_idx( pool, fec );
473 15 : }
474 3 : else {
475 3 : eqvoc( reasm, fec );
476 3 : eqvoc( reasm, pool_ele( pool, xid->idx ) );
477 3 : }
478 18 : if( FD_UNLIKELY( parent && parent->eqvoc && !parent->confirmed ) ) eqvoc( reasm, fec );
479 :
480 : /* Finally, return the newly inserted FEC. */
481 :
482 18 : return fec;
483 18 : }
484 :
485 : static fd_reasm_fec_t *
486 : publish_remove( fd_reasm_t * reasm,
487 0 : fd_hash_t const * merkle_root ) {
488 0 : fd_reasm_fec_t * pool = reasm_pool( reasm );
489 0 : fd_reasm_fec_t * fec = ancestry_ele_remove( reasm->ancestry, merkle_root, NULL, pool );
490 0 : if( FD_UNLIKELY( !fec ) ) fec = frontier_ele_remove( reasm->frontier, merkle_root, NULL, pool );
491 0 : return fec;
492 0 : }
493 :
494 : fd_reasm_fec_t *
495 0 : fd_reasm_publish( fd_reasm_t * reasm, fd_hash_t const * merkle_root ) {
496 0 : # if FD_REASM_USE_HANDHOLDING
497 0 : if( FD_UNLIKELY( !pool_ele( reasm_pool( reasm ), reasm->root ) ) ) { FD_LOG_WARNING(( "missing root" )); return NULL; }
498 0 : if( FD_UNLIKELY( !fd_reasm_query( reasm, merkle_root ) ) ) {
499 0 : FD_BASE58_ENCODE_32_BYTES( merkle_root->key, merkle_root_b58 );
500 0 : FD_LOG_WARNING(( "merkle root %s not found", merkle_root_b58 ));
501 0 : return NULL;
502 0 : }
503 0 : # endif
504 :
505 0 : fd_reasm_fec_t * pool = reasm_pool( reasm );
506 0 : ulong null = pool_idx_null( pool );
507 0 : fd_reasm_fec_t * oldr = pool_ele( pool, reasm->root );
508 0 : fd_reasm_fec_t * newr = fd_reasm_query( reasm, merkle_root );
509 :
510 : /* First, remove the previous root, and push it as the first element
511 : of the BFS queue. */
512 :
513 0 : fd_reasm_fec_t * head = publish_remove( reasm, &oldr->key ); /* initialize BFS queue */
514 0 : head->next = null; /* clear map next */
515 0 : fd_reasm_fec_t * tail = head; /* tail of BFS queue */
516 :
517 : /* Second, BFS down the tree, pruning all of root's ancestors and also
518 : any descendants of those ancestors. */
519 :
520 0 : while( FD_LIKELY( head ) ) {
521 0 : fd_reasm_fec_t * child = pool_ele( pool, head->child ); /* left-child */
522 0 : while( FD_LIKELY( child ) ) { /* iterate over children */
523 0 : if( FD_LIKELY( child != newr ) ) { /* stop at new root */
524 0 : tail->next = pool_idx( pool, publish_remove( reasm, &child->key ) ); /* remove node from map to reuse `.next` */
525 0 : tail = pool_ele( pool, tail->next ); /* push onto BFS queue (so descendants can be pruned) */
526 0 : tail->next = null; /* clear map next */
527 0 : }
528 0 : child = pool_ele( pool, child->sibling ); /* right-sibling */
529 0 : }
530 0 : bid_t * bid = bid_query( reasm->bid, head->slot, NULL );
531 0 : if( FD_UNLIKELY( bid ) ) bid_remove( reasm->bid, bid ); /* only first FEC */
532 :
533 : /* remove from the xid map */
534 0 : xid_t * xid = xid_query( reasm->xid, ( head->slot << 32 ) | head->fec_set_idx, NULL );
535 0 : if( FD_UNLIKELY( !xid ) ) FD_LOG_CRIT(( "xid not found for slot: %lu fec_set_idx: %u", head->slot, head->fec_set_idx ));
536 0 : xid_remove( reasm->xid, xid );
537 :
538 0 : fd_reasm_fec_t * next = pool_ele( pool, head->next ); /* pophead */
539 0 : head->free = 1;
540 0 : pool_ele_release( pool, head ); /* release */
541 0 : head = next; /* advance */
542 0 : }
543 :
544 : /* Third, remove any elements from the out queue that were pruned from
545 : the tree in the above. */
546 :
547 0 : ulong cnt = out_cnt( reasm->out );
548 0 : for( ulong i = 0UL; i < cnt; i++ ) {
549 0 : ulong idx = out_pop_head( reasm->out );
550 0 : if( FD_LIKELY( pool_ele( pool, idx )->free==0 ) ) out_push_tail( reasm->out, idx );
551 0 : }
552 :
553 0 : newr->parent = null; /* unlink old root */
554 0 : reasm->root = pool_idx( pool, newr ); /* replace with new root */
555 0 : return newr;
556 0 : }
557 :
558 : #include <stdio.h>
559 :
560 : FD_FN_UNUSED static void
561 0 : print( fd_reasm_t const * reasm, fd_reasm_fec_t const * fec, int space, const char * prefix ) {
562 0 : fd_reasm_fec_t const * pool = reasm_pool_const( reasm );
563 0 :
564 0 : if( fec == NULL ) return;
565 0 :
566 0 : if( space > 0 ) printf( "\n" );
567 0 : for( int i = 0; i < space; i++ ) printf( " " );
568 0 : FD_BASE58_ENCODE_32_BYTES( fec->key.key, key_b58 );
569 0 : printf( "%s%s", prefix, key_b58 );
570 0 :
571 0 : fd_reasm_fec_t const * curr = pool_ele_const( pool, fec->child );
572 0 : char new_prefix[1024]; /* FIXME size this correctly */
573 0 : while( curr ) {
574 0 : if( pool_ele_const( pool, curr->sibling ) ) {
575 0 : sprintf( new_prefix, "├── " ); /* branch indicating more siblings follow */
576 0 : print( reasm, curr, space + 4, new_prefix );
577 0 : } else {
578 0 : sprintf( new_prefix, "└── " ); /* end branch */
579 0 : print( reasm, curr, space + 4, new_prefix );
580 0 : }
581 0 : curr = pool_ele_const( pool, curr->sibling );
582 0 : }
583 0 : }
584 :
585 : static void
586 21 : ancestry_print( fd_reasm_t const * reasm, fd_reasm_fec_t const * fec, int space, const char * prefix, fd_reasm_fec_t const * prev, ulong recurse_depth ) {
587 21 : fd_reasm_fec_t const * pool = reasm_pool_const( reasm );
588 21 : if( fec == NULL ) return;
589 21 : recurse_depth++;
590 21 : if( recurse_depth == 2048 ) {
591 0 : FD_BASE58_ENCODE_32_BYTES( fec->key.key, key_b58 );
592 0 : FD_LOG_NOTICE(("Cutting off ancestry print at depth %lu, slot %lu. Continue printing with this root key %s.", recurse_depth, fec->slot, key_b58 ));
593 0 : return;
594 0 : }
595 21 : fd_reasm_fec_t const * child = fd_reasm_child_const( reasm, fec );
596 :
597 21 : if( !prev || /* root OR */
598 21 : ( fec->slot_complete || (!prev->eqvoc && fec->eqvoc) || fec->child == pool_idx_null( pool ) || child->sibling != pool_idx_null( pool ) )) {
599 18 : if( space > 0 ) printf( "\n" );
600 168 : for( int i = 0; i < space; i++ ) printf( " " );
601 18 : printf( "%s", prefix );
602 :
603 18 : FD_BASE58_ENCODE_32_BYTES( fec->key.key, key_b58 );
604 18 : key_b58[5] = '\0'; /* only print first 5 characters of key_b58 */
605 18 : printf( "%lu(%u) %s", fec->slot, fec->fec_set_idx, key_b58 );
606 18 : if( fec->eqvoc ) printf( " [eqvoc]" );
607 18 : if( fec->is_leader ) printf( " [leader]" );
608 18 : space += 5;
609 18 : fflush(stdout);
610 18 : }
611 :
612 21 : char new_prefix[1024]; /* FIXME size this correctly */
613 :
614 39 : while( child ) {
615 18 : if( pool_ele_const( pool, child->sibling ) ) {
616 6 : sprintf( new_prefix, "├── " ); /* branch indicating more siblings follow */
617 6 : ancestry_print( reasm, child, space, new_prefix, fec, recurse_depth );
618 12 : } else {
619 12 : sprintf( new_prefix, "└── " ); /* end branch */
620 12 : ancestry_print( reasm, child, space, new_prefix, fec, recurse_depth );
621 12 : }
622 18 : child = pool_ele_const( pool, child->sibling );
623 18 : }
624 21 : }
625 :
626 : void
627 3 : fd_reasm_print( fd_reasm_t const * reasm ) {
628 3 : FD_LOG_NOTICE( ( "\n\n[Reasm]" ) );
629 3 : fd_reasm_fec_t const * pool = reasm_pool_const( reasm );
630 :
631 3 : if( FD_LIKELY( reasm->root != pool_idx_null( pool ) ) ) {
632 3 : printf( "\n\n[Connected Fecs]\n" );
633 3 : ancestry_print( reasm, fd_reasm_root_const( reasm ), 0, "", NULL, 0 );
634 3 : }
635 :
636 3 : printf( "\n\n[Unconnected Fecs]\n" );
637 3 : dlist_t const * subtreel = reasm->_subtrlf;
638 3 : for( dlist_iter_t iter = dlist_iter_fwd_init( subtreel, pool );
639 3 : !dlist_iter_done ( iter, subtreel, pool );
640 3 : iter = dlist_iter_fwd_next( iter, subtreel, pool ) ) {
641 0 : fd_reasm_fec_t const * fec = pool_ele_const( pool, iter );
642 0 : ancestry_print( reasm, fec, 0, "", NULL, 0 );
643 0 : }
644 3 : printf( "\n\n" );
645 : fflush(stdout);
646 3 : }
|
