Line data    Source code

       1             : #ifndef HEADER_fd_src_flamenco_gossip_fd_gossip_purged_h
       2             : #define HEADER_fd_src_flamenco_gossip_fd_gossip_purged_h
       3             : 
       4             : #include "../fd_flamenco_base.h"
       5             : #include "../../util/fd_hash32.h"
       6             : 
       7             : /* fd_gossip_purged implements the "purged" side-table of the CRDS.
       8             :    When a CRDS entry is overridden by a newer value, fails to insert
       9             :    (stale), or is dropped because the origin has no known contact info,
      10             :    its hash is recorded here so it can appear in bloom filters and
      11             :    prevent peers from re-sending it.
      12             : 
      13             :    There are three mutually exclusive lists:
      14             : 
      15             :      - replaced_dlist:        Entries replaced by a newer value.  Expire in 60s.
      16             :      - failed_inserts_dlist:  Entries that failed to upsert.     Expire in 60s.
      17             :      - no_contact_info_dlist: Entries dropped for missing CI.    Expire in ~2 days.
      18             : 
      19             :    All three lists share a single pool, a map keyed by the first 8
      20             :    bytes of the value hash (so a hash is recorded once) and an hset of
      21             :    the hashes so they can be iterated together when building
      22             :    pull-request bloom filters. */
      23             : 
      24             : struct fd_gossip_purged_metrics {
      25             :   ulong purged_cnt;
      26             :   ulong purged_expired_cnt;
      27             :   ulong purged_evicted_cnt;
      28             : };
      29             : 
      30             : typedef struct fd_gossip_purged_metrics fd_gossip_purged_metrics_t;
      31             : 
      32             : struct fd_crds_purged {
      33             :   uchar hash[ 32UL ];
      34             : 
      35             :   struct {
      36             :     uint next;
      37             :   } pool;
      38             : 
      39             :   struct {
      40             :     ulong hash_prefix;
      41             :     uint  next;
      42             :     uint  prev;
      43             :   } map;
      44             : 
      45             :   /* We keep a linked list of purged values sorted by insertion time.
      46             :      The time used here is our node's wallclock.
      47             : 
      48             :      There are actually three (mutually exclusive) lists that reuse the
      49             :      same pointers here: one for "replaced" entries that expire in 60s,
      50             :      one for "failed_inserts" that expire after 60s, and one for
      51             :      "no_contact_info" entries that expire after 2 days. */
      52             :   struct {
      53             :     long  wallclock_nanos;
      54             :     uint  next;
      55             :     uint  prev;
      56             :   } expire;
      57             : 
      58             :   /* For no_contact_info entries, we also track the origin pubkey and
      59             :      chain entries by origin so they can all be drained when we learn
      60             :      the contact info for that pubkey. */
      61             :   fd_pubkey_t origin;
      62             :   struct {
      63             :     uint next;
      64             :     uint prev;
      65             :   } nci_map;
      66             : };
      67             : 
      68             : typedef struct fd_crds_purged fd_crds_purged_t;
      69             : 
      70             : FD_STATIC_ASSERT( sizeof(fd_crds_purged_t)==112UL, purged_entry_footprint );
      71             : 
      72             : struct fd_gossip_purged_private;
      73             : typedef struct fd_gossip_purged_private fd_gossip_purged_t;
      74             : 
      75             : struct fd_gossip_hset_private;
      76             : typedef struct fd_gossip_hset_private fd_gossip_hset_t;
      77             : 
      78          60 : #define FD_GOSSIP_PURGED_ALIGN 128UL
      79          18 : #define FD_GOSSIP_PURGED_MAGIC (0xf17eda2c39070ed0UL) /* firedancer purged v0 */
      80             : 
      81             : static inline void
      82             : fd_gossip_purged_generate_masks( ulong   mask,
      83             :                                  uint    mask_bits,
      84             :                                  ulong * start_mask,
      85       23808 :                                  ulong * end_mask ) {
      86             :   /* Agave defines the mask as a ulong with the top mask_bits bits set
      87             :      to the desired prefix and all other bits set to 1. */
      88       23808 :   FD_TEST( mask_bits<64U );
      89       23808 :   ulong range = fd_ulong_mask( 0U, (int)(63U-mask_bits) );
      90       23808 :   *start_mask = mask & ~range;
      91       23808 :   *end_mask   = mask | range;
      92       23808 : }
      93             : 
      94             : FD_PROTOTYPES_BEGIN
      95             : 
      96             : FD_FN_CONST ulong
      97             : fd_gossip_purged_align( void );
      98             : 
      99             : FD_FN_CONST ulong
     100             : fd_gossip_purged_footprint( ulong purged_max );
     101             : 
     102             : void *
     103             : fd_gossip_purged_new( void *     shmem,
     104             :                       fd_rng_t * rng,
     105             :                       ulong      purged_max );
     106             : 
     107             : fd_gossip_purged_t *
     108             : fd_gossip_purged_join( void * shpurged );
     109             : 
     110             : fd_gossip_purged_metrics_t const *
     111             : fd_gossip_purged_metrics( fd_gossip_purged_t const * purged );
     112             : 
     113             : /* fd_gossip_purged_len returns the number of entries currently tracked
     114             :    in the purged pool (across all three dlists). */
     115             : 
     116             : ulong
     117             : fd_gossip_purged_len( fd_gossip_purged_t const * purged );
     118             : 
     119             : /* fd_gossip_purged_hset returns the dense index of the hashes of all
     120             :    tracked entries, see fd_gossip_hset.h. */
     121             : 
     122             : fd_gossip_hset_t const *
     123             : fd_gossip_purged_hset( fd_gossip_purged_t const * purged );
     124             : 
     125             : /* fd_gossip_purged_insert_replaced records a hash that was purged
     126             :    because a newer CRDS value replaced it. */
     127             : 
     128             : void
     129             : fd_gossip_purged_insert_replaced( fd_gossip_purged_t * purged,
     130             :                                   uchar const *        hash,
     131             :                                   long                 now );
     132             : 
     133             : /* fd_gossip_purged_insert_failed_insert records a hash that failed to
     134             :    upsert the CRDS table (e.g. stale or lost a tiebreaker). */
     135             : 
     136             : void
     137             : fd_gossip_purged_insert_failed_insert( fd_gossip_purged_t * purged,
     138             :                                        uchar const *        hash,
     139             :                                        long                 now );
     140             : 
     141             : /* fd_gossip_purged_insert_no_contact_info records a hash that was
     142             :    dropped because the origin pubkey has no known contact info.  The
     143             :    hash is indexed like any other purged entry (so it appears in bloom
     144             :    filters) and chained per pubkey so all entries for a given origin
     145             :    can be drained when we learn their contact info. */
     146             : 
     147             : void
     148             : fd_gossip_purged_insert_no_contact_info( fd_gossip_purged_t * purged,
     149             :                                          uchar const *        origin,
     150             :                                          uchar const *        hash,
     151             :                                          long                 now );
     152             : 
     153             : /* fd_gossip_purged_drain_no_contact_info removes all no_contact_info
     154             :    entries associated with the given origin pubkey from the purged
     155             :    table, no_contact_info dlist, and per-pubkey chain.  This causes
     156             :    those hashes to disappear from bloom filters, so peers will re-send
     157             :    the corresponding CRDS values in future pull responses. */
     158             : 
     159             : void
     160             : fd_gossip_purged_drain_no_contact_info( fd_gossip_purged_t * purged,
     161             :                                         uchar const *        origin );
     162             : 
     163             : /* fd_gossip_purged_expire removes entries that have exceeded their
     164             :    expiry window from each of the three dlists. */
     165             : 
     166             : void
     167             : fd_gossip_purged_expire( fd_gossip_purged_t * purged,
     168             :                          long                 now );
     169             : 
     170             : FD_PROTOTYPES_END
     171             : 
     172             : #endif /* HEADER_fd_src_flamenco_gossip_fd_gossip_purged_h */