aboutsummaryrefslogtreecommitdiff
path: root/tests
diff options
context:
space:
mode:
Diffstat (limited to 'tests')
-rw-r--r--tests/.gitignore10
-rw-r--r--tests/automake.mk56
-rwxr-xr-xtests/flowgen.pl224
-rw-r--r--tests/test-classifier.c977
-rw-r--r--tests/test-dhcp-client.c189
-rw-r--r--tests/test-flows.c76
-rwxr-xr-xtests/test-flows.sh9
-rw-r--r--tests/test-hash.c155
-rw-r--r--tests/test-hmap.c281
-rw-r--r--tests/test-list.c159
-rw-r--r--tests/test-stp-ieee802.1d-199812
-rw-r--r--tests/test-stp-ieee802.1d-2004-fig17.431
-rw-r--r--tests/test-stp-ieee802.1d-2004-fig17.614
-rw-r--r--tests/test-stp-ieee802.1d-2004-fig17.717
-rw-r--r--tests/test-stp-iol-io-1.125
-rw-r--r--tests/test-stp-iol-io-1.214
-rw-r--r--tests/test-stp-iol-io-1.413
-rw-r--r--tests/test-stp-iol-io-1.540
-rw-r--r--tests/test-stp-iol-op-1.17
-rw-r--r--tests/test-stp-iol-op-1.48
-rw-r--r--tests/test-stp-iol-op-3.111
-rw-r--r--tests/test-stp-iol-op-3.311
-rw-r--r--tests/test-stp-iol-op-3.411
-rw-r--r--tests/test-stp.c648
-rwxr-xr-xtests/test-stp.sh7
-rw-r--r--tests/test-type-props.c41
26 files changed, 3046 insertions, 0 deletions
diff --git a/tests/.gitignore b/tests/.gitignore
new file mode 100644
index 00000000..11125035
--- /dev/null
+++ b/tests/.gitignore
@@ -0,0 +1,10 @@
+/Makefile
+/Makefile.in
+/test-classifier
+/test-dhcp-client
+/test-flows
+/test-hash
+/test-hmap
+/test-list
+/test-stp
+/test-type-props
diff --git a/tests/automake.mk b/tests/automake.mk
new file mode 100644
index 00000000..0508144f
--- /dev/null
+++ b/tests/automake.mk
@@ -0,0 +1,56 @@
+TESTS += tests/test-classifier
+noinst_PROGRAMS += tests/test-classifier
+tests_test_classifier_SOURCES = tests/test-classifier.c
+tests_test_classifier_LDADD = lib/libopenvswitch.a
+
+TESTS += tests/test-flows.sh
+noinst_PROGRAMS += tests/test-flows
+tests_test_flows_SOURCES = tests/test-flows.c
+tests_test_flows_LDADD = lib/libopenvswitch.a
+dist_check_SCRIPTS = tests/test-flows.sh tests/flowgen.pl
+
+TESTS += tests/test-hash
+noinst_PROGRAMS += tests/test-hash
+tests_test_hash_SOURCES = tests/test-hash.c
+tests_test_hash_LDADD = lib/libopenvswitch.a
+
+TESTS += tests/test-hmap
+noinst_PROGRAMS += tests/test-hmap
+tests_test_hmap_SOURCES = tests/test-hmap.c
+tests_test_hmap_LDADD = lib/libopenvswitch.a
+
+TESTS += tests/test-list
+noinst_PROGRAMS += tests/test-list
+tests_test_list_SOURCES = tests/test-list.c
+tests_test_list_LDADD = lib/libopenvswitch.a
+
+TESTS += tests/test-type-props
+noinst_PROGRAMS += tests/test-type-props
+tests_test_type_props_SOURCES = tests/test-type-props.c
+
+noinst_PROGRAMS += tests/test-dhcp-client
+tests_test_dhcp_client_SOURCES = tests/test-dhcp-client.c
+tests_test_dhcp_client_LDADD = lib/libopenvswitch.a $(FAULT_LIBS)
+
+TESTS += tests/test-stp.sh
+EXTRA_DIST += tests/test-stp.sh
+noinst_PROGRAMS += tests/test-stp
+
+tests_test_stp_SOURCES = tests/test-stp.c
+tests_test_stp_LDADD = lib/libopenvswitch.a
+stp_files = \
+ tests/test-stp-ieee802.1d-1998 \
+ tests/test-stp-ieee802.1d-2004-fig17.4 \
+ tests/test-stp-ieee802.1d-2004-fig17.6 \
+ tests/test-stp-ieee802.1d-2004-fig17.7 \
+ tests/test-stp-iol-op-1.1 \
+ tests/test-stp-iol-op-1.4 \
+ tests/test-stp-iol-op-3.1 \
+ tests/test-stp-iol-op-3.3 \
+ tests/test-stp-iol-io-1.1 \
+ tests/test-stp-iol-io-1.2 \
+ tests/test-stp-iol-io-1.4 \
+ tests/test-stp-iol-io-1.5
+TESTS_ENVIRONMENT += stp_files='$(stp_files)'
+
+EXTRA_DIST += $(stp_files)
diff --git a/tests/flowgen.pl b/tests/flowgen.pl
new file mode 100755
index 00000000..6325f1fe
--- /dev/null
+++ b/tests/flowgen.pl
@@ -0,0 +1,224 @@
+#! /usr/bin/perl
+
+use strict;
+use warnings;
+
+open(FLOWS, ">&=3");# or die "failed to open fd 3 for writing: $!\n";
+open(PACKETS, ">&=4");# or die "failed to open fd 4 for writing: $!\n";
+
+# Print pcap file header.
+print PACKETS pack('NnnNNNN',
+ 0xa1b2c3d4, # magic number
+ 2, # major version
+ 4, # minor version
+ 0, # time zone offset
+ 0, # time stamp accuracy
+ 1518, # snaplen
+ 1); # Ethernet
+
+output(DL_HEADER => '802.2');
+
+for my $dl_header qw(802.2+SNAP Ethernet) {
+ my %a = (DL_HEADER => $dl_header);
+ for my $dl_vlan qw(none zero nonzero) {
+ my %b = (%a, DL_VLAN => $dl_vlan);
+
+ # Non-IP case.
+ output(%b, DL_TYPE => 'non-ip');
+
+ for my $ip_options qw(no yes) {
+ my %c = (%b, DL_TYPE => 'ip', IP_OPTIONS => $ip_options);
+ for my $ip_fragment qw(no first middle last) {
+ my %d = (%c, IP_FRAGMENT => $ip_fragment);
+ for my $tp_proto qw(TCP TCP+options UDP ICMP other) {
+ output(%d, TP_PROTO => $tp_proto);
+ }
+ }
+ }
+ }
+}
+
+sub output {
+ my (%attrs) = @_;
+
+ # Compose flow.
+ my (%flow);
+ $flow{DL_SRC} = "00:02:e3:0f:80:a4";
+ $flow{DL_DST} = "00:1a:92:40:ac:05";
+ $flow{NW_PROTO} = 0;
+ $flow{NW_SRC} = '0.0.0.0';
+ $flow{NW_DST} = '0.0.0.0';
+ $flow{TP_SRC} = 0;
+ $flow{TP_DST} = 0;
+ if (defined($attrs{DL_VLAN})) {
+ my (%vlan_map) = ('none' => 0xffff,
+ 'zero' => 0,
+ 'nonzero' => 0x0123);
+ $flow{DL_VLAN} = $vlan_map{$attrs{DL_VLAN}};
+ } else {
+ $flow{DL_VLAN} = 0xffff; # OFP_VLAN_NONE
+ }
+ if ($attrs{DL_HEADER} eq '802.2') {
+ $flow{DL_TYPE} = 0x5ff; # OFP_DL_TYPE_NOT_ETH_TYPE
+ } elsif ($attrs{DL_TYPE} eq 'ip') {
+ $flow{DL_TYPE} = 0x0800; # ETH_TYPE_IP
+ $flow{NW_SRC} = '10.0.2.15';
+ $flow{NW_DST} = '192.168.1.20';
+ if ($attrs{TP_PROTO} eq 'other') {
+ $flow{NW_PROTO} = 42;
+ } elsif ($attrs{TP_PROTO} eq 'TCP' ||
+ $attrs{TP_PROTO} eq 'TCP+options') {
+ $flow{NW_PROTO} = 6; # IP_TYPE_TCP
+ $flow{TP_SRC} = 6667;
+ $flow{TP_DST} = 9998;
+ } elsif ($attrs{TP_PROTO} eq 'UDP') {
+ $flow{NW_PROTO} = 17; # IP_TYPE_UDP
+ $flow{TP_SRC} = 1112;
+ $flow{TP_DST} = 2223;
+ } elsif ($attrs{TP_PROTO} eq 'ICMP') {
+ $flow{NW_PROTO} = 1; # IP_TYPE_ICMP
+ $flow{TP_SRC} = 8; # echo request
+ $flow{TP_DST} = 0; # code
+ } else {
+ die;
+ }
+ if ($attrs{IP_FRAGMENT} ne 'no') {
+ $flow{TP_SRC} = $flow{TP_DST} = 0;
+ }
+ } elsif ($attrs{DL_TYPE} eq 'non-ip') {
+ $flow{DL_TYPE} = 0x5678;
+ } else {
+ die;
+ }
+
+ # Compose packet.
+ my $packet = '';
+ $packet .= pack_ethaddr($flow{DL_DST});
+ $packet .= pack_ethaddr($flow{DL_SRC});
+ $packet .= pack('n', 0) if $attrs{DL_HEADER} =~ /^802.2/;
+ if ($attrs{DL_HEADER} eq '802.2') {
+ $packet .= pack('CCC', 0x42, 0x42, 0x03); # LLC for 802.1D STP.
+ } else {
+ if ($attrs{DL_HEADER} eq '802.2+SNAP') {
+ $packet .= pack('CCC', 0xaa, 0xaa, 0x03); # LLC for SNAP.
+ $packet .= pack('CCC', 0, 0, 0); # SNAP OUI.
+ }
+ if ($attrs{DL_VLAN} ne 'none') {
+ $packet .= pack('nn', 0x8100, $flow{DL_VLAN});
+ }
+ $packet .= pack('n', $flow{DL_TYPE});
+ if ($attrs{DL_TYPE} eq 'ip') {
+ my $ip = pack('CCnnnCCnNN',
+ (4 << 4) | 5, # version, hdrlen
+ 0, # type of service
+ 0, # total length (filled in later)
+ 65432, # id
+ 0, # frag offset
+ 64, # ttl
+ $flow{NW_PROTO}, # protocol
+ 0, # checksum
+ 0x0a00020f, # source
+ 0xc0a80114); # dest
+ if ($attrs{IP_OPTIONS} eq 'yes') {
+ substr($ip, 0, 1) = pack('C', (4 << 4) | 8);
+ $ip .= pack('CCnnnCCCx',
+ 130, # type
+ 11, # length
+ 0x6bc5, # top secret
+ 0xabcd,
+ 0x1234,
+ 1,
+ 2,
+ 3);
+ }
+ if ($attrs{IP_FRAGMENT} ne 'no') {
+ my (%frag_map) = ('first' => 0x2000, # more frags, ofs 0
+ 'middle' => 0x2111, # more frags, ofs 0x888
+ 'last' => 0x0222); # last frag, ofs 0x1110
+ substr($ip, 6, 2)
+ = pack('n', $frag_map{$attrs{IP_FRAGMENT}});
+ }
+
+ if ($attrs{TP_PROTO} =~ '^TCP') {
+ my $tcp = pack('nnNNnnnn',
+ $flow{TP_SRC}, # source port
+ $flow{TP_DST}, # dest port
+ 87123455, # seqno
+ 712378912, # ackno
+ (5 << 12) | 0x02 | 0x10, # hdrlen, SYN, ACK
+ 5823, # window size
+ 18923, # checksum
+ 12893); # urgent pointer
+ if ($attrs{TP_PROTO} eq 'TCP+options') {
+ substr($tcp, 12, 2) = pack('n', (6 << 12) | 0x02 | 0x10);
+ $tcp .= pack('CCn', 2, 4, 1975); # MSS option
+ }
+ $tcp .= 'payload';
+ $ip .= $tcp;
+ } elsif ($attrs{TP_PROTO} eq 'UDP') {
+ my $len = 15;
+ my $udp = pack('nnnn', $flow{TP_SRC}, $flow{TP_DST}, $len, 0);
+ $udp .= chr($len) while length($udp) < $len;
+ $ip .= $udp;
+ } elsif ($attrs{TP_PROTO} eq 'ICMP') {
+ $ip .= pack('CCnnn',
+ 8, # echo request
+ 0, # code
+ 0, # checksum
+ 736, # identifier
+ 931); # sequence number
+ } elsif ($attrs{TP_PROTO} eq 'other') {
+ $ip .= 'other header';
+ } else {
+ die;
+ }
+
+ substr($ip, 2, 2) = pack('n', length($ip));
+ $packet .= $ip;
+ }
+ }
+ substr($packet, 12, 2) = pack('n', length($packet))
+ if $attrs{DL_HEADER} =~ /^802.2/;
+
+ print join(' ', map("$_=$attrs{$_}", keys(%attrs))), "\n";
+ print join(' ', map("$_=$flow{$_}", keys(%flow))), "\n";
+ print "\n";
+
+ print FLOWS pack('Nn',
+ 0, # wildcards
+ 1); # in_port
+ print FLOWS pack_ethaddr($flow{DL_SRC});
+ print FLOWS pack_ethaddr($flow{DL_DST});
+ print FLOWS pack('nnCxNNnn',
+ $flow{DL_VLAN},
+ $flow{DL_TYPE},
+ $flow{NW_PROTO},
+ inet_aton($flow{NW_SRC}),
+ inet_aton($flow{NW_DST}),
+ $flow{TP_SRC},
+ $flow{TP_DST});
+
+ print PACKETS pack('NNNN',
+ 0, # timestamp seconds
+ 0, # timestamp microseconds
+ length($packet), # bytes saved
+ length($packet)), # total length
+ $packet;
+}
+
+sub pack_ethaddr {
+ local ($_) = @_;
+ my $xx = '([0-9a-fA-F][0-9a-fA-F])';
+ my (@octets) = /$xx:$xx:$xx:$xx:$xx:$xx/;
+ @octets == 6 or die $_;
+ my ($out) = '';
+ $out .= pack('C', hex($_)) foreach @octets;
+ return $out;
+}
+
+sub inet_aton {
+ local ($_) = @_;
+ my ($a, $b, $c, $d) = /^(\d+)\.(\d+)\.(\d+)\.(\d+)$/;
+ defined $d or die $_;
+ return ($a << 24) | ($b << 16) | ($c << 8) | $d;
+}
diff --git a/tests/test-classifier.c b/tests/test-classifier.c
new file mode 100644
index 00000000..309c4dd6
--- /dev/null
+++ b/tests/test-classifier.c
@@ -0,0 +1,977 @@
+/*
+ * Copyright (c) 2009 Nicira Networks.
+ *
+ * Permission to use, copy, modify, and/or distribute this software for any
+ * purpose with or without fee is hereby granted, provided that the above
+ * copyright notice and this permission notice appear in all copies.
+ *
+ * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
+ * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
+ * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR
+ * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
+ * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
+ * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
+ * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
+ */
+
+/* "White box" tests for classifier.
+ *
+ * With very few exceptions, these tests obtain complete coverage of every
+ * basic block and every branch in the classifier implementation, e.g. a clean
+ * report from "gcov -b". (Covering the exceptions would require finding
+ * collisions in the hash function used for flow data, etc.)
+ *
+ * This test should receive a clean report from "valgrind --leak-check=full":
+ * it frees every heap block that it allocates.
+ */
+
+#include <config.h>
+#include <limits.h>
+#include "classifier.h"
+#include <errno.h>
+#include <limits.h>
+#include "flow.h"
+#include <limits.h>
+#include "packets.h"
+
+#undef NDEBUG
+#include <assert.h>
+
+struct test_rule {
+ int aux; /* Auxiliary data. */
+ struct cls_rule cls_rule; /* Classifier rule data. */
+};
+
+static struct test_rule *
+test_rule_from_cls_rule(const struct cls_rule *rule)
+{
+ return rule ? CONTAINER_OF(rule, struct test_rule, cls_rule) : NULL;
+}
+
+/* Trivial (linear) classifier. */
+struct tcls {
+ size_t n_rules;
+ size_t allocated_rules;
+ struct test_rule **rules;
+};
+
+static void
+tcls_init(struct tcls *tcls)
+{
+ tcls->n_rules = 0;
+ tcls->allocated_rules = 0;
+ tcls->rules = NULL;
+}
+
+static void
+tcls_destroy(struct tcls *tcls)
+{
+ if (tcls) {
+ size_t i;
+
+ for (i = 0; i < tcls->n_rules; i++) {
+ free(tcls->rules[i]);
+ }
+ free(tcls->rules);
+ }
+}
+
+static int
+tcls_count_exact(const struct tcls *tcls)
+{
+ int n_exact;
+ size_t i;
+
+ n_exact = 0;
+ for (i = 0; i < tcls->n_rules; i++) {
+ n_exact += tcls->rules[i]->cls_rule.wc.wildcards == 0;
+ }
+ return n_exact;
+}
+
+static bool
+tcls_is_empty(const struct tcls *tcls)
+{
+ return tcls->n_rules == 0;
+}
+
+static struct test_rule *
+tcls_insert(struct tcls *tcls, const struct test_rule *rule)
+{
+ size_t i;
+
+ assert(rule->cls_rule.wc.wildcards || rule->cls_rule.priority == UINT_MAX);
+ for (i = 0; i < tcls->n_rules; i++) {
+ const struct cls_rule *pos = &tcls->rules[i]->cls_rule;
+ if (pos->priority == rule->cls_rule.priority
+ && pos->wc.wildcards == rule->cls_rule.wc.wildcards
+ && flow_equal(&pos->flow, &rule->cls_rule.flow)) {
+ /* Exact match.
+ * XXX flow_equal should ignore wildcarded fields */
+ free(tcls->rules[i]);
+ tcls->rules[i] = xmemdup(rule, sizeof *rule);
+ return tcls->rules[i];
+ } else if (pos->priority <= rule->cls_rule.priority) {
+ break;
+ }
+ }
+
+ if (tcls->n_rules >= tcls->allocated_rules) {
+ tcls->rules = x2nrealloc(tcls->rules, &tcls->allocated_rules,
+ sizeof *tcls->rules);
+ }
+ if (i != tcls->n_rules) {
+ memmove(&tcls->rules[i + 1], &tcls->rules[i],
+ sizeof *tcls->rules * (tcls->n_rules - i));
+ }
+ tcls->rules[i] = xmemdup(rule, sizeof *rule);
+ tcls->n_rules++;
+ return tcls->rules[i];
+}
+
+static void
+tcls_remove(struct tcls *cls, const struct test_rule *rule)
+{
+ size_t i;
+
+ for (i = 0; i < cls->n_rules; i++) {
+ struct test_rule *pos = cls->rules[i];
+ if (pos == rule) {
+ free(pos);
+ memmove(&cls->rules[i], &cls->rules[i + 1],
+ sizeof *cls->rules * (cls->n_rules - i - 1));
+ cls->n_rules--;
+ return;
+ }
+ }
+ NOT_REACHED();
+}
+
+static uint32_t
+read_uint32(const void *p)
+{
+ uint32_t x;
+ memcpy(&x, p, sizeof x);
+ return x;
+}
+
+static bool
+match(const struct cls_rule *wild, const flow_t *fixed)
+{
+ int f_idx;
+
+ for (f_idx = 0; f_idx < CLS_N_FIELDS; f_idx++) {
+ const struct cls_field *f = &cls_fields[f_idx];
+ void *wild_field = (char *) &wild->flow + f->ofs;
+ void *fixed_field = (char *) fixed + f->ofs;
+
+ if ((wild->wc.wildcards & f->wildcards) == f->wildcards ||
+ !memcmp(wild_field, fixed_field, f->len)) {
+ /* Definite match. */
+ continue;
+ }
+
+ if (wild->wc.wildcards & f->wildcards) {
+ uint32_t test = read_uint32(wild_field);
+ uint32_t ip = read_uint32(fixed_field);
+ int shift = (f_idx == CLS_F_IDX_NW_SRC
+ ? OFPFW_NW_SRC_SHIFT : OFPFW_NW_DST_SHIFT);
+ uint32_t mask = flow_nw_bits_to_mask(wild->wc.wildcards, shift);
+ if (!((test ^ ip) & mask)) {
+ continue;
+ }
+ }
+
+ return false;
+ }
+ return true;
+}
+
+static struct cls_rule *
+tcls_lookup(const struct tcls *cls, const flow_t *flow, int include)
+{
+ size_t i;
+
+ for (i = 0; i < cls->n_rules; i++) {
+ struct test_rule *pos = cls->rules[i];
+ uint32_t wildcards = pos->cls_rule.wc.wildcards;
+ if (include & (wildcards ? CLS_INC_WILD : CLS_INC_EXACT)
+ && match(&pos->cls_rule, flow)) {
+ return &pos->cls_rule;
+ }
+ }
+ return NULL;
+}
+
+static void
+tcls_delete_matches(struct tcls *cls,
+ const struct cls_rule *target,
+ int include)
+{
+ size_t i;
+
+ for (i = 0; i < cls->n_rules; ) {
+ struct test_rule *pos = cls->rules[i];
+ uint32_t wildcards = pos->cls_rule.wc.wildcards;
+ if (include & (wildcards ? CLS_INC_WILD : CLS_INC_EXACT)
+ && match(target, &pos->cls_rule.flow)) {
+ tcls_remove(cls, pos);
+ } else {
+ i++;
+ }
+ }
+}
+
+#ifdef WORDS_BIGENDIAN
+#define HTONL(VALUE) ((uint32_t) (VALUE))
+#define HTONS(VALUE) ((uint32_t) (VALUE))
+#else
+#define HTONL(VALUE) (((((uint32_t) (VALUE)) & 0x000000ff) << 24) | \
+ ((((uint32_t) (VALUE)) & 0x0000ff00) << 8) | \
+ ((((uint32_t) (VALUE)) & 0x00ff0000) >> 8) | \
+ ((((uint32_t) (VALUE)) & 0xff000000) >> 24))
+#define HTONS(VALUE) (((((uint16_t) (VALUE)) & 0xff00) >> 8) | \
+ ((((uint16_t) (VALUE)) & 0x00ff) << 8))
+#endif
+
+static uint32_t nw_src_values[] = { HTONL(0xc0a80001),
+ HTONL(0xc0a04455) };
+static uint32_t nw_dst_values[] = { HTONL(0xc0a80002),
+ HTONL(0xc0a04455) };
+static uint16_t in_port_values[] = { HTONS(1), HTONS(OFPP_LOCAL) };
+static uint16_t dl_vlan_values[] = { HTONS(101), HTONS(0) };
+static uint16_t dl_type_values[] = { HTONS(ETH_TYPE_IP), HTONS(ETH_TYPE_ARP) };
+static uint16_t tp_src_values[] = { HTONS(49362), HTONS(80) };
+static uint16_t tp_dst_values[] = { HTONS(6667), HTONS(22) };
+static uint8_t dl_src_values[][6] = { { 0x00, 0x02, 0xe3, 0x0f, 0x80, 0xa4 },
+ { 0x5e, 0x33, 0x7f, 0x5f, 0x1e, 0x99 } };
+static uint8_t dl_dst_values[][6] = { { 0x4a, 0x27, 0x71, 0xae, 0x64, 0xc1 },
+ { 0xff, 0xff, 0xff, 0xff, 0xff, 0xff } };
+static uint8_t nw_proto_values[] = { IP_TYPE_TCP, IP_TYPE_ICMP };
+
+static void *values[CLS_N_FIELDS][2];
+
+static void
+init_values(void)
+{
+ values[CLS_F_IDX_IN_PORT][0] = &in_port_values[0];
+ values[CLS_F_IDX_IN_PORT][1] = &in_port_values[1];
+
+ values[CLS_F_IDX_DL_VLAN][0] = &dl_vlan_values[0];
+ values[CLS_F_IDX_DL_VLAN][1] = &dl_vlan_values[1];
+
+ values[CLS_F_IDX_DL_SRC][0] = dl_src_values[0];
+ values[CLS_F_IDX_DL_SRC][1] = dl_src_values[1];
+
+ values[CLS_F_IDX_DL_DST][0] = dl_dst_values[0];
+ values[CLS_F_IDX_DL_DST][1] = dl_dst_values[1];
+
+ values[CLS_F_IDX_DL_TYPE][0] = &dl_type_values[0];
+ values[CLS_F_IDX_DL_TYPE][1] = &dl_type_values[1];
+
+ values[CLS_F_IDX_NW_SRC][0] = &nw_src_values[0];
+ values[CLS_F_IDX_NW_SRC][1] = &nw_src_values[1];
+
+ values[CLS_F_IDX_NW_DST][0] = &nw_dst_values[0];
+ values[CLS_F_IDX_NW_DST][1] = &nw_dst_values[1];
+
+ values[CLS_F_IDX_NW_PROTO][0] = &nw_proto_values[0];
+ values[CLS_F_IDX_NW_PROTO][1] = &nw_proto_values[1];
+
+ values[CLS_F_IDX_TP_SRC][0] = &tp_src_values[0];
+ values[CLS_F_IDX_TP_SRC][1] = &tp_src_values[1];
+
+ values[CLS_F_IDX_TP_DST][0] = &tp_dst_values[0];
+ values[CLS_F_IDX_TP_DST][1] = &tp_dst_values[1];
+}
+
+#define N_NW_SRC_VALUES ARRAY_SIZE(nw_src_values)
+#define N_NW_DST_VALUES ARRAY_SIZE(nw_dst_values)
+#define N_IN_PORT_VALUES ARRAY_SIZE(in_port_values)
+#define N_DL_VLAN_VALUES ARRAY_SIZE(dl_vlan_values)
+#define N_DL_TYPE_VALUES ARRAY_SIZE(dl_type_values)
+#define N_TP_SRC_VALUES ARRAY_SIZE(tp_src_values)
+#define N_TP_DST_VALUES ARRAY_SIZE(tp_dst_values)
+#define N_DL_SRC_VALUES ARRAY_SIZE(dl_src_values)
+#define N_DL_DST_VALUES ARRAY_SIZE(dl_dst_values)
+#define N_NW_PROTO_VALUES ARRAY_SIZE(nw_proto_values)
+
+#define N_FLOW_VALUES (N_NW_SRC_VALUES * \
+ N_NW_DST_VALUES * \
+ N_IN_PORT_VALUES * \
+ N_DL_VLAN_VALUES * \
+ N_DL_TYPE_VALUES * \
+ N_TP_SRC_VALUES * \
+ N_TP_DST_VALUES * \
+ N_DL_SRC_VALUES * \
+ N_DL_DST_VALUES * \
+ N_NW_PROTO_VALUES)
+
+static unsigned int
+get_value(unsigned int *x, unsigned n_values)
+{
+ unsigned int rem = *x % n_values;
+ *x /= n_values;
+ return rem;
+}
+
+static struct cls_rule *
+lookup_with_include_bits(const struct classifier *cls,
+ const flow_t *flow, int include)
+{
+ switch (include) {
+ case CLS_INC_WILD:
+ return classifier_lookup_wild(cls, flow);
+ case CLS_INC_EXACT:
+ return classifier_lookup_exact(cls, flow);
+ case CLS_INC_WILD | CLS_INC_EXACT:
+ return classifier_lookup(cls, flow);
+ default:
+ abort();
+ }
+}
+
+static void
+compare_classifiers(struct classifier *cls, struct tcls *tcls)
+{
+ unsigned int i;
+
+ assert(classifier_count(cls) == tcls->n_rules);
+ assert(classifier_count_exact(cls) == tcls_count_exact(tcls));
+ for (i = 0; i < N_FLOW_VALUES; i++) {
+ struct cls_rule *cr0, *cr1;
+ flow_t flow;
+ unsigned int x;
+ int include;
+
+ x = i;
+ flow.nw_src = nw_src_values[get_value(&x, N_NW_SRC_VALUES)];
+ flow.nw_dst = nw_dst_values[get_value(&x, N_NW_DST_VALUES)];
+ flow.in_port = in_port_values[get_value(&x, N_IN_PORT_VALUES)];
+ flow.dl_vlan = dl_vlan_values[get_value(&x, N_DL_VLAN_VALUES)];
+ flow.dl_type = dl_type_values[get_value(&x, N_DL_TYPE_VALUES)];
+ flow.tp_src = tp_src_values[get_value(&x, N_TP_SRC_VALUES)];
+ flow.tp_dst = tp_dst_values[get_value(&x, N_TP_DST_VALUES)];
+ memcpy(flow.dl_src, dl_src_values[get_value(&x, N_DL_SRC_VALUES)],
+ ETH_ADDR_LEN);
+ memcpy(flow.dl_dst, dl_dst_values[get_value(&x, N_DL_DST_VALUES)],
+ ETH_ADDR_LEN);
+ flow.nw_proto = nw_proto_values[get_value(&x, N_NW_PROTO_VALUES)];
+ flow.reserved = 0;
+
+ for (include = 1; include <= 3; include++) {
+ cr0 = lookup_with_include_bits(cls, &flow, include);
+ cr1 = tcls_lookup(tcls, &flow, include);
+ assert((cr0 == NULL) == (cr1 == NULL));
+ if (cr0 != NULL) {
+ const struct test_rule *tr0 = test_rule_from_cls_rule(cr0);
+ const struct test_rule *tr1 = test_rule_from_cls_rule(cr1);
+
+ assert(flow_equal(&cr0->flow, &cr1->flow));
+ assert(cr0->wc.wildcards == cr1->wc.wildcards);
+ assert(cr0->priority == cr1->priority);
+ /* Skip nw_src_mask and nw_dst_mask, because they are derived
+ * members whose values are used only for optimization. */
+ assert(tr0->aux == tr1->aux);
+ }
+ }
+ }
+}
+
+static void
+free_rule(struct cls_rule *cls_rule, void *cls)
+{
+ classifier_remove(cls, cls_rule);
+ free(test_rule_from_cls_rule(cls_rule));
+}
+
+static void
+destroy_classifier(struct classifier *cls)
+{
+ classifier_for_each(cls, CLS_INC_ALL, free_rule, cls);
+ classifier_destroy(cls);
+}
+
+static void
+check_tables(const struct classifier *cls,
+ int n_tables, int n_buckets, int n_rules)
+{
+ int found_tables = 0;
+ int found_buckets = 0;
+ int found_rules = 0;
+ int i;
+
+ BUILD_ASSERT(CLS_N_FIELDS == ARRAY_SIZE(cls->tables));
+ for (i = 0; i < CLS_N_FIELDS; i++) {
+ const struct cls_bucket *bucket;
+ if (!hmap_is_empty(&cls->tables[i])) {
+ found_tables++;
+ }
+ HMAP_FOR_EACH (bucket, struct cls_bucket, hmap_node, &cls->tables[i]) {
+ found_buckets++;
+ assert(!list_is_empty(&bucket->rules));
+ found_rules += list_size(&bucket->rules);
+ }
+ }
+
+ if (!hmap_is_empty(&cls->exact_table)) {
+ found_tables++;
+ found_buckets++;
+ found_rules += hmap_count(&cls->exact_table);
+ }
+
+ assert(n_tables == -1 || found_tables == n_tables);
+ assert(n_rules == -1 || found_rules == n_rules);
+ assert(n_buckets == -1 || found_buckets == n_buckets);
+}
+
+static struct test_rule *
+make_rule(int wc_fields, unsigned int priority, int value_pat)
+{
+ const struct cls_field *f;
+ struct test_rule *rule;
+ uint32_t wildcards;
+ flow_t flow;
+
+ wildcards = 0;
+ memset(&flow, 0, sizeof flow);
+ for (f = &cls_fields[0]; f < &cls_fields[CLS_N_FIELDS]; f++) {
+ int f_idx = f - cls_fields;
+ if (wc_fields & (1u << f_idx)) {
+ wildcards |= f->wildcards;
+ } else {
+ int value_idx = (value_pat & (1u << f_idx)) != 0;
+ memcpy((char *) &flow + f->ofs, values[f_idx][value_idx], f->len);
+ }
+ }
+
+ rule = xcalloc(1, sizeof *rule);
+ cls_rule_from_flow(&rule->cls_rule, &flow, wildcards,
+ !wildcards ? UINT_MAX : priority);
+ return rule;
+}
+
+static void
+shuffle(unsigned int *p, size_t n)
+{
+ for (; n > 1; n--, p++) {
+ unsigned int *q = &p[rand() % n];
+ unsigned int tmp = *p;
+ *p = *q;
+ *q = tmp;
+ }
+}
+
+/* Tests an empty classifier. */
+static void
+test_empty(void)
+{
+ struct classifier cls;
+ struct tcls tcls;
+
+ classifier_init(&cls);
+ tcls_init(&tcls);
+ assert(classifier_is_empty(&cls));
+ assert(tcls_is_empty(&tcls));
+ compare_classifiers(&cls, &tcls);
+ classifier_destroy(&cls);
+ tcls_destroy(&tcls);
+}
+
+/* Destroys a null classifier. */
+static void
+test_destroy_null(void)
+{
+ classifier_destroy(NULL);
+}
+
+/* Tests classification with one rule at a time. */
+static void
+test_single_rule(void)
+{
+ unsigned int wc_fields; /* Hilarious. */
+
+ for (wc_fields = 0; wc_fields < (1u << CLS_N_FIELDS); wc_fields++) {
+ struct classifier cls;
+ struct test_rule *rule, *tcls_rule;
+ struct tcls tcls;
+
+ rule = make_rule(wc_fields,
+ hash_bytes(&wc_fields, sizeof wc_fields, 0), 0);
+
+ classifier_init(&cls);
+ tcls_init(&tcls);
+
+ tcls_rule = tcls_insert(&tcls, rule);
+ if (wc_fields) {
+ assert(!classifier_insert(&cls, &rule->cls_rule));
+ } else {
+ classifier_insert_exact(&cls, &rule->cls_rule);
+ }
+ check_tables(&cls, 1, 1, 1);
+ compare_classifiers(&cls, &tcls);
+
+ classifier_remove(&cls, &rule->cls_rule);
+ tcls_remove(&tcls, tcls_rule);
+ assert(classifier_is_empty(&cls));
+ assert(tcls_is_empty(&tcls));
+ compare_classifiers(&cls, &tcls);
+
+ free(rule);
+ classifier_destroy(&cls);
+ tcls_destroy(&tcls);
+ }
+}
+
+/* Tests replacing one rule by another. */
+static void
+test_rule_replacement(void)
+{
+ unsigned int wc_fields;
+
+ for (wc_fields = 0; wc_fields < (1u << CLS_N_FIELDS); wc_fields++) {
+ struct classifier cls;
+ struct test_rule *rule1, *tcls_rule1;
+ struct test_rule *rule2, *tcls_rule2;
+ struct tcls tcls;
+
+ rule1 = make_rule(wc_fields, OFP_DEFAULT_PRIORITY, UINT_MAX);
+ rule2 = make_rule(wc_fields, OFP_DEFAULT_PRIORITY, UINT_MAX);
+ rule2->aux += 5;
+ rule2->aux += 5;
+
+ classifier_init(&cls);
+ tcls_init(&tcls);
+ tcls_rule1 = tcls_insert(&tcls, rule1);
+ assert(!classifier_insert(&cls, &rule1->cls_rule));
+ check_tables(&cls, 1, 1, 1);
+ compare_classifiers(&cls, &tcls);
+ tcls_destroy(&tcls);
+
+ tcls_init(&tcls);
+ tcls_rule2 = tcls_insert(&tcls, rule2);
+ assert(test_rule_from_cls_rule(
+ classifier_insert(&cls, &rule2->cls_rule)) == rule1);
+ free(rule1);
+ check_tables(&cls, 1, 1, 1);
+ compare_classifiers(&cls, &tcls);
+ tcls_destroy(&tcls);
+ destroy_classifier(&cls);
+ }
+}
+
+static int
+table_mask(int table)
+{
+ return ((1u << CLS_N_FIELDS) - 1) & ~((1u << table) - 1);
+}
+
+static int
+random_wcf_in_table(int table, int seed)
+{
+ int wc_fields = (1u << table) | hash_int(seed, 0);
+ return wc_fields & table_mask(table);
+}
+
+/* Tests classification with two rules at a time that fall into the same
+ * bucket. */
+static void
+test_two_rules_in_one_bucket(void)
+{
+ int table, rel_pri, wcf_pat, value_pat;
+
+ for (table = 0; table <= CLS_N_FIELDS; table++) {
+ for (rel_pri = -1; rel_pri <= +1; rel_pri++) {
+ for (wcf_pat = 0; wcf_pat < 4; wcf_pat++) {
+ int n_value_pats = table == CLS_N_FIELDS - 1 ? 1 : 2;
+ for (value_pat = 0; value_pat < n_value_pats; value_pat++) {
+ struct test_rule *rule1, *tcls_rule1;
+ struct test_rule *rule2, *tcls_rule2;
+ struct test_rule *displaced_rule;
+ struct classifier cls;
+ struct tcls tcls;
+ unsigned int pri1, pri2;
+ int wcf1, wcf2;
+
+ if (table != CLS_F_IDX_EXACT) {
+ /* We can use identical priorities in this test because
+ * the classifier always chooses the rule added later
+ * for equal-priority rules that fall into the same
+ * bucket. */
+ pri1 = table * 257 + 50;
+ pri2 = pri1 + rel_pri;
+
+ wcf1 = (wcf_pat & 1
+ ? random_wcf_in_table(table, pri1)
+ : 1u << table);
+ wcf2 = (wcf_pat & 2
+ ? random_wcf_in_table(table, pri2)
+ : 1u << table);
+ if (value_pat) {
+ wcf1 &= ~(1u << (CLS_N_FIELDS - 1));
+ wcf2 &= ~(1u << (CLS_N_FIELDS - 1));
+ }
+ } else {
+ /* This classifier always puts exact-match rules at
+ * maximum priority. */
+ pri1 = pri2 = UINT_MAX;
+
+ /* No wildcard fields. */
+ wcf1 = wcf2 = 0;
+ }
+
+ rule1 = make_rule(wcf1, pri1, 0);
+ rule2 = make_rule(wcf2, pri2,
+ value_pat << (CLS_N_FIELDS - 1));
+
+ classifier_init(&cls);
+ tcls_init(&tcls);
+
+ tcls_rule1 = tcls_insert(&tcls, rule1);
+ tcls_rule2 = tcls_insert(&tcls, rule2);
+ assert(!classifier_insert(&cls, &rule1->cls_rule));
+ displaced_rule = test_rule_from_cls_rule(
+ classifier_insert(&cls, &rule2->cls_rule));
+ if (wcf1 != wcf2 || pri1 != pri2 || value_pat) {
+ assert(!displaced_rule);
+
+ check_tables(&cls, 1, 1, 2);
+ compare_classifiers(&cls, &tcls);
+
+ classifier_remove(&cls, &rule1->cls_rule);
+ tcls_remove(&tcls, tcls_rule1);
+ check_tables(&cls, 1, 1, 1);
+ compare_classifiers(&cls, &tcls);
+ } else {
+ assert(displaced_rule == rule1);
+ check_tables(&cls, 1, 1, 1);
+ compare_classifiers(&cls, &tcls);
+ }
+ free(rule1);
+
+ classifier_remove(&cls, &rule2->cls_rule);
+ tcls_remove(&tcls, tcls_rule2);
+ compare_classifiers(&cls, &tcls);
+ free(rule2);
+
+ destroy_classifier(&cls);
+ tcls_destroy(&tcls);
+ }
+ }
+ }
+ }
+}
+
+/* Tests classification with two rules at a time that fall into the same
+ * table but different buckets. */
+static void
+test_two_rules_in_one_table(void)
+{
+ int table, rel_pri, wcf_pat;
+
+ /* Skip tables 0 and CLS_F_IDX_EXACT because they have one bucket. */
+ for (table = 1; table < CLS_N_FIELDS; table++) {
+ for (rel_pri = -1; rel_pri <= +1; rel_pri++) {
+ for (wcf_pat = 0; wcf_pat < 5; wcf_pat++) {
+ struct test_rule *rule1, *tcls_rule1;
+ struct test_rule *rule2, *tcls_rule2;
+ struct classifier cls;
+ struct tcls tcls;
+ unsigned int pri1, pri2;
+ int wcf1, wcf2;
+ int value_mask, value_pat1, value_pat2;
+ int i;
+
+ /* We can use identical priorities in this test because the
+ * classifier always chooses the rule added later for
+ * equal-priority rules that fall into the same table. */
+ pri1 = table * 257 + 50;
+ pri2 = pri1 + rel_pri;
+
+ if (wcf_pat & 4) {
+ wcf1 = wcf2 = random_wcf_in_table(table, pri1);
+ } else {
+ wcf1 = (wcf_pat & 1
+ ? random_wcf_in_table(table, pri1)
+ : 1u << table);
+ wcf2 = (wcf_pat & 2
+ ? random_wcf_in_table(table, pri2)
+ : 1u << table);
+ }
+
+ /* Generate value patterns that will put the two rules into
+ * different buckets. */
+ value_mask = ((1u << table) - 1);
+ value_pat1 = hash_int(pri1, 1) & value_mask;
+ i = 0;
+ do {
+ value_pat2 = (hash_int(pri2, i++) & value_mask);
+ } while (value_pat1 == value_pat2);
+ rule1 = make_rule(wcf1, pri1, value_pat1);
+ rule2 = make_rule(wcf2, pri2, value_pat2);
+
+ classifier_init(&cls);
+ tcls_init(&tcls);
+
+ tcls_rule1 = tcls_insert(&tcls, rule1);
+ tcls_rule2 = tcls_insert(&tcls, rule2);
+ assert(!classifier_insert(&cls, &rule1->cls_rule));
+ assert(!classifier_insert(&cls, &rule2->cls_rule));
+ check_tables(&cls, 1, 2, 2);
+ compare_classifiers(&cls, &tcls);
+
+ classifier_remove(&cls, &rule1->cls_rule);
+ tcls_remove(&tcls, tcls_rule1);
+ check_tables(&cls, 1, 1, 1);
+ compare_classifiers(&cls, &tcls);
+ free(rule1);
+
+ classifier_remove(&cls, &rule2->cls_rule);
+ tcls_remove(&tcls, tcls_rule2);
+ compare_classifiers(&cls, &tcls);
+ free(rule2);
+
+ classifier_destroy(&cls);
+ tcls_destroy(&tcls);
+ }
+ }
+ }
+}
+
+/* Tests classification with two rules at a time that fall into different
+ * tables. */
+static void
+test_two_rules_in_different_tables(void)
+{
+ int table1, table2, rel_pri, wcf_pat;
+
+ for (table1 = 0; table1 < CLS_N_FIELDS; table1++) {
+ for (table2 = table1 + 1; table2 <= CLS_N_FIELDS; table2++) {
+ for (rel_pri = 0; rel_pri < 2; rel_pri++) {
+ for (wcf_pat = 0; wcf_pat < 4; wcf_pat++) {
+ struct test_rule *rule1, *tcls_rule1;
+ struct test_rule *rule2, *tcls_rule2;
+ struct classifier cls;
+ struct tcls tcls;
+ unsigned int pri1, pri2;
+ int wcf1, wcf2;
+
+ /* We must use unique priorities in this test because the
+ * classifier makes the rule choice undefined for rules of
+ * equal priority that fall into different tables. (In
+ * practice, lower-numbered tables win.) */
+ pri1 = table1 * 257 + 50;
+ pri2 = rel_pri ? pri1 - 1 : pri1 + 1;
+
+ wcf1 = (wcf_pat & 1
+ ? random_wcf_in_table(table1, pri1)
+ : 1u << table1);
+ wcf2 = (wcf_pat & 2
+ ? random_wcf_in_table(table2, pri2)
+ : 1u << table2);
+
+ if (table2 == CLS_F_IDX_EXACT) {
+ pri2 = UINT16_MAX;
+ wcf2 = 0;
+ }
+
+ rule1 = make_rule(wcf1, pri1, 0);
+ rule2 = make_rule(wcf2, pri2, 0);
+
+ classifier_init(&cls);
+ tcls_init(&tcls);
+
+ tcls_rule1 = tcls_insert(&tcls, rule1);
+ tcls_rule2 = tcls_insert(&tcls, rule2);
+ assert(!classifier_insert(&cls, &rule1->cls_rule));
+ assert(!classifier_insert(&cls, &rule2->cls_rule));
+ check_tables(&cls, 2, 2, 2);
+ compare_classifiers(&cls, &tcls);
+
+ classifier_remove(&cls, &rule1->cls_rule);
+ tcls_remove(&tcls, tcls_rule1);
+ check_tables(&cls, 1, 1, 1);
+ compare_classifiers(&cls, &tcls);
+ free(rule1);
+
+ classifier_remove(&cls, &rule2->cls_rule);
+ tcls_remove(&tcls, tcls_rule2);
+ compare_classifiers(&cls, &tcls);
+ free(rule2);
+
+ classifier_destroy(&cls);
+ tcls_destroy(&tcls);
+ }
+ }
+ }
+ }
+}
+
+/* Tests classification with many rules at a time that fall into the same
+ * bucket but have unique priorities (and various wildcards). */
+static void
+test_many_rules_in_one_bucket(void)
+{
+ enum { MAX_RULES = 50 };
+ int iteration, table;
+
+ for (iteration = 0; iteration < 3; iteration++) {
+ for (table = 0; table <= CLS_N_FIELDS; table++) {
+ unsigned int priorities[MAX_RULES];
+ struct classifier cls;
+ struct tcls tcls;
+ int i;
+
+ srand(hash_int(table, iteration));
+ for (i = 0; i < MAX_RULES; i++) {
+ priorities[i] = i * 129;
+ }
+ shuffle(priorities, ARRAY_SIZE(priorities));
+
+ classifier_init(&cls);
+ tcls_init(&tcls);
+
+ for (i = 0; i < MAX_RULES; i++) {
+ struct test_rule *rule;
+ unsigned int priority = priorities[i];
+ int wcf;
+
+ wcf = random_wcf_in_table(table, priority);
+ rule = make_rule(wcf, priority,
+ table == CLS_F_IDX_EXACT ? i : 1234);
+ tcls_insert(&tcls, rule);
+ assert(!classifier_insert(&cls, &rule->cls_rule));
+ check_tables(&cls, 1, 1, i + 1);
+ compare_classifiers(&cls, &tcls);
+ }
+
+ destroy_classifier(&cls);
+ tcls_destroy(&tcls);
+ }
+ }
+}
+
+/* Tests classification with many rules at a time that fall into the same
+ * table but random buckets. */
+static void
+test_many_rules_in_one_table(void)
+{
+ enum { MAX_RULES = 50 };
+ int iteration, table;
+
+ for (iteration = 0; iteration < 3; iteration++) {
+ for (table = 0; table < CLS_N_FIELDS; table++) {
+ unsigned int priorities[MAX_RULES];
+ struct classifier cls;
+ struct tcls tcls;
+ int i;
+
+ srand(hash_int(table, iteration));
+ for (i = 0; i < MAX_RULES; i++) {
+ priorities[i] = i * 129;
+ }
+ shuffle(priorities, ARRAY_SIZE(priorities));
+
+ classifier_init(&cls);
+ tcls_init(&tcls);
+
+ for (i = 0; i < MAX_RULES; i++) {
+ struct test_rule *rule;
+ unsigned int priority = priorities[i];
+ int wcf;
+
+ wcf = random_wcf_in_table(table, priority);
+ rule = make_rule(wcf, priority, hash_int(priority, 1));
+ tcls_insert(&tcls, rule);
+ assert(!classifier_insert(&cls, &rule->cls_rule));
+ check_tables(&cls, 1, -1, i + 1);
+ compare_classifiers(&cls, &tcls);
+ }
+
+ destroy_classifier(&cls);
+ tcls_destroy(&tcls);
+ }
+ }
+}
+
+/* Tests classification with many rules at a time that fall into random buckets
+ * in random tables. */
+static void
+test_many_rules_in_different_tables(void)
+{
+ enum { MAX_RULES = 50 };
+ int iteration;
+
+ for (iteration = 0; iteration < 30; iteration++) {
+ unsigned int priorities[MAX_RULES];
+ struct classifier cls;
+ struct tcls tcls;
+ int i;
+
+ srand(iteration);
+ for (i = 0; i < MAX_RULES; i++) {
+ priorities[i] = i * 129;
+ }
+ shuffle(priorities, ARRAY_SIZE(priorities));
+
+ classifier_init(&cls);
+ tcls_init(&tcls);
+
+ for (i = 0; i < MAX_RULES; i++) {
+ struct test_rule *rule;
+ unsigned int priority = priorities[i];
+ int table = rand() % (CLS_N_FIELDS + 1);
+ int wcf = random_wcf_in_table(table, rand());
+ int value_pat = rand() & ((1u << CLS_N_FIELDS) - 1);
+ rule = make_rule(wcf, priority, value_pat);
+ tcls_insert(&tcls, rule);
+ assert(!classifier_insert(&cls, &rule->cls_rule));
+ check_tables(&cls, -1, -1, i + 1);
+ compare_classifiers(&cls, &tcls);
+ }
+
+ while (!classifier_is_empty(&cls)) {
+ struct test_rule *rule = xmemdup(tcls.rules[rand() % tcls.n_rules],
+ sizeof(struct test_rule));
+ int include = rand() % 2 ? CLS_INC_WILD : CLS_INC_EXACT;
+ include |= (rule->cls_rule.wc.wildcards
+ ? CLS_INC_WILD : CLS_INC_EXACT);
+ classifier_for_each_match(&cls, &rule->cls_rule, include,
+ free_rule, &cls);
+ tcls_delete_matches(&tcls, &rule->cls_rule, include);
+ compare_classifiers(&cls, &tcls);
+ free(rule);
+ }
+ putchar('.');
+ fflush(stdout);
+
+ destroy_classifier(&cls);
+ tcls_destroy(&tcls);
+ }
+}
+
+static void
+run_test(void (*function)(void))
+{
+ function();
+ putchar('.');
+ fflush(stdout);
+}
+
+int
+main(void)
+{
+ init_values();
+ run_test(test_empty);
+ run_test(test_destroy_null);
+ run_test(test_single_rule);
+ run_test(test_rule_replacement);
+ run_test(test_two_rules_in_one_bucket);
+ run_test(test_two_rules_in_one_table);
+ run_test(test_two_rules_in_different_tables);
+ run_test(test_many_rules_in_one_bucket);
+ run_test(test_many_rules_in_one_table);
+ run_test(test_many_rules_in_different_tables);
+ putchar('\n');
+ return 0;
+}
diff --git a/tests/test-dhcp-client.c b/tests/test-dhcp-client.c
new file mode 100644
index 00000000..2fee3fc1
--- /dev/null
+++ b/tests/test-dhcp-client.c
@@ -0,0 +1,189 @@
+/*
+ * Copyright (c) 2008, 2009 Nicira Networks.
+ *
+ * Permission to use, copy, modify, and/or distribute this software for any
+ * purpose with or without fee is hereby granted, provided that the above
+ * copyright notice and this permission notice appear in all copies.
+ *
+ * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
+ * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
+ * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR
+ * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
+ * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
+ * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
+ * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
+ */
+
+#include <config.h>
+#include "dhcp-client.h"
+#include <arpa/inet.h>
+#include <getopt.h>
+#include <stdlib.h>
+#include <limits.h>
+#include "command-line.h"
+#include "dhcp.h"
+#include "fatal-signal.h"
+#include "fault.h"
+#include "poll-loop.h"
+#include "util.h"
+#include "vlog.h"
+
+/* --request-ip: IP address to request from server. If zero, then do not
+ * request a specific IP address. */
+static struct in_addr request_ip;
+
+/* --vendor-class: Vendor class string to include in request. If null, no
+ * vendor class string is included. */
+static const char *vendor_class;
+
+/* --no-resolv-conf: Update /etc/resolv.conf to match DHCP reply? */
+static bool update_resolv_conf = true;
+
+static void parse_options(int argc, char *argv[]);
+static void usage(void);
+static void release(void *cli_);
+static void modify_dhcp_request(struct dhcp_msg *, void *aux);
+
+int
+main(int argc, char *argv[])
+{
+ struct dhclient *cli;
+ int error;
+
+ set_program_name(argv[0]);
+ register_fault_handlers();
+ vlog_init();
+ parse_options(argc, argv);
+
+ argc -= optind;
+ argv += optind;
+ if (argc != 1) {
+ ovs_fatal(0, "exactly one non-option argument required; "
+ "use --help for help");
+ }
+
+ error = dhclient_create(argv[0], modify_dhcp_request, NULL, NULL, &cli);
+ if (error) {
+ ovs_fatal(error, "dhclient_create failed");
+ }
+ dhclient_init(cli, request_ip.s_addr);
+ fatal_signal_add_hook(release, cli, true);
+
+ for (;;) {
+ fatal_signal_block();
+ dhclient_run(cli);
+ if (dhclient_changed(cli)) {
+ dhclient_configure_netdev(cli);
+ if (update_resolv_conf) {
+ dhclient_update_resolv_conf(cli);
+ }
+ }
+ dhclient_wait(cli);
+ fatal_signal_unblock();
+ poll_block();
+ }
+}
+
+static void
+release(void *cli_)
+{
+ struct dhclient *cli = cli_;
+ dhclient_release(cli);
+ if (dhclient_changed(cli)) {
+ dhclient_configure_netdev(cli);
+ }
+}
+
+static void
+modify_dhcp_request(struct dhcp_msg *msg, void *aux UNUSED)
+{
+ if (vendor_class) {
+ dhcp_msg_put_string(msg, DHCP_CODE_VENDOR_CLASS, vendor_class);
+ }
+}
+
+static void
+parse_options(int argc, char *argv[])
+{
+ enum {
+ OPT_REQUEST_IP = UCHAR_MAX + 1,
+ OPT_VENDOR_CLASS,
+ OPT_NO_RESOLV_CONF
+ };
+ static struct option long_options[] = {
+ {"request-ip", required_argument, 0, OPT_REQUEST_IP },
+ {"vendor-class", required_argument, 0, OPT_VENDOR_CLASS },
+ {"no-resolv-conf", no_argument, 0, OPT_NO_RESOLV_CONF},
+ {"verbose", optional_argument, 0, 'v'},
+ {"help", no_argument, 0, 'h'},
+ {"version", no_argument, 0, 'V'},
+ {0, 0, 0, 0},
+ };
+ char *short_options = long_options_to_short_options(long_options);
+
+ for (;;) {
+ int c;
+
+ c = getopt_long(argc, argv, short_options, long_options, NULL);
+ if (c == -1) {
+ break;
+ }
+
+ switch (c) {
+ case OPT_REQUEST_IP:
+ if (!inet_aton(optarg, &request_ip)) {
+ ovs_fatal(0,
+ "--request-ip argument is not a valid IP address");
+ }
+ break;
+
+ case OPT_VENDOR_CLASS:
+ vendor_class = optarg;
+ break;
+
+ case OPT_NO_RESOLV_CONF:
+ update_resolv_conf = false;
+ break;
+
+ case 'h':
+ usage();
+
+ case 'V':
+ printf("%s %s compiled "__DATE__" "__TIME__"\n",
+ program_name, VERSION BUILDNR);
+ exit(EXIT_SUCCESS);
+
+ case 'v':
+ vlog_set_verbosity(optarg);
+ break;
+
+ case '?':
+ exit(EXIT_FAILURE);
+
+ default:
+ abort();
+ }
+ }
+ free(short_options);
+}
+
+static void
+usage(void)
+{
+ printf("%s: standalone program for testing Open vSwitch DHCP client.\n"
+ "usage: %s [OPTIONS] NETDEV\n"
+ "where NETDEV is a network device (e.g. eth0).\n"
+ "\nDHCP options:\n"
+ " --request-ip=IP request specified IP address (default:\n"
+ " do not request a specific IP)\n"
+ " --vendor-class=STRING use STRING as vendor class (default:\n"
+ " none); use OpenFlow to imitate secchan\n"
+ " --no-resolv-conf do not update /etc/resolv.conf\n",
+ program_name, program_name);
+ vlog_usage();
+ printf("\nOther options:\n"
+ " -h, --help display this help message\n"
+ " -V, --version display version information\n");
+ exit(EXIT_SUCCESS);
+}
+
diff --git a/tests/test-flows.c b/tests/test-flows.c
new file mode 100644
index 00000000..663c5a6d
--- /dev/null
+++ b/tests/test-flows.c
@@ -0,0 +1,76 @@
+#include <config.h>
+#include "flow.h"
+#include <errno.h>
+#include <stdlib.h>
+#include <string.h>
+#include "openflow/openflow.h"
+#include "timeval.h"
+#include "ofpbuf.h"
+#include "ofp-print.h"
+#include "pcap.h"
+#include "util.h"
+#include "vlog.h"
+
+#undef NDEBUG
+#include <assert.h>
+
+int
+main(int argc UNUSED, char *argv[])
+{
+ struct ofp_match expected_match;
+ FILE *flows, *pcap;
+ int retval;
+ int n = 0, errors = 0;
+
+ set_program_name(argv[0]);
+ time_init();
+ vlog_init();
+
+ flows = stdin;
+ pcap = fdopen(3, "rb");
+ if (!pcap) {
+ ovs_fatal(errno, "failed to open fd 3 for reading");
+ }
+
+ retval = pcap_read_header(pcap);
+ if (retval) {
+ ovs_fatal(retval > 0 ? retval : 0, "reading pcap header failed");
+ }
+
+ while (fread(&expected_match, sizeof expected_match, 1, flows)) {
+ struct ofpbuf *packet;
+ struct ofp_match extracted_match;
+ flow_t flow;
+
+ n++;
+
+ retval = pcap_read(pcap, &packet);
+ if (retval == EOF) {
+ ovs_fatal(0, "unexpected end of file reading pcap file");
+ } else if (retval) {
+ ovs_fatal(retval, "error reading pcap file");
+ }
+
+ flow_extract(packet, 1, &flow);
+ flow_to_match(&flow, 0, &extracted_match);
+
+ if (memcmp(&expected_match, &extracted_match, sizeof expected_match)) {
+ char *exp_s = ofp_match_to_string(&expected_match, 2);
+ char *got_s = ofp_match_to_string(&extracted_match, 2);
+ errors++;
+ printf("mismatch on packet #%d (1-based).\n", n);
+ printf("Packet:\n");
+ ofp_print_packet(stdout, packet->data, packet->size, packet->size);
+ printf("Expected flow:\n%s\n", exp_s);
+ printf("Actually extracted flow:\n%s\n", got_s);
+ printf("\n");
+ free(exp_s);
+ free(got_s);
+ }
+
+ ofpbuf_delete(packet);
+ }
+ printf("checked %d packets, %d errors\n", n, errors);
+ return errors != 0;
+}
+
diff --git a/tests/test-flows.sh b/tests/test-flows.sh
new file mode 100755
index 00000000..0d38ad78
--- /dev/null
+++ b/tests/test-flows.sh
@@ -0,0 +1,9 @@
+#! /bin/sh -e
+srcdir=`cd $srcdir && pwd`
+trap 'rm -f flows$$ pcap$$ out$$' 0 1 2 13 15
+cd tests
+"$srcdir"/tests/flowgen.pl >/dev/null 3>flows$$ 4>pcap$$
+./test-flows <flows$$ 3<pcap$$ >out$$ || true
+diff -u - out$$ <<EOF
+checked 247 packets, 0 errors
+EOF
diff --git a/tests/test-hash.c b/tests/test-hash.c
new file mode 100644
index 00000000..55a544fc
--- /dev/null
+++ b/tests/test-hash.c
@@ -0,0 +1,155 @@
+/*
+ * Copyright (c) 2009 Nicira Networks.
+ *
+ * Permission to use, copy, modify, and/or distribute this software for any
+ * purpose with or without fee is hereby granted, provided that the above
+ * copyright notice and this permission notice appear in all copies.
+ *
+ * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
+ * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
+ * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR
+ * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
+ * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
+ * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
+ * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
+ */
+
+#include <config.h>
+#include <inttypes.h>
+#include <stdio.h>
+#include <stdlib.h>
+#include <string.h>
+#include "hash.h"
+
+#undef NDEBUG
+#include <assert.h>
+
+static void
+set_bit(uint32_t array[3], int bit)
+{
+ assert(bit >= 0 && bit <= 96);
+ memset(array, 0, sizeof(uint32_t) * 3);
+ if (bit < 96) {
+ array[bit / 32] = UINT32_C(1) << (bit % 32);
+ }
+}
+
+static uint32_t
+hash_words_cb(uint32_t input)
+{
+ return hash_words(&input, 1, 0);
+}
+
+static uint32_t
+hash_int_cb(uint32_t input)
+{
+ return hash_int(input, 0);
+}
+
+static void
+check_word_hash(uint32_t (*hash)(uint32_t), const char *name,
+ int min_unique)
+{
+ int i, j;
+
+ for (i = 0; i <= 32; i++) {
+ uint32_t in1 = i < 32 ? UINT32_C(1) << i : 0;
+ for (j = i + 1; j <= 32; j++) {
+ uint32_t in2 = j < 32 ? UINT32_C(1) << j : 0;
+ uint32_t out1 = hash(in1);
+ uint32_t out2 = hash(in2);
+ const uint32_t unique_mask = (UINT32_C(1) << min_unique) - 1;
+ int ofs;
+ for (ofs = 0; ofs < 32 - min_unique; ofs++) {
+ uint32_t bits1 = (out1 >> ofs) & unique_mask;
+ uint32_t bits2 = (out2 >> ofs) & unique_mask;
+ if (bits1 == bits2) {
+ printf("Partial collision for '%s':\n", name);
+ printf("%s(%08"PRIx32") = %08"PRIx32"\n", name, in1, out1);
+ printf("%s(%08"PRIx32") = %08"PRIx32"\n", name, in2, out2);
+ printf("%d bits of output starting at bit %d "
+ "are both 0x%"PRIx32"\n", min_unique, ofs, bits1);
+ exit(1);
+ }
+ }
+ }
+ }
+}
+
+int
+main(void)
+{
+ int i, j;
+
+ /* Check that all hashes computed with hash_words with one 1-bit (or no
+ * 1-bits) set within a single 32-bit word have different values in all
+ * 11-bit consecutive runs.
+ *
+ * Given a random distribution, the probability of at least one collision
+ * in any set of 11 bits is approximately
+ *
+ * 1 - ((2**11 - 1)/2**11)**C(33,2)
+ * == 1 - (2047/2048)**528
+ * =~ 0.22
+ *
+ * There are 21 ways to pick 11 consecutive bits in a 32-bit word, so if we
+ * assumed independence then the chance of having no collisions in any of
+ * those 11-bit runs would be (1-0.22)**21 =~ .0044. Obviously
+ * independence must be a bad assumption :-)
+ */
+ check_word_hash(hash_words_cb, "hash_words", 11);
+
+ /* Check that all hash functions of with one 1-bit (or no 1-bits) set
+ * within three 32-bit words have different values in their lowest 12
+ * bits.
+ *
+ * Given a random distribution, the probability of at least one collision
+ * in 12 bits is approximately
+ *
+ * 1 - ((2**12 - 1)/2**12)**C(97,2)
+ * == 1 - (4095/4096)**4656
+ * =~ 0.68
+ *
+ * so we are doing pretty well to not have any collisions in 12 bits.
+ */
+ for (i = 0; i <= 96; i++) {
+ for (j = i + 1; j <= 96; j++) {
+ uint32_t in1[3], in2[3];
+ uint32_t out1, out2;
+ const int min_unique = 12;
+ const uint32_t unique_mask = (UINT32_C(1) << min_unique) - 1;
+
+ set_bit(in1, i);
+ set_bit(in2, j);
+ out1 = hash_words(in1, 3, 0);
+ out2 = hash_words(in2, 3, 0);
+ if ((out1 & unique_mask) == (out2 & unique_mask)) {
+ printf("Partial collision:\n");
+ printf("hash(1 << %d) == %08"PRIx32"\n", i, out1);
+ printf("hash(1 << %d) == %08"PRIx32"\n", j, out2);
+ printf("The low-order %d bits of output are both "
+ "0x%"PRIx32"\n", min_unique, out1 & unique_mask);
+ exit(1);
+ }
+ }
+ }
+
+ /* Check that all hashes computed with hash_int with one 1-bit (or no
+ * 1-bits) set within a single 32-bit word have different values in all
+ * 14-bit consecutive runs.
+ *
+ * Given a random distribution, the probability of at least one collision
+ * in any set of 14 bits is approximately
+ *
+ * 1 - ((2**14 - 1)/2**14)**C(33,2)
+ * == 1 - (16,383/16,834)**528
+ * =~ 0.031
+ *
+ * There are 18 ways to pick 14 consecutive bits in a 32-bit word, so if we
+ * assumed independence then the chance of having no collisions in any of
+ * those 14-bit runs would be (1-0.03)**18 =~ 0.56. This seems reasonable.
+ */
+ check_word_hash(hash_int_cb, "hash_int", 14);
+
+ return 0;
+}
diff --git a/tests/test-hmap.c b/tests/test-hmap.c
new file mode 100644
index 00000000..684a5bae
--- /dev/null
+++ b/tests/test-hmap.c
@@ -0,0 +1,281 @@
+/* A non-exhaustive test for some of the functions and macros declared in
+ * hmap.h. */
+
+#include <config.h>
+#include "hmap.h"
+#include <string.h>
+#include "hash.h"
+#include "util.h"
+
+#undef NDEBUG
+#include <assert.h>
+
+/* Sample hmap element. */
+struct element {
+ int value;
+ struct hmap_node node;
+};
+
+typedef size_t hash_func(int value);
+
+static int
+compare_ints(const void *a_, const void *b_)
+{
+ const int *a = a_;
+ const int *b = b_;
+ return *a < *b ? -1 : *a > *b;
+}
+
+/* Verifies that 'hmap' contains exactly the 'n' values in 'values'. */
+static void
+check_hmap(struct hmap *hmap, const int values[], size_t n,
+ hash_func *hash)
+{
+ int *sort_values, *hmap_values;
+ struct element *e;
+ size_t i;
+
+ /* Check that all the values are there in iteration. */
+ sort_values = xmalloc(sizeof *sort_values * n);
+ hmap_values = xmalloc(sizeof *sort_values * n);
+
+ i = 0;
+ HMAP_FOR_EACH (e, struct element, node, hmap) {
+ assert(i < n);
+ hmap_values[i++] = e->value;
+ }
+ assert(i == n);
+
+ memcpy(sort_values, values, sizeof *sort_values * n);
+ qsort(sort_values, n, sizeof *sort_values, compare_ints);
+ qsort(hmap_values, n, sizeof *hmap_values, compare_ints);
+
+ for (i = 0; i < n; i++) {
+ assert(sort_values[i] == hmap_values[i]);
+ }
+
+ free(hmap_values);
+ free(sort_values);
+
+ /* Check that all the values are there in lookup. */
+ for (i = 0; i < n; i++) {
+ size_t count = 0;
+
+ HMAP_FOR_EACH_WITH_HASH (e, struct element, node,
+ hash(values[i]), hmap) {
+ count += e->value == values[i];
+ }
+ assert(count == 1);
+ }
+
+ /* Check counters. */
+ assert(hmap_is_empty(hmap) == !n);
+ assert(hmap_count(hmap) == n);
+}
+
+/* Puts the 'n' values in 'values' into 'elements', and then puts those
+ * elements into 'hmap'. */
+static void
+make_hmap(struct hmap *hmap, struct element elements[],
+ int values[], size_t n, hash_func *hash)
+{
+ size_t i;
+
+ hmap_init(hmap);
+ for (i = 0; i < n; i++) {
+ elements[i].value = i;
+ hmap_insert(hmap, &elements[i].node, hash(elements[i].value));
+ values[i] = i;
+ }
+}
+
+static void
+shuffle(int *p, size_t n)
+{
+ for (; n > 1; n--, p++) {
+ int *q = &p[rand() % n];
+ int tmp = *p;
+ *p = *q;
+ *q = tmp;
+ }
+}
+
+#if 0
+/* Prints the values in 'hmap', plus 'name' as a title. */
+static void
+print_hmap(const char *name, struct hmap *hmap)
+{
+ struct element *e;
+
+ printf("%s:", name);
+ HMAP_FOR_EACH (e, struct element, node, hmap) {
+ printf(" %d(%zu)", e->value, e->node.hash & hmap->mask);
+ }
+ printf("\n");
+}
+
+/* Prints the 'n' values in 'values', plus 'name' as a title. */
+static void
+print_ints(const char *name, const int *values, size_t n)
+{
+ size_t i;
+
+ printf("%s:", name);
+ for (i = 0; i < n; i++) {
+ printf(" %d", values[i]);
+ }
+ printf("\n");
+}
+#endif
+
+static size_t
+identity_hash(int value)
+{
+ return value;
+}
+
+static size_t
+good_hash(int value)
+{
+ return hash_int(value, 0x1234abcd);
+}
+
+static size_t
+constant_hash(int value UNUSED)
+{
+ return 123;
+}
+
+/* Tests basic hmap insertion and deletion. */
+static void
+test_hmap_insert_delete(hash_func *hash)
+{
+ enum { N_ELEMS = 100 };
+
+ struct element elements[N_ELEMS];
+ int values[N_ELEMS];
+ struct hmap hmap;
+ size_t i;
+
+ hmap_init(&hmap);
+ for (i = 0; i < N_ELEMS; i++) {
+ elements[i].value = i;
+ hmap_insert(&hmap, &elements[i].node, hash(i));
+ values[i] = i;
+ check_hmap(&hmap, values, i + 1, hash);
+ }
+ shuffle(values, N_ELEMS);
+ for (i = 0; i < N_ELEMS; i++) {
+ hmap_remove(&hmap, &elements[values[i]].node);
+ check_hmap(&hmap, values + (i + 1), N_ELEMS - (i + 1), hash);
+ }
+ hmap_destroy(&hmap);
+}
+
+/* Tests basic hmap_reserve() and hmap_shrink(). */
+static void
+test_hmap_reserve_shrink(hash_func *hash)
+{
+ enum { N_ELEMS = 32 };
+
+ size_t i;
+
+ for (i = 0; i < N_ELEMS; i++) {
+ struct element elements[N_ELEMS];
+ int values[N_ELEMS];
+ struct hmap hmap;
+ size_t j;
+
+ hmap_init(&hmap);
+ hmap_reserve(&hmap, i);
+ for (j = 0; j < N_ELEMS; j++) {
+ elements[j].value = j;
+ hmap_insert(&hmap, &elements[j].node, hash(j));
+ values[j] = j;
+ check_hmap(&hmap, values, j + 1, hash);
+ }
+ shuffle(values, N_ELEMS);
+ for (j = 0; j < N_ELEMS; j++) {
+ hmap_remove(&hmap, &elements[values[j]].node);
+ hmap_shrink(&hmap);
+ check_hmap(&hmap, values + (j + 1), N_ELEMS - (j + 1), hash);
+ }
+ hmap_destroy(&hmap);
+ }
+}
+
+/* Tests that HMAP_FOR_EACH_SAFE properly allows for deletion of the current
+ * element of a hmap. */
+static void
+test_hmap_for_each_safe(hash_func *hash)
+{
+ enum { MAX_ELEMS = 10 };
+ size_t n;
+ unsigned long int pattern;
+
+ for (n = 0; n <= MAX_ELEMS; n++) {
+ for (pattern = 0; pattern < 1ul << n; pattern++) {
+ struct element elements[MAX_ELEMS];
+ int values[MAX_ELEMS];
+ struct hmap hmap;
+ struct element *e, *next;
+ size_t n_remaining;
+ int i;
+
+ make_hmap(&hmap, elements, values, n, hash);
+
+ i = 0;
+ n_remaining = n;
+ HMAP_FOR_EACH_SAFE (e, next, struct element, node, &hmap) {
+ assert(i < n);
+ if (pattern & (1ul << e->value)) {
+ size_t j;
+ hmap_remove(&hmap, &e->node);
+ for (j = 0; ; j++) {
+ assert(j < n_remaining);
+ if (values[j] == e->value) {
+ values[j] = values[--n_remaining];
+ break;
+ }
+ }
+ }
+ check_hmap(&hmap, values, n_remaining, hash);
+ i++;
+ }
+ assert(i == n);
+
+ for (i = 0; i < n; i++) {
+ if (pattern & (1ul << i)) {
+ n_remaining++;
+ }
+ }
+ assert(n == n_remaining);
+
+ hmap_destroy(&hmap);
+ }
+ }
+}
+
+static void
+run_test(void (*function)(hash_func *))
+{
+ hash_func *hash_funcs[] = { identity_hash, good_hash, constant_hash };
+ size_t i;
+
+ for (i = 0; i < ARRAY_SIZE(hash_funcs); i++) {
+ function(hash_funcs[i]);
+ printf(".");
+ fflush(stdout);
+ }
+}
+
+int
+main(void)
+{
+ run_test(test_hmap_insert_delete);
+ run_test(test_hmap_for_each_safe);
+ run_test(test_hmap_reserve_shrink);
+ printf("\n");
+ return 0;
+}
+
diff --git a/tests/test-list.c b/tests/test-list.c
new file mode 100644
index 00000000..62857be9
--- /dev/null
+++ b/tests/test-list.c
@@ -0,0 +1,159 @@
+/* A non-exhaustive test for some of the functions and macros declared in
+ * list.h. */
+
+#include <config.h>
+#include "list.h"
+#include <string.h>
+
+#undef NDEBUG
+#include <assert.h>
+
+/* Sample list element. */
+struct element {
+ int value;
+ struct list node;
+};
+
+/* Puts the 'n' values in 'values' into 'elements', and then puts those
+ * elements in order into 'list'. */
+static void
+make_list(struct list *list, struct element elements[],
+ int values[], size_t n)
+{
+ size_t i;
+
+ list_init(list);
+ for (i = 0; i < n; i++) {
+ elements[i].value = i;
+ list_push_back(list, &elements[i].node);
+ values[i] = i;
+ }
+}
+
+/* Verifies that 'list' contains exactly the 'n' values in 'values', in the
+ * specified order. */
+static void
+check_list(struct list *list, const int values[], size_t n)
+{
+ struct element *e;
+ size_t i;
+
+ i = 0;
+ LIST_FOR_EACH (e, struct element, node, list) {
+ assert(i < n);
+ assert(e->value == values[i]);
+ i++;
+ }
+ assert(&e->node == list);
+ assert(i == n);
+
+ i = 0;
+ LIST_FOR_EACH_REVERSE (e, struct element, node, list) {
+ assert(i < n);
+ assert(e->value == values[n - i - 1]);
+ i++;
+ }
+ assert(&e->node == list);
+ assert(i == n);
+
+ assert(list_is_empty(list) == !n);
+ assert(list_size(list) == n);
+}
+
+#if 0
+/* Prints the values in 'list', plus 'name' as a title. */
+static void
+print_list(const char *name, struct list *list)
+{
+ struct element *e;
+
+ printf("%s:", name);
+ LIST_FOR_EACH (e, struct element, node, list) {
+ printf(" %d", e->value);
+ }
+ printf("\n");
+}
+#endif
+
+/* Tests basic list construction. */
+static void
+test_list_construction(void)
+{
+ enum { MAX_ELEMS = 100 };
+ size_t n;
+
+ for (n = 0; n <= MAX_ELEMS; n++) {
+ struct element elements[MAX_ELEMS];
+ int values[MAX_ELEMS];
+ struct list list;
+
+ make_list(&list, elements, values, n);
+ check_list(&list, values, n);
+ }
+}
+
+/* Tests that LIST_FOR_EACH_SAFE properly allows for deletion of the current
+ * element of a list. */
+static void
+test_list_for_each_safe(void)
+{
+ enum { MAX_ELEMS = 10 };
+ size_t n;
+ unsigned long int pattern;
+
+ for (n = 0; n <= MAX_ELEMS; n++) {
+ for (pattern = 0; pattern < 1ul << n; pattern++) {
+ struct element elements[MAX_ELEMS];
+ int values[MAX_ELEMS];
+ struct list list;
+ struct element *e, *next;
+ size_t values_idx, n_remaining;
+ int i;
+
+ make_list(&list, elements, values, n);
+
+ i = 0;
+ values_idx = 0;
+ n_remaining = n;
+ LIST_FOR_EACH_SAFE (e, next, struct element, node, &list) {
+ assert(i < n);
+ if (pattern & (1ul << i)) {
+ list_remove(&e->node);
+ n_remaining--;
+ memmove(&values[values_idx], &values[values_idx + 1],
+ sizeof *values * (n_remaining - values_idx));
+ } else {
+ values_idx++;
+ }
+ check_list(&list, values, n_remaining);
+ i++;
+ }
+ assert(i == n);
+ assert(&e->node == &list);
+
+ for (i = 0; i < n; i++) {
+ if (pattern & (1ul << i)) {
+ n_remaining++;
+ }
+ }
+ assert(n == n_remaining);
+ }
+ }
+}
+
+static void
+run_test(void (*function)(void))
+{
+ function();
+ printf(".");
+}
+
+int
+main(void)
+{
+ run_test(test_list_construction);
+ run_test(test_list_for_each_safe);
+ printf("\n");
+ return 0;
+}
+
diff --git a/tests/test-stp-ieee802.1d-1998 b/tests/test-stp-ieee802.1d-1998
new file mode 100644
index 00000000..f1982a03
--- /dev/null
+++ b/tests/test-stp-ieee802.1d-1998
@@ -0,0 +1,12 @@
+# This is the STP example from IEEE 802.1D-1998.
+bridge 0 0x42 = a b
+bridge 1 0x97 = c:5 a d:5
+bridge 2 0x45 = b e
+bridge 3 0x57 = b:5 e:5
+bridge 4 0x83 = a:5 e:5
+run 1000
+check 0 = root
+check 1 = F F:10 F
+check 2 = F:10 B
+check 3 = F:5 F
+check 4 = F:5 B
diff --git a/tests/test-stp-ieee802.1d-2004-fig17.4 b/tests/test-stp-ieee802.1d-2004-fig17.4
new file mode 100644
index 00000000..1f708630
--- /dev/null
+++ b/tests/test-stp-ieee802.1d-2004-fig17.4
@@ -0,0 +1,31 @@
+# This is the STP example from IEEE 802.1D-2004 figures 17.4 and 17.5.
+bridge 0 0x111 = a b e c
+bridge 1 0x222 = a b d f
+bridge 2 0x333 = c d l j h g
+bridge 3 0x444 = e f n m k i
+bridge 4 0x555 = g i 0 0
+bridge 5 0x666 = h k 0 0
+bridge 6 0x777 = j m 0 0
+bridge 7 0x888 = l n 0 0
+run 1000
+check 0 = root
+check 1 = F:10 B F F
+check 2 = F:10 B F F F F
+check 3 = F:10 B F F F F
+check 4 = F:20 B F F
+check 5 = F:20 B F F
+check 6 = F:20 B F F
+check 7 = F:20 B F F
+
+# Now connect two ports of bridge 7 to the same LAN.
+bridge 7 = l n o o
+# Same results except for bridge 7:
+run 1000
+check 0 = root
+check 1 = F:10 B F F
+check 2 = F:10 B F F F F
+check 3 = F:10 B F F F F
+check 4 = F:20 B F F
+check 5 = F:20 B F F
+check 6 = F:20 B F F
+check 7 = F:20 B F B
diff --git a/tests/test-stp-ieee802.1d-2004-fig17.6 b/tests/test-stp-ieee802.1d-2004-fig17.6
new file mode 100644
index 00000000..6ed59177
--- /dev/null
+++ b/tests/test-stp-ieee802.1d-2004-fig17.6
@@ -0,0 +1,14 @@
+# This is the STP example from IEEE 802.1D-2004 figure 17.6.
+bridge 0 0x111 = a b l
+bridge 1 0x222 = b c d
+bridge 2 0x333 = d e f
+bridge 3 0x444 = f g h
+bridge 4 0x555 = j h i
+bridge 5 0x666 = l j k
+run 1000
+check 0 = root
+check 1 = F:10 F F
+check 2 = F:20 F F
+check 3 = F:30 F B
+check 4 = F:20 F F
+check 5 = F:10 F F
diff --git a/tests/test-stp-ieee802.1d-2004-fig17.7 b/tests/test-stp-ieee802.1d-2004-fig17.7
new file mode 100644
index 00000000..daa0cdf2
--- /dev/null
+++ b/tests/test-stp-ieee802.1d-2004-fig17.7
@@ -0,0 +1,17 @@
+# This is the STP example from IEEE 802.1D-2004 figure 17.7.
+bridge 0 0xaa = b
+bridge 1 0x111 = a b d f h g e c
+bridge 2 0x222 = g h j l n m k i
+run 1000
+check 0 = root
+check 1 = F F:10 F F F F F F
+check 2 = B F:20 F F F F F F
+
+# This is not the port priority change described in that figure,
+# but I don't understand what port priority change would cause
+# that change.
+bridge 2 = g X j l n m k i
+run 1000
+check 0 = root
+check 1 = F F:10 F F F F F F
+check 2 = F:20 D F F F F F F
diff --git a/tests/test-stp-iol-io-1.1 b/tests/test-stp-iol-io-1.1
new file mode 100644
index 00000000..186d6c4c
--- /dev/null
+++ b/tests/test-stp-iol-io-1.1
@@ -0,0 +1,25 @@
+# This test file approximates the following test from "Bridge
+# Functions Consortium Spanning Tree Interoperability Test Suite
+# Version 1.5":
+# STP.io.1.1: Link Failure
+bridge 0 0x111 = a b c
+bridge 1 0x222 = a b c
+run 1000
+check 0 = root
+check 1 = F:10 B B
+bridge 1 = 0 _ _
+run 1000
+check 0 = root
+check 1 = F F:10 B
+bridge 1 = X _ _
+run 1000
+check 0 = root
+check 1 = D F:10 B
+bridge 1 = _ 0 _
+run 1000
+check 0 = root
+check 1 = D F F:10
+bridge 1 = _ X _
+run 1000
+check 0 = root
+check 1 = D D F:10
diff --git a/tests/test-stp-iol-io-1.2 b/tests/test-stp-iol-io-1.2
new file mode 100644
index 00000000..285bbd88
--- /dev/null
+++ b/tests/test-stp-iol-io-1.2
@@ -0,0 +1,14 @@
+# This test file approximates the following test from "Bridge
+# Functions Consortium Spanning Tree Interoperability Test Suite
+# Version 1.5":
+# STP.io.1.2: Repeated Network
+bridge 0 0x111 = a a
+bridge 1 0x222 = a a
+run 1000
+check 0 = rootid:0x111 F B
+check 1 = rootid:0x111 F:10 B
+bridge 1 = a^0x90 _
+run 1000
+check 0 = rootid:0x111 F B
+check 1 = rootid:0x111 B F:10
+
diff --git a/tests/test-stp-iol-io-1.4 b/tests/test-stp-iol-io-1.4
new file mode 100644
index 00000000..0065aaf5
--- /dev/null
+++ b/tests/test-stp-iol-io-1.4
@@ -0,0 +1,13 @@
+# This test file approximates the following test from "Bridge
+# Functions Consortium Spanning Tree Interoperability Test Suite
+# Version 1.5":
+# STP.io.1.4: Network Initialization
+bridge 0 0x111 = a b c
+bridge 1 0x222 = b d e
+bridge 2 0x333 = a d f
+bridge 3 0x444 = c e f
+run 1000
+check 0 = root
+check 1 = F:10 F F
+check 2 = F:10 B F
+check 3 = F:10 B B
diff --git a/tests/test-stp-iol-io-1.5 b/tests/test-stp-iol-io-1.5
new file mode 100644
index 00000000..285d29de
--- /dev/null
+++ b/tests/test-stp-iol-io-1.5
@@ -0,0 +1,40 @@
+# This test file approximates the following test from "Bridge
+# Functions Consortium Spanning Tree Interoperability Test Suite
+# Version 1.5":
+# STP.io.1.5: Topology Change
+bridge 0 0x111 = a b d c
+bridge 1 0x222 = a b f e
+bridge 2 0x333 = c d g h
+bridge 3 0x444 = e f g h
+run 1000
+check 0 = root
+check 1 = F:10 B F F
+check 2 = B F:10 F F
+check 3 = B F:20 B B
+bridge 1^0x7000
+run 1000
+check 0 = F:10 B F F
+check 1 = root
+check 2 = B F:20 B B
+check 3 = B F:10 F F
+bridge 2^0x6000
+run 1000
+check 0 = F F B F:10
+check 1 = F:20 B B B
+check 2 = root
+check 3 = F F F:10 B
+bridge 3^0x5000
+run 1000
+check 0 = B B B F:20
+check 1 = F F B F:10
+check 2 = F F F:10 B
+check 3 = root
+bridge 0^0x4000
+bridge 1^0x4001
+bridge 2^0x4002
+bridge 3^0x4003
+run 1000
+check 0 = root
+check 1 = F:10 B F F
+check 2 = B F:10 F F
+check 3 = B F:20 B B
diff --git a/tests/test-stp-iol-op-1.1 b/tests/test-stp-iol-op-1.1
new file mode 100644
index 00000000..8432bf36
--- /dev/null
+++ b/tests/test-stp-iol-op-1.1
@@ -0,0 +1,7 @@
+# This test file approximates the following tests from "Bridge
+# Functions Consortium Spanning Tree Protocol Operations Test Suite
+# Version 2.3":
+# Test STP.op.1.1 ­ Root ID Initialized to Bridge ID
+# Test STP.op.1.2 ­ Root Path Cost Initialized to Zero
+bridge 0 0x123 =
+check 0 = root
diff --git a/tests/test-stp-iol-op-1.4 b/tests/test-stp-iol-op-1.4
new file mode 100644
index 00000000..6a121164
--- /dev/null
+++ b/tests/test-stp-iol-op-1.4
@@ -0,0 +1,8 @@
+# This test file approximates the following test from "Bridge
+# Functions Consortium Spanning Tree Protocol Operations Test Suite
+# Version 2.3":
+# Test STP.op.1.4 ­ All Ports Initialized to Designated Ports
+bridge 0 0x123 = a b c d e f
+check 0 = Li Li Li Li Li Li
+run 1000
+check 0 = F F F F F F
diff --git a/tests/test-stp-iol-op-3.1 b/tests/test-stp-iol-op-3.1
new file mode 100644
index 00000000..3e1099cb
--- /dev/null
+++ b/tests/test-stp-iol-op-3.1
@@ -0,0 +1,11 @@
+# This test file approximates the following test from "Bridge
+# Functions Consortium Spanning Tree Protocol Operations Test Suite
+# Version 2.3":
+# Test STP.op.3.1 ­ Root Bridge Selection: Root ID Values
+bridge 0 0x111 = a
+bridge 1 0x222 = a
+check 0 = rootid:0x111 Li
+check 1 = rootid:0x222 Li
+run 1000
+check 0 = rootid:0x111 root
+check 1 = rootid:0x111 F:10
diff --git a/tests/test-stp-iol-op-3.3 b/tests/test-stp-iol-op-3.3
new file mode 100644
index 00000000..2bcd45e1
--- /dev/null
+++ b/tests/test-stp-iol-op-3.3
@@ -0,0 +1,11 @@
+# This test file approximates the following test from "Bridge
+# Functions Consortium Spanning Tree Protocol Operations Test Suite
+# Version 2.3":
+# Test STP.op.3.3 ­ Root Bridge Selection: Bridge ID Values
+bridge 0 0x333^0x6000 = a
+bridge 1 0x222^0x7000 = b
+bridge 2 0x111 = a b
+run 1000
+check 0 = rootid:0x333^0x6000 root
+check 1 = rootid:0x333^0x6000 F:20
+check 2 = rootid:0x333^0x6000 F:10 F
diff --git a/tests/test-stp-iol-op-3.4 b/tests/test-stp-iol-op-3.4
new file mode 100644
index 00000000..2bcd45e1
--- /dev/null
+++ b/tests/test-stp-iol-op-3.4
@@ -0,0 +1,11 @@
+# This test file approximates the following test from "Bridge
+# Functions Consortium Spanning Tree Protocol Operations Test Suite
+# Version 2.3":
+# Test STP.op.3.3 ­ Root Bridge Selection: Bridge ID Values
+bridge 0 0x333^0x6000 = a
+bridge 1 0x222^0x7000 = b
+bridge 2 0x111 = a b
+run 1000
+check 0 = rootid:0x333^0x6000 root
+check 1 = rootid:0x333^0x6000 F:20
+check 2 = rootid:0x333^0x6000 F:10 F
diff --git a/tests/test-stp.c b/tests/test-stp.c
new file mode 100644
index 00000000..07336815
--- /dev/null
+++ b/tests/test-stp.c
@@ -0,0 +1,648 @@
+/*
+ * Copyright (c) 2008, 2009 Nicira Networks.
+ *
+ * Permission to use, copy, modify, and/or distribute this software for any
+ * purpose with or without fee is hereby granted, provided that the above
+ * copyright notice and this permission notice appear in all copies.
+ *
+ * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
+ * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
+ * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR
+ * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
+ * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
+ * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
+ * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
+ */
+
+#include "stp.h"
+#include <assert.h>
+#include <ctype.h>
+#include <errno.h>
+#include <inttypes.h>
+#include <stdarg.h>
+#include <stdlib.h>
+#include "ofpbuf.h"
+#include "packets.h"
+
+struct bpdu {
+ int port_no;
+ void *data;
+ size_t size;
+};
+
+struct bridge {
+ struct test_case *tc;
+ int id;
+ bool reached;
+
+ struct stp *stp;
+
+ struct lan *ports[STP_MAX_PORTS];
+ int n_ports;
+
+#define RXQ_SIZE 16
+ struct bpdu rxq[RXQ_SIZE];
+ int rxq_head, rxq_tail;
+};
+
+struct lan_conn {
+ struct bridge *bridge;
+ int port_no;
+};
+
+struct lan {
+ struct test_case *tc;
+ const char *name;
+ bool reached;
+ struct lan_conn conns[16];
+ int n_conns;
+};
+
+struct test_case {
+ struct bridge *bridges[16];
+ int n_bridges;
+ struct lan *lans[26];
+ int n_lans;
+};
+
+static const char *file_name;
+static int line_number;
+static char line[128];
+static char *pos, *token;
+static int n_warnings;
+
+static struct test_case *
+new_test_case(void)
+{
+ struct test_case *tc = xmalloc(sizeof *tc);
+ tc->n_bridges = 0;
+ tc->n_lans = 0;
+ return tc;
+}
+
+static void
+send_bpdu(struct ofpbuf *pkt, int port_no, void *b_)
+{
+ struct bridge *b = b_;
+ struct lan *lan;
+
+ assert(port_no < b->n_ports);
+ lan = b->ports[port_no];
+ if (lan) {
+ const void *data = pkt->l3;
+ size_t size = (char *) ofpbuf_tail(pkt) - (char *) data;
+ int i;
+
+ for (i = 0; i < lan->n_conns; i++) {
+ struct lan_conn *conn = &lan->conns[i];
+ if (conn->bridge != b || conn->port_no != port_no) {
+ struct bridge *dst = conn->bridge;
+ struct bpdu *bpdu = &dst->rxq[dst->rxq_head++ % RXQ_SIZE];
+ assert(dst->rxq_head - dst->rxq_tail <= RXQ_SIZE);
+ bpdu->data = xmemdup(data, size);
+ bpdu->size = size;
+ bpdu->port_no = conn->port_no;
+ }
+ }
+ }
+ ofpbuf_delete(pkt);
+}
+
+static struct bridge *
+new_bridge(struct test_case *tc, int id)
+{
+ struct bridge *b = xmalloc(sizeof *b);
+ char name[16];
+ b->tc = tc;
+ b->id = id;
+ snprintf(name, sizeof name, "stp%x", id);
+ b->stp = stp_create(name, id, send_bpdu, b);
+ assert(tc->n_bridges < ARRAY_SIZE(tc->bridges));
+ b->n_ports = 0;
+ b->rxq_head = b->rxq_tail = 0;
+ tc->bridges[tc->n_bridges++] = b;
+ return b;
+}
+
+static struct lan *
+new_lan(struct test_case *tc, const char *name)
+{
+ struct lan *lan = xmalloc(sizeof *lan);
+ lan->tc = tc;
+ lan->name = xstrdup(name);
+ lan->n_conns = 0;
+ assert(tc->n_lans < ARRAY_SIZE(tc->lans));
+ tc->lans[tc->n_lans++] = lan;
+ return lan;
+}
+
+static void
+reconnect_port(struct bridge *b, int port_no, struct lan *new_lan)
+{
+ struct lan *old_lan;
+ int j;
+
+ assert(port_no < b->n_ports);
+ old_lan = b->ports[port_no];
+ if (old_lan == new_lan) {
+ return;
+ }
+
+ /* Disconnect from old_lan. */
+ if (old_lan) {
+ for (j = 0; j < old_lan->n_conns; j++) {
+ struct lan_conn *c = &old_lan->conns[j];
+ if (c->bridge == b && c->port_no == port_no) {
+ memmove(c, c + 1, sizeof *c * (old_lan->n_conns - j - 1));
+ old_lan->n_conns--;
+ break;
+ }
+ }
+ }
+
+ /* Connect to new_lan. */
+ b->ports[port_no] = new_lan;
+ if (new_lan) {
+ int conn_no = new_lan->n_conns++;
+ assert(conn_no < ARRAY_SIZE(new_lan->conns));
+ new_lan->conns[conn_no].bridge = b;
+ new_lan->conns[conn_no].port_no = port_no;
+ }
+}
+
+static void
+new_port(struct bridge *b, struct lan *lan, int path_cost)
+{
+ int port_no = b->n_ports++;
+ struct stp_port *p = stp_get_port(b->stp, port_no);
+ assert(port_no < ARRAY_SIZE(b->ports));
+ b->ports[port_no] = NULL;
+ stp_port_set_path_cost(p, path_cost);
+ stp_port_enable(p);
+ reconnect_port(b, port_no, lan);
+}
+
+static void
+dump(struct test_case *tc)
+{
+ int i;
+
+ for (i = 0; i < tc->n_bridges; i++) {
+ struct bridge *b = tc->bridges[i];
+ struct stp *stp = b->stp;
+ int j;
+
+ printf("%s:", stp_get_name(stp));
+ if (stp_is_root_bridge(stp)) {
+ printf(" root");
+ }
+ printf("\n");
+ for (j = 0; j < b->n_ports; j++) {
+ struct stp_port *p = stp_get_port(stp, j);
+ enum stp_state state = stp_port_get_state(p);
+
+ printf("\tport %d", j);
+ if (b->ports[j]) {
+ printf(" (lan %s)", b->ports[j]->name);
+ } else {
+ printf(" (disconnected)");
+ }
+ printf(": %s", stp_state_name(state));
+ if (p == stp_get_root_port(stp)) {
+ printf(" (root port, root_path_cost=%u)", stp_get_root_path_cost(stp));
+ }
+ printf("\n");
+ }
+ }
+}
+
+static void dump_lan_tree(struct test_case *, struct lan *, int level);
+
+static void
+dump_bridge_tree(struct test_case *tc, struct bridge *b, int level)
+{
+ int i;
+
+ if (b->reached) {
+ return;
+ }
+ b->reached = true;
+ for (i = 0; i < level; i++) {
+ printf("\t");
+ }
+ printf("%s\n", stp_get_name(b->stp));
+ for (i = 0; i < b->n_ports; i++) {
+ struct lan *lan = b->ports[i];
+ struct stp_port *p = stp_get_port(b->stp, i);
+ if (stp_port_get_state(p) == STP_FORWARDING && lan) {
+ dump_lan_tree(tc, lan, level + 1);
+ }
+ }
+}
+
+static void
+dump_lan_tree(struct test_case *tc, struct lan *lan, int level)
+{
+ int i;
+
+ if (lan->reached) {
+ return;
+ }
+ lan->reached = true;
+ for (i = 0; i < level; i++) {
+ printf("\t");
+ }
+ printf("%s\n", lan->name);
+ for (i = 0; i < lan->n_conns; i++) {
+ struct bridge *b = lan->conns[i].bridge;
+ dump_bridge_tree(tc, b, level + 1);
+ }
+}
+
+static void
+tree(struct test_case *tc)
+{
+ int i;
+
+ for (i = 0; i < tc->n_bridges; i++) {
+ struct bridge *b = tc->bridges[i];
+ b->reached = false;
+ }
+ for (i = 0; i < tc->n_lans; i++) {
+ struct lan *lan = tc->lans[i];
+ lan->reached = false;
+ }
+ for (i = 0; i < tc->n_bridges; i++) {
+ struct bridge *b = tc->bridges[i];
+ struct stp *stp = b->stp;
+ if (stp_is_root_bridge(stp)) {
+ dump_bridge_tree(tc, b, 0);
+ }
+ }
+}
+
+static void
+simulate(struct test_case *tc, int granularity)
+{
+ int time;
+
+ for (time = 0; time < 1000 * 180; time += granularity) {
+ int round_trips;
+ int i;
+
+ for (i = 0; i < tc->n_bridges; i++) {
+ stp_tick(tc->bridges[i]->stp, granularity);
+ }
+ for (round_trips = 0; round_trips < granularity; round_trips++) {
+ bool any = false;
+ for (i = 0; i < tc->n_bridges; i++) {
+ struct bridge *b = tc->bridges[i];
+ for (; b->rxq_tail != b->rxq_head; b->rxq_tail++) {
+ struct bpdu *bpdu = &b->rxq[b->rxq_tail % RXQ_SIZE];
+ stp_received_bpdu(stp_get_port(b->stp, bpdu->port_no),
+ bpdu->data, bpdu->size);
+ any = true;
+ }
+ }
+ if (!any) {
+ break;
+ }
+ }
+ }
+}
+
+static void
+err(const char *message, ...)
+ PRINTF_FORMAT(1, 2)
+ NO_RETURN;
+
+static void
+err(const char *message, ...)
+{
+ va_list args;
+
+ fprintf(stderr, "%s:%d:%td: ", file_name, line_number, pos - line);
+ va_start(args, message);
+ vfprintf(stderr, message, args);
+ va_end(args);
+ putc('\n', stderr);
+
+ exit(EXIT_FAILURE);
+}
+
+static void
+warn(const char *message, ...)
+ PRINTF_FORMAT(1, 2);
+
+static void
+warn(const char *message, ...)
+{
+ va_list args;
+
+ fprintf(stderr, "%s:%d: ", file_name, line_number);
+ va_start(args, message);
+ vfprintf(stderr, message, args);
+ va_end(args);
+ putc('\n', stderr);
+
+ n_warnings++;
+}
+
+static bool
+get_token(void)
+{
+ char *start;
+
+ while (isspace((unsigned char) *pos)) {
+ pos++;
+ }
+ if (*pos == '\0') {
+ token = NULL;
+ return false;
+ }
+
+ start = pos;
+ if (isalpha((unsigned char) *pos)) {
+ while (isalpha((unsigned char) *++pos)) {
+ continue;
+ }
+ } else if (isdigit((unsigned char) *pos)) {
+ if (*pos == '0' && (pos[1] == 'x' || pos[1] == 'X')) {
+ pos += 2;
+ while (isxdigit((unsigned char) *pos)) {
+ pos++;
+ }
+ } else {
+ while (isdigit((unsigned char) *++pos)) {
+ continue;
+ }
+ }
+ } else {
+ pos++;
+ }
+
+ free(token);
+ token = xmemdup0(start, pos - start);
+ return true;
+}
+
+static bool
+get_int(int *intp)
+{
+ char *save_pos = pos;
+ if (token && isdigit((unsigned char) *token)) {
+ *intp = strtol(token, NULL, 0);
+ get_token();
+ return true;
+ } else {
+ pos = save_pos;
+ return false;
+ }
+}
+
+static bool
+match(const char *want)
+{
+ if (token && !strcmp(want, token)) {
+ get_token();
+ return true;
+ } else {
+ return false;
+ }
+}
+
+static int
+must_get_int(void)
+{
+ int x;
+ if (!get_int(&x)) {
+ err("expected integer");
+ }
+ return x;
+}
+
+static void
+must_match(const char *want)
+{
+ if (!match(want)) {
+ err("expected \"%s\"", want);
+ }
+}
+
+int
+main(int argc, char *argv[])
+{
+ struct test_case *tc;
+ FILE *input_file;
+ int i;
+
+ if (argc != 2) {
+ ovs_fatal(0, "usage: test-stp INPUT.STP\n");
+ }
+ file_name = argv[1];
+
+ input_file = fopen(file_name, "r");
+ if (!input_file) {
+ ovs_fatal(errno, "error opening \"%s\"", file_name);
+ }
+
+ tc = new_test_case();
+ for (i = 0; i < 26; i++) {
+ char name[2];
+ name[0] = 'a' + i;
+ name[1] = '\0';
+ new_lan(tc, name);
+ }
+
+ for (line_number = 1; fgets(line, sizeof line, input_file);
+ line_number++)
+ {
+ char *newline, *hash;
+
+ newline = strchr(line, '\n');
+ if (newline) {
+ *newline = '\0';
+ }
+ hash = strchr(line, '#');
+ if (hash) {
+ *hash = '\0';
+ }
+
+ pos = line;
+ if (!get_token()) {
+ continue;
+ }
+ if (match("bridge")) {
+ struct bridge *bridge;
+ int bridge_no, port_no;
+
+ bridge_no = must_get_int();
+ if (bridge_no < tc->n_bridges) {
+ bridge = tc->bridges[bridge_no];
+ } else if (bridge_no == tc->n_bridges) {
+ bridge = new_bridge(tc, must_get_int());
+ } else {
+ err("bridges must be numbered consecutively from 0");
+ }
+ if (match("^")) {
+ stp_set_bridge_priority(bridge->stp, must_get_int());
+ }
+
+ if (match("=")) {
+ for (port_no = 0; port_no < STP_MAX_PORTS; port_no++) {
+ struct stp_port *p = stp_get_port(bridge->stp, port_no);
+ if (!token || match("X")) {
+ stp_port_disable(p);
+ } else if (match("_")) {
+ /* Nothing to do. */
+ } else {
+ struct lan *lan;
+ int path_cost;
+
+ if (!strcmp(token, "0")) {
+ lan = NULL;
+ } else if (strlen(token) == 1 && islower(*token)) {
+ lan = tc->lans[*token - 'a'];
+ } else {
+ err("%s is not a valid LAN name "
+ "(0 or a lowercase letter)", token);
+ }
+ get_token();
+
+ path_cost = match(":") ? must_get_int() : 10;
+ if (port_no < bridge->n_ports) {
+ stp_port_set_path_cost(p, path_cost);
+ stp_port_enable(p);
+ reconnect_port(bridge, port_no, lan);
+ } else if (port_no == bridge->n_ports) {
+ new_port(bridge, lan, path_cost);
+ } else {
+ err("ports must be numbered consecutively");
+ }
+ if (match("^")) {
+ stp_port_set_priority(p, must_get_int());
+ }
+ }
+ }
+ }
+ } else if (match("run")) {
+ simulate(tc, must_get_int());
+ } else if (match("dump")) {
+ dump(tc);
+ } else if (match("tree")) {
+ tree(tc);
+ } else if (match("check")) {
+ struct bridge *b;
+ struct stp *stp;
+ int bridge_no, port_no;
+
+ bridge_no = must_get_int();
+ if (bridge_no >= tc->n_bridges) {
+ err("no bridge numbered %d", bridge_no);
+ }
+ b = tc->bridges[bridge_no];
+ stp = b->stp;
+
+ must_match("=");
+
+ if (match("rootid")) {
+ uint64_t rootid;
+ must_match(":");
+ rootid = must_get_int();
+ if (match("^")) {
+ rootid |= (uint64_t) must_get_int() << 48;
+ } else {
+ rootid |= UINT64_C(0x8000) << 48;
+ }
+ if (stp_get_designated_root(stp) != rootid) {
+ warn("%s: root %"PRIx64", not %"PRIx64,
+ stp_get_name(stp), stp_get_designated_root(stp),
+ rootid);
+ }
+ }
+
+ if (match("root")) {
+ if (stp_get_root_path_cost(stp)) {
+ warn("%s: root path cost of root is %u but should be 0",
+ stp_get_name(stp), stp_get_root_path_cost(stp));
+ }
+ if (!stp_is_root_bridge(stp)) {
+ warn("%s: root is %"PRIx64", not %"PRIx64,
+ stp_get_name(stp),
+ stp_get_designated_root(stp), stp_get_bridge_id(stp));
+ }
+ for (port_no = 0; port_no < b->n_ports; port_no++) {
+ struct stp_port *p = stp_get_port(stp, port_no);
+ enum stp_state state = stp_port_get_state(p);
+ if (!(state & (STP_DISABLED | STP_FORWARDING))) {
+ warn("%s: root port %d in state %s",
+ stp_get_name(b->stp), port_no,
+ stp_state_name(state));
+ }
+ }
+ } else {
+ for (port_no = 0; port_no < STP_MAX_PORTS; port_no++) {
+ struct stp_port *p = stp_get_port(stp, port_no);
+ enum stp_state state;
+ if (token == NULL || match("D")) {
+ state = STP_DISABLED;
+ } else if (match("B")) {
+ state = STP_BLOCKING;
+ } else if (match("Li")) {
+ state = STP_LISTENING;
+ } else if (match("Le")) {
+ state = STP_LEARNING;
+ } else if (match("F")) {
+ state = STP_FORWARDING;
+ } else if (match("_")) {
+ continue;
+ } else {
+ err("unknown port state %s", token);
+ }
+ if (stp_port_get_state(p) != state) {
+ warn("%s port %d: state is %s but should be %s",
+ stp_get_name(stp), port_no,
+ stp_state_name(stp_port_get_state(p)),
+ stp_state_name(state));
+ }
+ if (state == STP_FORWARDING) {
+ struct stp_port *root_port = stp_get_root_port(stp);
+ if (match(":")) {
+ int root_path_cost = must_get_int();
+ if (p != root_port) {
+ warn("%s: port %d is not the root port",
+ stp_get_name(stp), port_no);
+ if (!root_port) {
+ warn("%s: (there is no root port)",
+ stp_get_name(stp));
+ } else {
+ warn("%s: (port %d is the root port)",
+ stp_get_name(stp),
+ stp_port_no(root_port));
+ }
+ } else if (root_path_cost
+ != stp_get_root_path_cost(stp)) {
+ warn("%s: root path cost is %u, should be %d",
+ stp_get_name(stp),
+ stp_get_root_path_cost(stp),
+ root_path_cost);
+ }
+ } else if (p == root_port) {
+ warn("%s: port %d is the root port but "
+ "not expected to be",
+ stp_get_name(stp), port_no);
+ }
+ }
+ }
+ }
+ if (n_warnings) {
+ exit(EXIT_FAILURE);
+ }
+ }
+ if (get_token()) {
+ err("trailing garbage on line");
+ }
+ }
+
+ return 0;
+}
diff --git a/tests/test-stp.sh b/tests/test-stp.sh
new file mode 100755
index 00000000..fd6acf54
--- /dev/null
+++ b/tests/test-stp.sh
@@ -0,0 +1,7 @@
+#! /bin/sh
+set -e
+progress=
+for d in ${stp_files}; do
+ echo "Testing $d..."
+ $SUPERVISOR ./tests/test-stp ${srcdir}/$d
+done
diff --git a/tests/test-type-props.c b/tests/test-type-props.c
new file mode 100644
index 00000000..67dabae8
--- /dev/null
+++ b/tests/test-type-props.c
@@ -0,0 +1,41 @@
+#include <config.h>
+#include "type-props.h"
+#include <stdio.h>
+#include <stdlib.h>
+
+#define MUST_SUCCEED(EXPRESSION) \
+ if (!(EXPRESSION)) { \
+ fprintf(stderr, "%s:%d: %s failed\n", \
+ __FILE__, __LINE__, #EXPRESSION); \
+ exit(EXIT_FAILURE); \
+ }
+
+#define TEST_TYPE(type, minimum, maximum, is_signed) \
+ MUST_SUCCEED(TYPE_IS_INTEGER(type)); \
+ MUST_SUCCEED(TYPE_IS_SIGNED(type) == is_signed); \
+ MUST_SUCCEED(TYPE_MAXIMUM(type) == maximum); \
+ MUST_SUCCEED(TYPE_MINIMUM(type) == minimum);
+
+int
+main (void)
+{
+ TEST_TYPE(char, CHAR_MIN, CHAR_MAX, (CHAR_MIN < 0));
+
+ TEST_TYPE(signed char, SCHAR_MIN, SCHAR_MAX, 1);
+ TEST_TYPE(short int, SHRT_MIN, SHRT_MAX, 1);
+ TEST_TYPE(int, INT_MIN, INT_MAX, 1);
+ TEST_TYPE(long int, LONG_MIN, LONG_MAX, 1);
+ TEST_TYPE(long long int, LLONG_MIN, LLONG_MAX, 1);
+
+ TEST_TYPE(unsigned char, 0, UCHAR_MAX, 0);
+ TEST_TYPE(unsigned short int, 0, USHRT_MAX, 0);
+ TEST_TYPE(unsigned int, 0, UINT_MAX, 0);
+ TEST_TYPE(unsigned long int, 0, ULONG_MAX, 0);
+ TEST_TYPE(unsigned long long int, 0, ULLONG_MAX, 0);
+
+ MUST_SUCCEED(!(TYPE_IS_INTEGER(float)));
+ MUST_SUCCEED(!(TYPE_IS_INTEGER(double)));
+ MUST_SUCCEED(!(TYPE_IS_INTEGER(long double)));
+
+ return 0;
+}
generated by cgit v1.2.3 (git 2.25.1) at 2024-07-07 13:05:01 +0000