Line data    Source code

       1             : #ifndef HEADER_fd_src_discof_repair_fd_inflight_h
       2             : #define HEADER_fd_src_discof_repair_fd_inflight_h
       3             : 
       4             : #include "fd_policy.h"
       5             : 
       6             : /* fd_inflight tracks repair requests that are inflight to other
       7             :    validators.  This module is useful for metrics and reporting.
       8             :    In-exact updates of orphan requests and highest window requests from
       9             :    this module are non-critical, but exact updates of shred requests are
      10             :    critical. Repair tile relies on this module to be able to re-request
      11             :    any shreds that it has sent, because policy next does not request any
      12             :    shred twice.
      13             : 
      14             :    Requests are key-ed by (slot, shred_idx, nonce) as in the current
      15             :    strategy (see fd_policy.h).  Since we generate the nonce based on the
      16             :    time bucketed by 16ms, which is less than the retransmission timeout,
      17             :    it's highly unlikely that a retransmission request will have the same
      18             :    nonce.  The chances that an inflight request does not get a response
      19             :    are non-negligible due to shred tile upstream deduping duplicates. */
      20             : 
      21             : /* Max number of pending requests */
      22           0 : #define FD_INFLIGHT_REQ_MAX (1<<20)
      23             : 
      24             : struct fd_inflight_key {
      25             :   ulong slot;       /* slot of the request */
      26             :   ulong shred_idx;  /* shred index of the request */
      27             :   ulong nonce;      /* computed nonce */
      28             : };
      29             : typedef struct fd_inflight_key fd_inflight_key_t;
      30             : 
      31             : struct __attribute__((aligned(128UL))) fd_inflight {
      32             :   fd_inflight_key_t key;
      33             :   ulong             next;          /* reserved for internal use by fd_pool and fd_map_chain */
      34             :   ulong             prev;          /* for fd_map_chain */
      35             :   long              timestamp_ns;  /* timestamp when request was created (nanoseconds) */
      36             :   fd_pubkey_t       pubkey;        /* public key of the peer */
      37             : 
      38             : 
      39             :   /* Reserved for DLL eviction */
      40             :   ulong             prevll;      /* pool index of previous element in DLL */
      41             :   ulong             nextll;      /* pool index of next element in DLL */
      42             : };
      43             : typedef struct fd_inflight fd_inflight_t;
      44             : 
      45             : #define POOL_NAME   fd_inflight_pool
      46           0 : #define POOL_T      fd_inflight_t
      47             : #include "../../util/tmpl/fd_pool.c"
      48             : 
      49             : #define MAP_NAME            fd_inflight_map
      50           0 : #define MAP_KEY             key
      51           0 : #define MAP_ELE_T           fd_inflight_t
      52             : #define MAP_KEY_T           fd_inflight_key_t
      53           0 : #define MAP_KEY_EQ(k0, k1)  (((k0)->nonce==(k1)->nonce) & ((k0)->shred_idx==(k1)->shred_idx) & ((k0)->slot==(k1)->slot))
      54           0 : #define MAP_KEY_HASH(k,s)   fd_hash( (s), (k), sizeof(fd_inflight_key_t) )
      55             : #define MAP_MULTI           1 /* It's possible but extremely unlikely that we'll insert duplicates */
      56             : /* Removal via the non-_fast version is kind of strange in the possible
      57             :    presence of duplicate keys. */
      58             : #define MAP_OPTIMIZE_RANDOM_ACCESS_REMOVAL 1
      59             : #include "../../util/tmpl/fd_map_chain.c"
      60             : 
      61             : #define DLIST_NAME      fd_inflight_dlist
      62             : #define DLIST_ELE_T     fd_inflight_t
      63           0 : #define DLIST_PREV      prevll
      64           0 : #define DLIST_NEXT      nextll
      65             : #include "../../util/tmpl/fd_dlist.c"
      66             : 
      67             : struct fd_inflights {
      68             :   /* Each element in the pool is either OUTSTANDING, POPPED (when it
      69             :      times out), or FREE.
      70             : 
      71             :             insert                  pop
      72             :      FREE  --------> OUTSTANDING -----------> POPPED
      73             :       ^                  |                      |
      74             :       |     remove       |  remove, or evicted  |
      75             :       -------------------------------------------
      76             : 
      77             :     All elements begin as FREE.  Elements that are FREE are released in
      78             :     the pool.  Elements that are OUTSTANDING are in map and
      79             :     outstanding_dl.  Elements that are POPPED are in popped_map and
      80             :     popped_dl.  If we need to acquire an element and the pool is empty,
      81             :     the oldest POPPED element will be evicted. */
      82             :   fd_inflight_t       * pool;
      83             :   fd_inflight_map_t   * map;
      84             :   fd_inflight_map_t   * popped_map;
      85             :   fd_inflight_dlist_t   outstanding_dl[1];
      86             :   fd_inflight_dlist_t   popped_dl[1];
      87             :   ulong                 popped_cnt;
      88             : };
      89             : typedef struct fd_inflights fd_inflights_t;
      90             : 
      91             : FD_FN_CONST static inline ulong
      92           0 : fd_inflights_align( void ) { return 128UL; }
      93             : 
      94             : FD_FN_CONST static inline ulong
      95           0 : fd_inflights_footprint( void ) {
      96           0 :   ulong chain_cnt = fd_inflight_map_chain_cnt_est( FD_INFLIGHT_REQ_MAX );
      97           0 :   return FD_LAYOUT_FINI(
      98           0 :     FD_LAYOUT_APPEND(
      99           0 :     FD_LAYOUT_APPEND(
     100           0 :     FD_LAYOUT_APPEND(
     101           0 :     FD_LAYOUT_APPEND(
     102           0 :     FD_LAYOUT_INIT,
     103           0 :       alignof(fd_inflights_t),  sizeof(fd_inflights_t)                            ),
     104           0 :       fd_inflight_pool_align(), fd_inflight_pool_footprint( FD_INFLIGHT_REQ_MAX ) ),
     105           0 :       fd_inflight_map_align(),  fd_inflight_map_footprint ( chain_cnt           ) ),
     106           0 :       fd_inflight_map_align(),  fd_inflight_map_footprint ( chain_cnt           ) ),
     107           0 :     fd_inflights_align() );
     108           0 : }
     109             : 
     110             : void *
     111             : fd_inflights_new( void * shmem,
     112             :                   ulong  seed );
     113             : 
     114             : fd_inflights_t *
     115             : fd_inflights_join( void * shmem );
     116             : 
     117             : void
     118             : fd_inflights_request_insert( fd_inflights_t * table, ulong nonce, fd_pubkey_t const * pubkey, ulong slot, ulong shred_idx );
     119             : 
     120             : long
     121             : fd_inflights_request_remove( fd_inflights_t * table, ulong nonce, ulong slot, ulong shred_idx, fd_pubkey_t * peer_out );
     122             : 
     123             : /* Important! Caller must guarantee that the request list is not empty.
     124             :    This function cannot fail and will always try to populate the output
     125             :    parameters. Typical use should only call this after
     126             :    fd_inflights_should_drain returns true. */
     127             : 
     128             : void
     129             : fd_inflights_request_pop( fd_inflights_t * table, ulong * nonce_out, ulong * slot_out, ulong * shred_idx_out );
     130             : 
     131             : static inline int
     132           0 : fd_inflights_should_drain( fd_inflights_t * table, long now ) {
     133             :   /* peek at head */
     134           0 :   if( FD_UNLIKELY( fd_inflight_dlist_is_empty( table->outstanding_dl, table->pool ) ) ) return 0;
     135             : 
     136           0 :   fd_inflight_t * inflight_req = fd_inflight_dlist_ele_peek_head( table->outstanding_dl, table->pool );
     137           0 :   if( FD_UNLIKELY( inflight_req->timestamp_ns + FD_POLICY_DEDUP_TIMEOUT < now ) ) return 1;
     138           0 :   return 0;
     139           0 : }
     140             : 
     141             : /* Returns the number of new outstanding requests that can be made
     142             :    until the inflight pool is full, and there are no popped
     143             :    requests to evict.  If this is 0, then the next insert would
     144             :    evict an outstanding request. */
     145             : 
     146             : static inline ulong
     147           0 : fd_inflights_outstanding_free( fd_inflights_t * table ) {
     148           0 :   return fd_inflight_pool_free( table->pool ) + table->popped_cnt;
     149           0 : }
     150             : 
     151             : void
     152             : fd_inflights_print( fd_inflight_dlist_t * dlist, fd_inflight_t * pool );
     153             : 
     154             : #endif /* HEADER_fd_src_discof_repair_fd_inflight_h */