]>
Commit | Line | Data |
---|---|---|
718e3744 | 1 | /* BGP routing table |
896014f4 DL |
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 along | |
17 | * with this program; see the file COPYING; if not, write to the Free Software | |
18 | * Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA | |
19 | */ | |
718e3744 | 20 | |
21 | #include <zebra.h> | |
22 | ||
23 | #include "prefix.h" | |
24 | #include "memory.h" | |
25 | #include "sockunion.h" | |
3f9c7369 | 26 | #include "queue.h" |
039f3a34 | 27 | #include "filter.h" |
4dcadbef | 28 | #include "command.h" |
718e3744 | 29 | |
30 | #include "bgpd/bgpd.h" | |
31 | #include "bgpd/bgp_table.h" | |
32 | ||
d62a17ae | 33 | void bgp_table_lock(struct bgp_table *rt) |
228da428 | 34 | { |
d62a17ae | 35 | rt->lock++; |
228da428 CC |
36 | } |
37 | ||
d62a17ae | 38 | void bgp_table_unlock(struct bgp_table *rt) |
228da428 | 39 | { |
d62a17ae | 40 | assert(rt->lock > 0); |
41 | rt->lock--; | |
228da428 | 42 | |
d62a17ae | 43 | if (rt->lock != 0) { |
44 | return; | |
45 | } | |
718e3744 | 46 | |
d62a17ae | 47 | route_table_finish(rt->route_table); |
48 | rt->route_table = NULL; | |
228da428 | 49 | |
d62a17ae | 50 | XFREE(MTYPE_BGP_TABLE, rt); |
718e3744 | 51 | } |
52 | ||
d62a17ae | 53 | void bgp_table_finish(struct bgp_table **rt) |
718e3744 | 54 | { |
d62a17ae | 55 | if (*rt != NULL) { |
56 | bgp_table_unlock(*rt); | |
57 | *rt = NULL; | |
58 | } | |
718e3744 | 59 | } |
60 | ||
67174041 AS |
61 | /* |
62 | * bgp_node_create | |
63 | */ | |
d62a17ae | 64 | static struct route_node *bgp_node_create(route_table_delegate_t *delegate, |
65 | struct route_table *table) | |
718e3744 | 66 | { |
d62a17ae | 67 | struct bgp_node *node; |
68 | node = XCALLOC(MTYPE_BGP_NODE, sizeof(struct bgp_node)); | |
69 | return bgp_node_to_rnode(node); | |
718e3744 | 70 | } |
71 | ||
67174041 AS |
72 | /* |
73 | * bgp_node_destroy | |
74 | */ | |
d62a17ae | 75 | static void bgp_node_destroy(route_table_delegate_t *delegate, |
76 | struct route_table *table, struct route_node *node) | |
718e3744 | 77 | { |
d62a17ae | 78 | struct bgp_node *bgp_node; |
79 | bgp_node = bgp_node_from_rnode(node); | |
80 | XFREE(MTYPE_BGP_NODE, bgp_node); | |
718e3744 | 81 | } |
82 | ||
67174041 AS |
83 | /* |
84 | * Function vector to customize the behavior of the route table | |
85 | * library for BGP route tables. | |
86 | */ | |
d62a17ae | 87 | route_table_delegate_t bgp_table_delegate = {.create_node = bgp_node_create, |
88 | .destroy_node = bgp_node_destroy}; | |
718e3744 | 89 | |
67174041 AS |
90 | /* |
91 | * bgp_table_init | |
92 | */ | |
960035b2 | 93 | struct bgp_table *bgp_table_init(struct bgp *bgp, afi_t afi, safi_t safi) |
718e3744 | 94 | { |
d62a17ae | 95 | struct bgp_table *rt; |
718e3744 | 96 | |
d62a17ae | 97 | rt = XCALLOC(MTYPE_BGP_TABLE, sizeof(struct bgp_table)); |
718e3744 | 98 | |
d62a17ae | 99 | rt->route_table = route_table_init_with_delegate(&bgp_table_delegate); |
718e3744 | 100 | |
d62a17ae | 101 | /* |
102 | * Set up back pointer to bgp_table. | |
103 | */ | |
104 | rt->route_table->info = rt; | |
718e3744 | 105 | |
960035b2 PZ |
106 | /* |
107 | * pointer to bgp instance allows working back from bgp_info to bgp | |
108 | */ | |
109 | rt->bgp = bgp; | |
110 | ||
d62a17ae | 111 | bgp_table_lock(rt); |
112 | rt->afi = afi; | |
113 | rt->safi = safi; | |
cbdfbaa5 | 114 | |
d62a17ae | 115 | return rt; |
cbdfbaa5 | 116 | } |
1dacdd8b MR |
117 | |
118 | static struct bgp_node * | |
119 | bgp_route_next_until_maxlen(struct bgp_node *node, const struct bgp_node *limit, | |
120 | const uint8_t maxlen) | |
121 | { | |
122 | if (node->l_left && node->p.prefixlen < maxlen | |
123 | && node->l_left->p.prefixlen <= maxlen) { | |
124 | return bgp_node_from_rnode(node->l_left); | |
125 | } | |
126 | if (node->l_right && node->p.prefixlen < maxlen | |
127 | && node->l_right->p.prefixlen <= maxlen) { | |
128 | return bgp_node_from_rnode(node->l_right); | |
129 | } | |
130 | ||
131 | while (node->parent && node != limit) { | |
132 | if (bgp_node_from_rnode(node->parent->l_left) == node | |
133 | && node->parent->l_right) { | |
134 | return bgp_node_from_rnode(node->parent->l_right); | |
135 | } | |
136 | node = bgp_node_from_rnode(node->parent); | |
137 | } | |
138 | return NULL; | |
139 | } | |
140 | ||
141 | void bgp_table_range_lookup(const struct bgp_table *table, struct prefix *p, | |
142 | uint8_t maxlen, struct list *matches) | |
143 | { | |
144 | struct bgp_node *node = bgp_node_from_rnode(table->route_table->top); | |
145 | struct bgp_node *matched = NULL; | |
146 | ||
1dacdd8b MR |
147 | while (node && node->p.prefixlen <= p->prefixlen |
148 | && prefix_match(&node->p, p)) { | |
149 | if (node->info && node->p.prefixlen == p->prefixlen) { | |
150 | matched = node; | |
151 | break; | |
152 | } | |
153 | node = bgp_node_from_rnode(node->link[prefix_bit( | |
154 | &p->u.prefix, node->p.prefixlen)]); | |
155 | } | |
156 | ||
9f134cdc A |
157 | if (node == NULL) |
158 | return; | |
159 | ||
1dacdd8b MR |
160 | if ((matched == NULL && node->p.prefixlen > maxlen) || !node->parent) |
161 | return; | |
162 | else if (matched == NULL) | |
163 | matched = node = bgp_node_from_rnode(node->parent); | |
164 | ||
165 | if (matched->info) { | |
166 | bgp_lock_node(matched); | |
167 | listnode_add(matches, matched); | |
168 | } | |
169 | ||
170 | while ((node = bgp_route_next_until_maxlen(node, matched, maxlen))) { | |
171 | if (prefix_match(p, &node->p)) { | |
172 | if (node->info) { | |
173 | bgp_lock_node(node); | |
174 | listnode_add(matches, node); | |
175 | } | |
176 | } | |
177 | } | |
178 | } |