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 _RTE_RIB_H_
7 #define _RTE_RIB_H_
8
9 /**
10 * @file
11 *
12 * RTE RIB library.
13 *
14 * Level compressed tree implementation for IPv4 Longest Prefix Match
15 */
16
17 #include <stdlib.h>
18 #include <stdint.h>
19
20
21 #ifdef __cplusplus
22 extern "C" {
23 #endif
24
25 /**
26 * rte_rib_get_nxt() flags
27 */
28 enum {
29 /** flag to get all subroutes in a RIB tree */
30 RTE_RIB_GET_NXT_ALL,
31 /** flag to get first matched subroutes in a RIB tree */
32 RTE_RIB_GET_NXT_COVER
33 };
34
35 struct rte_rib;
36 struct rte_rib_node;
37
38 /** RIB configuration structure */
39 struct rte_rib_conf {
40 /**
41 * Size of extension block inside rte_rib_node.
42 * This space could be used to store additional user
43 * defined data.
44 */
45 size_t ext_sz;
46 /* size of rte_rib_node's pool */
47 int max_nodes;
48 };
49
50 /**
51 * Get an IPv4 mask from prefix length
52 * It is caller responsibility to make sure depth is not bigger than 32
53 *
54 * @param depth
55 * prefix length
56 * @return
57 * IPv4 mask
58 */
59 static inline uint32_t
rte_rib_depth_to_mask(uint8_t depth)60 rte_rib_depth_to_mask(uint8_t depth)
61 {
62 return (uint32_t)(UINT64_MAX << (32 - depth));
63 }
64
65 /**
66 * Lookup an IP into the RIB structure
67 *
68 * @param rib
69 * RIB object handle
70 * @param ip
71 * IP to be looked up in the RIB
72 * @return
73 * pointer to struct rte_rib_node on success
74 * NULL otherwise
75 */
76 struct rte_rib_node *
77 rte_rib_lookup(struct rte_rib *rib, uint32_t ip);
78
79 /**
80 * Lookup less specific route into the RIB structure
81 *
82 * @param ent
83 * Pointer to struct rte_rib_node that represents target route
84 * @return
85 * pointer to struct rte_rib_node that represents
86 * less specific route on success
87 * NULL otherwise
88 */
89 struct rte_rib_node *
90 rte_rib_lookup_parent(struct rte_rib_node *ent);
91
92 /**
93 * Lookup prefix into the RIB structure
94 *
95 * @param rib
96 * RIB object handle
97 * @param ip
98 * net to be looked up in the RIB
99 * @param depth
100 * prefix length
101 * @return
102 * pointer to struct rte_rib_node on success
103 * NULL otherwise
104 */
105 struct rte_rib_node *
106 rte_rib_lookup_exact(struct rte_rib *rib, uint32_t ip, uint8_t depth);
107
108 /**
109 * Retrieve next more specific prefix from the RIB
110 * that is covered by ip/depth supernet in an ascending order
111 *
112 * @param rib
113 * RIB object handle
114 * @param ip
115 * net address of supernet prefix that covers returned more specific prefixes
116 * @param depth
117 * supernet prefix length
118 * @param last
119 * pointer to the last returned prefix to get next prefix
120 * or
121 * NULL to get first more specific prefix
122 * @param flag
123 * -RTE_RIB_GET_NXT_ALL
124 * get all prefixes from subtrie
125 * -RTE_RIB_GET_NXT_COVER
126 * get only first more specific prefix even if it have more specifics
127 * @return
128 * pointer to the next more specific prefix
129 * NULL if there is no prefixes left
130 */
131 struct rte_rib_node *
132 rte_rib_get_nxt(struct rte_rib *rib, uint32_t ip, uint8_t depth,
133 struct rte_rib_node *last, int flag);
134
135 /**
136 * Remove prefix from the RIB
137 *
138 * @param rib
139 * RIB object handle
140 * @param ip
141 * net to be removed from the RIB
142 * @param depth
143 * prefix length
144 */
145 void
146 rte_rib_remove(struct rte_rib *rib, uint32_t ip, uint8_t depth);
147
148 /**
149 * Insert prefix into the RIB
150 *
151 * @param rib
152 * RIB object handle
153 * @param ip
154 * net to be inserted to the RIB
155 * @param depth
156 * prefix length
157 * @return
158 * pointer to new rte_rib_node on success
159 * NULL otherwise
160 */
161 struct rte_rib_node *
162 rte_rib_insert(struct rte_rib *rib, uint32_t ip, uint8_t depth);
163
164 /**
165 * Get an ip from rte_rib_node
166 *
167 * @param node
168 * pointer to the rib node
169 * @param ip
170 * pointer to the ip to save
171 * @return
172 * 0 on success.
173 * -1 on failure with rte_errno indicating reason for failure.
174 */
175 int
176 rte_rib_get_ip(const struct rte_rib_node *node, uint32_t *ip);
177
178 /**
179 * Get a depth from rte_rib_node
180 *
181 * @param node
182 * pointer to the rib node
183 * @param depth
184 * pointer to the depth to save
185 * @return
186 * 0 on success.
187 * -1 on failure with rte_errno indicating reason for failure.
188 */
189 int
190 rte_rib_get_depth(const struct rte_rib_node *node, uint8_t *depth);
191
192 /**
193 * Get ext field from the rib node
194 * It is caller responsibility to make sure there are necessary space
195 * for the ext field inside rib node.
196 *
197 * @param node
198 * pointer to the rib node
199 * @return
200 * pointer to the ext
201 */
202 void *
203 rte_rib_get_ext(struct rte_rib_node *node);
204
205 /**
206 * Get nexthop from the rib node
207 *
208 * @param node
209 * pointer to the rib node
210 * @param nh
211 * pointer to the nexthop to save
212 * @return
213 * 0 on success.
214 * -1 on failure with rte_errno indicating reason for failure.
215 */
216 int
217 rte_rib_get_nh(const struct rte_rib_node *node, uint64_t *nh);
218
219 /**
220 * Set nexthop into the rib node
221 *
222 * @param node
223 * pointer to the rib node
224 * @param nh
225 * nexthop value to set to the rib node
226 * @return
227 * 0 on success.
228 * -1 on failure with rte_errno indicating reason for failure.
229 */
230 int
231 rte_rib_set_nh(struct rte_rib_node *node, uint64_t nh);
232
233 /**
234 * Create RIB
235 *
236 * @param name
237 * RIB name
238 * @param socket_id
239 * NUMA socket ID for RIB table memory allocation
240 * @param conf
241 * Structure containing the configuration
242 * @return
243 * Handle to RIB object on success
244 * NULL otherwise with rte_errno indicating reason for failure.
245 */
246 struct rte_rib *
247 rte_rib_create(const char *name, int socket_id,
248 const struct rte_rib_conf *conf);
249
250 /**
251 * Find an existing RIB object and return a pointer to it.
252 *
253 * @param name
254 * Name of the rib object as passed to rte_rib_create()
255 * @return
256 * Pointer to RIB object on success
257 * NULL otherwise with rte_errno indicating reason for failure.
258 */
259 struct rte_rib *
260 rte_rib_find_existing(const char *name);
261
262 /**
263 * Free an RIB object.
264 *
265 * @param rib
266 * RIB object handle created with rte_rib_create().
267 * If rib is NULL, no operation is performed.
268 */
269 void
270 rte_rib_free(struct rte_rib *rib);
271
272 #ifdef __cplusplus
273 }
274 #endif
275
276 #endif /* _RTE_RIB_H_ */
277