]> git.proxmox.com Git - mirror_frr.git/blob - bgpd/bgp_table.c
*: Fixup to use proper list_cmp functions
[mirror_frr.git] / bgpd / bgp_table.c
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
33 void bgp_table_lock(struct bgp_table *rt)
34 {
35 rt->lock++;
36 }
37
38 void bgp_table_unlock(struct bgp_table *rt)
39 {
40 assert(rt->lock > 0);
41 rt->lock--;
42
43 if (rt->lock != 0) {
44 return;
45 }
46
47 route_table_finish(rt->route_table);
48 rt->route_table = NULL;
49
50 XFREE(MTYPE_BGP_TABLE, rt);
51 }
52
53 void bgp_table_finish(struct bgp_table **rt)
54 {
55 if (*rt != NULL) {
56 bgp_table_unlock(*rt);
57 *rt = NULL;
58 }
59 }
60
61 /*
62 * bgp_node_create
63 */
64 static struct route_node *bgp_node_create(route_table_delegate_t *delegate,
65 struct route_table *table)
66 {
67 struct bgp_node *node;
68 node = XCALLOC(MTYPE_BGP_NODE, sizeof(struct bgp_node));
69 return bgp_node_to_rnode(node);
70 }
71
72 /*
73 * bgp_node_destroy
74 */
75 static void bgp_node_destroy(route_table_delegate_t *delegate,
76 struct route_table *table, struct route_node *node)
77 {
78 struct bgp_node *bgp_node;
79 bgp_node = bgp_node_from_rnode(node);
80 XFREE(MTYPE_BGP_NODE, bgp_node);
81 }
82
83 /*
84 * Function vector to customize the behavior of the route table
85 * library for BGP route tables.
86 */
87 route_table_delegate_t bgp_table_delegate = {.create_node = bgp_node_create,
88 .destroy_node = bgp_node_destroy};
89
90 /*
91 * bgp_table_init
92 */
93 struct bgp_table *bgp_table_init(struct bgp *bgp, afi_t afi, safi_t safi)
94 {
95 struct bgp_table *rt;
96
97 rt = XCALLOC(MTYPE_BGP_TABLE, sizeof(struct bgp_table));
98
99 rt->route_table = route_table_init_with_delegate(&bgp_table_delegate);
100
101 /*
102 * Set up back pointer to bgp_table.
103 */
104 route_table_set_info(rt->route_table, rt);
105
106 /*
107 * pointer to bgp instance allows working back from bgp_path_info to bgp
108 */
109 rt->bgp = bgp;
110
111 bgp_table_lock(rt);
112 rt->afi = afi;
113 rt->safi = safi;
114
115 return rt;
116 }
117
118 static struct bgp_node *
119 bgp_route_next_until_maxlen(struct bgp_node *node, const struct bgp_node *limit,
120 const uint8_t maxlen)
121 {
122 if (node->l_left && node->p.prefixlen < maxlen
123 && node->l_left->p.prefixlen <= maxlen) {
124 return bgp_node_from_rnode(node->l_left);
125 }
126 if (node->l_right && node->p.prefixlen < maxlen
127 && node->l_right->p.prefixlen <= maxlen) {
128 return bgp_node_from_rnode(node->l_right);
129 }
130
131 while (node->parent && node != limit) {
132 if (bgp_node_from_rnode(node->parent->l_left) == node
133 && node->parent->l_right) {
134 return bgp_node_from_rnode(node->parent->l_right);
135 }
136 node = bgp_node_from_rnode(node->parent);
137 }
138 return NULL;
139 }
140
141 void bgp_table_range_lookup(const struct bgp_table *table, struct prefix *p,
142 uint8_t maxlen, struct list *matches)
143 {
144 struct bgp_node *node = bgp_node_from_rnode(table->route_table->top);
145 struct bgp_node *matched = NULL;
146
147 while (node && node->p.prefixlen <= p->prefixlen
148 && prefix_match(&node->p, p)) {
149 if (node->info && node->p.prefixlen == p->prefixlen) {
150 matched = node;
151 break;
152 }
153 node = bgp_node_from_rnode(node->link[prefix_bit(
154 &p->u.prefix, node->p.prefixlen)]);
155 }
156
157 if (node == NULL)
158 return;
159
160 if ((matched == NULL && node->p.prefixlen > maxlen) || !node->parent)
161 return;
162 else if (matched == NULL)
163 matched = node = bgp_node_from_rnode(node->parent);
164
165 if (matched->info) {
166 bgp_lock_node(matched);
167 listnode_add(matches, matched);
168 }
169
170 while ((node = bgp_route_next_until_maxlen(node, matched, maxlen))) {
171 if (prefix_match(p, &node->p)) {
172 if (node->info) {
173 bgp_lock_node(node);
174 listnode_add(matches, node);
175 }
176 }
177 }
178 }