Line data Source code
1 : #include "fd_leaders.h"
2 : #include "../../ballet/chacha/fd_chacha_rng.h"
3 : #include "../../ballet/wsample/fd_wsample.h"
4 :
5 : #define SORT_NAME sort_vote_weights_by_stake_id
6 71960895 : #define SORT_KEY_T fd_vote_stake_weight_t
7 114719655 : #define SORT_BEFORE(a,b) ((a).stake > (b).stake ? 1 : ((a).stake < (b).stake ? 0 : memcmp( (a).id_key.uc, (b).id_key.uc, 32UL )>0))
8 : #include "../../util/tmpl/fd_sort.c"
9 :
10 : #define SORT_NAME sort_vote_weights_by_id
11 68508501 : #define SORT_KEY_T fd_vote_stake_weight_t
12 110332995 : #define SORT_BEFORE(a,b) (memcmp( (a).id_key.uc, (b).id_key.uc, 32UL )>0)
13 : #include "../../util/tmpl/fd_sort.c"
14 :
15 : #define SORT_NAME sort_weights_by_stake_id
16 46274751 : #define SORT_KEY_T fd_stake_weight_t
17 74540490 : #define SORT_BEFORE(a,b) ((a).stake > (b).stake ? 1 : ((a).stake < (b).stake ? 0 : memcmp( (a).key.uc, (b).key.uc, 32UL )>0))
18 : #include "../../util/tmpl/fd_sort.c"
19 :
20 : #define SORT_NAME sort_weights_by_id
21 43028889 : #define SORT_KEY_T fd_stake_weight_t
22 70222491 : #define SORT_BEFORE(a,b) (memcmp( (a).key.uc, (b).key.uc, 32UL )>0)
23 : #include "../../util/tmpl/fd_sort.c"
24 :
25 : ulong
26 : compute_id_weights_from_vote_weights( fd_stake_weight_t * stake_weight,
27 : fd_vote_stake_weight_t const * vote_stake_weight,
28 234 : ulong staked_cnt ) {
29 :
30 : /* Copy from input message [(vote, id, stake)] into old format [(id, stake)]. */
31 234 : ulong idx = 0UL;
32 2713563 : for( ulong i=0UL; i<staked_cnt; i++ ) {
33 2713329 : memcpy( stake_weight[ idx ].key.uc, vote_stake_weight[ i ].id_key.uc, sizeof(fd_pubkey_t) );
34 2713329 : stake_weight[ idx ].stake = vote_stake_weight[ i ].stake;
35 2713329 : idx++;
36 2713329 : }
37 :
38 : /* Sort [(id, stake)] by id, so we can dedup */
39 234 : sort_weights_by_id_inplace( stake_weight, idx );
40 :
41 : /* Dedup entries, aggregating stake */
42 234 : ulong j=0UL;
43 2713329 : for( ulong i=1UL; i<idx; i++ ) {
44 2713095 : fd_pubkey_t * pre = &stake_weight[ j ].key;
45 2713095 : fd_pubkey_t * cur = &stake_weight[ i ].key;
46 2713095 : if( 0==memcmp( pre, cur, sizeof(fd_pubkey_t) ) ) {
47 60 : stake_weight[ j ].stake += stake_weight[ i ].stake;
48 2713035 : } else {
49 2713035 : ++j;
50 2713035 : stake_weight[ j ].stake = stake_weight[ i ].stake;
51 2713035 : memcpy( stake_weight[ j ].key.uc, stake_weight[ i ].key.uc, sizeof(fd_pubkey_t) );
52 2713035 : }
53 2713095 : }
54 234 : ulong staked_cnt_by_id = fd_ulong_min( idx, j+1 );
55 :
56 : /* Sort [(id, stake)] by stake then id, as expected */
57 234 : sort_weights_by_stake_id_inplace( stake_weight, staked_cnt_by_id );
58 :
59 234 : return staked_cnt_by_id;
60 234 : }
61 :
62 : ulong
63 0 : fd_epoch_leaders_align( void ) {
64 0 : return FD_EPOCH_LEADERS_ALIGN;
65 0 : }
66 :
67 : FD_FN_CONST ulong
68 : fd_epoch_leaders_footprint( ulong pub_cnt,
69 13437 : ulong slot_cnt ) {
70 13437 : if( FD_UNLIKELY( ( pub_cnt == 0UL )
71 13437 : | ( pub_cnt >UINT_MAX-3UL )
72 13437 : | ( slot_cnt== 0UL ) ) )
73 0 : return 0UL;
74 13437 : return FD_EPOCH_LEADERS_FOOTPRINT( pub_cnt, slot_cnt );
75 13437 : }
76 :
77 : void *
78 : fd_epoch_leaders_new( void * shmem,
79 : ulong epoch,
80 : ulong slot0,
81 : ulong slot_cnt,
82 : ulong pub_cnt,
83 : fd_vote_stake_weight_t * stakes,
84 : ulong excluded_stake,
85 6711 : ulong vote_keyed_lsched ) {
86 6711 : if( FD_UNLIKELY( !shmem ) ) {
87 0 : FD_LOG_WARNING(( "NULL shmem" ));
88 0 : return NULL;
89 0 : }
90 :
91 6711 : ulong laddr = (ulong)shmem;
92 6711 : if( FD_UNLIKELY( !fd_ulong_is_aligned( laddr, FD_EPOCH_LEADERS_ALIGN ) ) ) {
93 0 : FD_LOG_WARNING(( "misaligned shmem" ));
94 0 : return NULL;
95 0 : }
96 :
97 6711 : if( FD_UNLIKELY( !pub_cnt ) ) {
98 0 : FD_LOG_WARNING(( "pub_cnt is 0" ));
99 0 : return NULL;
100 0 : }
101 :
102 : /* This code can be be removed when enable_vote_address_leader_schedule is
103 : enabled and cleared.
104 : And, as a consequence, stakes can be made const. */
105 6711 : if( FD_LIKELY( vote_keyed_lsched==0 ) ) {
106 : /* Sort [(vote, id, stake)] by id, so we can dedup */
107 6699 : sort_vote_weights_by_id_inplace( stakes, pub_cnt );
108 :
109 : /* Dedup entries, aggregating stake */
110 6699 : ulong j=0UL;
111 4568559 : for( ulong i=1UL; i<pub_cnt; i++ ) {
112 4561860 : fd_pubkey_t * pre = &stakes[ j ].id_key;
113 4561860 : fd_pubkey_t * cur = &stakes[ i ].id_key;
114 4561860 : if( 0==memcmp( pre, cur, sizeof(fd_pubkey_t) ) ) {
115 60 : stakes[ j ].stake += stakes[ i ].stake;
116 4561800 : } else {
117 4561800 : ++j;
118 4561800 : stakes[ j ].stake = stakes[ i ].stake;
119 4561800 : memcpy( stakes[ j ].id_key.uc, stakes[ i ].id_key.uc, sizeof(fd_pubkey_t) );
120 : /* vote doesn't matter */
121 4561800 : }
122 4561860 : }
123 6699 : pub_cnt = fd_ulong_min( pub_cnt, j+1 );
124 :
125 : /* Sort [(vote, id, stake)] by stake then id, as expected */
126 6699 : sort_vote_weights_by_stake_id_inplace( stakes, pub_cnt );
127 6699 : }
128 :
129 : /* The eventual layout that we want is:
130 : struct (align=8, footprint=48)
131 : list of indices (align=4, footprint=4*ceil(slot_cnt/4))
132 : (up to 60 bytes of padding to align to 64)
133 : list of pubkeys (align=32, footprint=32*pub_cnt)
134 : the indeterminate pubkey (align=32, footprint=32)
135 : leader membership bitset (align=8, footprint=8*ceil((pub_cnt+1)/64))
136 : (possibly 32 bytes of padding to align to 64)
137 :
138 : but in order to generate the list of indices, we want to use
139 : wsample, which needs some memory to work. Turns out that we
140 : probably have all the memory we need right here in shmem, we just
141 : need to be careful about how we use it; for most of the values of
142 : pub_cnt we care about, wsample's footprint is less than 32*pub_cnt.
143 :
144 : This works out because we can delay copying the pubkeys until we're
145 : done with the wsample object. There's a lot of type punning going
146 : on here, so watch out. */
147 6711 : ulong sched_cnt = (slot_cnt+FD_EPOCH_SLOTS_PER_ROTATION-1UL)/FD_EPOCH_SLOTS_PER_ROTATION;
148 :
149 6711 : ulong leader_bits_word_cnt = FD_EPOCH_LEADERS_BITSET_WORD_CNT( pub_cnt );
150 :
151 6711 : fd_epoch_leaders_t * leaders = (fd_epoch_leaders_t *)fd_type_pun( (void *)laddr );
152 6711 : laddr += sizeof(fd_epoch_leaders_t);
153 :
154 6711 : laddr = fd_ulong_align_up( laddr, alignof(uint) );
155 6711 : uint * sched = (uint *)fd_type_pun( (void *)laddr );
156 6711 : laddr += sizeof(uint)*sched_cnt;
157 :
158 6711 : laddr = fd_ulong_align_up( laddr, fd_ulong_max( sizeof(fd_pubkey_t), FD_WSAMPLE_ALIGN ) );
159 : /* These two alias, like a union. We don't need pubkeys until we're
160 : done with wsample. */
161 6711 : void * wsample_mem = (void *)fd_type_pun( (void *)laddr );
162 6711 : fd_pubkey_t * pubkeys = (fd_pubkey_t *)fd_type_pun( (void *)laddr );
163 :
164 6711 : FD_TEST( laddr+fd_wsample_footprint( pub_cnt, 0 )<=(ulong)wsample_mem + fd_epoch_leaders_footprint( pub_cnt, slot_cnt ) );
165 :
166 : /* Create and seed ChaCha20Rng */
167 6711 : fd_chacha_rng_t _rng[1];
168 6711 : fd_chacha_rng_t * rng = fd_chacha_rng_join( fd_chacha_rng_new( _rng, FD_CHACHA_RNG_MODE_MOD ) );
169 6711 : uchar key[ 32 ] = {0};
170 6711 : memcpy( key, &epoch, sizeof(ulong) );
171 6711 : fd_chacha_rng_init( rng, key, FD_CHACHA_RNG_ALGO_CHACHA20 );
172 :
173 6711 : void * _wsample = fd_wsample_new_init( wsample_mem, rng, pub_cnt, 0, FD_WSAMPLE_HINT_POWERLAW_NOREMOVE );
174 4575234 : for( ulong i=0UL; i<pub_cnt; i++ ) _wsample = fd_wsample_new_add( _wsample, stakes[i].stake );
175 6711 : fd_wsample_t * wsample = fd_wsample_join( fd_wsample_new_fini( _wsample, excluded_stake ) );
176 6711 : FD_TEST( wsample );
177 :
178 : /* Generate samples. We need uints, so we can't use sample_many. Map
179 : any FD_WSAMPLE_INDETERMINATE values to pub_cnt. */
180 7396803 : for( ulong i=0UL; i<sched_cnt; i++ ) sched[ i ] = (uint)fd_ulong_min( fd_wsample_sample( wsample ), pub_cnt );
181 :
182 : /* Clean up the wsample object */
183 6711 : fd_wsample_delete( fd_wsample_leave( wsample ) );
184 6711 : fd_chacha_rng_delete( fd_chacha_rng_leave( rng ) );
185 :
186 : /* Now we can use the space for the pubkeys */
187 4575234 : for( ulong i=0UL; i<pub_cnt; i++ ) memcpy( pubkeys+i, &stakes[ i ].id_key, 32UL );
188 :
189 : /* copy indeterminate leader to the last spot */
190 6711 : static const uchar fd_indeterminate_leader[32] = { FD_INDETERMINATE_LEADER };
191 6711 : memcpy( pubkeys+pub_cnt, fd_indeterminate_leader, 32UL );
192 :
193 6711 : ulong leader_bits_laddr = fd_ulong_align_up( (ulong)(pubkeys+pub_cnt+1UL), alignof(ulong) );
194 6711 : ulong * leader_bits = (ulong *)fd_type_pun( (void *)leader_bits_laddr );
195 :
196 6711 : FD_TEST( leader_bits_laddr + leader_bits_word_cnt*sizeof(ulong) <= (ulong)shmem + fd_epoch_leaders_footprint( pub_cnt, slot_cnt ) );
197 81753 : for( ulong i=0UL; i<leader_bits_word_cnt; i++ ) leader_bits[i] = 0UL;
198 7396803 : for( ulong i=0UL; i<sched_cnt; i++ ) leader_bits[ sched[i]>>6 ] |= (1UL<<(sched[i]&63UL));
199 :
200 : /* Construct the final struct */
201 6711 : leaders->epoch = epoch;
202 6711 : leaders->slot0 = slot0;
203 6711 : leaders->slot_cnt = slot_cnt;
204 6711 : leaders->pub = pubkeys;
205 6711 : leaders->pub_cnt = pub_cnt;
206 6711 : leaders->sched = sched;
207 6711 : leaders->sched_cnt = sched_cnt;
208 6711 : leaders->leader_bits = leader_bits;
209 6711 : leaders->leader_bits_word_cnt = leader_bits_word_cnt;
210 :
211 6711 : return (void *)shmem;
212 6711 : }
213 :
214 : fd_epoch_leaders_t *
215 6711 : fd_epoch_leaders_join( void * shleaders ) {
216 6711 : return (fd_epoch_leaders_t *)shleaders;
217 6711 : }
218 :
219 : void *
220 6366 : fd_epoch_leaders_leave( fd_epoch_leaders_t * leaders ) {
221 6366 : return (void *)leaders;
222 6366 : }
223 :
224 : void *
225 6366 : fd_epoch_leaders_delete( void * shleaders ) {
226 6366 : return shleaders;
227 6366 : }
|
