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