Line data    Source code

       1             : #include "fd_gossip_hset.h"
       2             : #include "../../util/log/fd_log.h"
       3             : 
       4             : #include <string.h>
       5             : 
       6     5564259 : #define HSET_NULL (UINT_MAX)
       7             : 
       8             : static ulong
       9         480 : 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         480 :   return fd_ulong_min( fd_ulong_max( (ulong)fd_ulong_find_msb( ele_max ), 8UL )-7UL, 16UL );
      14         480 : }
      15             : 
      16             : static ulong
      17         240 : hset_chunk_max( ulong ele_max ) {
      18             :   /* Every bucket has at most one non-full chunk. */
      19         240 :   return ele_max/8UL + (1UL<<hset_lg_bucket_cnt( ele_max ));
      20         240 : }
      21             : 
      22             : FD_FN_CONST ulong
      23         255 : fd_gossip_hset_align( void ) {
      24         255 :   return FD_GOSSIP_HSET_ALIGN;
      25         255 : }
      26             : 
      27             : FD_FN_CONST ulong
      28         195 : fd_gossip_hset_footprint( ulong ele_max ) {
      29         195 :   if( FD_UNLIKELY( !ele_max || !fd_ulong_is_pow2( ele_max ) || ele_max>(1UL<<31) ) ) return 0UL;
      30         195 :   ulong chunk_max = hset_chunk_max( ele_max );
      31         195 :   ulong l;
      32         195 :   l = FD_LAYOUT_INIT;
      33         195 :   l = FD_LAYOUT_APPEND( l, FD_GOSSIP_HSET_ALIGN, sizeof(fd_gossip_hset_t)                         );
      34         195 :   l = FD_LAYOUT_APPEND( l, alignof(uint),        sizeof(uint)*(1UL<<hset_lg_bucket_cnt( ele_max )) );
      35         195 :   l = FD_LAYOUT_APPEND( l, 64UL,                 sizeof(fd_gossip_hset_chunk_t)*chunk_max          );
      36         195 :   l = FD_LAYOUT_APPEND( l, 64UL,                 256UL*chunk_max                                    );
      37         195 :   l = FD_LAYOUT_APPEND( l, alignof(uint),        sizeof(uint)*8UL*chunk_max                         );
      38         195 :   l = FD_LAYOUT_APPEND( l, alignof(uint),        sizeof(uint)*ele_max                               );
      39         195 :   return FD_LAYOUT_FINI( l, FD_GOSSIP_HSET_ALIGN );
      40         195 : }
      41             : 
      42             : void *
      43             : fd_gossip_hset_new( void * shmem,
      44          45 :                     ulong  ele_max ) {
      45          45 :   if( FD_UNLIKELY( !shmem ) ) {
      46           0 :     FD_LOG_WARNING(( "NULL shmem" ));
      47           0 :     return NULL;
      48           0 :   }
      49             : 
      50          45 :   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          45 :   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          45 :   ulong lg_bucket_cnt = hset_lg_bucket_cnt( ele_max );
      61          45 :   ulong chunk_max     = hset_chunk_max( ele_max );
      62             : 
      63          45 :   FD_SCRATCH_ALLOC_INIT( l, shmem );
      64          45 :   fd_gossip_hset_t * hset = FD_SCRATCH_ALLOC_APPEND( l, FD_GOSSIP_HSET_ALIGN, sizeof(fd_gossip_hset_t)                  );
      65          45 :   void * _bucket_head     = FD_SCRATCH_ALLOC_APPEND( l, alignof(uint),        sizeof(uint)*(1UL<<lg_bucket_cnt)         );
      66          45 :   void * _chunk           = FD_SCRATCH_ALLOC_APPEND( l, 64UL,                 sizeof(fd_gossip_hset_chunk_t)*chunk_max  );
      67          45 :   void * _hash            = FD_SCRATCH_ALLOC_APPEND( l, 64UL,                 256UL*chunk_max                           );
      68          45 :   void * _owner           = FD_SCRATCH_ALLOC_APPEND( l, alignof(uint),        sizeof(uint)*8UL*chunk_max                );
      69          45 :   void * _slot            = FD_SCRATCH_ALLOC_APPEND( l, alignof(uint),        sizeof(uint)*ele_max                      );
      70          45 :   FD_TEST( FD_SCRATCH_ALLOC_FINI( l, FD_GOSSIP_HSET_ALIGN )==(ulong)shmem+fd_gossip_hset_footprint( ele_max ) );
      71             : 
      72          45 :   hset->ele_max       = ele_max;
      73          45 :   hset->chunk_max     = chunk_max;
      74          45 :   hset->lg_bucket_cnt = lg_bucket_cnt;
      75          45 :   hset->bucket_head   = (uint *)_bucket_head;
      76          45 :   hset->chunk         = (fd_gossip_hset_chunk_t *)_chunk;
      77          45 :   hset->hash          = (uchar (*)[ 32 ])_hash;
      78          45 :   hset->owner         = (uint *)_owner;
      79          45 :   hset->slot          = (uint *)_slot;
      80             : 
      81        1287 :   for( ulong b=0UL; b<(1UL<<lg_bucket_cnt); b++ ) hset->bucket_head[ b ] = HSET_NULL;
      82       20445 :   for( ulong c=0UL; c<chunk_max; c++ ) {
      83       20400 :     hset->chunk[ c ].next = c+1UL<chunk_max ? (uint)(c+1UL) : HSET_NULL;
      84       20400 :     hset->chunk[ c ].cnt  = 0U;
      85       20400 :   }
      86          45 :   hset->chunk_free = 0U;
      87             :   /* Lanes past a chunk's cnt are read (and ignored) by bloom inserts */
      88          45 :   memset( _hash, 0, 256UL*chunk_max );
      89      153312 :   for( ulong i=0UL; i<ele_max; i++ ) hset->slot[ i ] = HSET_NULL;
      90             : 
      91          45 :   FD_COMPILER_MFENCE();
      92          45 :   FD_VOLATILE( hset->magic ) = FD_GOSSIP_HSET_MAGIC;
      93          45 :   FD_COMPILER_MFENCE();
      94             : 
      95          45 :   return (void *)hset;
      96          45 : }
      97             : 
      98             : fd_gossip_hset_t *
      99          45 : fd_gossip_hset_join( void * shhset ) {
     100          45 :   if( FD_UNLIKELY( !shhset ) ) {
     101           0 :     FD_LOG_WARNING(( "NULL shhset" ));
     102           0 :     return NULL;
     103           0 :   }
     104             : 
     105          45 :   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          45 :   fd_gossip_hset_t * hset = (fd_gossip_hset_t *)shhset;
     111             : 
     112          45 :   if( FD_UNLIKELY( hset->magic!=FD_GOSSIP_HSET_MAGIC ) ) {
     113           0 :     FD_LOG_WARNING(( "bad magic" ));
     114           0 :     return NULL;
     115           0 :   }
     116             : 
     117          45 :   return hset;
     118          45 : }
     119             : 
     120             : static inline ulong
     121             : hset_bucket( fd_gossip_hset_t const * hset,
     122     7337790 :              uchar const *            hash ) {
     123     7337790 :   return fd_ulong_load_8( hash )>>(64UL-hset->lg_bucket_cnt);
     124     7337790 : }
     125             : 
     126             : void
     127             : fd_gossip_hset_insert( fd_gossip_hset_t * hset,
     128             :                        ulong              ele_idx,
     129     3717144 :                        uchar const *      hash ) {
     130     3717144 :   ulong b    = hset_bucket( hset, hash );
     131     3717144 :   ulong head = hset->bucket_head[ b ];
     132     3717144 :   if( FD_UNLIKELY( head==HSET_NULL || hset->chunk[ head ].cnt==8U ) ) {
     133      466767 :     ulong c = hset->chunk_free;
     134      466767 :     FD_TEST( c!=HSET_NULL ); /* impossible, see hset_chunk_max */
     135      466767 :     hset->chunk_free       = hset->chunk[ c ].next;
     136      466767 :     hset->chunk[ c ].next  = (uint)head;
     137      466767 :     hset->chunk[ c ].cnt   = 0U;
     138      466767 :     hset->bucket_head[ b ] = (uint)c;
     139      466767 :     head = c;
     140      466767 :   }
     141     3717144 :   ulong s = 8UL*head + hset->chunk[ head ].cnt++;
     142     3717144 :   memcpy( hset->hash[ s ], hash, 32UL );
     143     3717144 :   hset->owner[ s ]       = (uint)ele_idx;
     144     3717144 :   hset->slot[ ele_idx ]  = (uint)s;
     145     3717144 : }
     146             : 
     147             : void
     148             : fd_gossip_hset_remove( fd_gossip_hset_t * hset,
     149     3620646 :                        ulong              ele_idx ) {
     150     3620646 :   ulong s    = hset->slot[ ele_idx ];
     151     3620646 :   ulong b    = hset_bucket( hset, hset->hash[ s ] );
     152     3620646 :   ulong head = hset->bucket_head[ b ];
     153     3620646 :   ulong last = 8UL*head + hset->chunk[ head ].cnt - 1UL;
     154     3620646 :   if( FD_LIKELY( s!=last ) ) {
     155             :     /* Fill the hole with the head chunk's last hash */
     156     3563577 :     memcpy( hset->hash[ s ], hset->hash[ last ], 32UL );
     157     3563577 :     ulong moved = hset->owner[ last ];
     158     3563577 :     hset->owner[ s ]     = (uint)moved;
     159     3563577 :     hset->slot[ moved ]  = (uint)s;
     160     3563577 :   }
     161     3620646 :   hset->slot[ ele_idx ] = HSET_NULL;
     162     3620646 :   if( FD_UNLIKELY( !--hset->chunk[ head ].cnt ) ) {
     163      454170 :     hset->bucket_head[ b ] = hset->chunk[ head ].next;
     164      454170 :     hset->chunk[ head ].next = hset->chunk_free;
     165      454170 :     hset->chunk_free = (uint)head;
     166      454170 :   }
     167     3620646 : }
     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     1768569 :            fd_gossip_hset_t const * hset ) {
     175     1768569 :   ulong c = HSET_NULL;
     176     1772124 :   for( ulong b=it->bucket; b<=it->bucket_end; b++ ) {
     177     1735254 :     c = hset->bucket_head[ b ];
     178     1735254 :     if( FD_LIKELY( c!=HSET_NULL ) ) { it->bucket = b; break; }
     179     1735254 :   }
     180     1768569 :   it->chunk = c;
     181     1768569 : }
     182             : 
     183             : static inline void
     184             : hset_prefetch( fd_gossip_hset_t const * hset,
     185    19876953 :                ulong                    c ) {
     186    19876953 :   if( FD_UNLIKELY( c==HSET_NULL ) ) return;
     187    19841706 :   uchar const * h = hset->hash[ 8UL*c ];
     188    19841706 :   __builtin_prefetch( h     ); __builtin_prefetch( h+ 64UL );
     189    19841706 :   __builtin_prefetch( h+128 ); __builtin_prefetch( h+192UL );
     190    19841706 :   __builtin_prefetch( hset->chunk+c );
     191    19841706 : }
     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       36870 :                           ulong                    end_hash ) {
     198       36870 :   ulong shift = 64UL-hset->lg_bucket_cnt;
     199       36870 :   ulong low   = (1UL<<shift)-1UL;
     200       36870 :   it->start      = start_hash;
     201       36870 :   it->end        = end_hash;
     202       36870 :   it->filter     = (start_hash&low)!=0UL || (end_hash&low)!=low;
     203       36870 :   it->bucket     = start_hash>>shift;
     204       36870 :   it->bucket_end = end_hash>>shift;
     205       36870 :   hset_seek( it, hset );
     206       36870 :   if( FD_LIKELY( it->chunk!=HSET_NULL ) ) {
     207       34299 :     hset_prefetch( hset, it->chunk );
     208       34299 :     hset_prefetch( hset, hset->chunk[ it->chunk ].next );
     209       34299 :   }
     210       36870 : }
     211             : 
     212             : void
     213             : fd_gossip_hset_iter_next( fd_gossip_hset_iter_t *  it,
     214    19842654 :                           fd_gossip_hset_t const * hset ) {
     215    19842654 :   ulong c = hset->chunk[ it->chunk ].next;
     216    19842654 :   if( FD_UNLIKELY( c==HSET_NULL ) ) {
     217     1731699 :     it->bucket++;
     218     1731699 :     hset_seek( it, hset );
     219     1731699 :     c = it->chunk;
     220     1731699 :     if( FD_UNLIKELY( c==HSET_NULL ) ) return;
     221     1731699 :   }
     222    19808355 :   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    19808355 :   ulong n = hset->chunk[ c ].next;
     226    19808355 :   if( FD_UNLIKELY( n==HSET_NULL && it->bucket<it->bucket_end ) ) n = hset->bucket_head[ it->bucket+1UL ];
     227    19808355 :   hset_prefetch( hset, n );
     228    19808355 : }