Line data Source code
1 : #ifndef HEADER_fd_src_disco_pack_fd_pack_cost_h
2 : #define HEADER_fd_src_disco_pack_fd_pack_cost_h
3 :
4 : #include "../../ballet/fd_ballet_base.h"
5 : #include "fd_compute_budget_program.h"
6 : #include "../../flamenco/runtime/fd_system_ids_pp.h"
7 : #include "../../ballet/txn/fd_txn.h"
8 :
9 : /* The functions in this header implement the transaction cost model
10 : that is soon to be part of consensus.
11 : The cost model consists of several components:
12 : * per-signature cost: The costs associated with transaction
13 : signatures + signatures from precompiles (ED25519 + SECP256*)
14 : * per-write-lock cost: cost assiciated with aquiring write locks
15 : for writable accounts listed in the transaction.
16 : * instruction data length cost: The fixed cost for each instruction
17 : data byte in the transaction payload.
18 : * built-in execution cost: The fixed cost associated with "builtin"
19 : instructions. "What are builtins" is defined here:
20 : https://github.com/anza-xyz/agave/blob/1baa4033e0d2d4175373f07b73ddda2f3cc0a8d6/builtins-default-costs/src/lib.rs#L120-L200
21 : After SIMD 170, all builtins have a fixed cost of 3000 cus.
22 : * BPF execution cost: The costs assosiated with any instruction
23 : that is not a builtin. This value comes from the VM after
24 : transaction execution.
25 : * loaded accounts data cost: Costs associated with all the account
26 : data loaded from the chain. This value is known in the
27 : transaction loading stage, after accounts data is loaded.
28 : These are all summed to determine the total transaction cost. */
29 :
30 : /* The exception to these costs are simple vote transactions, incur a
31 : fixed cost regardless of their actual execution cost or account data
32 : loaded. */
33 :
34 : /* To compute the built-in cost, we need to check a table. The table
35 : is known ahead of time though, so we can build a perfect hash
36 : table for performance.
37 : The values of the table are based on https://github.com/
38 : solana-labs/solana/blob/9fb105c801e2999a24f0773443d6164e30c9ff0c/
39 : runtime/src/block_cost_limits.rs#L34-L47 . */
40 :
41 :
42 :
43 : struct __attribute__((aligned(32))) fd_pack_builtin_prog_cost {
44 : uchar program_id[32];
45 : ulong cost_per_instr;
46 : };
47 : typedef struct fd_pack_builtin_prog_cost fd_pack_builtin_prog_cost_t;
48 :
49 : #define MAP_PERFECT_NAME fd_pack_builtin
50 : #define MAP_PERFECT_LG_TBL_SZ 4
51 : #define MAP_PERFECT_T fd_pack_builtin_prog_cost_t
52 : #define MAP_PERFECT_HASH_C 478U
53 : #define MAP_PERFECT_KEY program_id
54 : #define MAP_PERFECT_KEY_T fd_acct_addr_t const *
55 : #define MAP_PERFECT_ZERO_KEY (0,0,0,0, 0,0,0,0, 0,0,0,0, 0,0,0,0, 0,0,0,0, 0,0,0,0, 0,0,0,0, 0,0,0,0)
56 : #define MAP_PERFECT_COMPLEX_KEY 1
57 9690993 : #define MAP_PERFECT_KEYS_EQUAL(k1,k2) (!memcmp( (k1), (k2), 32UL ))
58 :
59 64150497 : #define PERFECT_HASH( u ) (((478U*(u))>>28)&0xFU)
60 :
61 : #define MAP_PERFECT_HASH_PP( a00,a01,a02,a03,a04,a05,a06,a07,a08,a09,a10,a11,a12,a13,a14,a15, \
62 : a16,a17,a18,a19,a20,a21,a22,a23,a24,a25,a26,a27,a28,a29,a30,a31) \
63 : PERFECT_HASH( (a08 | (a09<<8) | (a10<<16) | (a11<<24)) )
64 9690993 : #define MAP_PERFECT_HASH_R( ptr ) PERFECT_HASH( fd_uint_load_4( (uchar const *)ptr->b + 8UL ) )
65 :
66 :
67 : /* The cost model estimates 200,000 CUs for builtin programs that were migrated to BPF */
68 : #define MAP_PERFECT_0 ( VOTE_PROG_ID ), .cost_per_instr= FD_COMPUTE_BUDGET_MAX_BUILTIN_CU_LIMIT
69 : #define MAP_PERFECT_1 ( SYS_PROG_ID ), .cost_per_instr= FD_COMPUTE_BUDGET_MAX_BUILTIN_CU_LIMIT
70 : #define MAP_PERFECT_2 ( COMPUTE_BUDGET_PROG_ID ), .cost_per_instr= FD_COMPUTE_BUDGET_MAX_BUILTIN_CU_LIMIT
71 : #define MAP_PERFECT_3 ( BPF_UPGRADEABLE_PROG_ID ), .cost_per_instr= FD_COMPUTE_BUDGET_MAX_BUILTIN_CU_LIMIT
72 : #define MAP_PERFECT_4 ( BPF_LOADER_1_PROG_ID ), .cost_per_instr= FD_COMPUTE_BUDGET_MAX_BUILTIN_CU_LIMIT
73 : #define MAP_PERFECT_5 ( BPF_LOADER_2_PROG_ID ), .cost_per_instr= FD_COMPUTE_BUDGET_MAX_BUILTIN_CU_LIMIT
74 : #define MAP_PERFECT_6 ( LOADER_V4_PROG_ID ), .cost_per_instr= FD_COMPUTE_BUDGET_MAX_BUILTIN_CU_LIMIT
75 : #define MAP_PERFECT_7 ( KECCAK_SECP_PROG_ID ), .cost_per_instr= FD_COMPUTE_BUDGET_MAX_BUILTIN_CU_LIMIT
76 : #define MAP_PERFECT_8 ( ED25519_SV_PROG_ID ), .cost_per_instr= FD_COMPUTE_BUDGET_MAX_BUILTIN_CU_LIMIT
77 : #define MAP_PERFECT_9 ( SECP256R1_PROG_ID ), .cost_per_instr= FD_COMPUTE_BUDGET_MAX_BUILTIN_CU_LIMIT
78 :
79 : #include "../../util/tmpl/fd_map_perfect.c"
80 :
81 : /* Redefine it so we can use it below */
82 : #define MAP_PERFECT_HASH_PP( a00,a01,a02,a03,a04,a05,a06,a07,a08,a09,a10,a11,a12,a13,a14,a15, \
83 : a16,a17,a18,a19,a20,a21,a22,a23,a24,a25,a26,a27,a28,a29,a30,a31) \
84 54459504 : PERFECT_HASH( ((uint)a08 | ((uint)a09<<8) | ((uint)a10<<16) | ((uint)a11<<24)) )
85 :
86 13576758 : #define FD_PACK_COST_PER_SIGNATURE ( 720UL)
87 0 : #define FD_PACK_COST_PER_NON_STRICT_ED25519_SIGNATURE ( 2280UL)
88 0 : #define FD_PACK_COST_PER_ED25519_SIGNATURE ( 2400UL)
89 0 : #define FD_PACK_COST_PER_SECP256K1_SIGNATURE ( 6690UL)
90 0 : #define FD_PACK_COST_PER_SECP256R1_SIGNATURE ( 4800UL)
91 13578210 : #define FD_PACK_COST_PER_WRITABLE_ACCT ( 300UL)
92 13576716 : #define FD_PACK_INV_COST_PER_INSTR_DATA_BYTE ( 4UL)
93 :
94 : /* The computation here is similar to the computation for the max
95 : fd_txn_t size. There are various things a transaction can include
96 : that consume CUs, and they also consume some bytes of payload. It
97 : then becomes an integer linear programming problem. First, the best
98 : use of bytes is to include a compute budget program instruction that
99 : requests 1.4M CUs. That also requires the invocation of another
100 : non-builtin program, consuming 3 bytes of payload. In total to do
101 : this, we need 2 pubkey and 11 bytes of instruction payload. This is
102 : >18,000 CUs per byte, which is obviously the best move.
103 :
104 : From there, we can also invoke built-in programs with no accounts and
105 : no instruction data, which also consumes 3 bytes of payload. The
106 : most expensive built-in is the BPF upgradeable loader. We're limited
107 : to 64 instructions, so we can only consume it at most 62 times. This
108 : is about 675 CUs per byte.
109 :
110 : We've maxed out the instruction limit, so we can only continue to
111 : increase the cost by adding writable accounts or writable signer
112 : accounts. Writable signers consume 96 bytes use 1020 CUs. Writable
113 : non-signers consume 32 bytes and use 300 CUs. That's 10.6 CUs/byte
114 : and 9.4 CUs/byte, respectively, so in general, writable signers are
115 : more efficient and we want to add as many as we can. We also need at
116 : least one writable signer to be the fee payer, and, although it's
117 : unusual, there's actually no reason the non-builtin program can't be
118 : a writable signer too.
119 :
120 : Finally, with any bytes that remain, we can add them to one of the
121 : instruction datas for 0.25 CUs/byte.
122 :
123 : Note that by default, 64MiB of data are assumed for the loaded
124 : accounts data size cost. This corresponds (currently) to 16384 CUs.
125 :
126 : This gives a transaction that looks like
127 : Field bytes consumed CUs used
128 : sig cnt 1 0
129 : fee payer sig 64 720
130 : 8 other signatures 512 5,670
131 : fixed header (no ALTs) 3 0
132 : acct addr cnt 1 0
133 : fee payer pubkey 32 300
134 : 8 writable pubkeys 256 2,400
135 : 2 writable non-signers 64 600
136 : CBP, BPF upg loader 64 0
137 : Recent blockhash 32 0
138 : Instruction count 1 0
139 : Compute budget program ix 8 151.25
140 : 62 dummy BPF upg ixs 186 146,940
141 : 1 dummy non-builtin ix 8 1,400,001.25
142 : loaded accts data cost 0 16384
143 : + ---------------------------------------------------------------
144 : 1,232 1,573,166
145 :
146 : One of the main take-aways from this is that the cost of a
147 : transaction easily fits in a uint. */
148 : #define FD_PACK_MAX_TXN_COST (1573166UL)
149 : FD_STATIC_ASSERT( FD_PACK_MAX_TXN_COST < (ulong)UINT_MAX, fd_pack_max_cost );
150 :
151 : /* Every transaction has at least a fee payer, a writable signer. */
152 : #define FD_PACK_MIN_TXN_COST (FD_PACK_COST_PER_SIGNATURE+FD_PACK_COST_PER_WRITABLE_ACCT)
153 :
154 : /* NOTE: THE FOLLOWING CONSTANTS ARE CONSENSUS CRITICAL AND CANNOT BE
155 : CHANGED WITHOUT COORDINATING WITH ANZA. */
156 :
157 : /* These are bounds on known limits. Upper bound values are used to
158 : calculate memory footprints while lower bounds are used for
159 : initializing consensus-dependent logic and invariant checking. As a
160 : leader, it is OK to produce blocks using limits smaller than the
161 : active on-chain limits. Replay should always use the correct
162 : chain-derived limits.
163 :
164 : The actual limits used by pack may be updated dynamically to some
165 : in-bounds value. If there is an anticipated feature activation that
166 : changes these limits, the upper bound should be the largest
167 : anticipated value while the lower bound should be the current active
168 : limit. For Frankendancer, the actual value used for consensus will be
169 : retrieved from Agave at runtime. */
170 63 : #define FD_PACK_MAX_COST_PER_BLOCK_LOWER_BOUND (48000000UL)
171 63 : #define FD_PACK_MAX_VOTE_COST_PER_BLOCK_LOWER_BOUND (36000000UL)
172 63 : #define FD_PACK_MAX_WRITE_COST_PER_ACCT_LOWER_BOUND (12000000UL)
173 :
174 126 : #define FD_PACK_MAX_COST_PER_BLOCK_UPPER_BOUND (100000000UL) /* simd 0286 */
175 63 : #define FD_PACK_MAX_VOTE_COST_PER_BLOCK_UPPER_BOUND ( 36000000UL)
176 63 : #define FD_PACK_MAX_WRITE_COST_PER_ACCT_UPPER_BOUND ( FD_PACK_MAX_COST_PER_BLOCK_UPPER_BOUND * 4UL / 10UL ) /* simd 0306 */
177 :
178 : FD_STATIC_ASSERT( FD_MAX_TXN_PER_SLOT_CU==(FD_PACK_MAX_COST_PER_BLOCK_UPPER_BOUND/FD_PACK_MIN_TXN_COST), max_txn_per_slot_cu );
179 :
180 : /* The txncache should at most store one entry for each transaction, so
181 : you would expect this value to be just FD_MAX_TXN_PER_SLOT. But
182 : there's a minor complication ... Agave inserts each transaction into
183 : the status cache twice, once with the signature as the key, and
184 : once with the message hash as the key. This is to support querying
185 : transactions by either signature or message hash. We load snapshots
186 : from Agave nodes which serve both entries, and there is no way to
187 : filter out the by signature entries which are useless to us, so
188 : initially the status cache needs twice as much space. */
189 3 : #define FD_PACK_MAX_TXNCACHE_TXN_PER_SLOT (2UL*FD_MAX_TXN_PER_SLOT)
190 :
191 :
192 : /* https://github.com/anza-xyz/agave/blob/v2.0.1/programs/vote/src/vote_processor.rs#L55 */
193 :
194 38157 : #define FD_PACK_VOTE_DEFAULT_COMPUTE_UNITS 2100UL
195 :
196 : /* A simple vote transaction has the authorized voter (writable
197 : signer), the vote account (writable non-signer), clock sysvar, slot
198 : hashes sysvar (both readonly), and the vote program (readonly). Then
199 : it has one instruction a built-in to the vote program, which has a
200 : fixed cost of DEFAULT_COMPUTE_UNITS, and an instruction data cost of
201 : 8.
202 :
203 : See https://github.com/firedancer-io/agave/blob/v2.1.11-fd/sdk/src/simple_vote_transaction_checker.rs */
204 : static const ulong FD_PACK_SIMPLE_VOTE_COST = ( FD_PACK_COST_PER_SIGNATURE +
205 : 2UL*FD_PACK_COST_PER_WRITABLE_ACCT +
206 : FD_PACK_VOTE_DEFAULT_COMPUTE_UNITS +
207 : 8 );
208 :
209 :
210 : /* Computes the total cost and a few related properties for the
211 : specified transaction. On success, returns the cost, which is in
212 : [1020, FD_PACK_MAX_TXN_COST] and sets or clears the
213 : FD_TXN_P_FLAG_IS_SIMPLE_VOTE bit of the value pointed to by flags to
214 : indicate whether the transaction is a simple vote or not.
215 :
216 : Additionally:
217 : If opt_execution_cost is non-null, on success it will contain the
218 : execution cost (BPF execution cost + built-in execution cost). This
219 : value is in [0, the returned value).
220 : If opt_fee is non-null, on success it will contain the priority fee,
221 : measured in lamports (i.e. the part of the fee that excludes the
222 : per-signature fee). This value is in [0, ULONG_MAX].
223 : If opt_precompile_sig_cnt is non-null, on success it will contain the
224 : total number of signatures in precompile instructions, namely Keccak
225 : and Ed25519 signature verification programs. This value is in [0,
226 : 256*64]. Note that this does not do full parsing of the precompile
227 : instruction, and it may be malformed. If
228 : opt_loaded_accounts_data_cost is non-null, on success it will contain
229 : the total requested cost due to loaded accounts data. This value is
230 : in [0, the returned value).
231 :
232 : On failure, returns 0 and does not modify the value pointed to by
233 : flags, opt_execution_cost, opt_fee, or opt_precompile_sig_cnt. */
234 : static inline ulong
235 : fd_pack_compute_cost( fd_txn_t const * txn,
236 : uchar const * payload,
237 : uint * flags,
238 : ulong * opt_execution_cost,
239 : ulong * opt_fee,
240 : ulong * opt_precompile_sig_cnt,
241 13614876 : ulong * opt_loaded_accounts_data_cost ) {
242 :
243 54459504 : #define ROW(x) fd_pack_builtin_tbl + MAP_PERFECT_HASH_PP( x )
244 13614876 : fd_pack_builtin_prog_cost_t const * compute_budget_row = ROW( COMPUTE_BUDGET_PROG_ID );
245 13614876 : fd_pack_builtin_prog_cost_t const * ed25519_precompile_row = ROW( ED25519_SV_PROG_ID );
246 13614876 : fd_pack_builtin_prog_cost_t const * secp256k1_precomp_row = ROW( KECCAK_SECP_PROG_ID );
247 13614876 : fd_pack_builtin_prog_cost_t const * secp256r1_precomp_row = ROW( SECP256R1_PROG_ID );
248 13614876 : #undef ROW
249 :
250 : /* special handling for simple votes */
251 13614876 : if( FD_UNLIKELY( fd_txn_is_simple_vote_transaction( txn, payload ) ) ) {
252 : #if DETAILED_LOGGING
253 : FD_BASE58_ENCODE_64_BYTES( (const uchar *)fd_txn_get_signatures(txn, payload), signature_cstr );
254 : FD_LOG_NOTICE(( "TXN SIMPLE_VOTE signature[%s] total_cost[%lu]", signature_cstr, FD_PACK_SIMPLE_VOTE_COST));
255 : #endif
256 38157 : *flags |= FD_TXN_P_FLAGS_IS_SIMPLE_VOTE;
257 38157 : fd_ulong_store_if( !!opt_execution_cost, opt_execution_cost, FD_PACK_VOTE_DEFAULT_COMPUTE_UNITS );
258 38157 : fd_ulong_store_if( !!opt_fee, opt_fee, 0 );
259 38157 : fd_ulong_store_if( !!opt_precompile_sig_cnt, opt_precompile_sig_cnt, 0 );
260 38157 : fd_ulong_store_if( !!opt_loaded_accounts_data_cost, opt_loaded_accounts_data_cost, 0 );
261 38157 : return FD_PACK_SIMPLE_VOTE_COST;
262 38157 : }
263 :
264 13576719 : *flags &= ~FD_TXN_P_FLAGS_IS_SIMPLE_VOTE;
265 :
266 : /* We need to be mindful of overflow here, but it's not terrible.
267 : signature_cost < FD_TXN_ACCT_ADDR_MAX*720 + FD_TXN_INSTR_MAX * UCHAR_MAX * 6690,
268 : writable_cost <= FD_TXN_ACCT_ADDR_MAX*300 */
269 13576719 : ulong signature_cnt = fd_txn_account_cnt( txn, FD_TXN_ACCT_CAT_SIGNER );
270 13576719 : ulong signature_cost = FD_PACK_COST_PER_SIGNATURE * signature_cnt;
271 13576719 : ulong writable_cost = FD_PACK_COST_PER_WRITABLE_ACCT * fd_txn_account_cnt( txn, FD_TXN_ACCT_CAT_WRITABLE );
272 :
273 13576719 : ulong instr_data_sz = 0UL; /* < FD_TPU_MTU */
274 13576719 : ulong non_builtin_cnt = 0UL; /* <= FD_TXN_INSTR_MAX */
275 13576719 : ulong precompile_sig_cnt = 0UL; /* <= FD_TXN_INSTR_MAX * UCHAR_MAX */
276 13576719 : fd_acct_addr_t const * addr_base = fd_txn_get_acct_addrs( txn, payload );
277 :
278 13576719 : fd_compute_budget_program_state_t cbp[1];
279 13576719 : fd_compute_budget_program_init( cbp );
280 :
281 23267709 : for( ulong i=0UL; i<txn->instr_cnt; i++ ) {
282 9690993 : instr_data_sz += txn->instr[i].data_sz;
283 :
284 9690993 : ulong prog_id_idx = (ulong)txn->instr[i].program_id;
285 9690993 : fd_acct_addr_t const * prog_id = addr_base + prog_id_idx;
286 :
287 : /* Lookup prog_id in hash table */
288 :
289 9690993 : fd_pack_builtin_prog_cost_t null_row[1] = {{{ 0 }, 0UL }};
290 9690993 : fd_pack_builtin_prog_cost_t const * in_tbl = fd_pack_builtin_query( prog_id, null_row );
291 9690993 : non_builtin_cnt += !in_tbl->cost_per_instr; /* The only one with no cost is the null one */
292 :
293 9690993 : if( FD_UNLIKELY( in_tbl==compute_budget_row ) ) {
294 4234494 : if( FD_UNLIKELY( 0==fd_compute_budget_program_parse( payload+txn->instr[i].data_off, txn->instr[i].data_sz, cbp ) ) )
295 3 : return 0UL;
296 5456499 : } else if( FD_UNLIKELY( (in_tbl==ed25519_precompile_row) ) ) {
297 : /* First byte is # of signatures. Branchless tail reading here is
298 : probably okay, but this seems safer. */
299 0 : ulong ed25519_signature_count = (txn->instr[i].data_sz>0) ? (ulong)payload[ txn->instr[i].data_off ] : 0UL;
300 0 : precompile_sig_cnt += ed25519_signature_count;
301 0 : signature_cost += ed25519_signature_count * FD_PACK_COST_PER_ED25519_SIGNATURE;
302 5456499 : } else if( FD_UNLIKELY( (in_tbl==secp256k1_precomp_row) ) ) {
303 0 : ulong secp256k1_signature_count = (txn->instr[i].data_sz>0) ? (ulong)payload[ txn->instr[i].data_off ] : 0UL;
304 0 : precompile_sig_cnt += secp256k1_signature_count;
305 0 : signature_cost += secp256k1_signature_count * FD_PACK_COST_PER_SECP256K1_SIGNATURE;
306 5456499 : } else if( FD_UNLIKELY( (in_tbl==secp256r1_precomp_row) ) ) {
307 0 : ulong secp256r1_signature_count = (txn->instr[i].data_sz>0) ? (ulong)payload[ txn->instr[i].data_off ] : 0UL;
308 0 : precompile_sig_cnt += secp256r1_signature_count;
309 0 : signature_cost += secp256r1_signature_count * FD_PACK_COST_PER_SECP256R1_SIGNATURE;
310 0 : }
311 9690993 : }
312 :
313 13576716 : ulong instr_data_cost = instr_data_sz / FD_PACK_INV_COST_PER_INSTR_DATA_BYTE; /* <= 320 */
314 :
315 13576716 : ulong fee[1];
316 13576716 : uint execution_cost[1];
317 13576716 : ulong loaded_account_data_cost[1];
318 13576716 : fd_compute_budget_program_finalize( cbp, txn->instr_cnt, txn->instr_cnt-non_builtin_cnt, fee, execution_cost, loaded_account_data_cost );
319 :
320 13576716 : fd_ulong_store_if( !!opt_execution_cost, opt_execution_cost, (ulong)(*execution_cost) );
321 13576716 : fd_ulong_store_if( !!opt_fee, opt_fee, *fee );
322 13576716 : fd_ulong_store_if( !!opt_precompile_sig_cnt, opt_precompile_sig_cnt, precompile_sig_cnt );
323 13576716 : fd_ulong_store_if( !!opt_loaded_accounts_data_cost, opt_loaded_accounts_data_cost, *loaded_account_data_cost );
324 :
325 : #if DETAILED_LOGGING
326 : FD_BASE58_ENCODE_64_BYTES( (const uchar *)fd_txn_get_signatures(txn, payload), signature_cstr );
327 : FD_LOG_NOTICE(( "TXN signature[%s] signature_cost[%lu] writable_cost[%lu] instr_data_cost[%lu] non_builtin_cost[%lu] loaded_account_data_cost[%lu] precompile_sig_cnt[%lu] fee[%lu]",
328 : signature_cstr, signature_cost, writable_cost, instr_data_cost, non_builtin_cost, *loaded_account_data_cost, precompile_sig_cnt, *fee));
329 : #endif
330 :
331 : /* <= FD_PACK_MAX_COST, so no overflow concerns */
332 13576716 : return signature_cost + writable_cost + *execution_cost + instr_data_cost + *loaded_account_data_cost;
333 13576719 : }
334 : #undef MAP_PERFECT_HASH_PP
335 : #undef PERFECT_HASH
336 :
337 : #endif /* HEADER_fd_src_disco_pack_fd_pack_cost_h */
|
