]>
Commit | Line | Data |
---|---|---|
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 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 | */ | |
20 | ||
21 | #include <zebra.h> | |
22 | ||
23 | #include "prefix.h" | |
24 | #include "memory.h" | |
25 | #include "sockunion.h" | |
26 | #include "queue.h" | |
27 | #include "filter.h" | |
28 | #include "command.h" | |
29 | ||
30 | #include "bgpd/bgpd.h" | |
31 | #include "bgpd/bgp_table.h" | |
32 | #include "bgp_addpath.h" | |
33 | ||
34 | void bgp_table_lock(struct bgp_table *rt) | |
35 | { | |
36 | rt->lock++; | |
37 | } | |
38 | ||
39 | void bgp_table_unlock(struct bgp_table *rt) | |
40 | { | |
41 | assert(rt->lock > 0); | |
42 | rt->lock--; | |
43 | ||
44 | if (rt->lock != 0) { | |
45 | return; | |
46 | } | |
47 | ||
48 | route_table_finish(rt->route_table); | |
49 | rt->route_table = NULL; | |
50 | ||
51 | XFREE(MTYPE_BGP_TABLE, rt); | |
52 | } | |
53 | ||
54 | void bgp_table_finish(struct bgp_table **rt) | |
55 | { | |
56 | if (*rt != NULL) { | |
57 | bgp_table_unlock(*rt); | |
58 | *rt = NULL; | |
59 | } | |
60 | } | |
61 | ||
62 | /* | |
63 | * bgp_node_create | |
64 | */ | |
65 | static struct route_node *bgp_node_create(route_table_delegate_t *delegate, | |
66 | struct route_table *table) | |
67 | { | |
68 | struct bgp_node *node; | |
69 | node = XCALLOC(MTYPE_BGP_NODE, sizeof(struct bgp_node)); | |
70 | ||
71 | RB_INIT(bgp_adj_out_rb, &node->adj_out); | |
72 | return bgp_node_to_rnode(node); | |
73 | } | |
74 | ||
75 | /* | |
76 | * bgp_node_destroy | |
77 | */ | |
78 | static void bgp_node_destroy(route_table_delegate_t *delegate, | |
79 | struct route_table *table, struct route_node *node) | |
80 | { | |
81 | struct bgp_node *bgp_node; | |
82 | struct bgp_table *rt; | |
83 | bgp_node = bgp_node_from_rnode(node); | |
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 | ||
92 | XFREE(MTYPE_BGP_NODE, bgp_node); | |
93 | } | |
94 | ||
95 | /* | |
96 | * Function vector to customize the behavior of the route table | |
97 | * library for BGP route tables. | |
98 | */ | |
99 | route_table_delegate_t bgp_table_delegate = {.create_node = bgp_node_create, | |
100 | .destroy_node = bgp_node_destroy}; | |
101 | ||
102 | /* | |
103 | * bgp_table_init | |
104 | */ | |
105 | struct bgp_table *bgp_table_init(struct bgp *bgp, afi_t afi, safi_t safi) | |
106 | { | |
107 | struct bgp_table *rt; | |
108 | ||
109 | rt = XCALLOC(MTYPE_BGP_TABLE, sizeof(struct bgp_table)); | |
110 | ||
111 | rt->route_table = route_table_init_with_delegate(&bgp_table_delegate); | |
112 | ||
113 | /* | |
114 | * Set up back pointer to bgp_table. | |
115 | */ | |
116 | route_table_set_info(rt->route_table, rt); | |
117 | ||
118 | /* | |
119 | * pointer to bgp instance allows working back from bgp_path_info to bgp | |
120 | */ | |
121 | rt->bgp = bgp; | |
122 | ||
123 | bgp_table_lock(rt); | |
124 | rt->afi = afi; | |
125 | rt->safi = safi; | |
126 | ||
127 | return rt; | |
128 | } | |
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 | ||
159 | while (node && node->p.prefixlen <= p->prefixlen | |
160 | && prefix_match(&node->p, p)) { | |
161 | if (bgp_node_has_bgp_path_info_data(node) | |
162 | && node->p.prefixlen == p->prefixlen) { | |
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 | ||
170 | if (node == NULL) | |
171 | return; | |
172 | ||
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 | ||
178 | if (bgp_node_has_bgp_path_info_data(matched)) { | |
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)) { | |
185 | if (bgp_node_has_bgp_path_info_data(node)) { | |
186 | bgp_lock_node(node); | |
187 | listnode_add(matches, node); | |
188 | } | |
189 | } | |
190 | } | |
191 | } |