[ovs-dev] [PATCHv6 00/14] Revalidate flows with unique identifiers.

[Joe Stringer]

This series modifies the dpif interface for flow commands to use 128-bit unique
identifiers as an alternative to the netlink-formatted flow key, and caches the
mask/actions in the udpif_key. This significantly reduces the cost of
assembling messages between revalidators and the datapath, improving
revalidation performance by 40% or more. In a test environment of many
short-lived flows constantly being set up in the datapath, this increases the
number of flows that can be maintained in the linux datapath from around
130-140K up to 190-200K. For the userspace datapath, this decreases the time
spent revalidating 160K flows from 250ms to 150ms.

The core of the changes sits in the handler and revalidator code. Handlers take
responsibility for creating udpif_key cache entries which now include a copy of
the flow mask and actions. The key and mask are stored in 'struct match' format
rather than the current netlink format, which allows the memory footprint to be
the same or smaller for flows with simple actionsets.

Revalidators request datapaths to dump flows using only the unique identifier
and stats, and in cases where full revalidation is required, it will use the
udpif_key cache of the key/mask/acts to validate the flow. Revalidators will
detect datapath support for the UID feature, and omit flow keys from netlink
transactions if it is supported. For backwards compatibility, flow keys will
always be serialised if UID support is not detected in the datapath.

This series is also made available here to assist review:
https://github.com/joestringer/openvswitch/tree/submit/ufid_v6

v6:
- Address feedback from Ben
- Split out "dpif: Add Unique flow identifiers." into three patches
- Reduce netlink conversions for all datapaths
- Reduce udpif_key footprint
- Added x64 version of murmurhash3
- Added hash function tests
- Various bugfixes
- Rebase

v5:
- Rebase
- Various bugfixes
- Improve logging

v4:
- Datapath memory leak fixes
- Enable UID-based terse dumping and deleting by default
- Shifted UID generation down to dpif
- Log flow UIDs in more places
- Various fixes

RFCv3:
- Add datapath implementation
- Minor fixes
- Rebased

RFCv2:
- Revised early patches from v1 feedback
- Add Acks from Ben
- Rebased

RFCv1:
http://openvswitch.org/pipermail/dev/2014-August/044383.html


Joe Stringer (14):
  revalidator: Distinguish new and duplicate flows.
  revalidator: Use 'cmap' for storing ukeys.
  revalidator: Protect ukeys with a mutex.
  udpif: Separate udpif_key maps from revalidators.
  upcall: Rename dump_op -> ukey_op.
  upcall: Create ukeys in handler threads.
  upcall: Revalidate using cache of mask, actions.
  tests: Mention binomial coefficient in hash tests.
  hash: Add 128-bit murmurhash.
  dpif: Generate flow_hash for revalidators in dpif.
  datapath: Add support for unique flow identifiers.
  dpif: Index flows using unique identifiers.
  dpif: Minimize memory copy for revalidation.
  udpif: Simplify storage of key, mask in udpif_key.

 datapath/datapath.c                               |  215 ++++--
 datapath/flow.h                                   |   12 +-
 datapath/flow_netlink.c                           |   60 ++
 datapath/flow_netlink.h                           |    2 +
 datapath/flow_table.c                             |  230 +++++--
 datapath/flow_table.h                             |    5 +-
 datapath/linux/compat/include/linux/openvswitch.h |   29 +
 include/openvswitch/types.h                       |    7 +
 lib/dpctl.c                                       |   14 +-
 lib/dpif-netdev.c                                 |  152 +++--
 lib/dpif-netlink.c                                |  134 +++-
 lib/dpif-provider.h                               |    9 +-
 lib/dpif.c                                        |   56 +-
 lib/dpif.h                                        |   50 +-
 lib/hash.c                                        |  289 +++++++-
 lib/hash.h                                        |   15 +-
 lib/odp-util.c                                    |   54 ++
 lib/odp-util.h                                    |   25 +
 ofproto/netflow.c                                 |    3 +-
 ofproto/netflow.h                                 |    2 +-
 ofproto/ofproto-dpif-upcall.c                     |  755 +++++++++++++--------
 ofproto/ofproto-dpif.c                            |  100 ++-
 ofproto/ofproto-dpif.h                            |    3 +
 tests/dpif-netdev.at                              |    5 +
 tests/ofproto-dpif.at                             |   28 +-
 tests/ofproto-macros.at                           |    1 +
 tests/test-hash.c                                 |   88 ++-
 27 files changed, 1823 insertions(+), 520 deletions(-)

-- 
1.7.10.4