Line data Source code
1 : #ifndef HEADER_fd_src_discof_replay_fd_rdisp_h
2 : #define HEADER_fd_src_discof_replay_fd_rdisp_h
3 :
4 : #include "../../disco/fd_disco_base.h"
5 :
6 : /* fd_rdisp defines methods for building a DAG (directed acyclic graph)
7 : of transactions, executing them in the appropriate order with the
8 : maximum amount of parallelism, and keeping track of the accounts they
9 : write to compute the LtHash efficiently.
10 :
11 : Transactions must appear to execute in the order in which they occur
12 : in the block (the "serial fiction"). However, when two transactions
13 : are independent, they can actually be scheduled in either order, or
14 : in parallel. Two transactions are independent unless one writes to
15 : an account that the other reads or writes. If two transactions are
16 : not independent, the one that comes earlier in the block is a
17 : predecessor transaction of the one that comes later in the block. In
18 : order to ensure correct execution, a transaction cannot be executed
19 : until all its predecessor transactions have completed. In this file,
20 : a transaction completing means that the results of its account writes
21 : will be visible to a subsequent transaction executing on any core.
22 :
23 : Shockingly, this dispatcher does not need to keep a copy of
24 : transactions (more on this later), which means it operates almost
25 : entirely on transaction indices. An index is a positive integer
26 : (uint) up to some maximum. The 0 index is a sentinel, and doesn't
27 : correspond to a real transaction. It's up to the caller to maintain
28 : the mapping between each transaction index and the transaction itself.
29 :
30 : A transaction index is in one of the following states:
31 : * FREE, which means it doesn't correspond to a transaction.
32 : * PENDING, which means it corresponds to a transaction that can't
33 : be scheduled yet because it must come after transactions that
34 : have not completed execution yet.
35 : * READY, which means all predecessor transactions have completed
36 : execution, but this transaction index has not been returned by
37 : get_next_ready yet.
38 : * ZOMBIE, which means the transaction completed execution, and
39 : successor transactions may be transitioned to the READY state,
40 : but the transaction index should not be recycled yet, because
41 : there are outstanding non-execution tasks associated with this
42 : transaction.
43 : * DISPATCHED, which means this transaction index was returned by
44 : get_next_ready but has not been completed yet.
45 :
46 :
47 : --------------> PENDING
48 : add_txn | |
49 : FREE ---------| |
50 : ^ | V get_next_ready
51 : | --------------> READY ----------------
52 : | |
53 : | |
54 : | complete_txn(reclaim) V
55 : |<-------------------------------------------- DISPATCHED
56 : | |
57 : | | complete_txn(noreclaim)
58 : | complete_txn(reclaim) V
59 : |<---------------------------------------------- ZOMBIE
60 :
61 :
62 : Additionally, fd_rdisp is block-aware, and even somewhat fork-aware.
63 : Prior to inserting a transaction, a block must be added. Then, when
64 : a transaction is inserted, the caller must specify the block it is
65 : part of.
66 :
67 : At all times, each block is either STAGED or UNSTAGED. Blocks that
68 : are STAGED benefit from the full parallelization-maximizing dispatch,
69 : but at most four linear chains of blocks can be STAGED at any time.
70 : Assuming the limit of four is still satisfied, when a block is added,
71 : it may be added as STAGED. Otherwise, if it's added as UNSTAGED, it
72 : may be promoted to STAGED later, though this is worse for performance
73 : than adding it as STAGED initially. Blocks may be demoted from
74 : STAGED to UNSTAGED only if the linear chain doesn't contain any
75 : PENDING, READY, or DISPATCHED transactions.
76 :
77 : Prior to properly introducing staging lanes, we need to introduce two
78 : more concepts. A block can be insert-ready, schedule-ready, neither,
79 : or both. A block must be insert-ready to call add_txn on
80 : it; a block must be schedule-ready to call get_next_ready on it.
81 : Various functions either require or modify these properties of a
82 : block. These properties are necessary but not sufficient for the
83 : respective functions to succeed; for example, a block may be
84 : schedule-ready but empty, in which case, scheduling will still not
85 : succeed. An UNSTAGED block is always both insert-ready and
86 : schedule-ready.
87 :
88 : A staging lane can contain a single block or a sequence of blocks.
89 : When a staging lane contains more than one block, some restrictions
90 : apply, namely, only the first block in the sequence is
91 : schedule-ready, and only the last block in the sequence is
92 : insert-ready, where first and last are determined by the order in
93 : which the block is staged. Although this restriction makes the
94 : interface a bit more complicated, it's driven by performance
95 : requirements and common use cases. Basically, there's no use for
96 : being able to replay a block before we've replayed its parent block.
97 :
98 : Basically, rdisp is designed to handle three situations well:
99 : * The normal case, where replay is pretty much caught up, and there
100 : are only one or two forks, containing only one or two un-replayed
101 : blocks each.
102 : * The startup case, where repair is far ahead of replay, but there's
103 : only a single fork, or very few forks
104 : * The DoS case, where there are many forks, perhaps duplicate
105 : blocks, and we don't know which to prioritize yet, but we will
106 : execute some, and prune the rest later. This includes the case
107 : where we stop receiving transactions from some of the forks but
108 : don't know that the block has ended.
109 :
110 : In the normal case, there are few enough unreplayed blocks that it
111 : doesn't really matter how the staging lanes are used. For the
112 : startup case, the long linear chains of blocks can all be STAGED using
113 : the same lane with no performance degradation. In the DoS case, most
114 : of the forks will be UNSTAGED, and using some combination of
115 : replaying, cancelling, and demoting blocks, staging lanes can be freed
116 : up so that the canonical chain can emerge.
117 :
118 : Consider the following example of storing a fork tree in staging
119 : lanes:
120 : - Slot 10's parent is not specified
121 : - Slot 11's parent is slot 10
122 : - Slot 13's parent is slot 11
123 : - Slot 14's parent is also slot 11
124 :
125 : Since the caller chooses the staging lane, the caller may choose
126 : between
127 : Lane 0: 10 --> 11 --> 13
128 : Lane 1: 14
129 : and
130 : Lane 0: 10 --> 11 --> 14
131 : Lane 1: 13.
132 : or any of the various combinations that consume more staging lanes.
133 : Note that the concept of staging lanes is a performance optimization,
134 : not a safety feature. With the first arrangement, the caller cannot
135 : call get_next_ready on slot 13 in between slots 10 and 11, but
136 : there's no issue with calling it on slot 14 then, which would
137 : obviously result in an incorrect replay. It's ultimately the caller's
138 : responsibility to ensure correct replay.
139 :
140 : In addition to scheduling transactions efficiently, rdisp also
141 : provides functionality for computing the LtHash efficiently. For
142 : each account that is written to in the block, we need to subtract the
143 : account's initial hash value as of the start of the block and then
144 : add in the account's final hash value as of the end of the block to
145 : compute the LtHash. Thus, at least naively, there are two conceptual
146 : tasks per writable account, named for how the value is used: the
147 : subtraction task and the addition task.
148 :
149 : The subtraction task is a bit simpler, since we know we're going to
150 : need it for a given account once we see the first transaction that
151 : marks it as writable. In addition, because it reads the previous
152 : value of the account, it never conflicts with executing transactions.
153 : The subtraction tasks are only on the critical path in the way
154 : transaction sigverify tasks are; they must be done before voting on
155 : the block, but that's it.
156 :
157 : The addition tasks are much trickier to get right. We want to
158 : dispatch the addition task for an account as soon as the last write
159 : completes, but we don't know a priori when a write was the last
160 : write, unless we wait until the slot ends. However, waiting until
161 : the slot ends means it's much more likely addition tasks end up on
162 : the critical path, and our main goal is to avoid that. Furthermore,
163 : if we schedule an addition task, then subsequently receive a
164 : transaction that writes to that account, we need to be careful not to
165 : cause a data race. Even though we wouldn't care about the value
166 : returned, the current implementation of the acctdb does not tolerate
167 : races.
168 :
169 : All of this leads to a split and slightly complicated API. Addition
170 : tasks are represented with pseudo-transactions the caller can create
171 : and then schedule when idle (see below). These pseudo-transactions
172 : can be returned when scheduling the next transaction. On the other
173 : hand, when adding a transaction, rdisp optionally populates a bitmask
174 : indicating which writable accounts have not been marked as writable
175 : in a transaction inserted since the most recent pseudo-transaction
176 : was created for it. That's a little obtuse, but essentially creating
177 : a pseudo-transaction for an account address makes it new again. */
178 :
179 : #define FD_RDISP_MAX_DEPTH 0x7FFFFFUL /* 23 bit numbers, approx 8M */
180 : #define FD_RDISP_MAX_BLOCK_DEPTH 0xFFFFUL /* 16 bits */
181 1000 : #define FD_RDISP_UNSTAGED ULONG_MAX
182 5031 : #define FD_RDISP_MAX_ACCT_PER_TXN FD_TXN_ACCT_ADDR_MAX
183 :
184 : /* 62,500,000 CUs gets 3137 transactions with 64 writers and one with 34
185 : writers for a total of 200,802. Then we add 8k for inflation
186 : rewards, 10 for sysvars, 4000 for vote accounts, and a bit of
187 : padding. */
188 25085 : #define FD_RDISP_MAX_WRITERS_PER_BLOCK 217354UL
189 :
190 0 : #define FD_RDISP_LTHASH_PSEUDO_TXN 0x80000000UL
191 :
192 : /* FD_RDISP_MAX_SCORE is the largest score that will be assigned to a
193 : transaction internally. Lower scores are better. It should be close
194 : to 1 to maximize the scoring function's dynamic range, but small
195 : enough that when added to relevant sized integers, it is distinct
196 : from the next integer. That stops being true at 2^17, where
197 : I+0.996f rounds to I+1 in float. Pseudo-transactions can push a
198 : block's integer parts (last_serializing, inserted_cnt) that high, so
199 : fd_rdisp_score clamps the sum. */
200 0 : #define FD_RDISP_MAX_SCORE 0.996f
201 :
202 : /* FD_RDISP_PTXN_SCORE is the fractional score of every staged LtHash
203 : pseudo-transaction. It is above FD_RDISP_MAX_SCORE, so within a
204 : serializing class every READY transaction is handed out before any
205 : READY pseudo-transaction. Pseudo-transactions are not ordered among
206 : themselves. fd_rdisp_score keeps the sum below integer_part+1 for
207 : every integer part below 2^24. From 2^14 the largest transaction
208 : fraction and this constant round to the same float, and from 2^16 the
209 : clamp sets in. A block of a few thousand transactions and additions
210 : stays well below 2^14. */
211 0 : #define FD_RDISP_PTXN_SCORE 0.997f
212 :
213 : /* FD_RDISP_READY_ACCT_EMA_MAX bounds the reference EMA of an account
214 : that fd_rdisp_add_ready_pseudo_txn may hand out, which is to say an
215 : account still worth speculating on once its writers have completed.
216 : The EMA adds 0.005 per transaction referencing the account and decays
217 : per transaction inserted, so an account referenced by one in ten
218 : recent transactions sits near 0.1, one in twenty near 0.05. An
219 : account over the threshold is considered hot and likely written again
220 : before the block ends. The EMA is always less than 1.0, so we can
221 : use a threshold of 1.0 to state a policy of speculating on every
222 : account. */
223 1008 : #define FD_RDISP_READY_ACCT_EMA_MAX (1.0f)
224 :
225 : /* fd_rdisp_score returns frac+integer_part as a float that is
226 : >=integer_part and strictly <integer_part+1. The integer part of a
227 : score is how many completions the node waits for, so a sum that
228 : rounded up to integer_part+1 would wait for one completion too many,
229 : possibly one that never comes. For a fraction of at most
230 : FD_RDISP_MAX_SCORE the plain sum is below integer_part+1 until 2^17
231 : and is returned bit for bit. A sum that rounds up, which the
232 : pseudo-transaction fraction does from 2^16, is replaced by the
233 : largest float below integer_part+1. Requires 0<=frac<1 and
234 : integer_part<2^24. */
235 : FD_FN_CONST static inline float
236 : fd_rdisp_score( float frac,
237 1542 : uint integer_part ) {
238 1542 : float s = frac + (float)integer_part;
239 1542 : float next = (float)(integer_part+1U);
240 1542 : if( FD_UNLIKELY( s>=next ) ) {
241 : /* next>=1.0f is a positive normal, so the float just below it is
242 : one bit pattern down. */
243 0 : union { float f; uint u; } t;
244 0 : t.f = next;
245 0 : t.u--;
246 0 : s = t.f;
247 0 : }
248 1542 : return s;
249 1542 : }
250 :
251 : struct fd_rdisp;
252 : typedef struct fd_rdisp fd_rdisp_t;
253 :
254 : /* fd_rdisp_neww_* is a bitset used to indicate which accounts are new
255 : writers, where new has the specific meaning described above and in
256 : the comment for fd_rdisp_add_txn. Accounts marked read-only will
257 : have the corresponding bit clear. */
258 : #define SET_NAME fd_rdisp_neww
259 : #define SET_MAX FD_RDISP_MAX_ACCT_PER_TXN
260 : #include "../../util/tmpl/fd_set.c"
261 :
262 : /* fd_rdisp is set up so that the tag of a block can be adjusted to
263 : account for differences in handling duplicate blocks/equivocation. */
264 : #define FD_RDISP_BLOCK_TAG_T ulong
265 :
266 : FD_PROTOTYPES_BEGIN
267 :
268 : /* fd_rdisp_{align,footprint} return the required alignment and
269 : footprint in bytes for a region of memory to be used as a dispatcher.
270 : depth is the maximum number of transaction indices that can be
271 : tracked at a time. Depth must be at least 2 and cannot exceed
272 : FD_RDISP_MAX_DEPTH. block_depth is the maximum number of blocks that
273 : this dispatcher can track. block_depth must be at least 4 and cannot
274 : exceed FD_RDISP_MAX_BLOCK_DEPTH. The account pool holds the
275 : FD_RDISP_MAX_ACCT_PER_TXN accounts each of the depth transactions can
276 : reference, plus acct_extra entries for the accounts a staging lane
277 : keeps in its writable set past the life of their transactions. See
278 : fd_rdisp_add_pseudo_txn. Pass 0 for acct_extra when the writable
279 : sets are not used. Returns 0 if the account pool would exceed the
280 : index space of an account edge. */
281 : ulong fd_rdisp_align ( void );
282 : ulong fd_rdisp_footprint( ulong depth, ulong block_depth, ulong acct_extra );
283 :
284 :
285 : /* fd_rdisp_new formats a region of memory that satisfies the required
286 : footprint and alignment for use as a dispatcher. depth and
287 : block_depth are as explained in fd_rdisp_footprint. mem is a pointer
288 : to the first byte of a region of memory with the required alignment
289 : and footprint. seed is an arbitrary ulong that is used to determine
290 : a seed of various internal hash tables. On return, the caller will
291 : not be joined.
292 :
293 : fd_rdisp_join joins the caller to the dispatcher, enabling it for
294 : use. */
295 : void *
296 : fd_rdisp_new( void * mem,
297 : ulong depth,
298 : ulong block_depth,
299 : ulong acct_extra,
300 : ulong seed );
301 :
302 : fd_rdisp_t *
303 : fd_rdisp_join( void * mem );
304 :
305 : /* fd_rdisp_suggest_staging_lane recommends a staging lane to use for a
306 : potential new block that has a parent block with block tag
307 : parent_block. duplicate is non-zero if this is not the first block
308 : we've seen for its slot.
309 :
310 : This function uses the following logic:
311 : 1. If it's a duplicate, suggest FD_RDISP_UNSTAGED
312 : 2. If parent is the last block in any existing staging lane, suggest
313 : that lane
314 : 3. If there is at least one free lane, suggest a free lane
315 : 4. Else, suggest FD_RDISP_UNSTAGED
316 : Note that this function does not add the block (use add_block) for
317 : that, and does not modify the state of the dispatcher. The caller
318 : should feel free to use or not use the suggested staging lane. */
319 : ulong
320 : fd_rdisp_suggest_staging_lane( fd_rdisp_t const * disp,
321 : FD_RDISP_BLOCK_TAG_T parent_block,
322 : int duplicate );
323 :
324 :
325 : /* fd_rdisp_add_block allocates a new block with the tag new_block from
326 : disp's internal pool. new_block must not be the invalid block tag
327 : value, and it must be distinct from all other values passed as
328 : new_block in all prior calls to fd_rdisp_add_block.
329 :
330 : staging_lane must be either [0,4) or FD_RDISP_UNSTAGED. If
331 : staging_lane is FD_RDISP_UNSTAGED, the block will be UNSTAGED (see
332 : the long comment at the beginning of this header), schedule-ready,
333 : and insert-ready.
334 : If staging_lane is in [0, 4), the block will be STAGED, and it will
335 : be insert-ready. If the specified staging lane contained any blocks
336 : at the time of the call, the last one will no longer be insert-ready,
337 : making this the only insert-ready block in the lane. If the
338 : specified staging lane did not contain any blocks at the time of the
339 : call, then the newly added block will also be schedule-ready.
340 :
341 : Note: if staging lane is in [0, 4) and the specified staging lane
342 : contains a block, that block must have all of its LtHash
343 : pseudo-transactions created prior to calling this function. See
344 : fd_rdisp_add_all_pseudo_txn for more details.
345 :
346 : On successful return, the tag new_block will be usable for other
347 : functions that take a block tag block.
348 :
349 : Returns 0 on success, and -1 on error, which can only happen if out
350 : of resources (the number of unremoved blocks is greater than or equal
351 : to the block_depth) or if new_block was already known. */
352 : int
353 : fd_rdisp_add_block( fd_rdisp_t * disp,
354 : FD_RDISP_BLOCK_TAG_T new_block,
355 : ulong staging_lane );
356 :
357 : /* fd_rdisp_remove_block deallocates a previously-allocated block with
358 : the block tag block, freeing all resources associated with it. block
359 : must be empty (not contain any transactions or pseudo-transactions in
360 : the PENDING, READY, DISPATCHED, or ZOMBIE states), not have any
361 : createable pseudo-transaction, and be schedule-ready. Returns 0 on
362 : success, and -1 if block is not known. After a successful return,
363 : the block tag block will not be known. */
364 : int
365 : fd_rdisp_remove_block( fd_rdisp_t * disp,
366 : FD_RDISP_BLOCK_TAG_T block );
367 :
368 :
369 : /* fd_rdisp_abandon_block is similar to remove_block, but works when the
370 : block contains transactions. It immediately transitions all
371 : transactions part of the block to FREE, and then removes the block as
372 : in fd_rdisp_remove_block. Note that if a transaction is DISPATCHED
373 : at the time of the call complete_txn should NOT be called on that
374 : transaction index when it completes. The specified block must be
375 : schedule-ready.
376 :
377 : In V1 of the dispatcher, this only works if there are no DISPATCHED
378 : transactions.
379 :
380 : Returns 0 on success, and -1 if block is not known. After a
381 : successful return, the block tag block will not be known. */
382 : int
383 : fd_rdisp_abandon_block( fd_rdisp_t * disp,
384 : FD_RDISP_BLOCK_TAG_T block );
385 :
386 :
387 : /* fd_rdisp_{promote,demote}_block modify whether a block is STAGED or
388 : UNSTAGED. Specifically, promote_block promotes the specified block
389 : from UNSTAGED to STAGED, using the specified staging_lane.
390 : demote_block demotes the specified block from STAGED to UNSTAGED.
391 : disp must be a valid local join. If the block tag block is not
392 : known, or is not in the requisite state (UNSTAGED from promote,
393 : STAGED for demote), returns -1.
394 :
395 : When promote_block promotes the specified block, it is placed at the
396 : end of the linear chain in the specified staging_lane. That means
397 : the operation is as if abandon_block were called on the specified
398 : block, then add_block with the specified staging_lane, and then all
399 : transactions in the PENDING and READY states in this block were
400 : re-added in the same order they were originally added. It is
401 : undefined behavior if the specified block contains any transactions
402 : in the DISPATCHED stage. As in add_block, upon successful return,
403 : the specified block will be insert-ready, but will only be
404 : schedule-ready if the specified staging lane was empty at the time of
405 : the call.
406 :
407 : demote_block has the additional requirement that the specified block
408 : must be schedule-ready and empty, that is, not containing any
409 : transactions in the PENDING, READY, or DISPATCHED states.
410 :
411 : For both functions, every LtHash pseudo-transaction created for the
412 : block must have completed, and information about which accounts need
413 : addition tasks is carried over. */
414 :
415 : int
416 : fd_rdisp_promote_block( fd_rdisp_t * disp,
417 : FD_RDISP_BLOCK_TAG_T block,
418 : ulong staging_lane );
419 : int
420 : fd_rdisp_demote_block( fd_rdisp_t * disp,
421 : FD_RDISP_BLOCK_TAG_T block );
422 :
423 : /* fd_rdisp_clear_writable_set forgets every account in the writable set
424 : of the block's lane. No addition pseudo-transaction will be created
425 : for them and demotion registers none of them as unstaged writable
426 : accounts. Transactions added afterwards with a NULL new_writable
427 : keep the set empty. Returns 0 on success and -1 if the block is not
428 : found, not staged, or not schedule-ready. */
429 : int
430 : fd_rdisp_clear_writable_set( fd_rdisp_t * disp,
431 : FD_RDISP_BLOCK_TAG_T block );
432 :
433 :
434 : /* fd_rdisp_rekey_block renames the block with tag old_tag so that it
435 : has tag new_tag instead. The block retains all transactions, its
436 : STAGED/UNSTAGED state, etc. On successful return, tag old_tag will
437 : no longer be a known tag, and new_tag must be used in any future
438 : calls to refer to the block previously known as old_tag.
439 :
440 : disp must be a valid local join. new_tag must not be a known tag,
441 : but old_tag must be a known tag.
442 :
443 : Return 0 on success and -1 on error. The only error cases are if
444 : new_tag is already a known tag or old_tag is not a known tag. */
445 : int
446 : fd_rdisp_rekey_block( fd_rdisp_t * disp,
447 : FD_RDISP_BLOCK_TAG_T new_tag,
448 : FD_RDISP_BLOCK_TAG_T old_tag );
449 :
450 : /* fd_rdisp_add_txn adds a transaction to the block with tag
451 : insert_block in serial order. That means that this dispatcher will
452 : ensure this transaction appears to execute after each transaction
453 : added to this block in a prior call.
454 :
455 : insert_block must be a known block that is insert-ready. txn,
456 : payload, and alts describe the transaction to be added. txn must be
457 : the result of parsing payload, and alts contains the expansion and
458 : selection of the address lookup tables mentioned in the transaction
459 : (i.e. all the writable accounts followed by all the read-only
460 : accounts). alts may be NULL, even if the transaction specifies that
461 : it loads accounts from an address lookup table; in this case,
462 : addresses from ALTs are ignored. There must be no duplicate accounts
463 : in the transaction to be added.
464 :
465 : Shockingly, this dispatcher does not retain any read interest (much
466 : less write interest) in the transaction (txn, payload, or alts). On
467 : success, it returns a transaction index that was previously in the
468 : FREE state. This API is designed to facilitate a model of use where
469 : the replay tile copies the incoming transaction to a region of
470 : private memory, adds it to this dispatcher, and then copies it (using
471 : non-temporal stores) to the output dcache at a location determined by
472 : the returned index. Although there are two memcpys in this approach,
473 : it should result in fewer cache misses.
474 :
475 : If serializing is non-zero, this transaction will be a serialization
476 : point: all transactions added prior to this one must complete before
477 : this transaction can be scheduled, and this transaction must complete
478 : before any subsequently added transactions can be scheduled. This is
479 : not good for performance, but is useful for the rare case when
480 : repair/turbine is several slots ahead of replay, and a transaction
481 : loads some accounts from an address lookup table, but we haven't
482 : executed the transaction to populate that part of the address lookup
483 : table yet. This is the primary use for alts==NULL.
484 :
485 : If new_writable is non-NULL, the provided bitset will be populated.
486 : Upon return, bit i will be set in new_writable if account i (in the
487 : standard order) was writable, and this is the first transaction in
488 : this block to record it as writable since the most recent call to
489 : fd_rdisp_add_pseudo_txn that created a pseudo-transaction for this
490 : account address; otherwise bit i will be cleared. If new_writable is
491 : NULL, the accounts in this transaction will be ignored for the
492 : purposes of LtHash tracking. Obviously, if alts==NULL, accounts in
493 : alts will not be included in LtHash tracking.
494 :
495 : rdisp can track depth*FD_RDISP_MAX_ACCT_PER_TXN writable accounts,
496 : which is enough so it doesn't run out even if the whole depth is full
497 : with transactions that write to the maximum number of unique
498 : accounts. However, it is possible to run out of state for tracking
499 : accounts by adding transactions, scheduling and completing them
500 : repeatedly. If depth is less than
501 : max CUs per block
502 : -------------------------------,
503 : 300 * FD_RDISP_MAX_ACCT_PER_TXN
504 :
505 : the caller MUST create and schedule pseudo-transactions every depth
506 : transactions or depth*MAX_ACCT_PER_TXN writable accounts. For
507 : example, at 75M CUs and MAX_ACCT_PER_TXN=128, care needs to be taken
508 : if depth is less than 2000.
509 :
510 : Returns 0 and does not add the transaction on failure. Fails if
511 : there were no free transaction indices, if the block with tag
512 : insert_block did not exist, or if it was not schedule-ready.
513 :
514 : At the time this function returns, the returned transaction index
515 : will be in the PENDING or READY state, depending on whether it
516 : conflicts with something previously inserted. */
517 : ulong
518 : fd_rdisp_add_txn( fd_rdisp_t * disp,
519 : FD_RDISP_BLOCK_TAG_T insert_block,
520 : fd_txn_t const * txn,
521 : uchar const * payload,
522 : fd_acct_addr_t const * alts,
523 : int serializing,
524 : fd_rdisp_neww_t * new_writable );
525 :
526 : /* fd_rdisp_peek_free_txn returns the transaction index the next
527 : successful fd_rdisp_add_txn will return if no transaction is
528 : completed and reclaimed in between, or 0 if there are no free
529 : transaction indices. A hint for prefetching the caller's per
530 : transaction state; it does not change the dispatcher. */
531 : ulong
532 : fd_rdisp_peek_free_txn( fd_rdisp_t const * disp );
533 :
534 : /* fd_rdisp_get_next_ready returns the transaction index of a READY
535 : transaction that was inserted with block tag schedule_block if one
536 : exists, otherwise an LtHash pseudo-transaction if one exists,
537 : otherwise 0. The block with the tag schedule_block must be
538 : schedule-ready.
539 :
540 : If there are multiple READY transactions, which exact one is returned
541 : is arbitrary. That said, this function does make some effort to pick
542 : one that (upon completion) will unlock more parallelism. Similarly,
543 : if there are multiple READY LtHash pseudo-transactions, this function
544 : makes some effort to return one that is less likely to be written to
545 : again in this block. You can identify whether the returned value is
546 : a normal transaction or an LtHash pseudo-transaction by examining the
547 : high bit (returned value & FD_RDISP_LTHASH_PSEUDO_TXN non-zero), and
548 : decode it with fd_rdisp_pseudo_txn_to_addr.
549 :
550 : disp must be a valid local join. At the time this function returns,
551 : the returned transaction or pseudo-transaction index (if nonzero)
552 : will transition to the DISPATCHED state. */
553 : ulong
554 : fd_rdisp_get_next_ready( fd_rdisp_t * disp,
555 : FD_RDISP_BLOCK_TAG_T schedule_block );
556 :
557 : /* fd_rdisp_complete_txn notifies the dispatcher that the specified
558 : transaction or pseudo-transaction (which must have been in the
559 : DISPATCHED state) has completed. Logs warning and returns on error
560 : (invalid txn_idx, not in DISPATCHED state). This function may cause
561 : other transactions to transition from PENDING to READY.
562 :
563 : At the time this function returns, the specified transaction index
564 : will be in the FREE state, if reclaim!=0. Otherwise, if reclaim==0,
565 : the specified transaction index will be in the ZOMBIE state. A
566 : ZOMBIE transaction has the exact same effect as a FREE transaction on
567 : causing other transactions to transition from PENDING to READY.
568 : However, the dispatcher will not reclaim the specified transaction
569 : index until a future invocation of fd_rdisp_complete_txn with the
570 : same txn_idx, which must have reclaim!=0. This is useful when there
571 : is non-execution work to be done asynchronously for the transaction,
572 : but the caller would like to unblock the execution of transactions
573 : that depend on this one. If txn_idx is an LtHash pseudo-transaction,
574 : this function will ignore the value of reclaim and behave like
575 : reclaim!=0. */
576 : void
577 : fd_rdisp_complete_txn( fd_rdisp_t * disp,
578 : ulong txn_idx,
579 : int reclaim );
580 :
581 : /* fd_rdisp_pseudo_txn_to_addr stores to out the account address
582 : (pubkey) associated with a pseudo-transaction index txn_idx. txn_idx
583 : must be in the PENDING, READY, or DISPATCHED state, which means
584 : txn_idx must have been returned from get_next_ready or
585 : fd_rdisp_add_pseudo_txn and must have FD_RDISP_LTHASH_PSEUDO_TXN set.
586 : Note that this means once you call complete_txn on a txn_idx, you
587 : cannot call this function on it any more. disp must be a valid local
588 : join. out must be non-NULL. */
589 : void
590 : fd_rdisp_pseudo_txn_to_addr( fd_rdisp_t const * disp,
591 : ulong txn_idx,
592 : fd_acct_addr_t * out );
593 :
594 : /* fd_rdisp_add_pseudo_txn creates an LtHash addition pseudo-transaction
595 : for an arbitrary account that was marked as writable by a transaction
596 : added to insert_block with add_txn since the last call to
597 : add_pseudo_txn that returned that address (if any). If no account
598 : meets that condition, returns 0.
599 :
600 : fd_rdisp_add_all_pseudo_txn repeats calls to add_pseudo_txn until it
601 : returns 0. The transaction indices of the pseudo-transactions that
602 : get created in the process are not provided to the caller.
603 :
604 : disp must be a valid local join, and insert_block must be a known
605 : block that is insert-ready. Returns the transaction index for the
606 : pseudo-txn that was created, but for most uses, this value is not
607 : very meaningful.
608 :
609 : Accounts are classified into two classes. The first class of
610 : accounts, whose every writer in the block has completed, and whose
611 : reference EMA is under the threshold, come out first, last completed
612 : first. A pseudo-transaction for one of them is READY on creation,
613 : barring an outstanding serializing transaction. The second class of
614 : accounts come out coldest first, by reference EMA, and their
615 : pseudo-transactions are PENDING behind the writer still outstanding.
616 : fd_rdisp_add_ready_pseudo_txn pops from the first class only.
617 :
618 : Summing all that up: if you're catching up or otherwise not at the
619 : tip of the chain, just wait until the end of the block and call
620 : add_all_pseudo_txn. If you are at the tip of the chain, dispatch all
621 : READY transactions, then all the sigverify, PoH verify, and LtHash
622 : subtraction tasks first, since the results of those are definitely
623 : needed. If you're still idle, call add_ready_pseudo_txn once, then
624 : get_next_ready once, and repeat.
625 :
626 : IMPORTANT: if insert_block is staged, add_pseudo_txn must be called
627 : until it returns 0 prior to inserting another block in the same
628 : staging lane. You may also use fd_rdisp_add_all_pseudo_txn for this
629 : purpose.
630 :
631 : Note: If insert_block is unstaged, pseudo-transactions are always
632 : after normal transactions. This behavior differs slightly from
633 : staged blocks (where the pseudo-transaction is inserted in a way that
634 : preserves serial fiction) and may change in the future. This
635 : shouldn't cause problems, but it probably means that the best
636 : approach for unstaged blocks is to call add_all_pseudo_txn after the
637 : last transaction is received. Anything else is trying to optimize
638 : for dispatching performance, but in a situation where that doesn't
639 : really apply.
640 :
641 : Note: the criteria described in the first paragraph is a bit
642 : complicated, so here's an easier way to think about it. You can
643 : imagine that when a transaction is added with add_txn, all its
644 : writable account addresses get added to a per-block set. Then this
645 : function removes one address from that set and creates a
646 : pseudo-transaction for it. If add_txn is subsequently called with a
647 : transaction that writes to that same account, it goes back into the
648 : set, so add_pseudo_txn may return it again. */
649 : ulong
650 : fd_rdisp_add_pseudo_txn( fd_rdisp_t * disp,
651 : FD_RDISP_BLOCK_TAG_T insert_block );
652 :
653 : void
654 : fd_rdisp_add_all_pseudo_txn( fd_rdisp_t * disp,
655 : FD_RDISP_BLOCK_TAG_T insert_block );
656 :
657 : /* fd_rdisp_add_ready_pseudo_txn is add_pseudo_txn restricted to the
658 : accounts whose addition can be hashed now, meaning every writer of
659 : the account in insert_block has completed and its reference EMA is
660 : under the threshold of fd_rdisp_set_ready_acct_ema_max. The
661 : pseudo-transaction it creates is READY on creation, unless a
662 : serializing transaction is still outstanding ahead of it. Returns 0
663 : if no account qualifies, or if insert_block is unstaged. */
664 : ulong
665 : fd_rdisp_add_ready_pseudo_txn( fd_rdisp_t * disp,
666 : FD_RDISP_BLOCK_TAG_T insert_block );
667 :
668 : /* fd_rdisp_set_ready_acct_ema_max sets the reference EMA threshold of
669 : fd_rdisp_add_ready_pseudo_txn, FD_RDISP_READY_ACCT_EMA_MAX by
670 : default. An account qualifies when its last writer completes under
671 : the threshold in force at that moment, so a later change does not
672 : reclassify accounts already in the set. */
673 : void
674 : fd_rdisp_set_ready_acct_ema_max( fd_rdisp_t * disp, float ema_max );
675 :
676 :
677 : /* fd_rdisp_add_writable and add_extra_pseudo_txn informs rdisp that the
678 : account address pointed to by addr should be considered having been
679 : written at this point in insertion order for the sake of LtHash
680 : tracking. The primary use case for these two functions is tracking
681 : LtHash tasks for serializing transactions, but it is also useful for
682 : accounts that are written by non-transaction processes (e.g. rewards
683 : distribution). add_extra_pseudo_txn takes the additional step of
684 : creating a pseudo transaction for this account address unless it is
685 : sure that an appropriate one already exists.
686 :
687 : disp must be a valid local join. insert_block must be insert-ready.
688 : schedule_block must be schedule-ready. If the block is both
689 : insert-ready and schedule-ready, prefer add_writable. addr is a
690 : pointer to the account address of interest.
691 :
692 : add_writable returns -1 on error (block not found or not
693 : insert-ready), 1 if this is the first write to the specified account
694 : since the most recent call to fd_rdisp_add_pseudo_txn that added a
695 : pseudo-transaction for this account address, and 0 otherwise. This
696 : is essentially the value of the bit in new_writable.
697 :
698 : On the other hand, add_extra_pseudo_txn returns the
699 : pseudo-transaction index that was created. WARNING:
700 : add_extra_pseudo_txn can result in two addition pseudo-transaction
701 : without an intervening write. This function shouldn't really exist
702 : because normally it's not possible to add to a block unless it is
703 : insert-ready, so it is a bit of a hack. */
704 : int
705 : fd_rdisp_add_writable( fd_rdisp_t * disp,
706 : FD_RDISP_BLOCK_TAG_T insert_block,
707 : fd_acct_addr_t const * addr );
708 : ulong
709 : fd_rdisp_add_extra_pseudo_txn( fd_rdisp_t * disp,
710 : FD_RDISP_BLOCK_TAG_T schedule_block,
711 : fd_acct_addr_t const * addr );
712 :
713 : typedef struct {
714 : FD_RDISP_BLOCK_TAG_T schedule_ready_block;
715 : FD_RDISP_BLOCK_TAG_T insert_ready_block;
716 : } fd_rdisp_staging_lane_info_t;
717 :
718 : /* fd_rdisp_staging_lane_info copies the current staging lane info to
719 : out. Returns a 4-bit bitset, where bit i being set means that
720 : staging lane i is occupied. If staging lane i is occupied, then
721 : out_sched[i] is populated. */
722 : ulong
723 : fd_rdisp_staging_lane_info( fd_rdisp_t const * disp,
724 : fd_rdisp_staging_lane_info_t out_sched[ static 4 ] );
725 :
726 : /* fd_rdisp_lane_writable_cnt returns the number of accounts in the
727 : writable set of staging_lane, which must be in [0,4).
728 :
729 : fd_rdisp_lane_ready_acct_cnt returns how many of them
730 : fd_rdisp_add_ready_pseudo_txn would currently pick from. */
731 : ulong
732 : fd_rdisp_lane_writable_cnt( fd_rdisp_t * disp, ulong staging_lane );
733 :
734 : ulong
735 : fd_rdisp_lane_ready_acct_cnt( fd_rdisp_t * disp, ulong staging_lane );
736 :
737 : /* fd_rdisp_verify does some light verification and internal consistency
738 : checks of some internal data structures. Aborts with an error
739 : message if anything fails verification. disp is a pointer to a valid
740 : local join, and scratch is a pointer to a region of scratch memory
741 : with at least depth+depth*FD_RDISP_MAX_ACCT_PER_TXN+acct_extra+2
742 : elements, one per transaction and pseudo-transaction slot, that will
743 : be clobbered (its contents at the time of the function call are
744 : ignored). */
745 : void
746 : fd_rdisp_verify( fd_rdisp_t const * disp,
747 : uint * scratch );
748 :
749 : void *
750 : fd_rdisp_leave( fd_rdisp_t * disp );
751 :
752 : void *
753 : fd_rdisp_delete( void * mem );
754 :
755 : FD_PROTOTYPES_END
756 :
757 : #endif /* HEADER_fd_src_discof_replay_fd_rdisp_h */
|
