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, and executing them in the appropriate order with the
8 : maximum amount of parallelism.
9 :
10 : Transactions must appear to execute in the order in which they occur
11 : in the block (the "serial fiction"). However, when two transactions
12 : are independent, they can actually be scheduled in either order, or
13 : in parallel. Two transactions are independent unless one writes to
14 : an account that the other reads or writes. If two transactions are
15 : not independent, the one that comes earlier in the block is a
16 : predecessor transaction of the one that comes later in the block. In
17 : order to ensure correct execution, a transaction cannot be executed
18 : until all its predecessor transactions have completed. In this file,
19 : a transaction completing means that the results of its account writes
20 : will be visible to a subsequent transaction executing on any core.
21 :
22 : Shockingly, this dispatcher does not need to keep a copy of
23 : transactions (more on this later), which means it operates almost
24 : entirely on transaction indices. An index is a positive integer
25 : (uint) up to some maximum. The 0 index is a sentinel, and doesn't
26 : correspond to a real transaction. It's up to the caller to maintain
27 : the mapping between each transaction index and the transaction itself.
28 :
29 : A transaction index is in one of the following states:
30 : * FREE, which means it doesn't correspond to a transaction.
31 : * PENDING, which means it corresponds to a transaction that can't
32 : be scheduled yet because it must come after transactions that
33 : have not completed execution yet.
34 : * READY, which means all predecessor transactions have completed
35 : execution, but this transaction index has not been returned by
36 : get_next_ready yet.
37 : * ZOMBIE, which means the transaction completed execution, and
38 : successor transactions may be transitioned to the READY state,
39 : but the transaction index should not be recycled yet, because
40 : there are outstanding non-execution tasks associated with this
41 : transaction.
42 : * DISPATCHED, which means this transaction index was returned by
43 : get_next_ready but has not been completed yet.
44 :
45 :
46 : --------------> PENDING
47 : add_txn | |
48 : FREE ---------| |
49 : ^ | V get_next_ready
50 : | --------------> READY ----------------
51 : | |
52 : | |
53 : | complete_txn(reclaim) V
54 : |<-------------------------------------------- DISPATCHED
55 : | |
56 : | | complete_txn(noreclaim)
57 : | complete_txn(reclaim) V
58 : |<---------------------------------------------- ZOMBIE
59 :
60 :
61 : Additionally, fd_rdisp is block-aware, and even somewhat fork-aware.
62 : Prior to inserting a transaction, a block must be added. Then, when
63 : a transaction is inserted, the caller must specify the block it is
64 : part of.
65 :
66 : At all times, each block is either STAGED or UNSTAGED. Blocks that
67 : are STAGED benefit from the full parallelization-maximizing dispatch,
68 : but at most four linear chains of blocks can be STAGED at any time.
69 : Assuming the limit of four is still satisfied, when a block is added,
70 : it may be added as STAGED. Otherwise, if it's added as UNSTAGED, it
71 : may be promoted to STAGED later, though this is worse for performance
72 : than adding it as STAGED initially. Blocks may be demoted from
73 : STAGED to UNSTAGED only if the linear chain doesn't contain any
74 : PENDING, READY, or DISPATCHED transactions.
75 :
76 : Prior to properly introducing staging lanes, we need to introduce two
77 : more concepts. A block can be insert-ready, schedule-ready, neither,
78 : or both. A block must be insert-ready to call add_txn on
79 : it; a block must be schedule-ready to call get_next_ready on it.
80 : Various functions either require or modify these properties of a
81 : block. These properties are necessary but not sufficient for the
82 : respective functions to succeed; for example, a block may be
83 : schedule-ready but empty, in which case, scheduling will still not
84 : succeed. An UNSTAGED block is always both insert-ready and
85 : schedule-ready.
86 :
87 : A staging lane can contain a single block or a sequence of blocks.
88 : When a staging lane contains more than one block, some restrictions
89 : apply, namely, only the first block in the sequence is
90 : schedule-ready, and only the last block in the sequence is
91 : insert-ready, where first and last are determined by the order in
92 : which the block is staged. Although this restriction makes the
93 : interface a bit more complicated, it's driven by performance
94 : requirements and common use cases. Basically, there's no use for
95 : being able to replay a block before we've replayed its parent block.
96 :
97 : Basically, rdisp is designed to handle three situations well:
98 : * The normal case, where replay is pretty much caught up, and there
99 : are only one or two forks, containing only one or two un-replayed
100 : blocks each.
101 : * The startup case, where repair is far ahead of replay, but there's
102 : only a single fork, or very few forks
103 : * The DoS case, where there are many forks, perhaps duplicate
104 : blocks, and we don't know which to prioritize yet, but we will
105 : execute some, and prune the rest later. This includes the case
106 : where we stop receiving transactions from some of the forks but
107 : don't know that the block has ended.
108 :
109 : In the normal case, there are few enough unreplayed blocks that it
110 : doesn't really matter how the staging lanes are used. For the
111 : startup case, the long linear chains of blocks can all be STAGED using
112 : the same lane with no performance degradation. In the DoS case, most
113 : of the forks will be UNSTAGED, and using some combination of
114 : replaying, cancelling, and demoting blocks, staging lanes can be freed
115 : up so that the canonical chain can emerge.
116 :
117 : Consider the following example of storing a fork tree in staging
118 : lanes:
119 : - Slot 10's parent is not specified
120 : - Slot 11's parent is slot 10
121 : - Slot 13's parent is slot 11
122 : - Slot 14's parent is also slot 11
123 :
124 : Since the caller chooses the staging lane, the caller may choose
125 : between
126 : Lane 0: 10 --> 11 --> 13
127 : Lane 1: 14
128 : and
129 : Lane 0: 10 --> 11 --> 14
130 : Lane 1: 13.
131 : or any of the various combinations that consume more staging lanes.
132 : Note that the concept of staging lanes is a performance optimization,
133 : not a safety feature. With the first arrangement, the caller cannot
134 : call get_next_ready on slot 13 in between slots 10 and 11, but
135 : there's no issue with calling it on slot 14 then, which would
136 : obviously result in an incorrect replay. It's ultimately the caller's
137 : responsibility to ensure correct replay. */
138 :
139 : #define FD_RDISP_MAX_DEPTH 0x7FFFFFUL /* 23 bit numbers, approx 8M */
140 2162664 : #define FD_RDISP_MAX_BLOCK_DEPTH 0xFFFFUL /* 16 bits */
141 395691 : #define FD_RDISP_UNSTAGED ULONG_MAX
142 :
143 : /* FD_RDISP_MAX_SCORE is the largest score that will be assigned to a
144 : transaction internally. Lower scores are better. It should be close
145 : to 1 to maximize the scoring function's dynamic range, but small
146 : enough that when added to relevant sized integers, it is distinct
147 : from the next integer. */
148 18 : #define FD_RDISP_MAX_SCORE 0.996f
149 :
150 : struct fd_rdisp;
151 : typedef struct fd_rdisp fd_rdisp_t;
152 :
153 : /* fd_rdisp is set up so that the tag of a block can be adjusted to
154 : account for differences in handling duplicate blocks/equivocation. */
155 : #define FD_RDISP_BLOCK_TAG_T ulong
156 :
157 : FD_PROTOTYPES_BEGIN
158 :
159 : /* fd_rdisp_{align,footprint} return the required alignment and
160 : footprint in bytes for a region of memory to be used as a dispatcher.
161 : depth is the maximum number of transaction indices that can be
162 : tracked at a time. Depth must be at least 2 and cannot exceed
163 : FD_RDISP_MAX_DEPTH. block_depth is the maximum number of blocks that
164 : this dispatcher can track. block_depth must be at least 4 and cannot
165 : exceed FD_RDISP_MAX_BLOCK_DEPTH. */
166 : ulong fd_rdisp_align ( void );
167 : ulong fd_rdisp_footprint( ulong depth, ulong block_depth );
168 :
169 :
170 : /* fd_rdisp_new formats a region of memory that satisfies the required
171 : footprint and alignment for use as a dispatcher. depth and
172 : block_depth are as explained in fd_rdisp_footprint. mem is a pointer
173 : to the first byte of a region of memory with the required alignment
174 : and footprint. seed is an arbitrary ulong that is used to determine
175 : a seed of various internal hash tables. On return, the caller will
176 : not be joined.
177 :
178 : fd_rdisp_join joins the caller to the dispatcher, enabling it for
179 : use. */
180 : void *
181 : fd_rdisp_new( void * mem,
182 : ulong depth,
183 : ulong block_depth,
184 : ulong seed );
185 :
186 : fd_rdisp_t *
187 : fd_rdisp_join( void * mem );
188 :
189 : /* fd_rdisp_suggest_staging_lane recommends a staging lane to use for a
190 : potential new block that has a parent block with block tag
191 : parent_block. duplicate is non-zero if this is not the first block
192 : we've seen for its slot.
193 :
194 : This function uses the following logic:
195 : 1. If it's a duplicate, suggest FD_RDISP_UNSTAGED
196 : 2. If parent is the last block in any existing staging lane, suggest
197 : that lane
198 : 3. If there is at least one free lane, suggest a free lane
199 : 4. Else, suggest FD_RDISP_UNSTAGED
200 : Note that this function does not add the block (use add_block) for
201 : that, and does not modify the state of the dispatcher. The caller
202 : should feel free to use or not use the suggested staging lane. */
203 : ulong
204 : fd_rdisp_suggest_staging_lane( fd_rdisp_t const * disp,
205 : FD_RDISP_BLOCK_TAG_T parent_block,
206 : int duplicate );
207 :
208 :
209 : /* fd_rdisp_add_block allocates a new block with the tag new_block from
210 : disp's internal pool. new_block must not be the invalid block tag
211 : value, and it must be distinct from all other values passed as
212 : new_block in all prior calls to fd_rdisp_add_block.
213 :
214 : staging_lane must be either [0,4) or FD_RDISP_UNSTAGED. If
215 : staging_lane is FD_RDISP_UNSTAGED, the block will be UNSTAGED (see
216 : the long comment at the beginning of this header), schedule-ready,
217 : and insert-ready.
218 : If staging_lane is in [0, 4), the block will be STAGED, and it will
219 : be insert-ready. If the specified staging lane contained any blocks
220 : at the time of the call, the last one will no longer be insert-ready,
221 : making this the only insert-ready block in the lane. If the
222 : specified staging lane did not contain any blocks at the time of the
223 : call, then the newly added block will also be schedule-ready.
224 :
225 : On successful return, the tag new_block will be usable for other
226 : functions that take a block tag block.
227 :
228 : Returns 0 on success, and -1 on error, which can only happen if out
229 : of resources (the number of unremoved blocks is greater than or equal
230 : to the block_depth) or if new_block was already known. */
231 : int
232 : fd_rdisp_add_block( fd_rdisp_t * disp,
233 : FD_RDISP_BLOCK_TAG_T new_block,
234 : ulong staging_lane );
235 :
236 : /* fd_rdisp_remove_block deallocates a previously-allocated block with
237 : the block tag block, freeing all resources associated with it. block
238 : must be empty (not contain any transactions in the PENDING, READY,
239 : DISPATCHED, or ZOMBIE states), and schedule-ready.
240 : Returns 0 on success, and -1 if block is not known. After a
241 : successful return, the block tag block will not be known. */
242 : int
243 : fd_rdisp_remove_block( fd_rdisp_t * disp,
244 : FD_RDISP_BLOCK_TAG_T block );
245 :
246 :
247 : /* fd_rdisp_abandon_block is similar to remove_block, but works when the
248 : block contains transactions. It immediately transitions all
249 : transactions part of the block to FREE, and then removes the block as
250 : in fd_rdisp_remove_block. Note that if a transaction is DISPATCHED
251 : at the time of the call complete_txn should NOT be called on that
252 : transaction index when it completes. The specified block must be
253 : schedule-ready.
254 :
255 : In V1 of the dispatcher, this only works if there are no DISPATCHED
256 : transactions.
257 :
258 : Returns 0 on success, and -1 if block is not known. After a
259 : successful return, the block tag block will not be known. */
260 : int
261 : fd_rdisp_abandon_block( fd_rdisp_t * disp,
262 : FD_RDISP_BLOCK_TAG_T block );
263 :
264 :
265 : /* fd_rdisp_{promote,demote}_block modify whether a block is STAGED or
266 : UNSTAGED. Specifically, promote_block promotes the specified block
267 : from UNSTAGED to STAGED, using the specified staging_lane.
268 : demote_block demotes the specified block from STAGED to UNSTAGED.
269 : disp must be a valid local join. If the block tag block is not
270 : known, or is not in the requisite state (UNSTAGED from promote,
271 : STAGED for demote), returns -1.
272 :
273 : When promote_block promotes the specified block, it is placed at the
274 : end of the linear chain in the specified staging_lane. That means
275 : the operation is as if abandon_block were called on the specified
276 : block, then add_block with the specified staging_lane, and then all
277 : transactions in the PENDING and READY states in this block were
278 : re-added in the same order they were originally added. It is
279 : undefined behavior if the specified block contains any transactions
280 : in the DISPATCHED stage. As in add_block, upon successful return,
281 : the specified block will be insert-ready, but will only be
282 : schedule-ready if the specified staging lane was empty at the time of
283 : the call.
284 :
285 : demote_block has the additional requirement that the specified block
286 : must be schedule-ready and empty, that is, not containing any
287 : transactions in the PENDING, READY, or DISPATCHED states. */
288 :
289 : int
290 : fd_rdisp_promote_block( fd_rdisp_t * disp,
291 : FD_RDISP_BLOCK_TAG_T block,
292 : ulong staging_lane );
293 : int
294 : fd_rdisp_demote_block( fd_rdisp_t * disp,
295 : FD_RDISP_BLOCK_TAG_T block );
296 :
297 :
298 : /* fd_rdisp_rekey_block renames the block with tag old_tag so that it
299 : has tag new_tag instead. The block retains all transactions, its
300 : STAGED/UNSTAGED state, etc. On successful return, tag old_tag will
301 : no longer be a known tag, and new_tag must be used in any future
302 : calls to refer to the block previously known as old_tag.
303 :
304 : disp must be a valid local join. new_tag must not be a known tag,
305 : but old_tag must be a known tag.
306 :
307 : Return 0 on success and -1 on error. The only error cases are if
308 : new_tag is already a known tag or old_tag is not a known tag. */
309 : int
310 : fd_rdisp_rekey_block( fd_rdisp_t * disp,
311 : FD_RDISP_BLOCK_TAG_T new_tag,
312 : FD_RDISP_BLOCK_TAG_T old_tag );
313 :
314 : /* fd_rdisp_add_txn adds a transaction to the block with tag
315 : insert_block in serial order. That means that this dispatcher will
316 : ensure this transaction appears to execute after each transaction
317 : added to this block in a prior call.
318 :
319 : insert_block must be a known block that is insert-ready. txn,
320 : payload, and alts describe the transaction to be added. txn must be
321 : the result of parsing payload, and alts contains the expansion and
322 : selection of the address lookup tables mentioned in the transaction
323 : (i.e. all the writable accounts followed by all the read-only
324 : accounts). alts may be NULL, even if the transaction specifies that
325 : it loads accounts from an address lookup table; in this case,
326 : addresses from ALTs are ignored. There must be no duplicate accounts
327 : in the transaction to be added.
328 :
329 : Shockingly, this dispatcher does not retain any read interest (much
330 : less write interest) in the transaction (txn, payload, or alts). On
331 : success, it returns a transaction index that was previously in the
332 : FREE state. This API is designed to facilitate a model of use where
333 : the replay tile copies the incoming transaction to a region of
334 : private memory, adds it to this dispatcher, and then copies it (using
335 : non-temporal stores) to the output dcache at a location determined by
336 : the returned index. Although there are two memcpys in this approach,
337 : it should result in fewer cache misses.
338 :
339 : If serializing is non-zero, this transaction will be a serialization
340 : point: all transactions added prior to this one must complete before
341 : this transaction can be scheduled, and this transaction must complete
342 : before any subsequently added transactions can be scheduled. This is
343 : not good for performance, but is useful for the rare case when
344 : repair/turbine is several slots ahead of replay, and a transaction
345 : loads some accounts from an address lookup table, but we haven't
346 : executed the transaction to populate that part of the address lookup
347 : table yet. This is the primary use for alts==NULL.
348 :
349 : Returns 0 and does not add the transaction on failure. Fails if
350 : there were no free transaction indices, if the block with tag
351 : insert_block did not exist, or if it was not schedule-ready.
352 :
353 : At the time this function returns, the returned transaction index
354 : will be in the PENDING or READY state, depending on whether it
355 : conflicts with something previously inserted. */
356 : ulong
357 : fd_rdisp_add_txn( fd_rdisp_t * disp,
358 : FD_RDISP_BLOCK_TAG_T insert_block,
359 : fd_txn_t const * txn,
360 : uchar const * payload,
361 : fd_acct_addr_t const * alts,
362 : int serializing );
363 :
364 : /* fd_rdisp_get_next_ready returns the transaction index of a READY
365 : transaction that was inserted with block tag schedule_block if one
366 : exists, and 0 otherwise. The block with the tag schedule_block must
367 : be schedule-ready.
368 :
369 : If there are multiple READY transactions, which exact one is returned
370 : is arbitrary. That said, this function does make some effort to pick
371 : one that (upon completion) will unlock more parallelism. disp must
372 : be a valid local join. At the time this function returns, the
373 : returned transaction index (if nonzero) will transition to the
374 : DISPATCHED state. */
375 : ulong
376 : fd_rdisp_get_next_ready( fd_rdisp_t * disp,
377 : FD_RDISP_BLOCK_TAG_T schedule_block );
378 :
379 : /* fd_rdisp_complete_txn notifies the dispatcher that the specified
380 : transaction (which must have been in the DISPATCHED state) has
381 : completed. Logs warning and returns on error (invalid txn_idx, not
382 : in DISPATCHED state). This function may cause other transactions to
383 : transition from PENDING to READY.
384 :
385 : At the time this function returns, the specified transaction index
386 : will be in the FREE state, if reclaim!=0. Otherwise, if reclaim==0,
387 : the specified transaction index will be in the ZOMBIE state. A
388 : ZOMBIE transaction has the exact same effect as a FREE transaction on
389 : causing other transactions to transition from PENDING to READY.
390 : However, the dispatcher will not reclaim the specified transaction
391 : index, until a future invocation of fd_rdisp_complete_txn where
392 : reclaim!=0. This is useful when there is non-execution work to be
393 : done asynchronously for the transaction, but the caller would like to
394 : unblock the execution of transactions that depend on this one. */
395 : void
396 : fd_rdisp_complete_txn( fd_rdisp_t * disp,
397 : ulong txn_idx,
398 : int reclaim );
399 :
400 :
401 : typedef struct {
402 : FD_RDISP_BLOCK_TAG_T schedule_ready_block;
403 : FD_RDISP_BLOCK_TAG_T insert_ready_block;
404 : } fd_rdisp_staging_lane_info_t;
405 :
406 : /* fd_rdisp_staging_lane_info copies the current staging lane info to
407 : out. Returns a 4-bit bitset, where bit i being set means that
408 : staging lane i is occupied. If staging lane i is occupied, then
409 : out_sched[i] is populated. */
410 : ulong
411 : fd_rdisp_staging_lane_info( fd_rdisp_t const * disp,
412 : fd_rdisp_staging_lane_info_t out_sched[ static 4 ] );
413 :
414 : /* fd_rdisp_verify does some light verification and internal consistency
415 : checks of some internal data structures. Aborts with an error
416 : message if anything fails verification. disp is a pointer to a valid
417 : local join, and scratch is a pointer to a region of scratch memory
418 : with at least depth+1 elements that will be clobbered (its contents
419 : at the time of the function call are ignored). */
420 : void
421 : fd_rdisp_verify( fd_rdisp_t const * disp,
422 : uint * scratch );
423 :
424 : void *
425 : fd_rdisp_leave( fd_rdisp_t * disp );
426 :
427 : void *
428 : fd_rdisp_delete( void * mem );
429 :
430 : FD_PROTOTYPES_END
431 :
432 : #endif /* HEADER_fd_src_discof_replay_fd_rdisp_h */
|
