Line data Source code
1 : #include "fd_collector_overrides.h"
2 : #include "../fd_rwlock.h"
3 : #include "../../util/fd_hash32.h"
4 :
5 400854 : #define FD_COLLECTOR_OVERRIDES_FORK_CNT (FD_COLLECTOR_OVERRIDES_MAX_FORK_WIDTH+1UL)
6 400854 : #define FD_COLLECTOR_OVERRIDES_MASK_WORD_CNT ((FD_COLLECTOR_OVERRIDES_FORK_CNT+63UL)/64UL)
7 :
8 : struct override_ele {
9 : fd_pubkey_t pubkey;
10 : ulong epoch;
11 : fd_pubkey_t inflation; /* valid iff has_inflation */
12 : fd_pubkey_t block; /* valid iff has_block */
13 : ulong mask[ FD_COLLECTOR_OVERRIDES_MASK_WORD_CNT ]; /* fork membership bits */
14 : uint next; /* pool / map chain */
15 : uint prev_multi;
16 : uint next_multi;
17 : uchar has_inflation;
18 : uchar has_block;
19 : };
20 : typedef struct override_ele override_ele_t;
21 :
22 : #define POOL_NAME override_pool
23 252 : #define POOL_T override_ele_t
24 12 : #define POOL_NEXT next
25 : #define POOL_IDX_T uint
26 : #define POOL_LAZY 1
27 : #include "../../util/tmpl/fd_pool.c"
28 :
29 : #define MAP_NAME override_map
30 : #define MAP_MULTI 1
31 : #define MAP_OPTIMIZE_RANDOM_ACCESS_REMOVAL 1
32 : #define MAP_KEY_T fd_pubkey_t
33 63 : #define MAP_ELE_T override_ele_t
34 222 : #define MAP_KEY pubkey
35 276 : #define MAP_KEY_EQ(k0,k1) (!memcmp( k0, k1, sizeof(fd_pubkey_t) ))
36 726 : #define MAP_KEY_HASH(key,seed) (fd_hash32( key->uc, seed ))
37 240 : #define MAP_PREV prev_multi
38 357 : #define MAP_NEXT next_multi
39 5286 : #define MAP_IDX_T uint
40 : #include "../../util/tmpl/fd_map_chain.c"
41 :
42 126 : #define FD_COLLECTOR_OVERRIDES_MAGIC (0xF17EDA2CC011EC70UL) /* FIREDANCER COLLECTOR V0 */
43 :
44 : struct fd_collector_overrides {
45 : ulong magic;
46 : ulong pool_off;
47 : ulong map_off;
48 :
49 : ulong forks_used[ FD_COLLECTOR_OVERRIDES_MASK_WORD_CNT ]; /* allocated fork id bits */
50 : ushort root_idx;
51 :
52 : fd_rwlock_t lock;
53 : };
54 : typedef struct fd_collector_overrides fd_collector_overrides_t;
55 :
56 : static inline override_ele_t *
57 4872 : get_pool( fd_collector_overrides_t const * co ) {
58 4872 : return fd_type_pun( (uchar *)co + co->pool_off );
59 4872 : }
60 :
61 : static inline override_map_t *
62 4851 : get_map( fd_collector_overrides_t const * co ) {
63 4851 : return fd_type_pun( (uchar *)co + co->map_off );
64 4851 : }
65 :
66 : static inline int
67 : mask_test( ulong const mask[ FD_COLLECTOR_OVERRIDES_MASK_WORD_CNT ],
68 258351 : ushort idx ) {
69 258351 : return !!( mask[ idx>>6 ] & (1UL<<(idx&63UL)) );
70 258351 : }
71 :
72 : static inline void
73 : mask_set( ulong mask[ FD_COLLECTOR_OVERRIDES_MASK_WORD_CNT ],
74 12825 : ushort idx ) {
75 12825 : mask[ idx>>6 ] |= (1UL<<(idx&63UL));
76 12825 : }
77 :
78 : static inline void
79 : mask_clear( ulong mask[ FD_COLLECTOR_OVERRIDES_MASK_WORD_CNT ],
80 102 : ushort idx ) {
81 102 : mask[ idx>>6 ] &= ~(1UL<<(idx&63UL));
82 102 : }
83 :
84 : static inline int
85 33 : mask_any( ulong const mask[ FD_COLLECTOR_OVERRIDES_MASK_WORD_CNT ] ) {
86 813 : for( ulong i=0UL; i<FD_COLLECTOR_OVERRIDES_MASK_WORD_CNT; i++ ) {
87 801 : if( mask[ i ] ) return 1;
88 801 : }
89 12 : return 0;
90 33 : }
91 :
92 : ulong
93 3078 : fd_collector_overrides_align( void ) {
94 3078 : return FD_COLLECTOR_OVERRIDES_ALIGN;
95 3078 : }
96 :
97 : ulong
98 513 : fd_collector_overrides_footprint( ulong max_overrides ) {
99 513 : ulong chain_cnt = override_map_chain_cnt_est( max_overrides );
100 :
101 513 : ulong l = FD_LAYOUT_INIT;
102 513 : l = FD_LAYOUT_APPEND( l, fd_collector_overrides_align(), sizeof(fd_collector_overrides_t) );
103 513 : l = FD_LAYOUT_APPEND( l, override_pool_align(), override_pool_footprint( max_overrides ) );
104 513 : l = FD_LAYOUT_APPEND( l, override_map_align(), override_map_footprint( chain_cnt ) );
105 513 : return FD_LAYOUT_FINI( l, fd_collector_overrides_align() );
106 513 : }
107 :
108 : void *
109 : fd_collector_overrides_new( void * shmem,
110 : ulong max_overrides,
111 126 : ulong seed ) {
112 126 : if( FD_UNLIKELY( !shmem ) ) {
113 0 : FD_LOG_WARNING(( "NULL shmem" ));
114 0 : return NULL;
115 0 : }
116 :
117 126 : if( FD_UNLIKELY( !fd_ulong_is_aligned( (ulong)shmem, fd_collector_overrides_align() ) ) ) {
118 0 : FD_LOG_WARNING(( "misaligned shmem" ));
119 0 : return NULL;
120 0 : }
121 :
122 126 : ulong chain_cnt = override_map_chain_cnt_est( max_overrides );
123 :
124 126 : FD_SCRATCH_ALLOC_INIT( l, shmem );
125 126 : fd_collector_overrides_t * co = FD_SCRATCH_ALLOC_APPEND( l, fd_collector_overrides_align(), sizeof(fd_collector_overrides_t) );
126 126 : void * pool_mem = FD_SCRATCH_ALLOC_APPEND( l, override_pool_align(), override_pool_footprint( max_overrides ) );
127 126 : void * map_mem = FD_SCRATCH_ALLOC_APPEND( l, override_map_align(), override_map_footprint( chain_cnt ) );
128 :
129 126 : override_ele_t * pool = override_pool_join( override_pool_new( pool_mem, max_overrides ) );
130 126 : if( FD_UNLIKELY( !pool ) ) {
131 0 : FD_LOG_WARNING(( "Failed to create collector overrides pool" ));
132 0 : return NULL;
133 0 : }
134 :
135 126 : override_map_t * map = override_map_join( override_map_new( map_mem, chain_cnt, seed ) );
136 126 : if( FD_UNLIKELY( !map ) ) {
137 0 : FD_LOG_WARNING(( "Failed to create collector overrides map" ));
138 0 : return NULL;
139 0 : }
140 :
141 126 : co->pool_off = (ulong)pool - (ulong)shmem;
142 126 : co->map_off = (ulong)map - (ulong)shmem;
143 126 : fd_memset( co->forks_used, 0, sizeof(co->forks_used) );
144 126 : co->forks_used[0] = 1UL; /* root */
145 126 : co->root_idx = 0;
146 :
147 126 : fd_rwlock_new( &co->lock );
148 :
149 126 : FD_COMPILER_MFENCE();
150 126 : FD_VOLATILE( co->magic ) = FD_COLLECTOR_OVERRIDES_MAGIC;
151 126 : FD_COMPILER_MFENCE();
152 :
153 126 : return co;
154 126 : }
155 :
156 : fd_collector_overrides_t *
157 126 : fd_collector_overrides_join( void * shmem ) {
158 126 : fd_collector_overrides_t * co = (fd_collector_overrides_t *)shmem;
159 :
160 126 : if( FD_UNLIKELY( !co ) ) {
161 0 : FD_LOG_WARNING(( "NULL collector overrides" ));
162 0 : return NULL;
163 0 : }
164 :
165 126 : if( FD_UNLIKELY( co->magic!=FD_COLLECTOR_OVERRIDES_MAGIC ) ) {
166 0 : FD_LOG_WARNING(( "Invalid collector overrides magic" ));
167 0 : return NULL;
168 0 : }
169 :
170 126 : return co;
171 126 : }
172 :
173 : ushort
174 12585 : fd_collector_overrides_new_child( fd_collector_overrides_t * co ) {
175 12585 : fd_rwlock_write( &co->lock );
176 :
177 12585 : ushort idx = USHORT_MAX;
178 400041 : for( ulong word_idx=0UL; word_idx<FD_COLLECTOR_OVERRIDES_MASK_WORD_CNT; word_idx++ ) {
179 400041 : ulong free = ~co->forks_used[ word_idx ];
180 400041 : if( FD_UNLIKELY( !free ) ) continue;
181 12585 : ulong candidate = (word_idx<<6) + (ulong)fd_ulong_find_lsb( free );
182 12585 : if( FD_UNLIKELY( candidate>FD_COLLECTOR_OVERRIDES_MAX_FORK_WIDTH ) ) break;
183 12585 : idx = (ushort)candidate;
184 12585 : break;
185 12585 : }
186 12585 : if( FD_UNLIKELY( idx==USHORT_MAX ) ) FD_LOG_CRIT(( "no free collector override forks" ));
187 12585 : mask_set( co->forks_used, idx );
188 :
189 12585 : fd_rwlock_unwrite( &co->lock );
190 12585 : return idx;
191 12585 : }
192 :
193 : void
194 : fd_collector_overrides_inherit( fd_collector_overrides_t * co,
195 : ushort parent_idx,
196 : ushort child_idx,
197 291 : ulong min_epoch ) {
198 291 : fd_rwlock_write( &co->lock );
199 :
200 291 : override_ele_t * pool = get_pool( co );
201 291 : override_map_t * map = get_map( co );
202 :
203 291 : for( override_map_iter_t iter = override_map_iter_init( map, pool );
204 318 : !override_map_iter_done( iter, map, pool );
205 291 : iter = override_map_iter_next( iter, map, pool ) ) {
206 27 : override_ele_t * ele = override_map_iter_ele( iter, map, pool );
207 27 : if( mask_test( ele->mask, parent_idx ) && ele->epoch>=min_epoch ) {
208 21 : mask_set( ele->mask, child_idx );
209 21 : }
210 27 : }
211 :
212 291 : fd_rwlock_unwrite( &co->lock );
213 291 : }
214 :
215 : /* Removes fork_idx from every entry, freeing entries with no
216 : remaining fork. Assumes the write lock is held. */
217 :
218 : static void
219 : release_fork( fd_collector_overrides_t * co,
220 69 : ushort fork_idx ) {
221 69 : override_ele_t * pool = get_pool( co );
222 69 : override_map_t * map = get_map( co );
223 :
224 69 : for( override_map_iter_t iter = override_map_iter_init( map, pool );
225 111 : !override_map_iter_done( iter, map, pool ); ) {
226 42 : override_ele_t * ele = override_map_iter_ele( iter, map, pool );
227 42 : iter = override_map_iter_next( iter, map, pool );
228 42 : if( !mask_test( ele->mask, fork_idx ) ) continue;
229 33 : mask_clear( ele->mask, fork_idx );
230 33 : if( FD_UNLIKELY( !mask_any( ele->mask ) ) ) {
231 12 : FD_TEST( override_map_ele_remove_fast( map, ele, pool ) );
232 12 : override_pool_ele_release( pool, ele );
233 12 : }
234 33 : }
235 :
236 69 : mask_clear( co->forks_used, fork_idx );
237 69 : }
238 :
239 : void
240 : fd_collector_overrides_advance_root( fd_collector_overrides_t * co,
241 516 : ushort root_idx ) {
242 516 : fd_rwlock_write( &co->lock );
243 :
244 516 : if( FD_LIKELY( root_idx==co->root_idx ) ) {
245 453 : fd_rwlock_unwrite( &co->lock );
246 453 : return;
247 453 : }
248 :
249 258174 : for( ulong i=0UL; i<=FD_COLLECTOR_OVERRIDES_MAX_FORK_WIDTH; i++ ) {
250 258111 : if( i!=(ulong)root_idx && mask_test( co->forks_used, (ushort)i ) ) release_fork( co, (ushort)i );
251 258111 : }
252 63 : co->root_idx = root_idx;
253 :
254 63 : fd_rwlock_unwrite( &co->lock );
255 63 : }
256 :
257 : void
258 : fd_collector_overrides_purge_child( fd_collector_overrides_t * co,
259 6 : ushort fork_idx ) {
260 6 : fd_rwlock_write( &co->lock );
261 :
262 6 : if( FD_UNLIKELY( fork_idx==co->root_idx ) ) {
263 0 : fd_rwlock_unwrite( &co->lock );
264 0 : return;
265 0 : }
266 :
267 6 : release_fork( co, fork_idx );
268 :
269 6 : fd_rwlock_unwrite( &co->lock );
270 6 : }
271 :
272 : void
273 3987 : fd_collector_overrides_reset( fd_collector_overrides_t * co ) {
274 3987 : fd_rwlock_write( &co->lock );
275 :
276 3987 : override_map_reset( get_map( co ) );
277 3987 : override_pool_reset( get_pool( co ) );
278 3987 : fd_memset( co->forks_used, 0, sizeof(co->forks_used) );
279 3987 : co->forks_used[0] = 1UL;
280 3987 : co->root_idx = 0;
281 :
282 3987 : fd_rwlock_unwrite( &co->lock );
283 3987 : }
284 :
285 : ushort
286 4095 : fd_collector_overrides_get_root_idx( fd_collector_overrides_t * co ) {
287 4095 : fd_rwlock_read( &co->lock );
288 4095 : ushort idx = co->root_idx;
289 4095 : fd_rwlock_unread( &co->lock );
290 4095 : return idx;
291 4095 : }
292 :
293 : void
294 : fd_collector_overrides_upsert( fd_collector_overrides_t * co,
295 : ushort fork_idx,
296 : ulong epoch,
297 : fd_pubkey_t const * pubkey,
298 : int has_inflation,
299 : fd_pubkey_t const * inflation,
300 : int has_block,
301 219 : fd_pubkey_t const * block ) {
302 219 : FD_TEST( has_inflation || has_block );
303 :
304 219 : fd_rwlock_write( &co->lock );
305 :
306 219 : override_ele_t * pool = get_pool( co );
307 219 : override_map_t * map = get_map( co );
308 :
309 : /* Join an existing identical entry (captured by a sibling fork) if
310 : one exists. */
311 219 : for( uint idx = (uint)override_map_idx_query_const( map, pubkey, UINT_MAX, pool );
312 234 : idx!=UINT_MAX;
313 219 : idx = (uint)override_map_idx_next_const( idx, UINT_MAX, pool ) ) {
314 18 : override_ele_t * ele = override_pool_ele( pool, idx );
315 18 : if( ele->epoch!=epoch ) continue;
316 6 : if( ele->has_inflation!=(uchar)!!has_inflation ) continue;
317 6 : if( ele->has_block!=(uchar)!!has_block ) continue;
318 6 : if( has_inflation && !fd_pubkey_eq( &ele->inflation, inflation ) ) continue;
319 3 : if( has_block && !fd_pubkey_eq( &ele->block, block ) ) continue;
320 3 : mask_set( ele->mask, fork_idx );
321 3 : fd_rwlock_unwrite( &co->lock );
322 3 : return;
323 3 : }
324 :
325 216 : if( FD_UNLIKELY( !override_pool_free( pool ) ) ) {
326 0 : FD_LOG_CRIT(( "collector overrides pool is full" ));
327 0 : }
328 :
329 216 : override_ele_t * ele = override_pool_ele_acquire( pool );
330 216 : ele->pubkey = *pubkey;
331 216 : ele->epoch = epoch;
332 216 : ele->has_inflation = (uchar)!!has_inflation;
333 216 : ele->has_block = (uchar)!!has_block;
334 216 : ele->inflation = has_inflation ? *inflation : (fd_pubkey_t){0};
335 216 : ele->block = has_block ? *block : (fd_pubkey_t){0};
336 216 : fd_memset( ele->mask, 0, sizeof(ele->mask) );
337 216 : mask_set( ele->mask, fork_idx );
338 216 : FD_TEST( override_map_ele_insert( map, ele, pool ) );
339 :
340 216 : fd_rwlock_unwrite( &co->lock );
341 216 : }
342 :
343 : int
344 : fd_collector_overrides_query( fd_collector_overrides_t * co,
345 : ushort fork_idx,
346 : ulong epoch,
347 : fd_pubkey_t const * pubkey,
348 : fd_pubkey_t * inflation_out_opt,
349 285 : fd_pubkey_t * block_out_opt ) {
350 285 : fd_rwlock_read( &co->lock );
351 :
352 285 : override_ele_t * pool = get_pool( co );
353 285 : override_map_t * map = get_map( co );
354 :
355 285 : int flags = 0;
356 285 : for( uint idx = (uint)override_map_idx_query_const( map, pubkey, UINT_MAX, pool );
357 321 : idx!=UINT_MAX;
358 285 : idx = (uint)override_map_idx_next_const( idx, UINT_MAX, pool ) ) {
359 258 : override_ele_t const * ele = override_pool_ele_const( pool, idx );
360 258 : if( ele->epoch!=epoch ) continue;
361 234 : if( !mask_test( ele->mask, fork_idx ) ) continue;
362 222 : if( ele->has_inflation ) {
363 87 : flags |= FD_COLLECTOR_OVERRIDE_INFLATION;
364 87 : if( inflation_out_opt ) *inflation_out_opt = ele->inflation;
365 87 : }
366 222 : if( ele->has_block ) {
367 153 : flags |= FD_COLLECTOR_OVERRIDE_BLOCK;
368 153 : if( block_out_opt ) *block_out_opt = ele->block;
369 153 : }
370 222 : break;
371 234 : }
372 :
373 285 : fd_rwlock_unread( &co->lock );
374 285 : return flags;
375 285 : }
376 :
377 : ulong
378 21 : fd_collector_overrides_ele_cnt( fd_collector_overrides_t * co ) {
379 21 : fd_rwlock_read( &co->lock );
380 21 : ulong cnt = override_pool_used( get_pool( co ) );
381 21 : fd_rwlock_unread( &co->lock );
382 21 : return cnt;
383 21 : }
|
