[PATCH nft 0/6] shrink memory usage for interval sets

[PATCH nft 0/6] shrink memory usage for interval sets

[Pablo Neira Ayuso]

Hi,

This is a continuation in the effort to reduce memory consumption for
sets from userspace.

Patch #1 adds a helper function as preparation work.

Patch #2 fixes invalid auto-merging of elements with different timeout.

Patch #3 add EXPR_RANGE_VALUE to reduce memory consumption of ranges,
which now require two struct expr instead of four.

Patch #4 makes a simple constification of a helper function to detect
interval sets with single key.

Patch #5 renames a field from set to init in mnl_nft_setelem_batch()
to prepare for passing struct set.

Patch #6 reworks the transformation from range to the singleton elements
that represents intervals through EXPR_F_INTERVAL_END to create them
only before the netlink message.

This shrinks runtime userspace memory consumption from 70.50 Mbytes to
43.38 Mbytes for a 100k intervals set sample.

Pablo Neira Ayuso (6):
  intervals: add helper function to set previous element
  intervals: do not merge intervals with different timeout
  src: add EXPR_RANGE_VALUE expression and use it
  rule: constify set_is_non_concat_range()
  mnl: rename list of expression in mnl_nft_setelem_batch()
  src: rework singleton interval transformation to reduce memory consumption

 include/expression.h |  13 ++
 include/intervals.h  |   2 +
 include/list.h       |   8 ++
 include/mnl.h        |   3 +-
 include/rule.h       |   2 +-
 src/expression.c     |  85 +++++++++++++
 src/intervals.c      | 280 +++++++++++++++++++++++++------------------
 src/mergesort.c      |   2 +
 src/mnl.c            |  81 +++++++++++--
 src/rule.c           |   4 +-
 10 files changed, 345 insertions(+), 135 deletions(-)

-- 
2.30.2

[PATCH nft 1/6] intervals: add helper function to set previous element

[Pablo Neira Ayuso]

Add helper function to set previous element during the automerge
iteration. No functional changes are intended.

Signed-off-by: Pablo Neira Ayuso <pablo@netfilter.org>
---
 src/intervals.c | 16 ++++++++++------
 1 file changed, 10 insertions(+), 6 deletions(-)

diff --git a/src/intervals.c b/src/intervals.c
index 12cccbdab752..44fdda36e35f 100644
--- a/src/intervals.c
+++ b/src/intervals.c
@@ -148,6 +148,14 @@ static void set_sort_splice(struct expr *init, struct set *set)
 	}
 }
 
+static void set_prev_elem(struct expr **prev, struct expr *i,
+			  struct range *prev_range, struct range *range)
+{
+	*prev = i;
+	mpz_set(prev_range->low, range->low);
+	mpz_set(prev_range->high, range->high);
+}
+
 static void setelem_automerge(struct set_automerge_ctx *ctx)
 {
 	struct expr *i, *next, *prev = NULL;
@@ -168,9 +176,7 @@ static void setelem_automerge(struct set_automerge_ctx *ctx)
 		range_expr_value_high(range.high, i);
 
 		if (!prev) {
-			prev = i;
-			mpz_set(prev_range.low, range.low);
-			mpz_set(prev_range.high, range.high);
+			set_prev_elem(&prev, i, &prev_range, &range);
 			continue;
 		}
 
@@ -192,9 +198,7 @@ static void setelem_automerge(struct set_automerge_ctx *ctx)
 			}
 		}
 
-		prev = i;
-		mpz_set(prev_range.low, range.low);
-		mpz_set(prev_range.high, range.high);
+		set_prev_elem(&prev, i, &prev_range, &range);
 	}
 
 	mpz_clear(prev_range.low);
-- 
2.30.2

[PATCH nft 2/6] intervals: do not merge intervals with different timeout

[Pablo Neira Ayuso]

If timeout/expiration of contiguous intervals is different, then do not
merge them.

Fixes: 81e36530fcac ("src: replace interval segment tree overlap and automerge")
Signed-off-by: Pablo Neira Ayuso <pablo@netfilter.org>
---
 src/intervals.c | 4 +++-
 1 file changed, 3 insertions(+), 1 deletion(-)

diff --git a/src/intervals.c b/src/intervals.c
index 44fdda36e35f..6308cc8e2c08 100644
--- a/src/intervals.c
+++ b/src/intervals.c
@@ -175,7 +175,9 @@ static void setelem_automerge(struct set_automerge_ctx *ctx)
 		range_expr_value_low(range.low, i);
 		range_expr_value_high(range.high, i);
 
