1 /* Copyright (c) 2008 The Board of Trustees of The Leland Stanford
4 * We are making the OpenFlow specification and associated documentation
5 * (Software) available for public use and benefit with the expectation
6 * that others will use, modify and enhance the Software and contribute
7 * those enhancements back to the community. However, since we would
8 * like to make the Software available for broadest use, with as few
9 * restrictions as possible permission is hereby granted, free of
10 * charge, to any person obtaining a copy of this Software to deal in
11 * the Software under the copyrights without restriction, including
12 * without limitation the rights to use, copy, modify, merge, publish,
13 * distribute, sublicense, and/or sell copies of the Software, and to
14 * permit persons to whom the Software is furnished to do so, subject to
15 * the following conditions:
17 * The above copyright notice and this permission notice shall be
18 * included in all copies or substantial portions of the Software.
20 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
21 * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
22 * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
23 * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS
24 * BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN
25 * ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN
26 * CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
29 * The name and trademarks of copyright holder(s) may NOT be used in
30 * advertising or publicity pertaining to the Software or any
31 * derivatives without specific, written prior permission.
56 struct lan *ports[STP_MAX_PORTS];
60 struct bpdu rxq[RXQ_SIZE];
61 int rxq_head, rxq_tail;
65 struct bridge *bridge;
73 struct lan_conn conns[16];
78 struct bridge *bridges[16];
84 static const char *file_name;
85 static int line_number;
86 static char line[128];
87 static char *pos, *token;
88 static int n_warnings;
90 static struct test_case *
93 struct test_case *tc = xmalloc(sizeof *tc);
100 send_bpdu(const void *data, size_t size, int port_no, void *b_)
102 struct bridge *b = b_;
106 assert(port_no < b->n_ports);
107 lan = b->ports[port_no];
111 for (i = 0; i < lan->n_conns; i++) {
112 struct lan_conn *conn = &lan->conns[i];
113 if (conn->bridge != b || conn->port_no != port_no) {
114 struct bridge *dst = conn->bridge;
115 struct bpdu *bpdu = &dst->rxq[dst->rxq_head++ % RXQ_SIZE];
116 assert(dst->rxq_head - dst->rxq_tail <= RXQ_SIZE);
117 bpdu->data = xmemdup(data, size);
119 bpdu->port_no = conn->port_no;
124 static struct bridge *
125 new_bridge(struct test_case *tc, int id)
127 struct bridge *b = xmalloc(sizeof *b);
131 snprintf(name, sizeof name, "stp%x", id);
132 b->stp = stp_create(name, id, send_bpdu, b);
133 assert(tc->n_bridges < ARRAY_SIZE(tc->bridges));
135 b->rxq_head = b->rxq_tail = 0;
136 tc->bridges[tc->n_bridges++] = b;
141 new_lan(struct test_case *tc, const char *name)
143 struct lan *lan = xmalloc(sizeof *lan);
145 lan->name = xstrdup(name);
147 assert(tc->n_lans < ARRAY_SIZE(tc->lans));
148 tc->lans[tc->n_lans++] = lan;
153 reconnect_port(struct bridge *b, int port_no, struct lan *new_lan)
158 assert(port_no < b->n_ports);
159 old_lan = b->ports[port_no];
160 if (old_lan == new_lan) {
164 /* Disconnect from old_lan. */
166 for (j = 0; j < old_lan->n_conns; j++) {
167 struct lan_conn *c = &old_lan->conns[j];
168 if (c->bridge == b && c->port_no == port_no) {
169 memmove(c, c + 1, sizeof *c * (old_lan->n_conns - j - 1));
176 /* Connect to new_lan. */
177 b->ports[port_no] = new_lan;
179 int conn_no = new_lan->n_conns++;
180 assert(conn_no < ARRAY_SIZE(new_lan->conns));
181 new_lan->conns[conn_no].bridge = b;
182 new_lan->conns[conn_no].port_no = port_no;
187 new_port(struct bridge *b, struct lan *lan, int path_cost)
189 int port_no = b->n_ports++;
190 struct stp_port *p = stp_get_port(b->stp, port_no);
191 assert(port_no < ARRAY_SIZE(b->ports));
192 b->ports[port_no] = NULL;
193 stp_port_set_path_cost(p, path_cost);
195 reconnect_port(b, port_no, lan);
199 dump(struct test_case *tc)
203 for (i = 0; i < tc->n_bridges; i++) {
204 struct bridge *b = tc->bridges[i];
205 struct stp *stp = b->stp;
208 printf("%s:", stp_get_name(stp));
209 if (stp_is_root_bridge(stp)) {
213 for (j = 0; j < b->n_ports; j++) {
214 struct stp_port *p = stp_get_port(stp, j);
215 enum stp_state state = stp_port_get_state(p);
217 printf("\tport %d", j);
219 printf(" (lan %s)", b->ports[j]->name);
221 printf(" (disconnected)");
223 printf(": %s", stp_state_name(state));
224 if (p == stp_get_root_port(stp)) {
225 printf(" (root port, root_path_cost=%u)", stp_get_root_path_cost(stp));
232 static void dump_lan_tree(struct test_case *, struct lan *, int level);
235 dump_bridge_tree(struct test_case *tc, struct bridge *b, int level)
243 for (i = 0; i < level; i++) {
246 printf("%s\n", stp_get_name(b->stp));
247 for (i = 0; i < b->n_ports; i++) {
248 struct lan *lan = b->ports[i];
249 struct stp_port *p = stp_get_port(b->stp, i);
250 if (stp_port_get_state(p) == STP_FORWARDING && lan) {
251 dump_lan_tree(tc, lan, level + 1);
257 dump_lan_tree(struct test_case *tc, struct lan *lan, int level)
265 for (i = 0; i < level; i++) {
268 printf("%s\n", lan->name);
269 for (i = 0; i < lan->n_conns; i++) {
270 struct bridge *b = lan->conns[i].bridge;
271 dump_bridge_tree(tc, b, level + 1);
276 tree(struct test_case *tc)
280 for (i = 0; i < tc->n_bridges; i++) {
281 struct bridge *b = tc->bridges[i];
284 for (i = 0; i < tc->n_lans; i++) {
285 struct lan *lan = tc->lans[i];
286 lan->reached = false;
288 for (i = 0; i < tc->n_bridges; i++) {
289 struct bridge *b = tc->bridges[i];
290 struct stp *stp = b->stp;
291 if (stp_is_root_bridge(stp)) {
292 dump_bridge_tree(tc, b, 0);
298 simulate(struct test_case *tc, int granularity)
302 for (time = 0; time < 256 * 180; time += granularity) {
306 for (i = 0; i < tc->n_bridges; i++) {
307 stp_tick(tc->bridges[i]->stp, granularity);
309 for (round_trips = 0; round_trips < granularity; round_trips++) {
311 for (i = 0; i < tc->n_bridges; i++) {
312 struct bridge *b = tc->bridges[i];
313 for (; b->rxq_tail != b->rxq_head; b->rxq_tail++) {
314 struct bpdu *bpdu = &b->rxq[b->rxq_tail % RXQ_SIZE];
315 stp_received_bpdu(stp_get_port(b->stp, bpdu->port_no),
316 bpdu->data, bpdu->size);
328 err(const char *message, ...)
333 err(const char *message, ...)
337 fprintf(stderr, "%s:%d:%td: ", file_name, line_number, pos - line);
338 va_start(args, message);
339 vfprintf(stderr, message, args);
347 warn(const char *message, ...)
351 warn(const char *message, ...)
355 fprintf(stderr, "%s:%d: ", file_name, line_number);
356 va_start(args, message);
357 vfprintf(stderr, message, args);
369 while (isspace((unsigned char) *pos)) {
378 if (isalpha((unsigned char) *pos)) {
379 while (isalpha((unsigned char) *++pos)) {
382 } else if (isdigit((unsigned char) *pos)) {
383 if (*pos == '0' && (pos[1] == 'x' || pos[1] == 'X')) {
385 while (isxdigit((unsigned char) *pos)) {
389 while (isdigit((unsigned char) *++pos)) {
398 token = xmemdup0(start, pos - start);
405 char *save_pos = pos;
406 if (token && isdigit((unsigned char) *token)) {
407 *intp = strtol(token, NULL, 0);
417 match(const char *want)
419 if (token && !strcmp(want, token)) {
432 err("expected integer");
438 must_match(const char *want)
441 err("expected \"%s\"", want);
446 main(int argc, char *argv[])
448 struct test_case *tc;
453 fatal(0, "usage: test-stp INPUT.STP\n");
457 input_file = fopen(file_name, "r");
459 fatal(errno, "error opening \"%s\"", file_name);
462 tc = new_test_case();
463 for (i = 0; i < 26; i++) {
470 for (line_number = 1; fgets(line, sizeof line, input_file);
473 char *newline, *hash;
475 newline = strchr(line, '\n');
479 hash = strchr(line, '#');
488 if (match("bridge")) {
489 struct bridge *bridge;
490 int bridge_no, port_no;
492 bridge_no = must_get_int();
493 if (bridge_no < tc->n_bridges) {
494 bridge = tc->bridges[bridge_no];
495 } else if (bridge_no == tc->n_bridges) {
496 bridge = new_bridge(tc, must_get_int());
498 err("bridges must be numbered consecutively from 0");
501 stp_set_bridge_priority(bridge->stp, must_get_int());
505 for (port_no = 0; port_no < STP_MAX_PORTS; port_no++) {
506 struct stp_port *p = stp_get_port(bridge->stp, port_no);
507 if (!token || match("X")) {
509 } else if (match("_")) {
515 if (!strcmp(token, "0")) {
517 } else if (strlen(token) == 1 && islower(*token)) {
518 lan = tc->lans[*token - 'a'];
520 err("%s is not a valid LAN name "
521 "(0 or a lowercase letter)", token);
525 path_cost = match(":") ? must_get_int() : 10;
526 if (port_no < bridge->n_ports) {
527 stp_port_set_path_cost(p, path_cost);
529 reconnect_port(bridge, port_no, lan);
530 } else if (port_no == bridge->n_ports) {
531 new_port(bridge, lan, path_cost);
533 err("ports must be numbered consecutively");
536 stp_port_set_priority(p, must_get_int());
541 } else if (match("run")) {
542 simulate(tc, must_get_int());
543 } else if (match("dump")) {
545 } else if (match("tree")) {
547 } else if (match("check")) {
550 int bridge_no, port_no;
552 bridge_no = must_get_int();
553 if (bridge_no >= tc->n_bridges) {
554 err("no bridge numbered %d", bridge_no);
556 b = tc->bridges[bridge_no];
561 if (match("rootid")) {
564 rootid = must_get_int();
566 rootid |= (uint64_t) must_get_int() << 48;
568 rootid |= UINT64_C(0x8000) << 48;
570 if (stp_get_designated_root(stp) != rootid) {
571 warn("%s: root %"PRIx64", not %"PRIx64,
572 stp_get_name(stp), stp_get_designated_root(stp),
578 if (stp_get_root_path_cost(stp)) {
579 warn("%s: root path cost of root is %u but should be 0",
580 stp_get_name(stp), stp_get_root_path_cost(stp));
582 if (!stp_is_root_bridge(stp)) {
583 warn("%s: root is %"PRIx64", not %"PRIx64,
585 stp_get_designated_root(stp), stp_get_bridge_id(stp));
587 for (port_no = 0; port_no < b->n_ports; port_no++) {
588 struct stp_port *p = stp_get_port(stp, port_no);
589 enum stp_state state = stp_port_get_state(p);
590 if (!(state & (STP_DISABLED | STP_FORWARDING))) {
591 warn("%s: root port %d in state %s",
592 stp_get_name(b->stp), port_no,
593 stp_state_name(state));
597 for (port_no = 0; port_no < STP_MAX_PORTS; port_no++) {
598 struct stp_port *p = stp_get_port(stp, port_no);
599 enum stp_state state;
600 if (token == NULL || match("D")) {
601 state = STP_DISABLED;
602 } else if (match("B")) {
603 state = STP_BLOCKING;
604 } else if (match("Li")) {
605 state = STP_LISTENING;
606 } else if (match("Le")) {
607 state = STP_LEARNING;
608 } else if (match("F")) {
609 state = STP_FORWARDING;
610 } else if (match("_")) {
613 err("unknown port state %s", token);
615 if (stp_port_get_state(p) != state) {
616 warn("%s port %d: state is %s but should be %s",
617 stp_get_name(stp), port_no,
618 stp_state_name(stp_port_get_state(p)),
619 stp_state_name(state));
621 if (state == STP_FORWARDING) {
622 struct stp_port *root_port = stp_get_root_port(stp);
624 int root_path_cost = must_get_int();
625 if (p != root_port) {
626 warn("%s: port %d is not the root port",
627 stp_get_name(stp), port_no);
629 warn("%s: (there is no root port)",
632 warn("%s: (port %d is the root port)",
634 stp_port_no(root_port));
636 } else if (root_path_cost
637 != stp_get_root_path_cost(stp)) {
638 warn("%s: root path cost is %u, should be %d",
640 stp_get_root_path_cost(stp),
643 } else if (p == root_port) {
644 warn("%s: port %d is the root port but "
645 "not expected to be",
646 stp_get_name(stp), port_no);
656 err("trailing garbage on line");