From patchwork Tue Sep 5 23:59:48 2017 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: "Wang, Yipeng1" X-Patchwork-Id: 28398 Return-Path: X-Original-To: patchwork@dpdk.org Delivered-To: patchwork@dpdk.org Received: from [92.243.14.124] (localhost [IPv6:::1]) by dpdk.org (Postfix) with ESMTP id 216335A6E; Wed, 6 Sep 2017 02:00:52 +0200 (CEST) Received: from mga07.intel.com (mga07.intel.com [134.134.136.100]) by dpdk.org (Postfix) with ESMTP id C51A7374F for ; Wed, 6 Sep 2017 02:00:48 +0200 (CEST) Received: from fmsmga003.fm.intel.com ([10.253.24.29]) by orsmga105.jf.intel.com with ESMTP; 05 Sep 2017 17:00:48 -0700 X-ExtLoop1: 1 X-IronPort-AV: E=Sophos;i="5.41,481,1498546800"; d="scan'208";a="897423627" Received: from bdw-yipeng.jf.intel.com ([10.54.81.30]) by FMSMGA003.fm.intel.com with ESMTP; 05 Sep 2017 17:00:47 -0700 From: Yipeng Wang To: dev@dpdk.org Cc: charlie.tai@intel.com, sameh.gobriel@intel.com, ren.wang@intel.com, yipeng1.wang@intel.com, john.mcnamara@intel.com Date: Tue, 5 Sep 2017 16:59:48 -0700 Message-Id: <1504655989-1518-7-git-send-email-yipeng1.wang@intel.com> X-Mailer: git-send-email 2.7.4 In-Reply-To: <1504655989-1518-1-git-send-email-yipeng1.wang@intel.com> References: <1504315481-12854-1-git-send-email-yipeng1.wang@intel.com> <1504655989-1518-1-git-send-email-yipeng1.wang@intel.com> Subject: [dpdk-dev] [PATCH v3 6/7] test/member: add functional and perf tests X-BeenThere: dev@dpdk.org X-Mailman-Version: 2.1.15 Precedence: list List-Id: DPDK patches and discussions List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: dev-bounces@dpdk.org Sender: "dev" This patch adds functional and performance tests for membership library. Signed-off-by: Yipeng Wang --- test/test/Makefile | 3 + test/test/test_member.c | 682 +++++++++++++++++++++++++++++++++++++++++++ test/test/test_member_perf.c | 643 ++++++++++++++++++++++++++++++++++++++++ 3 files changed, 1328 insertions(+) create mode 100644 test/test/test_member.c create mode 100644 test/test/test_member_perf.c diff --git a/test/test/Makefile b/test/test/Makefile index 42d9a49..b61dde3 100644 --- a/test/test/Makefile +++ b/test/test/Makefile @@ -123,6 +123,9 @@ SRCS-y += test_logs.c SRCS-y += test_memcpy.c SRCS-y += test_memcpy_perf.c + +SRCS-$(CONFIG_RTE_LIBRTE_MEMBER) += test_member.c +SRCS-$(CONFIG_RTE_LIBRTE_MEMBER) += test_member_perf.c SRCS-$(CONFIG_RTE_LIBRTE_EFD) += test_efd.c SRCS-$(CONFIG_RTE_LIBRTE_EFD) += test_efd_perf.c diff --git a/test/test/test_member.c b/test/test/test_member.c new file mode 100644 index 0000000..8965e81 --- /dev/null +++ b/test/test/test_member.c @@ -0,0 +1,682 @@ +/*- + * BSD LICENSE + * + * Copyright(c) 2017 Intel Corporation. All rights reserved. + * All rights reserved. + * + * Redistribution and use in source and binary forms, with or without + * modification, are permitted provided that the following conditions + * are met: + * + * * Redistributions of source code must retain the above copyright + * notice, this list of conditions and the following disclaimer. + * * Redistributions in binary form must reproduce the above copyright + * notice, this list of conditions and the following disclaimer in + * the documentation and/or other materials provided with the + * distribution. + * * Neither the name of Intel Corporation nor the names of its + * contributors may be used to endorse or promote products derived + * from this software without specific prior written permission. + * + * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS + * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT + * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR + * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT + * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, + * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT + * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, + * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY + * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT + * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE + * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. + */ + +/* This test is for membership library's simple feature test */ + +#include +#include +#include +#include +#include +#include +#include + +#include "test.h" + +void *setsum_ht; +void *setsum_cache; +void *setsum_vbf; + +/* 5-tuple key type */ +struct flow_key { + uint32_t ip_src; + uint32_t ip_dst; + uint16_t port_src; + uint16_t port_dst; + uint8_t proto; +} __attribute__((packed)); + + +/* Keys used by unit test functions */ +static struct flow_key keys[5] = { + { + .ip_src = IPv4(0x03, 0x02, 0x01, 0x00), + .ip_dst = IPv4(0x07, 0x06, 0x05, 0x04), + .port_src = 0x0908, + .port_dst = 0x0b0a, + .proto = 0x0c, + }, + { + .ip_src = IPv4(0x13, 0x12, 0x11, 0x10), + .ip_dst = IPv4(0x17, 0x16, 0x15, 0x14), + .port_src = 0x1918, + .port_dst = 0x1b1a, + .proto = 0x1c, + }, + { + .ip_src = IPv4(0x23, 0x22, 0x21, 0x20), + .ip_dst = IPv4(0x27, 0x26, 0x25, 0x24), + .port_src = 0x2928, + .port_dst = 0x2b2a, + .proto = 0x2c, + }, + { + .ip_src = IPv4(0x33, 0x32, 0x31, 0x30), + .ip_dst = IPv4(0x37, 0x36, 0x35, 0x34), + .port_src = 0x3938, + .port_dst = 0x3b3a, + .proto = 0x3c, + }, + { + .ip_src = IPv4(0x43, 0x42, 0x41, 0x40), + .ip_dst = IPv4(0x47, 0x46, 0x45, 0x44), + .port_src = 0x4948, + .port_dst = 0x4b4a, + .proto = 0x4c, + } +}; + +uint32_t test_set[5] = {1, 2, 3, 4, 5}; + +#define ITERATIONS 3 +#define KEY_SIZE 4 + +#define MAX_ENTRIES (1 << 16) +uint8_t gened_keys[MAX_ENTRIES][KEY_SIZE]; + +static struct rte_member_parameters params = { + .num_keys = MAX_ENTRIES, /* Total hash table entries. */ + .key_len = KEY_SIZE, /* Length of hash key. */ + + /*num_set and false_positive_rate only relevant to vBF setsum*/ + .num_set = 32, + .false_positive_rate = 0.03, + .prim_hash_seed = 1, + .sec_hash_seed = 11, + .socket_id = 0 /* NUMA Socket ID for memory. */ +}; + + +/* + * Sequence of operations for find existing setsummary + * + * - create setsum + * - find existing setsum: hit + * - find non-existing setsum: miss + * + */ +static int +test_member_find_existing(void) +{ + void *tmp_setsum = NULL, *result = NULL; + struct rte_member_parameters tmp_params = { + .name = "member_find_existing", + .num_keys = MAX_ENTRIES, /* Total hash table entries. */ + .key_len = KEY_SIZE, /* Length of hash key. */ + .type = RTE_MEMBER_TYPE_HT, + .num_set = 32, + .false_positive_rate = 0.03, + .prim_hash_seed = 1, + .sec_hash_seed = 11, + .socket_id = 0 /* NUMA Socket ID for memory. */ + }; + + /* Create */ + tmp_setsum = rte_member_create(&tmp_params); + TEST_ASSERT(tmp_setsum != NULL, "setsum creation failed"); + + /* Try to find existing hash table */ + result = rte_member_find_existing("member_find_existing"); + TEST_ASSERT(result == tmp_setsum, "could not find existing setsum"); + + /* Try to find non-existing hash table */ + result = rte_member_find_existing("member_find_non_existing"); + TEST_ASSERT(result == NULL, "found setsum that shouldn't exist"); + + /* Cleanup. */ + rte_member_free(tmp_setsum); + + return 0; +} + + +/* + * Test for bad creating parameters + */ +static int +test_member_create_bad_param(void) +{ + void *bad_setsum = NULL; + struct rte_member_parameters bad_params = { + .num_keys = MAX_ENTRIES, /* Total hash table entries. */ + .key_len = KEY_SIZE, /* Length of hash key. */ + .type = RTE_MEMBER_TYPE_HT, + .num_set = 32, + .false_positive_rate = 0.03, + .prim_hash_seed = 1, + .sec_hash_seed = 11, + .socket_id = 0 /* NUMA Socket ID for memory. */ + }; + + bad_params.name = "bad_param1"; + bad_params.num_set = 0; + bad_params.type = RTE_MEMBER_TYPE_VBF; + /* test with 0 set for vBF should fail */ + bad_setsum = rte_member_create(&bad_params); + if (bad_setsum != NULL) { + rte_member_free(bad_setsum); + printf("Impossible creating setsum successfully with invalid " + "number of set for vBF\n"); + return -1; + } + + bad_params.name = "bad_param2"; + bad_params.false_positive_rate = 0; + bad_params.num_set = 32; + /* test with 0 false positive for vBF should fail */ + bad_setsum = rte_member_create(&bad_params); + if (bad_setsum != NULL) { + rte_member_free(bad_setsum); + printf("Impossible creating setsum successfully with invalid " + "false positive rate for vBF\n"); + return -1; + } + + bad_params.name = "bad_param3"; + bad_params.false_positive_rate = 0.03; + bad_params.num_keys = 31; + /* test with less than 1 key per BF for vBF should fail */ + bad_setsum = rte_member_create(&bad_params); + if (bad_setsum != NULL) { + rte_member_free(bad_setsum); + printf("Impossible creating setsum successfully with invalid " + "num_keys for vBF\n"); + return -1; + } + + bad_params.name = "bad_param4"; + bad_params.type = RTE_MEMBER_TYPE_HT; + bad_params.num_keys = RTE_MEMBER_BUCKET_ENTRIES / 2; + /* test with less than 1 bucket for HTSS should fail */ + bad_setsum = rte_member_create(&bad_params); + if (bad_setsum != NULL) { + rte_member_free(bad_setsum); + printf("Impossible creating setsum successfully with too few " + "number of keys(entries) for HT\n"); + return -1; + } + + bad_params.name = "bad_param5"; + bad_params.num_keys = RTE_MEMBER_ENTRIES_MAX + 1; + /* test with more than maximum entries for HTSS should fail */ + bad_setsum = rte_member_create(&bad_params); + if (bad_setsum != NULL) { + rte_member_free(bad_setsum); + printf("Impossible creating setsum successfully with to many " + "number of keys(entries) for HT\n"); + return -1; + } + + bad_params.name = "bad_param5"; + /* test with same name should fail */ + bad_setsum = rte_member_create(&bad_params); + if (bad_setsum != NULL) { + rte_member_free(bad_setsum); + printf("Impossible creating setsum successfully with existed " + "name\n"); + return -1; + } + + rte_member_free(bad_setsum); + return 0; +} + + +/* Create test setsummaries. */ +static int test_member_create(void) +{ + params.key_len = sizeof(struct flow_key); + + params.name = "test_member_ht"; + params.iscache = 0; + params.type = RTE_MEMBER_TYPE_HT; + setsum_ht = rte_member_create(¶ms); + + params.name = "test_member_cache"; + params.iscache = 1; + setsum_cache = rte_member_create(¶ms); + + params.name = "test_member_vbf"; + params.type = RTE_MEMBER_TYPE_VBF; + setsum_vbf = rte_member_create(¶ms); + + if (setsum_ht == NULL || setsum_cache == NULL || setsum_vbf == NULL) { + printf("Creation of setsums fail\n"); + return -1; + } + printf("Creation of setsums success\n"); + return 0; +} + +static int test_member_insert(void) +{ + int ret_ht, ret_cache, ret_vbf, i; + + for (i = 0; i < 5; i++) { + ret_ht = rte_member_add(setsum_ht, &keys[i], test_set[i]); + ret_cache = rte_member_add(setsum_cache, &keys[i], + test_set[i]); + ret_vbf = rte_member_add(setsum_vbf, &keys[i], test_set[i]); + TEST_ASSERT(ret_ht >= 0 && ret_cache >= 0 && ret_vbf >= 0, + "insert error"); + } + printf("insert key success\n"); + return 0; +} + +static int test_member_lookup(void) +{ + int ret_ht, ret_cache, ret_vbf, i; + uint16_t set_ht, set_cache, set_vbf; + MEMBER_SET_TYPE set_ids_ht[5] = {0}; + MEMBER_SET_TYPE set_ids_cache[5] = {0}; + MEMBER_SET_TYPE set_ids_vbf[5] = {0}; + + uint32_t num_key_ht = 5; + uint32_t num_key_cache = 5; + uint32_t num_key_vbf = 5; + + const void *key_array[5]; + + /* single lookup test */ + for (i = 0; i < 5; i++) { + ret_ht = rte_member_lookup(setsum_ht, &keys[i], &set_ht); + ret_cache = rte_member_lookup(setsum_cache, &keys[i], + &set_cache); + ret_vbf = rte_member_lookup(setsum_vbf, &keys[i], &set_vbf); + TEST_ASSERT(ret_ht >= 0 && ret_cache >= 0 && ret_vbf >= 0, + "single lookup function error"); + + TEST_ASSERT(set_ht == test_set[i] && + set_cache == test_set[i] && + set_vbf == test_set[i], + "single lookup set value error"); + } + printf("lookup single key success\n"); + + /* bulk lookup test */ + for (i = 0; i < 5; i++) + key_array[i] = &keys[i]; + + ret_ht = rte_member_lookup_bulk(setsum_ht, &key_array[0], + num_key_ht, set_ids_ht); + + ret_cache = rte_member_lookup_bulk(setsum_cache, &key_array[0], + num_key_cache, set_ids_cache); + + ret_vbf = rte_member_lookup_bulk(setsum_vbf, &key_array[0], + num_key_vbf, set_ids_vbf); + + TEST_ASSERT(ret_ht >= 0 && ret_cache >= 0 && ret_vbf >= 0, + "bulk lookup function error"); + + for (i = 0; i < 5; i++) { + TEST_ASSERT((set_ids_ht[i] == test_set[i]) && + (set_ids_cache[i] == test_set[i]) && + (set_ids_vbf[i] == test_set[i]), + "bulk lookup result error"); + } + + return 0; +} + + +static int test_member_delete(void) +{ + int ret_ht, ret_cache, ret_vbf, i; + uint16_t set_ht, set_cache, set_vbf; + for (i = 0; i < 5; i++) { + ret_ht = rte_member_delete(setsum_ht, &keys[i], test_set[i]); + ret_cache = rte_member_delete(setsum_cache, &keys[i], + test_set[i]); + ret_vbf = rte_member_delete(setsum_vbf, &keys[i], test_set[i]); + /* VBF does not support delete yet, so return error code */ + TEST_ASSERT(ret_ht >= 0 && ret_cache >= 0, + "key deletion function error"); + TEST_ASSERT(ret_vbf < 0, + "vbf does not support deletion, error"); + } + + for (i = 0; i < 5; i++) { + ret_ht = rte_member_lookup(setsum_ht, &keys[i], &set_ht); + ret_cache = rte_member_lookup(setsum_cache, &keys[i], + &set_cache); + ret_vbf = rte_member_lookup(setsum_vbf, &keys[i], &set_vbf); + TEST_ASSERT(ret_ht >= 0 && ret_cache >= 0, + "key lookup function error"); + TEST_ASSERT(set_ht == RTE_MEMBER_NO_MATCH && + ret_cache == RTE_MEMBER_NO_MATCH, + "key deletion failed"); + } + printf("delete success\n"); + return 0; +} + + +static int test_member_multimatch(void) +{ + int ret_ht, ret_vbf, ret_cache; + MEMBER_SET_TYPE set_ids_ht[32] = {0}; + MEMBER_SET_TYPE set_ids_vbf[32] = {0}; + MEMBER_SET_TYPE set_ids_cache[32] = {0}; + + MEMBER_SET_TYPE set_ids_ht_m[5][32] = {{0} }; + MEMBER_SET_TYPE set_ids_vbf_m[5][32] = {{0} }; + MEMBER_SET_TYPE set_ids_cache_m[5][32] = {{0} }; + + uint32_t match_count_ht[5]; + uint32_t match_count_vbf[5]; + uint32_t match_count_cache[5]; + + uint32_t num_key_ht = 5; + uint32_t num_key_vbf = 5; + uint32_t num_key_cache = 5; + + const void *key_array[5]; + + uint32_t i, j; + /* same key at most inserted 2*entry_per_bucket times for HT mode */ + for (i = 1; i < 33; i++) { + for (j = 0; j < 5; j++) { + ret_ht = rte_member_add(setsum_ht, &keys[j], i); + ret_vbf = rte_member_add(setsum_vbf, &keys[j], i); + ret_cache = rte_member_add(setsum_cache, &keys[j], i); + + TEST_ASSERT(ret_ht >= 0 && ret_vbf >= 0 && + ret_cache >= 0, + "insert function error"); + } + } + + /* single multimatch test */ + for (i = 0; i < 5; i++) { + ret_vbf = rte_member_lookup_multi(setsum_vbf, &keys[i], 32, + set_ids_vbf); + ret_ht = rte_member_lookup_multi(setsum_ht, &keys[i], 32, + set_ids_ht); + ret_cache = rte_member_lookup_multi(setsum_cache, &keys[i], 32, + set_ids_cache); + /* + * for cache mode, it does not support multimatch + * the mutimatch should work like single match + */ + TEST_ASSERT(ret_ht == 32 && ret_vbf == 32 && ret_cache == 1, + "single lookup_multi error"); + TEST_ASSERT(set_ids_cache[0] == 32, + "single lookup_multi cache error"); + + for (j = 1; j < 33; j++) { + TEST_ASSERT(set_ids_ht[j-1] == j && + set_ids_vbf[j-1] == j, + "single multimatch lookup error"); + } + } + printf("lookup single key for multimatch success\n"); + + /* bulk multimatch test */ + + for (i = 0; i < 5; i++) + key_array[i] = &keys[i]; + ret_vbf = rte_member_lookup_multi_bulk(setsum_vbf, + &key_array[0], num_key_ht, 32, match_count_vbf, + (MEMBER_SET_TYPE *)set_ids_vbf_m); + + ret_ht = rte_member_lookup_multi_bulk(setsum_ht, + &key_array[0], num_key_vbf, 32, match_count_ht, + (MEMBER_SET_TYPE *)set_ids_ht_m); + + ret_cache = rte_member_lookup_multi_bulk(setsum_cache, + &key_array[0], num_key_cache, 32, match_count_cache, + (MEMBER_SET_TYPE *)set_ids_cache_m); + + + for (j = 0; j < 5; j++) { + TEST_ASSERT(match_count_ht[j] == 32, + "bulk multimatch lookup HT match count error"); + TEST_ASSERT(match_count_vbf[j] == 32, + "bulk multimatch lookup vBF match count error"); + TEST_ASSERT(match_count_cache[j] == 1, + "bulk multimatch lookup CACHE match count error"); + TEST_ASSERT(set_ids_cache_m[j][0] == 32, + "bulk multimatch lookup CACHE set value error"); + + for (i = 1; i < 33; i++) { + TEST_ASSERT(set_ids_ht_m[j][i-1] == i, + "bulk multimatch lookup HT set value error"); + TEST_ASSERT(set_ids_vbf_m[j][i-1] == i, + "bulk multimatch lookup vBF set value error"); + } + } + + printf("lookup for bulk multimatch success\n"); + + return 0; +} + + +static int key_compare(const void *key1, const void *key2) +{ + return memcmp(key1, key2, KEY_SIZE); +} + +static void +setup_keys_and_data(void) +{ + unsigned int i, j; + int num_duplicates; + + /* Reset all arrays */ + for (i = 0; i < KEY_SIZE; i++) + gened_keys[0][i] = 0; + + /* Generate a list of keys, some of which may be duplicates */ + for (i = 0; i < MAX_ENTRIES; i++) { + for (j = 0; j < KEY_SIZE; j++) + gened_keys[i][j] = rte_rand() & 0xFF; + } + + /* Remove duplicates from the keys array */ + do { + num_duplicates = 0; + /* Sort the list of keys to make it easier to find duplicates */ + qsort(gened_keys, MAX_ENTRIES, KEY_SIZE, key_compare); + + /* Sift through the list of keys and look for duplicates */ + int num_duplicates = 0; + for (i = 0; i < MAX_ENTRIES - 1; i++) { + if (memcmp(gened_keys[i], gened_keys[i + 1], + KEY_SIZE) == 0) { + /* This key already exists, try again */ + num_duplicates++; + for (j = 0; j < KEY_SIZE; j++) + gened_keys[i][j] = rte_rand() & 0xFF; + } + } + } while (num_duplicates != 0); +} + + +static inline int +add_gened_keys(void *setsum, unsigned int *added_keys) +{ + int ret = 0; + + for (*added_keys = 0; ret >= 0 && *added_keys < MAX_ENTRIES; + (*added_keys)++) { + uint16_t set = (rte_rand() & 0xf) + 1; + ret = rte_member_add(setsum, &gened_keys[*added_keys], set); + } + return ret; +} + + +static inline int +add_gened_keys_cache(void *setsum, unsigned int *added_keys) +{ + int ret = 0; + + for (*added_keys = 0; ret == 0 && *added_keys < MAX_ENTRIES; + (*added_keys)++) { + uint16_t set = (rte_rand() & 0xf) + 1; + ret = rte_member_add(setsum, &gened_keys[*added_keys], set); + } + return ret; +} + +static int +test_member_loadfactor(void) +{ + unsigned int j; + unsigned int added_keys, average_keys_added = 0; + int ret; + + setup_keys_and_data(); + + rte_member_free(setsum_ht); + rte_member_free(setsum_cache); + rte_member_free(setsum_vbf); + + params.key_len = KEY_SIZE; + params.name = "test_member_ht"; + params.iscache = 0; + params.type = RTE_MEMBER_TYPE_HT; + setsum_ht = rte_member_create(¶ms); + + params.name = "test_member_cache"; + params.iscache = 1; + setsum_cache = rte_member_create(¶ms); + + + if (setsum_ht == NULL || setsum_cache == NULL) { + printf("Creation of setsums fail\n"); + return -1; + } + /* test HT mode */ + for (j = 0; j < ITERATIONS; j++) { + /* Add random entries until key cannot be added */ + ret = add_gened_keys(setsum_ht, &added_keys); + if (ret != -ENOSPC) { + printf("Unexpected error when adding keys\n"); + return -1; + } + average_keys_added += added_keys; + + /* Reset the table */ + rte_member_reset(setsum_ht); + + /* Print a dot to show progress on operations */ + printf("."); + fflush(stdout); + } + + average_keys_added /= ITERATIONS; + + printf("\nKeys inserted when no space(non-cache) = %.2f%% (%u/%u)\n", + ((double) average_keys_added / params.num_keys * 100), + average_keys_added, params.num_keys); + + /* test cache mode */ + added_keys = average_keys_added = 0; + for (j = 0; j < ITERATIONS; j++) { + /* Add random entries until key cannot be added */ + ret = add_gened_keys_cache(setsum_cache, &added_keys); + if (ret != 1) { + printf("Unexpected error when adding keys\n"); + return -1; + } + average_keys_added += added_keys; + + /* Reset the table */ + rte_member_reset(setsum_cache); + + /* Print a dot to show progress on operations */ + printf("."); + fflush(stdout); + } + + average_keys_added /= ITERATIONS; + + printf("\nKeys inserted when eviction happens(cache)= %.2f%% (%u/%u)\n", + ((double) average_keys_added / params.num_keys * 100), + average_keys_added, params.num_keys); + return 0; +} + +static void +perform_free(void) +{ + rte_member_free(setsum_ht); + rte_member_free(setsum_cache); + rte_member_free(setsum_vbf); +} + +static int +test_member(void) +{ + if (test_member_create_bad_param() < 0) + return -1; + + if (test_member_find_existing() < 0) + return -1; + + if (test_member_create() < 0) { + perform_free(); + return -1; + } + if (test_member_insert() < 0) { + perform_free(); + return -1; + } + if (test_member_lookup() < 0) { + perform_free(); + return -1; + } + if (test_member_delete() < 0) { + perform_free(); + return -1; + } + if (test_member_multimatch() < 0) { + perform_free(); + return -1; + } + if (test_member_loadfactor() < 0) { + rte_member_free(setsum_ht); + rte_member_free(setsum_cache); + return -1; + } + + perform_free(); + return 0; +} + +REGISTER_TEST_COMMAND(member_autotest, test_member); diff --git a/test/test/test_member_perf.c b/test/test/test_member_perf.c new file mode 100644 index 0000000..2bb3a31 --- /dev/null +++ b/test/test/test_member_perf.c @@ -0,0 +1,643 @@ +/*- + * BSD LICENSE + * + * Copyright(c) 2017 Intel Corporation. All rights reserved. + * All rights reserved. + * + * Redistribution and use in source and binary forms, with or without + * modification, are permitted provided that the following conditions + * are met: + * + * * Redistributions of source code must retain the above copyright + * notice, this list of conditions and the following disclaimer. + * * Redistributions in binary form must reproduce the above copyright + * notice, this list of conditions and the following disclaimer in + * the documentation and/or other materials provided with the + * distribution. + * * Neither the name of Intel Corporation nor the names of its + * contributors may be used to endorse or promote products derived + * from this software without specific prior written permission. + * + * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS + * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT + * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR + * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT + * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, + * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT + * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, + * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY + * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT + * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE + * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. + */ + +#include +#include + +#include +#include +#include +#include +#include +#include +#include + +#include "test.h" + +#define NUM_KEYSIZES 10 +#define NUM_SHUFFLES 10 +#define MAX_KEYSIZE 64 +#define MAX_ENTRIES (1 << 19) +#define KEYS_TO_ADD (MAX_ENTRIES * 75 / 100) /* 75% table utilization */ +#define NUM_LOOKUPS (KEYS_TO_ADD * 5) /* Loop among keys added, several times */ +#define VBF_SET_CNT 32 +#define BURST_SIZE 64 +#define VBF_FALSE_RATE 0.03 + + +static unsigned int test_socket_id; + +enum sstype { + HT = 0, + CACHE, + VBF, + NUM_TYPE +}; + +enum operations { + ADD = 0, + LOOKUP, + LOOKUP_BULK, + LOOKUP_MULTI, + LOOKUP_MULTI_BULK, + DELETE, + LOOKUP_MISS, + NUM_OPERATIONS +}; + + +struct member_perf_params { + void *setsum[NUM_TYPE]; + uint32_t key_size; + unsigned int cycle; +}; + + +static uint32_t hashtest_key_lens[] = { + /* standard key sizes */ + 4, 8, 16, 32, 48, 64, + /* IPv4 SRC + DST + protocol, unpadded */ + 9, + /* IPv4 5-tuple, unpadded */ + 13, + /* IPv6 5-tuple, unpadded */ + 37, + /* IPv6 5-tuple, padded to 8-byte boundary */ + 40 +}; + +/* Array to store number of cycles per operation */ +uint64_t cycles[NUM_TYPE][NUM_KEYSIZES][NUM_OPERATIONS]; +uint64_t false_data[NUM_TYPE][NUM_KEYSIZES]; +uint64_t false_data_bulk[NUM_TYPE][NUM_KEYSIZES]; +uint64_t false_data_multi[NUM_TYPE][NUM_KEYSIZES]; +uint64_t false_data_multi_bulk[NUM_TYPE][NUM_KEYSIZES]; + +uint64_t false_hit[NUM_TYPE][NUM_KEYSIZES]; + + +MEMBER_SET_TYPE data[NUM_TYPE][/* Array to store the data */KEYS_TO_ADD]; + +/* Array to store all input keys */ +uint8_t keys[KEYS_TO_ADD][MAX_KEYSIZE]; + +/* Shuffle the keys that have been added, so lookups will be totally random */ +static void +shuffle_input_keys(struct member_perf_params *params) +{ + MEMBER_SET_TYPE temp_data; + unsigned int i, j; + uint32_t swap_idx; + uint8_t temp_key[MAX_KEYSIZE]; + + for (i = KEYS_TO_ADD - 1; i > 0; i--) { + swap_idx = rte_rand() % i; + memcpy(temp_key, keys[i], hashtest_key_lens[params->cycle]); + memcpy(keys[i], keys[swap_idx], + hashtest_key_lens[params->cycle]); + memcpy(keys[swap_idx], temp_key, + hashtest_key_lens[params->cycle]); + for (j = 0; j < NUM_TYPE; j++) { + temp_data = data[j][i]; + data[j][i] = data[j][swap_idx]; + data[j][swap_idx] = temp_data; + } + } +} + +static int key_compare(const void *key1, const void *key2) +{ + return memcmp(key1, key2, MAX_KEYSIZE); +} + +struct rte_member_parameters member_params = { + .num_keys = MAX_ENTRIES, /* Total hash table entries. */ + .key_len = 4, /* Length of hash key. */ + + /* num_set and false_positive_rate only relevant to vBF setsum*/ + .num_set = VBF_SET_CNT, + .false_positive_rate = 0.03, + .prim_hash_seed = 0, + .sec_hash_seed = 1, + .socket_id = 0, /* NUMA Socket ID for memory. */ + }; + + + +static int +setup_keys_and_data(struct member_perf_params *params, unsigned int cycle, + int miss) +{ + unsigned int i, j; + int num_duplicates; + + params->key_size = hashtest_key_lens[cycle]; + params->cycle = cycle; + + /* Reset all arrays */ + for (i = 0; i < params->key_size; i++) + keys[0][i] = 0; + + /* Generate a list of keys, some of which may be duplicates */ + for (i = 0; i < KEYS_TO_ADD; i++) { + for (j = 0; j < params->key_size; j++) + keys[i][j] = rte_rand() & 0xFF; + + data[HT][i] = data[CACHE][i] = (rte_rand() & 0x7FFE) + 1; + data[VBF][i] = rte_rand() % VBF_SET_CNT + 1; + } + + /* Remove duplicates from the keys array */ + do { + num_duplicates = 0; + + /* Sort the list of keys to make it easier to find duplicates */ + qsort(keys, KEYS_TO_ADD, MAX_KEYSIZE, key_compare); + + /* Sift through the list of keys and look for duplicates */ + int num_duplicates = 0; + for (i = 0; i < KEYS_TO_ADD - 1; i++) { + if (memcmp(keys[i], keys[i + 1], + params->key_size) == 0) { + /* This key already exists, try again */ + num_duplicates++; + for (j = 0; j < params->key_size; j++) + keys[i][j] = rte_rand() & 0xFF; + } + } + } while (num_duplicates != 0); + + /* Shuffle the random values again */ + shuffle_input_keys(params); + + /* For testing miss lookup, we insert half and lookup the other half */ + unsigned int entry_cnt, bf_key_cnt; + if (!miss) { + entry_cnt = MAX_ENTRIES; + bf_key_cnt = KEYS_TO_ADD; + } else { + entry_cnt = MAX_ENTRIES / 2; + bf_key_cnt = KEYS_TO_ADD / 2; + } + member_params.false_positive_rate = VBF_FALSE_RATE; + member_params.key_len = params->key_size; + member_params.socket_id = test_socket_id; + member_params.num_keys = entry_cnt; + member_params.name = "test_member_ht"; + member_params.iscache = 0; + member_params.type = RTE_MEMBER_TYPE_HT; + params->setsum[HT] = rte_member_create(&member_params); + if (params->setsum[HT] == NULL) + fprintf(stderr, "ht create fail\n"); + + member_params.name = "test_member_cache"; + member_params.iscache = 1; + params->setsum[CACHE] = rte_member_create(&member_params); + if (params->setsum[CACHE] == NULL) + fprintf(stderr, "CACHE create fail\n"); + + member_params.name = "test_member_vbf"; + member_params.type = RTE_MEMBER_TYPE_VBF; + member_params.num_keys = bf_key_cnt; + params->setsum[VBF] = rte_member_create(&member_params); + if (params->setsum[VBF] == NULL) + fprintf(stderr, "VBF create fail\n"); + for (i = 0; i < NUM_TYPE; i++) { + if (params->setsum[i] == NULL) + return -1; + } + + return 0; +} + +static int +timed_adds(struct member_perf_params *params, int type) +{ + const uint64_t start_tsc = rte_rdtsc(); + unsigned int i, a; + int32_t ret; + + for (i = 0; i < KEYS_TO_ADD; i++) { + ret = rte_member_add(params->setsum[type], &keys[i], + data[type][i]); + if (ret < 0) { + printf("Error %d in rte_member_add - key=0x", ret); + for (a = 0; a < params->key_size; a++) + printf("%02x", keys[i][a]); + printf(" value=%d, type: %d\n", data[type][i], type); + + return -1; + } + } + + const uint64_t end_tsc = rte_rdtsc(); + const uint64_t time_taken = end_tsc - start_tsc; + + cycles[type][params->cycle][ADD] = time_taken / KEYS_TO_ADD; + return 0; +} + +static int +timed_lookups(struct member_perf_params *params, int type) +{ + unsigned int i, j; + + false_data[type][params->cycle] = 0; + + const uint64_t start_tsc = rte_rdtsc(); + MEMBER_SET_TYPE result; + int ret; + + for (i = 0; i < NUM_LOOKUPS / KEYS_TO_ADD; i++) { + for (j = 0; j < KEYS_TO_ADD; j++) { + ret = rte_member_lookup(params->setsum[type], &keys[j], + &result); + if (ret < 0) { + printf("lookup wrong internally"); + return -1; + } + if (result != data[type][j]) + false_data[type][params->cycle]++; + } + } + + const uint64_t end_tsc = rte_rdtsc(); + const uint64_t time_taken = end_tsc - start_tsc; + + cycles[type][params->cycle][LOOKUP] = time_taken / NUM_LOOKUPS; + + return 0; +} + +static int +timed_lookups_bulk(struct member_perf_params *params, int type) +{ + unsigned int i, j, k; + MEMBER_SET_TYPE result[BURST_SIZE] = {0}; + const void *keys_burst[BURST_SIZE]; + int ret; + + false_data_bulk[type][params->cycle] = 0; + + const uint64_t start_tsc = rte_rdtsc(); + + for (i = 0; i < NUM_LOOKUPS / KEYS_TO_ADD; i++) { + for (j = 0; j < KEYS_TO_ADD / BURST_SIZE; j++) { + for (k = 0; k < BURST_SIZE; k++) + keys_burst[k] = keys[j * BURST_SIZE + k]; + + ret = rte_member_lookup_bulk(params->setsum[type], + &keys_burst[0], + BURST_SIZE, + result); + if (ret <= 0) { + printf("lookup bulk has wrong return value\n"); + return -1; + } + for (k = 0; k < BURST_SIZE; k++) { + uint32_t data_idx = j * BURST_SIZE + k; + if (result[k] != data[type][data_idx]) + false_data_bulk[type][params->cycle]++; + } + } + } + + const uint64_t end_tsc = rte_rdtsc(); + const uint64_t time_taken = end_tsc - start_tsc; + + cycles[type][params->cycle][LOOKUP_BULK] = time_taken / NUM_LOOKUPS; + + return 0; +} + + +static int +timed_lookups_multimatch(struct member_perf_params *params, int type) +{ + unsigned int i, j; + MEMBER_SET_TYPE result[RTE_MEMBER_BUCKET_ENTRIES] = {0}; + int ret; + false_data_multi[type][params->cycle] = 0; + + const uint64_t start_tsc = rte_rdtsc(); + + for (i = 0; i < NUM_LOOKUPS / KEYS_TO_ADD; i++) { + for (j = 0; j < KEYS_TO_ADD; j++) { + ret = rte_member_lookup_multi(params->setsum[type], + &keys[j], RTE_MEMBER_BUCKET_ENTRIES, result); + if (type != CACHE && ret <= 0) { + printf("lookup multi has wrong return value %d," + "type %d\n", ret, type); + } + if (result[0] != data[type][j]) + false_data_multi[type][params->cycle]++; + } + } + + const uint64_t end_tsc = rte_rdtsc(); + const uint64_t time_taken = end_tsc - start_tsc; + + cycles[type][params->cycle][LOOKUP_MULTI] = time_taken / NUM_LOOKUPS; + + return 0; +} + + +static int +timed_lookups_multimatch_bulk(struct member_perf_params *params, int type) +{ + unsigned int i, j, k; + MEMBER_SET_TYPE result[BURST_SIZE][RTE_MEMBER_BUCKET_ENTRIES] = {{0} }; + const void *keys_burst[BURST_SIZE]; + uint32_t match_count[BURST_SIZE]; + int ret; + + false_data_multi_bulk[type][params->cycle] = 0; + + const uint64_t start_tsc = rte_rdtsc(); + + for (i = 0; i < NUM_LOOKUPS / KEYS_TO_ADD; i++) { + for (j = 0; j < KEYS_TO_ADD / BURST_SIZE; j++) { + for (k = 0; k < BURST_SIZE; k++) + keys_burst[k] = keys[j * BURST_SIZE + k]; + + ret = rte_member_lookup_multi_bulk( + params->setsum[type], + &keys_burst[0], BURST_SIZE, + RTE_MEMBER_BUCKET_ENTRIES, match_count, + (MEMBER_SET_TYPE *)result); + if (ret < 0) { + printf("lookup multimatch bulk has wrong return" + " value\n"); + return -1; + } + for (k = 0; k < BURST_SIZE; k++) { + if (type != CACHE && match_count[k] == 0) { + printf("lookup multimatch bulk get " + "wrong match count\n"); + return -1; + } + uint32_t data_idx = j * BURST_SIZE + k; + if (result[k][0] != data[type][data_idx]) + false_data_multi_bulk[type][params->cycle]++; + } + } + } + + const uint64_t end_tsc = rte_rdtsc(); + const uint64_t time_taken = end_tsc - start_tsc; + + cycles[type][params->cycle][LOOKUP_MULTI_BULK] = time_taken / + NUM_LOOKUPS; + + return 0; +} + +static int +timed_deletes(struct member_perf_params *params, int type) +{ + unsigned int i; + int32_t ret; + + if (type == VBF) + return 0; + const uint64_t start_tsc = rte_rdtsc(); + for (i = 0; i < KEYS_TO_ADD; i++) { + ret = rte_member_delete(params->setsum[type], &keys[i], + data[type][i]); + if (type != CACHE && ret < 0) { + printf("delete error\n"); + return -1; + } + } + + const uint64_t end_tsc = rte_rdtsc(); + const uint64_t time_taken = end_tsc - start_tsc; + + cycles[type][params->cycle][DELETE] = time_taken / KEYS_TO_ADD; + + return 0; +} + + +static int +timed_miss_lookup(struct member_perf_params *params, int type) +{ + unsigned int i, j; + int ret; + + false_hit[type][params->cycle] = 0; + + for (i = 0; i < KEYS_TO_ADD / 2; i++) { + ret = rte_member_add(params->setsum[type], &keys[i], + data[type][i]); + if (ret < 0) { + unsigned int a; + printf("Error %d in rte_member_add - key=0x", ret); + for (a = 0; a < params->key_size; a++) + printf("%02x", keys[i][a]); + printf(" value=%d, type: %d\n", data[type][i], type); + + return -1; + } + } + + const uint64_t start_tsc = rte_rdtsc(); + MEMBER_SET_TYPE result; + + for (i = 0; i < 2 * NUM_LOOKUPS / KEYS_TO_ADD; i++) { + for (j = KEYS_TO_ADD / 2; j < KEYS_TO_ADD; j++) { + ret = rte_member_lookup(params->setsum[type], &keys[j], + &result); + if (ret < 0) { + printf("lookup wrong internally"); + return -1; + } + if (result != RTE_MEMBER_NO_MATCH) + false_hit[type][params->cycle]++; + } + } + + const uint64_t end_tsc = rte_rdtsc(); + const uint64_t time_taken = end_tsc - start_tsc; + + cycles[type][params->cycle][LOOKUP_MISS] = time_taken / NUM_LOOKUPS; + + return 0; +} + + + +static void +perform_frees(struct member_perf_params *params) +{ + int i; + for (i = 0; i < NUM_TYPE; i++) { + if (params->setsum[i] != NULL) { + rte_member_free(params->setsum[i]); + params->setsum[i] = NULL; + } + } +} + +static int +exit_with_fail(const char *testname, struct member_perf_params *params, + unsigned int i, unsigned int j) +{ + printf("<<<<>>>>\n", + testname, hashtest_key_lens[params->cycle], i, j); + perform_frees(params); + return -1; +} + +static int +run_all_tbl_perf_tests(void) +{ + unsigned int i, j, k; + struct member_perf_params params; + + printf("Measuring performance, please wait\n"); + fflush(stdout); + + test_socket_id = rte_socket_id(); + + + for (i = 0; i < NUM_KEYSIZES; i++) { + if (setup_keys_and_data(¶ms, i, 0) < 0) { + printf("Could not create keys/data/table\n"); + return -1; + } + for (j = 0; j < NUM_TYPE; j++) { + + if (timed_adds(¶ms, j) < 0) + return exit_with_fail("timed_adds", ¶ms, + i, j); + + for (k = 0; k < NUM_SHUFFLES; k++) + shuffle_input_keys(¶ms); + + if (timed_lookups(¶ms, j) < 0) + return exit_with_fail("timed_lookups", ¶ms, + i, j); + + if (timed_lookups_bulk(¶ms, j) < 0) + return exit_with_fail("timed_lookups_bulk", + ¶ms, i, j); + + if (timed_lookups_multimatch(¶ms, j) < 0) + return exit_with_fail("timed_lookups_multi", + ¶ms, i, j); + + if (timed_lookups_multimatch_bulk(¶ms, j) < 0) + return exit_with_fail("timed_lookups_multi_bulk", + ¶ms, i, j); + + if (timed_deletes(¶ms, j) < 0) + return exit_with_fail("timed_deletes", ¶ms, + i, j); + + /* Print a dot to show progress on operations */ + } + printf("."); + fflush(stdout); + + perform_frees(¶ms); + } + + /* test false postivie rate using un-inserted keys */ + for (i = 0; i < NUM_KEYSIZES; i++) { + if (setup_keys_and_data(¶ms, i, 1) < 0) { + printf("Could not create keys/data/table\n"); + return -1; + } + for (j = 0; j < NUM_TYPE; j++) { + if (timed_miss_lookup(¶ms, j) < 0) + return exit_with_fail("timed_miss_lookup", + ¶ms, i, j); + } + perform_frees(¶ms); + } + + printf("\nResults (in CPU cycles/operation)\n"); + printf("-----------------------------------\n"); + printf("\n%-18s%-18s%-18s%-18s%-18s%-18s%-18s%-18s%-18s\n", + "Keysize", "type", "Add", "Lookup", "Lookup_bulk", + "lookup_multi", "lookup_multi_bulk", "Delete", + "miss_lookup"); + for (i = 0; i < NUM_KEYSIZES; i++) { + for (j = 0; j < NUM_TYPE; j++) { + printf("%-18d", hashtest_key_lens[i]); + printf("%-18d", j); + for (k = 0; k < NUM_OPERATIONS; k++) + printf("%-18"PRIu64, cycles[j][i][k]); + printf("\n"); + } + } + + printf("\nFalse results rate (and false positive rate)\n"); + printf("-----------------------------------\n"); + printf("\n%-18s%-18s%-18s%-18s%-18s%-18s%-18s\n", + "Keysize", "type", "fr_single", "fr_bulk", "fr_multi", + "fr_multi_bulk", "false_positive_rate"); + /* key size not influence False rate so just print out one key size */ + for (i = 0; i < 1; i++) { + for (j = 0; j < NUM_TYPE; j++) { + printf("%-18d", hashtest_key_lens[i]); + printf("%-18d", j); + printf("%-18f", (float)false_data[j][i] / NUM_LOOKUPS); + printf("%-18f", (float)false_data_bulk[j][i] / + NUM_LOOKUPS); + printf("%-18f", (float)false_data_multi[j][i] / + NUM_LOOKUPS); + printf("%-18f", (float)false_data_multi_bulk[j][i] / + NUM_LOOKUPS); + printf("%-18f", (float)false_hit[j][i] / + NUM_LOOKUPS); + printf("\n"); + } + } + + return 0; +} + +static int +test_member_perf(void) +{ + + if (run_all_tbl_perf_tests() < 0) + return -1; + + return 0; +} + +REGISTER_TEST_COMMAND(member_perf_autotest, test_member_perf);