Line data    Source code

       1             : #ifndef HEADER_fd_src_discof_repair_fd_reqlim_h
       2             : #define HEADER_fd_src_discof_repair_fd_reqlim_h
       3             : 
       4             : /* fd_reqlim implements a dedup cache for already sent Repair requests.
       5             :    It is backed by a map and linked list, in which the least recently
       6             :    used (oldest Repair request) in the map is evicted when the map is
       7             :    full. */
       8             : 
       9             : #include "../../util/fd_util.h"
      10             : 
      11             : #define FD_REQLIM_DEDUP_TIMEOUT 80000000L /* 80 ms - how long to wait before re-requesting the same shred */
      12             : 
      13             : FD_STATIC_ASSERT( 16000000L < FD_REQLIM_DEDUP_TIMEOUT, "DEDUP_TIMEOUT must be greater than 16ms to avoid rnonces from trivially clashing" );
      14             : 
      15             : /* fd_reqlim_ele describes an element in the dedup cache.  The key
      16             :    compactly encodes an fd_repair_req_t.
      17             : 
      18             :    | kind (4 bits) | slot (32 bits) | shred_idx (28 bits) |
      19             :    | bits 63:60    | bits 59:28     | bits 27:0           |
      20             : 
      21             :    kind uses the FD_REPAIR_KIND_* wire values directly.
      22             : 
      23             :    Note the common header (sig, from, to, ts, nonce) is not included. */
      24             : 
      25             : struct fd_reqlim_ele {
      26             :   ulong key;      /* compact encoding of fd_repair_req_t detailed above */
      27             :   ulong prev;     /* reserved by lru */
      28             :   ulong next;
      29             :   ulong hash;     /* reserved by pool and map_chain */
      30             :   long  req_ts;   /* timestamp when the request was sent */
      31             : };
      32             : typedef struct fd_reqlim_ele fd_reqlim_ele_t;
      33             : 
      34             : FD_FN_CONST static inline ulong
      35           0 : fd_reqlim_key( uint kind, ulong slot, uint shred_idx ) {
      36           0 :   ulong k = (ulong)fd_uint_extract_lsb( kind, 4 );
      37           0 :   ulong i = (ulong)fd_uint_extract_lsb( shred_idx, 28 );
      38           0 :   ulong s = fd_ulong_extract_lsb( slot, 32 );
      39           0 :   return k << 60 | s << 28 | i;
      40           0 : }
      41             : 
      42             : #define POOL_NAME fd_reqlim_pool
      43           0 : #define POOL_T    fd_reqlim_ele_t
      44           0 : #define POOL_NEXT hash
      45             : #include "../../util/tmpl/fd_pool.c"
      46             : 
      47             : #define MAP_NAME  fd_reqlim_map
      48             : #define MAP_ELE_T fd_reqlim_ele_t
      49           0 : #define MAP_NEXT  hash
      50             : #include "../../util/tmpl/fd_map_chain.c"
      51             : 
      52             : #define DLIST_NAME   fd_reqlim_lru
      53             : #define DLIST_ELE_T  fd_reqlim_ele_t
      54           0 : #define DLIST_NEXT   next
      55           0 : #define DLIST_PREV   prev
      56             : #include "../../util/tmpl/fd_dlist.c"
      57             : 
      58             : struct fd_reqlim {
      59             :   fd_reqlim_map_t * map;  /* map of dedup elements */
      60             :   fd_reqlim_ele_t * pool; /* memory pool of dedup elements */
      61             :   fd_reqlim_lru_t * lru;  /* linked list of dedup elements by insertion order */
      62             : };
      63             : typedef struct fd_reqlim fd_reqlim_t;
      64             : 
      65             : /* Constructors */
      66             : 
      67             : FD_FN_CONST static inline ulong
      68           0 : fd_reqlim_align( void ) {
      69           0 :   return 128UL;
      70           0 : }
      71             : 
      72             : FD_FN_CONST static inline ulong
      73           0 : fd_reqlim_footprint( ulong dedup_max ) {
      74           0 :   return FD_LAYOUT_FINI(
      75           0 :     FD_LAYOUT_APPEND(
      76           0 :     FD_LAYOUT_APPEND(
      77           0 :     FD_LAYOUT_APPEND(
      78           0 :     FD_LAYOUT_APPEND(
      79           0 :     FD_LAYOUT_INIT,
      80           0 :       fd_reqlim_align(),      sizeof(fd_reqlim_t)                       ),
      81           0 :       fd_reqlim_map_align(),  fd_reqlim_map_footprint ( dedup_max )     ),
      82           0 :       fd_reqlim_pool_align(), fd_reqlim_pool_footprint( dedup_max )     ),
      83           0 :       fd_reqlim_lru_align(),  fd_reqlim_lru_footprint()                 ),
      84           0 :     fd_reqlim_align() );
      85           0 : }
      86             : 
      87             : /* fd_reqlim_new formats an unused memory region for use as a dedup
      88             :    cache.  mem is a non-NULL pointer to this region in the local address
      89             :    space with the required footprint and alignment. */
      90             : 
      91             : void *
      92             : fd_reqlim_new( void * shmem, ulong dedup_max, ulong seed );
      93             : 
      94             : /* fd_reqlim_join joins the caller to the dedup cache.  Returns a pointer
      95             :    in the local address space to dedup on success. */
      96             : 
      97             : fd_reqlim_t *
      98             : fd_reqlim_join( void * shdedup );
      99             : 
     100             : /* fd_reqlim_leave leaves a current local join. */
     101             : 
     102             : void *
     103             : fd_reqlim_leave( fd_reqlim_t const * dedup );
     104             : 
     105             : /* fd_reqlim_delete unformats a memory region used as a dedup cache. */
     106             : 
     107             : void *
     108             : fd_reqlim_delete( void * dedup );
     109             : 
     110             : /* fd_reqlim_next returns 1 if key is deduped (already sent within the
     111             :    dedup timeout window), 0 otherwise.  When not deduped, the key is
     112             :    inserted/refreshed in the cache with the current timestamp. */
     113             : 
     114             : int
     115             : fd_reqlim_next( fd_reqlim_t * dedup, ulong key, long now );
     116             : 
     117             : /* fd_reqlim_query returns 1 if key is in the dedup cache and was sent
     118             :    within the dedup timeout window, 0 otherwise.  Read-only: does not
     119             :    insert or update any state. */
     120             : 
     121             : int
     122             : fd_reqlim_query( fd_reqlim_t const * dedup, ulong key, long now );
     123             : 
     124             : #endif /* HEADER_fd_src_discof_repair_fd_reqlim_h */