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 "dp-packet.h"
  13 #include "packets.h"
  14 #include "openvswitch/vlog.h"
  15
  16 #define MAX_PORTS 10
  17
  18 struct bpdu {
  19     int port_no;
  20     void *data;
  21     size_t size;
  22 };
  23
  24 struct bridge {
  25     struct test_case *tc;
  26     int id;
  27     bool reached;
  28
  29     struct rstp *rstp;
  30
  31     struct lan *ports[RSTP_MAX_PORTS];
  32     int n_ports;
  33     int n_active_ports;
  34
  35 #define RXQ_SIZE 16
  36     struct bpdu rxq[RXQ_SIZE];
  37     int rxq_head, rxq_tail;
  38 };
  39
  40 struct lan_conn {
  41     struct bridge *bridge;
  42     int port_no;
  43 };
  44
  45 struct lan {
  46     struct test_case *tc;
  47     const char *name;
  48     bool reached;
  49     struct lan_conn conns[16];
  50     int n_conns;
  51 };
  52
  53 struct test_case {
  54     struct bridge *bridges[16];
  55     int n_bridges;
  56     struct lan *lans[26];
  57     int n_lans;
  58 };
  59
  60 static const char *file_name;
  61 static int line_number;
  62 static char line[128];
  63 static char *pos, *token;
  64 static int n_warnings;
  65
  66 static struct test_case *
  67 new_test_case(void)
  68 {
  69     struct test_case *tc = xmalloc(sizeof *tc);
  70
  71     tc->n_bridges = 0;
  72     tc->n_lans = 0;
  73     return tc;
  74 }
  75
  76 /* This callback is called with rstp_mutex held. */
  77 static void
  78 send_bpdu(struct dp_packet *pkt, void *port_, void *b_)
  79     OVS_REQUIRES(rstp_mutex)
  80 {
  81     struct bridge *b = b_;
  82     struct lan *lan;
  83     const struct rstp_port *port = port_;
  84     uint16_t port_no = port->port_number;
  85
  86     assert(port_no < b->n_ports);
  87     lan = b->ports[port_no];
  88     if (lan) {
  89         const void *data = dp_packet_l3(pkt);
  90         size_t size = (char *) dp_packet_tail(pkt) - (char *) data;
  91         int i;
  92
  93         for (i = 0; i < lan->n_conns; i++) {
  94             struct lan_conn *conn = &lan->conns[i];
  95
  96             if (conn->bridge != b || conn->port_no != port_no) {
  97                 struct bridge *dst = conn->bridge;
  98                 struct bpdu *bpdu = &dst->rxq[dst->rxq_head++ % RXQ_SIZE];
  99
 100                 assert(dst->rxq_head - dst->rxq_tail <= RXQ_SIZE);
 101                 bpdu->data = xmemdup(data, size);
 102                 bpdu->size = size;
 103                 bpdu->port_no = conn->port_no;
 104             }
 105         }
 106     }
 107     dp_packet_delete(pkt);
 108 }
 109
 110 static struct bridge *
 111 new_bridge(struct test_case *tc, int id)
 112 {
 113     struct bridge *b = xmalloc(sizeof *b);
 114     char name[16];
 115     struct rstp_port *p;
 116     int i;
 117
 118     b->tc = tc;
 119     b->id = id;
 120     snprintf(name, sizeof name, "rstp%x", id);
 121     b->rstp = rstp_create(name, id, send_bpdu, b);
 122     for (i = 1; i < MAX_PORTS; i++) {
 123         p = rstp_add_port(b->rstp);
 124         rstp_port_set_aux(p, p);
 125         rstp_port_set_state(p, RSTP_DISABLED);
 126         rstp_port_set_mac_operational(p, true);
 127     }
 128
 129     assert(tc->n_bridges < ARRAY_SIZE(tc->bridges));
 130     b->n_ports = 1;
 131     b->n_active_ports = 1;
 132     b->rxq_head = b->rxq_tail = 0;
 133     tc->bridges[tc->n_bridges++] = b;
 134     return b;
 135 }
 136
 137 static struct lan *
 138 new_lan(struct test_case *tc, const char *name)
 139 {
 140     struct lan *lan = xmalloc(sizeof *lan);
 141     lan->tc = tc;
 142     lan->name = xstrdup(name);
 143     lan->n_conns = 0;
 144     assert(tc->n_lans < ARRAY_SIZE(tc->lans));
 145     tc->lans[tc->n_lans++] = lan;
 146     return lan;
 147 }
 148
 149 static void
 150 reconnect_port(struct bridge *b, int port_no, struct lan *new_lan)
 151 {
 152     struct lan *old_lan;
 153     int j;
 154
 155     assert(port_no < b->n_ports);
 156     old_lan = b->ports[port_no];
 157     if (old_lan == new_lan) {
 158         return;
 159     }
 160
 161     /* Disconnect from old_lan. */
 162     if (old_lan) {
 163         for (j = 0; j < old_lan->n_conns; j++) {
 164             struct lan_conn *c = &old_lan->conns[j];
 165
 166             if (c->bridge == b && c->port_no == port_no) {
 167                 memmove(c, c + 1, sizeof *c * (old_lan->n_conns - j - 1));
 168                 old_lan->n_conns--;
 169                 break;
 170             }
 171         }
 172     }
 173
 174     /* Connect to new_lan. */
 175     b->ports[port_no] = new_lan;
 176     if (new_lan) {
 177         int conn_no = new_lan->n_conns++;
 178
 179         assert(conn_no < ARRAY_SIZE(new_lan->conns));
 180         new_lan->conns[conn_no].bridge = b;
 181         new_lan->conns[conn_no].port_no = port_no;
 182     }
 183 }
 184
 185 static void
 186 new_port(struct bridge *b, struct lan *lan, uint32_t path_cost)
 187 {
 188     int port_no = b->n_ports++;
 189     struct rstp_port *p = rstp_get_port(b->rstp, port_no);
 190
 191     assert(port_no < ARRAY_SIZE(b->ports));
 192     b->ports[port_no] = NULL;
 193     /* Enable port. */
 194     reinitialize_port(p);
 195     rstp_port_set_path_cost(p, path_cost);
 196     rstp_port_set_state(p, RSTP_DISCARDING);
 197     rstp_port_set_mac_operational(p, true);
 198     reconnect_port(b, port_no, lan);
 199 }
 200
 201 static void
 202 dump(struct test_case *tc)
 203 {
 204     int i;
 205
 206     for (i = 0; i < tc->n_bridges; i++) {
 207         struct bridge *b = tc->bridges[i];
 208         struct rstp *rstp = b->rstp;
 209         int j;
 210
 211         printf("%s:", rstp_get_name(rstp));
 212         if (rstp_is_root_bridge(rstp)) {
 213             printf(" root");
 214         }
 215         printf("\n");
 216         for (j = 0; j < b->n_ports; j++) {
 217             struct rstp_port *p = rstp_get_port(rstp, j);
 218             enum rstp_state state = rstp_port_get_state(p);
 219
 220             printf("\tport %d", j);
 221             if (b->ports[j]) {
 222                 printf(" (lan %s)", b->ports[j]->name);
 223             } else {
 224                 printf(" (disconnected)");
 225             }
 226             printf(": %s", rstp_state_name(state));
 227             if (p == rstp_get_root_port(rstp)) {
 228                 printf(" (root port, root_path_cost=%u)",
 229                        rstp_get_root_path_cost(rstp));
 230             }
 231             printf("\n");
 232         }
 233     }
 234 }
 235
 236 static void dump_lan_tree(struct test_case *, struct lan *, int level);
 237
 238 static void
 239 dump_bridge_tree(struct test_case *tc, struct bridge *b, int level)
 240 {
 241     int i;
 242
 243     if (b->reached) {
 244         return;
 245     }
 246     b->reached = true;
 247     for (i = 0; i < level; i++) {
 248         printf("\t");
 249     }
 250     printf("%s\n", rstp_get_name(b->rstp));
 251     for (i = 0; i < b->n_ports; i++) {
 252         struct lan *lan = b->ports[i];
 253         struct rstp_port *p = rstp_get_port(b->rstp, i);
 254
 255         if (rstp_port_get_state(p) == RSTP_FORWARDING && lan) {
 256             dump_lan_tree(tc, lan, level + 1);
 257         }
 258     }
 259 }
 260
 261 static void
 262 dump_lan_tree(struct test_case *tc, struct lan *lan, int level)
 263 {
 264     int i;
 265
 266     if (lan->reached) {
 267         return;
 268     }
 269     lan->reached = true;
 270     for (i = 0; i < level; i++) {
 271         printf("\t");
 272     }
 273     printf("%s\n", lan->name);
 274     for (i = 0; i < lan->n_conns; i++) {
 275         struct bridge *b = lan->conns[i].bridge;
 276
 277         dump_bridge_tree(tc, b, level + 1);
 278     }
 279 }
 280
 281 static void
 282 tree(struct test_case *tc)
 283 {
 284     int i;
 285
 286     for (i = 0; i < tc->n_bridges; i++) {
 287         struct bridge *b = tc->bridges[i];
 288
 289         b->reached = false;
 290     }
 291     for (i = 0; i < tc->n_lans; i++) {
 292         struct lan *lan = tc->lans[i];
 293
 294         lan->reached = false;
 295     }
 296     for (i = 0; i < tc->n_bridges; i++) {
 297         struct bridge *b = tc->bridges[i];
 298         struct rstp *rstp = b->rstp;
 299
 300         if (rstp_is_root_bridge(rstp)) {
 301             dump_bridge_tree(tc, b, 0);
 302         }
 303     }
 304 }
 305
 306 static void
 307 simulate(struct test_case *tc, int granularity)
 308 {
 309     int time, i, round_trips;
 310
 311     for (time = 0; time < 1000 * 180; time += granularity) {
 312
 313         for (i = 0; i < tc->n_bridges; i++) {
 314             rstp_tick_timers(tc->bridges[i]->rstp);
 315         }
 316         for (round_trips = 0; round_trips < granularity; round_trips++) {
 317             bool any = false;
 318
 319             for (i = 0; i < tc->n_bridges; i++) {
 320                 struct bridge *b = tc->bridges[i];
 321
 322                 for (; b->rxq_tail != b->rxq_head; b->rxq_tail++) {
 323                     struct bpdu *bpdu = &b->rxq[b->rxq_tail % RXQ_SIZE];
 324
 325                     rstp_port_received_bpdu(rstp_get_port(b->rstp,
 326                                                           bpdu->port_no),
 327                                             bpdu->data, bpdu->size);
 328                     free(bpdu->data);
 329                     any = true;
 330                 }
 331             }
 332             if (!any) {
 333                 break;
 334             }
 335         }
 336     }
 337 }
 338
 339 OVS_NO_RETURN static void
 340 err(const char *message, ...)
 341     OVS_PRINTF_FORMAT(1, 2);
 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     OVS_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);