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