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