My point is only that a hash API stands by itself, as would a CRC API. On Fri, Oct 16, 2015 at 9:26 AM, HePeng <xnhp0...@icloud.com> wrote:
> > 在 2015年10月16日，下午8:44，Bill Fischofer <bill.fischo...@linaro.org> 写道： > > Barry has done some recent work on hash functions and it seems that AES > provides a much better distribution than CRC, and with very good > performance on those platforms that have AES instructions. > > > I do not see your point. Do you mean that it is not necessary to have CRC > as an ODP API? > I think Barry’s work can be useful to choose which hash function as a > default one, but > does it mean that we do not need a CRC API in ODP? All in all, we may need > CRC as a > sort of check code. > > Perhaps it is better to have a general hash function API? > > > > > On Thu, Oct 15, 2015 at 9:59 PM, HePeng <xnhp0...@icloud.com> wrote: > >> >> 在 2015年10月16日，上午4:19，Ola Liljedahl <ola.liljed...@linaro.org> 写道： >> >> >> >> On 12 October 2015 at 16:30, Maxim Uvarov <maxim.uva...@linaro.org> >> wrote: >> >>> On 10/09/2015 16:27, HePeng wrote: >>> >>>> >>>> 在 2015年10月9日，下午8:20，Maxim Uvarov <maxim.uva...@linaro.org<mailto: >>>>> maxim.uva...@linaro.org>> 写道： >>>>> >>>>> Please specify git commit hash related to original code. >>>>> >>>>> I'm thinking how to maintain that in future. And looks like there >>>>> will be no way other then walk over all new patches >>>>> and modify them to our odp code. In that case reference to original >>>>> git base will be helpful. >>>>> >>>>> Thank you, >>>>> Maxim. >>>>> >>>> >>>> Rujiacs is my colleague. She has proposed in total 5 patches for hash >>>> table implementations (imported from DPDK): >>>> >>>> [5/5] Add test program for hash lib >>>> [4/5] Add four byte key hash table >>>> [3/5] Add cuckoo hash table >>>> [2/5] Modify the Ring structure >>>> [1/5] Add Jhash and CRC functions >>>> >>>> The 5 patches are currently all in the helper/ directory (they are not >>>> APIs). >>>> >>>> All these patches have been discussed and reviewed (except 2/5, however >>>> it has been already used by some one. I’ve seen it in the mail list). >>>> Here is the outcome of the discussions: >>>> >>>> For hash table implementations, the reviews focus on the convention >>>> differences between DPDK and ODP. >>>> For hash functions, some people think that CRC should be put in the >>>> odp/include as a public API. >>>> I am a little bit confused with what to do next. >>>> Maybe going back to firstly add the hash functions and then merging the >>>> hash table implementations can make all these patches clear? >>>> >>>> >>>> The first step includes: >>>> >>>> 1) add a generic hash APIs into API-NEXT branches ( in include/odp) >>>> >>>> 2) add CRC hash APIs into the API-NEXT branches ( in include/odp), >>>> and put SW implementations in the linux-generic. CRC is special since >>>> many >>>> cpus have CRC accelerated instructions. >>>> >>>> 2) add Jhash implementations in helper/ >>>> >>>> Then, >>>> >>>> 1) add 2 hash tables implementations in helper/ >>>> >>>> >>>> How about this ? >>>> Thanks. >>>> >>> >>> Hello He, >>> >>> we discussed today on meeting that. That is good steps to go. 1) crc odp >>> api + it's linux-generic implementation 2) jhash for helper. >>> >>> For crc you can use simple crc(void *ptr, size_t len) for first version. >>> I.e. do not take care about packet segmentation, and later >>> we will switch it to segmented version crc(odp_packet_t pkt). >>> >> I doubt you want to compute the CRC over all of the data in a packet, >> selected pieces of the actual payload seems more realistic. As usual, we >> need an actual use case to drive the API definition >> >> >> Hi Ola, >> CRC can be used as a hash function as well as to verify the packet >> payload. A well-known usage is to re-calculate the crc code after TTL minus >> 1. However, modern network card or network processor usually has built-in >> hardware logic that can re-calculate crc automatically. In my opinion, crc >> is more likely being used as a hash function in many dataplane programs. >> >> >> >> >> >>> >>> Thanks, >>> Maxim. >>> >>> >>> >>> >>>> >>>>> >>>>> On 10/09/15 11:37, HePeng wrote: >>>>> >>>>>> >>>>>> 在 2015年10月9日，下午4:36，Ola Liljedahl <ola.liljed...@linaro.org<mailto: >>>>>>> ola.liljed...@linaro.org><mailto:ola.liljed...@linaro.org>> 写道： >>>>>>> >>>>>>> On 9 October 2015 at 10:33, HePeng <xnhp0...@icloud.com<mailto: >>>>>>> xnhp0...@icloud.com><mailto:xnhp0...@icloud.com>> wrote: >>>>>>> >>>>>>> >>>>>>> 在 2015年10月9日，下午4:26，Ola Liljedahl >>>>>>>> <ola.liljed...@linaro.org <mailto:ola.liljed...@linaro.org> >>>>>>>> <mailto:ola.liljed...@linaro.org>> 写道： >>>>>>>> >>>>>>>> On 8 October 2015 at 14:43, HePeng <xnhp0...@icloud.com<mailto: >>>>>>>> xnhp0...@icloud.com> >>>>>>>> <mailto:xnhp0...@icloud.com>> wrote: >>>>>>>> >>>>>>>> >>>>>>>> 在 2015年10月8日，下午8:13，Ola Liljedahl >>>>>>>>> <ola.liljed...@linaro.org <mailto:ola.liljed...@linaro.org> >>>>>>>>> <mailto:ola.liljed...@linaro.org>> 写道： >>>>>>>>> >>>>>>>>> On 8 October 2015 at 10:02, Bill Fischofer >>>>>>>>> <bill.fischo...@linaro.org <mailto: >>>>>>>>> bill.fischo...@linaro.org> >>>>>>>>> <mailto:bill.fischo...@linaro.org>> wrote: >>>>>>>>> >>>>>>>>> Trying to keep the rte_ prefix would be confusing. One >>>>>>>>> of the precepts of ODP is that it doesn't preclude an >>>>>>>>> application also using an underlying SDK in addition to >>>>>>>>> ODP APIs. Whether that makes sense is up to the >>>>>>>>> application, of course. But if ODP were to start using >>>>>>>>> other prefixes I'd imagine that would get very messy. >>>>>>>>> >>>>>>>>> It would also be confusing to have functions that use odp_ >>>>>>>>> naming conventions but don't behave like ODP functions >>>>>>>>> (with regards to e.g. handling and returning errors or >>>>>>>>> checking parameters). >>>>>>>>> >>>>>>>> We can fix this by wrapping these functions. >>>>>>>> >>>>>>>> I don't follow you. How can you make these function behave like >>>>>>>> ODP functions by "wrapping" them? >>>>>>>> Me thinks you have to modify the implementation in order to >>>>>>>> change the behaviour. >>>>>>>> >>>>>>> >>>>>>> I mean that perhaps not all the functions needs to be changed, >>>>>>> only the exposed ones (APIs). Some functions are static and are >>>>>>> only used in >>>>>>> the internal of implementation, these functions can reserve their >>>>>>> code. >>>>>>> >>>>>>> Static functions can have whatever names you like. But if their >>>>>>> implementation contributes to the behaviour as seen by callers of the >>>>>>> public functions, that behaviour must be compliant with the ODP style. >>>>>>> >>>>>> >>>>>> I see. Thanks. >>>>>> >>>>>> >>>>>> >>>>>>> >>>>>>>> But considering that the internal code is already ready, I >>>>>>>> am thinking reserve the code of *static* functions (internal >>>>>>>> implementations)? >>>>>>>> >>>>>>>> >>>>>>>> >>>>>>>> >>>>>>>>> So if we rename code imported from e.g. DPDK, we should >>>>>>>>> also convert it to behave like proper ODP functions. That >>>>>>>>> we can base the implementation on preexisting code is just >>>>>>>>> incidental and should not affect how the code behaves. >>>>>>>>> >>>>>>>>> >>>>>>>>> On Wednesday, October 7, 2015, Ola Liljedahl >>>>>>>>> <ola.liljed...@linaro.org <mailto: >>>>>>>>> ola.liljed...@linaro.org> >>>>>>>>> <mailto:ola.liljed...@linaro.org>> wrote: >>>>>>>>> >>>>>>>>> On 23 September 2015 at 19:51, Maxim Uvarov >>>>>>>>> <maxim.uva...@linaro.org <mailto: >>>>>>>>> maxim.uva...@linaro.org>> wrote: >>>>>>>>> >>>>>>>>> >>>>>>>>> >>>>>>>>> On 09/20/15 07:04, rujiacs wrote: >>>>>>>>> >>>>>>>>> Signed-off-by: rujiacs <ruji...@163.com >>>>>>>>> <mailto:ruji...@163.com>> >>>>>>>>> --- >>>>>>>>> helper/hash_fbk.c | 179 ++++++++++++++++ >>>>>>>>> helper/include/odp/helper/hash_fbk.h | 404 >>>>>>>>> +++++++++++++++++++++++++++++++++++ >>>>>>>>> 2 files changed, 583 insertions(+) >>>>>>>>> create mode 100644 helper/hash_fbk.c >>>>>>>>> create mode 100644 >>>>>>>>> helper/include/odp/helper/hash_fbk.h >>>>>>>>> >>>>>>>>> diff --git a/helper/hash_fbk.c >>>>>>>>> b/helper/hash_fbk.c >>>>>>>>> new file mode 100644 >>>>>>>>> index 0000000..eae7596 >>>>>>>>> --- /dev/null >>>>>>>>> +++ b/helper/hash_fbk.c >>>>>>>>> @@ -0,0 +1,179 @@ >>>>>>>>> +/** >>>>>>>>> + * BSD LICENSE >>>>>>>>> + * >>>>>>>>> + * Copyright(c) 2010-2014 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 <stdint.h> >>>>>>>>> +#include <stdio.h> >>>>>>>>> +#include <stdarg.h> >>>>>>>>> +#include <string.h> >>>>>>>>> +#include <errno.h> >>>>>>>>> + >>>>>>>>> +#include <odp/shared_memory.h> >>>>>>>>> +#include <odp/rwlock.h> >>>>>>>>> +#include "odph_debug.h" >>>>>>>>> +#include <odp/helper/hash_fbk.h> >>>>>>>>> + >>>>>>>>> +static TAILQ_HEAD(, odp_fbk_hash_table) >>>>>>>>> fbk_hash_list; >>>>>>>>> +static odp_rwlock_t fbk_hash_lock; >>>>>>>>> + >>>>>>>>> +void >>>>>>>>> +odp_fbk_hash_list_init() >>>>>>>>> +{ >>>>>>>>> + TAILQ_INIT(&fbk_hash_list); >>>>>>>>> + odp_rwlock_init(&fbk_hash_lock); >>>>>>>>> +} >>>>>>>>> + >>>>>>>>> +/** >>>>>>>>> + * Performs a lookup for an existing hash >>>>>>>>> table, and returns a pointer to >>>>>>>>> + * the table if found. >>>>>>>>> + * >>>>>>>>> + * @param name >>>>>>>>> + * Name of the hash table to find >>>>>>>>> + * >>>>>>>>> + * @return >>>>>>>>> + * pointer to hash table structure or >>>>>>>>> NULL on error. >>>>>>>>> + */ >>>>>>>>> +struct odp_fbk_hash_table * >>>>>>>>> +odp_fbk_hash_find_existing(const char >>>>>>>>> *name) >>>>>>>>> +{ >>>>>>>>> + struct odp_fbk_hash_table *h = NULL; >>>>>>>>> + >>>>>>>>> + odp_rwlock_read_lock(&fbk_hash_lock); >>>>>>>>> + TAILQ_FOREACH(h, &fbk_hash_list, next) { >>>>>>>>> + if (strncmp(name, h->name, >>>>>>>>> ODP_FBK_HASH_NAMESIZE) == 0) >>>>>>>>> + break; >>>>>>>>> + } >>>>>>>>> + odp_rwlock_read_unlock(&fbk_hash_lock); >>>>>>>>> + if (h == NULL) { >>>>>>>>> + return NULL; >>>>>>>>> + } >>>>>>>>> + return h; >>>>>>>>> >>>>>>>>> simple return h. (if it's NULL, NULL will be >>>>>>>>> returned.) >>>>>>>>> >>>>>>>>> >>>>>>>>> >>>>>>>>> +} >>>>>>>>> + >>>>>>>>> +/** >>>>>>>>> + * Create a new hash table for use with >>>>>>>>> four byte keys. >>>>>>>>> + * >>>>>>>>> + * @param params >>>>>>>>> + * Parameters used in creation of hash >>>>>>>>> table. >>>>>>>>> + * >>>>>>>>> + * @return >>>>>>>>> + * Pointer to hash table structure that >>>>>>>>> is used in future hash table >>>>>>>>> + * operations, or NULL on error. >>>>>>>>> + */ >>>>>>>>> +struct odp_fbk_hash_table * >>>>>>>>> +odp_fbk_hash_create(const struct >>>>>>>>> odp_fbk_hash_params *params) >>>>>>>>> +{ >>>>>>>>> + struct odp_fbk_hash_table *ht = >>>>>>>>> NULL; >>>>>>>>> + odp_shm_t shm; >>>>>>>>> + char >>>>>>>>> hash_name[ODP_FBK_HASH_NAMESIZE]; >>>>>>>>> + const uint32_t mem_size = >>>>>>>>> + sizeof(*ht) + (sizeof(ht->t[0]) * >>>>>>>>> params->entries); >>>>>>>>> + uint32_t i; >>>>>>>>> + >>>>>>>>> + /* Error checking of parameters. */ >>>>>>>>> + if >>>>>>>>> ((!odp_is_power_of_2(params->entries)) || >>>>>>>>> + >>>>>>>>> >>>>>>>>> (!odp_is_power_of_2(params->entries_per_bucket)) >>>>>>>>> || >>>>>>>>> + (params->entries == 0) || >>>>>>>>> + (params->entries_per_bucket == 0) || >>>>>>>>> + (params->entries_per_bucket > >>>>>>>>> params->entries) || >>>>>>>>> + (params->entries > >>>>>>>>> ODP_FBK_HASH_ENTRIES_MAX) || >>>>>>>>> >>>>>>>>> >>>>>>>>> ODP_FBK_HASH_ENTRIES_MAX has to have ODOH_ >>>>>>>>> prefix if the goal is to put it to helpers. >>>>>>>>> >>>>>>>>> + (params->entries_per_bucket > >>>>>>>>> ODP_FBK_HASH_ENTRIES_PER_BUCKET_MAX)) { >>>>>>>>> + return NULL; >>>>>>>>> + } >>>>>>>>> + >>>>>>>>> + snprintf(hash_name, sizeof(hash_name), >>>>>>>>> "FBK_%s", params->name); >>>>>>>>> + >>>>>>>>> + odp_rwlock_write_lock(&fbk_hash_lock); >>>>>>>>> + >>>>>>>>> + /* guarantee there's no existing */ >>>>>>>>> + TAILQ_FOREACH(ht, &fbk_hash_list, next) { >>>>>>>>> + if (strncmp(params->name, ht->name, >>>>>>>>> ODP_FBK_HASH_NAMESIZE) == 0) >>>>>>>>> + break; >>>>>>>>> + } >>>>>>>>> + if (ht != NULL) >>>>>>>>> + goto exit; >>>>>>>>> + >>>>>>>>> + printf("reserve\n"); >>>>>>>>> >>>>>>>>> remove print. >>>>>>>>> >>>>>>>>> + /* Allocate memory for table. */ >>>>>>>>> + shm = odp_shm_reserve(hash_name, >>>>>>>>> mem_size, ODP_CACHE_LINE_SIZE, 0); >>>>>>>>> + if (shm == ODP_SHM_INVALID) { >>>>>>>>> + ODPH_ERR("Failed to allocate fbk hash >>>>>>>>> table\n"); >>>>>>>>> + goto exit; >>>>>>>>> + } >>>>>>>>> + ht = odp_shm_addr(shm); >>>>>>>>> + >>>>>>>>> + /* Set up hash table context. */ >>>>>>>>> + ht->shm = shm; >>>>>>>>> + snprintf(ht->name, sizeof(ht->name), >>>>>>>>> "%s", params->name); >>>>>>>>> + ht->entries = params->entries; >>>>>>>>> + ht->entries_per_bucket = >>>>>>>>> params->entries_per_bucket; >>>>>>>>> + ht->used_entries = 0; >>>>>>>>> + ht->bucket_mask = (params->entries / >>>>>>>>> params->entries_per_bucket) - 1; >>>>>>>>> + for (ht->bucket_shift = 0, i = 1; >>>>>>>>> + (params->entries_per_bucket & i) == 0; >>>>>>>>> + ht->bucket_shift++, i <<= 1) >>>>>>>>> + ; /* empty loop body */ >>>>>>>>> + >>>>>>>>> + if (params->hash_func != NULL) { >>>>>>>>> + ht->hash_func = params->hash_func; >>>>>>>>> + ht->init_val = params->init_val; >>>>>>>>> + } else { >>>>>>>>> + ht->hash_func = >>>>>>>>> ODP_FBK_HASH_FUNC_DEFAULT; >>>>>>>>> + ht->init_val = >>>>>>>>> ODP_FBK_HASH_INIT_VAL_DEFAULT; >>>>>>>>> + } >>>>>>>>> + >>>>>>>>> + TAILQ_INSERT_TAIL(&fbk_hash_list, ht, >>>>>>>>> next); >>>>>>>>> + >>>>>>>>> +exit: >>>>>>>>> + odp_rwlock_write_unlock(&fbk_hash_lock); >>>>>>>>> + >>>>>>>>> + return ht; >>>>>>>>> +} >>>>>>>>> + >>>>>>>>> +/** >>>>>>>>> + * Free all memory used by a hash table. >>>>>>>>> + * >>>>>>>>> + * @param ht >>>>>>>>> + * Hash table to deallocate. >>>>>>>>> + */ >>>>>>>>> +void >>>>>>>>> +odp_fbk_hash_free(struct >>>>>>>>> odp_fbk_hash_table *ht) >>>>>>>>> +{ >>>>>>>>> + if (ht == NULL) >>>>>>>>> + return; >>>>>>>>> + >>>>>>>>> + odp_rwlock_write_lock(&fbk_hash_lock); >>>>>>>>> + TAILQ_REMOVE(&fbk_hash_list, ht, next); >>>>>>>>> + odp_rwlock_write_unlock(&fbk_hash_lock); >>>>>>>>> + >>>>>>>>> + odp_shm_free(ht->shm); >>>>>>>>> +} >>>>>>>>> diff --git >>>>>>>>> a/helper/include/odp/helper/hash_fbk.h >>>>>>>>> b/helper/include/odp/helper/hash_fbk.h >>>>>>>>> new file mode 100644 >>>>>>>>> index 0000000..48cc65a >>>>>>>>> --- /dev/null >>>>>>>>> +++ b/helper/include/odp/helper/hash_fbk.h >>>>>>>>> @@ -0,0 +1,404 @@ >>>>>>>>> +/*- >>>>>>>>> + * BSD LICENSE >>>>>>>>> + * >>>>>>>>> + * Copyright(c) 2010-2014 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_FBK_HASH_H_ >>>>>>>>> +#define _ODP_FBK_HASH_H_ >>>>>>>>> + >>>>>>>>> +/** >>>>>>>>> + * @file >>>>>>>>> + * >>>>>>>>> + * This is a hash table implementation for >>>>>>>>> four byte keys (fbk). >>>>>>>>> + * >>>>>>>>> + * Note that the return value of the add >>>>>>>>> function should always be checked as, >>>>>>>>> + * if a bucket is full, the key is not >>>>>>>>> added even if there is space in other >>>>>>>>> + * buckets. This keeps the lookup function >>>>>>>>> very simple and therefore fast. >>>>>>>>> + */ >>>>>>>>> + >>>>>>>>> +#include <stdint.h> >>>>>>>>> +#include <errno.h> >>>>>>>>> +#include <sys/queue.h> >>>>>>>>> + >>>>>>>>> +#ifdef __cplusplus >>>>>>>>> +extern "C" { >>>>>>>>> +#endif >>>>>>>>> + >>>>>>>>> +#include <string.h> >>>>>>>>> + >>>>>>>>> +#ifndef ODP_FBK_HASH_FUNC_DEFAULT >>>>>>>>> +#ifdef ODP_MACHINE_CPUFLAG_SSE4_2 >>>>>>>>> >>>>>>>>> >>>>>>>>> ODP_ to ODPH_ everywhere. >>>>>>>>> >>>>>>>>> >>>>>>>>> +#include <odp/helper/hash_crc.h> >>>>>>>>> +/** Default four-byte key hash function if >>>>>>>>> none is specified. */ >>>>>>>>> +#define ODP_FBK_HASH_FUNC_DEFAULT >>>>>>>>> odp_hash_crc_4byte >>>>>>>>> +#else >>>>>>>>> +#include <odp/helper/hash_jhash.h> >>>>>>>>> +#define ODP_FBK_HASH_FUNC_DEFAULT >>>>>>>>> odp_jhash_1word >>>>>>>>> +#endif >>>>>>>>> +#endif >>>>>>>>> + >>>>>>>>> +#ifndef ODP_FBK_HASH_INIT_VAL_DEFAULT >>>>>>>>> +/** Initialising value used when >>>>>>>>> calculating hash. */ >>>>>>>>> +#define ODP_FBK_HASH_INIT_VAL_DEFAULT >>>>>>>>> 0xFFFFFFFF >>>>>>>>> +#endif >>>>>>>>> + >>>>>>>>> +/** The maximum number of entries in the >>>>>>>>> hash table that is suppoodpd. */ >>>>>>>>> +#define ODP_FBK_HASH_ENTRIES_MAX (1 << 20) >>>>>>>>> + >>>>>>>>> +/** The maximum number of entries in each >>>>>>>>> bucket that is suppoodpd. */ >>>>>>>>> +#define >>>>>>>>> ODP_FBK_HASH_ENTRIES_PER_BUCKET_MAX 256 >>>>>>>>> + >>>>>>>>> +/** Maximum size of string for naming the >>>>>>>>> hash. */ >>>>>>>>> +#define ODP_FBK_HASH_NAMESIZE 32 >>>>>>>>> + >>>>>>>>> +/** Type of function that can be used for >>>>>>>>> calculating the hash value. */ >>>>>>>>> +typedef uint32_t >>>>>>>>> (*odp_fbk_hash_fn)(uint32_t key, uint32_t >>>>>>>>> init_val); >>>>>>>>> + >>>>>>>>> +/** Parameters used when creating >>>>>>>>> four-byte key hash table. */ >>>>>>>>> +struct odp_fbk_hash_params { >>>>>>>>> >>>>>>>>> odph_ >>>>>>>>> >>>>>>>>> If it is still all DPDK syntax and semantics (and >>>>>>>>> not adapted to e.g. ODP handling), why not keep >>>>>>>>> the RTE names? >>>>>>>>> >>>>>>>>> + const char *name; /**< Name of the >>>>>>>>> hash table. */ >>>>>>>>> + uint32_t entries; /**< Total number of >>>>>>>>> entries. */ >>>>>>>>> + uint32_t entries_per_bucket; /**< >>>>>>>>> Number of entries in a bucket. */ >>>>>>>>> + odp_fbk_hash_fn hash_func; /**< The >>>>>>>>> hash function. */ >>>>>>>>> + uint32_t init_val; /**< For initialising >>>>>>>>> hash function. */ >>>>>>>>> +}; >>>>>>>>> + >>>>>>>>> +/** Individual entry in the four-byte key >>>>>>>>> hash table. */ >>>>>>>>> +union odp_fbk_hash_entry { >>>>>>>>> + uint64_t whole_entry; /**< For >>>>>>>>> accessing entire entry. */ >>>>>>>>> + struct { >>>>>>>>> + uint16_t is_entry; /**< Non-zero if >>>>>>>>> entry is active. */ >>>>>>>>> + uint16_t value; /**< Value returned by >>>>>>>>> lookup. */ >>>>>>>>> + uint32_t key; /**< Key used to find >>>>>>>>> value. */ >>>>>>>>> + } entry; /**< For accessing each >>>>>>>>> entry part. */ >>>>>>>>> +}; >>>>>>>>> + >>>>>>>>> + >>>>>>>>> +/** The four-byte key hash table >>>>>>>>> structure. */ >>>>>>>>> +struct odp_fbk_hash_table { >>>>>>>>> + TAILQ_ENTRY(odp_fbk_hash_table) next; >>>>>>>>> + odp_shm_t shm; >>>>>>>>> + >>>>>>>>> + char name[ODP_FBK_HASH_NAMESIZE]; >>>>>>>>> /**< Name of the hash. */ >>>>>>>>> + uint32_t entries; /**< Total number of >>>>>>>>> entries. */ >>>>>>>>> + uint32_t entries_per_bucket; /**< >>>>>>>>> Number of entries in a bucket. */ >>>>>>>>> + uint32_t used_entries; /**< How many >>>>>>>>> entries are used. */ >>>>>>>>> + uint32_t bucket_mask; /**< To find >>>>>>>>> which bucket the key is in. */ >>>>>>>>> + uint32_t bucket_shift; /**< Convert >>>>>>>>> bucket to table offset. */ >>>>>>>>> + odp_fbk_hash_fn hash_func; /**< The >>>>>>>>> hash function. */ >>>>>>>>> + uint32_t init_val; /**< For initialising >>>>>>>>> hash function. */ >>>>>>>>> + >>>>>>>>> + /** A flat table of all buckets. */ >>>>>>>>> + union odp_fbk_hash_entry t[0]; >>>>>>>>> +}; >>>>>>>>> + >>>>>>>>> +/** >>>>>>>>> + * Find the offset into hash table of the >>>>>>>>> bucket containing a particular key. >>>>>>>>> + * >>>>>>>>> + * @param ht >>>>>>>>> + * Pointer to hash table. >>>>>>>>> + * @param key >>>>>>>>> + * Key to calculate bucket for. >>>>>>>>> + * @return >>>>>>>>> + * Offset into hash table. >>>>>>>>> + */ >>>>>>>>> +static inline uint32_t >>>>>>>>> +odp_fbk_hash_get_bucket(const struct >>>>>>>>> odp_fbk_hash_table *ht, uint32_t key) >>>>>>>>> +{ >>>>>>>>> + return (ht->hash_func(key, >>>>>>>>> ht->init_val) & ht->bucket_mask) << >>>>>>>>> + ht->bucket_shift; >>>>>>>>> +} >>>>>>>>> + >>>>>>>>> +/** >>>>>>>>> + * Add a key to an existing hash table >>>>>>>>> with bucket id. >>>>>>>>> + * This operation is not multi-thread safe >>>>>>>>> + * and should only be called from one >>>>>>>>> thread. >>>>>>>>> + * >>>>>>>>> + * @param ht >>>>>>>>> + * Hash table to add the key to. >>>>>>>>> + * @param key >>>>>>>>> + * Key to add to the hash table. >>>>>>>>> + * @param value >>>>>>>>> + * Value to associate with key. >>>>>>>>> + * @param bucket >>>>>>>>> + * Bucket to associate with key. >>>>>>>>> + * @return >>>>>>>>> + * 0 if ok, or negative value on error. >>>>>>>>> + */ >>>>>>>>> +static inline int >>>>>>>>> +odp_fbk_hash_add_key_with_bucket(struct >>>>>>>>> odp_fbk_hash_table *ht, >>>>>>>>> + uint32_t key, uint16_t value, uint32_t >>>>>>>>> bucket) >>>>>>>>> +{ >>>>>>>>> + /* >>>>>>>>> + * The writing of a new value to >>>>>>>>> the hash table is done as a single >>>>>>>>> + * 64bit operation. This should >>>>>>>>> help prevent individual entries being >>>>>>>>> + * corrupted due to race >>>>>>>>> conditions, but it's still possible to >>>>>>>>> + * overwrite entries that have just >>>>>>>>> been made valid. >>>>>>>>> + */ >>>>>>>>> + const uint64_t new_entry = >>>>>>>>> ((uint64_t)(key) << 32) | >>>>>>>>> + ((uint64_t)(value) << 16) | >>>>>>>>> + 1; /* 1 = is_entry bit. */ >>>>>>>>> + uint32_t i; >>>>>>>>> + >>>>>>>>> + for (i = 0; i < >>>>>>>>> ht->entries_per_bucket; i++) { >>>>>>>>> + /* Set entry if unused. */ >>>>>>>>> + if (!ht->t[bucket + i].entry.is < >>>>>>>>> http://entry.is/> >>>>>>>>> <http://entry.is/>_entry) { >>>>>>>>> + ht->t[bucket + i].whole_entry = >>>>>>>>> new_entry; >>>>>>>>> + ht->used_entries++; >>>>>>>>> + return 0; >>>>>>>>> + } >>>>>>>>> + /* Change value if key already exists. */ >>>>>>>>> + if (ht->t[bucket + i].entry.key == key) { >>>>>>>>> + ht->t[bucket + i].entry.value = value; >>>>>>>>> + return 0; >>>>>>>>> + } >>>>>>>>> + } >>>>>>>>> + >>>>>>>>> + return -ENOSPC; /* No space in >>>>>>>>> bucket. */ >>>>>>>>> +} >>>>>>>>> + >>>>>>>>> +/** >>>>>>>>> + * Add a key to an existing hash table. >>>>>>>>> This operation is not multi-thread safe >>>>>>>>> + * and should only be called from one >>>>>>>>> thread. >>>>>>>>> + * >>>>>>>>> + * @param ht >>>>>>>>> + * Hash table to add the key to. >>>>>>>>> + * @param key >>>>>>>>> + * Key to add to the hash table. >>>>>>>>> + * @param value >>>>>>>>> + * Value to associate with key. >>>>>>>>> + * @return >>>>>>>>> + * 0 if ok, or negative value on error. >>>>>>>>> + */ >>>>>>>>> +static inline int >>>>>>>>> +odp_fbk_hash_add_key(struct >>>>>>>>> odp_fbk_hash_table *ht, >>>>>>>>> + uint32_t key, uint16_t value) >>>>>>>>> +{ >>>>>>>>> + return >>>>>>>>> odp_fbk_hash_add_key_with_bucket(ht, >>>>>>>>> + key, value, >>>>>>>>> odp_fbk_hash_get_bucket(ht, key)); >>>>>>>>> +} >>>>>>>>> + >>>>>>>>> +/** >>>>>>>>> + * Remove a key with a given bucket id >>>>>>>>> from an existing hash table. >>>>>>>>> + * This operation is not multi-thread >>>>>>>>> + * safe and should only be called from one >>>>>>>>> thread. >>>>>>>>> + * >>>>>>>>> + * @param ht >>>>>>>>> + * Hash table to remove the key from. >>>>>>>>> + * @param key >>>>>>>>> + * Key to remove from the hash table. >>>>>>>>> + * @param bucket >>>>>>>>> + * Bucket id associate with key. >>>>>>>>> + * @return >>>>>>>>> + * 0 if ok, or negative value on error. >>>>>>>>> + */ >>>>>>>>> +static inline int >>>>>>>>> +odp_fbk_hash_delete_key_with_bucket(struct >>>>>>>>> odp_fbk_hash_table *ht, >>>>>>>>> + uint32_t key, uint32_t bucket) >>>>>>>>> +{ >>>>>>>>> + uint32_t last_entry = >>>>>>>>> ht->entries_per_bucket - 1; >>>>>>>>> + uint32_t i, j; >>>>>>>>> + >>>>>>>>> + for (i = 0; i < >>>>>>>>> ht->entries_per_bucket; i++) { >>>>>>>>> + if (ht->t[bucket + i].entry.key == key) { >>>>>>>>> + /* Find last key in bucket. */ >>>>>>>>> + for (j = ht->entries_per_bucket >>>>>>>>> - 1; j > i; j--) { >>>>>>>>> + if (!ht->t[bucket + j].entry.is < >>>>>>>>> http://entry.is/> >>>>>>>>> <http://entry.is/>_entry) { >>>>>>>>> + last_entry = j - 1; >>>>>>>>> + } >>>>>>>>> + } >>>>>>>>> + /* >>>>>>>>> + * Move the last key to the >>>>>>>>> deleted key's position, and >>>>>>>>> + * delete the last key. >>>>>>>>> lastEntry and i may be same but >>>>>>>>> + * it doesn't matter. >>>>>>>>> + */ >>>>>>>>> + ht->t[bucket + i].whole_entry = >>>>>>>>> + ht->t[bucket + last_entry].whole_entry; >>>>>>>>> + ht->t[bucket + last_entry].whole_entry = >>>>>>>>> 0; >>>>>>>>> + >>>>>>>>> + ht->used_entries--; >>>>>>>>> + return 0; >>>>>>>>> + } >>>>>>>>> + } >>>>>>>>> + >>>>>>>>> + return -ENOENT; /* Key didn't >>>>>>>>> exist. */ >>>>>>>>> +} >>>>>>>>> + >>>>>>>>> +/** >>>>>>>>> + * Remove a key from an existing hash >>>>>>>>> table. This operation is not multi-thread >>>>>>>>> + * safe and should only be called from one >>>>>>>>> thread. >>>>>>>>> + * >>>>>>>>> + * @param ht >>>>>>>>> + * Hash table to remove the key from. >>>>>>>>> + * @param key >>>>>>>>> + * Key to remove from the hash table. >>>>>>>>> + * @return >>>>>>>>> + * 0 if ok, or negative value on error. >>>>>>>>> + */ >>>>>>>>> +static inline int >>>>>>>>> +odp_fbk_hash_delete_key(struct >>>>>>>>> odp_fbk_hash_table *ht, uint32_t key) >>>>>>>>> +{ >>>>>>>>> + return >>>>>>>>> odp_fbk_hash_delete_key_with_bucket(ht, >>>>>>>>> + key, odp_fbk_hash_get_bucket(ht, key)); >>>>>>>>> +} >>>>>>>>> + >>>>>>>>> +/** >>>>>>>>> + * Find a key in the hash table with a >>>>>>>>> given bucketid. >>>>>>>>> + * This operation is multi-thread safe. >>>>>>>>> + * >>>>>>>>> + * @param ht >>>>>>>>> + * Hash table to look in. >>>>>>>>> + * @param key >>>>>>>>> + * Key to find. >>>>>>>>> + * @param bucket >>>>>>>>> + * Bucket associate to the key. >>>>>>>>> + * @return >>>>>>>>> + * The value that was associated with >>>>>>>>> the key, or negative value on error. >>>>>>>>> + */ >>>>>>>>> +static inline int >>>>>>>>> +odp_fbk_hash_lookup_with_bucket(const >>>>>>>>> struct odp_fbk_hash_table *ht, >>>>>>>>> + uint32_t key, uint32_t bucket) >>>>>>>>> +{ >>>>>>>>> + union odp_fbk_hash_entry >>>>>>>>> current_entry; >>>>>>>>> + uint32_t i; >>>>>>>>> + >>>>>>>>> + for (i = 0; i < >>>>>>>>> ht->entries_per_bucket; i++) { >>>>>>>>> + /* Single read of entry, which should be >>>>>>>>> atomic. */ >>>>>>>>> + current_entry.whole_entry = ht->t[bucket >>>>>>>>> + i].whole_entry; >>>>>>>>> + if (!current_entry.entry.is_entry) { >>>>>>>>> + return -ENOENT; /* Error once we hit an >>>>>>>>> empty field. */ >>>>>>>>> + } >>>>>>>>> + if (current_entry.entry.key == key) { >>>>>>>>> + return current_entry.entry.value; >>>>>>>>> + } >>>>>>>>> + } >>>>>>>>> + return -ENOENT; /* Key didn't >>>>>>>>> exist. */ >>>>>>>>> +} >>>>>>>>> + >>>>>>>>> +/** >>>>>>>>> + * Find a key in the hash table. This >>>>>>>>> operation is multi-thread safe. >>>>>>>>> + * >>>>>>>>> + * @param ht >>>>>>>>> + * Hash table to look in. >>>>>>>>> + * @param key >>>>>>>>> + * Key to find. >>>>>>>>> + * @return >>>>>>>>> + * The value that was associated with >>>>>>>>> the key, or negative value on error. >>>>>>>>> + */ >>>>>>>>> +static inline int >>>>>>>>> +odp_fbk_hash_lookup(const struct >>>>>>>>> odp_fbk_hash_table *ht, uint32_t key) >>>>>>>>> +{ >>>>>>>>> + return >>>>>>>>> odp_fbk_hash_lookup_with_bucket(ht, >>>>>>>>> + key, odp_fbk_hash_get_bucket(ht, key)); >>>>>>>>> +} >>>>>>>>> + >>>>>>>>> +/** >>>>>>>>> + * Delete all entries in a hash table. >>>>>>>>> This operation is not multi-thread >>>>>>>>> + * safe and should only be called from one >>>>>>>>> thread. >>>>>>>>> + * >>>>>>>>> + * @param ht >>>>>>>>> + * Hash table to delete entries in. >>>>>>>>> + */ >>>>>>>>> +static inline void >>>>>>>>> +odp_fbk_hash_clear_all(struct >>>>>>>>> odp_fbk_hash_table *ht) >>>>>>>>> +{ >>>>>>>>> + memset(ht->t, 0, sizeof(ht->t[0]) * >>>>>>>>> ht->entries); >>>>>>>>> + ht->used_entries = 0; >>>>>>>>> +} >>>>>>>>> + >>>>>>>>> +/** >>>>>>>>> + * Find what fraction of entries are being >>>>>>>>> used. >>>>>>>>> + * >>>>>>>>> + * @param ht >>>>>>>>> + * Hash table to find how many entries >>>>>>>>> are being used in. >>>>>>>>> + * @return >>>>>>>>> + * Load factor of the hash table, or >>>>>>>>> negative value on error. >>>>>>>>> + */ >>>>>>>>> +static inline double >>>>>>>>> +odp_fbk_hash_get_load_factor(struct >>>>>>>>> odp_fbk_hash_table *ht) >>>>>>>>> +{ >>>>>>>>> + return (double)ht->used_entries / >>>>>>>>> (double)ht->entries; >>>>>>>>> +} >>>>>>>>> + >>>>>>>>> +/** >>>>>>>>> + * Performs a lookup for an existing hash >>>>>>>>> table, and returns a pointer to >>>>>>>>> + * the table if found. >>>>>>>>> + * >>>>>>>>> + * @param name >>>>>>>>> + * Name of the hash table to find >>>>>>>>> + * >>>>>>>>> + * @return >>>>>>>>> + * pointer to hash table structure or >>>>>>>>> NULL on error with odp_errno >>>>>>>>> + * set appropriately. Possible odp_errno >>>>>>>>> values include: >>>>>>>>> + * - ENOENT - required entry not >>>>>>>>> available to return. >>>>>>>>> + */ >>>>>>>>> +struct odp_fbk_hash_table >>>>>>>>> *odp_fbk_hash_find_existing(const char >>>>>>>>> *name); >>>>>>>>> + >>>>>>>>> +/** >>>>>>>>> + * Create a new hash table for use with >>>>>>>>> four byte keys. >>>>>>>>> + * >>>>>>>>> + * @param params >>>>>>>>> + * Parameters used in creation of hash >>>>>>>>> table. >>>>>>>>> + * >>>>>>>>> + * @return >>>>>>>>> + * Pointer to hash table structure that >>>>>>>>> is used in future hash table >>>>>>>>> + * operations, or NULL on error with >>>>>>>>> odp_errno set appropriately. >>>>>>>>> + * Possible odp_errno error values >>>>>>>>> include: >>>>>>>>> + * - E_ODP_NO_CONFIG - function could >>>>>>>>> not get pointer to odp_config structure >>>>>>>>> + * - E_ODP_SECONDARY - function was >>>>>>>>> called from a secondary process instance >>>>>>>>> + * - EINVAL - invalid parameter value >>>>>>>>> passed to function >>>>>>>>> + * - ENOSPC - the maximum number of >>>>>>>>> memzones has already been allocated >>>>>>>>> + * - EEXIST - a memzone with the same >>>>>>>>> name already exists >>>>>>>>> + * - ENOMEM - no appropriate memory >>>>>>>>> area found in which to create memzone >>>>>>>>> + */ >>>>>>>>> +struct odp_fbk_hash_table * \ >>>>>>>>> +odp_fbk_hash_create(const struct >>>>>>>>> odp_fbk_hash_params *params); >>>>>>>>> + >>>>>>>>> + >>>>>>>>> +/** >>>>>>>>> + * Initialize the global structures used >>>>>>>>> by fbk >>>>>>>>> + */ >>>>>>>>> +void odp_fbk_hash_list_init(void); >>>>>>>>> + >>>>>>>>> +/** >>>>>>>>> + * Free all memory used by a hash table. >>>>>>>>> + * Has no effect on hash tables allocated >>>>>>>>> in memory zones >>>>>>>>> + * >>>>>>>>> + * @param ht >>>>>>>>> + * Hash table to deallocate. >>>>>>>>> + */ >>>>>>>>> +void odp_fbk_hash_free(struct >>>>>>>>> odp_fbk_hash_table *ht); >>>>>>>>> + >>>>>>>>> +#ifdef __cplusplus >>>>>>>>> +} >>>>>>>>> +#endif >>>>>>>>> + >>>>>>>>> +#endif /* _ODP_FBK_HASH_H_ */ >>>>>>>>> >>>>>>>>> >>>>>>>>> _______________________________________________ >>>>>>>>> lng-odp mailing list >>>>>>>>> lng-odp@lists.linaro.org <mailto:lng-odp@lists.linaro.org> >>>>>>>>> https://lists.linaro.org/mailman/listinfo/lng-odp >>>>>>>>> >>>>>>>>> >>>>>>>>> >>>>>>>>> _______________________________________________ >>>>>>>>> lng-odp mailing list >>>>>>>>> lng-odp@lists.linaro.org <mailto:lng-odp@lists.linaro.org><mailto: >>>>>>>>> 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 >> >> > >
_______________________________________________ lng-odp mailing list lng-odp@lists.linaro.org https://lists.linaro.org/mailman/listinfo/lng-odp
