Line data Source code
1 : #include "fd_forest.h"
2 :
3 : static fd_hash_t empty_mr = { .ul = { 0, 0, 0, 0 } };
4 : static fd_hash_t invalid_mr = { .ul = { ULONG_MAX, ULONG_MAX, ULONG_MAX, ULONG_MAX } };
5 :
6 : static ulong *
7 177384 : fd_forest_deque( fd_forest_t * forest ) {
8 177384 : return fd_wksp_laddr_fast( fd_forest_wksp( forest ), forest->deque_gaddr );
9 177384 : }
10 :
11 : void *
12 96 : fd_forest_new( void * shmem, ulong ele_max, ulong seed ) {
13 96 : FD_TEST( fd_ulong_is_pow2( ele_max ) );
14 :
15 96 : if( FD_UNLIKELY( !shmem ) ) {
16 0 : FD_LOG_WARNING(( "NULL mem" ));
17 0 : return NULL;
18 0 : }
19 :
20 96 : if( FD_UNLIKELY( !fd_ulong_is_aligned( (ulong)shmem, fd_forest_align() ) ) ) {
21 0 : FD_LOG_WARNING(( "misaligned mem" ));
22 0 : return NULL;
23 0 : }
24 :
25 96 : ulong footprint = fd_forest_footprint( ele_max );
26 96 : if( FD_UNLIKELY( !footprint ) ) {
27 0 : FD_LOG_WARNING(( "bad ele_max (%lu)", ele_max ));
28 0 : return NULL;
29 0 : }
30 :
31 96 : fd_wksp_t * wksp = fd_wksp_containing( shmem );
32 96 : if( FD_UNLIKELY( !wksp ) ) {
33 0 : FD_LOG_WARNING(( "shmem must be part of a workspace" ));
34 0 : return NULL;
35 0 : }
36 :
37 96 : fd_memset( shmem, 0, footprint );
38 96 : fd_forest_t * forest;
39 :
40 96 : FD_SCRATCH_ALLOC_INIT( l, shmem );
41 96 : forest = FD_SCRATCH_ALLOC_APPEND( l, fd_forest_align(), sizeof(fd_forest_t) );
42 96 : void * pool = FD_SCRATCH_ALLOC_APPEND( l, fd_forest_pool_align(), fd_forest_pool_footprint ( ele_max ) );
43 96 : void * ancestry = FD_SCRATCH_ALLOC_APPEND( l, fd_forest_ancestry_align(), fd_forest_ancestry_footprint( ele_max ) );
44 96 : void * frontier = FD_SCRATCH_ALLOC_APPEND( l, fd_forest_frontier_align(), fd_forest_frontier_footprint( ele_max ) );
45 96 : void * subtrees = FD_SCRATCH_ALLOC_APPEND( l, fd_forest_subtrees_align(), fd_forest_subtrees_footprint( ele_max ) );
46 96 : void * orphaned = FD_SCRATCH_ALLOC_APPEND( l, fd_forest_orphaned_align(), fd_forest_orphaned_footprint( ele_max ) );
47 96 : void * subtlist = FD_SCRATCH_ALLOC_APPEND( l, fd_forest_subtlist_align(), fd_forest_subtlist_footprint( ) );
48 :
49 : /* indexers */
50 :
51 96 : void * requestd = FD_SCRATCH_ALLOC_APPEND( l, fd_forest_requests_align(), fd_forest_requests_footprint( ele_max ) );
52 96 : void * reqslist = FD_SCRATCH_ALLOC_APPEND( l, fd_forest_reqslist_align(), fd_forest_reqslist_footprint( ) );
53 96 : void * reqspool = FD_SCRATCH_ALLOC_APPEND( l, fd_forest_reqspool_align(), fd_forest_reqspool_footprint( ele_max ) );
54 96 : void * consumed = FD_SCRATCH_ALLOC_APPEND( l, fd_forest_consumed_align(), fd_forest_consumed_footprint( ele_max ) );
55 96 : void * conslist = FD_SCRATCH_ALLOC_APPEND( l, fd_forest_conslist_align(), fd_forest_conslist_footprint( ) );
56 96 : void * conspool = FD_SCRATCH_ALLOC_APPEND( l, fd_forest_conspool_align(), fd_forest_conspool_footprint( ele_max ) );
57 96 : void * orphreqs = FD_SCRATCH_ALLOC_APPEND( l, fd_forest_requests_align(), fd_forest_requests_footprint( ele_max ) );
58 96 : void * orphlist = FD_SCRATCH_ALLOC_APPEND( l, fd_forest_reqslist_align(), fd_forest_reqslist_footprint( ) );
59 96 : void * deque = FD_SCRATCH_ALLOC_APPEND( l, fd_forest_deque_align(), fd_forest_deque_footprint ( ele_max ) );
60 96 : FD_TEST( FD_SCRATCH_ALLOC_FINI( l, fd_forest_align() ) == (ulong)shmem + footprint );
61 :
62 96 : forest->root = ULONG_MAX;
63 96 : forest->wksp_gaddr = fd_wksp_gaddr_fast( wksp, forest );
64 96 : forest->pool_gaddr = fd_wksp_gaddr_fast( wksp, fd_forest_pool_join ( fd_forest_pool_new ( pool, ele_max ) ) );
65 96 : forest->ancestry_gaddr = fd_wksp_gaddr_fast( wksp, fd_forest_ancestry_join( fd_forest_ancestry_new( ancestry, ele_max, seed ) ) );
66 96 : forest->frontier_gaddr = fd_wksp_gaddr_fast( wksp, fd_forest_frontier_join( fd_forest_frontier_new( frontier, ele_max, seed ) ) );
67 96 : forest->subtrees_gaddr = fd_wksp_gaddr_fast( wksp, fd_forest_subtrees_join( fd_forest_subtrees_new( subtrees, ele_max, seed ) ) );
68 96 : forest->orphaned_gaddr = fd_wksp_gaddr_fast( wksp, fd_forest_orphaned_join( fd_forest_orphaned_new( orphaned, ele_max, seed ) ) );
69 96 : forest->subtlist_gaddr = fd_wksp_gaddr_fast( wksp, fd_forest_subtlist_join( fd_forest_subtlist_new( subtlist ) ) );
70 :
71 : /* indexers */
72 :
73 96 : forest->requests_gaddr = fd_wksp_gaddr_fast( wksp, fd_forest_requests_join( fd_forest_requests_new( requestd, ele_max, seed ) ) );
74 96 : forest->reqslist_gaddr = fd_wksp_gaddr_fast( wksp, fd_forest_reqslist_join( fd_forest_reqslist_new( reqslist ) ) );
75 96 : forest->reqspool_gaddr = fd_wksp_gaddr_fast( wksp, fd_forest_reqspool_join( fd_forest_reqspool_new( reqspool, ele_max ) ) );
76 96 : forest->consumed_gaddr = fd_wksp_gaddr_fast( wksp, fd_forest_consumed_join( fd_forest_consumed_new( consumed, ele_max, seed ) ) );
77 96 : forest->conslist_gaddr = fd_wksp_gaddr_fast( wksp, fd_forest_conslist_join( fd_forest_conslist_new( conslist ) ) );
78 96 : forest->conspool_gaddr = fd_wksp_gaddr_fast( wksp, fd_forest_conspool_join( fd_forest_conspool_new( conspool, ele_max ) ) );
79 96 : forest->orphreqs_gaddr = fd_wksp_gaddr_fast( wksp, fd_forest_requests_join( fd_forest_requests_new( orphreqs, ele_max, seed ) ) );
80 96 : forest->orphlist_gaddr = fd_wksp_gaddr_fast( wksp, fd_forest_reqslist_join( fd_forest_reqslist_new( orphlist ) ) );
81 96 : forest->deque_gaddr = fd_wksp_gaddr_fast( wksp, fd_forest_deque_join ( fd_forest_deque_new ( deque, ele_max ) ) );
82 96 : forest->iter = (fd_forest_iter_t){ .ele_idx = ULONG_MAX, .list_gaddr = forest->reqslist_gaddr };
83 96 : forest->orphiter = (fd_forest_iter_t){ .ele_idx = ULONG_MAX, .list_gaddr = forest->orphlist_gaddr };
84 :
85 96 : FD_COMPILER_MFENCE();
86 96 : FD_VOLATILE( forest->magic ) = FD_FOREST_MAGIC;
87 96 : FD_COMPILER_MFENCE();
88 :
89 96 : return shmem;
90 96 : }
91 :
92 : fd_forest_t *
93 96 : fd_forest_join( void * shforest ) {
94 96 : fd_forest_t * forest = (fd_forest_t *)shforest;
95 :
96 96 : if( FD_UNLIKELY( !forest ) ) {
97 0 : FD_LOG_WARNING(( "NULL forest" ));
98 0 : return NULL;
99 0 : }
100 :
101 96 : if( FD_UNLIKELY( !fd_ulong_is_aligned((ulong)forest, fd_forest_align() ) ) ) {
102 0 : FD_LOG_WARNING(( "misaligned forest" ));
103 0 : return NULL;
104 0 : }
105 :
106 96 : fd_wksp_t * wksp = fd_wksp_containing( forest );
107 96 : if( FD_UNLIKELY( !wksp ) ) {
108 0 : FD_LOG_WARNING(( "forest must be part of a workspace" ));
109 0 : return NULL;
110 0 : }
111 :
112 96 : return forest;
113 96 : }
114 :
115 : void *
116 36 : fd_forest_leave( fd_forest_t const * forest ) {
117 :
118 36 : if( FD_UNLIKELY( !forest ) ) {
119 0 : FD_LOG_WARNING(( "NULL forest" ));
120 0 : return NULL;
121 0 : }
122 :
123 36 : return (void *)forest;
124 36 : }
125 :
126 : void *
127 36 : fd_forest_delete( void * forest ) {
128 :
129 36 : if( FD_UNLIKELY( !forest ) ) {
130 0 : FD_LOG_WARNING(( "NULL forest" ));
131 0 : return NULL;
132 0 : }
133 :
134 36 : if( FD_UNLIKELY( !fd_ulong_is_aligned((ulong)forest, fd_forest_align() ) ) ) {
135 0 : FD_LOG_WARNING(( "misaligned forest" ));
136 0 : return NULL;
137 0 : }
138 :
139 : // TODO: zero out mem?
140 :
141 36 : return forest;
142 36 : }
143 :
144 : static void
145 : requests_insert( fd_forest_t * forest,
146 : fd_forest_requests_t * reqsmap,
147 : fd_forest_reqslist_t * reqslist,
148 420 : ulong pool_idx ) {
149 420 : fd_forest_ref_t * pool = fd_forest_reqspool( forest );
150 420 : if( fd_forest_requests_ele_query( reqsmap, &pool_idx, NULL, pool ) ) return;
151 405 : fd_forest_ref_t * ele = fd_forest_reqspool_ele_acquire( pool );
152 405 : ele->idx = pool_idx;
153 405 : fd_forest_requests_ele_insert( reqsmap, ele, pool );
154 405 : fd_forest_reqslist_ele_push_tail( reqslist, ele, pool );
155 405 : }
156 :
157 : static void
158 : requests_remove( fd_forest_t * forest,
159 : fd_forest_requests_t * reqsmap,
160 : fd_forest_reqslist_t * reqslist,
161 : fd_forest_iter_t * reqiter,
162 22005 : ulong pool_idx ) {
163 22005 : fd_forest_ref_t * pool = fd_forest_reqspool( forest );
164 22005 : fd_forest_ref_t * ele;
165 22005 : if( FD_LIKELY( ele = fd_forest_requests_ele_remove( reqsmap, &pool_idx, NULL, pool ) ) ) {
166 : /* invalidate the iterator if it is on the removed slot. */
167 141 : if( FD_UNLIKELY( reqiter->ele_idx == pool_idx ) ) {
168 9 : reqiter->ele_idx = ULONG_MAX;
169 9 : }
170 141 : fd_forest_reqslist_ele_remove( reqslist, ele, pool );
171 141 : fd_forest_reqspool_ele_release( pool, ele );
172 141 : }
173 22005 : }
174 :
175 : static void
176 519 : consumed_insert( fd_forest_t * forest, ulong pool_idx ) {
177 519 : fd_forest_consumed_t * consumed = fd_forest_consumed( forest );
178 519 : fd_forest_ref_t * pool = fd_forest_conspool( forest );
179 519 : fd_forest_ref_t * ele = fd_forest_conspool_ele_acquire( pool );
180 519 : ele->idx = pool_idx;
181 519 : fd_forest_consumed_ele_insert( consumed, ele, pool );
182 519 : fd_forest_conslist_ele_push_tail( fd_forest_conslist( forest ), ele, pool );
183 519 : }
184 :
185 : static void
186 11355 : consumed_remove( fd_forest_t * forest, ulong forest_pool_idx ) {
187 11355 : fd_forest_consumed_t * consumed = fd_forest_consumed( forest );
188 11355 : fd_forest_ref_t * pool = fd_forest_conspool( forest );
189 11355 : fd_forest_ref_t * ele;
190 11355 : if( FD_LIKELY( ele = fd_forest_consumed_ele_remove( consumed, &forest_pool_idx, NULL, pool ) ) ) {
191 396 : fd_forest_conslist_ele_remove( fd_forest_conslist( forest ), ele, pool );
192 396 : fd_forest_conspool_ele_release( pool, ele );
193 396 : }
194 11355 : }
195 :
196 : fd_forest_t *
197 96 : fd_forest_init( fd_forest_t * forest, ulong root_slot ) {
198 96 : fd_forest_blk_t * pool = fd_forest_pool( forest );
199 96 : ulong null = fd_forest_pool_idx_null( pool );
200 96 : fd_forest_frontier_t * frontier = fd_forest_frontier( forest );
201 :
202 : /* Initialize the root node from a pool element. */
203 :
204 96 : fd_forest_blk_t * root_ele = fd_forest_pool_ele_acquire( pool );
205 96 : root_ele->slot = root_slot;
206 96 : root_ele->parent = null;
207 96 : root_ele->child = null;
208 96 : root_ele->sibling = null;
209 96 : root_ele->buffered_idx = 0;
210 96 : root_ele->complete_idx = 0;
211 96 : root_ele->chain_confirmed = 1;
212 :
213 96 : root_ele->merkle_roots[0].mr = (fd_hash_t){ .key = { 0 } };
214 :
215 96 : forest->root = fd_forest_pool_idx( pool, root_ele );
216 96 : fd_forest_frontier_ele_insert( frontier, root_ele, pool ); /* cannot fail */
217 96 : consumed_insert( forest, fd_forest_pool_idx( pool, root_ele ) );
218 :
219 : /* Sanity checks. */
220 :
221 96 : FD_TEST( root_ele == fd_forest_frontier_ele_query( frontier, &root_slot, NULL, pool ));
222 96 : FD_TEST( root_ele->slot == root_slot );
223 :
224 96 : return forest;
225 96 : }
226 :
227 : int
228 114 : fd_forest_verify( fd_forest_t const * forest ) {
229 114 : #define FAIL( msg ) do { FD_LOG_WARNING(( "fd_forest_verify: %s", msg )); return -1; } while(0)
230 114 : if( FD_UNLIKELY( !forest ) ) {
231 0 : FAIL( "NULL forest" );
232 0 : }
233 :
234 114 : if( FD_UNLIKELY( !fd_ulong_is_aligned( (ulong)forest, fd_forest_align() ) ) ) {
235 0 : FAIL( "misaligned forest" );
236 0 : }
237 :
238 114 : fd_wksp_t * wksp = fd_wksp_containing( forest );
239 114 : if( FD_UNLIKELY( !wksp ) ) {
240 0 : FAIL( "forest must be part of a workspace" );
241 0 : }
242 :
243 114 : if( FD_UNLIKELY( forest->magic!=FD_FOREST_MAGIC ) ) {
244 0 : FAIL( "bad magic" );
245 0 : }
246 :
247 114 : fd_forest_blk_t const * pool = fd_forest_pool_const( forest );
248 :
249 114 : fd_forest_frontier_t const * frontier = fd_forest_frontier_const( forest );
250 114 : fd_forest_orphaned_t const * orphaned = fd_forest_orphaned_const( forest );
251 114 : fd_forest_ancestry_t const * ancestry = fd_forest_ancestry_const( forest );
252 114 : fd_forest_subtrees_t const * subtrees = fd_forest_subtrees_const( forest );
253 :
254 114 : if( fd_forest_ancestry_verify( ancestry, fd_forest_pool_max( pool ), pool ) == -1 ) FAIL( "ancestry map corrupted" );
255 114 : if( fd_forest_frontier_verify( frontier, fd_forest_pool_max( pool ), pool ) == -1 ) FAIL( "frontier map corrupted" );
256 114 : if( fd_forest_subtrees_verify( subtrees, fd_forest_pool_max( pool ), pool ) == -1 ) FAIL( "subtrees map corrupted" );
257 114 : if( fd_forest_orphaned_verify( orphaned, fd_forest_pool_max( pool ), pool ) == -1 ) FAIL( "orphaned map corrupted" );
258 :
259 : /* Invariant: elements can only appear in one of the four maps. */
260 285 : 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 ) ) {
261 171 : fd_forest_blk_t const * ele = fd_forest_frontier_iter_ele_const( iter, frontier, pool );
262 171 : if( fd_forest_ancestry_ele_query_const( ancestry, &ele->slot, NULL, pool ) ) FAIL( "element in frontier map also in ancestry map" );
263 171 : if( fd_forest_orphaned_ele_query_const( orphaned, &ele->slot, NULL, pool ) ) FAIL( "element in frontier map also in orphaned map" );
264 171 : if( fd_forest_subtrees_ele_query_const( subtrees, &ele->slot, NULL, pool ) ) FAIL( "element in frontier map also in subtrees map" );
265 171 : }
266 :
267 168 : 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 ) ) {
268 54 : fd_forest_blk_t const * ele = fd_forest_orphaned_iter_ele_const( iter, orphaned, pool );
269 54 : if( fd_forest_ancestry_ele_query_const( ancestry, &ele->slot, NULL, pool ) ) FAIL( "element in orphaned map also in ancestry map" );
270 54 : if( fd_forest_frontier_ele_query_const( frontier, &ele->slot, NULL, pool ) ) FAIL( "element in orphaned map also in frontier map" );
271 54 : if( fd_forest_subtrees_ele_query_const( subtrees, &ele->slot, NULL, pool ) ) FAIL( "element in orphaned map also in subtrees map" );
272 54 : }
273 :
274 159 : 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 ) ) {
275 45 : fd_forest_blk_t const * ele = fd_forest_subtrees_iter_ele_const( iter, subtrees, pool );
276 45 : if( fd_forest_ancestry_ele_query_const( ancestry, &ele->slot, NULL, pool ) ) FAIL( "element in subtrees map also in ancestry map" );
277 45 : if( fd_forest_frontier_ele_query_const( frontier, &ele->slot, NULL, pool ) ) FAIL( "element in subtrees map also in frontier map" );
278 45 : if( fd_forest_orphaned_ele_query_const( orphaned, &ele->slot, NULL, pool ) ) FAIL( "element in subtrees map also in orphaned map" );
279 45 : }
280 :
281 114 : fd_forest_consumed_t const * consumed = fd_forest_consumed_const( forest );
282 114 : fd_forest_ref_t const * conspool = fd_forest_conspool_const( forest );
283 :
284 : /* from every frontier walk back and verify that there is an ancestor in the consumed map */
285 285 : 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 ) ) {
286 171 : fd_forest_blk_t const * ele = fd_forest_frontier_iter_ele_const( iter, frontier, pool );
287 171 : int found = 0;
288 324 : while( FD_LIKELY( ele ) ) {
289 324 : ulong ele_idx = fd_forest_pool_idx( pool, ele );
290 324 : if( fd_forest_consumed_ele_query_const( consumed, &ele_idx, NULL, conspool ) ) {
291 171 : found = 1;
292 171 : break;
293 171 : }
294 153 : ele = fd_forest_pool_ele_const( pool, ele->parent );
295 153 : }
296 171 : if( FD_UNLIKELY( !found ) ) FAIL( "element in frontier map does not have an ancestor in the consumed map" );
297 171 : }
298 :
299 : /* Consumed map elements must be in the frontier or ancestry map. */
300 :
301 264 : 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 ) ) {
302 150 : fd_forest_ref_t const * ele = fd_forest_consumed_iter_ele_const( iter, consumed, conspool );
303 150 : fd_forest_blk_t const * ele_ = fd_forest_pool_ele_const( pool, ele->idx );
304 150 : if( !fd_forest_ancestry_ele_query_const( ancestry, &ele_->slot, NULL, pool ) && !fd_forest_frontier_ele_query_const( frontier, &ele_->slot, NULL, pool ) ) {
305 0 : FAIL( "element in consumed map not in the ancestry or frontier map" );
306 0 : }
307 150 : }
308 :
309 : /* Request map + list invariants */
310 114 : fd_forest_requests_t const * requests = fd_forest_requests_const( forest );
311 114 : fd_forest_reqslist_t const * reqslist = fd_forest_reqslist_const( forest );
312 114 : fd_forest_ref_t const * reqspool = fd_forest_reqspool_const( forest );
313 :
314 114 : if( forest->iter.ele_idx != fd_forest_pool_idx_null( pool ) &&
315 114 : forest->iter.ele_idx != fd_forest_reqslist_ele_peek_head_const( reqslist, reqspool )->idx ) {
316 0 : FAIL( "iterator is not at the head of the request list" );
317 0 : }
318 :
319 : /* Every element in the request list must be in the request map */
320 228 : 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 ) ) {
321 114 : fd_forest_ref_t const * ele = fd_forest_reqslist_iter_ele_const( iter, reqslist, reqspool );
322 114 : fd_forest_blk_t const * ele_ = fd_forest_pool_ele_const( pool, ele->idx );
323 114 : if( !fd_forest_ancestry_ele_query_const( ancestry, &ele_->slot, NULL, pool ) && !fd_forest_frontier_ele_query_const( frontier, &ele_->slot, NULL, pool ) ) {
324 0 : FAIL( "element in request list not in the ancestry or frontier map" );
325 0 : }
326 114 : if( !fd_forest_requests_ele_query_const( requests, &ele->idx, NULL, reqspool ) ) FAIL( "element in request list not in the request map" );
327 114 : }
328 :
329 : /* Orphan request map + list invariants. The orphan request map and
330 : list share the same reqspool with the main request map and list, so
331 : in addition to being internally consistent, a block must never be in
332 : both the main request map and the orphan request map - that would
333 : leave duplicate references to the same pool idx and corrupt the
334 : shared pool when one of them is removed. */
335 :
336 114 : fd_forest_requests_t const * orphreqs = fd_forest_orphreqs_const( forest );
337 114 : fd_forest_reqslist_t const * orphlist = fd_forest_orphlist_const( forest );
338 :
339 114 : if( forest->orphiter.ele_idx != fd_forest_pool_idx_null( pool ) &&
340 114 : forest->orphiter.ele_idx != fd_forest_reqslist_ele_peek_head_const( orphlist, reqspool )->idx ) {
341 0 : FAIL( "orphan iterator is not at the head of the orphan request list" );
342 0 : }
343 :
344 159 : for( fd_forest_reqslist_iter_t iter = fd_forest_reqslist_iter_fwd_init( orphlist, reqspool ); !fd_forest_reqslist_iter_done( iter, orphlist, reqspool ); iter = fd_forest_reqslist_iter_fwd_next( iter, orphlist, reqspool ) ) {
345 45 : fd_forest_ref_t const * ele = fd_forest_reqslist_iter_ele_const( iter, orphlist, reqspool );
346 45 : fd_forest_blk_t const * ele_ = fd_forest_pool_ele_const( pool, ele->idx );
347 45 : if( !fd_forest_subtrees_ele_query_const( subtrees, &ele_->slot, NULL, pool ) && !fd_forest_orphaned_ele_query_const( orphaned, &ele_->slot, NULL, pool ) ) {
348 0 : FAIL( "element in orphan request list not in the subtrees or orphaned map" );
349 0 : }
350 45 : if( !fd_forest_requests_ele_query_const( orphreqs, &ele->idx, NULL, reqspool ) ) FAIL( "element in orphan request list not in the orphan request map" );
351 45 : if( fd_forest_requests_ele_query_const( requests, &ele->idx, NULL, reqspool ) ) FAIL( "element in both the main request map and the orphan request map" );
352 45 : }
353 :
354 : /* Tree structure invariants. Walk every element in every map and
355 : verify the left-child / right-sibling / parent links are mutually
356 : consistent, that slots strictly increase from parent to child, that
357 : there are no cycles, and that each element lives in the correct map
358 : for its position in the tree. */
359 :
360 114 : ulong null = fd_forest_pool_idx_null( pool );
361 114 : ulong max = fd_forest_pool_max( pool );
362 :
363 : /* Root must exist, be parentless, and live in ancestry or frontier. */
364 :
365 114 : if( FD_UNLIKELY( forest->root == null ) ) FAIL( "root is null" );
366 114 : {
367 114 : fd_forest_blk_t const * root = fd_forest_pool_ele_const( pool, forest->root );
368 114 : if( FD_UNLIKELY( root->parent != null ) ) FAIL( "root has a parent" );
369 114 : if( FD_UNLIKELY( !fd_forest_ancestry_ele_query_const( ancestry, &root->slot, NULL, pool ) &&
370 114 : !fd_forest_frontier_ele_query_const( frontier, &root->slot, NULL, pool ) ) ) {
371 0 : FAIL( "root not in ancestry or frontier" );
372 0 : }
373 114 : }
374 :
375 : /* Per-element parent/child/sibling link checks, applied to every
376 : element regardless of which map it lives in. */
377 :
378 672 : # define CHECK_TREE_ELE( ele ) do { \
379 672 : ulong ele_idx = fd_forest_pool_idx( pool, (ele) ); \
380 672 : if( (ele)->parent != null ) { \
381 513 : fd_forest_blk_t const * p = fd_forest_pool_ele_const( pool, (ele)->parent ); \
382 513 : if( FD_UNLIKELY( (ele)->parent_slot != p->slot ) ) FAIL( "parent_slot != parent ele slot" ); \
383 513 : if( FD_UNLIKELY( (ele)->slot <= p->slot ) ) FAIL( "child slot <= parent slot" ); \
384 513 : } \
385 672 : ulong steps = 0; \
386 672 : ulong child_idx = (ele)->child; \
387 1185 : while( child_idx != null ) { \
388 513 : if( FD_UNLIKELY( ++steps > max ) ) FAIL( "sibling chain longer than pool (cycle)" ); \
389 513 : fd_forest_blk_t const * c = fd_forest_pool_ele_const( pool, child_idx ); \
390 513 : if( FD_UNLIKELY( c->parent != ele_idx ) ) FAIL( "child->parent does not point back to ele" ); \
391 513 : if( FD_UNLIKELY( c->parent_slot != (ele)->slot ) ) FAIL( "child->parent_slot mismatch" ); \
392 513 : if( FD_UNLIKELY( c->slot <= (ele)->slot ) ) FAIL( "child slot <= parent slot" ); \
393 513 : child_idx = c->sibling; \
394 513 : } \
395 672 : } while(0)
396 :
397 : /* ancestry: connected interior nodes - must have at least one child,
398 : and may only be parentless if it is the root. */
399 :
400 516 : for( fd_forest_ancestry_iter_t iter = fd_forest_ancestry_iter_init( ancestry, pool ); !fd_forest_ancestry_iter_done( iter, ancestry, pool ); iter = fd_forest_ancestry_iter_next( iter, ancestry, pool ) ) {
401 402 : fd_forest_blk_t const * ele = fd_forest_ancestry_iter_ele_const( iter, ancestry, pool );
402 402 : CHECK_TREE_ELE( ele );
403 402 : if( FD_UNLIKELY( ele->child == null ) ) FAIL( "ancestry element has no child" );
404 402 : if( FD_UNLIKELY( ele->parent == null && fd_forest_pool_idx( pool, ele ) != forest->root ) ) FAIL( "ancestry element parentless but not root" );
405 402 : }
406 :
407 : /* frontier: tips of the connected tree - must be childless, and may
408 : only be parentless if it is the root. */
409 :
410 285 : 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 ) ) {
411 171 : fd_forest_blk_t const * ele = fd_forest_frontier_iter_ele_const( iter, frontier, pool );
412 171 : CHECK_TREE_ELE( ele );
413 171 : if( FD_UNLIKELY( ele->child != null ) ) FAIL( "frontier element has a child" );
414 171 : if( FD_UNLIKELY( ele->parent == null && fd_forest_pool_idx( pool, ele ) != forest->root ) ) FAIL( "frontier element parentless but not root" );
415 171 : }
416 :
417 : /* subtrees: heads of orphan trees - must be parentless. */
418 :
419 159 : 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 ) ) {
420 45 : fd_forest_blk_t const * ele = fd_forest_subtrees_iter_ele_const( iter, subtrees, pool );
421 45 : CHECK_TREE_ELE( ele );
422 45 : if( FD_UNLIKELY( ele->parent != null ) ) FAIL( "subtree head has a parent" );
423 45 : }
424 :
425 : /* orphaned: interior orphan nodes - must have a parent, and walking
426 : up the parent chain must terminate at a subtree head. */
427 :
428 168 : 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 ) ) {
429 54 : fd_forest_blk_t const * ele = fd_forest_orphaned_iter_ele_const( iter, orphaned, pool );
430 54 : CHECK_TREE_ELE( ele );
431 54 : if( FD_UNLIKELY( ele->parent == null ) ) FAIL( "orphaned element has no parent" );
432 54 : fd_forest_blk_t const * cur = ele;
433 54 : ulong steps = 0;
434 348 : while( cur->parent != null ) {
435 294 : if( FD_UNLIKELY( ++steps > max ) ) FAIL( "orphan parent chain longer than pool (cycle)" );
436 294 : cur = fd_forest_pool_ele_const( pool, cur->parent );
437 294 : }
438 54 : if( FD_UNLIKELY( !fd_forest_subtrees_ele_query_const( subtrees, &cur->slot, NULL, pool ) ) ) FAIL( "orphan tree head not in subtrees map" );
439 54 : }
440 :
441 114 : # undef CHECK_TREE_ELE
442 :
443 114 : return 0;
444 114 : }
445 : #undef FAIL
446 :
447 : /* {maps}_remove removes an ele from {maps}. does not unlink ele. */
448 :
449 : static fd_forest_blk_t *
450 156 : ancestry_frontier_remove( fd_forest_t * forest, ulong slot ) {
451 156 : fd_forest_blk_t * pool = fd_forest_pool( forest );
452 156 : fd_forest_blk_t * ele = NULL;
453 156 : ele = fd_forest_ancestry_ele_remove( fd_forest_ancestry( forest ), &slot, NULL, pool );
454 156 : ele = fd_ptr_if( !ele, fd_forest_frontier_ele_remove( fd_forest_frontier( forest ), &slot, NULL, pool ), ele );
455 156 : return ele;
456 156 : }
457 :
458 : static fd_forest_blk_t *
459 78 : subtrees_orphaned_remove( fd_forest_t * forest, ulong slot ) {
460 78 : fd_forest_blk_t * pool = fd_forest_pool( forest );
461 78 : fd_forest_blk_t * ele = NULL;
462 78 : ele = fd_forest_orphaned_ele_remove( fd_forest_orphaned( forest ), &slot, NULL, pool );
463 78 : if( ele ) return ele;
464 57 : ele = fd_forest_subtrees_ele_remove( fd_forest_subtrees( forest ), &slot, NULL, pool );
465 57 : if( ele ) fd_forest_subtlist_ele_remove( fd_forest_subtlist( forest ), ele, pool );
466 57 : return ele;
467 78 : }
468 :
469 : /* link ele to the tree via its sibling. */
470 :
471 : static void
472 69 : link_sibling( fd_forest_t * forest, fd_forest_blk_t * sibling, fd_forest_blk_t * ele ) {
473 69 : fd_forest_blk_t * pool = fd_forest_pool( forest );
474 69 : ulong null = fd_forest_pool_idx_null( pool );
475 87 : while( FD_UNLIKELY( sibling->sibling != null )) sibling = fd_forest_pool_ele( pool, sibling->sibling );
476 69 : sibling->sibling = fd_forest_pool_idx( pool, ele );
477 69 : }
478 :
479 : /* link child to the tree via its parent. */
480 :
481 : static void
482 12861 : link( fd_forest_t * forest, fd_forest_blk_t * parent, fd_forest_blk_t * child ) {
483 12861 : fd_forest_blk_t * pool = fd_forest_pool( forest );
484 12861 : ulong null = fd_forest_pool_idx_null( pool );
485 12861 : if( FD_LIKELY( parent->child == null ) ) parent->child = fd_forest_pool_idx( pool, child ); /* left-child */
486 69 : else link_sibling( forest, fd_forest_pool_ele( pool, parent->child ), child ); /* right-sibling */
487 12861 : child->parent = fd_forest_pool_idx( pool, parent );
488 12861 : }
489 :
490 : /* advance_consumed_frontier attempts to advance the consumed frontier beginning from slot
491 : using BFS. head is the first element of a linked list representing
492 : the BFS queue. A slot can be advanced if all shreds for the block
493 : are received ie. consumed_idx = complete_idx. */
494 :
495 : static void
496 153264 : advance_consumed_frontier( fd_forest_t * forest, ulong slot, ulong parent_slot ) {
497 153264 : fd_forest_blk_t * pool = fd_forest_pool( forest );
498 153264 : fd_forest_ref_t * conspool = fd_forest_conspool( forest );
499 153264 : fd_forest_consumed_t * consumed = fd_forest_consumed( forest );
500 153264 : ulong * queue = fd_forest_deque( forest );
501 :
502 153264 : ulong slot_pool_idx = fd_forest_pool_idx( pool, fd_forest_query( forest, slot ) );
503 153264 : ulong parent_pool_idx = fd_forest_pool_idx( pool, fd_forest_query( forest, parent_slot ) );
504 153264 : fd_forest_ref_t * ele;
505 153264 : ele = fd_forest_consumed_ele_query( consumed, &slot_pool_idx, NULL, conspool );
506 153264 : ele = fd_ptr_if( !ele, fd_forest_consumed_ele_query( consumed, &parent_pool_idx, NULL, conspool ), ele );
507 153264 : if( FD_UNLIKELY( !ele ) ) return;
508 :
509 104616 : FD_CHECK_CRIT( fd_forest_deque_cnt( queue ) == 0, "invariant violation" );
510 :
511 : /* BFS elements as pool idxs.
512 : Invariant: whatever is in the queue, must be in the consumed map. */
513 104616 : fd_forest_deque_push_tail( queue, ele->idx );
514 209589 : while( FD_LIKELY( fd_forest_deque_cnt( queue ) ) ) {
515 104973 : fd_forest_blk_t * head = fd_forest_pool_ele( pool, fd_forest_deque_pop_head( queue ) );
516 104973 : fd_forest_blk_t * child = fd_forest_pool_ele( pool, head->child );
517 :
518 104973 : int all_shreds_received = head->complete_idx != UINT_MAX && head->complete_idx == head->buffered_idx;
519 :
520 104973 : if( FD_LIKELY( child && all_shreds_received ) ) { /* we've received all the shreds for the slot - not all the FECs for the slot need to be completed */
521 351 : consumed_remove( forest, fd_forest_pool_idx( pool, head ) );
522 708 : while( FD_LIKELY( child ) ) { /* add children to consumed frontier */
523 357 : consumed_insert( forest, fd_forest_pool_idx( pool, child ) );
524 357 : fd_forest_deque_push_tail( queue, fd_forest_pool_idx( pool, child ) );
525 357 : child = fd_forest_pool_ele( pool, child->sibling );
526 357 : }
527 351 : }
528 104973 : }
529 104616 : }
530 :
531 : fd_forest_blk_t *
532 501468 : fd_forest_query( fd_forest_t * forest, ulong slot ) {
533 501468 : fd_forest_blk_t * pool = fd_forest_pool( forest );
534 501468 : fd_forest_ancestry_t * ancestry = fd_forest_ancestry( forest );
535 501468 : fd_forest_frontier_t * frontier = fd_forest_frontier( forest );
536 501468 : fd_forest_subtrees_t * subtrees = fd_forest_subtrees( forest );
537 501468 : fd_forest_orphaned_t * orphaned = fd_forest_orphaned( forest );
538 :
539 501468 : fd_forest_blk_t * ele = NULL;
540 501468 : ele = fd_forest_ancestry_ele_query( ancestry, &slot, NULL, pool );
541 501468 : ele = fd_ptr_if( !ele, fd_forest_frontier_ele_query( frontier, &slot, NULL, pool ), ele );
542 501468 : ele = fd_ptr_if( !ele, fd_forest_subtrees_ele_query( subtrees, &slot, NULL, pool ), ele );
543 501468 : ele = fd_ptr_if( !ele, fd_forest_orphaned_ele_query( orphaned, &slot, NULL, pool ), ele );
544 501468 : return ele;
545 501468 : }
546 :
547 : /* remove_and_unlink removes a block from the forest and unlinks it from
548 : its parent. Orphans all the descendants of the block. Also removes
549 : from sibling chain, consumed map, and requests map if needed. Does
550 : NOT release the block from the pool. */
551 : static void
552 10875 : remove_and_unlink( fd_forest_t * forest, fd_forest_blk_t * blk ) {
553 10875 : fd_forest_blk_t * pool = fd_forest_pool( forest );
554 10875 : fd_forest_orphaned_t * orphaned = fd_forest_orphaned( forest );
555 10875 : fd_forest_frontier_t * frontier = fd_forest_frontier( forest );
556 10875 : fd_forest_ancestry_t * ancestry = fd_forest_ancestry( forest );
557 10875 : fd_forest_consumed_t * consumed = fd_forest_consumed( forest );
558 10875 : fd_forest_ref_t * conspool = fd_forest_conspool( forest );
559 10875 : ulong null = fd_forest_pool_idx_null( pool );
560 :
561 : /* Clean up the parent, and remove block from the maps */
562 10875 : fd_forest_blk_t * parent = fd_forest_pool_ele( pool, blk->parent );
563 10875 : if( FD_UNLIKELY( !parent ) ) {
564 36 : subtrees_orphaned_remove( forest, blk->slot ); /* remove from subtrees and subtree list */
565 10839 : } else {
566 : /* remove the block from the parent's child list */
567 :
568 10839 : blk->parent = null;
569 10839 : fd_forest_blk_t * child = fd_forest_pool_ele( pool, parent->child );
570 10839 : if( FD_LIKELY( child->slot == blk->slot ) ) {
571 10830 : parent->child = child->sibling;
572 10830 : } else {
573 : /* go through the sibling list, and remove the block */
574 9 : fd_forest_blk_t * sibling = fd_forest_pool_ele( pool, child->sibling );
575 9 : fd_forest_blk_t * prev = child;
576 15 : while( FD_LIKELY( sibling ) ) {
577 15 : if( FD_LIKELY( sibling->slot == blk->slot ) ) {
578 9 : prev->sibling = sibling->sibling;
579 9 : break;
580 9 : }
581 6 : prev = sibling;
582 6 : sibling = fd_forest_pool_ele( pool, sibling->sibling );
583 6 : }
584 9 : }
585 10839 : blk->sibling = null;
586 :
587 : /* remove the block itself from the maps */
588 :
589 10839 : fd_forest_blk_t * removed = fd_forest_orphaned_ele_remove( orphaned, &blk->slot, NULL, pool );
590 10839 : if( !removed ) {
591 27 : removed = ancestry_frontier_remove( forest, blk->slot ); FD_TEST( removed );
592 :
593 : /* We removed from the main tree, so we possible need to insert parent into the frontier.
594 : Only need to add parent to the frontier if it doesn't have any other children. */
595 :
596 27 : if( parent->child == null ) {
597 18 : parent = fd_forest_ancestry_ele_remove( ancestry, &blk->parent_slot, NULL, pool );
598 18 : fd_forest_frontier_ele_insert( frontier, parent, pool );
599 : /* ensure parent is reachable from consumed frontier */
600 18 : ulong ancestor = fd_forest_pool_idx( pool, parent );
601 150 : while( FD_UNLIKELY( ancestor!=null &&
602 132 : !fd_forest_consumed_ele_query( consumed, &ancestor, NULL, conspool ) ) ) {
603 132 : ancestor = fd_forest_pool_ele( pool, ancestor )->parent;
604 132 : }
605 18 : if( FD_UNLIKELY( ancestor==null ) ) consumed_insert( forest, fd_forest_pool_idx( pool, parent ) );
606 18 : }
607 27 : }
608 10839 : }
609 :
610 : /* finally, release the block from reference maps */
611 10875 : consumed_remove( forest, fd_forest_pool_idx( pool, blk ) );
612 10875 : requests_remove( forest, fd_forest_orphreqs( forest ), fd_forest_orphlist( forest ), &forest->orphiter, fd_forest_pool_idx( pool, blk ) );
613 10875 : requests_remove( forest, fd_forest_requests( forest ), fd_forest_reqslist( forest ), &forest->iter, fd_forest_pool_idx( pool, blk ) );
614 :
615 : /* orphan/subtree all the descendants of ele, if there are any. In
616 : eviction case, this is no-op. */
617 10875 : ulong * queue = fd_forest_deque( forest );
618 10875 : fd_forest_deque_push_tail( queue, fd_forest_pool_idx( pool, blk ) );
619 :
620 21765 : while( FD_LIKELY( fd_forest_deque_cnt( queue ) ) ) {
621 10890 : fd_forest_blk_t * curr = fd_forest_pool_ele( pool, fd_forest_deque_pop_head( queue ) );
622 10890 : fd_forest_blk_t * child = fd_forest_pool_ele( pool, curr->child );
623 10905 : while( FD_LIKELY( child ) ) {
624 : /* remove all descendants from all structures */
625 15 : ancestry_frontier_remove( forest, child->slot );
626 15 : subtrees_orphaned_remove( forest, child->slot );
627 15 : consumed_remove( forest, fd_forest_pool_idx( pool, child ) );
628 15 : requests_remove( forest, fd_forest_requests( forest ), fd_forest_reqslist( forest ), &forest->iter, fd_forest_pool_idx( pool, child ) );
629 :
630 15 : fd_forest_deque_push_tail( queue, fd_forest_pool_idx( pool, child ) );
631 15 : child = fd_forest_pool_ele( pool, child->sibling );
632 15 : }
633 : /* this is the ele itself, do not reinsert */
634 10890 : if( FD_UNLIKELY( curr==blk ) ) continue;
635 :
636 15 : else if( FD_UNLIKELY( fd_forest_pool_ele( pool, curr->parent ) == blk ) ) { /* direct child of the ele, insert it into subtrees */
637 12 : curr->parent = fd_forest_pool_idx_null( pool );
638 12 : curr->sibling = fd_forest_pool_idx_null( pool );
639 12 : fd_forest_subtrees_ele_insert ( fd_forest_subtrees( forest ), curr, pool );
640 12 : fd_forest_subtlist_ele_push_tail( fd_forest_subtlist( forest ), curr, pool );
641 12 : requests_insert( forest, fd_forest_orphreqs( forest ), fd_forest_orphlist( forest ), fd_forest_pool_idx( pool, curr ) );
642 :
643 12 : } else { /* otherwise, not direct descendant of ele, insert it into orphaned */
644 3 : fd_forest_orphaned_ele_insert( orphaned, curr, pool );
645 3 : }
646 10890 : }
647 10875 : }
648 :
649 : static ulong
650 10857 : clear_leaf( fd_forest_t * forest, ulong slot ) {
651 10857 : fd_forest_blk_t * pool = fd_forest_pool( forest );
652 10857 : fd_forest_blk_t * blk = fd_forest_query( forest, slot );
653 10857 : FD_TEST( blk );
654 :
655 10857 : remove_and_unlink( forest, blk );
656 10857 : fd_forest_pool_ele_release( pool, blk );
657 :
658 10857 : return slot;
659 10857 : }
660 :
661 : /* returns latest confirmed leaf in the subtree rooted at root */
662 : static fd_forest_blk_t *
663 9 : latest_confirmed_slot( fd_forest_t * forest, ulong root_idx ) {
664 9 : ulong * queue = fd_forest_deque( forest );
665 9 : fd_forest_blk_t * latest_confirmed = NULL;
666 9 : fd_forest_blk_t * pool = fd_forest_pool( forest );
667 9 : fd_forest_deque_remove_all( queue );
668 9 : fd_forest_deque_push_tail( queue, root_idx );
669 :
670 : /* BFS through the tree. Since there can only be one confirmed fork,
671 : the last confirmed node we find must be the latest confirmed slot.
672 : We could be more effecient by limiting the search when we find a
673 : confirmed node, but left like this for now. */
674 :
675 1494 : while( FD_LIKELY( !fd_forest_deque_empty( queue ) ) ) {
676 1485 : fd_forest_blk_t * blk = fd_forest_pool_ele( pool, fd_forest_deque_pop_head( queue ) );
677 1485 : if( FD_LIKELY( blk->chain_confirmed || memcmp( &blk->confirmed_bid, &empty_mr, sizeof( fd_hash_t ) ) != 0 ) ) {
678 36 : latest_confirmed = blk;
679 36 : }
680 1485 : fd_forest_blk_t * child = fd_forest_pool_ele( pool, blk->child );
681 2961 : while( FD_LIKELY( child ) ) {
682 1476 : fd_forest_deque_push_tail( queue, fd_forest_pool_idx( pool, child ) );
683 1476 : child = fd_forest_pool_ele( pool, child->sibling );
684 1476 : }
685 1485 : }
686 9 : return latest_confirmed;
687 9 : }
688 :
689 : static fd_forest_blk_t *
690 6 : gca( fd_forest_t * forest, fd_forest_blk_t * blk1, fd_forest_blk_t * blk2 ) {
691 6 : fd_forest_blk_t * pool = fd_forest_pool( forest );
692 6 : fd_forest_blk_t * parent1 = blk1;
693 6 : fd_forest_blk_t * parent2 = blk2;
694 21 : while( FD_LIKELY( parent1 && parent2 ) ) {
695 21 : if( FD_LIKELY( parent1->slot == parent2->slot ) ) return parent1;
696 15 : if( parent1->slot > parent2->slot ) parent1 = fd_forest_pool_ele( pool, parent1->parent );
697 3 : else parent2 = fd_forest_pool_ele( pool, parent2->parent );
698 15 : }
699 0 : return NULL;
700 6 : }
701 :
702 : #define UPDATE_BEST_CANDIDATE( best_confrmd, best_unconfrmd, ele, filter ) \
703 5249079 : if( FD_UNLIKELY( filter ) ) continue; \
704 5249079 : do { \
705 23175 : int _confirmed = ele->chain_confirmed || !fd_hash_eq( &ele->confirmed_bid, &empty_mr ); \
706 23175 : if( FD_UNLIKELY( _confirmed ) ) { \
707 12324 : if( FD_LIKELY( !best_confrmd ) ) best_confrmd = ele; \
708 12324 : else best_confrmd = fd_ptr_if( best_confrmd->slot < ele->slot, ele, best_confrmd ); \
709 12324 : } else { \
710 10851 : if( FD_LIKELY( !best_unconfrmd ) ) best_unconfrmd = ele; \
711 10851 : else best_unconfrmd = fd_ptr_if( best_unconfrmd->slot < ele->slot, ele, best_unconfrmd ); \
712 10851 : } \
713 23175 : } while(0)
714 :
715 : /* fd_forest_evict is called when the forest has no more free elements,
716 : but we are trying to insert a new block.
717 : When this happens, forest begins evicting in the following order:
718 :
719 : 1. Orphaned, unconfirmed leaves
720 : 2. Connected, unconfirmed leaves
721 : 3. Orphaned, confirmed leaves
722 :
723 : We follow a general heuristic of evicting the leaf (youngest
724 : descendant) in each category first, with an exception. If the leaf is
725 : the parent of the slot we are adding, we pick a different leaf to
726 : evict. This is to avoid getting stuck in a cycle of creating an
727 : orphan that would immediately get evicted again by its parent getting
728 : requested.
729 :
730 : If we have confirmations we also avoid adding new slots that we are
731 : certain won't get confirmed.
732 :
733 : The likely most common case of eviction being called is when we have
734 : disconnected from the cluster for a while, or if we are catching up
735 : from far behind. In these cases, the distance from the last root to
736 : current turbine could be > slot max. But if we just blindly evict
737 : orphans at will, this could make the problem worse. Imagine slot_max =
738 : 1000, and we are 2000 slots behind.
739 :
740 : slot [unconnected] slot - slot - ... - slot
741 : 1 1001 1002 2000
742 :
743 : At this point if we receive slot 1000 -- this is a good case. Ideally
744 : we would evict slot 2000, and add slot 1000, and we make progress
745 : towards completing catchup. But if we receive slot 2002, and we evict
746 : slot 2000, then the next orphan request would give us 2001, 2000 again
747 : and again, and theoretically we never make progress towards completing
748 : catchup.
749 :
750 : It's unclear if we should evict orphans ONLY if the slot being added
751 : is closer to the root. It's possible that the new, later orphan is
752 : actually closer to the root than the older, earlier orphan, and those
753 : were just dud slots sent to us by an ancestor. In practice, the need
754 : repair orphan process is much faster than the turbine process, so for
755 : now we make the choice to optimistically keep orphans, and rely on the
756 : repair orphan process to quickly connect ancestry, faster than the
757 : future slots can come and evict it.
758 :
759 : WHAT IF WE HAVE NO ORPHANS.
760 :
761 : If we don't have orphans, we need to evict the newest unconfirmed
762 : leaf. I.e. start by trimming from the tip of the tree, but on
763 : a fork that is a minority.
764 :
765 : i.e best case:
766 :
767 : 1 ── 2 ── 4 ── 6 ── 7 ── 8 ...... ── 1000 <- 1001 would like to be added to the rree
768 : └── 3 ── 5
769 :
770 : If 1000 is confirmed, and 5 is not, we should evict 5 first, and then add 1001.
771 :
772 : 1 ── 2 ── 4 ── 6 ── 7 ── 8 ...... ── 1000 ── 1001 <- 1002 would like to be added to the rree
773 : └── 3
774 :
775 : Similarly, after 1002 arrives:
776 : 1 ── 2 ── 4 ── 6 ── 7 ── 8 ...... ── 1000 ── 1001 ── 1002 <- 1003 would like to be added to the rree
777 :
778 : Now we have one fork, with 1003 chaining to 1002. If 1002 is
779 : confirmed, then it's truly unfortunate... We (and most likely the
780 : cluster) hasn't rooted in max_live_slots! As long as 2 is also
781 : confirmed, then we are just going to optimistically publish forward to
782 : slot 2 and make it our new root. Note 2 MUST have undergone
783 : fec_chain_verify before it can be confirmed. If 2 is still not
784 : confirmed, we could still be in the process of evicting + repairing
785 : duplicates, so we must wait for 2 to be confirmed before we can
786 : publish forward.
787 :
788 : If 1002 is NOT confirmed, we cannot evict it and add 1003. This puts
789 : us under the case where we can't evict our parent. At this point we
790 : would rely on a confirmation to occur eventually that prunes state and
791 : frees up pool elements.
792 :
793 : This also works in the degenerate DoS case, where we have an extremely
794 : wide tree. Imagine someone someone with leader slots 1001 thru 1995 is
795 : doing the following attck:
796 :
797 : 1 ── 2 ── 3 ── 4 ── 5 ── <-- when we try to add 6, we run into eviction policy
798 : ├── 1001'
799 : ├── 1003'
800 : ...
801 : └── 1995'
802 : Even if the confirmation for 5 is lagging coming in (or it requires us
803 : to replay 6 to see it), we can follow a general policy of evicting the
804 : newest unconfirmed leaf. Newest implies furthest from the root. So we
805 : would evict 1995' first, and then add 6. */
806 :
807 :
808 : static ulong
809 10887 : evict( fd_forest_t * forest, ulong new_slot, ulong parent_slot ) {
810 : /* TODO If we've reached the point that we need to evict,
811 : should we stop using the orphan iterator to make requests? i.e.
812 : focus only on rebuilding ancestry. */
813 :
814 10887 : (void)new_slot;
815 10887 : fd_forest_frontier_t * frontier = fd_forest_frontier( forest );
816 10887 : fd_forest_subtlist_t * subtlist = fd_forest_subtlist( forest );
817 10887 : fd_forest_subtrees_t * subtrees = fd_forest_subtrees( forest );
818 10887 : fd_forest_orphaned_t * orphaned = fd_forest_orphaned( forest );
819 10887 : fd_forest_blk_t * pool = fd_forest_pool( forest );
820 :
821 : /* Generally, best policy for eviction is to evict in the order of:
822 : 1. Highest unconfirmed orphan leaf - furthest from root
823 : 2. Highest unconfirmed leaf in ancestry - furthest from tip of execution
824 : 3. Highest confirmed orphan leaf
825 : 4. Highest confirmed leaf in ancestry - at this point we would not evict this candidate.
826 :
827 : Since there can only be one confirmed fork, if we have more than
828 : one fork, then we should always be able to evict the unconfirmed
829 : slots with ease.
830 :
831 : There's some exceptions. We cannot evict slots that would be our
832 : parent, because this would create a loop of evictions. Or, if the
833 : slot we are adding is older than the rest of our orphans, we
834 : shouldn't add it. or maybe we should? FAAAAA currently we will. */
835 :
836 10887 : fd_forest_blk_t * unconfrmd_orphan = NULL; /* 1st best candidate for eviction is the highest unconfirmed orphan. */
837 10887 : fd_forest_blk_t * confirmed_orphan = NULL; /* 3rd best candidate for eviction is the highest confirmed orphan. */
838 10887 : for( fd_forest_subtlist_iter_t iter = fd_forest_subtlist_iter_fwd_init( subtlist, pool );
839 33999 : !fd_forest_subtlist_iter_done( iter, subtlist, pool );
840 23112 : iter = fd_forest_subtlist_iter_fwd_next( iter, subtlist, pool ) ) {
841 23112 : fd_forest_blk_t * ele = fd_forest_subtlist_iter_ele( iter, subtlist, pool );
842 23112 : UPDATE_BEST_CANDIDATE( confirmed_orphan, unconfrmd_orphan, ele, ele->child != ULONG_MAX || ele->slot == parent_slot );
843 1485 : }
844 10887 : for( fd_forest_orphaned_iter_t iter = fd_forest_orphaned_iter_init( orphaned, pool );
845 5225955 : !fd_forest_orphaned_iter_done( iter, orphaned, pool );
846 5215068 : iter = fd_forest_orphaned_iter_next( iter, orphaned, pool ) ) {
847 5215068 : fd_forest_blk_t * ele = fd_forest_orphaned_iter_ele( iter, orphaned, pool );
848 5215068 : UPDATE_BEST_CANDIDATE( confirmed_orphan, unconfrmd_orphan, ele, ele->child != ULONG_MAX || ele->slot == parent_slot );
849 10809 : }
850 :
851 10887 : fd_forest_blk_t * unconfrmd_leaf = NULL; /* 2nd best candidate for eviction is the highest unconfirmed leaf. */
852 10887 : fd_forest_blk_t * confirmed_leaf = NULL; /* 4th best candidate for eviction is the highest confirmed leaf. */
853 10887 : for( fd_forest_frontier_iter_t iter = fd_forest_frontier_iter_init( frontier, pool );
854 21786 : !fd_forest_frontier_iter_done( iter, frontier, pool );
855 10899 : iter = fd_forest_frontier_iter_next( iter, frontier, pool ) ) {
856 10899 : fd_forest_blk_t * ele = fd_forest_frontier_iter_ele( iter, frontier, pool );
857 10899 : UPDATE_BEST_CANDIDATE( confirmed_leaf, unconfrmd_leaf, ele, iter.ele_idx == forest->root || ele->slot == parent_slot );
858 10881 : }
859 :
860 10887 : if( FD_UNLIKELY( !unconfrmd_leaf && !confirmed_leaf && !unconfrmd_orphan && !confirmed_orphan ) ) {
861 : /* This can only happen 1 of two ways:
862 : 1. One fork in orphans, and root is alone (common situation in
863 : catchup). The new slot's parent is the tip of the orphan
864 : fork. Ignore the slot in this case.
865 : 2. One long fork, and the new slot's parent is the tip of the
866 : fork. Force a root in this case. */
867 3 : if( fd_forest_orphaned_ele_query( orphaned, &parent_slot, NULL, pool ) ) return ULONG_MAX;
868 :
869 3 : ulong new_root = fd_forest_pool_ele( pool, forest->root )->child;
870 3 : fd_forest_blk_t * new_root_ele = new_root==fd_forest_pool_idx_null( pool ) ? NULL : fd_forest_pool_ele( pool, new_root );
871 :
872 3 : if( FD_UNLIKELY( !new_root_ele || !new_root_ele->chain_confirmed ) ) return ULONG_MAX;
873 :
874 3 : FD_LOG_INFO(( "[%s] forest force rooting on slot %lu", __func__, new_root_ele->slot ));
875 3 : ulong evicted_slot = fd_forest_pool_ele( pool, forest->root )->slot;
876 3 : fd_forest_publish( forest, new_root_ele->slot );
877 3 : return evicted_slot;
878 3 : }
879 10884 : if( FD_UNLIKELY( unconfrmd_orphan )) {
880 10827 : return clear_leaf( forest, unconfrmd_orphan->slot );
881 10827 : }
882 57 : if( FD_UNLIKELY( unconfrmd_leaf )) {
883 18 : return clear_leaf( forest, unconfrmd_leaf->slot );
884 18 : }
885 39 : if( FD_UNLIKELY( confirmed_orphan )) {
886 15 : fd_forest_blk_t * parent = fd_forest_query( forest, parent_slot );
887 : /* Always accept a new orphan subtree root, as it could bring us
888 : closer to confirmation */
889 15 : if( !parent ) {
890 6 : return clear_leaf( forest, confirmed_orphan->slot );
891 6 : }
892 :
893 : /* While in general it's safe to evict a confirmed orphan, we don't
894 : want to evict them if this new slot is uselessly adding to a
895 : fork we KNOW isn't confirmed. i.e., if there is another fork in
896 : this subtree that isn't confirmed, but it's parent is parent_slot.
897 :
898 : Ex. We shouldn't evict a confirmed orphan leaf if the parent_slot
899 : is the other fork that is unconfirmed. Also can't evict a
900 : confirmed orphan if we are creating a new fork in the main tree
901 : that doesn't continue the singular confirmed fork.
902 :
903 : i.e. for any subtree:
904 :
905 : 0 ── 1 ── 2 ── 3 (confirmed) ── 4(confirmed) ── 5 ── 6 ──> add 7 here is valid.
906 : └──> add 7 here is valid.
907 : └──> add 7 here is invalid. */
908 9 : ulong subtree_root = forest->root;
909 9 : if( fd_forest_subtrees_ele_query( subtrees, &parent_slot, NULL, pool ) ||
910 9 : fd_forest_orphaned_ele_query( orphaned, &parent_slot, NULL, pool ) ) {
911 : /* if adding to an orphan, find the root of the orphan subtree. */
912 3 : fd_forest_blk_t * root = parent;
913 1446 : while( FD_LIKELY( root->parent != ULONG_MAX ) ) {
914 1443 : root = fd_forest_pool_ele( pool, root->parent );
915 1443 : }
916 3 : subtree_root = fd_forest_pool_idx( pool, root );
917 3 : }
918 :
919 9 : fd_forest_blk_t * latest_confirmed_leaf = latest_confirmed_slot( forest, subtree_root );
920 9 : if( !latest_confirmed_leaf || latest_confirmed_leaf == gca( forest, latest_confirmed_leaf, parent )) {
921 6 : return clear_leaf( forest, confirmed_orphan->slot ); /* is not a useless new fork. */
922 6 : }
923 : /* is a useless new fork. */
924 3 : return ULONG_MAX;
925 24 : } else {
926 : /* Should never be evicting a confirmed leaf. This is only non-NULL
927 : if:
928 : (1) we have no orphans, and theres only two forks in the main
929 : tree, and the parent of the non confirmed fork is is our parent.
930 : in this case we should just ignore this insert. TODO: optionally
931 : we could evict the non confirmed fork if its a separate fork.
932 : (2) we could have one orphan fork where parent_slot is at the
933 : tip, and everything in main tree is confirmed. in this case we
934 : should also ignore this insert. */
935 24 : return ULONG_MAX;
936 24 : }
937 39 : }
938 : #undef UPDATE_BEST_CANDIDATE
939 :
940 : static fd_forest_blk_t *
941 12969 : acquire( fd_forest_t * forest, ulong slot, ulong parent_slot, ulong * evicted ) {
942 12969 : fd_forest_blk_t * pool = fd_forest_pool( forest );
943 12969 : if( FD_UNLIKELY( !fd_forest_pool_free( pool ) ) ) {
944 10887 : ulong evicted_ = evict( forest, slot, parent_slot );
945 10887 : if( FD_LIKELY( evicted )) *evicted = evicted_;
946 10887 : if( FD_UNLIKELY( evicted_ == ULONG_MAX ) ) {
947 27 : return NULL;
948 27 : }
949 10887 : }
950 12942 : fd_forest_blk_t * blk = fd_forest_pool_ele_acquire( pool );
951 12942 : ulong null = fd_forest_pool_idx_null( pool );
952 :
953 12942 : blk->slot = slot;
954 12942 : blk->parent_slot = parent_slot;
955 12942 : blk->next = null;
956 12942 : blk->parent = null;
957 12942 : blk->child = null;
958 12942 : blk->sibling = null;
959 12942 : blk->chain_confirmed = 0;
960 :
961 12942 : blk->buffered_idx = UINT_MAX;
962 12942 : blk->complete_idx = UINT_MAX;
963 :
964 12942 : fd_forest_blk_idxs_null( blk->idxs );
965 12942 : blk->lowest_verified_fec = UINT_MAX;
966 12942 : memset( blk->merkle_roots, 0, sizeof( blk->merkle_roots ) ); /* expensive*/
967 12942 : blk->confirmed_bid = empty_mr;
968 :
969 12942 : blk->est_buffered_tick_recv = 0;
970 :
971 : /* Metrics tracking */
972 :
973 12942 : fd_forest_blk_idxs_null( blk->code );
974 12942 : blk->first_shred_ts = 0;
975 12942 : blk->first_req_ts = 0;
976 12942 : blk->turbine_cnt = 0;
977 12942 : blk->repair_cnt = 0;
978 12942 : blk->recovered_cnt = 0;
979 :
980 12942 : return blk;
981 12969 : }
982 :
983 : fd_forest_blk_t *
984 13092 : fd_forest_blk_insert( fd_forest_t * forest, ulong slot, ulong parent_slot, ulong * evicted ) {
985 13092 : FD_CHECK_CRIT( slot > fd_forest_root_slot( forest ), "invalid argument" );
986 :
987 13092 : fd_forest_ancestry_t * ancestry = fd_forest_ancestry( forest );
988 13092 : fd_forest_frontier_t * frontier = fd_forest_frontier( forest );
989 13092 : fd_forest_subtrees_t * subtrees = fd_forest_subtrees( forest );
990 13092 : fd_forest_subtlist_t * subtlist = fd_forest_subtlist( forest );
991 13092 : fd_forest_orphaned_t * orphaned = fd_forest_orphaned( forest );
992 13092 : fd_forest_consumed_t * consumed = fd_forest_consumed( forest );
993 13092 : fd_forest_ref_t * conspool = fd_forest_conspool( forest );
994 13092 : fd_forest_requests_t * requests = fd_forest_requests( forest );
995 13092 : fd_forest_ref_t * reqspool = fd_forest_reqspool( forest );
996 13092 : fd_forest_blk_t * pool = fd_forest_pool ( forest );
997 13092 : ulong * bfs = fd_forest_deque( forest );
998 13092 : ulong null = fd_forest_pool_idx_null( pool );
999 :
1000 13092 : fd_forest_blk_t * ele = fd_forest_query( forest, slot );
1001 13092 : if( FD_LIKELY( ele ) ) {
1002 : /* May need to update the parent_slot, if this
1003 : this was a sentinel block that was created for a confirmed msg.
1004 : A parent update for a sentinel block only occurs once. This
1005 : is separate from the parent update for a confirmed equivocating
1006 : block. */
1007 123 : if( FD_UNLIKELY( ele->parent_slot == ULONG_MAX && parent_slot != ULONG_MAX ) ) {
1008 6 : ele->parent_slot = parent_slot;
1009 6 : FD_TEST( fd_forest_subtrees_ele_query( subtrees, &slot, NULL, pool ) || fd_forest_orphaned_ele_query( orphaned, &slot, NULL, pool ) );
1010 6 : subtrees_orphaned_remove( forest, slot ); // if this is a sentinel block, then it must be orphaned
1011 : /* The sentinel was an orphan subtree head, so it is in the orphan
1012 : requests list. Now that its parent is known it will be re-linked
1013 : below and may join the main tree (frontier) or become an interior
1014 : orphan, neither of which belongs in the orphan requests list. Drop
1015 : the orphan request entry now; if it ends up a subtree head again the
1016 : subtrees branch below will re-add it. Failing to remove it here
1017 : leaves the same pool idx in both the orphan and main request maps
1018 : (which share a single reqspool), corrupting both lists. */
1019 6 : requests_remove( forest, fd_forest_orphreqs( forest ), fd_forest_orphlist( forest ), &forest->orphiter, fd_forest_pool_idx( pool, ele ) );
1020 117 : } else {
1021 117 : return ele;
1022 117 : }
1023 12969 : } else {
1024 12969 : ele = acquire( forest, slot, parent_slot, evicted );
1025 12969 : if( FD_UNLIKELY( !ele ) ) return NULL; /* no space in pool, so we can't add this slot */
1026 12969 : }
1027 :
1028 12948 : fd_forest_blk_t * parent = NULL;
1029 :
1030 12948 : if( FD_LIKELY ( parent = fd_forest_ancestry_ele_query ( ancestry, &parent_slot, NULL, pool ) ) ) { /* parent is in ancestry, ele makes new frontier */
1031 63 : fd_forest_frontier_ele_insert( frontier, ele, pool );
1032 12885 : } else if( FD_UNLIKELY( parent = fd_forest_frontier_ele_remove( frontier, &parent_slot, NULL, pool ) ) ) { /* parent is in frontier, ele makes new frontier */
1033 438 : fd_forest_ancestry_ele_insert( ancestry, parent, pool );
1034 438 : fd_forest_frontier_ele_insert( frontier, ele, pool );
1035 12447 : } else if( FD_UNLIKELY( parent = fd_forest_orphaned_ele_query ( orphaned, &parent_slot, NULL, pool ) ) ) { /* parent is in orphaned, ele makes new orphaned */
1036 12255 : fd_forest_orphaned_ele_insert( orphaned, ele, pool );
1037 12255 : } else if( FD_UNLIKELY( parent = fd_forest_subtrees_ele_query ( subtrees, &parent_slot, NULL, pool ) ) ) { /* parent is in subtrees, ele makes new orphaned */
1038 51 : fd_forest_orphaned_ele_insert( orphaned, ele, pool );
1039 141 : } else { /* parent is not in any map, ele makes new subtree */
1040 141 : fd_forest_subtrees_ele_insert( subtrees, ele, pool );
1041 141 : fd_forest_subtlist_ele_push_tail( fd_forest_subtlist( forest ), ele, pool );
1042 :
1043 141 : requests_insert( forest, fd_forest_orphreqs( forest ), fd_forest_orphlist( forest ), fd_forest_pool_idx( pool, ele ) );
1044 141 : }
1045 :
1046 12948 : if( FD_LIKELY( parent ) ) link( forest, parent, ele );
1047 :
1048 : /* Iterate subtrees and connect ones where the parent slot matches up
1049 : to the new ele.*/
1050 :
1051 12948 : for( fd_forest_subtlist_iter_t iter = fd_forest_subtlist_iter_fwd_init( subtlist, pool );
1052 37794 : !fd_forest_subtlist_iter_done( iter, subtlist, pool );
1053 24846 : iter = fd_forest_subtlist_iter_fwd_next( iter, subtlist, pool ) ) {
1054 24846 : fd_forest_blk_t * orphan = fd_forest_subtlist_iter_ele( iter, subtlist, pool );
1055 : // edge case where for a sentinel node the parent_slot == slot, so we want to avoid linking it to itself
1056 24846 : if( FD_LIKELY( orphan->slot != ele->slot ) ) fd_forest_deque_push_tail( bfs, fd_forest_pool_idx( pool, orphan ) );
1057 24846 : }
1058 37653 : while( FD_LIKELY( fd_forest_deque_cnt( bfs ) ) ) {
1059 24705 : fd_forest_blk_t * orphan = fd_forest_pool_ele( pool, fd_forest_deque_pop_head( bfs ) );
1060 24705 : if( FD_UNLIKELY( orphan->parent_slot == ele->slot ) ) {
1061 54 : link( forest, ele, orphan );
1062 54 : fd_forest_subtrees_ele_remove( subtrees, &orphan->slot, NULL, pool );
1063 54 : fd_forest_subtlist_ele_remove( fd_forest_subtlist( forest ), orphan, pool );
1064 54 : requests_remove( forest, fd_forest_orphreqs( forest ), fd_forest_orphlist( forest ), &forest->orphiter, fd_forest_pool_idx( pool, orphan ) );
1065 54 : fd_forest_orphaned_ele_insert( orphaned, orphan, pool );
1066 54 : }
1067 24705 : }
1068 :
1069 : /* At this point we are in the state where:
1070 :
1071 : ele < in frontier/subtrees/orphaned >
1072 : |
1073 : children < all in orphaned >
1074 :
1075 : if ele is in frontier, we need to extend the frontier from this child.
1076 : if ele is in orphaned/subtrees, we are done. don't do anything, */
1077 :
1078 12948 : 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 ) );
1079 13482 : while( FD_LIKELY( !fd_forest_deque_empty( bfs ) ) ) {
1080 534 : fd_forest_blk_t * parent = fd_forest_pool_ele( pool, fd_forest_deque_pop_head( bfs ) );
1081 534 : fd_forest_blk_t * child = fd_forest_pool_ele( pool, parent->child );
1082 534 : if( FD_LIKELY( child ) ) {
1083 30 : fd_forest_frontier_ele_remove( frontier, &parent->slot, NULL, pool );
1084 30 : fd_forest_ancestry_ele_insert( ancestry, parent, pool );
1085 30 : }
1086 567 : while( FD_LIKELY( child ) ) {
1087 33 : fd_forest_orphaned_ele_remove( orphaned, &child->slot, NULL, pool );
1088 33 : requests_remove( forest, fd_forest_orphreqs( forest ), fd_forest_orphlist( forest ), &forest->orphiter, fd_forest_pool_idx( pool, child ) );
1089 33 : fd_forest_frontier_ele_insert( frontier, child, pool );
1090 33 : fd_forest_deque_push_tail( bfs, fd_forest_pool_idx( pool, child ) );
1091 33 : child = fd_forest_pool_ele( pool, child->sibling );
1092 33 : }
1093 534 : }
1094 :
1095 12948 : if( FD_LIKELY( fd_forest_ancestry_ele_query( ancestry, &ele->slot, NULL, pool ) ||
1096 12948 : fd_forest_frontier_ele_query( frontier, &ele->slot, NULL, pool ) ) ) {
1097 : /* There is a chance that we connected this ele to the main tree. If
1098 : this ele doesn't have a parent in the consumed/requests map, add it to the
1099 : consumed/requests map. */
1100 501 : ulong ancestor = fd_forest_pool_idx( pool, ele );
1101 501 : int has_requests_anc = 0;
1102 501 : int has_consumed_anc = 0;
1103 3060 : while( ancestor != null && (!has_requests_anc || !has_consumed_anc) ) {
1104 2559 : if( fd_forest_consumed_ele_query( consumed, &ancestor, NULL, conspool ) ) has_consumed_anc = 1;
1105 2559 : if( fd_forest_requests_ele_query( requests, &ancestor, NULL, reqspool ) ) has_requests_anc = 1;
1106 2559 : ancestor = fd_forest_pool_ele( pool, ancestor )->parent;
1107 2559 : }
1108 501 : if( FD_UNLIKELY( !has_requests_anc ) ) {
1109 105 : requests_insert( forest, fd_forest_requests( forest ), fd_forest_reqslist( forest ), fd_forest_pool_idx( pool, ele ) );
1110 : /* we want to remove any children than are in the requests list. This isn't necessary during any regular boot.
1111 : However if we are booting from very far behind (>30k slots), the requests list will be very large and in
1112 : nearly reverse order. */
1113 105 : ulong * queue = fd_forest_deque( forest );
1114 105 : fd_forest_deque_push_tail( queue, fd_forest_pool_idx( pool, ele ) );
1115 222 : while( FD_LIKELY( fd_forest_deque_cnt( queue ) ) ) {
1116 117 : fd_forest_blk_t * child = fd_forest_pool_ele( pool, fd_forest_deque_pop_head( queue ) );
1117 117 : if( FD_LIKELY( child != ele ) ) {
1118 12 : requests_remove( forest, fd_forest_requests( forest ), fd_forest_reqslist( forest ), &forest->iter, fd_forest_pool_idx( pool, child ) );
1119 12 : }
1120 117 : child = fd_forest_pool_ele( pool, child->child );
1121 129 : while( FD_LIKELY( child ) ) {
1122 12 : fd_forest_deque_push_tail( queue, fd_forest_pool_idx( pool, child ) );
1123 12 : child = fd_forest_pool_ele( pool, child->sibling );
1124 12 : }
1125 117 : }
1126 105 : }
1127 501 : if( FD_UNLIKELY( !has_consumed_anc ) ) consumed_insert( forest, fd_forest_pool_idx( pool, ele ) );
1128 501 : }
1129 12948 : return ele;
1130 13092 : }
1131 :
1132 : /* Updates a forest_blk_t's parent, which requires updates to the blk
1133 : itself, the blk's old parent, the new parent, and all its
1134 : descendants. */
1135 : static fd_forest_blk_t *
1136 18 : verified_parent_update( fd_forest_t * forest, fd_forest_blk_t * ele, ulong parent_slot ) {
1137 18 : fd_forest_blk_t * pool = fd_forest_pool( forest );
1138 18 : fd_hash_t confirmed_bid = ele->confirmed_bid; /* save confirmation status for re-insertion */
1139 :
1140 : /* remove from maps, unlink from old parent. children orphaned. */
1141 18 : remove_and_unlink( forest, ele );
1142 :
1143 18 : ulong slot = ele->slot;
1144 18 : fd_forest_pool_ele_release( pool, ele );
1145 :
1146 : /* ele is now gone. blk_insert it! and then restore saved verified state */
1147 :
1148 18 : fd_forest_blk_t * new_ele = fd_forest_blk_insert( forest, slot, parent_slot, NULL );
1149 18 : new_ele->confirmed_bid = confirmed_bid;
1150 :
1151 18 : return new_ele;
1152 18 : }
1153 :
1154 : static inline int
1155 157947 : merkle_recvd( fd_forest_blk_t * ele, uint fec_idx ) {
1156 157947 : return memcmp( &ele->merkle_roots[fec_idx].mr, &empty_mr, sizeof(fd_hash_t) ) != 0;
1157 157947 : }
1158 :
1159 : /* returns 1 if the FEC set after the given FEC set has been confirmed */
1160 : static inline int
1161 158148 : next_merkle_confirmed( fd_forest_blk_t * ele, uint fec_idx ) {
1162 : // not possible for anything to be verified if the slot doesn't know the last index
1163 158148 : if( ele->complete_idx == UINT_MAX ) return 0;
1164 : /* if we are asking about the block_id, it's stored in the confirmed_bid field */
1165 453 : if( FD_UNLIKELY( fec_idx == (ele->complete_idx / 32UL) ) ) {
1166 249 : return !fd_hash_eq( &ele->confirmed_bid, &empty_mr );
1167 249 : }
1168 204 : return ele->lowest_verified_fec <= (fec_idx + 1UL);
1169 453 : }
1170 :
1171 : /* Returns the chained merkle root that commits to the given FEC set.
1172 : Only meaningful when next_merkle_confirmed() is true; otherwise the
1173 : returned cmr may be uninitialized. For most FEC sets this is
1174 : merkle_roots[fec_idx+1].cmr. For the last FEC in the slot (fec_idx
1175 : == complete_idx/32) it is confirmed_bid.
1176 :
1177 : Guard against OOB read: an attacker can send a fec_idx beyond
1178 : complete_idx. The shred gets filtered upstream, so we don't need to
1179 : guard against it here. */
1180 :
1181 : static inline fd_hash_t *
1182 207 : next_chained_merkle( fd_forest_blk_t * ele, uint fec_idx ) {
1183 207 : if( FD_UNLIKELY( fec_idx == ele->complete_idx / 32UL ) ) {
1184 105 : return &ele->confirmed_bid;
1185 105 : }
1186 102 : return &ele->merkle_roots[fec_idx + 1].cmr;
1187 207 : }
1188 :
1189 : /* data_shred_insert accepts the first complete_idx it sees while
1190 : complete_idx is UINT_MAX, and rejects any subsequent shreds that are
1191 : greater than the complete_idx. This is applies for the very first
1192 : slot_complete seen (could be incorrect), or after the complete_idx has
1193 : been cleared by fec_clear due to an incorrect FEC. */
1194 :
1195 : fd_forest_blk_t *
1196 : fd_forest_data_shred_insert( fd_forest_t * forest,
1197 : ulong slot,
1198 : ulong parent_slot,
1199 : uint shred_idx,
1200 : uint fec_set_idx,
1201 : int slot_complete,
1202 : int ref_tick,
1203 : int src,
1204 : fd_hash_t * mr,
1205 153246 : fd_hash_t * cmr ) {
1206 153246 : FD_TEST( shred_idx < FD_SHRED_BLK_MAX );
1207 153246 : fd_forest_blk_t * ele = fd_forest_query( forest, slot );
1208 153246 : FD_CHECK_ERR( !!ele, "ele is not in the forest. data_shred_insert should be preceded by blk_insert" );
1209 :
1210 : /* Pre-filtering on merkle root.
1211 : If we have knowledge of the confirmed merkle root, we can reject
1212 : shreds that don't match it. Else, we'll accept any and all shreds,
1213 : and invalidating the merkle root if we see more than 1 version of
1214 : the FEC. */
1215 :
1216 153246 : uint fec_idx = fec_set_idx / 32UL;
1217 :
1218 : /* If this is a slot_complete shred and we know the confirmed
1219 : block_id, we can immediately verify or reject. This check is
1220 : independent of the complete_idx / lowest_verified_fec state, so it
1221 : covers the case after fec_clear resets those fields. */
1222 :
1223 153246 : if( FD_UNLIKELY( slot_complete && !fd_hash_eq( &ele->confirmed_bid, &empty_mr ) ) ) {
1224 36 : if( FD_UNLIKELY( !fd_hash_eq( &ele->confirmed_bid, mr ) ) ) return NULL; /* wrong version */
1225 30 : if( FD_UNLIKELY( ele->parent_slot != parent_slot ) ) ele = verified_parent_update( forest, ele, parent_slot );
1226 30 : ele->lowest_verified_fec = fec_idx; /* last FEC verified */
1227 30 : ele->merkle_roots[fec_idx].mr = *mr;
1228 30 : ele->merkle_roots[fec_idx].cmr = *cmr;
1229 30 : }
1230 :
1231 : /* We can automatically reject if the shred index is greater than the
1232 : complete index, as it clearly signifies some duplicity is
1233 : occurring. What if this shred is part of the canonical chain
1234 : though? When the duplicate confirmation arrives from tower, the
1235 : false complete_idx will be cleared, and shreds higher than the
1236 : false complete_idx will be accepted. */
1237 :
1238 153240 : if( FD_UNLIKELY( shred_idx > ele->complete_idx ) ) {
1239 0 : FD_LOG_WARNING(( "[%s] slot %lu shred index %u is greater than known complete_idx %u. rejecting shred", __func__, slot, shred_idx, ele->complete_idx ));
1240 0 : return NULL;
1241 0 : }
1242 :
1243 : /* Otherwise if this is any other shred and we know the verification
1244 : status, we can immediately verify or reject. */
1245 :
1246 153240 : if( FD_UNLIKELY( next_merkle_confirmed( ele, fec_idx ) ) ) { /* if the cmr pointing to this FEC has been confirmed, then... */
1247 198 : if( FD_UNLIKELY( !fd_hash_eq( next_chained_merkle( ele, fec_idx ), mr ) ) ) {
1248 : /* merkle root doesn't match the verified CMR */
1249 3 : return NULL; /* do not accept this shred. */
1250 195 : } else {
1251 :
1252 : /* A validated mr, but the parent slot is wrong. This means we
1253 : initially received a the wrong version of the slot that also
1254 : had a different parent slot. We need to update the parent slot
1255 : to the correct one. We can _probably_ get away with not doing
1256 : this update (it wouldn't cause the validator to halt), but for
1257 : the sake of correctness, we'll do it. It is theoretically only
1258 : possible for the parent_slot update to happen once, after
1259 : the fec_chain_verify has identified an incorrect FEC. */
1260 :
1261 195 : if( FD_UNLIKELY( ele->parent_slot != parent_slot ) ) ele = verified_parent_update( forest, ele, parent_slot );
1262 195 : ele->merkle_roots[fec_idx].mr = *mr;
1263 195 : ele->merkle_roots[fec_idx].cmr = *cmr;
1264 :
1265 195 : }
1266 153042 : } else { /* No verification / knowledge of canonical merkle root */
1267 153042 : if( FD_UNLIKELY( !merkle_recvd( ele, fec_idx ) ) ) {
1268 5163 : ele->merkle_roots[fec_idx].mr = *mr;
1269 5163 : ele->merkle_roots[fec_idx].cmr = *cmr;
1270 147879 : } else {
1271 : /* verify that the received merkle root is consistent with the current merkle root.
1272 : No need to check the cmr, because matching mr implies matching cmr. */
1273 147879 : fd_hash_t * current_mr = &ele->merkle_roots[fec_idx].mr;
1274 147879 : if( FD_UNLIKELY( !fd_hash_eq( current_mr, mr ) ) ) {
1275 3 : FD_BASE58_ENCODE_32_BYTES( current_mr->key, current_mr_b58 ); FD_BASE58_ENCODE_32_BYTES( mr->key, mr_b58 );
1276 3 : FD_LOG_INFO(( "[%s] multiple versions detected for slot %lu fec set %u, invalidating. current_mr %s, received_mr %s", __func__, slot, fec_set_idx, current_mr_b58, mr_b58 ));
1277 3 : ele->merkle_roots[fec_idx].mr = invalid_mr; /* invalidate the merkle root */
1278 3 : }
1279 147879 : }
1280 153042 : }
1281 :
1282 : /* Shred accepted, merkle root verified (as much as possible). */
1283 :
1284 153237 : if( FD_UNLIKELY( slot_complete && ele->complete_idx != UINT_MAX && shred_idx != ele->complete_idx ) ) {
1285 : /* It is always beneficial for us to take the minimum slot complete
1286 : index because this enables the chain verification to start
1287 : earlier. */
1288 0 : FD_LOG_WARNING(( "[%s] slot %lu shred_idx %u is slot_complete, but recorded complete_idx is %u. Updating complete_idx to %u", __func__, slot, shred_idx, ele->complete_idx, shred_idx ));
1289 0 : }
1290 153237 : ele->complete_idx = fd_uint_if( slot_complete, shred_idx, ele->complete_idx );
1291 :
1292 153237 : if( !fd_forest_blk_idxs_test( ele->idxs, shred_idx ) ) { /* newly seen shred */
1293 152949 : ele->turbine_cnt += (src==SHRED_SRC_TURBINE);
1294 152949 : ele->repair_cnt += (src==SHRED_SRC_REPAIR);
1295 152949 : ele->recovered_cnt += (src==SHRED_SRC_RECOVERED);
1296 152949 : }
1297 153237 : if( FD_UNLIKELY( ele->first_shred_ts == 0 ) ) ele->first_shred_ts = fd_tickcount();
1298 :
1299 153237 : fd_forest_blk_idxs_insert( ele->idxs, shred_idx );
1300 306069 : while( ele->buffered_idx + 1 < FD_SHRED_BLK_MAX && fd_forest_blk_idxs_test( ele->idxs, ele->buffered_idx + 1U ) ) {
1301 152832 : ele->buffered_idx++;
1302 152832 : ele->est_buffered_tick_recv = ref_tick;
1303 : /* If the buffered_idx increases, this means the
1304 : est_buffered_tick_recv is at least ref_tick */
1305 152832 : }
1306 :
1307 : /* If equivocating, buffered_idx needs to be clamped to complete_idx */
1308 153237 : if( FD_UNLIKELY( ele->buffered_idx != UINT_MAX && ele->buffered_idx > ele->complete_idx ) ) ele->buffered_idx = ele->complete_idx;
1309 :
1310 153237 : advance_consumed_frontier( forest, slot, parent_slot );
1311 153237 : return ele;
1312 153240 : }
1313 :
1314 : fd_forest_blk_t *
1315 4914 : 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, fd_hash_t * mr, fd_hash_t * cmr ) {
1316 4914 : FD_TEST( last_shred_idx < FD_SHRED_BLK_MAX );
1317 :
1318 4914 : fd_forest_blk_t * ele = fd_forest_query( forest, slot );
1319 4914 : FD_CHECK_ERR( !!ele, "ele is not in the forest. fec_insert should be preceded by blk_insert" );
1320 :
1321 4914 : uint fec_idx = fec_set_idx / 32UL; /* index into merkle root array */
1322 :
1323 : /* if the FEC set is beyond the complete_idx, then we reject the FEC */
1324 4914 : if( FD_UNLIKELY( fec_set_idx > ele->complete_idx ) ) {
1325 6 : FD_LOG_WARNING(( "[%s] slot %lu fec set %u is greater than known complete_idx %u. rejecting FEC", __func__, slot, fec_set_idx, ele->complete_idx ));
1326 6 : return NULL;
1327 6 : }
1328 :
1329 : /* reject if the fec is confirmed and the merkle root doesn't match */
1330 4908 : if( FD_UNLIKELY( next_merkle_confirmed( ele, fec_idx ) && !fd_hash_eq( next_chained_merkle( ele, fec_idx ), mr ) ) ) return NULL;
1331 :
1332 4905 : if( FD_UNLIKELY( merkle_recvd( ele, fec_idx ) && !fd_hash_eq( &ele->merkle_roots[fec_idx].mr, mr ) ) ) {
1333 : /* overwrite the merkle root with the new one */
1334 6 : FD_BASE58_ENCODE_32_BYTES( ele->merkle_roots[fec_idx].mr.key, mr_b58 );
1335 6 : FD_BASE58_ENCODE_32_BYTES( mr->key, mr_recv_b58 );
1336 6 : FD_LOG_WARNING(( "[%s] received a version of slot %lu fec_set_idx %u that isn't recorded. current_mr %s, received_mr %s", __func__, slot, fec_set_idx, mr_b58, mr_recv_b58 ));
1337 : /* there are two cases:
1338 : (1) the first and common case is that we've received a mix of
1339 : shreds from equivocating FEC siblings A & B. In forest we have
1340 : recorded hash = { invalid_mr } for this fec set because we've
1341 : received a mix of merkle roots, so we nulled the FEC set. Let's
1342 : say fec_resolver then completes version B, and delivers it. We
1343 : can safely overwrite our null merkle root with B because we know
1344 : we must've received all the data for version B!
1345 :
1346 : (2) the second case is that we get two FEC completion msgs: one
1347 : for both version B and A. They get completed, one after the
1348 : other. We first overwrite from { invalid_mr } to B. But if
1349 : version A arrives, what should we do? If B is the correct
1350 : version, but we choose to overwrite the fec when A arrive, then
1351 : we need to ask shred to re-deliver the FEC set. Since we
1352 : don't know at this time if B or A is correct, we optimize for
1353 : case 1, and overwrite the merkle root with the new one. */
1354 6 : ele->merkle_roots[fec_idx].mr = *mr;
1355 6 : ele->merkle_roots[fec_idx].cmr = *cmr;
1356 6 : }
1357 :
1358 4905 : if( FD_UNLIKELY( slot_complete && ele->child != ULONG_MAX ) ) {
1359 : /* check for a child that is confirmed */
1360 57 : fd_forest_blk_t * child = fd_forest_pool_ele( fd_forest_pool( forest ), ele->child );
1361 117 : while( FD_UNLIKELY( child ) ) {
1362 66 : if( FD_UNLIKELY( child->chain_confirmed ) ) {
1363 6 : ele->confirmed_bid = child->merkle_roots[0].cmr;
1364 6 : break;
1365 6 : }
1366 60 : child = fd_forest_pool_ele( fd_forest_pool( forest ), child->sibling );
1367 60 : }
1368 57 : }
1369 :
1370 : /* It's important that we set the cmpl idx here. If this happens to be
1371 : the last fec_complete we needed to finish the slot, then we rely on
1372 : the advance_consumed_frontier call in the below data_shred_insert
1373 : to move forward the consumed frontier. */
1374 157566 : for( uint idx = fec_set_idx; idx <= last_shred_idx; idx++ ) {
1375 152661 : 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, mr, cmr );
1376 152661 : }
1377 4905 : return ele;
1378 4908 : }
1379 :
1380 : fd_forest_blk_t *
1381 0 : fd_forest_code_shred_insert( fd_forest_t * forest, ulong slot, uint shred_idx ) {
1382 0 : fd_forest_blk_t * ele = fd_forest_query( forest, slot );
1383 0 : if( FD_UNLIKELY( !ele ) ) {
1384 0 : return NULL;
1385 0 : }
1386 0 : if( FD_UNLIKELY( ele->first_shred_ts == 0 ) ) ele->first_shred_ts = fd_tickcount();
1387 :
1388 0 : if( FD_UNLIKELY( shred_idx >= fd_forest_blk_idxs_max( ele->code ) ) ) {
1389 0 : ele->turbine_cnt += 1;
1390 0 : return ele;
1391 0 : }
1392 :
1393 0 : if( FD_LIKELY( !fd_forest_blk_idxs_test( ele->code, shred_idx ) ) ) { /* newly seen shred */
1394 0 : ele->turbine_cnt += 1;
1395 0 : fd_forest_blk_idxs_insert( ele->code, shred_idx );
1396 0 : }
1397 0 : return ele;
1398 0 : }
1399 :
1400 : fd_forest_blk_t *
1401 75 : fd_forest_fec_chain_verify( fd_forest_t * forest, fd_forest_blk_t * ele, fd_hash_t const * bid ) {
1402 75 : uint fec_idx = ele->complete_idx / 32UL;
1403 :
1404 75 : ele->confirmed_bid = *bid; /* confirmed */
1405 75 : fd_hash_t const * expected_mr = bid;
1406 :
1407 270 : while( FD_UNLIKELY( !ele->chain_confirmed ) ) {
1408 237 : if( FD_UNLIKELY( fd_hash_eq( &ele->merkle_roots[fec_idx].mr, &empty_mr ) ) ) return NULL; /* can't verify the chain further */
1409 234 : if( FD_UNLIKELY( !fd_hash_eq( expected_mr, &ele->merkle_roots[fec_idx].mr ) ) ) return ele;
1410 :
1411 : /* This FEC merkle is correct, and the chained merkle is correct. */
1412 207 : ele->lowest_verified_fec = fec_idx;
1413 207 : expected_mr = &ele->merkle_roots[fec_idx].cmr;
1414 :
1415 207 : if( FD_UNLIKELY( fec_idx==0 ) ) {
1416 : /* hop to the parent slot, but first we've made it through this
1417 : slot successfully verifying the chain! mark it confirmed! */
1418 180 : ele->chain_confirmed = 1;
1419 180 : FD_LOG_DEBUG(( "[%s] confirmed full slot %lu", __func__, ele->slot ));
1420 180 : ele = fd_forest_pool_ele( fd_forest_pool( forest ), ele->parent );
1421 :
1422 180 : if( FD_UNLIKELY( !ele ) ) return NULL; /* can't verify the chain further */
1423 :
1424 168 : ele->confirmed_bid = *expected_mr; /* CMR of child slot */
1425 168 : if( FD_UNLIKELY( ele->complete_idx == UINT_MAX ) ) return NULL; /* can't verify the chain further */
1426 :
1427 168 : fec_idx = ele->complete_idx / 32UL;
1428 168 : continue;
1429 168 : }
1430 27 : fec_idx--; /* go back one FEC set */
1431 27 : }
1432 33 : return NULL;
1433 75 : }
1434 :
1435 : void
1436 27 : fd_forest_fec_clear( fd_forest_t * forest, ulong slot, uint fec_set_idx, uint max_shred_idx ) {
1437 27 : if( FD_UNLIKELY( slot <= fd_forest_root_slot( forest ) ) ) return;
1438 27 : fd_forest_blk_t * ele = fd_forest_query( forest, slot );
1439 27 : if( FD_UNLIKELY( !ele ) ) return;
1440 :
1441 849 : for( uint i=fec_set_idx; i<=fec_set_idx+max_shred_idx; i++ ) {
1442 822 : fd_forest_blk_idxs_remove( ele->idxs, i );
1443 822 : }
1444 :
1445 : /* clear complete_idx if we've cleared the last FEC in the slot */
1446 27 : if( FD_UNLIKELY( fec_set_idx+max_shred_idx == ele->complete_idx ) ) {
1447 21 : ele->complete_idx = UINT_MAX;
1448 21 : ele->lowest_verified_fec = UINT_MAX;
1449 21 : }
1450 :
1451 : /* There is a chance that the repair iterator is on this exact slot.
1452 : This means that this slot is in the requests list, and also at the
1453 : head of it. If we fec_clear on a range that is less than the
1454 : iterator's next_shred_idx, then the iterator will pop the slot as
1455 : "done" (next_shred_idx > complete_idx) without ever rerequesting
1456 : this fec. We must mark the slot incomplete so that the iterator can
1457 : re-request everything. Don't particularly care about the clear of
1458 : orphan slots as they are guaranteed to be iterated again. */
1459 :
1460 27 : if( FD_UNLIKELY( forest->iter.ele_idx == fd_forest_pool_idx( fd_forest_pool( forest ), ele ) ) ) {
1461 0 : forest->iter.shred_idx = UINT_MAX;
1462 0 : }
1463 :
1464 27 : if( FD_UNLIKELY( fec_set_idx == 0 ) ) ele->buffered_idx = UINT_MAX;
1465 9 : else ele->buffered_idx = fd_uint_if( ele->buffered_idx != UINT_MAX, fd_uint_min( ele->buffered_idx, fec_set_idx - 1 ), UINT_MAX );
1466 :
1467 27 : uint fec_idx = fec_set_idx / 32UL;
1468 27 : memset( &ele->merkle_roots[fec_idx].mr, 0, sizeof(fd_hash_t) );
1469 :
1470 : /* Add this slot back to requests map */
1471 27 : fd_forest_blk_t * pool = fd_forest_pool( forest );
1472 27 : fd_forest_ancestry_t * ancestry = fd_forest_ancestry( forest );
1473 27 : fd_forest_frontier_t * frontier = fd_forest_frontier( forest );
1474 27 : if( FD_LIKELY( fd_forest_ancestry_ele_query( ancestry, &ele->slot, NULL, pool ) ||
1475 27 : fd_forest_frontier_ele_query( frontier, &ele->slot, NULL, pool ) ) ) {
1476 18 : int has_requests_anc = 0;
1477 18 : ulong ancestor = fd_forest_pool_idx( pool, ele );
1478 33 : while( ancestor != fd_forest_pool_idx_null( pool ) && !has_requests_anc ) {
1479 33 : if( fd_forest_requests_ele_query( fd_forest_requests( forest ), &ancestor, NULL, fd_forest_reqspool( forest ) ) ) {
1480 18 : has_requests_anc = 1;
1481 18 : break;
1482 18 : }
1483 15 : ancestor = fd_forest_pool_ele( pool, ancestor )->parent;
1484 15 : }
1485 18 : if( FD_UNLIKELY( !has_requests_anc ) ) {
1486 0 : requests_insert( forest, fd_forest_requests( forest ), fd_forest_reqslist( forest ), fd_forest_pool_idx( pool, ele ) );
1487 :
1488 : /* remove any children than are in the requests list */
1489 0 : ulong * queue = fd_forest_deque( forest );
1490 0 : fd_forest_deque_push_tail( queue, fd_forest_pool_idx( pool, ele ) );
1491 0 : while( FD_LIKELY( fd_forest_deque_cnt( queue ) ) ) {
1492 0 : fd_forest_blk_t * child = fd_forest_pool_ele( pool, fd_forest_deque_pop_head( queue ) );
1493 0 : if( FD_LIKELY( child != ele ) ) requests_remove( forest, fd_forest_requests( forest ), fd_forest_reqslist( forest ), &forest->iter, fd_forest_pool_idx( pool, child ) );
1494 0 : child = fd_forest_pool_ele( pool, child->child );
1495 0 : while( FD_LIKELY( child ) ) {
1496 0 : fd_forest_deque_push_tail( queue, fd_forest_pool_idx( pool, child ) );
1497 0 : child = fd_forest_pool_ele( pool, child->sibling );
1498 0 : }
1499 0 : }
1500 0 : }
1501 : /* TODO we could update consumed, but it's not that necessary since
1502 : clearing a fec of a completed slot shouldn't really affect the
1503 : notion of when we completed the slot. consumed is also updated
1504 : mainly for metrics. For now we leave it alone. */
1505 18 : }
1506 27 : FD_LOG_INFO(( "[%s] cleared slot %lu fec set %u", __func__, slot, fec_set_idx ));
1507 27 : }
1508 :
1509 : fd_forest_blk_t const *
1510 39 : fd_forest_publish( fd_forest_t * forest, ulong new_root_slot ) {
1511 39 : fd_forest_ancestry_t * ancestry = fd_forest_ancestry( forest );
1512 39 : fd_forest_orphaned_t * orphaned = fd_forest_orphaned( forest );
1513 39 : fd_forest_frontier_t * frontier = fd_forest_frontier( forest );
1514 39 : fd_forest_subtrees_t * subtrees = fd_forest_subtrees( forest );
1515 39 : fd_forest_subtlist_t * subtlist = fd_forest_subtlist( forest );
1516 39 : fd_forest_ref_t * conspool = fd_forest_conspool( forest );
1517 39 : fd_forest_blk_t * pool = fd_forest_pool( forest );
1518 39 : ulong null = fd_forest_pool_idx_null( pool );
1519 39 : ulong * queue = fd_forest_deque( forest );
1520 :
1521 39 : fd_forest_blk_t * old_root_ele = fd_forest_pool_ele( pool, forest->root );
1522 39 : fd_forest_blk_t * new_root_ele = fd_forest_query( forest, new_root_slot );
1523 :
1524 : /* As an unfortunate side effect of maintaining forest slots in such
1525 : a fine-grained way, and also the possibility we can publish forwards
1526 : and backwards non-monotically, we have to consider every possible case of
1527 : what the new root could be.
1528 : 1. new root not in forest.
1529 : 2. new root in ancestry or frontier.
1530 : 3. new root in orphaned or subtrees. */
1531 :
1532 : /* 1. If we haven't been getting repairs, and we have a gap between
1533 : the root and orphans. we publish forward to a slot that we don't
1534 : have. In that case this isn't a bug, but we should be treating
1535 : this new root like the snapshot slot / init root. TODO: possible
1536 : could be publishing backwards to a slot that we don't have. */
1537 :
1538 39 : if( FD_UNLIKELY( !new_root_ele ) ) {
1539 : /* TODO remove this codepath, we should never be publishing to a slot that we don't have any more */
1540 6 : new_root_ele = fd_forest_blk_insert( forest, new_root_slot, old_root_ele->slot, NULL ); /* ensures new root is inserted as a frontier element */
1541 6 : new_root_ele->complete_idx = 0;
1542 6 : new_root_ele->buffered_idx = 0;
1543 6 : requests_insert( forest, fd_forest_requests( forest ), fd_forest_reqslist( forest ), fd_forest_pool_idx( pool, new_root_ele ) );
1544 6 : advance_consumed_frontier( forest, new_root_slot, 0 ); /* advances consumed frontier if possible */
1545 6 : }
1546 :
1547 : /* First, remove the previous root, and add it to a FIFO prune queue.
1548 : head points to the queue head (initialized with old_root_ele). */
1549 39 : FD_CHECK_CRIT( fd_forest_deque_cnt( queue ) == 0, "invariant violation" );
1550 :
1551 : /* 2. New root is in forest, and is either in ancestry or frontier
1552 : (means it is part of the main repair tree). This is the common
1553 : case. */
1554 :
1555 39 : fd_forest_blk_t * head = ancestry_frontier_remove( forest, old_root_ele->slot );
1556 39 : if( FD_LIKELY( head ) ) fd_forest_deque_push_tail( queue, fd_forest_pool_idx( pool, head ) );
1557 :
1558 : /* BFS down the tree, inserting each ele into the prune queue except
1559 : for the new root. Loop invariant: head always descends from
1560 : old_root_ele and never descends from new_root_ele. */
1561 :
1562 153 : while( FD_LIKELY( fd_forest_deque_cnt( queue ) ) ) {
1563 114 : head = fd_forest_pool_ele( pool, fd_forest_deque_pop_head( queue ) );
1564 114 : fd_forest_blk_t * child = fd_forest_pool_ele( pool, head->child );
1565 222 : while( FD_LIKELY( child ) ) {
1566 108 : if( FD_LIKELY( child != new_root_ele ) ) { /* do not prune new root or descendants */
1567 75 : child = ancestry_frontier_remove( forest, child->slot );
1568 75 : fd_forest_deque_push_tail( queue, fd_forest_pool_idx( pool, child ) );
1569 75 : }
1570 108 : child = fd_forest_pool_ele( pool, child->sibling );
1571 108 : }
1572 :
1573 114 : consumed_remove( forest, fd_forest_pool_idx( pool, head ) );
1574 114 : requests_remove( forest, fd_forest_requests( forest ), fd_forest_reqslist( forest ), &forest->iter, fd_forest_pool_idx( pool, head ) );
1575 114 : fd_forest_pool_ele_release( pool, head );
1576 114 : }
1577 :
1578 39 : new_root_ele->parent = null; /* unlink new root from parent */
1579 39 : new_root_ele->chain_confirmed = 1;
1580 39 : forest->root = fd_forest_pool_idx( pool, new_root_ele );
1581 :
1582 : /* 3. New root is in orphaned. This is the case where maybe the
1583 : expected snapshot slot has jumped far ahead. Invariants tell
1584 : us that the entire ancestry and frontier must have been pruned
1585 : above, so the consumed list and requests list must be empty.*/
1586 :
1587 39 : int new_root_is_orphan = fd_forest_subtrees_ele_query( subtrees, &new_root_ele->slot, NULL, pool ) ||
1588 39 : fd_forest_orphaned_ele_query( orphaned, &new_root_ele->slot, NULL, pool );
1589 :
1590 39 : if( FD_UNLIKELY( new_root_is_orphan ) ) {
1591 :
1592 : /* Extend the frontier from the new root */
1593 :
1594 6 : fd_forest_deque_push_tail( queue, fd_forest_pool_idx( pool, new_root_ele ) );
1595 18 : while( FD_LIKELY( fd_forest_deque_cnt( queue ) ) ) {
1596 12 : head = fd_forest_pool_ele( pool, fd_forest_deque_pop_head( queue ) );
1597 12 : subtrees_orphaned_remove( forest, head->slot );
1598 :
1599 12 : fd_forest_blk_t * child = fd_forest_pool_ele( pool, head->child );
1600 12 : if( FD_LIKELY( child ) ) fd_forest_ancestry_ele_insert( ancestry, head, pool );
1601 6 : else fd_forest_frontier_ele_insert( frontier, head, pool );
1602 18 : while( child ) {
1603 6 : fd_forest_deque_push_tail( queue, fd_forest_pool_idx( pool, child ) );
1604 6 : child = fd_forest_pool_ele( pool, child->sibling );
1605 6 : }
1606 12 : requests_remove( forest, fd_forest_orphreqs( forest ), fd_forest_orphlist( forest ), &forest->orphiter, fd_forest_pool_idx( pool, head ) );
1607 12 : }
1608 6 : }
1609 :
1610 : /* If there is nothing on the consumed, like in the case where we
1611 : publish to an orphan, or during catchup where all of our repair
1612 : consumed frontiers were < the new root. In that case we need to
1613 : continue repairing from the new root, so add it to the consumed
1614 : map. */
1615 :
1616 39 : if( FD_UNLIKELY( fd_forest_conslist_is_empty( fd_forest_conslist( forest ), conspool ) ) ) {
1617 21 : consumed_insert( forest, fd_forest_pool_idx( pool, new_root_ele ) );
1618 21 : requests_insert( forest, fd_forest_requests( forest ), fd_forest_reqslist( forest ), fd_forest_pool_idx( pool, new_root_ele ) );
1619 : /* TODO: is there a chance when we actually need to repair the root
1620 : after snapshot expected slot goes in? in this case this is
1621 : invalid */
1622 21 : new_root_ele->complete_idx = 0;
1623 21 : new_root_ele->buffered_idx = 0;
1624 21 : advance_consumed_frontier( forest, new_root_ele->slot, 0 );
1625 21 : }
1626 :
1627 : /* Lastly, cleanup orphans if there orphan heads < new_root_slot.
1628 : First, add any relevant orphans to the prune queue. */
1629 :
1630 39 : for( fd_forest_subtlist_iter_t iter = fd_forest_subtlist_iter_fwd_init( subtlist, pool );
1631 57 : !fd_forest_subtlist_iter_done( iter, subtlist, pool );
1632 39 : iter = fd_forest_subtlist_iter_fwd_next( iter, subtlist, pool ) ) {
1633 18 : fd_forest_blk_t * ele = fd_forest_subtlist_iter_ele( iter, subtlist, pool );
1634 18 : if( FD_UNLIKELY( ele->slot < new_root_slot ) ) {
1635 9 : fd_forest_deque_push_tail( queue, fd_forest_pool_idx( pool, ele ) );
1636 9 : }
1637 18 : }
1638 :
1639 : /* Now BFS and clean up children of these orphan heads */
1640 48 : while( FD_UNLIKELY( fd_forest_deque_cnt( queue ) ) ) {
1641 9 : head = fd_forest_pool_ele( pool, fd_forest_deque_pop_head( queue ) );
1642 9 : fd_forest_blk_t * child = fd_forest_pool_ele( pool, head->child );
1643 15 : while( FD_LIKELY( child ) ) {
1644 6 : if( FD_LIKELY( child != new_root_ele ) ) {
1645 0 : fd_forest_deque_push_tail( queue, fd_forest_pool_idx( pool, child ) );
1646 0 : }
1647 6 : child = fd_forest_pool_ele( pool, child->sibling );
1648 6 : }
1649 9 : subtrees_orphaned_remove( forest, head->slot );
1650 : /* Remove from orphan requests if present */
1651 9 : requests_remove( forest, fd_forest_orphreqs( forest ), fd_forest_orphlist( forest ), &forest->orphiter, fd_forest_pool_idx( pool, head ) );
1652 9 : fd_forest_pool_ele_release( pool, head ); /* free head */
1653 9 : }
1654 :
1655 39 : new_root_ele->sibling = null; /* unlink new root from siblings, just in case */
1656 39 : return new_root_ele;
1657 39 : }
1658 :
1659 :
1660 : ulong
1661 0 : fd_forest_highest_repaired_slot( fd_forest_t const * forest ) {
1662 0 : fd_forest_blk_t const * pool = fd_forest_pool_const( forest );
1663 0 : fd_forest_blk_t const * root = fd_forest_pool_ele_const( pool, forest->root );
1664 0 : fd_forest_conslist_t const * conslist = fd_forest_conslist_const( forest );
1665 0 : fd_forest_ref_t const * conspool = fd_forest_conspool_const( forest );
1666 :
1667 0 : if( FD_UNLIKELY( !root ) ) return 0;
1668 :
1669 0 : ulong max_repaired_slot = root->slot;
1670 0 : for( fd_forest_conslist_iter_t iter = fd_forest_conslist_iter_fwd_init( conslist, conspool );
1671 0 : !fd_forest_conslist_iter_done( iter, conslist, conspool );
1672 0 : iter = fd_forest_conslist_iter_fwd_next( iter, conslist, conspool ) ) {
1673 0 : fd_forest_ref_t const * ele = fd_forest_conslist_iter_ele_const( iter, conslist, conspool );
1674 0 : fd_forest_blk_t const * ele_ = fd_forest_pool_ele_const( pool, ele->idx );
1675 0 : if( FD_LIKELY( ele_->slot > max_repaired_slot ) ) max_repaired_slot = ele_->slot;
1676 0 : }
1677 0 : return max_repaired_slot;
1678 0 : }
1679 :
1680 :
1681 : fd_forest_t *
1682 0 : fd_forest_clear( fd_forest_t * forest ) {
1683 0 : return forest;
1684 0 : }
1685 :
1686 : fd_forest_iter_t *
1687 273 : fd_forest_iter_next( fd_forest_iter_t * iter, fd_forest_t * forest ) {
1688 273 : fd_forest_blk_t const * pool = fd_forest_pool_const( forest );
1689 273 : fd_forest_blk_t const * ele = fd_forest_pool_ele_const( pool, iter->ele_idx );
1690 273 : fd_forest_reqslist_t * reqslist = iter->list_gaddr == forest->reqslist_gaddr ? fd_forest_reqslist( forest ) : fd_forest_orphlist( forest );
1691 273 : fd_forest_requests_t * reqsmap = iter->list_gaddr == forest->reqslist_gaddr ? fd_forest_requests( forest ) : fd_forest_orphreqs( forest );
1692 273 : fd_forest_ref_t * reqspool = fd_forest_reqspool( forest );
1693 :
1694 : /* forest->iter.ele_idx should always refer to the head of the
1695 : requests list, unless iter.ele_idx is null (initializing)*/
1696 273 : if( FD_UNLIKELY( iter->ele_idx != fd_forest_pool_idx_null( pool ) &&
1697 273 : iter->ele_idx != fd_forest_reqslist_ele_peek_head( reqslist, reqspool )->idx ) ) {
1698 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));
1699 : /* check if the iterator ele_idx lives in the forest for debugging. */
1700 0 : fd_forest_blk_t const * ele_iter = fd_forest_pool_ele_const( pool, iter->ele_idx );
1701 0 : fd_forest_blk_t const * req_head = fd_forest_pool_ele_const( pool, fd_forest_reqslist_ele_peek_head( reqslist, reqspool )->idx );
1702 0 : ulong slot_iter = ele_iter ? ele_iter->slot : 0;
1703 0 : ulong slot_req_head = req_head ? req_head->slot : 0;
1704 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, slot_iter, (void *)fd_forest_query( forest, slot_iter ), req_head->slot, (void *)fd_forest_query( forest, slot_req_head ) ));
1705 0 : }
1706 :
1707 273 : uint next_shred_idx = iter->shred_idx;
1708 315 : for(;;) {
1709 315 : next_shred_idx++;
1710 :
1711 : /* Case 1: No more shreds in this slot to request, move to the
1712 : next one. Wraparound the shred_idx.
1713 :
1714 : Case 2: original iter.shred_idx == UINT_MAX (implies prev req
1715 : was a highest_window_idx request). Also requires moving to next
1716 : slot and wrapping the shred_idx. */
1717 :
1718 315 : if( FD_UNLIKELY( !ele || next_shred_idx > ele->complete_idx || iter->shred_idx == UINT_MAX ) ) {
1719 :
1720 : /* done requesting this slot. peek the next slot from requests
1721 : deque. But first, add this slot's children to the requests
1722 : deque! Debatable: should we add this slot's children to
1723 : the requests deque until we have actually sent reqs for every
1724 : shred of the slot? */
1725 :
1726 141 : if( FD_LIKELY( ele ) ) {
1727 111 : fd_forest_blk_t const * child = fd_forest_pool_ele_const( pool, ele->child );
1728 177 : while( FD_LIKELY( child ) ) {
1729 66 : requests_insert( forest, reqsmap, reqslist, fd_forest_pool_idx( pool, child ) );
1730 66 : child = fd_forest_pool_ele_const( pool, child->sibling );
1731 66 : }
1732 : /* so annoying. cant call requests_remove because itll invalidate the current iter->ele_idx,
1733 : so we explicitly pop the head and free the ele here. */
1734 111 : fd_forest_ref_t * head = fd_forest_reqslist_ele_pop_head( reqslist, reqspool );
1735 111 : fd_forest_requests_ele_remove ( reqsmap, &head->idx, NULL, reqspool );
1736 111 : fd_forest_reqspool_ele_release( reqspool, head );
1737 :
1738 111 : if( FD_UNLIKELY( iter->shred_idx == UINT_MAX && ( ele->buffered_idx == UINT_MAX || ele->buffered_idx < ele->complete_idx ) ) ) {
1739 : /* If we just made a highest_window_idx request, add this slot
1740 : back to the requests deque at the end. Also condition on
1741 : whether or not this slot is still incomplete. If the slot
1742 : is complete and we add it back to the loop, we will end up
1743 : infinite looping. */
1744 69 : requests_insert( forest, reqsmap, reqslist, iter->ele_idx );
1745 69 : }
1746 111 : }
1747 :
1748 : /* Move onto the next slot */
1749 141 : if( FD_UNLIKELY( fd_forest_reqslist_is_empty( reqslist, reqspool ) ) ) {
1750 6 : iter->ele_idx = fd_forest_pool_idx_null( pool );
1751 6 : iter->shred_idx = UINT_MAX;
1752 6 : return iter;
1753 6 : }
1754 :
1755 135 : iter->ele_idx = fd_forest_reqslist_ele_peek_head( reqslist, reqspool )->idx;
1756 135 : ele = fd_forest_pool_ele_const( pool, iter->ele_idx );
1757 :
1758 135 : if( FD_UNLIKELY( !fd_forest_query( forest, ele->slot ) ) ) {
1759 : /* TODO: should never meet this condition if the iterator
1760 : invariants are maintained. Can consider changing back to
1761 : LOG_CRIT after dynamic expected snapshot slot changes go in,
1762 : or removing this check entirely. */
1763 0 : FD_LOG_WARNING(( "[%s] slot %lu not found in forest. purging from requests list.", __func__, ele->slot ));
1764 0 : requests_remove( forest, reqsmap, reqslist, iter, iter->ele_idx );
1765 0 : return iter;
1766 0 : }
1767 135 : next_shred_idx = ele->buffered_idx + 1;
1768 135 : }
1769 :
1770 : /* Common case - valid shred to request. Note you can't know the
1771 : ele->complete_idx until you have actually received the slot
1772 : complete shred, but the last shred may have been evicted, so we
1773 : need leq. */
1774 :
1775 309 : if( ele->complete_idx != UINT_MAX &&
1776 309 : next_shred_idx <= ele->complete_idx &&
1777 309 : !fd_forest_blk_idxs_test( ele->idxs, next_shred_idx ) ) {
1778 192 : iter->shred_idx = next_shred_idx;
1779 192 : break;
1780 192 : }
1781 :
1782 : /* Current slot actually needs a highest_window_idx request */
1783 :
1784 117 : if( FD_UNLIKELY( ele->complete_idx == UINT_MAX ) ) {
1785 75 : iter->shred_idx = UINT_MAX;
1786 75 : break;
1787 75 : }
1788 117 : }
1789 267 : return iter;
1790 273 : }
1791 :
1792 : int
1793 0 : fd_forest_iter_done( fd_forest_iter_t * iter, fd_forest_t * forest ) {
1794 0 : fd_forest_blk_t const * pool = fd_forest_pool_const( forest );
1795 0 : return iter->ele_idx == fd_forest_pool_idx_null( pool ); /* no more elements */
1796 0 : }
1797 :
1798 : #include <stdio.h>
1799 :
1800 : #define FD_FOREST_ORPHANED_PRINT_MAX_DEPTH 500UL
1801 :
1802 : static void
1803 : orphaned_print( fd_forest_t const * forest,
1804 : fd_forest_blk_t const * ele,
1805 : fd_forest_blk_t const * prev,
1806 : ulong last_printed,
1807 : int depth,
1808 : const char * prefix,
1809 1530 : ulong print_depth ) {
1810 :
1811 1530 : if( FD_UNLIKELY( ele == NULL ) ) return;
1812 :
1813 : /* Prevent stack overflow from excessive recursion */
1814 1530 : if( FD_UNLIKELY( print_depth >= FD_FOREST_ORPHANED_PRINT_MAX_DEPTH ) ) {
1815 0 : printf( "... (truncated: too many orphaned nodes, max depth %lu reached)\n", FD_FOREST_ORPHANED_PRINT_MAX_DEPTH );
1816 0 : return;
1817 0 : }
1818 :
1819 1530 : fd_forest_blk_t const * pool = fd_forest_pool_const( forest );
1820 1530 : int digits = (int)fd_ulong_base10_dig_cnt( ele->slot );
1821 :
1822 : /* If there is a prefix, this means we are on a fork, and we need to
1823 : indent to the correct depth. We do depth - 1 for more satisfying
1824 : spacing. */
1825 1530 : if( FD_UNLIKELY( strcmp( prefix, "" ) ) ) {
1826 0 : for( int i = 0; i < depth - 1; i++ ) printf( " " );
1827 0 : if( depth > 0 ) printf( "%s", prefix );
1828 0 : }
1829 :
1830 1530 : if ( FD_UNLIKELY( !prev ) ) { // New interval
1831 33 : printf("[%lu" , ele->slot );
1832 33 : last_printed = ele->slot;
1833 33 : depth += 1 + digits;
1834 33 : }
1835 :
1836 1530 : fd_forest_blk_t const * curr = fd_forest_pool_ele_const( pool, ele->child );
1837 :
1838 : /* Cases in which we close the interval:
1839 : 1. the slots are no longer consecutive. no eliding, close bracket
1840 : 2. current ele has multiple children, want to print forks.
1841 : Maintain last_printed on this fork so that we don't print [a, a]
1842 : intervals. */
1843 :
1844 1530 : fd_forest_blk_t const * new_prev = ele;
1845 :
1846 1530 : if( prev && prev->slot != ele->slot - 1 ) { // non-consecutive, do not elide
1847 3 : if( last_printed == prev->slot ){
1848 3 : printf( "] ── [%lu", ele->slot );
1849 3 : depth += digits + 6;
1850 3 : } else {
1851 0 : printf( ", %lu] ── [%lu", prev->slot, ele->slot );
1852 0 : depth += digits + (int)fd_ulong_base10_dig_cnt( prev->slot ) + 8;
1853 0 : }
1854 3 : last_printed = ele->slot;
1855 1527 : } else if( curr && curr->sibling != ULONG_MAX ) { // has multiple children, do not elide
1856 0 : if( last_printed == ele->slot ){
1857 0 : printf( "] ── " );
1858 0 : depth += 5;
1859 0 : } else {
1860 0 : printf( ", %lu] ── ", ele->slot );
1861 0 : depth += digits + 2;
1862 0 : }
1863 0 : last_printed = ele->slot;
1864 0 : new_prev = NULL;
1865 0 : }
1866 :
1867 1530 : if( !curr ){ // no children, close bracket, end fork
1868 33 : if( last_printed == ele->slot ){
1869 12 : printf( "]\n" );
1870 21 : } else {
1871 21 : printf( ", %lu]\n", ele->slot );
1872 21 : }
1873 33 : return;
1874 33 : }
1875 :
1876 1497 : char new_prefix[32];
1877 1497 : new_prefix[0] = '\0'; /* first fork stays on the same line, no prefix */
1878 2994 : while( curr ) {
1879 1497 : orphaned_print( forest, curr, new_prev, last_printed, depth, new_prefix, print_depth + 1UL );
1880 1497 : curr = fd_forest_pool_ele_const( pool, curr->sibling );
1881 :
1882 : /* Set up prefix for following iterations */
1883 1497 : if( curr && curr->sibling != ULONG_MAX ) {
1884 0 : sprintf( new_prefix, "├── " ); /* any following forks start on new lines */
1885 1497 : } else {
1886 1497 : sprintf( new_prefix, "└── " ); /* any following forks start on new lines */
1887 1497 : }
1888 1497 : }
1889 :
1890 1497 : }
1891 :
1892 : static void
1893 660 : 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 ) {
1894 660 : fd_forest_blk_t const * pool = fd_forest_pool_const( forest );
1895 :
1896 660 : if( ele == NULL ) return;
1897 :
1898 : /* print the slot itself. either we might need to start a new interval, or it may get elided */
1899 660 : fd_forest_blk_t const * child = fd_forest_pool_ele_const( pool, ele->child );
1900 :
1901 660 : if( !elide ) {
1902 333 : if( space > 0 ) printf( "\n" );
1903 2703 : for( int i = 0; i < space; i++ ) printf( " " );
1904 333 : printf( "%s", prefix );
1905 333 : printf( "%lu", ele->slot );
1906 333 : }
1907 :
1908 660 : if( !child && !elide ) { /* double check these cases arent the same...*/
1909 93 : printf( "]" );
1910 93 : return;
1911 93 : } /* no children, close bracket */
1912 :
1913 567 : if( !child && elide ) {
1914 81 : printf( ", %lu]", ele->slot );
1915 81 : return;
1916 81 : }
1917 :
1918 486 : prev = ele;
1919 486 : char new_prefix[1024]; /* FIXME size this correctly */
1920 486 : int one_child = child && child->sibling == ULONG_MAX;
1921 486 : if( one_child &&
1922 486 : child->slot != ele->slot + 1 ) { // if I have ONE CHILD and one child is non-consecutive
1923 :
1924 90 : if( elide ) {
1925 : /* current slot wasn't printed, but now that we are branching,
1926 : we will want to print the current slot and close the bracket */
1927 15 : printf( ", %lu]", ele->slot );
1928 15 : space += fd_int_max( (int)fd_ulong_base10_dig_cnt( ele->slot ) + 2, 0 );
1929 75 : } else {
1930 75 : printf( "]");
1931 75 : }
1932 :
1933 90 : sprintf( new_prefix, "└── [" ); /* end branch */
1934 90 : ancestry_print( forest, child, space + 5, new_prefix, prev, 0 );
1935 396 : } else if ( one_child && child->slot == ele->slot + 1 ) {
1936 327 : ancestry_print( forest, child, space, prefix, prev, 1);
1937 327 : } else { /* multiple children */
1938 69 : if( elide ) {
1939 : /* current slot wasn't printed, but now that we are branching,
1940 : we will want to print the current slot and close the bracket */
1941 51 : printf( ", %lu]", ele->slot );
1942 51 : space += fd_int_max( (int)fd_ulong_base10_dig_cnt( ele->slot ) + 2, 0 );
1943 51 : } else {
1944 18 : printf( "]");
1945 18 : }
1946 :
1947 213 : while( child ) {
1948 144 : if( fd_forest_pool_ele_const( pool, child->sibling ) ) {
1949 75 : sprintf( new_prefix, "├── [" ); /* branch indicating more siblings follow */
1950 75 : ancestry_print( forest, child, space + 5, new_prefix, prev, 0 );
1951 75 : } else {
1952 69 : sprintf( new_prefix, "└── [" ); /* end branch */
1953 69 : ancestry_print( forest, child, space + 5, new_prefix, prev, 0 );
1954 69 : }
1955 144 : child = fd_forest_pool_ele_const( pool, child->sibling );
1956 144 : }
1957 69 : }
1958 486 : }
1959 :
1960 : void
1961 99 : fd_forest_ancestry_print( fd_forest_t const * forest ) {
1962 99 : printf(("\n\n[Ancestry]\n" ) );
1963 99 : ancestry_print( forest, fd_forest_pool_ele_const( fd_forest_pool_const( forest ), forest->root ), 0, "[", NULL, 0 );
1964 99 : fflush(stdout); /* Ensure ancestry printf output is flushed */
1965 99 : }
1966 :
1967 : void
1968 99 : fd_forest_frontier_print( fd_forest_t const * forest ) {
1969 99 : printf( "\n\n[Repairing Next]\n" );
1970 99 : fd_forest_conslist_t const * conslist = fd_forest_conslist_const( forest );
1971 99 : fd_forest_ref_t const * conspool = fd_forest_conspool_const( forest );
1972 99 : fd_forest_blk_t const * pool = fd_forest_pool_const( forest );
1973 99 : for( fd_forest_conslist_iter_t iter = fd_forest_conslist_iter_fwd_init( conslist, conspool );
1974 255 : !fd_forest_conslist_iter_done( iter, conslist, conspool );
1975 156 : iter = fd_forest_conslist_iter_fwd_next( iter, conslist, conspool ) ) {
1976 156 : fd_forest_ref_t const * ele = fd_forest_conslist_iter_ele_const( iter, conslist, conspool );
1977 156 : fd_forest_blk_t const * ele_ = fd_forest_pool_ele_const( pool, ele->idx );
1978 156 : printf("%lu (%u/%u)\n", ele_->slot, ele_->buffered_idx + 1, ele_->complete_idx + 1 );
1979 156 : }
1980 99 : fflush(stdout);
1981 99 : }
1982 :
1983 : void
1984 99 : fd_forest_orphaned_print( fd_forest_t const * forest ) {
1985 99 : printf( "\n[Orphaned]\n" );
1986 99 : fd_forest_subtlist_t const * subtlist = fd_forest_subtlist_const( forest );
1987 99 : fd_forest_blk_t const * pool = fd_forest_pool_const( forest );
1988 99 : for( fd_forest_subtlist_iter_t iter = fd_forest_subtlist_iter_fwd_init( subtlist, pool );
1989 132 : !fd_forest_subtlist_iter_done( iter, subtlist, pool );
1990 99 : iter = fd_forest_subtlist_iter_fwd_next( iter, subtlist, pool ) ) {
1991 33 : fd_forest_blk_t const * ele = fd_forest_subtlist_iter_ele_const( iter, subtlist, pool );
1992 33 : orphaned_print( forest, fd_forest_pool_ele_const( fd_forest_pool_const( forest ), fd_forest_pool_idx( pool, ele ) ), NULL, 0, 0, "", 0UL );
1993 33 : }
1994 99 : fflush(stdout);
1995 99 : }
1996 :
1997 : void
1998 99 : fd_forest_print( fd_forest_t const * forest ) {
1999 99 : if( FD_UNLIKELY( forest->root == ULONG_MAX ) ) return;
2000 99 : FD_LOG_NOTICE(("\n\n[Forest]" ) );
2001 99 : fd_forest_ancestry_print( forest );
2002 99 : fd_forest_frontier_print( forest );
2003 99 : fd_forest_orphaned_print( forest );
2004 99 : printf("\n");
2005 :
2006 : fflush(stdout);
2007 99 : }
2008 :
2009 : #undef FD_FOREST_PRINT
|
