tests/test-stp.c

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