DPDK  17.05.2
rte_lpm.h
Go to the documentation of this file.
1 /*-
2  * BSD LICENSE
3  *
4  * Copyright(c) 2010-2014 Intel Corporation. All rights reserved.
5  * All rights reserved.
6  *
7  * Redistribution and use in source and binary forms, with or without
8  * modification, are permitted provided that the following conditions
9  * are met:
10  *
11  * * Redistributions of source code must retain the above copyright
12  * notice, this list of conditions and the following disclaimer.
13  * * Redistributions in binary form must reproduce the above copyright
14  * notice, this list of conditions and the following disclaimer in
15  * the documentation and/or other materials provided with the
16  * distribution.
17  * * Neither the name of Intel Corporation nor the names of its
18  * contributors may be used to endorse or promote products derived
19  * from this software without specific prior written permission.
20  *
21  * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
22  * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
23  * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
24  * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
25  * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
26  * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
27  * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
28  * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
29  * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
30  * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
31  * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
32  */
33 
34 #ifndef _RTE_LPM_H_
35 #define _RTE_LPM_H_
36 
42 #include <errno.h>
43 #include <sys/queue.h>
44 #include <stdint.h>
45 #include <stdlib.h>
46 #include <rte_branch_prediction.h>
47 #include <rte_byteorder.h>
48 #include <rte_memory.h>
49 #include <rte_common.h>
50 #include <rte_vect.h>
51 #include <rte_compat.h>
52 
53 #ifdef __cplusplus
54 extern "C" {
55 #endif
56 
58 #define RTE_LPM_NAMESIZE 32
59 
61 #define RTE_LPM_MAX_DEPTH 32
62 
64 #define RTE_LPM_TBL24_NUM_ENTRIES (1 << 24)
65 
67 #define RTE_LPM_TBL8_GROUP_NUM_ENTRIES 256
68 
70 #define RTE_LPM_MAX_TBL8_NUM_GROUPS (1 << 24)
71 
73 #define RTE_LPM_TBL8_NUM_GROUPS 256
74 
76 #define RTE_LPM_TBL8_NUM_ENTRIES (RTE_LPM_TBL8_NUM_GROUPS * \
77  RTE_LPM_TBL8_GROUP_NUM_ENTRIES)
78 
80 #if defined(RTE_LIBRTE_LPM_DEBUG)
81 #define RTE_LPM_RETURN_IF_TRUE(cond, retval) do { \
82  if (cond) return (retval); \
83 } while (0)
84 #else
85 #define RTE_LPM_RETURN_IF_TRUE(cond, retval)
86 #endif
87 
89 #define RTE_LPM_VALID_EXT_ENTRY_BITMASK 0x03000000
90 
92 #define RTE_LPM_LOOKUP_SUCCESS 0x01000000
93 
94 #if RTE_BYTE_ORDER == RTE_LITTLE_ENDIAN
95 
96 __extension__
97 struct rte_lpm_tbl_entry_v20 {
103  RTE_STD_C11
104  union {
105  uint8_t next_hop;
106  uint8_t group_idx;
107  };
108  /* Using single uint8_t to store 3 values. */
109  uint8_t valid :1;
117  uint8_t valid_group :1;
118  uint8_t depth :6;
119 };
120 
121 __extension__
122 struct rte_lpm_tbl_entry {
128  uint32_t next_hop :24;
129  /* Using single uint8_t to store 3 values. */
130  uint32_t valid :1;
138  uint32_t valid_group :1;
139  uint32_t depth :6;
140 };
141 
142 #else
143 __extension__
144 struct rte_lpm_tbl_entry_v20 {
145  uint8_t depth :6;
146  uint8_t valid_group :1;
147  uint8_t valid :1;
148  union {
149  uint8_t group_idx;
150  uint8_t next_hop;
151  };
152 };
153 
154 __extension__
155 struct rte_lpm_tbl_entry {
156  uint32_t depth :6;
157  uint32_t valid_group :1;
158  uint32_t valid :1;
159  uint32_t next_hop :24;
160 
161 };
162 
163 #endif
164 
166 struct rte_lpm_config {
167  uint32_t max_rules;
168  uint32_t number_tbl8s;
169  int flags;
170 };
171 
173 struct rte_lpm_rule_v20 {
174  uint32_t ip;
175  uint8_t next_hop;
176 };
177 
178 struct rte_lpm_rule {
179  uint32_t ip;
180  uint32_t next_hop;
181 };
182 
184 struct rte_lpm_rule_info {
185  uint32_t used_rules;
186  uint32_t first_rule;
187 };
188 
190 struct rte_lpm_v20 {
191  /* LPM metadata. */
192  char name[RTE_LPM_NAMESIZE];
193  uint32_t max_rules;
194  struct rte_lpm_rule_info rule_info[RTE_LPM_MAX_DEPTH];
196  /* LPM Tables. */
197  struct rte_lpm_tbl_entry_v20 tbl24[RTE_LPM_TBL24_NUM_ENTRIES]
198  __rte_cache_aligned;
199  struct rte_lpm_tbl_entry_v20 tbl8[RTE_LPM_TBL8_NUM_ENTRIES]
200  __rte_cache_aligned;
201  struct rte_lpm_rule_v20 rules_tbl[]
202  __rte_cache_aligned;
203 };
204 
205 struct rte_lpm {
206  /* LPM metadata. */
207  char name[RTE_LPM_NAMESIZE];
208  uint32_t max_rules;
209  uint32_t number_tbl8s;
210  struct rte_lpm_rule_info rule_info[RTE_LPM_MAX_DEPTH];
212  /* LPM Tables. */
213  struct rte_lpm_tbl_entry tbl24[RTE_LPM_TBL24_NUM_ENTRIES]
214  __rte_cache_aligned;
215  struct rte_lpm_tbl_entry *tbl8;
216  struct rte_lpm_rule *rules_tbl;
217 };
218 
238 struct rte_lpm *
239 rte_lpm_create(const char *name, int socket_id,
240  const struct rte_lpm_config *config);
241 struct rte_lpm_v20 *
242 rte_lpm_create_v20(const char *name, int socket_id, int max_rules, int flags);
243 struct rte_lpm *
244 rte_lpm_create_v1604(const char *name, int socket_id,
245  const struct rte_lpm_config *config);
246 
257 struct rte_lpm *
258 rte_lpm_find_existing(const char *name);
259 struct rte_lpm_v20 *
260 rte_lpm_find_existing_v20(const char *name);
261 struct rte_lpm *
262 rte_lpm_find_existing_v1604(const char *name);
263 
272 void
273 rte_lpm_free(struct rte_lpm *lpm);
274 void
275 rte_lpm_free_v20(struct rte_lpm_v20 *lpm);
276 void
277 rte_lpm_free_v1604(struct rte_lpm *lpm);
278 
293 int
294 rte_lpm_add(struct rte_lpm *lpm, uint32_t ip, uint8_t depth, uint32_t next_hop);
295 int
296 rte_lpm_add_v20(struct rte_lpm_v20 *lpm, uint32_t ip, uint8_t depth,
297  uint8_t next_hop);
298 int
299 rte_lpm_add_v1604(struct rte_lpm *lpm, uint32_t ip, uint8_t depth,
300  uint32_t next_hop);
301 
317 int
318 rte_lpm_is_rule_present(struct rte_lpm *lpm, uint32_t ip, uint8_t depth,
319 uint32_t *next_hop);
320 int
321 rte_lpm_is_rule_present_v20(struct rte_lpm_v20 *lpm, uint32_t ip, uint8_t depth,
322 uint8_t *next_hop);
323 int
324 rte_lpm_is_rule_present_v1604(struct rte_lpm *lpm, uint32_t ip, uint8_t depth,
325 uint32_t *next_hop);
326 
339 int
340 rte_lpm_delete(struct rte_lpm *lpm, uint32_t ip, uint8_t depth);
341 int
342 rte_lpm_delete_v20(struct rte_lpm_v20 *lpm, uint32_t ip, uint8_t depth);
343 int
344 rte_lpm_delete_v1604(struct rte_lpm *lpm, uint32_t ip, uint8_t depth);
345 
352 void
353 rte_lpm_delete_all(struct rte_lpm *lpm);
354 void
355 rte_lpm_delete_all_v20(struct rte_lpm_v20 *lpm);
356 void
357 rte_lpm_delete_all_v1604(struct rte_lpm *lpm);
358 
371 static inline int
372 rte_lpm_lookup(struct rte_lpm *lpm, uint32_t ip, uint32_t *next_hop)
373 {
374  unsigned tbl24_index = (ip >> 8);
375  uint32_t tbl_entry;
376  const uint32_t *ptbl;
377 
378  /* DEBUG: Check user input arguments. */
379  RTE_LPM_RETURN_IF_TRUE(((lpm == NULL) || (next_hop == NULL)), -EINVAL);
380 
381  /* Copy tbl24 entry */
382  ptbl = (const uint32_t *)(&lpm->tbl24[tbl24_index]);
383  tbl_entry = *ptbl;
384 
385  /* Copy tbl8 entry (only if needed) */
386  if (unlikely((tbl_entry & RTE_LPM_VALID_EXT_ENTRY_BITMASK) ==
387  RTE_LPM_VALID_EXT_ENTRY_BITMASK)) {
388 
389  unsigned tbl8_index = (uint8_t)ip +
390  (((uint32_t)tbl_entry & 0x00FFFFFF) *
391  RTE_LPM_TBL8_GROUP_NUM_ENTRIES);
392 
393  ptbl = (const uint32_t *)&lpm->tbl8[tbl8_index];
394  tbl_entry = *ptbl;
395  }
396 
397  *next_hop = ((uint32_t)tbl_entry & 0x00FFFFFF);
398  return (tbl_entry & RTE_LPM_LOOKUP_SUCCESS) ? 0 : -ENOENT;
399 }
400 
421 #define rte_lpm_lookup_bulk(lpm, ips, next_hops, n) \
422  rte_lpm_lookup_bulk_func(lpm, ips, next_hops, n)
423 
424 static inline int
425 rte_lpm_lookup_bulk_func(const struct rte_lpm *lpm, const uint32_t *ips,
426  uint32_t *next_hops, const unsigned n)
427 {
428  unsigned i;
429  unsigned tbl24_indexes[n];
430  const uint32_t *ptbl;
431 
432  /* DEBUG: Check user input arguments. */
433  RTE_LPM_RETURN_IF_TRUE(((lpm == NULL) || (ips == NULL) ||
434  (next_hops == NULL)), -EINVAL);
435 
436  for (i = 0; i < n; i++) {
437  tbl24_indexes[i] = ips[i] >> 8;
438  }
439 
440  for (i = 0; i < n; i++) {
441  /* Simply copy tbl24 entry to output */
442  ptbl = (const uint32_t *)&lpm->tbl24[tbl24_indexes[i]];
443  next_hops[i] = *ptbl;
444 
445  /* Overwrite output with tbl8 entry if needed */
446  if (unlikely((next_hops[i] & RTE_LPM_VALID_EXT_ENTRY_BITMASK) ==
447  RTE_LPM_VALID_EXT_ENTRY_BITMASK)) {
448 
449  unsigned tbl8_index = (uint8_t)ips[i] +
450  (((uint32_t)next_hops[i] & 0x00FFFFFF) *
451  RTE_LPM_TBL8_GROUP_NUM_ENTRIES);
452 
453  ptbl = (const uint32_t *)&lpm->tbl8[tbl8_index];
454  next_hops[i] = *ptbl;
455  }
456  }
457  return 0;
458 }
459 
460 /* Mask four results. */
461 #define RTE_LPM_MASKX4_RES UINT64_C(0x00ffffff00ffffff)
462 
482 static inline void
483 rte_lpm_lookupx4(const struct rte_lpm *lpm, xmm_t ip, uint32_t hop[4],
484  uint32_t defv);
485 
486 #if defined(RTE_ARCH_ARM) || defined(RTE_ARCH_ARM64)
487 #include "rte_lpm_neon.h"
488 #elif defined(RTE_ARCH_PPC_64)
489 #include "rte_lpm_altivec.h"
490 #else
491 #include "rte_lpm_sse.h"
492 #endif
493 
494 #ifdef __cplusplus
495 }
496 #endif
497 
498 #endif /* _RTE_LPM_H_ */
Generated by   doxygen 1.8.1.2