tests/bgpd/test_bgp_table.c

   1 /*
   2  * BGP Routing table range lookup test
   3  * Copyright (C) 2012 OSR.
   4  * Copyright (C) 2018 Marcel Röthke (marcel.roethke@haw-hamburg.de), for HAW
   5  * Hamburg
   6  *
   7  * This file is part of FRRouting
   8  *
   9  * Quagga is free software; you can redistribute it and/or modify it
  10  * under the terms of the GNU General Public License as published by the
  11  * Free Software Foundation; either version 2, or (at your option) any
  12  * later version.
  13  *
  14  * Quagga is distributed in the hope that it will be useful, but
  15  * WITHOUT ANY WARRANTY; without even the implied warranty of
  16  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  17  * General Public License for more details.
  18  *
  19  * You should have received a copy of the GNU General Public License along
  20  * with this program; see the file COPYING; if not, write to the Free Software
  21  * Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA
  22  */
  23
  24 #include <zebra.h>
  25
  26 #include "prefix.h"
  27 #include "table.h"
  28 #include "bgpd/bgp_table.h"
  29 #include "linklist.h"
  30
  31 /*
  32  * test_node_t
  33  *
  34  * Information that is kept for each node in the radix tree.
  35  */
  36 struct test_node_t {
  37
  38         /*
  39          * Human readable representation of the string. Allocated using
  40          * malloc()/dup().
  41          */
  42         char *prefix_str;
  43 };
  44
  45 /*
  46  * add_node
  47  *
  48  * Add the given prefix (passed in as a string) to the given table.
  49  */
  50 static void add_node(struct bgp_table *table, const char *prefix_str)
  51 {
  52         struct prefix_ipv4 p;
  53         struct test_node_t *node;
  54         struct bgp_node *rn;
  55
  56         assert(prefix_str);
  57
  58         if (str2prefix_ipv4(prefix_str, &p) <= 0)
  59                 assert(0);
  60
  61         rn = bgp_node_get(table, (struct prefix *)&p);
  62         if (rn->info) {
  63                 assert(0);
  64                 return;
  65         }
  66
  67         node = malloc(sizeof(struct test_node_t));
  68         assert(node);
  69         node->prefix_str = strdup(prefix_str);
  70         assert(node->prefix_str);
  71         rn->info = node;
  72 }
  73
  74 static void print_range_result(struct list *list)
  75 {
  76
  77         struct listnode *listnode;
  78         struct bgp_node *bnode;
  79
  80         for (ALL_LIST_ELEMENTS_RO(list, listnode, bnode)) {
  81                 char buf[PREFIX2STR_BUFFER];
  82
  83                 prefix2str(&bnode->p, buf, PREFIX2STR_BUFFER);
  84                 printf("%s\n", buf);
  85         }
  86 }
  87
  88 static void check_lookup_result(struct list *list, va_list arglist)
  89 {
  90         char *prefix_str;
  91         unsigned int prefix_count = 0;
  92
  93         printf("Searching results\n");
  94         while ((prefix_str = va_arg(arglist, char *))) {
  95                 struct listnode *listnode;
  96                 struct bgp_node *bnode;
  97                 struct prefix p;
  98                 bool found = false;
  99
 100                 prefix_count++;
 101                 printf("Searching for %s\n", prefix_str);
 102
 103                 if (str2prefix(prefix_str, &p) <= 0)
 104                         assert(0);
 105
 106                 for (ALL_LIST_ELEMENTS_RO(list, listnode, bnode)) {
 107                         if (prefix_same(&bnode->p, &p))
 108                                 found = true;
 109                 }
 110
 111                 assert(found);
 112         }
 113
 114         printf("Checking for unexpected result items\n");
 115         printf("Expecting %d found %d\n", prefix_count, listcount(list));
 116         assert(prefix_count == listcount(list));
 117 }
 118
 119 static void do_test(struct bgp_table *table, const char *prefix,
 120                     uint32_t maxlen, ...)
 121 {
 122         va_list arglist;
 123         struct list *list = list_new();
 124         struct prefix p;
 125
 126         list->del = (void (*)(void *))bgp_unlock_node;
 127
 128         va_start(arglist, maxlen);
 129         printf("\nDoing lookup for %s-%d\n", prefix, maxlen);
 130         if (str2prefix(prefix, &p) <= 0)
 131                 assert(0);
 132         bgp_table_range_lookup(table, &p, maxlen, list);
 133         print_range_result(list);
 134
 135         check_lookup_result(list, arglist);
 136
 137         list_delete_and_null(&list);
 138
 139         va_end(arglist);
 140
 141         printf("Checks successfull\n");
 142 }
 143
 144 /*
 145  * test_range_lookup
 146  */
 147 static void test_range_lookup(void)
 148 {
 149         struct bgp_table *table = bgp_table_init(NULL, AFI_IP, SAFI_UNICAST);
 150
 151         printf("Testing bgp_table_range_lookup\n");
 152
 153         printf("Setup bgp_table");
 154         const char *prefixes[] = {"1.16.0.0/16",   "1.16.128.0/18",
 155                                   "1.16.192.0/18", "1.16.64.0/19",
 156                                   "1.16.160.0/19", "1.16.32.0/20",
 157                                   "1.16.32.0/21",  "16.0.0.0/16"};
 158
 159         int num_prefixes = sizeof(prefixes) / sizeof(prefixes[0]);
 160
 161         for (int i = 0; i < num_prefixes; i++)
 162                 add_node(table, prefixes[i]);
 163
 164         do_test(table, "1.16.0.0/17", 20, "1.16.64.0/19", "1.16.32.0/20", NULL);
 165         do_test(table, "1.16.128.0/17", 20, "1.16.128.0/18", "1.16.192.0/18",
 166                 "1.16.160.0/19", NULL);
 167
 168         do_test(table, "1.16.128.0/17", 20, "1.16.128.0/18", "1.16.192.0/18",
 169                 "1.16.160.0/19", NULL);
 170
 171         do_test(table, "1.16.0.0/16", 18, "1.16.0.0/16", "1.16.128.0/18",
 172                 "1.16.192.0/18", NULL);
 173
 174         do_test(table, "1.16.0.0/16", 21, "1.16.0.0/16", "1.16.128.0/18",
 175                 "1.16.192.0/18", "1.16.64.0/19", "1.16.160.0/19",
 176                 "1.16.32.0/20", "1.16.32.0/21", NULL);
 177
 178         do_test(table, "1.17.0.0/16", 20, NULL);
 179
 180         do_test(table, "128.0.0.0/8", 16, NULL);
 181
 182         do_test(table, "16.0.0.0/8", 16, "16.0.0.0/16", NULL);
 183
 184         do_test(table, "0.0.0.0/3", 21, "1.16.0.0/16", "1.16.128.0/18",
 185                 "1.16.192.0/18", "1.16.64.0/19", "1.16.160.0/19",
 186                 "1.16.32.0/20", "1.16.32.0/21", "16.0.0.0/16", NULL);
 187 }
 188
 189 int main(void)
 190 {
 191         test_range_lookup();
 192 }