On 23 September 2015 at 19:51, Maxim Uvarov <maxim.uva...@linaro.org> wrote:
> > > On 09/20/15 07:04, rujiacs wrote: > >> Signed-off-by: rujiacs <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_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_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 > 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