Skip to contentSkip to conversation

memory reduction in concatenation and maps

PATCH In review Pablo Neira Ayuso 1 participant 5 messages Jun 16, 2025 – Jun 23, 2025 netfilter

lore
Share & tools
lore

Pablo Neira Ayuso

author maintainer
#0 lore raw

cover memory reduction in concatenation and maps

Hi,

This series uses EXPR_RANGE_VALUE in maps to reduce memory usage:

Patch #1 reduces memory footprint in concatenation of intervals, with the following 100k example set:

 table inet x {
        set y {
                typeof ip saddr . tcp dport
                flags interval
                elements = {
                        0.1.2.0-0.1.2.240 . 0-1,
                        ...				# 100k-1 entries more
                }
        }

}

Before: 123.80 Mbytes
After: 80.19 Mbytes (-35.23%)

Patch #2 remove EXPR_F_SINGLETON in EXPR_RANGE_VALUE that is required by next patch.

Patch #3 reduces memory footprint in maps.

With 100k map with concatenations:

  table inet x {
         map y {
                    typeof ip saddr . tcp dport :  ip saddr
                    flags interval
                    elements = {
                        1.0.2.0-1.0.2.240 . 0-2 : 1.0.2.10,
                        ...
         }
  }

Before: 153.6 Mbytes
After: 108.9 Mbytes (-29.11%)

With 100k map without concatenations:

  table inet x {
         map y {
                    typeof ip saddr :  ip saddr
                    flags interval
                    elements = {
                        1.0.2.0-1.0.2.240 : 1.0.2.10,
                        ...
         }
  }

Before: 74.36 Mbytes
After: 62.39 Mbytes (-16.10%)

This is passing tests/shell.

Pablo Neira Ayuso (3):
src: use constant range expression for interval+concatenation sets
expression: constant range is not a singleton
src: use EXPR_RANGE_VALUE in interval maps

 src/evaluate.c   |  8 ++++---
 src/expression.c |  2 +-
 src/netlink.c    | 61 ++++++++++++++++++++++++++++++++++++++++++------
 src/optimize.c   |  3 +++
 4 files changed, 63 insertions(+), 11 deletions(-)
Signature · 1 line
2.30.2
author maintainer
#1 lore raw

PATCH v2 1/3 src: use constant range expression for interval+concatenation sets

Expand 347039f64509 ("src: add symbol range expression to further compact intervals") to use constant range expression for elements with concatenation of intervals.

Ruleset with 100k elements of this type:

 table inet x {
        set y {
                typeof ip saddr . tcp dport
                flags interval
                elements = {
			0.1.2.0-0.1.2.240 . 0-1,
			...
		}
	}

}

Memory consumption for this set:

Before: 123.80 Mbytes
After: 80.19 Mbytes (-35.23%)

This patch keeps the workaround 2fbade3cd990 ("netlink: bogus concatenated set ranges with netlink message overrun") in place.

---
v2: fix error hint when flags interval is missing in set declaration

 src/evaluate.c |  5 +++--
 src/netlink.c  | 11 +++++++++++
 2 files changed, 14 insertions(+), 2 deletions(-)
src/evaluate.c +3 -2
index 9c7f23cb080e..b157a9c9d935 100644
@@ -1879,6 +1879,7 @@ static int expr_evaluate_set_elem(struct eval_ctx *ctx, struct expr **expr)
 		switch (elem->key->etype) {
 		case EXPR_PREFIX:
 		case EXPR_RANGE:
+		case EXPR_RANGE_VALUE:
 			key = elem->key;
 			goto err_missing_flag;
 		case EXPR_CONCAT:
@@ -1886,6 +1887,7 @@ static int expr_evaluate_set_elem(struct eval_ctx *ctx, struct expr **expr)
 				switch (key->etype) {
 				case EXPR_PREFIX:
 				case EXPR_RANGE:
+				case EXPR_RANGE_VALUE:
 					goto err_missing_flag;
 				default:
 					break;
@@ -2366,9 +2368,8 @@ static int expr_evaluate_symbol_range(struct eval_ctx *ctx, struct expr **exprp)
 	left = range->left;
 	right = range->right;
 
-	/* concatenation and maps need more work to use constant_range_expr. */
+	/* maps need more work to use constant_range_expr. */
 	if (ctx->set && !set_is_map(ctx->set->flags) &&
-	    set_is_non_concat_range(ctx->set) &&
 	    left->etype == EXPR_VALUE &&
 	    right->etype == EXPR_VALUE) {
 		constant_range = constant_range_expr_alloc(&expr->location,
src/netlink.c +11 -0
index 73fe579a477c..94cf177213fd 100644
@@ -285,6 +285,17 @@ static int __netlink_gen_concat_key(uint32_t flags, const struct expr *i,
 			byteorder_switch_expr_value(value, expr);
 
 		i = expr;
+		break;
+	case EXPR_RANGE_VALUE:
+		if (flags & EXPR_F_INTERVAL_END)
+			mpz_init_set(value, i->range.high);
+		else
+			mpz_init_set(value, i->range.low);
+
+		if (expr_basetype(i)->type == TYPE_INTEGER &&
+		    i->byteorder == BYTEORDER_HOST_ENDIAN)
+			byteorder_switch_expr_value(value, i);
+
 		break;
 	case EXPR_PREFIX:
 		if (flags & EXPR_F_INTERVAL_END) {
Signature · 1 line
2.30.2
author maintainer
#2 lore raw

PATCH 2/3 expression: constant range is not a singleton

In reply to Pablo Neira Ayuso

Remove the EXPR_F_SINGLETON flag in EXPR_RANGE_VALUE so it can be used in maps.

expr_evaluate_set() does not toggle NFT_SET_INTERVAL for anonymous sets because a singleton is assumed to be place, leading to this BUG:

 BUG: invalid data expression type range_value
 nft: src/netlink.c:577: netlink_gen_key: Assertion `0' failed.
---
 src/expression.c | 2 +-
 1 file changed, 1 insertion(+), 1 deletion(-)
src/expression.c +1 -1
index dc9a44677b28..aa97413d0794 100644
@@ -612,7 +612,7 @@ struct expr *constant_range_expr_alloc(const struct location *loc,
 	struct expr *expr;
 
 	expr = expr_alloc(loc, EXPR_RANGE_VALUE, dtype, byteorder, len);
-	expr->flags = EXPR_F_CONSTANT | EXPR_F_SINGLETON;
+	expr->flags = EXPR_F_CONSTANT;
 
 	mpz_init_set(expr->range.low, low);
 	mpz_init_set(expr->range.high, high);
Signature · 1 line
2.30.2
author maintainer
#3 lore raw

PATCH 3/3 src: use EXPR_RANGE_VALUE in interval maps

In reply to Pablo Neira Ayuso

Remove the restriction on maps to use EXPR_RANGE_VALUE to reduce memory consumption.

With 100k map with concatenation:

  table inet x {
         map y {
                    typeof ip saddr . tcp dport :  ip saddr
                    flags interval
                    elements = {
                        1.0.2.0-1.0.2.240 . 0-2 : 1.0.2.10,
			...
	 }

}

Before: 153.6 Mbytes
After: 108.9 Mbytes (-29.11%)

With 100k map without concatenation:

  table inet x {
         map y {
                    typeof ip saddr :  ip saddr
                    flags interval
                    elements = {
                        1.0.2.0-1.0.2.240 : 1.0.2.10,
			...
	 }

}

Before: 74.36 Mbytes
After: 62.39 Mbytes (-16.10%)

---
 src/evaluate.c |  5 +++--
 src/netlink.c  | 50 +++++++++++++++++++++++++++++++++++++++++++-------
 src/optimize.c |  3 +++
 3 files changed, 49 insertions(+), 9 deletions(-)
src/evaluate.c +3 -2
index b157a9c9d935..fac6c657dcbb 100644
@@ -2268,6 +2268,7 @@ static bool data_mapping_has_interval(struct expr *data)
 	struct expr *i;
 
 	if (data->etype == EXPR_RANGE ||
+	    data->etype == EXPR_RANGE_VALUE ||
 	    data->etype == EXPR_PREFIX)
 		return true;
 
@@ -2276,6 +2277,7 @@ static bool data_mapping_has_interval(struct expr *data)
 
 	list_for_each_entry(i, &data->expressions, list) {
 		if (i->etype == EXPR_RANGE ||
+		    i->etype == EXPR_RANGE_VALUE ||
 		    i->etype == EXPR_PREFIX)
 			return true;
 	}
@@ -2368,8 +2370,7 @@ static int expr_evaluate_symbol_range(struct eval_ctx *ctx, struct expr **exprp)
 	left = range->left;
 	right = range->right;
 
-	/* maps need more work to use constant_range_expr. */
-	if (ctx->set && !set_is_map(ctx->set->flags) &&
+	if (ctx->set &&
 	    left->etype == EXPR_VALUE &&
 	    right->etype == EXPR_VALUE) {
 		constant_range = constant_range_expr_alloc(&expr->location,
src/netlink.c +43 -7

90 lines not on this page · raw message

src/optimize.c +3 -0
index 5b7b0ab62fbc..89ba0d9dee6a 100644
@@ -172,6 +172,7 @@ static bool stmt_expr_supported(const struct expr *expr)
 	case EXPR_SYMBOL:
 	case EXPR_RANGE_SYMBOL:
 	case EXPR_RANGE:
+	case EXPR_RANGE_VALUE:
 	case EXPR_PREFIX:
 	case EXPR_SET:
 	case EXPR_LIST:
@@ -667,6 +668,7 @@ static void __merge_concat(const struct optimize_ctx *ctx, uint32_t i,
 			case EXPR_PREFIX:
 			case EXPR_RANGE_SYMBOL:
 			case EXPR_RANGE:
+			case EXPR_RANGE_VALUE:
 				clone = expr_clone(stmt_a->expr->right);
 				compound_expr_add(concat, clone);
 				break;
@@ -778,6 +780,7 @@ static void build_verdict_map(struct expr *expr, struct stmt *verdict,
 	case EXPR_PREFIX:
 	case EXPR_RANGE_SYMBOL:
 	case EXPR_RANGE:
+	case EXPR_RANGE_VALUE:
 	case EXPR_VALUE:
 	case EXPR_SYMBOL:
 	case EXPR_CONCAT:
Signature · 1 line
2.30.2