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