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 update all funk records for the most recently
42 : published transactions (if it is not frozen) or all transactions
43 : in preparation (if they are not frozen). */
44 :
45 : #include "../util/fd_util.h"
46 : #include "../util/valloc/fd_valloc.h"
47 :
48 : /* FD_FUNK_SUCCESS is used by various APIs to indicate the operation
49 : successfully completed. This will be 0. FD_FUNK_ERR_* gives a
50 : number of error codes used by fd_funk APIs. These will be negative
51 : integers. */
52 :
53 22722261 : #define FD_FUNK_SUCCESS (0) /* Success */
54 3 : #define FD_FUNK_ERR_INVAL (-1) /* Failed due to obviously invalid inputs */
55 3 : #define FD_FUNK_ERR_XID (-2) /* Failed due to transaction id issue (e.g. xid present/absent when it should be absent/present) */
56 24 : #define FD_FUNK_ERR_KEY (-3) /* Failed due to record key issue (e.g. key present/absent when it should be absent/present) */
57 57476949 : #define FD_FUNK_ERR_FROZEN (-4) /* Failed due to frozen issue (e.g. attempt to change records in a frozen transaction) */
58 3 : #define FD_FUNK_ERR_TXN (-5) /* Failed due to transaction map issue (e.g. funk txn_max too small) */
59 199065191 : #define FD_FUNK_ERR_REC (-6) /* Failed due to record map issue (e.g. funk rec_max too small) */
60 3 : #define FD_FUNK_ERR_MEM (-7) /* Failed due to wksp issue (e.g. wksp too small) */
61 0 : #define FD_FUNK_ERR_SYS (-8) /* Failed system call (e.g. a file write) */
62 0 : #define FD_FUNK_ERR_PURIFY (-9) /* fd_funk_purify failed. */
63 :
64 : /* FD_FUNK_REC_KEY_{ALIGN,FOOTPRINT} describe the alignment and
65 : footprint of a fd_funk_rec_key_t. ALIGN is a positive integer power
66 : of 2. FOOTPRINT is a multiple of ALIGN. These are provided to
67 : facilitate compile time declarations. */
68 :
69 : #define FD_FUNK_REC_KEY_ALIGN (8UL)
70 180 : #define FD_FUNK_REC_KEY_FOOTPRINT (40UL) /* 32 byte hash + 8 byte meta */
71 :
72 : /* A fd_funk_rec_key_t identifies a funk record. Compact binary keys
73 : are encouraged but a cstr can be used so long as it has
74 : strlen(cstr)<FD_FUNK_REC_KEY_FOOTPRINT and the characters c[i] for i
75 : in [strlen(cstr),FD_FUNK_REC_KEY_FOOTPRINT) zero. (Also, if encoding
76 : a cstr in a key, recommend using first byte to encode the strlen for
77 : accelerating cstr operations further but this is up to the user.) */
78 :
79 : union __attribute__((aligned(FD_FUNK_REC_KEY_ALIGN))) fd_funk_rec_key {
80 : uchar uc[ FD_FUNK_REC_KEY_FOOTPRINT ];
81 : uint ui[ 10 ];
82 : ulong ul[ 5 ];
83 : };
84 :
85 : typedef union fd_funk_rec_key fd_funk_rec_key_t;
86 :
87 : /* FD_FUNK_TXN_XID_{ALIGN,FOOTPRINT} describe the alignment and
88 : footprint of a fd_funk_txn_xid_t. ALIGN is a positive integer power
89 : of 2. FOOTPRINT is a multiple of ALIGN. These are provided to
90 : facilitate compile time declarations. */
91 :
92 : #define FD_FUNK_TXN_XID_ALIGN (8UL)
93 : #define FD_FUNK_TXN_XID_FOOTPRINT (16UL)
94 :
95 : /* A fd_funk_txn_xid_t identifies a funk transaction currently in
96 : preparation. Compact binary identifiers are encouraged but a cstr
97 : can be used so long as it has
98 : strlen(cstr)<FD_FUNK_TXN_XID_FOOTPRINT and characters c[i] for i
99 : in [strlen(cstr),FD_FUNK_TXN_KEY_FOOTPRINT) zero. (Also, if
100 : encoding a cstr in a transaction id, recommend using first byte to
101 : encode the strlen for accelerating cstr operations even further but
102 : this is more up to the application.) */
103 :
104 : union __attribute__((aligned(FD_FUNK_TXN_XID_ALIGN))) fd_funk_txn_xid {
105 : uchar uc[ FD_FUNK_TXN_XID_FOOTPRINT ];
106 : ulong ul[ FD_FUNK_TXN_XID_FOOTPRINT / sizeof(ulong) ];
107 : };
108 :
109 : typedef union fd_funk_txn_xid fd_funk_txn_xid_t;
110 :
111 : /* FD_FUNK_XID_KEY_PAIR_{ALIGN,FOOTPRINT} describe the alignment and
112 : footprint of a fd_funk_xid_key_pair_t. ALIGN is a positive integer
113 : power of 2. FOOTPRINT is a multiple of ALIGN. These are provided to
114 : facilitate compile time declarations. */
115 :
116 : #define FD_FUNK_XID_KEY_PAIR_ALIGN (8UL)
117 : #define FD_FUNK_XID_KEY_PAIR_FOOTPRINT (56UL)
118 :
119 : /* A fd_funk_xid_key_pair_t identifies a funk record. It is just
120 : xid and key packed into the same structure. */
121 :
122 : struct fd_funk_xid_key_pair {
123 : fd_funk_txn_xid_t xid[1];
124 : fd_funk_rec_key_t key[1];
125 : };
126 :
127 : typedef struct fd_funk_xid_key_pair fd_funk_xid_key_pair_t;
128 :
129 : /* A fd_funk_shmem_t is the top part of a funk object in shared memory. */
130 :
131 : struct fd_funk_shmem_private;
132 : typedef struct fd_funk_shmem_private fd_funk_shmem_t;
133 :
134 : /* A fd_funk_t * is local join handle to a funk instance */
135 :
136 : struct fd_funk_private;
137 : typedef struct fd_funk_private fd_funk_t;
138 :
139 : FD_PROTOTYPES_BEGIN
140 :
141 : /* fd_funk_rec_key_hash provides a family of hashes that hash the key
142 : pointed to by k to a uniform quasi-random 64-bit integer. seed
143 : selects the particular hash function to use and can be an arbitrary
144 : 64-bit value. Returns the hash. The hash functions are high quality
145 : but not cryptographically secure. Assumes k is in the caller's
146 : address space and valid. */
147 :
148 : #if FD_HAS_INT128
149 :
150 : /* If the target supports uint128, fd_funk_rec_key_hash is seeded
151 : xxHash3 with 64-bit output size. (open source BSD licensed) */
152 :
153 : static inline ulong
154 0 : fd_xxh3_mul128_fold64( ulong lhs, ulong rhs ) {
155 0 : uint128 product = (uint128)lhs * (uint128)rhs;
156 0 : return (ulong)product ^ (ulong)( product>>64 );
157 0 : }
158 :
159 : static inline ulong
160 : fd_xxh3_mix16b( ulong i0, ulong i1,
161 : ulong s0, ulong s1,
162 0 : ulong seed ) {
163 0 : return fd_xxh3_mul128_fold64( i0 ^ (s0 + seed), i1 ^ (s1 - seed) );
164 0 : }
165 :
166 : FD_FN_PURE static inline ulong
167 : fd_funk_rec_key_hash1( uchar const key[ 32 ],
168 : ulong rec_type,
169 0 : ulong seed ) {
170 0 : seed ^= rec_type;
171 0 : ulong k0 = FD_LOAD( ulong, key+ 0 );
172 0 : ulong k1 = FD_LOAD( ulong, key+ 8 );
173 0 : ulong k2 = FD_LOAD( ulong, key+16 );
174 0 : ulong k3 = FD_LOAD( ulong, key+24 );
175 0 : ulong acc = 32 * 0x9E3779B185EBCA87ULL;
176 0 : acc += fd_xxh3_mix16b( k0, k1, 0xbe4ba423396cfeb8UL, 0x1cad21f72c81017cUL, seed );
177 0 : acc += fd_xxh3_mix16b( k2, k3, 0xdb979083e96dd4deUL, 0x1f67b3b7a4a44072UL, seed );
178 0 : acc = acc ^ (acc >> 37);
179 0 : acc *= 0x165667919E3779F9ULL;
180 0 : acc = acc ^ (acc >> 32);
181 0 : return acc;
182 0 : }
183 :
184 : FD_FN_PURE static inline ulong
185 : fd_funk_rec_key_hash( fd_funk_rec_key_t const * k,
186 531463735 : ulong seed ) {
187 531463735 : seed ^= k->ul[4];
188 : /* tons of ILP */
189 531463735 : return (fd_ulong_hash( seed ^ (1UL<<0) ^ k->ul[0] ) ^ fd_ulong_hash( seed ^ (1UL<<1) ^ k->ul[1] ) ) ^
190 531463735 : (fd_ulong_hash( seed ^ (1UL<<2) ^ k->ul[2] ) ^ fd_ulong_hash( seed ^ (1UL<<3) ^ k->ul[3] ) );
191 531463735 : }
192 :
193 : #else
194 :
195 : /* If the target does not support xxHash3, fallback to the 'old' funk
196 : key hash function.
197 :
198 : FIXME This version is vulnerable to HashDoS */
199 :
200 : FD_FN_PURE static inline ulong
201 : fd_funk_rec_key_hash1( uchar const key[ 32 ],
202 : ulong rec_type,
203 : ulong seed ) {
204 : seed ^= rec_type;
205 : /* tons of ILP */
206 : return (fd_ulong_hash( seed ^ (1UL<<0) ^ FD_LOAD( ulong, key+ 0 ) ) ^
207 : fd_ulong_hash( seed ^ (1UL<<1) ^ FD_LOAD( ulong, key+ 8 ) ) ) ^
208 : (fd_ulong_hash( seed ^ (1UL<<2) ^ FD_LOAD( ulong, key+16 ) ) ^
209 : fd_ulong_hash( seed ^ (1UL<<3) ^ FD_LOAD( ulong, key+24 ) ) );
210 : }
211 :
212 : FD_FN_PURE static inline ulong
213 : fd_funk_rec_key_hash( fd_funk_rec_key_t const * k,
214 : ulong seed ) {
215 : return fd_funk_rec_key_hash1( k->uc, k->ul[4], seed );
216 : }
217 :
218 : #endif /* FD_HAS_INT128 */
219 :
220 : /* fd_funk_rec_key_eq returns 1 if keys pointed to by ka and kb are
221 : equal and 0 otherwise. Assumes ka and kb are in the caller's address
222 : space and valid. */
223 :
224 : FD_FN_UNUSED FD_FN_PURE static int /* Workaround -Winline */
225 : fd_funk_rec_key_eq( fd_funk_rec_key_t const * ka,
226 1881031104 : fd_funk_rec_key_t const * kb ) {
227 1881031104 : ulong const * a = ka->ul;
228 1881031104 : ulong const * b = kb->ul;
229 1881031104 : return !( ((a[0]^b[0]) | (a[1]^b[1])) | ((a[2]^b[2]) | (a[3]^b[3])) | (a[4]^b[4]) ) ;
230 1881031104 : }
231 :
232 : /* fd_funk_rec_key_copy copies the key pointed to by ks into the key
233 : pointed to by kd and returns kd. Assumes kd and ks are in the
234 : caller's address space and valid. */
235 :
236 : static inline fd_funk_rec_key_t *
237 : fd_funk_rec_key_copy( fd_funk_rec_key_t * kd,
238 509395145 : fd_funk_rec_key_t const * ks ) {
239 509395145 : ulong * d = kd->ul;
240 509395145 : ulong const * s = ks->ul;
241 509395145 : d[0] = s[0]; d[1] = s[1]; d[2] = s[2]; d[3] = s[3]; d[4] = s[4];
242 509395145 : return kd;
243 509395145 : }
244 :
245 : /* fd_funk_txn_xid_hash provides a family of hashes that hash the xid
246 : pointed to by x to a uniform quasi-random 64-bit integer. seed
247 : selects the particular hash function to use and can be an arbitrary
248 : 64-bit value. Returns the hash. The hash functions are high quality
249 : but not cryptographically secure. Assumes x is in the caller's
250 : address space and valid. */
251 :
252 : FD_FN_UNUSED FD_FN_PURE static ulong /* Work around -Winline */
253 : fd_funk_txn_xid_hash( fd_funk_txn_xid_t const * x,
254 394482213 : ulong seed ) {
255 394482213 : return ( fd_ulong_hash( seed ^ (1UL<<0) ^ x->ul[0] ) ^ fd_ulong_hash( seed ^ (1UL<<1) ^ x->ul[1] ) ); /* tons of ILP */
256 394482213 : }
257 :
258 : /* fd_funk_txn_xid_eq returns 1 if transaction id pointed to by xa and
259 : xb are equal and 0 otherwise. Assumes xa and xb are in the caller's
260 : address space and valid. */
261 :
262 : FD_FN_PURE static inline int
263 : fd_funk_txn_xid_eq( fd_funk_txn_xid_t const * xa,
264 2620828600 : fd_funk_txn_xid_t const * xb ) {
265 2620828600 : ulong const * a = xa->ul;
266 2620828600 : ulong const * b = xb->ul;
267 2620828600 : return !( (a[0]^b[0]) | (a[1]^b[1]) );
268 2620828600 : }
269 :
270 : /* fd_funk_txn_xid_copy copies the transaction id pointed to by xs into
271 : the transaction id pointed to by xd and returns xd. Assumes xd and
272 : xs are in the caller's address space and valid. */
273 :
274 : static inline fd_funk_txn_xid_t *
275 : fd_funk_txn_xid_copy( fd_funk_txn_xid_t * xd,
276 299068740 : fd_funk_txn_xid_t const * xs ) {
277 299068740 : ulong * d = xd->ul;
278 299068740 : ulong const * s = xs->ul;
279 299068740 : d[0] = s[0]; d[1] = s[1];
280 299068740 : return xd;
281 299068740 : }
282 :
283 : /* fd_funk_txn_xid_eq_root returns 1 if transaction id pointed to by x
284 : is the root transaction. Assumes x is in the caller's address space
285 : and valid. */
286 :
287 : FD_FN_PURE static inline int
288 120657237 : fd_funk_txn_xid_eq_root( fd_funk_txn_xid_t const * x ) {
289 120657237 : ulong const * a = x->ul;
290 120657237 : return !(a[0] | a[1]);
291 120657237 : }
292 :
293 : /* fd_funk_txn_xid_set_root sets transaction id pointed to by x to the
294 : root transaction and returns x. Assumes x is in the caller's address
295 : space and valid. */
296 :
297 : static inline fd_funk_txn_xid_t *
298 214586094 : fd_funk_txn_xid_set_root( fd_funk_txn_xid_t * x ) {
299 214586094 : ulong * a = x->ul;
300 214586094 : a[0] = 0UL; a[1] = 0UL;
301 214586094 : return x;
302 214586094 : }
303 :
304 : /* fd_funk_xid_key_pair_hash produces a 64-bit hash case for a
305 : xid_key_pair. Assumes p is in the caller's address space and valid. */
306 :
307 : FD_FN_PURE static inline ulong
308 : fd_funk_xid_key_pair_hash( fd_funk_xid_key_pair_t const * p,
309 525463735 : ulong seed ) {
310 : /* We ignore the xid part of the key because we need all the instances
311 : of a given record key to appear in the same hash
312 : chain. fd_funk_rec_query_global depends on this. */
313 525463735 : return fd_funk_rec_key_hash( p->key, seed );
314 525463735 : }
315 :
316 : /* fd_funk_xid_key_pair_eq returns 1 if (xid,key) pair pointed to by pa
317 : and pb are equal and 0 otherwise. Assumes pa and pb are in the
318 : caller's address space and valid. */
319 :
320 : FD_FN_UNUSED FD_FN_PURE static int /* Work around -Winline */
321 : fd_funk_xid_key_pair_eq( fd_funk_xid_key_pair_t const * pa,
322 809454576 : fd_funk_xid_key_pair_t const * pb ) {
323 809454576 : return fd_funk_txn_xid_eq( pa->xid, pb->xid ) & fd_funk_rec_key_eq( pa->key, pb->key );
324 809454576 : }
325 :
326 : /* fd_funk_xid_key_pair_copy copies the (xid,key) pair pointed to by ps
327 : into the (xid,key) pair to by pd and returns pd. Assumes pd and ps
328 : are in the caller's address space and valid. */
329 :
330 : static inline fd_funk_xid_key_pair_t *
331 : fd_funk_xid_key_pair_copy( fd_funk_xid_key_pair_t * pd,
332 3000000 : fd_funk_xid_key_pair_t const * ps ) {
333 3000000 : fd_funk_txn_xid_copy( pd->xid, ps->xid );
334 3000000 : fd_funk_rec_key_copy( pd->key, ps->key );
335 3000000 : return pd;
336 3000000 : }
337 :
338 : /* fd_funk_xid_key_pair_init set the (xid,key) pair p to pair formed
339 : from the transaction id pointed to by x and the record key pointed to
340 : by k. Assumes p, x and k are in the caller's address space and
341 : valid. */
342 :
343 : static inline fd_funk_xid_key_pair_t *
344 : fd_funk_xid_key_pair_init( fd_funk_xid_key_pair_t * p,
345 : fd_funk_txn_xid_t const * x,
346 5008626 : fd_funk_rec_key_t const * k ) {
347 5008626 : fd_funk_txn_xid_copy( p->xid, x );
348 5008626 : fd_funk_rec_key_copy( p->key, k );
349 5008626 : return p;
350 5008626 : }
351 :
352 : /* fd_funk_strerror converts an FD_FUNK_SUCCESS / FD_FUNK_ERR_* code
353 : into a human readable cstr. The lifetime of the returned pointer is
354 : infinite. The returned pointer is always to a non-NULL cstr. */
355 :
356 : FD_FN_CONST char const *
357 : fd_funk_strerror( int err );
358 :
359 : /* TODO: Consider renaming transaction/txn to update (too much typing)?
360 : upd (probably too similar to UDP) node? block? blk? state? commit?
361 : ... to reduce naming collisions with terminology in use elsewhere?
362 :
363 : TODO: Consider fine tuning {REC,TXN}_{ALIGN,FOOTPRINT} to balance
364 : application use cases with in memory packing with AVX / CPU cache
365 : friendly accelerability. Likewise, virtually everything in here can
366 : be AVX accelerated if desired. E.g. 8 uint hash in parallel then an
367 : 8 wide xor lane reduction tree in hash?
368 :
369 : TODO: Consider letting the user provide alternatives for record and
370 : transaction hashes at compile time (e.g. ids in blockchain apps are
371 : often already crypto secure hashes in which case x->ul[0] ^ seed is
372 : just as good theoretically and faster practically). */
373 :
374 : FD_PROTOTYPES_END
375 :
376 : #endif /* HEADER_fd_src_funk_fd_funk_base_h */
|
