Line data Source code
1 : #include "fd_reasm.h"
2 : #include "fd_reasm_private.h"
3 :
4 : #define LOGGING 0
5 :
6 : FD_FN_CONST ulong
7 78 : fd_reasm_align( void ) {
8 78 : return alignof(fd_reasm_t);
9 78 : }
10 :
11 : ulong
12 18 : fd_reasm_footprint( ulong fec_max ) {
13 18 : int lgf_max = fd_ulong_find_msb( fd_ulong_pow2_up( fec_max ) );
14 18 : return FD_LAYOUT_FINI(
15 18 : FD_LAYOUT_APPEND(
16 18 : FD_LAYOUT_APPEND(
17 18 : FD_LAYOUT_APPEND(
18 18 : FD_LAYOUT_APPEND(
19 18 : FD_LAYOUT_APPEND(
20 18 : FD_LAYOUT_APPEND(
21 18 : FD_LAYOUT_APPEND(
22 18 : FD_LAYOUT_APPEND(
23 18 : FD_LAYOUT_APPEND(
24 18 : FD_LAYOUT_INIT,
25 18 : alignof(fd_reasm_t), sizeof(fd_reasm_t) ),
26 18 : pool_align(), pool_footprint ( fec_max ) ),
27 18 : ancestry_align(), ancestry_footprint( fec_max ) ),
28 18 : frontier_align(), frontier_footprint( fec_max ) ),
29 18 : orphaned_align(), orphaned_footprint( fec_max ) ),
30 18 : subtrees_align(), subtrees_footprint( fec_max ) ),
31 18 : bfs_align(), bfs_footprint ( fec_max ) ),
32 18 : out_align(), out_footprint ( fec_max ) ),
33 18 : slot_mr_align(), slot_mr_footprint ( lgf_max ) ),
34 18 : fd_reasm_align() );
35 18 : }
36 :
37 : void *
38 9 : fd_reasm_new( void * shmem, ulong fec_max, ulong seed ) {
39 :
40 9 : if( FD_UNLIKELY( !shmem ) ) {
41 0 : FD_LOG_WARNING(( "NULL mem" ));
42 0 : return NULL;
43 0 : }
44 :
45 9 : if( FD_UNLIKELY( !fd_ulong_is_aligned( (ulong)shmem, fd_reasm_align() ) ) ) {
46 0 : FD_LOG_WARNING(( "misaligned mem" ));
47 0 : return NULL;
48 0 : }
49 :
50 9 : ulong footprint = fd_reasm_footprint( fec_max );
51 9 : if( FD_UNLIKELY( !footprint ) ) {
52 0 : FD_LOG_WARNING(( "bad fec_max (%lu)", fec_max ));
53 0 : return NULL;
54 0 : }
55 :
56 9 : fd_wksp_t * wksp = fd_wksp_containing( shmem );
57 9 : if( FD_UNLIKELY( !wksp ) ) {
58 0 : FD_LOG_WARNING(( "shmem must be part of a workspace" ));
59 0 : return NULL;
60 0 : }
61 :
62 9 : fd_memset( shmem, 0, footprint );
63 :
64 9 : int lgf_max = fd_ulong_find_msb( fd_ulong_pow2_up( fec_max ) );
65 :
66 9 : fd_reasm_t * reasm;
67 9 : FD_SCRATCH_ALLOC_INIT( l, shmem );
68 9 : reasm = FD_SCRATCH_ALLOC_APPEND( l, alignof(fd_reasm_t), sizeof(fd_reasm_t) );
69 9 : void * pool = FD_SCRATCH_ALLOC_APPEND( l, pool_align(), pool_footprint ( fec_max ) );
70 9 : void * ancestry = FD_SCRATCH_ALLOC_APPEND( l, ancestry_align(), ancestry_footprint( fec_max ) );
71 9 : void * frontier = FD_SCRATCH_ALLOC_APPEND( l, frontier_align(), frontier_footprint( fec_max ) );
72 9 : void * orphaned = FD_SCRATCH_ALLOC_APPEND( l, orphaned_align(), orphaned_footprint( fec_max ) );
73 9 : void * subtrees = FD_SCRATCH_ALLOC_APPEND( l, subtrees_align(), subtrees_footprint( fec_max ) );
74 9 : void * bfs = FD_SCRATCH_ALLOC_APPEND( l, bfs_align(), bfs_footprint ( fec_max ) );
75 9 : void * out = FD_SCRATCH_ALLOC_APPEND( l, out_align(), out_footprint ( fec_max ) );
76 9 : void * slot_mr = FD_SCRATCH_ALLOC_APPEND( l, slot_mr_align(), slot_mr_footprint ( lgf_max ) );
77 9 : FD_TEST( FD_SCRATCH_ALLOC_FINI( l, fd_reasm_align() ) == (ulong)shmem + footprint );
78 :
79 9 : reasm->slot0 = ULONG_MAX;
80 9 : reasm->root = pool_idx_null( pool );
81 9 : reasm->pool = pool_new ( pool, fec_max );
82 9 : reasm->ancestry = ancestry_new ( ancestry, fec_max, seed );
83 9 : reasm->frontier = frontier_new ( frontier, fec_max, seed );
84 9 : reasm->orphaned = orphaned_new ( orphaned, fec_max, seed );
85 9 : reasm->subtrees = subtrees_new ( subtrees, fec_max, seed );
86 9 : /* */ subtreel_new ( reasm->_subtrlf );
87 9 : reasm->bfs = bfs_new ( bfs, fec_max );
88 9 : reasm->out = out_new ( out, fec_max );
89 9 : reasm->slot_mr = slot_mr_new ( slot_mr, lgf_max );
90 :
91 9 : return shmem;
92 9 : }
93 :
94 : fd_reasm_t *
95 9 : fd_reasm_join( void * shreasm ) {
96 9 : fd_reasm_t * reasm = (fd_reasm_t *)shreasm;
97 :
98 9 : if( FD_UNLIKELY( !reasm ) ) {
99 0 : FD_LOG_WARNING(( "NULL reasm" ));
100 0 : return NULL;
101 0 : }
102 :
103 9 : reasm->pool = pool_join ( reasm->pool );
104 9 : reasm->ancestry = ancestry_join( reasm->ancestry );
105 9 : reasm->frontier = frontier_join( reasm->frontier );
106 9 : reasm->orphaned = orphaned_join( reasm->orphaned );
107 9 : reasm->subtrees = subtrees_join( reasm->subtrees );
108 9 : reasm->subtreel = subtreel_join( reasm->_subtrlf );
109 9 : reasm->bfs = bfs_join ( reasm->bfs );
110 9 : reasm->out = out_join ( reasm->out );
111 9 : reasm->slot_mr = slot_mr_join ( reasm->slot_mr );
112 :
113 9 : return reasm;
114 9 : }
115 :
116 : void *
117 6 : fd_reasm_leave( fd_reasm_t * reasm ) {
118 :
119 6 : if( FD_UNLIKELY( !reasm ) ) {
120 0 : FD_LOG_WARNING(( "NULL reasm" ));
121 0 : return NULL;
122 0 : }
123 :
124 6 : return (void *)reasm;
125 6 : }
126 :
127 : void *
128 6 : fd_reasm_delete( void * shreasm ) {
129 6 : fd_reasm_t * reasm = (fd_reasm_t *)shreasm;
130 :
131 6 : if( FD_UNLIKELY( !reasm ) ) {
132 0 : FD_LOG_WARNING(( "NULL reasm" ));
133 0 : return NULL;
134 0 : }
135 :
136 6 : if( FD_UNLIKELY( !fd_ulong_is_aligned((ulong)reasm, fd_reasm_align() ) ) ) {
137 0 : FD_LOG_WARNING(( "misaligned reasm" ));
138 0 : return NULL;
139 0 : }
140 :
141 6 : return reasm;
142 6 : }
143 :
144 6 : fd_reasm_fec_t * fd_reasm_root ( fd_reasm_t * reasm ) { return pool_ele ( reasm->pool, reasm->root ); }
145 0 : fd_reasm_fec_t const * fd_reasm_root_const ( fd_reasm_t const * reasm ) { return pool_ele_const( reasm->pool, reasm->root ); }
146 0 : fd_reasm_fec_t * fd_reasm_parent ( fd_reasm_t * reasm, fd_reasm_fec_t * child ) { return pool_ele ( reasm->pool, child->parent ); }
147 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, child->parent ); }
148 0 : fd_reasm_fec_t * fd_reasm_child ( fd_reasm_t * reasm, fd_reasm_fec_t * parent ) { return pool_ele ( reasm->pool, parent->child ); }
149 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, parent->child ); }
150 0 : fd_reasm_fec_t * fd_reasm_sibling ( fd_reasm_t * reasm, fd_reasm_fec_t * sibling ) { return pool_ele ( reasm->pool, sibling->sibling ); }
151 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, sibling->sibling ); }
152 :
153 : ulong
154 0 : fd_reasm_slot0( fd_reasm_t * reasm ) {
155 0 : return reasm->slot0;
156 0 : }
157 :
158 : ulong
159 0 : fd_reasm_free( fd_reasm_t * reasm ) {
160 0 : return pool_free( reasm->pool );
161 0 : }
162 :
163 : fd_reasm_fec_t *
164 24 : fd_reasm_out( fd_reasm_t * reasm ) {
165 24 : if( FD_UNLIKELY( out_empty( reasm->out ) ) ) return NULL;
166 21 : return pool_ele( reasm->pool, out_pop_head( reasm->out ) );
167 24 : }
168 :
169 : fd_reasm_fec_t *
170 : fd_reasm_query( fd_reasm_t const * reasm,
171 180 : fd_hash_t const * merkle_root ) {
172 180 : fd_reasm_fec_t * fec = NULL;
173 180 : fec = ancestry_ele_query( reasm->ancestry, merkle_root, NULL, reasm->pool );
174 180 : fec = fd_ptr_if( !fec, frontier_ele_query( reasm->frontier, merkle_root, NULL, reasm->pool ), fec );
175 180 : fec = fd_ptr_if( !fec, orphaned_ele_query( reasm->orphaned, merkle_root, NULL, reasm->pool ), fec );
176 180 : fec = fd_ptr_if( !fec, subtrees_ele_query( reasm->subtrees, merkle_root, NULL, reasm->pool ), fec );
177 180 : return fec;
178 180 : }
179 :
180 : static void
181 123 : overwrite_invalid_cmr( fd_reasm_t * reasm, fd_reasm_fec_t * child ) {
182 123 : if( FD_UNLIKELY( child->fec_set_idx==0 && !fd_reasm_query( reasm, &child->cmr ) ) ) {
183 54 : slot_mr_t * slot_mr_parent = slot_mr_query( reasm->slot_mr, child->slot - child->parent_off, NULL );
184 54 : if( FD_LIKELY( slot_mr_parent ) ) {
185 6 : fd_reasm_fec_t * parent = fd_reasm_query( reasm, &slot_mr_parent->block_id );
186 6 : if( FD_LIKELY( parent ) ) {
187 6 : FD_LOG_INFO(( "overwriting invalid cmr for FEC slot: %lu fec_set_idx: %u from %s (CMR) to %s (parent's block id)", child->slot, child->fec_set_idx, FD_BASE58_ENC_32_ALLOCA( &child->cmr ), FD_BASE58_ENC_32_ALLOCA( &parent->key ) ));
188 6 : child->cmr = parent->key; /* use the parent's merkle root */
189 6 : }
190 6 : }
191 54 : }
192 123 : }
193 :
194 : static void
195 : link( fd_reasm_t * reasm,
196 : fd_reasm_fec_t * parent,
197 54 : fd_reasm_fec_t * child ) {
198 54 : child->parent = pool_idx( reasm->pool, parent );
199 54 : if( FD_LIKELY( parent->child == pool_idx_null( reasm->pool ) ) ) {
200 45 : parent->child = pool_idx( reasm->pool, child ); /* set as left-child. */
201 45 : } else {
202 9 : fd_reasm_fec_t * curr = pool_ele( reasm->pool, parent->child );
203 9 : while( curr->sibling != pool_idx_null( reasm->pool ) ) curr = pool_ele( reasm->pool, curr->sibling );
204 9 : curr->sibling = pool_idx( reasm->pool, child ); /* set as right-sibling. */
205 9 : if( FD_UNLIKELY( !parent->slot_complete ) ) child->eqvoc = 1; /* set to equivocating */
206 9 : }
207 54 : }
208 :
209 : fd_reasm_fec_t *
210 : fd_reasm_insert( fd_reasm_t * reasm,
211 : fd_hash_t const * merkle_root,
212 : fd_hash_t const * chained_merkle_root,
213 : ulong slot,
214 : uint fec_set_idx,
215 : ushort parent_off,
216 : ushort data_cnt,
217 : int data_complete,
218 : int slot_complete,
219 63 : int leader ) {
220 :
221 : # if LOGGING
222 : FD_LOG_NOTICE(( "inserting (%lu %u) %s %s. %u %d %d", slot, fec_set_idx, FD_BASE58_ENC_32_ALLOCA( merkle_root ), FD_BASE58_ENC_32_ALLOCA( chained_merkle_root ), data_cnt, data_complete, slot_complete ));
223 : # endif
224 :
225 63 : # if FD_REASM_USE_HANDHOLDING
226 63 : FD_TEST( pool_free( reasm->pool ) );
227 63 : FD_TEST( !fd_reasm_query( reasm, merkle_root ) );
228 63 : # endif
229 :
230 63 : fd_reasm_fec_t * pool = reasm->pool;
231 63 : ulong null = pool_idx_null( pool );
232 :
233 63 : ancestry_t * ancestry = reasm->ancestry;
234 63 : frontier_t * frontier = reasm->frontier;
235 63 : orphaned_t * orphaned = reasm->orphaned;
236 63 : subtrees_t * subtrees = reasm->subtrees;
237 63 : subtreel_t * subtreel = reasm->subtreel;
238 :
239 63 : ulong * bfs = reasm->bfs;
240 63 : ulong * out = reasm->out;
241 :
242 63 : fd_reasm_fec_t * fec = pool_ele_acquire( pool );
243 63 : fec->key = *merkle_root;
244 63 : fec->next = null;
245 63 : fec->parent = null;
246 63 : fec->child = null;
247 63 : fec->sibling = null;
248 63 : fec->slot = slot;
249 63 : fec->parent_off = parent_off;
250 63 : fec->fec_set_idx = fec_set_idx;
251 63 : fec->data_cnt = data_cnt;
252 63 : fec->data_complete = data_complete;
253 63 : fec->slot_complete = slot_complete;
254 63 : fec->leader = leader;
255 63 : fec->eqvoc = 0;
256 63 : fec->bank_idx = null;
257 63 : fec->parent_bank_idx = null;
258 :
259 63 : if( FD_UNLIKELY( !chained_merkle_root ) ) { /* initialize the reasm with the root */
260 9 : FD_TEST( reasm->root==pool_idx_null( reasm->pool ) );
261 9 : slot_mr_t * slot_mr = slot_mr_insert( reasm->slot_mr, slot );
262 9 : slot_mr->block_id = fec->key;
263 9 : reasm->root = pool_idx( pool, fec );
264 9 : reasm->slot0 = slot;
265 9 : frontier_ele_insert( reasm->frontier, fec, pool );
266 9 : return fec;
267 9 : }
268 :
269 54 : fec->cmr = *chained_merkle_root;
270 :
271 : /* This is a gross case reasm needs to handle because Agave currently
272 : does not validate chained merkle roots across slots ie. if a leader
273 : sends a bad chained merkle root on a slot boundary, the cluster
274 : might converge on the leader's block anyways. So we overwrite the
275 : chained merkle root based on the slot and parent_off metadata.
276 : There are two cases: 1. we receive the parent before the child. In
277 : this case we just overwrite the child's CMR. 2. we receive the
278 : child before the parent. In this case every time we receive a new
279 : FEC set we need to check the orphan roots for whether we can link
280 : the orphan to the new FEC via slot metadata, since the chained
281 : merkle root metadata on that orphan root might be wrong. */
282 :
283 54 : if( FD_UNLIKELY( slot_complete ) ) {
284 39 : slot_mr_t * slot_mr = slot_mr_query( reasm->slot_mr, slot, NULL );
285 39 : if( FD_UNLIKELY( slot_mr ) ) {
286 3 : FD_LOG_WARNING(( "equivocating block_id for FEC slot: %lu fec_set_idx: %u prev: %s curr: %s", fec->slot, fec->fec_set_idx, FD_BASE58_ENC_32_ALLOCA( &slot_mr->block_id ), FD_BASE58_ENC_32_ALLOCA( &fec->key ) )); /* it's possible there's equivocation... */
287 36 : } else {
288 36 : slot_mr = slot_mr_insert( reasm->slot_mr, slot );
289 36 : slot_mr->block_id = fec->key;
290 36 : }
291 39 : }
292 54 : overwrite_invalid_cmr( reasm, fec ); /* handle receiving parent before child */
293 :
294 : /* First, we search for the parent of this new FEC and link if found.
295 : The new FEC set may result in a new leaf or a new orphan tree root
296 : so we need to check that. */
297 :
298 54 : fd_reasm_fec_t * parent = NULL;
299 54 : if( FD_LIKELY( parent = ancestry_ele_query ( ancestry, &fec->cmr, NULL, pool ) ) ) { /* parent is connected non-leaf */
300 6 : frontier_ele_insert( frontier, fec, pool );
301 6 : out_push_tail( out, pool_idx( pool, fec ) );
302 48 : } else if( FD_LIKELY( parent = frontier_ele_remove( frontier, &fec->cmr, NULL, pool ) ) ) { /* parent is connected leaf */
303 21 : ancestry_ele_insert( ancestry, parent, pool );
304 21 : frontier_ele_insert( frontier, fec, pool );
305 21 : out_push_tail( out, pool_idx( pool, fec ) );
306 27 : } else if( FD_LIKELY( parent = orphaned_ele_query ( orphaned, &fec->cmr, NULL, pool ) ) ) { /* parent is orphaned non-root */
307 0 : orphaned_ele_insert( orphaned, fec, pool );
308 27 : } else if( FD_LIKELY( parent = subtrees_ele_query ( subtrees, &fec->cmr, NULL, pool ) ) ) { /* parent is orphaned root */
309 0 : orphaned_ele_insert( orphaned, fec, pool );
310 27 : } else { /* parent not found */
311 27 : subtrees_ele_insert ( subtrees, fec, pool );
312 27 : subtreel_ele_push_tail( subtreel, fec, pool );
313 27 : }
314 :
315 54 : if( FD_LIKELY( parent ) ) link( reasm, parent, fec );
316 :
317 : /* Second, we search for children of this new FEC and link them to it.
318 : By definition any children must be orphaned (a child cannot be part
319 : of a connected tree before its parent). Therefore, we only search
320 : through the orphaned subtrees. As part of this operation, we also
321 : coalesce connected orphans into the same tree. This way we only
322 : need to search the orphan tree roots (vs. all orphaned nodes). */
323 :
324 54 : FD_TEST( bfs_empty( bfs ) );
325 54 : for( subtreel_iter_t iter = subtreel_iter_fwd_init( subtreel, pool );
326 123 : !subtreel_iter_done ( iter, subtreel, pool );
327 69 : iter = subtreel_iter_fwd_next( iter, subtreel, pool ) ) {
328 69 : bfs_push_tail( bfs, subtreel_iter_idx( iter, subtreel, pool ) );
329 69 : }
330 :
331 : /* connects subtrees to the new FEC */
332 123 : while( FD_LIKELY( !bfs_empty( bfs ) ) ) {
333 69 : fd_reasm_fec_t * orphan_root = pool_ele( reasm->pool, bfs_pop_head( bfs ) );
334 69 : overwrite_invalid_cmr( reasm, orphan_root ); /* handle receiving child before parent */
335 69 : if( FD_LIKELY( orphan_root && 0==memcmp( orphan_root->cmr.uc, fec->key.uc, sizeof(fd_hash_t) ) ) ) { /* this orphan_root is a direct child of fec */
336 27 : link( reasm, fec, orphan_root );
337 27 : subtrees_ele_remove( subtrees, &orphan_root->key, NULL, pool );
338 27 : subtreel_ele_remove( subtreel, orphan_root, pool );
339 27 : orphaned_ele_insert( orphaned, orphan_root, pool );
340 27 : }
341 69 : }
342 :
343 : /* At this point we are in a state where:
344 :
345 : ele < in frontier/subtrees/orphaned >
346 : |
347 : children < all in orphaned >
348 :
349 : if ele is in orphaned/subtrees, we are done and this state is
350 : correct.
351 : if ele is an frontier, then we need to extend the
352 : frontier from this ele. (make ele and all its children the ancestry,
353 : except the leaf, which needs to be added to the frontier).
354 : it's not possible for ele to be in ancestry at this point! */
355 :
356 : /* Third, we advance the frontier beginning from this FEC, if it was
357 : connected. By definition if this FEC was connected then its parent
358 : is connected, so by induction this new FEC extends the frontier.
359 : However, even though we have already inserted this new FEC into the
360 : frontier it is not necessarily a leaf, as it may have connected to
361 : orphaned children. So we BFS the from the new FEC outward until we
362 : reach the leaves. */
363 :
364 54 : if( FD_LIKELY( frontier_ele_query( frontier, &fec->key, NULL, pool ) ) ) bfs_push_tail( bfs, pool_idx( pool, fec ) );
365 108 : while( FD_LIKELY( !bfs_empty( bfs ) ) ) {
366 54 : fd_reasm_fec_t * parent = pool_ele( pool, bfs_pop_head( bfs ) );
367 54 : fd_reasm_fec_t * child = pool_ele( pool, parent->child );
368 54 : if( FD_LIKELY( child ) ) {
369 24 : frontier_ele_remove( frontier, &parent->key, NULL, pool );
370 24 : ancestry_ele_insert( ancestry, parent, pool );
371 24 : }
372 81 : while( FD_LIKELY( child ) ) {
373 27 : FD_TEST( orphaned_ele_remove( orphaned, &child->key, NULL, pool ) );
374 27 : frontier_ele_insert( frontier, child, pool );
375 27 : bfs_push_tail( bfs, pool_idx( pool, child ) );
376 27 : out_push_tail( out, pool_idx( pool, child ) );
377 27 : child = pool_ele( pool, child->sibling );
378 27 : }
379 54 : }
380 54 : return fec;
381 54 : }
382 :
383 : static fd_reasm_fec_t *
384 : publish_remove( fd_reasm_t * reasm,
385 15 : fd_hash_t const * merkle_root ) {
386 15 : fd_reasm_fec_t * fec = ancestry_ele_remove( reasm->ancestry, merkle_root, NULL, reasm->pool );
387 15 : if( FD_UNLIKELY( !fec ) ) fec = frontier_ele_remove( reasm->frontier, merkle_root, NULL, reasm->pool );
388 15 : return fec;
389 15 : }
390 :
391 : fd_reasm_fec_t *
392 3 : fd_reasm_publish( fd_reasm_t * reasm, fd_hash_t const * merkle_root ) {
393 3 : # if FD_REASM_USE_HANDHOLDING
394 3 : if( FD_UNLIKELY( !pool_ele( reasm->pool, reasm->root ) ) ) { FD_LOG_WARNING(( "missing root" )); return NULL; }
395 3 : if( FD_UNLIKELY( !fd_reasm_query( reasm, merkle_root ) ) ) { FD_LOG_WARNING(( "merkle root %s not found", FD_BASE58_ENC_32_ALLOCA( merkle_root ) )); return NULL; }
396 3 : # endif
397 :
398 3 : fd_reasm_fec_t * pool = reasm->pool;
399 3 : ulong null = pool_idx_null( pool );
400 3 : fd_reasm_fec_t * oldr = pool_ele( pool, reasm->root );
401 3 : fd_reasm_fec_t * newr = fd_reasm_query( reasm, merkle_root );
402 :
403 : /* First, remove the previous root, and push it as the first element
404 : of the BFS queue. */
405 :
406 3 : fd_reasm_fec_t * head = publish_remove( reasm, &oldr->key ); /* initialize BFS queue */
407 3 : head->next = null; /* clear map next */
408 3 : fd_reasm_fec_t * tail = head; /* tail of BFS queue */
409 :
410 : /* Second, BFS down the tree, pruning all of root's ancestors and also
411 : any descendants of those ancestors. */
412 :
413 18 : while( FD_LIKELY( head ) ) {
414 15 : fd_reasm_fec_t * child = pool_ele( pool, head->child ); /* left-child */
415 30 : while( FD_LIKELY( child ) ) { /* iterate over children */
416 15 : if( FD_LIKELY( child != newr ) ) { /* stop at new root */
417 12 : tail->next = pool_idx( pool, publish_remove( reasm, &child->key ) ); /* remove node from map to reuse `.next` */
418 12 : tail = pool_ele( pool, tail->next ); /* push onto BFS queue (so descendants can be pruned) */
419 12 : tail->next = null; /* clear map next */
420 12 : }
421 15 : child = pool_ele( pool, child->sibling ); /* right-sibling */
422 15 : }
423 15 : slot_mr_t * slot_mr = slot_mr_query( reasm->slot_mr, head->slot, NULL );
424 15 : if( FD_UNLIKELY( slot_mr ) ) slot_mr_remove( reasm->slot_mr, slot_mr ); /* only first FEC */
425 :
426 15 : fd_reasm_fec_t * next = pool_ele( pool, head->next ); /* pophead */
427 15 : pool_ele_release( pool, head ); /* release */
428 15 : head = next; /* advance */
429 15 : }
430 3 : newr->parent = null; /* unlink old root */
431 3 : reasm->root = pool_idx( pool, newr ); /* replace with new root */
432 3 : return newr;
433 3 : }
434 :
435 : #include <stdio.h>
436 :
437 : FD_FN_UNUSED static void
438 0 : print( fd_reasm_t const * reasm, fd_reasm_fec_t const * fec, int space, const char * prefix ) {
439 0 : fd_reasm_fec_t * pool = reasm->pool;
440 0 :
441 0 : if( fec == NULL ) return;
442 0 :
443 0 : if( space > 0 ) printf( "\n" );
444 0 : for( int i = 0; i < space; i++ ) printf( " " );
445 0 : printf( "%s%s", prefix, FD_BASE58_ENC_32_ALLOCA( &fec->key ) );
446 0 :
447 0 : fd_reasm_fec_t const * curr = pool_ele_const( pool, fec->child );
448 0 : char new_prefix[1024]; /* FIXME size this correctly */
449 0 : while( curr ) {
450 0 : if( pool_ele_const( pool, curr->sibling ) ) {
451 0 : sprintf( new_prefix, "├── " ); /* branch indicating more siblings follow */
452 0 : print( reasm, curr, space + 4, new_prefix );
453 0 : } else {
454 0 : sprintf( new_prefix, "└── " ); /* end branch */
455 0 : print( reasm, curr, space + 4, new_prefix );
456 0 : }
457 0 : curr = pool_ele_const( pool, curr->sibling );
458 0 : }
459 0 : }
460 :
461 : void
462 0 : fd_reasm_print( fd_reasm_t const * reasm ) {
463 0 : FD_LOG_NOTICE( ( "\n\n[Reasm]" ) );
464 0 : fd_reasm_fec_t * pool = reasm->pool;
465 :
466 0 : printf(("\n\n[Frontier]\n" ) );
467 0 : frontier_t * frontier = reasm->frontier;
468 0 : for( frontier_iter_t iter = frontier_iter_init( frontier, pool );
469 0 : !frontier_iter_done( iter, frontier, pool );
470 0 : iter = frontier_iter_next( iter, frontier, pool ) ) {
471 0 : fd_reasm_fec_t const * fec = pool_ele_const( reasm->pool, iter.ele_idx );
472 0 : printf( "(%lu, %u) %s\n", fec->slot, fec->fec_set_idx, FD_BASE58_ENC_32_ALLOCA( &fec->key ) );
473 0 : }
474 :
475 0 : printf(("\n\n[Subtrees]\n" ) );
476 0 : subtrees_t * subtrees = reasm->subtrees;
477 0 : for( subtrees_iter_t iter = subtrees_iter_init( subtrees, pool );
478 0 : !subtrees_iter_done( iter, subtrees, pool );
479 0 : iter = subtrees_iter_next( iter, subtrees, pool ) ) {
480 0 : fd_reasm_fec_t const * fec = pool_ele_const( reasm->pool, iter.ele_idx );
481 0 : printf( "(%lu, %u) %s\n", fec->slot, fec->fec_set_idx, FD_BASE58_ENC_32_ALLOCA( &fec->key ) );
482 0 : }
483 :
484 : // print( reasm, pool_ele_const( reasm->pool, reasm->root ), 0, "" );
485 : // printf( "\n\n" );
486 : // for( out_iter_t iter = out_iter_init( reasm->out ); !out_iter_done( reasm->out, iter ); iter = out_iter_next( reasm->out, iter ) ) {
487 : // ulong * idx = out_iter_ele( reasm->out, iter );
488 : // printf( "%s\n", FD_BASE58_ENC_32_ALLOCA( pool_ele_const( reasm->pool, *idx ) ) );
489 : // }
490 0 : printf( "\n\n" );
491 0 : }
|
