Perhaps a generic hash table APIs (not cuckoo hash) could be put in the main APIs?
> 在 2016年4月6日，下午10:18，Ru Jia <ji...@ict.ac.cn> 写道： > > Last year, there was a discussion about cuckoo hash. I saw the last reply > (https://lists.linaro.org/pipermail/lng-odp/2015-December/017921.html > <https://lists.linaro.org/pipermail/lng-odp/2015-December/017921.html>). > > You recommended to: > “ > 1) have this code with queues api; > 2) remove ring code completely from helper > 3) move ring code inside linux-generic (I will reuse it for shm pktio ipc); > 4) test performance of cuckoo hash > 5) move it to odp hash API when it will be ready (to do that code should > not use other helper code, just native odp apis). > ” > > Now I find a ring structure in platform/linux-generic/pktio, so I use it to > implement cuckoo hash. Then as the 5th point, I put it into odp apis. > > So, where should cuckoo hash be? > > And if it’s need to move cuckoo hash into helper, do I need to use odp_queue > to implement it? > 发件人: Mike Holmes [mailto:mike.hol...@linaro.org] > 发送时间: 2016年4月6日 19:43 > 收件人: Ru Jia > 抄送: lng-odp; hep...@ict.ac.cn > 主题: Re: [lng-odp] [API-NEXT PATCH 1/3] api: add cuckoo hash api > > Thank you for the patch > > Remember that if there is a new API added we also need good validation test > coverage in test/validation for it to be accepted eventually into master. > > The performance test is a really good thing to have but we need a cunit test > case to help platforms ensure that they all operate the same way for a given > release. > > Is there a reason this is not a helper rather than an odp API like the other > hashtable support, can this be HW accelerated ? > > > Mike > > On 6 April 2016 at 06:02, Ru Jia <ji...@ict.ac.cn <mailto:ji...@ict.ac.cn>> > wrote: >> Added cuckoo hash api, which is an efficient hash table. It could >> be used for many algorithms. >> >> Signed-off-by: Ru Jia <ji...@ict.ac.cn <mailto:ji...@ict.ac.cn>> >> --- >> include/odp/api/spec/cuckoo_hash.h | 463 >> +++++++++++++++++++++ >> include/odp_api.h | 1 + >> .../linux-generic/include/odp/api/cuckoo_hash.h | 34 ++ >> 3 files changed, 498 insertions(+) >> create mode 100644 include/odp/api/spec/cuckoo_hash.h >> create mode 100644 platform/linux-generic/include/odp/api/cuckoo_hash.h >> >> diff --git a/include/odp/api/spec/cuckoo_hash.h >> b/include/odp/api/spec/cuckoo_hash.h >> new file mode 100644 >> index 0000000..ca147ce >> --- /dev/null >> +++ b/include/odp/api/spec/cuckoo_hash.h >> @@ -0,0 +1,463 @@ >> +/* Copyright (c) 2015, Linaro Limited >> + * All rights reserved. >> + * >> + * SPDX-License-Identifier: BSD-3-Clause >> + */ >> + >> +/*- >> + * 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. >> + */ >> + >> +#ifndef ODP_API_CUCKOO_HASH_H_ >> +#define ODP_API_CUCKOO_HASH_H_ >> + >> +#include <odp/api/shared_memory.h> >> +#include <odp/api/hash.h> >> +#include <odp/api/align.h> >> +#include <odp/api/std_types.h> >> + >> +/** >> + * @file >> + * >> + * ODP Cuckoo Hash Table Implementation >> + */ >> + >> +#ifdef __cplusplus >> +extern "C" { >> +#endif >> + >> +/** Maximum number of characters in hash name.*/ >> +#define ODP_CUCKOO_HASH_NAMESIZE 32 >> + >> +/* 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))) >> + >> +typedef struct _ring _ring_t; >> + >> +/** >> + * @typedef odp_hash_function >> + * odp hash function >> + */ >> +typedef uint32_t (*odp_cuckoo_hash_func_t)( >> + const void *key, uint32_t data_len, >> + uint32_t init_val); >> + >> +/** >> + * @typedef odp_hash_cmp_eq_t >> + * odp hash compare function >> + */ >> +typedef int (*odp_cuckoo_hash_cmp_eq_t)( >> + const void *key1, >> + const void *key2, size_t data_len); >> + >> +/** A hash table structure. */ >> +typedef struct odp_cuckoo_hash_tbl { >> + /**< Name of the hash. */ >> + char name[ODP_CUCKOO_HASH_NAMESIZE]; >> + /**< Total table entries. */ >> + uint32_t entries; >> + /**< Number of buckets in table. */ >> + uint32_t num_buckets; >> + /**< Length of hash key. */ >> + uint32_t key_len; >> + /**< Function used by hash_func */ >> + odp_cuckoo_hash_func_t hash_func; >> + /**< Init value used by hash_func. */ >> + uint32_t hash_func_init_val; >> + /**< Function used to compare keys. */ >> + odp_cuckoo_hash_cmp_eq_t hash_cmp_eq; >> + /**< Bitmask for getting bucket index from hash signature. */ >> + uint32_t bucket_bitmask; >> + /**< Size of each key entry. */ >> + uint32_t key_entry_size; >> + /**< Ring that stores all indexes of the free slots in the key table >> */ >> + _ring_t *free_slots; >> + /**< Table storing all keys and data */ >> + void *key_store; >> + /** Table with buckets storing all the hash values and key indexes >> + to the key table*/ >> + struct cuckoo_hash_bucket *buckets; >> + /** memory used to store keys*/ >> + odp_shm_t shm_key; >> + /** memory used to store buckets*/ >> + odp_shm_t shm_bucket; >> +} odp_cuckoo_hash_tbl_t ODP_ALIGNED_CACHE; >> + >> +/** >> + * Parameters used when creating the cuckoo hash table. >> + */ >> +typedef struct odp_cuckoo_hash_param { >> + /**< Name of the hash table. */ >> + const char *name; >> + /**< Total hash table entries. */ >> + uint32_t entries; >> + /**< Length of hash key. */ >> + uint32_t key_len; >> + /**< Primary Hash function used to calculate hash. */ >> + odp_cuckoo_hash_func_t hash_func; >> + /**< Init value used by hash_func. */ >> + uint32_t hash_func_init_val; >> + /**< Indicate if additional parameters are present. */ >> + uint8_t extra_flag; >> +} odp_cuckoo_hash_param_t; >> + >> +/** >> + * Create a new cuckoo hash table. >> + * >> + * @param ht >> + * hash table if successful >> + * @param params >> + * Parameters used to create and initialise the hash table. >> + * @return >> + * 0 on success >> + * negative value on errors including: >> + * - -EINVAL - invalid parameter passed to function >> + * - -EEXIST - a hash table with the same name already exists >> + * - -ENOMEM - no appropriate memory area found in which to create >> memzone >> + */ >> +int >> +odp_cuckoo_hash_create( >> + odp_cuckoo_hash_tbl_t **ht, >> + const odp_cuckoo_hash_param_t *params); >> + >> +/** >> + * Find an existing hash table object and return a pointer to it. >> + * >> + * @param name >> + * Name of the hash table as passed to odp_hash_create() >> + * @return >> + * Pointer to hash table or NULL if object not found >> + */ >> +odp_cuckoo_hash_tbl_t * >> +odp_cuckoo_hash_find_existing(const char *name); >> + >> +/** >> + * De-allocate all memory used by hash table. >> + * @param h >> + * Hash table to free >> + */ >> +void >> +odp_cuckoo_hash_destroy(odp_cuckoo_hash_tbl_t *h); >> + >> +/** >> + * Reset all hash structure, by zeroing all entries >> + * @param h >> + * Hash table to reset >> + */ >> +void >> +odp_cuckoo_hash_reset(odp_cuckoo_hash_tbl_t *h); >> + >> +/** >> + * Add a key-value pair to an existing hash table. >> + * This operation is not multi-thread safe >> + * and should only be called from one thread. >> + * >> + * @param h >> + * Hash table to add the key to. >> + * @param key >> + * Key to add to the hash table. >> + * @param data >> + * Data to add to the hash table. >> + * @return >> + * - 0 if added successfully >> + * - -EINVAL if the parameters are invalid. >> + * - -ENOSPC if there is no space in the hash for this key. >> + */ >> +int >> +odp_cuckoo_hash_add_key_data( >> + const odp_cuckoo_hash_tbl_t *h, >> + const void *key, void *data); >> + >> +/** >> + * Add a key-value pair with a pre-computed hash value >> + * to an existing hash table. >> + * This operation is not multi-thread safe >> + * and should only be called from one thread. >> + * >> + * @param h >> + * Hash table to add the key to. >> + * @param key >> + * Key to add to the hash table. >> + * @param sig >> + * Precomputed hash value for 'key' >> + * @param data >> + * Data to add to the hash table. >> + * @return >> + * - 0 if added successfully >> + * - -EINVAL if the parameters are invalid. >> + * - -ENOSPC if there is no space in the hash for this key. >> + */ >> +int32_t >> +odp_cuckoo_hash_add_key_with_hash_data( >> + const odp_cuckoo_hash_tbl_t *h, const void *key, >> + uint32_t sig, void *data); >> + >> +/** >> + * Add a key to an existing hash table. This operation is not multi-thread >> + * safe and should only be called from one thread. >> + * >> + * @param h >> + * Hash table to add the key to. >> + * @param key >> + * Key to add to the hash table. >> + * @return >> + * - -EINVAL if the parameters are invalid. >> + * - -ENOSPC if there is no space in the hash for this key. >> + * - A positive value that can be used by the caller as an offset into an >> + * array of user data. This value is unique for this key. >> + */ >> +int32_t >> +odp_cuckoo_hash_add_key(const odp_cuckoo_hash_tbl_t *h, const void *key); >> + >> +/** >> + * Add a key to an existing hash table. >> + * This operation is not multi-thread safe >> + * and should only be called from one thread. >> + * >> + * @param h >> + * Hash table to add the key to. >> + * @param key >> + * Key to add to the hash table. >> + * @param sig >> + * Precomputed hash value for 'key'. >> + * @return >> + * - -EINVAL if the parameters are invalid. >> + * - -ENOSPC if there is no space in the hash for this key. >> + * - A positive value that can be used by the caller as an offset into an >> + * array of user data. This value is unique for this key. >> + */ >> +int32_t >> +odp_cuckoo_hash_add_key_with_hash( >> + const odp_cuckoo_hash_tbl_t *h, >> + const void *key, uint32_t sig); >> + >> +/** >> + * Remove a key from an existing hash table. >> + * This operation is not multi-thread safe >> + * and should only be called from one thread. >> + * >> + * @param h >> + * Hash table to remove the key from. >> + * @param key >> + * Key to remove from the hash table. >> + * @return >> + * - -EINVAL if the parameters are invalid. >> + * - -ENOENT if the key is not found. >> + * - A positive value that can be used by the caller as an offset into an >> + * array of user data. This value is unique for this key, and is the >> same >> + * value that was returned when the key was added. >> + */ >> +int32_t >> +odp_cuckoo_hash_del_key( >> + const odp_cuckoo_hash_tbl_t *h, const void *key); >> + >> +/** >> + * Remove a key from an existing hash table. >> + * This operation is not multi-thread safe >> + * and should only be called from one thread. >> + * >> + * @param h >> + * Hash table to remove the key from. >> + * @param key >> + * Key to remove from the hash table. >> + * @param sig >> + * Precomputed hash value for 'key'. >> + * @return >> + * - -EINVAL if the parameters are invalid. >> + * - -ENOENT if the key is not found. >> + * - A positive value that can be used by the caller as an offset into an >> + * array of user data. This value is unique for this key, and is the >> same >> + * value that was returned when the key was added. >> + */ >> +int32_t >> +odp_cuckoo_hash_del_key_with_hash( >> + const odp_cuckoo_hash_tbl_t *h, const void *key, uint32_t sig); >> + >> +/** >> + * Find a key-value pair in the hash table. >> + * This operation is multi-thread safe. >> + * >> + * @param h >> + * Hash table to look in. >> + * @param key >> + * Key to find. >> + * @param data >> + * Output with pointer to data returned from the hash table. >> + * @return >> + * 0 if successful lookup >> + * - EINVAL if the parameters are invalid. >> + * - ENOENT if the key is not found. >> + */ >> +int >> +odp_cukoo_hash_lookup_data( >> + const odp_cuckoo_hash_tbl_t *h, >> + const void *key, void **data); >> + >> +/** >> + * Find a key-value pair with a pre-computed hash value >> + * to an existing hash table. >> + * This operation is multi-thread safe. >> + * >> + * @param h >> + * Hash table to look in. >> + * @param key >> + * Key to find. >> + * @param sig >> + * Precomputed hash value for 'key' >> + * @param data >> + * Output with pointer to data returned from the hash table. >> + * @return >> + * 0 if successful lookup >> + * - EINVAL if the parameters are invalid. >> + * - ENOENT if the key is not found. >> + */ >> +int >> +odp_cuckoo_hash_lookup_with_hash_data( >> + const odp_cuckoo_hash_tbl_t *h, const void *key, >> + uint32_t sig, void **data); >> + >> +/** >> + * Find a key in the hash table. >> + * This operation is multi-thread safe. >> + * >> + * @param h >> + * Hash table to look in. >> + * @param key >> + * Key to find. >> + * @return >> + * - -EINVAL if the parameters are invalid. >> + * - -ENOENT if the key is not found. >> + * - A positive value that can be used by the caller as an offset into an >> + * array of user data. This value is unique for this key, and is the >> same >> + * value that was returned when the key was added. >> + */ >> +int32_t >> +odp_cuckoo_hash_lookup(const odp_cuckoo_hash_tbl_t *h, const void *key); >> + >> +/** >> + * Find a key in the hash table. >> + * This operation is multi-thread safe. >> + * >> + * @param h >> + * Hash table to look in. >> + * @param key >> + * Key to find. >> + * @param sig >> + * Hash value to remove from the hash table. >> + * @return >> + * - -EINVAL if the parameters are invalid. >> + * - -ENOENT if the key is not found. >> + * - A positive value that can be used by the caller as an offset into an >> + * array of user data. This value is unique for this key, and is the >> same >> + * value that was returned when the key was added. >> + */ >> +int32_t >> +odp_cuckoo_hash_lookup_with_hash( >> + const odp_cuckoo_hash_tbl_t *h, const void *key, uint32_t sig); >> + >> +/** >> + * Find multiple keys in the hash table. >> + * This operation is multi-thread safe. >> + * >> + * @param h >> + * Hash table to look in. >> + * @param keys >> + * A pointer to a list of keys to look for. >> + * @param num_keys >> + * How many keys are in the keys list (less than >> odp_HASH_LOOKUP_BULK_MAX). >> + * @param hit_mask >> + * Output containing a bitmask with all successful lookups. >> + * @param data >> + * Output containing array of data returned from all the successful >> lookups. >> + * @return >> + * -EINVAL if there's an error, otherwise number of successful lookups. >> + */ >> +int >> +odp_cuckoo_hash_lookup_bulk_data( >> + const odp_cuckoo_hash_tbl_t *h, const void **keys, >> + uint32_t num_keys, uint64_t *hit_mask, void *data[]); >> + >> +/** >> + * Find multiple keys in the hash table. >> + * This operation is multi-thread safe. >> + * >> + * @param h >> + * Hash table to look in. >> + * @param keys >> + * A pointer to a list of keys to look for. >> + * @param num_keys >> + * How many keys are in the keys list (less than HASH_LOOKUP_BULK_MAX). >> + * @param positions >> + * Output containing a list of values, corresponding to the list of keys >> that >> + * can be used by the caller as an offset into an array of user data. >> These >> + * values are unique for each key, and are the same values that were >> returned >> + * when each key was added. If a key in the list was not found, then >> -ENOENT >> + * will be the value. >> + * @return >> + * -EINVAL if there's an error, otherwise 0. >> + */ >> +int >> +odp_cuckoo_hash_lookup_bulk( >> + const odp_cuckoo_hash_tbl_t *h, const void **keys, >> + uint32_t num_keys, int32_t *positions); >> + >> +/** >> + * Iterate through the hash table, returning key-value pairs. >> + * >> + * @param h >> + * Hash table to iterate >> + * @param key >> + * Output containing the key where current iterator >> + * was pointing at >> + * @param data >> + * Output containing the data associated with key. >> + * Returns NULL if data was not stored. >> + * @param next >> + * Pointer to iterator. Should be 0 to start iterating the hash table. >> + * Iterator is incremented after each call of this function. >> + * @return >> + * Position where key was stored, if successful. >> + * - -EINVAL if the parameters are invalid. >> + * - -ENOENT if end of the hash table. >> + */ >> +int32_t >> +odp_cuckoo_hash_iterate( >> + const odp_cuckoo_hash_tbl_t *h, >> + const void **key, void **data, uint32_t *next); >> + >> +#ifdef __cplusplus >> +} >> +#endif >> + >> +#endif /* ODP_API_HASH_H_ */ >> diff --git a/include/odp_api.h b/include/odp_api.h >> index 44b67ee..721c852 100644 >> --- a/include/odp_api.h >> +++ b/include/odp_api.h >> @@ -59,6 +59,7 @@ extern "C" { >> #include <odp/api/spinlock_recursive.h> >> #include <odp/api/rwlock_recursive.h> >> #include <odp/api/std_clib.h> >> +#include <odp/api/cuckoo_hash.h> >> >> #ifdef __cplusplus >> } >> diff --git a/platform/linux-generic/include/odp/api/cuckoo_hash.h >> b/platform/linux-generic/include/odp/api/cuckoo_hash.h >> new file mode 100644 >> index 0000000..b4dfd78 >> --- /dev/null >> +++ b/platform/linux-generic/include/odp/api/cuckoo_hash.h >> @@ -0,0 +1,34 @@ >> +/* Copyright (c) 2015, Linaro Limited >> + * All rights reserved. >> + * >> + * SPDX-License-Identifier: BSD-3-Clause >> + */ >> + >> +/** >> + * @file >> + * >> + * ODP Cuckoo Hash Table >> + */ >> + >> +#ifndef ODP_PLAT_CUCKOO_HASH_H_ >> +#define ODP_PLAT_CUCKOO_HASH_H_ >> + >> +#ifdef __cplusplus >> +extern "C" { >> +#endif >> + >> +/** @ingroup odp_cuckoo_hash >> + * @{ >> + */ >> + >> +/** >> + * @} >> + */ >> + >> +#include <odp/api/spec/cuckoo_hash.h> >> + >> +#ifdef __cplusplus >> +} >> +#endif >> + >> +#endif >> -- >> 1.9.1 >> >> >> _______________________________________________ >> lng-odp mailing list >> lng-odp@lists.linaro.org <mailto:lng-odp@lists.linaro.org> >> https://lists.linaro.org/mailman/listinfo/lng-odp >> <https://lists.linaro.org/mailman/listinfo/lng-odp> > > > > -- > Mike Holmes > Technical Manager - Linaro Networking Group > Linaro.org <http://www.linaro.org/> │ Open source software for ARM SoCs > "Work should be fun and collaborative, the rest follows" > > _______________________________________________ > lng-odp mailing list > lng-odp@lists.linaro.org > https://lists.linaro.org/mailman/listinfo/lng-odp
_______________________________________________ lng-odp mailing list lng-odp@lists.linaro.org https://lists.linaro.org/mailman/listinfo/lng-odp
