Re: [ovs-dev] [PATCH ovn v2 3/3] expr: Combine OR sub-expressions into supersets.
Bleep bloop. Greetings Ilya Maximets, I am a robot and I have tried out your
patch.
Thanks for your contribution.
I encountered some error that I wasn't expecting. See the details below.
checkpatch:
WARNING: Line is 93 characters long (recommended limit is 79)
#1300 FILE: p-set-addresses:17522:
# priority=2001,ip,metadata=0x1,nw_src=10.6.0.6
actions=conjunction(2,1/2),conjunction(3,1/2)
WARNING: Line is 93 characters long (recommended limit is 79)
#1301 FILE: p-set-addresses:17523:
# priority=2001,ip,metadata=0x1,nw_src=10.4.0.4
actions=conjunction(2,1/2),conjunction(3,1/2)
WARNING: Line is 93 characters long (recommended limit is 79)
#1302 FILE: p-set-addresses:17524:
# priority=2001,ip,metadata=0x1,nw_src=10.5.0.5
actions=conjunction(2,1/2),conjunction(3,1/2)
WARNING: Line is 93 characters long (recommended limit is 79)
#1368 FILE: p-set-addresses:17586:
# priority=2001,ip,metadata=0x1,nw_dst=10.9.0.9
actions=conjunction(4,1/2),conjunction(6,1/2)
WARNING: Line is 112 characters long (recommended limit is 79)
#1370 FILE: p-set-addresses:17588:
# priority=2001,ip,metadata=0x1,nw_src=10.5.0.5
actions=conjunction(4,2/2),conjunction(5,2/2),conjunction(6,2/2)
WARNING: Line is 112 characters long (recommended limit is 79)
#1371 FILE: p-set-addresses:17589:
# priority=2001,ip,metadata=0x1,nw_src=10.4.0.4
actions=conjunction(4,2/2),conjunction(5,2/2),conjunction(6,2/2)
WARNING: Line is 112 characters long (recommended limit is 79)
#1372 FILE: p-set-addresses:17590:
# priority=2001,ip,metadata=0x1,nw_src=10.6.0.6
actions=conjunction(4,2/2),conjunction(5,2/2),conjunction(6,2/2)
WARNING: Line is 93 characters long (recommended limit is 79)
#1400 FILE: p-set-addresses:17607:
# priority=2001,ip,metadata=0x1,nw_dst=10.9.0.9
actions=conjunction(7,1/2),conjunction(8,1/2)
WARNING: Line is 112 characters long (recommended limit is 79)
#1402 FILE: p-set-addresses:17609:
# priority=2001,ip,metadata=0x1,nw_src=10.5.0.5
actions=conjunction(7,2/2),conjunction(8,2/2),conjunction(9,2/2)
WARNING: Line is 112 characters long (recommended limit is 79)
#1403 FILE: p-set-addresses:17610:
# priority=2001,ip,metadata=0x1,nw_src=10.6.0.6
actions=conjunction(7,2/2),conjunction(8,2/2),conjunction(9,2/2)
WARNING: Line is 112 characters long (recommended limit is 79)
#1404 FILE: p-set-addresses:17611:
# priority=2001,ip,metadata=0x1,nw_src=10.4.0.4
actions=conjunction(7,2/2),conjunction(8,2/2),conjunction(9,2/2)
WARNING: Line is 95 characters long (recommended limit is 79)
#1420 FILE: p-set-addresses:17627:
# priority=2001,ip,metadata=0x1,nw_dst=10.9.0.9
actions=conjunction(10,1/2),conjunction(11,1/2)
WARNING: Line is 95 characters long (recommended limit is 79)
#1421 FILE: p-set-addresses:17628:
# priority=2001,ip,metadata=0x1,nw_src=10.5.0.5
actions=conjunction(10,2/2),conjunction(11,2/2)
WARNING: Line is 95 characters long (recommended limit is 79)
#1422 FILE: p-set-addresses:17629:
# priority=2001,ip,metadata=0x1,nw_src=10.6.0.6
actions=conjunction(10,2/2),conjunction(11,2/2)
WARNING: Line is 95 characters long (recommended limit is 79)
#1423 FILE: p-set-addresses:17630:
# priority=2001,ip,metadata=0x1,nw_src=10.4.0.4
actions=conjunction(10,2/2),conjunction(11,2/2)
WARNING: Line is 80 characters long (recommended limit is 79)
#1432 FILE: p-set-addresses:19443:
AT_CHECK([ovs-ofctl dump-flows br-int | grep "10.1.2.10/31"], [0], [ignore])
WARNING: Line is 92 characters long (recommended limit is 79)
#1450 FILE: p-set-addresses:31516:
lsp-set-addresses lsp${i}-${j} "aa:aa:aa:00:0$i:0$j
192.$i.$i.$((($j + 1) * 4))"
WARNING: Line is 82 characters long (recommended limit is 79)
#1459 FILE: p-set-addresses:31548:
AT_CHECK([test $(ovs-ofctl dump-flows br-int table=44 | grep 192. | wc -l) ==
10])
Lines checked: 1466, Warnings: 18, Errors: 0
Please check this out. If you feel there has been an error, please email
acon...@redhat.com
Thanks,
0-day Robot
___
dev mailing list
d...@openvswitch.org
https://mail.openvswitch.org/mailman/listinfo/ovs-dev
[ovs-dev] [PATCH ovn v2 3/3] expr: Combine OR sub-expressions into supersets.
If two simple CMP expressions within OR have exact same masks, and
their values differ in a single bit, these expressions can be combined
into one by removing that bit from the mask.
E.g. Expression (tcp.src == 6441 || tcp.src == 6443) can be
simplified down to single tcp.src == 0x1929/0xfffd.
6441 = 0x1929 = 0b0001100100101001
6643 = 0x192b = 0b0001100100101011
^
0x1929 0b0001100100101001
/ = /
0xfffd 0b1101
Since the bit can be either 0 or 1, there is no need to check it at all.
Add checking of possibility to combine two expressions into a new
superset while handling supersets in crushed OR expressions. This
allows to combine entries multiple times as well as remove entries
that are subsets of newly created supersets.
The loop will not spin for way too long, because every jump back means
removal of at least one existing entry from the list.
Change allows to efficiently squash IP address sets as well as matches
on other fully maskable fields like L4 ports and MAC addresses. E.g.:
$ ./tests/ovstest test-ovn expr-to-flows <<< \
"ip4.src == {172.168.12.0/24, 172.168.13.0/24, 172.168.15.0/24}"
ip,nw_src=172.168.15.0/24
ip,nw_src=172.168.12.0/23
$ ./tests/ovstest test-ovn expr-to-flows <<< \
"ip4.src == {172.168.12.0/24, 172.168.13.0/24, 172.168.14.0/24, \
172.168.15.0/24}"
ip,nw_src=172.168.12.0/22
In this case, first we combine 12 and 13, then 14 and 15, then results
of two previous combinations.
It's a greedy algorithm, i.e. it makes locally optimal decisions on
each step that may or may not be globally optimal:
$ ./tests/ovstest test-ovn expr-to-flows <<< \
"ip4.src == {172.168.12.0/24, 172.168.13.0/24, 172.168.14.0/24, \
172.168.15.0/24, 172.169.12.0/24}"
ip,nw_src=172.168.12.0/22
ip,nw_src=172.169.12.0/24
But
$ ./tests/ovstest test-ovn expr-to-flows <<< \
"ip4.src == {172.169.12.0/24, 172.168.12.0/24, 172.168.13.0/24, \
172.168.14.0/24, 172.168.15.0/24}"
ip,nw_src=172.168.13.0/255.255.253.0
ip,nw_src=172.168.14.0/24
ip,nw_src=172.168.12.0/255.254.255.0
In the case above it would be better to combine all the 172.168.*
subnets, but it doesn't happen if 172.169.12.0/24 is at the top of
the list, because it can be paired with 172.168.12.0/24 instead.
However, produced results are good enough in most cases. Full
non-greedy solution will likely be much more computationally complex.
Tests updated to reflect this change. Extra couple of specific tests
added. Tests that depend on the exact number of OpenFlow rules
updated to use addresses that cannot be combined.
This change makes address set I-P less efficient, but it also
reduces the number of generated OpenFlow rules, so very efficient
I-P is less important.
Signed-off-by: Ilya Maximets
---
controller/lflow.c | 5 +-
lib/expr.c | 77 +++-
tests/ovn-controller.at | 399
tests/ovn.at| 198 ++--
4 files changed, 366 insertions(+), 313 deletions(-)
diff --git a/controller/lflow.c b/controller/lflow.c
index 003195ae4..7c57c9acc 100644
--- a/controller/lflow.c
+++ b/controller/lflow.c
@@ -449,8 +449,9 @@ consider_lflow_for_added_as_ips__(
new_fake_as->n_values = 2;
new_fake_as->values[0] = new_fake_as->values[1] =
as_diff_added->values[0];
-/* Make a dummy ip that is different from the real one. */
-new_fake_as->values[1].value.u8_val++;
+/* Make a dummy ip that is different from the real one in 2 bits,
+ * so expression normalization won't combine them. */
+new_fake_as->values[1].value.u8_val ^= 3;
dummy_ip = new_fake_as->values[1].value.ipv6;
has_dummy_ip = true;
fake_as = new_fake_as;
diff --git a/lib/expr.c b/lib/expr.c
index d881e07f7..da1faf1e4 100644
--- a/lib/expr.c
+++ b/lib/expr.c
@@ -2522,9 +2522,39 @@ crush_and_string(struct expr *expr, const struct
expr_symbol *symbol)
return expr_fix(expr);
}
-/* This function expects an OR expression with already crushed sub
- * expressions, so they are plain comparisons. Result is the same
- * expression, but with unnecessary sub-expressions removed. */
+/* Given 2 CMP expressions for the same maskable symbol, calculates bitmaps
+ * that starts at the same offset, has the same size and cover all the
+ * masked bits in both expressions. Results are correctly aligned to be
+ * used in bitmap_* functions. */
+static void
+expr_bitmap_mask_range(struct expr *a, struct expr *b,
+ const struct expr_symbol *symbol,
+ unsigned long **a_bitmap, unsigned long **b_bitmap,
+ size_t *start_ofs, size_t *n_bits)
+{
+ovs_assert(a->type == EXPR_T_CMP);
+ovs_assert(b->type == EXPR_T_CMP);
+
+*n_bits = sizeof
