[dpdk-dev] [PATCH 2/6] hash: replace existing hash library with cuckoo hash implementation

Bruce Richardson bruce.richardson at intel.com
Wed Jun 17 17:31:35 CEST 2015


On Fri, Jun 05, 2015 at 03:33:20PM +0100, Pablo de Lara wrote:
> This patch replaces the existing hash library with another approach,
> using the Cuckoo Hash method to resolve collisions (open addressing),
> which pushes items from a full bucket when a new entry tries
> to be added in it, storing the evicted entry in an alternative location,
> using a secondary hash function.
> 
> This gives the user the ability to store more entries when a bucket
> is full, in comparison with the previous implementation.
> Therefore, the unit test has been updated, as some scenarios have changed
> (such as the previous removed restriction).
> 
> Also note that the API has not been changed, although new fields
> have been added in the rte_hash structure.
> The main change when creating a new table is that the number of entries
> per bucket is fixed now, so its parameter is ignored now
> (still there to maintain the same parameters structure).
> 
> As a last note, the maximum burst size in lookup_burst function
> hash been increased to 64, to improve performance.
> 
> Signed-off-by: Pablo de Lara <pablo.de.lara.guarch at intel.com>

I'm getting compile errors with icc and clang with this patch. Something to
fix in your V2.

/home/bruce/dpdk.org/app/test/test_hash.c:567:2: fatal error: array index 5 is past the end of the array (which contains 5 elements) [-Warray-bounds]
        expected_pos[5] = pos[5];
        ^            ~
/home/bruce/dpdk.org/app/test/test_hash.c:548:2: note: array 'expected_pos' declared here
        int expected_pos[5];
        ^
1 error generated.

Further review comments to follow.

/Bruce



More information about the dev mailing list