This is an automated email from the git hooks/post-receive script. It was generated because a ref change was pushed to the repository containing the project "".

The branch, api-next has been updated via 1a24b758857eef4caf2a1801851315b6c93edd76 (commit) via d1e693d7177d10f382d69b659ab359fddee783b5 (commit) from 449cd8f2c3a694b219fcbb98d7d9948bce583ca1 (commit)

Those revisions listed above that are new to this repository have not appeared on any other notification email; so we list those revisions in full, below.

- Log ----------------------------------------------------------------- commit 1a24b758857eef4caf2a1801851315b6c93edd76 Author: Ru Jia jiaru@ict.ac.cn Date: Mon Jun 13 14:42:14 2016 +0800

helper: test: add test of cuckoo hash table

This test program consists of basic validation tests and performance tests.

Signed-off-by: Ru Jia jiaru@ict.ac.cn Reviewed-and-tested-by: Bill Fischofer bill.fischofer@linaro.org Signed-off-by: Maxim Uvarov maxim.uvarov@linaro.org

diff --git a/helper/test/.gitignore b/helper/test/.gitignore index 5ce3c3b..482fdb5 100644 --- a/helper/test/.gitignore +++ b/helper/test/.gitignore @@ -1,6 +1,7 @@ *.trs *.log chksum +cuckootable odpthreads parse process diff --git a/helper/test/Makefile.am b/helper/test/Makefile.am index e9e8785..0811d28 100644 --- a/helper/test/Makefile.am +++ b/helper/test/Makefile.am @@ -6,10 +6,11 @@ AM_LDFLAGS += -static TESTS_ENVIRONMENT += TEST_DIR=${builddir}

EXECUTABLES = chksum$(EXEEXT) \ + cuckootable$(EXEEXT) \ + table$(EXEEXT) \ thread$(EXEEXT) \ parse$(EXEEXT)\ - process$(EXEEXT)\ - table$(EXEEXT) + process$(EXEEXT)

COMPILE_ONLY = odpthreads

@@ -27,6 +28,7 @@ bin_PROGRAMS = $(EXECUTABLES) $(COMPILE_ONLY) EXTRA_DIST = odpthreads_as_processes odpthreads_as_pthreads

