Line data Source code
1 : // SPDX-License-Identifier: GPL-2.0-or-later
2 : /*
3 : * Routing Table
4 : * Copyright (C) 1998 Kunihiro Ishiguro
5 : */
6 :
7 : #ifndef _ZEBRA_TABLE_H
8 : #define _ZEBRA_TABLE_H
9 :
10 : #include "memory.h"
11 : #include "hash.h"
12 : #include "prefix.h"
13 : #include "typesafe.h"
14 :
15 : #ifdef __cplusplus
16 : extern "C" {
17 : #endif
18 :
19 : DECLARE_MTYPE(ROUTE_NODE);
20 :
21 : /*
22 : * Forward declarations.
23 : */
24 : struct route_node;
25 : struct route_table;
26 :
27 : /*
28 : * route_table_delegate_t
29 : *
30 : * Function vector that can be used by a client to customize the
31 : * behavior of one or more route tables.
32 : */
33 : typedef const struct route_table_delegate_t_ route_table_delegate_t;
34 :
35 : typedef struct route_node *(*route_table_create_node_func_t)(
36 : route_table_delegate_t *, struct route_table *);
37 :
38 : typedef void (*route_table_destroy_node_func_t)(route_table_delegate_t *,
39 : struct route_table *,
40 : struct route_node *);
41 :
42 : struct route_table_delegate_t_ {
43 : route_table_create_node_func_t create_node;
44 : route_table_destroy_node_func_t destroy_node;
45 : };
46 :
47 : PREDECL_HASH(rn_hash_node);
48 :
49 : /* Routing table top structure. */
50 : struct route_table {
51 : struct route_node *top;
52 : struct rn_hash_node_head hash;
53 :
54 : /*
55 : * Delegate that performs certain functions for this table.
56 : */
57 : route_table_delegate_t *delegate;
58 : void (*cleanup)(struct route_table *, struct route_node *);
59 :
60 : unsigned long count;
61 :
62 : /*
63 : * User data.
64 : */
65 : void *info;
66 : };
67 :
68 : /*
69 : * node->link is really internal to the table code and should not be
70 : * accessed by outside code. We don't have any writers (yay), though some
71 : * readers are left to be fixed.
72 : *
73 : * rationale: we need to add a hash table in parallel, to speed up
74 : * exact-match lookups.
75 : *
76 : * same really applies for node->parent, though that's less of an issue.
77 : * table->link should be - and is - NEVER written by outside code
78 : */
79 : #ifdef FRR_COMPILING_TABLE_C
80 : #define table_rdonly(x) x
81 : #define table_internal(x) x
82 : #else
83 : #define table_rdonly(x) const x
84 : #define table_internal(x) \
85 : const x __attribute__( \
86 : (deprecated("this should only be accessed by lib/table.c")))
87 : /* table_internal is for node->link and node->lock, once we have done
88 : * something about remaining accesses */
89 : #endif
90 :
91 : /* so... the problem with this is that "const" doesn't mean "readonly".
92 : * It in fact may allow the compiler to optimize based on the assumption
93 : * that the value doesn't change. Hence, since the only purpose of this
94 : * is to aid in development, don't put the "const" in release builds.
95 : *
96 : * (I haven't seen this actually break, but GCC and LLVM are getting ever
97 : * more aggressive in optimizing...)
98 : */
99 : #ifndef DEV_BUILD
100 : #undef table_rdonly
101 : #define table_rdonly(x) x
102 : #endif
103 :
104 : /*
105 : * Macro that defines all fields in a route node.
106 : */
107 : #define ROUTE_NODE_FIELDS \
108 : /* Actual prefix of this radix. */ \
109 : struct prefix p; \
110 : \
111 : /* Tree link. */ \
112 : struct route_table *table_rdonly(table); \
113 : struct route_node *table_rdonly(parent); \
114 : struct route_node *table_rdonly(link[2]); \
115 : \
116 : /* Lock of this radix */ \
117 : unsigned int table_rdonly(lock); \
118 : \
119 : struct rn_hash_node_item nodehash; \
120 : /* Each node of route. */ \
121 : void *info; \
122 :
123 :
124 : /* Each routing entry. */
125 : struct route_node {
126 : ROUTE_NODE_FIELDS
127 :
128 : #define l_left link[0]
129 : #define l_right link[1]
130 : };
131 :
132 : typedef struct route_table_iter_t_ route_table_iter_t;
133 :
134 : typedef enum {
135 : RT_ITER_STATE_INIT,
136 : RT_ITER_STATE_ITERATING,
137 : RT_ITER_STATE_PAUSED,
138 : RT_ITER_STATE_DONE
139 : } route_table_iter_state_t;
140 :
141 : /*
142 : * route_table_iter_t
143 : *
144 : * Structure that holds state for iterating over a route table.
145 : */
146 : struct route_table_iter_t_ {
147 :
148 : route_table_iter_state_t state;
149 :
150 : /*
151 : * Routing table that we are iterating over. The caller must ensure
152 : * that that table outlives the iterator.
153 : */
154 : struct route_table *table;
155 :
156 : /*
157 : * The node that the iterator is currently on.
158 : */
159 : struct route_node *current;
160 :
161 : /*
162 : * The last prefix that the iterator processed before it was paused.
163 : */
164 : struct prefix pause_prefix;
165 : };
166 :
167 : /* Prototypes. */
168 : extern struct route_table *route_table_init(void);
169 :
170 : extern struct route_table *
171 : route_table_init_with_delegate(route_table_delegate_t *delegate);
172 :
173 : extern route_table_delegate_t *route_table_get_default_delegate(void);
174 :
175 490 : static inline void *route_table_get_info(struct route_table *table)
176 : {
177 490 : return table->info;
178 : }
179 :
180 208 : static inline void route_table_set_info(struct route_table *table, void *d)
181 : {
182 208 : table->info = d;
183 0 : }
184 :
185 : extern void route_table_finish(struct route_table *table);
186 : extern struct route_node *route_top(struct route_table *table);
187 : extern struct route_node *route_next(struct route_node *node);
188 : extern struct route_node *route_next_until(struct route_node *node,
189 : const struct route_node *limit);
190 : extern struct route_node *route_node_get(struct route_table *table,
191 : union prefixconstptr pu);
192 : extern struct route_node *route_node_lookup(struct route_table *table,
193 : union prefixconstptr pu);
194 : extern struct route_node *route_node_lookup_maynull(struct route_table *table,
195 : union prefixconstptr pu);
196 : extern struct route_node *route_node_match(struct route_table *table,
197 : union prefixconstptr pu);
198 : extern struct route_node *route_node_match_ipv4(struct route_table *table,
199 : const struct in_addr *addr);
200 : extern struct route_node *route_node_match_ipv6(struct route_table *table,
201 : const struct in6_addr *addr);
202 :
203 : extern unsigned long route_table_count(struct route_table *table);
204 :
205 : extern struct route_node *route_node_create(route_table_delegate_t *delegate,
206 : struct route_table *table);
207 : extern void route_node_delete(struct route_node *node);
208 : extern void route_node_destroy(route_table_delegate_t *delegate,
209 : struct route_table *table,
210 : struct route_node *node);
211 :
212 : extern struct route_node *route_table_get_next(struct route_table *table,
213 : union prefixconstptr pu);
214 : extern int route_table_prefix_iter_cmp(const struct prefix *p1,
215 : const struct prefix *p2);
216 :
217 : /*
218 : * Iterator functions.
219 : */
220 : extern void route_table_iter_init(route_table_iter_t *iter,
221 : struct route_table *table);
222 : extern void route_table_iter_pause(route_table_iter_t *iter);
223 : extern void route_table_iter_cleanup(route_table_iter_t *iter);
224 :
225 : /*
226 : * Inline functions.
227 : */
228 :
229 : /* Lock node. */
230 840 : static inline struct route_node *route_lock_node(struct route_node *node)
231 : {
232 840 : (*(unsigned *)&node->lock)++;
233 752 : return node;
234 : }
235 :
236 : /* Unlock node. */
237 732 : static inline void route_unlock_node(struct route_node *node)
238 : {
239 732 : assert(node->lock > 0);
240 732 : (*(unsigned *)&node->lock)--;
241 :
242 732 : if (node->lock == 0)
243 162 : route_node_delete(node);
244 732 : }
245 :
246 0 : static inline unsigned int route_node_get_lock_count(struct route_node *node)
247 : {
248 0 : return node->lock;
249 : }
250 :
251 : /*
252 : * route_table_iter_next
253 : *
254 : * Get the next node in the tree.
255 : */
256 : static inline struct route_node *route_table_iter_next(route_table_iter_t *iter)
257 : {
258 : struct route_node *node;
259 :
260 : switch (iter->state) {
261 :
262 : case RT_ITER_STATE_INIT:
263 :
264 : /*
265 : * We're just starting the iteration.
266 : */
267 : node = route_top(iter->table);
268 : break;
269 :
270 : case RT_ITER_STATE_ITERATING:
271 : node = route_next(iter->current);
272 : break;
273 :
274 : case RT_ITER_STATE_PAUSED:
275 :
276 : /*
277 : * Start with the node following pause_prefix.
278 : */
279 : node = route_table_get_next(iter->table, &iter->pause_prefix);
280 : break;
281 :
282 : case RT_ITER_STATE_DONE:
283 : return NULL;
284 :
285 : default:
286 : /* Suppress uninitialized variable warning */
287 : node = NULL;
288 : assert(0);
289 : }
290 :
291 : iter->current = node;
292 : if (node)
293 : iter->state = RT_ITER_STATE_ITERATING;
294 : else
295 : iter->state = RT_ITER_STATE_DONE;
296 :
297 : return node;
298 : }
299 :
300 : /*
301 : * route_table_iter_is_done
302 : *
303 : * Returns true if the iteration is complete.
304 : */
305 : static inline int route_table_iter_is_done(route_table_iter_t *iter)
306 : {
307 : return iter->state == RT_ITER_STATE_DONE;
308 : }
309 :
310 : /*
311 : * route_table_iter_started
312 : *
313 : * Returns true if this iterator has started iterating over the tree.
314 : */
315 : static inline int route_table_iter_started(route_table_iter_t *iter)
316 : {
317 : return iter->state != RT_ITER_STATE_INIT;
318 : }
319 :
320 : #ifdef _FRR_ATTRIBUTE_PRINTFRR
321 : #pragma FRR printfrr_ext "%pRN" (struct route_node *)
322 : #endif
323 :
324 : #ifdef __cplusplus
325 : }
326 : #endif
327 :
328 : #endif /* _ZEBRA_TABLE_H */
|
