From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from EUR02-VE1-obe.outbound.protection.outlook.com (mail-eopbgr20045.outbound.protection.outlook.com [40.107.2.45]) by dpdk.org (Postfix) with ESMTP id 125151B158 for ; Thu, 11 Oct 2018 07:24:25 +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=e6T9kWioKYTB6rN1J5mkF2e5Q53e36Palra8JNmsm+w=; b=L6oW1vu99gIJuKDgSEM32CS11zY2G4iYuNDfVzfLbT8obJs8P9d36mkpjzybNCWp91yaZIhSKx4JDuxaXG2x0w1kdztfGBmvXaG76J0YCXu7GBU3gbVjOSTOxdDGZq2d9eDcYDwsjj6Ke19INPb2RcqZk4KJ5GvCW7PJZcXXn9E= Received: from AM6PR08MB3672.eurprd08.prod.outlook.com (20.177.115.29) by AM6PR08MB3064.eurprd08.prod.outlook.com (52.135.163.149) with Microsoft SMTP Server (version=TLS1_2, cipher=TLS_ECDHE_RSA_WITH_AES_256_GCM_SHA384) id 15.20.1207.21; Thu, 11 Oct 2018 05:24:23 +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.027; Thu, 11 Oct 2018 05:24:23 +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 , "Gobriel, Sameh" Thread-Topic: [dpdk-dev] [PATCH 4/4] hash: enable lock-free reader-writer concurrency Thread-Index: AQHUWTzTzwGE8jRjuEmdunM9Uo3m7KULEcIAgA57ZKA= Date: Thu, 11 Oct 2018 05:24:23 +0000 Message-ID: References: <1536253938-192391-1-git-send-email-honnappa.nagarahalli@arm.com> <1536253938-192391-5-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: x-originating-ip: [217.140.103.75] x-ms-publictraffictype: Email x-microsoft-exchange-diagnostics: 1; AM6PR08MB3064; 6:itydkee98QSchSWFvhkTgnsia1c+wN3EgOrZPgiHVh5R3KIwEO7Z3WMpfj/lJ8+UpHds73rlGvpWRKD7IG0qFG9f3tho95u1ebQsbmG39OLbu/T6b9b0/0SPXWttVcLF+R4Fe6cPeuGhsp7IJ9VtwsTmuiI+ZijVqf3qs3ENQJ3puHKyP4YBisGur5WKL2YMYJPFlBglxtG9rif0acJyUKNa19O7FbBFA1ZSsJtajkCcuL73rljNgHwznDkdt1OaMU5do0hqrKzfQkX6Pd7Dka5eCQHzhPrJ8181V+ZAjTM2g4DAGeOiZpYNDM71VUkhSrLmjXa+ZSV3BYWfd8jg8nrkuIVtAYIY8Pbr4zOy7jVnxS9RxBgaDxaWRr3lV6/SwkJj3LYPh9gz2buuoA1XEi0AgDQ84j2N8zMlLD6NEFrMJejawunRRjDlLkUiv2NmhInyqRb8xul9lRdLmydEPw==; 5:hJaqyalMdOcH9l8K1ijFlQwNoLDXTPNoU/7sbUYTS4t7fRN0ne47Ai/de0jPi+u/HqNucXipFXl1PY6k62lyCdmF7uOaaHr/q3Nlu1FVlg25aEERa0UxZW+CDXlDy1tIAVS5ypq8gvbWCCvm2PIuuTjIQeHg3Xx35bPb9pTrc8M=; 7:0evc1GHGrgOnk7PGGlfM+4sxwqwIYSs6Ci746V9hYEcHfJ7gwJZItnpiA5T0bZfVjeBl841BOSjg8Fk5Ke88qfajcwLg3VA/y4yijMHSzR9aSd7p6Kwa9nD9U1OSW9Cd6MqzY9XuIHQmoFD8lhOVc3vfgBRYNV32N2foSAgL/6Kxjw530uWdrE7Qbjp4S9POFTVyd9tqBNPCmRE3alICcPZ2vc0bWFEaCpbq9z8S4g9oMw5KzSCC1qk7GzNj8JIi x-ms-exchange-antispam-srfa-diagnostics: SOS;SOR; x-ms-office365-filtering-correlation-id: 48d53d48-8060-48c1-3b7f-08d62f39ce2b x-ms-office365-filtering-ht: Tenant x-microsoft-antispam: BCL:0; PCL:0; RULEID:(7020095)(4652040)(8989299)(4534185)(4627221)(201703031133081)(201702281549075)(8990200)(5600074)(711020)(4618075)(2017052603328)(7153060)(7193020); SRVR:AM6PR08MB3064; x-ms-traffictypediagnostic: AM6PR08MB3064: nodisclaimer: True x-microsoft-antispam-prvs: x-exchange-antispam-report-test: UriScan:(278428928389397); x-ms-exchange-senderadcheck: 1 x-exchange-antispam-report-cfa-test: BCL:0; PCL:0; RULEID:(8211001083)(6040522)(2401047)(5005006)(8121501046)(3002001)(93006095)(93001095)(10201501046)(3231355)(944501410)(52105095)(6055026)(149066)(150057)(6041310)(20161123560045)(20161123558120)(20161123562045)(201703131423095)(201702281528075)(20161123555045)(201703061421075)(201703061406153)(20161123564045)(201708071742011)(7699051)(76991055); SRVR:AM6PR08MB3064; BCL:0; PCL:0; RULEID:; SRVR:AM6PR08MB3064; x-forefront-prvs: 08220FA8D6 x-forefront-antispam-report: SFV:NSPM; SFS:(10009020)(376002)(366004)(396003)(136003)(39860400002)(346002)(199004)(189003)(43544003)(476003)(3846002)(486006)(54906003)(110136005)(316002)(68736007)(25786009)(11346002)(71190400001)(71200400001)(446003)(33656002)(6116002)(14454004)(478600001)(72206003)(5660300001)(93886005)(66066001)(81166006)(8936002)(26005)(5250100002)(81156014)(7736002)(74316002)(305945005)(102836004)(186003)(6246003)(106356001)(105586002)(6346003)(2900100001)(97736004)(4326008)(2906002)(229853002)(76176011)(55016002)(14444005)(7696005)(6306002)(86362001)(6506007)(53936002)(9686003)(256004)(6436002)(99286004)(21314002); DIR:OUT; SFP:1101; SCL:1; SRVR:AM6PR08MB3064; H:AM6PR08MB3672.eurprd08.prod.outlook.com; FPR:; SPF:None; LANG:en; PTR:InfoNoRecords; A:1; MX:1; received-spf: None (protection.outlook.com: arm.com does not designate permitted sender hosts) authentication-results: spf=none (sender IP is ) smtp.mailfrom=Honnappa.Nagarahalli@arm.com; x-microsoft-antispam-message-info: PmQVcNG1Dcvgx6w8/qfxg5wsEk+N9SxpQ58oloPOHoZsjqLseEK87sU59g8PfTbS5PdHr9qU4vOlUvS9kSBBn+koFzJZ0zZjBy7QpVwADIdzLXNQvkDfuPYqMd4w9jXJKgp1J5E2VIqv4FVSz8wcM0oADFts2JvOtwnom3I/uD/2wGIGXqzxM45HiXfIRJUT3PXOScdCcBclPwc8i+O0kX0NCz6LNcF6VnmPeTwBvuPiic2Y5RaFe5osPzg5rbWxtDyciL372EkAY7upxtsJzNRWAZoX5jYFYKx9Dxo+Hqza7ccDq+NInE3UpLRwY8WSFh5lcXW5qnfDcn9rMJO6E7zykrk26jbahLyfibmnPUc= 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: 48d53d48-8060-48c1-3b7f-08d62f39ce2b X-MS-Exchange-CrossTenant-originalarrivaltime: 11 Oct 2018 05:24:23.7303 (UTC) X-MS-Exchange-CrossTenant-fromentityheader: Hosted X-MS-Exchange-CrossTenant-id: f34e5979-57d9-4aaa-ad4d-b122a662184d X-MS-Exchange-Transport-CrossTenantHeadersStamped: AM6PR08MB3064 Subject: Re: [dpdk-dev] [PATCH 4/4] hash: enable lock-free reader-writer concurrency 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: Thu, 11 Oct 2018 05:24:25 -0000 > >> > > >> >Add the flag to enable reader-writer concurrency during run time. > >> >The rte_hash_del_xxx APIs do not free the keystore element when this > >> >flag is enabled. Hence a new API, rte_hash_free_key_with_position, > >> >to free the key store element is added. > >> > > >> >+/** Flag to support lock free reader writer concurrency */ #define > >> >+RTE_HASH_EXTRA_FLAGS_RW_CONCURRENCY_LF 0x08 > >> [Wang, Yipeng] It would be good to indicate that the lockless > >> implementation works for single writer multiple readers. > >Multi-writers are supported by using the rw-lock or transactional > >memory. Essentially, we still have single writer. This patch works fine = with > multi-writer as defined by ' MULTI_WRITER_ADD' flag. I have tested it as = well. > I will enable this test case in V2. > > > >> Also, if people use a mix of the flags for example set both > >> multiwriter and LF flags, then I guess either we need to return an > >> error or maybe multiwriter should have higher priority. Currently the > >> RW_CONCURRENCY will assume MULTI_WRITER_ADD I think. > >As mentioned above, multi-writer and LF combination is supported. Yes, > RW_CONCURRENCY currently assumes MULTI_WRITER_ADD. > >I think we should separate them. > [Wang, Yipeng] It would be great if you could just add a little bit more > comments to both of the flags to be more specific on what Read write > concurrency mean in both cases, just in case users got confused. > You may also want to update the documentation later > (https://doc.dpdk.org/guides/prog_guide/hash_lib.html). I will add the documentation once the patch is accepted. >=20 > > > >> >+ > >> > /** Signature of key that is stored internally. */ typedef uint32_t > >> > hash_sig_t; > >> > > >> >@@ -143,6 +148,11 @@ rte_hash_count(const struct rte_hash *h); > >> > * and should only be called from one thread by default. > >> > * Thread safety can be enabled by setting flag during > >> > * table creation. > >> >+ * When lock free reader writer concurrency is enabled, > >> >+ * if this API is called to update an existing entry, > >> >+ * the application should free any memory allocated for > >> >+ * previous 'data' only after all the readers have stopped > >> >+ * using previous 'data'. > >> [Wang, Yipeng] Could you be more specific on this description? > >> When add_key API is called, the users do not know if it will update > >> an existing entry or inserting a new one, do they? > >I think, it will depend on the application. The applications I have > >worked on so far, added a hash entry as a result of receiving an event > >and updated it on receiving another event. I can change the comments to > indicate that the applications need to be aware of add/update operations. > [Wang, Yipeng] Even if for current rte_hash, after update, the applicatio= n may > still use the old data. It is the upper level application's Responsibilit= y. How is it > specific to lock free implementation? I agree. I think it makes sense to keep this warning, but make it not speci= fic to lock-free algorithm. I will make this change in V3. > > > >> > rte_hash_del_key(const struct rte_hash *h, const void *key); @@ > >> > -251,6 > >> >+274,12 @@ rte_hash_del_key(const struct rte_hash *h, const void > >> >+*key); > >> > * and should only be called from one thread by default. > >> > * Thread safety can be enabled by setting flag during > >> > * table creation. > >> >+ * If lock free reader writer concurrency is enabled, > >> >+ * the hash library's internal memory for the deleted > >> >+ * key is not freed. It should be freed by calling > >> >+ * rte_hash_free_key_with_position API after all > >> >+ * the readers have stopped using the hash entry > >> >+ * corresponding to this key. > >> > * > >> > * @param h > >> > * Hash table to remove the key from. > >> >@@ -264,6 +293,8 @@ rte_hash_del_key(const struct rte_hash *h, const > >> void *key); > >> > * - A positive value that can be used by the caller as an offset = into an > >> > * array of user data. This value is unique for this key, and is= the same > >> > * value that was returned when the key was added. > >> >+ * When lock free concurrency is enabled, this value should be u= sed > >> >+ * while calling the rte_hash_free_key_with_position API. > >> > */ > >> > int32_t > >> > rte_hash_del_key_with_hash(const struct rte_hash *h, const void > >> >*key, hash_sig_t sig); @@ -290,6 +321,30 @@ > >> rte_hash_get_key_with_position(const struct rte_hash *h, const > >> int32_t position, > >> > void **key); > >> > > >> [Wang, Yipeng] If possible, how about having a new delete function > >> instead of modifying the current one? > >> I think it does not need to be tied with the lockless implementation, > >> it is orthogonal to multi-threading implementation. > >> people using locks may still want this new deletion behavior. > >> If people want old behavior, they can call current API, otherwise > >> they can call the new deletion function, followed by > Rte_hash_free_key_with_position later. > >I like the terms 'delete' and 'free'. I am finding it hard to come up > >with a good name for the API. It will be on the lines of > 'rte_hash_del_key_with_hash_no_free' - I do not like the name much. > >Instead, we could have a configuration flag for the hash table, > >'RTE_HASH_EXTRA_FLAGS_FREE_MEM_ON_DEL'. If this is enabled, > 'rte_hash_del_...' APIs will free the key store index and any internal me= mory. > Enabling lock-free RW concurrency will enable this flag. > >User can enable this flag explicitly while not using lock-free RW concur= rency > as well. > [Wang, Yipeng] I am OK with either way. For flag, maybe we should call it > RTE_HASH_EXTRA_FLAGS_RECYCLE _ON_DEL, since The key-data pair index is > recycled to be more specific. User should know that the index might be re= - > used by another write. > BTW, current flag is only 8 bit, as we specify more and more flags, maybe= we > should announce an API change to change it to 32bit for next release. I agree. Do you know how to do this? Do you want to take care of this?