mergesort: find base value expression type via recursion
Pablo Neira Ayuso
maintainerPATCH v3 1/1 mergesort: find base value expression type via recursion
Sets that store flags might contain a mixture of values and binary operations. Find the base value type via recursion to compare the expressions.
Fixes 14ee0a979b62 ("src: sort set elements in netlink_get_setelems()")
Fixes 3926a3369bb5 ("mergesort: unbreak listing with binops")
Signed-off-by Pablo Neira Ayuso <[email protected]>
---
v3: simplify concatenation, take first component of the tuple as key for sorting
src/mergesort.c | 49 ++++++++----------- tests/shell/testcases/sets/0055tcpflags_0 | 27 ++++++++++ .../testcases/sets/dumps/0055tcpflags_0.nft | 10 ++++ 3 files changed, 57 insertions(+), 29 deletions(-) create mode 100755 tests/shell/testcases/sets/0055tcpflags_0 create mode 100644 tests/shell/testcases/sets/dumps/0055tcpflags_0.nft
src/mergesort.c +20 -29
@@ -13,43 +13,34 @@static int expr_msort_cmp (const struct expr *e1,const struct expr *e2); -static int concat_expr_msort_cmp (const struct expr *e1,const struct expr *e2) +static const struct expr *expr_msort_value (const struct expr *expr) { -struct list_head *l = (&e2->expressions)->next; -const struct expr *i1, *i2; -int ret; - -list_for_each_entry (i1, &e1->expressions, list) { - i2 = list_entry(l, typeof(struct expr), list); - - ret =expr_msort_cmp (i1, i2); -if (ret) -return ret; - - l = l->next; - } - -return false; -} - -static int expr_msort_cmp (const struct expr *e1,const struct expr *e2) -{ -switch (e1->etype) { +switch (expr->etype) {case EXPR_SET_ELEM : -return expr_msort_cmp (e1->key, e2->key); +return expr_msort_value (expr->key); +case EXPR_BINOP : +case EXPR_MAPPING : +return expr_msort_value (expr->left);case EXPR_VALUE : -return mpz_cmp (e1->value, e2->value); +return expr;case EXPR_CONCAT : -return concat_expr_msort_cmp (e1, e2); -case EXPR_MAPPING : -return expr_msort_cmp (e1->left, e2->left); -case EXPR_BINOP : -return expr_msort_cmp (e1->left, e2->left); + expr = list_first_entry(&expr->expressions, struct expr, list); +return expr_msort_value (expr);default : -BUG ("Unknown expression %s\n" ,expr_name (e1)); +BUG ("Unknown expression %s\n" ,expr_name (expr)); } } +static int expr_msort_cmp (const struct expr *e1,const struct expr *e2) +{ + e1 =expr_msort_value (e1); + e2 =expr_msort_value (e2); + +assert (e1->etype == e2->etype && e1->etype ==EXPR_VALUE ); + +return mpz_cmp (e1->value, e2->value); +} +static void list_splice_sorted (struct list_head *list,struct list_head *head) {struct list_head *h = head->next;
tests/shell/testcases/sets/0055tcpflags_0 new file +27 -0
@@ -0,0 +1,27 @@ +#!/bin/bash + +EXPECTED="add table ip test + +add set ip test tcp_good_flags { type tcp_flag ; flags constant ; elements = { + ( 0 | 0 | 0 |ack| 0 | 0 ), \ + ( 0 | 0 | 0 |ack| 0 |urg), \ + ( 0 | 0 | 0 |ack|psh| 0 ), \ + ( 0 | 0 | 0 |ack|psh|urg), \ + ( 0 | 0 |rst| 0 | 0 | 0 ), \ + ( 0 | 0 |rst|ack| 0 | 0 ), \ + ( 0 | 0 |rst|ack| 0 |urg), \ + ( 0 | 0 |rst|ack|psh| 0 ), \ + ( 0 | 0 |rst|ack|psh|urg), \ + ( 0 |syn| 0 | 0 | 0 | 0 ), \ + ( 0 |syn| 0 |ack| 0 | 0 ), \ + ( 0 |syn| 0 |ack| 0 |urg), \ + ( 0 |syn| 0 |ack|psh| 0 ), \ + ( 0 |syn| 0 |ack|psh|urg), \ + (fin| 0 | 0 |ack| 0 | 0 ), \ + (fin| 0 | 0 |ack| 0 |urg), \ + (fin| 0 | 0 |ack|psh| 0 ), \ + (fin| 0 | 0 |ack|psh|urg) \ +} ; }" + +set -e +$NFT -f - <<< $EXPECTED
tests/shell/testcases/sets/dumps/0055tcpflags_0.nft new file +10 -0
@@ -0,0 +1,10 @@ +table ip test { + set tcp_good_flags { + type tcp_flag + flags constant + elements = { fin | psh | ack | urg, fin | psh | ack, fin | ack | urg, fin | ack, syn | psh | ack | urg, + syn | psh | ack, syn | ack | urg, syn | ack, syn, rst | psh | ack | urg, + rst | psh | ack, rst | ack | urg, rst | ack, rst, psh | ack | urg, + psh | ack, ack | urg, ack } + } +}
Signature · 1 line
2.20.1