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