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 5260749 : #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 387426621 : #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 164936303 : #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 445433 : parent_idx = FD_FUNK_TXN_IDX_NULL;
90 :
91 445433 : _child_head_cidx = &funk->shmem->child_head_cidx;
92 445433 : _child_tail_cidx = &funk->shmem->child_tail_cidx;
93 :
94 610219 : } else {
95 :
96 610219 : parent_idx = (ulong)(parent - funk->txn_pool->ele);
97 :
98 610219 : _child_head_cidx = &parent->child_head_cidx;
99 610219 : _child_tail_cidx = &parent->child_tail_cidx;
100 :
101 610219 : }
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 537280 : 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 837980 : 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 837980 : fd_wksp_t * wksp = funk->wksp;
159 837980 : fd_alloc_t * alloc = funk->alloc;
160 837980 : fd_funk_rec_map_t * rec_map = funk->rec_map;
161 837980 : fd_funk_rec_pool_t * rec_pool = funk->rec_pool;
162 837980 : ulong rec_max = fd_funk_rec_pool_ele_max( rec_pool );
163 837980 : fd_funk_txn_map_t * txn_map = funk->txn_map;
164 837980 : fd_funk_txn_pool_t * txn_pool = funk->txn_pool;
165 :
166 837980 : fd_funk_txn_t * txn = &txn_pool->ele[ txn_idx ];
167 837980 : uint rec_idx = txn->rec_head_idx;
168 21420329 : while( !fd_funk_rec_idx_is_null( rec_idx ) ) {
169 :
170 20582349 : if( FD_UNLIKELY( rec_idx>=rec_max ) ) FD_LOG_CRIT(( "memory corruption detected (bad idx)" ));
171 20582349 : 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 20582349 : fd_funk_rec_t * rec = &rec_pool->ele[ rec_idx ];
175 20582349 : uint next_idx = rec->next_idx;
176 20582349 : rec->txn_cidx = fd_funk_txn_cidx( FD_FUNK_TXN_IDX_NULL );
177 :
178 20582349 : for(;;) {
179 20582349 : fd_funk_rec_map_query_t rec_query[1];
180 20582349 : int err = fd_funk_rec_map_remove( rec_map, fd_funk_rec_pair( rec ), NULL, rec_query, FD_MAP_FLAG_BLOCKING );
181 20582349 : if( FD_UNLIKELY( err == FD_MAP_ERR_AGAIN ) ) continue;
182 20582349 : if( err == FD_MAP_ERR_KEY ) break;
183 20582349 : if( FD_UNLIKELY( err != FD_MAP_SUCCESS ) ) FD_LOG_CRIT(( "map corruption" ));
184 20582349 : if( rec != fd_funk_rec_map_query_ele( rec_query ) ) break;
185 20582349 : fd_funk_val_flush( rec, alloc, wksp );
186 20582349 : fd_funk_rec_pool_release( rec_pool, rec, 1 );
187 20582349 : break;
188 20582349 : }
189 :
190 20582349 : rec_idx = next_idx;
191 20582349 : }
192 :
193 : /* Leave the family */
194 :
195 837980 : ulong sibling_prev_idx = fd_funk_txn_idx( txn->sibling_prev_cidx );
196 837980 : ulong sibling_next_idx = fd_funk_txn_idx( txn->sibling_next_cidx );
197 :
198 : /* TODO: Consider branchless impl */
199 :
200 837980 : if( FD_LIKELY( fd_funk_txn_idx_is_null( sibling_prev_idx ) ) ) { /* opt for non-compete */
201 407293 : ulong parent_idx = fd_funk_txn_idx( txn_pool->ele[ txn_idx ].parent_cidx );
202 407293 : if( FD_LIKELY( fd_funk_txn_idx_is_null( parent_idx ) ) ) { /* No older sib and is a funk child, opt for incr pub */
203 136757 : funk->shmem->child_head_cidx = fd_funk_txn_cidx( sibling_next_idx );
204 270536 : } else { /* No older sib and has parent */
205 270536 : txn_pool->ele[ parent_idx ].child_head_cidx = fd_funk_txn_cidx( sibling_next_idx );
206 270536 : }
207 430687 : } else { /* Has older sib */
208 430687 : txn_pool->ele[ sibling_prev_idx ].sibling_next_cidx = fd_funk_txn_cidx( sibling_next_idx );
209 430687 : }
210 :
211 837980 : if( FD_LIKELY( fd_funk_txn_idx_is_null( sibling_next_idx ) ) ) { /* opt for non-compete */
212 660528 : ulong parent_idx = fd_funk_txn_idx( txn_pool->ele[ txn_idx ].parent_cidx );
213 660528 : if( FD_LIKELY( fd_funk_txn_idx_is_null( parent_idx ) ) ) { /* No younger sib and is a funk child, opt for incr pub */
214 262877 : funk->shmem->child_tail_cidx = fd_funk_txn_cidx( sibling_prev_idx );
215 397651 : } else { /* No younger sib and has parent */
216 397651 : txn_pool->ele[ parent_idx ].child_tail_cidx = fd_funk_txn_cidx( sibling_prev_idx );
217 397651 : }
218 660528 : } else { /* Has younger sib */
219 177452 : txn_pool->ele[ sibling_next_idx ].sibling_prev_cidx = fd_funk_txn_cidx( sibling_prev_idx );
220 177452 : }
221 :
222 837980 : fd_funk_txn_map_query_t query[1];
223 837980 : if( fd_funk_txn_map_remove( txn_map, fd_funk_txn_xid( txn ), NULL, query, FD_MAP_FLAG_BLOCKING ) == FD_MAP_SUCCESS ) {
224 837980 : fd_funk_txn_pool_release( txn_pool, txn, 1 );
225 837980 : }
226 837980 : }
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 475243 : ulong txn_idx ) {
237 475243 : ulong cancel_cnt = 0UL;
238 :
239 475243 : ulong parent_stack_idx = FD_FUNK_TXN_IDX_NULL;
240 :
241 1200717 : for(;;) {
242 :
243 1200717 : fd_funk_txn_t * txn = &funk->txn_pool->ele[ txn_idx ];
244 1200717 : txn->tag = tag;
245 :
246 1200717 : ulong youngest_idx = fd_funk_txn_idx( txn->child_tail_cidx );
247 1200717 : if( FD_LIKELY( fd_funk_txn_idx_is_null( youngest_idx ) ) ) { /* txn is is childless, opt for incr pub */
248 :
249 837980 : fd_funk_txn_cancel_childless( funk, txn_idx ); /* If this can fail, return cancel_cnt here on fail */
250 837980 : cancel_cnt++;
251 :
252 837980 : txn_idx = parent_stack_idx; /* Pop the parent stack */
253 837980 : if( FD_LIKELY( fd_funk_txn_idx_is_null( txn_idx ) ) ) break; /* If stack is empty, we are done, opt for incr pub */
254 362737 : parent_stack_idx = fd_funk_txn_idx( funk->txn_pool->ele[ txn_idx ].stack_cidx );
255 362737 : continue;
256 837980 : }
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 362737 : txn->stack_cidx = fd_funk_txn_cidx( parent_stack_idx );
263 362737 : parent_stack_idx = txn_idx;
264 :
265 362737 : txn_idx = youngest_idx;
266 362737 : }
267 :
268 475243 : return cancel_cnt;
269 475243 : }
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 215977 : ulong txn_idx ) {
300 215977 : ulong parent_idx = fd_funk_txn_idx( funk->txn_pool->ele[ txn_idx ].parent_cidx );
301 :
302 215977 : 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 215977 : }
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 215977 : ulong skip_idx ) {
321 :
322 215977 : 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 544070 : 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 544070 : fd_funk_txn_t * sibling = &funk->txn_pool->ele[ sibling_idx ];
334 544070 : sibling->tag = tag;
335 :
336 544070 : if( FD_UNLIKELY( sibling_idx!=skip_idx ) ) { /* Not skip_idx so push onto the cancel stack, opt for non-compete */
337 328093 : sibling->stack_cidx = fd_funk_txn_cidx( cancel_stack_idx );
338 328093 : cancel_stack_idx = sibling_idx;
339 328093 : }
340 :
341 544070 : ulong younger_idx = fd_funk_txn_idx( sibling->sibling_next_cidx );
342 544070 : if( FD_LIKELY( fd_funk_txn_idx_is_null( younger_idx ) ) ) break; /* opt for non-compete */
343 328093 : sibling_idx = younger_idx;
344 :
345 328093 : }
346 :
347 : /* Cancel all transactions and their descendants on the cancel stack */
348 :
349 215977 : ulong cancel_cnt = 0UL;
350 :
351 544070 : while( !fd_funk_txn_idx_is_null( cancel_stack_idx ) ) { /* TODO: peel first iter to make more predictable? */
352 328093 : ulong sibling_idx = cancel_stack_idx;
353 328093 : cancel_stack_idx = fd_funk_txn_idx( funk->txn_pool->ele[ sibling_idx ].stack_cidx );
354 328093 : cancel_cnt += fd_funk_txn_cancel_family( funk, tag, sibling_idx );
355 328093 : }
356 :
357 215977 : return cancel_cnt;
358 215977 : }
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 : /* Cancel all outstanding transactions */
419 :
420 : ulong
421 : fd_funk_txn_cancel_all( fd_funk_t * funk,
422 0 : int verbose ) {
423 0 : return fd_funk_txn_cancel_children( funk, NULL, verbose );
424 0 : }
425 :
426 : /* fd_funk_txn_update applies the record updates in transaction txn_idx
427 : to another transaction or the parent transaction. Callers have
428 : already validated our input arguments.
429 :
430 : On entry, the head/tail of the destination records are at
431 : *_dst_rec_head_idx / *_dst_rec_tail_idx. All transactions on this
432 : list will have transaction id dst_xid and vice versa. That is, this
433 : is the record list the last published transaction or txn_idx's
434 : in-prep parent transaction.
435 :
436 : On exit, the head/tail of the updated records is at
437 : *_dst_rec_head_idx / *_dst_rec_tail_idx. As before, all transactions
438 : on this list will have transaction id dst_xid and vice versa.
439 : Transaction txn_idx will have an _empty_ record list.
440 :
441 : Updates in the transaction txn_idx are processed from oldest to
442 : youngest. If an update erases an existing record in dest, the record
443 : to erase is removed from the destination records without perturbing
444 : the order of remaining destination records. If an update is to
445 : update an existing record, the destination record value is updated
446 : and the order of the destination records is unchanged. If an update
447 : is to create a new record, the record is appended to the list of
448 : existing values as youngest without changing the order of existing
449 : values. If an update erases a record in an in-prep parent, the
450 : erasure will be moved into the parent as the youngest without
451 : changing the order of existing values. */
452 :
453 : static void
454 : fd_funk_txn_update( fd_funk_t * funk,
455 : uint * _dst_rec_head_idx, /* Pointer to the dst list head */
456 : uint * _dst_rec_tail_idx, /* Pointer to the dst list tail */
457 : ulong dst_txn_idx, /* Transaction index of the merge destination */
458 : fd_funk_txn_xid_t const * dst_xid, /* dst xid */
459 215977 : ulong txn_idx ) { /* Transaction index of the records to merge */
460 215977 : fd_wksp_t * wksp = funk->wksp;
461 215977 : fd_alloc_t * alloc = funk->alloc;
462 215977 : fd_funk_rec_map_t * rec_map = funk->rec_map;
463 215977 : fd_funk_rec_pool_t * rec_pool = funk->rec_pool;
464 215977 : fd_funk_txn_pool_t * txn_pool = funk->txn_pool;
465 :
466 215977 : fd_funk_txn_t * txn = &txn_pool->ele[ txn_idx ];
467 215977 : uint rec_idx = txn->rec_head_idx;
468 2166170 : while( !fd_funk_rec_idx_is_null( rec_idx ) ) {
469 1950193 : fd_funk_rec_t * rec = &rec_pool->ele[ rec_idx ];
470 1950193 : uint next_rec_idx = rec->next_idx;
471 :
472 : /* See if (dst_xid,key) already exists. */
473 1950193 : fd_funk_xid_key_pair_t pair[1];
474 1950193 : fd_funk_xid_key_pair_init( pair, dst_xid, rec->pair.key );
475 1950193 : for(;;) {
476 1950193 : fd_funk_rec_map_query_t rec_query[1];
477 1950193 : int err = fd_funk_rec_map_remove( rec_map, pair, NULL, rec_query, FD_MAP_FLAG_BLOCKING );
478 1950193 : if( FD_UNLIKELY( err == FD_MAP_ERR_AGAIN ) ) continue;
479 1950193 : if( err == FD_MAP_ERR_KEY ) break;
480 170229 : if( FD_UNLIKELY( err != FD_MAP_SUCCESS ) ) FD_LOG_CRIT(( "map corruption" ));
481 :
482 : /* Remove from the transaction */
483 170229 : fd_funk_rec_t * rec2 = fd_funk_rec_map_query_ele( rec_query );
484 170229 : uint prev_idx = rec2->prev_idx;
485 170229 : uint next_idx = rec2->next_idx;
486 170229 : if( fd_funk_rec_idx_is_null( prev_idx ) ) {
487 2454 : *_dst_rec_head_idx = next_idx;
488 167775 : } else {
489 167775 : rec_pool->ele[ prev_idx ].next_idx = next_idx;
490 167775 : }
491 170229 : if( fd_funk_rec_idx_is_null( next_idx ) ) {
492 411 : *_dst_rec_tail_idx = prev_idx;
493 169818 : } else {
494 169818 : rec_pool->ele[ next_idx ].prev_idx = prev_idx;
495 169818 : }
496 : /* Clean up value */
497 170229 : fd_funk_val_flush( rec2, alloc, wksp );
498 170229 : rec2->txn_cidx = fd_funk_txn_cidx( FD_FUNK_TXN_IDX_NULL );
499 170229 : fd_funk_rec_pool_release( rec_pool, rec2, 1 );
500 170229 : break;
501 170229 : }
502 :
503 : /* Add the new record to the transaction. We can update the xid in
504 : place because it is not used for hashing the element. We have
505 : to preserve the original element to preserve the
506 : newest-to-oldest ordering in the hash
507 : chain. fd_funk_rec_query_global relies on this subtle
508 : property. */
509 :
510 1950193 : rec->pair.xid[0] = *dst_xid;
511 1950193 : rec->txn_cidx = fd_funk_txn_cidx( dst_txn_idx );
512 :
513 1950193 : if( fd_funk_rec_idx_is_null( *_dst_rec_head_idx ) ) {
514 4647 : *_dst_rec_head_idx = rec_idx;
515 4647 : rec->prev_idx = FD_FUNK_REC_IDX_NULL;
516 1945546 : } else {
517 1945546 : rec_pool->ele[ *_dst_rec_tail_idx ].next_idx = rec_idx;
518 1945546 : rec->prev_idx = *_dst_rec_tail_idx;
519 1945546 : }
520 1950193 : *_dst_rec_tail_idx = rec_idx;
521 1950193 : rec->next_idx = FD_FUNK_REC_IDX_NULL;
522 :
523 1950193 : rec_idx = next_rec_idx;
524 1950193 : }
525 :
526 215977 : txn_pool->ele[ txn_idx ].rec_head_idx = FD_FUNK_REC_IDX_NULL;
527 215977 : txn_pool->ele[ txn_idx ].rec_tail_idx = FD_FUNK_REC_IDX_NULL;
528 215977 : }
529 :
530 : /* fd_funk_txn_publish_funk_child publishes a transaction that is known
531 : to be a child of funk. Callers have already validated our input
532 : arguments. Returns FD_FUNK_SUCCESS on success and an FD_FUNK_ERR_*
533 : code on failure. (There are currently no failure cases but the
534 : plumbing is there if value handling requires it at some point.) */
535 :
536 : static int
537 : fd_funk_txn_publish_funk_child( fd_funk_t * const funk,
538 : ulong const tag,
539 203977 : ulong const txn_idx ) {
540 :
541 : /* Apply the updates in txn to the last published transactions */
542 :
543 203977 : 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 );
544 :
545 : /* Cancel all competing transaction histories */
546 :
547 203977 : ulong oldest_idx = fd_funk_txn_oldest_sibling( funk, txn_idx );
548 203977 : fd_funk_txn_cancel_sibling_list( funk, tag, oldest_idx, txn_idx );
549 :
550 : /* Make all the children children of funk */
551 :
552 203977 : fd_funk_txn_t * txn = fd_funk_txn_pool_ele( funk->txn_pool, txn_idx );
553 203977 : ulong child_head_idx = fd_funk_txn_idx( txn->child_head_cidx );
554 203977 : ulong child_tail_idx = fd_funk_txn_idx( txn->child_tail_cidx );
555 :
556 203977 : ulong child_idx = child_head_idx;
557 386202 : while( FD_UNLIKELY( !fd_funk_txn_idx_is_null( child_idx ) ) ) { /* opt for incr pub */
558 182225 : fd_funk_txn_t * child_txn = fd_funk_txn_pool_ele( funk->txn_pool, child_idx );
559 182225 : child_txn->tag = tag;
560 182225 : child_txn->parent_cidx = fd_funk_txn_cidx( FD_FUNK_TXN_IDX_NULL );
561 182225 : child_idx = fd_funk_txn_idx( child_txn->sibling_next_cidx );
562 182225 : }
563 :
564 203977 : funk->shmem->child_head_cidx = fd_funk_txn_cidx( child_head_idx );
565 203977 : funk->shmem->child_tail_cidx = fd_funk_txn_cidx( child_tail_idx );
566 :
567 203977 : fd_funk_txn_xid_copy( funk->shmem->last_publish, fd_funk_txn_xid( txn ) );
568 :
569 : /* Remove the mapping */
570 :
571 203977 : fd_funk_txn_map_query_t query[1];
572 203977 : if( fd_funk_txn_map_remove( funk->txn_map, funk->shmem->last_publish, NULL, query, FD_MAP_FLAG_BLOCKING ) == FD_MAP_SUCCESS ) {
573 203977 : fd_funk_txn_pool_release( funk->txn_pool, txn, 1 );
574 203977 : }
575 :
576 203977 : return FD_FUNK_SUCCESS;
577 203977 : }
578 :
579 : ulong
580 : fd_funk_txn_publish( fd_funk_t * funk,
581 : fd_funk_txn_t * txn,
582 147637 : int verbose ) {
583 :
584 : #ifdef FD_FUNK_HANDHOLDING
585 : if( FD_UNLIKELY( !funk ) ) {
586 : if( FD_UNLIKELY( verbose ) ) FD_LOG_WARNING(( "NULL funk" ));
587 : return 0UL;
588 : }
589 : if( FD_UNLIKELY( !fd_funk_txn_valid( funk, txn ) ) ) {
590 : if( FD_UNLIKELY( verbose ) ) FD_LOG_WARNING(( "bad txn" ));
591 : return 0UL;
592 : }
593 : #else
594 147637 : (void)verbose;
595 147637 : #endif
596 :
597 147637 : ulong txn_idx = (ulong)(txn - funk->txn_pool->ele);
598 :
599 147637 : ulong tag = funk->shmem->cycle_tag++;
600 :
601 147637 : ulong publish_stack_idx = FD_FUNK_TXN_IDX_NULL;
602 :
603 203977 : for(;;) {
604 203977 : fd_funk_txn_t * txn2 = &funk->txn_pool->ele[ txn_idx ];
605 203977 : txn2->tag = tag;
606 :
607 : /* At this point, txn_idx is a transaction that needs to be
608 : published and has been tagged. If txn is a child of funk, we are
609 : ready to publish txn and everything on the publish stack. */
610 :
611 203977 : ulong parent_idx = fd_funk_txn_idx( txn2->parent_cidx );
612 203977 : if( FD_LIKELY( fd_funk_txn_idx_is_null( parent_idx ) ) ) break; /* opt for incr pub */
613 :
614 : /* txn_idx has a parent. Validate and tag it. Push txn to the
615 : publish stack and recurse into the parent. */
616 :
617 56340 : txn2->stack_cidx = fd_funk_txn_cidx( publish_stack_idx );
618 56340 : publish_stack_idx = txn_idx;
619 :
620 56340 : txn_idx = parent_idx;
621 56340 : }
622 :
623 147637 : ulong publish_cnt = 0UL;
624 :
625 203977 : for(;;) {
626 :
627 : /* At this point, all the transactions we need to publish are
628 : tagged, txn is the next up publish funk and publish_stack has the
629 : transactions to follow in order by pop. We use a new tag for
630 : each publish as txn and its siblings we potentially visited in a
631 : previous iteration of this loop. */
632 :
633 203977 : if( FD_UNLIKELY( fd_funk_txn_publish_funk_child( funk, funk->shmem->cycle_tag++, txn_idx ) ) ) break;
634 203977 : publish_cnt++;
635 :
636 203977 : txn_idx = publish_stack_idx;
637 203977 : if( FD_LIKELY( fd_funk_txn_idx_is_null( txn_idx ) ) ) break; /* opt for incr pub */
638 56340 : publish_stack_idx = fd_funk_txn_idx( funk->txn_pool->ele[ txn_idx ].stack_cidx );
639 56340 : }
640 :
641 147637 : return publish_cnt;
642 147637 : }
643 :
644 : int
645 : fd_funk_txn_publish_into_parent( fd_funk_t * funk,
646 : fd_funk_txn_t * txn,
647 12000 : int verbose ) {
648 : #ifdef FD_FUNK_HANDHOLDING
649 : if( FD_UNLIKELY( !funk ) ) {
650 : if( FD_UNLIKELY( verbose ) ) FD_LOG_WARNING(( "NULL funk" ));
651 : return FD_FUNK_ERR_INVAL;
652 : }
653 : if( FD_UNLIKELY( !fd_funk_txn_valid( funk, txn ) ) ) {
654 : if( FD_UNLIKELY( verbose ) ) FD_LOG_WARNING(( "bad txn" ));
655 : return 0UL;
656 : }
657 : #else
658 12000 : (void)verbose;
659 12000 : #endif
660 :
661 12000 : fd_funk_txn_map_t * txn_map = funk->txn_map;
662 12000 : fd_funk_txn_pool_t * txn_pool = funk->txn_pool;
663 12000 : ulong txn_idx = (ulong)(txn - txn_pool->ele);
664 :
665 12000 : ulong oldest_idx = fd_funk_txn_oldest_sibling( funk, txn_idx );
666 12000 : fd_funk_txn_cancel_sibling_list( funk, funk->shmem->cycle_tag++, oldest_idx, txn_idx );
667 :
668 12000 : ulong parent_idx = fd_funk_txn_idx( txn->parent_cidx );
669 12000 : if( fd_funk_txn_idx_is_null( parent_idx ) ) {
670 : /* Publish to root */
671 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 );
672 : /* Inherit the children */
673 2568 : funk->shmem->child_head_cidx = txn->child_head_cidx;
674 2568 : funk->shmem->child_tail_cidx = txn->child_tail_cidx;
675 9432 : } else {
676 9432 : fd_funk_txn_t * parent_txn = &txn_pool->ele[ parent_idx ];
677 9432 : fd_funk_txn_update( funk, &parent_txn->rec_head_idx, &parent_txn->rec_tail_idx, parent_idx, &parent_txn->xid, txn_idx );
678 : /* Inherit the children */
679 9432 : parent_txn->child_head_cidx = txn->child_head_cidx;
680 9432 : parent_txn->child_tail_cidx = txn->child_tail_cidx;
681 9432 : }
682 :
683 : /* Adjust the parent pointers of the children to point to their grandparent */
684 12000 : ulong child_idx = fd_funk_txn_idx( txn->child_head_cidx );
685 21123 : while( FD_UNLIKELY( !fd_funk_txn_idx_is_null( child_idx ) ) ) {
686 9123 : txn_pool->ele[ child_idx ].parent_cidx = fd_funk_txn_cidx( parent_idx );
687 9123 : child_idx = fd_funk_txn_idx( txn_pool->ele[ child_idx ].sibling_next_cidx );
688 9123 : }
689 :
690 12000 : fd_funk_txn_map_query_t query[1];
691 12000 : if( fd_funk_txn_map_remove( txn_map, fd_funk_txn_xid( txn ), NULL, query, FD_MAP_FLAG_BLOCKING ) == FD_MAP_SUCCESS ) {
692 12000 : fd_funk_txn_pool_release( txn_pool, txn, 1 );
693 12000 : }
694 :
695 12000 : return FD_FUNK_SUCCESS;
696 12000 : }
697 :
698 : /* Return the first record in a transaction. Returns NULL if the
699 : transaction has no records yet. */
700 :
701 : fd_funk_rec_t const *
702 : fd_funk_txn_first_rec( fd_funk_t * funk,
703 47622933 : fd_funk_txn_t const * txn ) {
704 47622933 : uint rec_idx;
705 47622933 : if( FD_UNLIKELY( NULL == txn ))
706 3247731 : rec_idx = funk->shmem->rec_head_idx;
707 44375202 : else
708 44375202 : rec_idx = txn->rec_head_idx;
709 47622933 : if( fd_funk_rec_idx_is_null( rec_idx ) ) return NULL;
710 31761792 : return funk->rec_pool->ele + rec_idx;
711 47622933 : }
712 :
713 : fd_funk_rec_t const *
714 : fd_funk_txn_last_rec( fd_funk_t * funk,
715 0 : fd_funk_txn_t const * txn ) {
716 0 : uint rec_idx;
717 0 : if( FD_UNLIKELY( NULL == txn ))
718 0 : rec_idx = funk->shmem->rec_tail_idx;
719 0 : else
720 0 : rec_idx = txn->rec_tail_idx;
721 0 : if( fd_funk_rec_idx_is_null( rec_idx ) ) return NULL;
722 0 : return funk->rec_pool->ele + rec_idx;
723 0 : }
724 :
725 : /* Return the next record in a transaction. Returns NULL if the
726 : transaction has no more records. */
727 :
728 : fd_funk_rec_t const *
729 : fd_funk_txn_next_rec( fd_funk_t * funk,
730 656335248 : fd_funk_rec_t const * rec ) {
731 656335248 : uint rec_idx = rec->next_idx;
732 656335248 : if( fd_funk_rec_idx_is_null( rec_idx ) ) return NULL;
733 594079938 : return funk->rec_pool->ele + rec_idx;
734 656335248 : }
735 :
736 : fd_funk_rec_t const *
737 : fd_funk_txn_prev_rec( fd_funk_t * funk,
738 318768039 : fd_funk_rec_t const * rec ) {
739 318768039 : uint rec_idx = rec->prev_idx;
740 318768039 : if( fd_funk_rec_idx_is_null( rec_idx ) ) return NULL;
741 288274521 : return funk->rec_pool->ele + rec_idx;
742 318768039 : }
743 :
744 : fd_funk_txn_xid_t
745 18918876 : fd_funk_generate_xid(void) {
746 18918876 : fd_funk_txn_xid_t xid;
747 18918876 : static FD_TL ulong seq = 0;
748 18918876 : xid.ul[0] =
749 18918876 : (fd_log_cpu_id() + 1U)*3138831853UL +
750 18918876 : (fd_log_thread_id() + 1U)*9180195821UL +
751 18918876 : (++seq)*6208101967UL;
752 18918876 : xid.ul[1] = ((ulong)fd_tickcount())*2810745731UL;
753 18918876 : return xid;
754 18918876 : }
755 :
756 : static void
757 3817717099 : fd_funk_txn_all_iter_skip_nulls( fd_funk_txn_all_iter_t * iter ) {
758 3817717099 : if( iter->chain_idx == iter->chain_cnt ) return;
759 6465226736 : while( fd_funk_txn_map_iter_done( iter->txn_map_iter ) ) {
760 2826233943 : if( ++(iter->chain_idx) == iter->chain_cnt ) break;
761 2647509637 : iter->txn_map_iter = fd_funk_txn_map_iter( &iter->txn_map, iter->chain_idx );
762 2647509637 : }
763 3817717099 : }
764 :
765 : void
766 : fd_funk_txn_all_iter_new( fd_funk_t * funk,
767 178724306 : fd_funk_txn_all_iter_t * iter ) {
768 178724306 : iter->txn_map = *funk->txn_map;
769 178724306 : iter->chain_cnt = fd_funk_txn_map_chain_cnt( funk->txn_map );
770 178724306 : iter->chain_idx = 0;
771 178724306 : iter->txn_map_iter = fd_funk_txn_map_iter( funk->txn_map, 0 );
772 178724306 : fd_funk_txn_all_iter_skip_nulls( iter );
773 178724306 : }
774 :
775 : int
776 3817717099 : fd_funk_txn_all_iter_done( fd_funk_txn_all_iter_t * iter ) {
777 3817717099 : return ( iter->chain_idx == iter->chain_cnt );
778 3817717099 : }
779 :
780 : void
781 3638992793 : fd_funk_txn_all_iter_next( fd_funk_txn_all_iter_t * iter ) {
782 3638992793 : iter->txn_map_iter = fd_funk_txn_map_iter_next( iter->txn_map_iter );
783 3638992793 : fd_funk_txn_all_iter_skip_nulls( iter );
784 3638992793 : }
785 :
786 : fd_funk_txn_t const *
787 1846548 : fd_funk_txn_all_iter_ele_const( fd_funk_txn_all_iter_t * iter ) {
788 1846548 : return fd_funk_txn_map_iter_ele_const( iter->txn_map_iter );
789 1846548 : }
790 :
791 : fd_funk_txn_t *
792 3637145631 : fd_funk_txn_all_iter_ele( fd_funk_txn_all_iter_t * iter ) {
793 3637145631 : return fd_funk_txn_map_iter_ele( iter->txn_map_iter );
794 3637145631 : }
795 :
796 : int
797 12 : fd_funk_txn_verify( fd_funk_t * funk ) {
798 12 : fd_funk_txn_map_t * txn_map = funk->txn_map;
799 12 : fd_funk_txn_pool_t * txn_pool = funk->txn_pool;
800 12 : ulong txn_max = fd_funk_txn_pool_ele_max( txn_pool );
801 :
802 12 : ulong funk_child_head_idx = fd_funk_txn_idx( funk->shmem->child_head_cidx ); /* Previously verified */
803 12 : ulong funk_child_tail_idx = fd_funk_txn_idx( funk->shmem->child_tail_cidx ); /* Previously verified */
804 :
805 12 : fd_funk_txn_xid_t const * last_publish = funk->shmem->last_publish; /* Previously verified */
806 :
807 24 : # define TEST(c) do { \
808 24 : if( FD_UNLIKELY( !(c) ) ) { FD_LOG_WARNING(( "FAIL: %s", #c )); return FD_FUNK_ERR_INVAL; } \
809 24 : } while(0)
810 :
811 12 : # define IS_VALID( idx ) ( (idx==FD_FUNK_TXN_IDX_NULL) || \
812 12 : ((idx<txn_max) && (!fd_funk_txn_xid_eq( fd_funk_txn_xid( &txn_pool->ele[idx] ), last_publish ))) )
813 :
814 12 : TEST( !fd_funk_txn_map_verify( txn_map ) );
815 12 : TEST( !fd_funk_txn_pool_verify( txn_pool ) );
816 :
817 : /* Tag all transactions as not visited yet */
818 :
819 1572876 : for( ulong txn_idx=0UL; txn_idx<txn_max; txn_idx++ ) txn_pool->ele[ txn_idx ].tag = 0UL;
820 :
821 : /* Visit all transactions in preparation, traversing from oldest to
822 : youngest. */
823 :
824 12 : do {
825 :
826 : /* Push all children of funk to the stack */
827 :
828 12 : ulong stack_idx = FD_FUNK_TXN_IDX_NULL;
829 12 : ulong child_idx = funk_child_head_idx;
830 12 : while( !fd_funk_txn_idx_is_null( child_idx ) ) {
831 :
832 : /* Make sure valid idx, not tagged (detects cycles) and child
833 : knows it is a child of funk. Then tag as visited / in-prep,
834 : push to stack and update prep_cnt */
835 :
836 0 : TEST( IS_VALID( child_idx ) );
837 0 : TEST( !txn_pool->ele[ child_idx ].tag );
838 0 : TEST( fd_funk_txn_idx_is_null( fd_funk_txn_idx( txn_pool->ele[ child_idx ].parent_cidx ) ) );
839 0 : txn_pool->ele[ child_idx ].tag = 1UL;
840 0 : txn_pool->ele[ child_idx ].stack_cidx = fd_funk_txn_cidx( stack_idx );
841 0 : stack_idx = child_idx;
842 :
843 0 : ulong next_idx = fd_funk_txn_idx( txn_pool->ele[ child_idx ].sibling_next_cidx );
844 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 );
845 0 : child_idx = next_idx;
846 0 : }
847 :
848 12 : while( !fd_funk_txn_idx_is_null( stack_idx ) ) {
849 :
850 : /* Pop the next transaction to traverse */
851 :
852 0 : ulong txn_idx = stack_idx;
853 0 : stack_idx = fd_funk_txn_idx( txn_pool->ele[ txn_idx ].stack_cidx );
854 :
855 : /* Push all children of txn to the stack */
856 :
857 0 : ulong child_idx = fd_funk_txn_idx( txn_pool->ele[ txn_idx ].child_head_cidx );
858 0 : while( !fd_funk_txn_idx_is_null( child_idx ) ) {
859 :
860 : /* Make sure valid idx, not tagged (detects cycles) and child
861 : knows it is a child of txn_idx. Then tag as visited /
862 : in-prep, push to stack and update prep_cnt */
863 :
864 0 : TEST( IS_VALID( child_idx ) );
865 0 : TEST( !txn_pool->ele[ child_idx ].tag );
866 0 : TEST( fd_funk_txn_idx( txn_pool->ele[ child_idx ].parent_cidx )==txn_idx );
867 0 : txn_pool->ele[ child_idx ].tag = 1UL;
868 0 : txn_pool->ele[ child_idx ].stack_cidx = fd_funk_txn_cidx( stack_idx );
869 0 : stack_idx = child_idx;
870 :
871 0 : ulong next_idx = fd_funk_txn_idx( txn_pool->ele[ child_idx ].sibling_next_cidx );
872 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 );
873 0 : child_idx = next_idx;
874 0 : }
875 0 : }
876 :
877 12 : } while(0);
878 :
879 : /* Do it again with a youngest to oldest traversal to test reverse
880 : link integrity */
881 :
882 12 : do {
883 :
884 : /* Push all children of funk to the stack */
885 :
886 12 : ulong stack_idx = FD_FUNK_TXN_IDX_NULL;
887 12 : ulong child_idx = funk_child_tail_idx;
888 12 : while( !fd_funk_txn_idx_is_null( child_idx ) ) {
889 :
890 : /* Make sure valid idx, tagged as visited above (detects cycles)
891 : and child knows it is a child of funk. Then tag as visited /
892 : in-prep, push to stack and update prep_cnt */
893 :
894 0 : TEST( IS_VALID( child_idx ) );
895 0 : TEST( txn_pool->ele[ child_idx ].tag==1UL );
896 0 : TEST( fd_funk_txn_idx_is_null( fd_funk_txn_idx( txn_pool->ele[ child_idx ].parent_cidx ) ) );
897 0 : txn_pool->ele[ child_idx ].tag = 2UL;
898 0 : txn_pool->ele[ child_idx ].stack_cidx = fd_funk_txn_cidx( stack_idx );
899 0 : stack_idx = child_idx;
900 :
901 0 : ulong prev_idx = fd_funk_txn_idx( txn_pool->ele[ child_idx ].sibling_prev_cidx );
902 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 );
903 0 : child_idx = prev_idx;
904 0 : }
905 :
906 12 : while( !fd_funk_txn_idx_is_null( stack_idx ) ) {
907 :
908 : /* Pop the next transaction to traverse */
909 :
910 0 : ulong txn_idx = stack_idx;
911 0 : stack_idx = fd_funk_txn_idx( txn_pool->ele[ txn_idx ].stack_cidx );
912 :
913 : /* Push all children of txn to the stack */
914 :
915 0 : ulong child_idx = fd_funk_txn_idx( txn_pool->ele[ txn_idx ].child_tail_cidx );
916 0 : while( !fd_funk_txn_idx_is_null( child_idx ) ) {
917 :
918 : /* Make sure valid idx, tagged as visited above (detects cycles)
919 : and child knows it is a child of txn_idx. Then, tag as
920 : visited / in-prep, push to stack and update prep_cnt */
921 :
922 0 : TEST( IS_VALID( child_idx ) );
923 0 : TEST( txn_pool->ele[ child_idx ].tag==1UL );
924 0 : TEST( fd_funk_txn_idx( txn_pool->ele[ child_idx ].parent_cidx )==txn_idx );
925 0 : txn_pool->ele[ child_idx ].tag = 2UL;
926 0 : txn_pool->ele[ child_idx ].stack_cidx = fd_funk_txn_cidx( stack_idx );
927 0 : stack_idx = child_idx;
928 :
929 0 : ulong prev_idx = fd_funk_txn_idx( txn_pool->ele[ child_idx ].sibling_prev_cidx );
930 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 );
931 0 : child_idx = prev_idx;
932 0 : }
933 0 : }
934 12 : } while(0);
935 :
936 12 : # undef IS_VALID
937 12 : # undef TEST
938 :
939 12 : return FD_FUNK_SUCCESS;
940 12 : }
941 :
942 : int
943 0 : fd_funk_txn_valid( fd_funk_t const * funk, fd_funk_txn_t const * txn ) {
944 0 : ulong txn_idx = (ulong)(txn - funk->txn_pool->ele);
945 0 : ulong txn_max = fd_funk_txn_pool_ele_max( funk->txn_pool );
946 0 : if( txn_idx>=txn_max || txn != txn_idx + funk->txn_pool->ele ) return 0;
947 0 : fd_funk_txn_map_query_t query[1];
948 0 : if( FD_UNLIKELY( fd_funk_txn_map_query_try( funk->txn_map, &txn->xid, NULL, query, 0 ) ) ) return 0;
949 0 : if( fd_funk_txn_map_query_ele( query ) != txn ) return 0;
950 0 : return 1;
951 0 : }
|
