lib: remove C++ include guard from private headers
[dpdk.git] / lib / fib / dir24_8.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 _DIR24_8_H_
7 #define _DIR24_8_H_
8
9 #include <rte_prefetch.h>
10 #include <rte_branch_prediction.h>
11
12 /**
13  * @file
14  * DIR24_8 algorithm
15  */
16
17 #define DIR24_8_TBL24_NUM_ENT           (1 << 24)
18 #define DIR24_8_TBL8_GRP_NUM_ENT        256U
19 #define DIR24_8_EXT_ENT                 1
20 #define DIR24_8_TBL24_MASK              0xffffff00
21
22 #define BITMAP_SLAB_BIT_SIZE_LOG2       6
23 #define BITMAP_SLAB_BIT_SIZE            (1 << BITMAP_SLAB_BIT_SIZE_LOG2)
24 #define BITMAP_SLAB_BITMASK             (BITMAP_SLAB_BIT_SIZE - 1)
25
26 struct dir24_8_tbl {
27         uint32_t        number_tbl8s;   /**< Total number of tbl8s */
28         uint32_t        rsvd_tbl8s;     /**< Number of reserved tbl8s */
29         uint32_t        cur_tbl8s;      /**< Current number of tbl8s */
30         enum rte_fib_dir24_8_nh_sz      nh_sz;  /**< Size of nexthop entry */
31         uint64_t        def_nh;         /**< Default next hop */
32         uint64_t        *tbl8;          /**< tbl8 table. */
33         uint64_t        *tbl8_idxes;    /**< bitmap containing free tbl8 idxes*/
34         /* tbl24 table. */
35         __extension__ uint64_t  tbl24[0] __rte_cache_aligned;
36 };
37
38 static inline void *
39 get_tbl24_p(struct dir24_8_tbl *dp, uint32_t ip, uint8_t nh_sz)
40 {
41         return (void *)&((uint8_t *)dp->tbl24)[(ip &
42                 DIR24_8_TBL24_MASK) >> (8 - nh_sz)];
43 }
44
45 static inline  uint8_t
46 bits_in_nh(uint8_t nh_sz)
47 {
48         return 8 * (1 << nh_sz);
49 }
50
51 static inline uint64_t
52 get_max_nh(uint8_t nh_sz)
53 {
54         return ((1ULL << (bits_in_nh(nh_sz) - 1)) - 1);
55 }
56
57 static  inline uint32_t
58 get_tbl24_idx(uint32_t ip)
59 {
60         return ip >> 8;
61 }
62
63 static  inline uint32_t
64 get_tbl8_idx(uint32_t res, uint32_t ip)
65 {
66         return (res >> 1) * DIR24_8_TBL8_GRP_NUM_ENT + (uint8_t)ip;
67 }
68
69 static inline uint64_t
70 lookup_msk(uint8_t nh_sz)
71 {
72         return ((1ULL << ((1 << (nh_sz + 3)) - 1)) << 1) - 1;
73 }
74
75 static inline uint8_t
76 get_psd_idx(uint32_t val, uint8_t nh_sz)
77 {
78         return val & ((1 << (3 - nh_sz)) - 1);
79 }
80
81 static inline uint32_t
82 get_tbl_idx(uint32_t val, uint8_t nh_sz)
83 {
84         return val >> (3 - nh_sz);
85 }
86
87 static inline uint64_t
88 get_tbl24(struct dir24_8_tbl *dp, uint32_t ip, uint8_t nh_sz)
89 {
90         return ((dp->tbl24[get_tbl_idx(get_tbl24_idx(ip), nh_sz)] >>
91                 (get_psd_idx(get_tbl24_idx(ip), nh_sz) *
92                 bits_in_nh(nh_sz))) & lookup_msk(nh_sz));
93 }
94
95 static inline uint64_t
96 get_tbl8(struct dir24_8_tbl *dp, uint32_t res, uint32_t ip, uint8_t nh_sz)
97 {
98         return ((dp->tbl8[get_tbl_idx(get_tbl8_idx(res, ip), nh_sz)] >>
99                 (get_psd_idx(get_tbl8_idx(res, ip), nh_sz) *
100                 bits_in_nh(nh_sz))) & lookup_msk(nh_sz));
101 }
102
103 static inline int
104 is_entry_extended(uint64_t ent)
105 {
106         return (ent & DIR24_8_EXT_ENT) == DIR24_8_EXT_ENT;
107 }
108
109 #define LOOKUP_FUNC(suffix, type, bulk_prefetch, nh_sz)                 \
110 static inline void dir24_8_lookup_bulk_##suffix(void *p, const uint32_t *ips, \
111         uint64_t *next_hops, const unsigned int n)                      \
112 {                                                                       \
113         struct dir24_8_tbl *dp = (struct dir24_8_tbl *)p;               \
114         uint64_t tmp;                                                   \
115         uint32_t i;                                                     \
116         uint32_t prefetch_offset =                                      \
117                 RTE_MIN((unsigned int)bulk_prefetch, n);                \
118                                                                         \
119         for (i = 0; i < prefetch_offset; i++)                           \
120                 rte_prefetch0(get_tbl24_p(dp, ips[i], nh_sz));          \
121         for (i = 0; i < (n - prefetch_offset); i++) {                   \
122                 rte_prefetch0(get_tbl24_p(dp,                           \
123                         ips[i + prefetch_offset], nh_sz));              \
124                 tmp = ((type *)dp->tbl24)[ips[i] >> 8];                 \
125                 if (unlikely(is_entry_extended(tmp)))                   \
126                         tmp = ((type *)dp->tbl8)[(uint8_t)ips[i] +      \
127                                 ((tmp >> 1) * DIR24_8_TBL8_GRP_NUM_ENT)]; \
128                 next_hops[i] = tmp >> 1;                                \
129         }                                                               \
130         for (; i < n; i++) {                                            \
131                 tmp = ((type *)dp->tbl24)[ips[i] >> 8];                 \
132                 if (unlikely(is_entry_extended(tmp)))                   \
133                         tmp = ((type *)dp->tbl8)[(uint8_t)ips[i] +      \
134                                 ((tmp >> 1) * DIR24_8_TBL8_GRP_NUM_ENT)]; \
135                 next_hops[i] = tmp >> 1;                                \
136         }                                                               \
137 }                                                                       \
138
139 LOOKUP_FUNC(1b, uint8_t, 5, 0)
140 LOOKUP_FUNC(2b, uint16_t, 6, 1)
141 LOOKUP_FUNC(4b, uint32_t, 15, 2)
142 LOOKUP_FUNC(8b, uint64_t, 12, 3)
143
144 static inline void
145 dir24_8_lookup_bulk(struct dir24_8_tbl *dp, const uint32_t *ips,
146         uint64_t *next_hops, const unsigned int n, uint8_t nh_sz)
147 {
148         uint64_t tmp;
149         uint32_t i;
150         uint32_t prefetch_offset = RTE_MIN(15U, n);
151
152         for (i = 0; i < prefetch_offset; i++)
153                 rte_prefetch0(get_tbl24_p(dp, ips[i], nh_sz));
154         for (i = 0; i < (n - prefetch_offset); i++) {
155                 rte_prefetch0(get_tbl24_p(dp, ips[i + prefetch_offset],
156                         nh_sz));
157                 tmp = get_tbl24(dp, ips[i], nh_sz);
158                 if (unlikely(is_entry_extended(tmp)))
159                         tmp = get_tbl8(dp, tmp, ips[i], nh_sz);
160
161                 next_hops[i] = tmp >> 1;
162         }
163         for (; i < n; i++) {
164                 tmp = get_tbl24(dp, ips[i], nh_sz);
165                 if (unlikely(is_entry_extended(tmp)))
166                         tmp = get_tbl8(dp, tmp, ips[i], nh_sz);
167
168                 next_hops[i] = tmp >> 1;
169         }
170 }
171
172 static inline void
173 dir24_8_lookup_bulk_0(void *p, const uint32_t *ips,
174         uint64_t *next_hops, const unsigned int n)
175 {
176         struct dir24_8_tbl *dp = (struct dir24_8_tbl *)p;
177
178         dir24_8_lookup_bulk(dp, ips, next_hops, n, 0);
179 }
180
181 static inline void
182 dir24_8_lookup_bulk_1(void *p, const uint32_t *ips,
183         uint64_t *next_hops, const unsigned int n)
184 {
185         struct dir24_8_tbl *dp = (struct dir24_8_tbl *)p;
186
187         dir24_8_lookup_bulk(dp, ips, next_hops, n, 1);
188 }
189
190 static inline void
191 dir24_8_lookup_bulk_2(void *p, const uint32_t *ips,
192         uint64_t *next_hops, const unsigned int n)
193 {
194         struct dir24_8_tbl *dp = (struct dir24_8_tbl *)p;
195
196         dir24_8_lookup_bulk(dp, ips, next_hops, n, 2);
197 }
198
199 static inline void
200 dir24_8_lookup_bulk_3(void *p, const uint32_t *ips,
201         uint64_t *next_hops, const unsigned int n)
202 {
203         struct dir24_8_tbl *dp = (struct dir24_8_tbl *)p;
204
205         dir24_8_lookup_bulk(dp, ips, next_hops, n, 3);
206 }
207
208 static inline void
209 dir24_8_lookup_bulk_uni(void *p, const uint32_t *ips,
210         uint64_t *next_hops, const unsigned int n)
211 {
212         struct dir24_8_tbl *dp = (struct dir24_8_tbl *)p;
213         uint64_t tmp;
214         uint32_t i;
215         uint32_t prefetch_offset = RTE_MIN(15U, n);
216         uint8_t nh_sz = dp->nh_sz;
217
218         for (i = 0; i < prefetch_offset; i++)
219                 rte_prefetch0(get_tbl24_p(dp, ips[i], nh_sz));
220         for (i = 0; i < (n - prefetch_offset); i++) {
221                 rte_prefetch0(get_tbl24_p(dp, ips[i + prefetch_offset],
222                         nh_sz));
223                 tmp = get_tbl24(dp, ips[i], nh_sz);
224                 if (unlikely(is_entry_extended(tmp)))
225                         tmp = get_tbl8(dp, tmp, ips[i], nh_sz);
226
227                 next_hops[i] = tmp >> 1;
228         }
229         for (; i < n; i++) {
230                 tmp = get_tbl24(dp, ips[i], nh_sz);
231                 if (unlikely(is_entry_extended(tmp)))
232                         tmp = get_tbl8(dp, tmp, ips[i], nh_sz);
233
234                 next_hops[i] = tmp >> 1;
235         }
236 }
237
238 void *
239 dir24_8_create(const char *name, int socket_id, struct rte_fib_conf *conf);
240
241 void
242 dir24_8_free(void *p);
243
244 rte_fib_lookup_fn_t
245 dir24_8_get_lookup_fn(void *p, enum rte_fib_lookup_type type);
246
247 int
248 dir24_8_modify(struct rte_fib *fib, uint32_t ip, uint8_t depth,
249         uint64_t next_hop, int op);
250
251 #endif /* _DIR24_8_H_ */