Line data Source code
1 : #include "fd_prune_finder.h"
2 : #include "../../util/log/fd_log.h"
3 :
4 : /* Maximum number of origins tracked in the outer map. Matches
5 : Agave's ReceivedCache capacity of 2 * CRDS_UNIQUE_PUBKEY_CAPACITY. */
6 0 : #define FD_PRUNE_FINDER_ORIGIN_MAX (16384UL)
7 :
8 : /* Maximum number of relayers tracked per origin. Matches Agave's
9 : ReceivedCacheEntry::CAPACITY. When the inner map is full, new
10 : relayers are silently dropped (score-0 entries are pruned first,
11 : so an attacker cannot displace good relayers). */
12 : #define FD_PRUNE_FINDER_RELAYER_MAX (50UL)
13 :
14 : /* Minimum number of fresh (num_dups==0) messages recorded for an
15 : origin before a prune decision is made. Matches Agave's
16 : ReceivedCache::MIN_NUM_UPSERTS. */
17 : #define FD_PRUNE_FINDER_MIN_NUM_UPSERTS (20UL)
18 :
19 : /* Minimum number of relayers to keep (never pruned) per origin,
20 : regardless of score or stake. Matches Agave's
21 : CRDS_GOSSIP_PRUNE_MIN_INGRESS_NODES. */
22 : #define FD_PRUNE_FINDER_MIN_INGRESS_NODES (2UL)
23 :
24 : /* Fraction of stake that must be covered before additional relayers
25 : can be pruned. min_ingress_stake = min(identity_stake, origin_stake)
26 : * FD_PRUNE_FINDER_STAKE_THRESHOLD_PCT / 100. Matches Agave's
27 : CRDS_GOSSIP_PRUNE_STAKE_THRESHOLD_PCT = 0.15. */
28 0 : #define FD_PRUNE_FINDER_STAKE_THRESHOLD_PCT (15UL)
29 :
30 : /* Number of duplicates below which a relayer is considered timely
31 : (its score is incremented). Matches Agave's
32 : ReceivedCacheEntry::NUM_DUPS_THRESHOLD. */
33 : #define FD_PRUNE_FINDER_NUM_DUPS_THRESHOLD (2UL)
34 :
35 : struct pubkey_private {
36 : uchar b[ 32UL ];
37 : };
38 :
39 : typedef struct pubkey_private pubkey_private_t;
40 :
41 : /* fd_prune_relayer stores the score for a single relayer within an
42 : origin entry. The score counts how many times this relayer was
43 : among the first NUM_DUPS_THRESHOLD (2) to deliver a message from
44 : this origin. relayer_stake is cached at insertion time. */
45 :
46 : struct fd_prune_relayer {
47 : uchar pubkey[ 32UL ];
48 : ulong score;
49 : ulong stake;
50 : };
51 :
52 : typedef struct fd_prune_relayer fd_prune_relayer_t;
53 :
54 : /* fd_prune_origin is an entry in the outer map, keyed by origin
55 : pubkey. It tracks all known relayers for that origin and the
56 : number of fresh (num_dups==0) messages received. */
57 :
58 : struct fd_prune_origin {
59 : pubkey_private_t origin_pubkey;
60 :
61 : ulong num_upserts;
62 : ulong origin_stake;
63 : ulong relayers_cnt;
64 : fd_prune_relayer_t relayers[ FD_PRUNE_FINDER_RELAYER_MAX ];
65 :
66 : ulong pool_next;
67 :
68 : ulong map_next;
69 : ulong map_prev;
70 :
71 : ulong lru_prev;
72 : ulong lru_next;
73 : };
74 :
75 : typedef struct fd_prune_origin fd_prune_origin_t;
76 :
77 : #define POOL_NAME pool
78 0 : #define POOL_NEXT pool_next
79 0 : #define POOL_T fd_prune_origin_t
80 : #include "../../util/tmpl/fd_pool.c"
81 :
82 : #pragma GCC diagnostic push
83 : #pragma GCC diagnostic ignored "-Wunused-value"
84 : #define DLIST_NAME lru_list
85 : #define DLIST_ELE_T fd_prune_origin_t
86 0 : #define DLIST_PREV lru_prev
87 0 : #define DLIST_NEXT lru_next
88 : #include "../../util/tmpl/fd_dlist.c"
89 : #pragma GCC diagnostic pop
90 :
91 : #define MAP_NAME origin_map
92 : #define MAP_ELE_T fd_prune_origin_t
93 : #define MAP_KEY_T pubkey_private_t
94 0 : #define MAP_KEY origin_pubkey
95 0 : #define MAP_IDX_T ulong
96 0 : #define MAP_NEXT map_next
97 0 : #define MAP_PREV map_prev
98 0 : #define MAP_KEY_HASH(k,s) ((s) ^ fd_ulong_load_8( (k)->b ))
99 0 : #define MAP_KEY_EQ(k0,k1) (!memcmp((k0)->b, (k1)->b, 32UL))
100 : #define MAP_OPTIMIZE_RANDOM_ACCESS_REMOVAL 1
101 : #include "../../util/tmpl/fd_map_chain.c"
102 :
103 : /* Maximum number of (destination, origin) pairs that can be buffered
104 : between record and pop_prune calls. 17 push values * 50 relayers
105 : per origin = 850 worst case. */
106 : #define FD_PRUNE_FINDER_PENDING_MAX (850UL)
107 :
108 : struct fd_prune_pending {
109 : uchar relayer[ 32UL ];
110 : uchar origin[ 32UL ];
111 : };
112 :
113 : struct fd_prune_finder_private {
114 : fd_prune_origin_t * pool;
115 : origin_map_t * origins;
116 : lru_list_t * lru;
117 :
118 : uchar identity_pubkey[ 32UL ];
119 : ulong identity_stake;
120 :
121 : ulong pending_cnt;
122 : ulong pending_read;
123 : struct fd_prune_pending pending[ FD_PRUNE_FINDER_PENDING_MAX ];
124 : };
125 :
126 : FD_FN_CONST ulong
127 0 : fd_prune_finder_align( void ) {
128 0 : return 128UL;
129 0 : }
130 :
131 : FD_FN_CONST ulong
132 0 : fd_prune_finder_footprint( void ) {
133 0 : ulong chain_cnt = origin_map_chain_cnt_est( FD_PRUNE_FINDER_ORIGIN_MAX );
134 0 : ulong l;
135 0 : l = FD_LAYOUT_INIT;
136 0 : l = FD_LAYOUT_APPEND( l, alignof(fd_prune_finder_t), sizeof(fd_prune_finder_t) );
137 0 : l = FD_LAYOUT_APPEND( l, pool_align(), pool_footprint( FD_PRUNE_FINDER_ORIGIN_MAX ) );
138 0 : l = FD_LAYOUT_APPEND( l, origin_map_align(), origin_map_footprint( chain_cnt ) );
139 0 : l = FD_LAYOUT_APPEND( l, lru_list_align(), lru_list_footprint() );
140 0 : l = FD_LAYOUT_FINI( l, fd_prune_finder_align() );
141 0 : return l;
142 0 : }
143 :
144 : void *
145 0 : fd_prune_finder_new( void * shmem ) {
146 0 : if( FD_UNLIKELY( !shmem ) ) return NULL;
147 0 : if( FD_UNLIKELY( !fd_ulong_is_aligned( (ulong)shmem, fd_prune_finder_align() ) ) ) return NULL;
148 :
149 0 : ulong chain_cnt = origin_map_chain_cnt_est( FD_PRUNE_FINDER_ORIGIN_MAX );
150 :
151 0 : FD_SCRATCH_ALLOC_INIT( l, shmem );
152 0 : fd_prune_finder_t * pf = FD_SCRATCH_ALLOC_APPEND( l, alignof(fd_prune_finder_t), sizeof(fd_prune_finder_t) );
153 0 : void * pool_mem = FD_SCRATCH_ALLOC_APPEND( l, pool_align(), pool_footprint( FD_PRUNE_FINDER_ORIGIN_MAX ) );
154 0 : void * map_mem = FD_SCRATCH_ALLOC_APPEND( l, origin_map_align(), origin_map_footprint( chain_cnt ) );
155 0 : void * lru_mem = FD_SCRATCH_ALLOC_APPEND( l, lru_list_align(), lru_list_footprint() );
156 :
157 0 : pf->pool = pool_join( pool_new( pool_mem, FD_PRUNE_FINDER_ORIGIN_MAX ) );
158 0 : FD_TEST( pf->pool );
159 0 : pf->origins = origin_map_join( origin_map_new( map_mem, chain_cnt, 0UL ) );
160 0 : FD_TEST( pf->origins );
161 0 : pf->lru = lru_list_join( lru_list_new( lru_mem ) );
162 0 : FD_TEST( pf->lru );
163 :
164 0 : fd_memset( pf->identity_pubkey, 0, 32UL );
165 0 : pf->identity_stake = 0UL;
166 :
167 0 : pf->pending_cnt = 0UL;
168 0 : pf->pending_read = 0UL;
169 :
170 0 : return pf;
171 0 : }
172 :
173 : fd_prune_finder_t *
174 0 : fd_prune_finder_join( void * shpf ) {
175 0 : return (fd_prune_finder_t *)shpf;
176 0 : }
177 :
178 : void
179 : fd_prune_finder_set_identity( fd_prune_finder_t * pf,
180 : uchar const * identity_pubkey,
181 0 : ulong identity_stake ) {
182 0 : fd_memcpy( pf->identity_pubkey, identity_pubkey, 32UL );
183 0 : pf->identity_stake = identity_stake;
184 0 : }
185 :
186 : static inline fd_prune_relayer_t *
187 : find_relayer( fd_prune_origin_t * origin,
188 0 : uchar const * relayer_pubkey ) {
189 0 : for( ulong i=0UL; i<origin->relayers_cnt; i++ ) {
190 0 : if( FD_UNLIKELY( !memcmp( origin->relayers[ i ].pubkey, relayer_pubkey, 32UL ) ) ) {
191 0 : return &origin->relayers[ i ];
192 0 : }
193 0 : }
194 0 : return NULL;
195 0 : }
196 :
197 : static inline fd_prune_relayer_t *
198 : insert_relayer( fd_prune_origin_t * origin,
199 : uchar const * relayer_pubkey,
200 : ulong score,
201 0 : ulong relayer_stake ) {
202 0 : if( FD_UNLIKELY( origin->relayers_cnt>=FD_PRUNE_FINDER_RELAYER_MAX ) ) return NULL;
203 0 : fd_prune_relayer_t * r = &origin->relayers[ origin->relayers_cnt++ ];
204 0 : fd_memcpy( r->pubkey, relayer_pubkey, 32UL );
205 0 : r->score = score;
206 0 : r->stake = relayer_stake;
207 0 : return r;
208 0 : }
209 :
210 : #define SORT_NAME sort_relayers_desc
211 0 : #define SORT_KEY_T fd_prune_relayer_t
212 0 : #define SORT_BEFORE(a,b) ((a).score>(b).score || ((a).score==(b).score && (a).stake>(b).stake))
213 : #define SORT_QUICK_SWAP_MINIMIZE 1
214 : #include "../../util/tmpl/fd_sort.c"
215 :
216 : /* do_prune executes the prune decision for a single origin entry.
217 : Sorts relayers by (score, stake) descending, keeps at least
218 : min_ingress_nodes (2) and enough stake to cover min_ingress_stake,
219 : then appends (destination, origin) pairs for the remaining relayers
220 : to the pending buffer. Resets the origin entry afterward. */
221 :
222 : static void
223 : do_prune( fd_prune_finder_t * pf,
224 0 : fd_prune_origin_t * origin ) {
225 0 : ulong cnt = origin->relayers_cnt;
226 0 : if( FD_UNLIKELY( !cnt ) ) {
227 0 : origin->num_upserts = 0UL;
228 0 : origin->relayers_cnt = 0UL;
229 0 : return;
230 0 : }
231 :
232 0 : sort_relayers_desc_insert( origin->relayers, cnt );
233 :
234 : /* Compute min_ingress_stake = min(identity_stake, origin_stake) * 15/100.
235 : Relayers covering the top min_ingress_nodes and enough cumulative
236 : stake to meet min_ingress_stake are kept; the rest are pruned. */
237 0 : ulong min_base = fd_ulong_min( pf->identity_stake, origin->origin_stake );
238 0 : ulong min_ingress_stake = min_base * FD_PRUNE_FINDER_STAKE_THRESHOLD_PCT / 100UL;
239 :
240 0 : ulong cum_stake = 0UL;
241 :
242 0 : for( ulong i=0UL; i<cnt; i++ ) {
243 0 : fd_prune_relayer_t * r = &origin->relayers[ i ];
244 :
245 0 : if( FD_LIKELY( i<FD_PRUNE_FINDER_MIN_INGRESS_NODES ) ) {
246 0 : cum_stake += r->stake;
247 0 : continue;
248 0 : }
249 :
250 0 : if( FD_LIKELY( cum_stake<min_ingress_stake ) ) {
251 0 : cum_stake += r->stake;
252 0 : continue;
253 0 : }
254 :
255 : /* Filter out origin == relayer (per Agave) */
256 0 : if( FD_UNLIKELY( !memcmp( r->pubkey, origin->origin_pubkey.b, 32UL ) ) ) continue;
257 :
258 0 : FD_TEST( pf->pending_cnt<FD_PRUNE_FINDER_PENDING_MAX );
259 0 : struct fd_prune_pending * p = &pf->pending[ pf->pending_cnt++ ];
260 0 : fd_memcpy( p->relayer, r->pubkey, 32UL );
261 0 : fd_memcpy( p->origin, origin->origin_pubkey.b, 32UL );
262 0 : }
263 :
264 : /* Reset the origin entry (matching Agave's std::mem::take). */
265 0 : origin->num_upserts = 0UL;
266 0 : origin->relayers_cnt = 0UL;
267 0 : }
268 :
269 : void
270 : fd_prune_finder_record( fd_prune_finder_t * pf,
271 : uchar const * origin_pubkey,
272 : ulong origin_stake,
273 : uchar const * relayer_pubkey,
274 : ulong relayer_stake,
275 0 : ulong num_dups ) {
276 0 : fd_prune_origin_t * origin = origin_map_ele_query( pf->origins,
277 0 : fd_type_pun_const( origin_pubkey ),
278 0 : NULL,
279 0 : pf->pool );
280 :
281 0 : if( FD_UNLIKELY( !origin ) ) {
282 0 : if( FD_LIKELY( pool_free( pf->pool ) ) ) {
283 0 : origin = pool_ele_acquire( pf->pool );
284 0 : } else {
285 0 : origin = lru_list_ele_pop_head( pf->lru, pf->pool );
286 0 : origin_map_ele_remove( pf->origins, &origin->origin_pubkey, NULL, pf->pool );
287 0 : }
288 :
289 0 : origin->num_upserts = 0UL;
290 0 : origin->relayers_cnt = 0UL;
291 0 : origin->origin_stake = origin_stake;
292 0 : fd_memcpy( origin->origin_pubkey.b, origin_pubkey, 32UL );
293 :
294 0 : origin_map_ele_insert( pf->origins, origin, pf->pool );
295 0 : lru_list_ele_push_tail( pf->lru, origin, pf->pool );
296 0 : } else {
297 0 : lru_list_ele_remove( pf->lru, origin, pf->pool );
298 0 : lru_list_ele_push_tail( pf->lru, origin, pf->pool );
299 0 : origin->origin_stake = origin_stake;
300 0 : }
301 :
302 0 : if( FD_UNLIKELY( !num_dups ) ) origin->num_upserts++;
303 :
304 0 : if( FD_LIKELY( num_dups<FD_PRUNE_FINDER_NUM_DUPS_THRESHOLD ) ) {
305 0 : fd_prune_relayer_t * r = find_relayer( origin, relayer_pubkey );
306 0 : if( FD_LIKELY( r ) ) {
307 0 : r->score++;
308 0 : r->stake = relayer_stake;
309 0 : } else {
310 0 : insert_relayer( origin, relayer_pubkey, 1UL, relayer_stake );
311 0 : }
312 0 : } else {
313 : /* Late delivery (num_dups >= 2): insert with score 0 if room.
314 : Do not increment score — prevents spoofed addresses from
315 : penalizing a good relayer. But do ensure the relayer is in
316 : the map so it can be pruned later. */
317 0 : fd_prune_relayer_t * r = find_relayer( origin, relayer_pubkey );
318 0 : if( FD_UNLIKELY( !r ) ) {
319 0 : insert_relayer( origin, relayer_pubkey, 0UL, relayer_stake );
320 0 : } else {
321 0 : r->stake = relayer_stake;
322 0 : }
323 0 : }
324 :
325 0 : if( FD_UNLIKELY( origin->num_upserts>=FD_PRUNE_FINDER_MIN_NUM_UPSERTS ) ) {
326 0 : do_prune( pf, origin );
327 0 : }
328 0 : }
329 :
330 : int
331 : fd_prune_finder_pop_prune( fd_prune_finder_t * pf,
332 : uchar const ** out_relayer,
333 0 : uchar const ** out_origin ) {
334 0 : if( FD_UNLIKELY( pf->pending_read>=pf->pending_cnt ) ) {
335 0 : pf->pending_read = 0UL;
336 0 : pf->pending_cnt = 0UL;
337 0 : return 0;
338 0 : }
339 :
340 0 : struct fd_prune_pending * p = &pf->pending[ pf->pending_read++ ];
341 0 : *out_relayer = p->relayer;
342 0 : *out_origin = p->origin;
343 0 : return 1;
344 0 : }
|
