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 "fd_progcache_base.h"
      31             : #include <stdatomic.h>
      32             : 
      33             : FD_PROTOTYPES_BEGIN
      34             : 
      35             : /* Helper APIs for the CLOCK bit array */
      36             : 
      37             : /* fd_prog_cbits_slot returns the 64-bit slot that contains the bit pair
      38             :    for the record with pool index rec_idx. */
      39             : 
      40             : FD_FN_CONST static inline atomic_ulong *
      41             : fd_prog_cbits_slot( atomic_ulong * bits,
      42         489 :                     ulong          rec_idx ) {
      43         489 :   return &bits[ rec_idx>>5 ];
      44         489 : }
      45             : 
      46             : /* fd_prog_{visited,exists}_bit return the bit index of the {visited,
      47             :    exists} flag for a record within its slot (see fd_prog_cbits_slot).
      48             : 
      49             :    Full example:
      50             : 
      51             :      slot_p = fd_prog_cbits_slot( bits, idx )
      52             :      slot = atomic_load_explicit( slot, memory_order_relaxed )
      53             :      rec_exists = fd_ulong_extract_bit( slot, fd_prog_visited_bit( idx ) ) */
      54             : 
      55             : FD_FN_CONST static inline int
      56         834 : fd_prog_visited_bit( ulong rec_idx ) {
      57         834 :   return 2*(rec_idx & 31UL);
      58         834 : }
      59             : 
      60             : FD_FN_CONST static inline int
      61         336 : fd_prog_exists_bit( ulong rec_idx ) {
      62         336 :   return fd_prog_visited_bit( rec_idx )+1;
      63         336 : }
      64             : 
      65             : /* fd_prog_cbits_{align,footprint} return the alignment/size requirement
      66             :    for the cbits array. */
      67             : 
      68             : static inline ulong
      69        1878 : fd_prog_cbits_align( void ) {
      70        1878 :   return 64UL;
      71        1878 : }
      72             : 
      73             : static inline ulong
      74         489 : fd_prog_cbits_footprint( ulong rec_max ) {
      75         489 :   return fd_ulong_align_up( rec_max*2, 512UL ) / 8UL;
      76         489 : }
      77             : 
      78             : /* fd_prog_clock_init initializes CLOCK cache replacement algo state. */
      79             : 
      80             : void
      81             : fd_prog_clock_init( atomic_ulong * cbits,
      82             :                     ulong          rec_max );
      83             : 
      84             : /* fd_prog_clock_touch marks the record at the given index as recently
      85             :    touched which makes it less likely to get evicted. */
      86             : 
      87             : static inline void
      88             : fd_prog_clock_touch( atomic_ulong * cbits,
      89          90 :                      ulong          rec_idx ) {
      90          90 :   atomic_ulong * slot_p = fd_prog_cbits_slot( cbits, rec_idx );
      91             :   /* Set the "exists" and "visited" bits */
      92          90 :   ulong mask = 3UL<<(fd_prog_visited_bit( rec_idx ));
      93          90 :   atomic_fetch_or_explicit( slot_p, mask, memory_order_relaxed );
      94          90 : }
      95             : 
      96             : /* fd_prog_clock_remove indicates that the record at the given index is
      97             :    about to be deleted.  Should be run before a deletion, not after. */
      98             : 
      99             : static inline void
     100             : fd_prog_clock_remove( atomic_ulong * cbits,
     101          54 :                       ulong          rec_idx ) {
     102          54 :   atomic_ulong * slot_p = fd_prog_cbits_slot( cbits, rec_idx );
     103             :   /* Clear the "exists" and "visited" bits */
     104          54 :   ulong mask = ~( (3UL<<fd_prog_visited_bit( rec_idx )) );
     105             :   atomic_fetch_and_explicit( slot_p, mask, memory_order_relaxed );
     106          54 : }
     107             : 
     108             : /* fd_prog_clock_evict evicts records until at least rec_min records
     109             :    and heap_min bytes of heap space are queued for reclamation. */
     110             : 
     111             : void
     112             : fd_prog_clock_evict( fd_progcache_t * progcache,
     113             :                      ulong            rec_min,
     114             :                      ulong            heap_min );
     115             : 
     116             : FD_PROTOTYPES_END
     117             : 
     118             : #endif /* HEADER_fd_src_flamenco_progcache_fd_progcache_clock_h */