Cover Detail
Show a cover letter.
GET /api/covers/45795/?format=api
{ "id": 45795, "url": "http://patches.dpdk.org/api/covers/45795/?format=api", "web_url": "http://patches.dpdk.org/project/dpdk/cover/1538418902-154892-1-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": "<1538418902-154892-1-git-send-email-yipeng1.wang@intel.com>", "list_archive_url": "https://inbox.dpdk.org/dev/1538418902-154892-1-git-send-email-yipeng1.wang@intel.com", "date": "2018-10-01T18:34:58", "name": "[v5,0/4] hash: add extendable bucket and partial key hashing", "submitter": { "id": 754, "url": "http://patches.dpdk.org/api/people/754/?format=api", "name": "Wang, Yipeng1", "email": "yipeng1.wang@intel.com" }, "mbox": "http://patches.dpdk.org/project/dpdk/cover/1538418902-154892-1-git-send-email-yipeng1.wang@intel.com/mbox/", "series": [ { "id": 1624, "url": "http://patches.dpdk.org/api/series/1624/?format=api", "web_url": "http://patches.dpdk.org/project/dpdk/list/?series=1624", "date": "2018-10-01T18:34:58", "name": "hash: add extendable bucket and partial key hashing", "version": 5, "mbox": "http://patches.dpdk.org/series/1624/mbox/" } ], "comments": "http://patches.dpdk.org/api/covers/45795/comments/", "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 3AD704F91;\n\tTue, 2 Oct 2018 03:40:17 +0200 (CEST)", "from mga03.intel.com (mga03.intel.com [134.134.136.65])\n\tby dpdk.org (Postfix) with ESMTP id 5E9474CB3\n\tfor <dev@dpdk.org>; Tue, 2 Oct 2018 03:40:14 +0200 (CEST)", "from fmsmga002.fm.intel.com ([10.253.24.26])\n\tby orsmga103.jf.intel.com with ESMTP/TLS/DHE-RSA-AES256-GCM-SHA384;\n\t01 Oct 2018 18:40:13 -0700", "from skx-yipeng.jf.intel.com ([10.54.81.175])\n\tby fmsmga002.fm.intel.com with ESMTP; 01 Oct 2018 18:40:13 -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,329,1534834800\"; d=\"scan'208\";a=\"91287626\"", "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": "Mon, 1 Oct 2018 11:34:58 -0700", "Message-Id": "<1538418902-154892-1-git-send-email-yipeng1.wang@intel.com>", "X-Mailer": "git-send-email 2.7.4", "In-Reply-To": "<1537993618-92630-1-git-send-email-yipeng1.wang@intel.com>", "References": "<1537993618-92630-1-git-send-email-yipeng1.wang@intel.com>", "Subject": "[dpdk-dev] [PATCH v5 0/4] hash: add extendable bucket and partial\n\tkey hashing", "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": "This patch set made two major optimizations over the current rte_hash\nlibrary.\n\nFirst, it adds Extendable Bucket Table feature: a new structure that can\naccommodate keys that failed to get inserted into the main hash table due to\nthe unlikely event of excessive hash collisions. The hash table buckets will\nget extended using a linked list to host these keys. This new design will\nguarantee insertion of 100% of the keys for a given hash table size with\nminimal overhead. A new flag value is added for user to indicate if the\nextendable bucket feature should be enabled or not. The linked list buckets is\nsimilar concept to the extendable bucket hash table in packet framework.\nIn details, for insertion, the linked buckets will be used to store the keys\nthat fail to get in the primary and the secondary bucket and the cuckoo path\ncould not find an empty location for the maximum path length (small\nprobability). For lookup, the key is checked first in the primary, then the\nsecondary, then if the secondary is extended the linked list is traversed\nfor a possible match.\n\nSecond, the patch set changes the current hashing algorithm to be \"partial-key\nhashing\". Partial-key hashing is the concept from Bin Fan, et al.'s paper\n\"MemC3: Compact and Concurrent MemCache with Dumber Caching and Smarter\nHashing\". Instead of storing both 32-bit signature and alternative signature\nin the bucket, we only store a small 16-bit signature and calculate the\nalternative bucket index by XORing the signature with the current bucket index.\nThis doubles the hash table memory efficiency since now one bucket\nonly occupies one cache line instead of two in the original design.\n\nv4->v5:\n1. hash: for the first commit, move back the lock and read \"position\" in the\nwhile condition as Honnappa suggested.\n2. hash: minor coding style change (Honnappa) and commit message typo fix.\n3. Add Review-by from Honnappa.\n\nv3->v4:\n1. hash: Revise commit message to be more clear for \"utilization\" (Honnappa)\n2. hash: in delete key function, return bucket change to use rte_ring_sp_enqueue\ninstead of rte_ring_mp_enqueue, since it is already protected inside locks.\n3. hash: update rte_hash_iterate comments (Honnappa)\n4. hash: Add a new commit to fix race condition in the rte_hash_iterate (Honnappa)\n5. hash/test: during utilization test, double check rte_hash_cnt returns correct\nvalue (Honnappa)\n6. hash: for partial-key-hashing commit, break the get_buckets_index function\ninto three. It may make future extension easier (Honnappa)\n7. hash: change the comment for typedef uint32_t hash_sig_t to be more clear\nto users (Honnappa)\n\nv2->v3:\nThe first four commits were separated from this patch set as another\nindependent patch set:\nhttps://mails.dpdk.org/archives/dev/2018-September/113118.html\n1. hash: move snprintf for ext_ring name under the ext_table condition.\n2. hash: fix memory leak by freeing ext_buckets in rte_hash_free.\n3. hash: after failing cuckoo path, search not only ext buckets, but also the\nsecondary bucket first to see if there may be an empty location now.\n4. hash: totally rewrote the key deleting function logic. If the deleted key was\nnot in the last bucket of the linked list when ext table enabled, the last\nentry in the linked list will be placed in the vacant slot from the deleted\nkey. The purpose is to compact the entries in the linked list to be more close\nto the main table. This is to make sure that not many extendable buckets are\nwasted with only one or two entries after some time of running, also benefit\nlookup speed.\n5. Other minor coding style/comments improvements.\n\nV1->V2:\n1. hash: Rewrite rte_hash_get_last_bkt to be more concise.\n2. hash: Reorder the rte_hash struct to align cache line better.\n3. test: Minor changes in auto test to add key insertion failure check during\niteration test.\n4. test: Add new commit to fix read-write test non-consecutive core issue.\n4. hash: Add a new commit to remove unnecessary code introduced by previous\npatches.\n5. hash: Comments improvement and coding style improvements over multiple\nplaces.\n\nSigned-off-by: Yipeng Wang <yipeng1.wang@intel.com>\n\nYipeng Wang (4):\n hash: fix race condition in iterate\n hash: add extendable bucket feature\n test/hash: implement extendable bucket hash test\n hash: use partial-key hashing\n\n lib/librte_hash/rte_cuckoo_hash.c | 580 ++++++++++++++++++++++++++++----------\n lib/librte_hash/rte_cuckoo_hash.h | 11 +-\n lib/librte_hash/rte_hash.h | 8 +-\n test/test/test_hash.c | 159 ++++++++++-\n test/test/test_hash_perf.c | 114 ++++++--\n 5 files changed, 677 insertions(+), 195 deletions(-)" }