@@ -82,7 +82,7 @@ SRCS-y += test_memcpy.c
SRCS-y += test_memcpy_perf.c
SRCS-$(CONFIG_RTE_LIBRTE_HASH) += test_hash.c
-SRCS-$(CONFIG_RTE_LIBRTE_HASH) += test_hash_perf_new.c
+SRCS-$(CONFIG_RTE_LIBRTE_HASH) += test_hash_perf.c
SRCS-$(CONFIG_RTE_LIBRTE_HASH) += test_hash_functions.c
SRCS-$(CONFIG_RTE_LIBRTE_HASH) += test_hash_scaling.c
new file mode 100644
@@ -0,0 +1,560 @@
+/*-
+ * BSD LICENSE
+ *
+ * Copyright(c) 2010-2015 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 <stdio.h>
+#include <inttypes.h>
+
+#include <rte_lcore.h>
+#include <rte_cycles.h>
+#include <rte_malloc.h>
+#include <rte_hash.h>
+#include <rte_hash_crc.h>
+#include <rte_jhash.h>
+#include <rte_fbk_hash.h>
+#include <rte_random.h>
+#include <rte_string_fns.h>
+
+#include "test.h"
+
+#define KEYS_TO_ADD (1 << 18)
+#define MAX_ENTRIES (KEYS_TO_ADD * 4) /* 25% table utilization */
+#define NUM_LOOKUPS (KEYS_TO_ADD * 10) /* Loop among keys added, several times */
+#define BUCKET_SIZE 4
+#define NUM_BUCKETS (MAX_ENTRIES / BUCKET_SIZE)
+#define MAX_KEYSIZE 64
+#define NUM_KEYSIZES 10
+#define NUM_SHUFFLES 10
+#define BURST_SIZE 16
+
+enum operations {
+ ADD = 0,
+ LOOKUP,
+ LOOKUP_MULTI,
+ DELETE,
+ NUM_OPERATIONS
+};
+
+static uint32_t hashtest_key_lens[] = {
+ 4, 8, 16, 32, 48, 64, /* standard key sizes */
+ 9, /* IPv4 SRC + DST + protocol, unpadded */
+ 13, /* IPv4 5-tuple, unpadded */
+ 37, /* IPv6 5-tuple, unpadded */
+ 40 /* IPv6 5-tuple, padded to 8-byte boundary */
+};
+struct rte_hash *h[NUM_KEYSIZES];
+/* Array that stores if a slot is full */
+uint8_t slot_taken[MAX_ENTRIES];
+/* Array to store number of cycles per operation */
+uint64_t cycles[NUM_KEYSIZES][NUM_OPERATIONS][2];
+/* Array to store all input keys */
+uint8_t keys[KEYS_TO_ADD][MAX_KEYSIZE];
+/* Array to store the precomputed hash for 'keys' */
+hash_sig_t signatures[KEYS_TO_ADD];
+/* Array to store how many busy entries have each bucket */
+uint8_t buckets[NUM_BUCKETS];
+
+/* Parameters used for hash table in unit test functions. */
+static struct rte_hash_parameters ut_params = {
+ .entries = MAX_ENTRIES,
+ .bucket_entries = BUCKET_SIZE,
+ .hash_func = rte_jhash,
+ .hash_func_init_val = 0,
+};
+
+static int
+create_table(unsigned table_index)
+{
+ char name[RTE_HASH_NAMESIZE];
+
+ sprintf(name, "test_hash%d", hashtest_key_lens[table_index]);
+ ut_params.name = name;
+ ut_params.key_len = hashtest_key_lens[table_index];
+ ut_params.socket_id = rte_socket_id();
+ h[table_index] = rte_hash_find_existing(name);
+ if (h[table_index] != NULL)
+ /*
+ * If table was already created, free it to create it again,
+ * so we force it is empty
+ */
+ rte_hash_free(h[table_index]);
+ h[table_index] = rte_hash_create(&ut_params);
+ if (h[table_index] == NULL) {
+ printf("Error creating table\n");
+ return -1;
+ }
+ return 0;
+
+}
+
+/* Shuffle the keys that have been added, so lookups will be totally random */
+static void
+shuffle_input_keys(unsigned table_index)
+{
+ unsigned i;
+ uint32_t swap_idx;
+ uint8_t temp_key[RTE_HASH_KEY_LENGTH_MAX];
+ hash_sig_t temp_signature;
+
+ for (i = 0; i < KEYS_TO_ADD; i++) {
+ do
+ swap_idx = rte_rand() % KEYS_TO_ADD;
+ while (swap_idx == i);
+
+ memcpy(temp_key, keys[i], hashtest_key_lens[table_index]);
+ temp_signature = signatures[i];
+
+ memcpy(keys[i], keys[swap_idx], hashtest_key_lens[table_index]);
+ signatures[i] = signatures[swap_idx];
+
+ memcpy(keys[swap_idx], temp_key, hashtest_key_lens[table_index]);
+ signatures[swap_idx] = temp_signature;
+ }
+}
+
+/*
+ * Creates the table and looks for random keys which
+ * ALL can fit in hash table (no errors)
+ */
+static int
+get_input_keys(unsigned table_index)
+{
+ unsigned i, j;
+ unsigned bucket_idx, incr, success = 1;
+ uint8_t k = 0;
+ int32_t ret;
+ const uint32_t bucket_bitmask = NUM_BUCKETS - 1;
+
+ /* Reset all arrays */
+ for (i = 0; i < MAX_ENTRIES; i++)
+ slot_taken[i] = 0;
+
+ for (i = 0; i < NUM_BUCKETS; i++)
+ buckets[i] = 0;
+
+ for (j = 0; j < hashtest_key_lens[table_index]; j++)
+ keys[0][j] = 0;
+
+ /*
+ * Add only entries that are not duplicated and that fits in the table
+ * (cannot store more than BUCKET_SIZE entries in a bucket).
+ * Regardless a key has been added correctly or not (success),
+ * the next one to try will be increased by 1.
+ */
+ for (i = 0; i < KEYS_TO_ADD;) {
+ incr = 0;
+ if (i != 0) {
+ keys[i][0] = ++k;
+ /* Overflow, need to increment the next byte */
+ if (keys[i][0] == 0)
+ incr = 1;
+ for (j = 1; j < hashtest_key_lens[table_index]; j++) {
+ /* Do not increase next byte */
+ if (incr == 0)
+ if (success == 1)
+ keys[i][j] = keys[i - 1][j];
+ else
+ keys[i][j] = keys[i][j];
+ /* Increase next byte by one */
+ else {
+ if (success == 1)
+ keys[i][j] = keys[i-1][j] + 1;
+ else
+ keys[i][j] = keys[i][j] + 1;
+ if (keys[i][j] == 0)
+ incr = 1;
+ else
+ incr = 0;
+ }
+ }
+ }
+ success = 0;
+ signatures[i] = rte_hash_hash(h[table_index], keys[i]);
+ bucket_idx = signatures[i] & bucket_bitmask;
+ /* If bucket is full, do not try to insert the key */
+ if (buckets[bucket_idx] == BUCKET_SIZE)
+ continue;
+ /* If key can be added, leave in successful key arrays "keys" */
+ ret = rte_hash_add_key_with_hash(h[table_index], keys[i],
+ signatures[i]);
+ if (ret >= 0) {
+ /* If key is already added, ignore the entry and do not store */
+ if (slot_taken[ret])
+ continue;
+ else {
+ /* Store the returned position and mark slot as taken */
+ slot_taken[ret] = 1;
+ buckets[bucket_idx]++;
+ success = 1;
+ i++;
+ }
+ }
+ }
+
+ /* Reset the table, so we can measure the time to add all the entries */
+ rte_hash_free(h[table_index]);
+ h[table_index] = rte_hash_create(&ut_params);
+
+ return 0;
+}
+
+static int
+timed_adds(unsigned with_hash, unsigned table_index) {
+ unsigned i;
+ const uint64_t start_tsc = rte_rdtsc();
+
+ for (i = 0; i < KEYS_TO_ADD; i++) {
+ if (with_hash)
+ rte_hash_add_key_with_hash(h[table_index],
+ (const void *) keys[i],
+ signatures[i]);
+ else
+ rte_hash_add_key(h[table_index], keys[i]);
+ }
+
+ const uint64_t end_tsc = rte_rdtsc();
+ const uint64_t time_taken = end_tsc - start_tsc;
+ const float seconds_taken = (float)time_taken/rte_get_tsc_hz();
+
+ cycles[table_index][ADD][with_hash] = time_taken/KEYS_TO_ADD;
+
+ printf("\n%"PRIu64" adds in %f seconds\n", (uint64_t)KEYS_TO_ADD,
+ seconds_taken);
+ printf("Average %"PRIu64" tsc ticks per add\n",
+ cycles[table_index][ADD][with_hash]);
+ printf("Average %"PRIu64" adds per second\n",
+ (KEYS_TO_ADD * rte_get_tsc_hz())/time_taken);
+ return 0;
+}
+
+static int
+timed_lookups(unsigned with_hash, unsigned table_index)
+{
+ unsigned i, j;
+ 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++) {
+ if (with_hash)
+ rte_hash_lookup_with_hash(h[table_index],
+ (const void *) keys[j],
+ signatures[j]);
+ else
+ rte_hash_lookup(h[table_index], keys[j]);
+ }
+ }
+
+ const uint64_t end_tsc = rte_rdtsc();
+ const uint64_t time_taken = end_tsc - start_tsc;
+ const float seconds_taken = (float)time_taken/rte_get_tsc_hz();
+
+ cycles[table_index][LOOKUP][with_hash] = time_taken/NUM_LOOKUPS;
+
+ printf("%"PRIu64" lookups in %f seconds\n", (uint64_t) NUM_LOOKUPS,
+ seconds_taken);
+ printf("Average %"PRIu64" tsc ticks per lookup\n",
+ cycles[table_index][LOOKUP][with_hash]);
+ printf("Average %"PRIu64" lookups per second\n",
+ (NUM_LOOKUPS * rte_get_tsc_hz())/time_taken);
+ return 0;
+}
+
+static int
+timed_lookups_multi(unsigned table_index)
+{
+ unsigned i, j, k;
+ int32_t positions_burst[BURST_SIZE];
+ const void *keys_burst[BURST_SIZE];
+ 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];
+ rte_hash_lookup_bulk(h[table_index],
+ (const void **) keys_burst,
+ BURST_SIZE,
+ positions_burst);
+ }
+ }
+
+ const uint64_t end_tsc = rte_rdtsc();
+ const uint64_t time_taken = end_tsc - start_tsc;
+ const float seconds_taken = (float)time_taken/rte_get_tsc_hz();
+
+ cycles[table_index][LOOKUP_MULTI][0] = time_taken/NUM_LOOKUPS;
+
+ printf("%"PRIu64" lookups in %f seconds\n", (uint64_t)NUM_LOOKUPS,
+ seconds_taken);
+ printf("Average %"PRIu64" tsc ticks per lookup\n",
+ cycles[table_index][LOOKUP_MULTI][0]);
+ printf("Average %"PRIu64" lookups per second\n",
+ (NUM_LOOKUPS * rte_get_tsc_hz())/time_taken);
+ return 0;
+}
+
+static int
+timed_deletes(unsigned with_hash, unsigned table_index)
+{
+ unsigned i;
+ const uint64_t start_tsc = rte_rdtsc();
+
+ for (i = 0; i < KEYS_TO_ADD; i++) {
+ if (with_hash)
+ rte_hash_del_key_with_hash(h[table_index],
+ (const void *) keys[i],
+ signatures[i]);
+ else
+ rte_hash_del_key(h[table_index],
+ (const void *) keys[i]);
+ }
+
+ const uint64_t end_tsc = rte_rdtsc();
+ const uint64_t time_taken = end_tsc - start_tsc;
+ const float seconds_taken = (float)time_taken/rte_get_tsc_hz();
+
+ cycles[table_index][DELETE][with_hash] = time_taken/KEYS_TO_ADD;
+
+ printf("\n%"PRIu64" deletions in %f seconds\n", (uint64_t) KEYS_TO_ADD,
+ seconds_taken);
+ printf("Average %"PRIu64" tsc ticks per deletion\n",
+ cycles[table_index][DELETE][with_hash]);
+ printf("Average %"PRIu64" deletions per second\n",
+ (KEYS_TO_ADD * rte_get_tsc_hz())/time_taken);
+ return 0;
+}
+
+static void
+free_table(unsigned table_index)
+{
+ rte_hash_free(h[table_index]);
+}
+
+static int
+reset_table(unsigned table_index)
+{
+ free_table(table_index);
+ if (create_table(table_index) != 0)
+ return -1;
+
+ return 0;
+}
+
+static int
+run_all_tbl_perf_tests(void)
+{
+ unsigned i, j;
+
+ for (i = 0; i < NUM_KEYSIZES; i++) {
+ if (create_table(i) < 0)
+ return -1;
+
+ if (get_input_keys(i) < 0)
+ return -1;
+
+ printf("\n------ KEY SIZE = %u ----------\n\n",
+ hashtest_key_lens[i]);
+ printf("\n ----- WITH PRECOMPUTED HASH VALUES -----\n\n");
+
+ printf("\nTimed additions\n");
+ printf("------------------\n");
+ if (timed_adds(1, i) < 0)
+ return -1;
+
+ for (j = 0; j < NUM_SHUFFLES; j++)
+ shuffle_input_keys(i);
+
+ printf("\nTimed lookups\n");
+ printf("------------------\n");
+ if (timed_lookups(1, i) < 0)
+ return -1;
+
+ printf("\nTimed deletions\n");
+ printf("------------------\n");
+ if (timed_deletes(1, i) < 0)
+ return -1;
+
+ if (reset_table(i) < 0)
+ return -1;
+
+ printf("\n ----- WITH JUST KEYS -----\n\n");
+
+ printf("\nTimed additions\n");
+ printf("------------------\n");
+ if (timed_adds(0, i) < 0)
+ return -1;
+
+ for (j = 0; j < NUM_SHUFFLES; j++)
+ shuffle_input_keys(i);
+
+ printf("\nTimed lookups\n");
+ printf("------------------\n");
+ if (timed_lookups(0, i) < 0)
+ return -1;
+
+ printf("\nTimed lookups multi\n");
+ printf("------------------\n");
+ if (timed_lookups_multi(i) < 0)
+ return -1;
+
+ printf("\nTimed deletions\n");
+ printf("------------------\n");
+ if (timed_deletes(0, i) < 0)
+ return -1;
+
+ free_table(i);
+
+ }
+ printf("\nResults (in CPU cycles/operation)\n");
+ printf("-----------------------------------\n");
+ printf("\nWith precomputed hash\n");
+ printf("\n%-18s%-18s%-18s%-18s%-18s\n",
+ "Keysize", "Add", "Lookup", "Lookup_bulk", "Delete");
+ for (i = 0; i < NUM_KEYSIZES; i++) {
+ printf("%-18d", hashtest_key_lens[i]);
+ for (j = 0; j < NUM_OPERATIONS; j++)
+ printf("%-18"PRIu64, cycles[i][j][1]);
+ printf("\n");
+ }
+ printf("\nWith just keys\n");
+ printf("\n%-18s%-18s%-18s%-18s%-18s\n",
+ "Keysize", "Add", "Lookup", "Lookup_bulk", "Delete");
+ for (i = 0; i < NUM_KEYSIZES; i++) {
+ printf("%-18d", hashtest_key_lens[i]);
+ for (j = 0; j < NUM_OPERATIONS; j++)
+ printf("%-18"PRIu64, cycles[i][j][0]);
+ printf("\n");
+ }
+
+ return 0;
+}
+
+/* Control operation of performance testing of fbk hash. */
+#define LOAD_FACTOR 0.667 /* How full to make the hash table. */
+#define TEST_SIZE 1000000 /* How many operations to time. */
+#define TEST_ITERATIONS 30 /* How many measurements to take. */
+#define ENTRIES (1 << 15) /* How many entries. */
+
+static int
+fbk_hash_perf_test(void)
+{
+ struct rte_fbk_hash_params params = {
+ .name = "fbk_hash_test",
+ .entries = ENTRIES,
+ .entries_per_bucket = 4,
+ .socket_id = rte_socket_id(),
+ };
+ struct rte_fbk_hash_table *handle = NULL;
+ uint32_t *keys = NULL;
+ unsigned indexes[TEST_SIZE];
+ uint64_t lookup_time = 0;
+ unsigned added = 0;
+ unsigned value = 0;
+ uint32_t key;
+ uint16_t val;
+ unsigned i, j;
+
+ handle = rte_fbk_hash_create(¶ms);
+ if (handle == NULL) {
+ printf("Error creating table\n");
+ return -1;
+ }
+
+ keys = rte_zmalloc(NULL, ENTRIES * sizeof(*keys), 0);
+ if (keys == NULL) {
+ printf("fbk hash: memory allocation for key store failed\n");
+ return -1;
+ }
+
+ /* Generate random keys and values. */
+ for (i = 0; i < ENTRIES; i++) {
+ key = (uint32_t)rte_rand();
+ key = ((uint64_t)key << 32) | (uint64_t)rte_rand();
+ val = (uint16_t)rte_rand();
+
+ if (rte_fbk_hash_add_key(handle, key, val) == 0) {
+ keys[added] = key;
+ added++;
+ }
+ if (added > (LOAD_FACTOR * ENTRIES))
+ break;
+ }
+
+ for (i = 0; i < TEST_ITERATIONS; i++) {
+ uint64_t begin;
+ uint64_t end;
+
+ /* Generate random indexes into keys[] array. */
+ for (j = 0; j < TEST_SIZE; j++)
+ indexes[j] = rte_rand() % added;
+
+ begin = rte_rdtsc();
+ /* Do lookups */
+ for (j = 0; j < TEST_SIZE; j++)
+ value += rte_fbk_hash_lookup(handle, keys[indexes[j]]);
+
+ end = rte_rdtsc();
+ lookup_time += (double)(end - begin);
+ }
+
+ printf("\n\n *** FBK Hash function performance test results ***\n");
+ /*
+ * The use of the 'value' variable ensures that the hash lookup is not
+ * being optimised out by the compiler.
+ */
+ if (value != 0)
+ printf("Number of ticks per lookup = %g\n",
+ (double)lookup_time /
+ ((double)TEST_ITERATIONS * (double)TEST_SIZE));
+
+ rte_fbk_hash_free(handle);
+
+ return 0;
+}
+
+static int
+test_hash_perf(void)
+{
+ if (run_all_tbl_perf_tests() < 0)
+ return -1;
+
+ if (fbk_hash_perf_test() < 0)
+ return -1;
+
+ return 0;
+}
+
+static struct test_command hash_perf_cmd = {
+ .command = "hash_perf_autotest",
+ .callback = test_hash_perf,
+};
+REGISTER_TEST_COMMAND(hash_perf_cmd);
deleted file mode 100644
@@ -1,560 +0,0 @@
-/*-
- * BSD LICENSE
- *
- * Copyright(c) 2010-2015 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 <stdio.h>
-#include <inttypes.h>
-
-#include <rte_lcore.h>
-#include <rte_cycles.h>
-#include <rte_malloc.h>
-#include <rte_hash.h>
-#include <rte_hash_crc.h>
-#include <rte_jhash.h>
-#include <rte_fbk_hash.h>
-#include <rte_random.h>
-#include <rte_string_fns.h>
-
-#include "test.h"
-
-#define KEYS_TO_ADD (1 << 18)
-#define MAX_ENTRIES (KEYS_TO_ADD * 4) /* 25% table utilization */
-#define NUM_LOOKUPS (KEYS_TO_ADD * 10) /* Loop among keys added, several times */
-#define BUCKET_SIZE 4
-#define NUM_BUCKETS (MAX_ENTRIES / BUCKET_SIZE)
-#define MAX_KEYSIZE 64
-#define NUM_KEYSIZES 10
-#define NUM_SHUFFLES 10
-#define BURST_SIZE 16
-
-enum operations {
- ADD = 0,
- LOOKUP,
- LOOKUP_MULTI,
- DELETE,
- NUM_OPERATIONS
-};
-
-static uint32_t hashtest_key_lens[] = {
- 4, 8, 16, 32, 48, 64, /* standard key sizes */
- 9, /* IPv4 SRC + DST + protocol, unpadded */
- 13, /* IPv4 5-tuple, unpadded */
- 37, /* IPv6 5-tuple, unpadded */
- 40 /* IPv6 5-tuple, padded to 8-byte boundary */
-};
-struct rte_hash *h[NUM_KEYSIZES];
-/* Array that stores if a slot is full */
-uint8_t slot_taken[MAX_ENTRIES];
-/* Array to store number of cycles per operation */
-uint64_t cycles[NUM_KEYSIZES][NUM_OPERATIONS][2];
-/* Array to store all input keys */
-uint8_t keys[KEYS_TO_ADD][MAX_KEYSIZE];
-/* Array to store the precomputed hash for 'keys' */
-hash_sig_t signatures[KEYS_TO_ADD];
-/* Array to store how many busy entries have each bucket */
-uint8_t buckets[NUM_BUCKETS];
-
-/* Parameters used for hash table in unit test functions. */
-static struct rte_hash_parameters ut_params = {
- .entries = MAX_ENTRIES,
- .bucket_entries = BUCKET_SIZE,
- .hash_func = rte_jhash,
- .hash_func_init_val = 0,
-};
-
-static int
-create_table(unsigned table_index)
-{
- char name[RTE_HASH_NAMESIZE];
-
- sprintf(name, "test_hash%d", hashtest_key_lens[table_index]);
- ut_params.name = name;
- ut_params.key_len = hashtest_key_lens[table_index];
- ut_params.socket_id = rte_socket_id();
- h[table_index] = rte_hash_find_existing(name);
- if (h[table_index] != NULL)
- /*
- * If table was already created, free it to create it again,
- * so we force it is empty
- */
- rte_hash_free(h[table_index]);
- h[table_index] = rte_hash_create(&ut_params);
- if (h[table_index] == NULL) {
- printf("Error creating table\n");
- return -1;
- }
- return 0;
-
-}
-
-/* Shuffle the keys that have been added, so lookups will be totally random */
-static void
-shuffle_input_keys(unsigned table_index)
-{
- unsigned i;
- uint32_t swap_idx;
- uint8_t temp_key[RTE_HASH_KEY_LENGTH_MAX];
- hash_sig_t temp_signature;
-
- for (i = 0; i < KEYS_TO_ADD; i++) {
- do
- swap_idx = rte_rand() % KEYS_TO_ADD;
- while (swap_idx == i);
-
- memcpy(temp_key, keys[i], hashtest_key_lens[table_index]);
- temp_signature = signatures[i];
-
- memcpy(keys[i], keys[swap_idx], hashtest_key_lens[table_index]);
- signatures[i] = signatures[swap_idx];
-
- memcpy(keys[swap_idx], temp_key, hashtest_key_lens[table_index]);
- signatures[swap_idx] = temp_signature;
- }
-}
-
-/*
- * Creates the table and looks for random keys which
- * ALL can fit in hash table (no errors)
- */
-static int
-get_input_keys(unsigned table_index)
-{
- unsigned i, j;
- unsigned bucket_idx, incr, success = 1;
- uint8_t k = 0;
- int32_t ret;
- const uint32_t bucket_bitmask = NUM_BUCKETS - 1;
-
- /* Reset all arrays */
- for (i = 0; i < MAX_ENTRIES; i++)
- slot_taken[i] = 0;
-
- for (i = 0; i < NUM_BUCKETS; i++)
- buckets[i] = 0;
-
- for (j = 0; j < hashtest_key_lens[table_index]; j++)
- keys[0][j] = 0;
-
- /*
- * Add only entries that are not duplicated and that fits in the table
- * (cannot store more than BUCKET_SIZE entries in a bucket).
- * Regardless a key has been added correctly or not (success),
- * the next one to try will be increased by 1.
- */
- for (i = 0; i < KEYS_TO_ADD;) {
- incr = 0;
- if (i != 0) {
- keys[i][0] = ++k;
- /* Overflow, need to increment the next byte */
- if (keys[i][0] == 0)
- incr = 1;
- for (j = 1; j < hashtest_key_lens[table_index]; j++) {
- /* Do not increase next byte */
- if (incr == 0)
- if (success == 1)
- keys[i][j] = keys[i - 1][j];
- else
- keys[i][j] = keys[i][j];
- /* Increase next byte by one */
- else {
- if (success == 1)
- keys[i][j] = keys[i-1][j] + 1;
- else
- keys[i][j] = keys[i][j] + 1;
- if (keys[i][j] == 0)
- incr = 1;
- else
- incr = 0;
- }
- }
- }
- success = 0;
- signatures[i] = rte_hash_hash(h[table_index], keys[i]);
- bucket_idx = signatures[i] & bucket_bitmask;
- /* If bucket is full, do not try to insert the key */
- if (buckets[bucket_idx] == BUCKET_SIZE)
- continue;
- /* If key can be added, leave in successful key arrays "keys" */
- ret = rte_hash_add_key_with_hash(h[table_index], keys[i],
- signatures[i]);
- if (ret >= 0) {
- /* If key is already added, ignore the entry and do not store */
- if (slot_taken[ret])
- continue;
- else {
- /* Store the returned position and mark slot as taken */
- slot_taken[ret] = 1;
- buckets[bucket_idx]++;
- success = 1;
- i++;
- }
- }
- }
-
- /* Reset the table, so we can measure the time to add all the entries */
- rte_hash_free(h[table_index]);
- h[table_index] = rte_hash_create(&ut_params);
-
- return 0;
-}
-
-static int
-timed_adds(unsigned with_hash, unsigned table_index) {
- unsigned i;
- const uint64_t start_tsc = rte_rdtsc();
-
- for (i = 0; i < KEYS_TO_ADD; i++) {
- if (with_hash)
- rte_hash_add_key_with_hash(h[table_index],
- (const void *) keys[i],
- signatures[i]);
- else
- rte_hash_add_key(h[table_index], keys[i]);
- }
-
- const uint64_t end_tsc = rte_rdtsc();
- const uint64_t time_taken = end_tsc - start_tsc;
- const float seconds_taken = (float)time_taken/rte_get_tsc_hz();
-
- cycles[table_index][ADD][with_hash] = time_taken/KEYS_TO_ADD;
-
- printf("\n%"PRIu64" adds in %f seconds\n", (uint64_t)KEYS_TO_ADD,
- seconds_taken);
- printf("Average %"PRIu64" tsc ticks per add\n",
- cycles[table_index][ADD][with_hash]);
- printf("Average %"PRIu64" adds per second\n",
- (KEYS_TO_ADD * rte_get_tsc_hz())/time_taken);
- return 0;
-}
-
-static int
-timed_lookups(unsigned with_hash, unsigned table_index)
-{
- unsigned i, j;
- 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++) {
- if (with_hash)
- rte_hash_lookup_with_hash(h[table_index],
- (const void *) keys[j],
- signatures[j]);
- else
- rte_hash_lookup(h[table_index], keys[j]);
- }
- }
-
- const uint64_t end_tsc = rte_rdtsc();
- const uint64_t time_taken = end_tsc - start_tsc;
- const float seconds_taken = (float)time_taken/rte_get_tsc_hz();
-
- cycles[table_index][LOOKUP][with_hash] = time_taken/NUM_LOOKUPS;
-
- printf("%"PRIu64" lookups in %f seconds\n", (uint64_t) NUM_LOOKUPS,
- seconds_taken);
- printf("Average %"PRIu64" tsc ticks per lookup\n",
- cycles[table_index][LOOKUP][with_hash]);
- printf("Average %"PRIu64" lookups per second\n",
- (NUM_LOOKUPS * rte_get_tsc_hz())/time_taken);
- return 0;
-}
-
-static int
-timed_lookups_multi(unsigned table_index)
-{
- unsigned i, j, k;
- int32_t positions_burst[BURST_SIZE];
- const void *keys_burst[BURST_SIZE];
- 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];
- rte_hash_lookup_bulk(h[table_index],
- (const void **) keys_burst,
- BURST_SIZE,
- positions_burst);
- }
- }
-
- const uint64_t end_tsc = rte_rdtsc();
- const uint64_t time_taken = end_tsc - start_tsc;
- const float seconds_taken = (float)time_taken/rte_get_tsc_hz();
-
- cycles[table_index][LOOKUP_MULTI][0] = time_taken/NUM_LOOKUPS;
-
- printf("%"PRIu64" lookups in %f seconds\n", (uint64_t)NUM_LOOKUPS,
- seconds_taken);
- printf("Average %"PRIu64" tsc ticks per lookup\n",
- cycles[table_index][LOOKUP_MULTI][0]);
- printf("Average %"PRIu64" lookups per second\n",
- (NUM_LOOKUPS * rte_get_tsc_hz())/time_taken);
- return 0;
-}
-
-static int
-timed_deletes(unsigned with_hash, unsigned table_index)
-{
- unsigned i;
- const uint64_t start_tsc = rte_rdtsc();
-
- for (i = 0; i < KEYS_TO_ADD; i++) {
- if (with_hash)
- rte_hash_del_key_with_hash(h[table_index],
- (const void *) keys[i],
- signatures[i]);
- else
- rte_hash_del_key(h[table_index],
- (const void *) keys[i]);
- }
-
- const uint64_t end_tsc = rte_rdtsc();
- const uint64_t time_taken = end_tsc - start_tsc;
- const float seconds_taken = (float)time_taken/rte_get_tsc_hz();
-
- cycles[table_index][DELETE][with_hash] = time_taken/KEYS_TO_ADD;
-
- printf("\n%"PRIu64" deletions in %f seconds\n", (uint64_t) KEYS_TO_ADD,
- seconds_taken);
- printf("Average %"PRIu64" tsc ticks per deletion\n",
- cycles[table_index][DELETE][with_hash]);
- printf("Average %"PRIu64" deletions per second\n",
- (KEYS_TO_ADD * rte_get_tsc_hz())/time_taken);
- return 0;
-}
-
-static void
-free_table(unsigned table_index)
-{
- rte_hash_free(h[table_index]);
-}
-
-static int
-reset_table(unsigned table_index)
-{
- free_table(table_index);
- if (create_table(table_index) != 0)
- return -1;
-
- return 0;
-}
-
-static int
-run_all_tbl_perf_tests(void)
-{
- unsigned i, j;
-
- for (i = 0; i < NUM_KEYSIZES; i++) {
- if (create_table(i) < 0)
- return -1;
-
- if (get_input_keys(i) < 0)
- return -1;
-
- printf("\n------ KEY SIZE = %u ----------\n\n",
- hashtest_key_lens[i]);
- printf("\n ----- WITH PRECOMPUTED HASH VALUES -----\n\n");
-
- printf("\nTimed additions\n");
- printf("------------------\n");
- if (timed_adds(1, i) < 0)
- return -1;
-
- for (j = 0; j < NUM_SHUFFLES; j++)
- shuffle_input_keys(i);
-
- printf("\nTimed lookups\n");
- printf("------------------\n");
- if (timed_lookups(1, i) < 0)
- return -1;
-
- printf("\nTimed deletions\n");
- printf("------------------\n");
- if (timed_deletes(1, i) < 0)
- return -1;
-
- if (reset_table(i) < 0)
- return -1;
-
- printf("\n ----- WITH JUST KEYS -----\n\n");
-
- printf("\nTimed additions\n");
- printf("------------------\n");
- if (timed_adds(0, i) < 0)
- return -1;
-
- for (j = 0; j < NUM_SHUFFLES; j++)
- shuffle_input_keys(i);
-
- printf("\nTimed lookups\n");
- printf("------------------\n");
- if (timed_lookups(0, i) < 0)
- return -1;
-
- printf("\nTimed lookups multi\n");
- printf("------------------\n");
- if (timed_lookups_multi(i) < 0)
- return -1;
-
- printf("\nTimed deletions\n");
- printf("------------------\n");
- if (timed_deletes(0, i) < 0)
- return -1;
-
- free_table(i);
-
- }
- printf("\nResults (in CPU cycles/operation)\n");
- printf("-----------------------------------\n");
- printf("\nWith precomputed hash\n");
- printf("\n%-18s%-18s%-18s%-18s%-18s\n",
- "Keysize", "Add", "Lookup", "Lookup_bulk", "Delete");
- for (i = 0; i < NUM_KEYSIZES; i++) {
- printf("%-18d", hashtest_key_lens[i]);
- for (j = 0; j < NUM_OPERATIONS; j++)
- printf("%-18"PRIu64, cycles[i][j][1]);
- printf("\n");
- }
- printf("\nWith just keys\n");
- printf("\n%-18s%-18s%-18s%-18s%-18s\n",
- "Keysize", "Add", "Lookup", "Lookup_bulk", "Delete");
- for (i = 0; i < NUM_KEYSIZES; i++) {
- printf("%-18d", hashtest_key_lens[i]);
- for (j = 0; j < NUM_OPERATIONS; j++)
- printf("%-18"PRIu64, cycles[i][j][0]);
- printf("\n");
- }
-
- return 0;
-}
-
-/* Control operation of performance testing of fbk hash. */
-#define LOAD_FACTOR 0.667 /* How full to make the hash table. */
-#define TEST_SIZE 1000000 /* How many operations to time. */
-#define TEST_ITERATIONS 30 /* How many measurements to take. */
-#define ENTRIES (1 << 15) /* How many entries. */
-
-static int
-fbk_hash_perf_test(void)
-{
- struct rte_fbk_hash_params params = {
- .name = "fbk_hash_test",
- .entries = ENTRIES,
- .entries_per_bucket = 4,
- .socket_id = rte_socket_id(),
- };
- struct rte_fbk_hash_table *handle = NULL;
- uint32_t *keys = NULL;
- unsigned indexes[TEST_SIZE];
- uint64_t lookup_time = 0;
- unsigned added = 0;
- unsigned value = 0;
- uint32_t key;
- uint16_t val;
- unsigned i, j;
-
- handle = rte_fbk_hash_create(¶ms);
- if (handle == NULL) {
- printf("Error creating table\n");
- return -1;
- }
-
- keys = rte_zmalloc(NULL, ENTRIES * sizeof(*keys), 0);
- if (keys == NULL) {
- printf("fbk hash: memory allocation for key store failed\n");
- return -1;
- }
-
- /* Generate random keys and values. */
- for (i = 0; i < ENTRIES; i++) {
- key = (uint32_t)rte_rand();
- key = ((uint64_t)key << 32) | (uint64_t)rte_rand();
- val = (uint16_t)rte_rand();
-
- if (rte_fbk_hash_add_key(handle, key, val) == 0) {
- keys[added] = key;
- added++;
- }
- if (added > (LOAD_FACTOR * ENTRIES))
- break;
- }
-
- for (i = 0; i < TEST_ITERATIONS; i++) {
- uint64_t begin;
- uint64_t end;
-
- /* Generate random indexes into keys[] array. */
- for (j = 0; j < TEST_SIZE; j++)
- indexes[j] = rte_rand() % added;
-
- begin = rte_rdtsc();
- /* Do lookups */
- for (j = 0; j < TEST_SIZE; j++)
- value += rte_fbk_hash_lookup(handle, keys[indexes[j]]);
-
- end = rte_rdtsc();
- lookup_time += (double)(end - begin);
- }
-
- printf("\n\n *** FBK Hash function performance test results ***\n");
- /*
- * The use of the 'value' variable ensures that the hash lookup is not
- * being optimised out by the compiler.
- */
- if (value != 0)
- printf("Number of ticks per lookup = %g\n",
- (double)lookup_time /
- ((double)TEST_ITERATIONS * (double)TEST_SIZE));
-
- rte_fbk_hash_free(handle);
-
- return 0;
-}
-
-static int
-test_hash_perf_new(void)
-{
- if (run_all_tbl_perf_tests() < 0)
- return -1;
-
- if (fbk_hash_perf_test() < 0)
- return -1;
-
- return 0;
-}
-
-static struct test_command hash_perf_new_cmd = {
- .command = "hash_perf_new_autotest",
- .callback = test_hash_perf_new,
-};
-REGISTER_TEST_COMMAND(hash_perf_new_cmd);