Line data    Source code

       1             : #ifndef HEADER_fd_src_flamenco_gossip_fd_gossip_hset_h
       2             : #define HEADER_fd_src_flamenco_gossip_fd_gossip_hset_h
       3             : 
       4             : #include "../../util/fd_util_base.h"
       5             : #include "../../util/bits/fd_bits.h"
       6             : 
       7             : /* fd_gossip_hset is a secondary index over the 32 byte value hashes of
       8             :    a pool (the CRDS table or the purged table) that makes building pull
       9             :    request bloom filters a mostly sequential scan.
      10             : 
      11             :    Hashes are bucketed by the top lg_bucket_cnt bits of their 64-bit
      12             :    prefix (fd_ulong_load_8 of the hash, the same prefix the pull request
      13             :    mask is applied to).  Each bucket is a list of chunks of 8 hashes
      14             :    stored contiguously (256 bytes), so a mask range maps to a run of
      15             :    buckets and each chunk feeds one fd_bloom_insert8.  All chunks of a
      16             :    bucket are full except its head.  Insert appends to the head chunk
      17             :    and remove moves the head chunk's last hash into the hole, so both
      18             :    are O(1) regardless of how hashes are distributed.
      19             : 
      20             :    Elements are identified by their index in the owning pool, in
      21             :    [0,ele_max).  The hset keeps its own copy of the hash. */
      22             : 
      23           0 : #define FD_GOSSIP_HSET_ALIGN (64UL)
      24           0 : #define FD_GOSSIP_HSET_MAGIC (0xf17eda2c3a5e7000UL) /* firedancer hset v0 */
      25             : 
      26             : struct fd_gossip_hset_chunk {
      27             :   uint next; /* next (full) chunk in the bucket, or UINT_MAX */
      28             :   uint cnt;  /* number of hashes in the chunk, in [1,8] while in use */
      29             : };
      30             : 
      31             : typedef struct fd_gossip_hset_chunk fd_gossip_hset_chunk_t;
      32             : 
      33             : struct __attribute__((aligned(FD_GOSSIP_HSET_ALIGN))) fd_gossip_hset_private {
      34             :   ulong                    ele_max;
      35             :   ulong                    chunk_max;
      36             :   ulong                    lg_bucket_cnt;
      37             :   uint                     chunk_free;  /* free chunk stack head, UINT_MAX if empty */
      38             :   uint *                   bucket_head; /* [2^lg_bucket_cnt] head chunk, UINT_MAX if empty */
      39             :   fd_gossip_hset_chunk_t * chunk;       /* [chunk_max] */
      40             :   uchar                 (* hash)[ 32 ]; /* [chunk_max*8] */
      41             :   uint *                   owner;       /* [chunk_max*8] element index for a hash slot */
      42             :   uint *                   slot;        /* [ele_max]     hash slot of an element */
      43             :   ulong                    magic;       /* ==FD_GOSSIP_HSET_MAGIC */
      44             : };
      45             : 
      46             : typedef struct fd_gossip_hset_private fd_gossip_hset_t;
      47             : 
      48             : /* fd_gossip_hset_iter_t iterates the chunks holding the hashes whose
      49             :    prefix is in [start,end]. */
      50             : 
      51             : struct fd_gossip_hset_iter {
      52             :   ulong bucket;
      53             :   ulong bucket_end;
      54             :   ulong chunk;
      55             :   ulong start;
      56             :   ulong end;
      57             :   int   filter; /* the range does not cover whole buckets */
      58             : };
      59             : 
      60             : typedef struct fd_gossip_hset_iter fd_gossip_hset_iter_t;
      61             : 
      62             : FD_PROTOTYPES_BEGIN
      63             : 
      64             : FD_FN_CONST ulong
      65             : fd_gossip_hset_align( void );
      66             : 
      67             : FD_FN_CONST ulong
      68             : fd_gossip_hset_footprint( ulong ele_max );
      69             : 
      70             : /* fd_gossip_hset_new formats shmem for up to ele_max elements.
      71             :    ele_max must be a power of 2 in [1,2^31]. */
      72             : 
      73             : void *
      74             : fd_gossip_hset_new( void * shmem,
      75             :                     ulong  ele_max );
      76             : 
      77             : fd_gossip_hset_t *
      78             : fd_gossip_hset_join( void * shhset );
      79             : 
      80             : /* fd_gossip_hset_insert adds element ele_idx with the given hash.
      81             :    ele_idx must not already be in the hset. */
      82             : 
      83             : void
      84             : fd_gossip_hset_insert( fd_gossip_hset_t * hset,
      85             :                        ulong              ele_idx,
      86             :                        uchar const *      hash );
      87             : 
      88             : /* fd_gossip_hset_remove removes element ele_idx, which must be in the
      89             :    hset. */
      90             : 
      91             : void
      92             : fd_gossip_hset_remove( fd_gossip_hset_t * hset,
      93             :                        ulong              ele_idx );
      94             : 
      95             : /* fd_gossip_hset_iter_init starts iterating the hashes whose prefix
      96             :    falls in the pull request mask range for (mask, mask_bits), see
      97             :    fd_gossip_purged_generate_masks.  Iteration yields chunks: a block
      98             :    of 8 hashes (fd_gossip_hset_iter_hashes) and a bit mask of the
      99             :    lanes that hold an in range hash (fd_gossip_hset_iter_lanes, can be
     100             :    0 when filtering).  The hset must not be modified while
     101             :    iterating. */
     102             : 
     103             : void
     104             : fd_gossip_hset_iter_init( fd_gossip_hset_iter_t *  it,
     105             :                           fd_gossip_hset_t const * hset,
     106             :                           ulong                    start_hash,
     107             :                           ulong                    end_hash );
     108             : 
     109             : static inline int
     110           0 : fd_gossip_hset_iter_done( fd_gossip_hset_iter_t const * it ) {
     111           0 :   return it->chunk==(ulong)UINT_MAX;
     112           0 : }
     113             : 
     114             : void
     115             : fd_gossip_hset_iter_next( fd_gossip_hset_iter_t *  it,
     116             :                           fd_gossip_hset_t const * hset );
     117             : 
     118             : static inline uchar const *
     119             : fd_gossip_hset_iter_hashes( fd_gossip_hset_iter_t const * it,
     120           0 :                             fd_gossip_hset_t const *      hset ) {
     121           0 :   return hset->hash[ 8UL*it->chunk ];
     122           0 : }
     123             : 
     124             : /* fd_gossip_hset_iter_owner returns the element index that owns the
     125             :    hash in the given lane of the current chunk.  The lane must be set in
     126             :    fd_gossip_hset_iter_lanes. */
     127             : 
     128             : static inline ulong
     129             : fd_gossip_hset_iter_owner( fd_gossip_hset_iter_t const * it,
     130             :                            fd_gossip_hset_t const *      hset,
     131           0 :                            ulong                         lane ) {
     132           0 :   return hset->owner[ 8UL*it->chunk+lane ];
     133           0 : }
     134             : 
     135             : static inline uint
     136             : fd_gossip_hset_iter_lanes( fd_gossip_hset_iter_t const * it,
     137           0 :                            fd_gossip_hset_t const *      hset ) {
     138           0 :   uint lanes = (1U<<hset->chunk[ it->chunk ].cnt)-1U;
     139           0 :   if( FD_UNLIKELY( it->filter ) ) {
     140           0 :     uchar const * h = hset->hash[ 8UL*it->chunk ];
     141           0 :     for( ulong i=0UL; i<8UL; i++ ) {
     142           0 :       ulong p = fd_ulong_load_8( h+32UL*i );
     143           0 :       lanes &= ~((uint)((p<it->start) | (p>it->end))<<i);
     144           0 :     }
     145           0 :   }
     146           0 :   return lanes;
     147           0 : }
     148             : 
     149             : FD_PROTOTYPES_END
     150             : 
     151             : #endif /* HEADER_fd_src_flamenco_gossip_fd_gossip_hset_h */