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 8038794 : #define MAP_PERFECT_KEYS_EQUAL(k1,k2) (!memcmp( (k1), (k2), 32UL ))
44 :
45 75901599 : #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 8038794 : #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 ( VOTE_PROG_ID ), .cost_per_instr=VOTE_PROG_COST
57 : #define MAP_PERFECT_2 ( SYS_PROG_ID ), .cost_per_instr= 150UL
58 : #define MAP_PERFECT_3 ( COMPUTE_BUDGET_PROG_ID ), .cost_per_instr= 150UL
59 : #define MAP_PERFECT_4 ( ADDR_LUT_PROG_ID ), .cost_per_instr= 750UL
60 : #define MAP_PERFECT_5 ( BPF_UPGRADEABLE_PROG_ID ), .cost_per_instr= 2370UL
61 : #define MAP_PERFECT_6 ( BPF_LOADER_1_PROG_ID ), .cost_per_instr= 1140UL
62 : #define MAP_PERFECT_7 ( BPF_LOADER_2_PROG_ID ), .cost_per_instr= 570UL
63 : #define MAP_PERFECT_8 ( LOADER_V4_PROG_ID ), .cost_per_instr= 2000UL
64 : #define MAP_PERFECT_9 ( KECCAK_SECP_PROG_ID ), .cost_per_instr= 720UL
65 : #define MAP_PERFECT_10 ( ED25519_SV_PROG_ID ), .cost_per_instr= 720UL
66 : #define MAP_PERFECT_11 ( SECP256R1_PROG_ID ), .cost_per_instr= 720UL
67 :
68 : #include "../../util/tmpl/fd_map_perfect.c"
69 :
70 : /* Redefine it so we can use it below */
71 : #define MAP_PERFECT_HASH_PP( a00,a01,a02,a03,a04,a05,a06,a07,a08,a09,a10,a11,a12,a13,a14,a15, \
72 : a16,a17,a18,a19,a20,a21,a22,a23,a24,a25,a26,a27,a28,a29,a30,a31) \
73 67862805 : PERFECT_HASH( ((uint)a08 | ((uint)a09<<8) | ((uint)a10<<16) | ((uint)a11<<24)) )
74 :
75 13572561 : #define FD_PACK_COST_PER_SIGNATURE (720UL)
76 13573905 : #define FD_PACK_COST_PER_WRITABLE_ACCT (300UL)
77 13572558 : #define FD_PACK_INV_COST_PER_INSTR_DATA_BYTE ( 4UL)
78 :
79 : /* This is an extremely conservative upper bound on the max cost. The
80 : majority of it comes from TXN_INSTR_MAX*2370, which is excessively
81 : high in this branch. The only useful insight from this limit is that
82 : costs will fit conveniently in a uint and definitely in a ulong. A
83 : transaction with cost this high can't fit in a block, so will never
84 : make it on chain, but that's not the job of this part of the code to
85 : know about. */
86 : #define FD_PACK_MAX_TXN_COST (156981760UL)
87 : FD_STATIC_ASSERT( FD_PACK_MAX_TXN_COST>= (
88 : ((ulong)FD_TXN_ACCT_ADDR_MAX*(720UL+300UL)) + /* writable signer are the most expensive */
89 : ((ulong)FD_TXN_INSTR_MAX*2370UL) + /* the most expensive built-in */
90 : (FD_TPU_MTU/FD_PACK_INV_COST_PER_INSTR_DATA_BYTE) +
91 : (ulong)FD_COMPUTE_BUDGET_MAX_CU_LIMIT), fd_pack_max_cost );
92 : FD_STATIC_ASSERT( FD_PACK_MAX_TXN_COST < (ulong)UINT_MAX, fd_pack_max_cost );
93 :
94 : /* Every transaction has at least a fee payer, a writable signer. */
95 : #define FD_PACK_MIN_TXN_COST (FD_PACK_COST_PER_SIGNATURE+FD_PACK_COST_PER_WRITABLE_ACCT)
96 :
97 : /* A typical vote transaction has the authorized voter (writable
98 : signer), the vote account (writable non-signer), clock sysvar, slot
99 : hashes sysvar (both readonly), and the vote program (readonly). Then
100 : it has one instruction a built-in to the vote program, which is
101 : typically 61 bytes (1 slot) or 69 bytes (2 slot) long. The mean over
102 : 1000 slots of vote transactions is 69.3 bytes. */
103 : static const ulong FD_PACK_TYPICAL_VOTE_COST = ( FD_PACK_COST_PER_SIGNATURE +
104 : 2UL*FD_PACK_COST_PER_WRITABLE_ACCT +
105 : 69UL/FD_PACK_INV_COST_PER_INSTR_DATA_BYTE +
106 : VOTE_PROG_COST );
107 :
108 : #undef VOTE_PROG_COST
109 :
110 :
111 : /* Computes the total cost and a few related properties for the
112 : specified transaction. On success, returns the cost, which is in
113 : [1020, FD_PACK_MAX_TXN_COST] and sets or clears the
114 : FD_TXN_P_FLAG_IS_SIMPLE_VOTE bit of the value pointed to by flags to
115 : indicate whether the transaction is a simple vote or not.
116 :
117 : Additionally:
118 : If opt_execution_cost is non-null, on success it will contain the
119 : execution cost (BPF execution cost + built-in execution cost). This
120 : value is in [0, the returned value).
121 : If opt_fee is non-null, on success it will contain the priority fee,
122 : measured in lamports (i.e. the part of the fee that excludes the
123 : per-signature fee). This value is in [0, ULONG_MAX].
124 : If opt_precompile_sig_cnt is non-null, on success it will contain the
125 : total number of signatures in precompile instructions, namely Keccak
126 : and Ed25519 signature verification programs. This value is in [0,
127 : 256*64]. Note that this does not do full parsing of the precompile
128 : instruction, and it may be malformed.
129 :
130 : On failure, returns 0 and does not modify the value pointed to by
131 : flags, opt_execution_cost, opt_fee, or opt_precompile_sig_cnt. */
132 : static inline ulong
133 : fd_pack_compute_cost( fd_txn_t const * txn,
134 : uchar const * payload,
135 : uint * flags,
136 : ulong * opt_execution_cost,
137 : ulong * opt_fee,
138 13572561 : ulong * opt_precompile_sig_cnt ) {
139 :
140 67862805 : #define ROW(x) fd_pack_builtin_tbl + MAP_PERFECT_HASH_PP( x )
141 :
142 13572561 : fd_pack_builtin_prog_cost_t const * compute_budget_row = ROW( COMPUTE_BUDGET_PROG_ID );
143 13572561 : fd_pack_builtin_prog_cost_t const * vote_row = ROW( VOTE_PROG_ID );
144 13572561 : fd_pack_builtin_prog_cost_t const * ed25519_precompile_row = ROW( ED25519_SV_PROG_ID );
145 13572561 : fd_pack_builtin_prog_cost_t const * keccak_precompile_row = ROW( KECCAK_SECP_PROG_ID );
146 13572561 : fd_pack_builtin_prog_cost_t const * secp256r1_precomp_row = ROW( SECP256R1_PROG_ID );
147 13572561 : #undef ROW
148 :
149 : /* We need to be mindful of overflow here, but it's not terrible.
150 : signature_cost <= FD_TXN_ACCT_ADDR_MAX*720,
151 : writable_cost <= FD_TXN_ACCT_ADDR_MAX*300 */
152 :
153 13572561 : ulong signature_cost = FD_PACK_COST_PER_SIGNATURE * fd_txn_account_cnt( txn, FD_TXN_ACCT_CAT_SIGNER );
154 13572561 : ulong writable_cost = FD_PACK_COST_PER_WRITABLE_ACCT * fd_txn_account_cnt( txn, FD_TXN_ACCT_CAT_WRITABLE );
155 :
156 13572561 : ulong instr_data_sz = 0UL; /* < FD_TPU_MTU */
157 13572561 : ulong builtin_cost = 0UL; /* <= 2370*FD_TXN_INSTR_MAX */
158 13572561 : ulong non_builtin_cnt = 0UL; /* <= FD_TXN_INSTR_MAX */
159 13572561 : ulong vote_instr_cnt = 0UL; /* <= FD_TXN_INSTR_MAX */
160 13572561 : ulong precompile_sig_cnt = 0UL; /* <= FD_TXN_INSTR_MAX * UCHAR_MAX */
161 13572561 : fd_acct_addr_t const * addr_base = fd_txn_get_acct_addrs( txn, payload );
162 :
163 13572561 : fd_compute_budget_program_state_t cbp[1];
164 13572561 : fd_compute_budget_program_init( cbp );
165 :
166 :
167 21611352 : for( ulong i=0UL; i<txn->instr_cnt; i++ ) {
168 8038794 : instr_data_sz += txn->instr[i].data_sz;
169 :
170 8038794 : ulong prog_id_idx = (ulong)txn->instr[i].program_id;
171 8038794 : fd_acct_addr_t const * prog_id = addr_base + prog_id_idx;
172 :
173 : /* Lookup prog_id in hash table */
174 :
175 8038794 : fd_pack_builtin_prog_cost_t null_row[1] = {{{ 0 }, 0UL }};
176 8038794 : fd_pack_builtin_prog_cost_t const * in_tbl = fd_pack_builtin_query( prog_id, null_row );
177 8038794 : builtin_cost += in_tbl->cost_per_instr;
178 8038794 : non_builtin_cnt += !in_tbl->cost_per_instr; /* The only one with no cost is the null one */
179 :
180 8038794 : if( FD_UNLIKELY( in_tbl==compute_budget_row ) ) {
181 2739513 : if( FD_UNLIKELY( 0==fd_compute_budget_program_parse( payload+txn->instr[i].data_off, txn->instr[i].data_sz, cbp ) ) )
182 3 : return 0UL;
183 5299281 : } else if( FD_UNLIKELY( (in_tbl==ed25519_precompile_row) | (in_tbl==keccak_precompile_row) | (in_tbl==secp256r1_precomp_row) ) ) {
184 : /* First byte is # of signatures. Branchless tail reading here is
185 : probably okay, but this seems safer. */
186 0 : precompile_sig_cnt += (txn->instr[i].data_sz>0) ? (ulong)payload[ txn->instr[i].data_off ] : 0UL;
187 0 : }
188 :
189 8038791 : vote_instr_cnt += (ulong)(in_tbl==vote_row);
190 :
191 8038791 : }
192 :
193 13572558 : ulong instr_data_cost = instr_data_sz / FD_PACK_INV_COST_PER_INSTR_DATA_BYTE; /* <= 320 */
194 :
195 13572558 : ulong fee[1];
196 13572558 : uint compute[1];
197 13572558 : fd_compute_budget_program_finalize( cbp, txn->instr_cnt, fee, compute );
198 :
199 13572558 : non_builtin_cnt = fd_ulong_min( non_builtin_cnt, FD_COMPUTE_BUDGET_MAX_CU_LIMIT/FD_COMPUTE_BUDGET_DEFAULT_INSTR_CU_LIMIT );
200 :
201 13572558 : ulong non_builtin_cost = fd_ulong_if( (cbp->flags & FD_COMPUTE_BUDGET_PROGRAM_FLAG_SET_CU) && (non_builtin_cnt>0UL),
202 13572558 : (ulong)*compute,
203 13572558 : non_builtin_cnt*FD_COMPUTE_BUDGET_DEFAULT_INSTR_CU_LIMIT
204 13572558 : ); /* <= FD_COMPUTE_BUDGET_MAX_CU_LIMIT */
205 :
206 :
207 13572558 : if( FD_LIKELY( (vote_instr_cnt==1UL) & (txn->instr_cnt==1UL) ) ) *flags |= FD_TXN_P_FLAGS_IS_SIMPLE_VOTE;
208 13534962 : else *flags &= ~FD_TXN_P_FLAGS_IS_SIMPLE_VOTE;
209 :
210 13572558 : fd_ulong_store_if( !!opt_execution_cost, opt_execution_cost, builtin_cost + non_builtin_cost );
211 13572558 : fd_ulong_store_if( !!opt_fee, opt_fee, *fee );
212 13572558 : fd_ulong_store_if( !!opt_precompile_sig_cnt, opt_precompile_sig_cnt, precompile_sig_cnt );
213 :
214 : /* <= FD_PACK_MAX_COST, so no overflow concerns */
215 13572558 : return signature_cost + writable_cost + builtin_cost + instr_data_cost + non_builtin_cost;
216 13572561 : }
217 : #undef MAP_PERFECT_HASH_PP
218 : #undef PERFECT_HASH
219 : #endif /* HEADER_fd_src_ballet_pack_fd_pack_cost_h */
|
