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 "fd_progcache_xid.h"
8 : #include "../../util/racesan/fd_racesan_target.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 : fd_progcache_fork_id_t
37 : fd_progcache_attach_child( fd_progcache_join_t * cache,
38 3801 : fd_progcache_fork_id_t parent_fork_id ) {
39 3801 : if( FD_UNLIKELY( !cache ) ) FD_LOG_CRIT(( "invalid arguments" ));
40 :
41 3801 : fd_rwlock_write( &cache->shmem->txn.rwlock );
42 3801 : if( FD_UNLIKELY( fd_prog_txnp_free( cache->txn.pool )==0UL ) ) {
43 0 : FD_LOG_ERR(( "fd_progcache_attach_child failed: transaction object pool out of memory" ));
44 0 : }
45 :
46 3801 : ulong txn_max = fd_prog_txnp_max( cache->txn.pool );
47 3801 : ulong parent_idx;
48 3801 : uint * _child_head_idx;
49 3801 : uint * _child_tail_idx;
50 :
51 3801 : fd_progcache_fork_id_t root = __atomic_load_n( &cache->shmem->txn.root, memory_order_relaxed );
52 3801 : if( FD_UNLIKELY( parent_fork_id == root ) ) {
53 :
54 3687 : parent_idx = FD_PROGCACHE_TXN_IDX_NULL;
55 :
56 3687 : _child_head_idx = &cache->shmem->txn.child_head_idx;
57 3687 : _child_tail_idx = &cache->shmem->txn.child_tail_idx;
58 :
59 3687 : } else {
60 :
61 114 : parent_idx = fd_prog_txnm_idx_query( cache->txn.map, &parent_fork_id, ULONG_MAX, cache->txn.pool );
62 114 : if( FD_UNLIKELY( parent_idx==ULONG_MAX ) ) {
63 0 : FD_LOG_CRIT(( "fd_progcache_attach_child failed: user provided invalid parent fork_id %lu", parent_fork_id ));
64 0 : }
65 114 : if( FD_UNLIKELY( parent_idx >= txn_max ) )
66 0 : FD_LOG_CRIT(( "progcache: corruption detected (attach_child parent_idx=%lu txn_max=%lu)", parent_idx, txn_max ));
67 :
68 114 : _child_head_idx = &cache->txn.pool[ parent_idx ].child_head_idx;
69 114 : _child_tail_idx = &cache->txn.pool[ parent_idx ].child_tail_idx;
70 :
71 114 : }
72 :
73 3801 : uint txn_idx = (uint)fd_prog_txnp_idx_acquire( cache->txn.pool );
74 3801 : if( FD_UNLIKELY( txn_idx==UINT_MAX ) ) FD_LOG_ERR(( "fd_progcache_attach_child failed: transaction object pool out of memory" ));
75 3801 : fd_progcache_txn_t * txn = &cache->txn.pool[ txn_idx ];
76 3801 : txn->xid = __atomic_add_fetch( &cache->shmem->txn.seq, 1UL, memory_order_relaxed );
77 :
78 3801 : uint sibling_prev_idx = *_child_tail_idx;
79 :
80 3801 : int first_born = sibling_prev_idx==UINT_MAX;
81 3801 : if( FD_UNLIKELY( !first_born && (ulong)sibling_prev_idx >= txn_max ) )
82 0 : FD_LOG_CRIT(( "progcache: corruption detected (attach_child sibling_prev_idx=%u txn_max=%lu)", sibling_prev_idx, txn_max ));
83 :
84 3801 : txn->parent_idx = (uint)parent_idx;
85 3801 : txn->child_head_idx = UINT_MAX;
86 3801 : txn->child_tail_idx = UINT_MAX;
87 3801 : txn->sibling_prev_idx = (uint)sibling_prev_idx;
88 3801 : txn->sibling_next_idx = UINT_MAX;
89 :
90 3801 : txn->rec_head_idx = UINT_MAX;
91 3801 : txn->rec_tail_idx = UINT_MAX;
92 :
93 : /* TODO: consider branchless impl */
94 3801 : if( FD_LIKELY( first_born ) ) *_child_head_idx = (uint)txn_idx; /* opt for non-compete */
95 9 : else cache->txn.pool[ sibling_prev_idx ].sibling_next_idx = (uint)txn_idx;
96 :
97 3801 : *_child_tail_idx = (uint)txn_idx;
98 :
99 3801 : fd_prog_txnm_idx_insert( cache->txn.map, txn_idx, cache->txn.pool );
100 :
101 3801 : fd_rwlock_unwrite( &cache->shmem->txn.rwlock );
102 3801 : return txn->xid;
103 3801 : }
104 :
105 : static void
106 : fd_progcache_cancel_one( fd_progcache_join_t * cache,
107 123 : fd_progcache_txn_t * txn ) {
108 123 : ulong rec_max = fd_prog_recp_ele_max( cache->rec.pool );
109 123 : ulong txn_max = fd_prog_txnp_max( cache->txn.pool );
110 :
111 123 : fd_rwlock_write( &txn->lock );
112 :
113 123 : if( FD_UNLIKELY( txn->child_head_idx!=UINT_MAX ||
114 123 : txn->child_tail_idx!=UINT_MAX ) ) {
115 0 : FD_LOG_CRIT(( "fd_progcache_cancel failed: txn at %p with fork_id %lu has children (data corruption?)",
116 0 : (void *)txn, txn->xid ));
117 0 : }
118 :
119 : /* Remove records */
120 :
121 183 : for( uint idx = txn->rec_head_idx; idx!=UINT_MAX; idx = cache->rec.pool->ele[ idx ].next_idx ) {
122 60 : if( FD_UNLIKELY( (ulong)idx >= rec_max ) )
123 0 : FD_LOG_CRIT(( "progcache: corruption detected (cancel_one rec_idx=%u rec_max=%lu)", idx, rec_max ));
124 60 : atomic_store_explicit( &cache->rec.pool->ele[ idx ].txn_idx, UINT_MAX, memory_order_release );
125 60 : fd_racesan_hook( "prog_cancel_one:post_orphan" );
126 60 : fd_prog_delete_rec( cache, &cache->rec.pool->ele[ idx ] );
127 60 : }
128 :
129 123 : txn->rec_head_idx = UINT_MAX;
130 123 : txn->rec_tail_idx = UINT_MAX;
131 :
132 : /* Remove transaction from fork graph */
133 :
134 123 : uint self_idx = (uint)( txn - cache->txn.pool );
135 123 : uint prev_idx = txn->sibling_prev_idx;
136 123 : uint next_idx = txn->sibling_next_idx;
137 123 : if( next_idx!=UINT_MAX ) {
138 0 : if( FD_UNLIKELY( (ulong)next_idx >= txn_max ) )
139 0 : FD_LOG_CRIT(( "progcache: corruption detected (cancel_one sibling_next_idx=%u txn_max=%lu)", next_idx, txn_max ));
140 0 : cache->txn.pool[ next_idx ].sibling_prev_idx = prev_idx;
141 0 : }
142 123 : if( prev_idx!=UINT_MAX ) {
143 9 : if( FD_UNLIKELY( (ulong)prev_idx >= txn_max ) )
144 0 : FD_LOG_CRIT(( "progcache: corruption detected (cancel_one sibling_prev_idx=%u txn_max=%lu)", prev_idx, txn_max ));
145 9 : cache->txn.pool[ prev_idx ].sibling_next_idx = next_idx;
146 9 : }
147 123 : if( txn->parent_idx!=UINT_MAX ) {
148 57 : if( FD_UNLIKELY( (ulong)txn->parent_idx >= txn_max ) )
149 0 : FD_LOG_CRIT(( "progcache: corruption detected (cancel_one parent_idx=%u txn_max=%lu)", txn->parent_idx, txn_max ));
150 57 : fd_progcache_txn_t * parent = &cache->txn.pool[ txn->parent_idx ];
151 57 : if( parent->child_head_idx==self_idx ) parent->child_head_idx = next_idx;
152 57 : if( parent->child_tail_idx==self_idx ) parent->child_tail_idx = prev_idx;
153 66 : } else {
154 66 : if( cache->shmem->txn.child_head_idx==self_idx ) cache->shmem->txn.child_head_idx = next_idx;
155 66 : if( cache->shmem->txn.child_tail_idx==self_idx ) cache->shmem->txn.child_tail_idx = prev_idx;
156 66 : }
157 :
158 : /* Remove transaction from index */
159 :
160 123 : if( FD_UNLIKELY( !fd_prog_txnm_ele_remove( cache->txn.map, &txn->xid, NULL, cache->txn.pool ) ) ) {
161 0 : FD_LOG_CRIT(( "fd_progcache_cancel failed: fd_prog_txnm_ele_remove(%lu) failed", txn->xid ));
162 0 : }
163 :
164 : /* Free transaction object */
165 :
166 123 : fd_rwlock_unwrite( &txn->lock );
167 123 : fd_prog_txnp_ele_release( cache->txn.pool, txn );
168 123 : }
169 :
170 : /* Cancels txn and all children */
171 :
172 : static void
173 : fd_progcache_cancel_tree( fd_progcache_join_t * cache,
174 123 : fd_progcache_txn_t * txn ) {
175 123 : ulong txn_max = fd_prog_txnp_max( cache->txn.pool );
176 129 : for(;;) {
177 129 : uint child_idx = txn->child_head_idx;
178 129 : if( child_idx==UINT_MAX ) break;
179 6 : if( FD_UNLIKELY( (ulong)child_idx >= txn_max ) )
180 0 : FD_LOG_CRIT(( "progcache: corruption detected (cancel_tree child_idx=%u txn_max=%lu)", child_idx, txn_max ));
181 6 : fd_progcache_txn_t * child = &cache->txn.pool[ child_idx ];
182 6 : fd_progcache_cancel_tree( cache, child );
183 6 : }
184 123 : fd_progcache_cancel_one( cache, txn );
185 123 : }
186 :
187 : /* Cancels all left/right siblings */
188 :
189 : static void
190 : fd_progcache_cancel_prev_list( fd_progcache_join_t * cache,
191 36 : fd_progcache_txn_t * txn ) {
192 36 : ulong txn_max = fd_prog_txnp_max( cache->txn.pool );
193 36 : uint cur_idx = txn->sibling_prev_idx;
194 36 : while( cur_idx!=UINT_MAX ) {
195 0 : if( FD_UNLIKELY( (ulong)cur_idx >= txn_max ) )
196 0 : FD_LOG_CRIT(( "progcache: corruption detected (cancel_prev_list txn_idx=%u txn_max=%lu)", cur_idx, txn_max ));
197 0 : fd_progcache_txn_t * sibling = &cache->txn.pool[ cur_idx ];
198 0 : uint next = sibling->sibling_prev_idx;
199 0 : fd_progcache_cancel_tree( cache, sibling );
200 0 : cur_idx = next;
201 0 : }
202 36 : }
203 :
204 : static void
205 : fd_progcache_cancel_next_list( fd_progcache_join_t * cache,
206 36 : fd_progcache_txn_t * txn ) {
207 36 : ulong txn_max = fd_prog_txnp_max( cache->txn.pool );
208 36 : uint cur_idx = txn->sibling_next_idx;
209 36 : while( cur_idx!=UINT_MAX ) {
210 0 : if( FD_UNLIKELY( (ulong)cur_idx >= txn_max ) )
211 0 : FD_LOG_CRIT(( "progcache: corruption detected (cancel_next_list txn_idx=%u txn_max=%lu)", cur_idx, txn_max ));
212 0 : fd_progcache_txn_t * sibling = &cache->txn.pool[ cur_idx ];
213 0 : uint next = sibling->sibling_next_idx;
214 0 : fd_progcache_cancel_tree( cache, sibling );
215 0 : cur_idx = next;
216 0 : }
217 36 : }
218 :
219 : /* fd_progcache_txn_publish_one merges an in-prep transaction whose
220 : parent is the last published, into the parent. */
221 :
222 : static void
223 : fd_progcache_txn_publish_one( fd_progcache_join_t * cache,
224 36 : fd_progcache_txn_t * txn ) {
225 :
226 : /* Phase 1: Mark transaction as "last published" */
227 :
228 36 : fd_progcache_fork_id_t const fork_id = txn->xid;
229 36 : if( FD_UNLIKELY( txn->parent_idx!=UINT_MAX ) ) {
230 0 : FD_LOG_CRIT(( "fd_progcache_publish failed: txn with fork_id %lu is not a child of the last published txn", fork_id ));
231 0 : }
232 36 : fd_racesan_hook( "prog_publish_one:pre_xid_store" );
233 36 : __atomic_store_n( &cache->shmem->txn.root, fork_id, memory_order_release );
234 :
235 : /* Phase 2: Drain inserters from transaction */
236 :
237 36 : fd_rwlock_write( &txn->lock );
238 :
239 : /* Phase 3: Detach records */
240 :
241 36 : ulong rec_max = fd_prog_recp_ele_max( cache->rec.pool );
242 42 : for( uint idx = txn->rec_head_idx; idx!=UINT_MAX; idx = cache->rec.pool->ele[ idx ].next_idx ) {
243 6 : if( FD_UNLIKELY( (ulong)idx >= rec_max ) )
244 0 : FD_LOG_CRIT(( "progcache: corruption detected (publish_one rec_idx=%u rec_max=%lu)", idx, rec_max ));
245 6 : atomic_store_explicit( &cache->rec.pool->ele[ idx ].txn_idx, UINT_MAX, memory_order_release );
246 6 : fd_progcache_admin_metrics_g.root_cnt++;
247 6 : }
248 :
249 36 : txn->rec_head_idx = UINT_MAX;
250 36 : txn->rec_tail_idx = UINT_MAX;
251 :
252 : /* Phase 4: Remove transaction from fork graph */
253 :
254 36 : { /* Adjust the parent pointers of the children to point to "last published" */
255 36 : ulong txn_max = fd_prog_txnp_max( cache->txn.pool );
256 36 : ulong child_idx = txn->child_head_idx;
257 42 : while( child_idx!=UINT_MAX ) {
258 6 : if( FD_UNLIKELY( child_idx >= txn_max ) )
259 0 : FD_LOG_CRIT(( "progcache: corruption detected (publish_one child_idx=%lu txn_max=%lu)", child_idx, txn_max ));
260 6 : cache->txn.pool[ child_idx ].parent_idx = UINT_MAX;
261 6 : child_idx = cache->txn.pool[ child_idx ].sibling_next_idx;
262 6 : }
263 36 : }
264 :
265 : /* Phase 5: Remove transaction from index */
266 :
267 36 : if( FD_UNLIKELY( fd_prog_txnm_idx_remove( cache->txn.map, &txn->xid, ULONG_MAX, cache->txn.pool )==ULONG_MAX ) ) {
268 0 : FD_LOG_CRIT(( "fd_progcache_publish failed: fd_prog_txnm_idx_remove(%lu) failed", txn->xid ));
269 0 : }
270 :
271 : /* Phase 6: Free transaction object */
272 :
273 36 : fd_rwlock_unwrite( &txn->lock );
274 36 : txn->parent_idx = UINT_MAX;
275 36 : txn->sibling_prev_idx = UINT_MAX;
276 36 : txn->sibling_next_idx = UINT_MAX;
277 36 : txn->child_head_idx = UINT_MAX;
278 36 : txn->child_tail_idx = UINT_MAX;
279 36 : fd_prog_txnp_ele_release( cache->txn.pool, txn );
280 36 : }
281 :
282 : void
283 : fd_progcache_advance_root( fd_progcache_join_t * cache,
284 36 : fd_progcache_fork_id_t fork_id ) {
285 36 : if( FD_UNLIKELY( !cache ) ) FD_LOG_CRIT(( "invalid arguments" ));
286 :
287 : /* Detach records from txns without acquiring record locks */
288 :
289 36 : fd_rwlock_write( &cache->shmem->txn.rwlock );
290 :
291 36 : ulong txn_max = fd_prog_txnp_max( cache->txn.pool );
292 36 : uint txn_idx = (uint)fd_prog_txnm_idx_query( cache->txn.map, &fork_id, UINT_MAX, cache->txn.pool );
293 36 : if( FD_UNLIKELY( txn_idx==UINT_MAX ) ) {
294 0 : FD_LOG_CRIT(( "fd_progcache_advance_root failed: invalid fork_id %lu", fork_id ));
295 0 : }
296 36 : if( FD_UNLIKELY( (ulong)txn_idx >= txn_max ) )
297 0 : FD_LOG_CRIT(( "progcache: corruption detected (advance_root txn_idx=%u txn_max=%lu)", txn_idx, txn_max ));
298 36 : fd_progcache_txn_t * txn = &cache->txn.pool[ txn_idx ];
299 36 : if( FD_UNLIKELY( txn->parent_idx!=UINT_MAX ) ) {
300 0 : FD_LOG_CRIT(( "fd_progcache_advance_root: parent of txn %lu is not root", fork_id ));
301 0 : }
302 :
303 36 : fd_progcache_cancel_prev_list( cache, txn );
304 36 : fd_progcache_cancel_next_list( cache, txn );
305 :
306 36 : txn->sibling_prev_idx = UINT_MAX;
307 36 : txn->sibling_next_idx = UINT_MAX;
308 36 : cache->shmem->txn.child_head_idx = txn->child_head_idx;
309 36 : cache->shmem->txn.child_tail_idx = txn->child_tail_idx;
310 :
311 36 : fd_progcache_txn_publish_one( cache, txn );
312 :
313 36 : fd_rwlock_unwrite( &cache->shmem->txn.rwlock );
314 :
315 36 : fd_prog_reclaim_work( cache );
316 36 : }
317 :
318 : void
319 : fd_progcache_cancel_fork( fd_progcache_join_t * cache,
320 117 : fd_progcache_fork_id_t fork_id ) {
321 117 : if( FD_UNLIKELY( !cache ) ) {
322 0 : FD_LOG_CRIT(( "invalid arguments" ));
323 0 : }
324 :
325 117 : fd_rwlock_write( &cache->shmem->txn.rwlock );
326 117 : fd_progcache_txn_t * txn = fd_prog_txnm_ele_query( cache->txn.map, &fork_id, NULL, cache->txn.pool );
327 117 : if( FD_UNLIKELY( !txn ) ) {
328 0 : FD_LOG_CRIT(( "fd_progcache_cancel failed: invalid fork_id %lu", fork_id ));
329 0 : }
330 117 : fd_progcache_cancel_tree( cache, txn );
331 117 : fd_rwlock_unwrite( &cache->shmem->txn.rwlock );
332 117 : fd_prog_reclaim_work( cache );
333 117 : }
334 :
335 : /* reset_rec_map frees all records in a progcache instance. */
336 :
337 : static void
338 3588 : reset_rec_map( fd_progcache_join_t * cache ) {
339 3588 : fd_progcache_rec_t * rec0 = cache->rec.pool->ele;
340 3588 : ulong chain_cnt = fd_prog_recm_chain_cnt( cache->rec.map );
341 462852 : for( ulong chain_idx=0UL; chain_idx<chain_cnt; chain_idx++ ) {
342 459264 : for(
343 459264 : fd_prog_recm_iter_t iter = fd_prog_recm_iter( cache->rec.map, chain_idx );
344 459264 : !fd_prog_recm_iter_done( iter );
345 459264 : ) {
346 0 : fd_progcache_rec_t * rec = fd_prog_recm_iter_ele( iter );
347 0 : ulong next = fd_prog_recm_private_idx( rec->map_next );
348 :
349 0 : if( rec->exists ) {
350 0 : fd_prog_recm_query_t rec_query[1];
351 0 : int err = fd_prog_recm_remove( cache->rec.map, &rec->pair, NULL, rec_query, FD_MAP_FLAG_BLOCKING );
352 0 : if( FD_UNLIKELY( err!=FD_MAP_SUCCESS ) ) FD_LOG_CRIT(( "fd_prog_recm_remove failed (%i-%s)", err, fd_map_strerror( err ) ));
353 0 : fd_progcache_val_free( rec, cache );
354 0 : }
355 :
356 0 : rec->exists = 0;
357 0 : fd_prog_clock_remove( cache->clock.bits, (ulong)( rec-rec0 ) );
358 0 : fd_prog_recp_release( cache->rec.pool, rec );
359 0 : iter.ele_idx = next;
360 0 : }
361 459264 : }
362 3588 : }
363 :
364 : /* clear_txn_list does a depth-first traversal of the txn tree.
365 : Removes all txns. */
366 :
367 : static void
368 : clear_txn_list( fd_progcache_join_t * join,
369 7182 : uint txn_head_idx ) {
370 7182 : ulong txn_max = fd_prog_txnp_max( join->txn.pool );
371 10776 : for( uint idx = txn_head_idx; idx!=UINT_MAX; ) {
372 3594 : if( FD_UNLIKELY( (ulong)idx >= txn_max ) )
373 0 : FD_LOG_CRIT(( "progcache: corruption detected (clear_txn_list txn_idx=%u txn_max=%lu)", idx, txn_max ));
374 3594 : fd_progcache_txn_t * txn = &join->txn.pool[ idx ];
375 3594 : uint next_idx = txn->sibling_next_idx;
376 3594 : uint child_idx = txn->child_head_idx;
377 3594 : txn->rec_head_idx = UINT_MAX;
378 3594 : txn->rec_tail_idx = UINT_MAX;
379 3594 : txn->child_head_idx = UINT_MAX;
380 3594 : txn->child_tail_idx = UINT_MAX;
381 3594 : txn->parent_idx = UINT_MAX;
382 3594 : txn->sibling_prev_idx = UINT_MAX;
383 3594 : txn->sibling_next_idx = UINT_MAX;
384 3594 : clear_txn_list( join, child_idx );
385 3594 : 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" ));
386 3594 : fd_prog_txnp_ele_release( join->txn.pool, txn );
387 3594 : idx = next_idx;
388 3594 : }
389 7182 : }
390 :
391 : void
392 3588 : fd_progcache_reset( fd_progcache_join_t * cache ) {
393 3588 : clear_txn_list( cache, cache->shmem->txn.child_head_idx );
394 3588 : cache->shmem->txn.child_head_idx = UINT_MAX;
395 3588 : cache->shmem->txn.child_tail_idx = UINT_MAX;
396 3588 : reset_rec_map( cache );
397 3588 : cache->shmem->txn.root = fd_progcache_fork_id_initial();
398 3588 : cache->shmem->txn.seq = fd_progcache_fork_id_initial();
399 3588 : }
400 :
401 : static int
402 : fd_progcache_verify_siblings( fd_progcache_txn_t * pool,
403 : ulong txn_max,
404 : uint head_idx,
405 : uint tail_idx,
406 : uint expected_parent_idx,
407 : uint * stack,
408 87 : ulong * stack_top ) {
409 :
410 210 : # define TEST(c) do { \
411 210 : if( FD_UNLIKELY( !(c) ) ) { FD_LOG_WARNING(( "FAIL: %s", #c )); return -1; } \
412 210 : } while(0)
413 :
414 87 : TEST( (head_idx==UINT_MAX)==(tail_idx==UINT_MAX) );
415 :
416 87 : uint last_idx = UINT_MAX;
417 96 : for( uint idx = head_idx; idx!=UINT_MAX; ) {
418 9 : TEST( idx<txn_max );
419 9 : fd_progcache_txn_t * child = &pool[ idx ];
420 9 : TEST( !child->tag );
421 9 : TEST( child->parent_idx==expected_parent_idx );
422 9 : child->tag = 1;
423 9 : TEST( *stack_top<FD_PROGCACHE_DEPTH_MAX );
424 9 : stack[ (*stack_top)++ ] = idx;
425 9 : last_idx = idx;
426 9 : uint next_idx = child->sibling_next_idx;
427 9 : if( next_idx!=UINT_MAX ) {
428 0 : TEST( next_idx<txn_max );
429 0 : TEST( pool[ next_idx ].sibling_prev_idx==idx );
430 0 : }
431 9 : idx = next_idx;
432 9 : }
433 87 : TEST( last_idx==tail_idx );
434 :
435 87 : # undef TEST
436 :
437 87 : return 0;
438 87 : }
439 :
440 : int
441 78 : fd_progcache_verify( fd_progcache_join_t * join ) {
442 :
443 690 : # define TEST(c) do { \
444 690 : if( FD_UNLIKELY( !(c) ) ) { FD_LOG_WARNING(( "FAIL: %s", #c )); return -1; } \
445 690 : } while(0)
446 :
447 78 : TEST( join );
448 :
449 78 : fd_progcache_shmem_t * shmem = join->shmem;
450 78 : TEST( shmem );
451 78 : TEST( shmem->magic==FD_PROGCACHE_SHMEM_MAGIC );
452 78 : TEST( shmem->wksp_tag );
453 :
454 78 : TEST( !fd_prog_recp_verify( join->rec.pool ) );
455 78 : TEST( !fd_prog_recm_verify( join->rec.map ) );
456 :
457 78 : ulong rec_max = fd_prog_recp_ele_max( join->rec.pool );
458 78 : fd_progcache_rec_t * rec0 = join->rec.pool->ele;
459 :
460 78 : ulong txn_max = fd_prog_txnp_max( join->txn.pool );
461 78 : TEST( !fd_prog_txnm_verify( join->txn.map, txn_max, join->txn.pool ) );
462 :
463 1326 : for( ulong i=0UL; i<txn_max; i++ ) join->txn.pool[ i ].tag = 0;
464 :
465 78 : uint stack[ FD_PROGCACHE_DEPTH_MAX ];
466 78 : ulong stack_top = 0UL;
467 :
468 78 : TEST( !fd_progcache_verify_siblings( join->txn.pool, txn_max,
469 78 : shmem->txn.child_head_idx, shmem->txn.child_tail_idx,
470 78 : UINT_MAX, stack, &stack_top ) );
471 :
472 87 : while( stack_top ) {
473 9 : uint txn_idx = stack[ --stack_top ];
474 9 : fd_progcache_txn_t * txn = &join->txn.pool[ txn_idx ];
475 9 : TEST( !fd_progcache_verify_siblings( join->txn.pool, txn_max,
476 9 : txn->child_head_idx, txn->child_tail_idx,
477 9 : txn_idx, stack, &stack_top ) );
478 9 : }
479 :
480 1326 : for( ulong i=0UL; i<txn_max; i++ ) {
481 1248 : if( !join->txn.pool[ i ].tag ) continue;
482 9 : fd_progcache_txn_t * txn = &join->txn.pool[ i ];
483 :
484 9 : TEST( (txn->rec_head_idx==UINT_MAX)==(txn->rec_tail_idx==UINT_MAX) );
485 :
486 9 : ulong rec_cnt = 0UL;
487 9 : uint prev = UINT_MAX;
488 12 : for( uint idx = txn->rec_head_idx; idx!=UINT_MAX; ) {
489 3 : TEST( idx<rec_max );
490 3 : TEST( rec_cnt<rec_max ); /* cycle detection */
491 3 : fd_progcache_rec_t * rec = &rec0[ idx ];
492 3 : TEST( rec->prev_idx==prev );
493 3 : TEST( rec->exists );
494 3 : prev = idx;
495 3 : idx = rec->next_idx;
496 3 : rec_cnt++;
497 3 : }
498 9 : TEST( prev==txn->rec_tail_idx );
499 9 : }
500 :
501 78 : ulong chain_cnt = fd_prog_recm_chain_cnt( join->rec.map );
502 1326 : for( ulong chain_idx=0UL; chain_idx<chain_cnt; chain_idx++ ) {
503 1248 : for(
504 1248 : fd_prog_recm_iter_t iter = fd_prog_recm_iter( join->rec.map, chain_idx );
505 1257 : !fd_prog_recm_iter_done( iter );
506 1248 : iter = fd_prog_recm_iter_next( iter )
507 1248 : ) {
508 9 : fd_progcache_rec_t * rec = fd_prog_recm_iter_ele( iter );
509 9 : TEST( rec->exists );
510 :
511 : /* Verify clock exists bit is set for mapped records */
512 9 : ulong rec_idx = (ulong)( rec - rec0 );
513 9 : TEST( rec_idx<rec_max );
514 9 : atomic_ulong * slot_p = fd_prog_cbits_slot( join->clock.bits, rec_idx );
515 9 : ulong slot_val = atomic_load_explicit( slot_p, memory_order_relaxed );
516 9 : TEST( fd_ulong_extract_bit( slot_val, fd_prog_exists_bit( rec_idx ) ) );
517 9 : }
518 1248 : }
519 :
520 78 : {
521 78 : ulong reclaim_cnt = 0UL;
522 78 : for( uint idx = join->rec.reclaim_head; idx!=UINT_MAX; ) {
523 0 : TEST( idx<rec_max );
524 0 : TEST( reclaim_cnt<rec_max ); /* cycle detection */
525 0 : idx = rec0[ idx ].reclaim_next;
526 0 : reclaim_cnt++;
527 0 : }
528 78 : }
529 :
530 78 : # undef TEST
531 :
532 78 : return 0;
533 78 : }
|
