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
_______________________________________________
dev mailing list
dev@openvswitch.org
http://openvswitch.org/mailman/listinfo/dev
