2 * Copyright (C) 1998, 2001 Kunihiro Ishiguro
4 * This file is part of GNU Zebra.
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
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.
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
25 #include "sockunion.h"
30 #include "bgpd/bgpd.h"
31 #include "bgpd/bgp_table.h"
32 #include "bgp_addpath.h"
34 void bgp_table_lock(struct bgp_table
*rt
)
39 void bgp_table_unlock(struct bgp_table
*rt
)
48 route_table_finish(rt
->route_table
);
49 rt
->route_table
= NULL
;
51 XFREE(MTYPE_BGP_TABLE
, rt
);
54 void bgp_table_finish(struct bgp_table
**rt
)
57 bgp_table_unlock(*rt
);
65 static struct route_node
*bgp_node_create(route_table_delegate_t
*delegate
,
66 struct route_table
*table
)
68 struct bgp_node
*node
;
69 node
= XCALLOC(MTYPE_BGP_NODE
, sizeof(struct bgp_node
));
71 RB_INIT(bgp_adj_out_rb
, &node
->adj_out
);
72 return bgp_node_to_rnode(node
);
78 static void bgp_node_destroy(route_table_delegate_t
*delegate
,
79 struct route_table
*table
, struct route_node
*node
)
81 struct bgp_node
*bgp_node
;
83 bgp_node
= bgp_node_from_rnode(node
);
87 bgp_addpath_free_node_data(&rt
->bgp
->tx_addpath
,
88 &bgp_node
->tx_addpath
,
92 XFREE(MTYPE_BGP_NODE
, bgp_node
);
96 * Function vector to customize the behavior of the route table
97 * library for BGP route tables.
99 route_table_delegate_t bgp_table_delegate
= {.create_node
= bgp_node_create
,
100 .destroy_node
= bgp_node_destroy
};
105 struct bgp_table
*bgp_table_init(struct bgp
*bgp
, afi_t afi
, safi_t safi
)
107 struct bgp_table
*rt
;
109 rt
= XCALLOC(MTYPE_BGP_TABLE
, sizeof(struct bgp_table
));
111 rt
->route_table
= route_table_init_with_delegate(&bgp_table_delegate
);
114 * Set up back pointer to bgp_table.
116 route_table_set_info(rt
->route_table
, rt
);
119 * pointer to bgp instance allows working back from bgp_path_info to bgp
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
)
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
);
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
);
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
);
148 node
= bgp_node_from_rnode(node
->parent
);
153 void bgp_table_range_lookup(const struct bgp_table
*table
, struct prefix
*p
,
154 uint8_t maxlen
, struct list
*matches
)
156 struct bgp_node
*node
= bgp_node_from_rnode(table
->route_table
->top
);
157 struct bgp_node
*matched
= NULL
;
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
) {
166 node
= bgp_node_from_rnode(node
->link
[prefix_bit(
167 &p
->u
.prefix
, node
->p
.prefixlen
)]);
173 if ((matched
== NULL
&& node
->p
.prefixlen
> maxlen
) || !node
->parent
)
175 else if (matched
== NULL
)
176 matched
= node
= bgp_node_from_rnode(node
->parent
);
178 if (bgp_node_has_bgp_path_info_data(matched
)) {
179 bgp_lock_node(matched
);
180 listnode_add(matches
, matched
);
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
)) {
187 listnode_add(matches
, node
);