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 8257503 : #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 1182 : #define MAP_ELE_T fd_funk_txn_t 75 : #define MAP_KEY_T fd_funk_txn_xid_t 76 : #define MAP_KEY xid 77 3128118 : #define MAP_KEY_EQ(k0,k1) fd_funk_txn_xid_eq((k0),(k1)) 78 3537468 : #define MAP_KEY_HASH(k0,seed) fd_funk_txn_xid_hash((k0),(seed)) 79 1182 : #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 1932918 : #define FD_FUNK_TXN_STATE_FREE (0U) 88 889500 : #define FD_FUNK_TXN_STATE_ACTIVE (1U) 89 347205 : #define FD_FUNK_TXN_STATE_CANCEL (2U) 90 224775 : #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 5072640 : static inline uint fd_funk_txn_cidx( ulong idx ) { return (uint) idx; } 97 5040423 : 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 5565693 : 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_xid returns a pointer in the local address space of the 107 : ID of an in-preparation transaction. Assumes txn points to an 108 : in-preparation transaction in the caller's address space. The 109 : lifetime of the returned pointer is the same as the txn's pointer 110 : lifetime. The value at the pointer will be stable for the lifetime 111 : of the returned pointer. */ 112 : 113 225957 : FD_FN_CONST static inline fd_funk_txn_xid_t const * fd_funk_txn_xid( fd_funk_txn_t const * txn ) { return &txn->xid; } 114 : 115 : /* fd_funk_txn_{parent,child_head,child_tail,sibling_prev,sibling_next} 116 : return a pointer in the caller's address space to the corresponding 117 : relative in-preparation transaction of in-preparation transaction 118 : txn. 119 : 120 : Specifically: 121 : 122 : - parent is the parent transaction. NULL if txn is a child of funk. 123 : - child_head is txn's oldest child. NULL if txn has no children. 124 : - child_tail is txn's youngest child. NULL if txn has no children. 125 : - sibling_prev is txn's closest older sibling. NULL if txn is the 126 : oldest sibling. 127 : - sibling_next is txn's closest younger sibling. NULL if txn is the 128 : youngest sibling. 129 : 130 : E.g. child_head==NULL indicates txn has no children. 131 : child_head!=NULL and child_head==child_tail indicates txn has one 132 : child. child_head!=NULL and child_tail!=NULL and 133 : child_head!=child_tail indicates txn has many children. 134 : sibling_prev==sibling_next==NULL indicate no siblings / locally 135 : competing transactions to txn. If the txn and all its ancestors have 136 : no siblings, there are no transaction histories competing with txn 137 : globally. */ 138 : 139 : #define FD_FUNK_ACCESSOR(field) \ 140 : FD_FN_PURE static inline fd_funk_txn_t * \ 141 : fd_funk_txn_##field( fd_funk_txn_t const * txn, \ 142 0 : fd_funk_txn_pool_t const * pool ) { \ 143 0 : ulong idx = fd_funk_txn_idx( txn->field##_cidx ); \ 144 0 : if( idx==FD_FUNK_TXN_IDX_NULL ) return NULL; \ 145 0 : return pool->ele + idx; \ 146 0 : } 147 : 148 : FD_FUNK_ACCESSOR( parent ) 149 : FD_FUNK_ACCESSOR( child_head ) 150 : FD_FUNK_ACCESSOR( child_tail ) 151 : FD_FUNK_ACCESSOR( sibling_prev ) 152 : FD_FUNK_ACCESSOR( sibling_next ) 153 : 154 : #undef FD_FUNK_ACCESSOR 155 : 156 : /* fd_funk_txn_frozen returns 1 if the in-preparation transaction is 157 : frozen (i.e. has children) and 0 otherwise (i.e. has no children). 158 : Assumes txn points to an in-preparation transaction in the caller's 159 : address space. */ 160 : 161 : FD_FN_PURE static inline int 162 1284366 : fd_funk_txn_is_frozen( fd_funk_txn_t const * txn ) { 163 1284366 : return !fd_funk_txn_idx_is_null( fd_funk_txn_idx( txn->child_head_cidx ) ); 164 1284366 : } 165 : 166 : typedef struct fd_funk_rec fd_funk_rec_t; 167 : 168 : /* Operations */ 169 : /* fd_funk_txn_prepare starts preparation of a transaction. The 170 : transaction will be a child of the in-preparation transaction pointed 171 : to by parent. A NULL parent means the transaction should be a child 172 : of funk. xid points to transaction id that should be used for the 173 : transaction. This id must be unique over all in-preparation 174 : transactions, the root transaction and the last published 175 : transaction. It is strongly recommended to use globally unique ids 176 : when possible. Returns a pointer in the caller's address space to 177 : the in-preparation transaction on success and NULL on failure. The 178 : lifetime of the returned pointer is as described in 179 : fd_funk_txn_query. 180 : 181 : At start of preparation, the records in the txn are a virtual clone of the 182 : records in its parent transaction. The funk records can be modified 183 : when the funk has no children. Similarly, the records of an 184 : in-preparation transaction can be freely modified when it has 185 : no children. 186 : 187 : Assumes funk is a current local join. Reasons for failure include 188 : funk is NULL, the funk's transaction map is full, the parent is 189 : neither NULL nor points to an in-preparation funk transaction, xid is 190 : NULL, the requested xid is in use (i.e. the last published or matches 191 : another in-preparation transaction). 192 : 193 : This is a reasonably fast O(1) time (theoretical minimum), reasonably 194 : small O(1) space (theoretical minimum), does no allocation, does no 195 : system calls, and produces no garbage to collect (at this layer at 196 : least). That is, we can scalably track forks until we run out of 197 : resources allocated to the funk. */ 198 : 199 : void 200 : fd_funk_txn_prepare( fd_funk_t * funk, 201 : fd_funk_txn_xid_t const * parent, 202 : fd_funk_txn_xid_t const * xid ); 203 : 204 : /* Misc */ 205 : 206 : /* fd_funk_txn_verify verifies a transaction map. Returns 207 : FD_FUNK_SUCCESS if the transaction map appears intact and 208 : FD_FUNK_ERR_INVAL if not (logs details). Meant to be called as part 209 : of fd_funk_verify. */ 210 : 211 : int 212 : fd_funk_txn_verify( fd_funk_t * funk ); 213 : 214 : FD_FN_UNUSED static char const * 215 1144092 : fd_funk_txn_state_str( uint state ) { 216 1144092 : switch( state ) { 217 572046 : case FD_FUNK_TXN_STATE_FREE: return "free"; 218 572046 : case FD_FUNK_TXN_STATE_ACTIVE: return "alive"; 219 0 : case FD_FUNK_TXN_STATE_CANCEL: return "cancel"; 220 0 : case FD_FUNK_TXN_STATE_PUBLISH: return "publish"; 221 0 : default: return "unknown"; 222 1144092 : } 223 1144092 : } 224 : 225 : #ifndef __cplusplus 226 : 227 : FD_FN_UNUSED static void 228 : fd_funk_txn_state_assert( fd_funk_txn_t const * txn, 229 317454 : uint want ) { 230 317454 : uint have = FD_VOLATILE_CONST( txn->state ); 231 317454 : if( FD_UNLIKELY( want!=have ) ) { 232 0 : FD_LOG_CRIT(( "Invariant violation detected on funk txn: expected state %u-%s, found state %u-%s", 233 0 : want, fd_funk_txn_state_str( want ), 234 0 : have, fd_funk_txn_state_str( have ) )); 235 0 : } 236 317454 : } 237 : 238 : FD_FN_UNUSED static void 239 : fd_funk_txn_xid_assert( fd_funk_txn_t const * txn, 240 0 : fd_funk_txn_xid_t const * xid ) { 241 0 : uint found_state = FD_VOLATILE_CONST( txn->state ); 242 0 : fd_funk_txn_xid_t found_xid = FD_VOLATILE_CONST( txn->xid ); 243 0 : int xid_ok = fd_funk_txn_xid_eq( &found_xid, xid ); 244 0 : int state_ok = found_state==FD_FUNK_TXN_STATE_ACTIVE; 245 0 : if( FD_UNLIKELY( !xid_ok || !state_ok ) ) { 246 0 : if( !xid_ok ) { 247 0 : FD_LOG_CRIT(( "Data race detected: funk txn %p %lu:%lu use-after-free", 248 0 : (void *)txn, 249 0 : xid->ul[0], xid->ul[1] )); 250 0 : } else { 251 0 : FD_LOG_CRIT(( "Data race detected: funk txn %p %lu:%lu in invalid state %u-%s", 252 0 : (void *)txn, 253 0 : xid->ul[0], xid->ul[1], 254 0 : found_state, fd_funk_txn_state_str( found_state ) )); 255 0 : } 256 0 : } 257 0 : } 258 : 259 : #endif /* !__cplusplus */ 260 : 261 : FD_PROTOTYPES_END 262 : 263 : #endif /* HEADER_fd_src_funk_fd_funk_txn_h */
