pipapo with element shadowing, wildcard support

[Florian Westphal <fw@strlen.de>]

[-- Attachment #1: Type: text/plain, Size: 2601 bytes --]

Hi,

I am currently looking into pipapo and wildcard matching.
Before going into a bit more details consider the following
example set:

 map s {
   typeof iifname . ip saddr . oifname : verdict
   flags interval
 }

This works fine, but pipapo comes with caveats.
1. Currently pipapo allows to insert a 'narrow' key like e.g.:
  add element t s {  "lo" . 127.0.0.1 . "lo"  : accept }

  ... and then add a 'broader' one afterwards, e.g.:
  add element t s {  "lo" . 127.0.0.1/8 . "lo"  : drop }

but this doesn't work when placing these add calls in the
reverse order (you get -EEXIST).

Question would be if it makes sense to relax the -EEXIST checks so that in
step 1 the wider key could be inserted first and then allow it to be
(partially) shadowed later.

Things get worse when adding wildcard support:

 map s {
   typeof iifname . ip saddr . oifname : verdict
   flags interval
   elements = { "*" . 127.0.0.5 . "" : jump test1,
                "*" . 127.0.0.1 . "" : jump test2,
                "lo" . 127.0.0.1 . "" : jump test3,
                "lo" . 127.0.0.5 . "" : jump test4 }
 }

(requires attached nft hack to permit both "*" and "" identifiers)

Example is same as before:
 add element inet t s '{  "lo" . 127.0.0.1 . "" counter : jump testlo1 }'
 add element inet t s '{  "lo" . 127.0.0.0/8 . "" counter : jump testW1 }'

 works but not vice versa.  (fails with -EEXIST).

If the existing behavior is ok as-is, i.e. userspace has to pre-order the
add calls, then no changes are needed.

But I dislike this, I don't think users should be expected to first
autoremove existing elements, then add the new element, then add back the
old, wider entry.

I also worry that we could end up with subtle bugs, e.g. rule(set) dumps
that can't be restored because of element ordering tripping over -EEXIST
test.

Do you think that:
   add element inet t s '{  "lo" . 127.0.0.0/8 . ...'
   add element inet t s '{  "lo" . 127.0.0.1 . ...'

should work, i.e. second element add should work (and override the
pre-existing entry in case new entry is more specific)?

AFAICS the 'override' part isn't as easy as relaxing the -EEXIST checks;
we would have to re-order the elements internally, else even 'lo 127.0.0.1'
would match the /8 entry first, so we would require to order the elements
so the most narrow element is placed first in the lookup table.

That in turn won't be nice to handle from kernel, so I wonder if nftables
needs to do more work here, similar to how we 'auto-merge' for rbtree/interval
set types?

Before I spend more time on it, has anyone looked into this before?

Thanks!

[-- Attachment #2: nft-wildcard-support-hack.diff --]
[-- Type: text/plain, Size: 1515 bytes --]

diff --git a/src/evaluate.c b/src/evaluate.c
--- a/src/evaluate.c
+++ b/src/evaluate.c
@@ -378,11 +378,10 @@ static int expr_evaluate_string(struct eval_ctx *ctx, struct expr **exprp)
 	memset(data + len, 0, data_len - len);
 	mpz_export_data(data, expr->value, BYTEORDER_HOST_ENDIAN, len);
 
-	if (strlen(data) == 0)
-		return expr_error(ctx->msgs, expr,
-				  "Empty string is not allowed");
+	datalen = strlen(data);
+	if (datalen)
+		datalen--;
 
-	datalen = strlen(data) - 1;
 	if (data[datalen] != '*') {
 		/* We need to reallocate the constant expression with the right
 		 * expression length to avoid problems on big endian.
@@ -395,11 +394,7 @@ static int expr_evaluate_string(struct eval_ctx *ctx, struct expr **exprp)
 		return 0;
 	}
 
-	if (datalen == 0)
-		return expr_error(ctx->msgs, expr,
-				  "All-wildcard strings are not supported");
-
-	if (data[datalen - 1] == '\\') {
+	if (datalen > 0 && data[datalen - 1] == '\\') {
 		char unescaped_str[data_len];
 
 		memset(unescaped_str, 0, sizeof(unescaped_str));
diff --git a/src/segtree.c b/src/segtree.c
--- a/src/segtree.c
+++ b/src/segtree.c
@@ -412,7 +412,8 @@ void concat_range_aggregate(struct expr *set)
 				unsigned int str_len = prefix_len / BITS_PER_BYTE;
 				char data[str_len + 2];
 
-				mpz_export_data(data, r1->value, BYTEORDER_HOST_ENDIAN, str_len);
+				if (str_len)
+					mpz_export_data(data, r1->value, BYTEORDER_HOST_ENDIAN, str_len);
 				data[str_len] = '*';
 
 				tmp = constant_expr_alloc(&r1->location, r1->dtype,