LCOV - code coverage report
Current view: top level - funk - fd_funk_txn.c (source / functions) Hit Total Coverage
Test: cov.lcov Lines: 390 535 72.9 %
Date: 2025-09-17 04:38:03 Functions: 22 31 71.0 %

          Line data    Source code
       1             : #include "fd_funk.h"
       2             : 
       3             : /* Provide the actual transaction map implementation */
       4             : 
       5             : #define POOL_NAME          fd_funk_txn_pool
       6     2107161 : #define POOL_ELE_T         fd_funk_txn_t
       7             : #define POOL_IDX_T         uint
       8     5256294 : #define POOL_NEXT          map_next
       9             : #define POOL_IMPL_STYLE    2
      10             : #include "../util/tmpl/fd_pool_para.c"
      11             : 
      12             : #define MAP_NAME              fd_funk_txn_map
      13   588585870 : #define MAP_ELE_T             fd_funk_txn_t
      14           0 : #define MAP_KEY_T             fd_funk_txn_xid_t
      15     1053513 : #define MAP_KEY               xid
      16             : #define MAP_KEY_EQ(k0,k1)     fd_funk_txn_xid_eq((k0),(k1))
      17             : #define MAP_KEY_HASH(k0,seed) fd_funk_txn_xid_hash((k0),(seed))
      18   394080410 : #define MAP_NEXT              map_next
      19             : #define MAP_HASH              map_hash
      20          33 : #define MAP_MAGIC             (0xf173da2ce7172db0UL) /* Firedancer txn db version 0 */
      21             : #define MAP_IMPL_STYLE        2
      22             : #include "../util/tmpl/fd_map_chain_para.c"
      23             : 
      24             : /* TODO: remove this lock */
      25             : #include "../flamenco/fd_rwlock.h"
      26             : static fd_rwlock_t funk_txn_lock[ 1 ] = {0};
      27             : 
      28             : void
      29           0 : fd_funk_txn_start_read( fd_funk_t * funk FD_PARAM_UNUSED ) {
      30           0 :   fd_rwlock_read( funk_txn_lock );
      31           0 : }
      32             : 
      33             : void
      34           0 : fd_funk_txn_end_read( fd_funk_t * funk FD_PARAM_UNUSED ) {
      35           0 :   fd_rwlock_unread( funk_txn_lock );
      36           0 : }
      37             : 
      38             : void
      39          33 : fd_funk_txn_start_write( fd_funk_t * funk FD_PARAM_UNUSED ) {
      40          33 :   fd_rwlock_write( funk_txn_lock );
      41          33 : }
      42             : 
      43             : void
      44          33 : fd_funk_txn_end_write( fd_funk_t * funk FD_PARAM_UNUSED ) {
      45          33 :   fd_rwlock_unwrite( funk_txn_lock );
      46          33 : }
      47             : 
      48             : fd_funk_txn_t *
      49             : fd_funk_txn_prepare( fd_funk_t *               funk,
      50             :                      fd_funk_txn_t *           parent,
      51             :                      fd_funk_txn_xid_t const * xid,
      52     1315650 :                      int                       verbose ) {
      53             : 
      54     1315650 :   if( FD_UNLIKELY( !funk ) ) FD_LOG_CRIT(( "NULL funk" ));
      55     1315650 :   if( FD_UNLIKELY( !xid  ) ) FD_LOG_CRIT(( "NULL xid"  ));
      56     1315650 :   if( FD_UNLIKELY( fd_funk_txn_xid_eq_root( xid ) ) ) FD_LOG_CRIT(( "xid is root" ));
      57             : 
      58             : #ifdef FD_FUNK_HANDHOLDING
      59             :   if( FD_UNLIKELY( parent && !fd_funk_txn_valid( funk, parent ) ) ) {
      60             :     if( FD_UNLIKELY( verbose ) ) FD_LOG_WARNING(( "bad txn" ));
      61             :     return NULL;
      62             :   }
      63             :   if( FD_UNLIKELY( fd_funk_txn_xid_eq( xid, funk->shmem->last_publish ) ) ) {
      64             :     if( FD_UNLIKELY( verbose ) ) FD_LOG_WARNING(( "xid is the last published" ));
      65             :     return NULL;
      66             :   }
      67             : #endif
      68             : 
      69     1315650 :   fd_funk_txn_map_query_t query[1];
      70     1315650 :   if( FD_UNLIKELY( fd_funk_txn_map_query_try( funk->txn_map, xid, NULL, query, 0 ) != FD_MAP_ERR_KEY ) ) {
      71      262125 :     if( FD_UNLIKELY( verbose ) ) FD_LOG_WARNING(( "xid in use" ));
      72      262125 :     return NULL;
      73      262125 :   }
      74             : 
      75     1053525 :   ulong  parent_idx;
      76     1053525 :   uint * _child_head_cidx;
      77     1053525 :   uint * _child_tail_cidx;
      78             : 
      79     1053525 :   if( FD_LIKELY( !parent ) ) { /* opt for incr pub */
      80             : 
      81      445488 :     parent_idx = FD_FUNK_TXN_IDX_NULL;
      82             : 
      83      445488 :     _child_head_cidx = &funk->shmem->child_head_cidx;
      84      445488 :     _child_tail_cidx = &funk->shmem->child_tail_cidx;
      85             : 
      86      608037 :   } else {
      87             : 
      88      608037 :     parent_idx = (ulong)(parent - funk->txn_pool->ele);
      89             : 
      90      608037 :     _child_head_cidx = &parent->child_head_cidx;
      91      608037 :     _child_tail_cidx = &parent->child_tail_cidx;
      92             : 
      93      608037 :   }
      94             : 
      95             :   /* Get a new transaction from the map */
      96             : 
      97     1053525 :   fd_funk_txn_t * txn = fd_funk_txn_pool_acquire( funk->txn_pool, NULL, 1, NULL );
      98     1053525 :   if( txn == NULL ) {
      99          12 :     if( FD_UNLIKELY( verbose ) ) FD_LOG_WARNING(( "transaction pool is exhuasted" ));
     100          12 :     return NULL;
     101          12 :   }
     102     1053513 :   fd_funk_txn_xid_copy( &txn->xid, xid );
     103     1053513 :   ulong txn_idx = (ulong)(txn - funk->txn_pool->ele);
     104             : 
     105             :   /* Join the family */
     106             : 
     107     1053513 :   ulong sibling_prev_idx = fd_funk_txn_idx( *_child_tail_cidx );
     108             : 
     109     1053513 :   int first_born = fd_funk_txn_idx_is_null( sibling_prev_idx );
     110             : 
     111     1053513 :   txn->parent_cidx       = fd_funk_txn_cidx( parent_idx           );
     112     1053513 :   txn->child_head_cidx   = fd_funk_txn_cidx( FD_FUNK_TXN_IDX_NULL );
     113     1053513 :   txn->child_tail_cidx   = fd_funk_txn_cidx( FD_FUNK_TXN_IDX_NULL );
     114     1053513 :   txn->sibling_prev_cidx = fd_funk_txn_cidx( sibling_prev_idx     );
     115     1053513 :   txn->sibling_next_cidx = fd_funk_txn_cidx( FD_FUNK_TXN_IDX_NULL );
     116     1053513 :   txn->stack_cidx        = fd_funk_txn_cidx( FD_FUNK_TXN_IDX_NULL );
     117     1053513 :   txn->tag               = 0UL;
     118             : 
     119     1053513 :   txn->lock = 0;
     120     1053513 :   txn->rec_head_idx = FD_FUNK_REC_IDX_NULL;
     121     1053513 :   txn->rec_tail_idx = FD_FUNK_REC_IDX_NULL;
     122             : 
     123             :   /* TODO: consider branchless impl */
     124     1053513 :   if( FD_LIKELY( first_born ) ) *_child_head_cidx                = fd_funk_txn_cidx( txn_idx ); /* opt for non-compete */
     125      536700 :   else funk->txn_pool->ele[ sibling_prev_idx ].sibling_next_cidx = fd_funk_txn_cidx( txn_idx );
     126             : 
     127     1053513 :   *_child_tail_cidx = fd_funk_txn_cidx( txn_idx );
     128             : 
     129     1053513 :   fd_funk_txn_map_insert( funk->txn_map, txn, FD_MAP_FLAG_BLOCKING );
     130             : 
     131     1053513 :   return txn;
     132     1053525 : }
     133             : 
     134             : /* fd_funk_txn_cancel_childless cancels a transaction that is known
     135             :    to be childless.  Callers have already validated our input arguments.
     136             :    Assumes that cancelling in the app can't fail but that could be
     137             :    straightforward to support by giving this an error and plumbing
     138             :    through to abort the overall cancel operation when it hits a error. */
     139             : 
     140             : static void
     141             : fd_funk_txn_cancel_childless( fd_funk_t * funk,
     142      837561 :                               ulong       txn_idx ) {
     143             : 
     144             :   /* Remove all records used by this transaction.  Note that we don't
     145             :      need to bother doing all the individual removal operations as we
     146             :      are removing the whole list.  We do reset the record transaction
     147             :      idx with NULL though we can detect cycles as soon as possible
     148             :      and abort. */
     149             : 
     150      837561 :   fd_wksp_t *          wksp     = funk->wksp;
     151      837561 :   fd_alloc_t *         alloc    = funk->alloc;
     152      837561 :   fd_funk_rec_map_t *  rec_map  = funk->rec_map;
     153      837561 :   fd_funk_rec_pool_t * rec_pool = funk->rec_pool;
     154      837561 :   ulong                rec_max  = fd_funk_rec_pool_ele_max( rec_pool );
     155      837561 :   fd_funk_txn_map_t *  txn_map  = funk->txn_map;
     156      837561 :   fd_funk_txn_pool_t * txn_pool = funk->txn_pool;
     157             : 
     158      837561 :   fd_funk_txn_t * txn = &txn_pool->ele[ txn_idx ];
     159      837561 :   uint rec_idx = txn->rec_head_idx;
     160     2379138 :   while( !fd_funk_rec_idx_is_null( rec_idx ) ) {
     161             : 
     162     1541577 :     if( FD_UNLIKELY( rec_idx>=rec_max ) ) FD_LOG_CRIT(( "memory corruption detected (bad idx)" ));
     163     1541577 :     if( FD_UNLIKELY( fd_funk_txn_idx( rec_pool->ele[ rec_idx ].txn_cidx )!=txn_idx ) )
     164           0 :       FD_LOG_CRIT(( "memory corruption detected (cycle or bad idx)" ));
     165             : 
     166     1541577 :     fd_funk_rec_t * rec = &rec_pool->ele[ rec_idx ];
     167     1541577 :     uint next_idx = rec->next_idx;
     168     1541577 :     rec->txn_cidx = fd_funk_txn_cidx( FD_FUNK_TXN_IDX_NULL );
     169             : 
     170     1541577 :     for(;;) {
     171     1541577 :       fd_funk_rec_map_query_t rec_query[1];
     172     1541577 :       int err = fd_funk_rec_map_remove( rec_map, fd_funk_rec_pair( rec ), NULL, rec_query, FD_MAP_FLAG_BLOCKING );
     173     1541577 :       if( FD_UNLIKELY( err == FD_MAP_ERR_AGAIN ) ) continue;
     174     1541577 :       if( err == FD_MAP_ERR_KEY ) break;
     175     1541577 :       if( FD_UNLIKELY( err != FD_MAP_SUCCESS ) ) FD_LOG_CRIT(( "map corruption" ));
     176     1541577 :       if( rec != fd_funk_rec_map_query_ele( rec_query ) ) break;
     177     1541577 :       fd_funk_val_flush( rec, alloc, wksp );
     178     1541577 :       fd_funk_rec_pool_release( rec_pool, rec, 1 );
     179     1541577 :       break;
     180     1541577 :     }
     181             : 
     182     1541577 :     rec_idx = next_idx;
     183     1541577 :   }
     184             : 
     185             :   /* Leave the family */
     186             : 
     187      837561 :   ulong sibling_prev_idx = fd_funk_txn_idx( txn->sibling_prev_cidx );
     188      837561 :   ulong sibling_next_idx = fd_funk_txn_idx( txn->sibling_next_cidx );
     189             : 
     190             :   /* TODO: Consider branchless impl */
     191             : 
     192      837561 :   if( FD_LIKELY( fd_funk_txn_idx_is_null( sibling_prev_idx ) ) ) { /* opt for non-compete */
     193      407289 :     ulong parent_idx = fd_funk_txn_idx( txn_pool->ele[ txn_idx ].parent_cidx );
     194      407289 :     if( FD_LIKELY( fd_funk_txn_idx_is_null( parent_idx ) ) ) { /* No older sib and is a funk child, opt for incr pub */
     195      136761 :       funk->shmem->child_head_cidx = fd_funk_txn_cidx( sibling_next_idx );
     196      270528 :     } else { /* No older sib and has parent */
     197      270528 :       txn_pool->ele[ parent_idx ].child_head_cidx = fd_funk_txn_cidx( sibling_next_idx );
     198      270528 :     }
     199      430272 :   } else { /* Has older sib */
     200      430272 :     txn_pool->ele[ sibling_prev_idx ].sibling_next_cidx = fd_funk_txn_cidx( sibling_next_idx );
     201      430272 :   }
     202             : 
     203      837561 :   if( FD_LIKELY( fd_funk_txn_idx_is_null( sibling_next_idx ) ) ) { /* opt for non-compete */
     204      660684 :     ulong parent_idx = fd_funk_txn_idx( txn_pool->ele[ txn_idx ].parent_cidx );
     205      660684 :     if( FD_LIKELY( fd_funk_txn_idx_is_null( parent_idx ) ) ) { /* No younger sib and is a funk child, opt for incr pub */
     206      262608 :       funk->shmem->child_tail_cidx = fd_funk_txn_cidx( sibling_prev_idx );
     207      398076 :     } else { /* No younger sib and has parent */
     208      398076 :       txn_pool->ele[ parent_idx ].child_tail_cidx = fd_funk_txn_cidx( sibling_prev_idx );
     209      398076 :     }
     210      660684 :   } else { /* Has younger sib */
     211      176877 :     txn_pool->ele[ sibling_next_idx ].sibling_prev_cidx = fd_funk_txn_cidx( sibling_prev_idx );
     212      176877 :   }
     213             : 
     214      837561 :   fd_funk_txn_map_query_t query[1];
     215      837561 :   if( fd_funk_txn_map_remove( txn_map, fd_funk_txn_xid( txn ), NULL, query, FD_MAP_FLAG_BLOCKING ) == FD_MAP_SUCCESS ) {
     216      837561 :     fd_funk_txn_pool_release( txn_pool, txn, 1 );
     217      837561 :   }
     218      837561 : }
     219             : 
     220             : /* fd_funk_txn_cancel_family cancels a transaction and all its
     221             :    descendants in a tree-depth-first-ordered sense from youngest to
     222             :    oldest.  Callers have already validated our input arguments.  Returns
     223             :    the number of transactions canceled. */
     224             : 
     225             : static ulong
     226             : fd_funk_txn_cancel_family( fd_funk_t *  funk,
     227             :                            ulong        tag,
     228      474282 :                            ulong        txn_idx ) {
     229      474282 :   ulong cancel_cnt = 0UL;
     230             : 
     231      474282 :   ulong parent_stack_idx = FD_FUNK_TXN_IDX_NULL;
     232             : 
     233     1200840 :   for(;;) {
     234             : 
     235     1200840 :     fd_funk_txn_t * txn = &funk->txn_pool->ele[ txn_idx ];
     236     1200840 :     txn->tag = tag;
     237             : 
     238     1200840 :     ulong youngest_idx = fd_funk_txn_idx( txn->child_tail_cidx );
     239     1200840 :     if( FD_LIKELY( fd_funk_txn_idx_is_null( youngest_idx ) ) ) { /* txn is is childless, opt for incr pub */
     240             : 
     241      837561 :       fd_funk_txn_cancel_childless( funk, txn_idx ); /* If this can fail, return cancel_cnt here on fail */
     242      837561 :       cancel_cnt++;
     243             : 
     244      837561 :       txn_idx = parent_stack_idx;                                  /* Pop the parent stack */
     245      837561 :       if( FD_LIKELY( fd_funk_txn_idx_is_null( txn_idx ) ) ) break; /* If stack is empty, we are done, opt for incr pub */
     246      363279 :       parent_stack_idx = fd_funk_txn_idx( funk->txn_pool->ele[ txn_idx ].stack_cidx );
     247      363279 :       continue;
     248      837561 :     }
     249             : 
     250             :     /* txn has at least one child and the youngest is youngest_idx.  Tag
     251             :        the youngest child, push txn onto the parent stack and recurse
     252             :        into the youngest child. */
     253             : 
     254      363279 :     txn->stack_cidx = fd_funk_txn_cidx( parent_stack_idx );
     255      363279 :     parent_stack_idx = txn_idx;
     256             : 
     257      363279 :     txn_idx = youngest_idx;
     258      363279 :   }
     259             : 
     260      474282 :   return cancel_cnt;
     261      474282 : }
     262             : 
     263             : ulong
     264             : fd_funk_txn_cancel( fd_funk_t *     funk,
     265             :                     fd_funk_txn_t * txn,
     266      147159 :                     int             verbose ) {
     267             : 
     268      147159 :   if( FD_UNLIKELY( !funk ) ) FD_LOG_CRIT(( "NULL funk" ));
     269      147159 :   if( FD_UNLIKELY( !txn  ) ) FD_LOG_CRIT(( "NULL txn"  ));
     270             : #ifdef FD_FUNK_HANDHOLDING
     271             :   if( FD_UNLIKELY( !fd_funk_txn_valid( funk, txn ) ) ) {
     272             :     if( FD_UNLIKELY( verbose ) ) FD_LOG_WARNING(( "bad txn" ));
     273             :     return 0UL;
     274             :   }
     275             : #else
     276      147159 :   (void)verbose;
     277      147159 : #endif
     278             : 
     279      147159 :   ulong txn_idx = (ulong)(txn - funk->txn_pool->ele);
     280      147159 :   return fd_funk_txn_cancel_family( funk, funk->shmem->cycle_tag++, txn_idx );
     281      147159 : }
     282             : 
     283             : /* fd_funk_txn_oldest_sibling returns the index of the oldest sibling
     284             :    in txn_idx's family.  Callers have already validated our input
     285             :    arguments.  The caller should validate the return index. */
     286             : 
     287             : static inline ulong
     288             : fd_funk_txn_oldest_sibling( fd_funk_t *  funk,
     289      215826 :                             ulong        txn_idx ) {
     290      215826 :   ulong parent_idx = fd_funk_txn_idx( funk->txn_pool->ele[ txn_idx ].parent_cidx );
     291             : 
     292      215826 :   if( FD_LIKELY( fd_funk_txn_idx_is_null( parent_idx ) ) ) return fd_funk_txn_idx( funk->shmem->child_head_cidx ); /* opt for incr pub */
     293             : 
     294        9468 :   return fd_funk_txn_idx( funk->txn_pool->ele[ parent_idx ].child_head_cidx );
     295      215826 : }
     296             : 
     297             : /* fd_funk_txn_cancel_sibling_list cancels siblings from sibling_idx down
     298             :    to the youngest sibling inclusive in the order from youngest to
     299             :    sibling_idx.  Callers have already validated our input arguments
     300             :    except sibling_idx.  Returns the number of cancelled transactions
     301             :    (should be at least 1).  If any sibling is skip_idx, it will be not
     302             :    be cancelled but still tagged as visited.  Passing
     303             :    FD_FUNK_TXN_IDX_NULL for skip_idx will cancel all siblings from
     304             :    sibling_idx to the youngest inclusive. */
     305             : 
     306             : static ulong
     307             : fd_funk_txn_cancel_sibling_list( fd_funk_t * funk,
     308             :                                     ulong          tag,
     309             :                                     ulong          sibling_idx,
     310      215826 :                                     ulong          skip_idx ) {
     311             : 
     312      215826 :   ulong cancel_stack_idx = FD_FUNK_TXN_IDX_NULL;
     313             : 
     314             :   /* Push siblings_idx and its younger siblings inclusive (skipping
     315             :      sibling skip_idx if encounter) onto the cancel stack from oldest to
     316             :      youngest (such that we cancel youngest to oldest). */
     317             : 
     318      542949 :   for(;;) {
     319             : 
     320             :     /* At this point, sibling_idx is a sibling we might want to add to
     321             :        the sibling stack.  Validate and tag it. */
     322             : 
     323      542949 :     fd_funk_txn_t * sibling = &funk->txn_pool->ele[ sibling_idx ];
     324      542949 :     sibling->tag = tag;
     325             : 
     326      542949 :     if( FD_UNLIKELY( sibling_idx!=skip_idx ) ) { /* Not skip_idx so push onto the cancel stack, opt for non-compete */
     327      327123 :       sibling->stack_cidx = fd_funk_txn_cidx( cancel_stack_idx );
     328      327123 :       cancel_stack_idx = sibling_idx;
     329      327123 :     }
     330             : 
     331      542949 :     ulong younger_idx = fd_funk_txn_idx( sibling->sibling_next_cidx );
     332      542949 :     if( FD_LIKELY( fd_funk_txn_idx_is_null( younger_idx ) ) ) break; /* opt for non-compete */
     333      327123 :     sibling_idx = younger_idx;
     334             : 
     335      327123 :   }
     336             : 
     337             :   /* Cancel all transactions and their descendants on the cancel stack */
     338             : 
     339      215826 :   ulong cancel_cnt = 0UL;
     340             : 
     341      542949 :   while( !fd_funk_txn_idx_is_null( cancel_stack_idx ) ) { /* TODO: peel first iter to make more predictable? */
     342      327123 :     ulong sibling_idx = cancel_stack_idx;
     343      327123 :     cancel_stack_idx  = fd_funk_txn_idx( funk->txn_pool->ele[ sibling_idx ].stack_cidx );
     344      327123 :     cancel_cnt += fd_funk_txn_cancel_family( funk, tag, sibling_idx );
     345      327123 :   }
     346             : 
     347      215826 :   return cancel_cnt;
     348      215826 : }
     349             : 
     350             : ulong
     351             : fd_funk_txn_cancel_siblings( fd_funk_t *     funk,
     352             :                              fd_funk_txn_t * txn,
     353           0 :                              int             verbose ) {
     354             : 
     355             : #ifdef FD_FUNK_HANDHOLDING
     356             :   if( FD_UNLIKELY( !funk ) ) {
     357             :     if( FD_UNLIKELY( verbose ) ) FD_LOG_WARNING(( "NULL funk" ));
     358             :     return 0UL;
     359             :   }
     360             :   if( FD_UNLIKELY( !fd_funk_txn_valid( funk, txn ) ) ) {
     361             :     if( FD_UNLIKELY( verbose ) ) FD_LOG_WARNING(( "bad txn" ));
     362             :     return 0UL;
     363             :   }
     364             : #else
     365           0 :   (void)verbose;
     366           0 : #endif
     367             : 
     368           0 :   ulong txn_idx = (ulong)(txn - funk->txn_pool->ele);
     369             : 
     370           0 :   ulong oldest_idx = fd_funk_txn_oldest_sibling( funk, txn_idx );
     371             : 
     372           0 :   return fd_funk_txn_cancel_sibling_list( funk, funk->shmem->cycle_tag++, oldest_idx, txn_idx );
     373           0 : }
     374             : 
     375             : ulong
     376             : fd_funk_txn_cancel_children( fd_funk_t *     funk,
     377             :                              fd_funk_txn_t * txn,
     378           0 :                              int             verbose ) {
     379             : 
     380             : #ifdef FD_FUNK_HANDHOLDING
     381             :   if( FD_UNLIKELY( !funk ) ) {
     382             :     if( FD_UNLIKELY( verbose ) ) FD_LOG_WARNING(( "NULL funk" ));
     383             :     return 0UL;
     384             :   }
     385             : #else
     386           0 :   (void)verbose;
     387           0 : #endif
     388             : 
     389           0 :   ulong oldest_idx;
     390             : 
     391           0 :   if( FD_LIKELY( txn == NULL ) ) {
     392           0 :     oldest_idx = fd_funk_txn_idx( funk->shmem->child_head_cidx ); /* opt for non-compete */
     393           0 :   } else {
     394           0 :     if( FD_UNLIKELY( !fd_funk_txn_valid( funk, txn ) ) ) {
     395           0 :       if( FD_UNLIKELY( verbose ) ) FD_LOG_CRIT(( "bad txn" ));
     396           0 :       return 0UL;
     397           0 :     }
     398           0 :     oldest_idx = fd_funk_txn_idx( txn->child_head_cidx );
     399           0 :   }
     400             : 
     401           0 :   if( fd_funk_txn_idx_is_null( oldest_idx ) ) {
     402           0 :     return 0UL;
     403           0 :   }
     404             : 
     405           0 :   return fd_funk_txn_cancel_sibling_list( funk, funk->shmem->cycle_tag++, oldest_idx, FD_FUNK_TXN_IDX_NULL );
     406           0 : }
     407             : 
     408             : ulong
     409           0 : fd_funk_txn_cancel_root( fd_funk_t * funk ) {
     410           0 :   fd_funk_rec_map_t * rec_map = funk->rec_map;
     411           0 :   fd_funk_rec_pool_t * rec_pool = funk->rec_pool;
     412           0 :   ulong chain_cnt = fd_funk_rec_map_chain_cnt( rec_map );
     413           0 :   for( ulong chain_idx=0UL; chain_idx<chain_cnt; chain_idx++ ) {
     414           0 :     for(
     415           0 :         fd_funk_rec_map_iter_t iter = fd_funk_rec_map_iter( rec_map, chain_idx );
     416           0 :         !fd_funk_rec_map_iter_done( iter );
     417           0 :         iter = fd_funk_rec_map_iter_next( iter )
     418           0 :     ) {
     419           0 :       for (;;) {
     420           0 :         fd_funk_rec_map_query_t rec_query[1];
     421           0 :         int err = fd_funk_rec_map_remove( rec_map, fd_funk_rec_pair( iter.ele ), NULL, rec_query, FD_MAP_FLAG_BLOCKING );
     422           0 :         if( FD_UNLIKELY( err == FD_MAP_ERR_AGAIN ) ) continue;
     423           0 :         if( err == FD_MAP_ERR_KEY ) break;
     424           0 :         if( FD_UNLIKELY( err != FD_MAP_SUCCESS ) ) FD_LOG_CRIT(( "map corruption" ));
     425           0 :         if( iter.ele != fd_funk_rec_map_query_ele( rec_query ) ) break;
     426           0 :         fd_funk_val_flush( fd_funk_rec_map_iter_ele( iter ), fd_funk_alloc( funk ), fd_funk_wksp( funk ) );
     427           0 :         fd_funk_rec_pool_release( rec_pool, fd_funk_rec_map_query_ele( rec_query ), 1 );
     428           0 :       }
     429           0 :     }
     430           0 :   }
     431             : 
     432           0 :   return 0UL;
     433           0 : }
     434             : 
     435             : /* Cancel all outstanding transactions */
     436             : 
     437             : ulong
     438             : fd_funk_txn_cancel_all( fd_funk_t *     funk,
     439           0 :                         int             verbose ) {
     440           0 :   return fd_funk_txn_cancel_children( funk, NULL, verbose );
     441           0 : }
     442             : 
     443             : /* fd_funk_txn_update applies the record updates in transaction txn_idx
     444             :    to another transaction or the parent transaction.  Callers have
     445             :    already validated our input arguments.
     446             : 
     447             :    On entry, the head/tail of the destination records are at
     448             :    *_dst_rec_head_idx / *_dst_rec_tail_idx.  All transactions on this
     449             :    list will have transaction id dst_xid and vice versa.  That is, this
     450             :    is the record list the last published transaction or txn_idx's
     451             :    in-prep parent transaction.
     452             : 
     453             :    On exit, the head/tail of the updated records is at
     454             :    *_dst_rec_head_idx / *_dst_rec_tail_idx.  As before, all transactions
     455             :    on this list will have transaction id dst_xid and vice versa.
     456             :    Transaction txn_idx will have an _empty_ record list.
     457             : 
     458             :    Updates in the transaction txn_idx are processed from oldest to
     459             :    youngest.  If an update erases an existing record in dest, the record
     460             :    to erase is removed from the destination records without perturbing
     461             :    the order of remaining destination records.  If an update is to
     462             :    update an existing record, the destination record value is updated
     463             :    and the order of the destination records is unchanged.  If an update
     464             :    is to create a new record, the record is appended to the list of
     465             :    existing values as youngest without changing the order of existing
     466             :    values.  If an update erases a record in an in-prep parent, the
     467             :    erasure will be moved into the parent as the youngest without
     468             :    changing the order of existing values. */
     469             : 
     470             : static void
     471             : fd_funk_txn_update( fd_funk_t *               funk,
     472             :                     uint *                    _dst_rec_head_idx, /* Pointer to the dst list head */
     473             :                     uint *                    _dst_rec_tail_idx, /* Pointer to the dst list tail */
     474             :                     ulong                     dst_txn_idx,       /* Transaction index of the merge destination */
     475             :                     fd_funk_txn_xid_t const * dst_xid,           /* dst xid */
     476      215826 :                     ulong                     txn_idx ) {        /* Transaction index of the records to merge */
     477      215826 :   fd_wksp_t *          wksp     = funk->wksp;
     478      215826 :   fd_alloc_t *         alloc    = funk->alloc;
     479      215826 :   fd_funk_rec_map_t *  rec_map  = funk->rec_map;
     480      215826 :   fd_funk_rec_pool_t * rec_pool = funk->rec_pool;
     481      215826 :   fd_funk_txn_pool_t * txn_pool = funk->txn_pool;
     482             : 
     483      215826 :   int const critical = _dst_rec_head_idx==NULL;
     484      215826 :   if( critical ) {
     485             :     /* If the root transaction is being updated, we need to mark
     486             :        the beginning of a critical section becuase fd_funk_purify can't fix it */
     487      206358 :     fd_begin_crit( funk );
     488      206358 :   }
     489             : 
     490      215826 :   fd_funk_txn_t * txn = &txn_pool->ele[ txn_idx ];
     491      215826 :   uint rec_idx = txn->rec_head_idx;
     492      437349 :   while( !fd_funk_rec_idx_is_null( rec_idx ) ) {
     493      221523 :     fd_funk_rec_t * rec = &rec_pool->ele[ rec_idx ];
     494      221523 :     uint next_rec_idx = rec->next_idx;
     495             : 
     496             :     /* See if (dst_xid,key) already exists.  */
     497      221523 :     fd_funk_xid_key_pair_t pair[1];
     498      221523 :     fd_funk_xid_key_pair_init( pair, dst_xid, rec->pair.key );
     499      221523 :     for(;;) {
     500      221523 :       fd_funk_rec_map_query_t rec_query[1];
     501      221523 :       int err = fd_funk_rec_map_remove( rec_map, pair, NULL, rec_query, FD_MAP_FLAG_BLOCKING );
     502      221523 :       if( FD_UNLIKELY( err == FD_MAP_ERR_AGAIN ) ) continue;
     503      221523 :       if( err == FD_MAP_ERR_KEY ) break;
     504      171363 :       if( FD_UNLIKELY( err != FD_MAP_SUCCESS ) ) FD_LOG_CRIT(( "map corruption" ));
     505             : 
     506             :       /* Remove from the transaction */
     507      171363 :       fd_funk_rec_t * rec2 = fd_funk_rec_map_query_ele( rec_query );
     508      171363 :       uint prev_idx = rec2->prev_idx;
     509      171363 :       uint next_idx = rec2->next_idx;
     510      171363 :       if( fd_funk_rec_idx_is_null( prev_idx ) ) {
     511      170595 :         if( _dst_rec_head_idx ) *_dst_rec_head_idx = next_idx;
     512      170595 :       } else {
     513         768 :         rec_pool->ele[ prev_idx ].next_idx = next_idx;
     514         768 :       }
     515      171363 :       if( fd_funk_rec_idx_is_null( next_idx ) ) {
     516      170484 :         if( _dst_rec_tail_idx ) *_dst_rec_tail_idx = prev_idx;
     517      170484 :       } else {
     518         879 :         rec_pool->ele[ next_idx ].prev_idx = prev_idx;
     519         879 :       }
     520             :       /* Clean up value */
     521      171363 :       fd_funk_val_flush( rec2, alloc, wksp );
     522      171363 :       rec2->txn_cidx = fd_funk_txn_cidx( FD_FUNK_TXN_IDX_NULL );
     523      171363 :       fd_funk_rec_pool_release( rec_pool, rec2, 1 );
     524      171363 :       break;
     525      171363 :     }
     526             : 
     527             :     /* Add the new record to the transaction. We can update the xid in
     528             :        place because it is not used for hashing the element. We have
     529             :        to preserve the original element to preserve the
     530             :        newest-to-oldest ordering in the hash
     531             :        chain. fd_funk_rec_query_global relies on this subtle
     532             :        property. */
     533             : 
     534      221523 :     rec->pair.xid[0] = *dst_xid;
     535      221523 :     rec->txn_cidx = fd_funk_txn_cidx( dst_txn_idx );
     536             : 
     537      221523 :     rec->prev_idx = FD_FUNK_REC_IDX_NULL;
     538      221523 :     if( _dst_rec_head_idx ) {
     539       50745 :       if( fd_funk_rec_idx_is_null( *_dst_rec_head_idx ) ) {
     540        4842 :         *_dst_rec_head_idx = rec_idx;
     541       45903 :       } else {
     542       45903 :         rec_pool->ele[ *_dst_rec_tail_idx ].next_idx = rec_idx;
     543       45903 :         rec->prev_idx = *_dst_rec_tail_idx;
     544       45903 :       }
     545       50745 :       *_dst_rec_tail_idx = rec_idx;
     546       50745 :     }
     547      221523 :     rec->next_idx = FD_FUNK_REC_IDX_NULL;
     548             : 
     549      221523 :     rec_idx = next_rec_idx;
     550      221523 :   }
     551             : 
     552      215826 :   txn_pool->ele[ txn_idx ].rec_head_idx = FD_FUNK_REC_IDX_NULL;
     553      215826 :   txn_pool->ele[ txn_idx ].rec_tail_idx = FD_FUNK_REC_IDX_NULL;
     554             : 
     555      215826 :   if( critical ) {
     556      206358 :     fd_end_crit( funk );
     557      206358 :   }
     558      215826 : }
     559             : 
     560             : /* fd_funk_txn_publish_funk_child publishes a transaction that is known
     561             :    to be a child of funk.  Callers have already validated our input
     562             :    arguments.  Returns FD_FUNK_SUCCESS on success and an FD_FUNK_ERR_*
     563             :    code on failure.  (There are currently no failure cases but the
     564             :    plumbing is there if value handling requires it at some point.) */
     565             : 
     566             : static int
     567             : fd_funk_txn_publish_funk_child( fd_funk_t * const funk,
     568             :                                 ulong       const tag,
     569      203826 :                                 ulong       const txn_idx ) {
     570             : 
     571             :   /* Apply the updates in txn to the last published transactions */
     572             : 
     573      203826 :   fd_funk_txn_update( funk, NULL, NULL, FD_FUNK_TXN_IDX_NULL, fd_funk_root( funk ), txn_idx );
     574             : 
     575             :   /* Cancel all competing transaction histories */
     576             : 
     577      203826 :   ulong oldest_idx = fd_funk_txn_oldest_sibling( funk, txn_idx );
     578      203826 :   fd_funk_txn_cancel_sibling_list( funk, tag, oldest_idx, txn_idx );
     579             : 
     580             :   /* Make all the children children of funk */
     581             : 
     582      203826 :   fd_funk_txn_t * txn = fd_funk_txn_pool_ele( funk->txn_pool, txn_idx );
     583      203826 :   ulong child_head_idx = fd_funk_txn_idx( txn->child_head_cidx );
     584      203826 :   ulong child_tail_idx = fd_funk_txn_idx( txn->child_tail_cidx );
     585             : 
     586      203826 :   ulong child_idx = child_head_idx;
     587      385290 :   while( FD_UNLIKELY( !fd_funk_txn_idx_is_null( child_idx ) ) ) { /* opt for incr pub */
     588      181464 :     fd_funk_txn_t * child_txn = fd_funk_txn_pool_ele( funk->txn_pool, child_idx );
     589      181464 :     child_txn->tag = tag;
     590      181464 :     child_txn->parent_cidx = fd_funk_txn_cidx( FD_FUNK_TXN_IDX_NULL );
     591      181464 :     child_idx = fd_funk_txn_idx( child_txn->sibling_next_cidx );
     592      181464 :   }
     593             : 
     594      203826 :   funk->shmem->child_head_cidx = fd_funk_txn_cidx( child_head_idx );
     595      203826 :   funk->shmem->child_tail_cidx = fd_funk_txn_cidx( child_tail_idx );
     596             : 
     597      203826 :   fd_funk_txn_xid_copy( funk->shmem->last_publish, fd_funk_txn_xid( txn ) );
     598             : 
     599             :   /* Remove the mapping */
     600             : 
     601      203826 :   fd_funk_txn_map_query_t query[1];
     602      203826 :   if( fd_funk_txn_map_remove( funk->txn_map, funk->shmem->last_publish, NULL, query, FD_MAP_FLAG_BLOCKING ) == FD_MAP_SUCCESS ) {
     603      203826 :     fd_funk_txn_pool_release( funk->txn_pool, txn, 1 );
     604      203826 :   }
     605             : 
     606      203826 :   return FD_FUNK_SUCCESS;
     607      203826 : }
     608             : 
     609             : ulong
     610             : fd_funk_txn_publish( fd_funk_t *     funk,
     611             :                      fd_funk_txn_t * txn,
     612      147603 :                      int             verbose ) {
     613             : 
     614             : #ifdef FD_FUNK_HANDHOLDING
     615             :   if( FD_UNLIKELY( !funk ) ) {
     616             :     if( FD_UNLIKELY( verbose ) ) FD_LOG_WARNING(( "NULL funk" ));
     617             :     return 0UL;
     618             :   }
     619             :   if( FD_UNLIKELY( !fd_funk_txn_valid( funk, txn ) ) ) {
     620             :     if( FD_UNLIKELY( verbose ) ) FD_LOG_WARNING(( "bad txn" ));
     621             :     return 0UL;
     622             :   }
     623             : #else
     624      147603 :   (void)verbose;
     625      147603 : #endif
     626             : 
     627      147603 :   ulong txn_idx = (ulong)(txn - funk->txn_pool->ele);
     628             : 
     629      147603 :   ulong tag = funk->shmem->cycle_tag++;
     630             : 
     631      147603 :   ulong publish_stack_idx = FD_FUNK_TXN_IDX_NULL;
     632             : 
     633      203826 :   for(;;) {
     634      203826 :     fd_funk_txn_t * txn2 = &funk->txn_pool->ele[ txn_idx ];
     635      203826 :     txn2->tag = tag;
     636             : 
     637             :     /* At this point, txn_idx is a transaction that needs to be
     638             :        published and has been tagged.  If txn is a child of funk, we are
     639             :        ready to publish txn and everything on the publish stack. */
     640             : 
     641      203826 :     ulong parent_idx = fd_funk_txn_idx( txn2->parent_cidx );
     642      203826 :     if( FD_LIKELY( fd_funk_txn_idx_is_null( parent_idx ) ) ) break; /* opt for incr pub */
     643             : 
     644             :     /* txn_idx has a parent.  Validate and tag it.  Push txn to the
     645             :        publish stack and recurse into the parent. */
     646             : 
     647       56223 :     txn2->stack_cidx = fd_funk_txn_cidx( publish_stack_idx );
     648       56223 :     publish_stack_idx = txn_idx;
     649             : 
     650       56223 :     txn_idx = parent_idx;
     651       56223 :   }
     652             : 
     653      147603 :   ulong publish_cnt = 0UL;
     654             : 
     655      203826 :   for(;;) {
     656             : 
     657             :     /* At this point, all the transactions we need to publish are
     658             :        tagged, txn is the next up publish funk and publish_stack has the
     659             :        transactions to follow in order by pop.  We use a new tag for
     660             :        each publish as txn and its siblings we potentially visited in a
     661             :        previous iteration of this loop. */
     662             : 
     663      203826 :     if( FD_UNLIKELY( fd_funk_txn_publish_funk_child( funk, funk->shmem->cycle_tag++, txn_idx ) ) ) break;
     664      203826 :     publish_cnt++;
     665             : 
     666      203826 :     txn_idx = publish_stack_idx;
     667      203826 :     if( FD_LIKELY( fd_funk_txn_idx_is_null( txn_idx ) ) ) break; /* opt for incr pub */
     668       56223 :     publish_stack_idx = fd_funk_txn_idx( funk->txn_pool->ele[ txn_idx ].stack_cidx );
     669       56223 :   }
     670             : 
     671      147603 :   return publish_cnt;
     672      147603 : }
     673             : 
     674             : int
     675             : fd_funk_txn_publish_into_parent( fd_funk_t *     funk,
     676             :                                  fd_funk_txn_t * txn,
     677       12000 :                                  int             verbose ) {
     678             : #ifdef FD_FUNK_HANDHOLDING
     679             :   if( FD_UNLIKELY( !funk ) ) {
     680             :     if( FD_UNLIKELY( verbose ) ) FD_LOG_WARNING(( "NULL funk" ));
     681             :     return FD_FUNK_ERR_INVAL;
     682             :   }
     683             :   if( FD_UNLIKELY( !fd_funk_txn_valid( funk, txn ) ) ) {
     684             :     if( FD_UNLIKELY( verbose ) ) FD_LOG_WARNING(( "bad txn" ));
     685             :     return 0UL;
     686             :   }
     687             : #else
     688       12000 :   (void)verbose;
     689       12000 : #endif
     690             : 
     691       12000 :   fd_funk_txn_map_t *  txn_map  = funk->txn_map;
     692       12000 :   fd_funk_txn_pool_t * txn_pool = funk->txn_pool;
     693       12000 :   ulong txn_idx = (ulong)(txn - txn_pool->ele);
     694             : 
     695       12000 :   ulong oldest_idx = fd_funk_txn_oldest_sibling( funk, txn_idx );
     696       12000 :   fd_funk_txn_cancel_sibling_list( funk, funk->shmem->cycle_tag++, oldest_idx, txn_idx );
     697             : 
     698       12000 :   ulong parent_idx = fd_funk_txn_idx( txn->parent_cidx );
     699       12000 :   if( fd_funk_txn_idx_is_null( parent_idx ) ) {
     700             :     /* Publish to root */
     701        2532 :     fd_funk_txn_update( funk, NULL, NULL, FD_FUNK_TXN_IDX_NULL, fd_funk_root( funk ), txn_idx );
     702             :     /* Inherit the children */
     703        2532 :     funk->shmem->child_head_cidx = txn->child_head_cidx;
     704        2532 :     funk->shmem->child_tail_cidx = txn->child_tail_cidx;
     705        9468 :   } else {
     706        9468 :     fd_funk_txn_t * parent_txn = &txn_pool->ele[ parent_idx ];
     707        9468 :     fd_funk_txn_update( funk, &parent_txn->rec_head_idx, &parent_txn->rec_tail_idx, parent_idx, &parent_txn->xid, txn_idx );
     708             :     /* Inherit the children */
     709        9468 :     parent_txn->child_head_cidx = txn->child_head_cidx;
     710        9468 :     parent_txn->child_tail_cidx = txn->child_tail_cidx;
     711        9468 :   }
     712             : 
     713             :   /* Adjust the parent pointers of the children to point to their grandparent */
     714       12000 :   ulong child_idx = fd_funk_txn_idx( txn->child_head_cidx );
     715       21174 :   while( FD_UNLIKELY( !fd_funk_txn_idx_is_null( child_idx ) ) ) {
     716        9174 :     txn_pool->ele[ child_idx ].parent_cidx = fd_funk_txn_cidx( parent_idx );
     717        9174 :     child_idx = fd_funk_txn_idx( txn_pool->ele[ child_idx ].sibling_next_cidx );
     718        9174 :   }
     719             : 
     720       12000 :   fd_funk_txn_map_query_t query[1];
     721       12000 :   if( fd_funk_txn_map_remove( txn_map, fd_funk_txn_xid( txn ), NULL, query, FD_MAP_FLAG_BLOCKING ) == FD_MAP_SUCCESS ) {
     722       12000 :     fd_funk_txn_pool_release( txn_pool, txn, 1 );
     723       12000 :   }
     724             : 
     725       12000 :   return FD_FUNK_SUCCESS;
     726       12000 : }
     727             : 
     728             : fd_funk_rec_t const *
     729             : fd_funk_txn_first_rec( fd_funk_t *           funk,
     730    47624211 :                        fd_funk_txn_t const * txn ) {
     731    47624211 :   if( FD_UNLIKELY( !txn ) ) return NULL;
     732    44376480 :   uint rec_idx = txn->rec_head_idx;
     733    44376480 :   if( fd_funk_rec_idx_is_null( rec_idx ) ) return NULL;
     734    28516608 :   return funk->rec_pool->ele + rec_idx;
     735    44376480 : }
     736             : 
     737             : fd_funk_rec_t const *
     738             : fd_funk_txn_last_rec( fd_funk_t *           funk,
     739           0 :                       fd_funk_txn_t const * txn ) {
     740           0 :   if( FD_UNLIKELY( !txn ) ) return NULL;
     741           0 :   uint rec_idx = txn->rec_tail_idx;
     742           0 :   if( fd_funk_rec_idx_is_null( rec_idx ) ) return NULL;
     743           0 :   return funk->rec_pool->ele + rec_idx;
     744           0 : }
     745             : 
     746             : /* Return the next record in a transaction. Returns NULL if the
     747             :    transaction has no more records. */
     748             : 
     749             : fd_funk_rec_t const *
     750             : fd_funk_txn_next_rec( fd_funk_t *           funk,
     751   445015851 :                       fd_funk_rec_t const * rec ) {
     752   445015851 :   uint rec_idx = rec->next_idx;
     753   445015851 :   if( fd_funk_rec_idx_is_null( rec_idx ) ) return NULL;
     754   187996728 :   return funk->rec_pool->ele + rec_idx;
     755   445015851 : }
     756             : 
     757             : fd_funk_rec_t const *
     758             : fd_funk_txn_prev_rec( fd_funk_t *           funk,
     759   318768039 :                       fd_funk_rec_t const * rec ) {
     760   318768039 :   uint rec_idx = rec->prev_idx;
     761   318768039 :   if( fd_funk_rec_idx_is_null( rec_idx ) ) return NULL;
     762    90265524 :   return funk->rec_pool->ele + rec_idx;
     763   318768039 : }
     764             : 
     765             : fd_funk_txn_xid_t
     766    18918894 : fd_funk_generate_xid(void) {
     767    18918894 :   fd_funk_txn_xid_t xid;
     768    18918894 :   static FD_TL ulong seq = 0;
     769    18918894 :   xid.ul[0] =
     770    18918894 :     (fd_log_cpu_id() + 1U)*3138831853UL +
     771    18918894 :     (fd_log_thread_id() + 1U)*9180195821UL +
     772    18918894 :     (++seq)*6208101967UL;
     773    18918894 :   xid.ul[1] = ((ulong)fd_tickcount())*2810745731UL;
     774    18918894 :   return xid;
     775    18918894 : }
     776             : 
     777             : static void
     778     1949853 : fd_funk_txn_all_iter_skip_nulls( fd_funk_txn_all_iter_t * iter ) {
     779     1949853 :   if( iter->chain_idx == iter->chain_cnt ) return;
     780     9948894 :   while( fd_funk_txn_map_iter_done( iter->txn_map_iter ) ) {
     781     8101068 :     if( ++(iter->chain_idx) == iter->chain_cnt ) break;
     782     7999041 :     iter->txn_map_iter = fd_funk_txn_map_iter( &iter->txn_map, iter->chain_idx );
     783     7999041 :   }
     784     1949853 : }
     785             : 
     786             : void
     787             : fd_funk_txn_all_iter_new( fd_funk_t *              funk,
     788      102027 :                           fd_funk_txn_all_iter_t * iter ) {
     789      102027 :   iter->txn_map = *funk->txn_map;
     790      102027 :   iter->chain_cnt = fd_funk_txn_map_chain_cnt( funk->txn_map );
     791      102027 :   iter->chain_idx = 0;
     792      102027 :   iter->txn_map_iter = fd_funk_txn_map_iter( funk->txn_map, 0 );
     793      102027 :   fd_funk_txn_all_iter_skip_nulls( iter );
     794      102027 : }
     795             : 
     796             : int
     797     1949853 : fd_funk_txn_all_iter_done( fd_funk_txn_all_iter_t * iter ) {
     798     1949853 :   return ( iter->chain_idx == iter->chain_cnt );
     799     1949853 : }
     800             : 
     801             : void
     802     1847826 : fd_funk_txn_all_iter_next( fd_funk_txn_all_iter_t * iter ) {
     803     1847826 :   iter->txn_map_iter = fd_funk_txn_map_iter_next( iter->txn_map_iter );
     804     1847826 :   fd_funk_txn_all_iter_skip_nulls( iter );
     805     1847826 : }
     806             : 
     807             : fd_funk_txn_t const *
     808     1847826 : fd_funk_txn_all_iter_ele_const( fd_funk_txn_all_iter_t * iter ) {
     809     1847826 :   return fd_funk_txn_map_iter_ele_const( iter->txn_map_iter );
     810     1847826 : }
     811             : 
     812             : fd_funk_txn_t *
     813           0 : fd_funk_txn_all_iter_ele( fd_funk_txn_all_iter_t * iter ) {
     814           0 :   return fd_funk_txn_map_iter_ele( iter->txn_map_iter );
     815           0 : }
     816             : 
     817             : int
     818          12 : fd_funk_txn_verify( fd_funk_t * funk ) {
     819          12 :   fd_funk_txn_map_t *  txn_map  = funk->txn_map;
     820          12 :   fd_funk_txn_pool_t * txn_pool = funk->txn_pool;
     821          12 :   ulong                txn_max  = fd_funk_txn_pool_ele_max( txn_pool );
     822             : 
     823          12 :   ulong funk_child_head_idx = fd_funk_txn_idx( funk->shmem->child_head_cidx ); /* Previously verified */
     824          12 :   ulong funk_child_tail_idx = fd_funk_txn_idx( funk->shmem->child_tail_cidx ); /* Previously verified */
     825             : 
     826          12 :   fd_funk_txn_xid_t const * last_publish = funk->shmem->last_publish; /* Previously verified */
     827             : 
     828          24 : # define TEST(c) do {                                                                           \
     829          24 :     if( FD_UNLIKELY( !(c) ) ) { FD_LOG_WARNING(( "FAIL: %s", #c )); return FD_FUNK_ERR_INVAL; } \
     830          24 :   } while(0)
     831             : 
     832          12 : # define IS_VALID( idx ) ( (idx==FD_FUNK_TXN_IDX_NULL) || \
     833          12 :                            ((idx<txn_max) && (!fd_funk_txn_xid_eq( fd_funk_txn_xid( &txn_pool->ele[idx] ), last_publish ))) )
     834             : 
     835          12 :   TEST( !fd_funk_txn_map_verify( txn_map ) );
     836          12 :   TEST( !fd_funk_txn_pool_verify( txn_pool ) );
     837             : 
     838             :   /* Tag all transactions as not visited yet */
     839             : 
     840     1572876 :   for( ulong txn_idx=0UL; txn_idx<txn_max; txn_idx++ ) txn_pool->ele[ txn_idx ].tag = 0UL;
     841             : 
     842             :   /* Visit all transactions in preparation, traversing from oldest to
     843             :      youngest. */
     844             : 
     845          12 :   do {
     846             : 
     847             :     /* Push all children of funk to the stack */
     848             : 
     849          12 :     ulong stack_idx = FD_FUNK_TXN_IDX_NULL;
     850          12 :     ulong child_idx = funk_child_head_idx;
     851          12 :     while( !fd_funk_txn_idx_is_null( child_idx ) ) {
     852             : 
     853             :       /* Make sure valid idx, not tagged (detects cycles) and child
     854             :          knows it is a child of funk.  Then tag as visited / in-prep,
     855             :          push to stack and update prep_cnt */
     856             : 
     857           0 :       TEST( IS_VALID( child_idx ) );
     858           0 :       TEST( !txn_pool->ele[ child_idx ].tag );
     859           0 :       TEST( fd_funk_txn_idx_is_null( fd_funk_txn_idx( txn_pool->ele[ child_idx ].parent_cidx ) ) );
     860           0 :       txn_pool->ele[ child_idx ].tag        = 1UL;
     861           0 :       txn_pool->ele[ child_idx ].stack_cidx = fd_funk_txn_cidx( stack_idx );
     862           0 :       stack_idx                   = child_idx;
     863             : 
     864           0 :       ulong next_idx = fd_funk_txn_idx( txn_pool->ele[ child_idx ].sibling_next_cidx );
     865           0 :       if( !fd_funk_txn_idx_is_null( next_idx ) ) TEST( fd_funk_txn_idx( txn_pool->ele[ next_idx ].sibling_prev_cidx )==child_idx );
     866           0 :       child_idx = next_idx;
     867           0 :     }
     868             : 
     869          12 :     while( !fd_funk_txn_idx_is_null( stack_idx ) ) {
     870             : 
     871             :       /* Pop the next transaction to traverse */
     872             : 
     873           0 :       ulong txn_idx = stack_idx;
     874           0 :       stack_idx = fd_funk_txn_idx( txn_pool->ele[ txn_idx ].stack_cidx );
     875             : 
     876             :       /* Push all children of txn to the stack */
     877             : 
     878           0 :       ulong child_idx = fd_funk_txn_idx( txn_pool->ele[ txn_idx ].child_head_cidx );
     879           0 :       while( !fd_funk_txn_idx_is_null( child_idx ) ) {
     880             : 
     881             :         /* Make sure valid idx, not tagged (detects cycles) and child
     882             :            knows it is a child of txn_idx.  Then tag as visited /
     883             :            in-prep, push to stack and update prep_cnt */
     884             : 
     885           0 :         TEST( IS_VALID( child_idx ) );
     886           0 :         TEST( !txn_pool->ele[ child_idx ].tag );
     887           0 :         TEST( fd_funk_txn_idx( txn_pool->ele[ child_idx ].parent_cidx )==txn_idx );
     888           0 :         txn_pool->ele[ child_idx ].tag        = 1UL;
     889           0 :         txn_pool->ele[ child_idx ].stack_cidx = fd_funk_txn_cidx( stack_idx );
     890           0 :         stack_idx                   = child_idx;
     891             : 
     892           0 :         ulong next_idx = fd_funk_txn_idx( txn_pool->ele[ child_idx ].sibling_next_cidx );
     893           0 :         if( !fd_funk_txn_idx_is_null( next_idx ) ) TEST( fd_funk_txn_idx( txn_pool->ele[ next_idx ].sibling_prev_cidx )==child_idx );
     894           0 :         child_idx = next_idx;
     895           0 :       }
     896           0 :     }
     897             : 
     898          12 :   } while(0);
     899             : 
     900             :   /* Do it again with a youngest to oldest traversal to test reverse
     901             :      link integrity */
     902             : 
     903          12 :   do {
     904             : 
     905             :     /* Push all children of funk to the stack */
     906             : 
     907          12 :     ulong stack_idx = FD_FUNK_TXN_IDX_NULL;
     908          12 :     ulong child_idx = funk_child_tail_idx;
     909          12 :     while( !fd_funk_txn_idx_is_null( child_idx ) ) {
     910             : 
     911             :       /* Make sure valid idx, tagged as visited above (detects cycles)
     912             :          and child knows it is a child of funk.  Then tag as visited /
     913             :          in-prep, push to stack and update prep_cnt */
     914             : 
     915           0 :       TEST( IS_VALID( child_idx ) );
     916           0 :       TEST( txn_pool->ele[ child_idx ].tag==1UL );
     917           0 :       TEST( fd_funk_txn_idx_is_null( fd_funk_txn_idx( txn_pool->ele[ child_idx ].parent_cidx ) ) );
     918           0 :       txn_pool->ele[ child_idx ].tag        = 2UL;
     919           0 :       txn_pool->ele[ child_idx ].stack_cidx = fd_funk_txn_cidx( stack_idx );
     920           0 :       stack_idx                             = child_idx;
     921             : 
     922           0 :       ulong prev_idx = fd_funk_txn_idx( txn_pool->ele[ child_idx ].sibling_prev_cidx );
     923           0 :       if( !fd_funk_txn_idx_is_null( prev_idx ) ) TEST( fd_funk_txn_idx( txn_pool->ele[ prev_idx ].sibling_next_cidx )==child_idx );
     924           0 :       child_idx = prev_idx;
     925           0 :     }
     926             : 
     927          12 :     while( !fd_funk_txn_idx_is_null( stack_idx ) ) {
     928             : 
     929             :       /* Pop the next transaction to traverse */
     930             : 
     931           0 :       ulong txn_idx = stack_idx;
     932           0 :       stack_idx = fd_funk_txn_idx( txn_pool->ele[ txn_idx ].stack_cidx );
     933             : 
     934             :       /* Push all children of txn to the stack */
     935             : 
     936           0 :       ulong child_idx = fd_funk_txn_idx( txn_pool->ele[ txn_idx ].child_tail_cidx );
     937           0 :       while( !fd_funk_txn_idx_is_null( child_idx ) ) {
     938             : 
     939             :         /* Make sure valid idx, tagged as visited above (detects cycles)
     940             :            and child knows it is a child of txn_idx.  Then, tag as
     941             :            visited / in-prep, push to stack and update prep_cnt */
     942             : 
     943           0 :         TEST( IS_VALID( child_idx ) );
     944           0 :         TEST( txn_pool->ele[ child_idx ].tag==1UL );
     945           0 :         TEST( fd_funk_txn_idx( txn_pool->ele[ child_idx ].parent_cidx )==txn_idx );
     946           0 :         txn_pool->ele[ child_idx ].tag        = 2UL;
     947           0 :         txn_pool->ele[ child_idx ].stack_cidx = fd_funk_txn_cidx( stack_idx );
     948           0 :         stack_idx                             = child_idx;
     949             : 
     950           0 :         ulong prev_idx = fd_funk_txn_idx( txn_pool->ele[ child_idx ].sibling_prev_cidx );
     951           0 :         if( !fd_funk_txn_idx_is_null( prev_idx ) ) TEST( fd_funk_txn_idx( txn_pool->ele[ prev_idx ].sibling_next_cidx )==child_idx );
     952           0 :         child_idx = prev_idx;
     953           0 :       }
     954           0 :     }
     955          12 :   } while(0);
     956             : 
     957          12 : # undef IS_VALID
     958          12 : # undef TEST
     959             : 
     960          12 :   return FD_FUNK_SUCCESS;
     961          12 : }
     962             : 
     963             : int
     964           0 : fd_funk_txn_valid( fd_funk_t const * funk, fd_funk_txn_t const * txn ) {
     965           0 :   ulong txn_idx = (ulong)(txn - funk->txn_pool->ele);
     966           0 :   ulong txn_max = fd_funk_txn_pool_ele_max( funk->txn_pool );
     967           0 :   if( txn_idx>=txn_max || txn != txn_idx + funk->txn_pool->ele ) return 0;
     968           0 :   fd_funk_txn_map_query_t query[1];
     969           0 :   int    err  = FD_MAP_ERR_AGAIN;
     970           0 :   while( err == FD_MAP_ERR_AGAIN ) {
     971           0 :     err = fd_funk_txn_map_query_try( funk->txn_map, &txn->xid, NULL, query, 0 );
     972           0 :     if( FD_UNLIKELY( err == FD_MAP_ERR_KEY ) ) {
     973           0 :       FD_LOG_DEBUG(( "fd_funk_txn_map_query_try() failed: %d on chain %lu", err, fd_funk_txn_map_iter_chain_idx( funk->txn_map, &txn->xid ) ));
     974           0 :       return 0;
     975           0 :     }
     976           0 :     if( FD_UNLIKELY( err == FD_MAP_ERR_CORRUPT ) ) {
     977           0 :       FD_LOG_WARNING(( "fd_funk_txn_map_query_try() failed: %d on chain %lu", err, fd_funk_txn_map_iter_chain_idx( funk->txn_map, &txn->xid ) ));
     978           0 :       return 0;
     979           0 :     }
     980           0 :     if( FD_LIKELY( err == FD_MAP_SUCCESS ) ) {
     981           0 :       if( fd_funk_txn_map_query_ele( query ) != txn ) {
     982           0 :         FD_LOG_WARNING(( "fd_funk_txn_map_query_ele() failed: %p != %p", (void *)fd_funk_txn_map_query_ele( query ), (void *)txn ));
     983           0 :         return 0;
     984           0 :       }
     985           0 :       break;
     986           0 :     }
     987             :     /* Normally we'd do this, but we didn't really do any non-atomic reads of element fields.
     988             :        err = fd_funk_txn_map_query_test( query ); */
     989           0 :   }
     990           0 :   return 1;
     991           0 : }

Generated by: LCOV version 1.14