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             :    store node identities in a lookup table and only store an index
      28             :    into it for each rotation. */
      29             : 
      30             : #include "../fd_flamenco_base.h"
      31             : #include "fd_leaders_base.h"
      32             : #include "../stakes/fd_stake_weight.h"
      33             : #include "../../ballet/wsample/fd_wsample.h"
      34             : 
      35          51 : #define FD_ULONG_MAX(  a, b ) (__builtin_choose_expr( __builtin_constant_p( a ) & __builtin_constant_p( b ),        \
      36          51 :                                                       ((ulong )(a))>=((ulong )(b)) ? ((ulong )(a)) : ((ulong )(b)), \
      37          51 :                                                       fd_ulong_max( (a), (b) ) ))
      38             : 
      39             : /* FD_EPOCH_LEADERS_{ALIGN,FOOTPRINT} are compile-time-friendly versions
      40             :    of the fd_epoch_leaders_{align,footprint} functions. */
      41             : 
      42           0 : #define FD_EPOCH_LEADERS_ALIGN (64UL)
      43             : #define FD_EPOCH_LEADERS_FOOTPRINT( pub_cnt, slot_cnt )                                                     \
      44       14316 :   ( FD_LAYOUT_FINI( FD_LAYOUT_APPEND( FD_LAYOUT_APPEND( FD_LAYOUT_APPEND(                                   \
      45       14316 :     FD_LAYOUT_INIT,                                                                                         \
      46       14316 :       alignof(fd_epoch_leaders_t), sizeof(fd_epoch_leaders_t)                            ),                 \
      47       14316 :       alignof(uint),               (                                                                        \
      48       14316 :         (slot_cnt+FD_EPOCH_SLOTS_PER_ROTATION-1UL)/FD_EPOCH_SLOTS_PER_ROTATION*sizeof(uint)                 \
      49       14316 :         )                                                                                ),                 \
      50       14316 :       32UL,                        (                                                                        \
      51       14316 :         (slot_cnt+FD_EPOCH_SLOTS_PER_ROTATION-1UL)/FD_EPOCH_SLOTS_PER_ROTATION*32UL                         \
      52       14316 :         )                                                                                ),                 \
      53       14316 :       FD_EPOCH_LEADERS_ALIGN                                                             )  +               \
      54       14316 :       FD_ULONG_ALIGN_UP( FD_ULONG_MAX( 32UL*(pub_cnt),                                                      \
      55       14316 :                                        FD_WSAMPLE_FOOTPRINT( pub_cnt, 0 ) ), 64UL ) )
      56             : 
      57     4443495 : #define FD_EPOCH_SLOTS_PER_ROTATION (4UL)
      58             : 
      59             : /* fd_epoch_leaders_t contains the leader schedule of a Solana epoch. */
      60             : 
      61             : struct fd_epoch_leaders {
      62             :   /* This struct contains the schedule for epoch `epoch` which spans
      63             :      slots [slot0, slot0+slot_cnt). */
      64             :   ulong epoch;
      65             :   ulong slot0;
      66             :   ulong slot_cnt;
      67             : 
      68             :   /* pub is a lookup table of node public keys, one per vote-account
      69             :      stake entry, with length pub_cnt.  Node public keys may repeat. */
      70             :   fd_pubkey_t * pub;
      71             :   ulong         pub_cnt;
      72             : 
      73             :   /* sched contains the leader schedule in the form of indexes into
      74             :      the pub array.  For sched_cnt, refer to below. */
      75             :   uint *        sched;
      76             :   ulong         sched_cnt;
      77             : 
      78             :   /* vote_addr is the leader vote account address per rotation
      79             :      (sched_cnt entries).  Needed by SIMD-0232 fee collection: multiple
      80             :      vote accounts can share one node identity, so the vote address
      81             :      cannot be recovered from pub. */
      82             :   fd_pubkey_t * vote_addr;
      83             : };
      84             : typedef struct fd_epoch_leaders fd_epoch_leaders_t;
      85             : 
      86             : FD_PROTOTYPES_BEGIN
      87             : 
      88             : /* fd_epoch_leaders_{align,footprint} describe the required footprint
      89             :    and alignment of the leader schedule object.  pub_cnt is the number
      90             :    of vote-account stake entries.  slot_cnt is the number of slots in
      91             :    the epoch. */
      92             : 
      93             : FD_FN_CONST ulong
      94             : fd_epoch_leaders_align( void );
      95             : 
      96             : FD_FN_CONST ulong
      97             : fd_epoch_leaders_footprint( ulong pub_cnt,
      98             :                             ulong slot_cnt );
      99             : 
     100             : /* fd_epoch_leaders_new formats a memory region for use as a leader
     101             :    schedule object.  shmem points to the first byte of a memory region
     102             :    with matching alignment and footprint requirements.  The leader
     103             :    schedule object will contain the leader schedule for epoch `epoch`
     104             :    which spans slots [slot0, slot0+slot_cnt).  `slot0` must be the first
     105             :    slot in the epoch, but slot_cnt can be less than the length of the
     106             :    epoch to derive only the first portion of the leader schedule.
     107             :    slot_cnt must be at most MAX_SLOTS_PER_EPOCH (FD_LOG_ERR otherwise).
     108             :    pub_cnt is the number of entries in stakes.
     109             :    `stakes` points to the first entry of pub_cnt entries of stake
     110             :    weights sorted by tuple (stake, pubkey) in descending order.
     111             : 
     112             :    If geo_aware is 1, the schedule is reordered so that nearby
     113             :    leaders tend to follow each other as in SIMD-0675.  Every leader
     114             :    still gets the same number of rotations, the schedule just goes
     115             :    through an extra re-ordering step at the end.  Every entry in stakes
     116             :    needs a valid location, otherwise this will FD_LOG_ERR.
     117             : 
     118             :    Deriving only the first portion of the leader schedule is not
     119             :    supported with the geo-aware leader schedule (geo_aware non-zero).
     120             : 
     121             :    Does NOT retain a read interest in stakes upon return.
     122             :    The caller is not joined to the object on return. */
     123             : 
     124             : void *
     125             : fd_epoch_leaders_new( void  *                  shmem,
     126             :                       ulong                    epoch,
     127             :                       ulong                    slot0,
     128             :                       ulong                    slot_cnt,
     129             :                       ulong                    pub_cnt,
     130             :                       fd_vote_stake_weight_t * stakes, /* indexed [0, pub_cnt) */
     131             :                       int                      geo_aware );
     132             : 
     133             : /* fd_epoch_leaders_use_geo_aware returns 1 if the leader schedule for
     134             :    schedule_epoch should be geo-aware, and 0 otherwise. */
     135             : int
     136             : fd_epoch_leaders_use_geo_aware( fd_features_t const *       features,
     137             :                                 fd_epoch_schedule_t const * epoch_schedule,
     138             :                                 ulong                       schedule_epoch );
     139             : 
     140             : /* fd_epoch_leaders_join joins the caller to the leader schedule object.
     141             :    fd_epoch_leaders_leave undoes an existing join. */
     142             : 
     143             : fd_epoch_leaders_t *
     144             : fd_epoch_leaders_join( void * shleaders );
     145             : 
     146             : void *
     147             : fd_epoch_leaders_leave( fd_epoch_leaders_t * leaders );
     148             : 
     149             : /* fd_epoch_leaders_delete unformats a memory region and returns owner-
     150             :    ship back to the caller. */
     151             : 
     152             : void *
     153             : fd_epoch_leaders_delete( void * shleaders );
     154             : 
     155             : /* fd_epoch_leaders_get returns a pointer to the selected public key
     156             :    given a slot.  Returns NULL if slot is not in [slot0, slot0+slot_cnt)
     157             :    given the values supplied in fd_epoch_leaders_new. */
     158             : 
     159             : FD_FN_PURE static inline fd_pubkey_t const *
     160             : fd_epoch_leaders_get( fd_epoch_leaders_t const * leaders,
     161     3105699 :                       ulong                      slot ) {
     162     3105699 :   if( FD_UNLIKELY( leaders==NULL ) ) return NULL;
     163     3105699 :   ulong slot_delta = slot - leaders->slot0;
     164     3105699 :   if( FD_UNLIKELY( slot      < leaders->slot0    ) ) return NULL;
     165     3105471 :   if( FD_UNLIKELY( slot_delta>=leaders->slot_cnt ) ) return NULL;
     166     3104763 :   return (fd_pubkey_t const *)( leaders->pub + leaders->sched[ slot_delta/FD_EPOCH_SLOTS_PER_ROTATION ] );
     167     3105471 : }
     168             : 
     169             : /* fd_epoch_leaders_get_vote returns a pointer to the vote account
     170             :    address of the leader for the given slot.  Same lookup semantics as
     171             :    fd_epoch_leaders_get. */
     172             : 
     173             : FD_FN_PURE static inline fd_pubkey_t const *
     174             : fd_epoch_leaders_get_vote( fd_epoch_leaders_t const * leaders,
     175     1308231 :                            ulong                      slot ) {
     176     1308231 :   if( FD_UNLIKELY( leaders==NULL ) ) return NULL;
     177     1308231 :   ulong slot_delta = slot - leaders->slot0;
     178     1308231 :   if( FD_UNLIKELY( slot      < leaders->slot0    ) ) return NULL;
     179     1308231 :   if( FD_UNLIKELY( slot_delta>=leaders->slot_cnt ) ) return NULL;
     180     1308228 :   return (fd_pubkey_t const *)( leaders->vote_addr + slot_delta/FD_EPOCH_SLOTS_PER_ROTATION );
     181     1308231 : }
     182             : 
     183             : FD_PROTOTYPES_END
     184             : 
     185             : #endif /* HEADER_fd_src_flamenco_leaders_fd_leaders_h */