Re: [ovs-dev] [PATCH 4/4] expr: Better simplify some special cases of expressions.

[Ben Pfaff]

On Mon, Oct 10, 2016 at 04:52:07PM -0700, Andy Zhou wrote:
> On Thu, Oct 6, 2016 at 8:30 PM, Ben Pfaff  wrote:
> 
> > It's pretty unlikely that a human would write expressions like these, but
> > they can come up in machine-generated expressions and it seems best to
> > simplify them in an efficient way.
> >
> > Signed-off-by: Ben Pfaff 
> >
> Acked-by: Andy Zhou 

Thanks for the reviews!  I applied these to master and I'm planning to
apply the first three to branch-2.6 in a minute.
___
dev mailing list
dev@openvswitch.org
http://openvswitch.org/mailman/listinfo/dev

Re: [ovs-dev] [PATCH 4/4] expr: Better simplify some special cases of expressions.

[Andy Zhou]

On Thu, Oct 6, 2016 at 8:30 PM, Ben Pfaff  wrote:

> It's pretty unlikely that a human would write expressions like these, but
> they can come up in machine-generated expressions and it seems best to
> simplify them in an efficient way.
>
> Signed-off-by: Ben Pfaff 
>
Acked-by: Andy Zhou 
___
dev mailing list
dev@openvswitch.org
http://openvswitch.org/mailman/listinfo/dev

[ovs-dev] [PATCH 4/4] expr: Better simplify some special cases of expressions.

[Ben Pfaff]

It's pretty unlikely that a human would write expressions like these, but
they can come up in machine-generated expressions and it seems best to
simplify them in an efficient way.

Signed-off-by: Ben Pfaff 
---
 ovn/lib/expr.c | 41 ++---
 tests/ovn.at   | 12 
 2 files changed, 46 insertions(+), 7 deletions(-)

diff --git a/ovn/lib/expr.c b/ovn/lib/expr.c
index a197474..5399985 100644
--- a/ovn/lib/expr.c
+++ b/ovn/lib/expr.c
@@ -297,6 +297,10 @@ expr_fix(struct expr *expr)
 
 /* Formatting. */
 
+/* Searches bits [0,width) in 'sv' for a contiguous sequence of 1-bits.  If one
+ * such sequence exists, stores the index of the first 1-bit into '*startp' and
+ * the number of 1-bits into '*n_bitsp'.  Stores 0 into both variables if no
+ * such sequence, or more than one, exists. */
 static void
 find_bitwise_range(const union mf_subvalue *sv, int width,
int *startp, int *n_bitsp)
@@ -1729,18 +1733,41 @@ expr_simplify_relational(struct expr *expr)
 ovs_assert(n_bits > 0);
 end = start + n_bits;
 
-struct expr *new;
-if (expr->cmp.relop == EXPR_R_LE || expr->cmp.relop == EXPR_R_GE) {
+/* Handle some special cases.
+ *
+ * These optimize to just "true":
+ *
+ *tcp.dst >= 0
+ *tcp.dst <= 65535
+ *
+ * These are easier to understand, and equivalent, when treated as if
+ * > or < were !=:
+ *
+ *tcp.dst > 0
+ *tcp.dst < 65535
+ */
+bool lt = expr->cmp.relop == EXPR_R_LT || expr->cmp.relop == EXPR_R_LE;
+bool eq = expr->cmp.relop == EXPR_R_LE || expr->cmp.relop == EXPR_R_GE;
+if (bitwise_scan(value, sizeof *value, !lt, start, end) == end) {
+if (eq) {
+expr_destroy(expr);
+return expr_create_boolean(true);
+} else {
+return expr_simplify_ne(expr);
+}
+}
+
+/* Reduce "tcp.dst >= 1234" to "tcp.dst == 1234 || tcp.dst > 1234",
+ * and similarly for "tcp.dst <= 1234". */
+struct expr *new = NULL;
+if (eq) {
 new = xmemdup(expr, sizeof *expr);
 new->cmp.relop = EXPR_R_EQ;
-} else {
-new = NULL;
 }
 
-bool b = expr->cmp.relop == EXPR_R_LT || expr->cmp.relop == EXPR_R_LE;
-for (int z = bitwise_scan(value, sizeof *value, b, start, end);
+for (int z = bitwise_scan(value, sizeof *value, lt, start, end);
  z < end;
- z = bitwise_scan(value, sizeof *value, b, z + 1, end)) {
+ z = bitwise_scan(value, sizeof *value, lt, z + 1, end)) {
 struct expr *e;
 
 e = xmemdup(expr, sizeof *expr);
diff --git a/tests/ovn.at b/tests/ovn.at
index be85004..5f3f4df 100644
--- a/tests/ovn.at
+++ b/tests/ovn.at
@@ -433,6 +433,18 @@ AT_CHECK([simplify 'eth.dst == 0/0'], [0], [1
 ])
 AT_CHECK([simplify 'eth.dst != 0/0'], [0], [0
 ])
+AT_CHECK([simplify 'tcp.dst >= 0'], [0],
+[ip.proto == 0x6 && (eth.type == 0x800 || eth.type == 0x86dd)
+])
+AT_CHECK([simplify 'tcp.dst <= 65535'], [0],
+[ip.proto == 0x6 && (eth.type == 0x800 || eth.type == 0x86dd)
+])
+AT_CHECK([simplify 'tcp.dst > 0'], [0],
+[[(tcp.dst[0] || tcp.dst[1] || tcp.dst[2] || tcp.dst[3] || tcp.dst[4] || 
tcp.dst[5] || tcp.dst[6] || tcp.dst[7] || tcp.dst[8] || tcp.dst[9] || 
tcp.dst[10] || tcp.dst[11] || tcp.dst[12] || tcp.dst[13] || tcp.dst[14] || 
tcp.dst[15]) && ip.proto == 0x6 && (eth.type == 0x800 || eth.type == 0x86dd)
+]])
+AT_CHECK([simplify 'tcp.dst < 65535'], [0],
+[[(!tcp.dst[0] || !tcp.dst[1] || !tcp.dst[2] || !tcp.dst[3] || !tcp.dst[4] 
|| !tcp.dst[5] || !tcp.dst[6] || !tcp.dst[7] || !tcp.dst[8] || !tcp.dst[9] || 
!tcp.dst[10] || !tcp.dst[11] || !tcp.dst[12] || !tcp.dst[13] || !tcp.dst[14] || 
!tcp.dst[15]) && ip.proto == 0x6 && (eth.type == 0x800 || eth.type == 0x86dd)
+]])
 AT_CLEANUP
 
 AT_SETUP([ovn -- 4-term numeric expression normalization])
-- 
2.1.3

___
dev mailing list
dev@openvswitch.org
http://openvswitch.org/mailman/listinfo/dev