Line data    Source code

       1             : #ifndef HEADER_fd_src_discof_repair_fd_policy_h
       2             : #define HEADER_fd_src_discof_repair_fd_policy_h
       3             : 
       4             : /* fd_policy implements the policy of the Repair agent.  It determines
       5             :    what next repair request the validator should make. It also
       6             :    determines which peer(s) the validator should make the request to.
       7             : 
       8             :    The default policy implementation is to prioritize discovering
       9             :    ancestry for orphaned slots first (making an orphan request), and
      10             :    then making forward progress on the main ancestry tree (making a
      11             :    regular request) when there are no orphan requests to make.
      12             : 
      13             :    Regular shred requests are made round-robin BFS with time-based
      14             :    dedup: round-robin through all the repair peers we know about, and
      15             :    BFS down the repair forest (see fd_forest.h).
      16             : 
      17             :    This policy dedups identical repair requests that occur within a
      18             :    specified amount of time window of each other. */
      19             : 
      20             : #include "../forest/fd_forest.h"
      21             : #include "../../util/net/fd_net_headers.h"
      22             : #include "fd_repair.h"
      23             : #include "fd_reqlim.h"
      24             : #include "../../disco/shred/fd_rnonce_ss.h"
      25             : 
      26             : /* fd_policy_peer_t describes a peer validator that serves repairs.
      27             :    Peers are discovered through gossip, via a "ContactInfo" message that
      28             :    shares the validator's ip and repair server port. */
      29             : 
      30             : struct fd_policy_peer {
      31             :   fd_pubkey_t key;     /* map key, pubkey of the validator */
      32             :   ulong       next;    /* reserved for map_chain, pool */
      33             :   uint        ip4;     /* ip4 addr of the peer */
      34             :   ushort      port;    /* repair server port of the peer */
      35             :   ulong       req_cnt; /* count of requests we've sent to this peer */
      36             :   ulong       res_cnt; /* count of responses we've received from this peer */
      37             : 
      38             :   struct {
      39             :     ulong next;
      40             :     ulong prev;
      41             :   } dlist;
      42             : 
      43             :   /* below are for measuring bandwidth usage */
      44             :   long  first_req_ts;
      45             :   long  last_req_ts;
      46             : 
      47             :   long  first_resp_ts;
      48             :   long  last_resp_ts;
      49             : 
      50             :   long  total_lat; /* total RTT over all responses in ns */
      51             :   long  ewma_lat;  /* exponential weighted moving average of RTT in ns */
      52             :   ulong stake;
      53             : 
      54             :   uint unanswered; /* requests sent since last response received */
      55             :   uint ping;       /* whether this peer currently has a ping in our sign queue */
      56             : };
      57             : typedef struct fd_policy_peer fd_policy_peer_t;
      58             : 
      59             : #define MAP_NAME                 fd_policy_peer_map
      60             : #define MAP_ELE_T                fd_policy_peer_t
      61             : #define MAP_KEY_T                fd_pubkey_t
      62           0 : #define MAP_KEY_EQ(k0,k1)        (!memcmp( (k0)->uc, (k1)->uc, 32UL ))
      63           0 : #define MAP_KEY_HASH(key,seed)   (seed^fd_ulong_load_8( (key)->uc ))
      64             : #include "../../util/tmpl/fd_map_chain.c"
      65             : 
      66             : #define POOL_NAME fd_policy_peer_pool
      67           0 : #define POOL_T    fd_policy_peer_t
      68             : #include "../../util/tmpl/fd_pool.c"
      69             : 
      70             : #define DLIST_NAME  fd_policy_peer_dlist
      71             : #define DLIST_ELE_T fd_policy_peer_t
      72           0 : #define DLIST_NEXT  dlist.next
      73           0 : #define DLIST_PREV  dlist.prev
      74             : #include "../../util/tmpl/fd_dlist.c"
      75             : 
      76             : /* fd_policy_peers implements the data structures and bookkeeping for
      77             :    selecting repair peers via round-robin. */
      78             : 
      79             : struct fd_policy_peers {
      80             :   fd_policy_peer_t * pool;        /* memory pool of peers */
      81             :   fd_policy_peer_dlist_t * fast;  /* peers with ewma RTT <= FD_POLICY_LATENCY_THRESH */
      82             :   fd_policy_peer_dlist_t * slow;  /* peers with ewma RTT >  FD_POLICY_LATENCY_THRESH or no RTT measured */
      83             :   fd_policy_peer_map_t * map;     /* map keyed by pubkey to peer data */
      84             :   struct {
      85             :      uint cnt;                                /* fast selections since last slow, wraps at FD_POLICY_FAST_PER_SLOW */
      86             :      fd_policy_peer_dlist_iter_t fast_iter;   /* round-robin iterator into fast list */
      87             :      fd_policy_peer_dlist_iter_t slow_iter;   /* round-robin iterator into slow list */
      88             :   } select;
      89             : };
      90             : typedef struct fd_policy_peers fd_policy_peers_t;
      91             : 
      92             : /* Policy parameters start */
      93           0 : #define FD_POLICY_LATENCY_THRESH       100e6L /* less than this is a BEST peer, otherwise a WORST peer */
      94           0 : #define FD_POLICY_FAST_PER_SLOW        6U     /* pick 6 fast peers per 1 slow peer */
      95           0 : #define FD_POLICY_EWMA_ALPHA_DENOM     8UL    /* EWMA weight = 1/DENOM, i.e. ewma = 7/8*old + 1/8*sample */
      96             : /* Policy parameters end */
      97             : 
      98             : struct fd_policy {
      99             :   fd_policy_peers_t peers; /* repair peers (strategy & data) */
     100             :   long              tsmax; /* maximum time for an iteration before resetting the DFS to root */
     101             :   long              tsref; /* reference timestamp for resetting DFS */
     102             : 
     103             :   fd_rnonce_ss_t    rnonce_ss[1];
     104             : 
     105             :   ulong turbine_slot0;
     106             : };
     107             : typedef struct fd_policy fd_policy_t;
     108             : 
     109             : /* Constructors */
     110             : 
     111             : /* fd_policy_{align,footprint} return the required alignment and
     112             :    footprint of a memory region suitable for use as policy with up to
     113             :    ele_max eles and vote_max votes. */
     114             : 
     115             : FD_FN_CONST static inline ulong
     116           0 : fd_policy_align( void ) {
     117           0 :   return 128UL;
     118           0 : }
     119             : 
     120             : FD_FN_CONST static inline ulong
     121           0 : fd_policy_footprint( ulong peer_max ) {
     122           0 :   ulong peer_chain_cnt = fd_policy_peer_map_chain_cnt_est( peer_max );
     123           0 :   return FD_LAYOUT_FINI(
     124           0 :     FD_LAYOUT_APPEND(
     125           0 :     FD_LAYOUT_APPEND(
     126           0 :     FD_LAYOUT_APPEND(
     127           0 :     FD_LAYOUT_APPEND(
     128           0 :     FD_LAYOUT_APPEND(
     129           0 :     FD_LAYOUT_INIT,
     130           0 :       fd_policy_align(),            sizeof(fd_policy_t)                             ),
     131           0 :       fd_policy_peer_map_align(),   fd_policy_peer_map_footprint ( peer_chain_cnt ) ),
     132           0 :       fd_policy_peer_pool_align(),  fd_policy_peer_pool_footprint( peer_max )       ),
     133           0 :       fd_policy_peer_dlist_align(), fd_policy_peer_dlist_footprint()                ),
     134           0 :       fd_policy_peer_dlist_align(), fd_policy_peer_dlist_footprint()                ),
     135           0 :     fd_policy_align() );
     136           0 : }
     137             : 
     138             : /* fd_policy_new formats an unused memory region for use as a policy.
     139             :    mem is a non-NULL pointer to this region in the local address space
     140             :    with the required footprint and alignment.  rnonce_ss is copied
     141             :    locally, so the read interest is not retained after this function
     142             :    returns. */
     143             : 
     144             : void *
     145             : fd_policy_new( void * shmem, ulong peer_max, ulong seed, fd_rnonce_ss_t const * rnonce_ss );
     146             : 
     147             : /* fd_policy_join joins the caller to the policy.  policy points to the
     148             :    first byte of the memory region backing the policy in the caller's
     149             :    address space.  Returns a pointer in the local address space to
     150             :    policy on success. */
     151             : 
     152             : fd_policy_t *
     153             : fd_policy_join( void * policy );
     154             : 
     155             : /* fd_policy_leave leaves a current local join.  Returns a pointer to
     156             :    the underlying shared memory region on success and NULL on failure
     157             :    (logs details).  Reasons for failure include policy is NULL. */
     158             : 
     159             : void *
     160             : fd_policy_leave( fd_policy_t const * policy );
     161             : 
     162             : /* fd_policy_delete unformats a memory region used as a policy.  Assumes
     163             :    only the nobody is joined to the region.  Returns a pointer to the
     164             :    underlying shared memory region or NULL if used obviously in error
     165             :    (e.g. policy is obviously not a policy ... logs details).  The
     166             :    ownership of the memory region is transferred to the caller. */
     167             : 
     168             : void *
     169             : fd_policy_delete( void * policy );
     170             : 
     171             : /* fd_policy_next returns the next repair request that should be made.
     172             :    Currently wraps on top of the forest iterator, but also handles
     173             :    making orphan requests and highest shred requests.  For non-normal
     174             :    repair requests, policy uses the dedup cache to deduplicate requests.
     175             :    For all normal requests, the caller must check the dedup cache before
     176             :    making a request. */
     177             : 
     178             : fd_repair_msg_t const *
     179             : fd_policy_next( fd_policy_t * policy, fd_reqlim_t * dedup, fd_forest_t * forest, fd_repair_t * repair, long now, ulong highest_known_slot, int * charge_busy );
     180             : 
     181             : /* fd_policy_peer_upsert upserts a peer into the policy.  If the peer
     182             :    does not exist, it is created.  If the peer already exists, it is
     183             :    updated.  Returns a pointer to the peer if a new peer was created,
     184             :    otherwise NULL (including on updates). */
     185             : fd_policy_peer_t const *
     186             : fd_policy_peer_upsert( fd_policy_t * policy, fd_pubkey_t const * key, fd_ip4_port_t const * addr );
     187             : 
     188             : fd_policy_peer_t *
     189             : fd_policy_peer_query( fd_policy_t * policy, fd_pubkey_t const * key );
     190             : 
     191             : int
     192             : fd_policy_peer_remove( fd_policy_t * policy, fd_pubkey_t const * key );
     193             : 
     194             : fd_pubkey_t const *
     195             : fd_policy_peer_select( fd_policy_t * policy );
     196             : 
     197             : void
     198             : fd_policy_peer_request_update( fd_policy_t * policy, fd_pubkey_t const * to );
     199             : 
     200             : static inline fd_policy_peer_dlist_t *
     201           0 : fd_policy_peer_latency_bucket( fd_policy_t * policy, long lat, ulong res_cnt ) {
     202           0 :    if( res_cnt == 0 || lat > FD_POLICY_LATENCY_THRESH ) return policy->peers.slow;
     203           0 :    return policy->peers.fast;
     204           0 : }
     205             : 
     206             : void
     207             : fd_policy_peer_response_update( fd_policy_t * policy, fd_pubkey_t const * to, long rtt );
     208             : 
     209             : void
     210             : fd_policy_set_turbine_slot0( fd_policy_t * policy, ulong slot );
     211             : 
     212             : #endif /* HEADER_fd_src_choreo_policy_fd_policy_h */