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 #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         if (node == NULL)
 160                 return;
 161
 162         while (node->p.prefixlen <= p->prefixlen && prefix_match(&node->p, p)) {
 163                 if (bgp_node_has_bgp_path_info_data(node)
 164                     && node->p.prefixlen == p->prefixlen) {
 165                         matched = node;
 166                         break;
 167                 }
 168                 node = bgp_node_from_rnode(node->link[prefix_bit(
 169                         &p->u.prefix, node->p.prefixlen)]);
 170         }
 171
 172         if (matched == NULL && node->p.prefixlen <= maxlen
 173             && prefix_match(p, &node->p) && node->parent == NULL)
 174                 matched = node;
 175         else if ((matched == NULL && node->p.prefixlen > maxlen) || !node->parent)
 176                 return;
 177         else if (matched == NULL)
 178                 matched = node = bgp_node_from_rnode(node->parent);
 179
 180         if (bgp_node_has_bgp_path_info_data(matched)) {
 181                 bgp_lock_node(matched);
 182                 listnode_add(matches, matched);
 183         }
 184
 185         while ((node = bgp_route_next_until_maxlen(node, matched, maxlen))) {
 186                 if (prefix_match(p, &node->p)) {
 187                         if (bgp_node_has_bgp_path_info_data(node)) {
 188                                 bgp_lock_node(node);
 189                                 listnode_add(matches, node);
 190                         }
 191                 }
 192         }
 193 }