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