Line data Source code
1 : #include "fd_funk.h"
2 :
3 : /* Provide the actual transaction map implementation */
4 :
5 : #define POOL_NAME fd_funk_txn_pool
6 2111415 : #define POOL_ELE_T fd_funk_txn_t
7 : #define POOL_IDX_T uint
8 5260746 : #define POOL_NEXT map_next
9 : #define POOL_IMPL_STYLE 2
10 : #include "../util/tmpl/fd_pool_para.c"
11 :
12 : #define MAP_NAME fd_funk_txn_map
13 387426618 : #define MAP_ELE_T fd_funk_txn_t
14 0 : #define MAP_KEY_T fd_funk_txn_xid_t
15 1055640 : #define MAP_KEY xid
16 : #define MAP_KEY_EQ(k0,k1) fd_funk_txn_xid_eq((k0),(k1))
17 : #define MAP_KEY_HASH(k0,seed) fd_funk_txn_xid_hash((k0),(seed))
18 164877203 : #define MAP_NEXT map_next
19 : #define MAP_HASH map_hash
20 33 : #define MAP_MAGIC (0xf173da2ce7172db0UL) /* Firedancer txn db version 0 */
21 : #define MAP_IMPL_STYLE 2
22 : #include "../util/tmpl/fd_map_chain_para.c"
23 :
24 : /* TODO: remove this lock */
25 : #include "../flamenco/fd_rwlock.h"
26 : static fd_rwlock_t funk_txn_lock[ 1 ] = {0};
27 :
28 : void
29 0 : fd_funk_txn_start_read( fd_funk_t * funk FD_PARAM_UNUSED ) {
30 0 : fd_rwlock_read( funk_txn_lock );
31 0 : }
32 :
33 : void
34 0 : fd_funk_txn_end_read( fd_funk_t * funk FD_PARAM_UNUSED ) {
35 0 : fd_rwlock_unread( funk_txn_lock );
36 0 : }
37 :
38 : void
39 15 : fd_funk_txn_start_write( fd_funk_t * funk FD_PARAM_UNUSED ) {
40 15 : fd_rwlock_write( funk_txn_lock );
41 15 : }
42 :
43 : void
44 15 : fd_funk_txn_end_write( fd_funk_t * funk FD_PARAM_UNUSED ) {
45 15 : fd_rwlock_unwrite( funk_txn_lock );
46 15 : }
47 :
48 : fd_funk_txn_t *
49 : fd_funk_txn_prepare( fd_funk_t * funk,
50 : fd_funk_txn_t * parent,
51 : fd_funk_txn_xid_t const * xid,
52 1317777 : int verbose ) {
53 :
54 : #ifdef FD_FUNK_HANDHOLDING
55 : if( FD_UNLIKELY( !funk ) ) {
56 : if( FD_UNLIKELY( verbose ) ) FD_LOG_WARNING(( "NULL funk" ));
57 : return NULL;
58 : }
59 : if( FD_UNLIKELY( !xid ) ) {
60 : if( FD_UNLIKELY( verbose ) ) FD_LOG_WARNING(( "NULL xid" ));
61 : return NULL;
62 : }
63 : if( FD_UNLIKELY( parent && !fd_funk_txn_valid( funk, parent ) ) ) {
64 : if( FD_UNLIKELY( verbose ) ) FD_LOG_WARNING(( "bad txn" ));
65 : return NULL;
66 : }
67 : if( FD_UNLIKELY( fd_funk_txn_xid_eq_root( xid ) ) ) {
68 : if( FD_UNLIKELY( verbose ) ) FD_LOG_WARNING(( "xid is the root" ));
69 : return NULL;
70 : }
71 : if( FD_UNLIKELY( fd_funk_txn_xid_eq( xid, funk->shmem->last_publish ) ) ) {
72 : if( FD_UNLIKELY( verbose ) ) FD_LOG_WARNING(( "xid is the last published" ));
73 : return NULL;
74 : }
75 : #endif
76 :
77 1317777 : fd_funk_txn_map_query_t query[1];
78 1317777 : if( FD_UNLIKELY( fd_funk_txn_map_query_try( funk->txn_map, xid, NULL, query, 0 ) != FD_MAP_ERR_KEY ) ) {
79 262125 : if( FD_UNLIKELY( verbose ) ) FD_LOG_WARNING(( "xid in use" ));
80 262125 : return NULL;
81 262125 : }
82 :
83 1055652 : ulong parent_idx;
84 1055652 : uint * _child_head_cidx;
85 1055652 : uint * _child_tail_cidx;
86 :
87 1055652 : if( FD_LIKELY( !parent ) ) { /* opt for incr pub */
88 :
89 445418 : parent_idx = FD_FUNK_TXN_IDX_NULL;
90 :
91 445418 : _child_head_cidx = &funk->shmem->child_head_cidx;
92 445418 : _child_tail_cidx = &funk->shmem->child_tail_cidx;
93 :
94 610234 : } else {
95 :
96 610234 : parent_idx = (ulong)(parent - funk->txn_pool->ele);
97 :
98 610234 : _child_head_cidx = &parent->child_head_cidx;
99 610234 : _child_tail_cidx = &parent->child_tail_cidx;
100 :
101 610234 : }
102 :
103 : /* Get a new transaction from the map */
104 :
105 1055652 : fd_funk_txn_t * txn = fd_funk_txn_pool_acquire( funk->txn_pool, NULL, 1, NULL );
106 1055652 : if( txn == NULL ) {
107 12 : if( FD_UNLIKELY( verbose ) ) FD_LOG_WARNING(( "transaction pool is exhuasted" ));
108 12 : return NULL;
109 12 : }
110 1055640 : fd_funk_txn_xid_copy( &txn->xid, xid );
111 1055640 : ulong txn_idx = (ulong)(txn - funk->txn_pool->ele);
112 :
113 : /* Join the family */
114 :
115 1055640 : ulong sibling_prev_idx = fd_funk_txn_idx( *_child_tail_cidx );
116 :
117 1055640 : int first_born = fd_funk_txn_idx_is_null( sibling_prev_idx );
118 :
119 1055640 : txn->parent_cidx = fd_funk_txn_cidx( parent_idx );
120 1055640 : txn->child_head_cidx = fd_funk_txn_cidx( FD_FUNK_TXN_IDX_NULL );
121 1055640 : txn->child_tail_cidx = fd_funk_txn_cidx( FD_FUNK_TXN_IDX_NULL );
122 1055640 : txn->sibling_prev_cidx = fd_funk_txn_cidx( sibling_prev_idx );
123 1055640 : txn->sibling_next_cidx = fd_funk_txn_cidx( FD_FUNK_TXN_IDX_NULL );
124 1055640 : txn->stack_cidx = fd_funk_txn_cidx( FD_FUNK_TXN_IDX_NULL );
125 1055640 : txn->tag = 0UL;
126 :
127 1055640 : txn->lock = 0;
128 1055640 : txn->rec_head_idx = FD_FUNK_REC_IDX_NULL;
129 1055640 : txn->rec_tail_idx = FD_FUNK_REC_IDX_NULL;
130 :
131 : /* TODO: consider branchless impl */
132 1055640 : if( FD_LIKELY( first_born ) ) *_child_head_cidx = fd_funk_txn_cidx( txn_idx ); /* opt for non-compete */
133 537283 : else funk->txn_pool->ele[ sibling_prev_idx ].sibling_next_cidx = fd_funk_txn_cidx( txn_idx );
134 :
135 1055640 : *_child_tail_cidx = fd_funk_txn_cidx( txn_idx );
136 :
137 1055640 : fd_funk_txn_map_insert( funk->txn_map, txn, FD_MAP_FLAG_BLOCKING );
138 :
139 1055640 : return txn;
140 1055652 : }
141 :
142 : /* fd_funk_txn_cancel_childless cancels a transaction that is known
143 : to be childless. Callers have already validated our input arguments.
144 : Assumes that cancelling in the app can't fail but that could be
145 : straightforward to support by giving this an error and plumbing
146 : through to abort the overall cancel operation when it hits a error. */
147 :
148 : static void
149 : fd_funk_txn_cancel_childless( fd_funk_t * funk,
150 837970 : ulong txn_idx ) {
151 :
152 : /* Remove all records used by this transaction. Note that we don't
153 : need to bother doing all the individual removal operations as we
154 : are removing the whole list. We do reset the record transaction
155 : idx with NULL though we can detect cycles as soon as possible
156 : and abort. */
157 :
158 837970 : fd_wksp_t * wksp = funk->wksp;
159 837970 : fd_alloc_t * alloc = funk->alloc;
160 837970 : fd_funk_rec_map_t * rec_map = funk->rec_map;
161 837970 : fd_funk_rec_pool_t * rec_pool = funk->rec_pool;
162 837970 : ulong rec_max = fd_funk_rec_pool_ele_max( rec_pool );
163 837970 : fd_funk_txn_map_t * txn_map = funk->txn_map;
164 837970 : fd_funk_txn_pool_t * txn_pool = funk->txn_pool;
165 :
166 837970 : fd_funk_txn_t * txn = &txn_pool->ele[ txn_idx ];
167 837970 : uint rec_idx = txn->rec_head_idx;
168 20036546 : while( !fd_funk_rec_idx_is_null( rec_idx ) ) {
169 :
170 19198576 : if( FD_UNLIKELY( rec_idx>=rec_max ) ) FD_LOG_CRIT(( "memory corruption detected (bad idx)" ));
171 19198576 : if( FD_UNLIKELY( fd_funk_txn_idx( rec_pool->ele[ rec_idx ].txn_cidx )!=txn_idx ) )
172 0 : FD_LOG_CRIT(( "memory corruption detected (cycle or bad idx)" ));
173 :
174 19198576 : fd_funk_rec_t * rec = &rec_pool->ele[ rec_idx ];
175 19198576 : uint next_idx = rec->next_idx;
176 19198576 : rec->txn_cidx = fd_funk_txn_cidx( FD_FUNK_TXN_IDX_NULL );
177 :
178 19198576 : for(;;) {
179 19198576 : fd_funk_rec_map_query_t rec_query[1];
180 19198576 : int err = fd_funk_rec_map_remove( rec_map, fd_funk_rec_pair( rec ), NULL, rec_query, FD_MAP_FLAG_BLOCKING );
181 19198576 : if( FD_UNLIKELY( err == FD_MAP_ERR_AGAIN ) ) continue;
182 19198576 : if( err == FD_MAP_ERR_KEY ) break;
183 19198576 : if( FD_UNLIKELY( err != FD_MAP_SUCCESS ) ) FD_LOG_CRIT(( "map corruption" ));
184 19198576 : if( rec != fd_funk_rec_map_query_ele( rec_query ) ) break;
185 19198576 : fd_funk_val_flush( rec, alloc, wksp );
186 19198576 : fd_funk_rec_pool_release( rec_pool, rec, 1 );
187 19198576 : break;
188 19198576 : }
189 :
190 19198576 : rec_idx = next_idx;
191 19198576 : }
192 :
193 : /* Leave the family */
194 :
195 837970 : ulong sibling_prev_idx = fd_funk_txn_idx( txn->sibling_prev_cidx );
196 837970 : ulong sibling_next_idx = fd_funk_txn_idx( txn->sibling_next_cidx );
197 :
198 : /* TODO: Consider branchless impl */
199 :
200 837970 : if( FD_LIKELY( fd_funk_txn_idx_is_null( sibling_prev_idx ) ) ) { /* opt for non-compete */
201 407273 : ulong parent_idx = fd_funk_txn_idx( txn_pool->ele[ txn_idx ].parent_cidx );
202 407273 : if( FD_LIKELY( fd_funk_txn_idx_is_null( parent_idx ) ) ) { /* No older sib and is a funk child, opt for incr pub */
203 136749 : funk->shmem->child_head_cidx = fd_funk_txn_cidx( sibling_next_idx );
204 270524 : } else { /* No older sib and has parent */
205 270524 : txn_pool->ele[ parent_idx ].child_head_cidx = fd_funk_txn_cidx( sibling_next_idx );
206 270524 : }
207 430697 : } else { /* Has older sib */
208 430697 : txn_pool->ele[ sibling_prev_idx ].sibling_next_cidx = fd_funk_txn_cidx( sibling_next_idx );
209 430697 : }
210 :
211 837970 : if( FD_LIKELY( fd_funk_txn_idx_is_null( sibling_next_idx ) ) ) { /* opt for non-compete */
212 660533 : ulong parent_idx = fd_funk_txn_idx( txn_pool->ele[ txn_idx ].parent_cidx );
213 660533 : if( FD_LIKELY( fd_funk_txn_idx_is_null( parent_idx ) ) ) { /* No younger sib and is a funk child, opt for incr pub */
214 262899 : funk->shmem->child_tail_cidx = fd_funk_txn_cidx( sibling_prev_idx );
215 397634 : } else { /* No younger sib and has parent */
216 397634 : txn_pool->ele[ parent_idx ].child_tail_cidx = fd_funk_txn_cidx( sibling_prev_idx );
217 397634 : }
218 660533 : } else { /* Has younger sib */
219 177437 : txn_pool->ele[ sibling_next_idx ].sibling_prev_cidx = fd_funk_txn_cidx( sibling_prev_idx );
220 177437 : }
221 :
222 837970 : fd_funk_txn_map_query_t query[1];
223 837970 : if( fd_funk_txn_map_remove( txn_map, fd_funk_txn_xid( txn ), NULL, query, FD_MAP_FLAG_BLOCKING ) == FD_MAP_SUCCESS ) {
224 837970 : fd_funk_txn_pool_release( txn_pool, txn, 1 );
225 837970 : }
226 837970 : }
227 :
228 : /* fd_funk_txn_cancel_family cancels a transaction and all its
229 : descendants in a tree-depth-first-ordered sense from youngest to
230 : oldest. Callers have already validated our input arguments. Returns
231 : the number of transactions canceled. */
232 :
233 : static ulong
234 : fd_funk_txn_cancel_family( fd_funk_t * funk,
235 : ulong tag,
236 475250 : ulong txn_idx ) {
237 475250 : ulong cancel_cnt = 0UL;
238 :
239 475250 : ulong parent_stack_idx = FD_FUNK_TXN_IDX_NULL;
240 :
241 1200690 : for(;;) {
242 :
243 1200690 : fd_funk_txn_t * txn = &funk->txn_pool->ele[ txn_idx ];
244 1200690 : txn->tag = tag;
245 :
246 1200690 : ulong youngest_idx = fd_funk_txn_idx( txn->child_tail_cidx );
247 1200690 : if( FD_LIKELY( fd_funk_txn_idx_is_null( youngest_idx ) ) ) { /* txn is is childless, opt for incr pub */
248 :
249 837970 : fd_funk_txn_cancel_childless( funk, txn_idx ); /* If this can fail, return cancel_cnt here on fail */
250 837970 : cancel_cnt++;
251 :
252 837970 : txn_idx = parent_stack_idx; /* Pop the parent stack */
253 837970 : if( FD_LIKELY( fd_funk_txn_idx_is_null( txn_idx ) ) ) break; /* If stack is empty, we are done, opt for incr pub */
254 362720 : parent_stack_idx = fd_funk_txn_idx( funk->txn_pool->ele[ txn_idx ].stack_cidx );
255 362720 : continue;
256 837970 : }
257 :
258 : /* txn has at least one child and the youngest is youngest_idx. Tag
259 : the youngest child, push txn onto the parent stack and recurse
260 : into the youngest child. */
261 :
262 362720 : txn->stack_cidx = fd_funk_txn_cidx( parent_stack_idx );
263 362720 : parent_stack_idx = txn_idx;
264 :
265 362720 : txn_idx = youngest_idx;
266 362720 : }
267 :
268 475250 : return cancel_cnt;
269 475250 : }
270 :
271 : ulong
272 : fd_funk_txn_cancel( fd_funk_t * funk,
273 : fd_funk_txn_t * txn,
274 147150 : int verbose ) {
275 :
276 : #ifdef FD_FUNK_HANDHOLDING
277 : if( FD_UNLIKELY( !funk ) ) {
278 : if( FD_UNLIKELY( verbose ) ) FD_LOG_WARNING(( "NULL funk" ));
279 : return 0UL;
280 : }
281 : if( FD_UNLIKELY( !fd_funk_txn_valid( funk, txn ) ) ) {
282 : if( FD_UNLIKELY( verbose ) ) FD_LOG_WARNING(( "bad txn" ));
283 : return 0UL;
284 : }
285 : #else
286 147150 : (void)verbose;
287 147150 : #endif
288 :
289 147150 : ulong txn_idx = (ulong)(txn - funk->txn_pool->ele);
290 147150 : return fd_funk_txn_cancel_family( funk, funk->shmem->cycle_tag++, txn_idx );
291 147150 : }
292 :
293 : /* fd_funk_txn_oldest_sibling returns the index of the oldest sibling
294 : in txn_idx's family. Callers have already validated our input
295 : arguments. The caller should validate the return index. */
296 :
297 : static inline ulong
298 : fd_funk_txn_oldest_sibling( fd_funk_t * funk,
299 215984 : ulong txn_idx ) {
300 215984 : ulong parent_idx = fd_funk_txn_idx( funk->txn_pool->ele[ txn_idx ].parent_cidx );
301 :
302 215984 : if( FD_LIKELY( fd_funk_txn_idx_is_null( parent_idx ) ) ) return fd_funk_txn_idx( funk->shmem->child_head_cidx ); /* opt for incr pub */
303 :
304 9432 : return fd_funk_txn_idx( funk->txn_pool->ele[ parent_idx ].child_head_cidx );
305 215984 : }
306 :
307 : /* fd_funk_txn_cancel_sibling_list cancels siblings from sibling_idx down
308 : to the youngest sibling inclusive in the order from youngest to
309 : sibling_idx. Callers have already validated our input arguments
310 : except sibling_idx. Returns the number of cancelled transactions
311 : (should be at least 1). If any sibling is skip_idx, it will be not
312 : be cancelled but still tagged as visited. Passing
313 : FD_FUNK_TXN_IDX_NULL for skip_idx will cancel all siblings from
314 : sibling_idx to the youngest inclusive. */
315 :
316 : static ulong
317 : fd_funk_txn_cancel_sibling_list( fd_funk_t * funk,
318 : ulong tag,
319 : ulong sibling_idx,
320 215984 : ulong skip_idx ) {
321 :
322 215984 : ulong cancel_stack_idx = FD_FUNK_TXN_IDX_NULL;
323 :
324 : /* Push siblings_idx and its younger siblings inclusive (skipping
325 : sibling skip_idx if encounter) onto the cancel stack from oldest to
326 : youngest (such that we cancel youngest to oldest). */
327 :
328 544084 : for(;;) {
329 :
330 : /* At this point, sibling_idx is a sibling we might want to add to
331 : the sibling stack. Validate and tag it. */
332 :
333 544084 : fd_funk_txn_t * sibling = &funk->txn_pool->ele[ sibling_idx ];
334 544084 : sibling->tag = tag;
335 :
336 544084 : if( FD_UNLIKELY( sibling_idx!=skip_idx ) ) { /* Not skip_idx so push onto the cancel stack, opt for non-compete */
337 328100 : sibling->stack_cidx = fd_funk_txn_cidx( cancel_stack_idx );
338 328100 : cancel_stack_idx = sibling_idx;
339 328100 : }
340 :
341 544084 : ulong younger_idx = fd_funk_txn_idx( sibling->sibling_next_cidx );
342 544084 : if( FD_LIKELY( fd_funk_txn_idx_is_null( younger_idx ) ) ) break; /* opt for non-compete */
343 328100 : sibling_idx = younger_idx;
344 :
345 328100 : }
346 :
347 : /* Cancel all transactions and their descendants on the cancel stack */
348 :
349 215984 : ulong cancel_cnt = 0UL;
350 :
351 544084 : while( !fd_funk_txn_idx_is_null( cancel_stack_idx ) ) { /* TODO: peel first iter to make more predictable? */
352 328100 : ulong sibling_idx = cancel_stack_idx;
353 328100 : cancel_stack_idx = fd_funk_txn_idx( funk->txn_pool->ele[ sibling_idx ].stack_cidx );
354 328100 : cancel_cnt += fd_funk_txn_cancel_family( funk, tag, sibling_idx );
355 328100 : }
356 :
357 215984 : return cancel_cnt;
358 215984 : }
359 :
360 : ulong
361 : fd_funk_txn_cancel_siblings( fd_funk_t * funk,
362 : fd_funk_txn_t * txn,
363 0 : int verbose ) {
364 :
365 : #ifdef FD_FUNK_HANDHOLDING
366 : if( FD_UNLIKELY( !funk ) ) {
367 : if( FD_UNLIKELY( verbose ) ) FD_LOG_WARNING(( "NULL funk" ));
368 : return 0UL;
369 : }
370 : if( FD_UNLIKELY( !fd_funk_txn_valid( funk, txn ) ) ) {
371 : if( FD_UNLIKELY( verbose ) ) FD_LOG_WARNING(( "bad txn" ));
372 : return 0UL;
373 : }
374 : #else
375 0 : (void)verbose;
376 0 : #endif
377 :
378 0 : ulong txn_idx = (ulong)(txn - funk->txn_pool->ele);
379 :
380 0 : ulong oldest_idx = fd_funk_txn_oldest_sibling( funk, txn_idx );
381 :
382 0 : return fd_funk_txn_cancel_sibling_list( funk, funk->shmem->cycle_tag++, oldest_idx, txn_idx );
383 0 : }
384 :
385 : ulong
386 : fd_funk_txn_cancel_children( fd_funk_t * funk,
387 : fd_funk_txn_t * txn,
388 0 : int verbose ) {
389 :
390 : #ifdef FD_FUNK_HANDHOLDING
391 : if( FD_UNLIKELY( !funk ) ) {
392 : if( FD_UNLIKELY( verbose ) ) FD_LOG_WARNING(( "NULL funk" ));
393 : return 0UL;
394 : }
395 : if( FD_UNLIKELY( !fd_funk_txn_valid( funk, txn ) ) ) {
396 : if( FD_UNLIKELY( verbose ) ) FD_LOG_WARNING(( "bad txn" ));
397 : return 0UL;
398 : }
399 : #else
400 0 : (void)verbose;
401 0 : #endif
402 :
403 0 : ulong oldest_idx;
404 :
405 0 : if( FD_LIKELY( txn == NULL ) ) {
406 0 : oldest_idx = fd_funk_txn_idx( funk->shmem->child_head_cidx ); /* opt for non-compete */
407 0 : } else {
408 0 : oldest_idx = fd_funk_txn_idx( txn->child_head_cidx );
409 0 : }
410 :
411 0 : if( fd_funk_txn_idx_is_null( oldest_idx ) ) {
412 0 : return 0UL;
413 0 : }
414 :
415 0 : return fd_funk_txn_cancel_sibling_list( funk, funk->shmem->cycle_tag++, oldest_idx, FD_FUNK_TXN_IDX_NULL );
416 0 : }
417 :
418 : ulong
419 0 : fd_funk_txn_cancel_root( fd_funk_t * funk ) {
420 0 : fd_funk_rec_map_t * rec_map = funk->rec_map;
421 0 : fd_funk_rec_pool_t * rec_pool = funk->rec_pool;
422 0 : ulong chain_cnt = fd_funk_rec_map_chain_cnt( rec_map );
423 0 : for( ulong chain_idx=0UL; chain_idx<chain_cnt; chain_idx++ ) {
424 0 : for(
425 0 : fd_funk_rec_map_iter_t iter = fd_funk_rec_map_iter( rec_map, chain_idx );
426 0 : !fd_funk_rec_map_iter_done( iter );
427 0 : iter = fd_funk_rec_map_iter_next( iter )
428 0 : ) {
429 0 : for (;;) {
430 0 : fd_funk_rec_map_query_t rec_query[1];
431 0 : int err = fd_funk_rec_map_remove( rec_map, fd_funk_rec_pair( iter.ele ), NULL, rec_query, FD_MAP_FLAG_BLOCKING );
432 0 : if( FD_UNLIKELY( err == FD_MAP_ERR_AGAIN ) ) continue;
433 0 : if( err == FD_MAP_ERR_KEY ) break;
434 0 : if( FD_UNLIKELY( err != FD_MAP_SUCCESS ) ) FD_LOG_CRIT(( "map corruption" ));
435 0 : if( iter.ele != fd_funk_rec_map_query_ele( rec_query ) ) break;
436 0 : fd_funk_val_flush( fd_funk_rec_map_iter_ele( iter ), fd_funk_alloc( funk ), fd_funk_wksp( funk ) );
437 0 : fd_funk_rec_pool_release( rec_pool, fd_funk_rec_map_query_ele( rec_query ), 1 );
438 0 : }
439 0 : }
440 0 : }
441 :
442 0 : return 0UL;
443 0 : }
444 :
445 : /* Cancel all outstanding transactions */
446 :
447 : ulong
448 : fd_funk_txn_cancel_all( fd_funk_t * funk,
449 0 : int verbose ) {
450 0 : return fd_funk_txn_cancel_children( funk, NULL, verbose );
451 0 : }
452 :
453 : /* fd_funk_txn_update applies the record updates in transaction txn_idx
454 : to another transaction or the parent transaction. Callers have
455 : already validated our input arguments.
456 :
457 : On entry, the head/tail of the destination records are at
458 : *_dst_rec_head_idx / *_dst_rec_tail_idx. All transactions on this
459 : list will have transaction id dst_xid and vice versa. That is, this
460 : is the record list the last published transaction or txn_idx's
461 : in-prep parent transaction.
462 :
463 : On exit, the head/tail of the updated records is at
464 : *_dst_rec_head_idx / *_dst_rec_tail_idx. As before, all transactions
465 : on this list will have transaction id dst_xid and vice versa.
466 : Transaction txn_idx will have an _empty_ record list.
467 :
468 : Updates in the transaction txn_idx are processed from oldest to
469 : youngest. If an update erases an existing record in dest, the record
470 : to erase is removed from the destination records without perturbing
471 : the order of remaining destination records. If an update is to
472 : update an existing record, the destination record value is updated
473 : and the order of the destination records is unchanged. If an update
474 : is to create a new record, the record is appended to the list of
475 : existing values as youngest without changing the order of existing
476 : values. If an update erases a record in an in-prep parent, the
477 : erasure will be moved into the parent as the youngest without
478 : changing the order of existing values. */
479 :
480 : static void
481 : fd_funk_txn_update( fd_funk_t * funk,
482 : uint * _dst_rec_head_idx, /* Pointer to the dst list head */
483 : uint * _dst_rec_tail_idx, /* Pointer to the dst list tail */
484 : ulong dst_txn_idx, /* Transaction index of the merge destination */
485 : fd_funk_txn_xid_t const * dst_xid, /* dst xid */
486 215984 : ulong txn_idx ) { /* Transaction index of the records to merge */
487 215984 : fd_wksp_t * wksp = funk->wksp;
488 215984 : fd_alloc_t * alloc = funk->alloc;
489 215984 : fd_funk_rec_map_t * rec_map = funk->rec_map;
490 215984 : fd_funk_rec_pool_t * rec_pool = funk->rec_pool;
491 215984 : fd_funk_txn_pool_t * txn_pool = funk->txn_pool;
492 :
493 215984 : int critical = (_dst_rec_head_idx == &funk->shmem->rec_head_idx);
494 215984 : if (critical) {
495 : /* If the root transaction is being updated, we need to mark
496 : the beginning of a critical section becuase fd_funk_purify can't fix it */
497 206552 : fd_begin_crit(funk);
498 206552 : }
499 :
500 215984 : fd_funk_txn_t * txn = &txn_pool->ele[ txn_idx ];
501 215984 : uint rec_idx = txn->rec_head_idx;
502 2205954 : while( !fd_funk_rec_idx_is_null( rec_idx ) ) {
503 1989970 : fd_funk_rec_t * rec = &rec_pool->ele[ rec_idx ];
504 1989970 : uint next_rec_idx = rec->next_idx;
505 :
506 : /* See if (dst_xid,key) already exists. */
507 1989970 : fd_funk_xid_key_pair_t pair[1];
508 1989970 : fd_funk_xid_key_pair_init( pair, dst_xid, rec->pair.key );
509 1989970 : for(;;) {
510 1989970 : fd_funk_rec_map_query_t rec_query[1];
511 1989970 : int err = fd_funk_rec_map_remove( rec_map, pair, NULL, rec_query, FD_MAP_FLAG_BLOCKING );
512 1989970 : if( FD_UNLIKELY( err == FD_MAP_ERR_AGAIN ) ) continue;
513 1989970 : if( err == FD_MAP_ERR_KEY ) break;
514 170229 : if( FD_UNLIKELY( err != FD_MAP_SUCCESS ) ) FD_LOG_CRIT(( "map corruption" ));
515 :
516 : /* Remove from the transaction */
517 170229 : fd_funk_rec_t * rec2 = fd_funk_rec_map_query_ele( rec_query );
518 170229 : uint prev_idx = rec2->prev_idx;
519 170229 : uint next_idx = rec2->next_idx;
520 170229 : if( fd_funk_rec_idx_is_null( prev_idx ) ) {
521 2454 : *_dst_rec_head_idx = next_idx;
522 167775 : } else {
523 167775 : rec_pool->ele[ prev_idx ].next_idx = next_idx;
524 167775 : }
525 170229 : if( fd_funk_rec_idx_is_null( next_idx ) ) {
526 411 : *_dst_rec_tail_idx = prev_idx;
527 169818 : } else {
528 169818 : rec_pool->ele[ next_idx ].prev_idx = prev_idx;
529 169818 : }
530 : /* Clean up value */
531 170229 : fd_funk_val_flush( rec2, alloc, wksp );
532 170229 : rec2->txn_cidx = fd_funk_txn_cidx( FD_FUNK_TXN_IDX_NULL );
533 170229 : fd_funk_rec_pool_release( rec_pool, rec2, 1 );
534 170229 : break;
535 170229 : }
536 :
537 : /* Add the new record to the transaction. We can update the xid in
538 : place because it is not used for hashing the element. We have
539 : to preserve the original element to preserve the
540 : newest-to-oldest ordering in the hash
541 : chain. fd_funk_rec_query_global relies on this subtle
542 : property. */
543 :
544 1989970 : rec->pair.xid[0] = *dst_xid;
545 1989970 : rec->txn_cidx = fd_funk_txn_cidx( dst_txn_idx );
546 :
547 1989970 : if( fd_funk_rec_idx_is_null( *_dst_rec_head_idx ) ) {
548 4647 : *_dst_rec_head_idx = rec_idx;
549 4647 : rec->prev_idx = FD_FUNK_REC_IDX_NULL;
550 1985323 : } else {
551 1985323 : rec_pool->ele[ *_dst_rec_tail_idx ].next_idx = rec_idx;
552 1985323 : rec->prev_idx = *_dst_rec_tail_idx;
553 1985323 : }
554 1989970 : *_dst_rec_tail_idx = rec_idx;
555 1989970 : rec->next_idx = FD_FUNK_REC_IDX_NULL;
556 :
557 1989970 : rec_idx = next_rec_idx;
558 1989970 : }
559 :
560 215984 : txn_pool->ele[ txn_idx ].rec_head_idx = FD_FUNK_REC_IDX_NULL;
561 215984 : txn_pool->ele[ txn_idx ].rec_tail_idx = FD_FUNK_REC_IDX_NULL;
562 :
563 215984 : if (critical) {
564 206552 : fd_end_crit(funk);
565 206552 : }
566 215984 : }
567 :
568 : /* fd_funk_txn_publish_funk_child publishes a transaction that is known
569 : to be a child of funk. Callers have already validated our input
570 : arguments. Returns FD_FUNK_SUCCESS on success and an FD_FUNK_ERR_*
571 : code on failure. (There are currently no failure cases but the
572 : plumbing is there if value handling requires it at some point.) */
573 :
574 : static int
575 : fd_funk_txn_publish_funk_child( fd_funk_t * const funk,
576 : ulong const tag,
577 203984 : ulong const txn_idx ) {
578 :
579 : /* Apply the updates in txn to the last published transactions */
580 :
581 203984 : fd_funk_txn_update( funk, &funk->shmem->rec_head_idx, &funk->shmem->rec_tail_idx, FD_FUNK_TXN_IDX_NULL, fd_funk_root( funk ), txn_idx );
582 :
583 : /* Cancel all competing transaction histories */
584 :
585 203984 : ulong oldest_idx = fd_funk_txn_oldest_sibling( funk, txn_idx );
586 203984 : fd_funk_txn_cancel_sibling_list( funk, tag, oldest_idx, txn_idx );
587 :
588 : /* Make all the children children of funk */
589 :
590 203984 : fd_funk_txn_t * txn = fd_funk_txn_pool_ele( funk->txn_pool, txn_idx );
591 203984 : ulong child_head_idx = fd_funk_txn_idx( txn->child_head_cidx );
592 203984 : ulong child_tail_idx = fd_funk_txn_idx( txn->child_tail_cidx );
593 :
594 203984 : ulong child_idx = child_head_idx;
595 386235 : while( FD_UNLIKELY( !fd_funk_txn_idx_is_null( child_idx ) ) ) { /* opt for incr pub */
596 182251 : fd_funk_txn_t * child_txn = fd_funk_txn_pool_ele( funk->txn_pool, child_idx );
597 182251 : child_txn->tag = tag;
598 182251 : child_txn->parent_cidx = fd_funk_txn_cidx( FD_FUNK_TXN_IDX_NULL );
599 182251 : child_idx = fd_funk_txn_idx( child_txn->sibling_next_cidx );
600 182251 : }
601 :
602 203984 : funk->shmem->child_head_cidx = fd_funk_txn_cidx( child_head_idx );
603 203984 : funk->shmem->child_tail_cidx = fd_funk_txn_cidx( child_tail_idx );
604 :
605 203984 : fd_funk_txn_xid_copy( funk->shmem->last_publish, fd_funk_txn_xid( txn ) );
606 :
607 : /* Remove the mapping */
608 :
609 203984 : fd_funk_txn_map_query_t query[1];
610 203984 : if( fd_funk_txn_map_remove( funk->txn_map, funk->shmem->last_publish, NULL, query, FD_MAP_FLAG_BLOCKING ) == FD_MAP_SUCCESS ) {
611 203984 : fd_funk_txn_pool_release( funk->txn_pool, txn, 1 );
612 203984 : }
613 :
614 203984 : return FD_FUNK_SUCCESS;
615 203984 : }
616 :
617 : ulong
618 : fd_funk_txn_publish( fd_funk_t * funk,
619 : fd_funk_txn_t * txn,
620 147634 : int verbose ) {
621 :
622 : #ifdef FD_FUNK_HANDHOLDING
623 : if( FD_UNLIKELY( !funk ) ) {
624 : if( FD_UNLIKELY( verbose ) ) FD_LOG_WARNING(( "NULL funk" ));
625 : return 0UL;
626 : }
627 : if( FD_UNLIKELY( !fd_funk_txn_valid( funk, txn ) ) ) {
628 : if( FD_UNLIKELY( verbose ) ) FD_LOG_WARNING(( "bad txn" ));
629 : return 0UL;
630 : }
631 : #else
632 147634 : (void)verbose;
633 147634 : #endif
634 :
635 147634 : ulong txn_idx = (ulong)(txn - funk->txn_pool->ele);
636 :
637 147634 : ulong tag = funk->shmem->cycle_tag++;
638 :
639 147634 : ulong publish_stack_idx = FD_FUNK_TXN_IDX_NULL;
640 :
641 203984 : for(;;) {
642 203984 : fd_funk_txn_t * txn2 = &funk->txn_pool->ele[ txn_idx ];
643 203984 : txn2->tag = tag;
644 :
645 : /* At this point, txn_idx is a transaction that needs to be
646 : published and has been tagged. If txn is a child of funk, we are
647 : ready to publish txn and everything on the publish stack. */
648 :
649 203984 : ulong parent_idx = fd_funk_txn_idx( txn2->parent_cidx );
650 203984 : if( FD_LIKELY( fd_funk_txn_idx_is_null( parent_idx ) ) ) break; /* opt for incr pub */
651 :
652 : /* txn_idx has a parent. Validate and tag it. Push txn to the
653 : publish stack and recurse into the parent. */
654 :
655 56350 : txn2->stack_cidx = fd_funk_txn_cidx( publish_stack_idx );
656 56350 : publish_stack_idx = txn_idx;
657 :
658 56350 : txn_idx = parent_idx;
659 56350 : }
660 :
661 147634 : ulong publish_cnt = 0UL;
662 :
663 203984 : for(;;) {
664 :
665 : /* At this point, all the transactions we need to publish are
666 : tagged, txn is the next up publish funk and publish_stack has the
667 : transactions to follow in order by pop. We use a new tag for
668 : each publish as txn and its siblings we potentially visited in a
669 : previous iteration of this loop. */
670 :
671 203984 : if( FD_UNLIKELY( fd_funk_txn_publish_funk_child( funk, funk->shmem->cycle_tag++, txn_idx ) ) ) break;
672 203984 : publish_cnt++;
673 :
674 203984 : txn_idx = publish_stack_idx;
675 203984 : if( FD_LIKELY( fd_funk_txn_idx_is_null( txn_idx ) ) ) break; /* opt for incr pub */
676 56350 : publish_stack_idx = fd_funk_txn_idx( funk->txn_pool->ele[ txn_idx ].stack_cidx );
677 56350 : }
678 :
679 147634 : return publish_cnt;
680 147634 : }
681 :
682 : int
683 : fd_funk_txn_publish_into_parent( fd_funk_t * funk,
684 : fd_funk_txn_t * txn,
685 12000 : int verbose ) {
686 : #ifdef FD_FUNK_HANDHOLDING
687 : if( FD_UNLIKELY( !funk ) ) {
688 : if( FD_UNLIKELY( verbose ) ) FD_LOG_WARNING(( "NULL funk" ));
689 : return FD_FUNK_ERR_INVAL;
690 : }
691 : if( FD_UNLIKELY( !fd_funk_txn_valid( funk, txn ) ) ) {
692 : if( FD_UNLIKELY( verbose ) ) FD_LOG_WARNING(( "bad txn" ));
693 : return 0UL;
694 : }
695 : #else
696 12000 : (void)verbose;
697 12000 : #endif
698 :
699 12000 : fd_funk_txn_map_t * txn_map = funk->txn_map;
700 12000 : fd_funk_txn_pool_t * txn_pool = funk->txn_pool;
701 12000 : ulong txn_idx = (ulong)(txn - txn_pool->ele);
702 :
703 12000 : ulong oldest_idx = fd_funk_txn_oldest_sibling( funk, txn_idx );
704 12000 : fd_funk_txn_cancel_sibling_list( funk, funk->shmem->cycle_tag++, oldest_idx, txn_idx );
705 :
706 12000 : ulong parent_idx = fd_funk_txn_idx( txn->parent_cidx );
707 12000 : if( fd_funk_txn_idx_is_null( parent_idx ) ) {
708 : /* Publish to root */
709 2568 : fd_funk_txn_update( funk, &funk->shmem->rec_head_idx, &funk->shmem->rec_tail_idx, FD_FUNK_TXN_IDX_NULL, fd_funk_root( funk ), txn_idx );
710 : /* Inherit the children */
711 2568 : funk->shmem->child_head_cidx = txn->child_head_cidx;
712 2568 : funk->shmem->child_tail_cidx = txn->child_tail_cidx;
713 9432 : } else {
714 9432 : fd_funk_txn_t * parent_txn = &txn_pool->ele[ parent_idx ];
715 9432 : fd_funk_txn_update( funk, &parent_txn->rec_head_idx, &parent_txn->rec_tail_idx, parent_idx, &parent_txn->xid, txn_idx );
716 : /* Inherit the children */
717 9432 : parent_txn->child_head_cidx = txn->child_head_cidx;
718 9432 : parent_txn->child_tail_cidx = txn->child_tail_cidx;
719 9432 : }
720 :
721 : /* Adjust the parent pointers of the children to point to their grandparent */
722 12000 : ulong child_idx = fd_funk_txn_idx( txn->child_head_cidx );
723 21123 : while( FD_UNLIKELY( !fd_funk_txn_idx_is_null( child_idx ) ) ) {
724 9123 : txn_pool->ele[ child_idx ].parent_cidx = fd_funk_txn_cidx( parent_idx );
725 9123 : child_idx = fd_funk_txn_idx( txn_pool->ele[ child_idx ].sibling_next_cidx );
726 9123 : }
727 :
728 12000 : fd_funk_txn_map_query_t query[1];
729 12000 : if( fd_funk_txn_map_remove( txn_map, fd_funk_txn_xid( txn ), NULL, query, FD_MAP_FLAG_BLOCKING ) == FD_MAP_SUCCESS ) {
730 12000 : fd_funk_txn_pool_release( txn_pool, txn, 1 );
731 12000 : }
732 :
733 12000 : return FD_FUNK_SUCCESS;
734 12000 : }
735 :
736 : /* Return the first record in a transaction. Returns NULL if the
737 : transaction has no records yet. */
738 :
739 : fd_funk_rec_t const *
740 : fd_funk_txn_first_rec( fd_funk_t * funk,
741 47622933 : fd_funk_txn_t const * txn ) {
742 47622933 : uint rec_idx;
743 47622933 : if( FD_UNLIKELY( NULL == txn ))
744 3247731 : rec_idx = funk->shmem->rec_head_idx;
745 44375202 : else
746 44375202 : rec_idx = txn->rec_head_idx;
747 47622933 : if( fd_funk_rec_idx_is_null( rec_idx ) ) return NULL;
748 31761792 : return funk->rec_pool->ele + rec_idx;
749 47622933 : }
750 :
751 : fd_funk_rec_t const *
752 : fd_funk_txn_last_rec( fd_funk_t * funk,
753 0 : fd_funk_txn_t const * txn ) {
754 0 : uint rec_idx;
755 0 : if( FD_UNLIKELY( NULL == txn ))
756 0 : rec_idx = funk->shmem->rec_tail_idx;
757 0 : else
758 0 : rec_idx = txn->rec_tail_idx;
759 0 : if( fd_funk_rec_idx_is_null( rec_idx ) ) return NULL;
760 0 : return funk->rec_pool->ele + rec_idx;
761 0 : }
762 :
763 : /* Return the next record in a transaction. Returns NULL if the
764 : transaction has no more records. */
765 :
766 : fd_funk_rec_t const *
767 : fd_funk_txn_next_rec( fd_funk_t * funk,
768 656335248 : fd_funk_rec_t const * rec ) {
769 656335248 : uint rec_idx = rec->next_idx;
770 656335248 : if( fd_funk_rec_idx_is_null( rec_idx ) ) return NULL;
771 594079938 : return funk->rec_pool->ele + rec_idx;
772 656335248 : }
773 :
774 : fd_funk_rec_t const *
775 : fd_funk_txn_prev_rec( fd_funk_t * funk,
776 318768039 : fd_funk_rec_t const * rec ) {
777 318768039 : uint rec_idx = rec->prev_idx;
778 318768039 : if( fd_funk_rec_idx_is_null( rec_idx ) ) return NULL;
779 288274521 : return funk->rec_pool->ele + rec_idx;
780 318768039 : }
781 :
782 : fd_funk_txn_xid_t
783 18918876 : fd_funk_generate_xid(void) {
784 18918876 : fd_funk_txn_xid_t xid;
785 18918876 : static FD_TL ulong seq = 0;
786 18918876 : xid.ul[0] =
787 18918876 : (fd_log_cpu_id() + 1U)*3138831853UL +
788 18918876 : (fd_log_thread_id() + 1U)*9180195821UL +
789 18918876 : (++seq)*6208101967UL;
790 18918876 : xid.ul[1] = ((ulong)fd_tickcount())*2810745731UL;
791 18918876 : return xid;
792 18918876 : }
793 :
794 : static void
795 4362470163 : fd_funk_txn_all_iter_skip_nulls( fd_funk_txn_all_iter_t * iter ) {
796 4362470163 : if( iter->chain_idx == iter->chain_cnt ) return;
797 7157021812 : while( fd_funk_txn_map_iter_done( iter->txn_map_iter ) ) {
798 3000257613 : if( ++(iter->chain_idx) == iter->chain_cnt ) break;
799 2794551649 : iter->txn_map_iter = fd_funk_txn_map_iter( &iter->txn_map, iter->chain_idx );
800 2794551649 : }
801 4362470163 : }
802 :
803 : void
804 : fd_funk_txn_all_iter_new( fd_funk_t * funk,
805 205705964 : fd_funk_txn_all_iter_t * iter ) {
806 205705964 : iter->txn_map = *funk->txn_map;
807 205705964 : iter->chain_cnt = fd_funk_txn_map_chain_cnt( funk->txn_map );
808 205705964 : iter->chain_idx = 0;
809 205705964 : iter->txn_map_iter = fd_funk_txn_map_iter( funk->txn_map, 0 );
810 205705964 : fd_funk_txn_all_iter_skip_nulls( iter );
811 205705964 : }
812 :
813 : int
814 4362470163 : fd_funk_txn_all_iter_done( fd_funk_txn_all_iter_t * iter ) {
815 4362470163 : return ( iter->chain_idx == iter->chain_cnt );
816 4362470163 : }
817 :
818 : void
819 4156764199 : fd_funk_txn_all_iter_next( fd_funk_txn_all_iter_t * iter ) {
820 4156764199 : iter->txn_map_iter = fd_funk_txn_map_iter_next( iter->txn_map_iter );
821 4156764199 : fd_funk_txn_all_iter_skip_nulls( iter );
822 4156764199 : }
823 :
824 : fd_funk_txn_t const *
825 1846548 : fd_funk_txn_all_iter_ele_const( fd_funk_txn_all_iter_t * iter ) {
826 1846548 : return fd_funk_txn_map_iter_ele_const( iter->txn_map_iter );
827 1846548 : }
828 :
829 : fd_funk_txn_t *
830 4154917045 : fd_funk_txn_all_iter_ele( fd_funk_txn_all_iter_t * iter ) {
831 4154917045 : return fd_funk_txn_map_iter_ele( iter->txn_map_iter );
832 4154917045 : }
833 :
834 : int
835 12 : fd_funk_txn_verify( fd_funk_t * funk ) {
836 12 : fd_funk_txn_map_t * txn_map = funk->txn_map;
837 12 : fd_funk_txn_pool_t * txn_pool = funk->txn_pool;
838 12 : ulong txn_max = fd_funk_txn_pool_ele_max( txn_pool );
839 :
840 12 : ulong funk_child_head_idx = fd_funk_txn_idx( funk->shmem->child_head_cidx ); /* Previously verified */
841 12 : ulong funk_child_tail_idx = fd_funk_txn_idx( funk->shmem->child_tail_cidx ); /* Previously verified */
842 :
843 12 : fd_funk_txn_xid_t const * last_publish = funk->shmem->last_publish; /* Previously verified */
844 :
845 24 : # define TEST(c) do { \
846 24 : if( FD_UNLIKELY( !(c) ) ) { FD_LOG_WARNING(( "FAIL: %s", #c )); return FD_FUNK_ERR_INVAL; } \
847 24 : } while(0)
848 :
849 12 : # define IS_VALID( idx ) ( (idx==FD_FUNK_TXN_IDX_NULL) || \
850 12 : ((idx<txn_max) && (!fd_funk_txn_xid_eq( fd_funk_txn_xid( &txn_pool->ele[idx] ), last_publish ))) )
851 :
852 12 : TEST( !fd_funk_txn_map_verify( txn_map ) );
853 12 : TEST( !fd_funk_txn_pool_verify( txn_pool ) );
854 :
855 : /* Tag all transactions as not visited yet */
856 :
857 1572876 : for( ulong txn_idx=0UL; txn_idx<txn_max; txn_idx++ ) txn_pool->ele[ txn_idx ].tag = 0UL;
858 :
859 : /* Visit all transactions in preparation, traversing from oldest to
860 : youngest. */
861 :
862 12 : do {
863 :
864 : /* Push all children of funk to the stack */
865 :
866 12 : ulong stack_idx = FD_FUNK_TXN_IDX_NULL;
867 12 : ulong child_idx = funk_child_head_idx;
868 12 : while( !fd_funk_txn_idx_is_null( child_idx ) ) {
869 :
870 : /* Make sure valid idx, not tagged (detects cycles) and child
871 : knows it is a child of funk. Then tag as visited / in-prep,
872 : push to stack and update prep_cnt */
873 :
874 0 : TEST( IS_VALID( child_idx ) );
875 0 : TEST( !txn_pool->ele[ child_idx ].tag );
876 0 : TEST( fd_funk_txn_idx_is_null( fd_funk_txn_idx( txn_pool->ele[ child_idx ].parent_cidx ) ) );
877 0 : txn_pool->ele[ child_idx ].tag = 1UL;
878 0 : txn_pool->ele[ child_idx ].stack_cidx = fd_funk_txn_cidx( stack_idx );
879 0 : stack_idx = child_idx;
880 :
881 0 : ulong next_idx = fd_funk_txn_idx( txn_pool->ele[ child_idx ].sibling_next_cidx );
882 0 : if( !fd_funk_txn_idx_is_null( next_idx ) ) TEST( fd_funk_txn_idx( txn_pool->ele[ next_idx ].sibling_prev_cidx )==child_idx );
883 0 : child_idx = next_idx;
884 0 : }
885 :
886 12 : while( !fd_funk_txn_idx_is_null( stack_idx ) ) {
887 :
888 : /* Pop the next transaction to traverse */
889 :
890 0 : ulong txn_idx = stack_idx;
891 0 : stack_idx = fd_funk_txn_idx( txn_pool->ele[ txn_idx ].stack_cidx );
892 :
893 : /* Push all children of txn to the stack */
894 :
895 0 : ulong child_idx = fd_funk_txn_idx( txn_pool->ele[ txn_idx ].child_head_cidx );
896 0 : while( !fd_funk_txn_idx_is_null( child_idx ) ) {
897 :
898 : /* Make sure valid idx, not tagged (detects cycles) and child
899 : knows it is a child of txn_idx. Then tag as visited /
900 : in-prep, push to stack and update prep_cnt */
901 :
902 0 : TEST( IS_VALID( child_idx ) );
903 0 : TEST( !txn_pool->ele[ child_idx ].tag );
904 0 : TEST( fd_funk_txn_idx( txn_pool->ele[ child_idx ].parent_cidx )==txn_idx );
905 0 : txn_pool->ele[ child_idx ].tag = 1UL;
906 0 : txn_pool->ele[ child_idx ].stack_cidx = fd_funk_txn_cidx( stack_idx );
907 0 : stack_idx = child_idx;
908 :
909 0 : ulong next_idx = fd_funk_txn_idx( txn_pool->ele[ child_idx ].sibling_next_cidx );
910 0 : if( !fd_funk_txn_idx_is_null( next_idx ) ) TEST( fd_funk_txn_idx( txn_pool->ele[ next_idx ].sibling_prev_cidx )==child_idx );
911 0 : child_idx = next_idx;
912 0 : }
913 0 : }
914 :
915 12 : } while(0);
916 :
917 : /* Do it again with a youngest to oldest traversal to test reverse
918 : link integrity */
919 :
920 12 : do {
921 :
922 : /* Push all children of funk to the stack */
923 :
924 12 : ulong stack_idx = FD_FUNK_TXN_IDX_NULL;
925 12 : ulong child_idx = funk_child_tail_idx;
926 12 : while( !fd_funk_txn_idx_is_null( child_idx ) ) {
927 :
928 : /* Make sure valid idx, tagged as visited above (detects cycles)
929 : and child knows it is a child of funk. Then tag as visited /
930 : in-prep, push to stack and update prep_cnt */
931 :
932 0 : TEST( IS_VALID( child_idx ) );
933 0 : TEST( txn_pool->ele[ child_idx ].tag==1UL );
934 0 : TEST( fd_funk_txn_idx_is_null( fd_funk_txn_idx( txn_pool->ele[ child_idx ].parent_cidx ) ) );
935 0 : txn_pool->ele[ child_idx ].tag = 2UL;
936 0 : txn_pool->ele[ child_idx ].stack_cidx = fd_funk_txn_cidx( stack_idx );
937 0 : stack_idx = child_idx;
938 :
939 0 : ulong prev_idx = fd_funk_txn_idx( txn_pool->ele[ child_idx ].sibling_prev_cidx );
940 0 : if( !fd_funk_txn_idx_is_null( prev_idx ) ) TEST( fd_funk_txn_idx( txn_pool->ele[ prev_idx ].sibling_next_cidx )==child_idx );
941 0 : child_idx = prev_idx;
942 0 : }
943 :
944 12 : while( !fd_funk_txn_idx_is_null( stack_idx ) ) {
945 :
946 : /* Pop the next transaction to traverse */
947 :
948 0 : ulong txn_idx = stack_idx;
949 0 : stack_idx = fd_funk_txn_idx( txn_pool->ele[ txn_idx ].stack_cidx );
950 :
951 : /* Push all children of txn to the stack */
952 :
953 0 : ulong child_idx = fd_funk_txn_idx( txn_pool->ele[ txn_idx ].child_tail_cidx );
954 0 : while( !fd_funk_txn_idx_is_null( child_idx ) ) {
955 :
956 : /* Make sure valid idx, tagged as visited above (detects cycles)
957 : and child knows it is a child of txn_idx. Then, tag as
958 : visited / in-prep, push to stack and update prep_cnt */
959 :
960 0 : TEST( IS_VALID( child_idx ) );
961 0 : TEST( txn_pool->ele[ child_idx ].tag==1UL );
962 0 : TEST( fd_funk_txn_idx( txn_pool->ele[ child_idx ].parent_cidx )==txn_idx );
963 0 : txn_pool->ele[ child_idx ].tag = 2UL;
964 0 : txn_pool->ele[ child_idx ].stack_cidx = fd_funk_txn_cidx( stack_idx );
965 0 : stack_idx = child_idx;
966 :
967 0 : ulong prev_idx = fd_funk_txn_idx( txn_pool->ele[ child_idx ].sibling_prev_cidx );
968 0 : if( !fd_funk_txn_idx_is_null( prev_idx ) ) TEST( fd_funk_txn_idx( txn_pool->ele[ prev_idx ].sibling_next_cidx )==child_idx );
969 0 : child_idx = prev_idx;
970 0 : }
971 0 : }
972 12 : } while(0);
973 :
974 12 : # undef IS_VALID
975 12 : # undef TEST
976 :
977 12 : return FD_FUNK_SUCCESS;
978 12 : }
979 :
980 : int
981 0 : fd_funk_txn_valid( fd_funk_t const * funk, fd_funk_txn_t const * txn ) {
982 0 : ulong txn_idx = (ulong)(txn - funk->txn_pool->ele);
983 0 : ulong txn_max = fd_funk_txn_pool_ele_max( funk->txn_pool );
984 0 : if( txn_idx>=txn_max || txn != txn_idx + funk->txn_pool->ele ) return 0;
985 0 : fd_funk_txn_map_query_t query[1];
986 0 : if( FD_UNLIKELY( fd_funk_txn_map_query_try( funk->txn_map, &txn->xid, NULL, query, 0 ) ) ) return 0;
987 0 : if( fd_funk_txn_map_query_ele( query ) != txn ) return 0;
988 0 : return 1;
989 0 : }
|
