LCOV - code coverage report
Current view: top level - disco/pack - fd_compute_budget_program.h (source / functions) Hit Total Coverage
Test: cov.lcov Lines: 86 90 95.6 %
Date: 2025-03-20 12:08:36 Functions: 9 27 33.3 %

          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 "../../ballet/fd_ballet_base.h"
       4             : #include "../../ballet/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    15006381 : #define FD_COMPUTE_BUDGET_PROGRAM_FLAG_SET_CU             ((ushort)0x01) /* ... SetComputeUnitLimit ... */
      22     1433286 : #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     1407897 : #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    95189367 : #define FD_COMPUTE_BUDGET_MICRO_LAMPORTS_PER_LAMPORT     (    1000000UL)
      43             : 
      44    39311400 : #define FD_COMPUTE_BUDGET_DEFAULT_INSTR_CU_LIMIT         (     200000UL)
      45    28604862 : #define FD_COMPUTE_BUDGET_MAX_CU_LIMIT                   (    1400000UL)
      46    13598481 : #define FD_COMPUTE_BUDGET_HEAP_COST                      (          8UL)
      47    27196962 : #define FD_COMPUTE_BUDGET_ACCOUNT_DATA_COST_PAGE_SIZE    (32UL * 1024UL)
      48             : 
      49             : /* Max loaded data size is 64 MiB */
      50    13598496 : #define FD_COMPUTE_BUDGET_MAX_LOADED_DATA_SZ    (64UL*1024UL*1024UL)
      51             : 
      52             : /* ---- End consensus-critical constants */
      53             : 
      54             : 
      55             : struct fd_compute_budget_program_private_state {
      56             :   /* flags: Which instructions have been parsed so far in this transaction? See
      57             :      above for their meaning. */
      58             :   ushort  flags;
      59             :   /* compute_budge_instr_cnt: How many compute budget instructions have been
      60             :      parsed so far? compute_budget_instr_cnt in [0, 4]. */
      61             :   ushort  compute_budget_instr_cnt;
      62             :   /* compute_units: if SET_CU is in flags, this stores the total requested
      63             :      compute units for the whole transaction. Otherwise 0. Realistically should
      64             :      be less than 12M, but there's nothing enforcing that at this stage. */
      65             :   uint    compute_units;
      66             :   /* loaded_acct_data_sz: if SET_LOADED_DATA_SZ is in flags, this stores
      67             :      the max total data (in bytes) that the transaction will load from
      68             :      the accounts it references.  Otherwise, 0. */
      69             :   uint    loaded_acct_data_sz;
      70             :   /* heap_size: if SET_HEAP is in flags, this stores the size in bytes of the
      71             :      BPF heap used for executing this transaction. Otherwise, 0. Must be a
      72             :      multiple of 1024. */
      73             :   uint    heap_size;
      74             :   /* micro_lamports_per_cu: if SET_FEE is in flags, this stores the
      75             :      requested prioritization fee in micro-lamports per compute unit.
      76             :      Otherwise, 0. */
      77             :   ulong   micro_lamports_per_cu;
      78             : };
      79             : typedef struct fd_compute_budget_program_private_state fd_compute_budget_program_state_t;
      80             : 
      81             : /* fd_compute_budge_program_init: initializes an
      82             :    fd_compute_budget_program_state_t to prepare it for parsing a transaction.
      83             :    Also equivalent to just initializing the state on the stack with = {0}. */
      84    13635654 : static inline void fd_compute_budget_program_init( fd_compute_budget_program_state_t * state ) {
      85    13635654 :   *state = (fd_compute_budget_program_state_t) {0};
      86    13635654 : }
      87             : /* fd_compute_budget_program_parse: Parses a single ComputeBudgetProgram
      88             :    instruction.  Updates the state stored in state.  Returns 0 if the
      89             :    instruction was invalid, which means the transaction should fail.
      90             :    instr_data points to the first byte of the instruction data from the
      91             :    transaction.  data_sz specifies the length of the instruction data, so
      92             :    instr_data[ i ] for i in [0, data_sz) gives the instruction data. */
      93             : static inline int
      94             : fd_compute_budget_program_parse( uchar const * instr_data,
      95             :                                  ulong         data_sz,
      96     4274523 :                                  fd_compute_budget_program_state_t * state ) {
      97     4274523 :   if( FD_UNLIKELY( data_sz<5 ) ) return 0;
      98     4274523 :   switch( *instr_data ) {
      99          18 :     case 0:
     100             :       /* Formerly RequestUnitsDeprecated, but invalid since
     101             :          EfhYd3SafzGT472tYQDUc4dPd2xdEfKs5fwkowUgVt4W. */
     102          18 :       return 0;
     103          21 :     case 1:
     104             :       /* Parse a RequestHeapFrame instruction */
     105          21 :       if( FD_UNLIKELY( data_sz<5 ) ) return 0;
     106          21 :       if( FD_UNLIKELY( (state->flags & FD_COMPUTE_BUDGET_PROGRAM_FLAG_SET_HEAP)!=0 ) ) return 0;
     107          21 :       state->heap_size = FD_LOAD( uint, instr_data+1 );
     108          21 :       if( (state->heap_size%FD_COMPUTE_BUDGET_HEAP_FRAME_GRANULARITY) ) return 0;
     109          21 :       state->flags |= FD_COMPUTE_BUDGET_PROGRAM_FLAG_SET_HEAP;
     110          21 :       state->compute_budget_instr_cnt++;
     111          21 :       return 1;
     112     1433292 :     case 2:
     113             :       /* Parse a SetComputeUnitLimit instruction */
     114     1433292 :       if( FD_UNLIKELY( data_sz<5 ) ) return 0;
     115     1433292 :       if( FD_UNLIKELY( (state->flags & FD_COMPUTE_BUDGET_PROGRAM_FLAG_SET_CU)!=0 ) ) return 0;
     116     1433289 :       state->compute_units = FD_LOAD( uint, instr_data+1 );
     117     1433289 :       state->compute_units = fd_uint_min( state->compute_units, FD_COMPUTE_BUDGET_MAX_CU_LIMIT );
     118     1433289 :       state->flags |= FD_COMPUTE_BUDGET_PROGRAM_FLAG_SET_CU;
     119     1433289 :       state->compute_budget_instr_cnt++;
     120     1433289 :       return 1;
     121     1433289 :     case 3:
     122             :       /* Parse a SetComputeUnitPrice instruction */
     123     1433289 :       if( FD_UNLIKELY( data_sz<9 ) ) return 0;
     124     1433289 :       if( FD_UNLIKELY( (state->flags & FD_COMPUTE_BUDGET_PROGRAM_FLAG_SET_FEE)!=0 ) ) return 0;
     125     1433286 :       state->micro_lamports_per_cu = FD_LOAD( ulong, instr_data+1 );
     126     1433286 :       state->flags |= FD_COMPUTE_BUDGET_PROGRAM_FLAG_SET_FEE;
     127     1433286 :       state->compute_budget_instr_cnt++;
     128     1433286 :       return 1;
     129     1407900 :     case 4:
     130             :       /* Parse a SetLoadedAccountsDataSizeLimit instruction */
     131     1407900 :       if( FD_UNLIKELY( data_sz<5 ) ) return 0;
     132     1407900 :       if( FD_UNLIKELY( (state->flags & FD_COMPUTE_BUDGET_PROGRAM_FLAG_SET_LOADED_DATA_SZ)!=0 ) ) return 0;
     133     1407897 :       state->loaded_acct_data_sz = FD_LOAD( uint, instr_data+1 );
     134     1407897 :       if( FD_UNLIKELY( state->loaded_acct_data_sz==0U ) ) return 0;
     135     1407897 :       state->loaded_acct_data_sz = fd_uint_min( state->loaded_acct_data_sz, FD_COMPUTE_BUDGET_MAX_LOADED_DATA_SZ );
     136     1407897 :       state->flags |= FD_COMPUTE_BUDGET_PROGRAM_FLAG_SET_LOADED_DATA_SZ;
     137     1407897 :       state->compute_budget_instr_cnt++;
     138     1407897 :       return 1;
     139           3 :     default:
     140           3 :       return 0;
     141     4274523 :   }
     142     4274523 : }
     143             : 
     144             : /* fd_compute_budget_program_finalize: digests the state that resulted from
     145             :    processing all of the ComputeBudgetProgram instructions in a transaction to
     146             :    compute the total priority rewards for the transaction.  state must point to
     147             :    a previously initialized fd_compute_budget_program_state_t.  instr_cnt is the
     148             :    total number of instructions in the transaction, including
     149             :    ComputeBudgetProgram instructions.  out_rewards and out_compute must be
     150             :    non-null.  The total priority rewards for the transaction (i.e. not counting
     151             :    the per-signature fee) is stored in out_rewards.  The maximum number of
     152             :    compute units this transaction can consume is stored in out_compute.  If the
     153             :    transaction execution has not completed by this limit, it is terminated and
     154             :    considered failed. */
     155             : static inline void
     156             : fd_compute_budget_program_finalize( fd_compute_budget_program_state_t const * state,
     157             :                                     ulong                                     instr_cnt,
     158             :                                     ulong *                                   out_rewards,
     159             :                                     uint *                                    out_compute,
     160    13598481 :                                     ulong *                                   out_loaded_account_data_cost ) {
     161    13598481 :   ulong cu_limit = 0UL;
     162    13598481 :   if( FD_LIKELY( (state->flags & FD_COMPUTE_BUDGET_PROGRAM_FLAG_SET_CU)==0U ) ) {
     163             :     /* Use default compute limit */
     164    12165216 :     cu_limit = (instr_cnt - state->compute_budget_instr_cnt) * FD_COMPUTE_BUDGET_DEFAULT_INSTR_CU_LIMIT;
     165    12165216 :   } else cu_limit = state->compute_units;
     166             : 
     167    13598481 :   cu_limit = fd_ulong_min( cu_limit, FD_COMPUTE_BUDGET_MAX_CU_LIMIT );
     168             : 
     169    13598481 :   *out_compute = (uint)cu_limit;
     170             : 
     171    13598481 :   ulong loaded_accounts_data_size = 0UL;
     172    13598481 :   if( FD_LIKELY( (state->flags & FD_COMPUTE_BUDGET_PROGRAM_FLAG_SET_LOADED_DATA_SZ)==0U ) ) {
     173             :     /* Use default loaded account data size */
     174    12190599 :     loaded_accounts_data_size = FD_COMPUTE_BUDGET_MAX_LOADED_DATA_SZ;
     175    12190599 :   } else loaded_accounts_data_size = state->loaded_acct_data_sz;
     176             : 
     177             :   /* https://github.com/firedancer-io/agave/blob/927c6d30ed5e1baea30c06ebf2aa0c9bae0e1dd1/sdk/fee-structure/src/lib.rs#L122-L129
     178             : 
     179             :      loaded_accounts_data_size <= FD_COMPUTE_BUDGET_MAX_LOADED_DATA_SZ
     180             :      means no overflow */
     181    13598481 :   ulong loaded_accounts_data_cost = FD_COMPUTE_BUDGET_HEAP_COST * ( (
     182    13598481 :    loaded_accounts_data_size + ( FD_COMPUTE_BUDGET_ACCOUNT_DATA_COST_PAGE_SIZE - 1UL )
     183    13598481 :   ) / FD_COMPUTE_BUDGET_ACCOUNT_DATA_COST_PAGE_SIZE );
     184    13598481 :   *out_loaded_account_data_cost = loaded_accounts_data_cost;
     185             : 
     186    13598481 :   ulong total_fee = 0UL;
     187             : 
     188             :   /* We need to compute max(ceil((cu_limit * micro_lamports_per_cu)/10^6),
     189             :      ULONG_MAX).  Unfortunately, the product can overflow.  Solana solves
     190             :      this by doing the arithmetic with ultra-wide integers, but that puts a
     191             :      128-bit division on the critical path.  Gross.  It's frustrating because
     192             :      the overflow case likely results in a transaction that's so expensive
     193             :      nobody can afford it anyways, but we should not break compatibility with
     194             :      Solana over this.  Instead we'll do the arithmetic carefully:
     195             :      Let cu_limit = c_h*10^6 + c_l, where 0 <= c_l < 10^6.
     196             :      Similarly, let micro_lamports_per_cu = p_h*10^6 + p_l, where
     197             :      0 <= p_l < 10^6.  Since cu_limit < 2^32, c_h < 2^13;
     198             :      micro_lamports_per_cu < 2^64, so p_h<2^45.
     199             : 
     200             :      ceil( (cu_limit * micro_lamports_per_cu)/10^6)
     201             :      = ceil( ((c_h*10^6+c_l)*(p_h*10^6+p_l))/10^6 )
     202             :      = c_h*p_h*10^6 + c_h*p_l + c_l*p_h + ceil( (c_l*p_l)/10^6 )
     203             :      c_h*p_h < 2^58, so we can compute it with normal multiplication.
     204             :      If c_h*p_h > floor(ULONG_MAX/10^6), then we know c_h*p_h*10^6 will hit
     205             :      the saturation point.  The "cross" terms are less than 2^64 by
     206             :      construction (since we divided by 10^6 and then multiply by something
     207             :      strictly less than 10^6).  c_l*p_l < 10^12 < 2^40, so that's safe as
     208             :      well.
     209             :      In fact, the sum of the right three terms is no larger than:
     210             :      floor((2^32-1)/10^6)*(10^6-1) + (10^6-1)*floor((2^64-1)/10^6) + 10^6-1
     211             :      == 0xffffef3a08574e4c < 2^64, so we can do the additions without
     212             :      worrying about overflow.
     213             :      Of course, we still need to check the final addition of the first term
     214             :      with the remaining terms.  As a bonus, all of the divisions can now be
     215             :      done via "magic multiplication."
     216             : 
     217             :      Note that this computation was done before I was aware of the
     218             :      1.4M CU limit.  Taking that limit into account could make the
     219             :      code a little cleaner, but we'll just keep the version that
     220             :      supports CU limits up to UINT_MAX, since I'm sure the limit will
     221             :      go up someday. */
     222    13598481 :   do {
     223    13598481 :     ulong c_h  =                     cu_limit / FD_COMPUTE_BUDGET_MICRO_LAMPORTS_PER_LAMPORT;
     224    13598481 :     ulong c_l  =                     cu_limit % FD_COMPUTE_BUDGET_MICRO_LAMPORTS_PER_LAMPORT;
     225    13598481 :     ulong p_h  = state->micro_lamports_per_cu / FD_COMPUTE_BUDGET_MICRO_LAMPORTS_PER_LAMPORT;
     226    13598481 :     ulong p_l  = state->micro_lamports_per_cu % FD_COMPUTE_BUDGET_MICRO_LAMPORTS_PER_LAMPORT;
     227             : 
     228    13598481 :     ulong hh = c_h * p_h;
     229    13598481 :     if( FD_UNLIKELY( hh>(ULONG_MAX/FD_COMPUTE_BUDGET_MICRO_LAMPORTS_PER_LAMPORT) ) ) {
     230           0 :       total_fee = ULONG_MAX;
     231           0 :       break;
     232           0 :     }
     233    13598481 :     hh *= FD_COMPUTE_BUDGET_MICRO_LAMPORTS_PER_LAMPORT;
     234             : 
     235    13598481 :     ulong hl = c_h*p_l + c_l*p_h;
     236    13598481 :     ulong ll = (c_l*p_l + FD_COMPUTE_BUDGET_MICRO_LAMPORTS_PER_LAMPORT - 1UL)/FD_COMPUTE_BUDGET_MICRO_LAMPORTS_PER_LAMPORT;
     237    13598481 :     ulong right_three_terms = hl + ll;
     238             : 
     239    13598481 :     total_fee = hh + right_three_terms;
     240    13598481 :     if( FD_UNLIKELY( total_fee<hh ) ) total_fee = ULONG_MAX;
     241    13598481 :   } while( 0 );
     242           0 :   *out_rewards = total_fee;
     243    13598481 : }
     244             : 
     245             : #endif /* HEADER_fd_src_ballet_pack_fd_compute_budget_program_h */

Generated by: LCOV version 1.14