tests/test-rstp.c

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