Line data Source code
1 : #include "fd_leaders.h"
2 : #include "../../ballet/chacha20/fd_chacha20rng.h"
3 : #include "../../ballet/wsample/fd_wsample.h"
4 :
5 : #define SORT_NAME sort_vote_weights_by_stake_id
6 16194411 : #define SORT_KEY_T fd_vote_stake_weight_t
7 24863502 : #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 15805968 : #define SORT_KEY_T fd_vote_stake_weight_t
12 24197487 : #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 6351 : ulong slot_cnt ) {
23 6351 : if( FD_UNLIKELY( ( pub_cnt == 0UL )
24 6351 : | ( pub_cnt >UINT_MAX-3UL )
25 6351 : | ( slot_cnt== 0UL ) ) )
26 0 : return 0UL;
27 6351 : return FD_EPOCH_LEADERS_FOOTPRINT( pub_cnt, slot_cnt );
28 6351 : }
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 6336 : ulong vote_keyed_lsched ) {
39 6336 : (void)vote_keyed_lsched;
40 6336 : if( FD_UNLIKELY( !shmem ) ) {
41 0 : FD_LOG_WARNING(( "NULL shmem" ));
42 0 : return NULL;
43 0 : }
44 :
45 6336 : ulong laddr = (ulong)shmem;
46 6336 : 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 6336 : if( FD_LIKELY( vote_keyed_lsched==0 ) ) {
55 : /* Sort [(vote, id, stake)] by id, so we can dedup */
56 6330 : sort_vote_weights_by_id_inplace( stakes, pub_cnt );
57 :
58 : /* Dedup entries, aggregating stake */
59 6330 : ulong j=0UL;
60 1320012 : for( ulong i=1UL; i<pub_cnt; i++ ) {
61 1313682 : fd_pubkey_t * pre = &stakes[ j ].id_key;
62 1313682 : fd_pubkey_t * cur = &stakes[ i ].id_key;
63 1313682 : if( 0==memcmp( pre, cur, sizeof(fd_pubkey_t) ) ) {
64 30 : stakes[ j ].stake += stakes[ i ].stake;
65 1313652 : } else {
66 1313652 : ++j;
67 1313652 : stakes[ j ].stake = stakes[ i ].stake;
68 1313652 : memcpy( stakes[ j ].id_key.uc, stakes[ i ].id_key.uc, sizeof(fd_pubkey_t) );
69 : /* vote doesn't matter */
70 1313652 : }
71 1313682 : }
72 6330 : pub_cnt = fd_ulong_min( pub_cnt, j+1 );
73 :
74 : /* Sort [(vote, id, stake)] by stake then id, as expected */
75 6330 : sort_vote_weights_by_stake_id_inplace( stakes, pub_cnt );
76 6330 : }
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 6336 : ulong sched_cnt = (slot_cnt+FD_EPOCH_SLOTS_PER_ROTATION-1UL)/FD_EPOCH_SLOTS_PER_ROTATION;
96 :
97 6336 : fd_epoch_leaders_t * leaders = (fd_epoch_leaders_t *)fd_type_pun( (void *)laddr );
98 6336 : laddr += sizeof(fd_epoch_leaders_t);
99 :
100 6336 : laddr = fd_ulong_align_up( laddr, alignof(uint) );
101 6336 : uint * sched = (uint *)fd_type_pun( (void *)laddr );
102 6336 : laddr += sizeof(uint)*sched_cnt;
103 :
104 6336 : 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 6336 : void * wsample_mem = (void *)fd_type_pun( (void *)laddr );
108 6336 : fd_pubkey_t * pubkeys = (fd_pubkey_t *)fd_type_pun( (void *)laddr );
109 :
110 6336 : 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 6336 : fd_chacha20rng_t _rng[1];
114 6336 : fd_chacha20rng_t * rng = fd_chacha20rng_join( fd_chacha20rng_new( _rng, FD_CHACHA20RNG_MODE_MOD ) );
115 6336 : uchar key[ 32 ] = {0};
116 6336 : memcpy( key, &epoch, sizeof(ulong) );
117 6336 : fd_chacha20rng_init( rng, key );
118 :
119 6336 : void * _wsample = fd_wsample_new_init( wsample_mem, rng, pub_cnt, 0, FD_WSAMPLE_HINT_POWERLAW_NOREMOVE );
120 1326330 : for( ulong i=0UL; i<pub_cnt; i++ ) _wsample = fd_wsample_new_add( _wsample, stakes[i].stake );
121 6336 : 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 891462 : 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 6336 : fd_wsample_delete( fd_wsample_leave( wsample ) );
129 6336 : fd_chacha20rng_delete( fd_chacha20rng_leave( rng ) );
130 :
131 : /* Now we can use the space for the pubkeys */
132 1326330 : 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 6336 : static const uchar fd_indeterminate_leader[32] = { FD_INDETERMINATE_LEADER };
136 6336 : memcpy( pubkeys+pub_cnt, fd_indeterminate_leader, 32UL );
137 :
138 : /* Construct the final struct */
139 6336 : leaders->epoch = epoch;
140 6336 : leaders->slot0 = slot0;
141 6336 : leaders->slot_cnt = slot_cnt;
142 6336 : leaders->pub = pubkeys;
143 6336 : leaders->pub_cnt = pub_cnt;
144 6336 : leaders->sched = sched;
145 6336 : leaders->sched_cnt = sched_cnt;
146 :
147 6336 : return (void *)shmem;
148 6336 : }
149 :
150 : fd_epoch_leaders_t *
151 6336 : fd_epoch_leaders_join( void * shleaders ) {
152 6336 : return (fd_epoch_leaders_t *)shleaders;
153 6336 : }
154 :
155 : void *
156 6207 : fd_epoch_leaders_leave( fd_epoch_leaders_t * leaders ) {
157 6207 : return (void *)leaders;
158 6207 : }
159 :
160 : void *
161 6207 : fd_epoch_leaders_delete( void * shleaders ) {
162 6207 : return shleaders;
163 6207 : }
|
