Line data Source code
1 : #ifndef HEADER_fd_src_funk_fd_funk_base_h 2 : #define HEADER_fd_src_funk_fd_funk_base_h 3 : 4 : /* Funk terminology / concepts: 5 : 6 : - A funk instance stores records. 7 : 8 : - A record is a key-value pair. 9 : 10 : - keys are a fixed length fd_funk_rec_key_t. 11 : 12 : - values are variable size arbitrary binary data with an upper bound 13 : to the size. 14 : 15 : - Records are indexed by key. 16 : 17 : - A funk transaction describes changes to the funk records. 18 : 19 : - A transactions has a globally unique identifier and a parent 20 : transaction. 21 : 22 : - Transactions with children cannot be modified. 23 : 24 : - The chain of transactions through a transaction's ancestors 25 : (its parent, grandparent, great-grandparent, ...) provides a 26 : history of the funk all the way back the "root" transaction. 27 : 28 : - A transaction can be either in preparation or published. 29 : 30 : - The ancestors of a published transaction cannot be modified. 31 : 32 : - In preparation transactions can be cancelled. 33 : 34 : - Cancelling a transaction will discard all funk record updates for 35 : that transaction and any descendant transactions. 36 : 37 : - Published transactions cannot be cancelled. 38 : 39 : - Critically, competing/parallel transaction histories are allowed. 40 : 41 : - A user can to read / write all funk records for the most recently 42 : published transactions and all transactions locally in preparation. */ 43 : 44 : #include "../util/fd_util.h" 45 : #include "../util/valloc/fd_valloc.h" 46 : 47 : /* FD_FUNK_SUCCESS is used by various APIs to indicate the operation 48 : successfully completed. This will be 0. FD_FUNK_ERR_* gives a 49 : number of error codes used by fd_funk APIs. These will be negative 50 : integers. */ 51 : 52 923011314 : #define FD_FUNK_SUCCESS (0) /* Success */ 53 4776642903 : #define FD_FUNK_ERR_INVAL (-1) /* Failed due to obviously invalid inputs */ 54 3 : #define FD_FUNK_ERR_XID (-2) /* Failed due to transaction id issue (e.g. xid present/absent when it should be absent/present) */ 55 1828050 : #define FD_FUNK_ERR_KEY (-3) /* Failed due to record key issue (e.g. key present/absent when it should be absent/present) */ 56 43221825 : #define FD_FUNK_ERR_FROZEN (-4) /* Failed due to frozen issue (e.g. attempt to change records in a frozen transaction) */ 57 3 : #define FD_FUNK_ERR_TXN (-5) /* Failed due to transaction map issue (e.g. funk txn_max too small) */ 58 20210667 : #define FD_FUNK_ERR_REC (-6) /* Failed due to record map issue (e.g. funk rec_max too small) */ 59 3 : #define FD_FUNK_ERR_MEM (-7) /* Failed due to wksp issue (e.g. wksp too small) */ 60 0 : #define FD_FUNK_ERR_SYS (-8) /* Failed system call (e.g. a file write) */ 61 : 62 : /* FD_FUNK_REC_KEY_{ALIGN,FOOTPRINT} describe the alignment and 63 : footprint of a fd_funk_rec_key_t. ALIGN is a positive integer power 64 : of 2. FOOTPRINT is a multiple of ALIGN. These are provided to 65 : facilitate compile time declarations. */ 66 : 67 : #define FD_FUNK_REC_KEY_ALIGN (8UL) 68 7939836 : #define FD_FUNK_REC_KEY_FOOTPRINT (40UL) /* 32 byte hash + 8 byte meta */ 69 : 70 : /* A fd_funk_rec_key_t identifies a funk record. Compact binary keys 71 : are encouraged but a cstr can be used so long as it has 72 : strlen(cstr)<FD_FUNK_REC_KEY_FOOTPRINT and the characters c[i] for i 73 : in [strlen(cstr),FD_FUNK_REC_KEY_FOOTPRINT) zero. (Also, if encoding 74 : a cstr in a key, recommend using first byte to encode the strlen for 75 : accelerating cstr operations further but this is up to the user.) */ 76 : 77 : union __attribute__((aligned(FD_FUNK_REC_KEY_ALIGN))) fd_funk_rec_key { 78 : char c [ FD_FUNK_REC_KEY_FOOTPRINT ]; 79 : uchar uc[ FD_FUNK_REC_KEY_FOOTPRINT ]; 80 : ulong ul[ FD_FUNK_REC_KEY_FOOTPRINT / sizeof(ulong) ]; 81 : }; 82 : 83 : typedef union fd_funk_rec_key fd_funk_rec_key_t; 84 : 85 : /* FD_FUNK_TXN_XID_{ALIGN,FOOTPRINT} describe the alignment and 86 : footprint of a fd_funk_txn_xid_t. ALIGN is a positive integer power 87 : of 2. FOOTPRINT is a multiple of ALIGN. These are provided to 88 : facilitate compile time declarations. */ 89 : 90 : #define FD_FUNK_TXN_XID_ALIGN (8UL) 91 : #define FD_FUNK_TXN_XID_FOOTPRINT (16UL) 92 : 93 : /* A fd_funk_txn_xid_t identifies a funk transaction. Compact binary 94 : identifiers are encouraged but a cstr can be used so long as it has 95 : strlen(cstr)<FD_FUNK_TXN_XID_FOOTPRINT and characters c[i] for i in 96 : [strlen(cstr),FD_FUNK_TXN_KEY_FOOTPRINT) zero. (Also, if encoding a 97 : cstr in a transaction id, recommend using first byte to encode the 98 : strlen for accelerating cstr operations even further but this is more 99 : up to the application.) */ 100 : 101 : union __attribute__((aligned(FD_FUNK_TXN_XID_ALIGN))) fd_funk_txn_xid { 102 : char c [ FD_FUNK_TXN_XID_FOOTPRINT ]; 103 : uchar uc[ FD_FUNK_TXN_XID_FOOTPRINT ]; 104 : ulong ul[ FD_FUNK_TXN_XID_FOOTPRINT / sizeof(ulong) ]; 105 : }; 106 : 107 : typedef union fd_funk_txn_xid fd_funk_txn_xid_t; 108 : 109 : /* FD_FUNK_XID_KEY_PAIR_{ALIGN,FOOTPRINT} describe the alignment and 110 : footprint of a fd_funk_xid_key_pair_t. ALIGN is a positive integer 111 : power of 2. FOOTPRINT is a multiple of ALIGN. These are provided to 112 : facilitate compile time declarations. */ 113 : 114 : #define FD_FUNK_XID_KEY_PAIR_ALIGN (8UL) 115 : #define FD_FUNK_XID_KEY_PAIR_FOOTPRINT (56UL) 116 : 117 : /* A fd_funk_xid_key_pair_t identifies a funk record. It is just 118 : xid and key packed into the same structure. */ 119 : 120 : struct fd_funk_xid_key_pair { 121 : fd_funk_txn_xid_t xid[1]; 122 : fd_funk_rec_key_t key[1]; 123 : }; 124 : 125 : typedef struct fd_funk_xid_key_pair fd_funk_xid_key_pair_t; 126 : 127 : /* A fd_funk_t * is an opaque handle of a local join to a funk instance */ 128 : 129 : struct fd_funk_private; 130 : typedef struct fd_funk_private fd_funk_t; 131 : 132 : FD_PROTOTYPES_BEGIN 133 : 134 : /* fd_funk_rec_key_hash provides a family of hashes that hash the key 135 : pointed to by k to a uniform quasi-random 64-bit integer. seed 136 : selects the particular hash function to use and can be an arbitrary 137 : 64-bit value. Returns the hash. The hash functions are high quality 138 : but not cryptographically secure. Assumes k is in the caller's 139 : address space and valid. */ 140 : 141 : FD_FN_UNUSED FD_FN_PURE static ulong /* Workaround -Winline */ 142 : fd_funk_rec_key_hash( fd_funk_rec_key_t const * k, 143 3809214090 : ulong seed ) { 144 3809214090 : return (fd_ulong_hash( seed ^ (1UL<<0) ^ k->ul[0] ) ^ fd_ulong_hash( seed ^ (1UL<<1) ^ k->ul[1] ) ) ^ 145 3809214090 : (fd_ulong_hash( seed ^ (1UL<<2) ^ k->ul[2] ) ^ fd_ulong_hash( seed ^ (1UL<<3) ^ k->ul[3] ) ) ^ 146 3809214090 : (fd_ulong_hash( seed ^ (1UL<<4) ^ k->ul[4] ) ); /* tons of ILP */ 147 3809214090 : } 148 : 149 : /* fd_funk_rec_key_eq returns 1 if keys pointed to by ka and kb are 150 : equal and 0 otherwise. Assumes ka and kb are in the caller's address 151 : space and valid. */ 152 : 153 : FD_FN_UNUSED FD_FN_PURE static int /* Workaround -Winline */ 154 : fd_funk_rec_key_eq( fd_funk_rec_key_t const * ka, 155 3789541359 : fd_funk_rec_key_t const * kb ) { 156 3789541359 : ulong const * a = ka->ul; 157 3789541359 : ulong const * b = kb->ul; 158 3789541359 : return !( ((a[0]^b[0]) | (a[1]^b[1])) | ((a[2]^b[2]) | (a[3]^b[3])) | (a[4]^b[4]) ) ; 159 3789541359 : } 160 : 161 : /* fd_funk_rec_key_copy copies the key pointed to by ks into the key 162 : pointed to by kd and returns kd. Assumes kd and ks are in the 163 : caller's address space and valid. */ 164 : 165 : static inline fd_funk_rec_key_t * 166 : fd_funk_rec_key_copy( fd_funk_rec_key_t * kd, 167 639208623 : fd_funk_rec_key_t const * ks ) { 168 639208623 : ulong * d = kd->ul; 169 639208623 : ulong const * s = ks->ul; 170 639208623 : d[0] = s[0]; d[1] = s[1]; d[2] = s[2]; d[3] = s[3]; d[4] = s[4]; 171 639208623 : return kd; 172 639208623 : } 173 : 174 : /* fd_funk_txn_xid_hash provides a family of hashes that hash the xid 175 : pointed to by x to a uniform quasi-random 64-bit integer. seed 176 : selects the particular hash function to use and can be an arbitrary 177 : 64-bit value. Returns the hash. The hash functions are high quality 178 : but not cryptographically secure. Assumes x is in the caller's 179 : address space and valid. */ 180 : 181 : FD_FN_UNUSED FD_FN_PURE static ulong /* Work around -Winline */ 182 : fd_funk_txn_xid_hash( fd_funk_txn_xid_t const * x, 183 1029450123 : ulong seed ) { 184 1029450123 : return ( fd_ulong_hash( seed ^ (1UL<<0) ^ x->ul[0] ) ^ fd_ulong_hash( seed ^ (1UL<<1) ^ x->ul[1] ) ); /* tons of ILP */ 185 1029450123 : } 186 : 187 : /* fd_funk_txn_xid_eq returns 1 if transaction id pointed to by xa and 188 : xb are equal and 0 otherwise. Assumes xa and xb are in the caller's 189 : address space and valid. */ 190 : 191 : FD_FN_PURE static inline int 192 : fd_funk_txn_xid_eq( fd_funk_txn_xid_t const * xa, 193 5109163380 : fd_funk_txn_xid_t const * xb ) { 194 5109163380 : ulong const * a = xa->ul; 195 5109163380 : ulong const * b = xb->ul; 196 5109163380 : return !( (a[0]^b[0]) | (a[1]^b[1]) ); 197 5109163380 : } 198 : 199 : /* fd_funk_txn_xid_copy copies the transaction id pointed to by xs into 200 : the transaction id pointed to by xd and returns xd. Assumes xd and 201 : xs are in the caller's address space and valid. */ 202 : 203 : static inline fd_funk_txn_xid_t * 204 : fd_funk_txn_xid_copy( fd_funk_txn_xid_t * xd, 205 646886946 : fd_funk_txn_xid_t const * xs ) { 206 646886946 : ulong * d = xd->ul; 207 646886946 : ulong const * s = xs->ul; 208 646886946 : d[0] = s[0]; d[1] = s[1]; 209 646886946 : return xd; 210 646886946 : } 211 : 212 : /* fd_funk_txn_xid_eq_root returns 1 if transaction id pointed to by x 213 : is the root transaction. Assumes x is in the caller's address space 214 : and valid. */ 215 : 216 : FD_FN_PURE static inline int 217 1222894236 : fd_funk_txn_xid_eq_root( fd_funk_txn_xid_t const * x ) { 218 1222894236 : ulong const * a = x->ul; 219 1222894236 : return !(a[0] | a[1]); 220 1222894236 : } 221 : 222 : /* fd_funk_txn_xid_set_root sets transaction id pointed to by x to the 223 : root transaction and returns x. Assumes x is in the caller's address 224 : space and valid. */ 225 : 226 : static inline fd_funk_txn_xid_t * 227 816963 : fd_funk_txn_xid_set_root( fd_funk_txn_xid_t * x ) { 228 816963 : ulong * a = x->ul; 229 816963 : a[0] = 0UL; a[1] = 0UL; 230 816963 : return x; 231 816963 : } 232 : 233 : /* fd_funk_xid_key_pair_hash produces a 64-bit hash case for a 234 : xid_key_pair. Assumes p is in the caller's address space and valid. */ 235 : 236 : FD_FN_PURE static inline ulong 237 : fd_funk_xid_key_pair_hash( fd_funk_xid_key_pair_t const * p, 238 3353393634 : ulong seed ) { 239 : /* We ignore the xid part of the key because we need all the instances 240 : of a given record key to appear in the same hash 241 : chain. fd_funk_rec_query_global depends on this. */ 242 3353393634 : return fd_funk_rec_key_hash( p->key, seed ); 243 3353393634 : } 244 : 245 : /* fd_funk_xid_key_pair_eq returns 1 if (xid,key) pair pointed to by pa 246 : and pb are equal and 0 otherwise. Assumes pa and pb are in the 247 : caller's address space and valid. */ 248 : 249 : FD_FN_UNUSED FD_FN_PURE static int /* Work around -Winline */ 250 : fd_funk_xid_key_pair_eq( fd_funk_xid_key_pair_t const * pa, 251 2321901225 : fd_funk_xid_key_pair_t const * pb ) { 252 2321901225 : return fd_funk_txn_xid_eq( pa->xid, pb->xid ) & fd_funk_rec_key_eq( pa->key, pb->key ); 253 2321901225 : } 254 : 255 : /* fd_funk_xid_key_pair_copy copies the (xid,key) pair pointed to by ps 256 : into the (xid,key) pair to by pd and returns pd. Assumes pd and ps 257 : are in the caller's address space and valid. */ 258 : 259 : static inline fd_funk_xid_key_pair_t * 260 : fd_funk_xid_key_pair_copy( fd_funk_xid_key_pair_t * pd, 261 10856379 : fd_funk_xid_key_pair_t const * ps ) { 262 10856379 : fd_funk_txn_xid_copy( pd->xid, ps->xid ); 263 10856379 : fd_funk_rec_key_copy( pd->key, ps->key ); 264 10856379 : return pd; 265 10856379 : } 266 : 267 : /* fd_funk_xid_key_pair_init set the (xid,key) pair p to pair formed 268 : from the transaction id pointed to by x and the record key pointed to 269 : by k. Assumes p, x and k are in the caller's address space and 270 : valid. */ 271 : 272 : static inline fd_funk_xid_key_pair_t * 273 : fd_funk_xid_key_pair_init( fd_funk_xid_key_pair_t * p, 274 : fd_funk_txn_xid_t const * x, 275 625352244 : fd_funk_rec_key_t const * k ) { 276 625352244 : fd_funk_txn_xid_copy( p->xid, x ); 277 625352244 : fd_funk_rec_key_copy( p->key, k ); 278 625352244 : return p; 279 625352244 : } 280 : 281 : /* fd_funk_strerror converts an FD_FUNK_SUCCESS / FD_FUNK_ERR_* code 282 : into a human readable cstr. The lifetime of the returned pointer is 283 : infinite. The returned pointer is always to a non-NULL cstr. */ 284 : 285 : FD_FN_CONST char const * 286 : fd_funk_strerror( int err ); 287 : 288 : /* TODO: Consider renaming transaction/txn to update (too much typing)? 289 : upd (probably too similar to UDP) node? block? blk? state? commit? 290 : ... to reduce naming collisions with terminology in use elsewhere? 291 : 292 : TODO: Consider fine tuning {REC,TXN}_{ALIGN,FOOTPRINT} to balance 293 : application use cases with in memory packing with AVX / CPU cache 294 : friendly accelerability. Likewise, virtually everything in here can 295 : be AVX accelerated if desired. E.g. 8 uint hash in parallel then an 296 : 8 wide xor lane reduction tree in hash? 297 : 298 : TODO: Consider letting the user provide alternatives for record and 299 : transaction hashes at compile time (e.g. ids in blockchain apps are 300 : often already crypto secure hashes in which case x->ul[0] ^ seed is 301 : just as good theoretically and faster practically). */ 302 : 303 : FD_PROTOTYPES_END 304 : 305 : #endif /* HEADER_fd_src_funk_fd_funk_base_h */
