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 : #define FD_FOREST_PRINT 1
10 :
11 : void *
12 0 : fd_forest_new( void * shmem, ulong ele_max, ulong seed ) {
13 0 : FD_TEST( fd_ulong_is_pow2( ele_max ) );
14 :
15 0 : if( FD_UNLIKELY( !shmem ) ) {
16 0 : FD_LOG_WARNING(( "NULL mem" ));
17 0 : return NULL;
18 0 : }
19 :
20 0 : if( FD_UNLIKELY( !fd_ulong_is_aligned( (ulong)shmem, fd_forest_align() ) ) ) {
21 0 : FD_LOG_WARNING(( "misaligned mem" ));
22 0 : return NULL;
23 0 : }
24 :
25 0 : ulong footprint = fd_forest_footprint( ele_max );
26 0 : if( FD_UNLIKELY( !footprint ) ) {
27 0 : FD_LOG_WARNING(( "bad ele_max (%lu)", ele_max ));
28 0 : return NULL;
29 0 : }
30 :
31 0 : fd_wksp_t * wksp = fd_wksp_containing( shmem );
32 0 : if( FD_UNLIKELY( !wksp ) ) {
33 0 : FD_LOG_WARNING(( "shmem must be part of a workspace" ));
34 0 : return NULL;
35 0 : }
36 :
37 0 : fd_memset( shmem, 0, footprint );
38 0 : fd_forest_t * forest;
39 :
40 0 : FD_SCRATCH_ALLOC_INIT( l, shmem );
41 0 : forest = FD_SCRATCH_ALLOC_APPEND( l, fd_forest_align(), sizeof(fd_forest_t) );
42 0 : void * ver = FD_SCRATCH_ALLOC_APPEND( l, fd_fseq_align(), fd_fseq_footprint() );
43 0 : void * pool = FD_SCRATCH_ALLOC_APPEND( l, fd_forest_pool_align(), fd_forest_pool_footprint ( ele_max ) );
44 0 : void * ancestry = FD_SCRATCH_ALLOC_APPEND( l, fd_forest_ancestry_align(), fd_forest_ancestry_footprint( ele_max ) );
45 0 : void * frontier = FD_SCRATCH_ALLOC_APPEND( l, fd_forest_frontier_align(), fd_forest_frontier_footprint( ele_max ) );
46 0 : void * orphaned = FD_SCRATCH_ALLOC_APPEND( l, fd_forest_orphaned_align(), fd_forest_orphaned_footprint( ele_max ) );
47 0 : void * deque = FD_SCRATCH_ALLOC_APPEND( l, fd_forest_deque_align(), fd_forest_deque_footprint ( ele_max ) );
48 0 : FD_TEST( FD_SCRATCH_ALLOC_FINI( l, fd_forest_align() ) == (ulong)shmem + footprint );
49 :
50 0 : forest->root = ULONG_MAX;
51 0 : forest->wksp_gaddr = fd_wksp_gaddr_fast( wksp, forest );
52 0 : forest->ver_gaddr = fd_wksp_gaddr_fast( wksp, fd_fseq_join ( fd_fseq_new ( ver, FD_FOREST_VER_UNINIT ) ) );
53 0 : forest->pool_gaddr = fd_wksp_gaddr_fast( wksp, fd_forest_pool_join ( fd_forest_pool_new ( pool, ele_max ) ) );
54 0 : forest->ancestry_gaddr = fd_wksp_gaddr_fast( wksp, fd_forest_ancestry_join( fd_forest_ancestry_new( ancestry, ele_max, seed ) ) );
55 0 : forest->frontier_gaddr = fd_wksp_gaddr_fast( wksp, fd_forest_frontier_join( fd_forest_frontier_new( frontier, ele_max, seed ) ) );
56 0 : forest->orphaned_gaddr = fd_wksp_gaddr_fast( wksp, fd_forest_orphaned_join( fd_forest_orphaned_new( orphaned, ele_max, seed ) ) );
57 0 : forest->deque_gaddr = fd_wksp_gaddr_fast( wksp, fd_forest_deque_join ( fd_forest_deque_new ( deque, ele_max ) ) );
58 :
59 0 : FD_COMPILER_MFENCE();
60 0 : FD_VOLATILE( forest->magic ) = FD_FOREST_MAGIC;
61 0 : FD_COMPILER_MFENCE();
62 :
63 0 : return shmem;
64 0 : }
65 :
66 : fd_forest_t *
67 0 : fd_forest_join( void * shforest ) {
68 0 : fd_forest_t * forest = (fd_forest_t *)shforest;
69 :
70 0 : if( FD_UNLIKELY( !forest ) ) {
71 0 : FD_LOG_WARNING(( "NULL forest" ));
72 0 : return NULL;
73 0 : }
74 :
75 0 : if( FD_UNLIKELY( !fd_ulong_is_aligned((ulong)forest, fd_forest_align() ) ) ) {
76 0 : FD_LOG_WARNING(( "misaligned forest" ));
77 0 : return NULL;
78 0 : }
79 :
80 0 : fd_wksp_t * wksp = fd_wksp_containing( forest );
81 0 : if( FD_UNLIKELY( !wksp ) ) {
82 0 : FD_LOG_WARNING(( "forest must be part of a workspace" ));
83 0 : return NULL;
84 0 : }
85 :
86 0 : return forest;
87 0 : }
88 :
89 : void *
90 0 : fd_forest_leave( fd_forest_t const * forest ) {
91 :
92 0 : if( FD_UNLIKELY( !forest ) ) {
93 0 : FD_LOG_WARNING(( "NULL forest" ));
94 0 : return NULL;
95 0 : }
96 :
97 0 : return (void *)forest;
98 0 : }
99 :
100 : void *
101 0 : fd_forest_delete( void * forest ) {
102 :
103 0 : if( FD_UNLIKELY( !forest ) ) {
104 0 : FD_LOG_WARNING(( "NULL forest" ));
105 0 : return NULL;
106 0 : }
107 :
108 0 : if( FD_UNLIKELY( !fd_ulong_is_aligned((ulong)forest, fd_forest_align() ) ) ) {
109 0 : FD_LOG_WARNING(( "misaligned forest" ));
110 0 : return NULL;
111 0 : }
112 :
113 : // TODO: zero out mem?
114 :
115 0 : return forest;
116 0 : }
117 :
118 : fd_forest_t *
119 0 : fd_forest_init( fd_forest_t * forest, ulong root_slot ) {
120 0 : FD_TEST( forest );
121 0 : FD_TEST( fd_fseq_query( fd_forest_ver( forest ) ) == FD_FOREST_VER_UNINIT );
122 :
123 0 : VER_INC;
124 :
125 0 : fd_forest_ele_t * pool = fd_forest_pool( forest );
126 0 : ulong null = fd_forest_pool_idx_null( pool );
127 0 : fd_forest_frontier_t * frontier = fd_forest_frontier( forest );
128 :
129 : /* Initialize the root node from a pool element. */
130 :
131 0 : fd_forest_ele_t * root_ele = fd_forest_pool_ele_acquire( pool );
132 0 : root_ele->slot = root_slot;
133 0 : root_ele->parent = null;
134 0 : root_ele->child = null;
135 0 : root_ele->sibling = null;
136 0 : root_ele->buffered_idx = 0;
137 0 : root_ele->complete_idx = 0;
138 :
139 0 : fd_forest_ele_idxs_null( root_ele->idxs );
140 :
141 0 : forest->root = fd_forest_pool_idx( pool, root_ele );
142 0 : fd_forest_frontier_ele_insert( frontier, root_ele, pool ); /* cannot fail */
143 :
144 : /* Sanity checks. */
145 :
146 0 : FD_TEST( root_ele );
147 0 : FD_TEST( root_ele == fd_forest_frontier_ele_query( frontier, &root_slot, NULL, pool ));
148 0 : FD_TEST( root_ele->slot == root_slot );
149 :
150 0 : return forest;
151 0 : }
152 :
153 : void *
154 0 : fd_forest_fini( fd_forest_t * forest ) {
155 0 : fd_fseq_update( fd_forest_ver( forest ), FD_FOREST_VER_UNINIT );
156 0 : return (void *)forest;
157 0 : }
158 :
159 : int
160 0 : fd_forest_verify( fd_forest_t const * forest ) {
161 0 : if( FD_UNLIKELY( !forest ) ) {
162 0 : FD_LOG_WARNING(( "NULL forest" ));
163 0 : return -1;
164 0 : }
165 :
166 0 : if( FD_UNLIKELY( !fd_ulong_is_aligned( (ulong)forest, fd_forest_align() ) ) ) {
167 0 : FD_LOG_WARNING(( "misaligned forest" ));
168 0 : return -1;
169 0 : }
170 :
171 0 : fd_wksp_t * wksp = fd_wksp_containing( forest );
172 0 : if( FD_UNLIKELY( !wksp ) ) {
173 0 : FD_LOG_WARNING(( "forest must be part of a workspace" ));
174 0 : return -1;
175 0 : }
176 :
177 0 : if( FD_UNLIKELY( forest->magic!=FD_FOREST_MAGIC ) ) {
178 0 : FD_LOG_WARNING(( "bad magic" ));
179 0 : return -1;
180 0 : }
181 :
182 0 : if( FD_UNLIKELY( fd_fseq_query( fd_forest_ver_const( forest ) ) == ULONG_MAX ) ) {
183 0 : FD_LOG_WARNING(( "forest uninitialized or invalid" ));
184 0 : return -1;
185 0 : }
186 :
187 0 : fd_forest_ele_t const * pool = fd_forest_pool_const( forest );
188 0 : if( fd_forest_ancestry_verify( fd_forest_ancestry_const( forest ), fd_forest_pool_max( pool ), pool ) == -1 ) return -1;
189 0 : if( fd_forest_frontier_verify( fd_forest_frontier_const( forest ), fd_forest_pool_max( pool ), pool ) == -1 ) return -1;
190 :
191 0 : fd_forest_frontier_t const * frontier = fd_forest_frontier_const( forest );
192 0 : fd_forest_orphaned_t const * orphaned = fd_forest_orphaned_const( forest );
193 0 : fd_forest_ancestry_t const * ancestry = fd_forest_ancestry_const( forest );
194 :
195 : /* Invariant: elements can only appear in one of the three maps. */
196 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 ) ) {
197 0 : fd_forest_ele_t const * ele = fd_forest_frontier_iter_ele_const( iter, frontier, pool );
198 0 : if( fd_forest_ancestry_ele_query_const( ancestry, &ele->slot, NULL, pool ) ) return -1;
199 0 : if( fd_forest_orphaned_ele_query_const( orphaned, &ele->slot, NULL, pool ) ) return -1;
200 0 : }
201 :
202 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 ) ) {
203 0 : fd_forest_ele_t const * ele = fd_forest_orphaned_iter_ele_const( iter, orphaned, pool );
204 0 : if( fd_forest_ancestry_ele_query_const( ancestry, &ele->slot, NULL, pool ) ) return -1;
205 0 : if( fd_forest_frontier_ele_query_const( frontier, &ele->slot, NULL, pool ) ) return -1;
206 0 : }
207 :
208 0 : return 0;
209 0 : }
210 :
211 : FD_FN_PURE static inline ulong *
212 0 : fd_forest_deque( fd_forest_t * forest ) {
213 0 : return fd_wksp_laddr_fast( fd_forest_wksp( forest ), forest->deque_gaddr );
214 0 : }
215 :
216 : /* remove removes and returns a connected ele from ancestry or frontier
217 : maps. does not remove orphaned ele. does not unlink ele. */
218 :
219 : static fd_forest_ele_t *
220 0 : ancestry_frontier_remove( fd_forest_t * forest, ulong slot ) {
221 0 : fd_forest_ele_t * pool = fd_forest_pool( forest );
222 0 : fd_forest_ele_t * ele = NULL;
223 0 : ele = fd_forest_ancestry_ele_remove( fd_forest_ancestry( forest ), &slot, NULL, pool );
224 0 : ele = fd_ptr_if( !ele, fd_forest_frontier_ele_remove( fd_forest_frontier( forest ), &slot, NULL, pool ), ele );
225 0 : return ele;
226 0 : }
227 :
228 : /* link ele to the tree via its sibling. */
229 :
230 : static void
231 0 : link_sibling( fd_forest_t * forest, fd_forest_ele_t * sibling, fd_forest_ele_t * ele ) {
232 0 : fd_forest_ele_t * pool = fd_forest_pool( forest );
233 0 : ulong null = fd_forest_pool_idx_null( pool );
234 0 : while( FD_UNLIKELY( sibling->sibling != null )) sibling = fd_forest_pool_ele( pool, sibling->sibling );
235 0 : sibling->sibling = fd_forest_pool_idx( pool, ele );
236 0 : }
237 :
238 : /* link child to the tree via its parent. */
239 :
240 : static void
241 0 : link( fd_forest_t * forest, fd_forest_ele_t * parent, fd_forest_ele_t * child ) {
242 0 : fd_forest_ele_t * pool = fd_forest_pool( forest );
243 0 : ulong null = fd_forest_pool_idx_null( pool );
244 0 : if( FD_LIKELY( parent->child == null ) ) parent->child = fd_forest_pool_idx( pool, child ); /* left-child */
245 0 : else link_sibling( forest, fd_forest_pool_ele( pool, parent->child ), child ); /* right-sibling */
246 0 : child->parent = fd_forest_pool_idx( pool, parent );
247 0 : }
248 :
249 : /* advance_frontier attempts to advance the frontier beginning from slot
250 : using BFS. head is the first element of a linked list representing
251 : the BFS queue. A slot can be advanced if all shreds for the block
252 : are received ie. consumed_idx = complete_idx. */
253 :
254 : static void
255 0 : advance_frontier( fd_forest_t * forest, ulong slot, ushort parent_off ) {
256 0 : fd_forest_ele_t * pool = fd_forest_pool( forest );
257 0 : fd_forest_ancestry_t * ancestry = fd_forest_ancestry( forest );
258 0 : fd_forest_frontier_t * frontier = fd_forest_frontier( forest );
259 0 : ulong * queue = fd_forest_deque( forest );
260 :
261 0 : fd_forest_ele_t * ele;
262 0 : ele = fd_forest_frontier_ele_query( fd_forest_frontier( forest ), &slot, NULL, pool );
263 0 : ulong parent_slot = slot - parent_off;
264 0 : ele = fd_ptr_if( !ele, fd_forest_frontier_ele_query( fd_forest_frontier( forest ), &parent_slot, NULL, pool ), ele );
265 0 : if( FD_UNLIKELY( !ele ) ) return;
266 :
267 0 : # if FD_FOREST_USE_HANDHOLDING
268 0 : FD_TEST( fd_forest_deque_cnt( queue ) == 0 );
269 0 : # endif
270 :
271 : /* BFS elements as pool idxs.
272 : Invariant: whatever is in the queue, must be on the frontier. */
273 0 : fd_forest_deque_push_tail( queue, fd_forest_pool_idx( pool, ele ) );
274 0 : while( FD_LIKELY( fd_forest_deque_cnt( queue ) ) ) {
275 0 : fd_forest_ele_t * head = fd_forest_pool_ele( pool, fd_forest_deque_pop_head( queue ) );
276 0 : fd_forest_ele_t * child = fd_forest_pool_ele( pool, head->child );
277 0 : if( FD_LIKELY( child && head->complete_idx != UINT_MAX && head->buffered_idx == head->complete_idx ) ) {
278 0 : fd_forest_frontier_ele_remove( frontier, &head->slot, NULL, pool );
279 0 : fd_forest_ancestry_ele_insert( ancestry, head, pool );
280 0 : while( FD_LIKELY( child ) ) { /* append children to frontier */
281 0 : fd_forest_ancestry_ele_remove( ancestry, &child->slot, NULL, pool );
282 0 : fd_forest_frontier_ele_insert( frontier, child, pool );
283 :
284 0 : fd_forest_deque_push_tail( queue, fd_forest_pool_idx( pool, child ) );
285 0 : child = fd_forest_pool_ele( pool, child->sibling );
286 0 : }
287 0 : }
288 0 : }
289 0 : }
290 :
291 : static fd_forest_ele_t *
292 0 : query( fd_forest_t * forest, ulong slot ) {
293 0 : fd_forest_ele_t * pool = fd_forest_pool( forest );
294 0 : fd_forest_ancestry_t * ancestry = fd_forest_ancestry( forest );
295 0 : fd_forest_frontier_t * frontier = fd_forest_frontier( forest );
296 0 : fd_forest_orphaned_t * orphaned = fd_forest_orphaned( forest );
297 :
298 0 : fd_forest_ele_t * ele;
299 0 : ele = fd_forest_ancestry_ele_query( ancestry, &slot, NULL, pool );
300 0 : ele = fd_ptr_if( !ele, fd_forest_frontier_ele_query( frontier, &slot, NULL, pool ), ele );
301 0 : ele = fd_ptr_if( !ele, fd_forest_orphaned_ele_query( orphaned, &slot, NULL, pool ), ele );
302 0 : return ele;
303 0 : }
304 :
305 : static fd_forest_ele_t *
306 0 : acquire( fd_forest_t * forest, ulong slot ) {
307 0 : fd_forest_ele_t * pool = fd_forest_pool( forest );
308 0 : fd_forest_ele_t * ele = fd_forest_pool_ele_acquire( pool );
309 0 : ulong null = fd_forest_pool_idx_null( pool );
310 :
311 0 : ele->slot = slot;
312 0 : ele->next = null;
313 0 : ele->parent = null;
314 0 : ele->child = null;
315 0 : ele->sibling = null;
316 :
317 0 : ele->buffered_idx = UINT_MAX;
318 0 : ele->complete_idx = UINT_MAX;
319 :
320 0 : fd_forest_ele_idxs_null( ele->cmpl ); /* FIXME expensive */
321 0 : fd_forest_ele_idxs_null( ele->fecs ); /* FIXME expensive */
322 0 : fd_forest_ele_idxs_null( ele->idxs ); /* FIXME expensive */
323 :
324 0 : return ele;
325 0 : }
326 :
327 : static fd_forest_ele_t *
328 0 : insert( fd_forest_t * forest, ulong slot, ushort parent_off ) {
329 0 : fd_forest_ele_t * pool = fd_forest_pool( forest );
330 :
331 0 : # if FD_FOREST_USE_HANDHOLDING
332 0 : FD_TEST( parent_off <= slot ); /* caller err - inval */
333 0 : FD_TEST( fd_forest_pool_free( pool ) ); /* impl err - oom */
334 0 : FD_TEST( slot > fd_forest_root_slot( forest ) ); /* caller error - inval */
335 0 : # endif
336 :
337 0 : fd_forest_ele_t * ele = acquire( forest, slot );
338 0 : ulong parent_slot = slot - parent_off;
339 0 : fd_forest_ele_t * parent = query( forest, parent_slot );
340 0 : if( FD_LIKELY( parent ) ) {
341 0 : fd_forest_ancestry_ele_insert( fd_forest_ancestry( forest ), ele, pool );
342 0 : link( forest, parent, ele ); /* cannot fail */
343 :
344 : /* Edge case where we are creating a fork off of a node that is behind the frontier.
345 : We need to add this node to the frontier. */
346 :
347 0 : fd_forest_ele_t * ancestor = parent;
348 0 : while( ancestor /* ancestor exists */
349 0 : && !fd_forest_frontier_ele_query( fd_forest_frontier( forest ), &ancestor->slot, NULL, pool ) /* ancestor is not on frontier */
350 0 : && !fd_forest_orphaned_ele_query( fd_forest_orphaned( forest ), &ancestor->slot, NULL, pool ) /* ancestor is not an orphan */ ) {
351 0 : ancestor = fd_forest_pool_ele( pool, ancestor->parent );
352 0 : }
353 0 : if( FD_UNLIKELY( !ancestor ) ) {
354 : /* Did not find ancestor on frontier OR orphan, which means it must be behind the frontier barrier. */
355 0 : fd_forest_ancestry_ele_remove( fd_forest_ancestry( forest ), &ele->slot, NULL, pool );
356 0 : fd_forest_frontier_ele_insert( fd_forest_frontier( forest ), ele, pool );
357 0 : }
358 0 : }
359 0 : return ele;
360 0 : }
361 :
362 : fd_forest_ele_t *
363 0 : fd_forest_query( fd_forest_t * forest, ulong slot ) {
364 0 : return query( forest, slot );
365 0 : }
366 :
367 : fd_forest_ele_t *
368 0 : fd_forest_data_shred_insert( fd_forest_t * forest, ulong slot, ushort parent_off, uint shred_idx, uint fec_set_idx, FD_PARAM_UNUSED int data_complete, int slot_complete ) {
369 0 : # if FD_FOREST_USE_HANDHOLDING
370 0 : FD_TEST( slot > fd_forest_root_slot( forest ) ); /* caller error - inval */
371 0 : # endif
372 :
373 0 : VER_INC;
374 :
375 0 : fd_forest_ele_t * pool = fd_forest_pool( forest );
376 0 : fd_forest_ele_t * ele = query( forest, slot );
377 0 : if( FD_UNLIKELY( !ele ) ) ele = insert( forest, slot, parent_off ); /* cannot fail */
378 0 : if( FD_UNLIKELY( ele->parent == fd_forest_pool_idx_null( pool ) ) ) {
379 :
380 : /* `ele` is an orphan tree root so it does not have a parent. Now,
381 : having received a shred for ele, we know ele's parent
382 : slot. Here we check whether ele's parent is already in the tree.
383 : If it is, then the orphan tree rooted at ele can be linked to the
384 : tree containing ele's parent (which may be another orphan tree or
385 : the canonical tree). */
386 :
387 0 : fd_forest_ele_t * parent = query( forest, slot - parent_off );
388 0 : if( FD_UNLIKELY( !parent ) ) { /* parent is either in canonical or another orphan tree */
389 0 : parent = acquire( forest, slot - parent_off );
390 0 : fd_forest_orphaned_ele_insert( fd_forest_orphaned( forest ), parent, pool ); /* update orphan root */
391 0 : }
392 0 : fd_forest_orphaned_ele_remove( fd_forest_orphaned( forest ), &ele->slot, NULL, pool );
393 0 : fd_forest_ancestry_ele_insert( fd_forest_ancestry( forest ), ele, pool );
394 0 : link( forest, parent, ele );
395 0 : }
396 0 : fd_forest_ele_idxs_insert( ele->fecs, fec_set_idx );
397 0 : fd_forest_ele_idxs_insert( ele->idxs, shred_idx );
398 0 : while( fd_forest_ele_idxs_test( ele->idxs, ele->buffered_idx + 1U ) ) ele->buffered_idx++;
399 0 : ele->complete_idx = fd_uint_if( slot_complete, shred_idx, ele->complete_idx );
400 0 : advance_frontier( forest, slot, parent_off );
401 0 : return ele;
402 0 : }
403 :
404 : fd_forest_ele_t const *
405 0 : fd_forest_publish( fd_forest_t * forest, ulong new_root_slot ) {
406 0 : FD_LOG_DEBUG(( "[%s] slot %lu", __func__, new_root_slot ));
407 :
408 0 : VER_INC;
409 :
410 0 : fd_forest_ancestry_t * ancestry = fd_forest_ancestry( forest );
411 0 : fd_forest_frontier_t * frontier = fd_forest_frontier( forest );
412 0 : fd_forest_orphaned_t * orphaned = fd_forest_orphaned( forest );
413 0 : fd_forest_ele_t * pool = fd_forest_pool( forest );
414 0 : ulong null = fd_forest_pool_idx_null( pool );
415 0 : ulong * queue = fd_forest_deque( forest );
416 :
417 0 : fd_forest_ele_t * old_root_ele = fd_forest_pool_ele( pool, forest->root );
418 0 : fd_forest_ele_t * new_root_ele = query( forest, new_root_slot );
419 :
420 0 : # if FD_FOREST_USE_HANDHOLDING
421 0 : if( FD_LIKELY( new_root_ele ) ) {
422 0 : FD_TEST( new_root_ele->slot > old_root_ele->slot ); /* caller error - inval */
423 0 : }
424 0 : # endif
425 :
426 : /* Edge case where if we haven't been getting repairs, and we have a
427 : gap between the root and orphans. we publish forward to a slot that
428 : we don't have. This only case this should be happening is when we
429 : load a second incremental and that incremental slot lives in the
430 : gap. In that case this isn't a bug, but we should be treating this
431 : new root like the snapshot slot / init root. Should be happening
432 : very rarely given a well-functioning repair. */
433 :
434 0 : if( FD_UNLIKELY( !new_root_ele ) ) {
435 0 : new_root_ele = acquire( forest, new_root_slot );
436 0 : new_root_ele->complete_idx = 0;
437 0 : new_root_ele->buffered_idx = 0;
438 0 : fd_forest_frontier_ele_insert( frontier, new_root_ele, pool );
439 0 : }
440 :
441 : /* First, remove the previous root, and add it to a FIFO prune queue.
442 : head points to the queue head (initialized with old_root_ele). */
443 0 : # if FD_FOREST_USE_HANDHOLDING
444 0 : FD_TEST( fd_forest_deque_cnt( queue ) == 0 );
445 0 : # endif
446 0 : fd_forest_ele_t * head = ancestry_frontier_remove( forest, old_root_ele->slot );
447 0 : if( FD_LIKELY( head ) ) fd_forest_deque_push_tail( queue, fd_forest_pool_idx( pool, head ) );
448 :
449 : /* Second, BFS down the tree, inserting each ele into the prune queue
450 : except for the new root. Loop invariant: head always descends from
451 : old_root_ele and never descends from new_root_ele. */
452 :
453 0 : while( FD_LIKELY( fd_forest_deque_cnt( queue ) ) ) {
454 0 : head = fd_forest_pool_ele( pool, fd_forest_deque_pop_head( queue ) );
455 0 : fd_forest_ele_t * child = fd_forest_pool_ele( pool, head->child );
456 0 : while( FD_LIKELY( child ) ) {
457 0 : if( FD_LIKELY( child != new_root_ele ) ) { /* do not prune new root or descendants */
458 0 : ulong idx = fd_forest_ancestry_idx_remove( ancestry, &child->slot, null, pool );
459 0 : idx = fd_ulong_if( idx != null, idx, fd_forest_frontier_idx_remove( frontier, &child->slot, null, pool ) );
460 0 : fd_forest_deque_push_tail( queue, idx );
461 0 : }
462 0 : child = fd_forest_pool_ele( pool, child->sibling );
463 0 : }
464 0 : fd_forest_pool_ele_release( pool, head );
465 0 : }
466 :
467 : /* If there is nothing on the frontier, we have hit an edge case
468 : during catching up where all of our frontiers were < the new root.
469 : In that case we need to continue repairing from the new root, so
470 : add it to the frontier. */
471 :
472 0 : if( FD_UNLIKELY( fd_forest_frontier_iter_done( fd_forest_frontier_iter_init( frontier, pool ), frontier, pool ) ) ) {
473 0 : fd_forest_ele_t * remove = fd_forest_ancestry_ele_remove( ancestry, &new_root_ele->slot, NULL, pool );
474 0 : if( FD_UNLIKELY( !remove ) ) {
475 : /* Very rare case where during second incremental load we could publish to an orphaned slot */
476 0 : remove = fd_forest_orphaned_ele_remove( orphaned, &new_root_ele->slot, NULL, pool );
477 0 : }
478 0 : FD_TEST( remove == new_root_ele );
479 0 : fd_forest_frontier_ele_insert( frontier, new_root_ele, pool );
480 0 : new_root_ele->complete_idx = 0;
481 0 : new_root_ele->buffered_idx = 0;
482 0 : advance_frontier( forest, new_root_ele->slot, 0 );
483 0 : }
484 :
485 0 : new_root_ele->parent = null; /* unlink new root from parent */
486 0 : forest->root = fd_forest_pool_idx( pool, new_root_ele );
487 :
488 : /* Lastly, cleanup orphans if there orphan heads < new_root_slot.
489 : First, add any relevant orphans to the prune queue. */
490 :
491 0 : for( fd_forest_orphaned_iter_t iter = fd_forest_orphaned_iter_init( orphaned, pool );
492 0 : !fd_forest_orphaned_iter_done( iter, orphaned, pool );
493 0 : iter = fd_forest_orphaned_iter_next( iter, orphaned, pool ) ) {
494 0 : fd_forest_ele_t * ele = fd_forest_orphaned_iter_ele( iter, orphaned, pool );
495 0 : if( FD_UNLIKELY( ele->slot < new_root_slot ) ) {
496 0 : fd_forest_deque_push_tail( queue, fd_forest_pool_idx( pool, ele ) );
497 0 : }
498 0 : }
499 :
500 : /* Now BFS and clean up children of these orphan heads */
501 0 : while( FD_UNLIKELY( fd_forest_deque_cnt( queue ) ) ) {
502 0 : head = fd_forest_pool_ele( pool, fd_forest_deque_pop_head( queue ) );
503 0 : fd_forest_ele_t * child = fd_forest_pool_ele( pool, head->child );
504 0 : while( FD_LIKELY( child ) ) {
505 0 : if( FD_LIKELY( child != new_root_ele ) ) {
506 0 : fd_forest_deque_push_tail( queue, fd_forest_pool_idx( pool, child ) );
507 0 : }
508 0 : child = fd_forest_pool_ele( pool, child->sibling );
509 0 : }
510 0 : ulong remove = fd_forest_orphaned_idx_remove( orphaned, &head->slot, null, pool ); /* remove myself */
511 0 : remove = fd_ulong_if( remove == null, fd_forest_ancestry_idx_remove( ancestry, &head->slot, null, pool ), remove );
512 0 : fd_forest_pool_ele_release( pool, head ); /* free head */
513 0 : }
514 0 : return new_root_ele;
515 0 : }
516 :
517 : fd_forest_iter_t
518 0 : fd_forest_iter_init( fd_forest_t * forest ) {
519 : /* Find first element. Anything on the frontier. */
520 0 : fd_forest_ele_t const * pool = fd_forest_pool_const( forest );
521 0 : fd_forest_frontier_t const * frontier = fd_forest_frontier_const( forest );
522 :
523 0 : fd_forest_frontier_iter_t frontier_iter = fd_forest_frontier_iter_init( frontier, pool );
524 0 : fd_forest_iter_t repair_iter = { fd_forest_pool_idx_null( pool ),
525 0 : UINT_MAX,
526 0 : fd_fseq_query( fd_forest_ver_const( forest ) ),
527 0 : frontier_iter };
528 : /* Nothing on frontier */
529 :
530 0 : if( FD_UNLIKELY( fd_forest_frontier_iter_done( frontier_iter, frontier, pool ) ) ) return repair_iter;
531 :
532 : /* Populate initial iter shred index */
533 :
534 0 : fd_forest_ele_t const * ele = fd_forest_frontier_iter_ele_const( frontier_iter, frontier, pool );
535 0 : while( ele->complete_idx != UINT_MAX && ele->buffered_idx == ele->complete_idx ) {
536 : /* This fork frontier is actually complete, so we can skip it. Also
537 : handles edge case where we are calling iter_init right after a
538 : forest_init */
539 0 : frontier_iter = fd_forest_frontier_iter_next( frontier_iter, frontier, pool );
540 0 : if( FD_UNLIKELY( fd_forest_frontier_iter_done( frontier_iter, frontier, pool ) ) ) {
541 0 : repair_iter.ele_idx = fd_forest_pool_idx_null( pool );
542 0 : repair_iter.shred_idx = UINT_MAX; /* no more elements */
543 0 : return repair_iter;
544 0 : }
545 0 : ele = fd_forest_frontier_iter_ele_const( frontier_iter, frontier, pool );
546 0 : }
547 :
548 0 : repair_iter.ele_idx = frontier_iter.ele_idx;
549 0 : repair_iter.shred_idx = ele->complete_idx == UINT_MAX ? UINT_MAX : ele->buffered_idx + 1;
550 :
551 0 : return repair_iter;
552 0 : }
553 :
554 : fd_forest_iter_t
555 0 : fd_forest_iter_next( fd_forest_iter_t iter, fd_forest_t const * forest ) {
556 0 : fd_forest_frontier_t const * frontier = fd_forest_frontier_const( forest );
557 0 : fd_forest_ele_t const * pool = fd_forest_pool_const( forest );
558 0 : fd_forest_ele_t const * ele = fd_forest_pool_ele_const( pool, iter.ele_idx );
559 :
560 0 : if( iter.frontier_ver != fd_fseq_query( fd_forest_ver_const( forest ) ) ) {
561 : /* If the frontier has changed since we started this traversal, we
562 : need to reset the iterator. */
563 0 : iter.ele_idx = fd_forest_pool_idx_null( pool ) ;
564 0 : iter.shred_idx = UINT_MAX; /* no more elements */
565 0 : return iter;
566 0 : }
567 :
568 0 : uint next_shred_idx = iter.shred_idx;
569 0 : for(;;) {
570 0 : next_shred_idx++;
571 :
572 : /* Case 1: No more shreds in this slot to request, move to the
573 : next one. Wraparound the shred_idx.
574 :
575 : Case 2: original iter.shred_idx == UINT_MAX (implies prev req
576 : was a highest_window_idx request). Also requires moving to next
577 : slot and wrapping the shred_idx. */
578 :
579 0 : if( FD_UNLIKELY( next_shred_idx >= ele->complete_idx || iter.shred_idx == UINT_MAX ) ) {
580 0 : iter.ele_idx = ele->child;
581 0 : ele = fd_forest_pool_ele_const( pool, iter.ele_idx );
582 0 : if( FD_UNLIKELY( iter.ele_idx == fd_forest_pool_idx_null( pool ) ) ) {
583 0 : iter.shred_idx = UINT_MAX; /* no more elements */
584 :
585 : /* rare and unlikely to happen during a regular run, but if the
586 : frontier pool hasn't changed at all since we started this
587 : traversal, we can cleanly select the next node in the
588 : frontier using the stored frontier iterator. If the frontier
589 : has changed though, we should just return done and let the
590 : caller reset the iterator. */
591 :
592 0 : if( FD_UNLIKELY( iter.frontier_ver == fd_fseq_query( fd_forest_ver_const( forest ) ) ) ) {
593 0 : iter.head = fd_forest_frontier_iter_next( iter.head, frontier, pool );
594 0 : if( FD_UNLIKELY( !fd_forest_frontier_iter_done( iter.head, frontier, pool ) ) ) {
595 0 : iter.ele_idx = iter.head.ele_idx;
596 0 : ele = fd_forest_pool_ele_const( pool, iter.head.ele_idx );
597 0 : iter.shred_idx = ele->complete_idx == UINT_MAX ? UINT_MAX : ele->buffered_idx + 1;
598 0 : }
599 0 : }
600 0 : return iter;
601 0 : }
602 0 : next_shred_idx = ele->buffered_idx + 1;
603 0 : }
604 :
605 : /* Common case - valid shred to request. Note you can't know the
606 : ele->complete_idx until you have actually recieved the slot
607 : complete shred, thus the we can do lt instead of leq */
608 :
609 0 : if( ele->complete_idx != UINT_MAX &&
610 0 : next_shred_idx < ele->complete_idx &&
611 0 : !fd_forest_ele_idxs_test( ele->idxs, next_shred_idx ) ) {
612 0 : iter.shred_idx = next_shred_idx;
613 0 : break;
614 0 : }
615 :
616 : /* Current slot actually needs a highest_window_idx request */
617 :
618 0 : if( FD_UNLIKELY( ele->complete_idx == UINT_MAX ) ) {
619 0 : iter.shred_idx = UINT_MAX;
620 0 : break;
621 0 : }
622 0 : }
623 0 : return iter;
624 0 : }
625 :
626 : int
627 0 : fd_forest_iter_done( fd_forest_iter_t iter, fd_forest_t const * forest ) {
628 0 : fd_forest_ele_t const * pool = fd_forest_pool_const( forest );
629 0 : return iter.ele_idx == fd_forest_pool_idx_null( pool ); /* no more elements */
630 0 : }
631 :
632 : #include <stdio.h>
633 :
634 : static void
635 0 : preorder( fd_forest_t const * forest, fd_forest_ele_t const * ele ) {
636 0 : fd_forest_ele_t const * pool = fd_forest_pool_const( forest );
637 0 : fd_forest_ele_t const * child = fd_forest_pool_ele_const( pool, ele->child );
638 0 : printf( "%lu ", ele->slot );
639 0 : while( FD_LIKELY( child ) ) {
640 0 : preorder( forest, child );
641 0 : child = fd_forest_pool_ele_const( pool, child->sibling );
642 0 : }
643 0 : }
644 :
645 : void
646 0 : fd_forest_preorder_print( fd_forest_t const * forest ) {
647 0 : FD_LOG_NOTICE( ( "\n\n[Preorder]" ) );
648 0 : preorder( forest, fd_forest_pool_ele_const( fd_forest_pool_const( forest ), forest->root ) );
649 0 : printf( "\n\n" );
650 0 : }
651 :
652 : /* TODO use bit tricks / change */
653 : static int
654 0 : num_digits( ulong slot ) {
655 : /* using log10 */
656 0 : int digits = 0;
657 0 : while( slot ) {
658 0 : digits++;
659 0 : slot /= 10;
660 0 : }
661 0 : return digits;
662 0 : }
663 :
664 : static void
665 : ancestry_print2( fd_forest_t const * forest,
666 : fd_forest_ele_t const * ele,
667 : fd_forest_ele_t const * prev,
668 : ulong last_printed,
669 : int depth,
670 0 : const char * prefix ) {
671 :
672 0 : if( FD_UNLIKELY( ele == NULL ) ) return;
673 :
674 0 : fd_forest_ele_t const * pool = fd_forest_pool_const( forest );
675 0 : int digits = num_digits( ele->slot );
676 :
677 : /* If there is a prefix, this means we are on a fork, and we need to
678 : indent to the correct depth. We do depth - 1 for more satisfying
679 : spacing. */
680 0 : if( FD_UNLIKELY( strcmp( prefix, "" ) ) ) {
681 0 : for( int i = 0; i < depth - 1; i++ ) printf( " " );
682 0 : if( depth > 0 ) printf( "%s", prefix );
683 0 : }
684 :
685 0 : if ( FD_UNLIKELY( !prev ) ) { // New interval
686 0 : printf("[%lu" , ele->slot );
687 0 : last_printed = ele->slot;
688 0 : depth += 1 + digits;
689 0 : }
690 :
691 0 : fd_forest_ele_t const * curr = fd_forest_pool_ele_const( pool, ele->child );
692 :
693 : /* Cases in which we close the interval:
694 : 1. the slots are no longer consecutive. no eliding, close bracket
695 : 2. current ele has multiple children, want to print forks.
696 : Maintain last_printed on this fork so that we don't print [a, a]
697 : intervals. */
698 :
699 0 : fd_forest_ele_t const * new_prev = ele;
700 :
701 0 : if( prev && prev->slot != ele->slot - 1 ) { // non-consecutive, do not elide
702 0 : if( last_printed == prev->slot ){
703 0 : printf( "] ── [%lu", ele->slot );
704 0 : depth += digits + 6;
705 0 : } else {
706 0 : printf( ", %lu] ── [%lu", prev->slot, ele->slot );
707 0 : depth += digits + num_digits(prev->slot ) + 8;
708 0 : }
709 0 : last_printed = ele->slot;
710 0 : } else if( curr && curr->sibling != ULONG_MAX ) { // has multiple children, do not elide
711 0 : if( last_printed == ele->slot ){
712 0 : printf( "] ── " );
713 0 : depth += 5;
714 0 : } else {
715 0 : printf( ", %lu] ── ", ele->slot );
716 0 : depth += digits + 2;
717 0 : }
718 0 : last_printed = ele->slot;
719 0 : new_prev = NULL;
720 0 : }
721 :
722 0 : if( !curr ){ // no children, close bracket, end fork
723 0 : if( last_printed == ele->slot ){
724 0 : printf( "]\n" );
725 0 : } else {
726 0 : printf( ", %lu]\n", ele->slot );
727 0 : }
728 0 : return;
729 0 : }
730 :
731 0 : char new_prefix[512]; /* FIXME size this correctly */
732 0 : new_prefix[0] = '\0'; /* first fork stays on the same line, no prefix */
733 0 : while( curr ) {
734 0 : if( fd_forest_pool_ele_const( pool, curr->sibling ) ) {
735 0 : ancestry_print2( forest, curr, new_prev, last_printed, depth, new_prefix );
736 0 : } else {
737 0 : ancestry_print2( forest, curr, new_prev, last_printed, depth, new_prefix );
738 0 : }
739 0 : curr = fd_forest_pool_ele_const( pool, curr->sibling );
740 :
741 : /* Set up prefix for following iterations */
742 0 : if( curr && curr->sibling != ULONG_MAX ) {
743 0 : sprintf( new_prefix, "├── " ); /* any following forks start on new lines */
744 0 : } else {
745 0 : sprintf( new_prefix, "└── " ); /* any following forks start on new lines */
746 0 : }
747 0 : }
748 :
749 0 : }
750 :
751 : static void FD_FN_UNUSED
752 0 : ancestry_print( fd_forest_t const * forest, fd_forest_ele_t const * ele, int space, const char * prefix ) {
753 0 : fd_forest_ele_t const * pool = fd_forest_pool_const( forest );
754 0 :
755 0 : if( ele == NULL ) return;
756 0 :
757 0 : if( space > 0 ) printf( "\n" );
758 0 : for( int i = 0; i < space; i++ ) printf( " " );
759 0 : if ( ele->complete_idx == UINT_MAX ) printf( "%s%lu (%u/?)", prefix, ele->slot, ele->buffered_idx + 1 );
760 0 : else printf( "%s%lu (%u/%u)", prefix, ele->slot, ele->buffered_idx + 1, ele->complete_idx + 1 );
761 0 :
762 0 : fd_forest_ele_t const * curr = fd_forest_pool_ele_const( pool, ele->child );
763 0 :
764 0 : char new_prefix[1024]; /* FIXME size this correctly */
765 0 : while( curr ) {
766 0 : if( fd_forest_pool_ele_const( pool, curr->sibling ) ) {
767 0 : sprintf( new_prefix, "├── " ); /* branch indicating more siblings follow */
768 0 : ancestry_print( forest, curr, space + 4, new_prefix );
769 0 : } else {
770 0 : sprintf( new_prefix, "└── " ); /* end branch */
771 0 : ancestry_print( forest, curr, space + 4, new_prefix );
772 0 : }
773 0 : curr = fd_forest_pool_ele_const( pool, curr->sibling );
774 0 : }
775 0 : }
776 :
777 : static void
778 0 : ancestry_print3( fd_forest_t const * forest, fd_forest_ele_t const * ele, int space, const char * prefix, fd_forest_ele_t const * prev, int elide ) {
779 0 : fd_forest_ele_t const * pool = fd_forest_pool_const( forest );
780 :
781 0 : if( ele == NULL ) return;
782 :
783 : /* print the slot itself. either we might need to start a new interval, or it may get elided */
784 0 : fd_forest_ele_t const * child = fd_forest_pool_ele_const( pool, ele->child );
785 :
786 0 : if( !elide ) {
787 0 : if( space > 0 ) printf( "\n" );
788 0 : for( int i = 0; i < space; i++ ) printf( " " );
789 0 : printf( "%s", prefix );
790 0 : printf( "%lu", ele->slot );
791 0 : }
792 :
793 0 : if( !child && !elide ) { /* double check these cases arent the same...*/
794 0 : printf( "]" );
795 0 : return;
796 0 : } /* no children, close bracket */
797 :
798 0 : if( !child && elide ) {
799 0 : printf( ", %lu]", ele->slot );
800 0 : return;
801 0 : }
802 :
803 0 : prev = ele;
804 0 : char new_prefix[1024]; /* FIXME size this correctly */
805 0 : int one_child = child && child->sibling == ULONG_MAX;
806 0 : if( one_child &&
807 0 : child->slot != ele->slot + 1 ) { // if I have ONE CHILD and one child is non-consecutive
808 :
809 0 : if( elide ) {
810 : /* current slot wasn't printed, but now that we are branching,
811 : we will want to print the current slot and close the bracket */
812 0 : printf( ", %lu]", ele->slot );
813 0 : space += fd_int_max( num_digits( ele->slot ) + 2, 0 );
814 0 : } else {
815 0 : printf( "]");
816 0 : }
817 :
818 0 : sprintf( new_prefix, "└── [" ); /* end branch */
819 0 : ancestry_print3( forest, child, space + 5, new_prefix, prev, 0 );
820 0 : } else if ( one_child && child->slot == ele->slot + 1 ) {
821 0 : ancestry_print3( forest, child, space, prefix, prev, 1);
822 0 : } else { /* multiple children */
823 0 : if( elide ) {
824 : /* current slot wasn't printed, but now that we are branching,
825 : we will want to print the current slot and close the bracket */
826 0 : printf( ", %lu]", ele->slot );
827 0 : space += fd_int_max( num_digits( ele->slot ) + 2, 0 );
828 0 : } else {
829 0 : printf( "]");
830 0 : }
831 :
832 0 : while( child ) {
833 0 : if( fd_forest_pool_ele_const( pool, child->sibling ) ) {
834 0 : sprintf( new_prefix, "├── [" ); /* branch indicating more siblings follow */
835 0 : ancestry_print3( forest, child, space + 5, new_prefix, prev, 0 );
836 0 : } else {
837 0 : sprintf( new_prefix, "└── [" ); /* end branch */
838 0 : ancestry_print3( forest, child, space + 5, new_prefix, prev, 0 );
839 0 : }
840 0 : child = fd_forest_pool_ele_const( pool, child->sibling );
841 0 : }
842 0 : }
843 0 : }
844 :
845 : void
846 0 : fd_forest_ancestry_print( fd_forest_t const * forest ) {
847 0 : FD_LOG_NOTICE(("\n\n[Ancestry]\n\n" ) );
848 :
849 0 : ancestry_print3( forest, fd_forest_pool_ele_const( fd_forest_pool_const( forest ), forest->root ), 0, "[", NULL, 0 );
850 0 : }
851 :
852 : void
853 0 : fd_forest_frontier_print( fd_forest_t const * forest ) {
854 0 : printf( "\n\n[Frontier]\n" );
855 0 : fd_forest_ele_t const * pool = fd_forest_pool_const( forest );
856 0 : fd_forest_frontier_t const * frontier = fd_forest_frontier_const( forest );
857 0 : for( fd_forest_frontier_iter_t iter = fd_forest_frontier_iter_init( frontier, pool );
858 0 : !fd_forest_frontier_iter_done( iter, frontier, pool );
859 0 : iter = fd_forest_frontier_iter_next( iter, frontier, pool ) ) {
860 0 : fd_forest_ele_t const * ele = fd_forest_frontier_iter_ele_const( iter, frontier, pool );
861 0 : printf("%lu (%u/%u)\n", ele->slot, ele->buffered_idx + 1, ele->complete_idx + 1 );
862 : //ancestry_print( forest, fd_forest_pool_ele_const( fd_forest_pool_const( forest ), fd_forest_pool_idx( pool, ele ) ), 0, "" );
863 0 : }
864 0 : }
865 :
866 : void
867 0 : fd_forest_orphaned_print( fd_forest_t const * forest ) {
868 0 : printf( "\n\n[Orphaned]\n" );
869 0 : fd_forest_orphaned_t const * orphaned = fd_forest_orphaned_const( forest );
870 0 : fd_forest_ele_t const * pool = fd_forest_pool_const( forest );
871 0 : for( fd_forest_orphaned_iter_t iter = fd_forest_orphaned_iter_init( orphaned, pool );
872 0 : !fd_forest_orphaned_iter_done( iter, orphaned, pool );
873 0 : iter = fd_forest_orphaned_iter_next( iter, orphaned, pool ) ) {
874 0 : fd_forest_ele_t const * ele = fd_forest_orphaned_iter_ele_const( iter, orphaned, pool );
875 0 : ancestry_print2( forest, fd_forest_pool_ele_const( fd_forest_pool_const( forest ), fd_forest_pool_idx( pool, ele ) ), NULL, 0, 0, "" );
876 0 : }
877 0 : }
878 :
879 : void
880 0 : fd_forest_print( fd_forest_t const * forest ) {
881 0 : if( FD_UNLIKELY( forest->root == ULONG_MAX ) ) return;
882 0 : # if FD_FOREST_PRINT
883 0 : fd_forest_ancestry_print( forest );
884 0 : fd_forest_frontier_print( forest );
885 0 : fd_forest_orphaned_print( forest );
886 : printf("\n\n");
887 0 : # endif
888 0 : }
889 :
890 : #undef FD_FOREST_PRINT
|
