[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