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        4044 :                           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        4044 :   static const ulong pop_max_raw[ FD_ACCDB_CACHE_CLASS_CNT ] = {
      15        4044 :      215000000UL,  /* class 0: ~16% of accounts   */
      16        4044 :     1041000000UL,  /* class 1: ~77.6% of accounts */
      17        4044 :       76000000UL,  /* class 2: ~5.6%              */
      18        4044 :        8000000UL,  /* class 3: ~0.6%              */
      19        4044 :        4000000UL,  /* class 4: ~0.3%              */
      20        4044 :         461000UL,  /* class 5: ~0.03%             */
      21        4044 :         244000UL,  /* class 6: ~0.02%             */
      22        4044 :           5000UL,  /* class 7: ~0.0003%           */
      23        4044 :   };
      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        4044 :   ulong pop_max[ FD_ACCDB_CACHE_CLASS_CNT ];
      31       36396 :   for( ulong c=0UL; c<FD_ACCDB_CACHE_CLASS_CNT; c++ ) {
      32       32352 :     pop_max[c] = fd_ulong_min( pop_max_raw[c], FD_ACCDB_CACHE_LINE_MAX );
      33       32352 :   }
      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        4044 :   static const ulong density[ FD_ACCDB_CACHE_CLASS_CNT ] = {
      42        4044 :        25UL,  /* class 0 */
      43        4044 :        20UL,  /* class 1 */
      44        4044 :        12UL,  /* class 2 */
      45        4044 :         7UL,  /* class 3 */
      46        4044 :         6UL,  /* class 4 */
      47        4044 :         3UL,  /* class 5 */
      48        4044 :         1UL,  /* class 6 */
      49        4044 :         1UL,  /* class 7 */
      50        4044 :   };
      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        4044 :   static const ulong ws_target[ FD_ACCDB_CACHE_CLASS_CNT ] = {
      64        4044 :     16384UL,  /* class 0: p99 ~13.4K, ample headroom (small slots) */
      65        4044 :     13000UL,  /* class 1: p99 ~10.4K */
      66        4044 :      4096UL,  /* class 2: p99  ~3.2K */
      67        4044 :      3072UL,  /* class 3: p99  ~2.0K, was undersized at 1.3K */
      68        4044 :      1800UL,  /* class 4: p99  ~1.0K, needs headroom for pre-evict to keep up */
      69        4044 :       512UL,  /* class 5: p99    ~66, was wastefully sized at 1.3K */
      70        4044 :       704UL,  /* class 6: p99   ~212 */
      71        4044 :       544UL,  /* class 7: p99   ~179; staging covered by MIN_RESERVED */
      72        4044 :   };
      73             : 
      74        4044 :   ulong slot_sz_sum = ( fd_accdb_cache_slot_sz[ 0UL ] +
      75        4044 :                         fd_accdb_cache_slot_sz[ 1UL ] +
      76        4044 :                         fd_accdb_cache_slot_sz[ 2UL ] +
      77        4044 :                         fd_accdb_cache_slot_sz[ 3UL ] +
      78        4044 :                         fd_accdb_cache_slot_sz[ 4UL ] +
      79        4044 :                         fd_accdb_cache_slot_sz[ 5UL ] +
      80        4044 :                         fd_accdb_cache_slot_sz[ 6UL ] +
      81        4044 :                         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        4044 :   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        4044 :   ulong minimum_cost = min_reserved * slot_sz_sum;
      94             : 
      95        4044 :   if( FD_UNLIKELY( cache_footprint<minimum_cost ) ) {
      96             :     /* Budget too small to meet minimum requirement.  Return 0 to
      97             :        indicate failure. */
      98          12 :     FD_LOG_WARNING(( "cache_footprint must be at least %lu GiB to meet minimum requirements", (minimum_cost+(1UL<<30UL)-1)/(1UL<<30UL) ));
      99          12 :     FD_LOG_WARNING(( "%lu<%lu", cache_footprint, minimum_cost ));
     100         108 :     for( ulong c=0UL; c<FD_ACCDB_CACHE_CLASS_CNT; c++ ) class_cnt[ c ] = 0UL;
     101          12 :     return 0;
     102          12 :   }
     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        4032 :   ulong remaining = cache_footprint;
     114       36288 :   for( ulong c=0UL; c<FD_ACCDB_CACHE_CLASS_CNT; c++ ) {
     115       32256 :     class_cnt[c] = min_reserved;
     116       32256 :     remaining   -= min_reserved * fd_accdb_cache_slot_sz[c];
     117       32256 :   }
     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       36288 :   for( ulong c=0UL; c<FD_ACCDB_CACHE_CLASS_CNT; c++ ) {
     127       32256 :     if( ws_target[c]<=class_cnt[c] ) continue;
     128       32172 :     ulong want = ws_target[c] - class_cnt[c];
     129       32172 :     want = fd_ulong_min( want, pop_max[c]>class_cnt[c] ? pop_max[c]-class_cnt[c] : 0UL );
     130       32172 :     ulong cost = want * fd_accdb_cache_slot_sz[c];
     131       32172 :     if( FD_UNLIKELY( cost>remaining ) ) {
     132        5070 :       class_cnt[c] += remaining / fd_accdb_cache_slot_sz[c];
     133        5070 :       remaining     = 0UL;
     134       27102 :     } else {
     135       27102 :       class_cnt[c] += want;
     136       27102 :       remaining    -= cost;
     137       27102 :     }
     138       32172 :   }
     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        4032 :   int capped[ FD_ACCDB_CACHE_CLASS_CNT ];
     145       36288 :   for( ulong c=0UL; c<FD_ACCDB_CACHE_CLASS_CNT; c++ ) capped[c] = 0;
     146             : 
     147        4074 :   for( ulong iter=0UL; iter<FD_ACCDB_CACHE_CLASS_CNT && remaining; iter++ ) {
     148          84 :     ulong total_w = 0UL;
     149         756 :     for( ulong c=0UL; c<FD_ACCDB_CACHE_CLASS_CNT; c++ )
     150         672 :       if( !capped[c] ) total_w += density[c];
     151          84 :     if( FD_UNLIKELY( !total_w ) ) break;
     152             : 
     153          75 :     int any_capped = 0;
     154         675 :     for( ulong c=0UL; c<FD_ACCDB_CACHE_CLASS_CNT; c++ ) {
     155         600 :       if( capped[c] ) continue;
     156         459 :       ulong budget = remaining * density[c] / total_w;
     157         459 :       ulong extra  = budget / fd_accdb_cache_slot_sz[c];
     158         459 :       if( class_cnt[c]+extra >= pop_max[c] ) {
     159          81 :         ulong added  = pop_max[c] - class_cnt[c];
     160          81 :         class_cnt[c] = pop_max[c];
     161          81 :         remaining   -= added * fd_accdb_cache_slot_sz[c];
     162          81 :         capped[c]    = 1;
     163          81 :         any_capped   = 1;
     164          81 :       }
     165         459 :     }
     166             : 
     167          75 :     if( !any_capped ) {
     168             :       /* No caps hit.  Final proportional allocation. */
     169          33 :       total_w = 0UL;
     170         297 :       for( ulong c=0UL; c<FD_ACCDB_CACHE_CLASS_CNT; c++ )
     171         264 :         if( !capped[c] ) total_w += density[c];
     172          33 :       if( FD_UNLIKELY( !total_w ) ) break;
     173         297 :       for( ulong c=0UL; c<FD_ACCDB_CACHE_CLASS_CNT; c++ ) {
     174         264 :         if( capped[c] ) continue;
     175         255 :         ulong budget = remaining * density[c] / total_w;
     176         255 :         class_cnt[c] += budget / fd_accdb_cache_slot_sz[c];
     177         255 :       }
     178          33 :       break;
     179          33 :     }
     180          75 :   }
     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        4032 :   remaining = cache_footprint;
     190       36288 :   for( ulong c=0UL; c<FD_ACCDB_CACHE_CLASS_CNT; c++ )
     191       32256 :     remaining -= class_cnt[c] * fd_accdb_cache_slot_sz[c];
     192             : 
     193       36288 :   for( ulong c=0UL; c<FD_ACCDB_CACHE_CLASS_CNT; c++ ) capped[c] = class_cnt[c]>=FD_ACCDB_CACHE_LINE_MAX;
     194             : 
     195        4038 :   for( ulong iter=0UL; iter<FD_ACCDB_CACHE_CLASS_CNT && remaining; iter++ ) {
     196        3915 :     ulong total_w = 0UL;
     197       35235 :     for( ulong c=0UL; c<FD_ACCDB_CACHE_CLASS_CNT; c++ ) {
     198       31320 :       if( !capped[c] ) total_w += density[c];
     199       31320 :     }
     200        3915 :     if( FD_UNLIKELY( !total_w ) ) break;
     201             : 
     202        3915 :     int any_capped = 0;
     203       35235 :     for( ulong c=0UL; c<FD_ACCDB_CACHE_CLASS_CNT; c++ ) {
     204       31320 :       if( capped[c] ) continue;
     205       31299 :       ulong budget = remaining * density[c] / total_w;
     206       31299 :       ulong extra  = budget / fd_accdb_cache_slot_sz[c];
     207       31299 :       if( class_cnt[c]+extra >= FD_ACCDB_CACHE_LINE_MAX ) {
     208           6 :         ulong added  = FD_ACCDB_CACHE_LINE_MAX - class_cnt[c];
     209           6 :         class_cnt[c] = FD_ACCDB_CACHE_LINE_MAX;
     210           6 :         remaining   -= added * fd_accdb_cache_slot_sz[c];
     211           6 :         capped[c]    = 1;
     212           6 :         any_capped   = 1;
     213           6 :       }
     214       31299 :     }
     215             : 
     216        3915 :     if( !any_capped ) {
     217        3909 :       total_w = 0UL;
     218       35181 :       for( ulong c=0UL; c<FD_ACCDB_CACHE_CLASS_CNT; c++ ) {
     219       31272 :         if( !capped[c] ) total_w += density[c];
     220       31272 :       }
     221        3909 :       if( FD_UNLIKELY( !total_w ) ) break;
     222       35181 :       for( ulong c=0UL; c<FD_ACCDB_CACHE_CLASS_CNT; c++ ) {
     223       31272 :         if( capped[c] ) continue;
     224       31257 :         ulong budget = remaining * density[c] / total_w;
     225       31257 :         ulong extra  = budget / fd_accdb_cache_slot_sz[c];
     226       31257 :         extra        = fd_ulong_min( extra, FD_ACCDB_CACHE_LINE_MAX - class_cnt[c] );
     227       31257 :         class_cnt[c] += extra;
     228       31257 :         remaining    -= extra * fd_accdb_cache_slot_sz[c];
     229       31257 :       }
     230        3909 :       break;
     231        3909 :     }
     232        3915 :   }
     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       35304 :   for( ulong c=0UL; c<FD_ACCDB_CACHE_CLASS_CNT && remaining; c++ ) {
     241       31272 :     if( class_cnt[c]>=FD_ACCDB_CACHE_LINE_MAX ) continue;
     242       31257 :     ulong room  = FD_ACCDB_CACHE_LINE_MAX - class_cnt[c];
     243       31257 :     ulong extra = fd_ulong_min( room, remaining / fd_accdb_cache_slot_sz[c] );
     244       31257 :     class_cnt[c] += extra;
     245       31257 :     remaining    -= extra * fd_accdb_cache_slot_sz[c];
     246       31257 :   }
     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        4032 :   ulong unspent = cache_footprint;
     252       36288 :   for( ulong c=0UL; c<FD_ACCDB_CACHE_CLASS_CNT; c++ )
     253       32256 :     unspent -= class_cnt[c] * fd_accdb_cache_slot_sz[c];
     254        4032 :   if( FD_UNLIKELY( unspent >= fd_accdb_cache_slot_sz[ 0UL ] ) ) {
     255           6 :     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           6 :                      (unspent+(1UL<<30UL)-1UL)/(1UL<<30UL) ));
     257           6 :   }
     258             : 
     259        4032 :   return 1;
     260        4044 : }
     261             : 
     262             : ulong
     263      444114 : fd_accdb_cache_class( ulong data_sz ) {
     264      444114 :   if( FD_LIKELY( data_sz<=128UL ) ) return 0UL;
     265      178005 :   else if( FD_LIKELY( data_sz<=512UL ) ) return 1UL;
     266      162405 :   else if( FD_LIKELY( data_sz<=2048UL ) ) return 2UL;
     267      162105 :   else if( FD_LIKELY( data_sz<=8192UL ) ) return 3UL;
     268      119016 :   else if( FD_LIKELY( data_sz<=32768UL ) ) return 4UL;
     269       31080 :   else if( FD_LIKELY( data_sz<=131072UL ) ) return 5UL;
     270       31080 :   else if( FD_LIKELY( data_sz<=1048576UL ) ) return 6UL;
     271        1626 :   return 7UL;
     272      444114 : }