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