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