Patch Detail
get:
Show a patch.
patch:
Update a patch.
put:
Update a patch.
GET /api/patches/8371/?format=api
{ "id": 8371, "url": "http://patches.dpdk.org/api/patches/8371/?format=api", "web_url": "http://patches.dpdk.org/project/dpdk/patch/1446207772-58543-1-git-send-email-pablo.de.lara.guarch@intel.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": "<1446207772-58543-1-git-send-email-pablo.de.lara.guarch@intel.com>", "list_archive_url": "https://inbox.dpdk.org/dev/1446207772-58543-1-git-send-email-pablo.de.lara.guarch@intel.com", "date": "2015-10-30T12:22:52", "name": "[dpdk-dev,v2] hash: fix scaling by reducing contention", "commit_ref": null, "pull_url": null, "state": "superseded", "archived": true, "hash": "05b187b5b8eae26ba8cd6437a538e2bee3b0c30d", "submitter": { "id": 9, "url": "http://patches.dpdk.org/api/people/9/?format=api", "name": "De Lara Guarch, Pablo", "email": "pablo.de.lara.guarch@intel.com" }, "delegate": null, "mbox": "http://patches.dpdk.org/project/dpdk/patch/1446207772-58543-1-git-send-email-pablo.de.lara.guarch@intel.com/mbox/", "series": [], "comments": "http://patches.dpdk.org/api/patches/8371/comments/", "check": "pending", "checks": "http://patches.dpdk.org/api/patches/8371/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 [IPv6:::1])\n\tby dpdk.org (Postfix) with ESMTP id B619C8E69;\n\tFri, 30 Oct 2015 13:23:00 +0100 (CET)", "from mga02.intel.com (mga02.intel.com [134.134.136.20])\n\tby dpdk.org (Postfix) with ESMTP id 0EC4B8E67\n\tfor <dev@dpdk.org>; Fri, 30 Oct 2015 13:22:58 +0100 (CET)", "from orsmga002.jf.intel.com ([10.7.209.21])\n\tby orsmga101.jf.intel.com with ESMTP; 30 Oct 2015 05:22:56 -0700", "from sie-lab-214-036.ir.intel.com (HELO\n\tsie-lab-214-174.ir.intel.com) ([10.237.214.36])\n\tby orsmga002.jf.intel.com with ESMTP; 30 Oct 2015 05:22:54 -0700" ], "X-ExtLoop1": "1", "X-IronPort-AV": "E=Sophos;i=\"5.20,218,1444719600\"; d=\"scan'208\";a=\"838804818\"", "From": "Pablo de Lara <pablo.de.lara.guarch@intel.com>", "To": "dev@dpdk.org", "Date": "Fri, 30 Oct 2015 12:22:52 +0000", "Message-Id": "<1446207772-58543-1-git-send-email-pablo.de.lara.guarch@intel.com>", "X-Mailer": "git-send-email 2.4.3", "In-Reply-To": "<1443802033-245423-1-git-send-email-pablo.de.lara.guarch@intel.com>", "References": "<1443802033-245423-1-git-send-email-pablo.de.lara.guarch@intel.com>", "Subject": "[dpdk-dev] [PATCH v2] hash: fix scaling by reducing contention", "X-BeenThere": "dev@dpdk.org", "X-Mailman-Version": "2.1.15", "Precedence": "list", "List-Id": "patches and discussions about DPDK <dev.dpdk.org>", "List-Unsubscribe": "<http://dpdk.org/ml/options/dev>,\n\t<mailto:dev-request@dpdk.org?subject=unsubscribe>", "List-Archive": "<http://dpdk.org/ml/archives/dev/>", "List-Post": "<mailto:dev@dpdk.org>", "List-Help": "<mailto:dev-request@dpdk.org?subject=help>", "List-Subscribe": "<http://dpdk.org/ml/listinfo/dev>,\n\t<mailto:dev-request@dpdk.org?subject=subscribe>", "Errors-To": "dev-bounces@dpdk.org", "Sender": "\"dev\" <dev-bounces@dpdk.org>" }, "content": "From: \"De Lara Guarch, Pablo\" <pablo.de.lara.guarch@intel.com>\n\nIf using multiple cores on a system with hardware transactional\nmemory support, thread scaling does not work, as there was a single\npoint in the hash library which is a bottleneck for all threads,\nwhich is the \"free_slots\" ring, which stores all the indices of\nthe free slots in the table.\n\nThis patch fixes the problem, by creating a local cache per logical core,\nwhich stores locally indices of free slots,\nso most times, writer threads will not interfere each other.\n\nFixes: 48a399119619 (\"hash: replace with cuckoo hash implementation\")\n\nSigned-off-by: Pablo de Lara <pablo.de.lara.guarch@intel.com>\n---\n\nChanges in v2:\n - Include patch dependency below\n\nThis patch depends on patch \"hash: free internal ring when freeing hash\"\n(http://www.dpdk.org/dev/patchwork/patch/7377/)\n\n app/test/test_hash_scaling.c | 1 +\n doc/guides/rel_notes/release_2_2.rst | 5 ++\n lib/librte_hash/rte_cuckoo_hash.c | 144 ++++++++++++++++++++++++++++++-----\n lib/librte_hash/rte_hash.h | 3 +\n 4 files changed, 133 insertions(+), 20 deletions(-)", "diff": "diff --git a/app/test/test_hash_scaling.c b/app/test/test_hash_scaling.c\nindex 39602cb..e7cb7e2 100644\n--- a/app/test/test_hash_scaling.c\n+++ b/app/test/test_hash_scaling.c\n@@ -133,6 +133,7 @@ test_hash_scaling(int locking_mode)\n \t\t.hash_func = rte_hash_crc,\n \t\t.hash_func_init_val = 0,\n \t\t.socket_id = rte_socket_id(),\n+\t\t.extra_flag = 1 << RTE_HASH_TRANS_MEM_SUPPORT_FLAG,\n \t};\n \tstruct rte_hash *handle;\n \tchar name[RTE_HASH_NAMESIZE];\ndiff --git a/doc/guides/rel_notes/release_2_2.rst b/doc/guides/rel_notes/release_2_2.rst\nindex 89e4d58..14d2ed9 100644\n--- a/doc/guides/rel_notes/release_2_2.rst\n+++ b/doc/guides/rel_notes/release_2_2.rst\n@@ -79,6 +79,11 @@ Drivers\n \n Fixed issue when releasing null control queue.\n \n+* **hash: Fixed thread scaling by reducing contention.**\n+\n+ Fixed issue in hash library where, using multiple cores with\n+ hardware transactional memory support, thread scaling did not work,\n+ due to the global ring that is shared by all cores.\n \n Libraries\n ~~~~~~~~~\ndiff --git a/lib/librte_hash/rte_cuckoo_hash.c b/lib/librte_hash/rte_cuckoo_hash.c\nindex 409fc2e..43788a4 100644\n--- a/lib/librte_hash/rte_cuckoo_hash.c\n+++ b/lib/librte_hash/rte_cuckoo_hash.c\n@@ -96,8 +96,15 @@ EAL_REGISTER_TAILQ(rte_hash_tailq)\n \n #define KEY_ALIGNMENT\t\t\t16\n \n+#define LCORE_CACHE_SIZE\t\t8\n+\n typedef int (*rte_hash_cmp_eq_t)(const void *key1, const void *key2, size_t key_len);\n \n+struct lcore_cache {\n+\tunsigned len; /**< Cache len */\n+\tvoid *objs[LCORE_CACHE_SIZE]; /**< Cache objects */\n+} __rte_cache_aligned;\n+\n /** A hash table structure. */\n struct rte_hash {\n \tchar name[RTE_HASH_NAMESIZE]; /**< Name of the hash. */\n@@ -117,6 +124,10 @@ struct rte_hash {\n \tstruct rte_hash_bucket *buckets;\t/**< Table with buckets storing all the\n \t\t\t\t\t\t\thash values and key indexes\n \t\t\t\t\t\t\tto the key table*/\n+\tuint8_t hw_trans_mem_support;\t/**< Hardware transactional\n+\t\t\t\t\t\t\tmemory support */\n+\tstruct lcore_cache *local_free_slots;\n+\t/**< Local cache per lcore, storing some indexes of the free slots */\n } __rte_cache_aligned;\n \n /* Structure storing both primary and secondary hashes */\n@@ -183,6 +194,8 @@ rte_hash_create(const struct rte_hash_parameters *params)\n \tvoid *k = NULL;\n \tvoid *buckets = NULL;\n \tchar ring_name[RTE_RING_NAMESIZE];\n+\tunsigned num_key_slots;\n+\tunsigned hw_trans_mem_support = 0;\n \tunsigned i;\n \n \thash_list = RTE_TAILQ_CAST(rte_hash_tailq.head, rte_hash_list);\n@@ -202,6 +215,10 @@ rte_hash_create(const struct rte_hash_parameters *params)\n \t\treturn NULL;\n \t}\n \n+\t/* Check extra flags bit to check extra options. */\n+\tif (params->extra_flag & (1 << RTE_HASH_TRANS_MEM_SUPPORT_FLAG))\n+\t\thw_trans_mem_support = 1;\n+\n \tsnprintf(hash_name, sizeof(hash_name), \"HT_%s\", params->name);\n \n \t/* Guarantee there's no existing */\n@@ -238,7 +255,18 @@ rte_hash_create(const struct rte_hash_parameters *params)\n \tconst uint32_t key_entry_size = sizeof(struct rte_hash_key) + params->key_len;\n \n \t/* Store all keys and leave the first entry as a dummy entry for lookup_bulk */\n-\tconst uint64_t key_tbl_size = (uint64_t) key_entry_size * (params->entries + 1);\n+\tif (hw_trans_mem_support)\n+\t\t/*\n+\t\t * Increase number of slots by total number of indices\n+\t\t * that can be stored in the lcore caches\n+\t\t * except for the first cache\n+\t\t */\n+\t\tnum_key_slots = params->entries + (RTE_MAX_LCORE - 1) *\n+\t\t\t\t\tLCORE_CACHE_SIZE + 1;\n+\telse\n+\t\tnum_key_slots = params->entries + 1;\n+\n+\tconst uint64_t key_tbl_size = (uint64_t) key_entry_size * num_key_slots;\n \n \tk = rte_zmalloc_socket(NULL, key_tbl_size,\n \t\t\tRTE_CACHE_LINE_SIZE, params->socket_id);\n@@ -288,13 +316,19 @@ rte_hash_create(const struct rte_hash_parameters *params)\n #endif\n \n \tsnprintf(ring_name, sizeof(ring_name), \"HT_%s\", params->name);\n-\tr = rte_ring_create(ring_name, rte_align32pow2(params->entries + 1),\n-\t\t\t\tparams->socket_id, 0);\n+\tr = rte_ring_create(ring_name, rte_align32pow2(num_key_slots),\n+\t\t\tparams->socket_id, 0);\n \tif (r == NULL) {\n \t\tRTE_LOG(ERR, HASH, \"memory allocation failed\\n\");\n \t\tgoto err;\n \t}\n \n+\tif (hw_trans_mem_support) {\n+\t\th->local_free_slots = rte_zmalloc_socket(NULL,\n+\t\t\t\tsizeof(struct lcore_cache) * RTE_MAX_LCORE,\n+\t\t\t\tRTE_CACHE_LINE_SIZE, params->socket_id);\n+\t}\n+\n \t/* Setup hash context */\n \tsnprintf(h->name, sizeof(h->name), \"%s\", params->name);\n \th->entries = params->entries;\n@@ -307,9 +341,9 @@ rte_hash_create(const struct rte_hash_parameters *params)\n \th->buckets = buckets;\n \th->hash_func = (params->hash_func == NULL) ?\n \t\tDEFAULT_HASH_FUNC : params->hash_func;\n-\n \th->key_store = k;\n \th->free_slots = r;\n+\th->hw_trans_mem_support = hw_trans_mem_support;\n \n \t/* populate the free slots ring. Entry zero is reserved for key misses */\n \tfor (i = 1; i < params->entries + 1; i++)\n@@ -357,6 +391,9 @@ rte_hash_free(struct rte_hash *h)\n \n \trte_rwlock_write_unlock(RTE_EAL_TAILQ_RWLOCK);\n \n+\tif (h->hw_trans_mem_support)\n+\t\trte_free(h->local_free_slots);\n+\n \trte_ring_free(h->free_slots);\n \trte_free(h->key_store);\n \trte_free(h->buckets);\n@@ -402,6 +439,12 @@ rte_hash_reset(struct rte_hash *h)\n \t/* Repopulate the free slots ring. Entry zero is reserved for key misses */\n \tfor (i = 1; i < h->entries + 1; i++)\n \t\trte_ring_sp_enqueue(h->free_slots, (void *)((uintptr_t) i));\n+\n+\tif (h->hw_trans_mem_support) {\n+\t\t/* Reset local caches per lcore */\n+\t\tfor (i = 0; i < RTE_MAX_LCORE; i++)\n+\t\t\th->local_free_slots[i].len = 0;\n+\t}\n }\n \n /* Search for an entry that can be pushed to its alternative location */\n@@ -468,6 +511,17 @@ make_space_bucket(const struct rte_hash *h, struct rte_hash_bucket *bkt)\n \n }\n \n+static inline void\n+enqueue_slot(const struct rte_hash *h, struct lcore_cache *cached_free_slots,\n+\t\tvoid *slot_id)\n+{\n+\tif (h->hw_trans_mem_support) {\n+\t\tcached_free_slots->objs[cached_free_slots->len] = slot_id;\n+\t\tcached_free_slots->len++;\n+\t} else\n+\t\trte_ring_sp_enqueue(h->free_slots, slot_id);\n+}\n+\n static inline int32_t\n __rte_hash_add_key_with_hash(const struct rte_hash *h, const void *key,\n \t\t\t\t\t\thash_sig_t sig, void *data)\n@@ -477,9 +531,12 @@ __rte_hash_add_key_with_hash(const struct rte_hash *h, const void *key,\n \tunsigned i;\n \tstruct rte_hash_bucket *prim_bkt, *sec_bkt;\n \tstruct rte_hash_key *new_k, *k, *keys = h->key_store;\n-\tvoid *slot_id;\n+\tvoid *slot_id = NULL;\n \tuint32_t new_idx;\n \tint ret;\n+\tunsigned n_slots;\n+\tunsigned lcore_id;\n+\tstruct lcore_cache *cached_free_slots = NULL;\n \n \tprim_bucket_idx = sig & h->bucket_bitmask;\n \tprim_bkt = &h->buckets[prim_bucket_idx];\n@@ -491,8 +548,28 @@ __rte_hash_add_key_with_hash(const struct rte_hash *h, const void *key,\n \trte_prefetch0(sec_bkt);\n \n \t/* Get a new slot for storing the new key */\n-\tif (rte_ring_sc_dequeue(h->free_slots, &slot_id) != 0)\n-\t\treturn -ENOSPC;\n+\tif (h->hw_trans_mem_support) {\n+\t\tlcore_id = rte_lcore_id();\n+\t\tcached_free_slots = &h->local_free_slots[lcore_id];\n+\t\t/* Try to get a free slot from the local cache */\n+\t\tif (cached_free_slots->len == 0) {\n+\t\t\t/* Need to get another burst of free slots from global ring */\n+\t\t\tn_slots = rte_ring_mc_dequeue_burst(h->free_slots,\n+\t\t\t\t\tcached_free_slots->objs, LCORE_CACHE_SIZE);\n+\t\t\tif (n_slots == 0)\n+\t\t\t\treturn -ENOSPC;\n+\n+\t\t\tcached_free_slots->len += n_slots;\n+\t\t}\n+\n+\t\t/* Get a free slot from the local cache */\n+\t\tcached_free_slots->len--;\n+\t\tslot_id = cached_free_slots->objs[cached_free_slots->len];\n+\t} else {\n+\t\tif (rte_ring_sc_dequeue(h->free_slots, &slot_id) != 0)\n+\t\t\treturn -ENOSPC;\n+\t}\n+\n \tnew_k = RTE_PTR_ADD(keys, (uintptr_t)slot_id * h->key_entry_size);\n \trte_prefetch0(new_k);\n \tnew_idx = (uint32_t)((uintptr_t) slot_id);\n@@ -500,11 +577,12 @@ __rte_hash_add_key_with_hash(const struct rte_hash *h, const void *key,\n \t/* Check if key is already inserted in primary location */\n \tfor (i = 0; i < RTE_HASH_BUCKET_ENTRIES; i++) {\n \t\tif (prim_bkt->signatures[i].current == sig &&\n-\t\t\t\tprim_bkt->signatures[i].alt == alt_hash) {\n+\t\t\t\tprim_bkt->signatures[i].alt == alt_hash) {\n \t\t\tk = (struct rte_hash_key *) ((char *)keys +\n \t\t\t\t\tprim_bkt->key_idx[i] * h->key_entry_size);\n \t\t\tif (h->rte_hash_cmp_eq(key, k->key, h->key_len) == 0) {\n-\t\t\t\trte_ring_sp_enqueue(h->free_slots, slot_id);\n+\t\t\t\t/* Enqueue index of free slot back in the ring. */\n+\t\t\t\tenqueue_slot(h, cached_free_slots, slot_id);\n \t\t\t\t/* Update data */\n \t\t\t\tk->pdata = data;\n \t\t\t\t/*\n@@ -519,11 +597,12 @@ __rte_hash_add_key_with_hash(const struct rte_hash *h, const void *key,\n \t/* Check if key is already inserted in secondary location */\n \tfor (i = 0; i < RTE_HASH_BUCKET_ENTRIES; i++) {\n \t\tif (sec_bkt->signatures[i].alt == sig &&\n-\t\t\t\tsec_bkt->signatures[i].current == alt_hash) {\n+\t\t\t\tsec_bkt->signatures[i].current == alt_hash) {\n \t\t\tk = (struct rte_hash_key *) ((char *)keys +\n \t\t\t\t\tsec_bkt->key_idx[i] * h->key_entry_size);\n \t\t\tif (h->rte_hash_cmp_eq(key, k->key, h->key_len) == 0) {\n-\t\t\t\trte_ring_sp_enqueue(h->free_slots, slot_id);\n+\t\t\t\t/* Enqueue index of free slot back in the ring. */\n+\t\t\t\tenqueue_slot(h, cached_free_slots, slot_id);\n \t\t\t\t/* Update data */\n \t\t\t\tk->pdata = data;\n \t\t\t\t/*\n@@ -566,10 +645,9 @@ __rte_hash_add_key_with_hash(const struct rte_hash *h, const void *key,\n \t}\n \n \t/* Error in addition, store new slot back in the ring and return error */\n-\trte_ring_sp_enqueue(h->free_slots,\n-\t\t(void *)((uintptr_t) new_idx));\n-\treturn ret;\n+\tenqueue_slot(h, cached_free_slots, (void *)((uintptr_t) new_idx));\n \n+\treturn ret;\n }\n \n int32_t\n@@ -701,6 +779,34 @@ rte_hash_lookup_data(const struct rte_hash *h, const void *key, void **data)\n \treturn __rte_hash_lookup_with_hash(h, key, rte_hash_hash(h, key), data);\n }\n \n+static inline void\n+remove_entry(const struct rte_hash *h, struct rte_hash_bucket *bkt, unsigned i)\n+{\n+\tunsigned lcore_id, n_slots;\n+\tstruct lcore_cache *cached_free_slots;\n+\n+\tbkt->signatures[i].sig = NULL_SIGNATURE;\n+\tif (h->hw_trans_mem_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);\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)bkt->key_idx[i]);\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)bkt->key_idx[i]));\n+\t}\n+}\n+\n static inline int32_t\n __rte_hash_del_key_with_hash(const struct rte_hash *h, const void *key,\n \t\t\t\t\t\thash_sig_t sig)\n@@ -721,9 +827,8 @@ __rte_hash_del_key_with_hash(const struct rte_hash *h, const void *key,\n \t\t\tk = (struct rte_hash_key *) ((char *)keys +\n \t\t\t\t\tbkt->key_idx[i] * h->key_entry_size);\n \t\t\tif (h->rte_hash_cmp_eq(key, k->key, h->key_len) == 0) {\n-\t\t\t\tbkt->signatures[i].sig = NULL_SIGNATURE;\n-\t\t\t\trte_ring_sp_enqueue(h->free_slots,\n-\t\t\t\t\t\t(void *)((uintptr_t)bkt->key_idx[i]));\n+\t\t\t\tremove_entry(h, bkt, i);\n+\n \t\t\t\t/*\n \t\t\t\t * Return index where key is stored,\n \t\t\t\t * substracting the first dummy index\n@@ -745,9 +850,8 @@ __rte_hash_del_key_with_hash(const struct rte_hash *h, const void *key,\n \t\t\tk = (struct rte_hash_key *) ((char *)keys +\n \t\t\t\t\tbkt->key_idx[i] * h->key_entry_size);\n \t\t\tif (h->rte_hash_cmp_eq(key, k->key, h->key_len) == 0) {\n-\t\t\t\tbkt->signatures[i].sig = NULL_SIGNATURE;\n-\t\t\t\trte_ring_sp_enqueue(h->free_slots,\n-\t\t\t\t\t\t(void *)((uintptr_t)bkt->key_idx[i]));\n+\t\t\t\tremove_entry(h, bkt, i);\n+\n \t\t\t\t/*\n \t\t\t\t * Return index where key is stored,\n \t\t\t\t * substracting the first dummy index\ndiff --git a/lib/librte_hash/rte_hash.h b/lib/librte_hash/rte_hash.h\nindex 175c0bb..24d4c60 100644\n--- a/lib/librte_hash/rte_hash.h\n+++ b/lib/librte_hash/rte_hash.h\n@@ -56,6 +56,9 @@ extern \"C\" {\n #define RTE_HASH_LOOKUP_BULK_MAX\t\t64\n #define RTE_HASH_LOOKUP_MULTI_MAX\t\tRTE_HASH_LOOKUP_BULK_MAX\n \n+/** Enable Hardware transactional memory support. */\n+#define RTE_HASH_TRANS_MEM_SUPPORT_FLAG\t\t0\n+\n /** Signature of key that is stored internally. */\n typedef uint32_t hash_sig_t;\n \n", "prefixes": [ "dpdk-dev", "v2" ] }