Line data    Source code

       1             : #ifndef HEADER_fd_src_flamenco_accdb_fd_accdb_cache_h
       2             : #define HEADER_fd_src_flamenco_accdb_fd_accdb_cache_h
       3             : 
       4             : #include "../../util/fd_util_base.h"
       5             : 
       6             : /* fd_accdb_cache.h provides a static algorithm for determining, given a
       7             :    fixed size cache_footprint specified by an operator, how to allocate
       8             :    that footprint into various account size classes to maximize expected
       9             :    cache hit while executing.
      10             : 
      11             :    The cache has 8 size classes (to fit in a single cache line) with a
      12             :    x4 geometric progression:
      13             : 
      14             :      Class 0: 0-128 B      (slot: 216 B)
      15             :      Class 1: 129-512 B    (slot: 600 B)
      16             :      Class 2: 513-2 KiB    (slot: 2,136 B)
      17             :      Class 3: 2K-8 KiB     (slot: 8,280 B)
      18             :      Class 4: 8K-32 KiB    (slot: 32,856 B)
      19             :      Class 5: 32K-128 KiB  (slot: 131,160 B)
      20             :      Class 6: 128K-1 MiB   (slot: 1,048,664 B)
      21             :      Class 7: 1M-10 MiB    (slot: 10,485,848 B)
      22             : 
      23             :    Each slot has 88 bytes of fixed metadata overhead
      24             :    (sizeof(fd_accdb_cache_line_t)) on top of the max data capacity
      25             :    for its class.  Slot sizes are 8-byte aligned.
      26             : 
      27             :    The allocation algorithm maximizes expected cache hit rate by
      28             :    distributing budget proportional to access density (observed accesses
      29             :    per byte of cache consumed), derived from empirical mainnet replay.
      30             :    Classes are capped at estimated population maximums to avoid
      31             :    over-provisioning. */
      32             : 
      33    44417709 : #define FD_ACCDB_CACHE_CLASS_CNT    (8UL)
      34        4164 : #define FD_ACCDB_CACHE_META_SZ     (88UL)
      35             : 
      36             : /* Per-class line count ceiling.  The acc cache index packs (class, line)
      37             :    into 32 bits as 3 bits of class and FD_ACCDB_CACHE_LINE_BITS bits of
      38             :    line index (see FD_ACCDB_ACC_CIDX_* in fd_accdb_private.h).  A class
      39             :    may not be sized larger than FD_ACCDB_CACHE_LINE_MAX slots, or two
      40             :    distinct lines would pack to the same cidx and reads would alias. */
      41             : 
      42      640608 : #define FD_ACCDB_CACHE_LINE_BITS    (29)
      43      428673 : #define FD_ACCDB_CACHE_LINE_MAX     (1UL<<FD_ACCDB_CACHE_LINE_BITS)
      44             : 
      45             : /* Maximum accounts a single acquire may request.
      46             :    FD_ACCDB_MAX_TX_ACCOUNT_LOCKS mirrors the mainnet per-transaction
      47             :    account-lock limit.  FD_ACCDB_MAX_TXN_PER_ACQUIRE mirrors
      48             :    FD_PACK_MAX_TXN_PER_BUNDLE, a bundle coalesces up to that many
      49             :    transactions into one acquire. */
      50      316122 : #define FD_ACCDB_MAX_TX_ACCOUNT_LOCKS (64UL)
      51         234 : #define FD_ACCDB_MAX_TXN_PER_ACQUIRE  (5UL)
      52         234 : #define FD_ACCDB_MAX_ACQUIRE_CNT      (FD_ACCDB_MAX_TXN_PER_ACQUIRE*FD_ACCDB_MAX_TX_ACCOUNT_LOCKS)
      53             : 
      54             : /* min_reserved is the minimum number of slots reserved per class so a
      55             :    worst-case batch of transactions can always execute fully in-memory.
      56             : 
      57             :    The floor is driven by the per-class peak that fd_accdb_acquire_a can
      58             :    atomically increment for the simultaneously live transactions (a
      59             :    bundle of up to 5).  Per pubkey, per class, the acquire reservation
      60             :    can add up to:
      61             :      +1 for the existing account's own size class (cache read line)
      62             :      +1 for the writable staging buffer (added to EVERY class)
      63             :      +1 for the unknown-programdata placeholder (added to EVERY class,
      64             :         unconditionally per pubkey under MAYBE_PROGRAMDATA, regardless
      65             :         of writable/existence, refunded later by acquire_b)
      66             :    = 3 slots in the worst-case-matching class for a writable account
      67             :    that already exists there.
      68             : 
      69             :    So worst case (all 64 writable + existing in the same class) gives
      70             :    64 * (1+1+1) = 192 slots per class per transaction.
      71             : 
      72             :    A read-only pubkey contributes at most (1)+(3) = 2 in any class (no
      73             :    writable +1 every class).  Unfortunately
      74             :    - The bundle path acquires every deduped pubkey writable.
      75             :    - We do NOT subtract for a read-only program.  A transaction is free
      76             :      to declare a program as writable.  The writability is demoted
      77             :      unless BPFUpgradeableLoader is present.  That said,
      78             :      BPFUpgradeableLoader is one of the ones that gets demoted.  So if
      79             :      demotion logic happens before acquire (which it is for the
      80             :      non-bundle path), we'd have at least one read-only account.
      81             :      Nonetheless, a transaction with zero instructions is valid, so
      82             :      there need not be an invoked program at all.
      83             :    - We do NOT subtract for the fee payer cannot-be-programdata
      84             :      constraint: the fee payer is still writable and still receives the
      85             :      placeholder reservation at (3) — only an acquire_a code change
      86             :      could exploit that.  Likewise, the read-only program likely lives
      87             :      in a BPF size class (class 3+), but we do not assume which class:
      88             :      we just deduct the writable (2) contribution that any read-only
      89             :      pubkey can never provide.)
      90             : 
      91             :    To summarize:
      92             : 
      93             :    Bundles disabled: 3 *  64 = 192 slots/class (worst case single transaction)
      94             :    Bundles enabled:  5 * 192 = 960 slots/class (worst case 5-transaction bundle)
      95             : 
      96             :    The above works out to ~2.10 GiB minimum cache budget for bundles
      97             :    disabled, and ~10.47 GiB minimum cache budget for bundles enabled. */
      98             : 
      99        4134 : #define FD_ACCDB_CACHE_MIN_RESERVED_TXN (3UL*FD_ACCDB_MAX_TX_ACCOUNT_LOCKS)
     100         234 : #define FD_ACCDB_CACHE_MIN_RESERVED_BUNDLE (3UL*FD_ACCDB_MAX_ACQUIRE_CNT)
     101             : 
     102             : FD_FN_CONST static inline ulong
     103         240 : fd_accdb_cache_min_reserved( int bundle_enabled ) {
     104         240 :   return bundle_enabled ? FD_ACCDB_CACHE_MIN_RESERVED_BUNDLE : FD_ACCDB_CACHE_MIN_RESERVED_TXN;
     105         240 : }
     106             : 
     107             : static const ulong fd_accdb_cache_slot_sz[ FD_ACCDB_CACHE_CLASS_CNT ] = {
     108             :   128UL+FD_ACCDB_CACHE_META_SZ,      /* class 0: 0-128 B     */
     109             :   512UL+FD_ACCDB_CACHE_META_SZ,      /* class 1: 129-512 B   */
     110             :   2048UL+FD_ACCDB_CACHE_META_SZ,     /* class 2: 513-2 KiB   */
     111             :   8192UL+FD_ACCDB_CACHE_META_SZ,     /* class 3: 2K-8 KiB    */
     112             :   32768UL+FD_ACCDB_CACHE_META_SZ,    /* class 4: 8K-32 KiB   */
     113             :   131072UL+FD_ACCDB_CACHE_META_SZ,   /* class 5: 32K-128 KiB */
     114             :   1048576UL+FD_ACCDB_CACHE_META_SZ,  /* class 6: 128K-1 MiB  */
     115             :   10485760UL+FD_ACCDB_CACHE_META_SZ, /* class 7: 1M-10 MiB   */
     116             : };
     117             : 
     118             : /* fd_accdb_cache_class_cnt computes the number of slots to allocate for
     119             :    each of the 8 size classes, given a total cache memory budget.
     120             : 
     121             :    The cache and staging pools are unified: class 7 slots serve double
     122             :    duty as both cache entries for large accounts and as 10 MiB staging
     123             :    buffers for writable accounts.  On commit, data is copied from the
     124             :    staging slot into a right-sized cache slot and the class 7 slot is
     125             :    released.
     126             : 
     127             :    cache_footprint is the total memory budget in bytes.
     128             : 
     129             :    class_cnt is populated with the slot count for each class on return.
     130             :    The sum of class_cnt[c]*slot_sz[c] will not exceed cache_footprint.
     131             : 
     132             :    Every class gets at least min_reserved entries, guaranteeing a
     133             :    worst-case batch can execute fully in memory regardless of account
     134             :    size mix.  See the min_reserved comment block above for the
     135             :    derivation (currently 192 per concurrently-live transaction).
     136             :    Returns 0 if the budget is too small for these minimums, or 1 on
     137             :    success.
     138             : 
     139             :    The algorithm:
     140             :    1) Reserves min_reserved of each class off the top.
     141             :    2) Reserves additional per-class minimums (at most 1% of remaining
     142             :       budget per class, clamped to [1, 1024] slots).
     143             :    3) Iteratively allocates remaining budget proportional to access
     144             :       density weights derived from mainnet replay data.
     145             :    4) Caps classes at estimated population maximums and redistributes
     146             :       surplus to uncapped classes. */
     147             : 
     148             : int
     149             : fd_accdb_cache_class_cnt( ulong   cache_footprint,
     150             :                           ulong   min_reserved,
     151             :                           ulong * class_cnt );
     152             : 
     153             : ulong
     154             : fd_accdb_cache_class( ulong data_sz );
     155             : 
     156             : #endif /* HEADER_fd_src_flamenco_accdb_fd_accdb_cache_h */