LCOV - code coverage report
Current view: top level - funk - fd_funk_base.h (source / functions) Hit Total Coverage
Test: cov.lcov Lines: 64 86 74.4 %
Date: 2025-07-01 05:00:49 Functions: 32 2220 1.4 %

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

Generated by: LCOV version 1.14