Line data    Source code

       1             : #ifndef HEADER_fd_src_flamenco_runtime_fd_blockhashes_h
       2             : #define HEADER_fd_src_flamenco_runtime_fd_blockhashes_h
       3             : 
       4             : #include "../fd_flamenco_base.h"
       5             : #include "../../util/fd_hash32.h"
       6             : 
       7             : /* fd_blockhashes.h provides a "blockhash queue" API.  The blockhash
       8             :    queue is a consensus-relevant data structure that is part of the slot
       9             :    bank.
      10             : 
      11             :    See solana_accounts_db::blockhash_queue::BlockhashQueue. */
      12             : 
      13             : /* FD_BLOCKHASHES_MAX is the most live entries Agave's BlockhashQueue
      14             :    ever holds: the purge keeps ages 0..300 inclusive.
      15             : 
      16             :    Every entry carries the hash_index it was registered at, and ages are
      17             :    computed from hash_index (see fd_blockhashes_check_age), as in Agave.
      18             :    Indices are usually consecutive, but a snapshot may skip some: a
      19             :    blockhash registered more than once (agave-ledger-tool create-snapshot
      20             :    synthesizing slots with 0 hashes per tick, during a restart on an
      21             :    Alpenglow cluster) keeps only its newest hash_index, so the older
      22             :    index is simply absent.  The queue holds only the entries that exist,
      23             :    so a skipped index costs no space and needs no special handling.
      24             : 
      25             :    FD_BLOCKHASHES_DEQ_MAX is the deque capacity: the power of two that
      26             :    holds FD_BLOCKHASHES_MAX entries.  The runtime evicts by count when
      27             :    it is full; entries beyond age 300 that this retains are never valid,
      28             :    since every lookup bounds the age. */
      29             : 
      30         948 : #define FD_BLOCKHASHES_MAX     (301UL)
      31       71022 : #define FD_BLOCKHASHES_DEQ_MAX (512UL)
      32             : FD_STATIC_ASSERT( !( FD_BLOCKHASHES_DEQ_MAX & (FD_BLOCKHASHES_DEQ_MAX-1UL) ), blockhashes_deq_max_pow2 );
      33             : FD_STATIC_ASSERT( FD_BLOCKHASHES_DEQ_MAX>=FD_BLOCKHASHES_MAX, blockhashes_deq_max_fits );
      34             : 
      35             : /* See solana_accounts_db::blockhash_queue::HashInfo. */
      36             : 
      37             : struct fd_blockhash_info {
      38             :   fd_hash_t hash;
      39             :   ulong     lamports_per_signature;
      40             :   ulong     hash_index; /* sequence number this blockhash was registered at */
      41             :   ushort    next;
      42             : };
      43             : 
      44             : typedef struct fd_blockhash_info fd_blockhash_info_t;
      45             : 
      46             : /* Declare a static size deque for the blockhash queue. */
      47             : 
      48             : #define DEQUE_NAME fd_blockhash_deq
      49        8979 : #define DEQUE_T    fd_blockhash_info_t
      50       66057 : #define DEQUE_MAX  FD_BLOCKHASHES_DEQ_MAX /* must be a power of 2 */
      51             : #include "../../util/tmpl/fd_deque.c"
      52             : 
      53             : /* Declare a separately chained hash map over the blockhash queue. */
      54             : 
      55             : #define FD_BLOCKHASH_MAP_CHAIN_MAX  (512UL)
      56             : #define FD_BLOCKHASH_MAP_FOOTPRINT (1048UL)
      57             : 
      58             : #define MAP_NAME          fd_blockhash_map
      59             : #define MAP_ELE_T         fd_blockhash_info_t
      60             : #define MAP_KEY_T         fd_hash_t
      61        8970 : #define MAP_KEY           hash
      62       29781 : #define MAP_IDX_T         ushort
      63        9843 : #define MAP_NEXT          next
      64        1947 : #define MAP_KEY_EQ(k0,k1) fd_hash_eq( (k0), (k1) )
      65       17457 : #define MAP_KEY_HASH(k,s) fd_hash32( (k->uc), (s) )
      66             : #include "../../util/tmpl/fd_map_chain.c"
      67             : 
      68             : /* fd_blockhashes_t is the class representing a blockhash queue.
      69             : 
      70             :    It is a static size container housing sub-structures as plain old
      71             :    struct members.  Safe to declare as a local variable assuming the
      72             :    stack is sufficiently sized.  Entirely self-contained and position-
      73             :    independent (safe to clone via fd_memcpy and safe to map into another
      74             :    address space).
      75             : 
      76             :    Under the hood it is an array-backed double-ended queue, and a
      77             :    separately-chained hash index on top.  New entries are inserted to
      78             :    the **tail** of the queue.  Entries are kept in ascending hash_index
      79             :    order, so the tail is the newest entry and its hash_index is the last
      80             :    registered one; consecutive entries may differ by more than one (see
      81             :    above). */
      82             : 
      83             : struct fd_blockhashes {
      84             : 
      85             :   union {
      86             :     fd_blockhash_map_t map[1];
      87             :     uchar map_mem[ FD_BLOCKHASH_MAP_FOOTPRINT ];
      88             :   };
      89             : 
      90             :   fd_blockhash_deq_private_t d;
      91             : 
      92             : };
      93             : 
      94             : typedef struct fd_blockhashes fd_blockhashes_t;
      95             : 
      96             : FD_PROTOTYPES_BEGIN
      97             : 
      98             : fd_blockhashes_t *
      99             : fd_blockhashes_init( fd_blockhashes_t * mem,
     100             :                      ulong              seed );
     101             : 
     102             : /* fd_blockhashes_push_new adds a new slot to the blockhash queue. The
     103             :    caller fills the returned pointer with blockhash queue info
     104             :    (currently only lamports_per_signature).  Called as part of regular
     105             :    runtime processing.  The new entry's hash_index is one past the
     106             :    newest entry's (0 on an empty queue, like Agave's genesis hash).
     107             :    Evicts the oldest entry if the queue is full (practically always the
     108             :    case except for the first few blocks after genesis).  Aborts if hash
     109             :    is already present.  Always returns a valid pointer. */
     110             : 
     111             : fd_blockhash_info_t *
     112             : fd_blockhashes_push_new( fd_blockhashes_t * blockhashes,
     113             :                          fd_hash_t const *  hash );
     114             : 
     115             : /* fd_blockhashes_push_old behaves like the above, but adding a new
     116             :    oldest entry instead, with hash_index one below the oldest entry's.
     117             :    Returns NULL if there is no more space or no lower hash_index.
     118             :    Aborts if hash is already present.  Useful for testing. */
     119             : 
     120             : fd_blockhash_info_t *
     121             : fd_blockhashes_push_old( fd_blockhashes_t * blockhashes,
     122             :                          fd_hash_t const *  hash );
     123             : 
     124             : /* fd_blockhashes_pop_new removes the newest blockhash queue entry. */
     125             : 
     126             : void
     127             : fd_blockhashes_pop_new( fd_blockhashes_t * blockhashes );
     128             : 
     129             : /* fd_blockhashes_age returns the age of info, an entry of blockhashes:
     130             :    how many hash indices it is behind the newest entry.  Assumes the
     131             :    queue is not empty. */
     132             : 
     133             : FD_FN_PURE static inline ulong
     134             : fd_blockhashes_age( fd_blockhashes_t const *    blockhashes,
     135        1080 :                     fd_blockhash_info_t const * info ) {
     136        1080 :   return fd_blockhash_deq_peek_tail_const( blockhashes->d.deque )->hash_index - info->hash_index;
     137        1080 : }
     138             : 
     139             : /* fd_blockhashes_check_age returns 1 if blockhash is in the queue with
     140             :    an age of at most max_age, and 0 otherwise. */
     141             : 
     142             : FD_FN_PURE int
     143             : fd_blockhashes_check_age( fd_blockhashes_t const * blockhashes,
     144             :                           fd_hash_t const *        blockhash,
     145             :                           ulong                    max_age );
     146             : 
     147             : FD_FN_PURE static inline fd_hash_t const *
     148        6738 : fd_blockhashes_peek_last_hash( fd_blockhashes_t const * blockhashes ) {
     149        6738 :   if( FD_UNLIKELY( fd_blockhash_deq_empty( blockhashes->d.deque ) ) ) return NULL;
     150        6735 :   return &fd_blockhash_deq_peek_tail_const( blockhashes->d.deque )->hash;
     151        6738 : }
     152             : 
     153             : 
     154             : FD_FN_PURE static inline fd_blockhash_info_t const *
     155         123 : fd_blockhashes_peek_last( fd_blockhashes_t const * blockhashes ) {
     156         123 :   if( FD_UNLIKELY( fd_blockhash_deq_empty( blockhashes->d.deque ) ) ) return NULL;
     157         123 :   return fd_blockhash_deq_peek_tail_const( blockhashes->d.deque );
     158         123 : }
     159             : 
     160             : FD_PROTOTYPES_END
     161             : 
     162             : #endif /* HEADER_fd_src_flamenco_runtime_fd_blockhashes_h */