From 7595afa4d30097c1177b69257118d8ad89a539be Mon Sep 17 00:00:00 2001 From: Christian Ehrhardt Date: Tue, 16 May 2017 14:51:32 +0200 Subject: Imported Upstream version 17.05 Change-Id: Id1e419c5a214e4a18739663b91f0f9a549f1fdc6 Signed-off-by: Christian Ehrhardt --- lib/librte_efd/rte_efd.h | 308 +++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 308 insertions(+) create mode 100644 lib/librte_efd/rte_efd.h (limited to 'lib/librte_efd/rte_efd.h') diff --git a/lib/librte_efd/rte_efd.h b/lib/librte_efd/rte_efd.h new file mode 100644 index 00000000..15968635 --- /dev/null +++ b/lib/librte_efd/rte_efd.h @@ -0,0 +1,308 @@ +/*- + * BSD LICENSE + * + * Copyright(c) 2016-2017 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_EFD_H_ +#define _RTE_EFD_H_ + +/** + * @file + * + * RTE EFD Table + */ + +#include + +#ifdef __cplusplus +extern "C" { +#endif + +/************************************************************************* + * User selectable constants + *************************************************************************/ + +/* + * If possible, best lookup performance will be achieved by ensuring that + * the entire table fits in the L3 cache. + * + * Some formulas for calculating various sizes are listed below: + * + * # of chunks = + * 2 ^ (ceiling(log2((requested # of rules) / + * (EFD_CHUNK_NUM_GROUPS * EFD_TARGET_GROUP_NUM_RULES)))) + * + * Target # of rules = (# of chunks) * EFD_CHUNK_NUM_GROUPS * + * EFD_TARGET_GROUP_NUM_RULES + * + * Group Size (in bytes) = 4 (per value bit) + * + * Table size (in bytes) = RTE_EFD_VALUE_NUM_BITS * (# of chunks) * + * EFD_CHUNK_NUM_GROUPS * (group size) + */ + +/** + * !!! This parameter should be adjusted for your application !!! + * + * This parameter adjusts the number of bits of value that can be + * stored in the table. + * For example, setting the number of bits to 3 will allow storing 8 values + * in the table (between 0 and 7). + * + * This number directly affects the performance of both lookups and insertion. + * In general, performance decreases as more bits are stored in the table. + * + * This number is directly proportional to the size of the online region + * used for lookups. + * + * Note that due to the way the CPU operates on memory, best lookup performance + * will be achieved when RTE_EFD_VALUE_NUM_BITS is a multiple of 8. + * These values align the hash indexes on 16-byte boundaries. + * The greatest performance drop is moving from 8->9 bits, 16->17 bits, etc. + * + * This value must be between 1 and 32 + */ +#ifndef RTE_EFD_VALUE_NUM_BITS +#define RTE_EFD_VALUE_NUM_BITS (8) +#endif + +/* + * EFD_TARGET_GROUP_NUM_RULES: + * Adjusts how many groups/chunks are allocated at table creation time + * to support the requested number of rules. Higher values pack entries + * more tightly in memory, resulting in a smaller memory footprint + * for the online table. + * This comes at the cost of lower insert/update performance. + * + * EFD_MAX_GROUP_NUM_RULES: + * This adjusts the amount of offline memory allocated to store key/value + * pairs for the table. The recommended numbers are upper-bounds for + * this parameter + * - any higher and it becomes very unlikely that a perfect hash function + * can be found for that group size. This value should be at + * least 40% larger than EFD_TARGET_GROUP_NUM_RULES + * + * Recommended values for various lookuptable and hashfunc sizes are: + * + * HASH_FUNC_SIZE = 16, LOOKUPTBL_SIZE = 16: + * EFD_TARGET_GROUP_NUM_RULES = 22 + * EFD_MAX_GROUP_NUM_RULES = 28 + */ +#define EFD_TARGET_GROUP_NUM_RULES (22) +#define EFD_MAX_GROUP_NUM_RULES (28LU) + +#define EFD_MIN_BALANCED_NUM_RULES 5 + +/** + * Maximum number of keys that can be looked up in one call to efd_lookup_bulk + */ +#ifndef RTE_EFD_BURST_MAX +#define RTE_EFD_BURST_MAX (32) +#endif + +/** Maximum number of characters in efd name.*/ +#define RTE_EFD_NAMESIZE 32 + +#if (RTE_EFD_VALUE_NUM_BITS > 0 && RTE_EFD_VALUE_NUM_BITS <= 8) +typedef uint8_t efd_value_t; +#elif (RTE_EFD_VALUE_NUM_BITS > 8 && RTE_EFD_VALUE_NUM_BITS <= 16) +typedef uint16_t efd_value_t; +#elif (RTE_EFD_VALUE_NUM_BITS > 16 && RTE_EFD_VALUE_NUM_BITS <= 32) +typedef uint32_t efd_value_t; +#else +#error("RTE_EFD_VALUE_NUM_BITS must be in the range [1:32]") +#endif + +#define EFD_LOOKUPTBL_SHIFT (32 - 4) +typedef uint16_t efd_lookuptbl_t; +typedef uint16_t efd_hashfunc_t; + +/** + * Creates an EFD table with a single offline region and multiple per-socket + * internally-managed copies of the online table used for lookups + * + * @param name + * EFD table name + * @param max_num_rules + * Minimum number of rules the table should be sized to hold. + * Will be rounded up to the next smallest valid table size + * @param key_len + * Length of the key + * @param online_cpu_socket_bitmask + * Bitmask specifying which sockets should get a copy of the online table. + * LSB = socket 0, etc. + * @param offline_cpu_socket + * Identifies the socket where the offline table will be allocated + * (and most efficiently accessed in the case of updates/insertions) + * + * @return + * EFD table, or NULL if table allocation failed or the bitmask is invalid + */ +struct rte_efd_table * +rte_efd_create(const char *name, uint32_t max_num_rules, uint32_t key_len, + uint8_t online_cpu_socket_bitmask, uint8_t offline_cpu_socket); + +/** + * Releases the resources from an EFD table + * + * @param table + * Table to free + */ +void +rte_efd_free(struct rte_efd_table *table); + +/** + * Find an existing EFD table object and return a pointer to it. + * + * @param name + * Name of the EFD table as passed to rte_efd_create() + * @return + * Pointer to EFD 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_efd_table* +rte_efd_find_existing(const char *name); + +#define RTE_EFD_UPDATE_WARN_GROUP_FULL (1) +#define RTE_EFD_UPDATE_NO_CHANGE (2) +#define RTE_EFD_UPDATE_FAILED (3) + +/** + * Computes an updated table entry for the supplied key/value pair. + * The update is then immediately applied to the provided table and + * all socket-local copies of the chunks are updated. + * This operation is not multi-thread safe + * and should only be called one from thread. + * + * @param table + * EFD table to reference + * @param socket_id + * Socket ID to use to lookup existing value (ideally caller's socket id) + * @param key + * EFD table key to modify + * @param value + * Value to associate with the key + * + * @return + * RTE_EFD_UPDATE_WARN_GROUP_FULL + * Operation is insert, and the last available space in the + * key's group was just used + * Future inserts may fail as groups fill up + * This operation was still successful, and entry contains a valid update + * RTE_EFD_UPDATE_FAILED + * Either the EFD failed to find a suitable perfect hash or the group was full + * This is a fatal error, and the table is now in an indeterminite state + * RTE_EFD_UPDATE_NO_CHANGE + * Operation resulted in no change to the table (same value already exists) + * 0 - success + */ +int +rte_efd_update(struct rte_efd_table *table, unsigned int socket_id, + const void *key, efd_value_t value); + +/** + * Removes any value currently associated with the specified key from the table + * This operation is not multi-thread safe + * and should only be called from one thread. + * + * @param table + * EFD table to reference + * @param socket_id + * Socket ID to use to lookup existing value (ideally caller's socket id) + * @param key + * EFD table key to delete + * @param prev_value + * If not NULL, will store the previous value here before deleting it + * + * @return + * 0 - successfully found and deleted the key + * nonzero otherwise + */ +int +rte_efd_delete(struct rte_efd_table *table, unsigned int socket_id, + const void *key, efd_value_t *prev_value); + +/** + * Looks up the value associated with a key + * This operation is multi-thread safe. + * + * NOTE: Lookups will *always* succeed - this is a property of + * using a perfect hash table. + * If the specified key was never inserted, a pseudorandom answer will be returned. + * There is no way to know based on the lookup if the key was ever inserted + * originally, so this must be tracked elsewhere. + * + * @param table + * EFD table to reference + * @param socket_id + * Socket ID to use to lookup existing value (ideally caller's socket id) + * @param key + * EFD table key to look up + * + * @return + * Value associated with the key, or random junk if they key was never inserted + */ +efd_value_t +rte_efd_lookup(const struct rte_efd_table *table, unsigned int socket_id, + const void *key); + +/** + * Looks up the value associated with several keys. + * This operation is multi-thread safe. + * + * NOTE: Lookups will *always* succeed - this is a property of + * using a perfect hash table. + * If the specified key was never inserted, a pseudorandom answer will be returned. + * There is no way to know based on the lookup if the key was ever inserted + * originally, so this must be tracked elsewhere. + * + * @param table + * EFD table to reference + * @param socket_id + * Socket ID to use to lookup existing value (ideally caller's socket id) + * @param num_keys + * Number of keys in the key_list array, must be less than RTE_EFD_BURST_MAX + * @param key_list + * Array of num_keys pointers which point to keys to look up + * @param value_list + * Array of size num_keys where lookup values will be stored + */ +void +rte_efd_lookup_bulk(const struct rte_efd_table *table, unsigned int socket_id, + int num_keys, const void **key_list, + efd_value_t *value_list); + +#ifdef __cplusplus +} +#endif + +#endif /* _RTE_EFD_H_ */ -- cgit 1.2.3-korg