Line data    Source code

       1             : #include "fd_top_votes.h"
       2             : 
       3          24 : #define FD_TOP_VOTES_MAGIC (0xF17EDA2CE7401E70UL) /* FIREDANCER TOP VOTES V0 */
       4             : 
       5             : struct fd_top_votes {
       6             :   ulong magic;
       7             :   ulong pool_off;
       8             :   ulong heap_off;
       9             :   ulong map_off;
      10             : 
      11             :   ulong min_stake_wmark;
      12             : };
      13             : typedef struct fd_top_votes fd_top_votes_t;
      14             : 
      15             : struct vote_ele {
      16             :   fd_pubkey_t pubkey;
      17             :   fd_pubkey_t node_account;
      18             :   ulong       stake;
      19             :   ulong       last_vote_slot;
      20             :   long        last_vote_timestamp;
      21             :   uchar       is_valid;
      22             : 
      23             :   ushort      left;
      24             :   ushort      right;
      25             :   ushort      next;
      26             : };
      27             : typedef struct vote_ele vote_ele_t;
      28             : 
      29             : #define HEAP_NAME       heap
      30         590 : #define HEAP_IDX_T      ushort
      31             : #define HEAP_T          vote_ele_t
      32           0 : #define HEAP_LT(e0,e1) ( ((e0)->stake < (e1)->stake) | \
      33           0 :                          (((e0)->stake==(e1)->stake) & \
      34           0 :                           (memcmp( &(e0)->pubkey, &(e1)->pubkey, sizeof(fd_pubkey_t) )<0 ) ) )
      35             : #include "../../util/tmpl/fd_heap.c"
      36             : 
      37             : #define POOL_NAME  pool
      38          48 : #define POOL_T     vote_ele_t
      39             : #define POOL_IDX_T ushort
      40             : #include "../../util/tmpl/fd_pool.c"
      41             : 
      42             : #define MAP_NAME               map
      43             : #define MAP_KEY_T              fd_pubkey_t
      44             : #define MAP_ELE_T              vote_ele_t
      45         301 : #define MAP_KEY                pubkey
      46         896 : #define MAP_KEY_EQ(k0,k1)      (!memcmp( k0, k1, sizeof(fd_pubkey_t) ))
      47        1197 : #define MAP_KEY_HASH(key,seed) (fd_hash( seed, key, sizeof(fd_pubkey_t) ))
      48        1821 : #define MAP_IDX_T              ushort
      49             : #include "../../util/tmpl/fd_map_chain.c"
      50             : 
      51             : static inline vote_ele_t *
      52        1797 : get_pool( fd_top_votes_t const * top_votes ) {
      53        1797 :   return (vote_ele_t *)( (ulong)top_votes + top_votes->pool_off );
      54        1797 : }
      55             : 
      56             : static inline heap_t *
      57         901 : get_heap( fd_top_votes_t const * top_votes ) {
      58         901 :   return (heap_t *)( (ulong)top_votes + top_votes->heap_off );
      59         901 : }
      60             : 
      61             : static inline map_t *
      62        1797 : get_map( fd_top_votes_t const * top_votes ) {
      63        1797 :   return (map_t *)( (ulong)top_votes + top_votes->map_off );
      64        1797 : }
      65             : 
      66             : ulong
      67         288 : fd_top_votes_align( void ) {
      68         288 :   return FD_TOP_VOTES_ALIGN;
      69         288 : }
      70             : 
      71             : ulong
      72          48 : fd_top_votes_footprint( ulong vote_accounts_max ) {
      73          48 :   ulong map_chain_cnt = map_chain_cnt_est( vote_accounts_max );
      74             : 
      75          48 :   ulong l = FD_LAYOUT_INIT;
      76          48 :   l = FD_LAYOUT_APPEND( l, fd_top_votes_align(), sizeof(fd_top_votes_t) );
      77          48 :   l = FD_LAYOUT_APPEND( l, pool_align(),         pool_footprint( vote_accounts_max ) );
      78          48 :   l = FD_LAYOUT_APPEND( l, heap_align(),         heap_footprint( vote_accounts_max ) );
      79          48 :   l = FD_LAYOUT_APPEND( l, map_align(),          map_footprint( map_chain_cnt ) );
      80          48 :   return FD_LAYOUT_FINI( l, fd_top_votes_align() );
      81          48 : }
      82             : 
      83             : void *
      84             : fd_top_votes_new( void * mem,
      85             :                   ushort vote_accounts_max,
      86          24 :                   ulong  seed ) {
      87          24 :   if( FD_UNLIKELY( !mem ) ) {
      88           0 :     FD_LOG_WARNING(( "NULL mem" ));
      89           0 :     return NULL;
      90           0 :   }
      91             : 
      92          24 :   if( FD_UNLIKELY( !fd_ulong_is_aligned( (ulong)mem, fd_top_votes_align() ) ) ) {
      93           0 :     FD_LOG_WARNING(( "misaligned mem" ));
      94           0 :     return NULL;
      95           0 :   }
      96             : 
      97          24 :   ulong map_chain_cnt = map_chain_cnt_est( vote_accounts_max );
      98             : 
      99          24 :   FD_SCRATCH_ALLOC_INIT( l, mem );
     100          24 :   fd_top_votes_t * top_votes = FD_SCRATCH_ALLOC_APPEND( l, fd_top_votes_align(), sizeof(fd_top_votes_t) );
     101          24 :   void *           pool_mem  = FD_SCRATCH_ALLOC_APPEND( l, pool_align(),         pool_footprint( vote_accounts_max ) );
     102          24 :   void *           heap_mem  = FD_SCRATCH_ALLOC_APPEND( l, heap_align(),         heap_footprint( vote_accounts_max ) );
     103          24 :   void *           map_mem   = FD_SCRATCH_ALLOC_APPEND( l, map_align(),          map_footprint( map_chain_cnt ) );
     104             : 
     105          24 :   if( FD_UNLIKELY( FD_SCRATCH_ALLOC_FINI( l, fd_top_votes_align() ) != (ulong)top_votes + fd_top_votes_footprint( vote_accounts_max ) ) ) {
     106           0 :     FD_LOG_WARNING(( "fd_banks_new: bad layout" ));
     107           0 :     return NULL;
     108           0 :   }
     109             : 
     110          24 :   if( FD_UNLIKELY( fd_top_votes_footprint( vote_accounts_max )>FD_TOP_VOTES_MAX_FOOTPRINT ) ) {
     111           0 :     FD_LOG_WARNING(( "fd_top_votes_new: bad footprint" ));
     112           0 :     return NULL;
     113           0 :   }
     114             : 
     115          24 :   vote_ele_t * pool = pool_join( pool_new( pool_mem, vote_accounts_max ) );
     116          24 :   if( FD_UNLIKELY( !pool ) ) {
     117           0 :     FD_LOG_WARNING(( "Failed to create top votes pool" ));
     118           0 :     return NULL;
     119           0 :   }
     120          24 :   top_votes->pool_off = (ulong)pool - (ulong)mem;
     121             : 
     122          24 :   heap_t * heap = heap_join( heap_new( heap_mem, vote_accounts_max ) );
     123          24 :   if( FD_UNLIKELY( !heap ) ) {
     124           0 :     FD_LOG_WARNING(( "Failed to create top votes heap" ));
     125           0 :     return NULL;
     126           0 :   }
     127          24 :   top_votes->heap_off = (ulong)heap - (ulong)mem;
     128             : 
     129          24 :   map_t * map = map_join( map_new( map_mem, map_chain_cnt, seed ) );
     130          24 :   if( FD_UNLIKELY( !map ) ) {
     131           0 :     FD_LOG_WARNING(( "Failed to create top votes map" ));
     132           0 :     return NULL;
     133           0 :   }
     134          24 :   top_votes->map_off = (ulong)map - (ulong)mem;
     135             : 
     136          24 :   FD_COMPILER_MFENCE();
     137          24 :   FD_VOLATILE( top_votes->magic ) = FD_TOP_VOTES_MAGIC;
     138          24 :   FD_COMPILER_MFENCE();
     139             : 
     140          24 :   return top_votes;
     141          24 : }
     142             : 
     143             : fd_top_votes_t *
     144          24 : fd_top_votes_join( void * mem ) {
     145          24 :   fd_top_votes_t * top_votes = (fd_top_votes_t *)mem;
     146             : 
     147          24 :   if( FD_UNLIKELY( !top_votes ) ) {
     148           0 :     FD_LOG_WARNING(( "NULL top votes" ));
     149           0 :     return NULL;
     150           0 :   }
     151             : 
     152          24 :   if( FD_UNLIKELY( top_votes->magic!=FD_TOP_VOTES_MAGIC ) ) {
     153           0 :     FD_LOG_WARNING(( "Invalid top votes magic" ));
     154           0 :     return NULL;
     155           0 :   }
     156             : 
     157          24 :   return top_votes;
     158          24 : }
     159             : 
     160             : void
     161         600 : fd_top_votes_init( fd_top_votes_t * top_votes ) {
     162         600 :   vote_ele_t * pool = get_pool( top_votes );
     163         600 :   heap_t *     heap = get_heap( top_votes );
     164         600 :   map_t *      map  = get_map( top_votes );
     165             : 
     166         600 :   top_votes->min_stake_wmark = 0UL;
     167             : 
     168             :   /* TODO: A smarter reset can probably be done here. */
     169         889 :   while( heap_ele_cnt( heap ) ) heap_ele_remove_min( heap, pool );
     170             : 
     171         600 :   map_reset( map );
     172         600 :   pool_reset( pool );
     173         600 : }
     174             : 
     175             : void
     176             : fd_top_votes_insert( fd_top_votes_t *    top_votes,
     177             :                      fd_pubkey_t const * pubkey,
     178             :                      fd_pubkey_t const * node_account,
     179             :                      ulong               stake,
     180             :                      ulong               last_vote_slot,
     181         301 :                      long                last_vote_timestamp ) {
     182             : /* If the heap is full, then we need to remove the minimum element.
     183             :    There are a few cases to consider:
     184             :    1. There are multiple elements at the bottom of the heap with the
     185             :       same stake.  In this case, evict all of them and insert the new
     186             :       element.
     187             :    2. The element we are attempting to insert has the same stake as
     188             :       the minimum element.  In this case, we remove all elements with
     189             :       the minimum stake and don't insert a new element.  We need to
     190             :       watermark the minimum stake value that was evicted to avoid
     191             :       allowing later inserts with the same stake.
     192             :    3. Don't insert the new element if it has a stake less than the
     193             :       watermark. */
     194             : 
     195         301 :   vote_ele_t * pool = get_pool( top_votes );
     196         301 :   heap_t *     heap = get_heap( top_votes );
     197         301 :   map_t *      map  = get_map( top_votes );
     198             : 
     199         301 :   if( FD_UNLIKELY( stake<=top_votes->min_stake_wmark ) ) return;
     200             : 
     201         301 :   if( FD_UNLIKELY( heap_ele_cnt( heap )==heap_ele_max( heap ) ) ) {
     202           0 :     vote_ele_t * ele = heap_ele_peek_min( heap, pool );
     203           0 :     if( stake<ele->stake ) return;
     204             : 
     205             :     /* If the prospective element ties with the minimum element, remove
     206             :        all elements with the same stake and update the watermark. */
     207           0 :     if( FD_UNLIKELY( stake==ele->stake ) ) {
     208           0 :       top_votes->min_stake_wmark = stake;
     209           0 :       while( (ele=heap_ele_peek_min( heap, pool )) && ele && ele->stake==stake ) {
     210           0 :         heap_ele_remove_min( heap, pool );
     211           0 :         map_ele_remove( map, &ele->pubkey, NULL, pool );
     212           0 :         pool_ele_release( pool, ele );
     213           0 :       }
     214           0 :       return;
     215           0 :     }
     216             : 
     217           0 :     ulong min_stake = ele->stake;
     218           0 :     while( (ele=heap_ele_peek_min( heap, pool )) && ele && min_stake==ele->stake ) {
     219           0 :       heap_ele_remove_min( heap, pool );
     220           0 :       map_ele_remove( map, &ele->pubkey, NULL, pool );
     221           0 :       pool_ele_release( pool, ele );
     222           0 :     }
     223           0 :   }
     224             : 
     225         301 :   vote_ele_t * ele         = pool_ele_acquire( pool );
     226         301 :   ele->pubkey              = *pubkey;
     227         301 :   ele->node_account        = *node_account;
     228         301 :   ele->stake               = stake;
     229         301 :   ele->last_vote_slot      = last_vote_slot;
     230         301 :   ele->last_vote_timestamp = last_vote_timestamp;
     231         301 :   ele->is_valid            = 1;
     232         301 :   heap_ele_insert( heap, ele, pool );
     233         301 :   map_ele_insert( map, ele, pool );
     234         301 : }
     235             : 
     236             : void
     237             : fd_top_votes_update( fd_top_votes_t *    top_votes,
     238             :                      fd_pubkey_t const * pubkey,
     239             :                      ulong               last_vote_slot,
     240         598 :                      long                last_vote_timestamp ) {
     241         598 :   vote_ele_t * pool = get_pool( top_votes );
     242         598 :   map_t *      map  = get_map( top_votes );
     243             : 
     244         598 :   ushort idx = (ushort)map_idx_query_const( map, pubkey, USHORT_MAX, pool );
     245         598 :   if( FD_UNLIKELY( idx==USHORT_MAX ) ) return;
     246         598 :   vote_ele_t * ele = pool_ele( pool, idx );
     247         598 :   ele->last_vote_slot      = last_vote_slot;
     248         598 :   ele->last_vote_timestamp = last_vote_timestamp;
     249         598 :   ele->is_valid            = 1;
     250         598 : }
     251             : 
     252             : void
     253             : fd_top_votes_invalidate( fd_top_votes_t *    top_votes,
     254           0 :                          fd_pubkey_t const * pubkey ) {
     255           0 :   vote_ele_t * pool = get_pool( top_votes );
     256           0 :   map_t *      map  = get_map( top_votes );
     257             : 
     258           0 :   ushort idx = (ushort)map_idx_query_const( map, pubkey, USHORT_MAX, pool );
     259           0 :   if( FD_UNLIKELY( idx==USHORT_MAX ) ) return;
     260           0 :   pool_ele( pool, idx )->is_valid = 0;
     261           0 : }
     262             : 
     263             : int
     264             : fd_top_votes_query( fd_top_votes_t const * top_votes,
     265             :                     fd_pubkey_t const *    pubkey,
     266             :                     fd_pubkey_t *          node_account_out_opt,
     267             :                     ulong *                stake_out_opt,
     268             :                     ulong *                last_vote_slot_out_opt,
     269         299 :                     long *                 last_vote_timestamp_out_opt ) {
     270         299 :   vote_ele_t * pool = get_pool( top_votes );
     271         299 :   map_t *      map  = get_map( top_votes );
     272             : 
     273         299 :   vote_ele_t const * ele = map_ele_query_const( map, pubkey, NULL, pool );
     274         299 :   if( FD_UNLIKELY( !ele ) ) return 0;
     275         299 :   if( FD_UNLIKELY( !ele->is_valid ) ) return 0;
     276             : 
     277         299 :   if( node_account_out_opt )        *node_account_out_opt        = ele->node_account;
     278         299 :   if( stake_out_opt )               *stake_out_opt               = ele->stake;
     279         299 :   if( last_vote_slot_out_opt )      *last_vote_slot_out_opt      = ele->last_vote_slot;
     280         299 :   if( last_vote_timestamp_out_opt ) *last_vote_timestamp_out_opt = ele->last_vote_timestamp;
     281         299 :   return 1;
     282         299 : }
     283             : 
     284             : FD_STATIC_ASSERT( FD_TOP_VOTES_ITER_FOOTPRINT == sizeof(map_iter_t), top_votes_iter );
     285             : FD_STATIC_ASSERT( FD_TOP_VOTES_ITER_ALIGN == alignof(map_iter_t), top_votes_iter );
     286             : 
     287             : static void
     288             : fd_top_votes_iter_skip_invalid( fd_top_votes_t const * top_votes,
     289           0 :                                 map_iter_t *           iter ) {
     290           0 :   map_t *      map  = get_map( top_votes );
     291           0 :   vote_ele_t * pool = get_pool( top_votes );
     292           0 :   while( !map_iter_done( *iter, map, pool ) ) {
     293           0 :     vote_ele_t * ele = map_iter_ele( *iter, map, pool );
     294           0 :     if( FD_LIKELY( ele->is_valid ) ) break;
     295           0 :     *iter = map_iter_next( *iter, map, pool );
     296           0 :   }
     297           0 : }
     298             : 
     299             : fd_top_votes_iter_t *
     300             : fd_top_votes_iter_init( fd_top_votes_t const * top_votes,
     301           0 :                         uchar                  iter_mem[ static FD_TOP_VOTES_ITER_FOOTPRINT ] ) {
     302           0 :   map_iter_t iter = map_iter_init( get_map( top_votes ), get_pool( top_votes ) );
     303           0 :   fd_top_votes_iter_skip_invalid( top_votes, &iter );
     304           0 :   memcpy( iter_mem, &iter, sizeof(map_iter_t) );
     305           0 :   return (fd_top_votes_iter_t *)iter_mem;
     306           0 : }
     307             : 
     308             : int
     309             : fd_top_votes_iter_done( fd_top_votes_t const * top_votes,
     310           0 :                         fd_top_votes_iter_t *  iter ) {
     311           0 :   map_iter_t * map_iter = (map_iter_t *)iter;
     312           0 :   return map_iter_done( *map_iter, get_map( top_votes ), get_pool( top_votes ) );
     313           0 : }
     314             : 
     315             : void
     316             : fd_top_votes_iter_next( fd_top_votes_t const * top_votes,
     317           0 :                         fd_top_votes_iter_t *  iter ) {
     318           0 :   map_iter_t * map_iter = (map_iter_t *)iter;
     319           0 :   *map_iter = map_iter_next( *map_iter, get_map( top_votes ), get_pool( top_votes ) );
     320           0 :   fd_top_votes_iter_skip_invalid( top_votes, map_iter );
     321           0 : }
     322             : 
     323             : void
     324             : fd_top_votes_iter_ele( fd_top_votes_t const * top_votes,
     325             :                        fd_top_votes_iter_t *  iter,
     326             :                        fd_pubkey_t *          pubkey_out,
     327             :                        fd_pubkey_t *          node_account_out_opt,
     328             :                        ulong *                stake_out_opt,
     329             :                        ulong *                last_vote_slot_out_opt,
     330           0 :                        long *                 last_vote_timestamp_out_opt ) {
     331           0 :   map_iter_t * map_iter = (map_iter_t *)iter;
     332           0 :   vote_ele_t * ele      = map_iter_ele( *map_iter, get_map( top_votes ), get_pool( top_votes ) );
     333           0 :   *pubkey_out = ele->pubkey;
     334             : 
     335           0 :   if( node_account_out_opt )        *node_account_out_opt        = ele->node_account;
     336           0 :   if( stake_out_opt )               *stake_out_opt               = ele->stake;
     337           0 :   if( last_vote_slot_out_opt )      *last_vote_slot_out_opt      = ele->last_vote_slot;
     338           0 :   if( last_vote_timestamp_out_opt ) *last_vote_timestamp_out_opt = ele->last_vote_timestamp;
     339           0 : }