Skip to contentSkip to conversation

intervals: add helper function to set previous element

PATCH New Pablo Neira Ayuso 1 participant 7 messages Jan 3, 2025 netfilter

lore
Share & tools
lore

Pablo Neira Ayuso

author maintainer
#0 lore raw

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

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

---
v2: no changes

 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
#1 lore raw

PATCH v2 2/7 intervals: do not merge intervals with different timeout

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

Fixes 81e36530fcac ("src: replace interval segment tree overlap and automerge")

---
v2: missing forward declaration, otherwise patch breaks bisection.

 src/intervals.c | 6 +++++-
 1 file changed, 5 insertions(+), 1 deletion(-)
src/intervals.c +5 -1
index 44fdda36e35f..ffd474fd595e 100644
@@ -156,6 +156,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;
@@ -175,7 +177,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
#2 lore raw

PATCH v2 3/7 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.

---
v2: add constant_range_expr_print_one() and use it.

 include/expression.h | 13 +++++++
 src/expression.c     | 83 +++++++++++++++++++++++++++++++++++++++++
 src/intervals.c      | 88 ++++++++++++++++++++++----------------------
 src/mergesort.c      |  2 +
 4 files changed, 143 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 +83 -0

107 lines not on this page · raw message

src/intervals.c +45 -43

193 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
#3 lore raw

PATCH v2 4/7 rule: constify set_is_non_concat_range()

In reply to Pablo Neira Ayuso

This is read-only, constify it.

---
v2: no changes

 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
#4 lore raw

PATCH v2 5/7 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.

---
v2: no changes.

 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
#5 lore raw

PATCH v2 6/7 mnl: do not send set size when set is constant set

In reply to Pablo Neira Ayuso

When turning element range into the interval representation based on singleton elements for the rbtree tree set backend, userspace adjusts the size to the internal kernel implementation.

For constant sets, this is leaking an internal kernel implementation detail that is fixed by kernel patch ("netfilter: nf_tables: fix set size with rbtree backend"). For non-constant sets, set size is just broken.

This patch is required by the follow up patch ("src: rework singleton interval transformation to reduce memory consumption").

On top of this, constant sets cannot be updated once they are bound, set size is not useful in this case. Remove this implicit set size for constant sets.

---
v2: new in this series.

 src/mnl.c | 2 --
 1 file changed, 2 deletions(-)
src/mnl.c +0 -2
index 52085d6d960a..5983fd468e56 100644
@@ -1265,8 +1265,6 @@ int mnl_nft_set_add(struct netlink_ctx *ctx, struct cmd *cmd,
 		if (set->desc.size != 0)
 			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);
 	}
 
 	udbuf = nftnl_udata_buf_alloc(NFT_USERDATA_MAXLEN);
Signature · 1 line
2.30.2
author maintainer
#6 lore raw

PATCH v2 7/7 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. For anonymous sets, when adjacent ranges are found, the end element is not added to the set to pack the set representation as in the original set_to_intervals() routine.

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.

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.

---
v2: - restore set_to_intervals() to use loop to iterate elements.
- added handling to pack adjacents ranges in anonymous sets for mnl_nft_setelem_batch() and setelem_to_interval().
- fix handling of all-zero never-match element in setelem_to_interval() leading to bogus zero element in set.

 include/intervals.h |   2 +
 include/list.h      |   8 ++
 include/mnl.h       |   3 +-
 src/intervals.c     | 187 +++++++++++++++++++++++++++++---------------
 src/mnl.c           |  70 +++++++++++++++--
 src/rule.c          |   4 +-
 6 files changed, 202 insertions(+), 72 deletions(-)
include/intervals.h +2 -0
index ef0fb53e7577..2366c295ca08 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 expr *next_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 +125 -62

220 lines not on this page · raw message

src/mnl.c +63 -7

122 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