2 * Copyright (c) 2008, 2009 Nicira Networks.
4 * Permission to use, copy, modify, and/or distribute this software for any
5 * purpose with or without fee is hereby granted, provided that the above
6 * copyright notice and this permission notice appear in all copies.
8 * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
9 * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
10 * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR
11 * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
12 * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
13 * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
14 * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
40 struct lan *ports[STP_MAX_PORTS];
44 struct bpdu rxq[RXQ_SIZE];
45 int rxq_head, rxq_tail;
49 struct bridge *bridge;
57 struct lan_conn conns[16];
62 struct bridge *bridges[16];
68 static const char *file_name;
69 static int line_number;
70 static char line[128];
71 static char *pos, *token;
72 static int n_warnings;
74 static struct test_case *
77 struct test_case *tc = xmalloc(sizeof *tc);
84 send_bpdu(struct ofpbuf *pkt, int port_no, void *b_)
86 struct bridge *b = b_;
89 assert(port_no < b->n_ports);
90 lan = b->ports[port_no];
92 const void *data = pkt->l3;
93 size_t size = (char *) ofpbuf_tail(pkt) - (char *) data;
96 for (i = 0; i < lan->n_conns; i++) {
97 struct lan_conn *conn = &lan->conns[i];
98 if (conn->bridge != b || conn->port_no != port_no) {
99 struct bridge *dst = conn->bridge;
100 struct bpdu *bpdu = &dst->rxq[dst->rxq_head++ % RXQ_SIZE];
101 assert(dst->rxq_head - dst->rxq_tail <= RXQ_SIZE);
102 bpdu->data = xmemdup(data, size);
104 bpdu->port_no = conn->port_no;
111 static struct bridge *
112 new_bridge(struct test_case *tc, int id)
114 struct bridge *b = xmalloc(sizeof *b);
118 snprintf(name, sizeof name, "stp%x", id);
119 b->stp = stp_create(name, id, send_bpdu, b);
120 assert(tc->n_bridges < ARRAY_SIZE(tc->bridges));
122 b->rxq_head = b->rxq_tail = 0;
123 tc->bridges[tc->n_bridges++] = b;
128 new_lan(struct test_case *tc, const char *name)
130 struct lan *lan = xmalloc(sizeof *lan);
132 lan->name = xstrdup(name);
134 assert(tc->n_lans < ARRAY_SIZE(tc->lans));
135 tc->lans[tc->n_lans++] = lan;
140 reconnect_port(struct bridge *b, int port_no, struct lan *new_lan)
145 assert(port_no < b->n_ports);
146 old_lan = b->ports[port_no];
147 if (old_lan == new_lan) {
151 /* Disconnect from old_lan. */
153 for (j = 0; j < old_lan->n_conns; j++) {
154 struct lan_conn *c = &old_lan->conns[j];
155 if (c->bridge == b && c->port_no == port_no) {
156 memmove(c, c + 1, sizeof *c * (old_lan->n_conns - j - 1));
163 /* Connect to new_lan. */
164 b->ports[port_no] = new_lan;
166 int conn_no = new_lan->n_conns++;
167 assert(conn_no < ARRAY_SIZE(new_lan->conns));
168 new_lan->conns[conn_no].bridge = b;
169 new_lan->conns[conn_no].port_no = port_no;
174 new_port(struct bridge *b, struct lan *lan, int path_cost)
176 int port_no = b->n_ports++;
177 struct stp_port *p = stp_get_port(b->stp, port_no);
178 assert(port_no < ARRAY_SIZE(b->ports));
179 b->ports[port_no] = NULL;
180 stp_port_set_path_cost(p, path_cost);
182 reconnect_port(b, port_no, lan);
186 dump(struct test_case *tc)
190 for (i = 0; i < tc->n_bridges; i++) {
191 struct bridge *b = tc->bridges[i];
192 struct stp *stp = b->stp;
195 printf("%s:", stp_get_name(stp));
196 if (stp_is_root_bridge(stp)) {
200 for (j = 0; j < b->n_ports; j++) {
201 struct stp_port *p = stp_get_port(stp, j);
202 enum stp_state state = stp_port_get_state(p);
204 printf("\tport %d", j);
206 printf(" (lan %s)", b->ports[j]->name);
208 printf(" (disconnected)");
210 printf(": %s", stp_state_name(state));
211 if (p == stp_get_root_port(stp)) {
212 printf(" (root port, root_path_cost=%u)", stp_get_root_path_cost(stp));
219 static void dump_lan_tree(struct test_case *, struct lan *, int level);
222 dump_bridge_tree(struct test_case *tc, struct bridge *b, int level)
230 for (i = 0; i < level; i++) {
233 printf("%s\n", stp_get_name(b->stp));
234 for (i = 0; i < b->n_ports; i++) {
235 struct lan *lan = b->ports[i];
236 struct stp_port *p = stp_get_port(b->stp, i);
237 if (stp_port_get_state(p) == STP_FORWARDING && lan) {
238 dump_lan_tree(tc, lan, level + 1);
244 dump_lan_tree(struct test_case *tc, struct lan *lan, int level)
252 for (i = 0; i < level; i++) {
255 printf("%s\n", lan->name);
256 for (i = 0; i < lan->n_conns; i++) {
257 struct bridge *b = lan->conns[i].bridge;
258 dump_bridge_tree(tc, b, level + 1);
263 tree(struct test_case *tc)
267 for (i = 0; i < tc->n_bridges; i++) {
268 struct bridge *b = tc->bridges[i];
271 for (i = 0; i < tc->n_lans; i++) {
272 struct lan *lan = tc->lans[i];
273 lan->reached = false;
275 for (i = 0; i < tc->n_bridges; i++) {
276 struct bridge *b = tc->bridges[i];
277 struct stp *stp = b->stp;
278 if (stp_is_root_bridge(stp)) {
279 dump_bridge_tree(tc, b, 0);
285 simulate(struct test_case *tc, int granularity)
289 for (time = 0; time < 1000 * 180; time += granularity) {
293 for (i = 0; i < tc->n_bridges; i++) {
294 stp_tick(tc->bridges[i]->stp, granularity);
296 for (round_trips = 0; round_trips < granularity; round_trips++) {
298 for (i = 0; i < tc->n_bridges; i++) {
299 struct bridge *b = tc->bridges[i];
300 for (; b->rxq_tail != b->rxq_head; b->rxq_tail++) {
301 struct bpdu *bpdu = &b->rxq[b->rxq_tail % RXQ_SIZE];
302 stp_received_bpdu(stp_get_port(b->stp, bpdu->port_no),
303 bpdu->data, bpdu->size);
315 err(const char *message, ...)
320 err(const char *message, ...)
324 fprintf(stderr, "%s:%d:%td: ", file_name, line_number, pos - line);
325 va_start(args, message);
326 vfprintf(stderr, message, args);
334 warn(const char *message, ...)
338 warn(const char *message, ...)
342 fprintf(stderr, "%s:%d: ", file_name, line_number);
343 va_start(args, message);
344 vfprintf(stderr, message, args);
356 while (isspace((unsigned char) *pos)) {
365 if (isalpha((unsigned char) *pos)) {
366 while (isalpha((unsigned char) *++pos)) {
369 } else if (isdigit((unsigned char) *pos)) {
370 if (*pos == '0' && (pos[1] == 'x' || pos[1] == 'X')) {
372 while (isxdigit((unsigned char) *pos)) {
376 while (isdigit((unsigned char) *++pos)) {
385 token = xmemdup0(start, pos - start);
392 char *save_pos = pos;
393 if (token && isdigit((unsigned char) *token)) {
394 *intp = strtol(token, NULL, 0);
404 match(const char *want)
406 if (token && !strcmp(want, token)) {
419 err("expected integer");
425 must_match(const char *want)
428 err("expected \"%s\"", want);
433 main(int argc, char *argv[])
435 struct test_case *tc;
440 ovs_fatal(0, "usage: test-stp INPUT.STP\n");
444 input_file = fopen(file_name, "r");
446 ovs_fatal(errno, "error opening \"%s\"", file_name);
449 tc = new_test_case();
450 for (i = 0; i < 26; i++) {
457 for (line_number = 1; fgets(line, sizeof line, input_file);
460 char *newline, *hash;
462 newline = strchr(line, '\n');
466 hash = strchr(line, '#');
475 if (match("bridge")) {
476 struct bridge *bridge;
477 int bridge_no, port_no;
479 bridge_no = must_get_int();
480 if (bridge_no < tc->n_bridges) {
481 bridge = tc->bridges[bridge_no];
482 } else if (bridge_no == tc->n_bridges) {
483 bridge = new_bridge(tc, must_get_int());
485 err("bridges must be numbered consecutively from 0");
488 stp_set_bridge_priority(bridge->stp, must_get_int());
492 for (port_no = 0; port_no < STP_MAX_PORTS; port_no++) {
493 struct stp_port *p = stp_get_port(bridge->stp, port_no);
494 if (!token || match("X")) {
496 } else if (match("_")) {
502 if (!strcmp(token, "0")) {
504 } else if (strlen(token) == 1 && islower(*token)) {
505 lan = tc->lans[*token - 'a'];
507 err("%s is not a valid LAN name "
508 "(0 or a lowercase letter)", token);
512 path_cost = match(":") ? must_get_int() : 10;
513 if (port_no < bridge->n_ports) {
514 stp_port_set_path_cost(p, path_cost);
516 reconnect_port(bridge, port_no, lan);
517 } else if (port_no == bridge->n_ports) {
518 new_port(bridge, lan, path_cost);
520 err("ports must be numbered consecutively");
523 stp_port_set_priority(p, must_get_int());
528 } else if (match("run")) {
529 simulate(tc, must_get_int());
530 } else if (match("dump")) {
532 } else if (match("tree")) {
534 } else if (match("check")) {
537 int bridge_no, port_no;
539 bridge_no = must_get_int();
540 if (bridge_no >= tc->n_bridges) {
541 err("no bridge numbered %d", bridge_no);
543 b = tc->bridges[bridge_no];
548 if (match("rootid")) {
551 rootid = must_get_int();
553 rootid |= (uint64_t) must_get_int() << 48;
555 rootid |= UINT64_C(0x8000) << 48;
557 if (stp_get_designated_root(stp) != rootid) {
558 warn("%s: root %"PRIx64", not %"PRIx64,
559 stp_get_name(stp), stp_get_designated_root(stp),
565 if (stp_get_root_path_cost(stp)) {
566 warn("%s: root path cost of root is %u but should be 0",
567 stp_get_name(stp), stp_get_root_path_cost(stp));
569 if (!stp_is_root_bridge(stp)) {
570 warn("%s: root is %"PRIx64", not %"PRIx64,
572 stp_get_designated_root(stp), stp_get_bridge_id(stp));
574 for (port_no = 0; port_no < b->n_ports; port_no++) {
575 struct stp_port *p = stp_get_port(stp, port_no);
576 enum stp_state state = stp_port_get_state(p);
577 if (!(state & (STP_DISABLED | STP_FORWARDING))) {
578 warn("%s: root port %d in state %s",
579 stp_get_name(b->stp), port_no,
580 stp_state_name(state));
584 for (port_no = 0; port_no < STP_MAX_PORTS; port_no++) {
585 struct stp_port *p = stp_get_port(stp, port_no);
586 enum stp_state state;
587 if (token == NULL || match("D")) {
588 state = STP_DISABLED;
589 } else if (match("B")) {
590 state = STP_BLOCKING;
591 } else if (match("Li")) {
592 state = STP_LISTENING;
593 } else if (match("Le")) {
594 state = STP_LEARNING;
595 } else if (match("F")) {
596 state = STP_FORWARDING;
597 } else if (match("_")) {
600 err("unknown port state %s", token);
602 if (stp_port_get_state(p) != state) {
603 warn("%s port %d: state is %s but should be %s",
604 stp_get_name(stp), port_no,
605 stp_state_name(stp_port_get_state(p)),
606 stp_state_name(state));
608 if (state == STP_FORWARDING) {
609 struct stp_port *root_port = stp_get_root_port(stp);
611 int root_path_cost = must_get_int();
612 if (p != root_port) {
613 warn("%s: port %d is not the root port",
614 stp_get_name(stp), port_no);
616 warn("%s: (there is no root port)",
619 warn("%s: (port %d is the root port)",
621 stp_port_no(root_port));
623 } else if (root_path_cost
624 != stp_get_root_path_cost(stp)) {
625 warn("%s: root path cost is %u, should be %d",
627 stp_get_root_path_cost(stp),
630 } else if (p == root_port) {
631 warn("%s: port %d is the root port but "
632 "not expected to be",
633 stp_get_name(stp), port_no);
643 err("trailing garbage on line");