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    45055896 : #define FD_ACCDB_CACHE_CLASS_CNT    (8UL)
      34        4104 : #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      630678 : #define FD_ACCDB_CACHE_LINE_BITS    (29)
      43      422124 : #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      305766 : #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.  While program accounts
      76             :      referenced for invocation must be read-only, a transaction with
      77             :      zero instructions is valid, so there need not be an invoked program
      78             :      at all.
      79             :    - We do NOT subtract for the fee payer cannot-be-programdata
      80             :      constraint: the fee payer is still writable and still receives the
      81             :      placeholder reservation at (3) — only an acquire_a code change
      82             :      could exploit that.  Likewise, the read-only program likely lives
      83             :      in a BPF size class (class 3+), but we do not assume which class:
      84             :      we just deduct the writable (2) contribution that any read-only
      85             :      pubkey can never provide.)
      86             : 
      87             :    To summarize:
      88             : 
      89             :    Bundles disabled: 3 *  64 = 192 slots/class (worst case single transaction)
      90             :    Bundles enabled:  5 * 192 = 960 slots/class (worst case 5-transaction bundle)
      91             : 
      92             :    The above works out to ~2.10 GiB minimum cache budget for bundles
      93             :    disabled, and ~10.47 GiB minimum cache budget for bundles enabled. */
      94             : 
      95        4074 : #define FD_ACCDB_CACHE_MIN_RESERVED_TXN (3UL*FD_ACCDB_MAX_TX_ACCOUNT_LOCKS)
      96         234 : #define FD_ACCDB_CACHE_MIN_RESERVED_BUNDLE (3UL*FD_ACCDB_MAX_ACQUIRE_CNT)
      97             : 
      98             : FD_FN_CONST static inline ulong
      99         240 : fd_accdb_cache_min_reserved( int bundle_enabled ) {
     100         240 :   return bundle_enabled ? FD_ACCDB_CACHE_MIN_RESERVED_BUNDLE : FD_ACCDB_CACHE_MIN_RESERVED_TXN;
     101         240 : }
     102             : 
     103             : static const ulong fd_accdb_cache_slot_sz[ FD_ACCDB_CACHE_CLASS_CNT ] = {
     104             :   128UL+FD_ACCDB_CACHE_META_SZ,      /* class 0: 0-128 B     */
     105             :   512UL+FD_ACCDB_CACHE_META_SZ,      /* class 1: 129-512 B   */
     106             :   2048UL+FD_ACCDB_CACHE_META_SZ,     /* class 2: 513-2 KiB   */
     107             :   8192UL+FD_ACCDB_CACHE_META_SZ,     /* class 3: 2K-8 KiB    */
     108             :   32768UL+FD_ACCDB_CACHE_META_SZ,    /* class 4: 8K-32 KiB   */
     109             :   131072UL+FD_ACCDB_CACHE_META_SZ,   /* class 5: 32K-128 KiB */
     110             :   1048576UL+FD_ACCDB_CACHE_META_SZ,  /* class 6: 128K-1 MiB  */
     111             :   10485760UL+FD_ACCDB_CACHE_META_SZ, /* class 7: 1M-10 MiB   */
     112             : };
     113             : 
     114             : /* fd_accdb_cache_class_cnt computes the number of slots to allocate for
     115             :    each of the 8 size classes, given a total cache memory budget.
     116             : 
     117             :    The cache and staging pools are unified: class 7 slots serve double
     118             :    duty as both cache entries for large accounts and as 10 MiB staging
     119             :    buffers for writable accounts.  On commit, data is copied from the
     120             :    staging slot into a right-sized cache slot and the class 7 slot is
     121             :    released.
     122             : 
     123             :    cache_footprint is the total memory budget in bytes.
     124             : 
     125             :    class_cnt is populated with the slot count for each class on return.
     126             :    The sum of class_cnt[c]*slot_sz[c] will not exceed cache_footprint.
     127             : 
     128             :    Every class gets at least min_reserved entries, guaranteeing a
     129             :    worst-case batch can execute fully in memory regardless of account
     130             :    size mix.  See the min_reserved comment block above for the
     131             :    derivation (currently 192 per concurrently-live transaction).
     132             :    Returns 0 if the budget is too small for these minimums, or 1 on
     133             :    success.
     134             : 
     135             :    The algorithm:
     136             :    1) Reserves min_reserved of each class off the top.
     137             :    2) Reserves additional per-class minimums (at most 1% of remaining
     138             :       budget per class, clamped to [1, 1024] slots).
     139             :    3) Iteratively allocates remaining budget proportional to access
     140             :       density weights derived from mainnet replay data.
     141             :    4) Caps classes at estimated population maximums and redistributes
     142             :       surplus to uncapped classes. */
     143             : 
     144             : int
     145             : fd_accdb_cache_class_cnt( ulong   cache_footprint,
     146             :                           ulong   min_reserved,
     147             :                           ulong * class_cnt );
     148             : 
     149             : ulong
     150             : fd_accdb_cache_class( ulong data_sz );
     151             : 
     152             : #endif /* HEADER_fd_src_flamenco_accdb_fd_accdb_cache_h */