]>
Commit | Line | Data |
---|---|---|
0964ad9c DL |
1 | /* |
2 | * SRC-DEST Routing Table | |
3 | * | |
4 | * Copyright (C) 2017 by David Lamparter & Christian Franke, | |
5 | * Open Source Routing / NetDEF Inc. | |
6 | * | |
7 | * This file is part of FreeRangeRouting (FRR) | |
8 | * | |
9 | * FRR is free software; you can redistribute it and/or modify it | |
10 | * under the terms of the GNU General Public License as published by the | |
11 | * Free Software Foundation; either version 2, or (at your option) any | |
12 | * later version. | |
13 | * | |
14 | * FRR is distributed in the hope that it will be useful, but | |
15 | * WITHOUT ANY WARRANTY; without even the implied warranty of | |
16 | * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU | |
17 | * General Public License for more details. | |
18 | * | |
19 | * You should have received a copy of the GNU General Public License | |
20 | * along with FRR; see the file COPYING. If not, write to the Free | |
21 | * Software Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA | |
22 | * 02111-1307, USA. | |
23 | */ | |
24 | ||
25 | #include <zebra.h> | |
26 | ||
27 | #include "srcdest_table.h" | |
28 | ||
29 | #include "memory.h" | |
30 | #include "prefix.h" | |
31 | #include "table.h" | |
32 | ||
33 | DEFINE_MTYPE_STATIC(LIB, ROUTE_SRC_NODE, "Route source node") | |
34 | ||
35 | /* ----- functions to manage rnodes _with_ srcdest table ----- */ | |
36 | struct srcdest_rnode | |
37 | { | |
38 | /* must be first in structure for casting to/from route_node */ | |
39 | ROUTE_NODE_FIELDS; | |
40 | ||
41 | struct route_table *src_table; | |
42 | }; | |
43 | ||
44 | static struct srcdest_rnode * | |
45 | srcdest_rnode_from_rnode (struct route_node *rn) | |
46 | { | |
47 | assert (rnode_is_dstnode (rn)); | |
48 | return (struct srcdest_rnode *) rn; | |
49 | } | |
50 | ||
51 | static struct route_node * | |
52 | srcdest_rnode_to_rnode (struct srcdest_rnode *srn) | |
53 | { | |
54 | return (struct route_node *) srn; | |
55 | } | |
56 | ||
57 | static struct route_node * | |
58 | srcdest_rnode_create (route_table_delegate_t *delegate, | |
59 | struct route_table *table) | |
60 | { | |
61 | struct srcdest_rnode *srn; | |
62 | srn = XCALLOC (MTYPE_ROUTE_NODE, sizeof (struct srcdest_rnode)); | |
63 | return srcdest_rnode_to_rnode(srn); | |
64 | } | |
65 | ||
66 | static void | |
67 | srcdest_rnode_destroy (route_table_delegate_t *delegate, | |
68 | struct route_table *table, struct route_node *rn) | |
69 | { | |
70 | struct srcdest_rnode *srn = srcdest_rnode_from_rnode(rn); | |
71 | struct route_table *src_table; | |
72 | ||
73 | /* Clear route node's src_table here already, otherwise the | |
74 | * deletion of the last node in the src_table will trigger | |
75 | * another call to route_table_finish for the src_table. | |
76 | * | |
77 | * (Compare with srcdest_srcnode_destroy) | |
78 | */ | |
79 | src_table = srn->src_table; | |
80 | srn->src_table = NULL; | |
81 | route_table_finish(src_table); | |
82 | XFREE (MTYPE_ROUTE_NODE, rn); | |
83 | } | |
84 | ||
85 | route_table_delegate_t _srcdest_dstnode_delegate = { | |
86 | .create_node = srcdest_rnode_create, | |
87 | .destroy_node = srcdest_rnode_destroy | |
88 | }; | |
89 | ||
90 | /* ----- functions to manage rnodes _in_ srcdest table ----- */ | |
91 | ||
92 | /* node creation / deletion for srcdest source prefix nodes. | |
93 | * the route_node isn't actually different from the normal route_node, | |
94 | * but the cleanup is special to free the table (and possibly the | |
95 | * destination prefix's route_node) */ | |
96 | ||
97 | static struct route_node * | |
98 | srcdest_srcnode_create (route_table_delegate_t *delegate, | |
99 | struct route_table *table) | |
100 | { | |
101 | return XCALLOC (MTYPE_ROUTE_SRC_NODE, sizeof (struct route_node)); | |
102 | } | |
103 | ||
104 | static void | |
105 | srcdest_srcnode_destroy (route_table_delegate_t *delegate, | |
106 | struct route_table *table, struct route_node *rn) | |
107 | { | |
108 | struct srcdest_rnode *srn; | |
109 | ||
110 | XFREE (MTYPE_ROUTE_SRC_NODE, rn); | |
111 | ||
112 | srn = table->info; | |
113 | if (srn->src_table && route_table_count (srn->src_table) == 0) | |
114 | { | |
115 | /* deleting the route_table from inside destroy_node is ONLY | |
116 | * permitted IF table->count is 0! see lib/table.c route_node_delete() | |
117 | * for details */ | |
118 | route_table_finish (srn->src_table); | |
119 | srn->src_table = NULL; | |
120 | ||
121 | /* drop the ref we're holding in srcdest_node_get(). there might be | |
122 | * non-srcdest routes, so the route_node may still exist. hence, it's | |
123 | * important to clear src_table above. */ | |
124 | route_unlock_node (srcdest_rnode_to_rnode (srn)); | |
125 | } | |
126 | } | |
127 | ||
128 | route_table_delegate_t _srcdest_srcnode_delegate = { | |
129 | .create_node = srcdest_srcnode_create, | |
130 | .destroy_node = srcdest_srcnode_destroy | |
131 | }; | |
132 | ||
133 | /* NB: read comments in code for refcounting before using! */ | |
134 | static struct route_node * | |
135 | srcdest_srcnode_get (struct route_node *rn, struct prefix_ipv6 *src_p) | |
136 | { | |
137 | struct srcdest_rnode *srn; | |
138 | ||
139 | if (!src_p || src_p->prefixlen == 0) | |
140 | return rn; | |
141 | ||
142 | srn = srcdest_rnode_from_rnode (rn); | |
143 | if (!srn->src_table) | |
144 | { | |
145 | /* this won't use srcdest_rnode, we're already on the source here */ | |
146 | srn->src_table = route_table_init_with_delegate (&_srcdest_srcnode_delegate); | |
147 | srn->src_table->info = srn; | |
148 | ||
149 | /* there is no route_unlock_node on the original rn here. | |
150 | * The reference is kept for the src_table. */ | |
151 | } | |
152 | else | |
153 | { | |
154 | /* only keep 1 reference for the src_table, makes the refcounting | |
155 | * more similar to the non-srcdest case. Either way after return from | |
156 | * function, the only reference held is the one on the return value. | |
157 | * | |
158 | * We can safely drop our reference here because src_table is holding | |
159 | * another reference, so this won't free rn */ | |
160 | route_unlock_node (rn); | |
161 | } | |
162 | ||
163 | return route_node_get (srn->src_table, (struct prefix *)src_p); | |
164 | } | |
165 | ||
166 | static struct route_node * | |
167 | srcdest_srcnode_lookup (struct route_node *rn, struct prefix_ipv6 *src_p) | |
168 | { | |
169 | struct srcdest_rnode *srn; | |
170 | ||
171 | if (!rn || !src_p || src_p->prefixlen == 0) | |
172 | return rn; | |
173 | ||
174 | /* We got this rn from a lookup, so its refcnt was incremented. As we won't | |
175 | * return return rn from any point beyond here, we should decrement its refcnt. | |
176 | */ | |
177 | route_unlock_node (rn); | |
178 | ||
179 | srn = srcdest_rnode_from_rnode (rn); | |
180 | if (!srn->src_table) | |
181 | return NULL; | |
182 | ||
183 | return route_node_lookup (srn->src_table, (struct prefix *)src_p); | |
184 | } | |
185 | ||
186 | /* ----- exported functions ----- */ | |
187 | ||
188 | struct route_table * | |
189 | srcdest_table_init(void) | |
190 | { | |
191 | return route_table_init_with_delegate(&_srcdest_dstnode_delegate); | |
192 | } | |
193 | ||
194 | struct route_node * | |
195 | srcdest_route_next(struct route_node *rn) | |
196 | { | |
197 | struct route_node *next, *parent; | |
198 | ||
199 | /* For a non src-dest node, just return route_next */ | |
200 | if (!(rnode_is_dstnode(rn) || rnode_is_srcnode(rn))) | |
201 | return route_next(rn); | |
202 | ||
203 | if (rnode_is_dstnode(rn)) | |
204 | { | |
205 | /* This means the route_node is part of the top hierarchy | |
206 | * and refers to a destination prefix. */ | |
207 | struct srcdest_rnode *srn = srcdest_rnode_from_rnode(rn); | |
208 | ||
209 | if (srn->src_table) | |
210 | next = route_top(srn->src_table); | |
211 | else | |
212 | next = NULL; | |
213 | ||
214 | if (next) | |
215 | { | |
216 | /* There is a source prefix. Return the node for it */ | |
217 | route_unlock_node(rn); | |
218 | return next; | |
219 | } | |
220 | else | |
221 | { | |
222 | /* There is no source prefix, just continue as usual */ | |
223 | return route_next(rn); | |
224 | } | |
225 | } | |
226 | ||
227 | /* This part handles the case of iterating source nodes. */ | |
228 | parent = route_lock_node(rn->table->info); | |
229 | next = route_next(rn); | |
230 | ||
231 | if (next) | |
232 | { | |
233 | /* There is another source node, continue in the source table */ | |
234 | route_unlock_node(parent); | |
235 | return next; | |
236 | } | |
237 | else | |
238 | { | |
239 | /* The source table is complete, continue in the parent table */ | |
240 | return route_next(parent); | |
241 | } | |
242 | } | |
243 | ||
244 | struct route_node * | |
78b81eaa | 245 | srcdest_rnode_get (struct route_table *table, union prefixptr dst_pu, |
0964ad9c DL |
246 | struct prefix_ipv6 *src_p) |
247 | { | |
248 | struct prefix_ipv6 *dst_p = dst_pu.p6; | |
249 | struct route_node *rn; | |
250 | ||
251 | rn = route_node_get (table, (struct prefix *) dst_p); | |
252 | return srcdest_srcnode_get (rn, src_p); | |
253 | } | |
254 | ||
255 | struct route_node * | |
78b81eaa | 256 | srcdest_rnode_lookup (struct route_table *table, union prefixptr dst_pu, |
0964ad9c DL |
257 | struct prefix_ipv6 *src_p) |
258 | { | |
259 | struct prefix_ipv6 *dst_p = dst_pu.p6; | |
260 | struct route_node *rn; | |
261 | struct route_node *srn; | |
262 | ||
263 | rn = route_node_lookup_maynull (table, (struct prefix *) dst_p); | |
264 | srn = srcdest_srcnode_lookup (rn, src_p); | |
265 | ||
266 | if (rn != NULL && rn == srn && !rn->info) | |
267 | { | |
268 | /* Match the behavior of route_node_lookup and don't return an | |
269 | * empty route-node for a dest-route */ | |
270 | route_unlock_node(rn); | |
271 | return NULL; | |
272 | } | |
273 | return srn; | |
274 | } | |
275 | ||
276 | void | |
277 | srcdest_rnode_prefixes (struct route_node *rn, struct prefix **p, | |
278 | struct prefix **src_p) | |
279 | { | |
280 | if (rnode_is_srcnode (rn)) | |
281 | { | |
282 | struct route_node *dst_rn = rn->table->info; | |
283 | if (p) | |
284 | *p = &dst_rn->p; | |
285 | if (src_p) | |
286 | *src_p = &rn->p; | |
287 | } | |
288 | else | |
289 | { | |
290 | if (p) | |
291 | *p = &rn->p; | |
292 | if (src_p) | |
293 | *src_p = NULL; | |
294 | } | |
295 | } | |
296 | ||
297 | const char * | |
298 | srcdest_rnode2str (struct route_node *rn, char *str, int size) | |
299 | { | |
300 | struct prefix *dst_p, *src_p; | |
301 | char dst_buf[PREFIX_STRLEN], src_buf[PREFIX_STRLEN]; | |
302 | ||
303 | srcdest_rnode_prefixes(rn, &dst_p, &src_p); | |
304 | ||
305 | snprintf(str, size, "%s%s%s", | |
306 | prefix2str(dst_p, dst_buf, sizeof(dst_buf)), | |
307 | (src_p && src_p->prefixlen) ? " from " : "", | |
308 | (src_p && src_p->prefixlen) ? prefix2str(src_p, src_buf, | |
309 | sizeof(src_buf)) | |
310 | : ""); | |
311 | return str; | |
312 | } |