Patch Detail
get:
Show a patch.
patch:
Update a patch.
put:
Update a patch.
GET /api/patches/44353/?format=api
{ "id": 44353, "url": "http://patches.dpdk.org/api/patches/44353/?format=api", "web_url": "http://patches.dpdk.org/project/dpdk/patch/1536253938-192391-5-git-send-email-honnappa.nagarahalli@arm.com/", "project": { "id": 1, "url": "http://patches.dpdk.org/api/projects/1/?format=api", "name": "DPDK", "link_name": "dpdk", "list_id": "dev.dpdk.org", "list_email": "dev@dpdk.org", "web_url": "http://core.dpdk.org", "scm_url": "git://dpdk.org/dpdk", "webscm_url": "http://git.dpdk.org/dpdk", "list_archive_url": "https://inbox.dpdk.org/dev", "list_archive_url_format": "https://inbox.dpdk.org/dev/{}", "commit_url_format": "" }, "msgid": "<1536253938-192391-5-git-send-email-honnappa.nagarahalli@arm.com>", "list_archive_url": "https://inbox.dpdk.org/dev/1536253938-192391-5-git-send-email-honnappa.nagarahalli@arm.com", "date": "2018-09-06T17:12:18", "name": "[4/4] hash: enable lock-free reader-writer concurrency", "commit_ref": null, "pull_url": null, "state": "superseded", "archived": true, "hash": "f8d7281545d48e2e479935828dbf74974329166b", "submitter": { "id": 1045, "url": "http://patches.dpdk.org/api/people/1045/?format=api", "name": "Honnappa Nagarahalli", "email": "honnappa.nagarahalli@arm.com" }, "delegate": { "id": 1, "url": "http://patches.dpdk.org/api/users/1/?format=api", "username": "tmonjalo", "first_name": "Thomas", "last_name": "Monjalon", "email": "thomas@monjalon.net" }, "mbox": "http://patches.dpdk.org/project/dpdk/patch/1536253938-192391-5-git-send-email-honnappa.nagarahalli@arm.com/mbox/", "series": [ { "id": 1214, "url": "http://patches.dpdk.org/api/series/1214/?format=api", "web_url": "http://patches.dpdk.org/project/dpdk/list/?series=1214", "date": "2018-09-06T17:12:14", "name": "Address reader-writer concurrency in rte_hash", "version": 1, "mbox": "http://patches.dpdk.org/series/1214/mbox/" } ], "comments": "http://patches.dpdk.org/api/patches/44353/comments/", "check": "success", "checks": "http://patches.dpdk.org/api/patches/44353/checks/", "tags": {}, "related": [], "headers": { "Return-Path": "<dev-bounces@dpdk.org>", "X-Original-To": "patchwork@dpdk.org", "Delivered-To": "patchwork@dpdk.org", "Received": [ "from [92.243.14.124] (localhost [127.0.0.1])\n\tby dpdk.org (Postfix) with ESMTP id BD344532C;\n\tThu, 6 Sep 2018 19:12:37 +0200 (CEST)", "from foss.arm.com (foss.arm.com [217.140.101.70])\n\tby dpdk.org (Postfix) with ESMTP id CB1DE4CBB\n\tfor <dev@dpdk.org>; Thu, 6 Sep 2018 19:12:35 +0200 (CEST)", "from usa-sjc-imap-foss1.foss.arm.com (unknown [10.72.51.249])\n\tby usa-sjc-mx-foss1.foss.arm.com (Postfix) with ESMTP id 490FD7A9;\n\tThu, 6 Sep 2018 10:12:35 -0700 (PDT)", "from 2p2660v4-1.austin.arm.com (2p2660v4-1.austin.arm.com\n\t[10.118.12.164])\n\tby usa-sjc-imap-foss1.foss.arm.com (Postfix) with ESMTPSA id\n\tCE8D63F557; Thu, 6 Sep 2018 10:12:34 -0700 (PDT)" ], "From": "Honnappa Nagarahalli <honnappa.nagarahalli@arm.com>", "To": "bruce.richardson@intel.com,\n\tpablo.de.lara.guarch@intel.com", "Cc": "dev@dpdk.org, honnappa.nagarahalli@dpdk.org, gavin.hu@arm.com,\n\tsteve.capper@arm.com, ola.liljedahl@arm.com, nd@arm.com,\n\tHonnappa Nagarahalli <honnappa.nagarahalli@arm.com>", "Date": "Thu, 6 Sep 2018 12:12:18 -0500", "Message-Id": "<1536253938-192391-5-git-send-email-honnappa.nagarahalli@arm.com>", "X-Mailer": "git-send-email 2.7.4", "In-Reply-To": "<1536253938-192391-1-git-send-email-honnappa.nagarahalli@arm.com>", "References": "<1536253938-192391-1-git-send-email-honnappa.nagarahalli@arm.com>", "Subject": "[dpdk-dev] [PATCH 4/4] hash: enable lock-free reader-writer\n\tconcurrency", "X-BeenThere": "dev@dpdk.org", "X-Mailman-Version": "2.1.15", "Precedence": "list", "List-Id": "DPDK patches and discussions <dev.dpdk.org>", "List-Unsubscribe": "<https://mails.dpdk.org/options/dev>,\n\t<mailto:dev-request@dpdk.org?subject=unsubscribe>", "List-Archive": "<http://mails.dpdk.org/archives/dev/>", "List-Post": "<mailto:dev@dpdk.org>", "List-Help": "<mailto:dev-request@dpdk.org?subject=help>", "List-Subscribe": "<https://mails.dpdk.org/listinfo/dev>,\n\t<mailto:dev-request@dpdk.org?subject=subscribe>", "Errors-To": "dev-bounces@dpdk.org", "Sender": "\"dev\" <dev-bounces@dpdk.org>" }, "content": "Add the flag to enable reader-writer concurrency during\nrun time. The rte_hash_del_xxx APIs do not free the keystore\nelement when this flag is enabled. Hence a new API,\nrte_hash_free_key_with_position, to free the key store element\nis added.\n\nSigned-off-by: Honnappa Nagarahalli <honnappa.nagarahalli@arm.com>\nReviewed-by: Gavin Hu <gavin.hu@arm.com>\nReviewed-by: Ola Liljedahl <ola.liljedahl@arm.com>\nReviewed-by: Steve Capper <steve.capper@arm.com>\n---\n lib/librte_hash/rte_cuckoo_hash.c | 105 ++++++++++++++++++++++++++---------\n lib/librte_hash/rte_cuckoo_hash.h | 2 +\n lib/librte_hash/rte_hash.h | 55 ++++++++++++++++++\n lib/librte_hash/rte_hash_version.map | 7 +++\n 4 files changed, 142 insertions(+), 27 deletions(-)", "diff": "diff --git a/lib/librte_hash/rte_cuckoo_hash.c b/lib/librte_hash/rte_cuckoo_hash.c\nindex 1e4a8d4..bf51a73 100644\n--- a/lib/librte_hash/rte_cuckoo_hash.c\n+++ b/lib/librte_hash/rte_cuckoo_hash.c\n@@ -93,6 +93,7 @@ rte_hash_create(const struct rte_hash_parameters *params)\n \tunsigned i;\n \tunsigned int hw_trans_mem_support = 0, multi_writer_support = 0;\n \tunsigned int readwrite_concur_support = 0;\n+\tunsigned int readwrite_concur_lf_support = 0;\n \n \trte_hash_function default_hash_func = (rte_hash_function)rte_jhash;\n \n@@ -124,6 +125,9 @@ rte_hash_create(const struct rte_hash_parameters *params)\n \t\tmulti_writer_support = 1;\n \t}\n \n+\tif (params->extra_flag & RTE_HASH_EXTRA_FLAGS_RW_CONCURRENCY_LF)\n+\t\treadwrite_concur_lf_support = 1;\n+\n \t/* Store all keys and leave the first entry as a dummy entry for lookup_bulk */\n \tif (multi_writer_support)\n \t\t/*\n@@ -272,6 +276,7 @@ rte_hash_create(const struct rte_hash_parameters *params)\n \th->hw_trans_mem_support = hw_trans_mem_support;\n \th->multi_writer_support = multi_writer_support;\n \th->readwrite_concur_support = readwrite_concur_support;\n+\th->readwrite_concur_lf_support = readwrite_concur_lf_support;\n \n #if defined(RTE_ARCH_X86)\n \tif (rte_cpu_get_flag_enabled(RTE_CPUFLAG_AVX2))\n@@ -647,19 +652,21 @@ rte_hash_cuckoo_move_insert_mw(struct rte_hash *h,\n \t\t\treturn -1;\n \t\t}\n \n-\t\t/* Inform the previous move. The current move need\n-\t\t * not be informed now as the current bucket entry\n-\t\t * is present in both primary and secondary.\n-\t\t * Since there is one writer, load acquires on\n-\t\t * tbl_chng_cnt are not required.\n-\t\t */\n-\t\t__atomic_store_n(&h->tbl_chng_cnt,\n-\t\t\t\t h->tbl_chng_cnt + 1,\n-\t\t\t\t __ATOMIC_RELEASE);\n-\t\t/* The stores to sig_alt and sig_current should not\n-\t\t * move above the store to tbl_chng_cnt.\n-\t\t */\n-\t\t__atomic_thread_fence(__ATOMIC_RELEASE);\n+\t\tif (h->readwrite_concur_lf_support) {\n+\t\t\t/* Inform the previous move. The current move need\n+\t\t\t * not be informed now as the current bucket entry\n+\t\t\t * is present in both primary and secondary.\n+\t\t\t * Since there is one writer, load acquires on\n+\t\t\t * tbl_chng_cnt are not required.\n+\t\t\t */\n+\t\t\t__atomic_store_n(&h->tbl_chng_cnt,\n+\t\t\t\t\t h->tbl_chng_cnt + 1,\n+\t\t\t\t\t __ATOMIC_RELEASE);\n+\t\t\t/* The stores to sig_alt and sig_current should not\n+\t\t\t * move above the store to tbl_chng_cnt.\n+\t\t\t */\n+\t\t\t__atomic_thread_fence(__ATOMIC_RELEASE);\n+\t\t}\n \n \t\t/* Need to swap current/alt sig to allow later\n \t\t * Cuckoo insert to move elements back to its\n@@ -679,19 +686,21 @@ rte_hash_cuckoo_move_insert_mw(struct rte_hash *h,\n \t\tcurr_bkt = curr_node->bkt;\n \t}\n \n-\t/* Inform the previous move. The current move need\n-\t * not be informed now as the current bucket entry\n-\t * is present in both primary and secondary.\n-\t * Since there is one writer, load acquires on\n-\t * tbl_chng_cnt are not required.\n-\t */\n-\t__atomic_store_n(&h->tbl_chng_cnt,\n-\t\t\t h->tbl_chng_cnt + 1,\n-\t\t\t __ATOMIC_RELEASE);\n-\t/* The stores to sig_alt and sig_current should not\n-\t * move above the store to tbl_chng_cnt.\n-\t */\n-\t__atomic_thread_fence(__ATOMIC_RELEASE);\n+\tif (h->readwrite_concur_lf_support) {\n+\t\t/* Inform the previous move. The current move need\n+\t\t * not be informed now as the current bucket entry\n+\t\t * is present in both primary and secondary.\n+\t\t * Since there is one writer, load acquires on\n+\t\t * tbl_chng_cnt are not required.\n+\t\t */\n+\t\t__atomic_store_n(&h->tbl_chng_cnt,\n+\t\t\t\t h->tbl_chng_cnt + 1,\n+\t\t\t\t __ATOMIC_RELEASE);\n+\t\t/* The stores to sig_alt and sig_current should not\n+\t\t * move above the store to tbl_chng_cnt.\n+\t\t */\n+\t\t__atomic_thread_fence(__ATOMIC_RELEASE);\n+\t}\n \n \tcurr_bkt->sig_current[curr_slot] = sig;\n \tcurr_bkt->sig_alt[curr_slot] = alt_hash;\n@@ -1090,7 +1099,12 @@ search_and_remove(const struct rte_hash *h, const void *key,\n \t\t\tk = (struct rte_hash_key *) ((char *)keys +\n \t\t\t\t\tkey_idx * h->key_entry_size);\n \t\t\tif (rte_hash_cmp_eq(key, k->key, h) == 0) {\n-\t\t\t\tremove_entry(h, bkt, i);\n+\t\t\t\t/* Do not free the key store element if\n+\t\t\t\t * lock-free concurrency is enabled as\n+\t\t\t\t * readers might still be using it.\n+\t\t\t\t */\n+\t\t\t\tif (!h->readwrite_concur_lf_support)\n+\t\t\t\t\tremove_entry(h, bkt, i);\n \n \t\t\t\t__atomic_store_n(&bkt->key_idx[i],\n \t\t\t\t\t\t EMPTY_SLOT,\n@@ -1177,6 +1191,43 @@ rte_hash_get_key_with_position(const struct rte_hash *h, const int32_t position,\n \treturn 0;\n }\n \n+int __rte_experimental\n+rte_hash_free_key_with_position(const struct rte_hash *h,\n+\t\t\t\tconst int32_t position)\n+{\n+\tRETURN_IF_TRUE(((h == NULL) || (position == EMPTY_SLOT)), -EINVAL);\n+\n+\tunsigned int lcore_id, n_slots;\n+\tstruct lcore_cache *cached_free_slots;\n+\tconst int32_t total_entries = h->num_buckets * RTE_HASH_BUCKET_ENTRIES;\n+\n+\t/* Out of bounds */\n+\tif (position >= total_entries)\n+\t\treturn -EINVAL;\n+\n+\tif (h->multi_writer_support) {\n+\t\tlcore_id = rte_lcore_id();\n+\t\tcached_free_slots = &h->local_free_slots[lcore_id];\n+\t\t/* Cache full, need to free it. */\n+\t\tif (cached_free_slots->len == LCORE_CACHE_SIZE) {\n+\t\t\t/* Need to enqueue the free slots in global ring. */\n+\t\t\tn_slots = rte_ring_mp_enqueue_burst(h->free_slots,\n+\t\t\t\t\t\tcached_free_slots->objs,\n+\t\t\t\t\t\tLCORE_CACHE_SIZE, NULL);\n+\t\t\tcached_free_slots->len -= n_slots;\n+\t\t}\n+\t\t/* Put index of new free slot in cache. */\n+\t\tcached_free_slots->objs[cached_free_slots->len] =\n+\t\t\t\t(void *)((uintptr_t)position);\n+\t\tcached_free_slots->len++;\n+\t} else {\n+\t\trte_ring_sp_enqueue(h->free_slots,\n+\t\t\t\t(void *)((uintptr_t)position));\n+\t}\n+\n+\treturn 0;\n+}\n+\n static inline void\n compare_signatures(uint32_t *prim_hash_matches, uint32_t *sec_hash_matches,\n \t\t\tconst struct rte_hash_bucket *prim_bkt,\ndiff --git a/lib/librte_hash/rte_cuckoo_hash.h b/lib/librte_hash/rte_cuckoo_hash.h\nindex 5ce864c..08d67b8 100644\n--- a/lib/librte_hash/rte_cuckoo_hash.h\n+++ b/lib/librte_hash/rte_cuckoo_hash.h\n@@ -168,6 +168,8 @@ struct rte_hash {\n \t/**< If multi-writer support is enabled. */\n \tuint8_t readwrite_concur_support;\n \t/**< If read-write concurrency support is enabled */\n+\tuint8_t readwrite_concur_lf_support;\n+\t/**< If read-write concurrency lock free support is enabled */\n \trte_hash_function hash_func; /**< Function used to calculate hash. */\n \tuint32_t hash_func_init_val; /**< Init value used by hash_func. */\n \trte_hash_cmp_eq_t rte_hash_custom_cmp_eq;\ndiff --git a/lib/librte_hash/rte_hash.h b/lib/librte_hash/rte_hash.h\nindex 05e024b..7d7372e 100644\n--- a/lib/librte_hash/rte_hash.h\n+++ b/lib/librte_hash/rte_hash.h\n@@ -14,6 +14,8 @@\n #include <stdint.h>\n #include <stddef.h>\n \n+#include <rte_compat.h>\n+\n #ifdef __cplusplus\n extern \"C\" {\n #endif\n@@ -37,6 +39,9 @@ extern \"C\" {\n /** Flag to support reader writer concurrency */\n #define RTE_HASH_EXTRA_FLAGS_RW_CONCURRENCY 0x04\n \n+/** Flag to support lock free reader writer concurrency */\n+#define RTE_HASH_EXTRA_FLAGS_RW_CONCURRENCY_LF 0x08\n+\n /** Signature of key that is stored internally. */\n typedef uint32_t hash_sig_t;\n \n@@ -143,6 +148,11 @@ rte_hash_count(const struct rte_hash *h);\n * and should only be called from one thread by default.\n * Thread safety can be enabled by setting flag during\n * table creation.\n+ * When lock free reader writer concurrency is enabled,\n+ * if this API is called to update an existing entry,\n+ * the application should free any memory allocated for\n+ * previous 'data' only after all the readers have stopped\n+ * using previous 'data'.\n *\n * @param h\n * Hash table to add the key to.\n@@ -165,6 +175,11 @@ rte_hash_add_key_data(struct rte_hash *h, const void *key, void *data);\n * and should only be called from one thread by default.\n * Thread safety can be enabled by setting flag during\n * table creation.\n+ * When lock free reader writer concurrency is enabled,\n+ * if this API is called to update an existing entry,\n+ * the application should free any memory allocated for\n+ * previous 'data' only after all the readers have stopped\n+ * using previous 'data'.\n *\n * @param h\n * Hash table to add the key to.\n@@ -230,6 +245,12 @@ rte_hash_add_key_with_hash(struct rte_hash *h, const void *key, hash_sig_t sig);\n * and should only be called from one thread by default.\n * Thread safety can be enabled by setting flag during\n * table creation.\n+ * If lock free reader writer concurrency is enabled,\n+ * the hash library's internal memory for the deleted\n+ * key is not freed. It should be freed by calling\n+ * rte_hash_free_key_with_position API after all\n+ * the readers have stopped using the hash entry\n+ * corresponding to this key.\n *\n * @param h\n * Hash table to remove the key from.\n@@ -241,6 +262,8 @@ rte_hash_add_key_with_hash(struct rte_hash *h, const void *key, hash_sig_t sig);\n * - A positive value that can be used by the caller as an offset into an\n * array of user data. This value is unique for this key, and is the same\n * value that was returned when the key was added.\n+ * When lock free concurrency is enabled, this value should be used\n+ * while calling the rte_hash_free_key_with_position API.\n */\n int32_t\n rte_hash_del_key(const struct rte_hash *h, const void *key);\n@@ -251,6 +274,12 @@ rte_hash_del_key(const struct rte_hash *h, const void *key);\n * and should only be called from one thread by default.\n * Thread safety can be enabled by setting flag during\n * table creation.\n+ * If lock free reader writer concurrency is enabled,\n+ * the hash library's internal memory for the deleted\n+ * key is not freed. It should be freed by calling\n+ * rte_hash_free_key_with_position API after all\n+ * the readers have stopped using the hash entry\n+ * corresponding to this key.\n *\n * @param h\n * Hash table to remove the key from.\n@@ -264,6 +293,8 @@ rte_hash_del_key(const struct rte_hash *h, const void *key);\n * - A positive value that can be used by the caller as an offset into an\n * array of user data. This value is unique for this key, and is the same\n * value that was returned when the key was added.\n+ * When lock free concurrency is enabled, this value should be used\n+ * while calling the rte_hash_free_key_with_position API.\n */\n int32_t\n rte_hash_del_key_with_hash(const struct rte_hash *h, const void *key, hash_sig_t sig);\n@@ -290,6 +321,30 @@ rte_hash_get_key_with_position(const struct rte_hash *h, const int32_t position,\n \t\t\t void **key);\n \n /**\n+ * @warning\n+ * @b EXPERIMENTAL: this API may change without prior notice\n+ *\n+ * Free hash library's internal memory given the position\n+ * of the key. This operation is not multi-thread safe and should\n+ * only be called from one thread by default. Thread safety\n+ * can be enabled by setting flag during table creation.\n+ * If lock free reader writer concurrency is enabled,\n+ * the hash library's internal memory must be freed using this API\n+ * after the key is deleted using rte_hash_del_key_xxx API.\n+ *\n+ * @param h\n+ * Hash table to get the key from.\n+ * @param position\n+ * Position returned when the key was deleted.\n+ * @return\n+ * - 0 if freed successfully\n+ * - -EINVAL if the parameters are invalid.\n+ */\n+int __rte_experimental\n+rte_hash_free_key_with_position(const struct rte_hash *h,\n+\t\t\t\tconst int32_t position);\n+\n+/**\n * Find a key-value pair in the hash table.\n * This operation is multi-thread safe with regarding to other lookup threads.\n * Read-write concurrency can be enabled by setting flag during\ndiff --git a/lib/librte_hash/rte_hash_version.map b/lib/librte_hash/rte_hash_version.map\nindex e216ac8..734ae28 100644\n--- a/lib/librte_hash/rte_hash_version.map\n+++ b/lib/librte_hash/rte_hash_version.map\n@@ -53,3 +53,10 @@ DPDK_18.08 {\n \trte_hash_count;\n \n } DPDK_16.07;\n+\n+EXPERIMENTAL {\n+\tglobal:\n+\n+\trte_hash_free_key_with_position;\n+\n+};\n", "prefixes": [ "4/4" ] }