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          60 : #define MAP_KEY_EQ(k0,k1)       (!memcmp( k0, k1, sizeof(fd_tower_stakes_vtr_xid_t) ))
      60         144 : #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          54 : #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         207 : #define MAP_T              fd_tower_stakes_slot_t
      85        4215 : #define MAP_KEY            slot
      86        4047 : #define MAP_KEY_NULL       ULONG_MAX
      87         168 : #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         258 : fd_tower_stakes_align( void ) {
     103         258 :   return alignof(fd_tower_stakes_t);
     104         258 : }
     105             : 
     106             : FD_FN_CONST static inline ulong
     107             : fd_tower_stakes_footprint( ulong slot_max,
     108          54 :                            ulong vtr_max ) {
     109          54 :   ulong vtr_stake_chain_cnt = fd_tower_stakes_vtr_map_chain_cnt_est( vtr_max * slot_max );
     110          54 :   int lg_slot_cnt = fd_ulong_find_msb( fd_ulong_pow2_up( slot_max ) ) + 1;
     111          54 :   return FD_LAYOUT_FINI(
     112          54 :     FD_LAYOUT_APPEND(
     113          54 :     FD_LAYOUT_APPEND(
     114          54 :     FD_LAYOUT_APPEND(
     115          54 :     FD_LAYOUT_APPEND(
     116          54 :     FD_LAYOUT_APPEND(
     117          54 :     FD_LAYOUT_INIT,
     118          54 :       alignof(fd_tower_stakes_t),       sizeof(fd_tower_stakes_t)                                  ),
     119          54 :       fd_tower_stakes_vtr_map_align(),  fd_tower_stakes_vtr_map_footprint( vtr_stake_chain_cnt )   ),
     120          54 :       fd_tower_stakes_vtr_pool_align(), fd_tower_stakes_vtr_pool_footprint( vtr_max * slot_max )   ),
     121          54 :       fd_tower_stakes_slot_align(),     fd_tower_stakes_slot_footprint( lg_slot_cnt )              ),
     122          54 :       fd_used_acc_scratch_align(),      fd_used_acc_scratch_footprint( vtr_max * slot_max )        ),
     123          54 :     fd_tower_stakes_align() );
     124          54 : }
     125             : 
     126             : /* fd_tower_stakes_new formats an unused memory region for use as a
     127             :    tower_stakes.  mem is a non-NULL pointer to this region in the local
     128             :    address space with the required footprint and alignment. */
     129             : 
     130             : void *
     131             : fd_tower_stakes_new( void * shmem,
     132             :                      ulong  slot_max,
     133             :                      ulong  vtr_max,
     134             :                      ulong  seed );
     135             : 
     136             : /* fd_tower_stakes_join joins the caller to the tower_stakes. shstakes
     137             :    points to the first byte of the memory region backing the shstakes in
     138             :    the caller's address space.
     139             : 
     140             :    Returns a pointer in the local address space to stakes on success. */
     141             : 
     142             : fd_tower_stakes_t *
     143             : fd_tower_stakes_join( void * shstakes );
     144             : 
     145             : /* fd_tower_stakes_leave stakes a current local join.  Returns a pointer
     146             :    to the underlying shared memory region on success and NULL on failure
     147             :    (logs details).  Reasons for failure include stakes is NULL. */
     148             : 
     149             : void *
     150             : fd_tower_stakes_leave( fd_tower_stakes_t const * stakes );
     151             : 
     152             : /* fd_tower_stakes_delete unformats a memory region used as a stakes.
     153             :    Assumes only the local process is joined to the region.  Returns a
     154             :    pointer to the underlying shared memory region or NULL if used
     155             :    obviously in error (e.g. stakes is obviously not a stakes ...  logs
     156             :    details).  The ownership of the memory region is transferred to the
     157             :    caller. */
     158             : 
     159             : void *
     160             : fd_tower_stakes_delete( void * stakes );
     161             : 
     162             : /* fd_tower_stakes_insert adds a new (voter, stake) pair to the epoch
     163             :    stakes for a specific slot, and returns the index of the new voter
     164             :    stake in the pool.  prev_voter_idx is the index of the previous voter
     165             :    stake in the pool.  If this is the first voter inserted for this
     166             :    slot, prev_voter_idx should be ULONG_MAX.  Example usage:
     167             : 
     168             :    prev_voter_idx = ULONG_MAX;
     169             :    for( v : voters ) {
     170             :      voter_idx = fd_tower_stakes_insert( tower_stakes, slot, v.vote_account, v.stake, prev_voter_idx );
     171             :      prev_voter_idx = voter_idx;
     172             :    } */
     173             : 
     174             : ulong
     175             : fd_tower_stakes_insert( fd_tower_stakes_t * tower_stakes,
     176             :                         ulong               slot,
     177             :                         fd_hash_t const *   vote_account,
     178             :                         ulong               stake,
     179             :                         ulong               prev_voter_idx );
     180             : 
     181             : void
     182             : fd_tower_stakes_remove( fd_tower_stakes_t * tower_stakes,
     183             :                         ulong               slot );
     184             : 
     185             : #endif /* HEADER_fd_src_choreo_tower_fd_tower_stakes_h */