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