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