dist_chksum_SOURCES = chksum.c +dist_cuckootable_SOURCES = cuckootable.c dist_odpthreads_SOURCES = odpthreads.c odpthreads_LDADD = $(LIB)/libodphelper-linux.la $(LIB)/libodp-linux.la dist_thread_SOURCES = thread.c diff --git a/helper/test/cuckootable.c b/helper/test/cuckootable.c new file mode 100644 index 0000000..5b4333b --- /dev/null +++ b/helper/test/cuckootable.c @@ -0,0 +1,573 @@ +/* Copyright (c) 2016, Linaro Limited + * All rights reserved. + * + * SPDX-License-Identifier: BSD-3-Clause + */ + +/*- + * BSD LICENSE + * + * Copyright(c) 2010-2016 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 <odp_api.h> +#include <test_debug.h> +#include <../odph_cuckootable.h> + +/******************************************************************************* + * Hash function performance test configuration section. + * + * The five arrays below control what tests are performed. Every combination + * from the array entries is tested. + */ +/******************************************************************************/ + +/* 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; +} __packed; + +/* + * Print out result of unit test hash operation. + */ +static void print_key_info( + const char *msg, const struct flow_key *key) +{ + 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("\n"); +} + +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, +} }; + +/* + * Basic sequence of operations for a single key: + * - put + * - get (hit) + * - remove + * - get (miss) + */ +static int test_put_remove(void) +{ + odph_table_t table; + odph_table_ops_t *ops; + + ops = &odph_cuckoo_table_ops; + + /* test with standard put/get/remove functions */ + int ret; + + table = ops->f_create("put_remove", 10, sizeof(struct flow_key), 0); + if (table == NULL) { + printf("cuckoo hash table creation failed\n"); + return -1; + } + + ret = odph_cuckoo_table_put_value(table, &keys[0], NULL); + print_key_info("Add", &keys[0]); + if (ret < 0) { + printf("failed to add key\n"); + odph_cuckoo_table_destroy(table); + return -1; + } + + ret = odph_cuckoo_table_get_value(table, &keys[0], NULL, 0); + print_key_info("Lkp", &keys[0]); + if (ret < 0) { + printf("failed to find key\n"); + odph_cuckoo_table_destroy(table); + return -1; + } + + ret = odph_cuckoo_table_remove_value(table, &keys[0]); + print_key_info("Del", &keys[0]); + if (ret < 0) { + printf("failed to delete key\n"); + odph_cuckoo_table_destroy(table); + return -1; + } + + ret = odph_cuckoo_table_get_value(table, &keys[0], NULL, 0); + print_key_info("Lkp", &keys[0]); + if (ret >= 0) { + printf("error: found key after deleting!\n"); + odph_cuckoo_table_destroy(table); + return -1; + } + + odph_cuckoo_table_destroy(table); + return 0; +} + +/* + * Sequence of operations for a single key: + * key type : struct flow_key + * value type: uint8_t + * - remove: miss + * - put + * - get: hit + * - put: update + * - get: hit (updated data) + * - remove: hit + * - remove: miss + */ +static int test_put_update_remove(void) +{ + odph_table_t table; + int ret; + uint8_t val1 = 1, val2 = 2, val = 0; + + table = odph_cuckoo_table_create( + "put_update_remove", + 10, sizeof(struct flow_key), sizeof(uint8_t)); + if (table == NULL) { + printf("failed to create table\n"); + return -1; + } + + ret = odph_cuckoo_table_remove_value(table, &keys[0]); + print_key_info("Del", &keys[0]); + if (ret >= 0) { + printf("error: found non-existent key\n"); + odph_cuckoo_table_destroy(table); + return -1; + } + + ret = odph_cuckoo_table_put_value(table, &keys[0], &val1); + print_key_info("Add", &keys[0]); + if (ret < 0) { + printf("failed to add key\n"); + odph_cuckoo_table_destroy(table); + return -1; + } + + ret = odph_cuckoo_table_get_value( + table, &keys[0], &val, sizeof(uint8_t)); + print_key_info("Lkp", &keys[0]); + if (ret < 0) { + printf("failed to find key\n"); + odph_cuckoo_table_destroy(table); + return -1; + } + + ret = odph_cuckoo_table_put_value(table, &keys[0], &val2); + if (ret < 0) { + printf("failed to re-add key\n"); + odph_cuckoo_table_destroy(table); + return -1; + } + + ret = odph_cuckoo_table_get_value( + table, &keys[0], &val, sizeof(uint8_t)); + print_key_info("Lkp", &keys[0]); + if (ret < 0) { + printf("failed to find key\n"); + odph_cuckoo_table_destroy(table); + return -1; + } + + ret = odph_cuckoo_table_remove_value(table, &keys[0]); + print_key_info("Del", &keys[0]); + if (ret < 0) { + printf("failed to delete key\n"); + odph_cuckoo_table_destroy(table); + return -1; + } + + ret = odph_cuckoo_table_remove_value(table, &keys[0]); + print_key_info("Del", &keys[0]); + if (ret >= 0) { + printf("error: deleted already deleted key\n"); + odph_cuckoo_table_destroy(table); + return -1; + } + + odph_cuckoo_table_destroy(table); + return 0; +} + +/* + * Sequence of operations for find existing hash table + * + * - create table + * - find existing table: hit + * - find non-existing table: miss + * + */ +static int test_table_lookup(void) +{ + odph_table_t table, result; + + /* Create cuckoo hash table. */ + table = odph_cuckoo_table_create("table_lookup", 10, 4, 0); + if (table == NULL) { + printf("failed to create table\n"); + return -1; + } + + /* Try to find existing hash table */ + result = odph_cuckoo_table_lookup("table_lookup"); + if (result != table) { + printf("error: could not find existing table\n"); + odph_cuckoo_table_destroy(table); + return -1; + } + + /* Try to find non-existing hash table */ + result = odph_cuckoo_table_lookup("non_existing"); + if (result != NULL) { + printf("error: found table that shouldn't exist.\n"); + odph_cuckoo_table_destroy(table); + return -1; + } + + /* Cleanup. */ + odph_cuckoo_table_destroy(table); + return 0; +} + +/* + * Sequence of operations for 5 keys + * - put keys + * - get keys: hit + * - remove keys : hit + * - get keys: miss + */ +static int test_five_keys(void) +{ + odph_table_t table; + unsigned i; + int ret; + + table = odph_cuckoo_table_create( + "five_keys", 10, sizeof(struct flow_key), 0); + if (table == NULL) { + printf("failed to create table\n"); + return -1; + } + + /* put */ + for (i = 0; i < 5; i++) { + ret = odph_cuckoo_table_put_value(table, &keys[i], NULL); + print_key_info("Add", &keys[i]); + if (ret < 0) { + printf("failed to add key %d\n", i); + odph_cuckoo_table_destroy(table); + return -1; + } + } + + /* get */ + for (i = 0; i < 5; i++) { + ret = odph_cuckoo_table_get_value(table, &keys[i], NULL, 0); + print_key_info("Lkp", &keys[i]); + if (ret < 0) { + printf("failed to find key %d\n", i); + odph_cuckoo_table_destroy(table); + return -1; + } + } + + /* remove */ + for (i = 0; i < 5; i++) { + ret = odph_cuckoo_table_remove_value(table, &keys[i]); + print_key_info("Del", &keys[i]); + if (ret < 0) { + printf("failed to delete key %d\n", i); + odph_cuckoo_table_destroy(table); + return -1; + } + } + + /* get */ + for (i = 0; i < 5; i++) { + ret = odph_cuckoo_table_get_value(table, &keys[i], NULL, 0); + print_key_info("Lkp", &keys[i]); + if (ret >= 0) { + printf("found non-existing key %d\n", i); + odph_cuckoo_table_destroy(table); + return -1; + } + } + + odph_cuckoo_table_destroy(table); + return 0; +} + +#define BUCKET_ENTRIES 4 +#define HASH_ENTRIES_MAX 1048576 +/* + * Do tests for cuchoo tabke creation with bad parameters. + */ +static int test_creation_with_bad_parameters(void) +{ + odph_table_t table; + + table = odph_cuckoo_table_create( + "bad_param_0", HASH_ENTRIES_MAX + 1, 4, 0); + if (table != NULL) { + odph_cuckoo_table_destroy(table); + printf("Impossible creating table successfully with entries in parameter exceeded\n"); + return -1; + } + + table = odph_cuckoo_table_create( + "bad_param_1", BUCKET_ENTRIES - 1, 4, 0); + if (table != NULL) { + odph_cuckoo_table_destroy(table); + printf("Impossible creating hash successfully if entries less than bucket_entries in parameter\n"); + return -1; + } + + table = odph_cuckoo_table_create("bad_param_2", 10, 0, 0); + if (table != NULL) { + odph_cuckoo_table_destroy(table); + printf("Impossible creating hash successfully if key_len in parameter is zero\n"); + return -1; + } + + printf("# Test successful. No more errors expected\n"); + + return 0; +} + +#define PERFORMANCE_CAPACITY 1000000 + +/* + * Test the performance of cuckoo hash table. + * table capacity : 1,000,000 + * key size : 4 bytes + * value size : 0 + * Insert at most number random keys into the table. If one + * insertion is failed, the rest insertions will be cancelled. + * The table utilization of the report will show actual number + * of items inserted. + * Then search all inserted items. + */ +static int test_performance(int number) +{ + odph_table_t table; + + /* generate random keys */ + uint8_t *key_space = NULL; + const void **key_ptr = NULL; + unsigned key_len = 4, j; + unsigned elem_num = (number > PERFORMANCE_CAPACITY) ? + PERFORMANCE_CAPACITY : number; + unsigned key_num = key_len * elem_num; + + key_space = (uint8_t *)malloc(key_num); + key_ptr = (const void **)malloc(sizeof(void *) * elem_num); + if (key_space == NULL) + return -ENOENT; + + for (j = 0; j < key_num; j++) { + key_space[j] = rand() % 255; + if (j % key_len == 0) + key_ptr[j / key_len] = &key_space[j]; + } + + unsigned num; + int ret = 0; + struct timeval start, end; + double add_time = 0; + + fflush(stdout); + table = odph_cuckoo_table_create( + "performance_test", PERFORMANCE_CAPACITY, key_len, 0); + if (table == NULL) { + printf("cuckoo table creation failed\n"); + return -ENOENT; + } + + /* insert (put) */ + gettimeofday(&start, 0); + for (j = 0; j < elem_num; j++) { + ret = odph_cuckoo_table_put_value( + table, &key_space[j * key_len], NULL); + if (ret < 0) + break; + } + gettimeofday(&end, 0); + num = j; + add_time = get_time_diff(&start, &end); + printf( + "add %u/%u (%.2f) items, time = %.9lfs\n", + num, PERFORMANCE_CAPACITY, + (double)num / PERFORMANCE_CAPACITY, add_time); + + /* search (get) */ + gettimeofday(&start, 0); + for (j = 0; j < num; j++) { + ret = odph_cuckoo_table_get_value( + table, &key_space[j * key_len], NULL, 0); + + if (ret < 0) + printf("lookup error\n"); + } + gettimeofday(&end, 0); + printf( + "lookup %u items, time = %.9lfs\n", + num, get_time_diff(&start, &end)); + + odph_cuckoo_table_destroy(table); + free(key_ptr); + free(key_space); + return ret; +} + +/* + * Do all unit and performance tests. + */ +static int +test_cuckoo_hash_table(void) +{ + if (test_put_remove() < 0) + return -1; + if (test_table_lookup() < 0) + return -1; + if (test_put_update_remove() < 0) + return -1; + if (test_five_keys() < 0) + return -1; + if (test_creation_with_bad_parameters() < 0) + return -1; + if (test_performance(950000) < 0) + return -1; + + return 0; +} + +int main(int argc TEST_UNUSED, char *argv[] TEST_UNUSED) +{ + odp_instance_t instance; + int ret = 0; + + ret = odp_init_global(&instance, NULL, NULL); + if (ret != 0) { + fprintf(stderr, "Error: ODP global init failed.\n"); + exit(EXIT_FAILURE); + } + + ret = odp_init_local(instance, ODP_THREAD_WORKER); + if (ret != 0) { + fprintf(stderr, "Error: ODP local init failed.\n"); + exit(EXIT_FAILURE); + } + + srand(time(0)); + ret = test_cuckoo_hash_table(); + + if (ret < 0) + printf("cuckoo hash table test fail!!\n"); + else + printf("All Tests pass!!\n"); + + if (odp_term_local()) { + fprintf(stderr, "Error: ODP local term failed.\n"); + exit(EXIT_FAILURE); + } + + if (odp_term_global(instance)) { + fprintf(stderr, "Error: ODP global term failed.\n"); + exit(EXIT_FAILURE); + } + + return ret; +}

