X-Git-Url: http://git.droids-corp.org/?a=blobdiff_plain;f=lib%2Flibrte_hash%2Frte_cuckoo_hash.h;h=85be49d3bbe7a1b1c57dfc79548d61d39b53cbc7;hb=b334236abd8dfeea625525de548b35b40cb68c3b;hp=f75392d27b9bf5c53c77500b5be98d362c392f65;hpb=4f4cd8717e48177a01e806cfbb9a86ed13ac1fbe;p=dpdk.git diff --git a/lib/librte_hash/rte_cuckoo_hash.h b/lib/librte_hash/rte_cuckoo_hash.h index f75392d27b..85be49d3bb 100644 --- a/lib/librte_hash/rte_cuckoo_hash.h +++ b/lib/librte_hash/rte_cuckoo_hash.h @@ -1,34 +1,6 @@ -/*- - * BSD LICENSE - * - * Copyright(c) 2016 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. +/* SPDX-License-Identifier: BSD-3-Clause + * Copyright(c) 2016 Intel Corporation + * Copyright(c) 2018 Arm Limited */ /* rte_cuckoo_hash.h @@ -57,15 +29,20 @@ #define RETURN_IF_TRUE(cond, retval) #endif -/* Hash function used if none is specified */ -#if defined(RTE_ARCH_X86) || defined(RTE_MACHINE_CPUFLAG_CRC32) -#include -#define DEFAULT_HASH_FUNC rte_hash_crc +#if defined(RTE_LIBRTE_HASH_DEBUG) +#define ERR_IF_TRUE(cond, fmt, args...) do { \ + if (cond) { \ + RTE_LOG(ERR, HASH, fmt, ##args); \ + return; \ + } \ +} while (0) #else -#include -#define DEFAULT_HASH_FUNC rte_jhash +#define ERR_IF_TRUE(cond, fmt, args...) #endif +#include +#include + #if defined(RTE_ARCH_X86) || defined(RTE_ARCH_ARM64) /* * All different options to select a key compare function, @@ -123,15 +100,14 @@ const rte_hash_cmp_eq_t cmp_jump_table[NUM_KEY_CMP_CASES] = { #endif -enum add_key_case { - ADD_KEY_SINGLEWRITER = 0, - ADD_KEY_MULTIWRITER, - ADD_KEY_MULTIWRITER_TM, -}; /** Number of items per bucket. */ #define RTE_HASH_BUCKET_ENTRIES 8 +#if !RTE_IS_POWER_OF_2(RTE_HASH_BUCKET_ENTRIES) +#error RTE_HASH_BUCKET_ENTRIES must be a power of 2 +#endif + #define NULL_SIGNATURE 0 #define EMPTY_SLOT 0 @@ -140,8 +116,6 @@ enum add_key_case { #define LCORE_CACHE_SIZE 64 -#define RTE_HASH_MAX_PUSHES 100 - #define RTE_HASH_BFS_QUEUE_MAX_LEN 1000 #define RTE_XABORT_CUCKOO_PATH_INVALIDED 0x4 @@ -150,7 +124,7 @@ enum add_key_case { struct lcore_cache { unsigned len; /**< Cache len */ - void *objs[LCORE_CACHE_SIZE]; /**< Cache objects */ + uint32_t objs[LCORE_CACHE_SIZE]; /**< Cache objects */ } __rte_cache_aligned; /* Structure that stores key-value pair */ @@ -161,25 +135,25 @@ struct rte_hash_key { }; /* Variable key size */ char key[0]; -} __attribute__((aligned(KEY_ALIGNMENT))); +}; /* All different signature compare functions */ enum rte_hash_sig_compare_function { RTE_HASH_COMPARE_SCALAR = 0, RTE_HASH_COMPARE_SSE, - RTE_HASH_COMPARE_AVX2, + RTE_HASH_COMPARE_NEON, RTE_HASH_COMPARE_NUM }; /** Bucket structure */ struct rte_hash_bucket { - hash_sig_t sig_current[RTE_HASH_BUCKET_ENTRIES]; + uint16_t sig_current[RTE_HASH_BUCKET_ENTRIES]; uint32_t key_idx[RTE_HASH_BUCKET_ENTRIES]; - hash_sig_t sig_alt[RTE_HASH_BUCKET_ENTRIES]; - uint8_t flag[RTE_HASH_BUCKET_ENTRIES]; + + void *next; } __rte_cache_aligned; /** A hash table structure. */ @@ -190,18 +164,38 @@ struct rte_hash { struct rte_ring *free_slots; /**< Ring that stores all indexes of the free slots in the key table */ - uint8_t hw_trans_mem_support; - /**< Hardware transactional memory support */ + struct lcore_cache *local_free_slots; /**< Local cache per lcore, storing some indexes of the free slots */ - enum add_key_case add_key; /**< Multi-writer hash add behavior */ - rte_spinlock_t *multiwriter_lock; /**< Multi-writer spinlock for w/o TM */ + /* RCU config */ + struct rte_hash_rcu_config *hash_rcu_cfg; + /**< HASH RCU QSBR configuration structure */ + struct rte_rcu_qsbr_dq *dq; /**< RCU QSBR defer queue. */ /* Fields used in lookup */ uint32_t key_len __rte_cache_aligned; /**< Length of hash key. */ + uint8_t hw_trans_mem_support; + /**< If hardware transactional memory is used. */ + uint8_t use_local_cache; + /**< If multi-writer support is enabled, use local cache + * to allocate key-store slots. + */ + uint8_t readwrite_concur_support; + /**< If read-write concurrency support is enabled */ + uint8_t ext_table_support; /**< Enable extendable bucket table */ + uint8_t no_free_on_del; + /**< If key index should be freed on calling rte_hash_del_xxx APIs. + * If this is set, rte_hash_free_key_with_position must be called to + * free the key index associated with the deleted entry. + * This flag is enabled by default. + */ + uint8_t readwrite_concur_lf_support; + /**< If read-write concurrency lock free support is enabled */ + uint8_t writer_takes_lock; + /**< Indicates if the writer threads need to take lock */ rte_hash_function hash_func; /**< Function used to calculate hash. */ uint32_t hash_func_init_val; /**< Init value used by hash_func. */ rte_hash_cmp_eq_t rte_hash_custom_cmp_eq; @@ -219,13 +213,29 @@ struct rte_hash { /**< Table with buckets storing all the hash values and key indexes * to the key table. */ + rte_rwlock_t *readwrite_lock; /**< Read-write lock thread-safety. */ + struct rte_hash_bucket *buckets_ext; /**< Extra buckets array */ + struct rte_ring *free_ext_bkts; /**< Ring of indexes of free buckets */ + /* Stores index of an empty ext bkt to be recycled on calling + * rte_hash_del_xxx APIs. When lock free read-write concurrency is + * enabled, an empty ext bkt cannot be put into free list immediately + * (as readers might be using it still). Hence freeing of the ext bkt + * is piggy-backed to freeing of the key index. + */ + uint32_t *ext_bkt_to_free; + uint32_t *tbl_chng_cnt; + /**< Indicates if the hash table changed from last read. */ } __rte_cache_aligned; struct queue_node { struct rte_hash_bucket *bkt; /* Current bucket on the bfs search */ + uint32_t cur_bkt_idx; struct queue_node *prev; /* Parent(bucket) in search path */ int prev_slot; /* Parent(slot) in search path */ }; +/** @internal Default RCU defer queue entries to reclaim in one go. */ +#define RTE_HASH_RCU_DQ_RECLAIM_MAX 16 + #endif