Line data    Source code

       1             : #ifndef HEADER_fd_src_flamenco_leaders_fd_leaders_h
       2             : #define HEADER_fd_src_flamenco_leaders_fd_leaders_h
       3             : 
       4             : /* fd_leaders provides APIs for the Solana leader schedule.
       5             :    Logic is compatible with Solana mainnet as of 2023-Jul.
       6             : 
       7             :    Every slot is assigned a leader (identified by a "node identity"
       8             :    public key).  The sequence of leaders for all slots in an epoch is
       9             :    called the "leader schedule".  The main responsibility of the leader
      10             :    is to produce a block for the slot.
      11             : 
      12             :    The leader schedule is divided into sched_cnt rotations.  Each
      13             :    rotation spans one or more slots, such that
      14             : 
      15             :      slots_per_epoch = sched_cnt * slots_per_rotation
      16             : 
      17             :    The leader can only change between rotations.  An example leader
      18             :    schedule looks as follows (where A, B, C are node identities and each
      19             :    column is a slot, with 4 slots per rotation)
      20             : 
      21             :      A  A  A  A  B  B  B  B  B  B  B  B  C  C  C  C  A  A  A  A
      22             :      ^           ^           ^           ^           ^
      23             :      rotation    rotation    rotation    rotation    rotation
      24             : 
      25             :    The mainnet epoch duration is quite long (currently 432000 slots, for
      26             :    more information see fd_sysvar_epoch_schedule.h).  To save space, we
      27             :    dedup pubkeys into a lookup table and only store an index for each
      28             :    rotation. */
      29             : 
      30             : #include "../fd_flamenco_base.h"
      31             : #include "../stakes/fd_stake_weight.h"
      32             : #include "../../ballet/wsample/fd_wsample.h"
      33             : 
      34          24 : #define FD_ULONG_MAX(  a, b ) (__builtin_choose_expr( __builtin_constant_p( a ) & __builtin_constant_p( b ),        \
      35          24 :                                                       ((ulong )(a))>=((ulong )(b)) ? ((ulong )(a)) : ((ulong )(b)), \
      36          24 :                                                       fd_ulong_max( (a), (b) ) ))
      37             : 
      38             : /* FD_EPOCH_LEADERS_{ALIGN,FOOTPRINT} are compile-time-friendly versions
      39             :    of the fd_epoch_leaders_{align,footprint} functions. */
      40             : 
      41           0 : #define FD_EPOCH_LEADERS_ALIGN (64UL)
      42             : #define FD_EPOCH_LEADERS_FOOTPRINT( pub_cnt, slot_cnt )                                                     \
      43       11220 :   ( FD_LAYOUT_FINI( FD_LAYOUT_APPEND( FD_LAYOUT_APPEND( FD_LAYOUT_APPEND(                                   \
      44       11220 :     FD_LAYOUT_INIT,                                                                                         \
      45       11220 :       alignof(fd_epoch_leaders_t), sizeof(fd_epoch_leaders_t)                            ),                 \
      46       11220 :       alignof(uint),               (                                                                        \
      47       11220 :         (slot_cnt+FD_EPOCH_SLOTS_PER_ROTATION-1UL)/FD_EPOCH_SLOTS_PER_ROTATION*sizeof(uint)                 \
      48       11220 :         )                                                                                ),                 \
      49       11220 :       32UL,                        (                                                                        \
      50       11220 :         (slot_cnt+FD_EPOCH_SLOTS_PER_ROTATION-1UL)/FD_EPOCH_SLOTS_PER_ROTATION*32UL                         \
      51       11220 :         )                                                                                ),                 \
      52       11220 :       FD_EPOCH_LEADERS_ALIGN                                                             )  +               \
      53       11220 :       FD_ULONG_ALIGN_UP( FD_ULONG_MAX( 32UL*(pub_cnt),                                                      \
      54       11220 :                                        FD_WSAMPLE_FOOTPRINT( pub_cnt, 0 ) ), 64UL ) )
      55             : 
      56     4303623 : #define FD_EPOCH_SLOTS_PER_ROTATION (4UL)
      57             : 
      58             : /* fd_epoch_leaders_t contains the leader schedule of a Solana epoch. */
      59             : 
      60             : struct fd_epoch_leaders {
      61             :   /* This struct contains the schedule for epoch `epoch` which spans
      62             :      slots [slot0, slot0+slot_cnt). */
      63             :   ulong epoch;
      64             :   ulong slot0;
      65             :   ulong slot_cnt;
      66             : 
      67             :   /* pub is a lookup table of node public keys, one per vote-account
      68             :      stake entry, with length pub_cnt.  Node public keys may repeat. */
      69             :   fd_pubkey_t * pub;
      70             :   ulong         pub_cnt;
      71             : 
      72             :   /* sched contains the leader schedule in the form of indexes into
      73             :      the pub array.  For sched_cnt, refer to below. */
      74             :   uint *        sched;
      75             :   ulong         sched_cnt;
      76             : 
      77             :   /* vote_addr is the leader vote account address per rotation
      78             :      (sched_cnt entries).  Needed by SIMD-0232 fee collection: multiple
      79             :      vote accounts can share one node identity, so the vote address
      80             :      cannot be recovered from pub. */
      81             :   fd_pubkey_t * vote_addr;
      82             : };
      83             : typedef struct fd_epoch_leaders fd_epoch_leaders_t;
      84             : 
      85             : FD_PROTOTYPES_BEGIN
      86             : 
      87             : /* fd_epoch_leaders_{align,footprint} describe the required footprint
      88             :    and alignment of the leader schedule object.  pub_cnt is the number
      89             :    of vote-account stake entries.  slot_cnt is the number of slots in
      90             :    the epoch. */
      91             : 
      92             : FD_FN_CONST ulong
      93             : fd_epoch_leaders_align( void );
      94             : 
      95             : FD_FN_CONST ulong
      96             : fd_epoch_leaders_footprint( ulong pub_cnt,
      97             :                             ulong slot_cnt );
      98             : 
      99             : /* fd_epoch_leaders_new formats a memory region for use as a leader
     100             :    schedule object.  shmem points to the first byte of a memory region
     101             :    with matching alignment and footprint requirements.  The leader
     102             :    schedule object will contain the leader schedule for epoch `epoch`
     103             :    which spans slots [slot0, slot0+slot_cnt).  `slot0` must be the first
     104             :    slot in the epoch, but slot_cnt can be less than the length of the
     105             :    epoch to derive only the first portion of the leader schedule.
     106             :    pub_cnt is the number of unique public keys in this schedule.
     107             :    `stakes` points to the first entry of pub_cnt entries of stake
     108             :    weights sorted by tuple (stake, pubkey) in descending order.
     109             : 
     110             :    Does NOT retain a read interest in stakes upon return.
     111             :    The caller is not joined to the object on return. */
     112             : void *
     113             : fd_epoch_leaders_new( void  *                  shmem,
     114             :                       ulong                    epoch,
     115             :                       ulong                    slot0,
     116             :                       ulong                    slot_cnt,
     117             :                       ulong                    pub_cnt,
     118             :                       fd_vote_stake_weight_t * stakes ); /* indexed [0, pub_cnt) */
     119             : 
     120             : /* fd_epoch_leaders_join joins the caller to the leader schedule object.
     121             :    fd_epoch_leaders_leave undoes an existing join. */
     122             : 
     123             : fd_epoch_leaders_t *
     124             : fd_epoch_leaders_join( void * shleaders );
     125             : 
     126             : void *
     127             : fd_epoch_leaders_leave( fd_epoch_leaders_t * leaders );
     128             : 
     129             : /* fd_epoch_leaders_delete unformats a memory region and returns owner-
     130             :    ship back to the caller. */
     131             : 
     132             : void *
     133             : fd_epoch_leaders_delete( void * shleaders );
     134             : 
     135             : /* fd_epoch_leaders_get returns a pointer to the selected public key
     136             :    given a slot.  Returns NULL if slot is not in [slot0, slot0+slot_cnt)
     137             :    given the values supplied in fd_epoch_leaders_new. */
     138             : 
     139             : FD_FN_PURE static inline fd_pubkey_t const *
     140             : fd_epoch_leaders_get( fd_epoch_leaders_t const * leaders,
     141     2977650 :                       ulong                      slot ) {
     142     2977650 :   if( FD_UNLIKELY( leaders==NULL ) ) return NULL;
     143     2977650 :   ulong slot_delta = slot - leaders->slot0;
     144     2977650 :   if( FD_UNLIKELY( slot      < leaders->slot0    ) ) return NULL;
     145     2977422 :   if( FD_UNLIKELY( slot_delta>=leaders->slot_cnt ) ) return NULL;
     146     2976714 :   return (fd_pubkey_t const *)( leaders->pub + leaders->sched[ slot_delta/FD_EPOCH_SLOTS_PER_ROTATION ] );
     147     2977422 : }
     148             : 
     149             : /* fd_epoch_leaders_get_vote returns a pointer to the vote account
     150             :    address of the leader for the given slot.  Same lookup semantics as
     151             :    fd_epoch_leaders_get. */
     152             : 
     153             : FD_FN_PURE static inline fd_pubkey_t const *
     154             : fd_epoch_leaders_get_vote( fd_epoch_leaders_t const * leaders,
     155     1302264 :                            ulong                      slot ) {
     156     1302264 :   if( FD_UNLIKELY( leaders==NULL ) ) return NULL;
     157     1302264 :   ulong slot_delta = slot - leaders->slot0;
     158     1302264 :   if( FD_UNLIKELY( slot      < leaders->slot0    ) ) return NULL;
     159     1302264 :   if( FD_UNLIKELY( slot_delta>=leaders->slot_cnt ) ) return NULL;
     160     1302261 :   return (fd_pubkey_t const *)( leaders->vote_addr + slot_delta/FD_EPOCH_SLOTS_PER_ROTATION );
     161     1302264 : }
     162             : 
     163             : FD_PROTOTYPES_END
     164             : 
     165             : #endif /* HEADER_fd_src_flamenco_leaders_fd_leaders_h */