From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from EUR02-HE1-obe.outbound.protection.outlook.com (mail-eopbgr10086.outbound.protection.outlook.com [40.107.1.86]) by dpdk.org (Postfix) with ESMTP id 893D52952 for ; Wed, 3 Oct 2018 06:37:16 +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=124wDIzeFmK6rQERYKnDKu7oEhm7bWCSPGhVnxAWJyY=; b=Qx3WzQNKx0Z7Y9Q4GzbUT2L89OhV/Ml1UMoL7ZSvtruTMapS7X38RKR+Ln3Hen4+2UF/ngF27rZ3F4IL5hAPKXv3XDpnwhjruHjN4di32bNUcWLFrf8AWKcqtKFAD3ymZSX7eP7C8K5ZEjRwiPe7XkubOOkazU+mo8yuH4emFVA= Received: from AM6PR08MB3672.eurprd08.prod.outlook.com (20.177.115.29) by AM6PR08MB3591.eurprd08.prod.outlook.com (20.177.114.224) with Microsoft SMTP Server (version=TLS1_2, cipher=TLS_ECDHE_RSA_WITH_AES_256_GCM_SHA384) id 15.20.1207.21; Wed, 3 Oct 2018 04:37:15 +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.026; Wed, 3 Oct 2018 04:37:14 +0000 From: Honnappa Nagarahalli To: "Wang, Yipeng1" , "Richardson, Bruce" CC: "Ananyev, Konstantin" , "dev@dpdk.org" , "Gobriel, Sameh" , nd Thread-Topic: [PATCH v4 2/4] hash: add extendable bucket feature Thread-Index: AQHUV4tn5zytEct7aE6GLUXLgUt5Y6UK4rDwgAG+fjCAAFMb8A== Date: Wed, 3 Oct 2018 04:37:14 +0000 Message-ID: References: <1537993618-92630-1-git-send-email-yipeng1.wang@intel.com> <1538155426-145177-1-git-send-email-yipeng1.wang@intel.com> <1538155426-145177-3-git-send-email-yipeng1.wang@intel.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; AM6PR08MB3591; 6:/yi+56LqwODqbY0ljkDqxTlMGiUrmnoPyD8FRqDXMdjz4W4QCIiOjbKJpl7gghjZxY009Nijrwz7+VfuRZsyDqLfVSAclWXdDCGFzgeDvZNTfmU7cVcdZGCwcTR7jFQ22h+oxrgqhq5lHL4cNOG2RwagXy/hEkcwKLxS4s6sNWRsQvFYirTnzrMjJdnlXcxYs7Fwh00LvuZyo3V+qH2EyOGBcP7ezEp3CjdlukRWucy+DTDglrNiwAKiZtQ4xEGcPDxqRK+koAMD954qAUa9A8Tc0ohdlKBuZurJ2zxEXCZk6pBYLOAbw8i3Odk+vGnlbYFnqCfIwMM0nAFjDLS7nyJMWbhQmdznfB42NmmSvh++jzB9kMB45os7apw6gQRHMOEGEl/f5mqSdbbGzbcJ/ksA7L4RoVKyqLpVAXszr1+1i/OQiDWDJ2bjJFq35JHM/9eSHQZK4T7VX4496qy9eQ==; 5:M+hxFX3ZXOsZ2NVRECI+180SKtTLN5yiX3OyRRNDNXt6vRiC8ATKgtTuSuCx2+Ta5zrFGkBivwlnmBfyw0uKAcFVFsFLsv2TUmCLP+qk/Jok2UFLH4VbF+0W9T0yS7n7DEb01HmTQNE61OSFfcnr58/OUFN4rIuEc6HQQlqtoP4=; 7:2jIYm8zby3aiV2FuqFtjSuElS8GyUanoFC+GL65NNb5L29GjnNihpki8/6l8qPkn6qR8ZVzCREhXDph4KeNE/XUY0pjrHgMzAv/Kvir2C+fnBxiNVi91BLnTLIJTA4k0FQe+9qbDD858fJwB22JlBINuOEYsYcRWb2kPWT8I0nH/qOSr/wVi3oXUZ+kH7k8wrGQxTOYvto/DCwQHhqdARbtPflWgtupfEEq6iVTnjnOnB5IeltcnUvSMzYFiZRhg x-ms-exchange-antispam-srfa-diagnostics: SOS; x-ms-office365-filtering-correlation-id: e865c7be-16cf-4072-d3d5-08d628e9e4bc 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:AM6PR08MB3591; x-ms-traffictypediagnostic: AM6PR08MB3591: 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)(3231355)(944501410)(52105095)(93006095)(93001095)(3002001)(10201501046)(6055026)(149066)(150057)(6041310)(20161123562045)(201703131423095)(201702281528075)(20161123555045)(201703061421075)(201703061406153)(20161123564045)(20161123558120)(20161123560045)(201708071742011)(7699051); SRVR:AM6PR08MB3591; BCL:0; PCL:0; RULEID:; SRVR:AM6PR08MB3591; x-forefront-prvs: 0814A2C7A3 x-forefront-antispam-report: SFV:NSPM; SFS:(10009020)(396003)(376002)(366004)(39860400002)(136003)(346002)(189003)(199004)(68736007)(33656002)(25786009)(14454004)(476003)(446003)(11346002)(86362001)(6246003)(53936002)(6506007)(26005)(186003)(106356001)(105586002)(102836004)(256004)(14444005)(486006)(66066001)(2900100001)(72206003)(478600001)(71190400001)(81166006)(81156014)(305945005)(229853002)(54906003)(8936002)(97736004)(8676002)(4326008)(71200400001)(3846002)(5250100002)(6116002)(2906002)(316002)(5660300001)(9686003)(99286004)(6436002)(55016002)(93886005)(76176011)(7736002)(110136005)(74316002)(7696005); DIR:OUT; SFP:1101; SCL:1; SRVR:AM6PR08MB3591; 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: gNmwdFmVt/WgZENzSnWg2fv0/S5ti+uHzDWlYSn3go4nDU7RkTJfc8SVbVMEXHjG0Xb347Rm58mH4cZ9bt2rqJhyCgbAwlRrAKfTcgIiSU1rIe11LIcOMT8YTZUDea6LuZQ2qGXsOLE1e0lIdPzdlt1At9ZIv5osFxB/BgyoH2kI5whhHUPu1oOPyD0VFqoQ3ItvdVp5pttfKXBhg1lYZ77Y6cVvhsf8zsK9/38COP0QF2oPNHc2fk17HvWZlrMRj/po2mP5nTP/vSI4W+3TC+MSXhN+n29ZZQ+sfrbELOa41Q+iPIN3GU6l8aH9zDg2keNcWCgtH7QjRNjjmZ99rt3Q+GijIRLpfNpXrpMzW7o= 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: e865c7be-16cf-4072-d3d5-08d628e9e4bc X-MS-Exchange-CrossTenant-originalarrivaltime: 03 Oct 2018 04:37:14.8481 (UTC) X-MS-Exchange-CrossTenant-fromentityheader: Hosted X-MS-Exchange-CrossTenant-id: f34e5979-57d9-4aaa-ad4d-b122a662184d X-MS-Exchange-Transport-CrossTenantHeadersStamped: AM6PR08MB3591 Subject: Re: [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 List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Wed, 03 Oct 2018 04:37:16 -0000 > >> + while (last_bkt->next) { > >> + prev_bkt =3D last_bkt; > >> + last_bkt =3D last_bkt->next; > >> + } > >Minor: We are trying to find the last bucket here, along with its previo= us. > May be we can modify 'rte_hash_get_last_bkt' instead? > > > [Wang, Yipeng] Then there will be one more store in each iteration for th= e > regular find_last. I was having an individual function for this but since= it is > only used here I removed that. If you think it is necessary or you may re= use it > somewhere else for LF, I can add it back. I am fine with the existing code. > >> + > >> + for (i =3D 0; i < RTE_HASH_BUCKET_ENTRIES; i++) { > >> + if (last_bkt->key_idx[i] !=3D EMPTY_SLOT) > >> + break; > >> + } > >> + /* found empty bucket and recycle */ > >> + if (i =3D=3D RTE_HASH_BUCKET_ENTRIES) { > >> + prev_bkt->next =3D last_bkt->next =3D NULL; > >> + uint32_t index =3D last_bkt - h->buckets_ext + 1; > >> + rte_ring_sp_enqueue(h->free_ext_bkts, (void > >> *)(uintptr_t)index); > >In the lock-less algorithm, the bucket cannot be freed immediately. I > >looked at couple of solutions. The bucket needs to be stored internally = and > should be associated with the key-store index (or position). I am thinkin= g that I > will add a field to 'struct rte_hash_key' > >to store the bucket pointer or index. > [Wang, Yipeng] Even if the bucket is recycled immediately, what's the wor= st > could happen? Even if there are readers currently iterating the deleted B= ucket, > it is still fine right? It is a miss anyway. Good question. Logically, freeing the bucket is similar to freeing memory. = I think the worst that can happen is, readers will continue looking up a bu= cket (and any additional linked buckets), that they do not have to. But, I = do not see any illegal memory accesses. I will have a better answer once I = get code this. > > > >From the code, my understanding is that we will free only the last > >bucket. We will never free the middle bucket, please correct me if I am > wrong. This will keep it simple for the lock-free algorithm. > [Wang, Yipeng] It is correct. > > > >I could work through these issues. So, I do not see any issues for lock-= free > algorithm (as of now :) ). > > > >> + > >> + /* Out of bounds of all buckets (both main table and ext table */ > >Typo: missing ')' > > > [Wang, Yipeng] Yeah thanks! >=20 Apologies :)