From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from EUR02-AM5-obe.outbound.protection.outlook.com (mail-eopbgr00071.outbound.protection.outlook.com [40.107.0.71]) by dpdk.org (Postfix) with ESMTP id 0B59D239 for ; Mon, 1 Oct 2018 06:11:29 +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=4V/fAMaVmZBMeynF+TM1GAYaZFQUpuy7hsCP3ItTWq4=; b=BznL8A/6ToDNH6ChcK2bpRm7AXMBEQIkJO9cJSVezxJDz9xtFd2qpkY6ZHEd3HD4wLpoxosBMlZL7Q/Tmgn58iUJZge5si38PatJ9UqjSTUWx0PHTZHMAdNQULEGXOcViFd4J4WfrZX1zfaS4lEcYS5UCf7pL1D2oSvQpqgo7eU= Received: from AM6PR08MB3672.eurprd08.prod.outlook.com (20.177.115.29) by AM6PR08MB3335.eurprd08.prod.outlook.com (52.135.165.16) with Microsoft SMTP Server (version=TLS1_2, cipher=TLS_ECDHE_RSA_WITH_AES_256_GCM_SHA384) id 15.20.1185.20; Mon, 1 Oct 2018 04:11:28 +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; Mon, 1 Oct 2018 04:11:28 +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: AQHUWTzTzwGE8jRjuEmdunM9Uo3m7A== Date: Mon, 1 Oct 2018 04:11:28 +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: 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; AM6PR08MB3335; 6:qXtHcP7rVO3mrPbLKQwrMPhq3KsdVaOp5hWu7Gtpvq5pW1P9In1DcK0visjnH/vEhKIoEoUIPxCoyeGx2Q5eES3f1WKHQr+HRPWnrdDjk/JFVNpUSZmmQAlAY2UvkB3xWDr98Bm2ROIjtsTrlI+nn7mLZchjaJw/T7wKgtLS72YprXbYN1DqBVP7UbaJ91hWaMtLXoGRfEMtuXKbiZV8X1BzVKxtpA6MDJAS6ZOXdQgBC114V1JRZDMDm+BnAUnAbEBWuLhvFeQ7Fm5C3dNmSv58CL7UzAg2Yi48iu0voaHX8iPUzZ8DBdvcSRIua+At4ukw3LAwxIjR11HhCYKB+FW8ym2itlrHqi3aqc7aWRmAciy5us3qwPS9EnD0PtfMel8Gv0qcxe0ASVvxtVzRHrSCVb+eZ1PbUmjJp/e1qwOkaUSOlJDEK+Rg9ukHzaq1WbHHSPaNs/sYPgwcN0bh5g==; 5:p7OGHWf/zRiEIIS175oxJIXnOXiM149NZT7zTzwaNx54dwno1BFaEsFLqQEV2tiDQ476z3UI7Ff4DAVb266dXhXZQfzf9u+4S+G6op2/kNVgUZvjj1QZHHxEF5WIy6ZUh7/eRALrrrvvFXF8iXMIyWBFUTkjdIIoSCBUm6Obcu0=; 7:3FUbCK1V2kHOsokH6VjQoNuPWachznetjnlezmBbDJOHXzNQtcsk1/5Q0+3vMbHDnP5jg5Pp8kQY/LbKGEhmQa+jELStNafaUd/R3u0Zo35yp2vfkIHb18hfkkfjcorJC6LJDvwto+4Ypk3jsw93/d4yCqoDv3N9ib2UcV/qjHH2Apad5vrDaybbiROy482saQ3HVnuSX8jawNr/GS9t55TRMStHuUj1FtieS7kJb5FKcfR3x5eghocOCptnMR5T x-ms-exchange-antispam-srfa-diagnostics: SOS;SOR; x-ms-office365-filtering-correlation-id: 1e733d85-ff1a-4f42-753c-08d62753f655 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:AM6PR08MB3335; x-ms-traffictypediagnostic: AM6PR08MB3335: 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)(3231355)(944501410)(52105095)(10201501046)(93006095)(93001095)(6055026)(149066)(150057)(6041310)(20161123560045)(201703131423095)(201702281528075)(20161123555045)(201703061421075)(201703061406153)(20161123564045)(20161123562045)(20161123558120)(201708071742011)(7699051); SRVR:AM6PR08MB3335; BCL:0; PCL:0; RULEID:; SRVR:AM6PR08MB3335; x-forefront-prvs: 0812095267 x-forefront-antispam-report: SFV:NSPM; SFS:(10009020)(346002)(366004)(396003)(376002)(39850400004)(136003)(189003)(199004)(9686003)(53936002)(486006)(34290500001)(478600001)(11346002)(71190400001)(71200400001)(74316002)(446003)(229853002)(72206003)(4326008)(7696005)(106356001)(25786009)(476003)(186003)(6116002)(3846002)(76176011)(26005)(6436002)(305945005)(7736002)(81166006)(81156014)(14444005)(6506007)(316002)(5660300001)(14454004)(97736004)(33656002)(54906003)(110136005)(8936002)(86362001)(102836004)(66066001)(105586002)(68736007)(5250100002)(55016002)(6246003)(256004)(99286004)(2906002)(2900100001)(21314002); DIR:OUT; SFP:1101; SCL:1; SRVR:AM6PR08MB3335; 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: Hq9aRl/6oyjZQwfCgKTpgriD90r4+oq20K5zAHnUDt8Y/plKiORfJ2HF9gz/glwbA+fwoiN/coqha1ihdg2rcd67o043qDyejw/njM1H7hZg9ip5TTgGqL+yMPkoFy1ey1+SfE1DFn+dn2MTyh/5KaM8G8b3OkKsUSVGJwgA9rJXnsJZSJWsHIWpHSq9ptVGOsx88fzlBJrHDzDR+75Ul7yHIQW3795l00ronqUPTgJrWvraWjCado9c841Iymc8+R3SP4pIACfGEYMQ6nFKREMCvIzmP96Dq98bd4ICm8UIdp/ZF2T3eyPFfLnk02QIHdEd+uuS/43O0zqsuZ5SG9CP/N95haQ/SkBufIfwdGI= 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: 1e733d85-ff1a-4f42-753c-08d62753f655 X-MS-Exchange-CrossTenant-originalarrivaltime: 01 Oct 2018 04:11:28.6974 (UTC) X-MS-Exchange-CrossTenant-fromentityheader: Hosted X-MS-Exchange-CrossTenant-id: f34e5979-57d9-4aaa-ad4d-b122a662184d X-MS-Exchange-Transport-CrossTenantHeadersStamped: AM6PR08MB3335 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: Mon, 01 Oct 2018 04:11:30 -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 implementat= ion > works for single writer multiple readers. Multi-writers are supported by using the rw-lock or transactional memory. E= ssentially, we still have single writer. This patch works fine with multi-w= riter as defined by ' MULTI_WRITER_ADD' flag. I have tested it as well. I w= ill enable this test case in V2. > Also, if people use a mix of the flags for example set both multiwriter a= nd LF > flags, then I guess either we need to return an error or maybe multiwrite= r > 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_C= ONCURRENCY currently assumes MULTI_WRITER_ADD. I think we should separate t= hem. > >+ > > /** 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 ex= isting > 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. >=20 > > * > > * @param h > > * Hash table to add the key to. > >@@ -165,6 +175,11 @@ rte_hash_add_key_data(struct rte_hash *h, const > >void *key, void *data); > > * 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'. > > * > > * @param h > > * Hash table to add the key to. > >@@ -230,6 +245,12 @@ rte_hash_add_key_with_hash(struct rte_hash *h, > >const void *key, hash_sig_t sig); > > * 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. > >@@ -241,6 +262,8 @@ rte_hash_add_key_with_hash(struct rte_hash *h, > const void *key, hash_sig_t sig); > > * - A positive value that can be used by the caller as an offset int= o an > > * array of user data. This value is unique for this key, and is th= e same > > * value that was returned when the key was added. > >+ * When lock free concurrency is enabled, this value should be used > >+ * while calling the rte_hash_free_key_with_position API. > > */ > > int32_t > > 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 int= o an > > * array of user data. This value is unique for this key, and is th= e same > > * value that was returned when the key was added. > >+ * When lock free concurrency is enabled, this value should be used > >+ * 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 instea= d 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 ca= n call > the new deletion function, followed by Rte_hash_free_key_with_position la= ter. 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_E= XTRA_FLAGS_FREE_MEM_ON_DEL'. If this is enabled, 'rte_hash_del_...' APIs wi= ll free the key store index and any internal memory. Enabling lock-free RW = concurrency will enable this flag. User can enable this flag explicitly whi= le not using lock-free RW concurrency as well.