LCOV - code coverage report
Current view: top level - funk - fd_funk_txn.h (source / functions) Hit Total Coverage
Test: cov.lcov Lines: 48 66 72.7 %
Date: 2025-10-24 04:32:27 Functions: 32 2072 1.5 %

          Line data    Source code
       1             : #ifndef HEADER_fd_src_funk_fd_funk_txn_h
       2             : #define HEADER_fd_src_funk_fd_funk_txn_h
       3             : 
       4             : /* This provides APIs for managing forks (preparing, publishing and
       5             :    cancelling funk transactions).  It is generally not meant to be
       6             :    included directly.  Use fd_funk.h instead.
       7             : 
       8             :    Funk transaction-level operations are not thread-safe.  External
       9             :    synchronization (e.g. mutex) is required when doing txn operations
      10             :    when other txn or rec operations may be concurrently running on other
      11             :    threads. */
      12             : 
      13             : #include "fd_funk_base.h"
      14             : #include "../flamenco/fd_rwlock.h"
      15             : 
      16             : /* FD_FUNK_TXN_{ALIGN,FOOTPRINT} describe the alignment and footprint of
      17             :    a fd_funk_txn_t.  ALIGN will be a power of 2, footprint will be a
      18             :    multiple of align.  These are provided to facilitate compile time
      19             :    declarations. */
      20             : 
      21             : #define FD_FUNK_TXN_ALIGN     (32UL)
      22             : #define FD_FUNK_TXN_FOOTPRINT (96UL)
      23             : 
      24             : /* FD_FUNK_TXN_IDX_NULL gives the map transaction idx value used to
      25             :    represent NULL.  It also is the maximum value for txn_max in a funk
      26             :    to support index compression.  (E.g. could use ushort / USHORT_MAX
      27             :    to use more aggressive compression or ulong / ULONG_MAX to disable
      28             :    index compression.) */
      29             : 
      30     6989763 : #define FD_FUNK_TXN_IDX_NULL ((ulong)UINT_MAX)
      31             : 
      32             : /* A fd_funk_txn_t is an opaque handle of an in-preparation funk
      33             :    transaction.  The details are exposed here to facilitate inlining
      34             :    various operations. */
      35             : 
      36             : struct __attribute__((aligned(FD_FUNK_TXN_ALIGN))) fd_funk_txn_private {
      37             : 
      38             :   /* These fields are managed by the funk's txn_map */
      39             : 
      40             :   fd_funk_txn_xid_t xid;      /* Transaction id, at a minimum, unique among all in-prepare and the last published transaction,
      41             :                                  ideally globally unique */
      42             :   ulong             map_next; /* Internal use by map */
      43             : 
      44             :   /* These fields are managed by the funk */
      45             : 
      46             :   uint   parent_cidx;       /* compr map index of the in-prep parent         txn, compr FD_FUNK_TXN_IDX_NULL if a funk child */
      47             :   uint   child_head_cidx;   /* "                              oldest   child      "                             childless */
      48             :   uint   child_tail_cidx;   /* "                              youngest child                                    childless */
      49             :   uint   sibling_prev_cidx; /* "                              older sibling                                     oldest sibling */
      50             :   uint   sibling_next_cidx; /* "                              younger sibling                                   youngest sibling */
      51             :   uint   stack_cidx;        /* Internal use by funk */
      52             :   ulong  tag;               /* Internal use by funk */
      53             : 
      54             :   uint  rec_head_idx;       /* Record map index of the first record, FD_FUNK_REC_IDX_NULL if none (from oldest to youngest) */
      55             :   uint  rec_tail_idx;       /* "                       last          " */
      56             : 
      57             :   uint  state;              /* one of FD_FUNK_TXN_STATE_* */
      58             : 
      59             :   fd_rwlock_t lock[1];
      60             : };
      61             : 
      62             : typedef struct fd_funk_txn_private fd_funk_txn_t;
      63             : 
      64             : /* fd_funk_txn_map allows for indexing transactions by their xid */
      65             : 
      66             : #define POOL_NAME          fd_funk_txn_pool
      67           6 : #define POOL_ELE_T         fd_funk_txn_t
      68             : #define POOL_IDX_T         uint
      69             : #define POOL_NEXT          map_next
      70             : #define POOL_IMPL_STYLE    1
      71             : #include "../util/tmpl/fd_pool_para.c"
      72             : 
      73             : #define MAP_NAME              fd_funk_txn_map
      74        1092 : #define MAP_ELE_T             fd_funk_txn_t
      75             : #define MAP_KEY_T             fd_funk_txn_xid_t
      76             : #define MAP_KEY               xid
      77     1676715 : #define MAP_KEY_EQ(k0,k1)     fd_funk_txn_xid_eq((k0),(k1))
      78     2267880 : #define MAP_KEY_HASH(k0,seed) fd_funk_txn_xid_hash((k0),(seed))
      79        1092 : #define MAP_NEXT              map_next
      80             : #define MAP_MAGIC             (0xf173da2ce7172db0UL) /* Firedancer txn db version 0 */
      81             : #define MAP_IMPL_STYLE        1
      82             : #include "../util/tmpl/fd_map_chain_para.c"
      83             : #undef  MAP_HASH
      84             : 
      85             : /* Funk transaction states */
      86             : 
      87     2724384 : #define FD_FUNK_TXN_STATE_FREE    (0U)
      88      895512 : #define FD_FUNK_TXN_STATE_ACTIVE  (1U)
      89      348846 : #define FD_FUNK_TXN_STATE_CANCEL  (2U)
      90      224583 : #define FD_FUNK_TXN_STATE_PUBLISH (3U)
      91             : 
      92             : FD_PROTOTYPES_BEGIN
      93             : 
      94             : /* fd_funk_txn_{cidx,idx} convert between an index and a compressed index. */
      95             : 
      96     5084592 : static inline uint  fd_funk_txn_cidx( ulong idx  ) { return (uint)  idx; }
      97     3765099 : static inline ulong fd_funk_txn_idx ( uint  cidx ) { return (ulong)cidx; }
      98             : 
      99             : /* fd_funk_txn_idx_is_null returns 1 if idx is FD_FUNK_TXN_IDX_NULL and
     100             :    0 otherwise. */
     101             : 
     102     4292196 : static inline int fd_funk_txn_idx_is_null( ulong idx ) { return idx==FD_FUNK_TXN_IDX_NULL; }
     103             : 
     104             : /* Accessors */
     105             : 
     106             : /* fd_funk_txn_query returns a pointer to an in-preparation transaction
     107             :    whose id is pointed to by xid.  Returns NULL if xid is not an
     108             :    in-preparation transaction.  Assumes funk is a current local join,
     109             :    map==fd_funk_txn_map( funk, fd_funk_wksp( funk ) ), xid points to a
     110             :    transaction id in the caller's address space and there are no
     111             :    concurrent operations on funk or xid.  Retains no interest in xid.
     112             : 
     113             :    The returned pointer is in the caller's address space and, if the
     114             :    return is non-NULL, the lifetime of the returned pointer is the
     115             :    lesser of the funk join or the transaction is published or canceled
     116             :    (either directly or indirectly via publish of a descendant, publish
     117             :    of a competing transaction history or cancel of an ancestor). */
     118             : 
     119             : FD_FN_PURE static inline fd_funk_txn_t *
     120             : fd_funk_txn_query( fd_funk_txn_xid_t const * xid,
     121      224787 :                    fd_funk_txn_map_t *       map ) {
     122      224787 :   do {
     123      224787 :     fd_funk_txn_map_query_t query[1];
     124      224787 :     if( FD_UNLIKELY( fd_funk_txn_map_query_try( map, xid, NULL, query, 0 ) ) ) return NULL;
     125      224787 :     fd_funk_txn_t * ele = fd_funk_txn_map_query_ele( query );
     126      224787 :     if( FD_LIKELY( !fd_funk_txn_map_query_test( query ) ) ) return ele;
     127      224787 :   } while( 1 );
     128      224787 : }
     129             : 
     130             : /* fd_funk_txn_xid returns a pointer in the local address space of the
     131             :    ID of an in-preparation transaction.  Assumes txn points to an
     132             :    in-preparation transaction in the caller's address space.  The
     133             :    lifetime of the returned pointer is the same as the txn's pointer
     134             :    lifetime.  The value at the pointer will be stable for the lifetime
     135             :    of the returned pointer. */
     136             : 
     137      225675 : FD_FN_CONST static inline fd_funk_txn_xid_t const * fd_funk_txn_xid( fd_funk_txn_t const * txn ) { return &txn->xid; }
     138             : 
     139             : /* fd_funk_txn_{parent,child_head,child_tail,sibling_prev,sibling_next}
     140             :    return a pointer in the caller's address space to the corresponding
     141             :    relative in-preparation transaction of in-preparation transaction
     142             :    txn.
     143             : 
     144             :    Specifically:
     145             : 
     146             :    - parent is the parent transaction.  NULL if txn is a child of funk.
     147             :    - child_head is txn's oldest child.  NULL if txn has no children.
     148             :    - child_tail is txn's youngest child.  NULL if txn has no children.
     149             :    - sibling_prev is txn's closest older sibling.  NULL if txn is the
     150             :      oldest sibling.
     151             :    - sibling_next is txn's closest younger sibling.  NULL if txn is the
     152             :      youngest sibling.
     153             : 
     154             :    E.g. child_head==NULL indicates txn has no children.
     155             :    child_head!=NULL and child_head==child_tail indicates txn has one
     156             :    child.  child_head!=NULL and child_tail!=NULL and
     157             :    child_head!=child_tail indicates txn has many children.
     158             :    sibling_prev==sibling_next==NULL indicate no siblings / locally
     159             :    competing transactions to txn.  If the txn and all its ancestors have
     160             :    no siblings, there are no transaction histories competing with txn
     161             :    globally. */
     162             : 
     163             : #define FD_FUNK_ACCESSOR(field)                          \
     164             : FD_FN_PURE static inline fd_funk_txn_t *                 \
     165             : fd_funk_txn_##field( fd_funk_txn_t const *      txn,     \
     166          18 :                      fd_funk_txn_pool_t const * pool ) { \
     167          18 :   ulong idx = fd_funk_txn_idx( txn->field##_cidx );      \
     168          18 :   if( idx==FD_FUNK_TXN_IDX_NULL ) return NULL;           \
     169          18 :   return pool->ele + idx;                                \
     170          18 : }
     171             : 
     172          18 : FD_FUNK_ACCESSOR( parent       )
     173             : FD_FUNK_ACCESSOR( child_head   )
     174             : FD_FUNK_ACCESSOR( child_tail   )
     175             : FD_FUNK_ACCESSOR( sibling_prev )
     176             : FD_FUNK_ACCESSOR( sibling_next )
     177             : 
     178             : #undef FD_FUNK_ACCESSOR
     179             : 
     180             : /* fd_funk_txn_frozen returns 1 if the in-preparation transaction is
     181             :    frozen (i.e. has children) and 0 otherwise (i.e. has no children).
     182             :    Assumes txn points to an in-preparation transaction in the caller's
     183             :    address space. */
     184             : 
     185             : FD_FN_PURE static inline int
     186         507 : fd_funk_txn_is_frozen( fd_funk_txn_t const * txn ) {
     187         507 :   return !fd_funk_txn_idx_is_null( fd_funk_txn_idx( txn->child_head_cidx ) );
     188         507 : }
     189             : 
     190             : typedef struct fd_funk_rec fd_funk_rec_t;
     191             : 
     192             : /* Operations */
     193             : /* fd_funk_txn_prepare starts preparation of a transaction.  The
     194             :    transaction will be a child of the in-preparation transaction pointed
     195             :    to by parent.  A NULL parent means the transaction should be a child
     196             :    of funk.  xid points to transaction id that should be used for the
     197             :    transaction.  This id must be unique over all in-preparation
     198             :    transactions, the root transaction and the last published
     199             :    transaction.  It is strongly recommended to use globally unique ids
     200             :    when possible.  Returns a pointer in the caller's address space to
     201             :    the in-preparation transaction on success and NULL on failure.  The
     202             :    lifetime of the returned pointer is as described in
     203             :    fd_funk_txn_query.
     204             : 
     205             :    At start of preparation, the records in the txn are a virtual clone of the
     206             :    records in its parent transaction.  The funk records can be modified
     207             :    when the funk has no children.  Similarly, the records of an
     208             :    in-preparation transaction can be freely modified when it has
     209             :    no children.
     210             : 
     211             :    Assumes funk is a current local join.  Reasons for failure include
     212             :    funk is NULL, the funk's transaction map is full, the parent is
     213             :    neither NULL nor points to an in-preparation funk transaction, xid is
     214             :    NULL, the requested xid is in use (i.e. the last published or matches
     215             :    another in-preparation transaction).
     216             : 
     217             :    This is a reasonably fast O(1) time (theoretical minimum), reasonably
     218             :    small O(1) space (theoretical minimum), does no allocation, does no
     219             :    system calls, and produces no garbage to collect (at this layer at
     220             :    least).  That is, we can scalably track forks until we run out of
     221             :    resources allocated to the funk. */
     222             : 
     223             : void
     224             : fd_funk_txn_prepare( fd_funk_t *               funk,
     225             :                      fd_funk_txn_xid_t const * parent,
     226             :                      fd_funk_txn_xid_t const * xid );
     227             : 
     228             : /* Misc */
     229             : 
     230             : /* fd_funk_txn_verify verifies a transaction map.  Returns
     231             :    FD_FUNK_SUCCESS if the transaction map appears intact and
     232             :    FD_FUNK_ERR_INVAL if not (logs details).  Meant to be called as part
     233             :    of fd_funk_verify. */
     234             : 
     235             : int
     236             : fd_funk_txn_verify( fd_funk_t * funk );
     237             : 
     238             : FD_FN_UNUSED static char const *
     239     1146912 : fd_funk_txn_state_str( uint state ) {
     240     1146912 :   switch( state ) {
     241      573456 :   case FD_FUNK_TXN_STATE_FREE:    return "free";
     242      573456 :   case FD_FUNK_TXN_STATE_ACTIVE:  return "alive";
     243           0 :   case FD_FUNK_TXN_STATE_CANCEL:  return "cancel";
     244           0 :   case FD_FUNK_TXN_STATE_PUBLISH: return "publish";
     245           0 :   default:                        return "unknown";
     246     1146912 :   }
     247     1146912 : }
     248             : 
     249             : #ifndef __cplusplus
     250             : 
     251             : FD_FN_UNUSED static void
     252             : fd_funk_txn_state_assert( fd_funk_txn_t const * txn,
     253      317868 :                           uint                  want ) {
     254      317868 :   uint have = FD_VOLATILE_CONST( txn->state );
     255      317868 :   if( FD_UNLIKELY( want!=have ) ) {
     256           0 :     FD_LOG_CRIT(( "Invariant violation detected on funk txn: expected state %u-%s, found state %u-%s",
     257           0 :                   want, fd_funk_txn_state_str( want ),
     258           0 :                   have, fd_funk_txn_state_str( have ) ));
     259           0 :   }
     260      317868 : }
     261             : 
     262             : FD_FN_UNUSED static void
     263             : fd_funk_txn_xid_assert( fd_funk_txn_t const *     txn,
     264        4188 :                         fd_funk_txn_xid_t const * xid ) {
     265        4188 :   uint              found_state = FD_VOLATILE_CONST( txn->state );
     266        4188 :   fd_funk_txn_xid_t found_xid   = FD_VOLATILE_CONST( txn->xid   );
     267        4188 :   int               xid_ok      = fd_funk_txn_xid_eq( &found_xid, xid );
     268        4188 :   int               state_ok    = found_state==FD_FUNK_TXN_STATE_ACTIVE;
     269        4188 :   if( FD_UNLIKELY( !xid_ok || !state_ok ) ) {
     270           0 :     if( !xid_ok ) {
     271           0 :       FD_LOG_CRIT(( "Data race detected: funk txn %p %lu:%lu use-after-free",
     272           0 :                     (void *)txn,
     273           0 :                     xid->ul[0], xid->ul[1] ));
     274           0 :     } else {
     275           0 :       FD_LOG_CRIT(( "Data race detected: funk txn %p %lu:%lu in invalid state %u-%s",
     276           0 :                     (void *)txn,
     277           0 :                     xid->ul[0], xid->ul[1],
     278           0 :                     found_state, fd_funk_txn_state_str( found_state ) ));
     279           0 :     }
     280           0 :   }
     281        4188 : }
     282             : 
     283             : #endif /* !__cplusplus */
     284             : 
     285             : FD_PROTOTYPES_END
     286             : 
     287             : #endif /* HEADER_fd_src_funk_fd_funk_txn_h */

Generated by: LCOV version 1.14