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 "../fd_ballet_base.h"
4 : #include "fd_compute_budget_program.h"
5 : #include "../../flamenco/runtime/fd_system_ids_pp.h"
6 :
7 : /* The functions in this header implement the transaction cost model
8 : that is soon to be part of consensus.
9 : The cost model consists of several components:
10 : * per-signature cost
11 : * per-write-lock cost
12 : * instruction data length cost
13 : * built-in execution cost
14 : * BPF execution cost
15 : These are all summed to determine the total cost. Additionally, this
16 : header provides a method for determining if a transaction is a simple
17 : vote transaction, in which case its costs are used slightly
18 : differently. */
19 :
20 : /* To compute the built-in cost, we need to check a table. The table
21 : is known ahead of time though, so we can build a perfect hash
22 : table for performance.
23 : The values of the table are based on https://github.com/
24 : solana-labs/solana/blob/9fb105c801e2999a24f0773443d6164e30c9ff0c/
25 : runtime/src/block_cost_limits.rs#L34-L47 . */
26 :
27 :
28 :
29 : struct __attribute__((aligned(32))) fd_pack_builtin_prog_cost {
30 : uchar program_id[32];
31 : ulong cost_per_instr;
32 : };
33 : typedef struct fd_pack_builtin_prog_cost fd_pack_builtin_prog_cost_t;
34 :
35 : #define MAP_PERFECT_NAME fd_pack_builtin
36 : #define MAP_PERFECT_LG_TBL_SZ 4
37 : #define MAP_PERFECT_T fd_pack_builtin_prog_cost_t
38 : #define MAP_PERFECT_HASH_C 478U
39 : #define MAP_PERFECT_KEY program_id
40 : #define MAP_PERFECT_KEY_T fd_acct_addr_t const *
41 : #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)
42 : #define MAP_PERFECT_COMPLEX_KEY 1
43 8039187 : #define MAP_PERFECT_KEYS_EQUAL(k1,k2) (!memcmp( (k1), (k2), 32UL ))
44 :
45 75902517 : #define PERFECT_HASH( u ) (((478U*(u))>>28)&0xFU)
46 :
47 : #define MAP_PERFECT_HASH_PP( a00,a01,a02,a03,a04,a05,a06,a07,a08,a09,a10,a11,a12,a13,a14,a15, \
48 : a16,a17,a18,a19,a20,a21,a22,a23,a24,a25,a26,a27,a28,a29,a30,a31) \
49 : PERFECT_HASH( (a08 | (a09<<8) | (a10<<16) | (a11<<24)) )
50 8039187 : #define MAP_PERFECT_HASH_R( ptr ) PERFECT_HASH( fd_uint_load_4( (uchar const *)ptr->b + 8UL ) )
51 :
52 :
53 : #define VOTE_PROG_COST 2100UL
54 :
55 : #define MAP_PERFECT_0 ( STAKE_PROG_ID ), .cost_per_instr= 750UL
56 : #define MAP_PERFECT_1 ( CONFIG_PROG_ID ), .cost_per_instr= 450UL
57 : #define MAP_PERFECT_2 ( VOTE_PROG_ID ), .cost_per_instr=VOTE_PROG_COST
58 : #define MAP_PERFECT_3 ( SYS_PROG_ID ), .cost_per_instr= 150UL
59 : #define MAP_PERFECT_4 ( COMPUTE_BUDGET_PROG_ID ), .cost_per_instr= 150UL
60 : #define MAP_PERFECT_5 ( ADDR_LUT_PROG_ID ), .cost_per_instr= 750UL
61 : #define MAP_PERFECT_6 ( BPF_UPGRADEABLE_PROG_ID ), .cost_per_instr= 2370UL
62 : #define MAP_PERFECT_7 ( BPF_LOADER_1_PROG_ID ), .cost_per_instr= 1140UL
63 : #define MAP_PERFECT_8 ( BPF_LOADER_2_PROG_ID ), .cost_per_instr= 570UL
64 : #define MAP_PERFECT_9 ( LOADER_V4_PROG_ID ), .cost_per_instr= 2000UL
65 : #define MAP_PERFECT_10 ( KECCAK_SECP_PROG_ID ), .cost_per_instr= 720UL
66 : #define MAP_PERFECT_11 ( ED25519_SV_PROG_ID ), .cost_per_instr= 720UL
67 : #define MAP_PERFECT_12 ( SECP256R1_PROG_ID ), .cost_per_instr= 720UL
68 :
69 : #include "../../util/tmpl/fd_map_perfect.c"
70 :
71 : /* Redefine it so we can use it below */
72 : #define MAP_PERFECT_HASH_PP( a00,a01,a02,a03,a04,a05,a06,a07,a08,a09,a10,a11,a12,a13,a14,a15, \
73 : a16,a17,a18,a19,a20,a21,a22,a23,a24,a25,a26,a27,a28,a29,a30,a31) \
74 67863330 : PERFECT_HASH( ((uint)a08 | ((uint)a09<<8) | ((uint)a10<<16) | ((uint)a11<<24)) )
75 :
76 13572666 : #define FD_PACK_COST_PER_SIGNATURE (720UL)
77 13574019 : #define FD_PACK_COST_PER_WRITABLE_ACCT (300UL)
78 13572663 : #define FD_PACK_INV_COST_PER_INSTR_DATA_BYTE ( 4UL)
79 :
80 : /* This is an extremely conservative upper bound on the max cost. The
81 : majority of it comes from TXN_INSTR_MAX*2370, which is excessively
82 : high in this branch. The only useful insight from this limit is that
83 : costs will fit conveniently in a uint and definitely in a ulong. A
84 : transaction with cost this high can't fit in a block, so will never
85 : make it on chain, but that's not the job of this part of the code to
86 : know about. */
87 : #define FD_PACK_MAX_TXN_COST (156981760UL)
88 : FD_STATIC_ASSERT( FD_PACK_MAX_TXN_COST>= (
89 : ((ulong)FD_TXN_ACCT_ADDR_MAX*(720UL+300UL)) + /* writable signer are the most expensive */
90 : ((ulong)FD_TXN_INSTR_MAX*2370UL) + /* the most expensive built-in */
91 : (FD_TPU_MTU/FD_PACK_INV_COST_PER_INSTR_DATA_BYTE) +
92 : (ulong)FD_COMPUTE_BUDGET_MAX_CU_LIMIT), fd_pack_max_cost );
93 : FD_STATIC_ASSERT( FD_PACK_MAX_TXN_COST < (ulong)UINT_MAX, fd_pack_max_cost );
94 :
95 : /* Every transaction has at least a fee payer, a writable signer. */
96 : #define FD_PACK_MIN_TXN_COST (FD_PACK_COST_PER_SIGNATURE+FD_PACK_COST_PER_WRITABLE_ACCT)
97 :
98 : /* A typical vote transaction has the authorized voter (writable
99 : signer), the vote account (writable non-signer), clock sysvar, slot
100 : hashes sysvar (both readonly), and the vote program (readonly). Then
101 : it has one instruction a built-in to the vote program, which is
102 : typically 61 bytes (1 slot) or 69 bytes (2 slot) long. The mean over
103 : 1000 slots of vote transactions is 69.3 bytes. */
104 : static const ulong FD_PACK_TYPICAL_VOTE_COST = ( FD_PACK_COST_PER_SIGNATURE +
105 : 2UL*FD_PACK_COST_PER_WRITABLE_ACCT +
106 : 69UL/FD_PACK_INV_COST_PER_INSTR_DATA_BYTE +
107 : VOTE_PROG_COST );
108 :
109 : #undef VOTE_PROG_COST
110 :
111 :
112 : /* Computes the total cost and a few related properties for the
113 : specified transaction. On success, returns the cost, which is in
114 : [1020, FD_PACK_MAX_TXN_COST] and sets or clears the
115 : FD_TXN_P_FLAG_IS_SIMPLE_VOTE bit of the value pointed to by flags to
116 : indicate whether the transaction is a simple vote or not.
117 :
118 : Additionally:
119 : If opt_execution_cost is non-null, on success it will contain the
120 : execution cost (BPF execution cost + built-in execution cost). This
121 : value is in [0, the returned value).
122 : If opt_fee is non-null, on success it will contain the priority fee,
123 : measured in lamports (i.e. the part of the fee that excludes the
124 : per-signature fee). This value is in [0, ULONG_MAX].
125 : If opt_precompile_sig_cnt is non-null, on success it will contain the
126 : total number of signatures in precompile instructions, namely Keccak
127 : and Ed25519 signature verification programs. This value is in [0,
128 : 256*64]. Note that this does not do full parsing of the precompile
129 : instruction, and it may be malformed.
130 :
131 : On failure, returns 0 and does not modify the value pointed to by
132 : flags, opt_execution_cost, opt_fee, or opt_precompile_sig_cnt. */
133 : static inline ulong
134 : fd_pack_compute_cost( fd_txn_t const * txn,
135 : uchar const * payload,
136 : uint * flags,
137 : ulong * opt_execution_cost,
138 : ulong * opt_fee,
139 13572666 : ulong * opt_precompile_sig_cnt ) {
140 :
141 67863330 : #define ROW(x) fd_pack_builtin_tbl + MAP_PERFECT_HASH_PP( x )
142 :
143 13572666 : fd_pack_builtin_prog_cost_t const * compute_budget_row = ROW( COMPUTE_BUDGET_PROG_ID );
144 13572666 : fd_pack_builtin_prog_cost_t const * vote_row = ROW( VOTE_PROG_ID );
145 13572666 : fd_pack_builtin_prog_cost_t const * ed25519_precompile_row = ROW( ED25519_SV_PROG_ID );
146 13572666 : fd_pack_builtin_prog_cost_t const * keccak_precompile_row = ROW( KECCAK_SECP_PROG_ID );
147 13572666 : fd_pack_builtin_prog_cost_t const * secp256r1_precomp_row = ROW( SECP256R1_PROG_ID );
148 13572666 : #undef ROW
149 :
150 : /* We need to be mindful of overflow here, but it's not terrible.
151 : signature_cost <= FD_TXN_ACCT_ADDR_MAX*720,
152 : writable_cost <= FD_TXN_ACCT_ADDR_MAX*300 */
153 :
154 13572666 : ulong signature_cost = FD_PACK_COST_PER_SIGNATURE * fd_txn_account_cnt( txn, FD_TXN_ACCT_CAT_SIGNER );
155 13572666 : ulong writable_cost = FD_PACK_COST_PER_WRITABLE_ACCT * fd_txn_account_cnt( txn, FD_TXN_ACCT_CAT_WRITABLE );
156 :
157 13572666 : ulong instr_data_sz = 0UL; /* < FD_TPU_MTU */
158 13572666 : ulong builtin_cost = 0UL; /* <= 2370*FD_TXN_INSTR_MAX */
159 13572666 : ulong non_builtin_cnt = 0UL; /* <= FD_TXN_INSTR_MAX */
160 13572666 : ulong vote_instr_cnt = 0UL; /* <= FD_TXN_INSTR_MAX */
161 13572666 : ulong precompile_sig_cnt = 0UL; /* <= FD_TXN_INSTR_MAX * UCHAR_MAX */
162 13572666 : fd_acct_addr_t const * addr_base = fd_txn_get_acct_addrs( txn, payload );
163 :
164 13572666 : fd_compute_budget_program_state_t cbp[1];
165 13572666 : fd_compute_budget_program_init( cbp );
166 :
167 :
168 21611850 : for( ulong i=0UL; i<txn->instr_cnt; i++ ) {
169 8039187 : instr_data_sz += txn->instr[i].data_sz;
170 :
171 8039187 : ulong prog_id_idx = (ulong)txn->instr[i].program_id;
172 8039187 : fd_acct_addr_t const * prog_id = addr_base + prog_id_idx;
173 :
174 : /* Lookup prog_id in hash table */
175 :
176 8039187 : fd_pack_builtin_prog_cost_t null_row[1] = {{{ 0 }, 0UL }};
177 8039187 : fd_pack_builtin_prog_cost_t const * in_tbl = fd_pack_builtin_query( prog_id, null_row );
178 8039187 : builtin_cost += in_tbl->cost_per_instr;
179 8039187 : non_builtin_cnt += !in_tbl->cost_per_instr; /* The only one with no cost is the null one */
180 :
181 8039187 : if( FD_UNLIKELY( in_tbl==compute_budget_row ) ) {
182 2739627 : if( FD_UNLIKELY( 0==fd_compute_budget_program_parse( payload+txn->instr[i].data_off, txn->instr[i].data_sz, cbp ) ) )
183 3 : return 0UL;
184 5299560 : } else if( FD_UNLIKELY( (in_tbl==ed25519_precompile_row) | (in_tbl==keccak_precompile_row) | (in_tbl==secp256r1_precomp_row) ) ) {
185 : /* First byte is # of signatures. Branchless tail reading here is
186 : probably okay, but this seems safer. */
187 0 : precompile_sig_cnt += (txn->instr[i].data_sz>0) ? (ulong)payload[ txn->instr[i].data_off ] : 0UL;
188 0 : }
189 :
190 8039184 : vote_instr_cnt += (ulong)(in_tbl==vote_row);
191 :
192 8039184 : }
193 :
194 13572663 : ulong instr_data_cost = instr_data_sz / FD_PACK_INV_COST_PER_INSTR_DATA_BYTE; /* <= 320 */
195 :
196 13572663 : ulong fee[1];
197 13572663 : uint compute[1];
198 13572663 : fd_compute_budget_program_finalize( cbp, txn->instr_cnt, fee, compute );
199 :
200 13572663 : non_builtin_cnt = fd_ulong_min( non_builtin_cnt, FD_COMPUTE_BUDGET_MAX_CU_LIMIT/FD_COMPUTE_BUDGET_DEFAULT_INSTR_CU_LIMIT );
201 :
202 13572663 : ulong non_builtin_cost = fd_ulong_if( (cbp->flags & FD_COMPUTE_BUDGET_PROGRAM_FLAG_SET_CU) && (non_builtin_cnt>0UL),
203 13572663 : (ulong)*compute,
204 13572663 : non_builtin_cnt*FD_COMPUTE_BUDGET_DEFAULT_INSTR_CU_LIMIT
205 13572663 : ); /* <= FD_COMPUTE_BUDGET_MAX_CU_LIMIT */
206 :
207 :
208 13572663 : if( FD_LIKELY( (vote_instr_cnt==1UL) & (txn->instr_cnt==1UL) ) ) *flags |= FD_TXN_P_FLAGS_IS_SIMPLE_VOTE;
209 13535019 : else *flags &= ~FD_TXN_P_FLAGS_IS_SIMPLE_VOTE;
210 :
211 13572663 : fd_ulong_store_if( !!opt_execution_cost, opt_execution_cost, builtin_cost + non_builtin_cost );
212 13572663 : fd_ulong_store_if( !!opt_fee, opt_fee, *fee );
213 13572663 : fd_ulong_store_if( !!opt_precompile_sig_cnt, opt_precompile_sig_cnt, precompile_sig_cnt );
214 :
215 : /* <= FD_PACK_MAX_COST, so no overflow concerns */
216 13572663 : return signature_cost + writable_cost + builtin_cost + instr_data_cost + non_builtin_cost;
217 13572666 : }
218 : #undef MAP_PERFECT_HASH_PP
219 : #undef PERFECT_HASH
220 : #endif /* HEADER_fd_src_ballet_pack_fd_pack_cost_h */
|
