Skip to contentSkip to conversation

shrink memory usage for interval sets

PATCH Superseded Pablo Neira Ayuso 1 participant 7 messages Dec 17, 2024 netfilter

v1 of 2 Superseded Latest is v2 →

lore
Share & tools
lore

Pablo Neira Ayuso

author maintainer
#0 lore raw

cover shrink memory usage for interval sets

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(-)
Signature · 1 line
2.30.2
author maintainer
#1 lore raw

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

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

---
 src/intervals.c | 16 ++++++++++------
 1 file changed, 10 insertions(+), 6 deletions(-)
src/intervals.c +10 -6
index 12cccbdab752..44fdda36e35f 100644
@@ -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);
Signature · 1 line
2.30.2
author maintainer
#2 lore raw

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

In reply to 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")
---
 src/intervals.c | 4 +++-
 1 file changed, 3 insertions(+), 1 deletion(-)
src/intervals.c +3 -1
index 44fdda36e35f..6308cc8e2c08 100644
@@ -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;
 		}
Signature · 1 line
2.30.2
author maintainer
#3 lore raw

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

In reply to 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.

---
 include/expression.h | 13 +++++++
 src/expression.c     | 85 +++++++++++++++++++++++++++++++++++++++++
 src/intervals.c      | 90 +++++++++++++++++++++++---------------------
 src/mergesort.c      |  2 +
 4 files changed, 147 insertions(+), 43 deletions(-)
include/expression.h +13 -0
index 877887ff1978..f2b45250872d 100644
@@ -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,
src/expression.c +85 -0

109 lines not on this page · raw message

src/intervals.c +47 -43

201 lines not on this page · raw message

src/mergesort.c +2 -0
index 5e676be16369..0452d60ad42b 100644
@@ -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;
Signature · 1 line
2.30.2
author maintainer
#4 lore raw

PATCH 4/6 rule: constify set_is_non_concat_range()

In reply to Pablo Neira Ayuso

This is read-only, constify it.

---
 include/rule.h | 2 +-
 1 file changed, 1 insertion(+), 1 deletion(-)
include/rule.h +1 -1
index 238be23eca90..86477c709544 100644
@@ -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;
 }
Signature · 1 line
2.30.2
author maintainer
#5 lore raw

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

In reply to 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.

---
 src/mnl.c | 12 ++++++------
 1 file changed, 6 insertions(+), 6 deletions(-)
src/mnl.c +6 -6
index 88fac5bd0393..52085d6d960a 100644
@@ -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);
Signature · 1 line
2.30.2
author maintainer
#6 lore raw

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

In reply to 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.

---
 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(-)
include/intervals.h +2 -0
index ef0fb53e7577..e71238abe238 100644
@@ -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
include/list.h +8 -0
index 37fbe3e275cc..4382a67005e8 100644
@@ -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.
include/mnl.h +2 -1
index 7c465d4426c4..f50ac644ccb9 100644
@@ -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);
src/intervals.c +106 -74

203 lines not on this page · raw message

src/mnl.c +65 -8

131 lines not on this page · raw message

src/rule.c +2 -2
index 151ed531969c..b897a15fcdf1 100644
@@ -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;
Signature · 1 line
2.30.2