commit d1e693d7177d10f382d69b659ab359fddee783b5 Author: Ru Jia jiaru@ict.ac.cn Date: Mon Jun 13 14:42:13 2016 +0800

helper: table: add impl of cuckoo hash table

Signed-off-by: Ru Jia jiaru@ict.ac.cn Reviewed-and-tested-by: Bill Fischofer bill.fischofer@linaro.org Signed-off-by: Maxim Uvarov maxim.uvarov@linaro.org

diff --git a/helper/Makefile.am b/helper/Makefile.am index aa58e8c..116a1f0 100644 --- a/helper/Makefile.am +++ b/helper/Makefile.am @@ -27,6 +27,7 @@ noinst_HEADERS = \ $(srcdir)/odph_debug.h \ $(srcdir)/odph_hashtable.h \ $(srcdir)/odph_lineartable.h \ + $(srcdir)/odph_cuckootable.h \ $(srcdir)/odph_list_internal.h

__LIB__libodphelper_linux_la_SOURCES = \ @@ -35,6 +36,7 @@ __LIB__libodphelper_linux_la_SOURCES = \ chksum.c \ linux.c \ hashtable.c \ - lineartable.c + lineartable.c \ + cuckootable.c

lib_LTLIBRARIES = $(LIB)/libodphelper-linux.la diff --git a/helper/cuckootable.c b/helper/cuckootable.c new file mode 100644 index 0000000..91a73b4 --- /dev/null +++ b/helper/cuckootable.c @@ -0,0 +1,743 @@ +/* Copyright (c) 2016, Linaro Limited + * All rights reserved. + * + * SPDX-License-Identifier: BSD-3-Clause + */ + +/*- + * BSD LICENSE + * + * Copyright(c) 2010-2016 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 <string.h> +#include <stdint.h> +#include <errno.h> +#include <stdio.h> + +#include "odph_cuckootable.h" +#include "odph_debug.h" +#include <odp_api.h> + +/* More efficient access to a map of single ullong */ +#define ULLONG_FOR_EACH_1(IDX, MAP) \ + for (; MAP && (((IDX) = __builtin_ctzll(MAP)), true); \ + MAP = (MAP & (MAP - 1))) + +/** @magic word, write to the first byte of the memory block + * to indicate this block is used by a cuckoo hash table + */ +#define ODPH_CUCKOO_TABLE_MAGIC_WORD 0xDFDFFDFD + +/** Number of items per bucket. */ +#define HASH_BUCKET_ENTRIES 4 + +#define NULL_SIGNATURE 0 +#define KEY_ALIGNMENT 16 + +/** Maximum size of hash table that can be created. */ +#define HASH_ENTRIES_MAX 1048576 + +/** @internal signature struct + * Structure storing both primary and secondary hashes + */ +struct cuckoo_table_signatures { + union { + struct { + uint32_t current; + uint32_t alt; + }; + uint64_t sig; + }; +}; + +/** @internal kay-value struct + * Structure that stores key-value pair + */ +struct cuckoo_table_key_value { + uint8_t *key; + uint8_t *value; +}; + +/** @internal bucket structure + * Put the elements with defferent keys but a same signature + * into a bucket, and each bucket has at most HASH_BUCKET_ENTRIES + * elements. + */ +struct cuckoo_table_bucket { + struct cuckoo_table_signatures signatures[HASH_BUCKET_ENTRIES]; + /* Includes dummy key index that always contains index 0 */ + odp_buffer_t key_buf[HASH_BUCKET_ENTRIES + 1]; + uint8_t flag[HASH_BUCKET_ENTRIES]; +} ODP_ALIGNED_CACHE; + +/* More efficient access to a map of single ullong */ +#define ULLONG_FOR_EACH_1(IDX, MAP) \ + for (; MAP && (((IDX) = __builtin_ctzll(MAP)), true); \ + MAP = (MAP & (MAP - 1))) + +/** A hash table structure. */ +typedef struct { + /**< for check */ + uint32_t magicword; + /**< Name of the hash. */ + char name[ODPH_TABLE_NAME_LEN]; + /**< Total table entries. */ + uint32_t entries; + /**< Number of buckets in table. */ + uint32_t num_buckets; + /**< Length of hash key. */ + uint32_t key_len; + /**< Length of value. */ + uint32_t value_len; + /**< Bitmask for getting bucket index from hash signature. */ + uint32_t bucket_bitmask; + /**< Queue that stores all free key-value slots*/ + odp_queue_t free_slots; + /** Table with buckets storing all the hash values and key indexes + to the key table*/ + struct cuckoo_table_bucket *buckets; +} odph_cuckoo_table_impl ODP_ALIGNED_CACHE; + +/** + * Aligns input parameter to the next power of 2 + * + * @param x + * The integer value to algin + * + * @return + * Input parameter aligned to the next power of 2 + */ +static inline uint32_t +align32pow2(uint32_t x) +{ + x--; + x |= x >> 1; + x |= x >> 2; + x |= x >> 4; + x |= x >> 8; + x |= x >> 16; + + return x + 1; +} + +/** + * Returns true if n is a power of 2 + * @param n + * Number to check + * @return 1 if true, 0 otherwise + */ +static inline int +is_power_of_2(uint32_t n) +{ + return n && !(n & (n - 1)); +} + +odph_table_t +odph_cuckoo_table_lookup(const char *name) +{ + odph_cuckoo_table_impl *tbl = NULL; + + if (name == NULL || strlen(name) >= ODPH_TABLE_NAME_LEN) + return NULL; + + tbl = (odph_cuckoo_table_impl *)odp_shm_addr(odp_shm_lookup(name)); + + if ( + tbl != NULL && + tbl->magicword == ODPH_CUCKOO_TABLE_MAGIC_WORD && + strcmp(tbl->name, name) == 0) + return (odph_table_t)tbl; +} + +odph_table_t +odph_cuckoo_table_create( + const char *name, uint32_t capacity, uint32_t key_size, + uint32_t value_size) +{ + odph_cuckoo_table_impl *tbl; + odp_shm_t shm_tbl; + + odp_pool_t pool; + odp_pool_param_t param; + + odp_queue_t queue; + odp_queue_param_t qparam; + + char pool_name[ODPH_TABLE_NAME_LEN + 3], + queue_name[ODPH_TABLE_NAME_LEN + 3]; + unsigned i; + uint32_t impl_size, kv_entry_size, + bucket_num, bucket_size; + + /* Check for valid parameters */ + if ( + (capacity > HASH_ENTRIES_MAX) || + (capacity < HASH_BUCKET_ENTRIES) || + (key_size == 0) || + (strlen(name) == 0)) { + ODPH_DBG("invalid parameters\n"); + return NULL; + } + + /* Guarantee there's no existing */ + tbl = (odph_cuckoo_table_impl *)odph_cuckoo_table_lookup(name); + if (tbl != NULL) { + ODPH_DBG("cuckoo hash table %s already exists\n", name); + return NULL; + } + + /* Calculate the sizes of different parts of cuckoo hash table */ + impl_size = sizeof(odph_cuckoo_table_impl); + kv_entry_size = sizeof(struct cuckoo_table_key_value) + + key_size + value_size; + + bucket_num = align32pow2(capacity) / HASH_BUCKET_ENTRIES; + bucket_size = bucket_num * sizeof(struct cuckoo_table_bucket); + + shm_tbl = odp_shm_reserve( + name, impl_size + bucket_size, + ODP_CACHE_LINE_SIZE, ODP_SHM_SW_ONLY); + + if (shm_tbl == ODP_SHM_INVALID) { + ODPH_DBG( + "shm allocation failed for odph_cuckoo_table_impl %s\n", + name); + return NULL; + } + + tbl = (odph_cuckoo_table_impl *)odp_shm_addr(shm_tbl); + memset(tbl, 0, impl_size + bucket_size); + + /* header of this mem block is the table impl struct, + * then the bucket pool. + */ + tbl->buckets = (struct cuckoo_table_bucket *)( + (char *)tbl + impl_size); + + /* initialize key-value buffer pool */ + snprintf(pool_name, sizeof(pool_name), "kv_%s", name); + pool = odp_pool_lookup(pool_name); + + if (pool != ODP_POOL_INVALID) + odp_pool_destroy(pool); + + param.type = ODP_POOL_BUFFER; + param.buf.size = kv_entry_size; + param.buf.align = ODP_CACHE_LINE_SIZE; + param.buf.num = capacity; + + pool = odp_pool_create(pool_name, &param); + + if (pool == ODP_POOL_INVALID) { + ODPH_DBG("failed to create key-value pool\n"); + odp_shm_free(shm_tbl); + return NULL; + } + + /* initialize free_slots queue */ + odp_queue_param_init(&qparam); + qparam.type = ODP_QUEUE_TYPE_PLAIN; + + snprintf(queue_name, sizeof(queue_name), "fs_%s", name); + queue = odp_queue_create(queue_name, &qparam); + if (queue == ODP_QUEUE_INVALID) { + ODPH_DBG("failed to create free_slots queue\n"); + odp_pool_destroy(pool); + odp_shm_free(shm_tbl); + return NULL; + } + + /* Setup hash context */ + snprintf(tbl->name, sizeof(tbl->name), "%s", name); + tbl->magicword = ODPH_CUCKOO_TABLE_MAGIC_WORD; + tbl->entries = capacity; + tbl->key_len = key_size; + tbl->value_len = value_size; + tbl->num_buckets = bucket_num; + tbl->bucket_bitmask = bucket_num - 1; + tbl->free_slots = queue; + + /* generate all free buffers, and put into queue */ + for (i = 0; i < capacity; i++) { + odp_event_t ev = odp_buffer_to_event( + odp_buffer_alloc(pool)); + if (ev == ODP_EVENT_INVALID) { + ODPH_DBG("failed to generate free slots\n"); + odph_cuckoo_table_destroy((odph_table_t)tbl); + return NULL; + } + + if (odp_queue_enq(queue, ev) < 0) { + ODPH_DBG("failed to enqueue free slots\n"); + odph_cuckoo_table_destroy((odph_table_t)tbl); + return NULL; + } + } + + return (odph_table_t)tbl; +} + +int +odph_cuckoo_table_destroy(odph_table_t tbl) +{ + int ret, i, j; + odph_cuckoo_table_impl *impl = NULL; + char pool_name[ODPH_TABLE_NAME_LEN + 3]; + + if (tbl == NULL) + return -1; + + impl = (odph_cuckoo_table_impl *)tbl; + + /* check magic word */ + if (impl->magicword != ODPH_CUCKOO_TABLE_MAGIC_WORD) { + ODPH_DBG("wrong magicword for cuckoo table\n"); + return -1; + } + + /* free all used buffers*/ + for (i = 0; i < impl->num_buckets; i++) { + for (j = 0; j < HASH_BUCKET_ENTRIES; j++) { + if (impl->buckets[i].signatures[j].current + != NULL_SIGNATURE) + odp_buffer_free(impl->buckets[i].key_buf[j]); + } + } + + /* free all free buffers */ + odp_event_t ev; + + while ((ev = odp_queue_deq(impl->free_slots)) + != ODP_EVENT_INVALID) { + odp_buffer_free(odp_buffer_from_event(ev)); + } + + /* destroy free_slots queue */ + ret = odp_queue_destroy(impl->free_slots); + if (ret < 0) + ODPH_DBG("failed to destroy free_slots queue\n"); + + /* destroy key-value pool */ + snprintf(pool_name, sizeof(pool_name), "kv_%s", impl->name); + ret = odp_pool_destroy(odp_pool_lookup(pool_name)); + if (ret != 0) { + ODPH_DBG("failed to destroy key-value buffer pool\n"); + return ret; + } + + /* free impl */ + odp_shm_free(odp_shm_lookup(impl->name)); +} + +static uint32_t hash(const odph_cuckoo_table_impl *h, const void *key) +{ + /* calc hash result by key */ + return odp_hash_crc32c(key, h->key_len, 0); +} + +/* Calc the secondary hash value from the primary hash value of a given key */ +static inline uint32_t +hash_secondary(const uint32_t primary_hash) +{ + static const unsigned all_bits_shift = 12; + static const unsigned alt_bits_xor = 0x5bd1e995; + + uint32_t tag = primary_hash >> all_bits_shift; + + return (primary_hash ^ ((tag + 1) * alt_bits_xor)); +} + +/* Search for an entry that can be pushed to its alternative location */ +static inline int +make_space_bucket( + const odph_cuckoo_table_impl *impl, + struct cuckoo_table_bucket *bkt) +{ + unsigned i, j; + int ret; + uint32_t next_bucket_idx; + struct cuckoo_table_bucket *next_bkt[HASH_BUCKET_ENTRIES]; + + /* + * Push existing item (search for bucket with space in + * alternative locations) to its alternative location + */ + for (i = 0; i < HASH_BUCKET_ENTRIES; i++) { + /* Search for space in alternative locations */ + next_bucket_idx = bkt->signatures[i].alt & impl->bucket_bitmask; + next_bkt[i] = &impl->buckets[next_bucket_idx]; + for (j = 0; j < HASH_BUCKET_ENTRIES; j++) { + if (next_bkt[i]->signatures[j].sig == NULL_SIGNATURE) + break; + } + + if (j != HASH_BUCKET_ENTRIES) + break; + } + + /* Alternative location has spare room (end of recursive function) */ + if (i != HASH_BUCKET_ENTRIES) { + next_bkt[i]->signatures[j].alt = bkt->signatures[i].current; + next_bkt[i]->signatures[j].current = bkt->signatures[i].alt; + next_bkt[i]->key_buf[j] = bkt->key_buf[i]; + return i; + } + + /* Pick entry that has not been pushed yet */ + for (i = 0; i < HASH_BUCKET_ENTRIES; i++) + if (bkt->flag[i] == 0) + break; + + /* All entries have been pushed, so entry cannot be added */ + if (i == HASH_BUCKET_ENTRIES) + return -ENOSPC; + + /* Set flag to indicate that this entry is going to be pushed */ + bkt->flag[i] = 1; + /* Need room in alternative bucket to insert the pushed entry */ + ret = make_space_bucket(impl, next_bkt[i]); + /* + * After recursive function. + * Clear flags and insert the pushed entry + * in its alternative location if successful, + * or return error + */ + bkt->flag[i] = 0; + if (ret >= 0) { + next_bkt[i]->signatures[ret].alt = bkt->signatures[i].current; + next_bkt[i]->signatures[ret].current = bkt->signatures[i].alt; + next_bkt[i]->key_buf[ret] = bkt->key_buf[i]; + return i; + } + + return ret; +} + +static inline int32_t +cuckoo_table_add_key_with_hash( + const odph_cuckoo_table_impl *h, const void *key, + uint32_t sig, void *data) +{ + uint32_t alt_hash; + uint32_t prim_bucket_idx, sec_bucket_idx; + unsigned i; + struct cuckoo_table_bucket *prim_bkt, *sec_bkt; + struct cuckoo_table_key_value *new_kv, *kv; + + odp_buffer_t new_buf; + int ret; + + prim_bucket_idx = sig & h->bucket_bitmask; + prim_bkt = &h->buckets[prim_bucket_idx]; + __builtin_prefetch((const void *)(uintptr_t)prim_bkt, 0, 3); + + alt_hash = hash_secondary(sig); + sec_bucket_idx = alt_hash & h->bucket_bitmask; + sec_bkt = &h->buckets[sec_bucket_idx]; + __builtin_prefetch((const void *)(uintptr_t)sec_bkt, 0, 3); + + /* Get a new slot for storing the new key */ + new_buf = odp_buffer_from_event(odp_queue_deq(h->free_slots)); + if (new_buf == ODP_BUFFER_INVALID) + return -ENOSPC; + + /* Check if key is already inserted in primary location */ + for (i = 0; i < HASH_BUCKET_ENTRIES; i++) { + if ( + prim_bkt->signatures[i].current == sig && + prim_bkt->signatures[i].alt == alt_hash) { + kv = (struct cuckoo_table_key_value *)odp_buffer_addr( + prim_bkt->key_buf[i]); + if (memcmp(key, kv->key, h->key_len) == 0) { + odp_queue_enq( + h->free_slots, + odp_buffer_to_event(new_buf)); + /* Update data */ + if (kv->value != NULL) + memcpy(kv->value, data, h->value_len); + + /* Return bucket index */ + return prim_bucket_idx; + } + } + } + + /* Check if key is already inserted in secondary location */ + for (i = 0; i < HASH_BUCKET_ENTRIES; i++) { + if ( + sec_bkt->signatures[i].alt == sig && + sec_bkt->signatures[i].current == alt_hash) { + kv = (struct cuckoo_table_key_value *)odp_buffer_addr( + sec_bkt->key_buf[i]); + if (memcmp(key, kv->key, h->key_len) == 0) { + odp_queue_enq( + h->free_slots, + odp_buffer_to_event(new_buf)); + /* Update data */ + if (kv->value != NULL) + memcpy(kv->value, data, h->value_len); + + /* Return bucket index */ + return sec_bucket_idx; + } + } + } + + new_kv = (struct cuckoo_table_key_value *)odp_buffer_addr(new_buf); + __builtin_prefetch((const void *)(uintptr_t)new_kv, 0, 3); + + /* Copy key and value. + * key-value mem block : struct cuckoo_table_key_value + * + key (key_len) + value (value_len) + */ + new_kv->key = (uint8_t *)new_kv + + sizeof(struct cuckoo_table_key_value); + memcpy(new_kv->key, key, h->key_len); + + if (h->value_len > 0) { + new_kv->value = new_kv->key + h->key_len; + memcpy(new_kv->value, data, h->value_len); + } else { + new_kv->value = NULL; + } + + /* Insert new entry is there is room in the primary bucket */ + for (i = 0; i < HASH_BUCKET_ENTRIES; i++) { + /* Check if slot is available */ + if (odp_likely(prim_bkt->signatures[i].sig == NULL_SIGNATURE)) { + prim_bkt->signatures[i].current = sig; + prim_bkt->signatures[i].alt = alt_hash; + prim_bkt->key_buf[i] = new_buf; + return prim_bucket_idx; + } + } + + /* Primary bucket is full, so we need to make space for new entry */ + ret = make_space_bucket(h, prim_bkt); + + /* + * After recursive function. + * Insert the new entry in the position of the pushed entry + * if successful or return error and + * store the new slot back in the pool + */ + if (ret >= 0) { + prim_bkt->signatures[ret].current = sig; + prim_bkt->signatures[ret].alt = alt_hash; + prim_bkt->key_buf[ret] = new_buf; + return prim_bucket_idx; + } + + /* Error in addition, store new slot back in the free_slots */ + odp_queue_enq(h->free_slots, odp_buffer_to_event(new_buf)); + return ret; +} + +int +odph_cuckoo_table_put_value(odph_table_t tbl, void *key, void *value) +{ + if ((tbl == NULL) || (key == NULL)) + return -EINVAL; + + odph_cuckoo_table_impl *impl = (odph_cuckoo_table_impl *)tbl; + int ret = cuckoo_table_add_key_with_hash( + impl, key, hash(impl, key), value); + + if (ret < 0) + return -1; + + return 0; +} + +static inline int32_t +cuckoo_table_lookup_with_hash( + const odph_cuckoo_table_impl *h, const void *key, + uint32_t sig, void **data_ptr) +{ + uint32_t bucket_idx; + uint32_t alt_hash; + unsigned i; + struct cuckoo_table_bucket *bkt; + struct cuckoo_table_key_value *kv; + + bucket_idx = sig & h->bucket_bitmask; + bkt = &h->buckets[bucket_idx]; + + /* Check if key is in primary location */ + for (i = 0; i < HASH_BUCKET_ENTRIES; i++) { + if ( + bkt->signatures[i].current == sig && + bkt->signatures[i].sig != NULL_SIGNATURE) { + kv = (struct cuckoo_table_key_value *)odp_buffer_addr( + bkt->key_buf[i]); + if (memcmp(key, kv->key, h->key_len) == 0) { + if (data_ptr != NULL) + *data_ptr = kv->value; + /* + * Return index where key is stored, + * subtracting the first dummy index + */ + return bucket_idx; + } + } + } + + /* Calculate secondary hash */ + alt_hash = hash_secondary(sig); + bucket_idx = alt_hash & h->bucket_bitmask; + bkt = &h->buckets[bucket_idx]; + + /* Check if key is in secondary location */ + for (i = 0; i < HASH_BUCKET_ENTRIES; i++) { + if ( + bkt->signatures[i].current == alt_hash && + bkt->signatures[i].alt == sig) { + kv = (struct cuckoo_table_key_value *)odp_buffer_addr( + bkt->key_buf[i]); + if (memcmp(key, kv->key, h->key_len) == 0) { + if (data_ptr != NULL) + *data_ptr = kv->value; + /* + * Return index where key is stored, + * subtracting the first dummy index + */ + return bucket_idx; + } + } + } + + return -ENOENT; +} + +int +odph_cuckoo_table_get_value( + odph_table_t tbl, void *key, void *buffer, uint32_t buffer_size) +{ + if ((tbl == NULL) || (key == NULL)) + return -EINVAL; + + odph_cuckoo_table_impl *impl = (odph_cuckoo_table_impl *)tbl; + void *tmp = NULL; + int ret; + + ret = cuckoo_table_lookup_with_hash(impl, key, hash(impl, key), &tmp); + + if (ret < 0) + return -1; + + if (impl->value_len > 0) + memcpy(buffer, tmp, impl->value_len); + + return 0; +} + +static inline int32_t +cuckoo_table_del_key_with_hash( + const odph_cuckoo_table_impl *h, + const void *key, uint32_t sig) +{ + uint32_t bucket_idx; + uint32_t alt_hash; + unsigned i; + struct cuckoo_table_bucket *bkt; + struct cuckoo_table_key_value *kv; + + bucket_idx = sig & h->bucket_bitmask; + bkt = &h->buckets[bucket_idx]; + + /* Check if key is in primary location */ + for (i = 0; i < HASH_BUCKET_ENTRIES; i++) { + if ( + bkt->signatures[i].current == sig && + bkt->signatures[i].sig != NULL_SIGNATURE) { + kv = (struct cuckoo_table_key_value *)odp_buffer_addr( + bkt->key_buf[i]); + if (memcmp(key, kv->key, h->key_len) == 0) { + bkt->signatures[i].sig = NULL_SIGNATURE; + odp_queue_enq( + h->free_slots, + odp_buffer_to_event( + bkt->key_buf[i])); + return bucket_idx; + } + } + } + + /* Calculate secondary hash */ + alt_hash = hash_secondary(sig); + bucket_idx = alt_hash & h->bucket_bitmask; + bkt = &h->buckets[bucket_idx]; + + /* Check if key is in secondary location */ + for (i = 0; i < HASH_BUCKET_ENTRIES; i++) { + if ( + bkt->signatures[i].current == alt_hash && + bkt->signatures[i].sig != NULL_SIGNATURE) { + kv = (struct cuckoo_table_key_value *)odp_buffer_addr( + bkt->key_buf[i]); + if (memcmp(key, kv->key, h->key_len) == 0) { + bkt->signatures[i].sig = NULL_SIGNATURE; + odp_queue_enq( + h->free_slots, + odp_buffer_to_event( + bkt->key_buf[i])); + return bucket_idx; + } + } + } + + return -ENOENT; +} + +int +odph_cuckoo_table_remove_value(odph_table_t tbl, void *key) +{ + if ((tbl == NULL) || (key == NULL)) + return -EINVAL; + + odph_cuckoo_table_impl *impl = (odph_cuckoo_table_impl *)tbl; + int ret = cuckoo_table_del_key_with_hash( + impl, key, hash(impl, key)); + + if (ret < 0) + return -1; + + return 0; +} + +odph_table_ops_t odph_cuckoo_table_ops = { + odph_cuckoo_table_create, + odph_cuckoo_table_lookup, + odph_cuckoo_table_destroy, + odph_cuckoo_table_put_value, + odph_cuckoo_table_get_value, + odph_cuckoo_table_remove_value +}; diff --git a/helper/odph_cuckootable.h b/helper/odph_cuckootable.h new file mode 100644 index 0000000..d569980 --- /dev/null +++ b/helper/odph_cuckootable.h @@ -0,0 +1,82 @@ +/* Copyright (c) 2016, Linaro Limited + * All rights reserved. + * + * SPDX-License-Identifier: BSD-3-Clause + */ + +/*- + * BSD LICENSE + * + * Copyright(c) 2010-2016 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. + */ + +#ifndef ODPH_CUCKOO_TABLE_H_ +#define ODPH_CUCKOO_TABLE_H_ + +#include <odp/helper/table.h> + +/** + * @file + * + * ODP Cuckoo Hash Table + */ + +#ifdef __cplusplus +extern "C" { +#endif + +odph_table_t odph_cuckoo_table_create( + const char *name, + uint32_t capacity, + uint32_t key_size, + uint32_t value_size); + +odph_table_t odph_cuckoo_table_lookup(const char *name); + +int odph_cuckoo_table_destroy(odph_table_t table); + +int odph_cuckoo_table_put_value( + odph_table_t table, + void *key, void *value); + +int odph_cuckoo_table_get_value( + odph_table_t table, + void *key, void *buffer, + uint32_t buffer_size); + +int odph_cuckoo_table_remove_value(odph_table_t table, void *key); + +extern odph_table_ops_t odph_cuckoo_table_ops; + +#ifdef __cplusplus +} +#endif + +#endif /* ODPH_CUCKOO_TABLE_H_ */

-----------------------------------------------------------------------

Summary of changes: helper/Makefile.am | 4 +- helper/cuckootable.c | 743 ++++++++++++++++++++++++++++++++++++++++++++++ helper/odph_cuckootable.h | 82 +++++ helper/test/.gitignore | 1 + helper/test/Makefile.am | 6 +- helper/test/cuckootable.c | 573 +++++++++++++++++++++++++++++++++++ 6 files changed, 1406 insertions(+), 3 deletions(-) create mode 100644 helper/cuckootable.c create mode 100644 helper/odph_cuckootable.h create mode 100644 helper/test/cuckootable.c

hooks/post-receive