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