optimize: compact bitmask matching in set/map

Check if right hand side of relational is a bitmask, ie.

     relational
       /   \
    ...     or
           /  \
       value   or
              /  \
         value    value

then, if left hand side is a binop expression, compare left and right
hand sides (not only left hand of this binop expression) to check for
redundant matches in consecutive rules, ie.

        relational
          /   \
       and     ...
      /   \
 payload  value

before this patch, only payload in the binop expression was compared.

This allows to compact several rules matching tcp flags in a set/map, eg.

 # nft -c -o -f ruleset.nft
 Merging:
 ruleset.nft:7:17-76:                 tcp flags & (fin | syn | rst | ack | urg) == fin | ack | urg
 ruleset.nft:8:17-70:                 tcp flags & (fin | syn | rst | ack | urg) == fin | ack
 ruleset.nft:9:17-64:                 tcp flags & (fin | syn | rst | ack | urg) == fin
 ruleset.nft:10:17-70:                 tcp flags & (fin | syn | rst | ack | urg) == syn | ack
 ruleset.nft:11:17-64:                 tcp flags & (fin | syn | rst | ack | urg) == syn
 ruleset.nft:12:17-70:                 tcp flags & (fin | syn | rst | ack | urg) == rst | ack
 ruleset.nft:13:17-64:                 tcp flags & (fin | syn | rst | ack | urg) == rst
 ruleset.nft:14:17-70:                 tcp flags & (fin | syn | rst | ack | urg) == ack | urg
 ruleset.nft:15:17-64:                 tcp flags & (fin | syn | rst | ack | urg) == ack
 into:
        tcp flags & (fin | syn | rst | ack | urg) == { fin | ack | urg, fin | ack, fin, syn | ack, syn, rst | ack, rst, ack | urg, ack }
 Merging:
 ruleset.nft:17:17-61:                 tcp flags & (ack | urg) == ack jump ack_chain
 ruleset.bft:18:17-61:                 tcp flags & (ack | urg) == urg jump urg_chain
 into:
        tcp flags & (ack | urg) vmap { ack : jump ack_chain, urg : jump urg_chain }

Signed-off-by: Pablo Neira Ayuso <pablo@netfilter.org>

1 files changed, 34 insertions, 1 deletions

diff --git a/src/optimize.c b/src/optimize.c
index bb849267..44010f2b 100644
--- a/src/optimize.c
+++ b/src/optimize.c
@@ -127,7 +127,17 @@ static bool __expr_cmp(const struct expr *expr_a, const struct expr *expr_b)
 			return false;
 		break;
 	case EXPR_BINOP:
-		return __expr_cmp(expr_a->left, expr_b->left);
+		if (!__expr_cmp(expr_a->left, expr_b->left))
+			return false;
+
+		return __expr_cmp(expr_a->right, expr_b->right);
+	case EXPR_SYMBOL:
+		if (expr_a->symtype != expr_b->symtype)
+			return false;
+		if (expr_a->symtype != SYMBOL_VALUE)
+			return false;
+
+		return !strcmp(expr_a->identifier, expr_b->identifier);
 	default:
 		return false;
 	}
@@ -135,6 +145,25 @@ static bool __expr_cmp(const struct expr *expr_a, const struct expr *expr_b)
 	return true;
 }
 
+static bool is_bitmask(const struct expr *expr)
+{
+	switch (expr->etype) {
+	case EXPR_BINOP:
+		if (expr->op == OP_OR &&
+		    !is_bitmask(expr->left))
+			return false;
+
+		return is_bitmask(expr->right);
+	case EXPR_VALUE:
+	case EXPR_SYMBOL:
+		return true;
+	default:
+		break;
+	}
+
+	return false;
+}
+
 static bool stmt_expr_supported(const struct expr *expr)
 {
 	switch (expr->right->etype) {
@@ -146,6 +175,10 @@ static bool stmt_expr_supported(const struct expr *expr)
 	case EXPR_LIST:
 	case EXPR_VALUE:
 		return true;
+	case EXPR_BINOP:
+		if (is_bitmask(expr->right))
+			return true;
+		break;
 	default:
 		break;
 	}