Line data Source code
1 : #ifndef HEADER_fd_src_discof_replay_fd_sched_h
2 : #define HEADER_fd_src_discof_replay_fd_sched_h
3 :
4 : #include "fd_rdisp.h"
5 : #include "../../disco/fd_txn_p.h"
6 : #include "../../disco/store/fd_store.h" /* for fd_store_fec_t */
7 : #include "../../flamenco/accdb/fd_accdb.h"
8 :
9 : /* fd_sched wraps all the smarts and mechanical chores around scheduling
10 : transactions for replay execution. It is built on top of the
11 : dispatcher fd_rdisp. The dispatcher is responsible for high
12 : performance lane-based scheduling of transactions. On top of that,
13 : we add fork-aware management of lanes, and policies regarding which
14 : lanes to prioritize for execution.
15 :
16 : Conceptually, transactions in a block form a DAG. We would like to
17 : make our way through a block with a sufficient degree of parallelism,
18 : such that the execution time of the critical path of the DAG is the
19 : limiting factor. The dispatcher does a good job of emerging the
20 : critical path of the DAG on the fly. Blocks are tracked by the
21 : dispatcher either as a block staged on a lane, or as an unstaged
22 : block. When a block is staged, it will enjoy the most intelligent
23 : online scheduling that the dispatcher has to offer. Lanes have to
24 : consist of linear chains of blocks down a fork. So to map a fork
25 : tree to lanes, we will need multiple lanes. Ideally, every branch in
26 : the fork tree sits on some lane. However, memory footprint limits us
27 : to a few number of lanes.
28 :
29 : This module implements a state machine for ensuring that blocks enter
30 : into and exit out of lanes in an orderly fashion. The public APIs of
31 : this module are invoked to drive state transitions on a small number
32 : of events, such as new transactions arriving, or transactions
33 : completing, or a block being aborted/abandoned. We also implement
34 : policies for deciding which blocks get staged onto lanes, or evicted
35 : from lanes, as well as which lanes to prioritize for execution.
36 :
37 :
38 : The general order in which calls happen under the normal case is:
39 :
40 : fd_sched_fec_ingest()* ... fd_sched_txn_next_ready()* ... fd_sched_txn_done()* ...
41 : more ingest, more ready, more done ...
42 : ...
43 : fd_sched_txn_next_ready() indicates that the last transaction in the block is being scheduled
44 : fd_sched_txn_done()*
45 : fd_sched_block_is_done()
46 : end-of-block processing in caller
47 : fd_sched_txn_next_ready() starts returning transactions from the next block
48 : more ingest, more ready, more done ...
49 : ... */
50 :
51 12 : #define FD_SCHED_MIN_DEPTH 478
52 : #define FD_SCHED_MAX_DEPTH FD_RDISP_MAX_DEPTH
53 :
54 : struct fd_sched;
55 : typedef struct fd_sched fd_sched_t;
56 :
57 : struct fd_sched_alut_ctx {
58 : fd_accdb_t * accdb;
59 : fd_accdb_fork_id_t fork_id;
60 : ulong els; /* Effective lookup slot. */
61 : };
62 : typedef struct fd_sched_alut_ctx fd_sched_alut_ctx_t;
63 :
64 : struct fd_sched_fec {
65 : ulong bank_idx; /* Index of the block. Assumed to be in [0, block_cnt_max). Caller
66 : is responsible for ensuring that bank idx is in bounds and unique
67 : across equivocated blocks. */
68 : ulong parent_bank_idx; /* Index of the parent block. Assumed to be in [0, block_cnt_max).
69 : Caller is responsible for ensuring that parent bank idx is in
70 : bounds and unique across equivocated blocks. */
71 : ulong slot; /* Slot number of the block. */
72 : ulong parent_slot; /* Slot number of the parent block. */
73 : fd_store_fec_t * fec; /* FEC set metadata. */
74 : uchar * data; /* Resolved laddr of the FEC set data buffer. */
75 : uint shred_cnt; /* Number of shreds in the FEC set. */
76 : uint is_last_in_batch:1; /* Set if this is the last FEC set in the batch; relevant because the
77 : parser should ignore trailing bytes at the end of a batch. */
78 : uint is_last_in_block:1; /* Set if this is the last FEC set in the block. */
79 : uint is_first_in_block:1; /* Set if this is the first FEC set in the block. Bank should increment refcnt for sched if such a FEC set has been ingested by sched. */
80 :
81 : fd_sched_alut_ctx_t alut_ctx[ 1 ];
82 : };
83 : typedef struct fd_sched_fec fd_sched_fec_t;
84 :
85 : /* The state of a transaction. Non mutually exclusive. */
86 0 : #define FD_SCHED_TXN_EXEC_DONE (0x0001UL)
87 0 : #define FD_SCHED_TXN_SIGVERIFY_DONE (0x0002UL)
88 0 : #define FD_SCHED_TXN_IS_COMMITTABLE (0x0004UL)
89 0 : #define FD_SCHED_TXN_IS_FEES_ONLY (0x0008UL)
90 : #define FD_SCHED_TXN_REPLAY_DONE (FD_SCHED_TXN_EXEC_DONE|FD_SCHED_TXN_SIGVERIFY_DONE)
91 :
92 : struct fd_sched_txn_info {
93 : ulong flags;
94 : int txn_err;
95 : long tick_parsed;
96 : long tick_sigverify_disp;
97 : long tick_sigverify_done;
98 : long tick_exec_disp;
99 : long tick_exec_done;
100 : ulong index_in_slot; /* 0-indexed position of this transaction within its block. */
101 : };
102 : typedef struct fd_sched_txn_info fd_sched_txn_info_t;
103 :
104 : /* The scheduler may return one of the following types of tasks for the
105 : replay tile.
106 :
107 : e - passed down to exec tiles.
108 : i - replay completes the task immediately.
109 : q - replay may either do it immediately or queue the task up. */
110 36 : #define FD_SCHED_TT_NULL (0UL)
111 72 : #define FD_SCHED_TT_BLOCK_START (1UL) /* (i) Start-of-block processing. */
112 24 : #define FD_SCHED_TT_BLOCK_END (2UL) /* (q) End-of-block processing. */
113 0 : #define FD_SCHED_TT_TXN_EXEC (3UL) /* (e) Transaction execution. */
114 0 : #define FD_SCHED_TT_TXN_SIGVERIFY (4UL) /* (e) Transaction sigverify. */
115 : #define FD_SCHED_TT_LTHASH (5UL) /* (e) Account lthash. */
116 45 : #define FD_SCHED_TT_POH_HASH (6UL) /* (e) PoH hashing. */
117 6 : #define FD_SCHED_TT_MARK_DEAD (7UL) /* (i) Mark the block dead. */
118 :
119 : struct fd_sched_block_start {
120 : ulong bank_idx; /* Same as in fd_sched_fec_t. */
121 : ulong parent_bank_idx; /* Same as in fd_sched_fec_t. */
122 : ulong slot; /* Slot number of the block. */
123 : };
124 : typedef struct fd_sched_block_start fd_sched_block_start_t;
125 :
126 : struct fd_sched_block_end {
127 : ulong bank_idx;
128 : };
129 : typedef struct fd_sched_block_end fd_sched_block_end_t;
130 :
131 : struct fd_sched_txn_exec {
132 : ulong bank_idx;
133 : ulong slot;
134 : ulong txn_idx;
135 : ulong exec_idx;
136 : };
137 : typedef struct fd_sched_txn_exec fd_sched_txn_exec_t;
138 :
139 : struct fd_sched_txn_sigverify {
140 : ulong bank_idx;
141 : ulong txn_idx;
142 : ulong exec_idx;
143 : };
144 : typedef struct fd_sched_txn_sigverify fd_sched_txn_sigverify_t;
145 :
146 : struct fd_sched_poh_hash {
147 : ulong bank_idx;
148 : ulong mblk_idx;
149 : ulong exec_idx;
150 : ulong hashcnt;
151 : fd_hash_t hash[ 1 ];
152 : };
153 : typedef struct fd_sched_poh_hash fd_sched_poh_hash_t;
154 :
155 : struct fd_sched_mark_dead {
156 : ulong bank_idx;
157 : };
158 : typedef struct fd_sched_mark_dead fd_sched_mark_dead_t;
159 :
160 : struct fd_sched_task {
161 : ulong task_type; /* Set to one of the task types defined above. */
162 : union {
163 : fd_sched_block_start_t block_start[ 1 ];
164 : fd_sched_block_end_t block_end[ 1 ];
165 : fd_sched_txn_exec_t txn_exec[ 1 ];
166 : fd_sched_txn_sigverify_t txn_sigverify[ 1 ];
167 : fd_sched_poh_hash_t poh_hash[ 1 ];
168 : fd_sched_mark_dead_t mark_dead[ 1 ];
169 : };
170 : };
171 : typedef struct fd_sched_task fd_sched_task_t;
172 :
173 : struct __attribute__((packed)) fd_microblock_hdr {
174 : /* Number of PoH hashes between this and last microblock */
175 : /* 0x00 */ ulong hash_cnt;
176 :
177 : /* PoH state after evaluating this microblock (including all
178 : appends and mixin). The input to the poh calculation of the first
179 : microblock is the last hash of the parent block, otherwise it is the
180 : hash of the previous microblock. */
181 : /* 0x08 */ uchar hash[32];
182 :
183 : /* Number of transactions in this microblock */
184 : /* 0x28 */ ulong txn_cnt;
185 : };
186 : typedef struct fd_microblock_hdr fd_microblock_hdr_t;
187 :
188 : FD_PROTOTYPES_BEGIN
189 :
190 : /* fd_sched_{align,footprint} return the required alignment and
191 : footprint in bytes for a region of memory to be used as a scheduler.
192 : footprint silently returns 0 if params are invalid (thus convenient
193 : to validate params).
194 :
195 : depth controls the reorder buffer transaction count (~1 million
196 : recommended for live replay, ~10k recommended for async replay).
197 : block_cnt_max is the maximum number of blocks that will be tracked by
198 : the scheduler. */
199 :
200 : ulong
201 : fd_sched_align( void );
202 :
203 : ulong
204 : fd_sched_footprint( ulong depth, /* in [FD_SCHED_MIN_DEPTH,FD_SCHED_MAX_DEPTH] */
205 : ulong block_cnt_max ); /* >= 1 */
206 :
207 : /* fd_sched_new creates a sched object backed by the given memory region
208 : (conforming to align() and footprint()). Returns NULL if any
209 : parameter is invalid. */
210 :
211 : void *
212 : fd_sched_new( void * mem,
213 : fd_rng_t * rng,
214 : ulong depth,
215 : ulong block_cnt_max,
216 : ulong exec_cnt );
217 :
218 : fd_sched_t *
219 : fd_sched_join( void * mem );
220 :
221 : /* Add the data in the FEC set to the scheduler. If is_last_fec is 1,
222 : then this is the last FEC set in the block. Transactions may span
223 : FEC set boundaries. The scheduler is responsible for incrementally
224 : parsing transactions from concatenated FEC set data. Assumes that
225 : FEC sets are delivered in replay order. That is, forks form a
226 : partial ordering over FEC sets: in-order per fork, but arbitrary
227 : ordering across forks. The fork tree is implied by the stream of
228 : parent-child relationships delivered in FEC sets. Also assumes that
229 : there is enough space in the scheduler to ingest the FEC set. The
230 : caller should generally call fd_sched_fec_can_ingest() first.
231 :
232 : Returns 1 on success, 0 if the block is bad and should be marked
233 : dead. */
234 : FD_WARN_UNUSED int
235 : fd_sched_fec_ingest( fd_sched_t * sched, fd_sched_fec_t * fec );
236 :
237 : /* Check if there is enough space in the scheduler to ingest the data in
238 : the FEC set. Returns 1 if there is, 0 otherwise. This is a cheap
239 : and conservative check. */
240 : int
241 : fd_sched_fec_can_ingest( fd_sched_t * sched, fd_sched_fec_t * fec );
242 :
243 : /* Returns the number of worst-case FEC sets sched can ingest. This is a
244 : cheap and conservative check. */
245 : ulong
246 : fd_sched_can_ingest_cnt( fd_sched_t * sched );
247 :
248 : /* Returns 1 if sched is drained, 0 otherwise. A drained scheduler will
249 : not return more work. Otherwise, next_ready will return more work,
250 : so long as there are exec tiles available. */
251 : int
252 : fd_sched_is_drained( fd_sched_t * sched );
253 :
254 : /* Obtain a transaction eligible for execution. This implies that all
255 : prior transactions with w-r or w-w conflicts have completed.
256 : Information regarding the scheduled transaction is written to the out
257 : pointer. Returns 1 on success, 0 on failure. Failures are generally
258 : transient and non-fatal, and are simply an indication that no
259 : transaction is ready for execution yet. When in-flight transactions
260 : retire or when more FEC sets are ingested, more transactions may
261 : become ready for execution.
262 :
263 : Transactions on the same fork will be returned in a way that
264 : maintains the serial fiction. That is, reordering can happen, but
265 : only within the constraint that transactions appear to be ready in
266 : the order in which they occur in the block. Transactions from
267 : different forks may interleave, and the caller should be prepared to
268 : switch execution context in response to interleavings. The scheduler
269 : will barrier on block boundaries, in the sense that transactions from
270 : a subsequent block will not be returned for execution until all
271 : transactions from the previous block have completed. This gives the
272 : caller a chance to perform end-of-block processing before
273 : transactions from a subsequent block start executing. In general,
274 : the caller should check if the last transaction in the current block
275 : is done, and if so, do end-of-block processing before calling this
276 : function to start the next block.
277 :
278 : In addition to returning transactions for execution, this function
279 : may also return a sigverify task. Sigverify can be completed
280 : asynchronously outside the critical path of transaction execution, as
281 : long as every transaction in a block passes sigverify before we
282 : commit the block. The scheduler prioritizes actual execution of
283 : transactions over sigverify, and in general sigverify tasks are only
284 : returned when no real transaction can be dispatched. In other words,
285 : the scheduler tries to exploit idle cycles in the exec tiles during
286 : times of low parallelism critical path progression.
287 :
288 : This function may also return a PoH hashing task. These tasks are
289 : lower priority than transaction execution, but higher priority than
290 : sigverify. This is because sigverify tasks are generally bite-sized,
291 : whereas PoH hashing can be longer, so we would like to get started on
292 : hashing sooner rather than later. */
293 : ulong
294 : fd_sched_task_next_ready( fd_sched_t * sched, fd_sched_task_t * out );
295 :
296 : /* Mark a task as complete. For transaction execution, this means that
297 : the effects of the execution are now visible on any core that could
298 : execute a subsequent transaction. Returns 0 on success, -1 if given
299 : the result of the task, the block turns out to be bad. -1 is only
300 : returned from PoH tasks.
301 :
302 : If a block has been abandoned or marked dead for any reason, it'll be
303 : pruned the moment in-flight task count hits 0 due to the last task
304 : completing. Then, in the immediate ensuing stem run loop,
305 : sched_pruned_next() will return the index for the corresponding bank
306 : so the refcnt can be decremented for sched.
307 :
308 : The transaction at the given index may be freed upon return from this
309 : function. Nonetheless, as long as there is no intervening FEC
310 : ingestion, it would still be safe to query the transaction using
311 : get_txn(). */
312 : int
313 : fd_sched_task_done( fd_sched_t * sched, ulong task_type, ulong txn_idx, ulong exec_idx, void * data );
314 :
315 : /* Abandon a block. This means that we are no longer interested in
316 : executing the block. This also implies that any block which chains
317 : off of the provided block shall be abandoned. This is mainly used
318 : when a block is aborted because we decided that it would be a
319 : dead/invalid block, and so there's no point in spending resources
320 : executing it. The scheduler will no longer return transactions from
321 : abandoned blocks for execution. This should only be invoked on an
322 : actively replayed block, and should only be invoked once on it.
323 :
324 : For the purposes of bank lifetime management, sched is a subsidiary
325 : of banks. So while sched sets things in motion for a bad block to be
326 : eagerly pruned, banks/replay is the sole initiator of actual pruning.
327 : The way this works is that an abandoned block will have its refcnt
328 : queued for release by sched as soon as, and only if, the block has no
329 : more in-flight tasks associated with it. No sooner, no later. In
330 : the immediate ensuing stem run loop, sched_pruned_next() will return
331 : the index for the corresponding bank so the refcnt can be decremented
332 : for sched. After that point, banks will eventually instruct sched to
333 : prune the block, when all other components release their refcnts on
334 : said bank. Then the bank_idx may be recycled for another block. */
335 : void
336 : fd_sched_block_abandon( fd_sched_t * sched, ulong bank_idx );
337 :
338 : /* Prune the given block including descendants of it. */
339 : void
340 : fd_sched_cancel( fd_sched_t * sched, ulong bank_idx );
341 :
342 : /* Add a block as immediately done to the scheduler. This is useful for
343 : installing the snapshot slot, or for informing the scheduler of a
344 : packed leader block. Parent block should be ULONG_MAX for the
345 : snapshot slot, and otherwise a block that hasn't been pruned. */
346 : void
347 : fd_sched_block_add_done( fd_sched_t * sched, ulong bank_idx, ulong parent_bank_idx, ulong slot );
348 :
349 : /* Advance the root, pruning all blocks across forks that do not descend
350 : from the new root. Assumes the new root is in the fork tree and
351 : connected to the current root. Also assumes that there are no more
352 : in-flight transactions from the soon-to-be-pruned blocks. This
353 : should be called after root_notify() and the caller is responsible
354 : for figuring out the new root to safely prune to. */
355 : void
356 : fd_sched_advance_root( fd_sched_t * sched, ulong root_idx );
357 :
358 : /* Notify the scheduler of a new root. This has the effect of calling
359 : abandon() on all minority forks that do not descend from the new
360 : root. Shortly after a call to this function, in-flight transactions
361 : from these abandoned blocks should retire from the execution
362 : pipeline, and the new root will be safe for pruning. */
363 : void
364 : fd_sched_root_notify( fd_sched_t * sched, ulong root_idx );
365 :
366 : /* Returns the index of a bank whose refcnt should be decremented for
367 : sched. This function should be called in a loop to drain all
368 : outstanding refcnt decrements before any other sched API is called in
369 : a stem run loop. Returns ULONG_MAX when there are no more
370 : outstanding references from sched and the loop should break. */
371 : ulong
372 : fd_sched_pruned_block_next( fd_sched_t * sched );
373 :
374 : void
375 : 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 );
376 :
377 : /* fd_sched_block_verify_ticks sets the tick window and verifies
378 : ticks on bank_idx (shred fuzz harness, no exec); 0 if valid. */
379 : int
380 : fd_sched_block_verify_ticks( fd_sched_t * sched,
381 : ulong bank_idx,
382 : ulong tick_height,
383 : ulong max_tick_height,
384 : ulong hashes_per_tick );
385 :
386 : /* fd_sched_set_bypass_poh_verify configures whether the per-microblock
387 : PoH end_hash comparison in maybe_mixin is bypassed. This is intended
388 : for test and fuzz harnesses: the expected end_hash is carried in the
389 : shred payload, so comparing it would reject any mutated input before
390 : the deeper parse/tick logic is exercised. Production call sites
391 : should leave this disabled. */
392 : void
393 : fd_sched_set_bypass_poh_verify( fd_sched_t * sched, int bypass_poh_verify );
394 :
395 : /* fd_sched_set_bypass_alut_resolution bypasses ALUT resolution during
396 : parsing (test/fuzz: no accounts DB). ALUT txns become serializing.
397 : Production call sites should leave this disabled. */
398 : void
399 : fd_sched_set_bypass_alut_resolution( fd_sched_t * sched, int bypass_alut_resolution );
400 :
401 : fd_txn_p_t *
402 : fd_sched_get_txn( fd_sched_t * sched, ulong txn_idx );
403 :
404 : fd_sched_txn_info_t *
405 : fd_sched_get_txn_info( fd_sched_t * sched, ulong txn_idx );
406 :
407 : fd_hash_t *
408 : fd_sched_get_poh( fd_sched_t * sched, ulong bank_idx );
409 :
410 : uint
411 : fd_sched_get_shred_cnt( fd_sched_t * sched, ulong bank_idx );
412 :
413 : void
414 : fd_sched_metrics_write( fd_sched_t * sched );
415 :
416 : /* Serialize the current state as a cstr to the returned buffer. Caller
417 : may read from the buffer until the next invocation of any fd_sched
418 : function. */
419 : char *
420 : fd_sched_get_state_cstr( fd_sched_t * sched );
421 :
422 : void *
423 : fd_sched_leave( fd_sched_t * sched );
424 :
425 : void *
426 : fd_sched_delete( void * mem );
427 :
428 : FD_PROTOTYPES_END
429 :
430 : #endif /* HEADER_fd_src_discof_replay_fd_sched_h */
|
