Line data    Source code

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