Branch data     Line data    Source code

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