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 8550 : fd_repair_blk_t * blk ) {
10 8550 : fd_repair_slot_meta_t const * meta = fd_repair_slot_meta( self, blk->slot );
11 8550 : ulong idx = fd_repair_blk_pool_idx( self->blk_pool, blk );
12 8550 : 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 8550 : if( FD_UNLIKELY( fd_repair_treap_ele_query_const( treap, blk, self->blk_pool )==blk ) ) return 0;
14 2009 : if( FD_UNLIKELY( meta->final_blk_idx!=idx && meta->notar_blk_idx!=idx && meta->eager_blk_idx==idx && !blk->eager ) ) return 0;
15 2009 : fd_repair_treap_ele_insert( treap, blk, self->blk_pool );
16 2009 : return 1;
17 2009 : }
18 :
19 : static int
20 : blk_treap_remove( fd_repair_t * self,
21 1008 : fd_repair_blk_t * blk ) {
22 1008 : fd_repair_slot_meta_t const * meta = fd_repair_slot_meta( self, blk->slot );
23 1008 : ulong idx = fd_repair_blk_pool_idx( self->blk_pool, blk );
24 1008 : 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 1008 : if( FD_LIKELY( fd_repair_treap_ele_query_const( treap, blk, self->blk_pool )!=blk ) ) return 0;
26 1008 : fd_repair_treap_ele_remove( treap, blk, self->blk_pool );
27 1008 : return 1;
28 1008 : }
29 :
30 : static fd_repair_blk_t *
31 : blk_insert( fd_repair_t * self,
32 : ulong slot,
33 2009 : fd_mr32_t const * dmr ) {
34 2009 : FD_TEST( fd_repair_blk_pool_free( self->blk_pool ) );
35 2009 : fd_repair_slot_meta_t * meta = fd_repair_slot_meta( self, slot );
36 2009 : fd_repair_blk_t * blk = fd_repair_blk_pool_ele_acquire( self->blk_pool );
37 2009 : blk->slot = slot;
38 2009 : blk->dmr = *dmr;
39 2009 : blk->parent = fd_repair_blk_pool_idx_null( self->blk_pool );
40 2009 : blk->child = fd_repair_blk_pool_idx_null( self->blk_pool );
41 2009 : blk->sibling = fd_repair_blk_pool_idx_null( self->blk_pool );
42 2009 : blk->cmpl_fec_cnt = 0U;
43 2009 : blk->rcvd_fec_cnt = 0U;
44 2009 : blk->buff_fec_cnt = 0U;
45 2009 : blk->cons_fec_cnt = 0U;
46 2009 : blk->wait_fec_cnt = 0U;
47 2009 : blk->parent_slot = ULONG_MAX;
48 2009 : blk->parent_dmr = (fd_mr32_t){ { 0 } };
49 2009 : blk->init_fec_cnt = 0U;
50 2009 : blk->init_parent_slot = ULONG_MAX;
51 :
52 2009 : 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 2009 : blk->meta_req = 0;
54 2009 : blk->highest_req = 0;
55 2009 : blk->orphan_req = 0;
56 2009 : memset( &blk->telemetry, 0, sizeof(blk->telemetry) );
57 2009 : blk->telemetry.last_cmpl_fec_idx = UINT_MAX;
58 2009 : blk->eager_ts = 0L;
59 2056276 : for( ulong k=0UL; k<self->fec_blk_max; k++ ) blk->fecs[ k ] = fd_repair_fec_pool_idx_null( self->fec_pool );
60 2009 : fd_repair_blk_map_ele_insert( self->blk_map, blk, self->blk_pool );
61 2009 : fd_repair_blk_orphan_map_ele_insert( self->orphan_map, blk, self->blk_pool );
62 2009 : if ( !memcmp( dmr, &hash_null, sizeof(fd_mr32_t) ) ) meta->eager_blk_idx = (uint)fd_repair_blk_pool_idx( self->blk_pool, blk );
63 1001 : 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 2009 : fd_repair_blk_treap_insert( self, blk );
65 2009 : return blk;
66 2009 : }
67 :
68 : static void
69 : compute_dmr( fd_repair_t * self,
70 992 : fd_repair_blk_t * blk ) {
71 992 : uint fec_set_cnt = blk->cmpl_fec_cnt;
72 :
73 992 : uchar tree_mem[ FD_BMTREE_COMMIT_FOOTPRINT( 0UL ) ] __attribute__((aligned(FD_BMTREE_COMMIT_ALIGN)));
74 992 : fd_bmtree_commit_t * tree = fd_bmtree_commit_init( tree_mem, FD_SHRED_MERKLE_NODE_SZ, FD_BMTREE_LONG_PREFIX_SZ, 0UL );
75 5537 : for( uint k=0U; k<fec_set_cnt; k++ ) {
76 4545 : fd_bmtree_node_t leaf[1];
77 4545 : memcpy( leaf->hash, fd_repair_fec_pool_ele( self->fec_pool, blk->fecs[ k ] )->mr.mr32.uc, sizeof(fd_mr32_t) );
78 4545 : fd_bmtree_commit_append( tree, leaf, 1UL );
79 4545 : }
80 :
81 992 : fd_bmtree_node_t parent_info[1];
82 992 : fd_sha256_t sha[1];
83 992 : fd_sha256_init ( sha );
84 992 : fd_sha256_append( sha, &blk->parent_slot, sizeof(ulong) );
85 992 : fd_sha256_append( sha, blk->parent_dmr.uc, sizeof(fd_mr32_t) );
86 992 : fd_sha256_append( sha, &fec_set_cnt, sizeof(uint) );
87 992 : fd_sha256_fini ( sha, parent_info->hash );
88 992 : fd_bmtree_commit_append( tree, parent_info, 1UL );
89 :
90 992 : memcpy( blk->dmr.uc, fd_bmtree_commit_fini( tree ), sizeof(fd_mr32_t) );
91 992 : }
92 :
93 : static void
94 : consume( fd_repair_t * self,
95 4557 : fd_repair_blk_t * blk ) {
96 4557 : fd_repair_slot_meta_t const * meta = fd_repair_slot_meta( self, blk->slot );
97 4557 : if( FD_UNLIKELY( meta->invalidated && !memcmp( &blk->dmr, &hash_null, sizeof(fd_mr32_t) ) ) ) return;
98 4557 : if( FD_UNLIKELY( blk->parent==fd_repair_blk_pool_idx_null( self->blk_pool ) ) ) return; /* orphaned, even if partly consumed */
99 4557 : if( FD_UNLIKELY( blk->cons_fec_cnt<=blk->init_fec_cnt ) ) {
100 1001 : fd_repair_blk_t const * parent = fd_repair_blk_pool_ele_const( self->blk_pool, blk->parent );
101 1001 : if( FD_LIKELY( parent!=self->root_blk && ( !parent->cmpl_fec_cnt || parent->cons_fec_cnt!=parent->cmpl_fec_cnt ) ) ) return;
102 1001 : }
103 4557 : ulong idx = fd_repair_blk_pool_idx( self->blk_pool, blk );
104 4557 : fd_repair_blk_t * eager = fd_repair_blk_pool_ele( self->blk_pool, meta->eager_blk_idx );
105 4557 : if( FD_UNLIKELY( eager && meta->eager_blk_idx!=idx && !meta->invalidated && !memcmp( &eager->dmr, &hash_null, sizeof(fd_mr32_t) ) ) ) {
106 0 : int dup = eager->parent==blk->parent;
107 0 : for( uint k=blk->cons_fec_cnt; dup && k<blk->buff_fec_cnt; k++ ) dup = eager->fecs[ k ]==blk->fecs[ k ];
108 0 : if( FD_LIKELY( dup ) ) {
109 0 : blk = eager;
110 0 : idx = meta->eager_blk_idx;
111 0 : }
112 0 : }
113 :
114 4557 : if( FD_UNLIKELY( self->reconsume && blk->cons_fec_cnt<blk->buff_fec_cnt ) ) { /* replay evicted, need to specially redeliver from the root */
115 0 : self->reconsume = 0;
116 0 : for( fd_repair_blk_t * anc = blk; anc && anc!=self->root_blk; anc = fd_repair_blk_pool_ele( self->blk_pool, anc->parent ) ) {
117 0 : 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 0 : }
119 0 : }
120 4557 : if( FD_UNLIKELY( meta->leader && meta->eager_blk_idx==idx ) ) { /* our leader blk goes first, in FEC order */
121 0 : 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 0 : blk->cons_fec_cnt = blk->buff_fec_cnt;
123 0 : return;
124 0 : }
125 9114 : 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 4557 : }
127 :
128 : static void
129 : cascade( fd_repair_t * self,
130 992 : fd_repair_blk_t * root ) {
131 992 : fd_repair_blk_t * pool = self->blk_pool;
132 992 : ulong null = fd_repair_blk_pool_idx_null( pool );
133 992 : ulong tidx = fd_repair_blk_pool_idx( pool, root );
134 992 : ulong idx = root->child;
135 992 : while( FD_LIKELY( idx!=null ) ) {
136 0 : fd_repair_blk_t * blk = fd_repair_blk_pool_ele( pool, idx );
137 0 : consume( self, blk );
138 0 : if( FD_LIKELY( blk->cmpl_fec_cnt && blk->cons_fec_cnt==blk->cmpl_fec_cnt && blk->child!=null ) ) { idx = blk->child; continue; }
139 0 : while( FD_LIKELY( idx!=tidx && fd_repair_blk_pool_ele( pool, idx )->sibling==null ) ) idx = fd_repair_blk_pool_ele( pool, idx )->parent;
140 0 : if( FD_UNLIKELY( idx==tidx ) ) break;
141 0 : idx = fd_repair_blk_pool_ele( pool, idx )->sibling;
142 0 : }
143 992 : }
144 :
145 : static void
146 : promote( fd_repair_t * self,
147 : fd_repair_blk_t * blk,
148 0 : uint * role ) {
149 0 : if( FD_LIKELY( *role==fd_repair_blk_pool_idx( self->blk_pool, blk ) ) ) return;
150 0 : int queued = blk_treap_remove( self, blk );
151 0 : *role = (uint)fd_repair_blk_pool_idx( self->blk_pool, blk );
152 0 : blk->eager = 0;
153 0 : if( FD_LIKELY( queued ) ) fd_repair_blk_treap_insert( self, blk );
154 0 : }
155 :
156 : static fd_repair_blk_t *
157 : link_parent( fd_repair_t * self,
158 1001 : fd_repair_blk_t * blk ) {
159 1001 : fd_repair_blk_t * pool = self->blk_pool;
160 1001 : if( FD_UNLIKELY( blk->parent_slot==ULONG_MAX ) ) return NULL;
161 1001 : if( FD_UNLIKELY( blk->parent_slot!=self->root && !memcmp( &blk->parent_dmr, &hash_null, sizeof(fd_mr32_t) ) ) ) return NULL;
162 :
163 1001 : fd_repair_blk_t * parent = fd_repair_blk_map_ele_query( self->blk_map, &blk->parent_slot, NULL, pool );
164 1001 : 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 1001 : if( FD_LIKELY( !parent ) ) return NULL;
166 :
167 1001 : if( FD_LIKELY( blk!=self->root_blk ) ) fd_repair_blk_orphan_map_ele_remove_fast( self->orphan_map, blk, pool );
168 :
169 1001 : blk->parent = fd_repair_blk_pool_idx( pool, parent );
170 1001 : blk->sibling = parent->child;
171 1001 : parent->child = fd_repair_blk_pool_idx( pool, blk );
172 1001 : return parent;
173 1001 : }
174 :
175 : static void
176 : link_ancestors( fd_repair_t * self,
177 0 : fd_repair_blk_t * blk ) {
178 0 : fd_repair_blk_t * pool = self->blk_pool;
179 0 : ulong null = fd_repair_blk_pool_idx_null( pool );
180 0 : fd_repair_blk_t * top = blk;
181 0 : for(;;) {
182 0 : if( FD_UNLIKELY( blk->parent_slot==ULONG_MAX || blk->parent_slot<self->root ) ) break;
183 0 : if( FD_UNLIKELY( blk->parent_slot!=self->root && !memcmp( &blk->parent_dmr, &hash_null, sizeof(fd_mr32_t) ) ) ) break;
184 0 : fd_repair_slot_meta_t * meta = fd_repair_slot_meta( self, blk->slot );
185 0 : fd_repair_slot_meta_t * pmeta = fd_repair_slot_meta( self, blk->parent_slot );
186 0 : int final = meta->final_blk_idx==fd_repair_blk_pool_idx( pool, blk );
187 0 : int unlinked = blk->parent==null;
188 0 : fd_repair_blk_t * parent = unlinked ? link_parent( self, blk ) : fd_repair_blk_pool_ele( pool, blk->parent );
189 0 : if( FD_UNLIKELY( parent && unlinked ) ) top = blk;
190 0 : if( FD_UNLIKELY( !parent ) ) {
191 0 : if( FD_UNLIKELY( blk->parent_slot==self->root ) ) break; /* names a root other than ours */
192 0 : parent = fd_repair_blk_notarized( self, blk->parent_slot, &blk->parent_dmr ); /* link_orphans links blk under it */
193 0 : if( FD_UNLIKELY( !parent ) ) break; /* the parent slot is settled otherwise */
194 0 : fd_repair_blk_treap_insert( self, blk ); /* its tile asks ORPHAN for eager ancestry, which may merge with the named parents */
195 0 : top = blk;
196 0 : }
197 0 : if( FD_UNLIKELY( final && pmeta->final_blk_idx==null ) ) promote( self, parent, &pmeta->final_blk_idx );
198 0 : blk = parent;
199 0 : }
200 0 : consume( self, top );
201 0 : if( FD_UNLIKELY( top->cmpl_fec_cnt && top->cons_fec_cnt==top->cmpl_fec_cnt ) ) cascade( self, top );
202 0 : }
203 :
204 : static void
205 : link_orphans( fd_repair_t * self,
206 992 : fd_repair_blk_t * parent ) {
207 992 : fd_repair_blk_t * pool = self->blk_pool;
208 992 : ulong null = fd_repair_blk_pool_idx_null( pool );
209 992 : fd_repair_slot_meta_t * pmeta = fd_repair_slot_meta( self, parent->slot );
210 992 : fd_repair_blk_t * next;
211 992 : for( fd_repair_blk_t * blk = fd_repair_blk_orphan_map_ele_query( self->orphan_map, &parent->dmr, NULL, pool );
212 992 : blk;
213 992 : blk = next ) {
214 0 : next = (fd_repair_blk_t *)fd_repair_blk_orphan_map_ele_next_const( blk, NULL, pool );
215 0 : if( FD_UNLIKELY( blk->parent_slot!=parent->slot ) ) continue;
216 0 : fd_repair_blk_orphan_map_ele_remove_fast( self->orphan_map, blk, pool );
217 0 : blk->parent = fd_repair_blk_pool_idx( pool, parent );
218 0 : blk->sibling = parent->child;
219 0 : parent->child = fd_repair_blk_pool_idx( pool, blk );
220 0 : 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 0 : }
222 992 : }
223 :
224 : static void
225 : unlink( fd_repair_t * self,
226 0 : fd_repair_blk_t * blk ) {
227 0 : fd_repair_blk_t * pool = self->blk_pool;
228 0 : ulong null = fd_repair_blk_pool_idx_null( pool );
229 0 : ulong idx = fd_repair_blk_pool_idx( pool, blk );
230 0 : if( FD_LIKELY( blk->parent!=null ) ) {
231 0 : ulong * link = &fd_repair_blk_pool_ele( pool, blk->parent )->child;
232 0 : while( *link!=idx ) link = &fd_repair_blk_pool_ele( pool, *link )->sibling;
233 0 : *link = blk->sibling;
234 0 : }
235 0 : ulong next;
236 0 : for( ulong c=blk->child; c!=null; c=next ) {
237 0 : fd_repair_blk_t * child = fd_repair_blk_pool_ele( pool, c );
238 0 : next = child->sibling;
239 0 : child->parent = null;
240 0 : child->sibling = null;
241 0 : 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 0 : }
243 0 : }
244 :
245 : static void
246 : prune( fd_repair_t * self,
247 0 : fd_repair_blk_t * blk ) {
248 0 : fd_repair_blk_t * pool = self->blk_pool;
249 0 : if( FD_UNLIKELY( !blk->telemetry.reported && self->telemetry.report ) ) self->telemetry.report( self->telemetry.ctx, blk );
250 0 : for( ulong k=0UL; k<self->fec_blk_max; k++ ) {
251 0 : if( FD_LIKELY( blk->fecs[ k ]==fd_repair_fec_pool_idx_null( self->fec_pool ) ) ) continue;
252 0 : int held = 0;
253 0 : for( fd_repair_blk_t const * other = fd_repair_blk_map_ele_query_const( self->blk_map, &blk->slot, NULL, pool );
254 0 : other && !held;
255 0 : other = fd_repair_blk_map_ele_next_const( other, NULL, pool ) ) {
256 0 : held = other!=blk && other->fecs[ k ]==blk->fecs[ k ];
257 0 : }
258 0 : if( FD_UNLIKELY( held ) ) continue;
259 0 : fd_repair_fec_t * fec = fd_repair_fec_pool_ele( self->fec_pool, blk->fecs[ k ] );
260 0 : fd_repair_fec_map_ele_remove_fast( self->fec_map, fec, self->fec_pool );
261 0 : fd_repair_fec_pool_ele_release ( self->fec_pool, fec );
262 0 : }
263 0 : unlink( self, blk );
264 0 : 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 0 : blk_treap_remove( self, blk );
266 0 : fd_repair_slot_meta_t * meta = fd_repair_slot_meta( self, blk->slot );
267 0 : 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 0 : 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 0 : 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 0 : fd_repair_blk_map_ele_remove_fast( self->blk_map, blk, pool );
271 0 : fd_repair_blk_pool_ele_release ( pool, blk );
272 0 : }
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 992 : long ts ) {
290 992 : fd_repair_blk_t * pool = self->blk_pool;
291 992 : ulong null = fd_repair_blk_pool_idx_null( pool );
292 992 : ulong idx = fd_repair_blk_pool_idx( pool, eager );
293 :
294 992 : fd_repair_blk_t * notar = fd_repair_blk_map_ele_query( self->blk_map, &eager->slot, NULL, pool );
295 1984 : while( notar && ( notar==eager || memcmp( ¬ar->dmr, &eager->dmr, sizeof(fd_mr32_t) ) ) ) {
296 992 : notar = (fd_repair_blk_t *)fd_repair_blk_map_ele_next_const( notar, NULL, pool );
297 992 : }
298 992 : fd_repair_slot_meta_t * meta = fd_repair_slot_meta( self, eager->slot );
299 992 : if( FD_UNLIKELY( !notar && meta->final_blk_idx!=null ) ) {
300 0 : eager->telemetry.cancelled_ts = fd_long_if( !eager->telemetry.cancelled_reason, ts, eager->telemetry.cancelled_ts );
301 0 : eager->telemetry.cancelled_reason = (uchar)FD_EVENT_BLOCK_RECEIVED_CANCELLED_REASON_NOTARIZED_VERSION;
302 0 : prune( self, eager );
303 0 : return;
304 0 : } /* turbine built a blk the cluster did not finalize */
305 992 : if( FD_LIKELY( !notar ) ) return;
306 :
307 1 : ulong next;
308 1 : for( ulong c=notar->child; c!=null; c=next ) {
309 0 : next = fd_repair_blk_pool_ele( pool, c )->sibling;
310 0 : fd_repair_blk_pool_ele( pool, c )->parent = idx;
311 0 : fd_repair_blk_pool_ele( pool, c )->sibling = eager->child;
312 0 : eager->child = c;
313 0 : }
314 1 : notar->child = null;
315 1 : 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 1 : blk_treap_remove( self, notar );
322 1 : 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 1 : 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 1 : notar->telemetry.reported = 1; /* the same block lives on as eager, we won't report two different lines for this */
325 :
326 1 : eager->telemetry.req_window_cnt += notar->telemetry.req_window_cnt;
327 1 : eager->telemetry.req_highest_cnt += notar->telemetry.req_highest_cnt;
328 1 : eager->telemetry.req_orphan_cnt += notar->telemetry.req_orphan_cnt;
329 1 : eager->telemetry.req_shred_bid_cnt += notar->telemetry.req_shred_bid_cnt;
330 1 : eager->telemetry.req_parent_cnt += notar->telemetry.req_parent_cnt;
331 1 : eager->telemetry.req_fec_root_cnt += notar->telemetry.req_fec_root_cnt;
332 1 : eager->telemetry.shred_res_cnt += notar->telemetry.shred_res_cnt;
333 1 : eager->telemetry.parent_res_cnt += notar->telemetry.parent_res_cnt;
334 1 : eager->telemetry.fec_root_res_cnt += notar->telemetry.fec_root_res_cnt;
335 : /* first timestamps */
336 1 : 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 1 : 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 1 : eager->telemetry.last_shred_res_ts = fd_long_max( eager->telemetry.last_shred_res_ts, notar->telemetry.last_shred_res_ts );
339 1 : prune( self, notar );
340 1 : link_ancestors( self, eager );
341 1 : }
342 :
343 : static void
344 : update_parent( fd_repair_t * self,
345 : ulong slot,
346 : uint fec_idx,
347 18223 : long ts ) {
348 18223 : if( FD_UNLIKELY( !fec_idx || fec_idx>=self->fec_blk_max ) ) return;
349 18223 : fd_repair_slot_meta_t * meta = fd_repair_slot_meta( self, slot );
350 18223 : fd_repair_blk_t * pool = self->blk_pool;
351 18223 : ulong null = fd_repair_blk_pool_idx_null( pool );
352 18223 : fd_repair_blk_t * next;
353 36448 : for( fd_repair_blk_t * blk = fd_repair_blk_map_ele_query( self->blk_map, &slot, NULL, pool ); blk; blk = next ) {
354 18225 : next = (fd_repair_blk_t *)fd_repair_blk_map_ele_next_const( blk, NULL, pool );
355 :
356 18225 : 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 1 : fd_repair_fec_t const * prev_fec = fd_repair_fec_pool_ele_const( self->fec_pool, blk->fecs[ fec_idx-1U ] );
358 1 : fd_repair_fec_t const * next_fec = fd_repair_fec_pool_ele_const( self->fec_pool, blk->fecs[ fec_idx ] );
359 :
360 1 : if( FD_LIKELY( !prev_fec->data_complete || next_fec->update_parent.new_parent_slot==ULONG_MAX ) ) continue;
361 1 : if( FD_UNLIKELY( blk->init_fec_cnt==fec_idx ) ) continue;
362 :
363 1 : fd_update_parent_t const * update = &next_fec->update_parent;
364 1 : int eager = meta->eager_blk_idx==fd_repair_blk_pool_idx( pool, blk );
365 1 : if( FD_UNLIKELY( eager && meta->invalidated ) ) continue;
366 :
367 1 : int bad = !fd_is_start_of_window( slot ) /* not in the first slot of its leader window */
368 1 : || blk->init_fec_cnt /* a second UpdateParent */
369 1 : || update->new_parent_slot<self->root /* a parent below the root */
370 1 : || update->new_parent_slot>=slot /* a parent newer than the header's */
371 1 : || ( eager && update->new_parent_slot>blk->init_parent_slot ) /* a parent newer than the header's */
372 1 : || !memcmp( &update->new_parent_block_id, &hash_null, sizeof(fd_mr32_t) ) /* a null parent block id */
373 1 : || ( 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 1 : 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 1 : if( FD_UNLIKELY( bad && eager ) ) { fd_repair_slot_invalidated( self, slot, FD_EVENT_BLOCK_RECEIVED_CANCELLED_REASON_INVALID_UPDATE_PARENT, ts ); continue; }
378 :
379 1 : if( FD_UNLIKELY( !eager ) ) {
380 0 : 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 0 : blk->init_fec_cnt = fec_idx;
385 0 : blk->cons_fec_cnt = fd_uint_max( blk->cons_fec_cnt, fec_idx ); /* stream starts at the UpdateParent, prefix is skipped */
386 0 : continue;
387 0 : }
388 :
389 1 : if( FD_LIKELY( blk->parent!=null ) ) {
390 0 : ulong idx = fd_repair_blk_pool_idx( pool, blk );
391 0 : ulong * link = &fd_repair_blk_pool_ele( pool, blk->parent )->child;
392 0 : while( *link!=idx ) link = &fd_repair_blk_pool_ele( pool, *link )->sibling;
393 0 : *link = blk->sibling;
394 0 : blk->parent = null;
395 0 : blk->sibling = null;
396 1 : } else if( FD_LIKELY( blk!=self->root_blk ) ) {
397 0 : fd_repair_blk_orphan_map_ele_remove_fast( self->orphan_map, blk, pool );
398 0 : }
399 :
400 1 : blk->parent_slot = update->new_parent_slot;
401 1 : blk->parent_dmr = FD_LOAD( fd_mr32_t, update->new_parent_block_id.uc );
402 1 : blk->init_fec_cnt = fec_idx;
403 1 : blk->cons_fec_cnt = fd_uint_max( blk->cons_fec_cnt, fec_idx );
404 1 : blk->orphan_req = 0; /* an ORPHAN req for the header's parent is moot */
405 :
406 1 : 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 1 : if( FD_UNLIKELY( link_parent( self, blk ) ) ) continue;
408 1 : fd_repair_slot_meta_t * pmeta = fd_repair_slot_meta( self, blk->parent_slot );
409 1 : 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 1 : fd_repair_blk_treap_insert( self, blk ); /* its tile asks ORPHAN for the new parent */
411 1 : }
412 18223 : }
413 :
414 : FD_FN_CONST ulong
415 12090 : fd_repair_align( void ) {
416 12090 : return fd_ulong_max( alignof(fd_repair_t), 128UL );
417 12090 : }
418 :
419 : FD_FN_CONST ulong
420 : fd_repair_footprint( ulong slot_max,
421 : ulong fec_max,
422 2015 : ulong fec_blk_max ) {
423 2015 : ulong blk_max = ( 5UL*slot_max+1UL )/2UL;
424 2015 : return FD_LAYOUT_FINI(
425 2015 : FD_LAYOUT_APPEND(
426 2015 : FD_LAYOUT_APPEND(
427 2015 : FD_LAYOUT_APPEND(
428 2015 : FD_LAYOUT_APPEND(
429 2015 : FD_LAYOUT_APPEND(
430 2015 : FD_LAYOUT_APPEND(
431 2015 : FD_LAYOUT_APPEND(
432 2015 : FD_LAYOUT_APPEND(
433 2015 : FD_LAYOUT_APPEND(
434 2015 : FD_LAYOUT_APPEND(
435 2015 : FD_LAYOUT_APPEND(
436 2015 : FD_LAYOUT_APPEND(
437 2015 : FD_LAYOUT_INIT,
438 2015 : fd_repair_align(), sizeof(fd_repair_t) ),
439 2015 : alignof(fd_repair_slot_meta_t), sizeof(fd_repair_slot_meta_t)*slot_max ),
440 2015 : fd_repair_blk_pool_align(), fd_repair_blk_pool_footprint ( blk_max ) ),
441 2015 : alignof(ulong), sizeof(ulong)*blk_max*fec_blk_max ),
442 2015 : fd_repair_blk_map_align(), fd_repair_blk_map_footprint ( fd_repair_blk_map_chain_cnt_est( blk_max ) ) ),
443 2015 : fd_repair_blk_orphan_map_align(), fd_repair_blk_orphan_map_footprint( fd_repair_blk_orphan_map_chain_cnt_est( blk_max ) ) ),
444 2015 : fd_repair_fec_pool_align(), fd_repair_fec_pool_footprint ( fec_max ) ),
445 2015 : fd_repair_fec_map_align(), fd_repair_fec_map_footprint ( fd_repair_fec_map_chain_cnt_est( fec_max ) ) ),
446 2015 : fd_repair_deque_align(), fd_repair_deque_footprint ( fec_max ) ),
447 2015 : fd_repair_treap_align(), fd_repair_treap_footprint ( blk_max ) ),
448 2015 : fd_repair_treap_align(), fd_repair_treap_footprint ( blk_max ) ),
449 2015 : fd_repair_treap_align(), fd_repair_treap_footprint ( blk_max ) ),
450 2015 : fd_repair_align() );
451 2015 : }
452 :
453 : void *
454 : fd_repair_new( void * shmem,
455 : ulong slot_max,
456 : ulong fec_max,
457 : ulong fec_blk_max,
458 1008 : ulong seed ) {
459 1008 : ulong footprint = fd_repair_footprint( slot_max, fec_max, fec_blk_max );
460 1008 : if( FD_UNLIKELY( !footprint || fec_blk_max<FD_FEC_BLK_MAX || fec_blk_max>UINT_MAX ) ) {
461 0 : FD_LOG_WARNING(( "bad footprint: %lu %lu %lu", slot_max, fec_max, fec_blk_max ));
462 0 : return NULL;
463 0 : }
464 :
465 1008 : fd_memset( shmem, 0, footprint );
466 1008 : fd_repair_t * repair;
467 :
468 1008 : ulong blk_max = ( 5UL*slot_max+1UL )/2UL;
469 :
470 1008 : FD_SCRATCH_ALLOC_INIT( l, shmem );
471 1008 : repair = FD_SCRATCH_ALLOC_APPEND( l, fd_repair_align(), sizeof(fd_repair_t) );
472 1008 : void * slot_meta = FD_SCRATCH_ALLOC_APPEND( l, alignof(fd_repair_slot_meta_t), sizeof(fd_repair_slot_meta_t)*slot_max );
473 1008 : void * blk_pool = FD_SCRATCH_ALLOC_APPEND( l, fd_repair_blk_pool_align(), fd_repair_blk_pool_footprint ( blk_max ) );
474 1008 : ulong * blk_fecs = FD_SCRATCH_ALLOC_APPEND( l, alignof(ulong), sizeof(ulong)*blk_max*fec_blk_max );
475 1008 : 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 1008 : 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 1008 : void * fec_pool = FD_SCRATCH_ALLOC_APPEND( l, fd_repair_fec_pool_align(), fd_repair_fec_pool_footprint ( fec_max ) );
478 1008 : 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 1008 : void * reasm_deque = FD_SCRATCH_ALLOC_APPEND( l, fd_repair_deque_align(), fd_repair_deque_footprint ( fec_max ) );
480 1008 : void * eager_treap = FD_SCRATCH_ALLOC_APPEND( l, fd_repair_treap_align(), fd_repair_treap_footprint ( blk_max ) );
481 1008 : void * notar_treap = FD_SCRATCH_ALLOC_APPEND( l, fd_repair_treap_align(), fd_repair_treap_footprint ( blk_max ) );
482 1008 : void * final_treap = FD_SCRATCH_ALLOC_APPEND( l, fd_repair_treap_align(), fd_repair_treap_footprint ( blk_max ) );
483 1008 : FD_TEST( FD_SCRATCH_ALLOC_FINI( l, fd_repair_align() ) == (ulong)shmem + footprint );
484 :
485 1008 : repair->root = ULONG_MAX;
486 1008 : repair->slot_max = slot_max;
487 1008 : repair->fec_blk_max = fec_blk_max;
488 1008 : repair->slot_meta = (fd_repair_slot_meta_t *)slot_meta;
489 3039 : for( ulong i=0UL; i<slot_max; i++ ) repair->slot_meta[ i ].slot = ULONG_MAX;
490 1008 : repair->blk_pool = fd_repair_blk_pool_join ( fd_repair_blk_pool_new ( blk_pool, blk_max ) );
491 6083 : for( ulong i=0UL; i<blk_max; i++ ) repair->blk_pool[ i ].fecs = blk_fecs + i*fec_blk_max;
492 1008 : 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 1008 : 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 1008 : repair->fec_pool = fd_repair_fec_pool_join ( fd_repair_fec_pool_new ( fec_pool, fec_max ) );
495 1008 : 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 1008 : repair->reasm_deque = fd_repair_deque_join ( fd_repair_deque_new ( reasm_deque, fec_max ) );
497 1008 : fd_repair_treap_seed( repair->blk_pool, blk_max, seed ); /* the treaps share each blk's prio */
498 1008 : repair->eager_treap = fd_repair_treap_join( fd_repair_treap_new( eager_treap, blk_max ) );
499 1008 : repair->notar_treap = fd_repair_treap_join( fd_repair_treap_new( notar_treap, blk_max ) );
500 1008 : repair->final_treap = fd_repair_treap_join( fd_repair_treap_new( final_treap, blk_max ) );
501 :
502 1008 : return shmem;
503 1008 : }
504 :
505 : fd_repair_t *
506 1008 : fd_repair_join( void * shrepair ) {
507 1008 : return (fd_repair_t *)shrepair;
508 1008 : }
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 1008 : void * report_ctx ) {
526 1008 : self->telemetry.report = report;
527 1008 : self->telemetry.ctx = report_ctx;
528 1008 : fd_repair_blk_t * blk = blk_insert( self, root, root_blk_mr );
529 1008 : blk->telemetry.reported = 1; /* the root is not a received block */
530 1008 : blk_treap_remove( self, blk ); /* the root is never repaired */
531 1008 : fd_repair_blk_orphan_map_ele_remove_fast( self->orphan_map, blk, self->blk_pool ); /* the root waits for nothing */
532 1008 : fd_repair_slot_meta( self, root )->final_blk_idx = (uint)fd_repair_blk_pool_idx( self->blk_pool, blk );
533 1008 : 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 1008 : blk->eager = 0;
535 1008 : self->root = root;
536 1008 : self->root_blk = blk;
537 1008 : self->catchup_slot = root;
538 1008 : }
539 :
540 : void
541 0 : fd_repair_fini( fd_repair_t * self ) {
542 0 : for( ulong i=0UL; i<self->slot_max; i++ ) self->slot_meta[ i ].slot = ULONG_MAX;
543 0 : fd_repair_blk_map_reset( self->blk_map );
544 0 : fd_repair_blk_orphan_map_reset( self->orphan_map );
545 0 : fd_repair_blk_pool_reset( self->blk_pool );
546 0 : fd_repair_fec_map_reset( self->fec_map );
547 0 : fd_repair_fec_pool_reset( self->fec_pool );
548 0 : fd_repair_deque_remove_all( self->reasm_deque );
549 0 : 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 0 : 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 0 : 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 0 : self->root = ULONG_MAX;
553 0 : self->root_blk = NULL;
554 0 : self->catchup_slot = 0UL;
555 0 : self->reconsume = 0;
556 0 : }
557 :
558 : void
559 : fd_repair_blk_dead( fd_repair_t * self,
560 : ulong slot,
561 : fd_mr32_t const * blk_mr,
562 0 : uint latest_fec_idx ) {
563 0 : fd_repair_blk_t * dead = fd_repair_blk_map_ele_query( self->blk_map, &slot, NULL, self->blk_pool );
564 0 : 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 0 : if( FD_UNLIKELY( !dead ) ) return;
566 :
567 0 : fd_repair_slot_meta_t * meta = fd_repair_slot_meta( self, slot );
568 0 : int eager = meta->eager_blk_idx==fd_repair_blk_pool_idx( self->blk_pool, dead );
569 0 : 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 0 : int prefix = eager && fd_is_start_of_window( slot ) && latest_fec_idx<bound;
571 0 : if( FD_UNLIKELY( prefix ) ) return; /* the optimistic prefix died, the block may still replay from an UpdateParent */
572 :
573 0 : blk_treap_remove( self, dead ); /* replay rejected it, no point repairing the rest */
574 0 : if( FD_LIKELY( !eager || meta->invalidated ) ) return;
575 :
576 0 : meta->invalidated = 1; /* turbine must not rebuild it */
577 0 : dead->eager = 0; /* never repaired by position */
578 0 : 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 0 : }
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 0 : long ts ) {
586 0 : fd_repair_slot_meta_t * meta = fd_repair_slot_meta( self, slot );
587 0 : fd_repair_blk_t const * existing_final = fd_repair_blk_pool_ele_const( self->blk_pool, meta->final_blk_idx );
588 0 : FD_CHECK_CRIT( !existing_final || !memcmp( &existing_final->dmr, blk_mr, sizeof(fd_mr32_t) ), "consensus safety violation" );
589 :
590 0 : fd_repair_blk_t * final = fd_repair_blk_map_ele_query( self->blk_map, &slot, NULL, self->blk_pool );
591 0 : 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 0 : if( FD_UNLIKELY( !final ) ) final = fd_repair_blk_notarized( self, slot, blk_mr );
593 0 : if( FD_UNLIKELY( !final ) ) return NULL;
594 :
595 0 : fd_repair_blk_t * pool = self->blk_pool;
596 0 : 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 0 : fd_repair_blk_t * next;
604 0 : for( fd_repair_blk_t * blk = fd_repair_blk_map_ele_query( self->blk_map, &slot, NULL, pool );
605 0 : blk;
606 0 : blk = next ) {
607 0 : next = (fd_repair_blk_t *)fd_repair_blk_map_ele_next_const( blk, NULL, pool );
608 0 : if( FD_LIKELY( blk==final ) ) continue;
609 0 : 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 0 : blk->telemetry.cancelled_ts = fd_long_if( !blk->telemetry.cancelled_reason, ts, blk->telemetry.cancelled_ts );
611 0 : 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 0 : prune( self, blk );
613 0 : }
614 0 : link_ancestors( self, final );
615 0 : return final;
616 0 : }
617 :
618 : fd_repair_blk_t *
619 : fd_repair_blk_notarized( fd_repair_t * self,
620 : ulong slot,
621 0 : fd_mr32_t const * blk_mr ) {
622 0 : fd_repair_slot_meta_t * meta = fd_repair_slot_meta( self, slot );
623 0 : 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 0 : 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 0 : for( fd_repair_blk_t * dup = fd_repair_blk_map_ele_query( self->blk_map, &slot, NULL, self->blk_pool );
626 0 : dup;
627 0 : dup = (fd_repair_blk_t *)fd_repair_blk_map_ele_next_const( dup, NULL, self->blk_pool ) ) {
628 0 : if( FD_UNLIKELY( memcmp( &dup->dmr, blk_mr, sizeof(fd_mr32_t) ) ) ) continue;
629 0 : 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 0 : link_ancestors( self, dup );
631 0 : return NULL;
632 0 : }
633 0 : fd_repair_blk_t * blk = blk_insert( self, slot, blk_mr );
634 0 : link_orphans( self, blk );
635 0 : return blk;
636 0 : }
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 0 : long ts ) {
646 0 : fd_repair_blk_t * blk = fd_repair_blk_map_ele_query( self->blk_map, &slot, NULL, self->blk_pool );
647 0 : 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 0 : if( FD_UNLIKELY( !blk ) ) return NULL; /* blk was pruned while the response was in flight */
649 0 : blk->telemetry.parent_res_cnt++;
650 0 : blk->telemetry.first_meta_res_ts = fd_long_if( !blk->telemetry.first_meta_res_ts, ts, blk->telemetry.first_meta_res_ts );
651 :
652 0 : if( FD_UNLIKELY( blk->parent_slot!=ULONG_MAX ) ) return NULL; /* duplicate response, eg. a retried request */
653 0 : if( FD_UNLIKELY( parent_slot>=slot ) ) return NULL; /* a blk's parent precedes it */
654 :
655 0 : int orphan = blk!=self->root_blk && blk->parent==fd_repair_blk_pool_idx_null( self->blk_pool );
656 0 : if( FD_LIKELY( orphan ) ) fd_repair_blk_orphan_map_ele_remove_fast( self->orphan_map, blk, self->blk_pool );
657 0 : blk->parent_slot = parent_slot;
658 0 : blk->parent_dmr = *parent_dmr;
659 0 : blk->cmpl_fec_cnt = fec_set_cnt;
660 0 : 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 0 : fd_repair_blk_treap_insert( self, blk ); /* its FEC sets can be discovered now */
662 :
663 0 : fd_repair_blk_t * parent = link_parent( self, blk );
664 0 : fd_repair_blk_t * created = NULL;
665 0 : if( FD_LIKELY( !parent ) ) parent = created = fd_repair_blk_notarized( self, parent_slot, parent_dmr ); /* links the child blks naming it */
666 0 : if( FD_LIKELY( parent ) ) {
667 0 : 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 0 : consume( self, blk );
669 0 : if( FD_UNLIKELY( blk->cmpl_fec_cnt && blk->cons_fec_cnt==blk->cmpl_fec_cnt ) ) cascade( self, blk );
670 0 : if( FD_LIKELY( !created ) ) link_ancestors( self, parent ); /* a held parent may itself be orphaned */
671 0 : }
672 0 : return created;
673 0 : }
674 :
675 : void
676 : fd_repair_slot_catchup( fd_repair_t * self,
677 0 : ulong slot ) {
678 0 : for( ulong s=fd_ulong_max( self->root+1UL, self->catchup_slot ); s<slot; s++ ) {
679 0 : fd_repair_slot_meta_t * meta = fd_repair_slot_meta( self, s );
680 0 : 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 0 : meta->eager_blk_idx = (uint)fd_repair_blk_pool_idx( self->blk_pool, blk_insert( self, s, fd_type_pun_const( &hash_null ) ) );
682 0 : }
683 0 : self->catchup_slot = fd_ulong_max( self->catchup_slot, slot );
684 0 : }
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 4557 : long ts ) {
698 4557 : fd_repair_shred_insert( self, last_shred, fec_mr, ts ); /* the last shred's header */
699 :
700 4557 : fd_mr_t key;
701 4557 : memcpy( key.mr32.uc, fec_mr->uc, sizeof(fd_mr32_t) );
702 4557 : fd_repair_fec_t * fec = fd_repair_fec_map_ele_query( self->fec_map, &key, NULL, self->fec_pool );
703 4557 : if( FD_UNLIKELY( !fec ) ) return NULL; /* fd_repair_shred_insert dropped it as conflicting with the eager blk */
704 :
705 4557 : int first_complete = !fec->fec_complete;
706 4557 : fec->cmpl_ts = fd_long_if( first_complete, ts, fec->cmpl_ts );
707 4557 : fec->data_rcvd = fd_uint_if( first_complete, data_rcvd, fec->data_rcvd );
708 4557 : fec->parity_rcvd = fd_uint_if( first_complete, parity_rcvd, fec->parity_rcvd );
709 4557 : fec->repair_rcvd = fd_uint_if( first_complete, repair_rcvd, fec->repair_rcvd );
710 4557 : fec->mr = key;
711 4557 : fec->fec_complete = 1;
712 4557 : fec->data_complete = !!( last_shred->data.flags & FD_SHRED_DATA_FLAG_DATA_COMPLETE );
713 4557 : fec->is_leader |= !!is_leader; /* a completion again from the network does not clear our own */
714 :
715 4557 : ulong slot = last_shred->slot; /* fd_shred_t is packed, the map query needs an aligned key */
716 4557 : fd_repair_slot_meta_t * meta = fd_repair_slot_meta( self, slot );
717 4557 : fd_repair_blk_t * pool = self->blk_pool;
718 4557 : fd_repair_blk_t * eager = fd_repair_blk_pool_ele( pool, meta->eager_blk_idx );
719 4557 : int cmpl = eager && !meta->invalidated && eager->cmpl_fec_cnt && !memcmp( &eager->dmr, &hash_null, sizeof(fd_mr32_t) );
720 9100 : for( uint k=0U; cmpl && k<eager->cmpl_fec_cnt; k++ ) {
721 4543 : 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 4543 : }
723 4557 : meta->leader |= (uint)!!is_leader;
724 4557 : if( FD_UNLIKELY( is_leader && eager ) ) eager->eager = 0; /* our own, never repaired */
725 4557 : 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 4557 : if( FD_UNLIKELY( cmpl ) ) {
727 992 : compute_dmr( self, eager );
728 992 : link_orphans( self, eager ); /* the blks naming its dmr waited for it */
729 992 : dedup( self, eager, ts );
730 992 : 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 992 : }
732 :
733 4557 : for( fd_repair_blk_t * blk = fd_repair_blk_map_ele_query( self->blk_map, &slot, NULL, pool );
734 9113 : blk;
735 4557 : blk = (fd_repair_blk_t *)fd_repair_blk_map_ele_next_const( blk, NULL, pool ) ) {
736 4556 : if( FD_LIKELY( blk->fecs[ fec->fec_idx ]!=fd_repair_fec_pool_idx( self->fec_pool, fec ) ) ) continue;
737 4556 : uint end = fd_uint_if( !!blk->cmpl_fec_cnt, blk->cmpl_fec_cnt, (uint)self->fec_blk_max );
738 9112 : while( blk->buff_fec_cnt<end
739 9112 : && blk->fecs[ blk->buff_fec_cnt ]!=fd_repair_fec_pool_idx_null( self->fec_pool )
740 9112 : && fd_repair_fec_pool_ele( self->fec_pool, blk->fecs[ blk->buff_fec_cnt ] )->fec_complete ) {
741 4556 : blk->buff_fec_cnt++;
742 4556 : }
743 4556 : if( FD_LIKELY( first_complete ) ) {
744 4556 : blk->telemetry.turbine_shred_cnt += turbine_cnt;
745 4556 : blk->telemetry.repair_shred_cnt += repair_cnt;
746 4556 : blk->telemetry.recovered_shred_cnt += recovered_cnt;
747 4556 : blk->telemetry.last_cmpl_fec_idx = fec->fec_idx*FD_FEC_SHRED_CNT;
748 4556 : }
749 4556 : 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 4556 : 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 4556 : consume( self, blk );
752 4556 : if( FD_UNLIKELY( blk->cmpl_fec_cnt && blk->cons_fec_cnt==blk->cmpl_fec_cnt ) ) cascade( self, blk );
753 4556 : }
754 4557 : return fec;
755 4557 : }
756 :
757 : void
758 : fd_repair_fec_evicted( fd_repair_t * self,
759 : ulong slot,
760 : uint fec_set_idx,
761 0 : fd_mr_t const * fec_mr ) {
762 0 : uint k = fec_set_idx/FD_FEC_SHRED_CNT;
763 0 : fd_repair_fec_t * fec = fd_repair_fec_map_ele_query( self->fec_map, fec_mr, NULL, self->fec_pool );
764 0 : if( FD_UNLIKELY( !fec || fec->fec_complete || fec->slot!=slot || fec->fec_idx!=k ) ) return;
765 :
766 0 : fec->data_rcvd = 0U; /* its req, still waiting since the set is incomplete, asks for every shred again */
767 0 : }
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 0 : long ts ) {
776 :
777 0 : uint fec_idx = fec_set_idx / FD_FEC_SHRED_CNT;
778 :
779 0 : fd_repair_blk_t * blk = fd_repair_blk_map_ele_query( self->blk_map, &slot, NULL, self->blk_pool );
780 0 : 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 0 : if( FD_UNLIKELY( !blk ) ) return NULL; /* blk was pruned while the response was in flight */
782 0 : blk->telemetry.fec_root_res_cnt++;
783 0 : blk->telemetry.first_meta_res_ts = fd_long_if( !blk->telemetry.first_meta_res_ts, ts, blk->telemetry.first_meta_res_ts );
784 :
785 0 : 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 0 : fd_repair_slot_meta_t * meta = fd_repair_slot_meta( self, slot );
788 0 : fd_repair_blk_t * eager = fd_repair_blk_pool_ele( self->blk_pool, meta->eager_blk_idx );
789 0 : 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 0 : if( FD_UNLIKELY( eqvoc ) ) fd_repair_slot_invalidated( self, slot, FD_EVENT_BLOCK_RECEIVED_CANCELLED_REASON_MERKLE_ROOT_MISMATCH, ts );
791 :
792 0 : fd_repair_fec_t * fec = fd_repair_fec_map_ele_query( self->fec_map, fec_mr, NULL, self->fec_pool );
793 0 : 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 0 : if( FD_UNLIKELY( !fec ) ) {
795 0 : FD_TEST( fd_repair_fec_pool_free( self->fec_pool ) );
796 0 : fec = fd_repair_fec_pool_ele_acquire( self->fec_pool );
797 0 : fec->mr = *fec_mr;
798 0 : fec->fec_idx = fec_idx;
799 0 : fec->slot = slot;
800 0 : fec->fec_complete = 0;
801 0 : fec->data_complete = 0;
802 0 : fec->first_ts = 0L;
803 0 : fec->cmpl_ts = 0L;
804 0 : fec->is_leader = 0;
805 0 : fec->data_rcvd = 0U;
806 0 : fec->parity_rcvd = 0U;
807 0 : fec->repair_rcvd = 0U;
808 0 : fec->update_parent.new_parent_slot = ULONG_MAX;
809 0 : fd_repair_fec_map_ele_insert( self->fec_map, fec, self->fec_pool );
810 0 : }
811 0 : fec->is_notar = 1;
812 0 : blk->fecs[ fec_idx ] = fd_repair_fec_pool_idx( self->fec_pool, fec );
813 :
814 0 : if( FD_UNLIKELY( fec->update_parent.new_parent_slot!=ULONG_MAX ) ) update_parent( self, slot, fec_idx, ts );
815 0 : if( FD_UNLIKELY( fec->data_complete ) ) update_parent( self, slot, fec_idx+1U, ts );
816 :
817 0 : if( FD_LIKELY( !fec->fec_complete ) ) return fec;
818 :
819 0 : uint end = fd_uint_if( !!blk->cmpl_fec_cnt, blk->cmpl_fec_cnt, (uint)self->fec_blk_max );
820 0 : while( blk->buff_fec_cnt<end
821 0 : && blk->fecs[ blk->buff_fec_cnt ]!=fd_repair_fec_pool_idx_null( self->fec_pool )
822 0 : && fd_repair_fec_pool_ele( self->fec_pool, blk->fecs[ blk->buff_fec_cnt ] )->fec_complete ) {
823 0 : blk->buff_fec_cnt++;
824 0 : }
825 0 : 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 0 : consume( self, blk );
827 0 : if( FD_UNLIKELY( blk->cmpl_fec_cnt && blk->cons_fec_cnt==blk->cmpl_fec_cnt ) ) cascade( self, blk );
828 0 : return fec;
829 0 : }
830 :
831 : void
832 : fd_repair_root_advanced( fd_repair_t * self,
833 : ulong slot,
834 0 : fd_mr32_t const * blk_mr ) {
835 0 : fd_repair_slot_meta_t const * meta = &self->slot_meta[ slot % self->slot_max ];
836 0 : 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 0 : FD_CHECK_CRIT( !existing_final || !memcmp( &existing_final->dmr, blk_mr, sizeof(fd_mr32_t) ), "consensus safety violation" );
838 :
839 0 : ulong root = self->root;
840 0 : 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 0 : for( ulong s=root; s<=slot; s++ ) {
842 0 : fd_repair_blk_t * next;
843 0 : for( fd_repair_blk_t * blk = fd_repair_blk_map_ele_query( self->blk_map, &s, NULL, self->blk_pool );
844 0 : blk;
845 0 : blk = next ) {
846 0 : next = (fd_repair_blk_t *)fd_repair_blk_map_ele_next_const( blk, NULL, self->blk_pool );
847 0 : if( FD_UNLIKELY( !blk->telemetry.reported && self->telemetry.report ) ) { blk->telemetry.reported = 1; self->telemetry.report( self->telemetry.ctx, blk ); }
848 0 : for( ulong k=0UL; k<self->fec_blk_max; k++ ) {
849 0 : ulong idx = blk->fecs[ k ];
850 0 : blk->fecs[ k ] = fd_repair_fec_pool_idx_null( self->fec_pool );
851 0 : if( FD_LIKELY( idx==fd_repair_fec_pool_idx_null( self->fec_pool ) ) ) continue;
852 0 : fd_repair_fec_t * fec = fd_repair_fec_pool_ele( self->fec_pool, idx );
853 0 : 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 0 : fd_repair_fec_map_ele_remove_fast( self->fec_map, fec, self->fec_pool );
855 0 : fd_repair_fec_pool_ele_release ( self->fec_pool, fec );
856 0 : }
857 0 : if( FD_UNLIKELY( s==slot && !memcmp( &blk->dmr, blk_mr, sizeof(fd_mr32_t) ) ) ) { /* the new root */
858 0 : blk_treap_remove( self, blk ); /* the root is never repaired */
859 0 : 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 0 : fd_repair_slot_meta( self, slot )->final_blk_idx = (uint)fd_repair_blk_pool_idx( self->blk_pool, blk );
861 0 : blk->eager = 0;
862 0 : root_blk = blk;
863 0 : continue;
864 0 : }
865 :
866 0 : unlink( self, blk );
867 0 : 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 0 : blk_treap_remove( self, blk );
869 0 : fd_repair_slot_meta_t * meta = fd_repair_slot_meta( self, s );
870 0 : 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 0 : 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 0 : fd_repair_blk_map_ele_remove_fast( self->blk_map, blk, self->blk_pool );
873 0 : fd_repair_blk_pool_ele_release ( self->blk_pool, blk );
874 0 : }
875 0 : }
876 0 : self->root_blk = root_blk;
877 0 : self->root = slot;
878 0 : }
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 150351 : long ts ) {
885 :
886 150351 : fd_mr_t key;
887 150351 : 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 150351 : fd_repair_fec_t * fec = fd_repair_fec_map_ele_query( self->fec_map, &key, NULL, self->fec_pool );
894 150351 : uint fec_idx = shred->idx / FD_FEC_SHRED_CNT;
895 150351 : if( FD_UNLIKELY( fec && ( fec->slot!=shred->slot || fec->fec_idx!=fec_idx ) ) ) return; /* a 20-byte root collision */
896 150351 : 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 150351 : if( FD_UNLIKELY( fec && !fec->first_ts ) ) fec->first_ts = ts;
898 :
899 150351 : fd_block_marker_t update[1];
900 150351 : 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 150351 : int data_complete = !!( shred->data.flags & FD_SHRED_DATA_FLAG_DATA_COMPLETE );
902 :
903 150351 : if( FD_UNLIKELY( parent_update && fec ) ) { fec->update_parent = update->update_parent; update_parent( self, shred->slot, fec_idx, ts ); }
904 150351 : 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 150351 : ulong parent_slot = shred->slot - shred->data.parent_off;
909 150351 : fd_repair_blk_t * pool = self->blk_pool;
910 150351 : ulong null = fd_repair_blk_pool_idx_null( pool );
911 150351 : fd_repair_slot_meta_t * meta = fd_repair_slot_meta( self, shred->slot );
912 150351 : fd_repair_blk_t const * fin = fd_repair_blk_pool_ele_const( pool, meta->final_blk_idx );
913 150351 : int fin_done = fin && fin->cmpl_fec_cnt && fin->buff_fec_cnt==fin->cmpl_fec_cnt;
914 :
915 150351 : 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 150351 : 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 150351 : fd_repair_blk_t * blk = fd_repair_blk_pool_ele( pool, meta->eager_blk_idx );
918 150351 : if( FD_UNLIKELY( blk->parent_slot==ULONG_MAX ) ) blk->parent_slot = parent_slot; /* created empty by a child or catchup */
919 150351 : 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 150351 : fd_block_marker_t marker[1];
924 150351 : 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 150351 : 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 150351 : int slot_complete = !!( shred->data.flags & FD_SHRED_DATA_FLAG_SLOT_COMPLETE );
928 150351 : 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 150351 : int parent_conflict = bad_header || blk->init_parent_slot!=parent_slot;
930 150351 : int complete_conflict = ( blk->cmpl_fec_cnt && fec_idx>=blk->cmpl_fec_cnt ) || ( slot_complete && fec_idx+1U<blk->rcvd_fec_cnt );
931 150351 : if( FD_UNLIKELY( eqvoc ) ) { fd_repair_slot_invalidated( self, shred->slot, FD_EVENT_BLOCK_RECEIVED_CANCELLED_REASON_MERKLE_ROOT_MISMATCH, ts ); return; }
932 150351 : 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 150351 : if( FD_UNLIKELY( complete_conflict ) ) { fd_repair_slot_invalidated( self, shred->slot, FD_EVENT_BLOCK_RECEIVED_CANCELLED_REASON_SLOT_COMPLETE_MISMATCH, ts ); return; }
934 150351 : 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 0 : fd_repair_slot_invalidated( self, shred->slot, FD_EVENT_BLOCK_RECEIVED_CANCELLED_REASON_INVALID_UPDATE_PARENT, ts );
937 0 : return;
938 0 : }
939 :
940 150351 : if( FD_UNLIKELY( parent_dmr ) ) { /* shred 0 again names the same parent, the key must not change while in orphan_map */
941 1001 : if( FD_UNLIKELY( blk!=self->root_blk && blk->parent==null ) ) fd_repair_blk_orphan_map_ele_remove_fast( self->orphan_map, blk, pool );
942 1001 : blk->parent_dmr = *parent_dmr;
943 1001 : if( FD_UNLIKELY( blk!=self->root_blk && blk->parent==null ) ) fd_repair_blk_orphan_map_ele_insert ( self->orphan_map, blk, pool );
944 1001 : }
945 150351 : 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 0 : fd_repair_slot_meta_t * pmeta = fd_repair_slot_meta( self, parent_slot );
947 0 : 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 0 : }
949 150351 : if( FD_UNLIKELY( slot_complete ) ) blk->cmpl_fec_cnt = fec_idx+1U;
950 150351 : if( FD_UNLIKELY( slot_complete || fec_idx+1U>blk->rcvd_fec_cnt ) ) { /* its repair limit moved */
951 6541 : blk->eager_ts = fd_long_if( fec_idx+1U>blk->rcvd_fec_cnt, ts, blk->eager_ts );
952 6541 : fd_repair_blk_treap_insert( self, blk );
953 6541 : }
954 :
955 150351 : if( FD_UNLIKELY( !fec ) ) {
956 4557 : FD_TEST( fd_repair_fec_pool_free( self->fec_pool ) );
957 4557 : fec = fd_repair_fec_pool_ele_acquire( self->fec_pool );
958 4557 : fec->mr = key;
959 4557 : fec->fec_idx = fec_idx;
960 4557 : fec->slot = shred->slot;
961 4557 : fec->fec_complete = 0;
962 4557 : fec->data_complete = 0;
963 4557 : fec->first_ts = ts;
964 4557 : fec->cmpl_ts = 0L;
965 4557 : fec->is_leader = 0;
966 4557 : fec->is_notar = 0;
967 4557 : fec->data_rcvd = 0U;
968 4557 : fec->parity_rcvd = 0U;
969 4557 : fec->repair_rcvd = 0U;
970 4557 : fec->update_parent.new_parent_slot = ULONG_MAX;
971 4557 : fd_repair_fec_map_ele_insert( self->fec_map, fec, self->fec_pool );
972 4557 : }
973 150351 : blk->fecs[ fec_idx ] = fd_repair_fec_pool_idx( self->fec_pool, fec );
974 150351 : blk->rcvd_fec_cnt = fd_uint_max( blk->rcvd_fec_cnt, fec_idx+1U );
975 150351 : 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 150351 : if( FD_UNLIKELY( parent_update ) ) { fec->update_parent = update->update_parent; update_parent( self, shred->slot, fec_idx, ts ); }
978 150351 : if( FD_UNLIKELY( data_complete ) ) { fec->data_complete = 1; update_parent( self, shred->slot, fec_idx+1U, ts ); }
979 150351 : }
980 :
981 : void
982 : fd_repair_slot_invalidated( fd_repair_t * self,
983 : ulong slot,
984 : int reason,
985 0 : long ts ) {
986 0 : fd_repair_slot_meta_t * meta = fd_repair_slot_meta( self, slot );
987 0 : fd_repair_blk_t * eager = fd_repair_blk_pool_ele( self->blk_pool, meta->eager_blk_idx );
988 0 : int first = !meta->invalidated;
989 0 : meta->invalidated = 1;
990 0 : if( FD_LIKELY( eager ) ) {
991 0 : eager->telemetry.cancelled_ts = fd_long_if( !eager->telemetry.cancelled_reason, ts, eager->telemetry.cancelled_ts );
992 0 : eager->telemetry.cancelled_reason = (uchar)reason;
993 0 : eager->eager = 0;
994 0 : }
995 0 : 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 0 : 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 0 : }
998 :
999 : fd_repair_slot_meta_t *
1000 : fd_repair_slot_meta( fd_repair_t * self,
1001 197766 : ulong slot ) {
1002 197766 : fd_repair_slot_meta_t * meta = &self->slot_meta[ slot % self->slot_max ];
1003 197766 : if( FD_UNLIKELY( meta->slot!=slot ) ) {
1004 2009 : meta->slot = slot;
1005 2009 : meta->eager_blk_idx = (uint)fd_repair_blk_pool_idx_null( self->blk_pool );
1006 2009 : meta->notar_blk_idx = (uint)fd_repair_blk_pool_idx_null( self->blk_pool );
1007 2009 : meta->final_blk_idx = (uint)fd_repair_blk_pool_idx_null( self->blk_pool );
1008 2009 : meta->invalidated = 0;
1009 2009 : meta->skipped = 0;
1010 2009 : meta->leader = 0;
1011 2009 : }
1012 197766 : return meta;
1013 197766 : }
1014 :
1015 : void
1016 : fd_repair_slot_skipped( fd_repair_t * self,
1017 0 : ulong slot ) {
1018 0 : fd_repair_slot_meta_t * meta = fd_repair_slot_meta( self, slot );
1019 0 : meta->skipped = 1; /* late repair requests or shreds for the slot must not recreate blks in it */
1020 :
1021 0 : fd_repair_blk_t * next;
1022 0 : for( fd_repair_blk_t * blk = fd_repair_blk_map_ele_query( self->blk_map, &slot, NULL, self->blk_pool );
1023 0 : blk;
1024 0 : blk = next ) {
1025 0 : next = (fd_repair_blk_t *)fd_repair_blk_map_ele_next_const( blk, NULL, self->blk_pool );
1026 0 : prune( self, blk );
1027 0 : }
1028 0 : }
|
