Line data    Source code

       1             : #ifndef HEADER_fd_src_flamenco_progcache_fd_progcache_clock_h
       2             : #define HEADER_fd_src_flamenco_progcache_fd_progcache_clock_h
       3             : 
       4             : /* fd_progcache_clock.h provides the cache eviction policy for the
       5             :    program cache (CLOCK).
       6             : 
       7             :    CLOCK is a cache replacement algorithm:
       8             :    Entries get evicted when the cache is full.
       9             : 
      10             :    There are two "cache is full" conditions:
      11             :    - No more progcache_rec descriptors available
      12             :    - Insufficient heap space to allocate a val
      13             : 
      14             :    The CLOCK algorithm works as follows:
      15             :    - There exists a "visited" bit for each progcache_rec
      16             :    - Whenever a user accesses a record, the visited bit is set
      17             :    - When cache replacement kicks in, the bit set is scanned
      18             :      (low-to-high cyclic).  For each record:
      19             :      - If the "visited" bit is set, unset it
      20             :      - Else ("visited" bit unset), evict the record
      21             : 
      22             :    Some implementation details:
      23             :    - The "visited" bits are stored in a dense bit array ("cbits")
      24             :      (Optimize for fast scans)
      25             :    - This bit array shadows the progcache_rec pool (including free
      26             :      entries)
      27             :    - An additional "exists" bit is interleaved with the "visited" bit,
      28             :      to disambiguate an existing idle entry from a free entry */
      29             : 
      30             : #include "../../util/bits/fd_bits.h"
      31             : #include "fd_progcache_base.h"
      32             : 
      33             : #include <stdatomic.h>
      34             : 
      35             : FD_PROTOTYPES_BEGIN
      36             : 
      37             : /* Helper APIs for the CLOCK bit array */
      38             : 
      39             : /* fd_prog_cbits_slot returns the 64-bit slot that contains the bit pair
      40             :    for the record with pool index rec_idx. */
      41             : 
      42             : FD_FN_CONST static inline atomic_ulong *
      43             : fd_prog_cbits_slot( atomic_ulong * bits,
      44     1256994 :                     ulong          rec_idx ) {
      45     1256994 :   return &bits[ rec_idx>>5 ];
      46     1256994 : }
      47             : 
      48             : /* fd_prog_{visited,exists}_bit return the bit index of the {visited,
      49             :    exists} flag for a record within its slot (see fd_prog_cbits_slot).
      50             : 
      51             :    Full example:
      52             : 
      53             :      slot_p = fd_prog_cbits_slot( bits, idx )
      54             :      slot = atomic_load_explicit( slot, memory_order_relaxed )
      55             :      rec_exists = fd_ulong_extract_bit( slot, fd_prog_visited_bit( idx ) ) */
      56             : 
      57             : FD_FN_CONST static inline int
      58     2513787 : fd_prog_visited_bit( ulong rec_idx ) {
      59     2513787 :   return 2*(rec_idx & 31UL);
      60     2513787 : }
      61             : 
      62             : FD_FN_CONST static inline int
      63     1256772 : fd_prog_exists_bit( ulong rec_idx ) {
      64     1256772 :   return fd_prog_visited_bit( rec_idx )+1;
      65     1256772 : }
      66             : 
      67             : /* fd_prog_cbits_{align,footprint} return the alignment/size requirement
      68             :    for the cbits array. */
      69             : 
      70             : static inline ulong
      71        2343 : fd_prog_cbits_align( void ) {
      72        2343 :   return 64UL;
      73        2343 : }
      74             : 
      75             : static inline ulong
      76         603 : fd_prog_cbits_footprint( ulong rec_max ) {
      77         603 :   return fd_ulong_align_up( rec_max*2, 512UL ) / 8UL;
      78         603 : }
      79             : 
      80             : /* fd_prog_clock_init initializes CLOCK cache replacement algo state. */
      81             : 
      82             : void
      83             : fd_prog_clock_init( atomic_ulong * cbits,
      84             :                     ulong          rec_max );
      85             : 
      86             : /* fd_prog_clock_touch marks the record at the given index as recently
      87             :    touched which makes it less likely to get evicted. */
      88             : 
      89             : static inline void
      90             : fd_prog_clock_touch( atomic_ulong * cbits,
      91         117 :                      ulong          rec_idx ) {
      92         117 :   atomic_ulong * slot_p = fd_prog_cbits_slot( cbits, rec_idx );
      93             :   /* Set the "exists" and "visited" bits */
      94         117 :   ulong mask = 3UL<<(fd_prog_visited_bit( rec_idx ));
      95         117 :   atomic_fetch_or_explicit( slot_p, mask, memory_order_relaxed );
      96         117 : }
      97             : 
      98             : /* fd_prog_clock_remove indicates that the record at the given index is
      99             :    about to be deleted.  Should be run before a deletion, not after. */
     100             : 
     101             : static inline void
     102             : fd_prog_clock_remove( atomic_ulong * cbits,
     103          96 :                       ulong          rec_idx ) {
     104          96 :   atomic_ulong * slot_p = fd_prog_cbits_slot( cbits, rec_idx );
     105             :   /* Clear the "exists" and "visited" bits */
     106          96 :   ulong mask = ~( (3UL<<fd_prog_visited_bit( rec_idx )) );
     107             :   atomic_fetch_and_explicit( slot_p, mask, memory_order_relaxed );
     108          96 : }
     109             : 
     110             : /* fd_prog_clock_evict evicts records until at least rec_min records
     111             :    and heap_min bytes of heap space are queued for reclamation. */
     112             : 
     113             : void
     114             : fd_prog_clock_evict( fd_progcache_t * progcache,
     115             :                      ulong            rec_min,
     116             :                      ulong            heap_min );
     117             : 
     118             : FD_PROTOTYPES_END
     119             : 
     120             : #endif /* HEADER_fd_src_flamenco_progcache_fd_progcache_clock_h */