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 8258904 : #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 6 : #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 1182 : #define MAP_ELE_T fd_funk_txn_t 73 : #define MAP_KEY_T fd_funk_txn_xid_t 74 : #define MAP_KEY xid 75 3128307 : #define MAP_KEY_EQ(k0,k1) fd_funk_txn_xid_eq((k0),(k1)) 76 3537813 : #define MAP_KEY_HASH(k0,seed) fd_funk_txn_xid_hash((k0),(seed)) 77 1182 : #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 1933710 : #define FD_FUNK_TXN_STATE_FREE (0U) 86 889602 : #define FD_FUNK_TXN_STATE_ACTIVE (1U) 87 347247 : #define FD_FUNK_TXN_STATE_CANCEL (2U) 88 224775 : #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 5073342 : static inline uint fd_funk_txn_cidx( ulong idx ) { return (uint) idx; } 95 5041305 : 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 5566680 : 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 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; } 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 1284870 : fd_funk_txn_is_frozen( fd_funk_txn_t const * txn ) { 161 1284870 : return !fd_funk_txn_idx_is_null( fd_funk_txn_idx( txn->child_head_cidx ) ); 162 1284870 : } 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. A NULL parent means the transaction should be a child 170 : of funk. xid points to transaction id that should be used for the 171 : transaction. This id must be unique over all in-preparation 172 : transactions, the root transaction and the last published 173 : transaction. It is strongly recommended to use globally unique ids 174 : when possible. Returns a pointer in the caller's address space to 175 : the in-preparation transaction on success and NULL on failure. The 176 : lifetime of the returned pointer is as described in 177 : fd_funk_txn_query. 178 : 179 : At start of preparation, the records in the txn are a virtual clone of the 180 : records in its parent transaction. The funk records can be modified 181 : when the funk has no children. Similarly, the records of an 182 : in-preparation transaction can be freely modified when it has 183 : no children. 184 : 185 : Assumes funk is a current local join. Reasons for failure include 186 : funk is NULL, the funk's transaction map is full, the parent is 187 : neither NULL nor points to an in-preparation funk transaction, xid is 188 : NULL, the requested xid is in use (i.e. the last published or matches 189 : another in-preparation transaction). 190 : 191 : This is a reasonably fast O(1) time (theoretical minimum), reasonably 192 : small O(1) space (theoretical minimum), does no allocation, does no 193 : system calls, and produces no garbage to collect (at this layer at 194 : least). That is, we can scalably track forks until we run out of 195 : resources allocated to the funk. */ 196 : 197 : void 198 : fd_funk_txn_prepare( fd_funk_t * funk, 199 : fd_funk_txn_xid_t const * parent, 200 : fd_funk_txn_xid_t const * xid ); 201 : 202 : /* Misc */ 203 : 204 : /* fd_funk_txn_verify verifies a transaction map. Returns 205 : FD_FUNK_SUCCESS if the transaction map appears intact and 206 : FD_FUNK_ERR_INVAL if not (logs details). Meant to be called as part 207 : of fd_funk_verify. */ 208 : 209 : int 210 : fd_funk_txn_verify( fd_funk_t * funk ); 211 : 212 : FD_FN_UNUSED static char const * 213 1144236 : fd_funk_txn_state_str( uint state ) { 214 1144236 : switch( state ) { 215 572118 : case FD_FUNK_TXN_STATE_FREE: return "free"; 216 572118 : case FD_FUNK_TXN_STATE_ACTIVE: return "alive"; 217 0 : case FD_FUNK_TXN_STATE_CANCEL: return "cancel"; 218 0 : case FD_FUNK_TXN_STATE_PUBLISH: return "publish"; 219 0 : default: return "unknown"; 220 1144236 : } 221 1144236 : } 222 : 223 : #ifndef __cplusplus 224 : 225 : FD_FN_UNUSED static void 226 : fd_funk_txn_state_assert( fd_funk_txn_t const * txn, 227 317484 : uint want ) { 228 317484 : uint have = FD_VOLATILE_CONST( txn->state ); 229 317484 : if( FD_UNLIKELY( want!=have ) ) { 230 0 : FD_LOG_CRIT(( "Invariant violation detected on funk txn: expected state %u-%s, found state %u-%s", 231 0 : want, fd_funk_txn_state_str( want ), 232 0 : have, fd_funk_txn_state_str( have ) )); 233 0 : } 234 317484 : } 235 : 236 : FD_FN_UNUSED static void 237 : fd_funk_txn_xid_assert( fd_funk_txn_t const * txn, 238 0 : fd_funk_txn_xid_t const * xid ) { 239 0 : uint found_state = FD_VOLATILE_CONST( txn->state ); 240 0 : fd_funk_txn_xid_t found_xid = FD_VOLATILE_CONST( txn->xid ); 241 0 : int xid_ok = fd_funk_txn_xid_eq( &found_xid, xid ); 242 0 : int state_ok = found_state==FD_FUNK_TXN_STATE_ACTIVE; 243 0 : if( FD_UNLIKELY( !xid_ok || !state_ok ) ) { 244 0 : if( !xid_ok ) { 245 0 : FD_LOG_CRIT(( "Data race detected: funk txn %p %lu:%lu use-after-free", 246 0 : (void *)txn, 247 0 : xid->ul[0], xid->ul[1] )); 248 0 : } else { 249 0 : FD_LOG_CRIT(( "Data race detected: funk txn %p %lu:%lu in invalid state %u-%s", 250 0 : (void *)txn, 251 0 : xid->ul[0], xid->ul[1], 252 0 : found_state, fd_funk_txn_state_str( found_state ) )); 253 0 : } 254 0 : } 255 0 : } 256 : 257 : #endif /* !__cplusplus */ 258 : 259 : FD_PROTOTYPES_END 260 : 261 : #endif /* HEADER_fd_src_funk_fd_funk_txn_h */
