[ovs-git] [openvswitch/ovs] 32157c: Factor prerequisites out of AND/OR trees with uniq...
GitHub
noreply at github.com
Thu May 24 20:56:34 UTC 2018
Branch: refs/heads/master
Home: https://github.com/openvswitch/ovs
Commit: 32157c87035da27e8d23ed8431633b059ce5c252
https://github.com/openvswitch/ovs/commit/32157c87035da27e8d23ed8431633b059ce5c252
Author: Jakub Sitnicki <jkbs at redhat.com>
Date: 2018-05-24 (Thu, 24 May 2018)
Changed paths:
M ovn/lib/expr.c
M tests/ovn.at
Log Message:
-----------
Factor prerequisites out of AND/OR trees with unique symbol
Appending prerequisites to sub-expressions of OR that are all over one
symbol prevents the expression-to-matches converter from applying
conjunctive matching. This happens during the annotation phase.
input: s1 == { c1, c2 } && s2 == { c3, c4 }
expanded: (s1 == c1 || s1 == c2) && (s2 == c3 || s2 == c4)
annotated: ((p1 && s1 == c1) || (p1 && s1 == c2)) &&
((p2 && s2 == c3) || (p2 && s2 == c4))
normalized: (p1 && p2 && s1 == c1 && s2 == c3) ||
(p1 && p2 && s1 == c1 && s2 == c4) ||
(p1 && p2 && s1 == c2 && s2 == c3) ||
(p1 && p2 && s1 == c2 && s2 == c4)
Where s1,s2 - symbols, c1..c4 - constants, p1,p2 - prerequisites.
Since sub-expressions of OR trees that are over one symbol all have the
same prerequisites, we can factor them out leaving the OR tree in tact,
and enabling the converter to apply conjunctive matching to
AND(OR(clause)) trees.
Going back to our example this change gives us:
input: s1 == { c1, c2 } && s2 == { c3, c4 }
expanded: (s1 == c1 || s1 == c2) && (s2 == c3 || s2 == c4)
annotated: (s1 == c1 || s1 == c2) && p1 && (s2 == c3 || s2 == c4) && p2
normalized: p1 && p2 && (s1 == c1 || s1 == c2) && (s2 == c3 || s2 == c4)
We also factor out the prerequisites out of pure AND or mixed AND/OR
trees to keep the common code path, but in this case the only thing we
gain is a shorter expression as prerequisites for each symbol appear
only once.
Documentation comments have been contributed by Ben Pfaff.
Signed-off-by: Jakub Sitnicki <jkbs at redhat.com>
Signed-off-by: Ben Pfaff <blp at ovn.org>
Commit: 55b259471719ceca1f0083bdd6a5f8c3e7690bae
https://github.com/openvswitch/ovs/commit/55b259471719ceca1f0083bdd6a5f8c3e7690bae
Author: Numan Siddique <nusiddiq at redhat.com>
Date: 2018-05-24 (Thu, 24 May 2018)
Changed paths:
M tests/ovn.at
Log Message:
-----------
Extend tests for conjunctive match support in OVN
Check the application of conjunctive matching to logical flow match
expressions. In particular cover the case where conjunctive matching is
applied to ACL match expressions that refer to Address Sets.
Mark Michelson who tested a similar patch [1] has found a significant
improvement in ACL processing and reduction of OF flows from an order of
1 million to few thousands. [2]
Signed-off-by: Numan Siddique <nusiddiq at redhat.com>
[1] - https://mail.openvswitch.org/pipermail/ovs-dev/2018-February/344523.html
[2] - https://mail.openvswitch.org/pipermail/ovs-dev/2018-February/344311.html
Signed-off-by: Ben Pfaff <blp at ovn.org>
Compare: https://github.com/openvswitch/ovs/compare/8af725e8b5b9...55b259471719
**NOTE:** This service been marked for deprecation: https://developer.github.com/changes/2018-04-25-github-services-deprecation/
Functionality will be removed from GitHub.com on January 31st, 2019.
More information about the git
mailing list