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 1558699241 : #define MAP_T fd_funk_txn_t
7 : #define MAP_KEY_T fd_funk_txn_xid_t
8 3758337 : #define MAP_KEY xid
9 : #define MAP_KEY_EQ(k0,k1) fd_funk_txn_xid_eq((k0),(k1))
10 829988157 : #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 1175702674 : #define MAP_NEXT map_next
13 1635111307 : #define MAP_HASH map_hash
14 408483 : #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 3758337 : #define ASSERT_IN_MAP( txn_idx ) do { \
52 3758337 : if( FD_UNLIKELY( txn_idx>=txn_max ) ) \
53 3758337 : FD_LOG_CRIT(( "memory corruption detected (bad_idx)" )); \
54 3758337 : } while(0)
55 :
56 7333491 : #define ASSERT_IN_PREP( txn_idx ) do { \
57 7333491 : if( FD_UNLIKELY( txn_idx>=txn_max ) ) \
58 7333491 : FD_LOG_CRIT(( "memory corruption detected (bad_idx)" )); \
59 7333491 : if( FD_UNLIKELY( !fd_funk_txn_map_query( map, fd_funk_txn_xid( &map[ txn_idx ] ), NULL ) ) ) \
60 7333491 : FD_LOG_CRIT(( "memory corruption detected (not in prep)" )); \
61 7333491 : } while(0)
62 :
63 3132822 : #define ASSERT_UNTAGGED( txn_idx ) do { \
64 3132822 : if( FD_UNLIKELY( map[ txn_idx ].tag==tag ) ) \
65 3132822 : FD_LOG_CRIT(( "memory corruption detected (cycle)" )); \
66 3132822 : } 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 4994712 : int verbose ) {
73 :
74 4994712 : if( FD_UNLIKELY( !funk ) ) {
75 196464 : if( FD_UNLIKELY( verbose ) ) FD_LOG_WARNING(( "NULL funk" ));
76 196464 : return NULL;
77 196464 : }
78 4798248 : fd_funk_check_write( funk );
79 :
80 4798248 : fd_funk_txn_t * map = fd_funk_txn_map( funk, fd_funk_wksp( funk ) );
81 :
82 4798248 : 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 4798224 : ulong txn_max = funk->txn_max;
88 :
89 4798224 : ulong parent_idx;
90 4798224 : uint * _child_head_cidx;
91 4798224 : uint * _child_tail_cidx;
92 :
93 4798224 : if( FD_LIKELY( !parent ) ) { /* opt for incr pub */
94 :
95 2117388 : parent_idx = FD_FUNK_TXN_IDX_NULL;
96 :
97 2117388 : _child_head_cidx = &funk->child_head_cidx;
98 2117388 : _child_tail_cidx = &funk->child_tail_cidx;
99 :
100 2680836 : } else {
101 :
102 2680836 : parent_idx = (ulong)(parent - map);
103 :
104 2680836 : 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 2484375 : 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 2295993 : _child_head_cidx = &parent->child_head_cidx;
115 2295993 : _child_tail_cidx = &parent->child_tail_cidx;
116 :
117 2295993 : }
118 :
119 4413381 : if( FD_UNLIKELY( !xid ) ) {
120 196461 : if( FD_UNLIKELY( verbose ) ) FD_LOG_WARNING(( "NULL xid" ));
121 196461 : return NULL;
122 196461 : }
123 :
124 4216920 : 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 4216914 : 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 4020459 : 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 3758337 : fd_funk_txn_t * txn = fd_funk_txn_map_insert( map, xid );
142 3758337 : ulong txn_idx = (ulong)(txn - map);
143 3758337 : ASSERT_IN_MAP( txn_idx );
144 :
145 : /* Join the family */
146 :
147 3758337 : ulong sibling_prev_idx = fd_funk_txn_idx( *_child_tail_cidx );
148 :
149 3758337 : int first_born = fd_funk_txn_idx_is_null( sibling_prev_idx );
150 3758337 : if( FD_UNLIKELY( !first_born ) ) ASSERT_IN_PREP( sibling_prev_idx ); /* opt for non-compete */
151 :
152 3758337 : txn->parent_cidx = fd_funk_txn_cidx( parent_idx );
153 3758337 : txn->child_head_cidx = fd_funk_txn_cidx( FD_FUNK_TXN_IDX_NULL );
154 3758337 : txn->child_tail_cidx = fd_funk_txn_cidx( FD_FUNK_TXN_IDX_NULL );
155 3758337 : txn->sibling_prev_cidx = fd_funk_txn_cidx( sibling_prev_idx );
156 3758337 : txn->sibling_next_cidx = fd_funk_txn_cidx( FD_FUNK_TXN_IDX_NULL );
157 3758337 : txn->stack_cidx = fd_funk_txn_cidx( FD_FUNK_TXN_IDX_NULL );
158 3758337 : txn->tag = 0UL;
159 :
160 3758337 : txn->rec_head_idx = FD_FUNK_REC_IDX_NULL;
161 3758337 : txn->rec_tail_idx = FD_FUNK_REC_IDX_NULL;
162 :
163 : /* TODO: consider branchless impl */
164 3758337 : 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 3758337 : *_child_tail_cidx = fd_funk_txn_cidx( txn_idx );
168 :
169 3758337 : return txn;
170 3758337 : }
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 2596914 : ulong txn_idx ) {
183 :
184 2596914 : 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 2596914 : fd_wksp_t * wksp = fd_funk_wksp ( funk );
193 2596914 : fd_alloc_t * alloc = fd_funk_alloc ( funk, wksp );
194 2596914 : fd_funk_rec_t * rec_map = fd_funk_rec_map( funk, wksp );
195 2596914 : fd_funk_partvec_t * partvec = fd_funk_get_partvec( funk, wksp );
196 2596914 : ulong rec_max = funk->rec_max;
197 :
198 2596914 : ulong rec_idx = map[ txn_idx ].rec_head_idx;
199 9009222 : while( !fd_funk_rec_idx_is_null( rec_idx ) ) {
200 :
201 6412308 : if( FD_UNLIKELY( rec_idx>=rec_max ) ) FD_LOG_CRIT(( "memory corruption detected (bad idx)" ));
202 6412308 : if( FD_UNLIKELY( fd_funk_txn_idx( rec_map[ rec_idx ].txn_cidx )!=txn_idx ) )
203 0 : FD_LOG_CRIT(( "memory corruption detected (cycle or bad idx)" ));
204 :
205 6412308 : ulong next_idx = rec_map[ rec_idx ].next_idx;
206 6412308 : rec_map[ rec_idx ].txn_cidx = fd_funk_txn_cidx( FD_FUNK_TXN_IDX_NULL );
207 :
208 6412308 : fd_funk_val_flush( &rec_map[ rec_idx ], alloc, wksp );
209 6412308 : fd_funk_part_set_intern( partvec, rec_map, &rec_map[ rec_idx ], FD_FUNK_PART_NULL );
210 :
211 6412308 : fd_funk_rec_map_remove( rec_map, fd_funk_rec_pair( &rec_map[ rec_idx ] ) );
212 :
213 6412308 : rec_idx = next_idx;
214 6412308 : }
215 :
216 : /* Leave the family */
217 :
218 2596914 : ulong sibling_prev_idx = fd_funk_txn_idx( map[ txn_idx ].sibling_prev_cidx );
219 2596914 : ulong sibling_next_idx = fd_funk_txn_idx( map[ txn_idx ].sibling_next_cidx );
220 :
221 : /* TODO: Consider branchless impl */
222 :
223 2596914 : if( FD_LIKELY( fd_funk_txn_idx_is_null( sibling_prev_idx ) ) ) { /* opt for non-compete */
224 1944147 : ulong parent_idx = fd_funk_txn_idx( map[ txn_idx ].parent_cidx );
225 1944147 : if( FD_LIKELY( fd_funk_txn_idx_is_null( parent_idx ) ) ) { /* No older sib and is a funk child, opt for incr pub */
226 1023474 : funk->child_head_cidx = fd_funk_txn_cidx( sibling_next_idx );
227 1023474 : } else { /* No older sib and has parent */
228 920673 : ASSERT_IN_PREP( parent_idx );
229 920673 : map[ parent_idx ].child_head_cidx = fd_funk_txn_cidx( sibling_next_idx );
230 920673 : }
231 1944147 : } else { /* Has older sib */
232 652767 : ASSERT_IN_PREP( sibling_prev_idx );
233 652767 : map[ sibling_prev_idx ].sibling_next_cidx = fd_funk_txn_cidx( sibling_next_idx );
234 652767 : }
235 :
236 2596914 : if( FD_LIKELY( fd_funk_txn_idx_is_null( sibling_next_idx ) ) ) { /* opt for non-compete */
237 2360598 : ulong parent_idx = fd_funk_txn_idx( map[ txn_idx ].parent_cidx );
238 2360598 : if( FD_LIKELY( fd_funk_txn_idx_is_null( parent_idx ) ) ) { /* No younger sib and is a funk child, opt for incr pub */
239 1197228 : funk->child_tail_cidx = fd_funk_txn_cidx( sibling_prev_idx );
240 1197228 : } else { /* No younger sib and has parent */
241 1163370 : ASSERT_IN_PREP( parent_idx );
242 1163370 : map[ parent_idx ].child_tail_cidx = fd_funk_txn_cidx( sibling_prev_idx );
243 1163370 : }
244 2360598 : } else { /* Has younger sib */
245 236316 : ASSERT_IN_PREP( sibling_next_idx );
246 236316 : map[ sibling_next_idx ].sibling_prev_cidx = fd_funk_txn_cidx( sibling_prev_idx );
247 236316 : }
248 :
249 2596914 : fd_funk_txn_map_remove( map, fd_funk_txn_xid( &map[ txn_idx ] ) );
250 2596914 : }
251 :
252 : /* fd_funk_txn_cancel_family cancels a transaction and all its
253 : descendants in a tree-depth-first-ordered sense from youngest to
254 : oldest. Callers have already validated our input arguments. Returns
255 : the number of transactions canceled. */
256 :
257 : static ulong
258 : fd_funk_txn_cancel_family( fd_funk_t * funk,
259 : fd_funk_txn_t * map,
260 : ulong txn_max,
261 : ulong tag,
262 1932246 : ulong txn_idx ) {
263 1932246 : ulong cancel_cnt = 0UL;
264 :
265 1932246 : map[ txn_idx ].tag = tag;
266 :
267 1932246 : ulong parent_stack_idx = FD_FUNK_TXN_IDX_NULL;
268 :
269 3261582 : for(;;) {
270 :
271 : /* At this point, txn_idx appears to be valid and has been tagged. */
272 :
273 3261582 : ulong youngest_idx = fd_funk_txn_idx( map[ txn_idx ].child_tail_cidx );
274 3261582 : if( FD_LIKELY( fd_funk_txn_idx_is_null( youngest_idx ) ) ) { /* txn is is childless, opt for incr pub */
275 :
276 2596914 : fd_funk_txn_cancel_childless( funk, map, txn_max, txn_idx ); /* If this can fail, return cancel_cnt here on fail */
277 2596914 : cancel_cnt++;
278 :
279 2596914 : txn_idx = parent_stack_idx; /* Pop the parent stack */
280 2596914 : if( FD_LIKELY( fd_funk_txn_idx_is_null( txn_idx ) ) ) break; /* If stack is empty, we are done, opt for incr pub */
281 664668 : parent_stack_idx = fd_funk_txn_idx( map[ txn_idx ].stack_cidx );
282 664668 : continue;
283 2596914 : }
284 :
285 : /* txn has at least one child and the youngest is youngest_idx. Tag
286 : the youngest child, push txn onto the parent stack and recurse
287 : into the youngest child. */
288 :
289 664668 : ASSERT_IN_PREP ( youngest_idx );
290 664668 : ASSERT_UNTAGGED( youngest_idx );
291 664668 : map[ youngest_idx ].tag = tag;
292 :
293 664668 : map[ txn_idx ].stack_cidx = fd_funk_txn_cidx( parent_stack_idx );
294 664668 : parent_stack_idx = txn_idx;
295 :
296 664668 : txn_idx = youngest_idx;
297 664668 : }
298 :
299 1932246 : return cancel_cnt;
300 1932246 : }
301 :
302 : ulong
303 : fd_funk_txn_cancel( fd_funk_t * funk,
304 : fd_funk_txn_t * txn,
305 2634879 : int verbose ) {
306 :
307 2634879 : if( FD_UNLIKELY( !funk ) ) {
308 196464 : if( FD_UNLIKELY( verbose ) ) FD_LOG_WARNING(( "NULL funk" ));
309 196464 : return 0UL;
310 196464 : }
311 :
312 2438415 : fd_funk_txn_t * map = fd_funk_txn_map( funk, fd_funk_wksp( funk ) );
313 :
314 2438415 : ulong txn_max = funk->txn_max;
315 :
316 2438415 : ulong txn_idx = (ulong)(txn - map);
317 :
318 2438415 : if( FD_UNLIKELY( (txn_idx>=txn_max) /* Out of map (incl NULL) */ | (txn!=(map+txn_idx)) /* Bad alignment */ ) ) {
319 786258 : if( FD_UNLIKELY( verbose ) ) FD_LOG_WARNING(( "txn is not a funk transaction" ));
320 786258 : return 0UL;
321 786258 : }
322 :
323 1652157 : if( FD_UNLIKELY( !fd_funk_txn_map_query( map, fd_funk_txn_xid( txn ), NULL ) ) ) {
324 188382 : if( FD_UNLIKELY( verbose ) ) FD_LOG_WARNING(( "txn is not in preparation" ));
325 188382 : return 0UL;
326 188382 : }
327 :
328 1463775 : return fd_funk_txn_cancel_family( funk, map, txn_max, funk->cycle_tag++, txn_idx );
329 1652157 : }
330 :
331 : /* fd_funk_txn_oldest_sibling returns the index of the oldest sibling
332 : in txn_idx's family. Callers have already validated our input
333 : arguments. The caller should validate the return index. */
334 :
335 : static inline ulong
336 : fd_funk_txn_oldest_sibling( fd_funk_t * funk,
337 : fd_funk_txn_t * map,
338 : ulong txn_max,
339 1161381 : ulong txn_idx ) {
340 :
341 1161381 : ulong parent_idx = fd_funk_txn_idx( map[ txn_idx ].parent_cidx );
342 :
343 1161381 : if( FD_LIKELY( fd_funk_txn_idx_is_null( parent_idx ) ) ) return fd_funk_txn_idx( funk->child_head_cidx ); /* opt for incr pub */
344 :
345 431451 : ASSERT_IN_PREP( parent_idx );
346 :
347 431451 : return fd_funk_txn_idx( map[ parent_idx ].child_head_cidx );
348 431451 : }
349 :
350 : /* fd_funk_txn_cancel_sibling_list cancels siblings from sibling_idx down
351 : to the youngest sibling inclusive in the order from youngest to
352 : sibling_idx. Callers have already validated our input arguments
353 : except sibling_idx. Returns the number of cancelled transactions
354 : (should be at least 1). If any sibling is skip_idx, it will be not
355 : be cancelled but still tagged as visited. Passing
356 : FD_FUNK_TXN_IDX_NULL for skip_idx will cancel all siblings from
357 : sibling_idx to the youngest inclusive. */
358 :
359 : static ulong
360 : fd_funk_txn_cancel_sibling_list( fd_funk_t * funk,
361 : fd_funk_txn_t * map,
362 : ulong txn_max,
363 : ulong tag,
364 : ulong sibling_idx,
365 1161381 : ulong skip_idx ) {
366 :
367 1161381 : ulong cancel_stack_idx = FD_FUNK_TXN_IDX_NULL;
368 :
369 : /* Push siblings_idx and its younger siblings inclusive (skipping
370 : sibling skip_idx if encounter) onto the cancel stack from oldest to
371 : youngest (such that we cancel youngest to oldest). */
372 :
373 1629852 : for(;;) {
374 :
375 : /* At this point, sibling_idx is a sibling we might want to add to
376 : the sibling stack. Validate and tag it. */
377 :
378 1629852 : ASSERT_IN_PREP ( sibling_idx );
379 1629852 : ASSERT_UNTAGGED( sibling_idx );
380 1629852 : map[ sibling_idx ].tag = tag;
381 :
382 1629852 : if( FD_UNLIKELY( sibling_idx!=skip_idx ) ) { /* Not skip_idx so push onto the cancel stack, opt for non-compete */
383 468471 : map[ sibling_idx ].stack_cidx = fd_funk_txn_cidx( cancel_stack_idx );
384 468471 : cancel_stack_idx = sibling_idx;
385 468471 : }
386 :
387 1629852 : ulong younger_idx = fd_funk_txn_idx( map[ sibling_idx ].sibling_next_cidx );
388 1629852 : if( FD_LIKELY( fd_funk_txn_idx_is_null( younger_idx ) ) ) break; /* opt for non-compete */
389 468471 : sibling_idx = younger_idx;
390 :
391 468471 : }
392 :
393 : /* Cancel all transactions and their descendants on the cancel stack */
394 :
395 1161381 : ulong cancel_cnt = 0UL;
396 :
397 1629852 : while( !fd_funk_txn_idx_is_null( cancel_stack_idx ) ) { /* TODO: peel first iter to make more predictable? */
398 468471 : ulong sibling_idx = cancel_stack_idx;
399 468471 : cancel_stack_idx = fd_funk_txn_idx( map[ sibling_idx ].stack_cidx );
400 :
401 468471 : cancel_cnt += fd_funk_txn_cancel_family( funk, map, txn_max, tag, sibling_idx );
402 468471 : }
403 :
404 1161381 : return cancel_cnt;
405 1161381 : }
406 :
407 : ulong
408 : fd_funk_txn_cancel_siblings( fd_funk_t * funk,
409 : fd_funk_txn_t * txn,
410 0 : int verbose ) {
411 :
412 0 : if( FD_UNLIKELY( !funk ) ) {
413 0 : if( FD_UNLIKELY( verbose ) ) FD_LOG_WARNING(( "NULL funk" ));
414 0 : return 0UL;
415 0 : }
416 :
417 0 : fd_funk_txn_t * map = fd_funk_txn_map( funk, fd_funk_wksp( funk ) );
418 :
419 0 : ulong txn_max = funk->txn_max;
420 :
421 0 : ulong txn_idx = (ulong)(txn - map);
422 :
423 0 : if( FD_UNLIKELY( (txn_idx>=txn_max) /* Out of map (incl NULL) */ | (txn!=(map+txn_idx)) /* Bad alignment */ ) ) {
424 0 : if( FD_UNLIKELY( verbose ) ) FD_LOG_WARNING(( "txn is not a funk transaction" ));
425 0 : return 0UL;
426 0 : }
427 :
428 0 : ulong oldest_idx = fd_funk_txn_oldest_sibling( funk, map, txn_max, txn_idx );
429 :
430 0 : return fd_funk_txn_cancel_sibling_list( funk, map, txn_max, funk->cycle_tag++, oldest_idx, txn_idx );
431 0 : }
432 :
433 : ulong
434 : fd_funk_txn_cancel_children( fd_funk_t * funk,
435 : fd_funk_txn_t * txn,
436 0 : int verbose ) {
437 :
438 0 : if( FD_UNLIKELY( !funk ) ) {
439 0 : if( FD_UNLIKELY( verbose ) ) FD_LOG_WARNING(( "NULL funk" ));
440 0 : return 0UL;
441 0 : }
442 :
443 0 : fd_funk_txn_t * map = fd_funk_txn_map( funk, fd_funk_wksp( funk ) );
444 :
445 0 : ulong txn_max = funk->txn_max;
446 :
447 0 : ulong oldest_idx;
448 :
449 0 : if( FD_LIKELY( txn == NULL ) ) {
450 0 : oldest_idx = fd_funk_txn_idx( funk->child_head_cidx ); /* opt for non-compete */
451 0 : } else {
452 0 : ulong txn_idx = (ulong)(txn - map);
453 0 : if( FD_UNLIKELY( (txn_idx>=txn_max) /* Out of map */ | (txn!=(map+txn_idx)) /* Bad alignment */ ) ) {
454 0 : if( FD_UNLIKELY( verbose ) ) FD_LOG_WARNING(( "txn is not a funk transaction" ));
455 0 : return 0UL;
456 0 : }
457 :
458 0 : if( FD_UNLIKELY( !fd_funk_txn_map_query( map, fd_funk_txn_xid( txn ), NULL ) ) ) {
459 0 : if( FD_UNLIKELY( verbose ) ) FD_LOG_WARNING(( "txn is not in preparation" ));
460 0 : return 0UL;
461 0 : }
462 :
463 0 : oldest_idx = fd_funk_txn_idx( txn->child_head_cidx );
464 0 : }
465 :
466 0 : if( fd_funk_txn_idx_is_null( oldest_idx ) ) {
467 0 : return 0UL;
468 0 : }
469 :
470 0 : return fd_funk_txn_cancel_sibling_list( funk, map, txn_max, funk->cycle_tag++, oldest_idx, FD_FUNK_TXN_IDX_NULL );
471 0 : }
472 :
473 : /* Cancel all outstanding transactions */
474 :
475 : ulong
476 : fd_funk_txn_cancel_all( fd_funk_t * funk,
477 0 : int verbose ) {
478 0 : return fd_funk_txn_cancel_children( funk, NULL, verbose );
479 0 : }
480 :
481 : /* fd_funk_txn_update applies the record updates in transaction txn_idx
482 : to another transaction or the parent transaction. Callers have
483 : already validated our input arguments.
484 :
485 : On entry, the head/tail of the destination records are at
486 : *_dst_rec_head_idx / *_dst_rec_tail_idx. All transactions on this
487 : list will have transaction id dst_xid and vice versa. That is, this
488 : is the record list the last published transaction or txn_idx's
489 : in-prep parent transaction.
490 :
491 : On exit, the head/tail of the updated records is at
492 : *_dst_rec_head_idx / *_dst_rec_tail_idx. As before, all transactions
493 : on this list will have transaction id dst_xid and vice versa.
494 : Transaction txn_idx will have an _empty_ record list.
495 :
496 : Updates in the transaction txn_idx are processed from oldest to
497 : youngest. If an update erases an existing record in dest, the record
498 : to erase is removed from the destination records without perturbing
499 : the order of remaining destination records. If an update is to
500 : update an existing record, the destination record value is updated
501 : and the order of the destination records is unchanged. If an update
502 : is to create a new record, the record is appended to the list of
503 : existing values as youngest without changing the order of existing
504 : values. If an update erases a record in an in-prep parent, the
505 : erasure will be moved into the parent as the youngest without
506 : changing the order of existing values. */
507 :
508 : static void
509 : fd_funk_txn_update( ulong * _dst_rec_head_idx, /* Pointer to the dst list head */
510 : ulong * _dst_rec_tail_idx, /* Pointer to the dst list tail */
511 : ulong dst_txn_idx, /* Transaction index of the merge destination */
512 : fd_funk_txn_xid_t const * dst_xid, /* dst xid */
513 : ulong txn_idx, /* Transaction index of the records to merge */
514 : ulong rec_max, /* ==funk->rec_max */
515 : fd_funk_txn_t * txn_map, /* ==fd_funk_rec_map( funk, wksp ) */
516 : fd_funk_rec_t * rec_map, /* ==fd_funk_rec_map( funk, wksp ) */
517 : fd_funk_partvec_t * partvec, /* ==fd_funk_get_partvec( funk, wksp ) */
518 : fd_alloc_t * alloc, /* ==fd_funk_alloc( funk, wksp ) */
519 1161381 : fd_wksp_t * wksp ) { /* ==fd_funk_wksp( funk ) */
520 : /* We don't need to do all the individual removal pointer updates
521 : as we are removing the whole list from txn_idx. */
522 :
523 1161381 : ulong rec_idx = txn_map[ txn_idx ].rec_head_idx;
524 2724474 : while( !fd_funk_rec_idx_is_null( rec_idx ) ) {
525 : /* Validate rec_idx */
526 :
527 1563093 : if( FD_UNLIKELY( rec_idx>=rec_max ) ) FD_LOG_CRIT(( "memory corruption detected (bad idx)" ));
528 1563093 : if( FD_UNLIKELY( fd_funk_txn_idx( rec_map[ rec_idx ].txn_cidx )!=txn_idx ) )
529 0 : FD_LOG_CRIT(( "memory corruption detected (cycle or bad idx)" ));
530 :
531 1563093 : fd_funk_rec_t * rec = &rec_map[ rec_idx ];
532 1563093 : ulong next_rec_idx = rec->next_idx;
533 :
534 : /* See if (dst_xid,key) already exists. Remove it if it does, and then clean up the corpse.
535 : We can take advantage of the ordering property that children
536 : come before parents in the hash chain, and all elements with
537 : the same record key have the same hash. */
538 1563093 : ulong * next = &rec->map_next;
539 2058695 : for(;;) {
540 2058695 : ulong ele_idx = fd_funk_rec_map_private_unbox_idx( *next );
541 2058695 : if( fd_funk_rec_map_private_is_null( ele_idx ) ) break;
542 1938752 : fd_funk_rec_t * ele = rec_map + ele_idx;
543 :
544 1938752 : if( FD_LIKELY( rec->map_hash == ele->map_hash ) &&
545 1938752 : FD_LIKELY( fd_funk_rec_key_eq( rec->pair.key, ele->pair.key ) ) &&
546 1938752 : FD_LIKELY( fd_funk_txn_xid_eq( dst_xid, ele->pair.xid ) ) ) {
547 : /* Remove from the transaction */
548 1443150 : ulong prev_idx = ele->prev_idx;
549 1443150 : ulong next_idx = ele->next_idx;
550 1443150 : if( fd_funk_rec_idx_is_null( prev_idx ) ) {
551 72420 : *_dst_rec_head_idx = next_idx;
552 1370730 : } else {
553 1370730 : rec_map[ prev_idx ].next_idx = next_idx;
554 1370730 : }
555 1443150 : if( fd_funk_rec_idx_is_null( next_idx ) ) {
556 23253 : *_dst_rec_tail_idx = prev_idx;
557 1419897 : } else {
558 1419897 : rec_map[ next_idx ].prev_idx = prev_idx;
559 1419897 : }
560 : /* Clean up value */
561 1443150 : fd_funk_val_flush( ele, alloc, wksp );
562 1443150 : ele->txn_cidx = fd_funk_txn_cidx( FD_FUNK_TXN_IDX_NULL );
563 1443150 : fd_funk_part_set_intern( partvec, rec_map, ele, FD_FUNK_PART_NULL );
564 : /* Remove from record map */
565 1443150 : fd_funk_rec_map_private_t * priv = fd_funk_rec_map_private( rec_map );
566 1443150 : *next = ele->map_next;
567 1443150 : ele->map_next = priv->free_stack;
568 1443150 : priv->free_stack = (ele_idx | (1UL<<63));
569 1443150 : priv->key_cnt--;
570 1443150 : break;
571 1443150 : }
572 :
573 495602 : next = &ele->map_next;
574 495602 : }
575 :
576 : /* Add the new record to the transaction. We can update the xid in
577 : place because it is not used for hashing the element. We have
578 : to preserve the original element to preserve the
579 : newest-to-oldest ordering in the hash
580 : chain. fd_funk_rec_query_global relies on this subtle
581 : property. */
582 :
583 1563093 : rec->pair.xid[0] = *dst_xid;
584 1563093 : rec->txn_cidx = fd_funk_txn_cidx( dst_txn_idx );
585 :
586 1563093 : if( fd_funk_rec_idx_is_null( *_dst_rec_head_idx ) ) {
587 11805 : *_dst_rec_head_idx = rec_idx;
588 11805 : rec->prev_idx = FD_FUNK_REC_IDX_NULL;
589 1551288 : } else {
590 1551288 : rec_map[ *_dst_rec_tail_idx ].next_idx = rec_idx;
591 1551288 : rec->prev_idx = *_dst_rec_tail_idx;
592 1551288 : }
593 1563093 : *_dst_rec_tail_idx = rec_idx;
594 1563093 : rec->next_idx = FD_FUNK_REC_IDX_NULL;
595 :
596 1563093 : rec_idx = next_rec_idx;
597 1563093 : }
598 :
599 1161381 : txn_map[ txn_idx ].rec_head_idx = FD_FUNK_REC_IDX_NULL;
600 1161381 : txn_map[ txn_idx ].rec_tail_idx = FD_FUNK_REC_IDX_NULL;
601 1161381 : }
602 :
603 : /* fd_funk_txn_publish_funk_child publishes a transaction that is known
604 : to be a child of funk. Callers have already validated our input
605 : arguments. Returns FD_FUNK_SUCCESS on success and an FD_FUNK_ERR_*
606 : code on failure. (There are currently no failure cases but the
607 : plumbing is there if value handling requires it at some point.) */
608 :
609 : static int
610 : fd_funk_txn_publish_funk_child( fd_funk_t * funk,
611 : fd_funk_txn_t * map,
612 : ulong txn_max,
613 : ulong tag,
614 723522 : ulong txn_idx ) {
615 :
616 723522 : fd_funk_check_write( funk );
617 :
618 : /* Apply the updates in txn to the last published transactions */
619 :
620 723522 : fd_wksp_t * wksp = fd_funk_wksp( funk );
621 723522 : fd_funk_txn_update( &funk->rec_head_idx, &funk->rec_tail_idx, FD_FUNK_TXN_IDX_NULL, fd_funk_root( funk ),
622 723522 : txn_idx, funk->rec_max, map, fd_funk_rec_map( funk, wksp ), fd_funk_get_partvec( funk, wksp ),
623 723522 : fd_funk_alloc( funk, wksp ), wksp );
624 :
625 : /* Cancel all competing transaction histories */
626 :
627 723522 : ulong oldest_idx = fd_funk_txn_oldest_sibling( funk, map, txn_max, txn_idx );
628 723522 : fd_funk_txn_cancel_sibling_list( funk, map, txn_max, tag, oldest_idx, txn_idx );
629 :
630 : /* Make all the children children of funk */
631 :
632 723522 : ulong child_head_idx = fd_funk_txn_idx( map[ txn_idx ].child_head_cidx );
633 723522 : ulong child_tail_idx = fd_funk_txn_idx( map[ txn_idx ].child_tail_cidx );
634 :
635 723522 : ulong child_idx = child_head_idx;
636 1241010 : while( FD_UNLIKELY( !fd_funk_txn_idx_is_null( child_idx ) ) ) { /* opt for incr pub */
637 :
638 517488 : ASSERT_IN_PREP ( child_idx );
639 517488 : ASSERT_UNTAGGED( child_idx );
640 517488 : map[ child_idx ].tag = tag;
641 :
642 517488 : map[ child_idx ].parent_cidx = fd_funk_txn_cidx( FD_FUNK_TXN_IDX_NULL );
643 :
644 517488 : child_idx = fd_funk_txn_idx( map[ child_idx ].sibling_next_cidx );
645 517488 : }
646 :
647 723522 : funk->child_head_cidx = fd_funk_txn_cidx( child_head_idx );
648 723522 : funk->child_tail_cidx = fd_funk_txn_cidx( child_tail_idx );
649 :
650 : /* Remove the mapping */
651 :
652 723522 : fd_funk_txn_xid_copy( funk->last_publish, fd_funk_txn_xid( &map[ txn_idx ] ) );
653 :
654 723522 : fd_funk_txn_map_remove( map, fd_funk_txn_xid( &map[ txn_idx ] ) );
655 :
656 723522 : return FD_FUNK_SUCCESS;
657 723522 : }
658 :
659 : ulong
660 : fd_funk_txn_publish( fd_funk_t * funk,
661 : fd_funk_txn_t * txn,
662 1573926 : int verbose ) {
663 :
664 1573926 : if( FD_UNLIKELY( !funk ) ) {
665 196464 : if( FD_UNLIKELY( verbose ) ) FD_LOG_WARNING(( "NULL funk" ));
666 196464 : return 0UL;
667 196464 : }
668 :
669 1377462 : fd_wksp_t * wksp = fd_funk_wksp( funk );
670 :
671 1377462 : fd_funk_txn_t * map = fd_funk_txn_map( funk, wksp );
672 :
673 1377462 : ulong txn_max = funk->txn_max;
674 :
675 1377462 : ulong txn_idx = (ulong)(txn - map);
676 :
677 1377462 : if( FD_UNLIKELY( (txn_idx>=txn_max) /* Out of map (incl NULL) */ | (txn!=(map+txn_idx)) /* Bad alignment */ ) ) {
678 786372 : if( FD_UNLIKELY( verbose ) ) FD_LOG_WARNING(( "txn is not a funk transaction" ));
679 786372 : return 0UL;
680 786372 : }
681 :
682 591090 : if( FD_UNLIKELY( !fd_funk_txn_map_query( map, fd_funk_txn_xid( txn ), NULL ) ) ) {
683 188382 : if( FD_UNLIKELY( verbose ) ) FD_LOG_WARNING(( "txn is not in preparation" ));
684 188382 : return 0UL;
685 188382 : }
686 :
687 402708 : ulong tag = funk->cycle_tag++;
688 :
689 402708 : ulong publish_stack_idx = FD_FUNK_TXN_IDX_NULL;
690 :
691 723522 : for(;;) {
692 723522 : map[ txn_idx ].tag = tag;
693 :
694 : /* At this point, txn_idx is a transaction that needs to be
695 : published and has been tagged. If txn is a child of funk, we are
696 : ready to publish txn and everything on the publish stack. */
697 :
698 723522 : ulong parent_idx = fd_funk_txn_idx( map[ txn_idx ].parent_cidx );
699 723522 : if( FD_LIKELY( fd_funk_txn_idx_is_null( parent_idx ) ) ) break; /* opt for incr pub */
700 :
701 : /* txn_idx has a parent. Validate and tag it. Push txn to the
702 : publish stack and recurse into the parent. */
703 :
704 320814 : ASSERT_IN_PREP ( parent_idx );
705 320814 : ASSERT_UNTAGGED( parent_idx );
706 :
707 320814 : map[ txn_idx ].stack_cidx = fd_funk_txn_cidx( publish_stack_idx );
708 320814 : publish_stack_idx = txn_idx;
709 :
710 320814 : txn_idx = parent_idx;
711 320814 : }
712 :
713 402708 : ulong publish_cnt = 0UL;
714 :
715 723522 : for(;;) {
716 :
717 : /* At this point, all the transactions we need to publish are
718 : tagged, txn is the next up publish funk and publish_stack has the
719 : transactions to follow in order by pop. We use a new tag for
720 : each publish as txn and its siblings we potentially visited in a
721 : previous iteration of this loop. */
722 :
723 723522 : if( FD_UNLIKELY( fd_funk_txn_publish_funk_child( funk, map, txn_max, funk->cycle_tag++, txn_idx ) ) ) break;
724 723522 : publish_cnt++;
725 :
726 723522 : txn_idx = publish_stack_idx;
727 723522 : if( FD_LIKELY( fd_funk_txn_idx_is_null( txn_idx ) ) ) break; /* opt for incr pub */
728 320814 : publish_stack_idx = fd_funk_txn_idx( map[ txn_idx ].stack_cidx );
729 320814 : }
730 :
731 402708 : return publish_cnt;
732 402708 : }
733 :
734 : int
735 : fd_funk_txn_publish_into_parent( fd_funk_t * funk,
736 : fd_funk_txn_t * txn,
737 437859 : int verbose ) {
738 437859 : if( FD_UNLIKELY( !funk ) ) {
739 0 : if( FD_UNLIKELY( verbose ) ) FD_LOG_WARNING(( "NULL funk" ));
740 0 : return FD_FUNK_ERR_INVAL;
741 0 : }
742 437859 : fd_funk_check_write( funk );
743 :
744 437859 : fd_wksp_t * wksp = fd_funk_wksp( funk );
745 :
746 437859 : fd_funk_txn_t * map = fd_funk_txn_map( funk, wksp );
747 :
748 437859 : ulong txn_idx = (ulong)(txn - map);
749 :
750 437859 : ulong oldest_idx = fd_funk_txn_oldest_sibling( funk, map, funk->txn_max, txn_idx );
751 437859 : fd_funk_txn_cancel_sibling_list( funk, map, funk->txn_max, funk->cycle_tag++, oldest_idx, txn_idx );
752 :
753 437859 : ulong parent_idx = fd_funk_txn_idx( txn->parent_cidx );
754 437859 : if( fd_funk_txn_idx_is_null( parent_idx ) ) {
755 : /* Publish to root */
756 6408 : if( fd_funk_txn_idx( funk->child_head_cidx ) != txn_idx || fd_funk_txn_idx( funk->child_tail_cidx ) != txn_idx )
757 0 : FD_LOG_CRIT(( "memory corruption detected (cycle or bad idx)" ));
758 6408 : fd_funk_txn_update( &funk->rec_head_idx, &funk->rec_tail_idx, FD_FUNK_TXN_IDX_NULL, fd_funk_root( funk ),
759 6408 : txn_idx, funk->rec_max, map, fd_funk_rec_map( funk, wksp ), fd_funk_get_partvec( funk, wksp ),
760 6408 : fd_funk_alloc( funk, wksp ), wksp );
761 : /* Inherit the children */
762 6408 : funk->child_head_cidx = txn->child_head_cidx;
763 6408 : funk->child_tail_cidx = txn->child_tail_cidx;
764 431451 : } else {
765 431451 : fd_funk_txn_t * parent_txn = map + parent_idx;
766 431451 : if( fd_funk_txn_idx( parent_txn->child_head_cidx ) != txn_idx || fd_funk_txn_idx( parent_txn->child_tail_cidx ) != txn_idx )
767 0 : FD_LOG_CRIT(( "memory corruption detected (cycle or bad idx)" ));
768 431451 : fd_funk_txn_update( &parent_txn->rec_head_idx, &parent_txn->rec_tail_idx, parent_idx, &parent_txn->xid,
769 431451 : txn_idx, funk->rec_max, map, fd_funk_rec_map( funk, wksp ), fd_funk_get_partvec( funk, wksp ),
770 431451 : fd_funk_alloc( funk, wksp ), wksp );
771 : /* Inherit the children */
772 431451 : parent_txn->child_head_cidx = txn->child_head_cidx;
773 431451 : parent_txn->child_tail_cidx = txn->child_tail_cidx;
774 431451 : }
775 :
776 : /* Adjust the parent pointers of the children to point to their grandparent */
777 437859 : ulong child_idx = fd_funk_txn_idx( txn->child_head_cidx );
778 461478 : while( FD_UNLIKELY( !fd_funk_txn_idx_is_null( child_idx ) ) ) {
779 23619 : map[ child_idx ].parent_cidx = fd_funk_txn_cidx( parent_idx );
780 23619 : child_idx = fd_funk_txn_idx( map[ child_idx ].sibling_next_cidx );
781 23619 : }
782 :
783 437859 : fd_funk_txn_map_remove( map, fd_funk_txn_xid( txn ) );
784 :
785 437859 : return FD_FUNK_SUCCESS;
786 437859 : }
787 :
788 : /* Unfortunately, the semantics of how to deal with the same record
789 : key appearing in multiple children is not defined. So, for now,
790 : this API is commented out. */
791 : #if 0
792 : int
793 : fd_funk_txn_merge_all_children( fd_funk_t * funk,
794 : fd_funk_txn_t * parent_txn,
795 : int verbose ) {
796 : if( FD_UNLIKELY( !funk ) ) {
797 : if( FD_UNLIKELY( verbose ) ) FD_LOG_WARNING(( "NULL funk" ));
798 : return FD_FUNK_ERR_INVAL;
799 : }
800 : fd_funk_check_write( funk );
801 :
802 : fd_wksp_t * wksp = fd_funk_wksp( funk );
803 :
804 : fd_funk_txn_t * map = fd_funk_txn_map( funk, wksp );
805 : ulong txn_max = funk->txn_max; /* Previously verified */
806 :
807 : ulong parent_idx;
808 : fd_funk_txn_xid_t * parent_xid;
809 : uint * child_head_cidx;
810 : uint * child_tail_cidx;
811 : ulong * rec_head_idx;
812 : ulong * rec_tail_idx;
813 : if( parent_txn == NULL ) { /* Root */
814 : parent_idx = FD_FUNK_TXN_IDX_NULL;
815 : parent_xid = funk->root;
816 : child_head_cidx = &funk->child_head_cidx;
817 : child_tail_cidx = &funk->child_tail_cidx;
818 : rec_head_idx = &funk->rec_head_idx;
819 : rec_tail_idx = &funk->rec_tail_idx;
820 : } else {
821 : parent_idx = (ulong)(parent_txn - map);
822 : ASSERT_IN_PREP( parent_idx );
823 : parent_xid = &parent_txn->xid;
824 : child_head_cidx = &parent_txn->child_head_cidx;
825 : child_tail_cidx = &parent_txn->child_tail_cidx;
826 : rec_head_idx = &parent_txn->rec_head_idx;
827 : rec_tail_idx = &parent_txn->rec_tail_idx;
828 : }
829 :
830 : ulong child_head_idx = fd_funk_txn_idx( *child_head_cidx );
831 : ulong child_idx = child_head_idx;
832 : while( FD_UNLIKELY( !fd_funk_txn_idx_is_null( child_idx ) ) ) { /* opt for incr pub */
833 : /* Merge records from child into parent */
834 :
835 : fd_funk_txn_t * txn = &map[ child_idx ];
836 : if( FD_UNLIKELY( !fd_funk_txn_idx_is_null( fd_funk_txn_idx( txn->child_head_cidx ) ) ) ) {
837 : FD_LOG_WARNING(("cannot call fd_funk_txn_merge_all_children if parent_txn has grandchildren"));
838 : return FD_FUNK_ERR_TXN;
839 : }
840 :
841 : fd_funk_txn_update( rec_head_idx, rec_tail_idx, parent_idx, parent_xid,
842 : child_idx, funk->rec_max, map, fd_funk_rec_map( funk, wksp ), fd_funk_get_partvec( funk, wksp ),
843 : fd_funk_alloc( funk, wksp ), wksp );
844 :
845 : child_idx = fd_funk_txn_idx( txn->sibling_next_cidx );
846 : fd_funk_txn_map_remove( map, fd_funk_txn_xid( txn ) );
847 :
848 : /* Update the pointers as we go in case we stop in the middle
849 : */
850 : *child_head_cidx = fd_funk_txn_cidx( child_idx );
851 : if( FD_UNLIKELY( !fd_funk_txn_idx_is_null( child_idx ) ) ) {
852 : map[ child_idx ].sibling_prev_cidx = fd_funk_txn_cidx( FD_FUNK_TXN_IDX_NULL );
853 : }
854 : }
855 :
856 : *child_tail_cidx = fd_funk_txn_cidx( FD_FUNK_TXN_IDX_NULL );
857 :
858 : return FD_FUNK_SUCCESS;
859 : }
860 : #endif
861 :
862 : /* Return the first record in a transaction. Returns NULL if the
863 : transaction has no records yet. */
864 :
865 : FD_FN_PURE fd_funk_rec_t const *
866 : fd_funk_txn_first_rec( fd_funk_t * funk,
867 5268909 : fd_funk_txn_t const * txn ) {
868 5268909 : ulong rec_idx;
869 5268909 : if( FD_UNLIKELY( NULL == txn ))
870 255000 : rec_idx = funk->rec_head_idx;
871 5013909 : else
872 5013909 : rec_idx = txn->rec_head_idx;
873 5268909 : if( fd_funk_rec_idx_is_null( rec_idx ) ) return NULL;
874 3231006 : fd_funk_rec_t const * rec_map = fd_funk_rec_map( funk, fd_funk_wksp( funk ) );
875 3231006 : return rec_map + rec_idx;
876 5268909 : }
877 :
878 : /* Return the next record in a transaction. Returns NULL if the
879 : transaction has no more records. */
880 :
881 : FD_FN_PURE fd_funk_rec_t const *
882 : fd_funk_txn_next_rec( fd_funk_t * funk,
883 46743843 : fd_funk_rec_t const * rec ) {
884 46743843 : ulong rec_idx = rec->next_idx;
885 46743843 : if( fd_funk_rec_idx_is_null( rec_idx ) ) return NULL;
886 43512837 : fd_funk_rec_t const * rec_map = fd_funk_rec_map( funk, fd_funk_wksp( funk ) );
887 43512837 : return rec_map + rec_idx;
888 46743843 : }
889 :
890 : fd_funk_txn_xid_t
891 21280944 : fd_funk_generate_xid(void) {
892 21280944 : fd_funk_txn_xid_t xid;
893 21280944 : static FD_TL ulong seq = 0;
894 21280944 : xid.ul[0] =
895 21280944 : (fd_log_cpu_id() + 1U)*3138831853UL +
896 21280944 : (fd_log_thread_id() + 1U)*9180195821UL +
897 21280944 : (++seq)*6208101967UL;
898 21280944 : xid.ul[1] = ((ulong)fd_tickcount())*2810745731UL;
899 21280944 : return xid;
900 21280944 : }
901 :
902 : int
903 22275108 : fd_funk_txn_verify( fd_funk_t * funk ) {
904 22275108 : fd_wksp_t * wksp = fd_funk_wksp( funk ); /* Previously verified */
905 22275108 : fd_funk_txn_t * map = fd_funk_txn_map( funk, wksp ); /* Previously verified */
906 22275108 : ulong txn_max = funk->txn_max; /* Previously verified */
907 :
908 22275108 : ulong funk_child_head_idx = fd_funk_txn_idx( funk->child_head_cidx ); /* Previously verified */
909 22275108 : ulong funk_child_tail_idx = fd_funk_txn_idx( funk->child_tail_cidx ); /* Previously verified */
910 :
911 22275108 : fd_funk_txn_xid_t const * last_publish = funk->last_publish; /* Previously verified */
912 :
913 745948386 : # define TEST(c) do { \
914 745948386 : if( FD_UNLIKELY( !(c) ) ) { FD_LOG_WARNING(( "FAIL: %s", #c )); return FD_FUNK_ERR_INVAL; } \
915 745948386 : } while(0)
916 :
917 22275108 : # define IS_VALID( idx ) ( (idx==FD_FUNK_TXN_IDX_NULL) || \
918 22275108 : ((idx<txn_max) && (!fd_funk_txn_xid_eq( fd_funk_txn_xid( &map[idx] ), last_publish ))) )
919 :
920 22275108 : TEST( !fd_funk_txn_map_verify( map ) );
921 :
922 22275108 : ulong free_cnt = txn_max - fd_funk_txn_map_key_cnt( map );
923 :
924 : /* Tag all transactions as not visited yet */
925 :
926 761131044 : for( ulong txn_idx=0UL; txn_idx<txn_max; txn_idx++ ) map[ txn_idx ].tag = 0UL;
927 :
928 : /* Visit all transactions in preparation, traversing from oldest to
929 : youngest. */
930 :
931 22275108 : ulong prep_cnt = 0UL;
932 22275108 : do {
933 :
934 : /* Push all children of funk to the stack */
935 :
936 22275108 : ulong stack_idx = FD_FUNK_TXN_IDX_NULL;
937 22275108 : ulong child_idx = funk_child_head_idx;
938 52164405 : while( !fd_funk_txn_idx_is_null( child_idx ) ) {
939 :
940 : /* Make sure valid idx, not tagged (detects cycles) and child
941 : knows it is a child of funk. Then tag as visited / in-prep,
942 : push to stack and update prep_cnt */
943 :
944 29889297 : TEST( IS_VALID( child_idx ) );
945 29889297 : TEST( !map[ child_idx ].tag );
946 29889297 : TEST( fd_funk_txn_idx_is_null( fd_funk_txn_idx( map[ child_idx ].parent_cidx ) ) );
947 29889297 : map[ child_idx ].tag = 1UL;
948 29889297 : map[ child_idx ].stack_cidx = fd_funk_txn_cidx( stack_idx );
949 29889297 : stack_idx = child_idx;
950 29889297 : prep_cnt++;
951 :
952 29889297 : ulong next_idx = fd_funk_txn_idx( map[ child_idx ].sibling_next_cidx );
953 29889297 : if( !fd_funk_txn_idx_is_null( next_idx ) ) TEST( fd_funk_txn_idx( map[ next_idx ].sibling_prev_cidx )==child_idx );
954 29889297 : child_idx = next_idx;
955 29889297 : }
956 :
957 119006091 : while( !fd_funk_txn_idx_is_null( stack_idx ) ) {
958 :
959 : /* Pop the next transaction to traverse */
960 :
961 96730983 : ulong txn_idx = stack_idx;
962 96730983 : stack_idx = fd_funk_txn_idx( map[ txn_idx ].stack_cidx );
963 :
964 : /* Push all children of txn to the stack */
965 :
966 96730983 : ulong child_idx = fd_funk_txn_idx( map[ txn_idx ].child_head_cidx );
967 163572669 : while( !fd_funk_txn_idx_is_null( child_idx ) ) {
968 :
969 : /* Make sure valid idx, not tagged (detects cycles) and child
970 : knows it is a child of txn_idx. Then tag as visited /
971 : in-prep, push to stack and update prep_cnt */
972 :
973 66841686 : TEST( IS_VALID( child_idx ) );
974 66841686 : TEST( !map[ child_idx ].tag );
975 66841686 : TEST( fd_funk_txn_idx( map[ child_idx ].parent_cidx )==txn_idx );
976 66841686 : map[ child_idx ].tag = 1UL;
977 66841686 : map[ child_idx ].stack_cidx = fd_funk_txn_cidx( stack_idx );
978 66841686 : stack_idx = child_idx;
979 66841686 : prep_cnt++;
980 :
981 66841686 : ulong next_idx = fd_funk_txn_idx( map[ child_idx ].sibling_next_cidx );
982 66841686 : if( !fd_funk_txn_idx_is_null( next_idx ) ) TEST( fd_funk_txn_idx( map[ next_idx ].sibling_prev_cidx )==child_idx );
983 66841686 : child_idx = next_idx;
984 66841686 : }
985 96730983 : }
986 :
987 22275108 : } while(0);
988 :
989 22275108 : TEST( (free_cnt+prep_cnt)==txn_max );
990 :
991 : /* Do it again with a youngest to oldest traversal to test reverse
992 : link integrity */
993 :
994 22275108 : prep_cnt = 0UL;
995 22275108 : do {
996 :
997 : /* Push all children of funk to the stack */
998 :
999 22275108 : ulong stack_idx = FD_FUNK_TXN_IDX_NULL;
1000 22275108 : ulong child_idx = funk_child_tail_idx;
1001 52164405 : while( !fd_funk_txn_idx_is_null( child_idx ) ) {
1002 :
1003 : /* Make sure valid idx, tagged as visited above (detects cycles)
1004 : and child knows it is a child of funk. Then tag as visited /
1005 : in-prep, push to stack and update prep_cnt */
1006 :
1007 29889297 : TEST( IS_VALID( child_idx ) );
1008 29889297 : TEST( map[ child_idx ].tag==1UL );
1009 29889297 : TEST( fd_funk_txn_idx_is_null( fd_funk_txn_idx( map[ child_idx ].parent_cidx ) ) );
1010 29889297 : map[ child_idx ].tag = 2UL;
1011 29889297 : map[ child_idx ].stack_cidx = fd_funk_txn_cidx( stack_idx );
1012 29889297 : stack_idx = child_idx;
1013 29889297 : prep_cnt++;
1014 :
1015 29889297 : ulong prev_idx = fd_funk_txn_idx( map[ child_idx ].sibling_prev_cidx );
1016 29889297 : if( !fd_funk_txn_idx_is_null( prev_idx ) ) TEST( fd_funk_txn_idx( map[ prev_idx ].sibling_next_cidx )==child_idx );
1017 29889297 : child_idx = prev_idx;
1018 29889297 : }
1019 :
1020 119006091 : while( !fd_funk_txn_idx_is_null( stack_idx ) ) {
1021 :
1022 : /* Pop the next transaction to traverse */
1023 :
1024 96730983 : ulong txn_idx = stack_idx;
1025 96730983 : stack_idx = fd_funk_txn_idx( map[ txn_idx ].stack_cidx );
1026 :
1027 : /* Push all children of txn to the stack */
1028 :
1029 96730983 : ulong child_idx = fd_funk_txn_idx( map[ txn_idx ].child_tail_cidx );
1030 163572669 : while( !fd_funk_txn_idx_is_null( child_idx ) ) {
1031 :
1032 : /* Make sure valid idx, tagged as visited above (detects cycles)
1033 : and child knows it is a child of txn_idx. Then, tag as
1034 : visited / in-prep, push to stack and update prep_cnt */
1035 :
1036 66841686 : TEST( IS_VALID( child_idx ) );
1037 66841686 : TEST( map[ child_idx ].tag==1UL );
1038 66841686 : TEST( fd_funk_txn_idx( map[ child_idx ].parent_cidx )==txn_idx );
1039 66841686 : map[ child_idx ].tag = 2UL;
1040 66841686 : map[ child_idx ].stack_cidx = fd_funk_txn_cidx( stack_idx );
1041 66841686 : stack_idx = child_idx;
1042 66841686 : prep_cnt++;
1043 :
1044 66841686 : ulong prev_idx = fd_funk_txn_idx( map[ child_idx ].sibling_prev_cidx );
1045 66841686 : if( !fd_funk_txn_idx_is_null( prev_idx ) ) TEST( fd_funk_txn_idx( map[ prev_idx ].sibling_next_cidx )==child_idx );
1046 66841686 : child_idx = prev_idx;
1047 66841686 : }
1048 96730983 : }
1049 22275108 : } while(0);
1050 :
1051 22275108 : TEST( (free_cnt+prep_cnt)==txn_max );
1052 :
1053 22275108 : TEST( fd_funk_txn_cnt( map )==prep_cnt );
1054 :
1055 22275108 : # undef IS_VALID
1056 22275108 : # undef TEST
1057 :
1058 22275108 : return FD_FUNK_SUCCESS;
1059 22275108 : }
1060 :
1061 : #undef ASSERT_UNTAGGED
1062 : #undef ASSERT_IN_PREP
1063 : #undef ASSERT_IN_MAP
|
