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 154776 : #define SORT_KEY_T fd_stake_weight_t
17 228954 : #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 144108 : #define SORT_KEY_T fd_stake_weight_t
22 210966 : #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 489 : ulong staked_cnt ) {
29 :
30 : /* Copy from input message [(vote, id, stake)] into old format [(id, stake)]. */
31 489 : ulong idx = 0UL;
32 19503 : for( ulong i=0UL; i<staked_cnt; i++ ) {
33 19014 : memcpy( stake_weight[ idx ].key.uc, vote_stake_weight[ i ].id_key.uc, sizeof(fd_pubkey_t) );
34 19014 : stake_weight[ idx ].stake = vote_stake_weight[ i ].stake;
35 19014 : idx++;
36 19014 : }
37 :
38 : /* Sort [(id, stake)] by id, so we can dedup */
39 489 : sort_weights_by_id_inplace( stake_weight, idx );
40 :
41 : /* Dedup entries, aggregating stake */
42 489 : ulong j=0UL;
43 19014 : for( ulong i=1UL; i<idx; i++ ) {
44 18525 : fd_pubkey_t * pre = &stake_weight[ j ].key;
45 18525 : fd_pubkey_t * cur = &stake_weight[ i ].key;
46 18525 : if( 0==memcmp( pre, cur, sizeof(fd_pubkey_t) ) ) {
47 60 : stake_weight[ j ].stake += stake_weight[ i ].stake;
48 18465 : } else {
49 18465 : ++j;
50 18465 : stake_weight[ j ].stake = stake_weight[ i ].stake;
51 18465 : memcpy( stake_weight[ j ].key.uc, stake_weight[ i ].key.uc, sizeof(fd_pubkey_t) );
52 18465 : }
53 18525 : }
54 489 : ulong staked_cnt_by_id = fd_ulong_min( idx, j+1 );
55 :
56 : /* Sort [(id, stake)] by stake then id, as expected */
57 489 : sort_weights_by_stake_id_inplace( stake_weight, staked_cnt_by_id );
58 :
59 489 : return staked_cnt_by_id;
60 489 : }
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 10833 : ulong slot_cnt ) {
70 10833 : if( FD_UNLIKELY( ( pub_cnt == 0UL )
71 10833 : | ( pub_cnt >UINT_MAX-3UL )
72 10833 : | ( slot_cnt== 0UL ) ) )
73 0 : return 0UL;
74 10833 : return FD_EPOCH_LEADERS_FOOTPRINT( pub_cnt, slot_cnt );
75 10833 : }
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 10824 : fd_vote_stake_weight_t * stakes ) {
84 10824 : if( FD_UNLIKELY( !shmem ) ) {
85 0 : FD_LOG_WARNING(( "NULL shmem" ));
86 0 : return NULL;
87 0 : }
88 :
89 10824 : ulong laddr = (ulong)shmem;
90 10824 : if( FD_UNLIKELY( !fd_ulong_is_aligned( laddr, FD_EPOCH_LEADERS_ALIGN ) ) ) {
91 0 : FD_LOG_WARNING(( "misaligned shmem" ));
92 0 : return NULL;
93 0 : }
94 :
95 10824 : if( FD_UNLIKELY( !pub_cnt ) ) {
96 0 : FD_LOG_WARNING(( "pub_cnt is 0" ));
97 0 : return NULL;
98 0 : }
99 :
100 : /* The eventual layout that we want is:
101 : struct (align=8, footprint=48)
102 : list of indices (align=4, footprint=4*ceil(slot_cnt/4))
103 : vote addr per rotation (align=32, footprint=32*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 : (possibly 32 bytes of padding to align to 64)
107 :
108 : but in order to generate the list of indices, we want to use
109 : wsample, which needs some memory to work. Turns out that we
110 : probably have all the memory we need right here in shmem, we just
111 : need to be careful about how we use it; for most of the values of
112 : pub_cnt we care about, wsample's footprint is less than 32*pub_cnt.
113 :
114 : This works out because we can delay copying the pubkeys until we're
115 : done with the wsample object. There's a lot of type punning going
116 : on here, so watch out. */
117 10824 : ulong sched_cnt = (slot_cnt+FD_EPOCH_SLOTS_PER_ROTATION-1UL)/FD_EPOCH_SLOTS_PER_ROTATION;
118 :
119 10824 : fd_epoch_leaders_t * leaders = (fd_epoch_leaders_t *)fd_type_pun( (void *)laddr );
120 10824 : laddr += sizeof(fd_epoch_leaders_t);
121 :
122 10824 : laddr = fd_ulong_align_up( laddr, alignof(uint) );
123 10824 : uint * sched = (uint *)fd_type_pun( (void *)laddr );
124 10824 : laddr += sizeof(uint)*sched_cnt;
125 :
126 10824 : laddr = fd_ulong_align_up( laddr, 32UL );
127 10824 : fd_pubkey_t * vote_addr = (fd_pubkey_t *)fd_type_pun( (void *)laddr );
128 10824 : laddr += 32UL*sched_cnt;
129 :
130 10824 : 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 10824 : void * wsample_mem = (void *)fd_type_pun( (void *)laddr );
134 10824 : fd_pubkey_t * pubkeys = (fd_pubkey_t *)fd_type_pun( (void *)laddr );
135 :
136 10824 : 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 10824 : fd_chacha_rng_t _rng[1];
140 10824 : fd_chacha_rng_t * rng = fd_chacha_rng_join( fd_chacha_rng_new( _rng, FD_CHACHA_RNG_MODE_MOD ) );
141 10824 : uchar key[ 32 ] = {0};
142 10824 : memcpy( key, &epoch, sizeof(ulong) );
143 10824 : fd_chacha_rng_init( rng, key, FD_CHACHA_RNG_ALGO_CHACHA20 );
144 :
145 10824 : void * _wsample = fd_wsample_new_init( wsample_mem, rng, pub_cnt, 0, FD_WSAMPLE_HINT_POWERLAW_NOREMOVE );
146 276081 : for( ulong i=0UL; i<pub_cnt; i++ ) _wsample = fd_wsample_new_add( _wsample, stakes[i].stake );
147 10824 : fd_wsample_t * wsample = fd_wsample_join( fd_wsample_new_fini( _wsample, 0UL ) );
148 10824 : FD_TEST( wsample );
149 :
150 : /* Generate samples. We need uints, so we can't use sample_many. */
151 3846360 : for( ulong i=0UL; i<sched_cnt; i++ ) sched[ i ] = (uint)fd_wsample_sample( wsample );
152 :
153 : /* Clean up the wsample object */
154 10824 : fd_wsample_delete( fd_wsample_leave( wsample ) );
155 10824 : fd_chacha_rng_delete( fd_chacha_rng_leave( rng ) );
156 :
157 : /* Now we can use the space for the pubkeys */
158 276081 : for( ulong i=0UL; i<pub_cnt; i++ ) memcpy( pubkeys+i, &stakes[ i ].id_key, 32UL );
159 :
160 : /* record the leader vote address per rotation */
161 3846360 : for( ulong i=0UL; i<sched_cnt; i++ ) memcpy( vote_addr+i, &stakes[ sched[ i ] ].vote_key, 32UL );
162 :
163 : /* Construct the final struct */
164 10824 : leaders->epoch = epoch;
165 10824 : leaders->slot0 = slot0;
166 10824 : leaders->slot_cnt = slot_cnt;
167 10824 : leaders->pub = pubkeys;
168 10824 : leaders->pub_cnt = pub_cnt;
169 10824 : leaders->sched = sched;
170 10824 : leaders->sched_cnt = sched_cnt;
171 10824 : leaders->vote_addr = vote_addr;
172 :
173 10824 : return (void *)shmem;
174 10824 : }
175 :
176 : fd_epoch_leaders_t *
177 10824 : fd_epoch_leaders_join( void * shleaders ) {
178 10824 : return (fd_epoch_leaders_t *)shleaders;
179 10824 : }
180 :
181 : void *
182 6318 : fd_epoch_leaders_leave( fd_epoch_leaders_t * leaders ) {
183 6318 : return (void *)leaders;
184 6318 : }
185 :
186 : void *
187 6318 : fd_epoch_leaders_delete( void * shleaders ) {
188 6318 : return shleaders;
189 6318 : }
|
