Line data    Source code

       1             : #ifndef HEADER_fd_src_waltz_ip_fd_fib4_private_h
       2             : #define HEADER_fd_src_waltz_ip_fd_fib4_private_h
       3             : 
       4             : #include "fd_fib4.h"
       5             : #include "../../util/fd_util.h"
       6             : 
       7             : #if FD_HAS_X86
       8             : #include <immintrin.h>
       9             : #endif
      10             : 
      11             : struct __attribute__((aligned(16))) fd_fib4_key {
      12             :   /* FIXME optimize this to 8 bytes? */
      13             :   uint addr;       /* prefix bits, little endian (low bits outside of mask are undefined) */
      14             :   uint mask;       /* bit pattern */
      15             :   uint prio;       /* lower is higher */
      16             :   int  mask_bits;  /* precompute mask bits for comparison */
      17             : };
      18             : 
      19             : typedef struct fd_fib4_key fd_fib4_key_t;
      20             : 
      21             : /* Hashmap private APIs */
      22             : union __attribute__((aligned(16))) fd_fib4_hmap_entry {
      23             :   struct {
      24             :     uint dst_addr; /* Little endian. All 32-bits defined */
      25             :     uint hash;
      26             :     fd_fib4_hop_t next_hop; /* 16 bytes */
      27             :   };
      28             : #if FD_HAS_X86
      29             :   __m128i xmm[2];
      30             : #endif
      31             : #if FD_HAS_AVX
      32             :   __m256i avx[1];
      33             : #endif
      34             : };
      35             : 
      36             : typedef union fd_fib4_hmap_entry fd_fib4_hmap_entry_t;
      37             : 
      38             : /* fd_fib4_hmap_entry_st stores from src into dst. Assumes no other writers,
      39             :    and that src is non-volatile. Best effort for atomicity, but only guaranteed
      40             :    when FD_HAS_AVX. */
      41             : static inline void
      42             : fd_fib4_hmap_entry_st( fd_fib4_hmap_entry_t       * dst,
      43         246 :                        fd_fib4_hmap_entry_t const * src ) {
      44         246 : # if FD_HAS_AVX
      45         246 :   FD_VOLATILE( dst->avx[0] ) = src->avx[0];
      46             : # else
      47             :   FD_VOLATILE( dst->dst_addr ) = src->dst_addr;
      48             :   FD_VOLATILE( dst->hash     ) = src->hash;
      49             :   FD_VOLATILE( dst->next_hop ) = src->next_hop;
      50             : #endif
      51         246 : }
      52             : 
      53             : /* fd_fib4_hmap_entry_ld loads from src into dst.
      54             :    Best effort for atomicity, but only guaranteed when FD_HAS_AVX.
      55             :    Assumes that dst is non-volatile. */
      56             : static inline void
      57             : fd_fib4_hmap_entry_ld( fd_fib4_hmap_entry_t       * dst,
      58         243 :                        fd_fib4_hmap_entry_t const * src ) {
      59             : 
      60         243 : # if FD_HAS_AVX
      61         243 :   dst->avx[0] = FD_VOLATILE_CONST( src->avx[0] );
      62             : # elif FD_HAS_X86
      63             :   dst->xmm[0] = FD_VOLATILE_CONST( src->xmm[0] );
      64             :   dst->xmm[1] = FD_VOLATILE_CONST( src->xmm[1] );
      65             : # else
      66             :   dst->dst_addr = FD_VOLATILE_CONST( src->dst_addr );
      67             :   dst->hash     = FD_VOLATILE_CONST( src->hash );
      68             :   dst->next_hop = FD_VOLATILE_CONST( src->next_hop );
      69             : #endif
      70         243 : }
      71             : 
      72             : static inline uint
      73         882 : fd_fib4_hmap_entry_hash( uint dst_addr, ulong seed ) {
      74         882 :   return fd_uint_hash( dst_addr ^ ((uint)seed) );
      75         882 : }
      76             : 
      77             : #define MAP_NAME            fd_fib4_hmap
      78        1101 : #define MAP_ELE_T           fd_fib4_hmap_entry_t
      79             : #define MAP_KEY_T           uint
      80        4401 : #define MAP_KEY             dst_addr
      81         636 : #define MAP_KEY_HASH(k,s)   fd_fib4_hmap_entry_hash( (*(k)), (s) )
      82             : #define MAP_ELE_MOVE(c,d,s) do { fd_fib4_hmap_entry_t * _src = (s); fd_fib4_hmap_entry_st( (d), _src ); _src->dst_addr = 0; } while(0)
      83             : 
      84             : #include "../../util/tmpl/fd_map_slot.c"
      85             : 
      86             : FD_STATIC_ASSERT( sizeof( fd_fib4_hmap_t)<=sizeof(( (fd_fib4_t){0}).hmap_join), "hmap_join is too small" );
      87             : 
      88             : /* fd_fib4_hmap_query_hop queries the /32 routing table for the next hop
      89             :    for the given destination address. Attempts (but does not guarantee) atomicity.
      90             :    If the destination address is not found, returns a route with rtype
      91             :    set to UNSPEC. The result is not guaranteed to be valid - the caller
      92             :    is responsible for validating the result. */
      93             : 
      94             : static inline fd_fib4_hop_t
      95             : fd_fib4_hmap_query_hop( fd_fib4_hmap_t const * map,
      96         390 :                         uint                   dst_addr ) {
      97         390 :   fd_fib4_hmap_entry_t const * entry = fd_fib4_hmap_query( map, &dst_addr );
      98         390 :   if( !entry ) return (fd_fib4_hop_t){0};
      99             : 
     100         213 :   fd_fib4_hmap_entry_t hmap_entry;
     101         213 :   fd_fib4_hmap_entry_ld( &hmap_entry, entry );
     102             : 
     103         213 :   return hmap_entry.next_hop;
     104         390 : }
     105             : 
     106             : struct __attribute__((aligned(FD_FIB4_ALIGN))) fd_fib4_priv {
     107             :   ulong hmap_offset;
     108             :   ulong hmap_cnt;
     109             :   ulong hmap_max;
     110             :   ulong generation;
     111             :   ulong cnt;
     112             :   ulong max;
     113             :   ulong hop_off;
     114             :   ulong seed;
     115             :   /* fd_fib4_key_t[] follows */
     116             :   /* fd_fib4_hop_t[] follows */
     117             :   /* hmap_mem        follows */
     118             : };
     119             : typedef struct fd_fib4_priv fd_fib4_priv_t;
     120             : 
     121             : FD_FN_CONST static inline ulong
     122         384 : fd_fib4_key_tbl_laddr( fd_fib4_priv_t const * fib ) {
     123         384 :   return (ulong)fib + sizeof(fd_fib4_priv_t);
     124         384 : }
     125             : 
     126             : FD_FN_PURE static inline ulong
     127         384 : fd_fib4_hop_tbl_laddr( fd_fib4_priv_t const * fib ) {
     128         384 :   return (ulong)fib + fib->hop_off;
     129         384 : }
     130             : 
     131         237 : FD_FN_CONST static inline fd_fib4_key_t const * fd_fib4_key_tbl_const( fd_fib4_priv_t const * fib ) { return (fd_fib4_key_t const *)fd_fib4_key_tbl_laddr( fib ); }
     132         147 : FD_FN_CONST static inline fd_fib4_key_t *       fd_fib4_key_tbl      ( fd_fib4_priv_t *       fib ) { return (fd_fib4_key_t *)      fd_fib4_key_tbl_laddr( fib ); }
     133         237 : FD_FN_CONST static inline fd_fib4_hop_t const * fd_fib4_hop_tbl_const( fd_fib4_priv_t const * fib ) { return (fd_fib4_hop_t const *)fd_fib4_hop_tbl_laddr( fib ); }
     134         147 : FD_FN_CONST static inline fd_fib4_hop_t *       fd_fib4_hop_tbl      ( fd_fib4_priv_t *       fib ) { return (fd_fib4_hop_t *)      fd_fib4_hop_tbl_laddr( fib ); }
     135             : 
     136          63 : static inline void *  fd_fib4_hmap_mem( fd_fib4_priv_t * priv ) {
     137          63 :   return (void *)( (ulong)priv + priv->hmap_offset);
     138          63 : }
     139             : 
     140             : /* Get the hashmap's total capacity (50% extra capacity beyond the requested size to optimize performance) */
     141         117 : static inline ulong   fd_fib4_hmap_get_ele_max   ( ulong max_cnt  ) { return fd_ulong_pow2_up( max_cnt + ( max_cnt>>1 ) ); }
     142             : /* Get the hashmap's probe limit (75% of total capacity). Higher than requested size to avoid probe failure */
     143          63 : static inline ulong   fd_fib4_hmap_get_probe_max ( ulong elem_max ) { return elem_max - ( elem_max>>2 );                   }
     144             : 
     145             : #endif /* HEADER_fd_src_waltz_ip_fd_fib4_private_h */