Patch Detail
get:
Show a patch.
patch:
Update a patch.
put:
Update a patch.
GET /api/patches/45624/?format=api
{ "id": 45624, "url": "http://patches.dpdk.org/api/patches/45624/?format=api", "web_url": "http://patches.dpdk.org/project/dpdk/patch/1538155426-145177-3-git-send-email-yipeng1.wang@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": "<1538155426-145177-3-git-send-email-yipeng1.wang@intel.com>", "list_archive_url": "https://inbox.dpdk.org/dev/1538155426-145177-3-git-send-email-yipeng1.wang@intel.com", "date": "2018-09-28T17:23:44", "name": "[v4,2/4] hash: add extendable bucket feature", "commit_ref": null, "pull_url": null, "state": "superseded", "archived": true, "hash": "49329e5e5adf8d1f7b2b7a6e5aa466b2b7dfda71", "submitter": { "id": 754, "url": "http://patches.dpdk.org/api/people/754/?format=api", "name": "Wang, Yipeng1", "email": "yipeng1.wang@intel.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/1538155426-145177-3-git-send-email-yipeng1.wang@intel.com/mbox/", "series": [ { "id": 1589, "url": "http://patches.dpdk.org/api/series/1589/?format=api", "web_url": "http://patches.dpdk.org/project/dpdk/list/?series=1589", "date": "2018-09-28T17:23:42", "name": "hash: add extendable bucket and partial key hashing", "version": 4, "mbox": "http://patches.dpdk.org/series/1589/mbox/" } ], "comments": "http://patches.dpdk.org/api/patches/45624/comments/", "check": "warning", "checks": "http://patches.dpdk.org/api/patches/45624/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 0FB4A1B19C;\n\tSat, 29 Sep 2018 02:29:07 +0200 (CEST)", "from mga07.intel.com (mga07.intel.com [134.134.136.100])\n\tby dpdk.org (Postfix) with ESMTP id 9E2D41B10C\n\tfor <dev@dpdk.org>; Sat, 29 Sep 2018 02:28:51 +0200 (CEST)", "from orsmga008.jf.intel.com ([10.7.209.65])\n\tby orsmga105.jf.intel.com with ESMTP/TLS/DHE-RSA-AES256-GCM-SHA384;\n\t28 Sep 2018 17:28:48 -0700", "from skx-yipeng.jf.intel.com ([10.54.81.175])\n\tby orsmga008.jf.intel.com with ESMTP; 28 Sep 2018 17:28:46 -0700" ], "X-Amp-Result": "SKIPPED(no attachment in message)", "X-Amp-File-Uploaded": "False", "X-ExtLoop1": "1", "X-IronPort-AV": "E=Sophos;i=\"5.54,317,1534834800\"; d=\"scan'208\";a=\"77286778\"", "From": "Yipeng Wang <yipeng1.wang@intel.com>", "To": "bruce.richardson@intel.com", "Cc": "konstantin.ananyev@intel.com, dev@dpdk.org, yipeng1.wang@intel.com,\n\thonnappa.nagarahalli@arm.com, sameh.gobriel@intel.com", "Date": "Fri, 28 Sep 2018 10:23:44 -0700", "Message-Id": "<1538155426-145177-3-git-send-email-yipeng1.wang@intel.com>", "X-Mailer": "git-send-email 2.7.4", "In-Reply-To": "<1538155426-145177-1-git-send-email-yipeng1.wang@intel.com>", "References": "<1537993618-92630-1-git-send-email-yipeng1.wang@intel.com>\n\t<1538155426-145177-1-git-send-email-yipeng1.wang@intel.com>", "Subject": "[dpdk-dev] [PATCH v4 2/4] hash: add extendable bucket feature", "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": "In use cases that hash table capacity needs to be guaranteed,\nthe extendable bucket feature can be used to contain extra\nkeys in linked lists when conflict happens. This is similar\nconcept to the extendable bucket hash table in packet\nframework.\n\nThis commit adds the extendable bucket feature. User can turn\nit on or off through the extra flag field during table\ncreation time.\n\nExtendable bucket table composes of buckets that can be\nlinked list to current main table. When extendable bucket\nis enabled, the hash table load can always acheive 100%.\nIn other words, the table can always accomodate the same\nnumber of keys as the specified table size. This provides\n100% table capacity guarantee.\nAlthough keys ending up in the ext buckets may have longer\nlook up time, they should be rare due to the cuckoo\nalgorithm.\n\nSigned-off-by: Yipeng Wang <yipeng1.wang@intel.com>\n---\n lib/librte_hash/rte_cuckoo_hash.c | 376 ++++++++++++++++++++++++++++++++------\n lib/librte_hash/rte_cuckoo_hash.h | 5 +\n lib/librte_hash/rte_hash.h | 3 +\n 3 files changed, 331 insertions(+), 53 deletions(-)", "diff": "diff --git a/lib/librte_hash/rte_cuckoo_hash.c b/lib/librte_hash/rte_cuckoo_hash.c\nindex eba13e9..02650b9 100644\n--- a/lib/librte_hash/rte_cuckoo_hash.c\n+++ b/lib/librte_hash/rte_cuckoo_hash.c\n@@ -31,6 +31,10 @@\n #include \"rte_hash.h\"\n #include \"rte_cuckoo_hash.h\"\n \n+#define FOR_EACH_BUCKET(CURRENT_BKT, START_BUCKET) \\\n+\tfor (CURRENT_BKT = START_BUCKET; \\\n+\t\tCURRENT_BKT != NULL; \\\n+\t\tCURRENT_BKT = CURRENT_BKT->next)\n \n TAILQ_HEAD(rte_hash_list, rte_tailq_entry);\n \n@@ -63,6 +67,14 @@ rte_hash_find_existing(const char *name)\n \treturn h;\n }\n \n+static inline struct rte_hash_bucket *\n+rte_hash_get_last_bkt(struct rte_hash_bucket *lst_bkt)\n+{\n+\twhile (lst_bkt->next != NULL)\n+\t\tlst_bkt = lst_bkt->next;\n+\treturn lst_bkt;\n+}\n+\n void rte_hash_set_cmp_func(struct rte_hash *h, rte_hash_cmp_eq_t func)\n {\n \th->cmp_jump_table_idx = KEY_CUSTOM;\n@@ -85,13 +97,17 @@ rte_hash_create(const struct rte_hash_parameters *params)\n \tstruct rte_tailq_entry *te = NULL;\n \tstruct rte_hash_list *hash_list;\n \tstruct rte_ring *r = NULL;\n+\tstruct rte_ring *r_ext = NULL;\n \tchar hash_name[RTE_HASH_NAMESIZE];\n \tvoid *k = NULL;\n \tvoid *buckets = NULL;\n+\tvoid *buckets_ext = NULL;\n \tchar ring_name[RTE_RING_NAMESIZE];\n+\tchar ext_ring_name[RTE_RING_NAMESIZE];\n \tunsigned num_key_slots;\n \tunsigned i;\n \tunsigned int hw_trans_mem_support = 0, multi_writer_support = 0;\n+\tunsigned int ext_table_support = 0;\n \tunsigned int readwrite_concur_support = 0;\n \n \trte_hash_function default_hash_func = (rte_hash_function)rte_jhash;\n@@ -124,6 +140,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_EXT_TABLE)\n+\t\text_table_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@@ -145,6 +164,24 @@ rte_hash_create(const struct rte_hash_parameters *params)\n \t\tgoto err;\n \t}\n \n+\tconst uint32_t num_buckets = rte_align32pow2(params->entries) /\n+\t\t\t\t\t\tRTE_HASH_BUCKET_ENTRIES;\n+\n+\t/* Create ring for extendable buckets. */\n+\tif (ext_table_support) {\n+\t\tsnprintf(ext_ring_name, sizeof(ext_ring_name), \"HT_EXT_%s\",\n+\t\t\t\t\t\t\t\tparams->name);\n+\t\tr_ext = rte_ring_create(ext_ring_name,\n+\t\t\t\trte_align32pow2(num_buckets + 1),\n+\t\t\t\tparams->socket_id, 0);\n+\n+\t\tif (r_ext == NULL) {\n+\t\t\tRTE_LOG(ERR, HASH, \"ext buckets memory allocation \"\n+\t\t\t\t\t\t\t\t\"failed\\n\");\n+\t\t\tgoto err;\n+\t\t}\n+\t}\n+\n \tsnprintf(hash_name, sizeof(hash_name), \"HT_%s\", params->name);\n \n \trte_rwlock_write_lock(RTE_EAL_TAILQ_RWLOCK);\n@@ -177,18 +214,34 @@ rte_hash_create(const struct rte_hash_parameters *params)\n \t\tgoto err_unlock;\n \t}\n \n-\tconst uint32_t num_buckets = rte_align32pow2(params->entries)\n-\t\t\t\t\t/ RTE_HASH_BUCKET_ENTRIES;\n-\n \tbuckets = rte_zmalloc_socket(NULL,\n \t\t\t\tnum_buckets * sizeof(struct rte_hash_bucket),\n \t\t\t\tRTE_CACHE_LINE_SIZE, params->socket_id);\n \n \tif (buckets == NULL) {\n-\t\tRTE_LOG(ERR, HASH, \"memory allocation failed\\n\");\n+\t\tRTE_LOG(ERR, HASH, \"buckets memory allocation failed\\n\");\n \t\tgoto err_unlock;\n \t}\n \n+\t/* Allocate same number of extendable buckets */\n+\tif (ext_table_support) {\n+\t\tbuckets_ext = rte_zmalloc_socket(NULL,\n+\t\t\t\tnum_buckets * sizeof(struct rte_hash_bucket),\n+\t\t\t\tRTE_CACHE_LINE_SIZE, params->socket_id);\n+\t\tif (buckets_ext == NULL) {\n+\t\t\tRTE_LOG(ERR, HASH, \"ext buckets memory allocation \"\n+\t\t\t\t\t\t\t\"failed\\n\");\n+\t\t\tgoto err_unlock;\n+\t\t}\n+\t\t/* Populate ext bkt ring. We reserve 0 similar to the\n+\t\t * key-data slot, just in case in future we want to\n+\t\t * use bucket index for the linked list and 0 means NULL\n+\t\t * for next bucket\n+\t\t */\n+\t\tfor (i = 1; i <= num_buckets; i++)\n+\t\t\trte_ring_sp_enqueue(r_ext, (void *)((uintptr_t) i));\n+\t}\n+\n \tconst uint32_t key_entry_size = sizeof(struct rte_hash_key) + params->key_len;\n \tconst uint64_t key_tbl_size = (uint64_t) key_entry_size * num_key_slots;\n \n@@ -262,6 +315,8 @@ rte_hash_create(const struct rte_hash_parameters *params)\n \th->num_buckets = num_buckets;\n \th->bucket_bitmask = h->num_buckets - 1;\n \th->buckets = buckets;\n+\th->buckets_ext = buckets_ext;\n+\th->free_ext_bkts = r_ext;\n \th->hash_func = (params->hash_func == NULL) ?\n \t\tdefault_hash_func : params->hash_func;\n \th->key_store = k;\n@@ -269,6 +324,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->ext_table_support = ext_table_support;\n \n #if defined(RTE_ARCH_X86)\n \tif (rte_cpu_get_flag_enabled(RTE_CPUFLAG_AVX2))\n@@ -304,9 +360,11 @@ rte_hash_create(const struct rte_hash_parameters *params)\n \trte_rwlock_write_unlock(RTE_EAL_TAILQ_RWLOCK);\n err:\n \trte_ring_free(r);\n+\trte_ring_free(r_ext);\n \trte_free(te);\n \trte_free(h);\n \trte_free(buckets);\n+\trte_free(buckets_ext);\n \trte_free(k);\n \treturn NULL;\n }\n@@ -344,8 +402,10 @@ rte_hash_free(struct rte_hash *h)\n \t\trte_free(h->readwrite_lock);\n \t}\n \trte_ring_free(h->free_slots);\n+\trte_ring_free(h->free_ext_bkts);\n \trte_free(h->key_store);\n \trte_free(h->buckets);\n+\trte_free(h->buckets_ext);\n \trte_free(h);\n \trte_free(te);\n }\n@@ -403,7 +463,6 @@ __hash_rw_writer_lock(const struct rte_hash *h)\n \t\trte_rwlock_write_lock(h->readwrite_lock);\n }\n \n-\n static inline void\n __hash_rw_reader_lock(const struct rte_hash *h)\n {\n@@ -448,6 +507,14 @@ rte_hash_reset(struct rte_hash *h)\n \twhile (rte_ring_dequeue(h->free_slots, &ptr) == 0)\n \t\trte_pause();\n \n+\t/* clear free extendable bucket ring and memory */\n+\tif (h->ext_table_support) {\n+\t\tmemset(h->buckets_ext, 0, h->num_buckets *\n+\t\t\t\t\t\tsizeof(struct rte_hash_bucket));\n+\t\twhile (rte_ring_dequeue(h->free_ext_bkts, &ptr) == 0)\n+\t\t\trte_pause();\n+\t}\n+\n \t/* Repopulate the free slots ring. Entry zero is reserved for key misses */\n \tif (h->multi_writer_support)\n \t\ttot_ring_cnt = h->entries + (RTE_MAX_LCORE - 1) *\n@@ -458,6 +525,13 @@ rte_hash_reset(struct rte_hash *h)\n \tfor (i = 1; i < tot_ring_cnt + 1; i++)\n \t\trte_ring_sp_enqueue(h->free_slots, (void *)((uintptr_t) i));\n \n+\t/* Repopulate the free ext bkt ring. */\n+\tif (h->ext_table_support) {\n+\t\tfor (i = 1; i < h->num_buckets + 1; i++)\n+\t\t\trte_ring_sp_enqueue(h->free_ext_bkts,\n+\t\t\t\t\t\t(void *)((uintptr_t) i));\n+\t}\n+\n \tif (h->multi_writer_support) {\n \t\t/* Reset local caches per lcore */\n \t\tfor (i = 0; i < RTE_MAX_LCORE; i++)\n@@ -524,24 +598,27 @@ rte_hash_cuckoo_insert_mw(const struct rte_hash *h,\n \t\tint32_t *ret_val)\n {\n \tunsigned int i;\n-\tstruct rte_hash_bucket *cur_bkt = prim_bkt;\n+\tstruct rte_hash_bucket *cur_bkt;\n \tint32_t ret;\n \n \t__hash_rw_writer_lock(h);\n \t/* Check if key was inserted after last check but before this\n \t * protected region in case of inserting duplicated keys.\n \t */\n-\tret = search_and_update(h, data, key, cur_bkt, sig, alt_hash);\n+\tret = search_and_update(h, data, key, prim_bkt, sig, alt_hash);\n \tif (ret != -1) {\n \t\t__hash_rw_writer_unlock(h);\n \t\t*ret_val = ret;\n \t\treturn 1;\n \t}\n-\tret = search_and_update(h, data, key, sec_bkt, alt_hash, sig);\n-\tif (ret != -1) {\n-\t\t__hash_rw_writer_unlock(h);\n-\t\t*ret_val = ret;\n-\t\treturn 1;\n+\n+\tFOR_EACH_BUCKET(cur_bkt, sec_bkt) {\n+\t\tret = search_and_update(h, data, key, cur_bkt, alt_hash, sig);\n+\t\tif (ret != -1) {\n+\t\t\t__hash_rw_writer_unlock(h);\n+\t\t\t*ret_val = ret;\n+\t\t\treturn 1;\n+\t\t}\n \t}\n \n \t/* Insert new entry if there is room in the primary\n@@ -580,7 +657,7 @@ rte_hash_cuckoo_move_insert_mw(const struct rte_hash *h,\n \t\t\tint32_t *ret_val)\n {\n \tuint32_t prev_alt_bkt_idx;\n-\tstruct rte_hash_bucket *cur_bkt = bkt;\n+\tstruct rte_hash_bucket *cur_bkt;\n \tstruct queue_node *prev_node, *curr_node = leaf;\n \tstruct rte_hash_bucket *prev_bkt, *curr_bkt = leaf->bkt;\n \tuint32_t prev_slot, curr_slot = leaf_slot;\n@@ -597,18 +674,20 @@ rte_hash_cuckoo_move_insert_mw(const struct rte_hash *h,\n \t/* Check if key was inserted after last check but before this\n \t * protected region.\n \t */\n-\tret = search_and_update(h, data, key, cur_bkt, sig, alt_hash);\n+\tret = search_and_update(h, data, key, bkt, sig, alt_hash);\n \tif (ret != -1) {\n \t\t__hash_rw_writer_unlock(h);\n \t\t*ret_val = ret;\n \t\treturn 1;\n \t}\n \n-\tret = search_and_update(h, data, key, alt_bkt, alt_hash, sig);\n-\tif (ret != -1) {\n-\t\t__hash_rw_writer_unlock(h);\n-\t\t*ret_val = ret;\n-\t\treturn 1;\n+\tFOR_EACH_BUCKET(cur_bkt, alt_bkt) {\n+\t\tret = search_and_update(h, data, key, cur_bkt, alt_hash, sig);\n+\t\tif (ret != -1) {\n+\t\t\t__hash_rw_writer_unlock(h);\n+\t\t\t*ret_val = ret;\n+\t\t\treturn 1;\n+\t\t}\n \t}\n \n \twhile (likely(curr_node->prev != NULL)) {\n@@ -711,15 +790,18 @@ __rte_hash_add_key_with_hash(const struct rte_hash *h, const void *key,\n {\n \thash_sig_t alt_hash;\n \tuint32_t prim_bucket_idx, sec_bucket_idx;\n-\tstruct rte_hash_bucket *prim_bkt, *sec_bkt;\n+\tstruct rte_hash_bucket *prim_bkt, *sec_bkt, *cur_bkt;\n \tstruct rte_hash_key *new_k, *keys = h->key_store;\n \tvoid *slot_id = NULL;\n-\tuint32_t new_idx;\n+\tvoid *ext_bkt_id = NULL;\n+\tuint32_t new_idx, bkt_id;\n \tint ret;\n \tunsigned n_slots;\n \tunsigned lcore_id;\n+\tunsigned int i;\n \tstruct lcore_cache *cached_free_slots = NULL;\n \tint32_t ret_val;\n+\tstruct rte_hash_bucket *last;\n \n \tprim_bucket_idx = sig & h->bucket_bitmask;\n \tprim_bkt = &h->buckets[prim_bucket_idx];\n@@ -739,10 +821,12 @@ __rte_hash_add_key_with_hash(const struct rte_hash *h, const void *key,\n \t}\n \n \t/* Check if key is already inserted in secondary location */\n-\tret = search_and_update(h, data, key, sec_bkt, alt_hash, sig);\n-\tif (ret != -1) {\n-\t\t__hash_rw_writer_unlock(h);\n-\t\treturn ret;\n+\tFOR_EACH_BUCKET(cur_bkt, sec_bkt) {\n+\t\tret = search_and_update(h, data, key, cur_bkt, alt_hash, sig);\n+\t\tif (ret != -1) {\n+\t\t\t__hash_rw_writer_unlock(h);\n+\t\t\treturn ret;\n+\t\t}\n \t}\n \t__hash_rw_writer_unlock(h);\n \n@@ -808,10 +892,70 @@ __rte_hash_add_key_with_hash(const struct rte_hash *h, const void *key,\n \telse if (ret == 1) {\n \t\tenqueue_slot_back(h, cached_free_slots, slot_id);\n \t\treturn ret_val;\n-\t} else {\n+\t}\n+\n+\t/* if ext table not enabled, we failed the insertion */\n+\tif (!h->ext_table_support) {\n \t\tenqueue_slot_back(h, cached_free_slots, slot_id);\n \t\treturn ret;\n \t}\n+\n+\t/* Now we need to go through the extendable bucket. Protection is needed\n+\t * to protect all extendable bucket processes.\n+\t */\n+\t__hash_rw_writer_lock(h);\n+\t/* We check for duplicates again since could be inserted before the lock */\n+\tret = search_and_update(h, data, key, prim_bkt, sig, alt_hash);\n+\tif (ret != -1) {\n+\t\tenqueue_slot_back(h, cached_free_slots, slot_id);\n+\t\tgoto failure;\n+\t}\n+\n+\tFOR_EACH_BUCKET(cur_bkt, sec_bkt) {\n+\t\tret = search_and_update(h, data, key, cur_bkt, alt_hash, sig);\n+\t\tif (ret != -1) {\n+\t\t\tenqueue_slot_back(h, cached_free_slots, slot_id);\n+\t\t\tgoto failure;\n+\t\t}\n+\t}\n+\n+\t/* Search sec and ext buckets to find an empty entry to insert. */\n+\tFOR_EACH_BUCKET(cur_bkt, sec_bkt) {\n+\t\tfor (i = 0; i < RTE_HASH_BUCKET_ENTRIES; i++) {\n+\t\t\t/* Check if slot is available */\n+\t\t\tif (likely(cur_bkt->key_idx[i] == EMPTY_SLOT)) {\n+\t\t\t\tcur_bkt->sig_current[i] = alt_hash;\n+\t\t\t\tcur_bkt->sig_alt[i] = sig;\n+\t\t\t\tcur_bkt->key_idx[i] = new_idx;\n+\t\t\t\t__hash_rw_writer_unlock(h);\n+\t\t\t\treturn new_idx - 1;\n+\t\t\t}\n+\t\t}\n+\t}\n+\n+\t/* Failed to get an empty entry from extendable buckets. Link a new\n+\t * extendable bucket. We first get a free bucket from ring.\n+\t */\n+\tif (rte_ring_sc_dequeue(h->free_ext_bkts, &ext_bkt_id) != 0) {\n+\t\tret = -ENOSPC;\n+\t\tgoto failure;\n+\t}\n+\n+\tbkt_id = (uint32_t)((uintptr_t)ext_bkt_id) - 1;\n+\t/* Use the first location of the new bucket */\n+\t(h->buckets_ext[bkt_id]).sig_current[0] = alt_hash;\n+\t(h->buckets_ext[bkt_id]).sig_alt[0] = sig;\n+\t(h->buckets_ext[bkt_id]).key_idx[0] = new_idx;\n+\t/* Link the new bucket to sec bucket linked list */\n+\tlast = rte_hash_get_last_bkt(sec_bkt);\n+\tlast->next = &h->buckets_ext[bkt_id];\n+\t__hash_rw_writer_unlock(h);\n+\treturn new_idx - 1;\n+\n+failure:\n+\t__hash_rw_writer_unlock(h);\n+\treturn ret;\n+\n }\n \n int32_t\n@@ -890,7 +1034,7 @@ __rte_hash_lookup_with_hash(const struct rte_hash *h, const void *key,\n {\n \tuint32_t bucket_idx;\n \thash_sig_t alt_hash;\n-\tstruct rte_hash_bucket *bkt;\n+\tstruct rte_hash_bucket *bkt, *cur_bkt;\n \tint ret;\n \n \tbucket_idx = sig & h->bucket_bitmask;\n@@ -910,10 +1054,12 @@ __rte_hash_lookup_with_hash(const struct rte_hash *h, const void *key,\n \tbkt = &h->buckets[bucket_idx];\n \n \t/* Check if key is in secondary location */\n-\tret = search_one_bucket(h, key, alt_hash, data, bkt);\n-\tif (ret != -1) {\n-\t\t__hash_rw_reader_unlock(h);\n-\t\treturn ret;\n+\tFOR_EACH_BUCKET(cur_bkt, bkt) {\n+\t\tret = search_one_bucket(h, key, alt_hash, data, cur_bkt);\n+\t\tif (ret != -1) {\n+\t\t\t__hash_rw_reader_unlock(h);\n+\t\t\treturn ret;\n+\t\t}\n \t}\n \t__hash_rw_reader_unlock(h);\n \treturn -ENOENT;\n@@ -978,16 +1124,42 @@ remove_entry(const struct rte_hash *h, struct rte_hash_bucket *bkt, unsigned i)\n \t}\n }\n \n+/* Compact the linked list by moving key from last entry in linked list to the\n+ * empty slot.\n+ */\n+static inline void\n+__rte_hash_compact_ll(struct rte_hash_bucket *cur_bkt, int pos) {\n+\tint i;\n+\tstruct rte_hash_bucket *last_bkt;\n+\n+\tif (!cur_bkt->next)\n+\t\treturn;\n+\n+\tlast_bkt = rte_hash_get_last_bkt(cur_bkt);\n+\n+\tfor (i = RTE_HASH_BUCKET_ENTRIES - 1; i >= 0; i--) {\n+\t\tif (last_bkt->key_idx[i] != EMPTY_SLOT) {\n+\t\t\tcur_bkt->key_idx[pos] = last_bkt->key_idx[i];\n+\t\t\tcur_bkt->sig_current[pos] = last_bkt->sig_current[i];\n+\t\t\tcur_bkt->sig_alt[pos] = last_bkt->sig_alt[i];\n+\t\t\tlast_bkt->sig_current[i] = NULL_SIGNATURE;\n+\t\t\tlast_bkt->sig_alt[i] = NULL_SIGNATURE;\n+\t\t\tlast_bkt->key_idx[i] = EMPTY_SLOT;\n+\t\t\treturn;\n+\t\t}\n+\t}\n+}\n+\n /* Search one bucket and remove the matched key */\n static inline int32_t\n search_and_remove(const struct rte_hash *h, const void *key,\n-\t\t\tstruct rte_hash_bucket *bkt, hash_sig_t sig)\n+\t\t\tstruct rte_hash_bucket *bkt, hash_sig_t sig, int *pos)\n {\n \tstruct rte_hash_key *k, *keys = h->key_store;\n \tunsigned int i;\n \tint32_t ret;\n \n-\t/* Check if key is in primary location */\n+\t/* Check if key is in bucket */\n \tfor (i = 0; i < RTE_HASH_BUCKET_ENTRIES; i++) {\n \t\tif (bkt->sig_current[i] == sig &&\n \t\t\t\tbkt->key_idx[i] != EMPTY_SLOT) {\n@@ -996,12 +1168,12 @@ search_and_remove(const struct rte_hash *h, const void *key,\n \t\t\tif (rte_hash_cmp_eq(key, k->key, h) == 0) {\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/* Return index where key is stored,\n \t\t\t\t * subtracting the first dummy index\n \t\t\t\t */\n \t\t\t\tret = bkt->key_idx[i] - 1;\n \t\t\t\tbkt->key_idx[i] = EMPTY_SLOT;\n+\t\t\t\t*pos = i;\n \t\t\t\treturn ret;\n \t\t\t}\n \t\t}\n@@ -1015,34 +1187,66 @@ __rte_hash_del_key_with_hash(const struct rte_hash *h, const void *key,\n {\n \tuint32_t bucket_idx;\n \thash_sig_t alt_hash;\n-\tstruct rte_hash_bucket *bkt;\n-\tint32_t ret;\n+\tstruct rte_hash_bucket *prim_bkt, *sec_bkt, *prev_bkt, *last_bkt;\n+\tstruct rte_hash_bucket *cur_bkt;\n+\tint pos;\n+\tint32_t ret, i;\n \n \tbucket_idx = sig & h->bucket_bitmask;\n-\tbkt = &h->buckets[bucket_idx];\n+\tprim_bkt = &h->buckets[bucket_idx];\n \n \t__hash_rw_writer_lock(h);\n \t/* look for key in primary bucket */\n-\tret = search_and_remove(h, key, bkt, sig);\n+\tret = search_and_remove(h, key, prim_bkt, sig, &pos);\n \tif (ret != -1) {\n-\t\t__hash_rw_writer_unlock(h);\n-\t\treturn ret;\n+\t\t__rte_hash_compact_ll(prim_bkt, pos);\n+\t\tlast_bkt = prim_bkt->next;\n+\t\tprev_bkt = prim_bkt;\n+\t\tgoto return_bkt;\n \t}\n \n \t/* Calculate secondary hash */\n \talt_hash = rte_hash_secondary_hash(sig);\n \tbucket_idx = alt_hash & h->bucket_bitmask;\n-\tbkt = &h->buckets[bucket_idx];\n+\tsec_bkt = &h->buckets[bucket_idx];\n+\n+\tFOR_EACH_BUCKET(cur_bkt, sec_bkt) {\n+\t\tret = search_and_remove(h, key, cur_bkt, alt_hash, &pos);\n+\t\tif (ret != -1) {\n+\t\t\t__rte_hash_compact_ll(cur_bkt, pos);\n+\t\t\tlast_bkt = sec_bkt->next;\n+\t\t\tprev_bkt = sec_bkt;\n+\t\t\tgoto return_bkt;\n+\t\t}\n+\t}\n \n-\t/* look for key in secondary bucket */\n-\tret = search_and_remove(h, key, bkt, alt_hash);\n-\tif (ret != -1) {\n+\t__hash_rw_writer_unlock(h);\n+\treturn -ENOENT;\n+\n+/* Search last bucket to see if empty to be recycled */\n+return_bkt:\n+\tif (!last_bkt) {\n \t\t__hash_rw_writer_unlock(h);\n \t\treturn ret;\n \t}\n+\twhile (last_bkt->next) {\n+\t\tprev_bkt = last_bkt;\n+\t\tlast_bkt = last_bkt->next;\n+\t}\n+\n+\tfor (i = 0; i < RTE_HASH_BUCKET_ENTRIES; i++) {\n+\t\tif (last_bkt->key_idx[i] != EMPTY_SLOT)\n+\t\t\tbreak;\n+\t}\n+\t/* found empty bucket and recycle */\n+\tif (i == RTE_HASH_BUCKET_ENTRIES) {\n+\t\tprev_bkt->next = last_bkt->next = NULL;\n+\t\tuint32_t index = last_bkt - h->buckets_ext + 1;\n+\t\trte_ring_sp_enqueue(h->free_ext_bkts, (void *)(uintptr_t)index);\n+\t}\n \n \t__hash_rw_writer_unlock(h);\n-\treturn -ENOENT;\n+\treturn ret;\n }\n \n int32_t\n@@ -1143,12 +1347,14 @@ __rte_hash_lookup_bulk(const struct rte_hash *h, const void **keys,\n {\n \tuint64_t hits = 0;\n \tint32_t i;\n+\tint32_t ret;\n \tuint32_t prim_hash[RTE_HASH_LOOKUP_BULK_MAX];\n \tuint32_t sec_hash[RTE_HASH_LOOKUP_BULK_MAX];\n \tconst struct rte_hash_bucket *primary_bkt[RTE_HASH_LOOKUP_BULK_MAX];\n \tconst struct rte_hash_bucket *secondary_bkt[RTE_HASH_LOOKUP_BULK_MAX];\n \tuint32_t prim_hitmask[RTE_HASH_LOOKUP_BULK_MAX] = {0};\n \tuint32_t sec_hitmask[RTE_HASH_LOOKUP_BULK_MAX] = {0};\n+\tstruct rte_hash_bucket *cur_bkt, *next_bkt;\n \n \t/* Prefetch first keys */\n \tfor (i = 0; i < PREFETCH_OFFSET && i < num_keys; i++)\n@@ -1266,6 +1472,34 @@ __rte_hash_lookup_bulk(const struct rte_hash *h, const void **keys,\n \t\tcontinue;\n \t}\n \n+\t/* all found, do not need to go through ext bkt */\n+\tif ((hits == ((1ULL << num_keys) - 1)) || !h->ext_table_support) {\n+\t\tif (hit_mask != NULL)\n+\t\t\t*hit_mask = hits;\n+\t\t__hash_rw_reader_unlock(h);\n+\t\treturn;\n+\t}\n+\n+\t/* need to check ext buckets for match */\n+\tfor (i = 0; i < num_keys; i++) {\n+\t\tif ((hits & (1ULL << i)) != 0)\n+\t\t\tcontinue;\n+\t\tnext_bkt = secondary_bkt[i]->next;\n+\t\tFOR_EACH_BUCKET(cur_bkt, next_bkt) {\n+\t\t\tif (data != NULL)\n+\t\t\t\tret = search_one_bucket(h, keys[i],\n+\t\t\t\t\t\tsec_hash[i], &data[i], cur_bkt);\n+\t\t\telse\n+\t\t\t\tret = search_one_bucket(h, keys[i],\n+\t\t\t\t\t\tsec_hash[i], NULL, cur_bkt);\n+\t\t\tif (ret != -1) {\n+\t\t\t\tpositions[i] = ret;\n+\t\t\t\thits |= 1ULL << i;\n+\t\t\t\tbreak;\n+\t\t\t}\n+\t\t}\n+\t}\n+\n \t__hash_rw_reader_unlock(h);\n \n \tif (hit_mask != NULL)\n@@ -1308,10 +1542,13 @@ rte_hash_iterate(const struct rte_hash *h, const void **key, void **data, uint32\n \n \tRETURN_IF_TRUE(((h == NULL) || (next == NULL)), -EINVAL);\n \n-\tconst uint32_t total_entries = h->num_buckets * RTE_HASH_BUCKET_ENTRIES;\n-\t/* Out of bounds */\n-\tif (*next >= total_entries)\n-\t\treturn -ENOENT;\n+\tconst uint32_t total_entries_main = h->num_buckets *\n+\t\t\t\t\t\t\tRTE_HASH_BUCKET_ENTRIES;\n+\tconst uint32_t total_entries = total_entries_main << 1;\n+\n+\t/* Out of bounds of all buckets (both main table and ext table */\n+\tif (*next >= total_entries_main)\n+\t\tgoto extend_table;\n \n \t/* Calculate bucket and index of current iterator */\n \tbucket_idx = *next / RTE_HASH_BUCKET_ENTRIES;\n@@ -1322,14 +1559,13 @@ rte_hash_iterate(const struct rte_hash *h, const void **key, void **data, uint32\n \twhile (h->buckets[bucket_idx].key_idx[idx] == EMPTY_SLOT) {\n \t\t(*next)++;\n \t\t/* End of table */\n-\t\tif (*next == total_entries) {\n+\t\tif (*next == total_entries_main) {\n \t\t\t__hash_rw_reader_unlock(h);\n-\t\t\treturn -ENOENT;\n+\t\t\tgoto extend_table;\n \t\t}\n \t\tbucket_idx = *next / RTE_HASH_BUCKET_ENTRIES;\n \t\tidx = *next % RTE_HASH_BUCKET_ENTRIES;\n \t}\n-\n \t/* Get position of entry in key table */\n \tposition = h->buckets[bucket_idx].key_idx[idx];\n \tnext_key = (struct rte_hash_key *) ((char *)h->key_store +\n@@ -1344,4 +1580,38 @@ rte_hash_iterate(const struct rte_hash *h, const void **key, void **data, uint32\n \t(*next)++;\n \n \treturn position - 1;\n+\n+/* Begin to iterate extendable buckets */\n+extend_table:\n+\t/* Out of total bound or if ext bucket feature is not enabled */\n+\tif (*next >= total_entries || !h->ext_table_support)\n+\t\treturn -ENOENT;\n+\n+\tbucket_idx = (*next - total_entries_main) / RTE_HASH_BUCKET_ENTRIES;\n+\tidx = (*next - total_entries_main) % RTE_HASH_BUCKET_ENTRIES;\n+\n+\t__hash_rw_reader_lock(h);\n+\twhile (h->buckets_ext[bucket_idx].key_idx[idx] == EMPTY_SLOT) {\n+\t\t(*next)++;\n+\t\tif (*next == total_entries) {\n+\t\t\t__hash_rw_reader_unlock(h);\n+\t\t\treturn -ENOENT;\n+\t\t}\n+\t\tbucket_idx = (*next - total_entries_main) /\n+\t\t\t\t\t\tRTE_HASH_BUCKET_ENTRIES;\n+\t\tidx = (*next - total_entries_main) % RTE_HASH_BUCKET_ENTRIES;\n+\t}\n+\t/* Get position of entry in key table */\n+\tposition = h->buckets_ext[bucket_idx].key_idx[idx];\n+\tnext_key = (struct rte_hash_key *) ((char *)h->key_store +\n+\t\t\t\tposition * h->key_entry_size);\n+\t/* Return key and data */\n+\t*key = next_key->key;\n+\t*data = next_key->pdata;\n+\n+\t__hash_rw_reader_unlock(h);\n+\n+\t/* Increment iterator */\n+\t(*next)++;\n+\treturn position - 1;\n }\ndiff --git a/lib/librte_hash/rte_cuckoo_hash.h b/lib/librte_hash/rte_cuckoo_hash.h\nindex fc0e5c2..e601520 100644\n--- a/lib/librte_hash/rte_cuckoo_hash.h\n+++ b/lib/librte_hash/rte_cuckoo_hash.h\n@@ -142,6 +142,8 @@ struct rte_hash_bucket {\n \thash_sig_t sig_alt[RTE_HASH_BUCKET_ENTRIES];\n \n \tuint8_t flag[RTE_HASH_BUCKET_ENTRIES];\n+\n+\tvoid *next;\n } __rte_cache_aligned;\n \n /** A hash table structure. */\n@@ -166,6 +168,7 @@ 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 ext_table_support; /**< Enable extendable bucket table */\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;\n@@ -184,6 +187,8 @@ struct rte_hash {\n \t * to the key table.\n \t */\n \trte_rwlock_t *readwrite_lock; /**< Read-write lock thread-safety. */\n+\tstruct rte_hash_bucket *buckets_ext; /**< Extra buckets array */\n+\tstruct rte_ring *free_ext_bkts; /**< Ring of indexes of free buckets */\n } __rte_cache_aligned;\n \n struct queue_node {\ndiff --git a/lib/librte_hash/rte_hash.h b/lib/librte_hash/rte_hash.h\nindex 9e7d931..11d8e28 100644\n--- a/lib/librte_hash/rte_hash.h\n+++ b/lib/librte_hash/rte_hash.h\n@@ -37,6 +37,9 @@ extern \"C\" {\n /** Flag to support reader writer concurrency */\n #define RTE_HASH_EXTRA_FLAGS_RW_CONCURRENCY 0x04\n \n+/** Flag to indicate the extendabe bucket table feature should be used */\n+#define RTE_HASH_EXTRA_FLAGS_EXT_TABLE 0x08\n+\n /** Signature of key that is stored internally. */\n typedef uint32_t hash_sig_t;\n \n", "prefixes": [ "v4", "2/4" ] }