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 612711 : #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 : 60 : typedef struct fd_funk_txn_private fd_funk_txn_t; 61 : 62 : /* fd_funk_txn_map allows for indexing transactions by their xid */ 63 : 64 : #define POOL_NAME fd_funk_txn_pool 65 0 : #define POOL_ELE_T fd_funk_txn_t 66 : #define POOL_IDX_T uint 67 : #define POOL_NEXT map_next 68 : #define POOL_IMPL_STYLE 1 69 : #include "../util/tmpl/fd_pool_para.c" 70 : 71 : #define MAP_NAME fd_funk_txn_map 72 0 : #define MAP_ELE_T fd_funk_txn_t 73 : #define MAP_KEY_T fd_funk_txn_xid_t 74 : #define MAP_KEY xid 75 83822 : #define MAP_KEY_EQ(k0,k1) fd_funk_txn_xid_eq((k0),(k1)) 76 193939 : #define MAP_KEY_HASH(k0,seed) fd_funk_txn_xid_hash((k0),(seed)) 77 0 : #define MAP_NEXT map_next 78 : #define MAP_MAGIC (0xf173da2ce7172db0UL) /* Firedancer txn db version 0 */ 79 : #define MAP_IMPL_STYLE 1 80 : #include "../util/tmpl/fd_map_chain_para.c" 81 : #undef MAP_HASH 82 : 83 : /* Funk transaction states */ 84 : 85 110296 : #define FD_FUNK_TXN_STATE_FREE (0U) 86 135031 : #define FD_FUNK_TXN_STATE_ACTIVE (1U) 87 0 : #define FD_FUNK_TXN_STATE_CANCEL (2U) 88 0 : #define FD_FUNK_TXN_STATE_PUBLISH (3U) 89 : 90 : FD_PROTOTYPES_BEGIN 91 : 92 : /* fd_funk_txn_{cidx,idx} convert between an index and a compressed index. */ 93 : 94 440824 : static inline uint fd_funk_txn_cidx( ulong idx ) { return (uint) idx; } 95 328124 : static inline ulong fd_funk_txn_idx ( uint cidx ) { return (ulong)cidx; } 96 : 97 : /* fd_funk_txn_idx_is_null returns 1 if idx is FD_FUNK_TXN_IDX_NULL and 98 : 0 otherwise. */ 99 : 100 331942 : static inline int fd_funk_txn_idx_is_null( ulong idx ) { return idx==FD_FUNK_TXN_IDX_NULL; } 101 : 102 : /* Accessors */ 103 : 104 : /* fd_funk_txn_xid returns a pointer in the local address space of the 105 : ID of an in-preparation transaction. Assumes txn points to an 106 : in-preparation transaction in the caller's address space. The 107 : lifetime of the returned pointer is the same as the txn's pointer 108 : lifetime. The value at the pointer will be stable for the lifetime 109 : of the returned pointer. */ 110 : 111 0 : FD_FN_CONST static inline fd_funk_txn_xid_t const * fd_funk_txn_xid( fd_funk_txn_t const * txn ) { return &txn->xid; } 112 : 113 : /* fd_funk_txn_{parent,child_head,child_tail,sibling_prev,sibling_next} 114 : return a pointer in the caller's address space to the corresponding 115 : relative in-preparation transaction of in-preparation transaction 116 : txn. 117 : 118 : Specifically: 119 : 120 : - parent is the parent transaction. NULL if txn is a child of funk. 121 : - child_head is txn's oldest child. NULL if txn has no children. 122 : - child_tail is txn's youngest child. NULL if txn has no children. 123 : - sibling_prev is txn's closest older sibling. NULL if txn is the 124 : oldest sibling. 125 : - sibling_next is txn's closest younger sibling. NULL if txn is the 126 : youngest sibling. 127 : 128 : E.g. child_head==NULL indicates txn has no children. 129 : child_head!=NULL and child_head==child_tail indicates txn has one 130 : child. child_head!=NULL and child_tail!=NULL and 131 : child_head!=child_tail indicates txn has many children. 132 : sibling_prev==sibling_next==NULL indicate no siblings / locally 133 : competing transactions to txn. If the txn and all its ancestors have 134 : no siblings, there are no transaction histories competing with txn 135 : globally. */ 136 : 137 : #define FD_FUNK_ACCESSOR(field) \ 138 : FD_FN_PURE static inline fd_funk_txn_t * \ 139 : fd_funk_txn_##field( fd_funk_txn_t const * txn, \ 140 0 : fd_funk_txn_pool_t const * pool ) { \ 141 0 : ulong idx = fd_funk_txn_idx( txn->field##_cidx ); \ 142 0 : if( idx==FD_FUNK_TXN_IDX_NULL ) return NULL; \ 143 0 : return pool->ele + idx; \ 144 0 : } 145 : 146 : FD_FUNK_ACCESSOR( parent ) 147 : FD_FUNK_ACCESSOR( child_head ) 148 : FD_FUNK_ACCESSOR( child_tail ) 149 : FD_FUNK_ACCESSOR( sibling_prev ) 150 : FD_FUNK_ACCESSOR( sibling_next ) 151 : 152 : #undef FD_FUNK_ACCESSOR 153 : 154 : /* fd_funk_txn_frozen returns 1 if the in-preparation transaction is 155 : frozen (i.e. has children) and 0 otherwise (i.e. has no children). 156 : Assumes txn points to an in-preparation transaction in the caller's 157 : address space. */ 158 : 159 : FD_FN_PURE static inline int 160 128812 : fd_funk_txn_is_frozen( fd_funk_txn_t const * txn ) { 161 128812 : return !fd_funk_txn_idx_is_null( fd_funk_txn_idx( txn->child_head_cidx ) ); 162 128812 : } 163 : 164 : typedef struct fd_funk_rec fd_funk_rec_t; 165 : 166 : /* Operations */ 167 : /* fd_funk_txn_prepare starts preparation of a transaction. The 168 : transaction will be a child of the in-preparation transaction pointed 169 : to by parent_xid. parent_xid must be non-NULL. To create a child of 170 : funk itself, pass the xid of the current last published transaction 171 : (i.e. fd_funk_last_publish( funk )) as parent_xid. xid points to the 172 : transaction id that should be used for the transaction. This id must 173 : be unique over all in-preparation transactions, the root transaction 174 : and the last published transaction. It is strongly recommended to 175 : use globally unique ids when possible. 176 : 177 : At start of preparation, the records in the txn are a virtual clone of the 178 : records in its parent transaction. The funk records can be modified 179 : when the funk has no children. Similarly, the records of an 180 : in-preparation transaction can be freely modified when it has 181 : no children. 182 : 183 : Assumes funk is a current local join. Requires funk, parent_xid and 184 : xid are non-NULL. parent_xid must be either the current last 185 : published transaction xid or the xid of an in-preparation transaction. 186 : Reasons for failure include the funk's transaction map is full, the 187 : requested xid is in use (i.e. the last published or matches another 188 : in-preparation transaction), or parent_xid is invalid. 189 : 190 : This is a reasonably fast O(1) time (theoretical minimum), reasonably 191 : small O(1) space (theoretical minimum), does no allocation, does no 192 : system calls, and produces no garbage to collect (at this layer at 193 : least). That is, we can scalably track forks until we run out of 194 : resources allocated to the funk. */ 195 : 196 : void 197 : fd_funk_txn_prepare( fd_funk_t * funk, 198 : fd_funk_txn_xid_t const * parent_xid, 199 : fd_funk_txn_xid_t const * xid ); 200 : 201 : /* Misc */ 202 : 203 : /* fd_funk_txn_verify verifies a transaction map. Returns 204 : FD_FUNK_SUCCESS if the transaction map appears intact and 205 : FD_FUNK_ERR_INVAL if not (logs details). Meant to be called as part 206 : of fd_funk_verify. */ 207 : 208 : int 209 : fd_funk_txn_verify( fd_funk_t * funk ); 210 : 211 : FD_FN_UNUSED static char const * 212 110200 : fd_funk_txn_state_str( uint state ) { 213 110200 : switch( state ) { 214 55100 : case FD_FUNK_TXN_STATE_FREE: return "free"; 215 55100 : case FD_FUNK_TXN_STATE_ACTIVE: return "alive"; 216 0 : case FD_FUNK_TXN_STATE_CANCEL: return "cancel"; 217 0 : case FD_FUNK_TXN_STATE_PUBLISH: return "publish"; 218 0 : default: return "unknown"; 219 110200 : } 220 110200 : } 221 : 222 : #ifndef __cplusplus 223 : 224 : FD_FN_UNUSED static void 225 : fd_funk_txn_state_assert( fd_funk_txn_t const * txn, 226 79938 : uint want ) { 227 79938 : uint have = FD_VOLATILE_CONST( txn->state ); 228 79938 : if( FD_UNLIKELY( want!=have ) ) { 229 0 : FD_LOG_CRIT(( "Invariant violation detected on funk txn: expected state %u-%s, found state %u-%s", 230 0 : want, fd_funk_txn_state_str( want ), 231 0 : have, fd_funk_txn_state_str( have ) )); 232 0 : } 233 79938 : } 234 : 235 : FD_FN_UNUSED static void 236 : fd_funk_txn_xid_assert( fd_funk_txn_t const * txn, 237 0 : fd_funk_txn_xid_t const * xid ) { 238 0 : uint found_state = FD_VOLATILE_CONST( txn->state ); 239 0 : fd_funk_txn_xid_t found_xid = FD_VOLATILE_CONST( txn->xid ); 240 0 : int xid_ok = fd_funk_txn_xid_eq( &found_xid, xid ); 241 0 : int state_ok = found_state==FD_FUNK_TXN_STATE_ACTIVE; 242 0 : if( FD_UNLIKELY( !xid_ok || !state_ok ) ) { 243 0 : if( !xid_ok ) { 244 0 : FD_LOG_CRIT(( "Data race detected: funk txn %p %lu:%lu use-after-free", 245 0 : (void *)txn, 246 0 : xid->ul[0], xid->ul[1] )); 247 0 : } else { 248 0 : FD_LOG_CRIT(( "Data race detected: funk txn %p %lu:%lu in invalid state %u-%s", 249 0 : (void *)txn, 250 0 : xid->ul[0], xid->ul[1], 251 0 : found_state, fd_funk_txn_state_str( found_state ) )); 252 0 : } 253 0 : } 254 0 : } 255 : 256 : #endif /* !__cplusplus */ 257 : 258 : FD_PROTOTYPES_END 259 : 260 : #endif /* HEADER_fd_src_funk_fd_funk_txn_h */
