Patch Detail
get:
Show a patch.
patch:
Update a patch.
put:
Update a patch.
GET /api/patches/6239/?format=api
{ "id": 6239, "url": "https://patches.dpdk.org/api/patches/6239/?format=api", "web_url": "https://patches.dpdk.org/project/dpdk/patch/1436444378-29106-2-git-send-email-pablo.de.lara.guarch@intel.com/", "project": { "id": 1, "url": "https://patches.dpdk.org/api/projects/1/?format=api", "name": "DPDK", "link_name": "dpdk", "list_id": "dev.dpdk.org", "list_email": "dev@dpdk.org", "web_url": "http://core.dpdk.org", "scm_url": "git://dpdk.org/dpdk", "webscm_url": "http://git.dpdk.org/dpdk", "list_archive_url": "https://inbox.dpdk.org/dev", "list_archive_url_format": "https://inbox.dpdk.org/dev/{}", "commit_url_format": "" }, "msgid": "<1436444378-29106-2-git-send-email-pablo.de.lara.guarch@intel.com>", "list_archive_url": "https://inbox.dpdk.org/dev/1436444378-29106-2-git-send-email-pablo.de.lara.guarch@intel.com", "date": "2015-07-09T12:19:38", "name": "[dpdk-dev,v3] test/hash: improve hash unit tests", "commit_ref": null, "pull_url": null, "state": "superseded", "archived": true, "hash": "72b5cedf2f6f9df1556efa168ee6fb1c2230a96a", "submitter": { "id": 9, "url": "https://patches.dpdk.org/api/people/9/?format=api", "name": "De Lara Guarch, Pablo", "email": "pablo.de.lara.guarch@intel.com" }, "delegate": null, "mbox": "https://patches.dpdk.org/project/dpdk/patch/1436444378-29106-2-git-send-email-pablo.de.lara.guarch@intel.com/mbox/", "series": [], "comments": "https://patches.dpdk.org/api/patches/6239/comments/", "check": "pending", "checks": "https://patches.dpdk.org/api/patches/6239/checks/", "tags": {}, "related": [], "headers": { "Return-Path": "<dev-bounces@dpdk.org>", "X-Original-To": "patchwork@dpdk.org", "Delivered-To": "patchwork@dpdk.org", "Received": [ "from [92.243.14.124] (localhost [IPv6:::1])\n\tby dpdk.org (Postfix) with ESMTP id BD211C332;\n\tThu, 9 Jul 2015 14:19:47 +0200 (CEST)", "from mga01.intel.com (mga01.intel.com [192.55.52.88])\n\tby dpdk.org (Postfix) with ESMTP id 65C275A44\n\tfor <dev@dpdk.org>; Thu, 9 Jul 2015 14:19:42 +0200 (CEST)", "from orsmga002.jf.intel.com ([10.7.209.21])\n\tby fmsmga101.fm.intel.com with ESMTP; 09 Jul 2015 05:19:41 -0700", "from irvmail001.ir.intel.com ([163.33.26.43])\n\tby orsmga002.jf.intel.com with ESMTP; 09 Jul 2015 05:19:39 -0700", "from sivswdev02.ir.intel.com (sivswdev02.ir.intel.com\n\t[10.237.217.46])\n\tby irvmail001.ir.intel.com (8.14.3/8.13.6/MailSET/Hub) with ESMTP id\n\tt69CJcYg018761 for <dev@dpdk.org>; Thu, 9 Jul 2015 13:19:39 +0100", "from sivswdev02.ir.intel.com (localhost [127.0.0.1])\n\tby sivswdev02.ir.intel.com with ESMTP id t69CJcv0029147\n\tfor <dev@dpdk.org>; Thu, 9 Jul 2015 13:19:38 +0100", "(from pdelarax@localhost)\n\tby sivswdev02.ir.intel.com with id t69CJcrV029143\n\tfor dev@dpdk.org; Thu, 9 Jul 2015 13:19:38 +0100" ], "X-ExtLoop1": "1", "X-IronPort-AV": "E=Sophos;i=\"5.15,439,1432623600\"; d=\"scan'208\";a=\"761219153\"", "From": "Pablo de Lara <pablo.de.lara.guarch@intel.com>", "To": "dev@dpdk.org", "Date": "Thu, 9 Jul 2015 13:19:38 +0100", "Message-Id": "<1436444378-29106-2-git-send-email-pablo.de.lara.guarch@intel.com>", "X-Mailer": "git-send-email 1.7.4.1", "In-Reply-To": "<1436444378-29106-1-git-send-email-pablo.de.lara.guarch@intel.com>", "References": "<1436373007-9711-1-git-send-email-pablo.de.lara.guarch@intel.com>\n\t<1436444378-29106-1-git-send-email-pablo.de.lara.guarch@intel.com>", "Subject": "[dpdk-dev] [PATCH v3] test/hash: improve hash unit tests", "X-BeenThere": "dev@dpdk.org", "X-Mailman-Version": "2.1.15", "Precedence": "list", "List-Id": "patches and discussions about DPDK <dev.dpdk.org>", "List-Unsubscribe": "<http://dpdk.org/ml/options/dev>,\n\t<mailto:dev-request@dpdk.org?subject=unsubscribe>", "List-Archive": "<http://dpdk.org/ml/archives/dev/>", "List-Post": "<mailto:dev@dpdk.org>", "List-Help": "<mailto:dev-request@dpdk.org?subject=help>", "List-Subscribe": "<http://dpdk.org/ml/listinfo/dev>,\n\t<mailto:dev-request@dpdk.org?subject=subscribe>", "Errors-To": "dev-bounces@dpdk.org", "Sender": "\"dev\" <dev-bounces@dpdk.org>" }, "content": "Add new unit test for calculating the average table utilization,\nusing random keys, based on number of entries that can be added\nuntil we encounter one that cannot be added (bucket if full)\n\nAlso, replace current hash_perf unit test to see performance more clear.\nThe current hash_perf unit test takes too long and add keys that\nmay or may not fit in the table and look up/delete that may not be\nin the table. This new unit test gets a set of keys that we know\nthat fits in the table, and then measure the time to add/look up/delete\nthem.\n\nSigned-off-by: Pablo de Lara <pablo.de.lara.guarch@intel.com>\n---\n app/test/test_hash.c | 66 +++-\n app/test/test_hash_perf.c | 927 ++++++++++++++++++++--------------------------\n 2 files changed, 462 insertions(+), 531 deletions(-)", "diff": "diff --git a/app/test/test_hash.c b/app/test/test_hash.c\nindex 4300de9..7c71ed6 100644\n--- a/app/test/test_hash.c\n+++ b/app/test/test_hash.c\n@@ -190,7 +190,7 @@ test_crc32_hash_alg_equiv(void)\n \tunsigned i, j;\n \tsize_t data_len;\n \n-\tprintf(\"# CRC32 implementations equivalence test\\n\");\n+\tprintf(\"\\n# CRC32 implementations equivalence test\\n\");\n \tfor (i = 0; i < CRC32_ITERATIONS; i++) {\n \t\t/* Randomizing data_len of data set */\n \t\tdata_len = (size_t) ((rte_rand() % sizeof(data64)) + 1);\n@@ -785,7 +785,7 @@ fbk_hash_unit_test(void)\n \n \t/* Try creating hashes with invalid parameters */\n \tprintf(\"# Testing hash creation with invalid parameters \"\n-\t\t\t\"- expert error msgs\\n\");\n+\t\t\t\"- expect error msgs\\n\");\n \thandle = rte_fbk_hash_create(&invalid_params_1);\n \tRETURN_IF_ERROR_FBK(handle != NULL, \"fbk hash creation should have failed\");\n \n@@ -1087,6 +1087,7 @@ static int test_hash_creation_with_bad_parameters(void)\n \t}\n \n \trte_hash_free(handle);\n+\tprintf(\"# Test successful. No more errors expected\\n\");\n \n \treturn 0;\n }\n@@ -1147,6 +1148,65 @@ test_hash_creation_with_good_parameters(void)\n \treturn 0;\n }\n \n+#define ITERATIONS 50\n+/*\n+ * Test to see the average table utilization (entries added/max entries)\n+ * before hitting a random entry that cannot be added\n+ */\n+static int test_average_table_utilization(void)\n+{\n+\tstruct rte_hash *handle;\n+\tuint8_t simple_key[RTE_HASH_KEY_LENGTH_MAX];\n+\tunsigned i, j;\n+\tunsigned added_keys, average_keys_added = 0;\n+\tint ret;\n+\n+\tprintf(\"\\n# Running test to determine average utilization\"\n+\t \"\\n before adding elements begins to fail\\n\");\n+\tprintf(\"Measuring performance, please wait\");\n+\tfflush(stdout);\n+\tut_params.entries = 1 << 20;\n+\tut_params.name = \"test_average_utilization\";\n+\tut_params.hash_func = rte_jhash;\n+\thandle = rte_hash_create(&ut_params);\n+\tRETURN_IF_ERROR(handle == NULL, \"hash creation failed\");\n+\n+\tfor (j = 0; j < ITERATIONS; j++) {\n+\t\tret = 0;\n+\t\t/* Add random entries until key cannot be added */\n+\t\tfor (added_keys = 0; ret >= 0; added_keys++) {\n+\t\t\tfor (i = 0; i < ut_params.key_len; i++)\n+\t\t\t\tsimple_key[i] = rte_rand() % 255;\n+\t\t\tret = rte_hash_add_key(handle, simple_key);\n+\t\t}\n+\t\tif (ret != -ENOSPC) {\n+\t\t\tprintf(\"Unexpected error when adding keys\\n\");\n+\t\t\trte_hash_free(handle);\n+\t\t\treturn -1;\n+\t\t}\n+\n+\t\taverage_keys_added += added_keys;\n+\n+\t\t/* Reset the table */\n+\t\trte_hash_free(handle);\n+\t\thandle = rte_hash_create(&ut_params);\n+\t\tRETURN_IF_ERROR(handle == NULL, \"hash creation failed\");\n+\n+\t\t/* Print a dot to show progress on operations */\n+\t\tprintf(\".\");\n+\t\tfflush(stdout);\n+\t}\n+\n+\taverage_keys_added /= ITERATIONS;\n+\n+\tprintf(\"\\nAverage table utilization = %.2f%% (%u/%u)\\n\",\n+\t\t((double) average_keys_added / ut_params.entries * 100),\n+\t\taverage_keys_added, ut_params.entries);\n+\trte_hash_free(handle);\n+\n+\treturn 0;\n+}\n+\n static uint8_t key[16] = {0x00, 0x01, 0x02, 0x03,\n \t\t\t0x04, 0x05, 0x06, 0x07,\n \t\t\t0x08, 0x09, 0x0a, 0x0b,\n@@ -1405,6 +1465,8 @@ test_hash(void)\n \t\treturn -1;\n \tif (test_hash_creation_with_good_parameters() < 0)\n \t\treturn -1;\n+\tif (test_average_table_utilization() < 0)\n+\t\treturn -1;\n \n \trun_hash_func_tests();\n \ndiff --git a/app/test/test_hash_perf.c b/app/test/test_hash_perf.c\nindex d0e5ce0..7acba59 100644\n--- a/app/test/test_hash_perf.c\n+++ b/app/test/test_hash_perf.c\n@@ -32,574 +32,440 @@\n */\n \n #include <stdio.h>\n-#include <stdint.h>\n-#include <string.h>\n-#include <stdlib.h>\n-#include <stdarg.h>\n-#include <errno.h>\n-#include <sys/queue.h>\n-\n-#include <rte_common.h>\n+#include <inttypes.h>\n+\n #include <rte_lcore.h>\n-#include <rte_malloc.h>\n #include <rte_cycles.h>\n+#include <rte_malloc.h>\n+#include <rte_hash.h>\n+#include <rte_hash_crc.h>\n+#include <rte_jhash.h>\n+#include <rte_fbk_hash.h>\n #include <rte_random.h>\n-#include <rte_memory.h>\n-#include <rte_memzone.h>\n-#include <rte_eal.h>\n-#include <rte_ip.h>\n #include <rte_string_fns.h>\n \n #include \"test.h\"\n \n-#include <rte_hash.h>\n-#include <rte_fbk_hash.h>\n-#include <rte_jhash.h>\n-#include <rte_hash_crc.h>\n-\n-/* Types of hash table performance test that can be performed */\n-enum hash_test_t {\n-\tADD_ON_EMPTY,\t\t/*< Add keys to empty table */\n-\tDELETE_ON_EMPTY,\t/*< Attempt to delete keys from empty table */\n-\tLOOKUP_ON_EMPTY,\t/*< Attempt to find keys in an empty table */\n-\tADD_UPDATE,\t\t/*< Add/update keys in a full table */\n-\tDELETE,\t\t\t/*< Delete keys from a full table */\n-\tLOOKUP\t\t\t/*< Find keys in a full table */\n+#define MAX_ENTRIES (1 << 20)\n+#define KEYS_TO_ADD (MAX_ENTRIES * 3 / 4) /* 75% table utilization */\n+#define NUM_LOOKUPS (KEYS_TO_ADD * 10) /* Loop among keys added, several times */\n+#define BUCKET_SIZE 4\n+#define NUM_BUCKETS (MAX_ENTRIES / BUCKET_SIZE)\n+#define MAX_KEYSIZE 64\n+#define NUM_KEYSIZES 10\n+#define NUM_SHUFFLES 10\n+#define BURST_SIZE 16\n+\n+enum operations {\n+\tADD = 0,\n+\tLOOKUP,\n+\tLOOKUP_MULTI,\n+\tDELETE,\n+\tNUM_OPERATIONS\n };\n \n-/* Function type for hash table operations. */\n-typedef int32_t (*hash_operation)(const struct rte_hash *h, const void *key);\n-\n-/* Structure to hold parameters used to run a hash table performance test */\n-struct tbl_perf_test_params {\n-\tenum hash_test_t test_type;\n-\tuint32_t num_iterations;\n-\tuint32_t entries;\n-\tuint32_t bucket_entries;\n-\tuint32_t key_len;\n-\trte_hash_function hash_func;\n-\tuint32_t hash_func_init_val;\n+static uint32_t hashtest_key_lens[] = {\n+\t/* standard key sizes */\n+\t4, 8, 16, 32, 48, 64,\n+\t/* IPv4 SRC + DST + protocol, unpadded */\n+\t9,\n+\t/* IPv4 5-tuple, unpadded */\n+\t13,\n+\t/* IPv6 5-tuple, unpadded */\n+\t37,\n+\t/* IPv6 5-tuple, padded to 8-byte boundary */\n+\t40\n };\n \n-#define ITERATIONS 10000\n-#define LOCAL_FBK_HASH_ENTRIES_MAX (1 << 15)\n+struct rte_hash *h[NUM_KEYSIZES];\n \n-/*******************************************************************************\n- * Hash table performance test configuration section.\n- */\n-struct tbl_perf_test_params tbl_perf_params[] =\n-{\n-/* Small table, add */\n-/* Test type | Iterations | Entries | BucketSize | KeyLen | HashFunc | InitVal */\n-{ ADD_ON_EMPTY, 1024, 1024, 1, 16, rte_jhash, 0},\n-{ ADD_ON_EMPTY, 1024, 1024, 2, 16, rte_jhash, 0},\n-{ ADD_ON_EMPTY, 1024, 1024, 4, 16, rte_jhash, 0},\n-{ ADD_ON_EMPTY, 1024, 1024, 8, 16, rte_jhash, 0},\n-{ ADD_ON_EMPTY, 1024, 1024, 16, 16, rte_jhash, 0},\n-{ ADD_ON_EMPTY, 1024, 1024, 1, 32, rte_jhash, 0},\n-{ ADD_ON_EMPTY, 1024, 1024, 2, 32, rte_jhash, 0},\n-{ ADD_ON_EMPTY, 1024, 1024, 4, 32, rte_jhash, 0},\n-{ ADD_ON_EMPTY, 1024, 1024, 8, 32, rte_jhash, 0},\n-{ ADD_ON_EMPTY, 1024, 1024, 16, 32, rte_jhash, 0},\n-{ ADD_ON_EMPTY, 1024, 1024, 1, 48, rte_jhash, 0},\n-{ ADD_ON_EMPTY, 1024, 1024, 2, 48, rte_jhash, 0},\n-{ ADD_ON_EMPTY, 1024, 1024, 4, 48, rte_jhash, 0},\n-{ ADD_ON_EMPTY, 1024, 1024, 8, 48, rte_jhash, 0},\n-{ ADD_ON_EMPTY, 1024, 1024, 16, 48, rte_jhash, 0},\n-{ ADD_ON_EMPTY, 1024, 1024, 1, 64, rte_jhash, 0},\n-{ ADD_ON_EMPTY, 1024, 1024, 2, 64, rte_jhash, 0},\n-{ ADD_ON_EMPTY, 1024, 1024, 4, 64, rte_jhash, 0},\n-{ ADD_ON_EMPTY, 1024, 1024, 8, 64, rte_jhash, 0},\n-{ ADD_ON_EMPTY, 1024, 1024, 16, 64, rte_jhash, 0},\n-/* Small table, update */\n-/* Test type | Iterations | Entries | BucketSize | KeyLen | HashFunc | InitVal */\n-{ ADD_UPDATE, ITERATIONS, 1024, 1, 16, rte_jhash, 0},\n-{ ADD_UPDATE, ITERATIONS, 1024, 2, 16, rte_jhash, 0},\n-{ ADD_UPDATE, ITERATIONS, 1024, 4, 16, rte_jhash, 0},\n-{ ADD_UPDATE, ITERATIONS, 1024, 8, 16, rte_jhash, 0},\n-{ ADD_UPDATE, ITERATIONS, 1024, 16, 16, rte_jhash, 0},\n-{ ADD_UPDATE, ITERATIONS, 1024, 1, 32, rte_jhash, 0},\n-{ ADD_UPDATE, ITERATIONS, 1024, 2, 32, rte_jhash, 0},\n-{ ADD_UPDATE, ITERATIONS, 1024, 4, 32, rte_jhash, 0},\n-{ ADD_UPDATE, ITERATIONS, 1024, 8, 32, rte_jhash, 0},\n-{ ADD_UPDATE, ITERATIONS, 1024, 16, 32, rte_jhash, 0},\n-{ ADD_UPDATE, ITERATIONS, 1024, 1, 48, rte_jhash, 0},\n-{ ADD_UPDATE, ITERATIONS, 1024, 2, 48, rte_jhash, 0},\n-{ ADD_UPDATE, ITERATIONS, 1024, 4, 48, rte_jhash, 0},\n-{ ADD_UPDATE, ITERATIONS, 1024, 8, 48, rte_jhash, 0},\n-{ ADD_UPDATE, ITERATIONS, 1024, 16, 48, rte_jhash, 0},\n-{ ADD_UPDATE, ITERATIONS, 1024, 1, 64, rte_jhash, 0},\n-{ ADD_UPDATE, ITERATIONS, 1024, 2, 64, rte_jhash, 0},\n-{ ADD_UPDATE, ITERATIONS, 1024, 4, 64, rte_jhash, 0},\n-{ ADD_UPDATE, ITERATIONS, 1024, 8, 64, rte_jhash, 0},\n-{ ADD_UPDATE, ITERATIONS, 1024, 16, 64, rte_jhash, 0},\n-/* Small table, lookup */\n-/* Test type | Iterations | Entries | BucketSize | KeyLen | HashFunc | InitVal */\n-{ LOOKUP, ITERATIONS, 1024, 1, 16, rte_jhash, 0},\n-{ LOOKUP, ITERATIONS, 1024, 2, 16, rte_jhash, 0},\n-{ LOOKUP, ITERATIONS, 1024, 4, 16, rte_jhash, 0},\n-{ LOOKUP, ITERATIONS, 1024, 8, 16, rte_jhash, 0},\n-{ LOOKUP, ITERATIONS, 1024, 16, 16, rte_jhash, 0},\n-{ LOOKUP, ITERATIONS, 1024, 1, 32, rte_jhash, 0},\n-{ LOOKUP, ITERATIONS, 1024, 2, 32, rte_jhash, 0},\n-{ LOOKUP, ITERATIONS, 1024, 4, 32, rte_jhash, 0},\n-{ LOOKUP, ITERATIONS, 1024, 8, 32, rte_jhash, 0},\n-{ LOOKUP, ITERATIONS, 1024, 16, 32, rte_jhash, 0},\n-{ LOOKUP, ITERATIONS, 1024, 1, 48, rte_jhash, 0},\n-{ LOOKUP, ITERATIONS, 1024, 2, 48, rte_jhash, 0},\n-{ LOOKUP, ITERATIONS, 1024, 4, 48, rte_jhash, 0},\n-{ LOOKUP, ITERATIONS, 1024, 8, 48, rte_jhash, 0},\n-{ LOOKUP, ITERATIONS, 1024, 16, 48, rte_jhash, 0},\n-{ LOOKUP, ITERATIONS, 1024, 1, 64, rte_jhash, 0},\n-{ LOOKUP, ITERATIONS, 1024, 2, 64, rte_jhash, 0},\n-{ LOOKUP, ITERATIONS, 1024, 4, 64, rte_jhash, 0},\n-{ LOOKUP, ITERATIONS, 1024, 8, 64, rte_jhash, 0},\n-{ LOOKUP, ITERATIONS, 1024, 16, 64, rte_jhash, 0},\n-/* Big table, add */\n-/* Test type | Iterations | Entries | BucketSize | KeyLen | HashFunc | InitVal */\n-{ ADD_ON_EMPTY, 1048576, 1048576, 1, 16, rte_jhash, 0},\n-{ ADD_ON_EMPTY, 1048576, 1048576, 2, 16, rte_jhash, 0},\n-{ ADD_ON_EMPTY, 1048576, 1048576, 4, 16, rte_jhash, 0},\n-{ ADD_ON_EMPTY, 1048576, 1048576, 8, 16, rte_jhash, 0},\n-{ ADD_ON_EMPTY, 1048576, 1048576, 16, 16, rte_jhash, 0},\n-{ ADD_ON_EMPTY, 1048576, 1048576, 1, 32, rte_jhash, 0},\n-{ ADD_ON_EMPTY, 1048576, 1048576, 2, 32, rte_jhash, 0},\n-{ ADD_ON_EMPTY, 1048576, 1048576, 4, 32, rte_jhash, 0},\n-{ ADD_ON_EMPTY, 1048576, 1048576, 8, 32, rte_jhash, 0},\n-{ ADD_ON_EMPTY, 1048576, 1048576, 16, 32, rte_jhash, 0},\n-{ ADD_ON_EMPTY, 1048576, 1048576, 1, 48, rte_jhash, 0},\n-{ ADD_ON_EMPTY, 1048576, 1048576, 2, 48, rte_jhash, 0},\n-{ ADD_ON_EMPTY, 1048576, 1048576, 4, 48, rte_jhash, 0},\n-{ ADD_ON_EMPTY, 1048576, 1048576, 8, 48, rte_jhash, 0},\n-{ ADD_ON_EMPTY, 1048576, 1048576, 16, 48, rte_jhash, 0},\n-{ ADD_ON_EMPTY, 1048576, 1048576, 1, 64, rte_jhash, 0},\n-{ ADD_ON_EMPTY, 1048576, 1048576, 2, 64, rte_jhash, 0},\n-{ ADD_ON_EMPTY, 1048576, 1048576, 4, 64, rte_jhash, 0},\n-{ ADD_ON_EMPTY, 1048576, 1048576, 8, 64, rte_jhash, 0},\n-{ ADD_ON_EMPTY, 1048576, 1048576, 16, 64, rte_jhash, 0},\n-/* Big table, update */\n-/* Test type | Iterations | Entries | BucketSize | KeyLen | HashFunc | InitVal */\n-{ ADD_UPDATE, ITERATIONS, 1048576, 1, 16, rte_jhash, 0},\n-{ ADD_UPDATE, ITERATIONS, 1048576, 2, 16, rte_jhash, 0},\n-{ ADD_UPDATE, ITERATIONS, 1048576, 4, 16, rte_jhash, 0},\n-{ ADD_UPDATE, ITERATIONS, 1048576, 8, 16, rte_jhash, 0},\n-{ ADD_UPDATE, ITERATIONS, 1048576, 16, 16, rte_jhash, 0},\n-{ ADD_UPDATE, ITERATIONS, 1048576, 1, 32, rte_jhash, 0},\n-{ ADD_UPDATE, ITERATIONS, 1048576, 2, 32, rte_jhash, 0},\n-{ ADD_UPDATE, ITERATIONS, 1048576, 4, 32, rte_jhash, 0},\n-{ ADD_UPDATE, ITERATIONS, 1048576, 8, 32, rte_jhash, 0},\n-{ ADD_UPDATE, ITERATIONS, 1048576, 16, 32, rte_jhash, 0},\n-{ ADD_UPDATE, ITERATIONS, 1048576, 1, 48, rte_jhash, 0},\n-{ ADD_UPDATE, ITERATIONS, 1048576, 2, 48, rte_jhash, 0},\n-{ ADD_UPDATE, ITERATIONS, 1048576, 4, 48, rte_jhash, 0},\n-{ ADD_UPDATE, ITERATIONS, 1048576, 8, 48, rte_jhash, 0},\n-{ ADD_UPDATE, ITERATIONS, 1048576, 16, 48, rte_jhash, 0},\n-{ ADD_UPDATE, ITERATIONS, 1048576, 1, 64, rte_jhash, 0},\n-{ ADD_UPDATE, ITERATIONS, 1048576, 2, 64, rte_jhash, 0},\n-{ ADD_UPDATE, ITERATIONS, 1048576, 4, 64, rte_jhash, 0},\n-{ ADD_UPDATE, ITERATIONS, 1048576, 8, 64, rte_jhash, 0},\n-{ ADD_UPDATE, ITERATIONS, 1048576, 16, 64, rte_jhash, 0},\n-/* Big table, lookup */\n-/* Test type | Iterations | Entries | BucketSize | KeyLen | HashFunc | InitVal */\n-{ LOOKUP, ITERATIONS, 1048576, 1, 16, rte_jhash, 0},\n-{ LOOKUP, ITERATIONS, 1048576, 2, 16, rte_jhash, 0},\n-{ LOOKUP, ITERATIONS, 1048576, 4, 16, rte_jhash, 0},\n-{ LOOKUP, ITERATIONS, 1048576, 8, 16, rte_jhash, 0},\n-{ LOOKUP, ITERATIONS, 1048576, 16, 16, rte_jhash, 0},\n-{ LOOKUP, ITERATIONS, 1048576, 1, 32, rte_jhash, 0},\n-{ LOOKUP, ITERATIONS, 1048576, 2, 32, rte_jhash, 0},\n-{ LOOKUP, ITERATIONS, 1048576, 4, 32, rte_jhash, 0},\n-{ LOOKUP, ITERATIONS, 1048576, 8, 32, rte_jhash, 0},\n-{ LOOKUP, ITERATIONS, 1048576, 16, 32, rte_jhash, 0},\n-{ LOOKUP, ITERATIONS, 1048576, 1, 48, rte_jhash, 0},\n-{ LOOKUP, ITERATIONS, 1048576, 2, 48, rte_jhash, 0},\n-{ LOOKUP, ITERATIONS, 1048576, 4, 48, rte_jhash, 0},\n-{ LOOKUP, ITERATIONS, 1048576, 8, 48, rte_jhash, 0},\n-{ LOOKUP, ITERATIONS, 1048576, 16, 48, rte_jhash, 0},\n-{ LOOKUP, ITERATIONS, 1048576, 1, 64, rte_jhash, 0},\n-{ LOOKUP, ITERATIONS, 1048576, 2, 64, rte_jhash, 0},\n-{ LOOKUP, ITERATIONS, 1048576, 4, 64, rte_jhash, 0},\n-{ LOOKUP, ITERATIONS, 1048576, 8, 64, rte_jhash, 0},\n-{ LOOKUP, ITERATIONS, 1048576, 16, 64, rte_jhash, 0},\n-/* Small table, add */\n-/* Test type | Iterations | Entries | BucketSize | KeyLen | HashFunc | InitVal */\n-{ ADD_ON_EMPTY, 1024, 1024, 1, 16, rte_hash_crc, 0},\n-{ ADD_ON_EMPTY, 1024, 1024, 2, 16, rte_hash_crc, 0},\n-{ ADD_ON_EMPTY, 1024, 1024, 4, 16, rte_hash_crc, 0},\n-{ ADD_ON_EMPTY, 1024, 1024, 8, 16, rte_hash_crc, 0},\n-{ ADD_ON_EMPTY, 1024, 1024, 16, 16, rte_hash_crc, 0},\n-{ ADD_ON_EMPTY, 1024, 1024, 1, 32, rte_hash_crc, 0},\n-{ ADD_ON_EMPTY, 1024, 1024, 2, 32, rte_hash_crc, 0},\n-{ ADD_ON_EMPTY, 1024, 1024, 4, 32, rte_hash_crc, 0},\n-{ ADD_ON_EMPTY, 1024, 1024, 8, 32, rte_hash_crc, 0},\n-{ ADD_ON_EMPTY, 1024, 1024, 16, 32, rte_hash_crc, 0},\n-{ ADD_ON_EMPTY, 1024, 1024, 1, 48, rte_hash_crc, 0},\n-{ ADD_ON_EMPTY, 1024, 1024, 2, 48, rte_hash_crc, 0},\n-{ ADD_ON_EMPTY, 1024, 1024, 4, 48, rte_hash_crc, 0},\n-{ ADD_ON_EMPTY, 1024, 1024, 8, 48, rte_hash_crc, 0},\n-{ ADD_ON_EMPTY, 1024, 1024, 16, 48, rte_hash_crc, 0},\n-{ ADD_ON_EMPTY, 1024, 1024, 1, 64, rte_hash_crc, 0},\n-{ ADD_ON_EMPTY, 1024, 1024, 2, 64, rte_hash_crc, 0},\n-{ ADD_ON_EMPTY, 1024, 1024, 4, 64, rte_hash_crc, 0},\n-{ ADD_ON_EMPTY, 1024, 1024, 8, 64, rte_hash_crc, 0},\n-{ ADD_ON_EMPTY, 1024, 1024, 16, 64, rte_hash_crc, 0},\n-/* Small table, update */\n-/* Test type | Iterations | Entries | BucketSize | KeyLen | HashFunc | InitVal */\n-{ ADD_UPDATE, ITERATIONS, 1024, 1, 16, rte_hash_crc, 0},\n-{ ADD_UPDATE, ITERATIONS, 1024, 2, 16, rte_hash_crc, 0},\n-{ ADD_UPDATE, ITERATIONS, 1024, 4, 16, rte_hash_crc, 0},\n-{ ADD_UPDATE, ITERATIONS, 1024, 8, 16, rte_hash_crc, 0},\n-{ ADD_UPDATE, ITERATIONS, 1024, 16, 16, rte_hash_crc, 0},\n-{ ADD_UPDATE, ITERATIONS, 1024, 1, 32, rte_hash_crc, 0},\n-{ ADD_UPDATE, ITERATIONS, 1024, 2, 32, rte_hash_crc, 0},\n-{ ADD_UPDATE, ITERATIONS, 1024, 4, 32, rte_hash_crc, 0},\n-{ ADD_UPDATE, ITERATIONS, 1024, 8, 32, rte_hash_crc, 0},\n-{ ADD_UPDATE, ITERATIONS, 1024, 16, 32, rte_hash_crc, 0},\n-{ ADD_UPDATE, ITERATIONS, 1024, 1, 48, rte_hash_crc, 0},\n-{ ADD_UPDATE, ITERATIONS, 1024, 2, 48, rte_hash_crc, 0},\n-{ ADD_UPDATE, ITERATIONS, 1024, 4, 48, rte_hash_crc, 0},\n-{ ADD_UPDATE, ITERATIONS, 1024, 8, 48, rte_hash_crc, 0},\n-{ ADD_UPDATE, ITERATIONS, 1024, 16, 48, rte_hash_crc, 0},\n-{ ADD_UPDATE, ITERATIONS, 1024, 1, 64, rte_hash_crc, 0},\n-{ ADD_UPDATE, ITERATIONS, 1024, 2, 64, rte_hash_crc, 0},\n-{ ADD_UPDATE, ITERATIONS, 1024, 4, 64, rte_hash_crc, 0},\n-{ ADD_UPDATE, ITERATIONS, 1024, 8, 64, rte_hash_crc, 0},\n-{ ADD_UPDATE, ITERATIONS, 1024, 16, 64, rte_hash_crc, 0},\n-/* Small table, lookup */\n-/* Test type | Iterations | Entries | BucketSize | KeyLen | HashFunc | InitVal */\n-{ LOOKUP, ITERATIONS, 1024, 1, 16, rte_hash_crc, 0},\n-{ LOOKUP, ITERATIONS, 1024, 2, 16, rte_hash_crc, 0},\n-{ LOOKUP, ITERATIONS, 1024, 4, 16, rte_hash_crc, 0},\n-{ LOOKUP, ITERATIONS, 1024, 8, 16, rte_hash_crc, 0},\n-{ LOOKUP, ITERATIONS, 1024, 16, 16, rte_hash_crc, 0},\n-{ LOOKUP, ITERATIONS, 1024, 1, 32, rte_hash_crc, 0},\n-{ LOOKUP, ITERATIONS, 1024, 2, 32, rte_hash_crc, 0},\n-{ LOOKUP, ITERATIONS, 1024, 4, 32, rte_hash_crc, 0},\n-{ LOOKUP, ITERATIONS, 1024, 8, 32, rte_hash_crc, 0},\n-{ LOOKUP, ITERATIONS, 1024, 16, 32, rte_hash_crc, 0},\n-{ LOOKUP, ITERATIONS, 1024, 1, 48, rte_hash_crc, 0},\n-{ LOOKUP, ITERATIONS, 1024, 2, 48, rte_hash_crc, 0},\n-{ LOOKUP, ITERATIONS, 1024, 4, 48, rte_hash_crc, 0},\n-{ LOOKUP, ITERATIONS, 1024, 8, 48, rte_hash_crc, 0},\n-{ LOOKUP, ITERATIONS, 1024, 16, 48, rte_hash_crc, 0},\n-{ LOOKUP, ITERATIONS, 1024, 1, 64, rte_hash_crc, 0},\n-{ LOOKUP, ITERATIONS, 1024, 2, 64, rte_hash_crc, 0},\n-{ LOOKUP, ITERATIONS, 1024, 4, 64, rte_hash_crc, 0},\n-{ LOOKUP, ITERATIONS, 1024, 8, 64, rte_hash_crc, 0},\n-{ LOOKUP, ITERATIONS, 1024, 16, 64, rte_hash_crc, 0},\n-/* Big table, add */\n-/* Test type | Iterations | Entries | BucketSize | KeyLen | HashFunc | InitVal */\n-{ ADD_ON_EMPTY, 1048576, 1048576, 1, 16, rte_hash_crc, 0},\n-{ ADD_ON_EMPTY, 1048576, 1048576, 2, 16, rte_hash_crc, 0},\n-{ ADD_ON_EMPTY, 1048576, 1048576, 4, 16, rte_hash_crc, 0},\n-{ ADD_ON_EMPTY, 1048576, 1048576, 8, 16, rte_hash_crc, 0},\n-{ ADD_ON_EMPTY, 1048576, 1048576, 16, 16, rte_hash_crc, 0},\n-{ ADD_ON_EMPTY, 1048576, 1048576, 1, 32, rte_hash_crc, 0},\n-{ ADD_ON_EMPTY, 1048576, 1048576, 2, 32, rte_hash_crc, 0},\n-{ ADD_ON_EMPTY, 1048576, 1048576, 4, 32, rte_hash_crc, 0},\n-{ ADD_ON_EMPTY, 1048576, 1048576, 8, 32, rte_hash_crc, 0},\n-{ ADD_ON_EMPTY, 1048576, 1048576, 16, 32, rte_hash_crc, 0},\n-{ ADD_ON_EMPTY, 1048576, 1048576, 1, 48, rte_hash_crc, 0},\n-{ ADD_ON_EMPTY, 1048576, 1048576, 2, 48, rte_hash_crc, 0},\n-{ ADD_ON_EMPTY, 1048576, 1048576, 4, 48, rte_hash_crc, 0},\n-{ ADD_ON_EMPTY, 1048576, 1048576, 8, 48, rte_hash_crc, 0},\n-{ ADD_ON_EMPTY, 1048576, 1048576, 16, 48, rte_hash_crc, 0},\n-{ ADD_ON_EMPTY, 1048576, 1048576, 1, 64, rte_hash_crc, 0},\n-{ ADD_ON_EMPTY, 1048576, 1048576, 2, 64, rte_hash_crc, 0},\n-{ ADD_ON_EMPTY, 1048576, 1048576, 4, 64, rte_hash_crc, 0},\n-{ ADD_ON_EMPTY, 1048576, 1048576, 8, 64, rte_hash_crc, 0},\n-{ ADD_ON_EMPTY, 1048576, 1048576, 16, 64, rte_hash_crc, 0},\n-/* Big table, update */\n-/* Test type | Iterations | Entries | BucketSize | KeyLen | HashFunc | InitVal */\n-{ ADD_UPDATE, ITERATIONS, 1048576, 1, 16, rte_hash_crc, 0},\n-{ ADD_UPDATE, ITERATIONS, 1048576, 2, 16, rte_hash_crc, 0},\n-{ ADD_UPDATE, ITERATIONS, 1048576, 4, 16, rte_hash_crc, 0},\n-{ ADD_UPDATE, ITERATIONS, 1048576, 8, 16, rte_hash_crc, 0},\n-{ ADD_UPDATE, ITERATIONS, 1048576, 16, 16, rte_hash_crc, 0},\n-{ ADD_UPDATE, ITERATIONS, 1048576, 1, 32, rte_hash_crc, 0},\n-{ ADD_UPDATE, ITERATIONS, 1048576, 2, 32, rte_hash_crc, 0},\n-{ ADD_UPDATE, ITERATIONS, 1048576, 4, 32, rte_hash_crc, 0},\n-{ ADD_UPDATE, ITERATIONS, 1048576, 8, 32, rte_hash_crc, 0},\n-{ ADD_UPDATE, ITERATIONS, 1048576, 16, 32, rte_hash_crc, 0},\n-{ ADD_UPDATE, ITERATIONS, 1048576, 1, 48, rte_hash_crc, 0},\n-{ ADD_UPDATE, ITERATIONS, 1048576, 2, 48, rte_hash_crc, 0},\n-{ ADD_UPDATE, ITERATIONS, 1048576, 4, 48, rte_hash_crc, 0},\n-{ ADD_UPDATE, ITERATIONS, 1048576, 8, 48, rte_hash_crc, 0},\n-{ ADD_UPDATE, ITERATIONS, 1048576, 16, 48, rte_hash_crc, 0},\n-{ ADD_UPDATE, ITERATIONS, 1048576, 1, 64, rte_hash_crc, 0},\n-{ ADD_UPDATE, ITERATIONS, 1048576, 2, 64, rte_hash_crc, 0},\n-{ ADD_UPDATE, ITERATIONS, 1048576, 4, 64, rte_hash_crc, 0},\n-{ ADD_UPDATE, ITERATIONS, 1048576, 8, 64, rte_hash_crc, 0},\n-{ ADD_UPDATE, ITERATIONS, 1048576, 16, 64, rte_hash_crc, 0},\n-/* Big table, lookup */\n-/* Test type | Iterations | Entries | BucketSize | KeyLen | HashFunc | InitVal */\n-{ LOOKUP, ITERATIONS, 1048576, 1, 16, rte_hash_crc, 0},\n-{ LOOKUP, ITERATIONS, 1048576, 2, 16, rte_hash_crc, 0},\n-{ LOOKUP, ITERATIONS, 1048576, 4, 16, rte_hash_crc, 0},\n-{ LOOKUP, ITERATIONS, 1048576, 8, 16, rte_hash_crc, 0},\n-{ LOOKUP, ITERATIONS, 1048576, 16, 16, rte_hash_crc, 0},\n-{ LOOKUP, ITERATIONS, 1048576, 1, 32, rte_hash_crc, 0},\n-{ LOOKUP, ITERATIONS, 1048576, 2, 32, rte_hash_crc, 0},\n-{ LOOKUP, ITERATIONS, 1048576, 4, 32, rte_hash_crc, 0},\n-{ LOOKUP, ITERATIONS, 1048576, 8, 32, rte_hash_crc, 0},\n-{ LOOKUP, ITERATIONS, 1048576, 16, 32, rte_hash_crc, 0},\n-{ LOOKUP, ITERATIONS, 1048576, 1, 48, rte_hash_crc, 0},\n-{ LOOKUP, ITERATIONS, 1048576, 2, 48, rte_hash_crc, 0},\n-{ LOOKUP, ITERATIONS, 1048576, 4, 48, rte_hash_crc, 0},\n-{ LOOKUP, ITERATIONS, 1048576, 8, 48, rte_hash_crc, 0},\n-{ LOOKUP, ITERATIONS, 1048576, 16, 48, rte_hash_crc, 0},\n-{ LOOKUP, ITERATIONS, 1048576, 1, 64, rte_hash_crc, 0},\n-{ LOOKUP, ITERATIONS, 1048576, 2, 64, rte_hash_crc, 0},\n-{ LOOKUP, ITERATIONS, 1048576, 4, 64, rte_hash_crc, 0},\n-{ LOOKUP, ITERATIONS, 1048576, 8, 64, rte_hash_crc, 0},\n-{ LOOKUP, ITERATIONS, 1048576, 16, 64, rte_hash_crc, 0},\n-};\n+/* Array that stores if a slot is full */\n+uint8_t slot_taken[MAX_ENTRIES];\n \n-/******************************************************************************/\n+/* Array to store number of cycles per operation */\n+uint64_t cycles[NUM_KEYSIZES][NUM_OPERATIONS][2];\n \n-/*\n- * Check condition and return an error if true. Assumes that \"handle\" is the\n- * name of the hash structure pointer to be freed.\n- */\n-#define RETURN_IF_ERROR(cond, str, ...) do {\t\t\t\t\\\n-\tif (cond) {\t\t\t\t\t\t\t\\\n-\t\tprintf(\"ERROR line %d: \" str \"\\n\", __LINE__, ##__VA_ARGS__); \\\n-\t\tif (handle) rte_hash_free(handle);\t\t\t\\\n-\t\treturn -1;\t\t\t\t\t\t\\\n-\t}\t\t\t\t\t\t\t\t\\\n-} while(0)\n-\n-#define RETURN_IF_ERROR_FBK(cond, str, ...) do {\t\t\t\t\\\n-\tif (cond) {\t\t\t\t\t\t\t\\\n-\t\tprintf(\"ERROR line %d: \" str \"\\n\", __LINE__, ##__VA_ARGS__); \\\n-\t\tif (handle) rte_fbk_hash_free(handle);\t\t\t\\\n-\t\trte_free(keys);\t\t\t\t\t\t\\\n-\t\treturn -1;\t\t\t\t\t\t\\\n-\t}\t\t\t\t\t\t\t\t\\\n-} while(0)\n+/* Array to store all input keys */\n+uint8_t keys[KEYS_TO_ADD][MAX_KEYSIZE];\n \n-/*\n- * Find average of array of numbers.\n- */\n-static double\n-get_avg(const uint32_t *array, uint32_t size)\n+/* Array to store the precomputed hash for 'keys' */\n+hash_sig_t signatures[KEYS_TO_ADD];\n+\n+/* Array to store how many busy entries have each bucket */\n+uint8_t buckets[NUM_BUCKETS];\n+\n+/* Array to store the positions where keys are added */\n+int32_t positions[KEYS_TO_ADD];\n+\n+/* Parameters used for hash table in unit test functions. */\n+static struct rte_hash_parameters ut_params = {\n+\t.entries = MAX_ENTRIES,\n+\t.bucket_entries = BUCKET_SIZE,\n+\t.hash_func = rte_jhash,\n+\t.hash_func_init_val = 0,\n+};\n+\n+static int\n+create_table(unsigned table_index)\n {\n-\tdouble sum = 0;\n-\tunsigned i;\n-\tfor (i = 0; i < size; i++)\n-\t\tsum += array[i];\n-\treturn sum / (double)size;\n+\tchar name[RTE_HASH_NAMESIZE];\n+\n+\tsprintf(name, \"test_hash%d\", hashtest_key_lens[table_index]);\n+\tut_params.name = name;\n+\tut_params.key_len = hashtest_key_lens[table_index];\n+\tut_params.socket_id = rte_socket_id();\n+\th[table_index] = rte_hash_find_existing(name);\n+\tif (h[table_index] != NULL)\n+\t\t/*\n+\t\t * If table was already created, free it to create it again,\n+\t\t * so we force it is empty\n+\t\t */\n+\t\trte_hash_free(h[table_index]);\n+\th[table_index] = rte_hash_create(&ut_params);\n+\tif (h[table_index] == NULL) {\n+\t\tprintf(\"Error creating table\\n\");\n+\t\treturn -1;\n+\t}\n+\treturn 0;\n+\n }\n \n-/*\n- * To help print out name of hash functions.\n- */\n-static const char *get_hash_name(rte_hash_function f)\n+/* Shuffle the keys that have been added, so lookups will be totally random */\n+static void\n+shuffle_input_keys(unsigned table_index)\n {\n-\tif (f == rte_jhash)\n-\t\treturn \"jhash\";\n+\tunsigned i;\n+\tuint32_t swap_idx;\n+\tuint8_t temp_key[RTE_HASH_KEY_LENGTH_MAX];\n+\thash_sig_t temp_signature;\n+\tint32_t temp_position;\n \n-\tif (f == rte_hash_crc)\n-\t\treturn \"rte_hash_crc\";\n+\tfor (i = KEYS_TO_ADD - 1; i > 0; i--) {\n+\t\tswap_idx = rte_rand() % i;\n \n-\treturn \"UnknownHash\";\n+\t\tmemcpy(temp_key, keys[i], hashtest_key_lens[table_index]);\n+\t\ttemp_signature = signatures[i];\n+\t\ttemp_position = positions[i];\n+\n+\t\tmemcpy(keys[i], keys[swap_idx], hashtest_key_lens[table_index]);\n+\t\tsignatures[i] = signatures[swap_idx];\n+\t\tpositions[i] = positions[swap_idx];\n+\n+\t\tmemcpy(keys[swap_idx], temp_key, hashtest_key_lens[table_index]);\n+\t\tsignatures[swap_idx] = temp_signature;\n+\t\tpositions[swap_idx] = temp_position;\n+\t}\n }\n \n /*\n- * Do a single performance test, of one type of operation.\n- *\n- * @param h\n- * hash table to run test on\n- * @param func\n- * function to call (add, delete or lookup function)\n- * @param avg_occupancy\n- * The average number of entries in each bucket of the hash table\n- * @param invalid_pos_count\n- * The amount of errors (e.g. due to a full bucket).\n- * @return\n- * The average number of ticks per hash function call. A negative number\n- * signifies failure.\n+ * Looks for random keys which\n+ * ALL can fit in hash table (no errors)\n */\n-static double\n-run_single_tbl_perf_test(const struct rte_hash *h, hash_operation func,\n-\t\tconst struct tbl_perf_test_params *params, double *avg_occupancy,\n-\t\tuint32_t *invalid_pos_count)\n+static int\n+get_input_keys(unsigned table_index)\n {\n-\tuint64_t begin, end, ticks = 0;\n-\tuint8_t *key = NULL;\n-\tuint32_t *bucket_occupancies = NULL;\n-\tuint32_t num_buckets, i, j;\n-\tint32_t pos;\n-\n-\t/* Initialise */\n-\tnum_buckets = params->entries / params->bucket_entries;\n-\tkey = rte_zmalloc(\"hash key\",\n-\t\t\t params->key_len * sizeof(uint8_t), 16);\n-\tif (key == NULL)\n-\t\treturn -1;\n+\tunsigned i, j;\n+\tunsigned bucket_idx, incr, success = 1;\n+\tuint8_t k = 0;\n+\tint32_t ret;\n+\tconst uint32_t bucket_bitmask = NUM_BUCKETS - 1;\n \n-\tbucket_occupancies = rte_calloc(\"bucket occupancies\",\n-\t\t\t\t\tnum_buckets, sizeof(uint32_t), 16);\n-\tif (bucket_occupancies == NULL) {\n-\t\trte_free(key);\n-\t\treturn -1;\n-\t}\n+\t/* Reset all arrays */\n+\tfor (i = 0; i < MAX_ENTRIES; i++)\n+\t\tslot_taken[i] = 0;\n \n-\tticks = 0;\n-\t*invalid_pos_count = 0;\n+\tfor (i = 0; i < NUM_BUCKETS; i++)\n+\t\tbuckets[i] = 0;\n \n-\tfor (i = 0; i < params->num_iterations; i++) {\n-\t\t/* Prepare inputs for the current iteration */\n-\t\tfor (j = 0; j < params->key_len; j++)\n-\t\t\tkey[j] = (uint8_t) rte_rand();\n+\tfor (j = 0; j < hashtest_key_lens[table_index]; j++)\n+\t\tkeys[0][j] = 0;\n \n-\t\t/* Perform operation, and measure time it takes */\n-\t\tbegin = rte_rdtsc();\n-\t\tpos = func(h, key);\n-\t\tend = rte_rdtsc();\n-\t\tticks += end - begin;\n+\t/*\n+\t * Add only entries that are not duplicated and that fits in the table\n+\t * (cannot store more than BUCKET_SIZE entries in a bucket).\n+\t * Regardless a key has been added correctly or not (success),\n+\t * the next one to try will be increased by 1.\n+\t */\n+\tfor (i = 0; i < KEYS_TO_ADD;) {\n+\t\tincr = 0;\n+\t\tif (i != 0) {\n+\t\t\tkeys[i][0] = ++k;\n+\t\t\t/* Overflow, need to increment the next byte */\n+\t\t\tif (keys[i][0] == 0)\n+\t\t\t\tincr = 1;\n+\t\t\tfor (j = 1; j < hashtest_key_lens[table_index]; j++) {\n+\t\t\t\t/* Do not increase next byte */\n+\t\t\t\tif (incr == 0)\n+\t\t\t\t\tif (success == 1)\n+\t\t\t\t\t\tkeys[i][j] = keys[i - 1][j];\n+\t\t\t\t\telse\n+\t\t\t\t\t\tkeys[i][j] = keys[i][j];\n+\t\t\t\t/* Increase next byte by one */\n+\t\t\t\telse {\n+\t\t\t\t\tif (success == 1)\n+\t\t\t\t\t\tkeys[i][j] = keys[i-1][j] + 1;\n+\t\t\t\t\telse\n+\t\t\t\t\t\tkeys[i][j] = keys[i][j] + 1;\n+\t\t\t\t\tif (keys[i][j] == 0)\n+\t\t\t\t\t\tincr = 1;\n+\t\t\t\t\telse\n+\t\t\t\t\t\tincr = 0;\n+\t\t\t\t}\n+\t\t\t}\n+\t\t}\n+\t\tsuccess = 0;\n+\t\tsignatures[i] = rte_hash_hash(h[table_index], keys[i]);\n+\t\tbucket_idx = signatures[i] & bucket_bitmask;\n+\t\t/* If bucket is full, do not try to insert the key */\n+\t\tif (buckets[bucket_idx] == BUCKET_SIZE)\n+\t\t\tcontinue;\n+\t\t/* If key can be added, leave in successful key arrays \"keys\" */\n+\t\tret = rte_hash_add_key_with_hash(h[table_index], keys[i],\n+\t\t\t\t\t\tsignatures[i]);\n+\t\tif (ret >= 0) {\n+\t\t\t/* If key is already added, ignore the entry and do not store */\n+\t\t\tif (slot_taken[ret])\n+\t\t\t\tcontinue;\n+\t\t\telse {\n+\t\t\t\t/* Store the returned position and mark slot as taken */\n+\t\t\t\tslot_taken[ret] = 1;\n+\t\t\t\tbuckets[bucket_idx]++;\n+\t\t\t\tsuccess = 1;\n+\t\t\t\ti++;\n+\t\t\t}\n+\t\t}\n+\t}\n+\n+\t/* Reset the table, so we can measure the time to add all the entries */\n+\trte_hash_free(h[table_index]);\n+\th[table_index] = rte_hash_create(&ut_params);\n \n-\t\t/* Other work per iteration */\n-\t\tif (pos < 0)\n-\t\t\t*invalid_pos_count += 1;\n+\treturn 0;\n+}\n+\n+static int\n+timed_adds(unsigned with_hash, unsigned table_index)\n+{\n+\tunsigned i;\n+\tconst uint64_t start_tsc = rte_rdtsc();\n+\tint32_t ret;\n+\n+\tfor (i = 0; i < KEYS_TO_ADD; i++) {\n+\t\tif (with_hash)\n+\t\t\tret = rte_hash_add_key_with_hash(h[table_index],\n+\t\t\t\t\t\t(const void *) keys[i],\n+\t\t\t\t\t\tsignatures[i]);\n \t\telse\n-\t\t\tbucket_occupancies[pos / params->bucket_entries]++;\n+\t\t\tret = rte_hash_add_key(h[table_index], keys[i]);\n+\n+\t\tif (ret >= 0)\n+\t\t\tpositions[i] = ret;\n+\t\telse {\n+\t\t\tprintf(\"Failed to add key number %u\\n\", ret);\n+\t\t\treturn -1;\n+\t\t}\n \t}\n-\t*avg_occupancy = get_avg(bucket_occupancies, num_buckets);\n \n-\trte_free(bucket_occupancies);\n-\trte_free(key);\n+\tconst uint64_t end_tsc = rte_rdtsc();\n+\tconst uint64_t time_taken = end_tsc - start_tsc;\n \n-\treturn (double)ticks / params->num_iterations;\n+\tcycles[table_index][ADD][with_hash] = time_taken/KEYS_TO_ADD;\n+\t/* Print a dot to show progress on operations */\n+\tprintf(\".\");\n+\tfflush(stdout);\n+\treturn 0;\n }\n \n-/*\n- * To help print out what tests are being done.\n- */\n-static const char *\n-get_tbl_perf_test_desc(enum hash_test_t type)\n+static int\n+timed_lookups(unsigned with_hash, unsigned table_index)\n {\n-\tswitch (type){\n-\tcase ADD_ON_EMPTY: return \"Add on Empty\";\n-\tcase DELETE_ON_EMPTY: return \"Delete on Empty\";\n-\tcase LOOKUP_ON_EMPTY: return \"Lookup on Empty\";\n-\tcase ADD_UPDATE: return \"Add Update\";\n-\tcase DELETE: return \"Delete\";\n-\tcase LOOKUP: return \"Lookup\";\n-\tdefault: return \"UNKNOWN\";\n+\tunsigned i, j;\n+\tconst uint64_t start_tsc = rte_rdtsc();\n+\tint32_t ret;\n+\n+\tfor (i = 0; i < NUM_LOOKUPS/KEYS_TO_ADD; i++) {\n+\t\tfor (j = 0; j < KEYS_TO_ADD; j++) {\n+\t\t\tif (with_hash)\n+\t\t\t\tret = rte_hash_lookup_with_hash(h[table_index],\n+\t\t\t\t\t\t\t(const void *) keys[j],\n+\t\t\t\t\t\t\tsignatures[j]);\n+\t\t\telse\n+\t\t\t\tret = rte_hash_lookup(h[table_index], keys[j]);\n+\t\t\tif (ret < 0 || ret != positions[j]) {\n+\t\t\t\tprintf(\"Key looked up in %d, should be in %d\\n\",\n+\t\t\t\t\tret, positions[j]);\n+\t\t\t\treturn -1;\n+\t\t\t}\n+\t\t}\n \t}\n+\n+\tconst uint64_t end_tsc = rte_rdtsc();\n+\tconst uint64_t time_taken = end_tsc - start_tsc;\n+\n+\tcycles[table_index][LOOKUP][with_hash] = time_taken/NUM_LOOKUPS;\n+\t/* Print a dot to show progress on operations */\n+\tprintf(\".\");\n+\tfflush(stdout);\n+\n+\treturn 0;\n }\n \n-/*\n- * Run a hash table performance test based on params.\n- */\n static int\n-run_tbl_perf_test(struct tbl_perf_test_params *params)\n+timed_lookups_multi(unsigned table_index)\n {\n-\tstatic unsigned calledCount = 5;\n-\tstruct rte_hash_parameters hash_params = {\n-\t\t.entries = params->entries,\n-\t\t.bucket_entries = params->bucket_entries,\n-\t\t.key_len = params->key_len,\n-\t\t.hash_func = params->hash_func,\n-\t\t.hash_func_init_val = params->hash_func_init_val,\n-\t\t.socket_id = rte_socket_id(),\n-\t};\n-\tstruct rte_hash *handle;\n-\tdouble avg_occupancy = 0, ticks = 0;\n-\tuint32_t num_iterations, invalid_pos;\n-\tchar name[RTE_HASH_NAMESIZE];\n-\tchar hashname[RTE_HASH_NAMESIZE];\n-\n-\tsnprintf(name, 32, \"test%u\", calledCount++);\n-\thash_params.name = name;\n-\n-\thandle = rte_hash_create(&hash_params);\n-\tRETURN_IF_ERROR(handle == NULL, \"hash creation failed\");\n-\n-\tswitch (params->test_type){\n-\tcase ADD_ON_EMPTY:\n-\t\tticks = run_single_tbl_perf_test(handle, rte_hash_add_key,\n-\t\t\t\tparams, &avg_occupancy, &invalid_pos);\n-\t\tbreak;\n-\tcase DELETE_ON_EMPTY:\n-\t\tticks = run_single_tbl_perf_test(handle, rte_hash_del_key,\n-\t\t\t\tparams, &avg_occupancy, &invalid_pos);\n-\t\tbreak;\n-\tcase LOOKUP_ON_EMPTY:\n-\t\tticks = run_single_tbl_perf_test(handle, rte_hash_lookup,\n-\t\t\t\tparams, &avg_occupancy, &invalid_pos);\n-\t\tbreak;\n-\tcase ADD_UPDATE:\n-\t\tnum_iterations = params->num_iterations;\n-\t\tparams->num_iterations = params->entries;\n-\t\trun_single_tbl_perf_test(handle, rte_hash_add_key, params,\n-\t\t\t\t&avg_occupancy, &invalid_pos);\n-\t\tparams->num_iterations = num_iterations;\n-\t\tticks = run_single_tbl_perf_test(handle, rte_hash_add_key,\n-\t\t\t\tparams, &avg_occupancy, &invalid_pos);\n-\t\tbreak;\n-\tcase DELETE:\n-\t\tnum_iterations = params->num_iterations;\n-\t\tparams->num_iterations = params->entries;\n-\t\trun_single_tbl_perf_test(handle, rte_hash_add_key, params,\n-\t\t\t\t&avg_occupancy, &invalid_pos);\n-\n-\t\tparams->num_iterations = num_iterations;\n-\t\tticks = run_single_tbl_perf_test(handle, rte_hash_del_key,\n-\t\t\t\tparams, &avg_occupancy, &invalid_pos);\n-\t\tbreak;\n-\tcase LOOKUP:\n-\t\tnum_iterations = params->num_iterations;\n-\t\tparams->num_iterations = params->entries;\n-\t\trun_single_tbl_perf_test(handle, rte_hash_add_key, params,\n-\t\t\t\t&avg_occupancy, &invalid_pos);\n-\n-\t\tparams->num_iterations = num_iterations;\n-\t\tticks = run_single_tbl_perf_test(handle, rte_hash_lookup,\n-\t\t\t\tparams, &avg_occupancy, &invalid_pos);\n-\t\tbreak;\n-\tdefault: return -1;\n+\tunsigned i, j, k;\n+\tint32_t positions_burst[BURST_SIZE];\n+\tconst void *keys_burst[BURST_SIZE];\n+\tconst uint64_t start_tsc = rte_rdtsc();\n+\n+\tfor (i = 0; i < NUM_LOOKUPS/KEYS_TO_ADD; i++) {\n+\t\tfor (j = 0; j < KEYS_TO_ADD/BURST_SIZE; j++) {\n+\t\t\tfor (k = 0; k < BURST_SIZE; k++)\n+\t\t\t\tkeys_burst[k] = keys[j * BURST_SIZE + k];\n+\n+\t\t\trte_hash_lookup_bulk(h[table_index],\n+\t\t\t\t\t\t(const void **) keys_burst,\n+\t\t\t\t\t\tBURST_SIZE,\n+\t\t\t\t\t\tpositions_burst);\n+\t\t\tfor (k = 0; k < BURST_SIZE; k++) {\n+\t\t\t\tif (positions_burst[k] != positions[j * BURST_SIZE + k]) {\n+\t\t\t\t\tprintf(\"Key looked up in %d, should be in %d\\n\",\n+\t\t\t\t\t\tpositions_burst[k],\n+\t\t\t\t\t\tpositions[j * BURST_SIZE + k]);\n+\t\t\t\t\treturn -1;\n+\t\t\t\t}\n+\t\t\t}\n+\t\t}\n \t}\n \n-\tsnprintf(hashname, RTE_HASH_NAMESIZE, \"%s\", get_hash_name(params->hash_func));\n-\n-\tprintf(\"%-12s, %-15s, %-16u, %-7u, %-18u, %-8u, %-19.2f, %.2f\\n\",\n-\t\thashname,\n-\t\tget_tbl_perf_test_desc(params->test_type),\n-\t\t(unsigned) params->key_len,\n-\t\t(unsigned) params->entries,\n-\t\t(unsigned) params->bucket_entries,\n-\t\t(unsigned) invalid_pos,\n-\t\tavg_occupancy,\n-\t\tticks\n-\t);\n-\n-\t/* Free */\n-\trte_hash_free(handle);\n+\tconst uint64_t end_tsc = rte_rdtsc();\n+\tconst uint64_t time_taken = end_tsc - start_tsc;\n+\n+\tcycles[table_index][LOOKUP_MULTI][0] = time_taken/NUM_LOOKUPS;\n+\t/* Print a dot to show progress on operations */\n+\tprintf(\".\");\n+\tfflush(stdout);\n+\n \treturn 0;\n }\n \n-/*\n- * Run all hash table performance tests.\n- */\n-static int run_all_tbl_perf_tests(void)\n+static int\n+timed_deletes(unsigned with_hash, unsigned table_index)\n {\n \tunsigned i;\n+\tconst uint64_t start_tsc = rte_rdtsc();\n+\tint32_t ret;\n+\n+\tfor (i = 0; i < KEYS_TO_ADD; i++) {\n+\t\tif (with_hash)\n+\t\t\tret = rte_hash_del_key_with_hash(h[table_index],\n+\t\t\t\t\t\t\t(const void *) keys[i],\n+\t\t\t\t\t\t\tsignatures[i]);\n+\t\telse\n+\t\t\tret = rte_hash_del_key(h[table_index],\n+\t\t\t\t\t\t\t(const void *) keys[i]);\n+\t\tif (ret >= 0)\n+\t\t\tpositions[i] = ret;\n+\t\telse {\n+\t\t\tprintf(\"Failed to add key number %u\\n\", ret);\n+\t\t\treturn -1;\n+\t\t}\n+\t}\n \n-\tprintf(\" *** Hash table performance test results ***\\n\");\n-\tprintf(\"Hash Func. , Operation , Key size (bytes), Entries, \"\n-\t \"Entries per bucket, Errors , Avg. bucket entries, Ticks/Op.\\n\");\n+\tconst uint64_t end_tsc = rte_rdtsc();\n+\tconst uint64_t time_taken = end_tsc - start_tsc;\n \n-\t/* Loop through every combination of test parameters */\n-\tfor (i = 0;\n-\t i < sizeof(tbl_perf_params) / sizeof(struct tbl_perf_test_params);\n-\t i++) {\n+\tcycles[table_index][DELETE][with_hash] = time_taken/KEYS_TO_ADD;\n+\t/* Print a dot to show progress on operations */\n+\tprintf(\".\");\n+\tfflush(stdout);\n \n-\t\t/* Perform test */\n-\t\tif (run_tbl_perf_test(&tbl_perf_params[i]) < 0)\n+\treturn 0;\n+}\n+\n+static void\n+free_table(unsigned table_index)\n+{\n+\trte_hash_free(h[table_index]);\n+}\n+\n+static int\n+reset_table(unsigned table_index)\n+{\n+\tfree_table(table_index);\n+\tif (create_table(table_index) != 0)\n+\t\treturn -1;\n+\n+\treturn 0;\n+}\n+\n+static int\n+run_all_tbl_perf_tests(void)\n+{\n+\tunsigned i, j;\n+\n+\tprintf(\"Measuring performance, please wait\");\n+\tfflush(stdout);\n+\tfor (i = 0; i < NUM_KEYSIZES; i++) {\n+\t\tif (create_table(i) < 0)\n \t\t\treturn -1;\n+\n+\t\tif (get_input_keys(i) < 0)\n+\t\t\treturn -1;\n+\n+\t\tif (timed_adds(0, i) < 0)\n+\t\t\treturn -1;\n+\n+\t\tfor (j = 0; j < NUM_SHUFFLES; j++)\n+\t\t\tshuffle_input_keys(i);\n+\n+\t\tif (timed_lookups(0, i) < 0)\n+\t\t\treturn -1;\n+\n+\t\tif (timed_lookups_multi(i) < 0)\n+\t\t\treturn -1;\n+\n+\t\tif (timed_deletes(0, i) < 0)\n+\t\t\treturn -1;\n+\n+\t\tif (reset_table(i) < 0)\n+\t\t\treturn -1;\n+\n+\t\tif (timed_adds(1, i) < 0)\n+\t\t\treturn -1;\n+\n+\t\tfor (j = 0; j < NUM_SHUFFLES; j++)\n+\t\t\tshuffle_input_keys(i);\n+\n+\t\tif (timed_lookups(1, i) < 0)\n+\t\t\treturn -1;\n+\n+\t\tif (timed_deletes(1, i) < 0)\n+\t\t\treturn -1;\n+\n+\t\tfree_table(i);\n+\t}\n+\tprintf(\"\\nResults (in CPU cycles/operation)\\n\");\n+\tprintf(\"---------------------------------\\n\");\n+\tprintf(\"\\nWithout pre-computed hash values\\n\");\n+\tprintf(\"\\n%-18s%-18s%-18s%-18s%-18s\\n\",\n+\t\t\t\"Keysize\", \"Add\", \"Lookup\", \"Lookup_bulk\", \"Delete\");\n+\tfor (i = 0; i < NUM_KEYSIZES; i++) {\n+\t\tprintf(\"%-18d\", hashtest_key_lens[i]);\n+\t\tfor (j = 0; j < NUM_OPERATIONS; j++)\n+\t\t\tprintf(\"%-18\"PRIu64, cycles[i][j][0]);\n+\t\tprintf(\"\\n\");\n+\t}\n+\tprintf(\"\\nWith pre-computed hash values\\n\");\n+\tprintf(\"\\n%-18s%-18s%-18s%-18s%-18s\\n\",\n+\t\t\t\"Keysize\", \"Add\", \"Lookup\", \"Lookup_bulk\", \"Delete\");\n+\tfor (i = 0; i < NUM_KEYSIZES; i++) {\n+\t\tprintf(\"%-18d\", hashtest_key_lens[i]);\n+\t\tfor (j = 0; j < NUM_OPERATIONS; j++)\n+\t\t\tprintf(\"%-18\"PRIu64, cycles[i][j][1]);\n+\t\tprintf(\"\\n\");\n \t}\n+\n \treturn 0;\n }\n \n@@ -624,28 +490,34 @@ fbk_hash_perf_test(void)\n \tuint64_t lookup_time = 0;\n \tunsigned added = 0;\n \tunsigned value = 0;\n+\tuint32_t key;\n+\tuint16_t val;\n \tunsigned i, j;\n \n \thandle = rte_fbk_hash_create(¶ms);\n-\tRETURN_IF_ERROR_FBK(handle == NULL, \"fbk hash creation failed\");\n+\tif (handle == NULL) {\n+\t\tprintf(\"Error creating table\\n\");\n+\t\treturn -1;\n+\t}\n \n \tkeys = rte_zmalloc(NULL, ENTRIES * sizeof(*keys), 0);\n-\tRETURN_IF_ERROR_FBK(keys == NULL,\n-\t\t\"fbk hash: memory allocation for key store failed\");\n+\tif (keys == NULL) {\n+\t\tprintf(\"fbk hash: memory allocation for key store failed\\n\");\n+\t\treturn -1;\n+\t}\n \n \t/* Generate random keys and values. */\n \tfor (i = 0; i < ENTRIES; i++) {\n-\t\tuint32_t key = (uint32_t)rte_rand();\n+\t\tkey = (uint32_t)rte_rand();\n \t\tkey = ((uint64_t)key << 32) | (uint64_t)rte_rand();\n-\t\tuint16_t val = (uint16_t)rte_rand();\n+\t\tval = (uint16_t)rte_rand();\n \n \t\tif (rte_fbk_hash_add_key(handle, key, val) == 0) {\n \t\t\tkeys[added] = key;\n \t\t\tadded++;\n \t\t}\n-\t\tif (added > (LOAD_FACTOR * ENTRIES)) {\n+\t\tif (added > (LOAD_FACTOR * ENTRIES))\n \t\t\tbreak;\n-\t\t}\n \t}\n \n \tfor (i = 0; i < TEST_ITERATIONS; i++) {\n@@ -653,15 +525,14 @@ fbk_hash_perf_test(void)\n \t\tuint64_t end;\n \n \t\t/* Generate random indexes into keys[] array. */\n-\t\tfor (j = 0; j < TEST_SIZE; j++) {\n+\t\tfor (j = 0; j < TEST_SIZE; j++)\n \t\t\tindexes[j] = rte_rand() % added;\n-\t\t}\n \n \t\tbegin = rte_rdtsc();\n \t\t/* Do lookups */\n-\t\tfor (j = 0; j < TEST_SIZE; j++) {\n+\t\tfor (j = 0; j < TEST_SIZE; j++)\n \t\t\tvalue += rte_fbk_hash_lookup(handle, keys[indexes[j]]);\n-\t\t}\n+\n \t\tend = rte_rdtsc();\n \t\tlookup_time += (double)(end - begin);\n \t}\n@@ -681,9 +552,6 @@ fbk_hash_perf_test(void)\n \treturn 0;\n }\n \n-/*\n- * Do all unit and performance tests.\n- */\n static int\n test_hash_perf(void)\n {\n@@ -692,11 +560,12 @@ test_hash_perf(void)\n \n \tif (fbk_hash_perf_test() < 0)\n \t\treturn -1;\n+\n \treturn 0;\n }\n \n static struct test_command hash_perf_cmd = {\n-\t.command = \"hash_perf_autotest\",\n-\t.callback = test_hash_perf,\n+\t\t.command = \"hash_perf_autotest\",\n+\t\t.callback = test_hash_perf,\n };\n REGISTER_TEST_COMMAND(hash_perf_cmd);\n", "prefixes": [ "dpdk-dev", "v3" ] }