[ovs-dev] [PATCH v2 2/2] lib/classifier: Optimize megaflows for single rule case.
Jarno Rajahalme
jrajahalme at nicira.com
Tue Jun 3 19:58:00 UTC 2014
On May 22, 2014, at 10:43 AM, Ben Pfaff <blp at nicira.com> wrote:
> I find myself wondering whether we could end up with a funny
> paradoxical mask, e.g. mark some bit of a TCP port as looked at even
> though we didn't mark the IP protocol as looked at. I am not sure
> whether this can happen or whether this is a problem. Actually,
> looking further, I guess it can't happen because we always unwildcard
> all the fields up to the current stage when we jump to range_out. In
> fact, I think that range_out wildcards the current stage, too: is that
> defeating the intended optimization here? (I see that you updated the
> tests so presumably not?)
Coming back to an old comment here… So, what we could do instead is to fill in the mask bits as we successfully compare, and fill in one bit of the differing uint32_t. This would get rid of another scan through the map in both outcomes, so it would be faster and simpler, and would take care of the prerequisites independent of the chosen boundaries of the lookup ranges (as long as the difference and the prerequisite are not in the same uint32_t, which is not the case for any field in struct flow).
This would be the incremental, what do you think:
diff --git a/lib/classifier.c b/lib/classifier.c
index b5416c6..2d47310 100644
--- a/lib/classifier.c
+++ b/lib/classifier.c
@@ -1385,8 +1385,7 @@ check_tries(struct trie_ctx trie_ctx[CLS_MAX_TRIES], unsigned int n_tries,
static inline bool
miniflow_and_mask_matches_flow(const struct miniflow *flow,
const struct minimask *mask,
- const struct flow *target,
- struct flow_wildcards *wc)
+ const struct flow *target)
{
const uint32_t *flowp = miniflow_get_u32_values(flow);
const uint32_t *maskp = miniflow_get_u32_values(&mask->masks);
@@ -1396,12 +1395,6 @@ miniflow_and_mask_matches_flow(const struct miniflow *flow,
uint32_t diff = (*flowp++ ^ FLOW_U32_VALUE(target, idx)) & *maskp++;
if (diff) {
- /* Only unwildcard if none of the differing bits is already
- * exact-matched. */
- if (wc && !(FLOW_U32_VALUE(&wc->masks, idx) & diff)) {
- /* Keep one bit of the difference. */
- FLOW_U32_VALUE(&wc->masks, idx) |= rightmost_1bit(diff);
- }
return false;
}
}
@@ -1417,7 +1410,7 @@ find_match(const struct cls_subtable *subtable, const struct flow *flow,
HMAP_FOR_EACH_WITH_HASH (rule, hmap_node, hash, &subtable->rules) {
if (miniflow_and_mask_matches_flow(&rule->flow, &subtable->mask,
- flow, NULL)) {
+ flow)) {
return rule;
}
}
@@ -1425,6 +1418,42 @@ find_match(const struct cls_subtable *subtable, const struct flow *flow,
return NULL;
}
+/* Returns true if 'target' satisifies 'flow'/'mask', that is, if each bit
+ * for which 'flow', for which 'mask' has a bit set, specifies a particular
+ * value has the correct value in 'target'.
+ *
+ * This function is equivalent to miniflow_and_mask_matches_flow() but this
+ * version fills in the mask bits in 'wc'. */
+static inline bool
+miniflow_and_mask_matches_flow_wc(const struct miniflow *flow,
+ const struct minimask *mask,
+ const struct flow *target,
+ struct flow_wildcards *wc)
+{
+ const uint32_t *flowp = miniflow_get_u32_values(flow);
+ const uint32_t *maskp = miniflow_get_u32_values(&mask->masks);
+ uint32_t idx;
+
+ MAP_FOR_EACH_INDEX(idx, mask->masks.map) {
+ uint32_t mask = *maskp++;
+ uint32_t diff = (*flowp++ ^ FLOW_U32_VALUE(target, idx)) & mask;
+
+ if (diff) {
+ /* Only unwildcard if none of the differing bits is already
+ * exact-matched. */
+ if (!(FLOW_U32_VALUE(&wc->masks, idx) & diff)) {
+ /* Keep one bit of the difference. */
+ FLOW_U32_VALUE(&wc->masks, idx) |= rightmost_1bit(diff);
+ }
+ return false;
+ }
+ /* Fill in the bits that were looked at. */
+ FLOW_U32_VALUE(&wc->masks, idx) |= mask;
+ }
+
+ return true;
+}
+
static struct cls_match *
find_match_wc(const struct cls_subtable *subtable, const struct flow *flow,
struct trie_ctx trie_ctx[CLS_MAX_TRIES], unsigned int n_tries,
@@ -1467,11 +1496,11 @@ find_match_wc(const struct cls_subtable *subtable, const struct flow *flow,
* optimization. */
if (!inode->s) {
ASSIGN_CONTAINER(rule, inode - i, index_nodes);
- if (miniflow_and_mask_matches_flow(&rule->flow, &subtable->mask,
- flow, wc)) {
- goto out;
+ if (miniflow_and_mask_matches_flow_wc(&rule->flow, &subtable->mask,
+ flow, wc)) {
+ return rule;
}
- goto range_out;
+ return NULL;
}
}
ofs.end = FLOW_U32S;
@@ -1499,7 +1528,7 @@ find_match_wc(const struct cls_subtable *subtable, const struct flow *flow,
ofs.start = TP_PORTS_OFS32;
goto range_out;
}
-out:
+
/* Must unwildcard all the fields, as they were looked at. */
flow_wildcards_fold_minimask(wc, &subtable->mask);
return rule;
diff --git a/tests/ofproto-dpif.at b/tests/ofproto-dpif.at
index 6d53cac..dffb2cc 100644
--- a/tests/ofproto-dpif.at
+++ b/tests/ofproto-dpif.at
@@ -3914,7 +3914,7 @@ AT_CHECK([ovs-appctl netdev-dummy/receive p1 'in_port(1),eth(src=50:54:00:00:00:
sleep 1
AT_CHECK([cat ovs-vswitchd.log | FILTER_FLOW_INSTALL | STRIP_XOUT], [0], [dnl
skb_priority(0),skb_mark(0/0),recirc_id(0),dp_hash(0/0),in_port(1),eth(src=50:54:00:00:00:09/ff:ff:ff:ff:ff:ff,dst=50:54:00:00:00:0a/00:00:00:00:00:00),eth_type(0x0800),ipv4(src=10.0.0.2/0.0.0.0,dst=10.0.0.1/0.0.0.0,proto=1/0,tos=0/0,ttl=64/0,frag=no/0xff),icmp(type=8/0,code=0/0), actions: <del>
-skb_priority(0),skb_mark(0/0),recirc_id(0),dp_hash(0/0),in_port(1),eth(src=50:54:00:00:00:0b/00:00:00:00:00:02,dst=50:54:00:00:00:0c/00:00:00:00:00:00),eth_type(0x0800),ipv4(src=10.0.0.4/0.0.0.0,dst=10.0.0.3/0.0.0.0,proto=1/0,tos=0/0,ttl=64/0,frag=no/0xff),icmp(type=8/0,code=0/0), actions: <del>
+skb_priority(0),skb_mark(0/0),recirc_id(0),dp_hash(0/0),in_port(1),eth(src=50:54:00:00:00:0b/ff:ff:00:00:00:02,dst=50:54:00:00:00:0c/00:00:00:00:00:00),eth_type(0x0800),ipv4(src=10.0.0.4/0.0.0.0,dst=10.0.0.3/0.0.0.0,proto=1/0,tos=0/0,ttl=64/0,frag=no/0xff),icmp(type=8/0,code=0/0), actions: <del>
])
OVS_VSWITCHD_STOP
AT_CLEANUP
@@ -3952,7 +3952,7 @@ AT_CHECK([ovs-appctl netdev-dummy/receive p1 'in_port(1),eth(src=50:54:00:00:00:
sleep 1
AT_CHECK([cat ovs-vswitchd.log | FILTER_FLOW_INSTALL | STRIP_XOUT], [0], [dnl
skb_priority(0),skb_mark(0/0),recirc_id(0),dp_hash(0/0),in_port(1),eth(src=50:54:00:00:00:07/00:00:00:00:00:00,dst=50:54:00:00:00:05/00:00:00:00:00:00),eth_type(0x86dd),ipv6(src=2001:db8:3c4d:1:2:3:4:5/ffff:ffff:ffff:ffff:ffff:ffff:ffff:ffff,dst=fe80::2/::,label=0/0,proto=10/0,tclass=0x70/0,hlimit=128/0,frag=no/0xff), actions: <del>
-skb_priority(0),skb_mark(0/0),recirc_id(0),dp_hash(0/0),in_port(1),eth(src=50:54:00:00:00:09/00:00:00:00:00:00,dst=50:54:00:00:00:0a/00:00:00:00:00:00),eth_type(0x86dd),ipv6(src=2001:db8:3c4d:5:4:3:2:1/0:0:0:4::,dst=2001:db8:3c4d:1:2:3:4:1/::,label=0/0,proto=99/0,tclass=0x70/0,hlimit=64/0,frag=no/0xff), actions: <del>
+skb_priority(0),skb_mark(0/0),recirc_id(0),dp_hash(0/0),in_port(1),eth(src=50:54:00:00:00:09/00:00:00:00:00:00,dst=50:54:00:00:00:0a/00:00:00:00:00:00),eth_type(0x86dd),ipv6(src=2001:db8:3c4d:5:4:3:2:1/ffff:ffff:0:4::,dst=2001:db8:3c4d:1:2:3:4:1/::,label=0/0,proto=99/0,tclass=0x70/0,hlimit=64/0,frag=no/0xff), actions: <del>
])
OVS_VSWITCHD_STOP
AT_CLEANUP
@@ -4136,7 +4136,7 @@ AT_CHECK([ovs-appctl netdev-dummy/receive p1 'in_port(1),eth(src=50:54:00:00:00:
sleep 1
AT_CHECK([cat ovs-vswitchd.log | FILTER_FLOW_INSTALL | STRIP_XOUT], [0], [dnl
skb_priority(0),skb_mark(0/0),recirc_id(0),dp_hash(0/0),in_port(1),eth(src=50:54:00:00:00:09/ff:ff:ff:ff:ff:ff,dst=50:54:00:00:00:0a/00:00:00:00:00:00),eth_type(0x0800),ipv4(src=10.0.0.2/0.0.0.0,dst=10.0.0.1/0.0.0.0,proto=1/0,tos=0/0,ttl=64/0,frag=no/0xff),icmp(type=8/0,code=0/0), actions: <del>
-skb_priority(0),skb_mark(0/0),recirc_id(0),dp_hash(0/0),in_port(1),eth(src=50:54:00:00:00:0b/00:00:00:00:00:02,dst=50:54:00:00:00:0c/00:00:00:00:00:00),eth_type(0x0800),ipv4(src=10.0.0.4/0.0.0.0,dst=10.0.0.3/0.0.0.0,proto=1/0,tos=0/0,ttl=64/0,frag=no/0xff),icmp(type=8/0,code=0/0), actions: <del>
+skb_priority(0),skb_mark(0/0),recirc_id(0),dp_hash(0/0),in_port(1),eth(src=50:54:00:00:00:0b/ff:ff:00:00:00:02,dst=50:54:00:00:00:0c/00:00:00:00:00:00),eth_type(0x0800),ipv4(src=10.0.0.4/0.0.0.0,dst=10.0.0.3/0.0.0.0,proto=1/0,tos=0/0,ttl=64/0,frag=no/0xff),icmp(type=8/0,code=0/0), actions: <del>
])
OVS_VSWITCHD_STOP
AT_CLEANUP
Jarno
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.openvswitch.org/pipermail/ovs-dev/attachments/20140603/c45eab56/attachment-0005.html>
More information about the dev
mailing list