From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from EUR03-DB5-obe.outbound.protection.outlook.com (mail-eopbgr40054.outbound.protection.outlook.com [40.107.4.54]) by dpdk.org (Postfix) with ESMTP id E171C1DBA for ; Mon, 1 Oct 2018 01:05:52 +0200 (CEST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=armh.onmicrosoft.com; s=selector1-arm-com; h=From:Date:Subject:Message-ID:Content-Type:MIME-Version:X-MS-Exchange-SenderADCheck; bh=dARvHxK5iTbEYI7LyJKGVT3Rys7mGPDoyUsTizuohFQ=; b=JyUn/cRpIZwCodbh/8Mufcihav6pmkZsQPZsweM68OH4/RnZ+eEqBy8+YONIdMehQQM4U809W9oGPwMTaQtArSvQI766/aEst9A/XwCx3YVoD720sXt0fZtYv5ONim4FHj9xC7XEP1EHCePoImTDyWpF8ESD0+ccEJ6XlEKYVwA= Received: from AM6PR08MB3672.eurprd08.prod.outlook.com (20.177.115.29) by AM6PR08MB3000.eurprd08.prod.outlook.com (52.135.163.29) with Microsoft SMTP Server (version=TLS1_2, cipher=TLS_ECDHE_RSA_WITH_AES_256_GCM_SHA384) id 15.20.1185.23; Sun, 30 Sep 2018 23:05:51 +0000 Received: from AM6PR08MB3672.eurprd08.prod.outlook.com ([fe80::f423:e46a:a03c:e928]) by AM6PR08MB3672.eurprd08.prod.outlook.com ([fe80::f423:e46a:a03c:e928%2]) with mapi id 15.20.1185.024; Sun, 30 Sep 2018 23:05:51 +0000 From: Honnappa Nagarahalli To: "Wang, Yipeng1" , "Richardson, Bruce" , "De Lara Guarch, Pablo" CC: "dev@dpdk.org" , "Gavin Hu (Arm Technology China)" , Steve Capper , Ola Liljedahl , nd Thread-Topic: [dpdk-dev] [PATCH 3/4] hash: fix rw concurrency while moving keys Thread-Index: AQHURgTOka1Jda13D0abVoUE3K2emKUFAR8AgASQU7A= Date: Sun, 30 Sep 2018 23:05:51 +0000 Message-ID: References: <1536253938-192391-1-git-send-email-honnappa.nagarahalli@arm.com> <1536253938-192391-4-git-send-email-honnappa.nagarahalli@arm.com> In-Reply-To: Accept-Language: en-US Content-Language: en-US X-MS-Has-Attach: X-MS-TNEF-Correlator: authentication-results: spf=none (sender IP is ) smtp.mailfrom=Honnappa.Nagarahalli@arm.com; x-originating-ip: [217.140.111.135] x-ms-publictraffictype: Email x-microsoft-exchange-diagnostics: 1; AM6PR08MB3000; 6:/D8uvokCnqG92faBwwAMo93AADp/ZIPFpAnipo6kzl5tZfe/OOLzMGDOiuH4+DTieOC+63NeAmG83ZG5dErSNOZAldYlbzIkgddF/bRsG4CdB0636Yi/pPJhMZ55WAjNneM3TGxR5SUSZp1/jV++aPKar7LkIEoV/Q8ZEWNduYxvGjjip6WUK5+QnduYMXOdtYezJqRofLXF+pKepX59tFBwqz6/AJej0LYZIvv+ZXaKXaoAFlEElFTl5NiYhSSKEE/UhKVGbr/EubzSm5DjBI7UlKY/ef509Jr8BAT4uGRtE16vGQvfTgx4LBWbJy9z1IhgwBT5CkIXn9jX0vtxcCVp9b9ezXUZxV1H+g4WN9JFzxT9tgB7zRYuWtc6US0YQaQlTcz9GCpExJnHBOAoWCasfDvSOLC/oo+z89BE3GCuWJ4bgW4MtM9xYXzOhjnbL7RdZZD5eNofdUc3O1S3fQ==; 5:6qaSTiyLWv9FCPGwpLag8SoK8d0PL/JUr6MYxfVjlt8S0B6/MeqwYmo/jZdeIzgVsNRAdOiAHqc5L2uR+RPmC47D7oX+8UpYzdAHLX19sLBNYCSrzvRvv7B96FhVfKHzywwO30LQ8Mn2ySZIcET37uDTmZnreWSHnYTwkY75Wmk=; 7:G9rYNd0H59ndSCjX2HDYs5Sw/Mn6FJ6/Ux+ZmfOl8Z8erJ3oegPz9ko7ZTdSg0f+KcA+pU1vce8xmw7Gx+evQX1/yQMNt69/NJdAyERP8VEz/JYL9p2N19Ztuglu+zluy35jgy7UxF3WaMWMMmAxohrwTxpDPbuQxY9Udk9vJksr2GlbIk3j/Za+oeCMgaZ8ylLvjHckQcRj++f1Dyz3OgV1C64Zi6XM9COU8VQC7SqG0mOcCgrmNu10b+vzSvHF x-ms-exchange-antispam-srfa-diagnostics: SOS;SOR; x-ms-office365-filtering-correlation-id: 4b6044ac-432f-4f55-4b61-08d627294462 x-ms-office365-filtering-ht: Tenant x-microsoft-antispam: BCL:0; PCL:0; RULEID:(7020095)(4652040)(8989299)(4534165)(4627221)(201703031133081)(201702281549075)(8990200)(5600074)(711020)(4618075)(2017052603328)(7153060)(7193020); SRVR:AM6PR08MB3000; x-ms-traffictypediagnostic: AM6PR08MB3000: nodisclaimer: True x-microsoft-antispam-prvs: x-exchange-antispam-report-test: UriScan:; x-ms-exchange-senderadcheck: 1 x-exchange-antispam-report-cfa-test: BCL:0; PCL:0; RULEID:(8211001083)(6040522)(2401047)(8121501046)(5005006)(10201501046)(3231355)(944501410)(52105095)(3002001)(93006095)(93001095)(6055026)(149066)(150057)(6041310)(20161123564045)(201703131423095)(201702281528075)(20161123555045)(201703061421075)(201703061406153)(20161123560045)(20161123562045)(20161123558120)(201708071742011)(7699051); SRVR:AM6PR08MB3000; BCL:0; PCL:0; RULEID:; SRVR:AM6PR08MB3000; x-forefront-prvs: 08118EFC2B x-forefront-antispam-report: SFV:NSPM; SFS:(10009020)(346002)(376002)(136003)(39850400004)(366004)(396003)(189003)(199004)(106356001)(72206003)(5250100002)(966005)(11346002)(486006)(476003)(4326008)(478600001)(33656002)(25786009)(2900100001)(186003)(229853002)(446003)(26005)(6246003)(2906002)(102836004)(55016002)(66066001)(97736004)(14454004)(34290500001)(6306002)(68736007)(76176011)(5660300001)(86362001)(6506007)(53936002)(8936002)(9686003)(14444005)(74316002)(316002)(99286004)(305945005)(71200400001)(6436002)(71190400001)(81166006)(105586002)(7736002)(54906003)(256004)(6116002)(3846002)(8676002)(81156014)(7696005)(110136005); DIR:OUT; SFP:1101; SCL:1; SRVR:AM6PR08MB3000; H:AM6PR08MB3672.eurprd08.prod.outlook.com; FPR:; SPF:None; LANG:en; PTR:InfoNoRecords; MX:1; A:1; received-spf: None (protection.outlook.com: arm.com does not designate permitted sender hosts) x-microsoft-antispam-message-info: B2gUfHOwgJ+JltFpDjZruovwIXJND+6sYTumec2RVM3UF6INrSKPIgRK+1kGgPbSBmhoxgGLz+4z8PDcVxQ5x4Ok567MJOVHluh8WsomUG+mcQhNM/DsKoACX2d7ZMElNDbEwqpbJIdauh38LBpZEdP395wvoHSQ/DBM4HYiahOkmjME1254grREqIo8vQKlseZs1H4gQpFmG7iq32d7LF+10830rPg4VQnfnjH8jG+ZDt1LymsQb6iYzaabLJDO2UEiGzGgAcziiRCGGcYT0Cn43yWtgeNjG0g+rC3IcWIo/dJB6TEwBs9sY444dSoc/CPsZZIzRyAaPbasQvzIDQgIEzKTgBES8B841HgLVxM= spamdiagnosticoutput: 1:99 spamdiagnosticmetadata: NSPM Content-Type: text/plain; charset="us-ascii" Content-Transfer-Encoding: quoted-printable MIME-Version: 1.0 X-OriginatorOrg: arm.com X-MS-Exchange-CrossTenant-Network-Message-Id: 4b6044ac-432f-4f55-4b61-08d627294462 X-MS-Exchange-CrossTenant-originalarrivaltime: 30 Sep 2018 23:05:51.3157 (UTC) X-MS-Exchange-CrossTenant-fromentityheader: Hosted X-MS-Exchange-CrossTenant-id: f34e5979-57d9-4aaa-ad4d-b122a662184d X-MS-Exchange-Transport-CrossTenantHeadersStamped: AM6PR08MB3000 Subject: Re: [dpdk-dev] [PATCH 3/4] hash: fix rw concurrency while moving keys 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: , X-List-Received-Date: Sun, 30 Sep 2018 23:05:53 -0000 > > > >Reader-writer concurrency issue, caused by moving the keys to their > >alternative locations during key insert, is solved by introducing a > >global counter(tbl_chng_cnt) indicating a change in table. > > > >@@ -662,6 +679,20 @@ rte_hash_cuckoo_move_insert_mw(const struct > rte_hash *h, > > curr_bkt =3D curr_node->bkt; > > } > > > >+ /* Inform the previous move. The current move need > >+ * not be informed now as the current bucket entry > >+ * is present in both primary and secondary. > >+ * Since there is one writer, load acquires on > >+ * tbl_chng_cnt are not required. > >+ */ > >+ __atomic_store_n(&h->tbl_chng_cnt, > >+ h->tbl_chng_cnt + 1, > >+ __ATOMIC_RELEASE); > >+ /* The stores to sig_alt and sig_current should not > >+ * move above the store to tbl_chng_cnt. > >+ */ > >+ __atomic_thread_fence(__ATOMIC_RELEASE); > >+ > [Wang, Yipeng] I believe for X86 this fence should not be compiled to any > code, otherwise we need macros for the compile time check. '__atomic_thread_fence(__ATOMIC_RELEASE)' provides load-load and load-store= fence [1]. Hence, it should not add any barriers for x86. [1] https://preshing.com/20130922/acquire-and-release-fences/ >=20 > >@@ -926,30 +957,56 @@ __rte_hash_lookup_with_hash(const struct > rte_hash *h, const void *key, > > uint32_t bucket_idx; > > hash_sig_t alt_hash; > > struct rte_hash_bucket *bkt; > >+ uint32_t cnt_b, cnt_a; > > int ret; > > > >- bucket_idx =3D sig & h->bucket_bitmask; > >- bkt =3D &h->buckets[bucket_idx]; > >- > > __hash_rw_reader_lock(h); > > > >- /* Check if key is in primary location */ > >- ret =3D search_one_bucket(h, key, sig, data, bkt); > >- if (ret !=3D -1) { > >- __hash_rw_reader_unlock(h); > >- return ret; > >- } > >- /* Calculate secondary hash */ > >- alt_hash =3D rte_hash_secondary_hash(sig); > >- bucket_idx =3D alt_hash & h->bucket_bitmask; > >- bkt =3D &h->buckets[bucket_idx]; > >+ do { > [Wang, Yipeng] As far as I know, the MemC3 paper "MemC3: Compact and > Concurrent MemCache with Dumber Caching and Smarter Hashing" > as well as OvS cmap uses similar version counter to implement read-write > concurrency for hash table, but one difference is reader checks even/odd = of > the version counter to make sure there is no concurrent writer. Could you= just > double check and confirm that this is not needed for your implementation? >=20 I relooked at this paper. My patch makes use of the fact that during the pr= ocess of shifting the key will be present in both primary and secondary buc= kets. The check for odd version counter is not required as the full key com= parison would have identified any false signature matches. > >--- a/lib/librte_hash/rte_hash.h > >+++ b/lib/librte_hash/rte_hash.h > >@@ -156,7 +156,7 @@ rte_hash_count(const struct rte_hash *h); > > * - -ENOSPC if there is no space in the hash for this key. > > */ > > int > >-rte_hash_add_key_data(const struct rte_hash *h, const void *key, void > >*data); > >+rte_hash_add_key_data(struct rte_hash *h, const void *key, void > >+*data); > > > > /** > > * Add a key-value pair with a pre-computed hash value @@ -180,7 > >+180,7 @@ rte_hash_add_key_data(const struct rte_hash *h, const void > *key, void *data); > > * - -ENOSPC if there is no space in the hash for this key. > > */ > > int32_t > >-rte_hash_add_key_with_hash_data(const struct rte_hash *h, const void > >*key, > >+rte_hash_add_key_with_hash_data(struct rte_hash *h, const void *key, > > hash_sig_t sig, void *data); > > > > /** > >@@ -200,7 +200,7 @@ rte_hash_add_key_with_hash_data(const struct > rte_hash *h, const void *key, > > * array of user data. This value is unique for this key. > > */ > > int32_t > >-rte_hash_add_key(const struct rte_hash *h, const void *key); > >+rte_hash_add_key(struct rte_hash *h, const void *key); > > > > /** > > * Add a key to an existing hash table. > >@@ -222,7 +222,7 @@ rte_hash_add_key(const struct rte_hash *h, const > void *key); > > * array of user data. This value is unique for this key. > > */ > > int32_t > >-rte_hash_add_key_with_hash(const struct rte_hash *h, const void *key, > >hash_sig_t sig); > >+rte_hash_add_key_with_hash(struct rte_hash *h, const void *key, > >+hash_sig_t sig); > > > > / >=20 > I think the above changes will break ABI by changing the parameter type? > Other people may know better on this.