[dpdk-dev] DPDK Hash library

[Dumitrescu, Cristian]

> -----Original Message-----
> From: dev [mailto:dev-bounces at dpdk.org] On Behalf Of Bruce Richardson
> Sent: Thursday, July 2, 2015 10:36 AM
> To: Abdul, Jaffar
> Cc: dev at dpdk.org
> Subject: Re: [dpdk-dev] DPDK Hash library
> 
> 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 number
> 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 give
> the fixed number of elements in each bucket.
> 
> 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 provide
> feedback
> on them if you can!
> 
> 	/Bruce
> >

To achieve this, you can also use the extendible bucket hash tables provided by librte_table.

API is in lib/librte_table/rte_table_hash.h:
1. rte_table_hash_ext = Extendible bucket hash table accepting any key size
2. rte_table_hash_key8_ext = Extendible bucket hash table accepting only a key size of 8 bytes (optimized for 8-byte keys)
3. rte_table_hash_key16_ext = 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 the pipeline construction provided by librte_pipeline. For more details on these hash table, please look into DPDK Programmer's Guide, chapter Packet Framework, section 24.4.3 Hash Table Design.