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_INT128
      29             :   uint128 uf[2];
      30             : #endif
      31             : #if FD_HAS_X86
      32             :   __m128i xmm[2];
      33             : #endif
      34             : #if FD_HAS_AVX
      35             :   __m256i avx[1];
      36             : #endif
      37             : };
      38             : 
      39             : typedef union fd_fib4_hmap_entry fd_fib4_hmap_entry_t;
      40             : 
      41             : /* fd_fib4_hmap_entry_st stores from src into dst. Assumes no other writers,
      42             :    and that src is non-volatile. Best effort for atomicity, but only guaranteed
      43             :    when FD_HAS_AVX. */
      44             : static inline void
      45             : fd_fib4_hmap_entry_st( fd_fib4_hmap_entry_t       * dst,
      46         240 :                        fd_fib4_hmap_entry_t const * src ) {
      47         240 : # if FD_HAS_AVX
      48         240 :   FD_VOLATILE( dst->avx[0] ) = src->avx[0];
      49             : # elif FD_HAS_X86
      50             :   FD_VOLATILE( dst->xmm[0] ) = src->xmm[0];
      51             :   FD_VOLATILE( dst->xmm[1] ) = src->xmm[1];
      52             : # elif FD_HAS_INT128
      53             :   FD_VOLATILE( dst->uf[0] )  = src->uf[0];
      54             :   FD_VOLATILE( dst->uf[1] )  = src->uf[1];
      55             : # else
      56             :   FD_VOLATILE( dst->dst_addr ) = src->dst_addr;
      57             :   FD_VOLATILE( dst->hash     ) = src->hash;
      58             :   FD_VOLATILE( dst->next_hop ) = src->next_hop;
      59             : #endif
      60         240 : }
      61             : 
      62             : /* fd_fib4_hmap_entry_ld loads from src into dst.
      63             :    Best effort for atomicity, but only guaranteed when FD_HAS_AVX.
      64             :    Assumes that dst is non-volatile. */
      65             : static inline void
      66             : fd_fib4_hmap_entry_ld( fd_fib4_hmap_entry_t       * dst,
      67         237 :                        fd_fib4_hmap_entry_t const * src ) {
      68             : 
      69         237 : # if FD_HAS_AVX
      70         237 :   dst->avx[0] = FD_VOLATILE_CONST( src->avx[0] );
      71             : # elif FD_HAS_X86
      72             :   dst->xmm[0] = FD_VOLATILE_CONST( src->xmm[0] );
      73             :   dst->xmm[1] = FD_VOLATILE_CONST( src->xmm[1] );
      74             : # elif FD_HAS_INT128
      75             :   dst->uf[0] = FD_VOLATILE_CONST( src->uf[0] );
      76             :   dst->uf[1] = FD_VOLATILE_CONST( src->uf[1] );
      77             : # else
      78             :   dst->dst_addr = FD_VOLATILE_CONST( src->dst_addr );
      79             :   dst->hash     = FD_VOLATILE_CONST( src->hash );
      80             :   dst->next_hop = FD_VOLATILE_CONST( src->next_hop );
      81             : #endif
      82         237 : }
      83             : 
      84             : static inline uint
      85         870 : fd_fib4_hmap_entry_hash( uint dst_addr, ulong seed ) {
      86         870 :   return fd_uint_hash( dst_addr ^ ((uint)seed) );
      87         870 : }
      88             : 
      89             : #define MAP_NAME            fd_fib4_hmap
      90        1095 : #define MAP_ELE_T           fd_fib4_hmap_entry_t
      91             : #define MAP_KEY_T           uint
      92        4389 : #define MAP_KEY             dst_addr
      93         630 : #define MAP_KEY_HASH(k,s)   fd_fib4_hmap_entry_hash( (*(k)), (s) )
      94             : #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)
      95             : 
      96             : #include "../../util/tmpl/fd_map_slot.c"
      97             : 
      98             : FD_STATIC_ASSERT( sizeof( fd_fib4_hmap_t)<=sizeof(( (fd_fib4_t){0}).hmap_join), "hmap_join is too small" );
      99             : 
     100             : /* fd_fib4_hmap_query_hop queries the /32 routing table for the next hop
     101             :    for the given destination address. Attempts (but does not guarantee) atomicity.
     102             :    If the destination address is not found, returns a route with rtype
     103             :    set to UNSPEC. The result is not guaranteed to be valid - the caller
     104             :    is responsible for validating the result. */
     105             : 
     106             : static inline fd_fib4_hop_t
     107             : fd_fib4_hmap_query_hop( fd_fib4_hmap_t const * map,
     108         390 :                         uint                   dst_addr ) {
     109         390 :   fd_fib4_hmap_entry_t const * entry = fd_fib4_hmap_query( map, &dst_addr );
     110         390 :   if( !entry ) return (fd_fib4_hop_t){0};
     111             : 
     112         213 :   fd_fib4_hmap_entry_t hmap_entry;
     113         213 :   fd_fib4_hmap_entry_ld( &hmap_entry, entry );
     114             : 
     115         213 :   return hmap_entry.next_hop;
     116         390 : }
     117             : 
     118             : struct __attribute__((aligned(FD_FIB4_ALIGN))) fd_fib4_priv {
     119             :   ulong hmap_offset;
     120             :   ulong hmap_cnt;
     121             :   ulong hmap_max;
     122             :   ulong generation;
     123             :   ulong cnt;
     124             :   ulong max;
     125             :   ulong hop_off;
     126             :   ulong seed;
     127             :   /* fd_fib4_key_t[] follows */
     128             :   /* fd_fib4_hop_t[] follows */
     129             :   /* hmap_mem        follows */
     130             : };
     131             : typedef struct fd_fib4_priv fd_fib4_priv_t;
     132             : 
     133             : FD_FN_CONST static inline ulong
     134         381 : fd_fib4_key_tbl_laddr( fd_fib4_priv_t const * fib ) {
     135         381 :   return (ulong)fib + sizeof(fd_fib4_priv_t);
     136         381 : }
     137             : 
     138             : FD_FN_PURE static inline ulong
     139         381 : fd_fib4_hop_tbl_laddr( fd_fib4_priv_t const * fib ) {
     140         381 :   return (ulong)fib + fib->hop_off;
     141         381 : }
     142             : 
     143         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 ); }
     144         144 : 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 ); }
     145         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 ); }
     146         144 : 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 ); }
     147             : 
     148          63 : static inline void *  fd_fib4_hmap_mem( fd_fib4_priv_t * priv ) {
     149          63 :   return (void *)( (ulong)priv + priv->hmap_offset);
     150          63 : }
     151             : 
     152             : /* Get the hashmap's total capacity (50% extra capacity beyond the requested size to optimize performance) */
     153         117 : static inline ulong   fd_fib4_hmap_get_ele_max   ( ulong max_cnt  ) { return fd_ulong_pow2_up( max_cnt + ( max_cnt>>1 ) ); }
     154             : /* Get the hashmap's probe limit (75% of total capacity). Higher than requested size to avoid probe failure */
     155          63 : static inline ulong   fd_fib4_hmap_get_probe_max ( ulong elem_max ) { return elem_max - ( elem_max>>2 );                   }
     156             : 
     157             : #endif /* HEADER_fd_src_waltz_ip_fd_fib4_private_h */