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 a 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 719268378 : #define FD_FUNK_SUCCESS (0) /* Success */ 53 3891887418 : #define FD_FUNK_ERR_INVAL (-1) /* Failed due to obviously invalid inputs */ 54 50445 : #define FD_FUNK_ERR_XID (-2) /* Failed due to transaction id issue (e.g. xid present/absent when it should be absent/present) */ 55 2887602 : #define FD_FUNK_ERR_KEY (-3) /* Failed due to record key issue (e.g. key present/absent when it should be absent/present) */ 56 98984640 : #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 9705705 : #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 7341168 : #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 2445280278 : ulong seed ) { 144 2445280278 : return (fd_ulong_hash( seed ^ (1UL<<0) ^ k->ul[0] ) ^ fd_ulong_hash( seed ^ (1UL<<1) ^ k->ul[1] ) ) ^ 145 2445280278 : (fd_ulong_hash( seed ^ (1UL<<2) ^ k->ul[2] ) ^ fd_ulong_hash( seed ^ (1UL<<3) ^ k->ul[3] ) ) ^ 146 2445280278 : (fd_ulong_hash( seed ^ (1UL<<4) ^ k->ul[4] ) ); /* tons of ILP */ 147 2445280278 : } 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 1695179274 : fd_funk_rec_key_t const * kb ) { 156 1695179274 : ulong const * a = ka->ul; 157 1695179274 : ulong const * b = kb->ul; 158 1695179274 : return !( ((a[0]^b[0]) | (a[1]^b[1])) | ((a[2]^b[2]) | (a[3]^b[3])) | (a[4]^b[4]) ) ; 159 1695179274 : } 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 662763846 : fd_funk_rec_key_t const * ks ) { 168 662763846 : ulong * d = kd->ul; 169 662763846 : ulong const * s = ks->ul; 170 662763846 : d[0] = s[0]; d[1] = s[1]; d[2] = s[2]; d[3] = s[3]; d[4] = s[4]; 171 662763846 : return kd; 172 662763846 : } 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 3529221540 : ulong seed ) { 184 3529221540 : return ( fd_ulong_hash( seed ^ (1UL<<0) ^ x->ul[0] ) ^ fd_ulong_hash( seed ^ (1UL<<1) ^ x->ul[1] ) ); /* tons of ILP */ 185 3529221540 : } 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 3459494373 : fd_funk_txn_xid_t const * xb ) { 194 3459494373 : ulong const * a = xa->ul; 195 3459494373 : ulong const * b = xb->ul; 196 3459494373 : return !( (a[0]^b[0]) | (a[1]^b[1]) ); 197 3459494373 : } 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 669171780 : fd_funk_txn_xid_t const * xs ) { 206 669171780 : ulong * d = xd->ul; 207 669171780 : ulong const * s = xs->ul; 208 669171780 : d[0] = s[0]; d[1] = s[1]; 209 669171780 : return xd; 210 669171780 : } 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 382165989 : fd_funk_txn_xid_eq_root( fd_funk_txn_xid_t const * x ) { 218 382165989 : ulong const * a = x->ul; 219 382165989 : return !(a[0] | a[1]); 220 382165989 : } 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 221139 : fd_funk_txn_xid_set_root( fd_funk_txn_xid_t * x ) { 228 221139 : ulong * a = x->ul; 229 221139 : a[0] = 0UL; a[1] = 0UL; 230 221139 : return x; 231 221139 : } 232 : 233 : /* fd_funk_xid_key_pair_hash provides a family of hashes that hash a 234 : (xid,key) pair to by p to a uniform quasi-random 64-bit integer. 235 : seed selects the particular hash function to use and can be an 236 : arbitrary 64-bit value. Returns the hash. The hash functions are 237 : high quality but not cryptographically secure. Assumes p is in the 238 : caller's address space and valid. */ 239 : 240 : FD_FN_PURE static inline ulong 241 : fd_funk_xid_key_pair_hash( fd_funk_xid_key_pair_t const * p, 242 2439280278 : ulong seed ) { 243 2439280278 : return fd_funk_txn_xid_hash( p->xid, seed ) ^ fd_funk_rec_key_hash( p->key, seed ); 244 2439280278 : } 245 : 246 : /* fd_funk_xid_key_pair_eq returns 1 if (xid,key) pair pointed to by pa 247 : and pb are equal and 0 otherwise. Assumes pa and pb are in the 248 : caller's address space and valid. */ 249 : 250 : FD_FN_UNUSED FD_FN_PURE static int /* Work around -Winline */ 251 : fd_funk_xid_key_pair_eq( fd_funk_xid_key_pair_t const * pa, 252 1091751135 : fd_funk_xid_key_pair_t const * pb ) { 253 1091751135 : return fd_funk_txn_xid_eq( pa->xid, pb->xid ) & fd_funk_rec_key_eq( pa->key, pb->key ); 254 1091751135 : } 255 : 256 : /* fd_funk_xid_key_pair_copy copies the (xid,key) pair pointed to by ps 257 : into the (xid,key) pair to by pd and returns pd. Assumes pd and ps 258 : are in the caller's address space and valid. */ 259 : 260 : static inline fd_funk_xid_key_pair_t * 261 : fd_funk_xid_key_pair_copy( fd_funk_xid_key_pair_t * pd, 262 9478461 : fd_funk_xid_key_pair_t const * ps ) { 263 9478461 : fd_funk_txn_xid_copy( pd->xid, ps->xid ); 264 9478461 : fd_funk_rec_key_copy( pd->key, ps->key ); 265 9478461 : return pd; 266 9478461 : } 267 : 268 : /* fd_funk_xid_key_pair_init set the (xid,key) pair p to pair formed 269 : from the transaction id pointed to by x and the record key pointed to 270 : by k. Assumes p, x and k are in the caller's address space and 271 : valid. */ 272 : 273 : static inline fd_funk_xid_key_pair_t * 274 : fd_funk_xid_key_pair_init( fd_funk_xid_key_pair_t * p, 275 : fd_funk_txn_xid_t const * x, 276 650285385 : fd_funk_rec_key_t const * k ) { 277 650285385 : fd_funk_txn_xid_copy( p->xid, x ); 278 650285385 : fd_funk_rec_key_copy( p->key, k ); 279 650285385 : return p; 280 650285385 : } 281 : 282 : /* fd_funk_strerror converts an FD_FUNK_SUCCESS / FD_FUNK_ERR_* code 283 : into a human readable cstr. The lifetime of the returned pointer is 284 : infinite. The returned pointer is always to a non-NULL cstr. */ 285 : 286 : FD_FN_CONST char const * 287 : fd_funk_strerror( int err ); 288 : 289 : /* TODO: Consider renaming transaction/txn to update (too much typing)? 290 : upd (probably too similar to UDP) node? block? blk? state? commit? 291 : ... to reduce naming collisions with terminology in use elsewhere? 292 : 293 : TODO: Consider fine tuning {REC,TXN}_{ALIGN,FOOTPRINT} to balance 294 : application use cases with in memory packing with AVX / CPU cache 295 : friendly accelerability. Likewise, virtually everything in here can 296 : be AVX accelerated if desired. E.g. 8 uint hash in parallel then an 297 : 8 wide xor lane reduction tree in hash? 298 : 299 : TODO: Consider letting the user provide alternatives for record and 300 : transaction hashes at compile time (e.g. ids in blockchain apps are 301 : often already crypto secure hashes in which case x->ul[0] ^ seed is 302 : just as good theoretically and faster practically). */ 303 : 304 : FD_PROTOTYPES_END 305 : 306 : #endif /* HEADER_fd_src_funk_fd_funk_base_h */
