Line data Source code
1 : #include <stdio.h> /* for vsnprintf */
2 : #include <stdarg.h> /* for va_list */
3 :
4 : #include "fd_sched.h"
5 : #include "../../flamenco/alpenglow/fd_block_marker_serde.h"
6 : #include "fd_execrp.h" /* for poh hash value */
7 : #include "../../ballet/sha256/fd_sha256.h"
8 : #include "../../disco/fd_disco_base.h" /* for FD_MAX_TXN_PER_SLOT_SHRED */
9 : #include "../../disco/fd_txn_p.h"
10 : #include "../../disco/metrics/fd_metrics.h" /* for fd_metrics_convert_seconds_to_ticks and etc. */
11 : #include "../../disco/pack/fd_chkdup.h"
12 : #include "../../disco/shred/fd_shredder.h" /* FD_SHREDDER_CHAINED_FEC_SET_PAYLOAD_SZ */
13 : #include "../../flamenco/runtime/fd_runtime.h" /* for fd_runtime_load_txn_address_lookup_tables */
14 : #include "../../flamenco/runtime/fd_system_ids.h"
15 : #include "../../flamenco/runtime/sysvar/fd_sysvar_slot_hashes.h" /* for ALUTs */
16 :
17 360 : #define FD_SCHED_MAX_STAGING_LANES_LOG (2)
18 360 : #define FD_SCHED_MAX_STAGING_LANES (1UL<<FD_SCHED_MAX_STAGING_LANES_LOG)
19 : #define FD_SCHED_MAX_EXEC_TILE_CNT (64UL)
20 810 : #define FD_SCHED_MAX_PRINT_BUF_SZ (2UL<<20)
21 : #define FD_SCHED_POISON_MAX_ACCT_PER_SLOT (64UL)
22 :
23 318 : #define FD_SCHED_MAX_POH_HASHES_PER_TASK (4096UL) /* This seems to be the sweet spot. */
24 :
25 : /* 64 ticks per slot, and a single gigantic microblock containing min
26 : size transactions. */
27 : FD_STATIC_ASSERT( FD_MAX_TXN_PER_SLOT_SHRED==((FD_SHRED_DATA_PAYLOAD_MAX_PER_SLOT-65UL*sizeof(fd_microblock_hdr_t))/FD_TXN_MIN_SERIALIZED_SZ), max_txn_per_slot_shred );
28 :
29 : /* We size the buffer to be able to hold residual data from the previous
30 : FEC set that only becomes parseable after the next FEC set is
31 : ingested, as well as the incoming FEC set. The largest minimally
32 : parseable unit of data is a transaction. So that much data may
33 : straddle FEC set boundaries. Other minimally parseable units of data
34 : include the microblock header and the microblock count within a
35 : batch. */
36 6 : #define FD_SCHED_MAX_PAYLOAD_PER_FEC (63985UL)
37 : FD_STATIC_ASSERT( FD_SCHED_MAX_PAYLOAD_PER_FEC>=FD_SHREDDER_CHAINED_FEC_SET_PAYLOAD_SZ, bump sched fec size bound ); /* FD_SHREDDER_CHAINED_FEC_SET_PAYLOAD_SZ is the bound we want, but older ledgers have larger FEC sets. */
38 : #define FD_SCHED_MAX_FEC_BUF_SZ (FD_SCHED_MAX_PAYLOAD_PER_FEC+FD_TXN_MTU)
39 : FD_STATIC_ASSERT( FD_TXN_MTU>=sizeof(fd_microblock_hdr_t), resize buffer for residual data );
40 : FD_STATIC_ASSERT( FD_TXN_MTU>=sizeof(ulong), resize buffer for residual data );
41 :
42 3 : #define FD_SCHED_MAX_TXN_PER_FEC ((FD_SCHED_MAX_PAYLOAD_PER_FEC-1UL)/FD_TXN_MIN_SERIALIZED_SZ+1UL) /* 478 */
43 3 : #define FD_SCHED_MAX_MBLK_PER_FEC ((FD_SCHED_MAX_PAYLOAD_PER_FEC-1UL)/sizeof(fd_microblock_hdr_t)+1UL) /* 1334 */
44 :
45 : FD_STATIC_ASSERT( FD_SCHED_MIN_DEPTH>=FD_SCHED_MAX_TXN_PER_FEC, limits );
46 : FD_STATIC_ASSERT( FD_SCHED_MAX_DEPTH<=FD_RDISP_MAX_DEPTH, limits );
47 : FD_STATIC_ASSERT( FD_SCHED_MAX_DEPTH<=UINT_MAX, txn_idx_width );
48 :
49 90 : #define FD_SCHED_MAGIC (0xace8a79c181f89b6UL) /* echo -n "fd_sched_v0" | sha512sum | head -c 16 */
50 :
51 : struct fd_sched_mblk {
52 : ulong start_txn_idx; /* inclusive parse idx */
53 : ulong end_txn_idx; /* non-inclusive parse idx */
54 : ulong curr_txn_idx; /* next txn to mixin, parse idx in block */
55 : ulong hashcnt; /* number of pure hashes, excluding final mixin */
56 : ulong curr_hashcnt;
57 : fd_hash_t end_hash[ 1 ];
58 : fd_hash_t curr_hash[ 1 ];
59 : uint curr_sig_cnt;
60 : uint next;
61 : uint mixin_txn_idx; /* rdisp pool idx of the next txn to mixin */
62 : int is_tick;
63 : };
64 : typedef struct fd_sched_mblk fd_sched_mblk_t;
65 :
66 : #define SLIST_NAME mblk_slist
67 : #define SLIST_ELE_T fd_sched_mblk_t
68 249 : #define SLIST_IDX_T uint
69 507 : #define SLIST_NEXT next
70 : #include "../../util/tmpl/fd_slist.c"
71 :
72 : #define SET_NAME txn_bitset
73 : #define SET_MAX FD_SCHED_MAX_DEPTH
74 : #include "../../util/tmpl/fd_set.c"
75 :
76 : struct fd_sched_block {
77 : ulong slot;
78 : ulong parent_slot;
79 : ulong parent_idx; /* Index of the parent in the pool. */
80 : ulong child_idx; /* Index of the left-child in the pool. */
81 : ulong sibling_idx; /* Index of the right-sibling in the pool. */
82 :
83 : /* Counters. */
84 : uint txn_parsed_cnt;
85 : /* txn_queued_cnt = txn_parsed_cnt-txn_in_flight_cnt-txn_done_cnt */
86 : uint txn_exec_in_flight_cnt;
87 : uint txn_exec_done_cnt;
88 : uint txn_sigverify_in_flight_cnt;
89 : uint txn_sigverify_done_cnt;
90 : uint poh_hashing_in_flight_cnt; /* number of in-flight PoH batch tasks */
91 : uint poh_mblk_in_flight_cnt; /* number of individual in-flight PoH jobs across batches */
92 : uint poh_hashing_done_cnt;
93 : uint poh_hash_cmp_done_cnt; /* poh_hashing_done_cnt==poh_hash_cmp_done_cnt+len(mixin_in_progress) */
94 : uint txn_done_cnt; /* A transaction is considered done when all types of tasks associated with it are done. */
95 : uint shred_cnt;
96 : uint shred_scan_idx; /* First shred boundary not before shred_scan_off. */
97 : uint shred_scan_off; /* Block byte offset at the start of shred_scan_idx. */
98 : uint mblk_cnt; /* Total number of microblocks, including ticks and non ticks.
99 : mblk_cnt==len(unhashed)+len(hashing_in_progress)+poh_mblk_in_flight_cnt+len(mixin_in_progress)+hash_cmp_done_cnt */
100 : uint mblk_tick_cnt; /* Total number of tick microblocks. */
101 : uint mblk_freed_cnt; /* This is ==hash_cmp_done_cnt in most cases, except for aborted
102 : blocks, where the freed cnt will catch up to mblk_cnt and surpass
103 : hash_cmp_done_cnt when the block is reaped. */
104 : uint mblk_unhashed_cnt; /* ==len(unhashed) */
105 : ulong hashcnt; /* How many hashes this block wants replay to do. A mixin/record counts as one hash. */
106 : ulong txn_pool_max_popcnt; /* Peak transaction pool occupancy during the time this block was replaying. */
107 : ulong mblk_pool_max_popcnt; /* Peak mblk pool occupancy. */
108 : ulong block_pool_max_popcnt; /* Peak block pool occupancy. */
109 : uint txn_idx_tail; /* Most recently parsed rdisp pool index. */
110 : uint txn_sigverify_next_idx; /* Next rdisp pool index to dispatch for sigverify, or 0 if caught up. */
111 : uint parse_mblk_idx; /* mblk pool index currently receiving parsed transactions. */
112 :
113 : /* PoH verify. */
114 : fd_hash_t poh_hash[ 1 ]; /* running end_hash of last parsed mblk */
115 : int last_mblk_is_tick;
116 : mblk_slist_t mblks_unhashed[ 1 ]; /* A microblock, once parsed out, is in one of these queues. It
117 : generally progresses from unhashed to hashing to mixin. When a
118 : microblock is being hashed/in-flight, it'll be transiently out of
119 : any of the queues. Once a microblock progresses through all stages
120 : of work, it'll be immediately freed. */
121 : mblk_slist_t mblks_hashing_in_progress[ 1 ];
122 : mblk_slist_t mblks_mixin_in_progress[ 1 ];
123 : uchar bmtree_mem[ FD_BMTREE_COMMIT_FOOTPRINT(0) ] __attribute__((aligned(FD_BMTREE_COMMIT_ALIGN)));
124 : fd_bmtree_commit_t * bmtree;
125 : ulong tick_hashcnt_wmk; /* All ticks in a valid block must accumulate the same number of
126 : hashes since the previous tick, or since block start, and this hash
127 : count must match hashes_per_tick for the block. */
128 : ulong curr_tick_hashcnt; /* Starts at 0, accumulates hashcnt, resets to 0 on the next tick. */
129 : ulong tick_height; /* Block is built off of a parent block with this many ticks. */
130 : ulong max_tick_height; /* Block should end with precisely this many ticks. */
131 : ulong hashes_per_tick; /* Fixed per block, feature gated, known after bank clone. */
132 : int inconsistent_hashes_per_tick;
133 : int zero_hash_tick;
134 :
135 : /* Parser state. */
136 : uchar txn[ FD_TXN_MAX_SZ ] __attribute__((aligned(alignof(fd_txn_t))));
137 : ulong mblks_rem; /* Number of microblocks remaining in the current batch. */
138 : ulong txns_rem; /* Number of transactions remaining in the current microblock. */
139 : uint fec_buf_sz; /* Size of the fec_buf in bytes. */
140 : uint fec_buf_soff; /* Starting offset into fec_buf for unparsed transactions. */
141 : uint fec_buf_boff; /* Byte offset into raw block data of the first byte currently in fec_buf */
142 : uint poison_cnt; /* [0, FD_SCHED_POISON_MAX_ACCT_PER_SLOT) */
143 : fd_acct_addr_t poison[ FD_SCHED_POISON_MAX_ACCT_PER_SLOT ]; /* Poison set to handle loader v3 implied programdata accounts.
144 :
145 : A transaction that lists a loader v3 program account P is charged
146 : for, and gated on, P's implicit programdata account PD, which the
147 : transaction does not have to declare. The dispatcher therefore
148 : establishes no dependency for said transaction against a
149 : transaction that writes PD without also touching P, for example a
150 : simple lamports transfer into PD, or a Close on an Unintialized PD.
151 : Every loader v3 instruction that changes a live PD's size or
152 : liveness (from alive to dead) does write lock P (except for the
153 : aforementioned Close on Unintialized PD). Simple transfers cannot
154 : debit PD since it's a PDA.
155 :
156 : So, when a loader v3 instruction that could modify PD is inserted,
157 : its writable accounts are added to a poison set, and any later
158 : transaction that writes a set member is inserted serializing. That
159 : sequences the unordered writer of PD against any implied use of PD
160 : for the rest of the block. This allows the runtime to treat the
161 : current fork's view of PD as stable.
162 :
163 : Note that this does not cover the case where the poisoning
164 : transaction (with the PD-modifying loader v3 instruction) and the
165 : PD-only transactions do not land in the same block. Non-determinism
166 : between the PD-only transaction and an implied PD transaction in
167 : that case is a protocol bug. */
168 : long fec_completed_ns; /* Network arrival (wallclock ns) of the FEC set being ingested; txns
169 : parse out only once the FEC completing their bytes arrives, so this
170 : is stamped on every txn parsed during the current ingest. */
171 : uint poison_serialize:1; /* Serialize everything in the rest of the block. Set when the poison
172 : set overflows or we couldn't maintain the poison property for any
173 : other reason. */
174 : uint fec_eob:1; /* FEC end-of-batch: set if the last FEC set in the batch is being
175 : ingested. */
176 : uint fec_sob:1; /* FEC start-of-batch: set if the parser expects to be parsing out a
177 : batch header. */
178 :
179 : /* Block state. */
180 : uint fec_eos:1; /* FEC end-of-stream: set if the last FEC set in the block has been
181 : ingested. */
182 : uint rooted:1; /* Set if the block is rooted. */
183 : uint dying:1; /* Set if the block has been abandoned and no transactions should be
184 : scheduled from it. */
185 : uint discarded:1; /* Set if the block went down with a discarded (not invalid) lineage:
186 : its own discard or an ancestor's. This field, along with
187 : dead_reason, can be in one of three possible combinations when a
188 : block is dead:
189 :
190 : dead_reason!=DEAD_ANCESTOR, discarded initialized to 0: invalid block due to dead_reason
191 : dead_reason==DEAD_ANCESTOR, discarded==0: invalid lineage
192 : dead_reason==DEAD_ANCESTOR||NONE, discarded==1: discarded lineage */
193 : uint refcnt:1; /* Starts at 1 when the block is added, set to 0 if caller has been
194 : informed to decrement refcnt for sched. */
195 : uint in_sched:1; /* Set if the block is being tracked by the scheduler. */
196 : uint in_rdisp:1; /* Set if the block is being tracked by the dispatcher, either as staged
197 : or unstaged. */
198 : uint block_start_signaled:1; /* Set if the start-of-block sentinel has been dispatched. */
199 : uint block_end_signaled:1; /* Set if the end-of-block sentinel has been dispatched. */
200 : uint block_start_done:1; /* Set if the start-of-block processing has been completed. */
201 : uint block_end_done:1; /* Set if the end-of-block processing has been completed. */
202 : uint staged:1; /* Set if the block is in a dispatcher staging lane; a staged block is
203 : tracked by the dispatcher. */
204 : ulong staging_lane; /* Ignored if staged==0. */
205 : ulong luf_depth; /* Depth of longest unstaged fork starting from this node; only
206 : stageable unstaged descendants are counted. */
207 : int dead_reason; /* One of FD_SCHED_DEAD_REASON_*; records the first reason the block
208 : was ruled invalid (set-once via record_dead_reason), NONE otherwise. */
209 : uchar fec_buf[ FD_SCHED_MAX_FEC_BUF_SZ ]; /* The previous FEC set could have some residual data that only becomes
210 : parseable after the next FEC set is ingested. */
211 :
212 : /* Alpenglow block footer, deserialized out of the marker batch at
213 : parse time. footer_seen is set if the block carries a footer
214 : marker and it is seen by sched; footer is only meaningful in that
215 : case. */
216 : fd_block_footer_t footer;
217 :
218 : /* Alpenglow block structure, mirroring agave's BlockComponentStage
219 : as a set of "seen" flags. Only maintained when sched->is_alpenglow.
220 : Together with mblk_cnt they determine what may come next:
221 :
222 : agave stage header footer alpentick mblk_cnt
223 : PreParentMarker 0 0 0 0
224 : AcceptingGenesisOrEntries 1 0 0 0 (and no genesis cert yet)
225 : AcceptingEntriesOrFooter 1 0 0 *
226 : AcceptingAlpentick 1 1 0 *
227 : Done 1 1 1 * */
228 : int header_seen;
229 : int genesis_cert_seen;
230 : int footer_seen;
231 : int alpentick_seen;
232 : };
233 : typedef struct fd_sched_block fd_sched_block_t;
234 :
235 : FD_STATIC_ASSERT( sizeof(fd_sched_mblk_t)==120UL, fd_sched_mblk );
236 : FD_STATIC_ASSERT( sizeof(fd_sched_txn_info_t)==192UL, fd_sched_txn_info );
237 : FD_STATIC_ASSERT( sizeof(fd_sched_block_t)==75840UL, fd_sched_block );
238 : FD_STATIC_ASSERT( sizeof(fd_hash_t)==sizeof(((fd_microblock_hdr_t *)0)->hash), unexpected poh hash size );
239 :
240 :
241 : struct fd_sched_metrics {
242 : uint block_added_cnt;
243 : uint block_added_staged_cnt;
244 : uint block_added_unstaged_cnt;
245 : uint block_added_dead_ood_cnt;
246 : uint block_removed_cnt;
247 : uint block_abandoned_cnt;
248 : uint block_bad_cnt;
249 : uint block_promoted_cnt;
250 : uint block_demoted_cnt;
251 : uint deactivate_no_child_cnt;
252 : uint deactivate_no_txn_cnt;
253 : uint deactivate_pruned_cnt;
254 : uint deactivate_abandoned_cnt;
255 : uint lane_switch_cnt;
256 : uint lane_promoted_cnt;
257 : uint lane_demoted_cnt;
258 : uint fork_observed_cnt;
259 : uint alut_success_cnt;
260 : uint alut_serializing_cnt;
261 : uint poison_latch_overflow_cnt;
262 : uint poison_latch_alt_cnt;
263 : uint poison_cnt_wmk;
264 : uint txn_poison_serializing_cnt;
265 : uint txn_poisoned_cnt;
266 : uint txn_abandoned_parsed_cnt;
267 : uint txn_abandoned_exec_done_cnt;
268 : uint txn_abandoned_done_cnt;
269 : uint txn_max_in_flight_cnt;
270 : ulong txn_weighted_in_flight_cnt;
271 : ulong txn_weighted_in_flight_tickcount;
272 : ulong txn_none_in_flight_tickcount;
273 : ulong txn_parsed_cnt;
274 : ulong txn_exec_done_cnt;
275 : ulong txn_sigverify_done_cnt;
276 : ulong txn_mixin_done_cnt;
277 : ulong txn_done_cnt;
278 : ulong mblk_parsed_cnt;
279 : ulong mblk_poh_hashed_cnt;
280 : ulong mblk_poh_done_cnt;
281 : ulong bytes_ingested_cnt;
282 : ulong bytes_ingested_unparsed_cnt;
283 : ulong bytes_dropped_cnt;
284 : ulong fec_cnt;
285 : };
286 : typedef struct fd_sched_metrics fd_sched_metrics_t;
287 :
288 : #define DEQUE_NAME ref_q
289 102 : #define DEQUE_T ulong
290 : #include "../../util/tmpl/fd_deque_dynamic.c"
291 :
292 : struct fd_sched {
293 : fd_acct_addr_t aluts[ 256 ]; /* Resolve ALUT accounts into this buffer for more parallelism. */
294 : char print_buf[ FD_SCHED_MAX_PRINT_BUF_SZ ];
295 : ulong print_buf_sz;
296 : ushort * shred_sz; /* Payload size of each ingested data shred, max_shreds_per_block per block pool idx. */
297 : ulong max_shreds_per_block; /* Immutable. */
298 : ulong max_txn_per_slot; /* Immutable. */
299 : ulong max_mblk_per_slot; /* Immutable, FD_SCHED_MAX_MBLK_PER_SLOT scaled with max_shreds_per_block. */
300 : fd_chkdup_t chkdup[ 1 ];
301 : fd_sched_metrics_t metrics[ 1 ];
302 : int is_alpenglow; /* set if alpenglow is enabled. */
303 : ulong canary; /* == FD_SCHED_MAGIC */
304 : ulong depth; /* Immutable. */
305 : ulong block_cnt_max; /* Immutable. */
306 : ulong exec_cnt; /* Immutable. */
307 : ulong poh_simd_min; /* Immutable. */
308 : ulong poh_simd_max; /* Immutable. */
309 : ulong poh_simd_iters_max; /* Immutable. */
310 : int bypass_poh_verify; /* Test/fuzz: skip the PoH end_hash compare in maybe_mixin. */
311 : int bypass_alut_resolution; /* Test/fuzz: skip ALUT resolution (no accdb). */
312 : long txn_in_flight_last_tick;
313 : long next_ready_last_tick;
314 : ulong next_ready_last_bank_idx;
315 : ulong root_idx;
316 : fd_rdisp_t * rdisp;
317 : ulong txn_exec_ready_bitset[ 1 ];
318 : ulong sigverify_ready_bitset[ 1 ];
319 : ulong poh_ready_bitset[ 1 ];
320 : ulong active_bank_idx; /* Index of the actively replayed block, or ULONG_MAX if no block is
321 : actively replayed; has to have a transaction to dispatch; staged
322 : blocks that have no transactions to dispatch are not eligible for
323 : being active. */
324 : ulong last_active_bank_idx;
325 : ulong staged_bitset; /* Bit i set if staging lane i is occupied. */
326 : ulong staged_head_bank_idx[ FD_SCHED_MAX_STAGING_LANES ]; /* Head of the linear chain in each staging lane, ignored if bit i is
327 : not set in the bitset. */
328 : ulong staged_popcnt_wmk;
329 : ulong txn_pool_free_cnt;
330 : fd_txn_p_t * txn_pool; /* Just a flat array. */
331 : fd_sched_txn_info_t * txn_info_pool; /* Just a flat array. */
332 : fd_sched_mblk_t * mblk_pool; /* Just a flat array. */
333 : ulong mblk_pool_free_cnt;
334 : uint mblk_pool_free_head;
335 : ulong tile_to_bank_idx[ FD_SCHED_MAX_EXEC_TILE_CNT ]; /* Index of the bank that the exec tile is executing against. */
336 : fd_sched_poh_hash_t poh_inflight[ FD_SCHED_MAX_EXEC_TILE_CNT ]; /* PoH dispatch metadata, indexed by exec tile. */
337 : txn_bitset_t exec_done_set[ txn_bitset_word_cnt ]; /* Indexed by txn_idx. */
338 : txn_bitset_t sigverify_done_set[ txn_bitset_word_cnt ]; /* Indexed by txn_idx. */
339 : txn_bitset_t poh_mixin_done_set[ txn_bitset_word_cnt ]; /* Indexed by txn_idx. */
340 : fd_sched_block_t * block_pool; /* Just a flat array. */
341 : ulong block_pool_popcnt;
342 : ulong * ref_q;
343 : };
344 : typedef struct fd_sched fd_sched_t;
345 :
346 :
347 : /* Internal helpers. */
348 :
349 : static int
350 : verify_ticks_eager( fd_sched_block_t * block );
351 :
352 : static int
353 : verify_ticks_final( fd_sched_block_t * block );
354 :
355 : static int
356 : ag_on_final( fd_sched_block_t * block );
357 :
358 : static void
359 : add_block( fd_sched_t * sched,
360 : ulong bank_idx,
361 : ulong parent_bank_idx );
362 :
363 : FD_WARN_UNUSED static int
364 : fd_sched_parse( fd_sched_t * sched, fd_sched_block_t * block, fd_sched_alut_ctx_t * alut_ctx );
365 :
366 : FD_WARN_UNUSED static int
367 : fd_sched_parse_txn( fd_sched_t * sched, fd_sched_block_t * block, fd_sched_alut_ctx_t * alut_ctx );
368 :
369 : static void
370 : dispatch_sigverify( fd_sched_t * sched, fd_sched_block_t * block, ulong bank_idx, int exec_tile_idx, fd_sched_task_t * out );
371 :
372 : static uint
373 : shred_split( fd_sched_t * sched,
374 : fd_sched_block_t * block,
375 : uint query );
376 :
377 : static void
378 : dispatch_poh( fd_sched_t * sched, fd_sched_block_t * block, ulong bank_idx, int exec_tile_idx, ulong max_cnt, fd_sched_task_t * out );
379 :
380 : static int
381 : poh_retire_mblk( fd_sched_t * sched, fd_sched_block_t * block, uint mblk_idx );
382 :
383 : static int
384 : poh_retire_ready_mblks( fd_sched_t * sched, fd_sched_block_t * block );
385 :
386 : static inline ulong
387 228 : poh_batch_max_cnt( fd_sched_t const * sched, ulong queued_cnt, ulong free_cnt, ulong threshold ) {
388 228 : ulong tile_cnt = free_cnt-threshold;
389 228 : ulong per_tile = (queued_cnt+tile_cnt-1UL)/tile_cnt;
390 228 : ulong max_cnt = fd_ulong_min( fd_ulong_max( per_tile, 1UL ), sched->poh_simd_max );
391 228 : return fd_ulong_if( max_cnt<sched->poh_simd_min, 1UL, max_cnt );
392 228 : }
393 :
394 : FD_WARN_UNUSED static int
395 : maybe_mixin( fd_sched_t * sched, fd_sched_block_t * block );
396 :
397 : static void
398 93 : free_mblk( fd_sched_t * sched, fd_sched_block_t * block, uint mblk_idx ) {
399 93 : sched->mblk_pool[ mblk_idx ].next = sched->mblk_pool_free_head;
400 93 : sched->mblk_pool_free_head = mblk_idx;
401 93 : sched->mblk_pool_free_cnt++;
402 93 : block->mblk_freed_cnt++;
403 93 : }
404 :
405 : static void
406 0 : free_mblk_slist( fd_sched_t * sched, fd_sched_block_t * block, mblk_slist_t * list ) {
407 0 : while( !mblk_slist_is_empty( list, sched->mblk_pool ) ) {
408 0 : uint idx = (uint)mblk_slist_idx_pop_head( list, sched->mblk_pool );
409 0 : free_mblk( sched, block, idx );
410 0 : }
411 0 : }
412 :
413 : static void
414 : try_activate_block( fd_sched_t * sched );
415 :
416 : static void
417 : check_or_set_active_block( fd_sched_t * sched );
418 :
419 : static void
420 : subtree_abandon( fd_sched_t * sched, fd_sched_block_t * block );
421 :
422 : static void
423 : subtree_release_refcnt( fd_sched_t * sched, fd_sched_block_t * block );
424 :
425 : static void
426 : subtree_prune( fd_sched_t * sched, ulong bank_idx, ulong except_idx );
427 :
428 : static void
429 : maybe_switch_block( fd_sched_t * sched, ulong bank_idx );
430 :
431 : FD_FN_UNUSED static ulong
432 : find_and_stage_longest_unstaged_fork( fd_sched_t * sched, int lane_idx );
433 :
434 : static ulong
435 : compute_longest_unstaged_fork( fd_sched_t * sched, ulong bank_idx );
436 :
437 : static ulong
438 : stage_longest_unstaged_fork( fd_sched_t * sched, ulong bank_idx, int lane_idx );
439 :
440 : static int
441 : lane_is_demotable( fd_sched_t * sched, int lane_idx );
442 :
443 : static ulong
444 : demote_lane( fd_sched_t * sched, int lane_idx );
445 :
446 : static inline fd_sched_block_t *
447 3450 : block_pool_ele( fd_sched_t * sched, ulong idx ) {
448 3450 : FD_TEST( idx<sched->block_cnt_max || idx==ULONG_MAX );
449 3450 : return idx==ULONG_MAX ? NULL : sched->block_pool+idx;
450 3450 : }
451 :
452 : FD_FN_UNUSED static inline int
453 0 : block_is_void( fd_sched_block_t * block ) {
454 0 : /* We've seen everything in the block and no transaction got parsed
455 0 : out. */
456 0 : return block->fec_eos && block->txn_parsed_cnt==0;
457 0 : }
458 :
459 : static inline int
460 54 : block_should_signal_end( fd_sched_block_t * block ) {
461 : /* Under the current policy of eager synchronous PoH mixin, hashing
462 : done plus fec_eos imply that all mixins have been done. */
463 54 : if( FD_UNLIKELY( !( !block->fec_eos || ((block->mblk_cnt==block->poh_hashing_done_cnt&&block->mblk_cnt==block->poh_hash_cmp_done_cnt)||block->mblk_cnt!=block->poh_hashing_done_cnt) ) ) ) FD_LOG_CRIT(( "invariant violation: slot %lu fec_eos %d mblk_cnt %u poh_hashing_done_cnt %u poh_hash_cmp_done_cnt %u", block->slot, block->fec_eos, block->mblk_cnt, block->poh_hashing_done_cnt, block->poh_hash_cmp_done_cnt ));
464 54 : return block->fec_eos && block->txn_parsed_cnt==block->txn_done_cnt && block->mblk_cnt==block->poh_hashing_done_cnt && block->block_start_done && !block->block_end_signaled;
465 54 : }
466 :
467 : static inline int
468 273 : block_will_signal_end( fd_sched_block_t * block ) {
469 273 : return block->fec_eos && !block->block_end_signaled;
470 273 : }
471 :
472 : /* Is there something known to be dispatchable in the block? This is an
473 : important liveness property. A block that doesn't contain any known
474 : dispatchable tasks will be deactivated or demoted. */
475 : static inline int
476 939 : block_is_dispatchable( fd_sched_block_t * block ) {
477 939 : ulong exec_queued_cnt = block->txn_parsed_cnt-block->txn_exec_in_flight_cnt-block->txn_exec_done_cnt;
478 939 : ulong sigverify_queued_cnt = block->txn_parsed_cnt-block->txn_sigverify_in_flight_cnt-block->txn_sigverify_done_cnt;
479 939 : ulong poh_queued_cnt = block->mblk_cnt-block->poh_mblk_in_flight_cnt-block->poh_hashing_done_cnt;
480 939 : return exec_queued_cnt>0UL ||
481 939 : sigverify_queued_cnt>0UL ||
482 939 : poh_queued_cnt>0UL ||
483 939 : !block->block_start_signaled ||
484 939 : block_will_signal_end( block );
485 939 : }
486 :
487 : static inline int
488 177 : block_is_in_flight( fd_sched_block_t * block ) {
489 177 : return block->txn_exec_in_flight_cnt || block->txn_sigverify_in_flight_cnt || block->poh_hashing_in_flight_cnt || (block->block_end_signaled && !block->block_end_done);
490 177 : }
491 :
492 : static inline int
493 1740 : block_is_done( fd_sched_block_t * block ) {
494 1740 : return block->fec_eos && block->txn_parsed_cnt==block->txn_done_cnt && block->mblk_cnt==block->poh_hash_cmp_done_cnt && block->block_start_done && block->block_end_done;
495 1740 : }
496 :
497 : static inline int
498 1248 : block_is_stageable( fd_sched_block_t * block ) {
499 1248 : int rv = !block_is_done( block ) && !block->dying;
500 1248 : if( FD_UNLIKELY( rv && !block->in_rdisp ) ) {
501 : /* Invariant: stageable blocks may be currently staged or unstaged,
502 : but must be in the dispatcher either way. When a block
503 : transitions to DONE, it will be immediately removed from the
504 : dispatcher. When a block transitions to DYING, it will be
505 : eventually abandoned from the dispatcher. */
506 0 : FD_LOG_CRIT(( "invariant violation: stageable block->in_rdisp==0, txn_parsed_cnt %u, txn_done_cnt %u, fec_eos %u,, slot %lu, parent slot %lu",
507 0 : block->txn_parsed_cnt, block->txn_done_cnt, (uint)block->fec_eos, block->slot, block->parent_slot ));
508 0 : }
509 1248 : return rv;
510 1248 : }
511 :
512 : static inline int
513 279 : block_is_promotable( fd_sched_block_t * block ) {
514 279 : return block_is_stageable( block ) && block_is_dispatchable( block ) && !block->staged;
515 279 : }
516 :
517 : static inline int
518 12 : block_is_demotable( fd_sched_block_t * block ) {
519 : /* A block can only be demoted from rdisp if it is empty, meaning no
520 : PENDING, READY, or DISPATCHED transactions. This is equivalent to
521 : having no in-flight transactions (DISPATCHED) and no queued
522 : transactions (PENDING or READY). This function actually implements
523 : a stronger requirement. We consider a block demotable only if
524 : there are no in-flight or queued tasks of any kind. */
525 12 : return !block_is_in_flight( block ) && !block_is_dispatchable( block ) && block->staged;
526 12 : }
527 :
528 : static inline int
529 858 : block_is_activatable( fd_sched_block_t * block ) {
530 858 : return block_is_stageable( block ) && block_is_dispatchable( block ) && block->staged;
531 858 : }
532 :
533 : static inline int
534 696 : block_should_deactivate( fd_sched_block_t * block ) {
535 : /* We allow a grace period, during which a block has nothing to
536 : dispatch, but has something in-flight. The block is allowed to
537 : stay activated and ingest FEC sets during this time. The block
538 : will be deactivated if there's still nothing to dispatch by the
539 : time all in-flight tasks are completed. */
540 696 : return !block_is_activatable( block ) && !block_is_in_flight( block );
541 696 : }
542 :
543 : static inline int
544 81 : block_is_prunable( fd_sched_block_t * block ) {
545 81 : return !block->in_rdisp && !block_is_in_flight( block );
546 81 : }
547 :
548 : static inline ulong
549 519 : block_to_idx( fd_sched_t * sched, fd_sched_block_t * block ) { return (ulong)(block-sched->block_pool); }
550 :
551 : __attribute__((format(printf,2,3)))
552 : static void
553 : fd_sched_printf( fd_sched_t * sched,
554 : char const * fmt,
555 405 : ... ) {
556 405 : va_list ap;
557 405 : ulong len;
558 405 : va_start( ap, fmt );
559 405 : int ret = vsnprintf( sched->print_buf+sched->print_buf_sz,
560 405 : FD_SCHED_MAX_PRINT_BUF_SZ-sched->print_buf_sz,
561 405 : fmt, ap );
562 405 : va_end( ap );
563 405 : len = fd_ulong_if( ret<0, 0UL, fd_ulong_min( (ulong)ret, FD_SCHED_MAX_PRINT_BUF_SZ-sched->print_buf_sz-1UL ) );
564 405 : sched->print_buf[ sched->print_buf_sz+len ] = '\0';
565 405 : sched->print_buf_sz += len;
566 405 : }
567 :
568 : FD_FN_UNUSED static void
569 0 : print_histogram( fd_sched_t * sched, fd_histf_t * hist, ulong converter, char * title ) {
570 0 : fd_sched_printf( sched, " +---------------------+----------------------+--------------+\n" );
571 0 : fd_sched_printf( sched, " | %-19s | | Count |\n", title );
572 0 : fd_sched_printf( sched, " +---------------------+----------------------+--------------+\n" );
573 0 :
574 0 : ulong total_count = 0;
575 0 : for( ulong i=0UL; i<fd_histf_bucket_cnt( hist ); i++ ) {
576 0 : total_count += fd_histf_cnt( hist, i );
577 0 : }
578 0 :
579 0 : for( ulong i=0UL; i< fd_histf_bucket_cnt( hist ); i++ ) {
580 0 : ulong bucket_count = fd_histf_cnt( hist, i );
581 0 :
582 0 : char * lt_str;
583 0 : char lt_buf[ 64 ];
584 0 : if( FD_UNLIKELY( i==fd_histf_bucket_cnt( hist )-1UL ) ) {
585 0 : lt_str = "+Inf";
586 0 : } else {
587 0 : ulong edge = fd_histf_right( hist, i );
588 0 : if( converter==FD_METRICS_CONVERTER_NANOSECONDS ) {
589 0 : edge = fd_metrics_convert_ticks_to_nanoseconds( edge-1UL );
590 0 : FD_TEST( fd_cstr_printf_check( lt_buf, sizeof( lt_buf ), NULL, "<= %lu nanos", edge ) );
591 0 : } else if( converter==FD_METRICS_CONVERTER_NONE ) {
592 0 : FD_TEST( fd_cstr_printf_check( lt_buf, sizeof( lt_buf ), NULL, "<= %lu", edge-1UL ) );
593 0 : }
594 0 : lt_str = lt_buf;
595 0 : }
596 0 :
597 0 : /* Create visual bar - scale to max 20 characters. */
598 0 : char bar_buf[ 22 ];
599 0 : if( bucket_count>0UL && total_count>0UL ) {
600 0 : ulong bar_length = (bucket_count*20UL)/total_count;
601 0 : if( !bar_length ) bar_length = 1;
602 0 : for( ulong j=0UL; j<bar_length; j++ ) { bar_buf[ j ] = '*'; }
603 0 : bar_buf[ bar_length ] = '\0';
604 0 : } else {
605 0 : bar_buf[ 0 ] = '\0';
606 0 : }
607 0 :
608 0 : fd_sched_printf( sched, " | %19s | %-20s | %12lu |\n", lt_str, bar_buf, bucket_count );
609 0 : }
610 0 : }
611 :
612 : FD_FN_UNUSED static void
613 24 : print_block_metrics( fd_sched_t * sched, fd_sched_block_t * block ) {
614 24 : fd_sched_printf( sched, "block idx %lu, block slot %lu, parent_slot %lu, fec_eos %d, rooted %d, txn_parsed_cnt %u, txn_exec_done_cnt %u, txn_sigverify_done_cnt %u, poh_hashing_done_cnt %u, poh_hash_cmp_done_cnt %u, txn_done_cnt %u, shred_cnt %u, mblk_cnt %u, mblk_freed_cnt %u, mblk_tick_cnt %u, mblk_unhashed_cnt %u, hashcnt %lu, txn_pool_max_popcnt %lu/%lu, mblk_pool_max_popcnt %lu/%lu, block_pool_max_popcnt %lu/%lu, mblks_rem %lu, txns_rem %lu, fec_buf_sz %u, fec_buf_boff %u, fec_buf_soff %u, fec_eob %d, fec_sob %d\n",
615 24 : block_to_idx( sched, block ), block->slot, block->parent_slot, block->fec_eos, block->rooted, block->txn_parsed_cnt, block->txn_exec_done_cnt, block->txn_sigverify_done_cnt, block->poh_hashing_done_cnt, block->poh_hash_cmp_done_cnt, block->txn_done_cnt, block->shred_cnt, block->mblk_cnt, block->mblk_freed_cnt, block->mblk_tick_cnt, block->mblk_unhashed_cnt, block->hashcnt, block->txn_pool_max_popcnt, sched->depth, block->mblk_pool_max_popcnt, sched->depth, block->block_pool_max_popcnt, sched->block_cnt_max, block->mblks_rem, block->txns_rem, block->fec_buf_sz, block->fec_buf_boff, block->fec_buf_soff, block->fec_eob, block->fec_sob );
616 24 : }
617 :
618 : FD_FN_UNUSED static void
619 243 : print_block_debug( fd_sched_t * sched, fd_sched_block_t * block ) {
620 243 : fd_sched_printf( sched, "block idx %lu, block slot %lu, parent_slot %lu, staged %d (lane %lu), dying %d, in_rdisp %d, fec_eos %d, rooted %d, block_start_signaled %d, block_end_signaled %d, block_start_done %d, block_end_done %d, txn_parsed_cnt %u, txn_exec_in_flight_cnt %u, txn_exec_done_cnt %u, txn_sigverify_in_flight_cnt %u, txn_sigverify_done_cnt %u, poh_hashing_in_flight_cnt %u, poh_mblk_in_flight_cnt %u, poh_hashing_done_cnt %u, poh_hash_cmp_done_cnt %u, txn_done_cnt %u, shred_cnt %u, mblk_cnt %u, mblk_freed_cnt %u, mblk_tick_cnt %u, mblk_unhashed_cnt %u, hashcnt %lu, txn_pool_max_popcnt %lu/%lu, mblk_pool_max_popcnt %lu/%lu, block_pool_max_popcnt %lu/%lu, tick_hashcnt_wmk %lu, curr_tick_hashcnt %lu, hashes_per_tick %lu, mblks_rem %lu, txns_rem %lu, fec_buf_sz %u, fec_buf_boff %u, fec_buf_soff %u, fec_eob %d, fec_sob %d\n",
621 243 : block_to_idx( sched, block ), block->slot, block->parent_slot, block->staged, block->staging_lane, block->dying, block->in_rdisp, block->fec_eos, block->rooted, block->block_start_signaled, block->block_end_signaled, block->block_start_done, block->block_end_done, block->txn_parsed_cnt, block->txn_exec_in_flight_cnt, block->txn_exec_done_cnt, block->txn_sigverify_in_flight_cnt, block->txn_sigverify_done_cnt, block->poh_hashing_in_flight_cnt, block->poh_mblk_in_flight_cnt, block->poh_hashing_done_cnt, block->poh_hash_cmp_done_cnt, block->txn_done_cnt, block->shred_cnt, block->mblk_cnt, block->mblk_freed_cnt, block->mblk_tick_cnt, block->mblk_unhashed_cnt, block->hashcnt, block->txn_pool_max_popcnt, sched->depth, block->mblk_pool_max_popcnt, sched->depth, block->block_pool_max_popcnt, sched->block_cnt_max, block->tick_hashcnt_wmk, block->curr_tick_hashcnt, block->hashes_per_tick, block->mblks_rem, block->txns_rem, block->fec_buf_sz, block->fec_buf_boff, block->fec_buf_soff, block->fec_eob, block->fec_sob );
622 243 : }
623 :
624 : FD_FN_UNUSED static void
625 60 : print_block_and_parent( fd_sched_t * sched, fd_sched_block_t * block ) {
626 60 : print_block_debug( sched, block );
627 60 : fd_sched_block_t * parent = block_pool_ele( sched, block->parent_idx );
628 60 : if( FD_LIKELY( parent ) ) print_block_debug( sched, parent );
629 60 : }
630 :
631 : FD_FN_UNUSED static void
632 69 : print_metrics( fd_sched_t * sched ) {
633 69 : fd_sched_printf( sched, "metrics: block_added_cnt %u, block_added_staged_cnt %u, block_added_unstaged_cnt %u, block_added_dead_ood_cnt %u, block_removed_cnt %u, block_abandoned_cnt %u, block_bad_cnt %u, block_promoted_cnt %u, block_demoted_cnt %u, deactivate_no_child_cnt %u, deactivate_no_txn_cnt %u, deactivate_pruned_cnt %u, deactivate_abandoned_cnt %u, lane_switch_cnt %u, lane_promoted_cnt %u, lane_demoted_cnt %u, fork_observed_cnt %u, alut_success_cnt %u, alut_serializing_cnt %u, poison_latch_overflow_cnt %u, poison_latch_alt_cnt %u, poison_cnt_wmk %u, txn_poison_serializing_cnt %u, txn_poisoned_cnt %u, txn_abandoned_parsed_cnt %u, txn_abandoned_exec_done_cnt %u, txn_abandoned_done_cnt %u, txn_max_in_flight_cnt %u, txn_weighted_in_flight_cnt %lu, txn_weighted_in_flight_tickcount %lu, txn_none_in_flight_tickcount %lu, txn_parsed_cnt %lu, txn_exec_done_cnt %lu, txn_sigverify_done_cnt %lu, txn_mixin_done_cnt %lu, txn_done_cnt %lu, mblk_parsed_cnt %lu, mblk_poh_hashed_cnt %lu, mblk_poh_done_cnt %lu, bytes_ingested_cnt %lu, bytes_ingested_unparsed_cnt %lu, bytes_dropped_cnt %lu, fec_cnt %lu\n",
634 69 : sched->metrics->block_added_cnt, sched->metrics->block_added_staged_cnt, sched->metrics->block_added_unstaged_cnt, sched->metrics->block_added_dead_ood_cnt, sched->metrics->block_removed_cnt, sched->metrics->block_abandoned_cnt, sched->metrics->block_bad_cnt, sched->metrics->block_promoted_cnt, sched->metrics->block_demoted_cnt, sched->metrics->deactivate_no_child_cnt, sched->metrics->deactivate_no_txn_cnt, sched->metrics->deactivate_pruned_cnt, sched->metrics->deactivate_abandoned_cnt, sched->metrics->lane_switch_cnt, sched->metrics->lane_promoted_cnt, sched->metrics->lane_demoted_cnt, sched->metrics->fork_observed_cnt, sched->metrics->alut_success_cnt, sched->metrics->alut_serializing_cnt, sched->metrics->poison_latch_overflow_cnt, sched->metrics->poison_latch_alt_cnt, sched->metrics->poison_cnt_wmk, sched->metrics->txn_poison_serializing_cnt, sched->metrics->txn_poisoned_cnt, sched->metrics->txn_abandoned_parsed_cnt, sched->metrics->txn_abandoned_exec_done_cnt, sched->metrics->txn_abandoned_done_cnt, sched->metrics->txn_max_in_flight_cnt, sched->metrics->txn_weighted_in_flight_cnt, sched->metrics->txn_weighted_in_flight_tickcount, sched->metrics->txn_none_in_flight_tickcount, sched->metrics->txn_parsed_cnt, sched->metrics->txn_exec_done_cnt, sched->metrics->txn_sigverify_done_cnt, sched->metrics->txn_mixin_done_cnt, sched->metrics->txn_done_cnt, sched->metrics->mblk_parsed_cnt, sched->metrics->mblk_poh_hashed_cnt, sched->metrics->mblk_poh_done_cnt, sched->metrics->bytes_ingested_cnt, sched->metrics->bytes_ingested_unparsed_cnt, sched->metrics->bytes_dropped_cnt, sched->metrics->fec_cnt );
635 69 : }
636 :
637 : FD_FN_UNUSED static void
638 69 : print_sched( fd_sched_t * sched ) {
639 69 : fd_sched_printf( sched, "sched canary 0x%lx, exec_cnt %lu, root_idx %lu, txn_exec_ready_bitset[ 0 ] 0x%lx, sigverify_ready_bitset[ 0 ] 0x%lx, poh_ready_bitset[ 0 ] 0x%lx, active_idx %lu, staged_bitset %lu, staged_head_idx[0] %lu, staged_head_idx[1] %lu, staged_head_idx[2] %lu, staged_head_idx[3] %lu, staged_popcnt_wmk %lu, txn_pool_free_cnt %lu/%lu, block_pool_popcnt %lu/%lu\n",
640 69 : sched->canary, sched->exec_cnt, sched->root_idx, sched->txn_exec_ready_bitset[ 0 ], sched->sigverify_ready_bitset[ 0 ], sched->poh_ready_bitset[ 0 ], sched->active_bank_idx, sched->staged_bitset, sched->staged_head_bank_idx[ 0 ], sched->staged_head_bank_idx[ 1 ], sched->staged_head_bank_idx[ 2 ], sched->staged_head_bank_idx[ 3 ], sched->staged_popcnt_wmk, sched->txn_pool_free_cnt, sched->depth, sched->block_pool_popcnt, sched->block_cnt_max );
641 69 : fd_sched_block_t * active_block = block_pool_ele( sched, sched->active_bank_idx );
642 69 : if( active_block ) print_block_debug( sched, active_block );
643 345 : for( int l=0; l<(int)FD_SCHED_MAX_STAGING_LANES; l++ ) {
644 276 : if( fd_ulong_extract_bit( sched->staged_bitset, l ) ) {
645 78 : fd_sched_block_t * block = block_pool_ele( sched, sched->staged_head_bank_idx[ l ] );
646 78 : print_block_debug( sched, block );
647 78 : }
648 276 : }
649 69 : }
650 :
651 : FD_FN_UNUSED static void
652 60 : print_all( fd_sched_t * sched, fd_sched_block_t * block ) {
653 60 : print_metrics( sched );
654 60 : print_sched( sched );
655 60 : print_block_and_parent( sched, block );
656 60 : }
657 :
658 : static inline void
659 : record_dead_reason( fd_sched_block_t * block,
660 60 : int dead_reason ) {
661 60 : if( FD_LIKELY( block->dead_reason==FD_SCHED_DEAD_REASON_NONE ) ) {
662 60 : block->dead_reason = dead_reason;
663 60 : block->discarded = 0;
664 60 : }
665 60 : }
666 :
667 : /* Record that the block goes down with its lineage rather than for a
668 : defect of its own, aka DEAD_ANCESTOR. Also record the parent's
669 : deadness flavor so we can tell a discarded (but not invalid) lineage
670 : from an invalid one.
671 :
672 : Gated on the block having no dead reason of its own, so a verdict
673 : sched already reached is never overwritten. That gate neither bounds
674 : how often the inherit runs nor sees a ruling the replay tile made,
675 : which leaves dead_reason NONE. Callers are responsible for invoking
676 : this only on a block that is newly going down. */
677 : static inline void
678 15 : record_lineage_death( fd_sched_block_t * block, fd_sched_block_t const * parent ) {
679 15 : if( FD_LIKELY( block->dead_reason==FD_SCHED_DEAD_REASON_NONE ) ) {
680 15 : record_dead_reason( block, FD_SCHED_DEAD_REASON_DEAD_ANCESTOR );
681 15 : block->discarded = parent->discarded;
682 15 : }
683 15 : }
684 :
685 : static void
686 45 : handle_bad_block( fd_sched_t * sched, fd_sched_block_t * block, int dead_reason ) {
687 45 : record_dead_reason( block, dead_reason );
688 45 : sched->print_buf_sz = 0UL;
689 45 : print_all( sched, block );
690 45 : FD_LOG_DEBUG(( "%s", sched->print_buf ));
691 45 : subtree_abandon( sched, block );
692 45 : sched->metrics->block_bad_cnt++;
693 45 : check_or_set_active_block( sched );
694 45 : }
695 :
696 : /* Returns the number of shred boundaries strictly before query.
697 : Transaction offsets are visited in nondecreasing order, so each
698 : shred length is scanned at most once per block. */
699 : static uint
700 : shred_split( fd_sched_t * sched,
701 : fd_sched_block_t * block,
702 24 : uint query ) {
703 24 : FD_TEST( block->shred_scan_idx<=block->shred_cnt );
704 24 : FD_TEST( block->shred_scan_off<=query );
705 24 : ushort const * shred_sz = sched->shred_sz + block_to_idx( sched, block )*sched->max_shreds_per_block;
706 39 : while( block->shred_scan_idx<block->shred_cnt ) {
707 39 : uint next_off = block->shred_scan_off + (uint)shred_sz[ block->shred_scan_idx ];
708 39 : if( next_off>=query ) break;
709 15 : block->shred_scan_off = next_off;
710 15 : block->shred_scan_idx++;
711 15 : }
712 24 : return block->shred_scan_idx;
713 24 : }
714 :
715 :
716 : /* Public functions. */
717 :
718 : ulong
719 1116 : fd_sched_align( void ) {
720 1116 : return fd_ulong_max( alignof(fd_sched_t),
721 1116 : fd_ulong_max( fd_rdisp_align(),
722 1116 : fd_ulong_max( alignof(fd_sched_block_t), 64UL ))); /* Minimally cache line aligned. */
723 1116 : }
724 :
725 : ulong
726 : fd_sched_footprint( ulong depth,
727 : ulong block_cnt_max,
728 : ulong max_shreds_per_block,
729 105 : ulong max_txn_per_slot ) {
730 105 : if( FD_UNLIKELY( depth<FD_SCHED_MIN_DEPTH || depth>FD_SCHED_MAX_DEPTH ) ) return 0UL; /* bad depth */
731 105 : if( FD_UNLIKELY( !block_cnt_max ) ) return 0UL; /* bad block_cnt_max */
732 105 : if( FD_UNLIKELY( depth>UINT_MAX-1UL ) ) return 0UL; /* mblk_pool use uint as pointers */
733 105 : if( FD_UNLIKELY( !max_shreds_per_block || max_shreds_per_block>UINT_MAX ) ) return 0UL; /* shred_cnt is uint */
734 102 : if( FD_UNLIKELY( !max_txn_per_slot || max_txn_per_slot >UINT_MAX ) ) return 0UL; /* txn_parsed_cnt is uint */
735 :
736 99 : ulong l = FD_LAYOUT_INIT;
737 99 : l = FD_LAYOUT_APPEND( l, fd_sched_align(), sizeof(fd_sched_t) );
738 99 : l = FD_LAYOUT_APPEND( l, fd_rdisp_align(), fd_rdisp_footprint( depth, block_cnt_max ) ); /* dispatcher */
739 99 : l = FD_LAYOUT_APPEND( l, alignof(fd_sched_block_t), block_cnt_max*sizeof(fd_sched_block_t) ); /* block pool */
740 99 : l = FD_LAYOUT_APPEND( l, alignof(ushort), block_cnt_max*max_shreds_per_block*sizeof(ushort) ); /* shred_sz */
741 99 : l = FD_LAYOUT_APPEND( l, ref_q_align(), ref_q_footprint( block_cnt_max ) );
742 99 : l = FD_LAYOUT_APPEND( l, alignof(fd_txn_p_t), depth*sizeof(fd_txn_p_t) ); /* txn_pool */
743 99 : l = FD_LAYOUT_APPEND( l, alignof(fd_sched_txn_info_t), depth*sizeof(fd_sched_txn_info_t) ); /* txn_info_pool */
744 99 : l = FD_LAYOUT_APPEND( l, alignof(fd_sched_mblk_t), depth*sizeof(fd_sched_mblk_t) ); /* mblk_pool */
745 99 : return FD_LAYOUT_FINI( l, fd_sched_align() );
746 102 : }
747 :
748 : void *
749 : fd_sched_new( void * mem,
750 : fd_rng_t * rng,
751 : ulong depth,
752 : ulong block_cnt_max,
753 : ulong max_shreds_per_block,
754 : ulong max_txn_per_slot,
755 : ulong exec_cnt,
756 90 : int is_alpenglow ) {
757 :
758 90 : if( FD_UNLIKELY( !mem ) ) {
759 0 : FD_LOG_WARNING(( "NULL mem" ));
760 0 : return NULL;
761 0 : }
762 :
763 90 : if( FD_UNLIKELY( !rng ) ) {
764 0 : FD_LOG_WARNING(( "NULL rng" ));
765 0 : return NULL;
766 0 : }
767 :
768 90 : if( FD_UNLIKELY( !fd_ulong_is_aligned( (ulong)mem, fd_sched_align() ) ) ) {
769 0 : FD_LOG_WARNING(( "misaligned mem (%p)", mem ));
770 0 : return NULL;
771 0 : }
772 :
773 90 : if( FD_UNLIKELY( depth<FD_SCHED_MIN_DEPTH || depth>FD_SCHED_MAX_DEPTH ) ) {
774 0 : FD_LOG_WARNING(( "bad depth (%lu)", depth ));
775 0 : return NULL;
776 0 : }
777 :
778 90 : if( FD_UNLIKELY( !block_cnt_max ) ) {
779 0 : FD_LOG_WARNING(( "bad block_cnt_max (%lu)", block_cnt_max ));
780 0 : return NULL;
781 0 : }
782 :
783 90 : if( FD_UNLIKELY( depth>UINT_MAX-1UL ) ) {
784 0 : FD_LOG_WARNING(( "bad depth (%lu)", depth ));
785 0 : return NULL;
786 0 : }
787 :
788 90 : if( FD_UNLIKELY( !max_shreds_per_block || max_shreds_per_block>UINT_MAX ) ) {
789 0 : FD_LOG_WARNING(( "bad max_shreds_per_block (%lu)", max_shreds_per_block ));
790 0 : return NULL;
791 0 : }
792 :
793 90 : if( FD_UNLIKELY( !max_txn_per_slot || max_txn_per_slot>UINT_MAX ) ) {
794 0 : FD_LOG_WARNING(( "bad max_txn_per_slot (%lu)", max_txn_per_slot ));
795 0 : return NULL;
796 0 : }
797 :
798 90 : if( FD_UNLIKELY( !exec_cnt || exec_cnt>FD_SCHED_MAX_EXEC_TILE_CNT ) ) {
799 0 : FD_LOG_WARNING(( "bad exec_cnt (%lu)", exec_cnt ));
800 0 : return NULL;
801 0 : }
802 :
803 90 : FD_SCRATCH_ALLOC_INIT( l, mem );
804 90 : fd_sched_t * sched = FD_SCRATCH_ALLOC_APPEND( l, fd_sched_align(), sizeof(fd_sched_t) );
805 90 : void * _rdisp = FD_SCRATCH_ALLOC_APPEND( l, fd_rdisp_align(), fd_rdisp_footprint( depth, block_cnt_max ) );
806 90 : void * _bpool = FD_SCRATCH_ALLOC_APPEND( l, alignof(fd_sched_block_t), block_cnt_max*sizeof(fd_sched_block_t) );
807 90 : /* */ FD_SCRATCH_ALLOC_APPEND( l, alignof(ushort), block_cnt_max*max_shreds_per_block*sizeof(ushort) );
808 90 : void * _ref_q = FD_SCRATCH_ALLOC_APPEND( l, ref_q_align(), ref_q_footprint( block_cnt_max ) );
809 90 : fd_txn_p_t * _txn_pool = FD_SCRATCH_ALLOC_APPEND( l, alignof(fd_txn_p_t), depth*sizeof(fd_txn_p_t) );
810 90 : fd_sched_txn_info_t * _txn_info_pool = FD_SCRATCH_ALLOC_APPEND( l, alignof(fd_sched_txn_info_t), depth*sizeof(fd_sched_txn_info_t) );
811 90 : fd_sched_mblk_t * _mblk_pool = FD_SCRATCH_ALLOC_APPEND( l, alignof(fd_sched_mblk_t), depth*sizeof(fd_sched_mblk_t) );
812 90 : FD_SCRATCH_ALLOC_FINI( l, fd_sched_align() );
813 :
814 90 : sched->txn_pool = _txn_pool;
815 90 : sched->txn_info_pool = _txn_info_pool;
816 90 : sched->mblk_pool = _mblk_pool;
817 :
818 90 : fd_rdisp_new( _rdisp, depth, block_cnt_max, fd_rng_ulong( rng ) );
819 :
820 90 : fd_sched_block_t * bpool = (fd_sched_block_t *)_bpool;
821 510 : for( ulong i=0; i<block_cnt_max; i++ ) {
822 420 : bpool[ i ].in_sched = 0;
823 420 : mblk_slist_new( bpool[ i ].mblks_unhashed );
824 420 : mblk_slist_new( bpool[ i ].mblks_hashing_in_progress );
825 420 : mblk_slist_new( bpool[ i ].mblks_mixin_in_progress );
826 420 : }
827 :
828 90 : FD_TEST( fd_chkdup_new( sched->chkdup, rng ) );
829 :
830 90 : fd_memset( sched->metrics, 0, sizeof(fd_sched_metrics_t) );
831 90 : sched->txn_in_flight_last_tick = LONG_MAX;
832 90 : sched->next_ready_last_tick = LONG_MAX;
833 90 : sched->next_ready_last_bank_idx = ULONG_MAX;
834 :
835 90 : sched->is_alpenglow = is_alpenglow;
836 90 : sched->canary = FD_SCHED_MAGIC;
837 90 : sched->depth = depth;
838 90 : sched->block_cnt_max = block_cnt_max;
839 90 : sched->max_shreds_per_block = max_shreds_per_block;
840 90 : sched->max_txn_per_slot = max_txn_per_slot;
841 90 : sched->max_mblk_per_slot = fd_ulong_min( FD_SCHED_MAX_MBLK_PER_SLOT*max_shreds_per_block/FD_SHRED_BLK_MAX, UINT_MAX ); /* mblk_cnt is uint */
842 90 : sched->exec_cnt = exec_cnt;
843 90 : sched->poh_simd_max = fd_sha256_simd_lane_max(); FD_CHECK_ERR( sched->poh_simd_max<=FD_SCHED_POH_PARA, "overly wide PoH SHA batch" );
844 90 : sched->poh_simd_min = fd_sha256_simd_lane_min();
845 90 : sched->poh_simd_iters_max = fd_ulong_max( (FD_SCHED_MAX_POH_HASHES_PER_TASK<<8)/fd_sha256_simd_iter_cost_q8(), 1UL );
846 90 : sched->bypass_poh_verify = 0;
847 90 : sched->bypass_alut_resolution = 0;
848 90 : sched->root_idx = ULONG_MAX;
849 90 : sched->active_bank_idx = ULONG_MAX;
850 90 : sched->last_active_bank_idx = ULONG_MAX;
851 90 : sched->staged_bitset = 0UL;
852 90 : sched->staged_popcnt_wmk = 0UL;
853 :
854 90 : sched->txn_exec_ready_bitset[ 0 ] = fd_ulong_mask_lsb( (int)exec_cnt );
855 90 : sched->sigverify_ready_bitset[ 0 ] = fd_ulong_mask_lsb( (int)exec_cnt );
856 90 : sched->poh_ready_bitset[ 0 ] = fd_ulong_mask_lsb( (int)exec_cnt );
857 :
858 90 : sched->txn_pool_free_cnt = depth-1UL; /* -1 because index 0 is unusable as a sentinel reserved by the dispatcher */
859 :
860 45876 : for( ulong i=0UL; i<depth-1UL; i++ ) sched->mblk_pool[ i ].next = (uint)(i+1UL);
861 90 : sched->mblk_pool[ depth-1UL ].next = UINT_MAX;
862 90 : sched->mblk_pool_free_head = 0U;
863 90 : sched->mblk_pool_free_cnt = depth;
864 :
865 90 : txn_bitset_new( sched->exec_done_set );
866 90 : txn_bitset_new( sched->sigverify_done_set );
867 90 : txn_bitset_new( sched->poh_mixin_done_set );
868 :
869 90 : sched->block_pool_popcnt = 0UL;
870 :
871 90 : ref_q_new( _ref_q, block_cnt_max );
872 :
873 90 : return sched;
874 90 : }
875 :
876 : fd_sched_t *
877 90 : fd_sched_join( void * mem ) {
878 :
879 90 : if( FD_UNLIKELY( !mem ) ) {
880 0 : FD_LOG_WARNING(( "NULL mem" ));
881 0 : return NULL;
882 0 : }
883 :
884 90 : fd_sched_t * sched = (fd_sched_t *)mem;
885 90 : FD_TEST( sched->canary==FD_SCHED_MAGIC );
886 90 : ulong depth = sched->depth;
887 90 : ulong block_cnt_max = sched->block_cnt_max;
888 90 : ulong max_shreds_per_block = sched->max_shreds_per_block;
889 :
890 90 : FD_SCRATCH_ALLOC_INIT( l, mem );
891 90 : /* */ FD_SCRATCH_ALLOC_APPEND( l, fd_sched_align(), sizeof(fd_sched_t) );
892 90 : void * _rdisp = FD_SCRATCH_ALLOC_APPEND( l, fd_rdisp_align(), fd_rdisp_footprint( depth, block_cnt_max ) );
893 90 : void * _bpool = FD_SCRATCH_ALLOC_APPEND( l, alignof(fd_sched_block_t), block_cnt_max*sizeof(fd_sched_block_t) );
894 90 : void * _shred_sz = FD_SCRATCH_ALLOC_APPEND( l, alignof(ushort), block_cnt_max*max_shreds_per_block*sizeof(ushort) );
895 90 : void * _ref_q = FD_SCRATCH_ALLOC_APPEND( l, ref_q_align(), ref_q_footprint( block_cnt_max ) );
896 90 : /* */ FD_SCRATCH_ALLOC_APPEND( l, alignof(fd_txn_p_t), depth*sizeof(fd_txn_p_t) );
897 90 : /* */ FD_SCRATCH_ALLOC_APPEND( l, alignof(fd_sched_txn_info_t), depth*sizeof(fd_sched_txn_info_t) );
898 90 : /* */ FD_SCRATCH_ALLOC_APPEND( l, alignof(fd_sched_mblk_t), depth*sizeof(fd_sched_mblk_t) );
899 90 : FD_SCRATCH_ALLOC_FINI( l, fd_sched_align() );
900 :
901 90 : sched->rdisp = fd_rdisp_join( _rdisp );
902 90 : sched->ref_q = ref_q_join( _ref_q );
903 90 : sched->block_pool = _bpool;
904 90 : sched->shred_sz = _shred_sz;
905 :
906 510 : for( ulong i=0; i<block_cnt_max; i++ ) {
907 420 : mblk_slist_join( sched->block_pool[ i ].mblks_unhashed );
908 420 : mblk_slist_join( sched->block_pool[ i ].mblks_hashing_in_progress );
909 420 : mblk_slist_join( sched->block_pool[ i ].mblks_mixin_in_progress );
910 420 : }
911 :
912 90 : txn_bitset_join( sched->exec_done_set );
913 90 : txn_bitset_join( sched->sigverify_done_set );
914 90 : txn_bitset_join( sched->poh_mixin_done_set );
915 :
916 90 : return sched;
917 90 : }
918 :
919 : int
920 147 : fd_sched_fec_can_ingest( fd_sched_t * sched, fd_sched_fec_t * fec ) {
921 147 : FD_TEST( sched->canary==FD_SCHED_MAGIC );
922 147 : FD_TEST( fec->bank_idx<sched->block_cnt_max );
923 147 : FD_TEST( fec->parent_bank_idx<sched->block_cnt_max );
924 :
925 147 : if( FD_UNLIKELY( fec->fec->data_sz>FD_SCHED_MAX_PAYLOAD_PER_FEC ) ) {
926 0 : sched->print_buf_sz = 0UL;
927 0 : print_metrics( sched );
928 0 : print_sched( sched );
929 0 : FD_LOG_NOTICE(( "%s", sched->print_buf ));
930 0 : FD_LOG_CRIT(( "invalid FEC set: fec->data_sz %lu, slot %lu, parent slot %lu", fec->fec->data_sz, fec->slot, fec->parent_slot ));
931 0 : }
932 :
933 147 : ulong fec_buf_sz = 0UL;
934 147 : fd_sched_block_t * block = block_pool_ele( sched, fec->bank_idx );
935 147 : if( FD_LIKELY( !fec->is_first_in_block ) ) {
936 57 : fec_buf_sz += block->fec_buf_sz-block->fec_buf_soff;
937 90 : } else {
938 : /* No residual data as this is a fresh new block. */
939 90 : }
940 : /* Addition is safe and won't overflow because we checked the FEC set
941 : size above. */
942 147 : fec_buf_sz += fec->fec->data_sz;
943 : /* Assuming every transaction is min size, do we have enough free
944 : entries in the txn pool? For a more precise txn count, we would
945 : have to do some parsing. */
946 147 : return sched->txn_pool_free_cnt>=fec_buf_sz/FD_TXN_MIN_SERIALIZED_SZ && sched->mblk_pool_free_cnt>=fec_buf_sz/sizeof(fd_microblock_hdr_t);
947 147 : }
948 :
949 : ulong
950 3 : fd_sched_can_ingest_cnt( fd_sched_t * sched ) {
951 3 : FD_TEST( sched->canary==FD_SCHED_MAGIC );
952 : /* Worst case, we need one byte from the incoming data to extract a
953 : transaction out of the residual data, and the rest of the incoming
954 : data contributes toward min sized transactions. */
955 3 : return fd_ulong_min( sched->txn_pool_free_cnt/FD_SCHED_MAX_TXN_PER_FEC, sched->mblk_pool_free_cnt/FD_SCHED_MAX_MBLK_PER_FEC );
956 3 : }
957 :
958 : int
959 48 : fd_sched_is_drained( fd_sched_t * sched ) {
960 48 : int nothing_inflight = sched->exec_cnt==(ulong)fd_ulong_popcnt( sched->txn_exec_ready_bitset[ 0 ]&sched->sigverify_ready_bitset[ 0 ]&sched->poh_ready_bitset[ 0 ] );
961 48 : int nothing_queued = sched->active_bank_idx==ULONG_MAX;
962 48 : return nothing_inflight && nothing_queued;
963 48 : }
964 :
965 : FD_WARN_UNUSED int
966 : fd_sched_fec_ingest( fd_sched_t * sched,
967 189 : fd_sched_fec_t * fec ) {
968 189 : FD_TEST( sched->canary==FD_SCHED_MAGIC );
969 189 : FD_TEST( fec->bank_idx<sched->block_cnt_max );
970 189 : FD_TEST( fec->parent_bank_idx<sched->block_cnt_max );
971 189 : FD_TEST( ref_q_empty( sched->ref_q ) );
972 :
973 189 : fd_sched_block_t * block = block_pool_ele( sched, fec->bank_idx );
974 :
975 189 : if( FD_UNLIKELY( fec->fec->data_sz>FD_SCHED_MAX_PAYLOAD_PER_FEC ) ) {
976 0 : sched->print_buf_sz = 0UL;
977 0 : print_all( sched, block );
978 0 : FD_LOG_NOTICE(( "%s", sched->print_buf ));
979 0 : FD_LOG_CRIT(( "invalid FEC set: fec->data_sz %lu, slot %lu, parent slot %lu", fec->fec->data_sz, fec->slot, fec->parent_slot ));
980 0 : }
981 :
982 189 : sched->metrics->fec_cnt++;
983 :
984 189 : if( FD_UNLIKELY( fec->is_first_in_block ) ) {
985 : /* This is a new block. */
986 129 : add_block( sched, fec->bank_idx, fec->parent_bank_idx );
987 129 : block->slot = fec->slot;
988 129 : block->parent_slot = fec->parent_slot;
989 :
990 129 : if( FD_UNLIKELY( block->dying ) ) {
991 : /* The child of a dead block is also dead. We added it to our
992 : fork tree just so we could track an entire lineage of dead
993 : children and propagate the dead property to the entire lineage,
994 : in case there were frags for more than one dead children
995 : in-flight at the time the parent was abandoned. That being
996 : said, we shouldn't need to add the dead child to the
997 : dispatcher. */
998 12 : sched->metrics->block_added_dead_ood_cnt++;
999 :
1000 : /* Release the refcnt right away since we don't intend to replay
1001 : it at all. We do this so its bank does not linger and stall
1002 : root advancement until the next root notify. */
1003 12 : subtree_release_refcnt( sched, block );
1004 :
1005 : /* Ignore the FEC set for a dead block. */
1006 12 : sched->metrics->bytes_dropped_cnt += fec->fec->data_sz;
1007 12 : return 0;
1008 12 : }
1009 :
1010 : /* Try to find a staging lane for this block. */
1011 117 : int alloc_lane = 0;
1012 117 : fd_sched_block_t * parent_block = block_pool_ele( sched, fec->parent_bank_idx );
1013 117 : if( FD_LIKELY( parent_block->staged ) ) {
1014 : /* Parent is staged. So see if we can continue down the same
1015 : staging lane. */
1016 6 : ulong staging_lane = parent_block->staging_lane;
1017 6 : ulong child_idx = parent_block->child_idx;
1018 12 : while( child_idx!=ULONG_MAX ) {
1019 6 : fd_sched_block_t * child = block_pool_ele( sched, child_idx );
1020 6 : if( child->staged && child->staging_lane==staging_lane ) {
1021 : /* Found a child on the same lane. So we're done. */
1022 0 : staging_lane = FD_RDISP_UNSTAGED;
1023 0 : break;
1024 0 : }
1025 6 : child_idx = child->sibling_idx;
1026 6 : }
1027 : /* No child is staged on the same lane as the parent. So stage
1028 : this block. This is the common case. */
1029 6 : if( FD_LIKELY( staging_lane!=FD_RDISP_UNSTAGED ) ) {
1030 6 : block->in_rdisp = 1;
1031 6 : block->staged = 1;
1032 6 : block->staging_lane = staging_lane;
1033 6 : fd_rdisp_add_block( sched->rdisp, fec->bank_idx, staging_lane );
1034 6 : sched->metrics->block_added_cnt++;
1035 6 : sched->metrics->block_added_staged_cnt++;
1036 6 : FD_LOG_DEBUG(( "block %lu:%lu entered lane %lu: add", block->slot, fec->bank_idx, staging_lane ));
1037 6 : } else {
1038 0 : alloc_lane = 1;
1039 0 : }
1040 111 : } else {
1041 111 : if( block_is_stageable( parent_block ) ) {
1042 : /* Parent is unstaged but stageable. So let's be unstaged too.
1043 : This is not only a policy decision to be lazy and not promote
1044 : the parent at the moment, but also an important invariant
1045 : that we maintain for deadlock freeness in the face of staging
1046 : lane shortage. See the comments in lane eviction for how
1047 : this invariant is relevant. */
1048 0 : block->in_rdisp = 1;
1049 0 : block->staged = 0;
1050 0 : fd_rdisp_add_block( sched->rdisp, fec->bank_idx, FD_RDISP_UNSTAGED );
1051 0 : sched->metrics->block_added_cnt++;
1052 0 : sched->metrics->block_added_unstaged_cnt++;
1053 0 : FD_LOG_DEBUG(( "block %lu:%lu entered lane unstaged: add", block->slot, fec->bank_idx ));
1054 111 : } else {
1055 111 : alloc_lane = 1;
1056 111 : }
1057 111 : }
1058 117 : if( FD_UNLIKELY( alloc_lane ) ) {
1059 : /* We weren't able to inherit the parent's staging lane. So try
1060 : to find a new staging lane. */
1061 111 : if( FD_LIKELY( sched->staged_bitset!=fd_ulong_mask_lsb( FD_SCHED_MAX_STAGING_LANES ) ) ) { /* Optimize for lane available. */
1062 108 : int lane_idx = fd_ulong_find_lsb( ~sched->staged_bitset );
1063 108 : if( FD_UNLIKELY( lane_idx>=(int)FD_SCHED_MAX_STAGING_LANES ) ) {
1064 0 : FD_LOG_CRIT(( "invariant violation: lane_idx %d, sched->staged_bitset %lx",
1065 0 : lane_idx, sched->staged_bitset ));
1066 0 : }
1067 108 : sched->staged_bitset = fd_ulong_set_bit( sched->staged_bitset, lane_idx );
1068 108 : sched->staged_head_bank_idx[ lane_idx ] = fec->bank_idx;
1069 108 : sched->staged_popcnt_wmk = fd_ulong_max( sched->staged_popcnt_wmk, (ulong)fd_ulong_popcnt( sched->staged_bitset ) );
1070 108 : block->in_rdisp = 1;
1071 108 : block->staged = 1;
1072 108 : block->staging_lane = (ulong)lane_idx;
1073 108 : fd_rdisp_add_block( sched->rdisp, fec->bank_idx, block->staging_lane );
1074 108 : sched->metrics->block_added_cnt++;
1075 108 : sched->metrics->block_added_staged_cnt++;
1076 108 : FD_LOG_DEBUG(( "block %lu:%lu entered lane %lu: add", block->slot, fec->bank_idx, block->staging_lane ));
1077 108 : } else {
1078 : /* No lanes available. */
1079 3 : block->in_rdisp = 1;
1080 3 : block->staged = 0;
1081 3 : fd_rdisp_add_block( sched->rdisp, fec->bank_idx, FD_RDISP_UNSTAGED );
1082 3 : sched->metrics->block_added_cnt++;
1083 3 : sched->metrics->block_added_unstaged_cnt++;
1084 3 : FD_LOG_DEBUG(( "block %lu:%lu entered lane unstaged: add", block->slot, fec->bank_idx ));
1085 3 : }
1086 111 : }
1087 117 : }
1088 :
1089 177 : block->txn_pool_max_popcnt = fd_ulong_max( block->txn_pool_max_popcnt, sched->depth - sched->txn_pool_free_cnt - 1UL );
1090 177 : block->mblk_pool_max_popcnt = fd_ulong_max( block->mblk_pool_max_popcnt, sched->depth - sched->mblk_pool_free_cnt );
1091 177 : block->block_pool_max_popcnt = fd_ulong_max( block->block_pool_max_popcnt, sched->block_pool_popcnt );
1092 :
1093 177 : if( FD_UNLIKELY( block->dying ) ) {
1094 : /* Ignore the FEC set for a dead block. */
1095 0 : sched->metrics->bytes_dropped_cnt += fec->fec->data_sz;
1096 0 : return 1;
1097 0 : }
1098 :
1099 177 : if( FD_UNLIKELY( !block->in_rdisp ) ) {
1100 : /* Invariant: block must be in the dispatcher at this point. */
1101 0 : sched->print_buf_sz = 0UL;
1102 0 : print_all( sched, block );
1103 0 : FD_LOG_NOTICE(( "%s", sched->print_buf ));
1104 0 : FD_LOG_CRIT(( "invariant violation: block->in_rdisp==0, slot %lu, parent slot %lu",
1105 0 : block->slot, block->parent_slot ));
1106 0 : }
1107 :
1108 177 : if( FD_UNLIKELY( block->fec_eos ) ) {
1109 : /* This means something is wrong upstream. We're getting more FEC
1110 : sets for a block that has already ended, or so we were told. */
1111 0 : sched->print_buf_sz = 0UL;
1112 0 : print_all( sched, block );
1113 0 : FD_LOG_NOTICE(( "%s", sched->print_buf ));
1114 0 : FD_LOG_CRIT(( "invariant violation: block->fec_eos set but getting more FEC sets, slot %lu, parent slot %lu", fec->slot, fec->parent_slot ));
1115 0 : }
1116 177 : if( FD_UNLIKELY( block->fec_eob ) ) {
1117 : /* fec_eob is only ever set from is_last_in_batch, and the parser is
1118 : expected to finish a batch in full upon getting the FEC set that
1119 : ends the batch. An incomplete parse is caught eagerly below,
1120 : which marks the block dying and is caught above. Getting here
1121 : means the eager check below regressed. */
1122 0 : sched->print_buf_sz = 0UL;
1123 0 : print_all( sched, block );
1124 0 : FD_LOG_NOTICE(( "%s", sched->print_buf ));
1125 0 : FD_LOG_CRIT(( "invariant violation: block->fec_eob set but getting more FEC sets, slot %lu, parent slot %lu", fec->slot, fec->parent_slot ));
1126 0 : }
1127 177 : if( FD_UNLIKELY( block->child_idx!=ULONG_MAX ) ) {
1128 : /* This means something is wrong upstream. FEC sets are not being
1129 : delivered in replay order. We got a child block FEC set before
1130 : this block was completely delivered. */
1131 0 : sched->print_buf_sz = 0UL;
1132 0 : print_all( sched, block );
1133 0 : fd_sched_block_t * child_block = block_pool_ele( sched, block->child_idx );
1134 0 : print_block_debug( sched, child_block );
1135 0 : FD_LOG_NOTICE(( "%s", sched->print_buf ));
1136 0 : FD_LOG_CRIT(( "invariant violation: block->child_idx %lu, slot %lu, parent slot %lu", block->child_idx, fec->slot, fec->parent_slot ));
1137 0 : }
1138 :
1139 177 : FD_TEST( block->fec_buf_sz>=block->fec_buf_soff );
1140 177 : if( FD_LIKELY( block->fec_buf_sz>block->fec_buf_soff ) ) {
1141 : /* If there is residual data from the previous FEC set within the
1142 : same batch, we move it to the beginning of the buffer and append
1143 : the new FEC set. */
1144 9 : memmove( block->fec_buf, block->fec_buf+block->fec_buf_soff, block->fec_buf_sz-block->fec_buf_soff );
1145 9 : }
1146 177 : block->fec_buf_boff += block->fec_buf_soff;
1147 177 : block->fec_buf_sz -= block->fec_buf_soff;
1148 177 : block->fec_buf_soff = 0;
1149 : /* Addition is safe and won't overflow because we checked the FEC
1150 : set size above. */
1151 177 : if( FD_UNLIKELY( block->fec_buf_sz+fec->fec->data_sz>FD_SCHED_MAX_FEC_BUF_SZ ) ) {
1152 : /* The residual carried over from the previous parse is bounded: it
1153 : can only be a partial transaction or a microblock/batch header
1154 : that straddles a FEC set boundary. Any trailing bytes past the
1155 : last microblock within the same batch are discarded by the
1156 : parser, so they never contribute to the residual. So residual <=
1157 : max(sizeof(ulong), sizeof(fd_microblock_hdr_t), FD_TXN_MTU), and
1158 : the buffer is sized to always fit the residual plus a single FEC
1159 : set. Otherwise, it's a bad block. Instead of crashing, we
1160 : should refuse to replay down the fork. */
1161 0 : FD_LOG_INFO(( "bad block: UNPARSEABLE_CONTENT, fec_buf_sz %u, fec->data_sz %lu, slot %lu, parent slot %lu", block->fec_buf_sz, fec->fec->data_sz, fec->slot, fec->parent_slot ));
1162 0 : handle_bad_block( sched, block, FD_SCHED_DEAD_REASON_UNPARSEABLE_CONTENT );
1163 0 : sched->metrics->bytes_dropped_cnt += fec->fec->data_sz;
1164 0 : return 0;
1165 0 : }
1166 :
1167 : /* Append the new FEC set to the end of the buffer. */
1168 177 : fd_memcpy( block->fec_buf+block->fec_buf_sz, fec->data, fec->fec->data_sz );
1169 177 : block->fec_buf_sz += (uint)fec->fec->data_sz;
1170 177 : sched->metrics->bytes_ingested_cnt += fec->fec->data_sz;
1171 :
1172 177 : block->fec_eob = fec->is_last_in_batch;
1173 177 : block->fec_eos = fec->is_last_in_block;
1174 :
1175 177 : ushort * shred_sz = sched->shred_sz + fec->bank_idx*sched->max_shreds_per_block;
1176 177 : uint prev_shred_off = 0U;
1177 369 : for( ulong i=0; i<fec->shred_cnt; i++ ) {
1178 192 : FD_TEST( block->shred_cnt<sched->max_shreds_per_block );
1179 192 : uint shred_off;
1180 192 : if( FD_LIKELY( i<32UL ) ) {
1181 192 : shred_off = fec->fec->shred_offs[ i ];
1182 192 : } else if( FD_UNLIKELY( i!=fec->shred_cnt-1UL ) ) {
1183 : /* We don't track shred boundaries after 32 shreds, assume they're
1184 : sized uniformly */
1185 0 : ulong num_overflow_shreds = fec->shred_cnt-32UL;
1186 0 : ulong overflow_idx = i-32UL;
1187 0 : ulong overflow_data_sz = fec->fec->data_sz-fec->fec->shred_offs[ 31 ];
1188 0 : shred_off = fec->fec->shred_offs[ 31 ] + (uint)(overflow_data_sz / num_overflow_shreds * (overflow_idx + 1UL));
1189 0 : } else {
1190 0 : shred_off = (uint)fec->fec->data_sz;
1191 0 : }
1192 192 : FD_TEST( shred_off>=prev_shred_off && shred_off-prev_shred_off<=USHORT_MAX );
1193 192 : shred_sz[ block->shred_cnt++ ] = (ushort)(shred_off-prev_shred_off);
1194 192 : prev_shred_off = shred_off;
1195 192 : }
1196 :
1197 177 : block->fec_completed_ns = fec->completed_ns;
1198 :
1199 177 : int err = fd_sched_parse( sched, block, fec->alut_ctx );
1200 :
1201 177 : if( FD_UNLIKELY( err!=FD_SCHED_DEAD_REASON_NONE ) ) {
1202 33 : handle_bad_block( sched, block, err );
1203 33 : sched->metrics->bytes_dropped_cnt += block->fec_buf_sz-block->fec_buf_soff;
1204 33 : return 0;
1205 33 : }
1206 :
1207 144 : if( FD_UNLIKELY( (fec->is_last_in_batch||fec->is_last_in_block) && (block->txns_rem||block->mblks_rem||block->fec_eob) ) ) {
1208 : /* A malformed block that fails to parse out exactly as many
1209 : transactions and microblocks as it should.
1210 :
1211 : Upon getting a last-in-batch FEC, everything in the ongoing batch
1212 : should completely parse, and the eob flag should be reset. There
1213 : should be no go around for a last-in-batch FEC. */
1214 0 : FD_LOG_INFO(( "bad block: SHORT_BLOCK, bytes_rem %u, txns_rem %lu, mblks_rem %lu, fec_eob %d, slot %lu, parent slot %lu", block->fec_buf_sz-block->fec_buf_soff, block->txns_rem, block->mblks_rem, block->fec_eob, block->slot, block->parent_slot ));
1215 0 : handle_bad_block( sched, block, FD_SCHED_DEAD_REASON_SHORT_BLOCK );
1216 0 : return 0;
1217 0 : }
1218 :
1219 144 : if( FD_UNLIKELY( block->fec_eos && !block->last_mblk_is_tick ) ) {
1220 : /* The last microblock should be a tick.
1221 :
1222 : Note that this early parse-time detection could cause us to throw
1223 : a slightly different error from Agave, in the case that there are
1224 : too few ticks, since the tick count check precedes the trailing
1225 : entry check in Agave. That being said, ultimately a
1226 : TRAILING_ENTRY renders a block invalid, regardless of anything
1227 : else. */
1228 0 : FD_LOG_INFO(( "bad block: TRAILING_ENTRY, slot %lu, parent slot %lu, mblk_cnt %u", block->slot, block->parent_slot, block->mblk_cnt ));
1229 0 : handle_bad_block( sched, block, FD_SCHED_DEAD_REASON_TRAILING_ENTRY );
1230 0 : return 0;
1231 0 : }
1232 :
1233 144 : if( FD_UNLIKELY( block->fec_eos && sched->is_alpenglow ) ) {
1234 6 : int dead_reason = ag_on_final( block );
1235 6 : if( FD_UNLIKELY( dead_reason!=FD_SCHED_DEAD_REASON_NONE ) ) {
1236 3 : handle_bad_block( sched, block, dead_reason );
1237 3 : return 0;
1238 3 : }
1239 6 : }
1240 :
1241 : /* We just received a FEC set, which may have made all transactions in
1242 : a partially parsed microblock available. If this were a malformed
1243 : block that ends in a non-tick microblock, there's not going to be a
1244 : hashing task from the missing ending tick to drain the mixin queue.
1245 : So we try to drain the mixin queue right here. Another option is
1246 : to drain it at dispatch time, when we are about to dispatch the end
1247 : of block signal, right before the check for whether block should
1248 : end. */
1249 141 : int mixin_res;
1250 144 : while( (mixin_res=maybe_mixin( sched, block )) ) {
1251 3 : if( FD_UNLIKELY( mixin_res==-1 ) ) {
1252 0 : handle_bad_block( sched, block, FD_SCHED_DEAD_REASON_ENTRY_HASH_MISMATCH_INGEST );
1253 0 : return 0;
1254 0 : }
1255 3 : FD_TEST( mixin_res==1||mixin_res==2 );
1256 3 : }
1257 :
1258 : /* Check if we need to set the active block. */
1259 141 : check_or_set_active_block( sched );
1260 :
1261 141 : return 1;
1262 141 : }
1263 :
1264 : ulong
1265 411 : fd_sched_task_next_ready( fd_sched_t * sched, fd_sched_task_t * out ) {
1266 411 : FD_TEST( sched->canary==FD_SCHED_MAGIC );
1267 411 : FD_TEST( ref_q_empty( sched->ref_q ) );
1268 :
1269 411 : ulong exec_ready_bitset0 = sched->txn_exec_ready_bitset[ 0 ];
1270 411 : ulong exec_fully_ready_bitset = sched->sigverify_ready_bitset[ 0 ] & sched->poh_ready_bitset[ 0 ] & exec_ready_bitset0;
1271 411 : if( FD_UNLIKELY( !exec_fully_ready_bitset ) ) {
1272 : /* Early exit if no exec tiles available. */
1273 36 : return 0UL;
1274 36 : }
1275 :
1276 375 : if( FD_UNLIKELY( sched->active_bank_idx==ULONG_MAX ) ) {
1277 : /* No need to try activating a block. If we're in this state,
1278 : there's truly nothing to execute. We will activate something
1279 : when we ingest a FEC set with transactions. */
1280 21 : return 0UL;
1281 21 : }
1282 :
1283 354 : out->task_type = FD_SCHED_TT_NULL;
1284 :
1285 : /* We could in theory reevaluate staging lane allocation here and do
1286 : promotion/demotion as needed. It's a policy decision to minimize
1287 : fork churn for now and just execute down the same active fork. */
1288 :
1289 354 : ulong bank_idx = sched->active_bank_idx;
1290 354 : fd_sched_block_t * block = block_pool_ele( sched, bank_idx );
1291 354 : if( FD_UNLIKELY( block_should_deactivate( block ) ) ) {
1292 0 : sched->print_buf_sz = 0UL;
1293 0 : print_all( sched, block );
1294 0 : FD_LOG_NOTICE(( "%s", sched->print_buf ));
1295 0 : FD_LOG_CRIT(( "invariant violation: active block %lu:%lu is not activatable nor has anything in-flight", block->slot, sched->active_bank_idx ));
1296 0 : }
1297 :
1298 354 : block->txn_pool_max_popcnt = fd_ulong_max( block->txn_pool_max_popcnt, sched->depth - sched->txn_pool_free_cnt - 1UL );
1299 354 : block->mblk_pool_max_popcnt = fd_ulong_max( block->mblk_pool_max_popcnt, sched->depth - sched->mblk_pool_free_cnt );
1300 354 : block->block_pool_max_popcnt = fd_ulong_max( block->block_pool_max_popcnt, sched->block_pool_popcnt );
1301 :
1302 354 : if( FD_UNLIKELY( !block->block_start_signaled ) ) {
1303 51 : out->task_type = FD_SCHED_TT_BLOCK_START;
1304 51 : out->block_start->bank_idx = bank_idx;
1305 51 : out->block_start->parent_bank_idx = block->parent_idx;
1306 51 : out->block_start->slot = block->slot;
1307 51 : block->block_start_signaled = 1;
1308 51 : sched->next_ready_last_tick = fd_tickcount();
1309 51 : sched->next_ready_last_bank_idx = bank_idx;
1310 51 : return 1UL;
1311 51 : }
1312 :
1313 303 : ulong exec_tile_idx0 = fd_ulong_if( !!exec_fully_ready_bitset, (ulong)fd_ulong_find_lsb( exec_fully_ready_bitset ), ULONG_MAX );
1314 303 : ulong exec_queued_cnt = block->txn_parsed_cnt-block->txn_exec_in_flight_cnt-block->txn_exec_done_cnt;
1315 303 : if( FD_LIKELY( exec_queued_cnt>0UL && fd_ulong_popcnt( exec_fully_ready_bitset ) ) ) { /* Optimize for no fork switching. */
1316 : /* Transaction execution has the highest priority. Current mainnet
1317 : block times are very much dominated by critical path transaction
1318 : execution. To achieve the fastest block replay speed, we can't
1319 : afford to make any mistake in critical path dispatching. Any
1320 : deviation from perfect critical path dispatching is basically
1321 : irrecoverable. As such, we try to keep all the exec tiles busy
1322 : with transaction execution, but we allow at most one transaction
1323 : to be in-flight per exec tile. This is to ensure that whenever a
1324 : critical path transaction completes, we have at least one exec
1325 : tile, e.g. the one that just completed said transaction, readily
1326 : available to continue executing down the critical path. */
1327 12 : out->txn_exec->txn_idx = fd_rdisp_get_next_ready( sched->rdisp, bank_idx );
1328 12 : if( FD_UNLIKELY( out->txn_exec->txn_idx==0UL ) ) {
1329 : /* There are transactions queued but none ready for execution.
1330 : This implies that there must be in-flight transactions on whose
1331 : completion the queued transactions depend. So we return and
1332 : wait for those in-flight transactions to retire. This is a
1333 : policy decision to execute as much as we can down the current
1334 : fork. */
1335 0 : if( FD_UNLIKELY( !block->txn_exec_in_flight_cnt ) ) {
1336 0 : sched->print_buf_sz = 0UL;
1337 0 : print_all( sched, block );
1338 0 : FD_LOG_NOTICE(( "%s", sched->print_buf ));
1339 0 : FD_LOG_CRIT(( "invariant violation: no ready transaction found but block->txn_exec_in_flight_cnt==0" ));
1340 0 : }
1341 :
1342 : /* Next up are PoH tasks. Same dispatching policy as sigverify
1343 : tasks. */
1344 0 : ulong poh_ready_bitset = exec_fully_ready_bitset;
1345 0 : ulong poh_hashing_queued_cnt = block->mblk_cnt-block->poh_mblk_in_flight_cnt-block->poh_hashing_done_cnt;
1346 0 : int poh_threshold = fd_int_if( block->txn_exec_in_flight_cnt>0U, 0, 1 );
1347 0 : if( FD_LIKELY( poh_hashing_queued_cnt>0UL && fd_ulong_popcnt( poh_ready_bitset )>poh_threshold ) ) {
1348 0 : ulong max_cnt = poh_batch_max_cnt( sched, poh_hashing_queued_cnt, (ulong)fd_ulong_popcnt( poh_ready_bitset ), (ulong)poh_threshold );
1349 0 : dispatch_poh( sched, block, bank_idx, fd_ulong_find_lsb( poh_ready_bitset ), max_cnt, out );
1350 0 : sched->next_ready_last_tick = fd_tickcount();
1351 0 : sched->next_ready_last_bank_idx = bank_idx;
1352 0 : return 1UL;
1353 0 : }
1354 :
1355 : /* Dispatch more sigverify tasks only if at least one exec tile is
1356 : executing transactions or completely idle. Allow at most one
1357 : sigverify task in-flight per tile, and only dispatch to
1358 : completely idle tiles. */
1359 0 : ulong sigverify_ready_bitset = exec_fully_ready_bitset;
1360 0 : ulong sigverify_queued_cnt = block->txn_parsed_cnt-block->txn_sigverify_in_flight_cnt-block->txn_sigverify_done_cnt;
1361 0 : if( FD_LIKELY( sigverify_queued_cnt>0UL && fd_ulong_popcnt( sigverify_ready_bitset )>fd_int_if( block->txn_exec_in_flight_cnt>0U, 0, 1 ) ) ) {
1362 0 : dispatch_sigverify( sched, block, bank_idx, fd_ulong_find_lsb( sigverify_ready_bitset ), out );
1363 0 : sched->next_ready_last_tick = sched->txn_info_pool[ out->txn_sigverify->txn_idx ].tick_sigverify_disp = fd_tickcount();
1364 0 : sched->next_ready_last_bank_idx = bank_idx;
1365 0 : return 1UL;
1366 0 : }
1367 0 : return 0UL;
1368 0 : }
1369 12 : out->task_type = FD_SCHED_TT_TXN_EXEC;
1370 12 : out->txn_exec->bank_idx = bank_idx;
1371 12 : out->txn_exec->slot = block->slot;
1372 12 : out->txn_exec->exec_idx = exec_tile_idx0;
1373 12 : FD_TEST( out->txn_exec->exec_idx!=ULONG_MAX );
1374 :
1375 12 : long now = fd_tickcount();
1376 12 : ulong delta = (ulong)(now-sched->txn_in_flight_last_tick);
1377 12 : ulong txn_exec_busy_cnt = sched->exec_cnt-(ulong)fd_ulong_popcnt( exec_ready_bitset0 );
1378 12 : sched->metrics->txn_none_in_flight_tickcount += fd_ulong_if( txn_exec_busy_cnt==0UL && sched->txn_in_flight_last_tick!=LONG_MAX, delta, 0UL );
1379 12 : sched->metrics->txn_weighted_in_flight_tickcount += fd_ulong_if( txn_exec_busy_cnt!=0UL, delta, 0UL );
1380 12 : sched->metrics->txn_weighted_in_flight_cnt += delta*txn_exec_busy_cnt;
1381 12 : sched->txn_in_flight_last_tick = now;
1382 :
1383 12 : sched->txn_info_pool[ out->txn_exec->txn_idx ].tick_exec_disp = now;
1384 12 : sched->txn_info_pool[ out->txn_exec->txn_idx ].exec_tile_idx = exec_tile_idx0;
1385 :
1386 12 : sched->txn_exec_ready_bitset[ 0 ] = fd_ulong_clear_bit( exec_ready_bitset0, (int)exec_tile_idx0);
1387 12 : sched->tile_to_bank_idx[ exec_tile_idx0 ] = bank_idx;
1388 :
1389 12 : block->txn_exec_in_flight_cnt++;
1390 12 : sched->metrics->txn_max_in_flight_cnt = fd_uint_max( sched->metrics->txn_max_in_flight_cnt, block->txn_exec_in_flight_cnt );
1391 :
1392 12 : if( FD_UNLIKELY( (~sched->txn_exec_ready_bitset[ 0 ])&(~sched->sigverify_ready_bitset[ 0 ])&(~sched->poh_ready_bitset[ 0 ])&fd_ulong_mask_lsb( (int)sched->exec_cnt ) ) ) FD_LOG_CRIT(( "invariant violation: txn_exec_ready_bitset 0x%lx sigverify_ready_bitset 0x%lx poh_ready_bitset 0x%lx", sched->txn_exec_ready_bitset[ 0 ], sched->sigverify_ready_bitset[ 0 ], sched->poh_ready_bitset[ 0 ] ));
1393 12 : ulong total_exec_busy_cnt = sched->exec_cnt-(ulong)fd_ulong_popcnt( sched->txn_exec_ready_bitset[ 0 ]&sched->sigverify_ready_bitset[ 0 ]&sched->poh_ready_bitset[ 0 ] );
1394 12 : if( FD_UNLIKELY( block->txn_exec_in_flight_cnt+block->txn_sigverify_in_flight_cnt+block->poh_hashing_in_flight_cnt!=total_exec_busy_cnt ) ) {
1395 : /* Ideally we'd simply assert that the two sides of the equation
1396 : are equal. But abandoned blocks throw a wrench into this. We
1397 : allow abandoned blocks to have in-flight transactions that are
1398 : naturally drained while we try to dispatch from another block.
1399 : In such cases, the total number of in-flight transactions
1400 : should include the abandoned blocks too. The contract is that
1401 : blocks with in-flight transactions cannot be abandoned or
1402 : demoted from rdisp. So a dying block has to be the head of one
1403 : of the staging lanes. */
1404 : // FIXME This contract no longer true if we implement immediate
1405 : // demotion of abandoned blocks.
1406 0 : ulong total_in_flight = 0UL;
1407 0 : for( int l=0; l<(int)FD_SCHED_MAX_STAGING_LANES; l++ ) {
1408 0 : if( fd_ulong_extract_bit( sched->staged_bitset, l ) ) {
1409 0 : fd_sched_block_t * staged_block = block_pool_ele( sched, sched->staged_head_bank_idx[ l ] );
1410 0 : if( FD_UNLIKELY( block_is_in_flight( staged_block )&&!(staged_block==block||staged_block->dying) ) ) {
1411 0 : sched->print_buf_sz = 0UL;
1412 0 : print_all( sched, staged_block );
1413 0 : FD_LOG_NOTICE(( "%s", sched->print_buf ));
1414 0 : FD_LOG_CRIT(( "invariant violation: in-flight block is neither active nor dying" ));
1415 0 : }
1416 0 : total_in_flight += staged_block->txn_exec_in_flight_cnt;
1417 0 : total_in_flight += staged_block->txn_sigverify_in_flight_cnt;
1418 0 : total_in_flight += staged_block->poh_hashing_in_flight_cnt;
1419 0 : }
1420 0 : }
1421 0 : if( FD_UNLIKELY( total_in_flight!=total_exec_busy_cnt ) ) {
1422 0 : sched->print_buf_sz = 0UL;
1423 0 : print_all( sched, block );
1424 0 : FD_LOG_NOTICE(( "%s", sched->print_buf ));
1425 0 : FD_LOG_CRIT(( "invariant violation: total_in_flight %lu != total_exec_busy_cnt %lu", total_in_flight, total_exec_busy_cnt ));
1426 0 : }
1427 0 : FD_LOG_DEBUG(( "exec_busy_cnt %lu checks out", total_exec_busy_cnt ));
1428 0 : }
1429 12 : sched->next_ready_last_tick = now;
1430 12 : sched->next_ready_last_bank_idx = bank_idx;
1431 12 : return 1UL;
1432 12 : }
1433 :
1434 : /* At this point txn_queued_cnt==0 */
1435 :
1436 : /* Next up are PoH tasks. Same dispatching policy as sigverify. */
1437 291 : ulong poh_ready_bitset = exec_fully_ready_bitset;
1438 291 : ulong poh_hashing_queued_cnt = block->mblk_cnt-block->poh_mblk_in_flight_cnt-block->poh_hashing_done_cnt;
1439 291 : int poh_threshold = fd_int_if( block->fec_eos||block->txn_exec_in_flight_cnt>0U||sched->exec_cnt==1UL, 0, 1 );
1440 291 : if( FD_LIKELY( poh_hashing_queued_cnt>0UL && fd_ulong_popcnt( poh_ready_bitset )>poh_threshold ) ) {
1441 228 : ulong max_cnt = poh_batch_max_cnt( sched, poh_hashing_queued_cnt, (ulong)fd_ulong_popcnt( poh_ready_bitset ), (ulong)poh_threshold );
1442 228 : dispatch_poh( sched, block, bank_idx, fd_ulong_find_lsb( poh_ready_bitset ), max_cnt, out );
1443 228 : sched->next_ready_last_tick = fd_tickcount();
1444 228 : sched->next_ready_last_bank_idx = bank_idx;
1445 228 : return 1UL;
1446 228 : }
1447 :
1448 : /* Try to dispatch a sigverify task, but leave one exec tile idle for
1449 : critical path execution, unless there's not going to be any more
1450 : real transactions for the critical path. In the degenerate case of
1451 : only one exec tile, keep it busy. */
1452 63 : ulong sigverify_ready_bitset = exec_fully_ready_bitset;
1453 63 : ulong sigverify_queued_cnt = block->txn_parsed_cnt-block->txn_sigverify_in_flight_cnt-block->txn_sigverify_done_cnt;
1454 63 : if( FD_LIKELY( sigverify_queued_cnt>0UL && fd_ulong_popcnt( sigverify_ready_bitset )>fd_int_if( block->fec_eos||block->txn_exec_in_flight_cnt>0U||sched->exec_cnt==1UL, 0, 1 ) ) ) {
1455 9 : dispatch_sigverify( sched, block, bank_idx, fd_ulong_find_lsb( sigverify_ready_bitset ), out );
1456 9 : sched->next_ready_last_tick = sched->txn_info_pool[ out->txn_sigverify->txn_idx ].tick_sigverify_disp = fd_tickcount();
1457 9 : sched->next_ready_last_bank_idx = bank_idx;
1458 9 : return 1UL;
1459 9 : }
1460 :
1461 54 : if( FD_UNLIKELY( block_should_signal_end( block ) ) ) {
1462 27 : FD_TEST( block->block_start_signaled );
1463 27 : int tick_reason = verify_ticks_final( block );
1464 27 : if( FD_UNLIKELY( tick_reason!=FD_SCHED_DEAD_REASON_NONE ) ) {
1465 : /* Tick verification can't be done at parse time (except for
1466 : TRAILING_ENTRY), because we may not know the expected number of
1467 : hashes yet. It can't be driven by transaction dispatch or
1468 : completion, because the block may be empty. Similarly, it can't
1469 : be driven by PoH hashing, because a bad block may simply not
1470 : have any microblocks. */
1471 3 : handle_bad_block( sched, block, tick_reason );
1472 3 : out->task_type = FD_SCHED_TT_MARK_DEAD;
1473 3 : out->mark_dead->bank_idx = bank_idx;
1474 3 : sched->next_ready_last_tick = fd_tickcount();
1475 3 : sched->next_ready_last_bank_idx = bank_idx;
1476 3 : return 1UL;
1477 3 : }
1478 24 : out->task_type = FD_SCHED_TT_BLOCK_END;
1479 24 : out->block_end->bank_idx = bank_idx;
1480 24 : block->block_end_signaled = 1;
1481 24 : FD_TEST( block->refcnt );
1482 24 : block->refcnt = 0;
1483 24 : FD_TEST( ref_q_avail( sched->ref_q ) );
1484 24 : ref_q_push_tail( sched->ref_q, bank_idx );
1485 24 : sched->next_ready_last_tick = fd_tickcount();
1486 24 : sched->next_ready_last_bank_idx = bank_idx;
1487 24 : return 1UL;
1488 24 : }
1489 :
1490 : /* Nothing queued for the active block. If we haven't received all
1491 : the FEC sets for it, then return and wait for more FEC sets, while
1492 : there are in-flight transactions. This is a policy decision to
1493 : minimize fork churn and allow for executing down the current fork
1494 : as much as we can. If we have received all the FEC sets for it,
1495 : then we'd still like to return and wait for the in-flight
1496 : transactions to retire, before switching to a different block.
1497 :
1498 : Either way, there should be in-flight transactions. We deactivate
1499 : the active block the moment we exhausted transactions from it.
1500 :
1501 : We don't assert block_is_in_flight() here because there might be
1502 : in-flight tasks from dying blocks that are preventing us from
1503 : dispatching anything momentarily. So we assert the global exec
1504 : tile busy count. This doesn't lose too much assertion coverage
1505 : since dying blocks are few and far between. */
1506 27 : ulong total_exec_busy_cnt = sched->exec_cnt-(ulong)fd_ulong_popcnt( exec_fully_ready_bitset );
1507 27 : if( FD_UNLIKELY( !total_exec_busy_cnt ) ) {
1508 0 : sched->print_buf_sz = 0UL;
1509 0 : print_all( sched, block );
1510 0 : FD_LOG_NOTICE(( "%s", sched->print_buf ));
1511 0 : FD_LOG_CRIT(( "invariant violation: expected in-flight tasks but none found" ));
1512 0 : }
1513 :
1514 27 : return 0UL;
1515 27 : }
1516 :
1517 : int
1518 324 : fd_sched_task_done( fd_sched_t * sched, ulong task_type, ulong txn_idx, ulong exec_idx, void * data ) {
1519 324 : FD_TEST( sched->canary==FD_SCHED_MAGIC );
1520 :
1521 324 : ulong bank_idx = ULONG_MAX;
1522 324 : switch( task_type ) {
1523 51 : case FD_SCHED_TT_BLOCK_START:
1524 75 : case FD_SCHED_TT_BLOCK_END: {
1525 75 : (void)txn_idx;
1526 75 : (void)data;
1527 75 : bank_idx = sched->active_bank_idx;
1528 75 : break;
1529 51 : }
1530 12 : case FD_SCHED_TT_TXN_EXEC:
1531 21 : case FD_SCHED_TT_TXN_SIGVERIFY: {
1532 21 : (void)data;
1533 21 : FD_TEST( txn_idx < sched->depth );
1534 21 : bank_idx = sched->tile_to_bank_idx[ exec_idx ];
1535 21 : break;
1536 21 : }
1537 228 : case FD_SCHED_TT_POH_HASH: {
1538 228 : (void)txn_idx;
1539 228 : bank_idx = sched->tile_to_bank_idx[ exec_idx ];
1540 228 : break;
1541 21 : }
1542 0 : default: FD_LOG_CRIT(( "unsupported task_type %lu", task_type ));
1543 324 : }
1544 324 : fd_sched_block_t * block = block_pool_ele( sched, bank_idx );
1545 :
1546 324 : if( FD_UNLIKELY( !block->in_sched ) ) {
1547 0 : FD_LOG_CRIT(( "invariant violation: block->in_sched==0, block %lu:%lu, parent slot %lu",
1548 0 : block->slot, bank_idx, block->parent_slot ));
1549 0 : }
1550 324 : if( FD_UNLIKELY( !block->staged ) ) {
1551 : /* Invariant: only staged blocks can have in-flight transactions. */
1552 0 : FD_LOG_CRIT(( "invariant violation: block->staged==0, block %lu:%lu, parent slot %lu",
1553 0 : block->slot, bank_idx, block->parent_slot ));
1554 0 : }
1555 324 : if( FD_UNLIKELY( !block->in_rdisp ) ) {
1556 : /* Invariant: staged blocks must be in the dispatcher. */
1557 0 : FD_LOG_CRIT(( "invariant violation: block->in_rdisp==0, block %lu:%lu, parent slot %lu",
1558 0 : block->slot, bank_idx, block->parent_slot ));
1559 0 : }
1560 :
1561 324 : block->txn_pool_max_popcnt = fd_ulong_max( block->txn_pool_max_popcnt, sched->depth - sched->txn_pool_free_cnt - 1UL );
1562 324 : block->mblk_pool_max_popcnt = fd_ulong_max( block->mblk_pool_max_popcnt, sched->depth - sched->mblk_pool_free_cnt );
1563 324 : block->block_pool_max_popcnt = fd_ulong_max( block->block_pool_max_popcnt, sched->block_pool_popcnt );
1564 :
1565 324 : int exec_tile_idx = (int)exec_idx;
1566 :
1567 324 : switch( task_type ) {
1568 51 : case FD_SCHED_TT_BLOCK_START: {
1569 51 : FD_TEST( !block->block_start_done );
1570 51 : block->block_start_done = 1;
1571 51 : break;
1572 51 : }
1573 24 : case FD_SCHED_TT_BLOCK_END: {
1574 : /* It may seem redundant to be invoking task_done() on these
1575 : somewhat fake tasks. But these are necessary to drive state
1576 : transition for empty blocks or slow blocks. */
1577 24 : FD_TEST( !block->block_end_done );
1578 24 : block->block_end_done = 1;
1579 24 : sched->print_buf_sz = 0UL;
1580 24 : print_block_metrics( sched, block );
1581 24 : FD_LOG_DEBUG(( "block %lu:%lu replayed fully: %s", block->slot, bank_idx, sched->print_buf ));
1582 24 : break;
1583 24 : }
1584 12 : case FD_SCHED_TT_TXN_EXEC: {
1585 12 : long now = fd_tickcount();
1586 12 : ulong delta = (ulong)(now-sched->txn_in_flight_last_tick);
1587 12 : ulong txn_exec_busy_cnt = sched->exec_cnt-(ulong)fd_ulong_popcnt( sched->txn_exec_ready_bitset[ 0 ] );
1588 12 : sched->metrics->txn_weighted_in_flight_tickcount += delta;
1589 12 : sched->metrics->txn_weighted_in_flight_cnt += delta*txn_exec_busy_cnt;
1590 12 : sched->txn_in_flight_last_tick = now;
1591 :
1592 12 : sched->txn_info_pool[ txn_idx ].tick_exec_done = now;
1593 :
1594 12 : block->txn_exec_done_cnt++;
1595 12 : block->txn_exec_in_flight_cnt--;
1596 12 : FD_TEST( !fd_ulong_extract_bit( sched->txn_exec_ready_bitset[ 0 ], exec_tile_idx ) );
1597 12 : sched->txn_exec_ready_bitset[ 0 ] = fd_ulong_set_bit( sched->txn_exec_ready_bitset[ 0 ], exec_tile_idx );
1598 12 : sched->metrics->txn_exec_done_cnt++;
1599 12 : txn_bitset_insert( sched->exec_done_set, txn_idx );
1600 12 : sched->txn_info_pool[ txn_idx ].flags |= FD_SCHED_TXN_EXEC_DONE;
1601 12 : if( txn_bitset_test( sched->sigverify_done_set, txn_idx ) && txn_bitset_test( sched->poh_mixin_done_set, txn_idx ) ) {
1602 : /* Release the txn_idx if all tasks on it are done. This is
1603 : guaranteed to only happen once per transaction because
1604 : whichever one completed first would not release. */
1605 0 : if( FD_UNLIKELY( block->txn_idx_tail==(uint)txn_idx ) ) block->txn_idx_tail = 0U;
1606 0 : fd_rdisp_complete_txn( sched->rdisp, txn_idx, 1 );
1607 0 : sched->txn_pool_free_cnt++;
1608 0 : block->txn_done_cnt++;
1609 0 : sched->metrics->txn_done_cnt++;
1610 12 : } else {
1611 12 : fd_rdisp_complete_txn( sched->rdisp, txn_idx, 0 );
1612 12 : }
1613 12 : break;
1614 12 : }
1615 9 : case FD_SCHED_TT_TXN_SIGVERIFY: {
1616 9 : sched->txn_info_pool[ txn_idx ].tick_sigverify_done = fd_tickcount();
1617 9 : block->txn_sigverify_done_cnt++;
1618 9 : block->txn_sigverify_in_flight_cnt--;
1619 9 : FD_TEST( !fd_ulong_extract_bit( sched->sigverify_ready_bitset[ 0 ], exec_tile_idx ) );
1620 9 : sched->sigverify_ready_bitset[ 0 ] = fd_ulong_set_bit( sched->sigverify_ready_bitset[ 0 ], exec_tile_idx );
1621 9 : sched->metrics->txn_sigverify_done_cnt++;
1622 9 : txn_bitset_insert( sched->sigverify_done_set, txn_idx );
1623 9 : sched->txn_info_pool[ txn_idx ].flags |= FD_SCHED_TXN_SIGVERIFY_DONE;
1624 9 : if( txn_bitset_test( sched->exec_done_set, txn_idx ) && txn_bitset_test( sched->poh_mixin_done_set, txn_idx ) ) {
1625 : /* Release the txn_idx if all tasks on it are done. This is
1626 : guaranteed to only happen once per transaction because
1627 : whichever one completed first would not release. */
1628 9 : if( FD_UNLIKELY( block->txn_idx_tail==(uint)txn_idx ) ) block->txn_idx_tail = 0U;
1629 9 : fd_rdisp_complete_txn( sched->rdisp, txn_idx, 1 );
1630 9 : sched->txn_pool_free_cnt++;
1631 9 : block->txn_done_cnt++;
1632 9 : sched->metrics->txn_done_cnt++;
1633 9 : }
1634 9 : break;
1635 9 : }
1636 228 : case FD_SCHED_TT_POH_HASH: {
1637 228 : block->poh_hashing_in_flight_cnt--;
1638 228 : FD_TEST( !fd_ulong_extract_bit( sched->poh_ready_bitset[ 0 ], exec_tile_idx ) );
1639 228 : sched->poh_ready_bitset[ 0 ] = fd_ulong_set_bit( sched->poh_ready_bitset[ 0 ], exec_tile_idx );
1640 228 : fd_execrp_poh_hash_done_msg_t * msg = fd_type_pun( data );
1641 228 : FD_TEST( msg->cnt && msg->cnt<=FD_EXECRP_POH_PARA );
1642 228 : fd_sched_poh_hash_t const * task = sched->poh_inflight+exec_tile_idx;
1643 228 : FD_TEST( msg->cnt==task->cnt );
1644 :
1645 : /* Once the block is found to be bad, the remaining elements are
1646 : put back on a list so that they get freed along with the
1647 : block. */
1648 228 : int dead_reason = FD_SCHED_DEAD_REASON_NONE;
1649 456 : for( ulong i=0UL; i<msg->cnt; i++ ) {
1650 228 : block->poh_mblk_in_flight_cnt--;
1651 228 : uint mblk_idx = (uint)task->mblk_idx[ i ];
1652 228 : fd_sched_mblk_t * mblk = sched->mblk_pool+mblk_idx;
1653 228 : mblk->curr_hashcnt += task->hashcnt;
1654 228 : memcpy( mblk->curr_hash, msg->hash+i, sizeof(fd_hash_t) );
1655 228 : if( FD_UNLIKELY( dead_reason!=FD_SCHED_DEAD_REASON_NONE ) || mblk->curr_hashcnt<mblk->hashcnt ) {
1656 132 : mblk_slist_idx_push_tail( block->mblks_hashing_in_progress, mblk_idx, sched->mblk_pool );
1657 132 : continue;
1658 132 : }
1659 96 : dead_reason = poh_retire_mblk( sched, block, mblk_idx );
1660 96 : }
1661 228 : if( FD_LIKELY( dead_reason==FD_SCHED_DEAD_REASON_NONE ) ) dead_reason = poh_retire_ready_mblks( sched, block );
1662 228 : if( FD_UNLIKELY( dead_reason!=FD_SCHED_DEAD_REASON_NONE ) ) {
1663 6 : handle_bad_block( sched, block, dead_reason );
1664 6 : return dead_reason;
1665 6 : }
1666 222 : break;
1667 228 : }
1668 324 : }
1669 :
1670 318 : if( FD_UNLIKELY( block->dying && !block_is_in_flight( block ) ) ) {
1671 0 : if( FD_UNLIKELY( sched->active_bank_idx==bank_idx ) ) {
1672 0 : FD_LOG_CRIT(( "invariant violation: active block %lu:%lu shouldn't be dying, parent slot %lu",
1673 0 : block->slot, bank_idx, block->parent_slot ));
1674 0 : }
1675 0 : FD_LOG_DEBUG(( "dying block %lu:%lu drained", block->slot, bank_idx ));
1676 0 : subtree_abandon( sched, block );
1677 0 : try_activate_block( sched );
1678 0 : return 0;
1679 0 : }
1680 :
1681 318 : if( FD_UNLIKELY( !block->dying && sched->active_bank_idx!=bank_idx ) ) {
1682 : /* Block is not dead. So we should be actively replaying it. */
1683 0 : fd_sched_block_t * active_block = block_pool_ele( sched, sched->active_bank_idx );
1684 0 : FD_LOG_CRIT(( "invariant violation: sched->active_bank_idx %lu, slot %lu, parent slot %lu, bank_idx %lu, slot %lu, parent slot %lu",
1685 0 : sched->active_bank_idx, active_block->slot, active_block->parent_slot,
1686 0 : bank_idx, block->slot, block->parent_slot ));
1687 0 : }
1688 :
1689 318 : maybe_switch_block( sched, bank_idx );
1690 :
1691 318 : return 0;
1692 318 : }
1693 :
1694 : void
1695 15 : fd_sched_block_abandon( fd_sched_t * sched, ulong bank_idx, int cause ) {
1696 15 : FD_TEST( sched->canary==FD_SCHED_MAGIC );
1697 15 : FD_TEST( bank_idx<sched->block_cnt_max );
1698 :
1699 15 : fd_sched_block_t * block = block_pool_ele( sched, bank_idx );
1700 15 : if( FD_UNLIKELY( !block->in_sched ) ) {
1701 0 : FD_LOG_CRIT(( "invariant violation: block->in_sched==0, block %lu:%lu, parent slot %lu",
1702 0 : block->slot, bank_idx, block->parent_slot ));
1703 0 : }
1704 :
1705 15 : if( FD_LIKELY( cause==FD_SCHED_ABANDON_DISCARDED && !block->dying ) ) block->discarded = 1;
1706 :
1707 15 : FD_LOG_INFO(( "abandoning block %lu:%lu", block->slot, bank_idx ));
1708 15 : sched->print_buf_sz = 0UL;
1709 15 : print_all( sched, block );
1710 15 : FD_LOG_DEBUG(( "%s", sched->print_buf ));
1711 :
1712 15 : subtree_abandon( sched, block );
1713 15 : try_activate_block( sched );
1714 15 : }
1715 :
1716 : int
1717 102 : fd_sched_get_dead_reason( fd_sched_t * sched, ulong bank_idx ) {
1718 102 : FD_TEST( sched->canary==FD_SCHED_MAGIC );
1719 102 : FD_TEST( bank_idx<sched->block_cnt_max );
1720 102 : fd_sched_block_t * block = block_pool_ele( sched, bank_idx );
1721 102 : if( FD_UNLIKELY( !block->in_sched ) ) return FD_SCHED_DEAD_REASON_NONE;
1722 102 : return block->dead_reason;
1723 102 : }
1724 :
1725 : int
1726 42 : fd_sched_block_is_discarded( fd_sched_t * sched, ulong bank_idx ) {
1727 42 : FD_TEST( sched->canary==FD_SCHED_MAGIC );
1728 42 : FD_TEST( bank_idx<sched->block_cnt_max );
1729 42 : fd_sched_block_t * block = block_pool_ele( sched, bank_idx );
1730 42 : if( FD_UNLIKELY( !block->in_sched ) ) return 0;
1731 42 : return (int)block->discarded;
1732 42 : }
1733 :
1734 : void
1735 0 : fd_sched_cancel( fd_sched_t * sched, ulong bank_idx ) {
1736 0 : FD_TEST( sched->canary==FD_SCHED_MAGIC );
1737 0 : FD_TEST( bank_idx<sched->block_cnt_max );
1738 :
1739 0 : fd_sched_block_t * block = block_pool_ele( sched, bank_idx );
1740 0 : if( FD_UNLIKELY( !block->in_sched ) ) return;
1741 0 : FD_LOG_INFO(( "canceling subtree at block %lu:%lu", block->slot, bank_idx ));
1742 0 : fd_sched_block_t * parent = block_pool_ele( sched, block->parent_idx );
1743 0 : if( FD_LIKELY( parent ) ) {
1744 : /* Splice the block out of its parent's children list. */
1745 0 : ulong block_idx = block_to_idx( sched, block );
1746 0 : ulong * idx_p = &parent->child_idx;
1747 0 : while( *idx_p!=block_idx ) {
1748 0 : idx_p = &(block_pool_ele( sched, *idx_p )->sibling_idx);
1749 0 : }
1750 0 : *idx_p = block->sibling_idx;
1751 0 : }
1752 0 : subtree_prune( sched, bank_idx, ULONG_MAX );
1753 0 : }
1754 :
1755 : void
1756 96 : fd_sched_block_add_done( fd_sched_t * sched, ulong bank_idx, ulong parent_bank_idx, ulong slot ) {
1757 96 : FD_TEST( sched->canary==FD_SCHED_MAGIC );
1758 96 : FD_TEST( bank_idx<sched->block_cnt_max );
1759 :
1760 96 : fd_sched_block_t * block = block_pool_ele( sched, bank_idx );
1761 96 : add_block( sched, bank_idx, parent_bank_idx );
1762 96 : block->slot = slot;
1763 96 : block->fec_eos = 1;
1764 96 : block->block_start_signaled = 1;
1765 96 : block->block_end_signaled = 1;
1766 96 : block->block_start_done = 1;
1767 96 : block->block_end_done = 1;
1768 96 : block->refcnt = 0;
1769 96 : if( FD_LIKELY( parent_bank_idx!=ULONG_MAX ) ) {
1770 6 : fd_sched_block_t * parent_block = block_pool_ele( sched, parent_bank_idx );
1771 6 : block->parent_slot = parent_block->slot;
1772 6 : }
1773 96 : if( FD_UNLIKELY( parent_bank_idx==ULONG_MAX ) ) {
1774 : /* Assumes that a NULL parent implies the snapshot slot. */
1775 90 : block->parent_slot = ULONG_MAX;
1776 90 : block->rooted = 1;
1777 90 : sched->root_idx = bank_idx;
1778 90 : }
1779 96 : }
1780 :
1781 : void
1782 0 : fd_sched_advance_root( fd_sched_t * sched, ulong root_idx ) {
1783 0 : FD_TEST( sched->canary==FD_SCHED_MAGIC );
1784 0 : FD_TEST( root_idx<sched->block_cnt_max );
1785 0 : FD_TEST( sched->root_idx<sched->block_cnt_max );
1786 0 : FD_TEST( ref_q_empty( sched->ref_q ) );
1787 :
1788 0 : fd_sched_block_t * new_root = block_pool_ele( sched, root_idx );
1789 0 : fd_sched_block_t * old_root = block_pool_ele( sched, sched->root_idx );
1790 0 : if( FD_UNLIKELY( !old_root->rooted ) ) {
1791 0 : FD_LOG_CRIT(( "invariant violation: old_root is not rooted, slot %lu, parent slot %lu",
1792 0 : old_root->slot, old_root->parent_slot ));
1793 0 : }
1794 :
1795 : /* Early exit if the new root is the same as the old root. */
1796 0 : if( FD_UNLIKELY( root_idx==sched->root_idx ) ) {
1797 0 : FD_LOG_INFO(( "new root is the same as the old root, slot %lu, parent slot %lu",
1798 0 : new_root->slot, new_root->parent_slot ));
1799 0 : return;
1800 0 : }
1801 :
1802 0 : subtree_prune( sched, sched->root_idx, root_idx );
1803 :
1804 0 : new_root->parent_idx = ULONG_MAX;
1805 0 : sched->root_idx = root_idx;
1806 0 : }
1807 :
1808 : void
1809 6 : fd_sched_root_notify( fd_sched_t * sched, ulong root_idx ) {
1810 6 : FD_TEST( sched->canary==FD_SCHED_MAGIC );
1811 6 : FD_TEST( root_idx<sched->block_cnt_max );
1812 6 : FD_TEST( sched->root_idx<sched->block_cnt_max );
1813 6 : FD_TEST( ref_q_empty( sched->ref_q ) );
1814 :
1815 6 : fd_sched_block_t * block = block_pool_ele( sched, root_idx );
1816 6 : fd_sched_block_t * old_root = block_pool_ele( sched, sched->root_idx );
1817 6 : if( FD_UNLIKELY( !old_root->rooted ) ) {
1818 0 : FD_LOG_CRIT(( "invariant violation: old_root is not rooted, slot %lu, parent slot %lu",
1819 0 : old_root->slot, old_root->parent_slot ));
1820 0 : }
1821 :
1822 : /* Early exit if the new root is the same as the old root. */
1823 6 : if( FD_UNLIKELY( root_idx==sched->root_idx ) ) {
1824 0 : FD_LOG_INFO(( "new root is the same as the old root, slot %lu, parent slot %lu",
1825 0 : block->slot, block->parent_slot ));
1826 0 : return;
1827 0 : }
1828 :
1829 : /* Mark every node from the new root up through its parents to the
1830 : old root as being rooted. */
1831 6 : fd_sched_block_t * curr = block;
1832 6 : fd_sched_block_t * prev = NULL;
1833 18 : while( curr ) {
1834 12 : if( FD_UNLIKELY( !block_is_done( curr ) ) ) {
1835 0 : FD_LOG_CRIT(( "invariant violation: rooting a block that is not done, slot %lu, parent slot %lu",
1836 0 : curr->slot, curr->parent_slot ));
1837 0 : }
1838 12 : if( FD_UNLIKELY( curr->dying ) ) {
1839 0 : FD_LOG_CRIT(( "invariant violation: rooting a block that is dying, slot %lu, parent slot %lu",
1840 0 : curr->slot, curr->parent_slot ));
1841 0 : }
1842 12 : if( FD_UNLIKELY( curr->staged ) ) {
1843 0 : FD_LOG_CRIT(( "invariant violation: rooting a block that is staged, slot %lu, parent slot %lu",
1844 0 : curr->slot, curr->parent_slot ));
1845 0 : }
1846 12 : if( FD_UNLIKELY( curr->in_rdisp ) ) {
1847 0 : FD_LOG_CRIT(( "invariant violation: rooting a block that is in the dispatcher, slot %lu, parent slot %lu",
1848 0 : curr->slot, curr->parent_slot ));
1849 0 : }
1850 12 : curr->rooted = 1;
1851 12 : prev = curr;
1852 12 : curr = block_pool_ele( sched, curr->parent_idx );
1853 12 : }
1854 :
1855 : /* If we didn't reach the old root, the new root is not a descendant. */
1856 6 : if( FD_UNLIKELY( prev!=old_root ) ) {
1857 0 : FD_LOG_CRIT(( "invariant violation: new root is not a descendant of old root, new root slot %lu, parent slot %lu, old root slot %lu, parent slot %lu",
1858 0 : block->slot, block->parent_slot, old_root->slot, old_root->parent_slot ));
1859 0 : }
1860 :
1861 6 : ulong old_active_bank_idx = sched->active_bank_idx;
1862 :
1863 : /* Now traverse from old root towards new root, and abandon all
1864 : minority forks. */
1865 6 : curr = old_root;
1866 12 : while( curr && curr->rooted && curr!=block ) { /* curr!=block to avoid abandoning good forks. */
1867 6 : fd_sched_block_t * rooted_child_block = NULL;
1868 6 : ulong child_idx = curr->child_idx;
1869 21 : while( child_idx!=ULONG_MAX ) {
1870 15 : fd_sched_block_t * child = block_pool_ele( sched, child_idx );
1871 15 : child_idx = child->sibling_idx;
1872 15 : if( child->rooted ) {
1873 6 : rooted_child_block = child;
1874 9 : } else {
1875 : /* This is a minority fork. Consensus converged elsewhere, so
1876 : the fork is discarded rather than invalid. Mark the subtree
1877 : root as discarded so subtree_abandon() propagates the flag
1878 : down.
1879 :
1880 : Gated on the block not already going down. A block that is
1881 : already dying was abandoned for a reason of its own, either
1882 : sched's own verdict or runtime's verdict on its validity, and
1883 : losing the fork choice race afterwards must not re-label it
1884 : discarded. */
1885 9 : if( FD_LIKELY( !child->dying ) ) child->discarded = 1;
1886 :
1887 9 : ulong abandoned_cnt = sched->metrics->block_abandoned_cnt;
1888 9 : subtree_abandon( sched, child );
1889 9 : abandoned_cnt = sched->metrics->block_abandoned_cnt-abandoned_cnt;
1890 9 : if( FD_UNLIKELY( abandoned_cnt ) ) FD_LOG_DEBUG(( "abandoned %lu blocks on minority fork starting at block %lu:%lu", abandoned_cnt, child->slot, block_to_idx( sched, child ) ));
1891 9 : }
1892 15 : }
1893 6 : curr = rooted_child_block;
1894 6 : }
1895 :
1896 : /* If the active block got abandoned, we need to reset it. */
1897 6 : if( sched->active_bank_idx==ULONG_MAX ) {
1898 6 : sched->metrics->deactivate_pruned_cnt += fd_uint_if( old_active_bank_idx!=ULONG_MAX, 1U, 0U );
1899 6 : try_activate_block( sched );
1900 6 : }
1901 6 : }
1902 :
1903 : ulong
1904 399 : fd_sched_pruned_block_next( fd_sched_t * sched ) {
1905 399 : if( !ref_q_empty( sched->ref_q ) ) {
1906 102 : ulong bank_idx = ref_q_pop_head( sched->ref_q );
1907 102 : return bank_idx;
1908 102 : }
1909 297 : return ULONG_MAX;
1910 399 : }
1911 :
1912 : void
1913 72 : fd_sched_set_poh_params( fd_sched_t * sched, ulong bank_idx, ulong tick_height, ulong max_tick_height, ulong hashes_per_tick, fd_hash_t const * start_poh ) {
1914 72 : FD_TEST( sched->canary==FD_SCHED_MAGIC );
1915 72 : FD_TEST( bank_idx<sched->block_cnt_max );
1916 72 : FD_TEST( max_tick_height>tick_height );
1917 72 : fd_sched_block_t * block = block_pool_ele( sched, bank_idx );
1918 72 : block->tick_height = tick_height;
1919 72 : block->max_tick_height = max_tick_height;
1920 72 : block->hashes_per_tick = hashes_per_tick;
1921 : #if FD_SCHED_SKIP_POH
1922 : /* No-op. */
1923 : (void)start_poh;
1924 : #else
1925 72 : if( FD_LIKELY( block->mblk_cnt ) ) {
1926 : /* Fix up the first mblk's curr_hash. */
1927 33 : FD_TEST( block->mblk_unhashed_cnt );
1928 33 : FD_TEST( !mblk_slist_is_empty( block->mblks_unhashed, sched->mblk_pool ) );
1929 33 : FD_TEST( !block->mblk_freed_cnt );
1930 33 : fd_sched_mblk_t * first_mblk = sched->mblk_pool + mblk_slist_idx_peek_head( block->mblks_unhashed, sched->mblk_pool );
1931 33 : memcpy( first_mblk->curr_hash, start_poh, sizeof(fd_hash_t) );
1932 39 : } else {
1933 39 : memcpy( block->poh_hash, start_poh, sizeof(fd_hash_t) );
1934 39 : }
1935 72 : #endif
1936 72 : }
1937 :
1938 : void
1939 6 : fd_sched_set_bypass_poh_verify( fd_sched_t * sched, int bypass_poh_verify ) {
1940 6 : FD_TEST( sched->canary==FD_SCHED_MAGIC );
1941 6 : sched->bypass_poh_verify = !!bypass_poh_verify;
1942 6 : }
1943 :
1944 : void
1945 0 : fd_sched_set_bypass_alut_resolution( fd_sched_t * sched, int bypass_alut_resolution ) {
1946 0 : FD_TEST( sched->canary==FD_SCHED_MAGIC );
1947 0 : sched->bypass_alut_resolution = !!bypass_alut_resolution;
1948 0 : }
1949 :
1950 : fd_txn_p_t *
1951 6 : fd_sched_get_txn( fd_sched_t * sched, ulong txn_idx ) {
1952 6 : FD_TEST( sched->canary==FD_SCHED_MAGIC );
1953 6 : if( FD_UNLIKELY( txn_idx>=sched->depth ) ) {
1954 0 : return NULL;
1955 0 : }
1956 6 : return sched->txn_pool+txn_idx;
1957 6 : }
1958 :
1959 : fd_sched_txn_info_t *
1960 0 : fd_sched_get_txn_info( fd_sched_t * sched, ulong txn_idx ) {
1961 0 : FD_TEST( sched->canary==FD_SCHED_MAGIC );
1962 0 : if( FD_UNLIKELY( txn_idx>=sched->depth ) ) {
1963 0 : return NULL;
1964 0 : }
1965 0 : return sched->txn_info_pool+txn_idx;
1966 0 : }
1967 :
1968 : fd_hash_t *
1969 0 : fd_sched_get_poh( fd_sched_t * sched, ulong bank_idx ) {
1970 0 : FD_TEST( sched->canary==FD_SCHED_MAGIC );
1971 0 : FD_TEST( bank_idx<sched->block_cnt_max );
1972 0 : fd_sched_block_t * block = block_pool_ele( sched, bank_idx );
1973 0 : FD_TEST( block->fec_eos );
1974 0 : FD_TEST( block->mblk_cnt );
1975 0 : return block->poh_hash;
1976 0 : }
1977 :
1978 : uint
1979 9 : fd_sched_get_shred_cnt( fd_sched_t * sched, ulong bank_idx ) {
1980 9 : FD_TEST( sched->canary==FD_SCHED_MAGIC );
1981 9 : FD_TEST( bank_idx<sched->block_cnt_max );
1982 9 : fd_sched_block_t * block = block_pool_ele( sched, bank_idx );
1983 9 : return block->shred_cnt;
1984 9 : }
1985 :
1986 : fd_block_footer_t const *
1987 0 : fd_sched_get_footer( fd_sched_t * sched, ulong bank_idx ) {
1988 0 : FD_TEST( sched->canary==FD_SCHED_MAGIC );
1989 0 : FD_TEST( bank_idx<sched->block_cnt_max );
1990 0 : fd_sched_block_t * block = block_pool_ele( sched, bank_idx );
1991 0 : return block->footer_seen ? &block->footer : NULL;
1992 0 : }
1993 :
1994 : void
1995 0 : fd_sched_metrics_write( fd_sched_t * sched ) {
1996 0 : FD_MGAUGE_SET( REPLAY, SCHED_ACTIVE_BANK_INDEX, sched->active_bank_idx );
1997 0 : FD_MGAUGE_SET( REPLAY, SCHED_LAST_DISPATCH_BANK_INDEX, sched->next_ready_last_bank_idx );
1998 0 : FD_MGAUGE_SET( REPLAY, SCHED_LAST_DISPATCH_TIMESTAMP_NANOS, fd_ulong_if( sched->next_ready_last_tick!=LONG_MAX, (ulong)sched->next_ready_last_tick, ULONG_MAX ) );
1999 0 : FD_MGAUGE_SET( REPLAY, SCHED_STAGING_LANE_OCCUPIED, (ulong)fd_ulong_popcnt( sched->staged_bitset ) );
2000 0 : FD_MGAUGE_SET( REPLAY, SCHED_STAGING_LANE_OCCUPIED_WATERMARK, sched->staged_popcnt_wmk );
2001 0 : ulong staging_lane_head_bank_idx[ FD_METRICS_ENUM_STAGING_LANE_CNT ];
2002 0 : for( ulong lane=0UL; lane<FD_METRICS_ENUM_STAGING_LANE_CNT; lane++ ) {
2003 0 : staging_lane_head_bank_idx[ lane ] = fd_ulong_if( fd_ulong_extract_bit( sched->staged_bitset, (int)lane ), sched->staged_head_bank_idx[ lane ], ULONG_MAX );
2004 0 : }
2005 0 : FD_MGAUGE_ENUM_COPY( REPLAY, SCHED_STAGING_LANE_HEAD_BANK_INDEX, staging_lane_head_bank_idx );
2006 0 : FD_MGAUGE_SET( REPLAY, SCHED_TXN_POOL_OCCUPIED, sched->depth-sched->txn_pool_free_cnt-1UL );
2007 0 : FD_MGAUGE_SET( REPLAY, SCHED_TXN_POOL_SIZE, sched->depth-1UL );
2008 0 : FD_MGAUGE_SET( REPLAY, SCHED_MICROBLOCK_POOL_OCCUPIED, sched->depth-sched->mblk_pool_free_cnt );
2009 0 : FD_MGAUGE_SET( REPLAY, SCHED_MICROBLOCK_POOL_SIZE, sched->depth );
2010 0 : FD_MGAUGE_SET( REPLAY, SCHED_BLOCK_POOL_OCCUPIED, sched->block_pool_popcnt );
2011 0 : FD_MGAUGE_SET( REPLAY, SCHED_BLOCK_POOL_SIZE, sched->block_cnt_max );
2012 :
2013 0 : ulong sched_block_added[ FD_METRICS_ENUM_SCHED_BLOCK_STAGING_CNT ];
2014 0 : sched_block_added[ FD_METRICS_ENUM_SCHED_BLOCK_STAGING_V_STAGED_IDX ] = sched->metrics->block_added_staged_cnt;
2015 0 : sched_block_added[ FD_METRICS_ENUM_SCHED_BLOCK_STAGING_V_UNSTAGED_IDX ] = sched->metrics->block_added_unstaged_cnt;
2016 0 : FD_MCNT_ENUM_COPY( REPLAY, SCHED_BLOCK_ADDED, sched_block_added );
2017 0 : FD_MCNT_SET( REPLAY, SCHED_BLOCK_REPLAYED, sched->metrics->block_removed_cnt );
2018 0 : FD_MCNT_SET( REPLAY, SCHED_BLOCK_ABANDONED, sched->metrics->block_abandoned_cnt );
2019 0 : FD_MCNT_SET( REPLAY, SCHED_BLOCK_REJECTED, sched->metrics->block_bad_cnt );
2020 0 : FD_MCNT_SET( REPLAY, SCHED_BLOCK_PROMOTED, sched->metrics->block_promoted_cnt );
2021 0 : FD_MCNT_SET( REPLAY, SCHED_BLOCK_DEMOTED, sched->metrics->block_demoted_cnt );
2022 0 : ulong sched_deactivate[ FD_METRICS_ENUM_SCHED_DEACTIVATE_REASON_CNT ];
2023 0 : sched_deactivate[ FD_METRICS_ENUM_SCHED_DEACTIVATE_REASON_V_NO_CHILD_IDX ] = sched->metrics->deactivate_no_child_cnt;
2024 0 : sched_deactivate[ FD_METRICS_ENUM_SCHED_DEACTIVATE_REASON_V_NO_WORK_IDX ] = sched->metrics->deactivate_no_txn_cnt;
2025 0 : sched_deactivate[ FD_METRICS_ENUM_SCHED_DEACTIVATE_REASON_V_ABANDONED_IDX ] = sched->metrics->deactivate_abandoned_cnt;
2026 0 : sched_deactivate[ FD_METRICS_ENUM_SCHED_DEACTIVATE_REASON_V_MINORITY_IDX ] = sched->metrics->deactivate_pruned_cnt;
2027 0 : FD_MCNT_ENUM_COPY( REPLAY, SCHED_DEACTIVATE, sched_deactivate );
2028 0 : FD_MCNT_SET( REPLAY, SCHED_LANE_SWITCHED, sched->metrics->lane_switch_cnt );
2029 0 : FD_MCNT_SET( REPLAY, SCHED_LANE_PROMOTED, sched->metrics->lane_promoted_cnt );
2030 0 : FD_MCNT_SET( REPLAY, SCHED_LANE_DEMOTED, sched->metrics->lane_demoted_cnt );
2031 0 : FD_MCNT_SET( REPLAY, SCHED_FORK_OBSERVED, sched->metrics->fork_observed_cnt );
2032 0 : ulong sched_alut[ FD_METRICS_ENUM_SCHED_ALUT_RESULT_CNT ];
2033 0 : sched_alut[ FD_METRICS_ENUM_SCHED_ALUT_RESULT_V_SUCCESS_IDX ] = sched->metrics->alut_success_cnt;
2034 0 : sched_alut[ FD_METRICS_ENUM_SCHED_ALUT_RESULT_V_FAILED_IDX ] = sched->metrics->alut_serializing_cnt;
2035 0 : FD_MCNT_ENUM_COPY( REPLAY, SCHED_ALUT, sched_alut );
2036 0 : FD_MCNT_SET( REPLAY, SCHED_TXN_PARSED_ABANDONED, sched->metrics->txn_abandoned_parsed_cnt );
2037 0 : FD_MCNT_SET( REPLAY, SCHED_TXN_EXECUTED_ABANDONED, sched->metrics->txn_abandoned_exec_done_cnt );
2038 0 : FD_MCNT_SET( REPLAY, SCHED_TXN_DONE_ABANDONED, sched->metrics->txn_abandoned_done_cnt );
2039 0 : FD_MCNT_SET( REPLAY, SCHED_WEIGHTED_IN_FLIGHT, sched->metrics->txn_weighted_in_flight_cnt );
2040 0 : FD_MCNT_SET( REPLAY, SCHED_WEIGHTED_IN_FLIGHT_DURATION_NANOS, sched->metrics->txn_weighted_in_flight_tickcount );
2041 0 : FD_MCNT_SET( REPLAY, SCHED_NONE_IN_FLIGHT_DURATION_NANOS, sched->metrics->txn_none_in_flight_tickcount );
2042 0 : FD_MCNT_SET( REPLAY, SCHED_TXN_PARSED, sched->metrics->txn_parsed_cnt );
2043 0 : FD_MCNT_SET( REPLAY, SCHED_TXN_EXECUTED, sched->metrics->txn_exec_done_cnt );
2044 0 : FD_MCNT_SET( REPLAY, SCHED_TXN_SIGNATURE_VERIFIED, sched->metrics->txn_sigverify_done_cnt );
2045 0 : FD_MCNT_SET( REPLAY, SCHED_TXN_POH_MIXED, sched->metrics->txn_mixin_done_cnt );
2046 0 : FD_MCNT_SET( REPLAY, SCHED_TXN_DONE, sched->metrics->txn_done_cnt );
2047 0 : FD_MCNT_SET( REPLAY, SCHED_MICROBLOCK_PARSED, sched->metrics->mblk_parsed_cnt );
2048 0 : FD_MCNT_SET( REPLAY, SCHED_MICROBLOCK_HASHED, sched->metrics->mblk_poh_hashed_cnt );
2049 0 : FD_MCNT_SET( REPLAY, SCHED_MICROBLOCK_DONE, sched->metrics->mblk_poh_done_cnt );
2050 0 : FD_MCNT_SET( REPLAY, SCHED_BYTES_INGESTED, sched->metrics->bytes_ingested_cnt );
2051 0 : FD_MCNT_SET( REPLAY, SCHED_BYTES_INGESTED_PADDING, sched->metrics->bytes_ingested_unparsed_cnt );
2052 0 : FD_MCNT_SET( REPLAY, SCHED_BYTES_DROPPED, sched->metrics->bytes_dropped_cnt );
2053 0 : FD_MCNT_SET( REPLAY, SCHED_FEC_INGESTED, sched->metrics->fec_cnt );
2054 0 : }
2055 :
2056 : char *
2057 9 : fd_sched_get_state_cstr( fd_sched_t * sched ) {
2058 9 : sched->print_buf_sz = 0UL;
2059 9 : print_metrics( sched );
2060 9 : print_sched( sched );
2061 9 : return sched->print_buf;
2062 9 : }
2063 :
2064 90 : void * fd_sched_leave ( fd_sched_t * sched ) { return sched; }
2065 90 : void * fd_sched_delete( void * mem ) { return mem; }
2066 :
2067 :
2068 : /* Internal helpers. */
2069 :
2070 : static void
2071 : add_block( fd_sched_t * sched,
2072 : ulong bank_idx,
2073 225 : ulong parent_bank_idx ) {
2074 225 : fd_sched_block_t * block = block_pool_ele( sched, bank_idx );
2075 225 : FD_TEST( !block->in_sched );
2076 225 : sched->block_pool_popcnt++;
2077 :
2078 225 : block->txn_parsed_cnt = 0U;
2079 225 : block->txn_exec_in_flight_cnt = 0U;
2080 225 : block->txn_exec_done_cnt = 0U;
2081 225 : block->txn_sigverify_in_flight_cnt = 0U;
2082 225 : block->txn_sigverify_done_cnt = 0U;
2083 225 : block->poh_hashing_in_flight_cnt = 0U;
2084 225 : block->poh_mblk_in_flight_cnt = 0U;
2085 225 : block->poh_hashing_done_cnt = 0U;
2086 225 : block->poh_hash_cmp_done_cnt = 0U;
2087 225 : block->txn_done_cnt = 0U;
2088 225 : block->shred_cnt = 0U;
2089 225 : block->shred_scan_idx = 0U;
2090 225 : block->shred_scan_off = 0U;
2091 225 : block->mblk_cnt = 0U;
2092 225 : block->mblk_freed_cnt = 0U;
2093 225 : block->mblk_tick_cnt = 0U;
2094 225 : block->mblk_unhashed_cnt = 0U;
2095 225 : block->hashcnt = 0UL;
2096 225 : block->dead_reason = FD_SCHED_DEAD_REASON_NONE;
2097 225 : block->txn_pool_max_popcnt = sched->depth - sched->txn_pool_free_cnt - 1UL;
2098 225 : block->mblk_pool_max_popcnt = sched->depth - sched->mblk_pool_free_cnt;
2099 225 : block->block_pool_max_popcnt = sched->block_pool_popcnt;
2100 225 : block->txn_idx_tail = 0U;
2101 225 : block->txn_sigverify_next_idx = 0U;
2102 225 : block->parse_mblk_idx = UINT_MAX;
2103 :
2104 225 : mblk_slist_remove_all( block->mblks_unhashed, sched->mblk_pool );
2105 225 : mblk_slist_remove_all( block->mblks_hashing_in_progress, sched->mblk_pool );
2106 225 : mblk_slist_remove_all( block->mblks_mixin_in_progress, sched->mblk_pool );
2107 225 : block->last_mblk_is_tick = 0;
2108 225 : block->tick_hashcnt_wmk = 0UL;
2109 225 : block->curr_tick_hashcnt = 0UL;
2110 225 : block->tick_height = ULONG_MAX;
2111 225 : block->max_tick_height = ULONG_MAX;
2112 225 : block->hashes_per_tick = ULONG_MAX;
2113 225 : block->inconsistent_hashes_per_tick = 0;
2114 225 : block->zero_hash_tick = 0;
2115 :
2116 225 : block->header_seen = 0;
2117 225 : block->genesis_cert_seen = 0;
2118 225 : block->footer_seen = 0;
2119 225 : block->alpentick_seen = 0;
2120 :
2121 225 : block->mblks_rem = 0UL;
2122 225 : block->txns_rem = 0UL;
2123 225 : block->fec_buf_sz = 0U;
2124 225 : block->fec_buf_boff = 0U;
2125 225 : block->fec_buf_soff = 0U;
2126 225 : block->poison_cnt = 0U;
2127 225 : block->poison_serialize = 0;
2128 225 : block->fec_eob = 0;
2129 225 : block->fec_sob = 1;
2130 :
2131 225 : block->fec_eos = 0;
2132 225 : block->rooted = 0;
2133 225 : block->dying = 0;
2134 225 : block->discarded = 0;
2135 225 : block->fec_completed_ns = 0L;
2136 225 : block->refcnt = 1;
2137 225 : block->in_sched = 1;
2138 225 : block->in_rdisp = 0;
2139 225 : block->block_start_signaled = 0;
2140 225 : block->block_end_signaled = 0;
2141 225 : block->block_start_done = 0;
2142 225 : block->block_end_done = 0;
2143 225 : block->staged = 0;
2144 :
2145 225 : block->luf_depth = 0UL;
2146 :
2147 : /* New leaf node, no child, no sibling. */
2148 225 : block->child_idx = ULONG_MAX;
2149 225 : block->sibling_idx = ULONG_MAX;
2150 225 : block->parent_idx = ULONG_MAX;
2151 :
2152 225 : if( FD_UNLIKELY( parent_bank_idx==ULONG_MAX ) ) {
2153 90 : return;
2154 90 : }
2155 :
2156 : /* node->parent link */
2157 135 : fd_sched_block_t * parent_block = block_pool_ele( sched, parent_bank_idx );
2158 135 : block->parent_idx = parent_bank_idx;
2159 :
2160 : /* parent->node and sibling->node links */
2161 135 : ulong child_idx = bank_idx;
2162 135 : if( FD_LIKELY( parent_block->child_idx==ULONG_MAX ) ) { /* Optimize for no forking. */
2163 108 : parent_block->child_idx = child_idx;
2164 108 : } else {
2165 27 : fd_sched_block_t * curr_block = block_pool_ele( sched, parent_block->child_idx );
2166 48 : while( curr_block->sibling_idx!=ULONG_MAX ) {
2167 21 : curr_block = block_pool_ele( sched, curr_block->sibling_idx );
2168 21 : }
2169 27 : curr_block->sibling_idx = child_idx;
2170 27 : sched->metrics->fork_observed_cnt++;
2171 27 : }
2172 :
2173 135 : if( FD_UNLIKELY( parent_block->dying ) ) {
2174 12 : record_lineage_death( block, parent_block );
2175 12 : block->dying = 1;
2176 12 : }
2177 135 : }
2178 :
2179 : /* Alpenglow block structure. agave's BlockComponentProcessor rules
2180 : an Alpenglow block invalid unless its components are laid out as
2181 :
2182 : header | [genesis cert] | entries* | footer | alpentick
2183 :
2184 : with exactly one header and one footer, and the alpentick as the
2185 : final component. The helpers below drive the same state machine off
2186 : the batches sched parses.
2187 :
2188 : TODO feature gate FLH */
2189 :
2190 : static int
2191 : ag_on_marker( fd_sched_t * sched,
2192 : fd_sched_block_t * block,
2193 57 : fd_block_marker_t const * marker ) {
2194 57 : (void)sched;
2195 57 : switch( marker->kind ) {
2196 :
2197 27 : case FD_BLOCK_MARKER_KIND_HEADER:
2198 27 : if( FD_UNLIKELY( block->header_seen ) ) {
2199 3 : FD_LOG_INFO(( "bad block: MULTIPLE_BLOCK_HEADERS, slot %lu, parent slot %lu", block->slot, block->parent_slot ));
2200 3 : return FD_SCHED_DEAD_REASON_MULTIPLE_BLOCK_HEADERS;
2201 3 : }
2202 : /* Checking for shred header and parent_slot mismatch occurs at the
2203 : rotor level, so it does not need to be checked in sched. We do
2204 : this because currently replay tile never sees shred headers. */
2205 24 : block->header_seen = 1;
2206 24 : return FD_SCHED_DEAD_REASON_NONE;
2207 :
2208 0 : case FD_BLOCK_MARKER_KIND_GENESIS_CERT:
2209 0 : if( FD_UNLIKELY( !block->header_seen ) ) {
2210 0 : FD_LOG_INFO(( "bad block: MISSING_PARENT_MARKER, slot %lu, parent slot %lu, genesis cert before header", block->slot, block->parent_slot ));
2211 0 : return FD_SCHED_DEAD_REASON_MISSING_PARENT_MARKER;
2212 0 : }
2213 0 : if( FD_UNLIKELY( block->mblk_cnt || block->genesis_cert_seen || block->footer_seen ) ) {
2214 0 : FD_LOG_INFO(( "bad block: GENESIS_CERT_OUT_OF_ORDER, slot %lu, parent slot %lu", block->slot, block->parent_slot ));
2215 0 : return FD_SCHED_DEAD_REASON_GENESIS_CERT_OUT_OF_ORDER;
2216 0 : }
2217 0 : block->genesis_cert_seen = 1;
2218 0 : return FD_SCHED_DEAD_REASON_NONE;
2219 :
2220 24 : case FD_BLOCK_MARKER_KIND_FOOTER:
2221 24 : if( FD_UNLIKELY( !block->header_seen ) ) {
2222 3 : FD_LOG_INFO(( "bad block: MISSING_PARENT_MARKER, slot %lu, parent slot %lu, footer before header", block->slot, block->parent_slot ));
2223 3 : return FD_SCHED_DEAD_REASON_MISSING_PARENT_MARKER;
2224 3 : }
2225 21 : if( FD_UNLIKELY( block->footer_seen ) ) {
2226 3 : FD_LOG_INFO(( "bad block: MULTIPLE_BLOCK_FOOTERS, slot %lu, parent slot %lu", block->slot, block->parent_slot ));
2227 3 : return FD_SCHED_DEAD_REASON_MULTIPLE_BLOCK_FOOTERS;
2228 3 : }
2229 18 : block->footer = marker->footer;
2230 18 : block->footer_seen = 1;
2231 18 : return FD_SCHED_DEAD_REASON_NONE;
2232 :
2233 6 : case FD_BLOCK_MARKER_KIND_UPDATE_PARENT:
2234 6 : if( FD_UNLIKELY( !block->header_seen || block->footer_seen ) ) {
2235 6 : FD_LOG_INFO(( "bad block: SPURIOUS_UPDATE_PARENT, slot %lu, parent slot %lu, header %d footer %d", block->slot, block->parent_slot, block->header_seen, block->footer_seen ));
2236 6 : return FD_SCHED_DEAD_REASON_SPURIOUS_UPDATE_PARENT;
2237 6 : }
2238 0 : FD_LOG_INFO(( "bad block: SPURIOUS_UPDATE_PARENT, FLH not activated, slot %lu, parent slot %lu, new_parent_slot %lu", block->slot, block->parent_slot, marker->update_parent.new_parent_slot ));
2239 0 : return FD_SCHED_DEAD_REASON_SPURIOUS_UPDATE_PARENT;
2240 :
2241 0 : default:
2242 0 : FD_LOG_INFO(( "bad block: slot %lu, parent slot %lu, unknown block marker kind %u", block->slot, block->parent_slot, marker->kind ));
2243 0 : return FD_SCHED_DEAD_REASON_BAD_BLOCK_MARKER;
2244 57 : }
2245 57 : }
2246 :
2247 : /* Called when a batch header declares one or more microblocks. */
2248 :
2249 : static int
2250 21 : ag_on_entry_batch( fd_sched_block_t * block ) {
2251 21 : if( FD_UNLIKELY( !block->header_seen ) ) {
2252 3 : FD_LOG_INFO(( "bad block: MISSING_PARENT_MARKER, slot %lu, parent slot %lu, entries before header", block->slot, block->parent_slot ));
2253 3 : return FD_SCHED_DEAD_REASON_MISSING_PARENT_MARKER;
2254 3 : }
2255 18 : if( FD_UNLIKELY( block->alpentick_seen ) ) {
2256 3 : FD_LOG_INFO(( "bad block: ENTRY_AFTER_BLOCK_FOOTER, slot %lu, parent slot %lu, batch after alpentick", block->slot, block->parent_slot ));
2257 3 : return FD_SCHED_DEAD_REASON_ENTRY_AFTER_BLOCK_FOOTER;
2258 3 : }
2259 : /* Only the alpentick may follow the footer: a batch of exactly one
2260 : microblock which must turn out to be a tick (checked when its
2261 : header parses). */
2262 15 : if( FD_UNLIKELY( block->footer_seen && block->mblks_rem!=1UL ) ) {
2263 0 : FD_LOG_INFO(( "bad block: ENTRY_AFTER_BLOCK_FOOTER, slot %lu, parent slot %lu, batch of %lu microblocks after footer", block->slot, block->parent_slot, block->mblks_rem ));
2264 0 : return FD_SCHED_DEAD_REASON_ENTRY_AFTER_BLOCK_FOOTER;
2265 0 : }
2266 15 : return FD_SCHED_DEAD_REASON_NONE;
2267 15 : }
2268 :
2269 : static int
2270 6 : ag_on_final( fd_sched_block_t * block ) {
2271 6 : if( FD_UNLIKELY( !block->footer_seen ) ) {
2272 3 : FD_LOG_INFO(( "bad block: MISSING_BLOCK_FOOTER, slot %lu, parent slot %lu", block->slot, block->parent_slot ));
2273 3 : return FD_SCHED_DEAD_REASON_MISSING_BLOCK_FOOTER;
2274 3 : }
2275 3 : if( FD_UNLIKELY( !block->alpentick_seen ) ) {
2276 0 : FD_LOG_INFO(( "bad block: INVALID_ALPENTICK_POSITION, slot %lu, parent slot %lu, block ended after footer without alpentick", block->slot, block->parent_slot ));
2277 0 : return FD_SCHED_DEAD_REASON_INVALID_ALPENTICK_POSITION;
2278 0 : }
2279 3 : return FD_SCHED_DEAD_REASON_NONE;
2280 3 : }
2281 :
2282 : /* Agave invokes verify_ticks() anywhere between once per slot and once
2283 : per entry batch, before transactions are parsed or dispatched for
2284 : execution. We can't do quite the same thing due to out-of-order
2285 : scheduling and the fact that we allow parsing to run well ahead of
2286 : block boundaries. Out-of-order scheduling is good, so is overlapping
2287 : parsing with execution. The easiest thing for us would be to just
2288 : delay verify_ticks() wholesale till the end of a slot, except that
2289 : this opens us up to bogus tick and hash counts, potentially causing
2290 : runaway consumption of compute cycles. Of all the checks that are
2291 : performed in verify_ticks(), two types are relevant to mitigating
2292 : this risk. One is constraining the number of ticks, and the other is
2293 : constraining the number of hashes per tick. So we implement these
2294 : checks here, and perform them on the fly as eagerly as possible.
2295 :
2296 : Returns FD_SCHED_DEAD_REASON_NONE (0) on success, else the
2297 : FD_SCHED_DEAD_REASON_* the block should be ruled invalid for. Does
2298 : not modify the block. */
2299 : static int
2300 252 : verify_ticks_eager( fd_sched_block_t * block ) {
2301 252 : FD_TEST( block->hashes_per_tick!=ULONG_MAX ); /* PoH params initialized. */
2302 :
2303 252 : if( FD_UNLIKELY( block->mblk_tick_cnt+block->tick_height>block->max_tick_height ) ) {
2304 3 : FD_LOG_INFO(( "bad block: TOO_MANY_TICKS, slot %lu, parent slot %lu, tick_cnt %u, tick_height %lu, max_tick_height %lu", block->slot, block->parent_slot, block->mblk_tick_cnt, block->tick_height, block->max_tick_height ));
2305 3 : return FD_SCHED_DEAD_REASON_TOO_MANY_TICKS;
2306 3 : }
2307 249 : if( FD_UNLIKELY( block->hashes_per_tick>1UL && block->zero_hash_tick ) ) {
2308 0 : FD_LOG_INFO(( "bad block: ZERO_HASH_TICK, slot %lu, parent slot %lu, has at least one zero hash tick", block->slot, block->parent_slot ));
2309 0 : return FD_SCHED_DEAD_REASON_ZERO_HASH_TICK;
2310 0 : }
2311 249 : if( FD_UNLIKELY( block->hashes_per_tick>1UL && block->mblk_tick_cnt && (block->hashes_per_tick!=block->tick_hashcnt_wmk||block->inconsistent_hashes_per_tick) ) ) {
2312 3 : FD_LOG_INFO(( "bad block: WRONG_HASHES_PER_TICK, slot %lu, parent slot %lu, expected %lu, got %lu", block->slot, block->parent_slot, block->hashes_per_tick, block->tick_hashcnt_wmk ));
2313 3 : return FD_SCHED_DEAD_REASON_WRONG_HASHES_PER_TICK;
2314 3 : }
2315 246 : if( FD_UNLIKELY( block->hashes_per_tick>1UL && block->curr_tick_hashcnt>block->hashes_per_tick ) ) { /* >1 to ignore low power hashing or no hashing cases */
2316 : /* We couldn't really check this at parse time because we may not
2317 : have the expected hashes per tick value yet. We couldn't delay
2318 : this till after all PoH hashing is done, because this would be a
2319 : DoS vector. This can't be merged with the above check, because a
2320 : malformed block might not end with a tick. As in, a block might
2321 : end with a non-tick microblock with a high hashcnt. Note that
2322 : checking the hashcnt between ticks transitively places an upper
2323 : bound on the hashcnt of individual microblocks, thus mitigating
2324 : the DoS vector. */
2325 0 : FD_LOG_INFO(( "bad block: TICK_HASHES_OVERFLOW, slot %lu, parent slot %lu, observed cumulative tick_hashcnt %lu, expected %lu", block->slot, block->parent_slot, block->curr_tick_hashcnt, block->hashes_per_tick ));
2326 0 : return FD_SCHED_DEAD_REASON_TICK_HASHES_OVERFLOW;
2327 0 : }
2328 :
2329 246 : return FD_SCHED_DEAD_REASON_NONE;
2330 246 : }
2331 :
2332 : /* https://github.com/anza-xyz/agave/blob/v3.0.6/ledger/src/blockstore_processor.rs#L1057
2333 :
2334 : The only check we don't do here is TRAILING_ENTRY, which can be done
2335 : independently when we parse the final FEC set of a block.
2336 :
2337 : Returns FD_SCHED_DEAD_REASON_NONE (0) on success, else the
2338 : FD_SCHED_DEAD_REASON_* the block should be ruled invalid for. Does
2339 : not modify the block. */
2340 : static int
2341 27 : verify_ticks_final( fd_sched_block_t * block ) {
2342 27 : FD_TEST( block->fec_eos );
2343 :
2344 27 : if( FD_UNLIKELY( block->mblk_tick_cnt+block->tick_height<block->max_tick_height ) ) {
2345 3 : FD_LOG_INFO(( "bad block: TOO_FEW_TICKS, slot %lu, parent slot %lu, tick_cnt %u, tick_height %lu, max_tick_height %lu", block->slot, block->parent_slot, block->mblk_tick_cnt, block->tick_height, block->max_tick_height ));
2346 3 : return FD_SCHED_DEAD_REASON_TOO_FEW_TICKS;
2347 3 : }
2348 :
2349 24 : return verify_ticks_eager( block );
2350 27 : }
2351 :
2352 : int
2353 : fd_sched_block_verify_ticks( fd_sched_t * sched,
2354 : ulong bank_idx,
2355 : ulong tick_height,
2356 : ulong max_tick_height,
2357 0 : ulong hashes_per_tick ) {
2358 0 : FD_TEST( sched->canary==FD_SCHED_MAGIC );
2359 0 : FD_TEST( bank_idx<sched->block_cnt_max );
2360 0 : FD_TEST( max_tick_height>tick_height );
2361 0 : fd_sched_block_t * block = block_pool_ele( sched, bank_idx );
2362 : /* Set the tick window directly; skip fd_sched_set_poh_params
2363 : PoH fixup, unneeded here and unsafe to repeat per FEC set. */
2364 0 : block->tick_height = tick_height;
2365 0 : block->max_tick_height = max_tick_height;
2366 0 : block->hashes_per_tick = hashes_per_tick;
2367 : /* fec_eos => slot fully ingested, so the TOO_FEW check is meaningful
2368 : too. */
2369 0 : return block->fec_eos ? verify_ticks_final( block ) : verify_ticks_eager( block );
2370 0 : }
2371 :
2372 288 : #define CHECK( cond ) do { \
2373 288 : if( FD_UNLIKELY( !(cond) ) ) { \
2374 51 : return FD_SCHED_DEAD_REASON_NONE; \
2375 51 : } \
2376 288 : } while( 0 )
2377 :
2378 : /* CHECK that it is safe to read at least n more bytes. */
2379 288 : #define CHECK_LEFT( n ) CHECK( (n)<=(block->fec_buf_sz-block->fec_buf_soff) )
2380 :
2381 : /* Consume as much as possible from the buffer. By the end of this
2382 : function, there could be residual data left over in the buffer. That
2383 : residual has to be either a partially received microblock header or a
2384 : transaction that straddles a FEC set boundary. These bytes are kept
2385 : and will be concatenated with the next FEC set. This residual is
2386 : bounded.
2387 :
2388 : Trailing bytes within a batch are dropped immediately. These
2389 : trailing bytes can span arbitrarily many FEC sets. */
2390 : FD_WARN_UNUSED static int
2391 177 : fd_sched_parse( fd_sched_t * sched, fd_sched_block_t * block, fd_sched_alut_ctx_t * alut_ctx ) {
2392 381 : while( 1 ) {
2393 393 : while( block->txns_rem>0UL ) {
2394 24 : int err = fd_sched_parse_txn( sched, block, alut_ctx );
2395 24 : if( FD_UNLIKELY( -1==err ) ) return FD_SCHED_DEAD_REASON_NONE;
2396 12 : else if( FD_UNLIKELY( err ) ) return err;
2397 24 : }
2398 :
2399 369 : if( block->txns_rem==0UL && block->mblks_rem>0UL ) {
2400 123 : if( FD_UNLIKELY( block->mblk_cnt>=sched->max_mblk_per_slot ) ) {
2401 : /* Microblock count is enforced as invariant
2402 : mblk_cnt+mblks_rem<=max_mblk_per_slot
2403 : when we read the declared count in a batch header. So we
2404 : shouldn't get here. */
2405 0 : sched->print_buf_sz = 0UL;
2406 0 : print_all( sched, block );
2407 0 : FD_LOG_NOTICE(( "%s", sched->print_buf ));
2408 0 : FD_LOG_CRIT(( "invariant violation: slot %lu, parent slot %lu, mblks_rem %lu, mblk_cnt %u (%u ticks) >= %lu", block->slot, block->parent_slot, block->mblks_rem, block->mblk_cnt, block->mblk_tick_cnt, sched->max_mblk_per_slot ));
2409 0 : }
2410 :
2411 123 : CHECK_LEFT( sizeof(fd_microblock_hdr_t) );
2412 117 : fd_microblock_hdr_t * hdr = (fd_microblock_hdr_t *)fd_type_pun( block->fec_buf+block->fec_buf_soff );
2413 117 : block->fec_buf_soff += (uint)sizeof(fd_microblock_hdr_t);
2414 :
2415 117 : if( FD_UNLIKELY( hdr->txn_cnt>fd_ulong_sat_sub( sched->max_txn_per_slot, block->txn_parsed_cnt ) ) ) {
2416 3 : FD_LOG_INFO(( "bad block: TOO_MANY_TXNS, microblock header declared too many transactions, slot %lu, parent slot %lu, txn_parsed_cnt %u, hdr->txn_cnt %lu", block->slot, block->parent_slot, block->txn_parsed_cnt, hdr->txn_cnt ));
2417 3 : return FD_SCHED_DEAD_REASON_TOO_MANY_TXNS;
2418 3 : }
2419 114 : if( FD_UNLIKELY( hdr->hash_cnt>fd_ulong_sat_sub( FD_RUNTIME_MAX_HASHES_PER_TICK, block->curr_tick_hashcnt ) ) ) {
2420 0 : FD_LOG_INFO(( "bad block: TICK_HASHES_OVERFLOW_INGEST, slot %lu, parent slot %lu, curr_tick_hashcnt %lu, hdr->hash_cnt %lu", block->slot, block->parent_slot, block->curr_tick_hashcnt, hdr->hash_cnt ));
2421 0 : return FD_SCHED_DEAD_REASON_TICK_HASHES_OVERFLOW_INGEST;
2422 0 : }
2423 114 : if( FD_UNLIKELY( sched->is_alpenglow && hdr->hash_cnt!=1UL ) ) {
2424 6 : FD_LOG_INFO(( "bad block: ALPENGLOW_HASH_CNT, slot %lu, parent slot %lu, mblk idx %u declared hash_cnt %lu", block->slot, block->parent_slot, block->mblk_cnt, hdr->hash_cnt ));
2425 6 : return FD_SCHED_DEAD_REASON_ALPENGLOW_HASH_CNT;
2426 6 : }
2427 108 : if( FD_UNLIKELY( sched->is_alpenglow && block->footer_seen ) ) {
2428 6 : if( FD_UNLIKELY( hdr->txn_cnt ) ) {
2429 0 : FD_LOG_INFO(( "bad block: ENTRY_AFTER_BLOCK_FOOTER, slot %lu, parent slot %lu, transaction microblock after footer", block->slot, block->parent_slot ));
2430 0 : return FD_SCHED_DEAD_REASON_ENTRY_AFTER_BLOCK_FOOTER;
2431 0 : }
2432 6 : block->alpentick_seen = 1;
2433 6 : }
2434 :
2435 108 : block->mblks_rem--;
2436 108 : block->txns_rem = hdr->txn_cnt;
2437 :
2438 : /* One might think that every microblock needs to have at least
2439 : one hash, otherwise the block should be considered invalid. A
2440 : vanilla validator certainly produces microblocks that conform
2441 : to this. But a modded validator could in theory produce
2442 : zero-hash microblocks. Agave's replay stage will happily take
2443 : those microblocks. The Agave implementation-defined way of
2444 : doing PoH verify is as follows:
2445 :
2446 : For a tick microblock, do the same number of hashes as
2447 : specified by the microblock. Zero hashes are not allowed.
2448 :
2449 : For a transaction microblock, if the number of hashes specified
2450 : by the microblock is <= 1, then do zero pure hashes, and simply
2451 : do a mixin/record. Otherwise, do (number of hashes-1) amount
2452 : of pure hashing, and then do a mixin. However, note that for
2453 : the purposes of tick_verify, the number of hashes specified by
2454 : the microblock is taken verbatim.
2455 :
2456 : An additional constraint is that Agave expects non-tick
2457 : microblocks to leave the cumulative tick hash count at least
2458 : one away from hashes_per_tick at the end of a batch:
2459 : https://github.com/anza-xyz/agave/blob/v4.0.0-rc.0/entry/src/entry.rs#L672
2460 :
2461 : Observe that this is not a net new constraint. Since ticks are
2462 : not allowed to have zero hashes, and ticks have to end at
2463 : exactly hashes_per_tick, this check is redundant.
2464 :
2465 :
2466 : Some additional references to Agave:
2467 :
2468 : On the consumer side, non-tick microblocks can have a zero hash
2469 : count, and the mixin will happen anyways:
2470 : https://github.com/anza-xyz/agave/blob/v4.0.0-rc.0/entry/src/entry.rs#L326
2471 : https://github.com/anza-xyz/agave/blob/v4.0.0-rc.0/entry/src/entry.rs#L542
2472 :
2473 : Ticks cannot have a zero hash count:
2474 : https://github.com/anza-xyz/agave/blob/v4.1.1/entry/src/entry.rs#L684
2475 :
2476 : On the producer side, Agave reserves at least one hash for the
2477 : tick, so an Agave produced tick would satisfy the verifier:
2478 : https://github.com/anza-xyz/agave/blob/v4.0.0-rc.0/entry/src/poh.rs#L78
2479 : https://github.com/anza-xyz/agave/blob/v4.0.0-rc.0/entry/src/poh.rs#L101 */
2480 108 : block->curr_tick_hashcnt = fd_ulong_sat_add( hdr->hash_cnt, block->curr_tick_hashcnt ); /* For tick_verify, take the number of hashes verbatim. */
2481 108 : sched->metrics->mblk_parsed_cnt++;
2482 108 : if( FD_UNLIKELY( !hdr->txn_cnt ) ) {
2483 : /* This is a tick microblock. */
2484 96 : if( FD_UNLIKELY( block->mblk_tick_cnt && block->tick_hashcnt_wmk!=block->curr_tick_hashcnt ) ) {
2485 3 : block->inconsistent_hashes_per_tick = 1;
2486 3 : if( FD_LIKELY( block->hashes_per_tick!=ULONG_MAX && block->hashes_per_tick>1UL ) ) {
2487 : /* >1 to ignore low power hashing or hashing disabled */
2488 0 : FD_LOG_INFO(( "bad block: INCONSISTENT_TICK_HASHES, slot %lu, parent slot %lu, tick idx %u, tick_hashcnt_wmk %lu, curr hashcnt %lu, hashes_per_tick %lu", block->slot, block->parent_slot, block->mblk_tick_cnt, block->tick_hashcnt_wmk, block->curr_tick_hashcnt, block->hashes_per_tick ));
2489 0 : return FD_SCHED_DEAD_REASON_INCONSISTENT_TICK_HASHES;
2490 0 : }
2491 3 : }
2492 96 : if( FD_UNLIKELY( !hdr->hash_cnt ) ) {
2493 0 : block->zero_hash_tick = 1;
2494 0 : if( FD_LIKELY( block->hashes_per_tick!=ULONG_MAX && block->hashes_per_tick>1UL ) ) {
2495 0 : FD_LOG_INFO(( "bad block: ZERO_HASH_TICK_INGEST, slot %lu, parent slot %lu, tick idx %u has zero hashes", block->slot, block->parent_slot, block->mblk_tick_cnt ));
2496 0 : return FD_SCHED_DEAD_REASON_ZERO_HASH_TICK_INGEST;
2497 0 : }
2498 0 : }
2499 96 : block->tick_hashcnt_wmk = fd_ulong_max( block->curr_tick_hashcnt, block->tick_hashcnt_wmk );
2500 96 : block->curr_tick_hashcnt = 0UL;
2501 96 : block->mblk_tick_cnt++;
2502 96 : }
2503 :
2504 108 : FD_TEST( sched->mblk_pool_free_cnt ); /* can_ingest should have guaranteed sufficient free capacity. */
2505 108 : uint mblk_idx = sched->mblk_pool_free_head;
2506 108 : sched->mblk_pool_free_head = sched->mblk_pool[ mblk_idx ].next;
2507 108 : sched->mblk_pool_free_cnt--;
2508 :
2509 108 : fd_sched_mblk_t * mblk = sched->mblk_pool+mblk_idx;
2510 108 : mblk->start_txn_idx = block->txn_parsed_cnt;
2511 108 : mblk->end_txn_idx = mblk->start_txn_idx+hdr->txn_cnt;
2512 108 : mblk->curr_txn_idx = mblk->start_txn_idx;
2513 108 : mblk->hashcnt = fd_ulong_sat_sub( hdr->hash_cnt, fd_ulong_if( !hdr->txn_cnt, 0UL, 1UL ) ); /* For pure hashing, implement saturating sub for non-tick microblocks. */
2514 108 : mblk->curr_hashcnt = 0UL;
2515 108 : mblk->curr_sig_cnt = 0U;
2516 108 : mblk->mixin_txn_idx = 0U;
2517 108 : mblk->is_tick = !hdr->txn_cnt;
2518 108 : memcpy( mblk->end_hash, hdr->hash, sizeof(fd_hash_t) );
2519 108 : memcpy( mblk->curr_hash, block->poh_hash, sizeof(fd_hash_t) );
2520 108 : block->parse_mblk_idx = mblk_idx;
2521 :
2522 : /* Update block tracking. */
2523 108 : block->hashcnt += mblk->hashcnt+fd_ulong_if( !hdr->txn_cnt, 0UL, 1UL );
2524 108 : memcpy( block->poh_hash, hdr->hash, sizeof(fd_hash_t) );
2525 108 : block->last_mblk_is_tick = mblk->is_tick;
2526 108 : block->mblk_cnt++;
2527 :
2528 : #if FD_SCHED_SKIP_POH
2529 : block->poh_hashing_done_cnt++;
2530 : block->poh_hash_cmp_done_cnt++;
2531 : free_mblk( sched, block, mblk_idx );
2532 : #else
2533 108 : mblk_slist_idx_push_tail( block->mblks_unhashed, mblk_idx, sched->mblk_pool );
2534 108 : block->mblk_unhashed_cnt++;
2535 108 : #endif
2536 108 : continue;
2537 108 : }
2538 246 : if( block->txns_rem==0UL && block->mblks_rem==0UL && block->fec_sob ) {
2539 165 : CHECK_LEFT( sizeof(ulong) );
2540 120 : FD_TEST( block->fec_buf_soff==0U );
2541 120 : block->mblks_rem = FD_LOAD( ulong, block->fec_buf );
2542 120 : block->fec_buf_soff += (uint)sizeof(ulong);
2543 :
2544 120 : if( FD_UNLIKELY( block->mblks_rem>fd_ulong_sat_sub( sched->max_mblk_per_slot, block->mblk_cnt ) ) ) {
2545 3 : FD_LOG_INFO(( "bad block: TOO_MANY_MICROBLOCKS, slot %lu, parent slot %lu, mblk_cnt %u (%u ticks) + hdr->mblk_cnt %lu >= %lu", block->slot, block->parent_slot, block->mblk_cnt, block->mblk_tick_cnt, block->mblks_rem, sched->max_mblk_per_slot ));
2546 3 : return FD_SCHED_DEAD_REASON_TOO_MANY_MICROBLOCKS;
2547 3 : }
2548 :
2549 117 : block->fec_sob = 0;
2550 :
2551 117 : if( FD_UNLIKELY( !block->mblks_rem && sched->is_alpenglow ) ) {
2552 : /* A zero-microblock batch is a block marker */
2553 57 : fd_block_marker_t marker[1];
2554 57 : int err = fd_block_marker_de( marker, block->fec_buf, (ulong)block->fec_buf_sz );
2555 57 : if( FD_UNLIKELY( err ) ) {
2556 0 : FD_LOG_INFO(( "bad block: slot %lu, unable to parse block marker (err %d)", block->slot, err ));
2557 0 : return FD_SCHED_DEAD_REASON_BAD_BLOCK_MARKER;
2558 0 : }
2559 57 : int dead_reason = ag_on_marker( sched, block, marker );
2560 57 : if( FD_UNLIKELY( dead_reason!=FD_SCHED_DEAD_REASON_NONE ) ) return dead_reason;
2561 60 : } else if( FD_UNLIKELY( block->mblks_rem && sched->is_alpenglow ) ) {
2562 21 : int dead_reason = ag_on_entry_batch( block );
2563 21 : if( FD_UNLIKELY( dead_reason!=FD_SCHED_DEAD_REASON_NONE ) ) return dead_reason;
2564 39 : } else if( FD_UNLIKELY( !block->mblks_rem && !sched->is_alpenglow ) ) {
2565 0 : FD_LOG_INFO(( "bad block: ZERO_MICROBLOCKS, slot %lu, parent slot %lu, mblk_cnt %u (%u ticks)", block->slot, block->parent_slot, block->mblk_cnt, block->mblk_tick_cnt ));
2566 0 : return FD_SCHED_DEAD_REASON_ZERO_MICROBLOCKS;
2567 0 : }
2568 96 : continue;
2569 117 : }
2570 81 : if( block->txns_rem==0UL && block->mblks_rem==0UL ) {
2571 81 : break;
2572 81 : }
2573 81 : }
2574 81 : if( !block->fec_sob && block->txns_rem==0UL && block->mblks_rem==0UL ) {
2575 : /* All microblocks announced by the current batch header have been
2576 : parsed out. Anything still in the buffer must be trailing bytes.
2577 : Drop them now because trailing bytes can span many FEC sets and
2578 : accumulating them would overflow the parse buffer. Any followup
2579 : FEC sets within the same batch will simply be discarded
2580 : wholesale. */
2581 81 : sched->metrics->bytes_ingested_unparsed_cnt += block->fec_buf_sz-block->fec_buf_soff;
2582 81 : block->fec_buf_boff += block->fec_buf_sz;
2583 81 : block->fec_buf_soff = 0U;
2584 81 : block->fec_buf_sz = 0U;
2585 81 : }
2586 81 : if( block->fec_eob ) {
2587 81 : block->fec_sob = 1;
2588 81 : block->fec_eob = 0;
2589 81 : }
2590 81 : return FD_SCHED_DEAD_REASON_NONE;
2591 177 : }
2592 :
2593 : static inline fd_acct_addr_t const *
2594 0 : get_acct( fd_txn_t const * txn, fd_acct_addr_t const * imms, fd_acct_addr_t const * alts, ushort idx ) {
2595 0 : if( FD_LIKELY( idx<txn->acct_addr_cnt ) ) return imms+idx;
2596 0 : if( FD_UNLIKELY( !alts ) ) return NULL;
2597 0 : return alts+(idx-txn->acct_addr_cnt);
2598 0 : }
2599 :
2600 : /* Returns 1 if the transaction write locks any account in the block's
2601 : poison set. */
2602 : static int
2603 12 : block_poison_hit( fd_sched_block_t const * block, fd_txn_t const * txn, fd_acct_addr_t const * imms, fd_acct_addr_t const * alts ) {
2604 12 : if( FD_LIKELY( !block->poison_cnt ) ) return 0;
2605 :
2606 0 : for( fd_txn_acct_iter_t iter = fd_txn_acct_iter_init( txn, FD_TXN_ACCT_CAT_WRITABLE ); iter!=fd_txn_acct_iter_end(); iter=fd_txn_acct_iter_next( iter ) ) {
2607 0 : fd_acct_addr_t const * acct = get_acct( txn, imms, alts, (ushort)fd_txn_acct_iter_idx( iter ) );
2608 : /* Shouldn't really happen, since ALT-serializing transactions don't
2609 : enter this function, so all account pubkeys are available. */
2610 0 : if( FD_UNLIKELY( !acct ) ) return 1;
2611 0 : for( uint j=0U; j<block->poison_cnt; j++ ) {
2612 0 : if( FD_UNLIKELY( !memcmp( block->poison[ j ].b, acct->b, 32UL ) ) ) return 1;
2613 0 : }
2614 0 : }
2615 :
2616 0 : return 0;
2617 0 : }
2618 :
2619 : /* Returns 0 on success, 1 if the poison set overflowed. */
2620 : static int
2621 0 : block_poison_insert( fd_sched_t * sched, fd_sched_block_t * block, fd_acct_addr_t const * acct ) {
2622 0 : for( uint j=0U; j<block->poison_cnt; j++ ) {
2623 0 : if( FD_UNLIKELY( !memcmp( block->poison[ j ].b, acct->b, 32UL ) ) ) return 0; /* Dedup. */
2624 0 : }
2625 :
2626 0 : if( FD_UNLIKELY( block->poison_cnt>=FD_SCHED_POISON_MAX_ACCT_PER_SLOT ) ) {
2627 0 : block->poison_serialize = 1;
2628 0 : sched->metrics->poison_latch_overflow_cnt++;
2629 0 : return 1;
2630 0 : }
2631 :
2632 0 : block->poison[ block->poison_cnt++ ] = *acct;
2633 0 : sched->metrics->poison_cnt_wmk = fd_uint_max( sched->metrics->poison_cnt_wmk, block->poison_cnt );
2634 0 : return 0;
2635 0 : }
2636 :
2637 : /* Adds relevant accounts to the poison set. This function is
2638 : conservative and stateless. Account data is not necessarily
2639 : available at insertion time, so we cannot tell which writable account
2640 : is the programdata PDA. So the rule is simply: if loader v3 appears
2641 : anywhere in the transaction account list, poison every writable
2642 : account of the transaction.
2643 :
2644 : That is sound because instruction level writability can never exceed
2645 : transaction level writability thanks to CPI rejecting writability
2646 : escalations. So any account a loader v3 instruction could modify, at
2647 : the top-level or in a CPI, must be transaction level writable.
2648 : Additionally, the loader being in the account keys is necessary for
2649 : any invocation of it. */
2650 : static void
2651 : block_poison_add( fd_sched_t * sched,
2652 : fd_sched_block_t * block,
2653 : fd_txn_t const * txn,
2654 : fd_acct_addr_t const * imms,
2655 : fd_acct_addr_t const * alts,
2656 12 : ulong alt_cnt ) {
2657 : /* The poison set is never consulted again once it enters a
2658 : serializing regime, so there is no point in adding anything to it.
2659 : Returning here also keeps the serializing counters at one increment
2660 : per block. */
2661 12 : if( FD_UNLIKELY( block->poison_serialize ) ) return;
2662 :
2663 : /* If we can't expand an ALT, we'd have to conservatively assume
2664 : there's loader v3 listed in it. And if there also happens to be a
2665 : writable account in an unresolvable ALT, we can't add it and we no
2666 : longer maintain poison list integrity, so we conservatively
2667 : serialize the rest of the block. */
2668 12 : int alt_unresolvable = alt_cnt && !alts;
2669 12 : int loader_present = 0;
2670 36 : for( ushort i=0; i<txn->acct_addr_cnt; i++ ) {
2671 24 : if( FD_UNLIKELY( !memcmp( imms[ i ].b, fd_solana_bpf_loader_upgradeable_program_id.key, 32UL ) ) ) {
2672 0 : loader_present = 1;
2673 0 : break;
2674 0 : }
2675 24 : }
2676 12 : if( !loader_present && !alt_unresolvable ) {
2677 12 : for( ulong i=0UL; i<alt_cnt; i++ ) {
2678 0 : if( FD_UNLIKELY( !memcmp( alts[ i ].b, fd_solana_bpf_loader_upgradeable_program_id.key, 32UL ) ) ) {
2679 0 : loader_present = 1;
2680 0 : break;
2681 0 : }
2682 0 : }
2683 12 : }
2684 12 : if( FD_LIKELY( !loader_present && !alt_unresolvable ) ) return;
2685 :
2686 0 : for( fd_txn_acct_iter_t iter = fd_txn_acct_iter_init( txn, FD_TXN_ACCT_CAT_WRITABLE ); iter!=fd_txn_acct_iter_end(); iter=fd_txn_acct_iter_next( iter ) ) {
2687 0 : fd_acct_addr_t const * acct = get_acct( txn, imms, alts, (ushort)fd_txn_acct_iter_idx( iter ) );
2688 0 : if( FD_UNLIKELY( !acct ) ) {
2689 0 : block->poison_serialize = 1;
2690 0 : sched->metrics->poison_latch_alt_cnt++;
2691 0 : break;
2692 0 : }
2693 0 : if( FD_UNLIKELY( block_poison_insert( sched, block, acct ) ) ) break;
2694 0 : }
2695 0 : }
2696 :
2697 : FD_WARN_UNUSED static int
2698 24 : fd_sched_parse_txn( fd_sched_t * sched, fd_sched_block_t * block, fd_sched_alut_ctx_t * alut_ctx ) {
2699 24 : fd_txn_t * txn = fd_type_pun( block->txn );
2700 :
2701 24 : uchar * payload = block->fec_buf+block->fec_buf_soff;
2702 24 : ulong remaining = block->fec_buf_sz-block->fec_buf_soff;
2703 24 : ulong pay_sz = 0UL;
2704 24 : ulong txn_sz = fd_txn_parse_core( payload,
2705 24 : remaining,
2706 24 : txn,
2707 24 : NULL,
2708 24 : &pay_sz );
2709 :
2710 : /* Can't parse out a full transaction yet, EAGAIN. */
2711 24 : if( FD_UNLIKELY( !pay_sz || !txn_sz ) ) return -1;
2712 :
2713 12 : if( FD_UNLIKELY( block->txn_parsed_cnt>=sched->max_txn_per_slot ) ) {
2714 : /* Transaction count is enforced as invariant
2715 : txn_parsed_cnt+txns_rem<=max_txn_per_slot
2716 : when we read the declared count in a microblock header. So we
2717 : shouldn't get here. */
2718 0 : sched->print_buf_sz = 0UL;
2719 0 : print_all( sched, block );
2720 0 : FD_LOG_NOTICE(( "%s", sched->print_buf ));
2721 0 : FD_LOG_CRIT(( "invariant violation: slot %lu, parent slot %lu, txn_parsed_cnt %u", block->slot, block->parent_slot, block->txn_parsed_cnt ));
2722 0 : }
2723 :
2724 12 : ulong imm_cnt = fd_txn_account_cnt( txn, FD_TXN_ACCT_CAT_IMM );
2725 12 : ulong alt_cnt = fd_txn_account_cnt( txn, FD_TXN_ACCT_CAT_ALT );
2726 :
2727 : /* Try to expand ALUTs. */
2728 12 : int serializing = 0;
2729 12 : if( alt_cnt>0UL ) {
2730 0 : if( FD_UNLIKELY( sched->bypass_alut_resolution ) ) {
2731 : /* test/fuzz: no accdb to query, so treat ALUT txns as serializing. */
2732 0 : serializing = 1;
2733 0 : } else {
2734 : /* Copy the slot hashes sysvar out and release the read BEFORE
2735 : resolving the ALTs. fd_runtime_load_txn_address_lookup_tables
2736 : issues its own fd_accdb_read_one per lookup table, and the accdb
2737 : acquire state is a single non-nestable flag — holding this read
2738 : open across that call would trip the IDLE assertion in
2739 : fd_accdb_acquire. The slot_hashes view aliases the record data,
2740 : so it must view the copy, not the released record. */
2741 0 : static uchar slot_hashes_buf[ FD_SYSVAR_SLOT_HASHES_BINCODE_SZ ];
2742 0 : ulong slot_hashes_sz = 0UL;
2743 0 : int have_slot_hashes = 0;
2744 0 : fd_acc_t ro = fd_accdb_read_one( alut_ctx->accdb, alut_ctx->fork_id, fd_sysvar_slot_hashes_id.uc );
2745 0 : if( FD_LIKELY( ro.lamports && ro.data_len<=sizeof(slot_hashes_buf) ) ) {
2746 0 : fd_memcpy( slot_hashes_buf, ro.data, ro.data_len );
2747 0 : slot_hashes_sz = ro.data_len;
2748 0 : have_slot_hashes = 1;
2749 0 : }
2750 0 : fd_accdb_unread_one( alut_ctx->accdb, &ro );
2751 :
2752 0 : fd_slot_hashes_t slot_hashes_view[1];
2753 0 : if( FD_LIKELY( have_slot_hashes &&
2754 0 : fd_sysvar_slot_hashes_view( slot_hashes_view, slot_hashes_buf, slot_hashes_sz ) ) ) {
2755 0 : serializing = !!fd_runtime_load_txn_address_lookup_tables( txn, payload, alut_ctx->accdb, alut_ctx->fork_id, alut_ctx->els, slot_hashes_view, sched->aluts );
2756 0 : sched->metrics->alut_success_cnt += (uint)!serializing;
2757 0 : } else {
2758 0 : serializing = 1;
2759 0 : }
2760 0 : }
2761 0 : }
2762 :
2763 : /* Capture alt_cnt before it's clamped below. Poisoning needs to
2764 : distinguish between "no ALT keys" from "ALT keys failed to
2765 : resolve". */
2766 12 : ulong poison_alt_cnt = alt_cnt;
2767 12 : fd_acct_addr_t const * poison_alts = (alt_cnt && !serializing) ? sched->aluts : NULL;
2768 :
2769 : /* Transactions should not have duplicate accounts.
2770 : https://github.com/anza-xyz/agave/blob/v3.1.11/ledger/src/blockstore_processor.rs#L778-L790 */
2771 12 : fd_acct_addr_t const * imms = fd_txn_get_acct_addrs( txn, payload );
2772 12 : fd_acct_addr_t * alts = (!alt_cnt||serializing) ? NULL : sched->aluts;
2773 12 : alt_cnt = alts ? alt_cnt : 0UL;
2774 12 : if( FD_UNLIKELY( fd_chkdup_check( sched->chkdup, imms, imm_cnt, alts, alt_cnt ) ) ) {
2775 0 : FD_LOG_INFO(( "bad block: DUPLICATE_ACCOUNT, slot %lu, parent slot %lu, txn_parsed_cnt %u", block->slot, block->parent_slot, block->txn_parsed_cnt ));
2776 0 : return FD_SCHED_DEAD_REASON_DUPLICATE_ACCOUNT;
2777 0 : }
2778 :
2779 : /* After any error return but before poisoning. */
2780 12 : sched->metrics->alut_serializing_cnt += (uint)serializing;
2781 :
2782 : /* At this point, we've decided whether the transaction is
2783 : ALT-serializing or not. If it didn't get serialized by ALT
2784 : expansion failure, check if it should be serialized by poisoning.
2785 : Add to the poison set after checking, so a poisoning transaction
2786 : doesn't get serialized against its own entries. Adding to the
2787 : poison set is unconditional. */
2788 12 : if( FD_UNLIKELY( !serializing && ( block->poison_serialize||block_poison_hit( block, txn, imms, poison_alts ) ) ) ) {
2789 0 : serializing = 1;
2790 0 : sched->metrics->txn_poisoned_cnt += block->poison_serialize ? 0U : 1U;
2791 0 : sched->metrics->txn_poison_serializing_cnt += block->poison_serialize ? 1U : 0U;
2792 0 : }
2793 12 : block_poison_add( sched, block, txn, imms, poison_alts, poison_alt_cnt );
2794 :
2795 12 : ulong bank_idx = (ulong)(block-sched->block_pool);
2796 12 : ulong txn_idx = fd_rdisp_add_txn( sched->rdisp, bank_idx, txn, payload, alts, serializing );
2797 12 : FD_TEST( txn_idx && txn_idx<sched->depth );
2798 :
2799 : /* This transaction either needs to be consumed by sigverify or PoH.
2800 : If either of the two are caught up, mark it for consumption.
2801 : Otherwise, link it to the tail of the chain. */
2802 :
2803 12 : ulong sigverify_dispatched_cnt = (ulong)block->txn_sigverify_done_cnt + (ulong)block->txn_sigverify_in_flight_cnt;
2804 12 : int sigverify_caught_up = sigverify_dispatched_cnt==block->txn_parsed_cnt;
2805 12 : #if !FD_SCHED_SKIP_POH
2806 12 : fd_sched_mblk_t * parse_mblk = sched->mblk_pool + block->parse_mblk_idx;
2807 12 : int poh_caught_up = parse_mblk->curr_txn_idx==block->txn_parsed_cnt;
2808 12 : #endif
2809 :
2810 12 : sched->txn_info_pool[ txn_idx ].next_idx = 0U;
2811 : /* Link to the previous transaction. */
2812 12 : if( FD_LIKELY( block->txn_idx_tail ) ) {
2813 0 : FD_TEST( block->txn_idx_tail<sched->depth );
2814 0 : sched->txn_info_pool[ block->txn_idx_tail ].next_idx = (uint)txn_idx;
2815 0 : }
2816 : /* If either consumer is caught up, update next pointer to the new
2817 : transaction. */
2818 12 : if( FD_LIKELY( sigverify_caught_up ) ) block->txn_sigverify_next_idx = (uint)txn_idx;
2819 12 : #if !FD_SCHED_SKIP_POH
2820 12 : if( FD_LIKELY( poh_caught_up ) ) parse_mblk->mixin_txn_idx = (uint)txn_idx;
2821 12 : #endif
2822 12 : block->txn_idx_tail = (uint)txn_idx;
2823 :
2824 12 : sched->metrics->txn_parsed_cnt++;
2825 12 : sched->txn_pool_free_cnt--;
2826 12 : fd_txn_p_t * txn_p = sched->txn_pool + txn_idx;
2827 12 : txn_p->payload_sz = (ushort)pay_sz;
2828 :
2829 12 : txn_p->start_shred_idx = (ushort)fd_uint_min( shred_split( sched, block, block->fec_buf_boff+block->fec_buf_soff ), USHORT_MAX ); /* monitoring-only ushorts; saturate under bench shred counts */
2830 12 : txn_p->start_shred_idx = fd_ushort_if( txn_p->start_shred_idx>0U, (ushort)(txn_p->start_shred_idx-1U), txn_p->start_shred_idx );
2831 12 : txn_p->end_shred_idx = (ushort)fd_uint_min( shred_split( sched, block, block->fec_buf_boff+block->fec_buf_soff+(uint)pay_sz ), USHORT_MAX );
2832 :
2833 12 : fd_memcpy( txn_p->payload, payload, pay_sz );
2834 12 : fd_memcpy( TXN(txn_p), txn, txn_sz );
2835 12 : txn_bitset_remove( sched->exec_done_set, txn_idx );
2836 12 : txn_bitset_remove( sched->sigverify_done_set, txn_idx );
2837 12 : txn_bitset_remove( sched->poh_mixin_done_set, txn_idx );
2838 12 : sched->txn_info_pool[ txn_idx ].flags = 0UL;
2839 12 : sched->txn_info_pool[ txn_idx ].received_ns = block->fec_completed_ns;
2840 12 : sched->txn_info_pool[ txn_idx ].txn_err = 0;
2841 12 : sched->txn_info_pool[ txn_idx ].is_simple_vote = 0;
2842 :
2843 12 : sched->txn_info_pool[ txn_idx ].tick_parsed = fd_tickcount();
2844 12 : sched->txn_info_pool[ txn_idx ].tick_sigverify_disp = LONG_MAX;
2845 12 : sched->txn_info_pool[ txn_idx ].tick_sigverify_done = LONG_MAX;
2846 12 : sched->txn_info_pool[ txn_idx ].tick_exec_disp = LONG_MAX;
2847 12 : sched->txn_info_pool[ txn_idx ].tick_exec_done = LONG_MAX;
2848 12 : sched->txn_info_pool[ txn_idx ].tick_load_start = LONG_MAX;
2849 12 : sched->txn_info_pool[ txn_idx ].tick_check_start = LONG_MAX;
2850 12 : sched->txn_info_pool[ txn_idx ].tick_exec_start = LONG_MAX;
2851 12 : sched->txn_info_pool[ txn_idx ].tick_commit_start = LONG_MAX;
2852 12 : sched->txn_info_pool[ txn_idx ].tick_commit_end = LONG_MAX;
2853 :
2854 12 : sched->txn_info_pool[ txn_idx ].slot = block->slot;
2855 12 : sched->txn_info_pool[ txn_idx ].bank_seq = ULONG_MAX;
2856 12 : sched->txn_info_pool[ txn_idx ].index_in_slot = block->txn_parsed_cnt;
2857 12 : sched->txn_info_pool[ txn_idx ].exec_tile_idx = ULONG_MAX;
2858 12 : sched->txn_info_pool[ txn_idx ].sigverify_exec_tile_idx = ULONG_MAX;
2859 12 : sched->txn_info_pool[ txn_idx ].compute_units_consumed = 0U;
2860 12 : sched->txn_info_pool[ txn_idx ].max_compute_units = ULONG_MAX;
2861 12 : sched->txn_info_pool[ txn_idx ].transaction_fee = 0UL;
2862 12 : sched->txn_info_pool[ txn_idx ].priority_fee = 0UL;
2863 12 : sched->txn_info_pool[ txn_idx ].tips = 0UL;
2864 12 : block->fec_buf_soff += (uint)pay_sz;
2865 12 : block->txn_parsed_cnt++;
2866 : #if FD_SCHED_SKIP_SIGVERIFY
2867 : txn_bitset_insert( sched->sigverify_done_set, txn_idx );
2868 : block->txn_sigverify_done_cnt++;
2869 : #endif
2870 : #if FD_SCHED_SKIP_POH
2871 : txn_bitset_insert( sched->poh_mixin_done_set, txn_idx );
2872 : #endif
2873 12 : block->txns_rem--;
2874 12 : return FD_SCHED_DEAD_REASON_NONE;
2875 12 : }
2876 :
2877 : #undef CHECK
2878 : #undef CHECK_LEFT
2879 :
2880 : static void
2881 9 : dispatch_sigverify( fd_sched_t * sched, fd_sched_block_t * block, ulong bank_idx, int exec_tile_idx, fd_sched_task_t * out ) {
2882 : /* Dispatch transactions for sigverify in parse order. */
2883 9 : uint txn_idx = block->txn_sigverify_next_idx;
2884 9 : FD_TEST( txn_idx && txn_idx<sched->depth );
2885 9 : out->task_type = FD_SCHED_TT_TXN_SIGVERIFY;
2886 9 : out->txn_sigverify->bank_idx = bank_idx;
2887 9 : out->txn_sigverify->txn_idx = txn_idx;
2888 9 : out->txn_sigverify->exec_idx = (ulong)exec_tile_idx;
2889 9 : sched->txn_info_pool[ out->txn_sigverify->txn_idx ].sigverify_exec_tile_idx = (ulong)exec_tile_idx;
2890 9 : sched->sigverify_ready_bitset[ 0 ] = fd_ulong_clear_bit( sched->sigverify_ready_bitset[ 0 ], exec_tile_idx );
2891 9 : sched->tile_to_bank_idx[ exec_tile_idx ] = bank_idx;
2892 9 : block->txn_sigverify_in_flight_cnt++;
2893 9 : block->txn_sigverify_next_idx = sched->txn_info_pool[ txn_idx ].next_idx;
2894 9 : if( FD_UNLIKELY( (~sched->txn_exec_ready_bitset[ 0 ])&(~sched->sigverify_ready_bitset[ 0 ])&(~sched->poh_ready_bitset[ 0 ])&fd_ulong_mask_lsb( (int)sched->exec_cnt ) ) ) FD_LOG_CRIT(( "invariant violation: txn_exec_ready_bitset 0x%lx sigverify_ready_bitset 0x%lx poh_ready_bitset 0x%lx", sched->txn_exec_ready_bitset[ 0 ], sched->sigverify_ready_bitset[ 0 ], sched->poh_ready_bitset[ 0 ] ));
2895 9 : }
2896 :
2897 : /* Retires a microblock whose PoH hashing has completed, and eagerly
2898 : does as much mixin as possible. Returns FD_SCHED_DEAD_REASON_NONE on
2899 : success, else the dead reason. */
2900 : static int
2901 96 : poh_retire_mblk( fd_sched_t * sched, fd_sched_block_t * block, uint mblk_idx ) {
2902 96 : fd_sched_mblk_t * mblk = sched->mblk_pool+mblk_idx;
2903 96 : FD_TEST( mblk->curr_hashcnt==mblk->hashcnt );
2904 96 : block->poh_hashing_done_cnt++;
2905 96 : sched->metrics->mblk_poh_hashed_cnt++;
2906 96 : if( FD_LIKELY( !mblk->is_tick ) ) {
2907 12 : mblk_slist_idx_push_tail( block->mblks_mixin_in_progress, mblk_idx, sched->mblk_pool );
2908 84 : } else {
2909 84 : block->poh_hash_cmp_done_cnt++;
2910 84 : sched->metrics->mblk_poh_done_cnt++;
2911 84 : free_mblk( sched, block, mblk_idx );
2912 84 : if( FD_UNLIKELY( memcmp( mblk->curr_hash, mblk->end_hash, sizeof(fd_hash_t) ) ) ) {
2913 0 : FD_BASE58_ENCODE_32_BYTES( mblk->curr_hash->hash, our_str );
2914 0 : FD_BASE58_ENCODE_32_BYTES( mblk->end_hash->hash, ref_str );
2915 0 : FD_LOG_INFO(( "bad block: TICK_HASH_MISMATCH, mblk %u, ours %s, claimed %s, hashcnt %lu, slot %lu, parent slot %lu", mblk_idx, our_str, ref_str, mblk->hashcnt, block->slot, block->parent_slot ));
2916 0 : return FD_SCHED_DEAD_REASON_TICK_HASH_MISMATCH;
2917 0 : }
2918 84 : }
2919 96 : int mixin_res;
2920 105 : while( (mixin_res=maybe_mixin( sched, block )) ) {
2921 9 : if( FD_UNLIKELY( mixin_res==-1 ) ) return FD_SCHED_DEAD_REASON_ENTRY_HASH_MISMATCH;
2922 9 : FD_TEST( mixin_res==1||mixin_res==2 );
2923 9 : }
2924 96 : return FD_SCHED_DEAD_REASON_NONE;
2925 96 : }
2926 :
2927 : /* Retires microblocks at the head of the unhashed queue that have
2928 : nothing left for PoH to hash. Returns FD_SCHED_DEAD_REASON_NONE on
2929 : success, else the dead reason. */
2930 : static int
2931 228 : poh_retire_ready_mblks( fd_sched_t * sched, fd_sched_block_t * block ) {
2932 228 : while( block->mblk_unhashed_cnt ) {
2933 84 : uint mblk_idx = (uint)mblk_slist_idx_peek_head( block->mblks_unhashed, sched->mblk_pool );
2934 84 : fd_sched_mblk_t * mblk = sched->mblk_pool+mblk_idx;
2935 84 : if( FD_LIKELY( mblk->curr_hashcnt!=mblk->hashcnt ) ) break;
2936 0 : mblk_slist_idx_pop_head( block->mblks_unhashed, sched->mblk_pool );
2937 0 : block->mblk_unhashed_cnt--;
2938 0 : int dead_reason = poh_retire_mblk( sched, block, mblk_idx );
2939 0 : if( FD_UNLIKELY( dead_reason!=FD_SCHED_DEAD_REASON_NONE ) ) return dead_reason;
2940 0 : }
2941 228 : return verify_ticks_eager( block );
2942 228 : }
2943 :
2944 : /* Assembles a PoH task for the given exec tile. Assumes there is a
2945 : PoH task available for dispatching. A microblock with nothing left
2946 : to hash is dispatched as a degenerate zero-hashcnt task, so that it
2947 : retires through fd_sched_task_done like any other PoH task. */
2948 : static void
2949 228 : dispatch_poh( fd_sched_t * sched, fd_sched_block_t * block, ulong bank_idx, int exec_tile_idx, ulong max_cnt, fd_sched_task_t * out ) {
2950 228 : FD_TEST( max_cnt>=1UL && max_cnt<=FD_SCHED_POH_PARA );
2951 : /* Every element of a batch advances by the same hashcnt, so the
2952 : batch hashcnt is the smallest remaining hashcnt of its elements.
2953 : Elements with more work left are re-queued on completion. */
2954 228 : fd_sched_poh_hash_t * poh = out->poh_hash;
2955 228 : ulong cnt = 0UL;
2956 228 : ulong hashcnt = ULONG_MAX;
2957 456 : while( cnt<max_cnt ) {
2958 228 : mblk_slist_t * list;
2959 228 : if( FD_LIKELY( !mblk_slist_is_empty( block->mblks_hashing_in_progress, sched->mblk_pool ) ) ) {
2960 : /* There's a PoH task in progress, just continue working on that. */
2961 132 : list = block->mblks_hashing_in_progress;
2962 132 : } else if( FD_LIKELY( block->mblk_unhashed_cnt ) ) {
2963 96 : list = block->mblks_unhashed;
2964 96 : } else {
2965 0 : break; /* Nothing more to batch. */
2966 0 : }
2967 228 : uint mblk_idx = (uint)mblk_slist_idx_pop_head( list, sched->mblk_pool );
2968 228 : fd_sched_mblk_t * mblk = sched->mblk_pool+mblk_idx;
2969 228 : ulong hashcnt_todo = mblk->hashcnt-mblk->curr_hashcnt;
2970 : /* A microblock with nothing left to hash can't share a batch with
2971 : one that has work left. The batch hashcnt would be zero, and the
2972 : latter would never make progress. */
2973 228 : if( FD_UNLIKELY( cnt && (!hashcnt_todo)!=(!hashcnt) ) ) {
2974 0 : mblk_slist_idx_push_head( list, mblk_idx, sched->mblk_pool );
2975 0 : break;
2976 0 : }
2977 228 : if( list==block->mblks_unhashed ) block->mblk_unhashed_cnt--;
2978 228 : hashcnt = fd_ulong_min( hashcnt, hashcnt_todo );
2979 228 : poh->mblk_idx[ cnt ] = mblk_idx;
2980 228 : memcpy( poh->hash+cnt, mblk->curr_hash, sizeof(fd_hash_t) );
2981 228 : cnt++;
2982 228 : block->poh_mblk_in_flight_cnt++;
2983 228 : }
2984 228 : FD_TEST( cnt ); /* poh_hashing_queued_cnt>0 implies at least one queued microblock. */
2985 :
2986 : /* See FD_SCHED_MAX_POH_HASHES_PER_TASK. */
2987 228 : hashcnt = fd_ulong_min( hashcnt, fd_ulong_if( cnt>=sched->poh_simd_min, sched->poh_simd_iters_max, FD_SCHED_MAX_POH_HASHES_PER_TASK ) );
2988 228 : out->task_type = FD_SCHED_TT_POH_HASH;
2989 228 : poh->bank_idx = bank_idx;
2990 228 : poh->exec_idx = (ulong)exec_tile_idx;
2991 228 : poh->cnt = cnt;
2992 228 : poh->hashcnt = hashcnt;
2993 228 : sched->poh_inflight[ exec_tile_idx ] = *poh;
2994 :
2995 228 : sched->poh_ready_bitset[ 0 ] = fd_ulong_clear_bit( sched->poh_ready_bitset[ 0 ], exec_tile_idx );
2996 228 : sched->tile_to_bank_idx[ exec_tile_idx ] = bank_idx;
2997 228 : block->poh_hashing_in_flight_cnt++;
2998 228 : if( FD_UNLIKELY( (~sched->txn_exec_ready_bitset[ 0 ])&(~sched->sigverify_ready_bitset[ 0 ])&(~sched->poh_ready_bitset[ 0 ])&fd_ulong_mask_lsb( (int)sched->exec_cnt ) ) ) FD_LOG_CRIT(( "invariant violation: txn_exec_ready_bitset 0x%lx sigverify_ready_bitset 0x%lx poh_ready_bitset 0x%lx", sched->txn_exec_ready_bitset[ 0 ], sched->sigverify_ready_bitset[ 0 ], sched->poh_ready_bitset[ 0 ] ));
2999 228 : }
3000 :
3001 : /* Does up to one transaction mixin. Returns 1 if one mixin was done, 2
3002 : if that mixin also completed a microblock, 0 if no transaction mixin
3003 : was available, -1 if there is a PoH verify error. */
3004 : FD_WARN_UNUSED static int
3005 249 : maybe_mixin( fd_sched_t * sched, fd_sched_block_t * block ) {
3006 249 : if( FD_UNLIKELY( mblk_slist_is_empty( block->mblks_mixin_in_progress, sched->mblk_pool ) ) ) return 0;
3007 18 : FD_TEST( block->poh_hashing_done_cnt-block->poh_hash_cmp_done_cnt>0 );
3008 :
3009 : /* The microblock we would like to do mixin on is at the head of the
3010 : queue. It may have had some mixin, it may have never had any
3011 : mixin. In the case of the former, we should continue to mixin the
3012 : same head microblock until it's done, lest the per-block bmtree
3013 : gets clobbered when we start a new one. */
3014 18 : ulong mblk_idx = mblk_slist_idx_pop_head( block->mblks_mixin_in_progress, sched->mblk_pool );
3015 18 : fd_sched_mblk_t * mblk = sched->mblk_pool+mblk_idx;
3016 :
3017 18 : if( FD_UNLIKELY( mblk->end_txn_idx>block->txn_parsed_cnt ) ) {
3018 : /* A partially parsed microblock is by definition at the end of the
3019 : FEC stream. If such a microblock is in progress, there should be
3020 : no other microblock in this block so far that hasn't been
3021 : dispatched, because microblocks are dispatched in parse order. */
3022 9 : if( FD_UNLIKELY( block->mblk_unhashed_cnt ) ) {
3023 0 : sched->print_buf_sz = 0UL;
3024 0 : print_all( sched, block );
3025 0 : FD_LOG_CRIT(( "invariant violation end_txn_idx %lu: %s", mblk->end_txn_idx, sched->print_buf ));
3026 0 : }
3027 :
3028 : /* If we've decided to start mixin on a partially parsed microblock,
3029 : there better be nothing else in-progress. Otherwise, they might
3030 : clobber the per-block bmtree for mixin. */
3031 9 : if( FD_UNLIKELY( mblk->curr_txn_idx!=mblk->start_txn_idx && (block->poh_mblk_in_flight_cnt||!mblk_slist_is_empty( block->mblks_hashing_in_progress, sched->mblk_pool )||!mblk_slist_is_empty( block->mblks_mixin_in_progress, sched->mblk_pool )) ) ) {
3032 0 : sched->print_buf_sz = 0UL;
3033 0 : print_all( sched, block );
3034 0 : FD_LOG_CRIT(( "invariant violation end_txn_idx %lu start_txn_idx %lu curr_txn_idx %lu: %s", mblk->end_txn_idx, mblk->start_txn_idx, mblk->curr_txn_idx, sched->print_buf ));
3035 0 : }
3036 9 : }
3037 :
3038 : /* Very rarely, we've finished hashing, but not all transactions in
3039 : the microblock have been parsed out. This can happen if we haven't
3040 : received all the FEC sets for this microblock. We can't yet fully
3041 : mixin the microblock. So we'll stick it back into the end of the
3042 : queue, and try to see if there's a fully parsed microblock.
3043 : Unless, there's truly nothing else to mixin. Then we would start
3044 : mixin with the partially parsed microblock. We do this because the
3045 : txn pool is meant to be an OOO scheduling window not tied to
3046 : max_live_slots sizing requirements, so there shouldn't be a way for
3047 : external input to tie up txn pool entries for longer than
3048 : necessary. */
3049 18 : if( FD_UNLIKELY( mblk->curr_txn_idx>=block->txn_parsed_cnt || /* Nothing more to mixin for this microblock. */
3050 18 : (mblk->end_txn_idx>block->txn_parsed_cnt && /* There is something to mixin, but the microblock isn't fully parsed yet ... */
3051 18 : mblk->curr_txn_idx==mblk->start_txn_idx && /* ... and we haven't started mixin on it yet ... */
3052 18 : (block->poh_mblk_in_flight_cnt || /* ... and another microblock is in-progress and might preempt this microblock and clobber the bmtree, so we shouldn't start the partial microblock just yet. Counting microblocks rather than tasks matters: a batched PoH task is retired one microblock at a time, and the ones not yet retired are off every list. */
3053 18 : !mblk_slist_is_empty( block->mblks_hashing_in_progress, sched->mblk_pool ) ||
3054 18 : !mblk_slist_is_empty( block->mblks_mixin_in_progress, sched->mblk_pool ))) ) ) {
3055 6 : mblk_slist_idx_push_tail( block->mblks_mixin_in_progress, mblk_idx, sched->mblk_pool );
3056 :
3057 : /* No other microblock in the mixin queue. */
3058 6 : if( FD_UNLIKELY( block->poh_hashing_done_cnt-block->poh_hash_cmp_done_cnt==1 ) ) return 0;
3059 :
3060 : /* At this point, there's at least one more microblock in the mixin
3061 : queue we could try. It's a predecessor (in parse order) that
3062 : finished hashing later than the partially parsed microblock at
3063 : the head of the mixin queue. */
3064 :
3065 : /* It should never clobber the bmtree for a microblock that has had some mixin done on it. */
3066 0 : if( FD_UNLIKELY( mblk->curr_txn_idx!=mblk->start_txn_idx ) ) {
3067 0 : sched->print_buf_sz = 0UL;
3068 0 : print_all( sched, block );
3069 0 : FD_LOG_CRIT(( "invariant violation curr_txn_idx %lu start_txn_idx %lu: %s", mblk->curr_txn_idx, mblk->start_txn_idx, sched->print_buf ));
3070 0 : }
3071 :
3072 0 : mblk_idx = mblk_slist_idx_pop_head( block->mblks_mixin_in_progress, sched->mblk_pool );
3073 0 : mblk = sched->mblk_pool+mblk_idx;
3074 :
3075 : /* It should be a fresh microblock for mixin. */
3076 0 : FD_TEST( mblk->curr_txn_idx==mblk->start_txn_idx );
3077 : /* Invariant: at any given point in time, there can be at most one
3078 : microblock that hasn't been fully parsed yet, due to the nature
3079 : of sequential parsing. So this microblock has to be fully
3080 : parsed. */
3081 0 : FD_TEST( mblk->end_txn_idx<=block->txn_parsed_cnt );
3082 0 : }
3083 :
3084 12 : FD_TEST( mblk->curr_txn_idx<mblk->end_txn_idx );
3085 :
3086 : /* Now mixin. */
3087 12 : if( FD_LIKELY( mblk->curr_txn_idx==mblk->start_txn_idx ) ) block->bmtree = fd_bmtree_commit_init( block->bmtree_mem, 32UL, 1UL, 0UL ); /* Optimize for single-transaction microblocks, which are the majority. */
3088 :
3089 12 : ulong txn_gidx = mblk->mixin_txn_idx;
3090 12 : uint next_txn_pool_idx = sched->txn_info_pool[ txn_gidx ].next_idx;
3091 12 : fd_txn_p_t * _txn = sched->txn_pool+txn_gidx;
3092 12 : fd_txn_t * txn = TXN(_txn);
3093 24 : for( ulong j=0; j<txn->signature_cnt; j++ ) {
3094 12 : fd_bmtree_node_t node[ 1 ];
3095 12 : fd_bmtree_hash_leaf( node, _txn->payload+txn->signature_off+FD_TXN_SIGNATURE_SZ*j, 64UL, 1UL );
3096 12 : fd_bmtree_commit_append( block->bmtree, node, 1UL );
3097 12 : mblk->curr_sig_cnt++;
3098 12 : }
3099 :
3100 : /* Release the txn_idx. */
3101 12 : txn_bitset_insert( sched->poh_mixin_done_set, txn_gidx );
3102 12 : sched->metrics->txn_mixin_done_cnt++;
3103 12 : if( txn_bitset_test( sched->exec_done_set, txn_gidx ) && txn_bitset_test( sched->sigverify_done_set, txn_gidx ) ) {
3104 0 : if( FD_UNLIKELY( block->txn_idx_tail==(uint)txn_gidx ) ) block->txn_idx_tail = 0U;
3105 0 : fd_rdisp_complete_txn( sched->rdisp, txn_gidx, 1 );
3106 0 : sched->txn_pool_free_cnt++;
3107 0 : block->txn_done_cnt++;
3108 0 : sched->metrics->txn_done_cnt++;
3109 0 : }
3110 :
3111 12 : mblk->curr_txn_idx++;
3112 12 : mblk->mixin_txn_idx = next_txn_pool_idx;
3113 12 : int rv = 2;
3114 12 : if( FD_LIKELY( mblk->curr_txn_idx==mblk->end_txn_idx ) ) {
3115 : /* Ready to compute the final hash for this microblock. */
3116 9 : block->poh_hash_cmp_done_cnt++;
3117 9 : sched->metrics->mblk_poh_done_cnt++;
3118 9 : uchar * root = fd_bmtree_commit_fini( block->bmtree );
3119 9 : uchar mixin_buf[ 64 ];
3120 9 : fd_memcpy( mixin_buf, mblk->curr_hash, 32UL );
3121 9 : fd_memcpy( mixin_buf+32UL, root, 32UL );
3122 9 : fd_sha256_hash( mixin_buf, 64UL, mblk->curr_hash );
3123 9 : free_mblk( sched, block, (uint)mblk_idx );
3124 : /* Bypass PoH verification for fuzzing/testing throughput. */
3125 9 : if( FD_UNLIKELY( !sched->bypass_poh_verify && memcmp( mblk->curr_hash, mblk->end_hash, sizeof(fd_hash_t) ) ) ) {
3126 0 : FD_BASE58_ENCODE_32_BYTES( mblk->curr_hash->hash, our_str );
3127 0 : FD_BASE58_ENCODE_32_BYTES( mblk->end_hash->hash, ref_str );
3128 0 : FD_LOG_INFO(( "bad block: poh hash mismatch on mblk %lu, ours %s, claimed %s, hashcnt %lu, txns [%lu,%lu), %u sigs, slot %lu, parent slot %lu", mblk_idx, our_str, ref_str, mblk->hashcnt, mblk->start_txn_idx, mblk->end_txn_idx, mblk->curr_sig_cnt, block->slot, block->parent_slot ));
3129 0 : return -1;
3130 0 : }
3131 9 : } else {
3132 : /* There are more transactions to mixin in this microblock. */
3133 3 : mblk_slist_idx_push_head( block->mblks_mixin_in_progress, mblk_idx, sched->mblk_pool );
3134 3 : rv = 1;
3135 3 : }
3136 :
3137 12 : return rv;
3138 12 : }
3139 :
3140 : static void
3141 204 : try_activate_block( fd_sched_t * sched ) {
3142 : /* Early return if there's already an active block. */
3143 204 : if( FD_LIKELY( sched->active_bank_idx!=ULONG_MAX ) ) return;
3144 :
3145 : /* See if there are any allocated staging lanes that we can activate
3146 : for scheduling ... */
3147 198 : ulong staged_bitset = sched->staged_bitset;
3148 267 : while( staged_bitset ) {
3149 162 : int lane_idx = fd_ulong_find_lsb( staged_bitset );
3150 162 : staged_bitset = fd_ulong_pop_lsb( staged_bitset );
3151 :
3152 162 : ulong head_idx = sched->staged_head_bank_idx[ lane_idx ];
3153 162 : fd_sched_block_t * head_block = block_pool_ele( sched, head_idx );
3154 162 : fd_sched_block_t * parent_block = block_pool_ele( sched, head_block->parent_idx );
3155 : //FIXME: restore these invariant checks when we have immediate demotion of dying blocks
3156 : //Today, dying blocks can remain staged if they have in-flight transactions.
3157 : // if( FD_UNLIKELY( parent_block->dying ) ) {
3158 : // /* Invariant: no child of a dying block should be staged. */
3159 : // FD_LOG_CRIT(( "invariant violation: staged_head_bank_idx %lu, slot %lu, parent slot %lu on lane %d has parent_block->dying set, slot %lu, parent slot %lu",
3160 : // head_idx, head_block->slot, head_block->parent_slot, lane_idx, parent_block->slot, parent_block->parent_slot ));
3161 : // }
3162 : // if( FD_UNLIKELY( head_block->dying ) ) {
3163 : // /* Invariant: no dying block should be staged. */
3164 : // FD_LOG_CRIT(( "invariant violation: staged_head_bank_idx %lu, slot %lu, prime %lu on lane %u has head_block->dying set",
3165 : // head_idx, (ulong)head_block->block_id.slot, (ulong)head_block->block_id.prime, lane_idx ));
3166 : // }
3167 162 : if( block_is_done( parent_block ) && block_is_activatable( head_block ) ) {
3168 : /* ... Yes, on this staging lane the parent block is done. So we
3169 : can activate the staged child. */
3170 93 : if( FD_UNLIKELY( head_idx!=sched->last_active_bank_idx ) ) { /* Unlikely because only possible under forking or on slot boundary. */
3171 87 : if( FD_UNLIKELY( sched->last_active_bank_idx!=head_block->parent_idx ) ) { /* Forking is rare. */
3172 87 : FD_LOG_DEBUG(( "activating block %lu:%lu: lane switch to %d", head_block->slot, head_idx, lane_idx ));
3173 87 : sched->metrics->lane_switch_cnt++;
3174 87 : } else {
3175 0 : FD_LOG_DEBUG(( "activating block %lu:%lu: lane %d waking up on slot boundary", head_block->slot, head_idx, lane_idx ));
3176 0 : }
3177 87 : }
3178 93 : sched->active_bank_idx = head_idx;
3179 93 : return;
3180 93 : }
3181 162 : }
3182 :
3183 : /* ... No, promote unstaged blocks. */
3184 105 : ulong root_idx = sched->root_idx;
3185 105 : if( FD_UNLIKELY( root_idx==ULONG_MAX ) ) {
3186 0 : FD_LOG_CRIT(( "invariant violation: root_idx==ULONG_MAX indicating fd_sched is uninitialized" ));
3187 0 : }
3188 : /* Find and stage the longest stageable unstaged fork. This is a
3189 : policy decision. */
3190 105 : ulong depth = compute_longest_unstaged_fork( sched, root_idx );
3191 105 : if( FD_LIKELY( depth>0UL ) ) {
3192 3 : if( FD_UNLIKELY( sched->staged_bitset==fd_ulong_mask_lsb( FD_SCHED_MAX_STAGING_LANES ) ) ) {
3193 : /* No more staging lanes available. All of them are occupied by
3194 : slow squatters. Only empty blocks can be demoted, and so
3195 : blocks with in-flight transactions, including dying in-flight
3196 : blocks, shouldn't be demoted. We demote all demotable lanes.
3197 : Demotion isn't all that expensive, since demotable blocks have
3198 : no transactions in them. If a demoted block proves to be
3199 : active still, it'll naturally promote back into a staging lane.
3200 :
3201 : In fact, all lanes should be demotable at this point. None of
3202 : the lanes have anything dispatchable, otherwise we would have
3203 : simply activated one of the dispatchable lanes. None of the
3204 : lanes have anything in-flight either, as we allow for a grace
3205 : period while something is in-flight, before we deactivate any
3206 : block. In principle, we could get rid of the grace period and
3207 : deactivate right away. In that case, it's okay if nothing is
3208 : demotable at the moment, as that simply implies that all lanes
3209 : have in-flight tasks. We would get another chance to try to
3210 : demote when the last in-flight task on any lane completes.
3211 :
3212 : Another interesting side effect of the current dispatching and
3213 : lane switching policy is that each lane should have exactly one
3214 : block in it at this point. A parent block by definition can't
3215 : be partially ingested. Any parent block that is fully ingested
3216 : and dispatchable would have made the lane dispatchable, and we
3217 : wouldn't be here. Any parent that is fully ingested and fully
3218 : dispatched would be fully done after the grace period. So
3219 : there could only be one block per lane, and it is
3220 : simultaneously the head and the tail of the lane.
3221 :
3222 : A note on why this whole thing does not deadlock:
3223 :
3224 : One might reasonably wonder what happens if all the lanes are
3225 : non-empty, non-dead, but for some reason couldn't be activated
3226 : for dispatching. We would deadlock in this case, as no lane
3227 : dispatches to the point of being demotable, and no unstaged
3228 : block can be promoted. Such is not in fact possible. The only
3229 : way a dispatchable lane can be ineligible for activation is if
3230 : it has a parent block that isn't done yet. So a deadlock
3231 : happens when this parent block, or any of its dispatchable
3232 : ancestors, is unstaged. An important invariant we maintain is
3233 : that a staged block can't have an unstaged stageable parent.
3234 : This invariant, by induction, gives us the guarantee that at
3235 : least one of the lanes can be activated. */
3236 15 : for( int l=0; l<(int)FD_SCHED_MAX_STAGING_LANES; l++ ) {
3237 : /* We would be able to assert that all lanes are demotable,
3238 : except that abandoned blocks are given no grace period for
3239 : deactivation. So there could be lanes transiently occupied
3240 : by dying blocks that are neither demotable (due to in-flight
3241 : tasks) nor activatable (due to being dying). If
3242 : rdisp_demote() supported non-empty blocks, then we could
3243 : probably restore the assertion. */
3244 12 : if( FD_UNLIKELY( !lane_is_demotable( sched, l ) ) ) continue;
3245 12 : ulong demoted_cnt = demote_lane( sched, l );
3246 12 : if( FD_UNLIKELY( demoted_cnt!=1UL ) ) {
3247 0 : FD_LOG_CRIT(( "invariant violation: %lu blocks demoted from lane %d, expected 1 demotion", demoted_cnt, l ));
3248 0 : }
3249 12 : sched->metrics->lane_demoted_cnt++;
3250 12 : }
3251 : /* We weren't able to successfully demote anything. This is
3252 : likely because all lanes are occupied by dying blocks with
3253 : in-flight tasks. We would get another chance to try to demote
3254 : when the last in-flight task on any lane completes. */
3255 3 : if( FD_UNLIKELY( sched->staged_bitset==fd_ulong_mask_lsb( FD_SCHED_MAX_STAGING_LANES ) ) ) return;
3256 3 : }
3257 3 : FD_TEST( sched->staged_bitset!=fd_ulong_mask_lsb( FD_SCHED_MAX_STAGING_LANES ) );
3258 3 : int lane_idx = fd_ulong_find_lsb( ~sched->staged_bitset );
3259 3 : if( FD_UNLIKELY( lane_idx>=(int)FD_SCHED_MAX_STAGING_LANES ) ) {
3260 0 : FD_LOG_CRIT(( "invariant violation: lane_idx %d, sched->staged_bitset %lx",
3261 0 : lane_idx, sched->staged_bitset ));
3262 0 : }
3263 3 : ulong head_bank_idx = stage_longest_unstaged_fork( sched, root_idx, lane_idx );
3264 3 : if( FD_UNLIKELY( head_bank_idx==ULONG_MAX ) ) {
3265 : /* We found a promotable fork depth>0. This should not happen. */
3266 0 : FD_LOG_CRIT(( "invariant violation: head_bank_idx==ULONG_MAX" ));
3267 0 : }
3268 : /* We don't bother with promotion unless the block is immediately
3269 : dispatchable. So it's okay to set the active block here. This
3270 : doesn't cause out-of-order block replay because any parent block
3271 : must be fully done. If the parent block were dead, this fork
3272 : would be marked dead too and ineligible for promotion. If the
3273 : parent block were not dead and not done and staged, we wouldn't
3274 : be trying to promote an unstaged fork. If the parent block were
3275 : not dead and not done and unstaged, it would've been part of this
3276 : unstaged fork. */
3277 3 : fd_sched_block_t * head_block = block_pool_ele( sched, head_bank_idx );
3278 3 : FD_LOG_DEBUG(( "activating block %lu:%lu: unstaged promotion to lane %d", head_block->slot, head_bank_idx, lane_idx ));
3279 3 : sched->active_bank_idx = head_bank_idx;
3280 3 : return;
3281 3 : }
3282 : /* No unstaged blocks to promote. So we're done. Yay. */
3283 105 : }
3284 :
3285 : static void
3286 186 : check_or_set_active_block( fd_sched_t * sched ) {
3287 186 : if( FD_UNLIKELY( sched->active_bank_idx==ULONG_MAX ) ) {
3288 138 : try_activate_block( sched );
3289 138 : } else {
3290 48 : fd_sched_block_t * active_block = block_pool_ele( sched, sched->active_bank_idx );
3291 48 : if( FD_UNLIKELY( block_should_deactivate( active_block ) ) ) {
3292 0 : sched->print_buf_sz = 0UL;
3293 0 : print_all( sched, active_block );
3294 0 : FD_LOG_NOTICE(( "%s", sched->print_buf ));
3295 0 : FD_LOG_CRIT(( "invariant violation: should have been deactivated" ));
3296 0 : }
3297 48 : }
3298 186 : }
3299 :
3300 : /* This function has two main jobs:
3301 : - Mark everything on the fork tree dying.
3302 : - Take blocks out of rdisp if possible. */
3303 : static void
3304 78 : subtree_mark_and_maybe_prune_rdisp( fd_sched_t * sched, fd_sched_block_t * block ) {
3305 78 : if( FD_UNLIKELY( block->rooted ) ) {
3306 0 : FD_LOG_CRIT(( "invariant violation: rooted block should not be abandoned, slot %lu, parent slot %lu",
3307 0 : block->slot, block->parent_slot ));
3308 0 : }
3309 : /* All minority fork nodes pass through this function eventually. So
3310 : this is a good point to check per-node invariants for minority
3311 : forks. */
3312 78 : if( FD_UNLIKELY( block->staged && !block->in_rdisp ) ) {
3313 0 : FD_LOG_CRIT(( "invariant violation: staged block is not in the dispatcher, slot %lu, parent slot %lu",
3314 0 : block->slot, block->parent_slot ));
3315 0 : }
3316 :
3317 78 : fd_sched_block_t * parent = block_pool_ele( sched, block->parent_idx );
3318 78 : if( FD_UNLIKELY( !parent || !parent->in_sched ) ) {
3319 : /* Only the root has no parent. Abandon should never be called on
3320 : the root. So any block we are trying to abandon should have a
3321 : parent. */
3322 0 : FD_LOG_CRIT(( "invariant violation: parent not found slot %lu, parent slot %lu",
3323 0 : block->slot, block->parent_slot ));
3324 0 : }
3325 :
3326 : /* Gated on the parent going down and on this block not already being
3327 : on its way down.
3328 :
3329 : The parent test is because this function also runs on the block the
3330 : public abandon API was called on, whose parent is very much alive.
3331 : Inheriting there would stamp DEAD_ANCESTOR on a block that went
3332 : down on its own, and overwrite the discarded bit the caller just
3333 : set with the live parent's 0.
3334 :
3335 : The block test is because the walk also revisits blocks that
3336 : already went down, and an ancestor abandoned later must not
3337 : re-label them. This cannot be decided based on dead_reason alone
3338 : because a verdict the replay tile made leaves it NONE.
3339 :
3340 : Descendants work fine either way, because dying is set below before
3341 : we recurse, so every child rightfully sees a dying parent. */
3342 78 : if( FD_UNLIKELY( parent->dying && !block->dying ) ) record_lineage_death( block, parent );
3343 :
3344 : /* Setting the flag is non-optional and can happen more than once. */
3345 78 : block->dying = 1;
3346 :
3347 : /* Removal from dispatcher should only happen once. */
3348 78 : if( block->in_rdisp ) {
3349 :
3350 : /* The dispatcher expects blocks to be abandoned in the same order
3351 : that they were added on each lane. There are no requirements on
3352 : the order of abandoning if two blocks are not on the same lane,
3353 : or if a block is unstaged. This means that in general we
3354 : shouldn't abandon a child block if the parent hasn't been
3355 : abandoned yet, if and only if they are on the same lane. So wait
3356 : until we can abandon the parent, and then descend down the fork
3357 : tree to ensure orderly abandoning. */
3358 69 : int in_order = !parent->in_rdisp || /* parent is not in the dispatcher */
3359 69 : !parent->staged || /* parent is in the dispatcher but not staged */
3360 69 : !block->staged || /* parent is in the dispatcher and staged but this block is unstaged */
3361 69 : block->staging_lane!=parent->staging_lane; /* this block is on a different staging lane than its parent */
3362 :
3363 69 : if( FD_UNLIKELY( in_order && block->staged && sched->active_bank_idx==sched->staged_head_bank_idx[ block->staging_lane ] && sched->active_bank_idx!=ULONG_MAX ) ) {
3364 42 : FD_TEST( block_pool_ele( sched, sched->active_bank_idx )==block );
3365 42 : FD_LOG_DEBUG(( "reset active_bank_idx %lu: abandon", sched->active_bank_idx ));
3366 42 : sched->last_active_bank_idx = sched->active_bank_idx;
3367 42 : sched->active_bank_idx = ULONG_MAX;
3368 42 : sched->metrics->deactivate_abandoned_cnt++;
3369 42 : }
3370 :
3371 : /* We inform the dispatcher of an abandon only when there are no
3372 : more in-flight transactions. Otherwise, if the dispatcher
3373 : recycles the same txn_id that was just abandoned, and we receive
3374 : completion of an in-flight transaction whose txn_id was just
3375 : recycled. */
3376 : // FIXME The recycling might be fine now that we no longer use
3377 : // txn_id to index into anything. We might be able to just drop
3378 : // txn_id on abandoned blocks. Though would this leak transaction
3379 : // content if the txn_id is recycled?
3380 : // Note that subtree pruning from sched isn't dependent on the
3381 : // in-flight check being present here, as is_prunable already checks
3382 : // for in-flight==0.
3383 69 : int abandon = in_order && !block_is_in_flight( block );
3384 :
3385 69 : if( abandon ) {
3386 66 : block->in_rdisp = 0;
3387 66 : fd_rdisp_abandon_block( sched->rdisp, (ulong)(block-sched->block_pool) );
3388 66 : block->txn_idx_tail = 0U;
3389 66 : sched->txn_pool_free_cnt += block->txn_parsed_cnt-block->txn_done_cnt; /* in_flight_cnt==0 */
3390 :
3391 66 : sched->metrics->block_abandoned_cnt++;
3392 66 : sched->metrics->txn_abandoned_parsed_cnt += block->txn_parsed_cnt;
3393 66 : sched->metrics->txn_abandoned_exec_done_cnt += block->txn_exec_done_cnt;
3394 66 : sched->metrics->txn_abandoned_done_cnt += block->txn_done_cnt;
3395 :
3396 : //FIXME when demote supports non-empty blocks, we should demote
3397 : //the block from the lane unconditionally and immediately,
3398 : //regardless of whether it's safe to abandon or not. So a block
3399 : //would go immediately from staged to unstaged and eventually to
3400 : //abandoned.
3401 66 : if( FD_LIKELY( block->staged ) ) {
3402 66 : FD_LOG_DEBUG(( "block %lu:%lu exited lane %lu: abandon", block->slot, block_to_idx( sched, block ), block->staging_lane ));
3403 66 : block->staged = 0;
3404 : /* Now release the staging lane. This will release the lane as
3405 : soon as we abandon the head block on a lane. Technically a
3406 : release should only happen when we remove the tail block on a
3407 : lane. This is fine though. The way we abandon guarantees by
3408 : induction that an entire lane will be abandoned. Only the
3409 : head block on a lane can possibly have in-flight
3410 : transactions, and so once a head block becomes eligible for
3411 : abandoning, the entire lane all the way to the tail block,
3412 : will be eligible. */
3413 66 : sched->staged_bitset = fd_ulong_clear_bit( sched->staged_bitset, (int)block->staging_lane );
3414 66 : sched->staged_head_bank_idx[ block->staging_lane ] = ULONG_MAX;
3415 66 : }
3416 66 : }
3417 69 : }
3418 :
3419 : /* Abandon the entire fork chaining off of this block. */
3420 78 : ulong child_idx = block->child_idx;
3421 87 : while( child_idx!=ULONG_MAX ) {
3422 9 : fd_sched_block_t * child = block_pool_ele( sched, child_idx );
3423 9 : subtree_mark_and_maybe_prune_rdisp( sched, child );
3424 9 : child_idx = child->sibling_idx;
3425 9 : }
3426 78 : }
3427 :
3428 : /* This function tells sched that the subtree is no longer worth
3429 : replaying. It can happen as a result of one of the following.
3430 : - Bad block at head of lane.
3431 : - Bad block at tail of lane.
3432 : - Root notify.
3433 :
3434 : It's safe to call this function more than once on the same block. */
3435 : static void
3436 69 : subtree_abandon( fd_sched_t * sched, fd_sched_block_t * block ) {
3437 69 : subtree_mark_and_maybe_prune_rdisp( sched, block );
3438 : /* We do not gate refcnt releases on the entire subtree being
3439 : prunable. In the root notify case there can be in-flight tasks in
3440 : the middle of a subtree, and gating on whole-subtree prunability
3441 : would defer the release of an otherwise prunable block, e.g. an
3442 : inactive sibling of an in-flight block, to a later abandon such as
3443 : a subsequent root notify. That could stall bank reclamation.
3444 :
3445 : The sched fork tree still stays in sync with the banks tree. This
3446 : is to prevent attacks targeting lifetime discrepancy. So while we
3447 : know that the subtree can be pruned from sched at this point, we
3448 : only release refcnts here and stop short of actually pruning, which
3449 : remains solely initiated by banks. */
3450 69 : subtree_release_refcnt( sched, block );
3451 69 : }
3452 :
3453 : /* Release the bank refcnt for every block in the subtree that sched is
3454 : done with. This is evaluated per block. A block's refcnt is
3455 : released as soon as that block individually qualifies, independent of
3456 : whether its siblings or descendants still have in-flight tasks. This
3457 : is safe because the actual pruning is initiated separately by banks,
3458 : and gated on the whole subtree's refcnts reaching zero. Releasing
3459 : refcnts eagerly per block get us there sooner. Blocks that are still
3460 : in-flight will be released when their last task drains. This
3461 : function is idempotent. */
3462 : static void
3463 90 : subtree_release_refcnt( fd_sched_t * sched, fd_sched_block_t * block ) {
3464 90 : FD_TEST( block->in_sched );
3465 90 : if( block->refcnt && block_is_prunable( block ) ) {
3466 78 : FD_TEST( block->dying ); /* The happy path releases the refcnt on full replay. Only bad blocks end up here. */
3467 78 : FD_TEST( !block->block_end_done ); /* Implied by an outstanding refcnt. The happy path releases the refcnt on full replay. */
3468 78 : block->refcnt = 0;
3469 78 : FD_TEST( ref_q_avail( sched->ref_q ) );
3470 78 : ref_q_push_tail( sched->ref_q, block_to_idx( sched, block ) );
3471 78 : if( FD_LIKELY( block->block_start_done ) ) FD_LOG_DEBUG(( "block %lu:%lu replayed partially, releasing refcnt without full replay", block->slot, block_to_idx( sched, block ) ));
3472 69 : else FD_LOG_DEBUG(( "block %lu:%lu replayed nothing, releasing refcnt without any replay", block->slot, block_to_idx( sched, block ) ));
3473 78 : }
3474 :
3475 90 : ulong child_idx = block->child_idx;
3476 99 : while( child_idx!=ULONG_MAX ) {
3477 9 : fd_sched_block_t * child_block = block_pool_ele( sched, child_idx );
3478 9 : subtree_release_refcnt( sched, child_block );
3479 9 : child_idx = child_block->sibling_idx;
3480 9 : }
3481 90 : }
3482 :
3483 : static void
3484 0 : subtree_prune( fd_sched_t * sched, ulong bank_idx, ulong except_idx ) {
3485 0 : fd_sched_block_t * head = block_pool_ele( sched, bank_idx );
3486 0 : head->parent_idx = ULONG_MAX;
3487 0 : fd_sched_block_t * tail = head;
3488 :
3489 0 : while( head ) {
3490 0 : FD_TEST( !head->refcnt );
3491 0 : FD_TEST( head->in_sched );
3492 0 : head->in_sched = 0;
3493 :
3494 0 : ulong child_idx = head->child_idx;
3495 0 : while( child_idx!=ULONG_MAX ) {
3496 0 : fd_sched_block_t * child = block_pool_ele( sched, child_idx );
3497 : /* Add children to be visited. We abuse the parent_idx field to
3498 : link up the next block to visit. */
3499 0 : if( child_idx!=except_idx ) {
3500 0 : tail->parent_idx = child_idx;
3501 0 : tail = child;
3502 0 : tail->parent_idx = ULONG_MAX;
3503 0 : }
3504 0 : child_idx = child->sibling_idx;
3505 0 : }
3506 :
3507 : /* Prune the current block. We will never publish halfway into a
3508 : staging lane, because anything that we are publishing away should
3509 : be out of the dispatcher at this point, much less staged.
3510 : - Anything on the rooted fork should have finished replaying
3511 : gracefully and be out of the dispatcher.
3512 : - Anything on minority forks should have been marked dying and
3513 : be taken out of the dispatcher.
3514 :
3515 : There should be no more in-flight tasks either. Prunes are
3516 : initiated by banks, and the refcnt on the bank won't drop to zero
3517 : unless all in-flight tasks have been drained. So the fact that
3518 : we're pruning implies that the bank thinks there's nothing more
3519 : in-flight. */
3520 0 : if( FD_UNLIKELY( block_is_in_flight( head ) ) ) {
3521 0 : FD_LOG_CRIT(( "invariant violation: block has tasks in flight (%u exec %u sigverify %u poh), slot %lu, parent slot %lu",
3522 0 : head->txn_exec_in_flight_cnt, head->txn_sigverify_in_flight_cnt, head->poh_hashing_in_flight_cnt, head->slot, head->parent_slot ));
3523 0 : }
3524 0 : if( FD_UNLIKELY( head->in_rdisp ) ) {
3525 : /* We should have removed it from the dispatcher when we were
3526 : notified of the new root, or when in-flight transactions were
3527 : drained. */
3528 0 : FD_LOG_CRIT(( "invariant violation: block is in the dispatcher, slot %lu, parent slot %lu", head->slot, head->parent_slot ));
3529 0 : }
3530 :
3531 : /* Return remaining mblk descriptors to the shared pool. */
3532 0 : free_mblk_slist( sched, head, head->mblks_unhashed );
3533 0 : free_mblk_slist( sched, head, head->mblks_hashing_in_progress );
3534 0 : free_mblk_slist( sched, head, head->mblks_mixin_in_progress );
3535 :
3536 0 : if( FD_UNLIKELY( !head->block_end_done ) ) {
3537 0 : sched->print_buf_sz = 0UL;
3538 0 : print_block_metrics( sched, head );
3539 0 : if( FD_LIKELY( head->block_start_done ) ) FD_LOG_DEBUG(( "block %lu:%lu replayed partially, pruning without full replay: %s", head->slot, block_to_idx( sched, head ), sched->print_buf ));
3540 0 : else FD_LOG_DEBUG(( "block %lu:%lu replayed nothing, pruning without any replay: %s", head->slot, block_to_idx( sched, head ), sched->print_buf ));
3541 0 : }
3542 :
3543 0 : sched->block_pool_popcnt--;
3544 :
3545 0 : fd_sched_block_t * next = block_pool_ele( sched, head->parent_idx );
3546 :
3547 : /* We don't have to clear the indices here since no one should be
3548 : accessing them. Defensive programming. */
3549 0 : head->parent_idx = ULONG_MAX;
3550 0 : head->child_idx = ULONG_MAX;
3551 0 : head->sibling_idx = ULONG_MAX;
3552 :
3553 0 : head = next;
3554 0 : }
3555 0 : }
3556 :
3557 : static void
3558 318 : maybe_switch_block( fd_sched_t * sched, ulong bank_idx ) {
3559 : /* This only happens rarely when there are dying in-flight blocks.
3560 : Early exit and don't let dying blocks affect replay. */
3561 318 : if( FD_UNLIKELY( bank_idx!=sched->active_bank_idx ) ) return;
3562 :
3563 318 : fd_sched_block_t * block = block_pool_ele( sched, bank_idx );
3564 318 : if( FD_UNLIKELY( block_is_done( block ) ) ) {
3565 24 : fd_rdisp_remove_block( sched->rdisp, bank_idx );
3566 24 : FD_LOG_DEBUG(( "block %lu:%lu exited lane %lu: remove", block->slot, bank_idx, block->staging_lane ));
3567 24 : block->in_rdisp = 0;
3568 24 : block->staged = 0;
3569 24 : sched->metrics->block_removed_cnt++;
3570 24 : FD_LOG_DEBUG(( "reset active_bank_idx %lu: remove", sched->active_bank_idx ));
3571 24 : sched->last_active_bank_idx = sched->active_bank_idx;
3572 24 : sched->active_bank_idx = ULONG_MAX;
3573 :
3574 : /* See if there is a child block down the same staging lane. This
3575 : is a policy decision to minimize fork churn. We could in theory
3576 : reevaluate staging lane allocation here and do promotion/demotion
3577 : as needed. */
3578 24 : ulong child_idx = block->child_idx;
3579 24 : while( child_idx!=ULONG_MAX ) {
3580 0 : fd_sched_block_t * child = block_pool_ele( sched, child_idx );
3581 0 : if( FD_LIKELY( child->staged && child->staging_lane==block->staging_lane ) ) {
3582 : /* There is a child block down the same staging lane ... */
3583 0 : if( FD_LIKELY( !child->dying ) ) {
3584 : /* ... and the child isn't dead */
3585 0 : if( FD_UNLIKELY( !block_is_activatable( child ) ) ) {
3586 : /* ... but the child is not activatable, likely because
3587 : there are no transactions available yet. */
3588 0 : sched->metrics->deactivate_no_txn_cnt++;
3589 0 : try_activate_block( sched );
3590 0 : return;
3591 0 : }
3592 : /* ... and it's immediately dispatchable, so switch the active
3593 : block to it, and have the child inherit the head status of
3594 : the lane. This is the common case. */
3595 0 : FD_LOG_DEBUG(( "activating block %lu:%lu: child inheritance on lane %lu", child->slot, child_idx, child->staging_lane ));
3596 0 : sched->active_bank_idx = child_idx;
3597 0 : sched->staged_head_bank_idx[ block->staging_lane ] = child_idx;
3598 0 : if( FD_UNLIKELY( !fd_ulong_extract_bit( sched->staged_bitset, (int)block->staging_lane ) ) ) {
3599 0 : FD_LOG_CRIT(( "invariant violation: staged_bitset 0x%lx bit %lu is not set, slot %lu, parent slot %lu, child slot %lu, parent slot %lu",
3600 0 : sched->staged_bitset, block->staging_lane, block->slot, block->parent_slot, child->slot, child->parent_slot ));
3601 0 : }
3602 0 : return;
3603 0 : } else {
3604 : /* ... but the child block is considered dead, likely because
3605 : the parser considers it invalid. */
3606 0 : FD_LOG_INFO(( "child block %lu is already dead", child->slot ));
3607 0 : subtree_abandon( sched, child );
3608 0 : break;
3609 0 : }
3610 0 : }
3611 0 : child_idx = child->sibling_idx;
3612 0 : }
3613 : /* There isn't a child block down the same staging lane. This is
3614 : the last block in the staging lane. Release the staging lane. */
3615 24 : sched->staged_bitset = fd_ulong_clear_bit( sched->staged_bitset, (int)block->staging_lane );
3616 24 : sched->staged_head_bank_idx[ block->staging_lane ] = ULONG_MAX;
3617 24 : sched->metrics->deactivate_no_child_cnt++;
3618 24 : try_activate_block( sched );
3619 294 : } else if( block_should_deactivate( block ) ) {
3620 : /* We exhausted the active block, but it's not fully done yet. We
3621 : are just not getting FEC sets for it fast enough. This could
3622 : happen when the network path is congested, or when the leader
3623 : simply went down. Reset the active block. */
3624 21 : sched->last_active_bank_idx = sched->active_bank_idx;
3625 21 : sched->active_bank_idx = ULONG_MAX;
3626 21 : sched->metrics->deactivate_no_txn_cnt++;
3627 21 : try_activate_block( sched );
3628 21 : }
3629 318 : }
3630 :
3631 : FD_FN_UNUSED static ulong
3632 0 : find_and_stage_longest_unstaged_fork( fd_sched_t * sched, int lane_idx ) {
3633 0 : ulong root_idx = sched->root_idx;
3634 0 :
3635 0 : if( FD_UNLIKELY( root_idx==ULONG_MAX ) ) {
3636 0 : FD_LOG_CRIT(( "invariant violation: root_idx==ULONG_MAX indicating fd_sched is uninitialized" ));
3637 0 : }
3638 0 :
3639 0 : /* First pass: compute the longest unstaged fork depth for each node
3640 0 : in the fork tree. */
3641 0 : ulong depth = compute_longest_unstaged_fork( sched, root_idx );
3642 0 :
3643 0 : /* Second pass: stage blocks on the longest unstaged fork. */
3644 0 : ulong head_bank_idx = stage_longest_unstaged_fork( sched, root_idx, lane_idx );
3645 0 :
3646 0 : if( FD_UNLIKELY( (depth>0UL && head_bank_idx==ULONG_MAX) || (depth==0UL && head_bank_idx!=ULONG_MAX) ) ) {
3647 0 : FD_LOG_CRIT(( "invariant violation: depth %lu, head_bank_idx %lu",
3648 0 : depth, head_bank_idx ));
3649 0 : }
3650 0 :
3651 0 : return head_bank_idx;
3652 0 : }
3653 :
3654 : /* Returns length of the longest stageable unstaged fork, if there is
3655 : one, and 0 otherwise. */
3656 : static ulong
3657 273 : compute_longest_unstaged_fork( fd_sched_t * sched, ulong bank_idx ) {
3658 273 : if( FD_UNLIKELY( bank_idx==ULONG_MAX ) ) {
3659 0 : FD_LOG_CRIT(( "invariant violation: bank_idx==ULONG_MAX" ));
3660 0 : }
3661 :
3662 273 : fd_sched_block_t * block = block_pool_ele( sched, bank_idx );
3663 :
3664 273 : ulong max_child_depth = 0UL;
3665 273 : ulong child_idx = block->child_idx;
3666 441 : while( child_idx!=ULONG_MAX ) {
3667 168 : ulong child_depth = compute_longest_unstaged_fork( sched, child_idx );
3668 168 : if( child_depth > max_child_depth ) {
3669 3 : max_child_depth = child_depth;
3670 3 : }
3671 168 : fd_sched_block_t * child = block_pool_ele( sched, child_idx );
3672 168 : child_idx = child->sibling_idx;
3673 168 : }
3674 :
3675 273 : block->luf_depth = max_child_depth + fd_ulong_if( block_is_promotable( block ), 1UL, 0UL );
3676 273 : return block->luf_depth;
3677 273 : }
3678 :
3679 : static ulong
3680 6 : stage_longest_unstaged_fork_helper( fd_sched_t * sched, ulong bank_idx, int lane_idx ) {
3681 6 : if( FD_UNLIKELY( bank_idx==ULONG_MAX ) ) {
3682 0 : FD_LOG_CRIT(( "invariant violation: bank_idx==ULONG_MAX" ));
3683 0 : }
3684 :
3685 6 : fd_sched_block_t * block = block_pool_ele( sched, bank_idx );
3686 :
3687 6 : int stage_it = fd_int_if( block_is_promotable( block ), 1, 0 );
3688 6 : ulong rv = fd_ulong_if( stage_it, bank_idx, ULONG_MAX );
3689 6 : if( FD_LIKELY( stage_it ) ) {
3690 3 : block->staged = 1;
3691 3 : block->staging_lane = (ulong)lane_idx;
3692 3 : fd_rdisp_promote_block( sched->rdisp, bank_idx, block->staging_lane );
3693 3 : sched->metrics->block_promoted_cnt++;
3694 3 : FD_LOG_DEBUG(( "block %lu:%lu entered lane %lu: promote", block->slot, bank_idx, block->staging_lane ));
3695 3 : }
3696 :
3697 : /* Base case: leaf node. */
3698 6 : if( block->child_idx==ULONG_MAX ) return rv;
3699 :
3700 3 : ulong max_depth = 0UL;
3701 3 : ulong best_child_idx = ULONG_MAX;
3702 3 : ulong child_idx = block->child_idx;
3703 18 : while( child_idx!=ULONG_MAX ) {
3704 15 : fd_sched_block_t * child = block_pool_ele( sched, child_idx );
3705 15 : if( child->luf_depth>max_depth ) {
3706 3 : max_depth = child->luf_depth;
3707 3 : best_child_idx = child_idx;
3708 3 : }
3709 15 : child_idx = child->sibling_idx;
3710 15 : }
3711 :
3712 : /* Recursively stage descendants. */
3713 3 : if( best_child_idx!=ULONG_MAX ) {
3714 3 : ulong head_bank_idx = stage_longest_unstaged_fork_helper( sched, best_child_idx, lane_idx );
3715 3 : rv = fd_ulong_if( rv!=ULONG_MAX, rv, head_bank_idx );
3716 3 : }
3717 :
3718 3 : return rv;
3719 6 : }
3720 :
3721 : /* Returns idx of head block of staged lane on success, idx_null
3722 : otherwise. */
3723 : static ulong
3724 3 : stage_longest_unstaged_fork( fd_sched_t * sched, ulong bank_idx, int lane_idx ) {
3725 3 : ulong head_bank_idx = stage_longest_unstaged_fork_helper( sched, bank_idx, lane_idx );
3726 3 : if( FD_LIKELY( head_bank_idx!=ULONG_MAX ) ) {
3727 3 : sched->metrics->lane_promoted_cnt++;
3728 3 : sched->staged_bitset = fd_ulong_set_bit( sched->staged_bitset, lane_idx );
3729 : /* No need to update staged_popcnt_wmk because the fact that there
3730 : are unstaged blocks implies we already maxed out lanes at one
3731 : point. */
3732 3 : sched->staged_head_bank_idx[ lane_idx ] = head_bank_idx;
3733 3 : }
3734 3 : return head_bank_idx;
3735 3 : }
3736 :
3737 : /* Check if an entire staging lane can be demoted. Returns 1 if all
3738 : blocks in the lane are demotable, 0 otherwise. */
3739 : static int
3740 12 : lane_is_demotable( fd_sched_t * sched, int lane_idx ) {
3741 12 : ulong bank_idx = sched->staged_head_bank_idx[ lane_idx ];
3742 :
3743 24 : while( bank_idx!=ULONG_MAX ) {
3744 12 : fd_sched_block_t * block = block_pool_ele( sched, bank_idx );
3745 12 : FD_TEST( block->staged );
3746 12 : FD_TEST( block->staging_lane==(ulong)lane_idx );
3747 :
3748 12 : if( FD_UNLIKELY( !block_is_demotable( block ) ) ) {
3749 : /* Found a non-demotable block. Early exit. */
3750 0 : return 0;
3751 0 : }
3752 :
3753 : /* Find the child in the same staging lane. */
3754 12 : ulong child_idx = block->child_idx;
3755 12 : ulong next_bank_idx = ULONG_MAX;
3756 12 : while( child_idx!=ULONG_MAX ) {
3757 0 : fd_sched_block_t * child = block_pool_ele( sched, child_idx );
3758 0 : if( child->staged && child->staging_lane==(ulong)lane_idx ) {
3759 0 : next_bank_idx = child_idx;
3760 0 : break;
3761 0 : }
3762 0 : child_idx = child->sibling_idx;
3763 0 : }
3764 12 : bank_idx = next_bank_idx;
3765 12 : }
3766 :
3767 12 : return 1;
3768 12 : }
3769 :
3770 : /* Demote all blocks in a staging lane. Assumes that all blocks in the
3771 : lane are demotable. Returns the number of blocks demoted. */
3772 : static ulong
3773 12 : demote_lane( fd_sched_t * sched, int lane_idx ) {
3774 12 : ulong bank_idx = sched->staged_head_bank_idx[ lane_idx ];
3775 12 : uint demoted_cnt = 0U;
3776 :
3777 24 : while( bank_idx!=ULONG_MAX ) {
3778 12 : fd_sched_block_t * block = block_pool_ele( sched, bank_idx );
3779 12 : FD_TEST( block->staged );
3780 12 : FD_TEST( block->staging_lane==(ulong)lane_idx );
3781 :
3782 12 : int ret = fd_rdisp_demote_block( sched->rdisp, bank_idx );
3783 12 : if( FD_UNLIKELY( ret!=0 ) ) {
3784 0 : FD_LOG_CRIT(( "fd_rdisp_demote_block failed for block %lu:%lu, lane %d", block->slot, bank_idx, lane_idx ));
3785 0 : }
3786 12 : FD_LOG_DEBUG(( "block %lu:%lu exited lane %lu: demote", block->slot, bank_idx, block->staging_lane ));
3787 12 : block->staged = 0;
3788 12 : demoted_cnt++;
3789 :
3790 : /* Find the child in the same staging lane. */
3791 12 : ulong child_idx = block->child_idx;
3792 12 : ulong next_bank_idx = ULONG_MAX;
3793 12 : while( child_idx!=ULONG_MAX ) {
3794 0 : fd_sched_block_t * child = block_pool_ele( sched, child_idx );
3795 0 : if( child->staged && child->staging_lane==(ulong)lane_idx ) {
3796 0 : next_bank_idx = child_idx;
3797 0 : break;
3798 0 : }
3799 0 : child_idx = child->sibling_idx;
3800 0 : }
3801 12 : bank_idx = next_bank_idx;
3802 12 : }
3803 :
3804 : /* Clear the lane. */
3805 12 : sched->staged_bitset = fd_ulong_clear_bit( sched->staged_bitset, lane_idx );
3806 12 : sched->staged_head_bank_idx[ lane_idx ] = ULONG_MAX;
3807 :
3808 12 : sched->metrics->block_demoted_cnt += demoted_cnt;
3809 12 : FD_LOG_DEBUG(( "demoted %u blocks in lane %d", demoted_cnt, lane_idx ));
3810 12 : return demoted_cnt;
3811 12 : }
|
