Line data Source code
1 : #include "fd_forest.h"
2 :
3 0 : static void ver_inc( ulong ** ver ) {
4 0 : fd_fseq_update( *ver, fd_fseq_query( *ver ) + 1 );
5 0 : }
6 :
7 0 : #define VER_INC ulong * ver __attribute__((cleanup(ver_inc))) = fd_forest_ver( forest ); ver_inc( &ver )
8 :
9 : void *
10 0 : fd_forest_new( void * shmem, ulong ele_max, ulong seed ) {
11 0 : FD_TEST( fd_ulong_is_pow2( ele_max ) );
12 :
13 0 : if( FD_UNLIKELY( !shmem ) ) {
14 0 : FD_LOG_WARNING(( "NULL mem" ));
15 0 : return NULL;
16 0 : }
17 :
18 0 : if( FD_UNLIKELY( !fd_ulong_is_aligned( (ulong)shmem, fd_forest_align() ) ) ) {
19 0 : FD_LOG_WARNING(( "misaligned mem" ));
20 0 : return NULL;
21 0 : }
22 :
23 0 : ulong footprint = fd_forest_footprint( ele_max );
24 0 : if( FD_UNLIKELY( !footprint ) ) {
25 0 : FD_LOG_WARNING(( "bad ele_max (%lu)", ele_max ));
26 0 : return NULL;
27 0 : }
28 :
29 0 : fd_wksp_t * wksp = fd_wksp_containing( shmem );
30 0 : if( FD_UNLIKELY( !wksp ) ) {
31 0 : FD_LOG_WARNING(( "shmem must be part of a workspace" ));
32 0 : return NULL;
33 0 : }
34 :
35 0 : fd_memset( shmem, 0, footprint );
36 0 : fd_forest_t * forest;
37 :
38 0 : FD_SCRATCH_ALLOC_INIT( l, shmem );
39 0 : forest = FD_SCRATCH_ALLOC_APPEND( l, fd_forest_align(), sizeof(fd_forest_t) );
40 0 : void * ver = FD_SCRATCH_ALLOC_APPEND( l, fd_fseq_align(), fd_fseq_footprint() );
41 0 : void * pool = FD_SCRATCH_ALLOC_APPEND( l, fd_forest_pool_align(), fd_forest_pool_footprint ( ele_max ) );
42 0 : void * ancestry = FD_SCRATCH_ALLOC_APPEND( l, fd_forest_ancestry_align(), fd_forest_ancestry_footprint( ele_max ) );
43 0 : void * frontier = FD_SCRATCH_ALLOC_APPEND( l, fd_forest_frontier_align(), fd_forest_frontier_footprint( ele_max ) );
44 0 : void * subtrees = FD_SCRATCH_ALLOC_APPEND( l, fd_forest_subtrees_align(), fd_forest_subtrees_footprint( ele_max ) );
45 0 : void * orphaned = FD_SCRATCH_ALLOC_APPEND( l, fd_forest_orphaned_align(), fd_forest_orphaned_footprint( ele_max ) );
46 0 : void * consumed = FD_SCRATCH_ALLOC_APPEND( l, fd_forest_consumed_align(), fd_forest_consumed_footprint( ele_max ) );
47 0 : void * conslist = FD_SCRATCH_ALLOC_APPEND( l, fd_forest_conslist_align(), fd_forest_conslist_footprint( ) );
48 0 : void * conspool = FD_SCRATCH_ALLOC_APPEND( l, fd_forest_conspool_align(), fd_forest_conspool_footprint( ele_max ) );
49 0 : void * deque = FD_SCRATCH_ALLOC_APPEND( l, fd_forest_deque_align(), fd_forest_deque_footprint ( ele_max ) );
50 0 : FD_TEST( FD_SCRATCH_ALLOC_FINI( l, fd_forest_align() ) == (ulong)shmem + footprint );
51 :
52 0 : forest->root = ULONG_MAX;
53 0 : forest->subtree_cnt = 0;
54 0 : forest->wksp_gaddr = fd_wksp_gaddr_fast( wksp, forest );
55 0 : forest->ver_gaddr = fd_wksp_gaddr_fast( wksp, fd_fseq_join ( fd_fseq_new ( ver, FD_FOREST_VER_UNINIT ) ) );
56 0 : forest->pool_gaddr = fd_wksp_gaddr_fast( wksp, fd_forest_pool_join ( fd_forest_pool_new ( pool, ele_max ) ) );
57 0 : forest->ancestry_gaddr = fd_wksp_gaddr_fast( wksp, fd_forest_ancestry_join( fd_forest_ancestry_new( ancestry, ele_max, seed ) ) );
58 0 : forest->frontier_gaddr = fd_wksp_gaddr_fast( wksp, fd_forest_frontier_join( fd_forest_frontier_new( frontier, ele_max, seed ) ) );
59 0 : forest->subtrees_gaddr = fd_wksp_gaddr_fast( wksp, fd_forest_subtrees_join( fd_forest_subtrees_new( subtrees, ele_max, seed ) ) );
60 0 : forest->orphaned_gaddr = fd_wksp_gaddr_fast( wksp, fd_forest_orphaned_join( fd_forest_orphaned_new( orphaned, ele_max, seed ) ) );
61 0 : forest->consumed_gaddr = fd_wksp_gaddr_fast( wksp, fd_forest_consumed_join( fd_forest_consumed_new( consumed, ele_max, seed ) ) );
62 0 : forest->conslist_gaddr = fd_wksp_gaddr_fast( wksp, fd_forest_conslist_join( fd_forest_conslist_new( conslist ) ) );
63 0 : forest->conspool_gaddr = fd_wksp_gaddr_fast( wksp, fd_forest_conspool_join( fd_forest_conspool_new( conspool, ele_max ) ) );
64 0 : forest->deque_gaddr = fd_wksp_gaddr_fast( wksp, fd_forest_deque_join ( fd_forest_deque_new ( deque, ele_max ) ) );
65 :
66 0 : FD_COMPILER_MFENCE();
67 0 : FD_VOLATILE( forest->magic ) = FD_FOREST_MAGIC;
68 0 : FD_COMPILER_MFENCE();
69 :
70 0 : return shmem;
71 0 : }
72 :
73 : fd_forest_t *
74 0 : fd_forest_join( void * shforest ) {
75 0 : fd_forest_t * forest = (fd_forest_t *)shforest;
76 :
77 0 : if( FD_UNLIKELY( !forest ) ) {
78 0 : FD_LOG_WARNING(( "NULL forest" ));
79 0 : return NULL;
80 0 : }
81 :
82 0 : if( FD_UNLIKELY( !fd_ulong_is_aligned((ulong)forest, fd_forest_align() ) ) ) {
83 0 : FD_LOG_WARNING(( "misaligned forest" ));
84 0 : return NULL;
85 0 : }
86 :
87 0 : fd_wksp_t * wksp = fd_wksp_containing( forest );
88 0 : if( FD_UNLIKELY( !wksp ) ) {
89 0 : FD_LOG_WARNING(( "forest must be part of a workspace" ));
90 0 : return NULL;
91 0 : }
92 :
93 0 : return forest;
94 0 : }
95 :
96 : void *
97 0 : fd_forest_leave( fd_forest_t const * forest ) {
98 :
99 0 : if( FD_UNLIKELY( !forest ) ) {
100 0 : FD_LOG_WARNING(( "NULL forest" ));
101 0 : return NULL;
102 0 : }
103 :
104 0 : return (void *)forest;
105 0 : }
106 :
107 : void *
108 0 : fd_forest_delete( void * forest ) {
109 :
110 0 : if( FD_UNLIKELY( !forest ) ) {
111 0 : FD_LOG_WARNING(( "NULL forest" ));
112 0 : return NULL;
113 0 : }
114 :
115 0 : if( FD_UNLIKELY( !fd_ulong_is_aligned((ulong)forest, fd_forest_align() ) ) ) {
116 0 : FD_LOG_WARNING(( "misaligned forest" ));
117 0 : return NULL;
118 0 : }
119 :
120 : // TODO: zero out mem?
121 :
122 0 : return forest;
123 0 : }
124 :
125 :
126 : static void
127 0 : consumed_insert( fd_forest_t * forest, ulong slot, ulong pool_idx ) {
128 0 : fd_forest_consumed_t * consumed = fd_forest_consumed( forest );
129 0 : fd_forest_cns_t * pool = fd_forest_conspool( forest );
130 0 : fd_forest_cns_t * ele = fd_forest_conspool_ele_acquire( pool );
131 0 : ele->slot = slot;
132 0 : ele->forest_pool_idx = pool_idx;
133 0 : fd_forest_consumed_ele_insert( consumed, ele, pool );
134 0 : fd_forest_conslist_ele_push_tail( fd_forest_conslist( forest ), ele, pool );
135 0 : }
136 :
137 : static void
138 0 : consumed_remove( fd_forest_t * forest, ulong slot ) {
139 0 : fd_forest_consumed_t * consumed = fd_forest_consumed( forest );
140 0 : fd_forest_cns_t * pool = fd_forest_conspool( forest );
141 0 : fd_forest_cns_t * ele;
142 0 : if( ( ele = fd_forest_consumed_ele_remove( consumed, &slot, NULL, pool ) ) ) {
143 0 : fd_forest_conslist_ele_remove( fd_forest_conslist( forest ), ele, pool );
144 0 : fd_forest_conspool_ele_release( pool, ele );
145 0 : }
146 0 : }
147 :
148 : fd_forest_t *
149 0 : fd_forest_init( fd_forest_t * forest, ulong root_slot ) {
150 0 : FD_TEST( forest );
151 0 : FD_TEST( fd_fseq_query( fd_forest_ver( forest ) ) == FD_FOREST_VER_UNINIT );
152 :
153 0 : VER_INC;
154 :
155 0 : fd_forest_blk_t * pool = fd_forest_pool( forest );
156 0 : ulong null = fd_forest_pool_idx_null( pool );
157 0 : fd_forest_frontier_t * frontier = fd_forest_frontier( forest );
158 :
159 : /* Initialize the root node from a pool element. */
160 :
161 0 : fd_forest_blk_t * root_ele = fd_forest_pool_ele_acquire( pool );
162 0 : root_ele->slot = root_slot;
163 0 : root_ele->parent = null;
164 0 : root_ele->child = null;
165 0 : root_ele->sibling = null;
166 0 : root_ele->buffered_idx = 0;
167 0 : root_ele->complete_idx = 0;
168 :
169 0 : fd_forest_blk_idxs_full( root_ele->fecs );
170 0 : fd_forest_blk_idxs_full( root_ele->cmpl );
171 :
172 0 : forest->root = fd_forest_pool_idx( pool, root_ele );
173 0 : fd_forest_frontier_ele_insert( frontier, root_ele, pool ); /* cannot fail */
174 0 : consumed_insert( forest, root_ele->slot, fd_forest_pool_idx( pool, root_ele ) );
175 :
176 : /* Sanity checks. */
177 :
178 0 : FD_TEST( root_ele );
179 0 : FD_TEST( root_ele == fd_forest_frontier_ele_query( frontier, &root_slot, NULL, pool ));
180 0 : FD_TEST( root_ele->slot == root_slot );
181 :
182 0 : return forest;
183 0 : }
184 :
185 : static ulong *
186 0 : fd_forest_deque( fd_forest_t * forest ) {
187 0 : return fd_wksp_laddr_fast( fd_forest_wksp( forest ), forest->deque_gaddr );
188 0 : }
189 :
190 : fd_forest_t *
191 0 : fd_forest_fini( fd_forest_t * forest ) {
192 0 : fd_fseq_update( fd_forest_ver( forest ), FD_FOREST_VER_INVAL );
193 :
194 0 : fd_forest_blk_t * pool = fd_forest_pool( forest );
195 0 : ulong null = fd_forest_pool_idx_null( pool );
196 0 : fd_forest_ancestry_t * ancestry = fd_forest_ancestry( forest );
197 0 : fd_forest_frontier_t * frontier = fd_forest_frontier( forest );
198 0 : fd_forest_subtrees_t * subtrees = fd_forest_subtrees( forest );
199 0 : fd_forest_orphaned_t * orphaned = fd_forest_orphaned( forest );
200 0 : if( FD_UNLIKELY( !fd_forest_pool_used( pool ) ) ) return forest;
201 :
202 0 : ulong * q = fd_forest_deque( forest );
203 0 : fd_forest_deque_remove_all( q );
204 0 : for( fd_forest_ancestry_iter_t iter = fd_forest_ancestry_iter_init( ancestry, pool );
205 0 : !fd_forest_ancestry_iter_done( iter, ancestry, pool );
206 0 : iter = fd_forest_ancestry_iter_next( iter, ancestry, pool ) ) {
207 0 : fd_forest_deque_push_tail( q, fd_forest_ancestry_iter_idx( iter, ancestry, pool ) );
208 0 : }
209 0 : while( !fd_forest_deque_empty( q ) ) {
210 0 : ulong idx = fd_forest_deque_pop_head( q );
211 0 : FD_TEST( fd_forest_ancestry_ele_remove( ancestry, &fd_forest_pool_ele( pool, idx )->slot, NULL, pool ) );
212 0 : fd_forest_pool_idx_release( pool, idx );
213 0 : }
214 0 : for( fd_forest_frontier_iter_t iter = fd_forest_frontier_iter_init( frontier, pool );
215 0 : !fd_forest_frontier_iter_done( iter, frontier, pool );
216 0 : iter = fd_forest_frontier_iter_next( iter, frontier, pool ) ) {
217 0 : fd_forest_deque_push_tail( q, fd_forest_frontier_iter_idx( iter, frontier, pool ) );
218 0 : }
219 0 : while( !fd_forest_deque_empty( q ) ) {
220 0 : ulong idx = fd_forest_deque_pop_head( q );
221 0 : FD_TEST( fd_forest_frontier_ele_remove( frontier, &fd_forest_pool_ele( pool, idx )->slot, NULL, pool ) );
222 0 : fd_forest_pool_idx_release( pool, idx );
223 0 : }
224 0 : for( fd_forest_subtrees_iter_t iter = fd_forest_subtrees_iter_init( subtrees, pool );
225 0 : !fd_forest_subtrees_iter_done( iter, subtrees, pool );
226 0 : iter = fd_forest_subtrees_iter_next( iter, subtrees, pool ) ) {
227 0 : fd_forest_deque_push_tail( q, fd_forest_subtrees_iter_idx( iter, subtrees, pool ) );
228 0 : }
229 0 : while( !fd_forest_deque_empty( q ) ) {
230 0 : ulong idx = fd_forest_deque_pop_head( q );
231 0 : FD_TEST( fd_forest_subtrees_ele_remove( subtrees, &fd_forest_pool_ele( pool, idx )->slot, NULL, pool ) );
232 0 : fd_forest_pool_idx_release( pool, idx );
233 0 : }
234 0 : for( fd_forest_orphaned_iter_t iter = fd_forest_orphaned_iter_init( orphaned, pool );
235 0 : !fd_forest_orphaned_iter_done( iter, orphaned, pool );
236 0 : iter = fd_forest_orphaned_iter_next( iter, orphaned, pool ) ) {
237 0 : fd_forest_deque_push_tail( q, fd_forest_orphaned_iter_idx( iter, orphaned, pool ) );
238 0 : }
239 0 : while( !fd_forest_deque_empty( q ) ) {
240 0 : ulong idx = fd_forest_deque_pop_head( q );
241 0 : FD_TEST( fd_forest_orphaned_ele_remove( orphaned, &fd_forest_pool_ele( pool, idx )->slot, NULL, pool ) );
242 0 : fd_forest_pool_idx_release( pool, idx );
243 0 : }
244 0 : forest->root = null;
245 0 : # if FD_FOREST_USE_HANDHOLDING
246 0 : FD_TEST( !fd_forest_pool_used( pool ) );
247 0 : # endif
248 :
249 0 : fd_fseq_update( fd_forest_ver( forest ), FD_FOREST_VER_UNINIT );
250 0 : return forest;
251 0 : }
252 :
253 : int
254 0 : fd_forest_verify( fd_forest_t const * forest ) {
255 0 : if( FD_UNLIKELY( !forest ) ) {
256 0 : FD_LOG_WARNING(( "NULL forest" ));
257 0 : return -1;
258 0 : }
259 :
260 0 : if( FD_UNLIKELY( !fd_ulong_is_aligned( (ulong)forest, fd_forest_align() ) ) ) {
261 0 : FD_LOG_WARNING(( "misaligned forest" ));
262 0 : return -1;
263 0 : }
264 :
265 0 : fd_wksp_t * wksp = fd_wksp_containing( forest );
266 0 : if( FD_UNLIKELY( !wksp ) ) {
267 0 : FD_LOG_WARNING(( "forest must be part of a workspace" ));
268 0 : return -1;
269 0 : }
270 :
271 0 : if( FD_UNLIKELY( forest->magic!=FD_FOREST_MAGIC ) ) {
272 0 : FD_LOG_WARNING(( "bad magic" ));
273 0 : return -1;
274 0 : }
275 :
276 0 : if( FD_UNLIKELY( fd_fseq_query( fd_forest_ver_const( forest ) ) == ULONG_MAX ) ) {
277 0 : FD_LOG_WARNING(( "forest uninitialized or invalid" ));
278 0 : return -1;
279 0 : }
280 :
281 0 : fd_forest_blk_t const * pool = fd_forest_pool_const( forest );
282 :
283 0 : fd_forest_frontier_t const * frontier = fd_forest_frontier_const( forest );
284 0 : fd_forest_orphaned_t const * orphaned = fd_forest_orphaned_const( forest );
285 0 : fd_forest_ancestry_t const * ancestry = fd_forest_ancestry_const( forest );
286 0 : fd_forest_subtrees_t const * subtrees = fd_forest_subtrees_const( forest );
287 :
288 0 : if( fd_forest_ancestry_verify( ancestry, fd_forest_pool_max( pool ), pool ) == -1 ) return -1;
289 0 : if( fd_forest_frontier_verify( frontier, fd_forest_pool_max( pool ), pool ) == -1 ) return -1;
290 0 : if( fd_forest_subtrees_verify( subtrees, fd_forest_pool_max( pool ), pool ) == -1 ) return -1;
291 0 : if( fd_forest_orphaned_verify( orphaned, fd_forest_pool_max( pool ), pool ) == -1 ) return -1;
292 :
293 : /* Invariant: elements can only appear in one of the four maps. */
294 0 : for( fd_forest_frontier_iter_t iter = fd_forest_frontier_iter_init( frontier, pool ); !fd_forest_frontier_iter_done( iter, frontier, pool ); iter = fd_forest_frontier_iter_next( iter, frontier, pool ) ) {
295 0 : fd_forest_blk_t const * ele = fd_forest_frontier_iter_ele_const( iter, frontier, pool );
296 0 : if( fd_forest_ancestry_ele_query_const( ancestry, &ele->slot, NULL, pool ) ) return -1;
297 0 : if( fd_forest_orphaned_ele_query_const( orphaned, &ele->slot, NULL, pool ) ) return -1;
298 0 : if( fd_forest_subtrees_ele_query_const( subtrees, &ele->slot, NULL, pool ) ) return -1;
299 0 : }
300 :
301 0 : for( fd_forest_orphaned_iter_t iter = fd_forest_orphaned_iter_init( orphaned, pool ); !fd_forest_orphaned_iter_done( iter, orphaned, pool ); iter = fd_forest_orphaned_iter_next( iter, orphaned, pool ) ) {
302 0 : fd_forest_blk_t const * ele = fd_forest_orphaned_iter_ele_const( iter, orphaned, pool );
303 0 : if( fd_forest_ancestry_ele_query_const( ancestry, &ele->slot, NULL, pool ) ) return -1;
304 0 : if( fd_forest_frontier_ele_query_const( frontier, &ele->slot, NULL, pool ) ) return -1;
305 0 : if( fd_forest_subtrees_ele_query_const( subtrees, &ele->slot, NULL, pool ) ) return -1;
306 0 : }
307 :
308 0 : for( fd_forest_subtrees_iter_t iter = fd_forest_subtrees_iter_init( subtrees, pool ); !fd_forest_subtrees_iter_done( iter, subtrees, pool ); iter = fd_forest_subtrees_iter_next( iter, subtrees, pool ) ) {
309 0 : fd_forest_blk_t const * ele = fd_forest_subtrees_iter_ele_const( iter, subtrees, pool );
310 0 : if( fd_forest_ancestry_ele_query_const( ancestry, &ele->slot, NULL, pool ) ) return -1;
311 0 : if( fd_forest_frontier_ele_query_const( frontier, &ele->slot, NULL, pool ) ) return -1;
312 0 : if( fd_forest_orphaned_ele_query_const( orphaned, &ele->slot, NULL, pool ) ) return -1;
313 0 : }
314 :
315 0 : fd_forest_consumed_t const * consumed = fd_forest_consumed_const( forest );
316 0 : fd_forest_cns_t const * conspool = fd_forest_conspool_const( forest );
317 :
318 : /* from every frontier walk back and verify that there is an ancestor in the consumed map */
319 0 : for( fd_forest_frontier_iter_t iter = fd_forest_frontier_iter_init( frontier, pool ); !fd_forest_frontier_iter_done( iter, frontier, pool ); iter = fd_forest_frontier_iter_next( iter, frontier, pool ) ) {
320 0 : fd_forest_blk_t const * ele = fd_forest_frontier_iter_ele_const( iter, frontier, pool );
321 0 : int found = 0;
322 0 : while( FD_LIKELY( ele ) ) {
323 0 : if( fd_forest_consumed_ele_query_const( consumed, &ele->slot, NULL, conspool ) ) {
324 0 : found = 1;
325 0 : break;
326 0 : }
327 0 : ele = fd_forest_pool_ele_const( pool, ele->parent );
328 0 : }
329 0 : if( FD_UNLIKELY( !found ) ) return -1;
330 0 : }
331 :
332 : /* Consumed map elements must be in the frontier or ancestry map. */
333 :
334 0 : for( fd_forest_consumed_iter_t iter = fd_forest_consumed_iter_init( consumed, conspool ); !fd_forest_consumed_iter_done( iter, consumed, conspool ); iter = fd_forest_consumed_iter_next( iter, consumed, conspool ) ) {
335 0 : fd_forest_cns_t const * ele = fd_forest_consumed_iter_ele_const( iter, consumed, conspool );
336 0 : if( !fd_forest_ancestry_ele_query_const( ancestry, &ele->slot, NULL, pool ) && !fd_forest_frontier_ele_query_const( frontier, &ele->slot, NULL, pool ) ) {
337 0 : return -1;
338 0 : }
339 0 : }
340 :
341 0 : return 0;
342 0 : }
343 :
344 : /* remove removes and returns a connected ele from ancestry or frontier
345 : maps. does not remove orphaned ele. does not unlink ele. */
346 :
347 : static fd_forest_blk_t *
348 0 : ancestry_frontier_remove( fd_forest_t * forest, ulong slot ) {
349 0 : fd_forest_blk_t * pool = fd_forest_pool( forest );
350 0 : fd_forest_blk_t * ele = NULL;
351 0 : ele = fd_forest_ancestry_ele_remove( fd_forest_ancestry( forest ), &slot, NULL, pool );
352 0 : ele = fd_ptr_if( !ele, fd_forest_frontier_ele_remove( fd_forest_frontier( forest ), &slot, NULL, pool ), ele );
353 0 : return ele;
354 0 : }
355 :
356 : static fd_forest_blk_t *
357 0 : subtrees_orphaned_remove( fd_forest_t * forest, ulong slot ) {
358 0 : fd_forest_blk_t * pool = fd_forest_pool( forest );
359 0 : fd_forest_blk_t * ele = NULL;
360 0 : ele = fd_forest_orphaned_ele_remove( fd_forest_orphaned( forest ), &slot, NULL, pool );
361 0 : if( ele ) return ele;
362 0 : ele = fd_forest_subtrees_ele_remove( fd_forest_subtrees( forest ), &slot, NULL, pool );
363 0 : if( ele ) forest->subtree_cnt--;
364 0 : return ele;
365 0 : }
366 :
367 : /* link ele to the tree via its sibling. */
368 :
369 : static void
370 0 : link_sibling( fd_forest_t * forest, fd_forest_blk_t * sibling, fd_forest_blk_t * ele ) {
371 0 : fd_forest_blk_t * pool = fd_forest_pool( forest );
372 0 : ulong null = fd_forest_pool_idx_null( pool );
373 0 : while( FD_UNLIKELY( sibling->sibling != null )) sibling = fd_forest_pool_ele( pool, sibling->sibling );
374 0 : sibling->sibling = fd_forest_pool_idx( pool, ele );
375 0 : }
376 :
377 : /* link child to the tree via its parent. */
378 :
379 : static void
380 0 : link( fd_forest_t * forest, fd_forest_blk_t * parent, fd_forest_blk_t * child ) {
381 0 : fd_forest_blk_t * pool = fd_forest_pool( forest );
382 0 : ulong null = fd_forest_pool_idx_null( pool );
383 0 : if( FD_LIKELY( parent->child == null ) ) parent->child = fd_forest_pool_idx( pool, child ); /* left-child */
384 0 : else link_sibling( forest, fd_forest_pool_ele( pool, parent->child ), child ); /* right-sibling */
385 0 : child->parent = fd_forest_pool_idx( pool, parent );
386 0 : }
387 :
388 : /* advance_consumed_frontier attempts to advance the consumed frontier beginning from slot
389 : using BFS. head is the first element of a linked list representing
390 : the BFS queue. A slot can be advanced if all shreds for the block
391 : are received ie. consumed_idx = complete_idx. */
392 :
393 : static void
394 0 : advance_consumed_frontier( fd_forest_t * forest, ulong slot, ulong parent_slot ) {
395 0 : fd_forest_blk_t * pool = fd_forest_pool( forest );
396 0 : fd_forest_cns_t * conspool = fd_forest_conspool( forest );
397 0 : fd_forest_consumed_t * consumed = fd_forest_consumed( forest );
398 0 : ulong * queue = fd_forest_deque( forest );
399 :
400 0 : fd_forest_cns_t * ele;
401 0 : ele = fd_forest_consumed_ele_query( consumed, &slot, NULL, conspool );
402 0 : ele = fd_ptr_if( !ele, fd_forest_consumed_ele_query( consumed, &parent_slot, NULL, conspool ), ele );
403 0 : if( FD_UNLIKELY( !ele ) ) return;
404 :
405 0 : # if FD_FOREST_USE_HANDHOLDING
406 0 : FD_TEST( fd_forest_deque_cnt( queue ) == 0 );
407 0 : # endif
408 :
409 : /* BFS elements as pool idxs.
410 : Invariant: whatever is in the queue, must be in the consumed map. */
411 0 : fd_forest_deque_push_tail( queue, ele->forest_pool_idx );
412 0 : while( FD_LIKELY( fd_forest_deque_cnt( queue ) ) ) {
413 0 : fd_forest_blk_t * head = fd_forest_pool_ele( pool, fd_forest_deque_pop_head( queue ) );
414 0 : fd_forest_blk_t * child = fd_forest_pool_ele( pool, head->child );
415 0 : if( FD_LIKELY( child &&
416 0 : head->complete_idx != UINT_MAX &&
417 0 : head->complete_idx == head->buffered_idx && /* we've received all the shreds for the slot */
418 0 : 0==memcmp( head->cmpl, head->fecs, sizeof(fd_forest_blk_idxs_t) * fd_forest_blk_idxs_word_cnt ) /* AND all the FECs for the slot have been completed */) ) {
419 0 : consumed_remove( forest, head->slot );
420 0 : while( FD_LIKELY( child ) ) { /* add children to consumed frontier */
421 0 : consumed_insert( forest, child->slot, fd_forest_pool_idx( pool, child ) );
422 :
423 0 : fd_forest_deque_push_tail( queue, fd_forest_pool_idx( pool, child ) );
424 0 : child = fd_forest_pool_ele( pool, child->sibling );
425 0 : }
426 0 : }
427 0 : }
428 0 : }
429 :
430 : static fd_forest_blk_t *
431 0 : query( fd_forest_t * forest, ulong slot ) {
432 0 : fd_forest_blk_t * pool = fd_forest_pool( forest );
433 0 : fd_forest_ancestry_t * ancestry = fd_forest_ancestry( forest );
434 0 : fd_forest_frontier_t * frontier = fd_forest_frontier( forest );
435 0 : fd_forest_subtrees_t * subtrees = fd_forest_subtrees( forest );
436 0 : fd_forest_orphaned_t * orphaned = fd_forest_orphaned( forest );
437 :
438 0 : fd_forest_blk_t * ele = NULL;
439 0 : ele = fd_forest_ancestry_ele_query( ancestry, &slot, NULL, pool );
440 0 : ele = fd_ptr_if( !ele, fd_forest_frontier_ele_query( frontier, &slot, NULL, pool ), ele );
441 0 : ele = fd_ptr_if( !ele, fd_forest_subtrees_ele_query( subtrees, &slot, NULL, pool ), ele );
442 0 : ele = fd_ptr_if( !ele, fd_forest_orphaned_ele_query( orphaned, &slot, NULL, pool ), ele );
443 0 : return ele;
444 0 : }
445 :
446 : static fd_forest_blk_t *
447 0 : acquire( fd_forest_t * forest, ulong slot, ulong parent_slot ) {
448 0 : fd_forest_blk_t * pool = fd_forest_pool( forest );
449 0 : if( FD_UNLIKELY( !fd_forest_pool_free( pool ) ) ) {
450 0 : FD_LOG_ERR(( "Firedancer ran out of memory when repairing new blocks. If this happened during catchup, your "
451 0 : "snapshot is likely too old and there are too many blocks to repair. You can fix this by using a more "
452 0 : "recent snapshot (if loading a pre-downloaded snapshot) or rebooting (if downloading the snapshot "
453 0 : "live). If this happened while running live (after catchup), Firedancer got disconnected from the "
454 0 : "cluster and stopped being able to receive shreds. Try rebooting." ));
455 0 : }
456 0 : fd_forest_blk_t * blk = fd_forest_pool_ele_acquire( pool );
457 0 : ulong null = fd_forest_pool_idx_null( pool );
458 :
459 0 : blk->slot = slot;
460 0 : blk->parent_slot = parent_slot;
461 0 : blk->next = null;
462 0 : blk->parent = null;
463 0 : blk->child = null;
464 0 : blk->sibling = null;
465 :
466 0 : blk->consumed_idx = UINT_MAX;
467 0 : blk->buffered_idx = UINT_MAX;
468 0 : blk->complete_idx = UINT_MAX;
469 :
470 0 : fd_forest_blk_idxs_null( blk->fecs ); /* expensive */
471 0 : fd_forest_blk_idxs_null( blk->idxs ); /* expensive */
472 0 : fd_forest_blk_idxs_null( blk->cmpl ); /* expensive */
473 :
474 0 : blk->est_buffered_tick_recv = 0;
475 :
476 : /* Metrics tracking */
477 :
478 0 : fd_forest_blk_idxs_null( blk->code ); /* expensive */
479 0 : blk->first_shred_ts = 0;
480 0 : blk->first_req_ts = 0;
481 0 : blk->turbine_cnt = 0;
482 0 : blk->repair_cnt = 0;
483 0 : blk->recovered_cnt = 0;
484 :
485 0 : return blk;
486 0 : }
487 :
488 : fd_forest_blk_t *
489 0 : fd_forest_query( fd_forest_t * forest, ulong slot ) {
490 0 : return query( forest, slot );
491 0 : }
492 :
493 : fd_forest_blk_t *
494 0 : fd_forest_blk_insert( fd_forest_t * forest, ulong slot, ulong parent_slot ) {
495 0 : # if FD_FOREST_USE_HANDHOLDING
496 0 : FD_TEST( slot > fd_forest_root_slot( forest ) ); /* caller error - inval */
497 0 : # endif
498 0 : fd_forest_blk_t * ele = query( forest, slot );
499 0 : if( FD_LIKELY( ele ) ) { return ele; }
500 :
501 0 : fd_forest_ancestry_t * ancestry = fd_forest_ancestry( forest );
502 0 : fd_forest_frontier_t * frontier = fd_forest_frontier( forest );
503 0 : fd_forest_subtrees_t * subtrees = fd_forest_subtrees( forest );
504 0 : fd_forest_orphaned_t * orphaned = fd_forest_orphaned( forest );
505 0 : fd_forest_consumed_t * consumed = fd_forest_consumed( forest );
506 0 : fd_forest_cns_t * conspool = fd_forest_conspool( forest );
507 0 : fd_forest_blk_t * pool = fd_forest_pool ( forest );
508 0 : ulong * bfs = fd_forest_deque( forest );
509 :
510 0 : fd_forest_blk_t * parent = NULL;
511 :
512 0 : ele = acquire( forest, slot, parent_slot );
513 :
514 0 : if( FD_LIKELY ( parent = fd_forest_ancestry_ele_query ( ancestry, &parent_slot, NULL, pool ) ) ) { /* parent is in ancestry, ele makes new frontier */
515 0 : fd_forest_frontier_ele_insert( frontier, ele, pool );
516 0 : } else if( FD_UNLIKELY( parent = fd_forest_frontier_ele_remove( frontier, &parent_slot, NULL, pool ) ) ) { /* parent is in frontier, ele makes new frontier */
517 0 : fd_forest_ancestry_ele_insert( ancestry, parent, pool );
518 0 : fd_forest_frontier_ele_insert( frontier, ele, pool );
519 0 : } else if( FD_UNLIKELY( parent = fd_forest_orphaned_ele_query ( orphaned, &parent_slot, NULL, pool ) ) ) { /* parent is in orphaned, ele makes new orphaned */
520 0 : fd_forest_orphaned_ele_insert( orphaned, ele, pool );
521 0 : } else if( FD_UNLIKELY( parent = fd_forest_subtrees_ele_query ( subtrees, &parent_slot, NULL, pool ) ) ) { /* parent is in subtrees, ele makes new orphaned */
522 0 : fd_forest_orphaned_ele_insert( orphaned, ele, pool );
523 0 : } else { /* parent is not in any map, ele makes new subtree */
524 0 : fd_forest_subtrees_ele_insert( subtrees, ele, pool );
525 0 : forest->subtree_cnt++;
526 0 : }
527 :
528 0 : if( FD_LIKELY( parent ) ) link( forest, parent, ele );
529 :
530 : /* Iterate subtrees and connect ones where the parent slot matches up
531 : to the new ele.*/
532 :
533 0 : for( fd_forest_subtrees_iter_t iter = fd_forest_subtrees_iter_init( subtrees, pool );
534 0 : !fd_forest_subtrees_iter_done( iter, subtrees, pool );
535 0 : iter = fd_forest_subtrees_iter_next( iter, subtrees, pool ) ) {
536 0 : fd_forest_blk_t * orphan = fd_forest_subtrees_iter_ele( iter, subtrees, pool );
537 0 : fd_forest_deque_push_tail( bfs, fd_forest_pool_idx( pool, orphan ) );
538 0 : }
539 0 : while( FD_LIKELY( fd_forest_deque_cnt( bfs ) ) ) {
540 0 : fd_forest_blk_t * orphan = fd_forest_pool_ele( pool, fd_forest_deque_pop_head( bfs ) );
541 0 : if( FD_UNLIKELY( orphan->parent_slot == ele->slot ) ) {
542 0 : link( forest, ele, orphan );
543 0 : fd_forest_subtrees_ele_remove( subtrees, &orphan->slot, NULL, pool );
544 0 : fd_forest_orphaned_ele_insert( orphaned, orphan, pool );
545 0 : forest->subtree_cnt--;
546 0 : }
547 0 : }
548 :
549 : /* At this point we are in the state where:
550 :
551 : ele < in frontier/subtrees/orphaned >
552 : |
553 : children < all in orphaned >
554 :
555 : if ele is in frontier, we need to extend the frontier from this child.
556 : if ele is in orphaned/subtrees, we are done. don't do anything, */
557 :
558 0 : if( FD_LIKELY( fd_forest_frontier_ele_query( frontier, &ele->slot, NULL, pool ) ) ) fd_forest_deque_push_tail( bfs, fd_forest_pool_idx( pool, ele ) );
559 0 : while( FD_LIKELY( !fd_forest_deque_empty( bfs ) ) ) {
560 0 : fd_forest_blk_t * parent = fd_forest_pool_ele( pool, fd_forest_deque_pop_head( bfs ) );
561 0 : fd_forest_blk_t * child = fd_forest_pool_ele( pool, parent->child );
562 0 : if( FD_LIKELY( child ) ) {
563 0 : fd_forest_frontier_ele_remove( frontier, &parent->slot, NULL, pool );
564 0 : fd_forest_ancestry_ele_insert( ancestry, parent, pool );
565 0 : }
566 0 : while( FD_LIKELY( child ) ) {
567 0 : fd_forest_orphaned_ele_remove( orphaned, &child->slot, NULL, pool );
568 0 : fd_forest_frontier_ele_insert( frontier, child, pool );
569 0 : fd_forest_deque_push_tail( bfs, fd_forest_pool_idx( pool, child ) );
570 0 : child = fd_forest_pool_ele( pool, child->sibling );
571 0 : }
572 0 : }
573 :
574 0 : FD_TEST( fd_forest_deque_empty( bfs ) );
575 0 : if( FD_LIKELY( fd_forest_ancestry_ele_query( ancestry, &ele->slot, NULL, pool ) ||
576 0 : fd_forest_frontier_ele_query( frontier, &ele->slot, NULL, pool ) ) ) {
577 : /* There is a chance that we connected this ele to the main tree.
578 : If this ele doesn't have a parent in the consumed map, add it
579 : to the consumed map. */
580 0 : fd_forest_blk_t * ancestor = ele;
581 0 : while( FD_UNLIKELY( ancestor && !fd_forest_consumed_ele_query( consumed, &ancestor->slot, NULL, conspool ) ) ) {
582 0 : ancestor = fd_forest_pool_ele( pool, ancestor->parent );
583 0 : }
584 0 : if( FD_UNLIKELY( !ancestor ) ) {
585 0 : FD_LOG_NOTICE(( "fd_forest: ensure_consumed_reachable: ele %lu is not reachable from consumed frontier, adding myself", ele->slot ));
586 0 : consumed_insert( forest, ele->slot, fd_forest_pool_idx( pool, ele ) );
587 0 : }
588 0 : }
589 0 : return ele;
590 0 : }
591 :
592 : fd_forest_blk_t *
593 0 : fd_forest_data_shred_insert( fd_forest_t * forest, ulong slot, ulong parent_slot, uint shred_idx, uint fec_set_idx, int slot_complete, int ref_tick, int src ) {
594 0 : VER_INC;
595 0 : fd_forest_blk_t * ele = query( forest, slot );
596 0 : # if FD_FOREST_USE_HANDHOLDING
597 0 : if( FD_UNLIKELY( !ele ) ) FD_LOG_ERR(( "fd_forest: fd_forest_data_shred_insert: ele %lu is not in the forest. data_shred_insert should be preceded by blk_insert", slot ));
598 0 : # endif
599 0 : fd_forest_blk_idxs_insert_if( ele->fecs, fec_set_idx > 0, fec_set_idx - 1 );
600 0 : fd_forest_blk_idxs_insert_if( ele->fecs, slot_complete, shred_idx );
601 0 : ele->complete_idx = fd_uint_if( slot_complete, shred_idx, ele->complete_idx );
602 :
603 0 : if( !fd_forest_blk_idxs_test( ele->idxs, shred_idx ) ) { /* newly seen shred */
604 0 : ele->turbine_cnt += (src==SHRED_SRC_TURBINE);
605 0 : ele->repair_cnt += (src==SHRED_SRC_REPAIR);
606 0 : ele->recovered_cnt += (src==SHRED_SRC_RECOVERED);
607 0 : }
608 0 : if( FD_UNLIKELY( ele->first_shred_ts == 0 ) ) ele->first_shred_ts = fd_tickcount();
609 :
610 0 : fd_forest_blk_idxs_insert( ele->idxs, shred_idx );
611 0 : while( fd_forest_blk_idxs_test( ele->idxs, ele->buffered_idx + 1U ) ) {
612 0 : ele->buffered_idx++;
613 0 : ele->est_buffered_tick_recv = ref_tick;
614 : /* If the buffered_idx increases, this means the
615 : est_buffered_tick_recv is at least ref_tick */
616 0 : }
617 0 : advance_consumed_frontier( forest, slot, parent_slot );
618 0 : return ele;
619 0 : }
620 :
621 : fd_forest_blk_t *
622 0 : fd_forest_fec_insert( fd_forest_t * forest, ulong slot, ulong parent_slot, uint last_shred_idx, uint fec_set_idx, int slot_complete, int ref_tick ) {
623 0 : VER_INC;
624 :
625 0 : fd_forest_blk_t * ele = query( forest, slot );
626 0 : # if FD_FOREST_USE_HANDHOLDING
627 0 : if( FD_UNLIKELY( !ele ) ) FD_LOG_ERR(( "fd_forest_fec_insert: ele %lu is not in the forest. fec_insert should be preceded by blk_insert", slot ));
628 0 : # endif
629 : /* It's important that we set the cmpl idx here. If this happens to be
630 : the last fec_complete we needed to finish the slot, then we rely on
631 : the advance_consumed_frontier call in the below data_shred_insert
632 : to move forward the consumed frontier. */
633 0 : fd_forest_blk_idxs_insert( ele->cmpl, last_shred_idx );
634 0 : for( uint idx = fec_set_idx; idx <= last_shred_idx; idx++ ) {
635 0 : ele = fd_forest_data_shred_insert( forest, slot, parent_slot, idx, fec_set_idx, slot_complete & (idx == last_shred_idx), ref_tick, SHRED_SRC_RECOVERED );
636 0 : }
637 0 : return ele;
638 0 : }
639 :
640 : fd_forest_blk_t *
641 0 : fd_forest_code_shred_insert( fd_forest_t * forest, ulong slot, uint shred_idx ) {
642 0 : fd_forest_blk_t * ele = query( forest, slot );
643 0 : if( FD_UNLIKELY( !ele ) ) {
644 0 : return NULL;
645 0 : }
646 0 : if( FD_UNLIKELY( ele->first_shred_ts == 0 ) ) ele->first_shred_ts = fd_tickcount();
647 :
648 0 : if( FD_UNLIKELY( shred_idx >= fd_forest_blk_idxs_max( ele->code ) ) ) {
649 0 : FD_LOG_INFO(( "fd_forest: fd_forest_code_shred_insert: shred_idx %u is greater than max, not tracking.", shred_idx ));
650 0 : ele->turbine_cnt += 1;
651 0 : return ele;
652 0 : }
653 :
654 0 : if( FD_LIKELY( !fd_forest_blk_idxs_test( ele->code, shred_idx ) ) ) { /* newly seen shred */
655 0 : ele->turbine_cnt += 1;
656 0 : fd_forest_blk_idxs_insert( ele->code, shred_idx );
657 0 : }
658 0 : return ele;
659 0 : }
660 :
661 : void
662 0 : fd_forest_fec_clear( fd_forest_t * forest, ulong slot, uint fec_set_idx, uint max_shred_idx ) {
663 0 : VER_INC;
664 :
665 0 : if( FD_UNLIKELY( slot <= fd_forest_root_slot( forest ) ) ) {
666 0 : FD_LOG_NOTICE(( "fd_forest: fd_forest_fec_clear: slot %lu is <= root slot %lu, ignoring", slot, fd_forest_root_slot( forest ) ));
667 0 : return;
668 0 : }
669 0 : fd_forest_blk_t * ele = query( forest, slot );
670 0 : if( FD_UNLIKELY( !ele ) ) return;
671 0 : if( FD_UNLIKELY( fd_forest_blk_idxs_test( ele->cmpl, max_shred_idx ) ) ) {
672 : /* It's possible the fec_resolver evicted something that we already
673 : completed. One way this can happen is if we produce a FEC set as
674 : leader, but for some reason a validator sends us shreds from that
675 : same FEC set. fec_resolver is still going to buffer those fec
676 : sets, because our own shreds don't go through fec_resolver. So
677 : then we are in a state where we have received fec_complete
678 : messages for all the FECs in our slot, but fec_resolver possibly
679 : has some incomplete ctxs for some of those FEC sets, that will
680 : eventually get evicted). */
681 0 : return;
682 0 : }
683 0 : for( uint i=fec_set_idx; i<=fec_set_idx+max_shred_idx; i++ ) {
684 0 : fd_forest_blk_idxs_remove( ele->idxs, i );
685 0 : }
686 0 : if( FD_UNLIKELY( fec_set_idx == 0 ) ) ele->buffered_idx = UINT_MAX;
687 0 : else ele->buffered_idx = fd_uint_if( ele->buffered_idx != UINT_MAX, fd_uint_min( ele->buffered_idx, fec_set_idx - 1 ), UINT_MAX );
688 0 : }
689 :
690 : fd_forest_blk_t const *
691 0 : fd_forest_publish( fd_forest_t * forest, ulong new_root_slot ) {
692 0 : FD_LOG_DEBUG(( "[%s] slot %lu", __func__, new_root_slot ));
693 :
694 0 : VER_INC;
695 :
696 0 : fd_forest_ancestry_t * ancestry = fd_forest_ancestry( forest );
697 0 : fd_forest_orphaned_t * orphaned = fd_forest_orphaned( forest );
698 0 : fd_forest_frontier_t * frontier = fd_forest_frontier( forest );
699 0 : fd_forest_subtrees_t * subtrees = fd_forest_subtrees( forest );
700 0 : fd_forest_cns_t * conspool = fd_forest_conspool( forest );
701 0 : fd_forest_blk_t * pool = fd_forest_pool( forest );
702 0 : ulong null = fd_forest_pool_idx_null( pool );
703 0 : ulong * queue = fd_forest_deque( forest );
704 :
705 0 : fd_forest_blk_t * old_root_ele = fd_forest_pool_ele( pool, forest->root );
706 0 : fd_forest_blk_t * new_root_ele = query( forest, new_root_slot );
707 :
708 0 : # if FD_FOREST_USE_HANDHOLDING
709 0 : if( FD_LIKELY( new_root_ele ) ) {
710 0 : FD_TEST( new_root_ele->slot > old_root_ele->slot ); /* caller error - inval */
711 0 : }
712 0 : # endif
713 :
714 : /* Edge case where if we haven't been getting repairs, and we have a
715 : gap between the root and orphans. we publish forward to a slot that
716 : we don't have. This only case this should be happening is when we
717 : load a second incremental and that incremental slot lives in the
718 : gap. In that case this isn't a bug, but we should be treating this
719 : new root like the snapshot slot / init root. Should be happening
720 : very rarely given a well-functioning repair. */
721 :
722 0 : if( FD_UNLIKELY( !new_root_ele ) ) {
723 0 : new_root_ele = fd_forest_blk_insert( forest, new_root_slot, 0 );
724 0 : new_root_ele->complete_idx = 0;
725 0 : new_root_ele->buffered_idx = 0;
726 0 : fd_forest_blk_idxs_full( new_root_ele->cmpl );
727 0 : fd_forest_blk_idxs_full( new_root_ele->fecs );
728 0 : advance_consumed_frontier( forest, new_root_slot, 0 ); /* advances consumed frontier if possible */
729 0 : }
730 :
731 : /* First, remove the previous root, and add it to a FIFO prune queue.
732 : head points to the queue head (initialized with old_root_ele). */
733 0 : # if FD_FOREST_USE_HANDHOLDING
734 0 : FD_TEST( fd_forest_deque_cnt( queue ) == 0 );
735 0 : # endif
736 0 : fd_forest_blk_t * head = ancestry_frontier_remove( forest, old_root_ele->slot );
737 0 : if( FD_LIKELY( head ) ) fd_forest_deque_push_tail( queue, fd_forest_pool_idx( pool, head ) );
738 :
739 : /* Second, BFS down the tree, inserting each ele into the prune queue
740 : except for the new root. Loop invariant: head always descends from
741 : old_root_ele and never descends from new_root_ele. */
742 :
743 0 : while( FD_LIKELY( fd_forest_deque_cnt( queue ) ) ) {
744 0 : head = fd_forest_pool_ele( pool, fd_forest_deque_pop_head( queue ) );
745 0 : fd_forest_blk_t * child = fd_forest_pool_ele( pool, head->child );
746 0 : while( FD_LIKELY( child ) ) {
747 0 : if( FD_LIKELY( child != new_root_ele ) ) { /* do not prune new root or descendants */
748 0 : child = ancestry_frontier_remove( forest, child->slot );
749 0 : fd_forest_deque_push_tail( queue, fd_forest_pool_idx( pool, child ) );
750 0 : }
751 0 : child = fd_forest_pool_ele( pool, child->sibling );
752 0 : }
753 :
754 0 : consumed_remove( forest, head->slot );
755 0 : fd_forest_pool_ele_release( pool, head );
756 0 : }
757 :
758 0 : new_root_ele->parent = null; /* unlink new root from parent */
759 0 : forest->root = fd_forest_pool_idx( pool, new_root_ele );
760 :
761 0 : int new_root_is_orphan = fd_forest_subtrees_ele_query( subtrees, &new_root_ele->slot, NULL, pool ) ||
762 0 : fd_forest_orphaned_ele_query( orphaned, &new_root_ele->slot, NULL, pool );
763 0 : if( FD_UNLIKELY( new_root_is_orphan ) ) {
764 :
765 : /* Extend the frontier from the new root */
766 :
767 0 : FD_TEST( fd_forest_deque_empty( queue ) );
768 0 : fd_forest_deque_push_tail( queue, fd_forest_pool_idx( pool, new_root_ele ) );
769 0 : while( FD_LIKELY( fd_forest_deque_cnt( queue ) ) ) {
770 0 : head = fd_forest_pool_ele( pool, fd_forest_deque_pop_head( queue ) );
771 0 : subtrees_orphaned_remove( forest, head->slot );
772 :
773 0 : fd_forest_blk_t * child = fd_forest_pool_ele( pool, head->child );
774 0 : if( FD_LIKELY( child ) ) fd_forest_ancestry_ele_insert( ancestry, head, pool );
775 0 : else fd_forest_frontier_ele_insert( frontier, head, pool );
776 0 : while( child ) {
777 0 : fd_forest_deque_push_tail( queue, fd_forest_pool_idx( pool, child ) );
778 0 : child = fd_forest_pool_ele( pool, child->sibling );
779 0 : }
780 0 : }
781 0 : }
782 :
783 : /* If there is nothing on the consumed, we have hit an edge case
784 : during catching up where all of our repair frontiers were < the new root.
785 : In that case we need to continue repairing from the new root, so
786 : add it to the consumed map. */
787 :
788 0 : if( FD_UNLIKELY( fd_forest_conslist_is_empty( fd_forest_conslist( forest ), conspool ) ) ) {
789 0 : consumed_insert( forest, new_root_ele->slot, fd_forest_pool_idx( pool, new_root_ele ) );
790 0 : new_root_ele->complete_idx = 0;
791 0 : new_root_ele->buffered_idx = 0;
792 0 : fd_forest_blk_idxs_full( new_root_ele->cmpl );
793 0 : fd_forest_blk_idxs_full( new_root_ele->fecs );
794 0 : advance_consumed_frontier( forest, new_root_ele->slot, 0 );
795 0 : }
796 :
797 : /* Lastly, cleanup orphans if there orphan heads < new_root_slot.
798 : First, add any relevant orphans to the prune queue. */
799 :
800 0 : for( fd_forest_subtrees_iter_t iter = fd_forest_subtrees_iter_init( subtrees, pool );
801 0 : !fd_forest_subtrees_iter_done( iter, subtrees, pool );
802 0 : iter = fd_forest_subtrees_iter_next( iter, subtrees, pool ) ) {
803 0 : fd_forest_blk_t * ele = fd_forest_subtrees_iter_ele( iter, subtrees, pool );
804 0 : if( FD_UNLIKELY( ele->slot < new_root_slot ) ) {
805 0 : fd_forest_deque_push_tail( queue, fd_forest_pool_idx( pool, ele ) );
806 0 : }
807 0 : }
808 :
809 : /* Now BFS and clean up children of these orphan heads */
810 0 : while( FD_UNLIKELY( fd_forest_deque_cnt( queue ) ) ) {
811 0 : head = fd_forest_pool_ele( pool, fd_forest_deque_pop_head( queue ) );
812 0 : fd_forest_blk_t * child = fd_forest_pool_ele( pool, head->child );
813 0 : while( FD_LIKELY( child ) ) {
814 0 : if( FD_LIKELY( child != new_root_ele ) ) {
815 0 : fd_forest_deque_push_tail( queue, fd_forest_pool_idx( pool, child ) );
816 0 : }
817 0 : child = fd_forest_pool_ele( pool, child->sibling );
818 0 : }
819 0 : ulong remove = fd_forest_orphaned_idx_remove( orphaned, &head->slot, null, pool ); /* remove myself */
820 0 : remove = fd_ulong_if( remove == null, fd_forest_subtrees_idx_remove( subtrees, &head->slot, null, pool ), remove );
821 0 : fd_forest_pool_ele_release( pool, head ); /* free head */
822 0 : }
823 0 : return new_root_ele;
824 0 : }
825 :
826 : fd_forest_t *
827 0 : fd_forest_clear( fd_forest_t * forest ) {
828 0 : return forest;
829 0 : }
830 :
831 : fd_forest_iter_t
832 0 : fd_forest_iter_init( fd_forest_t * forest ) {
833 : /* Find first element. Anything on the frontier. */
834 0 : fd_forest_blk_t const * pool = fd_forest_pool_const( forest );
835 0 : fd_forest_cns_t const * conspool = fd_forest_conspool_const( forest );
836 0 : fd_forest_conslist_t const * conslist = fd_forest_conslist( forest );
837 :
838 :
839 0 : fd_forest_conslist_iter_t consumed_iter = fd_forest_conslist_iter_fwd_init( conslist, conspool );
840 0 : fd_forest_iter_t repair_iter = { fd_forest_pool_idx_null( pool ),
841 0 : UINT_MAX,
842 0 : fd_fseq_query( fd_forest_ver_const( forest ) ),
843 0 : consumed_iter };
844 :
845 : /* Guaranteed to have at least one element on the consumed frontier */
846 : /* Populate initial iter shred index */
847 :
848 0 : fd_forest_cns_t const * ele_ = fd_forest_conslist_iter_ele_const( consumed_iter, conslist, conspool );
849 0 : fd_forest_blk_t const * ele = fd_forest_pool_ele_const( pool, ele_->forest_pool_idx );
850 :
851 0 : while( ele->complete_idx != UINT_MAX && ele->buffered_idx == ele->complete_idx ) {
852 : /* This fork frontier is actually complete, so we can skip it. Also
853 : handles edge case where we are calling iter_init right after a
854 : forest_init */
855 0 : consumed_iter = fd_forest_conslist_iter_fwd_next( consumed_iter, conslist, conspool );
856 0 : if( FD_UNLIKELY( fd_forest_conslist_iter_done( consumed_iter, conslist, conspool ) ) ) {
857 0 : repair_iter.ele_idx = fd_forest_pool_idx_null( pool );
858 0 : repair_iter.shred_idx = UINT_MAX; /* no more elements */
859 0 : return repair_iter;
860 0 : }
861 0 : ele_ = fd_forest_conslist_iter_ele_const( consumed_iter, conslist, conspool );
862 0 : ele = fd_forest_pool_ele_const( pool, ele_->forest_pool_idx );
863 0 : }
864 :
865 0 : repair_iter.ele_idx = ele_->forest_pool_idx;
866 0 : repair_iter.shred_idx = ele->complete_idx == UINT_MAX ? UINT_MAX : ele->buffered_idx + 1;
867 :
868 0 : return repair_iter;
869 0 : }
870 :
871 : fd_forest_iter_t
872 0 : fd_forest_iter_next( fd_forest_iter_t iter, fd_forest_t const * forest ) {
873 0 : fd_forest_blk_t const * pool = fd_forest_pool_const( forest );
874 0 : fd_forest_blk_t const * ele = fd_forest_pool_ele_const( pool, iter.ele_idx );
875 0 : fd_forest_conslist_t const * conslist = fd_forest_conslist_const( forest );
876 0 : fd_forest_cns_t const * conspool = fd_forest_conspool_const( forest );
877 :
878 0 : if( FD_UNLIKELY( iter.frontier_ver != fd_fseq_query( fd_forest_ver_const( forest ) ) ) ) {
879 : /* If the frontier has changed since we started this traversal, we
880 : need to reset the iterator. */
881 0 : iter.ele_idx = fd_forest_pool_idx_null( pool ) ;
882 0 : iter.shred_idx = UINT_MAX; /* no more elements */
883 0 : return iter;
884 0 : }
885 :
886 0 : uint next_shred_idx = iter.shred_idx;
887 0 : for(;;) {
888 0 : next_shred_idx++;
889 :
890 : /* Case 1: No more shreds in this slot to request, move to the
891 : next one. Wraparound the shred_idx.
892 :
893 : Case 2: original iter.shred_idx == UINT_MAX (implies prev req
894 : was a highest_window_idx request). Also requires moving to next
895 : slot and wrapping the shred_idx. */
896 :
897 0 : if( FD_UNLIKELY( next_shred_idx >= ele->complete_idx || iter.shred_idx == UINT_MAX ) ) {
898 0 : iter.ele_idx = ele->child;
899 0 : ele = fd_forest_pool_ele_const( pool, iter.ele_idx );
900 0 : if( FD_UNLIKELY( iter.ele_idx == fd_forest_pool_idx_null( pool ) ) ) {
901 0 : iter.shred_idx = UINT_MAX; /* no more elements */
902 :
903 : /* If the frontier pool hasn't changed at all since we started
904 : this traversal, we can cleanly select the next node in the
905 : frontier using the stored frontier iterator. If the frontier
906 : has changed though, we should just return done and let the
907 : caller reset the iterator. */
908 :
909 0 : if( FD_LIKELY( iter.frontier_ver == fd_fseq_query( fd_forest_ver_const( forest ) ) ) ) {
910 0 : iter.head = fd_forest_conslist_iter_fwd_next( iter.head, conslist, conspool );
911 0 : if( FD_UNLIKELY( !fd_forest_conslist_iter_done( iter.head, conslist, conspool ) ) ) {
912 0 : iter.ele_idx = fd_forest_conslist_iter_ele_const( iter.head, conslist, conspool )->forest_pool_idx;
913 0 : ele = fd_forest_pool_ele_const( pool, iter.ele_idx );
914 0 : iter.shred_idx = ele->complete_idx == UINT_MAX ? UINT_MAX : ele->buffered_idx + 1;
915 0 : } else {
916 0 : iter.ele_idx = fd_forest_pool_idx_null( pool ); /* no more elements */
917 0 : iter.shred_idx = UINT_MAX;
918 0 : }
919 0 : }
920 0 : return iter;
921 0 : }
922 0 : next_shred_idx = ele->buffered_idx + 1;
923 0 : }
924 :
925 : /* Common case - valid shred to request. Note you can't know the
926 : ele->complete_idx until you have actually received the slot
927 : complete shred, thus the we can do lt instead of leq */
928 :
929 0 : if( ele->complete_idx != UINT_MAX &&
930 0 : next_shred_idx < ele->complete_idx &&
931 0 : !fd_forest_blk_idxs_test( ele->idxs, next_shred_idx ) ) {
932 0 : iter.shred_idx = next_shred_idx;
933 0 : break;
934 0 : }
935 :
936 : /* Current slot actually needs a highest_window_idx request */
937 :
938 0 : if( FD_UNLIKELY( ele->complete_idx == UINT_MAX ) ) {
939 0 : iter.shred_idx = UINT_MAX;
940 0 : break;
941 0 : }
942 0 : }
943 0 : return iter;
944 0 : }
945 :
946 : int
947 0 : fd_forest_iter_done( fd_forest_iter_t iter, fd_forest_t const * forest ) {
948 0 : fd_forest_blk_t const * pool = fd_forest_pool_const( forest );
949 0 : return iter.ele_idx == fd_forest_pool_idx_null( pool ); /* no more elements */
950 0 : }
951 :
952 : #include <stdio.h>
953 :
954 : static void
955 0 : preorder( fd_forest_t const * forest, fd_forest_blk_t const * ele ) {
956 0 : fd_forest_blk_t const * pool = fd_forest_pool_const( forest );
957 0 : fd_forest_blk_t const * child = fd_forest_pool_ele_const( pool, ele->child );
958 0 : printf( "%lu ", ele->slot );
959 0 : while( FD_LIKELY( child ) ) {
960 0 : preorder( forest, child );
961 0 : child = fd_forest_pool_ele_const( pool, child->sibling );
962 0 : }
963 0 : }
964 :
965 : void
966 0 : fd_forest_preorder_print( fd_forest_t const * forest ) {
967 0 : FD_LOG_NOTICE( ( "\n\n[Preorder]" ) );
968 0 : preorder( forest, fd_forest_pool_ele_const( fd_forest_pool_const( forest ), forest->root ) );
969 0 : printf( "\n\n" );
970 0 : }
971 :
972 : /* TODO use bit tricks / change */
973 : static int
974 0 : num_digits( ulong slot ) {
975 : /* using log10 */
976 0 : int digits = 0;
977 0 : while( slot ) {
978 0 : digits++;
979 0 : slot /= 10;
980 0 : }
981 0 : return digits;
982 0 : }
983 :
984 : static void
985 : ancestry_print2( fd_forest_t const * forest,
986 : fd_forest_blk_t const * ele,
987 : fd_forest_blk_t const * prev,
988 : ulong last_printed,
989 : int depth,
990 0 : const char * prefix ) {
991 :
992 0 : if( FD_UNLIKELY( ele == NULL ) ) return;
993 :
994 0 : fd_forest_blk_t const * pool = fd_forest_pool_const( forest );
995 0 : int digits = num_digits( ele->slot );
996 :
997 : /* If there is a prefix, this means we are on a fork, and we need to
998 : indent to the correct depth. We do depth - 1 for more satisfying
999 : spacing. */
1000 0 : if( FD_UNLIKELY( strcmp( prefix, "" ) ) ) {
1001 0 : for( int i = 0; i < depth - 1; i++ ) printf( " " );
1002 0 : if( depth > 0 ) printf( "%s", prefix );
1003 0 : }
1004 :
1005 0 : if ( FD_UNLIKELY( !prev ) ) { // New interval
1006 0 : printf("[%lu" , ele->slot );
1007 0 : last_printed = ele->slot;
1008 0 : depth += 1 + digits;
1009 0 : }
1010 :
1011 0 : fd_forest_blk_t const * curr = fd_forest_pool_ele_const( pool, ele->child );
1012 :
1013 : /* Cases in which we close the interval:
1014 : 1. the slots are no longer consecutive. no eliding, close bracket
1015 : 2. current ele has multiple children, want to print forks.
1016 : Maintain last_printed on this fork so that we don't print [a, a]
1017 : intervals. */
1018 :
1019 0 : fd_forest_blk_t const * new_prev = ele;
1020 :
1021 0 : if( prev && prev->slot != ele->slot - 1 ) { // non-consecutive, do not elide
1022 0 : if( last_printed == prev->slot ){
1023 0 : printf( "] ── [%lu", ele->slot );
1024 0 : depth += digits + 6;
1025 0 : } else {
1026 0 : printf( ", %lu] ── [%lu", prev->slot, ele->slot );
1027 0 : depth += digits + num_digits(prev->slot ) + 8;
1028 0 : }
1029 0 : last_printed = ele->slot;
1030 0 : } else if( curr && curr->sibling != ULONG_MAX ) { // has multiple children, do not elide
1031 0 : if( last_printed == ele->slot ){
1032 0 : printf( "] ── " );
1033 0 : depth += 5;
1034 0 : } else {
1035 0 : printf( ", %lu] ── ", ele->slot );
1036 0 : depth += digits + 2;
1037 0 : }
1038 0 : last_printed = ele->slot;
1039 0 : new_prev = NULL;
1040 0 : }
1041 :
1042 0 : if( !curr ){ // no children, close bracket, end fork
1043 0 : if( last_printed == ele->slot ){
1044 0 : printf( "]\n" );
1045 0 : } else {
1046 0 : printf( ", %lu]\n", ele->slot );
1047 0 : }
1048 0 : return;
1049 0 : }
1050 :
1051 0 : char new_prefix[512]; /* FIXME size this correctly */
1052 0 : new_prefix[0] = '\0'; /* first fork stays on the same line, no prefix */
1053 0 : while( curr ) {
1054 0 : if( fd_forest_pool_ele_const( pool, curr->sibling ) ) {
1055 0 : ancestry_print2( forest, curr, new_prev, last_printed, depth, new_prefix );
1056 0 : } else {
1057 0 : ancestry_print2( forest, curr, new_prev, last_printed, depth, new_prefix );
1058 0 : }
1059 0 : curr = fd_forest_pool_ele_const( pool, curr->sibling );
1060 :
1061 : /* Set up prefix for following iterations */
1062 0 : if( curr && curr->sibling != ULONG_MAX ) {
1063 0 : sprintf( new_prefix, "├── " ); /* any following forks start on new lines */
1064 0 : } else {
1065 0 : sprintf( new_prefix, "└── " ); /* any following forks start on new lines */
1066 0 : }
1067 0 : }
1068 :
1069 0 : }
1070 :
1071 : static void
1072 0 : ancestry_print3( fd_forest_t const * forest, fd_forest_blk_t const * ele, int space, const char * prefix, fd_forest_blk_t const * prev, int elide ) {
1073 0 : fd_forest_blk_t const * pool = fd_forest_pool_const( forest );
1074 :
1075 0 : if( ele == NULL ) return;
1076 :
1077 : /* print the slot itself. either we might need to start a new interval, or it may get elided */
1078 0 : fd_forest_blk_t const * child = fd_forest_pool_ele_const( pool, ele->child );
1079 :
1080 0 : if( !elide ) {
1081 0 : if( space > 0 ) printf( "\n" );
1082 0 : for( int i = 0; i < space; i++ ) printf( " " );
1083 0 : printf( "%s", prefix );
1084 0 : printf( "%lu", ele->slot );
1085 0 : }
1086 :
1087 0 : if( !child && !elide ) { /* double check these cases arent the same...*/
1088 0 : printf( "]" );
1089 0 : return;
1090 0 : } /* no children, close bracket */
1091 :
1092 0 : if( !child && elide ) {
1093 0 : printf( ", %lu]", ele->slot );
1094 0 : return;
1095 0 : }
1096 :
1097 0 : prev = ele;
1098 0 : char new_prefix[1024]; /* FIXME size this correctly */
1099 0 : int one_child = child && child->sibling == ULONG_MAX;
1100 0 : if( one_child &&
1101 0 : child->slot != ele->slot + 1 ) { // if I have ONE CHILD and one child is non-consecutive
1102 :
1103 0 : if( elide ) {
1104 : /* current slot wasn't printed, but now that we are branching,
1105 : we will want to print the current slot and close the bracket */
1106 0 : printf( ", %lu]", ele->slot );
1107 0 : space += fd_int_max( num_digits( ele->slot ) + 2, 0 );
1108 0 : } else {
1109 0 : printf( "]");
1110 0 : }
1111 :
1112 0 : sprintf( new_prefix, "└── [" ); /* end branch */
1113 0 : ancestry_print3( forest, child, space + 5, new_prefix, prev, 0 );
1114 0 : } else if ( one_child && child->slot == ele->slot + 1 ) {
1115 0 : ancestry_print3( forest, child, space, prefix, prev, 1);
1116 0 : } else { /* multiple children */
1117 0 : if( elide ) {
1118 : /* current slot wasn't printed, but now that we are branching,
1119 : we will want to print the current slot and close the bracket */
1120 0 : printf( ", %lu]", ele->slot );
1121 0 : space += fd_int_max( num_digits( ele->slot ) + 2, 0 );
1122 0 : } else {
1123 0 : printf( "]");
1124 0 : }
1125 :
1126 0 : while( child ) {
1127 0 : if( fd_forest_pool_ele_const( pool, child->sibling ) ) {
1128 0 : sprintf( new_prefix, "├── [" ); /* branch indicating more siblings follow */
1129 0 : ancestry_print3( forest, child, space + 5, new_prefix, prev, 0 );
1130 0 : } else {
1131 0 : sprintf( new_prefix, "└── [" ); /* end branch */
1132 0 : ancestry_print3( forest, child, space + 5, new_prefix, prev, 0 );
1133 0 : }
1134 0 : child = fd_forest_pool_ele_const( pool, child->sibling );
1135 0 : }
1136 0 : }
1137 0 : }
1138 :
1139 : void
1140 0 : fd_forest_ancestry_print( fd_forest_t const * forest ) {
1141 0 : printf(("\n\n[Ancestry]\n" ) );
1142 0 : ancestry_print3( forest, fd_forest_pool_ele_const( fd_forest_pool_const( forest ), forest->root ), 0, "[", NULL, 0 );
1143 0 : fflush(stdout); /* Ensure ancestry printf output is flushed */
1144 0 : }
1145 :
1146 : void
1147 0 : fd_forest_frontier_print( fd_forest_t const * forest ) {
1148 0 : printf( "\n\n[Repairing Next]\n" );
1149 0 : fd_forest_conslist_t const * conslist = fd_forest_conslist_const( forest );
1150 0 : fd_forest_cns_t const * conspool = fd_forest_conspool_const( forest );
1151 0 : fd_forest_blk_t const * pool = fd_forest_pool_const( forest );
1152 0 : for( fd_forest_conslist_iter_t iter = fd_forest_conslist_iter_fwd_init( conslist, conspool );
1153 0 : !fd_forest_conslist_iter_done( iter, conslist, conspool );
1154 0 : iter = fd_forest_conslist_iter_fwd_next( iter, conslist, conspool ) ) {
1155 0 : fd_forest_cns_t const * ele = fd_forest_conslist_iter_ele_const( iter, conslist, conspool );
1156 0 : fd_forest_blk_t const * ele_ = fd_forest_pool_ele_const( pool, ele->forest_pool_idx );
1157 0 : printf("%lu (%u/%u)\n", ele_->slot, ele_->buffered_idx + 1, ele_->complete_idx + 1 );
1158 : //ancestry_print( forest, fd_forest_pool_ele_const( fd_forest_pool_const( forest ), fd_forest_pool_idx( pool, ele ) ), 0, "" );
1159 0 : }
1160 0 : fflush(stdout);
1161 0 : }
1162 :
1163 : void
1164 0 : fd_forest_orphaned_print( fd_forest_t const * forest ) {
1165 0 : printf( "\n[Orphaned]\n" );
1166 0 : fd_forest_subtrees_t const * subtrees = fd_forest_subtrees_const( forest );
1167 0 : fd_forest_blk_t const * pool = fd_forest_pool_const( forest );
1168 0 : for( fd_forest_subtrees_iter_t iter = fd_forest_subtrees_iter_init( subtrees, pool );
1169 0 : !fd_forest_subtrees_iter_done( iter, subtrees, pool );
1170 0 : iter = fd_forest_subtrees_iter_next( iter, subtrees, pool ) ) {
1171 0 : fd_forest_blk_t const * ele = fd_forest_subtrees_iter_ele_const( iter, subtrees, pool );
1172 0 : ancestry_print2( forest, fd_forest_pool_ele_const( fd_forest_pool_const( forest ), fd_forest_pool_idx( pool, ele ) ), NULL, 0, 0, "" );
1173 0 : }
1174 0 : fflush(stdout);
1175 0 : }
1176 :
1177 : void
1178 0 : fd_forest_print( fd_forest_t const * forest ) {
1179 0 : if( FD_UNLIKELY( forest->root == ULONG_MAX ) ) return;
1180 0 : FD_LOG_NOTICE(("\n\n[Forest]" ) );
1181 0 : fd_forest_ancestry_print( forest );
1182 0 : fd_forest_frontier_print( forest );
1183 0 : fd_forest_orphaned_print( forest );
1184 0 : printf("\n");
1185 : fflush(stdout);
1186 0 : }
1187 :
1188 : #undef FD_FOREST_PRINT
|
