Line data    Source code

       1             : #ifndef HEADER_fd_src_funk_fd_funkier_base_h
       2             : #define HEADER_fd_src_funk_fd_funkier_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_funkier_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_FUNKIER_SUCCESS is used by various APIs to indicate the operation
      49             :    successfully completed.  This will be 0.  FD_FUNKIER_ERR_* gives a
      50             :    number of error codes used by fd_funk APIs.  These will be negative
      51             :    integers. */
      52             : 
      53           0 : #define FD_FUNKIER_SUCCESS    (0)  /* Success */
      54           0 : #define FD_FUNKIER_ERR_INVAL  (-1) /* Failed due to obviously invalid inputs */
      55           0 : #define FD_FUNKIER_ERR_XID    (-2) /* Failed due to transaction id issue (e.g. xid present/absent when it should be absent/present) */
      56           0 : #define FD_FUNKIER_ERR_KEY    (-3) /* Failed due to record key issue (e.g. key present/absent when it should be absent/present) */
      57           0 : #define FD_FUNKIER_ERR_FROZEN (-4) /* Failed due to frozen issue (e.g. attempt to change records in a frozen transaction) */
      58           0 : #define FD_FUNKIER_ERR_TXN    (-5) /* Failed due to transaction map issue (e.g. funk txn_max too small) */
      59           0 : #define FD_FUNKIER_ERR_REC    (-6) /* Failed due to record map issue (e.g. funk rec_max too small) */
      60           0 : #define FD_FUNKIER_ERR_MEM    (-7) /* Failed due to wksp issue (e.g. wksp too small) */
      61           0 : #define FD_FUNKIER_ERR_SYS    (-8) /* Failed system call (e.g. a file write) */
      62             : 
      63             : /* FD_FUNKIER_REC_KEY_{ALIGN,FOOTPRINT} describe the alignment and
      64             :    footprint of a fd_funkier_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_FUNKIER_REC_KEY_ALIGN     (8UL)
      69             : #define FD_FUNKIER_REC_KEY_FOOTPRINT (40UL) /* 32 byte hash + 8 byte meta */
      70             : 
      71             : /* A fd_funkier_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_FUNKIER_REC_KEY_FOOTPRINT and the characters c[i] for i
      74             :    in [strlen(cstr),FD_FUNKIER_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_FUNKIER_REC_KEY_ALIGN))) fd_funkier_rec_key {
      79             :   char  c [ FD_FUNKIER_REC_KEY_FOOTPRINT ];
      80             :   uchar uc[ FD_FUNKIER_REC_KEY_FOOTPRINT ];
      81             :   ulong ul[ FD_FUNKIER_REC_KEY_FOOTPRINT / sizeof(ulong) ];
      82             : };
      83             : 
      84             : typedef union fd_funkier_rec_key fd_funkier_rec_key_t;
      85             : 
      86             : /* FD_FUNKIER_TXN_XID_{ALIGN,FOOTPRINT} describe the alignment and
      87             :    footprint of a fd_funkier_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_FUNKIER_TXN_XID_ALIGN     (8UL)
      92             : #define FD_FUNKIER_TXN_XID_FOOTPRINT (16UL)
      93             : 
      94             : /* A fd_funkier_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_FUNKIER_TXN_XID_FOOTPRINT and characters c[i] for i
      98             :    in [strlen(cstr),FD_FUNKIER_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_FUNKIER_TXN_XID_ALIGN))) fd_funkier_txn_xid {
     104             :   char  c [ FD_FUNKIER_TXN_XID_FOOTPRINT ];
     105             :   uchar uc[ FD_FUNKIER_TXN_XID_FOOTPRINT ];
     106             :   ulong ul[ FD_FUNKIER_TXN_XID_FOOTPRINT / sizeof(ulong) ];
     107             : };
     108             : 
     109             : typedef union fd_funkier_txn_xid fd_funkier_txn_xid_t;
     110             : 
     111             : /* FD_FUNKIER_XID_KEY_PAIR_{ALIGN,FOOTPRINT} describe the alignment and
     112             :    footprint of a fd_funkier_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_FUNKIER_XID_KEY_PAIR_ALIGN     (8UL)
     117             : #define FD_FUNKIER_XID_KEY_PAIR_FOOTPRINT (56UL)
     118             : 
     119             : /* A fd_funkier_xid_key_pair_t identifies a funk record.  It is just
     120             :    xid and key packed into the same structure. */
     121             : 
     122             : struct fd_funkier_xid_key_pair {
     123             :   fd_funkier_txn_xid_t xid[1];
     124             :   fd_funkier_rec_key_t key[1];
     125             : };
     126             : 
     127             : typedef struct fd_funkier_xid_key_pair fd_funkier_xid_key_pair_t;
     128             : 
     129             : /* A fd_funkier_t * is an opaque handle of a local join to a funk instance */
     130             : 
     131             : struct fd_funkier_private;
     132             : typedef struct fd_funkier_private fd_funkier_t;
     133             : 
     134             : FD_PROTOTYPES_BEGIN
     135             : 
     136             : /* fd_funkier_rec_key_hash provides a family of hashes that hash the key
     137             :    pointed to by k to a uniform quasi-random 64-bit integer.  seed
     138             :    selects the particular hash function to use and can be an arbitrary
     139             :    64-bit value.  Returns the hash.  The hash functions are high quality
     140             :    but not cryptographically secure.  Assumes k is in the caller's
     141             :    address space and valid. */
     142             : 
     143             : FD_FN_UNUSED FD_FN_PURE static ulong /* Workaround -Winline */
     144             : fd_funkier_rec_key_hash( fd_funkier_rec_key_t const * k,
     145           0 :                          ulong                     seed ) {
     146           0 :   return (fd_ulong_hash( seed ^ (1UL<<0) ^ k->ul[0] ) ^ fd_ulong_hash( seed ^ (1UL<<1) ^ k->ul[1] ) ) ^
     147           0 :          (fd_ulong_hash( seed ^ (1UL<<2) ^ k->ul[2] ) ^ fd_ulong_hash( seed ^ (1UL<<3) ^ k->ul[3] ) ) ^
     148           0 :          (fd_ulong_hash( seed ^ (1UL<<4) ^ k->ul[4] ) ); /* tons of ILP */
     149           0 : }
     150             : 
     151             : /* fd_funkier_rec_key_eq returns 1 if keys pointed to by ka and kb are
     152             :    equal and 0 otherwise.  Assumes ka and kb are in the caller's address
     153             :    space and valid. */
     154             : 
     155             : FD_FN_UNUSED FD_FN_PURE static int /* Workaround -Winline */
     156             : fd_funkier_rec_key_eq( fd_funkier_rec_key_t const * ka,
     157           0 :                        fd_funkier_rec_key_t const * kb ) {
     158           0 :   ulong const * a = ka->ul;
     159           0 :   ulong const * b = kb->ul;
     160           0 :   return !( ((a[0]^b[0]) | (a[1]^b[1])) | ((a[2]^b[2]) | (a[3]^b[3])) | (a[4]^b[4]) ) ;
     161           0 : }
     162             : 
     163             : /* fd_funkier_rec_key_copy copies the key pointed to by ks into the key
     164             :    pointed to by kd and returns kd.  Assumes kd and ks are in the
     165             :    caller's address space and valid. */
     166             : 
     167             : static inline fd_funkier_rec_key_t *
     168             : fd_funkier_rec_key_copy( fd_funkier_rec_key_t *       kd,
     169           0 :                          fd_funkier_rec_key_t const * ks ) {
     170           0 :   ulong *       d = kd->ul;
     171           0 :   ulong const * s = ks->ul;
     172           0 :   d[0] = s[0]; d[1] = s[1]; d[2] = s[2]; d[3] = s[3]; d[4] = s[4];
     173           0 :   return kd;
     174           0 : }
     175             : 
     176             : /* fd_funkier_txn_xid_hash provides a family of hashes that hash the xid
     177             :    pointed to by x to a uniform quasi-random 64-bit integer.  seed
     178             :    selects the particular hash function to use and can be an arbitrary
     179             :    64-bit value.  Returns the hash.  The hash functions are high quality
     180             :    but not cryptographically secure.  Assumes x is in the caller's
     181             :    address space and valid. */
     182             : 
     183             : FD_FN_UNUSED FD_FN_PURE static ulong /* Work around -Winline */
     184             : fd_funkier_txn_xid_hash( fd_funkier_txn_xid_t const * x,
     185           0 :                          ulong                     seed ) {
     186           0 :   return ( fd_ulong_hash( seed ^ (1UL<<0) ^ x->ul[0] ) ^ fd_ulong_hash( seed ^ (1UL<<1) ^ x->ul[1] ) ); /* tons of ILP */
     187           0 : }
     188             : 
     189             : /* fd_funkier_txn_xid_eq returns 1 if transaction id pointed to by xa and
     190             :    xb are equal and 0 otherwise.  Assumes xa and xb are in the caller's
     191             :    address space and valid. */
     192             : 
     193             : FD_FN_PURE static inline int
     194             : fd_funkier_txn_xid_eq( fd_funkier_txn_xid_t const * xa,
     195           0 :                        fd_funkier_txn_xid_t const * xb ) {
     196           0 :   ulong const * a = xa->ul;
     197           0 :   ulong const * b = xb->ul;
     198           0 :   return !( (a[0]^b[0]) | (a[1]^b[1]) );
     199           0 : }
     200             : 
     201             : /* fd_funkier_txn_xid_copy copies the transaction id pointed to by xs into
     202             :    the transaction id pointed to by xd and returns xd.  Assumes xd and
     203             :    xs are in the caller's address space and valid. */
     204             : 
     205             : static inline fd_funkier_txn_xid_t *
     206             : fd_funkier_txn_xid_copy( fd_funkier_txn_xid_t *       xd,
     207           0 :                          fd_funkier_txn_xid_t const * xs ) {
     208           0 :   ulong *       d = xd->ul;
     209           0 :   ulong const * s = xs->ul;
     210           0 :   d[0] = s[0]; d[1] = s[1];
     211           0 :   return xd;
     212           0 : }
     213             : 
     214             : /* fd_funkier_txn_xid_eq_root returns 1 if transaction id pointed to by x
     215             :    is the root transaction.  Assumes x is in the caller's address space
     216             :    and valid. */
     217             : 
     218             : FD_FN_PURE static inline int
     219           0 : fd_funkier_txn_xid_eq_root( fd_funkier_txn_xid_t const * x ) {
     220           0 :   ulong const * a = x->ul;
     221           0 :   return !(a[0] | a[1]);
     222           0 : }
     223             : 
     224             : /* fd_funkier_txn_xid_set_root sets transaction id pointed to by x to the
     225             :    root transaction and returns x.  Assumes x is in the caller's address
     226             :    space and valid. */
     227             : 
     228             : static inline fd_funkier_txn_xid_t *
     229           0 : fd_funkier_txn_xid_set_root( fd_funkier_txn_xid_t * x ) {
     230           0 :   ulong * a = x->ul;
     231           0 :   a[0] = 0UL; a[1] = 0UL;
     232           0 :   return x;
     233           0 : }
     234             : 
     235             : /* fd_funkier_xid_key_pair_hash produces a 64-bit hash case for a
     236             :    xid_key_pair. Assumes p is in the caller's address space and valid. */
     237             : 
     238             : FD_FN_PURE static inline ulong
     239             : fd_funkier_xid_key_pair_hash( fd_funkier_xid_key_pair_t const * p,
     240           0 :                               ulong                          seed ) {
     241             :   /* We ignore the xid part of the key because we need all the instances
     242             :      of a given record key to appear in the same hash
     243             :      chain. fd_funkier_rec_query_global depends on this. */
     244           0 :   return fd_funkier_rec_key_hash( p->key, seed );
     245           0 : }
     246             : 
     247             : /* fd_funkier_xid_key_pair_eq returns 1 if (xid,key) pair pointed to by pa
     248             :    and pb are equal and 0 otherwise.  Assumes pa and pb are in the
     249             :    caller's address space and valid. */
     250             : 
     251             : FD_FN_UNUSED FD_FN_PURE static int /* Work around -Winline */
     252             : fd_funkier_xid_key_pair_eq( fd_funkier_xid_key_pair_t const * pa,
     253           0 :                             fd_funkier_xid_key_pair_t const * pb ) {
     254           0 :   return fd_funkier_txn_xid_eq( pa->xid, pb->xid ) & fd_funkier_rec_key_eq( pa->key, pb->key );
     255           0 : }
     256             : 
     257             : /* fd_funkier_xid_key_pair_copy copies the (xid,key) pair pointed to by ps
     258             :    into the (xid,key) pair to by pd and returns pd.  Assumes pd and ps
     259             :    are in the caller's address space and valid. */
     260             : 
     261             : static inline fd_funkier_xid_key_pair_t *
     262             : fd_funkier_xid_key_pair_copy( fd_funkier_xid_key_pair_t *       pd,
     263           0 :                               fd_funkier_xid_key_pair_t const * ps ) {
     264           0 :   fd_funkier_txn_xid_copy( pd->xid, ps->xid );
     265           0 :   fd_funkier_rec_key_copy( pd->key, ps->key );
     266           0 :   return pd;
     267           0 : }
     268             : 
     269             : /* fd_funkier_xid_key_pair_init set the (xid,key) pair p to pair formed
     270             :    from the transaction id pointed to by x and the record key pointed to
     271             :    by k.  Assumes p, x and k are in the caller's address space and
     272             :    valid. */
     273             : 
     274             : static inline fd_funkier_xid_key_pair_t *
     275             : fd_funkier_xid_key_pair_init( fd_funkier_xid_key_pair_t *  p,
     276             :                               fd_funkier_txn_xid_t const * x,
     277           0 :                               fd_funkier_rec_key_t const * k ) {
     278           0 :   fd_funkier_txn_xid_copy( p->xid, x );
     279           0 :   fd_funkier_rec_key_copy( p->key, k );
     280           0 :   return p;
     281           0 : }
     282             : 
     283             : /* fd_funkier_strerror converts an FD_FUNKIER_SUCCESS / FD_FUNKIER_ERR_* code
     284             :    into a human readable cstr.  The lifetime of the returned pointer is
     285             :    infinite.  The returned pointer is always to a non-NULL cstr. */
     286             : 
     287             : FD_FN_CONST char const *
     288             : fd_funkier_strerror( int err );
     289             : 
     290             : /* TODO: Consider renaming transaction/txn to update (too much typing)?
     291             :    upd (probably too similar to UDP) node? block? blk? state? commit?
     292             :    ... to reduce naming collisions with terminology in use elsewhere?
     293             : 
     294             :    TODO: Consider fine tuning {REC,TXN}_{ALIGN,FOOTPRINT} to balance
     295             :    application use cases with in memory packing with AVX / CPU cache
     296             :    friendly accelerability.  Likewise, virtually everything in here can
     297             :    be AVX accelerated if desired.  E.g. 8 uint hash in parallel then an
     298             :    8 wide xor lane reduction tree in hash?
     299             : 
     300             :    TODO: Consider letting the user provide alternatives for record and
     301             :    transaction hashes at compile time (e.g. ids in blockchain apps are
     302             :    often already crypto secure hashes in which case x->ul[0] ^ seed is
     303             :    just as good theoretically and faster practically). */
     304             : 
     305             : FD_PROTOTYPES_END
     306             : 
     307             : #endif /* HEADER_fd_src_funk_fd_funkier_base_h */