diff options
Diffstat (limited to 'src/dpdk_lib18/librte_hash')
| -rwxr-xr-x | src/dpdk_lib18/librte_hash/Makefile | 53 | ||||
| -rwxr-xr-x | src/dpdk_lib18/librte_hash/rte_fbk_hash.c | 240 | ||||
| -rwxr-xr-x | src/dpdk_lib18/librte_hash/rte_fbk_hash.h | 397 | ||||
| -rwxr-xr-x | src/dpdk_lib18/librte_hash/rte_hash.c | 483 | ||||
| -rwxr-xr-x | src/dpdk_lib18/librte_hash/rte_hash.h | 310 | ||||
| -rwxr-xr-x | src/dpdk_lib18/librte_hash/rte_hash_crc.h | 110 | ||||
| -rwxr-xr-x | src/dpdk_lib18/librte_hash/rte_jhash.h | 253 |
7 files changed, 1846 insertions, 0 deletions
diff --git a/src/dpdk_lib18/librte_hash/Makefile b/src/dpdk_lib18/librte_hash/Makefile new file mode 100755 index 00000000..95e4c09c --- /dev/null +++ b/src/dpdk_lib18/librte_hash/Makefile @@ -0,0 +1,53 @@ +# 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 $(RTE_SDK)/mk/rte.vars.mk + +# library name +LIB = librte_hash.a + +CFLAGS += -O3 +CFLAGS += $(WERROR_FLAGS) -I$(SRCDIR) + +# all source are stored in SRCS-y +SRCS-$(CONFIG_RTE_LIBRTE_HASH) := rte_hash.c +SRCS-$(CONFIG_RTE_LIBRTE_HASH) += rte_fbk_hash.c + +# install this header file +SYMLINK-$(CONFIG_RTE_LIBRTE_HASH)-include := rte_hash.h +SYMLINK-$(CONFIG_RTE_LIBRTE_HASH)-include += rte_hash_crc.h +SYMLINK-$(CONFIG_RTE_LIBRTE_HASH)-include += rte_jhash.h +SYMLINK-$(CONFIG_RTE_LIBRTE_HASH)-include += rte_fbk_hash.h + +# this lib needs eal +DEPDIRS-$(CONFIG_RTE_LIBRTE_HASH) += lib/librte_eal lib/librte_malloc + +include $(RTE_SDK)/mk/rte.lib.mk diff --git a/src/dpdk_lib18/librte_hash/rte_fbk_hash.c b/src/dpdk_lib18/librte_hash/rte_fbk_hash.c new file mode 100755 index 00000000..421e1cdd --- /dev/null +++ b/src/dpdk_lib18/librte_hash/rte_fbk_hash.c @@ -0,0 +1,240 @@ +/** + * 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 <sys/queue.h> +#include <rte_memory.h> +#include <rte_memzone.h> +#include <rte_tailq.h> +#include <rte_eal.h> +#include <rte_eal_memconfig.h> +#include <rte_malloc.h> +#include <rte_common.h> +#include <rte_per_lcore.h> +#include <rte_errno.h> +#include <rte_string_fns.h> +#include <rte_cpuflags.h> +#include <rte_log.h> +#include <rte_spinlock.h> + +#include "rte_fbk_hash.h" + +TAILQ_HEAD(rte_fbk_hash_list, rte_tailq_entry); + +/** + * 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 rte_fbk_hash_table * +rte_fbk_hash_find_existing(const char *name) +{ + struct rte_fbk_hash_table *h = NULL; + struct rte_tailq_entry *te; + struct rte_fbk_hash_list *fbk_hash_list; + + /* check that we have an initialised tail queue */ + if ((fbk_hash_list = + RTE_TAILQ_LOOKUP_BY_IDX(RTE_TAILQ_FBK_HASH, + rte_fbk_hash_list)) == NULL) { + rte_errno = E_RTE_NO_TAILQ; + return NULL; + } + + rte_rwlock_read_lock(RTE_EAL_TAILQ_RWLOCK); + TAILQ_FOREACH(te, fbk_hash_list, next) { + h = (struct rte_fbk_hash_table *) te->data; + if (strncmp(name, h->name, RTE_FBK_HASH_NAMESIZE) == 0) + break; + } + rte_rwlock_read_unlock(RTE_EAL_TAILQ_RWLOCK); + if (te == NULL) { + rte_errno = ENOENT; + return NULL; + } + return h; +} + +/** + * 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 rte_fbk_hash_table * +rte_fbk_hash_create(const struct rte_fbk_hash_params *params) +{ + struct rte_fbk_hash_table *ht = NULL; + struct rte_tailq_entry *te; + char hash_name[RTE_FBK_HASH_NAMESIZE]; + const uint32_t mem_size = + sizeof(*ht) + (sizeof(ht->t[0]) * params->entries); + uint32_t i; + struct rte_fbk_hash_list *fbk_hash_list; + + /* check that we have an initialised tail queue */ + if ((fbk_hash_list = + RTE_TAILQ_LOOKUP_BY_IDX(RTE_TAILQ_FBK_HASH, + rte_fbk_hash_list)) == NULL) { + rte_errno = E_RTE_NO_TAILQ; + return NULL; + } + + /* Error checking of parameters. */ + if ((!rte_is_power_of_2(params->entries)) || + (!rte_is_power_of_2(params->entries_per_bucket)) || + (params->entries == 0) || + (params->entries_per_bucket == 0) || + (params->entries_per_bucket > params->entries) || + (params->entries > RTE_FBK_HASH_ENTRIES_MAX) || + (params->entries_per_bucket > RTE_FBK_HASH_ENTRIES_PER_BUCKET_MAX)){ + rte_errno = EINVAL; + return NULL; + } + + snprintf(hash_name, sizeof(hash_name), "FBK_%s", params->name); + + rte_rwlock_write_lock(RTE_EAL_TAILQ_RWLOCK); + + /* guarantee there's no existing */ + TAILQ_FOREACH(te, fbk_hash_list, next) { + ht = (struct rte_fbk_hash_table *) te->data; + if (strncmp(params->name, ht->name, RTE_FBK_HASH_NAMESIZE) == 0) + break; + } + if (te != NULL) + goto exit; + + te = rte_zmalloc("FBK_HASH_TAILQ_ENTRY", sizeof(*te), 0); + if (te == NULL) { + RTE_LOG(ERR, HASH, "Failed to allocate tailq entry\n"); + goto exit; + } + + /* Allocate memory for table. */ + ht = (struct rte_fbk_hash_table *)rte_zmalloc_socket(hash_name, mem_size, + 0, params->socket_id); + if (ht == NULL) { + RTE_LOG(ERR, HASH, "Failed to allocate fbk hash table\n"); + rte_free(te); + goto exit; + } + + /* Set up hash table context. */ + 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 = RTE_FBK_HASH_FUNC_DEFAULT; + ht->init_val = RTE_FBK_HASH_INIT_VAL_DEFAULT; + } + + te->data = (void *) ht; + + TAILQ_INSERT_TAIL(fbk_hash_list, te, next); + +exit: + rte_rwlock_write_unlock(RTE_EAL_TAILQ_RWLOCK); + + return ht; +} + +/** + * Free all memory used by a hash table. + * + * @param ht + * Hash table to deallocate. + */ +void +rte_fbk_hash_free(struct rte_fbk_hash_table *ht) +{ + struct rte_tailq_entry *te; + struct rte_fbk_hash_list *fbk_hash_list; + + if (ht == NULL) + return; + + /* check that we have an initialised tail queue */ + if ((fbk_hash_list = + RTE_TAILQ_LOOKUP_BY_IDX(RTE_TAILQ_FBK_HASH, + rte_fbk_hash_list)) == NULL) { + rte_errno = E_RTE_NO_TAILQ; + return; + } + + rte_rwlock_write_lock(RTE_EAL_TAILQ_RWLOCK); + + /* find out tailq entry */ + TAILQ_FOREACH(te, fbk_hash_list, next) { + if (te->data == (void *) ht) + break; + } + + if (te == NULL) { + rte_rwlock_write_unlock(RTE_EAL_TAILQ_RWLOCK); + return; + } + + TAILQ_REMOVE(fbk_hash_list, te, next); + + rte_rwlock_write_unlock(RTE_EAL_TAILQ_RWLOCK); + + rte_free(ht); + rte_free(te); +} + diff --git a/src/dpdk_lib18/librte_hash/rte_fbk_hash.h b/src/dpdk_lib18/librte_hash/rte_fbk_hash.h new file mode 100755 index 00000000..3d229bf9 --- /dev/null +++ b/src/dpdk_lib18/librte_hash/rte_fbk_hash.h @@ -0,0 +1,397 @@ +/*- + * 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 _RTE_FBK_HASH_H_ +#define _RTE_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 RTE_FBK_HASH_FUNC_DEFAULT +#ifdef RTE_MACHINE_CPUFLAG_SSE4_2 +#include <rte_hash_crc.h> +/** Default four-byte key hash function if none is specified. */ +#define RTE_FBK_HASH_FUNC_DEFAULT rte_hash_crc_4byte +#else +#include <rte_jhash.h> +#define RTE_FBK_HASH_FUNC_DEFAULT rte_jhash_1word +#endif +#endif + +#ifndef RTE_FBK_HASH_INIT_VAL_DEFAULT +/** Initialising value used when calculating hash. */ +#define RTE_FBK_HASH_INIT_VAL_DEFAULT 0xFFFFFFFF +#endif + +/** The maximum number of entries in the hash table that is supported. */ +#define RTE_FBK_HASH_ENTRIES_MAX (1 << 20) + +/** The maximum number of entries in each bucket that is supported. */ +#define RTE_FBK_HASH_ENTRIES_PER_BUCKET_MAX 256 + +/** Maximum size of string for naming the hash. */ +#define RTE_FBK_HASH_NAMESIZE 32 + +/** Type of function that can be used for calculating the hash value. */ +typedef uint32_t (*rte_fbk_hash_fn)(uint32_t key, uint32_t init_val); + +/** Parameters used when creating four-byte key hash table. */ +struct rte_fbk_hash_params { + 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. */ + int socket_id; /**< Socket to allocate memory on. */ + rte_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 rte_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 rte_fbk_hash_table { + char name[RTE_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. */ + rte_fbk_hash_fn hash_func; /**< The hash function. */ + uint32_t init_val; /**< For initialising hash function. */ + + /** A flat table of all buckets. */ + union rte_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 +rte_fbk_hash_get_bucket(const struct rte_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 +rte_fbk_hash_add_key_with_bucket(struct rte_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 +rte_fbk_hash_add_key(struct rte_fbk_hash_table *ht, + uint32_t key, uint16_t value) +{ + return rte_fbk_hash_add_key_with_bucket(ht, + key, value, rte_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 +rte_fbk_hash_delete_key_with_bucket(struct rte_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 +rte_fbk_hash_delete_key(struct rte_fbk_hash_table *ht, uint32_t key) +{ + return rte_fbk_hash_delete_key_with_bucket(ht, + key, rte_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 +rte_fbk_hash_lookup_with_bucket(const struct rte_fbk_hash_table *ht, + uint32_t key, uint32_t bucket) +{ + union rte_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 +rte_fbk_hash_lookup(const struct rte_fbk_hash_table *ht, uint32_t key) +{ + return rte_fbk_hash_lookup_with_bucket(ht, + key, rte_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 +rte_fbk_hash_clear_all(struct rte_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 +rte_fbk_hash_get_load_factor(struct rte_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 rte_errno + * set appropriately. Possible rte_errno values include: + * - ENOENT - required entry not available to return. + */ +struct rte_fbk_hash_table *rte_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 rte_errno set appropriately. + * Possible rte_errno error values include: + * - E_RTE_NO_CONFIG - function could not get pointer to rte_config structure + * - E_RTE_SECONDARY - function was called from a secondary process instance + * - E_RTE_NO_TAILQ - no tailq list could be got for the fbk hash table list + * - 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 rte_fbk_hash_table * \ +rte_fbk_hash_create(const struct rte_fbk_hash_params *params); + +/** + * 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 rte_fbk_hash_free(struct rte_fbk_hash_table *ht); + +#ifdef __cplusplus +} +#endif + +#endif /* _RTE_FBK_HASH_H_ */ diff --git a/src/dpdk_lib18/librte_hash/rte_hash.c b/src/dpdk_lib18/librte_hash/rte_hash.c new file mode 100755 index 00000000..ba827d25 --- /dev/null +++ b/src/dpdk_lib18/librte_hash/rte_hash.c @@ -0,0 +1,483 @@ +/*- + * 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 <string.h> +#include <stdint.h> +#include <errno.h> +#include <stdio.h> +#include <stdarg.h> +#include <sys/queue.h> + +#include <rte_common.h> +#include <rte_memory.h> /* for definition of RTE_CACHE_LINE_SIZE */ +#include <rte_log.h> +#include <rte_memcpy.h> +#include <rte_prefetch.h> +#include <rte_branch_prediction.h> +#include <rte_memzone.h> +#include <rte_malloc.h> +#include <rte_tailq.h> +#include <rte_eal.h> +#include <rte_eal_memconfig.h> +#include <rte_per_lcore.h> +#include <rte_errno.h> +#include <rte_string_fns.h> +#include <rte_cpuflags.h> +#include <rte_log.h> +#include <rte_rwlock.h> +#include <rte_spinlock.h> + +#include "rte_hash.h" + + +TAILQ_HEAD(rte_hash_list, rte_tailq_entry); + +/* Macro to enable/disable run-time checking of function parameters */ +#if defined(RTE_LIBRTE_HASH_DEBUG) +#define RETURN_IF_TRUE(cond, retval) do { \ + if (cond) return (retval); \ +} while (0) +#else +#define RETURN_IF_TRUE(cond, retval) +#endif + +/* Hash function used if none is specified */ +#ifdef RTE_MACHINE_CPUFLAG_SSE4_2 +#include <rte_hash_crc.h> +#define DEFAULT_HASH_FUNC rte_hash_crc +#else +#include <rte_jhash.h> +#define DEFAULT_HASH_FUNC rte_jhash +#endif + +/* Signature bucket size is a multiple of this value */ +#define SIG_BUCKET_ALIGNMENT 16 + +/* Stoered key size is a multiple of this value */ +#define KEY_ALIGNMENT 16 + +/* The high bit is always set in real signatures */ +#define NULL_SIGNATURE 0 + +/* Returns a pointer to the first signature in specified bucket. */ +static inline hash_sig_t * +get_sig_tbl_bucket(const struct rte_hash *h, uint32_t bucket_index) +{ + return (hash_sig_t *) + &(h->sig_tbl[bucket_index * h->sig_tbl_bucket_size]); +} + +/* Returns a pointer to the first key in specified bucket. */ +static inline uint8_t * +get_key_tbl_bucket(const struct rte_hash *h, uint32_t bucket_index) +{ + return (uint8_t *) &(h->key_tbl[bucket_index * h->bucket_entries * + h->key_tbl_key_size]); +} + +/* Returns a pointer to a key at a specific position in a specified bucket. */ +static inline void * +get_key_from_bucket(const struct rte_hash *h, uint8_t *bkt, uint32_t pos) +{ + return (void *) &bkt[pos * h->key_tbl_key_size]; +} + +/* Does integer division with rounding-up of result. */ +static inline uint32_t +div_roundup(uint32_t numerator, uint32_t denominator) +{ + return (numerator + denominator - 1) / denominator; +} + +/* Increases a size (if needed) to a multiple of alignment. */ +static inline uint32_t +align_size(uint32_t val, uint32_t alignment) +{ + return alignment * div_roundup(val, alignment); +} + +/* Returns the index into the bucket of the first occurrence of a signature. */ +static inline int +find_first(uint32_t sig, const uint32_t *sig_bucket, uint32_t num_sigs) +{ + uint32_t i; + for (i = 0; i < num_sigs; i++) { + if (sig == sig_bucket[i]) + return i; + } + return -1; +} + +struct rte_hash * +rte_hash_find_existing(const char *name) +{ + struct rte_hash *h = NULL; + struct rte_tailq_entry *te; + struct rte_hash_list *hash_list; + + /* check that we have an initialised tail queue */ + if ((hash_list = + RTE_TAILQ_LOOKUP_BY_IDX(RTE_TAILQ_HASH, rte_hash_list)) == NULL) { + rte_errno = E_RTE_NO_TAILQ; + return NULL; + } + + rte_rwlock_read_lock(RTE_EAL_TAILQ_RWLOCK); + TAILQ_FOREACH(te, hash_list, next) { + h = (struct rte_hash *) te->data; + if (strncmp(name, h->name, RTE_HASH_NAMESIZE) == 0) + break; + } + rte_rwlock_read_unlock(RTE_EAL_TAILQ_RWLOCK); + + if (te == NULL) { + rte_errno = ENOENT; + return NULL; + } + return h; +} + +struct rte_hash * +rte_hash_create(const struct rte_hash_parameters *params) +{ + struct rte_hash *h = NULL; + struct rte_tailq_entry *te; + uint32_t num_buckets, sig_bucket_size, key_size, + hash_tbl_size, sig_tbl_size, key_tbl_size, mem_size; + char hash_name[RTE_HASH_NAMESIZE]; + struct rte_hash_list *hash_list; + + /* check that we have an initialised tail queue */ + if ((hash_list = + RTE_TAILQ_LOOKUP_BY_IDX(RTE_TAILQ_HASH, rte_hash_list)) == NULL) { + rte_errno = E_RTE_NO_TAILQ; + return NULL; + } + + /* Check for valid parameters */ + if ((params == NULL) || + (params->entries > RTE_HASH_ENTRIES_MAX) || + (params->bucket_entries > RTE_HASH_BUCKET_ENTRIES_MAX) || + (params->entries < params->bucket_entries) || + !rte_is_power_of_2(params->entries) || + !rte_is_power_of_2(params->bucket_entries) || + (params->key_len == 0) || + (params->key_len > RTE_HASH_KEY_LENGTH_MAX)) { + rte_errno = EINVAL; + RTE_LOG(ERR, HASH, "rte_hash_create has invalid parameters\n"); + return NULL; + } + + snprintf(hash_name, sizeof(hash_name), "HT_%s", params->name); + + /* Calculate hash dimensions */ + num_buckets = params->entries / params->bucket_entries; + sig_bucket_size = align_size(params->bucket_entries * + sizeof(hash_sig_t), SIG_BUCKET_ALIGNMENT); + key_size = align_size(params->key_len, KEY_ALIGNMENT); + + hash_tbl_size = align_size(sizeof(struct rte_hash), RTE_CACHE_LINE_SIZE); + sig_tbl_size = align_size(num_buckets * sig_bucket_size, + RTE_CACHE_LINE_SIZE); + key_tbl_size = align_size(num_buckets * key_size * + params->bucket_entries, RTE_CACHE_LINE_SIZE); + + /* Total memory required for hash context */ + mem_size = hash_tbl_size + sig_tbl_size + key_tbl_size; + + rte_rwlock_write_lock(RTE_EAL_TAILQ_RWLOCK); + + /* guarantee there's no existing */ + TAILQ_FOREACH(te, hash_list, next) { + h = (struct rte_hash *) te->data; + if (strncmp(params->name, h->name, RTE_HASH_NAMESIZE) == 0) + break; + } + if (te != NULL) + goto exit; + + te = rte_zmalloc("HASH_TAILQ_ENTRY", sizeof(*te), 0); + if (te == NULL) { + RTE_LOG(ERR, HASH, "tailq entry allocation failed\n"); + goto exit; + } + + h = (struct rte_hash *)rte_zmalloc_socket(hash_name, mem_size, + RTE_CACHE_LINE_SIZE, params->socket_id); + if (h == NULL) { + RTE_LOG(ERR, HASH, "memory allocation failed\n"); + rte_free(te); + goto exit; + } + + /* Setup hash context */ + snprintf(h->name, sizeof(h->name), "%s", params->name); + h->entries = params->entries; + h->bucket_entries = params->bucket_entries; + h->key_len = params->key_len; + h->hash_func_init_val = params->hash_func_init_val; + h->num_buckets = num_buckets; + h->bucket_bitmask = h->num_buckets - 1; + h->sig_msb = 1 << (sizeof(hash_sig_t) * 8 - 1); + h->sig_tbl = (uint8_t *)h + hash_tbl_size; + h->sig_tbl_bucket_size = sig_bucket_size; + h->key_tbl = h->sig_tbl + sig_tbl_size; + h->key_tbl_key_size = key_size; + h->hash_func = (params->hash_func == NULL) ? + DEFAULT_HASH_FUNC : params->hash_func; + + te->data = (void *) h; + + TAILQ_INSERT_TAIL(hash_list, te, next); + +exit: + rte_rwlock_write_unlock(RTE_EAL_TAILQ_RWLOCK); + + return h; +} + +void +rte_hash_free(struct rte_hash *h) +{ + struct rte_tailq_entry *te; + struct rte_hash_list *hash_list; + + if (h == NULL) + return; + + /* check that we have an initialised tail queue */ + if ((hash_list = + RTE_TAILQ_LOOKUP_BY_IDX(RTE_TAILQ_HASH, rte_hash_list)) == NULL) { + rte_errno = E_RTE_NO_TAILQ; + return; + } + + rte_rwlock_write_lock(RTE_EAL_TAILQ_RWLOCK); + + /* find out tailq entry */ + TAILQ_FOREACH(te, hash_list, next) { + if (te->data == (void *) h) + break; + } + + if (te == NULL) { + rte_rwlock_write_unlock(RTE_EAL_TAILQ_RWLOCK); + return; + } + + TAILQ_REMOVE(hash_list, te, next); + + rte_rwlock_write_unlock(RTE_EAL_TAILQ_RWLOCK); + + rte_free(h); + rte_free(te); +} + +static inline int32_t +__rte_hash_add_key_with_hash(const struct rte_hash *h, + const void *key, hash_sig_t sig) +{ + hash_sig_t *sig_bucket; + uint8_t *key_bucket; + uint32_t bucket_index, i; + int32_t pos; + + /* Get the hash signature and bucket index */ + sig |= h->sig_msb; + bucket_index = sig & h->bucket_bitmask; + sig_bucket = get_sig_tbl_bucket(h, bucket_index); + key_bucket = get_key_tbl_bucket(h, bucket_index); + + /* Check if key is already present in the hash */ + for (i = 0; i < h->bucket_entries; i++) { + if ((sig == sig_bucket[i]) && + likely(memcmp(key, get_key_from_bucket(h, key_bucket, i), + h->key_len) == 0)) { + return bucket_index * h->bucket_entries + i; + } + } + + /* Check if any free slot within the bucket to add the new key */ + pos = find_first(NULL_SIGNATURE, sig_bucket, h->bucket_entries); + + if (unlikely(pos < 0)) + return -ENOSPC; + + /* Add the new key to the bucket */ + sig_bucket[pos] = sig; + rte_memcpy(get_key_from_bucket(h, key_bucket, pos), key, h->key_len); + return bucket_index * h->bucket_entries + pos; +} + +int32_t +rte_hash_add_key_with_hash(const struct rte_hash *h, + const void *key, hash_sig_t sig) +{ + RETURN_IF_TRUE(((h == NULL) || (key == NULL)), -EINVAL); + return __rte_hash_add_key_with_hash(h, key, sig); +} + +int32_t +rte_hash_add_key(const struct rte_hash *h, const void *key) +{ + RETURN_IF_TRUE(((h == NULL) || (key == NULL)), -EINVAL); + return __rte_hash_add_key_with_hash(h, key, rte_hash_hash(h, key)); +} + +static inline int32_t +__rte_hash_del_key_with_hash(const struct rte_hash *h, + const void *key, hash_sig_t sig) +{ + hash_sig_t *sig_bucket; + uint8_t *key_bucket; + uint32_t bucket_index, i; + + /* Get the hash signature and bucket index */ + sig = sig | h->sig_msb; + bucket_index = sig & h->bucket_bitmask; + sig_bucket = get_sig_tbl_bucket(h, bucket_index); + key_bucket = get_key_tbl_bucket(h, bucket_index); + + /* Check if key is already present in the hash */ + for (i = 0; i < h->bucket_entries; i++) { + if ((sig == sig_bucket[i]) && + likely(memcmp(key, get_key_from_bucket(h, key_bucket, i), + h->key_len) == 0)) { + sig_bucket[i] = NULL_SIGNATURE; + return bucket_index * h->bucket_entries + i; + } + } + + return -ENOENT; +} + +int32_t +rte_hash_del_key_with_hash(const struct rte_hash *h, + const void *key, hash_sig_t sig) +{ + RETURN_IF_TRUE(((h == NULL) || (key == NULL)), -EINVAL); + return __rte_hash_del_key_with_hash(h, key, sig); +} + +int32_t +rte_hash_del_key(const struct rte_hash *h, const void *key) +{ + RETURN_IF_TRUE(((h == NULL) || (key == NULL)), -EINVAL); + return __rte_hash_del_key_with_hash(h, key, rte_hash_hash(h, key)); +} + +static inline int32_t +__rte_hash_lookup_with_hash(const struct rte_hash *h, + const void *key, hash_sig_t sig) +{ + hash_sig_t *sig_bucket; + uint8_t *key_bucket; + uint32_t bucket_index, i; + + /* Get the hash signature and bucket index */ + sig |= h->sig_msb; + bucket_index = sig & h->bucket_bitmask; + sig_bucket = get_sig_tbl_bucket(h, bucket_index); + key_bucket = get_key_tbl_bucket(h, bucket_index); + + /* Check if key is already present in the hash */ + for (i = 0; i < h->bucket_entries; i++) { + if ((sig == sig_bucket[i]) && + likely(memcmp(key, get_key_from_bucket(h, key_bucket, i), + h->key_len) == 0)) { + return bucket_index * h->bucket_entries + i; + } + } + + return -ENOENT; +} + +int32_t +rte_hash_lookup_with_hash(const struct rte_hash *h, + const void *key, hash_sig_t sig) +{ + RETURN_IF_TRUE(((h == NULL) || (key == NULL)), -EINVAL); + return __rte_hash_lookup_with_hash(h, key, sig); +} + +int32_t +rte_hash_lookup(const struct rte_hash *h, const void *key) +{ + RETURN_IF_TRUE(((h == NULL) || (key == NULL)), -EINVAL); + return __rte_hash_lookup_with_hash(h, key, rte_hash_hash(h, key)); +} + +int +rte_hash_lookup_bulk(const struct rte_hash *h, const void **keys, + uint32_t num_keys, int32_t *positions) +{ + uint32_t i, j, bucket_index; + hash_sig_t sigs[RTE_HASH_LOOKUP_BULK_MAX]; + + RETURN_IF_TRUE(((h == NULL) || (keys == NULL) || (num_keys == 0) || + (num_keys > RTE_HASH_LOOKUP_BULK_MAX) || + (positions == NULL)), -EINVAL); + + /* Get the hash signature and bucket index */ + for (i = 0; i < num_keys; i++) { + sigs[i] = h->hash_func(keys[i], h->key_len, + h->hash_func_init_val) | h->sig_msb; + bucket_index = sigs[i] & h->bucket_bitmask; + + /* Pre-fetch relevant buckets */ + rte_prefetch1((void *) get_sig_tbl_bucket(h, bucket_index)); + rte_prefetch1((void *) get_key_tbl_bucket(h, bucket_index)); + } + + /* Check if key is already present in the hash */ + for (i = 0; i < num_keys; i++) { + bucket_index = sigs[i] & h->bucket_bitmask; + hash_sig_t *sig_bucket = get_sig_tbl_bucket(h, bucket_index); + uint8_t *key_bucket = get_key_tbl_bucket(h, bucket_index); + + positions[i] = -ENOENT; + + for (j = 0; j < h->bucket_entries; j++) { + if ((sigs[i] == sig_bucket[j]) && + likely(memcmp(keys[i], + get_key_from_bucket(h, key_bucket, j), + h->key_len) == 0)) { + positions[i] = bucket_index * + h->bucket_entries + j; + break; + } + } + } + + return 0; +} diff --git a/src/dpdk_lib18/librte_hash/rte_hash.h b/src/dpdk_lib18/librte_hash/rte_hash.h new file mode 100755 index 00000000..2ecaf1ad --- /dev/null +++ b/src/dpdk_lib18/librte_hash/rte_hash.h @@ -0,0 +1,310 @@ +/*- + * 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 _RTE_HASH_H_ +#define _RTE_HASH_H_ + +/** + * @file + * + * RTE Hash Table + */ + +#include <stdint.h> +#include <sys/queue.h> + +#ifdef __cplusplus +extern "C" { +#endif + +/** Maximum size of hash table that can be created. */ +#define RTE_HASH_ENTRIES_MAX (1 << 26) + +/** Maximum bucket size that can be created. */ +#define RTE_HASH_BUCKET_ENTRIES_MAX 16 + +/** Maximum length of key that can be used. */ +#define RTE_HASH_KEY_LENGTH_MAX 64 + +/** Max number of keys that can be searched for using rte_hash_lookup_multi. */ +#define RTE_HASH_LOOKUP_BULK_MAX 16 +#define RTE_HASH_LOOKUP_MULTI_MAX RTE_HASH_LOOKUP_BULK_MAX + +/** Max number of characters in hash name.*/ +#define RTE_HASH_NAMESIZE 32 + +/** Signature of key that is stored internally. */ +typedef uint32_t hash_sig_t; + +/** Type of function that can be used for calculating the hash value. */ +typedef uint32_t (*rte_hash_function)(const void *key, uint32_t key_len, + uint32_t init_val); + +/** + * Parameters used when creating the hash table. The total table entries and + * bucket entries must be a power of 2. + */ +struct rte_hash_parameters { + const char *name; /**< Name of the hash. */ + uint32_t entries; /**< Total hash table entries. */ + uint32_t bucket_entries; /**< Bucket entries. */ + uint32_t key_len; /**< Length of hash key. */ + rte_hash_function hash_func; /**< Function used to calculate hash. */ + uint32_t hash_func_init_val; /**< Init value used by hash_func. */ + int socket_id; /**< NUMA Socket ID for memory. */ +}; + +/** A hash table structure. */ +struct rte_hash { + char name[RTE_HASH_NAMESIZE]; /**< Name of the hash. */ + uint32_t entries; /**< Total table entries. */ + uint32_t bucket_entries; /**< Bucket entries. */ + uint32_t key_len; /**< Length of hash key. */ + rte_hash_function hash_func; /**< Function used to calculate hash. */ + uint32_t hash_func_init_val; /**< Init value used by hash_func. */ + uint32_t num_buckets; /**< Number of buckets in table. */ + uint32_t bucket_bitmask; /**< Bitmask for getting bucket index + from hash signature. */ + hash_sig_t sig_msb; /**< MSB is always set in valid signatures. */ + uint8_t *sig_tbl; /**< Flat array of hash signature buckets. */ + uint32_t sig_tbl_bucket_size; /**< Signature buckets may be padded for + alignment reasons, and this is the + bucket size used by sig_tbl. */ + uint8_t *key_tbl; /**< Flat array of key value buckets. */ + uint32_t key_tbl_key_size; /**< Keys may be padded for alignment + reasons, and this is the key size + used by key_tbl. */ +}; + +/** + * Create a new hash table. + * + * @param params + * Parameters used to create and initialise the hash table. + * @return + * Pointer to hash table structure that is used in future hash table + * operations, or NULL on error, with error code set in rte_errno. + * Possible rte_errno errors include: + * - E_RTE_NO_CONFIG - function could not get pointer to rte_config structure + * - E_RTE_SECONDARY - function was called from a secondary process instance + * - E_RTE_NO_TAILQ - no tailq list could be got for the hash table list + * - ENOENT - missing entry + * - EINVAL - invalid parameter 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 rte_hash * +rte_hash_create(const struct rte_hash_parameters *params); + + +/** + * Find an existing hash table object and return a pointer to it. + * + * @param name + * Name of the hash table as passed to rte_hash_create() + * @return + * Pointer to hash table or NULL if object not found + * with rte_errno set appropriately. Possible rte_errno values include: + * - ENOENT - value not available for return + */ +struct rte_hash * +rte_hash_find_existing(const char *name); + +/** + * De-allocate all memory used by hash table. + * @param h + * Hash table to free + */ +void +rte_hash_free(struct rte_hash *h); + +/** + * 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 +rte_hash_add_key(const struct rte_hash *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 + * Hash value 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 +rte_hash_add_key_with_hash(const struct rte_hash *h, + const void *key, hash_sig_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 +rte_hash_del_key(const struct rte_hash *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 + * 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 +rte_hash_del_key_with_hash(const struct rte_hash *h, + const void *key, hash_sig_t sig); + + +/** + * 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 +rte_hash_lookup(const struct rte_hash *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 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 +rte_hash_lookup_with_hash(const struct rte_hash *h, + const void *key, hash_sig_t sig); + + +/** + * Calc a hash value by key. This operation is not multi-process safe. + * + * @param h + * Hash table to look in. + * @param key + * Key to find. + * @return + * - hash value + */ +static inline hash_sig_t +rte_hash_hash(const struct rte_hash *h, const void *key) +{ + /* calc hash result by key */ + return h->hash_func(key, h->key_len, h->hash_func_init_val); +} + +#define rte_hash_lookup_multi rte_hash_lookup_bulk +/** + * 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 RTE_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 +rte_hash_lookup_bulk(const struct rte_hash *h, const void **keys, + uint32_t num_keys, int32_t *positions); +#ifdef __cplusplus +} +#endif + +#endif /* _RTE_HASH_H_ */ diff --git a/src/dpdk_lib18/librte_hash/rte_hash_crc.h b/src/dpdk_lib18/librte_hash/rte_hash_crc.h new file mode 100755 index 00000000..b48b0db1 --- /dev/null +++ b/src/dpdk_lib18/librte_hash/rte_hash_crc.h @@ -0,0 +1,110 @@ +/*- + * 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 _RTE_HASH_CRC_H_ +#define _RTE_HASH_CRC_H_ + +/** + * @file + * + * RTE CRC Hash + */ + +#ifdef __cplusplus +extern "C" { +#endif + +#include <stdint.h> +#include <nmmintrin.h> + +/** + * Use single crc32 instruction to perform a hash on a 4 byte value. + * + * @param data + * Data to perform hash on. + * @param init_val + * Value to initialise hash generator. + * @return + * 32bit calculated hash value. + */ +static inline uint32_t +rte_hash_crc_4byte(uint32_t data, uint32_t init_val) +{ + return _mm_crc32_u32(init_val, data); +} + +/** + * Use crc32 instruction to perform a hash. + * + * @param data + * Data to perform hash on. + * @param data_len + * How many bytes to use to calculate hash value. + * @param init_val + * Value to initialise hash generator. + * @return + * 32bit calculated hash value. + */ +static inline uint32_t +rte_hash_crc(const void *data, uint32_t data_len, uint32_t init_val) +{ + unsigned i; + uint32_t temp = 0; + const uint32_t *p32 = (const uint32_t *)data; + + for (i = 0; i < data_len / 4; i++) { + init_val = rte_hash_crc_4byte(*p32++, init_val); + } + + switch (3 - (data_len & 0x03)) { + case 0: + temp |= *((const uint8_t *)p32 + 2) << 16; + /* Fallthrough */ + case 1: + temp |= *((const uint8_t *)p32 + 1) << 8; + /* Fallthrough */ + case 2: + temp |= *((const uint8_t *)p32); + init_val = rte_hash_crc_4byte(temp, init_val); + default: + break; + } + + return init_val; +} + +#ifdef __cplusplus +} +#endif + +#endif /* _RTE_HASH_CRC_H_ */ diff --git a/src/dpdk_lib18/librte_hash/rte_jhash.h b/src/dpdk_lib18/librte_hash/rte_jhash.h new file mode 100755 index 00000000..a4bf5a1b --- /dev/null +++ b/src/dpdk_lib18/librte_hash/rte_jhash.h @@ -0,0 +1,253 @@ +/*- + * 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 _RTE_JHASH_H +#define _RTE_JHASH_H + +/** + * @file + * + * jhash functions. + */ + +#ifdef __cplusplus +extern "C" { +#endif + +#include <stdint.h> + +/* jhash.h: Jenkins hash support. + * + * Copyright (C) 1996 Bob Jenkins (bob_jenkins@burtleburtle.net) + * + * http://burtleburtle.net/bob/hash/ + * + * These are the credits from Bob's sources: + * + * lookup2.c, by Bob Jenkins, December 1996, Public Domain. + * hash(), hash2(), hash3, and mix() are externally useful functions. + * Routines to test the hash are included if SELF_TEST is defined. + * You can use this free for any purpose. It has no warranty. + * + * $FreeBSD$ + */ + +/** @internal Internal function. NOTE: Arguments are modified. */ +#define __rte_jhash_mix(a, b, c) do { \ + a -= b; a -= c; a ^= (c>>13); \ + b -= c; b -= a; b ^= (a<<8); \ + c -= a; c -= b; c ^= (b>>13); \ + a -= b; a -= c; a ^= (c>>12); \ + b -= c; b -= a; b ^= (a<<16); \ + c -= a; c -= b; c ^= (b>>5); \ + a -= b; a -= c; a ^= (c>>3); \ + b -= c; b -= a; b ^= (a<<10); \ + c -= a; c -= b; c ^= (b>>15); \ +} while (0) + +/** The golden ratio: an arbitrary value. */ +#define RTE_JHASH_GOLDEN_RATIO 0x9e3779b9 + +/** + * The most generic version, hashes an arbitrary sequence + * of bytes. No alignment or length assumptions are made about + * the input key. + * + * @param key + * Key to calculate hash of. + * @param length + * Length of key in bytes. + * @param initval + * Initialising value of hash. + * @return + * Calculated hash value. + */ +static inline uint32_t +rte_jhash(const void *key, uint32_t length, uint32_t initval) +{ + uint32_t a, b, c, len; + const uint8_t *k = (const uint8_t *)key; + const uint32_t *k32 = (const uint32_t *)key; + + len = length; + a = b = RTE_JHASH_GOLDEN_RATIO; + c = initval; + + while (len >= 12) { + a += k32[0]; + b += k32[1]; + c += k32[2]; + + __rte_jhash_mix(a,b,c); + + k += (3 * sizeof(uint32_t)), k32 += 3; + len -= (3 * sizeof(uint32_t)); + } + + c += length; + switch (len) { + case 11: c += ((uint32_t)k[10] << 24); + case 10: c += ((uint32_t)k[9] << 16); + case 9 : c += ((uint32_t)k[8] << 8); + case 8 : b += ((uint32_t)k[7] << 24); + case 7 : b += ((uint32_t)k[6] << 16); + case 6 : b += ((uint32_t)k[5] << 8); + case 5 : b += k[4]; + case 4 : a += ((uint32_t)k[3] << 24); + case 3 : a += ((uint32_t)k[2] << 16); + case 2 : a += ((uint32_t)k[1] << 8); + case 1 : a += k[0]; + default: break; + }; + + __rte_jhash_mix(a,b,c); + + return c; +} + +/** + * A special optimized version that handles 1 or more of uint32_ts. + * The length parameter here is the number of uint32_ts in the key. + * + * @param k + * Key to calculate hash of. + * @param length + * Length of key in units of 4 bytes. + * @param initval + * Initialising value of hash. + * @return + * Calculated hash value. + */ +static inline uint32_t +rte_jhash2(const uint32_t *k, uint32_t length, uint32_t initval) +{ + uint32_t a, b, c, len; + + a = b = RTE_JHASH_GOLDEN_RATIO; + c = initval; + len = length; + + while (len >= 3) { + a += k[0]; + b += k[1]; + c += k[2]; + __rte_jhash_mix(a, b, c); + k += 3; len -= 3; + } + + c += length * 4; + + switch (len) { + case 2 : b += k[1]; + case 1 : a += k[0]; + default: break; + }; + + __rte_jhash_mix(a,b,c); + + return c; +} + + +/** + * A special ultra-optimized versions that knows it is hashing exactly + * 3 words. + * + * @param a + * First word to calcuate hash of. + * @param b + * Second word to calcuate hash of. + * @param c + * Third word to calcuate hash of. + * @param initval + * Initialising value of hash. + * @return + * Calculated hash value. + */ +static inline uint32_t +rte_jhash_3words(uint32_t a, uint32_t b, uint32_t c, uint32_t initval) +{ + a += RTE_JHASH_GOLDEN_RATIO; + b += RTE_JHASH_GOLDEN_RATIO; + c += initval; + + __rte_jhash_mix(a, b, c); + + /* + * NOTE: In particular the "c += length; __rte_jhash_mix(a,b,c);" + * normally done at the end is not done here. + */ + return c; +} + +/** + * A special ultra-optimized versions that knows it is hashing exactly + * 2 words. + * + * @param a + * First word to calcuate hash of. + * @param b + * Second word to calcuate hash of. + * @param initval + * Initialising value of hash. + * @return + * Calculated hash value. + */ +static inline uint32_t +rte_jhash_2words(uint32_t a, uint32_t b, uint32_t initval) +{ + return rte_jhash_3words(a, b, 0, initval); +} + +/** + * A special ultra-optimized versions that knows it is hashing exactly + * 1 word. + * + * @param a + * Word to calcuate hash of. + * @param initval + * Initialising value of hash. + * @return + * Calculated hash value. + */ +static inline uint32_t +rte_jhash_1word(uint32_t a, uint32_t initval) +{ + return rte_jhash_3words(a, 0, 0, initval); +} + +#ifdef __cplusplus +} +#endif + +#endif /* _RTE_JHASH_H */ |