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 FreeRangeRouting (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"
32 DEFINE_MTYPE_STATIC(LIB
, ROUTE_SRC_NODE
, "Route source node")
34 /* ----- functions to manage rnodes _with_ srcdest table ----- */
35 struct srcdest_rnode
{
36 /* must be first in structure for casting to/from route_node */
39 struct route_table
*src_table
;
42 static struct srcdest_rnode
*srcdest_rnode_from_rnode(struct route_node
*rn
)
44 assert(rnode_is_dstnode(rn
));
45 return (struct srcdest_rnode
*)rn
;
48 static struct route_node
*srcdest_rnode_to_rnode(struct srcdest_rnode
*srn
)
50 return (struct route_node
*)srn
;
53 static struct route_node
*srcdest_rnode_create(route_table_delegate_t
*delegate
,
54 struct route_table
*table
)
56 struct srcdest_rnode
*srn
;
57 srn
= XCALLOC(MTYPE_ROUTE_NODE
, sizeof(struct srcdest_rnode
));
58 return srcdest_rnode_to_rnode(srn
);
61 static void srcdest_rnode_destroy(route_table_delegate_t
*delegate
,
62 struct route_table
*table
,
63 struct route_node
*rn
)
65 struct srcdest_rnode
*srn
= srcdest_rnode_from_rnode(rn
);
66 struct route_table
*src_table
;
68 /* Clear route node's src_table here already, otherwise the
69 * deletion of the last node in the src_table will trigger
70 * another call to route_table_finish for the src_table.
72 * (Compare with srcdest_srcnode_destroy)
74 src_table
= srn
->src_table
;
75 srn
->src_table
= NULL
;
76 route_table_finish(src_table
);
77 XFREE(MTYPE_ROUTE_NODE
, rn
);
80 route_table_delegate_t _srcdest_dstnode_delegate
= {
81 .create_node
= srcdest_rnode_create
,
82 .destroy_node
= srcdest_rnode_destroy
};
84 /* ----- functions to manage rnodes _in_ srcdest table ----- */
86 /* node creation / deletion for srcdest source prefix nodes.
87 * the route_node isn't actually different from the normal route_node,
88 * but the cleanup is special to free the table (and possibly the
89 * destination prefix's route_node) */
91 static struct route_node
*
92 srcdest_srcnode_create(route_table_delegate_t
*delegate
,
93 struct route_table
*table
)
95 return XCALLOC(MTYPE_ROUTE_SRC_NODE
, sizeof(struct route_node
));
98 static void srcdest_srcnode_destroy(route_table_delegate_t
*delegate
,
99 struct route_table
*table
,
100 struct route_node
*rn
)
102 struct srcdest_rnode
*srn
;
104 XFREE(MTYPE_ROUTE_SRC_NODE
, rn
);
107 if (srn
->src_table
&& route_table_count(srn
->src_table
) == 0) {
108 /* deleting the route_table from inside destroy_node is ONLY
109 * permitted IF table->count is 0! see lib/table.c
110 * route_node_delete()
112 route_table_finish(srn
->src_table
);
113 srn
->src_table
= NULL
;
115 /* drop the ref we're holding in srcdest_node_get(). there
117 * non-srcdest routes, so the route_node may still exist.
119 * important to clear src_table above. */
120 route_unlock_node(srcdest_rnode_to_rnode(srn
));
124 route_table_delegate_t _srcdest_srcnode_delegate
= {
125 .create_node
= srcdest_srcnode_create
,
126 .destroy_node
= srcdest_srcnode_destroy
};
128 /* NB: read comments in code for refcounting before using! */
129 static struct route_node
*srcdest_srcnode_get(struct route_node
*rn
,
130 struct prefix_ipv6
*src_p
)
132 struct srcdest_rnode
*srn
;
134 if (!src_p
|| src_p
->prefixlen
== 0)
137 srn
= srcdest_rnode_from_rnode(rn
);
138 if (!srn
->src_table
) {
139 /* this won't use srcdest_rnode, we're already on the source
141 srn
->src_table
= route_table_init_with_delegate(
142 &_srcdest_srcnode_delegate
);
143 srn
->src_table
->info
= srn
;
145 /* there is no route_unlock_node on the original rn here.
146 * The reference is kept for the src_table. */
148 /* only keep 1 reference for the src_table, makes the
150 * more similar to the non-srcdest case. Either way after
152 * function, the only reference held is the one on the return
155 * We can safely drop our reference here because src_table is
157 * another reference, so this won't free rn */
158 route_unlock_node(rn
);
161 return route_node_get(srn
->src_table
, (struct prefix
*)src_p
);
164 static struct route_node
*srcdest_srcnode_lookup(struct route_node
*rn
,
165 struct prefix_ipv6
*src_p
)
167 struct srcdest_rnode
*srn
;
169 if (!rn
|| !src_p
|| src_p
->prefixlen
== 0)
172 /* We got this rn from a lookup, so its refcnt was incremented. As we
174 * return return rn from any point beyond here, we should decrement its
177 route_unlock_node(rn
);
179 srn
= srcdest_rnode_from_rnode(rn
);
183 return route_node_lookup(srn
->src_table
, (struct prefix
*)src_p
);
186 /* ----- exported functions ----- */
188 struct route_table
*srcdest_table_init(void)
190 return route_table_init_with_delegate(&_srcdest_dstnode_delegate
);
193 struct route_node
*srcdest_route_next(struct route_node
*rn
)
195 struct route_node
*next
, *parent
;
197 /* For a non src-dest node, just return route_next */
198 if (!(rnode_is_dstnode(rn
) || rnode_is_srcnode(rn
)))
199 return route_next(rn
);
201 if (rnode_is_dstnode(rn
)) {
202 /* This means the route_node is part of the top hierarchy
203 * and refers to a destination prefix. */
204 struct srcdest_rnode
*srn
= srcdest_rnode_from_rnode(rn
);
207 next
= route_top(srn
->src_table
);
212 /* There is a source prefix. Return the node for it */
213 route_unlock_node(rn
);
216 /* There is no source prefix, just continue as usual */
217 return route_next(rn
);
221 /* This part handles the case of iterating source nodes. */
222 parent
= route_lock_node(rn
->table
->info
);
223 next
= route_next(rn
);
226 /* There is another source node, continue in the source table */
227 route_unlock_node(parent
);
230 /* The source table is complete, continue in the parent table */
231 return route_next(parent
);
235 struct route_node
*srcdest_rnode_get(struct route_table
*table
,
236 union prefixptr dst_pu
,
237 struct prefix_ipv6
*src_p
)
239 struct prefix_ipv6
*dst_p
= dst_pu
.p6
;
240 struct route_node
*rn
;
242 rn
= route_node_get(table
, (struct prefix
*)dst_p
);
243 return srcdest_srcnode_get(rn
, src_p
);
246 struct route_node
*srcdest_rnode_lookup(struct route_table
*table
,
247 union prefixptr dst_pu
,
248 struct prefix_ipv6
*src_p
)
250 struct prefix_ipv6
*dst_p
= dst_pu
.p6
;
251 struct route_node
*rn
;
252 struct route_node
*srn
;
254 rn
= route_node_lookup_maynull(table
, (struct prefix
*)dst_p
);
255 srn
= srcdest_srcnode_lookup(rn
, src_p
);
257 if (rn
!= NULL
&& rn
== srn
&& !rn
->info
) {
258 /* Match the behavior of route_node_lookup and don't return an
259 * empty route-node for a dest-route */
260 route_unlock_node(rn
);
266 void srcdest_rnode_prefixes(struct route_node
*rn
, struct prefix
**p
,
267 struct prefix
**src_p
)
269 if (rnode_is_srcnode(rn
)) {
270 struct route_node
*dst_rn
= rn
->table
->info
;
283 const char *srcdest_rnode2str(struct route_node
*rn
, char *str
, int size
)
285 struct prefix
*dst_p
, *src_p
;
286 char dst_buf
[PREFIX_STRLEN
], src_buf
[PREFIX_STRLEN
];
288 srcdest_rnode_prefixes(rn
, &dst_p
, &src_p
);
290 snprintf(str
, size
, "%s%s%s",
291 prefix2str(dst_p
, dst_buf
, sizeof(dst_buf
)),
292 (src_p
&& src_p
->prefixlen
) ? " from " : "",
293 (src_p
&& src_p
->prefixlen
)
294 ? prefix2str(src_p
, src_buf
, sizeof(src_buf
))