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