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