|           Line data    Source code 
       1             : #include "fd_funk_txn.h"
       2             : #include "fd_funk.h"
       3             : 
       4             : /* Provide the actual transaction map implementation */
       5             : 
       6             : #define POOL_NAME          fd_funk_txn_pool
       7     1144434 : #define POOL_ELE_T         fd_funk_txn_t
       8             : #define POOL_IDX_T         uint
       9     4300359 : #define POOL_NEXT          map_next
      10             : #define POOL_IMPL_STYLE    2
      11             : #include "../util/tmpl/fd_pool_para.c"
      12             : 
      13             : #define MAP_NAME              fd_funk_txn_map
      14     2968848 : #define MAP_ELE_T             fd_funk_txn_t
      15         591 : #define MAP_KEY_T             fd_funk_txn_xid_t
      16      572466 : #define MAP_KEY               xid
      17             : #define MAP_KEY_EQ(k0,k1)     fd_funk_txn_xid_eq((k0),(k1))
      18             : #define MAP_KEY_HASH(k0,seed) fd_funk_txn_xid_hash((k0),(seed))
      19     1879689 : #define MAP_NEXT              map_next
      20         111 : #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      571875 : #define fd_funk_txn_state_transition(txn, before, after) do {             \
      25      571875 :   FD_LOG_INFO(( "funk_txn laddr=%p xid=%lu:%lu state change (%u-%s) -> (%u-%s)", \
      26      571875 :                 (void *)(txn),                                            \
      27      571875 :                 (txn)->xid.ul[0], (txn)->xid.ul[1],                       \
      28      571875 :                 (before), fd_funk_txn_state_str( (before) ),              \
      29      571875 :                 (after),  fd_funk_txn_state_str( (after)  ) ));           \
      30      571875 :   if( FD_HAS_ATOMIC ) {                                                   \
      31      571875 :     if( FD_LIKELY( __sync_bool_compare_and_swap( &(txn)->state, before, after ) ) ) break; \
      32      571875 :   } else {                                                                \
      33           0 :     if( FD_LIKELY( (txn)->state == (before) ) ) {                         \
      34           0 :       (txn)->state = (after);                                             \
      35           0 :       break;                                                              \
      36           0 :     }                                                                     \
      37           0 :   }                                                                       \
      38      571875 :   uint have_ = FD_VOLATILE_CONST( (txn)->state );                         \
      39           0 :   FD_LOG_CRIT(( "Detected data race on funk txn %p: expected state %u-%s, found %u-%s, while transitioning to %u-%s", \
      40           0 :                 (void *)(txn),                                            \
      41           0 :                 (before), fd_funk_txn_state_str( before ),                \
      42           0 :                 have_,    fd_funk_txn_state_str( have_  ),                \
      43           0 :                 (after),  fd_funk_txn_state_str( after  ) ));             \
      44           0 : } while(0)
      45             : 
      46             : #define fd_funk_last_publish_transition(funk_shmem, after) do {           \
      47             :     fd_funk_shmem_t *   _shmem    = (funk_shmem);                         \
      48             :     fd_funk_txn_xid_t * _last_pub = _shmem->last_publish;                 \
      49             :     fd_funk_txn_xid_t   _prev_pub[1]; fd_funk_txn_xid_copy( _prev_pub, _last_pub ); \
      50             :     fd_funk_txn_xid_copy( _last_pub, (after) );                           \
      51             :     FD_LOG_INFO(( "funk last_publish (%lu:%lu) -> (%lu:%lu)",             \
      52             :                   _prev_pub->ul[0], _prev_pub->ul[1],                     \
      53             :                   _last_pub->ul[0], _last_pub->ul[1] ));                  \
      54             :   } while(0)
      55             : 
      56             : void
      57             : fd_funk_txn_prepare( fd_funk_t *               funk,
      58             :                      fd_funk_txn_xid_t const * parent_xid,
      59      571875 :                      fd_funk_txn_xid_t const * xid ) {
      60             : 
      61      571875 :   if( FD_UNLIKELY( !funk       ) ) FD_LOG_CRIT(( "NULL funk"       ));
      62      571875 :   if( FD_UNLIKELY( !parent_xid ) ) FD_LOG_CRIT(( "NULL parent_xid" ));
      63      571875 :   if( FD_UNLIKELY( !xid        ) ) FD_LOG_CRIT(( "NULL xid"        ));
      64      571875 :   if( FD_UNLIKELY( fd_funk_txn_xid_eq_root( xid ) ) ) FD_LOG_CRIT(( "xid is root" ));
      65             : 
      66      571875 :   if( FD_UNLIKELY( fd_funk_txn_xid_eq( xid, funk->shmem->last_publish ) ) ) {
      67           0 :     FD_LOG_ERR(( "fd_funk_txn_prepare failed: xid %lu:%lu is the last published",
      68           0 :                  xid->ul[0], xid->ul[1] ));
      69           0 :   }
      70             : 
      71      571875 :   fd_funk_txn_map_query_t query[1];
      72      571875 :   if( FD_UNLIKELY( fd_funk_txn_map_query_try( funk->txn_map, xid, NULL, query, 0 ) != FD_MAP_ERR_KEY ) ) {
      73           0 :     FD_LOG_ERR(( "fd_funk_txn_prepare failed: xid %lu:%lu already in use",
      74           0 :                  xid->ul[0], xid->ul[1] ));
      75           0 :   }
      76             : 
      77      571875 :   ulong  parent_idx;
      78      571875 :   uint * _child_head_cidx;
      79      571875 :   uint * _child_tail_cidx;
      80             : 
      81      571875 :   if( FD_UNLIKELY( fd_funk_txn_xid_eq( parent_xid, funk->shmem->last_publish ) ) ) {
      82             : 
      83      254472 :     parent_idx = FD_FUNK_TXN_IDX_NULL;
      84             : 
      85      254472 :     _child_head_cidx = &funk->shmem->child_head_cidx;
      86      254472 :     _child_tail_cidx = &funk->shmem->child_tail_cidx;
      87             : 
      88      317403 :   } else {
      89             : 
      90      317403 :     int query_err = fd_funk_txn_map_query_try( funk->txn_map, parent_xid, NULL, query, 0 );
      91      317403 :     if( FD_UNLIKELY( query_err!=FD_MAP_SUCCESS ) ) {
      92           0 :       FD_LOG_CRIT(( "fd_funk_txn_prepare failed: user provided invalid parent XID %lu:%lu (err %i-%s)",
      93           0 :                     parent_xid->ul[0], parent_xid->ul[1],
      94           0 :                     query_err, fd_map_strerror( query_err ) ));
      95           0 :     }
      96             : 
      97      317403 :     fd_funk_txn_t * parent = fd_funk_txn_map_query_ele( query );
      98      317403 :     fd_funk_txn_state_assert( parent, FD_FUNK_TXN_STATE_ACTIVE );
      99      317403 :     parent_idx = (ulong)(parent - funk->txn_pool->ele);
     100             : 
     101      317403 :     _child_head_cidx = &parent->child_head_cidx;
     102      317403 :     _child_tail_cidx = &parent->child_tail_cidx;
     103             : 
     104      317403 :   }
     105             : 
     106             :   /* Get a new transaction from the map */
     107             : 
     108      571875 :   fd_funk_txn_t * txn = fd_funk_txn_pool_acquire( funk->txn_pool, NULL, 1, NULL );
     109      571875 :   if( FD_UNLIKELY( !txn ) ) FD_LOG_ERR(( "fd_funk_txn_prepare failed: transaction object pool out of memory" ));
     110      571875 :   fd_funk_txn_xid_copy( &txn->xid, xid );
     111      571875 :   ulong txn_idx = (ulong)(txn - funk->txn_pool->ele);
     112             : 
     113             :   /* Join the family */
     114             : 
     115      571875 :   ulong sibling_prev_idx = fd_funk_txn_idx( *_child_tail_cidx );
     116             : 
     117      571875 :   int first_born = fd_funk_txn_idx_is_null( sibling_prev_idx );
     118             : 
     119      571875 :   txn->parent_cidx       = fd_funk_txn_cidx( parent_idx           );
     120      571875 :   txn->child_head_cidx   = fd_funk_txn_cidx( FD_FUNK_TXN_IDX_NULL );
     121      571875 :   txn->child_tail_cidx   = fd_funk_txn_cidx( FD_FUNK_TXN_IDX_NULL );
     122      571875 :   txn->sibling_prev_cidx = fd_funk_txn_cidx( sibling_prev_idx     );
     123      571875 :   txn->sibling_next_cidx = fd_funk_txn_cidx( FD_FUNK_TXN_IDX_NULL );
     124      571875 :   txn->stack_cidx        = fd_funk_txn_cidx( FD_FUNK_TXN_IDX_NULL );
     125      571875 :   txn->tag               = 0UL;
     126             : 
     127      571875 :   fd_funk_txn_state_transition( txn, FD_FUNK_TXN_STATE_FREE, FD_FUNK_TXN_STATE_ACTIVE );
     128      571875 :   txn->rec_head_idx = FD_FUNK_REC_IDX_NULL;
     129      571875 :   txn->rec_tail_idx = FD_FUNK_REC_IDX_NULL;
     130             : 
     131             :   /* TODO: consider branchless impl */
     132      571875 :   if( FD_LIKELY( first_born ) ) *_child_head_cidx                = fd_funk_txn_cidx( txn_idx ); /* opt for non-compete */
     133      223980 :   else funk->txn_pool->ele[ sibling_prev_idx ].sibling_next_cidx = fd_funk_txn_cidx( txn_idx );
     134             : 
     135      571875 :   *_child_tail_cidx = fd_funk_txn_cidx( txn_idx );
     136             : 
     137      571875 :   if( parent_xid ) {
     138      571875 :     if( FD_UNLIKELY( fd_funk_txn_map_query_test( query )!=FD_MAP_SUCCESS ) ) {
     139           0 :       FD_LOG_CRIT(( "Detected data race while preparing a funk txn" ));
     140           0 :     }
     141      571875 :   }
     142             : 
     143      571875 :   fd_funk_txn_map_insert( funk->txn_map, txn, FD_MAP_FLAG_BLOCKING );
     144      571875 : }
     145             : 
     146             : int
     147         249 : fd_funk_txn_verify( fd_funk_t * funk ) {
     148         249 :   fd_funk_txn_map_t *  txn_map  = funk->txn_map;
     149         249 :   fd_funk_txn_pool_t * txn_pool = funk->txn_pool;
     150         249 :   ulong                txn_max  = fd_funk_txn_pool_ele_max( txn_pool );
     151             : 
     152         249 :   ulong funk_child_head_idx = fd_funk_txn_idx( funk->shmem->child_head_cidx ); /* Previously verified */
     153         249 :   ulong funk_child_tail_idx = fd_funk_txn_idx( funk->shmem->child_tail_cidx ); /* Previously verified */
     154             : 
     155         249 :   fd_funk_txn_xid_t const * last_publish = funk->shmem->last_publish; /* Previously verified */
     156             : 
     157        4434 : # define TEST(c) do {                                                                           \
     158        4434 :     if( FD_UNLIKELY( !(c) ) ) { FD_LOG_WARNING(( "FAIL: %s", #c )); return FD_FUNK_ERR_INVAL; } \
     159        4434 :   } while(0)
     160             : 
     161         249 : # define IS_VALID( idx ) ( (idx==FD_FUNK_TXN_IDX_NULL) || \
     162         249 :                            ((idx<txn_max) && (!fd_funk_txn_xid_eq( fd_funk_txn_xid( &txn_pool->ele[idx] ), last_publish ))) )
     163             : 
     164         249 :   TEST( !fd_funk_txn_map_verify( txn_map ) );
     165         249 :   TEST( !fd_funk_txn_pool_verify( txn_pool ) );
     166             : 
     167             :   /* Tag all transactions as not visited yet */
     168             : 
     169     1580073 :   for( ulong txn_idx=0UL; txn_idx<txn_max; txn_idx++ ) txn_pool->ele[ txn_idx ].tag = 0UL;
     170             : 
     171             :   /* Visit all transactions in preparation, traversing from oldest to
     172             :      youngest. */
     173             : 
     174         249 :   do {
     175             : 
     176             :     /* Push all children of funk to the stack */
     177             : 
     178         249 :     ulong stack_idx = FD_FUNK_TXN_IDX_NULL;
     179         249 :     ulong child_idx = funk_child_head_idx;
     180         540 :     while( !fd_funk_txn_idx_is_null( child_idx ) ) {
     181             : 
     182             :       /* Make sure valid idx, not tagged (detects cycles) and child
     183             :          knows it is a child of funk.  Then tag as visited / in-prep,
     184             :          push to stack and update prep_cnt */
     185             : 
     186         291 :       TEST( IS_VALID( child_idx ) );
     187         291 :       TEST( !txn_pool->ele[ child_idx ].tag );
     188         291 :       TEST( fd_funk_txn_idx_is_null( fd_funk_txn_idx( txn_pool->ele[ child_idx ].parent_cidx ) ) );
     189         291 :       txn_pool->ele[ child_idx ].tag        = 1UL;
     190         291 :       txn_pool->ele[ child_idx ].stack_cidx = fd_funk_txn_cidx( stack_idx );
     191         291 :       stack_idx                   = child_idx;
     192             : 
     193         291 :       ulong next_idx = fd_funk_txn_idx( txn_pool->ele[ child_idx ].sibling_next_cidx );
     194         291 :       if( !fd_funk_txn_idx_is_null( next_idx ) ) TEST( fd_funk_txn_idx( txn_pool->ele[ next_idx ].sibling_prev_cidx )==child_idx );
     195         291 :       child_idx = next_idx;
     196         291 :     }
     197             : 
     198         840 :     while( !fd_funk_txn_idx_is_null( stack_idx ) ) {
     199             : 
     200             :       /* Pop the next transaction to traverse */
     201             : 
     202         591 :       ulong txn_idx = stack_idx;
     203         591 :       stack_idx = fd_funk_txn_idx( txn_pool->ele[ txn_idx ].stack_cidx );
     204             : 
     205             :       /* Push all children of txn to the stack */
     206             : 
     207         591 :       ulong child_idx = fd_funk_txn_idx( txn_pool->ele[ txn_idx ].child_head_cidx );
     208         891 :       while( !fd_funk_txn_idx_is_null( child_idx ) ) {
     209             : 
     210             :         /* Make sure valid idx, not tagged (detects cycles) and child
     211             :            knows it is a child of txn_idx.  Then tag as visited /
     212             :            in-prep, push to stack and update prep_cnt */
     213             : 
     214         300 :         TEST( IS_VALID( child_idx ) );
     215         300 :         TEST( !txn_pool->ele[ child_idx ].tag );
     216         300 :         TEST( fd_funk_txn_idx( txn_pool->ele[ child_idx ].parent_cidx )==txn_idx );
     217         300 :         txn_pool->ele[ child_idx ].tag        = 1UL;
     218         300 :         txn_pool->ele[ child_idx ].stack_cidx = fd_funk_txn_cidx( stack_idx );
     219         300 :         stack_idx                   = child_idx;
     220             : 
     221         300 :         ulong next_idx = fd_funk_txn_idx( txn_pool->ele[ child_idx ].sibling_next_cidx );
     222         300 :         if( !fd_funk_txn_idx_is_null( next_idx ) ) TEST( fd_funk_txn_idx( txn_pool->ele[ next_idx ].sibling_prev_cidx )==child_idx );
     223         300 :         child_idx = next_idx;
     224         300 :       }
     225         591 :     }
     226             : 
     227         249 :   } while(0);
     228             : 
     229             :   /* Do it again with a youngest to oldest traversal to test reverse
     230             :      link integrity */
     231             : 
     232         249 :   do {
     233             : 
     234             :     /* Push all children of funk to the stack */
     235             : 
     236         249 :     ulong stack_idx = FD_FUNK_TXN_IDX_NULL;
     237         249 :     ulong child_idx = funk_child_tail_idx;
     238         540 :     while( !fd_funk_txn_idx_is_null( child_idx ) ) {
     239             : 
     240             :       /* Make sure valid idx, tagged as visited above (detects cycles)
     241             :          and child knows it is a child of funk.  Then tag as visited /
     242             :          in-prep, push to stack and update prep_cnt */
     243             : 
     244         291 :       TEST( IS_VALID( child_idx ) );
     245         291 :       TEST( txn_pool->ele[ child_idx ].tag==1UL );
     246         291 :       TEST( fd_funk_txn_idx_is_null( fd_funk_txn_idx( txn_pool->ele[ child_idx ].parent_cidx ) ) );
     247         291 :       txn_pool->ele[ child_idx ].tag        = 2UL;
     248         291 :       txn_pool->ele[ child_idx ].stack_cidx = fd_funk_txn_cidx( stack_idx );
     249         291 :       stack_idx                             = child_idx;
     250             : 
     251         291 :       ulong prev_idx = fd_funk_txn_idx( txn_pool->ele[ child_idx ].sibling_prev_cidx );
     252         291 :       if( !fd_funk_txn_idx_is_null( prev_idx ) ) TEST( fd_funk_txn_idx( txn_pool->ele[ prev_idx ].sibling_next_cidx )==child_idx );
     253         291 :       child_idx = prev_idx;
     254         291 :     }
     255             : 
     256         840 :     while( !fd_funk_txn_idx_is_null( stack_idx ) ) {
     257             : 
     258             :       /* Pop the next transaction to traverse */
     259             : 
     260         591 :       ulong txn_idx = stack_idx;
     261         591 :       stack_idx = fd_funk_txn_idx( txn_pool->ele[ txn_idx ].stack_cidx );
     262             : 
     263             :       /* Push all children of txn to the stack */
     264             : 
     265         591 :       ulong child_idx = fd_funk_txn_idx( txn_pool->ele[ txn_idx ].child_tail_cidx );
     266         891 :       while( !fd_funk_txn_idx_is_null( child_idx ) ) {
     267             : 
     268             :         /* Make sure valid idx, tagged as visited above (detects cycles)
     269             :            and child knows it is a child of txn_idx.  Then, tag as
     270             :            visited / in-prep, push to stack and update prep_cnt */
     271             : 
     272         300 :         TEST( IS_VALID( child_idx ) );
     273         300 :         TEST( txn_pool->ele[ child_idx ].tag==1UL );
     274         300 :         TEST( fd_funk_txn_idx( txn_pool->ele[ child_idx ].parent_cidx )==txn_idx );
     275         300 :         txn_pool->ele[ child_idx ].tag        = 2UL;
     276         300 :         txn_pool->ele[ child_idx ].stack_cidx = fd_funk_txn_cidx( stack_idx );
     277         300 :         stack_idx                             = child_idx;
     278             : 
     279         300 :         ulong prev_idx = fd_funk_txn_idx( txn_pool->ele[ child_idx ].sibling_prev_cidx );
     280         300 :         if( !fd_funk_txn_idx_is_null( prev_idx ) ) TEST( fd_funk_txn_idx( txn_pool->ele[ prev_idx ].sibling_next_cidx )==child_idx );
     281         300 :         child_idx = prev_idx;
     282         300 :       }
     283         591 :     }
     284         249 :   } while(0);
     285             : 
     286         249 : # undef IS_VALID
     287         249 : # undef TEST
     288             : 
     289         249 :   return FD_FUNK_SUCCESS;
     290         249 : }
 |