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 0 : #define R (9UL) /* Radix of the sampling trees. */
17 0 : #define BUCKET_CNT (25UL) /* Number of active-set buckets (stake tiers). */
18 0 : #define TREE_CNT (1UL+BUCKET_CNT) /* Total number of trees: 1 pull-request tree + BUCKET_CNT bucket trees. */
19 0 : #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 0 : pr_weight( ulong stake ) {
33 0 : ulong stake_sol = stake / 1000000000UL;
34 0 : ulong bucket = stake_sol ? ( 64UL - (ulong)__builtin_clzl( stake_sol ) ) : 0UL;
35 0 : ulong w = bucket + 1UL;
36 0 : return w * w;
37 0 : }
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_entrypoint; /* per-peer is-entrypoint 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, 4UL, max_peers*sizeof(int) ); /* is_entrypoint */
232 0 : l = FD_LAYOUT_APPEND( l, 8UL, max_peers*sizeof(int *) ); /* is_removed */
233 0 : l = FD_LAYOUT_APPEND( l, 4UL, max_peers*BUCKET_CNT*sizeof(int) ); /* removed */
234 0 : l = FD_LAYOUT_APPEND( l, 64UL, TREE_CNT*internal_cnt*sizeof(tree_ele_t) );
235 0 : return FD_LAYOUT_FINI( l, 64UL );
236 0 : }
237 :
238 : void *
239 : fd_gossip_wsample_new( void * shmem,
240 : fd_rng_t * rng,
241 0 : ulong max_peers ) {
242 0 : if( FD_UNLIKELY( !shmem ) ) return NULL;
243 0 : if( FD_UNLIKELY( !rng ) ) return NULL;
244 0 : if( FD_UNLIKELY( !max_peers ) ) return NULL;
245 0 : if( FD_UNLIKELY( !fd_ulong_is_aligned( (ulong)shmem, fd_gossip_wsample_align() ) ) ) return NULL;
246 :
247 0 : ulong height;
248 0 : ulong internal_cnt;
249 0 : compute_height( max_peers, &height, &internal_cnt );
250 :
251 0 : fd_gossip_wsample_t * s = (fd_gossip_wsample_t *)shmem;
252 :
253 0 : s->rng = rng;
254 0 : s->max_peers = max_peers;
255 0 : s->internal_cnt = internal_cnt;
256 0 : s->height = height;
257 :
258 : /* Compute trailing-array pointers. */
259 0 : FD_SCRATCH_ALLOC_INIT( l, shmem );
260 0 : /* */ FD_SCRATCH_ALLOC_APPEND( l, 64UL, sizeof(struct fd_gossip_wsample_private) );
261 0 : s->stakes = FD_SCRATCH_ALLOC_APPEND( l, alignof(ulong), max_peers*sizeof(ulong) );
262 0 : s->exists = FD_SCRATCH_ALLOC_APPEND( l, alignof(int), max_peers*sizeof(int) );
263 0 : s->fresh = FD_SCRATCH_ALLOC_APPEND( l, alignof(int), max_peers*sizeof(int) );
264 0 : s->ping_tracked = FD_SCRATCH_ALLOC_APPEND( l, alignof(int), max_peers*sizeof(int) );
265 0 : s->is_entrypoint = FD_SCRATCH_ALLOC_APPEND( l, alignof(int), max_peers*sizeof(int) );
266 0 : s->is_removed = FD_SCRATCH_ALLOC_APPEND( l, alignof(int *), max_peers*sizeof(int *) );
267 0 : int * is_removed = FD_SCRATCH_ALLOC_APPEND( l, alignof(int), max_peers*BUCKET_CNT*sizeof(int) );
268 0 : s->trees = FD_SCRATCH_ALLOC_APPEND( l, 64UL, TREE_CNT*internal_cnt*sizeof(tree_ele_t) );
269 :
270 : /* Zero-initialize stakes, fresh flags, and trees. */
271 0 : fd_memset( s->stakes, 0, max_peers * sizeof(ulong) );
272 0 : fd_memset( s->exists, 0, max_peers * sizeof(int) );
273 0 : fd_memset( s->fresh, 0, max_peers * sizeof(int) );
274 0 : fd_memset( s->ping_tracked, 0, max_peers * sizeof(int) );
275 0 : fd_memset( s->is_entrypoint, 0, max_peers * sizeof(int) );
276 0 : fd_memset( is_removed, 0, max_peers * BUCKET_CNT*sizeof(int) );
277 0 : if( FD_LIKELY( internal_cnt ) ) fd_memset( s->trees, 0, TREE_CNT*internal_cnt*sizeof(tree_ele_t) );
278 :
279 : /* Zero-initialize total weights and self stake. */
280 0 : s->self_stake = 0UL;
281 0 : s->self_ci_idx = ULONG_MAX;
282 0 : s->pr_total_weight = 0UL;
283 0 : for( ulong b=0UL; b<BUCKET_CNT; b++ ) s->bucket_total_weight[ b ] = 0UL;
284 :
285 0 : for( ulong i=0UL; i<max_peers; i++ ) s->is_removed[ i ] = is_removed + i*BUCKET_CNT;
286 :
287 0 : return shmem;
288 0 : }
289 :
290 : fd_gossip_wsample_t *
291 0 : fd_gossip_wsample_join( void * shwsample ) {
292 0 : return (fd_gossip_wsample_t *)shwsample;
293 0 : }
294 :
295 : static inline int
296 : is_active( ulong stake,
297 : int ping_tracked,
298 0 : int is_entrypoint ) {
299 : /* 1. If the node is an entrypoint, it is active */
300 0 : if( FD_UNLIKELY( is_entrypoint ) ) return 1;
301 :
302 : /* 2. If the node has more than 1 sol staked, it is active */
303 0 : if( FD_UNLIKELY( stake>=1000000000UL ) ) return 1;
304 :
305 : /* 3. If the node has actively ponged a ping, it is active */
306 0 : if( FD_UNLIKELY( ping_tracked ) ) return 1;
307 :
308 0 : return 0;
309 0 : }
310 :
311 : void
312 : fd_gossip_wsample_add( fd_gossip_wsample_t * sampler,
313 : ulong ci_idx,
314 : ulong stake,
315 : int ping_tracked,
316 : int is_entrypoint,
317 0 : int is_me ) {
318 0 : FD_TEST( !sampler->exists[ ci_idx ] );
319 :
320 0 : sampler->exists[ ci_idx ] = 1;
321 0 : sampler->stakes[ ci_idx ] = stake;
322 0 : sampler->fresh[ ci_idx ] = 1; /* newly added peers are fresh */
323 0 : sampler->ping_tracked[ ci_idx ] = ping_tracked;
324 0 : sampler->is_entrypoint[ ci_idx ] = is_entrypoint;
325 0 : fd_memset( sampler->is_removed[ ci_idx ], 0, BUCKET_CNT*sizeof(int) );
326 :
327 0 : if( FD_UNLIKELY( is_me ) ) {
328 0 : FD_TEST( sampler->self_ci_idx==ULONG_MAX );
329 0 : sampler->self_ci_idx = ci_idx;
330 0 : return;
331 0 : }
332 :
333 0 : ulong height = sampler->height;
334 0 : ulong internal_cnt = sampler->internal_cnt;
335 :
336 : /* Only active peers get weight in any sampler tree. Inactive
337 : peers (e.g. un-pinged, or our own identity) are tracked by stake
338 : but remain unsampleable until they become active. */
339 0 : if( FD_LIKELY( is_active( stake, ping_tracked, is_entrypoint ) ) ) {
340 : /* Pull-request tree: log-squared weight matching Agave, with the
341 : peer's stake capped at our own stake. */
342 0 : ulong pr_w = pr_weight( fd_ulong_min( stake, sampler->self_stake ) );
343 0 : tree_add_weight( sampler->trees+PR_TREE_IDX*internal_cnt, height, internal_cnt, ci_idx, pr_w );
344 0 : sampler->pr_total_weight += pr_w;
345 :
346 : /* Bucket trees. */
347 0 : for( ulong b=0UL; b<BUCKET_CNT; b++ ) {
348 0 : ulong bw = adjusted_bucket_weight( stake, b, 1 /* is_fresh */ );
349 0 : tree_add_weight( sampler->trees+(1UL+b)*internal_cnt, height, internal_cnt, ci_idx, bw );
350 0 : sampler->bucket_total_weight[ b ] += bw;
351 0 : }
352 0 : }
353 0 : }
354 :
355 : void
356 : fd_gossip_wsample_remove( fd_gossip_wsample_t * sampler,
357 0 : ulong ci_idx ) {
358 0 : FD_TEST( sampler->exists[ ci_idx ] );
359 :
360 0 : sampler->exists[ ci_idx ] = 0;
361 0 : if( FD_UNLIKELY( sampler->self_ci_idx==ci_idx ) ) {
362 0 : sampler->self_ci_idx = ULONG_MAX;
363 0 : return;
364 0 : }
365 :
366 0 : int active = is_active( sampler->stakes[ ci_idx ], sampler->ping_tracked[ ci_idx ], sampler->is_entrypoint[ ci_idx ] );
367 0 : if( FD_UNLIKELY( !active ) ) return;
368 :
369 0 : ulong height = sampler->height;
370 0 : ulong internal_cnt = sampler->internal_cnt;
371 :
372 0 : ulong pr_w = adjusted_pr_weight( sampler->stakes[ ci_idx ], sampler->self_stake, sampler->fresh[ ci_idx ] );
373 0 : tree_sub_weight( sampler->trees+PR_TREE_IDX*internal_cnt, height, internal_cnt, ci_idx, pr_w );
374 0 : sampler->pr_total_weight -= pr_w;
375 :
376 0 : for( ulong b=0UL; b<BUCKET_CNT; b++ ) {
377 0 : if( FD_UNLIKELY( sampler->is_removed[ ci_idx ][ b ] ) ) continue; /* Peer was already sample-removed from this bucket, so no weight to remove. */
378 :
379 0 : ulong bw = adjusted_bucket_weight( sampler->stakes[ ci_idx ], b, sampler->fresh[ ci_idx ] );
380 0 : tree_sub_weight( sampler->trees+(1UL+b)*internal_cnt, height, internal_cnt, ci_idx, bw );
381 0 : sampler->bucket_total_weight[ b ] -= bw;
382 0 : }
383 0 : }
384 :
385 : ulong
386 0 : fd_gossip_wsample_sample_pull_request( fd_gossip_wsample_t * sampler ) {
387 0 : sample_result_t r = tree_sample( sampler->trees + PR_TREE_IDX*sampler->internal_cnt,
388 0 : sampler->height,
389 0 : sampler->internal_cnt,
390 0 : sampler->pr_total_weight,
391 0 : sampler->rng );
392 0 : return r.idx;
393 0 : }
394 :
395 : ulong
396 : fd_gossip_wsample_sample_remove_bucket( fd_gossip_wsample_t * sampler,
397 0 : ulong bucket ) {
398 0 : tree_ele_t * bt = sampler->trees + (1UL+bucket)*sampler->internal_cnt;
399 :
400 0 : sample_result_t r = tree_sample( bt,
401 0 : sampler->height,
402 0 : sampler->internal_cnt,
403 0 : sampler->bucket_total_weight[bucket],
404 0 : sampler->rng );
405 0 : if( FD_UNLIKELY( r.idx==ULONG_MAX ) ) return ULONG_MAX;
406 :
407 : /* Remove the sampled peer from this bucket tree so it cannot be
408 : sampled again until re-added with fd_gossip_wsample_add_bucket. */
409 0 : FD_TEST( sampler->exists[ r.idx ] );
410 0 : int active = is_active( sampler->stakes[ r.idx ], sampler->ping_tracked[ r.idx ], sampler->is_entrypoint[ r.idx ] );
411 0 : ulong weight = fd_ulong_if( active, adjusted_bucket_weight( sampler->stakes[ r.idx ], bucket, sampler->fresh[ r.idx ] ), 0UL );
412 0 : FD_TEST( r.weight==weight );
413 0 : FD_TEST( !sampler->is_removed[ r.idx ][ bucket ] );
414 0 : FD_TEST( sampler->self_ci_idx!=r.idx );
415 0 : tree_sub_weight( bt, sampler->height, sampler->internal_cnt, r.idx, r.weight );
416 0 : sampler->bucket_total_weight[ bucket ] -= r.weight;
417 0 : sampler->is_removed[ r.idx ][ bucket ] = 1;
418 :
419 0 : return r.idx;
420 0 : }
421 :
422 : void
423 : fd_gossip_wsample_add_bucket( fd_gossip_wsample_t * sampler,
424 : ulong bucket,
425 0 : ulong ci_idx ) {
426 0 : FD_TEST( sampler->exists[ ci_idx ] );
427 0 : FD_TEST( sampler->is_removed[ ci_idx ][ bucket ] );
428 0 : FD_TEST( sampler->self_ci_idx!=ci_idx );
429 :
430 0 : ulong stake = sampler->stakes[ ci_idx ];
431 0 : int is_fresh = sampler->fresh[ ci_idx ];
432 0 : int active = is_active( stake, sampler->ping_tracked[ ci_idx ], sampler->is_entrypoint[ ci_idx ] );
433 0 : ulong bw = fd_ulong_if( active, adjusted_bucket_weight( stake, bucket, is_fresh ), 0UL );
434 :
435 0 : tree_add_weight( sampler->trees + (1UL+bucket)*sampler->internal_cnt, sampler->height, sampler->internal_cnt, ci_idx, bw );
436 0 : sampler->bucket_total_weight[ bucket ] += bw;
437 0 : sampler->is_removed[ ci_idx ][ bucket ] = 0;
438 0 : }
439 :
440 : static void
441 : recompute( fd_gossip_wsample_t * sampler,
442 : ulong ci_idx,
443 : ulong old_stake,
444 : int old_fresh,
445 : int old_ping_tracked,
446 : int old_is_entrypoint,
447 0 : int old_is_me ) {
448 0 : FD_TEST( sampler->exists[ ci_idx ] );
449 :
450 0 : int old_active = is_active( old_stake, old_ping_tracked, old_is_entrypoint );
451 0 : int new_active = is_active( sampler->stakes[ ci_idx ], sampler->ping_tracked[ ci_idx ], sampler->is_entrypoint[ ci_idx ] );
452 :
453 0 : int is_fresh = sampler->fresh[ ci_idx ];
454 0 : ulong height = sampler->height;
455 0 : ulong internal_cnt = sampler->internal_cnt;
456 :
457 : /* Update pull-request tree weight. */
458 0 : tree_ele_t * pr = sampler->trees + PR_TREE_IDX*internal_cnt;
459 0 : ulong old_pr_w = fd_ulong_if( old_active, adjusted_pr_weight( old_stake, sampler->self_stake, old_fresh ), 0UL );
460 0 : if( FD_UNLIKELY( old_is_me ) ) old_pr_w = 0UL;
461 0 : ulong new_pr_w = fd_ulong_if( new_active, adjusted_pr_weight( sampler->stakes[ ci_idx ], sampler->self_stake, is_fresh ), 0UL );
462 0 : if( FD_UNLIKELY( sampler->self_ci_idx==ci_idx ) ) new_pr_w = 0UL;
463 :
464 0 : if( FD_LIKELY( new_pr_w>old_pr_w ) ){
465 0 : ulong delta = new_pr_w-old_pr_w;
466 0 : tree_add_weight( pr, height, internal_cnt, ci_idx, delta );
467 0 : sampler->pr_total_weight += delta;
468 0 : } else if( FD_LIKELY( new_pr_w<old_pr_w ) ) {
469 0 : ulong delta = old_pr_w-new_pr_w;
470 0 : tree_sub_weight( pr, height, internal_cnt, ci_idx, delta );
471 0 : sampler->pr_total_weight -= delta;
472 0 : }
473 :
474 : /* Update bucket trees. Only update buckets where the peer currently
475 : has weight (may have been sample-removed from individual buckets). */
476 0 : for( ulong b=0UL; b<BUCKET_CNT; b++ ) {
477 0 : tree_ele_t * bt = sampler->trees + (1UL+b)*internal_cnt;
478 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. */
479 :
480 0 : ulong old_bw = fd_ulong_if( old_active, adjusted_bucket_weight( old_stake, b, old_fresh ), 0UL );
481 0 : if( FD_UNLIKELY( old_is_me ) ) old_bw = 0UL;
482 0 : ulong new_bw = fd_ulong_if( new_active, adjusted_bucket_weight( sampler->stakes[ ci_idx ], b, is_fresh ), 0UL );
483 0 : if( FD_UNLIKELY( sampler->self_ci_idx==ci_idx ) ) new_bw = 0UL;
484 :
485 0 : if( FD_LIKELY( new_bw>old_bw ) ) {
486 0 : ulong delta = new_bw-old_bw;
487 0 : tree_add_weight( bt, height, internal_cnt, ci_idx, delta );
488 0 : sampler->bucket_total_weight[ b ] += delta;
489 0 : } else if( FD_LIKELY( new_bw < old_bw ) ) {
490 0 : ulong delta = old_bw-new_bw;
491 0 : tree_sub_weight( bt, height, internal_cnt, ci_idx, delta );
492 0 : sampler->bucket_total_weight[ b ] -= delta;
493 0 : }
494 0 : }
495 0 : }
496 :
497 : void
498 : fd_gossip_wsample_stake( fd_gossip_wsample_t * sampler,
499 : ulong ci_idx,
500 0 : ulong new_stake ) {
501 0 : FD_TEST( sampler->exists[ ci_idx ] );
502 :
503 0 : if( FD_UNLIKELY( sampler->stakes[ ci_idx ]==new_stake ) ) return;
504 0 : ulong old_stake = sampler->stakes[ ci_idx ];
505 0 : sampler->stakes[ ci_idx ] = new_stake;
506 0 : recompute( sampler, ci_idx, old_stake, sampler->fresh[ ci_idx ], sampler->ping_tracked[ ci_idx ], sampler->is_entrypoint[ ci_idx ], sampler->self_ci_idx==ci_idx );
507 0 : }
508 :
509 : void
510 : fd_gossip_wsample_fresh( fd_gossip_wsample_t * sampler,
511 : ulong ci_idx,
512 0 : int fresh ) {
513 0 : FD_TEST( sampler->exists[ ci_idx ] );
514 :
515 0 : if( FD_UNLIKELY( sampler->fresh[ ci_idx ]==fresh ) ) return;
516 0 : sampler->fresh[ ci_idx ] = fresh;
517 0 : recompute( sampler, ci_idx, sampler->stakes[ ci_idx ], !fresh, sampler->ping_tracked[ ci_idx ], sampler->is_entrypoint[ ci_idx ], sampler->self_ci_idx==ci_idx );
518 0 : }
519 :
520 : void
521 : fd_gossip_wsample_ping_tracked( fd_gossip_wsample_t * sampler,
522 : ulong ci_idx,
523 0 : int ping_tracked ) {
524 0 : FD_TEST( sampler->exists[ ci_idx ] );
525 :
526 0 : if( FD_UNLIKELY( sampler->ping_tracked[ ci_idx ]==ping_tracked ) ) return;
527 0 : sampler->ping_tracked[ ci_idx ] = ping_tracked;
528 0 : recompute( sampler, ci_idx, sampler->stakes[ ci_idx ], sampler->fresh[ ci_idx ], !ping_tracked, sampler->is_entrypoint[ ci_idx ], sampler->self_ci_idx==ci_idx );
529 0 : }
530 :
531 : void
532 : fd_gossip_wsample_is_entrypoint( fd_gossip_wsample_t * sampler,
533 : ulong ci_idx,
534 0 : int is_entrypoint ) {
535 0 : FD_TEST( sampler->exists[ ci_idx ] );
536 :
537 0 : if( FD_UNLIKELY( sampler->is_entrypoint[ ci_idx ]==is_entrypoint ) ) return;
538 0 : sampler->is_entrypoint[ ci_idx ] = is_entrypoint;
539 0 : recompute( sampler, ci_idx, sampler->stakes[ ci_idx ], sampler->fresh[ ci_idx ], sampler->ping_tracked[ ci_idx ], !is_entrypoint, sampler->self_ci_idx==ci_idx );
540 0 : }
541 :
542 : void
543 : fd_gossip_wsample_is_me( fd_gossip_wsample_t * sampler,
544 : ulong ci_idx,
545 0 : int is_me ) {
546 0 : FD_TEST( sampler->exists[ ci_idx ] );
547 0 : if( FD_LIKELY( !is_me ) ) {
548 0 : FD_TEST( sampler->self_ci_idx!=ci_idx );
549 0 : return;
550 0 : }
551 :
552 0 : FD_TEST( sampler->self_ci_idx==ci_idx || sampler->self_ci_idx==ULONG_MAX );
553 0 : if( FD_LIKELY( sampler->self_ci_idx==ci_idx ) ) return;
554 0 : sampler->self_ci_idx = ci_idx;
555 0 : recompute( sampler, ci_idx, sampler->stakes[ ci_idx ], sampler->fresh[ ci_idx ], sampler->ping_tracked[ ci_idx ], sampler->is_entrypoint[ ci_idx ], 0 );
556 0 : }
557 :
558 : void
559 : fd_gossip_wsample_set_identity( fd_gossip_wsample_t * sampler,
560 0 : ulong ci_idx ) {
561 0 : FD_TEST( sampler->self_ci_idx==ULONG_MAX || sampler->exists[ sampler->self_ci_idx ] );
562 0 : FD_TEST( ci_idx==ULONG_MAX || sampler->exists[ ci_idx ] );
563 0 : if( FD_UNLIKELY( sampler->self_ci_idx==ci_idx ) ) return;
564 :
565 0 : ulong old_ci_idx = sampler->self_ci_idx;
566 0 : sampler->self_ci_idx = ci_idx;
567 :
568 0 : if( FD_LIKELY( old_ci_idx!=ULONG_MAX ) ) {
569 0 : recompute( sampler, old_ci_idx, sampler->stakes[ old_ci_idx ], sampler->fresh[ old_ci_idx ], sampler->ping_tracked[ old_ci_idx ], sampler->is_entrypoint[ old_ci_idx ], 1 );
570 0 : }
571 :
572 0 : if( FD_LIKELY( ci_idx!=ULONG_MAX ) ) {
573 0 : recompute( sampler, ci_idx, sampler->stakes[ ci_idx ], sampler->fresh[ ci_idx ], sampler->ping_tracked[ ci_idx ], sampler->is_entrypoint[ ci_idx ], 0 );
574 0 : }
575 0 : }
576 :
577 : void
578 : fd_gossip_wsample_self_stake( fd_gossip_wsample_t * sampler,
579 0 : ulong self_stake ) {
580 0 : if( FD_UNLIKELY( sampler->self_stake==self_stake ) ) return;
581 :
582 0 : ulong old_self_stake = sampler->self_stake;
583 0 : sampler->self_stake = self_stake;
584 :
585 0 : ulong height = sampler->height;
586 0 : ulong internal_cnt = sampler->internal_cnt;
587 0 : tree_ele_t * pr = sampler->trees + PR_TREE_IDX*internal_cnt;
588 0 : ulong * stakes = sampler->stakes;
589 0 : int * fresh_flags = sampler->fresh;
590 :
591 0 : for( ulong i=0UL; i<sampler->max_peers; i++ ) {
592 0 : if( FD_UNLIKELY( !sampler->exists[ i ] ) ) continue;
593 :
594 0 : int active = is_active( stakes[ i ], sampler->ping_tracked[ i ], sampler->is_entrypoint[ i ] );
595 0 : ulong old_w = fd_ulong_if( active, adjusted_pr_weight( stakes[ i ], old_self_stake, fresh_flags[ i ] ), 0UL );
596 0 : if( FD_UNLIKELY( sampler->self_ci_idx==i ) ) old_w = 0UL;
597 0 : ulong new_w = fd_ulong_if( active, adjusted_pr_weight( stakes[ i ], self_stake, fresh_flags[ i ] ), 0UL );
598 0 : if( FD_UNLIKELY( sampler->self_ci_idx==i ) ) new_w = 0UL;
599 :
600 0 : if( FD_LIKELY( new_w>old_w ) ) {
601 0 : ulong delta = new_w-old_w;
602 0 : tree_add_weight( pr, height, internal_cnt, i, delta );
603 0 : sampler->pr_total_weight += delta;
604 0 : } else if( FD_LIKELY( new_w<old_w ) ) {
605 0 : ulong delta = old_w-new_w;
606 0 : tree_sub_weight( pr, height, internal_cnt, i, delta );
607 0 : sampler->pr_total_weight -= delta;
608 0 : }
609 0 : }
610 0 : }
|
