Line data    Source code

       1             : #include "fd_accdb_cache.h"
       2             : 
       3             : #include "../../util/bits/fd_bits.h"
       4             : #include "../../util/log/fd_log.h"
       5             : 
       6             : int
       7             : fd_accdb_cache_class_cnt( ulong   cache_footprint,
       8             :                           ulong   min_reserved,
       9          24 :                           ulong * class_cnt ) {
      10             :   /* Estimated max account population per class on mainnet.  Based on a
      11             :      full mainnet snapshot (1.118B accounts, 363.7 GiB, slot 393863972)
      12             :      with ~20% headroom. */
      13             : 
      14          24 :   static const ulong pop_max_raw[ FD_ACCDB_CACHE_CLASS_CNT ] = {
      15          24 :      215000000UL,  /* class 0: ~16% of accounts   */
      16          24 :     1041000000UL,  /* class 1: ~77.6% of accounts */
      17          24 :       76000000UL,  /* class 2: ~5.6%              */
      18          24 :        8000000UL,  /* class 3: ~0.6%              */
      19          24 :        4000000UL,  /* class 4: ~0.3%              */
      20          24 :         461000UL,  /* class 5: ~0.03%             */
      21          24 :         244000UL,  /* class 6: ~0.02%             */
      22          24 :           5000UL,  /* class 7: ~0.0003%           */
      23          24 :   };
      24             : 
      25             :   /* Hard per-class ceiling: cidx packs only FD_ACCDB_CACHE_LINE_BITS
      26             :      bits of line index, so a class with more than
      27             :      FD_ACCDB_CACHE_LINE_MAX slots would let two distinct lines pack to
      28             :      the same cidx and silently alias on read.  Clamp pop_max[c] to that
      29             :      representable bound before any phase of the allocator consults it.  */
      30          24 :   ulong pop_max[ FD_ACCDB_CACHE_CLASS_CNT ];
      31         216 :   for( ulong c=0UL; c<FD_ACCDB_CACHE_CLASS_CNT; c++ ) {
      32         192 :     pop_max[c] = fd_ulong_min( pop_max_raw[c], FD_ACCDB_CACHE_LINE_MAX );
      33         192 :   }
      34             : 
      35             :   /* Access density weights: total_accesses / slot_size from empirical
      36             :      mainnet replay (1000-slot sample at slot 406546575), adjusted for
      37             :      64-byte header offset when mapping data_sz to stored_sz cache
      38             :      classes.  Higher weight means more cache hits per byte of cache
      39             :      spent.  Classes 6, 7 are floored to 1. */
      40             : 
      41          24 :   static const ulong density[ FD_ACCDB_CACHE_CLASS_CNT ] = {
      42          24 :        25UL,  /* class 0 */
      43          24 :        20UL,  /* class 1 */
      44          24 :        12UL,  /* class 2 */
      45          24 :         7UL,  /* class 3 */
      46          24 :         6UL,  /* class 4 */
      47          24 :         3UL,  /* class 5 */
      48          24 :         1UL,  /* class 6 */
      49          24 :         1UL,  /* class 7 */
      50          24 :   };
      51             : 
      52             :   /* Per-class working-set targets (slot counts).  Derived from p99 of
      53             :      the distinct-pubkey-per-class working set measured over a 32-slot
      54             :      sliding window on the same 1000-slot mainnet sample, with ~25-50%
      55             :      headroom so allocations cover the typical hot set without wasting
      56             :      budget on classes whose live working set is tiny.
      57             : 
      58             :      These are floors used by Phase 2: each class is topped up to
      59             :      ws_target[c] above the Phase 1 base reservation, before
      60             :      density-based distribution.  Phase 3 then distributes any remaining
      61             :      budget by density. */
      62             : 
      63          24 :   static const ulong ws_target[ FD_ACCDB_CACHE_CLASS_CNT ] = {
      64          24 :     16384UL,  /* class 0: p99 ~13.4K, ample headroom (small slots) */
      65          24 :     13000UL,  /* class 1: p99 ~10.4K */
      66          24 :      4096UL,  /* class 2: p99  ~3.2K */
      67          24 :      3072UL,  /* class 3: p99  ~2.0K, was undersized at 1.3K */
      68          24 :      1800UL,  /* class 4: p99  ~1.0K, needs headroom for pre-evict to keep up */
      69          24 :       512UL,  /* class 5: p99    ~66, was wastefully sized at 1.3K */
      70          24 :       704UL,  /* class 6: p99   ~212 */
      71          24 :       544UL,  /* class 7: p99   ~179; staging covered by MIN_RESERVED */
      72          24 :   };
      73             : 
      74          24 :   ulong slot_sz_sum = ( fd_accdb_cache_slot_sz[ 0UL ] +
      75          24 :                         fd_accdb_cache_slot_sz[ 1UL ] +
      76          24 :                         fd_accdb_cache_slot_sz[ 2UL ] +
      77          24 :                         fd_accdb_cache_slot_sz[ 3UL ] +
      78          24 :                         fd_accdb_cache_slot_sz[ 4UL ] +
      79          24 :                         fd_accdb_cache_slot_sz[ 5UL ] +
      80          24 :                         fd_accdb_cache_slot_sz[ 6UL ] +
      81          24 :                         fd_accdb_cache_slot_sz[ 7UL ] );
      82             : 
      83             :   /* min_reserved is a runtime parameter; guard the Phase-1 cost
      84             :      multiplication against overflow before it wraps and makes the
      85             :      "budget too small" check below misbehave (a wrapped small value
      86             :      would pass the check and yield bogus class counts). */
      87          24 :   if( FD_UNLIKELY( min_reserved>ULONG_MAX/slot_sz_sum ) ) {
      88           0 :     FD_LOG_WARNING(( "cache_min_reserved %lu too large (overflows minimum cost)", min_reserved ));
      89           0 :     for( ulong c=0UL; c<FD_ACCDB_CACHE_CLASS_CNT; c++ ) class_cnt[ c ] = 0UL;
      90           0 :     return 0;
      91           0 :   }
      92             : 
      93          24 :   ulong minimum_cost = min_reserved * slot_sz_sum;
      94             : 
      95          24 :   if( FD_UNLIKELY( cache_footprint<minimum_cost ) ) {
      96             :     /* Budget too small to meet minimum requirement.  Return 0 to
      97             :        indicate failure. */
      98           0 :     FD_LOG_WARNING(( "cache_footprint must be at least %lu GiB to meet minimum requirements", (minimum_cost+(1UL<<30UL)-1)/(1UL<<30UL) ));
      99           0 :     FD_LOG_WARNING(( "%lu<%lu", cache_footprint, minimum_cost ));
     100           0 :     for( ulong c=0UL; c<FD_ACCDB_CACHE_CLASS_CNT; c++ ) class_cnt[ c ] = 0UL;
     101           0 :     return 0;
     102           0 :   }
     103             : 
     104             :   /* Phase 1: Reserve min_reserved of each class off the top.  This
     105             :      guarantees the worst-case batch (64 accounts per transaction,
     106             :      doubled to cover programdata, multiplied by max simultaneous
     107             :      transactions) can execute fully in memory.  Each referenced account
     108             :      reserves one slot in its own class plus one slot for its
     109             :      programdata account, which may land in any class.  Worst case all
     110             :      referenced accounts and all programdata accounts land in the same
     111             :      class. */
     112             : 
     113          24 :   ulong remaining = cache_footprint;
     114         216 :   for( ulong c=0UL; c<FD_ACCDB_CACHE_CLASS_CNT; c++ ) {
     115         192 :     class_cnt[c] = min_reserved;
     116         192 :     remaining   -= min_reserved * fd_accdb_cache_slot_sz[c];
     117         192 :   }
     118             : 
     119             :   /* Phase 2: Reserve up to ws_target[c] slots per class as a floor.
     120             :      Phase 1 already gave each class min_reserved slots; here we top up
     121             :      to ws_target[c] (or as much as remaining budget allows).  This
     122             :      keeps tiny working sets (128K/1M/10M classes) from being
     123             :      over-allocated and frees budget for hotter classes (8K, 2K) in
     124             :      Phase 3. */
     125             : 
     126         216 :   for( ulong c=0UL; c<FD_ACCDB_CACHE_CLASS_CNT; c++ ) {
     127         192 :     if( ws_target[c]<=class_cnt[c] ) continue;
     128         120 :     ulong want = ws_target[c] - class_cnt[c];
     129         120 :     want = fd_ulong_min( want, pop_max[c]>class_cnt[c] ? pop_max[c]-class_cnt[c] : 0UL );
     130         120 :     ulong cost = want * fd_accdb_cache_slot_sz[c];
     131         120 :     if( FD_UNLIKELY( cost>remaining ) ) {
     132           0 :       class_cnt[c] += remaining / fd_accdb_cache_slot_sz[c];
     133           0 :       remaining     = 0UL;
     134         120 :     } else {
     135         120 :       class_cnt[c] += want;
     136         120 :       remaining    -= cost;
     137         120 :     }
     138         120 :   }
     139             : 
     140             :   /* Phase 3: Iteratively allocate remaining budget proportional
     141             :      to access density.  When a class exceeds its population cap,
     142             :      freeze it and redistribute surplus to uncapped classes. */
     143             : 
     144          24 :   int capped[ FD_ACCDB_CACHE_CLASS_CNT ];
     145         216 :   for( ulong c=0UL; c<FD_ACCDB_CACHE_CLASS_CNT; c++ ) capped[c] = 0;
     146             : 
     147          24 :   for( ulong iter=0UL; iter<FD_ACCDB_CACHE_CLASS_CNT && remaining; iter++ ) {
     148          24 :     ulong total_w = 0UL;
     149         216 :     for( ulong c=0UL; c<FD_ACCDB_CACHE_CLASS_CNT; c++ )
     150         192 :       if( !capped[c] ) total_w += density[c];
     151          24 :     if( FD_UNLIKELY( !total_w ) ) break;
     152             : 
     153          24 :     int any_capped = 0;
     154         216 :     for( ulong c=0UL; c<FD_ACCDB_CACHE_CLASS_CNT; c++ ) {
     155         192 :       if( capped[c] ) continue;
     156         192 :       ulong budget = remaining * density[c] / total_w;
     157         192 :       ulong extra  = budget / fd_accdb_cache_slot_sz[c];
     158         192 :       if( class_cnt[c]+extra >= pop_max[c] ) {
     159           0 :         ulong added  = pop_max[c] - class_cnt[c];
     160           0 :         class_cnt[c] = pop_max[c];
     161           0 :         remaining   -= added * fd_accdb_cache_slot_sz[c];
     162           0 :         capped[c]    = 1;
     163           0 :         any_capped   = 1;
     164           0 :       }
     165         192 :     }
     166             : 
     167          24 :     if( !any_capped ) {
     168             :       /* No caps hit.  Final proportional allocation. */
     169          24 :       total_w = 0UL;
     170         216 :       for( ulong c=0UL; c<FD_ACCDB_CACHE_CLASS_CNT; c++ )
     171         192 :         if( !capped[c] ) total_w += density[c];
     172          24 :       if( FD_UNLIKELY( !total_w ) ) break;
     173         216 :       for( ulong c=0UL; c<FD_ACCDB_CACHE_CLASS_CNT; c++ ) {
     174         192 :         if( capped[c] ) continue;
     175         192 :         ulong budget = remaining * density[c] / total_w;
     176         192 :         class_cnt[c] += budget / fd_accdb_cache_slot_sz[c];
     177         192 :       }
     178          24 :       break;
     179          24 :     }
     180          24 :   }
     181             : 
     182             :   /* Phase 4: If all classes hit their population caps, there may
     183             :      still be remaining budget.  The accounts database can grow at
     184             :      runtime, so distribute excess uncapped, proportional to
     185             :      density.  This ensures we always use the full cache budget
     186             :      the operator gave us, up to the per-class cidx ceiling
     187             :      (FD_ACCDB_CACHE_LINE_MAX, enforced via the capped[] array). */
     188             : 
     189          24 :   remaining = cache_footprint;
     190         216 :   for( ulong c=0UL; c<FD_ACCDB_CACHE_CLASS_CNT; c++ )
     191         192 :     remaining -= class_cnt[c] * fd_accdb_cache_slot_sz[c];
     192             : 
     193         216 :   for( ulong c=0UL; c<FD_ACCDB_CACHE_CLASS_CNT; c++ ) capped[c] = class_cnt[c]>=FD_ACCDB_CACHE_LINE_MAX;
     194             : 
     195          24 :   for( ulong iter=0UL; iter<FD_ACCDB_CACHE_CLASS_CNT && remaining; iter++ ) {
     196          24 :     ulong total_w = 0UL;
     197         216 :     for( ulong c=0UL; c<FD_ACCDB_CACHE_CLASS_CNT; c++ ) {
     198         192 :       if( !capped[c] ) total_w += density[c];
     199         192 :     }
     200          24 :     if( FD_UNLIKELY( !total_w ) ) break;
     201             : 
     202          24 :     int any_capped = 0;
     203         216 :     for( ulong c=0UL; c<FD_ACCDB_CACHE_CLASS_CNT; c++ ) {
     204         192 :       if( capped[c] ) continue;
     205         192 :       ulong budget = remaining * density[c] / total_w;
     206         192 :       ulong extra  = budget / fd_accdb_cache_slot_sz[c];
     207         192 :       if( class_cnt[c]+extra >= FD_ACCDB_CACHE_LINE_MAX ) {
     208           0 :         ulong added  = FD_ACCDB_CACHE_LINE_MAX - class_cnt[c];
     209           0 :         class_cnt[c] = FD_ACCDB_CACHE_LINE_MAX;
     210           0 :         remaining   -= added * fd_accdb_cache_slot_sz[c];
     211           0 :         capped[c]    = 1;
     212           0 :         any_capped   = 1;
     213           0 :       }
     214         192 :     }
     215             : 
     216          24 :     if( !any_capped ) {
     217          24 :       total_w = 0UL;
     218         216 :       for( ulong c=0UL; c<FD_ACCDB_CACHE_CLASS_CNT; c++ ) {
     219         192 :         if( !capped[c] ) total_w += density[c];
     220         192 :       }
     221          24 :       if( FD_UNLIKELY( !total_w ) ) break;
     222         216 :       for( ulong c=0UL; c<FD_ACCDB_CACHE_CLASS_CNT; c++ ) {
     223         192 :         if( capped[c] ) continue;
     224         192 :         ulong budget = remaining * density[c] / total_w;
     225         192 :         ulong extra  = budget / fd_accdb_cache_slot_sz[c];
     226         192 :         extra        = fd_ulong_min( extra, FD_ACCDB_CACHE_LINE_MAX - class_cnt[c] );
     227         192 :         class_cnt[c] += extra;
     228         192 :         remaining    -= extra * fd_accdb_cache_slot_sz[c];
     229         192 :       }
     230          24 :       break;
     231          24 :     }
     232          24 :   }
     233             : 
     234             :   /* Spend any per-class integer-division truncation slack left after
     235             :      Phase 4.  Walk uncapped classes in descending density order and
     236             :      add as many slots as fit, capped at FD_ACCDB_CACHE_LINE_MAX.  This
     237             :      converges in at most one pass per class because each iteration
     238             :      either fills the class to LINE_MAX or drains remaining below
     239             :      slot_sz[c]. */
     240         216 :   for( ulong c=0UL; c<FD_ACCDB_CACHE_CLASS_CNT && remaining; c++ ) {
     241         192 :     if( class_cnt[c]>=FD_ACCDB_CACHE_LINE_MAX ) continue;
     242         192 :     ulong room  = FD_ACCDB_CACHE_LINE_MAX - class_cnt[c];
     243         192 :     ulong extra = fd_ulong_min( room, remaining / fd_accdb_cache_slot_sz[c] );
     244         192 :     class_cnt[c] += extra;
     245         192 :     remaining    -= extra * fd_accdb_cache_slot_sz[c];
     246         192 :   }
     247             : 
     248             :   /* Past FD_ACCDB_CACHE_LINE_MAX*slot_sz[c] (~6 TiB) the index space is
     249             :      fully saturated and any further budget is unspendable on cache
     250             :      lines.  Warn the operator so they can size down. */
     251          24 :   ulong unspent = cache_footprint;
     252         216 :   for( ulong c=0UL; c<FD_ACCDB_CACHE_CLASS_CNT; c++ )
     253         192 :     unspent -= class_cnt[c] * fd_accdb_cache_slot_sz[c];
     254          24 :   if( FD_UNLIKELY( unspent >= fd_accdb_cache_slot_sz[ 0UL ] ) ) {
     255           0 :     FD_LOG_WARNING(( "cache_footprint exceeds per-class index space; %lu GiB will be unused (raise FD_ACCDB_CACHE_LINE_BITS to use more)",
     256           0 :                      (unspent+(1UL<<30UL)-1UL)/(1UL<<30UL) ));
     257           0 :   }
     258             : 
     259          24 :   return 1;
     260          24 : }
     261             : 
     262             : ulong
     263     1261767 : fd_accdb_cache_class( ulong data_sz ) {
     264     1261767 :   if( FD_LIKELY( data_sz<=128UL ) ) return 0UL;
     265      262922 :   else if( FD_LIKELY( data_sz<=512UL ) ) return 1UL;
     266      154515 :   else if( FD_LIKELY( data_sz<=2048UL ) ) return 2UL;
     267      127971 :   else if( FD_LIKELY( data_sz<=8192UL ) ) return 3UL;
     268       69140 :   else if( FD_LIKELY( data_sz<=32768UL ) ) return 4UL;
     269       11433 :   else if( FD_LIKELY( data_sz<=131072UL ) ) return 5UL;
     270       12888 :   else if( FD_LIKELY( data_sz<=1048576UL ) ) return 6UL;
     271 >1844*10^16 :   return 7UL;
     272     1261767 : }