Line data    Source code

       1             : #include "fd_gossip_hset.h"
       2             : #include "../../util/log/fd_log.h"
       3             : 
       4             : #include <string.h>
       5             : 
       6           0 : #define HSET_NULL (UINT_MAX)
       7             : 
       8             : static ulong
       9           0 : hset_lg_bucket_cnt( ulong ele_max ) {
      10             :   /* ~128 elements per bucket when full, so a pull request mask range
      11             :      (mask_bits<=12 on mainnet sized tables) covers whole buckets and
      12             :      the partially filled head chunks waste few lanes. */
      13           0 :   return fd_ulong_min( fd_ulong_max( (ulong)fd_ulong_find_msb( ele_max ), 8UL )-7UL, 16UL );
      14           0 : }
      15             : 
      16             : static ulong
      17           0 : hset_chunk_max( ulong ele_max ) {
      18             :   /* Every bucket has at most one non-full chunk. */
      19           0 :   return ele_max/8UL + (1UL<<hset_lg_bucket_cnt( ele_max ));
      20           0 : }
      21             : 
      22             : FD_FN_CONST ulong
      23           0 : fd_gossip_hset_align( void ) {
      24           0 :   return FD_GOSSIP_HSET_ALIGN;
      25           0 : }
      26             : 
      27             : FD_FN_CONST ulong
      28           0 : fd_gossip_hset_footprint( ulong ele_max ) {
      29           0 :   if( FD_UNLIKELY( !ele_max || !fd_ulong_is_pow2( ele_max ) || ele_max>(1UL<<31) ) ) return 0UL;
      30           0 :   ulong chunk_max = hset_chunk_max( ele_max );
      31           0 :   ulong l;
      32           0 :   l = FD_LAYOUT_INIT;
      33           0 :   l = FD_LAYOUT_APPEND( l, FD_GOSSIP_HSET_ALIGN, sizeof(fd_gossip_hset_t)                         );
      34           0 :   l = FD_LAYOUT_APPEND( l, alignof(uint),        sizeof(uint)*(1UL<<hset_lg_bucket_cnt( ele_max )) );
      35           0 :   l = FD_LAYOUT_APPEND( l, 64UL,                 sizeof(fd_gossip_hset_chunk_t)*chunk_max          );
      36           0 :   l = FD_LAYOUT_APPEND( l, 64UL,                 256UL*chunk_max                                    );
      37           0 :   l = FD_LAYOUT_APPEND( l, alignof(uint),        sizeof(uint)*8UL*chunk_max                         );
      38           0 :   l = FD_LAYOUT_APPEND( l, alignof(uint),        sizeof(uint)*ele_max                               );
      39           0 :   return FD_LAYOUT_FINI( l, FD_GOSSIP_HSET_ALIGN );
      40           0 : }
      41             : 
      42             : void *
      43             : fd_gossip_hset_new( void * shmem,
      44           0 :                     ulong  ele_max ) {
      45           0 :   if( FD_UNLIKELY( !shmem ) ) {
      46           0 :     FD_LOG_WARNING(( "NULL shmem" ));
      47           0 :     return NULL;
      48           0 :   }
      49             : 
      50           0 :   if( FD_UNLIKELY( !fd_ulong_is_aligned( (ulong)shmem, fd_gossip_hset_align() ) ) ) {
      51           0 :     FD_LOG_WARNING(( "misaligned shmem" ));
      52           0 :     return NULL;
      53           0 :   }
      54             : 
      55           0 :   if( FD_UNLIKELY( !fd_gossip_hset_footprint( ele_max ) ) ) {
      56           0 :     FD_LOG_WARNING(( "bad ele_max" ));
      57           0 :     return NULL;
      58           0 :   }
      59             : 
      60           0 :   ulong lg_bucket_cnt = hset_lg_bucket_cnt( ele_max );
      61           0 :   ulong chunk_max     = hset_chunk_max( ele_max );
      62             : 
      63           0 :   FD_SCRATCH_ALLOC_INIT( l, shmem );
      64           0 :   fd_gossip_hset_t * hset = FD_SCRATCH_ALLOC_APPEND( l, FD_GOSSIP_HSET_ALIGN, sizeof(fd_gossip_hset_t)                  );
      65           0 :   void * _bucket_head     = FD_SCRATCH_ALLOC_APPEND( l, alignof(uint),        sizeof(uint)*(1UL<<lg_bucket_cnt)         );
      66           0 :   void * _chunk           = FD_SCRATCH_ALLOC_APPEND( l, 64UL,                 sizeof(fd_gossip_hset_chunk_t)*chunk_max  );
      67           0 :   void * _hash            = FD_SCRATCH_ALLOC_APPEND( l, 64UL,                 256UL*chunk_max                           );
      68           0 :   void * _owner           = FD_SCRATCH_ALLOC_APPEND( l, alignof(uint),        sizeof(uint)*8UL*chunk_max                );
      69           0 :   void * _slot            = FD_SCRATCH_ALLOC_APPEND( l, alignof(uint),        sizeof(uint)*ele_max                      );
      70           0 :   FD_TEST( FD_SCRATCH_ALLOC_FINI( l, FD_GOSSIP_HSET_ALIGN )==(ulong)shmem+fd_gossip_hset_footprint( ele_max ) );
      71             : 
      72           0 :   hset->ele_max       = ele_max;
      73           0 :   hset->chunk_max     = chunk_max;
      74           0 :   hset->lg_bucket_cnt = lg_bucket_cnt;
      75           0 :   hset->bucket_head   = (uint *)_bucket_head;
      76           0 :   hset->chunk         = (fd_gossip_hset_chunk_t *)_chunk;
      77           0 :   hset->hash          = (uchar (*)[ 32 ])_hash;
      78           0 :   hset->owner         = (uint *)_owner;
      79           0 :   hset->slot          = (uint *)_slot;
      80             : 
      81           0 :   for( ulong b=0UL; b<(1UL<<lg_bucket_cnt); b++ ) hset->bucket_head[ b ] = HSET_NULL;
      82           0 :   for( ulong c=0UL; c<chunk_max; c++ ) {
      83           0 :     hset->chunk[ c ].next = c+1UL<chunk_max ? (uint)(c+1UL) : HSET_NULL;
      84           0 :     hset->chunk[ c ].cnt  = 0U;
      85           0 :   }
      86           0 :   hset->chunk_free = 0U;
      87             :   /* Lanes past a chunk's cnt are read (and ignored) by bloom inserts */
      88           0 :   memset( _hash, 0, 256UL*chunk_max );
      89           0 :   for( ulong i=0UL; i<ele_max; i++ ) hset->slot[ i ] = HSET_NULL;
      90             : 
      91           0 :   FD_COMPILER_MFENCE();
      92           0 :   FD_VOLATILE( hset->magic ) = FD_GOSSIP_HSET_MAGIC;
      93           0 :   FD_COMPILER_MFENCE();
      94             : 
      95           0 :   return (void *)hset;
      96           0 : }
      97             : 
      98             : fd_gossip_hset_t *
      99           0 : fd_gossip_hset_join( void * shhset ) {
     100           0 :   if( FD_UNLIKELY( !shhset ) ) {
     101           0 :     FD_LOG_WARNING(( "NULL shhset" ));
     102           0 :     return NULL;
     103           0 :   }
     104             : 
     105           0 :   if( FD_UNLIKELY( !fd_ulong_is_aligned( (ulong)shhset, fd_gossip_hset_align() ) ) ) {
     106           0 :     FD_LOG_WARNING(( "misaligned shhset" ));
     107           0 :     return NULL;
     108           0 :   }
     109             : 
     110           0 :   fd_gossip_hset_t * hset = (fd_gossip_hset_t *)shhset;
     111             : 
     112           0 :   if( FD_UNLIKELY( hset->magic!=FD_GOSSIP_HSET_MAGIC ) ) {
     113           0 :     FD_LOG_WARNING(( "bad magic" ));
     114           0 :     return NULL;
     115           0 :   }
     116             : 
     117           0 :   return hset;
     118           0 : }
     119             : 
     120             : static inline ulong
     121             : hset_bucket( fd_gossip_hset_t const * hset,
     122           0 :              uchar const *            hash ) {
     123           0 :   return fd_ulong_load_8( hash )>>(64UL-hset->lg_bucket_cnt);
     124           0 : }
     125             : 
     126             : void
     127             : fd_gossip_hset_insert( fd_gossip_hset_t * hset,
     128             :                        ulong              ele_idx,
     129           0 :                        uchar const *      hash ) {
     130           0 :   ulong b    = hset_bucket( hset, hash );
     131           0 :   ulong head = hset->bucket_head[ b ];
     132           0 :   if( FD_UNLIKELY( head==HSET_NULL || hset->chunk[ head ].cnt==8U ) ) {
     133           0 :     ulong c = hset->chunk_free;
     134           0 :     FD_TEST( c!=HSET_NULL ); /* impossible, see hset_chunk_max */
     135           0 :     hset->chunk_free       = hset->chunk[ c ].next;
     136           0 :     hset->chunk[ c ].next  = (uint)head;
     137           0 :     hset->chunk[ c ].cnt   = 0U;
     138           0 :     hset->bucket_head[ b ] = (uint)c;
     139           0 :     head = c;
     140           0 :   }
     141           0 :   ulong s = 8UL*head + hset->chunk[ head ].cnt++;
     142           0 :   memcpy( hset->hash[ s ], hash, 32UL );
     143           0 :   hset->owner[ s ]       = (uint)ele_idx;
     144           0 :   hset->slot[ ele_idx ]  = (uint)s;
     145           0 : }
     146             : 
     147             : void
     148             : fd_gossip_hset_remove( fd_gossip_hset_t * hset,
     149           0 :                        ulong              ele_idx ) {
     150           0 :   ulong s    = hset->slot[ ele_idx ];
     151           0 :   ulong b    = hset_bucket( hset, hset->hash[ s ] );
     152           0 :   ulong head = hset->bucket_head[ b ];
     153           0 :   ulong last = 8UL*head + hset->chunk[ head ].cnt - 1UL;
     154           0 :   if( FD_LIKELY( s!=last ) ) {
     155             :     /* Fill the hole with the head chunk's last hash */
     156           0 :     memcpy( hset->hash[ s ], hset->hash[ last ], 32UL );
     157           0 :     ulong moved = hset->owner[ last ];
     158           0 :     hset->owner[ s ]     = (uint)moved;
     159           0 :     hset->slot[ moved ]  = (uint)s;
     160           0 :   }
     161           0 :   hset->slot[ ele_idx ] = HSET_NULL;
     162           0 :   if( FD_UNLIKELY( !--hset->chunk[ head ].cnt ) ) {
     163           0 :     hset->bucket_head[ b ] = hset->chunk[ head ].next;
     164           0 :     hset->chunk[ head ].next = hset->chunk_free;
     165           0 :     hset->chunk_free = (uint)head;
     166           0 :   }
     167           0 : }
     168             : 
     169             : /* hset_seek sets it->chunk to the head of the first non-empty bucket
     170             :    in [it->bucket,it->bucket_end]. */
     171             : 
     172             : static inline void
     173             : hset_seek( fd_gossip_hset_iter_t *  it,
     174           0 :            fd_gossip_hset_t const * hset ) {
     175           0 :   ulong c = HSET_NULL;
     176           0 :   for( ulong b=it->bucket; b<=it->bucket_end; b++ ) {
     177           0 :     c = hset->bucket_head[ b ];
     178           0 :     if( FD_LIKELY( c!=HSET_NULL ) ) { it->bucket = b; break; }
     179           0 :   }
     180           0 :   it->chunk = c;
     181           0 : }
     182             : 
     183             : static inline void
     184             : hset_prefetch( fd_gossip_hset_t const * hset,
     185           0 :                ulong                    c ) {
     186           0 :   if( FD_UNLIKELY( c==HSET_NULL ) ) return;
     187           0 :   uchar const * h = hset->hash[ 8UL*c ];
     188           0 :   __builtin_prefetch( h     ); __builtin_prefetch( h+ 64UL );
     189           0 :   __builtin_prefetch( h+128 ); __builtin_prefetch( h+192UL );
     190           0 :   __builtin_prefetch( hset->chunk+c );
     191           0 : }
     192             : 
     193             : void
     194             : fd_gossip_hset_iter_init( fd_gossip_hset_iter_t *  it,
     195             :                           fd_gossip_hset_t const * hset,
     196             :                           ulong                    start_hash,
     197           0 :                           ulong                    end_hash ) {
     198           0 :   ulong shift = 64UL-hset->lg_bucket_cnt;
     199           0 :   ulong low   = (1UL<<shift)-1UL;
     200           0 :   it->start      = start_hash;
     201           0 :   it->end        = end_hash;
     202           0 :   it->filter     = (start_hash&low)!=0UL || (end_hash&low)!=low;
     203           0 :   it->bucket     = start_hash>>shift;
     204           0 :   it->bucket_end = end_hash>>shift;
     205           0 :   hset_seek( it, hset );
     206           0 :   if( FD_LIKELY( it->chunk!=HSET_NULL ) ) {
     207           0 :     hset_prefetch( hset, it->chunk );
     208           0 :     hset_prefetch( hset, hset->chunk[ it->chunk ].next );
     209           0 :   }
     210           0 : }
     211             : 
     212             : void
     213             : fd_gossip_hset_iter_next( fd_gossip_hset_iter_t *  it,
     214           0 :                           fd_gossip_hset_t const * hset ) {
     215           0 :   ulong c = hset->chunk[ it->chunk ].next;
     216           0 :   if( FD_UNLIKELY( c==HSET_NULL ) ) {
     217           0 :     it->bucket++;
     218           0 :     hset_seek( it, hset );
     219           0 :     c = it->chunk;
     220           0 :     if( FD_UNLIKELY( c==HSET_NULL ) ) return;
     221           0 :   }
     222           0 :   it->chunk = c;
     223             :   /* The chunk after c is usually full and random in memory; start its
     224             :      loads now so they overlap hashing c. */
     225           0 :   ulong n = hset->chunk[ c ].next;
     226           0 :   if( FD_UNLIKELY( n==HSET_NULL && it->bucket<it->bucket_end ) ) n = hset->bucket_head[ it->bucket+1UL ];
     227           0 :   hset_prefetch( hset, n );
     228           0 : }