/* BGP routing table
- Copyright (C) 1998, 2001 Kunihiro Ishiguro
-
-This file is part of GNU Zebra.
-
-GNU Zebra is free software; you can redistribute it and/or modify it
-under the terms of the GNU General Public License as published by the
-Free Software Foundation; either version 2, or (at your option) any
-later version.
-
-GNU Zebra is distributed in the hope that it will be useful, but
-WITHOUT ANY WARRANTY; without even the implied warranty of
-MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
-General Public License for more details.
-
-You should have received a copy of the GNU General Public License
-along with GNU Zebra; see the file COPYING. If not, write to the Free
-Software Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA
-02111-1307, USA. */
+ * Copyright (C) 1998, 2001 Kunihiro Ishiguro
+ *
+ * This file is part of GNU Zebra.
+ *
+ * GNU Zebra is free software; you can redistribute it and/or modify it
+ * under the terms of the GNU General Public License as published by the
+ * Free Software Foundation; either version 2, or (at your option) any
+ * later version.
+ *
+ * GNU Zebra is distributed in the hope that it will be useful, but
+ * WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
+ * General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License along
+ * with this program; see the file COPYING; if not, write to the Free Software
+ * Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA
+ */
#include <zebra.h>
#include "bgpd/bgpd.h"
#include "bgpd/bgp_table.h"
-void
-bgp_table_lock (struct bgp_table *rt)
+void bgp_table_lock(struct bgp_table *rt)
{
- rt->lock++;
+ rt->lock++;
}
-void
-bgp_table_unlock (struct bgp_table *rt)
+void bgp_table_unlock(struct bgp_table *rt)
{
- assert (rt->lock > 0);
- rt->lock--;
-
- if (rt->lock != 0)
- {
- return;
- }
+ assert(rt->lock > 0);
+ rt->lock--;
- route_table_finish (rt->route_table);
- rt->route_table = NULL;
+ if (rt->lock != 0) {
+ return;
+ }
- if (rt->owner)
- {
- peer_unlock (rt->owner);
- rt->owner = NULL;
- }
+ route_table_finish(rt->route_table);
+ rt->route_table = NULL;
- XFREE (MTYPE_BGP_TABLE, rt);
+ XFREE(MTYPE_BGP_TABLE, rt);
}
-void
-bgp_table_finish (struct bgp_table **rt)
+void bgp_table_finish(struct bgp_table **rt)
{
- if (*rt != NULL)
- {
- bgp_table_unlock(*rt);
- *rt = NULL;
- }
+ if (*rt != NULL) {
+ bgp_table_unlock(*rt);
+ *rt = NULL;
+ }
}
/*
* bgp_node_create
*/
-static struct route_node *
-bgp_node_create (route_table_delegate_t *delegate, struct route_table *table)
+static struct route_node *bgp_node_create(route_table_delegate_t *delegate,
+ struct route_table *table)
{
- struct bgp_node *node;
- node = XCALLOC (MTYPE_BGP_NODE, sizeof (struct bgp_node));
- return bgp_node_to_rnode (node);
+ struct bgp_node *node;
+ node = XCALLOC(MTYPE_BGP_NODE, sizeof(struct bgp_node));
+ return bgp_node_to_rnode(node);
}
/*
* bgp_node_destroy
*/
-static void
-bgp_node_destroy (route_table_delegate_t *delegate,
- struct route_table *table, struct route_node *node)
+static void bgp_node_destroy(route_table_delegate_t *delegate,
+ struct route_table *table, struct route_node *node)
{
- struct bgp_node *bgp_node;
- bgp_node = bgp_node_from_rnode (node);
- XFREE (MTYPE_BGP_NODE, bgp_node);
+ struct bgp_node *bgp_node;
+ bgp_node = bgp_node_from_rnode(node);
+ XFREE(MTYPE_BGP_NODE, bgp_node);
}
/*
* Function vector to customize the behavior of the route table
* library for BGP route tables.
*/
-route_table_delegate_t bgp_table_delegate = {
- .create_node = bgp_node_create,
- .destroy_node = bgp_node_destroy
-};
+route_table_delegate_t bgp_table_delegate = {.create_node = bgp_node_create,
+ .destroy_node = bgp_node_destroy};
/*
* bgp_table_init
*/
-struct bgp_table *
-bgp_table_init (afi_t afi, safi_t safi)
+struct bgp_table *bgp_table_init(struct bgp *bgp, afi_t afi, safi_t safi)
{
- struct bgp_table *rt;
+ struct bgp_table *rt;
+
+ rt = XCALLOC(MTYPE_BGP_TABLE, sizeof(struct bgp_table));
- rt = XCALLOC (MTYPE_BGP_TABLE, sizeof (struct bgp_table));
+ rt->route_table = route_table_init_with_delegate(&bgp_table_delegate);
- rt->route_table = route_table_init_with_delegate (&bgp_table_delegate);
+ /*
+ * Set up back pointer to bgp_table.
+ */
+ rt->route_table->info = rt;
- /*
- * Set up back pointer to bgp_table.
- */
- rt->route_table->info = rt;
+ /*
+ * pointer to bgp instance allows working back from bgp_info to bgp
+ */
+ rt->bgp = bgp;
- bgp_table_lock (rt);
- rt->afi = afi;
- rt->safi = safi;
+ bgp_table_lock(rt);
+ rt->afi = afi;
+ rt->safi = safi;
- return rt;
+ return rt;
+}
+
+static struct bgp_node *
+bgp_route_next_until_maxlen(struct bgp_node *node, const struct bgp_node *limit,
+ const uint8_t maxlen)
+{
+ if (node->l_left && node->p.prefixlen < maxlen
+ && node->l_left->p.prefixlen <= maxlen) {
+ return bgp_node_from_rnode(node->l_left);
+ }
+ if (node->l_right && node->p.prefixlen < maxlen
+ && node->l_right->p.prefixlen <= maxlen) {
+ return bgp_node_from_rnode(node->l_right);
+ }
+
+ while (node->parent && node != limit) {
+ if (bgp_node_from_rnode(node->parent->l_left) == node
+ && node->parent->l_right) {
+ return bgp_node_from_rnode(node->parent->l_right);
+ }
+ node = bgp_node_from_rnode(node->parent);
+ }
+ return NULL;
+}
+
+void bgp_table_range_lookup(const struct bgp_table *table, struct prefix *p,
+ uint8_t maxlen, struct list *matches)
+{
+ struct bgp_node *node = bgp_node_from_rnode(table->route_table->top);
+ struct bgp_node *matched = NULL;
+
+ while (node && node->p.prefixlen <= p->prefixlen
+ && prefix_match(&node->p, p)) {
+ if (node->info && node->p.prefixlen == p->prefixlen) {
+ matched = node;
+ break;
+ }
+ node = bgp_node_from_rnode(node->link[prefix_bit(
+ &p->u.prefix, node->p.prefixlen)]);
+ }
+
+ if (node == NULL)
+ return;
+
+ if ((matched == NULL && node->p.prefixlen > maxlen) || !node->parent)
+ return;
+ else if (matched == NULL)
+ matched = node = bgp_node_from_rnode(node->parent);
+
+ if (matched->info) {
+ bgp_lock_node(matched);
+ listnode_add(matches, matched);
+ }
+
+ while ((node = bgp_route_next_until_maxlen(node, matched, maxlen))) {
+ if (prefix_match(p, &node->p)) {
+ if (node->info) {
+ bgp_lock_node(node);
+ listnode_add(matches, node);
+ }
+ }
+ }
}
projects / mirror_frr.git / blobdiff