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