]>
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" | |
dcc68b5e | 32 | #include "bgp_addpath.h" |
718e3744 | 33 | |
d62a17ae | 34 | void bgp_table_lock(struct bgp_table *rt) |
228da428 | 35 | { |
d62a17ae | 36 | rt->lock++; |
228da428 CC |
37 | } |
38 | ||
d62a17ae | 39 | void bgp_table_unlock(struct bgp_table *rt) |
228da428 | 40 | { |
d62a17ae | 41 | assert(rt->lock > 0); |
42 | rt->lock--; | |
228da428 | 43 | |
d62a17ae | 44 | if (rt->lock != 0) { |
45 | return; | |
46 | } | |
718e3744 | 47 | |
d62a17ae | 48 | route_table_finish(rt->route_table); |
49 | rt->route_table = NULL; | |
228da428 | 50 | |
d62a17ae | 51 | XFREE(MTYPE_BGP_TABLE, rt); |
718e3744 | 52 | } |
53 | ||
d62a17ae | 54 | void bgp_table_finish(struct bgp_table **rt) |
718e3744 | 55 | { |
d62a17ae | 56 | if (*rt != NULL) { |
57 | bgp_table_unlock(*rt); | |
58 | *rt = NULL; | |
59 | } | |
718e3744 | 60 | } |
61 | ||
67174041 AS |
62 | /* |
63 | * bgp_node_create | |
64 | */ | |
d62a17ae | 65 | static struct route_node *bgp_node_create(route_table_delegate_t *delegate, |
66 | struct route_table *table) | |
718e3744 | 67 | { |
d62a17ae | 68 | struct bgp_node *node; |
69 | node = XCALLOC(MTYPE_BGP_NODE, sizeof(struct bgp_node)); | |
a79c04e7 DS |
70 | |
71 | RB_INIT(bgp_adj_out_rb, &node->adj_out); | |
d62a17ae | 72 | return bgp_node_to_rnode(node); |
718e3744 | 73 | } |
74 | ||
67174041 AS |
75 | /* |
76 | * bgp_node_destroy | |
77 | */ | |
d62a17ae | 78 | static void bgp_node_destroy(route_table_delegate_t *delegate, |
79 | struct route_table *table, struct route_node *node) | |
718e3744 | 80 | { |
d62a17ae | 81 | struct bgp_node *bgp_node; |
dcc68b5e | 82 | struct bgp_table *rt; |
d62a17ae | 83 | bgp_node = bgp_node_from_rnode(node); |
dcc68b5e MS |
84 | rt = table->info; |
85 | ||
86 | if (rt->bgp) { | |
87 | bgp_addpath_free_node_data(&rt->bgp->tx_addpath, | |
88 | &bgp_node->tx_addpath, | |
89 | rt->afi, rt->safi); | |
90 | } | |
91 | ||
d62a17ae | 92 | XFREE(MTYPE_BGP_NODE, bgp_node); |
718e3744 | 93 | } |
94 | ||
67174041 AS |
95 | /* |
96 | * Function vector to customize the behavior of the route table | |
97 | * library for BGP route tables. | |
98 | */ | |
d62a17ae | 99 | route_table_delegate_t bgp_table_delegate = {.create_node = bgp_node_create, |
100 | .destroy_node = bgp_node_destroy}; | |
718e3744 | 101 | |
67174041 AS |
102 | /* |
103 | * bgp_table_init | |
104 | */ | |
960035b2 | 105 | struct bgp_table *bgp_table_init(struct bgp *bgp, afi_t afi, safi_t safi) |
718e3744 | 106 | { |
d62a17ae | 107 | struct bgp_table *rt; |
718e3744 | 108 | |
d62a17ae | 109 | rt = XCALLOC(MTYPE_BGP_TABLE, sizeof(struct bgp_table)); |
718e3744 | 110 | |
d62a17ae | 111 | rt->route_table = route_table_init_with_delegate(&bgp_table_delegate); |
718e3744 | 112 | |
d62a17ae | 113 | /* |
114 | * Set up back pointer to bgp_table. | |
115 | */ | |
6ca30e9e | 116 | route_table_set_info(rt->route_table, rt); |
718e3744 | 117 | |
960035b2 | 118 | /* |
9b6d8fcf | 119 | * pointer to bgp instance allows working back from bgp_path_info to bgp |
960035b2 PZ |
120 | */ |
121 | rt->bgp = bgp; | |
122 | ||
d62a17ae | 123 | bgp_table_lock(rt); |
124 | rt->afi = afi; | |
125 | rt->safi = safi; | |
cbdfbaa5 | 126 | |
d62a17ae | 127 | return rt; |
cbdfbaa5 | 128 | } |
1dacdd8b | 129 | |
f009ff26 | 130 | /* Delete the route node from the selection deferral route list */ |
131 | void bgp_delete_listnode(struct bgp_node *node) | |
132 | { | |
133 | struct route_node *rn = NULL; | |
134 | struct bgp_table *table = NULL; | |
135 | struct bgp *bgp = NULL; | |
136 | afi_t afi; | |
137 | safi_t safi; | |
138 | ||
139 | /* If the route to be deleted is selection pending, update the | |
140 | * route node in gr_info | |
141 | */ | |
142 | if (CHECK_FLAG(node->flags, BGP_NODE_SELECT_DEFER)) { | |
143 | table = bgp_node_table(node); | |
9e3b51a7 | 144 | |
145 | if (table) { | |
f009ff26 | 146 | bgp = table->bgp; |
9e3b51a7 | 147 | afi = table->afi; |
148 | safi = table->safi; | |
2ba1fe69 | 149 | } else |
150 | return; | |
151 | ||
f009ff26 | 152 | rn = bgp_node_to_rnode(node); |
153 | ||
f009ff26 | 154 | if (bgp && rn && rn->lock == 1) { |
155 | /* Delete the route from the selection pending list */ | |
36235319 QY |
156 | if ((node->rt_node) |
157 | && (bgp->gr_info[afi][safi].route_list)) { | |
f009ff26 | 158 | list_delete_node( |
159 | bgp->gr_info[afi][safi].route_list, | |
36235319 | 160 | node->rt_node); |
f009ff26 | 161 | node->rt_node = NULL; |
162 | } | |
163 | } | |
164 | } | |
165 | } | |
166 | ||
1dacdd8b MR |
167 | static struct bgp_node * |
168 | bgp_route_next_until_maxlen(struct bgp_node *node, const struct bgp_node *limit, | |
169 | const uint8_t maxlen) | |
170 | { | |
b54892e0 DS |
171 | const struct prefix *p = bgp_node_get_prefix(node); |
172 | ||
173 | if (node->l_left) { | |
174 | const struct prefix *left_p = | |
175 | bgp_node_get_prefix(bgp_node_from_rnode(node->l_left)); | |
176 | ||
177 | if (p->prefixlen < maxlen && left_p->prefixlen <= maxlen) | |
178 | return bgp_node_from_rnode(node->l_left); | |
1dacdd8b | 179 | } |
b54892e0 DS |
180 | |
181 | if (node->l_right) { | |
182 | const struct prefix *right_p = | |
183 | bgp_node_get_prefix(bgp_node_from_rnode(node->l_right)); | |
184 | ||
185 | if (p->prefixlen < maxlen && right_p->prefixlen <= maxlen) | |
186 | return bgp_node_from_rnode(node->l_right); | |
1dacdd8b MR |
187 | } |
188 | ||
189 | while (node->parent && node != limit) { | |
190 | if (bgp_node_from_rnode(node->parent->l_left) == node | |
191 | && node->parent->l_right) { | |
192 | return bgp_node_from_rnode(node->parent->l_right); | |
193 | } | |
194 | node = bgp_node_from_rnode(node->parent); | |
195 | } | |
196 | return NULL; | |
197 | } | |
198 | ||
99a088e7 DS |
199 | void bgp_table_range_lookup(const struct bgp_table *table, |
200 | const struct prefix *p, | |
1dacdd8b MR |
201 | uint8_t maxlen, struct list *matches) |
202 | { | |
203 | struct bgp_node *node = bgp_node_from_rnode(table->route_table->top); | |
204 | struct bgp_node *matched = NULL; | |
205 | ||
24b7eb48 MR |
206 | if (node == NULL) |
207 | return; | |
208 | ||
b54892e0 DS |
209 | const struct prefix *node_p = bgp_node_get_prefix(node); |
210 | ||
211 | while (node && node_p->prefixlen <= p->prefixlen | |
212 | && prefix_match(node_p, p)) { | |
6f94b685 | 213 | if (bgp_node_has_bgp_path_info_data(node) |
b54892e0 | 214 | && node_p->prefixlen == p->prefixlen) { |
1dacdd8b MR |
215 | matched = node; |
216 | break; | |
217 | } | |
218 | node = bgp_node_from_rnode(node->link[prefix_bit( | |
b54892e0 DS |
219 | &p->u.prefix, node_p->prefixlen)]); |
220 | node_p = bgp_node_get_prefix(node); | |
1dacdd8b MR |
221 | } |
222 | ||
5911f65c DS |
223 | if (!node) |
224 | return; | |
225 | ||
b54892e0 DS |
226 | node_p = bgp_node_get_prefix(node); |
227 | if (matched == NULL && node_p->prefixlen <= maxlen | |
228 | && prefix_match(p, node_p) && node->parent == NULL) | |
24b7eb48 | 229 | matched = node; |
b54892e0 DS |
230 | else if ((matched == NULL && node_p->prefixlen > maxlen) |
231 | || !node->parent) | |
1dacdd8b | 232 | return; |
5911f65c | 233 | else if (matched == NULL && node->parent) |
1dacdd8b MR |
234 | matched = node = bgp_node_from_rnode(node->parent); |
235 | ||
5911f65c DS |
236 | if (!matched) |
237 | return; | |
238 | ||
6f94b685 | 239 | if (bgp_node_has_bgp_path_info_data(matched)) { |
1dacdd8b MR |
240 | bgp_lock_node(matched); |
241 | listnode_add(matches, matched); | |
242 | } | |
243 | ||
244 | while ((node = bgp_route_next_until_maxlen(node, matched, maxlen))) { | |
b54892e0 DS |
245 | node_p = bgp_node_get_prefix(node); |
246 | if (prefix_match(p, node_p)) { | |
6f94b685 | 247 | if (bgp_node_has_bgp_path_info_data(node)) { |
1dacdd8b MR |
248 | bgp_lock_node(node); |
249 | listnode_add(matches, node); | |
250 | } | |
251 | } | |
252 | } | |
253 | } |