]>
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 MR |
129 | |
130 | static struct bgp_node * | |
131 | bgp_route_next_until_maxlen(struct bgp_node *node, const struct bgp_node *limit, | |
132 | const uint8_t maxlen) | |
133 | { | |
134 | if (node->l_left && node->p.prefixlen < maxlen | |
135 | && node->l_left->p.prefixlen <= maxlen) { | |
136 | return bgp_node_from_rnode(node->l_left); | |
137 | } | |
138 | if (node->l_right && node->p.prefixlen < maxlen | |
139 | && node->l_right->p.prefixlen <= maxlen) { | |
140 | return bgp_node_from_rnode(node->l_right); | |
141 | } | |
142 | ||
143 | while (node->parent && node != limit) { | |
144 | if (bgp_node_from_rnode(node->parent->l_left) == node | |
145 | && node->parent->l_right) { | |
146 | return bgp_node_from_rnode(node->parent->l_right); | |
147 | } | |
148 | node = bgp_node_from_rnode(node->parent); | |
149 | } | |
150 | return NULL; | |
151 | } | |
152 | ||
153 | void bgp_table_range_lookup(const struct bgp_table *table, struct prefix *p, | |
154 | uint8_t maxlen, struct list *matches) | |
155 | { | |
156 | struct bgp_node *node = bgp_node_from_rnode(table->route_table->top); | |
157 | struct bgp_node *matched = NULL; | |
158 | ||
1dacdd8b MR |
159 | while (node && node->p.prefixlen <= p->prefixlen |
160 | && prefix_match(&node->p, p)) { | |
6f94b685 DS |
161 | if (bgp_node_has_bgp_path_info_data(node) |
162 | && node->p.prefixlen == p->prefixlen) { | |
1dacdd8b MR |
163 | matched = node; |
164 | break; | |
165 | } | |
166 | node = bgp_node_from_rnode(node->link[prefix_bit( | |
167 | &p->u.prefix, node->p.prefixlen)]); | |
168 | } | |
169 | ||
9f134cdc A |
170 | if (node == NULL) |
171 | return; | |
172 | ||
1dacdd8b MR |
173 | if ((matched == NULL && node->p.prefixlen > maxlen) || !node->parent) |
174 | return; | |
175 | else if (matched == NULL) | |
176 | matched = node = bgp_node_from_rnode(node->parent); | |
177 | ||
6f94b685 | 178 | if (bgp_node_has_bgp_path_info_data(matched)) { |
1dacdd8b MR |
179 | bgp_lock_node(matched); |
180 | listnode_add(matches, matched); | |
181 | } | |
182 | ||
183 | while ((node = bgp_route_next_until_maxlen(node, matched, maxlen))) { | |
184 | if (prefix_match(p, &node->p)) { | |
6f94b685 | 185 | if (bgp_node_has_bgp_path_info_data(node)) { |
1dacdd8b MR |
186 | bgp_lock_node(node); |
187 | listnode_add(matches, node); | |
188 | } | |
189 | } | |
190 | } | |
191 | } |