tests/test-stp.c

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