From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from mga09.intel.com (mga09.intel.com [134.134.136.24]) by dpdk.org (Postfix) with ESMTP id 1FEFE11C5 for ; Thu, 2 Jul 2015 13:20:46 +0200 (CEST) Received: from orsmga003.jf.intel.com ([10.7.209.27]) by orsmga102.jf.intel.com with ESMTP; 02 Jul 2015 04:20:47 -0700 X-ExtLoop1: 1 X-IronPort-AV: E=Sophos;i="5.15,392,1432623600"; d="scan'208";a="598844226" Received: from irsmsx105.ger.corp.intel.com ([163.33.3.28]) by orsmga003.jf.intel.com with ESMTP; 02 Jul 2015 04:20:45 -0700 Received: from irsmsx108.ger.corp.intel.com ([169.254.11.201]) by irsmsx105.ger.corp.intel.com ([169.254.7.245]) with mapi id 14.03.0224.002; Thu, 2 Jul 2015 12:20:44 +0100 From: "Dumitrescu, Cristian" To: "Richardson, Bruce" , "Abdul, Jaffar" Thread-Topic: [dpdk-dev] DPDK Hash library Thread-Index: AQHQtKqeW2uxAEWFK06W+N13NaqHSp3IBaHg Date: Thu, 2 Jul 2015 11:20:44 +0000 Message-ID: <3EB4FA525960D640B5BDFFD6A3D89126323949C2@IRSMSX108.ger.corp.intel.com> References: <23903483D1A9B04AB5D759C6C845237F042C1A2EA7@ONWVEXCHMB05.ciena.com> <20150702093611.GB7688@bricha3-MOBL3> In-Reply-To: <20150702093611.GB7688@bricha3-MOBL3> Accept-Language: en-US Content-Language: en-US X-MS-Has-Attach: X-MS-TNEF-Correlator: x-originating-ip: [163.33.239.182] Content-Type: text/plain; charset="us-ascii" Content-Transfer-Encoding: quoted-printable MIME-Version: 1.0 Cc: "dev@dpdk.org" Subject: Re: [dpdk-dev] DPDK Hash library X-BeenThere: dev@dpdk.org X-Mailman-Version: 2.1.15 Precedence: list List-Id: patches and discussions about DPDK List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Thu, 02 Jul 2015 11:20:47 -0000 > -----Original Message----- > From: dev [mailto:dev-bounces@dpdk.org] On Behalf Of Bruce Richardson > Sent: Thursday, July 2, 2015 10:36 AM > To: Abdul, Jaffar > Cc: dev@dpdk.org > Subject: Re: [dpdk-dev] DPDK Hash library >=20 > On Wed, Jul 01, 2015 at 07:56:28PM -0400, Abdul, Jaffar wrote: > > Hi, > > > > I am wondering how can I use the hash library if I don't know the numbe= r > of entries in the bucket (number of entries in the bucket can grow > dynamically) > > I am trying to use the DPDK hash library for MAC table where I can't gi= ve > the fixed number of elements in each bucket. >=20 > The current DPDK hash library does not support this, unfortunately. There= is > currently an effort underway to do a cuckoo hash implementation for DPDK > (patches > already on-list), to allow items to move between buckets rather than just > failing > if a bucket is full. Please feel free to try out these patches and provid= e > feedback > on them if you can! >=20 > /Bruce > > To achieve this, you can also use the extendible bucket hash tables provide= d by librte_table. API is in lib/librte_table/rte_table_hash.h: 1. rte_table_hash_ext =3D Extendible bucket hash table accepting any key si= ze 2. rte_table_hash_key8_ext =3D Extendible bucket hash table accepting only = a key size of 8 bytes (optimized for 8-byte keys) 3. rte_table_hash_key16_ext =3D Extendible bucket hash table accepting only= a key size of 16 bytes (optimized for 16-byte keys) Extendible bucket means that each bucket starts with table space for only 4= keys; whenever a new key needs to be added to a bucket that already has 4 = keys, the bucket gets extended with space for 4 more keys, so basically the= bucket size goes up and down as keys are added or removed from a bucket. The tables in librte_table can be used standalone or in correlation with th= e pipeline construction provided by librte_pipeline. For more details on th= ese hash table, please look into DPDK Programmer's Guide, chapter Packet Fr= amework, section 24.4.3 Hash Table Design.