From patchwork Thu Nov 1 04:54:52 2018 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Honnappa Nagarahalli X-Patchwork-Id: 47637 X-Patchwork-Delegate: thomas@monjalon.net Return-Path: X-Original-To: patchwork@dpdk.org Delivered-To: patchwork@dpdk.org Received: from [92.243.14.124] (localhost [127.0.0.1]) by dpdk.org (Postfix) with ESMTP id 611694F90; Thu, 1 Nov 2018 05:55:23 +0100 (CET) Received: from foss.arm.com (foss.arm.com [217.140.101.70]) by dpdk.org (Postfix) with ESMTP id 33FDF2C2F for ; Thu, 1 Nov 2018 05:55:20 +0100 (CET) Received: from usa-sjc-imap-foss1.foss.arm.com (unknown [10.72.51.249]) by usa-sjc-mx-foss1.foss.arm.com (Postfix) with ESMTP id 6AF70EBD; Wed, 31 Oct 2018 21:55:19 -0700 (PDT) Received: from qc2400f-1.austin.arm.com (qc2400f-1.austin.arm.com [10.118.12.122]) by usa-sjc-imap-foss1.foss.arm.com (Postfix) with ESMTPSA id EDC343F557; Wed, 31 Oct 2018 21:55:18 -0700 (PDT) From: Honnappa Nagarahalli To: bruce.richardson@intel.com, pablo.de.lara.guarch@intel.com Cc: dev@dpdk.org, gavin.hu@arm.com, dharmik.thakkar@arm.com, nd@arm.com, yipeng1.wang@intel.com, sameh.gobriel@intel.com, Honnappa Nagarahalli Date: Wed, 31 Oct 2018 23:54:52 -0500 Message-Id: <20181101045454.632-2-honnappa.nagarahalli@arm.com> X-Mailer: git-send-email 2.17.1 In-Reply-To: <20181101045454.632-1-honnappa.nagarahalli@arm.com> References: <1539208085-30756-4-git-send-email-yipeng1.wang@intel.com> <20181101045454.632-1-honnappa.nagarahalli@arm.com> Subject: [dpdk-dev] [PATCH 1/3] hash: deprecate lock ellision and read/write concurreny flags X-BeenThere: dev@dpdk.org X-Mailman-Version: 2.1.15 Precedence: list List-Id: DPDK patches and discussions List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: dev-bounces@dpdk.org Sender: "dev" Hash library should provide read/write concurrency by default as most of the use cases require read/write concurrency. Hence the flag RTE_HASH_EXTRA_FLAGS_RW_CONCURRENCY is deprecated. The library will decide if locking is required to provide the concurrency based on other configuration flags. If a lock is used to provide the read/write concurrency, best possible locking mechanism available on the platform should be used. Hence, the flag RTE_HASH_EXTRA_FLAGS_TRANS_MEM_SUPPORT is deprecated. The library will use transactional memory if the platform supports it. Signed-off-by: Honnappa Nagarahalli Reviewed-by: Dharmik Thakkar Reviewed-by: Gavin Hu --- lib/librte_hash/rte_cuckoo_hash.c | 319 ++++++++++++++++++++++++++- lib/librte_hash/rte_hash.h | 22 +- lib/librte_hash/rte_hash_version.map | 7 + 3 files changed, 345 insertions(+), 3 deletions(-) diff --git a/lib/librte_hash/rte_cuckoo_hash.c b/lib/librte_hash/rte_cuckoo_hash.c index 5ddcccd87..a11de22be 100644 --- a/lib/librte_hash/rte_cuckoo_hash.c +++ b/lib/librte_hash/rte_cuckoo_hash.c @@ -121,7 +121,7 @@ get_alt_bucket_index(const struct rte_hash *h, } struct rte_hash * -rte_hash_create(const struct rte_hash_parameters *params) +rte_hash_create_v20(const struct rte_hash_parameters *params) { struct rte_hash *h = NULL; struct rte_tailq_entry *te = NULL; @@ -446,6 +446,323 @@ rte_hash_create(const struct rte_hash_parameters *params) rte_free(tbl_chng_cnt); return NULL; } +VERSION_SYMBOL(rte_hash_create, _v20, 2.0); + +struct rte_hash * +rte_hash_create_v1811(const struct rte_hash_parameters *params) +{ + struct rte_hash *h = NULL; + struct rte_tailq_entry *te = NULL; + struct rte_hash_list *hash_list; + struct rte_ring *r = NULL; + struct rte_ring *r_ext = NULL; + char hash_name[RTE_HASH_NAMESIZE]; + void *k = NULL; + void *buckets = NULL; + void *buckets_ext = NULL; + char ring_name[RTE_RING_NAMESIZE]; + char ext_ring_name[RTE_RING_NAMESIZE]; + unsigned num_key_slots; + unsigned i; + unsigned int use_local_cache = 0; + unsigned int ext_table_support = 0; + unsigned int readwrite_concur_support = 1; + unsigned int writer_takes_lock = 1; + unsigned int no_free_on_del = 0; + uint32_t *tbl_chng_cnt = NULL; + unsigned int readwrite_concur_lf_support = 0; + + rte_hash_function default_hash_func = (rte_hash_function)rte_jhash; + + hash_list = RTE_TAILQ_CAST(rte_hash_tailq.head, rte_hash_list); + + if (params == NULL) { + RTE_LOG(ERR, HASH, "rte_hash_create has no parameters\n"); + return NULL; + } + + /* Check for valid parameters */ + if ((params->entries > RTE_HASH_ENTRIES_MAX) || + (params->entries < RTE_HASH_BUCKET_ENTRIES) || + (params->key_len == 0)) { + rte_errno = EINVAL; + RTE_LOG(ERR, HASH, "rte_hash_create has invalid parameters\n"); + return NULL; + } + + /* Validate correct usage of extra options */ + if ((params->extra_flag & RTE_HASH_EXTRA_FLAGS_RW_CONCURRENCY_LF) && + (params->extra_flag & RTE_HASH_EXTRA_FLAGS_EXT_TABLE)) { + rte_errno = EINVAL; + RTE_LOG(ERR, HASH, "rte_hash_create: extendable bucket " + "feature not supported with rw concurrency " + "lock free\n"); + return NULL; + } + + /* Check extra flags field to check extra options. */ + if (params->extra_flag & RTE_HASH_EXTRA_FLAGS_MULTI_WRITER_ADD) + use_local_cache = 1; + + if (params->extra_flag & RTE_HASH_EXTRA_FLAGS_EXT_TABLE) + ext_table_support = 1; + + if (params->extra_flag & RTE_HASH_EXTRA_FLAGS_NO_FREE_ON_DEL) + no_free_on_del = 1; + + if (params->extra_flag & RTE_HASH_EXTRA_FLAGS_RW_CONCURRENCY_LF) { + /* Do not use lock for RW concurrency */ + readwrite_concur_support = 0; + readwrite_concur_lf_support = 1; + /* Enable not freeing internal memory/index on delete */ + no_free_on_del = 1; + } + + if ((params->extra_flag & RTE_HASH_EXTRA_FLAGS_RW_CONCURRENCY_LF) && + !(params->extra_flag & RTE_HASH_EXTRA_FLAGS_MULTI_WRITER_ADD)) + writer_takes_lock = 0; + + /* Store all keys and leave the first entry as a dummy entry for lookup_bulk */ + if (use_local_cache) + /* + * Increase number of slots by total number of indices + * that can be stored in the lcore caches + * except for the first cache + */ + num_key_slots = params->entries + (RTE_MAX_LCORE - 1) * + (LCORE_CACHE_SIZE - 1) + 1; + else + num_key_slots = params->entries + 1; + + snprintf(ring_name, sizeof(ring_name), "HT_%s", params->name); + /* Create ring (Dummy slot index is not enqueued) */ + r = rte_ring_create(ring_name, rte_align32pow2(num_key_slots), + params->socket_id, 0); + if (r == NULL) { + RTE_LOG(ERR, HASH, "memory allocation failed\n"); + goto err; + } + + const uint32_t num_buckets = rte_align32pow2(params->entries) / + RTE_HASH_BUCKET_ENTRIES; + + /* Create ring for extendable buckets. */ + if (ext_table_support) { + snprintf(ext_ring_name, sizeof(ext_ring_name), "HT_EXT_%s", + params->name); + r_ext = rte_ring_create(ext_ring_name, + rte_align32pow2(num_buckets + 1), + params->socket_id, 0); + + if (r_ext == NULL) { + RTE_LOG(ERR, HASH, "ext buckets memory allocation " + "failed\n"); + goto err; + } + } + + snprintf(hash_name, sizeof(hash_name), "HT_%s", params->name); + + rte_rwlock_write_lock(RTE_EAL_TAILQ_RWLOCK); + + /* guarantee there's no existing: this is normally already checked + * by ring creation above */ + TAILQ_FOREACH(te, hash_list, next) { + h = (struct rte_hash *) te->data; + if (strncmp(params->name, h->name, RTE_HASH_NAMESIZE) == 0) + break; + } + h = NULL; + if (te != NULL) { + rte_errno = EEXIST; + te = NULL; + goto err_unlock; + } + + te = rte_zmalloc("HASH_TAILQ_ENTRY", sizeof(*te), 0); + if (te == NULL) { + RTE_LOG(ERR, HASH, "tailq entry allocation failed\n"); + goto err_unlock; + } + + h = (struct rte_hash *)rte_zmalloc_socket(hash_name, sizeof(struct rte_hash), + RTE_CACHE_LINE_SIZE, params->socket_id); + + if (h == NULL) { + RTE_LOG(ERR, HASH, "memory allocation failed\n"); + goto err_unlock; + } + + buckets = rte_zmalloc_socket(NULL, + num_buckets * sizeof(struct rte_hash_bucket), + RTE_CACHE_LINE_SIZE, params->socket_id); + + if (buckets == NULL) { + RTE_LOG(ERR, HASH, "buckets memory allocation failed\n"); + goto err_unlock; + } + + /* Allocate same number of extendable buckets */ + if (ext_table_support) { + buckets_ext = rte_zmalloc_socket(NULL, + num_buckets * sizeof(struct rte_hash_bucket), + RTE_CACHE_LINE_SIZE, params->socket_id); + if (buckets_ext == NULL) { + RTE_LOG(ERR, HASH, "ext buckets memory allocation " + "failed\n"); + goto err_unlock; + } + /* Populate ext bkt ring. We reserve 0 similar to the + * key-data slot, just in case in future we want to + * use bucket index for the linked list and 0 means NULL + * for next bucket + */ + for (i = 1; i <= num_buckets; i++) + rte_ring_sp_enqueue(r_ext, (void *)((uintptr_t) i)); + } + + const uint32_t key_entry_size = + RTE_ALIGN(sizeof(struct rte_hash_key) + params->key_len, + KEY_ALIGNMENT); + const uint64_t key_tbl_size = (uint64_t) key_entry_size * num_key_slots; + + k = rte_zmalloc_socket(NULL, key_tbl_size, + RTE_CACHE_LINE_SIZE, params->socket_id); + + if (k == NULL) { + RTE_LOG(ERR, HASH, "memory allocation failed\n"); + goto err_unlock; + } + + tbl_chng_cnt = rte_zmalloc_socket(NULL, sizeof(uint32_t), + RTE_CACHE_LINE_SIZE, params->socket_id); + + if (tbl_chng_cnt == NULL) { + RTE_LOG(ERR, HASH, "memory allocation failed\n"); + goto err_unlock; + } + +/* + * If x86 architecture is used, select appropriate compare function, + * which may use x86 intrinsics, otherwise use memcmp + */ +#if defined(RTE_ARCH_X86) || defined(RTE_ARCH_ARM64) + /* Select function to compare keys */ + switch (params->key_len) { + case 16: + h->cmp_jump_table_idx = KEY_16_BYTES; + break; + case 32: + h->cmp_jump_table_idx = KEY_32_BYTES; + break; + case 48: + h->cmp_jump_table_idx = KEY_48_BYTES; + break; + case 64: + h->cmp_jump_table_idx = KEY_64_BYTES; + break; + case 80: + h->cmp_jump_table_idx = KEY_80_BYTES; + break; + case 96: + h->cmp_jump_table_idx = KEY_96_BYTES; + break; + case 112: + h->cmp_jump_table_idx = KEY_112_BYTES; + break; + case 128: + h->cmp_jump_table_idx = KEY_128_BYTES; + break; + default: + /* If key is not multiple of 16, use generic memcmp */ + h->cmp_jump_table_idx = KEY_OTHER_BYTES; + } +#else + h->cmp_jump_table_idx = KEY_OTHER_BYTES; +#endif + + if (use_local_cache) { + h->local_free_slots = rte_zmalloc_socket(NULL, + sizeof(struct lcore_cache) * RTE_MAX_LCORE, + RTE_CACHE_LINE_SIZE, params->socket_id); + } + + /* Default hash function */ +#if defined(RTE_ARCH_X86) + default_hash_func = (rte_hash_function)rte_hash_crc; +#elif defined(RTE_ARCH_ARM64) + if (rte_cpu_get_flag_enabled(RTE_CPUFLAG_CRC32)) + default_hash_func = (rte_hash_function)rte_hash_crc; +#endif + /* Setup hash context */ + snprintf(h->name, sizeof(h->name), "%s", params->name); + h->entries = params->entries; + h->key_len = params->key_len; + h->key_entry_size = key_entry_size; + h->hash_func_init_val = params->hash_func_init_val; + + h->num_buckets = num_buckets; + h->bucket_bitmask = h->num_buckets - 1; + h->buckets = buckets; + h->buckets_ext = buckets_ext; + h->free_ext_bkts = r_ext; + h->hash_func = (params->hash_func == NULL) ? + default_hash_func : params->hash_func; + h->key_store = k; + h->free_slots = r; + h->tbl_chng_cnt = tbl_chng_cnt; + *h->tbl_chng_cnt = 0; + h->hw_trans_mem_support = rte_tm_supported(); + h->use_local_cache = use_local_cache; + h->readwrite_concur_support = readwrite_concur_support; + h->ext_table_support = ext_table_support; + h->writer_takes_lock = writer_takes_lock; + h->no_free_on_del = no_free_on_del; + h->readwrite_concur_lf_support = readwrite_concur_lf_support; + +#if defined(RTE_ARCH_X86) + if (rte_cpu_get_flag_enabled(RTE_CPUFLAG_SSE2)) + h->sig_cmp_fn = RTE_HASH_COMPARE_SSE; + else +#endif + h->sig_cmp_fn = RTE_HASH_COMPARE_SCALAR; + + if (h->writer_takes_lock) { + h->readwrite_lock = rte_malloc(NULL, sizeof(rte_rwlock_t), + RTE_CACHE_LINE_SIZE); + if (h->readwrite_lock == NULL) + goto err_unlock; + + rte_rwlock_init(h->readwrite_lock); + } + + /* Populate free slots ring. Entry zero is reserved for key misses. */ + for (i = 1; i < num_key_slots; i++) + rte_ring_sp_enqueue(r, (void *)((uintptr_t) i)); + + te->data = (void *) h; + TAILQ_INSERT_TAIL(hash_list, te, next); + rte_rwlock_write_unlock(RTE_EAL_TAILQ_RWLOCK); + + return h; +err_unlock: + rte_rwlock_write_unlock(RTE_EAL_TAILQ_RWLOCK); +err: + rte_ring_free(r); + rte_ring_free(r_ext); + rte_free(te); + rte_free(h); + rte_free(buckets); + rte_free(buckets_ext); + rte_free(k); + rte_free(tbl_chng_cnt); + return NULL; +} +BIND_DEFAULT_SYMBOL(rte_hash_create, _v1811, 18.11); +MAP_STATIC_SYMBOL( + struct rte_hash *rte_hash_create( + const struct rte_hash_parameters *params), + rte_hash_create_v1811); void rte_hash_free(struct rte_hash *h) diff --git a/lib/librte_hash/rte_hash.h b/lib/librte_hash/rte_hash.h index c93d1a137..93c7019ec 100644 --- a/lib/librte_hash/rte_hash.h +++ b/lib/librte_hash/rte_hash.h @@ -30,13 +30,27 @@ extern "C" { #define RTE_HASH_LOOKUP_BULK_MAX 64 #define RTE_HASH_LOOKUP_MULTI_MAX RTE_HASH_LOOKUP_BULK_MAX -/** Enable Hardware transactional memory support. */ +/** + * @deprecated + * This define will be removed in the next release. + * If the target platform supports hardware transactional memory + * it will be used without user consent as it provides the best possible + * performance. + * + * Enable Hardware transactional memory support. + */ #define RTE_HASH_EXTRA_FLAGS_TRANS_MEM_SUPPORT 0x01 /** Default behavior of insertion, single writer/multi writer */ #define RTE_HASH_EXTRA_FLAGS_MULTI_WRITER_ADD 0x02 -/** Flag to support reader writer concurrency */ +/** + * @deprecated + * This define will be removed in the next release. + * This library should be thread-safe by default. + * + * Flag to support reader writer concurrency + */ #define RTE_HASH_EXTRA_FLAGS_RW_CONCURRENCY 0x04 /** Flag to indicate the extendabe bucket table feature should be used */ @@ -105,6 +119,10 @@ struct rte_hash; */ struct rte_hash * rte_hash_create(const struct rte_hash_parameters *params); +struct rte_hash * +rte_hash_create_v20(const struct rte_hash_parameters *params); +struct rte_hash * +rte_hash_create_v1811(const struct rte_hash_parameters *params); /** * Set a new hash compare function other than the default one. diff --git a/lib/librte_hash/rte_hash_version.map b/lib/librte_hash/rte_hash_version.map index 734ae28b0..c72469099 100644 --- a/lib/librte_hash/rte_hash_version.map +++ b/lib/librte_hash/rte_hash_version.map @@ -54,6 +54,13 @@ DPDK_18.08 { } DPDK_16.07; +DPDK_18.11 { + global: + + rte_hash_create; + +} DPDK_18.08; + EXPERIMENTAL { global: