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 119916 : fd_progcache_fork_id_t parent_fork_id ) {
20 119916 : if( FD_UNLIKELY( !cache ) ) FD_LOG_CRIT(( "invalid arguments" ));
21 :
22 119916 : fd_rwlock_write( &cache->shmem->txn.rwlock );
23 119916 : 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 119916 : ulong txn_max = fd_prog_txnp_max( cache->txn.pool );
28 119916 : ulong parent_idx;
29 119916 : uint * _child_head_idx;
30 119916 : uint * _child_tail_idx;
31 :
32 119916 : fd_progcache_fork_id_t root = __atomic_load_n( &cache->shmem->txn.root, memory_order_relaxed );
33 119916 : if( FD_UNLIKELY( parent_fork_id == root ) ) {
34 :
35 63945 : parent_idx = FD_PROGCACHE_TXN_IDX_NULL;
36 :
37 63945 : _child_head_idx = &cache->shmem->txn.child_head_idx;
38 63945 : _child_tail_idx = &cache->shmem->txn.child_tail_idx;
39 :
40 63945 : } else {
41 :
42 55971 : parent_idx = fd_prog_txnm_idx_query( cache->txn.map, &parent_fork_id, ULONG_MAX, cache->txn.pool );
43 55971 : 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 55971 : 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 55971 : _child_head_idx = &cache->txn.pool[ parent_idx ].child_head_idx;
50 55971 : _child_tail_idx = &cache->txn.pool[ parent_idx ].child_tail_idx;
51 :
52 55971 : }
53 :
54 119916 : uint txn_idx = (uint)fd_prog_txnp_idx_acquire( cache->txn.pool );
55 119916 : if( FD_UNLIKELY( txn_idx==UINT_MAX ) ) FD_LOG_ERR(( "fd_progcache_attach_child failed: transaction object pool out of memory" ));
56 119916 : fd_progcache_txn_t * txn = &cache->txn.pool[ txn_idx ];
57 119916 : txn->xid = __atomic_add_fetch( &cache->shmem->txn.seq, 1UL, memory_order_relaxed );
58 :
59 119916 : uint sibling_prev_idx = *_child_tail_idx;
60 :
61 119916 : int first_born = sibling_prev_idx==UINT_MAX;
62 119916 : 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 119916 : txn->parent_idx = (uint)parent_idx;
66 119916 : txn->child_head_idx = UINT_MAX;
67 119916 : txn->child_tail_idx = UINT_MAX;
68 119916 : txn->sibling_prev_idx = (uint)sibling_prev_idx;
69 119916 : txn->sibling_next_idx = UINT_MAX;
70 :
71 119916 : txn->rec_head_idx = UINT_MAX;
72 119916 : txn->rec_tail_idx = UINT_MAX;
73 :
74 : /* TODO: consider branchless impl */
75 120436 : if( FD_LIKELY( first_born ) ) *_child_head_idx = (uint)txn_idx; /* opt for non-compete */
76 >1844*10^16 : else cache->txn.pool[ sibling_prev_idx ].sibling_next_idx = (uint)txn_idx;
77 :
78 119916 : *_child_tail_idx = (uint)txn_idx;
79 :
80 119916 : fd_prog_txnm_idx_insert( cache->txn.map, txn_idx, cache->txn.pool );
81 :
82 119916 : fd_rwlock_unwrite( &cache->shmem->txn.rwlock );
83 119916 : return txn->xid;
84 119916 : }
85 :
86 : static void
87 : fd_progcache_cancel_one( fd_progcache_join_t * cache,
88 0 : fd_progcache_txn_t * txn ) {
89 0 : ulong rec_max = cache->rec.max;
90 0 : ulong txn_max = fd_prog_txnp_max( cache->txn.pool );
91 :
92 0 : fd_rwlock_write( &txn->lock );
93 :
94 0 : if( FD_UNLIKELY( txn->child_head_idx!=UINT_MAX ||
95 0 : 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 0 : for( uint idx = txn->rec_head_idx; idx!=UINT_MAX; ) {
103 0 : 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 0 : fd_progcache_rec_t * rec = &cache->rec.ele[ idx ];
106 0 : uint next_idx = rec->next_idx;
107 0 : 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 0 : atomic_store_explicit( &rec->txn_idx, UINT_MAX, memory_order_release );
110 0 : fd_racesan_hook( "prog_cancel_one:post_orphan" );
111 0 : fd_prog_delete_rec( cache, rec );
112 0 : idx = next_idx;
113 0 : }
114 :
115 0 : txn->rec_head_idx = UINT_MAX;
116 0 : txn->rec_tail_idx = UINT_MAX;
117 :
118 : /* Remove transaction from fork graph */
119 :
120 0 : uint self_idx = (uint)( txn - cache->txn.pool );
121 0 : uint prev_idx = txn->sibling_prev_idx;
122 0 : uint next_idx = txn->sibling_next_idx;
123 0 : 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 0 : if( prev_idx!=UINT_MAX ) {
129 0 : 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 0 : cache->txn.pool[ prev_idx ].sibling_next_idx = next_idx;
132 0 : }
133 0 : if( txn->parent_idx!=UINT_MAX ) {
134 0 : 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 0 : fd_progcache_txn_t * parent = &cache->txn.pool[ txn->parent_idx ];
137 0 : if( parent->child_head_idx==self_idx ) parent->child_head_idx = next_idx;
138 0 : if( parent->child_tail_idx==self_idx ) parent->child_tail_idx = prev_idx;
139 0 : } else {
140 0 : if( cache->shmem->txn.child_head_idx==self_idx ) cache->shmem->txn.child_head_idx = next_idx;
141 0 : if( cache->shmem->txn.child_tail_idx==self_idx ) cache->shmem->txn.child_tail_idx = prev_idx;
142 0 : }
143 :
144 : /* Remove transaction from index */
145 :
146 0 : 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 0 : fd_rwlock_unwrite( &txn->lock );
153 0 : fd_prog_txnp_ele_release( cache->txn.pool, txn );
154 0 : }
155 :
156 : /* Cancels txn and all children */
157 :
158 : static void
159 : fd_progcache_cancel_tree( fd_progcache_join_t * cache,
160 0 : fd_progcache_txn_t * txn ) {
161 0 : ulong txn_max = fd_prog_txnp_max( cache->txn.pool );
162 0 : for(;;) {
163 0 : uint child_idx = txn->child_head_idx;
164 0 : if( child_idx==UINT_MAX ) break;
165 0 : 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 0 : fd_progcache_txn_t * child = &cache->txn.pool[ child_idx ];
168 0 : fd_progcache_cancel_tree( cache, child );
169 0 : }
170 0 : fd_progcache_cancel_one( cache, txn );
171 0 : }
172 :
173 : /* Cancels all left/right siblings */
174 :
175 : static void
176 : fd_progcache_cancel_prev_list( fd_progcache_join_t * cache,
177 0 : fd_progcache_txn_t * txn ) {
178 0 : ulong txn_max = fd_prog_txnp_max( cache->txn.pool );
179 0 : uint cur_idx = txn->sibling_prev_idx;
180 0 : 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 0 : }
189 :
190 : static void
191 : fd_progcache_cancel_next_list( fd_progcache_join_t * cache,
192 0 : fd_progcache_txn_t * txn ) {
193 0 : ulong txn_max = fd_prog_txnp_max( cache->txn.pool );
194 0 : uint cur_idx = txn->sibling_next_idx;
195 0 : 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 0 : }
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 0 : fd_progcache_txn_t * txn ) {
211 :
212 : /* Phase 1: Mark transaction as "last published" */
213 :
214 0 : fd_progcache_fork_id_t const fork_id = txn->xid;
215 0 : 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 0 : fd_racesan_hook( "prog_publish_one:pre_xid_store" );
219 0 : __atomic_store_n( &cache->shmem->txn.root, fork_id, memory_order_release );
220 :
221 : /* Phase 2: Drain inserters from transaction */
222 :
223 0 : fd_rwlock_write( &txn->lock );
224 :
225 : /* Phase 3: Detach records */
226 :
227 0 : ulong rec_max = cache->rec.max;
228 0 : for( uint idx = txn->rec_head_idx; idx!=UINT_MAX; ) {
229 0 : 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 0 : uint next_idx = cache->rec.ele[ idx ].next_idx;
232 0 : 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 0 : atomic_store_explicit( &cache->rec.ele[ idx ].txn_idx, UINT_MAX, memory_order_release );
235 0 : fd_racesan_hook( "prog_publish_one:post_detach" );
236 0 : fd_progcache_admin_metrics_g.root_cnt++;
237 0 : idx = next_idx;
238 0 : }
239 :
240 0 : txn->rec_head_idx = UINT_MAX;
241 0 : txn->rec_tail_idx = UINT_MAX;
242 :
243 : /* Phase 4: Remove transaction from fork graph */
244 :
245 0 : { /* Adjust the parent pointers of the children to point to "last published" */
246 0 : ulong txn_max = fd_prog_txnp_max( cache->txn.pool );
247 0 : ulong child_idx = txn->child_head_idx;
248 0 : while( child_idx!=UINT_MAX ) {
249 0 : 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 0 : cache->txn.pool[ child_idx ].parent_idx = UINT_MAX;
252 0 : child_idx = cache->txn.pool[ child_idx ].sibling_next_idx;
253 0 : }
254 0 : }
255 :
256 : /* Phase 5: Remove transaction from index */
257 :
258 0 : 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 0 : fd_rwlock_unwrite( &txn->lock );
265 0 : txn->parent_idx = UINT_MAX;
266 0 : txn->sibling_prev_idx = UINT_MAX;
267 0 : txn->sibling_next_idx = UINT_MAX;
268 0 : txn->child_head_idx = UINT_MAX;
269 0 : txn->child_tail_idx = UINT_MAX;
270 0 : fd_prog_txnp_ele_release( cache->txn.pool, txn );
271 0 : }
272 :
273 : void
274 : fd_progcache_advance_root( fd_progcache_join_t * cache,
275 0 : fd_progcache_fork_id_t fork_id ) {
276 0 : if( FD_UNLIKELY( !cache ) ) FD_LOG_CRIT(( "invalid arguments" ));
277 :
278 : /* Detach records from txns without acquiring record locks */
279 :
280 0 : fd_rwlock_write( &cache->shmem->txn.rwlock );
281 :
282 0 : ulong txn_max = fd_prog_txnp_max( cache->txn.pool );
283 0 : uint txn_idx = (uint)fd_prog_txnm_idx_query( cache->txn.map, &fork_id, UINT_MAX, cache->txn.pool );
284 0 : 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 0 : 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 0 : fd_progcache_txn_t * txn = &cache->txn.pool[ txn_idx ];
290 0 : 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 0 : fd_progcache_cancel_prev_list( cache, txn );
295 0 : fd_progcache_cancel_next_list( cache, txn );
296 :
297 0 : txn->sibling_prev_idx = UINT_MAX;
298 0 : txn->sibling_next_idx = UINT_MAX;
299 0 : cache->shmem->txn.child_head_idx = txn->child_head_idx;
300 0 : cache->shmem->txn.child_tail_idx = txn->child_tail_idx;
301 :
302 0 : fd_progcache_txn_publish_one( cache, txn );
303 :
304 0 : fd_rwlock_unwrite( &cache->shmem->txn.rwlock );
305 0 : }
306 :
307 : void
308 : fd_progcache_cancel_fork( fd_progcache_join_t * cache,
309 0 : fd_progcache_fork_id_t fork_id ) {
310 0 : if( FD_UNLIKELY( !cache ) ) {
311 0 : FD_LOG_CRIT(( "invalid arguments" ));
312 0 : }
313 :
314 0 : fd_rwlock_write( &cache->shmem->txn.rwlock );
315 :
316 0 : fd_progcache_txn_t * txn = fd_prog_txnm_ele_query( cache->txn.map, &fork_id, NULL, cache->txn.pool );
317 0 : if( FD_UNLIKELY( !txn ) ) {
318 0 : FD_LOG_CRIT(( "fd_progcache_cancel failed: invalid fork_id %lu", fork_id ));
319 0 : }
320 0 : fd_progcache_cancel_tree( cache, txn );
321 :
322 0 : fd_rwlock_unwrite( &cache->shmem->txn.rwlock );
323 0 : }
324 :
325 : /* reset_rec_map frees all records in a progcache instance. */
326 :
327 : static void
328 64070 : reset_rec_map( fd_progcache_join_t * cache ) {
329 64070 : ulong chain_cnt = fd_prog_recm_chain_cnt( cache->rec.map );
330 8185273 : for( ulong chain_idx=0UL; chain_idx<chain_cnt; chain_idx++ ) {
331 8121203 : for(
332 8121203 : fd_prog_recm_iter_t iter = fd_prog_recm_iter( cache->rec.map, chain_idx );
333 8125891 : !fd_prog_recm_iter_done( iter );
334 8121203 : ) {
335 4688 : fd_progcache_rec_t * rec = fd_prog_recm_iter_ele( iter );
336 4688 : ulong next = fd_prog_recm_private_idx( rec->map_next );
337 :
338 4688 : fd_prog_recm_query_t rec_query[1];
339 4688 : int err = fd_prog_recm_remove( cache->rec.map, &rec->pair, NULL, rec_query, FD_MAP_FLAG_BLOCKING );
340 4688 : if( FD_UNLIKELY( err!=FD_MAP_SUCCESS ) ) FD_LOG_CRIT(( "fd_prog_recm_remove failed (%i-%s)", err, fd_map_strerror( err ) ));
341 4688 : if( FD_UNLIKELY( !fd_rwlock_trywrite( &rec->lock ) ) )
342 0 : FD_LOG_CRIT(( "fd_progcache_reset requires quiescence: record still read-locked" ));
343 4688 : fd_progcache_rec_release( cache, rec );
344 :
345 4688 : iter.ele_idx = next;
346 4688 : }
347 8121203 : }
348 64070 : }
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 184528 : uint txn_head_idx ) {
356 184528 : ulong txn_max = fd_prog_txnp_max( join->txn.pool );
357 304988 : for( uint idx = txn_head_idx; idx!=UINT_MAX; ) {
358 120460 : 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 120460 : fd_progcache_txn_t * txn = &join->txn.pool[ idx ];
361 120460 : uint next_idx = txn->sibling_next_idx;
362 120460 : uint child_idx = txn->child_head_idx;
363 120460 : txn->rec_head_idx = UINT_MAX;
364 120460 : txn->rec_tail_idx = UINT_MAX;
365 120460 : txn->child_head_idx = UINT_MAX;
366 120460 : txn->child_tail_idx = UINT_MAX;
367 120460 : txn->parent_idx = UINT_MAX;
368 120460 : txn->sibling_prev_idx = UINT_MAX;
369 120460 : txn->sibling_next_idx = UINT_MAX;
370 120460 : clear_txn_list( join, child_idx );
371 120460 : 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 120460 : fd_prog_txnp_ele_release( join->txn.pool, txn );
373 120460 : idx = next_idx;
374 120460 : }
375 184528 : }
376 :
377 : void
378 63996 : 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 63996 : fd_prog_reclaim_work( cache );
382 11136652 : for( ulong i=0UL; i<cache->rec.max; i++ ) {
383 11072656 : uchar st = __atomic_load_n( &cache->rec.ele[ i ].state, __ATOMIC_RELAXED );
384 11072656 : 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 11072656 : }
387 63996 : 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 63996 : clear_txn_list( cache, cache->shmem->txn.child_head_idx );
390 63996 : cache->shmem->txn.child_head_idx = UINT_MAX;
391 63996 : cache->shmem->txn.child_tail_idx = UINT_MAX;
392 63996 : reset_rec_map( cache );
393 63996 : cache->shmem->txn.root = fd_progcache_fork_id_initial();
394 63996 : }
395 :
396 : static int
397 : fd_progcache_verify_siblings( fd_progcache_txn_t * pool,
398 : ulong txn_max,
399 : uint head_idx,
400 : uint tail_idx,
401 : uint expected_parent_idx,
402 : uint * stack,
403 0 : ulong * stack_top ) {
404 :
405 0 : # define TEST(c) do { \
406 0 : if( FD_UNLIKELY( !(c) ) ) { FD_LOG_WARNING(( "FAIL: %s", #c )); return -1; } \
407 0 : } while(0)
408 :
409 0 : TEST( (head_idx==UINT_MAX)==(tail_idx==UINT_MAX) );
410 :
411 0 : uint last_idx = UINT_MAX;
412 0 : for( uint idx = head_idx; idx!=UINT_MAX; ) {
413 0 : TEST( idx<txn_max );
414 0 : fd_progcache_txn_t * child = &pool[ idx ];
415 0 : TEST( !child->tag );
416 0 : TEST( child->parent_idx==expected_parent_idx );
417 0 : child->tag = 1;
418 0 : TEST( *stack_top<FD_PROGCACHE_DEPTH_MAX );
419 0 : stack[ (*stack_top)++ ] = idx;
420 0 : last_idx = idx;
421 0 : uint next_idx = child->sibling_next_idx;
422 0 : if( next_idx!=UINT_MAX ) {
423 0 : TEST( next_idx<txn_max );
424 0 : TEST( pool[ next_idx ].sibling_prev_idx==idx );
425 0 : }
426 0 : idx = next_idx;
427 0 : }
428 0 : TEST( last_idx==tail_idx );
429 :
430 0 : # undef TEST
431 :
432 0 : return 0;
433 0 : }
434 :
435 : int
436 0 : fd_progcache_verify( fd_progcache_join_t * join ) {
437 :
438 0 : # define TEST(c) do { \
439 0 : if( FD_UNLIKELY( !(c) ) ) { FD_LOG_WARNING(( "FAIL: %s", #c )); return -1; } \
440 0 : } while(0)
441 :
442 0 : TEST( join );
443 :
444 0 : fd_progcache_shmem_t * shmem = join->shmem;
445 0 : TEST( shmem );
446 0 : TEST( shmem->magic==FD_PROGCACHE_SHMEM_MAGIC );
447 0 : TEST( shmem->wksp_tag );
448 :
449 0 : TEST( !fd_prog_recm_verify( join->rec.map ) );
450 :
451 0 : ulong rec_max = join->rec.max;
452 0 : fd_progcache_rec_t * rec0 = join->rec.ele;
453 :
454 0 : ulong txn_max = fd_prog_txnp_max( join->txn.pool );
455 0 : TEST( !fd_prog_txnm_verify( join->txn.map, txn_max, join->txn.pool ) );
456 :
457 0 : for( ulong i=0UL; i<txn_max; i++ ) join->txn.pool[ i ].tag = 0;
458 :
459 0 : uint stack[ FD_PROGCACHE_DEPTH_MAX ];
460 0 : ulong stack_top = 0UL;
461 :
462 0 : TEST( !fd_progcache_verify_siblings( join->txn.pool, txn_max,
463 0 : shmem->txn.child_head_idx, shmem->txn.child_tail_idx,
464 0 : UINT_MAX, stack, &stack_top ) );
465 :
466 0 : while( stack_top ) {
467 0 : uint txn_idx = stack[ --stack_top ];
468 0 : fd_progcache_txn_t * txn = &join->txn.pool[ txn_idx ];
469 0 : TEST( !fd_progcache_verify_siblings( join->txn.pool, txn_max,
470 0 : txn->child_head_idx, txn->child_tail_idx,
471 0 : txn_idx, stack, &stack_top ) );
472 0 : }
473 :
474 0 : for( ulong i=0UL; i<txn_max; i++ ) {
475 0 : if( !join->txn.pool[ i ].tag ) continue;
476 0 : fd_progcache_txn_t * txn = &join->txn.pool[ i ];
477 :
478 0 : TEST( (txn->rec_head_idx==UINT_MAX)==(txn->rec_tail_idx==UINT_MAX) );
479 :
480 0 : ulong rec_cnt = 0UL;
481 0 : uint prev = UINT_MAX;
482 0 : for( uint idx = txn->rec_head_idx; idx!=UINT_MAX; ) {
483 0 : TEST( idx<rec_max );
484 0 : TEST( rec_cnt<rec_max ); /* cycle detection */
485 0 : fd_progcache_rec_t * rec = &rec0[ idx ];
486 0 : TEST( rec->prev_idx==prev );
487 0 : TEST( rec->exists );
488 0 : prev = idx;
489 0 : idx = rec->next_idx;
490 0 : rec_cnt++;
491 0 : }
492 0 : TEST( prev==txn->rec_tail_idx );
493 0 : }
494 :
495 : /* A record is mapped, a zombie, free, or in flight -- never two. */
496 0 : ulong mapped_cnt = 0UL;
497 0 : ulong free_cnt = 0UL;
498 :
499 0 : ulong chain_cnt = fd_prog_recm_chain_cnt( join->rec.map );
500 0 : for( ulong chain_idx=0UL; chain_idx<chain_cnt; chain_idx++ ) {
501 0 : for(
502 0 : fd_prog_recm_iter_t iter = fd_prog_recm_iter( join->rec.map, chain_idx );
503 0 : !fd_prog_recm_iter_done( iter );
504 0 : iter = fd_prog_recm_iter_next( iter )
505 0 : ) {
506 0 : fd_progcache_rec_t * rec = fd_prog_recm_iter_ele( iter );
507 0 : TEST( rec->exists );
508 :
509 : /* Verify state is LIVE for mapped records */
510 0 : ulong rec_idx = (ulong)( rec - rec0 );
511 0 : TEST( rec_idx<rec_max );
512 0 : uchar st = __atomic_load_n( &rec->state, __ATOMIC_RELAXED );
513 : /* Mapped means LIVE, or LOADING while its publisher finishes. */
514 0 : TEST( st & ( FD_PROGCACHE_REC_LIVE | FD_PROGCACHE_REC_LOADING ) );
515 : /* Detached means rooted, so the load is over. */
516 0 : if( atomic_load_explicit( &rec->txn_idx, memory_order_acquire )==UINT_MAX )
517 0 : TEST( st & FD_PROGCACHE_REC_LIVE );
518 0 : TEST( st & FD_PROGCACHE_REC_MAPPED );
519 0 : TEST( (ulong)rec->size_class==fd_progcache_rec_class( shmem, rec_idx ) );
520 0 : mapped_cnt++;
521 0 : TEST( rec->lock.value!=FD_RWLOCK_WRITE_LOCK ); /* push relies on this */
522 0 : }
523 0 : }
524 :
525 : /* A free record is write-locked, dead, and in its own class's list. */
526 0 : for( ulong c=0UL; c<FD_PROGCACHE_CACHE_CLASS_CNT; c++ ) {
527 0 : ulong base = shmem->cache.rec_base [ c ];
528 0 : ulong class_max = shmem->cache.class_max[ c ];
529 :
530 0 : ulong cnt = 0UL;
531 0 : uint idx = (uint)( shmem->cache.free_top[ c ].ver_top & (ulong)UINT_MAX );
532 0 : while( idx!=UINT_MAX ) {
533 0 : TEST( (ulong)idx>=base && (ulong)idx<base+class_max );
534 0 : fd_progcache_rec_t * rec = &rec0[ idx ];
535 0 : TEST( !rec->exists );
536 0 : TEST( rec->lock.value==FD_RWLOCK_WRITE_LOCK );
537 0 : TEST( !__atomic_load_n( &rec->state, __ATOMIC_RELAXED ) );
538 0 : TEST( cnt<class_max ); /* cycle detection */
539 0 : cnt++;
540 0 : idx = rec->free_next;
541 0 : }
542 0 : TEST( cnt<=class_max );
543 0 : TEST( cnt==shmem->cache.free_cnt[ c ].val );
544 0 : free_cnt += cnt;
545 0 : }
546 :
547 0 : TEST( mapped_cnt+free_cnt<=rec_max );
548 :
549 0 : # undef TEST
550 :
551 0 : return 0;
552 0 : }
|
