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