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