Line data Source code
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 FRRouting (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 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
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"
31 : #include "printfrr.h"
32 :
33 27 : DEFINE_MTYPE_STATIC(LIB, ROUTE_SRC_NODE, "Route source node");
34 :
35 : /* ----- functions to manage rnodes _with_ srcdest table ----- */
36 : struct srcdest_rnode {
37 : /* must be first in structure for casting to/from route_node */
38 : ROUTE_NODE_FIELDS;
39 :
40 : struct route_table *src_table;
41 : };
42 :
43 187 : static struct srcdest_rnode *srcdest_rnode_from_rnode(struct route_node *rn)
44 : {
45 187 : assert(rnode_is_dstnode(rn));
46 187 : return (struct srcdest_rnode *)rn;
47 : }
48 :
49 : static struct route_node *srcdest_rnode_to_rnode(struct srcdest_rnode *srn)
50 : {
51 : return (struct route_node *)srn;
52 : }
53 :
54 36 : static struct route_node *srcdest_rnode_create(route_table_delegate_t *delegate,
55 : struct route_table *table)
56 : {
57 36 : struct srcdest_rnode *srn;
58 36 : srn = XCALLOC(MTYPE_ROUTE_NODE, sizeof(struct srcdest_rnode));
59 36 : return srcdest_rnode_to_rnode(srn);
60 : }
61 :
62 36 : static void srcdest_rnode_destroy(route_table_delegate_t *delegate,
63 : struct route_table *table,
64 : struct route_node *rn)
65 : {
66 36 : struct srcdest_rnode *srn = srcdest_rnode_from_rnode(rn);
67 36 : 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 36 : src_table = srn->src_table;
76 36 : srn->src_table = NULL;
77 36 : route_table_finish(src_table);
78 36 : XFREE(MTYPE_ROUTE_NODE, rn);
79 36 : }
80 :
81 : route_table_delegate_t _srcdest_dstnode_delegate = {
82 : .create_node = srcdest_rnode_create,
83 : .destroy_node = srcdest_rnode_destroy};
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 *
93 0 : srcdest_srcnode_create(route_table_delegate_t *delegate,
94 : struct route_table *table)
95 : {
96 0 : return XCALLOC(MTYPE_ROUTE_SRC_NODE, sizeof(struct route_node));
97 : }
98 :
99 0 : static void srcdest_srcnode_destroy(route_table_delegate_t *delegate,
100 : struct route_table *table,
101 : struct route_node *rn)
102 : {
103 0 : struct srcdest_rnode *srn;
104 :
105 0 : XFREE(MTYPE_ROUTE_SRC_NODE, rn);
106 :
107 0 : srn = route_table_get_info(table);
108 0 : 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 0 : route_table_finish(srn->src_table);
114 0 : 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 0 : route_unlock_node(srcdest_rnode_to_rnode(srn));
122 : }
123 0 : }
124 :
125 : route_table_delegate_t _srcdest_srcnode_delegate = {
126 : .create_node = srcdest_srcnode_create,
127 : .destroy_node = srcdest_srcnode_destroy};
128 :
129 : /* NB: read comments in code for refcounting before using! */
130 108 : static struct route_node *srcdest_srcnode_get(struct route_node *rn,
131 : const struct prefix_ipv6 *src_p)
132 : {
133 108 : struct srcdest_rnode *srn;
134 :
135 108 : if (!src_p || src_p->prefixlen == 0)
136 : return rn;
137 :
138 0 : srn = srcdest_rnode_from_rnode(rn);
139 0 : if (!srn->src_table) {
140 : /* this won't use srcdest_rnode, we're already on the source
141 : * here */
142 0 : srn->src_table = route_table_init_with_delegate(
143 : &_srcdest_srcnode_delegate);
144 0 : route_table_set_info(srn->src_table, srn);
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 0 : route_unlock_node(rn);
160 : }
161 :
162 0 : return route_node_get(srn->src_table, (const struct prefix *)src_p);
163 : }
164 :
165 19 : static struct route_node *srcdest_srcnode_lookup(
166 : struct route_node *rn,
167 : const struct prefix_ipv6 *src_p)
168 : {
169 19 : struct srcdest_rnode *srn;
170 :
171 19 : 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
175 : * won't
176 : * return return rn from any point beyond here, we should decrement its
177 : * refcnt.
178 : */
179 0 : route_unlock_node(rn);
180 :
181 0 : srn = srcdest_rnode_from_rnode(rn);
182 0 : if (!srn->src_table)
183 : return NULL;
184 :
185 0 : return route_node_lookup(srn->src_table, (const struct prefix *)src_p);
186 : }
187 :
188 : /* ----- exported functions ----- */
189 :
190 12 : struct route_table *srcdest_table_init(void)
191 : {
192 12 : return route_table_init_with_delegate(&_srcdest_dstnode_delegate);
193 : }
194 :
195 415 : struct route_node *srcdest_route_next(struct route_node *rn)
196 : {
197 415 : struct route_node *next, *parent;
198 :
199 : /* For a non src-dest node, just return route_next */
200 415 : if (!(rnode_is_dstnode(rn) || rnode_is_srcnode(rn)))
201 264 : return route_next(rn);
202 :
203 151 : 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 151 : struct srcdest_rnode *srn = srcdest_rnode_from_rnode(rn);
207 :
208 151 : if (srn->src_table)
209 0 : next = route_top(srn->src_table);
210 : else
211 : next = NULL;
212 :
213 0 : if (next) {
214 : /* There is a source prefix. Return the node for it */
215 0 : route_unlock_node(rn);
216 0 : return next;
217 : } else {
218 : /* There is no source prefix, just continue as usual */
219 151 : return route_next(rn);
220 : }
221 : }
222 :
223 : /* This part handles the case of iterating source nodes. */
224 0 : parent = route_lock_node(route_table_get_info(rn->table));
225 0 : next = route_next(rn);
226 :
227 0 : if (next) {
228 : /* There is another source node, continue in the source table */
229 0 : route_unlock_node(parent);
230 0 : return next;
231 : } else {
232 : /* The source table is complete, continue in the parent table */
233 0 : return route_next(parent);
234 : }
235 : }
236 :
237 108 : struct route_node *srcdest_rnode_get(struct route_table *table,
238 : union prefixconstptr dst_pu,
239 : const struct prefix_ipv6 *src_p)
240 : {
241 108 : const struct prefix_ipv6 *dst_p = dst_pu.p6;
242 108 : struct route_node *rn;
243 :
244 108 : rn = route_node_get(table, (const struct prefix *)dst_p);
245 108 : return srcdest_srcnode_get(rn, src_p);
246 : }
247 :
248 19 : struct route_node *srcdest_rnode_lookup(struct route_table *table,
249 : union prefixconstptr dst_pu,
250 : const struct prefix_ipv6 *src_p)
251 : {
252 19 : const struct prefix_ipv6 *dst_p = dst_pu.p6;
253 19 : struct route_node *rn;
254 19 : struct route_node *srn;
255 :
256 19 : rn = route_node_lookup_maynull(table, (const struct prefix *)dst_p);
257 19 : srn = srcdest_srcnode_lookup(rn, src_p);
258 :
259 19 : 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 0 : route_unlock_node(rn);
263 0 : return NULL;
264 : }
265 : return srn;
266 : }
267 :
268 149 : void srcdest_rnode_prefixes(const struct route_node *rn,
269 : const struct prefix **p,
270 : const struct prefix **src_p)
271 : {
272 149 : if (rnode_is_srcnode(rn)) {
273 0 : struct route_node *dst_rn = route_table_get_info(rn->table);
274 0 : if (p)
275 0 : *p = &dst_rn->p;
276 0 : if (src_p)
277 0 : *src_p = &rn->p;
278 : } else {
279 149 : if (p)
280 149 : *p = &rn->p;
281 149 : if (src_p)
282 149 : *src_p = NULL;
283 : }
284 149 : }
285 :
286 4 : const char *srcdest2str(const struct prefix *dst_p,
287 : const struct prefix_ipv6 *src_p,
288 : char *str, int size)
289 : {
290 4 : char dst_buf[PREFIX_STRLEN], src_buf[PREFIX_STRLEN];
291 :
292 4 : snprintf(str, size, "%s%s%s",
293 : prefix2str(dst_p, dst_buf, sizeof(dst_buf)),
294 0 : (src_p && src_p->prefixlen) ? " from " : "",
295 0 : (src_p && src_p->prefixlen)
296 0 : ? prefix2str(src_p, src_buf, sizeof(src_buf))
297 : : "");
298 4 : return str;
299 : }
300 :
301 0 : const char *srcdest_rnode2str(const struct route_node *rn, char *str, int size)
302 : {
303 0 : const struct prefix *dst_p, *src_p;
304 :
305 0 : srcdest_rnode_prefixes(rn, &dst_p, &src_p);
306 0 : return srcdest2str(dst_p, (const struct prefix_ipv6 *)src_p, str, size);
307 : }
308 :
309 9 : printfrr_ext_autoreg_p("RN", printfrr_rn);
310 4 : static ssize_t printfrr_rn(struct fbuf *buf, struct printfrr_eargs *ea,
311 : const void *ptr)
312 : {
313 4 : const struct route_node *rn = ptr;
314 4 : const struct prefix *dst_p, *src_p;
315 4 : char cbuf[PREFIX_STRLEN * 2 + 6];
316 :
317 4 : if (!rn)
318 0 : return bputs(buf, "(null)");
319 :
320 4 : srcdest_rnode_prefixes(rn, &dst_p, &src_p);
321 4 : srcdest2str(dst_p, (const struct prefix_ipv6 *)src_p,
322 : cbuf, sizeof(cbuf));
323 4 : return bputs(buf, cbuf);
324 : }
325 :
326 6 : struct route_table *srcdest_srcnode_table(struct route_node *rn)
327 : {
328 6 : if (rnode_is_dstnode(rn)) {
329 0 : struct srcdest_rnode *srn = srcdest_rnode_from_rnode(rn);
330 :
331 0 : return srn->src_table;
332 : }
333 : return NULL;
334 : }
|
