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 }