diff options
author | Pablo Neira Ayuso <pablo@netfilter.org> | 2020-09-03 12:33:21 +0200 |
---|---|---|
committer | Pablo Neira Ayuso <pablo@netfilter.org> | 2020-09-04 17:19:25 +0200 |
commit | 741a06ac15d2bd903b33e5032f5f6fcd54bebc4e (patch) | |
tree | fa2a9d76b894e37a76103b370f840719efa02335 /src | |
parent | c3bb98cd10670226de02455f5e45c5a170eec685 (diff) |
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.
Make sure concatenations are listed in a deterministic way via
concat_expr_msort_value() which builds a mpz value with the tuple.
Adjust a few tests after this update since listing differs after this
update.
Fixes: 14ee0a979b62 ("src: sort set elements in netlink_get_setelems()")
Fixes: 3926a3369bb5 ("mergesort: unbreak listing with binops")
Signed-off-by: Pablo Neira Ayuso <pablo@netfilter.org>
Diffstat (limited to 'src')
-rw-r--r-- | src/mergesort.c | 65 |
1 files changed, 40 insertions, 25 deletions
diff --git a/src/mergesort.c b/src/mergesort.c index 02094b48..41f35856 100644 --- a/src/mergesort.c +++ b/src/mergesort.c @@ -11,45 +11,60 @@ #include <gmputil.h> #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); - - ret = expr_msort_cmp(i1, i2); - if (ret) - return ret; - - l = l->next; + unsigned int len = 0, ilen; + const struct expr *i; + char data[512]; + + list_for_each_entry(i, &expr->expressions, list) { + ilen = div_round_up(i->len, BITS_PER_BYTE); + mpz_export_data(data + len, i->value, i->byteorder, ilen); + len += ilen; } - 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; |