Line data Source code
1 : #include "fd_progcache.h"
2 : #include "fd_progcache_admin.h"
3 : #include "fd_progcache_base.h"
4 : #include "fd_progcache_clock.h"
5 : #include "fd_progcache_rec.h"
6 : #include "fd_progcache_reclaim.h"
7 : #include "../../util/racesan/fd_racesan_target.h"
8 : #include "../../util/wksp/fd_wksp_private.h"
9 :
10 : /* FIXME get rid of this thread-local */
11 : FD_TL fd_progcache_admin_metrics_t fd_progcache_admin_metrics_g;
12 :
13 : /* Algorithm to estimate size of cache metadata structures (rec_pool
14 : object pool and rec_map hashchain table).
15 :
16 : FIXME Carefully balance this */
17 :
18 : static ulong
19 : fd_progcache_est_rec_max1( ulong wksp_footprint,
20 0 : ulong mean_cache_entry_size ) {
21 0 : return wksp_footprint / mean_cache_entry_size;
22 0 : }
23 :
24 : ulong
25 : fd_progcache_est_rec_max( ulong wksp_footprint,
26 0 : ulong mean_cache_entry_size ) {
27 0 : ulong est = fd_progcache_est_rec_max1( wksp_footprint, mean_cache_entry_size );
28 0 : if( FD_UNLIKELY( est>(1UL<<31) ) ) FD_LOG_ERR(( "fd_progcache_est_rec_max(wksp_footprint=%lu,mean_cache_entry_size=%lu) failed: invalid parameters", wksp_footprint, mean_cache_entry_size ));
29 0 : return fd_ulong_max( est, 2048UL );
30 0 : }
31 :
32 : /* Begin transaction-level operations. It is assumed that txn data
33 : structures are not concurrently modified. This includes txn_pool and
34 : txn_map. */
35 :
36 : void
37 : fd_progcache_attach_child( fd_progcache_join_t * cache,
38 : fd_xid_t const * xid_parent,
39 285 : fd_xid_t const * xid_new ) {
40 285 : fd_rwlock_write( &cache->shmem->txn.rwlock );
41 :
42 285 : if( FD_UNLIKELY( fd_prog_txnm_idx_query_const( cache->txn.map, xid_new, ULONG_MAX, cache->txn.pool )!=ULONG_MAX ) ) {
43 0 : FD_LOG_ERR(( "fd_progcache_attach_child failed: xid %lu:%lu already in use",
44 0 : xid_new->ul[0], xid_new->ul[1] ));
45 0 : }
46 285 : if( FD_UNLIKELY( fd_prog_txnp_free( cache->txn.pool )==0UL ) ) {
47 0 : FD_LOG_ERR(( "fd_progcache_attach_child failed: transaction object pool out of memory" ));
48 0 : }
49 :
50 285 : ulong txn_max = fd_prog_txnp_max( cache->txn.pool );
51 285 : ulong parent_idx;
52 285 : uint * _child_head_idx;
53 285 : uint * _child_tail_idx;
54 :
55 285 : if( FD_UNLIKELY( fd_funk_txn_xid_eq( xid_parent, cache->shmem->txn.last_publish ) ) ) {
56 :
57 171 : parent_idx = FD_FUNK_TXN_IDX_NULL;
58 :
59 171 : _child_head_idx = &cache->shmem->txn.child_head_idx;
60 171 : _child_tail_idx = &cache->shmem->txn.child_tail_idx;
61 :
62 171 : } else {
63 :
64 114 : parent_idx = fd_prog_txnm_idx_query( cache->txn.map, xid_parent, ULONG_MAX, cache->txn.pool );
65 114 : if( FD_UNLIKELY( parent_idx==ULONG_MAX ) ) {
66 0 : FD_LOG_CRIT(( "fd_progcache_attach_child failed: user provided invalid parent XID %lu:%lu",
67 0 : xid_parent->ul[0], xid_parent->ul[1] ));
68 0 : }
69 114 : if( FD_UNLIKELY( parent_idx >= txn_max ) )
70 0 : FD_LOG_CRIT(( "progcache: corruption detected (attach_child parent_idx=%lu txn_max=%lu)", parent_idx, txn_max ));
71 :
72 114 : _child_head_idx = &cache->txn.pool[ parent_idx ].child_head_idx;
73 114 : _child_tail_idx = &cache->txn.pool[ parent_idx ].child_tail_idx;
74 :
75 114 : }
76 :
77 285 : uint txn_idx = (uint)fd_prog_txnp_idx_acquire( cache->txn.pool );
78 285 : if( FD_UNLIKELY( txn_idx==UINT_MAX ) ) FD_LOG_ERR(( "fd_progcache_attach_child failed: transaction object pool out of memory" ));
79 285 : fd_progcache_txn_t * txn = &cache->txn.pool[ txn_idx ];
80 285 : fd_funk_txn_xid_copy( &txn->xid, xid_new );
81 :
82 285 : uint sibling_prev_idx = *_child_tail_idx;
83 :
84 285 : int first_born = sibling_prev_idx==UINT_MAX;
85 285 : if( FD_UNLIKELY( !first_born && (ulong)sibling_prev_idx >= txn_max ) )
86 0 : FD_LOG_CRIT(( "progcache: corruption detected (attach_child sibling_prev_idx=%u txn_max=%lu)", sibling_prev_idx, txn_max ));
87 :
88 285 : txn->parent_idx = (uint)parent_idx;
89 285 : txn->child_head_idx = UINT_MAX;
90 285 : txn->child_tail_idx = UINT_MAX;
91 285 : txn->sibling_prev_idx = (uint)sibling_prev_idx;
92 285 : txn->sibling_next_idx = UINT_MAX;
93 :
94 285 : txn->rec_head_idx = UINT_MAX;
95 285 : txn->rec_tail_idx = UINT_MAX;
96 :
97 : /* TODO: consider branchless impl */
98 285 : if( FD_LIKELY( first_born ) ) *_child_head_idx = (uint)txn_idx; /* opt for non-compete */
99 6 : else cache->txn.pool[ sibling_prev_idx ].sibling_next_idx = (uint)txn_idx;
100 :
101 285 : *_child_tail_idx = (uint)txn_idx;
102 :
103 285 : fd_prog_txnm_idx_insert( cache->txn.map, txn_idx, cache->txn.pool );
104 :
105 285 : fd_rwlock_unwrite( &cache->shmem->txn.rwlock );
106 285 : }
107 :
108 : static void
109 : fd_progcache_cancel_one( fd_progcache_join_t * cache,
110 183 : fd_progcache_txn_t * txn ) {
111 183 : ulong rec_max = fd_prog_recp_ele_max( cache->rec.pool );
112 183 : ulong txn_max = fd_prog_txnp_max( cache->txn.pool );
113 :
114 183 : fd_rwlock_write( &txn->lock );
115 :
116 183 : if( FD_UNLIKELY( txn->child_head_idx!=UINT_MAX ||
117 183 : txn->child_tail_idx!=UINT_MAX ) ) {
118 0 : FD_LOG_CRIT(( "fd_progcache_cancel failed: txn at %p with xid %lu:%lu has children (data corruption?)",
119 0 : (void *)txn, txn->xid.ul[0], txn->xid.ul[1] ));
120 0 : }
121 :
122 : /* Remove records */
123 :
124 192 : for( uint idx = txn->rec_head_idx; idx!=UINT_MAX; idx = cache->rec.pool->ele[ idx ].next_idx ) {
125 9 : if( FD_UNLIKELY( (ulong)idx >= rec_max ) )
126 0 : FD_LOG_CRIT(( "progcache: corruption detected (cancel_one rec_idx=%u rec_max=%lu)", idx, rec_max ));
127 9 : atomic_store_explicit( &cache->rec.pool->ele[ idx ].txn_idx, UINT_MAX, memory_order_release );
128 9 : fd_racesan_hook( "prog_cancel_one:post_orphan" );
129 9 : fd_prog_delete_rec( cache, &cache->rec.pool->ele[ idx ] );
130 9 : }
131 :
132 183 : txn->rec_head_idx = UINT_MAX;
133 183 : txn->rec_tail_idx = UINT_MAX;
134 :
135 : /* Remove transaction from fork graph */
136 :
137 183 : uint self_idx = (uint)( txn - cache->txn.pool );
138 183 : uint prev_idx = txn->sibling_prev_idx;
139 183 : uint next_idx = txn->sibling_next_idx;
140 183 : if( next_idx!=UINT_MAX ) {
141 0 : if( FD_UNLIKELY( (ulong)next_idx >= txn_max ) )
142 0 : FD_LOG_CRIT(( "progcache: corruption detected (cancel_one sibling_next_idx=%u txn_max=%lu)", next_idx, txn_max ));
143 0 : cache->txn.pool[ next_idx ].sibling_prev_idx = prev_idx;
144 0 : }
145 183 : if( prev_idx!=UINT_MAX ) {
146 6 : if( FD_UNLIKELY( (ulong)prev_idx >= txn_max ) )
147 0 : FD_LOG_CRIT(( "progcache: corruption detected (cancel_one sibling_prev_idx=%u txn_max=%lu)", prev_idx, txn_max ));
148 6 : cache->txn.pool[ prev_idx ].sibling_next_idx = next_idx;
149 6 : }
150 183 : if( txn->parent_idx!=UINT_MAX ) {
151 108 : if( FD_UNLIKELY( (ulong)txn->parent_idx >= txn_max ) )
152 0 : FD_LOG_CRIT(( "progcache: corruption detected (cancel_one parent_idx=%u txn_max=%lu)", txn->parent_idx, txn_max ));
153 108 : fd_progcache_txn_t * parent = &cache->txn.pool[ txn->parent_idx ];
154 108 : if( parent->child_head_idx==self_idx ) parent->child_head_idx = next_idx;
155 108 : if( parent->child_tail_idx==self_idx ) parent->child_tail_idx = prev_idx;
156 108 : } else {
157 75 : if( cache->shmem->txn.child_head_idx==self_idx ) cache->shmem->txn.child_head_idx = next_idx;
158 75 : if( cache->shmem->txn.child_tail_idx==self_idx ) cache->shmem->txn.child_tail_idx = prev_idx;
159 75 : }
160 :
161 : /* Remove transaction from index */
162 :
163 183 : if( FD_UNLIKELY( !fd_prog_txnm_ele_remove( cache->txn.map, &txn->xid, NULL, cache->txn.pool ) ) ) {
164 0 : FD_LOG_CRIT(( "fd_progcache_cancel failed: fd_funk_txn_map_remove(%lu:%lu) failed",
165 0 : txn->xid.ul[0], txn->xid.ul[1] ));
166 0 : }
167 :
168 : /* Free transaction object */
169 :
170 183 : fd_rwlock_unwrite( &txn->lock );
171 183 : fd_prog_txnp_ele_release( cache->txn.pool, txn );
172 183 : }
173 :
174 : /* Cancels txn and all children */
175 :
176 : static void
177 : fd_progcache_cancel_tree( fd_progcache_join_t * cache,
178 183 : fd_progcache_txn_t * txn ) {
179 183 : ulong txn_max = fd_prog_txnp_max( cache->txn.pool );
180 186 : for(;;) {
181 186 : uint child_idx = txn->child_head_idx;
182 186 : if( child_idx==UINT_MAX ) break;
183 3 : if( FD_UNLIKELY( (ulong)child_idx >= txn_max ) )
184 0 : FD_LOG_CRIT(( "progcache: corruption detected (cancel_tree child_idx=%u txn_max=%lu)", child_idx, txn_max ));
185 3 : fd_progcache_txn_t * child = &cache->txn.pool[ child_idx ];
186 3 : fd_progcache_cancel_tree( cache, child );
187 3 : }
188 183 : fd_progcache_cancel_one( cache, txn );
189 183 : }
190 :
191 : /* Cancels all left/right siblings */
192 :
193 : static void
194 : fd_progcache_cancel_prev_list( fd_progcache_join_t * cache,
195 15 : fd_progcache_txn_t * txn ) {
196 15 : ulong txn_max = fd_prog_txnp_max( cache->txn.pool );
197 15 : uint cur_idx = txn->sibling_prev_idx;
198 15 : while( cur_idx!=UINT_MAX ) {
199 0 : if( FD_UNLIKELY( (ulong)cur_idx >= txn_max ) )
200 0 : FD_LOG_CRIT(( "progcache: corruption detected (cancel_prev_list txn_idx=%u txn_max=%lu)", cur_idx, txn_max ));
201 0 : fd_progcache_txn_t * sibling = &cache->txn.pool[ cur_idx ];
202 0 : uint next = sibling->sibling_prev_idx;
203 0 : fd_progcache_cancel_tree( cache, sibling );
204 0 : cur_idx = next;
205 0 : }
206 15 : }
207 :
208 : static void
209 : fd_progcache_cancel_next_list( fd_progcache_join_t * cache,
210 15 : fd_progcache_txn_t * txn ) {
211 15 : ulong txn_max = fd_prog_txnp_max( cache->txn.pool );
212 15 : uint cur_idx = txn->sibling_next_idx;
213 15 : while( cur_idx!=UINT_MAX ) {
214 0 : if( FD_UNLIKELY( (ulong)cur_idx >= txn_max ) )
215 0 : FD_LOG_CRIT(( "progcache: corruption detected (cancel_next_list txn_idx=%u txn_max=%lu)", cur_idx, txn_max ));
216 0 : fd_progcache_txn_t * sibling = &cache->txn.pool[ cur_idx ];
217 0 : uint next = sibling->sibling_next_idx;
218 0 : fd_progcache_cancel_tree( cache, sibling );
219 0 : cur_idx = next;
220 0 : }
221 15 : }
222 :
223 : /* Move list of records to root txn (advance_root)
224 :
225 : For each record to be rooted:
226 : - gc_root to remove any shadowed rooted revision
227 : - drain readers
228 : - release if invalidation (which are now a no-op) */
229 :
230 : static void
231 : fd_progcache_txn_publish_release( fd_progcache_join_t * cache,
232 15 : uint head ) {
233 15 : ulong rec_max = fd_prog_recp_ele_max( cache->rec.pool );
234 24 : while( head!=UINT_MAX ) {
235 9 : if( FD_UNLIKELY( (ulong)head >= rec_max ) )
236 0 : FD_LOG_CRIT(( "progcache: corruption detected (publish_release rec_idx=%u rec_max=%lu)", head, rec_max ));
237 9 : fd_progcache_rec_t * rec = &cache->rec.pool->ele[ head ];
238 9 : uint next = rec->next_idx;
239 :
240 : /* Lock rec_map chain */
241 9 : struct {
242 9 : fd_prog_recm_txn_t txn[1];
243 9 : fd_prog_recm_txn_private_info_t info[1];
244 9 : } _map_txn;
245 9 : fd_prog_recm_txn_t * map_txn = fd_prog_recm_txn_init( _map_txn.txn, cache->rec.map, 1UL );
246 9 : fd_prog_recm_txn_add( map_txn, &rec->pair, 1 );
247 9 : int txn_err = fd_prog_recm_txn_try( map_txn, FD_MAP_FLAG_BLOCKING );
248 9 : if( FD_UNLIKELY( txn_err!=FD_MAP_SUCCESS ) ) {
249 0 : FD_LOG_CRIT(( "Failed to insert progcache record: cannot lock funk rec map chain: %i-%s", txn_err, fd_map_strerror( txn_err ) ));
250 0 : }
251 :
252 : /* Evict previous root value */
253 9 : fd_funk_xid_key_pair_t pair[1];
254 9 : fd_funk_rec_key_copy( pair->key, rec->pair.key );
255 9 : fd_funk_txn_xid_set_root( pair->xid );
256 9 : if( fd_prog_delete_rec_by_key( cache, pair, 0 )>=0 ) {
257 6 : fd_progcache_admin_metrics_g.gc_root_cnt++;
258 6 : }
259 :
260 : /* Migrate record to root */
261 9 : fd_rwlock_write( &rec->lock );
262 9 : fd_racesan_hook( "prog_publish_release:pre_retag" );
263 9 : rec->prev_idx = UINT_MAX;
264 9 : rec->next_idx = UINT_MAX;
265 9 : atomic_store_explicit( &rec->txn_idx, UINT_MAX, memory_order_release );
266 9 : fd_xid_t const root = { .ul = { ULONG_MAX, ULONG_MAX } };
267 9 : fd_funk_txn_xid_st_atomic( rec->pair.xid, &root );
268 9 : fd_rwlock_unwrite( &rec->lock );
269 9 : fd_progcache_admin_metrics_g.root_cnt++;
270 :
271 : /* Unlock rec_map chain */
272 9 : int test_err = fd_prog_recm_txn_test( map_txn );
273 9 : if( FD_UNLIKELY( test_err!=FD_MAP_SUCCESS ) ) FD_LOG_CRIT(( "fd_prog_recm_txn_test failed: %i-%s", test_err, fd_map_strerror( test_err ) ));
274 9 : fd_prog_recm_txn_fini( map_txn );
275 :
276 9 : head = next;
277 9 : }
278 15 : }
279 :
280 : /* fd_progcache_txn_publish_one merges an in-prep transaction whose
281 : parent is the last published, into the parent. */
282 :
283 : static uint
284 : fd_progcache_txn_publish_one( fd_progcache_join_t * cache,
285 15 : fd_progcache_txn_t * txn ) {
286 :
287 : /* Phase 1: Mark transaction as "last published" */
288 :
289 15 : fd_xid_t const xid = txn->xid;
290 15 : if( FD_UNLIKELY( txn->parent_idx!=UINT_MAX ) ) {
291 0 : FD_LOG_CRIT(( "fd_progcache_publish failed: txn with xid %lu:%lu is not a child of the last published txn", xid.ul[0], xid.ul[1] ));
292 0 : }
293 15 : fd_racesan_hook( "prog_publish_one:pre_xid_store" );
294 15 : fd_funk_txn_xid_st_atomic( cache->shmem->txn.last_publish, &xid );
295 :
296 : /* Phase 2: Drain inserters from transaction */
297 :
298 15 : fd_rwlock_write( &txn->lock );
299 :
300 : /* Phase 3: Detach records */
301 :
302 15 : ulong rec_max = fd_prog_recp_ele_max( cache->rec.pool );
303 24 : for( uint idx = txn->rec_head_idx; idx!=UINT_MAX; idx = cache->rec.pool->ele[ idx ].next_idx ) {
304 9 : if( FD_UNLIKELY( (ulong)idx >= rec_max ) )
305 0 : FD_LOG_CRIT(( "progcache: corruption detected (publish_one rec_idx=%u rec_max=%lu)", idx, rec_max ));
306 9 : atomic_store_explicit( &cache->rec.pool->ele[ idx ].txn_idx, UINT_MAX, memory_order_release );
307 9 : }
308 :
309 15 : uint rec_head = txn->rec_head_idx;
310 15 : txn->rec_head_idx = UINT_MAX;
311 15 : txn->rec_tail_idx = UINT_MAX;
312 :
313 : /* Phase 4: Remove transaction from fork graph */
314 :
315 15 : { /* Adjust the parent pointers of the children to point to "last published" */
316 15 : ulong txn_max = fd_prog_txnp_max( cache->txn.pool );
317 15 : ulong child_idx = txn->child_head_idx;
318 21 : while( child_idx!=UINT_MAX ) {
319 6 : if( FD_UNLIKELY( child_idx >= txn_max ) )
320 0 : FD_LOG_CRIT(( "progcache: corruption detected (publish_one child_idx=%lu txn_max=%lu)", child_idx, txn_max ));
321 6 : cache->txn.pool[ child_idx ].parent_idx = UINT_MAX;
322 6 : child_idx = cache->txn.pool[ child_idx ].sibling_next_idx;
323 6 : }
324 15 : }
325 :
326 : /* Phase 5: Remove transaction from index */
327 :
328 15 : if( FD_UNLIKELY( fd_prog_txnm_idx_remove( cache->txn.map, &txn->xid, ULONG_MAX, cache->txn.pool )==ULONG_MAX ) ) {
329 0 : FD_LOG_CRIT(( "fd_progcache_publish failed: fd_funk_txn_map_remove(%lu:%lu) failed",
330 0 : xid.ul[0], xid.ul[1] ));
331 0 : }
332 :
333 : /* Phase 6: Free transaction object */
334 :
335 15 : fd_rwlock_unwrite( &txn->lock );
336 15 : txn->parent_idx = UINT_MAX;
337 15 : txn->sibling_prev_idx = UINT_MAX;
338 15 : txn->sibling_next_idx = UINT_MAX;
339 15 : txn->child_head_idx = UINT_MAX;
340 15 : txn->child_tail_idx = UINT_MAX;
341 15 : fd_prog_txnp_ele_release( cache->txn.pool, txn );
342 :
343 15 : return rec_head;
344 15 : }
345 :
346 : void
347 : fd_progcache_advance_root( fd_progcache_join_t * cache,
348 15 : fd_xid_t const * xid ) {
349 :
350 : /* Detach records from txns without acquiring record locks */
351 :
352 15 : fd_rwlock_write( &cache->shmem->txn.rwlock );
353 :
354 15 : ulong txn_max = fd_prog_txnp_max( cache->txn.pool );
355 15 : uint txn_idx = (uint)fd_prog_txnm_idx_query( cache->txn.map, xid, UINT_MAX, cache->txn.pool );
356 15 : if( FD_UNLIKELY( txn_idx==UINT_MAX ) ) {
357 0 : FD_LOG_CRIT(( "fd_progcache_advance_root failed: invalid XID %lu:%lu",
358 0 : xid->ul[0], xid->ul[1] ));
359 0 : }
360 15 : if( FD_UNLIKELY( (ulong)txn_idx >= txn_max ) )
361 0 : FD_LOG_CRIT(( "progcache: corruption detected (advance_root txn_idx=%u txn_max=%lu)", txn_idx, txn_max ));
362 15 : fd_progcache_txn_t * txn = &cache->txn.pool[ txn_idx ];
363 15 : if( FD_UNLIKELY( txn->parent_idx!=UINT_MAX ) ) {
364 0 : FD_LOG_CRIT(( "fd_progcache_advance_root: parent of txn %lu:%lu is not root", xid->ul[0], xid->ul[1] ));
365 0 : }
366 :
367 15 : fd_progcache_cancel_prev_list( cache, txn );
368 15 : fd_progcache_cancel_next_list( cache, txn );
369 :
370 15 : txn->sibling_prev_idx = UINT_MAX;
371 15 : txn->sibling_next_idx = UINT_MAX;
372 15 : cache->shmem->txn.child_head_idx = txn->child_head_idx;
373 15 : cache->shmem->txn.child_tail_idx = txn->child_tail_idx;
374 :
375 15 : uint publish_head = fd_progcache_txn_publish_one( cache, txn );
376 :
377 15 : fd_rwlock_unwrite( &cache->shmem->txn.rwlock );
378 :
379 : /* Update records */
380 :
381 15 : fd_progcache_txn_publish_release( cache, publish_head );
382 15 : fd_prog_reclaim_work( cache );
383 15 : }
384 :
385 : void
386 : fd_progcache_cancel( fd_progcache_join_t * cache,
387 180 : fd_xid_t const * xid ) {
388 :
389 180 : fd_rwlock_write( &cache->shmem->txn.rwlock );
390 180 : fd_progcache_txn_t * txn = fd_prog_txnm_ele_query( cache->txn.map, xid, NULL, cache->txn.pool );
391 180 : if( FD_UNLIKELY( !txn ) ) {
392 0 : FD_LOG_CRIT(( "fd_progcache_cancel failed: invalid XID %lu:%lu",
393 0 : xid->ul[0], xid->ul[1] ));
394 0 : }
395 180 : fd_progcache_cancel_tree( cache, txn );
396 180 : fd_rwlock_unwrite( &cache->shmem->txn.rwlock );
397 180 : fd_prog_reclaim_work( cache );
398 180 : }
399 :
400 : /* reset_txn_list does a depth-first traversal of the txn tree.
401 : Detaches all recs from txns by emptying rec linked lists. */
402 :
403 : static void
404 : reset_txn_list( fd_progcache_join_t * cache,
405 0 : uint txn_head_idx ) {
406 0 : ulong txn_max = fd_prog_txnp_max( cache->txn.pool );
407 0 : for( uint idx = txn_head_idx; idx!=UINT_MAX; ) {
408 0 : if( FD_UNLIKELY( (ulong)idx >= txn_max ) )
409 0 : FD_LOG_CRIT(( "progcache: corruption detected (reset_txn_list txn_idx=%u txn_max=%lu)", idx, txn_max ));
410 0 : fd_progcache_txn_t * txn = &cache->txn.pool[ idx ];
411 0 : txn->rec_head_idx = UINT_MAX;
412 0 : txn->rec_tail_idx = UINT_MAX;
413 0 : reset_txn_list( cache, txn->child_head_idx );
414 0 : idx = txn->sibling_next_idx;
415 0 : }
416 0 : }
417 :
418 : /* reset_rec_map frees all records in a funk instance. */
419 :
420 : static void
421 0 : reset_rec_map( fd_progcache_join_t * cache ) {
422 0 : fd_progcache_rec_t * rec0 = cache->rec.pool->ele;
423 0 : ulong chain_cnt = fd_prog_recm_chain_cnt( cache->rec.map );
424 0 : for( ulong chain_idx=0UL; chain_idx<chain_cnt; chain_idx++ ) {
425 0 : for(
426 0 : fd_prog_recm_iter_t iter = fd_prog_recm_iter( cache->rec.map, chain_idx );
427 0 : !fd_prog_recm_iter_done( iter );
428 0 : ) {
429 0 : fd_progcache_rec_t * rec = fd_prog_recm_iter_ele( iter );
430 0 : ulong next = fd_prog_recm_private_idx( rec->map_next );
431 :
432 0 : if( rec->exists ) {
433 0 : fd_prog_recm_query_t rec_query[1];
434 0 : int err = fd_prog_recm_remove( cache->rec.map, &rec->pair, NULL, rec_query, FD_MAP_FLAG_BLOCKING );
435 0 : if( FD_UNLIKELY( err!=FD_MAP_SUCCESS ) ) FD_LOG_CRIT(( "fd_prog_recm_remove failed (%i-%s)", err, fd_map_strerror( err ) ));
436 0 : fd_progcache_val_free( rec, cache );
437 0 : }
438 :
439 0 : rec->exists = 0;
440 0 : fd_prog_clock_remove( cache->clock.bits, (ulong)( rec-rec0 ) );
441 0 : fd_prog_recp_release( cache->rec.pool, rec, 1 );
442 0 : iter.ele_idx = next;
443 0 : }
444 0 : }
445 0 : }
446 :
447 : void
448 0 : fd_progcache_reset( fd_progcache_join_t * cache ) {
449 0 : reset_txn_list( cache, cache->shmem->txn.child_head_idx );
450 0 : reset_rec_map( cache );
451 0 : }
452 :
453 : /* clear_txn_list does a depth-first traversal of the txn tree.
454 : Removes all txns. */
455 :
456 : static void
457 : clear_txn_list( fd_progcache_join_t * join,
458 0 : uint txn_head_idx ) {
459 0 : ulong txn_max = fd_prog_txnp_max( join->txn.pool );
460 0 : for( uint idx = txn_head_idx; idx!=UINT_MAX; ) {
461 0 : if( FD_UNLIKELY( (ulong)idx >= txn_max ) )
462 0 : FD_LOG_CRIT(( "progcache: corruption detected (clear_txn_list txn_idx=%u txn_max=%lu)", idx, txn_max ));
463 0 : fd_progcache_txn_t * txn = &join->txn.pool[ idx ];
464 0 : uint next_idx = txn->sibling_next_idx;
465 0 : uint child_idx = txn->child_head_idx;
466 0 : txn->rec_head_idx = UINT_MAX;
467 0 : txn->rec_tail_idx = UINT_MAX;
468 0 : txn->child_head_idx = UINT_MAX;
469 0 : txn->child_tail_idx = UINT_MAX;
470 0 : txn->parent_idx = UINT_MAX;
471 0 : txn->sibling_prev_idx = UINT_MAX;
472 0 : txn->sibling_next_idx = UINT_MAX;
473 0 : clear_txn_list( join, child_idx );
474 0 : if( FD_UNLIKELY( !fd_prog_txnm_ele_remove( join->txn.map, &txn->xid, NULL, join->txn.pool ) ) ) FD_LOG_CRIT(( "fd_prog_txnm_ele_remove failed" ));
475 0 : fd_prog_txnp_ele_release( join->txn.pool, txn );
476 0 : idx = next_idx;
477 0 : }
478 0 : }
479 :
480 : void
481 0 : fd_progcache_clear( fd_progcache_join_t * cache ) {
482 0 : clear_txn_list( cache, cache->shmem->txn.child_head_idx );
483 0 : cache->shmem->txn.child_head_idx = UINT_MAX;
484 0 : cache->shmem->txn.child_tail_idx = UINT_MAX;
485 0 : reset_rec_map( cache );
486 0 : }
487 :
488 : static int
489 : fd_progcache_verify_siblings( fd_progcache_txn_t * pool,
490 : ulong txn_max,
491 : uint head_idx,
492 : uint tail_idx,
493 : uint expected_parent_idx,
494 : uint * stack,
495 84 : ulong * stack_top ) {
496 :
497 204 : # define TEST(c) do { \
498 204 : if( FD_UNLIKELY( !(c) ) ) { FD_LOG_WARNING(( "FAIL: %s", #c )); return -1; } \
499 204 : } while(0)
500 :
501 84 : TEST( (head_idx==UINT_MAX)==(tail_idx==UINT_MAX) );
502 :
503 84 : uint last_idx = UINT_MAX;
504 93 : for( uint idx = head_idx; idx!=UINT_MAX; ) {
505 9 : TEST( idx<txn_max );
506 9 : fd_progcache_txn_t * child = &pool[ idx ];
507 9 : TEST( !child->tag );
508 9 : TEST( child->parent_idx==expected_parent_idx );
509 9 : child->tag = 1;
510 9 : TEST( *stack_top<FD_PROGCACHE_DEPTH_MAX );
511 9 : stack[ (*stack_top)++ ] = idx;
512 9 : last_idx = idx;
513 9 : uint next_idx = child->sibling_next_idx;
514 9 : if( next_idx!=UINT_MAX ) {
515 0 : TEST( next_idx<txn_max );
516 0 : TEST( pool[ next_idx ].sibling_prev_idx==idx );
517 0 : }
518 9 : idx = next_idx;
519 9 : }
520 84 : TEST( last_idx==tail_idx );
521 :
522 84 : # undef TEST
523 :
524 84 : return 0;
525 84 : }
526 :
527 : int
528 75 : fd_progcache_verify( fd_progcache_join_t * join ) {
529 :
530 690 : # define TEST(c) do { \
531 690 : if( FD_UNLIKELY( !(c) ) ) { FD_LOG_WARNING(( "FAIL: %s", #c )); return -1; } \
532 690 : } while(0)
533 :
534 75 : TEST( join );
535 :
536 75 : fd_progcache_shmem_t * shmem = join->shmem;
537 75 : TEST( shmem );
538 75 : TEST( shmem->magic==FD_PROGCACHE_SHMEM_MAGIC );
539 75 : TEST( shmem->wksp_tag );
540 :
541 75 : TEST( !fd_prog_recp_verify( join->rec.pool ) );
542 75 : TEST( !fd_prog_recm_verify( join->rec.map ) );
543 :
544 75 : ulong rec_max = fd_prog_recp_ele_max( join->rec.pool );
545 75 : fd_progcache_rec_t * rec0 = join->rec.pool->ele;
546 :
547 75 : ulong txn_max = fd_prog_txnp_max( join->txn.pool );
548 75 : TEST( !fd_prog_txnm_verify( join->txn.map, txn_max, join->txn.pool ) );
549 :
550 1275 : for( ulong i=0UL; i<txn_max; i++ ) join->txn.pool[ i ].tag = 0;
551 :
552 75 : uint stack[ FD_PROGCACHE_DEPTH_MAX ];
553 75 : ulong stack_top = 0UL;
554 :
555 75 : TEST( !fd_progcache_verify_siblings( join->txn.pool, txn_max,
556 75 : shmem->txn.child_head_idx, shmem->txn.child_tail_idx,
557 75 : UINT_MAX, stack, &stack_top ) );
558 :
559 84 : while( stack_top ) {
560 9 : uint txn_idx = stack[ --stack_top ];
561 9 : fd_progcache_txn_t * txn = &join->txn.pool[ txn_idx ];
562 9 : TEST( !fd_progcache_verify_siblings( join->txn.pool, txn_max,
563 9 : txn->child_head_idx, txn->child_tail_idx,
564 9 : txn_idx, stack, &stack_top ) );
565 9 : }
566 :
567 1275 : for( ulong i=0UL; i<txn_max; i++ ) {
568 1200 : if( !join->txn.pool[ i ].tag ) continue;
569 9 : fd_progcache_txn_t * txn = &join->txn.pool[ i ];
570 :
571 9 : TEST( (txn->rec_head_idx==UINT_MAX)==(txn->rec_tail_idx==UINT_MAX) );
572 :
573 9 : ulong rec_cnt = 0UL;
574 9 : uint prev = UINT_MAX;
575 9 : for( uint idx = txn->rec_head_idx; idx!=UINT_MAX; ) {
576 0 : TEST( idx<rec_max );
577 0 : TEST( rec_cnt<rec_max ); /* cycle detection */
578 0 : fd_progcache_rec_t * rec = &rec0[ idx ];
579 0 : TEST( rec->prev_idx==prev );
580 0 : TEST( rec->exists );
581 0 : prev = idx;
582 0 : idx = rec->next_idx;
583 0 : rec_cnt++;
584 0 : }
585 9 : TEST( prev==txn->rec_tail_idx );
586 9 : }
587 :
588 75 : ulong chain_cnt = fd_prog_recm_chain_cnt( join->rec.map );
589 1275 : for( ulong chain_idx=0UL; chain_idx<chain_cnt; chain_idx++ ) {
590 1200 : for(
591 1200 : fd_prog_recm_iter_t iter = fd_prog_recm_iter( join->rec.map, chain_idx );
592 1221 : !fd_prog_recm_iter_done( iter );
593 1200 : iter = fd_prog_recm_iter_next( iter )
594 1200 : ) {
595 21 : fd_progcache_rec_t * rec = fd_prog_recm_iter_ele( iter );
596 21 : TEST( rec->exists );
597 :
598 : /* Verify clock exists bit is set for mapped records */
599 21 : ulong rec_idx = (ulong)( rec - rec0 );
600 21 : TEST( rec_idx<rec_max );
601 21 : atomic_ulong * slot_p = fd_prog_cbits_slot( join->clock.bits, rec_idx );
602 21 : ulong slot_val = atomic_load_explicit( slot_p, memory_order_relaxed );
603 21 : TEST( fd_ulong_extract_bit( slot_val, fd_prog_exists_bit( rec_idx ) ) );
604 21 : }
605 1200 : }
606 :
607 75 : {
608 75 : ulong reclaim_cnt = 0UL;
609 75 : for( uint idx = join->rec.reclaim_head; idx!=UINT_MAX; ) {
610 0 : TEST( idx<rec_max );
611 0 : TEST( reclaim_cnt<rec_max ); /* cycle detection */
612 0 : idx = rec0[ idx ].reclaim_next;
613 0 : reclaim_cnt++;
614 0 : }
615 75 : }
616 :
617 75 : # undef TEST
618 :
619 75 : return 0;
620 75 : }
621 :
622 : void
623 0 : fd_progcache_wksp_metrics_update( fd_progcache_join_t * cache ) {
624 0 : fd_wksp_t * wksp = fd_wksp_containing( cache->shmem );
625 0 : if( FD_UNLIKELY( !wksp ) ) return;
626 0 : if( FD_UNLIKELY( fd_wksp_private_lock( wksp ) ) ) FD_LOG_CRIT(( "fd_wksp_private_lock failed" ));
627 :
628 0 : fd_wksp_private_pinfo_t * pinfo = fd_wksp_private_pinfo( wksp );
629 0 : ulong part_max = wksp->part_max;
630 0 : ulong cycle_tag = wksp->cycle_tag++;
631 :
632 0 : ulong free_part_cnt = 0UL;
633 0 : ulong free_sz = 0UL;
634 0 : ulong total_sz = 0UL;
635 0 : ulong free_part_max = 0UL;
636 :
637 0 : ulong i = fd_wksp_private_pinfo_idx( wksp->part_head_cidx );
638 0 : while( !fd_wksp_private_pinfo_idx_is_null( i ) ) {
639 0 : if( FD_UNLIKELY( i>=part_max ) || FD_UNLIKELY( pinfo[ i ].cycle_tag==cycle_tag ) ) {
640 0 : FD_LOG_CRIT(( "corrupt wksp detected" ));
641 0 : }
642 0 : pinfo[ i ].cycle_tag = cycle_tag; /* mark i as visited */
643 0 : ulong part_sz = fd_wksp_private_pinfo_sz( pinfo + i );
644 0 : ulong part_tag = pinfo[ i ].tag;
645 0 : ulong free_psz = fd_ulong_if( !part_tag, part_sz, 0UL );
646 0 : free_part_cnt += !part_tag;
647 0 : free_sz += free_psz;
648 0 : total_sz += part_sz;
649 0 : free_part_max = fd_ulong_max( free_part_max, free_psz );
650 0 : i = fd_wksp_private_pinfo_idx( pinfo[ i ].next_cidx );
651 0 : }
652 0 : fd_wksp_private_unlock( wksp );
653 :
654 0 : fd_progcache_admin_metrics_t * m = &fd_progcache_admin_metrics_g;
655 0 : m->wksp.free_part_cnt = free_part_cnt;
656 0 : m->wksp.free_sz = free_sz;
657 0 : m->wksp.total_sz = total_sz;
658 0 : m->wksp.free_part_max = free_part_max;
659 0 : }
|
