Line data Source code
1 : #include "fd_shred_dest.h"
2 : #include "../../util/fd_hash32.h"
3 :
4 : struct pubkey_to_idx {
5 : fd_pubkey_t key;
6 : ulong idx;
7 : };
8 : typedef struct pubkey_to_idx pubkey_to_idx_t;
9 :
10 : static const fd_pubkey_t null_pubkey = {{ 0 }};
11 :
12 : #define MAP_NAME pubkey_to_idx
13 323223588 : #define MAP_T pubkey_to_idx_t
14 413607330 : #define MAP_KEY_T fd_pubkey_t
15 1010043186 : #define MAP_KEY_NULL null_pubkey
16 : #define MAP_KEY_EQUAL_IS_SLOW 1
17 : #define MAP_MEMOIZE 0
18 413607330 : #define MAP_KEY_INVAL(k) MAP_KEY_EQUAL((k),MAP_KEY_NULL)
19 509155104 : #define MAP_KEY_EQUAL(k0,k1) (!memcmp( (k0).key, (k1).key, 32UL ))
20 322596726 : #define MAP_KEY_HASH(k,s) ((MAP_HASH_T)fd_hash32( (k).key, (s) ))
21 :
22 : #include "../../util/tmpl/fd_map_dynamic.c"
23 :
24 :
25 : /* This 45 byte struct gets hashed to compute the seed for ChaCha to
26 : compute the shred destinations. */
27 : struct __attribute__((packed)) shred_dest_input {
28 : ulong slot;
29 : uchar type; /* Data = 0b1010_0101, Code = 0b0101_1010 */
30 : uint idx;
31 : uchar leader_pubkey[32];
32 : };
33 : typedef struct shred_dest_input shred_dest_input_t;
34 :
35 : ulong
36 120630 : fd_shred_dest_footprint( ulong staked_cnt, ulong unstaked_cnt ) {
37 120630 : ulong cnt = staked_cnt+unstaked_cnt;
38 120630 : int lg_cnt = fd_ulong_find_msb( fd_ulong_pow2_up( 2UL*fd_ulong_max( cnt, 1UL ) ) );
39 120630 : return FD_LAYOUT_FINI( FD_LAYOUT_APPEND( FD_LAYOUT_APPEND( FD_LAYOUT_APPEND( FD_LAYOUT_APPEND( FD_LAYOUT_APPEND(
40 120630 : FD_LAYOUT_INIT,
41 120630 : fd_shred_dest_align(), sizeof(fd_shred_dest_t) ),
42 120630 : pubkey_to_idx_align(), pubkey_to_idx_footprint( lg_cnt ) ),
43 120630 : alignof(fd_shred_dest_weighted_t), sizeof(fd_shred_dest_weighted_t)*cnt ),
44 120630 : fd_wsample_align(), fd_wsample_footprint( staked_cnt, 1 )),
45 120630 : alignof(ulong), sizeof(ulong)*unstaked_cnt ),
46 120630 : FD_SHRED_DEST_ALIGN );
47 120630 : }
48 :
49 :
50 : void *
51 : fd_shred_dest_new( void * mem,
52 : fd_shred_dest_weighted_t const * info,
53 : ulong cnt,
54 : fd_epoch_leaders_t const * lsched,
55 : fd_pubkey_t const * source,
56 313437 : ulong seed ) {
57 :
58 313437 : if( FD_UNLIKELY( !mem ) ) {
59 3 : FD_LOG_WARNING(( "NULL mem" ));
60 3 : return NULL;
61 3 : }
62 :
63 313434 : if( FD_UNLIKELY( !fd_ulong_is_aligned( (ulong)mem, fd_shred_dest_align() ) ) ) {
64 3 : FD_LOG_WARNING(( "misaligned mem" ));
65 3 : return NULL;
66 3 : }
67 :
68 313431 : int lg_cnt = fd_ulong_find_msb( fd_ulong_pow2_up( 2UL*fd_ulong_max( cnt, 1UL ) ) );
69 313431 : FD_SCRATCH_ALLOC_INIT( footprint, mem );
70 313431 : fd_shred_dest_t * sdest;
71 313431 : /* */ sdest = FD_SCRATCH_ALLOC_APPEND( footprint, fd_shred_dest_align(), sizeof(fd_shred_dest_t) );
72 313431 : void * _map = FD_SCRATCH_ALLOC_APPEND( footprint, pubkey_to_idx_align(), pubkey_to_idx_footprint( lg_cnt ) );
73 313431 : void * _info = FD_SCRATCH_ALLOC_APPEND( footprint, alignof(fd_shred_dest_weighted_t), sizeof(fd_shred_dest_weighted_t)*cnt );
74 :
75 313431 : ulong cnts[2] = { 0UL, 0UL }; /* cnts[0] = staked, cnts[1] = unstaked */
76 :
77 313431 : fd_shred_dest_weighted_t * copy = (fd_shred_dest_weighted_t *)_info;
78 318372987 : for( ulong i=0UL; i<cnt; i++ ) {
79 318059556 : copy[i] = info[i];
80 318059556 : ulong stake = info[i].stake_lamports;
81 : /* Check to make we never have a staked node following an unstaked
82 : node, which would mean info is not sorted properly. */
83 318059556 : if( FD_UNLIKELY( (stake>0UL) & (cnts[1]>0UL) ) ) {
84 0 : FD_LOG_WARNING(( "info was not sorted properly. info[%lu] has non-zero stake %lu but follows an unstaked node", i, stake ));
85 0 : return NULL;
86 0 : }
87 318059556 : cnts[ stake==0UL ]++;
88 318059556 : }
89 :
90 313431 : ulong staked_cnt = cnts[0];
91 313431 : ulong unstaked_cnt = cnts[1];
92 :
93 313431 : void * _wsample = FD_SCRATCH_ALLOC_APPEND( footprint, fd_wsample_align(), fd_wsample_footprint( staked_cnt, 1 ));
94 313431 : void * _unstaked = FD_SCRATCH_ALLOC_APPEND( footprint, alignof(ulong), sizeof(ulong)*unstaked_cnt );
95 :
96 :
97 313431 : fd_chacha_rng_t * rng = fd_chacha_rng_join( fd_chacha_rng_new( sdest->rng, FD_CHACHA_RNG_MODE_SHIFT ) );
98 :
99 313431 : void * _staked = fd_wsample_new_init( _wsample, rng, staked_cnt, 1, FD_WSAMPLE_HINT_POWERLAW_REMOVE );
100 :
101 191646270 : for( ulong i=0UL; i<staked_cnt; i++ ) _staked = fd_wsample_new_add( _staked, info[i].stake_lamports );
102 313431 : _staked = fd_wsample_new_fini( _staked, 0UL );
103 :
104 313431 : pubkey_to_idx_t * pubkey_to_idx_map = pubkey_to_idx_join( pubkey_to_idx_new( _map, lg_cnt, seed ) );
105 318372987 : for( ulong i=0UL; i<cnt; i++ ) {
106 : /* we should never have duplicates in info[i].pubkey, but in case
107 : of duplicates it's better to skip than to segfault. */
108 318059556 : pubkey_to_idx_t * inserted = pubkey_to_idx_insert( pubkey_to_idx_map, info[i].pubkey );
109 318059556 : if( FD_UNLIKELY( !inserted ) ) {
110 0 : continue;
111 0 : }
112 318059556 : inserted->idx = i;
113 318059556 : }
114 313431 : pubkey_to_idx_t * query = pubkey_to_idx_query( pubkey_to_idx_map, *source, NULL );
115 313431 : if( FD_UNLIKELY( !query ) ) {
116 3 : FD_LOG_WARNING(( "source pubkey not found" ));
117 3 : return NULL;
118 3 : }
119 :
120 313428 : memset( sdest->null_dest, 0, sizeof(fd_shred_dest_weighted_t) );
121 313428 : sdest->lsched = lsched;
122 313428 : sdest->cnt = cnt;
123 313428 : sdest->all_destinations = copy;
124 313428 : sdest->staked = fd_wsample_join( _staked );
125 313428 : sdest->unstaked = _unstaked;
126 313428 : sdest->unstaked_unremoved_cnt = 0UL; /* unstaked doesn't get initialized until it's needed */
127 313428 : sdest->staked_cnt = staked_cnt;
128 313428 : sdest->unstaked_cnt = unstaked_cnt;
129 313428 : sdest->pubkey_to_idx_map = pubkey_to_idx_map;
130 313428 : sdest->source_validator_orig_idx = query->idx;
131 :
132 313428 : return (void *)sdest;
133 313431 : }
134 :
135 313431 : fd_shred_dest_t * fd_shred_dest_join( void * mem ) { return (fd_shred_dest_t *)mem; }
136 313212 : void * fd_shred_dest_leave( fd_shred_dest_t * sdest ) { return (void *)sdest; }
137 :
138 313212 : void * fd_shred_dest_delete( void * mem ) {
139 313212 : fd_shred_dest_t * sdest = (fd_shred_dest_t *)mem;
140 :
141 313212 : fd_chacha_rng_delete( fd_chacha_rng_leave( sdest->rng ) );
142 313212 : fd_wsample_delete ( fd_wsample_leave ( sdest->staked ) );
143 313212 : pubkey_to_idx_delete( pubkey_to_idx_leave( sdest->pubkey_to_idx_map ) );
144 313212 : return mem;
145 313212 : }
146 :
147 : /* sample_unstaked, sample_unstaked_noprepare, and
148 : prepare_unstaked_sampling are used to perform the specific form of
149 : unweighted random sampling that Solana uses for unstaked validators.
150 : In essence, you:
151 : 1. construct a list of all the unstaked validators,
152 : 2. delete the leader (if present)
153 : then repeatedly:
154 : 3. choose the chacha_rng_roll( |unstaked| )th element.
155 : 4. swap the last element in unstaked with the chosen element
156 : 5. return and remove the chosen element (which is now in the last
157 : position, so remove is O(1)).
158 : Steps 1 and 2 are both O(|unstaked|), but they can be combined
159 : relatively easily if we wait to construct the list until we know
160 : which element we need to delete. prepare_unstaked_sampling performs
161 : steps 1 and 2. sample_unstaked performs steps 3-5. Thus, you must
162 : call prepare_unstaked_sampling prior to calling sample_unstaked.
163 :
164 : When only sampling a single element from the list, forming the whole
165 : array is wasteful; we just need to know whether the element we choose
166 : comes before or after the element we deleted.
167 : sample_unstaked_noprepare returns the same result as
168 : prepare_unstaked_sampling followed by one call to sample_unstaked.
169 : sample_unstaked_noprepare does not read or modify the unstaked array,
170 : so it can be called without calling prepare_unstaked_sampling.
171 :
172 : remove_idx is the index of the element to remove in step 2. If it is
173 : not in [sdest->staked_cnt, sdest->staked_cnt+sdest->unstaked_cnt),
174 : then it will be ignored. sample_unstaked and
175 : sample_unstaked_noprepare return the index into
176 : sdest->all_destinations of the selected sample. The returned value
177 : will be in [sdest->staked_cnt, sdest->staked_cnt+sdest->unstaked_cnt)
178 : or FD_WSAMPLE_EMPTY. */
179 : static inline ulong
180 : sample_unstaked_noprepare( fd_shred_dest_t * sdest,
181 99 : ulong remove_idx ) {
182 : /* is remove_idx in
183 : [sdest->staked_cnt, sdest->staked_cnt+sdest->unstaked_cnt) ? */
184 99 : int remove_in_interval = (sdest->staked_cnt <= remove_idx) & (remove_idx < (sdest->staked_cnt+sdest->unstaked_cnt) );
185 99 : ulong unstaked_cnt = sdest->unstaked_cnt - (ulong)remove_in_interval;
186 99 : if( FD_UNLIKELY( unstaked_cnt==0UL ) ) return FD_WSAMPLE_EMPTY;
187 :
188 99 : ulong sample = sdest->staked_cnt + fd_chacha_rng_ulong_roll( sdest->rng, unstaked_cnt );
189 99 : return fd_ulong_if( (!remove_in_interval) | (sample<remove_idx), sample, sample+1UL );
190 99 : }
191 :
192 : /* It's cheaper to initialize unstaked without the element we want to
193 : delete than to delete it after initializing, so we defer the
194 : initialization until we know who the leader is. */
195 : static inline void
196 : prepare_unstaked_sampling( fd_shred_dest_t * sdest,
197 302091 : ulong remove_idx ) {
198 302091 : int remove_in_interval = (sdest->staked_cnt <= remove_idx) & (remove_idx < (sdest->staked_cnt+sdest->unstaked_cnt) );
199 302091 : ulong unstaked_cnt = sdest->unstaked_cnt - (ulong)remove_in_interval;
200 302091 : sdest->unstaked_unremoved_cnt = unstaked_cnt;
201 302091 : if( FD_UNLIKELY( unstaked_cnt==0UL ) ) return;
202 :
203 : /* If we had to remove something in the interval, we want to make sure
204 : it doesn't occur in the list of indices. Otherwise just take them
205 : all. */
206 301260 : ulong direct_index_up_to = fd_ulong_if( remove_in_interval, remove_idx - sdest->staked_cnt, unstaked_cnt );
207 301260 : ulong i=0UL;
208 259402476 : for( ; i<direct_index_up_to; i++ ) sdest->unstaked[i] = i+sdest->staked_cnt;
209 795855 : for( ; i<unstaked_cnt; i++ ) sdest->unstaked[i] = i+sdest->staked_cnt + 1UL;
210 301260 : }
211 :
212 : static inline ulong
213 259620174 : sample_unstaked( fd_shred_dest_t * sdest ) {
214 259620174 : if( FD_UNLIKELY( sdest->unstaked_unremoved_cnt==0UL ) ) return FD_WSAMPLE_EMPTY;
215 :
216 259336827 : ulong sample = fd_chacha_rng_ulong_roll( sdest->rng, sdest->unstaked_unremoved_cnt );
217 259336827 : ulong to_return = sdest->unstaked[sample];
218 259336827 : sdest->unstaked[sample] = sdest->unstaked[--sdest->unstaked_unremoved_cnt];
219 259336827 : return to_return;
220 259620174 : }
221 :
222 :
223 : /* Returns 0 on success
224 : https://github.com/anza-xyz/agave/blob/v2.2.1/ledger/src/shred.rs#L293 */
225 : static inline int
226 : compute_seeds( fd_shred_dest_t * sdest,
227 : fd_shred_t const * const * input_shreds,
228 : ulong shred_cnt,
229 : fd_pubkey_t const * leader,
230 : ulong slot,
231 1154688 : uchar dest_hash_output[ FD_SHRED_DEST_MAX_SHRED_CNT ][ 32 ] ) {
232 :
233 1154688 : shred_dest_input_t dest_hash_inputs [ FD_SHRED_DEST_MAX_SHRED_CNT ];
234 1154688 : fd_sha256_batch_t * sha256 = fd_sha256_batch_init( sdest->_sha256_batch );
235 :
236 10198185 : for( ulong i=0UL; i<shred_cnt; i++ ) {
237 9043497 : shred_dest_input_t * h_in = dest_hash_inputs+i;
238 9043497 : fd_shred_t const * shred = input_shreds[i];
239 9043497 : if( FD_UNLIKELY( shred->slot != slot ) ) return -1;
240 :
241 9043497 : uchar shred_type = fd_shred_type( shred->variant );
242 9043497 : h_in->slot = slot;
243 9043497 : h_in->type = fd_uchar_if( fd_shred_is_data( shred_type ), 0xA5, 0x5A );
244 9043497 : h_in->idx = shred->idx;
245 9043497 : memcpy( h_in->leader_pubkey, leader, 32UL );
246 :
247 9043497 : fd_sha256_batch_add( sha256, dest_hash_inputs+i, sizeof(shred_dest_input_t), dest_hash_output[ i ] );
248 9043497 : }
249 1154688 : fd_sha256_batch_fini( sha256 );
250 1154688 : return 0;
251 1154688 : }
252 :
253 :
254 : fd_shred_dest_idx_t *
255 : fd_shred_dest_compute_first( fd_shred_dest_t * sdest,
256 : fd_shred_t const * const * input_shreds,
257 : ulong shred_cnt,
258 125811 : fd_shred_dest_idx_t * out ) {
259 :
260 125811 : if( FD_UNLIKELY( shred_cnt==0UL ) ) return out;
261 :
262 125811 : if( FD_UNLIKELY( sdest->cnt<=1UL ) ) {
263 : /* We are the only validator that we know about, and we can't send
264 : it to ourself, so there's nobody we can send the shred to. */
265 0 : for( ulong i=0UL; i<shred_cnt; i++ ) out[ i ] = FD_SHRED_DEST_NO_DEST;
266 0 : return out;
267 0 : }
268 :
269 125811 : uchar dest_hash_outputs[ FD_SHRED_DEST_MAX_SHRED_CNT ][ 32 ];
270 :
271 125811 : ulong slot = input_shreds[0]->slot;
272 125811 : fd_pubkey_t const * leader = fd_epoch_leaders_get( sdest->lsched, slot );
273 125811 : if( FD_UNLIKELY( !leader ) ) return NULL;
274 :
275 125811 : if( FD_UNLIKELY( compute_seeds( sdest, input_shreds, shred_cnt, leader, slot, dest_hash_outputs ) ) ) return NULL;
276 :
277 : /* If we're calling this, we must be the leader. That means we had
278 : some stake when the leader schedule was created, but maybe not
279 : anymore? This version of the code is safe either way, but I should
280 : probably confirm this can happen. */
281 125811 : int source_validator_is_staked = sdest->source_validator_orig_idx<sdest->staked_cnt;
282 125811 : if( FD_LIKELY( source_validator_is_staked ) )
283 124149 : fd_wsample_remove_idx( sdest->staked, sdest->source_validator_orig_idx );
284 :
285 125811 : int any_staked_candidates = sdest->staked_cnt > (ulong)source_validator_is_staked;
286 7811622 : for( ulong i=0UL; i<shred_cnt; i++ ) {
287 7685811 : fd_wsample_seed_rng( sdest->staked, dest_hash_outputs[ i ] );
288 : /* Map FD_WSAMPLE_EMPTY (UINT_MAX) to FD_SHRED_DEST_NO_DEST.
289 : Otherwise, since wsample guarantees the returned index is in
290 : [0, INT_MAX], it will remain non-negative when cast to an int. */
291 7685811 : FD_STATIC_ASSERT( (int)FD_WSAMPLE_EMPTY <=-1, wsample_val );
292 7685811 : FD_STATIC_ASSERT( FD_SHRED_DEST_NO_DEST==(fd_shred_dest_idx_t)-1, wsample_val );
293 7685811 : if( FD_LIKELY( any_staked_candidates ) ) out[i] = (fd_shred_dest_idx_t)fd_int_max( (int)fd_wsample_sample( sdest->staked ), -1 );
294 99 : else out[i] = (fd_shred_dest_idx_t)sample_unstaked_noprepare( sdest, sdest->source_validator_orig_idx );
295 7685811 : }
296 125811 : fd_wsample_restore_all( sdest->staked );
297 :
298 125811 : return out;
299 125811 : }
300 :
301 : fd_shred_dest_idx_t *
302 : fd_shred_dest_compute_children( fd_shred_dest_t * sdest,
303 : fd_shred_t const * const * input_shreds,
304 : ulong shred_cnt,
305 : fd_shred_dest_idx_t * out,
306 : ulong out_stride,
307 : ulong fanout,
308 : ulong dest_cnt,
309 1067184 : ulong * opt_max_dest_cnt ) {
310 :
311 : /* The logic here is a little tricky since we are keeping track of
312 : staked and unstaked separately and only logically concatenating
313 : them [staked, unstaked] , but that does allow us to skip some
314 : samples sometimes. We're operating from the source validator's
315 : perspective here, so everything in the first person singular refers
316 : to the source validator. */
317 :
318 1067184 : ulong my_orig_idx = sdest->source_validator_orig_idx;
319 1067184 : int i_am_staked = my_orig_idx<sdest->staked_cnt;
320 :
321 1067184 : fd_ulong_store_if( !!opt_max_dest_cnt, opt_max_dest_cnt, 0UL );
322 :
323 1067184 : if( FD_UNLIKELY( (shred_cnt==0UL) | (dest_cnt==0UL) ) ) return out; /* Nothing to do */
324 :
325 1067184 : ulong slot = input_shreds[0]->slot;
326 1067184 : fd_pubkey_t const * leader = fd_epoch_leaders_get ( sdest->lsched, slot );
327 1067184 : if( FD_UNLIKELY( !leader ) ) return NULL; /* Unknown slot */
328 :
329 1067184 : pubkey_to_idx_t * query = pubkey_to_idx_query( sdest->pubkey_to_idx_map, *leader, NULL );
330 1067184 : int leader_is_staked = query ? (query->idx<sdest->staked_cnt): 0;
331 1067184 : ulong leader_idx = query ? query->idx : ULONG_MAX;
332 1067184 : if( FD_UNLIKELY( leader_idx==my_orig_idx ) ) return NULL; /* I am the leader. Use compute_first */
333 :
334 1067184 : if( FD_UNLIKELY( (sdest->cnt<=1UL) | /* We don't know about a single destination, so we can't send
335 : anything. */
336 1067184 : ( (!i_am_staked) & (sdest->staked_cnt-(ulong)leader_is_staked>fanout) ) ) ) {
337 : /* My position is somewhere after all the staked nodes, which means
338 : my shuffled index is always greater than fanout. That means I'm
339 : always at the bottom of the Turbine tree so I don't have to send
340 : any shreds to anyone. Contiguous rows take one memset, NO_DEST
341 : is all bytes 0xFF. */
342 38307 : if( FD_LIKELY( out_stride==shred_cnt ) ) fd_memset( out, 0xFF, dest_cnt*shred_cnt*sizeof(fd_shred_dest_idx_t) );
343 90 : else for( ulong j=0UL; j<dest_cnt; j++ ) for( ulong i=0UL; i<shred_cnt; i++ ) out[ j*out_stride + i ] = FD_SHRED_DEST_NO_DEST;
344 38307 : return out;
345 38307 : }
346 :
347 1028877 : uchar dest_hash_outputs[ FD_SHRED_DEST_MAX_SHRED_CNT ][ 32 ];
348 :
349 :
350 1028877 : if( FD_UNLIKELY( compute_seeds( sdest, input_shreds, shred_cnt, leader, slot, dest_hash_outputs ) ) ) return NULL;
351 :
352 1028877 : ulong max_dest_cnt = 0UL;
353 :
354 1028877 : ulong staked_shuffle[ sdest->staked_cnt+1UL ];
355 1028877 : ulong staked_shuffle_populated_cnt = 0UL;
356 :
357 2386563 : for( ulong i=0UL; i<shred_cnt; i++ ) {
358 : /* Remove the leader. */
359 1357686 : if( FD_LIKELY( query && leader_is_staked ) ) fd_wsample_remove_idx( sdest->staked, leader_idx );
360 :
361 1357686 : ulong my_idx = 0UL;
362 1357686 : fd_wsample_seed_rng( sdest->staked, dest_hash_outputs[ i ] ); /* Seeds both samplers since the rng is shared */
363 :
364 1357686 : if( FD_UNLIKELY( !i_am_staked ) ) {
365 : /* Quickly burn through all the staked nodes since I'll be in the
366 : unstaked portion. We don't care about the values, but we need
367 : to advance the RNG the right number of times, and sadly there's
368 : no other way to do it than this. There can't be too many of
369 : them since otherwise we would have taken the quick exit at the
370 : start of the function. */
371 37503 : staked_shuffle_populated_cnt = sdest->staked_cnt + 1UL;
372 37503 : fd_wsample_sample_and_remove_many( sdest->staked, staked_shuffle, staked_shuffle_populated_cnt );
373 37503 : my_idx += sdest->staked_cnt - (ulong)(query && leader_is_staked);
374 :
375 37503 : prepare_unstaked_sampling( sdest, leader_idx );
376 342495 : while( my_idx <= fanout ) {
377 325584 : ulong sample = sample_unstaked( sdest );
378 325584 : if( FD_UNLIKELY( sample==my_orig_idx ) ) break; /* Found me! */
379 304992 : if( FD_UNLIKELY( sample==FD_WSAMPLE_EMPTY ) ) return NULL; /* I couldn't find myself. This should be impossible. */
380 304992 : my_idx++;
381 304992 : }
382 1320183 : } else {
383 1320183 : staked_shuffle_populated_cnt = fd_ulong_min( fanout+1UL, sdest->staked_cnt+1UL );
384 1320183 : fd_wsample_sample_and_remove_many( sdest->staked, staked_shuffle, staked_shuffle_populated_cnt );
385 94021644 : while( my_idx <= fanout ) {
386 : /* my_idx < fanout+1UL because of the while loop condition.
387 : my_idx < staked_cnt+1UL because my_idx==staked_cnt will
388 : trigger sample==FD_WSAMPLE_EMPTY below. Thus, this access is
389 : safe. */
390 93718176 : ulong sample = staked_shuffle[ my_idx ];
391 93718176 : if( FD_UNLIKELY( sample==my_orig_idx ) ) break; /* Found me! */
392 92701461 : if( FD_UNLIKELY( sample==FD_WSAMPLE_EMPTY ) ) return NULL; /* I couldn't find myself. This should be impossible. */
393 92701461 : my_idx++;
394 92701461 : }
395 1320183 : }
396 :
397 1357686 : if( FD_LIKELY( my_idx > fanout ) ) {
398 : /* I'm at the bottom of Turbine tree for this shred. Fill in all
399 : the destinations with NO_DEST. */
400 67566363 : for( ulong j=0UL; j<dest_cnt; j++ ) out[ j*out_stride + i ] = FD_SHRED_DEST_NO_DEST;
401 :
402 320379 : fd_wsample_restore_all( sdest->staked );
403 320379 : continue; /* Next shred */
404 320379 : }
405 : /* If my index is | Send to indices
406 : ------------------------------------
407 : Leader (no idx) | 0 (just for reference)
408 : 0 | 1, 2, ..., F
409 : j in [1, F] | j + l*F for l in [1,F]
410 : [F+1, F^2+F] | Nobody
411 : [F^2+F+1, inf) | Not yet implemented in Agave code
412 : */
413 1037307 : ulong last_dest_idx = fd_ulong_if( my_idx==0UL, fanout, my_idx+fanout*fanout ); /* inclusive */
414 1037307 : ulong stride = fd_ulong_if( my_idx==0UL, 1UL, fanout );
415 :
416 1037307 : last_dest_idx = fd_ulong_min( last_dest_idx, my_idx + stride*dest_cnt );
417 :
418 1037307 : ulong cursor = my_idx+1UL;
419 1037307 : ulong stored_cnt = 0UL;
420 :
421 1037307 : if( FD_LIKELY( (last_dest_idx>=staked_shuffle_populated_cnt) & (staked_shuffle_populated_cnt<sdest->staked_cnt+1UL ) ) ) {
422 570681 : ulong adtl = fd_ulong_min( last_dest_idx+1UL, sdest->staked_cnt+1UL ) - staked_shuffle_populated_cnt;
423 :
424 570681 : fd_wsample_sample_and_remove_many( sdest->staked, staked_shuffle+staked_shuffle_populated_cnt, adtl );
425 570681 : staked_shuffle_populated_cnt += adtl;
426 570681 : }
427 :
428 152306799 : while( cursor<=fd_ulong_min( last_dest_idx, sdest->staked_cnt ) ) {
429 151534617 : ulong sample = staked_shuffle[ cursor ];
430 151534617 : if( FD_UNLIKELY( sample==FD_WSAMPLE_EMPTY ) ) break;
431 :
432 151269492 : if( FD_UNLIKELY( cursor == my_idx + stride*(stored_cnt+1UL) ) ) {
433 4702008 : out[ stored_cnt*out_stride + i ] = (fd_shred_dest_idx_t)sample;
434 4702008 : stored_cnt++;
435 4702008 : }
436 151269492 : cursor++;
437 151269492 : }
438 :
439 : /* Next set of samples (if any) come from the unstaked portion. If I
440 : am not staked, then prepare_unstaked_sampling was already called
441 : earlier. */
442 1037307 : if( FD_LIKELY( (cursor<=last_dest_idx) & !!i_am_staked ) ) prepare_unstaked_sampling( sdest, leader_idx );
443 260048550 : while( cursor<=last_dest_idx ) {
444 259294590 : ulong sample = sample_unstaked( sdest );
445 259294590 : if( FD_UNLIKELY( sample==FD_WSAMPLE_EMPTY ) ) break;
446 :
447 259011243 : if( FD_UNLIKELY( cursor == my_idx + stride*(stored_cnt+1UL) ) ) {
448 1298172 : out[ stored_cnt*out_stride + i ] = (fd_shred_dest_idx_t)sample;
449 1298172 : stored_cnt++;
450 1298172 : }
451 259011243 : cursor++;
452 259011243 : }
453 1037307 : max_dest_cnt = fd_ulong_max( max_dest_cnt, stored_cnt );
454 :
455 : /* The rest of my destinations are past the end of the tree */
456 59236113 : for( ulong j=stored_cnt; j<dest_cnt; j++ ) out[ j*out_stride + i ] = FD_SHRED_DEST_NO_DEST;
457 :
458 1037307 : fd_wsample_restore_all( sdest->staked );
459 :
460 1037307 : }
461 1028877 : fd_ulong_store_if( !!opt_max_dest_cnt, opt_max_dest_cnt, max_dest_cnt );
462 1028877 : return out;
463 1028877 : }
464 :
465 : fd_shred_dest_idx_t
466 : fd_shred_dest_pubkey_to_idx( fd_shred_dest_t * sdest,
467 3156555 : fd_pubkey_t const * pubkey ) {
468 3156555 : if( FD_UNLIKELY( !memcmp( pubkey, null_pubkey.uc, 32UL ) ) ) return FD_SHRED_DEST_NO_DEST;
469 :
470 3156555 : pubkey_to_idx_t default_res[ 1 ] = {{ .idx = FD_SHRED_DEST_NO_DEST }};
471 3156555 : pubkey_to_idx_t * query = pubkey_to_idx_query( sdest->pubkey_to_idx_map, *pubkey, default_res );
472 :
473 3156555 : return (fd_shred_dest_idx_t)query->idx;
474 3156555 : }
475 :
476 : fd_shred_dest_idx_t
477 : fd_shred_dest_leader_for_slot( fd_shred_dest_t const * sdest,
478 0 : ulong slot ) {
479 0 : fd_pubkey_t const * leader = fd_epoch_leaders_get( sdest->lsched, slot );
480 0 : if( FD_UNLIKELY( !leader ) ) return FD_SHRED_DEST_NO_DEST;
481 :
482 0 : pubkey_to_idx_t default_res[ 1 ] = {{ .idx = FD_SHRED_DEST_NO_DEST }};
483 0 : pubkey_to_idx_t const * query = pubkey_to_idx_query( sdest->pubkey_to_idx_map, *leader, default_res );
484 0 : if( FD_UNLIKELY( query->idx==sdest->source_validator_orig_idx ) ) return FD_SHRED_DEST_NO_DEST;
485 :
486 0 : return (fd_shred_dest_idx_t)query->idx;
487 0 : }
488 :
|
