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 0 : #define R (9UL) /* Radix of the sampling trees. */
18 0 : #define BUCKET_CNT (25UL) /* Number of active-set buckets (stake tiers). */
19 0 : #define TREE_CNT (1UL+BUCKET_CNT) /* Total number of trees: 1 pull-request tree + BUCKET_CNT bucket trees. */
20 0 : #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 0 : pr_weight( ulong stake ) {
34 0 : ulong stake_sol = stake / 1000000000UL;
35 0 : ulong bucket = stake_sol ? ( 64UL - (ulong)__builtin_clzl( stake_sol ) ) : 0UL;
36 0 : ulong w = bucket + 1UL;
37 0 : return w * w;
38 0 : }
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 0 : ulong * out_internal_cnt ) {
76 0 : ulong height = 0UL;
77 0 : ulong internal = 0UL;
78 0 : ulong pow_r = 1UL; /* R^height */
79 0 : while( leaf_cnt>pow_r ) {
80 0 : internal += pow_r;
81 0 : pow_r *= R;
82 0 : height++;
83 0 : }
84 0 : *out_height = height;
85 0 : *out_internal_cnt = internal;
86 0 : }
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 0 : ulong bucket ) {
94 0 : ulong peer_bucket = fd_active_set_stake_bucket( stake );
95 0 : ulong score = fd_ulong_min( bucket, peer_bucket ) + 1UL;
96 0 : return score * score;
97 0 : }
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 0 : int is_fresh ) {
108 0 : ulong full = pr_weight( fd_ulong_min( stake, self_stake ) );
109 0 : if( FD_LIKELY( is_fresh ) ) return full;
110 0 : if( FD_UNLIKELY( !stake ) ) return 0UL;
111 0 : ulong w = full/16UL;
112 0 : return w ? w : 1UL;
113 0 : }
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 0 : int is_fresh ) {
124 0 : ulong full = bucket_score( stake, bucket );
125 0 : if( FD_LIKELY( is_fresh ) ) return full;
126 0 : if( FD_UNLIKELY( !stake ) ) return 0UL;
127 0 : ulong w = full/16UL;
128 0 : return w ? w : 1UL;
129 0 : }
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 0 : ulong delta ) {
140 0 : ulong cursor = leaf_idx + internal_cnt;
141 0 : for( ulong h=0UL; h<height; h++ ) {
142 0 : ulong parent = (cursor-1UL) / R;
143 0 : ulong child_idx = cursor-1UL - R*parent;
144 0 : for( ulong k=0UL; k<R-1UL; k++ ) {
145 0 : tree[ parent ].left_sum[ k ] += (ulong)(((long)(child_idx-k-1UL))>>63) & delta;
146 0 : }
147 0 : cursor = parent;
148 0 : }
149 0 : }
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 0 : ulong delta ) {
160 0 : ulong cursor = leaf_idx + internal_cnt;
161 0 : for( ulong h=0UL; h<height; h++ ) {
162 0 : ulong parent = (cursor-1UL) / R;
163 0 : ulong child_idx = cursor-1UL - R*parent;
164 0 : for( ulong k=0UL; k<R-1UL; k++ ) {
165 0 : tree[ parent ].left_sum[ k ] -= (ulong)(((long)(child_idx-k-1UL))>>63) & delta;
166 0 : }
167 0 : cursor = parent;
168 0 : }
169 0 : }
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 0 : fd_rng_t * rng ) {
182 0 : if( FD_UNLIKELY( !total_weight ) ) {
183 0 : sample_result_t empty = { .idx = ULONG_MAX, .weight = 0UL };
184 0 : return empty;
185 0 : }
186 :
187 0 : ulong query = fd_rng_ulong_roll( rng, total_weight );
188 0 : ulong cursor = 0UL;
189 0 : ulong S = total_weight;
190 :
191 0 : for( ulong h=0UL; h<height; h++ ) {
192 0 : tree_ele_t const * e = tree + cursor;
193 :
194 : /* Branchless child selection: count how many left_sum entries are
195 : <= the query value. */
196 0 : ulong child_idx = 0UL;
197 0 : for( ulong i=0UL; i<R-1UL; i++ ) child_idx += (ulong)( e->left_sum[ i ]<=query );
198 :
199 0 : ulong lm1 = child_idx > 0UL ? e->left_sum[ child_idx-1UL] : 0UL;
200 0 : ulong li = child_idx < R-1UL ? e->left_sum[ child_idx ] : S;
201 :
202 0 : query -= lm1;
203 0 : S = li - lm1;
204 0 : cursor = R*cursor+child_idx+1UL;
205 0 : }
206 :
207 0 : sample_result_t result = { .idx = cursor - internal_cnt, .weight = S };
208 0 : return result;
209 0 : }
210 :
211 : FD_FN_CONST ulong
212 0 : fd_gossip_wsample_align( void ) {
213 0 : return 64UL;
214 0 : }
215 :
216 : FD_FN_CONST ulong
217 0 : fd_gossip_wsample_footprint( ulong max_peers ) {
218 0 : if( FD_UNLIKELY( !max_peers ) ) return 0UL;
219 :
220 0 : ulong height;
221 0 : ulong internal_cnt;
222 0 : compute_height( max_peers, &height, &internal_cnt );
223 0 : (void)height;
224 :
225 0 : ulong l = FD_LAYOUT_INIT;
226 0 : l = FD_LAYOUT_APPEND( l, 64UL, sizeof(struct fd_gossip_wsample_private) );
227 0 : l = FD_LAYOUT_APPEND( l, 8UL, max_peers*sizeof(ulong) ); /* stakes */
228 0 : l = FD_LAYOUT_APPEND( l, 4UL, max_peers*sizeof(int) ); /* exists */
229 0 : l = FD_LAYOUT_APPEND( l, 4UL, max_peers*sizeof(int) ); /* fresh */
230 0 : l = FD_LAYOUT_APPEND( l, 4UL, max_peers*sizeof(int) ); /* ping_tracked */
231 0 : l = FD_LAYOUT_APPEND( l, 8UL, max_peers*sizeof(int *) ); /* is_removed */
232 0 : l = FD_LAYOUT_APPEND( l, 4UL, max_peers*BUCKET_CNT*sizeof(int) ); /* removed */
233 0 : l = FD_LAYOUT_APPEND( l, 64UL, TREE_CNT*internal_cnt*sizeof(tree_ele_t) );
234 0 : return FD_LAYOUT_FINI( l, 64UL );
235 0 : }
236 :
237 : void *
238 : fd_gossip_wsample_new( void * shmem,
239 : fd_rng_t * rng,
240 0 : ulong max_peers ) {
241 0 : if( FD_UNLIKELY( !shmem ) ) return NULL;
242 0 : if( FD_UNLIKELY( !rng ) ) return NULL;
243 0 : if( FD_UNLIKELY( !max_peers ) ) return NULL;
244 0 : if( FD_UNLIKELY( !fd_ulong_is_aligned( (ulong)shmem, fd_gossip_wsample_align() ) ) ) return NULL;
245 :
246 0 : ulong height;
247 0 : ulong internal_cnt;
248 0 : compute_height( max_peers, &height, &internal_cnt );
249 :
250 0 : fd_gossip_wsample_t * s = (fd_gossip_wsample_t *)shmem;
251 :
252 0 : s->rng = rng;
253 0 : s->max_peers = max_peers;
254 0 : s->internal_cnt = internal_cnt;
255 0 : s->height = height;
256 :
257 : /* Compute trailing-array pointers. */
258 0 : FD_SCRATCH_ALLOC_INIT( l, shmem );
259 0 : /* */ FD_SCRATCH_ALLOC_APPEND( l, 64UL, sizeof(struct fd_gossip_wsample_private) );
260 0 : s->stakes = FD_SCRATCH_ALLOC_APPEND( l, alignof(ulong), max_peers*sizeof(ulong) );
261 0 : s->exists = FD_SCRATCH_ALLOC_APPEND( l, alignof(int), max_peers*sizeof(int) );
262 0 : s->fresh = FD_SCRATCH_ALLOC_APPEND( l, alignof(int), max_peers*sizeof(int) );
263 0 : s->ping_tracked = FD_SCRATCH_ALLOC_APPEND( l, alignof(int), max_peers*sizeof(int) );
264 0 : s->is_removed = FD_SCRATCH_ALLOC_APPEND( l, alignof(int *), max_peers*sizeof(int *) );
265 0 : int * is_removed = FD_SCRATCH_ALLOC_APPEND( l, alignof(int), max_peers*BUCKET_CNT*sizeof(int) );
266 0 : 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 0 : fd_memset( s->stakes, 0, max_peers * sizeof(ulong) );
270 0 : fd_memset( s->exists, 0, max_peers * sizeof(int) );
271 0 : fd_memset( s->fresh, 0, max_peers * sizeof(int) );
272 0 : fd_memset( s->ping_tracked, 0, max_peers * sizeof(int) );
273 0 : fd_memset( is_removed, 0, max_peers * BUCKET_CNT*sizeof(int) );
274 0 : 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 0 : s->self_stake = 0UL;
278 0 : s->self_ci_idx = ULONG_MAX;
279 0 : s->pr_total_weight = 0UL;
280 0 : for( ulong b=0UL; b<BUCKET_CNT; b++ ) s->bucket_total_weight[ b ] = 0UL;
281 :
282 0 : for( ulong i=0UL; i<max_peers; i++ ) s->is_removed[ i ] = is_removed + i*BUCKET_CNT;
283 :
284 0 : return shmem;
285 0 : }
286 :
287 : fd_gossip_wsample_t *
288 0 : fd_gossip_wsample_join( void * shwsample ) {
289 0 : return (fd_gossip_wsample_t *)shwsample;
290 0 : }
291 :
292 : static inline int
293 : is_active( ulong stake,
294 0 : int ping_tracked ) {
295 : /* 1. If the node has more than FD_GOSSIP_STAKED_THRESHOLD lamports
296 : staked, it is active */
297 0 : 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 0 : if( FD_UNLIKELY( ping_tracked ) ) return 1;
301 :
302 0 : return 0;
303 0 : }
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 0 : int is_me ) {
311 0 : FD_TEST( !sampler->exists[ ci_idx ] );
312 :
313 0 : sampler->exists[ ci_idx ] = 1;
314 0 : sampler->stakes[ ci_idx ] = stake;
315 0 : sampler->fresh[ ci_idx ] = 1; /* newly added peers are fresh */
316 0 : sampler->ping_tracked[ ci_idx ] = ping_tracked;
317 0 : fd_memset( sampler->is_removed[ ci_idx ], 0, BUCKET_CNT*sizeof(int) );
318 :
319 0 : 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 0 : ulong height = sampler->height;
326 0 : 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 0 : 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 0 : ulong pr_w = pr_weight( fd_ulong_min( stake, sampler->self_stake ) );
335 0 : tree_add_weight( sampler->trees+PR_TREE_IDX*internal_cnt, height, internal_cnt, ci_idx, pr_w );
336 0 : sampler->pr_total_weight += pr_w;
337 :
338 : /* Bucket trees. */
339 0 : for( ulong b=0UL; b<BUCKET_CNT; b++ ) {
340 0 : ulong bw = adjusted_bucket_weight( stake, b, 1 /* is_fresh */ );
341 0 : tree_add_weight( sampler->trees+(1UL+b)*internal_cnt, height, internal_cnt, ci_idx, bw );
342 0 : sampler->bucket_total_weight[ b ] += bw;
343 0 : }
344 0 : }
345 0 : }
346 :
347 : void
348 : fd_gossip_wsample_remove( fd_gossip_wsample_t * sampler,
349 0 : ulong ci_idx ) {
350 0 : FD_TEST( sampler->exists[ ci_idx ] );
351 :
352 0 : sampler->exists[ ci_idx ] = 0;
353 0 : if( FD_UNLIKELY( sampler->self_ci_idx==ci_idx ) ) {
354 0 : sampler->self_ci_idx = ULONG_MAX;
355 0 : return;
356 0 : }
357 :
358 0 : int active = is_active( sampler->stakes[ ci_idx ], sampler->ping_tracked[ ci_idx ] );
359 0 : if( FD_UNLIKELY( !active ) ) return;
360 :
361 0 : ulong height = sampler->height;
362 0 : ulong internal_cnt = sampler->internal_cnt;
363 :
364 0 : ulong pr_w = adjusted_pr_weight( sampler->stakes[ ci_idx ], sampler->self_stake, sampler->fresh[ ci_idx ] );
365 0 : tree_sub_weight( sampler->trees+PR_TREE_IDX*internal_cnt, height, internal_cnt, ci_idx, pr_w );
366 0 : sampler->pr_total_weight -= pr_w;
367 :
368 0 : for( ulong b=0UL; b<BUCKET_CNT; b++ ) {
369 0 : 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 0 : ulong bw = adjusted_bucket_weight( sampler->stakes[ ci_idx ], b, sampler->fresh[ ci_idx ] );
372 0 : tree_sub_weight( sampler->trees+(1UL+b)*internal_cnt, height, internal_cnt, ci_idx, bw );
373 0 : sampler->bucket_total_weight[ b ] -= bw;
374 0 : }
375 0 : }
376 :
377 : ulong
378 0 : fd_gossip_wsample_sample_pull_request( fd_gossip_wsample_t * sampler ) {
379 0 : sample_result_t r = tree_sample( sampler->trees + PR_TREE_IDX*sampler->internal_cnt,
380 0 : sampler->height,
381 0 : sampler->internal_cnt,
382 0 : sampler->pr_total_weight,
383 0 : sampler->rng );
384 0 : return r.idx;
385 0 : }
386 :
387 : ulong
388 : fd_gossip_wsample_sample_remove_bucket( fd_gossip_wsample_t * sampler,
389 0 : ulong bucket ) {
390 0 : tree_ele_t * bt = sampler->trees + (1UL+bucket)*sampler->internal_cnt;
391 :
392 0 : sample_result_t r = tree_sample( bt,
393 0 : sampler->height,
394 0 : sampler->internal_cnt,
395 0 : sampler->bucket_total_weight[bucket],
396 0 : sampler->rng );
397 0 : 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 0 : FD_TEST( sampler->exists[ r.idx ] );
402 0 : int active = is_active( sampler->stakes[ r.idx ], sampler->ping_tracked[ r.idx ] );
403 0 : ulong weight = fd_ulong_if( active, adjusted_bucket_weight( sampler->stakes[ r.idx ], bucket, sampler->fresh[ r.idx ] ), 0UL );
404 0 : FD_TEST( r.weight==weight );
405 0 : FD_TEST( !sampler->is_removed[ r.idx ][ bucket ] );
406 0 : FD_TEST( sampler->self_ci_idx!=r.idx );
407 0 : tree_sub_weight( bt, sampler->height, sampler->internal_cnt, r.idx, r.weight );
408 0 : sampler->bucket_total_weight[ bucket ] -= r.weight;
409 0 : sampler->is_removed[ r.idx ][ bucket ] = 1;
410 :
411 0 : return r.idx;
412 0 : }
413 :
414 : void
415 : fd_gossip_wsample_add_bucket( fd_gossip_wsample_t * sampler,
416 : ulong bucket,
417 0 : ulong ci_idx ) {
418 0 : FD_TEST( sampler->exists[ ci_idx ] );
419 0 : FD_TEST( sampler->is_removed[ ci_idx ][ bucket ] );
420 0 : FD_TEST( sampler->self_ci_idx!=ci_idx );
421 :
422 0 : ulong stake = sampler->stakes[ ci_idx ];
423 0 : int is_fresh = sampler->fresh[ ci_idx ];
424 0 : int active = is_active( stake, sampler->ping_tracked[ ci_idx ] );
425 0 : ulong bw = fd_ulong_if( active, adjusted_bucket_weight( stake, bucket, is_fresh ), 0UL );
426 :
427 0 : tree_add_weight( sampler->trees + (1UL+bucket)*sampler->internal_cnt, sampler->height, sampler->internal_cnt, ci_idx, bw );
428 0 : sampler->bucket_total_weight[ bucket ] += bw;
429 0 : sampler->is_removed[ ci_idx ][ bucket ] = 0;
430 0 : }
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 0 : int old_is_me ) {
439 0 : FD_TEST( sampler->exists[ ci_idx ] );
440 :
441 0 : int old_active = is_active( old_stake, old_ping_tracked );
442 0 : int new_active = is_active( sampler->stakes[ ci_idx ], sampler->ping_tracked[ ci_idx ] );
443 :
444 0 : int is_fresh = sampler->fresh[ ci_idx ];
445 0 : ulong height = sampler->height;
446 0 : ulong internal_cnt = sampler->internal_cnt;
447 :
448 : /* Update pull-request tree weight. */
449 0 : tree_ele_t * pr = sampler->trees + PR_TREE_IDX*internal_cnt;
450 0 : ulong old_pr_w = fd_ulong_if( old_active, adjusted_pr_weight( old_stake, sampler->self_stake, old_fresh ), 0UL );
451 0 : if( FD_UNLIKELY( old_is_me ) ) old_pr_w = 0UL;
452 0 : ulong new_pr_w = fd_ulong_if( new_active, adjusted_pr_weight( sampler->stakes[ ci_idx ], sampler->self_stake, is_fresh ), 0UL );
453 0 : if( FD_UNLIKELY( sampler->self_ci_idx==ci_idx ) ) new_pr_w = 0UL;
454 :
455 0 : if( FD_LIKELY( new_pr_w>old_pr_w ) ){
456 0 : ulong delta = new_pr_w-old_pr_w;
457 0 : tree_add_weight( pr, height, internal_cnt, ci_idx, delta );
458 0 : sampler->pr_total_weight += delta;
459 0 : } else if( FD_LIKELY( new_pr_w<old_pr_w ) ) {
460 0 : ulong delta = old_pr_w-new_pr_w;
461 0 : tree_sub_weight( pr, height, internal_cnt, ci_idx, delta );
462 0 : sampler->pr_total_weight -= delta;
463 0 : }
464 :
465 : /* Update bucket trees. Only update buckets where the peer currently
466 : has weight (may have been sample-removed from individual buckets). */
467 0 : for( ulong b=0UL; b<BUCKET_CNT; b++ ) {
468 0 : tree_ele_t * bt = sampler->trees + (1UL+b)*internal_cnt;
469 0 : 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 0 : ulong old_bw = fd_ulong_if( old_active, adjusted_bucket_weight( old_stake, b, old_fresh ), 0UL );
472 0 : if( FD_UNLIKELY( old_is_me ) ) old_bw = 0UL;
473 0 : ulong new_bw = fd_ulong_if( new_active, adjusted_bucket_weight( sampler->stakes[ ci_idx ], b, is_fresh ), 0UL );
474 0 : if( FD_UNLIKELY( sampler->self_ci_idx==ci_idx ) ) new_bw = 0UL;
475 :
476 0 : if( FD_LIKELY( new_bw>old_bw ) ) {
477 0 : ulong delta = new_bw-old_bw;
478 0 : tree_add_weight( bt, height, internal_cnt, ci_idx, delta );
479 0 : sampler->bucket_total_weight[ b ] += delta;
480 0 : } else if( FD_LIKELY( new_bw < old_bw ) ) {
481 0 : ulong delta = old_bw-new_bw;
482 0 : tree_sub_weight( bt, height, internal_cnt, ci_idx, delta );
483 0 : sampler->bucket_total_weight[ b ] -= delta;
484 0 : }
485 0 : }
486 0 : }
487 :
488 : void
489 : fd_gossip_wsample_stake( fd_gossip_wsample_t * sampler,
490 : ulong ci_idx,
491 0 : ulong new_stake ) {
492 0 : FD_TEST( sampler->exists[ ci_idx ] );
493 :
494 0 : if( FD_UNLIKELY( sampler->stakes[ ci_idx ]==new_stake ) ) return;
495 0 : ulong old_stake = sampler->stakes[ ci_idx ];
496 0 : sampler->stakes[ ci_idx ] = new_stake;
497 0 : recompute( sampler, ci_idx, old_stake, sampler->fresh[ ci_idx ], sampler->ping_tracked[ ci_idx ], sampler->self_ci_idx==ci_idx );
498 0 : }
499 :
500 : void
501 : fd_gossip_wsample_fresh( fd_gossip_wsample_t * sampler,
502 : ulong ci_idx,
503 0 : int fresh ) {
504 0 : FD_TEST( sampler->exists[ ci_idx ] );
505 :
506 0 : if( FD_UNLIKELY( sampler->fresh[ ci_idx ]==fresh ) ) return;
507 0 : sampler->fresh[ ci_idx ] = fresh;
508 0 : recompute( sampler, ci_idx, sampler->stakes[ ci_idx ], !fresh, sampler->ping_tracked[ ci_idx ], sampler->self_ci_idx==ci_idx );
509 0 : }
510 :
511 : void
512 : fd_gossip_wsample_ping_tracked( fd_gossip_wsample_t * sampler,
513 : ulong ci_idx,
514 0 : int ping_tracked ) {
515 0 : FD_TEST( sampler->exists[ ci_idx ] );
516 :
517 0 : if( FD_UNLIKELY( sampler->ping_tracked[ ci_idx ]==ping_tracked ) ) return;
518 0 : sampler->ping_tracked[ ci_idx ] = ping_tracked;
519 0 : recompute( sampler, ci_idx, sampler->stakes[ ci_idx ], sampler->fresh[ ci_idx ], !ping_tracked, sampler->self_ci_idx==ci_idx );
520 0 : }
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 0 : ulong self_stake ) {
560 0 : if( FD_UNLIKELY( sampler->self_stake==self_stake ) ) return;
561 :
562 0 : ulong old_self_stake = sampler->self_stake;
563 0 : sampler->self_stake = self_stake;
564 :
565 0 : ulong height = sampler->height;
566 0 : ulong internal_cnt = sampler->internal_cnt;
567 0 : tree_ele_t * pr = sampler->trees + PR_TREE_IDX*internal_cnt;
568 0 : ulong * stakes = sampler->stakes;
569 0 : int * fresh_flags = sampler->fresh;
570 :
571 0 : for( ulong i=0UL; i<sampler->max_peers; i++ ) {
572 0 : if( FD_UNLIKELY( !sampler->exists[ i ] ) ) continue;
573 :
574 0 : int active = is_active( stakes[ i ], sampler->ping_tracked[ i ] );
575 0 : ulong old_w = fd_ulong_if( active, adjusted_pr_weight( stakes[ i ], old_self_stake, fresh_flags[ i ] ), 0UL );
576 0 : if( FD_UNLIKELY( sampler->self_ci_idx==i ) ) old_w = 0UL;
577 0 : ulong new_w = fd_ulong_if( active, adjusted_pr_weight( stakes[ i ], self_stake, fresh_flags[ i ] ), 0UL );
578 0 : if( FD_UNLIKELY( sampler->self_ci_idx==i ) ) new_w = 0UL;
579 :
580 0 : if( FD_LIKELY( new_w>old_w ) ) {
581 0 : ulong delta = new_w-old_w;
582 0 : tree_add_weight( pr, height, internal_cnt, i, delta );
583 0 : sampler->pr_total_weight += delta;
584 0 : } else if( FD_LIKELY( new_w<old_w ) ) {
585 0 : ulong delta = old_w-new_w;
586 0 : tree_sub_weight( pr, height, internal_cnt, i, delta );
587 0 : sampler->pr_total_weight -= delta;
588 0 : }
589 0 : }
590 0 : }
|
