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