Line data Source code
1 : #ifndef HEADER_fd_src_disco_pack_fd_compute_budget_program_h
2 : #define HEADER_fd_src_disco_pack_fd_compute_budget_program_h
3 :
4 : #include "../../ballet/fd_ballet_base.h"
5 : #include "../../ballet/txn/fd_txn.h"
6 :
7 : /* This header contains utility functions for parsing compute budget
8 : program instructions from a transaction. I.e. given a transaction,
9 : what is its compute budget limit (in compute units) and what is the
10 : additional reward for including it? Unfortunately, due to the way
11 : compute budget program instructions are included in transactions,
12 : this is a per-transaction stateful process.
13 :
14 : This code is designed for high-performance use and so only error
15 : checks data coming from the transaction. */
16 :
17 :
18 : /* In general, compute budget instructions can occur at most once in a
19 : transaction. If an instruction is duplicated, the transaction is
20 : malformed and fails. These flags are used to keep track of what
21 : instructions have been seen so far. Have I seen a ... */
22 3850965 : #define FD_COMPUTE_BUDGET_PROGRAM_FLAG_SET_CU ((ushort)0x01) /* ... SetComputeUnitLimit ... */
23 3850767 : #define FD_COMPUTE_BUDGET_PROGRAM_FLAG_SET_FEE ((ushort)0x02) /* ... SetComputeUnitPrice ... */
24 36 : #define FD_COMPUTE_BUDGET_PROGRAM_FLAG_SET_HEAP ((ushort)0x04) /* ... RequestHeapFrame ... */
25 3850728 : #define FD_COMPUTE_BUDGET_PROGRAM_FLAG_SET_LOADED_DATA_SZ ((ushort)0x08) /* ... LoadedAccountDataSize ... */
26 : /* ... so far? */
27 :
28 :
29 : /* NOTE: THE FOLLOWING CONSTANTS ARE CONSENSUS CRITICAL AND CANNOT BE
30 : CHANGED WITHOUT COORDINATING WITH ANZA. */
31 :
32 : /* base58 decode of ComputeBudget111111111111111111111111111111 */
33 : static const uchar FD_COMPUTE_BUDGET_PROGRAM_ID[FD_TXN_ACCT_ADDR_SZ] = {
34 : 0x03,0x06,0x46,0x6f,0xe5,0x21,0x17,0x32,0xff,0xec,0xad,0xba,0x72,0xc3,0x9b,0xe7,
35 : 0xbc,0x8c,0xe5,0xbb,0xc5,0xf7,0x12,0x6b,0x2c,0x43,0x9b,0x3a,0x40,0x00,0x00,0x00
36 : };
37 :
38 : /* Heap frames must be between 32 KiB and 256 KiB inclusive, and any
39 : requests for larger heap frames must be a multiple of 1 KiB or the
40 : transaction is malformed. */
41 : #define FD_COMPUTE_BUDGET_MIN_HEAP_FRAME_BYTES ( 32UL*1024UL)
42 : #define FD_COMPUTE_BUDGET_MAX_HEAP_FRAME_BYTES ( 256UL*1024UL)
43 : #define FD_COMPUTE_BUDGET_HEAP_FRAME_GRANULARITY ( 1024UL)
44 : /* SetComputeUnitPrice specifies the price in "micro-lamports," which is
45 : 10^(-6) lamports, so 10^(-15) SOL. */
46 26989599 : #define FD_COMPUTE_BUDGET_MICRO_LAMPORTS_PER_LAMPORT ( 1000000UL)
47 :
48 4716 : #define FD_COMPUTE_BUDGET_MAX_BUILTIN_CU_LIMIT ( 3000UL)
49 4716 : #define FD_COMPUTE_BUDGET_DEFAULT_INSTR_CU_LIMIT ( 200000UL)
50 7707102 : #define FD_COMPUTE_BUDGET_MAX_CU_LIMIT ( 1400000UL)
51 3856137 : #define FD_COMPUTE_BUDGET_HEAP_COST ( 8UL)
52 7712274 : #define FD_COMPUTE_BUDGET_ACCOUNT_DATA_COST_PAGE_SIZE (32UL * 1024UL)
53 :
54 : /* Max loaded data size is 64 MiB */
55 3856152 : #define FD_COMPUTE_BUDGET_MAX_LOADED_DATA_SZ (64UL*1024UL*1024UL)
56 :
57 : /* ---- End consensus-critical constants */
58 :
59 :
60 : struct fd_compute_budget_program_private_state {
61 : /* flags: Which instructions have been parsed so far in this transaction? See
62 : above for their meaning. */
63 : ushort flags;
64 : /* compute_budge_instr_cnt: How many compute budget instructions have been
65 : parsed so far? compute_budget_instr_cnt in [0, 4]. */
66 : ushort compute_budget_instr_cnt;
67 : /* compute_units: if SET_CU is in flags, this stores the total requested
68 : compute units for the whole transaction, clamped by parse to
69 : FD_COMPUTE_BUDGET_MAX_CU_LIMIT. Otherwise 0. */
70 : uint compute_units;
71 : /* loaded_acct_data_sz: if SET_LOADED_DATA_SZ is in flags, this stores
72 : the max total data (in bytes) that the transaction will load from
73 : the accounts it references. Otherwise, 0. */
74 : uint loaded_acct_data_sz;
75 : /* heap_size: if SET_HEAP is in flags, this stores the size in bytes of the
76 : BPF heap used for executing this transaction. Otherwise, 0. Must be a
77 : multiple of 1024. */
78 : uint heap_size;
79 : /* micro_lamports_per_cu: if SET_FEE is in flags, this stores the
80 : requested prioritization fee in micro-lamports per compute unit.
81 : Otherwise, 0. */
82 : ulong micro_lamports_per_cu;
83 : };
84 : typedef struct fd_compute_budget_program_private_state fd_compute_budget_program_state_t;
85 :
86 : /* fd_compute_budge_program_init: initializes an
87 : fd_compute_budget_program_state_t to prepare it for parsing a transaction.
88 : Also equivalent to just initializing the state on the stack with = {0}. */
89 3856215 : static inline void fd_compute_budget_program_init( fd_compute_budget_program_state_t * state ) {
90 3856215 : *state = (fd_compute_budget_program_state_t) {0};
91 3856215 : }
92 : /* fd_compute_budget_program_parse: Parses a single ComputeBudgetProgram
93 : instruction. Updates the state stored in state. Returns 0 if the
94 : instruction was invalid, which means the transaction should fail.
95 : instr_data points to the first byte of the instruction data from the
96 : transaction. data_sz specifies the length of the instruction data, so
97 : instr_data[ i ] for i in [0, data_sz) gives the instruction data. */
98 : static inline int
99 : fd_compute_budget_program_parse( uchar const * instr_data,
100 : ulong data_sz,
101 11552550 : fd_compute_budget_program_state_t * state ) {
102 11552550 : if( FD_UNLIKELY( data_sz<5 ) ) return 0;
103 11552550 : switch( *instr_data ) {
104 18 : case 0:
105 : /* Formerly RequestUnitsDeprecated, but invalid since
106 : EfhYd3SafzGT472tYQDUc4dPd2xdEfKs5fwkowUgVt4W. */
107 18 : return 0;
108 60 : case 1:
109 : /* Parse a RequestHeapFrame instruction */
110 60 : if( FD_UNLIKELY( data_sz<5 ) ) return 0;
111 60 : if( FD_UNLIKELY( (state->flags & FD_COMPUTE_BUDGET_PROGRAM_FLAG_SET_HEAP)!=0 ) ) return 0;
112 60 : uint heap_size = FD_LOAD( uint, instr_data+1 );
113 60 : if( FD_UNLIKELY( heap_size%FD_COMPUTE_BUDGET_HEAP_FRAME_GRANULARITY ) ) return 0;
114 51 : if( FD_UNLIKELY( heap_size<FD_COMPUTE_BUDGET_MIN_HEAP_FRAME_BYTES || heap_size>FD_COMPUTE_BUDGET_MAX_HEAP_FRAME_BYTES ) ) return 0;
115 36 : state->heap_size = heap_size;
116 36 : state->flags |= FD_COMPUTE_BUDGET_PROGRAM_FLAG_SET_HEAP;
117 36 : state->compute_budget_instr_cnt++;
118 36 : return 1;
119 3850968 : case 2:
120 : /* Parse a SetComputeUnitLimit instruction */
121 3850968 : if( FD_UNLIKELY( data_sz<5 ) ) return 0;
122 3850968 : if( FD_UNLIKELY( (state->flags & FD_COMPUTE_BUDGET_PROGRAM_FLAG_SET_CU)!=0 ) ) return 0;
123 3850965 : state->compute_units = FD_LOAD( uint, instr_data+1 );
124 3850965 : state->compute_units = fd_uint_min( state->compute_units, FD_COMPUTE_BUDGET_MAX_CU_LIMIT );
125 3850965 : state->flags |= FD_COMPUTE_BUDGET_PROGRAM_FLAG_SET_CU;
126 3850965 : state->compute_budget_instr_cnt++;
127 3850965 : return 1;
128 3850770 : case 3:
129 : /* Parse a SetComputeUnitPrice instruction */
130 3850770 : if( FD_UNLIKELY( data_sz<9 ) ) return 0;
131 3850770 : if( FD_UNLIKELY( (state->flags & FD_COMPUTE_BUDGET_PROGRAM_FLAG_SET_FEE)!=0 ) ) return 0;
132 3850767 : state->micro_lamports_per_cu = FD_LOAD( ulong, instr_data+1 );
133 3850767 : state->flags |= FD_COMPUTE_BUDGET_PROGRAM_FLAG_SET_FEE;
134 3850767 : state->compute_budget_instr_cnt++;
135 3850767 : return 1;
136 3850731 : case 4:
137 : /* Parse a SetLoadedAccountsDataSizeLimit instruction */
138 3850731 : if( FD_UNLIKELY( data_sz<5 ) ) return 0;
139 3850731 : if( FD_UNLIKELY( (state->flags & FD_COMPUTE_BUDGET_PROGRAM_FLAG_SET_LOADED_DATA_SZ)!=0 ) ) return 0;
140 3850728 : state->loaded_acct_data_sz = FD_LOAD( uint, instr_data+1 );
141 3850728 : if( FD_UNLIKELY( state->loaded_acct_data_sz==0U ) ) return 0;
142 3850728 : state->loaded_acct_data_sz = fd_uint_min( state->loaded_acct_data_sz, FD_COMPUTE_BUDGET_MAX_LOADED_DATA_SZ );
143 3850728 : state->flags |= FD_COMPUTE_BUDGET_PROGRAM_FLAG_SET_LOADED_DATA_SZ;
144 3850728 : state->compute_budget_instr_cnt++;
145 3850728 : return 1;
146 3 : default:
147 3 : return 0;
148 11552550 : }
149 11552550 : }
150 :
151 : /* fd_compute_budget_program_finalize: digests the state that resulted
152 : from processing all of the ComputeBudgetProgram instructions in a
153 : transaction to compute the total priority rewards for the
154 : transaction. state must point to a previously initialized
155 : fd_compute_budget_program_state_t. instr_cnt is the total number of
156 : instructions in the transaction, including ComputeBudgetProgram
157 : instructions. builtin_instr_cnt is the total number of builtin
158 : instructions in the transaction. The set of builtin instructions is
159 : dependent on both the agave codebase and active feature flags. This
160 : codebase uses a hardcoded list of instructions that should be updated
161 : to exclude instructions as they are migrated to non-builtin status.
162 : out_rewards, out_compute and out_loaded_account_data_cost must be
163 : non-null. The total priority rewards for the transaction (i.e. not
164 : counting the per-signature fee) is stored in out_rewards. The
165 : maximum number of compute units this transaction can consume is
166 : stored in out_compute. If the transaction execution has not
167 : completed by this limit, it is terminated and considered failed. The
168 : compute unit cost of loading the transaction's account data is
169 : stored in out_loaded_account_data_cost. */
170 : static inline void
171 : fd_compute_budget_program_finalize( fd_compute_budget_program_state_t const * state,
172 : ulong instr_cnt,
173 : ulong builtin_instr_cnt,
174 : ulong * out_rewards,
175 : uint * out_compute,
176 3855657 : ulong * out_loaded_account_data_cost ) {
177 3855657 : ulong cu_limit = 0UL;
178 3855657 : if( FD_LIKELY( (state->flags & FD_COMPUTE_BUDGET_PROGRAM_FLAG_SET_CU)==0U ) ) {
179 : /* Use default compute limit */
180 4716 : cu_limit = (instr_cnt - builtin_instr_cnt) * FD_COMPUTE_BUDGET_DEFAULT_INSTR_CU_LIMIT + builtin_instr_cnt * FD_COMPUTE_BUDGET_MAX_BUILTIN_CU_LIMIT;
181 3850941 : } else cu_limit = state->compute_units;
182 :
183 3855657 : cu_limit = fd_ulong_min( cu_limit, FD_COMPUTE_BUDGET_MAX_CU_LIMIT );
184 :
185 3855657 : *out_compute = (uint)cu_limit;
186 :
187 3855657 : ulong loaded_accounts_data_size = 0UL;
188 3855657 : if( FD_LIKELY( (state->flags & FD_COMPUTE_BUDGET_PROGRAM_FLAG_SET_LOADED_DATA_SZ)==0U ) ) {
189 : /* Use default loaded account data size */
190 4944 : loaded_accounts_data_size = FD_COMPUTE_BUDGET_MAX_LOADED_DATA_SZ;
191 3850713 : } else loaded_accounts_data_size = state->loaded_acct_data_sz;
192 :
193 : /* https://github.com/firedancer-io/agave/blob/927c6d30ed5e1baea30c06ebf2aa0c9bae0e1dd1/sdk/fee-structure/src/lib.rs#L122-L129
194 :
195 : loaded_accounts_data_size <= FD_COMPUTE_BUDGET_MAX_LOADED_DATA_SZ
196 : means no overflow */
197 3855657 : ulong loaded_accounts_data_cost = FD_COMPUTE_BUDGET_HEAP_COST * ( (
198 3855657 : loaded_accounts_data_size + ( FD_COMPUTE_BUDGET_ACCOUNT_DATA_COST_PAGE_SIZE - 1UL )
199 3855657 : ) / FD_COMPUTE_BUDGET_ACCOUNT_DATA_COST_PAGE_SIZE );
200 3855657 : *out_loaded_account_data_cost = loaded_accounts_data_cost;
201 :
202 3855657 : ulong total_fee = 0UL;
203 :
204 : /* We need to compute min(ceil((cu_limit * micro_lamports_per_cu)/10^6),
205 : ULONG_MAX). Unfortunately, the product can overflow. Solana solves
206 : this by doing the arithmetic with ultra-wide integers, but that puts a
207 : 128-bit division on the critical path. Gross. It's frustrating because
208 : the overflow case likely results in a transaction that's so expensive
209 : nobody can afford it anyways, but we should not break compatibility with
210 : Solana over this. Instead we'll do the arithmetic carefully:
211 : Let cu_limit = c_h*10^6 + c_l, where 0 <= c_l < 10^6.
212 : Similarly, let micro_lamports_per_cu = p_h*10^6 + p_l, where
213 : 0 <= p_l < 10^6. Since cu_limit < 2^32, c_h < 2^13;
214 : micro_lamports_per_cu < 2^64, so p_h<2^45.
215 :
216 : ceil( (cu_limit * micro_lamports_per_cu)/10^6)
217 : = ceil( ((c_h*10^6+c_l)*(p_h*10^6+p_l))/10^6 )
218 : = c_h*p_h*10^6 + c_h*p_l + c_l*p_h + ceil( (c_l*p_l)/10^6 )
219 : c_h*p_h < 2^58, so we can compute it with normal multiplication.
220 : If c_h*p_h > floor(ULONG_MAX/10^6), then we know c_h*p_h*10^6 will hit
221 : the saturation point. The "cross" terms are less than 2^64 by
222 : construction (since we divided by 10^6 and then multiply by something
223 : strictly less than 10^6). c_l*p_l < 10^12 < 2^40, so that's safe as
224 : well.
225 : In fact, the sum of the right three terms is no larger than:
226 : floor((2^32-1)/10^6)*(10^6-1) + (10^6-1)*floor((2^64-1)/10^6) + 10^6-1
227 : == 0xffffef3a08574e4c < 2^64, so we can do the additions without
228 : worrying about overflow.
229 : Of course, we still need to check the final addition of the first term
230 : with the remaining terms. As a bonus, all of the divisions can now be
231 : done via "magic multiplication."
232 :
233 : Note that this computation was done before I was aware of the
234 : 1.4M CU limit. Taking that limit into account could make the
235 : code a little cleaner, but we'll just keep the version that
236 : supports CU limits up to UINT_MAX, since I'm sure the limit will
237 : go up someday. */
238 3855657 : do {
239 3855657 : ulong c_h = cu_limit / FD_COMPUTE_BUDGET_MICRO_LAMPORTS_PER_LAMPORT;
240 3855657 : ulong c_l = cu_limit % FD_COMPUTE_BUDGET_MICRO_LAMPORTS_PER_LAMPORT;
241 3855657 : ulong p_h = state->micro_lamports_per_cu / FD_COMPUTE_BUDGET_MICRO_LAMPORTS_PER_LAMPORT;
242 3855657 : ulong p_l = state->micro_lamports_per_cu % FD_COMPUTE_BUDGET_MICRO_LAMPORTS_PER_LAMPORT;
243 :
244 3855657 : ulong hh = c_h * p_h;
245 3855657 : if( FD_UNLIKELY( hh>(ULONG_MAX/FD_COMPUTE_BUDGET_MICRO_LAMPORTS_PER_LAMPORT) ) ) {
246 0 : total_fee = ULONG_MAX;
247 0 : break;
248 0 : }
249 3855657 : hh *= FD_COMPUTE_BUDGET_MICRO_LAMPORTS_PER_LAMPORT;
250 :
251 3855657 : ulong hl = c_h*p_l + c_l*p_h;
252 3855657 : ulong ll = (c_l*p_l + FD_COMPUTE_BUDGET_MICRO_LAMPORTS_PER_LAMPORT - 1UL)/FD_COMPUTE_BUDGET_MICRO_LAMPORTS_PER_LAMPORT;
253 3855657 : ulong right_three_terms = hl + ll;
254 :
255 3855657 : total_fee = hh + right_three_terms;
256 3855657 : if( FD_UNLIKELY( total_fee<hh ) ) total_fee = ULONG_MAX;
257 3855657 : } while( 0 );
258 3855657 : *out_rewards = total_fee;
259 3855657 : }
260 :
261 : #endif /* HEADER_fd_src_disco_pack_fd_compute_budget_program_h */
|
