[ovs-dev] [RFC HSA 2/4 V2] hsa-match: Sparse representation of a byte array derived from "struct match".
Alex Wang
alexw at nicira.com
Fri May 29 18:37:13 UTC 2015
For conducting Header Space Analysis (HSA), we convert the wildcarded
OpenFlow flow represented by 'struct match' into an encoded byte array.
To further save memory, we use a sparse array to represent such byte
array in the same way as 'struct miniflow'. So, this commit implements
the structs and functions for conversion between sparse array and
'struct match'.
This commit also implements the set operations (e.g. intersect, union,
complementation and difference) as functions.
Signed-off-by: Alex Wang <alexw at nicira.com>
---
PATCH -> V2:
- Fix sparse warnings.
- Adopt stylistic suggestions.
- Make the hsbm_intersect() and hsbm_init() more efficient.
---
lib/automake.mk | 2 +
lib/hsa-match.c | 372 ++++++++++++++++++++++++++++++++++++++++++++++++
lib/hsa-match.h | 93 ++++++++++++
tests/automake.mk | 2 +
tests/library.at | 5 +
tests/test-hsa-match.c | 177 +++++++++++++++++++++++
6 files changed, 651 insertions(+)
create mode 100644 lib/hsa-match.c
create mode 100644 lib/hsa-match.h
create mode 100644 tests/test-hsa-match.c
diff --git a/lib/automake.mk b/lib/automake.mk
index 7a34c1a..1a255c2 100644
--- a/lib/automake.mk
+++ b/lib/automake.mk
@@ -111,6 +111,8 @@ lib_libopenvswitch_la_SOURCES = \
lib/mac-learning.h \
lib/match.c \
lib/match.h \
+ lib/hsa-match.c \
+ lib/hsa-match.h \
lib/mcast-snooping.c \
lib/mcast-snooping.h \
lib/memory.c \
diff --git a/lib/hsa-match.c b/lib/hsa-match.c
new file mode 100644
index 0000000..c9d5854
--- /dev/null
+++ b/lib/hsa-match.c
@@ -0,0 +1,372 @@
+/*
+ * Copyright (c) 2015 Nicira, Inc.
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at:
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+#include <config.h>
+#include "hsa-match.h"
+#include "match.h"
+
+#include "util.h"
+
+/* Given 'hsbm' and 'match', initializes 'hsbm' with 'match'.
+ * Caller must guarantee, 'hsbm->values' is not assigned. */
+void
+hsbm_init(struct hsbm *hsbm, const struct match *match)
+{
+ const uint32_t *flow = (uint32_t *) &match->flow;
+ const uint32_t *wc = (uint32_t *) &match->wc;
+ size_t sz = 0;
+ size_t allocated_values = 0;
+ size_t i, j;
+
+ hsbm->map = 0;
+ hsbm->values = NULL;
+
+ /* Encodes every 4 bytes from 'match' to 8 bytes and sets the
+ * 'hsbm->map' and 'hsbm->values' correctly. */
+ for (i = 0; i < HSBM_VALUES_MAX; i++) {
+ uint64_t encoded_value = 0;
+
+ for (j = 0; j < 32; j++) {
+ uint8_t flow_bit = (flow[i] >> j) & 0x1;
+ uint8_t wc_bit = (wc[i] >> j) & 0x1;
+
+ /* If wc_bit is set, checks the bit. Otherwise, sets to 'x'. */
+ if (wc_bit) {
+ encoded_value |= ((uint64_t) (flow_bit ? HSBM_VALUE_BIT_EM_ONE
+ : HSBM_VALUE_BIT_EM_ZERO) << (2*j));
+ } else {
+ encoded_value |= ((uint64_t) HSBM_VALUE_BIT_WC << (2*j));
+ }
+ }
+
+ if (encoded_value == UINT64_MAX) {
+ hsbm->map |= (uint64_t) 0x1 << i;
+ } else {
+ if (sz >= allocated_values) {
+ hsbm->values = x2nrealloc(hsbm->values, &allocated_values,
+ sizeof *hsbm->values);
+ }
+ hsbm->values[sz++] = encoded_value;
+ }
+ }
+}
+
+/* Initializes 'hsbm' such that only one bit 'map_idx' in 'hsbm->map' is
+ * HSBM_MAP_BIT_NOT_WC. Correspondingly, sets the 'values[0]' so that
+ * the 'bit_idx' bit is set to 'bit_val'. */
+void
+hsbm_init_one_bit(struct hsbm *hsbm, size_t map_idx, size_t bit_idx,
+ size_t bit_val)
+{
+ ovs_assert(map_idx < HSBM_VALUES_MAX);
+ hsbm->map = ((uint64_t) 1 << HSBM_VALUES_MAX) - 1;
+ hsbm->map &= ~((uint64_t) 1 << map_idx);
+ hsbm->values = xzalloc(sizeof *hsbm->values);
+ hsbm->values[0] = ~((uint64_t) HSBM_VALUE_BIT_WC << 2*bit_idx)
+ | ((uint64_t) bit_val << 2*bit_idx);
+}
+
+/* Frees the 'values' pointer. */
+void
+hsbm_uninit(struct hsbm *hsbm)
+{
+ free(hsbm->values);
+}
+
+/* Destroys the 'hsbm'. */
+void
+hsbm_destroy(struct hsbm *hsbm)
+{
+ hsbm_uninit(hsbm);
+ free(hsbm);
+}
+
+/* Converts the 'hsbm' back to 'match'. */
+void
+hsbm_to_match(struct match *match, const struct hsbm *hsbm)
+{
+ uint32_t *flow = (uint32_t *) &match->flow;
+ uint32_t *wc = (uint32_t *) &match->wc;
+ size_t idx = 0;
+ size_t i;
+
+ for (i = 0; i < HSBM_VALUES_MAX; i++) {
+ if ((hsbm->map >> i) & 0x1) {
+ flow[i] = wc[i] = 0;
+ } else {
+ uint64_t encoded_value = hsbm->values[idx++];
+ uint32_t flow_value = 0;
+ uint32_t wc_value = 0;
+ size_t j;
+
+ for (j = 0; j < 32; j++) {
+ switch ((encoded_value >> (2*j)) & 0x3) {
+ /* wildcard unmasked (don't care), sets wc bit to '0'. */
+ case HSBM_VALUE_BIT_WC:
+ wc_value |= (uint32_t) 0 << j;
+ break;
+ /* exact match '1'. */
+ case HSBM_VALUE_BIT_EM_ONE:
+ flow_value |= (uint32_t) 1 << j;
+ wc_value |= (uint32_t) 1 << j;
+ break;
+ /* exact match '0'. */
+ case HSBM_VALUE_BIT_EM_ZERO:
+ flow_value |= (uint32_t) 0 << j;
+ wc_value |= (uint32_t) 1 << j;
+ break;
+ /* no intersection, error! */
+ default:
+ OVS_NOT_REACHED();
+ }
+ }
+ flow[i] = flow_value;
+ wc[i] = wc_value;
+ }
+ }
+}
+
+/* Returns true if 'hsbm1' is a subset of 'hsbm2'. */
+bool
+hsbm_check_subset(const struct hsbm *hsbm1,
+ const struct hsbm *hsbm2)
+{
+ uint64_t *vals1 = hsbm1->values;
+ uint64_t *vals2 = hsbm2->values;
+ size_t i;
+
+ for (i = 0; i < HSBM_VALUES_MAX; i++) {
+ uint8_t bit1 = (hsbm1->map >> i) & 0x1;
+ uint8_t bit2 = (hsbm2->map >> i) & 0x1;
+
+ if (bit1 == HSBM_MAP_BIT_WC && bit2 == HSBM_MAP_BIT_WC) {
+ /* Do nothing. */
+ } else if (bit1 == HSBM_MAP_BIT_WC && bit2 == HSBM_MAP_BIT_NOT_WC) {
+ /* 'hsbm2' is more specific, 'hsbm1' cannot be its subset. */
+ return false;
+ } else if (bit1 == HSBM_MAP_BIT_NOT_WC && bit2 == HSBM_MAP_BIT_WC) {
+ /* 'hsbm1' is more specific, skips the exact value. */
+ vals1++;
+ } else {
+ /* if both have specific values at index i, compares the values. */
+ if (*vals1++ & ~(*vals2++)) {
+ return false;
+ }
+ }
+ }
+
+ return true;
+}
+
+/* Creates and returns a 'hsbm_list'. */
+struct hsbm_list *
+hsbm_list_create(void)
+{
+ struct hsbm_list *ret = xmalloc(sizeof *ret);
+
+ list_init(&ret->list);
+
+ return ret;
+}
+
+/* Destroys the 'hsbm_list' and all its elements. */
+void
+hsbm_list_destroy(struct hsbm_list *hsbm_list)
+{
+ struct hsbm *iter, *next;
+
+ LIST_FOR_EACH_SAFE (iter, next, list_node, &hsbm_list->list) {
+ list_remove(&iter->list_node);
+ hsbm_destroy(iter);
+ }
+ free(hsbm_list);
+}
+
+/* Inserts the 'hsbm' to 'hsbm_list' while removing all duplicate, superset
+ * and subset. This function will take ownership of 'hsbm'. */
+void
+hsbm_insert_without_duplicate(struct hsbm_list *hsbm_list, struct hsbm *hsbm)
+{
+ struct hsbm *comp, *next;
+
+ LIST_FOR_EACH_SAFE (comp, next, list_node, &hsbm_list->list) {
+ bool is_subset = hsbm_check_subset(hsbm, comp);
+ bool is_superset = hsbm_check_subset(comp, hsbm);
+
+ if (is_subset) {
+ hsbm_destroy(hsbm);
+
+ return;
+ } else if (is_superset) {
+ /* If the to-be-inserted 'hsbm' is a superset of
+ * existing element, removes the existing one. */
+ list_remove(&comp->list_node);
+ hsbm_destroy(comp);
+ }
+ }
+ list_insert(&hsbm_list->list, &hsbm->list_node);
+}
+
+/* Given the 'hsbm', returns the complement of 'hsbm' as a list (union). */
+struct hsbm_list *
+hsbm_complement(struct hsbm *hsbm)
+{
+ struct hsbm_list *result = hsbm_list_create();
+ uint64_t *values = hsbm->values;
+ size_t i;
+
+ for (i = 0; i < HSBM_VALUES_MAX; i++) {
+ uint8_t map_bit = (hsbm->map >> i) & 0x1;
+
+ if (map_bit == 0) {
+ size_t j;
+
+ for (j = 0; j < 32; j++) {
+ struct hsbm *flap = NULL;
+
+ /* If a non-wildcarded bit is found, creates a flap. */
+ if (((*values >> 2*j) & 0x3) == HSBM_VALUE_BIT_EM_ZERO) {
+ flap = xmalloc(sizeof *flap);
+ hsbm_init_one_bit(flap, i, j, HSBM_VALUE_BIT_EM_ONE);
+ } else if (((*values >> 2*j) & 0x3) == HSBM_VALUE_BIT_EM_ONE) {
+ flap = xmalloc(sizeof *flap);
+ hsbm_init_one_bit(flap, i, j, HSBM_VALUE_BIT_EM_ZERO);
+ }
+ if (flap) {
+ list_insert(&result->list, &flap->list_node);
+ }
+ }
+ /* Jumps to next value. */
+ values++;
+ }
+ }
+
+ return result;
+}
+
+/* Given two 'hsbm's, returns the intersection of them.
+ * Returns NULL when the intersection is empty. */
+struct hsbm *
+hsbm_intersect(struct hsbm *comp_1, struct hsbm *comp_2)
+{
+ struct hsbm *result = xmalloc(sizeof *result);
+ uint64_t *vals_1 = comp_1->values;
+ uint64_t *vals_2 = comp_2->values;
+ uint64_t *vals_result;
+ size_t n_vals = 0;
+ size_t i;
+
+ result->map = comp_1->map & comp_2->map;
+ for (i = 0; i < HSBM_VALUES_MAX; i++) {
+ if (((result->map >> i) & 0x1) == 0) {
+ n_vals++;
+ }
+ }
+ vals_result = result->values = xmalloc(n_vals * sizeof *result->values);
+
+ for (i = 0; i < HSBM_VALUES_MAX; i++) {
+ uint8_t map_bit_1 = comp_1->map >> i & 0x1;
+ uint8_t map_bit_2 = comp_2->map >> i & 0x1;
+
+ if (map_bit_1 == HSBM_MAP_BIT_WC && map_bit_2 == HSBM_MAP_BIT_WC) {
+ /* Do nothing. */
+ } else if (map_bit_1 == HSBM_MAP_BIT_WC
+ && map_bit_2 == HSBM_MAP_BIT_NOT_WC) {
+ *vals_result++ = *vals_2++;
+ } else if (map_bit_1 == HSBM_MAP_BIT_NOT_WC
+ && map_bit_2 == HSBM_MAP_BIT_WC) {
+ *vals_result++ = *vals_1++;
+ } else {
+ uint64_t val = *vals_1++ & *vals_2++;
+
+ /* If intersection results in empty, returns NULL. */
+ if (!val) {
+ return NULL;
+ }
+ *vals_result++ = val;
+ }
+ }
+
+ return result;
+}
+
+/* Given two 'hsbm's, calculates the diff (hsbm_1 - hsbm_2) and returns
+ * the result in 'hsbm_list'. */
+struct hsbm_list *
+hsbm_diff(struct hsbm *hsbm_1, struct hsbm *hsbm_2)
+{
+ struct hsbm_list *result = hsbm_list_create();
+ struct hsbm_list *complement;
+ struct hsbm *iter;
+
+ complement = hsbm_complement(hsbm_2);
+
+ LIST_FOR_EACH (iter, list_node, &complement->list) {
+ struct hsbm *intersect = hsbm_intersect(hsbm_1, iter);
+
+ if (intersect) {
+ list_insert(&result->list, &intersect->list_node);
+ }
+ }
+ hsbm_list_destroy(complement);
+
+ return result;
+}
+
+/* Given the 'hsbm_list', checks if 'hsbm' can still find a match
+ * (non-NULL intersection) in 'hsbm_list'. Returns true if a match
+ * can be found, otherwise, false. */
+bool
+hsbm_list_check_hsbm(struct hsbm_list *hsbm_list, struct hsbm *hsbm)
+{
+ struct hsbm *iter;
+ bool ret = false;
+
+ LIST_FOR_EACH (iter, list_node, &hsbm_list->list) {
+ struct hsbm *intersect = hsbm_intersect(iter, hsbm);
+
+ if (intersect) {
+ hsbm_destroy(intersect);
+ ret = true;
+ break;
+ }
+ }
+
+ return ret;
+}
+
+/* Subtracts 'hsbm' from each element of 'hsbm_list', returns the result
+ * in another hsbm_list. The function will take ownership of 'hsbm_list'. */
+struct hsbm_list *
+hsbm_list_apply_hsbm(struct hsbm_list *hsbm_list, struct hsbm *hsbm)
+{
+ struct hsbm_list *result = hsbm_list_create();
+ struct hsbm *iter;
+
+ LIST_FOR_EACH (iter, list_node, &hsbm_list->list) {
+ struct hsbm_list *diff = hsbm_diff(iter, hsbm);
+ struct hsbm *tmp, *next;
+
+ LIST_FOR_EACH_SAFE (tmp, next, list_node, &diff->list) {
+ list_remove(&tmp->list_node);
+ hsbm_insert_without_duplicate(result, tmp);
+ }
+ hsbm_list_destroy(diff);
+ }
+ hsbm_list_destroy(hsbm_list);
+
+ return result;
+}
diff --git a/lib/hsa-match.h b/lib/hsa-match.h
new file mode 100644
index 0000000..f9f23e0
--- /dev/null
+++ b/lib/hsa-match.h
@@ -0,0 +1,93 @@
+/*
+ * Copyright (c) 2015 Nicira, Inc.
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at:
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+#ifndef HSA_MATCH_H
+#define HSA_MATCH_H 1
+
+#include "flow.h"
+#include "list.h"
+
+struct match;
+
+/*
+ * For conducting Header Space Analysis (HSA), we convert the wildcarded
+ * OpenFlow flow represented by 'struct match' into a byte array.
+ * Specifically, each bit in the OpenFlow flow is encoded into two bits:
+ *
+ * exact match 0 -> 01
+ * exact match 1 -> 10
+ * wildcard * -> 11
+ * empty -> 00
+ *
+ * We use '00' to indicate the empty bit resulted when intersecting two
+ * OpenFlow flows with exact match '0' and exact match '1' at same index.
+ *
+ * This conversion will generate a struct same size as 'struct match'.
+ * To save more space, we will use a sparse array to represent such byte
+ * array in the same way as 'struct miniflow'.
+ */
+#define HSBM_MAP_BIT_WC 1
+#define HSBM_MAP_BIT_NOT_WC 0
+
+#define HSBM_VALUE_BIT_EMPTY 0x0
+#define HSBM_VALUE_BIT_EM_ZERO 0x1
+#define HSBM_VALUE_BIT_EM_ONE 0x2
+#define HSBM_VALUE_BIT_WC 0x3
+
+/* A sparse representation of a byte array derived from "struct match".
+ *
+ * The 'map' member holds one bit for each uint64_t in the byte array. Each
+ * 1-bit indicates that the corresponding uint64_t is UINT64_MAX (i.e. all
+ * HSBM_VALUE_BIT_WC), each 0-bit that it is not all-one.
+ *
+ * The 'values' member is an array that has one element for each 0-bit in
+ * 'map'. The least-numbered 0-bit is in the first element of 'values', the
+ * next 0-bit is in the next array element, and so on.
+ */
+struct hsbm {
+ struct ovs_list list_node; /* In 'hsbm_list'. */
+ uint64_t map;
+ uint64_t *values;
+};
+
+/* Based on the description above, the maximum size of 'hsbm->values'
+ * is twice FLOW_U64S. */
+#define HSBM_VALUES_MAX (FLOW_U64S * 2)
+BUILD_ASSERT_DECL(HSBM_VALUES_MAX < 64);
+
+void hsbm_init(struct hsbm *, const struct match *);
+void hsbm_init_one_bit(struct hsbm *, size_t map_idx, size_t bit_idx,
+ size_t bit_val);
+void hsbm_uninit(struct hsbm *);
+void hsbm_destroy(struct hsbm *);
+void hsbm_to_match(struct match *, const struct hsbm *);
+bool hsbm_check_subset(const struct hsbm *, const struct hsbm *);
+
+/* List of 'struct hsbm's. */
+struct hsbm_list {
+ struct ovs_list list;
+};
+
+struct hsbm_list *hsbm_list_create(void);
+void hsbm_list_destroy(struct hsbm_list *);
+void hsbm_insert_without_duplicate(struct hsbm_list *, struct hsbm *);
+struct hsbm_list *hsbm_complement(struct hsbm *);
+struct hsbm *hsbm_intersect(struct hsbm *, struct hsbm *);
+struct hsbm_list *hsbm_diff(struct hsbm *, struct hsbm *);
+bool hsbm_list_check_hsbm(struct hsbm_list *, struct hsbm *);
+struct hsbm_list *hsbm_list_apply_hsbm(struct hsbm_list *, struct hsbm *);
+
+#endif /* hsa-match.h */
diff --git a/tests/automake.mk b/tests/automake.mk
index e63fb19..0ff8236 100644
--- a/tests/automake.mk
+++ b/tests/automake.mk
@@ -141,6 +141,7 @@ valgrind_wrappers = \
tests/valgrind/test-list \
tests/valgrind/test-lockfile \
tests/valgrind/test-multipath \
+ tests/valgrind/test-hsa-match \
tests/valgrind/test-odp \
tests/valgrind/test-ovsdb \
tests/valgrind/test-packets \
@@ -278,6 +279,7 @@ tests_ovstest_SOURCES = \
tests/test-list.c \
tests/test-lockfile.c \
tests/test-multipath.c \
+ tests/test-hsa-match.c \
tests/test-netflow.c \
tests/test-odp.c \
tests/test-packets.c \
diff --git a/tests/library.at b/tests/library.at
index cb1f858..c90d48f 100644
--- a/tests/library.at
+++ b/tests/library.at
@@ -209,3 +209,8 @@ AT_CLEANUP
AT_SETUP([use of public headers])
AT_CHECK([test-lib], [0], [])
AT_CLEANUP
+
+AT_SETUP([test hsa match])
+AT_CHECK([ovstest test-hsa-match], [0], [....
+])
+AT_CLEANUP
\ No newline at end of file
diff --git a/tests/test-hsa-match.c b/tests/test-hsa-match.c
new file mode 100644
index 0000000..2fea569
--- /dev/null
+++ b/tests/test-hsa-match.c
@@ -0,0 +1,177 @@
+/*
+ * Copyright (c) 2015 Nicira, Inc.
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at:
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+#include <config.h>
+#undef NDEBUG
+#include "hsa-match.h"
+#include "match.h"
+#include "util.h"
+#include <assert.h>
+#include "ovstest.h"
+
+static void
+test_init(void)
+{
+ struct hsbm hsbm, hsbm_one_bit;
+ struct match match, result;
+ uint64_t map, val, val0, val1;
+
+ /* Sets some fields. */
+ memset(&match, 0, sizeof match);
+ memset(&result, 0, sizeof result);
+ match_set_tun_id_masked(&match, (OVS_FORCE ovs_be64) 0x0123,
+ (OVS_FORCE ovs_be64) 0xFFFF);
+ match_set_reg(&match, 3, 0x1);
+
+ /* Expected results, please check lib/hsa-match.h for encoding details. */
+ map = UINT64_MAX & (((uint64_t) 1 << HSBM_VALUES_MAX) - 1);
+ map = map & ~((uint64_t) 1 << (offsetof(struct match, flow.tunnel.tun_id) / 4))
+ & ~((uint64_t) 1 << (offsetof(struct match, flow.regs[3]) / 4));
+ val0 = (uint64_t) 0xFFFFFFFF5556595AULL;
+ val1 = (uint64_t) 0x5555555555555556ULL;
+
+ /* Checks the conversion. */
+ hsbm_init(&hsbm, &match);
+ assert(hsbm.map == map && hsbm.values[0] == val0 && hsbm.values[1] == val1);
+ hsbm_to_match(&result, &hsbm);
+ assert(match_equal(&match, &result));
+
+ /* Tests just set one bit. */
+ hsbm_init_one_bit(&hsbm_one_bit, 10, 10, HSBM_VALUE_BIT_EM_ONE);
+ map = UINT64_MAX & (((uint64_t) 1 << HSBM_VALUES_MAX) - 1);
+ map = map & ~((uint64_t) 1 << 10);
+ val = ~((uint64_t) 0x3 << 20) | ((uint64_t) HSBM_VALUE_BIT_EM_ONE << 20);
+ assert(hsbm_one_bit.map == map && hsbm_one_bit.values[0] == val);
+
+ /* Cleans up. */
+ hsbm_uninit(&hsbm);
+ hsbm_uninit(&hsbm_one_bit);
+}
+
+static void
+test_check_subset(void)
+{
+ struct hsbm hsbm_superset, hsbm_subset;
+ struct match match_superset, match_subset;
+
+ memset(&match_superset, 0, sizeof match_superset);
+ memset(&match_subset, 0, sizeof match_subset);
+ /* Sets superset fields. */
+ match_set_tun_id_masked(&match_superset, (OVS_FORCE ovs_be64) 0x1200,
+ (OVS_FORCE ovs_be64) 0xFF00);
+ match_set_reg_masked(&match_superset, 3, 0x00FF0000, 0x00FF0000);
+ /* Sets subset fields. */
+ match_set_tun_id_masked(&match_subset, (OVS_FORCE ovs_be64) 0x1234,
+ (OVS_FORCE ovs_be64) 0xFFFF);
+ match_set_reg_masked(&match_subset, 3, 0x12FF3200, 0xFFFFFF00);
+
+ hsbm_init(&hsbm_superset, &match_superset);
+ hsbm_init(&hsbm_subset, &match_subset);
+
+ /* Checks subset. */
+ assert(hsbm_check_subset(&hsbm_subset, &hsbm_superset));
+ hsbm_uninit(&hsbm_superset);
+ hsbm_uninit(&hsbm_subset);
+}
+
+static void
+test_hsbm_complement(void)
+{
+ struct hsbm_list *result;
+ struct match match;
+ struct hsbm hsbm;
+ struct hsbm *iter;
+ size_t bit_idx = 0;
+
+ /* Sets just one field to all zero. */
+ memset(&match, 0, sizeof match);
+ match_set_reg(&match, 3, 0);
+ hsbm_init(&hsbm, &match);
+
+ result = hsbm_complement(&hsbm);
+
+ assert(list_size(&result->list) == 32);
+ LIST_FOR_EACH (iter, list_node, &result->list) {
+ assert(iter->map == hsbm.map);
+ assert(iter->values[0] ==
+ (~((uint64_t) HSBM_VALUE_BIT_WC << 2*bit_idx)
+ | ((uint64_t) HSBM_VALUE_BIT_EM_ONE << 2*bit_idx)));
+ bit_idx++;
+ }
+
+ hsbm_list_destroy(result);
+ hsbm_uninit(&hsbm);
+}
+
+static void
+test_hsbm_intersect(void)
+{
+ struct match match1, match2;
+ struct hsbm hsbm1, hsbm2;
+ struct hsbm *result;
+ uint64_t map, val0, val1, val2, val3;
+
+ memset(&match1, 0, sizeof match1);
+ match_set_tun_id_masked(&match1, (OVS_FORCE ovs_be64) 0x0123,
+ (OVS_FORCE ovs_be64) 0xFFFF);
+ match_set_reg(&match1, 3, 0x1);
+ hsbm_init(&hsbm1, &match1);
+
+ memset(&match2, 0, sizeof match2);
+ match_set_tun_id_masked(&match2, (OVS_FORCE ovs_be64) 0xABCD000000000000ULL,
+ (OVS_FORCE ovs_be64) 0xFFFF000000000000ULL);
+ match_set_reg(&match2, 4, 0);
+ hsbm_init(&hsbm2, &match2);
+
+ map = UINT64_MAX & (((uint64_t) 1 << HSBM_VALUES_MAX) - 1);
+ map = map
+ & ~((uint64_t) 1 << (offsetof(struct match, flow.tunnel.tun_id) / 4))
+ & ~((uint64_t) 1 << (offsetof(struct match, flow.tunnel.tun_id) / 4 + 1))
+ & ~((uint64_t) 1 << (offsetof(struct match, flow.regs[3]) / 4))
+ & ~((uint64_t) 1 << (offsetof(struct match, flow.regs[4]) / 4));
+ val0 = (uint64_t) 0xFFFFFFFF5556595AULL;
+ val1 = (uint64_t) 0x999AA5A6FFFFFFFFULL;
+ val2 = (uint64_t) 0x5555555555555556ULL;
+ val3 = (uint64_t) 0x5555555555555555ULL;
+
+ result = hsbm_intersect(&hsbm1, &hsbm2);
+ assert(result->map == map && result->values[0] == val0
+ && result->values[1] == val1 && result->values[2] == val2
+ && result->values[3] == val3);
+
+ hsbm_uninit(&hsbm1);
+ hsbm_uninit(&hsbm2);
+ hsbm_destroy(result);
+}
+
+static void
+run_test(void (*function)(void))
+{
+ function();
+ printf(".");
+}
+
+static void
+test_hsa_match_main(int argc OVS_UNUSED, char *argv[] OVS_UNUSED)
+{
+ run_test(test_init);
+ run_test(test_check_subset);
+ run_test(test_hsbm_complement);
+ run_test(test_hsbm_intersect);
+ printf("\n");
+}
+
+OVSTEST_REGISTER("test-hsa-match", test_hsa_match_main);
--
1.7.9.5
More information about the dev
mailing list