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_leaders_base.h"
31 : #include "../../ballet/wsample/fd_wsample.h"
32 :
33 45 : #define FD_ULONG_MAX( a, b ) (__builtin_choose_expr( __builtin_constant_p( a ) & __builtin_constant_p( b ), \
34 45 : ((ulong )(a))>=((ulong )(b)) ? ((ulong )(a)) : ((ulong )(b)), \
35 45 : fd_ulong_max( (a), (b) ) ))
36 :
37 : /* FD_EPOCH_LEADERS_{ALIGN,FOOTPRINT} are compile-time-friendly versions
38 : of the fd_epoch_leaders_{align,footprint} functions. */
39 :
40 0 : #define FD_EPOCH_LEADERS_ALIGN (64UL)
41 7092 : #define FD_EPOCH_LEADERS_BITSET_WORD_CNT( pub_cnt ) (((pub_cnt)+1UL+63UL)/64UL)
42 : #define FD_EPOCH_LEADERS_BITSET_FOOTPRINT( pub_cnt ) (FD_EPOCH_LEADERS_BITSET_WORD_CNT( pub_cnt )*sizeof(ulong))
43 : #define FD_EPOCH_LEADERS_FOOTPRINT( pub_cnt, slot_cnt ) \
44 15219 : ( FD_LAYOUT_FINI( FD_LAYOUT_APPEND( FD_LAYOUT_APPEND( \
45 15219 : FD_LAYOUT_INIT, \
46 15219 : alignof(fd_epoch_leaders_t), sizeof(fd_epoch_leaders_t) ), \
47 15219 : alignof(uint), ( \
48 15219 : (slot_cnt+FD_EPOCH_SLOTS_PER_ROTATION-1UL)/FD_EPOCH_SLOTS_PER_ROTATION*sizeof(uint) \
49 15219 : ) ), \
50 15219 : FD_EPOCH_LEADERS_ALIGN ) + \
51 15219 : FD_ULONG_ALIGN_UP( FD_ULONG_MAX( 32UL*((pub_cnt)+1UL) + FD_EPOCH_LEADERS_BITSET_FOOTPRINT( pub_cnt ), \
52 15219 : FD_WSAMPLE_FOOTPRINT( pub_cnt, 0 ) ), 64UL ) )
53 :
54 4328607 : #define FD_EPOCH_SLOTS_PER_ROTATION (4UL)
55 :
56 : /* fd_epoch_leaders_t contains the leader schedule of a Solana epoch. */
57 :
58 : struct fd_epoch_leaders {
59 : /* This struct contains the schedule for epoch `epoch` which spans
60 : slots [slot0, slot0+slot_cnt). */
61 : ulong epoch;
62 : ulong slot0;
63 : ulong slot_cnt;
64 :
65 : /* pub is a lookup table for node public keys with length pub_cnt */
66 : fd_pubkey_t * pub;
67 : ulong pub_cnt;
68 :
69 : /* sched contains the leader schedule in the form of indexes into
70 : the pub array. For sched_cnt, refer to below. */
71 : uint * sched;
72 : ulong sched_cnt;
73 :
74 : /* leader_bits stores whether pub[idx] appears at least once in sched.
75 : Includes one extra index for the indeterminate leader at idx==pub_cnt. */
76 : ulong * leader_bits;
77 : ulong leader_bits_word_cnt;
78 : };
79 : typedef struct fd_epoch_leaders fd_epoch_leaders_t;
80 :
81 : FD_PROTOTYPES_BEGIN
82 :
83 : /* fd_epoch_leaders_{align,footprint} describe the required footprint
84 : and alignment of the leader schedule object. pub_cnt is the number
85 : of unique public keys. slot_cnt is the number of slots in the
86 : epoch. */
87 :
88 : FD_FN_CONST ulong
89 : fd_epoch_leaders_align( void );
90 :
91 : FD_FN_CONST ulong
92 : fd_epoch_leaders_footprint( ulong pub_cnt,
93 : ulong slot_cnt );
94 :
95 : /* fd_epoch_leaders_new formats a memory region for use as a leader
96 : schedule object. shmem points to the first byte of a memory region
97 : with matching alignment and footprint requirements. The leader
98 : schedule object will contain the leader schedule for epoch `epoch`
99 : which spans slots [slot0, slot0+slot_cnt). `slot0` must be the first
100 : slot in the epoch, but slot_cnt can be less than the length of the
101 : epoch to derive only the first portion of the leader schedule.
102 : pub_cnt is the number of unique public keys in this schedule.
103 : `stakes` points to the first entry of pub_cnt entries of stake
104 : weights sorted by tuple (stake, pubkey) in descending order.
105 :
106 : If `stakes` does not include all staked nodes, e.g. in the case of an
107 : attack that swamps the network with fake validators, `stakes` should
108 : contain the first `pub_cnt` of them in the normal sort order, and the
109 : sum of the remaining stake must be provided in excluded_stake,
110 : measured in lamports.
111 :
112 : Does NOT retain a read interest in stakes upon return.
113 : The caller is not joined to the object on return. */
114 : void *
115 : fd_epoch_leaders_new( void * shmem,
116 : ulong epoch,
117 : ulong slot0,
118 : ulong slot_cnt,
119 : ulong pub_cnt,
120 : fd_vote_stake_weight_t * stakes, /* indexed [0, pub_cnt) */
121 : ulong excluded_stake );
122 :
123 : /* fd_epoch_leaders_join joins the caller to the leader schedule object.
124 : fd_epoch_leaders_leave undoes an existing join. */
125 :
126 : fd_epoch_leaders_t *
127 : fd_epoch_leaders_join( void * shleaders );
128 :
129 : void *
130 : fd_epoch_leaders_leave( fd_epoch_leaders_t * leaders );
131 :
132 : /* fd_epoch_leaders_delete unformats a memory region and returns owner-
133 : ship back to the caller. */
134 :
135 : void *
136 : fd_epoch_leaders_delete( void * shleaders );
137 :
138 : /* FD_INDETERMINATE_LEADER has base58 encoding
139 : 1111111111indeterminateLeader9QSxFYNqsXA. In hex, this pubkey ends
140 : with 0x0badf00d0badf00d. */
141 7095 : #define FD_INDETERMINATE_LEADER 0x00U,0x00U,0x00U,0x00U,0x00U,0x00U,0x00U,0x00U,0x00U,0x00U,0x99U,0xf6U,0x0fU,0x96U,0x2cU,0xddU,\
142 7095 : 0x38U,0x21U,0xf3U,0x0cU,0x16U,0x1dU,0xe3U,0x0aU,0x0bU,0xadU,0xf0U,0x0dU,0x0bU,0xadU,0xf0U,0x0dU
143 :
144 : /* fd_epoch_leaders_get returns a pointer to the selected public key
145 : given a slot. Returns NULL if slot is not in [slot0, slot0+slot_cnt)
146 : given the values supplied in fd_epoch_leaders_new.
147 :
148 : If a non-zero value was provided for excluded_stake in
149 : fd_epoch_leaders_new and a validator included in the excluded_stake
150 : is the leader for the requested slot, instead of returning the
151 : correct value (which is not known), fd_epoch_leaders_get will return
152 : a pointer to a pubkey with value FD_INDETERMINATE_LEADER. */
153 :
154 : FD_FN_PURE static inline fd_pubkey_t const *
155 : fd_epoch_leaders_get( fd_epoch_leaders_t const * leaders,
156 4315359 : ulong slot ) {
157 4315359 : if( FD_UNLIKELY( leaders==NULL ) ) return NULL;
158 4315359 : ulong slot_delta = slot - leaders->slot0;
159 4315359 : if( FD_UNLIKELY( slot < leaders->slot0 ) ) return NULL;
160 4315131 : if( FD_UNLIKELY( slot_delta>=leaders->slot_cnt ) ) return NULL;
161 4314423 : return (fd_pubkey_t const *)( leaders->pub + leaders->sched[ slot_delta/FD_EPOCH_SLOTS_PER_ROTATION ] );
162 4315131 : }
163 :
164 : FD_FN_PURE static inline int
165 : fd_epoch_leaders_is_leader_idx( fd_epoch_leaders_t const * leaders,
166 15189 : ulong idx ) {
167 15189 : if( FD_UNLIKELY( leaders==NULL ) ) return 0;
168 15189 : if( FD_UNLIKELY( idx>leaders->pub_cnt ) ) return 0;
169 15183 : ulong word_idx = idx>>6;
170 15183 : if( FD_UNLIKELY( word_idx>=leaders->leader_bits_word_cnt ) ) return 0;
171 15183 : return !!( leaders->leader_bits[ word_idx ] & (1UL<<(idx&63UL)) );
172 15183 : }
173 :
174 : FD_PROTOTYPES_END
175 :
176 : #endif /* HEADER_fd_src_flamenco_leaders_fd_leaders_h */
|
