Line data    Source code

       1             : #ifndef HEADER_fd_src_choreo_tower_fd_tower_blocks_h
       2             : #define HEADER_fd_src_choreo_tower_fd_tower_blocks_h
       3             : 
       4             : #include "../fd_choreo_base.h"
       5             : #include "fd_tower_voters.h"
       6             : 
       7             : /* fd_tower_blocks maintains tower-specific metadata about every block,
       8             :    such as what block_id we first replayed, what block_id we voted for,
       9             :    and what block_id was ultimately "duplicate confirmed".
      10             : 
      11             :    This is used by tower to make voting decisions, such as whether or
      12             :    not we can switch "forks".  In this context, a fork is a branch of a
      13             :    tree that extends from the root to a leaf.  For example:
      14             : 
      15             :         /-- 3-- 4  (A)
      16             :    1-- 2
      17             :         \-- 5      (B)
      18             : 
      19             :    Here, A and B are two different forks.  A is [1, 2, 3, 4] and B is
      20             :    [1, 2, 5], two branches that each extend from the root to a leaf.
      21             : 
      22             :    Note that even though fd_tower_blocks is block_id-aware, it does not
      23             :    use them for determining parentage.  Instead, parentage is based on
      24             :    slot numbers, so in cases of equivocation (duplicate blocks), tower
      25             :    will consider something an ancestor or descendant even if the block
      26             :    ids do not chain.
      27             : 
      28             :    This behavior intentionally mirrors the Agave logic implemented in
      29             :    `make_check_switch_threshold_decision`.  Essentially, tower is unable
      30             :    to distinguish duplicates because the vote account format (in which
      31             :    towers are stored) only stores slot numbers and not block_ids. */
      32             : 
      33             : struct fd_tower_blk {
      34             :   ulong     slot;               /* map key */
      35             :   ulong     parent_slot;        /* parent slot */
      36             :   ulong     epoch;              /* epoch of this slot */
      37             :   int       replayed;           /* whether we've replayed this slot yet */
      38             :   fd_hash_t replayed_block_id;  /* the block_id we _first_ replayed for this slot */
      39             :   int       voted;              /* whether we voted for this slot yet */
      40             :   fd_hash_t voted_block_id;     /* the block_id we voted on for this slot */
      41             :   int       confirmed;          /* whether this slot has been duplicate confirmed */
      42             :   fd_hash_t confirmed_block_id; /* the block_id that was duplicate confirmed */
      43             :   ulong     bank_idx;           /* pool idx of the bank as of this replayed block */
      44             : };
      45             : typedef struct fd_tower_blk fd_tower_blk_t;
      46             : 
      47             : #define MAP_NAME           fd_tower_blk
      48           0 : #define MAP_T              fd_tower_blk_t
      49           0 : #define MAP_KEY            slot
      50           0 : #define MAP_KEY_NULL       ULONG_MAX
      51           0 : #define MAP_KEY_INVAL(key) ((key)==ULONG_MAX)
      52             : #define MAP_MEMOIZE        0
      53             : #include "../../util/tmpl/fd_map_dynamic.c"
      54             : 
      55             : struct __attribute__((aligned(128UL))) fd_tower_blocks {
      56             :   fd_tower_blk_t * blk_map;
      57             : };
      58             : typedef struct fd_tower_blocks fd_tower_blocks_t;
      59             : 
      60             : FD_PROTOTYPES_BEGIN
      61             : 
      62             : FD_FN_CONST static inline ulong
      63           0 : fd_tower_blocks_align( void ) {
      64           0 :   return alignof(fd_tower_blocks_t);
      65           0 : }
      66             : 
      67             : FD_FN_CONST static inline ulong
      68           0 : fd_tower_blocks_footprint( ulong slot_max ) {
      69           0 :   int lg_slot_max = fd_ulong_find_msb( fd_ulong_pow2_up( slot_max ) ) + 1;
      70           0 :   return FD_LAYOUT_FINI(
      71           0 :     FD_LAYOUT_APPEND(
      72           0 :     FD_LAYOUT_APPEND(
      73           0 :     FD_LAYOUT_INIT,
      74           0 :       alignof(fd_tower_blocks_t), sizeof(fd_tower_blocks_t)             ),
      75           0 :       fd_tower_blk_align(),       fd_tower_blk_footprint( lg_slot_max ) ),
      76           0 :     fd_tower_blocks_align() );
      77           0 : }
      78             : 
      79             : /* fd_tower_blocks_new formats an unused memory region for use as a
      80             :    tower_blocks.  mem is a non-NULL pointer to this region in the local
      81             :    address space with the required footprint and alignment. */
      82             : 
      83             : void *
      84             : fd_tower_blocks_new( void * shmem,
      85             :                      ulong  slot_max,
      86             :                      ulong  seed );
      87             : 
      88             : /* fd_tower_blocks_join joins the caller to the tower_blocks. shblocks
      89             :    points to the first byte of the memory region backing the shblocks in
      90             :    the caller's address space.
      91             : 
      92             :    Returns a pointer in the local address space to blocks on success. */
      93             : 
      94             : fd_tower_blocks_t *
      95             : fd_tower_blocks_join( void * shblocks );
      96             : 
      97             : /* fd_tower_blocks_leave blocks a current local join.  Returns a pointer
      98             :    to the underlying shared memory region on success and NULL on failure
      99             :    (logs details).  Reasons for failure include blocks is NULL. */
     100             : 
     101             : void *
     102             : fd_tower_blocks_leave( fd_tower_blocks_t const * blocks );
     103             : 
     104             : /* fd_tower_blocks_delete unformats a memory region used as a blocks.
     105             :    Assumes only the local process is joined to the region.  Returns a
     106             :    pointer to the underlying shared memory region or NULL if used
     107             :    obviously in error (e.g. blocks is obviously not a blocks ...  logs
     108             :    details).  The ownership of the memory region is transferred to the
     109             :    caller. */
     110             : 
     111             : void *
     112             : fd_tower_blocks_delete( void * blocks );
     113             : 
     114             : /* fd_tower_is_slot_{ancestor,descendant} return 1 or 0 depending on
     115             :    whether the specified relationship is true in blocks. */
     116             : 
     117             : int
     118             : fd_tower_blocks_is_slot_ancestor( fd_tower_blocks_t * blocks,
     119             :                                   ulong               descendant_slot,
     120             :                                   ulong               ancestor_slot );
     121             : 
     122             : int
     123             : fd_tower_blocks_is_slot_descendant( fd_tower_blocks_t * blocks,
     124             :                                     ulong               ancestor_slot,
     125             :                                     ulong               descendant_slot );
     126             : 
     127             : /* fd_tower_blocks_lowest_common_ancestor returns the lowest common
     128             :    ancestor of slot1 and slot 2.  There is always an LCA in a valid
     129             :    tower_forks tree (the root). */
     130             : 
     131             : ulong
     132             : fd_tower_blocks_lowest_common_ancestor( fd_tower_blocks_t * blocks,
     133             :                                         ulong               slot1,
     134             :                                         ulong               slot2 );
     135             : 
     136             : /* fd_tower_blocks_canonical_block_id returns what we think to be the
     137             :    correct block id for a given slot, based on what we've observed.
     138             : 
     139             :    We prioritize in-order:
     140             :    1. the duplicate-confirmed block id
     141             :    2. our voted block id
     142             :    3. our first-replayed block id
     143             : 
     144             :    This is the canonical order because it reflects what we think is the
     145             :    "true" block id given the information we have.
     146             : 
     147             :    Agave behaves similarly, except they "purge" their replay bank hash
     148             :    so they're always comparing the confirmed block id */
     149             : 
     150             : fd_hash_t const *
     151             : fd_tower_blocks_canonical_block_id( fd_tower_blocks_t * blocks,
     152             :                                     ulong               slot );
     153             : 
     154             : /* fd_tower_blocks_{query,insert,remove} provide convenient wrappers for
     155             :    {querying,inserting,removing} into the underlying map. */
     156             : 
     157             : fd_tower_blk_t *
     158             : fd_tower_blocks_query( fd_tower_blocks_t * blocks,
     159             :                        ulong               slot );
     160             : 
     161             : fd_tower_blk_t *
     162             : fd_tower_blocks_insert( fd_tower_blocks_t * blocks,
     163             :                         ulong               slot,
     164             :                         ulong               parent_slot );
     165             : 
     166             : void
     167             : fd_tower_blocks_remove( fd_tower_blocks_t * blocks,
     168             :                         ulong               slot );
     169             : 
     170             : FD_PROTOTYPES_END
     171             : 
     172             : #endif /* HEADER_fd_src_choreo_tower_fd_tower_blocks_h */