DPDK  16.04.0
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 struct rte_lpm_tbl_entry_v20 {
102  union {
103  uint8_t next_hop;
104  uint8_t group_idx;
105  };
106  /* Using single uint8_t to store 3 values. */
107  uint8_t valid :1;
115  uint8_t valid_group :1;
116  uint8_t depth :6;
117 };
118 
119 struct rte_lpm_tbl_entry {
125  uint32_t next_hop :24;
126  /* Using single uint8_t to store 3 values. */
127  uint32_t valid :1;
135  uint32_t valid_group :1;
136  uint32_t depth :6;
137 };
138 
139 #else
140 struct rte_lpm_tbl_entry_v20 {
141  uint8_t depth :6;
142  uint8_t valid_group :1;
143  uint8_t valid :1;
144  union {
145  uint8_t group_idx;
146  uint8_t next_hop;
147  };
148 };
149 
150 struct rte_lpm_tbl_entry {
151  uint32_t depth :6;
152  uint32_t valid_group :1;
153  uint32_t valid :1;
154  uint32_t next_hop :24;
155 
156 };
157 
158 #endif
159 
161 struct rte_lpm_config {
162  uint32_t max_rules;
163  uint32_t number_tbl8s;
164  int flags;
165 };
166 
168 struct rte_lpm_rule_v20 {
169  uint32_t ip;
170  uint8_t next_hop;
171 };
172 
173 struct rte_lpm_rule {
174  uint32_t ip;
175  uint32_t next_hop;
176 };
177 
179 struct rte_lpm_rule_info {
180  uint32_t used_rules;
181  uint32_t first_rule;
182 };
183 
185 struct rte_lpm_v20 {
186  /* LPM metadata. */
187  char name[RTE_LPM_NAMESIZE];
188  uint32_t max_rules;
189  struct rte_lpm_rule_info rule_info[RTE_LPM_MAX_DEPTH];
191  /* LPM Tables. */
192  struct rte_lpm_tbl_entry_v20 tbl24[RTE_LPM_TBL24_NUM_ENTRIES]
193  __rte_cache_aligned;
194  struct rte_lpm_tbl_entry_v20 tbl8[RTE_LPM_TBL8_NUM_ENTRIES]
195  __rte_cache_aligned;
196  struct rte_lpm_rule_v20 rules_tbl[0] \
197  __rte_cache_aligned;
198 };
199 
200 struct rte_lpm {
201  /* LPM metadata. */
202  char name[RTE_LPM_NAMESIZE];
203  uint32_t max_rules;
204  uint32_t number_tbl8s;
205  struct rte_lpm_rule_info rule_info[RTE_LPM_MAX_DEPTH];
207  /* LPM Tables. */
208  struct rte_lpm_tbl_entry tbl24[RTE_LPM_TBL24_NUM_ENTRIES]
209  __rte_cache_aligned;
210  struct rte_lpm_tbl_entry *tbl8;
211  struct rte_lpm_rule *rules_tbl;
212 };
213 
233 struct rte_lpm *
234 rte_lpm_create(const char *name, int socket_id,
235  const struct rte_lpm_config *config);
236 struct rte_lpm_v20 *
237 rte_lpm_create_v20(const char *name, int socket_id, int max_rules, int flags);
238 struct rte_lpm *
239 rte_lpm_create_v1604(const char *name, int socket_id,
240  const struct rte_lpm_config *config);
241 
252 struct rte_lpm *
253 rte_lpm_find_existing(const char *name);
254 struct rte_lpm_v20 *
255 rte_lpm_find_existing_v20(const char *name);
256 struct rte_lpm *
257 rte_lpm_find_existing_v1604(const char *name);
258 
267 void
268 rte_lpm_free(struct rte_lpm *lpm);
269 void
270 rte_lpm_free_v20(struct rte_lpm_v20 *lpm);
271 void
272 rte_lpm_free_v1604(struct rte_lpm *lpm);
273 
288 int
289 rte_lpm_add(struct rte_lpm *lpm, uint32_t ip, uint8_t depth, uint32_t next_hop);
290 int
291 rte_lpm_add_v20(struct rte_lpm_v20 *lpm, uint32_t ip, uint8_t depth,
292  uint8_t next_hop);
293 int
294 rte_lpm_add_v1604(struct rte_lpm *lpm, uint32_t ip, uint8_t depth,
295  uint32_t next_hop);
296 
312 int
313 rte_lpm_is_rule_present(struct rte_lpm *lpm, uint32_t ip, uint8_t depth,
314 uint32_t *next_hop);
315 int
316 rte_lpm_is_rule_present_v20(struct rte_lpm_v20 *lpm, uint32_t ip, uint8_t depth,
317 uint8_t *next_hop);
318 int
319 rte_lpm_is_rule_present_v1604(struct rte_lpm *lpm, uint32_t ip, uint8_t depth,
320 uint32_t *next_hop);
321 
334 int
335 rte_lpm_delete(struct rte_lpm *lpm, uint32_t ip, uint8_t depth);
336 int
337 rte_lpm_delete_v20(struct rte_lpm_v20 *lpm, uint32_t ip, uint8_t depth);
338 int
339 rte_lpm_delete_v1604(struct rte_lpm *lpm, uint32_t ip, uint8_t depth);
340 
347 void
348 rte_lpm_delete_all(struct rte_lpm *lpm);
349 void
350 rte_lpm_delete_all_v20(struct rte_lpm_v20 *lpm);
351 void
352 rte_lpm_delete_all_v1604(struct rte_lpm *lpm);
353 
366 static inline int
367 rte_lpm_lookup(struct rte_lpm *lpm, uint32_t ip, uint32_t *next_hop)
368 {
369  unsigned tbl24_index = (ip >> 8);
370  uint32_t tbl_entry;
371  const uint32_t *ptbl;
372 
373  /* DEBUG: Check user input arguments. */
374  RTE_LPM_RETURN_IF_TRUE(((lpm == NULL) || (next_hop == NULL)), -EINVAL);
375 
376  /* Copy tbl24 entry */
377  ptbl = (const uint32_t *)(&lpm->tbl24[tbl24_index]);
378  tbl_entry = *ptbl;
379 
380  /* Copy tbl8 entry (only if needed) */
381  if (unlikely((tbl_entry & RTE_LPM_VALID_EXT_ENTRY_BITMASK) ==
382  RTE_LPM_VALID_EXT_ENTRY_BITMASK)) {
383 
384  unsigned tbl8_index = (uint8_t)ip +
385  (((uint32_t)tbl_entry & 0x00FFFFFF) *
386  RTE_LPM_TBL8_GROUP_NUM_ENTRIES);
387 
388  ptbl = (const uint32_t *)&lpm->tbl8[tbl8_index];
389  tbl_entry = *ptbl;
390  }
391 
392  *next_hop = ((uint32_t)tbl_entry & 0x00FFFFFF);
393  return (tbl_entry & RTE_LPM_LOOKUP_SUCCESS) ? 0 : -ENOENT;
394 }
395 
416 #define rte_lpm_lookup_bulk(lpm, ips, next_hops, n) \
417  rte_lpm_lookup_bulk_func(lpm, ips, next_hops, n)
418 
419 static inline int
420 rte_lpm_lookup_bulk_func(const struct rte_lpm *lpm, const uint32_t *ips,
421  uint32_t *next_hops, const unsigned n)
422 {
423  unsigned i;
424  unsigned tbl24_indexes[n];
425  const uint32_t *ptbl;
426 
427  /* DEBUG: Check user input arguments. */
428  RTE_LPM_RETURN_IF_TRUE(((lpm == NULL) || (ips == NULL) ||
429  (next_hops == NULL)), -EINVAL);
430 
431  for (i = 0; i < n; i++) {
432  tbl24_indexes[i] = ips[i] >> 8;
433  }
434 
435  for (i = 0; i < n; i++) {
436  /* Simply copy tbl24 entry to output */
437  ptbl = (const uint32_t *)&lpm->tbl24[tbl24_indexes[i]];
438  next_hops[i] = *ptbl;
439 
440  /* Overwrite output with tbl8 entry if needed */
441  if (unlikely((next_hops[i] & RTE_LPM_VALID_EXT_ENTRY_BITMASK) ==
442  RTE_LPM_VALID_EXT_ENTRY_BITMASK)) {
443 
444  unsigned tbl8_index = (uint8_t)ips[i] +
445  (((uint32_t)next_hops[i] & 0x00FFFFFF) *
446  RTE_LPM_TBL8_GROUP_NUM_ENTRIES);
447 
448  ptbl = (const uint32_t *)&lpm->tbl8[tbl8_index];
449  next_hops[i] = *ptbl;
450  }
451  }
452  return 0;
453 }
454 
455 /* Mask four results. */
456 #define RTE_LPM_MASKX4_RES UINT64_C(0x00ffffff00ffffff)
457 
477 static inline void
478 rte_lpm_lookupx4(const struct rte_lpm *lpm, xmm_t ip, uint32_t hop[4],
479  uint32_t defv);
480 
481 #if defined(RTE_ARCH_ARM) || defined(RTE_ARCH_ARM64)
482 #include "rte_lpm_neon.h"
483 #else
484 #include "rte_lpm_sse.h"
485 #endif
486 
487 #ifdef __cplusplus
488 }
489 #endif
490 
491 #endif /* _RTE_LPM_H_ */
Generated by   doxygen 1.8.1.2