tests/test-stp.c

   1 /*
   2  * Copyright (c) 2008, 2009, 2010, 2012, 2013, 2014 Nicira, Inc.
   3  *
   4  * Licensed under the Apache License, Version 2.0 (the "License");
   5  * you may not use this file except in compliance with the License.
   6  * You may obtain a copy of the License at:
   7  *
   8  *     http://www.apache.org/licenses/LICENSE-2.0
   9  *
  10  * Unless required by applicable law or agreed to in writing, software
  11  * distributed under the License is distributed on an "AS IS" BASIS,
  12  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  13  * See the License for the specific language governing permissions and
  14  * limitations under the License.
  15  */
  16
  17 #include <config.h>
  18 #undef NDEBUG
  19 #include "stp.h"
  20 #include <assert.h>
  21 #include <ctype.h>
  22 #include <errno.h>
  23 #include <inttypes.h>
  24 #include <stdarg.h>
  25 #include <stdlib.h>
  26 #include "ofpbuf.h"
  27 #include "ovstest.h"
  28 #include "packets.h"
  29 #include "vlog.h"
  30
  31 struct bpdu {
  32     int port_no;
  33     void *data;
  34     size_t size;
  35 };
  36
  37 struct bridge {
  38     struct test_case *tc;
  39     int id;
  40     bool reached;
  41
  42     struct stp *stp;
  43
  44     struct lan *ports[STP_MAX_PORTS];
  45     int n_ports;
  46
  47 #define RXQ_SIZE 16
  48     struct bpdu rxq[RXQ_SIZE];
  49     int rxq_head, rxq_tail;
  50 };
  51
  52 struct lan_conn {
  53     struct bridge *bridge;
  54     int port_no;
  55 };
  56
  57 struct lan {
  58     struct test_case *tc;
  59     const char *name;
  60     bool reached;
  61     struct lan_conn conns[16];
  62     int n_conns;
  63 };
  64
  65 struct test_case {
  66     struct bridge *bridges[16];
  67     int n_bridges;
  68     struct lan *lans[26];
  69     int n_lans;
  70 };
  71
  72 static const char *file_name;
  73 static int line_number;
  74 static char line[128];
  75 static char *pos, *token;
  76 static int n_warnings;
  77
  78 static struct test_case *
  79 new_test_case(void)
  80 {
  81     struct test_case *tc = xmalloc(sizeof *tc);
  82     tc->n_bridges = 0;
  83     tc->n_lans = 0;
  84     return tc;
  85 }
  86
  87 static void
  88 send_bpdu(struct ofpbuf *pkt, int port_no, void *b_)
  89 {
  90     struct bridge *b = b_;
  91     struct lan *lan;
  92
  93     assert(port_no < b->n_ports);
  94     lan = b->ports[port_no];
  95     if (lan) {
  96         const void *data = ofpbuf_l3(pkt);
  97         size_t size = (char *) ofpbuf_tail(pkt) - (char *) data;
  98         int i;
  99
 100         for (i = 0; i < lan->n_conns; i++) {
 101             struct lan_conn *conn = &lan->conns[i];
 102             if (conn->bridge != b || conn->port_no != port_no) {
 103                 struct bridge *dst = conn->bridge;
 104                 struct bpdu *bpdu = &dst->rxq[dst->rxq_head++ % RXQ_SIZE];
 105                 assert(dst->rxq_head - dst->rxq_tail <= RXQ_SIZE);
 106                 bpdu->data = xmemdup(data, size);
 107                 bpdu->size = size;
 108                 bpdu->port_no = conn->port_no;
 109             }
 110         }
 111     }
 112     ofpbuf_delete(pkt);
 113 }
 114
 115 static struct bridge *
 116 new_bridge(struct test_case *tc, int id)
 117 {
 118     struct bridge *b = xmalloc(sizeof *b);
 119     char name[16];
 120     b->tc = tc;
 121     b->id = id;
 122     snprintf(name, sizeof name, "stp%x", id);
 123     b->stp = stp_create(name, id, send_bpdu, b);
 124     assert(tc->n_bridges < ARRAY_SIZE(tc->bridges));
 125     b->n_ports = 0;
 126     b->rxq_head = b->rxq_tail = 0;
 127     tc->bridges[tc->n_bridges++] = b;
 128     return b;
 129 }
 130
 131 static struct lan *
 132 new_lan(struct test_case *tc, const char *name)
 133 {
 134     struct lan *lan = xmalloc(sizeof *lan);
 135     lan->tc = tc;
 136     lan->name = xstrdup(name);
 137     lan->n_conns = 0;
 138     assert(tc->n_lans < ARRAY_SIZE(tc->lans));
 139     tc->lans[tc->n_lans++] = lan;
 140     return lan;
 141 }
 142
 143 static void
 144 reconnect_port(struct bridge *b, int port_no, struct lan *new_lan)
 145 {
 146     struct lan *old_lan;
 147     int j;
 148
 149     assert(port_no < b->n_ports);
 150     old_lan = b->ports[port_no];
 151     if (old_lan == new_lan) {
 152         return;
 153     }
 154
 155     /* Disconnect from old_lan. */
 156     if (old_lan) {
 157         for (j = 0; j < old_lan->n_conns; j++) {
 158             struct lan_conn *c = &old_lan->conns[j];
 159             if (c->bridge == b && c->port_no == port_no) {
 160                 memmove(c, c + 1, sizeof *c * (old_lan->n_conns - j - 1));
 161                 old_lan->n_conns--;
 162                 break;
 163             }
 164         }
 165     }
 166
 167     /* Connect to new_lan. */
 168     b->ports[port_no] = new_lan;
 169     if (new_lan) {
 170         int conn_no = new_lan->n_conns++;
 171         assert(conn_no < ARRAY_SIZE(new_lan->conns));
 172         new_lan->conns[conn_no].bridge = b;
 173         new_lan->conns[conn_no].port_no = port_no;
 174     }
 175 }
 176
 177 static void
 178 new_port(struct bridge *b, struct lan *lan, int path_cost)
 179 {
 180     int port_no = b->n_ports++;
 181     struct stp_port *p = stp_get_port(b->stp, port_no);
 182     assert(port_no < ARRAY_SIZE(b->ports));
 183     b->ports[port_no] = NULL;
 184     stp_port_set_path_cost(p, path_cost);
 185     stp_port_enable(p);
 186     reconnect_port(b, port_no, lan);
 187 }
 188
 189 static void
 190 dump(struct test_case *tc)
 191 {
 192     int i;
 193
 194     for (i = 0; i < tc->n_bridges; i++) {
 195         struct bridge *b = tc->bridges[i];
 196         struct stp *stp = b->stp;
 197         int j;
 198
 199         printf("%s:", stp_get_name(stp));
 200         if (stp_is_root_bridge(stp)) {
 201             printf(" root");
 202         }
 203         printf("\n");
 204         for (j = 0; j < b->n_ports; j++) {
 205             struct stp_port *p = stp_get_port(stp, j);
 206             enum stp_state state = stp_port_get_state(p);
 207
 208             printf("\tport %d", j);
 209             if (b->ports[j]) {
 210                 printf(" (lan %s)", b->ports[j]->name);
 211             } else {
 212                 printf(" (disconnected)");
 213             }
 214             printf(": %s", stp_state_name(state));
 215             if (p == stp_get_root_port(stp)) {
 216                 printf(" (root port, root_path_cost=%u)", stp_get_root_path_cost(stp));
 217             }
 218             printf("\n");
 219         }
 220     }
 221 }
 222
 223 static void dump_lan_tree(struct test_case *, struct lan *, int level);
 224
 225 static void
 226 dump_bridge_tree(struct test_case *tc, struct bridge *b, int level)
 227 {
 228     int i;
 229
 230     if (b->reached) {
 231         return;
 232     }
 233     b->reached = true;
 234     for (i = 0; i < level; i++) {
 235         printf("\t");
 236     }
 237     printf("%s\n", stp_get_name(b->stp));
 238     for (i = 0; i < b->n_ports; i++) {
 239         struct lan *lan = b->ports[i];
 240         struct stp_port *p = stp_get_port(b->stp, i);
 241         if (stp_port_get_state(p) == STP_FORWARDING && lan) {
 242             dump_lan_tree(tc, lan, level + 1);
 243         }
 244     }
 245 }
 246
 247 static void
 248 dump_lan_tree(struct test_case *tc, struct lan *lan, int level)
 249 {
 250     int i;
 251
 252     if (lan->reached) {
 253         return;
 254     }
 255     lan->reached = true;
 256     for (i = 0; i < level; i++) {
 257         printf("\t");
 258     }
 259     printf("%s\n", lan->name);
 260     for (i = 0; i < lan->n_conns; i++) {
 261         struct bridge *b = lan->conns[i].bridge;
 262         dump_bridge_tree(tc, b, level + 1);
 263     }
 264 }
 265
 266 static void
 267 tree(struct test_case *tc)
 268 {
 269     int i;
 270
 271     for (i = 0; i < tc->n_bridges; i++) {
 272         struct bridge *b = tc->bridges[i];
 273         b->reached = false;
 274     }
 275     for (i = 0; i < tc->n_lans; i++) {
 276         struct lan *lan = tc->lans[i];
 277         lan->reached = false;
 278     }
 279     for (i = 0; i < tc->n_bridges; i++) {
 280         struct bridge *b = tc->bridges[i];
 281         struct stp *stp = b->stp;
 282         if (stp_is_root_bridge(stp)) {
 283             dump_bridge_tree(tc, b, 0);
 284         }
 285     }
 286 }
 287
 288 static void
 289 simulate(struct test_case *tc, int granularity)
 290 {
 291     int time;
 292
 293     for (time = 0; time < 1000 * 180; time += granularity) {
 294         int round_trips;
 295         int i;
 296
 297         for (i = 0; i < tc->n_bridges; i++) {
 298             stp_tick(tc->bridges[i]->stp, granularity);
 299         }
 300         for (round_trips = 0; round_trips < granularity; round_trips++) {
 301             bool any = false;
 302             for (i = 0; i < tc->n_bridges; i++) {
 303                 struct bridge *b = tc->bridges[i];
 304                 for (; b->rxq_tail != b->rxq_head; b->rxq_tail++) {
 305                     struct bpdu *bpdu = &b->rxq[b->rxq_tail % RXQ_SIZE];
 306                     stp_received_bpdu(stp_get_port(b->stp, bpdu->port_no),
 307                                       bpdu->data, bpdu->size);
 308                     free(bpdu->data);
 309                     any = true;
 310                 }
 311             }
 312             if (!any) {
 313                 break;
 314             }
 315         }
 316     }
 317 }
 318
 319 NO_RETURN static void
 320 err(const char *message, ...)
 321     PRINTF_FORMAT(1, 2);
 322
 323 static void
 324 err(const char *message, ...)
 325 {
 326     va_list args;
 327
 328     fprintf(stderr, "%s:%d:%"PRIdPTR": ", file_name, line_number, pos - line);
 329     va_start(args, message);
 330     vfprintf(stderr, message, args);
 331     va_end(args);
 332     putc('\n', stderr);
 333
 334     exit(EXIT_FAILURE);
 335 }
 336
 337 static void
 338 warn(const char *message, ...)
 339     PRINTF_FORMAT(1, 2);
 340
 341 static void
 342 warn(const char *message, ...)
 343 {
 344     va_list args;
 345
 346     fprintf(stderr, "%s:%d: ", file_name, line_number);
 347     va_start(args, message);
 348     vfprintf(stderr, message, args);
 349     va_end(args);
 350     putc('\n', stderr);
 351
 352     n_warnings++;
 353 }
 354
 355 static bool
 356 get_token(void)
 357 {
 358     char *start;
 359
 360     while (isspace((unsigned char) *pos)) {
 361         pos++;
 362     }
 363     if (*pos == '\0') {
 364         free(token);
 365         token = NULL;
 366         return false;
 367     }
 368
 369     start = pos;
 370     if (isalpha((unsigned char) *pos)) {
 371         while (isalpha((unsigned char) *++pos)) {
 372             continue;
 373         }
 374     } else if (isdigit((unsigned char) *pos)) {
 375         if (*pos == '0' && (pos[1] == 'x' || pos[1] == 'X')) {
 376             pos += 2;
 377             while (isxdigit((unsigned char) *pos)) {
 378                 pos++;
 379             }
 380         } else {
 381             while (isdigit((unsigned char) *++pos)) {
 382                 continue;
 383             }
 384         }
 385     } else {
 386         pos++;
 387     }
 388
 389     free(token);
 390     token = xmemdup0(start, pos - start);
 391     return true;
 392 }
 393
 394 static bool
 395 get_int(int *intp)
 396 {
 397     char *save_pos = pos;
 398     if (token && isdigit((unsigned char) *token)) {
 399         *intp = strtol(token, NULL, 0);
 400         get_token();
 401         return true;
 402     } else {
 403         pos = save_pos;
 404         return false;
 405     }
 406 }
 407
 408 static bool
 409 match(const char *want)
 410 {
 411     if (token && !strcmp(want, token)) {
 412         get_token();
 413         return true;
 414     } else {
 415         return false;
 416     }
 417 }
 418
 419 static int
 420 must_get_int(void)
 421 {
 422     int x;
 423     if (!get_int(&x)) {
 424         err("expected integer");
 425     }
 426     return x;
 427 }
 428
 429 static void
 430 must_match(const char *want)
 431 {
 432     if (!match(want)) {
 433         err("expected \"%s\"", want);
 434     }
 435 }
 436
 437 static void
 438 test_stp_main(int argc, char *argv[])
 439 {
 440     struct test_case *tc;
 441     FILE *input_file;
 442     int i;
 443
 444     vlog_set_pattern(VLF_CONSOLE, "%c|%p|%m");
 445     vlog_set_levels(NULL, VLF_SYSLOG, VLL_OFF);
 446
 447     if (argc != 2) {
 448         ovs_fatal(0, "usage: test-stp INPUT.STP\n");
 449     }
 450     file_name = argv[1];
 451
 452     input_file = fopen(file_name, "r");
 453     if (!input_file) {
 454         ovs_fatal(errno, "error opening \"%s\"", file_name);
 455     }
 456
 457     tc = new_test_case();
 458     for (i = 0; i < 26; i++) {
 459         char name[2];
 460         name[0] = 'a' + i;
 461         name[1] = '\0';
 462         new_lan(tc, name);
 463     }
 464
 465     for (line_number = 1; fgets(line, sizeof line, input_file);
 466          line_number++)
 467     {
 468         char *newline, *hash;
 469
 470         newline = strchr(line, '\n');
 471         if (newline) {
 472             *newline = '\0';
 473         }
 474         hash = strchr(line, '#');
 475         if (hash) {
 476             *hash = '\0';
 477         }
 478
 479         pos = line;
 480         if (!get_token()) {
 481             continue;
 482         }
 483         if (match("bridge")) {
 484             struct bridge *bridge;
 485             int bridge_no, port_no;
 486
 487             bridge_no = must_get_int();
 488             if (bridge_no < tc->n_bridges) {
 489                 bridge = tc->bridges[bridge_no];
 490             } else if (bridge_no == tc->n_bridges) {
 491                 bridge = new_bridge(tc, must_get_int());
 492             } else {
 493                 err("bridges must be numbered consecutively from 0");
 494             }
 495             if (match("^")) {
 496                 stp_set_bridge_priority(bridge->stp, must_get_int());
 497             }
 498
 499             if (match("=")) {
 500                 for (port_no = 0; port_no < STP_MAX_PORTS; port_no++) {
 501                     struct stp_port *p = stp_get_port(bridge->stp, port_no);
 502                     if (!token || match("X")) {
 503                         stp_port_disable(p);
 504                     } else if (match("_")) {
 505                         /* Nothing to do. */
 506                     } else {
 507                         struct lan *lan;
 508                         int path_cost;
 509
 510                         if (!strcmp(token, "0")) {
 511                             lan = NULL;
 512                         } else if (strlen(token) == 1
 513                                 && islower((unsigned char)*token)) {
 514                             lan = tc->lans[*token - 'a'];
 515                         } else {
 516                             err("%s is not a valid LAN name "
 517                                 "(0 or a lowercase letter)", token);
 518                         }
 519                         get_token();
 520
 521                         path_cost = match(":") ? must_get_int() : 10;
 522                         if (port_no < bridge->n_ports) {
 523                             stp_port_set_path_cost(p, path_cost);
 524                             stp_port_enable(p);
 525                             reconnect_port(bridge, port_no, lan);
 526                         } else if (port_no == bridge->n_ports) {
 527                             new_port(bridge, lan, path_cost);
 528                         } else {
 529                             err("ports must be numbered consecutively");
 530                         }
 531                         if (match("^")) {
 532                             stp_port_set_priority(p, must_get_int());
 533                         }
 534                     }
 535                 }
 536             }
 537         } else if (match("run")) {
 538             simulate(tc, must_get_int());
 539         } else if (match("dump")) {
 540             dump(tc);
 541         } else if (match("tree")) {
 542             tree(tc);
 543         } else if (match("check")) {
 544             struct bridge *b;
 545             struct stp *stp;
 546             int bridge_no, port_no;
 547
 548             bridge_no = must_get_int();
 549             if (bridge_no >= tc->n_bridges) {
 550                 err("no bridge numbered %d", bridge_no);
 551             }
 552             b = tc->bridges[bridge_no];
 553             stp = b->stp;
 554
 555             must_match("=");
 556
 557             if (match("rootid")) {
 558                 uint64_t rootid;
 559                 must_match(":");
 560                 rootid = must_get_int();
 561                 if (match("^")) {
 562                     rootid |= (uint64_t) must_get_int() << 48;
 563                 } else {
 564                     rootid |= UINT64_C(0x8000) << 48;
 565                 }
 566                 if (stp_get_designated_root(stp) != rootid) {
 567                     warn("%s: root %"PRIx64", not %"PRIx64,
 568                          stp_get_name(stp), stp_get_designated_root(stp),
 569                          rootid);
 570                 }
 571             }
 572
 573             if (match("root")) {
 574                 if (stp_get_root_path_cost(stp)) {
 575                     warn("%s: root path cost of root is %u but should be 0",
 576                          stp_get_name(stp), stp_get_root_path_cost(stp));
 577                 }
 578                 if (!stp_is_root_bridge(stp)) {
 579                     warn("%s: root is %"PRIx64", not %"PRIx64,
 580                          stp_get_name(stp),
 581                          stp_get_designated_root(stp), stp_get_bridge_id(stp));
 582                 }
 583                 for (port_no = 0; port_no < b->n_ports; port_no++) {
 584                     struct stp_port *p = stp_get_port(stp, port_no);
 585                     enum stp_state state = stp_port_get_state(p);
 586                     if (!(state & (STP_DISABLED | STP_FORWARDING))) {
 587                         warn("%s: root port %d in state %s",
 588                              stp_get_name(b->stp), port_no,
 589                              stp_state_name(state));
 590                     }
 591                 }
 592             } else {
 593                 for (port_no = 0; port_no < STP_MAX_PORTS; port_no++) {
 594                     struct stp_port *p = stp_get_port(stp, port_no);
 595                     enum stp_state state;
 596                     if (token == NULL || match("D")) {
 597                         state = STP_DISABLED;
 598                     } else if (match("B")) {
 599                         state = STP_BLOCKING;
 600                     } else if (match("Li")) {
 601                         state = STP_LISTENING;
 602                     } else if (match("Le")) {
 603                         state = STP_LEARNING;
 604                     } else if (match("F")) {
 605                         state = STP_FORWARDING;
 606                     } else if (match("_")) {
 607                         continue;
 608                     } else {
 609                         err("unknown port state %s", token);
 610                     }
 611                     if (stp_port_get_state(p) != state) {
 612                         warn("%s port %d: state is %s but should be %s",
 613                              stp_get_name(stp), port_no,
 614                              stp_state_name(stp_port_get_state(p)),
 615                              stp_state_name(state));
 616                     }
 617                     if (state == STP_FORWARDING) {
 618                         struct stp_port *root_port = stp_get_root_port(stp);
 619                         if (match(":")) {
 620                             int root_path_cost = must_get_int();
 621                             if (p != root_port) {
 622                                 warn("%s: port %d is not the root port",
 623                                      stp_get_name(stp), port_no);
 624                                 if (!root_port) {
 625                                     warn("%s: (there is no root port)",
 626                                          stp_get_name(stp));
 627                                 } else {
 628                                     warn("%s: (port %d is the root port)",
 629                                          stp_get_name(stp),
 630                                          stp_port_no(root_port));
 631                                 }
 632                             } else if (root_path_cost
 633                                        != stp_get_root_path_cost(stp)) {
 634                                 warn("%s: root path cost is %u, should be %d",
 635                                      stp_get_name(stp),
 636                                      stp_get_root_path_cost(stp),
 637                                      root_path_cost);
 638                             }
 639                         } else if (p == root_port) {
 640                             warn("%s: port %d is the root port but "
 641                                  "not expected to be",
 642                                  stp_get_name(stp), port_no);
 643                         }
 644                     }
 645                 }
 646             }
 647             if (n_warnings) {
 648                 exit(EXIT_FAILURE);
 649             }
 650         }
 651         if (get_token()) {
 652             err("trailing garbage on line");
 653         }
 654     }
 655     free(token);
 656
 657     for (i = 0; i < tc->n_lans; i++) {
 658         struct lan *lan = tc->lans[i];
 659         free(CONST_CAST(char *, lan->name));
 660         free(lan);
 661     }
 662     for (i = 0; i < tc->n_bridges; i++) {
 663         struct bridge *bridge = tc->bridges[i];
 664         stp_unref(bridge->stp);
 665         free(bridge);
 666     }
 667     free(tc);
 668     fclose(input_file);
 669 }
 670
 671 OVSTEST_REGISTER("test-stp", test_stp_main);