Signed-off-by: rujiacs <ruji...@163.com> --- helper/test/odp_hash.c | 1290 ++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 1290 insertions(+) create mode 100644 helper/test/odp_hash.c
diff --git a/helper/test/odp_hash.c b/helper/test/odp_hash.c new file mode 100644 index 0000000..8ca0f87 --- /dev/null +++ b/helper/test/odp_hash.c @@ -0,0 +1,1290 @@ +/*- + * 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 <stdint.h> +#include <string.h> +#include <stdlib.h> +#include <stdarg.h> +#include <errno.h> +#include <sys/queue.h> +#include <sys/time.h> +#include <time.h> + +#include <test_debug.h> +#include <odp.h> +#include <odp/helper/ring.h> +#include <odp/helper/hash.h> +#include <odp/helper/hash_crc.h> +#include <odp/helper/hash_jhash.h> +#include <odp/helper/hash_fbk.h> + +/******************************************************************************* + * Hash function performance test configuration section. Each performance test + * will be performed HASHTEST_ITERATIONS times. + * + * The five arrays below control what tests are performed. Every combination + * from the array entries is tested. + */ +static odp_hash_function hashtest_funcs[] = {odp_jhash, odp_hash_crc}; +static uint32_t hashtest_initvals[] = {0}; +static uint32_t hashtest_key_lens[] = {0, 2, 4, 5, 6, 7, 8, 10, 11, 15, 16, 21, 31, 32, 33, 63, 64}; +/******************************************************************************/ +#define LOCAL_FBK_HASH_ENTRIES_MAX (1 << 15) + +/* + * Check condition and return an error if true. Assumes that "handle" is the + * name of the hash structure pointer to be freed. + */ +#define RETURN_IF_ERROR(cond, str, ...) do { \ + if (cond) { \ + printf("ERROR line %d: " str "\n", __LINE__, ##__VA_ARGS__); \ + if (handle) \ + odp_hash_free(handle); \ + return -1; \ + } \ +} while (0) + +#define RETURN_IF_ERROR_FBK(cond, str, ...) do { \ + if (cond) { \ + printf("ERROR line %d: " str "\n", __LINE__, ##__VA_ARGS__); \ + if (handle) \ + odp_fbk_hash_free(handle); \ + return -1; \ + } \ +} while (0) + +/* 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)); + +/* + * Print out result of unit test hash operation. + */ +static void print_key_info(const char *msg, + const struct flow_key *key, + int32_t pos) +{ + const uint8_t *p = (const uint8_t *)key; + unsigned i; + + printf("%s key:0x", msg); + for (i = 0; i < sizeof(struct flow_key); i++) { + printf("%02X", p[i]); + } + printf(" @ pos %d\n", pos); +} + +static double get_time_diff(struct timeval *start, struct timeval *end) { + int sec = end->tv_sec - start->tv_sec; + int usec = end->tv_usec - start->tv_usec; + + if (usec < 0) { + sec--; + usec += 1000000; + } + double diff = sec + (double)usec/1000000; + return diff; +} + +/** Create IPv4 address */ +#define IPv4(a, b, c, d) ((uint32_t)(((a) & 0xff) << 24) | \ + (((b) & 0xff) << 16) | \ + (((c) & 0xff) << 8) | \ + ((d) & 0xff)) + +/* 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, +} }; + +/* Parameters used for hash table in unit test functions. Name set later. */ +static struct odp_hash_parameters ut_params = { + .entries = 64, + .key_len = sizeof(struct flow_key), /* 13 */ + .hash_func = odp_jhash, + .hash_func_init_val = 0, +}; + +static uint64_t odp_rand(void) +{ + uint64_t val; + val = rand(); + val <<= 32; + val += rand(); + return val; +} + +#define CRC32_ITERATIONS (1U << 20) +#define CRC32_DWORDS (1U << 6) + +/* + * Test a hash function. + */ +static void run_hash_func_test(odp_hash_function f, uint32_t init_val, + uint32_t key_len) +{ + static uint8_t key[ODP_HASH_KEY_LENGTH_MAX]; + unsigned i; + + + for (i = 0; i < key_len; i++) + key[i] = (uint8_t) odp_rand(); + + /* just to be on the safe side */ + if (!f) + return; + + f(key, key_len, init_val); +} + +/* + * Test all hash functions. + */ +static void run_hash_func_tests(void) +{ + unsigned i, j, k; + + for (i = 0; + i < sizeof(hashtest_funcs) / sizeof(odp_hash_function); + i++) { + for (j = 0; + j < sizeof(hashtest_initvals) / sizeof(uint32_t); + j++) { + for (k = 0; + k < sizeof(hashtest_key_lens) / sizeof(uint32_t); + k++) { + run_hash_func_test(hashtest_funcs[i], + hashtest_initvals[j], + hashtest_key_lens[k]); + } + } + } +} + +/* + * Basic sequence of operations for a single key: + * - add + * - lookup (hit) + * - delete + * - lookup (miss) + */ +static int test_add_delete(void) +{ + struct odp_hash *handle; + /* test with standard add/lookup/delete functions */ + int pos0, expectedPos0; + + ut_params.name = "test1"; + handle = odp_hash_create(&ut_params); + RETURN_IF_ERROR(handle == NULL, "hash creation failed"); + + pos0 = odp_hash_add_key(handle, &keys[0]); + print_key_info("Add", &keys[0], pos0); + RETURN_IF_ERROR(pos0 < 0, "failed to add key (pos0=%d)", pos0); + expectedPos0 = pos0; + + pos0 = odp_hash_lookup(handle, &keys[0]); + print_key_info("Lkp", &keys[0], pos0); + RETURN_IF_ERROR(pos0 != expectedPos0, + "failed to find key (pos0=%d)", pos0); + + pos0 = odp_hash_del_key(handle, &keys[0]); + print_key_info("Del", &keys[0], pos0); + RETURN_IF_ERROR(pos0 != expectedPos0, + "failed to delete key (pos0=%d)", pos0); + + pos0 = odp_hash_lookup(handle, &keys[0]); + print_key_info("Lkp", &keys[0], pos0); + RETURN_IF_ERROR(pos0 != -ENOENT, + "fail: found key after deleting! (pos0=%d)", pos0); + + odp_hash_free(handle); + + /* repeat test with precomputed hash functions */ + hash_sig_t hash_value; + int pos1, expectedPos1; + + handle = odp_hash_create(&ut_params); + RETURN_IF_ERROR(handle == NULL, "hash creation failed"); + + hash_value = odp_hash_hash(handle, &keys[0]); + pos1 = odp_hash_add_key_with_hash(handle, &keys[0], hash_value); + print_key_info("Add", &keys[0], pos1); + RETURN_IF_ERROR(pos1 < 0, "failed to add key (pos1=%d)", pos1); + expectedPos1 = pos1; + + pos1 = odp_hash_lookup_with_hash(handle, &keys[0], hash_value); + print_key_info("Lkp", &keys[0], pos1); + RETURN_IF_ERROR(pos1 != expectedPos1, + "failed to find key (pos1=%d)", pos1); + + pos1 = odp_hash_del_key_with_hash(handle, &keys[0], hash_value); + print_key_info("Del", &keys[0], pos1); + RETURN_IF_ERROR(pos1 != expectedPos1, + "failed to delete key (pos1=%d)", pos1); + + pos1 = odp_hash_lookup_with_hash(handle, &keys[0], hash_value); + print_key_info("Lkp", &keys[0], pos1); + RETURN_IF_ERROR(pos1 != -ENOENT, + "fail: found key after deleting! (pos1=%d)", pos1); + + odp_hash_free(handle); + + return 0; +} + +/* + * Sequence of operations for a single key: + * - delete: miss + * - add + * - lookup: hit + * - add: update + * - lookup: hit (updated data) + * - delete: hit + * - delete: miss + * - lookup: miss + */ +static int test_add_update_delete(void) +{ + struct odp_hash *handle; + int pos0, expectedPos0; + + ut_params.name = "test2"; + handle = odp_hash_create(&ut_params); + RETURN_IF_ERROR(handle == NULL, "hash creation failed"); + + pos0 = odp_hash_del_key(handle, &keys[0]); + print_key_info("Del", &keys[0], pos0); + RETURN_IF_ERROR(pos0 != -ENOENT, + "fail: found non-existent key (pos0=%d)", pos0); + + pos0 = odp_hash_add_key(handle, &keys[0]); + print_key_info("Add", &keys[0], pos0); + RETURN_IF_ERROR(pos0 < 0, "failed to add key (pos0=%d)", pos0); + expectedPos0 = pos0; + + pos0 = odp_hash_lookup(handle, &keys[0]); + print_key_info("Lkp", &keys[0], pos0); + RETURN_IF_ERROR(pos0 != expectedPos0, + "failed to find key (pos0=%d)", pos0); + + pos0 = odp_hash_add_key(handle, &keys[0]); + print_key_info("Add", &keys[0], pos0); + RETURN_IF_ERROR(pos0 != expectedPos0, + "failed to re-add key (pos0=%d)", pos0); + + pos0 = odp_hash_lookup(handle, &keys[0]); + print_key_info("Lkp", &keys[0], pos0); + RETURN_IF_ERROR(pos0 != expectedPos0, + "failed to find key (pos0=%d)", pos0); + + pos0 = odp_hash_del_key(handle, &keys[0]); + print_key_info("Del", &keys[0], pos0); + RETURN_IF_ERROR(pos0 != expectedPos0, + "failed to delete key (pos0=%d)", pos0); + + pos0 = odp_hash_del_key(handle, &keys[0]); + print_key_info("Del", &keys[0], pos0); + RETURN_IF_ERROR(pos0 != -ENOENT, + "fail: deleted already deleted key (pos0=%d)", pos0); + + pos0 = odp_hash_lookup(handle, &keys[0]); + print_key_info("Lkp", &keys[0], pos0); + RETURN_IF_ERROR(pos0 != -ENOENT, + "fail: found key after deleting! (pos0=%d)", pos0); + + odp_hash_free(handle); + return 0; +} + +/* + * Sequence of operations for find existing hash table + * + * - create table + * - find existing table: hit + * - find non-existing table: miss + * + */ +static int test_hash_find_existing(void) +{ + struct odp_hash *handle = NULL, *result = NULL; + + /* Create hash table. */ + ut_params.name = "hash_find_existing"; + handle = odp_hash_create(&ut_params); + RETURN_IF_ERROR(handle == NULL, "hash creation failed"); + + /* Try to find existing hash table */ + result = odp_hash_find_existing("hash_find_existing"); + RETURN_IF_ERROR(result != handle, "could not find existing hash table"); + + /* Try to find non-existing hash table */ + result = odp_hash_find_existing("hash_find_non_existing"); + RETURN_IF_ERROR(!(result == NULL), "found table that shouldn't exist"); + + /* Cleanup. */ + odp_hash_free(handle); + + return 0; +} + +/* + * Sequence of operations for 5 keys + * - add keys + * - lookup keys: hit + * - add keys (update) + * - lookup keys: hit (updated data) + * - delete keys : hit + * - lookup keys: miss + */ +static int test_five_keys(void) +{ + struct odp_hash *handle; + const void *key_array[5] = {0}; + int pos[5]; + int expected_pos[5]; + unsigned i; + int ret; + + ut_params.name = "test3"; + handle = odp_hash_create(&ut_params); + RETURN_IF_ERROR(handle == NULL, "hash creation failed"); + + /* Add */ + for (i = 0; i < 5; i++) { + pos[i] = odp_hash_add_key(handle, &keys[i]); + print_key_info("Add", &keys[i], pos[i]); + RETURN_IF_ERROR(pos[i] < 0, + "failed to add key (pos[%u]=%d)", i, pos[i]); + expected_pos[i] = pos[i]; + } + + /* Lookup */ + for (i = 0; i < 5; i++) + key_array[i] = &keys[i]; + + ret = odp_hash_lookup_multi(handle, &key_array[0], 5, (int32_t *)pos); + if (ret == 0) + for (i = 0; i < 5; i++) { + print_key_info("Lkp", key_array[i], pos[i]); + RETURN_IF_ERROR(pos[i] != expected_pos[i], "failed to find key (pos[%u]=%d)", i, pos[i]); + } + + /* Add - update */ + for (i = 0; i < 5; i++) { + pos[i] = odp_hash_add_key(handle, &keys[i]); + print_key_info("Add", &keys[i], pos[i]); + RETURN_IF_ERROR(pos[i] != expected_pos[i], "failed to add key (pos[%u]=%d)", i, pos[i]); + } + + /* Lookup */ + for (i = 0; i < 5; i++) { + pos[i] = odp_hash_lookup(handle, &keys[i]); + print_key_info("Lkp", &keys[i], pos[i]); + RETURN_IF_ERROR(pos[i] != expected_pos[i], "failed to find key (pos[%u]=%d)", i, pos[i]); + } + + /* Delete */ + for (i = 0; i < 5; i++) { + pos[i] = odp_hash_del_key(handle, &keys[i]); + print_key_info("Del", &keys[i], pos[i]); + RETURN_IF_ERROR(pos[i] != expected_pos[i], "failed to delete key (pos[%u]=%d)", i, pos[i]); + } + + /* Lookup */ + for (i = 0; i < 5; i++) { + pos[i] = odp_hash_lookup(handle, &keys[i]); + print_key_info("Lkp", &keys[i], pos[i]); + RETURN_IF_ERROR(pos[i] != -ENOENT, "found non-existent key (pos[%u]=%d)", i, pos[i]); + } + + /* Lookup multi */ + ret = odp_hash_lookup_multi(handle, &key_array[0], 5, (int32_t *)pos); + if (ret == 0) + for (i = 0; i < 5; i++) { + print_key_info("Lkp", key_array[i], pos[i]); + RETURN_IF_ERROR(pos[i] != -ENOENT, "found not-existent key (pos[%u]=%d)", i, pos[i]); + } + + odp_hash_free(handle); + + return 0; +} + +/******************************************************************************/ +static int +fbk_hash_unit_test(void) +{ + struct odp_fbk_hash_params params = { + .name = "fbk_hash_test", + .entries = LOCAL_FBK_HASH_ENTRIES_MAX, + .entries_per_bucket = 4, + }; + + struct odp_fbk_hash_params invalid_params_1 = { + .name = "invalid_1", + .entries = LOCAL_FBK_HASH_ENTRIES_MAX + 1, /* Not power of 2 */ + .entries_per_bucket = 4, + }; + + struct odp_fbk_hash_params invalid_params_2 = { + .name = "invalid_2", + .entries = 4, + .entries_per_bucket = 3, /* Not power of 2 */ + }; + + struct odp_fbk_hash_params invalid_params_3 = { + .name = "invalid_3", + .entries = 0, /* Entries is 0 */ + .entries_per_bucket = 4, + }; + + struct odp_fbk_hash_params invalid_params_4 = { + .name = "invalid_4", + .entries = LOCAL_FBK_HASH_ENTRIES_MAX, + .entries_per_bucket = 0, /* Entries per bucket is 0 */ + }; + + struct odp_fbk_hash_params invalid_params_5 = { + .name = "invalid_5", + .entries = 4, + .entries_per_bucket = 8, /* Entries per bucket > entries */ + }; + + struct odp_fbk_hash_params invalid_params_6 = { + .name = "invalid_6", + .entries = ODP_FBK_HASH_ENTRIES_MAX * 2, /* Entries > max allowed */ + .entries_per_bucket = 4, + }; + + struct odp_fbk_hash_params invalid_params_7 = { + .name = "invalid_7", + .entries = ODP_FBK_HASH_ENTRIES_MAX, + .entries_per_bucket = ODP_FBK_HASH_ENTRIES_PER_BUCKET_MAX * 2, /* Entries > max allowed */ + }; + + /* try to create two hashes with identical names + * in this case, trying to create a second one will not + * fail but will simply return pointer to the existing + * hash with that name. sort of like a "find hash by name" :-) + */ + struct odp_fbk_hash_params invalid_params_same_name_1 = { + .name = "same_name", /* hash with identical name */ + .entries = 4, + .entries_per_bucket = 2, + }; + + /* trying to create this hash should return a pointer to an existing hash */ + struct odp_fbk_hash_params invalid_params_same_name_2 = { + .name = "same_name", /* hash with identical name */ + .entries = ODP_FBK_HASH_ENTRIES_MAX, + .entries_per_bucket = 4, + }; + + /* this is a sanity check for "same name" test + * creating this hash will check if we are actually able to create + * multiple hashes with different names (instead of having just one). + */ + struct odp_fbk_hash_params different_name = { + .name = "different_name", /* different name */ + .entries = ODP_FBK_HASH_ENTRIES_MAX, + .entries_per_bucket = 4, + }; + + struct odp_fbk_hash_params params_jhash = { + .name = "valid", + .entries = LOCAL_FBK_HASH_ENTRIES_MAX, + .entries_per_bucket = 4, + .hash_func = odp_jhash_1word, /* Tests for different hash_func */ + .init_val = ODP_FBK_HASH_INIT_VAL_DEFAULT, + }; + + struct odp_fbk_hash_params params_nohash = { + .name = "valid nohash", + .entries = LOCAL_FBK_HASH_ENTRIES_MAX, + .entries_per_bucket = 4, + .hash_func = NULL, /* Tests for null hash_func */ + .init_val = ODP_FBK_HASH_INIT_VAL_DEFAULT, + }; + + struct odp_fbk_hash_table *handle, *tmp; + uint32_t keys[5] = {0xc6e18639, 0xe67c201c, 0xd4c8cffd, 0x44728691, 0xd5430fa9}; + uint16_t vals[5] = {28108, 5699, 38490, 2166, 61571}; + int status; + unsigned i; + double used_entries; + + /* Try creating hashes with invalid parameters */ + printf("# Testing hash creation with invalid parameters " + "- expect error msgs\n"); + handle = odp_fbk_hash_create(&invalid_params_1); + RETURN_IF_ERROR_FBK(handle != NULL, "fbk hash creation should have failed"); + + handle = odp_fbk_hash_create(&invalid_params_2); + RETURN_IF_ERROR_FBK(handle != NULL, "fbk hash creation should have failed"); + + handle = odp_fbk_hash_create(&invalid_params_3); + RETURN_IF_ERROR_FBK(handle != NULL, "fbk hash creation should have failed"); + + handle = odp_fbk_hash_create(&invalid_params_4); + RETURN_IF_ERROR_FBK(handle != NULL, "fbk hash creation should have failed"); + + handle = odp_fbk_hash_create(&invalid_params_5); + RETURN_IF_ERROR_FBK(handle != NULL, "fbk hash creation should have failed"); + + handle = odp_fbk_hash_create(&invalid_params_6); + RETURN_IF_ERROR_FBK(handle != NULL, "fbk hash creation should have failed"); + + handle = odp_fbk_hash_create(&invalid_params_7); + RETURN_IF_ERROR_FBK(handle != NULL, "fbk hash creation should have failed"); + + handle = odp_fbk_hash_create(&invalid_params_same_name_1); + RETURN_IF_ERROR_FBK(handle == NULL, "fbk hash creation should have succeeded"); + + tmp = odp_fbk_hash_create(&invalid_params_same_name_2); + RETURN_IF_ERROR_FBK(tmp == NULL, "fbk hash creation should have succeeded"); + if (tmp != handle) { + printf("ERROR line %d: hashes should have been the same\n", __LINE__); + odp_fbk_hash_free(handle); + odp_fbk_hash_free(tmp); + return -1; + } + + /* we are not freeing tmp or handle here because we need a hash list + * to be not empty for the next test */ + + /* create a hash in non-empty list - good for coverage */ + tmp = odp_fbk_hash_create(&different_name); + RETURN_IF_ERROR_FBK(tmp == NULL, "fbk hash creation should have succeeded"); + + /* free both hashes */ + odp_fbk_hash_free(handle); + odp_fbk_hash_free(tmp); + + /* Create empty jhash hash. */ + handle = odp_fbk_hash_create(¶ms_jhash); + RETURN_IF_ERROR_FBK(handle == NULL, "fbk jhash hash creation failed"); + + /* Cleanup. */ + odp_fbk_hash_free(handle); + + /* Create empty jhash hash. */ + handle = odp_fbk_hash_create(¶ms_nohash); + RETURN_IF_ERROR_FBK(handle == NULL, "fbk nohash hash creation failed"); + + /* Cleanup. */ + odp_fbk_hash_free(handle); + + /* Create empty hash. */ + handle = odp_fbk_hash_create(¶ms); + RETURN_IF_ERROR_FBK(handle == NULL, "fbk hash creation failed"); + + used_entries = odp_fbk_hash_get_load_factor(handle) * LOCAL_FBK_HASH_ENTRIES_MAX; + RETURN_IF_ERROR_FBK((unsigned)used_entries != 0, \ + "load factor right after creation is not zero but it should be"); + /* Add keys. */ + for (i = 0; i < 5; i++) { + status = odp_fbk_hash_add_key(handle, keys[i], vals[i]); + RETURN_IF_ERROR_FBK(status != 0, "fbk hash add failed"); + } + + used_entries = odp_fbk_hash_get_load_factor(handle) * LOCAL_FBK_HASH_ENTRIES_MAX; + RETURN_IF_ERROR_FBK((unsigned)used_entries != (unsigned)((((double)5)/LOCAL_FBK_HASH_ENTRIES_MAX)*LOCAL_FBK_HASH_ENTRIES_MAX), \ + "load factor now is not as expected"); + /* Find value of added keys. */ + for (i = 0; i < 5; i++) { + status = odp_fbk_hash_lookup(handle, keys[i]); + RETURN_IF_ERROR_FBK(status != vals[i], + "fbk hash lookup failed"); + } + + /* Change value of added keys. */ + for (i = 0; i < 5; i++) { + status = odp_fbk_hash_add_key(handle, keys[i], vals[4 - i]); + RETURN_IF_ERROR_FBK(status != 0, "fbk hash update failed"); + } + + /* Find new values. */ + for (i = 0; i < 5; i++) { + status = odp_fbk_hash_lookup(handle, keys[i]); + RETURN_IF_ERROR_FBK(status != vals[4-i], + "fbk hash lookup failed"); + } + + /* Delete keys individually. */ + for (i = 0; i < 5; i++) { + status = odp_fbk_hash_delete_key(handle, keys[i]); + RETURN_IF_ERROR_FBK(status != 0, "fbk hash delete failed"); + } + + used_entries = odp_fbk_hash_get_load_factor(handle) * LOCAL_FBK_HASH_ENTRIES_MAX; + RETURN_IF_ERROR_FBK((unsigned)used_entries != 0, \ + "load factor right after deletion is not zero but it should be"); + /* Lookup should now fail. */ + for (i = 0; i < 5; i++) { + status = odp_fbk_hash_lookup(handle, keys[i]); + RETURN_IF_ERROR_FBK(status == 0, + "fbk hash lookup should have failed"); + } + + /* Add keys again. */ + for (i = 0; i < 5; i++) { + status = odp_fbk_hash_add_key(handle, keys[i], vals[i]); + RETURN_IF_ERROR_FBK(status != 0, "fbk hash add failed"); + } + + /* Make sure they were added. */ + for (i = 0; i < 5; i++) { + status = odp_fbk_hash_lookup(handle, keys[i]); + RETURN_IF_ERROR_FBK(status != vals[i], + "fbk hash lookup failed"); + } + + /* Clear all entries. */ + odp_fbk_hash_clear_all(handle); + + /* Lookup should fail. */ + for (i = 0; i < 5; i++) { + status = odp_fbk_hash_lookup(handle, keys[i]); + RETURN_IF_ERROR_FBK(status == 0, + "fbk hash lookup should have failed"); + } + + /* coverage */ + + /* fill up the hash_table */ + for (i = 0; i < ODP_FBK_HASH_ENTRIES_MAX + 1; i++) + odp_fbk_hash_add_key(handle, i, (uint16_t) i); + + /* Find non-existent key in a full hashtable */ + status = odp_fbk_hash_lookup(handle, ODP_FBK_HASH_ENTRIES_MAX + 1); + RETURN_IF_ERROR_FBK(status != -ENOENT, + "fbk hash lookup succeeded"); + + /* Delete non-existent key in a full hashtable */ + status = odp_fbk_hash_delete_key(handle, ODP_FBK_HASH_ENTRIES_MAX + 1); + RETURN_IF_ERROR_FBK(status != -ENOENT, + "fbk hash delete succeeded"); + + /* Delete one key from a full hashtable */ + status = odp_fbk_hash_delete_key(handle, 1); + RETURN_IF_ERROR_FBK(status != 0, + "fbk hash delete failed"); + + /* Clear all entries. */ + odp_fbk_hash_clear_all(handle); + + /* Cleanup. */ + odp_fbk_hash_free(handle); + + /* Cover the NULL case. */ + odp_fbk_hash_free(0); + + return 0; +} + +#define BUCKET_ENTRIES 4 +/* + * Do tests for hash creation with bad parameters. + */ +static int test_hash_creation_with_bad_parameters(void) +{ + struct odp_hash *handle; + struct odp_hash_parameters params; + + handle = odp_hash_create(NULL); + if (handle != NULL) { + odp_hash_free(handle); + printf("Impossible creating hash sucessfully without any parameter\n"); + return -1; + } + + memcpy(¶ms, &ut_params, sizeof(params)); + params.name = "creation_with_bad_parameters_0"; + params.entries = ODP_HASH_ENTRIES_MAX + 1; + handle = odp_hash_create(¶ms); + if (handle != NULL) { + odp_hash_free(handle); + printf("Impossible creating hash sucessfully with entries in parameter exceeded\n"); + return -1; + } + + memcpy(¶ms, &ut_params, sizeof(params)); + params.name = "creation_with_bad_parameters_2"; + params.entries = BUCKET_ENTRIES - 1; + handle = odp_hash_create(¶ms); + if (handle != NULL) { + odp_hash_free(handle); + printf("Impossible creating hash sucessfully if entries less than bucket_entries in parameter\n"); + return -1; + } + + memcpy(¶ms, &ut_params, sizeof(params)); + params.name = "creation_with_bad_parameters_3"; + params.key_len = 0; + handle = odp_hash_create(¶ms); + if (handle != NULL) { + odp_hash_free(handle); + printf("Impossible creating hash sucessfully if key_len in parameter is zero\n"); + return -1; + } + + odp_hash_free(handle); + printf("# Test successful. No more errors expected\n"); + + return 0; +} + +/* + * Do tests for hash creation with parameters that look incorrect + * but are actually valid. + */ +static int +test_hash_creation_with_good_parameters(void) +{ + struct odp_hash *handle, *tmp; + struct odp_hash_parameters params; + + /* create with null hash function - should choose DEFAULT_HASH_FUNC */ + memcpy(¶ms, &ut_params, sizeof(params)); + params.name = "same_name"; + params.hash_func = NULL; + handle = odp_hash_create(¶ms); + if (handle == NULL) { + printf("Creating hash with null hash_func failed\n"); + return -1; + } + + /* this test is trying to create a hash with the same name as previous one. + * this should return a pointer to the hash we previously created. + * the previous hash isn't freed exactly for the purpose of it being in + * the hash list. + */ + memcpy(¶ms, &ut_params, sizeof(params)); + params.name = "same_name"; + tmp = odp_hash_create(¶ms); + + /* check if the returned handle is actually equal to the previous hash */ + if (handle != tmp) { + odp_hash_free(handle); + odp_hash_free(tmp); + printf("Creating hash with existing name was successful\n"); + return -1; + } + + /* try creating hash when there already are hashes in the list. + * the previous hash is not freed to have a non-empty hash list. + * the other hash that's in the list is still pointed to by "handle" var. + */ + memcpy(¶ms, &ut_params, sizeof(params)); + params.name = "different_name"; + tmp = odp_hash_create(¶ms); + if (tmp == NULL) { + odp_hash_free(handle); + printf("Creating hash with valid parameters failed\n"); + return -1; + } + + odp_hash_free(tmp); + odp_hash_free(handle); + + return 0; +} + +#define ITERATIONS 50 +#define NUM_ENTRIES 1024 +static int test_hash_iteration(void) +{ + struct odp_hash *handle; + unsigned i; + uint8_t keys[NUM_ENTRIES][ODP_HASH_KEY_LENGTH_MAX]; + const void *next_key; + void *next_data; + void *data[NUM_ENTRIES]; + unsigned added_keys; + uint32_t iter = 0; + int ret = 0; + + ut_params.entries = NUM_ENTRIES; + ut_params.name = "test_hash_iteration"; + ut_params.hash_func = odp_jhash; + ut_params.key_len = 16; + handle = odp_hash_create(&ut_params); + RETURN_IF_ERROR(handle == NULL, "hash creation failed"); + + /* Add random entries until key cannot be added */ + for (added_keys = 0; added_keys < NUM_ENTRIES; added_keys++) { + data[added_keys] = (void *) ((uintptr_t) odp_rand()); + for (i = 0; i < ut_params.key_len; i++) + keys[added_keys][i] = odp_rand() % 255; + ret = odp_hash_add_key_data(handle, keys[added_keys], data[added_keys]); + if (ret < 0) + break; + } + + /* Iterate through the hash table */ + while (odp_hash_iterate(handle, &next_key, &next_data, &iter) >= 0) { + /* Search for the key in the list of keys added */ + for (i = 0; i < NUM_ENTRIES; i++) { + if (memcmp(next_key, keys[i], ut_params.key_len) == 0) { + if (next_data != data[i]) { + printf("Data found in the hash table is" + "not the data added with the key\n"); + goto err; + } + added_keys--; + break; + } + } + if (i == NUM_ENTRIES) { + printf("Key found in the hash table was not added\n"); + goto err; + } + } + + /* Check if all keys have been iterated */ + if (added_keys != 0) { + printf("There were still %u keys to iterate\n", added_keys); + goto err; + } + + odp_hash_free(handle); + return 0; + +err: + odp_hash_free(handle); + return -1; +} + +static uint8_t key[16] = {0x00, 0x01, 0x02, 0x03, + 0x04, 0x05, 0x06, 0x07, + 0x08, 0x09, 0x0a, 0x0b, + 0x0c, 0x0d, 0x0e, 0x0f}; +static struct odp_hash_parameters hash_params_ex = { + .name = NULL, + .entries = 64, + .key_len = 0, + .hash_func = NULL, + .hash_func_init_val = 0, +}; + +/* + * add/delete key with jhash2 + */ +static int +test_hash_add_delete_jhash2(void) +{ + int ret = -1; + struct odp_hash *handle; + int32_t pos1, pos2; + + hash_params_ex.name = "hash_test_jhash2"; + hash_params_ex.key_len = 4; + hash_params_ex.hash_func = (odp_hash_function)odp_jhash_32b; + + handle = odp_hash_create(&hash_params_ex); + if (handle == NULL) { + printf("test_hash_add_delete_jhash2 fail to create hash\n"); + goto fail_jhash2; + } + pos1 = odp_hash_add_key(handle, (void *)&key[0]); + if (pos1 < 0) { + printf("test_hash_add_delete_jhash2 fail to add hash key\n"); + goto fail_jhash2; + } + + pos2 = odp_hash_del_key(handle, (void *)&key[0]); + if (pos2 < 0 || pos1 != pos2) { + printf("test_hash_add_delete_jhash2 delete different key from being added\n"); + goto fail_jhash2; + } + ret = 0; + +fail_jhash2: + if (handle != NULL) + odp_hash_free(handle); + + return ret; +} + +/* + * add/delete (2) key with jhash2 + */ +static int +test_hash_add_delete_2_jhash2(void) +{ + int ret = -1; + struct odp_hash *handle; + int32_t pos1, pos2; + + hash_params_ex.name = "hash_test_2_jhash2"; + hash_params_ex.key_len = 8; + hash_params_ex.hash_func = (odp_hash_function)odp_jhash_32b; + + handle = odp_hash_create(&hash_params_ex); + if (handle == NULL) + goto fail_2_jhash2; + + pos1 = odp_hash_add_key(handle, (void *)&key[0]); + if (pos1 < 0) + goto fail_2_jhash2; + + pos2 = odp_hash_del_key(handle, (void *)&key[0]); + if (pos2 < 0 || pos1 != pos2) + goto fail_2_jhash2; + + ret = 0; + +fail_2_jhash2: + if (handle != NULL) + odp_hash_free(handle); + + return ret; +} + +static uint32_t +test_hash_jhash_1word(const void *key, uint32_t length, uint32_t initval) +{ + const uint32_t *k = key; + + (void)(length); + + return odp_jhash_1word(k[0], initval); +} + +static uint32_t +test_hash_jhash_2word(const void *key, uint32_t length, uint32_t initval) +{ + const uint32_t *k = key; + + (void)(length); + + return odp_jhash_2words(k[0], k[1], initval); +} + +static uint32_t +test_hash_jhash_3word(const void *key, uint32_t length, uint32_t initval) +{ + const uint32_t *k = key; + + (void)(length); + + return odp_jhash_3words(k[0], k[1], k[2], initval); +} + +/* + * add/delete key with jhash 1word + */ +static int +test_hash_add_delete_jhash_1word(void) +{ + int ret = -1; + struct odp_hash *handle; + int32_t pos1, pos2; + + hash_params_ex.name = "hash_test_jhash_1word"; + hash_params_ex.key_len = 4; + hash_params_ex.hash_func = test_hash_jhash_1word; + + handle = odp_hash_create(&hash_params_ex); + if (handle == NULL) + goto fail_jhash_1word; + + pos1 = odp_hash_add_key(handle, (void *)&key[0]); + if (pos1 < 0) + goto fail_jhash_1word; + + pos2 = odp_hash_del_key(handle, (void *)&key[0]); + if (pos2 < 0 || pos1 != pos2) + goto fail_jhash_1word; + + ret = 0; + +fail_jhash_1word: + if (handle != NULL) + odp_hash_free(handle); + + return ret; +} + +/* + * add/delete key with jhash 2word + */ +static int +test_hash_add_delete_jhash_2word(void) +{ + int ret = -1; + struct odp_hash *handle; + int32_t pos1, pos2; + + hash_params_ex.name = "hash_test_jhash_2word"; + hash_params_ex.key_len = 8; + hash_params_ex.hash_func = test_hash_jhash_2word; + + handle = odp_hash_create(&hash_params_ex); + if (handle == NULL) + goto fail_jhash_2word; + + pos1 = odp_hash_add_key(handle, (void *)&key[0]); + if (pos1 < 0) + goto fail_jhash_2word; + + pos2 = odp_hash_del_key(handle, (void *)&key[0]); + if (pos2 < 0 || pos1 != pos2) + goto fail_jhash_2word; + + ret = 0; + +fail_jhash_2word: + if (handle != NULL) + odp_hash_free(handle); + + return ret; +} + +/* + * add/delete key with jhash 3word + */ +static int +test_hash_add_delete_jhash_3word(void) +{ + int ret = -1; + struct odp_hash *handle; + int32_t pos1, pos2; + + hash_params_ex.name = "hash_test_jhash_3word"; + hash_params_ex.key_len = 12; + hash_params_ex.hash_func = test_hash_jhash_3word; + + handle = odp_hash_create(&hash_params_ex); + if (handle == NULL) + goto fail_jhash_3word; + + pos1 = odp_hash_add_key(handle, (void *)&key[0]); + if (pos1 < 0) + goto fail_jhash_3word; + + pos2 = odp_hash_del_key(handle, (void *)&key[0]); + if (pos2 < 0 || pos1 != pos2) + goto fail_jhash_3word; + + ret = 0; + +fail_jhash_3word: + if (handle != NULL) + odp_hash_free(handle); + + return ret; +} + +#define ITERATIONS 50 +#define LOOKUP_TIMES 1000 +/* + * Test to see the average table utilization (entries added/max entries) + * before hitting a random entry that cannot be added + */ +static int test_average_table_utilization(void) +{ + struct odp_hash *handle; + uint8_t simple_key[ODP_HASH_KEY_LENGTH_MAX], lookup_key[LOOKUP_TIMES][ODP_HASH_KEY_LENGTH_MAX]; + unsigned i, j; + unsigned added_keys, average_keys_added = 0; + int ret, pos_arr[LOOKUP_TIMES]; + struct timeval start, add_end, lookup_end; + const void *bulk_key[LOOKUP_TIMES] = {0}; + double add_time = 0, lookup_time = 0, bulk_time = 0; + + printf("\n# Running test to determine average utilization\n before adding elements begins to fail\n"); + printf("Measuring performance, please wait"); + fflush(stdout); + ut_params.entries = 1 << 20; + ut_params.name = "test_average_utilization"; + ut_params.hash_func = odp_jhash; + handle = odp_hash_create(&ut_params); + RETURN_IF_ERROR(handle == NULL, "hash creation failed"); + + for (j = 0; j < ITERATIONS; j++) { + ret = 0; + unsigned added_one = 0; + gettimeofday(&start, 0); + /* Add random entries until key cannot be added */ + for (added_keys = 0; ret >= 0; added_keys++) { + for (i = 0; i < ut_params.key_len; i++) { + simple_key[i] = odp_rand() % 255; + if (added_one < LOOKUP_TIMES) { + lookup_key[added_one][i] = simple_key[i]; + } + } + if (added_one < LOOKUP_TIMES) { + bulk_key[added_one] = &lookup_key[added_one]; + } + ret = odp_hash_add_key(handle, simple_key); + added_one++; + } + gettimeofday(&add_end, 0); + add_time += get_time_diff(&start, &add_end); + if (ret != -ENOSPC) { + printf("Unexpected error when adding keys\n"); + odp_hash_free(handle); + return -1; + } + odp_hash_lookup_bulk(handle, &bulk_key[0], LOOKUP_TIMES, pos_arr); + gettimeofday(&start, 0); + bulk_time += get_time_diff(&lookup_end, &start); + + average_keys_added += added_keys; + + odp_hash_reset(handle); + + /* Print a dot to show progress on operations */ + printf("."); + fflush(stdout); + } + + average_keys_added /= ITERATIONS; + + printf("\nAverage table utilization = %.2f%% (%u/%u)\n", + ((double) average_keys_added / ut_params.entries * 100), + average_keys_added, ut_params.entries); + printf("Average insert time = %lf, lookup time = %lf, lookup_bulk time = %lf\n", + (add_time / ITERATIONS), (lookup_time / ITERATIONS), + (bulk_time / ITERATIONS)); + odp_hash_free(handle); + + return 0; +} + +/* + * Do all unit and performance tests. + */ +static int +test_hash(void) +{ + odp_hash_list_init(); + odph_ring_tailq_init(); + odp_fbk_hash_list_init(); + if (test_add_delete() < 0) + return -1; + if (test_hash_add_delete_jhash2() < 0) + return -1; + if (test_hash_add_delete_2_jhash2() < 0) + return -1; + if (test_hash_add_delete_jhash_1word() < 0) + return -1; + if (test_hash_add_delete_jhash_2word() < 0) + return -1; + if (test_hash_add_delete_jhash_3word() < 0) + return -1; + if (test_hash_find_existing() < 0) + return -1; + if (test_add_update_delete() < 0) + return -1; + if (test_five_keys() < 0) + return -1; + + if (fbk_hash_unit_test() < 0) + return -1; + + if (test_hash_creation_with_bad_parameters() < 0) + return -1; + if (test_hash_creation_with_good_parameters() < 0) + return -1; + if (test_hash_iteration() < 0) + return -1; + if (test_average_table_utilization() < 0) + return -1; + + run_hash_func_tests(); + return 0; +} + +int main(int argc TEST_UNUSED, char *argv[] TEST_UNUSED) +{ + if (odp_init_global(NULL, NULL)) { + LOG_ERR("Error: ODP global init failed.\n"); + exit(EXIT_FAILURE); + } + + if (odp_init_local(ODP_THREAD_WORKER)) { + LOG_ERR("Error: ODP local init failed.\n"); + exit(EXIT_FAILURE); + } + srand((int)time(0)); + int val = test_hash(); + + if (odp_term_local()) { + LOG_ERR("Error: ODP local term failed.\n"); + exit(EXIT_FAILURE); + } + + if (odp_term_global()) { + LOG_ERR("Error: ODP global term failed.\n"); + exit(EXIT_FAILURE); + } + + return val; +} -- 1.9.1 _______________________________________________ lng-odp mailing list lng-odp@lists.linaro.org https://lists.linaro.org/mailman/listinfo/lng-odp