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 : #define SORT_KEY_T fd_vote_stake_weight_t
7 : #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 : #define SORT_KEY_T fd_vote_stake_weight_t
12 : #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 46274658 : #define SORT_KEY_T fd_stake_weight_t
17 74540427 : #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 43028745 : #define SORT_KEY_T fd_stake_weight_t
22 70222377 : #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 471 : ulong staked_cnt ) {
29 :
30 : /* Copy from input message [(vote, id, stake)] into old format [(id, stake)]. */
31 471 : ulong idx = 0UL;
32 2714007 : for( ulong i=0UL; i<staked_cnt; i++ ) {
33 2713536 : memcpy( stake_weight[ idx ].key.uc, vote_stake_weight[ i ].id_key.uc, sizeof(fd_pubkey_t) );
34 2713536 : stake_weight[ idx ].stake = vote_stake_weight[ i ].stake;
35 2713536 : idx++;
36 2713536 : }
37 :
38 : /* Sort [(id, stake)] by id, so we can dedup */
39 471 : sort_weights_by_id_inplace( stake_weight, idx );
40 :
41 : /* Dedup entries, aggregating stake */
42 471 : ulong j=0UL;
43 2713536 : for( ulong i=1UL; i<idx; i++ ) {
44 2713065 : fd_pubkey_t * pre = &stake_weight[ j ].key;
45 2713065 : fd_pubkey_t * cur = &stake_weight[ i ].key;
46 2713065 : if( 0==memcmp( pre, cur, sizeof(fd_pubkey_t) ) ) {
47 60 : stake_weight[ j ].stake += stake_weight[ i ].stake;
48 2713005 : } else {
49 2713005 : ++j;
50 2713005 : stake_weight[ j ].stake = stake_weight[ i ].stake;
51 2713005 : memcpy( stake_weight[ j ].key.uc, stake_weight[ i ].key.uc, sizeof(fd_pubkey_t) );
52 2713005 : }
53 2713065 : }
54 471 : ulong staked_cnt_by_id = fd_ulong_min( idx, j+1 );
55 :
56 : /* Sort [(id, stake)] by stake then id, as expected */
57 471 : sort_weights_by_stake_id_inplace( stake_weight, staked_cnt_by_id );
58 :
59 471 : return staked_cnt_by_id;
60 471 : }
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 14199 : ulong slot_cnt ) {
70 14199 : if( FD_UNLIKELY( ( pub_cnt == 0UL )
71 14199 : | ( pub_cnt >UINT_MAX-3UL )
72 14199 : | ( slot_cnt== 0UL ) ) )
73 0 : return 0UL;
74 14199 : return FD_EPOCH_LEADERS_FOOTPRINT( pub_cnt, slot_cnt );
75 14199 : }
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 7092 : ulong excluded_stake ) {
85 7092 : if( FD_UNLIKELY( !shmem ) ) {
86 0 : FD_LOG_WARNING(( "NULL shmem" ));
87 0 : return NULL;
88 0 : }
89 :
90 7092 : ulong laddr = (ulong)shmem;
91 7092 : if( FD_UNLIKELY( !fd_ulong_is_aligned( laddr, FD_EPOCH_LEADERS_ALIGN ) ) ) {
92 0 : FD_LOG_WARNING(( "misaligned shmem" ));
93 0 : return NULL;
94 0 : }
95 :
96 7092 : if( FD_UNLIKELY( !pub_cnt ) ) {
97 0 : FD_LOG_WARNING(( "pub_cnt is 0" ));
98 0 : return NULL;
99 0 : }
100 :
101 : /* The eventual layout that we want is:
102 : struct (align=8, footprint=48)
103 : list of indices (align=4, footprint=4*ceil(slot_cnt/4))
104 : (up to 60 bytes of padding to align to 64)
105 : list of pubkeys (align=32, footprint=32*pub_cnt)
106 : the indeterminate pubkey (align=32, footprint=32)
107 : leader membership bitset (align=8, footprint=8*ceil((pub_cnt+1)/64))
108 : (possibly 32 bytes of padding to align to 64)
109 :
110 : but in order to generate the list of indices, we want to use
111 : wsample, which needs some memory to work. Turns out that we
112 : probably have all the memory we need right here in shmem, we just
113 : need to be careful about how we use it; for most of the values of
114 : pub_cnt we care about, wsample's footprint is less than 32*pub_cnt.
115 :
116 : This works out because we can delay copying the pubkeys until we're
117 : done with the wsample object. There's a lot of type punning going
118 : on here, so watch out. */
119 7092 : ulong sched_cnt = (slot_cnt+FD_EPOCH_SLOTS_PER_ROTATION-1UL)/FD_EPOCH_SLOTS_PER_ROTATION;
120 :
121 7092 : ulong leader_bits_word_cnt = FD_EPOCH_LEADERS_BITSET_WORD_CNT( pub_cnt );
122 :
123 7092 : fd_epoch_leaders_t * leaders = (fd_epoch_leaders_t *)fd_type_pun( (void *)laddr );
124 7092 : laddr += sizeof(fd_epoch_leaders_t);
125 :
126 7092 : laddr = fd_ulong_align_up( laddr, alignof(uint) );
127 7092 : uint * sched = (uint *)fd_type_pun( (void *)laddr );
128 7092 : laddr += sizeof(uint)*sched_cnt;
129 :
130 7092 : laddr = fd_ulong_align_up( laddr, fd_ulong_max( sizeof(fd_pubkey_t), FD_WSAMPLE_ALIGN ) );
131 : /* These two alias, like a union. We don't need pubkeys until we're
132 : done with wsample. */
133 7092 : void * wsample_mem = (void *)fd_type_pun( (void *)laddr );
134 7092 : fd_pubkey_t * pubkeys = (fd_pubkey_t *)fd_type_pun( (void *)laddr );
135 :
136 7092 : FD_TEST( laddr+fd_wsample_footprint( pub_cnt, 0 )<=(ulong)wsample_mem + fd_epoch_leaders_footprint( pub_cnt, slot_cnt ) );
137 :
138 : /* Create and seed ChaCha20Rng */
139 7092 : fd_chacha_rng_t _rng[1];
140 7092 : fd_chacha_rng_t * rng = fd_chacha_rng_join( fd_chacha_rng_new( _rng, FD_CHACHA_RNG_MODE_MOD ) );
141 7092 : uchar key[ 32 ] = {0};
142 7092 : memcpy( key, &epoch, sizeof(ulong) );
143 7092 : fd_chacha_rng_init( rng, key, FD_CHACHA_RNG_ALGO_CHACHA20 );
144 :
145 7092 : void * _wsample = fd_wsample_new_init( wsample_mem, rng, pub_cnt, 0, FD_WSAMPLE_HINT_POWERLAW_NOREMOVE );
146 4575681 : for( ulong i=0UL; i<pub_cnt; i++ ) _wsample = fd_wsample_new_add( _wsample, stakes[i].stake );
147 7092 : fd_wsample_t * wsample = fd_wsample_join( fd_wsample_new_fini( _wsample, excluded_stake ) );
148 7092 : FD_TEST( wsample );
149 :
150 : /* Generate samples. We need uints, so we can't use sample_many. Map
151 : any FD_WSAMPLE_INDETERMINATE values to pub_cnt. */
152 4158126 : for( ulong i=0UL; i<sched_cnt; i++ ) sched[ i ] = (uint)fd_ulong_min( fd_wsample_sample( wsample ), pub_cnt );
153 :
154 : /* Clean up the wsample object */
155 7092 : fd_wsample_delete( fd_wsample_leave( wsample ) );
156 7092 : fd_chacha_rng_delete( fd_chacha_rng_leave( rng ) );
157 :
158 : /* Now we can use the space for the pubkeys */
159 4575681 : for( ulong i=0UL; i<pub_cnt; i++ ) memcpy( pubkeys+i, &stakes[ i ].id_key, 32UL );
160 :
161 : /* copy indeterminate leader to the last spot */
162 7092 : static const uchar fd_indeterminate_leader[32] = { FD_INDETERMINATE_LEADER };
163 7092 : memcpy( pubkeys+pub_cnt, fd_indeterminate_leader, 32UL );
164 :
165 7092 : ulong leader_bits_laddr = fd_ulong_align_up( (ulong)(pubkeys+pub_cnt+1UL), alignof(ulong) );
166 7092 : ulong * leader_bits = (ulong *)fd_type_pun( (void *)leader_bits_laddr );
167 :
168 7092 : FD_TEST( leader_bits_laddr + leader_bits_word_cnt*sizeof(ulong) <= (ulong)shmem + fd_epoch_leaders_footprint( pub_cnt, slot_cnt ) );
169 82515 : for( ulong i=0UL; i<leader_bits_word_cnt; i++ ) leader_bits[i] = 0UL;
170 4158126 : for( ulong i=0UL; i<sched_cnt; i++ ) leader_bits[ sched[i]>>6 ] |= (1UL<<(sched[i]&63UL));
171 :
172 : /* Construct the final struct */
173 7092 : leaders->epoch = epoch;
174 7092 : leaders->slot0 = slot0;
175 7092 : leaders->slot_cnt = slot_cnt;
176 7092 : leaders->pub = pubkeys;
177 7092 : leaders->pub_cnt = pub_cnt;
178 7092 : leaders->sched = sched;
179 7092 : leaders->sched_cnt = sched_cnt;
180 7092 : leaders->leader_bits = leader_bits;
181 7092 : leaders->leader_bits_word_cnt = leader_bits_word_cnt;
182 :
183 7092 : return (void *)shmem;
184 7092 : }
185 :
186 : fd_epoch_leaders_t *
187 7092 : fd_epoch_leaders_join( void * shleaders ) {
188 7092 : return (fd_epoch_leaders_t *)shleaders;
189 7092 : }
190 :
191 : void *
192 6336 : fd_epoch_leaders_leave( fd_epoch_leaders_t * leaders ) {
193 6336 : return (void *)leaders;
194 6336 : }
195 :
196 : void *
197 6336 : fd_epoch_leaders_delete( void * shleaders ) {
198 6336 : return shleaders;
199 6336 : }
|
