* [PATCH nft 1/6] intervals: add helper function to set previous element
2024-12-17 21:15 [PATCH nft 0/6] shrink memory usage for interval sets Pablo Neira Ayuso
@ 2024-12-17 21:15 ` Pablo Neira Ayuso
2024-12-17 21:15 ` [PATCH nft 2/6] intervals: do not merge intervals with different timeout Pablo Neira Ayuso
` (4 subsequent siblings)
5 siblings, 0 replies; 7+ messages in thread
From: Pablo Neira Ayuso @ 2024-12-17 21:15 UTC (permalink / raw)
To: netfilter-devel
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
^ permalink raw reply related [flat|nested] 7+ messages in thread* [PATCH nft 2/6] intervals: do not merge intervals with different timeout
2024-12-17 21:15 [PATCH nft 0/6] shrink memory usage for interval sets Pablo Neira Ayuso
2024-12-17 21:15 ` [PATCH nft 1/6] intervals: add helper function to set previous element Pablo Neira Ayuso
@ 2024-12-17 21:15 ` Pablo Neira Ayuso
2024-12-17 21:15 ` [PATCH nft 3/6] src: add EXPR_RANGE_VALUE expression and use it Pablo Neira Ayuso
` (3 subsequent siblings)
5 siblings, 0 replies; 7+ messages in thread
From: Pablo Neira Ayuso @ 2024-12-17 21:15 UTC (permalink / raw)
To: netfilter-devel
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
^ permalink raw reply related [flat|nested] 7+ messages in thread* [PATCH nft 3/6] src: add EXPR_RANGE_VALUE expression and use it
2024-12-17 21:15 [PATCH nft 0/6] shrink memory usage for interval sets Pablo Neira Ayuso
2024-12-17 21:15 ` [PATCH nft 1/6] intervals: add helper function to set previous element Pablo Neira Ayuso
2024-12-17 21:15 ` [PATCH nft 2/6] intervals: do not merge intervals with different timeout Pablo Neira Ayuso
@ 2024-12-17 21:15 ` Pablo Neira Ayuso
2024-12-17 21:15 ` [PATCH nft 4/6] rule: constify set_is_non_concat_range() Pablo Neira Ayuso
` (2 subsequent siblings)
5 siblings, 0 replies; 7+ messages in thread
From: Pablo Neira Ayuso @ 2024-12-17 21:15 UTC (permalink / raw)
To: netfilter-devel
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
^ permalink raw reply related [flat|nested] 7+ messages in thread* [PATCH nft 4/6] rule: constify set_is_non_concat_range()
2024-12-17 21:15 [PATCH nft 0/6] shrink memory usage for interval sets Pablo Neira Ayuso
` (2 preceding siblings ...)
2024-12-17 21:15 ` [PATCH nft 3/6] src: add EXPR_RANGE_VALUE expression and use it Pablo Neira Ayuso
@ 2024-12-17 21:15 ` Pablo Neira Ayuso
2024-12-17 21:15 ` [PATCH nft 5/6] mnl: rename list of expression in mnl_nft_setelem_batch() Pablo Neira Ayuso
2024-12-17 21:15 ` [PATCH nft 6/6] src: rework singleton interval transformation to reduce memory consumption Pablo Neira Ayuso
5 siblings, 0 replies; 7+ messages in thread
From: Pablo Neira Ayuso @ 2024-12-17 21:15 UTC (permalink / raw)
To: netfilter-devel
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
^ permalink raw reply related [flat|nested] 7+ messages in thread* [PATCH nft 5/6] mnl: rename list of expression in mnl_nft_setelem_batch()
2024-12-17 21:15 [PATCH nft 0/6] shrink memory usage for interval sets Pablo Neira Ayuso
` (3 preceding siblings ...)
2024-12-17 21:15 ` [PATCH nft 4/6] rule: constify set_is_non_concat_range() Pablo Neira Ayuso
@ 2024-12-17 21:15 ` Pablo Neira Ayuso
2024-12-17 21:15 ` [PATCH nft 6/6] src: rework singleton interval transformation to reduce memory consumption Pablo Neira Ayuso
5 siblings, 0 replies; 7+ messages in thread
From: Pablo Neira Ayuso @ 2024-12-17 21:15 UTC (permalink / raw)
To: netfilter-devel
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
^ permalink raw reply related [flat|nested] 7+ messages in thread* [PATCH nft 6/6] src: rework singleton interval transformation to reduce memory consumption
2024-12-17 21:15 [PATCH nft 0/6] shrink memory usage for interval sets Pablo Neira Ayuso
` (4 preceding siblings ...)
2024-12-17 21:15 ` [PATCH nft 5/6] mnl: rename list of expression in mnl_nft_setelem_batch() Pablo Neira Ayuso
@ 2024-12-17 21:15 ` Pablo Neira Ayuso
5 siblings, 0 replies; 7+ messages in thread
From: Pablo Neira Ayuso @ 2024-12-17 21:15 UTC (permalink / raw)
To: netfilter-devel
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
^ permalink raw reply related [flat|nested] 7+ messages in thread