1 /* SPDX-License-Identifier: BSD-3-Clause
2 * Copyright(c) 2018 Vladimir Medvedkin <medvedkinv@gmail.com>
3 * Copyright(c) 2019 Intel Corporation
16 * All functions in this file may be changed or removed without prior notice.
18 * Level compressed tree implementation for IPv6 Longest Prefix Match
21 #include <rte_memcpy.h>
22 #include <rte_compat.h>
28 #define RTE_RIB6_IPV6_ADDR_SIZE 16
31 * rte_rib6_get_nxt() flags
34 /** flag to get all subroutes in a RIB tree */
36 /** flag to get first matched subroutes in a RIB tree */
37 RTE_RIB6_GET_NXT_COVER
43 /** RIB configuration structure */
44 struct rte_rib6_conf {
46 * Size of extension block inside rte_rib_node.
47 * This space could be used to store additional user
51 /* size of rte_rib_node's pool */
56 * Copy IPv6 address from one location to another
59 * pointer to the place to copy
61 * pointer from where to copy
64 rte_rib6_copy_addr(uint8_t *dst, const uint8_t *src)
66 if ((dst == NULL) || (src == NULL))
68 rte_memcpy(dst, src, RTE_RIB6_IPV6_ADDR_SIZE);
72 * Compare two IPv6 addresses
75 * pointer to the first ipv6 address
77 * pointer to the second ipv6 address
84 rte_rib6_is_equal(const uint8_t *ip1, const uint8_t *ip2) {
87 if ((ip1 == NULL) || (ip2 == NULL))
89 for (i = 0; i < RTE_RIB6_IPV6_ADDR_SIZE; i++) {
97 * Get 8-bit part of 128-bit IPv6 mask
102 * position of a 8-bit chunk in the 128-bit mask
105 * 8-bit chunk of the 128-bit IPv6 mask
107 static inline uint8_t
108 get_msk_part(uint8_t depth, int byte) {
112 depth = RTE_MIN(depth, 128);
113 part = RTE_MAX((int16_t)depth - (byte * 8), 0);
114 part = (part > 8) ? 8 : part;
115 return (uint16_t)(~UINT8_MAX) >> part;
119 * Lookup an IP into the RIB structure
124 * IP to be looked up in the RIB
126 * pointer to struct rte_rib6_node on success
130 struct rte_rib6_node *
131 rte_rib6_lookup(struct rte_rib6 *rib,
132 const uint8_t ip[RTE_RIB6_IPV6_ADDR_SIZE]);
135 * Lookup less specific route into the RIB structure
138 * Pointer to struct rte_rib6_node that represents target route
140 * pointer to struct rte_rib6_node that represents
141 * less specific route on success
145 struct rte_rib6_node *
146 rte_rib6_lookup_parent(struct rte_rib6_node *ent);
149 * Provides exact mach lookup of the prefix into the RIB structure
154 * net to be looked up in the RIB
158 * pointer to struct rte_rib6_node on success
162 struct rte_rib6_node *
163 rte_rib6_lookup_exact(struct rte_rib6 *rib,
164 const uint8_t ip[RTE_RIB6_IPV6_ADDR_SIZE], uint8_t depth);
167 * Retrieve next more specific prefix from the RIB
168 * that is covered by ip/depth supernet in an ascending order
173 * net address of supernet prefix that covers returned more specific prefixes
175 * supernet prefix length
177 * pointer to the last returned prefix to get next prefix
179 * NULL to get first more specific prefix
181 * -RTE_RIB6_GET_NXT_ALL
182 * get all prefixes from subtrie
183 * -RTE_RIB6_GET_NXT_COVER
184 * get only first more specific prefix even if it have more specifics
186 * pointer to the next more specific prefix
187 * NULL if there is no prefixes left
190 struct rte_rib6_node *
191 rte_rib6_get_nxt(struct rte_rib6 *rib,
192 const uint8_t ip[RTE_RIB6_IPV6_ADDR_SIZE],
193 uint8_t depth, struct rte_rib6_node *last, int flag);
196 * Remove prefix from the RIB
201 * net to be removed from the RIB
207 rte_rib6_remove(struct rte_rib6 *rib,
208 const uint8_t ip[RTE_RIB6_IPV6_ADDR_SIZE], uint8_t depth);
211 * Insert prefix into the RIB
216 * net to be inserted to the RIB
220 * pointer to new rte_rib6_node on success
224 struct rte_rib6_node *
225 rte_rib6_insert(struct rte_rib6 *rib,
226 const uint8_t ip[RTE_RIB6_IPV6_ADDR_SIZE], uint8_t depth);
229 * Get an ip from rte_rib6_node
232 * pointer to the rib6 node
234 * pointer to the ipv6 to save
237 * -1 on failure with rte_errno indicating reason for failure.
241 rte_rib6_get_ip(const struct rte_rib6_node *node,
242 uint8_t ip[RTE_RIB6_IPV6_ADDR_SIZE]);
245 * Get a depth from rte_rib6_node
248 * pointer to the rib6 node
250 * pointer to the depth to save
253 * -1 on failure with rte_errno indicating reason for failure.
257 rte_rib6_get_depth(const struct rte_rib6_node *node, uint8_t *depth);
260 * Get ext field from the rte_rib6_node
261 * It is caller responsibility to make sure there are necessary space
262 * for the ext field inside rib6 node.
265 * pointer to the rte_rib6_node
271 rte_rib6_get_ext(struct rte_rib6_node *node);
274 * Get nexthop from the rte_rib6_node
277 * pointer to the rib6 node
279 * pointer to the nexthop to save
282 * -1 on failure, with rte_errno indicating reason for failure.
286 rte_rib6_get_nh(const struct rte_rib6_node *node, uint64_t *nh);
289 * Set nexthop into the rte_rib6_node
292 * pointer to the rib6 node
294 * nexthop value to set to the rib6 node
297 * -1 on failure, with rte_errno indicating reason for failure.
301 rte_rib6_set_nh(struct rte_rib6_node *node, uint64_t nh);
309 * NUMA socket ID for RIB table memory allocation
311 * Structure containing the configuration
313 * Pointer to RIB object on success
314 * NULL otherwise with rte_errno indicating reason for failure.
318 rte_rib6_create(const char *name, int socket_id,
319 const struct rte_rib6_conf *conf);
322 * Find an existing RIB object and return a pointer to it.
325 * Name of the rib object as passed to rte_rib_create()
327 * Pointer to RIB object on success
328 * NULL otherwise with rte_errno indicating reason for failure.
332 rte_rib6_find_existing(const char *name);
335 * Free an RIB object.
344 rte_rib6_free(struct rte_rib6 *rib);
350 #endif /* _RTE_RIB6_H_ */