Line data Source code
1 : /* fd_gossip_wsample implements stake-weighted peer sampling for gossip.
2 :
3 : Internally, the sampler maintains 26 independent 9-ary left-sum trees
4 : (1 for pull-request sampling + 25 for bucket sampling). Each tree
5 : supports O(log_9 n) weight updates and O(log_9 n) sampling. See
6 : src/ballet/wsample/fd_wsample.c for a detailed explanation of the
7 : 9-ary left-sum tree data structure.
8 :
9 : The bucket scoring formula (bucket_score) and bucket count (25) match
10 : the active-set rotation logic in fd_active_set. */
11 :
12 : #include "fd_gossip_wsample.h"
13 : #include "fd_active_set.h"
14 : #include "../../util/log/fd_log.h"
15 :
16 37950807 : #define R (9UL) /* Radix of the sampling trees. */
17 513993 : #define BUCKET_CNT (25UL) /* Number of active-set buckets (stake tiers). */
18 63 : #define TREE_CNT (1UL+BUCKET_CNT) /* Total number of trees: 1 pull-request tree + BUCKET_CNT bucket trees. */
19 639054 : #define PR_TREE_IDX (0UL) /* Index of the pull-request tree among the TREE_CNT trees. */
20 :
21 : /* Computes the pull-request tree weight for a peer with the given
22 : stake. Matches Agave's formula:
23 :
24 : stake_sol = stake / LAMPORTS_PER_SOL
25 : bucket = floor(log2(stake_sol)) + 1 (0 when stake_sol==0)
26 : weight = (bucket + 1)^2
27 :
28 : This gives a logarithmic compression so that high-stake nodes are
29 : preferred but not overwhelmingly so. Zero-stake peers get weight 1. */
30 :
31 : static inline ulong
32 18669 : pr_weight( ulong stake ) {
33 18669 : ulong stake_sol = stake / 1000000000UL;
34 18669 : ulong bucket = stake_sol ? ( 64UL - (ulong)__builtin_clzl( stake_sol ) ) : 0UL;
35 18669 : ulong w = bucket + 1UL;
36 18669 : return w * w;
37 18669 : }
38 :
39 : /* 9-ary tree node. Each internal node stores the cumulative weight of
40 : its first R-1 subtrees (see fd_wsample.c for the algorithm). */
41 :
42 : struct gossip_wsample_tree_ele {
43 : ulong left_sum[ R-1UL ];
44 : };
45 :
46 : typedef struct gossip_wsample_tree_ele tree_ele_t;
47 :
48 : struct fd_gossip_wsample_private {
49 : fd_rng_t * rng; /* borrowed; not owned */
50 : ulong max_peers; /* capacity (max sparse peer idx + 1) */
51 : ulong internal_cnt; /* number of internal tree nodes per tree */
52 : ulong height; /* tree height (levels above the implicit
53 : leaves; 0 when max_peers<=1) */
54 : ulong * stakes; /* per-peer stake amounts */
55 : int * exists; /* per-peer existence flags (for quick validity checks) */
56 : int * fresh; /* per-peer freshness flags */
57 : int * ping_tracked; /* per-peer ping-tracked flag */
58 : int ** is_removed; /* per-peer per-bucket is-removed flag */
59 : tree_ele_t * trees; /* TREE_CNT * internal_cnt tree nodes */
60 : ulong self_stake; /* our own stake; PR weights are capped at this */
61 : ulong self_ci_idx; /* our own contact info index, or ULONG_MAX if none */
62 : ulong pr_total_weight;
63 : ulong bucket_total_weight[ BUCKET_CNT ];
64 : };
65 :
66 : /* Given a leaf count, computes the tree height and the number of
67 : internal nodes. height = ceil(log_R(leaf_cnt)); internal_cnt =
68 : sum_{i=0}^{height-1} R^i = (R^height - 1)/(R - 1). When
69 : leaf_cnt<=1, height and internal_cnt are both 0. */
70 :
71 : static inline void
72 : compute_height( ulong leaf_cnt,
73 : ulong * out_height,
74 132 : ulong * out_internal_cnt ) {
75 132 : ulong height = 0UL;
76 132 : ulong internal = 0UL;
77 132 : ulong pow_r = 1UL; /* R^height */
78 411 : while( leaf_cnt>pow_r ) {
79 279 : internal += pow_r;
80 279 : pow_r *= R;
81 279 : height++;
82 279 : }
83 132 : *out_height = height;
84 132 : *out_internal_cnt = internal;
85 132 : }
86 :
87 : /* Computes the weight of a peer with the given stake in the given
88 : bucket tree. Always returns >= 1 (even when stake is 0). */
89 :
90 : static inline ulong
91 : bucket_score( ulong stake,
92 527394 : ulong bucket ) {
93 527394 : ulong peer_bucket = fd_active_set_stake_bucket( stake );
94 527394 : ulong score = fd_ulong_min( bucket, peer_bucket ) + 1UL;
95 527394 : return score * score;
96 527394 : }
97 :
98 : /* Compute the target PR tree weight for a peer, accounting for
99 : freshness. Matches Agave's get_gossip_nodes logic: fresh peers get
100 : full weight, unfresh unstaked peers get 0, unfresh staked peers get
101 : full/16 (min 1). */
102 :
103 : static inline ulong
104 : adjusted_pr_weight( ulong stake,
105 : ulong self_stake,
106 6282 : int is_fresh ) {
107 6282 : ulong full = pr_weight( fd_ulong_min( stake, self_stake ) );
108 6282 : if( FD_LIKELY( is_fresh ) ) return full;
109 48 : if( FD_UNLIKELY( !stake ) ) return 0UL;
110 21 : ulong w = full/16UL;
111 21 : return w ? w : 1UL;
112 48 : }
113 :
114 : /* Compute the target bucket tree weight for a peer, accounting for
115 : freshness. In Agave, get_gossip_nodes filters stale peers before
116 : push active-set rotation, so unfresh peers should be downweighted in
117 : bucket trees too (unstaked excluded, staked 1/16). */
118 :
119 : static inline ulong
120 : adjusted_bucket_weight( ulong stake,
121 : ulong bucket,
122 527394 : int is_fresh ) {
123 527394 : ulong full = bucket_score( stake, bucket );
124 527394 : if( FD_LIKELY( is_fresh ) ) return full;
125 4812 : if( FD_UNLIKELY( !stake ) ) return 0UL;
126 4137 : ulong w = full/16UL;
127 4137 : return w ? w : 1UL;
128 4812 : }
129 :
130 : /* Add delta weight to the leaf at leaf_idx, propagating the update up
131 : to root. Uses branchless inner loop (see fd_wsample.c). */
132 :
133 : static void
134 : tree_add_weight( tree_ele_t * tree,
135 : ulong height,
136 : ulong internal_cnt,
137 : ulong leaf_idx,
138 352722 : ulong delta ) {
139 352722 : ulong cursor = leaf_idx + internal_cnt;
140 1697532 : for( ulong h=0UL; h<height; h++ ) {
141 1344810 : ulong parent = (cursor-1UL) / R;
142 1344810 : ulong child_idx = cursor-1UL - R*parent;
143 12103290 : for( ulong k=0UL; k<R-1UL; k++ ) {
144 10758480 : tree[ parent ].left_sum[ k ] += (ulong)(((long)(child_idx-k-1UL))>>63) & delta;
145 10758480 : }
146 1344810 : cursor = parent;
147 1344810 : }
148 352722 : }
149 :
150 : /* Subtract delta weight from the leaf at leaf_idx, propagating the
151 : update up to root. */
152 :
153 : static void
154 : tree_sub_weight( tree_ele_t * tree,
155 : ulong height,
156 : ulong internal_cnt,
157 : ulong leaf_idx,
158 191853 : ulong delta ) {
159 191853 : ulong cursor = leaf_idx + internal_cnt;
160 896688 : for( ulong h=0UL; h<height; h++ ) {
161 704835 : ulong parent = (cursor-1UL) / R;
162 704835 : ulong child_idx = cursor-1UL - R*parent;
163 6343515 : for( ulong k=0UL; k<R-1UL; k++ ) {
164 5638680 : tree[ parent ].left_sum[ k ] -= (ulong)(((long)(child_idx-k-1UL))>>63) & delta;
165 5638680 : }
166 704835 : cursor = parent;
167 704835 : }
168 191853 : }
169 :
170 : /* Weighted sample from a tree. Returns (leaf_idx, leaf_weight).
171 : Returns (.idx=ULONG_MAX, .weight=0) when total_weight==0. */
172 :
173 : typedef struct { ulong idx; ulong weight; } sample_result_t;
174 :
175 : static inline sample_result_t
176 : tree_sample( tree_ele_t const * tree,
177 : ulong height,
178 : ulong internal_cnt,
179 : ulong total_weight,
180 652758 : fd_rng_t * rng ) {
181 652758 : if( FD_UNLIKELY( !total_weight ) ) {
182 480 : sample_result_t empty = { .idx = ULONG_MAX, .weight = 0UL };
183 480 : return empty;
184 480 : }
185 :
186 652278 : ulong query = fd_rng_ulong_roll( rng, total_weight );
187 652278 : ulong cursor = 0UL;
188 652278 : ulong S = total_weight;
189 :
190 2052681 : for( ulong h=0UL; h<height; h++ ) {
191 1400403 : tree_ele_t const * e = tree + cursor;
192 :
193 : /* Branchless child selection: count how many left_sum entries are
194 : <= the query value. */
195 1400403 : ulong child_idx = 0UL;
196 12603627 : for( ulong i=0UL; i<R-1UL; i++ ) child_idx += (ulong)( e->left_sum[ i ]<=query );
197 :
198 1400403 : ulong lm1 = child_idx > 0UL ? e->left_sum[ child_idx-1UL] : 0UL;
199 1400403 : ulong li = child_idx < R-1UL ? e->left_sum[ child_idx ] : S;
200 :
201 1400403 : query -= lm1;
202 1400403 : S = li - lm1;
203 1400403 : cursor = R*cursor+child_idx+1UL;
204 1400403 : }
205 :
206 652278 : sample_result_t result = { .idx = cursor - internal_cnt, .weight = S };
207 652278 : return result;
208 652758 : }
209 :
210 : FD_FN_CONST ulong
211 129 : fd_gossip_wsample_align( void ) {
212 129 : return 64UL;
213 129 : }
214 :
215 : FD_FN_CONST ulong
216 72 : fd_gossip_wsample_footprint( ulong max_peers ) {
217 72 : if( FD_UNLIKELY( !max_peers ) ) return 0UL;
218 :
219 69 : ulong height;
220 69 : ulong internal_cnt;
221 69 : compute_height( max_peers, &height, &internal_cnt );
222 69 : (void)height;
223 :
224 69 : ulong l = FD_LAYOUT_INIT;
225 69 : l = FD_LAYOUT_APPEND( l, 64UL, sizeof(struct fd_gossip_wsample_private) );
226 69 : l = FD_LAYOUT_APPEND( l, 8UL, max_peers*sizeof(ulong) ); /* stakes */
227 69 : l = FD_LAYOUT_APPEND( l, 4UL, max_peers*sizeof(int) ); /* exists */
228 69 : l = FD_LAYOUT_APPEND( l, 4UL, max_peers*sizeof(int) ); /* fresh */
229 69 : l = FD_LAYOUT_APPEND( l, 4UL, max_peers*sizeof(int) ); /* ping_tracked */
230 69 : l = FD_LAYOUT_APPEND( l, 8UL, max_peers*sizeof(int *) ); /* is_removed */
231 69 : l = FD_LAYOUT_APPEND( l, 4UL, max_peers*BUCKET_CNT*sizeof(int) ); /* removed */
232 69 : l = FD_LAYOUT_APPEND( l, 64UL, TREE_CNT*internal_cnt*sizeof(tree_ele_t) );
233 69 : return FD_LAYOUT_FINI( l, 64UL );
234 72 : }
235 :
236 : void *
237 : fd_gossip_wsample_new( void * shmem,
238 : fd_rng_t * rng,
239 69 : ulong max_peers ) {
240 69 : if( FD_UNLIKELY( !shmem ) ) return NULL;
241 66 : if( FD_UNLIKELY( !rng ) ) return NULL;
242 66 : if( FD_UNLIKELY( !max_peers ) ) return NULL;
243 63 : if( FD_UNLIKELY( !fd_ulong_is_aligned( (ulong)shmem, fd_gossip_wsample_align() ) ) ) return NULL;
244 :
245 63 : ulong height;
246 63 : ulong internal_cnt;
247 63 : compute_height( max_peers, &height, &internal_cnt );
248 :
249 63 : fd_gossip_wsample_t * s = (fd_gossip_wsample_t *)shmem;
250 :
251 63 : s->rng = rng;
252 63 : s->max_peers = max_peers;
253 63 : s->internal_cnt = internal_cnt;
254 63 : s->height = height;
255 :
256 : /* Compute trailing-array pointers. */
257 63 : FD_SCRATCH_ALLOC_INIT( l, shmem );
258 63 : /* */ FD_SCRATCH_ALLOC_APPEND( l, 64UL, sizeof(struct fd_gossip_wsample_private) );
259 63 : s->stakes = FD_SCRATCH_ALLOC_APPEND( l, alignof(ulong), max_peers*sizeof(ulong) );
260 63 : s->exists = FD_SCRATCH_ALLOC_APPEND( l, alignof(int), max_peers*sizeof(int) );
261 63 : s->fresh = FD_SCRATCH_ALLOC_APPEND( l, alignof(int), max_peers*sizeof(int) );
262 63 : s->ping_tracked = FD_SCRATCH_ALLOC_APPEND( l, alignof(int), max_peers*sizeof(int) );
263 63 : s->is_removed = FD_SCRATCH_ALLOC_APPEND( l, alignof(int *), max_peers*sizeof(int *) );
264 63 : int * is_removed = FD_SCRATCH_ALLOC_APPEND( l, alignof(int), max_peers*BUCKET_CNT*sizeof(int) );
265 63 : s->trees = FD_SCRATCH_ALLOC_APPEND( l, 64UL, TREE_CNT*internal_cnt*sizeof(tree_ele_t) );
266 :
267 : /* Zero-initialize stakes, fresh flags, and trees. */
268 63 : fd_memset( s->stakes, 0, max_peers * sizeof(ulong) );
269 63 : fd_memset( s->exists, 0, max_peers * sizeof(int) );
270 63 : fd_memset( s->fresh, 0, max_peers * sizeof(int) );
271 63 : fd_memset( s->ping_tracked, 0, max_peers * sizeof(int) );
272 63 : fd_memset( is_removed, 0, max_peers * BUCKET_CNT*sizeof(int) );
273 63 : if( FD_LIKELY( internal_cnt ) ) fd_memset( s->trees, 0, TREE_CNT*internal_cnt*sizeof(tree_ele_t) );
274 :
275 : /* Zero-initialize total weights and self stake. */
276 63 : s->self_stake = 0UL;
277 63 : s->self_ci_idx = ULONG_MAX;
278 63 : s->pr_total_weight = 0UL;
279 1638 : for( ulong b=0UL; b<BUCKET_CNT; b++ ) s->bucket_total_weight[ b ] = 0UL;
280 :
281 16317 : for( ulong i=0UL; i<max_peers; i++ ) s->is_removed[ i ] = is_removed + i*BUCKET_CNT;
282 :
283 63 : return shmem;
284 63 : }
285 :
286 : fd_gossip_wsample_t *
287 63 : fd_gossip_wsample_join( void * shwsample ) {
288 63 : return (fd_gossip_wsample_t *)shwsample;
289 63 : }
290 :
291 : static inline int
292 : is_active( ulong stake,
293 80688 : int ping_tracked ) {
294 : /* 1. If the node has more than 1 sol staked, it is active */
295 80688 : if( FD_UNLIKELY( stake>=1000000000UL ) ) return 1;
296 :
297 : /* 2. If the node has actively ponged a ping, it is active */
298 20589 : if( FD_UNLIKELY( ping_tracked ) ) return 1;
299 :
300 18 : return 0;
301 20589 : }
302 :
303 : void
304 : fd_gossip_wsample_add( fd_gossip_wsample_t * sampler,
305 : ulong ci_idx,
306 : ulong stake,
307 : int ping_tracked,
308 12390 : int is_me ) {
309 12390 : FD_TEST( !sampler->exists[ ci_idx ] );
310 :
311 12390 : sampler->exists[ ci_idx ] = 1;
312 12390 : sampler->stakes[ ci_idx ] = stake;
313 12390 : sampler->fresh[ ci_idx ] = 1; /* newly added peers are fresh */
314 12390 : sampler->ping_tracked[ ci_idx ] = ping_tracked;
315 12390 : fd_memset( sampler->is_removed[ ci_idx ], 0, BUCKET_CNT*sizeof(int) );
316 :
317 12390 : if( FD_UNLIKELY( is_me ) ) {
318 0 : FD_TEST( sampler->self_ci_idx==ULONG_MAX );
319 0 : sampler->self_ci_idx = ci_idx;
320 0 : return;
321 0 : }
322 :
323 12390 : ulong height = sampler->height;
324 12390 : ulong internal_cnt = sampler->internal_cnt;
325 :
326 : /* Only active peers get weight in any sampler tree. Inactive
327 : peers (e.g. un-pinged, or our own identity) are tracked by stake
328 : but remain unsampleable until they become active. */
329 12390 : if( FD_LIKELY( is_active( stake, ping_tracked ) ) ) {
330 : /* Pull-request tree: log-squared weight matching Agave, with the
331 : peer's stake capped at our own stake. */
332 12387 : ulong pr_w = pr_weight( fd_ulong_min( stake, sampler->self_stake ) );
333 12387 : tree_add_weight( sampler->trees+PR_TREE_IDX*internal_cnt, height, internal_cnt, ci_idx, pr_w );
334 12387 : sampler->pr_total_weight += pr_w;
335 :
336 : /* Bucket trees. */
337 322062 : for( ulong b=0UL; b<BUCKET_CNT; b++ ) {
338 309675 : ulong bw = adjusted_bucket_weight( stake, b, 1 /* is_fresh */ );
339 309675 : tree_add_weight( sampler->trees+(1UL+b)*internal_cnt, height, internal_cnt, ci_idx, bw );
340 309675 : sampler->bucket_total_weight[ b ] += bw;
341 309675 : }
342 12387 : }
343 12390 : }
344 :
345 : void
346 : fd_gossip_wsample_remove( fd_gossip_wsample_t * sampler,
347 6162 : ulong ci_idx ) {
348 6162 : FD_TEST( sampler->exists[ ci_idx ] );
349 :
350 6162 : sampler->exists[ ci_idx ] = 0;
351 6162 : if( FD_UNLIKELY( sampler->self_ci_idx==ci_idx ) ) {
352 0 : sampler->self_ci_idx = ULONG_MAX;
353 0 : return;
354 0 : }
355 :
356 6162 : int active = is_active( sampler->stakes[ ci_idx ], sampler->ping_tracked[ ci_idx ] );
357 6162 : if( FD_UNLIKELY( !active ) ) return;
358 :
359 6162 : ulong height = sampler->height;
360 6162 : ulong internal_cnt = sampler->internal_cnt;
361 :
362 6162 : ulong pr_w = adjusted_pr_weight( sampler->stakes[ ci_idx ], sampler->self_stake, sampler->fresh[ ci_idx ] );
363 6162 : tree_sub_weight( sampler->trees+PR_TREE_IDX*internal_cnt, height, internal_cnt, ci_idx, pr_w );
364 6162 : sampler->pr_total_weight -= pr_w;
365 :
366 160212 : for( ulong b=0UL; b<BUCKET_CNT; b++ ) {
367 154050 : if( FD_UNLIKELY( sampler->is_removed[ ci_idx ][ b ] ) ) continue; /* Peer was already sample-removed from this bucket, so no weight to remove. */
368 :
369 153291 : ulong bw = adjusted_bucket_weight( sampler->stakes[ ci_idx ], b, sampler->fresh[ ci_idx ] );
370 153291 : tree_sub_weight( sampler->trees+(1UL+b)*internal_cnt, height, internal_cnt, ci_idx, bw );
371 153291 : sampler->bucket_total_weight[ b ] -= bw;
372 153291 : }
373 6162 : }
374 :
375 : ulong
376 620436 : fd_gossip_wsample_sample_pull_request( fd_gossip_wsample_t * sampler ) {
377 620436 : sample_result_t r = tree_sample( sampler->trees + PR_TREE_IDX*sampler->internal_cnt,
378 620436 : sampler->height,
379 620436 : sampler->internal_cnt,
380 620436 : sampler->pr_total_weight,
381 620436 : sampler->rng );
382 620436 : return r.idx;
383 620436 : }
384 :
385 : ulong
386 : fd_gossip_wsample_sample_remove_bucket( fd_gossip_wsample_t * sampler,
387 32322 : ulong bucket ) {
388 32322 : tree_ele_t * bt = sampler->trees + (1UL+bucket)*sampler->internal_cnt;
389 :
390 32322 : sample_result_t r = tree_sample( bt,
391 32322 : sampler->height,
392 32322 : sampler->internal_cnt,
393 32322 : sampler->bucket_total_weight[bucket],
394 32322 : sampler->rng );
395 32322 : if( FD_UNLIKELY( r.idx==ULONG_MAX ) ) return ULONG_MAX;
396 :
397 : /* Remove the sampled peer from this bucket tree so it cannot be
398 : sampled again until re-added with fd_gossip_wsample_add_bucket. */
399 31860 : FD_TEST( sampler->exists[ r.idx ] );
400 31860 : int active = is_active( sampler->stakes[ r.idx ], sampler->ping_tracked[ r.idx ] );
401 31860 : ulong weight = fd_ulong_if( active, adjusted_bucket_weight( sampler->stakes[ r.idx ], bucket, sampler->fresh[ r.idx ] ), 0UL );
402 31860 : FD_TEST( r.weight==weight );
403 31860 : FD_TEST( !sampler->is_removed[ r.idx ][ bucket ] );
404 31860 : FD_TEST( sampler->self_ci_idx!=r.idx );
405 31860 : tree_sub_weight( bt, sampler->height, sampler->internal_cnt, r.idx, r.weight );
406 31860 : sampler->bucket_total_weight[ bucket ] -= r.weight;
407 31860 : sampler->is_removed[ r.idx ][ bucket ] = 1;
408 :
409 31860 : return r.idx;
410 31860 : }
411 :
412 : void
413 : fd_gossip_wsample_add_bucket( fd_gossip_wsample_t * sampler,
414 : ulong bucket,
415 30168 : ulong ci_idx ) {
416 30168 : FD_TEST( sampler->exists[ ci_idx ] );
417 30168 : FD_TEST( sampler->is_removed[ ci_idx ][ bucket ] );
418 30168 : FD_TEST( sampler->self_ci_idx!=ci_idx );
419 :
420 30168 : ulong stake = sampler->stakes[ ci_idx ];
421 30168 : int is_fresh = sampler->fresh[ ci_idx ];
422 30168 : int active = is_active( stake, sampler->ping_tracked[ ci_idx ] );
423 30168 : ulong bw = fd_ulong_if( active, adjusted_bucket_weight( stake, bucket, is_fresh ), 0UL );
424 :
425 30168 : tree_add_weight( sampler->trees + (1UL+bucket)*sampler->internal_cnt, sampler->height, sampler->internal_cnt, ci_idx, bw );
426 30168 : sampler->bucket_total_weight[ bucket ] += bw;
427 30168 : sampler->is_removed[ ci_idx ][ bucket ] = 0;
428 30168 : }
429 :
430 : static void
431 : recompute( fd_gossip_wsample_t * sampler,
432 : ulong ci_idx,
433 : ulong old_stake,
434 : int old_fresh,
435 : int old_ping_tracked,
436 48 : int old_is_me ) {
437 48 : FD_TEST( sampler->exists[ ci_idx ] );
438 :
439 48 : int old_active = is_active( old_stake, old_ping_tracked );
440 48 : int new_active = is_active( sampler->stakes[ ci_idx ], sampler->ping_tracked[ ci_idx ] );
441 :
442 48 : int is_fresh = sampler->fresh[ ci_idx ];
443 48 : ulong height = sampler->height;
444 48 : ulong internal_cnt = sampler->internal_cnt;
445 :
446 : /* Update pull-request tree weight. */
447 48 : tree_ele_t * pr = sampler->trees + PR_TREE_IDX*internal_cnt;
448 48 : ulong old_pr_w = fd_ulong_if( old_active, adjusted_pr_weight( old_stake, sampler->self_stake, old_fresh ), 0UL );
449 48 : if( FD_UNLIKELY( old_is_me ) ) old_pr_w = 0UL;
450 48 : ulong new_pr_w = fd_ulong_if( new_active, adjusted_pr_weight( sampler->stakes[ ci_idx ], sampler->self_stake, is_fresh ), 0UL );
451 48 : if( FD_UNLIKELY( sampler->self_ci_idx==ci_idx ) ) new_pr_w = 0UL;
452 :
453 48 : if( FD_LIKELY( new_pr_w>old_pr_w ) ){
454 21 : ulong delta = new_pr_w-old_pr_w;
455 21 : tree_add_weight( pr, height, internal_cnt, ci_idx, delta );
456 21 : sampler->pr_total_weight += delta;
457 27 : } else if( FD_LIKELY( new_pr_w<old_pr_w ) ) {
458 21 : ulong delta = old_pr_w-new_pr_w;
459 21 : tree_sub_weight( pr, height, internal_cnt, ci_idx, delta );
460 21 : sampler->pr_total_weight -= delta;
461 21 : }
462 :
463 : /* Update bucket trees. Only update buckets where the peer currently
464 : has weight (may have been sample-removed from individual buckets). */
465 1248 : for( ulong b=0UL; b<BUCKET_CNT; b++ ) {
466 1200 : tree_ele_t * bt = sampler->trees + (1UL+b)*internal_cnt;
467 1200 : if( FD_UNLIKELY( sampler->is_removed[ ci_idx ][ b ] ) ) continue; /* Peer is currently sample-removed from this bucket, so has no weight to update. */
468 :
469 1200 : ulong old_bw = fd_ulong_if( old_active, adjusted_bucket_weight( old_stake, b, old_fresh ), 0UL );
470 1200 : if( FD_UNLIKELY( old_is_me ) ) old_bw = 0UL;
471 1200 : ulong new_bw = fd_ulong_if( new_active, adjusted_bucket_weight( sampler->stakes[ ci_idx ], b, is_fresh ), 0UL );
472 1200 : if( FD_UNLIKELY( sampler->self_ci_idx==ci_idx ) ) new_bw = 0UL;
473 :
474 1200 : if( FD_LIKELY( new_bw>old_bw ) ) {
475 465 : ulong delta = new_bw-old_bw;
476 465 : tree_add_weight( bt, height, internal_cnt, ci_idx, delta );
477 465 : sampler->bucket_total_weight[ b ] += delta;
478 735 : } else if( FD_LIKELY( new_bw < old_bw ) ) {
479 516 : ulong delta = old_bw-new_bw;
480 516 : tree_sub_weight( bt, height, internal_cnt, ci_idx, delta );
481 516 : sampler->bucket_total_weight[ b ] -= delta;
482 516 : }
483 1200 : }
484 48 : }
485 :
486 : void
487 : fd_gossip_wsample_stake( fd_gossip_wsample_t * sampler,
488 : ulong ci_idx,
489 9 : ulong new_stake ) {
490 9 : FD_TEST( sampler->exists[ ci_idx ] );
491 :
492 9 : if( FD_UNLIKELY( sampler->stakes[ ci_idx ]==new_stake ) ) return;
493 9 : ulong old_stake = sampler->stakes[ ci_idx ];
494 9 : sampler->stakes[ ci_idx ] = new_stake;
495 9 : recompute( sampler, ci_idx, old_stake, sampler->fresh[ ci_idx ], sampler->ping_tracked[ ci_idx ], sampler->self_ci_idx==ci_idx );
496 9 : }
497 :
498 : void
499 : fd_gossip_wsample_fresh( fd_gossip_wsample_t * sampler,
500 : ulong ci_idx,
501 24 : int fresh ) {
502 24 : FD_TEST( sampler->exists[ ci_idx ] );
503 :
504 24 : if( FD_UNLIKELY( sampler->fresh[ ci_idx ]==fresh ) ) return;
505 24 : sampler->fresh[ ci_idx ] = fresh;
506 24 : recompute( sampler, ci_idx, sampler->stakes[ ci_idx ], !fresh, sampler->ping_tracked[ ci_idx ], sampler->self_ci_idx==ci_idx );
507 24 : }
508 :
509 : void
510 : fd_gossip_wsample_ping_tracked( fd_gossip_wsample_t * sampler,
511 : ulong ci_idx,
512 15 : int ping_tracked ) {
513 15 : FD_TEST( sampler->exists[ ci_idx ] );
514 :
515 15 : if( FD_UNLIKELY( sampler->ping_tracked[ ci_idx ]==ping_tracked ) ) return;
516 15 : sampler->ping_tracked[ ci_idx ] = ping_tracked;
517 15 : recompute( sampler, ci_idx, sampler->stakes[ ci_idx ], sampler->fresh[ ci_idx ], !ping_tracked, sampler->self_ci_idx==ci_idx );
518 15 : }
519 :
520 : void
521 : fd_gossip_wsample_is_me( fd_gossip_wsample_t * sampler,
522 : ulong ci_idx,
523 0 : int is_me ) {
524 0 : FD_TEST( sampler->exists[ ci_idx ] );
525 0 : if( FD_LIKELY( !is_me ) ) {
526 0 : FD_TEST( sampler->self_ci_idx!=ci_idx );
527 0 : return;
528 0 : }
529 :
530 0 : FD_TEST( sampler->self_ci_idx==ci_idx || sampler->self_ci_idx==ULONG_MAX );
531 0 : if( FD_LIKELY( sampler->self_ci_idx==ci_idx ) ) return;
532 0 : sampler->self_ci_idx = ci_idx;
533 0 : recompute( sampler, ci_idx, sampler->stakes[ ci_idx ], sampler->fresh[ ci_idx ], sampler->ping_tracked[ ci_idx ], 0 );
534 0 : }
535 :
536 : void
537 : fd_gossip_wsample_set_identity( fd_gossip_wsample_t * sampler,
538 0 : ulong ci_idx ) {
539 0 : FD_TEST( sampler->self_ci_idx==ULONG_MAX || sampler->exists[ sampler->self_ci_idx ] );
540 0 : FD_TEST( ci_idx==ULONG_MAX || sampler->exists[ ci_idx ] );
541 0 : if( FD_UNLIKELY( sampler->self_ci_idx==ci_idx ) ) return;
542 :
543 0 : ulong old_ci_idx = sampler->self_ci_idx;
544 0 : sampler->self_ci_idx = ci_idx;
545 :
546 0 : if( FD_LIKELY( old_ci_idx!=ULONG_MAX ) ) {
547 0 : recompute( sampler, old_ci_idx, sampler->stakes[ old_ci_idx ], sampler->fresh[ old_ci_idx ], sampler->ping_tracked[ old_ci_idx ], 1 );
548 0 : }
549 :
550 0 : if( FD_LIKELY( ci_idx!=ULONG_MAX ) ) {
551 0 : recompute( sampler, ci_idx, sampler->stakes[ ci_idx ], sampler->fresh[ ci_idx ], sampler->ping_tracked[ ci_idx ], 0 );
552 0 : }
553 0 : }
554 :
555 : void
556 : fd_gossip_wsample_self_stake( fd_gossip_wsample_t * sampler,
557 21 : ulong self_stake ) {
558 21 : if( FD_UNLIKELY( sampler->self_stake==self_stake ) ) return;
559 :
560 21 : ulong old_self_stake = sampler->self_stake;
561 21 : sampler->self_stake = self_stake;
562 :
563 21 : ulong height = sampler->height;
564 21 : ulong internal_cnt = sampler->internal_cnt;
565 21 : tree_ele_t * pr = sampler->trees + PR_TREE_IDX*internal_cnt;
566 21 : ulong * stakes = sampler->stakes;
567 21 : int * fresh_flags = sampler->fresh;
568 :
569 357 : for( ulong i=0UL; i<sampler->max_peers; i++ ) {
570 336 : if( FD_UNLIKELY( !sampler->exists[ i ] ) ) continue;
571 :
572 12 : int active = is_active( stakes[ i ], sampler->ping_tracked[ i ] );
573 12 : ulong old_w = fd_ulong_if( active, adjusted_pr_weight( stakes[ i ], old_self_stake, fresh_flags[ i ] ), 0UL );
574 12 : if( FD_UNLIKELY( sampler->self_ci_idx==i ) ) old_w = 0UL;
575 12 : ulong new_w = fd_ulong_if( active, adjusted_pr_weight( stakes[ i ], self_stake, fresh_flags[ i ] ), 0UL );
576 12 : if( FD_UNLIKELY( sampler->self_ci_idx==i ) ) new_w = 0UL;
577 :
578 12 : if( FD_LIKELY( new_w>old_w ) ) {
579 6 : ulong delta = new_w-old_w;
580 6 : tree_add_weight( pr, height, internal_cnt, i, delta );
581 6 : sampler->pr_total_weight += delta;
582 6 : } else if( FD_LIKELY( new_w<old_w ) ) {
583 3 : ulong delta = old_w-new_w;
584 3 : tree_sub_weight( pr, height, internal_cnt, i, delta );
585 3 : sampler->pr_total_weight -= delta;
586 3 : }
587 12 : }
588 21 : }
|
