[ovs-dev] [PATCH 0/3] 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 then traversed to find if certain sub-tables can be
   skipped.  If the longest matching prefix on the packet's address
   is, e.g., /16, then 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.

Both these techniques stem from ideas by Ethan, but I'm responsible
for the bugs most likely luring in there.  A thorough review would
be welcome.

The third patch implements on-demand trie lookup, which delays the
trie lookup until the field(s) in question become relevant.  This
adds some complexity and I was not able to find significant
performance difference, so this one should be considered as an item
for further discussion.

Jarno Rajahalme (3):
  Classifier: Staged sub-table matching.
  Classifier: Track IP addresses for more wildcarding.
  Classifier: On-demand prefix tree lookup.

 lib/classifier.c             |  759 ++++++++++++++++++++++++++++++++++++++++--
 lib/classifier.h             |   25 +-
 lib/flow.c                   |  175 +++++++++-
 lib/flow.h                   |   82 +++--
 lib/match.c                  |    2 +-
 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.h                   |   13 +
 ofproto/ofproto-dpif-xlate.c |    2 +-
 ofproto/ofproto-dpif.c       |    2 +-
 ofproto/ofproto.c            |    2 +-
 tests/classifier.at          |   38 +++
 tests/ofproto-dpif.at        |    4 +-
 tests/test-classifier.c      |   12 +-
 utilities/ovs-ofctl.c        |    4 +-
 18 files changed, 1116 insertions(+), 70 deletions(-)

-- 
1.7.10.4