> -----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.
