datapath: Use hash table more tolerant of collisions for flow table.
authorBen Pfaff <blp@nicira.com>
Tue, 1 Sep 2009 17:31:32 +0000 (10:31 -0700)
committerBen Pfaff <blp@nicira.com>
Tue, 1 Sep 2009 17:36:42 +0000 (10:36 -0700)
commit6fa58f7a1533b96d8c958581ed18e0e5a245157b
tree2b2a3ee3bf08ea3bd17dd8f86924cc68a27f5150
parent3c4fae5f4563848dd6392434424e10e32e6b6f83
datapath: Use hash table more tolerant of collisions for flow table.

The hash table used until now in the kernel datapath for storing the flow
table provides only two slots that a given flow can occupy.  If both of
those slots are already full, for a given flow, then that flow cannot be
added at all and its packets must be handled entirely in userspace, taking
a performance hit.  The code does attempt to compensate for this by making
the flow table rather large: 8 slots per flow actually in the flow table.
In practice, this is usually good enough, but some of the tests that we
have run show bad enough performance degradation or even timeouts of
various kinds that we want to implement something better.

This commit replaces the existing hash table by one with a completely
different design in which buckets are flexibly sized and can accept any
number of collisions.  By use of suitable levels of indirection, this
design is both simple and RCU-compatible.  I did consider other schemes,
but none of the ones that I came up with shared both of those two
properties.

This commit also adds kerneldoc comments for all of the flow table
non-static functions and data structures.

This has been lightly tested for correctness.  It has not been tested for
performance.

Bug #1656.  Bug #1851.
datapath/datapath.c
datapath/datapath.h
datapath/table.c