Line data    Source code

       1             : #include "fd_vinyl_meta.h"
       2             : 
       3             : #define MAP_NAME                  fd_vinyl_meta
       4    50956248 : #define MAP_ELE_T                 fd_vinyl_meta_ele_t
       5             : #define MAP_KEY_T                 fd_vinyl_key_t
       6     1997640 : #define MAP_KEY                   phdr.key
       7             : #define MAP_KEY_EQ(k0,k1)         fd_vinyl_key_eq( (k0), (k1) )
       8             : #define MAP_KEY_HASH(key,seed)    fd_vinyl_key_memo( (seed), (key) )
       9             : #define MAP_MEMOIZE               1
      10     3061716 : #define MAP_MEMO                  memo
      11             : #define MAP_KEY_EQ_IS_SLOW        1
      12             : #define MAP_ELE_IS_FREE(ctx,ele)  (!(ele)->phdr.ctl)
      13             : #define MAP_ELE_FREE(ctx,ele)     do { (ele)->phdr.ctl = 0UL; } while(0)
      14             : #define MAP_ELE_MOVE(ctx,dst,src) do { fd_vinyl_meta_ele_t * _src = (src); *(dst) = *_src; _src->phdr.ctl = 0UL; } while(0)
      15             : #define MAP_IMPL_STYLE            2
      16             : #include "../../util/tmpl/fd_map_slot_para.c"
      17             : 
      18             : int
      19             : fd_vinyl_meta_query_fast( fd_vinyl_meta_ele_t const * ele0,
      20             :                           ulong                       ele_max,
      21             :                           fd_vinyl_key_t const *      key,
      22             :                           ulong                       memo,
      23    22503069 :                           ulong *                     _ele_idx ) {
      24             : 
      25    22503069 :   ulong ele_idx = memo & (ele_max-1UL);
      26             : 
      27    22503069 :   int err = FD_VINYL_ERR_CORRUPT;
      28             : 
      29    22503069 :   ulong rem;
      30             : 
      31    27842088 :   for( rem=ele_max; rem; rem-- ) { /* guarantee finite termination in face of corruption */
      32    27842088 :     fd_vinyl_meta_ele_t const * ele = ele0 + ele_idx;
      33             : 
      34    27842088 :     if( FD_UNLIKELY( !ele->phdr.ctl ) ) { /* not found */
      35     7502265 :       *_ele_idx = ele_idx;
      36     7502265 :       err       = FD_VINYL_ERR_KEY;
      37     7502265 :       break;
      38     7502265 :     }
      39             : 
      40    20339823 :     if( FD_LIKELY( ele->memo==memo ) && FD_LIKELY( fd_vinyl_key_eq( &ele->phdr.key, key ) ) ) { /* found */
      41    15000804 :       *_ele_idx = ele_idx;
      42    15000804 :       err       = FD_VINYL_SUCCESS;
      43    15000804 :       break;
      44    15000804 :    }
      45             : 
      46     5339019 :     ele_idx = (ele_idx+1UL) & (ele_max-1UL); /* collision, try next slot */
      47     5339019 :   }
      48             : 
      49    22503069 :   FD_CRIT( rem, "corruption detected" );
      50             : 
      51    22503069 :   return err;
      52    22503069 : }
      53             : 
      54             : #include "../line/fd_vinyl_line.h" /* FIXME: gross (maybe make line below meta in the API hierarchy?) */
      55             : 
      56             : void
      57             : fd_vinyl_meta_remove_fast( fd_vinyl_meta_ele_t * ele0,
      58             :                            ulong                 ele_max,
      59             :                            ulong *               lock,
      60             :                            int                   lock_shift,
      61             :                            fd_vinyl_line_t *     line,
      62             :                            ulong                 line_cnt,
      63     3750531 :                            ulong                 ele_idx ) {
      64             : 
      65             :   /* At this point, we know:
      66             : 
      67             :      - nobody will lock any elements behind our back (single writer)
      68             :      - no elements are locked (not in a prepare)
      69             :      - there is at least one unoccupied element in the meta (pair_max < ele_max)
      70             :      - there is at least one   occupied element in the meta (ele_idx)
      71             :      - (thus ele_max is at least 2)
      72             : 
      73             :      When we remove element ele_idx, we might need to move elements in
      74             :      the cyclic contiguously occupied range starting at ele_idx toward
      75             :      ele_idx (but not before ele_idx) to keep their probe sequences
      76             :      intact.  This can interfere with lockfree non-blocking concurrent
      77             :      reads whose probe sequences overlap this range.
      78             : 
      79             :      Thus, we determine the set of contiguously occupied elements
      80             :      starting at ele_idx, determine the range of corresponding locks and
      81             :      lock them before we remove ele_idx to protect concurrent readers.
      82             :      If the map is not overfilled, contig_cnt is O(1) elements.
      83             : 
      84             :      If the ele is currently cached, we also need to update the
      85             :      underlying line to it points to the moved location. */
      86             : 
      87     3750531 :   ulong contig_cnt;
      88             : 
      89     5829162 :   for( contig_cnt=1UL; contig_cnt<ele_max; contig_cnt++ )
      90     5829162 :     if( FD_LIKELY( !ele0[ (ele_idx + contig_cnt) & (ele_max-1UL) ].phdr.ctl ) ) break;
      91             : 
      92     3750531 :   FD_CRIT( contig_cnt<ele_max, "corruption detected" );
      93             : 
      94             :   /* At this point, contig_cnt is in [1,ele_max) and meta elements
      95             :      [ele_idx,ele_idx+contig_cnt) (cyclic) are the contiguously occupied
      96             :      elements starting at ele_idx.  Determine the set of locks that
      97             :      cover this set. */
      98             : 
      99     3750531 :   ulong lock_lo  =  ele_idx                     >> lock_shift;        /* lock that covers first element (wrapped) */
     100     3750531 :   ulong lock_hi  = (ele_idx + contig_cnt - 1UL) >> lock_shift;        /* lock that covers last  element (unwrapped) */
     101     3750531 :   ulong lock_max =  ele_max                     >> lock_shift;        /* max locks */
     102     3750531 :   ulong lock_cnt = fd_ulong_min( lock_hi - lock_lo + 1UL, lock_max ); /* num locks required */
     103             : 
     104             :   /* Lock the range */
     105             : 
     106     8020473 :   for( ulong idx=0UL; idx<lock_cnt; idx++ ) fd_vinyl_meta_lock_update_fast( lock + ((lock_lo + idx) & (lock_max-1UL)), 1L );
     107             : 
     108             :   /* At this point, we are clear to remove ele_idx.  Make a hole at
     109             :      ele_idx and then iterate over the contig_cnt-1 remaining cyclically
     110             :      contiguously occupied elements, repairing broken probe sequences as
     111             :      we go.  Since we already learned how many contiguous elements there
     112             :      are (from the above locking), we can simplify the iteration
     113             :      slightly over a standard remove. */
     114             : 
     115     3750531 :   ele0[ ele_idx ].phdr.ctl = 0UL;
     116             : 
     117     3750531 :   ulong hole_idx = ele_idx;
     118             : 
     119     5829162 :   for( ulong rem=contig_cnt-1UL; rem; rem-- ) {
     120     2078631 :     ele_idx = (ele_idx+1UL) & (ele_max-1UL);
     121             : 
     122             :     /* At this point, meta elements before hole_idx (cyclic) have intact
     123             :        probe sequences, meta element hole_idx is unoccupied, meta
     124             :        elements (hole_idx,ele_idx) (cyclic) are occupied with intact
     125             :        probe sequences and meta elements [ele_idx,ele_idx+rem) (cyclic)
     126             :        are occupied but might have broken probe sequences due to the
     127             :        hole.
     128             : 
     129             :        If a probe looking for the key at ele_idx does not start its
     130             :        probe in (hole_idx,ele_idx] (cyclic), probing will fail
     131             :        erroneously due to the hole.  In this case, we move ele_idx to
     132             :        hole_idx to restore the probe sequence for the key at ele_idx,
     133             :        making a new hole at ele_idx.  As the probe sequences following
     134             :        the new hole could still be broken, we continue repairing probe
     135             :        sequences for elements following the new hole. */
     136             : 
     137     2078631 :     ulong start_idx = ele0[ ele_idx ].memo & (ele_max-1UL);
     138             : 
     139     2078631 :     if( !( ((hole_idx<start_idx) & (start_idx<=ele_idx)                       ) |
     140     2078631 :            ((hole_idx>ele_idx) & ((hole_idx<start_idx) | (start_idx<=ele_idx))) ) ) {
     141             : 
     142      673278 :       ulong line_idx = ele0[ ele_idx ].line_idx;
     143      673278 :       if( FD_LIKELY( line_idx<line_cnt ) ) {
     144           0 :         FD_CRIT( line[ line_idx ].ele_idx==ele_idx, "corruption detected" );
     145           0 :         line[ line_idx ].ele_idx = hole_idx;
     146      673278 :       } else {
     147      673278 :         FD_CRIT( line_idx==ULONG_MAX, "corruption detected" );
     148      673278 :       }
     149             : 
     150      673278 :       ele0[ hole_idx ] = ele0[ ele_idx ];
     151      673278 :       ele0[ ele_idx ].phdr.ctl = 0UL;
     152             : 
     153      673278 :       hole_idx = ele_idx;
     154             : 
     155      673278 :     }
     156     2078631 :   }
     157             : 
     158             :   /* Unlock the range */
     159             : 
     160     8020473 :   for( ulong idx=0UL; idx<lock_cnt; idx++ ) fd_vinyl_meta_lock_update_fast( lock + ((lock_lo + idx) & (lock_max-1UL)), 1L );
     161     3750531 : }