Line data Source code
1 : #ifndef HEADER_fd_src_ballet_pack_fd_pack_h
2 : #define HEADER_fd_src_ballet_pack_fd_pack_h
3 :
4 : /* fd_pack defines methods that prioritizes Solana transactions,
5 : selecting a subset (potentially all) and ordering them to attempt to
6 : maximize the overall profitability of the validator. */
7 :
8 : #include "../fd_ballet_base.h"
9 : #include "../txn/fd_txn.h"
10 : #include "fd_est_tbl.h"
11 : #include "fd_microblock.h"
12 :
13 0 : #define FD_PACK_ALIGN (128UL)
14 :
15 43839 : #define FD_PACK_MAX_BANK_TILES 62UL
16 :
17 : /* NOTE: THE FOLLOWING CONSTANTS ARE CONSENSUS CRITICAL AND CANNOT BE
18 : CHANGED WITHOUT COORDINATING WITH ANZA. */
19 15237 : #define FD_PACK_MAX_COST_PER_BLOCK (48000000UL)
20 315 : #define FD_PACK_MAX_VOTE_COST_PER_BLOCK (36000000UL)
21 306 : #define FD_PACK_MAX_WRITE_COST_PER_ACCT (12000000UL)
22 27145119 : #define FD_PACK_FEE_PER_SIGNATURE (5000UL) /* In lamports */
23 :
24 : /* Each block is limited to 32k parity shreds. We don't want pack to
25 : produce a block with so many transactions we can't shred it, but the
26 : correspondence between transactions and parity shreds is somewhat
27 : complicated, so we need to use conservative limits.
28 :
29 : Except for the final batch in the block, the current version of the
30 : shred tile shreds microblock batches of size (25431, 63671] bytes,
31 : including the microblock headers, but excluding the microblock count.
32 : The worst case size by bytes/parity shred is a 25871 byte microblock
33 : batch, which produces 31 parity shreds. The final microblock batch,
34 : however, may be as bad as 48 bytes triggering the creation of 17
35 : parity shreds. This gives us a limit of floor((32k - 17)/31)*25871 +
36 : 48 = 27,319,824 bytes.
37 :
38 : To get this right, the pack tile needs to add in the 48-byte
39 : microblock headers for each microblock, and we also need to subtract
40 : out the tick bytes, which aren't known until PoH initialization is
41 : complete.
42 :
43 : Note that the number of parity shreds in each FEC set is always at
44 : least as many as the number of data shreds, so we don't need to
45 : consider the data shreds limit. */
46 3 : #define FD_PACK_MAX_DATA_PER_BLOCK (((32UL*1024UL-17UL)/31UL)*25871UL + 48UL)
47 :
48 : /* Optionally allow up to 1M shreds per block for benchmarking. */
49 0 : #define LARGER_MAX_DATA_PER_BLOCK (((32UL*32UL*1024UL-17UL)/31UL)*25871UL + 48UL)
50 :
51 : /* ---- End consensus-critical constants */
52 :
53 27145128 : #define FD_TXN_P_FLAGS_IS_SIMPLE_VOTE (1U)
54 25482 : #define FD_TXN_P_FLAGS_SANITIZE_SUCCESS (2U)
55 17943 : #define FD_TXN_P_FLAGS_EXECUTE_SUCCESS (4U)
56 :
57 :
58 : /* The Solana network and Firedancer implementation details impose
59 : several limits on what pack can produce. These limits are grouped in
60 : this one struct fd_pack_limits_t, which is just a convenient way to
61 : pass them around. The limits listed below are arithmetic limits.
62 : The limits imposed by practical constraints are almost certainly
63 : much, much tighter. */
64 : struct fd_pack_limits {
65 : /* max_{cost, vote_cost}_per_block, max_write_cost_per_acct are
66 : consensus-critical limits and must be agreed on cluster-wide. A
67 : block that consumes more than max_cost_per_block cost units
68 : (closely related to, but not identical to CUs) in total is invalid.
69 : Similarly, a block where the sum of the cost of all vote
70 : transactions exceeds max_vote_cost_per_block cost units is invalid.
71 : Similarly, a block in where the sum of the cost of all transactions
72 : that write to a given account exceeds max_write_cost_per_acct is
73 : invalid. */
74 : ulong max_cost_per_block; /* in [0, ULONG_MAX) */
75 : ulong max_vote_cost_per_block; /* in [0, max_cost_per_block] */
76 : ulong max_write_cost_per_acct; /* in [0, max_cost_per_block] */
77 :
78 : /* max_data_bytes_per_block is derived from consensus-critical limits
79 : on the number of shreds in a block, but is not directly enforced.
80 : Separation of concerns means that it's not a good idea for pack to
81 : know exactly how the block will be shredded, but at the same time,
82 : we don't want to end up in a situation where we produced a block
83 : that had too many shreds, because the shred tile's only recourse
84 : would be to kill the block. To address this, pack limits the size
85 : of the data it puts into the block to a limit that we can prove
86 : will never cause the shred tile to produce too many shreds.
87 :
88 : This limit includes transaction and microblock headers for
89 : non-empty microblocks that pack produces. */
90 : ulong max_data_bytes_per_block; /* in [0, ULONG_MAX - 183] */
91 :
92 : /* max_txn_per_microblock and max_microblocks_per_block are
93 : Firedancer-imposed implementation limits to bound the amount of
94 : memory consumption that pack uses. Pack will produce microblocks
95 : with no more than max_txn_per_microblock transactions.
96 : Additionally, once pack produces max_microblocks_per_block
97 : non-empty microblocks in a block, all subsequent attempts to
98 : schedule a microblock will return an empty microblock until
99 : fd_pack_end_block is called. */
100 : ulong max_txn_per_microblock; /* in [0, 16777216] */
101 : ulong max_microblocks_per_block; /* in [0, 1e12) */
102 :
103 : };
104 : typedef struct fd_pack_limits fd_pack_limits_t;
105 :
106 :
107 : /* Forward declare opaque handle */
108 : struct fd_pack_private;
109 : typedef struct fd_pack_private fd_pack_t;
110 :
111 : /* fd_pack_{align,footprint} return the required alignment and
112 : footprint in bytes for a region of memory to be used as a pack
113 : object.
114 :
115 : pack_depth sets the maximum number of pending transactions that pack
116 : stores and may eventually schedule. pack_depth must be at least 4.
117 :
118 : bank_tile_cnt sets the number of bank tiles to which this pack object
119 : can schedule transactions. bank_tile_cnt must be in [1,
120 : FD_PACK_MAX_BANK_TILES].
121 :
122 : limits sets various limits for the blocks and microblocks that pack
123 : can produce. */
124 :
125 0 : FD_FN_CONST static inline ulong fd_pack_align ( void ) { return FD_PACK_ALIGN; }
126 :
127 : FD_FN_PURE ulong
128 : fd_pack_footprint( ulong pack_depth,
129 : ulong bank_tile_cnt,
130 : fd_pack_limits_t const * limits );
131 :
132 :
133 : /* fd_pack_new formats a region of memory to be suitable for use as a
134 : pack object. mem is a non-NULL pointer to a region of memory in the
135 : local address space with the required alignment and footprint.
136 : pack_depth, bank_tile_cnt, and limits are as above. rng is a local
137 : join to a random number generator used to perturb estimates.
138 :
139 : Returns `mem` (which will be properly formatted as a pack object) on
140 : success and NULL on failure. Logs details on failure. The caller
141 : will not be joined to the pack object when this function returns. */
142 : void * fd_pack_new( void * mem,
143 : ulong pack_depth, ulong bank_tile_cnt, fd_pack_limits_t const * limits,
144 : fd_rng_t * rng );
145 :
146 : /* fd_pack_join joins the caller to the pack object. Every successful
147 : join should have a matching leave. Returns mem. */
148 : fd_pack_t * fd_pack_join( void * mem );
149 :
150 :
151 : /* fd_pack_avail_txn_cnt returns the number of transactions that this
152 : pack object has available to schedule but that have not been
153 : scheduled yet. pack must be a valid local join. The return value
154 : will be in [0, pack_depth). */
155 :
156 : /* For performance reasons, implement this here. The offset is STATIC_ASSERTed
157 : in fd_pack.c. */
158 43179 : #define FD_PACK_PENDING_TXN_CNT_OFF 64
159 : FD_FN_PURE static inline ulong
160 43179 : fd_pack_avail_txn_cnt( fd_pack_t const * pack ) {
161 43179 : return *((ulong const *)((uchar const *)pack + FD_PACK_PENDING_TXN_CNT_OFF));
162 43179 : }
163 :
164 : /* fd_pack_current_block_cost returns the number of CUs that have been
165 : scheduled in the current block, net of any rebates. It should be
166 : between 0 and the specified value of max_cost_per_block, but it can
167 : be slightly higher due to temporary cost model nonsense. Due to
168 : rebates, this number may decrease as the block progresses. pack must
169 : be a valid local join. */
170 : FD_FN_PURE ulong fd_pack_current_block_cost( fd_pack_t const * pack );
171 :
172 : /* fd_pack_bank_tile_cnt: returns the value of bank_tile_cnt provided in
173 : pack when the pack object was initialized with fd_pack_new. pack
174 : must be a valid local join. The result will be in [1,
175 : FD_PACK_MAX_BANK_TILES]. */
176 : FD_FN_PURE ulong fd_pack_bank_tile_cnt( fd_pack_t const * pack );
177 :
178 : /* fd_pack_set_block_limits: Updates the limits provided fd_pack_new to
179 : the new values. Any future microblocks produced by this pack object
180 : will not cause a block to have more than max_microblocks_per_block
181 : non-empty microblocks or more than max_data_bytes_per_block data
182 : bytes (counting microblock headers as before). Limits are inclusive,
183 : as per usual (i.e. a block may have exactly
184 : max_microblocks_per_block microblocks, but not more). pack must be
185 : a valid local join.
186 :
187 : The typical place to call this is immediately after
188 : fd_pack_end_block; if this is called after some microblocks have been
189 : produced for the current block, and the current block already exceeds
190 : the limits, all the remaining microblocks in the block will be empty,
191 : but the call is valid. */
192 : void fd_pack_set_block_limits( fd_pack_t * pack, ulong max_microblocks_per_block, ulong max_data_bytes_per_block );
193 :
194 : /* Return values for fd_pack_insert_txn_fini: Non-negative values
195 : indicate the transaction was accepted and may be returned in a future
196 : microblock. Negative values indicate that the transaction was
197 : rejected and will never be returned in a future microblock.
198 : Transactions can be rejected through no fault of their own, so it
199 : doesn't necessarily imply bad behavior.
200 :
201 : The non-negative (success) codes are essentially a bitflag of two
202 : bits:
203 : * whether the transaction met the criteria for a simple vote or not,
204 : * whether this transaction replaced a previously accepted, low
205 : priority transaction, rather than being accepted in addition to all
206 : the previously accepted transactions. Since pack maintains a heap
207 : with a fixed max size of pack_depth, replacing transaction is
208 : necessary whenever the heap is full.
209 :
210 : The negative (failure) codes are a normal enumeration (not a
211 : bitflag).
212 : * PRIORITY: pack's heap was full and the transaction's priority was
213 : lower than the worst currently accepted transaction.
214 : * DUPLICATE: the transaction is a duplicate of a currently accepted
215 : transaction.
216 : * UNAFFORDABLE: the fee payer could not afford the transaction fee
217 : (not yet implemented).
218 : * ADDR_LUT: the transaction tried to load an account from an address
219 : lookup table, which is not yet supported.
220 : * EXPIRED: the transaction was already expired upon insertion based
221 : on the provided value of expires_at compared to the last call to
222 : fd_pack_expire_before.
223 : * TOO_LARGE: the transaction requested too many CUs and would never
224 : be scheduled if it had been accepted.
225 : * ACCOUNT_CNT: the transaction tried to load more than 64 account
226 : addresses.
227 : * DUPLICATE_ACCT: the transaction included an account address twice
228 : in its list of account addresses to load.
229 : * ESTIMATION_FAIL: estimation of the transaction's compute cost and
230 : fee failed, typically because the transaction contained a
231 : malformed ComputeBudgetProgram instruction.
232 : * WRITES_SYSVAR: the transaction attempts to write-lock a sysvar.
233 : Write-locking a sysvar can cause heavy contention. Agave
234 : solves this by downgrading these to read locks, but we instead
235 : solve it by refusing to pack such transactions.
236 :
237 : NOTE: The corresponding enum in metrics.xml must be kept in sync
238 : with any changes to these return values. */
239 0 : #define FD_PACK_INSERT_ACCEPT_VOTE_REPLACE ( 3)
240 494592 : #define FD_PACK_INSERT_ACCEPT_NONVOTE_REPLACE ( 2)
241 37596 : #define FD_PACK_INSERT_ACCEPT_VOTE_ADD ( 1)
242 13040262 : #define FD_PACK_INSERT_ACCEPT_NONVOTE_ADD ( 0)
243 0 : #define FD_PACK_INSERT_REJECT_PRIORITY ( -1)
244 3 : #define FD_PACK_INSERT_REJECT_DUPLICATE ( -2)
245 0 : #define FD_PACK_INSERT_REJECT_UNAFFORDABLE ( -3)
246 : #define FD_PACK_INSERT_REJECT_ADDR_LUT ( -4)
247 12 : #define FD_PACK_INSERT_REJECT_EXPIRED ( -5)
248 0 : #define FD_PACK_INSERT_REJECT_TOO_LARGE ( -6)
249 3 : #define FD_PACK_INSERT_REJECT_ACCOUNT_CNT ( -7)
250 3 : #define FD_PACK_INSERT_REJECT_DUPLICATE_ACCT ( -8)
251 3 : #define FD_PACK_INSERT_REJECT_ESTIMATION_FAIL ( -9)
252 87 : #define FD_PACK_INSERT_REJECT_WRITES_SYSVAR (-10)
253 0 : #define FD_PACK_INSERT_REJECT_BUNDLE_BLACKLIST (-11)
254 :
255 : /* The FD_PACK_INSERT_{ACCEPT, REJECT}_* values defined above are in the
256 : range [-FD_PACK_INSERT_RETVAL_OFF,
257 : -FD_PACK_INSERT_RETVAL_OFF+FD_PACK_INSERT_RETVAL_CNT ) */
258 0 : #define FD_PACK_INSERT_RETVAL_OFF 11
259 0 : #define FD_PACK_INSERT_RETVAL_CNT 15
260 :
261 : FD_STATIC_ASSERT( FD_PACK_INSERT_REJECT_BUNDLE_BLACKLIST>=-FD_PACK_INSERT_RETVAL_OFF, pack_retval );
262 : FD_STATIC_ASSERT( FD_PACK_INSERT_ACCEPT_VOTE_REPLACE<FD_PACK_INSERT_RETVAL_CNT-FD_PACK_INSERT_RETVAL_OFF, pack_retval );
263 :
264 : /* fd_pack_insert_txn_{init,fini,cancel} execute the process of
265 : inserting a new transaction into the pool of available transactions
266 : that may be scheduled by the pack object.
267 :
268 : fd_pack_insert_txn_init returns a piece of memory from the txnmem
269 : region where the transaction should be stored. The lifetime of this
270 : memory is managed by fd_pack as explained below.
271 :
272 : Every call to fd_pack_insert_init must be paired with a call to
273 : exactly one of _fini or _cancel. Calling fd_pack_insert_txn_fini
274 : finalizes the transaction insert process and makes the newly-inserted
275 : transaction available for scheduling. Calling
276 : fd_pack_insert_txn_cancel aborts the transaction insertion process.
277 : The txn pointer passed to _fini or _cancel must come from the most
278 : recent call to _init.
279 :
280 : The caller of these methods should not retain any read or write
281 : interest in the transaction after _fini or _cancel have been called.
282 :
283 : expires_at (for _fini only) bounds the lifetime of the inserted
284 : transaction. No particular unit is prescribed, and it need not be
285 : higher than the previous call to txn_fini. If fd_pack_expire_before
286 : has been previously called with a value larger (strictly) than the
287 : provided expires_at, the transaction will be rejected with EXPIRED.
288 : See fd_pack_expire_before for more details.
289 :
290 : pack must be a local join of a pack object. From the caller's
291 : perspective, these functions cannot fail, though pack may reject a
292 : transaction for a variety of reasons. fd_pack_insert_txn_fini
293 : returns one of the FD_PACK_INSERT_ACCEPT_* or FD_PACK_INSERT_REJECT_*
294 : codes explained above.
295 : */
296 : fd_txn_e_t * fd_pack_insert_txn_init ( fd_pack_t * pack );
297 : int fd_pack_insert_txn_fini ( fd_pack_t * pack, fd_txn_e_t * txn, ulong expires_at );
298 : void fd_pack_insert_txn_cancel( fd_pack_t * pack, fd_txn_e_t * txn );
299 :
300 :
301 : /* fd_pack_schedule_next_microblock schedules transactions to form a
302 : microblock, which is a set of non-conflicting transactions.
303 :
304 : pack must be a local join of a pack object. Transactions part of the
305 : scheduled microblock are copied to out in no particular order. The
306 : cumulative cost of these transactions will not exceed total_cus, and
307 : the number of transactions will not exceed the value of
308 : max_txn_per_microblock given in fd_pack_new.
309 :
310 : The requested_cus field of each transaction will be populated with
311 : the requested execution CUs, which is different from the total cost
312 : CUs used by `total_cus`. The flags field will be set to 0 or
313 : FD_TXN_P_FLAGS_IS_SIMPLE_VOTE.
314 :
315 : The block will not contain more than
316 : vote_fraction*max_txn_per_microblock votes, and votes in total will
317 : not consume more than vote_fraction*total_cus of the microblock.
318 :
319 : Returns the number of transactions in the scheduled microblock. The
320 : return value may be 0 if there are no eligible transactions at the
321 : moment. */
322 :
323 : ulong fd_pack_schedule_next_microblock( fd_pack_t * pack, ulong total_cus, float vote_fraction, ulong bank_tile, fd_txn_p_t * out );
324 :
325 :
326 : /* fd_pack_rebate_cus adjusts the compute unit accounting for the
327 : specified transactions to take into account the actual consumed CUs
328 : after execution. When a transaction is scheduled by
329 : schedule_next_microblock, pack assumes that it uses all the CUs it
330 : requests for the purposes of several CU limits. If it doesn't use
331 : all the requested CUs, this function "rebates" them to pack so that
332 : they can be consumed by a different transaction in the block.
333 :
334 : pack must be a valid local join of a pack object. txns, indexed [0,
335 : txn_cnt), should point to the first of txn_cnt transactions scheduled
336 : in a microblock by pack. Although txns does not need to be the same
337 : specific pointer passed to out in a call to schedule_next_microblock,
338 : it should point to the same data as returned by a call to
339 : schedule_next_microblock, other than flags and executed_cus fields.
340 : Similarly, txn_cnt should be the return value of the corresponding
341 : prior call to schedule_next_microblock. txn_cnt==0 is okay and a
342 : no-op. txns==NULL is okay if txn_cnt==0.
343 :
344 : This function reads the requested_cus and executed_cus fields of the
345 : transactions in txns. It expects that both refer to just execution
346 : CUs, and do not include e.g. write lock cost units.
347 :
348 : IMPORTANT: CU limits are reset at the end of each block, so this
349 : should not be called for transactions from a prior block.
350 : Specifically, there must not be a call to fd_pack_end_block between
351 : the call to schedule_next_microblock this is paired with and the call
352 : to rebate_cus.
353 :
354 : This function operates independently of microblock_complete. In
355 : general, you probably need to call both. microblock_complete must be
356 : called before scheduling another microblock to that bank tile, while
357 : rebate_cus is optional and has much more relaxed ordering
358 : constraints. The restriction about intervening calls to end_block
359 : and that this must come after schedule_next_microblock are the only
360 : ordering constraints. */
361 : void fd_pack_rebate_cus( fd_pack_t * pack, fd_txn_p_t const * txns, ulong txn_cnt );
362 :
363 : /* fd_pack_microblock_complete signals that the bank_tile with index
364 : bank_tile has completed its previously scheduled microblock. This
365 : permits the scheduling of transactions that conflict with the
366 : previously scheduled microblock. It is safe to call this multiple
367 : times after a microblock or even if bank_tile does not have a
368 : previously scheduled; in this case, the function will return 0 and
369 : act as a no-op. Returns 1 if the bank_tile had an outstanding,
370 : previously scheduled microblock to mark as completed. */
371 : int fd_pack_microblock_complete( fd_pack_t * pack, ulong bank_tile );
372 :
373 : /* fd_pack_expire_before deletes all available transactions with
374 : expires_at values strictly less than expire_before. pack must be a
375 : local join of a pack object. Returns the number of transactions
376 : deleted. Subsequent calls to fd_pack_expire_before with the same or
377 : a smaller value are no-ops. */
378 : ulong fd_pack_expire_before( fd_pack_t * pack, ulong expire_before );
379 :
380 : /* fd_pack_delete_txn removes a transaction (identified by its first
381 : signature) from the pool of available transactions. Returns 1 if the
382 : transaction was found (and then removed) and 0 if not. */
383 : int fd_pack_delete_transaction( fd_pack_t * pack, fd_ed25519_sig_t const * sig0 );
384 :
385 : /* fd_pack_end_block resets some state to prepare for the next block.
386 : Specifically, the per-block limits are cleared and transactions in
387 : the microblocks scheduled after the call to this function are allowed
388 : to conflict with transactions in microblocks scheduled before the
389 : call to this function, even within gap microblocks. */
390 : void fd_pack_end_block( fd_pack_t * pack );
391 :
392 :
393 : /* fd_pack_clear_all resets the state associated with this pack object.
394 : All pending transactions are removed from the pool of available
395 : transactions and all limits are reset. */
396 : void fd_pack_clear_all( fd_pack_t * pack );
397 :
398 :
399 : /* fd_pack_metrics_write writes period metric values to the metrics
400 : system. pack must be a valid local join. */
401 : void
402 : fd_pack_metrics_write( fd_pack_t const * pack );
403 :
404 :
405 : /* fd_pack_leave leaves a local join of a pack object. Returns pack. */
406 : void * fd_pack_leave( fd_pack_t * pack );
407 : /* fd_pack_delete unformats a memory region used to store a pack object
408 : and returns ownership of the memory to the caller. Returns mem. */
409 : void * fd_pack_delete( void * mem );
410 :
411 : /* fd_pack_verify (for debugging use primarily) checks to ensure several
412 : invariants are satisfied. scratch must point to the first byte of a
413 : piece of memory meeting the same alignment and footprint constraints
414 : as pack. Returns 0 on success and a negative value on failure
415 : (logging a warning with details). */
416 : int fd_pack_verify( fd_pack_t * pack, void * scratch );
417 :
418 : FD_PROTOTYPES_END
419 : #endif /* HEADER_fd_src_ballet_pack_fd_pack_h */
|
