Line data Source code
1 : #ifndef HEADER_fd_src_funk_fd_funk_rec_h 2 : #define HEADER_fd_src_funk_fd_funk_rec_h 3 : 4 : /* fd_funk_rec.h provides APIs for managing funk records */ 5 : 6 : #include "fd_funk_txn.h" /* Includes fd_funk_base.h */ 7 : 8 : /* FD_FUNK_REC_{ALIGN,FOOTPRINT} describe the alignment and footprint of 9 : a fd_funk_rec_t. ALIGN will be a power of 2, footprint will be a 10 : multiple of align. These are provided to facilitate compile time 11 : declarations. */ 12 : 13 0 : #define FD_FUNK_REC_ALIGN (32UL) 14 : 15 : /* FD_FUNK_REC_IDX_NULL gives the map record idx value used to represent 16 : NULL. This value also set a limit on how large rec_max can be. */ 17 : 18 13592697 : #define FD_FUNK_REC_IDX_NULL (UINT_MAX) 19 : 20 : /* A fd_funk_rec_t describes a funk record. */ 21 : 22 : struct __attribute__((aligned(FD_FUNK_REC_ALIGN))) fd_funk_rec { 23 : 24 : /* These fields are managed by the funk's rec_map */ 25 : 26 : fd_funk_xid_key_pair_t pair; /* Transaction id and record key pair */ 27 : uint map_next; /* Internal use by map */ 28 : 29 : /* These fields are managed by the user */ 30 : 31 : uchar user[ 4 ]; 32 : 33 : /* These fields are managed by funk */ 34 : 35 : ulong ver_lock; /* Record version and lock bits */ 36 : 37 : uint next_idx; /* Record map index of next record in its transaction */ 38 : uint prev_idx; /* Record map index of previous record in its transaction */ 39 : 40 : /* Note: use of uint here requires FD_FUNK_REC_VAL_MAX to be at most 41 : (1UL<<28)-1. */ 42 : 43 : ulong val_sz : 28; /* Num bytes in record value, in [0,val_max] */ 44 : ulong val_max : 28; /* Max byte in record value, in [0,FD_FUNK_REC_VAL_MAX], 0 if val_gaddr is 0 */ 45 : ulong tag : 1; /* Used for internal validation */ 46 : ulong val_gaddr; /* Wksp gaddr on record value if any, 0 if val_max is 0 47 : If non-zero, the region [val_gaddr,val_gaddr+val_max) will be a current fd_alloc allocation (such that it is 48 : has tag wksp_tag) and the owner of the region will be the record. The allocator is 49 : fd_funk_alloc(). IMPORTANT! HAS NO GUARANTEED ALIGNMENT! */ 50 : 51 : }; 52 : 53 : typedef struct fd_funk_rec fd_funk_rec_t; 54 : 55 : FD_STATIC_ASSERT( sizeof(fd_funk_rec_t) == 3U*FD_FUNK_REC_ALIGN, record size is wrong ); 56 : 57 : #define FD_FUNK_REC_PAIR_FMT "xid=%lu:%lu,key=%016lx:%016lx:%016lx:%016lx" 58 : #define FD_FUNK_REC_PAIR_FMT_ARGS(p) \ 59 : (p).xid->ul[0], (p).xid->ul[1], \ 60 : fd_ulong_bswap( (p).key->ul[0] ), fd_ulong_bswap( (p).key->ul[1] ), \ 61 : fd_ulong_bswap( (p).key->ul[2] ), fd_ulong_bswap( (p).key->ul[3] ) 62 : 63 : /* fd_funk_rec_map allows for indexing records by their (xid,key) pair. 64 : It is used to store all records of the last published transaction and 65 : the records being updated for a transaction that is in-preparation. 66 : Published records are stored under the pair (root,key). (This is 67 : done so that publishing a transaction doesn't require updating all 68 : transaction id of all the records that were not updated by the 69 : publish.) */ 70 : 71 : #define POOL_NAME fd_funk_rec_pool 72 : #define POOL_ELE_T fd_funk_rec_t 73 : #define POOL_IDX_T uint 74 : #define POOL_NEXT map_next 75 : #define POOL_IMPL_STYLE 1 76 : #define POOL_LAZY 1 77 : #include "../util/tmpl/fd_pool_para.c" 78 : 79 : #define MAP_NAME fd_funk_rec_map 80 48990 : #define MAP_ELE_T fd_funk_rec_t 81 : #define MAP_KEY_T fd_funk_xid_key_pair_t 82 : #define MAP_KEY pair 83 2042934 : #define MAP_KEY_EQ(k0,k1) fd_funk_xid_key_pair_eq((k0),(k1)) 84 2693127 : #define MAP_KEY_HASH(k0,seed) fd_funk_xid_key_pair_hash((k0),(seed)) 85 : #define MAP_IDX_T uint 86 48990 : #define MAP_NEXT map_next 87 : #define MAP_MAGIC (0xf173da2ce77ecdb0UL) /* Firedancer rec db version 0 */ 88 17951097 : #define FD_FUNK_REC_MAP_CNT_WIDTH 43 89 12734385 : #define MAP_CNT_WIDTH FD_FUNK_REC_MAP_CNT_WIDTH 90 : #define MAP_IMPL_STYLE 1 91 : #define MAP_PEDANTIC 1 92 : #include "../util/tmpl/fd_map_chain_para.c" 93 : 94 : typedef fd_funk_rec_map_query_t fd_funk_rec_query_t; 95 : 96 : /* fd_funk_rec_prepare_t represents a new record that has been 97 : prepared but not inserted into the map yet. See documentation for 98 : fd_funk_rec_prepare. */ 99 : 100 : struct _fd_funk_rec_prepare { 101 : fd_funk_rec_t * rec; 102 : uint * rec_head_idx; 103 : uint * rec_tail_idx; 104 : }; 105 : 106 : typedef struct _fd_funk_rec_prepare fd_funk_rec_prepare_t; 107 : 108 : FD_PROTOTYPES_BEGIN 109 : 110 : /* fd_funk_rec_idx_is_null returns 1 if idx is FD_FUNK_REC_IDX_NULL and 111 : 0 otherwise. */ 112 : 113 3154290 : FD_FN_CONST static inline int fd_funk_rec_idx_is_null( uint idx ) { return idx==FD_FUNK_REC_IDX_NULL; } 114 : 115 : /* Accessors */ 116 : 117 : /* FIXME deprecate */ 118 : 119 : fd_funk_rec_t * 120 : fd_funk_rec_query_try( fd_funk_t * funk, 121 : fd_funk_txn_xid_t const * xid, 122 : fd_funk_rec_key_t const * key, 123 : fd_funk_rec_query_t * query ); 124 : 125 : /* fd_funk_rec_{pair,xid,key} returns a pointer in the local address 126 : space of the {(transaction id,record key) pair,transaction id,record 127 : key} of a live record. Assumes rec points to a live record in the 128 : caller's address space. The lifetime of the returned pointer is the 129 : same as rec. The value at the pointer will be constant for its 130 : lifetime. */ 131 : 132 231 : FD_FN_CONST static inline fd_funk_xid_key_pair_t const * fd_funk_rec_pair( fd_funk_rec_t const * rec ) { return &rec->pair; } 133 12237 : FD_FN_CONST static inline fd_funk_txn_xid_t const * fd_funk_rec_xid ( fd_funk_rec_t const * rec ) { return rec->pair.xid; } 134 0 : FD_FN_CONST static inline fd_funk_rec_key_t const * fd_funk_rec_key ( fd_funk_rec_t const * rec ) { return rec->pair.key; } 135 : 136 : /* fd_funk_rec_prepare creates an unpublished funk record entry. This 137 : is the first step to adding a funk record to a transaction. Record 138 : entry acquisition may fail if the record object pool is exhausted 139 : (FD_FUNK_ERR_REC) or the transaction is not writable 140 : (FD_FUNK_ERR_FROZEN). The returned record entry (located in funk 141 : shared memory) is then either be cancelled or published by the 142 : caller. This record is invisible to funk query or record-iteration 143 : operations until published. Concurrent record preparation is fine. */ 144 : 145 : fd_funk_rec_t * 146 : fd_funk_rec_prepare( fd_funk_t * funk, 147 : fd_funk_txn_xid_t const * xid, 148 : fd_funk_rec_key_t const * key, 149 : fd_funk_rec_prepare_t * prepare, 150 : int * opt_err ); 151 : 152 : /* fd_funk_rec_publish makes a prepared record globally visible. First, 153 : registers a record with the txn's record list, then inserts it into 154 : the record map. Concurrent record publishing is fine, even to the 155 : same transaction. Crashes the application with FD_LOG_CRIT if the 156 : caller attempts to publish the same (txn,xid) key twice. */ 157 : 158 : void 159 : fd_funk_rec_publish( fd_funk_t * funk, 160 : fd_funk_rec_prepare_t * prepare ); 161 : 162 : /* Misc */ 163 : 164 : /* fd_funk_rec_verify verifies the record map. Returns FD_FUNK_SUCCESS 165 : if the record map appears intact and FD_FUNK_ERR_INVAL if not (logs 166 : details). Meant to be called as part of fd_funk_verify. As such, it 167 : assumes funk is non-NULL, fd_funk_{wksp,txn_map,rec_map} have been 168 : verified to work and the txn_map has been verified. */ 169 : 170 : int 171 : fd_funk_rec_verify( fd_funk_t * funk ); 172 : 173 : /* Record locking ****************************************************** 174 : 175 : The funk_rec 'ver_lock' field synchronizes record accesses via atomic 176 : CAS. There exist three access types: 177 : - 'read': read-only record access 178 : - 'write': record creation or modification 179 : - 'admin': record destruction (during rooting) 180 : 181 : Record locking has two goals: 182 : - Delay destruction of records until other accesses complete 183 : - Detect usage bugs (e.g. conflicting write attempts to the same 184 : record) 185 : 186 : 'ver_lock' is encoded as two integers packed into a 64-bit ulong: 187 : - 'ver': version counter incremented on every record destruction 188 : and creation (lsb=0 implies record is dead, lsb=1 implies 189 : record is alive) 190 : - 'lock': max implies record is write locked. Otherwise, equals 191 : the number of active read locks. 192 : 193 : There further exist the following transitions: 194 : - 'write lock acquire': lock=0 --> lock=max 195 : - 'write lock release': lock=max --> lock=0 196 : - 'read lock acquire': lock=n --> lock=n+1 197 : - 'read lock release': lock=n+1 --> lock=n 198 : - 'destroy': ver=n --> ver=n+1 (where n%2 == 0) 199 : - 'create': ver=n --> ver=n+1 (where n%2 == 1) 200 : 201 : ***********************************************************************/ 202 : 203 2052321 : #define FD_FUNK_REC_LOCK_BIT_CNT (11) 204 285 : #define FD_FUNK_REC_LOCK_MASK ( (1UL<<FD_FUNK_REC_LOCK_BIT_CNT)-1UL ) 205 684012 : #define FD_FUNK_REC_VER_BIT_CNT (64 - FD_FUNK_REC_LOCK_BIT_CNT) 206 684012 : #define FD_FUNK_REC_VER_MASK ( (1UL<<FD_FUNK_REC_VER_BIT_CNT)-1UL ) 207 : 208 : FD_FN_CONST static inline ulong 209 : fd_funk_rec_ver_lock( ulong ver, 210 684012 : ulong lock ) { 211 684012 : return ver<<FD_FUNK_REC_LOCK_BIT_CNT | lock; 212 684012 : } 213 : 214 : FD_FN_CONST static inline ulong 215 684012 : fd_funk_rec_ver_bits( ulong ver_lock ) { 216 684012 : return ver_lock >> FD_FUNK_REC_LOCK_BIT_CNT; 217 684012 : } 218 : 219 : FD_FN_CONST static inline ulong 220 684012 : fd_funk_rec_ver_inc( ulong ver ) { 221 684012 : return (ver+1UL) & FD_FUNK_REC_VER_MASK; 222 684012 : } 223 : 224 : FD_FN_CONST static inline ulong 225 0 : fd_funk_rec_lock_bits( ulong ver_lock ) { 226 0 : return ver_lock & ( (1UL<<FD_FUNK_REC_LOCK_BIT_CNT)-1UL ); 227 0 : } 228 : 229 : FD_FN_CONST static inline int 230 0 : fd_funk_rec_ver_alive( ulong ver ) { 231 0 : return !!( ver & 1UL ); 232 0 : } 233 : 234 : FD_PROTOTYPES_END 235 : 236 : #endif /* HEADER_fd_src_funk_fd_funk_rec_h */
