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