Line data Source code
1 : #include "fd_gossip_purged_private.h"
2 : #include "fd_gossip_hset.h"
3 : #include "../../util/rng/fd_rng.h"
4 :
5 : struct fd_gossip_purged_private {
6 : fd_crds_purged_t * pool;
7 : purged_map_t * map; /* dedup by hash prefix */
8 : replaced_dlist_t * replaced_dlist;
9 : failed_inserts_dlist_t * failed_inserts_dlist;
10 : no_contact_info_dlist_t * no_contact_info_dlist;
11 :
12 : /* Per-origin-pubkey map (MAP_MULTI) for no_contact_info entries.
13 : When we learn a contact info for a pubkey, we drain all
14 : associated hashes from the purged table so peers re-send them.
15 : Elements live in the purged pool above. */
16 : nci_origin_map_t * nci_origin_map;
17 :
18 : /* Dense copy of the hashes for building pull request filters */
19 : fd_gossip_hset_t * hset;
20 :
21 : fd_gossip_purged_metrics_t metrics[1];
22 :
23 : ulong magic; /* ==FD_GOSSIP_PURGED_MAGIC */
24 : };
25 :
26 : static const long STAKED_EXPIRE_DURATION_NANOS = 432000L*400L*1000L*1000L;
27 : static const long REPLACED_EXPIRE_DURATION_NANOS = 60L*1000L*1000L*1000L;
28 : static const long FAILED_INSERTS_EXPIRE_DURATION_NANOS = 60L*1000L*1000L*1000L;
29 :
30 : FD_FN_CONST ulong
31 33 : fd_gossip_purged_align( void ) {
32 33 : return FD_GOSSIP_PURGED_ALIGN;
33 33 : }
34 :
35 : FD_FN_CONST ulong
36 24 : fd_gossip_purged_footprint( ulong purged_max ) {
37 24 : ulong nci_origin_max = fd_ulong_pow2_up( purged_max/4UL );
38 24 : ulong l;
39 24 : l = FD_LAYOUT_INIT;
40 24 : l = FD_LAYOUT_APPEND( l, FD_GOSSIP_PURGED_ALIGN, sizeof(fd_gossip_purged_t) );
41 24 : l = FD_LAYOUT_APPEND( l, purged_pool_align(), purged_pool_footprint( purged_max ) );
42 24 : l = FD_LAYOUT_APPEND( l, purged_map_align(), purged_map_footprint( purged_map_chain_cnt_est( purged_max ) ) );
43 24 : l = FD_LAYOUT_APPEND( l, replaced_dlist_align(), replaced_dlist_footprint() );
44 24 : l = FD_LAYOUT_APPEND( l, failed_inserts_dlist_align(), failed_inserts_dlist_footprint() );
45 24 : l = FD_LAYOUT_APPEND( l, no_contact_info_dlist_align(), no_contact_info_dlist_footprint() );
46 24 : l = FD_LAYOUT_APPEND( l, nci_origin_map_align(), nci_origin_map_footprint( nci_origin_max ) );
47 24 : l = FD_LAYOUT_APPEND( l, fd_gossip_hset_align(), fd_gossip_hset_footprint( purged_max ) );
48 24 : return FD_LAYOUT_FINI( l, FD_GOSSIP_PURGED_ALIGN );
49 24 : }
50 :
51 : void *
52 : fd_gossip_purged_new( void * shmem,
53 : fd_rng_t * rng,
54 9 : ulong purged_max ) {
55 9 : if( FD_UNLIKELY( !shmem ) ) {
56 0 : FD_LOG_WARNING(( "NULL shmem" ));
57 0 : return NULL;
58 0 : }
59 :
60 9 : if( FD_UNLIKELY( !fd_ulong_is_aligned( (ulong)shmem, fd_gossip_purged_align() ) ) ) {
61 0 : FD_LOG_WARNING(( "misaligned shmem" ));
62 0 : return NULL;
63 0 : }
64 :
65 9 : if( FD_UNLIKELY( !fd_ulong_is_pow2( purged_max ) ) ) {
66 0 : FD_LOG_WARNING(( "purged_max must be a power of 2" ));
67 0 : return NULL;
68 0 : }
69 :
70 9 : if( FD_UNLIKELY( !rng ) ) {
71 0 : FD_LOG_WARNING(( "NULL rng" ));
72 0 : return NULL;
73 0 : }
74 :
75 9 : ulong nci_origin_max = fd_ulong_pow2_up( purged_max/4UL );
76 :
77 9 : FD_SCRATCH_ALLOC_INIT( l, shmem );
78 9 : fd_gossip_purged_t * purged = FD_SCRATCH_ALLOC_APPEND( l, FD_GOSSIP_PURGED_ALIGN, sizeof(fd_gossip_purged_t) );
79 9 : void * _pool = FD_SCRATCH_ALLOC_APPEND( l, purged_pool_align(), purged_pool_footprint( purged_max ) );
80 9 : void * _map = FD_SCRATCH_ALLOC_APPEND( l, purged_map_align(), purged_map_footprint( purged_map_chain_cnt_est( purged_max ) ) );
81 9 : void * _replaced_dlist = FD_SCRATCH_ALLOC_APPEND( l, replaced_dlist_align(), replaced_dlist_footprint() );
82 9 : void * _failed_inserts_dlist = FD_SCRATCH_ALLOC_APPEND( l, failed_inserts_dlist_align(), failed_inserts_dlist_footprint() );
83 9 : void * _nci_dlist = FD_SCRATCH_ALLOC_APPEND( l, no_contact_info_dlist_align(), no_contact_info_dlist_footprint() );
84 9 : void * _nci_origin_map = FD_SCRATCH_ALLOC_APPEND( l, nci_origin_map_align(), nci_origin_map_footprint( nci_origin_max ) );
85 9 : void * _hset = FD_SCRATCH_ALLOC_APPEND( l, fd_gossip_hset_align(), fd_gossip_hset_footprint( purged_max ) );
86 9 : FD_TEST( FD_SCRATCH_ALLOC_FINI( l, FD_GOSSIP_PURGED_ALIGN ) == (ulong)shmem + fd_gossip_purged_footprint( purged_max ) );
87 :
88 9 : purged->pool = purged_pool_join( purged_pool_new( _pool, purged_max ) );
89 9 : FD_TEST( purged->pool );
90 :
91 9 : purged->map = purged_map_join( purged_map_new( _map, purged_map_chain_cnt_est( purged_max ), fd_rng_ulong( rng ) ) );
92 9 : FD_TEST( purged->map );
93 :
94 9 : purged->replaced_dlist = replaced_dlist_join( replaced_dlist_new( _replaced_dlist ) );
95 9 : FD_TEST( purged->replaced_dlist );
96 :
97 9 : purged->failed_inserts_dlist = failed_inserts_dlist_join( failed_inserts_dlist_new( _failed_inserts_dlist ) );
98 9 : FD_TEST( purged->failed_inserts_dlist );
99 :
100 9 : purged->no_contact_info_dlist = no_contact_info_dlist_join( no_contact_info_dlist_new( _nci_dlist ) );
101 9 : FD_TEST( purged->no_contact_info_dlist );
102 :
103 9 : purged->nci_origin_map = nci_origin_map_join( nci_origin_map_new( _nci_origin_map, nci_origin_max, fd_rng_ulong( rng ) ) );
104 9 : FD_TEST( purged->nci_origin_map );
105 :
106 9 : purged->hset = fd_gossip_hset_join( fd_gossip_hset_new( _hset, purged_max ) );
107 9 : FD_TEST( purged->hset );
108 :
109 9 : memset( purged->metrics, 0, sizeof(fd_gossip_purged_metrics_t) );
110 :
111 9 : FD_COMPILER_MFENCE();
112 9 : FD_VOLATILE( purged->magic ) = FD_GOSSIP_PURGED_MAGIC;
113 9 : FD_COMPILER_MFENCE();
114 :
115 9 : return (void *)purged;
116 9 : }
117 :
118 : fd_gossip_purged_t *
119 9 : fd_gossip_purged_join( void * shpurged ) {
120 9 : if( FD_UNLIKELY( !shpurged ) ) {
121 0 : FD_LOG_WARNING(( "NULL shpurged" ));
122 0 : return NULL;
123 0 : }
124 :
125 9 : if( FD_UNLIKELY( !fd_ulong_is_aligned( (ulong)shpurged, fd_gossip_purged_align() ) ) ) {
126 0 : FD_LOG_WARNING(( "misaligned shpurged" ));
127 0 : return NULL;
128 0 : }
129 :
130 9 : fd_gossip_purged_t * purged = (fd_gossip_purged_t *)shpurged;
131 :
132 9 : if( FD_UNLIKELY( purged->magic!=FD_GOSSIP_PURGED_MAGIC ) ) {
133 0 : FD_LOG_WARNING(( "bad magic" ));
134 0 : return NULL;
135 0 : }
136 :
137 9 : return purged;
138 9 : }
139 :
140 : fd_gossip_purged_metrics_t const *
141 0 : fd_gossip_purged_metrics( fd_gossip_purged_t const * purged ) {
142 0 : return purged->metrics;
143 0 : }
144 :
145 : ulong
146 36033 : fd_gossip_purged_len( fd_gossip_purged_t const * purged ) {
147 36033 : return purged_pool_used( purged->pool );
148 36033 : }
149 :
150 : fd_gossip_hset_t const *
151 12294 : fd_gossip_purged_hset( fd_gossip_purged_t const * purged ) {
152 12294 : return purged->hset;
153 12294 : }
154 :
155 : static inline void
156 : purged_unindex( fd_gossip_purged_t * purged,
157 36009 : fd_crds_purged_t * ele ) {
158 36009 : purged_map_ele_remove_fast( purged->map, ele, purged->pool );
159 36009 : fd_gossip_hset_remove( purged->hset, purged_pool_idx( purged->pool, ele ) );
160 36009 : }
161 :
162 : static fd_crds_purged_t *
163 : acquire_ele( fd_gossip_purged_t * purged,
164 : uchar const * hash,
165 : ulong hash_prefix,
166 85161 : long now ) {
167 85161 : fd_crds_purged_t * ele;
168 85161 : if( FD_UNLIKELY( !purged_pool_free( purged->pool ) ) ) {
169 36000 : if( FD_LIKELY( !replaced_dlist_is_empty( purged->replaced_dlist, purged->pool ) ) ) {
170 36000 : ele = replaced_dlist_ele_pop_head( purged->replaced_dlist, purged->pool );
171 36000 : } else if( FD_LIKELY( !failed_inserts_dlist_is_empty( purged->failed_inserts_dlist, purged->pool ) ) ) {
172 0 : ele = failed_inserts_dlist_ele_pop_head( purged->failed_inserts_dlist, purged->pool );
173 0 : } else {
174 0 : ele = no_contact_info_dlist_ele_pop_head( purged->no_contact_info_dlist, purged->pool );
175 0 : nci_origin_map_ele_remove_fast( purged->nci_origin_map, ele, purged->pool );
176 0 : }
177 36000 : purged_unindex( purged, ele );
178 36000 : purged->metrics->purged_evicted_cnt++;
179 49161 : } else {
180 49161 : ele = purged_pool_ele_acquire( purged->pool );
181 49161 : purged->metrics->purged_cnt++;
182 49161 : }
183 :
184 85161 : fd_memcpy( ele->hash, hash, 32UL );
185 85161 : ele->map.hash_prefix = hash_prefix;
186 85161 : ele->expire.wallclock_nanos = now;
187 85161 : purged_map_ele_insert( purged->map, ele, purged->pool );
188 85161 : fd_gossip_hset_insert( purged->hset, purged_pool_idx( purged->pool, ele ), hash );
189 85161 : return ele;
190 85161 : }
191 :
192 : void
193 : fd_gossip_purged_insert_replaced( fd_gossip_purged_t * purged,
194 : uchar const * hash,
195 48477 : long now ) {
196 48477 : ulong hash_prefix = fd_ulong_load_8( hash );
197 48477 : if( FD_UNLIKELY( purged_map_ele_query_const( purged->map, &hash_prefix, NULL, purged->pool ) ) ) return;
198 :
199 48477 : fd_crds_purged_t * ele = acquire_ele( purged, hash, hash_prefix, now );
200 48477 : replaced_dlist_ele_push_tail( purged->replaced_dlist, ele, purged->pool );
201 48477 : }
202 :
203 : void
204 : fd_gossip_purged_insert_failed_insert( fd_gossip_purged_t * purged,
205 : uchar const * hash,
206 30672 : long now ) {
207 30672 : ulong hash_prefix = fd_ulong_load_8( hash );
208 30672 : if( FD_UNLIKELY( purged_map_ele_query_const( purged->map, &hash_prefix, NULL, purged->pool ) ) ) return;
209 :
210 30666 : fd_crds_purged_t * ele = acquire_ele( purged, hash, hash_prefix, now );
211 30666 : failed_inserts_dlist_ele_push_tail( purged->failed_inserts_dlist, ele, purged->pool );
212 30666 : }
213 :
214 : void
215 : fd_gossip_purged_insert_no_contact_info( fd_gossip_purged_t * purged,
216 : uchar const * origin,
217 : uchar const * hash,
218 6021 : long now ) {
219 6021 : ulong hash_prefix = fd_ulong_load_8( hash );
220 6021 : if( FD_UNLIKELY( purged_map_ele_query_const( purged->map, &hash_prefix, NULL, purged->pool ) ) ) return;
221 :
222 6018 : fd_crds_purged_t * ele = acquire_ele( purged, hash, hash_prefix, now );
223 6018 : fd_memcpy( ele->origin.uc, origin, 32UL );
224 6018 : no_contact_info_dlist_ele_push_tail( purged->no_contact_info_dlist, ele, purged->pool );
225 6018 : nci_origin_map_ele_insert( purged->nci_origin_map, ele, purged->pool );
226 6018 : }
227 :
228 : void
229 : fd_gossip_purged_drain_no_contact_info( fd_gossip_purged_t * purged,
230 6 : uchar const * origin ) {
231 : /* Iterate all entries in the MAP_MULTI chain for this origin,
232 : removing each one. We use idx-based iteration so we can
233 : capture the next index before removing the current element
234 : (which clobbers its chain pointers). */
235 6 : fd_pubkey_t const * key = (fd_pubkey_t const *)origin;
236 6 : ulong idx = nci_origin_map_idx_query_const( purged->nci_origin_map, key, ULONG_MAX, purged->pool );
237 9 : while( idx!=ULONG_MAX ) {
238 3 : ulong next_idx = nci_origin_map_idx_next_const( idx, ULONG_MAX, purged->pool );
239 3 : fd_crds_purged_t * entry = &purged->pool[ idx ];
240 :
241 3 : nci_origin_map_ele_remove_fast( purged->nci_origin_map, entry, purged->pool );
242 3 : no_contact_info_dlist_ele_remove( purged->no_contact_info_dlist, entry, purged->pool );
243 3 : purged_unindex( purged, entry );
244 3 : purged_pool_ele_release( purged->pool, entry );
245 :
246 3 : purged->metrics->purged_cnt--;
247 3 : idx = next_idx;
248 3 : }
249 6 : }
250 :
251 : void
252 : fd_gossip_purged_expire( fd_gossip_purged_t * purged,
253 6 : long now ) {
254 9 : while( !replaced_dlist_is_empty( purged->replaced_dlist, purged->pool ) ) {
255 6 : fd_crds_purged_t * head = replaced_dlist_ele_peek_head( purged->replaced_dlist, purged->pool );
256 :
257 6 : if( FD_LIKELY( head->expire.wallclock_nanos>now-REPLACED_EXPIRE_DURATION_NANOS ) ) break;
258 :
259 3 : replaced_dlist_ele_pop_head( purged->replaced_dlist, purged->pool );
260 3 : purged_unindex( purged, head );
261 3 : purged_pool_ele_release( purged->pool, head );
262 :
263 3 : purged->metrics->purged_cnt--;
264 3 : purged->metrics->purged_expired_cnt++;
265 3 : }
266 :
267 9 : while( !failed_inserts_dlist_is_empty( purged->failed_inserts_dlist, purged->pool ) ) {
268 6 : fd_crds_purged_t * head = failed_inserts_dlist_ele_peek_head( purged->failed_inserts_dlist, purged->pool );
269 :
270 : /* Agave uses 20 seconds here for failed inserts, but it's a little
271 : bit short and causes occasional bandwidth jittering. Use 60
272 : seconds instead. */
273 6 : if( FD_LIKELY( head->expire.wallclock_nanos>now-FAILED_INSERTS_EXPIRE_DURATION_NANOS ) ) break;
274 :
275 3 : failed_inserts_dlist_ele_pop_head( purged->failed_inserts_dlist, purged->pool );
276 3 : purged_unindex( purged, head );
277 3 : purged_pool_ele_release( purged->pool, head );
278 :
279 3 : purged->metrics->purged_cnt--;
280 3 : purged->metrics->purged_expired_cnt++;
281 3 : }
282 :
283 6 : while( !no_contact_info_dlist_is_empty( purged->no_contact_info_dlist, purged->pool ) ) {
284 3 : fd_crds_purged_t * head = no_contact_info_dlist_ele_peek_head( purged->no_contact_info_dlist, purged->pool );
285 :
286 : /* Super long expiry time ... these don't get expired from peer
287 : tables since they can last up to ~2 days, so we would otherwise
288 : keep re-requesting these. Reasonable to just fill the LRU with
289 : them and let them cycle off then, or of course once we learn the
290 : contact info of whoever the origin was. */
291 3 : if( FD_LIKELY( head->expire.wallclock_nanos>now-STAKED_EXPIRE_DURATION_NANOS ) ) break;
292 :
293 0 : no_contact_info_dlist_ele_pop_head( purged->no_contact_info_dlist, purged->pool );
294 0 : purged_unindex( purged, head );
295 0 : nci_origin_map_ele_remove_fast( purged->nci_origin_map, head, purged->pool );
296 0 : purged_pool_ele_release( purged->pool, head );
297 :
298 0 : purged->metrics->purged_cnt--;
299 0 : purged->metrics->purged_expired_cnt++;
300 0 : }
301 6 : }
|
