mergesort: find base value expression type via recursion
Pablo Neira Ayuso
maintainerPATCH v4 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]>
---
v4: Make sure concatenations are listed in a deterministic way via
concat_expr_msort_value.
Adjust a few tests after this update since listing differs.
src/mergesort.c | 61 ++++++++++++------- .../nft-f/dumps/0012different_defines_0.nft | 2 +- tests/shell/testcases/sets/0055tcpflags_0 | 27 ++++++++ .../dumps/0037_set_with_inet_service_0.nft | 8 +-- .../testcases/sets/dumps/0055tcpflags_0.nft | 10 +++ 5 files changed, 81 insertions(+), 27 deletions(-) create mode 100755 tests/shell/testcases/sets/0055tcpflags_0 create mode 100644 tests/shell/testcases/sets/dumps/0055tcpflags_0.nft
src/mergesort.c +39 -22
@@ -12,44 +12,61 @@#include <list.h> static int expr_msort_cmp (const struct expr *e1,const struct expr *e2); +static void expr_msort_value (const struct expr *expr,mpz_t value); -static int concat_expr_msort_cmp (const struct expr *e1,const struct expr *e2) +static void concat_expr_msort_value (const struct expr *expr,mpz_t value) { -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); +const struct expr *i; +unsigned int len =0 ; +char data[512 ]; - ret =expr_msort_cmp (i1, i2); -if (ret) -return ret; +mpz_init (value); - l = l->next; +list_for_each_entry (i, &expr->expressions, list) { +mpz_export_data (data + len, i->value, i->byteorder, i->len); + len += i->len; } -return false; +mpz_import_data (value, data,BYTEORDER_HOST_ENDIAN , len); } -static int expr_msort_cmp (const struct expr *e1,const struct expr *e2) +static void expr_msort_value (const struct expr *expr,mpz_t value) { -switch (e1->etype) { +switch (expr->etype) {case EXPR_SET_ELEM : -return expr_msort_cmp (e1->key, e2->key); +expr_msort_value (expr->key, value); +break ; +case EXPR_BINOP : +case EXPR_MAPPING : +expr_msort_value (expr->left, value); +break ;case EXPR_VALUE : -return mpz_cmp (e1->value, e2->value); +mpz_set (value, expr->value); +break ;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); +concat_expr_msort_value (expr, value); +break ;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) +{ +mpz_t value1, value2; +int ret; + +mpz_init (value1); +mpz_init (value2); +expr_msort_value (e1, value1); +expr_msort_value (e2, value2); + ret =mpz_cmp (value1, value2); +mpz_clear (value1); +mpz_clear (value2); + +return ret; +} +static void list_splice_sorted (struct list_head *list,struct list_head *head) {struct list_head *h = head->next;
tests/shell/testcases/nft-f/dumps/0012different_defines_0.nft +1 -1
@@ -8,7 +8,7 @@ table inet t { ip6 daddr fe0::1 ip6 saddr fe0::2 ip saddr vmap { 10.0.0.0 : drop, 10.0.0.2 : accept } ip6 daddr vmap { fe0::1 : drop, fe0::2 : accept } - ip6 saddr . ip6 nexthdr { fe0::1 . udp, fe0::2 . tcp } + ip6 saddr . ip6 nexthdr { fe0::2 . tcp, fe0::1 . udp } ip daddr . iif vmap { 10.0.0.0 . "lo" : accept } tcp dport 100-222 udp dport vmap { 100-222 : accept }
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/0037_set_with_inet_service_0.nft +4 -4
@@ -1,11 +1,11 @@ table inet filter { set myset { type ipv4_addr . inet_proto . inet_service - elements = { 192.168.0.12 . tcp . 53, - 192.168.0.12 . tcp . 80, + elements = { 192.168.0.113 . tcp . 22, + 192.168.0.12 . tcp . 53, 192.168.0.12 . udp . 53, - 192.168.0.13 . tcp . 80, - 192.168.0.113 . tcp . 22 } + 192.168.0.12 . tcp . 80, + 192.168.0.13 . tcp . 80 } } chain forward {
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