tests/test-rstp.c

   1 #include <config.h>
   2 #undef NDEBUG
   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 NO_RETURN static void
 339 err(const char *message, ...)
 340     PRINTF_FORMAT(1, 2);
 341
 342 static void
 343 err(const char *message, ...)
 344 {
 345     va_list args;
 346
 347     fprintf(stderr, "%s:%d:%"PRIdPTR": ", file_name, line_number, pos - line);
 348     va_start(args, message);
 349     vfprintf(stderr, message, args);
 350     va_end(args);
 351     putc('\n', stderr);
 352
 353     exit(EXIT_FAILURE);
 354 }
 355
 356 static void
 357 warn(const char *message, ...)
 358     PRINTF_FORMAT(1, 2);
 359
 360 static void
 361 warn(const char *message, ...)
 362 {
 363     va_list args;
 364
 365     fprintf(stderr, "%s:%d: ", file_name, line_number);
 366     va_start(args, message);
 367     vfprintf(stderr, message, args);
 368     va_end(args);
 369     putc('\n', stderr);
 370
 371     n_warnings++;
 372 }
 373
 374 static bool
 375 get_token(void)
 376 {
 377     char *start;
 378
 379     while (isspace((unsigned char) *pos)) {
 380         pos++;
 381     }
 382     if (*pos == '\0') {
 383         free(token);
 384         token = NULL;
 385         return false;
 386     }
 387
 388     start = pos;
 389     if (isalpha((unsigned char) *pos)) {
 390         while (isalpha((unsigned char) *++pos)) {
 391             continue;
 392         }
 393     } else if (isdigit((unsigned char) *pos)) {
 394         if (*pos == '0' && (pos[1] == 'x' || pos[1] == 'X')) {
 395             pos += 2;
 396             while (isxdigit((unsigned char) *pos)) {
 397                 pos++;
 398             }
 399         } else {
 400             while (isdigit((unsigned char) *++pos)) {
 401                 continue;
 402             }
 403         }
 404     } else {
 405         pos++;
 406     }
 407
 408     free(token);
 409     token = xmemdup0(start, pos - start);
 410     return true;
 411 }
 412
 413 static bool
 414 get_int(int *intp)
 415 {
 416     char *save_pos = pos;
 417
 418     if (token && isdigit((unsigned char) *token)) {
 419         *intp = strtol(token, NULL, 0);
 420         get_token();
 421         return true;
 422     } else {
 423         pos = save_pos;
 424         return false;
 425     }
 426 }
 427
 428 static bool
 429 match(const char *want)
 430 {
 431     if (token && !strcmp(want, token)) {
 432         get_token();
 433         return true;
 434     } else {
 435         return false;
 436     }
 437 }
 438
 439 static int
 440 must_get_int(void)
 441 {
 442     int x;
 443
 444     if (!get_int(&x)) {
 445         err("expected integer");
 446     }
 447     return x;
 448 }
 449
 450 static void
 451 must_match(const char *want)
 452 {
 453     if (!match(want)) {
 454         err("expected \"%s\"", want);
 455     }
 456 }
 457
 458 static void
 459 test_rstp_main(int argc, char *argv[])
 460 {
 461     struct test_case *tc;
 462     FILE *input_file;
 463     int i;
 464
 465     vlog_set_pattern(VLF_CONSOLE, "%c|%p|%m");
 466     vlog_set_levels(NULL, VLF_SYSLOG, VLL_OFF);
 467
 468     if (argc != 2) {
 469         ovs_fatal(0, "usage: test-rstp INPUT.RSTP\n");
 470     }
 471     file_name = argv[1];
 472
 473     input_file = fopen(file_name, "r");
 474     if (!input_file) {
 475         ovs_fatal(errno, "error opening \"%s\"", file_name);
 476     }
 477
 478     tc = new_test_case();
 479     for (i = 0; i < 26; i++) {
 480         char name[2];
 481
 482         name[0] = 'a' + i;
 483         name[1] = '\0';
 484         new_lan(tc, name);
 485     }
 486
 487     for (line_number = 1; fgets(line, sizeof line, input_file);
 488          line_number++)
 489     {
 490         char *newline, *hash;
 491
 492         newline = strchr(line, '\n');
 493         if (newline) {
 494             *newline = '\0';
 495         }
 496         hash = strchr(line, '#');
 497         if (hash) {
 498             *hash = '\0';
 499         }
 500
 501         pos = line;
 502         if (!get_token()) {
 503             continue;
 504         }
 505         if (match("bridge")) {
 506             struct bridge *bridge;
 507             int bridge_no, port_no;
 508
 509             bridge_no = must_get_int();
 510             if (bridge_no < tc->n_bridges) {
 511                 bridge = tc->bridges[bridge_no];
 512             } else if (bridge_no == tc->n_bridges) {
 513                 bridge = new_bridge(tc, must_get_int());
 514             } else {
 515                 err("bridges must be numbered consecutively from 0");
 516             }
 517             if (match("^")) {
 518                 rstp_set_bridge_priority(bridge->rstp, must_get_int());
 519             }
 520             if (match("=")) {
 521                 for (port_no = 1; port_no < MAX_PORTS; port_no++) {
 522                     struct rstp_port *p = rstp_get_port(bridge->rstp, port_no);
 523
 524                     if (!token || match("X")) {
 525                         /* Disable port. */
 526                         reinitialize_port(p);
 527                         rstp_port_set_state(p, RSTP_DISABLED);
 528                         rstp_port_set_mac_operational(p, false);
 529                     } else if (match("_")) {
 530                         /* Nothing to do. */
 531                     } else {
 532                         struct lan *lan;
 533                         uint32_t path_cost;
 534
 535                         if (!strcmp(token, "0")) {
 536                             lan = NULL;
 537                         } else if (strlen(token) == 1
 538                                 && islower((unsigned char)*token)) {
 539                             lan = tc->lans[*token - 'a'];
 540                         } else {
 541                             err("%s is not a valid LAN name "
 542                                 "(0 or a lowercase letter)", token);
 543                         }
 544                         get_token();
 545
 546                         path_cost = match(":") ? must_get_int() :
 547                                                  RSTP_DEFAULT_PORT_PATH_COST;
 548                         if (port_no < bridge->n_ports) {
 549                             /* Enable port. */
 550                             reinitialize_port(p);
 551                             rstp_port_set_path_cost(p, path_cost);
 552                             rstp_port_set_state(p, RSTP_DISCARDING);
 553                             rstp_port_set_mac_operational(p, true);
 554                             reconnect_port(bridge, port_no, lan);
 555                         } else if (port_no == bridge->n_ports) {
 556                             new_port(bridge, lan, path_cost);
 557                             bridge->n_active_ports++;
 558                         } else {
 559                             err("ports must be numbered consecutively");
 560                         }
 561                         if (match("^")) {
 562                             rstp_port_set_priority(p, must_get_int());
 563                         }
 564                     }
 565                 }
 566             }
 567         } else if (match("run")) {
 568             simulate(tc, must_get_int());
 569         } else if (match("dump")) {
 570             dump(tc);
 571         } else if (match("tree")) {
 572             tree(tc);
 573         } else if (match("check")) {
 574             struct bridge *b;
 575             struct rstp *rstp;
 576             int bridge_no, port_no;
 577             uint32_t cost_value;
 578
 579             bridge_no = must_get_int();
 580             if (bridge_no >= tc->n_bridges) {
 581                 err("no bridge numbered %d", bridge_no);
 582             }
 583             b = tc->bridges[bridge_no];
 584             rstp = b->rstp;
 585
 586             must_match("=");
 587
 588             if (match("rootid")) {
 589                 uint64_t rootid;
 590
 591                 must_match(":");
 592                 rootid = must_get_int();
 593                 if (match("^")) {
 594                     rootid |= (uint64_t) must_get_int() << 48;
 595                 } else {
 596                     rootid |= UINT64_C(0x8000) << 48;
 597                 }
 598                 if (rstp_get_designated_root(rstp) != rootid) {
 599                     warn("%s: root "RSTP_ID_FMT", not %"PRIx64,
 600                          rstp_get_name(rstp),
 601                          RSTP_ID_ARGS(rstp_get_designated_root(rstp)),
 602                          rootid);
 603                 }
 604             }
 605             cost_value = rstp_get_root_path_cost(rstp);
 606             if (match("root")) {
 607                 if (cost_value != 0) {
 608                     warn("%s: root path cost of root is %d instead of 0 \n",
 609                          rstp_get_name(rstp), cost_value);
 610                 }
 611                 if (!rstp_is_root_bridge(rstp)) {
 612                     warn("%s: root is "RSTP_ID_FMT", not "RSTP_ID_FMT"",
 613                          rstp_get_name(rstp),
 614                          RSTP_ID_ARGS(rstp_get_designated_root(rstp)),
 615                          RSTP_ID_ARGS(rstp_get_bridge_id(rstp)));
 616                 }
 617                 for (port_no = 1; port_no < b->n_active_ports; port_no++) {
 618                     struct rstp_port *p = rstp_get_port(rstp, port_no);
 619                     enum rstp_state state = rstp_port_get_state(p);
 620
 621                     if (state != RSTP_DISABLED && state != RSTP_FORWARDING) {
 622                         warn("%s: root port %d in state %s",
 623                              rstp_get_name(b->rstp), port_no,
 624                              rstp_state_name(state));
 625                     }
 626                 }
 627             } else {
 628                 for (port_no = 1; port_no < b->n_active_ports; port_no++) {
 629                     struct rstp_port *p = rstp_get_port(rstp, port_no);
 630                     enum rstp_state state;
 631
 632                     if (token == NULL || match("D")) {
 633                         state = RSTP_DISABLED;
 634                     } else if (match("Di")) {
 635                         state = RSTP_DISCARDING;
 636                     } else if (match("Le")) {
 637                         state = RSTP_LEARNING;
 638                     } else if (match("F")) {
 639                         state = RSTP_FORWARDING;
 640                     } else if (match("_")) {
 641                         continue;
 642                     } else {
 643                         err("unknown port state %s", token);
 644                     }
 645                     if (rstp_port_get_state(p) != state) {
 646                         warn("%s port %d: state is %s but should be %s",
 647                              rstp_get_name(rstp), port_no,
 648                              rstp_state_name(rstp_port_get_state(p)),
 649                              rstp_state_name(state));
 650                     }
 651                     if (state == RSTP_FORWARDING) {
 652                         struct rstp_port *root_port = rstp_get_root_port(rstp);
 653
 654                         if (match(":")) {
 655                             int root_path_cost = must_get_int();
 656
 657                             if (p != root_port) {
 658                                 warn("%s: port %d is not the root port",
 659                                      rstp_get_name(rstp), port_no);
 660                                 if (!root_port) {
 661                                     warn("%s: (there is no root port)",
 662                                          rstp_get_name(rstp));
 663                                 } else {
 664                                     warn("%s: (port %d is the root port)",
 665                                          rstp_get_name(rstp),
 666                                          rstp_port_get_number(root_port));
 667                                 }
 668                             } else if (cost_value != root_path_cost) {
 669                                 warn("%s: root path cost is %d, should be %d",
 670                                      rstp_get_name(rstp),
 671                                      cost_value,
 672                                      root_path_cost);
 673                             }
 674                         } else if (p == root_port) {
 675                             warn("%s: port %d is the root port but "
 676                                  "not expected to be",
 677                                  rstp_get_name(rstp), port_no);
 678                         }
 679                     }
 680                 }
 681             }
 682             if (n_warnings) {
 683                 printf("failing because of %d warnings\n", n_warnings);
 684                 exit(EXIT_FAILURE);
 685             }
 686         }
 687         if (get_token()) {
 688             printf("failing because of errors\n");
 689             err("trailing garbage on line");
 690         }
 691     }
 692     free(token);
 693
 694     for (i = 0; i < tc->n_lans; i++) {
 695         struct lan *lan = tc->lans[i];
 696
 697         free(CONST_CAST(char *, lan->name));
 698         free(lan);
 699     }
 700     for (i = 0; i < tc->n_bridges; i++) {
 701         struct bridge *bridge = tc->bridges[i];
 702         int j;
 703
 704         for (j = 1; j < MAX_PORTS; j++) {
 705             rstp_port_unref(rstp_get_port(bridge->rstp, j));
 706         }
 707         rstp_unref(bridge->rstp);
 708         free(bridge);
 709     }
 710     free(tc);
 711 }
 712
 713 OVSTEST_REGISTER("test-rstp", test_rstp_main);