[ovs-dev] [PATCH v2 0/9] Classifier: Better wildcarding

[Jarno Rajahalme]

This series implements two techniques for better wildcarding:

1. Staged sub-table matching: Each sub-table is matched in segments,
   starting from metadata and lower protocol layer fields, progressing
   towards higher layers only as needed.  That is, if we can determine
   that there is no match on a specific segment, the higher layer
   fields need not be looked at, and hence will not need to be
   unwildcarded.

2. Prefix tree (trie) lookup for IP address fields: Classifier
   maintains a tree representation of the used address space.  The
   tree is traversed to find if certain sub-tables can be skipped.  If
   the longest matching prefix on the packet's address is, e.g., /16,
   the rest of the address field need not be unwildcarded in most
   cases.  However, if there are flow entries with more specific
   addresses, enough bits need to be unwildcarded to ensure that
   future packets that should match the more specific entries do not
   match the kernel flow being created due to the current packet.

   The prefixes used for trie lookup are configurable via the OVSDB
   "Flow_Table" table.

The last patch implements on-demand trie lookup, which delays the trie
lookup until the field(s) in question become relevant.  This adds some
complexity and may be of significance when flow tables match on large
number of addresses.

v2:
  - Address Ben's comments.
  - Adds minimatch_matches_flow_likely() which improves performance
    slightly.
  - Adds 64-bit mapping, which enables nice cleanup.
  - Adds a clz() implementation in lib/util.c.
  - Adds "fieldspec" for configuring prefix lookup.

Jarno Rajahalme (9):
  lib/util: Make raw_ctz() implementation non-static.
  lib/util: Add ctz64() and popcount64().
  miniflow: Use 64-bit map.
  Classifier: Add minimatch_matches_flow_likely()
  Classifier: Staged sub-table matching.
  lib/util: Add clz() and clz64().
  Classifier: Track IP addresses for more wildcarding.
  schema: Add "fieldspec" to table "Flow_Table".
  Classifier: On-demand prefix tree lookup.

 lib/classifier.c             |  803 ++++++++++++++++++++++++++++++++++++++++--
 lib/classifier.h             |   30 +-
 lib/dpif-netdev.c            |    2 +-
 lib/flow.c                   |  305 ++++++++--------
 lib/flow.h                   |  104 ++++--
 lib/match.c                  |   62 +++-
 lib/match.h                  |    4 +
 lib/meta-flow.c              |   56 +++
 lib/meta-flow.h              |    4 +
 lib/nx-match.c               |    2 +-
 lib/ofp-util.c               |    2 +-
 lib/ofp-util.h               |    2 +-
 lib/util.c                   |   27 +-
 lib/util.h                   |   86 ++++-
 ofproto/ofproto-dpif-xlate.c |    2 +-
 ofproto/ofproto-dpif.c       |    2 +-
 ofproto/ofproto.c            |    8 +-
 ofproto/ofproto.h            |    8 +
 tests/classifier.at          |   39 ++
 tests/library.at             |    1 +
 tests/ofproto-dpif.at        |    6 +-
 tests/test-classifier.c      |   29 +-
 tests/test-util.c            |  120 ++++++-
 utilities/ovs-ofctl.c        |    4 +-
 vswitchd/bridge.c            |   60 ++++
 vswitchd/vswitch.ovsschema   |    9 +-
 26 files changed, 1534 insertions(+), 243 deletions(-)

-- 
1.7.10.4