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 16194453 : #define SORT_KEY_T fd_vote_stake_weight_t
7 24863526 : #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 15806010 : #define SORT_KEY_T fd_vote_stake_weight_t
12 24197511 : #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 : ulong
16 0 : fd_epoch_leaders_align( void ) {
17 0 : return FD_EPOCH_LEADERS_ALIGN;
18 0 : }
19 :
20 : FD_FN_CONST ulong
21 : fd_epoch_leaders_footprint( ulong pub_cnt,
22 6375 : ulong slot_cnt ) {
23 6375 : if( FD_UNLIKELY( ( pub_cnt == 0UL )
24 6375 : | ( pub_cnt >UINT_MAX-3UL )
25 6375 : | ( slot_cnt== 0UL ) ) )
26 0 : return 0UL;
27 6375 : return FD_EPOCH_LEADERS_FOOTPRINT( pub_cnt, slot_cnt );
28 6375 : }
29 :
30 : void *
31 : fd_epoch_leaders_new( void * shmem,
32 : ulong epoch,
33 : ulong slot0,
34 : ulong slot_cnt,
35 : ulong pub_cnt,
36 : fd_vote_stake_weight_t * stakes,
37 : ulong excluded_stake,
38 6360 : ulong vote_keyed_lsched ) {
39 6360 : (void)vote_keyed_lsched;
40 6360 : if( FD_UNLIKELY( !shmem ) ) {
41 0 : FD_LOG_WARNING(( "NULL shmem" ));
42 0 : return NULL;
43 0 : }
44 :
45 6360 : ulong laddr = (ulong)shmem;
46 6360 : if( FD_UNLIKELY( !fd_ulong_is_aligned( laddr, FD_EPOCH_LEADERS_ALIGN ) ) ) {
47 0 : FD_LOG_WARNING(( "misaligned shmem" ));
48 0 : return NULL;
49 0 : }
50 :
51 : /* This code can be be removed when enable_vote_address_leader_schedule is
52 : enabled and cleared.
53 : And, as a consequence, stakes can be made const. */
54 6360 : if( FD_LIKELY( vote_keyed_lsched==0 ) ) {
55 : /* Sort [(vote, id, stake)] by id, so we can dedup */
56 6354 : sort_vote_weights_by_id_inplace( stakes, pub_cnt );
57 :
58 : /* Dedup entries, aggregating stake */
59 6354 : ulong j=0UL;
60 1320054 : for( ulong i=1UL; i<pub_cnt; i++ ) {
61 1313700 : fd_pubkey_t * pre = &stakes[ j ].id_key;
62 1313700 : fd_pubkey_t * cur = &stakes[ i ].id_key;
63 1313700 : if( 0==memcmp( pre, cur, sizeof(fd_pubkey_t) ) ) {
64 30 : stakes[ j ].stake += stakes[ i ].stake;
65 1313670 : } else {
66 1313670 : ++j;
67 1313670 : stakes[ j ].stake = stakes[ i ].stake;
68 1313670 : memcpy( stakes[ j ].id_key.uc, stakes[ i ].id_key.uc, sizeof(fd_pubkey_t) );
69 : /* vote doesn't matter */
70 1313670 : }
71 1313700 : }
72 6354 : pub_cnt = fd_ulong_min( pub_cnt, j+1 );
73 :
74 : /* Sort [(vote, id, stake)] by stake then id, as expected */
75 6354 : sort_vote_weights_by_stake_id_inplace( stakes, pub_cnt );
76 6354 : }
77 :
78 : /* The eventual layout that we want is:
79 : struct (align=8, footprint=48)
80 : list of indices (align=4, footprint=4*ceil(slot_cnt/4))
81 : (up to 60 bytes of padding to align to 64)
82 : list of pubkeys (align=32, footprint=32*pub_cnt)
83 : the indeterminate pubkey (align=32, footprint=32)
84 : (possibly 32 bytes of padding to align to 64)
85 :
86 : but in order to generate the list of indices, we want to use
87 : wsample, which needs some memory to work. Turns out that we
88 : probably have all the memory we need right here in shmem, we just
89 : need to be careful about how we use it; for most of the values of
90 : pub_cnt we care about, wsample's footprint is less than 32*pub_cnt.
91 :
92 : This works out because we can delay copying the pubkeys until we're
93 : done with the wsample object. There's a lot of type punning going
94 : on here, so watch out. */
95 6360 : ulong sched_cnt = (slot_cnt+FD_EPOCH_SLOTS_PER_ROTATION-1UL)/FD_EPOCH_SLOTS_PER_ROTATION;
96 :
97 6360 : fd_epoch_leaders_t * leaders = (fd_epoch_leaders_t *)fd_type_pun( (void *)laddr );
98 6360 : laddr += sizeof(fd_epoch_leaders_t);
99 :
100 6360 : laddr = fd_ulong_align_up( laddr, alignof(uint) );
101 6360 : uint * sched = (uint *)fd_type_pun( (void *)laddr );
102 6360 : laddr += sizeof(uint)*sched_cnt;
103 :
104 6360 : laddr = fd_ulong_align_up( laddr, fd_ulong_max( sizeof(fd_pubkey_t), FD_WSAMPLE_ALIGN ) );
105 : /* These two alias, like a union. We don't need pubkeys until we're
106 : done with wsample. */
107 6360 : void * wsample_mem = (void *)fd_type_pun( (void *)laddr );
108 6360 : fd_pubkey_t * pubkeys = (fd_pubkey_t *)fd_type_pun( (void *)laddr );
109 :
110 6360 : FD_TEST( laddr+fd_wsample_footprint( pub_cnt, 0 )<=(ulong)wsample_mem + fd_epoch_leaders_footprint( pub_cnt, slot_cnt ) );
111 :
112 : /* Create and seed ChaCha20Rng */
113 6360 : fd_chacha_rng_t _rng[1];
114 6360 : fd_chacha_rng_t * rng = fd_chacha_rng_join( fd_chacha_rng_new( _rng, FD_CHACHA_RNG_MODE_MOD ) );
115 6360 : uchar key[ 32 ] = {0};
116 6360 : memcpy( key, &epoch, sizeof(ulong) );
117 6360 : fd_chacha20_rng_init( rng, key );
118 :
119 6360 : void * _wsample = fd_wsample_new_init( wsample_mem, rng, pub_cnt, 0, FD_WSAMPLE_HINT_POWERLAW_NOREMOVE );
120 1326396 : for( ulong i=0UL; i<pub_cnt; i++ ) _wsample = fd_wsample_new_add( _wsample, stakes[i].stake );
121 6360 : fd_wsample_t * wsample = fd_wsample_join( fd_wsample_new_fini( _wsample, excluded_stake ) );
122 :
123 : /* Generate samples. We need uints, so we can't use sample_many. Map
124 : any FD_WSAMPLE_INDETERMINATE values to pub_cnt. */
125 894498 : for( ulong i=0UL; i<sched_cnt; i++ ) sched[ i ] = (uint)fd_ulong_min( fd_wsample_sample( wsample ), pub_cnt );
126 :
127 : /* Clean up the wsample object */
128 6360 : fd_wsample_delete( fd_wsample_leave( wsample ) );
129 6360 : fd_chacha_rng_delete( fd_chacha_rng_leave( rng ) );
130 :
131 : /* Now we can use the space for the pubkeys */
132 1326396 : for( ulong i=0UL; i<pub_cnt; i++ ) memcpy( pubkeys+i, &stakes[ i ].id_key, 32UL );
133 :
134 : /* copy indeterminate leader to the last spot */
135 6360 : static const uchar fd_indeterminate_leader[32] = { FD_INDETERMINATE_LEADER };
136 6360 : memcpy( pubkeys+pub_cnt, fd_indeterminate_leader, 32UL );
137 :
138 : /* Construct the final struct */
139 6360 : leaders->epoch = epoch;
140 6360 : leaders->slot0 = slot0;
141 6360 : leaders->slot_cnt = slot_cnt;
142 6360 : leaders->pub = pubkeys;
143 6360 : leaders->pub_cnt = pub_cnt;
144 6360 : leaders->sched = sched;
145 6360 : leaders->sched_cnt = sched_cnt;
146 :
147 6360 : return (void *)shmem;
148 6360 : }
149 :
150 : fd_epoch_leaders_t *
151 6360 : fd_epoch_leaders_join( void * shleaders ) {
152 6360 : return (fd_epoch_leaders_t *)shleaders;
153 6360 : }
154 :
155 : void *
156 6219 : fd_epoch_leaders_leave( fd_epoch_leaders_t * leaders ) {
157 6219 : return (void *)leaders;
158 6219 : }
159 :
160 : void *
161 6219 : fd_epoch_leaders_delete( void * shleaders ) {
162 6219 : return shleaders;
163 6219 : }
|
