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