-		if (!prev) {
+		if (!prev ||
+		    interval_expr_key(prev)->timeout != interval_expr_key(i)->timeout ||
+		    interval_expr_key(prev)->expiration != interval_expr_key(i)->expiration) {
 			set_prev_elem(&prev, i, &prev_range, &range);
 			continue;
 		}
-- 
2.30.2

[PATCH nft 3/6] src: add EXPR_RANGE_VALUE expression and use it

[Pablo Neira Ayuso]

set element with range takes 4 instances of struct expr:

  EXPR_SET_ELEM -> EXPR_RANGE -> (2) EXPR_VALUE

where EXPR_RANGE represents two references to struct expr with constant
value.

This new EXPR_RANGE_VALUE trims it down to two expressions:

  EXPR_SET_ELEM -> EXPR_RANGE_VALUE

with two direct low and high values that represent the range:

  struct {
      mpz_t low;
      mpz_t high;
  };

this two new direct values in struct expr do not modify its size.

setelem_expr_to_range() translates EXPR_RANGE to EXPR_RANGE_VALUE, this
conversion happens at a later stage.

constant_range_expr_print() translates this structure to constant values
to reuse the existing datatype_print() which relies in singleton values.

The automerge routine has been updated to use EXPR_RANGE_VALUE.

This requires a follow up patch to rework the conversion from range
expression to singleton element to provide a noticeable memory
consumption reduction.

Signed-off-by: Pablo Neira Ayuso <pablo@netfilter.org>
---
 include/expression.h | 13 +++++++
 src/expression.c     | 85 +++++++++++++++++++++++++++++++++++++++++
 src/intervals.c      | 90 +++++++++++++++++++++++---------------------
 src/mergesort.c      |  2 +
 4 files changed, 147 insertions(+), 43 deletions(-)

diff --git a/include/expression.h b/include/expression.h
index 877887ff1978..f2b45250872d 100644
--- a/include/expression.h
+++ b/include/expression.h
@@ -48,6 +48,7 @@
  * @EXPR_XFRM		XFRM (ipsec) expression
  * @EXPR_SET_ELEM_CATCHALL catchall element expression
  * @EXPR_FLAGCMP	flagcmp expression
+ * @EXPR_RANGE_VALUE	constant range expression
  */
 enum expr_types {
 	EXPR_INVALID,
@@ -80,6 +81,7 @@ enum expr_types {
 	EXPR_XFRM,
 	EXPR_SET_ELEM_CATCHALL,
 	EXPR_FLAGCMP,
+	EXPR_RANGE_VALUE,
 
 	EXPR_MAX = EXPR_FLAGCMP
 };
@@ -278,6 +280,11 @@ struct expr {
 			/* EXPR_VALUE */
 			mpz_t			value;
 		};
+		struct {
+			/* EXPR_RANGE_VALUE */
+			mpz_t			low;
+			mpz_t			high;
+		} range;
 		struct {
 			/* EXPR_PREFIX */
 			struct expr		*prefix;
@@ -473,6 +480,12 @@ extern struct expr *constant_expr_join(const struct expr *e1,
 				       const struct expr *e2);
 extern struct expr *constant_expr_splice(struct expr *expr, unsigned int len);
 
+extern struct expr *constant_range_expr_alloc(const struct location *loc,
+					      const struct datatype *dtype,
+					      enum byteorder byteorder,
+					      unsigned int len,
+					      mpz_t low, mpz_t high);
+
 extern struct expr *flag_expr_alloc(const struct location *loc,
 				    const struct datatype *dtype,
 				    enum byteorder byteorder,
diff --git a/src/expression.c b/src/expression.c
index 62786f483eed..bee379800501 100644
--- a/src/expression.c
+++ b/src/expression.c
@@ -542,6 +542,86 @@ struct expr *constant_expr_splice(struct expr *expr, unsigned int len)
 	return slice;
 }
 
+static void constant_range_expr_print(const struct expr *expr,
+				      struct output_ctx *octx)
+{
+	unsigned char data[sizeof(struct in6_addr) * BITS_PER_BYTE];
+	unsigned int flags = octx->flags;
+	struct expr *value;
+
+	octx->flags &= ~(NFT_CTX_OUTPUT_SERVICE |
+			 NFT_CTX_OUTPUT_REVERSEDNS |
+			 NFT_CTX_OUTPUT_GUID);
+	octx->flags |= NFT_CTX_OUTPUT_NUMERIC_ALL;
+
+	/* create dummy temporary constant expression to print range. */
+	mpz_export_data(data, expr->range.low, expr->byteorder, expr->len / BITS_PER_BYTE);
+	value = constant_expr_alloc(&expr->location,
+				    expr->dtype,
+				    expr->byteorder,
+				    expr->len,
+				    data);
+	expr_print(value, octx);
+	expr_free(value);
+
+	nft_print(octx, "-");
+
+	mpz_export_data(data, expr->range.high, expr->byteorder, expr->len / BITS_PER_BYTE);
+	value = constant_expr_alloc(&expr->location,
+				    expr->dtype,
+				    expr->byteorder,
+				    expr->len,
+				    data);
+	expr_print(value, octx);
+	expr_free(value);
+
+	octx->flags = flags;
+}
+
+static bool constant_range_expr_cmp(const struct expr *e1, const struct expr *e2)
+{
+	return expr_basetype(e1) == expr_basetype(e2) &&
+	       !mpz_cmp(e1->range.low, e2->range.low) &&
+	       !mpz_cmp(e1->range.high, e2->range.high);
+}
+
+static void constant_range_expr_clone(struct expr *new, const struct expr *expr)
+{
+	mpz_init_set(new->range.low, expr->range.low);
+	mpz_init_set(new->range.high, expr->range.high);
+}
+
+static void constant_range_expr_destroy(struct expr *expr)
+{
+	mpz_clear(expr->range.low);
+	mpz_clear(expr->range.high);
+}
+
+static const struct expr_ops constant_range_expr_ops = {
+	.type		= EXPR_RANGE_VALUE,
+	.name		= "range_value",
+	.print		= constant_range_expr_print,
+	.cmp		= constant_range_expr_cmp,
+	.clone		= constant_range_expr_clone,
+	.destroy	= constant_range_expr_destroy,
+};
+
+struct expr *constant_range_expr_alloc(const struct location *loc,
+				       const struct datatype *dtype,
+				       enum byteorder byteorder,
+				       unsigned int len, mpz_t low, mpz_t high)
+{
+	struct expr *expr;
+
+	expr = expr_alloc(loc, EXPR_RANGE_VALUE, dtype, byteorder, len);
+	expr->flags = EXPR_F_CONSTANT | EXPR_F_SINGLETON;
+
+	mpz_init_set(expr->range.low, low);
+	mpz_init_set(expr->range.high, high);
+
+	return expr;
+}
+
 /*
  * Allocate a constant expression with a single bit set at position n.
  */
@@ -1545,6 +1625,8 @@ void range_expr_value_low(mpz_t rop, const struct expr *expr)
 	switch (expr->etype) {
 	case EXPR_VALUE:
 		return mpz_set(rop, expr->value);
+	case EXPR_RANGE_VALUE:
+		return mpz_set(rop, expr->range.low);
 	case EXPR_PREFIX:
 		return range_expr_value_low(rop, expr->prefix);
 	case EXPR_RANGE:
@@ -1565,6 +1647,8 @@ void range_expr_value_high(mpz_t rop, const struct expr *expr)
 	switch (expr->etype) {
 	case EXPR_VALUE:
 		return mpz_set(rop, expr->value);
+	case EXPR_RANGE_VALUE:
+		return mpz_set(rop, expr->range.high);
 	case EXPR_PREFIX:
 		range_expr_value_low(rop, expr->prefix);
 		assert(expr->len >= expr->prefix_len);
@@ -1616,6 +1700,7 @@ static const struct expr_ops *__expr_ops_by_type(enum expr_types etype)
 	case EXPR_XFRM: return &xfrm_expr_ops;
 	case EXPR_SET_ELEM_CATCHALL: return &set_elem_catchall_expr_ops;
 	case EXPR_FLAGCMP: return &flagcmp_expr_ops;
+	case EXPR_RANGE_VALUE: return &constant_range_expr_ops;
 	}
 
 	return NULL;
diff --git a/src/intervals.c b/src/intervals.c
index 6308cc8e2c08..c46874d9a6ce 100644
--- a/src/intervals.c
+++ b/src/intervals.c
@@ -17,15 +17,24 @@ static void set_to_range(struct expr *init);
 
 static void setelem_expr_to_range(struct expr *expr)
 {
-	unsigned char data[sizeof(struct in6_addr) * BITS_PER_BYTE];
-	struct expr *key, *value;
+	struct expr *key;
 	mpz_t rop;
 
 	assert(expr->etype == EXPR_SET_ELEM);
 
 	switch (expr->key->etype) {
 	case EXPR_SET_ELEM_CATCHALL:
+	case EXPR_RANGE_VALUE:
+		break;
 	case EXPR_RANGE:
+		key = constant_range_expr_alloc(&expr->location,
+						expr->key->dtype,
+						expr->key->byteorder,
+						expr->key->len,
+						expr->key->left->value,
+						expr->key->right->value);
+		expr_free(expr->key);
+		expr->key = key;
 		break;
 	case EXPR_PREFIX:
 		if (expr->key->prefix->etype != EXPR_VALUE)
@@ -37,16 +46,13 @@ static void setelem_expr_to_range(struct expr *expr)
 			mpz_switch_byteorder(expr->key->prefix->value, expr->len / BITS_PER_BYTE);
 
 		mpz_ior(rop, rop, expr->key->prefix->value);
-	        mpz_export_data(data, rop, expr->key->prefix->byteorder,
-				expr->key->prefix->len / BITS_PER_BYTE);
+		key = constant_range_expr_alloc(&expr->location,
+						expr->key->dtype,
+						expr->key->byteorder,
+						expr->key->len,
+						expr->key->prefix->value,
+						rop);
 		mpz_clear(rop);
-		value = constant_expr_alloc(&expr->location,
-					    expr->key->prefix->dtype,
-					    expr->key->prefix->byteorder,
-					    expr->key->prefix->len, data);
-		key = range_expr_alloc(&expr->location,
-				       expr_get(expr->key->prefix),
-				       value);
 		expr_free(expr->key);
 		expr->key = key;
 		break;
@@ -54,9 +60,12 @@ static void setelem_expr_to_range(struct expr *expr)
 		if (expr_basetype(expr)->type == TYPE_STRING)
 			mpz_switch_byteorder(expr->key->value, expr->len / BITS_PER_BYTE);
 
-		key = range_expr_alloc(&expr->location,
-				       expr_clone(expr->key),
-				       expr_get(expr->key));
+		key = constant_range_expr_alloc(&expr->location,
+						expr->key->dtype,
+						expr->key->byteorder,
+						expr->key->len,
+						expr->key->value,
+						expr->key->value);
 		expr_free(expr->key);
 		expr->key = key;
 		break;
@@ -76,8 +85,8 @@ static void purge_elem(struct set_automerge_ctx *ctx, struct expr *i)
 {
 	if (ctx->debug_mask & NFT_DEBUG_SEGTREE) {
 		pr_gmp_debug("remove: [%Zx-%Zx]\n",
-			     i->key->left->value,
-			     i->key->right->value);
+			     i->key->range.low,
+			     i->key->range.high);
 	}
 	list_move_tail(&i->list, &ctx->purge->expressions);
 }
@@ -107,19 +116,16 @@ static bool merge_ranges(struct set_automerge_ctx *ctx,
 	if (prev->flags & EXPR_F_KERNEL) {
 		prev->location = i->location;
 		purge_elem(ctx, prev);
-		expr_free(i->key->left);
-		i->key->left = expr_get(prev->key->left);
+		mpz_set(i->key->range.low, prev->key->range.low);
 		mpz_set(prev_range->high, range->high);
 		return true;
 	} else if (i->flags & EXPR_F_KERNEL) {
 		i->location = prev->location;
 		purge_elem(ctx, i);
-		expr_free(prev->key->right);
-		prev->key->right = expr_get(i->key->right);
+		mpz_set(prev->key->range.high, i->key->range.high);
 		mpz_set(prev_range->high, range->high);
 	} else {
-		expr_free(prev->key->right);
-		prev->key->right = expr_get(i->key->right);
+		mpz_set(prev->key->range.high, i->key->range.high);
 		mpz_set(prev_range->high, range->high);
 		list_del(&i->list);
 		expr_free(i);
@@ -156,6 +162,8 @@ static void set_prev_elem(struct expr **prev, struct expr *i,
 	mpz_set(prev_range->high, range->high);
 }
 
+static struct expr *interval_expr_key(struct expr *i);
+
 static void setelem_automerge(struct set_automerge_ctx *ctx)
 {
 	struct expr *i, *next, *prev = NULL;
@@ -270,7 +278,7 @@ int set_automerge(struct list_head *msgs, struct cmd *cmd, struct set *set,
 		} else if (existing_set) {
 			if (debug_mask & NFT_DEBUG_SEGTREE) {
 				pr_gmp_debug("add: [%Zx-%Zx]\n",
-					     i->key->left->value, i->key->right->value);
+					     i->key->range.low, i->key->range.high);
 			}
 			clone = expr_clone(i);
 			clone->flags |= EXPR_F_KERNEL;
@@ -304,9 +312,8 @@ static void remove_elem(struct expr *prev, struct set *set, struct expr *purge)
 static void __adjust_elem_left(struct set *set, struct expr *prev, struct expr *i)
 {
 	prev->flags &= ~EXPR_F_KERNEL;
-	expr_free(prev->key->left);
-	prev->key->left = expr_get(i->key->right);
-	mpz_add_ui(prev->key->left->value, prev->key->left->value, 1);
+	mpz_set(prev->key->range.low, i->key->range.high);
+	mpz_add_ui(prev->key->range.low, prev->key->range.low, 1);
 	list_move(&prev->list, &set->existing_set->init->expressions);
 }
 
@@ -324,9 +331,8 @@ static void adjust_elem_left(struct set *set, struct expr *prev, struct expr *i,
 static void __adjust_elem_right(struct set *set, struct expr *prev, struct expr *i)
 {
 	prev->flags &= ~EXPR_F_KERNEL;
-	expr_free(prev->key->right);
-	prev->key->right = expr_get(i->key->left);
-	mpz_sub_ui(prev->key->right->value, prev->key->right->value, 1);
+	mpz_set(prev->key->range.high, i->key->range.low);
+	mpz_sub_ui(prev->key->range.high, prev->key->range.high, 1);
 	list_move(&prev->list, &set->existing_set->init->expressions);
 }
 
@@ -355,14 +361,12 @@ static void split_range(struct set *set, struct expr *prev, struct expr *i,
 
 	prev->flags &= ~EXPR_F_KERNEL;
 	clone = expr_clone(prev);
-	expr_free(clone->key->left);
-	clone->key->left = expr_get(i->key->right);
-	mpz_add_ui(clone->key->left->value, i->key->right->value, 1);
+	mpz_set(clone->key->range.low, i->key->range.high);
+	mpz_add_ui(clone->key->range.low, i->key->range.high, 1);
 	list_add_tail(&clone->list, &set->existing_set->init->expressions);
 
-	expr_free(prev->key->right);
-	prev->key->right = expr_get(i->key->left);
-	mpz_sub_ui(prev->key->right->value, i->key->left->value, 1);
+	mpz_set(prev->key->range.high, i->key->range.low);
+	mpz_sub_ui(prev->key->range.high, i->key->range.low, 1);
 	list_move(&prev->list, &set->existing_set->init->expressions);
 
 	list_del(&i->list);
@@ -535,13 +539,13 @@ int set_delete(struct list_head *msgs, struct cmd *cmd, struct set *set,
 	if (debug_mask & NFT_DEBUG_SEGTREE) {
 		list_for_each_entry(i, &init->expressions, list)
 			pr_gmp_debug("remove: [%Zx-%Zx]\n",
-				     i->key->left->value, i->key->right->value);
+				     i->key->range.low, i->key->range.high);
 		list_for_each_entry(i, &add->expressions, list)
 			pr_gmp_debug("add: [%Zx-%Zx]\n",
-				     i->key->left->value, i->key->right->value);
+				     i->key->range.low, i->key->range.high);
 		list_for_each_entry(i, &existing_set->init->expressions, list)
 			pr_gmp_debug("existing: [%Zx-%Zx]\n",
-				     i->key->left->value, i->key->right->value);
+				     i->key->range.low, i->key->range.high);
 	}
 
 	if (list_empty(&add->expressions)) {
@@ -696,7 +700,7 @@ int set_to_intervals(const struct set *set, struct expr *init, bool add)
 			continue;
 
 		if (!prev && segtree_needs_first_segment(set, init, add) &&
-		    mpz_cmp_ui(elem->key->left->value, 0)) {
+		    mpz_cmp_ui(elem->key->range.low, 0)) {
 			mpz_set_ui(p, 0);
 			expr = constant_expr_alloc(&internal_location,
 						   set->key->dtype,
@@ -720,15 +724,15 @@ int set_to_intervals(const struct set *set, struct expr *init, bool add)
 				mpz_switch_byteorder(p, set->key->len / BITS_PER_BYTE);
 
 			if (!(set->flags & NFT_SET_ANONYMOUS) ||
-			    mpz_cmp(p, elem->key->left->value) != 0)
+			    mpz_cmp(p, elem->key->range.low) != 0)
 				list_add_tail(&newelem->list, &intervals);
 			else
 				expr_free(newelem);
 		}
 		newelem = NULL;
 
-		if (mpz_scan0(elem->key->right->value, 0) != set->key->len) {
-			mpz_add_ui(p, elem->key->right->value, 1);
+		if (mpz_scan0(elem->key->range.high, 0) != set->key->len) {
+			mpz_add_ui(p, elem->key->range.high, 1);
 			expr = constant_expr_alloc(&elem->key->location, set->key->dtype,
 						   set->key->byteorder, set->key->len,
 						   NULL);
@@ -750,7 +754,7 @@ int set_to_intervals(const struct set *set, struct expr *init, bool add)
 		expr = constant_expr_alloc(&elem->key->location, set->key->dtype,
 					   set->key->byteorder, set->key->len, NULL);
 
-		mpz_set(expr->value, elem->key->left->value);
+		mpz_set(expr->value, elem->key->range.low);
 		if (set->key->byteorder == BYTEORDER_HOST_ENDIAN)
 			mpz_switch_byteorder(expr->value, set->key->len / BITS_PER_BYTE);
 
diff --git a/src/mergesort.c b/src/mergesort.c
index 5e676be16369..0452d60ad42b 100644
--- a/src/mergesort.c
+++ b/src/mergesort.c
@@ -38,6 +38,8 @@ static mpz_srcptr expr_msort_value(const struct expr *expr, mpz_t value)
 		return expr_msort_value(expr->left, value);
 	case EXPR_VALUE:
 		return expr->value;
+	case EXPR_RANGE_VALUE:
+		return expr->range.low;
 	case EXPR_CONCAT:
 		concat_expr_msort_value(expr, value);
 		break;
-- 
2.30.2

[PATCH nft 4/6] rule: constify set_is_non_concat_range()

[Pablo Neira Ayuso]

This is read-only, constify it.

Signed-off-by: Pablo Neira Ayuso <pablo@netfilter.org>
---
 include/rule.h | 2 +-
 1 file changed, 1 insertion(+), 1 deletion(-)

diff --git a/include/rule.h b/include/rule.h
index 238be23eca90..86477c709544 100644
--- a/include/rule.h
+++ b/include/rule.h
@@ -423,7 +423,7 @@ static inline bool set_is_interval(uint32_t set_flags)
 	return set_flags & NFT_SET_INTERVAL;
 }
 
-static inline bool set_is_non_concat_range(struct set *s)
+static inline bool set_is_non_concat_range(const struct set *s)
 {
 	return (s->flags & NFT_SET_INTERVAL) && s->desc.field_count <= 1;
 }
-- 
2.30.2

[PATCH nft 5/6] mnl: rename list of expression in mnl_nft_setelem_batch()

[Pablo Neira Ayuso]

Rename set to init to prepare to pass struct set to this function in
the follow up patch. No functional changes are intended.

Signed-off-by: Pablo Neira Ayuso <pablo@netfilter.org>
---
 src/mnl.c | 12 ++++++------
 1 file changed, 6 insertions(+), 6 deletions(-)

diff --git a/src/mnl.c b/src/mnl.c
index 88fac5bd0393..52085d6d960a 100644
--- a/src/mnl.c
+++ b/src/mnl.c
@@ -1731,7 +1731,7 @@ static int mnl_nft_setelem_batch(const struct nftnl_set *nls, struct cmd *cmd,
 				 struct nftnl_batch *batch,
 				 enum nf_tables_msg_types msg_type,
 				 unsigned int flags, uint32_t *seqnum,
-				 const struct expr *set,
+				 const struct expr *init,
 				 struct netlink_ctx *ctx)
 {
 	struct nlattr *nest1, *nest2;
@@ -1743,8 +1743,8 @@ static int mnl_nft_setelem_batch(const struct nftnl_set *nls, struct cmd *cmd,
 	if (msg_type == NFT_MSG_NEWSETELEM)
 		flags |= NLM_F_CREATE;
 
-	if (set)
-		expr = list_first_entry(&set->expressions, struct expr, list);
+	if (init)
+		expr = list_first_entry(&init->expressions, struct expr, list);
 
 next:
 	nlh = nftnl_nlmsg_build_hdr(nftnl_batch_buffer(batch), msg_type,
@@ -1764,13 +1764,13 @@ next:
 				 htonl(nftnl_set_get_u32(nls, NFTNL_SET_ID)));
 	}
 
-	if (!set || list_empty(&set->expressions))
+	if (!init || list_empty(&init->expressions))
 		return 0;
 
 	assert(expr);
 	nest1 = mnl_attr_nest_start(nlh, NFTA_SET_ELEM_LIST_ELEMENTS);
-	list_for_each_entry_from(expr, &set->expressions, list) {
-		nlse = alloc_nftnl_setelem(set, expr);
+	list_for_each_entry_from(expr, &init->expressions, list) {
+		nlse = alloc_nftnl_setelem(init, expr);
 
 		cmd_add_loc(cmd, nlh, &expr->location);
 		nest2 = mnl_attr_nest_start(nlh, ++i);
-- 
2.30.2

[PATCH nft 6/6] src: rework singleton interval transformation to reduce memory consumption

[Pablo Neira Ayuso]

set_to_intervals() expands range expressions into a list of singleton
elements before building the netlink message that is sent to userspace.
This is because the kernel expects this list of singleton elements where
EXPR_F_INTERVAL_END denotes a closing interval. This expansion
significantly increases memory consumption in userspace.

This patch updates the logic to transform the range expression up to two
temporary singleton element expressions through setelem_to_interval().
Then, these two elements are used to allocate the nftnl_set_elem objects
through alloc_nftnl_setelem_interval() to build the netlink message,
finally all these temporary objects are released.

After this update, set_to_intervals() only deals with adding the
non-matching all zero element to the interval set when it is not there
as the kernel expects. The set size used to be monotonically incremented
from set_to_intervals() during the expansion from range to singleton
elements. After this patch, mnl_nft_set_add() calculates the set size
based on the expansion to individual elements.

In combination with the new EXPR_RANGE_VALUE expression, this shrinks
runtime userspace memory consumption from 70.50 Mbytes to 43.38 Mbytes
for a 100k intervals set sample.

Signed-off-by: Pablo Neira Ayuso <pablo@netfilter.org>
---
 include/intervals.h |   2 +
 include/list.h      |   8 ++
 include/mnl.h       |   3 +-
 src/intervals.c     | 180 ++++++++++++++++++++++++++------------------
 src/mnl.c           |  73 ++++++++++++++++--
 src/rule.c          |   4 +-
 6 files changed, 185 insertions(+), 85 deletions(-)

diff --git a/include/intervals.h b/include/intervals.h
index ef0fb53e7577..e71238abe238 100644
--- a/include/intervals.h
+++ b/include/intervals.h
@@ -7,5 +7,7 @@ int set_delete(struct list_head *msgs, struct cmd *cmd, struct set *set,
 	       struct expr *init, unsigned int debug_mask);
 int set_overlap(struct list_head *msgs, struct set *set, struct expr *init);
 int set_to_intervals(const struct set *set, struct expr *init, bool add);
+int setelem_to_interval(const struct set *set, struct expr *elem,
+			struct list_head *interval_list);
 
 #endif
diff --git a/include/list.h b/include/list.h
index 37fbe3e275cc..4382a67005e8 100644
--- a/include/list.h
+++ b/include/list.h
@@ -348,6 +348,14 @@ static inline void list_splice_tail_init(struct list_head *list,
 #define list_first_entry(ptr, type, member) \
 	list_entry((ptr)->next, type, member)
 
+/**
+ * list_prev_entry - get the prev element in list
+ * @ptr:        the type * to cursor
+ * @member:     the name of the list_head within the struct.
+ */
+#define list_prev_entry(ptr, member) \
+        list_entry((ptr)->member.prev, typeof(*(ptr)), member)
+
 /**
  * list_last_entry - get the last element from a list
  * @ptr:        the list head to take the element from.
diff --git a/include/mnl.h b/include/mnl.h
index 7c465d4426c4..f50ac644ccb9 100644
--- a/include/mnl.h
+++ b/include/mnl.h
@@ -66,7 +66,8 @@ int mnl_nft_setelem_add(struct netlink_ctx *ctx, struct cmd *cmd,
 			const struct set *set, const struct expr *expr,
 			unsigned int flags);
 int mnl_nft_setelem_del(struct netlink_ctx *ctx, struct cmd *cmd,
-			const struct handle *h, const struct expr *init);
+			const struct handle *h, const struct set *set,
+			const struct expr *init);
 int mnl_nft_setelem_flush(struct netlink_ctx *ctx, const struct cmd *cmd);
 int mnl_nft_setelem_get(struct netlink_ctx *ctx, struct nftnl_set *nls,
 			bool reset);
diff --git a/src/intervals.c b/src/intervals.c
index c46874d9a6ce..c9dfed5e550e 100644
--- a/src/intervals.c
+++ b/src/intervals.c
@@ -683,97 +683,129 @@ static bool segtree_needs_first_segment(const struct set *set,
 
 int set_to_intervals(const struct set *set, struct expr *init, bool add)
 {
-	struct expr *i, *n, *prev = NULL, *elem, *newelem = NULL, *root, *expr;
+	struct expr *i, *elem, *root, *expr;
 	LIST_HEAD(intervals);
-	uint32_t flags;
-	mpz_t p, q;
+	mpz_t p;
 
-	mpz_init2(p, set->key->len);
-	mpz_init2(q, set->key->len);
+	if (list_empty(&init->expressions))
+		return 0;
 
-	list_for_each_entry_safe(i, n, &init->expressions, list) {
-		flags = 0;
+	i = list_first_entry(&init->expressions, struct expr, list);
+	if (!i)
+		return 0;
 
-		elem = interval_expr_key(i);
+	elem = interval_expr_key(i);
 
-		if (elem->key->etype == EXPR_SET_ELEM_CATCHALL)
-			continue;
+	if (elem->key->etype == EXPR_SET_ELEM_CATCHALL)
+		return 0;
 
-		if (!prev && segtree_needs_first_segment(set, init, add) &&
-		    mpz_cmp_ui(elem->key->range.low, 0)) {
-			mpz_set_ui(p, 0);
-			expr = constant_expr_alloc(&internal_location,
-						   set->key->dtype,
-						   set->key->byteorder,
-						   set->key->len, NULL);
-			mpz_set(expr->value, p);
-			root = set_elem_expr_alloc(&internal_location, expr);
-			if (i->etype == EXPR_MAPPING) {
-				root = mapping_expr_alloc(&internal_location,
-							  root,
-							  expr_get(i->right));
-			}
-			root->flags |= EXPR_F_INTERVAL_END;
-			list_add(&root->list, &intervals);
-			init->size++;
+	if (segtree_needs_first_segment(set, init, add) &&
+	    mpz_cmp_ui(elem->key->range.low, 0)) {
+		mpz_init2(p, set->key->len);
+		mpz_set_ui(p, 0);
+		expr = constant_range_expr_alloc(&internal_location,
+						 set->key->dtype,
+						 set->key->byteorder,
+					         set->key->len, p, p);
+		mpz_clear(p);
+
+		root = set_elem_expr_alloc(&internal_location, expr);
+		if (i->etype == EXPR_MAPPING) {
+			root = mapping_expr_alloc(&internal_location,
+						  root,
+						  expr_get(i->right));
 		}
+		root->flags |= EXPR_F_INTERVAL_END;
+		list_add(&root->list, &intervals);
+	}
 
-		if (newelem) {
-			mpz_set(p, interval_expr_key(newelem)->key->value);
-			if (set->key->byteorder == BYTEORDER_HOST_ENDIAN)
-				mpz_switch_byteorder(p, set->key->len / BITS_PER_BYTE);
+	list_splice_init(&intervals, &init->expressions);
 
-			if (!(set->flags & NFT_SET_ANONYMOUS) ||
-			    mpz_cmp(p, elem->key->range.low) != 0)
-				list_add_tail(&newelem->list, &intervals);
-			else
-				expr_free(newelem);
-		}
-		newelem = NULL;
-
-		if (mpz_scan0(elem->key->range.high, 0) != set->key->len) {
-			mpz_add_ui(p, elem->key->range.high, 1);
-			expr = constant_expr_alloc(&elem->key->location, set->key->dtype,
-						   set->key->byteorder, set->key->len,
-						   NULL);
-			mpz_set(expr->value, p);
-			if (set->key->byteorder == BYTEORDER_HOST_ENDIAN)
-				mpz_switch_byteorder(expr->value, set->key->len / BITS_PER_BYTE);
-
-			newelem = set_elem_expr_alloc(&expr->location, expr);
-			if (i->etype == EXPR_MAPPING) {
-				newelem = mapping_expr_alloc(&expr->location,
-							     newelem,
-							     expr_get(i->right));
-			}
-			newelem->flags |= EXPR_F_INTERVAL_END;
-		} else {
-			flags = EXPR_F_INTERVAL_OPEN;
-		}
+	return 0;
+}
+
+static void set_elem_stmt_clone(struct expr *dst, const struct expr *src)
+{
+	struct stmt *stmt, *nstmt;
+
+	list_for_each_entry(stmt, &src->stmt_list, list) {
+		nstmt = xzalloc(sizeof(*stmt));
+		/* this is fine by now for the supported stateful statements. */
+		*nstmt = *stmt;
+		list_add_tail(&nstmt->list, &dst->stmt_list);
+	}
+}
 
-		expr = constant_expr_alloc(&elem->key->location, set->key->dtype,
-					   set->key->byteorder, set->key->len, NULL);
+static void set_elem_expr_copy(struct expr *dst, const struct expr *src)
+{
+	if (src->comment)
+		dst->comment = xstrdup(src->comment);
+	if (src->timeout)
+		dst->timeout = src->timeout;
+	if (src->expiration)
+		dst->expiration = src->expiration;
+
+	set_elem_stmt_clone(dst, src);
+}
 
-		mpz_set(expr->value, elem->key->range.low);
-		if (set->key->byteorder == BYTEORDER_HOST_ENDIAN)
-			mpz_switch_byteorder(expr->value, set->key->len / BITS_PER_BYTE);
+int setelem_to_interval(const struct set *set, struct expr *elem,
+			struct list_head *intervals)
+{
+	struct expr *key, *low, *high;
 
-		expr_free(elem->key);
-		elem->key = expr;
-		i->flags |= flags;
-		init->size++;
-		list_move_tail(&i->list, &intervals);
+	switch (elem->etype) {
+	case EXPR_MAPPING:
+		key = elem->left->key;
+		break;
+	case EXPR_SET_ELEM:
+		key = elem->key;
+		break;
+	default:
+		BUG("unhandled expression type %d\n", elem->etype);
+		return -1;
+	}
 
-		prev = i;
+	if (key->etype == EXPR_SET_ELEM_CATCHALL)
+		return 0;
+
+	assert(key->etype == EXPR_RANGE_VALUE);
+
+	low = constant_expr_alloc(&key->location, set->key->dtype,
+				  set->key->byteorder, set->key->len, NULL);
+
+	mpz_set(low->value, key->range.low);
+	if (set->key->byteorder == BYTEORDER_HOST_ENDIAN)
+		mpz_switch_byteorder(low->value, set->key->len / BITS_PER_BYTE);
+
+	low = set_elem_expr_alloc(&key->location, low);
+	set_elem_expr_copy(low, interval_expr_key(elem));
+
+	if (elem->etype == EXPR_MAPPING)
+		low = mapping_expr_alloc(&elem->location,
+					 low, expr_get(elem->right));
+
+	list_add_tail(&low->list, intervals);
+
+	if (!mpz_cmp_ui(key->range.high, 0)) {
+		low->flags |= EXPR_F_INTERVAL_END;
+		return 0;
+	} else if (mpz_scan0(key->range.high, 0) == set->key->len) {
+		low->flags |= EXPR_F_INTERVAL_OPEN;
+		return 0;
 	}
 
-	if (newelem)
-		list_add_tail(&newelem->list, &intervals);
+	high = constant_expr_alloc(&key->location, set->key->dtype,
+				   set->key->byteorder, set->key->len,
+				   NULL);
+	mpz_set(high->value, key->range.high);
+	mpz_add_ui(high->value, high->value, 1);
+	if (set->key->byteorder == BYTEORDER_HOST_ENDIAN)
+		mpz_switch_byteorder(high->value, set->key->len / BITS_PER_BYTE);
 
-	list_splice_init(&intervals, &init->expressions);
+	high = set_elem_expr_alloc(&key->location, high);
 
-	mpz_clear(p);
-	mpz_clear(q);
+	high->flags |= EXPR_F_INTERVAL_END;
+	list_add_tail(&high->list, intervals);
 
 	return 0;
 }
diff --git a/src/mnl.c b/src/mnl.c
index 52085d6d960a..1124fecbbd90 100644
--- a/src/mnl.c
+++ b/src/mnl.c
@@ -30,6 +30,7 @@
 
 #include <mnl.h>
 #include <cmd.h>
+#include <intervals.h>
 #include <net/if.h>
 #include <sys/socket.h>
 #include <arpa/inet.h>
@@ -1266,7 +1267,14 @@ int mnl_nft_set_add(struct netlink_ctx *ctx, struct cmd *cmd,
 			nftnl_set_set_u32(nls, NFTNL_SET_DESC_SIZE,
 					  set->desc.size);
 	} else if (set->init) {
-		nftnl_set_set_u32(nls, NFTNL_SET_DESC_SIZE, set->init->size);
+		unsigned int size;
+
+		if (set_is_non_concat_range(set))
+			size = (set->init->size * 2) + 1;
+		else
+			size = set->init->size;
+
+		nftnl_set_set_u32(nls, NFTNL_SET_DESC_SIZE, size);
 	}
 
 	udbuf = nftnl_udata_buf_alloc(NFT_USERDATA_MAXLEN);
@@ -1727,17 +1735,46 @@ static void netlink_dump_setelem_done(struct netlink_ctx *ctx)
 	fprintf(fp, "\n");
 }
 
+static struct nftnl_set_elem *
+alloc_nftnl_setelem_interval(const struct set *set, const struct expr *init,
+			     struct expr *elem,
+			     struct nftnl_set_elem **nlse_high)
+{
+	struct nftnl_set_elem *nlse[2] = {};
+	LIST_HEAD(interval_list);
+	struct expr *expr, *next;
+	int i = 0;
+
+	if (setelem_to_interval(set, elem, &interval_list) < 0)
+		memory_allocation_error();
+
+	if (list_empty(&interval_list)) {
+		*nlse_high = NULL;
+		nlse[i++] = alloc_nftnl_setelem(init, elem);
+		return nlse[0];
+	}
+
+	list_for_each_entry_safe(expr, next, &interval_list, list) {
+		nlse[i++] = alloc_nftnl_setelem(init, expr);
+		list_del(&expr->list);
+		expr_free(expr);
+	}
+	*nlse_high = nlse[1];
+
+	return nlse[0];
+}
+
 static int mnl_nft_setelem_batch(const struct nftnl_set *nls, struct cmd *cmd,
 				 struct nftnl_batch *batch,
 				 enum nf_tables_msg_types msg_type,
 				 unsigned int flags, uint32_t *seqnum,
-				 const struct expr *init,
+				 const struct set *set, const struct expr *init,
 				 struct netlink_ctx *ctx)
 {
+	struct nftnl_set_elem *nlse, *nlse_high = NULL;
 	struct nlattr *nest1, *nest2;
-	struct nftnl_set_elem *nlse;
-	struct nlmsghdr *nlh;
 	struct expr *expr = NULL;
+	struct nlmsghdr *nlh;
 	int i = 0;
 
 	if (msg_type == NFT_MSG_NEWSETELEM)
@@ -1770,9 +1807,24 @@ next:
 	assert(expr);
 	nest1 = mnl_attr_nest_start(nlh, NFTA_SET_ELEM_LIST_ELEMENTS);
 	list_for_each_entry_from(expr, &init->expressions, list) {
-		nlse = alloc_nftnl_setelem(init, expr);
+
+		if (set_is_non_concat_range(set)) {
+			if (!nlse_high) {
+				nlse = alloc_nftnl_setelem_interval(set, init, expr, &nlse_high);
+			} else {
+				nlse = nlse_high;
+				nlse_high = NULL;
+			}
+		} else {
+			nlse = alloc_nftnl_setelem(init, expr);
+		}
 
 		cmd_add_loc(cmd, nlh, &expr->location);
+
+		/* rewind one step, range high still needs to be added. */
+		if (nlse_high)
+			expr = list_prev_entry(expr, list);
+
 		nest2 = mnl_attr_nest_start(nlh, ++i);
 		nftnl_set_elem_nlmsg_build_payload(nlh, nlse);
 		mnl_attr_nest_end(nlh, nest2);
@@ -1780,6 +1832,10 @@ next:
 		netlink_dump_setelem(nlse, ctx);
 		nftnl_set_elem_free(nlse);
 		if (mnl_nft_attr_nest_overflow(nlh, nest1, nest2)) {
+			if (nlse_high) {
+				nftnl_set_elem_free(nlse_high);
+				nlse_high = NULL;
+			}
 			mnl_attr_nest_end(nlh, nest1);
 			mnl_nft_batch_continue(batch);
 			mnl_seqnum_inc(seqnum);
@@ -1817,7 +1873,7 @@ int mnl_nft_setelem_add(struct netlink_ctx *ctx, struct cmd *cmd,
 	netlink_dump_set(nls, ctx);
 
 	err = mnl_nft_setelem_batch(nls, cmd, ctx->batch, NFT_MSG_NEWSETELEM,
-				    flags, &ctx->seqnum, expr, ctx);
+				    flags, &ctx->seqnum, set, expr, ctx);
 	nftnl_set_free(nls);
 
 	return err;
@@ -1854,7 +1910,8 @@ int mnl_nft_setelem_flush(struct netlink_ctx *ctx, const struct cmd *cmd)
 }
 
 int mnl_nft_setelem_del(struct netlink_ctx *ctx, struct cmd *cmd,
-			const struct handle *h, const struct expr *init)
+			const struct handle *h, const struct set *set,
+			const struct expr *init)
 {
 	enum nf_tables_msg_types msg_type = NFT_MSG_DELSETELEM;
 	struct nftnl_set *nls;
@@ -1877,7 +1934,7 @@ int mnl_nft_setelem_del(struct netlink_ctx *ctx, struct cmd *cmd,
 		msg_type = NFT_MSG_DESTROYSETELEM;
 
 	err = mnl_nft_setelem_batch(nls, cmd, ctx->batch, msg_type, 0,
-				    &ctx->seqnum, init, ctx);
+				    &ctx->seqnum, set, init, ctx);
 	nftnl_set_free(nls);
 
 	return err;
diff --git a/src/rule.c b/src/rule.c
index 151ed531969c..b897a15fcdf1 100644
--- a/src/rule.c
+++ b/src/rule.c
@@ -1550,14 +1550,14 @@ static int do_command_insert(struct netlink_ctx *ctx, struct cmd *cmd)
 
 static int do_delete_setelems(struct netlink_ctx *ctx, struct cmd *cmd)
 {
+	const struct set *set = cmd->elem.set;
 	struct expr *expr = cmd->elem.expr;
-	struct set *set = cmd->elem.set;
 
 	if (set_is_non_concat_range(set) &&
 	    set_to_intervals(set, expr, false) < 0)
 		return -1;
 
-	if (mnl_nft_setelem_del(ctx, cmd, &cmd->handle, cmd->elem.expr) < 0)
+	if (mnl_nft_setelem_del(ctx, cmd, &cmd->handle, set, cmd->elem.expr) < 0)
 		return -1;
 
 	return 0;
-- 
2.30.2