Line data Source code
1 : #include "fd_reasm.h"
2 : #include "fd_reasm_private.h"
3 : #include "../../disco/shred/fd_fec_set.h"
4 :
5 : #define LOGGING 0
6 :
7 : FD_FN_CONST ulong
8 555 : fd_reasm_align( void ) {
9 555 : return alignof(fd_reasm_t);
10 555 : }
11 :
12 : FD_FN_CONST ulong
13 126 : fd_reasm_footprint( ulong fec_max ) {
14 126 : ulong max_slots = fd_ulong_max(fec_max / FD_FEC_BLK_MAX, 1UL); /* add capacity for a block id per slot */
15 126 : ulong chain_cnt = ancestry_chain_cnt_est( fec_max ); /* estimated buckets for ancestry map */
16 126 : int lgf_max = fd_ulong_find_msb( fd_ulong_pow2_up( fec_max + max_slots ) ); /* capacity for fec_max fecs + (fec_max / 1024) more block ids */
17 126 : return FD_LAYOUT_FINI(
18 126 : FD_LAYOUT_APPEND(
19 126 : FD_LAYOUT_APPEND(
20 126 : FD_LAYOUT_APPEND(
21 126 : FD_LAYOUT_APPEND(
22 126 : FD_LAYOUT_APPEND(
23 126 : FD_LAYOUT_APPEND(
24 126 : FD_LAYOUT_APPEND(
25 126 : FD_LAYOUT_APPEND(
26 126 : FD_LAYOUT_INIT,
27 126 : alignof(fd_reasm_t), sizeof(fd_reasm_t) ),
28 126 : pool_align(), pool_footprint ( fec_max ) ),
29 126 : ancestry_align(), ancestry_footprint( chain_cnt ) ),
30 126 : frontier_align(), frontier_footprint( chain_cnt ) ),
31 126 : orphaned_align(), orphaned_footprint( chain_cnt ) ),
32 126 : subtrees_align(), subtrees_footprint( chain_cnt ) ),
33 126 : bfs_align(), bfs_footprint ( fec_max ) ),
34 126 : xid_align(), xid_footprint ( lgf_max ) ),
35 126 : fd_reasm_align() );
36 126 : }
37 :
38 : void *
39 : fd_reasm_new( void * shmem,
40 : ulong fec_max,
41 63 : ulong seed ) {
42 :
43 63 : if( FD_UNLIKELY( !shmem ) ) {
44 0 : FD_LOG_WARNING(( "NULL mem" ));
45 0 : return NULL;
46 0 : }
47 :
48 63 : if( FD_UNLIKELY( !fd_ulong_is_aligned( (ulong)shmem, fd_reasm_align() ) ) ) {
49 0 : FD_LOG_WARNING(( "misaligned mem" ));
50 0 : return NULL;
51 0 : }
52 :
53 63 : ulong footprint = fd_reasm_footprint( fec_max );
54 63 : if( FD_UNLIKELY( !footprint ) ) {
55 0 : FD_LOG_WARNING(( "bad fec_max (%lu)", fec_max ));
56 0 : return NULL;
57 0 : }
58 :
59 63 : fd_wksp_t * wksp = fd_wksp_containing( shmem );
60 63 : if( FD_UNLIKELY( !wksp ) ) {
61 0 : FD_LOG_WARNING(( "shmem must be part of a workspace" ));
62 0 : return NULL;
63 0 : }
64 :
65 63 : fd_memset( shmem, 0, footprint );
66 :
67 63 : ulong max_slots = fd_ulong_max(fec_max / FD_FEC_BLK_MAX, 1UL); /* add capacity for a block id per slot */
68 63 : int lgf_max = fd_ulong_find_msb( fd_ulong_pow2_up( fec_max + max_slots ) ); /* capacity for fec_max fecs + (fec_max / 1024) more block ids */
69 63 : ulong chain_cnt = ancestry_chain_cnt_est( fec_max ); /* estimated buckets for ancestry map */
70 :
71 63 : fd_reasm_t * reasm;
72 63 : FD_SCRATCH_ALLOC_INIT( l, shmem );
73 63 : reasm = FD_SCRATCH_ALLOC_APPEND( l, alignof(fd_reasm_t), sizeof(fd_reasm_t) );
74 63 : void * pool = FD_SCRATCH_ALLOC_APPEND( l, pool_align(), pool_footprint ( fec_max ) );
75 63 : void * ancestry = FD_SCRATCH_ALLOC_APPEND( l, ancestry_align(), ancestry_footprint( chain_cnt ) );
76 63 : void * frontier = FD_SCRATCH_ALLOC_APPEND( l, frontier_align(), frontier_footprint( chain_cnt ) );
77 63 : void * orphaned = FD_SCRATCH_ALLOC_APPEND( l, orphaned_align(), orphaned_footprint( chain_cnt ) );
78 63 : void * subtrees = FD_SCRATCH_ALLOC_APPEND( l, subtrees_align(), subtrees_footprint( chain_cnt ) );
79 63 : void * bfs = FD_SCRATCH_ALLOC_APPEND( l, bfs_align(), bfs_footprint ( fec_max ) );
80 63 : void * xid = FD_SCRATCH_ALLOC_APPEND( l, xid_align(), xid_footprint ( lgf_max ) );
81 63 : FD_TEST( FD_SCRATCH_ALLOC_FINI( l, fd_reasm_align() ) == (ulong)shmem + footprint );
82 :
83 63 : reasm->slot0 = ULONG_MAX;
84 63 : reasm->root = pool_idx_null( pool );
85 63 : reasm->pool_gaddr = fd_wksp_gaddr_fast( wksp, pool_join( pool_new( pool, fec_max ) ) );
86 63 : reasm->wksp_gaddr = fd_wksp_gaddr_fast( wksp, reasm );
87 63 : reasm->ancestry = ancestry_new( ancestry, chain_cnt, seed );
88 63 : reasm->frontier = frontier_new( frontier, chain_cnt, seed );
89 63 : reasm->orphaned = orphaned_new( orphaned, chain_cnt, seed );
90 63 : reasm->subtrees = subtrees_new( subtrees, chain_cnt, seed );
91 63 : reasm->subtreel = subtreel_new( reasm->_subtrlf );
92 63 : reasm->out = out_new ( reasm->_out );
93 63 : reasm->bfs = bfs_new ( bfs, fec_max );
94 63 : reasm->xid = xid_new ( xid, lgf_max, seed );
95 :
96 63 : return shmem;
97 63 : }
98 :
99 : fd_reasm_t *
100 63 : fd_reasm_join( void * shreasm ) {
101 63 : fd_reasm_t * reasm = (fd_reasm_t *)shreasm;
102 :
103 63 : if( FD_UNLIKELY( !reasm ) ) {
104 0 : FD_LOG_WARNING(( "NULL reasm" ));
105 0 : return NULL;
106 0 : }
107 : /* pool join handled in fd_reasm_new */
108 63 : reasm->ancestry = ancestry_join( reasm->ancestry );
109 63 : reasm->frontier = frontier_join( reasm->frontier );
110 63 : reasm->orphaned = orphaned_join( reasm->orphaned );
111 63 : reasm->subtrees = subtrees_join( reasm->subtrees );
112 63 : reasm->subtreel = subtreel_join( reasm->_subtrlf );
113 63 : reasm->out = out_join ( reasm->_out );
114 63 : reasm->bfs = bfs_join ( reasm->bfs );
115 63 : reasm->xid = xid_join ( reasm->xid );
116 :
117 63 : return reasm;
118 63 : }
119 :
120 : void *
121 51 : fd_reasm_leave( fd_reasm_t * reasm ) {
122 :
123 51 : if( FD_UNLIKELY( !reasm ) ) {
124 0 : FD_LOG_WARNING(( "NULL reasm" ));
125 0 : return NULL;
126 0 : }
127 :
128 51 : return (void *)reasm;
129 51 : }
130 :
131 : void *
132 51 : fd_reasm_delete( void * shreasm ) {
133 51 : fd_reasm_t * reasm = (fd_reasm_t *)shreasm;
134 :
135 51 : if( FD_UNLIKELY( !reasm ) ) {
136 0 : FD_LOG_WARNING(( "NULL reasm" ));
137 0 : return NULL;
138 0 : }
139 :
140 51 : if( FD_UNLIKELY( !fd_ulong_is_aligned((ulong)reasm, fd_reasm_align() ) ) ) {
141 0 : FD_LOG_WARNING(( "misaligned reasm" ));
142 0 : return NULL;
143 0 : }
144 :
145 51 : return reasm;
146 51 : }
147 :
148 6 : fd_reasm_fec_t * fd_reasm_root ( fd_reasm_t * reasm ) { return pool_ele ( reasm_pool ( reasm ), reasm->root ); }
149 6 : fd_reasm_fec_t const * fd_reasm_root_const ( fd_reasm_t const * reasm ) { return pool_ele_const( reasm_pool_const( reasm ), reasm->root ); }
150 111 : fd_reasm_fec_t * fd_reasm_parent ( fd_reasm_t * reasm, fd_reasm_fec_t * child ) { return pool_ele ( reasm_pool ( reasm ), child->parent ); }
151 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 ); }
152 12486 : fd_reasm_fec_t * fd_reasm_child ( fd_reasm_t * reasm, fd_reasm_fec_t * parent ) { return pool_ele ( reasm_pool ( reasm ), parent->child ); }
153 42 : 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 ); }
154 12312 : fd_reasm_fec_t * fd_reasm_sibling ( fd_reasm_t * reasm, fd_reasm_fec_t * sibling ) { return pool_ele ( reasm_pool ( reasm ), sibling->sibling ); }
155 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 ); }
156 :
157 : ulong
158 0 : fd_reasm_slot0( fd_reasm_t * reasm ) {
159 0 : return reasm->slot0;
160 0 : }
161 :
162 : ulong
163 3 : fd_reasm_free( fd_reasm_t * reasm ) {
164 3 : return pool_free( reasm_pool( reasm ) );
165 3 : }
166 :
167 : fd_reasm_fec_t *
168 3 : fd_reasm_peek( fd_reasm_t * reasm ) {
169 3 : fd_reasm_fec_t * pool = reasm_pool( reasm );
170 3 : for( out_iter_t iter = out_iter_fwd_init( reasm->out, pool );
171 3 : !out_iter_done ( iter, reasm->out, pool );
172 3 : iter = out_iter_fwd_next( iter, reasm->out, pool ) ) {
173 0 : fd_reasm_fec_t * fec = out_iter_ele( iter, reasm->out, pool );
174 0 : if( FD_LIKELY( fec && !fec->popped && ( !fec->eqvoc || fec->confirmed ) ) ) return fec;
175 0 : }
176 3 : return NULL;
177 3 : }
178 :
179 : fd_reasm_fec_t *
180 171 : fd_reasm_pop( fd_reasm_t * reasm ) {
181 171 : fd_reasm_fec_t * pool = reasm_pool( reasm );
182 201 : while( FD_LIKELY( !out_is_empty( reasm->out, pool ) ) ) {
183 156 : fd_reasm_fec_t * fec = out_ele_pop_head( reasm->out, pool );
184 156 : fec->in_out = 0;
185 156 : if( FD_LIKELY( !fec->popped && ( !fec->eqvoc || fec->confirmed ) ) ) {
186 126 : fec->popped = 1;
187 126 : return fec;
188 126 : }
189 156 : }
190 45 : return NULL;
191 171 : }
192 :
193 : fd_reasm_fec_t *
194 : fd_reasm_query( fd_reasm_t * reasm,
195 37821 : fd_hash_t const * merkle_root ) {
196 37821 : fd_reasm_fec_t * pool = reasm_pool( reasm );
197 37821 : fd_reasm_fec_t * fec = NULL;
198 37821 : fec = ancestry_ele_query( reasm->ancestry, merkle_root, NULL, pool );
199 37821 : fec = fd_ptr_if( !fec, frontier_ele_query( reasm->frontier, merkle_root, NULL, pool ), fec );
200 37821 : fec = fd_ptr_if( !fec, orphaned_ele_query( reasm->orphaned, merkle_root, NULL, pool ), fec );
201 37821 : fec = fd_ptr_if( !fec, subtrees_ele_query( reasm->subtrees, merkle_root, NULL, pool ), fec );
202 37821 : return fec;
203 37821 : }
204 :
205 : void
206 : fd_reasm_confirm( fd_reasm_t * reasm,
207 27 : fd_hash_t const * block_id ) {
208 27 : fd_reasm_fec_t * pool = reasm_pool( reasm );
209 27 : fd_reasm_fec_t * fec = ancestry_ele_query( reasm->ancestry, block_id, NULL, pool );
210 27 : fec = fd_ptr_if( !fec, frontier_ele_query( reasm->frontier, block_id, NULL, pool ), fec );
211 :
212 : /* TODO there is a potential optimization where we don't actually need
213 : to confirm every FEC and instead just confirm at the slot-level.
214 : Given roughly ~1k shreds per slot at 32 shreds per FEC, this would
215 : save ~32 loop iterations. Punting given the additional complexity
216 : of bookkeeping and logic this would require.
217 :
218 : If this FEC has not been popped, then that means we need to
219 : redeliver it for execution. Reasm could be in a state where by
220 : confirming the child of an equivocating chain, the child is
221 : confirmed & popped, but the parent of it is confirmed & not
222 : *popped*. It was not delivered through the reasm out queue because
223 : it was backfilled. In the off chance that the parent confirmation
224 : arrives after the child confirmation, we need to make sure to not
225 : redeliver the parent again. The invariant is that if a FEC is
226 : already confirmed, either it or its child must have already been
227 : delivered for execution. */
228 :
229 27 : if( FD_LIKELY( fec && !fec->popped && !fec->in_out && !fec->confirmed ) ) {
230 9 : out_ele_push_tail( reasm->out, fec, pool );
231 9 : fec->in_out = 1;
232 9 : }
233 :
234 96 : while( FD_LIKELY( fec && !fec->confirmed ) ) {
235 69 : fec->confirmed = 1;
236 69 : fec = fd_reasm_parent( reasm, fec );
237 69 : }
238 27 : }
239 :
240 : /* Mark the entire subtree beginning from root as equivocating. This is
241 : linear in the number of descendants in the subtree, but amortizes
242 : because we can short-circuit the BFS at nodes that are already marked
243 : equivocating, so each node is visited at most once. */
244 :
245 : static void
246 : eqvoc( fd_reasm_t * reasm,
247 108 : fd_reasm_fec_t * root ) {
248 108 : fd_reasm_fec_t * pool = reasm_pool( reasm );
249 108 : ulong * bfs = reasm->bfs;
250 108 : bfs_push_tail( bfs, pool_idx( pool, root ) );
251 240 : while( FD_LIKELY( !bfs_empty( bfs ) ) ) {
252 132 : fd_reasm_fec_t * descendant = pool_ele( pool, bfs_pop_head( bfs ) );
253 132 : if( FD_LIKELY( descendant->eqvoc ) ) continue;
254 105 : descendant->eqvoc = 1;
255 105 : fd_reasm_fec_t * child = fd_reasm_child( reasm, descendant );
256 129 : while( FD_LIKELY( child ) ) {
257 24 : bfs_push_tail( bfs, pool_idx( pool, child ) );
258 24 : child = fd_reasm_sibling( reasm, child );
259 24 : }
260 105 : }
261 108 : }
262 :
263 : static int
264 : validate_intra( fd_reasm_fec_t const * parent,
265 12606 : fd_reasm_fec_t const * child ) {
266 12606 : return child->fec_set_idx==parent->fec_set_idx+FD_FEC_SHRED_CNT &&
267 12606 : child->parent_off ==parent->parent_off &&
268 12606 : !parent->slot_complete;
269 12606 : }
270 :
271 : static int
272 : validate_inter( fd_reasm_fec_t const * parent,
273 12606 : fd_reasm_fec_t const * child ) {
274 12606 : return child->slot - child->parent_off==parent->slot &&
275 12606 : child->fec_set_idx==0 &&
276 12606 : parent->slot_complete;
277 12606 : }
278 :
279 : static inline int
280 : validate_chained_block_id( fd_reasm_fec_t const * parent,
281 12606 : fd_reasm_fec_t const * child ) {
282 12606 : return fd_int_if( parent->slot==child->slot, validate_intra( parent, child ), validate_inter( parent, child ) );
283 12606 : }
284 :
285 : static void
286 : link( fd_reasm_t * reasm,
287 : fd_reasm_fec_t * parent,
288 12570 : fd_reasm_fec_t * child ) {
289 12570 : fd_reasm_fec_t * pool = reasm_pool( reasm );
290 12570 : child->parent = pool_idx( pool, parent );
291 12570 : if( FD_LIKELY( parent->child == pool_idx_null( pool ) ) ) {
292 12516 : parent->child = pool_idx( pool, child ); /* set as left-child. */
293 12516 : } else {
294 54 : fd_reasm_fec_t * sibling = pool_ele( pool, parent->child );
295 66 : while( FD_LIKELY( sibling->sibling != pool_idx_null( pool ) ) ) sibling = pool_ele( pool, sibling->sibling );
296 54 : sibling->sibling = pool_idx( pool, child ); /* set as right-sibling. */
297 54 : }
298 12570 : }
299 :
300 : /* Assumes caller is de-duplicating FEC sets of the same merkle root.
301 : Updates the xid map and inserts the new FEC into the head of the
302 : xid list. */
303 : static xid_t *
304 12642 : xid_update( fd_reasm_t * reasm, ulong slot, uint fec_set_idx, ulong pool_idx ) {
305 12642 : fd_reasm_fec_t * new_fec = pool_ele( reasm_pool( reasm ), pool_idx );
306 12642 : xid_t * xid = xid_query( reasm->xid, (slot << 32) | fec_set_idx, NULL );
307 12642 : if( FD_UNLIKELY( xid ) ) {
308 42 : new_fec->xid_next = xid->idx;
309 42 : xid->idx = pool_idx; /* updates head ptr */
310 42 : xid->cnt++;
311 12600 : } else {
312 12600 : xid = xid_insert( reasm->xid, (slot << 32) | fec_set_idx );
313 12600 : if( FD_UNLIKELY( !xid ) ) FD_LOG_CRIT(( "xid map full, slot=%lu fec_set_idx=%u", slot, fec_set_idx ));
314 12600 : xid->idx = pool_idx;
315 12600 : xid->cnt = 1;
316 12600 : }
317 12642 : return xid;
318 12642 : }
319 :
320 : static fd_reasm_fec_t *
321 : clear_xid_metadata( fd_reasm_t * reasm,
322 12372 : fd_reasm_fec_t * fec ) {
323 12372 : fd_reasm_fec_t * pool = reasm_pool( reasm );
324 12372 : ulong fec_idx = pool_idx( pool, fec );
325 :
326 12372 : xid_t * xid = xid_query( reasm->xid, (fec->slot << 32)|fec->fec_set_idx, NULL );
327 12372 : xid->cnt--;
328 12372 : if( FD_LIKELY( !xid->cnt ) ) {
329 12360 : xid_remove( reasm->xid, xid );
330 12360 : } else if( xid->idx==fec_idx ) {
331 3 : xid->idx = fec->xid_next;
332 9 : } else {
333 9 : fd_reasm_fec_t * prev = pool_ele( pool, xid->idx );
334 9 : while( prev->xid_next!=fec_idx ) prev = pool_ele( pool, prev->xid_next );
335 9 : prev->xid_next = fec->xid_next;
336 9 : }
337 :
338 12372 : return fec;
339 12372 : }
340 :
341 : static void
342 : subtrees_remove( fd_reasm_t * reasm,
343 : fd_reasm_fec_t * root,
344 9 : fd_store_t * opt_store ) {
345 9 : fd_reasm_fec_t * pool = reasm_pool( reasm );
346 9 : ulong * bfs = reasm->bfs;
347 :
348 9 : FD_TEST( bfs_empty( bfs ) );
349 9 : bfs_push_tail( bfs, pool_idx( pool, root ) );
350 12306 : while( FD_LIKELY( !bfs_empty( bfs ) ) ) {
351 12297 : fd_reasm_fec_t * ele = pool_ele( pool, bfs_pop_head( bfs ) );
352 :
353 12297 : fd_reasm_fec_t * child = fd_reasm_child( reasm, ele );
354 24585 : while( FD_LIKELY( child ) ) {
355 12288 : bfs_push_tail( bfs, pool_idx( pool, child ) );
356 12288 : child = fd_reasm_sibling( reasm, child );
357 12288 : }
358 :
359 12297 : if( FD_UNLIKELY( subtrees_ele_query( reasm->subtrees, &ele->key, NULL, pool )==ele ) ) {
360 9 : subtrees_ele_remove( reasm->subtrees, &ele->key, NULL, pool );
361 9 : subtreel_ele_remove( reasm->subtreel, ele, pool );
362 12288 : } else {
363 12288 : FD_TEST( orphaned_ele_remove( reasm->orphaned, &ele->key, NULL, pool )==ele );
364 12288 : }
365 :
366 12297 : clear_xid_metadata( reasm, ele );
367 12297 : if( FD_LIKELY( opt_store ) ) fd_store_remove( opt_store, &ele->key );
368 12297 : pool_ele_release( pool, ele );
369 12297 : }
370 9 : FD_TEST( bfs_empty( bfs ) );
371 9 : }
372 :
373 : void
374 : fd_reasm_pool_release( fd_reasm_t * reasm,
375 21 : fd_reasm_fec_t * ele ){
376 21 : pool_ele_release( reasm_pool( reasm ), ele );
377 21 : }
378 :
379 : ulong
380 0 : fd_reasm_pool_idx( fd_reasm_t * reasm, fd_reasm_fec_t * ele ) {
381 0 : return pool_idx( reasm_pool( reasm ), ele );
382 0 : }
383 :
384 : fd_reasm_fec_t *
385 : fd_reasm_remove( fd_reasm_t * reasm,
386 : fd_reasm_fec_t * head,
387 15 : fd_store_t * opt_store ) {
388 : /* see fd_forest.c clear_leaf */
389 :
390 15 : fd_reasm_fec_t * pool = reasm_pool( reasm );
391 15 : orphaned_t * orphaned = reasm->orphaned;
392 15 : frontier_t * frontier = reasm->frontier;
393 15 : ancestry_t * ancestry = reasm->ancestry;
394 15 : subtrees_t * subtrees = reasm->subtrees;
395 15 : subtreel_t * subtreel = reasm->subtreel;
396 :
397 15 : FD_TEST( head );
398 :
399 15 : fd_reasm_fec_t * tail = head;
400 :
401 15 : if( FD_LIKELY( orphaned_ele_query( orphaned, &head->key, NULL, pool ) ||
402 15 : subtrees_ele_query( subtrees, &head->key, NULL, pool ) ) ) {
403 3 : FD_TEST( head->child == ULONG_MAX ); /* must be a leaf node */
404 12 : } else {
405 : /* Node is in frontier or ancestry. If the leaf is in the frontier,
406 : we could be removing something that has been executed. Move the
407 : head pointer up to where we begin evicting.
408 :
409 : We search up the tree until the theoretical boundary of a bank.
410 : This is usually when we jump to a parent slot, but if an
411 : equivocation occured, this could also be the middle of the slot.
412 :
413 : 0 ── 32 ── 64 ── 96 (confirmed)
414 : └── 64' ── 96' ── 128' (eqvoc)
415 :
416 : Note we only have execute a slot twice (have 2 bank idxs for it)
417 : if the slot equivocated, we replayed the wrong version, and then
418 : replayed the confirmed version afterwards.
419 :
420 : The state after executing the wrong version first is:
421 :
422 : 0 ──── 32 ──── 64 ──── 96 ──── 128
423 : (bank_idx=1) (bank_idx=1) .... (all bank_idx=1)
424 :
425 : After receiving and executing the confirmed version, the state
426 : looks like:
427 :
428 : 0 (b=2) ── 32 (b=2) ── 64 (b=2) ── 96 (b=2) (confirmed)
429 : └── 64' (b=1) ── 96' (b=1) ── 128' (b=1) (eqvoc)
430 :
431 : Here we want to evict only until fec 64'. Or let's say we are
432 : getting around to executing the confirmed version, but we haven't
433 : executed it yet.
434 :
435 : 0 (b=1) ── 32 (b=1) ── 64 (b=ULONG_MAX) ── 96 (b=ULONG_MAX) (confirmed, but not executed yet)
436 : └── 64' (b=1) ── 96' (b=1) ── 128'(b=1) (eqvoc)
437 :
438 : Now we know we should evict until the max(parent has > 1 child, or fec set idx == 0) */
439 :
440 15 : while( FD_LIKELY( head ) ) {
441 15 : fd_reasm_fec_t * parent = fd_reasm_parent( reasm, head ); /* parent must exist. It's not possible to walk up past root */
442 :
443 15 : if( FD_UNLIKELY( head->fec_set_idx==0 ) ) break;
444 6 : if( FD_UNLIKELY( head->sibling != pool_idx_null( pool ) ) ) break; /* if the parent has more than 1 child, we know for sure the parent is a slot boundary or eqvoc point, so we can stop here. */
445 6 : if( FD_UNLIKELY( parent->child != pool_idx( pool, head ) ) ) break; /* if the parent has more than 1 child, we know for sure the parent is a slot boundary or eqvoc point, so we can stop here. */
446 3 : head = parent;
447 3 : }
448 12 : }
449 15 : FD_LOG_INFO(( "evicting reasm slot %lu, fec idx %u, down to %u bank_idx %lu", head->slot, head->fec_set_idx, tail->fec_set_idx, head->bank_idx ));
450 :
451 : /* Orphan the entire subtree from the tail :( */
452 15 : if( FD_UNLIKELY( fd_reasm_child( reasm, tail ) ) ) {
453 : /* subtree this child. This code path should only be hit if this is
454 : banks-driven eviction, so children are guaranteed to be in main
455 : tree right now. */
456 3 : ulong * bfs = reasm->bfs;
457 3 : bfs_push_tail( bfs, pool_idx( pool, tail ) );
458 27 : while( FD_LIKELY( !bfs_empty( bfs ) ) ) {
459 24 : fd_reasm_fec_t * ele = pool_ele( pool, bfs_pop_head( bfs ) );
460 24 : fd_reasm_fec_t * child = fd_reasm_child( reasm, ele );
461 45 : while( FD_LIKELY( child ) ) {
462 21 : bfs_push_tail( bfs, pool_idx( pool, child ) );
463 21 : child = pool_ele( pool, child->sibling );
464 21 : }
465 :
466 24 : if( FD_UNLIKELY( ele == tail ) ) continue;
467 : /* remove each child from the maps */
468 21 : if( FD_UNLIKELY( !ancestry_ele_remove( ancestry, &ele->key, NULL, pool ) ) ) frontier_ele_remove( frontier, &ele->key, NULL, pool );
469 21 : if( FD_LIKELY( ele->in_out ) ) { out_ele_remove( reasm->out, ele, pool ); ele->in_out = 0; }
470 :
471 21 : if( FD_UNLIKELY( ele->parent == pool_idx( pool, tail ) ) ) {
472 3 : subtrees_ele_insert( subtrees, ele, pool );
473 3 : subtreel_ele_push_tail( reasm->subtreel, ele, pool );
474 3 : ele->parent = ULONG_MAX;
475 3 : ele->sibling = ULONG_MAX;
476 18 : } else {
477 18 : orphaned_ele_insert( orphaned, ele, pool );
478 18 : }
479 21 : }
480 : /* unlink the leaf from its children. */
481 3 : tail->child = ULONG_MAX;
482 3 : }
483 :
484 15 : fd_reasm_fec_t * parent = fd_reasm_parent( reasm, head );
485 15 : if( FD_LIKELY( parent ) ) {
486 : /* Clean up the parent pointing to this head, and remove block from the maps
487 : remove the block from the parent's child list */
488 :
489 12 : fd_reasm_fec_t * child = pool_ele( pool, parent->child );
490 12 : if( FD_LIKELY( 0==memcmp( &child->key, &head->key, sizeof(fd_hash_t) ) ) ) { /* evicted is left-child (or only child) */
491 9 : parent->child = child->sibling;
492 9 : } else {
493 : /* evicted is a right-sibling */
494 3 : fd_reasm_fec_t * sibling = pool_ele( pool, child->sibling );
495 3 : fd_reasm_fec_t * prev = child;
496 6 : while( FD_LIKELY( sibling && memcmp( &sibling->key, &head->key, sizeof(fd_hash_t) ) ) ) {
497 3 : prev = sibling;
498 3 : sibling = pool_ele( pool, sibling->sibling );
499 3 : }
500 3 : prev->sibling = sibling->sibling;
501 3 : }
502 :
503 : /* remove the chain itself from the maps */
504 :
505 12 : fd_reasm_fec_t * removed_orphan = NULL;
506 12 : if( FD_LIKELY ( removed_orphan = orphaned_ele_remove( orphaned, &head->key, NULL, pool ) ) ) {
507 0 : clear_xid_metadata( reasm, head );
508 0 : if( FD_LIKELY( opt_store ) ) fd_store_remove( opt_store, &head->key );
509 0 : return head;
510 0 : }
511 :
512 : /* remove from ancestry and frontier */
513 12 : fd_reasm_fec_t * curr = head;
514 27 : while( FD_LIKELY( curr ) ) {
515 15 : fd_reasm_fec_t * removed = ancestry_ele_remove( ancestry, &curr->key, NULL, pool );
516 15 : if( !removed ) removed = frontier_ele_remove( frontier, &curr->key, NULL, pool );
517 15 : if( FD_LIKELY( removed->in_out ) ) { out_ele_remove( reasm->out, removed, pool ); removed->in_out = 0; }
518 :
519 15 : curr = fd_reasm_child( reasm, curr ); /* guaranteed only one child */
520 15 : clear_xid_metadata( reasm, removed );
521 15 : if( FD_LIKELY( opt_store ) ) fd_store_remove( opt_store, &removed->key );
522 15 : }
523 :
524 : /* We removed from the main tree, so we might need to insert parent into the frontier.
525 : Only need to add parent to the frontier if it doesn't have any other children. */
526 :
527 12 : if( parent->child == pool_idx_null( pool ) ) {
528 6 : parent = ancestry_ele_remove( ancestry, &parent->key, NULL, pool );
529 6 : FD_TEST( parent );
530 6 : frontier_ele_insert( frontier, parent, pool );
531 6 : }
532 12 : return head;
533 12 : }
534 :
535 : /* No parent, remove from subtrees and subtree list */
536 3 : subtrees_ele_remove( subtrees, &head->key, NULL, pool );
537 3 : subtreel_ele_remove( subtreel, head, pool );
538 3 : clear_xid_metadata( reasm, head );
539 3 : if( FD_LIKELY( opt_store ) ) fd_store_remove( opt_store, &head->key );
540 3 : return head;
541 15 : }
542 :
543 : fd_reasm_fec_t *
544 : latest_confirmed_fec( fd_reasm_t * reasm,
545 0 : ulong subtree_root ) {
546 0 : ulong * bfs = reasm->bfs;
547 0 : fd_reasm_fec_t * pool = reasm_pool( reasm );
548 0 : bfs_push_tail( bfs, subtree_root );
549 0 : fd_reasm_fec_t * latest_confirmed = NULL;
550 0 : while( FD_LIKELY( !bfs_empty( bfs ) ) ) {
551 0 : fd_reasm_fec_t * ele = pool_ele( pool, bfs_pop_head( bfs ) );
552 0 : if( FD_LIKELY( ele->confirmed ) ) {
553 0 : if( FD_LIKELY( latest_confirmed == NULL ||
554 0 : latest_confirmed->slot < ele->slot ||
555 0 : (latest_confirmed->slot == ele->slot && latest_confirmed->fec_set_idx < ele->fec_set_idx)) )
556 0 : latest_confirmed = ele;
557 0 : }
558 0 : fd_reasm_fec_t * child = fd_reasm_child( reasm, ele );
559 0 : while( FD_LIKELY( child ) ) {
560 0 : bfs_push_tail( bfs, pool_idx( pool, child ) );
561 0 : child = pool_ele( pool, child->sibling );
562 0 : }
563 0 : }
564 0 : return latest_confirmed;
565 0 : }
566 :
567 : static fd_reasm_fec_t *
568 : gca( fd_reasm_t * reasm,
569 : fd_reasm_fec_t * a,
570 0 : fd_reasm_fec_t * b ) {
571 0 : fd_reasm_fec_t * parent1 = a;
572 0 : fd_reasm_fec_t * parent2 = b;
573 0 : while( FD_LIKELY( parent1 && parent2 ) ) {
574 0 : if( FD_LIKELY( parent1 == parent2 ) ) return parent1;
575 0 : if( parent1->slot > parent2->slot ||
576 0 : ( parent1->slot == parent2->slot && parent1->fec_set_idx > parent2->fec_set_idx ) ) parent1 = fd_reasm_parent( reasm, parent1 );
577 0 : else parent2 = fd_reasm_parent( reasm, parent2 );
578 0 : }
579 0 : return NULL;
580 0 : }
581 :
582 : /* Caller guarantees new_root and parent_root are non-NULL */
583 : static fd_reasm_fec_t *
584 : evict( fd_reasm_t * reasm,
585 : fd_store_t * opt_store,
586 : fd_hash_t const * new_root FD_PARAM_UNUSED,
587 12 : fd_hash_t const * parent_root ) {
588 12 : fd_reasm_fec_t * pool = reasm_pool( reasm );
589 12 : frontier_t * frontier = reasm->frontier;
590 12 : orphaned_t * orphaned = reasm->orphaned;
591 12 : subtrees_t * subtrees = reasm->subtrees;
592 12 : subtreel_t * subtreel = reasm->subtreel;
593 :
594 : /* Generally, best policy for eviction is to evict in the order of:
595 : 1. Highest unconfirmed orphan leaf - furthest from root
596 : 2. Highest incomplete, unconfirmed leaf in ancestry - furthest from tip of execution
597 : 3. Highest confirmed orphan leaf - evictable, since unrelated to banks, but less ideal */
598 :
599 12 : fd_reasm_fec_t * unconfrmd_orphan = NULL; /* 1st best candidate for eviction is the highest unconfirmed orphan. */
600 12 : fd_reasm_fec_t * confirmed_orphan = NULL; /* 3rd best candidate for eviction is the highest confirmed orphan. */
601 12 : for( subtreel_iter_t iter = subtreel_iter_fwd_init( subtreel, pool );
602 18 : !subtreel_iter_done ( iter, subtreel, pool );
603 12 : iter = subtreel_iter_fwd_next( iter, subtreel, pool ) ) {
604 6 : fd_reasm_fec_t * ele = subtreel_iter_ele( iter, subtreel, pool );
605 6 : if( ele->child != ULONG_MAX || memcmp( &ele->key, parent_root, sizeof(fd_hash_t) ) == 0 ) continue;
606 3 : if( FD_UNLIKELY( ele->confirmed ) ) confirmed_orphan = fd_ptr_if( !confirmed_orphan || ele->slot > confirmed_orphan->slot, ele, confirmed_orphan );
607 3 : else unconfrmd_orphan = fd_ptr_if( !unconfrmd_orphan || ele->slot > unconfrmd_orphan->slot, ele, unconfrmd_orphan );
608 3 : }
609 12 : for( orphaned_iter_t iter = orphaned_iter_init( orphaned, pool );
610 12 : !orphaned_iter_done( iter, orphaned, pool );
611 12 : iter = orphaned_iter_next( iter, orphaned, pool ) ) {
612 0 : fd_reasm_fec_t * ele = orphaned_iter_ele( iter, orphaned, pool );
613 0 : if( ele->child != ULONG_MAX || memcmp( &ele->key, parent_root, sizeof(fd_hash_t) ) == 0 ) continue;
614 0 : if( FD_UNLIKELY( ele->confirmed ) ) confirmed_orphan = fd_ptr_if( !confirmed_orphan || ele->slot > confirmed_orphan->slot, ele, confirmed_orphan );
615 0 : else unconfrmd_orphan = fd_ptr_if( !unconfrmd_orphan || ele->slot > unconfrmd_orphan->slot, ele, unconfrmd_orphan );
616 0 : }
617 :
618 12 : if( FD_UNLIKELY( unconfrmd_orphan )) {
619 3 : return fd_reasm_remove( reasm, unconfrmd_orphan, opt_store );
620 3 : }
621 :
622 9 : fd_reasm_fec_t * unconfrmd_leaf = NULL; /* 2nd best candidate for eviction is the highest unconfirmed, incomplete slot. */
623 9 : for( frontier_iter_t iter = frontier_iter_init( frontier, pool );
624 24 : !frontier_iter_done( iter, frontier, pool );
625 15 : iter = frontier_iter_next( iter, frontier, pool ) ) {
626 15 : fd_reasm_fec_t * ele = frontier_iter_ele( iter, frontier, pool );
627 15 : if( iter.ele_idx == reasm->root
628 15 : || 0==memcmp( &ele->key, parent_root, sizeof(fd_hash_t) )
629 15 : || ele->confirmed
630 15 : || ele->slot_complete
631 15 : || ele->is_leader ) continue; /* not a candidate */
632 9 : unconfrmd_leaf = fd_ptr_if( !unconfrmd_leaf || ele->slot > unconfrmd_leaf->slot, ele, unconfrmd_leaf );
633 9 : }
634 :
635 9 : if( FD_UNLIKELY( unconfrmd_leaf )) {
636 6 : return fd_reasm_remove( reasm, unconfrmd_leaf, opt_store );
637 6 : }
638 :
639 : /* Already did traversal to find best confirmed orphan candidate,
640 : which is the third choice */
641 :
642 3 : if( FD_UNLIKELY( confirmed_orphan )) {
643 0 : fd_reasm_fec_t * parent = fd_reasm_query( reasm, parent_root );
644 0 : if( !parent ) {
645 0 : return fd_reasm_remove( reasm, confirmed_orphan, opt_store );
646 0 : }
647 : /* for any subtree:
648 : 0 ── 1 ── 2 ── 3 (confirmed) ── 4(confirmed) ── 5 ── 6 ──> add 7 here is valid.
649 : └──> add 7 here is valid.
650 : └──> add 7 here is invalid. */
651 0 : ulong subtree_root = reasm->root;
652 0 : if( subtrees_ele_query( subtrees, parent_root, NULL, pool ) ||
653 0 : orphaned_ele_query( orphaned, parent_root, NULL, pool ) ) {
654 : /* if adding to an orphan, find the root of the orphan subtree. */
655 0 : fd_reasm_fec_t * root = parent;
656 0 : while( FD_LIKELY( root->parent != ULONG_MAX ) ) {
657 0 : root = pool_ele( pool, root->parent );
658 0 : }
659 0 : subtree_root = pool_idx( pool, root );
660 0 : }
661 :
662 0 : fd_reasm_fec_t * latest_confirmed_leaf = latest_confirmed_fec( reasm, subtree_root );
663 0 : if( !latest_confirmed_leaf || latest_confirmed_leaf == gca( reasm, latest_confirmed_leaf, parent )) {
664 0 : return fd_reasm_remove( reasm, confirmed_orphan, opt_store );
665 0 : }
666 : /* is a useless new fork. */
667 0 : return NULL;
668 0 : }
669 3 : return NULL; /* nothing else could be evicted */
670 3 : }
671 :
672 : fd_reasm_fec_t *
673 : fd_reasm_init( fd_reasm_t * reasm,
674 : fd_hash_t const * initial_block_id,
675 57 : ulong slot ) {
676 :
677 57 : fd_reasm_fec_t * pool = reasm_pool( reasm );
678 57 : ulong null = pool_idx_null( pool );
679 :
680 57 : FD_TEST( pool_free( pool ) );
681 57 : fd_reasm_fec_t * fec = pool_ele_acquire( pool );
682 57 : fec->key = *initial_block_id;
683 57 : fec->next = null;
684 57 : fec->parent = null;
685 57 : fec->child = null;
686 57 : fec->sibling = null;
687 57 : fec->slot = slot;
688 57 : fec->parent_off = 0;
689 57 : fec->fec_set_idx = 0U;
690 57 : fec->data_cnt = 0U;
691 57 : fec->data_complete = 0;
692 57 : fec->slot_complete = 1;
693 57 : fec->is_leader = 0;
694 57 : fec->eqvoc = 0;
695 57 : fec->confirmed = 0;
696 57 : fec->popped = 0;
697 57 : fec->bank_dead = 0;
698 57 : fec->bank_idx = null;
699 57 : fec->parent_bank_idx = null;
700 57 : fec->bank_seq = null;
701 57 : fec->out.next = null;
702 57 : fec->out.prev = null;
703 57 : fec->in_out = 0;
704 57 : fec->subtreel.next = null;
705 57 : fec->subtreel.prev = null;
706 :
707 :
708 57 : FD_TEST( reasm->root==pool_idx_null( pool ) );
709 57 : fec->confirmed = 1;
710 57 : fec->popped = 1;
711 57 : /* */ xid_update( reasm, slot, 0U, pool_idx( pool, fec ) );
712 57 : reasm->root = pool_idx( pool, fec );
713 57 : reasm->slot0 = slot;
714 57 : frontier_ele_insert( reasm->frontier, fec, pool );
715 57 : return fec;
716 57 : }
717 :
718 : fd_reasm_fec_t *
719 : fd_reasm_insert( fd_reasm_t * reasm,
720 : fd_hash_t const * merkle_root,
721 : fd_hash_t const * chained_merkle_root,
722 : ulong slot,
723 : uint fec_set_idx,
724 : ushort parent_off,
725 : ushort data_cnt,
726 : int data_complete,
727 : int slot_complete,
728 : int is_leader,
729 : fd_store_t * opt_store,
730 12615 : fd_reasm_fec_t ** evicted ) {
731 :
732 : # if LOGGING
733 : FD_BASE58_ENCODE_32_BYTES( merkle_root->key, merkle_root_b58 );
734 : FD_BASE58_ENCODE_32_BYTES( chained_merkle_root->key, chained_merkle_root_b58 );
735 : 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 ));
736 : # endif
737 :
738 12615 : fd_reasm_fec_t * pool = reasm_pool( reasm );
739 12615 : # if FD_REASM_USE_HANDHOLDING
740 12615 : FD_TEST( !fd_reasm_query( reasm, merkle_root ) );
741 12615 : # endif
742 :
743 12615 : FD_TEST( chained_merkle_root );
744 :
745 12615 : ulong null = pool_idx_null( pool );
746 12615 : ancestry_t * ancestry = reasm->ancestry;
747 12615 : frontier_t * frontier = reasm->frontier;
748 12615 : orphaned_t * orphaned = reasm->orphaned;
749 12615 : subtrees_t * subtrees = reasm->subtrees;
750 12615 : subtreel_t * subtreel = reasm->subtreel;
751 :
752 12615 : ulong * bfs = reasm->bfs;
753 12615 : out_t * out = reasm->out;
754 :
755 12615 : *evicted = NULL;
756 :
757 12615 : if( FD_UNLIKELY( pool_free( pool )==1UL ) ) {
758 12 : FD_TEST( reasm->root!=pool_idx_null( pool ) );
759 : /* The eviction removes evicted elements from the maps, but leaves
760 : the elements in the pool for caller to release. Thus, in order
761 : for the following insert/acquire to succeed, we have to start
762 : evicting when we have 1 remaining free element in the pool. This
763 : element is the one that will be acquired below. reasm is
764 : dependent on the caller to then release the evicted elements back
765 : to the pool before the next insert/acquire. */
766 12 : fd_reasm_fec_t * evicted_fec = evict( reasm, opt_store, merkle_root, chained_merkle_root );
767 12 : if( FD_UNLIKELY( evicted_fec == NULL ) ) {
768 3 : FD_LOG_INFO(("reasm failed to evict a fec set when inserting slot %lu fec set %u", slot, fec_set_idx));
769 :
770 : /* in this case we want to signal to the replay tile that we
771 : failed to insert the FEC set. This is effectively is the same
772 : logic as if we had this FEC set, and then it got evicted, and
773 : then the caller now needs to process the evicted FEC set. So
774 : here we acquire the final pool element for it and return it
775 : to the caller as the evicted FEC set. */
776 :
777 3 : fd_reasm_fec_t * fec = pool_ele_acquire( pool );
778 3 : fec->key = *merkle_root;
779 3 : fec->cmr = *chained_merkle_root;
780 3 : fec->parent = null;
781 3 : fec->child = null;
782 3 : fec->slot = slot;
783 3 : fec->parent_off = parent_off;
784 3 : fec->fec_set_idx = fec_set_idx;
785 3 : fec->bank_idx = null;
786 :
787 3 : *evicted = fec;
788 3 : return NULL;
789 3 : }
790 :
791 9 : *evicted = evicted_fec;
792 9 : }
793 :
794 12612 : FD_TEST( pool_free( pool ) );
795 12612 : fd_reasm_fec_t * fec = pool_ele_acquire( pool );
796 12612 : fec->key = *merkle_root;
797 12612 : fec->next = null;
798 12612 : fec->parent = null;
799 12612 : fec->child = null;
800 12612 : fec->sibling = null;
801 12612 : fec->slot = slot;
802 12612 : fec->parent_off = parent_off;
803 12612 : fec->fec_set_idx = fec_set_idx;
804 12612 : fec->data_cnt = data_cnt;
805 12612 : fec->data_complete = data_complete;
806 12612 : fec->slot_complete = slot_complete;
807 12612 : fec->is_leader = is_leader;
808 12612 : fec->eqvoc = 0;
809 12612 : fec->confirmed = 0;
810 12612 : fec->popped = 0;
811 12612 : fec->bank_dead = 0;
812 12612 : fec->bank_idx = null;
813 12612 : fec->parent_bank_idx = null;
814 12612 : fec->bank_seq = null;
815 :
816 : /* set the out and subtreel pointers to null */
817 12612 : fec->out.next = null;
818 12612 : fec->out.prev = null;
819 12612 : fec->in_out = 0;
820 12612 : fec->xid_next = null;
821 12612 : fec->subtreel.next = null;
822 12612 : fec->subtreel.prev = null;
823 :
824 12612 : fec->cmr = *chained_merkle_root;
825 :
826 12612 : fd_reasm_fec_t * parent = fd_reasm_query( reasm, chained_merkle_root );
827 12612 : if( FD_UNLIKELY( parent && !validate_chained_block_id( parent, fec ) ) ) {
828 27 : FD_BASE58_ENCODE_32_BYTES( fec->key.key, child_key_cstr );
829 27 : FD_BASE58_ENCODE_32_BYTES( parent->key.key, parent_key_cstr );
830 27 : FD_LOG_INFO(( "[%s] failed to validate chained block id FEC: (%lu %u %s). parent (%lu %u %s).", __func__, fec->slot, fec->fec_set_idx, child_key_cstr, parent->slot, parent->fec_set_idx, parent_key_cstr ));
831 27 : pool_ele_release( pool, fec );
832 27 : return NULL;
833 27 : }
834 :
835 : /* If the FEC's parent already exists link it correctly: the new FEC
836 : set may result in a new leaf or a new orphan tree root so we need
837 : to check that. */
838 :
839 12585 : parent = NULL;
840 12585 : if( FD_LIKELY( parent = ancestry_ele_query( ancestry, &fec->cmr, NULL, pool ) ) ) { /* parent is connected non-leaf */
841 48 : frontier_ele_insert( frontier, fec, pool );
842 48 : out_ele_push_tail( out, fec, pool );
843 48 : fec->in_out = 1;
844 12537 : } else if( FD_LIKELY ( parent = frontier_ele_remove( frontier, &fec->cmr, NULL, pool ) ) ) { /* parent is connected leaf */
845 192 : ancestry_ele_insert( ancestry, parent, pool );
846 192 : frontier_ele_insert( frontier, fec, pool );
847 192 : out_ele_push_tail( out, fec, pool );
848 192 : fec->in_out = 1;
849 12345 : } else if( FD_LIKELY ( parent = orphaned_ele_query( orphaned, &fec->cmr, NULL, pool ) ) ) { /* parent is orphaned non-root */
850 12282 : orphaned_ele_insert( orphaned, fec, pool );
851 12282 : } else if( FD_LIKELY ( parent = subtrees_ele_query( subtrees, &fec->cmr, NULL, pool ) ) ) { /* parent is orphaned root */
852 12 : orphaned_ele_insert( orphaned, fec, pool );
853 51 : } else { /* parent not found */
854 51 : subtrees_ele_insert( subtrees, fec, pool );
855 51 : subtreel_ele_push_tail( subtreel, fec, pool );
856 51 : }
857 :
858 12585 : if( FD_LIKELY( parent ) ) link( reasm, parent, fec );
859 :
860 : /* Second, we search for children of this new FEC and link them to it.
861 : By definition any children must be orphaned (a child cannot be part
862 : of a connected tree before its parent). Therefore, we only search
863 : through the orphaned subtrees. As part of this operation, we also
864 : coalesce orphans into orphan subtrees. An orphan may be connected
865 : to its parent, but part of an orphaned subtree. This way we only
866 : need to search for children the orphan subtree roots (vs. all
867 : orphaned nodes). */
868 :
869 12585 : ulong min_descendant = ULONG_MAX; /* needed for eqvoc checks below */
870 12585 : FD_TEST( bfs_empty( bfs ) );
871 12585 : for( subtreel_iter_t iter = subtreel_iter_fwd_init( subtreel, pool );
872 24999 : !subtreel_iter_done ( iter, subtreel, pool );
873 12585 : iter = subtreel_iter_fwd_next( iter, subtreel, pool ) ) {
874 12414 : fd_reasm_fec_t * parent = fec;
875 12414 : fd_reasm_fec_t * child = subtreel_iter_ele( iter, subtreel, pool );
876 12414 : if( FD_UNLIKELY( !fd_hash_eq( &parent->key, &child->cmr ) ) ) continue;
877 45 : if( FD_UNLIKELY( !validate_chained_block_id( parent, child ) ) ) {
878 9 : FD_BASE58_ENCODE_32_BYTES( child->key.key, child_key_cstr );
879 9 : FD_BASE58_ENCODE_32_BYTES( parent->key.key, parent_key_cstr );
880 9 : FD_LOG_INFO(( "[%s] failed to validate chained block id FEC: (%lu %u %s). parent (%lu %u %s).", __func__, child->slot, child->fec_set_idx, child_key_cstr, parent->slot, parent->fec_set_idx, parent_key_cstr ));
881 9 : subtrees_remove( reasm, child, opt_store );
882 9 : continue;
883 9 : }
884 36 : link( reasm, parent, child );
885 36 : subtrees_ele_remove( subtrees, &child->key, NULL, pool );
886 36 : subtreel_ele_remove( subtreel, child, pool );
887 36 : orphaned_ele_insert( orphaned, child, pool );
888 36 : min_descendant = fd_ulong_min( min_descendant, child->slot );
889 36 : }
890 :
891 : /* Third, we advance the frontier outward beginning from fec as we may
892 : have connected orphaned descendants to fec in the above step. This
893 : does a BFS outward from fec until it reaches leaves, moving fec and
894 : its non-leaf descendants into ancestry and leaves into frontier.
895 :
896 : parent (ancestry) orphan root (subtrees)
897 : | |
898 : fec (frontier) orphan child (orphaned)
899 :
900 : parent
901 : |
902 : fec <- frontier is here
903 : |
904 : orphan root
905 : |
906 : orphan child <- advance to here */
907 :
908 12585 : if( FD_LIKELY( frontier_ele_query( frontier, &fec->key, NULL, pool ) ) ) bfs_push_tail( bfs, pool_idx( pool, fec ) );
909 12864 : while( FD_LIKELY( !bfs_empty( bfs ) ) ) {
910 279 : fd_reasm_fec_t * parent = pool_ele( pool, bfs_pop_head( bfs ) );
911 279 : fd_reasm_fec_t * child = pool_ele( pool, parent->child );
912 279 : if( FD_LIKELY( child ) ) {
913 33 : frontier_ele_remove( frontier, &parent->key, NULL, pool );
914 33 : ancestry_ele_insert( ancestry, parent, pool );
915 33 : }
916 318 : while( FD_LIKELY( child ) ) {
917 39 : FD_TEST( orphaned_ele_remove( orphaned, &child->key, NULL, pool ) );
918 39 : frontier_ele_insert( frontier, child, pool );
919 39 : bfs_push_tail( bfs, pool_idx( pool, child ) );
920 39 : out_ele_push_tail( out, child, pool );
921 39 : child->in_out = 1;
922 39 : child = pool_ele( pool, child->sibling );
923 39 : }
924 279 : }
925 :
926 : /* Fourth, check and handle equivocation. There are three cases.
927 :
928 : 1. we've already seen this FEC's xid (slot, fec_set_idx)
929 : 2. this FEC's parent equivocates. */
930 :
931 12585 : xid_t * xid = xid_query( reasm->xid, (slot<<32) | fec_set_idx, NULL );
932 12585 : if( FD_UNLIKELY( xid ) ) {
933 42 : eqvoc( reasm, fec );
934 42 : eqvoc( reasm, pool_ele( pool, xid->idx ) ); /* most recent appearance of this xid */
935 : /* We can call eqvoc on the head of the xid list because we maintain
936 : the order of most recent to least recent. Inductively, this marks
937 : all FECs with the same xid as equivocating. */
938 42 : }
939 12585 : xid_update( reasm, slot, fec_set_idx, pool_idx( pool, fec ) );
940 12585 : if( FD_UNLIKELY( parent && parent->eqvoc && !parent->confirmed ) ) eqvoc( reasm, fec );
941 :
942 : /* Finally, return the newly inserted FEC. */
943 12585 : return fec;
944 12585 : }
945 :
946 : fd_reasm_fec_t *
947 : fd_reasm_publish( fd_reasm_t * reasm,
948 : fd_hash_t const * merkle_root,
949 15 : fd_store_t * opt_store ) {
950 :
951 15 : # if FD_REASM_USE_HANDHOLDING
952 15 : if( FD_UNLIKELY( !pool_ele( reasm_pool( reasm ), reasm->root ) ) ) { FD_LOG_WARNING(( "missing root" )); return NULL; }
953 15 : if( FD_UNLIKELY( !fd_reasm_query( reasm, merkle_root ) ) ) {
954 0 : FD_BASE58_ENCODE_32_BYTES( merkle_root->key, merkle_root_b58 );
955 0 : FD_LOG_WARNING(( "merkle root %s not found", merkle_root_b58 ));
956 0 : return NULL;
957 0 : }
958 15 : # endif
959 :
960 15 : fd_reasm_fec_t * pool = reasm_pool( reasm );
961 15 : ulong null = pool_idx_null( pool );
962 15 : fd_reasm_fec_t * oldr = pool_ele( pool, reasm->root );
963 15 : fd_reasm_fec_t * newr = fd_reasm_query( reasm, merkle_root );
964 15 : ulong * bfs = reasm->bfs;
965 :
966 15 : bfs_push_tail( bfs, pool_idx( pool, oldr ) );
967 :
968 : /* First, BFS down the tree, pruning all of root's ancestors and also
969 : any descendants of those ancestors. */
970 :
971 : /* Also, prune any subtrees who's root is less than the new root. */
972 :
973 15 : subtreel_t * subtreel = reasm->subtreel;
974 15 : for( subtreel_iter_t iter = subtreel_iter_fwd_init( subtreel, pool );
975 15 : !subtreel_iter_done ( iter, subtreel, pool );
976 15 : iter = subtreel_iter_fwd_next( iter, subtreel, pool ) ) {
977 0 : fd_reasm_fec_t * ele = subtreel_iter_ele( iter, subtreel, pool );
978 0 : if( ele->slot < newr->slot ) {
979 0 : bfs_push_tail( bfs, pool_idx( pool, ele ) );
980 0 : }
981 0 : }
982 :
983 72 : while( FD_LIKELY( !bfs_empty( bfs ) ) ) {
984 57 : fd_reasm_fec_t * head = pool_ele( pool, bfs_pop_head( bfs ) );
985 :
986 57 : fd_reasm_fec_t * fec = ancestry_ele_remove( reasm->ancestry, &head->key, NULL, pool );
987 57 : if( FD_UNLIKELY( !fec ) ) fec = frontier_ele_remove( reasm->frontier, &head->key, NULL, pool );
988 57 : if( FD_UNLIKELY( !fec ) ) fec = orphaned_ele_remove( reasm->orphaned, &head->key, NULL, pool );
989 57 : if( FD_UNLIKELY( !fec ) ) {
990 0 : fec = subtrees_ele_remove( reasm->subtrees, &head->key, NULL, pool );
991 0 : subtreel_ele_remove( reasm->subtreel, head, pool );
992 0 : }
993 :
994 57 : fd_reasm_fec_t * child = pool_ele( pool, head->child );
995 114 : while( FD_LIKELY( child ) ) { /* iterate over children */
996 57 : if( FD_LIKELY( child != newr ) ) { /* stop at new root */
997 42 : bfs_push_tail( bfs, pool_idx( pool, child ) );
998 42 : }
999 57 : child = pool_ele( pool, child->sibling ); /* right-sibling */
1000 57 : }
1001 57 : clear_xid_metadata( reasm, head );
1002 57 : if( FD_LIKELY( opt_store ) ) fd_store_remove( opt_store, &head->key );
1003 57 : if( FD_LIKELY( head->in_out ) ) { out_ele_remove( reasm->out, head, pool ); head->in_out = 0; }
1004 57 : pool_ele_release( pool, head );
1005 57 : }
1006 :
1007 15 : newr->parent = null; /* unlink old root */
1008 15 : newr->sibling = null;
1009 15 : reasm->root = pool_idx( pool, newr ); /* replace with new root */
1010 15 : return newr;
1011 15 : }
1012 :
1013 : #include <stdio.h>
1014 :
1015 : FD_FN_UNUSED static void
1016 0 : print( fd_reasm_t const * reasm, fd_reasm_fec_t const * fec, int space, const char * prefix ) {
1017 0 : fd_reasm_fec_t const * pool = reasm_pool_const( reasm );
1018 0 :
1019 0 : if( fec == NULL ) return;
1020 0 :
1021 0 : if( space > 0 ) printf( "\n" );
1022 0 : for( int i = 0; i < space; i++ ) printf( " " );
1023 0 : FD_BASE58_ENCODE_32_BYTES( fec->key.key, key_b58 );
1024 0 : printf( "%s%s", prefix, key_b58 );
1025 0 :
1026 0 : fd_reasm_fec_t const * curr = pool_ele_const( pool, fec->child );
1027 0 : char new_prefix[1024]; /* FIXME size this correctly */
1028 0 : while( curr ) {
1029 0 : if( pool_ele_const( pool, curr->sibling ) ) {
1030 0 : sprintf( new_prefix, "├── " ); /* branch indicating more siblings follow */
1031 0 : print( reasm, curr, space + 4, new_prefix );
1032 0 : } else {
1033 0 : sprintf( new_prefix, "└── " ); /* end branch */
1034 0 : print( reasm, curr, space + 4, new_prefix );
1035 0 : }
1036 0 : curr = pool_ele_const( pool, curr->sibling );
1037 0 : }
1038 0 : }
1039 :
1040 : static void
1041 42 : 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 ) {
1042 42 : fd_reasm_fec_t const * pool = reasm_pool_const( reasm );
1043 42 : if( fec == NULL ) return;
1044 42 : recurse_depth++;
1045 42 : if( recurse_depth == 2048 ) {
1046 0 : FD_BASE58_ENCODE_32_BYTES( fec->key.key, key_b58 );
1047 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 ));
1048 0 : return;
1049 0 : }
1050 42 : fd_reasm_fec_t const * child = fd_reasm_child_const( reasm, fec );
1051 :
1052 42 : if( !prev || /* root OR */
1053 42 : ( fec->slot_complete || (!prev->eqvoc && fec->eqvoc) || fec->child == pool_idx_null( pool ) || child->sibling != pool_idx_null( pool ) )) {
1054 39 : if( space > 0 ) printf( "\n" );
1055 384 : for( int i = 0; i < space; i++ ) printf( " " );
1056 39 : printf( "%s", prefix );
1057 :
1058 39 : FD_BASE58_ENCODE_32_BYTES( fec->key.key, key_b58 );
1059 39 : key_b58[5] = '\0'; /* only print first 5 characters of key_b58 */
1060 39 : printf( "%lu(%u) %s", fec->slot, fec->fec_set_idx, key_b58 );
1061 39 : if( fec->eqvoc ) printf( " [eqvoc]" );
1062 39 : if( fec->is_leader ) printf( " [leader]" );
1063 39 : space += 5;
1064 39 : fflush(stdout);
1065 39 : }
1066 :
1067 42 : char new_prefix[1024]; /* FIXME size this correctly */
1068 :
1069 75 : while( child ) {
1070 33 : if( pool_ele_const( pool, child->sibling ) ) {
1071 9 : sprintf( new_prefix, "├── " ); /* branch indicating more siblings follow */
1072 9 : ancestry_print( reasm, child, space, new_prefix, fec, recurse_depth );
1073 24 : } else {
1074 24 : sprintf( new_prefix, "└── " ); /* end branch */
1075 24 : ancestry_print( reasm, child, space, new_prefix, fec, recurse_depth );
1076 24 : }
1077 33 : child = pool_ele_const( pool, child->sibling );
1078 33 : }
1079 42 : }
1080 :
1081 : void
1082 6 : fd_reasm_print( fd_reasm_t const * reasm ) {
1083 6 : FD_LOG_NOTICE( ( "\n\n[Reasm - showing only leaves, slot completes, and branches]" ) );
1084 6 : fd_reasm_fec_t const * pool = reasm_pool_const( reasm );
1085 6 : printf( "ele cnt: %lu\n", pool_used( pool ) );
1086 :
1087 6 : if( FD_LIKELY( reasm->root != pool_idx_null( pool ) ) ) {
1088 6 : printf( "\n\n[Connected Fecs]\n" );
1089 6 : ancestry_print( reasm, fd_reasm_root_const( reasm ), 0, "", NULL, 0 );
1090 6 : }
1091 :
1092 6 : printf( "\n\n[Unconnected Fecs]\n" );
1093 6 : subtreel_t const * subtreel = reasm->_subtrlf;
1094 6 : for( subtreel_iter_t iter = subtreel_iter_fwd_init( subtreel, pool );
1095 9 : !subtreel_iter_done ( iter, subtreel, pool );
1096 6 : iter = subtreel_iter_fwd_next( iter, subtreel, pool ) ) {
1097 3 : fd_reasm_fec_t const * fec = subtreel_iter_ele_const( iter, subtreel, pool );
1098 3 : ancestry_print( reasm, fec, 0, "", NULL, 0 );
1099 3 : }
1100 :
1101 6 : printf( "\n\n" );
1102 : fflush(stdout);
1103 6 : }
|
