From patchwork Mon Oct 8 08:47:07 2018 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Bhargava Shastry X-Patchwork-Id: 980411 Return-Path: X-Original-To: incoming@patchwork.ozlabs.org Delivered-To: patchwork-incoming@bilbo.ozlabs.org Authentication-Results: ozlabs.org; spf=pass (mailfrom) smtp.mailfrom=openvswitch.org (client-ip=140.211.169.12; helo=mail.linuxfoundation.org; envelope-from=ovs-dev-bounces@openvswitch.org; receiver=) Authentication-Results: ozlabs.org; dmarc=none (p=none dis=none) header.from=sect.tu-berlin.de Received: from mail.linuxfoundation.org (mail.linuxfoundation.org [140.211.169.12]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (No client certificate requested) by ozlabs.org (Postfix) with ESMTPS id 42TDWc3KxCz9sBq for ; Mon, 8 Oct 2018 19:47:23 +1100 (AEDT) Received: from mail.linux-foundation.org (localhost [127.0.0.1]) by mail.linuxfoundation.org (Postfix) with ESMTP id C94C9D12; Mon, 8 Oct 2018 08:47:19 +0000 (UTC) X-Original-To: dev@openvswitch.org Delivered-To: ovs-dev@mail.linuxfoundation.org Received: from smtp1.linuxfoundation.org (smtp1.linux-foundation.org [172.17.192.35]) by mail.linuxfoundation.org (Postfix) with ESMTPS id 836B1CD2 for ; Mon, 8 Oct 2018 08:47:18 +0000 (UTC) X-Greylist: domain auto-whitelisted by SQLgrey-1.7.6 Received: from mail.sec.t-labs.tu-berlin.de (mail.sec.t-labs.tu-berlin.de [130.149.230.43]) by smtp1.linuxfoundation.org (Postfix) with ESMTP id 83BED4DA for ; Mon, 8 Oct 2018 08:47:16 +0000 (UTC) From: bshastry@sect.tu-berlin.de To: dev@openvswitch.org Date: Mon, 8 Oct 2018 10:47:07 +0200 Message-Id: <20181008084707.8652-1-bshastry@sect.tu-berlin.de> X-Mailer: git-send-email 2.17.1 X-Spam-Status: No, score=-1.9 required=5.0 tests=BAYES_00 autolearn=ham version=3.3.1 X-Spam-Checker-Version: SpamAssassin 3.3.1 (2010-03-16) on smtp1.linux-foundation.org Cc: Bhargava Shastry Subject: [ovs-dev] [PATCH v2] ossfuzz: Speed up flow extract fuzzing by X-BeenThere: ovs-dev@openvswitch.org X-Mailman-Version: 2.1.12 Precedence: list List-Id: List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , MIME-Version: 1.0 Sender: ovs-dev-bounces@openvswitch.org Errors-To: ovs-dev-bounces@openvswitch.org From: Bhargava Shastry Accepts fixes suggested by 0-day robot. Refactor miniflow tests out of flow_extract_target.c into a new target called miniflow_target.c The biggest motivation for this massive (7-10x) increase in fuzzing speed. Prior to the refactoring, we were doing roughly 900 executions per second on flow_extract_target. Now, we are doing roughly 6000 executions per second on the flow_extract_target and roughly 9000 executions per second on the new miniflow_target. Moving forward, creating micro fuzz targets that are really fast is a better strategy. Since all these micro targets can be scheduled in parallel by oss-fuzz, the test throughput increases by a non-trivial amount. Signed-off-by: Bhargava Shastry --- tests/oss-fuzz/automake.mk | 12 +- tests/oss-fuzz/config/miniflow_target.options | 3 + tests/oss-fuzz/flow_extract_target.c | 367 ++---------------- tests/oss-fuzz/miniflow_target.c | 366 +++++++++++++++++ 4 files changed, 410 insertions(+), 338 deletions(-) create mode 100644 tests/oss-fuzz/config/miniflow_target.options create mode 100644 tests/oss-fuzz/miniflow_target.c diff --git a/tests/oss-fuzz/automake.mk b/tests/oss-fuzz/automake.mk index 4fbdb4c2b..2c506be3d 100644 --- a/tests/oss-fuzz/automake.mk +++ b/tests/oss-fuzz/automake.mk @@ -3,7 +3,8 @@ OSS_FUZZ_TARGETS = \ tests/oss-fuzz/json_parser_target \ tests/oss-fuzz/ofp_print_target \ tests/oss-fuzz/expr_parse_target \ - tests/oss-fuzz/odp_target + tests/oss-fuzz/odp_target \ + tests/oss-fuzz/miniflow_target EXTRA_PROGRAMS += $(OSS_FUZZ_TARGETS) oss-fuzz-targets: $(OSS_FUZZ_TARGETS) @@ -38,12 +39,19 @@ tests_oss_fuzz_odp_target_SOURCES = \ tests_oss_fuzz_odp_target_LDADD = lib/libopenvswitch.la tests_oss_fuzz_odp_target_LDFLAGS = $(LIB_FUZZING_ENGINE) -lc++ +tests_oss_fuzz_miniflow_target_SOURCES = \ + tests/oss-fuzz/miniflow_target.c \ + tests/oss-fuzz/fuzzer.h +tests_oss_fuzz_miniflow_target_LDADD = lib/libopenvswitch.la +tests_oss_fuzz_miniflow_target_LDFLAGS = $(LIB_FUZZING_ENGINE) -lc++ + EXTRA_DIST += \ tests/oss-fuzz/config/flow_extract_target.options \ tests/oss-fuzz/config/json_parser_target.options \ tests/oss-fuzz/config/ofp_print_target.options \ tests/oss-fuzz/config/expr_parse_target.options \ tests/oss-fuzz/config/odp_target.options \ + tests/oss-fuzz/config/miniflow_target.options \ tests/oss-fuzz/config/ovs.dict \ tests/oss-fuzz/config/expr.dict \ - tests/oss-fuzz/config/odp.dict + tests/oss-fuzz/config/odp.dict \ No newline at end of file diff --git a/tests/oss-fuzz/config/miniflow_target.options b/tests/oss-fuzz/config/miniflow_target.options new file mode 100644 index 000000000..4849f282d --- /dev/null +++ b/tests/oss-fuzz/config/miniflow_target.options @@ -0,0 +1,3 @@ +[libfuzzer] +dict = ovs.dict +close_fd_mask = 3 \ No newline at end of file diff --git a/tests/oss-fuzz/flow_extract_target.c b/tests/oss-fuzz/flow_extract_target.c index 3ad1a9628..9e82675e3 100644 --- a/tests/oss-fuzz/flow_extract_target.c +++ b/tests/oss-fuzz/flow_extract_target.c @@ -10,338 +10,36 @@ #include "classifier-private.h" static void -shuffle_u32s(uint32_t *p, size_t n) +test_flow_hash(const struct flow *flow) { - for (; n > 1; n--, p++) { - uint32_t *q = &p[random_range(n)]; - uint32_t tmp = *p; - *p = *q; - *q = tmp; - } -} - -/* Returns a copy of 'src'. The caller must eventually free the returned - * miniflow with free(). */ -static struct miniflow * -miniflow_clone__(const struct miniflow *src) -{ - struct miniflow *dst; - size_t data_size; - - data_size = miniflow_alloc(&dst, 1, src); - miniflow_clone(dst, src, data_size / sizeof(uint64_t)); - return dst; -} - -/* Returns a hash value for 'flow', given 'basis'. */ -static inline uint32_t -miniflow_hash__(const struct miniflow *flow, uint32_t basis) -{ - const uint64_t *p = miniflow_get_values(flow); - size_t n_values = miniflow_n_values(flow); - struct flowmap hash_map = FLOWMAP_EMPTY_INITIALIZER; - uint32_t hash = basis; - size_t idx; - - FLOWMAP_FOR_EACH_INDEX (idx, flow->map) { - uint64_t value = *p++; - - if (value) { - hash = hash_add64(hash, value); - flowmap_set(&hash_map, idx, 1); - } - } - map_t map; - FLOWMAP_FOR_EACH_MAP (map, hash_map) { - hash = hash_add64(hash, map); - } - - return hash_finish(hash, n_values); -} - -static uint32_t -random_value(void) -{ - static const uint32_t values_[] = - { 0xffffffff, 0xaaaaaaaa, 0x55555555, 0x80000000, - 0x00000001, 0xface0000, 0x00d00d1e, 0xdeadbeef }; - - return values_[random_range(ARRAY_SIZE(values_))]; -} - -static bool -choose(unsigned int n, unsigned int *idxp) -{ - if (*idxp < n) { - return true; - } else { - *idxp -= n; - return false; - } -} - -#define FLOW_U32S (FLOW_U64S * 2) - -static bool -init_consecutive_values(int n_consecutive, struct flow *flow, - unsigned int *idxp) -{ - uint32_t *flow_u32 = (uint32_t *) flow; - - if (choose(FLOW_U32S - n_consecutive + 1, idxp)) { - int i; - - for (i = 0; i < n_consecutive; i++) { - flow_u32[*idxp + i] = random_value(); - } - return true; - } else { - return false; - } -} - -static bool -next_random_flow(struct flow *flow, unsigned int idx) -{ - uint32_t *flow_u32 = (uint32_t *) flow; - - memset(flow, 0, sizeof *flow); - - /* Empty flow. */ - if (choose(1, &idx)) { - return true; - } - - /* All flows with a small number of consecutive nonzero values. */ - for (int i = 1; i <= 4; i++) { - if (init_consecutive_values(i, flow, &idx)) { - return true; - } - } - - /* All flows with a large number of consecutive nonzero values. */ - for (int i = FLOW_U32S - 4; i <= FLOW_U32S; i++) { - if (init_consecutive_values(i, flow, &idx)) { - return true; - } - } - - /* All flows with exactly two nonconsecutive nonzero values. */ - if (choose((FLOW_U32S - 1) * (FLOW_U32S - 2) / 2, &idx)) { - int ofs1; - - for (ofs1 = 0; ofs1 < FLOW_U32S - 2; ofs1++) { - int ofs2; - - for (ofs2 = ofs1 + 2; ofs2 < FLOW_U32S; ofs2++) { - if (choose(1, &idx)) { - flow_u32[ofs1] = random_value(); - flow_u32[ofs2] = random_value(); - return true; - } - } - } - OVS_NOT_REACHED(); - } - - /* 16 randomly chosen flows with N >= 3 nonzero values. */ - if (choose(16 * (FLOW_U32S - 4), &idx)) { - int n = idx / 16 + 3; - - for (int i = 0; i < n; i++) { - flow_u32[i] = random_value(); - } - shuffle_u32s(flow_u32, FLOW_U32S); - - return true; - } - - return false; -} - -static void -any_random_flow(struct flow *flow) -{ - static unsigned int max; - if (!max) { - while (next_random_flow(flow, max)) { - max++; - } - } - - next_random_flow(flow, random_range(max)); -} - -static void -toggle_masked_flow_bits(struct flow *flow, const struct flow_wildcards *mask) -{ - const uint32_t *mask_u32 = (const uint32_t *) &mask->masks; - uint32_t *flow_u32 = (uint32_t *) flow; - int i; - - for (i = 0; i < FLOW_U32S; i++) { - if (mask_u32[i] != 0) { - uint32_t bit; - - do { - bit = 1u << random_range(32); - } while (!(bit & mask_u32[i])); - flow_u32[i] ^= bit; - } - } -} - -static void -wildcard_extra_bits(struct flow_wildcards *mask) -{ - uint32_t *mask_u32 = (uint32_t *) &mask->masks; - int i; - - for (i = 0; i < FLOW_U32S; i++) { - if (mask_u32[i] != 0) { - uint32_t bit; - - do { - bit = 1u << random_range(32); - } while (!(bit & mask_u32[i])); - mask_u32[i] &= ~bit; - } - } -} - -static void -test_miniflow(struct flow *flow) -{ - struct miniflow *miniflow, *miniflow2, *miniflow3; - struct flow flow2, flow3; - struct flow_wildcards mask; - struct minimask *minimask; - int i; - - const uint64_t *flow_u64 = (const uint64_t *) flow; - - /* Convert flow to miniflow. */ - miniflow = miniflow_create(flow); - - /* Check that the flow equals its miniflow. */ - for (i = 0; i < FLOW_MAX_VLAN_HEADERS; i++) { - assert(miniflow_get_vid(miniflow, i) == - vlan_tci_to_vid(flow->vlans[i].tci)); - } - for (i = 0; i < FLOW_U64S; i++) { - assert(miniflow_get(miniflow, i) == flow_u64[i]); - } - - /* Check that the miniflow equals itself. */ - assert(miniflow_equal(miniflow, miniflow)); - - /* Convert miniflow back to flow and verify that it's the same. */ - miniflow_expand(miniflow, &flow2); - assert(flow_equal(flow, &flow2)); - /* Check that copying a miniflow works properly. */ - miniflow2 = miniflow_clone__(miniflow); - assert(miniflow_equal(miniflow, miniflow2)); - assert(miniflow_hash__(miniflow, 0) == miniflow_hash__(miniflow2, 0)); - miniflow_expand(miniflow2, &flow3); - assert(flow_equal(flow, &flow3)); - - /* Check that masked matches work as expected for identical flows and - * miniflows. */ - do { - next_random_flow(&mask.masks, 1); - } while (flow_wildcards_is_catchall(&mask)); - minimask = minimask_create(&mask); - assert(minimask_is_catchall(minimask) - == flow_wildcards_is_catchall(&mask)); - assert(miniflow_equal_in_minimask(miniflow, miniflow2, minimask)); - assert(miniflow_equal_flow_in_minimask(miniflow, &flow2, minimask)); - assert(miniflow_hash_in_minimask(miniflow, minimask, 0x12345678) == - flow_hash_in_minimask(flow, minimask, 0x12345678)); - assert(minimask_hash(minimask, 0) == - miniflow_hash__(&minimask->masks, 0)); - - /* Check that masked matches work as expected for differing flows and - * miniflows. */ - toggle_masked_flow_bits(&flow2, &mask); - assert(!miniflow_equal_flow_in_minimask(miniflow, &flow2, minimask)); - miniflow3 = miniflow_create(&flow2); - assert(!miniflow_equal_in_minimask(miniflow, miniflow3, minimask)); - - free(miniflow); - free(miniflow2); - free(miniflow3); - free(minimask); -} - -static void -test_minimask_has_extra(struct flow *flow) -{ - struct flow_wildcards catchall; - struct minimask *minicatchall; - - flow_wildcards_init_catchall(&catchall); - minicatchall = minimask_create(&catchall); - assert(minimask_is_catchall(minicatchall)); - - struct flow_wildcards mask; - struct minimask *minimask; - - mask.masks = *flow; - minimask = minimask_create(&mask); - assert(!minimask_has_extra(minimask, minimask)); - assert(minimask_has_extra(minicatchall, minimask) - == !minimask_is_catchall(minimask)); - if (!minimask_is_catchall(minimask)) { - struct minimask *minimask2; - - wildcard_extra_bits(&mask); - minimask2 = minimask_create(&mask); - assert(minimask_has_extra(minimask2, minimask)); - assert(!minimask_has_extra(minimask, minimask2)); - free(minimask2); - } - - free(minimask); - free(minicatchall); + uint32_t hash = flow_hash_5tuple(flow, 0); + hash = flow_hash_symmetric_l4(flow, 0); + hash = flow_hash_symmetric_l2(flow, 0); + hash = flow_hash_symmetric_l3l4(flow, 0, NULL); + hash = flow_hash_symmetric_l3(flow, 0); + hash = flow_hash_fields(flow, NX_HASH_FIELDS_ETH_SRC, hash); + hash = flow_hash_fields(flow, NX_HASH_FIELDS_SYMMETRIC_L4, hash); + hash = flow_hash_fields(flow, NX_HASH_FIELDS_SYMMETRIC_L3L4, hash); + hash = flow_hash_fields(flow, NX_HASH_FIELDS_SYMMETRIC_L3L4_UDP, hash); + hash = flow_hash_fields(flow, NX_HASH_FIELDS_NW_SRC, hash); + hash = flow_hash_fields(flow, NX_HASH_FIELDS_NW_DST, hash); + hash = flow_hash_fields(flow, NX_HASH_FIELDS_SYMMETRIC_L3, hash); + ignore(hash); } static void -test_minimask_combine(struct flow *flow) +test_flow_mask(const struct flow *flow) { struct flow_wildcards catchall; - struct minimask *minicatchall; flow_wildcards_init_catchall(&catchall); - minicatchall = minimask_create(&catchall); - assert(minimask_is_catchall(minicatchall)); - - struct minimask *minimask, *minimask2; - struct flow_wildcards mask, mask2, combined, combined2; - struct { - struct minimask minicombined; - uint64_t storage[FLOW_U64S]; - } m; - struct flow flow2; - - mask.masks = *flow; - minimask = minimask_create(&mask); - - minimask_combine(&m.minicombined, minimask, minicatchall, m.storage); - assert(minimask_is_catchall(&m.minicombined)); - - any_random_flow(&flow2); - mask2.masks = flow2; - minimask2 = minimask_create(&mask2); - - minimask_combine(&m.minicombined, minimask, minimask2, m.storage); - flow_wildcards_and(&combined, &mask, &mask2); - minimask_expand(&m.minicombined, &combined2); - assert(flow_wildcards_equal(&combined, &combined2)); - - free(minimask); - free(minimask2); - - free(minicatchall); + flow_mask_hash_fields(flow, &catchall, NX_HASH_FIELDS_ETH_SRC); + flow_mask_hash_fields(flow, &catchall, NX_HASH_FIELDS_SYMMETRIC_L4); + flow_mask_hash_fields(flow, &catchall, NX_HASH_FIELDS_SYMMETRIC_L3L4); + flow_mask_hash_fields(flow, &catchall, NX_HASH_FIELDS_SYMMETRIC_L3L4_UDP); + flow_mask_hash_fields(flow, &catchall, NX_HASH_FIELDS_NW_SRC); + flow_mask_hash_fields(flow, &catchall, NX_HASH_FIELDS_NW_DST); + flow_mask_hash_fields(flow, &catchall, NX_HASH_FIELDS_SYMMETRIC_L3); } int @@ -362,28 +60,25 @@ LLVMFuzzerTestOneInput(const uint8_t *data, size_t size) ignore(tcp_flags); } - /* Do miniflow tests. */ - test_miniflow(&flow); - test_minimask_has_extra(&flow); - test_minimask_combine(&flow); - /* Parse TCP flags. */ if (dp_packet_size(&packet) >= ETH_HEADER_LEN) { uint16_t tcp_flags = parse_tcp_flags(&packet); ignore(tcp_flags); } + /* Count headers. */ + int count = flow_count_vlan_headers(&flow); + ignore(count); + /* Extract metadata. */ struct match flow_metadata; flow_get_metadata(&flow, &flow_metadata); /* Hashing functions. */ - uint32_t hash = flow_hash_5tuple(&flow, 0); - hash = flow_hash_symmetric_l4(&flow, 0); - hash = flow_hash_symmetric_l2(&flow, 0); - hash = flow_hash_symmetric_l3l4(&flow, 0, NULL); - hash = flow_hash_symmetric_l3(&flow, 0); - ignore(hash); + test_flow_hash(&flow); + + /* Masking functions. */ + test_flow_mask(&flow); /* Convert flow to match. */ struct match match; @@ -402,4 +97,4 @@ LLVMFuzzerTestOneInput(const uint8_t *data, size_t size) ovs_hex_dump(stdout, &ext_match, sizeof ext_match, 0, false); return 0; -} +} \ No newline at end of file diff --git a/tests/oss-fuzz/miniflow_target.c b/tests/oss-fuzz/miniflow_target.c new file mode 100644 index 000000000..8b6569e35 --- /dev/null +++ b/tests/oss-fuzz/miniflow_target.c @@ -0,0 +1,366 @@ +#include +#include "classifier.h" +#include "fuzzer.h" +#include "dp-packet.h" +#include "flow.h" +#include "openvswitch/ofp-match.h" +#include "openvswitch/ofp-print.h" +#include "openvswitch/match.h" +#include "classifier-private.h" +#include "util.h" + +static void +shuffle_u32s(uint32_t *p, size_t n) +{ + for (; n > 1; n--, p++) { + uint32_t *q = &p[random_range(n)]; + uint32_t tmp = *p; + *p = *q; + *q = tmp; + } +} + +/* Returns a copy of 'src'. The caller must eventually free the returned + * miniflow with free(). */ +static struct miniflow * +miniflow_clone__(const struct miniflow *src) +{ + struct miniflow *dst; + size_t data_size; + + data_size = miniflow_alloc(&dst, 1, src); + miniflow_clone(dst, src, data_size / sizeof(uint64_t)); + return dst; +} + +/* Returns a hash value for 'flow', given 'basis'. */ +static inline uint32_t +miniflow_hash__(const struct miniflow *flow, uint32_t basis) +{ + const uint64_t *p = miniflow_get_values(flow); + size_t n_values = miniflow_n_values(flow); + struct flowmap hash_map = FLOWMAP_EMPTY_INITIALIZER; + uint32_t hash = basis; + size_t idx; + + FLOWMAP_FOR_EACH_INDEX (idx, flow->map) { + uint64_t value = *p++; + + if (value) { + hash = hash_add64(hash, value); + flowmap_set(&hash_map, idx, 1); + } + } + map_t map; + FLOWMAP_FOR_EACH_MAP (map, hash_map) { + hash = hash_add64(hash, map); + } + + return hash_finish(hash, n_values); +} + +static uint32_t +random_value(void) +{ + static const uint32_t values_[] = + { 0xffffffff, 0xaaaaaaaa, 0x55555555, 0x80000000, + 0x00000001, 0xface0000, 0x00d00d1e, 0xdeadbeef }; + + return values_[random_range(ARRAY_SIZE(values_))]; +} + +static bool +choose(unsigned int n, unsigned int *idxp) +{ + if (*idxp < n) { + return true; + } else { + *idxp -= n; + return false; + } +} + +#define FLOW_U32S (FLOW_U64S * 2) + +static bool +init_consecutive_values(int n_consecutive, struct flow *flow, + unsigned int *idxp) +{ + uint32_t *flow_u32 = (uint32_t *) flow; + + if (choose(FLOW_U32S - n_consecutive + 1, idxp)) { + int i; + + for (i = 0; i < n_consecutive; i++) { + flow_u32[i + *idxp] = random_value(); + } + return true; + } else { + return false; + } +} + +static bool +next_random_flow(struct flow *flow, unsigned int idx) +{ + uint32_t *flow_u32 = (uint32_t *) flow; + + memset(flow, 0, sizeof *flow); + + /* Empty flow. */ + if (choose(1, &idx)) { + return true; + } + + /* All flows with a small number of consecutive nonzero values. */ + for (int i = 1; i <= 4; i++) { + if (init_consecutive_values(i, flow, &idx)) { + return true; + } + } + + /* All flows with a large number of consecutive nonzero values. */ + for (int i = FLOW_U32S - 4; i <= FLOW_U32S; i++) { + if (init_consecutive_values(i, flow, &idx)) { + return true; + } + } + + /* All flows with exactly two nonconsecutive nonzero values. */ + if (choose((FLOW_U32S - 1) * (FLOW_U32S - 2) / 2, &idx)) { + int ofs1; + + for (ofs1 = 0; ofs1 < FLOW_U32S - 2; ofs1++) { + int ofs2; + + for (ofs2 = ofs1 + 2; ofs2 < FLOW_U32S; ofs2++) { + if (choose(1, &idx)) { + flow_u32[ofs1] = random_value(); + flow_u32[ofs2] = random_value(); + return true; + } + } + } + OVS_NOT_REACHED(); + } + + /* 16 randomly chosen flows with N >= 3 nonzero values. */ + if (choose(16 * (FLOW_U32S - 4), &idx)) { + int n = idx / 16 + 3; + + for (int i = 0; i < n; i++) { + flow_u32[i] = random_value(); + } + shuffle_u32s(flow_u32, FLOW_U32S); + + return true; + } + + return false; +} + +static void +any_random_flow(struct flow *flow) +{ + static unsigned int max; + if (!max) { + while (next_random_flow(flow, max)) { + max++; + } + } + + next_random_flow(flow, random_range(max)); +} + +static void +toggle_masked_flow_bits(struct flow *flow, const struct flow_wildcards *mask) +{ + const uint32_t *mask_u32 = (const uint32_t *) &mask->masks; + uint32_t *flow_u32 = (uint32_t *) flow; + int i; + + for (i = 0; i < FLOW_U32S; i++) { + if (mask_u32[i] != 0) { + uint32_t bit; + + do { + bit = 1u << random_range(32); + } while (!(bit & mask_u32[i])); + flow_u32[i] ^= bit; + } + } +} + +static void +wildcard_extra_bits(struct flow_wildcards *mask) +{ + uint32_t *mask_u32 = (uint32_t *) &mask->masks; + int i; + + for (i = 0; i < FLOW_U32S; i++) { + if (mask_u32[i] != 0) { + uint32_t bit; + + do { + bit = 1u << random_range(32); + } while (!(bit & mask_u32[i])); + mask_u32[i] &= ~bit; + } + } +} + +static void +test_miniflow(struct flow *flow) +{ + struct miniflow *miniflow, *miniflow2, *miniflow3; + struct flow flow2, flow3; + struct flow_wildcards mask; + struct minimask *minimask; + int i; + + const uint64_t *flow_u64 = (const uint64_t *) flow; + + /* Convert flow to miniflow. */ + miniflow = miniflow_create(flow); + + /* Obtain miniflow hash. */ + uint32_t hash = miniflow_hash_5tuple(miniflow, 0); + ignore(hash); + + /* Check that the flow equals its miniflow. */ + for (i = 0; i < FLOW_MAX_VLAN_HEADERS; i++) { + ovs_assert(miniflow_get_vid(miniflow, i) == + vlan_tci_to_vid(flow->vlans[i].tci)); + } + for (i = 0; i < FLOW_U64S; i++) { + ovs_assert(miniflow_get(miniflow, i) == flow_u64[i]); + } + + /* Check that the miniflow equals itself. */ + ovs_assert(miniflow_equal(miniflow, miniflow)); + + /* Convert miniflow back to flow and verify that it's the same. */ + miniflow_expand(miniflow, &flow2); + ovs_assert(flow_equal(flow, &flow2)); + /* Check that copying a miniflow works properly. */ + miniflow2 = miniflow_clone__(miniflow); + ovs_assert(miniflow_equal(miniflow, miniflow2)); + ovs_assert(miniflow_hash__(miniflow, 0) == miniflow_hash__(miniflow2, 0)); + miniflow_expand(miniflow2, &flow3); + ovs_assert(flow_equal(flow, &flow3)); + + /* Check that masked matches work as expected for identical flows and + * miniflows. */ + do { + next_random_flow(&mask.masks, 1); + } while (flow_wildcards_is_catchall(&mask)); + minimask = minimask_create(&mask); + ovs_assert(minimask_is_catchall(minimask) + == flow_wildcards_is_catchall(&mask)); + ovs_assert(miniflow_equal_in_minimask(miniflow, miniflow2, minimask)); + ovs_assert(miniflow_equal_flow_in_minimask(miniflow, &flow2, minimask)); + ovs_assert(miniflow_hash_in_minimask(miniflow, minimask, 0x12345678) == + flow_hash_in_minimask(flow, minimask, 0x12345678)); + ovs_assert(minimask_hash(minimask, 0) == + miniflow_hash__(&minimask->masks, 0)); + + /* Check that masked matches work as expected for differing flows and + * miniflows. */ + toggle_masked_flow_bits(&flow2, &mask); + ovs_assert(!miniflow_equal_flow_in_minimask(miniflow, &flow2, minimask)); + miniflow3 = miniflow_create(&flow2); + ovs_assert(!miniflow_equal_in_minimask(miniflow, miniflow3, minimask)); + + free(miniflow); + free(miniflow2); + free(miniflow3); + free(minimask); +} + +static void +test_minimask_has_extra(struct flow *flow) +{ + struct flow_wildcards catchall; + struct minimask *minicatchall; + + flow_wildcards_init_catchall(&catchall); + minicatchall = minimask_create(&catchall); + ovs_assert(minimask_is_catchall(minicatchall)); + + struct flow_wildcards mask; + struct minimask *minimask; + + mask.masks = *flow; + minimask = minimask_create(&mask); + ovs_assert(!minimask_has_extra(minimask, minimask)); + ovs_assert(minimask_has_extra(minicatchall, minimask) + == !minimask_is_catchall(minimask)); + if (!minimask_is_catchall(minimask)) { + struct minimask *minimask2; + + wildcard_extra_bits(&mask); + minimask2 = minimask_create(&mask); + ovs_assert(minimask_has_extra(minimask2, minimask)); + ovs_assert(!minimask_has_extra(minimask, minimask2)); + free(minimask2); + } + + free(minimask); + free(minicatchall); +} + +static void +test_minimask_combine(struct flow *flow) +{ + struct flow_wildcards catchall; + struct minimask *minicatchall; + + flow_wildcards_init_catchall(&catchall); + minicatchall = minimask_create(&catchall); + ovs_assert(minimask_is_catchall(minicatchall)); + + struct minimask *minimask, *minimask2; + struct flow_wildcards mask, mask2, combined, combined2; + struct { + struct minimask minicombined; + uint64_t storage[FLOW_U64S]; + } m; + struct flow flow2; + + mask.masks = *flow; + minimask = minimask_create(&mask); + + minimask_combine(&m.minicombined, minimask, minicatchall, m.storage); + ovs_assert(minimask_is_catchall(&m.minicombined)); + + any_random_flow(&flow2); + mask2.masks = flow2; + minimask2 = minimask_create(&mask2); + + minimask_combine(&m.minicombined, minimask, minimask2, m.storage); + flow_wildcards_and(&combined, &mask, &mask2); + minimask_expand(&m.minicombined, &combined2); + ovs_assert(flow_wildcards_equal(&combined, &combined2)); + + free(minimask); + free(minimask2); + + free(minicatchall); +} + + +int +LLVMFuzzerTestOneInput(const uint8_t *data, size_t size) +{ + struct dp_packet packet; + struct flow flow; + dp_packet_use_const(&packet, data, size); + flow_extract(&packet, &flow); + + /* Do miniflow tests. */ + test_miniflow(&flow); + test_minimask_has_extra(&flow); + test_minimask_combine(&flow); + + return 0; +}