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 0 : #define FD_RDISP_UNSTAGED ULONG_MAX
182 0 : #define FD_RDISP_MAX_ACCT_PER_TXN FD_TXN_ACCT_ADDR_MAX
183 :
184 :
185 0 : #define FD_RDISP_LTHASH_PSEUDO_TXN 0x80000000UL
186 :
187 : /* FD_RDISP_MAX_SCORE is the largest score that will be assigned to a
188 : transaction internally. Lower scores are better. It should be close
189 : to 1 to maximize the scoring function's dynamic range, but small
190 : enough that when added to relevant sized integers, it is distinct
191 : from the next integer. */
192 0 : #define FD_RDISP_MAX_SCORE 0.996f
193 :
194 : struct fd_rdisp;
195 : typedef struct fd_rdisp fd_rdisp_t;
196 :
197 : /* fd_rdisp_neww_* is a bitset used to indicate which accounts are new
198 : writers, where new has the specific meaning described above and in
199 : the comment for fd_rdisp_add_txn. Accounts marked read-only will
200 : have the corresponding bit clear. */
201 : #define SET_NAME fd_rdisp_neww
202 : #define SET_MAX FD_RDISP_MAX_ACCT_PER_TXN
203 : #include "../../util/tmpl/fd_set.c"
204 :
205 : /* fd_rdisp is set up so that the tag of a block can be adjusted to
206 : account for differences in handling duplicate blocks/equivocation. */
207 : #define FD_RDISP_BLOCK_TAG_T ulong
208 :
209 : FD_PROTOTYPES_BEGIN
210 :
211 : /* fd_rdisp_{align,footprint} return the required alignment and
212 : footprint in bytes for a region of memory to be used as a dispatcher.
213 : depth is the maximum number of transaction indices that can be
214 : tracked at a time. Depth must be at least 2 and cannot exceed
215 : FD_RDISP_MAX_DEPTH. block_depth is the maximum number of blocks that
216 : this dispatcher can track. block_depth must be at least 4 and cannot
217 : exceed FD_RDISP_MAX_BLOCK_DEPTH. */
218 : ulong fd_rdisp_align ( void );
219 : ulong fd_rdisp_footprint( ulong depth, ulong block_depth );
220 :
221 :
222 : /* fd_rdisp_new formats a region of memory that satisfies the required
223 : footprint and alignment for use as a dispatcher. depth and
224 : block_depth are as explained in fd_rdisp_footprint. mem is a pointer
225 : to the first byte of a region of memory with the required alignment
226 : and footprint. seed is an arbitrary ulong that is used to determine
227 : a seed of various internal hash tables. On return, the caller will
228 : not be joined.
229 :
230 : fd_rdisp_join joins the caller to the dispatcher, enabling it for
231 : use. */
232 : void *
233 : fd_rdisp_new( void * mem,
234 : ulong depth,
235 : ulong block_depth,
236 : ulong seed );
237 :
238 : fd_rdisp_t *
239 : fd_rdisp_join( void * mem );
240 :
241 : /* fd_rdisp_suggest_staging_lane recommends a staging lane to use for a
242 : potential new block that has a parent block with block tag
243 : parent_block. duplicate is non-zero if this is not the first block
244 : we've seen for its slot.
245 :
246 : This function uses the following logic:
247 : 1. If it's a duplicate, suggest FD_RDISP_UNSTAGED
248 : 2. If parent is the last block in any existing staging lane, suggest
249 : that lane
250 : 3. If there is at least one free lane, suggest a free lane
251 : 4. Else, suggest FD_RDISP_UNSTAGED
252 : Note that this function does not add the block (use add_block) for
253 : that, and does not modify the state of the dispatcher. The caller
254 : should feel free to use or not use the suggested staging lane. */
255 : ulong
256 : fd_rdisp_suggest_staging_lane( fd_rdisp_t const * disp,
257 : FD_RDISP_BLOCK_TAG_T parent_block,
258 : int duplicate );
259 :
260 :
261 : /* fd_rdisp_add_block allocates a new block with the tag new_block from
262 : disp's internal pool. new_block must not be the invalid block tag
263 : value, and it must be distinct from all other values passed as
264 : new_block in all prior calls to fd_rdisp_add_block.
265 :
266 : staging_lane must be either [0,4) or FD_RDISP_UNSTAGED. If
267 : staging_lane is FD_RDISP_UNSTAGED, the block will be UNSTAGED (see
268 : the long comment at the beginning of this header), schedule-ready,
269 : and insert-ready.
270 : If staging_lane is in [0, 4), the block will be STAGED, and it will
271 : be insert-ready. If the specified staging lane contained any blocks
272 : at the time of the call, the last one will no longer be insert-ready,
273 : making this the only insert-ready block in the lane. If the
274 : specified staging lane did not contain any blocks at the time of the
275 : call, then the newly added block will also be schedule-ready.
276 :
277 : Note: if staging lane is in [0, 4) and the specified staging lane
278 : contains a block, that block must have all of its LtHash
279 : pseudo-transactions created prior to calling this function. See
280 : fd_rdisp_add_all_pseudo_txn for more details.
281 :
282 : On successful return, the tag new_block will be usable for other
283 : functions that take a block tag block.
284 :
285 : Returns 0 on success, and -1 on error, which can only happen if out
286 : of resources (the number of unremoved blocks is greater than or equal
287 : to the block_depth) or if new_block was already known. */
288 : int
289 : fd_rdisp_add_block( fd_rdisp_t * disp,
290 : FD_RDISP_BLOCK_TAG_T new_block,
291 : ulong staging_lane );
292 :
293 : /* fd_rdisp_remove_block deallocates a previously-allocated block with
294 : the block tag block, freeing all resources associated with it. block
295 : must be empty (not contain any transactions or pseudo-transactions in
296 : the PENDING, READY, DISPATCHED, or ZOMBIE states), not have any
297 : createable pseudo-transaction, and be schedule-ready. Returns 0 on
298 : success, and -1 if block is not known. After a successful return,
299 : the block tag block will not be known. */
300 : int
301 : fd_rdisp_remove_block( fd_rdisp_t * disp,
302 : FD_RDISP_BLOCK_TAG_T block );
303 :
304 :
305 : /* fd_rdisp_abandon_block is similar to remove_block, but works when the
306 : block contains transactions. It immediately transitions all
307 : transactions part of the block to FREE, and then removes the block as
308 : in fd_rdisp_remove_block. Note that if a transaction is DISPATCHED
309 : at the time of the call complete_txn should NOT be called on that
310 : transaction index when it completes. The specified block must be
311 : schedule-ready.
312 :
313 : In V1 of the dispatcher, this only works if there are no DISPATCHED
314 : transactions.
315 :
316 : Returns 0 on success, and -1 if block is not known. After a
317 : successful return, the block tag block will not be known. */
318 : int
319 : fd_rdisp_abandon_block( fd_rdisp_t * disp,
320 : FD_RDISP_BLOCK_TAG_T block );
321 :
322 :
323 : /* fd_rdisp_{promote,demote}_block modify whether a block is STAGED or
324 : UNSTAGED. Specifically, promote_block promotes the specified block
325 : from UNSTAGED to STAGED, using the specified staging_lane.
326 : demote_block demotes the specified block from STAGED to UNSTAGED.
327 : disp must be a valid local join. If the block tag block is not
328 : known, or is not in the requisite state (UNSTAGED from promote,
329 : STAGED for demote), returns -1.
330 :
331 : When promote_block promotes the specified block, it is placed at the
332 : end of the linear chain in the specified staging_lane. That means
333 : the operation is as if abandon_block were called on the specified
334 : block, then add_block with the specified staging_lane, and then all
335 : transactions in the PENDING and READY states in this block were
336 : re-added in the same order they were originally added. It is
337 : undefined behavior if the specified block contains any transactions
338 : in the DISPATCHED stage. As in add_block, upon successful return,
339 : the specified block will be insert-ready, but will only be
340 : schedule-ready if the specified staging lane was empty at the time of
341 : the call.
342 :
343 : demote_block has the additional requirement that the specified block
344 : must be schedule-ready and empty, that is, not containing any
345 : transactions in the PENDING, READY, or DISPATCHED states.
346 :
347 : For both functions, any LtHash pseudo-transactions that have been
348 : added to block are discarded, but information about which accounts
349 : need addition tasks are carried over. */
350 :
351 : int
352 : fd_rdisp_promote_block( fd_rdisp_t * disp,
353 : FD_RDISP_BLOCK_TAG_T block,
354 : ulong staging_lane );
355 : int
356 : fd_rdisp_demote_block( fd_rdisp_t * disp,
357 : FD_RDISP_BLOCK_TAG_T block );
358 :
359 :
360 : /* fd_rdisp_rekey_block renames the block with tag old_tag so that it
361 : has tag new_tag instead. The block retains all transactions, its
362 : STAGED/UNSTAGED state, etc. On successful return, tag old_tag will
363 : no longer be a known tag, and new_tag must be used in any future
364 : calls to refer to the block previously known as old_tag.
365 :
366 : disp must be a valid local join. new_tag must not be a known tag,
367 : but old_tag must be a known tag.
368 :
369 : Return 0 on success and -1 on error. The only error cases are if
370 : new_tag is already a known tag or old_tag is not a known tag. */
371 : int
372 : fd_rdisp_rekey_block( fd_rdisp_t * disp,
373 : FD_RDISP_BLOCK_TAG_T new_tag,
374 : FD_RDISP_BLOCK_TAG_T old_tag );
375 :
376 : /* fd_rdisp_add_txn adds a transaction to the block with tag
377 : insert_block in serial order. That means that this dispatcher will
378 : ensure this transaction appears to execute after each transaction
379 : added to this block in a prior call.
380 :
381 : insert_block must be a known block that is insert-ready. txn,
382 : payload, and alts describe the transaction to be added. txn must be
383 : the result of parsing payload, and alts contains the expansion and
384 : selection of the address lookup tables mentioned in the transaction
385 : (i.e. all the writable accounts followed by all the read-only
386 : accounts). alts may be NULL, even if the transaction specifies that
387 : it loads accounts from an address lookup table; in this case,
388 : addresses from ALTs are ignored. There must be no duplicate accounts
389 : in the transaction to be added.
390 :
391 : Shockingly, this dispatcher does not retain any read interest (much
392 : less write interest) in the transaction (txn, payload, or alts). On
393 : success, it returns a transaction index that was previously in the
394 : FREE state. This API is designed to facilitate a model of use where
395 : the replay tile copies the incoming transaction to a region of
396 : private memory, adds it to this dispatcher, and then copies it (using
397 : non-temporal stores) to the output dcache at a location determined by
398 : the returned index. Although there are two memcpys in this approach,
399 : it should result in fewer cache misses.
400 :
401 : If serializing is non-zero, this transaction will be a serialization
402 : point: all transactions added prior to this one must complete before
403 : this transaction can be scheduled, and this transaction must complete
404 : before any subsequently added transactions can be scheduled. This is
405 : not good for performance, but is useful for the rare case when
406 : repair/turbine is several slots ahead of replay, and a transaction
407 : loads some accounts from an address lookup table, but we haven't
408 : executed the transaction to populate that part of the address lookup
409 : table yet. This is the primary use for alts==NULL.
410 :
411 : If new_writable is non-NULL, the provided bitset will be populated.
412 : Upon return, bit i will be set in new_writable if account i (in the
413 : standard order) was writable, and this is the first transaction in
414 : this block to record it as writable since the most recent call to
415 : fd_rdisp_add_pseudo_txn that created a pseudo-transaction for this
416 : account address; otherwise bit i will be cleared. If new_writable is
417 : NULL, the accounts in this transaction will be ignored for the
418 : purposes of LtHash tracking. Obviously, if alts==NULL, accounts in
419 : alts will not be included in LtHash tracking.
420 :
421 : rdisp can track depth*FD_RDISP_MAX_ACCT_PER_TXN writable accounts,
422 : which is enough so it doesn't run out even if the whole depth is full
423 : with transactions that write to the maximum number of unique
424 : accounts. However, it is possible to run out of state for tracking
425 : accounts by adding transactions, scheduling and completing them
426 : repeatedly. If depth is less than
427 : max CUs per block
428 : -------------------------------,
429 : 300 * FD_RDISP_MAX_ACCT_PER_TXN
430 :
431 : the caller MUST create and schedule pseudo-transactions every depth
432 : transactions or depth*MAX_ACCT_PER_TXN writable accounts. For
433 : example, at 75M CUs and MAX_ACCT_PER_TXN=128, care needs to be taken
434 : if depth is less than 2000.
435 :
436 : Returns 0 and does not add the transaction on failure. Fails if
437 : there were no free transaction indices, if the block with tag
438 : insert_block did not exist, or if it was not schedule-ready.
439 :
440 : At the time this function returns, the returned transaction index
441 : will be in the PENDING or READY state, depending on whether it
442 : conflicts with something previously inserted. */
443 : ulong
444 : fd_rdisp_add_txn( fd_rdisp_t * disp,
445 : FD_RDISP_BLOCK_TAG_T insert_block,
446 : fd_txn_t const * txn,
447 : uchar const * payload,
448 : fd_acct_addr_t const * alts,
449 : int serializing,
450 : fd_rdisp_neww_t * new_writable );
451 :
452 : /* fd_rdisp_peek_free_txn returns the transaction index the next
453 : successful fd_rdisp_add_txn will return if no transaction is
454 : completed and reclaimed in between, or 0 if there are no free
455 : transaction indices. A hint for prefetching the caller's per
456 : transaction state; it does not change the dispatcher. */
457 : ulong
458 : fd_rdisp_peek_free_txn( fd_rdisp_t const * disp );
459 :
460 : /* fd_rdisp_get_next_ready returns the transaction index of a READY
461 : transaction that was inserted with block tag schedule_block if one
462 : exists, otherwise an LtHash pseudo-transaction if one exists,
463 : otherwise 0. The block with the tag schedule_block must be
464 : schedule-ready.
465 :
466 : If there are multiple READY transactions, which exact one is returned
467 : is arbitrary. That said, this function does make some effort to pick
468 : one that (upon completion) will unlock more parallelism. Similarly,
469 : if there are multiple READY LtHash pseudo-transactions, this function
470 : makes some effort to return one that is less likely to be written to
471 : again in this block. You can identify whether the returned value is
472 : a normal transaction or an LtHash pseudo-transaction by examining the
473 : high bit (returned value & FD_RDISP_LTHASH_PSEUDO_TXN non-zero), and
474 : decode it with fd_rdisp_pseudo_txn_to_addr.
475 :
476 : disp must be a valid local join. At the time this function returns,
477 : the returned transaction or pseudo-transaction index (if nonzero)
478 : will transition to the DISPATCHED state. */
479 : ulong
480 : fd_rdisp_get_next_ready( fd_rdisp_t * disp,
481 : FD_RDISP_BLOCK_TAG_T schedule_block );
482 :
483 : /* fd_rdisp_complete_txn notifies the dispatcher that the specified
484 : transaction or pseudo-transaction (which must have been in the
485 : DISPATCHED state) has completed. Logs warning and returns on error
486 : (invalid txn_idx, not in DISPATCHED state). This function may cause
487 : other transactions to transition from PENDING to READY.
488 :
489 : At the time this function returns, the specified transaction index
490 : will be in the FREE state, if reclaim!=0. Otherwise, if reclaim==0,
491 : the specified transaction index will be in the ZOMBIE state. A
492 : ZOMBIE transaction has the exact same effect as a FREE transaction on
493 : causing other transactions to transition from PENDING to READY.
494 : However, the dispatcher will not reclaim the specified transaction
495 : index until a future invocation of fd_rdisp_complete_txn with the
496 : same txn_idx, which must have reclaim!=0. This is useful when there
497 : is non-execution work to be done asynchronously for the transaction,
498 : but the caller would like to unblock the execution of transactions
499 : that depend on this one. If txn_idx is an LtHash pseudo-transaction,
500 : this function will ignore the value of reclaim and behave like
501 : reclaim!=0. */
502 : void
503 : fd_rdisp_complete_txn( fd_rdisp_t * disp,
504 : ulong txn_idx,
505 : int reclaim );
506 :
507 : /* fd_rdisp_pseudo_txn_to_addr stores to out the account address
508 : (pubkey) associated with a pseudo-transaction index txn_idx. txn_idx
509 : must be in the PENDING, READY, or DISPATCHED state, which means
510 : txn_idx must have been returned from get_next_ready or
511 : fd_rdisp_add_pseudo_txn and must have FD_RDISP_LTHASH_PSEUDO_TXN set.
512 : Note that this means once you call complete_txn on a txn_idx, you
513 : cannot call this function on it any more. disp must be a valid local
514 : join. out must be non-NULL. */
515 : void
516 : fd_rdisp_pseudo_txn_to_addr( fd_rdisp_t const * disp,
517 : ulong txn_idx,
518 : fd_acct_addr_t * out );
519 :
520 : /* fd_rdisp_add_pseudo_txn creates an LtHash addition pseudo-transaction
521 : for an arbitrary account that was marked as writable by a transaction
522 : added to insert_block with add_txn since the last call to
523 : add_pseudo_txn that returned that address (if any). If no account
524 : meets that condition, returns 0.
525 :
526 : fd_rdisp_add_all_pseudo_txn repeats calls to add_pseudo_txn until it
527 : returns 0. The transaction indices of the pseudo-transactions that
528 : get created in the process are not provided to the caller.
529 :
530 : disp must be a valid local join, and insert_block must be a known
531 : block that is insert-ready. Returns the transaction index for the
532 : pseudo-txn that was created, but for most uses, this value is not
533 : very meaningful.
534 :
535 : This function tries to create a pseudo-transaction that is READY if
536 : it can. Additionally, it will try to create a pseudo-transaction for
537 : an account that is less likely to be written to again. This means
538 : when there are multiple account addresses that meet the criteria in
539 : the first paragraph, which is returned is effectively arbitrary.
540 : It's clear that other things being equal, creating a
541 : pseudo-transaction that is READY is better than creating one that is
542 : PENDING. Similarly, it's clear that creating a pseudo-transaction
543 : for an account that is less likely to be written is better than one
544 : for an account more likely to be written again. However, combining
545 : them is slightly tricky. The criteria we would like is that it's
546 : better to create a pseudo-transaction for a PENDING account B than a
547 : READY account A if it's likely another transaction that writes to
548 : account A will arrive before we can complete the addition LtHash task
549 : for A. Implementing this requires estimating how long hashing takes
550 : and a more precise estimate of when a transaction will be used again
551 : than we have, so we ignore this.
552 :
553 : Summing all that up: if you're catching or otherwise not at the tip
554 : of the chain, just wait until the end of the block and call
555 : add_all_pseudo_txn. If you are at the tip of the chain, dispatch all
556 : READY transactions, then all the sigverify, PoH verify, and LtHash
557 : subtraction tasks first, since the results of those are definitely
558 : needed. If you're still idle, call add_pseudo_txn once, then
559 : get_next_ready once, and repeat.
560 :
561 : IMPORTANT: if insert_block is staged, add_pseudo_txn must be called
562 : until it returns 0 prior to inserting another block in the same
563 : staging lane. You may also use fd_rdisp_add_all_pseudo_txn for this
564 : purpose.
565 :
566 : Note: If insert_block is unstaged, pseudo-transactions are always
567 : after normal transactions. This behavior differs slightly from
568 : staged blocks (where the pseudo-transaction is inserted in a way that
569 : preserves serial fiction) and may change in the future. This
570 : shouldn't cause problems, but it probably means that the best
571 : approach for unstaged blocks is to call add_all_pseudo_txn after the
572 : last transaction is received. Anything else is trying to optimize
573 : for dispatching performance, but in a situation where that doesn't
574 : really apply.
575 :
576 : Note: the criteria described in the first paragraph is a bit
577 : complicated, so here's an easier way to think about it. You can
578 : imagine that when a transaction is added with add_txn, all its
579 : writable account addresses get added to a per-block set. Then this
580 : function removes one address from that set and creates a
581 : pseudo-transaction for it. If add_txn is subsequently called with a
582 : transaction that writes to that same account, it goes back into the
583 : set, so add_pseudo_txn may return it again. */
584 : ulong
585 : fd_rdisp_add_pseudo_txn( fd_rdisp_t * disp,
586 : FD_RDISP_BLOCK_TAG_T insert_block );
587 :
588 : void
589 : fd_rdisp_add_all_pseudo_txn( fd_rdisp_t * disp,
590 : FD_RDISP_BLOCK_TAG_T insert_block );
591 :
592 :
593 : /* fd_rdisp_add_writable and add_extra_pseudo_txn informs rdisp that the
594 : account address pointed to by addr should be considered having been
595 : written at this point in insertion order for the sake of LtHash
596 : tracking. The primary use case for these two functions is tracking
597 : LtHash tasks for serializing transactions, but it is also useful for
598 : accounts that are written by non-transaction processes (e.g. rewards
599 : distribution). add_extra_pseudo_txn takes the additional step of
600 : creating a pseudo transaction for this account address unless it is
601 : sure that an appropriate one already exists.
602 :
603 : disp must be a valid local join. insert_block must be insert-ready.
604 : schedule_block must be schedule-ready. If the block is both
605 : insert-ready and schedule-ready, prefer add_writable. addr is a
606 : pointer to the account address of interest.
607 :
608 : add_writable returns -1 on error (block not found or not
609 : insert-ready), 1 if this is the first write to the specified account
610 : since the most recent call to fd_rdisp_add_pseudo_txn that added a
611 : pseudo-transaction for this account address, and 0 otherwise. This
612 : is essentially the value of the bit in new_writable.
613 :
614 : On the other hand, add_extra_pseudo_txn returns the
615 : pseudo-transaction index that was created. WARNING:
616 : add_extra_pseudo_txn can result in two addition pseudo-transaction
617 : without an intervening write. This function shouldn't really exist
618 : because normally it's not possible to add to a block unless it is
619 : insert-ready, so it is a bit of a hack. */
620 : int
621 : fd_rdisp_add_writable( fd_rdisp_t * disp,
622 : FD_RDISP_BLOCK_TAG_T insert_block,
623 : fd_acct_addr_t const * addr );
624 : ulong
625 : fd_rdisp_add_extra_pseudo_txn( fd_rdisp_t * disp,
626 : FD_RDISP_BLOCK_TAG_T schedule_block,
627 : fd_acct_addr_t const * addr );
628 :
629 : typedef struct {
630 : FD_RDISP_BLOCK_TAG_T schedule_ready_block;
631 : FD_RDISP_BLOCK_TAG_T insert_ready_block;
632 : } fd_rdisp_staging_lane_info_t;
633 :
634 : /* fd_rdisp_staging_lane_info copies the current staging lane info to
635 : out. Returns a 4-bit bitset, where bit i being set means that
636 : staging lane i is occupied. If staging lane i is occupied, then
637 : out_sched[i] is populated. */
638 : ulong
639 : fd_rdisp_staging_lane_info( fd_rdisp_t const * disp,
640 : fd_rdisp_staging_lane_info_t out_sched[ static 4 ] );
641 :
642 : /* fd_rdisp_verify does some light verification and internal consistency
643 : checks of some internal data structures. Aborts with an error
644 : message if anything fails verification. disp is a pointer to a valid
645 : local join, and scratch is a pointer to a region of scratch memory
646 : with at least depth*(FD_RDISP_MAX_ACCT_PER_TXN+1)+2 elements that
647 : will be clobbered (its contents at the time of the function call are
648 : ignored). */
649 : void
650 : fd_rdisp_verify( fd_rdisp_t const * disp,
651 : uint * scratch );
652 :
653 : void *
654 : fd_rdisp_leave( fd_rdisp_t * disp );
655 :
656 : void *
657 : fd_rdisp_delete( void * mem );
658 :
659 : FD_PROTOTYPES_END
660 :
661 : #endif /* HEADER_fd_src_discof_replay_fd_rdisp_h */
|
