Line data Source code
1 : #include "fd_funkier.h"
2 :
3 : /* Provide the actual transaction map implementation */
4 :
5 : #define POOL_NAME fd_funkier_txn_pool
6 0 : #define POOL_ELE_T fd_funkier_txn_t
7 : #define POOL_IDX_T uint
8 0 : #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_funkier_txn_map
13 0 : #define MAP_ELE_T fd_funkier_txn_t
14 0 : #define MAP_KEY_T fd_funkier_txn_xid_t
15 0 : #define MAP_KEY xid
16 : #define MAP_KEY_EQ(k0,k1) fd_funkier_txn_xid_eq((k0),(k1))
17 : #define MAP_KEY_HASH(k0,seed) fd_funkier_txn_xid_hash((k0),(seed))
18 0 : #define MAP_NEXT map_next
19 : #define MAP_HASH map_hash
20 0 : #define MAP_MAGIC (0xf173da2ce7172db0UL) /* Firedancer txn db version 0 */
21 : #define MAP_IMPL_STYLE 2
22 : #include "../util/tmpl/fd_map_para.c"
23 :
24 : fd_funkier_txn_t *
25 : fd_funkier_txn_prepare( fd_funkier_t * funk,
26 : fd_funkier_txn_t * parent,
27 : fd_funkier_txn_xid_t const * xid,
28 0 : int verbose ) {
29 :
30 : #ifdef FD_FUNKIER_HANDHOLDING
31 : if( FD_UNLIKELY( !funk ) ) {
32 : if( FD_UNLIKELY( verbose ) ) FD_LOG_WARNING(( "NULL funk" ));
33 : return NULL;
34 : }
35 : if( FD_UNLIKELY( !xid ) ) {
36 : if( FD_UNLIKELY( verbose ) ) FD_LOG_WARNING(( "NULL xid" ));
37 : return NULL;
38 : }
39 : if( FD_UNLIKELY( parent && !fd_funkier_txn_valid( funk, parent ) ) ) {
40 : if( FD_UNLIKELY( verbose ) ) FD_LOG_WARNING(( "bad txn" ));
41 : return NULL;
42 : }
43 : if( FD_UNLIKELY( fd_funkier_txn_xid_eq_root( xid ) ) ) {
44 : if( FD_UNLIKELY( verbose ) ) FD_LOG_WARNING(( "xid is the root" ));
45 : return NULL;
46 : }
47 : if( FD_UNLIKELY( fd_funkier_txn_xid_eq( xid, funk->last_publish ) ) ) {
48 : if( FD_UNLIKELY( verbose ) ) FD_LOG_WARNING(( "xid is the last published" ));
49 : return NULL;
50 : }
51 : #endif
52 :
53 0 : fd_wksp_t * wksp = fd_funkier_wksp( funk );
54 0 : fd_funkier_txn_map_t txn_map = fd_funkier_txn_map( funk, wksp );
55 0 : fd_funkier_txn_pool_t txn_pool = fd_funkier_txn_pool( funk, wksp );
56 :
57 0 : fd_funkier_txn_map_query_t query[1];
58 0 : if( FD_UNLIKELY( fd_funkier_txn_map_query_try( &txn_map, xid, NULL, query ) != FD_MAP_ERR_KEY ) ) {
59 0 : if( FD_UNLIKELY( verbose ) ) FD_LOG_WARNING(( "xid in use" ));
60 0 : return NULL;
61 0 : }
62 :
63 0 : ulong parent_idx;
64 0 : uint * _child_head_cidx;
65 0 : uint * _child_tail_cidx;
66 :
67 0 : if( FD_LIKELY( !parent ) ) { /* opt for incr pub */
68 :
69 0 : parent_idx = FD_FUNKIER_TXN_IDX_NULL;
70 :
71 0 : _child_head_cidx = &funk->child_head_cidx;
72 0 : _child_tail_cidx = &funk->child_tail_cidx;
73 :
74 0 : } else {
75 :
76 0 : parent_idx = (ulong)(parent - txn_pool.ele);
77 :
78 0 : _child_head_cidx = &parent->child_head_cidx;
79 0 : _child_tail_cidx = &parent->child_tail_cidx;
80 :
81 0 : }
82 :
83 : /* Get a new transaction from the map */
84 :
85 0 : fd_funkier_txn_t * txn = fd_funkier_txn_pool_acquire( &txn_pool, NULL, 1, NULL );
86 0 : if( txn == NULL ) {
87 0 : if( FD_UNLIKELY( verbose ) ) FD_LOG_WARNING(( "transaction pool is exhuasted" ));
88 0 : return NULL;
89 0 : }
90 0 : fd_funkier_txn_xid_copy( &txn->xid, xid );
91 0 : ulong txn_idx = (ulong)(txn - txn_pool.ele);
92 :
93 : /* Join the family */
94 :
95 0 : ulong sibling_prev_idx = fd_funkier_txn_idx( *_child_tail_cidx );
96 :
97 0 : int first_born = fd_funkier_txn_idx_is_null( sibling_prev_idx );
98 :
99 0 : txn->parent_cidx = fd_funkier_txn_cidx( parent_idx );
100 0 : txn->child_head_cidx = fd_funkier_txn_cidx( FD_FUNKIER_TXN_IDX_NULL );
101 0 : txn->child_tail_cidx = fd_funkier_txn_cidx( FD_FUNKIER_TXN_IDX_NULL );
102 0 : txn->sibling_prev_cidx = fd_funkier_txn_cidx( sibling_prev_idx );
103 0 : txn->sibling_next_cidx = fd_funkier_txn_cidx( FD_FUNKIER_TXN_IDX_NULL );
104 0 : txn->stack_cidx = fd_funkier_txn_cidx( FD_FUNKIER_TXN_IDX_NULL );
105 0 : txn->tag = 0UL;
106 :
107 0 : txn->rec_head_idx = FD_FUNKIER_REC_IDX_NULL;
108 0 : txn->rec_tail_idx = FD_FUNKIER_REC_IDX_NULL;
109 :
110 : /* TODO: consider branchless impl */
111 0 : if( FD_LIKELY( first_born ) ) *_child_head_cidx = fd_funkier_txn_cidx( txn_idx ); /* opt for non-compete */
112 0 : else txn_pool.ele[ sibling_prev_idx ].sibling_next_cidx = fd_funkier_txn_cidx( txn_idx );
113 :
114 0 : *_child_tail_cidx = fd_funkier_txn_cidx( txn_idx );
115 :
116 0 : fd_funkier_txn_map_insert( &txn_map, txn, FD_MAP_FLAG_BLOCKING );
117 :
118 0 : return txn;
119 0 : }
120 :
121 : int
122 0 : fd_funkier_txn_is_full( fd_funkier_t * funk ) {
123 0 : fd_wksp_t * wksp = fd_funkier_wksp( funk );
124 0 : fd_funkier_txn_pool_t txn_pool = fd_funkier_txn_pool( funk, wksp );
125 0 : return fd_funkier_txn_pool_is_empty( &txn_pool );
126 0 : }
127 :
128 : /* fd_funkier_txn_cancel_childless cancels a transaction that is known
129 : to be childless. Callers have already validated our input arguments.
130 : Assumes that cancelling in the app can't fail but that could be
131 : straightforward to support by giving this an error and plumbing
132 : through to abort the overall cancel operation when it hits a error. */
133 :
134 : static void
135 : fd_funkier_txn_cancel_childless( fd_funkier_t * funk,
136 0 : ulong txn_idx ) {
137 :
138 : /* Remove all records used by this transaction. Note that we don't
139 : need to bother doing all the individual removal operations as we
140 : are removing the whole list. We do reset the record transaction
141 : idx with NULL though we can detect cycles as soon as possible
142 : and abort. */
143 :
144 0 : fd_wksp_t * wksp = fd_funkier_wksp( funk );
145 0 : fd_alloc_t * alloc = fd_funkier_alloc( funk, wksp );
146 0 : fd_funkier_rec_map_t rec_map = fd_funkier_rec_map( funk, wksp );
147 0 : fd_funkier_rec_pool_t rec_pool = fd_funkier_rec_pool( funk, wksp );
148 0 : ulong rec_max = funk->rec_max;
149 0 : fd_funkier_txn_map_t txn_map = fd_funkier_txn_map( funk, wksp );
150 0 : fd_funkier_txn_pool_t txn_pool = fd_funkier_txn_pool( funk, wksp );
151 :
152 0 : fd_funkier_txn_t * txn = &txn_pool.ele[ txn_idx ];
153 0 : ulong rec_idx = txn->rec_head_idx;
154 0 : while( !fd_funkier_rec_idx_is_null( rec_idx ) ) {
155 :
156 0 : if( FD_UNLIKELY( rec_idx>=rec_max ) ) FD_LOG_CRIT(( "memory corruption detected (bad idx)" ));
157 0 : if( FD_UNLIKELY( fd_funkier_txn_idx( rec_pool.ele[ rec_idx ].txn_cidx )!=txn_idx ) )
158 0 : FD_LOG_CRIT(( "memory corruption detected (cycle or bad idx)" ));
159 :
160 0 : fd_funkier_rec_t * rec = &rec_pool.ele[ rec_idx ];
161 0 : ulong next_idx = rec->next_idx;
162 0 : rec->txn_cidx = fd_funkier_txn_cidx( FD_FUNKIER_TXN_IDX_NULL );
163 :
164 0 : for(;;) {
165 0 : fd_funkier_rec_map_query_t rec_query[1];
166 0 : int err = fd_funkier_rec_map_remove( &rec_map, fd_funkier_rec_pair( rec ), NULL, rec_query, FD_MAP_FLAG_BLOCKING );
167 0 : if( FD_UNLIKELY( err == FD_MAP_ERR_AGAIN ) ) continue;
168 0 : if( err == FD_MAP_ERR_KEY ) break;
169 0 : if( FD_UNLIKELY( err != FD_MAP_SUCCESS ) ) FD_LOG_CRIT(( "map corruption" ));
170 0 : if( rec != fd_funkier_rec_map_query_ele( rec_query ) ) break;
171 0 : fd_funkier_val_flush( rec, alloc, wksp );
172 0 : fd_funkier_rec_pool_release( &rec_pool, rec, 1 );
173 0 : break;
174 0 : }
175 :
176 0 : rec_idx = next_idx;
177 0 : }
178 :
179 : /* Leave the family */
180 :
181 0 : ulong sibling_prev_idx = fd_funkier_txn_idx( txn->sibling_prev_cidx );
182 0 : ulong sibling_next_idx = fd_funkier_txn_idx( txn->sibling_next_cidx );
183 :
184 : /* TODO: Consider branchless impl */
185 :
186 0 : if( FD_LIKELY( fd_funkier_txn_idx_is_null( sibling_prev_idx ) ) ) { /* opt for non-compete */
187 0 : ulong parent_idx = fd_funkier_txn_idx( txn_pool.ele[ txn_idx ].parent_cidx );
188 0 : if( FD_LIKELY( fd_funkier_txn_idx_is_null( parent_idx ) ) ) { /* No older sib and is a funk child, opt for incr pub */
189 0 : funk->child_head_cidx = fd_funkier_txn_cidx( sibling_next_idx );
190 0 : } else { /* No older sib and has parent */
191 0 : txn_pool.ele[ parent_idx ].child_head_cidx = fd_funkier_txn_cidx( sibling_next_idx );
192 0 : }
193 0 : } else { /* Has older sib */
194 0 : txn_pool.ele[ sibling_prev_idx ].sibling_next_cidx = fd_funkier_txn_cidx( sibling_next_idx );
195 0 : }
196 :
197 0 : if( FD_LIKELY( fd_funkier_txn_idx_is_null( sibling_next_idx ) ) ) { /* opt for non-compete */
198 0 : ulong parent_idx = fd_funkier_txn_idx( txn_pool.ele[ txn_idx ].parent_cidx );
199 0 : if( FD_LIKELY( fd_funkier_txn_idx_is_null( parent_idx ) ) ) { /* No younger sib and is a funk child, opt for incr pub */
200 0 : funk->child_tail_cidx = fd_funkier_txn_cidx( sibling_prev_idx );
201 0 : } else { /* No younger sib and has parent */
202 0 : txn_pool.ele[ parent_idx ].child_tail_cidx = fd_funkier_txn_cidx( sibling_prev_idx );
203 0 : }
204 0 : } else { /* Has younger sib */
205 0 : txn_pool.ele[ sibling_next_idx ].sibling_prev_cidx = fd_funkier_txn_cidx( sibling_prev_idx );
206 0 : }
207 :
208 0 : fd_funkier_txn_map_query_t query[1];
209 0 : if( fd_funkier_txn_map_remove( &txn_map, fd_funkier_txn_xid( txn ), NULL, query, FD_MAP_FLAG_BLOCKING ) == FD_MAP_SUCCESS ) {
210 0 : fd_funkier_txn_pool_release( &txn_pool, txn, 1 );
211 0 : }
212 0 : }
213 :
214 : /* fd_funkier_txn_cancel_family cancels a transaction and all its
215 : descendants in a tree-depth-first-ordered sense from youngest to
216 : oldest. Callers have already validated our input arguments. Returns
217 : the number of transactions canceled. */
218 :
219 : static ulong
220 : fd_funkier_txn_cancel_family( fd_funkier_t * funk,
221 : ulong tag,
222 0 : ulong txn_idx ) {
223 0 : ulong cancel_cnt = 0UL;
224 :
225 0 : fd_wksp_t * wksp = fd_funkier_wksp ( funk );
226 0 : fd_funkier_txn_pool_t txn_pool = fd_funkier_txn_pool( funk, wksp );
227 :
228 0 : ulong parent_stack_idx = FD_FUNKIER_TXN_IDX_NULL;
229 :
230 0 : for(;;) {
231 :
232 0 : fd_funkier_txn_t * txn = &txn_pool.ele[ txn_idx ];
233 0 : txn->tag = tag;
234 :
235 0 : ulong youngest_idx = fd_funkier_txn_idx( txn->child_tail_cidx );
236 0 : if( FD_LIKELY( fd_funkier_txn_idx_is_null( youngest_idx ) ) ) { /* txn is is childless, opt for incr pub */
237 :
238 0 : fd_funkier_txn_cancel_childless( funk, txn_idx ); /* If this can fail, return cancel_cnt here on fail */
239 0 : cancel_cnt++;
240 :
241 0 : txn_idx = parent_stack_idx; /* Pop the parent stack */
242 0 : if( FD_LIKELY( fd_funkier_txn_idx_is_null( txn_idx ) ) ) break; /* If stack is empty, we are done, opt for incr pub */
243 0 : parent_stack_idx = fd_funkier_txn_idx( txn_pool.ele[ txn_idx ].stack_cidx );
244 0 : continue;
245 0 : }
246 :
247 : /* txn has at least one child and the youngest is youngest_idx. Tag
248 : the youngest child, push txn onto the parent stack and recurse
249 : into the youngest child. */
250 :
251 0 : txn->stack_cidx = fd_funkier_txn_cidx( parent_stack_idx );
252 0 : parent_stack_idx = txn_idx;
253 :
254 0 : txn_idx = youngest_idx;
255 0 : }
256 :
257 0 : return cancel_cnt;
258 0 : }
259 :
260 : ulong
261 : fd_funkier_txn_cancel( fd_funkier_t * funk,
262 : fd_funkier_txn_t * txn,
263 0 : int verbose ) {
264 :
265 : #ifdef FD_FUNKIER_HANDHOLDING
266 : if( FD_UNLIKELY( !funk ) ) {
267 : if( FD_UNLIKELY( verbose ) ) FD_LOG_WARNING(( "NULL funk" ));
268 : return 0UL;
269 : }
270 : if( FD_UNLIKELY( !fd_funkier_txn_valid( funk, txn ) ) ) {
271 : if( FD_UNLIKELY( verbose ) ) FD_LOG_WARNING(( "bad txn" ));
272 : return 0UL;
273 : }
274 : #else
275 0 : (void)verbose;
276 0 : #endif
277 :
278 0 : fd_wksp_t * wksp = fd_funkier_wksp( funk );
279 0 : fd_funkier_txn_pool_t txn_pool = fd_funkier_txn_pool( funk, wksp );
280 0 : ulong txn_idx = (ulong)(txn - txn_pool.ele);
281 :
282 0 : return fd_funkier_txn_cancel_family( funk, funk->cycle_tag++, txn_idx );
283 0 : }
284 :
285 : /* fd_funkier_txn_oldest_sibling returns the index of the oldest sibling
286 : in txn_idx's family. Callers have already validated our input
287 : arguments. The caller should validate the return index. */
288 :
289 : static inline ulong
290 : fd_funkier_txn_oldest_sibling( fd_funkier_t * funk,
291 0 : ulong txn_idx ) {
292 :
293 0 : fd_wksp_t * wksp = fd_funkier_wksp( funk );
294 0 : fd_funkier_txn_pool_t txn_pool = fd_funkier_txn_pool( funk, wksp );
295 0 : ulong parent_idx = fd_funkier_txn_idx( txn_pool.ele[ txn_idx ].parent_cidx );
296 :
297 0 : if( FD_LIKELY( fd_funkier_txn_idx_is_null( parent_idx ) ) ) return fd_funkier_txn_idx( funk->child_head_cidx ); /* opt for incr pub */
298 :
299 0 : return fd_funkier_txn_idx( txn_pool.ele[ parent_idx ].child_head_cidx );
300 0 : }
301 :
302 : /* fd_funkier_txn_cancel_sibling_list cancels siblings from sibling_idx down
303 : to the youngest sibling inclusive in the order from youngest to
304 : sibling_idx. Callers have already validated our input arguments
305 : except sibling_idx. Returns the number of cancelled transactions
306 : (should be at least 1). If any sibling is skip_idx, it will be not
307 : be cancelled but still tagged as visited. Passing
308 : FD_FUNKIER_TXN_IDX_NULL for skip_idx will cancel all siblings from
309 : sibling_idx to the youngest inclusive. */
310 :
311 : static ulong
312 : fd_funkier_txn_cancel_sibling_list( fd_funkier_t * funk,
313 : ulong tag,
314 : ulong sibling_idx,
315 0 : ulong skip_idx ) {
316 :
317 0 : fd_wksp_t * wksp = fd_funkier_wksp( funk );
318 0 : fd_funkier_txn_pool_t txn_pool = fd_funkier_txn_pool( funk, wksp );
319 :
320 0 : ulong cancel_stack_idx = FD_FUNKIER_TXN_IDX_NULL;
321 :
322 : /* Push siblings_idx and its younger siblings inclusive (skipping
323 : sibling skip_idx if encounter) onto the cancel stack from oldest to
324 : youngest (such that we cancel youngest to oldest). */
325 :
326 0 : for(;;) {
327 :
328 : /* At this point, sibling_idx is a sibling we might want to add to
329 : the sibling stack. Validate and tag it. */
330 :
331 0 : fd_funkier_txn_t * sibling = &txn_pool.ele[ sibling_idx ];
332 0 : sibling->tag = tag;
333 :
334 0 : if( FD_UNLIKELY( sibling_idx!=skip_idx ) ) { /* Not skip_idx so push onto the cancel stack, opt for non-compete */
335 0 : sibling->stack_cidx = fd_funkier_txn_cidx( cancel_stack_idx );
336 0 : cancel_stack_idx = sibling_idx;
337 0 : }
338 :
339 0 : ulong younger_idx = fd_funkier_txn_idx( sibling->sibling_next_cidx );
340 0 : if( FD_LIKELY( fd_funkier_txn_idx_is_null( younger_idx ) ) ) break; /* opt for non-compete */
341 0 : sibling_idx = younger_idx;
342 :
343 0 : }
344 :
345 : /* Cancel all transactions and their descendants on the cancel stack */
346 :
347 0 : ulong cancel_cnt = 0UL;
348 :
349 0 : while( !fd_funkier_txn_idx_is_null( cancel_stack_idx ) ) { /* TODO: peel first iter to make more predictable? */
350 0 : ulong sibling_idx = cancel_stack_idx;
351 0 : cancel_stack_idx = fd_funkier_txn_idx( txn_pool.ele[ sibling_idx ].stack_cidx );
352 0 : cancel_cnt += fd_funkier_txn_cancel_family( funk, tag, sibling_idx );
353 0 : }
354 :
355 0 : return cancel_cnt;
356 0 : }
357 :
358 : ulong
359 : fd_funkier_txn_cancel_siblings( fd_funkier_t * funk,
360 : fd_funkier_txn_t * txn,
361 0 : int verbose ) {
362 :
363 : #ifdef FD_FUNKIER_HANDHOLDING
364 : if( FD_UNLIKELY( !funk ) ) {
365 : if( FD_UNLIKELY( verbose ) ) FD_LOG_WARNING(( "NULL funk" ));
366 : return 0UL;
367 : }
368 : if( FD_UNLIKELY( !fd_funkier_txn_valid( funk, txn ) ) ) {
369 : if( FD_UNLIKELY( verbose ) ) FD_LOG_WARNING(( "bad txn" ));
370 : return 0UL;
371 : }
372 : #else
373 0 : (void)verbose;
374 0 : #endif
375 :
376 0 : fd_wksp_t * wksp = fd_funkier_wksp( funk );
377 0 : fd_funkier_txn_pool_t txn_pool = fd_funkier_txn_pool( funk, wksp );
378 0 : ulong txn_idx = (ulong)(txn - txn_pool.ele);
379 :
380 0 : ulong oldest_idx = fd_funkier_txn_oldest_sibling( funk, txn_idx );
381 :
382 0 : return fd_funkier_txn_cancel_sibling_list( funk, funk->cycle_tag++, oldest_idx, txn_idx );
383 0 : }
384 :
385 : ulong
386 : fd_funkier_txn_cancel_children( fd_funkier_t * funk,
387 : fd_funkier_txn_t * txn,
388 0 : int verbose ) {
389 :
390 : #ifdef FD_FUNKIER_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_funkier_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_funkier_txn_idx( funk->child_head_cidx ); /* opt for non-compete */
407 0 : } else {
408 0 : oldest_idx = fd_funkier_txn_idx( txn->child_head_cidx );
409 0 : }
410 :
411 0 : if( fd_funkier_txn_idx_is_null( oldest_idx ) ) {
412 0 : return 0UL;
413 0 : }
414 :
415 0 : return fd_funkier_txn_cancel_sibling_list( funk, funk->cycle_tag++, oldest_idx, FD_FUNKIER_TXN_IDX_NULL );
416 0 : }
417 :
418 : /* Cancel all outstanding transactions */
419 :
420 : ulong
421 : fd_funkier_txn_cancel_all( fd_funkier_t * funk,
422 0 : int verbose ) {
423 0 : return fd_funkier_txn_cancel_children( funk, NULL, verbose );
424 0 : }
425 :
426 : /* fd_funkier_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_funkier_txn_update( fd_funkier_t * funk,
455 : ulong * _dst_rec_head_idx, /* Pointer to the dst list head */
456 : ulong * _dst_rec_tail_idx, /* Pointer to the dst list tail */
457 : ulong dst_txn_idx, /* Transaction index of the merge destination */
458 : fd_funkier_txn_xid_t const * dst_xid, /* dst xid */
459 0 : ulong txn_idx ) { /* Transaction index of the records to merge */
460 0 : fd_wksp_t * wksp = fd_funkier_wksp( funk );
461 0 : fd_alloc_t * alloc = fd_funkier_alloc( funk, wksp );
462 0 : fd_funkier_rec_map_t rec_map = fd_funkier_rec_map( funk, wksp );
463 0 : fd_funkier_rec_pool_t rec_pool = fd_funkier_rec_pool( funk, wksp );
464 0 : fd_funkier_txn_pool_t txn_pool = fd_funkier_txn_pool( funk, wksp );
465 :
466 0 : fd_funkier_txn_t * txn = &txn_pool.ele[ txn_idx ];
467 0 : ulong rec_idx = txn->rec_head_idx;
468 0 : while( !fd_funkier_rec_idx_is_null( rec_idx ) ) {
469 0 : fd_funkier_rec_t * rec = &rec_pool.ele[ rec_idx ];
470 0 : ulong next_rec_idx = rec->next_idx;
471 :
472 : /* See if (dst_xid,key) already exists. */
473 0 : fd_funkier_xid_key_pair_t pair[1];
474 0 : fd_funkier_xid_key_pair_init( pair, dst_xid, rec->pair.key );
475 0 : for(;;) {
476 0 : fd_funkier_rec_map_query_t rec_query[1];
477 0 : int err = fd_funkier_rec_map_remove( &rec_map, pair, NULL, rec_query, FD_MAP_FLAG_BLOCKING );
478 0 : if( FD_UNLIKELY( err == FD_MAP_ERR_AGAIN ) ) continue;
479 0 : if( err == FD_MAP_ERR_KEY ) break;
480 0 : if( FD_UNLIKELY( err != FD_MAP_SUCCESS ) ) FD_LOG_CRIT(( "map corruption" ));
481 :
482 : /* Remove from the transaction */
483 0 : fd_funkier_rec_t * rec2 = fd_funkier_rec_map_query_ele( rec_query );
484 0 : ulong prev_idx = rec2->prev_idx;
485 0 : ulong next_idx = rec2->next_idx;
486 0 : if( fd_funkier_rec_idx_is_null( prev_idx ) ) {
487 0 : *_dst_rec_head_idx = next_idx;
488 0 : } else {
489 0 : rec_pool.ele[ prev_idx ].next_idx = next_idx;
490 0 : }
491 0 : if( fd_funkier_rec_idx_is_null( next_idx ) ) {
492 0 : *_dst_rec_tail_idx = prev_idx;
493 0 : } else {
494 0 : rec_pool.ele[ next_idx ].prev_idx = prev_idx;
495 0 : }
496 : /* Clean up value */
497 0 : fd_funkier_val_flush( rec2, alloc, wksp );
498 0 : rec2->txn_cidx = fd_funkier_txn_cidx( FD_FUNKIER_TXN_IDX_NULL );
499 0 : fd_funkier_rec_pool_release( &rec_pool, rec2, 1 );
500 0 : break;
501 0 : }
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_funkier_rec_query_global relies on this subtle
508 : property. */
509 :
510 0 : rec->pair.xid[0] = *dst_xid;
511 0 : rec->txn_cidx = fd_funkier_txn_cidx( dst_txn_idx );
512 :
513 0 : if( fd_funkier_rec_idx_is_null( *_dst_rec_head_idx ) ) {
514 0 : *_dst_rec_head_idx = rec_idx;
515 0 : rec->prev_idx = FD_FUNKIER_REC_IDX_NULL;
516 0 : } else {
517 0 : rec_pool.ele[ *_dst_rec_tail_idx ].next_idx = rec_idx;
518 0 : rec->prev_idx = *_dst_rec_tail_idx;
519 0 : }
520 0 : *_dst_rec_tail_idx = rec_idx;
521 0 : rec->next_idx = FD_FUNKIER_REC_IDX_NULL;
522 :
523 0 : rec_idx = next_rec_idx;
524 0 : }
525 :
526 0 : txn_pool.ele[ txn_idx ].rec_head_idx = FD_FUNKIER_REC_IDX_NULL;
527 0 : txn_pool.ele[ txn_idx ].rec_tail_idx = FD_FUNKIER_REC_IDX_NULL;
528 0 : }
529 :
530 : /* fd_funkier_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_FUNKIER_SUCCESS on success and an FD_FUNKIER_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_funkier_txn_publish_funk_child( fd_funkier_t * funk,
538 : ulong tag,
539 0 : ulong txn_idx ) {
540 :
541 : /* Apply the updates in txn to the last published transactions */
542 :
543 0 : fd_funkier_txn_update( funk, &funk->rec_head_idx, &funk->rec_tail_idx, FD_FUNKIER_TXN_IDX_NULL, fd_funkier_root( funk ), txn_idx );
544 :
545 : /* Cancel all competing transaction histories */
546 :
547 0 : ulong oldest_idx = fd_funkier_txn_oldest_sibling( funk, txn_idx );
548 0 : fd_funkier_txn_cancel_sibling_list( funk, tag, oldest_idx, txn_idx );
549 :
550 : /* Make all the children children of funk */
551 :
552 0 : fd_wksp_t * wksp = fd_funkier_wksp( funk );
553 0 : fd_funkier_txn_map_t txn_map = fd_funkier_txn_map( funk, wksp );
554 0 : fd_funkier_txn_pool_t txn_pool = fd_funkier_txn_pool( funk, wksp );
555 :
556 0 : ulong child_head_idx = fd_funkier_txn_idx( txn_pool.ele[ txn_idx ].child_head_cidx );
557 0 : ulong child_tail_idx = fd_funkier_txn_idx( txn_pool.ele[ txn_idx ].child_tail_cidx );
558 :
559 0 : ulong child_idx = child_head_idx;
560 0 : while( FD_UNLIKELY( !fd_funkier_txn_idx_is_null( child_idx ) ) ) { /* opt for incr pub */
561 0 : fd_funkier_txn_t * txn = &txn_pool.ele[ child_idx ];
562 0 : txn->tag = tag;
563 0 : txn->parent_cidx = fd_funkier_txn_cidx( FD_FUNKIER_TXN_IDX_NULL );
564 0 : child_idx = fd_funkier_txn_idx( txn->sibling_next_cidx );
565 0 : }
566 :
567 0 : funk->child_head_cidx = fd_funkier_txn_cidx( child_head_idx );
568 0 : funk->child_tail_cidx = fd_funkier_txn_cidx( child_tail_idx );
569 :
570 0 : fd_funkier_txn_xid_copy( funk->last_publish, fd_funkier_txn_xid( &txn_pool.ele[ txn_idx ] ) );
571 :
572 : /* Remove the mapping */
573 :
574 0 : fd_funkier_txn_map_query_t query[1];
575 0 : if( fd_funkier_txn_map_remove( &txn_map, funk->last_publish, NULL, query, FD_MAP_FLAG_BLOCKING ) == FD_MAP_SUCCESS ) {
576 0 : fd_funkier_txn_pool_release( &txn_pool, &txn_pool.ele[ txn_idx ], 1 );
577 0 : }
578 :
579 0 : return FD_FUNKIER_SUCCESS;
580 0 : }
581 :
582 : ulong
583 : fd_funkier_txn_publish( fd_funkier_t * funk,
584 : fd_funkier_txn_t * txn,
585 0 : int verbose ) {
586 :
587 : #ifdef FD_FUNKIER_HANDHOLDING
588 : if( FD_UNLIKELY( !funk ) ) {
589 : if( FD_UNLIKELY( verbose ) ) FD_LOG_WARNING(( "NULL funk" ));
590 : return 0UL;
591 : }
592 : if( FD_UNLIKELY( !fd_funkier_txn_valid( funk, txn ) ) ) {
593 : if( FD_UNLIKELY( verbose ) ) FD_LOG_WARNING(( "bad txn" ));
594 : return 0UL;
595 : }
596 : #else
597 0 : (void)verbose;
598 0 : #endif
599 :
600 0 : fd_wksp_t * wksp = fd_funkier_wksp( funk );
601 0 : fd_funkier_txn_pool_t txn_pool = fd_funkier_txn_pool( funk, wksp );
602 0 : ulong txn_idx = (ulong)(txn - txn_pool.ele);
603 :
604 0 : ulong tag = funk->cycle_tag++;
605 :
606 0 : ulong publish_stack_idx = FD_FUNKIER_TXN_IDX_NULL;
607 :
608 0 : for(;;) {
609 0 : fd_funkier_txn_t * txn2 = &txn_pool.ele[ txn_idx ];
610 0 : txn2->tag = tag;
611 :
612 : /* At this point, txn_idx is a transaction that needs to be
613 : published and has been tagged. If txn is a child of funk, we are
614 : ready to publish txn and everything on the publish stack. */
615 :
616 0 : ulong parent_idx = fd_funkier_txn_idx( txn2->parent_cidx );
617 0 : if( FD_LIKELY( fd_funkier_txn_idx_is_null( parent_idx ) ) ) break; /* opt for incr pub */
618 :
619 : /* txn_idx has a parent. Validate and tag it. Push txn to the
620 : publish stack and recurse into the parent. */
621 :
622 0 : txn2->stack_cidx = fd_funkier_txn_cidx( publish_stack_idx );
623 0 : publish_stack_idx = txn_idx;
624 :
625 0 : txn_idx = parent_idx;
626 0 : }
627 :
628 0 : ulong publish_cnt = 0UL;
629 :
630 0 : for(;;) {
631 :
632 : /* At this point, all the transactions we need to publish are
633 : tagged, txn is the next up publish funk and publish_stack has the
634 : transactions to follow in order by pop. We use a new tag for
635 : each publish as txn and its siblings we potentially visited in a
636 : previous iteration of this loop. */
637 :
638 0 : if( FD_UNLIKELY( fd_funkier_txn_publish_funk_child( funk, funk->cycle_tag++, txn_idx ) ) ) break;
639 0 : publish_cnt++;
640 :
641 0 : txn_idx = publish_stack_idx;
642 0 : if( FD_LIKELY( fd_funkier_txn_idx_is_null( txn_idx ) ) ) break; /* opt for incr pub */
643 0 : publish_stack_idx = fd_funkier_txn_idx( txn_pool.ele[ txn_idx ].stack_cidx );
644 0 : }
645 :
646 0 : return publish_cnt;
647 0 : }
648 :
649 : int
650 : fd_funkier_txn_publish_into_parent( fd_funkier_t * funk,
651 : fd_funkier_txn_t * txn,
652 0 : int verbose ) {
653 : #ifdef FD_FUNKIER_HANDHOLDING
654 : if( FD_UNLIKELY( !funk ) ) {
655 : if( FD_UNLIKELY( verbose ) ) FD_LOG_WARNING(( "NULL funk" ));
656 : return FD_FUNKIER_ERR_INVAL;
657 : }
658 : if( FD_UNLIKELY( !fd_funkier_txn_valid( funk, txn ) ) ) {
659 : if( FD_UNLIKELY( verbose ) ) FD_LOG_WARNING(( "bad txn" ));
660 : return 0UL;
661 : }
662 : #else
663 0 : (void)verbose;
664 0 : #endif
665 :
666 0 : fd_wksp_t * wksp = fd_funkier_wksp( funk );
667 0 : fd_funkier_txn_map_t txn_map = fd_funkier_txn_map( funk, fd_funkier_wksp( funk ) );
668 0 : fd_funkier_txn_pool_t txn_pool = fd_funkier_txn_pool( funk, wksp );
669 0 : ulong txn_idx = (ulong)(txn - txn_pool.ele);
670 :
671 0 : ulong oldest_idx = fd_funkier_txn_oldest_sibling( funk, txn_idx );
672 0 : fd_funkier_txn_cancel_sibling_list( funk, funk->cycle_tag++, oldest_idx, txn_idx );
673 :
674 0 : ulong parent_idx = fd_funkier_txn_idx( txn->parent_cidx );
675 0 : if( fd_funkier_txn_idx_is_null( parent_idx ) ) {
676 : /* Publish to root */
677 0 : fd_funkier_txn_update( funk, &funk->rec_head_idx, &funk->rec_tail_idx, FD_FUNKIER_TXN_IDX_NULL, fd_funkier_root( funk ), txn_idx );
678 : /* Inherit the children */
679 0 : funk->child_head_cidx = txn->child_head_cidx;
680 0 : funk->child_tail_cidx = txn->child_tail_cidx;
681 0 : } else {
682 0 : fd_funkier_txn_t * parent_txn = &txn_pool.ele[ parent_idx ];
683 0 : fd_funkier_txn_update( funk, &parent_txn->rec_head_idx, &parent_txn->rec_tail_idx, parent_idx, &parent_txn->xid, txn_idx );
684 : /* Inherit the children */
685 0 : parent_txn->child_head_cidx = txn->child_head_cidx;
686 0 : parent_txn->child_tail_cidx = txn->child_tail_cidx;
687 0 : }
688 :
689 : /* Adjust the parent pointers of the children to point to their grandparent */
690 0 : ulong child_idx = fd_funkier_txn_idx( txn->child_head_cidx );
691 0 : while( FD_UNLIKELY( !fd_funkier_txn_idx_is_null( child_idx ) ) ) {
692 0 : txn_pool.ele[ child_idx ].parent_cidx = fd_funkier_txn_cidx( parent_idx );
693 0 : child_idx = fd_funkier_txn_idx( txn_pool.ele[ child_idx ].sibling_next_cidx );
694 0 : }
695 :
696 0 : fd_funkier_txn_map_query_t query[1];
697 0 : if( fd_funkier_txn_map_remove( &txn_map, fd_funkier_txn_xid( txn ), NULL, query, FD_MAP_FLAG_BLOCKING ) == FD_MAP_SUCCESS ) {
698 0 : fd_funkier_txn_pool_release( &txn_pool, txn, 1 );
699 0 : }
700 :
701 0 : return FD_FUNKIER_SUCCESS;
702 0 : }
703 :
704 : /* Return the first record in a transaction. Returns NULL if the
705 : transaction has no records yet. */
706 :
707 : FD_FN_PURE fd_funkier_rec_t const *
708 : fd_funkier_txn_first_rec( fd_funkier_t * funk,
709 0 : fd_funkier_txn_t const * txn ) {
710 0 : ulong rec_idx;
711 0 : if( FD_UNLIKELY( NULL == txn ))
712 0 : rec_idx = funk->rec_head_idx;
713 0 : else
714 0 : rec_idx = txn->rec_head_idx;
715 0 : if( fd_funkier_rec_idx_is_null( rec_idx ) ) return NULL;
716 0 : fd_wksp_t * wksp = fd_funkier_wksp( funk );
717 0 : fd_funkier_rec_pool_t rec_pool = fd_funkier_rec_pool( funk, wksp );
718 0 : return rec_pool.ele + rec_idx;
719 0 : }
720 :
721 : FD_FN_PURE fd_funkier_rec_t const *
722 : fd_funkier_txn_last_rec( fd_funkier_t * funk,
723 0 : fd_funkier_txn_t const * txn ) {
724 0 : ulong rec_idx;
725 0 : if( FD_UNLIKELY( NULL == txn ))
726 0 : rec_idx = funk->rec_tail_idx;
727 0 : else
728 0 : rec_idx = txn->rec_tail_idx;
729 0 : if( fd_funkier_rec_idx_is_null( rec_idx ) ) return NULL;
730 0 : fd_wksp_t * wksp = fd_funkier_wksp( funk );
731 0 : fd_funkier_rec_pool_t rec_pool = fd_funkier_rec_pool( funk, wksp );
732 0 : return rec_pool.ele + rec_idx;
733 0 : }
734 :
735 : /* Return the next record in a transaction. Returns NULL if the
736 : transaction has no more records. */
737 :
738 : fd_funkier_rec_t const *
739 : fd_funkier_txn_next_rec( fd_funkier_t * funk,
740 0 : fd_funkier_rec_t const * rec ) {
741 0 : ulong rec_idx = rec->next_idx;
742 0 : if( fd_funkier_rec_idx_is_null( rec_idx ) ) return NULL;
743 0 : fd_wksp_t * wksp = fd_funkier_wksp( funk );
744 0 : fd_funkier_rec_pool_t rec_pool = fd_funkier_rec_pool( funk, wksp );
745 0 : return rec_pool.ele + rec_idx;
746 0 : }
747 :
748 : fd_funkier_rec_t const *
749 : fd_funkier_txn_prev_rec( fd_funkier_t * funk,
750 0 : fd_funkier_rec_t const * rec ) {
751 0 : ulong rec_idx = rec->prev_idx;
752 0 : if( fd_funkier_rec_idx_is_null( rec_idx ) ) return NULL;
753 0 : fd_wksp_t * wksp = fd_funkier_wksp( funk );
754 0 : fd_funkier_rec_pool_t rec_pool = fd_funkier_rec_pool( funk, wksp );
755 0 : return rec_pool.ele + rec_idx;
756 0 : }
757 :
758 : fd_funkier_txn_xid_t
759 0 : fd_funkier_generate_xid(void) {
760 0 : fd_funkier_txn_xid_t xid;
761 0 : static FD_TL ulong seq = 0;
762 0 : xid.ul[0] =
763 0 : (fd_log_cpu_id() + 1U)*3138831853UL +
764 0 : (fd_log_thread_id() + 1U)*9180195821UL +
765 0 : (++seq)*6208101967UL;
766 0 : xid.ul[1] = ((ulong)fd_tickcount())*2810745731UL;
767 0 : return xid;
768 0 : }
769 :
770 : static void
771 0 : fd_funkier_txn_all_iter_skip_nulls( fd_funkier_txn_all_iter_t * iter ) {
772 0 : if( iter->chain_idx == iter->chain_cnt ) return;
773 0 : while( fd_funkier_txn_map_iter_done( iter->txn_map_iter ) ) {
774 0 : if( ++(iter->chain_idx) == iter->chain_cnt ) break;
775 0 : iter->txn_map_iter = fd_funkier_txn_map_iter( &iter->txn_map, iter->chain_idx );
776 0 : }
777 0 : }
778 :
779 : void
780 0 : fd_funkier_txn_all_iter_new( fd_funkier_t * funk, fd_funkier_txn_all_iter_t * iter ) {
781 0 : fd_wksp_t * wksp = fd_funkier_wksp( funk );
782 0 : iter->txn_map = fd_funkier_txn_map( funk, wksp );
783 0 : iter->chain_cnt = fd_funkier_txn_map_chain_cnt( &iter->txn_map );
784 0 : iter->chain_idx = 0;
785 0 : iter->txn_map_iter = fd_funkier_txn_map_iter( &iter->txn_map, 0 );
786 0 : fd_funkier_txn_all_iter_skip_nulls( iter );
787 0 : }
788 :
789 : int
790 0 : fd_funkier_txn_all_iter_done( fd_funkier_txn_all_iter_t * iter ) {
791 0 : return ( iter->chain_idx == iter->chain_cnt );
792 0 : }
793 :
794 : void
795 0 : fd_funkier_txn_all_iter_next( fd_funkier_txn_all_iter_t * iter ) {
796 0 : iter->txn_map_iter = fd_funkier_txn_map_iter_next( iter->txn_map_iter );
797 0 : fd_funkier_txn_all_iter_skip_nulls( iter );
798 0 : }
799 :
800 : fd_funkier_txn_t const *
801 0 : fd_funkier_txn_all_iter_ele_const( fd_funkier_txn_all_iter_t * iter ) {
802 0 : return fd_funkier_txn_map_iter_ele_const( iter->txn_map_iter );
803 0 : }
804 :
805 : fd_funkier_txn_t *
806 0 : fd_funkier_txn_all_iter_ele( fd_funkier_txn_all_iter_t * iter ) {
807 0 : return fd_funkier_txn_map_iter_ele( iter->txn_map_iter );
808 0 : }
809 :
810 : #ifdef FD_FUNKIER_HANDHOLDING
811 : int
812 : fd_funkier_txn_verify( fd_funkier_t * funk ) {
813 : fd_wksp_t * wksp = fd_funkier_wksp( funk );
814 : fd_funkier_txn_map_t txn_map = fd_funkier_txn_map( funk, wksp );
815 : fd_funkier_txn_pool_t txn_pool = fd_funkier_txn_pool( funk, wksp );
816 : ulong txn_max = funk->txn_max;
817 :
818 : ulong funk_child_head_idx = fd_funkier_txn_idx( funk->child_head_cidx ); /* Previously verified */
819 : ulong funk_child_tail_idx = fd_funkier_txn_idx( funk->child_tail_cidx ); /* Previously verified */
820 :
821 : fd_funkier_txn_xid_t const * last_publish = funk->last_publish; /* Previously verified */
822 :
823 : # define TEST(c) do { \
824 : if( FD_UNLIKELY( !(c) ) ) { FD_LOG_WARNING(( "FAIL: %s", #c )); return FD_FUNKIER_ERR_INVAL; } \
825 : } while(0)
826 :
827 : # define IS_VALID( idx ) ( (idx==FD_FUNKIER_TXN_IDX_NULL) || \
828 : ((idx<txn_max) && (!fd_funkier_txn_xid_eq( fd_funkier_txn_xid( &txn_pool.ele[idx] ), last_publish ))) )
829 :
830 : TEST( !fd_funkier_txn_map_verify( &txn_map ) );
831 : TEST( !fd_funkier_txn_pool_verify( &txn_pool ) );
832 :
833 : /* Tag all transactions as not visited yet */
834 :
835 : for( ulong txn_idx=0UL; txn_idx<txn_max; txn_idx++ ) txn_pool.ele[ txn_idx ].tag = 0UL;
836 :
837 : /* Visit all transactions in preparation, traversing from oldest to
838 : youngest. */
839 :
840 : do {
841 :
842 : /* Push all children of funk to the stack */
843 :
844 : ulong stack_idx = FD_FUNKIER_TXN_IDX_NULL;
845 : ulong child_idx = funk_child_head_idx;
846 : while( !fd_funkier_txn_idx_is_null( child_idx ) ) {
847 :
848 : /* Make sure valid idx, not tagged (detects cycles) and child
849 : knows it is a child of funk. Then tag as visited / in-prep,
850 : push to stack and update prep_cnt */
851 :
852 : TEST( IS_VALID( child_idx ) );
853 : TEST( !txn_pool.ele[ child_idx ].tag );
854 : TEST( fd_funkier_txn_idx_is_null( fd_funkier_txn_idx( txn_pool.ele[ child_idx ].parent_cidx ) ) );
855 : txn_pool.ele[ child_idx ].tag = 1UL;
856 : txn_pool.ele[ child_idx ].stack_cidx = fd_funkier_txn_cidx( stack_idx );
857 : stack_idx = child_idx;
858 :
859 : ulong next_idx = fd_funkier_txn_idx( txn_pool.ele[ child_idx ].sibling_next_cidx );
860 : if( !fd_funkier_txn_idx_is_null( next_idx ) ) TEST( fd_funkier_txn_idx( txn_pool.ele[ next_idx ].sibling_prev_cidx )==child_idx );
861 : child_idx = next_idx;
862 : }
863 :
864 : while( !fd_funkier_txn_idx_is_null( stack_idx ) ) {
865 :
866 : /* Pop the next transaction to traverse */
867 :
868 : ulong txn_idx = stack_idx;
869 : stack_idx = fd_funkier_txn_idx( txn_pool.ele[ txn_idx ].stack_cidx );
870 :
871 : /* Push all children of txn to the stack */
872 :
873 : ulong child_idx = fd_funkier_txn_idx( txn_pool.ele[ txn_idx ].child_head_cidx );
874 : while( !fd_funkier_txn_idx_is_null( child_idx ) ) {
875 :
876 : /* Make sure valid idx, not tagged (detects cycles) and child
877 : knows it is a child of txn_idx. Then tag as visited /
878 : in-prep, push to stack and update prep_cnt */
879 :
880 : TEST( IS_VALID( child_idx ) );
881 : TEST( !txn_pool.ele[ child_idx ].tag );
882 : TEST( fd_funkier_txn_idx( txn_pool.ele[ child_idx ].parent_cidx )==txn_idx );
883 : txn_pool.ele[ child_idx ].tag = 1UL;
884 : txn_pool.ele[ child_idx ].stack_cidx = fd_funkier_txn_cidx( stack_idx );
885 : stack_idx = child_idx;
886 :
887 : ulong next_idx = fd_funkier_txn_idx( txn_pool.ele[ child_idx ].sibling_next_cidx );
888 : if( !fd_funkier_txn_idx_is_null( next_idx ) ) TEST( fd_funkier_txn_idx( txn_pool.ele[ next_idx ].sibling_prev_cidx )==child_idx );
889 : child_idx = next_idx;
890 : }
891 : }
892 :
893 : } while(0);
894 :
895 : /* Do it again with a youngest to oldest traversal to test reverse
896 : link integrity */
897 :
898 : do {
899 :
900 : /* Push all children of funk to the stack */
901 :
902 : ulong stack_idx = FD_FUNKIER_TXN_IDX_NULL;
903 : ulong child_idx = funk_child_tail_idx;
904 : while( !fd_funkier_txn_idx_is_null( child_idx ) ) {
905 :
906 : /* Make sure valid idx, tagged as visited above (detects cycles)
907 : and child knows it is a child of funk. Then tag as visited /
908 : in-prep, push to stack and update prep_cnt */
909 :
910 : TEST( IS_VALID( child_idx ) );
911 : TEST( txn_pool.ele[ child_idx ].tag==1UL );
912 : TEST( fd_funkier_txn_idx_is_null( fd_funkier_txn_idx( txn_pool.ele[ child_idx ].parent_cidx ) ) );
913 : txn_pool.ele[ child_idx ].tag = 2UL;
914 : txn_pool.ele[ child_idx ].stack_cidx = fd_funkier_txn_cidx( stack_idx );
915 : stack_idx = child_idx;
916 :
917 : ulong prev_idx = fd_funkier_txn_idx( txn_pool.ele[ child_idx ].sibling_prev_cidx );
918 : if( !fd_funkier_txn_idx_is_null( prev_idx ) ) TEST( fd_funkier_txn_idx( txn_pool.ele[ prev_idx ].sibling_next_cidx )==child_idx );
919 : child_idx = prev_idx;
920 : }
921 :
922 : while( !fd_funkier_txn_idx_is_null( stack_idx ) ) {
923 :
924 : /* Pop the next transaction to traverse */
925 :
926 : ulong txn_idx = stack_idx;
927 : stack_idx = fd_funkier_txn_idx( txn_pool.ele[ txn_idx ].stack_cidx );
928 :
929 : /* Push all children of txn to the stack */
930 :
931 : ulong child_idx = fd_funkier_txn_idx( txn_pool.ele[ txn_idx ].child_tail_cidx );
932 : while( !fd_funkier_txn_idx_is_null( child_idx ) ) {
933 :
934 : /* Make sure valid idx, tagged as visited above (detects cycles)
935 : and child knows it is a child of txn_idx. Then, tag as
936 : visited / in-prep, push to stack and update prep_cnt */
937 :
938 : TEST( IS_VALID( child_idx ) );
939 : TEST( txn_pool.ele[ child_idx ].tag==1UL );
940 : TEST( fd_funkier_txn_idx( txn_pool.ele[ child_idx ].parent_cidx )==txn_idx );
941 : txn_pool.ele[ child_idx ].tag = 2UL;
942 : txn_pool.ele[ child_idx ].stack_cidx = fd_funkier_txn_cidx( stack_idx );
943 : stack_idx = child_idx;
944 :
945 : ulong prev_idx = fd_funkier_txn_idx( txn_pool.ele[ child_idx ].sibling_prev_cidx );
946 : if( !fd_funkier_txn_idx_is_null( prev_idx ) ) TEST( fd_funkier_txn_idx( txn_pool.ele[ prev_idx ].sibling_next_cidx )==child_idx );
947 : child_idx = prev_idx;
948 : }
949 : }
950 : } while(0);
951 :
952 : # undef IS_VALID
953 : # undef TEST
954 :
955 : return FD_FUNKIER_SUCCESS;
956 : }
957 :
958 : int
959 : fd_funkier_txn_valid( fd_funkier_t * funk, fd_funkier_txn_t const * txn ) {
960 : fd_wksp_t * wksp = fd_funkier_wksp( funk );
961 : fd_funkier_txn_pool_t txn_pool = fd_funkier_txn_pool( funk, wksp );
962 : ulong txn_idx = (ulong)(txn - txn_pool.ele);
963 : if( txn_idx >= funk->txn_max || txn != txn_idx + txn_pool.ele ) return 0;
964 : fd_funkier_txn_map_t txn_map = fd_funkier_txn_map( funk, wksp );
965 : fd_funkier_txn_map_query_t query[1];
966 : if( FD_UNLIKELY( fd_funkier_txn_map_query_try( &txn_map, &txn->xid, NULL, query ) ) ) return 0;
967 : if( fd_funkier_txn_map_query_ele( query ) != txn ) return 0;
968 : return 1;
969 : }
970 :
971 : #endif
|
