]>
Commit | Line | Data |
---|---|---|
718e3744 | 1 | /* |
2 | * Routing Table functions. | |
3 | * Copyright (C) 1998 Kunihiro Ishiguro | |
4 | * | |
5 | * This file is part of GNU Zebra. | |
6 | * | |
7 | * GNU Zebra is free software; you can redistribute it and/or modify it | |
8 | * under the terms of the GNU General Public License as published by the | |
9 | * Free Software Foundation; either version 2, or (at your option) any | |
10 | * later version. | |
11 | * | |
12 | * GNU Zebra is distributed in the hope that it will be useful, but | |
13 | * WITHOUT ANY WARRANTY; without even the implied warranty of | |
14 | * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU | |
15 | * General Public License for more details. | |
16 | * | |
17 | * You should have received a copy of the GNU General Public License | |
18 | * along with GNU Zebra; see the file COPYING. If not, write to the Free | |
19 | * Software Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA | |
20 | * 02111-1307, USA. | |
21 | */ | |
22 | ||
23 | #include <zebra.h> | |
24 | ||
25 | #include "prefix.h" | |
26 | #include "table.h" | |
27 | #include "memory.h" | |
28 | #include "sockunion.h" | |
29 | ||
3eb8ef37 AS |
30 | static void route_node_delete (struct route_node *); |
31 | static void route_table_free (struct route_table *); | |
718e3744 | 32 | \f |
33 | struct route_table * | |
34 | route_table_init (void) | |
35 | { | |
36 | struct route_table *rt; | |
37 | ||
38 | rt = XCALLOC (MTYPE_ROUTE_TABLE, sizeof (struct route_table)); | |
39 | return rt; | |
40 | } | |
41 | ||
42 | void | |
43 | route_table_finish (struct route_table *rt) | |
44 | { | |
45 | route_table_free (rt); | |
46 | } | |
47 | ||
48 | /* Allocate new route node. */ | |
8cc4198f | 49 | static struct route_node * |
50 | route_node_new (void) | |
718e3744 | 51 | { |
52 | struct route_node *node; | |
53 | node = XCALLOC (MTYPE_ROUTE_NODE, sizeof (struct route_node)); | |
54 | return node; | |
55 | } | |
56 | ||
57 | /* Allocate new route node with prefix set. */ | |
8cc4198f | 58 | static struct route_node * |
718e3744 | 59 | route_node_set (struct route_table *table, struct prefix *prefix) |
60 | { | |
61 | struct route_node *node; | |
62 | ||
63 | node = route_node_new (); | |
64 | ||
65 | prefix_copy (&node->p, prefix); | |
66 | node->table = table; | |
67 | ||
68 | return node; | |
69 | } | |
70 | ||
71 | /* Free route node. */ | |
8cc4198f | 72 | static void |
718e3744 | 73 | route_node_free (struct route_node *node) |
74 | { | |
75 | XFREE (MTYPE_ROUTE_NODE, node); | |
76 | } | |
77 | ||
78 | /* Free route table. */ | |
3eb8ef37 | 79 | static void |
718e3744 | 80 | route_table_free (struct route_table *rt) |
81 | { | |
82 | struct route_node *tmp_node; | |
83 | struct route_node *node; | |
84 | ||
85 | if (rt == NULL) | |
86 | return; | |
87 | ||
88 | node = rt->top; | |
89 | ||
3eb8ef37 AS |
90 | /* Bulk deletion of nodes remaining in this table. This function is not |
91 | called until workers have completed their dependency on this table. | |
92 | A final route_unlock_node() will not be called for these nodes. */ | |
718e3744 | 93 | while (node) |
94 | { | |
95 | if (node->l_left) | |
96 | { | |
97 | node = node->l_left; | |
98 | continue; | |
99 | } | |
100 | ||
101 | if (node->l_right) | |
102 | { | |
103 | node = node->l_right; | |
104 | continue; | |
105 | } | |
106 | ||
107 | tmp_node = node; | |
108 | node = node->parent; | |
109 | ||
3eb8ef37 AS |
110 | tmp_node->table->count--; |
111 | tmp_node->lock = 0; /* to cause assert if unlocked after this */ | |
112 | route_node_free (tmp_node); | |
113 | ||
718e3744 | 114 | if (node != NULL) |
115 | { | |
116 | if (node->l_left == tmp_node) | |
117 | node->l_left = NULL; | |
118 | else | |
119 | node->l_right = NULL; | |
718e3744 | 120 | } |
121 | else | |
122 | { | |
718e3744 | 123 | break; |
124 | } | |
125 | } | |
126 | ||
3eb8ef37 AS |
127 | assert (rt->count == 0); |
128 | ||
718e3744 | 129 | XFREE (MTYPE_ROUTE_TABLE, rt); |
130 | return; | |
131 | } | |
132 | ||
133 | /* Utility mask array. */ | |
38cc00cd | 134 | static const u_char maskbit[] = |
718e3744 | 135 | { |
136 | 0x00, 0x80, 0xc0, 0xe0, 0xf0, 0xf8, 0xfc, 0xfe, 0xff | |
137 | }; | |
138 | ||
139 | /* Common prefix route genaration. */ | |
140 | static void | |
141 | route_common (struct prefix *n, struct prefix *p, struct prefix *new) | |
142 | { | |
143 | int i; | |
144 | u_char diff; | |
145 | u_char mask; | |
146 | ||
147 | u_char *np = (u_char *)&n->u.prefix; | |
148 | u_char *pp = (u_char *)&p->u.prefix; | |
149 | u_char *newp = (u_char *)&new->u.prefix; | |
150 | ||
151 | for (i = 0; i < p->prefixlen / 8; i++) | |
152 | { | |
153 | if (np[i] == pp[i]) | |
154 | newp[i] = np[i]; | |
155 | else | |
156 | break; | |
157 | } | |
158 | ||
159 | new->prefixlen = i * 8; | |
160 | ||
161 | if (new->prefixlen != p->prefixlen) | |
162 | { | |
163 | diff = np[i] ^ pp[i]; | |
164 | mask = 0x80; | |
165 | while (new->prefixlen < p->prefixlen && !(mask & diff)) | |
166 | { | |
167 | mask >>= 1; | |
168 | new->prefixlen++; | |
169 | } | |
170 | newp[i] = np[i] & maskbit[new->prefixlen % 8]; | |
171 | } | |
172 | } | |
173 | ||
718e3744 | 174 | static void |
175 | set_link (struct route_node *node, struct route_node *new) | |
176 | { | |
1352ef32 | 177 | unsigned int bit = prefix_bit (&new->p.u.prefix, node->p.prefixlen); |
718e3744 | 178 | |
179 | node->link[bit] = new; | |
180 | new->parent = node; | |
181 | } | |
182 | ||
183 | /* Lock node. */ | |
184 | struct route_node * | |
185 | route_lock_node (struct route_node *node) | |
186 | { | |
187 | node->lock++; | |
188 | return node; | |
189 | } | |
190 | ||
191 | /* Unlock node. */ | |
192 | void | |
193 | route_unlock_node (struct route_node *node) | |
194 | { | |
3eb8ef37 | 195 | assert (node->lock > 0); |
718e3744 | 196 | node->lock--; |
197 | ||
198 | if (node->lock == 0) | |
199 | route_node_delete (node); | |
200 | } | |
201 | ||
718e3744 | 202 | /* Find matched prefix. */ |
203 | struct route_node * | |
38cc00cd | 204 | route_node_match (const struct route_table *table, const struct prefix *p) |
718e3744 | 205 | { |
206 | struct route_node *node; | |
207 | struct route_node *matched; | |
208 | ||
209 | matched = NULL; | |
210 | node = table->top; | |
211 | ||
212 | /* Walk down tree. If there is matched route then store it to | |
213 | matched. */ | |
214 | while (node && node->p.prefixlen <= p->prefixlen && | |
215 | prefix_match (&node->p, p)) | |
216 | { | |
217 | if (node->info) | |
218 | matched = node; | |
f8416810 PJ |
219 | |
220 | if (node->p.prefixlen == p->prefixlen) | |
221 | break; | |
222 | ||
1352ef32 | 223 | node = node->link[prefix_bit(&p->u.prefix, node->p.prefixlen)]; |
718e3744 | 224 | } |
225 | ||
226 | /* If matched route found, return it. */ | |
227 | if (matched) | |
228 | return route_lock_node (matched); | |
229 | ||
230 | return NULL; | |
231 | } | |
232 | ||
233 | struct route_node * | |
38cc00cd SH |
234 | route_node_match_ipv4 (const struct route_table *table, |
235 | const struct in_addr *addr) | |
718e3744 | 236 | { |
237 | struct prefix_ipv4 p; | |
238 | ||
239 | memset (&p, 0, sizeof (struct prefix_ipv4)); | |
240 | p.family = AF_INET; | |
241 | p.prefixlen = IPV4_MAX_PREFIXLEN; | |
242 | p.prefix = *addr; | |
243 | ||
244 | return route_node_match (table, (struct prefix *) &p); | |
245 | } | |
246 | ||
247 | #ifdef HAVE_IPV6 | |
248 | struct route_node * | |
38cc00cd SH |
249 | route_node_match_ipv6 (const struct route_table *table, |
250 | const struct in6_addr *addr) | |
718e3744 | 251 | { |
252 | struct prefix_ipv6 p; | |
253 | ||
254 | memset (&p, 0, sizeof (struct prefix_ipv6)); | |
255 | p.family = AF_INET6; | |
256 | p.prefixlen = IPV6_MAX_PREFIXLEN; | |
257 | p.prefix = *addr; | |
258 | ||
259 | return route_node_match (table, (struct prefix *) &p); | |
260 | } | |
261 | #endif /* HAVE_IPV6 */ | |
262 | ||
263 | /* Lookup same prefix node. Return NULL when we can't find route. */ | |
264 | struct route_node * | |
3eb8ef37 | 265 | route_node_lookup (const struct route_table *table, struct prefix *p) |
718e3744 | 266 | { |
267 | struct route_node *node; | |
47d3b607 JBD |
268 | u_char prefixlen = p->prefixlen; |
269 | const u_char *prefix = &p->u.prefix; | |
718e3744 | 270 | |
271 | node = table->top; | |
272 | ||
47d3b607 | 273 | while (node && node->p.prefixlen <= prefixlen && |
718e3744 | 274 | prefix_match (&node->p, p)) |
275 | { | |
47d3b607 | 276 | if (node->p.prefixlen == prefixlen) |
f8416810 | 277 | return node->info ? route_lock_node (node) : NULL; |
718e3744 | 278 | |
47d3b607 | 279 | node = node->link[prefix_bit(prefix, node->p.prefixlen)]; |
718e3744 | 280 | } |
281 | ||
282 | return NULL; | |
283 | } | |
284 | ||
285 | /* Add node to routing table. */ | |
286 | struct route_node * | |
3eb8ef37 | 287 | route_node_get (struct route_table *const table, struct prefix *p) |
718e3744 | 288 | { |
289 | struct route_node *new; | |
290 | struct route_node *node; | |
291 | struct route_node *match; | |
47d3b607 JBD |
292 | u_char prefixlen = p->prefixlen; |
293 | const u_char *prefix = &p->u.prefix; | |
718e3744 | 294 | |
295 | match = NULL; | |
296 | node = table->top; | |
47d3b607 | 297 | while (node && node->p.prefixlen <= prefixlen && |
718e3744 | 298 | prefix_match (&node->p, p)) |
299 | { | |
47d3b607 | 300 | if (node->p.prefixlen == prefixlen) |
f8416810 | 301 | return route_lock_node (node); |
47d3b607 | 302 | |
718e3744 | 303 | match = node; |
47d3b607 | 304 | node = node->link[prefix_bit(prefix, node->p.prefixlen)]; |
718e3744 | 305 | } |
306 | ||
307 | if (node == NULL) | |
308 | { | |
309 | new = route_node_set (table, p); | |
310 | if (match) | |
311 | set_link (match, new); | |
312 | else | |
313 | table->top = new; | |
314 | } | |
315 | else | |
316 | { | |
317 | new = route_node_new (); | |
318 | route_common (&node->p, p, &new->p); | |
319 | new->p.family = p->family; | |
320 | new->table = table; | |
321 | set_link (new, node); | |
322 | ||
323 | if (match) | |
324 | set_link (match, new); | |
325 | else | |
326 | table->top = new; | |
327 | ||
328 | if (new->p.prefixlen != p->prefixlen) | |
329 | { | |
330 | match = new; | |
331 | new = route_node_set (table, p); | |
332 | set_link (match, new); | |
3eb8ef37 | 333 | table->count++; |
718e3744 | 334 | } |
335 | } | |
3eb8ef37 | 336 | table->count++; |
718e3744 | 337 | route_lock_node (new); |
338 | ||
339 | return new; | |
340 | } | |
341 | ||
342 | /* Delete node from the routing table. */ | |
3eb8ef37 | 343 | static void |
718e3744 | 344 | route_node_delete (struct route_node *node) |
345 | { | |
346 | struct route_node *child; | |
347 | struct route_node *parent; | |
348 | ||
349 | assert (node->lock == 0); | |
350 | assert (node->info == NULL); | |
351 | ||
352 | if (node->l_left && node->l_right) | |
353 | return; | |
354 | ||
355 | if (node->l_left) | |
356 | child = node->l_left; | |
357 | else | |
358 | child = node->l_right; | |
359 | ||
360 | parent = node->parent; | |
361 | ||
362 | if (child) | |
363 | child->parent = parent; | |
364 | ||
365 | if (parent) | |
366 | { | |
367 | if (parent->l_left == node) | |
368 | parent->l_left = child; | |
369 | else | |
370 | parent->l_right = child; | |
371 | } | |
372 | else | |
373 | node->table->top = child; | |
374 | ||
3eb8ef37 AS |
375 | node->table->count--; |
376 | ||
718e3744 | 377 | route_node_free (node); |
378 | ||
379 | /* If parent node is stub then delete it also. */ | |
380 | if (parent && parent->lock == 0) | |
381 | route_node_delete (parent); | |
382 | } | |
383 | ||
384 | /* Get fist node and lock it. This function is useful when one want | |
385 | to lookup all the node exist in the routing table. */ | |
386 | struct route_node * | |
387 | route_top (struct route_table *table) | |
388 | { | |
389 | /* If there is no node in the routing table return NULL. */ | |
390 | if (table->top == NULL) | |
391 | return NULL; | |
392 | ||
393 | /* Lock the top node and return it. */ | |
394 | route_lock_node (table->top); | |
395 | return table->top; | |
396 | } | |
397 | ||
398 | /* Unlock current node and lock next node then return it. */ | |
399 | struct route_node * | |
400 | route_next (struct route_node *node) | |
401 | { | |
402 | struct route_node *next; | |
403 | struct route_node *start; | |
404 | ||
405 | /* Node may be deleted from route_unlock_node so we have to preserve | |
406 | next node's pointer. */ | |
407 | ||
408 | if (node->l_left) | |
409 | { | |
410 | next = node->l_left; | |
411 | route_lock_node (next); | |
412 | route_unlock_node (node); | |
413 | return next; | |
414 | } | |
415 | if (node->l_right) | |
416 | { | |
417 | next = node->l_right; | |
418 | route_lock_node (next); | |
419 | route_unlock_node (node); | |
420 | return next; | |
421 | } | |
422 | ||
423 | start = node; | |
424 | while (node->parent) | |
425 | { | |
426 | if (node->parent->l_left == node && node->parent->l_right) | |
427 | { | |
428 | next = node->parent->l_right; | |
429 | route_lock_node (next); | |
430 | route_unlock_node (start); | |
431 | return next; | |
432 | } | |
433 | node = node->parent; | |
434 | } | |
435 | route_unlock_node (start); | |
436 | return NULL; | |
437 | } | |
438 | ||
439 | /* Unlock current node and lock next node until limit. */ | |
440 | struct route_node * | |
441 | route_next_until (struct route_node *node, struct route_node *limit) | |
442 | { | |
443 | struct route_node *next; | |
444 | struct route_node *start; | |
445 | ||
446 | /* Node may be deleted from route_unlock_node so we have to preserve | |
447 | next node's pointer. */ | |
448 | ||
449 | if (node->l_left) | |
450 | { | |
451 | next = node->l_left; | |
452 | route_lock_node (next); | |
453 | route_unlock_node (node); | |
454 | return next; | |
455 | } | |
456 | if (node->l_right) | |
457 | { | |
458 | next = node->l_right; | |
459 | route_lock_node (next); | |
460 | route_unlock_node (node); | |
461 | return next; | |
462 | } | |
463 | ||
464 | start = node; | |
465 | while (node->parent && node != limit) | |
466 | { | |
467 | if (node->parent->l_left == node && node->parent->l_right) | |
468 | { | |
469 | next = node->parent->l_right; | |
470 | route_lock_node (next); | |
471 | route_unlock_node (start); | |
472 | return next; | |
473 | } | |
474 | node = node->parent; | |
475 | } | |
476 | route_unlock_node (start); | |
477 | return NULL; | |
478 | } | |
3eb8ef37 AS |
479 | |
480 | unsigned long | |
481 | route_table_count (const struct route_table *table) | |
482 | { | |
483 | return table->count; | |
484 | } |