Line data    Source code

       1             : #include "fd_active_set.h"
       2             : #include "fd_active_set_private.h"
       3             : 
       4             : FD_FN_CONST ulong
       5           9 : fd_active_set_align( void ) {
       6           9 :   return FD_ACTIVE_SET_ALIGN;
       7           9 : }
       8             : 
       9             : FD_FN_CONST ulong
      10           3 : fd_active_set_footprint( void ) {
      11           3 :   ulong l;
      12           3 :   l = FD_LAYOUT_INIT;
      13           3 :   l = FD_LAYOUT_APPEND( l, FD_ACTIVE_SET_ALIGN, sizeof(fd_active_set_t) );
      14           3 :   l = FD_LAYOUT_APPEND( l, FD_BLOOM_ALIGN,      25UL*12UL*fd_bloom_footprint( 0.1, 32768UL ) );
      15           3 :   return FD_LAYOUT_FINI( l, FD_ACTIVE_SET_ALIGN );
      16           3 : }
      17             : 
      18             : void *
      19             : fd_active_set_new( void *     shmem,
      20           3 :                    fd_rng_t * rng ) {
      21           3 :   if( FD_UNLIKELY( !shmem ) ) {
      22           0 :     FD_LOG_WARNING(( "NULL shmem" ));
      23           0 :     return NULL;
      24           0 :   }
      25             : 
      26           3 :   if( FD_UNLIKELY( !fd_ulong_is_aligned( (ulong)shmem, fd_active_set_align() ) ) ) {
      27           0 :     FD_LOG_WARNING(( "misaligned shmem" ));
      28           0 :     return NULL;
      29           0 :   }
      30             : 
      31           3 :   ulong bloom_footprint = fd_bloom_footprint( 0.1, 32768UL );
      32             : 
      33           3 :   FD_SCRATCH_ALLOC_INIT( l, shmem );
      34           3 :   fd_active_set_t * as = FD_SCRATCH_ALLOC_APPEND( l, FD_ACTIVE_SET_ALIGN, sizeof(fd_active_set_t) );
      35           3 :   uchar * _blooms = FD_SCRATCH_ALLOC_APPEND( l, FD_BLOOM_ALIGN, 25UL*12UL*bloom_footprint );
      36             : 
      37           0 :   as->rng = rng;
      38          78 :   for( ulong i=0UL; i<25UL; i++ ) {
      39          75 :     fd_active_set_entry_t * entry = as->entries[ i ];
      40          75 :     entry->nodes_idx = 0UL;
      41          75 :     entry->nodes_len = 0UL;
      42             : 
      43         975 :     for( ulong j=0UL; j<12UL; j++ ) {
      44         900 :       fd_active_set_peer_t * peer = entry->nodes[ j ];
      45         900 :       peer->bloom = fd_bloom_join( fd_bloom_new( _blooms, rng, 0.1, 32768UL ) );
      46         900 :       if( FD_UNLIKELY( !peer->bloom ) ) {
      47           0 :         FD_LOG_WARNING(( "failed to create bloom filter" ));
      48           0 :         return NULL;
      49           0 :       }
      50         900 :       _blooms += bloom_footprint;
      51         900 :     }
      52          75 :   }
      53             : 
      54           3 :   FD_COMPILER_MFENCE();
      55           3 :   FD_VOLATILE( as->magic ) = FD_ACTIVE_SET_MAGIC;
      56           3 :   FD_COMPILER_MFENCE();
      57             : 
      58           3 :   return (void *)as;
      59           3 : }
      60             : 
      61             : fd_active_set_t *
      62           3 : fd_active_set_join( void * shas ) {
      63           3 :   if( FD_UNLIKELY( !shas ) ) {
      64           0 :     FD_LOG_WARNING(( "NULL shas" ));
      65           0 :     return NULL;
      66           0 :   }
      67             : 
      68           3 :   if( FD_UNLIKELY( !fd_ulong_is_aligned( (ulong)shas, fd_active_set_align() ) ) ) {
      69           0 :     FD_LOG_WARNING(( "misaligned shas" ));
      70           0 :     return NULL;
      71           0 :   }
      72             : 
      73           3 :   fd_active_set_t * as = (fd_active_set_t *)shas;
      74             : 
      75           3 :   if( FD_UNLIKELY( as->magic!=FD_ACTIVE_SET_MAGIC ) ) {
      76           0 :     FD_LOG_WARNING(( "bad magic" ));
      77           0 :     return NULL;
      78           0 :   }
      79             : 
      80           3 :   return as;
      81           3 : }
      82             : 
      83             : ulong
      84             : fd_active_set_nodes( fd_active_set_t * active_set,
      85             :                      uchar const *     identity_pubkey,
      86             :                      ulong             identity_stake,
      87             :                      uchar const *     origin,
      88             :                      ulong             origin_stake,
      89             :                      int               ignore_prunes_if_peer_is_origin,
      90           3 :                      ulong             out_nodes[ static 12UL ] ) {
      91           3 :   ulong stake_bucket = fd_active_set_stake_bucket( fd_ulong_min( identity_stake, origin_stake ) );
      92           3 :   fd_active_set_entry_t * entry = active_set->entries[ stake_bucket ];
      93             : 
      94           3 :   int identity_eq_origin = !memcmp( identity_pubkey, origin, 32UL );
      95             : 
      96           3 :   ulong out_idx = 0UL;
      97           3 :   for( ulong i=0UL; i<entry->nodes_len; i++ ) {
      98           0 :     fd_active_set_peer_t * peer = entry->nodes[ (entry->nodes_idx+i) % 12UL ];
      99             : 
     100           0 :     int must_push_if_peer_is_origin = ignore_prunes_if_peer_is_origin && !memcmp( peer->pubkey, origin, 32UL );
     101           0 :     int must_push_own_values = identity_eq_origin && !memcmp( peer->pubkey, identity_pubkey, 32UL ); /* why ? */
     102           0 :     if( FD_UNLIKELY( fd_bloom_contains( peer->bloom, origin, 32UL ) && !must_push_own_values && !must_push_if_peer_is_origin ) ) continue;
     103           0 :     out_nodes[ out_idx++ ] = stake_bucket*12UL + i;
     104           0 :   }
     105           3 :   return out_idx;
     106           3 : }
     107             : 
     108             : uchar const *
     109             : fd_active_set_node_pubkey( fd_active_set_t * active_set,
     110           0 :                            ulong             peer_idx ){
     111           0 :   ulong bucket = peer_idx / FD_ACTIVE_SET_PEERS_PER_ENTRY;
     112           0 :   ulong idx    = peer_idx % FD_ACTIVE_SET_PEERS_PER_ENTRY;
     113           0 :   if( FD_UNLIKELY( bucket>=FD_ACTIVE_SET_STAKE_ENTRIES ) ) {
     114           0 :     FD_LOG_ERR(( "peer_idx out of range" ));
     115           0 :   }
     116           0 :   if( FD_UNLIKELY( active_set->entries[ bucket ]->nodes_len<=idx ) ) {
     117           0 :     FD_LOG_ERR(( "peer_idx out of range within bucket" ));
     118           0 :   }
     119             : 
     120           0 :   return active_set->entries[ bucket ]->nodes[ idx ]->pubkey;
     121           0 : }
     122             : 
     123             : void
     124             : fd_active_set_prune( fd_active_set_t * active_set,
     125             :                      uchar const *     push_dest,
     126             :                      uchar const *     origin,
     127             :                      ulong             origin_stake,
     128             :                      uchar const *     identity_pubkey,
     129           0 :                      ulong             identity_stake ) {
     130           0 :   if( FD_UNLIKELY( !memcmp( identity_pubkey, origin, 32UL ) ) ) return;
     131             : 
     132           0 :   ulong bucket = fd_active_set_stake_bucket( fd_ulong_min( identity_stake, origin_stake ) );
     133           0 :   for( ulong i=0UL; i<12UL; i++ ) {
     134           0 :     if( FD_UNLIKELY( !memcmp( active_set->entries[ bucket ]->nodes[ i ]->pubkey, push_dest, 32UL ) ) ) {
     135           0 :       fd_bloom_insert( active_set->entries[ bucket ]->nodes[ i ]->bloom, origin, 32UL );
     136           0 :       return;
     137           0 :     }
     138           0 :   }
     139           0 : }
     140             : 
     141             : ulong
     142             : fd_active_set_rotate( fd_active_set_t * active_set,
     143           3 :                       fd_crds_t *       crds ) {
     144           3 :   ulong num_bloom_filter_items = fd_ulong_max( fd_crds_peer_count( crds ), 512UL );
     145             : 
     146           3 :   ulong bucket = fd_rng_ulong_roll( active_set->rng, 25UL );
     147           3 :   fd_active_set_entry_t * entry = active_set->entries[ bucket ];
     148             : 
     149           3 :   ulong replace_idx;
     150             : 
     151           3 :   if( FD_LIKELY( entry->nodes_len==12UL ) ) {
     152           0 :     replace_idx      = entry->nodes_idx;
     153           0 :     entry->nodes_idx = (entry->nodes_idx+1UL) % 12UL;
     154           0 :     fd_crds_bucket_add( crds, bucket, entry->nodes[ replace_idx ]->pubkey );
     155           3 :   } else {
     156           3 :     replace_idx = entry->nodes_len;
     157           3 :   }
     158             : 
     159           3 :   fd_active_set_peer_t * replace = entry->nodes[ replace_idx ];
     160             : 
     161           3 :   fd_contact_info_t const * new_peer = fd_crds_bucket_sample_and_remove( crds, active_set->rng, bucket );
     162           3 :   if( FD_UNLIKELY( !new_peer ) ) {
     163           0 :     return ULONG_MAX;
     164           0 :   }
     165             : 
     166           3 :   fd_bloom_initialize( replace->bloom, num_bloom_filter_items );
     167           3 :   fd_bloom_insert( replace->bloom, new_peer->pubkey.uc, 32UL );
     168           3 :   fd_memcpy( replace->pubkey, new_peer->pubkey.uc, 32UL );
     169           3 :   entry->nodes_len = fd_ulong_min( entry->nodes_len+1UL, 12UL );
     170           3 :   return bucket*12UL+replace_idx;
     171           3 : }