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_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 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, 4UL, max_peers*sizeof(int) ); /* is_entrypoint */
232 69 : l = FD_LAYOUT_APPEND( l, 8UL, max_peers*sizeof(int *) ); /* is_removed */
233 69 : l = FD_LAYOUT_APPEND( l, 4UL, max_peers*BUCKET_CNT*sizeof(int) ); /* removed */
234 69 : l = FD_LAYOUT_APPEND( l, 64UL, TREE_CNT*internal_cnt*sizeof(tree_ele_t) );
235 69 : return FD_LAYOUT_FINI( l, 64UL );
236 72 : }
237 :
238 : void *
239 : fd_gossip_wsample_new( void * shmem,
240 : fd_rng_t * rng,
241 69 : ulong max_peers ) {
242 69 : if( FD_UNLIKELY( !shmem ) ) return NULL;
243 66 : if( FD_UNLIKELY( !rng ) ) return NULL;
244 66 : if( FD_UNLIKELY( !max_peers ) ) return NULL;
245 63 : if( FD_UNLIKELY( !fd_ulong_is_aligned( (ulong)shmem, fd_gossip_wsample_align() ) ) ) return NULL;
246 :
247 63 : ulong height;
248 63 : ulong internal_cnt;
249 63 : compute_height( max_peers, &height, &internal_cnt );
250 :
251 63 : fd_gossip_wsample_t * s = (fd_gossip_wsample_t *)shmem;
252 :
253 63 : s->rng = rng;
254 63 : s->max_peers = max_peers;
255 63 : s->internal_cnt = internal_cnt;
256 63 : s->height = height;
257 :
258 : /* Compute trailing-array pointers. */
259 63 : FD_SCRATCH_ALLOC_INIT( l, shmem );
260 63 : /* */ FD_SCRATCH_ALLOC_APPEND( l, 64UL, sizeof(struct fd_gossip_wsample_private) );
261 63 : s->stakes = FD_SCRATCH_ALLOC_APPEND( l, alignof(ulong), max_peers*sizeof(ulong) );
262 63 : s->exists = FD_SCRATCH_ALLOC_APPEND( l, alignof(int), max_peers*sizeof(int) );
263 63 : s->fresh = FD_SCRATCH_ALLOC_APPEND( l, alignof(int), max_peers*sizeof(int) );
264 63 : s->ping_tracked = FD_SCRATCH_ALLOC_APPEND( l, alignof(int), max_peers*sizeof(int) );
265 63 : s->is_entrypoint = FD_SCRATCH_ALLOC_APPEND( l, alignof(int), max_peers*sizeof(int) );
266 63 : s->is_removed = FD_SCRATCH_ALLOC_APPEND( l, alignof(int *), max_peers*sizeof(int *) );
267 63 : int * is_removed = FD_SCRATCH_ALLOC_APPEND( l, alignof(int), max_peers*BUCKET_CNT*sizeof(int) );
268 63 : 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 63 : fd_memset( s->exists, 0, max_peers * sizeof(int) );
273 63 : fd_memset( s->fresh, 0, max_peers * sizeof(int) );
274 63 : fd_memset( s->ping_tracked, 0, max_peers * sizeof(int) );
275 63 : fd_memset( s->is_entrypoint, 0, max_peers * sizeof(int) );
276 63 : fd_memset( is_removed, 0, max_peers * BUCKET_CNT*sizeof(int) );
277 63 : 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 63 : s->self_stake = 0UL;
281 63 : s->self_ci_idx = ULONG_MAX;
282 63 : s->pr_total_weight = 0UL;
283 1638 : for( ulong b=0UL; b<BUCKET_CNT; b++ ) s->bucket_total_weight[ b ] = 0UL;
284 :
285 16317 : for( ulong i=0UL; i<max_peers; i++ ) s->is_removed[ i ] = is_removed + i*BUCKET_CNT;
286 :
287 63 : return shmem;
288 63 : }
289 :
290 : fd_gossip_wsample_t *
291 63 : fd_gossip_wsample_join( void * shwsample ) {
292 63 : return (fd_gossip_wsample_t *)shwsample;
293 63 : }
294 :
295 : static inline int
296 : is_active( ulong stake,
297 : int ping_tracked,
298 80688 : int is_entrypoint ) {
299 : /* 1. If the node is an entrypoint, it is active */
300 80688 : if( FD_UNLIKELY( is_entrypoint ) ) return 1;
301 :
302 : /* 2. If the node has more than 1 sol staked, it is active */
303 80688 : if( FD_UNLIKELY( stake>=1000000000UL ) ) return 1;
304 :
305 : /* 3. If the node has actively ponged a ping, it is active */
306 20589 : if( FD_UNLIKELY( ping_tracked ) ) return 1;
307 :
308 18 : return 0;
309 20589 : }
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 12390 : int is_me ) {
318 12390 : FD_TEST( !sampler->exists[ ci_idx ] );
319 :
320 12390 : sampler->exists[ ci_idx ] = 1;
321 12390 : sampler->stakes[ ci_idx ] = stake;
322 12390 : sampler->fresh[ ci_idx ] = 1; /* newly added peers are fresh */
323 12390 : sampler->ping_tracked[ ci_idx ] = ping_tracked;
324 12390 : sampler->is_entrypoint[ ci_idx ] = is_entrypoint;
325 12390 : fd_memset( sampler->is_removed[ ci_idx ], 0, BUCKET_CNT*sizeof(int) );
326 :
327 12390 : 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 12390 : ulong height = sampler->height;
334 12390 : 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 12390 : 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 12387 : ulong pr_w = pr_weight( fd_ulong_min( stake, sampler->self_stake ) );
343 12387 : tree_add_weight( sampler->trees+PR_TREE_IDX*internal_cnt, height, internal_cnt, ci_idx, pr_w );
344 12387 : sampler->pr_total_weight += pr_w;
345 :
346 : /* Bucket trees. */
347 322062 : for( ulong b=0UL; b<BUCKET_CNT; b++ ) {
348 309675 : ulong bw = adjusted_bucket_weight( stake, b, 1 /* is_fresh */ );
349 309675 : tree_add_weight( sampler->trees+(1UL+b)*internal_cnt, height, internal_cnt, ci_idx, bw );
350 309675 : sampler->bucket_total_weight[ b ] += bw;
351 309675 : }
352 12387 : }
353 12390 : }
354 :
355 : void
356 : fd_gossip_wsample_remove( fd_gossip_wsample_t * sampler,
357 6162 : ulong ci_idx ) {
358 6162 : FD_TEST( sampler->exists[ ci_idx ] );
359 :
360 6162 : sampler->exists[ ci_idx ] = 0;
361 6162 : if( FD_UNLIKELY( sampler->self_ci_idx==ci_idx ) ) {
362 0 : sampler->self_ci_idx = ULONG_MAX;
363 0 : return;
364 0 : }
365 :
366 6162 : int active = is_active( sampler->stakes[ ci_idx ], sampler->ping_tracked[ ci_idx ], sampler->is_entrypoint[ ci_idx ] );
367 6162 : if( FD_UNLIKELY( !active ) ) return;
368 :
369 6162 : ulong height = sampler->height;
370 6162 : ulong internal_cnt = sampler->internal_cnt;
371 :
372 6162 : ulong pr_w = adjusted_pr_weight( sampler->stakes[ ci_idx ], sampler->self_stake, sampler->fresh[ ci_idx ] );
373 6162 : tree_sub_weight( sampler->trees+PR_TREE_IDX*internal_cnt, height, internal_cnt, ci_idx, pr_w );
374 6162 : sampler->pr_total_weight -= pr_w;
375 :
376 160212 : for( ulong b=0UL; b<BUCKET_CNT; b++ ) {
377 154050 : 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 153291 : ulong bw = adjusted_bucket_weight( sampler->stakes[ ci_idx ], b, sampler->fresh[ ci_idx ] );
380 153291 : tree_sub_weight( sampler->trees+(1UL+b)*internal_cnt, height, internal_cnt, ci_idx, bw );
381 153291 : sampler->bucket_total_weight[ b ] -= bw;
382 153291 : }
383 6162 : }
384 :
385 : ulong
386 620436 : fd_gossip_wsample_sample_pull_request( fd_gossip_wsample_t * sampler ) {
387 620436 : sample_result_t r = tree_sample( sampler->trees + PR_TREE_IDX*sampler->internal_cnt,
388 620436 : sampler->height,
389 620436 : sampler->internal_cnt,
390 620436 : sampler->pr_total_weight,
391 620436 : sampler->rng );
392 620436 : return r.idx;
393 620436 : }
394 :
395 : ulong
396 : fd_gossip_wsample_sample_remove_bucket( fd_gossip_wsample_t * sampler,
397 32322 : ulong bucket ) {
398 32322 : tree_ele_t * bt = sampler->trees + (1UL+bucket)*sampler->internal_cnt;
399 :
400 32322 : sample_result_t r = tree_sample( bt,
401 32322 : sampler->height,
402 32322 : sampler->internal_cnt,
403 32322 : sampler->bucket_total_weight[bucket],
404 32322 : sampler->rng );
405 32322 : 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 31860 : FD_TEST( sampler->exists[ r.idx ] );
410 31860 : int active = is_active( sampler->stakes[ r.idx ], sampler->ping_tracked[ r.idx ], sampler->is_entrypoint[ r.idx ] );
411 31860 : ulong weight = fd_ulong_if( active, adjusted_bucket_weight( sampler->stakes[ r.idx ], bucket, sampler->fresh[ r.idx ] ), 0UL );
412 31860 : FD_TEST( r.weight==weight );
413 31860 : FD_TEST( !sampler->is_removed[ r.idx ][ bucket ] );
414 31860 : FD_TEST( sampler->self_ci_idx!=r.idx );
415 31860 : tree_sub_weight( bt, sampler->height, sampler->internal_cnt, r.idx, r.weight );
416 31860 : sampler->bucket_total_weight[ bucket ] -= r.weight;
417 31860 : sampler->is_removed[ r.idx ][ bucket ] = 1;
418 :
419 31860 : return r.idx;
420 31860 : }
421 :
422 : void
423 : fd_gossip_wsample_add_bucket( fd_gossip_wsample_t * sampler,
424 : ulong bucket,
425 30168 : ulong ci_idx ) {
426 30168 : FD_TEST( sampler->exists[ ci_idx ] );
427 30168 : FD_TEST( sampler->is_removed[ ci_idx ][ bucket ] );
428 30168 : FD_TEST( sampler->self_ci_idx!=ci_idx );
429 :
430 30168 : ulong stake = sampler->stakes[ ci_idx ];
431 30168 : int is_fresh = sampler->fresh[ ci_idx ];
432 30168 : int active = is_active( stake, sampler->ping_tracked[ ci_idx ], sampler->is_entrypoint[ ci_idx ] );
433 30168 : ulong bw = fd_ulong_if( active, adjusted_bucket_weight( stake, bucket, is_fresh ), 0UL );
434 :
435 30168 : tree_add_weight( sampler->trees + (1UL+bucket)*sampler->internal_cnt, sampler->height, sampler->internal_cnt, ci_idx, bw );
436 30168 : sampler->bucket_total_weight[ bucket ] += bw;
437 30168 : sampler->is_removed[ ci_idx ][ bucket ] = 0;
438 30168 : }
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 48 : int old_is_me ) {
448 48 : FD_TEST( sampler->exists[ ci_idx ] );
449 :
450 48 : int old_active = is_active( old_stake, old_ping_tracked, old_is_entrypoint );
451 48 : int new_active = is_active( sampler->stakes[ ci_idx ], sampler->ping_tracked[ ci_idx ], sampler->is_entrypoint[ ci_idx ] );
452 :
453 48 : int is_fresh = sampler->fresh[ ci_idx ];
454 48 : ulong height = sampler->height;
455 48 : ulong internal_cnt = sampler->internal_cnt;
456 :
457 : /* Update pull-request tree weight. */
458 48 : tree_ele_t * pr = sampler->trees + PR_TREE_IDX*internal_cnt;
459 48 : ulong old_pr_w = fd_ulong_if( old_active, adjusted_pr_weight( old_stake, sampler->self_stake, old_fresh ), 0UL );
460 48 : if( FD_UNLIKELY( old_is_me ) ) old_pr_w = 0UL;
461 48 : ulong new_pr_w = fd_ulong_if( new_active, adjusted_pr_weight( sampler->stakes[ ci_idx ], sampler->self_stake, is_fresh ), 0UL );
462 48 : if( FD_UNLIKELY( sampler->self_ci_idx==ci_idx ) ) new_pr_w = 0UL;
463 :
464 48 : if( FD_LIKELY( new_pr_w>old_pr_w ) ){
465 21 : ulong delta = new_pr_w-old_pr_w;
466 21 : tree_add_weight( pr, height, internal_cnt, ci_idx, delta );
467 21 : sampler->pr_total_weight += delta;
468 27 : } else if( FD_LIKELY( new_pr_w<old_pr_w ) ) {
469 21 : ulong delta = old_pr_w-new_pr_w;
470 21 : tree_sub_weight( pr, height, internal_cnt, ci_idx, delta );
471 21 : sampler->pr_total_weight -= delta;
472 21 : }
473 :
474 : /* Update bucket trees. Only update buckets where the peer currently
475 : has weight (may have been sample-removed from individual buckets). */
476 1248 : for( ulong b=0UL; b<BUCKET_CNT; b++ ) {
477 1200 : tree_ele_t * bt = sampler->trees + (1UL+b)*internal_cnt;
478 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. */
479 :
480 1200 : ulong old_bw = fd_ulong_if( old_active, adjusted_bucket_weight( old_stake, b, old_fresh ), 0UL );
481 1200 : if( FD_UNLIKELY( old_is_me ) ) old_bw = 0UL;
482 1200 : ulong new_bw = fd_ulong_if( new_active, adjusted_bucket_weight( sampler->stakes[ ci_idx ], b, is_fresh ), 0UL );
483 1200 : if( FD_UNLIKELY( sampler->self_ci_idx==ci_idx ) ) new_bw = 0UL;
484 :
485 1200 : if( FD_LIKELY( new_bw>old_bw ) ) {
486 465 : ulong delta = new_bw-old_bw;
487 465 : tree_add_weight( bt, height, internal_cnt, ci_idx, delta );
488 465 : sampler->bucket_total_weight[ b ] += delta;
489 735 : } else if( FD_LIKELY( new_bw < old_bw ) ) {
490 516 : ulong delta = old_bw-new_bw;
491 516 : tree_sub_weight( bt, height, internal_cnt, ci_idx, delta );
492 516 : sampler->bucket_total_weight[ b ] -= delta;
493 516 : }
494 1200 : }
495 48 : }
496 :
497 : void
498 : fd_gossip_wsample_stake( fd_gossip_wsample_t * sampler,
499 : ulong ci_idx,
500 9 : ulong new_stake ) {
501 9 : FD_TEST( sampler->exists[ ci_idx ] );
502 :
503 9 : if( FD_UNLIKELY( sampler->stakes[ ci_idx ]==new_stake ) ) return;
504 9 : ulong old_stake = sampler->stakes[ ci_idx ];
505 9 : sampler->stakes[ ci_idx ] = new_stake;
506 9 : 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 9 : }
508 :
509 : void
510 : fd_gossip_wsample_fresh( fd_gossip_wsample_t * sampler,
511 : ulong ci_idx,
512 24 : int fresh ) {
513 24 : FD_TEST( sampler->exists[ ci_idx ] );
514 :
515 24 : if( FD_UNLIKELY( sampler->fresh[ ci_idx ]==fresh ) ) return;
516 24 : sampler->fresh[ ci_idx ] = fresh;
517 24 : 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 24 : }
519 :
520 : void
521 : fd_gossip_wsample_ping_tracked( fd_gossip_wsample_t * sampler,
522 : ulong ci_idx,
523 15 : int ping_tracked ) {
524 15 : FD_TEST( sampler->exists[ ci_idx ] );
525 :
526 15 : if( FD_UNLIKELY( sampler->ping_tracked[ ci_idx ]==ping_tracked ) ) return;
527 15 : sampler->ping_tracked[ ci_idx ] = ping_tracked;
528 15 : 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 15 : }
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 21 : ulong self_stake ) {
580 21 : if( FD_UNLIKELY( sampler->self_stake==self_stake ) ) return;
581 :
582 21 : ulong old_self_stake = sampler->self_stake;
583 21 : sampler->self_stake = self_stake;
584 :
585 21 : ulong height = sampler->height;
586 21 : ulong internal_cnt = sampler->internal_cnt;
587 21 : tree_ele_t * pr = sampler->trees + PR_TREE_IDX*internal_cnt;
588 21 : ulong * stakes = sampler->stakes;
589 21 : int * fresh_flags = sampler->fresh;
590 :
591 357 : for( ulong i=0UL; i<sampler->max_peers; i++ ) {
592 336 : if( FD_UNLIKELY( !sampler->exists[ i ] ) ) continue;
593 :
594 12 : int active = is_active( stakes[ i ], sampler->ping_tracked[ i ], sampler->is_entrypoint[ i ] );
595 12 : ulong old_w = fd_ulong_if( active, adjusted_pr_weight( stakes[ i ], old_self_stake, fresh_flags[ i ] ), 0UL );
596 12 : if( FD_UNLIKELY( sampler->self_ci_idx==i ) ) old_w = 0UL;
597 12 : ulong new_w = fd_ulong_if( active, adjusted_pr_weight( stakes[ i ], self_stake, fresh_flags[ i ] ), 0UL );
598 12 : if( FD_UNLIKELY( sampler->self_ci_idx==i ) ) new_w = 0UL;
599 :
600 12 : if( FD_LIKELY( new_w>old_w ) ) {
601 6 : ulong delta = new_w-old_w;
602 6 : tree_add_weight( pr, height, internal_cnt, i, delta );
603 6 : sampler->pr_total_weight += delta;
604 6 : } else if( FD_LIKELY( new_w<old_w ) ) {
605 3 : ulong delta = old_w-new_w;
606 3 : tree_sub_weight( pr, height, internal_cnt, i, delta );
607 3 : sampler->pr_total_weight -= delta;
608 3 : }
609 12 : }
610 21 : }
|
