Line data    Source code

       1             : #ifndef HEADER_fd_src_vinyl_line_fd_vinyl_line_h
       2             : #define HEADER_fd_src_vinyl_line_fd_vinyl_line_h
       3             : 
       4             : /* A vinyl tile caches key-val pairs in DRAM for performance reasons
       5             :    and to faciliate operations like creating a new pair or asynchronous
       6             :    I/O.  This cache can be _completely_ lost without impacting the
       7             :    recoverabilty exactly key-val state at the time the bstream was most
       8             :    recently sync'd.
       9             : 
      10             :    This cache is logically organized into line_cnt cache lines.
      11             : 
      12             :    An eviction sequence gives the preferred order in which lines should
      13             :    be reused.  Though a line always has a position in the eviction
      14             :    sequence, a given line may not be evictable due to acquires for read
      15             :    or modify on that line.  A quota system bounds the worst case number
      16             :    of acquired lines in order to guarantee there are always some
      17             :    evictable lines.
      18             : 
      19             :    When a pair is evicted from a line, the line is moved to the least
      20             :    recently used (LRU) position in the eviction sequence so that unused
      21             :    lines can be quickly found and preferentially reused before any lines
      22             :    caching pairs.
      23             : 
      24             :    The eviction sequence is given by a circular doubly linked list and a
      25             :    cursor positioned at the LRU line.  Given the above, the sequence
      26             :    always contains exactly line_cnt lines.  Given the LRU line is
      27             :    tracked explicitly and circular list, the most recently used (MRU)
      28             :    line is tracked implicitly as the line "older" than the LRU line. */
      29             : 
      30             : #include "../meta/fd_vinyl_meta.h"
      31             : #include "../data/fd_vinyl_data.h"
      32             : 
      33             : /* FD_VINYL_LINE_EVICT_PRIO_* specify eviction priorties.  These should
      34             :    be compatible with fd_vinyl_req_evict_prio and FD_VINYL_REQ_FLAG_* */
      35             : 
      36           0 : #define FD_VINYL_LINE_EVICT_PRIO_MRU (0) /* <0 also treated as MRU */
      37     4497588 : #define FD_VINYL_LINE_EVICT_PRIO_LRU (1)
      38     3000000 : #define FD_VINYL_LINE_EVICT_PRIO_UNC (2) /* >2 also treated as UNC */
      39             : 
      40             : /* FD_VINYL_LINE_MAX gives the maximum number of lines that can be
      41             :    handled by a vinyl tile.  This is a large power of 2 minus 1.  The
      42             :    below value ensures that a value in [0,line_cnt] can be represented
      43             :    in 32-bits.  Note that larger is possible but requires more DRAM
      44             :    overhead.  For typical applications (where pair vals sizes are
      45             :    measured in KiB to MiB), a line_cnt at this LINE_MAX would require
      46             :    impractically large amounts of DRAM for the vinyl cache ... TiB to
      47             :    PiB). */
      48             : 
      49           0 : #define FD_VINYL_LINE_MAX ((1UL<<32)-1UL)
      50             : 
      51             : /* FD_VINYL_LINE_REF_MAX gives the max acquires-for-read allowed on a
      52             :    vinyl cache line.  Like LINE_MAX, this could be made larger at the
      53             :    expense of more DRAM overhead (and, more theoretical, more frequent
      54             :    line version wrapping for speculative reads).  The current value is
      55             :    sufficient to support an impractical number of concurrent clients
      56             :    acquiring the same pair for concurrently read. */
      57             : 
      58             : #define FD_VINYL_LINE_REF_MAX ((1L<<32)-2L)
      59             : 
      60             : /* FD_VINYL_LINE_VER_MAX gives the maximum number of versions a line
      61             :    can have before its version number gets reused.  This is a large
      62             :    power of 2 minus 1 such that version number reuse is impractical over
      63             :    the duration of any speculative reads. */
      64             : 
      65             : #define FD_VINYL_LINE_VER_MAX ((1UL<<32)-1UL)
      66             : 
      67             : /* A fd_vinyl_line_t stores information the vinyl tile uses to track
      68             :    how a key-val pair has been cached in DRAM.  If the val field is
      69             :    NULL, there is no pair cached in that line and all other fields are
      70             :    ignored.  Practically speaking, the vinyl tile uses this (local)
      71             :    structure to tie together the (shared) pair meta map and the (shared)
      72             :    data cache region.
      73             : 
      74             :    ctl contains:
      75             : 
      76             :      ver: This is bumped every time the line is changed to allow clients
      77             :      to do reliable lockfree speculative reads of the line under the
      78             :      assumption speculative reader will complete and test their
      79             :      speculative read before the version number can wrap.
      80             : 
      81             :      ref: -1 - the line is acquired for modify, 0 - the line is not
      82             :      acquired for anything (and thus is evictable), >0 - the line is
      83             :      acquired-for-read ref times. */
      84             : 
      85             : struct __attribute__((aligned(32))) fd_vinyl_line {
      86             :   fd_vinyl_data_obj_t * obj;            /* location in the data cache of the data_obj storing val, NULL if not caching a pair */
      87             :   ulong                 ele_idx;        /* map element storing key and the pair metadata (app and key), in [0,map_cnt) */
      88             :   ulong                 ctl;            /* packs the line version and line reference count */
      89             :   uint                  line_idx_older; /* older line in eviction sequence, in [0,line_cnt) */
      90             :   uint                  line_idx_newer; /* newer line in eviction sequence, in [0,line_cnt) */
      91             : };
      92             : 
      93             : typedef struct fd_vinyl_line fd_vinyl_line_t;
      94             : 
      95             : FD_PROTOTYPES_BEGIN
      96             : 
      97             : /* fd_vinyl_line_ctl returns ver and ref encoded as a line ctl.  ver is
      98             :    wrapped to be in [0,FD_VINYL_LINE_VER_MAX].  ref is assumed to be in
      99             :    [-1,FD_VINYL_LINE_REF_MAX].
     100             : 
     101             :    fd_vinyl_line_ctl_{ver,ref} returns the decoded eponymous field from
     102             :    a line ctl.  The return will be in
     103             :    {[0,FD_VINYL_LINE_VER_MAX]),[-1,FD_VINYL_LINE_REF_MAX]}. */
     104             : 
     105             : FD_FN_CONST static inline ulong
     106             : fd_vinyl_line_ctl( ulong ver,
     107     3000000 :                    long  ref ) {
     108     3000000 :   return (ver<<32) | ((ulong)(ref+1L));
     109     3000000 : }
     110             : 
     111     3000000 : FD_FN_CONST static inline ulong fd_vinyl_line_ctl_ver( ulong ctl ) { return ctl>>32; }
     112     3000000 : FD_FN_CONST static inline long  fd_vinyl_line_ctl_ref( ulong ctl ) { return ((long)(ctl & ((1UL<<32)-1UL)))-1L; }
     113             : 
     114             : /* fd_vinyl_line_evict_prio changes the eviction priority of line
     115             :    line_idx to evict_prio.  Cannot fail from the caller's perspective
     116             :    (will FD_LOG_CRIT if line corruption was detected). */
     117             : 
     118             : void
     119             : fd_vinyl_line_evict_prio( uint *            _line_idx_lru, /* Pointer to the LRU line idx */
     120             :                           fd_vinyl_line_t * line,          /* Indexed [0,line_cnt) */
     121             :                           ulong             _line_cnt,     /* In [3,FD_VINYL_LINE_MAX] */
     122             :                           ulong             _line_idx,     /* In [0,line_cnt) */
     123             :                           int               evict_prio );  /* FD_VINYL_LINE_EVICT_PRIO_* */
     124             : 
     125             : /* fd_vinyl_line_evict_lru finds the least recently used evictable line
     126             :    and evicts it.  Returns the line_idx of that line (will be free to
     127             :    use).  Cannot fail from the caller's perspecitve (will FD_LOG_CRIT if
     128             :    corruption was detected or quotas were misconfigured). */
     129             : 
     130             : ulong
     131             : fd_vinyl_line_evict_lru( uint *                _line_idx_lru, /* Pointer to the LRU line idx */
     132             :                          fd_vinyl_line_t *     line,          /* Indexed [0,line_cnt) */
     133             :                          ulong                 line_cnt,      /* In [3,FD_VINYL_LINE_MAX] */
     134             :                          fd_vinyl_meta_ele_t * ele0,          /* Indexed [0,ele_max) */
     135             :                          ulong                 ele_max,
     136             :                          fd_vinyl_data_t *     data );
     137             : 
     138             : FD_PROTOTYPES_END
     139             : 
     140             : #endif /* HEADER_fd_src_vinyl_line_fd_vinyl_line_h */