LCOV - code coverage report
Current view: top level - disco/store - fd_store.h (source / functions) Hit Total Coverage
Test: cov.lcov Lines: 54 87 62.1 %
Date: 2025-10-13 04:42:14 Functions: 25 375 6.7 %

          Line data    Source code
       1             : #ifndef HEADER_fd_src_discof_repair_fd_store_h
       2             : #define HEADER_fd_src_discof_repair_fd_store_h
       3             : 
       4             : /* fd_store is a high-performance in-memory storage engine for shreds as
       5             :    they are received from the network.
       6             : 
       7             :    The elements in the store themselves are not shreds, but FEC set
       8             :    payloads.  Briefly, FEC sets are groupings of shreds that encode the
       9             :    same data but provide redundancy and security.  While Firedancer
      10             :    receives individual shreds over Turbine / Repair (the relevant Solana
      11             :    protocols), a lot of Firedancer's validation of those shreds can only
      12             :    be done at the FEC set boundary.  Also, there are potential future
      13             :    protocol changes to encode all shreds in a FEC set so that they can
      14             :    only be decoded once the entire FEC set is received ("all-coding").
      15             : 
      16             :    Therefore, the FEC set becomes the logical unit for the store vs.
      17             :    individual shreds.  Replay will only ever attempt replay of a FEC set
      18             :    so there is no need to store at the granularity of individual shreds.
      19             :    The store is essentially a mapping of merkle root->FEC set payload,
      20             :    in which the merkle root was produced by feeding every shred in a FEC
      21             :    set into a merkle tree.  This uniquely identifies a FEC set, because
      22             :    if any of the shreds change, the merkle root changes.
      23             : 
      24             :    Shreds are coalesced and inserted into the store as bytes.  The max
      25             :    bytes per FEC set is currently variable-length but capped at 63985.
      26             :    In the future this will be fixed to 31840 bytes, when FEC sets are
      27             :    enforced to always be 32 shreds.
      28             : 
      29             :    The shared memory used by a store instance is within a workspace such
      30             :    that it is also persistent and remotely inspectable.  Store is
      31             :    designed to be used inter-process (allowing concurrent joins from
      32             :    multiple tiles), relocated in memory (via wksp operations), and
      33             :    accessed concurrently (managing conflicts with a lock).
      34             : 
      35             :    EQUIVOCATION
      36             : 
      37             :    There is a protocol violation called equivocation (also known as
      38             :    "duplicates") that results in two or more blocks for the same slot.
      39             :    The actual conflict occurs at the shred level: a leader produces two
      40             :    or more shreds for the same slot at the same index, with different
      41             :    data payloads.  The result will be two different FEC sets for the
      42             :    same "logical" FEC set based on (slot, fec_set_idx).
      43             : 
      44             :    Unfortunately a naive keying scheme such as (slot, fec_set_idx) is
      45             :    insufficient as a result of equivocation.  As mentioned earlier,
      46             :    Store instead uses the merkle root as the key for its FEC set
      47             :    elements, at the cost of some keying performance and complexity.
      48             : 
      49             :    ARCHITECTURE
      50             : 
      51             :    In the Firedancer topology, Shred tile writes to store and Replay
      52             :    tile reads from store.  Replay tile only reads from the store after
      53             :    Repair tile (which is downstream of Shred) has notified Replay that a
      54             :    FEC set is ready.  Shred's writes are append-only and Replay is
      55             :    responsible for publishing once it is done consuming (signaled by a
      56             :    new Tower root).
      57             : 
      58             :    Shred (writes) -> Repair (notif) -> Replay (reads, publishes)
      59             : 
      60             :    ORDERING
      61             : 
      62             :    In the above architecture, Repair delivers FEC sets to Replay in
      63             :    partial order.  Any given fork will be delivered in-order, but
      64             :    concurrent forks can be delivered in arbitrary order.  Another way to
      65             :    phrase this is a parent FEC set will always be delivered before the
      66             :    child (see fd_reasm).
      67             : 
      68             :    CONCURRENCY
      69             : 
      70             :    It is possible to design Store access in a way that enables parallel
      71             :    writes and minimizes lock contention between readers and writers.
      72             :    Store contains a fd_rwlock (read-write lock), but the name is a bit
      73             :    of a misnomer because writes can actually be concurrent and the only
      74             :    operation that will actually need the write lock is publish, which
      75             :    will be done by Replay.  It is more appropriate to describe as an
      76             :    exclusive-shared access lock.
      77             : 
      78             :    In this design, writers (Shred tiles) hold the shared lock during
      79             :    their access.  The reader (Replay tile) also holds the shared lock
      80             :    during its access, and given both Shred and Replay will be taking out
      81             :    shared locks, they will not contend.
      82             : 
      83             :    For parallel writes, the Store's hash function is carefully designed
      84             :    to partition the keyspace so that the same Shred tile always writes
      85             :    to the same map slots.  This ensures map collisions always happen on
      86             :    the same Shred tile and cannot happen across tiles.  Specifically, if
      87             :    two different FEC sets hash to the same slot, it is guaranteed that
      88             :    to be the same Shred tile processing both those FEC sets.  This
      89             :    prevents a data race in which multiple Shred tiles (each with a
      90             :    handle to the shared lock) write to the same map slot.
      91             : 
      92             :    The hash function is defined as follows:
      93             :    ```
      94             :    #define MAP_KEY_HASH(key,seed) ((ulong)key->mr.ul[0]%seed + (key)->part*seed)
      95             :    ```
      96             :    where `key` is a key type that includes the merkle root (32 bytes)
      97             :    and the partition index (8 bytes) that is equivalent to the Shred
      98             :    tile index doing the insertion.  seed, on initialization, is the
      99             :    number of chains/buckets in the map_chain divided by the number of
     100             :    partitions.  In effect, seed is the size of each partition.  For
     101             :    example, if the map_chain is sized to 1024, and there are 4 shred
     102             :    tiles, then the seed is 1024/4 = 256.  Then the map key hash can
     103             :    bound the chain index of each partition as such: shred tile 0 will
     104             :    write to chains 0-255, shred tile 1 will write to chains 256-511,
     105             :    shred tile 2 will write to chains 512-767, and shred tile 3 will
     106             :    write to chains 768-1023, without overlap.  The merkle root is a 32
     107             :    byte SHA-256 hash, so we can expect a fairly uniform distribution of
     108             :    hash values even after truncating to the first 8 bytes, without
     109             :    needing to introduce more randomness.  Thus we can repurpose the
     110             :    `seed` argument to be the number of partitions.
     111             : 
     112             :    Essentially, this allows for limited single-producer single-consumer
     113             :    (SPSC) concurrency, where the producer is a given Shred tile and the
     114             :    consumer is Replay tile.  The SPSC concurrency is limited in that the
     115             :    Store should 1. only be read by Replay after Repair has notified
     116             :    Replay it is time to read (ie. Shred has finished writing), and 2. be
     117             :    written to by Shred(s) in append-only fashion, so Shred never
     118             :    modifies or removes from the map.  Store is backed by fd_map_chain,
     119             :    which is not thread-safe generally, but does support this particular
     120             :    SPSC concurrency model in cases where the consumer is guaranteed to
     121             :    be lagging the producer.
     122             : 
     123             :    Analyzing fd_map_chain in gory detail, in the case of a map collision
     124             :    where Replay tile is reading an element and Shred tile writes a new
     125             :    element to the same map slot, that new element is prepended to the
     126             :    hash chain within that slot (which modifies what the head of the
     127             :    chain points to as well as the now-previous head in the hash chain's
     128             :    `.next` field, but does not touch application data).  With fencing
     129             :    enabled (MAP_INSERT_FENCE), it is guaranteed the consumer either
     130             :    reads the head before or after the update.  If it reads before, that
     131             :    is safe, it would just check the key (if no match, iterate down the
     132             :    chain etc.)  If it reads after, it is also safe because the new
     133             :    element is guaranteed to be before the old element in the chain, so
     134             :    it would just do one more iteration.  Note the consumer should always
     135             :    use fd_store_query_const to ensure the underlying fd_map_chain is not
     136             :    modified during querying.
     137             : 
     138             :    The exception to the above is publishing.  Publishing requires
     139             :    exclusive access because it involves removing from fd_map_chain,
     140             :    which is not safe for shared access.  So the Replay tile should take
     141             :    out the exclusive lock.  Publishing happens at most once per slot, so
     142             :    it is a relatively infrequent Store access compared to FEC queries
     143             :    and inserts (which is good because it is also the most expensive). */
     144             : 
     145             : #include "../../flamenco/fd_rwlock.h"
     146             : #include "../../flamenco/types/fd_types_custom.h"
     147             : #include "../../util/hist/fd_histf.h"
     148             : 
     149             : /* FD_STORE_USE_HANDHOLDING:  Define this to non-zero at compile time
     150             :    to turn on additional runtime checks and logging. */
     151             : 
     152             : #ifndef FD_STORE_USE_HANDHOLDING
     153             : #define FD_STORE_USE_HANDHOLDING 1
     154             : #endif
     155             : 
     156             : /* FD_STORE_ALIGN specifies the alignment needed for store.  ALIGN is
     157             :    double x86 cache line to mitigate various kinds of false sharing (eg.
     158             :    ACLPF adjacent cache line prefetch). */
     159             : 
     160             : #define FD_STORE_ALIGN (128UL)
     161             : 
     162             : /* FD_STORE_MAGIC is a magic number for detecting store corruption. */
     163             : 
     164           9 : #define FD_STORE_MAGIC (0xf17eda2ce75702e0UL) /* firedancer store version 0 */
     165             : 
     166             : /* FD_STORE_DATA_MAX defines a constant for the maximum size of a FEC
     167             :    set payload.  The value is computed from the maximum number
     168             :    of shreds in a FEC set * the payload bytes per shred.
     169             : 
     170             :    67 shreds per FEC set * 955 payloads per shred = 63985 bytes max. */
     171             : 
     172           0 : #define FD_STORE_DATA_MAX (63985UL) /* TODO fixed-32 */
     173             : 
     174             : /* fd_store_fec describes a store element (FEC set).  The pointer fields
     175             :    implement a left-child, right-sibling n-ary tree. */
     176             : 
     177             : struct __attribute__((packed)) fd_store_key {
     178             :    fd_hash_t mr;
     179             :    ulong     part; /* partition index of the inserter */
     180             : };
     181             : typedef struct fd_store_key fd_store_key_t;
     182             : 
     183             : struct __attribute__((aligned(FD_STORE_ALIGN))) fd_store_fec {
     184             : 
     185             :   /* Keys */
     186             : 
     187             :   fd_store_key_t key; /* map key, merkle root of the FEC set + a partition index */
     188             :   fd_hash_t cmr;      /* parent's map key, chained merkle root of the FEC set */
     189             : 
     190             :   /* Pointers.  These are internal to the store and callers should not
     191             :                 interface with them directly. */
     192             : 
     193             :   ulong next;    /* reserved for internal use by fd_pool, fd_map_chain */
     194             :   ulong parent;  /* pool idx of the parent */
     195             :   ulong child;   /* pool idx of the left-child */
     196             :   ulong sibling; /* pool idx of the right-sibling */
     197             : 
     198             :   /* Data */
     199             : 
     200             :   ulong data_sz;                 /* TODO fixed-32. sz of the FEC set payload, guaranteed < FD_STORE_DATA_MAX */
     201             :   uchar data[FD_STORE_DATA_MAX]; /* FEC set payload = coalesced data shreds (byte array) */
     202             : };
     203             : typedef struct fd_store_fec fd_store_fec_t;
     204             : 
     205             : #define POOL_NAME  fd_store_pool
     206         507 : #define POOL_ELE_T fd_store_fec_t
     207             : #include "../../util/tmpl/fd_pool_para.c"
     208             : 
     209             : #define MAP_NAME               fd_store_map
     210             : #define MAP_ELE_T              fd_store_fec_t
     211             : #define MAP_KEY_T              fd_store_key_t
     212          51 : #define MAP_KEY                key
     213         540 : #define MAP_KEY_EQ(k0,k1)      (!memcmp((k0),(k1), sizeof(fd_hash_t)))
     214         477 : #define MAP_KEY_HASH(key,seed) ((ulong)key->mr.ul[0]%seed + (key)->part*seed) /* See documentation above for the hash function */
     215             : #define MAP_INSERT_FENCE       1
     216             : #include "../../util/tmpl/fd_map_chain.c"
     217             : 
     218             : struct fd_store {
     219             :   ulong magic;       /* ==FD_STORE_MAGIC */
     220             :   ulong fec_max;     /* max number of FEC sets that can be stored */
     221             :   ulong part_cnt;    /* number of partitions, also the number of writers */
     222             :   ulong root;        /* pool idx of the root */
     223             :   ulong slot0;       /* FIXME this hack is needed until the block_id is in the bank (manifest) */
     224             :   ulong store_gaddr; /* wksp gaddr of store in the backing wksp, non-zero gaddr */
     225             :   ulong map_gaddr;   /* wksp gaddr of map of fd_store_key->fd_store_fec */
     226             :   ulong pool_mem_gaddr; /* wksp gaddr of shmem_t object in pool_para */
     227             :   ulong pool_ele_gaddr; /* wksp gaddr of first ele_t object in pool_para */
     228             :   fd_rwlock_t lock; /* rwlock for concurrent access */
     229             : };
     230             : typedef struct fd_store fd_store_t;
     231             : 
     232             : FD_PROTOTYPES_BEGIN
     233             : 
     234             : /* Constructors */
     235             : 
     236             : /* fd_store_{align,footprint} return the required alignment and
     237             :    footprint of a memory region suitable for use as store with up to
     238             :    fec_max elements.  fec_max is an integer power-of-two. */
     239             : 
     240             : FD_FN_CONST static inline ulong
     241         111 : fd_store_align( void ) {
     242         111 :   return alignof(fd_store_t);
     243         111 : }
     244             : 
     245             : FD_FN_CONST static inline ulong
     246          21 : fd_store_footprint( ulong fec_max ) {
     247          21 :   if( FD_UNLIKELY( !fd_ulong_is_pow2( fec_max ) ) ) return 0UL;
     248          21 :   return FD_LAYOUT_FINI(
     249          21 :     FD_LAYOUT_APPEND(
     250          21 :     FD_LAYOUT_APPEND(
     251          21 :     FD_LAYOUT_APPEND(
     252          21 :     FD_LAYOUT_APPEND(
     253          21 :     FD_LAYOUT_INIT,
     254          21 :       alignof(fd_store_t),     sizeof(fd_store_t)                ),
     255          21 :       fd_store_map_align(),    fd_store_map_footprint( fec_max ) ),
     256          21 :       fd_store_pool_align(),   fd_store_pool_footprint()         ),
     257          21 :       alignof(fd_store_fec_t), sizeof(fd_store_fec_t)*fec_max    ),
     258          21 :     fd_store_align() );
     259          21 : }
     260             : 
     261             : /* fd_store_new formats an unused memory region for use as a store.
     262             :    mem is a non-NULL pointer to this region in the local address space
     263             :    with the required footprint and alignment.  fec_max is an integer
     264             :    power-of-two. */
     265             : 
     266             : void *
     267             : fd_store_new( void * shmem, ulong fec_max, ulong part_cnt );
     268             : 
     269             : /* fd_store_join joins the caller to the store.  store points to the
     270             :    first byte of the memory region backing the store in the caller's
     271             :    address space.
     272             : 
     273             :    Returns a pointer in the local address space to store on success. */
     274             : 
     275             : fd_store_t *
     276             : fd_store_join( void * store );
     277             : 
     278             : /* fd_store_leave leaves a current local join.  Returns a pointer to the
     279             :    underlying shared memory region on success and NULL on failure (logs
     280             :    details).  Reasons for failure include store is NULL. */
     281             : 
     282             : void *
     283             : fd_store_leave( fd_store_t const * store );
     284             : 
     285             : /* fd_store_delete unformats a memory region used as a store.
     286             :    Assumes only the nobody is joined to the region.  Returns a
     287             :    pointer to the underlying shared memory region or NULL if used
     288             :    obviously in error (e.g. store is obviously not a store ... logs
     289             :    details).  The ownership of the memory region is transferred to the
     290             :    caller. */
     291             : 
     292             : void *
     293             : fd_store_delete( void * shstore );
     294             : 
     295             : /* Accessors */
     296             : 
     297             : /* fd_store_wksp returns the local join to the wksp backing the store.
     298             :    The lifetime of the returned pointer is at least as long as the
     299             :    lifetime of the local join.  Assumes store is a current local
     300             :    join. */
     301             : 
     302             : FD_FN_PURE static inline fd_wksp_t *
     303        1734 : fd_store_wksp( fd_store_t const * store ) {
     304        1734 :   return (fd_wksp_t *)( ( (ulong)store ) - store->store_gaddr );
     305        1734 : }
     306             : 
     307             : /* fd_store_pool computes and returns a local join handle to the pool_para. */
     308         666 : FD_FN_PURE static inline fd_store_pool_t fd_store_pool( fd_store_t const * store ) {
     309         666 :    return (fd_store_pool_t){ .pool    = fd_wksp_laddr_fast( fd_store_wksp( store ), store->pool_mem_gaddr ),
     310         666 :                              .ele     = fd_wksp_laddr_fast( fd_store_wksp( store ), store->pool_ele_gaddr ),
     311         666 :                              .ele_max = store->fec_max };
     312         666 : }
     313             : 
     314             : /* fd_store_{map,map_const,fec0,fec0_const,root,root_const} returns a
     315             :    pointer in the caller's address space to the corresponding store
     316             :    field.  const versions for each are also provided. */
     317             : 
     318         168 : FD_FN_PURE static inline fd_store_map_t       * fd_store_map       ( fd_store_t       * store ) { return fd_wksp_laddr_fast( fd_store_wksp( store ), store->map_gaddr );                              }
     319         234 : FD_FN_PURE static inline fd_store_map_t const * fd_store_map_const ( fd_store_t const * store ) { return fd_wksp_laddr_fast( fd_store_wksp( store ), store->map_gaddr );                              }
     320         165 : FD_FN_PURE static inline fd_store_fec_t       * fd_store_fec0      ( fd_store_t       * store ) { fd_store_pool_t pool = fd_store_pool( store ); return pool.ele;                                     }
     321         234 : FD_FN_PURE static inline fd_store_fec_t const * fd_store_fec0_const( fd_store_t const * store ) { fd_store_pool_t pool = fd_store_pool( store ); return pool.ele;                                     }
     322          15 : FD_FN_PURE static inline fd_store_fec_t       * fd_store_root      ( fd_store_t       * store ) { fd_store_pool_t pool = fd_store_pool( store ); return fd_store_pool_ele      ( &pool, store->root); }
     323           3 : FD_FN_PURE static inline fd_store_fec_t const * fd_store_root_const( fd_store_t const * store ) { fd_store_pool_t pool = fd_store_pool( store ); return fd_store_pool_ele_const( &pool, store->root); }
     324             : 
     325             : /* fd_store_{parent,child,sibling} returns a pointer in the caller's
     326             :    address space to the corresponding {parent,left-child,right-sibling}
     327             :    of fec.  Assumes store is a current local join and fec is a valid
     328             :    pointer to a pool element inside store.  const versions for each are
     329             :    also provided. */
     330             : 
     331           0 : FD_FN_PURE static inline fd_store_fec_t       * fd_store_parent       ( fd_store_t       * store, fd_store_fec_t const * fec ) { fd_store_pool_t pool = fd_store_pool( store ); return fd_store_pool_ele      ( &pool, fec->parent  ); }
     332           0 : FD_FN_PURE static inline fd_store_fec_t const * fd_store_parent_const ( fd_store_t const * store, fd_store_fec_t const * fec ) { fd_store_pool_t pool = fd_store_pool( store ); return fd_store_pool_ele_const( &pool, fec->parent  ); }
     333           0 : FD_FN_PURE static inline fd_store_fec_t       * fd_store_child        ( fd_store_t       * store, fd_store_fec_t const * fec ) { fd_store_pool_t pool = fd_store_pool( store ); return fd_store_pool_ele      ( &pool, fec->child   ); }
     334           0 : FD_FN_PURE static inline fd_store_fec_t const * fd_store_child_const  ( fd_store_t const * store, fd_store_fec_t const * fec ) { fd_store_pool_t pool = fd_store_pool( store ); return fd_store_pool_ele_const( &pool, fec->child   ); }
     335           0 : FD_FN_PURE static inline fd_store_fec_t       * fd_store_sibling      ( fd_store_t       * store, fd_store_fec_t const * fec ) { fd_store_pool_t pool = fd_store_pool( store ); return fd_store_pool_ele      ( &pool, fec->sibling ); }
     336           0 : FD_FN_PURE static inline fd_store_fec_t const * fd_store_sibling_const( fd_store_t const * store, fd_store_fec_t const * fec ) { fd_store_pool_t pool = fd_store_pool( store ); return fd_store_pool_ele_const( &pool, fec->sibling ); }
     337             : 
     338             : /* fd_store_{shacq, shrel, exacq, exrel} acquires / releases the shared
     339             :    / exclusive lock.  Callers should typically use the
     340             :    FD_STORE_SHARED_LOCK and FD_STORE_EXCLUSIVE_LOCK macros to acquire
     341             :    and release the lock instead of calling these functions directly. */
     342             : 
     343           0 : FD_FN_PURE static inline void fd_store_shacq( fd_store_t * store ) { fd_rwlock_read   ( &store->lock ); }
     344           0 : FD_FN_PURE static inline void fd_store_shrel( fd_store_t * store ) { fd_rwlock_unread ( &store->lock ); }
     345           0 : FD_FN_PURE static inline void fd_store_exacq( fd_store_t * store ) { fd_rwlock_write  ( &store->lock ); }
     346           0 : FD_FN_PURE static inline void fd_store_exrel( fd_store_t * store ) { fd_rwlock_unwrite( &store->lock ); }
     347             : 
     348             : struct fd_store_lock_ctx {
     349             :   fd_store_t * store_;
     350             :   long       * acq_start;
     351             :   long       * acq_end;
     352             :   long       * work_end;
     353             : };
     354             : 
     355             : static inline void
     356           0 : fd_store_shared_lock_cleanup( struct fd_store_lock_ctx * ctx ) { *(ctx->work_end) = fd_tickcount(); fd_store_shrel( ctx->store_ ); }
     357             : 
     358           0 : #define FD_STORE_SHARED_LOCK(store, shacq_start, shacq_end, shrel_end) do {                                  \
     359           0 :   struct fd_store_lock_ctx lock_ctx __attribute__((cleanup(fd_store_shared_lock_cleanup))) =                 \
     360           0 :       { .store_ = (store), .work_end = &(shrel_end), .acq_start = &(shacq_start), .acq_end = &(shacq_end) }; \
     361           0 :   shacq_start = fd_tickcount();                                                                              \
     362           0 :   fd_store_shacq( lock_ctx.store_ );                                                                         \
     363           0 :   shacq_end = fd_tickcount();                                                                                \
     364           0 :   do
     365             : 
     366           0 : #define FD_STORE_SHARED_LOCK_END while(0); } while(0)
     367             : 
     368             : static inline void
     369           0 : fd_store_exclusive_lock_cleanup( struct fd_store_lock_ctx * ctx ) { *(ctx->work_end) = fd_tickcount(); fd_store_exrel( ctx->store_ ); }
     370             : 
     371           0 : #define FD_STORE_EXCLUSIVE_LOCK(store, exacq_start, exacq_end, exrel_end) do {                             \
     372           0 :   struct fd_store_lock_ctx lock_ctx __attribute__((cleanup(fd_store_exclusive_lock_cleanup))) =            \
     373           0 :     { .store_ = (store), .work_end = &(exrel_end), .acq_start = &(exacq_start), .acq_end = &(exacq_end) }; \
     374           0 :   exacq_start = fd_tickcount();                                                                            \
     375           0 :   fd_store_exacq( lock_ctx.store_ );                                                                       \
     376           0 :   exacq_end = fd_tickcount();                                                                              \
     377           0 :   do
     378           0 : #define FD_STORE_EXCLUSIVE_LOCK_END while(0); } while(0)
     379             : 
     380             : struct fd_store_histf {
     381             :   fd_histf_t * histf;
     382             :   long         ts;
     383             : };
     384             : typedef struct fd_store_histf fd_store_histf_t;
     385             : 
     386             : static inline void
     387           0 : fd_store_histf( fd_store_histf_t * ctx ) {
     388           0 :   fd_histf_sample( ctx->histf, (ulong)fd_long_max( fd_tickcount() - ctx->ts, 0UL ) );
     389           0 : }
     390             : 
     391             : #define FD_STORE_HISTF_BEGIN(metric) do {                                                                                \
     392             :    fd_store_histf_t _ctx __attribute__((cleanup(fd_store_histf))) = { .histf = (metric), .ts = fd_tickcount() }; \
     393             :    do
     394             : 
     395             : #define FD_STORE_HISTF_END while(0); } while(0)
     396             : 
     397             : /* fd_store_{query,query_const} queries the FEC set keyed by merkle.
     398             :    Returns a pointer to the fd_store_fec_t if found, NULL otherwise.
     399             : 
     400             :    Both the const and non-const versions are concurrency safe; as in
     401             :    they avoid using the non-const map_ele_query that reorders the chain.
     402             :    fd_store_query gets around this by calling map idx_query_const, which
     403             :    does not reorder the chain, and then indexes directly into the pool
     404             :    and returns a non-const pointer to the element of interest.
     405             : 
     406             :    Assumes caller has acquired the shared lock via fd_store_shacq.
     407             : 
     408             :    IMPORTANT SAFETY TIP!  Caller should only call fd_store_shrel when
     409             :    they no longer retain interest in the returned pointer. */
     410             : 
     411             : FD_FN_PURE static inline fd_store_fec_t *
     412          93 : fd_store_query( fd_store_t * store, fd_hash_t const * merkle_root ) {
     413          93 :    fd_store_key_t  key  = { .mr = *merkle_root, .part = UINT_MAX };
     414          93 :    fd_store_pool_t pool = fd_store_pool( store );
     415         102 :    for( uint i = 0; i < store->part_cnt; i++ ) {
     416         102 :       key.part = i;
     417         102 :       ulong idx = fd_store_map_idx_query_const( fd_store_map( store ), &key, ULONG_MAX, fd_store_fec0( store ) );
     418         102 :       if( idx != ULONG_MAX ) return fd_store_pool_ele( &pool, idx );
     419         102 :    }
     420           0 :    return NULL;
     421          93 : }
     422             : 
     423             : FD_FN_PURE static inline fd_store_fec_t const *
     424         177 : fd_store_query_const( fd_store_t const * store, fd_hash_t * merkle_root ) {
     425         177 :    fd_store_key_t key = { .mr = *merkle_root, .part = UINT_MAX };
     426         285 :    for( uint i = 0; i < store->part_cnt; i++ ) {
     427         234 :       key.part = i;
     428         234 :       fd_store_fec_t const * fec = fd_store_map_ele_query_const( fd_store_map_const( store ), &key, NULL, fd_store_fec0_const( store ) );
     429         234 :       if( fec ) return fec;
     430         234 :    }
     431          51 :    return NULL;
     432         177 : }
     433             : 
     434             : /* Operations */
     435             : 
     436             : /* fd_store_insert inserts a new FEC set keyed by merkle.  Returns the
     437             :    newly inserted fd_store_fec_t.  Each fd_store_fec_t can hold at most
     438             :    FD_STORE_DATA_MAX bytes of data, and caller is responsible for
     439             :    copying into the region.
     440             : 
     441             :    Assumes store is a current local join and has space for another
     442             :    element.  Does additional checks when handholding is enabled and
     443             :    fails insertion (returning NULL) if checks fail.  If this is the
     444             :    first element being inserted into store, the store root will be set
     445             :    to this newly inserted element.
     446             : 
     447             :    Assumes caller has acquired either the shared or exclusive lock via
     448             :    fd_store_shacq or fd_store_exacq.  See top-level documentation for
     449             :    why this operation may only require a shared lock vs. exclusive.
     450             : 
     451             :    IMPORTANT SAFETY TIP!  Caller should only call fd_store_shrel or
     452             :    fd_store_exrel when they no longer retain interest in the returned
     453             :    pointer. */
     454             : 
     455             : fd_store_fec_t *
     456             : fd_store_insert( fd_store_t * store,
     457             :                  ulong        part_idx,
     458             :                  fd_hash_t  * merkle_root );
     459             : 
     460             : /* fd_store_link queries for and links the child keyed by merkle_root to
     461             :    parent keyed by chained_merkle_root.  Returns a pointer to the child.
     462             :    Assumes merkle_root and chained_merkle_root are both non-NULL and key
     463             :    elements currently in the store.
     464             : 
     465             :    Assumes caller has acquired the shared lock via fd_store_shacq.
     466             : 
     467             :    IMPORTANT SAFETY TIP!  Caller should only call fd_store_shrel when
     468             :    they no longer retain interest in the returned pointer. */
     469             : 
     470             : fd_store_fec_t *
     471             : fd_store_link( fd_store_t * store,
     472             :                fd_hash_t  * merkle_root,
     473             :                fd_hash_t  * chained_merkle_root );
     474             : 
     475             : /* fd_store_publish publishes merkle_root as the new store root, pruning
     476             :    all elements across branches that do not descend from the new root.
     477             :    Returns a pointer to the new root.  Assumes merkle_root is in the
     478             :    store and connected to the root (if handholding is enabled does
     479             :    additional checks and returns NULL on error).  Note pruning can
     480             :    result in store elements greater than the new root slot being
     481             :    removed.  These are elements that become orphaned as a result of the
     482             :    common ancestor with the new root being removed (the entire branch
     483             :    ie. fork is pruned).
     484             : 
     485             :    For example, in the tree (preorder) [0 1 2 4 3 5 6] publishing 2 will
     486             :    result in [0 1] being removed given they are ancestors of 2, and
     487             :    removing 1 will leave [3 5 6] orphaned and also removed.
     488             : 
     489             :    Assumes caller has acquired the exclusive lock via fd_store_exacq.
     490             : 
     491             :    IMPORTANT SAFETY TIP!  Caller should only call fd_store_exrel when
     492             :    they no longer retain interest in the returned pointer. */
     493             : 
     494             : fd_store_fec_t *
     495             : fd_store_publish( fd_store_t *      store,
     496             :                   fd_hash_t const * merkle_root );
     497             : 
     498             : /* fd_store_clear clears the store.  All elements are removed from the
     499             :    map and released back into the pool.  Does not zero-out fields.
     500             : 
     501             :    IMPORTANT SAFETY TIP!  the store must be non-empty. */
     502             : 
     503             : fd_store_t *
     504             : fd_store_clear( fd_store_t * store );
     505             : 
     506             : /* TODO fd_store_verify */
     507             : 
     508             : /* fd_store_print pretty-prints a formatted store as a tree structure.
     509             :    Printing begins from the store root and each node is the FEC set key
     510             :    (merkle root hash). */
     511             : 
     512             : int
     513             : fd_store_verify( fd_store_t * store );
     514             : 
     515             : void
     516             : fd_store_print( fd_store_t const * store );
     517             : 
     518             : FD_PROTOTYPES_END
     519             : 
     520             : #endif /* HEADER_fd_src_discof_repair_fd_store_h */

Generated by: LCOV version 1.14