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