Line data    Source code

       1             : #ifndef HEADER_fd_src_choreo_tower_fd_tower_stakes_h
       2             : #define HEADER_fd_src_choreo_tower_fd_tower_stakes_h
       3             : 
       4             : /* fd_tower_stakes_t tracks stakes of the top k voters in a slot (as of
       5             :    SIMD-0357, k=2000).  While the stakes are usually the same for every
       6             :    slot in a given epoch, it is not guaranteed.  Specifically, if there
       7             :    is a fork across an epoch boundary, the set of voters and their
       8             :    stakes may be different across slots in the same epoch because the
       9             :    slots are on different forks that calculated the stakes differently.
      10             :    If we have not rooted a slot in the new epoch yet, this could be
      11             :    different from other forks, but if we have rooted an epoch slot, the
      12             :    stakes for each voter are the same for all forks that descend from
      13             :    that root (forks that do not descend will have been pruned).
      14             : 
      15             :    This is currently exclusively used for the switch check, which
      16             :    requires the stakes of each voter on the HEAVIEST fork in the epoch.
      17             :    We need to do all this tracking because tower cannot query the vote
      18             :    states from any bank at will.  Replay determines which banks can be
      19             :    queried, and won't know beforehand which banks will be the heaviest.
      20             : 
      21             :    fd_tower_stakes_t is backed by two hash maps:
      22             :    1. fd_tower_stakes_vtr_map: this maps a vote account to a voter stake
      23             :    2. fd_tower_stakes_slot_map: this maps a slot to a voter stake index
      24             : 
      25             :    The voter_stake_map has a compound key {vote_account, slot}, so that
      26             :    the map can be queries O(1) by slot and vote account. As we populate
      27             :    the map, we also thread a linkedlist through all the entries for the
      28             :    same slot. This is possible because the vote stake map is populated/
      29             :    updated all at once when a slot arrives from the bank, so we can
      30             :    sequentially link the current entry to the previous entry. Then the
      31             :    last entry in the linkedlist (last voter we process for a slot) will
      32             :    have its key {vote_account, slot} put in the slot_stakes_map. This
      33             :    way on publish, we have a way to query all the stakes / voters for a
      34             :    slot without doing a full scan of the voter_stake_map. */
      35             : 
      36             : #include "../fd_choreo_base.h"
      37             : 
      38             : struct fd_tower_stakes_vtr_xid {
      39             :     fd_hash_t addr; /* vote account address */
      40             :     ulong     slot;
      41             : };
      42             : typedef struct fd_tower_stakes_vtr_xid fd_tower_stakes_vtr_xid_t;
      43             : 
      44             : static const fd_tower_stakes_vtr_xid_t fd_tower_stakes_vtr_xid_null = { .addr = {{ 0 }}, .slot = 0UL };
      45             : 
      46             : struct fd_tower_stakes_vtr {
      47             :   fd_tower_stakes_vtr_xid_t key;
      48             :   ulong                     prev;
      49             :   ulong                     next;
      50             :   ulong                     stake;
      51             : };
      52             : typedef struct fd_tower_stakes_vtr fd_tower_stakes_vtr_t;
      53             : 
      54             : #define MAP_NAME                fd_tower_stakes_vtr_map
      55             : #define MAP_ELE_T               fd_tower_stakes_vtr_t
      56             : #define MAP_KEY_T               fd_tower_stakes_vtr_xid_t
      57          33 : #define MAP_KEY_EQ(k0,k1)       (!memcmp( k0, k1, sizeof(fd_tower_stakes_vtr_xid_t) ))
      58          93 : #define MAP_KEY_HASH(key, seed) fd_ulong_hash( ((key)->slot) ^ ((key)->addr.ul[0]) ^ (seed) )
      59             : #include "../../util/tmpl/fd_map_chain.c"
      60             : 
      61             : #define POOL_NAME fd_tower_stakes_vtr_pool
      62         108 : #define POOL_T    fd_tower_stakes_vtr_t
      63             : #include "../../util/tmpl/fd_pool.c"
      64             : 
      65             : /* Some really terrible witchcraft to track used vote accounts for
      66             :    whatever reason. For example, switch check needs to make sure it's
      67             :    not repeating usage of the same vote account. We can flip a bit on
      68             :    the vote stake pool index if its been used. Caller should ensure that
      69             :    the set is cleared before and after each use. The size of the set
      70             :    will be the number of elements in the vote stake pool. */
      71             : 
      72             : #define SET_NAME    fd_used_acc_scratch
      73             : #include "../../util/tmpl/fd_set_dynamic.c"
      74             : 
      75             : struct fd_tower_stakes_slot {
      76             :   ulong slot;
      77             :   ulong head; /* pool idx of the head of a linked list of voters in this slot */
      78             : };
      79             : typedef struct fd_tower_stakes_slot fd_tower_stakes_slot_t;
      80             : 
      81             : #define MAP_NAME           fd_tower_stakes_slot
      82         219 : #define MAP_T              fd_tower_stakes_slot_t
      83        5163 : #define MAP_KEY            slot
      84        5052 : #define MAP_KEY_NULL       ULONG_MAX
      85         111 : #define MAP_KEY_INVAL(key) ((key)==ULONG_MAX)
      86             : #define MAP_MEMOIZE        0
      87             : #include "../../util/tmpl/fd_map_dynamic.c"
      88             : 
      89             : struct fd_tower;
      90             : 
      91             : FD_PROTOTYPES_BEGIN
      92             : 
      93             : /* fd_tower_stakes_insert adds a new (voter, stake) pair to the epoch
      94             :    stakes for a specific slot, and returns the index of the new voter
      95             :    stake in the pool.  prev_voter_idx is the index of the previous voter
      96             :    stake in the pool.  If this is the first voter inserted for this
      97             :    slot, prev_voter_idx should be ULONG_MAX.  Example usage:
      98             : 
      99             :    prev_voter_idx = ULONG_MAX;
     100             :    for( v : voters ) {
     101             :      voter_idx = fd_tower_stakes_insert( tower, slot, v.vote_account, v.stake, prev_voter_idx );
     102             :      prev_voter_idx = voter_idx;
     103             :    } */
     104             : 
     105             : ulong
     106             : fd_tower_stakes_insert( struct fd_tower *  tower,
     107             :                         ulong              slot,
     108             :                         fd_hash_t const *  vote_account,
     109             :                         ulong              stake,
     110             :                         ulong              prev_voter_idx );
     111             : 
     112             : void
     113             : fd_tower_stakes_remove( struct fd_tower * tower,
     114             :                         ulong             slot );
     115             : 
     116             : #endif /* HEADER_fd_src_choreo_tower_fd_tower_stakes_h */