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