]>
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)); | |
70 | return bgp_node_to_rnode(node); | |
718e3744 | 71 | } |
72 | ||
67174041 AS |
73 | /* |
74 | * bgp_node_destroy | |
75 | */ | |
d62a17ae | 76 | static void bgp_node_destroy(route_table_delegate_t *delegate, |
77 | struct route_table *table, struct route_node *node) | |
718e3744 | 78 | { |
d62a17ae | 79 | struct bgp_node *bgp_node; |
dcc68b5e | 80 | struct bgp_table *rt; |
d62a17ae | 81 | bgp_node = bgp_node_from_rnode(node); |
dcc68b5e MS |
82 | rt = table->info; |
83 | ||
84 | if (rt->bgp) { | |
85 | bgp_addpath_free_node_data(&rt->bgp->tx_addpath, | |
86 | &bgp_node->tx_addpath, | |
87 | rt->afi, rt->safi); | |
88 | } | |
89 | ||
d62a17ae | 90 | XFREE(MTYPE_BGP_NODE, bgp_node); |
718e3744 | 91 | } |
92 | ||
67174041 AS |
93 | /* |
94 | * Function vector to customize the behavior of the route table | |
95 | * library for BGP route tables. | |
96 | */ | |
d62a17ae | 97 | route_table_delegate_t bgp_table_delegate = {.create_node = bgp_node_create, |
98 | .destroy_node = bgp_node_destroy}; | |
718e3744 | 99 | |
67174041 AS |
100 | /* |
101 | * bgp_table_init | |
102 | */ | |
960035b2 | 103 | struct bgp_table *bgp_table_init(struct bgp *bgp, afi_t afi, safi_t safi) |
718e3744 | 104 | { |
d62a17ae | 105 | struct bgp_table *rt; |
718e3744 | 106 | |
d62a17ae | 107 | rt = XCALLOC(MTYPE_BGP_TABLE, sizeof(struct bgp_table)); |
718e3744 | 108 | |
d62a17ae | 109 | rt->route_table = route_table_init_with_delegate(&bgp_table_delegate); |
718e3744 | 110 | |
d62a17ae | 111 | /* |
112 | * Set up back pointer to bgp_table. | |
113 | */ | |
6ca30e9e | 114 | route_table_set_info(rt->route_table, rt); |
718e3744 | 115 | |
960035b2 | 116 | /* |
9b6d8fcf | 117 | * pointer to bgp instance allows working back from bgp_path_info to bgp |
960035b2 PZ |
118 | */ |
119 | rt->bgp = bgp; | |
120 | ||
d62a17ae | 121 | bgp_table_lock(rt); |
122 | rt->afi = afi; | |
123 | rt->safi = safi; | |
cbdfbaa5 | 124 | |
d62a17ae | 125 | return rt; |
cbdfbaa5 | 126 | } |
1dacdd8b MR |
127 | |
128 | static struct bgp_node * | |
129 | bgp_route_next_until_maxlen(struct bgp_node *node, const struct bgp_node *limit, | |
130 | const uint8_t maxlen) | |
131 | { | |
132 | if (node->l_left && node->p.prefixlen < maxlen | |
133 | && node->l_left->p.prefixlen <= maxlen) { | |
134 | return bgp_node_from_rnode(node->l_left); | |
135 | } | |
136 | if (node->l_right && node->p.prefixlen < maxlen | |
137 | && node->l_right->p.prefixlen <= maxlen) { | |
138 | return bgp_node_from_rnode(node->l_right); | |
139 | } | |
140 | ||
141 | while (node->parent && node != limit) { | |
142 | if (bgp_node_from_rnode(node->parent->l_left) == node | |
143 | && node->parent->l_right) { | |
144 | return bgp_node_from_rnode(node->parent->l_right); | |
145 | } | |
146 | node = bgp_node_from_rnode(node->parent); | |
147 | } | |
148 | return NULL; | |
149 | } | |
150 | ||
151 | void bgp_table_range_lookup(const struct bgp_table *table, struct prefix *p, | |
152 | uint8_t maxlen, struct list *matches) | |
153 | { | |
154 | struct bgp_node *node = bgp_node_from_rnode(table->route_table->top); | |
155 | struct bgp_node *matched = NULL; | |
156 | ||
1dacdd8b MR |
157 | while (node && node->p.prefixlen <= p->prefixlen |
158 | && prefix_match(&node->p, p)) { | |
159 | if (node->info && node->p.prefixlen == p->prefixlen) { | |
160 | matched = node; | |
161 | break; | |
162 | } | |
163 | node = bgp_node_from_rnode(node->link[prefix_bit( | |
164 | &p->u.prefix, node->p.prefixlen)]); | |
165 | } | |
166 | ||
9f134cdc A |
167 | if (node == NULL) |
168 | return; | |
169 | ||
1dacdd8b MR |
170 | if ((matched == NULL && node->p.prefixlen > maxlen) || !node->parent) |
171 | return; | |
172 | else if (matched == NULL) | |
173 | matched = node = bgp_node_from_rnode(node->parent); | |
174 | ||
175 | if (matched->info) { | |
176 | bgp_lock_node(matched); | |
177 | listnode_add(matches, matched); | |
178 | } | |
179 | ||
180 | while ((node = bgp_route_next_until_maxlen(node, matched, maxlen))) { | |
181 | if (prefix_match(p, &node->p)) { | |
182 | if (node->info) { | |
183 | bgp_lock_node(node); | |
184 | listnode_add(matches, node); | |
185 | } | |
186 | } | |
187 | } | |
188 | } |