2 * SRC-DEST Routing Table
4 * Copyright (C) 2017 by David Lamparter & Christian Franke,
5 * Open Source Routing / NetDEF Inc.
7 * This file is part of FRRouting (FRR)
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
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.
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
26 #include "srcdest_table.h"
33 DEFINE_MTYPE_STATIC(LIB
, ROUTE_SRC_NODE
, "Route source node");
35 /* ----- functions to manage rnodes _with_ srcdest table ----- */
36 struct srcdest_rnode
{
37 /* must be first in structure for casting to/from route_node */
40 struct route_table
*src_table
;
43 static struct srcdest_rnode
*srcdest_rnode_from_rnode(struct route_node
*rn
)
45 assert(rnode_is_dstnode(rn
));
46 return (struct srcdest_rnode
*)rn
;
49 static struct route_node
*srcdest_rnode_to_rnode(struct srcdest_rnode
*srn
)
51 return (struct route_node
*)srn
;
54 static struct route_node
*srcdest_rnode_create(route_table_delegate_t
*delegate
,
55 struct route_table
*table
)
57 struct srcdest_rnode
*srn
;
58 srn
= XCALLOC(MTYPE_ROUTE_NODE
, sizeof(struct srcdest_rnode
));
59 return srcdest_rnode_to_rnode(srn
);
62 static void srcdest_rnode_destroy(route_table_delegate_t
*delegate
,
63 struct route_table
*table
,
64 struct route_node
*rn
)
66 struct srcdest_rnode
*srn
= srcdest_rnode_from_rnode(rn
);
67 struct route_table
*src_table
;
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.
73 * (Compare with srcdest_srcnode_destroy)
75 src_table
= srn
->src_table
;
76 srn
->src_table
= NULL
;
77 route_table_finish(src_table
);
78 XFREE(MTYPE_ROUTE_NODE
, rn
);
81 route_table_delegate_t _srcdest_dstnode_delegate
= {
82 .create_node
= srcdest_rnode_create
,
83 .destroy_node
= srcdest_rnode_destroy
};
85 /* ----- functions to manage rnodes _in_ srcdest table ----- */
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) */
92 static struct route_node
*
93 srcdest_srcnode_create(route_table_delegate_t
*delegate
,
94 struct route_table
*table
)
96 return XCALLOC(MTYPE_ROUTE_SRC_NODE
, sizeof(struct route_node
));
99 static void srcdest_srcnode_destroy(route_table_delegate_t
*delegate
,
100 struct route_table
*table
,
101 struct route_node
*rn
)
103 struct srcdest_rnode
*srn
;
105 XFREE(MTYPE_ROUTE_SRC_NODE
, rn
);
107 srn
= route_table_get_info(table
);
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()
113 route_table_finish(srn
->src_table
);
114 srn
->src_table
= NULL
;
116 /* drop the ref we're holding in srcdest_node_get(). there
118 * non-srcdest routes, so the route_node may still exist.
120 * important to clear src_table above. */
121 route_unlock_node(srcdest_rnode_to_rnode(srn
));
125 route_table_delegate_t _srcdest_srcnode_delegate
= {
126 .create_node
= srcdest_srcnode_create
,
127 .destroy_node
= srcdest_srcnode_destroy
};
129 /* NB: read comments in code for refcounting before using! */
130 static struct route_node
*srcdest_srcnode_get(struct route_node
*rn
,
131 const struct prefix_ipv6
*src_p
)
133 struct srcdest_rnode
*srn
;
135 if (!src_p
|| src_p
->prefixlen
== 0)
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
142 srn
->src_table
= route_table_init_with_delegate(
143 &_srcdest_srcnode_delegate
);
144 route_table_set_info(srn
->src_table
, srn
);
146 /* there is no route_unlock_node on the original rn here.
147 * The reference is kept for the src_table. */
149 /* only keep 1 reference for the src_table, makes the
151 * more similar to the non-srcdest case. Either way after
153 * function, the only reference held is the one on the return
156 * We can safely drop our reference here because src_table is
158 * another reference, so this won't free rn */
159 route_unlock_node(rn
);
162 return route_node_get(srn
->src_table
, (const struct prefix
*)src_p
);
165 static struct route_node
*srcdest_srcnode_lookup(
166 struct route_node
*rn
,
167 const struct prefix_ipv6
*src_p
)
169 struct srcdest_rnode
*srn
;
171 if (!rn
|| !src_p
|| src_p
->prefixlen
== 0)
174 /* We got this rn from a lookup, so its refcnt was incremented. As we
176 * return return rn from any point beyond here, we should decrement its
179 route_unlock_node(rn
);
181 srn
= srcdest_rnode_from_rnode(rn
);
185 return route_node_lookup(srn
->src_table
, (const struct prefix
*)src_p
);
188 /* ----- exported functions ----- */
190 struct route_table
*srcdest_table_init(void)
192 return route_table_init_with_delegate(&_srcdest_dstnode_delegate
);
195 struct route_node
*srcdest_route_next(struct route_node
*rn
)
197 struct route_node
*next
, *parent
;
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
);
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
);
209 next
= route_top(srn
->src_table
);
214 /* There is a source prefix. Return the node for it */
215 route_unlock_node(rn
);
218 /* There is no source prefix, just continue as usual */
219 return route_next(rn
);
223 /* This part handles the case of iterating source nodes. */
224 parent
= route_lock_node(route_table_get_info(rn
->table
));
225 next
= route_next(rn
);
228 /* There is another source node, continue in the source table */
229 route_unlock_node(parent
);
232 /* The source table is complete, continue in the parent table */
233 return route_next(parent
);
237 struct route_node
*srcdest_rnode_get(struct route_table
*table
,
238 union prefixconstptr dst_pu
,
239 const struct prefix_ipv6
*src_p
)
241 const struct prefix_ipv6
*dst_p
= dst_pu
.p6
;
242 struct route_node
*rn
;
244 rn
= route_node_get(table
, (const struct prefix
*)dst_p
);
245 return srcdest_srcnode_get(rn
, src_p
);
248 struct route_node
*srcdest_rnode_lookup(struct route_table
*table
,
249 union prefixconstptr dst_pu
,
250 const struct prefix_ipv6
*src_p
)
252 const struct prefix_ipv6
*dst_p
= dst_pu
.p6
;
253 struct route_node
*rn
;
254 struct route_node
*srn
;
256 rn
= route_node_lookup_maynull(table
, (const struct prefix
*)dst_p
);
257 srn
= srcdest_srcnode_lookup(rn
, src_p
);
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
);
268 void srcdest_rnode_prefixes(const struct route_node
*rn
,
269 const struct prefix
**p
,
270 const struct prefix
**src_p
)
272 if (rnode_is_srcnode(rn
)) {
273 struct route_node
*dst_rn
= route_table_get_info(rn
->table
);
286 const char *srcdest2str(const struct prefix
*dst_p
,
287 const struct prefix_ipv6
*src_p
,
290 char dst_buf
[PREFIX_STRLEN
], src_buf
[PREFIX_STRLEN
];
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
))
301 const char *srcdest_rnode2str(const struct route_node
*rn
, char *str
, int size
)
303 const struct prefix
*dst_p
, *src_p
;
305 srcdest_rnode_prefixes(rn
, &dst_p
, &src_p
);
306 return srcdest2str(dst_p
, (const struct prefix_ipv6
*)src_p
, str
, size
);
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
)
313 const struct route_node
*rn
= ptr
;
314 const struct prefix
*dst_p
, *src_p
;
317 srcdest_rnode_prefixes(rn
, &dst_p
, &src_p
);
318 srcdest2str(dst_p
, (const struct prefix_ipv6
*)src_p
, buf
, bsz
);
320 strlcpy(buf
, "NULL", bsz
);
326 struct route_table
*srcdest_srcnode_table(struct route_node
*rn
)
328 if (rnode_is_dstnode(rn
)) {
329 struct srcdest_rnode
*srn
= srcdest_rnode_from_rnode(rn
);
331 return srn
->src_table
;