Line data    Source code

       1             : #ifndef HEADER_fd_src_flamenco_progcache_fd_progcache_h
       2             : #define HEADER_fd_src_flamenco_progcache_fd_progcache_h
       3             : 
       4             : /* fd_progcache.h provides program cache data structures.
       5             : 
       6             :    Records and value slots are one and the same: the record array is
       7             :    partitioned by size class (rec_base[c] .. rec_base[c]+class_max[c]), and a
       8             :    record's value storage is the arena slot at its own index.  Acquiring a
       9             :    record from a class's free list is acquiring its value slot.
      10             : 
      11             :    Lock ordering: spill.lock (outermost, held across a spilled frame's
      12             :    execution), global txn lock, txn lock, recm chain_lock, rec.lock.  An
      13             :    in-flight record's read lock is outside the ordering.  None of these locks
      14             :    prefer writers, so a writer can in principle be starved by readers. */
      15             : 
      16             : #include "fd_progcache_rec.h" /* includes fd_progcache_base.h */
      17             : #include "fd_progcache_cache.h"
      18             : #include "fd_progcache_xid.h"
      19             : #include "../fd_rwlock.h"
      20             : #include "../runtime/fd_runtime_const.h"
      21             : 
      22             : /* Eviction may claim records still attached to a live fork (unlinked under the
      23             :    fork lock); 0 restricts it to rooted records. */
      24             : 
      25             : #ifndef FD_PROGCACHE_EVICT_UNROOTED
      26             : #define FD_PROGCACHE_EVICT_UNROOTED 1
      27             : #endif
      28             : 
      29             : /* fd_progcache_shmem_t is the top-level shared memory data structure
      30             :    of the progcache. */
      31             : 
      32         204 : #define FD_PROGCACHE_SHMEM_MAGIC (0xf17eda2ce7fc2c03UL)
      33             : 
      34             : /* spill.lock serializes spilling, so the spad holds at most one CPI stack:
      35             :    FD_MAX_INSTRUCTION_STACK_DEPTH frames of FD_PROGCACHE_CACHE_SLOT_TOP_SZ. */
      36             : 
      37             : #define FD_PROGCACHE_SPAD_MAX (FD_MAX_INSTRUCTION_STACK_DEPTH * FD_PROGCACHE_CACHE_SLOT_TOP_SZ)
      38             : 
      39             : struct fd_progcache_shmem {
      40             : 
      41             :   ulong magic;
      42             :   ulong wksp_tag;
      43             :   ulong seed;
      44             : 
      45             :   struct {
      46             :     uint  max;        /* == sum of class_max */
      47             :     ulong map_gaddr;
      48             :     ulong ele_gaddr;
      49             :   } rec;
      50             : 
      51             :   struct __attribute__((aligned(64))) {
      52             :     fd_rwlock_t rwlock;
      53             :     ulong       max;
      54             :     ulong       map_gaddr;
      55             :     ulong       pool_gaddr;
      56             :     ulong       ele_gaddr;
      57             :     uint        child_head_idx;
      58             :     uint        child_tail_idx;
      59             :     fd_progcache_fork_id_t root;
      60             :     fd_progcache_fork_id_t seq;
      61             :   } txn;
      62             : 
      63             :   struct {
      64             :     fd_rwlock_t        lock;
      65             :     fd_progcache_rec_t rec[ FD_MAX_INSTRUCTION_STACK_DEPTH ];
      66             :     uint               rec_used;
      67             :     uint               spad_used;
      68             :     uint               spad_off[ FD_MAX_INSTRUCTION_STACK_DEPTH ];
      69             :     uchar              spad[ FD_PROGCACHE_SPAD_MAX ] __attribute__((aligned(64UL)));
      70             :   } spill;
      71             : 
      72             :   /* Size-class cache.  The record array is partitioned by class: class c
      73             :      owns records [rec_base[c], rec_base[c]+class_max[c]), and record idx's value
      74             :      storage is the fixed-size arena slot at (idx - rec_base[c]).  A value is
      75             :      stored in the smallest class whose slot holds it */
      76             :   struct {
      77             :     ulong       class_max  [ FD_PROGCACHE_CACHE_CLASS_CNT ]; /* records per class */
      78             :     ulong       rec_base   [ FD_PROGCACHE_CACHE_CLASS_CNT ]; /* first rec idx of class c */
      79             :     ulong       arena_gaddr[ FD_PROGCACHE_CACHE_CLASS_CNT ]; /* value arena base */
      80             : 
      81             :     /* Per-class free list of records */
      82             :     struct __attribute__((aligned(64))) { ulong ver_top; } free_top[ FD_PROGCACHE_CACHE_CLASS_CNT ];
      83             : 
      84             :     /* Per-class approximate depth of the free list */
      85             :     struct __attribute__((aligned(64))) { ulong val; } free_cnt[ FD_PROGCACHE_CACHE_CLASS_CNT ];
      86             : 
      87             :     /* Per-class CLOCK position */
      88             :     struct __attribute__((aligned(64))) { ulong val; } clock_hand[ FD_PROGCACHE_CACHE_CLASS_CNT ];
      89             : 
      90             :     /* Round-robin cursor for fd_progcache_housekeeping */
      91             :     struct __attribute__((aligned(64))) { ulong val; } housekeep_hand;
      92             :   } cache;
      93             : 
      94             : };
      95             : 
      96             : FD_STATIC_ASSERT( FD_PROGCACHE_SPAD_MAX<=UINT_MAX, "layout" );
      97             : 
      98             : /* Declare a separately-chained concurrent hash map for cache entries */
      99             : 
     100             : #define MAP_NAME              fd_prog_recm
     101        1020 : #define MAP_ELE_T             fd_progcache_rec_t
     102             : #define MAP_KEY_T             fd_progcache_rec_key_t
     103             : #define MAP_KEY               pair
     104     2661849 : #define MAP_KEY_EQ(k0,k1)     fd_progcache_rec_key_eq((k0),(k1))
     105     5497130 : #define MAP_KEY_HASH(k0,seed) fd_progcache_rec_key_hash( &(k0)->prog, (seed) )
     106             : #define MAP_IDX_T             uint
     107        1020 : #define MAP_NEXT              map_next
     108             : #define MAP_MAGIC             (0xf173da2ce77ecdb8UL)
     109             : #define MAP_IMPL_STYLE        1
     110             : #include "../../util/tmpl/fd_map_chain_para.c"
     111             : 
     112             : /* fd_progcache_class_free_cnt returns the number of free records in class c (its
     113             :    free-list depth).  Approximate: a separate atomic from the list head, so it can
     114             :    momentarily disagree with it.  It feeds occupancy gauges. */
     115             : static inline ulong
     116             : fd_progcache_class_free_cnt( fd_progcache_shmem_t * pc,
     117         159 :                              ulong                  c ) {
     118         159 :   return __atomic_load_n( &pc->cache.free_cnt[ c ].val, __ATOMIC_RELAXED );
     119         159 : }
     120             : 
     121             : /* fd_progcache_rec_class returns the size class owning record rec_idx
     122             :    (record ranges are contiguous and ascending by class). */
     123             : 
     124             : static inline ulong
     125             : fd_progcache_rec_class( fd_progcache_shmem_t const * pc,
     126        2052 :                         ulong                        rec_idx ) {
     127        2052 :   ulong c = 0UL;
     128        2052 :   while( c+1UL<FD_PROGCACHE_CACHE_CLASS_CNT && rec_idx >= pc->cache.rec_base[ c+1UL ] ) c++;
     129        2052 :   return c;
     130        2052 : }
     131             : 
     132             : /* Declare a tree / hash map hybrid of fork graph nodes (externally
     133             :    synchronized) */
     134             : 
     135             : struct __attribute__((aligned(64))) fd_progcache_txn {
     136             :   fd_progcache_fork_id_t xid;
     137             :   uint                   map_next;
     138             :   fd_rwlock_t            lock;
     139             :   ushort                 tag : 2;
     140             : 
     141             :   uint   parent_idx;
     142             :   uint   child_head_idx;
     143             :   uint   child_tail_idx;
     144             :   uint   sibling_prev_idx;
     145             :   uint   sibling_next_idx;
     146             : 
     147             :   uint   rec_head_idx;
     148             :   uint   rec_tail_idx;
     149             : };
     150             : 
     151             : #define POOL_NAME       fd_prog_txnp
     152             : #define POOL_T          fd_progcache_txn_t
     153             : #define POOL_IDX_T      uint
     154        9093 : #define POOL_NEXT       map_next
     155             : #define POOL_IMPL_STYLE 1
     156             : #include "../../util/tmpl/fd_pool.c"
     157             : 
     158             : #define  MAP_NAME              fd_prog_txnm
     159             : #define  MAP_ELE_T             fd_progcache_txn_t
     160             : #define  MAP_KEY               xid
     161             : #define  MAP_IDX_T             uint
     162             : #define  MAP_NEXT              map_next
     163             : #define  MAP_MAGIC             (0xf173da2ce77ecdb9UL)
     164             : #define  MAP_IMPL_STYLE        1
     165             : #include "../../util/tmpl/fd_map_chain.c"
     166             : 
     167             : /* Declare fd_progcache_join_t now that we have all dependencies */
     168             : 
     169             : struct fd_progcache_join {
     170             : 
     171             :   fd_progcache_shmem_t * shmem;
     172             : 
     173             :   struct {
     174             :     fd_prog_recm_t       map[1];
     175             :     fd_progcache_rec_t * ele;   /* record array (partitioned by size class) */
     176             :     ulong                max;
     177             :   } rec;
     178             : 
     179             :   struct {
     180             :     fd_prog_txnm_t *     map;
     181             :     fd_progcache_txn_t * pool;
     182             :   } txn;
     183             : 
     184             :   void * data_base;
     185             : 
     186             : };
     187             : 
     188             : /* Snapshots per-class occupancy for metrics.  Both arrays are
     189             :    FD_PROGCACHE_CACHE_CLASS_CNT long. */
     190             : static inline void
     191             : fd_progcache_cache_class_occupancy( fd_progcache_join_t * join,
     192             :                                     ulong *               used,
     193           0 :                                     ulong *               max ) {
     194           0 :   fd_progcache_shmem_t * pc = join->shmem;
     195           0 :   for( ulong c=0UL; c<FD_PROGCACHE_CACHE_CLASS_CNT; c++ ) {
     196           0 :     ulong n = pc->cache.class_max[ c ];
     197             :     /* free_cnt is maintained separately from the free-list head, so a
     198             :        concurrent pop can transiently overshoot it; clamp before deriving. */
     199           0 :     ulong free_cnt = fd_progcache_class_free_cnt( pc, c );
     200           0 :     max [ c ] = n;
     201           0 :     used[ c ] = n - fd_ulong_min( free_cnt, n );
     202           0 :   }
     203           0 : }
     204             : 
     205             : FD_PROTOTYPES_BEGIN
     206             : 
     207             : FD_FN_CONST ulong
     208             : fd_progcache_shmem_align( void );
     209             : 
     210             : /* fd_progcache_shmem_min_sz returns the smallest progcache_sz that provisions
     211             :    txn_max, rounded up to the next MiB boundary: every class at
     212             :    fd_progcache_cache_class_min. */
     213             : 
     214             : ulong
     215             : fd_progcache_shmem_min_sz( ulong txn_max );
     216             : 
     217             : /* fd_progcache_shmem_{footprint,new} size and construct a program cache.
     218             :    txn_max bounds concurrent fork-graph nodes and progcache_sz is the shared memory
     219             :    budget, which covers everything: this shmem, the fork graph, the record array
     220             :    and the per-class value arenas.  footprint returns progcache_sz, or 0 if that
     221             :    budget is below fd_progcache_shmem_min_sz.
     222             :    shmem_new derives the split internally, provisioning every byte it can into
     223             :    value slots, and allocates nothing beyond the region it is given. */
     224             : 
     225             : ulong
     226             : fd_progcache_shmem_footprint( ulong txn_max,
     227             :                               ulong progcache_sz );
     228             : 
     229             : fd_progcache_shmem_t *
     230             : fd_progcache_shmem_new( void * shmem,
     231             :                         ulong  wksp_tag,
     232             :                         ulong  seed,
     233             :                         ulong  txn_max,
     234             :                         ulong  progcache_sz );
     235             : 
     236             : fd_progcache_join_t *
     237             : fd_progcache_shmem_join( fd_progcache_join_t *  ljoin,
     238             :                          fd_progcache_shmem_t * shmem );
     239             : 
     240             : void *
     241             : fd_progcache_shmem_leave( fd_progcache_join_t *   ljoin,
     242             :                           fd_progcache_shmem_t ** opt_shmem );
     243             : 
     244             : void *
     245             : fd_progcache_shmem_delete( fd_progcache_shmem_t * shmem );
     246             : 
     247             : void *
     248             : fd_progcache_shmem_delete_fast( fd_progcache_shmem_t * shmem );
     249             : 
     250             : FD_FN_CONST static inline fd_progcache_fork_id_t
     251       12603 : fd_progcache_fork_id_initial( void ) {
     252       12603 :   return 0UL;
     253       12603 : }
     254             : 
     255             : FD_PROTOTYPES_END
     256             : 
     257             : #endif /* HEADER_fd_src_flamenco_progcache_fd_progcache_h */