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    12821259 : #define FD_ACCDB_CACHE_CLASS_CNT    (8UL)
      34        3765 : #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      557505 : #define FD_ACCDB_CACHE_LINE_BITS    (29)
      43      377256 : #define FD_ACCDB_CACHE_LINE_MAX     (1UL<<FD_ACCDB_CACHE_LINE_BITS)
      44             : 
      45             : /* min_reserved is supplied at runtime by the caller (see
      46             :    fd_accdb_cache_class_cnt and fd_accdb_shmem_new).  It is the minimum
      47             :    number of slots reserved per class so a worst-case batch of
      48             :    transactions can always execute fully in-memory.
      49             : 
      50             :    The floor is driven by the per-class peak that
      51             :    fd_accdb_acquire_a can atomically increment for the simultaneously-
      52             :    live transactions (a bundle of up to 5).  Per pubkey, per class, the
      53             :    acquire reservation can add up to:
      54             :      +1 for the existing account's own size class (cache read line)
      55             :      +1 for the writable staging buffer (added to EVERY class)
      56             :      +1 for the unknown-programdata placeholder (added to EVERY class,
      57             :          unconditionally per pubkey under MAYBE_PROGRAMDATA)
      58             :    = 3 slots in the worst-case-matching class for a writable account
      59             :    that already exists there.  Solana requires at least one read-only
      60             :    pubkey per txn (the invoked program), which can contribute at most
      61             :    2 (no writable +1 every class), so the per-txn worst case is:
      62             :      63 * 3 + 1 * 2 = 191 slots per class per txn.
      63             : 
      64             :    Bundles enabled:  5 * 191 = 955  (worst case 5-transaction bundle)
      65             :    Bundles disabled:     191       (worst case single transaction)
      66             : 
      67             :    See src/app/firedancer/topology.c for the canonical derivation. */
      68             : 
      69             : static const ulong fd_accdb_cache_slot_sz[ FD_ACCDB_CACHE_CLASS_CNT ] = {
      70             :   128UL+FD_ACCDB_CACHE_META_SZ,      /* class 0: 0-128 B     */
      71             :   512UL+FD_ACCDB_CACHE_META_SZ,      /* class 1: 129-512 B   */
      72             :   2048UL+FD_ACCDB_CACHE_META_SZ,     /* class 2: 513-2 KiB   */
      73             :   8192UL+FD_ACCDB_CACHE_META_SZ,     /* class 3: 2K-8 KiB    */
      74             :   32768UL+FD_ACCDB_CACHE_META_SZ,    /* class 4: 8K-32 KiB   */
      75             :   131072UL+FD_ACCDB_CACHE_META_SZ,   /* class 5: 32K-128 KiB */
      76             :   1048576UL+FD_ACCDB_CACHE_META_SZ,  /* class 6: 128K-1 MiB  */
      77             :   10485760UL+FD_ACCDB_CACHE_META_SZ, /* class 7: 1M-10 MiB   */
      78             : };
      79             : 
      80             : /* fd_accdb_cache_class_cnt computes the number of slots to allocate for
      81             :    each of the 8 size classes, given a total cache memory budget.
      82             : 
      83             :    The cache and staging pools are unified: class 7 slots serve double
      84             :    duty as both cache entries for large accounts and as 10 MiB staging
      85             :    buffers for writable accounts.  On commit, data is copied from the
      86             :    staging slot into a right-sized cache slot and the class 7 slot is
      87             :    released.
      88             : 
      89             :    cache_footprint is the total memory budget in bytes.
      90             : 
      91             :    class_cnt is populated with the slot count for each class on return.
      92             :    The sum of class_cnt[c]*slot_sz[c] will not exceed cache_footprint.
      93             : 
      94             :    Every class gets at least min_reserved entries, guaranteeing a
      95             :    worst-case batch can execute fully in memory regardless of account
      96             :    size mix.  See the min_reserved comment block above for the
      97             :    derivation (currently 192 per concurrently-live transaction).
      98             :    Returns 0 if the budget is too small for these minimums, or 1 on
      99             :    success.
     100             : 
     101             :    The algorithm:
     102             :    1) Reserves min_reserved of each class off the top.
     103             :    2) Reserves additional per-class minimums (at most 1% of remaining
     104             :       budget per class, clamped to [1, 1024] slots).
     105             :    3) Iteratively allocates remaining budget proportional to access
     106             :       density weights derived from mainnet replay data.
     107             :    4) Caps classes at estimated population maximums and redistributes
     108             :       surplus to uncapped classes. */
     109             : 
     110             : int
     111             : fd_accdb_cache_class_cnt( ulong   cache_footprint,
     112             :                           ulong   min_reserved,
     113             :                           ulong * class_cnt );
     114             : 
     115             : ulong
     116             : fd_accdb_cache_class( ulong data_sz );
     117             : 
     118             : #endif /* HEADER_fd_src_flamenco_accdb_fd_accdb_cache_h */