Line data Source code
1 : #include "fd_repair.h"
2 : #include "../../ballet/bmtree/fd_bmtree.h"
3 : #include "../../ballet/sha256/fd_sha256.h"
4 : #include "../../flamenco/alpenglow/fd_block_marker_serde.h"
5 : #include "../../disco/events/generated/fd_event_gen.h"
6 :
7 : int
8 : fd_repair_blk_treap_insert( fd_repair_t * self,
9 115929 : fd_repair_blk_t * blk ) {
10 115929 : fd_repair_slot_meta_t const * meta = fd_repair_slot_meta( self, blk->slot );
11 115929 : ulong idx = fd_repair_blk_pool_idx( self->blk_pool, blk );
12 115929 : fd_repair_treap_t * treap = meta->final_blk_idx==idx ? self->final_treap : meta->notar_blk_idx==idx ? self->notar_treap : self->eager_treap;
13 115929 : if( FD_UNLIKELY( fd_repair_treap_ele_query_const( treap, blk, self->blk_pool )==blk ) ) return 0;
14 62493 : if( FD_UNLIKELY( meta->final_blk_idx!=idx && meta->notar_blk_idx!=idx && meta->eager_blk_idx==idx && !blk->eager ) ) return 0;
15 62478 : fd_repair_treap_ele_insert( treap, blk, self->blk_pool );
16 62478 : return 1;
17 62493 : }
18 :
19 : static int
20 : blk_treap_remove( fd_repair_t * self,
21 16179 : fd_repair_blk_t * blk ) {
22 16179 : fd_repair_slot_meta_t const * meta = fd_repair_slot_meta( self, blk->slot );
23 16179 : ulong idx = fd_repair_blk_pool_idx( self->blk_pool, blk );
24 16179 : fd_repair_treap_t * treap = meta->final_blk_idx==idx ? self->final_treap : meta->notar_blk_idx==idx ? self->notar_treap : self->eager_treap;
25 16179 : if( FD_LIKELY( fd_repair_treap_ele_query_const( treap, blk, self->blk_pool )!=blk ) ) return 0;
26 16053 : fd_repair_treap_ele_remove( treap, blk, self->blk_pool );
27 16053 : return 1;
28 16179 : }
29 :
30 : static fd_repair_blk_t *
31 : blk_insert( fd_repair_t * self,
32 : ulong slot,
33 62337 : fd_mr32_t const * dmr ) {
34 62337 : FD_TEST( fd_repair_blk_pool_free( self->blk_pool ) );
35 62337 : fd_repair_slot_meta_t * meta = fd_repair_slot_meta( self, slot );
36 62337 : fd_repair_blk_t * blk = fd_repair_blk_pool_ele_acquire( self->blk_pool );
37 62337 : blk->slot = slot;
38 62337 : blk->dmr = *dmr;
39 62337 : blk->parent = fd_repair_blk_pool_idx_null( self->blk_pool );
40 62337 : blk->child = fd_repair_blk_pool_idx_null( self->blk_pool );
41 62337 : blk->sibling = fd_repair_blk_pool_idx_null( self->blk_pool );
42 62337 : blk->cmpl_fec_cnt = 0U;
43 62337 : blk->rcvd_fec_cnt = 0U;
44 62337 : blk->buff_fec_cnt = 0U;
45 62337 : blk->cons_fec_cnt = 0U;
46 62337 : blk->wait_fec_cnt = 0U;
47 62337 : blk->parent_slot = ULONG_MAX;
48 62337 : blk->parent_dmr = (fd_mr32_t){ { 0 } };
49 62337 : blk->init_fec_cnt = 0U;
50 62337 : blk->init_parent_slot = ULONG_MAX;
51 :
52 62337 : blk->eager = (!memcmp( dmr, &hash_null, sizeof(fd_mr32_t)) && !meta->invalidated && meta->final_blk_idx==fd_repair_blk_pool_idx_null( self->blk_pool ) && !meta->leader );
53 62337 : blk->meta_req = 0;
54 62337 : blk->highest_req = 0;
55 62337 : blk->orphan_req = 0;
56 62337 : memset( &blk->telemetry, 0, sizeof(blk->telemetry) );
57 62337 : blk->telemetry.last_cmpl_fec_idx = UINT_MAX;
58 62337 : blk->eager_ts = 0L;
59 31988097 : for( ulong k=0UL; k<self->fec_blk_max; k++ ) blk->fecs[ k ] = fd_repair_fec_pool_idx_null( self->fec_pool );
60 62337 : fd_repair_blk_map_ele_insert( self->blk_map, blk, self->blk_pool );
61 62337 : fd_repair_blk_orphan_map_ele_insert( self->orphan_map, blk, self->blk_pool );
62 62337 : if ( !memcmp( dmr, &hash_null, sizeof(fd_mr32_t) ) ) meta->eager_blk_idx = (uint)fd_repair_blk_pool_idx( self->blk_pool, blk );
63 61332 : else if( meta->notar_blk_idx==fd_repair_blk_pool_idx_null( self->blk_pool ) ) meta->notar_blk_idx = (uint)fd_repair_blk_pool_idx( self->blk_pool, blk );
64 62337 : fd_repair_blk_treap_insert( self, blk );
65 62337 : return blk;
66 62337 : }
67 :
68 : static void
69 : compute_dmr( fd_repair_t * self,
70 684 : fd_repair_blk_t * blk ) {
71 684 : uint fec_set_cnt = blk->cmpl_fec_cnt;
72 :
73 684 : uchar tree_mem[ FD_BMTREE_COMMIT_FOOTPRINT( 0UL ) ] __attribute__((aligned(FD_BMTREE_COMMIT_ALIGN)));
74 684 : fd_bmtree_commit_t * tree = fd_bmtree_commit_init( tree_mem, FD_SHRED_MERKLE_NODE_SZ, FD_BMTREE_LONG_PREFIX_SZ, 0UL );
75 7812 : for( uint k=0U; k<fec_set_cnt; k++ ) {
76 7128 : fd_bmtree_node_t leaf[1];
77 7128 : memcpy( leaf->hash, fd_repair_fec_pool_ele( self->fec_pool, blk->fecs[ k ] )->mr.mr32.uc, sizeof(fd_mr32_t) );
78 7128 : fd_bmtree_commit_append( tree, leaf, 1UL );
79 7128 : }
80 :
81 684 : fd_bmtree_node_t parent_info[1];
82 684 : fd_sha256_t sha[1];
83 684 : fd_sha256_init ( sha );
84 684 : fd_sha256_append( sha, &blk->parent_slot, sizeof(ulong) );
85 684 : fd_sha256_append( sha, blk->parent_dmr.uc, sizeof(fd_mr32_t) );
86 684 : fd_sha256_append( sha, &fec_set_cnt, sizeof(uint) );
87 684 : fd_sha256_fini ( sha, parent_info->hash );
88 684 : fd_bmtree_commit_append( tree, parent_info, 1UL );
89 :
90 684 : memcpy( blk->dmr.uc, fd_bmtree_commit_fini( tree ), sizeof(fd_mr32_t) );
91 684 : }
92 :
93 : static void
94 : consume( fd_repair_t * self,
95 192204 : fd_repair_blk_t * blk ) {
96 192204 : fd_repair_slot_meta_t const * meta = fd_repair_slot_meta( self, blk->slot );
97 192204 : if( FD_UNLIKELY( meta->invalidated && !memcmp( &blk->dmr, &hash_null, sizeof(fd_mr32_t) ) ) ) return;
98 192147 : if( FD_UNLIKELY( blk->parent==fd_repair_blk_pool_idx_null( self->blk_pool ) ) ) return; /* orphaned, even if partly consumed */
99 131202 : if( FD_UNLIKELY( blk->cons_fec_cnt<=blk->init_fec_cnt ) ) {
100 104781 : fd_repair_blk_t const * parent = fd_repair_blk_pool_ele_const( self->blk_pool, blk->parent );
101 104781 : if( FD_LIKELY( parent!=self->root_blk && ( !parent->cmpl_fec_cnt || parent->cons_fec_cnt!=parent->cmpl_fec_cnt ) ) ) return;
102 104781 : }
103 92646 : ulong idx = fd_repair_blk_pool_idx( self->blk_pool, blk );
104 92646 : fd_repair_blk_t * eager = fd_repair_blk_pool_ele( self->blk_pool, meta->eager_blk_idx );
105 92646 : if( FD_UNLIKELY( eager && meta->eager_blk_idx!=idx && !meta->invalidated && !memcmp( &eager->dmr, &hash_null, sizeof(fd_mr32_t) ) ) ) {
106 51 : int dup = eager->parent==blk->parent;
107 69 : for( uint k=blk->cons_fec_cnt; dup && k<blk->buff_fec_cnt; k++ ) dup = eager->fecs[ k ]==blk->fecs[ k ];
108 51 : if( FD_LIKELY( dup ) ) {
109 36 : blk = eager;
110 36 : idx = meta->eager_blk_idx;
111 36 : }
112 51 : }
113 :
114 92646 : if( FD_UNLIKELY( self->reconsume && blk->cons_fec_cnt<blk->buff_fec_cnt ) ) { /* replay evicted, need to specially redeliver from the root */
115 27 : self->reconsume = 0;
116 87 : for( fd_repair_blk_t * anc = blk; anc && anc!=self->root_blk; anc = fd_repair_blk_pool_ele( self->blk_pool, anc->parent ) ) {
117 114 : for( uint k=anc->cons_fec_cnt; k>anc->init_fec_cnt; k-- ) fd_repair_deque_push_head( self->reasm_deque, (fd_repair_deque_t){ .blk_idx = (uint)fd_repair_blk_pool_idx( self->blk_pool, anc ), .fec_idx = k-1U } );
118 60 : }
119 27 : }
120 92646 : if( FD_UNLIKELY( meta->leader && meta->eager_blk_idx==idx ) ) { /* our leader blk goes first, in FEC order */
121 33 : for( uint k=blk->buff_fec_cnt; k>blk->cons_fec_cnt; k-- ) fd_repair_deque_push_head( self->reasm_deque, (fd_repair_deque_t){ .blk_idx = (uint)idx, .fec_idx = k-1U } );
122 18 : blk->cons_fec_cnt = blk->buff_fec_cnt;
123 18 : return;
124 18 : }
125 160266 : for( ; blk->cons_fec_cnt<blk->buff_fec_cnt; blk->cons_fec_cnt++ ) fd_repair_deque_push_tail( self->reasm_deque, (fd_repair_deque_t){ .blk_idx = (uint)idx, .fec_idx = blk->cons_fec_cnt } );
126 92628 : }
127 :
128 : static void
129 : cascade( fd_repair_t * self,
130 32478 : fd_repair_blk_t * root ) {
131 32478 : fd_repair_blk_t * pool = self->blk_pool;
132 32478 : ulong null = fd_repair_blk_pool_idx_null( pool );
133 32478 : ulong tidx = fd_repair_blk_pool_idx( pool, root );
134 32478 : ulong idx = root->child;
135 42615 : while( FD_LIKELY( idx!=null ) ) {
136 33087 : fd_repair_blk_t * blk = fd_repair_blk_pool_ele( pool, idx );
137 33087 : consume( self, blk );
138 33087 : if( FD_LIKELY( blk->cmpl_fec_cnt && blk->cons_fec_cnt==blk->cmpl_fec_cnt && blk->child!=null ) ) { idx = blk->child; continue; }
139 56037 : while( FD_LIKELY( idx!=tidx && fd_repair_blk_pool_ele( pool, idx )->sibling==null ) ) idx = fd_repair_blk_pool_ele( pool, idx )->parent;
140 22989 : if( FD_UNLIKELY( idx==tidx ) ) break;
141 39 : idx = fd_repair_blk_pool_ele( pool, idx )->sibling;
142 39 : }
143 32478 : }
144 :
145 : static void
146 : promote( fd_repair_t * self,
147 : fd_repair_blk_t * blk,
148 168 : uint * role ) {
149 168 : if( FD_LIKELY( *role==fd_repair_blk_pool_idx( self->blk_pool, blk ) ) ) return;
150 153 : int queued = blk_treap_remove( self, blk );
151 153 : *role = (uint)fd_repair_blk_pool_idx( self->blk_pool, blk );
152 153 : blk->eager = 0;
153 153 : if( FD_LIKELY( queued ) ) fd_repair_blk_treap_insert( self, blk );
154 153 : }
155 :
156 : static fd_repair_blk_t *
157 : link_parent( fd_repair_t * self,
158 46473 : fd_repair_blk_t * blk ) {
159 46473 : fd_repair_blk_t * pool = self->blk_pool;
160 46473 : if( FD_UNLIKELY( blk->parent_slot==ULONG_MAX ) ) return NULL;
161 46473 : if( FD_UNLIKELY( blk->parent_slot!=self->root && !memcmp( &blk->parent_dmr, &hash_null, sizeof(fd_mr32_t) ) ) ) return NULL;
162 :
163 46467 : fd_repair_blk_t * parent = fd_repair_blk_map_ele_query( self->blk_map, &blk->parent_slot, NULL, pool );
164 46611 : while( parent && memcmp( &parent->dmr, &blk->parent_dmr, sizeof(fd_mr32_t) ) ) parent = (fd_repair_blk_t *)fd_repair_blk_map_ele_next_const( parent, NULL, pool );
165 46467 : if( FD_LIKELY( !parent ) ) return NULL;
166 :
167 46164 : if( FD_LIKELY( blk!=self->root_blk ) ) fd_repair_blk_orphan_map_ele_remove_fast( self->orphan_map, blk, pool );
168 :
169 46164 : blk->parent = fd_repair_blk_pool_idx( pool, parent );
170 46164 : blk->sibling = parent->child;
171 46164 : parent->child = fd_repair_blk_pool_idx( pool, blk );
172 46164 : return parent;
173 46467 : }
174 :
175 : static void
176 : link_ancestors( fd_repair_t * self,
177 45699 : fd_repair_blk_t * blk ) {
178 45699 : fd_repair_blk_t * pool = self->blk_pool;
179 45699 : ulong null = fd_repair_blk_pool_idx_null( pool );
180 45699 : fd_repair_blk_t * top = blk;
181 66042 : for(;;) {
182 66042 : if( FD_UNLIKELY( blk->parent_slot==ULONG_MAX || blk->parent_slot<self->root ) ) break;
183 20343 : if( FD_UNLIKELY( blk->parent_slot!=self->root && !memcmp( &blk->parent_dmr, &hash_null, sizeof(fd_mr32_t) ) ) ) break;
184 20343 : fd_repair_slot_meta_t * meta = fd_repair_slot_meta( self, blk->slot );
185 20343 : fd_repair_slot_meta_t * pmeta = fd_repair_slot_meta( self, blk->parent_slot );
186 20343 : int final = meta->final_blk_idx==fd_repair_blk_pool_idx( pool, blk );
187 20343 : int unlinked = blk->parent==null;
188 20343 : fd_repair_blk_t * parent = unlinked ? link_parent( self, blk ) : fd_repair_blk_pool_ele( pool, blk->parent );
189 20343 : if( FD_UNLIKELY( parent && unlinked ) ) top = blk;
190 20343 : if( FD_UNLIKELY( !parent ) ) {
191 12 : if( FD_UNLIKELY( blk->parent_slot==self->root ) ) break; /* names a root other than ours */
192 12 : parent = fd_repair_blk_notarized( self, blk->parent_slot, &blk->parent_dmr ); /* link_orphans links blk under it */
193 12 : if( FD_UNLIKELY( !parent ) ) break; /* the parent slot is settled otherwise */
194 12 : fd_repair_blk_treap_insert( self, blk ); /* its tile asks ORPHAN for eager ancestry, which may merge with the named parents */
195 12 : top = blk;
196 12 : }
197 20343 : if( FD_UNLIKELY( final && pmeta->final_blk_idx==null ) ) promote( self, parent, &pmeta->final_blk_idx );
198 20343 : blk = parent;
199 20343 : }
200 45699 : consume( self, top );
201 45699 : if( FD_UNLIKELY( top->cmpl_fec_cnt && top->cons_fec_cnt==top->cmpl_fec_cnt ) ) cascade( self, top );
202 45699 : }
203 :
204 : static void
205 : link_orphans( fd_repair_t * self,
206 46374 : fd_repair_blk_t * parent ) {
207 46374 : fd_repair_blk_t * pool = self->blk_pool;
208 46374 : ulong null = fd_repair_blk_pool_idx_null( pool );
209 46374 : fd_repair_slot_meta_t * pmeta = fd_repair_slot_meta( self, parent->slot );
210 46374 : fd_repair_blk_t * next;
211 46374 : for( fd_repair_blk_t * blk = fd_repair_blk_orphan_map_ele_query( self->orphan_map, &parent->dmr, NULL, pool );
212 46554 : blk;
213 46374 : blk = next ) {
214 180 : next = (fd_repair_blk_t *)fd_repair_blk_orphan_map_ele_next_const( blk, NULL, pool );
215 180 : if( FD_UNLIKELY( blk->parent_slot!=parent->slot ) ) continue;
216 177 : fd_repair_blk_orphan_map_ele_remove_fast( self->orphan_map, blk, pool );
217 177 : blk->parent = fd_repair_blk_pool_idx( pool, parent );
218 177 : blk->sibling = parent->child;
219 177 : parent->child = fd_repair_blk_pool_idx( pool, blk );
220 177 : if( FD_UNLIKELY( fd_repair_slot_meta( self, blk->slot )->final_blk_idx==fd_repair_blk_pool_idx( pool, blk ) && pmeta->final_blk_idx==null ) ) promote( self, parent, &pmeta->final_blk_idx );
221 177 : }
222 46374 : }
223 :
224 : static void
225 : unlink( fd_repair_t * self,
226 159 : fd_repair_blk_t * blk ) {
227 159 : fd_repair_blk_t * pool = self->blk_pool;
228 159 : ulong null = fd_repair_blk_pool_idx_null( pool );
229 159 : ulong idx = fd_repair_blk_pool_idx( pool, blk );
230 159 : if( FD_LIKELY( blk->parent!=null ) ) {
231 54 : ulong * link = &fd_repair_blk_pool_ele( pool, blk->parent )->child;
232 84 : while( *link!=idx ) link = &fd_repair_blk_pool_ele( pool, *link )->sibling;
233 54 : *link = blk->sibling;
234 54 : }
235 159 : ulong next;
236 201 : for( ulong c=blk->child; c!=null; c=next ) {
237 42 : fd_repair_blk_t * child = fd_repair_blk_pool_ele( pool, c );
238 42 : next = child->sibling;
239 42 : child->parent = null;
240 42 : child->sibling = null;
241 42 : if( FD_LIKELY( child!=self->root_blk ) ) fd_repair_blk_orphan_map_ele_insert( self->orphan_map, child, pool ); /* waits for blk's dmr again, should it be held again */
242 42 : }
243 159 : }
244 :
245 : static void
246 : prune( fd_repair_t * self,
247 84 : fd_repair_blk_t * blk ) {
248 84 : fd_repair_blk_t * pool = self->blk_pool;
249 84 : if( FD_UNLIKELY( !blk->telemetry.reported && self->telemetry.report ) ) self->telemetry.report( self->telemetry.ctx, blk );
250 43092 : for( ulong k=0UL; k<self->fec_blk_max; k++ ) {
251 43008 : if( FD_LIKELY( blk->fecs[ k ]==fd_repair_fec_pool_idx_null( self->fec_pool ) ) ) continue;
252 57 : int held = 0;
253 57 : for( fd_repair_blk_t const * other = fd_repair_blk_map_ele_query_const( self->blk_map, &blk->slot, NULL, pool );
254 159 : other && !held;
255 102 : other = fd_repair_blk_map_ele_next_const( other, NULL, pool ) ) {
256 102 : held = other!=blk && other->fecs[ k ]==blk->fecs[ k ];
257 102 : }
258 57 : if( FD_UNLIKELY( held ) ) continue;
259 36 : fd_repair_fec_t * fec = fd_repair_fec_pool_ele( self->fec_pool, blk->fecs[ k ] );
260 36 : fd_repair_fec_map_ele_remove_fast( self->fec_map, fec, self->fec_pool );
261 36 : fd_repair_fec_pool_ele_release ( self->fec_pool, fec );
262 36 : }
263 84 : unlink( self, blk );
264 84 : if( FD_UNLIKELY( blk!=self->root_blk && blk->parent==fd_repair_blk_pool_idx_null( pool ) ) ) fd_repair_blk_orphan_map_ele_remove_fast( self->orphan_map, blk, pool );
265 84 : blk_treap_remove( self, blk );
266 84 : fd_repair_slot_meta_t * meta = fd_repair_slot_meta( self, blk->slot );
267 84 : if( FD_UNLIKELY( meta->eager_blk_idx==fd_repair_blk_pool_idx( pool, blk ) ) ) meta->eager_blk_idx = (uint)fd_repair_blk_pool_idx_null( pool );
268 84 : if( FD_UNLIKELY( meta->notar_blk_idx==fd_repair_blk_pool_idx( pool, blk ) ) ) meta->notar_blk_idx = (uint)fd_repair_blk_pool_idx_null( pool );
269 84 : if( FD_UNLIKELY( meta->final_blk_idx==fd_repair_blk_pool_idx( pool, blk ) ) ) meta->final_blk_idx = (uint)fd_repair_blk_pool_idx_null( pool );
270 84 : fd_repair_blk_map_ele_remove_fast( self->blk_map, blk, pool );
271 84 : fd_repair_blk_pool_ele_release ( pool, blk );
272 84 : }
273 :
274 : /* dedup checks for a duplicate of eager among the notar blks. Only the
275 : eager blk can be duplicated, since notar blk DMRs are known a priori.
276 :
277 : Merge strategy if a duplicate is found:
278 : - eager is kept, notar is freed
279 : - eager inherits notar's children
280 : - eager takes notar's parent if it has none, as same DMR implies same
281 : parent
282 :
283 : Replay builds one bank for the block until then: consume holds notar
284 : behind eager, which delivers the FEC sets they share. */
285 :
286 : static void
287 : dedup( fd_repair_t * self,
288 : fd_repair_blk_t * eager,
289 684 : long ts ) {
290 684 : fd_repair_blk_t * pool = self->blk_pool;
291 684 : ulong null = fd_repair_blk_pool_idx_null( pool );
292 684 : ulong idx = fd_repair_blk_pool_idx( pool, eager );
293 :
294 684 : fd_repair_blk_t * notar = fd_repair_blk_map_ele_query( self->blk_map, &eager->slot, NULL, pool );
295 1416 : while( notar && ( notar==eager || memcmp( ¬ar->dmr, &eager->dmr, sizeof(fd_mr32_t) ) ) ) {
296 732 : notar = (fd_repair_blk_t *)fd_repair_blk_map_ele_next_const( notar, NULL, pool );
297 732 : }
298 684 : fd_repair_slot_meta_t * meta = fd_repair_slot_meta( self, eager->slot );
299 684 : if( FD_UNLIKELY( !notar && meta->final_blk_idx!=null ) ) {
300 3 : eager->telemetry.cancelled_ts = fd_long_if( !eager->telemetry.cancelled_reason, ts, eager->telemetry.cancelled_ts );
301 3 : eager->telemetry.cancelled_reason = (uchar)FD_EVENT_BLOCK_RECEIVED_CANCELLED_REASON_NOTARIZED_VERSION;
302 3 : prune( self, eager );
303 3 : return;
304 3 : } /* turbine built a blk the cluster did not finalize */
305 681 : if( FD_LIKELY( !notar ) ) return;
306 :
307 33 : ulong next;
308 54 : for( ulong c=notar->child; c!=null; c=next ) {
309 21 : next = fd_repair_blk_pool_ele( pool, c )->sibling;
310 21 : fd_repair_blk_pool_ele( pool, c )->parent = idx;
311 21 : fd_repair_blk_pool_ele( pool, c )->sibling = eager->child;
312 21 : eager->child = c;
313 21 : }
314 33 : notar->child = null;
315 33 : if( FD_UNLIKELY( notar->parent!=null && eager->parent==null ) ) {
316 0 : if( FD_LIKELY( eager!=self->root_blk ) ) fd_repair_blk_orphan_map_ele_remove_fast( self->orphan_map, eager, pool );
317 0 : eager->parent = notar->parent;
318 0 : eager->sibling = fd_repair_blk_pool_ele( pool, notar->parent )->child;
319 0 : fd_repair_blk_pool_ele( pool, notar->parent )->child = idx;
320 0 : }
321 33 : blk_treap_remove( self, notar );
322 33 : if( FD_UNLIKELY( meta->final_blk_idx==fd_repair_blk_pool_idx( pool, notar ) ) ) { meta->final_blk_idx = (uint)null; promote( self, eager, &meta->final_blk_idx ); }
323 33 : if( FD_UNLIKELY( meta->notar_blk_idx==fd_repair_blk_pool_idx( pool, notar ) ) ) { meta->notar_blk_idx = (uint)null; promote( self, eager, &meta->notar_blk_idx ); }
324 33 : notar->telemetry.reported = 1; /* the same block lives on as eager, we won't report two different lines for this */
325 :
326 33 : eager->telemetry.req_window_cnt += notar->telemetry.req_window_cnt;
327 33 : eager->telemetry.req_highest_cnt += notar->telemetry.req_highest_cnt;
328 33 : eager->telemetry.req_orphan_cnt += notar->telemetry.req_orphan_cnt;
329 33 : eager->telemetry.req_shred_bid_cnt += notar->telemetry.req_shred_bid_cnt;
330 33 : eager->telemetry.req_parent_cnt += notar->telemetry.req_parent_cnt;
331 33 : eager->telemetry.req_fec_root_cnt += notar->telemetry.req_fec_root_cnt;
332 33 : eager->telemetry.shred_res_cnt += notar->telemetry.shred_res_cnt;
333 33 : eager->telemetry.parent_res_cnt += notar->telemetry.parent_res_cnt;
334 33 : eager->telemetry.fec_root_res_cnt += notar->telemetry.fec_root_res_cnt;
335 : /* first timestamps */
336 33 : eager->telemetry.first_req_ts = fd_long_if( !eager->telemetry.first_req_ts || ( notar->telemetry.first_req_ts && notar->telemetry.first_req_ts <eager->telemetry.first_req_ts ), notar->telemetry.first_req_ts, eager->telemetry.first_req_ts );
337 33 : eager->telemetry.first_meta_res_ts = fd_long_if( !eager->telemetry.first_meta_res_ts || ( notar->telemetry.first_meta_res_ts && notar->telemetry.first_meta_res_ts<eager->telemetry.first_meta_res_ts ), notar->telemetry.first_meta_res_ts, eager->telemetry.first_meta_res_ts );
338 33 : eager->telemetry.last_shred_res_ts = fd_long_max( eager->telemetry.last_shred_res_ts, notar->telemetry.last_shred_res_ts );
339 33 : prune( self, notar );
340 33 : link_ancestors( self, eager );
341 33 : }
342 :
343 : static void
344 : update_parent( fd_repair_t * self,
345 : ulong slot,
346 : uint fec_idx,
347 384 : long ts ) {
348 384 : if( FD_UNLIKELY( !fec_idx || fec_idx>=self->fec_blk_max ) ) return;
349 384 : fd_repair_slot_meta_t * meta = fd_repair_slot_meta( self, slot );
350 384 : fd_repair_blk_t * pool = self->blk_pool;
351 384 : ulong null = fd_repair_blk_pool_idx_null( pool );
352 384 : fd_repair_blk_t * next;
353 792 : for( fd_repair_blk_t * blk = fd_repair_blk_map_ele_query( self->blk_map, &slot, NULL, pool ); blk; blk = next ) {
354 408 : next = (fd_repair_blk_t *)fd_repair_blk_map_ele_next_const( blk, NULL, pool );
355 :
356 408 : if( FD_LIKELY( blk->fecs[ fec_idx-1U ]==fd_repair_fec_pool_idx_null( self->fec_pool ) || blk->fecs[ fec_idx ]==fd_repair_fec_pool_idx_null( self->fec_pool ) ) ) continue;
357 198 : fd_repair_fec_t const * prev_fec = fd_repair_fec_pool_ele_const( self->fec_pool, blk->fecs[ fec_idx-1U ] );
358 198 : fd_repair_fec_t const * next_fec = fd_repair_fec_pool_ele_const( self->fec_pool, blk->fecs[ fec_idx ] );
359 :
360 198 : if( FD_LIKELY( !prev_fec->data_complete || next_fec->update_parent.new_parent_slot==ULONG_MAX ) ) continue;
361 186 : if( FD_UNLIKELY( blk->init_fec_cnt==fec_idx ) ) continue;
362 :
363 129 : fd_update_parent_t const * update = &next_fec->update_parent;
364 129 : int eager = meta->eager_blk_idx==fd_repair_blk_pool_idx( pool, blk );
365 129 : if( FD_UNLIKELY( eager && meta->invalidated ) ) continue;
366 :
367 129 : int bad = !fd_is_start_of_window( slot ) /* not in the first slot of its leader window */
368 129 : || blk->init_fec_cnt /* a second UpdateParent */
369 129 : || update->new_parent_slot<self->root /* a parent below the root */
370 129 : || update->new_parent_slot>=slot /* a parent newer than the header's */
371 129 : || ( eager && update->new_parent_slot>blk->init_parent_slot ) /* a parent newer than the header's */
372 129 : || !memcmp( &update->new_parent_block_id, &hash_null, sizeof(fd_mr32_t) ) /* a null parent block id */
373 129 : || ( eager && update->new_parent_slot==blk->parent_slot && !memcmp( &update->new_parent_block_id, &blk->parent_dmr, sizeof(fd_mr32_t) ) ); /* updating to the same thing */
374 :
375 : /* TODO: mark notarize blks invalid? */
376 129 : if( FD_UNLIKELY( bad && !eager ) ) { FD_LOG_WARNING(( "notarized blk at slot %lu has an invalid UpdateParent at fec set idx %u, ignoring it", slot, fec_idx*FD_FEC_SHRED_CNT )); continue; }
377 129 : if( FD_UNLIKELY( bad && eager ) ) { fd_repair_slot_invalidated( self, slot, FD_EVENT_BLOCK_RECEIVED_CANCELLED_REASON_INVALID_UPDATE_PARENT, ts ); continue; }
378 :
379 108 : if( FD_UNLIKELY( !eager ) ) {
380 12 : if( FD_UNLIKELY( blk->parent_slot!=ULONG_MAX && ( blk->parent_slot!=update->new_parent_slot || memcmp( &blk->parent_dmr, &update->new_parent_block_id, sizeof(fd_mr32_t) ) ) ) ) {
381 0 : FD_LOG_WARNING(( "notarized blk at slot %lu has an UpdateParent naming slot %lu, not its proven parent slot %lu, ignoring it", slot, update->new_parent_slot, blk->parent_slot ));
382 0 : continue;
383 0 : }
384 12 : blk->init_fec_cnt = fec_idx;
385 12 : blk->cons_fec_cnt = fd_uint_max( blk->cons_fec_cnt, fec_idx ); /* stream starts at the UpdateParent, prefix is skipped */
386 12 : continue;
387 12 : }
388 :
389 96 : if( FD_LIKELY( blk->parent!=null ) ) {
390 39 : ulong idx = fd_repair_blk_pool_idx( pool, blk );
391 39 : ulong * link = &fd_repair_blk_pool_ele( pool, blk->parent )->child;
392 39 : while( *link!=idx ) link = &fd_repair_blk_pool_ele( pool, *link )->sibling;
393 39 : *link = blk->sibling;
394 39 : blk->parent = null;
395 39 : blk->sibling = null;
396 57 : } else if( FD_LIKELY( blk!=self->root_blk ) ) {
397 57 : fd_repair_blk_orphan_map_ele_remove_fast( self->orphan_map, blk, pool );
398 57 : }
399 :
400 96 : blk->parent_slot = update->new_parent_slot;
401 96 : blk->parent_dmr = FD_LOAD( fd_mr32_t, update->new_parent_block_id.uc );
402 96 : blk->init_fec_cnt = fec_idx;
403 96 : blk->cons_fec_cnt = fd_uint_max( blk->cons_fec_cnt, fec_idx );
404 96 : blk->orphan_req = 0; /* an ORPHAN req for the header's parent is moot */
405 :
406 96 : fd_repair_blk_orphan_map_ele_insert( self->orphan_map, blk, pool ); /* under the new key, link_parent takes it out if the new parent is held */
407 96 : if( FD_UNLIKELY( link_parent( self, blk ) ) ) continue;
408 24 : fd_repair_slot_meta_t * pmeta = fd_repair_slot_meta( self, blk->parent_slot );
409 24 : if( FD_UNLIKELY( pmeta->eager_blk_idx==null && pmeta->final_blk_idx==null && !pmeta->skipped && !pmeta->invalidated ) ) blk_insert( self, blk->parent_slot, fd_type_pun_const( &hash_null ) ); /* seed the new parent slot's eager blk */
410 24 : fd_repair_blk_treap_insert( self, blk ); /* its tile asks ORPHAN for the new parent */
411 24 : }
412 384 : }
413 :
414 : FD_FN_CONST ulong
415 4827 : fd_repair_align( void ) {
416 4827 : return fd_ulong_max( alignof(fd_repair_t), 128UL );
417 4827 : }
418 :
419 : FD_FN_CONST ulong
420 : fd_repair_footprint( ulong slot_max,
421 : ulong fec_max,
422 876 : ulong fec_blk_max ) {
423 876 : ulong blk_max = ( 5UL*slot_max+1UL )/2UL;
424 876 : return FD_LAYOUT_FINI(
425 876 : FD_LAYOUT_APPEND(
426 876 : FD_LAYOUT_APPEND(
427 876 : FD_LAYOUT_APPEND(
428 876 : FD_LAYOUT_APPEND(
429 876 : FD_LAYOUT_APPEND(
430 876 : FD_LAYOUT_APPEND(
431 876 : FD_LAYOUT_APPEND(
432 876 : FD_LAYOUT_APPEND(
433 876 : FD_LAYOUT_APPEND(
434 876 : FD_LAYOUT_APPEND(
435 876 : FD_LAYOUT_APPEND(
436 876 : FD_LAYOUT_APPEND(
437 876 : FD_LAYOUT_INIT,
438 876 : fd_repair_align(), sizeof(fd_repair_t) ),
439 876 : alignof(fd_repair_slot_meta_t), sizeof(fd_repair_slot_meta_t)*slot_max ),
440 876 : fd_repair_blk_pool_align(), fd_repair_blk_pool_footprint ( blk_max ) ),
441 876 : alignof(ulong), sizeof(ulong)*blk_max*fec_blk_max ),
442 876 : fd_repair_blk_map_align(), fd_repair_blk_map_footprint ( fd_repair_blk_map_chain_cnt_est( blk_max ) ) ),
443 876 : fd_repair_blk_orphan_map_align(), fd_repair_blk_orphan_map_footprint( fd_repair_blk_orphan_map_chain_cnt_est( blk_max ) ) ),
444 876 : fd_repair_fec_pool_align(), fd_repair_fec_pool_footprint ( fec_max ) ),
445 876 : fd_repair_fec_map_align(), fd_repair_fec_map_footprint ( fd_repair_fec_map_chain_cnt_est( fec_max ) ) ),
446 876 : fd_repair_deque_align(), fd_repair_deque_footprint ( fec_max ) ),
447 876 : fd_repair_treap_align(), fd_repair_treap_footprint ( blk_max ) ),
448 876 : fd_repair_treap_align(), fd_repair_treap_footprint ( blk_max ) ),
449 876 : fd_repair_treap_align(), fd_repair_treap_footprint ( blk_max ) ),
450 876 : fd_repair_align() );
451 876 : }
452 :
453 : void *
454 : fd_repair_new( void * shmem,
455 : ulong slot_max,
456 : ulong fec_max,
457 : ulong fec_blk_max,
458 444 : ulong seed ) {
459 444 : ulong footprint = fd_repair_footprint( slot_max, fec_max, fec_blk_max );
460 444 : if( FD_UNLIKELY( !footprint || fec_blk_max<FD_FEC_BLK_MAX || fec_blk_max>UINT_MAX ) ) {
461 3 : FD_LOG_WARNING(( "bad footprint: %lu %lu %lu", slot_max, fec_max, fec_blk_max ));
462 3 : return NULL;
463 3 : }
464 :
465 441 : fd_memset( shmem, 0, footprint );
466 441 : fd_repair_t * repair;
467 :
468 441 : ulong blk_max = ( 5UL*slot_max+1UL )/2UL;
469 :
470 441 : FD_SCRATCH_ALLOC_INIT( l, shmem );
471 441 : repair = FD_SCRATCH_ALLOC_APPEND( l, fd_repair_align(), sizeof(fd_repair_t) );
472 441 : void * slot_meta = FD_SCRATCH_ALLOC_APPEND( l, alignof(fd_repair_slot_meta_t), sizeof(fd_repair_slot_meta_t)*slot_max );
473 441 : void * blk_pool = FD_SCRATCH_ALLOC_APPEND( l, fd_repair_blk_pool_align(), fd_repair_blk_pool_footprint ( blk_max ) );
474 441 : ulong * blk_fecs = FD_SCRATCH_ALLOC_APPEND( l, alignof(ulong), sizeof(ulong)*blk_max*fec_blk_max );
475 441 : void * blk_map = FD_SCRATCH_ALLOC_APPEND( l, fd_repair_blk_map_align(), fd_repair_blk_map_footprint ( fd_repair_blk_map_chain_cnt_est( blk_max ) ) );
476 441 : void * orphan_map = FD_SCRATCH_ALLOC_APPEND( l, fd_repair_blk_orphan_map_align(), fd_repair_blk_orphan_map_footprint( fd_repair_blk_orphan_map_chain_cnt_est( blk_max ) ) );
477 441 : void * fec_pool = FD_SCRATCH_ALLOC_APPEND( l, fd_repair_fec_pool_align(), fd_repair_fec_pool_footprint ( fec_max ) );
478 441 : void * fec_map = FD_SCRATCH_ALLOC_APPEND( l, fd_repair_fec_map_align(), fd_repair_fec_map_footprint ( fd_repair_fec_map_chain_cnt_est( fec_max ) ) );
479 441 : void * reasm_deque = FD_SCRATCH_ALLOC_APPEND( l, fd_repair_deque_align(), fd_repair_deque_footprint ( fec_max ) );
480 441 : void * eager_treap = FD_SCRATCH_ALLOC_APPEND( l, fd_repair_treap_align(), fd_repair_treap_footprint ( blk_max ) );
481 441 : void * notar_treap = FD_SCRATCH_ALLOC_APPEND( l, fd_repair_treap_align(), fd_repair_treap_footprint ( blk_max ) );
482 441 : void * final_treap = FD_SCRATCH_ALLOC_APPEND( l, fd_repair_treap_align(), fd_repair_treap_footprint ( blk_max ) );
483 441 : FD_TEST( FD_SCRATCH_ALLOC_FINI( l, fd_repair_align() ) == (ulong)shmem + footprint );
484 :
485 441 : repair->root = ULONG_MAX;
486 441 : repair->slot_max = slot_max;
487 441 : repair->fec_blk_max = fec_blk_max;
488 441 : repair->slot_meta = (fd_repair_slot_meta_t *)slot_meta;
489 7497 : for( ulong i=0UL; i<slot_max; i++ ) repair->slot_meta[ i ].slot = ULONG_MAX;
490 441 : repair->blk_pool = fd_repair_blk_pool_join ( fd_repair_blk_pool_new ( blk_pool, blk_max ) );
491 18081 : for( ulong i=0UL; i<blk_max; i++ ) repair->blk_pool[ i ].fecs = blk_fecs + i*fec_blk_max;
492 441 : repair->blk_map = fd_repair_blk_map_join ( fd_repair_blk_map_new ( blk_map, fd_repair_blk_map_chain_cnt_est( blk_max ), seed ) );
493 441 : repair->orphan_map = fd_repair_blk_orphan_map_join( fd_repair_blk_orphan_map_new( orphan_map, fd_repair_blk_orphan_map_chain_cnt_est( blk_max ), seed ) );
494 441 : repair->fec_pool = fd_repair_fec_pool_join ( fd_repair_fec_pool_new ( fec_pool, fec_max ) );
495 441 : repair->fec_map = fd_repair_fec_map_join ( fd_repair_fec_map_new ( fec_map, fd_repair_fec_map_chain_cnt_est( fec_max ), seed ) );
496 441 : repair->reasm_deque = fd_repair_deque_join ( fd_repair_deque_new ( reasm_deque, fec_max ) );
497 441 : fd_repair_treap_seed( repair->blk_pool, blk_max, seed ); /* the treaps share each blk's prio */
498 441 : repair->eager_treap = fd_repair_treap_join( fd_repair_treap_new( eager_treap, blk_max ) );
499 441 : repair->notar_treap = fd_repair_treap_join( fd_repair_treap_new( notar_treap, blk_max ) );
500 441 : repair->final_treap = fd_repair_treap_join( fd_repair_treap_new( final_treap, blk_max ) );
501 :
502 441 : return shmem;
503 441 : }
504 :
505 : fd_repair_t *
506 441 : fd_repair_join( void * shrepair ) {
507 441 : return (fd_repair_t *)shrepair;
508 441 : }
509 :
510 : void *
511 0 : fd_repair_leave( fd_repair_t const * self ) {
512 0 : return (void *)self;
513 0 : }
514 :
515 : void *
516 0 : fd_repair_delete( void * shrepair ) {
517 0 : return shrepair;
518 0 : }
519 :
520 : void
521 : fd_repair_init( fd_repair_t * self,
522 : ulong root,
523 : fd_mr32_t const * root_blk_mr,
524 : fd_repair_report_fn_t report,
525 15651 : void * report_ctx ) {
526 15651 : self->telemetry.report = report;
527 15651 : self->telemetry.ctx = report_ctx;
528 15651 : fd_repair_blk_t * blk = blk_insert( self, root, root_blk_mr );
529 15651 : blk->telemetry.reported = 1; /* the root is not a received block */
530 15651 : blk_treap_remove( self, blk ); /* the root is never repaired */
531 15651 : fd_repair_blk_orphan_map_ele_remove_fast( self->orphan_map, blk, self->blk_pool ); /* the root waits for nothing */
532 15651 : fd_repair_slot_meta( self, root )->final_blk_idx = (uint)fd_repair_blk_pool_idx( self->blk_pool, blk );
533 15651 : fd_repair_slot_meta( self, root )->eager_blk_idx = (uint)fd_repair_blk_pool_idx_null( self->blk_pool ); /* the genesis root has a null dmr, but is not turbine's */
534 15651 : blk->eager = 0;
535 15651 : self->root = root;
536 15651 : self->root_blk = blk;
537 15651 : self->catchup_slot = root;
538 15651 : }
539 :
540 : void
541 15330 : fd_repair_fini( fd_repair_t * self ) {
542 260610 : for( ulong i=0UL; i<self->slot_max; i++ ) self->slot_meta[ i ].slot = ULONG_MAX;
543 15330 : fd_repair_blk_map_reset( self->blk_map );
544 15330 : fd_repair_blk_orphan_map_reset( self->orphan_map );
545 15330 : fd_repair_blk_pool_reset( self->blk_pool );
546 15330 : fd_repair_fec_map_reset( self->fec_map );
547 15330 : fd_repair_fec_pool_reset( self->fec_pool );
548 15330 : fd_repair_deque_remove_all( self->reasm_deque );
549 15330 : self->eager_treap = fd_repair_treap_join( fd_repair_treap_new( fd_repair_treap_leave( self->eager_treap ), fd_repair_blk_pool_max( self->blk_pool ) ) );
550 15330 : self->notar_treap = fd_repair_treap_join( fd_repair_treap_new( fd_repair_treap_leave( self->notar_treap ), fd_repair_blk_pool_max( self->blk_pool ) ) );
551 15330 : self->final_treap = fd_repair_treap_join( fd_repair_treap_new( fd_repair_treap_leave( self->final_treap ), fd_repair_blk_pool_max( self->blk_pool ) ) );
552 15330 : self->root = ULONG_MAX;
553 15330 : self->root_blk = NULL;
554 15330 : self->catchup_slot = 0UL;
555 15330 : self->reconsume = 0;
556 15330 : }
557 :
558 : void
559 : fd_repair_blk_dead( fd_repair_t * self,
560 : ulong slot,
561 : fd_mr32_t const * blk_mr,
562 51 : uint latest_fec_idx ) {
563 51 : fd_repair_blk_t * dead = fd_repair_blk_map_ele_query( self->blk_map, &slot, NULL, self->blk_pool );
564 57 : while( dead && memcmp( &dead->dmr, blk_mr, sizeof(fd_mr32_t) ) ) dead = (fd_repair_blk_t *)fd_repair_blk_map_ele_next_const( dead, NULL, self->blk_pool );
565 51 : if( FD_UNLIKELY( !dead ) ) return;
566 :
567 51 : fd_repair_slot_meta_t * meta = fd_repair_slot_meta( self, slot );
568 51 : int eager = meta->eager_blk_idx==fd_repair_blk_pool_idx( self->blk_pool, dead );
569 51 : uint bound = dead->init_fec_cnt ? dead->init_fec_cnt*FD_FEC_SHRED_CNT : UINT_MAX; /* UINT_MAX latest_fec_idx (no FLH) is never a prefix */
570 51 : int prefix = eager && fd_is_start_of_window( slot ) && latest_fec_idx<bound;
571 51 : if( FD_UNLIKELY( prefix ) ) return; /* the optimistic prefix died, the block may still replay from an UpdateParent */
572 :
573 42 : blk_treap_remove( self, dead ); /* replay rejected it, no point repairing the rest */
574 42 : if( FD_LIKELY( !eager || meta->invalidated ) ) return;
575 :
576 15 : meta->invalidated = 1; /* turbine must not rebuild it */
577 15 : dead->eager = 0; /* never repaired by position */
578 15 : if( FD_LIKELY( dead->parent!=fd_repair_blk_pool_idx_null( self->blk_pool ) ) ) cascade( self, fd_repair_blk_pool_ele( self->blk_pool, dead->parent ) ); /* delivers the notar blks held behind it */
579 15 : }
580 :
581 : fd_repair_blk_t *
582 : fd_repair_blk_finalized( fd_repair_t * self,
583 : ulong slot,
584 : fd_mr32_t const * blk_mr,
585 78 : long ts ) {
586 78 : fd_repair_slot_meta_t * meta = fd_repair_slot_meta( self, slot );
587 78 : fd_repair_blk_t const * existing_final = fd_repair_blk_pool_ele_const( self->blk_pool, meta->final_blk_idx );
588 78 : FD_CHECK_CRIT( !existing_final || !memcmp( &existing_final->dmr, blk_mr, sizeof(fd_mr32_t) ), "consensus safety violation" );
589 :
590 78 : fd_repair_blk_t * final = fd_repair_blk_map_ele_query( self->blk_map, &slot, NULL, self->blk_pool );
591 96 : while( final && memcmp( &final->dmr, blk_mr, sizeof(fd_mr32_t) ) ) final = (fd_repair_blk_t *)fd_repair_blk_map_ele_next_const( final, NULL, self->blk_pool );
592 78 : if( FD_UNLIKELY( !final ) ) final = fd_repair_blk_notarized( self, slot, blk_mr );
593 78 : if( FD_UNLIKELY( !final ) ) return NULL;
594 :
595 75 : fd_repair_blk_t * pool = self->blk_pool;
596 75 : promote( self, final, &meta->final_blk_idx );
597 : /* The eager blk keeps its positional repair: peers without the whole
598 : block still serve its shreds, which by-id repair cannot ask them for. */
599 :
600 : /* Remove all equivocating blocks except the finalized one. Their
601 : children name them, not the finalized blk, and are unlinked. */
602 :
603 75 : fd_repair_blk_t * next;
604 75 : for( fd_repair_blk_t * blk = fd_repair_blk_map_ele_query( self->blk_map, &slot, NULL, pool );
605 183 : blk;
606 108 : blk = next ) {
607 108 : next = (fd_repair_blk_t *)fd_repair_blk_map_ele_next_const( blk, NULL, pool );
608 108 : if( FD_LIKELY( blk==final ) ) continue;
609 33 : if( FD_UNLIKELY( meta->eager_blk_idx==fd_repair_blk_pool_idx( pool, blk ) && !meta->invalidated && !memcmp( &blk->dmr, &hash_null, sizeof(fd_mr32_t) ) ) ) continue; /* turbine may still complete as the finalized blk, see dedup */
610 24 : blk->telemetry.cancelled_ts = fd_long_if( !blk->telemetry.cancelled_reason, ts, blk->telemetry.cancelled_ts );
611 24 : blk->telemetry.cancelled_reason = (uchar)fd_int_if( !blk->telemetry.cancelled_reason, FD_EVENT_BLOCK_RECEIVED_CANCELLED_REASON_NOTARIZED_VERSION, blk->telemetry.cancelled_reason ); /* an invalidated eager blk keeps its reason */
612 24 : prune( self, blk );
613 24 : }
614 75 : link_ancestors( self, final );
615 75 : return final;
616 78 : }
617 :
618 : fd_repair_blk_t *
619 : fd_repair_blk_notarized( fd_repair_t * self,
620 : ulong slot,
621 45759 : fd_mr32_t const * blk_mr ) {
622 45759 : fd_repair_slot_meta_t * meta = fd_repair_slot_meta( self, slot );
623 45759 : if( FD_UNLIKELY( !memcmp( blk_mr, &hash_null, sizeof(fd_mr32_t) ) ) ) return NULL; /* never a real blk id, only turbine makes an eager blk */
624 45759 : if( FD_UNLIKELY( meta->final_blk_idx!=fd_repair_blk_pool_idx_null( self->blk_pool ) || meta->skipped ) ) return NULL; /* the slot is settled */
625 45738 : for( fd_repair_blk_t * dup = fd_repair_blk_map_ele_query( self->blk_map, &slot, NULL, self->blk_pool );
626 45849 : dup;
627 45738 : dup = (fd_repair_blk_t *)fd_repair_blk_map_ele_next_const( dup, NULL, self->blk_pool ) ) {
628 159 : if( FD_UNLIKELY( memcmp( &dup->dmr, blk_mr, sizeof(fd_mr32_t) ) ) ) continue;
629 48 : if( FD_LIKELY( meta->notar_blk_idx==fd_repair_blk_pool_idx_null( self->blk_pool ) ) ) promote( self, dup, &meta->notar_blk_idx ); /* already have it, now named */
630 48 : link_ancestors( self, dup );
631 48 : return NULL;
632 159 : }
633 45690 : fd_repair_blk_t * blk = blk_insert( self, slot, blk_mr );
634 45690 : link_orphans( self, blk );
635 45690 : return blk;
636 45738 : }
637 :
638 : fd_repair_blk_t *
639 : fd_repair_blk_parented( fd_repair_t * self,
640 : ulong slot,
641 : fd_mr32_t const * blk_mr,
642 : ulong parent_slot,
643 : fd_mr32_t const * parent_dmr,
644 : uint fec_set_cnt,
645 45594 : long ts ) {
646 45594 : fd_repair_blk_t * blk = fd_repair_blk_map_ele_query( self->blk_map, &slot, NULL, self->blk_pool );
647 45603 : while( FD_LIKELY( blk && memcmp( &blk->dmr, blk_mr, sizeof(fd_mr32_t) ) ) ) blk = (fd_repair_blk_t *)fd_repair_blk_map_ele_next_const( blk, NULL, self->blk_pool );
648 45594 : if( FD_UNLIKELY( !blk ) ) return NULL; /* blk was pruned while the response was in flight */
649 45591 : blk->telemetry.parent_res_cnt++;
650 45591 : blk->telemetry.first_meta_res_ts = fd_long_if( !blk->telemetry.first_meta_res_ts, ts, blk->telemetry.first_meta_res_ts );
651 :
652 45591 : if( FD_UNLIKELY( blk->parent_slot!=ULONG_MAX ) ) return NULL; /* duplicate response, eg. a retried request */
653 45582 : if( FD_UNLIKELY( parent_slot>=slot ) ) return NULL; /* a blk's parent precedes it */
654 :
655 45576 : int orphan = blk!=self->root_blk && blk->parent==fd_repair_blk_pool_idx_null( self->blk_pool );
656 45576 : if( FD_LIKELY( orphan ) ) fd_repair_blk_orphan_map_ele_remove_fast( self->orphan_map, blk, self->blk_pool );
657 45576 : blk->parent_slot = parent_slot;
658 45576 : blk->parent_dmr = *parent_dmr;
659 45576 : blk->cmpl_fec_cnt = fec_set_cnt;
660 45576 : if( FD_LIKELY( orphan ) ) fd_repair_blk_orphan_map_ele_insert( self->orphan_map, blk, self->blk_pool ); /* under the named parent, link_parent takes it out if the parent is held */
661 45576 : fd_repair_blk_treap_insert( self, blk ); /* its FEC sets can be discovered now */
662 :
663 45576 : fd_repair_blk_t * parent = link_parent( self, blk );
664 45576 : fd_repair_blk_t * created = NULL;
665 45576 : if( FD_LIKELY( !parent ) ) parent = created = fd_repair_blk_notarized( self, parent_slot, parent_dmr ); /* links the child blks naming it */
666 45576 : if( FD_LIKELY( parent ) ) {
667 45564 : if( FD_UNLIKELY( fd_repair_slot_meta( self, slot )->final_blk_idx==fd_repair_blk_pool_idx( self->blk_pool, blk ) ) ) promote( self, parent, &fd_repair_slot_meta( self, parent_slot )->final_blk_idx ); /* finalized ancestry */
668 45564 : consume( self, blk );
669 45564 : if( FD_UNLIKELY( blk->cmpl_fec_cnt && blk->cons_fec_cnt==blk->cmpl_fec_cnt ) ) cascade( self, blk );
670 45564 : if( FD_LIKELY( !created ) ) link_ancestors( self, parent ); /* a held parent may itself be orphaned */
671 45564 : }
672 45576 : return created;
673 45582 : }
674 :
675 : void
676 : fd_repair_slot_catchup( fd_repair_t * self,
677 21 : ulong slot ) {
678 81 : for( ulong s=fd_ulong_max( self->root+1UL, self->catchup_slot ); s<slot; s++ ) {
679 60 : fd_repair_slot_meta_t * meta = fd_repair_slot_meta( self, s );
680 60 : if( FD_UNLIKELY( meta->skipped || meta->invalidated || meta->final_blk_idx!=fd_repair_blk_pool_idx_null( self->blk_pool ) || meta->eager_blk_idx!=fd_repair_blk_pool_idx_null( self->blk_pool ) ) ) continue;
681 48 : meta->eager_blk_idx = (uint)fd_repair_blk_pool_idx( self->blk_pool, blk_insert( self, s, fd_type_pun_const( &hash_null ) ) );
682 48 : }
683 21 : self->catchup_slot = fd_ulong_max( self->catchup_slot, slot );
684 21 : }
685 :
686 : fd_repair_fec_t *
687 : fd_repair_fec_complete( fd_repair_t * self,
688 : fd_shred_t const * last_shred,
689 : fd_mr32_t const * fec_mr,
690 : int is_leader,
691 : uint turbine_cnt,
692 : uint repair_cnt,
693 : uint recovered_cnt,
694 : uint data_rcvd,
695 : uint parity_rcvd,
696 : uint repair_rcvd,
697 67797 : long ts ) {
698 67797 : fd_repair_shred_insert( self, last_shred, fec_mr, ts ); /* the last shred's header */
699 :
700 67797 : fd_mr_t key;
701 67797 : memcpy( key.mr32.uc, fec_mr->uc, sizeof(fd_mr32_t) );
702 67797 : fd_repair_fec_t * fec = fd_repair_fec_map_ele_query( self->fec_map, &key, NULL, self->fec_pool );
703 67797 : if( FD_UNLIKELY( !fec ) ) return NULL; /* fd_repair_shred_insert dropped it as conflicting with the eager blk */
704 :
705 67773 : int first_complete = !fec->fec_complete;
706 67773 : fec->cmpl_ts = fd_long_if( first_complete, ts, fec->cmpl_ts );
707 67773 : fec->data_rcvd = fd_uint_if( first_complete, data_rcvd, fec->data_rcvd );
708 67773 : fec->parity_rcvd = fd_uint_if( first_complete, parity_rcvd, fec->parity_rcvd );
709 67773 : fec->repair_rcvd = fd_uint_if( first_complete, repair_rcvd, fec->repair_rcvd );
710 67773 : fec->mr = key;
711 67773 : fec->fec_complete = 1;
712 67773 : fec->data_complete = !!( last_shred->data.flags & FD_SHRED_DATA_FLAG_DATA_COMPLETE );
713 67773 : fec->is_leader |= !!is_leader; /* a completion again from the network does not clear our own */
714 :
715 67773 : ulong slot = last_shred->slot; /* fd_shred_t is packed, the map query needs an aligned key */
716 67773 : fd_repair_slot_meta_t * meta = fd_repair_slot_meta( self, slot );
717 67773 : fd_repair_blk_t * pool = self->blk_pool;
718 67773 : fd_repair_blk_t * eager = fd_repair_blk_pool_ele( pool, meta->eager_blk_idx );
719 67773 : int cmpl = eager && !meta->invalidated && eager->cmpl_fec_cnt && !memcmp( &eager->dmr, &hash_null, sizeof(fd_mr32_t) );
720 75015 : for( uint k=0U; cmpl && k<eager->cmpl_fec_cnt; k++ ) {
721 7242 : cmpl = eager->fecs[ k ]!=fd_repair_fec_pool_idx_null( self->fec_pool ) && fd_repair_fec_pool_ele( self->fec_pool, eager->fecs[ k ] )->fec_complete;
722 7242 : }
723 67773 : meta->leader |= (uint)!!is_leader;
724 67773 : if( FD_UNLIKELY( is_leader && eager ) ) eager->eager = 0; /* our own, never repaired */
725 67773 : if( FD_UNLIKELY( is_leader && eager && meta->final_blk_idx!=meta->eager_blk_idx && meta->notar_blk_idx!=meta->eager_blk_idx ) ) blk_treap_remove( self, eager );
726 67773 : if( FD_UNLIKELY( cmpl ) ) {
727 684 : compute_dmr( self, eager );
728 684 : link_orphans( self, eager ); /* the blks naming its dmr waited for it */
729 684 : dedup( self, eager, ts );
730 684 : if( FD_UNLIKELY( fd_repair_fec_map_ele_query( self->fec_map, &key, NULL, self->fec_pool )!=fec ) ) return NULL; /* dedup pruned eager and with it the FEC set */
731 684 : }
732 :
733 67770 : for( fd_repair_blk_t * blk = fd_repair_blk_map_ele_query( self->blk_map, &slot, NULL, pool );
734 135669 : blk;
735 67899 : blk = (fd_repair_blk_t *)fd_repair_blk_map_ele_next_const( blk, NULL, pool ) ) {
736 67899 : if( FD_LIKELY( blk->fecs[ fec->fec_idx ]!=fd_repair_fec_pool_idx( self->fec_pool, fec ) ) ) continue;
737 67845 : uint end = fd_uint_if( !!blk->cmpl_fec_cnt, blk->cmpl_fec_cnt, (uint)self->fec_blk_max );
738 135678 : while( blk->buff_fec_cnt<end
739 135678 : && blk->fecs[ blk->buff_fec_cnt ]!=fd_repair_fec_pool_idx_null( self->fec_pool )
740 135678 : && fd_repair_fec_pool_ele( self->fec_pool, blk->fecs[ blk->buff_fec_cnt ] )->fec_complete ) {
741 67833 : blk->buff_fec_cnt++;
742 67833 : }
743 67845 : if( FD_LIKELY( first_complete ) ) {
744 67839 : blk->telemetry.turbine_shred_cnt += turbine_cnt;
745 67839 : blk->telemetry.repair_shred_cnt += repair_cnt;
746 67839 : blk->telemetry.recovered_shred_cnt += recovered_cnt;
747 67839 : blk->telemetry.last_cmpl_fec_idx = fec->fec_idx*FD_FEC_SHRED_CNT;
748 67839 : }
749 67845 : blk->telemetry.last_shred_ts = fd_long_if( blk->cmpl_fec_cnt && blk->buff_fec_cnt==blk->cmpl_fec_cnt && !blk->telemetry.last_shred_ts, ts, blk->telemetry.last_shred_ts );
750 67845 : if( FD_UNLIKELY( blk->cmpl_fec_cnt && blk->buff_fec_cnt==blk->cmpl_fec_cnt && !blk->telemetry.reported && self->telemetry.report ) ) { blk->telemetry.reported = 1; self->telemetry.report( self->telemetry.ctx, blk ); }
751 67845 : consume( self, blk );
752 67845 : if( FD_UNLIKELY( blk->cmpl_fec_cnt && blk->cons_fec_cnt==blk->cmpl_fec_cnt ) ) cascade( self, blk );
753 67845 : }
754 67770 : return fec;
755 67773 : }
756 :
757 : void
758 : fd_repair_fec_evicted( fd_repair_t * self,
759 : ulong slot,
760 : uint fec_set_idx,
761 3 : fd_mr_t const * fec_mr ) {
762 3 : uint k = fec_set_idx/FD_FEC_SHRED_CNT;
763 3 : fd_repair_fec_t * fec = fd_repair_fec_map_ele_query( self->fec_map, fec_mr, NULL, self->fec_pool );
764 3 : if( FD_UNLIKELY( !fec || fec->fec_complete || fec->slot!=slot || fec->fec_idx!=k ) ) return;
765 :
766 3 : fec->data_rcvd = 0U; /* its req, still waiting since the set is incomplete, asks for every shred again */
767 3 : }
768 :
769 : fd_repair_fec_t *
770 : fd_repair_fec_notarized( fd_repair_t * self,
771 : ulong slot,
772 : fd_mr32_t const * blk_mr,
773 : uint fec_set_idx,
774 : fd_mr_t const * fec_mr,
775 60729 : long ts ) {
776 :
777 60729 : uint fec_idx = fec_set_idx / FD_FEC_SHRED_CNT;
778 :
779 60729 : fd_repair_blk_t * blk = fd_repair_blk_map_ele_query( self->blk_map, &slot, NULL, self->blk_pool );
780 60753 : while( blk && memcmp( &blk->dmr, blk_mr, sizeof(fd_mr32_t) ) ) blk = (fd_repair_blk_t *)fd_repair_blk_map_ele_next_const( blk, NULL, self->blk_pool );
781 60729 : if( FD_UNLIKELY( !blk ) ) return NULL; /* blk was pruned while the response was in flight */
782 60726 : blk->telemetry.fec_root_res_cnt++;
783 60726 : blk->telemetry.first_meta_res_ts = fd_long_if( !blk->telemetry.first_meta_res_ts, ts, blk->telemetry.first_meta_res_ts );
784 :
785 60726 : if( FD_UNLIKELY( blk->fecs[ fec_idx ]!=fd_repair_fec_pool_idx_null( self->fec_pool ) ) ) return NULL; /* duplicate response, eg. a retried request */
786 :
787 60723 : fd_repair_slot_meta_t * meta = fd_repair_slot_meta( self, slot );
788 60723 : fd_repair_blk_t * eager = fd_repair_blk_pool_ele( self->blk_pool, meta->eager_blk_idx );
789 60723 : int eqvoc = eager && eager->fecs[ fec_idx ]!=fd_repair_fec_pool_idx_null( self->fec_pool ) && memcmp( &fd_repair_fec_pool_ele( self->fec_pool, eager->fecs[ fec_idx ] )->mr.mr20, &fec_mr->mr20, sizeof(fd_mr20_t) );
790 60723 : if( FD_UNLIKELY( eqvoc ) ) fd_repair_slot_invalidated( self, slot, FD_EVENT_BLOCK_RECEIVED_CANCELLED_REASON_MERKLE_ROOT_MISMATCH, ts );
791 :
792 60723 : fd_repair_fec_t * fec = fd_repair_fec_map_ele_query( self->fec_map, fec_mr, NULL, self->fec_pool );
793 60723 : if( FD_UNLIKELY( fec && ( fec->slot!=slot || fec->fec_idx!=fec_idx ) ) ) return NULL; /* a FEC set root commits to its slot and index, so this leaf names no FEC set a shred can fill */
794 60714 : if( FD_UNLIKELY( !fec ) ) {
795 60684 : FD_TEST( fd_repair_fec_pool_free( self->fec_pool ) );
796 60684 : fec = fd_repair_fec_pool_ele_acquire( self->fec_pool );
797 60684 : fec->mr = *fec_mr;
798 60684 : fec->fec_idx = fec_idx;
799 60684 : fec->slot = slot;
800 60684 : fec->fec_complete = 0;
801 60684 : fec->data_complete = 0;
802 60684 : fec->first_ts = 0L;
803 60684 : fec->cmpl_ts = 0L;
804 60684 : fec->is_leader = 0;
805 60684 : fec->data_rcvd = 0U;
806 60684 : fec->parity_rcvd = 0U;
807 60684 : fec->repair_rcvd = 0U;
808 60684 : fec->update_parent.new_parent_slot = ULONG_MAX;
809 60684 : fd_repair_fec_map_ele_insert( self->fec_map, fec, self->fec_pool );
810 60684 : }
811 60714 : fec->is_notar = 1;
812 60714 : blk->fecs[ fec_idx ] = fd_repair_fec_pool_idx( self->fec_pool, fec );
813 :
814 60714 : if( FD_UNLIKELY( fec->update_parent.new_parent_slot!=ULONG_MAX ) ) update_parent( self, slot, fec_idx, ts );
815 60714 : if( FD_UNLIKELY( fec->data_complete ) ) update_parent( self, slot, fec_idx+1U, ts );
816 :
817 60714 : if( FD_LIKELY( !fec->fec_complete ) ) return fec;
818 :
819 9 : uint end = fd_uint_if( !!blk->cmpl_fec_cnt, blk->cmpl_fec_cnt, (uint)self->fec_blk_max );
820 18 : while( blk->buff_fec_cnt<end
821 18 : && blk->fecs[ blk->buff_fec_cnt ]!=fd_repair_fec_pool_idx_null( self->fec_pool )
822 18 : && fd_repair_fec_pool_ele( self->fec_pool, blk->fecs[ blk->buff_fec_cnt ] )->fec_complete ) {
823 9 : blk->buff_fec_cnt++;
824 9 : }
825 9 : if( FD_UNLIKELY( blk->cmpl_fec_cnt && blk->buff_fec_cnt==blk->cmpl_fec_cnt && !blk->telemetry.reported && self->telemetry.report ) ) { blk->telemetry.reported = 1; self->telemetry.report( self->telemetry.ctx, blk ); }
826 9 : consume( self, blk );
827 9 : if( FD_UNLIKELY( blk->cmpl_fec_cnt && blk->cons_fec_cnt==blk->cmpl_fec_cnt ) ) cascade( self, blk );
828 9 : return fec;
829 60714 : }
830 :
831 : void
832 : fd_repair_root_advanced( fd_repair_t * self,
833 : ulong slot,
834 33 : fd_mr32_t const * blk_mr ) {
835 33 : fd_repair_slot_meta_t const * meta = &self->slot_meta[ slot % self->slot_max ];
836 33 : fd_repair_blk_t const * existing_final = meta->slot==slot ? fd_repair_blk_pool_ele_const( self->blk_pool, meta->final_blk_idx ) : NULL;
837 33 : FD_CHECK_CRIT( !existing_final || !memcmp( &existing_final->dmr, blk_mr, sizeof(fd_mr32_t) ), "consensus safety violation" );
838 :
839 33 : ulong root = self->root;
840 33 : fd_repair_blk_t * root_blk = NULL; /* the new root, if held. self->root_blk is the old root until freed below: it left orphan_map on becoming root and must not be removed again */
841 135 : for( ulong s=root; s<=slot; s++ ) {
842 102 : fd_repair_blk_t * next;
843 102 : for( fd_repair_blk_t * blk = fd_repair_blk_map_ele_query( self->blk_map, &s, NULL, self->blk_pool );
844 207 : blk;
845 105 : blk = next ) {
846 105 : next = (fd_repair_blk_t *)fd_repair_blk_map_ele_next_const( blk, NULL, self->blk_pool );
847 105 : if( FD_UNLIKELY( !blk->telemetry.reported && self->telemetry.report ) ) { blk->telemetry.reported = 1; self->telemetry.report( self->telemetry.ctx, blk ); }
848 53865 : for( ulong k=0UL; k<self->fec_blk_max; k++ ) {
849 53760 : ulong idx = blk->fecs[ k ];
850 53760 : blk->fecs[ k ] = fd_repair_fec_pool_idx_null( self->fec_pool );
851 53760 : if( FD_LIKELY( idx==fd_repair_fec_pool_idx_null( self->fec_pool ) ) ) continue;
852 30 : fd_repair_fec_t * fec = fd_repair_fec_pool_ele( self->fec_pool, idx );
853 30 : if( FD_LIKELY( fd_repair_fec_map_ele_query( self->fec_map, &fec->mr, NULL, self->fec_pool )!=fec ) ) continue; /* freed through a sibling */
854 30 : fd_repair_fec_map_ele_remove_fast( self->fec_map, fec, self->fec_pool );
855 30 : fd_repair_fec_pool_ele_release ( self->fec_pool, fec );
856 30 : }
857 105 : if( FD_UNLIKELY( s==slot && !memcmp( &blk->dmr, blk_mr, sizeof(fd_mr32_t) ) ) ) { /* the new root */
858 30 : blk_treap_remove( self, blk ); /* the root is never repaired */
859 30 : if( FD_LIKELY( blk!=self->root_blk && blk->parent==fd_repair_blk_pool_idx_null( self->blk_pool ) ) ) fd_repair_blk_orphan_map_ele_remove_fast( self->orphan_map, blk, self->blk_pool ); /* its parent was just freed, the root waits for nothing */
860 30 : fd_repair_slot_meta( self, slot )->final_blk_idx = (uint)fd_repair_blk_pool_idx( self->blk_pool, blk );
861 30 : blk->eager = 0;
862 30 : root_blk = blk;
863 30 : continue;
864 30 : }
865 :
866 75 : unlink( self, blk );
867 75 : if( FD_UNLIKELY( blk!=self->root_blk && blk->parent==fd_repair_blk_pool_idx_null( self->blk_pool ) ) ) fd_repair_blk_orphan_map_ele_remove_fast( self->orphan_map, blk, self->blk_pool );
868 75 : blk_treap_remove( self, blk );
869 75 : fd_repair_slot_meta_t * meta = fd_repair_slot_meta( self, s );
870 75 : if( FD_UNLIKELY( meta->eager_blk_idx==fd_repair_blk_pool_idx( self->blk_pool, blk ) ) ) meta->eager_blk_idx = (uint)fd_repair_blk_pool_idx_null( self->blk_pool ); /* the root slot's meta stays live, its roles must not name freed blks */
871 75 : if( FD_UNLIKELY( meta->notar_blk_idx==fd_repair_blk_pool_idx( self->blk_pool, blk ) ) ) meta->notar_blk_idx = (uint)fd_repair_blk_pool_idx_null( self->blk_pool );
872 75 : fd_repair_blk_map_ele_remove_fast( self->blk_map, blk, self->blk_pool );
873 75 : fd_repair_blk_pool_ele_release ( self->blk_pool, blk );
874 75 : }
875 102 : }
876 33 : self->root_blk = root_blk;
877 33 : self->root = slot;
878 33 : }
879 :
880 : void
881 : fd_repair_shred_insert( fd_repair_t * self,
882 : fd_shred_t const * shred,
883 : fd_mr32_t const * fec_mr,
884 68955 : long ts ) {
885 :
886 68955 : fd_mr_t key;
887 68955 : memcpy( key.mr32.uc, fec_mr->uc, sizeof(fd_mr32_t) );
888 :
889 : /* First, handle a Notar shred (shred for a FEC set that has already
890 : reached a notarized status ie. SafeToNotar or stronger). It also
891 : belongs to the eager blk, so fall through. */
892 :
893 68955 : fd_repair_fec_t * fec = fd_repair_fec_map_ele_query( self->fec_map, &key, NULL, self->fec_pool );
894 68955 : uint fec_idx = shred->idx / FD_FEC_SHRED_CNT;
895 68955 : if( FD_UNLIKELY( fec && ( fec->slot!=shred->slot || fec->fec_idx!=fec_idx ) ) ) return; /* a 20-byte root collision */
896 68955 : if( FD_UNLIKELY( fec && fec->is_notar && !fec->fec_complete ) ) fec->data_rcvd = fd_uint_set_bit( fec->data_rcvd, (int)( shred->idx - fec_idx * FD_FEC_SHRED_CNT ) );
897 68955 : if( FD_UNLIKELY( fec && !fec->first_ts ) ) fec->first_ts = ts;
898 :
899 68955 : fd_block_marker_t update[1];
900 68955 : int parent_update = shred->idx%FD_FEC_SHRED_CNT==0U && shred->idx && !fd_block_marker_de( update, fd_shred_data_payload( shred ), fd_shred_payload_sz( shred ) ) && update->kind==FD_BLOCK_MARKER_KIND_UPDATE_PARENT;
901 68955 : int data_complete = !!( shred->data.flags & FD_SHRED_DATA_FLAG_DATA_COMPLETE );
902 :
903 68955 : if( FD_UNLIKELY( parent_update && fec ) ) { fec->update_parent = update->update_parent; update_parent( self, shred->slot, fec_idx, ts ); }
904 68955 : if( FD_UNLIKELY( data_complete && fec ) ) { fec->data_complete = 1; update_parent( self, shred->slot, fec_idx+1U, ts ); }
905 :
906 : /* Second, handle an Eager shred (from Turbine or Eager Repair). */
907 :
908 68955 : ulong parent_slot = shred->slot - shred->data.parent_off;
909 68955 : fd_repair_blk_t * pool = self->blk_pool;
910 68955 : ulong null = fd_repair_blk_pool_idx_null( pool );
911 68955 : fd_repair_slot_meta_t * meta = fd_repair_slot_meta( self, shred->slot );
912 68955 : fd_repair_blk_t const * fin = fd_repair_blk_pool_ele_const( pool, meta->final_blk_idx );
913 68955 : int fin_done = fin && fin->cmpl_fec_cnt && fin->buff_fec_cnt==fin->cmpl_fec_cnt;
914 :
915 68955 : if( FD_UNLIKELY( meta->skipped || meta->invalidated || ( fin_done && meta->eager_blk_idx==null ) ) ) return; /* a final cert ahead of turbine still lets turbine build the blk, dedup merges it */
916 8322 : if( FD_UNLIKELY( meta->eager_blk_idx==null ) ) meta->eager_blk_idx = (uint)fd_repair_blk_pool_idx( pool, blk_insert( self, shred->slot, fd_type_pun_const( &hash_null ) ) );
917 8322 : fd_repair_blk_t * blk = fd_repair_blk_pool_ele( pool, meta->eager_blk_idx );
918 8322 : if( FD_UNLIKELY( blk->parent_slot==ULONG_MAX ) ) blk->parent_slot = parent_slot; /* created empty by a child or catchup */
919 8322 : if( FD_UNLIKELY( blk->init_parent_slot==ULONG_MAX ) ) blk->init_parent_slot = parent_slot;
920 :
921 : /* Check for misbehavior that can invalidate the eager block. */
922 :
923 8322 : fd_block_marker_t marker[1];
924 8322 : int bad_header = shred->idx==0U && ( fd_block_marker_de( marker, fd_shred_data_payload( shred ), fd_shred_payload_sz( shred ) ) || marker->kind!=FD_BLOCK_MARKER_KIND_HEADER || marker->header.parent_slot!=parent_slot );
925 8322 : fd_mr32_t const * parent_dmr = ( shred->idx==0U && !blk->init_fec_cnt ) ? fd_type_pun_const( &marker->header.parent_block_id ) : NULL;
926 :
927 8322 : int slot_complete = !!( shred->data.flags & FD_SHRED_DATA_FLAG_SLOT_COMPLETE );
928 8322 : int eqvoc = blk->fecs[ fec_idx ]!=fd_repair_fec_pool_idx_null( self->fec_pool ) && blk->fecs[ fec_idx ]!=fd_repair_fec_pool_idx( self->fec_pool, fec ); /* the leader signed two FEC sets at this index, eg. two shred 0s */
929 8322 : int parent_conflict = bad_header || blk->init_parent_slot!=parent_slot;
930 8322 : int complete_conflict = ( blk->cmpl_fec_cnt && fec_idx>=blk->cmpl_fec_cnt ) || ( slot_complete && fec_idx+1U<blk->rcvd_fec_cnt );
931 8322 : if( FD_UNLIKELY( eqvoc ) ) { fd_repair_slot_invalidated( self, shred->slot, FD_EVENT_BLOCK_RECEIVED_CANCELLED_REASON_MERKLE_ROOT_MISMATCH, ts ); return; }
932 8316 : if( FD_UNLIKELY( parent_conflict ) ) { fd_repair_slot_invalidated( self, shred->slot, bad_header ? FD_EVENT_BLOCK_RECEIVED_CANCELLED_REASON_INVALID_BLOCK_HEADER : FD_EVENT_BLOCK_RECEIVED_CANCELLED_REASON_PARENT_OFF_MISMATCH, ts ); return; }
933 8313 : if( FD_UNLIKELY( complete_conflict ) ) { fd_repair_slot_invalidated( self, shred->slot, FD_EVENT_BLOCK_RECEIVED_CANCELLED_REASON_SLOT_COMPLETE_MISMATCH, ts ); return; }
934 8304 : if( FD_UNLIKELY( shred->idx==0U && blk->init_fec_cnt && marker->header.parent_slot==blk->parent_slot && !memcmp( &marker->header.parent_block_id, &blk->parent_dmr, sizeof(fd_mr32_t) ) ) ) {
935 : /* a late shred 0 header == UpdateParent's parent */
936 3 : fd_repair_slot_invalidated( self, shred->slot, FD_EVENT_BLOCK_RECEIVED_CANCELLED_REASON_INVALID_UPDATE_PARENT, ts );
937 3 : return;
938 3 : }
939 :
940 8301 : if( FD_UNLIKELY( parent_dmr ) ) { /* shred 0 again names the same parent, the key must not change while in orphan_map */
941 789 : if( FD_UNLIKELY( blk!=self->root_blk && blk->parent==null ) ) fd_repair_blk_orphan_map_ele_remove_fast( self->orphan_map, blk, pool );
942 789 : blk->parent_dmr = *parent_dmr;
943 789 : if( FD_UNLIKELY( blk!=self->root_blk && blk->parent==null ) ) fd_repair_blk_orphan_map_ele_insert ( self->orphan_map, blk, pool );
944 789 : }
945 8301 : if( FD_UNLIKELY( parent_dmr && blk->parent==null && !link_parent( self, blk ) ) ) { /* waits unlinked for the named parent to be held, eg. to complete on turbine */
946 240 : fd_repair_slot_meta_t * pmeta = fd_repair_slot_meta( self, parent_slot );
947 240 : if( FD_UNLIKELY( pmeta->eager_blk_idx==null && pmeta->final_blk_idx==null && !pmeta->skipped && !pmeta->invalidated ) ) blk_insert( self, parent_slot, fd_type_pun_const( &hash_null ) ); /* seed the parent slot's eager blk, turbine may have lost it */
948 240 : }
949 8301 : if( FD_UNLIKELY( slot_complete ) ) blk->cmpl_fec_cnt = fec_idx+1U;
950 8301 : if( FD_UNLIKELY( slot_complete || fec_idx+1U>blk->rcvd_fec_cnt ) ) { /* its repair limit moved */
951 7842 : blk->eager_ts = fd_long_if( fec_idx+1U>blk->rcvd_fec_cnt, ts, blk->eager_ts );
952 7842 : fd_repair_blk_treap_insert( self, blk );
953 7842 : }
954 :
955 8301 : if( FD_UNLIKELY( !fec ) ) {
956 7398 : FD_TEST( fd_repair_fec_pool_free( self->fec_pool ) );
957 7398 : fec = fd_repair_fec_pool_ele_acquire( self->fec_pool );
958 7398 : fec->mr = key;
959 7398 : fec->fec_idx = fec_idx;
960 7398 : fec->slot = shred->slot;
961 7398 : fec->fec_complete = 0;
962 7398 : fec->data_complete = 0;
963 7398 : fec->first_ts = ts;
964 7398 : fec->cmpl_ts = 0L;
965 7398 : fec->is_leader = 0;
966 7398 : fec->is_notar = 0;
967 7398 : fec->data_rcvd = 0U;
968 7398 : fec->parity_rcvd = 0U;
969 7398 : fec->repair_rcvd = 0U;
970 7398 : fec->update_parent.new_parent_slot = ULONG_MAX;
971 7398 : fd_repair_fec_map_ele_insert( self->fec_map, fec, self->fec_pool );
972 7398 : }
973 8301 : blk->fecs[ fec_idx ] = fd_repair_fec_pool_idx( self->fec_pool, fec );
974 8301 : blk->rcvd_fec_cnt = fd_uint_max( blk->rcvd_fec_cnt, fec_idx+1U );
975 8301 : fec->data_rcvd = fd_uint_if( fec->fec_complete, fec->data_rcvd, fd_uint_set_bit( fec->data_rcvd, (int)( shred->idx - fec_idx*FD_FEC_SHRED_CNT ) ) );
976 :
977 8301 : if( FD_UNLIKELY( parent_update ) ) { fec->update_parent = update->update_parent; update_parent( self, shred->slot, fec_idx, ts ); }
978 8301 : if( FD_UNLIKELY( data_complete ) ) { fec->data_complete = 1; update_parent( self, shred->slot, fec_idx+1U, ts ); }
979 8301 : }
980 :
981 : void
982 : fd_repair_slot_invalidated( fd_repair_t * self,
983 : ulong slot,
984 : int reason,
985 45501 : long ts ) {
986 45501 : fd_repair_slot_meta_t * meta = fd_repair_slot_meta( self, slot );
987 45501 : fd_repair_blk_t * eager = fd_repair_blk_pool_ele( self->blk_pool, meta->eager_blk_idx );
988 45501 : int first = !meta->invalidated;
989 45501 : meta->invalidated = 1;
990 45501 : if( FD_LIKELY( eager ) ) {
991 93 : eager->telemetry.cancelled_ts = fd_long_if( !eager->telemetry.cancelled_reason, ts, eager->telemetry.cancelled_ts );
992 93 : eager->telemetry.cancelled_reason = (uchar)reason;
993 93 : eager->eager = 0;
994 93 : }
995 45501 : if( FD_LIKELY( eager && meta->final_blk_idx!=meta->eager_blk_idx && meta->notar_blk_idx!=meta->eager_blk_idx ) ) blk_treap_remove( self, eager ); /* still the eager blk, never repaired */
996 45501 : if( FD_LIKELY( first && eager && eager->parent!=fd_repair_blk_pool_idx_null( self->blk_pool ) ) ) cascade( self, fd_repair_blk_pool_ele( self->blk_pool, eager->parent ) ); /* delivers the notar blks held behind it */
997 45501 : }
998 :
999 : fd_repair_slot_meta_t *
1000 : fd_repair_slot_meta( fd_repair_t * self,
1001 841230 : ulong slot ) {
1002 841230 : fd_repair_slot_meta_t * meta = &self->slot_meta[ slot % self->slot_max ];
1003 841230 : if( FD_UNLIKELY( meta->slot!=slot ) ) {
1004 62166 : meta->slot = slot;
1005 62166 : meta->eager_blk_idx = (uint)fd_repair_blk_pool_idx_null( self->blk_pool );
1006 62166 : meta->notar_blk_idx = (uint)fd_repair_blk_pool_idx_null( self->blk_pool );
1007 62166 : meta->final_blk_idx = (uint)fd_repair_blk_pool_idx_null( self->blk_pool );
1008 62166 : meta->invalidated = 0;
1009 62166 : meta->skipped = 0;
1010 62166 : meta->leader = 0;
1011 62166 : }
1012 841230 : return meta;
1013 841230 : }
1014 :
1015 : void
1016 : fd_repair_slot_skipped( fd_repair_t * self,
1017 36 : ulong slot ) {
1018 36 : fd_repair_slot_meta_t * meta = fd_repair_slot_meta( self, slot );
1019 36 : meta->skipped = 1; /* late repair requests or shreds for the slot must not recreate blks in it */
1020 :
1021 36 : fd_repair_blk_t * next;
1022 36 : for( fd_repair_blk_t * blk = fd_repair_blk_map_ele_query( self->blk_map, &slot, NULL, self->blk_pool );
1023 60 : blk;
1024 36 : blk = next ) {
1025 : next = (fd_repair_blk_t *)fd_repair_blk_map_ele_next_const( blk, NULL, self->blk_pool );
1026 24 : prune( self, blk );
1027 24 : }
1028 36 : }
|
