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             : */
      37             : 
      38             : #include "../fd_choreo_base.h"
      39             : 
      40             : struct fd_tower_stakes_vtr_xid {
      41             :     fd_hash_t addr; /* vote account address */
      42             :     ulong     slot;
      43             : };
      44             : typedef struct fd_tower_stakes_vtr_xid fd_tower_stakes_vtr_xid_t;
      45             : 
      46             : static const fd_tower_stakes_vtr_xid_t fd_tower_stakes_vtr_xid_null = { .addr = {{ 0 }}, .slot = 0UL };
      47             : 
      48             : struct fd_tower_stakes_vtr {
      49             :   fd_tower_stakes_vtr_xid_t key;
      50             :   ulong                     prev;
      51             :   ulong                     next;
      52             :   ulong                     stake;
      53             : };
      54             : typedef struct fd_tower_stakes_vtr fd_tower_stakes_vtr_t;
      55             : 
      56             : #define MAP_NAME                fd_tower_stakes_vtr_map
      57             : #define MAP_ELE_T               fd_tower_stakes_vtr_t
      58             : #define MAP_KEY_T               fd_tower_stakes_vtr_xid_t
      59           0 : #define MAP_KEY_EQ(k0,k1)       (!memcmp( k0, k1, sizeof(fd_tower_stakes_vtr_xid_t) ))
      60           0 : #define MAP_KEY_HASH(key, seed) fd_ulong_hash( ((key)->slot) ^ ((key)->addr.ul[0]) ^ (seed) )
      61             : #include "../../util/tmpl/fd_map_chain.c"
      62             : 
      63             : #define POOL_NAME fd_tower_stakes_vtr_pool
      64           0 : #define POOL_T    fd_tower_stakes_vtr_t
      65             : #include "../../util/tmpl/fd_pool.c"
      66             : 
      67             : /* Some really terrible witchcraft to track used vote accounts for
      68             :    whatever reason. For example, switch check needs to make sure it's
      69             :    not repeating usage of the same vote account. We can flip a bit on
      70             :    the vote stake pool index if its been used. Caller should ensure that
      71             :    the set is cleared before and after each use. The size of the set
      72             :    will be the number of elements in the vote stake pool. */
      73             : 
      74             : #define SET_NAME    fd_used_acc_scratch
      75             : #include "../../util/tmpl/fd_set_dynamic.c"
      76             : 
      77             : struct fd_tower_stakes_slot {
      78             :   ulong slot;
      79             :   ulong head; /* pool idx of the head of a linked list of voters in this slot */
      80             : };
      81             : typedef struct fd_tower_stakes_slot fd_tower_stakes_slot_t;
      82             : 
      83             : #define MAP_NAME           fd_tower_stakes_slot
      84           0 : #define MAP_T              fd_tower_stakes_slot_t
      85           0 : #define MAP_KEY            slot
      86           0 : #define MAP_KEY_NULL       ULONG_MAX
      87           0 : #define MAP_KEY_INVAL(key) ((key)==ULONG_MAX)
      88             : #define MAP_MEMOIZE        0
      89             : #include "../../util/tmpl/fd_map_dynamic.c"
      90             : 
      91             : struct __attribute__((aligned(128UL))) fd_tower_stakes {
      92             :   fd_tower_stakes_vtr_map_t * vtr_map;
      93             :   fd_tower_stakes_vtr_t *     vtr_pool;
      94             :   fd_tower_stakes_slot_t *    slot_map;
      95             :   fd_used_acc_scratch_t *     used_acc_scratch;
      96             : };
      97             : typedef struct fd_tower_stakes fd_tower_stakes_t;
      98             : 
      99             : FD_PROTOTYPES_BEGIN
     100             : 
     101             : FD_FN_CONST static inline ulong
     102           0 : fd_tower_stakes_align( void ) {
     103           0 :   return alignof(fd_tower_stakes_t);
     104           0 : }
     105             : 
     106             : FD_FN_CONST static inline ulong
     107           0 : fd_tower_stakes_footprint( ulong slot_max ) {
     108           0 :   int lg_slot_cnt = fd_ulong_find_msb( fd_ulong_pow2_up( slot_max ) ) + 1;
     109           0 :   return FD_LAYOUT_FINI(
     110           0 :     FD_LAYOUT_APPEND(
     111           0 :     FD_LAYOUT_APPEND(
     112           0 :     FD_LAYOUT_APPEND(
     113           0 :     FD_LAYOUT_APPEND(
     114           0 :     FD_LAYOUT_APPEND(
     115           0 :     FD_LAYOUT_INIT,
     116           0 :       alignof(fd_tower_stakes_t),       sizeof(fd_tower_stakes_t)                                     ),
     117           0 :       fd_tower_stakes_vtr_map_align(),  fd_tower_stakes_vtr_map_footprint ( FD_VOTER_MAX * slot_max ) ),
     118           0 :       fd_tower_stakes_vtr_pool_align(), fd_tower_stakes_vtr_pool_footprint( FD_VOTER_MAX * slot_max ) ),
     119           0 :       fd_tower_stakes_slot_align(),      fd_tower_stakes_slot_footprint( lg_slot_cnt )                  ),
     120           0 :       fd_used_acc_scratch_align(),      fd_used_acc_scratch_footprint( FD_VOTER_MAX * slot_max )      ),
     121           0 :     fd_tower_stakes_align() );
     122           0 : }
     123             : 
     124             : /* fd_tower_stakes_new formats an unused memory region for use as a
     125             :    tower_stakes.  mem is a non-NULL pointer to this region in the local
     126             :    address space with the required footprint and alignment. */
     127             : 
     128             : void *
     129             : fd_tower_stakes_new( void * shmem,
     130             :                      ulong  slot_max,
     131             :                      ulong  seed );
     132             : 
     133             : /* fd_tower_stakes_join joins the caller to the tower_stakes. shstakes
     134             :    points to the first byte of the memory region backing the shstakes in
     135             :    the caller's address space.
     136             : 
     137             :    Returns a pointer in the local address space to stakes on success. */
     138             : 
     139             : fd_tower_stakes_t *
     140             : fd_tower_stakes_join( void * shstakes );
     141             : 
     142             : /* fd_tower_stakes_leave stakes a current local join.  Returns a pointer
     143             :    to the underlying shared memory region on success and NULL on failure
     144             :    (logs details).  Reasons for failure include stakes is NULL. */
     145             : 
     146             : void *
     147             : fd_tower_stakes_leave( fd_tower_stakes_t const * stakes );
     148             : 
     149             : /* fd_tower_stakes_delete unformats a memory region used as a stakes.
     150             :    Assumes only the local process is joined to the region.  Returns a
     151             :    pointer to the underlying shared memory region or NULL if used
     152             :    obviously in error (e.g. stakes is obviously not a stakes ...  logs
     153             :    details).  The ownership of the memory region is transferred to the
     154             :    caller. */
     155             : 
     156             : void *
     157             : fd_tower_stakes_delete( void * stakes );
     158             : 
     159             : /* fd_tower_stakes_insert adds a new (voter, stake) pair to the epoch
     160             :    stakes for a specific slot, and returns the index of the new voter
     161             :    stake in the pool.  prev_voter_idx is the index of the previous voter
     162             :    stake in the pool.  If this is the first voter inserted for this
     163             :    slot, prev_voter_idx should be ULONG_MAX.  Example usage:
     164             : 
     165             :    prev_voter_idx = ULONG_MAX;
     166             :    for( v : voters ) {
     167             :      voter_idx = fd_tower_stakes_insert( tower_stakes, slot, v.vote_account, v.stake, prev_voter_idx );
     168             :      prev_voter_idx = voter_idx;
     169             :    } */
     170             : 
     171             : ulong
     172             : fd_tower_stakes_insert( fd_tower_stakes_t * tower_stakes,
     173             :                         ulong               slot,
     174             :                         fd_hash_t const *   vote_account,
     175             :                         ulong               stake,
     176             :                         ulong               prev_voter_idx );
     177             : 
     178             : void
     179             : fd_tower_stakes_remove( fd_tower_stakes_t * tower_stakes,
     180             :                         ulong               slot );
     181             : 
     182             : #endif /* HEADER_fd_src_choreo_tower_fd_tower_stakes_h */