Line data Source code
1 : #include "fd_funk.h"
2 :
3 : /* Provide the actual transaction map implementation */
4 :
5 : #define MAP_NAME fd_funk_txn_map
6 1104027921 : #define MAP_T fd_funk_txn_t
7 : #define MAP_KEY_T fd_funk_txn_xid_t
8 1592718 : #define MAP_KEY xid
9 : #define MAP_KEY_EQ(k0,k1) fd_funk_txn_xid_eq((k0),(k1))
10 779049543 : #define MAP_KEY_HASH(k0,seed) fd_funk_txn_xid_hash((k0),(seed))
11 : #define MAP_KEY_COPY(kd,ks) fd_funk_txn_xid_copy((kd),(ks))
12 744567846 : #define MAP_NEXT map_next
13 1534057560 : #define MAP_HASH map_hash
14 30 : #define MAP_MAGIC (0xf173da2ce7172db0UL) /* Firedancer trn db version 0 */
15 : #define MAP_IMPL_STYLE 2
16 : #define MAP_MEMOIZE 1
17 : #include "../util/tmpl/fd_map_giant.c"
18 :
19 : /* As described in fd_funk_txn.h, like the extensive tests in verify
20 : (which, by its very nature, is called on maps whose integrity is
21 : unclear to the caller), these have been fortified again memory
22 : corruption (accidental or deliberate) by doing out of bounds memory
23 : access detection and cycle (infinite loop) detection in all the
24 : various operations below.
25 :
26 : This is debatably overkill but, given this code is the pointy end of
27 : the stick for keeping transaction histories clean (i.e. cancelling a
28 : wrong transaction could lose information and publishing a wrong
29 : transaction is even worse), the overhead for the detection is
30 : minimal, and these operations aren't particularly performance
31 : critical anyway, seems a more-than-worthwhile safeguard. Likewise,
32 : it also guarantees strict algo overheads of these in the face of
33 : corruption.
34 :
35 : When there is a corruption issue detected realtime, it is prima facie
36 : evidence of either software bug, hardware fault or compromised
37 : process. In all cases, these functions will refuse to proceed
38 : further and abort with FD_LOG_CRIT to minimize the blast radius of
39 : possible corruption and give the user as much details (stack trace
40 : and core) to diagnose the source of the issue. This handling is
41 : mostly isolated to the below macros and thus easy to modify or
42 : disable.
43 :
44 : The corruption detection works by ensuring all map indices are in
45 : bounds and then applying a unique tag during various map traversals
46 : such that operations can detected if a transaction has already been
47 : encountered earlier in the traversal (and thus will create a
48 : cycle/infinite loop) in the shortest possible algorithm overhead to
49 : detect such a cycle. */
50 :
51 1592718 : #define ASSERT_IN_MAP( txn_idx ) do { \
52 1592718 : if( FD_UNLIKELY( txn_idx>=txn_max ) ) \
53 1592718 : FD_LOG_CRIT(( "memory corruption detected (bad_idx)" )); \
54 1592718 : } while(0)
55 :
56 4715574 : #define ASSERT_IN_PREP( txn_idx ) do { \
57 4715574 : if( FD_UNLIKELY( txn_idx>=txn_max ) ) \
58 4715574 : FD_LOG_CRIT(( "memory corruption detected (bad_idx)" )); \
59 4715574 : if( FD_UNLIKELY( !fd_funk_txn_map_query( map, fd_funk_txn_xid( &map[ txn_idx ] ), NULL ) ) ) \
60 4715574 : FD_LOG_CRIT(( "memory corruption detected (not in prep)" )); \
61 4715574 : } while(0)
62 :
63 1824210 : #define ASSERT_UNTAGGED( txn_idx ) do { \
64 1824210 : if( FD_UNLIKELY( map[ txn_idx ].tag==tag ) ) \
65 1824210 : FD_LOG_CRIT(( "memory corruption detected (cycle)" )); \
66 1824210 : } while(0)
67 :
68 : fd_funk_txn_t *
69 : fd_funk_txn_prepare( fd_funk_t * funk,
70 : fd_funk_txn_t * parent,
71 : fd_funk_txn_xid_t const * xid,
72 2829093 : int verbose ) {
73 :
74 2829093 : if( FD_UNLIKELY( !funk ) ) {
75 196464 : if( FD_UNLIKELY( verbose ) ) FD_LOG_WARNING(( "NULL funk" ));
76 196464 : return NULL;
77 196464 : }
78 2632629 : fd_funk_check_write( funk );
79 :
80 2632629 : fd_funk_txn_t * map = fd_funk_txn_map( funk, fd_funk_wksp( funk ) );
81 :
82 2632629 : if( FD_UNLIKELY( fd_funk_txn_map_is_full( map ) ) ) {
83 24 : if( FD_UNLIKELY( verbose ) ) FD_LOG_WARNING(( "too many transactions in preparation" ));
84 24 : return NULL;
85 24 : }
86 :
87 2632605 : ulong txn_max = funk->txn_max;
88 :
89 2632605 : ulong parent_idx;
90 2632605 : uint * _child_head_cidx;
91 2632605 : uint * _child_tail_cidx;
92 :
93 2632605 : if( FD_LIKELY( !parent ) ) { /* opt for incr pub */
94 :
95 1035756 : parent_idx = FD_FUNK_TXN_IDX_NULL;
96 :
97 1035756 : _child_head_cidx = &funk->child_head_cidx;
98 1035756 : _child_tail_cidx = &funk->child_tail_cidx;
99 :
100 1596849 : } else {
101 :
102 1596849 : parent_idx = (ulong)(parent - map);
103 :
104 1596849 : if( FD_UNLIKELY( (parent_idx>=txn_max) /* Out of map */ | (parent!=(map+parent_idx)) /* Bad alignment */ ) ) {
105 196461 : if( FD_UNLIKELY( verbose ) ) FD_LOG_WARNING(( "parent is not a funk transaction" ));
106 196461 : return NULL;
107 196461 : }
108 :
109 1400388 : if( FD_UNLIKELY( !fd_funk_txn_map_query( map, fd_funk_txn_xid( parent ), NULL ) ) ) {
110 188382 : if( FD_UNLIKELY( verbose ) ) FD_LOG_WARNING(( "parent is not in preparation" ));
111 188382 : return NULL;
112 188382 : }
113 :
114 1212006 : _child_head_cidx = &parent->child_head_cidx;
115 1212006 : _child_tail_cidx = &parent->child_tail_cidx;
116 :
117 1212006 : }
118 :
119 2247762 : if( FD_UNLIKELY( !xid ) ) {
120 196461 : if( FD_UNLIKELY( verbose ) ) FD_LOG_WARNING(( "NULL xid" ));
121 196461 : return NULL;
122 196461 : }
123 :
124 2051301 : if( FD_UNLIKELY( fd_funk_txn_xid_eq_root( xid ) ) ) {
125 6 : if( FD_UNLIKELY( verbose ) ) FD_LOG_WARNING(( "xid is the root" ));
126 6 : return NULL;
127 6 : }
128 :
129 2051295 : if( FD_UNLIKELY( fd_funk_txn_xid_eq( xid, funk->last_publish ) ) ) {
130 196455 : if( FD_UNLIKELY( verbose ) ) FD_LOG_WARNING(( "xid is the last published" ));
131 196455 : return NULL;
132 196455 : }
133 :
134 1854840 : if( FD_UNLIKELY( fd_funk_txn_map_query( map, xid, NULL ) ) ) {
135 262122 : if( FD_UNLIKELY( verbose ) ) FD_LOG_WARNING(( "id already a transaction" ));
136 262122 : return NULL;
137 262122 : }
138 :
139 : /* Get a new transaction from the map */
140 :
141 1592718 : fd_funk_txn_t * txn = fd_funk_txn_map_insert( map, xid );
142 1592718 : ulong txn_idx = (ulong)(txn - map);
143 1592718 : ASSERT_IN_MAP( txn_idx );
144 :
145 : /* Join the family */
146 :
147 1592718 : ulong sibling_prev_idx = fd_funk_txn_idx( *_child_tail_cidx );
148 :
149 1592718 : int first_born = fd_funk_txn_idx_is_null( sibling_prev_idx );
150 1592718 : if( FD_UNLIKELY( !first_born ) ) ASSERT_IN_PREP( sibling_prev_idx ); /* opt for non-compete */
151 :
152 1592718 : txn->parent_cidx = fd_funk_txn_cidx( parent_idx );
153 1592718 : txn->child_head_cidx = fd_funk_txn_cidx( FD_FUNK_TXN_IDX_NULL );
154 1592718 : txn->child_tail_cidx = fd_funk_txn_cidx( FD_FUNK_TXN_IDX_NULL );
155 1592718 : txn->sibling_prev_cidx = fd_funk_txn_cidx( sibling_prev_idx );
156 1592718 : txn->sibling_next_cidx = fd_funk_txn_cidx( FD_FUNK_TXN_IDX_NULL );
157 1592718 : txn->stack_cidx = fd_funk_txn_cidx( FD_FUNK_TXN_IDX_NULL );
158 1592718 : txn->tag = 0UL;
159 :
160 1592718 : txn->rec_head_idx = FD_FUNK_REC_IDX_NULL;
161 1592718 : txn->rec_tail_idx = FD_FUNK_REC_IDX_NULL;
162 :
163 : /* TODO: consider branchless impl */
164 1592718 : if( FD_LIKELY( first_born ) ) *_child_head_cidx = fd_funk_txn_cidx( txn_idx ); /* opt for non-compete */
165 796092 : else map[ sibling_prev_idx ].sibling_next_cidx = fd_funk_txn_cidx( txn_idx );
166 :
167 1592718 : *_child_tail_cidx = fd_funk_txn_cidx( txn_idx );
168 :
169 1592718 : return txn;
170 1592718 : }
171 :
172 : /* fd_funk_txn_cancel_childless cancels a transaction that is known
173 : to be childless. Callers have already validated our input arguments.
174 : Assumes that cancelling in the app can't fail but that could be
175 : straightforward to support by giving this an error and plumbing
176 : through to abort the overall cancel operation when it hits a error. */
177 :
178 : static void
179 : fd_funk_txn_cancel_childless( fd_funk_t * funk,
180 : fd_funk_txn_t * map,
181 : ulong txn_max,
182 1289097 : ulong txn_idx ) {
183 :
184 1289097 : fd_funk_check_write( funk );
185 :
186 : /* Remove all records used by this transaction. Note that we don't
187 : need to bother doing all the individual removal operations as we
188 : are removing the whole list. We do reset the record transaction
189 : idx with NULL though we can detect cycles as soon as possible
190 : and abort. */
191 :
192 1289097 : fd_wksp_t * wksp = fd_funk_wksp ( funk );
193 1289097 : fd_alloc_t * alloc = fd_funk_alloc ( funk, wksp );
194 1289097 : fd_funk_rec_t * rec_map = fd_funk_rec_map( funk, wksp );
195 1289097 : ulong rec_max = funk->rec_max;
196 :
197 1289097 : ulong rec_idx = map[ txn_idx ].rec_head_idx;
198 4873959 : while( !fd_funk_rec_idx_is_null( rec_idx ) ) {
199 :
200 3584862 : if( FD_UNLIKELY( rec_idx>=rec_max ) ) FD_LOG_CRIT(( "memory corruption detected (bad idx)" ));
201 3584862 : if( FD_UNLIKELY( fd_funk_txn_idx( rec_map[ rec_idx ].txn_cidx )!=txn_idx ) )
202 0 : FD_LOG_CRIT(( "memory corruption detected (cycle or bad idx)" ));
203 :
204 3584862 : ulong next_idx = rec_map[ rec_idx ].next_idx;
205 3584862 : rec_map[ rec_idx ].txn_cidx = fd_funk_txn_cidx( FD_FUNK_TXN_IDX_NULL );
206 :
207 3584862 : fd_funk_val_flush( &rec_map[ rec_idx ], alloc, wksp );
208 3584862 : fd_funk_rec_map_remove( rec_map, fd_funk_rec_pair( &rec_map[ rec_idx ] ) );
209 :
210 3584862 : rec_idx = next_idx;
211 3584862 : }
212 :
213 : /* Leave the family */
214 :
215 1289097 : ulong sibling_prev_idx = fd_funk_txn_idx( map[ txn_idx ].sibling_prev_cidx );
216 1289097 : ulong sibling_next_idx = fd_funk_txn_idx( map[ txn_idx ].sibling_next_cidx );
217 :
218 : /* TODO: Consider branchless impl */
219 :
220 1289097 : if( FD_LIKELY( fd_funk_txn_idx_is_null( sibling_prev_idx ) ) ) { /* opt for non-compete */
221 636330 : ulong parent_idx = fd_funk_txn_idx( map[ txn_idx ].parent_cidx );
222 636330 : if( FD_LIKELY( fd_funk_txn_idx_is_null( parent_idx ) ) ) { /* No older sib and is a funk child, opt for incr pub */
223 166380 : funk->child_head_cidx = fd_funk_txn_cidx( sibling_next_idx );
224 469950 : } else { /* No older sib and has parent */
225 469950 : ASSERT_IN_PREP( parent_idx );
226 469950 : map[ parent_idx ].child_head_cidx = fd_funk_txn_cidx( sibling_next_idx );
227 469950 : }
228 652767 : } else { /* Has older sib */
229 652767 : ASSERT_IN_PREP( sibling_prev_idx );
230 652767 : map[ sibling_prev_idx ].sibling_next_cidx = fd_funk_txn_cidx( sibling_next_idx );
231 652767 : }
232 :
233 1289097 : if( FD_LIKELY( fd_funk_txn_idx_is_null( sibling_next_idx ) ) ) { /* opt for non-compete */
234 1052781 : ulong parent_idx = fd_funk_txn_idx( map[ txn_idx ].parent_cidx );
235 1052781 : if( FD_LIKELY( fd_funk_txn_idx_is_null( parent_idx ) ) ) { /* No younger sib and is a funk child, opt for incr pub */
236 340134 : funk->child_tail_cidx = fd_funk_txn_cidx( sibling_prev_idx );
237 712647 : } else { /* No younger sib and has parent */
238 712647 : ASSERT_IN_PREP( parent_idx );
239 712647 : map[ parent_idx ].child_tail_cidx = fd_funk_txn_cidx( sibling_prev_idx );
240 712647 : }
241 1052781 : } else { /* Has younger sib */
242 236316 : ASSERT_IN_PREP( sibling_next_idx );
243 236316 : map[ sibling_next_idx ].sibling_prev_cidx = fd_funk_txn_cidx( sibling_prev_idx );
244 236316 : }
245 :
246 1289097 : fd_funk_txn_map_remove( map, fd_funk_txn_xid( &map[ txn_idx ] ) );
247 1289097 : }
248 :
249 : /* fd_funk_txn_cancel_family cancels a transaction and all its
250 : descendants in a tree-depth-first-ordered sense from youngest to
251 : oldest. Callers have already validated our input arguments. Returns
252 : the number of transactions canceled. */
253 :
254 : static ulong
255 : fd_funk_txn_cancel_family( fd_funk_t * funk,
256 : fd_funk_txn_t * map,
257 : ulong txn_max,
258 : ulong tag,
259 624429 : ulong txn_idx ) {
260 624429 : ulong cancel_cnt = 0UL;
261 :
262 624429 : map[ txn_idx ].tag = tag;
263 :
264 624429 : ulong parent_stack_idx = FD_FUNK_TXN_IDX_NULL;
265 :
266 1953765 : for(;;) {
267 :
268 : /* At this point, txn_idx appears to be valid and has been tagged. */
269 :
270 1953765 : ulong youngest_idx = fd_funk_txn_idx( map[ txn_idx ].child_tail_cidx );
271 1953765 : if( FD_LIKELY( fd_funk_txn_idx_is_null( youngest_idx ) ) ) { /* txn is is childless, opt for incr pub */
272 :
273 1289097 : fd_funk_txn_cancel_childless( funk, map, txn_max, txn_idx ); /* If this can fail, return cancel_cnt here on fail */
274 1289097 : cancel_cnt++;
275 :
276 1289097 : txn_idx = parent_stack_idx; /* Pop the parent stack */
277 1289097 : if( FD_LIKELY( fd_funk_txn_idx_is_null( txn_idx ) ) ) break; /* If stack is empty, we are done, opt for incr pub */
278 664668 : parent_stack_idx = fd_funk_txn_idx( map[ txn_idx ].stack_cidx );
279 664668 : continue;
280 1289097 : }
281 :
282 : /* txn has at least one child and the youngest is youngest_idx. Tag
283 : the youngest child, push txn onto the parent stack and recurse
284 : into the youngest child. */
285 :
286 664668 : ASSERT_IN_PREP ( youngest_idx );
287 664668 : ASSERT_UNTAGGED( youngest_idx );
288 664668 : map[ youngest_idx ].tag = tag;
289 :
290 664668 : map[ txn_idx ].stack_cidx = fd_funk_txn_cidx( parent_stack_idx );
291 664668 : parent_stack_idx = txn_idx;
292 :
293 664668 : txn_idx = youngest_idx;
294 664668 : }
295 :
296 624429 : return cancel_cnt;
297 624429 : }
298 :
299 : ulong
300 : fd_funk_txn_cancel( fd_funk_t * funk,
301 : fd_funk_txn_t * txn,
302 1327062 : int verbose ) {
303 :
304 1327062 : if( FD_UNLIKELY( !funk ) ) {
305 196464 : if( FD_UNLIKELY( verbose ) ) FD_LOG_WARNING(( "NULL funk" ));
306 196464 : return 0UL;
307 196464 : }
308 :
309 1130598 : fd_funk_txn_t * map = fd_funk_txn_map( funk, fd_funk_wksp( funk ) );
310 :
311 1130598 : ulong txn_max = funk->txn_max;
312 :
313 1130598 : ulong txn_idx = (ulong)(txn - map);
314 :
315 1130598 : if( FD_UNLIKELY( (txn_idx>=txn_max) /* Out of map (incl NULL) */ | (txn!=(map+txn_idx)) /* Bad alignment */ ) ) {
316 786258 : if( FD_UNLIKELY( verbose ) ) FD_LOG_WARNING(( "txn is not a funk transaction" ));
317 786258 : return 0UL;
318 786258 : }
319 :
320 344340 : if( FD_UNLIKELY( !fd_funk_txn_map_query( map, fd_funk_txn_xid( txn ), NULL ) ) ) {
321 188382 : if( FD_UNLIKELY( verbose ) ) FD_LOG_WARNING(( "txn is not in preparation" ));
322 188382 : return 0UL;
323 188382 : }
324 :
325 155958 : return fd_funk_txn_cancel_family( funk, map, txn_max, funk->cycle_tag++, txn_idx );
326 344340 : }
327 :
328 : /* fd_funk_txn_oldest_sibling returns the index of the oldest sibling
329 : in txn_idx's family. Callers have already validated our input
330 : arguments. The caller should validate the return index. */
331 :
332 : static inline ulong
333 : fd_funk_txn_oldest_sibling( fd_funk_t * funk,
334 : fd_funk_txn_t * map,
335 : ulong txn_max,
336 303579 : ulong txn_idx ) {
337 :
338 303579 : ulong parent_idx = fd_funk_txn_idx( map[ txn_idx ].parent_cidx );
339 :
340 303579 : if( FD_LIKELY( fd_funk_txn_idx_is_null( parent_idx ) ) ) return fd_funk_txn_idx( funk->child_head_cidx ); /* opt for incr pub */
341 :
342 23592 : ASSERT_IN_PREP( parent_idx );
343 :
344 23592 : return fd_funk_txn_idx( map[ parent_idx ].child_head_cidx );
345 23592 : }
346 :
347 : /* fd_funk_txn_cancel_sibling_list cancels siblings from sibling_idx down
348 : to the youngest sibling inclusive in the order from youngest to
349 : sibling_idx. Callers have already validated our input arguments
350 : except sibling_idx. Returns the number of cancelled transactions
351 : (should be at least 1). If any sibling is skip_idx, it will be not
352 : be cancelled but still tagged as visited. Passing
353 : FD_FUNK_TXN_IDX_NULL for skip_idx will cancel all siblings from
354 : sibling_idx to the youngest inclusive. */
355 :
356 : static ulong
357 : fd_funk_txn_cancel_sibling_list( fd_funk_t * funk,
358 : fd_funk_txn_t * map,
359 : ulong txn_max,
360 : ulong tag,
361 : ulong sibling_idx,
362 303579 : ulong skip_idx ) {
363 :
364 303579 : ulong cancel_stack_idx = FD_FUNK_TXN_IDX_NULL;
365 :
366 : /* Push siblings_idx and its younger siblings inclusive (skipping
367 : sibling skip_idx if encounter) onto the cancel stack from oldest to
368 : youngest (such that we cancel youngest to oldest). */
369 :
370 772050 : for(;;) {
371 :
372 : /* At this point, sibling_idx is a sibling we might want to add to
373 : the sibling stack. Validate and tag it. */
374 :
375 772050 : ASSERT_IN_PREP ( sibling_idx );
376 772050 : ASSERT_UNTAGGED( sibling_idx );
377 772050 : map[ sibling_idx ].tag = tag;
378 :
379 772050 : if( FD_UNLIKELY( sibling_idx!=skip_idx ) ) { /* Not skip_idx so push onto the cancel stack, opt for non-compete */
380 468471 : map[ sibling_idx ].stack_cidx = fd_funk_txn_cidx( cancel_stack_idx );
381 468471 : cancel_stack_idx = sibling_idx;
382 468471 : }
383 :
384 772050 : ulong younger_idx = fd_funk_txn_idx( map[ sibling_idx ].sibling_next_cidx );
385 772050 : if( FD_LIKELY( fd_funk_txn_idx_is_null( younger_idx ) ) ) break; /* opt for non-compete */
386 468471 : sibling_idx = younger_idx;
387 :
388 468471 : }
389 :
390 : /* Cancel all transactions and their descendants on the cancel stack */
391 :
392 303579 : ulong cancel_cnt = 0UL;
393 :
394 772050 : while( !fd_funk_txn_idx_is_null( cancel_stack_idx ) ) { /* TODO: peel first iter to make more predictable? */
395 468471 : ulong sibling_idx = cancel_stack_idx;
396 468471 : cancel_stack_idx = fd_funk_txn_idx( map[ sibling_idx ].stack_cidx );
397 :
398 468471 : cancel_cnt += fd_funk_txn_cancel_family( funk, map, txn_max, tag, sibling_idx );
399 468471 : }
400 :
401 303579 : return cancel_cnt;
402 303579 : }
403 :
404 : ulong
405 : fd_funk_txn_cancel_siblings( fd_funk_t * funk,
406 : fd_funk_txn_t * txn,
407 0 : int verbose ) {
408 :
409 0 : if( FD_UNLIKELY( !funk ) ) {
410 0 : if( FD_UNLIKELY( verbose ) ) FD_LOG_WARNING(( "NULL funk" ));
411 0 : return 0UL;
412 0 : }
413 :
414 0 : fd_funk_txn_t * map = fd_funk_txn_map( funk, fd_funk_wksp( funk ) );
415 :
416 0 : ulong txn_max = funk->txn_max;
417 :
418 0 : ulong txn_idx = (ulong)(txn - map);
419 :
420 0 : if( FD_UNLIKELY( (txn_idx>=txn_max) /* Out of map (incl NULL) */ | (txn!=(map+txn_idx)) /* Bad alignment */ ) ) {
421 0 : if( FD_UNLIKELY( verbose ) ) FD_LOG_WARNING(( "txn is not a funk transaction" ));
422 0 : return 0UL;
423 0 : }
424 :
425 0 : ulong oldest_idx = fd_funk_txn_oldest_sibling( funk, map, txn_max, txn_idx );
426 :
427 0 : return fd_funk_txn_cancel_sibling_list( funk, map, txn_max, funk->cycle_tag++, oldest_idx, txn_idx );
428 0 : }
429 :
430 : ulong
431 : fd_funk_txn_cancel_children( fd_funk_t * funk,
432 : fd_funk_txn_t * txn,
433 0 : int verbose ) {
434 :
435 0 : if( FD_UNLIKELY( !funk ) ) {
436 0 : if( FD_UNLIKELY( verbose ) ) FD_LOG_WARNING(( "NULL funk" ));
437 0 : return 0UL;
438 0 : }
439 :
440 0 : fd_funk_txn_t * map = fd_funk_txn_map( funk, fd_funk_wksp( funk ) );
441 :
442 0 : ulong txn_max = funk->txn_max;
443 :
444 0 : ulong oldest_idx;
445 :
446 0 : if( FD_LIKELY( txn == NULL ) ) {
447 0 : oldest_idx = fd_funk_txn_idx( funk->child_head_cidx ); /* opt for non-compete */
448 0 : } else {
449 0 : ulong txn_idx = (ulong)(txn - map);
450 0 : if( FD_UNLIKELY( (txn_idx>=txn_max) /* Out of map */ | (txn!=(map+txn_idx)) /* Bad alignment */ ) ) {
451 0 : if( FD_UNLIKELY( verbose ) ) FD_LOG_WARNING(( "txn is not a funk transaction" ));
452 0 : return 0UL;
453 0 : }
454 :
455 0 : if( FD_UNLIKELY( !fd_funk_txn_map_query( map, fd_funk_txn_xid( txn ), NULL ) ) ) {
456 0 : if( FD_UNLIKELY( verbose ) ) FD_LOG_WARNING(( "txn is not in preparation" ));
457 0 : return 0UL;
458 0 : }
459 :
460 0 : oldest_idx = fd_funk_txn_idx( txn->child_head_cidx );
461 0 : }
462 :
463 0 : if( fd_funk_txn_idx_is_null( oldest_idx ) ) {
464 0 : return 0UL;
465 0 : }
466 :
467 0 : return fd_funk_txn_cancel_sibling_list( funk, map, txn_max, funk->cycle_tag++, oldest_idx, FD_FUNK_TXN_IDX_NULL );
468 0 : }
469 :
470 : /* Cancel all outstanding transactions */
471 :
472 : ulong
473 : fd_funk_txn_cancel_all( fd_funk_t * funk,
474 0 : int verbose ) {
475 0 : return fd_funk_txn_cancel_children( funk, NULL, verbose );
476 0 : }
477 :
478 : /* fd_funk_txn_update applies the record updates in transaction txn_idx
479 : to another transaction or the parent transaction. Callers have
480 : already validated our input arguments.
481 :
482 : On entry, the head/tail of the destination records are at
483 : *_dst_rec_head_idx / *_dst_rec_tail_idx. All transactions on this
484 : list will have transaction id dst_xid and vice versa. That is, this
485 : is the record list the last published transaction or txn_idx's
486 : in-prep parent transaction.
487 :
488 : On exit, the head/tail of the updated records is at
489 : *_dst_rec_head_idx / *_dst_rec_tail_idx. As before, all transactions
490 : on this list will have transaction id dst_xid and vice versa.
491 : Transaction txn_idx will have an _empty_ record list.
492 :
493 : Updates in the transaction txn_idx are processed from oldest to
494 : youngest. If an update erases an existing record in dest, the record
495 : to erase is removed from the destination records without perturbing
496 : the order of remaining destination records. If an update is to
497 : update an existing record, the destination record value is updated
498 : and the order of the destination records is unchanged. If an update
499 : is to create a new record, the record is appended to the list of
500 : existing values as youngest without changing the order of existing
501 : values. If an update erases a record in an in-prep parent, the
502 : erasure will be moved into the parent as the youngest without
503 : changing the order of existing values. */
504 :
505 : static void
506 : fd_funk_txn_update( ulong * _dst_rec_head_idx, /* Pointer to the dst list head */
507 : ulong * _dst_rec_tail_idx, /* Pointer to the dst list tail */
508 : ulong dst_txn_idx, /* Transaction index of the merge destination */
509 : fd_funk_txn_xid_t const * dst_xid, /* dst xid */
510 : ulong txn_idx, /* Transaction index of the records to merge */
511 : ulong rec_max, /* ==funk->rec_max */
512 : fd_funk_txn_t * txn_map, /* ==fd_funk_rec_map( funk, wksp ) */
513 : fd_funk_rec_t * rec_map, /* ==fd_funk_rec_map( funk, wksp ) */
514 : fd_alloc_t * alloc, /* ==fd_funk_alloc( funk, wksp ) */
515 303579 : fd_wksp_t * wksp ) { /* ==fd_funk_wksp( funk ) */
516 : /* We don't need to do all the individual removal pointer updates
517 : as we are removing the whole list from txn_idx. */
518 :
519 303579 : ulong rec_idx = txn_map[ txn_idx ].rec_head_idx;
520 853467 : while( !fd_funk_rec_idx_is_null( rec_idx ) ) {
521 : /* Validate rec_idx */
522 :
523 549888 : if( FD_UNLIKELY( rec_idx>=rec_max ) ) FD_LOG_CRIT(( "memory corruption detected (bad idx)" ));
524 549888 : if( FD_UNLIKELY( fd_funk_txn_idx( rec_map[ rec_idx ].txn_cidx )!=txn_idx ) )
525 0 : FD_LOG_CRIT(( "memory corruption detected (cycle or bad idx)" ));
526 :
527 549888 : fd_funk_rec_t * rec = &rec_map[ rec_idx ];
528 549888 : ulong next_rec_idx = rec->next_idx;
529 :
530 : /* See if (dst_xid,key) already exists. Remove it if it does, and then clean up the corpse.
531 : We can take advantage of the ordering property that children
532 : come before parents in the hash chain, and all elements with
533 : the same record key have the same hash. */
534 549888 : ulong * next = &rec->map_next;
535 865986 : for(;;) {
536 865986 : ulong ele_idx = fd_funk_rec_map_private_unbox_idx( *next );
537 865986 : if( fd_funk_rec_map_private_is_null( ele_idx ) ) break;
538 748428 : fd_funk_rec_t * ele = rec_map + ele_idx;
539 :
540 748428 : if( FD_LIKELY( rec->map_hash == ele->map_hash ) &&
541 748428 : FD_LIKELY( fd_funk_rec_key_eq( rec->pair.key, ele->pair.key ) ) &&
542 748428 : FD_LIKELY( fd_funk_txn_xid_eq( dst_xid, ele->pair.xid ) ) ) {
543 : /* Remove from the transaction */
544 432330 : ulong prev_idx = ele->prev_idx;
545 432330 : ulong next_idx = ele->next_idx;
546 432330 : if( fd_funk_rec_idx_is_null( prev_idx ) ) {
547 6222 : *_dst_rec_head_idx = next_idx;
548 426108 : } else {
549 426108 : rec_map[ prev_idx ].next_idx = next_idx;
550 426108 : }
551 432330 : if( fd_funk_rec_idx_is_null( next_idx ) ) {
552 1161 : *_dst_rec_tail_idx = prev_idx;
553 431169 : } else {
554 431169 : rec_map[ next_idx ].prev_idx = prev_idx;
555 431169 : }
556 : /* Clean up value */
557 432330 : fd_funk_val_flush( ele, alloc, wksp );
558 432330 : ele->txn_cidx = fd_funk_txn_cidx( FD_FUNK_TXN_IDX_NULL );
559 : /* Remove from record map */
560 432330 : fd_funk_rec_map_private_t * priv = fd_funk_rec_map_private( rec_map );
561 432330 : *next = ele->map_next;
562 432330 : ele->map_next = priv->free_stack;
563 432330 : priv->free_stack = (ele_idx | (1UL<<63));
564 432330 : priv->key_cnt--;
565 432330 : break;
566 432330 : }
567 :
568 316098 : next = &ele->map_next;
569 316098 : }
570 :
571 : /* Add the new record to the transaction. We can update the xid in
572 : place because it is not used for hashing the element. We have
573 : to preserve the original element to preserve the
574 : newest-to-oldest ordering in the hash
575 : chain. fd_funk_rec_query_global relies on this subtle
576 : property. */
577 :
578 549888 : rec->pair.xid[0] = *dst_xid;
579 549888 : rec->txn_cidx = fd_funk_txn_cidx( dst_txn_idx );
580 :
581 549888 : if( fd_funk_rec_idx_is_null( *_dst_rec_head_idx ) ) {
582 11805 : *_dst_rec_head_idx = rec_idx;
583 11805 : rec->prev_idx = FD_FUNK_REC_IDX_NULL;
584 538083 : } else {
585 538083 : rec_map[ *_dst_rec_tail_idx ].next_idx = rec_idx;
586 538083 : rec->prev_idx = *_dst_rec_tail_idx;
587 538083 : }
588 549888 : *_dst_rec_tail_idx = rec_idx;
589 549888 : rec->next_idx = FD_FUNK_REC_IDX_NULL;
590 :
591 549888 : rec_idx = next_rec_idx;
592 549888 : }
593 :
594 303579 : txn_map[ txn_idx ].rec_head_idx = FD_FUNK_REC_IDX_NULL;
595 303579 : txn_map[ txn_idx ].rec_tail_idx = FD_FUNK_REC_IDX_NULL;
596 303579 : }
597 :
598 : /* fd_funk_txn_publish_funk_child publishes a transaction that is known
599 : to be a child of funk. Callers have already validated our input
600 : arguments. Returns FD_FUNK_SUCCESS on success and an FD_FUNK_ERR_*
601 : code on failure. (There are currently no failure cases but the
602 : plumbing is there if value handling requires it at some point.) */
603 :
604 : static int
605 : fd_funk_txn_publish_funk_child( fd_funk_t * funk,
606 : fd_funk_txn_t * map,
607 : ulong txn_max,
608 : ulong tag,
609 273579 : ulong txn_idx ) {
610 :
611 273579 : fd_funk_check_write( funk );
612 :
613 : /* Apply the updates in txn to the last published transactions */
614 :
615 273579 : fd_wksp_t * wksp = fd_funk_wksp( funk );
616 273579 : fd_funk_txn_update( &funk->rec_head_idx, &funk->rec_tail_idx, FD_FUNK_TXN_IDX_NULL, fd_funk_root( funk ),
617 273579 : txn_idx, funk->rec_max, map, fd_funk_rec_map( funk, wksp ),
618 273579 : fd_funk_alloc( funk, wksp ), wksp );
619 :
620 : /* Cancel all competing transaction histories */
621 :
622 273579 : ulong oldest_idx = fd_funk_txn_oldest_sibling( funk, map, txn_max, txn_idx );
623 273579 : fd_funk_txn_cancel_sibling_list( funk, map, txn_max, tag, oldest_idx, txn_idx );
624 :
625 : /* Make all the children children of funk */
626 :
627 273579 : ulong child_head_idx = fd_funk_txn_idx( map[ txn_idx ].child_head_cidx );
628 273579 : ulong child_tail_idx = fd_funk_txn_idx( map[ txn_idx ].child_tail_cidx );
629 :
630 273579 : ulong child_idx = child_head_idx;
631 565662 : while( FD_UNLIKELY( !fd_funk_txn_idx_is_null( child_idx ) ) ) { /* opt for incr pub */
632 :
633 292083 : ASSERT_IN_PREP ( child_idx );
634 292083 : ASSERT_UNTAGGED( child_idx );
635 292083 : map[ child_idx ].tag = tag;
636 :
637 292083 : map[ child_idx ].parent_cidx = fd_funk_txn_cidx( FD_FUNK_TXN_IDX_NULL );
638 :
639 292083 : child_idx = fd_funk_txn_idx( map[ child_idx ].sibling_next_cidx );
640 292083 : }
641 :
642 273579 : funk->child_head_cidx = fd_funk_txn_cidx( child_head_idx );
643 273579 : funk->child_tail_cidx = fd_funk_txn_cidx( child_tail_idx );
644 :
645 : /* Remove the mapping */
646 :
647 273579 : fd_funk_txn_xid_copy( funk->last_publish, fd_funk_txn_xid( &map[ txn_idx ] ) );
648 :
649 273579 : fd_funk_txn_map_remove( map, fd_funk_txn_xid( &map[ txn_idx ] ) );
650 :
651 273579 : return FD_FUNK_SUCCESS;
652 273579 : }
653 :
654 : ulong
655 : fd_funk_txn_publish( fd_funk_t * funk,
656 : fd_funk_txn_t * txn,
657 1349388 : int verbose ) {
658 :
659 1349388 : if( FD_UNLIKELY( !funk ) ) {
660 196464 : if( FD_UNLIKELY( verbose ) ) FD_LOG_WARNING(( "NULL funk" ));
661 196464 : return 0UL;
662 196464 : }
663 :
664 1152924 : fd_wksp_t * wksp = fd_funk_wksp( funk );
665 :
666 1152924 : fd_funk_txn_t * map = fd_funk_txn_map( funk, wksp );
667 :
668 1152924 : ulong txn_max = funk->txn_max;
669 :
670 1152924 : ulong txn_idx = (ulong)(txn - map);
671 :
672 1152924 : if( FD_UNLIKELY( (txn_idx>=txn_max) /* Out of map (incl NULL) */ | (txn!=(map+txn_idx)) /* Bad alignment */ ) ) {
673 786372 : if( FD_UNLIKELY( verbose ) ) FD_LOG_WARNING(( "txn is not a funk transaction" ));
674 786372 : return 0UL;
675 786372 : }
676 :
677 366552 : if( FD_UNLIKELY( !fd_funk_txn_map_query( map, fd_funk_txn_xid( txn ), NULL ) ) ) {
678 188382 : if( FD_UNLIKELY( verbose ) ) FD_LOG_WARNING(( "txn is not in preparation" ));
679 188382 : return 0UL;
680 188382 : }
681 :
682 178170 : ulong tag = funk->cycle_tag++;
683 :
684 178170 : ulong publish_stack_idx = FD_FUNK_TXN_IDX_NULL;
685 :
686 273579 : for(;;) {
687 273579 : map[ txn_idx ].tag = tag;
688 :
689 : /* At this point, txn_idx is a transaction that needs to be
690 : published and has been tagged. If txn is a child of funk, we are
691 : ready to publish txn and everything on the publish stack. */
692 :
693 273579 : ulong parent_idx = fd_funk_txn_idx( map[ txn_idx ].parent_cidx );
694 273579 : if( FD_LIKELY( fd_funk_txn_idx_is_null( parent_idx ) ) ) break; /* opt for incr pub */
695 :
696 : /* txn_idx has a parent. Validate and tag it. Push txn to the
697 : publish stack and recurse into the parent. */
698 :
699 95409 : ASSERT_IN_PREP ( parent_idx );
700 95409 : ASSERT_UNTAGGED( parent_idx );
701 :
702 95409 : map[ txn_idx ].stack_cidx = fd_funk_txn_cidx( publish_stack_idx );
703 95409 : publish_stack_idx = txn_idx;
704 :
705 95409 : txn_idx = parent_idx;
706 95409 : }
707 :
708 178170 : ulong publish_cnt = 0UL;
709 :
710 273579 : for(;;) {
711 :
712 : /* At this point, all the transactions we need to publish are
713 : tagged, txn is the next up publish funk and publish_stack has the
714 : transactions to follow in order by pop. We use a new tag for
715 : each publish as txn and its siblings we potentially visited in a
716 : previous iteration of this loop. */
717 :
718 273579 : if( FD_UNLIKELY( fd_funk_txn_publish_funk_child( funk, map, txn_max, funk->cycle_tag++, txn_idx ) ) ) break;
719 273579 : publish_cnt++;
720 :
721 273579 : txn_idx = publish_stack_idx;
722 273579 : if( FD_LIKELY( fd_funk_txn_idx_is_null( txn_idx ) ) ) break; /* opt for incr pub */
723 95409 : publish_stack_idx = fd_funk_txn_idx( map[ txn_idx ].stack_cidx );
724 95409 : }
725 :
726 178170 : return publish_cnt;
727 178170 : }
728 :
729 : int
730 : fd_funk_txn_publish_into_parent( fd_funk_t * funk,
731 : fd_funk_txn_t * txn,
732 30000 : int verbose ) {
733 30000 : if( FD_UNLIKELY( !funk ) ) {
734 0 : if( FD_UNLIKELY( verbose ) ) FD_LOG_WARNING(( "NULL funk" ));
735 0 : return FD_FUNK_ERR_INVAL;
736 0 : }
737 30000 : fd_funk_check_write( funk );
738 :
739 30000 : fd_wksp_t * wksp = fd_funk_wksp( funk );
740 :
741 30000 : fd_funk_txn_t * map = fd_funk_txn_map( funk, wksp );
742 :
743 30000 : ulong txn_idx = (ulong)(txn - map);
744 :
745 30000 : ulong oldest_idx = fd_funk_txn_oldest_sibling( funk, map, funk->txn_max, txn_idx );
746 30000 : fd_funk_txn_cancel_sibling_list( funk, map, funk->txn_max, funk->cycle_tag++, oldest_idx, txn_idx );
747 :
748 30000 : ulong parent_idx = fd_funk_txn_idx( txn->parent_cidx );
749 30000 : if( fd_funk_txn_idx_is_null( parent_idx ) ) {
750 : /* Publish to root */
751 6408 : if( fd_funk_txn_idx( funk->child_head_cidx ) != txn_idx || fd_funk_txn_idx( funk->child_tail_cidx ) != txn_idx )
752 0 : FD_LOG_CRIT(( "memory corruption detected (cycle or bad idx)" ));
753 6408 : fd_funk_txn_update( &funk->rec_head_idx, &funk->rec_tail_idx, FD_FUNK_TXN_IDX_NULL, fd_funk_root( funk ),
754 6408 : txn_idx, funk->rec_max, map, fd_funk_rec_map( funk, wksp ),
755 6408 : fd_funk_alloc( funk, wksp ), wksp );
756 : /* Inherit the children */
757 6408 : funk->child_head_cidx = txn->child_head_cidx;
758 6408 : funk->child_tail_cidx = txn->child_tail_cidx;
759 23592 : } else {
760 23592 : fd_funk_txn_t * parent_txn = map + parent_idx;
761 23592 : if( fd_funk_txn_idx( parent_txn->child_head_cidx ) != txn_idx || fd_funk_txn_idx( parent_txn->child_tail_cidx ) != txn_idx )
762 0 : FD_LOG_CRIT(( "memory corruption detected (cycle or bad idx)" ));
763 23592 : fd_funk_txn_update( &parent_txn->rec_head_idx, &parent_txn->rec_tail_idx, parent_idx, &parent_txn->xid,
764 23592 : txn_idx, funk->rec_max, map, fd_funk_rec_map( funk, wksp ),
765 23592 : fd_funk_alloc( funk, wksp ), wksp );
766 : /* Inherit the children */
767 23592 : parent_txn->child_head_cidx = txn->child_head_cidx;
768 23592 : parent_txn->child_tail_cidx = txn->child_tail_cidx;
769 23592 : }
770 :
771 : /* Adjust the parent pointers of the children to point to their grandparent */
772 30000 : ulong child_idx = fd_funk_txn_idx( txn->child_head_cidx );
773 53619 : while( FD_UNLIKELY( !fd_funk_txn_idx_is_null( child_idx ) ) ) {
774 23619 : map[ child_idx ].parent_cidx = fd_funk_txn_cidx( parent_idx );
775 23619 : child_idx = fd_funk_txn_idx( map[ child_idx ].sibling_next_cidx );
776 23619 : }
777 :
778 30000 : fd_funk_txn_map_remove( map, fd_funk_txn_xid( txn ) );
779 :
780 30000 : return FD_FUNK_SUCCESS;
781 30000 : }
782 :
783 : /* Unfortunately, the semantics of how to deal with the same record
784 : key appearing in multiple children is not defined. So, for now,
785 : this API is commented out. */
786 : #if 0
787 : int
788 : fd_funk_txn_merge_all_children( fd_funk_t * funk,
789 : fd_funk_txn_t * parent_txn,
790 : int verbose ) {
791 : if( FD_UNLIKELY( !funk ) ) {
792 : if( FD_UNLIKELY( verbose ) ) FD_LOG_WARNING(( "NULL funk" ));
793 : return FD_FUNK_ERR_INVAL;
794 : }
795 : fd_funk_check_write( funk );
796 :
797 : fd_wksp_t * wksp = fd_funk_wksp( funk );
798 :
799 : fd_funk_txn_t * map = fd_funk_txn_map( funk, wksp );
800 : ulong txn_max = funk->txn_max; /* Previously verified */
801 :
802 : ulong parent_idx;
803 : fd_funk_txn_xid_t * parent_xid;
804 : uint * child_head_cidx;
805 : uint * child_tail_cidx;
806 : ulong * rec_head_idx;
807 : ulong * rec_tail_idx;
808 : if( parent_txn == NULL ) { /* Root */
809 : parent_idx = FD_FUNK_TXN_IDX_NULL;
810 : parent_xid = funk->root;
811 : child_head_cidx = &funk->child_head_cidx;
812 : child_tail_cidx = &funk->child_tail_cidx;
813 : rec_head_idx = &funk->rec_head_idx;
814 : rec_tail_idx = &funk->rec_tail_idx;
815 : } else {
816 : parent_idx = (ulong)(parent_txn - map);
817 : ASSERT_IN_PREP( parent_idx );
818 : parent_xid = &parent_txn->xid;
819 : child_head_cidx = &parent_txn->child_head_cidx;
820 : child_tail_cidx = &parent_txn->child_tail_cidx;
821 : rec_head_idx = &parent_txn->rec_head_idx;
822 : rec_tail_idx = &parent_txn->rec_tail_idx;
823 : }
824 :
825 : ulong child_head_idx = fd_funk_txn_idx( *child_head_cidx );
826 : ulong child_idx = child_head_idx;
827 : while( FD_UNLIKELY( !fd_funk_txn_idx_is_null( child_idx ) ) ) { /* opt for incr pub */
828 : /* Merge records from child into parent */
829 :
830 : fd_funk_txn_t * txn = &map[ child_idx ];
831 : if( FD_UNLIKELY( !fd_funk_txn_idx_is_null( fd_funk_txn_idx( txn->child_head_cidx ) ) ) ) {
832 : FD_LOG_WARNING(("cannot call fd_funk_txn_merge_all_children if parent_txn has grandchildren"));
833 : return FD_FUNK_ERR_TXN;
834 : }
835 :
836 : fd_funk_txn_update( rec_head_idx, rec_tail_idx, parent_idx, parent_xid,
837 : child_idx, funk->rec_max, map, fd_funk_rec_map( funk, wksp ),
838 : fd_funk_alloc( funk, wksp ), wksp );
839 :
840 : child_idx = fd_funk_txn_idx( txn->sibling_next_cidx );
841 : fd_funk_txn_map_remove( map, fd_funk_txn_xid( txn ) );
842 :
843 : /* Update the pointers as we go in case we stop in the middle
844 : */
845 : *child_head_cidx = fd_funk_txn_cidx( child_idx );
846 : if( FD_UNLIKELY( !fd_funk_txn_idx_is_null( child_idx ) ) ) {
847 : map[ child_idx ].sibling_prev_cidx = fd_funk_txn_cidx( FD_FUNK_TXN_IDX_NULL );
848 : }
849 : }
850 :
851 : *child_tail_cidx = fd_funk_txn_cidx( FD_FUNK_TXN_IDX_NULL );
852 :
853 : return FD_FUNK_SUCCESS;
854 : }
855 : #endif
856 :
857 : /* Return the first record in a transaction. Returns NULL if the
858 : transaction has no records yet. */
859 :
860 : FD_FN_PURE fd_funk_rec_t const *
861 : fd_funk_txn_first_rec( fd_funk_t * funk,
862 4861050 : fd_funk_txn_t const * txn ) {
863 4861050 : ulong rec_idx;
864 4861050 : if( FD_UNLIKELY( NULL == txn ))
865 255000 : rec_idx = funk->rec_head_idx;
866 4606050 : else
867 4606050 : rec_idx = txn->rec_head_idx;
868 4861050 : if( fd_funk_rec_idx_is_null( rec_idx ) ) return NULL;
869 3154092 : fd_funk_rec_t const * rec_map = fd_funk_rec_map( funk, fd_funk_wksp( funk ) );
870 3154092 : return rec_map + rec_idx;
871 4861050 : }
872 :
873 : /* Return the next record in a transaction. Returns NULL if the
874 : transaction has no more records. */
875 :
876 : FD_FN_PURE fd_funk_rec_t const *
877 : fd_funk_txn_next_rec( fd_funk_t * funk,
878 46014141 : fd_funk_rec_t const * rec ) {
879 46014141 : ulong rec_idx = rec->next_idx;
880 46014141 : if( fd_funk_rec_idx_is_null( rec_idx ) ) return NULL;
881 42860049 : fd_funk_rec_t const * rec_map = fd_funk_rec_map( funk, fd_funk_wksp( funk ) );
882 42860049 : return rec_map + rec_idx;
883 46014141 : }
884 :
885 : fd_funk_txn_xid_t
886 19115325 : fd_funk_generate_xid(void) {
887 19115325 : fd_funk_txn_xid_t xid;
888 19115325 : static FD_TL ulong seq = 0;
889 19115325 : xid.ul[0] =
890 19115325 : (fd_log_cpu_id() + 1U)*3138831853UL +
891 19115325 : (fd_log_thread_id() + 1U)*9180195821UL +
892 19115325 : (++seq)*6208101967UL;
893 19115325 : xid.ul[1] = ((ulong)fd_tickcount())*2810745731UL;
894 19115325 : return xid;
895 19115325 : }
896 :
897 : int
898 9692196 : fd_funk_txn_verify( fd_funk_t * funk ) {
899 9692196 : fd_wksp_t * wksp = fd_funk_wksp( funk ); /* Previously verified */
900 9692196 : fd_funk_txn_t * map = fd_funk_txn_map( funk, wksp ); /* Previously verified */
901 9692196 : ulong txn_max = funk->txn_max; /* Previously verified */
902 :
903 9692196 : ulong funk_child_head_idx = fd_funk_txn_idx( funk->child_head_cidx ); /* Previously verified */
904 9692196 : ulong funk_child_tail_idx = fd_funk_txn_idx( funk->child_tail_cidx ); /* Previously verified */
905 :
906 9692196 : fd_funk_txn_xid_t const * last_publish = funk->last_publish; /* Previously verified */
907 :
908 609292950 : # define TEST(c) do { \
909 609292950 : if( FD_UNLIKELY( !(c) ) ) { FD_LOG_WARNING(( "FAIL: %s", #c )); return FD_FUNK_ERR_INVAL; } \
910 609292950 : } while(0)
911 :
912 9692196 : # define IS_VALID( idx ) ( (idx==FD_FUNK_TXN_IDX_NULL) || \
913 9692196 : ((idx<txn_max) && (!fd_funk_txn_xid_eq( fd_funk_txn_xid( &map[idx] ), last_publish ))) )
914 :
915 9692196 : TEST( !fd_funk_txn_map_verify( map ) );
916 :
917 9692196 : ulong free_cnt = txn_max - fd_funk_txn_map_key_cnt( map );
918 :
919 : /* Tag all transactions as not visited yet */
920 :
921 345894948 : for( ulong txn_idx=0UL; txn_idx<txn_max; txn_idx++ ) map[ txn_idx ].tag = 0UL;
922 :
923 : /* Visit all transactions in preparation, traversing from oldest to
924 : youngest. */
925 :
926 9692196 : ulong prep_cnt = 0UL;
927 9692196 : do {
928 :
929 : /* Push all children of funk to the stack */
930 :
931 9692196 : ulong stack_idx = FD_FUNK_TXN_IDX_NULL;
932 9692196 : ulong child_idx = funk_child_head_idx;
933 32391261 : while( !fd_funk_txn_idx_is_null( child_idx ) ) {
934 :
935 : /* Make sure valid idx, not tagged (detects cycles) and child
936 : knows it is a child of funk. Then tag as visited / in-prep,
937 : push to stack and update prep_cnt */
938 :
939 22699065 : TEST( IS_VALID( child_idx ) );
940 22699065 : TEST( !map[ child_idx ].tag );
941 22699065 : TEST( fd_funk_txn_idx_is_null( fd_funk_txn_idx( map[ child_idx ].parent_cidx ) ) );
942 22699065 : map[ child_idx ].tag = 1UL;
943 22699065 : map[ child_idx ].stack_cidx = fd_funk_txn_cidx( stack_idx );
944 22699065 : stack_idx = child_idx;
945 22699065 : prep_cnt++;
946 :
947 22699065 : ulong next_idx = fd_funk_txn_idx( map[ child_idx ].sibling_next_cidx );
948 22699065 : if( !fd_funk_txn_idx_is_null( next_idx ) ) TEST( fd_funk_txn_idx( map[ next_idx ].sibling_prev_cidx )==child_idx );
949 22699065 : child_idx = next_idx;
950 22699065 : }
951 :
952 92035881 : while( !fd_funk_txn_idx_is_null( stack_idx ) ) {
953 :
954 : /* Pop the next transaction to traverse */
955 :
956 82343685 : ulong txn_idx = stack_idx;
957 82343685 : stack_idx = fd_funk_txn_idx( map[ txn_idx ].stack_cidx );
958 :
959 : /* Push all children of txn to the stack */
960 :
961 82343685 : ulong child_idx = fd_funk_txn_idx( map[ txn_idx ].child_head_cidx );
962 141988305 : while( !fd_funk_txn_idx_is_null( child_idx ) ) {
963 :
964 : /* Make sure valid idx, not tagged (detects cycles) and child
965 : knows it is a child of txn_idx. Then tag as visited /
966 : in-prep, push to stack and update prep_cnt */
967 :
968 59644620 : TEST( IS_VALID( child_idx ) );
969 59644620 : TEST( !map[ child_idx ].tag );
970 59644620 : TEST( fd_funk_txn_idx( map[ child_idx ].parent_cidx )==txn_idx );
971 59644620 : map[ child_idx ].tag = 1UL;
972 59644620 : map[ child_idx ].stack_cidx = fd_funk_txn_cidx( stack_idx );
973 59644620 : stack_idx = child_idx;
974 59644620 : prep_cnt++;
975 :
976 59644620 : ulong next_idx = fd_funk_txn_idx( map[ child_idx ].sibling_next_cidx );
977 59644620 : if( !fd_funk_txn_idx_is_null( next_idx ) ) TEST( fd_funk_txn_idx( map[ next_idx ].sibling_prev_cidx )==child_idx );
978 59644620 : child_idx = next_idx;
979 59644620 : }
980 82343685 : }
981 :
982 9692196 : } while(0);
983 :
984 9692196 : TEST( (free_cnt+prep_cnt)==txn_max );
985 :
986 : /* Do it again with a youngest to oldest traversal to test reverse
987 : link integrity */
988 :
989 9692196 : prep_cnt = 0UL;
990 9692196 : do {
991 :
992 : /* Push all children of funk to the stack */
993 :
994 9692196 : ulong stack_idx = FD_FUNK_TXN_IDX_NULL;
995 9692196 : ulong child_idx = funk_child_tail_idx;
996 32391261 : while( !fd_funk_txn_idx_is_null( child_idx ) ) {
997 :
998 : /* Make sure valid idx, tagged as visited above (detects cycles)
999 : and child knows it is a child of funk. Then tag as visited /
1000 : in-prep, push to stack and update prep_cnt */
1001 :
1002 22699065 : TEST( IS_VALID( child_idx ) );
1003 22699065 : TEST( map[ child_idx ].tag==1UL );
1004 22699065 : TEST( fd_funk_txn_idx_is_null( fd_funk_txn_idx( map[ child_idx ].parent_cidx ) ) );
1005 22699065 : map[ child_idx ].tag = 2UL;
1006 22699065 : map[ child_idx ].stack_cidx = fd_funk_txn_cidx( stack_idx );
1007 22699065 : stack_idx = child_idx;
1008 22699065 : prep_cnt++;
1009 :
1010 22699065 : ulong prev_idx = fd_funk_txn_idx( map[ child_idx ].sibling_prev_cidx );
1011 22699065 : if( !fd_funk_txn_idx_is_null( prev_idx ) ) TEST( fd_funk_txn_idx( map[ prev_idx ].sibling_next_cidx )==child_idx );
1012 22699065 : child_idx = prev_idx;
1013 22699065 : }
1014 :
1015 92035881 : while( !fd_funk_txn_idx_is_null( stack_idx ) ) {
1016 :
1017 : /* Pop the next transaction to traverse */
1018 :
1019 82343685 : ulong txn_idx = stack_idx;
1020 82343685 : stack_idx = fd_funk_txn_idx( map[ txn_idx ].stack_cidx );
1021 :
1022 : /* Push all children of txn to the stack */
1023 :
1024 82343685 : ulong child_idx = fd_funk_txn_idx( map[ txn_idx ].child_tail_cidx );
1025 141988305 : while( !fd_funk_txn_idx_is_null( child_idx ) ) {
1026 :
1027 : /* Make sure valid idx, tagged as visited above (detects cycles)
1028 : and child knows it is a child of txn_idx. Then, tag as
1029 : visited / in-prep, push to stack and update prep_cnt */
1030 :
1031 59644620 : TEST( IS_VALID( child_idx ) );
1032 59644620 : TEST( map[ child_idx ].tag==1UL );
1033 59644620 : TEST( fd_funk_txn_idx( map[ child_idx ].parent_cidx )==txn_idx );
1034 59644620 : map[ child_idx ].tag = 2UL;
1035 59644620 : map[ child_idx ].stack_cidx = fd_funk_txn_cidx( stack_idx );
1036 59644620 : stack_idx = child_idx;
1037 59644620 : prep_cnt++;
1038 :
1039 59644620 : ulong prev_idx = fd_funk_txn_idx( map[ child_idx ].sibling_prev_cidx );
1040 59644620 : if( !fd_funk_txn_idx_is_null( prev_idx ) ) TEST( fd_funk_txn_idx( map[ prev_idx ].sibling_next_cidx )==child_idx );
1041 59644620 : child_idx = prev_idx;
1042 59644620 : }
1043 82343685 : }
1044 9692196 : } while(0);
1045 :
1046 9692196 : TEST( (free_cnt+prep_cnt)==txn_max );
1047 :
1048 9692196 : TEST( fd_funk_txn_cnt( map )==prep_cnt );
1049 :
1050 9692196 : # undef IS_VALID
1051 9692196 : # undef TEST
1052 :
1053 9692196 : return FD_FUNK_SUCCESS;
1054 9692196 : }
1055 :
1056 : #undef ASSERT_UNTAGGED
1057 : #undef ASSERT_IN_PREP
1058 : #undef ASSERT_IN_MAP
|
