fib/trie.h

   1 /* SPDX-License-Identifier: BSD-3-Clause
   2  * Copyright(c) 2018 Vladimir Medvedkin <medvedkinv@gmail.com>
   3  * Copyright(c) 2019 Intel Corporation
   4  */
   5
   6 #ifndef _TRIE_H_
   7 #define _TRIE_H_
   8
   9 /**
  10  * @file
  11  * RTE IPv6 Longest Prefix Match (LPM)
  12  */
  13 #include <rte_prefetch.h>
  14 #include <rte_branch_prediction.h>
  15
  16 #ifdef __cplusplus
  17 extern "C" {
  18 #endif
  19
  20 /* @internal Total number of tbl24 entries. */
  21 #define TRIE_TBL24_NUM_ENT      (1 << 24)
  22 /* Maximum depth value possible for IPv6 LPM. */
  23 #define TRIE_MAX_DEPTH          128
  24 /* @internal Number of entries in a tbl8 group. */
  25 #define TRIE_TBL8_GRP_NUM_ENT   256ULL
  26 /* @internal Total number of tbl8 groups in the tbl8. */
  27 #define TRIE_TBL8_NUM_GROUPS    65536
  28 /* @internal bitmask with valid and valid_group fields set */
  29 #define TRIE_EXT_ENT            1
  30
  31 #define BITMAP_SLAB_BIT_SIZE_LOG2       6
  32 #define BITMAP_SLAB_BIT_SIZE            (1ULL << BITMAP_SLAB_BIT_SIZE_LOG2)
  33 #define BITMAP_SLAB_BITMASK             (BITMAP_SLAB_BIT_SIZE - 1)
  34
  35 struct rte_trie_tbl {
  36         uint32_t        number_tbl8s;   /**< Total number of tbl8s */
  37         uint32_t        rsvd_tbl8s;     /**< Number of reserved tbl8s */
  38         uint32_t        cur_tbl8s;      /**< Current cumber of tbl8s */
  39         uint64_t        def_nh;         /**< Default next hop */
  40         enum rte_fib_trie_nh_sz nh_sz;  /**< Size of nexthop entry */
  41         uint64_t        *tbl8;          /**< tbl8 table. */
  42         uint32_t        *tbl8_pool;     /**< bitmap containing free tbl8 idxes*/
  43         uint32_t        tbl8_pool_pos;
  44         /* tbl24 table. */
  45         __extension__ uint64_t  tbl24[0] __rte_cache_aligned;
  46 };
  47
  48 static inline uint32_t
  49 get_tbl24_idx(const uint8_t *ip)
  50 {
  51         return ip[0] << 16|ip[1] << 8|ip[2];
  52 }
  53
  54 static inline void *
  55 get_tbl24_p(struct rte_trie_tbl *dp, const uint8_t *ip, uint8_t nh_sz)
  56 {
  57         uint32_t tbl24_idx;
  58
  59         tbl24_idx = get_tbl24_idx(ip);
  60         return (void *)&((uint8_t *)dp->tbl24)[tbl24_idx << nh_sz];
  61 }
  62
  63 static inline uint8_t
  64 bits_in_nh(uint8_t nh_sz)
  65 {
  66         return 8 * (1 << nh_sz);
  67 }
  68
  69 static inline uint64_t
  70 get_max_nh(uint8_t nh_sz)
  71 {
  72         return ((1ULL << (bits_in_nh(nh_sz) - 1)) - 1);
  73 }
  74
  75 static inline uint64_t
  76 lookup_msk(uint8_t nh_sz)
  77 {
  78         return ((1ULL << ((1 << (nh_sz + 3)) - 1)) << 1) - 1;
  79 }
  80
  81 static inline uint8_t
  82 get_psd_idx(uint32_t val, uint8_t nh_sz)
  83 {
  84         return val & ((1 << (3 - nh_sz)) - 1);
  85 }
  86
  87 static inline uint32_t
  88 get_tbl_pos(uint32_t val, uint8_t nh_sz)
  89 {
  90         return val >> (3 - nh_sz);
  91 }
  92
  93 static inline uint64_t
  94 get_tbl_val_by_idx(uint64_t *tbl, uint32_t idx, uint8_t nh_sz)
  95 {
  96         return ((tbl[get_tbl_pos(idx, nh_sz)] >> (get_psd_idx(idx, nh_sz) *
  97                 bits_in_nh(nh_sz))) & lookup_msk(nh_sz));
  98 }
  99
 100 static inline void *
 101 get_tbl_p_by_idx(uint64_t *tbl, uint64_t idx, uint8_t nh_sz)
 102 {
 103         return (uint8_t *)tbl + (idx << nh_sz);
 104 }
 105
 106 static inline int
 107 is_entry_extended(uint64_t ent)
 108 {
 109         return (ent & TRIE_EXT_ENT) == TRIE_EXT_ENT;
 110 }
 111
 112 #define LOOKUP_FUNC(suffix, type, nh_sz)                                \
 113 static inline void rte_trie_lookup_bulk_##suffix(void *p,               \
 114         uint8_t ips[][RTE_FIB6_IPV6_ADDR_SIZE],                         \
 115         uint64_t *next_hops, const unsigned int n)                      \
 116 {                                                                       \
 117         struct rte_trie_tbl *dp = (struct rte_trie_tbl *)p;             \
 118         uint64_t tmp;                                                   \
 119         uint32_t i, j;                                                  \
 120                                                                         \
 121         for (i = 0; i < n; i++) {                                       \
 122                 tmp = ((type *)dp->tbl24)[get_tbl24_idx(&ips[i][0])];   \
 123                 j = 3;                                                  \
 124                 while (is_entry_extended(tmp)) {                        \
 125                         tmp = ((type *)dp->tbl8)[ips[i][j++] +          \
 126                                 ((tmp >> 1) * TRIE_TBL8_GRP_NUM_ENT)];  \
 127                 }                                                       \
 128                 next_hops[i] = tmp >> 1;                                \
 129         }                                                               \
 130 }
 131 LOOKUP_FUNC(2b, uint16_t, 1)
 132 LOOKUP_FUNC(4b, uint32_t, 2)
 133 LOOKUP_FUNC(8b, uint64_t, 3)
 134
 135 void *
 136 trie_create(const char *name, int socket_id, struct rte_fib6_conf *conf);
 137
 138 void
 139 trie_free(void *p);
 140
 141 rte_fib6_lookup_fn_t
 142 trie_get_lookup_fn(void *p, enum rte_fib6_lookup_type type);
 143
 144 int
 145 trie_modify(struct rte_fib6 *fib, const uint8_t ip[RTE_FIB6_IPV6_ADDR_SIZE],
 146         uint8_t depth, uint64_t next_hop, int op);
 147
 148
 149 #ifdef __cplusplus
 150 }
 151 #endif
 152
 153 #endif /* _TRIE_H_ */