Import from old repository commit 61ef2b42a9c4ba8e1600f15bb0236765edc2ad45.
[openvswitch] / tests / test-stp.c
1 /*
2  * Copyright (c) 2008, 2009 Nicira Networks.
3  *
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.
7  *
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.
15  */
16
17 #include "stp.h"
18 #include <assert.h>
19 #include <ctype.h>
20 #include <errno.h>
21 #include <inttypes.h>
22 #include <stdarg.h>
23 #include <stdlib.h>
24 #include "ofpbuf.h"
25 #include "packets.h"
26
27 struct bpdu {
28     int port_no;
29     void *data;
30     size_t size;
31 };
32
33 struct bridge {
34     struct test_case *tc;
35     int id;
36     bool reached;
37
38     struct stp *stp;
39
40     struct lan *ports[STP_MAX_PORTS];
41     int n_ports;
42
43 #define RXQ_SIZE 16
44     struct bpdu rxq[RXQ_SIZE];
45     int rxq_head, rxq_tail;
46 };
47
48 struct lan_conn {
49     struct bridge *bridge;
50     int port_no;
51 };
52
53 struct lan {
54     struct test_case *tc;
55     const char *name;
56     bool reached;
57     struct lan_conn conns[16];
58     int n_conns;
59 };
60
61 struct test_case {
62     struct bridge *bridges[16];
63     int n_bridges;
64     struct lan *lans[26];
65     int n_lans;
66 };
67
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;
73
74 static struct test_case *
75 new_test_case(void)
76 {
77     struct test_case *tc = xmalloc(sizeof *tc);
78     tc->n_bridges = 0;
79     tc->n_lans = 0;
80     return tc;
81 }
82
83 static void
84 send_bpdu(struct ofpbuf *pkt, int port_no, void *b_)
85 {
86     struct bridge *b = b_;
87     struct lan *lan;
88
89     assert(port_no < b->n_ports);
90     lan = b->ports[port_no];
91     if (lan) {
92         const void *data = pkt->l3;
93         size_t size = (char *) ofpbuf_tail(pkt) - (char *) data;
94         int i;
95
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);
103                 bpdu->size = size;
104                 bpdu->port_no = conn->port_no;
105             }
106         }
107     }
108     ofpbuf_delete(pkt);
109 }
110
111 static struct bridge *
112 new_bridge(struct test_case *tc, int id)
113 {
114     struct bridge *b = xmalloc(sizeof *b);
115     char name[16];
116     b->tc = tc;
117     b->id = id;
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));
121     b->n_ports = 0;
122     b->rxq_head = b->rxq_tail = 0;
123     tc->bridges[tc->n_bridges++] = b;
124     return b;
125 }
126
127 static struct lan *
128 new_lan(struct test_case *tc, const char *name)
129 {
130     struct lan *lan = xmalloc(sizeof *lan);
131     lan->tc = tc;
132     lan->name = xstrdup(name);
133     lan->n_conns = 0;
134     assert(tc->n_lans < ARRAY_SIZE(tc->lans));
135     tc->lans[tc->n_lans++] = lan;
136     return lan;
137 }
138
139 static void
140 reconnect_port(struct bridge *b, int port_no, struct lan *new_lan)
141 {
142     struct lan *old_lan;
143     int j;
144
145     assert(port_no < b->n_ports);
146     old_lan = b->ports[port_no];
147     if (old_lan == new_lan) {
148         return;
149     }
150
151     /* Disconnect from old_lan. */
152     if (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));
157                 old_lan->n_conns--;
158                 break;
159             }
160         }
161     }
162
163     /* Connect to new_lan. */
164     b->ports[port_no] = new_lan;
165     if (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;
170     }
171 }
172
173 static void
174 new_port(struct bridge *b, struct lan *lan, int path_cost)
175 {
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);
181     stp_port_enable(p);
182     reconnect_port(b, port_no, lan);
183 }
184
185 static void
186 dump(struct test_case *tc)
187 {
188     int i;
189
190     for (i = 0; i < tc->n_bridges; i++) {
191         struct bridge *b = tc->bridges[i];
192         struct stp *stp = b->stp;
193         int j;
194
195         printf("%s:", stp_get_name(stp));
196         if (stp_is_root_bridge(stp)) {
197             printf(" root");
198         }
199         printf("\n");
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);
203
204             printf("\tport %d", j);
205             if (b->ports[j]) {
206                 printf(" (lan %s)", b->ports[j]->name);
207             } else {
208                 printf(" (disconnected)");
209             }
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));
213             }
214             printf("\n");
215         }
216     }
217 }
218
219 static void dump_lan_tree(struct test_case *, struct lan *, int level);
220
221 static void
222 dump_bridge_tree(struct test_case *tc, struct bridge *b, int level)
223 {
224     int i;
225
226     if (b->reached) {
227         return;
228     }
229     b->reached = true;
230     for (i = 0; i < level; i++) {
231         printf("\t");
232     }
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);
239         }
240     }
241 }
242
243 static void
244 dump_lan_tree(struct test_case *tc, struct lan *lan, int level) 
245 {
246     int i;
247
248     if (lan->reached) {
249         return;
250     }
251     lan->reached = true;
252     for (i = 0; i < level; i++) {
253         printf("\t");
254     }
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);
259     }
260 }
261
262 static void
263 tree(struct test_case *tc)
264 {
265     int i;
266
267     for (i = 0; i < tc->n_bridges; i++) {
268         struct bridge *b = tc->bridges[i];
269         b->reached = false;
270     }
271     for (i = 0; i < tc->n_lans; i++) {
272         struct lan *lan = tc->lans[i];
273         lan->reached = false;
274     }
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);
280         }
281     }
282 }
283
284 static void
285 simulate(struct test_case *tc, int granularity)
286 {
287     int time;
288
289     for (time = 0; time < 1000 * 180; time += granularity) {
290         int round_trips;
291         int i;
292
293         for (i = 0; i < tc->n_bridges; i++) {
294             stp_tick(tc->bridges[i]->stp, granularity);
295         }
296         for (round_trips = 0; round_trips < granularity; round_trips++) {
297             bool any = false;
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);
304                     any = true;
305                 }
306             }
307             if (!any) {
308                 break;
309             }
310         }
311     }
312 }
313
314 static void
315 err(const char *message, ...)
316     PRINTF_FORMAT(1, 2)
317     NO_RETURN;
318
319 static void
320 err(const char *message, ...)
321 {
322     va_list args;
323
324     fprintf(stderr, "%s:%d:%td: ", file_name, line_number, pos - line);
325     va_start(args, message);
326     vfprintf(stderr, message, args);
327     va_end(args);
328     putc('\n', stderr);
329
330     exit(EXIT_FAILURE);
331 }
332
333 static void
334 warn(const char *message, ...)
335     PRINTF_FORMAT(1, 2);
336
337 static void
338 warn(const char *message, ...)
339 {
340     va_list args;
341
342     fprintf(stderr, "%s:%d: ", file_name, line_number);
343     va_start(args, message);
344     vfprintf(stderr, message, args);
345     va_end(args);
346     putc('\n', stderr);
347
348     n_warnings++;
349 }
350
351 static bool
352 get_token(void)
353 {
354     char *start;
355
356     while (isspace((unsigned char) *pos)) {
357         pos++;
358     }
359     if (*pos == '\0') {
360         token = NULL;
361         return false;
362     }
363
364     start = pos;
365     if (isalpha((unsigned char) *pos)) {
366         while (isalpha((unsigned char) *++pos)) {
367             continue;
368         }
369     } else if (isdigit((unsigned char) *pos)) {
370         if (*pos == '0' && (pos[1] == 'x' || pos[1] == 'X')) {
371             pos += 2;
372             while (isxdigit((unsigned char) *pos)) {
373                 pos++;
374             }
375         } else {
376             while (isdigit((unsigned char) *++pos)) {
377                 continue;
378             }
379         }
380     } else {
381         pos++;
382     }
383
384     free(token);
385     token = xmemdup0(start, pos - start);
386     return true;
387 }
388
389 static bool
390 get_int(int *intp)
391 {
392     char *save_pos = pos;
393     if (token && isdigit((unsigned char) *token)) {
394         *intp = strtol(token, NULL, 0);
395         get_token();
396         return true;
397     } else {
398         pos = save_pos;
399         return false;
400     }
401 }
402
403 static bool
404 match(const char *want)
405 {
406     if (token && !strcmp(want, token)) {
407         get_token();
408         return true;
409     } else {
410         return false;
411     }
412 }
413
414 static int
415 must_get_int(void)
416 {
417     int x;
418     if (!get_int(&x)) {
419         err("expected integer");
420     }
421     return x;
422 }
423
424 static void
425 must_match(const char *want)
426 {
427     if (!match(want)) {
428         err("expected \"%s\"", want);
429     }
430 }
431
432 int
433 main(int argc, char *argv[])
434 {
435     struct test_case *tc;
436     FILE *input_file;
437     int i;
438
439     if (argc != 2) {
440         ovs_fatal(0, "usage: test-stp INPUT.STP\n");
441     }
442     file_name = argv[1];
443
444     input_file = fopen(file_name, "r");
445     if (!input_file) {
446         ovs_fatal(errno, "error opening \"%s\"", file_name);
447     }
448
449     tc = new_test_case();
450     for (i = 0; i < 26; i++) {
451         char name[2];
452         name[0] = 'a' + i;
453         name[1] = '\0';
454         new_lan(tc, name);
455     }
456
457     for (line_number = 1; fgets(line, sizeof line, input_file);
458          line_number++)
459     {
460         char *newline, *hash;
461
462         newline = strchr(line, '\n');
463         if (newline) {
464             *newline = '\0';
465         }
466         hash = strchr(line, '#');
467         if (hash) {
468             *hash = '\0';
469         }
470
471         pos = line;
472         if (!get_token()) {
473             continue;
474         }
475         if (match("bridge")) {
476             struct bridge *bridge;
477             int bridge_no, port_no;
478
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());
484             } else {
485                 err("bridges must be numbered consecutively from 0");
486             }
487             if (match("^")) {
488                 stp_set_bridge_priority(bridge->stp, must_get_int());
489             }
490
491             if (match("=")) {
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")) {
495                         stp_port_disable(p);
496                     } else if (match("_")) {
497                         /* Nothing to do. */
498                     } else {
499                         struct lan *lan;
500                         int path_cost;
501
502                         if (!strcmp(token, "0")) {
503                             lan = NULL;
504                         } else if (strlen(token) == 1 && islower(*token)) {
505                             lan = tc->lans[*token - 'a']; 
506                         } else {
507                             err("%s is not a valid LAN name "
508                                 "(0 or a lowercase letter)", token);
509                         }
510                         get_token();
511
512                         path_cost = match(":") ? must_get_int() : 10;
513                         if (port_no < bridge->n_ports) {
514                             stp_port_set_path_cost(p, path_cost);
515                             stp_port_enable(p);
516                             reconnect_port(bridge, port_no, lan);
517                         } else if (port_no == bridge->n_ports) {
518                             new_port(bridge, lan, path_cost);
519                         } else {
520                             err("ports must be numbered consecutively");
521                         }
522                         if (match("^")) {
523                             stp_port_set_priority(p, must_get_int());
524                         }
525                     }
526                 }
527             }
528         } else if (match("run")) {
529             simulate(tc, must_get_int());
530         } else if (match("dump")) {
531             dump(tc);
532         } else if (match("tree")) {
533             tree(tc);
534         } else if (match("check")) {
535             struct bridge *b;
536             struct stp *stp;
537             int bridge_no, port_no;
538
539             bridge_no = must_get_int();
540             if (bridge_no >= tc->n_bridges) {
541                 err("no bridge numbered %d", bridge_no);
542             }
543             b = tc->bridges[bridge_no];
544             stp = b->stp;
545
546             must_match("=");
547
548             if (match("rootid")) {
549                 uint64_t rootid;
550                 must_match(":");
551                 rootid = must_get_int();
552                 if (match("^")) {
553                     rootid |= (uint64_t) must_get_int() << 48;
554                 } else {
555                     rootid |= UINT64_C(0x8000) << 48;
556                 }
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),
560                          rootid);
561                 }
562             }
563
564             if (match("root")) {
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));
568                 }
569                 if (!stp_is_root_bridge(stp)) {
570                     warn("%s: root is %"PRIx64", not %"PRIx64,
571                          stp_get_name(stp),
572                          stp_get_designated_root(stp), stp_get_bridge_id(stp));
573                 }
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));
581                     }
582                 }
583             } else {
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("_")) {
598                         continue;
599                     } else {
600                         err("unknown port state %s", token);
601                     }
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));
607                     }
608                     if (state == STP_FORWARDING) {
609                         struct stp_port *root_port = stp_get_root_port(stp);
610                         if (match(":")) {
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);
615                                 if (!root_port) {
616                                     warn("%s: (there is no root port)",
617                                          stp_get_name(stp));
618                                 } else {
619                                     warn("%s: (port %d is the root port)",
620                                          stp_get_name(stp),
621                                          stp_port_no(root_port));
622                                 }
623                             } else if (root_path_cost
624                                        != stp_get_root_path_cost(stp)) {
625                                 warn("%s: root path cost is %u, should be %d",
626                                      stp_get_name(stp),
627                                      stp_get_root_path_cost(stp),
628                                      root_path_cost);
629                             }
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);
634                         }
635                     }
636                 }
637             }
638             if (n_warnings) {
639                 exit(EXIT_FAILURE);
640             }
641         }
642         if (get_token()) {
643             err("trailing garbage on line");
644         }
645     }
646
647     return 0;
648 }