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 /* Satisfy link requirements from including bgpd.h */
  32 struct zebra_privs_t bgpd_privs = {0};
  33 /*
  34  * test_node_t
  35  *
  36  * Information that is kept for each node in the radix tree.
  37  */
  38 struct test_node_t {
  39
  40         /*
  41          * Human readable representation of the string. Allocated using
  42          * malloc()/dup().
  43          */
  44         char *prefix_str;
  45 };
  46
  47 /*
  48  * add_node
  49  *
  50  * Add the given prefix (passed in as a string) to the given table.
  51  */
  52 static void add_node(struct bgp_table *table, const char *prefix_str)
  53 {
  54         struct prefix_ipv4 p;
  55         struct test_node_t *node;
  56         struct bgp_node *rn;
  57
  58         assert(prefix_str);
  59
  60         if (str2prefix_ipv4(prefix_str, &p) <= 0)
  61                 assert(0);
  62
  63         rn = bgp_node_get(table, (struct prefix *)&p);
  64         if (rn->info) {
  65                 assert(0);
  66                 return;
  67         }
  68
  69         node = malloc(sizeof(struct test_node_t));
  70         assert(node);
  71         node->prefix_str = strdup(prefix_str);
  72         assert(node->prefix_str);
  73         rn->info = node;
  74 }
  75
  76 static void print_range_result(struct list *list)
  77 {
  78
  79         struct listnode *listnode;
  80         struct bgp_node *bnode;
  81
  82         for (ALL_LIST_ELEMENTS_RO(list, listnode, bnode)) {
  83                 char buf[PREFIX2STR_BUFFER];
  84
  85                 prefix2str(&bnode->p, buf, PREFIX2STR_BUFFER);
  86                 printf("%s\n", buf);
  87         }
  88 }
  89
  90 static void check_lookup_result(struct list *list, va_list arglist)
  91 {
  92         char *prefix_str;
  93         unsigned int prefix_count = 0;
  94
  95         printf("Searching results\n");
  96         while ((prefix_str = va_arg(arglist, char *))) {
  97                 struct listnode *listnode;
  98                 struct bgp_node *bnode;
  99                 struct prefix p;
 100                 bool found = false;
 101
 102                 prefix_count++;
 103                 printf("Searching for %s\n", prefix_str);
 104
 105                 if (str2prefix(prefix_str, &p) <= 0)
 106                         assert(0);
 107
 108                 for (ALL_LIST_ELEMENTS_RO(list, listnode, bnode)) {
 109                         if (prefix_same(&bnode->p, &p))
 110                                 found = true;
 111                 }
 112
 113                 assert(found);
 114         }
 115
 116         printf("Checking for unexpected result items\n");
 117         printf("Expecting %d found %d\n", prefix_count, listcount(list));
 118         assert(prefix_count == listcount(list));
 119 }
 120
 121 static void do_test(struct bgp_table *table, const char *prefix,
 122                     uint32_t maxlen, ...)
 123 {
 124         va_list arglist;
 125         struct list *list = list_new();
 126         struct prefix p;
 127
 128         list->del = (void (*)(void *))bgp_unlock_node;
 129
 130         va_start(arglist, maxlen);
 131         printf("\nDoing lookup for %s-%d\n", prefix, maxlen);
 132         if (str2prefix(prefix, &p) <= 0)
 133                 assert(0);
 134         bgp_table_range_lookup(table, &p, maxlen, list);
 135         print_range_result(list);
 136
 137         check_lookup_result(list, arglist);
 138
 139         list_delete(&list);
 140
 141         va_end(arglist);
 142
 143         printf("Checks successfull\n");
 144 }
 145
 146 /*
 147  * test_range_lookup
 148  */
 149 static void test_range_lookup(void)
 150 {
 151         struct bgp_table *table = bgp_table_init(NULL, AFI_IP, SAFI_UNICAST);
 152
 153         printf("Testing bgp_table_range_lookup\n");
 154
 155         printf("Setup bgp_table");
 156         const char *prefixes[] = {"1.16.0.0/16",   "1.16.128.0/18",
 157                                   "1.16.192.0/18", "1.16.64.0/19",
 158                                   "1.16.160.0/19", "1.16.32.0/20",
 159                                   "1.16.32.0/21",  "16.0.0.0/16"};
 160
 161         int num_prefixes = sizeof(prefixes) / sizeof(prefixes[0]);
 162
 163         for (int i = 0; i < num_prefixes; i++)
 164                 add_node(table, prefixes[i]);
 165
 166         do_test(table, "1.16.0.0/17", 20, "1.16.64.0/19", "1.16.32.0/20", NULL);
 167         do_test(table, "1.16.128.0/17", 20, "1.16.128.0/18", "1.16.192.0/18",
 168                 "1.16.160.0/19", NULL);
 169
 170         do_test(table, "1.16.128.0/17", 20, "1.16.128.0/18", "1.16.192.0/18",
 171                 "1.16.160.0/19", NULL);
 172
 173         do_test(table, "1.16.0.0/16", 18, "1.16.0.0/16", "1.16.128.0/18",
 174                 "1.16.192.0/18", NULL);
 175
 176         do_test(table, "1.16.0.0/16", 21, "1.16.0.0/16", "1.16.128.0/18",
 177                 "1.16.192.0/18", "1.16.64.0/19", "1.16.160.0/19",
 178                 "1.16.32.0/20", "1.16.32.0/21", NULL);
 179
 180         do_test(table, "1.17.0.0/16", 20, NULL);
 181
 182         do_test(table, "128.0.0.0/8", 16, NULL);
 183
 184         do_test(table, "16.0.0.0/8", 16, "16.0.0.0/16", NULL);
 185
 186         do_test(table, "0.0.0.0/3", 21, "1.16.0.0/16", "1.16.128.0/18",
 187                 "1.16.192.0/18", "1.16.64.0/19", "1.16.160.0/19",
 188                 "1.16.32.0/20", "1.16.32.0/21", "16.0.0.0/16", NULL);
 189 }
 190
 191 int main(void)
 192 {
 193         test_range_lookup();
 194 }