unixctl: Skip Python unixctl tests.
[openvswitch] / tests / test-stp.c
1 /*
2  * Copyright (c) 2008, 2009, 2010 Nicira Networks.
3  *
4  * Licensed under the Apache License, Version 2.0 (the "License");
5  * you may not use this file except in compliance with the License.
6  * You may obtain a copy of the License at:
7  *
8  *     http://www.apache.org/licenses/LICENSE-2.0
9  *
10  * Unless required by applicable law or agreed to in writing, software
11  * distributed under the License is distributed on an "AS IS" BASIS,
12  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13  * See the License for the specific language governing permissions and
14  * limitations under the License.
15  */
16
17 #include <config.h>
18
19 #include "stp.h"
20 #include <assert.h>
21 #include <ctype.h>
22 #include <errno.h>
23 #include <inttypes.h>
24 #include <stdarg.h>
25 #include <stdlib.h>
26 #include "ofpbuf.h"
27 #include "packets.h"
28 #include "vlog.h"
29
30 struct bpdu {
31     int port_no;
32     void *data;
33     size_t size;
34 };
35
36 struct bridge {
37     struct test_case *tc;
38     int id;
39     bool reached;
40
41     struct stp *stp;
42
43     struct lan *ports[STP_MAX_PORTS];
44     int n_ports;
45
46 #define RXQ_SIZE 16
47     struct bpdu rxq[RXQ_SIZE];
48     int rxq_head, rxq_tail;
49 };
50
51 struct lan_conn {
52     struct bridge *bridge;
53     int port_no;
54 };
55
56 struct lan {
57     struct test_case *tc;
58     const char *name;
59     bool reached;
60     struct lan_conn conns[16];
61     int n_conns;
62 };
63
64 struct test_case {
65     struct bridge *bridges[16];
66     int n_bridges;
67     struct lan *lans[26];
68     int n_lans;
69 };
70
71 static const char *file_name;
72 static int line_number;
73 static char line[128];
74 static char *pos, *token;
75 static int n_warnings;
76
77 static struct test_case *
78 new_test_case(void)
79 {
80     struct test_case *tc = xmalloc(sizeof *tc);
81     tc->n_bridges = 0;
82     tc->n_lans = 0;
83     return tc;
84 }
85
86 static void
87 send_bpdu(struct ofpbuf *pkt, int port_no, void *b_)
88 {
89     struct bridge *b = b_;
90     struct lan *lan;
91
92     assert(port_no < b->n_ports);
93     lan = b->ports[port_no];
94     if (lan) {
95         const void *data = pkt->l3;
96         size_t size = (char *) ofpbuf_tail(pkt) - (char *) data;
97         int i;
98
99         for (i = 0; i < lan->n_conns; i++) {
100             struct lan_conn *conn = &lan->conns[i];
101             if (conn->bridge != b || conn->port_no != port_no) {
102                 struct bridge *dst = conn->bridge;
103                 struct bpdu *bpdu = &dst->rxq[dst->rxq_head++ % RXQ_SIZE];
104                 assert(dst->rxq_head - dst->rxq_tail <= RXQ_SIZE);
105                 bpdu->data = xmemdup(data, size);
106                 bpdu->size = size;
107                 bpdu->port_no = conn->port_no;
108             }
109         }
110     }
111     ofpbuf_delete(pkt);
112 }
113
114 static struct bridge *
115 new_bridge(struct test_case *tc, int id)
116 {
117     struct bridge *b = xmalloc(sizeof *b);
118     char name[16];
119     b->tc = tc;
120     b->id = id;
121     snprintf(name, sizeof name, "stp%x", id);
122     b->stp = stp_create(name, id, send_bpdu, b);
123     assert(tc->n_bridges < ARRAY_SIZE(tc->bridges));
124     b->n_ports = 0;
125     b->rxq_head = b->rxq_tail = 0;
126     tc->bridges[tc->n_bridges++] = b;
127     return b;
128 }
129
130 static struct lan *
131 new_lan(struct test_case *tc, const char *name)
132 {
133     struct lan *lan = xmalloc(sizeof *lan);
134     lan->tc = tc;
135     lan->name = xstrdup(name);
136     lan->n_conns = 0;
137     assert(tc->n_lans < ARRAY_SIZE(tc->lans));
138     tc->lans[tc->n_lans++] = lan;
139     return lan;
140 }
141
142 static void
143 reconnect_port(struct bridge *b, int port_no, struct lan *new_lan)
144 {
145     struct lan *old_lan;
146     int j;
147
148     assert(port_no < b->n_ports);
149     old_lan = b->ports[port_no];
150     if (old_lan == new_lan) {
151         return;
152     }
153
154     /* Disconnect from old_lan. */
155     if (old_lan) {
156         for (j = 0; j < old_lan->n_conns; j++) {
157             struct lan_conn *c = &old_lan->conns[j];
158             if (c->bridge == b && c->port_no == port_no) {
159                 memmove(c, c + 1, sizeof *c * (old_lan->n_conns - j - 1));
160                 old_lan->n_conns--;
161                 break;
162             }
163         }
164     }
165
166     /* Connect to new_lan. */
167     b->ports[port_no] = new_lan;
168     if (new_lan) {
169         int conn_no = new_lan->n_conns++;
170         assert(conn_no < ARRAY_SIZE(new_lan->conns));
171         new_lan->conns[conn_no].bridge = b;
172         new_lan->conns[conn_no].port_no = port_no;
173     }
174 }
175
176 static void
177 new_port(struct bridge *b, struct lan *lan, int path_cost)
178 {
179     int port_no = b->n_ports++;
180     struct stp_port *p = stp_get_port(b->stp, port_no);
181     assert(port_no < ARRAY_SIZE(b->ports));
182     b->ports[port_no] = NULL;
183     stp_port_set_path_cost(p, path_cost);
184     stp_port_enable(p);
185     reconnect_port(b, port_no, lan);
186 }
187
188 static void
189 dump(struct test_case *tc)
190 {
191     int i;
192
193     for (i = 0; i < tc->n_bridges; i++) {
194         struct bridge *b = tc->bridges[i];
195         struct stp *stp = b->stp;
196         int j;
197
198         printf("%s:", stp_get_name(stp));
199         if (stp_is_root_bridge(stp)) {
200             printf(" root");
201         }
202         printf("\n");
203         for (j = 0; j < b->n_ports; j++) {
204             struct stp_port *p = stp_get_port(stp, j);
205             enum stp_state state = stp_port_get_state(p);
206
207             printf("\tport %d", j);
208             if (b->ports[j]) {
209                 printf(" (lan %s)", b->ports[j]->name);
210             } else {
211                 printf(" (disconnected)");
212             }
213             printf(": %s", stp_state_name(state));
214             if (p == stp_get_root_port(stp)) {
215                 printf(" (root port, root_path_cost=%u)", stp_get_root_path_cost(stp));
216             }
217             printf("\n");
218         }
219     }
220 }
221
222 static void dump_lan_tree(struct test_case *, struct lan *, int level);
223
224 static void
225 dump_bridge_tree(struct test_case *tc, struct bridge *b, int level)
226 {
227     int i;
228
229     if (b->reached) {
230         return;
231     }
232     b->reached = true;
233     for (i = 0; i < level; i++) {
234         printf("\t");
235     }
236     printf("%s\n", stp_get_name(b->stp));
237     for (i = 0; i < b->n_ports; i++) {
238         struct lan *lan = b->ports[i];
239         struct stp_port *p = stp_get_port(b->stp, i);
240         if (stp_port_get_state(p) == STP_FORWARDING && lan) {
241             dump_lan_tree(tc, lan, level + 1);
242         }
243     }
244 }
245
246 static void
247 dump_lan_tree(struct test_case *tc, struct lan *lan, int level)
248 {
249     int i;
250
251     if (lan->reached) {
252         return;
253     }
254     lan->reached = true;
255     for (i = 0; i < level; i++) {
256         printf("\t");
257     }
258     printf("%s\n", lan->name);
259     for (i = 0; i < lan->n_conns; i++) {
260         struct bridge *b = lan->conns[i].bridge;
261         dump_bridge_tree(tc, b, level + 1);
262     }
263 }
264
265 static void
266 tree(struct test_case *tc)
267 {
268     int i;
269
270     for (i = 0; i < tc->n_bridges; i++) {
271         struct bridge *b = tc->bridges[i];
272         b->reached = false;
273     }
274     for (i = 0; i < tc->n_lans; i++) {
275         struct lan *lan = tc->lans[i];
276         lan->reached = false;
277     }
278     for (i = 0; i < tc->n_bridges; i++) {
279         struct bridge *b = tc->bridges[i];
280         struct stp *stp = b->stp;
281         if (stp_is_root_bridge(stp)) {
282             dump_bridge_tree(tc, b, 0);
283         }
284     }
285 }
286
287 static void
288 simulate(struct test_case *tc, int granularity)
289 {
290     int time;
291
292     for (time = 0; time < 1000 * 180; time += granularity) {
293         int round_trips;
294         int i;
295
296         for (i = 0; i < tc->n_bridges; i++) {
297             stp_tick(tc->bridges[i]->stp, granularity);
298         }
299         for (round_trips = 0; round_trips < granularity; round_trips++) {
300             bool any = false;
301             for (i = 0; i < tc->n_bridges; i++) {
302                 struct bridge *b = tc->bridges[i];
303                 for (; b->rxq_tail != b->rxq_head; b->rxq_tail++) {
304                     struct bpdu *bpdu = &b->rxq[b->rxq_tail % RXQ_SIZE];
305                     stp_received_bpdu(stp_get_port(b->stp, bpdu->port_no),
306                                       bpdu->data, bpdu->size);
307                     free(bpdu->data);
308                     any = true;
309                 }
310             }
311             if (!any) {
312                 break;
313             }
314         }
315     }
316 }
317
318 static void
319 err(const char *message, ...)
320     PRINTF_FORMAT(1, 2)
321     NO_RETURN;
322
323 static void
324 err(const char *message, ...)
325 {
326     va_list args;
327
328     fprintf(stderr, "%s:%d:%td: ", file_name, line_number, pos - line);
329     va_start(args, message);
330     vfprintf(stderr, message, args);
331     va_end(args);
332     putc('\n', stderr);
333
334     exit(EXIT_FAILURE);
335 }
336
337 static void
338 warn(const char *message, ...)
339     PRINTF_FORMAT(1, 2);
340
341 static void
342 warn(const char *message, ...)
343 {
344     va_list args;
345
346     fprintf(stderr, "%s:%d: ", file_name, line_number);
347     va_start(args, message);
348     vfprintf(stderr, message, args);
349     va_end(args);
350     putc('\n', stderr);
351
352     n_warnings++;
353 }
354
355 static bool
356 get_token(void)
357 {
358     char *start;
359
360     while (isspace((unsigned char) *pos)) {
361         pos++;
362     }
363     if (*pos == '\0') {
364         free(token);
365         token = NULL;
366         return false;
367     }
368
369     start = pos;
370     if (isalpha((unsigned char) *pos)) {
371         while (isalpha((unsigned char) *++pos)) {
372             continue;
373         }
374     } else if (isdigit((unsigned char) *pos)) {
375         if (*pos == '0' && (pos[1] == 'x' || pos[1] == 'X')) {
376             pos += 2;
377             while (isxdigit((unsigned char) *pos)) {
378                 pos++;
379             }
380         } else {
381             while (isdigit((unsigned char) *++pos)) {
382                 continue;
383             }
384         }
385     } else {
386         pos++;
387     }
388
389     free(token);
390     token = xmemdup0(start, pos - start);
391     return true;
392 }
393
394 static bool
395 get_int(int *intp)
396 {
397     char *save_pos = pos;
398     if (token && isdigit((unsigned char) *token)) {
399         *intp = strtol(token, NULL, 0);
400         get_token();
401         return true;
402     } else {
403         pos = save_pos;
404         return false;
405     }
406 }
407
408 static bool
409 match(const char *want)
410 {
411     if (token && !strcmp(want, token)) {
412         get_token();
413         return true;
414     } else {
415         return false;
416     }
417 }
418
419 static int
420 must_get_int(void)
421 {
422     int x;
423     if (!get_int(&x)) {
424         err("expected integer");
425     }
426     return x;
427 }
428
429 static void
430 must_match(const char *want)
431 {
432     if (!match(want)) {
433         err("expected \"%s\"", want);
434     }
435 }
436
437 int
438 main(int argc, char *argv[])
439 {
440     struct test_case *tc;
441     FILE *input_file;
442     int i;
443
444     vlog_set_pattern(VLF_CONSOLE, "%c|%p|%m");
445     vlog_set_levels(NULL, VLF_SYSLOG, VLL_OFF);
446
447     if (argc != 2) {
448         ovs_fatal(0, "usage: test-stp INPUT.STP\n");
449     }
450     file_name = argv[1];
451
452     input_file = fopen(file_name, "r");
453     if (!input_file) {
454         ovs_fatal(errno, "error opening \"%s\"", file_name);
455     }
456
457     tc = new_test_case();
458     for (i = 0; i < 26; i++) {
459         char name[2];
460         name[0] = 'a' + i;
461         name[1] = '\0';
462         new_lan(tc, name);
463     }
464
465     for (line_number = 1; fgets(line, sizeof line, input_file);
466          line_number++)
467     {
468         char *newline, *hash;
469
470         newline = strchr(line, '\n');
471         if (newline) {
472             *newline = '\0';
473         }
474         hash = strchr(line, '#');
475         if (hash) {
476             *hash = '\0';
477         }
478
479         pos = line;
480         if (!get_token()) {
481             continue;
482         }
483         if (match("bridge")) {
484             struct bridge *bridge;
485             int bridge_no, port_no;
486
487             bridge_no = must_get_int();
488             if (bridge_no < tc->n_bridges) {
489                 bridge = tc->bridges[bridge_no];
490             } else if (bridge_no == tc->n_bridges) {
491                 bridge = new_bridge(tc, must_get_int());
492             } else {
493                 err("bridges must be numbered consecutively from 0");
494             }
495             if (match("^")) {
496                 stp_set_bridge_priority(bridge->stp, must_get_int());
497             }
498
499             if (match("=")) {
500                 for (port_no = 0; port_no < STP_MAX_PORTS; port_no++) {
501                     struct stp_port *p = stp_get_port(bridge->stp, port_no);
502                     if (!token || match("X")) {
503                         stp_port_disable(p);
504                     } else if (match("_")) {
505                         /* Nothing to do. */
506                     } else {
507                         struct lan *lan;
508                         int path_cost;
509
510                         if (!strcmp(token, "0")) {
511                             lan = NULL;
512                         } else if (strlen(token) == 1
513                                 && islower((unsigned char)*token)) {
514                             lan = tc->lans[*token - 'a'];
515                         } else {
516                             err("%s is not a valid LAN name "
517                                 "(0 or a lowercase letter)", token);
518                         }
519                         get_token();
520
521                         path_cost = match(":") ? must_get_int() : 10;
522                         if (port_no < bridge->n_ports) {
523                             stp_port_set_path_cost(p, path_cost);
524                             stp_port_enable(p);
525                             reconnect_port(bridge, port_no, lan);
526                         } else if (port_no == bridge->n_ports) {
527                             new_port(bridge, lan, path_cost);
528                         } else {
529                             err("ports must be numbered consecutively");
530                         }
531                         if (match("^")) {
532                             stp_port_set_priority(p, must_get_int());
533                         }
534                     }
535                 }
536             }
537         } else if (match("run")) {
538             simulate(tc, must_get_int());
539         } else if (match("dump")) {
540             dump(tc);
541         } else if (match("tree")) {
542             tree(tc);
543         } else if (match("check")) {
544             struct bridge *b;
545             struct stp *stp;
546             int bridge_no, port_no;
547
548             bridge_no = must_get_int();
549             if (bridge_no >= tc->n_bridges) {
550                 err("no bridge numbered %d", bridge_no);
551             }
552             b = tc->bridges[bridge_no];
553             stp = b->stp;
554
555             must_match("=");
556
557             if (match("rootid")) {
558                 uint64_t rootid;
559                 must_match(":");
560                 rootid = must_get_int();
561                 if (match("^")) {
562                     rootid |= (uint64_t) must_get_int() << 48;
563                 } else {
564                     rootid |= UINT64_C(0x8000) << 48;
565                 }
566                 if (stp_get_designated_root(stp) != rootid) {
567                     warn("%s: root %"PRIx64", not %"PRIx64,
568                          stp_get_name(stp), stp_get_designated_root(stp),
569                          rootid);
570                 }
571             }
572
573             if (match("root")) {
574                 if (stp_get_root_path_cost(stp)) {
575                     warn("%s: root path cost of root is %u but should be 0",
576                          stp_get_name(stp), stp_get_root_path_cost(stp));
577                 }
578                 if (!stp_is_root_bridge(stp)) {
579                     warn("%s: root is %"PRIx64", not %"PRIx64,
580                          stp_get_name(stp),
581                          stp_get_designated_root(stp), stp_get_bridge_id(stp));
582                 }
583                 for (port_no = 0; port_no < b->n_ports; port_no++) {
584                     struct stp_port *p = stp_get_port(stp, port_no);
585                     enum stp_state state = stp_port_get_state(p);
586                     if (!(state & (STP_DISABLED | STP_FORWARDING))) {
587                         warn("%s: root port %d in state %s",
588                              stp_get_name(b->stp), port_no,
589                              stp_state_name(state));
590                     }
591                 }
592             } else {
593                 for (port_no = 0; port_no < STP_MAX_PORTS; port_no++) {
594                     struct stp_port *p = stp_get_port(stp, port_no);
595                     enum stp_state state;
596                     if (token == NULL || match("D")) {
597                         state = STP_DISABLED;
598                     } else if (match("B")) {
599                         state = STP_BLOCKING;
600                     } else if (match("Li")) {
601                         state = STP_LISTENING;
602                     } else if (match("Le")) {
603                         state = STP_LEARNING;
604                     } else if (match("F")) {
605                         state = STP_FORWARDING;
606                     } else if (match("_")) {
607                         continue;
608                     } else {
609                         err("unknown port state %s", token);
610                     }
611                     if (stp_port_get_state(p) != state) {
612                         warn("%s port %d: state is %s but should be %s",
613                              stp_get_name(stp), port_no,
614                              stp_state_name(stp_port_get_state(p)),
615                              stp_state_name(state));
616                     }
617                     if (state == STP_FORWARDING) {
618                         struct stp_port *root_port = stp_get_root_port(stp);
619                         if (match(":")) {
620                             int root_path_cost = must_get_int();
621                             if (p != root_port) {
622                                 warn("%s: port %d is not the root port",
623                                      stp_get_name(stp), port_no);
624                                 if (!root_port) {
625                                     warn("%s: (there is no root port)",
626                                          stp_get_name(stp));
627                                 } else {
628                                     warn("%s: (port %d is the root port)",
629                                          stp_get_name(stp),
630                                          stp_port_no(root_port));
631                                 }
632                             } else if (root_path_cost
633                                        != stp_get_root_path_cost(stp)) {
634                                 warn("%s: root path cost is %u, should be %d",
635                                      stp_get_name(stp),
636                                      stp_get_root_path_cost(stp),
637                                      root_path_cost);
638                             }
639                         } else if (p == root_port) {
640                             warn("%s: port %d is the root port but "
641                                  "not expected to be",
642                                  stp_get_name(stp), port_no);
643                         }
644                     }
645                 }
646             }
647             if (n_warnings) {
648                 exit(EXIT_FAILURE);
649             }
650         }
651         if (get_token()) {
652             err("trailing garbage on line");
653         }
654     }
655     free(token);
656
657     for (i = 0; i < tc->n_lans; i++) {
658         struct lan *lan = tc->lans[i];
659         free((char *) lan->name);
660         free(lan);
661     }
662     for (i = 0; i < tc->n_bridges; i++) {
663         struct bridge *bridge = tc->bridges[i];
664         stp_destroy(bridge->stp);
665         free(bridge);
666     }
667     free(tc);
668
669     return 0;
670 }