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 1720807782 : #define MAP_T fd_funk_txn_t
7 : #define MAP_KEY_T fd_funk_txn_xid_t
8 2547906 : #define MAP_KEY xid
9 : #define MAP_KEY_EQ(k0,k1) fd_funk_txn_xid_eq((k0),(k1))
10 858799176 : #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 1376335325 : #define MAP_NEXT map_next
13 2024801844 : #define MAP_HASH map_hash
14 110571 : #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 : a 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 2547906 : #define ASSERT_IN_MAP( txn_idx ) do { \
52 2547906 : if( FD_UNLIKELY( txn_idx>=txn_max ) ) \
53 2547906 : FD_LOG_CRIT(( "memory corruption detected (bad_idx)" )); \
54 2547906 : } while(0)
55 :
56 4737072 : #define ASSERT_IN_PREP( txn_idx ) do { \
57 4737072 : if( FD_UNLIKELY( txn_idx>=txn_max ) ) \
58 4737072 : FD_LOG_CRIT(( "memory corruption detected (bad_idx)" )); \
59 4737072 : if( FD_UNLIKELY( !fd_funk_txn_map_query( map, fd_funk_txn_xid( &map[ txn_idx ] ), NULL ) ) ) \
60 4737072 : FD_LOG_CRIT(( "memory corruption detected (not in prep)" )); \
61 4737072 : } while(0)
62 :
63 2097456 : #define ASSERT_UNTAGGED( txn_idx ) do { \
64 2097456 : if( FD_UNLIKELY( map[ txn_idx ].tag==tag ) ) \
65 2097456 : FD_LOG_CRIT(( "memory corruption detected (cycle)" )); \
66 2097456 : } 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 3784281 : int verbose ) {
73 :
74 3784281 : if( FD_UNLIKELY( !funk ) ) {
75 196464 : if( FD_UNLIKELY( verbose ) ) FD_LOG_WARNING(( "NULL funk" ));
76 196464 : return NULL;
77 196464 : }
78 3587817 : fd_funk_check_write( funk );
79 :
80 3587817 : fd_funk_txn_t * map = fd_funk_txn_map( funk, fd_funk_wksp( funk ) );
81 :
82 3587817 : 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 3587793 : ulong txn_max = funk->txn_max;
88 :
89 3587793 : ulong parent_idx;
90 3587793 : uint * _child_head_cidx;
91 3587793 : uint * _child_tail_cidx;
92 :
93 3587793 : if( FD_LIKELY( !parent ) ) { /* opt for incr pub */
94 :
95 1735311 : parent_idx = FD_FUNK_TXN_IDX_NULL;
96 :
97 1735311 : _child_head_cidx = &funk->child_head_cidx;
98 1735311 : _child_tail_cidx = &funk->child_tail_cidx;
99 :
100 1852482 : } else {
101 :
102 1852482 : parent_idx = (ulong)(parent - map);
103 :
104 1852482 : 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 1656021 : 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 1467639 : _child_head_cidx = &parent->child_head_cidx;
115 1467639 : _child_tail_cidx = &parent->child_tail_cidx;
116 :
117 1467639 : }
118 :
119 3202950 : if( FD_UNLIKELY( !xid ) ) {
120 196461 : if( FD_UNLIKELY( verbose ) ) FD_LOG_WARNING(( "NULL xid" ));
121 196461 : return NULL;
122 196461 : }
123 :
124 3006489 : 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 3006483 : 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 2810028 : 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 2547906 : fd_funk_txn_t * txn = fd_funk_txn_map_insert( map, xid );
142 2547906 : ulong txn_idx = (ulong)(txn - map);
143 2547906 : ASSERT_IN_MAP( txn_idx );
144 :
145 : /* Join the family */
146 :
147 2547906 : ulong sibling_prev_idx = fd_funk_txn_idx( *_child_tail_cidx );
148 :
149 2547906 : int first_born = fd_funk_txn_idx_is_null( sibling_prev_idx );
150 2547906 : if( FD_UNLIKELY( !first_born ) ) ASSERT_IN_PREP( sibling_prev_idx ); /* opt for non-compete */
151 :
152 2547906 : txn->parent_cidx = fd_funk_txn_cidx( parent_idx );
153 2547906 : txn->child_head_cidx = fd_funk_txn_cidx( FD_FUNK_TXN_IDX_NULL );
154 2547906 : txn->child_tail_cidx = fd_funk_txn_cidx( FD_FUNK_TXN_IDX_NULL );
155 2547906 : txn->sibling_prev_cidx = fd_funk_txn_cidx( sibling_prev_idx );
156 2547906 : txn->sibling_next_cidx = fd_funk_txn_cidx( FD_FUNK_TXN_IDX_NULL );
157 2547906 : txn->stack_cidx = fd_funk_txn_cidx( FD_FUNK_TXN_IDX_NULL );
158 2547906 : txn->tag = 0UL;
159 :
160 2547906 : txn->rec_head_idx = FD_FUNK_REC_IDX_NULL;
161 2547906 : txn->rec_tail_idx = FD_FUNK_REC_IDX_NULL;
162 :
163 : /* TODO: consider branchless impl */
164 2547906 : if( FD_LIKELY( first_born ) ) *_child_head_cidx = fd_funk_txn_cidx( txn_idx ); /* opt for non-compete */
165 499149 : else map[ sibling_prev_idx ].sibling_next_cidx = fd_funk_txn_cidx( txn_idx );
166 :
167 2547906 : *_child_tail_cidx = fd_funk_txn_cidx( txn_idx );
168 :
169 2547906 : return txn;
170 2547906 : }
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 1772601 : ulong txn_idx ) {
183 :
184 1772601 : 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 1772601 : fd_wksp_t * wksp = fd_funk_wksp ( funk );
193 1772601 : fd_alloc_t * alloc = fd_funk_alloc ( funk, wksp );
194 1772601 : fd_funk_rec_t * rec_map = fd_funk_rec_map( funk, wksp );
195 1772601 : fd_funk_partvec_t * partvec = fd_funk_get_partvec( funk, wksp );
196 1772601 : ulong rec_max = funk->rec_max;
197 :
198 1772601 : ulong rec_idx = map[ txn_idx ].rec_head_idx;
199 5789493 : while( !fd_funk_rec_idx_is_null( rec_idx ) ) {
200 :
201 4016892 : if( FD_UNLIKELY( rec_idx>=rec_max ) ) FD_LOG_CRIT(( "memory corruption detected (bad idx)" ));
202 4016892 : 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 4016892 : ulong next_idx = rec_map[ rec_idx ].next_idx;
206 4016892 : rec_map[ rec_idx ].txn_cidx = fd_funk_txn_cidx( FD_FUNK_TXN_IDX_NULL );
207 :
208 4016892 : fd_funk_val_flush( &rec_map[ rec_idx ], alloc, wksp );
209 4016892 : fd_funk_part_set_intern( partvec, rec_map, &rec_map[ rec_idx ], FD_FUNK_PART_NULL );
210 :
211 4016892 : fd_funk_rec_map_remove( rec_map, fd_funk_rec_pair( &rec_map[ rec_idx ] ) );
212 :
213 4016892 : rec_idx = next_idx;
214 4016892 : }
215 :
216 : /* Leave the family */
217 :
218 1772601 : ulong sibling_prev_idx = fd_funk_txn_idx( map[ txn_idx ].sibling_prev_cidx );
219 1772601 : ulong sibling_next_idx = fd_funk_txn_idx( map[ txn_idx ].sibling_next_cidx );
220 :
221 : /* TODO: Consider branchless impl */
222 :
223 1772601 : if( FD_LIKELY( fd_funk_txn_idx_is_null( sibling_prev_idx ) ) ) { /* opt for non-compete */
224 1375761 : ulong parent_idx = fd_funk_txn_idx( map[ txn_idx ].parent_cidx );
225 1375761 : if( FD_LIKELY( fd_funk_txn_idx_is_null( parent_idx ) ) ) { /* No older sib and is a funk child, opt for incr pub */
226 695607 : funk->child_head_cidx = fd_funk_txn_cidx( sibling_next_idx );
227 695607 : } else { /* No older sib and has parent */
228 680154 : ASSERT_IN_PREP( parent_idx );
229 680154 : map[ parent_idx ].child_head_cidx = fd_funk_txn_cidx( sibling_next_idx );
230 680154 : }
231 1375761 : } else { /* Has older sib */
232 396840 : ASSERT_IN_PREP( sibling_prev_idx );
233 396840 : map[ sibling_prev_idx ].sibling_next_cidx = fd_funk_txn_cidx( sibling_next_idx );
234 396840 : }
235 :
236 1772601 : if( FD_LIKELY( fd_funk_txn_idx_is_null( sibling_next_idx ) ) ) { /* opt for non-compete */
237 1604259 : ulong parent_idx = fd_funk_txn_idx( map[ txn_idx ].parent_cidx );
238 1604259 : if( FD_LIKELY( fd_funk_txn_idx_is_null( parent_idx ) ) ) { /* No younger sib and is a funk child, opt for incr pub */
239 820449 : funk->child_tail_cidx = fd_funk_txn_cidx( sibling_prev_idx );
240 820449 : } else { /* No younger sib and has parent */
241 783810 : ASSERT_IN_PREP( parent_idx );
242 783810 : map[ parent_idx ].child_tail_cidx = fd_funk_txn_cidx( sibling_prev_idx );
243 783810 : }
244 1604259 : } else { /* Has younger sib */
245 168342 : ASSERT_IN_PREP( sibling_next_idx );
246 168342 : map[ sibling_next_idx ].sibling_prev_cidx = fd_funk_txn_cidx( sibling_prev_idx );
247 168342 : }
248 :
249 1772601 : fd_funk_txn_map_remove( map, fd_funk_txn_xid( &map[ txn_idx ] ) );
250 1772601 : }
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 1466112 : ulong txn_idx ) {
263 1466112 : ulong cancel_cnt = 0UL;
264 :
265 1466112 : map[ txn_idx ].tag = tag;
266 :
267 1466112 : ulong parent_stack_idx = FD_FUNK_TXN_IDX_NULL;
268 :
269 2079090 : for(;;) {
270 :
271 : /* At this point, txn_idx appears to be valid and has been tagged. */
272 :
273 2079090 : ulong youngest_idx = fd_funk_txn_idx( map[ txn_idx ].child_tail_cidx );
274 2079090 : if( FD_LIKELY( fd_funk_txn_idx_is_null( youngest_idx ) ) ) { /* txn is is childless, opt for incr pub */
275 :
276 1772601 : fd_funk_txn_cancel_childless( funk, map, txn_max, txn_idx ); /* If this can fail, return cancel_cnt here on fail */
277 1772601 : cancel_cnt++;
278 :
279 1772601 : txn_idx = parent_stack_idx; /* Pop the parent stack */
280 1772601 : if( FD_LIKELY( fd_funk_txn_idx_is_null( txn_idx ) ) ) break; /* If stack is empty, we are done, opt for incr pub */
281 306489 : parent_stack_idx = fd_funk_txn_idx( map[ txn_idx ].stack_cidx );
282 306489 : continue;
283 1772601 : }
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 306489 : ASSERT_IN_PREP ( youngest_idx );
290 306489 : ASSERT_UNTAGGED( youngest_idx );
291 306489 : map[ youngest_idx ].tag = tag;
292 :
293 306489 : map[ txn_idx ].stack_cidx = fd_funk_txn_cidx( parent_stack_idx );
294 306489 : parent_stack_idx = txn_idx;
295 :
296 306489 : txn_idx = youngest_idx;
297 306489 : }
298 :
299 1466112 : return cancel_cnt;
300 1466112 : }
301 :
302 : ulong
303 : fd_funk_txn_cancel( fd_funk_t * funk,
304 : fd_funk_txn_t * txn,
305 2321292 : int verbose ) {
306 :
307 2321292 : if( FD_UNLIKELY( !funk ) ) {
308 196464 : if( FD_UNLIKELY( verbose ) ) FD_LOG_WARNING(( "NULL funk" ));
309 196464 : return 0UL;
310 196464 : }
311 :
312 2124828 : fd_funk_txn_t * map = fd_funk_txn_map( funk, fd_funk_wksp( funk ) );
313 :
314 2124828 : ulong txn_max = funk->txn_max;
315 :
316 2124828 : ulong txn_idx = (ulong)(txn - map);
317 :
318 2124828 : 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 1338570 : 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 1150188 : return fd_funk_txn_cancel_family( funk, map, txn_max, funk->cycle_tag++, txn_idx );
329 1338570 : }
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 772650 : ulong txn_idx ) {
340 :
341 772650 : ulong parent_idx = fd_funk_txn_idx( map[ txn_idx ].parent_cidx );
342 :
343 772650 : 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 109020 : ASSERT_IN_PREP( parent_idx );
346 :
347 109020 : return fd_funk_txn_idx( map[ parent_idx ].child_head_cidx );
348 109020 : }
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 772650 : ulong skip_idx ) {
366 :
367 772650 : 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 1088574 : 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 1088574 : ASSERT_IN_PREP ( sibling_idx );
379 1088574 : ASSERT_UNTAGGED( sibling_idx );
380 1088574 : map[ sibling_idx ].tag = tag;
381 :
382 1088574 : if( FD_UNLIKELY( sibling_idx!=skip_idx ) ) { /* Not skip_idx so push onto the cancel stack, opt for non-compete */
383 315924 : map[ sibling_idx ].stack_cidx = fd_funk_txn_cidx( cancel_stack_idx );
384 315924 : cancel_stack_idx = sibling_idx;
385 315924 : }
386 :
387 1088574 : ulong younger_idx = fd_funk_txn_idx( map[ sibling_idx ].sibling_next_cidx );
388 1088574 : if( FD_LIKELY( fd_funk_txn_idx_is_null( younger_idx ) ) ) break; /* opt for non-compete */
389 315924 : sibling_idx = younger_idx;
390 :
391 315924 : }
392 :
393 : /* Cancel all transactions and their descendants on the cancel stack */
394 :
395 772650 : ulong cancel_cnt = 0UL;
396 :
397 1088574 : while( !fd_funk_txn_idx_is_null( cancel_stack_idx ) ) { /* TODO: peel first iter to make more predictable? */
398 315924 : ulong sibling_idx = cancel_stack_idx;
399 315924 : cancel_stack_idx = fd_funk_txn_idx( map[ sibling_idx ].stack_cidx );
400 :
401 315924 : cancel_cnt += fd_funk_txn_cancel_family( funk, map, txn_max, tag, sibling_idx );
402 315924 : }
403 :
404 772650 : return cancel_cnt;
405 772650 : }
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 775044 : fd_wksp_t * wksp ) { /* ==fd_funk_wksp( funk ) */
520 : /* We don't need to to do all the individual removal pointer updates
521 : as we are removing the whole list from txn_idx. Likewise, we
522 : temporarily repurpose txn_cidx as a loop detector for additional
523 : corruption protection. */
524 :
525 775044 : ulong rec_idx = txn_map[ txn_idx ].rec_head_idx;
526 1928079 : while( !fd_funk_rec_idx_is_null( rec_idx ) ) {
527 :
528 : /* Validate rec_idx */
529 :
530 1153035 : if( FD_UNLIKELY( rec_idx>=rec_max ) ) FD_LOG_CRIT(( "memory corruption detected (bad idx)" ));
531 1153035 : if( FD_UNLIKELY( fd_funk_txn_idx( rec_map[ rec_idx ].txn_cidx )!=txn_idx ) )
532 0 : FD_LOG_CRIT(( "memory corruption detected (cycle or bad idx)" ));
533 1153035 : if( FD_UNLIKELY( rec_map[ rec_idx ].val_no_free ) )
534 0 : FD_LOG_CRIT(( "new record was speed loaded" ));
535 1153035 : rec_map[ rec_idx ].txn_cidx = fd_funk_txn_cidx( FD_FUNK_TXN_IDX_NULL );
536 :
537 1153035 : ulong next_idx = rec_map[ rec_idx ].next_idx;
538 :
539 : /* See if (dst_xid,key) already exists */
540 :
541 1153035 : fd_funk_xid_key_pair_t dst_pair[1];
542 1153035 : fd_funk_xid_key_pair_init( dst_pair, dst_xid, fd_funk_rec_key( &rec_map[ rec_idx ] ) );
543 :
544 1153035 : fd_funk_rec_t * dst_rec = fd_funk_rec_map_query( rec_map, dst_pair, NULL );
545 :
546 1153035 : if( FD_UNLIKELY( rec_map[ rec_idx ].flags & FD_FUNK_REC_FLAG_ERASE ) ) { /* Erase a published key */
547 :
548 : /* Remove from partition */
549 190332 : fd_funk_part_set_intern( partvec, rec_map, &rec_map[rec_idx], FD_FUNK_PART_NULL );
550 :
551 190332 : if( FD_UNLIKELY( !dst_rec ) ) {
552 :
553 : /* Note that we only set the erase flag if there is was ancestor
554 : to this transaction with the key in it. So if are merging
555 : into the last published transaction and we didn't find a
556 : record there, we have a memory corruption problem. */
557 :
558 882 : if( FD_UNLIKELY( fd_funk_txn_idx_is_null( dst_txn_idx ) ) ) {
559 0 : FD_LOG_CRIT(( "memory corruption detected (bad ancestor)" ));
560 0 : }
561 :
562 : /* Otherwise, txn is an erase of this record from one of
563 : dst's ancestors. So we move the erase from (src_xid,key) and
564 : to (dst_xid,key). We need to do this by a map remove / map
565 : insert to keep map queries working correctly. Note that
566 : value metadata was flushed when erase was first set on
567 : (src_xid,key). */
568 :
569 882 : fd_funk_rec_map_remove( rec_map, fd_funk_rec_pair( &rec_map[ rec_idx ] ) );
570 :
571 882 : if( !fd_funk_txn_xid_eq_root( dst_xid ) ) {
572 882 : dst_rec = fd_funk_rec_map_insert( rec_map, dst_pair ); /* Guaranteed to succeed at this point due to above remove */
573 :
574 882 : ulong dst_rec_idx = (ulong)(dst_rec - rec_map);
575 :
576 882 : ulong dst_prev_idx = *_dst_rec_tail_idx;
577 :
578 882 : dst_rec->prev_idx = dst_prev_idx;
579 882 : dst_rec->next_idx = FD_FUNK_REC_IDX_NULL;
580 882 : dst_rec->txn_cidx = fd_funk_txn_cidx( dst_txn_idx );
581 882 : dst_rec->tag = 0U;
582 :
583 882 : if( fd_funk_rec_idx_is_null( dst_prev_idx ) ) *_dst_rec_head_idx = dst_rec_idx;
584 798 : else rec_map[ dst_prev_idx ].next_idx = dst_rec_idx;
585 :
586 882 : *_dst_rec_tail_idx = dst_rec_idx;
587 :
588 882 : fd_funk_val_init( dst_rec );
589 882 : fd_funk_part_init( dst_rec );
590 882 : dst_rec->flags |= FD_FUNK_REC_FLAG_ERASE;
591 882 : }
592 :
593 189450 : } else {
594 :
595 : /* The erase in rec_idx erases this transaction. Unmap
596 : (src_xid,key) (note that value was flushed when erase was
597 : first set), flush dst xid's value, remove dst it from the dst
598 : sequence and unmap (dst_xid,key) */
599 :
600 189450 : fd_funk_rec_map_remove( rec_map, fd_funk_rec_pair( &rec_map[ rec_idx ] ) );
601 :
602 189450 : fd_funk_val_flush( dst_rec, alloc, wksp );
603 189450 : fd_funk_part_set_intern( partvec, rec_map, dst_rec, FD_FUNK_PART_NULL );
604 :
605 189450 : if( fd_funk_txn_xid_eq_root( dst_xid ) ) {
606 189396 : ulong prev_idx = dst_rec->prev_idx;
607 189396 : ulong next_idx = dst_rec->next_idx;
608 :
609 189396 : if( FD_UNLIKELY( fd_funk_rec_idx_is_null( prev_idx ) ) ) *_dst_rec_head_idx = next_idx;
610 171684 : else rec_map[ prev_idx ].next_idx = next_idx;
611 :
612 189396 : if( FD_UNLIKELY( fd_funk_rec_idx_is_null( next_idx ) ) ) *_dst_rec_tail_idx = prev_idx;
613 176484 : else rec_map[ next_idx ].prev_idx = prev_idx;
614 :
615 189396 : fd_funk_rec_map_remove( rec_map, dst_pair );
616 :
617 189396 : } else {
618 : /* Leave a new erase record */
619 54 : fd_funk_val_init( dst_rec );
620 54 : fd_funk_part_init( dst_rec );
621 54 : dst_rec->flags |= FD_FUNK_REC_FLAG_ERASE;
622 54 : }
623 189450 : }
624 :
625 962703 : } else {
626 :
627 : /* At this point, we are either creating a new record or updating
628 : an existing one. In either case, we are going to be keeping
629 : around the src's value for later use and for speed, we do this
630 : zero-copy / in-place. So we stash record value in stack
631 : temporaries and unmap (xid,key). Note this strictly frees 1
632 : record from the rec_map, guaranteeing at least 1 record free in
633 : the record map below. Note that we can't just reuse rec_idx in
634 : the update case because that could break map queries. */
635 :
636 962703 : ulong val_sz = (ulong)rec_map[ rec_idx ].val_sz;
637 962703 : ulong val_max = (ulong)rec_map[ rec_idx ].val_max;
638 962703 : ulong val_gaddr = rec_map[ rec_idx ].val_gaddr;
639 962703 : int val_no_free = rec_map[ rec_idx ].val_no_free;
640 962703 : uint part = rec_map[ rec_idx ].part;
641 :
642 962703 : fd_funk_part_set_intern( partvec, rec_map, &rec_map[ rec_idx ], FD_FUNK_PART_NULL );
643 962703 : fd_funk_rec_map_remove( rec_map, fd_funk_rec_pair( &rec_map[ rec_idx ] ) );
644 :
645 962703 : if( FD_UNLIKELY( !dst_rec ) ) { /* Create a published key */
646 :
647 246834 : dst_rec = fd_funk_rec_map_insert( rec_map, dst_pair ); /* Guaranteed to succeed at this point due to above remove */
648 :
649 246834 : ulong dst_rec_idx = (ulong)(dst_rec - rec_map);
650 246834 : ulong dst_prev_idx = *_dst_rec_tail_idx;
651 :
652 246834 : dst_rec->prev_idx = dst_prev_idx;
653 246834 : dst_rec->next_idx = FD_FUNK_REC_IDX_NULL;
654 246834 : dst_rec->txn_cidx = fd_funk_txn_cidx( dst_txn_idx );
655 246834 : dst_rec->tag = 0U;
656 :
657 246834 : fd_funk_part_init( dst_rec );
658 :
659 246834 : if( fd_funk_rec_idx_is_null( dst_prev_idx ) ) *_dst_rec_head_idx = dst_rec_idx;
660 246342 : else rec_map[ dst_prev_idx ].next_idx = dst_rec_idx;
661 :
662 246834 : *_dst_rec_tail_idx = dst_rec_idx;
663 :
664 715869 : } else { /* Update a published key */
665 :
666 715869 : fd_funk_val_flush( dst_rec, alloc, wksp ); /* Free up any preexisting value resources */
667 :
668 715869 : }
669 :
670 : /* Unstash value metadata from stack temporaries into dst_rec */
671 :
672 962703 : dst_rec->val_sz = (uint)val_sz;
673 962703 : dst_rec->val_max = (uint)val_max;
674 962703 : dst_rec->val_gaddr = val_gaddr;
675 962703 : dst_rec->val_no_free = val_no_free;
676 962703 : dst_rec->flags &= ~FD_FUNK_REC_FLAG_ERASE;
677 :
678 : /* Use the new partition */
679 :
680 962703 : fd_funk_part_set_intern( partvec, rec_map, dst_rec, part );
681 962703 : }
682 :
683 : /* Advance to the next record */
684 :
685 1153035 : rec_idx = next_idx;
686 1153035 : }
687 :
688 775044 : txn_map[ txn_idx ].rec_head_idx = FD_FUNK_REC_IDX_NULL;
689 775044 : txn_map[ txn_idx ].rec_tail_idx = FD_FUNK_REC_IDX_NULL;
690 775044 : }
691 :
692 : /* fd_funk_txn_publish_funk_child publishes a transaction that is known
693 : to be a child of funk. Callers have already validated our input
694 : arguments. Returns FD_FUNK_SUCCESS on success and an FD_FUNK_ERR_*
695 : code on failure. (There are currently no failure cases but the
696 : plumbing is there if value handling requires it at some point.) */
697 :
698 : static int
699 : fd_funk_txn_publish_funk_child( fd_funk_t * funk,
700 : fd_funk_txn_t * map,
701 : ulong txn_max,
702 : ulong tag,
703 663564 : ulong txn_idx ) {
704 :
705 663564 : fd_funk_check_write( funk );
706 :
707 : /* Apply the updates in txn to the last published transactions */
708 :
709 663564 : fd_wksp_t * wksp = fd_funk_wksp( funk );
710 663564 : fd_funk_txn_update( &funk->rec_head_idx, &funk->rec_tail_idx, FD_FUNK_TXN_IDX_NULL, fd_funk_root( funk ),
711 663564 : txn_idx, funk->rec_max, map, fd_funk_rec_map( funk, wksp ), fd_funk_get_partvec( funk, wksp ),
712 663564 : fd_funk_alloc( funk, wksp ), wksp );
713 :
714 : /* Cancel all competing transaction histories */
715 :
716 663564 : ulong oldest_idx = fd_funk_txn_oldest_sibling( funk, map, txn_max, txn_idx );
717 663564 : fd_funk_txn_cancel_sibling_list( funk, map, txn_max, tag, oldest_idx, txn_idx );
718 :
719 : /* Make all the children children of funk */
720 :
721 663564 : ulong child_head_idx = fd_funk_txn_idx( map[ txn_idx ].child_head_cidx );
722 663564 : ulong child_tail_idx = fd_funk_txn_idx( map[ txn_idx ].child_tail_cidx );
723 :
724 663564 : ulong child_idx = child_head_idx;
725 1080093 : while( FD_UNLIKELY( !fd_funk_txn_idx_is_null( child_idx ) ) ) { /* opt for incr pub */
726 :
727 416529 : ASSERT_IN_PREP ( child_idx );
728 416529 : ASSERT_UNTAGGED( child_idx );
729 416529 : map[ child_idx ].tag = tag;
730 :
731 416529 : map[ child_idx ].parent_cidx = fd_funk_txn_cidx( FD_FUNK_TXN_IDX_NULL );
732 :
733 416529 : child_idx = fd_funk_txn_idx( map[ child_idx ].sibling_next_cidx );
734 416529 : }
735 :
736 663564 : funk->child_head_cidx = fd_funk_txn_cidx( child_head_idx );
737 663564 : funk->child_tail_cidx = fd_funk_txn_cidx( child_tail_idx );
738 :
739 : /* Remove the mapping */
740 :
741 663564 : fd_funk_txn_xid_copy( funk->last_publish, fd_funk_txn_xid( &map[ txn_idx ] ) );
742 :
743 663564 : fd_funk_txn_map_remove( map, fd_funk_txn_xid( &map[ txn_idx ] ) );
744 :
745 663564 : return FD_FUNK_SUCCESS;
746 663564 : }
747 :
748 : ulong
749 : fd_funk_txn_publish( fd_funk_t * funk,
750 : fd_funk_txn_t * txn,
751 1548918 : int verbose ) {
752 :
753 1548918 : if( FD_UNLIKELY( !funk ) ) {
754 196464 : if( FD_UNLIKELY( verbose ) ) FD_LOG_WARNING(( "NULL funk" ));
755 196464 : return 0UL;
756 196464 : }
757 :
758 1352454 : fd_wksp_t * wksp = fd_funk_wksp( funk );
759 :
760 1352454 : fd_funk_txn_t * map = fd_funk_txn_map( funk, wksp );
761 :
762 1352454 : ulong txn_max = funk->txn_max;
763 :
764 1352454 : ulong txn_idx = (ulong)(txn - map);
765 :
766 1352454 : if( FD_UNLIKELY( (txn_idx>=txn_max) /* Out of map (incl NULL) */ | (txn!=(map+txn_idx)) /* Bad alignment */ ) ) {
767 786372 : if( FD_UNLIKELY( verbose ) ) FD_LOG_WARNING(( "txn is not a funk transaction" ));
768 786372 : return 0UL;
769 786372 : }
770 :
771 566082 : if( FD_UNLIKELY( !fd_funk_txn_map_query( map, fd_funk_txn_xid( txn ), NULL ) ) ) {
772 188382 : if( FD_UNLIKELY( verbose ) ) FD_LOG_WARNING(( "txn is not in preparation" ));
773 188382 : return 0UL;
774 188382 : }
775 :
776 377700 : ulong tag = funk->cycle_tag++;
777 :
778 377700 : ulong publish_stack_idx = FD_FUNK_TXN_IDX_NULL;
779 :
780 663564 : for(;;) {
781 663564 : map[ txn_idx ].tag = tag;
782 :
783 : /* At this point, txn_idx is a transaction that needs to be
784 : published and has been tagged. If txn is a child of funk, we are
785 : ready to publish txn and everything on the publish stack. */
786 :
787 663564 : ulong parent_idx = fd_funk_txn_idx( map[ txn_idx ].parent_cidx );
788 663564 : if( FD_LIKELY( fd_funk_txn_idx_is_null( parent_idx ) ) ) break; /* opt for incr pub */
789 :
790 : /* txn_idx has a parent. Validate and tag it. Push txn to the
791 : publish stack and recurse into the parent. */
792 :
793 285864 : ASSERT_IN_PREP ( parent_idx );
794 285864 : ASSERT_UNTAGGED( parent_idx );
795 :
796 285864 : map[ txn_idx ].stack_cidx = fd_funk_txn_cidx( publish_stack_idx );
797 285864 : publish_stack_idx = txn_idx;
798 :
799 285864 : txn_idx = parent_idx;
800 285864 : }
801 :
802 377700 : ulong publish_cnt = 0UL;
803 :
804 663564 : for(;;) {
805 :
806 : /* At this point, all the transactions we need to publish are
807 : tagged, txn is the next up publish funk and publish_stack has the
808 : transactions to follow in order by pop. We use a new tag for
809 : each publish as txn and its siblings we potentially visited in a
810 : previous iteration of this loop. */
811 :
812 663564 : if( FD_UNLIKELY( fd_funk_txn_publish_funk_child( funk, map, txn_max, funk->cycle_tag++, txn_idx ) ) ) break;
813 663564 : publish_cnt++;
814 :
815 663564 : txn_idx = publish_stack_idx;
816 663564 : if( FD_LIKELY( fd_funk_txn_idx_is_null( txn_idx ) ) ) break; /* opt for incr pub */
817 285864 : publish_stack_idx = fd_funk_txn_idx( map[ txn_idx ].stack_cidx );
818 285864 : }
819 :
820 377700 : return publish_cnt;
821 377700 : }
822 :
823 : int
824 : fd_funk_txn_publish_into_parent( fd_funk_t * funk,
825 : fd_funk_txn_t * txn,
826 109086 : int verbose ) {
827 109086 : if( FD_UNLIKELY( !funk ) ) {
828 0 : if( FD_UNLIKELY( verbose ) ) FD_LOG_WARNING(( "NULL funk" ));
829 0 : return FD_FUNK_ERR_INVAL;
830 0 : }
831 109086 : fd_funk_check_write( funk );
832 :
833 109086 : fd_wksp_t * wksp = fd_funk_wksp( funk );
834 :
835 109086 : fd_funk_txn_t * map = fd_funk_txn_map( funk, wksp );
836 :
837 109086 : ulong txn_idx = (ulong)(txn - map);
838 :
839 109086 : ulong oldest_idx = fd_funk_txn_oldest_sibling( funk, map, funk->txn_max, txn_idx );
840 109086 : fd_funk_txn_cancel_sibling_list( funk, map, funk->txn_max, funk->cycle_tag++, oldest_idx, txn_idx );
841 :
842 109086 : ulong parent_idx = fd_funk_txn_idx( txn->parent_cidx );
843 109086 : if( fd_funk_txn_idx_is_null( parent_idx ) ) {
844 : /* Publish to root */
845 66 : if( fd_funk_txn_idx( funk->child_head_cidx ) != txn_idx || fd_funk_txn_idx( funk->child_tail_cidx ) != txn_idx )
846 0 : FD_LOG_CRIT(( "memory corruption detected (cycle or bad idx)" ));
847 66 : fd_funk_txn_update( &funk->rec_head_idx, &funk->rec_tail_idx, FD_FUNK_TXN_IDX_NULL, fd_funk_root( funk ),
848 66 : txn_idx, funk->rec_max, map, fd_funk_rec_map( funk, wksp ), fd_funk_get_partvec( funk, wksp ),
849 66 : fd_funk_alloc( funk, wksp ), wksp );
850 : /* Inherit the children */
851 66 : funk->child_head_cidx = txn->child_head_cidx;
852 66 : funk->child_tail_cidx = txn->child_tail_cidx;
853 109020 : } else {
854 109020 : fd_funk_txn_t * parent_txn = map + parent_idx;
855 109020 : if( fd_funk_txn_idx( parent_txn->child_head_cidx ) != txn_idx || fd_funk_txn_idx( parent_txn->child_tail_cidx ) != txn_idx )
856 0 : FD_LOG_CRIT(( "memory corruption detected (cycle or bad idx)" ));
857 109020 : fd_funk_txn_update( &parent_txn->rec_head_idx, &parent_txn->rec_tail_idx, parent_idx, &parent_txn->xid,
858 109020 : txn_idx, funk->rec_max, map, fd_funk_rec_map( funk, wksp ), fd_funk_get_partvec( funk, wksp ),
859 109020 : fd_funk_alloc( funk, wksp ), wksp );
860 : /* Inherit the children */
861 109020 : parent_txn->child_head_cidx = txn->child_head_cidx;
862 109020 : parent_txn->child_tail_cidx = txn->child_tail_cidx;
863 109020 : }
864 :
865 : /* Adjust the parent pointers of the children to point to their grandparent */
866 109086 : ulong child_idx = fd_funk_txn_idx( txn->child_head_cidx );
867 109263 : while( FD_UNLIKELY( !fd_funk_txn_idx_is_null( child_idx ) ) ) {
868 177 : map[ child_idx ].parent_cidx = fd_funk_txn_cidx( parent_idx );
869 177 : child_idx = fd_funk_txn_idx( map[ child_idx ].sibling_next_cidx );
870 177 : }
871 :
872 109086 : fd_funk_txn_map_remove( map, fd_funk_txn_xid( txn ) );
873 :
874 109086 : return FD_FUNK_SUCCESS;
875 109086 : }
876 :
877 : int
878 : fd_funk_txn_merge_all_children( fd_funk_t * funk,
879 : fd_funk_txn_t * parent_txn,
880 2301 : int verbose ) {
881 2301 : if( FD_UNLIKELY( !funk ) ) {
882 0 : if( FD_UNLIKELY( verbose ) ) FD_LOG_WARNING(( "NULL funk" ));
883 0 : return FD_FUNK_ERR_INVAL;
884 0 : }
885 2301 : fd_funk_check_write( funk );
886 :
887 2301 : fd_wksp_t * wksp = fd_funk_wksp( funk );
888 :
889 2301 : fd_funk_txn_t * map = fd_funk_txn_map( funk, wksp );
890 :
891 2301 : ulong txn_max = fd_funk_txn_map_key_max( map );
892 :
893 2301 : ulong parent_idx = (ulong)(parent_txn - map);
894 :
895 2301 : ASSERT_IN_PREP( parent_idx );
896 :
897 2301 : ulong child_head_idx = fd_funk_txn_idx( map[ parent_idx ].child_head_cidx );
898 :
899 2301 : ulong child_idx = child_head_idx;
900 4695 : while( FD_UNLIKELY( !fd_funk_txn_idx_is_null( child_idx ) ) ) { /* opt for incr pub */
901 : /* Merge records from child into parent */
902 :
903 2394 : fd_funk_txn_t * txn = &map[ child_idx ];
904 2394 : if( FD_UNLIKELY( !fd_funk_txn_idx_is_null( fd_funk_txn_idx( txn->child_head_cidx ) ) ) ) {
905 0 : FD_LOG_WARNING(("cannot call fd_funk_txn_merge_all_children if parent_txn has grandchildren"));
906 0 : return FD_FUNK_ERR_TXN;
907 0 : }
908 :
909 2394 : fd_funk_txn_update( &parent_txn->rec_head_idx, &parent_txn->rec_tail_idx, parent_idx, &parent_txn->xid,
910 2394 : child_idx, funk->rec_max, map, fd_funk_rec_map( funk, wksp ), fd_funk_get_partvec( funk, wksp ),
911 2394 : fd_funk_alloc( funk, wksp ), wksp );
912 :
913 2394 : child_idx = fd_funk_txn_idx( txn->sibling_next_cidx );
914 2394 : fd_funk_txn_map_remove( map, fd_funk_txn_xid( txn ) );
915 2394 : }
916 :
917 2301 : parent_txn->child_head_cidx = fd_funk_txn_cidx( FD_FUNK_TXN_IDX_NULL );
918 2301 : parent_txn->child_tail_cidx = fd_funk_txn_cidx( FD_FUNK_TXN_IDX_NULL );
919 :
920 2301 : return FD_FUNK_SUCCESS;
921 2301 : }
922 :
923 : /* Return the first record in a transaction. Returns NULL if the
924 : transaction has no records yet. */
925 :
926 : FD_FN_PURE fd_funk_rec_t const *
927 : fd_funk_txn_first_rec( fd_funk_t * funk,
928 217374 : fd_funk_txn_t const * txn ) {
929 217374 : ulong rec_idx;
930 217374 : if( FD_UNLIKELY( NULL == txn ))
931 6300 : rec_idx = funk->rec_head_idx;
932 211074 : else
933 211074 : rec_idx = txn->rec_head_idx;
934 217374 : if( fd_funk_rec_idx_is_null( rec_idx ) ) return NULL;
935 169761 : fd_funk_rec_t const * rec_map = fd_funk_rec_map( funk, fd_funk_wksp( funk ) );
936 169761 : return rec_map + rec_idx;
937 217374 : }
938 :
939 : /* Return the next record in a transaction. Returns NULL if the
940 : transaction has no more records. */
941 :
942 : FD_FN_PURE fd_funk_rec_t const *
943 : fd_funk_txn_next_rec( fd_funk_t * funk,
944 2070993 : fd_funk_rec_t const * rec ) {
945 2070993 : ulong rec_idx = rec->next_idx;
946 2070993 : if( fd_funk_rec_idx_is_null( rec_idx ) ) return NULL;
947 1901232 : fd_funk_rec_t const * rec_map = fd_funk_rec_map( funk, fd_funk_wksp( funk ) );
948 1901232 : return rec_map + rec_idx;
949 2070993 : }
950 :
951 : fd_funk_txn_xid_t
952 20682798 : fd_funk_generate_xid(void) {
953 20682798 : fd_funk_txn_xid_t xid;
954 20682798 : static FD_TL ulong seq = 0;
955 20682798 : xid.ul[0] =
956 20682798 : (fd_log_cpu_id() + 1U)*3138831853UL +
957 20682798 : (fd_log_thread_id() + 1U)*9180195821UL +
958 20682798 : (++seq)*6208101967UL;
959 20682798 : xid.ul[1] = ((ulong)fd_tickcount())*2810745731UL;
960 20682798 : return xid;
961 20682798 : }
962 :
963 : int
964 22026408 : fd_funk_txn_verify( fd_funk_t * funk ) {
965 22026408 : fd_wksp_t * wksp = fd_funk_wksp( funk ); /* Previously verified */
966 22026408 : fd_funk_txn_t * map = fd_funk_txn_map( funk, wksp ); /* Previously verified */
967 22026408 : ulong txn_max = funk->txn_max; /* Previously verified */
968 :
969 22026408 : ulong funk_child_head_idx = fd_funk_txn_idx( funk->child_head_cidx ); /* Previously verified */
970 22026408 : ulong funk_child_tail_idx = fd_funk_txn_idx( funk->child_tail_cidx ); /* Previously verified */
971 :
972 22026408 : fd_funk_txn_xid_t const * last_publish = funk->last_publish; /* Previously verified */
973 :
974 856024092 : # define TEST(c) do { \
975 856024092 : if( FD_UNLIKELY( !(c) ) ) { FD_LOG_WARNING(( "FAIL: %s", #c )); return FD_FUNK_ERR_INVAL; } \
976 856024092 : } while(0)
977 :
978 22026408 : # define IS_VALID( idx ) ( (idx==FD_FUNK_TXN_IDX_NULL) || \
979 22026408 : ((idx<txn_max) && (!fd_funk_txn_xid_eq( fd_funk_txn_xid( &map[idx] ), last_publish ))) )
980 :
981 22026408 : TEST( !fd_funk_txn_map_verify( map ) );
982 :
983 22026408 : ulong free_cnt = txn_max - fd_funk_txn_map_key_cnt( map );
984 :
985 : /* Tag all transactions as not visited yet */
986 :
987 729048744 : for( ulong txn_idx=0UL; txn_idx<txn_max; txn_idx++ ) map[ txn_idx ].tag = 0UL;
988 :
989 : /* Visit all transactions in preparation, traversing from oldest to
990 : youngest. */
991 :
992 22026408 : ulong prep_cnt = 0UL;
993 22026408 : do {
994 :
995 : /* Push all children of funk to the stack */
996 :
997 22026408 : ulong stack_idx = FD_FUNK_TXN_IDX_NULL;
998 22026408 : ulong child_idx = funk_child_head_idx;
999 52708581 : while( !fd_funk_txn_idx_is_null( child_idx ) ) {
1000 :
1001 : /* Make sure valid idx, not tagged (detects cycles) and child
1002 : knows it is a child of funk. Then tag as visited / in-prep,
1003 : push to stack and update prep_cnt */
1004 :
1005 30682173 : TEST( IS_VALID( child_idx ) );
1006 30682173 : TEST( !map[ child_idx ].tag );
1007 30682173 : TEST( fd_funk_txn_idx_is_null( fd_funk_txn_idx( map[ child_idx ].parent_cidx ) ) );
1008 30682173 : map[ child_idx ].tag = 1UL;
1009 30682173 : map[ child_idx ].stack_cidx = fd_funk_txn_cidx( stack_idx );
1010 30682173 : stack_idx = child_idx;
1011 30682173 : prep_cnt++;
1012 :
1013 30682173 : ulong next_idx = fd_funk_txn_idx( map[ child_idx ].sibling_next_cidx );
1014 30682173 : if( !fd_funk_txn_idx_is_null( next_idx ) ) TEST( fd_funk_txn_idx( map[ next_idx ].sibling_prev_cidx )==child_idx );
1015 30682173 : child_idx = next_idx;
1016 30682173 : }
1017 :
1018 134597451 : while( !fd_funk_txn_idx_is_null( stack_idx ) ) {
1019 :
1020 : /* Pop the next transaction to traverse */
1021 :
1022 112571043 : ulong txn_idx = stack_idx;
1023 112571043 : stack_idx = fd_funk_txn_idx( map[ txn_idx ].stack_cidx );
1024 :
1025 : /* Push all children of txn to the stack */
1026 :
1027 112571043 : ulong child_idx = fd_funk_txn_idx( map[ txn_idx ].child_head_cidx );
1028 194459913 : while( !fd_funk_txn_idx_is_null( child_idx ) ) {
1029 :
1030 : /* Make sure valid idx, not tagged (detects cycles) and child
1031 : knows it is a child of txn_idx. Then tag as visited /
1032 : in-prep, push to stack and update prep_cnt */
1033 :
1034 81888870 : TEST( IS_VALID( child_idx ) );
1035 81888870 : TEST( !map[ child_idx ].tag );
1036 81888870 : TEST( fd_funk_txn_idx( map[ child_idx ].parent_cidx )==txn_idx );
1037 81888870 : map[ child_idx ].tag = 1UL;
1038 81888870 : map[ child_idx ].stack_cidx = fd_funk_txn_cidx( stack_idx );
1039 81888870 : stack_idx = child_idx;
1040 81888870 : prep_cnt++;
1041 :
1042 81888870 : ulong next_idx = fd_funk_txn_idx( map[ child_idx ].sibling_next_cidx );
1043 81888870 : if( !fd_funk_txn_idx_is_null( next_idx ) ) TEST( fd_funk_txn_idx( map[ next_idx ].sibling_prev_cidx )==child_idx );
1044 81888870 : child_idx = next_idx;
1045 81888870 : }
1046 112571043 : }
1047 :
1048 22026408 : } while(0);
1049 :
1050 22026408 : TEST( (free_cnt+prep_cnt)==txn_max );
1051 :
1052 : /* Do it again with a youngest to oldest traversal to test reverse
1053 : link integrity */
1054 :
1055 22026408 : prep_cnt = 0UL;
1056 22026408 : do {
1057 :
1058 : /* Push all children of funk to the stack */
1059 :
1060 22026408 : ulong stack_idx = FD_FUNK_TXN_IDX_NULL;
1061 22026408 : ulong child_idx = funk_child_tail_idx;
1062 52708581 : while( !fd_funk_txn_idx_is_null( child_idx ) ) {
1063 :
1064 : /* Make sure valid idx, tagged as visited above (detects cycles)
1065 : and child knows it is a child of funk. Then tag as visited /
1066 : in-prep, push to stack and update prep_cnt */
1067 :
1068 30682173 : TEST( IS_VALID( child_idx ) );
1069 30682173 : TEST( map[ child_idx ].tag==1UL );
1070 30682173 : TEST( fd_funk_txn_idx_is_null( fd_funk_txn_idx( map[ child_idx ].parent_cidx ) ) );
1071 30682173 : map[ child_idx ].tag = 2UL;
1072 30682173 : map[ child_idx ].stack_cidx = fd_funk_txn_cidx( stack_idx );
1073 30682173 : stack_idx = child_idx;
1074 30682173 : prep_cnt++;
1075 :
1076 30682173 : ulong prev_idx = fd_funk_txn_idx( map[ child_idx ].sibling_prev_cidx );
1077 30682173 : if( !fd_funk_txn_idx_is_null( prev_idx ) ) TEST( fd_funk_txn_idx( map[ prev_idx ].sibling_next_cidx )==child_idx );
1078 30682173 : child_idx = prev_idx;
1079 30682173 : }
1080 :
1081 134597451 : while( !fd_funk_txn_idx_is_null( stack_idx ) ) {
1082 :
1083 : /* Pop the next transaction to traverse */
1084 :
1085 112571043 : ulong txn_idx = stack_idx;
1086 112571043 : stack_idx = fd_funk_txn_idx( map[ txn_idx ].stack_cidx );
1087 :
1088 : /* Push all children of txn to the stack */
1089 :
1090 112571043 : ulong child_idx = fd_funk_txn_idx( map[ txn_idx ].child_tail_cidx );
1091 194459913 : while( !fd_funk_txn_idx_is_null( child_idx ) ) {
1092 :
1093 : /* Make sure valid idx, tagged as visited above (detects cycles)
1094 : and child knows it is a child of txn_idx. Then, tag as
1095 : visited / in-prep, push to stack and update prep_cnt */
1096 :
1097 81888870 : TEST( IS_VALID( child_idx ) );
1098 81888870 : TEST( map[ child_idx ].tag==1UL );
1099 81888870 : TEST( fd_funk_txn_idx( map[ child_idx ].parent_cidx )==txn_idx );
1100 81888870 : map[ child_idx ].tag = 2UL;
1101 81888870 : map[ child_idx ].stack_cidx = fd_funk_txn_cidx( stack_idx );
1102 81888870 : stack_idx = child_idx;
1103 81888870 : prep_cnt++;
1104 :
1105 81888870 : ulong prev_idx = fd_funk_txn_idx( map[ child_idx ].sibling_prev_cidx );
1106 81888870 : if( !fd_funk_txn_idx_is_null( prev_idx ) ) TEST( fd_funk_txn_idx( map[ prev_idx ].sibling_next_cidx )==child_idx );
1107 81888870 : child_idx = prev_idx;
1108 81888870 : }
1109 112571043 : }
1110 22026408 : } while(0);
1111 :
1112 22026408 : TEST( (free_cnt+prep_cnt)==txn_max );
1113 :
1114 22026408 : TEST( fd_funk_txn_cnt( map )==prep_cnt );
1115 :
1116 22026408 : # undef IS_VALID
1117 22026408 : # undef TEST
1118 :
1119 22026408 : return FD_FUNK_SUCCESS;
1120 22026408 : }
1121 :
1122 : #undef ASSERT_UNTAGGED
1123 : #undef ASSERT_IN_PREP
1124 : #undef ASSERT_IN_MAP
|
