[ovs-dev] [PATCHv8 00/11] 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. Revalidators request datapaths to dump flows using
only the unique identifier and stats, rather than the full set of
netlink-formatted flow key, mask and actions.

In cases where full revalidation is required, revalidators will use the
udpif_key cache of the key/mask/acts to validate the flow. The dpif will
detect datapath support for the unique identifer "UFID" feature, and omit flow
keys from netlink transactions if it is supported. For backwards compatibility,
flow keys will always be serialised if UFID 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_v8

v8:
- Rename UID -> UFID
- Clarify dpif interface descriptions
- Remove 'struct odputil_uidbuf'
- Simplify dpif-netlink UFID marshalling
- 32-bit build fix
- Fix null dereference in datapath when paired with older userspace
- Don't generate UFIDs for feature probes or ovs-dpctl usage
- Rebase
- All patches are reviewed/acked except datapath changes.

v7:
- Remove OVS_DP_F_INDEX_BY_UID
- Rework datapath UID serialization for variable length UIDs
- Create ukeys from revalidator threads in corner cases
- Hide "terse" flags from flow_get,flow_del dpif interface
- Scattered replacements of memcpy with u128_equal()
- Rebase

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

Joe Stringer (11):
  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.
  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.

 datapath/datapath.c                               |  238 ++++--
 datapath/flow.h                                   |   13 +-
 datapath/flow_netlink.c                           |   42 +
 datapath/flow_netlink.h                           |    1 +
 datapath/flow_table.c                             |  230 +++++-
 datapath/flow_table.h                             |    3 +
 datapath/linux/compat/include/linux/openvswitch.h |   25 +
 include/openvswitch/types.h                       |   14 +
 lib/dpctl.c                                       |    8 +-
 lib/dpif-netdev.c                                 |  192 +++--
 lib/dpif-netlink.c                                |  256 ++++++-
 lib/dpif-provider.h                               |   13 +-
 lib/dpif.c                                        |   65 +-
 lib/dpif.h                                        |   46 +-
 lib/hash.c                                        |  266 ++++++-
 lib/hash.h                                        |   11 +-
 lib/odp-util.c                                    |   59 ++
 lib/odp-util.h                                    |    4 +
 ofproto/ofproto-dpif-upcall.c                     |  843 +++++++++++++++------
 ofproto/ofproto-dpif.c                            |   12 +-
 tests/dpif-netdev.at                              |    5 +
 tests/ofproto-dpif.at                             |   28 +-
 tests/ofproto-macros.at                           |    1 +
 tests/test-hash.c                                 |   83 ++
 24 files changed, 1944 insertions(+), 514 deletions(-)

-- 
1.7.10.4