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>

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;