tests/test-rstp.c

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