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