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 : /* Transaction-level operations. txn_pool and txn_map are serialized by
14 : txn.rwlock: written here under the exclusive lock, read shared by the user
15 : and eviction paths. */
16 :
17 : fd_progcache_fork_id_t
18 : fd_progcache_attach_child( fd_progcache_join_t * cache,
19 4575 : fd_progcache_fork_id_t parent_fork_id ) {
20 4575 : if( FD_UNLIKELY( !cache ) ) FD_LOG_CRIT(( "invalid arguments" ));
21 :
22 4575 : fd_rwlock_write( &cache->shmem->txn.rwlock );
23 4575 : if( FD_UNLIKELY( fd_prog_txnp_free( cache->txn.pool )==0UL ) ) {
24 0 : FD_LOG_ERR(( "fd_progcache_attach_child failed: transaction object pool out of memory" ));
25 0 : }
26 :
27 4575 : ulong txn_max = fd_prog_txnp_max( cache->txn.pool );
28 4575 : ulong parent_idx;
29 4575 : uint * _child_head_idx;
30 4575 : uint * _child_tail_idx;
31 :
32 4575 : fd_progcache_fork_id_t root = __atomic_load_n( &cache->shmem->txn.root, memory_order_relaxed );
33 4575 : if( FD_UNLIKELY( parent_fork_id == root ) ) {
34 :
35 4368 : parent_idx = FD_PROGCACHE_TXN_IDX_NULL;
36 :
37 4368 : _child_head_idx = &cache->shmem->txn.child_head_idx;
38 4368 : _child_tail_idx = &cache->shmem->txn.child_tail_idx;
39 :
40 4368 : } else {
41 :
42 207 : parent_idx = fd_prog_txnm_idx_query( cache->txn.map, &parent_fork_id, ULONG_MAX, cache->txn.pool );
43 207 : if( FD_UNLIKELY( parent_idx==ULONG_MAX ) ) {
44 0 : FD_LOG_CRIT(( "fd_progcache_attach_child failed: user provided invalid parent fork_id %lu", parent_fork_id ));
45 0 : }
46 207 : if( FD_UNLIKELY( parent_idx >= txn_max ) )
47 0 : FD_LOG_CRIT(( "progcache: corruption detected (attach_child parent_idx=%lu txn_max=%lu)", parent_idx, txn_max ));
48 :
49 207 : _child_head_idx = &cache->txn.pool[ parent_idx ].child_head_idx;
50 207 : _child_tail_idx = &cache->txn.pool[ parent_idx ].child_tail_idx;
51 :
52 207 : }
53 :
54 4575 : uint txn_idx = (uint)fd_prog_txnp_idx_acquire( cache->txn.pool );
55 4575 : if( FD_UNLIKELY( txn_idx==UINT_MAX ) ) FD_LOG_ERR(( "fd_progcache_attach_child failed: transaction object pool out of memory" ));
56 4575 : fd_progcache_txn_t * txn = &cache->txn.pool[ txn_idx ];
57 4575 : txn->xid = __atomic_add_fetch( &cache->shmem->txn.seq, 1UL, memory_order_relaxed );
58 :
59 4575 : uint sibling_prev_idx = *_child_tail_idx;
60 :
61 4575 : int first_born = sibling_prev_idx==UINT_MAX;
62 4575 : if( FD_UNLIKELY( !first_born && (ulong)sibling_prev_idx >= txn_max ) )
63 0 : FD_LOG_CRIT(( "progcache: corruption detected (attach_child sibling_prev_idx=%u txn_max=%lu)", sibling_prev_idx, txn_max ));
64 :
65 4575 : txn->parent_idx = (uint)parent_idx;
66 4575 : txn->child_head_idx = UINT_MAX;
67 4575 : txn->child_tail_idx = UINT_MAX;
68 4575 : txn->sibling_prev_idx = (uint)sibling_prev_idx;
69 4575 : txn->sibling_next_idx = UINT_MAX;
70 :
71 4575 : txn->rec_head_idx = UINT_MAX;
72 4575 : txn->rec_tail_idx = UINT_MAX;
73 :
74 : /* TODO: consider branchless impl */
75 4575 : if( FD_LIKELY( first_born ) ) *_child_head_idx = (uint)txn_idx; /* opt for non-compete */
76 201 : else cache->txn.pool[ sibling_prev_idx ].sibling_next_idx = (uint)txn_idx;
77 :
78 4575 : *_child_tail_idx = (uint)txn_idx;
79 :
80 4575 : fd_prog_txnm_idx_insert( cache->txn.map, txn_idx, cache->txn.pool );
81 :
82 4575 : fd_rwlock_unwrite( &cache->shmem->txn.rwlock );
83 4575 : return txn->xid;
84 4575 : }
85 :
86 : static void
87 : fd_progcache_cancel_one( fd_progcache_join_t * cache,
88 369 : fd_progcache_txn_t * txn ) {
89 369 : ulong rec_max = cache->rec.max;
90 369 : ulong txn_max = fd_prog_txnp_max( cache->txn.pool );
91 :
92 369 : fd_rwlock_write( &txn->lock );
93 :
94 369 : if( FD_UNLIKELY( txn->child_head_idx!=UINT_MAX ||
95 369 : txn->child_tail_idx!=UINT_MAX ) ) {
96 0 : FD_LOG_CRIT(( "fd_progcache_cancel failed: txn at %p with fork_id %lu has children (data corruption?)",
97 0 : (void *)txn, txn->xid ));
98 0 : }
99 :
100 : /* Remove records */
101 :
102 2610 : for( uint idx = txn->rec_head_idx; idx!=UINT_MAX; ) {
103 2241 : if( FD_UNLIKELY( (ulong)idx >= rec_max ) )
104 0 : FD_LOG_CRIT(( "progcache: corruption detected (cancel_one rec_idx=%u rec_max=%lu)", idx, rec_max ));
105 2241 : fd_progcache_rec_t * rec = &cache->rec.ele[ idx ];
106 2241 : uint next_idx = rec->next_idx;
107 2241 : if( FD_UNLIKELY( next_idx!=UINT_MAX && (ulong)next_idx >= rec_max ) )
108 0 : FD_LOG_CRIT(( "progcache: corruption detected (cancel_one next_idx=%u rec_max=%lu)", next_idx, rec_max ));
109 2241 : atomic_store_explicit( &rec->txn_idx, UINT_MAX, memory_order_release );
110 2241 : fd_racesan_hook( "prog_cancel_one:post_orphan" );
111 2241 : fd_prog_delete_rec( cache, rec );
112 2241 : idx = next_idx;
113 2241 : }
114 :
115 369 : txn->rec_head_idx = UINT_MAX;
116 369 : txn->rec_tail_idx = UINT_MAX;
117 :
118 : /* Remove transaction from fork graph */
119 :
120 369 : uint self_idx = (uint)( txn - cache->txn.pool );
121 369 : uint prev_idx = txn->sibling_prev_idx;
122 369 : uint next_idx = txn->sibling_next_idx;
123 369 : if( next_idx!=UINT_MAX ) {
124 0 : if( FD_UNLIKELY( (ulong)next_idx >= txn_max ) )
125 0 : FD_LOG_CRIT(( "progcache: corruption detected (cancel_one sibling_next_idx=%u txn_max=%lu)", next_idx, txn_max ));
126 0 : cache->txn.pool[ next_idx ].sibling_prev_idx = prev_idx;
127 0 : }
128 369 : if( prev_idx!=UINT_MAX ) {
129 201 : if( FD_UNLIKELY( (ulong)prev_idx >= txn_max ) )
130 0 : FD_LOG_CRIT(( "progcache: corruption detected (cancel_one sibling_prev_idx=%u txn_max=%lu)", prev_idx, txn_max ));
131 201 : cache->txn.pool[ prev_idx ].sibling_next_idx = next_idx;
132 201 : }
133 369 : if( txn->parent_idx!=UINT_MAX ) {
134 57 : if( FD_UNLIKELY( (ulong)txn->parent_idx >= txn_max ) )
135 0 : FD_LOG_CRIT(( "progcache: corruption detected (cancel_one parent_idx=%u txn_max=%lu)", txn->parent_idx, txn_max ));
136 57 : fd_progcache_txn_t * parent = &cache->txn.pool[ txn->parent_idx ];
137 57 : if( parent->child_head_idx==self_idx ) parent->child_head_idx = next_idx;
138 57 : if( parent->child_tail_idx==self_idx ) parent->child_tail_idx = prev_idx;
139 312 : } else {
140 312 : if( cache->shmem->txn.child_head_idx==self_idx ) cache->shmem->txn.child_head_idx = next_idx;
141 312 : if( cache->shmem->txn.child_tail_idx==self_idx ) cache->shmem->txn.child_tail_idx = prev_idx;
142 312 : }
143 :
144 : /* Remove transaction from index */
145 :
146 369 : if( FD_UNLIKELY( !fd_prog_txnm_ele_remove( cache->txn.map, &txn->xid, NULL, cache->txn.pool ) ) ) {
147 0 : FD_LOG_CRIT(( "fd_progcache_cancel failed: fd_prog_txnm_ele_remove(%lu) failed", txn->xid ));
148 0 : }
149 :
150 : /* Free transaction object */
151 :
152 369 : fd_rwlock_unwrite( &txn->lock );
153 369 : fd_prog_txnp_ele_release( cache->txn.pool, txn );
154 369 : }
155 :
156 : /* Cancels txn and all children */
157 :
158 : static void
159 : fd_progcache_cancel_tree( fd_progcache_join_t * cache,
160 369 : fd_progcache_txn_t * txn ) {
161 369 : ulong txn_max = fd_prog_txnp_max( cache->txn.pool );
162 375 : for(;;) {
163 375 : uint child_idx = txn->child_head_idx;
164 375 : if( child_idx==UINT_MAX ) break;
165 6 : if( FD_UNLIKELY( (ulong)child_idx >= txn_max ) )
166 0 : FD_LOG_CRIT(( "progcache: corruption detected (cancel_tree child_idx=%u txn_max=%lu)", child_idx, txn_max ));
167 6 : fd_progcache_txn_t * child = &cache->txn.pool[ child_idx ];
168 6 : fd_progcache_cancel_tree( cache, child );
169 6 : }
170 369 : fd_progcache_cancel_one( cache, txn );
171 369 : }
172 :
173 : /* Cancels all left/right siblings */
174 :
175 : static void
176 : fd_progcache_cancel_prev_list( fd_progcache_join_t * cache,
177 147 : fd_progcache_txn_t * txn ) {
178 147 : ulong txn_max = fd_prog_txnp_max( cache->txn.pool );
179 147 : uint cur_idx = txn->sibling_prev_idx;
180 147 : while( cur_idx!=UINT_MAX ) {
181 0 : if( FD_UNLIKELY( (ulong)cur_idx >= txn_max ) )
182 0 : FD_LOG_CRIT(( "progcache: corruption detected (cancel_prev_list txn_idx=%u txn_max=%lu)", cur_idx, txn_max ));
183 0 : fd_progcache_txn_t * sibling = &cache->txn.pool[ cur_idx ];
184 0 : uint next = sibling->sibling_prev_idx;
185 0 : fd_progcache_cancel_tree( cache, sibling );
186 0 : cur_idx = next;
187 0 : }
188 147 : }
189 :
190 : static void
191 : fd_progcache_cancel_next_list( fd_progcache_join_t * cache,
192 147 : fd_progcache_txn_t * txn ) {
193 147 : ulong txn_max = fd_prog_txnp_max( cache->txn.pool );
194 147 : uint cur_idx = txn->sibling_next_idx;
195 147 : while( cur_idx!=UINT_MAX ) {
196 0 : if( FD_UNLIKELY( (ulong)cur_idx >= txn_max ) )
197 0 : FD_LOG_CRIT(( "progcache: corruption detected (cancel_next_list txn_idx=%u txn_max=%lu)", cur_idx, txn_max ));
198 0 : fd_progcache_txn_t * sibling = &cache->txn.pool[ cur_idx ];
199 0 : uint next = sibling->sibling_next_idx;
200 0 : fd_progcache_cancel_tree( cache, sibling );
201 0 : cur_idx = next;
202 0 : }
203 147 : }
204 :
205 : /* fd_progcache_txn_publish_one merges an in-prep transaction whose
206 : parent is the last published, into the parent. */
207 :
208 : static void
209 : fd_progcache_txn_publish_one( fd_progcache_join_t * cache,
210 147 : fd_progcache_txn_t * txn ) {
211 :
212 : /* Phase 1: Mark transaction as "last published" */
213 :
214 147 : fd_progcache_fork_id_t const fork_id = txn->xid;
215 147 : if( FD_UNLIKELY( txn->parent_idx!=UINT_MAX ) ) {
216 0 : FD_LOG_CRIT(( "fd_progcache_publish failed: txn with fork_id %lu is not a child of the last published txn", fork_id ));
217 0 : }
218 147 : fd_racesan_hook( "prog_publish_one:pre_xid_store" );
219 147 : __atomic_store_n( &cache->shmem->txn.root, fork_id, memory_order_release );
220 :
221 : /* Phase 2: Drain inserters from transaction */
222 :
223 147 : fd_rwlock_write( &txn->lock );
224 :
225 : /* Phase 3: Detach records */
226 :
227 147 : ulong rec_max = cache->rec.max;
228 660 : for( uint idx = txn->rec_head_idx; idx!=UINT_MAX; ) {
229 513 : if( FD_UNLIKELY( (ulong)idx >= rec_max ) )
230 0 : FD_LOG_CRIT(( "progcache: corruption detected (publish_one rec_idx=%u rec_max=%lu)", idx, rec_max ));
231 513 : uint next_idx = cache->rec.ele[ idx ].next_idx;
232 513 : if( FD_UNLIKELY( next_idx!=UINT_MAX && (ulong)next_idx >= rec_max ) )
233 0 : FD_LOG_CRIT(( "progcache: corruption detected (publish_one next_idx=%u rec_max=%lu)", next_idx, rec_max ));
234 513 : atomic_store_explicit( &cache->rec.ele[ idx ].txn_idx, UINT_MAX, memory_order_release );
235 513 : fd_racesan_hook( "prog_publish_one:post_detach" );
236 513 : fd_progcache_admin_metrics_g.root_cnt++;
237 513 : idx = next_idx;
238 513 : }
239 :
240 147 : txn->rec_head_idx = UINT_MAX;
241 147 : txn->rec_tail_idx = UINT_MAX;
242 :
243 : /* Phase 4: Remove transaction from fork graph */
244 :
245 147 : { /* Adjust the parent pointers of the children to point to "last published" */
246 147 : ulong txn_max = fd_prog_txnp_max( cache->txn.pool );
247 147 : ulong child_idx = txn->child_head_idx;
248 153 : while( child_idx!=UINT_MAX ) {
249 6 : if( FD_UNLIKELY( child_idx >= txn_max ) )
250 0 : FD_LOG_CRIT(( "progcache: corruption detected (publish_one child_idx=%lu txn_max=%lu)", child_idx, txn_max ));
251 6 : cache->txn.pool[ child_idx ].parent_idx = UINT_MAX;
252 6 : child_idx = cache->txn.pool[ child_idx ].sibling_next_idx;
253 6 : }
254 147 : }
255 :
256 : /* Phase 5: Remove transaction from index */
257 :
258 147 : if( FD_UNLIKELY( fd_prog_txnm_idx_remove( cache->txn.map, &txn->xid, ULONG_MAX, cache->txn.pool )==ULONG_MAX ) ) {
259 0 : FD_LOG_CRIT(( "fd_progcache_publish failed: fd_prog_txnm_idx_remove(%lu) failed", txn->xid ));
260 0 : }
261 :
262 : /* Phase 6: Free transaction object */
263 :
264 147 : fd_rwlock_unwrite( &txn->lock );
265 147 : txn->parent_idx = UINT_MAX;
266 147 : txn->sibling_prev_idx = UINT_MAX;
267 147 : txn->sibling_next_idx = UINT_MAX;
268 147 : txn->child_head_idx = UINT_MAX;
269 147 : txn->child_tail_idx = UINT_MAX;
270 147 : fd_prog_txnp_ele_release( cache->txn.pool, txn );
271 147 : }
272 :
273 : void
274 : fd_progcache_advance_root( fd_progcache_join_t * cache,
275 147 : fd_progcache_fork_id_t fork_id ) {
276 147 : if( FD_UNLIKELY( !cache ) ) FD_LOG_CRIT(( "invalid arguments" ));
277 :
278 : /* Detach records from txns without acquiring record locks */
279 :
280 147 : fd_rwlock_write( &cache->shmem->txn.rwlock );
281 :
282 147 : ulong txn_max = fd_prog_txnp_max( cache->txn.pool );
283 147 : uint txn_idx = (uint)fd_prog_txnm_idx_query( cache->txn.map, &fork_id, UINT_MAX, cache->txn.pool );
284 147 : if( FD_UNLIKELY( txn_idx==UINT_MAX ) ) {
285 0 : FD_LOG_CRIT(( "fd_progcache_advance_root failed: invalid fork_id %lu", fork_id ));
286 0 : }
287 147 : if( FD_UNLIKELY( (ulong)txn_idx >= txn_max ) )
288 0 : FD_LOG_CRIT(( "progcache: corruption detected (advance_root txn_idx=%u txn_max=%lu)", txn_idx, txn_max ));
289 147 : fd_progcache_txn_t * txn = &cache->txn.pool[ txn_idx ];
290 147 : if( FD_UNLIKELY( txn->parent_idx!=UINT_MAX ) ) {
291 0 : FD_LOG_CRIT(( "fd_progcache_advance_root: parent of txn %lu is not root", fork_id ));
292 0 : }
293 :
294 147 : fd_progcache_cancel_prev_list( cache, txn );
295 147 : fd_progcache_cancel_next_list( cache, txn );
296 :
297 147 : txn->sibling_prev_idx = UINT_MAX;
298 147 : txn->sibling_next_idx = UINT_MAX;
299 147 : cache->shmem->txn.child_head_idx = txn->child_head_idx;
300 147 : cache->shmem->txn.child_tail_idx = txn->child_tail_idx;
301 :
302 147 : fd_progcache_txn_publish_one( cache, txn );
303 :
304 147 : fd_rwlock_unwrite( &cache->shmem->txn.rwlock );
305 147 : }
306 :
307 : void
308 : fd_progcache_cancel_fork( fd_progcache_join_t * cache,
309 363 : fd_progcache_fork_id_t fork_id ) {
310 363 : if( FD_UNLIKELY( !cache ) ) {
311 0 : FD_LOG_CRIT(( "invalid arguments" ));
312 0 : }
313 :
314 363 : fd_rwlock_write( &cache->shmem->txn.rwlock );
315 :
316 363 : fd_progcache_txn_t * txn = fd_prog_txnm_ele_query( cache->txn.map, &fork_id, NULL, cache->txn.pool );
317 363 : if( FD_UNLIKELY( !txn ) ) {
318 0 : FD_LOG_CRIT(( "fd_progcache_cancel failed: invalid fork_id %lu", fork_id ));
319 0 : }
320 363 : fd_progcache_cancel_tree( cache, txn );
321 :
322 363 : fd_rwlock_unwrite( &cache->shmem->txn.rwlock );
323 363 : }
324 :
325 : /* reset_rec_map frees all records in a progcache instance. */
326 :
327 : static void
328 3957 : reset_rec_map( fd_progcache_join_t * cache ) {
329 3957 : ulong chain_cnt = fd_prog_recm_chain_cnt( cache->rec.map );
330 510453 : for( ulong chain_idx=0UL; chain_idx<chain_cnt; chain_idx++ ) {
331 506496 : for(
332 506496 : fd_prog_recm_iter_t iter = fd_prog_recm_iter( cache->rec.map, chain_idx );
333 508953 : !fd_prog_recm_iter_done( iter );
334 506496 : ) {
335 2457 : fd_progcache_rec_t * rec = fd_prog_recm_iter_ele( iter );
336 2457 : ulong next = fd_prog_recm_private_idx( rec->map_next );
337 :
338 2457 : fd_prog_recm_query_t rec_query[1];
339 2457 : int err = fd_prog_recm_remove( cache->rec.map, &rec->pair, NULL, rec_query, FD_MAP_FLAG_BLOCKING );
340 2457 : if( FD_UNLIKELY( err!=FD_MAP_SUCCESS ) ) FD_LOG_CRIT(( "fd_prog_recm_remove failed (%i-%s)", err, fd_map_strerror( err ) ));
341 2457 : if( FD_UNLIKELY( !fd_rwlock_trywrite( &rec->lock ) ) )
342 0 : FD_LOG_CRIT(( "fd_progcache_reset requires quiescence: record still read-locked" ));
343 2457 : fd_progcache_rec_release( cache, rec );
344 :
345 2457 : iter.ele_idx = next;
346 2457 : }
347 506496 : }
348 3957 : }
349 :
350 : /* clear_txn_list does a depth-first traversal of the txn tree.
351 : Removes all txns. */
352 :
353 : static void
354 : clear_txn_list( fd_progcache_join_t * join,
355 7959 : uint txn_head_idx ) {
356 7959 : ulong txn_max = fd_prog_txnp_max( join->txn.pool );
357 11961 : for( uint idx = txn_head_idx; idx!=UINT_MAX; ) {
358 4002 : if( FD_UNLIKELY( (ulong)idx >= txn_max ) )
359 0 : FD_LOG_CRIT(( "progcache: corruption detected (clear_txn_list txn_idx=%u txn_max=%lu)", idx, txn_max ));
360 4002 : fd_progcache_txn_t * txn = &join->txn.pool[ idx ];
361 4002 : uint next_idx = txn->sibling_next_idx;
362 4002 : uint child_idx = txn->child_head_idx;
363 4002 : txn->rec_head_idx = UINT_MAX;
364 4002 : txn->rec_tail_idx = UINT_MAX;
365 4002 : txn->child_head_idx = UINT_MAX;
366 4002 : txn->child_tail_idx = UINT_MAX;
367 4002 : txn->parent_idx = UINT_MAX;
368 4002 : txn->sibling_prev_idx = UINT_MAX;
369 4002 : txn->sibling_next_idx = UINT_MAX;
370 4002 : clear_txn_list( join, child_idx );
371 4002 : 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" ));
372 4002 : fd_prog_txnp_ele_release( join->txn.pool, txn );
373 4002 : idx = next_idx;
374 4002 : }
375 7959 : }
376 :
377 : void
378 3957 : fd_progcache_reset( fd_progcache_join_t * cache ) {
379 : /* Zombies are not in the map, so reset_rec_map cannot see them. Collect
380 : them first; one that survives the sweep is held by an active reader. */
381 3957 : fd_prog_reclaim_work( cache );
382 688518 : for( ulong i=0UL; i<cache->rec.max; i++ ) {
383 684561 : uchar st = __atomic_load_n( &cache->rec.ele[ i ].state, __ATOMIC_RELAXED );
384 684561 : if( FD_UNLIKELY( ( st & ( FD_PROGCACHE_REC_LIVE|FD_PROGCACHE_REC_MAPPED ) )==FD_PROGCACHE_REC_LIVE ) )
385 0 : FD_LOG_CRIT(( "fd_progcache_reset requires quiescence: record %lu awaits collection (active readers?)", i ));
386 684561 : }
387 3957 : if( FD_UNLIKELY( cache->shmem->spill.lock.value || cache->shmem->spill.rec_used || cache->shmem->spill.spad_used ) )
388 0 : FD_LOG_CRIT(( "fd_progcache_reset requires quiescence: spill in use" ));
389 3957 : clear_txn_list( cache, cache->shmem->txn.child_head_idx );
390 3957 : cache->shmem->txn.child_head_idx = UINT_MAX;
391 3957 : cache->shmem->txn.child_tail_idx = UINT_MAX;
392 3957 : reset_rec_map( cache );
393 3957 : cache->shmem->txn.root = fd_progcache_fork_id_initial();
394 3957 : cache->shmem->txn.seq = fd_progcache_fork_id_initial();
395 3957 : }
396 :
397 : static int
398 : fd_progcache_verify_siblings( fd_progcache_txn_t * pool,
399 : ulong txn_max,
400 : uint head_idx,
401 : uint tail_idx,
402 : uint expected_parent_idx,
403 : uint * stack,
404 243 : ulong * stack_top ) {
405 :
406 702 : # define TEST(c) do { \
407 702 : if( FD_UNLIKELY( !(c) ) ) { FD_LOG_WARNING(( "FAIL: %s", #c )); return -1; } \
408 702 : } while(0)
409 :
410 243 : TEST( (head_idx==UINT_MAX)==(tail_idx==UINT_MAX) );
411 :
412 243 : uint last_idx = UINT_MAX;
413 297 : for( uint idx = head_idx; idx!=UINT_MAX; ) {
414 54 : TEST( idx<txn_max );
415 54 : fd_progcache_txn_t * child = &pool[ idx ];
416 54 : TEST( !child->tag );
417 54 : TEST( child->parent_idx==expected_parent_idx );
418 54 : child->tag = 1;
419 54 : TEST( *stack_top<FD_PROGCACHE_DEPTH_MAX );
420 54 : stack[ (*stack_top)++ ] = idx;
421 54 : last_idx = idx;
422 54 : uint next_idx = child->sibling_next_idx;
423 54 : if( next_idx!=UINT_MAX ) {
424 0 : TEST( next_idx<txn_max );
425 0 : TEST( pool[ next_idx ].sibling_prev_idx==idx );
426 0 : }
427 54 : idx = next_idx;
428 54 : }
429 243 : TEST( last_idx==tail_idx );
430 :
431 243 : # undef TEST
432 :
433 243 : return 0;
434 243 : }
435 :
436 : int
437 192 : fd_progcache_verify( fd_progcache_join_t * join ) {
438 :
439 172911 : # define TEST(c) do { \
440 172911 : if( FD_UNLIKELY( !(c) ) ) { FD_LOG_WARNING(( "FAIL: %s", #c )); return -1; } \
441 172911 : } while(0)
442 :
443 192 : TEST( join );
444 :
445 192 : fd_progcache_shmem_t * shmem = join->shmem;
446 192 : TEST( shmem );
447 192 : TEST( shmem->magic==FD_PROGCACHE_SHMEM_MAGIC );
448 189 : TEST( shmem->wksp_tag );
449 :
450 189 : TEST( !fd_prog_recm_verify( join->rec.map ) );
451 :
452 189 : ulong rec_max = join->rec.max;
453 189 : fd_progcache_rec_t * rec0 = join->rec.ele;
454 :
455 189 : ulong txn_max = fd_prog_txnp_max( join->txn.pool );
456 189 : TEST( !fd_prog_txnm_verify( join->txn.map, txn_max, join->txn.pool ) );
457 :
458 3645 : for( ulong i=0UL; i<txn_max; i++ ) join->txn.pool[ i ].tag = 0;
459 :
460 189 : uint stack[ FD_PROGCACHE_DEPTH_MAX ];
461 189 : ulong stack_top = 0UL;
462 :
463 189 : TEST( !fd_progcache_verify_siblings( join->txn.pool, txn_max,
464 189 : shmem->txn.child_head_idx, shmem->txn.child_tail_idx,
465 189 : UINT_MAX, stack, &stack_top ) );
466 :
467 243 : while( stack_top ) {
468 54 : uint txn_idx = stack[ --stack_top ];
469 54 : fd_progcache_txn_t * txn = &join->txn.pool[ txn_idx ];
470 54 : TEST( !fd_progcache_verify_siblings( join->txn.pool, txn_max,
471 54 : txn->child_head_idx, txn->child_tail_idx,
472 54 : txn_idx, stack, &stack_top ) );
473 54 : }
474 :
475 3549 : for( ulong i=0UL; i<txn_max; i++ ) {
476 3366 : if( !join->txn.pool[ i ].tag ) continue;
477 54 : fd_progcache_txn_t * txn = &join->txn.pool[ i ];
478 :
479 54 : TEST( (txn->rec_head_idx==UINT_MAX)==(txn->rec_tail_idx==UINT_MAX) );
480 :
481 54 : ulong rec_cnt = 0UL;
482 54 : uint prev = UINT_MAX;
483 534 : for( uint idx = txn->rec_head_idx; idx!=UINT_MAX; ) {
484 486 : TEST( idx<rec_max );
485 486 : TEST( rec_cnt<rec_max ); /* cycle detection */
486 486 : fd_progcache_rec_t * rec = &rec0[ idx ];
487 486 : TEST( rec->prev_idx==prev );
488 483 : TEST( rec->exists );
489 480 : prev = idx;
490 480 : idx = rec->next_idx;
491 480 : rec_cnt++;
492 480 : }
493 48 : TEST( prev==txn->rec_tail_idx );
494 48 : }
495 :
496 : /* A record is mapped, a zombie, free, or in flight -- never two. */
497 183 : ulong mapped_cnt = 0UL;
498 183 : ulong free_cnt = 0UL;
499 :
500 183 : ulong chain_cnt = fd_prog_recm_chain_cnt( join->rec.map );
501 25530 : for( ulong chain_idx=0UL; chain_idx<chain_cnt; chain_idx++ ) {
502 25350 : for(
503 25350 : fd_prog_recm_iter_t iter = fd_prog_recm_iter( join->rec.map, chain_idx );
504 26370 : !fd_prog_recm_iter_done( iter );
505 25350 : iter = fd_prog_recm_iter_next( iter )
506 25350 : ) {
507 1023 : fd_progcache_rec_t * rec = fd_prog_recm_iter_ele( iter );
508 1023 : TEST( rec->exists );
509 :
510 : /* Verify state is LIVE for mapped records */
511 1023 : ulong rec_idx = (ulong)( rec - rec0 );
512 1023 : TEST( rec_idx<rec_max );
513 1023 : uchar st = __atomic_load_n( &rec->state, __ATOMIC_RELAXED );
514 : /* Mapped means LIVE, or LOADING while its publisher finishes. */
515 1023 : TEST( st & ( FD_PROGCACHE_REC_LIVE | FD_PROGCACHE_REC_LOADING ) );
516 : /* Detached means rooted, so the load is over. */
517 1020 : if( atomic_load_explicit( &rec->txn_idx, memory_order_acquire )==UINT_MAX )
518 543 : TEST( st & FD_PROGCACHE_REC_LIVE );
519 1020 : TEST( st & FD_PROGCACHE_REC_MAPPED );
520 1020 : TEST( (ulong)rec->size_class==fd_progcache_rec_class( shmem, rec_idx ) );
521 1020 : mapped_cnt++;
522 1020 : TEST( rec->lock.value!=FD_RWLOCK_WRITE_LOCK ); /* push relies on this */
523 1020 : }
524 25350 : }
525 :
526 : /* A free record is write-locked, dead, and in its own class's list. */
527 1260 : for( ulong c=0UL; c<FD_PROGCACHE_CACHE_CLASS_CNT; c++ ) {
528 1080 : ulong base = shmem->cache.rec_base [ c ];
529 1080 : ulong class_max = shmem->cache.class_max[ c ];
530 :
531 1080 : ulong cnt = 0UL;
532 1080 : uint idx = (uint)( shmem->cache.free_top[ c ].ver_top & (ulong)UINT_MAX );
533 33174 : while( idx!=UINT_MAX ) {
534 32094 : TEST( (ulong)idx>=base && (ulong)idx<base+class_max );
535 32094 : fd_progcache_rec_t * rec = &rec0[ idx ];
536 32094 : TEST( !rec->exists );
537 32094 : TEST( rec->lock.value==FD_RWLOCK_WRITE_LOCK );
538 32094 : TEST( !__atomic_load_n( &rec->state, __ATOMIC_RELAXED ) );
539 32094 : TEST( cnt<class_max ); /* cycle detection */
540 32094 : cnt++;
541 32094 : idx = rec->free_next;
542 32094 : }
543 1080 : TEST( cnt<=class_max );
544 1080 : TEST( cnt==shmem->cache.free_cnt[ c ].val );
545 1080 : free_cnt += cnt;
546 1080 : }
547 :
548 180 : TEST( mapped_cnt+free_cnt<=rec_max );
549 :
550 180 : # undef TEST
551 :
552 180 : return 0;
553 180 : }
|
