* [PATCH nft,v4 0/7] revisit overlap/automerge codebase
@ 2022-04-12 14:47 Pablo Neira Ayuso
2022-04-12 14:47 ` [PATCH nft,v4 1/7] src: add EXPR_F_KERNEL to identify expression in the kernel Pablo Neira Ayuso
` (6 more replies)
0 siblings, 7 replies; 16+ messages in thread
From: Pablo Neira Ayuso @ 2022-04-12 14:47 UTC (permalink / raw)
To: netfilter-devel
Hi,
This is another iteration of the set element automerge codebase rework,
posted last time in March 1st.
This series comes with a oneliner fix for Patch 2/7 "src: replace interval
segment tree overlap and automerge" that sets on i->elem_flags instead of
elem->elem_flags (this was breaking open intervals).
Now tests/monitor are passing fine in this batch.
This patchset removes the segment tree interval overlap/automerge codebase.
This is replaced with mergesort of the set elements + check for overlaps by
linearly iterating the set elements. This also allows to use automerge with
set element deletions.
This is passing tests/shell, tests/py and tests/monitor.
Pablo Neira Ayuso (7):
src: add EXPR_F_KERNEL to identify expression in the kernel
src: replace interval segment tree overlap and automerge
src: remove rbtree datastructure
mnl: update mnl_nft_setelem_del() to allow for more reuse
intervals: add support to automerge with kernel elements
evaluate: allow for zero length ranges
intervals: support to partial deletion with automerge
include/Makefile.am | 2 +-
include/expression.h | 7 +-
include/intervals.h | 12 +
include/mnl.h | 3 +-
include/rbtree.h | 98 ---
include/rule.h | 2 +
src/Makefile.am | 2 +-
src/cache.c | 6 +
src/evaluate.c | 75 +-
src/intervals.c | 740 ++++++++++++++++++
src/libnftables.c | 4 +-
src/mergesort.c | 1 +
src/mnl.c | 6 +-
src/netlink.c | 1 +
src/rbtree.c | 388 ---------
src/rule.c | 25 +-
src/segtree.c | 660 +---------------
.../shell/testcases/sets/0069interval_merge_0 | 28 +
.../sets/dumps/0069interval_merge_0.nft | 9 +
19 files changed, 895 insertions(+), 1174 deletions(-)
create mode 100644 include/intervals.h
delete mode 100644 include/rbtree.h
create mode 100644 src/intervals.c
delete mode 100644 src/rbtree.c
create mode 100755 tests/shell/testcases/sets/0069interval_merge_0
create mode 100644 tests/shell/testcases/sets/dumps/0069interval_merge_0.nft
--
2.30.2
^ permalink raw reply [flat|nested] 16+ messages in thread
* [PATCH nft,v4 1/7] src: add EXPR_F_KERNEL to identify expression in the kernel
2022-04-12 14:47 [PATCH nft,v4 0/7] revisit overlap/automerge codebase Pablo Neira Ayuso
@ 2022-04-12 14:47 ` Pablo Neira Ayuso
2022-04-12 14:47 ` [PATCH nft,v4 2/7] src: replace interval segment tree overlap and automerge Pablo Neira Ayuso
` (5 subsequent siblings)
6 siblings, 0 replies; 16+ messages in thread
From: Pablo Neira Ayuso @ 2022-04-12 14:47 UTC (permalink / raw)
To: netfilter-devel
This allows to identify the set elements that reside in the kernel.
Signed-off-by: Pablo Neira Ayuso <pablo@netfilter.org>
---
include/expression.h | 2 ++
src/netlink.c | 1 +
src/segtree.c | 10 ++++++++--
3 files changed, 11 insertions(+), 2 deletions(-)
diff --git a/include/expression.h b/include/expression.h
index 78f788b3c377..ce32e1f3d20c 100644
--- a/include/expression.h
+++ b/include/expression.h
@@ -192,6 +192,7 @@ const struct expr_ops *expr_ops_by_type(enum expr_types etype);
* @EXPR_F_INTERVAL_END: set member ends an open interval
* @EXPR_F_BOOLEAN: expression is boolean (set by relational expr on LHS)
* @EXPR_F_INTERVAL: expression describes a interval
+ * @EXPR_F_KERNEL: expression resides in the kernel
*/
enum expr_flags {
EXPR_F_CONSTANT = 0x1,
@@ -200,6 +201,7 @@ enum expr_flags {
EXPR_F_INTERVAL_END = 0x8,
EXPR_F_BOOLEAN = 0x10,
EXPR_F_INTERVAL = 0x20,
+ EXPR_F_KERNEL = 0x40,
};
#include <payload.h>
diff --git a/src/netlink.c b/src/netlink.c
index 775c6f5170e2..24a9ad9852f3 100644
--- a/src/netlink.c
+++ b/src/netlink.c
@@ -1286,6 +1286,7 @@ key_end:
}
expr = set_elem_expr_alloc(&netlink_location, key);
+ expr->flags |= EXPR_F_KERNEL;
if (nftnl_set_elem_is_set(nlse, NFTNL_SET_ELEM_TIMEOUT))
expr->timeout = nftnl_set_elem_get_u64(nlse, NFTNL_SET_ELEM_TIMEOUT);
diff --git a/src/segtree.c b/src/segtree.c
index a61ea3d2854a..832bc7dd1402 100644
--- a/src/segtree.c
+++ b/src/segtree.c
@@ -1060,9 +1060,10 @@ void interval_map_decompose(struct expr *set)
mpz_and(p, expr_value(low)->value, range);
- if (!mpz_cmp_ui(range, 0))
+ if (!mpz_cmp_ui(range, 0)) {
+ low->flags |= EXPR_F_KERNEL;
compound_expr_add(set, expr_get(low));
- else if ((!range_is_prefix(range) ||
+ } else if ((!range_is_prefix(range) ||
!(i->dtype->flags & DTYPE_F_PREFIX)) ||
mpz_cmp_ui(p, 0)) {
struct expr *tmp;
@@ -1087,6 +1088,7 @@ void interval_map_decompose(struct expr *set)
} else {
interval_expr_copy(tmp, low);
}
+ tmp->flags |= EXPR_F_KERNEL;
compound_expr_add(set, tmp);
} else {
@@ -1109,6 +1111,7 @@ void interval_map_decompose(struct expr *set)
} else {
interval_expr_copy(prefix, low);
}
+ prefix->flags |= EXPR_F_KERNEL;
compound_expr_add(set, prefix);
}
@@ -1134,6 +1137,7 @@ void interval_map_decompose(struct expr *set)
i = range_expr_alloc(&low->location,
expr_clone(expr_value(low)), i);
i = set_elem_expr_alloc(&low->location, i);
+
if (low->etype == EXPR_MAPPING) {
i = mapping_expr_alloc(&i->location, i,
expr_clone(low->right));
@@ -1141,6 +1145,8 @@ void interval_map_decompose(struct expr *set)
} else {
interval_expr_copy(i, low);
}
+ i->flags |= EXPR_F_KERNEL;
+
expr_free(low);
}
--
2.30.2
^ permalink raw reply related [flat|nested] 16+ messages in thread
* [PATCH nft,v4 2/7] src: replace interval segment tree overlap and automerge
2022-04-12 14:47 [PATCH nft,v4 0/7] revisit overlap/automerge codebase Pablo Neira Ayuso
2022-04-12 14:47 ` [PATCH nft,v4 1/7] src: add EXPR_F_KERNEL to identify expression in the kernel Pablo Neira Ayuso
@ 2022-04-12 14:47 ` Pablo Neira Ayuso
2022-04-12 14:47 ` [PATCH nft,v4 3/7] src: remove rbtree datastructure Pablo Neira Ayuso
` (4 subsequent siblings)
6 siblings, 0 replies; 16+ messages in thread
From: Pablo Neira Ayuso @ 2022-04-12 14:47 UTC (permalink / raw)
To: netfilter-devel
This is a rewrite of the segtree interval codebase.
This patch now splits the original set_to_interval() function in three
routines:
- add set_automerge() to merge overlapping and contiguous ranges.
The elements, expressed either as single value, prefix and ranges are
all first normalized to ranges. This elements expressed as ranges are
mergesorted. Then, there is a linear list inspection to check for
merge candidates. This code only merges elements in the same batch,
ie. it does not merge elements in the kernela and the userspace batch.
- add set_overlap() to check for overlapping set elements. Linux
kernel >= 5.7 already checks for overlaps, older kernels still needs
this code. This code checks for two conflict types:
1) between elements in this batch.
2) between elements in this batch and kernelspace.
The elements in the kernel are temporarily merged into the list of
elements in the batch to check for this overlaps. The EXPR_F_KERNEL
flag allows us to restore the set cache after the overlap check has
been performed.
- set_to_interval() now only transforms set elements, expressed as range
e.g. [a,b], to individual set elements using the EXPR_F_INTERVAL_END
flag notation to represent e.g. [a,b+1), where b+1 has the
EXPR_F_INTERVAL_END flag set on.
More relevant updates:
- The overlap and automerge routines are now performed in the evaluation
phase.
- The userspace set object representation now stores a reference to the
existing kernel set object (in case there is already a set with this
same name in the kernel). This is required by the new overlap and
automerge approach.
Signed-off-by: Pablo Neira Ayuso <pablo@netfilter.org>
---
include/Makefile.am | 1 +
include/expression.h | 4 -
include/intervals.h | 9 +
include/rule.h | 2 +
src/Makefile.am | 1 +
src/evaluate.c | 70 ++++-
src/intervals.c | 392 ++++++++++++++++++++++++++
src/mergesort.c | 1 +
src/rule.c | 13 +-
src/segtree.c | 650 -------------------------------------------
10 files changed, 477 insertions(+), 666 deletions(-)
create mode 100644 include/intervals.h
create mode 100644 src/intervals.c
diff --git a/include/Makefile.am b/include/Makefile.am
index b997f46b75be..940b7fafb0b4 100644
--- a/include/Makefile.am
+++ b/include/Makefile.am
@@ -8,6 +8,7 @@ noinst_HEADERS = cli.h \
expression.h \
fib.h \
hash.h \
+ intervals.h \
ipopt.h \
json.h \
mini-gmp.h \
diff --git a/include/expression.h b/include/expression.h
index ce32e1f3d20c..c2d67d4c88af 100644
--- a/include/expression.h
+++ b/include/expression.h
@@ -486,10 +486,6 @@ extern struct expr *list_expr_alloc(const struct location *loc);
extern struct expr *set_expr_alloc(const struct location *loc,
const struct set *set);
-extern int set_to_intervals(struct list_head *msgs, struct set *set,
- struct expr *init, bool add,
- unsigned int debug_mask, bool merge,
- struct output_ctx *octx);
extern void concat_range_aggregate(struct expr *set);
extern void interval_map_decompose(struct expr *set);
diff --git a/include/intervals.h b/include/intervals.h
new file mode 100644
index 000000000000..f69800638070
--- /dev/null
+++ b/include/intervals.h
@@ -0,0 +1,9 @@
+#ifndef NFTABLES_INTERVALS_H
+#define NFTABLES_INTERVALS_H
+
+void set_to_range(struct expr *init);
+int set_automerge(struct list_head *msgs, struct set *set, struct expr *init);
+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);
+
+#endif
diff --git a/include/rule.h b/include/rule.h
index 150576641b39..e232b97afed7 100644
--- a/include/rule.h
+++ b/include/rule.h
@@ -324,6 +324,7 @@ void rule_stmt_insert_at(struct rule *rule, struct stmt *nstmt,
* @key: key expression (data type, length))
* @data: mapping data expression
* @objtype: mapping object type
+ * @existing_set: reference to existing set in the kernel
* @init: initializer
* @rg_cache: cached range element (left)
* @policy: set mechanism policy
@@ -345,6 +346,7 @@ struct set {
struct expr *key;
struct expr *data;
uint32_t objtype;
+ struct set *existing_set;
struct expr *init;
struct expr *rg_cache;
uint32_t policy;
diff --git a/src/Makefile.am b/src/Makefile.am
index e96cee77691b..fe0632e7c37d 100644
--- a/src/Makefile.am
+++ b/src/Makefile.am
@@ -48,6 +48,7 @@ libnftables_la_SOURCES = \
exthdr.c \
fib.c \
hash.c \
+ intervals.c \
ipopt.c \
meta.c \
rt.c \
diff --git a/src/evaluate.c b/src/evaluate.c
index 6b3b63662411..1b20d76f8111 100644
--- a/src/evaluate.c
+++ b/src/evaluate.c
@@ -29,6 +29,7 @@
#include <expression.h>
#include <statement.h>
+#include <intervals.h>
#include <netlink.h>
#include <time.h>
#include <rule.h>
@@ -1453,6 +1454,36 @@ static const struct expr *expr_set_elem(const struct expr *expr)
return expr;
}
+static int interval_set_eval(struct eval_ctx *ctx, struct set *set,
+ struct expr *init)
+{
+ int ret;
+
+ if (!init)
+ return 0;
+
+ ret = 0;
+ switch (ctx->cmd->op) {
+ case CMD_CREATE:
+ case CMD_ADD:
+ if (set->automerge)
+ ret = set_automerge(ctx->msgs, set, init);
+ else
+ ret = set_overlap(ctx->msgs, set, init);
+ break;
+ case CMD_DELETE:
+ set_to_range(init);
+ break;
+ case CMD_GET:
+ break;
+ default:
+ assert(1);
+ break;
+ }
+
+ return ret;
+}
+
static int expr_evaluate_set(struct eval_ctx *ctx, struct expr **expr)
{
struct expr *set = *expr, *i, *next;
@@ -1540,6 +1571,7 @@ static int expr_evaluate_set(struct eval_ctx *ctx, struct expr **expr)
datatype_set(set, ctx->ectx.dtype);
set->len = ctx->ectx.len;
set->flags |= EXPR_F_CONSTANT;
+
return 0;
}
@@ -1622,6 +1654,12 @@ static int expr_evaluate_map(struct eval_ctx *ctx, struct expr **expr)
ctx->set = mappings->set;
if (expr_evaluate(ctx, &map->mappings->set->init) < 0)
return -1;
+
+ if (set_is_interval(map->mappings->set->init->set_flags) &&
+ !(map->mappings->set->init->set_flags & NFT_SET_CONCAT) &&
+ interval_set_eval(ctx, ctx->set, map->mappings->set->init) < 0)
+ return -1;
+
expr_set_context(&ctx->ectx, ctx->set->key->dtype, ctx->set->key->len);
if (binop_transfer(ctx, expr) < 0)
return -1;
@@ -3794,6 +3832,12 @@ static int stmt_evaluate_objref_map(struct eval_ctx *ctx, struct stmt *stmt)
ctx->set = mappings->set;
if (expr_evaluate(ctx, &map->mappings->set->init) < 0)
return -1;
+
+ if (set_is_interval(map->mappings->set->init->set_flags) &&
+ !(map->mappings->set->init->set_flags & NFT_SET_CONCAT) &&
+ interval_set_eval(ctx, ctx->set, map->mappings->set->init) < 0)
+ return -1;
+
ctx->set = NULL;
map_set_concat_info(map);
@@ -3930,14 +3974,20 @@ static int setelem_evaluate(struct eval_ctx *ctx, struct cmd *cmd)
return set_not_found(ctx, &ctx->cmd->handle.set.location,
ctx->cmd->handle.set.name);
+ set->existing_set = set;
ctx->set = set;
expr_set_context(&ctx->ectx, set->key->dtype, set->key->len);
if (expr_evaluate(ctx, &cmd->expr) < 0)
return -1;
- ctx->set = NULL;
cmd->elem.set = set_get(set);
+ if (set_is_interval(ctx->set->flags) &&
+ !(set->flags & NFT_SET_CONCAT))
+ return interval_set_eval(ctx, ctx->set, cmd->expr);
+
+ ctx->set = NULL;
+
return 0;
}
@@ -4009,6 +4059,7 @@ static int set_expr_evaluate_concat(struct eval_ctx *ctx, struct expr **expr)
static int set_evaluate(struct eval_ctx *ctx, struct set *set)
{
+ struct set *existing_set = NULL;
unsigned int num_stmts = 0;
struct table *table;
struct stmt *stmt;
@@ -4021,7 +4072,8 @@ static int set_evaluate(struct eval_ctx *ctx, struct set *set)
if (table == NULL)
return table_not_found(ctx);
- if (!set_cache_find(table, set->handle.set.name))
+ existing_set = set_cache_find(table, set->handle.set.name);
+ if (!existing_set)
set_cache_add(set_get(set), table);
}
@@ -4085,9 +4137,16 @@ static int set_evaluate(struct eval_ctx *ctx, struct set *set)
if (num_stmts > 1)
set->flags |= NFT_SET_EXPR;
- if (set_is_anonymous(set->flags))
+ if (set_is_anonymous(set->flags)) {
+ if (set_is_interval(set->init->set_flags) &&
+ !(set->init->set_flags & NFT_SET_CONCAT) &&
+ interval_set_eval(ctx, set, set->init) < 0)
+ return -1;
+
return 0;
+ }
+ set->existing_set = existing_set;
ctx->set = set;
if (set->init != NULL) {
__expr_set_context(&ctx->ectx, set->key->dtype,
@@ -4098,6 +4157,11 @@ static int set_evaluate(struct eval_ctx *ctx, struct set *set)
return expr_error(ctx->msgs, set->init, "Set %s: Unexpected initial type %s, missing { }?",
set->handle.set.name, expr_name(set->init));
}
+
+ if (set_is_interval(ctx->set->flags) &&
+ !(ctx->set->flags & NFT_SET_CONCAT))
+ return interval_set_eval(ctx, ctx->set, set->init);
+
ctx->set = NULL;
return 0;
diff --git a/src/intervals.c b/src/intervals.c
new file mode 100644
index 000000000000..c6f66e634d4c
--- /dev/null
+++ b/src/intervals.c
@@ -0,0 +1,392 @@
+/*
+ * Copyright (c) 2022 Pablo Neira Ayuso <pablo@netfilter.org>
+ *
+ * This program is free software; you can redistribute it and/or modify
+ * it under the terms of the GNU General Public License version 2 (or any
+ * later) as published by the Free Software Foundation.
+ */
+
+#include <nftables.h>
+#include <expression.h>
+#include <intervals.h>
+#include <rule.h>
+
+static void setelem_expr_to_range(struct expr *expr)
+{
+ unsigned char data[sizeof(struct in6_addr) * BITS_PER_BYTE];
+ struct expr *key, *value;
+ mpz_t rop;
+
+ assert(expr->etype == EXPR_SET_ELEM);
+
+ switch (expr->key->etype) {
+ case EXPR_RANGE:
+ break;
+ case EXPR_PREFIX:
+ mpz_init(rop);
+ mpz_bitmask(rop, expr->key->len - expr->key->prefix_len);
+ mpz_ior(rop, rop, expr->key->prefix->value);
+ mpz_export_data(data, rop, expr->key->prefix->byteorder,
+ expr->key->prefix->len / BITS_PER_BYTE);
+ 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;
+ case EXPR_VALUE:
+ key = range_expr_alloc(&expr->location,
+ expr_clone(expr->key),
+ expr_get(expr->key));
+ expr_free(expr->key);
+ expr->key = key;
+ break;
+ default:
+ assert(1);
+ }
+}
+
+static void remove_overlapping_range(struct expr *i, struct expr *init)
+{
+ list_del(&i->list);
+ expr_free(i);
+ init->size--;
+}
+
+struct range {
+ mpz_t low;
+ mpz_t high;
+};
+
+static void merge_ranges(struct expr *prev, struct expr *i,
+ struct range *prev_range, struct range *range,
+ struct expr *init)
+{
+ expr_free(prev->key->right);
+ prev->key->right = expr_get(i->key->right);
+ list_del(&i->list);
+ expr_free(i);
+ mpz_set(prev_range->high, range->high);
+ init->size--;
+}
+
+static void setelem_automerge(struct list_head *msgs, struct set *set,
+ struct expr *init)
+{
+ struct expr *i, *next, *prev = NULL;
+ struct range range, prev_range;
+ mpz_t rop;
+
+ mpz_init(prev_range.low);
+ mpz_init(prev_range.high);
+ mpz_init(range.low);
+ mpz_init(range.high);
+ mpz_init(rop);
+
+ list_for_each_entry_safe(i, next, &init->expressions, list) {
+ if (i->key->etype == EXPR_SET_ELEM_CATCHALL)
+ continue;
+
+ range_expr_value_low(range.low, i);
+ 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);
+ continue;
+ }
+
+ if (mpz_cmp(prev_range.low, range.low) <= 0 &&
+ mpz_cmp(prev_range.high, range.high) >= 0) {
+ remove_overlapping_range(i, init);
+ continue;
+ } else if (mpz_cmp(range.low, prev_range.high) <= 0) {
+ merge_ranges(prev, i, &prev_range, &range, init);
+ continue;
+ } else if (set->automerge) {
+ mpz_sub(rop, range.low, prev_range.high);
+ /* two contiguous ranges */
+ if (mpz_cmp_ui(rop, 1) == 0) {
+ merge_ranges(prev, i, &prev_range, &range, init);
+ continue;
+ }
+ }
+
+ prev = i;
+ mpz_set(prev_range.low, range.low);
+ mpz_set(prev_range.high, range.high);
+ }
+
+ mpz_clear(prev_range.low);
+ mpz_clear(prev_range.high);
+ mpz_clear(range.low);
+ mpz_clear(range.high);
+ mpz_clear(rop);
+}
+
+static struct expr *interval_expr_key(struct expr *i)
+{
+ struct expr *elem;
+
+ switch (i->etype) {
+ case EXPR_MAPPING:
+ elem = i->left;
+ break;
+ case EXPR_SET_ELEM:
+ elem = i;
+ break;
+ default:
+ assert(1);
+ return NULL;
+ }
+
+ return elem;
+}
+
+void set_to_range(struct expr *init)
+{
+ struct expr *i, *elem;
+
+ list_for_each_entry(i, &init->expressions, list) {
+ elem = interval_expr_key(i);
+ setelem_expr_to_range(elem);
+ }
+
+ list_expr_sort(&init->expressions);
+}
+
+int set_automerge(struct list_head *msgs, struct set *set, struct expr *init)
+{
+ set_to_range(init);
+
+ if (set->flags & NFT_SET_MAP)
+ return 0;
+
+ setelem_automerge(msgs, set, init);
+
+ return 0;
+}
+
+static int setelem_overlap(struct list_head *msgs, struct set *set,
+ struct expr *init)
+{
+ struct expr *i, *next, *elem, *prev = NULL;
+ struct range range, prev_range;
+ int err = 0;
+ mpz_t rop;
+
+ mpz_init(prev_range.low);
+ mpz_init(prev_range.high);
+ mpz_init(range.low);
+ mpz_init(range.high);
+ mpz_init(rop);
+
+ list_for_each_entry_safe(elem, next, &init->expressions, list) {
+ i = interval_expr_key(elem);
+
+ if (i->key->etype == EXPR_SET_ELEM_CATCHALL)
+ continue;
+
+ range_expr_value_low(range.low, i);
+ range_expr_value_high(range.high, i);
+
+ if (!prev) {
+ prev = elem;
+ mpz_set(prev_range.low, range.low);
+ mpz_set(prev_range.high, range.high);
+ continue;
+ }
+
+ if (mpz_cmp(prev_range.low, range.low) == 0 &&
+ mpz_cmp(prev_range.high, range.high) == 0 &&
+ (elem->flags & EXPR_F_KERNEL || prev->flags & EXPR_F_KERNEL))
+ goto next;
+
+ if (mpz_cmp(prev_range.low, range.low) <= 0 &&
+ mpz_cmp(prev_range.high, range.high) >= 0) {
+ if (prev->flags & EXPR_F_KERNEL)
+ expr_error(msgs, i, "interval overlaps with an existing one");
+ else if (elem->flags & EXPR_F_KERNEL)
+ expr_error(msgs, prev, "interval overlaps with an existing one");
+ else
+ expr_binary_error(msgs, i, prev,
+ "conflicting intervals specified");
+ err = -1;
+ goto err_out;
+ } else if (mpz_cmp(range.low, prev_range.high) <= 0) {
+ if (prev->flags & EXPR_F_KERNEL)
+ expr_error(msgs, i, "interval overlaps with an existing one");
+ else if (elem->flags & EXPR_F_KERNEL)
+ expr_error(msgs, prev, "interval overlaps with an existing one");
+ else
+ expr_binary_error(msgs, i, prev,
+ "conflicting intervals specified");
+ err = -1;
+ goto err_out;
+ }
+next:
+ prev = elem;
+ mpz_set(prev_range.low, range.low);
+ mpz_set(prev_range.high, range.high);
+ }
+
+err_out:
+ mpz_clear(prev_range.low);
+ mpz_clear(prev_range.high);
+ mpz_clear(range.low);
+ mpz_clear(range.high);
+ mpz_clear(rop);
+
+ return err;
+}
+
+/* overlap detection for intervals already exists in Linux kernels >= 5.7. */
+int set_overlap(struct list_head *msgs, struct set *set, struct expr *init)
+{
+ struct set *existing_set = set->existing_set;
+ struct expr *i, *n;
+ int err;
+
+ if (existing_set && existing_set->init) {
+ list_splice_init(&existing_set->init->expressions,
+ &init->expressions);
+ }
+
+ set_to_range(init);
+
+ err = setelem_overlap(msgs, set, init);
+
+ list_for_each_entry_safe(i, n, &init->expressions, list) {
+ if (i->flags & EXPR_F_KERNEL)
+ list_move_tail(&i->list, &existing_set->init->expressions);
+ }
+
+ return err;
+}
+
+static bool segtree_needs_first_segment(const struct set *set,
+ const struct expr *init, bool add)
+{
+ if (add && !set->root) {
+ /* Add the first segment in four situations:
+ *
+ * 1) This is an anonymous set.
+ * 2) This set exists and it is empty.
+ * 3) New empty set and, separately, new elements are added.
+ * 4) This set is created with a number of initial elements.
+ */
+ if ((set_is_anonymous(set->flags)) ||
+ (set->init && set->init->size == 0) ||
+ (set->init == NULL && init) ||
+ (set->init == init)) {
+ return true;
+ }
+ }
+ /* This is an update for a set that already contains elements, so don't
+ * add the first non-matching elements otherwise we hit EEXIST.
+ */
+ return false;
+}
+
+int set_to_intervals(const struct set *set, struct expr *init, bool add)
+{
+ struct expr *i, *n, *prev = NULL, *elem, *newelem = NULL, *root, *expr;
+ LIST_HEAD(intervals);
+ uint32_t flags;
+ mpz_t p, q;
+
+ mpz_init2(p, set->key->len);
+ mpz_init2(q, set->key->len);
+
+ list_for_each_entry_safe(i, n, &init->expressions, list) {
+ flags = 0;
+
+ elem = interval_expr_key(i);
+
+ if (elem->key->etype == EXPR_SET_ELEM_CATCHALL)
+ continue;
+
+ if (!prev && segtree_needs_first_segment(set, init, add) &&
+ mpz_cmp_ui(elem->key->left->value, 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 (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);
+
+ if (!(set->flags & NFT_SET_ANONYMOUS) ||
+ mpz_cmp(p, elem->key->left->value) != 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);
+ 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(&internal_location, expr);
+ if (i->etype == EXPR_MAPPING) {
+ newelem = mapping_expr_alloc(&internal_location,
+ newelem,
+ expr_get(i->right));
+ }
+ newelem->flags |= EXPR_F_INTERVAL_END;
+ } else {
+ flags = NFTNL_SET_ELEM_F_INTERVAL_OPEN;
+ }
+
+ 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);
+ if (set->key->byteorder == BYTEORDER_HOST_ENDIAN)
+ mpz_switch_byteorder(expr->value, set->key->len / BITS_PER_BYTE);
+
+ expr_free(elem->key);
+ elem->key = expr;
+ i->elem_flags |= flags;
+ init->size++;
+ list_move_tail(&i->list, &intervals);
+
+ prev = i;
+ }
+
+ if (newelem)
+ list_add_tail(&newelem->list, &intervals);
+
+ list_splice_init(&intervals, &init->expressions);
+
+ mpz_clear(p);
+ mpz_clear(q);
+
+ return 0;
+}
diff --git a/src/mergesort.c b/src/mergesort.c
index 152b0556b164..8e6aac5fb24e 100644
--- a/src/mergesort.c
+++ b/src/mergesort.c
@@ -36,6 +36,7 @@ static void expr_msort_value(const struct expr *expr, mpz_t value)
break;
case EXPR_BINOP:
case EXPR_MAPPING:
+ case EXPR_RANGE:
expr_msort_value(expr->left, value);
break;
case EXPR_VALUE:
diff --git a/src/rule.c b/src/rule.c
index 19b8cb0323ee..89f1304b8222 100644
--- a/src/rule.c
+++ b/src/rule.c
@@ -26,6 +26,7 @@
#include <json.h>
#include <cache.h>
#include <owner.h>
+#include <intervals.h>
#include <libnftnl/common.h>
#include <libnftnl/ruleset.h>
@@ -1495,9 +1496,7 @@ static int do_add_elements(struct netlink_ctx *ctx, struct cmd *cmd,
struct set *set = cmd->elem.set;
if (set_is_non_concat_range(set) &&
- set_to_intervals(ctx->msgs, set, init, true,
- ctx->nft->debug_mask, set->automerge,
- &ctx->nft->output) < 0)
+ set_to_intervals(set, init, true) < 0)
return -1;
return __do_add_elements(ctx, set, init, flags);
@@ -1522,9 +1521,7 @@ static int do_add_set(struct netlink_ctx *ctx, struct cmd *cmd,
* comes too late which might result in spurious ENFILE errors.
*/
if (set_is_non_concat_range(set) &&
- set_to_intervals(ctx->msgs, set, set->init, true,
- ctx->nft->debug_mask, set->automerge,
- &ctx->nft->output) < 0)
+ set_to_intervals(set, set->init, true) < 0)
return -1;
}
@@ -1601,9 +1598,7 @@ static int do_delete_setelems(struct netlink_ctx *ctx, struct cmd *cmd)
struct set *set = cmd->elem.set;
if (set_is_non_concat_range(set) &&
- set_to_intervals(ctx->msgs, set, expr, false,
- ctx->nft->debug_mask, set->automerge,
- &ctx->nft->output) < 0)
+ set_to_intervals(set, expr, false) < 0)
return -1;
if (mnl_nft_setelem_del(ctx, cmd) < 0)
diff --git a/src/segtree.c b/src/segtree.c
index 832bc7dd1402..4eb74485e848 100644
--- a/src/segtree.c
+++ b/src/segtree.c
@@ -19,574 +19,6 @@
#include <expression.h>
#include <gmputil.h>
#include <utils.h>
-#include <rbtree.h>
-
-/**
- * struct seg_tree - segment tree
- *
- * @root: the rbtree's root
- * @type: the datatype of the dimension
- * @dwidth: width of the dimension
- * @byteorder: byteorder of elements
- * @debug_mask: display debugging information
- */
-struct seg_tree {
- struct rb_root root;
- const struct datatype *keytype;
- unsigned int keylen;
- const struct datatype *datatype;
- unsigned int datalen;
- enum byteorder byteorder;
- unsigned int debug_mask;
-};
-
-enum elementary_interval_flags {
- EI_F_INTERVAL_END = 0x1,
- EI_F_INTERVAL_OPEN = 0x2,
-};
-
-/**
- * struct elementary_interval - elementary interval [left, right]
- *
- * @rb_node: seg_tree rb node
- * @list: list node for linearized tree
- * @left: left endpoint
- * @right: right endpoint
- * @size: interval size (right - left)
- * @flags: flags
- * @expr: associated expression
- */
-struct elementary_interval {
- union {
- struct rb_node rb_node;
- struct list_head list;
- };
-
- mpz_t left;
- mpz_t right;
- mpz_t size;
-
- enum elementary_interval_flags flags;
- struct expr *expr;
-};
-
-static void seg_tree_init(struct seg_tree *tree, const struct set *set,
- struct expr *init, unsigned int debug_mask)
-{
- struct expr *first;
-
- first = list_entry(init->expressions.next, struct expr, list);
- tree->root = RB_ROOT;
- tree->keytype = set->key->dtype;
- tree->keylen = set->key->len;
- tree->datatype = NULL;
- tree->datalen = 0;
- if (set->data) {
- tree->datatype = set->data->dtype;
- tree->datalen = set->data->len;
- }
- tree->byteorder = first->byteorder;
- tree->debug_mask = debug_mask;
-}
-
-static struct elementary_interval *ei_alloc(const mpz_t left, const mpz_t right,
- struct expr *expr,
- enum elementary_interval_flags flags)
-{
- struct elementary_interval *ei;
-
- ei = xzalloc(sizeof(*ei));
- mpz_init_set(ei->left, left);
- mpz_init_set(ei->right, right);
- mpz_init(ei->size);
- mpz_sub(ei->size, right, left);
- if (expr != NULL)
- ei->expr = expr_get(expr);
- ei->flags = flags;
- return ei;
-}
-
-static void ei_destroy(struct elementary_interval *ei)
-{
- mpz_clear(ei->left);
- mpz_clear(ei->right);
- mpz_clear(ei->size);
- if (ei->expr != NULL)
- expr_free(ei->expr);
- xfree(ei);
-}
-
-/**
- * ei_lookup - find elementary interval containing point p
- *
- * @tree: segment tree
- * @p: the point
- */
-static struct elementary_interval *ei_lookup(struct seg_tree *tree, const mpz_t p)
-{
- struct rb_node *n = tree->root.rb_node;
- struct elementary_interval *ei;
-
- while (n != NULL) {
- ei = rb_entry(n, struct elementary_interval, rb_node);
-
- if (mpz_cmp(p, ei->left) >= 0 &&
- mpz_cmp(p, ei->right) <= 0)
- return ei;
- else if (mpz_cmp(p, ei->left) <= 0)
- n = n->rb_left;
- else if (mpz_cmp(p, ei->right) > 0)
- n = n->rb_right;
- }
- return NULL;
-}
-
-static void ei_remove(struct seg_tree *tree, struct elementary_interval *ei)
-{
- rb_erase(&ei->rb_node, &tree->root);
-}
-
-static void __ei_insert(struct seg_tree *tree, struct elementary_interval *new)
-{
- struct rb_node **p = &tree->root.rb_node;
- struct rb_node *parent = NULL;
- struct elementary_interval *ei;
-
- while (*p != NULL) {
- parent = *p;
- ei = rb_entry(parent, struct elementary_interval, rb_node);
-
- if (mpz_cmp(new->left, ei->left) >= 0 &&
- mpz_cmp(new->left, ei->right) <= 0)
- break;
- else if (mpz_cmp(new->left, ei->left) <= 0)
- p = &(*p)->rb_left;
- else if (mpz_cmp(new->left, ei->left) > 0)
- p = &(*p)->rb_right;
- }
-
- rb_link_node(&new->rb_node, parent, p);
- rb_insert_color(&new->rb_node, &tree->root);
-}
-
-static bool segtree_debug(unsigned int debug_mask)
-{
- if (debug_mask & NFT_DEBUG_SEGTREE)
- return true;
-
- return false;
-}
-
-/**
- * ei_insert - insert an elementary interval into the tree
- *
- * @tree: the seg_tree
- * @new: the elementary interval
- *
- * New entries take precedence over existing ones. Insertions are assumed to
- * be ordered by descending interval size, meaning the new interval never
- * extends over more than two existing intervals.
- */
-static int ei_insert(struct list_head *msgs, struct seg_tree *tree,
- struct elementary_interval *new, bool merge)
-{
- struct elementary_interval *lei, *rei, *ei;
- struct expr *new_expr, *expr;
- mpz_t p;
-
- mpz_init2(p, tree->keylen);
-
- /*
- * Lookup the intervals containing the left and right endpoints.
- */
- lei = ei_lookup(tree, new->left);
- rei = ei_lookup(tree, new->right);
-
- if (segtree_debug(tree->debug_mask))
- pr_gmp_debug("insert: [%Zx %Zx]\n", new->left, new->right);
-
- if (lei != NULL && rei != NULL && lei == rei) {
- if (!merge) {
- ei = lei;
- goto err;
- }
- /* single element contained in an existing interval */
- if (mpz_cmp(new->left, new->right) == 0) {
- ei_destroy(new);
- goto out;
- }
-
- /*
- * The new interval is entirely contained in the same interval,
- * split it into two parts:
- *
- * [lei_left, new_left) and (new_right, rei_right]
- */
- if (segtree_debug(tree->debug_mask))
- pr_gmp_debug("split [%Zx %Zx]\n", lei->left, lei->right);
-
- ei_remove(tree, lei);
-
- mpz_sub_ui(p, new->left, 1);
- if (mpz_cmp(lei->left, p) <= 0)
- __ei_insert(tree, ei_alloc(lei->left, p, lei->expr, 0));
-
- mpz_add_ui(p, new->right, 1);
- if (mpz_cmp(p, rei->right) < 0)
- __ei_insert(tree, ei_alloc(p, rei->right, lei->expr, 0));
- ei_destroy(lei);
- } else {
- if (lei != NULL) {
- if (!merge) {
- ei = lei;
- goto err;
- }
- /*
- * Left endpoint is within lei, adjust it so we have:
- *
- * [lei_left, new_left)[new_left, new_right]
- */
- if (segtree_debug(tree->debug_mask)) {
- pr_gmp_debug("adjust left [%Zx %Zx]\n",
- lei->left, lei->right);
- }
-
- mpz_sub_ui(lei->right, new->left, 1);
- mpz_sub(lei->size, lei->right, lei->left);
- if (mpz_sgn(lei->size) < 0) {
- ei_remove(tree, lei);
- ei_destroy(lei);
- }
- }
- if (rei != NULL) {
- if (!merge) {
- ei = rei;
- goto err;
- }
- /*
- * Right endpoint is within rei, adjust it so we have:
- *
- * [new_left, new_right](new_right, rei_right]
- */
- if (segtree_debug(tree->debug_mask)) {
- pr_gmp_debug("adjust right [%Zx %Zx]\n",
- rei->left, rei->right);
- }
-
- mpz_add_ui(rei->left, new->right, 1);
- mpz_sub(rei->size, rei->right, rei->left);
- if (mpz_sgn(rei->size) < 0) {
- ei_remove(tree, rei);
- ei_destroy(rei);
- }
- }
- }
-
- __ei_insert(tree, new);
-out:
- mpz_clear(p);
-
- return 0;
-err:
- mpz_clear(p);
- errno = EEXIST;
- if (new->expr->etype == EXPR_MAPPING) {
- new_expr = new->expr->left;
- expr = ei->expr->left;
- } else {
- new_expr = new->expr;
- expr = ei->expr;
- }
-
- return expr_binary_error(msgs, new_expr, expr,
- "conflicting intervals specified");
-}
-
-/*
- * Sort intervals according to their priority, which is defined inversely to
- * their size.
- *
- * The beginning of the interval is used as secondary sorting criterion. This
- * makes sure that overlapping ranges with equal priority are next to each
- * other, allowing to easily detect unsolvable conflicts during insertion.
- *
- * Note: unsolvable conflicts can only occur when using ranges or two identical
- * prefix specifications.
- */
-static int interval_cmp(const void *p1, const void *p2)
-{
- const struct elementary_interval *e1 = *(void * const *)p1;
- const struct elementary_interval *e2 = *(void * const *)p2;
- mpz_t d;
- int ret;
-
- mpz_init(d);
-
- mpz_sub(d, e2->size, e1->size);
- if (mpz_cmp_ui(d, 0))
- ret = mpz_sgn(d);
- else
- ret = mpz_cmp(e1->left, e2->left);
-
- mpz_clear(d);
- return ret;
-}
-
-static unsigned int expr_to_intervals(const struct expr *set,
- unsigned int keylen,
- struct elementary_interval **intervals)
-{
- struct elementary_interval *ei;
- struct expr *i, *next;
- unsigned int n;
- mpz_t low, high;
-
- mpz_init2(low, keylen);
- mpz_init2(high, keylen);
-
- /*
- * Convert elements to intervals.
- */
- n = 0;
- list_for_each_entry_safe(i, next, &set->expressions, list) {
- range_expr_value_low(low, i);
- range_expr_value_high(high, i);
- ei = ei_alloc(low, high, i, 0);
- intervals[n++] = ei;
- }
- mpz_clear(high);
- mpz_clear(low);
-
- return n;
-}
-
-static bool intervals_match(const struct elementary_interval *e1,
- const struct elementary_interval *e2)
-{
- return mpz_cmp(e1->left, e2->left) == 0 &&
- mpz_cmp(e1->right, e2->right) == 0;
-}
-
-/* This function checks for overlaps in two ways:
- *
- * 1) A new interval end intersects an existing interval.
- * 2) New intervals that are larger than existing ones, that don't intersect
- * at all, but that wrap the existing ones.
- */
-static bool interval_overlap(const struct elementary_interval *e1,
- const struct elementary_interval *e2)
-{
- if (intervals_match(e1, e2))
- return false;
-
- return (mpz_cmp(e1->left, e2->left) >= 0 &&
- mpz_cmp(e1->left, e2->right) <= 0) ||
- (mpz_cmp(e1->right, e2->left) >= 0 &&
- mpz_cmp(e1->right, e2->right) <= 0) ||
- (mpz_cmp(e1->left, e2->left) <= 0 &&
- mpz_cmp(e1->right, e2->right) >= 0);
-}
-
-static int set_overlap(struct list_head *msgs, const struct set *set,
- struct expr *init, unsigned int keylen, bool add)
-{
- struct elementary_interval *new_intervals[init->size + 1];
- struct elementary_interval *intervals[set->init->size + 1];
- unsigned int n, m, i, j;
- int ret = 0;
-
- n = expr_to_intervals(init, keylen, new_intervals);
- m = expr_to_intervals(set->init, keylen, intervals);
-
- for (i = 0; i < n; i++) {
- bool found = false;
-
- for (j = 0; j < m; j++) {
- if (add && interval_overlap(new_intervals[i],
- intervals[j])) {
- expr_error(msgs, new_intervals[i]->expr,
- "interval overlaps with an existing one");
- errno = EEXIST;
- ret = -1;
- goto out;
- } else if (!add && intervals_match(new_intervals[i],
- intervals[j])) {
- found = true;
- break;
- }
- }
- if (!add && !found) {
- expr_error(msgs, new_intervals[i]->expr,
- "interval not found in set");
- errno = ENOENT;
- ret = -1;
- break;
- }
- }
-out:
- for (i = 0; i < n; i++)
- ei_destroy(new_intervals[i]);
- for (i = 0; i < m; i++)
- ei_destroy(intervals[i]);
-
- return ret;
-}
-
-static int set_to_segtree(struct list_head *msgs, struct set *set,
- struct expr *init, struct seg_tree *tree,
- bool add, bool merge)
-{
- struct elementary_interval **intervals;
- struct expr *i, *next;
- unsigned int n, m;
- int err = 0;
-
- /* We are updating an existing set with new elements, check if the new
- * interval overlaps with any of the existing ones.
- */
- if (set->init && set->init != init) {
- err = set_overlap(msgs, set, init, tree->keylen, add);
- if (err < 0)
- return err;
- }
-
- intervals = xmalloc_array(init->size, sizeof(intervals[0]));
- n = expr_to_intervals(init, tree->keylen, intervals);
-
- list_for_each_entry_safe(i, next, &init->expressions, list) {
- list_del(&i->list);
- expr_free(i);
- }
-
- /*
- * Sort intervals by priority.
- */
- qsort(intervals, n, sizeof(intervals[0]), interval_cmp);
-
- /*
- * Insert elements into tree
- */
- for (n = 0; n < init->size; n++) {
- err = ei_insert(msgs, tree, intervals[n], merge);
- if (err < 0) {
- struct elementary_interval *ei;
- struct rb_node *node, *next;
-
- for (m = n; m < init->size; m++)
- ei_destroy(intervals[m]);
-
- rb_for_each_entry_safe(ei, node, next, &tree->root, rb_node) {
- ei_remove(tree, ei);
- ei_destroy(ei);
- }
- break;
- }
- }
-
- xfree(intervals);
- return err;
-}
-
-static bool segtree_needs_first_segment(const struct set *set,
- const struct expr *init, bool add)
-{
- if (add && !set->root) {
- /* Add the first segment in four situations:
- *
- * 1) This is an anonymous set.
- * 2) This set exists and it is empty.
- * 3) New empty set and, separately, new elements are added.
- * 4) This set is created with a number of initial elements.
- */
- if ((set_is_anonymous(set->flags)) ||
- (set->init && set->init->size == 0) ||
- (set->init == NULL && init) ||
- (set->init == init)) {
- return true;
- }
- }
- /* This is an update for a set that already contains elements, so don't
- * add the first non-matching elements otherwise we hit EEXIST.
- */
- return false;
-}
-
-static void segtree_linearize(struct list_head *list, const struct set *set,
- const struct expr *init, struct seg_tree *tree,
- bool add, bool merge)
-{
- bool needs_first_segment = segtree_needs_first_segment(set, init, add);
- struct elementary_interval *ei, *nei, *prev = NULL;
- struct rb_node *node, *next;
- mpz_t p, q;
-
- mpz_init2(p, tree->keylen);
- mpz_init2(q, tree->keylen);
-
- /*
- * Convert the tree of open intervals to half-closed map expressions.
- */
- rb_for_each_entry_safe(ei, node, next, &tree->root, rb_node) {
- if (segtree_debug(tree->debug_mask))
- pr_gmp_debug("iter: [%Zx %Zx]\n", ei->left, ei->right);
-
- if (prev == NULL) {
- /*
- * If the first segment doesn't begin at zero, insert a
- * non-matching segment to cover [0, first_left).
- */
- if (needs_first_segment && mpz_cmp_ui(ei->left, 0)) {
- mpz_set_ui(p, 0);
- mpz_sub_ui(q, ei->left, 1);
- nei = ei_alloc(p, q, NULL, EI_F_INTERVAL_END);
- list_add_tail(&nei->list, list);
- }
- } else {
- /*
- * If the previous segment doesn't end directly left to
- * this one, insert a non-matching segment to cover
- * (prev_right, ei_left).
- */
- mpz_add_ui(p, prev->right, 1);
- if (mpz_cmp(p, ei->left) < 0 ||
- (!set_is_anonymous(set->flags) && !merge)) {
- mpz_sub_ui(q, ei->left, 1);
- nei = ei_alloc(p, q, NULL, EI_F_INTERVAL_END);
- list_add_tail(&nei->list, list);
- } else if (add && merge &&
- ei->expr->etype != EXPR_MAPPING) {
- /* Merge contiguous segments only in case of
- * new additions.
- */
- mpz_set(prev->right, ei->right);
- ei_remove(tree, ei);
- ei_destroy(ei);
- continue;
- }
- }
-
- ei_remove(tree, ei);
- list_add_tail(&ei->list, list);
-
- prev = ei;
- }
-
- /*
- * If the last segment doesn't end at the right side of the dimension,
- * insert a non-matching segment to cover (last_right, end].
- */
- if (mpz_scan0(prev->right, 0) != tree->keylen) {
- mpz_add_ui(p, prev->right, 1);
- mpz_bitmask(q, tree->keylen);
- nei = ei_alloc(p, q, NULL, EI_F_INTERVAL_END);
- list_add_tail(&nei->list, list);
- } else {
- prev->flags |= EI_F_INTERVAL_OPEN;
- }
-
- mpz_clear(p);
- mpz_clear(q);
-}
static void interval_expr_copy(struct expr *dst, struct expr *src)
{
@@ -600,88 +32,6 @@ static void interval_expr_copy(struct expr *dst, struct expr *src)
list_splice_init(&src->stmt_list, &dst->stmt_list);
}
-static void set_insert_interval(struct expr *set, struct seg_tree *tree,
- const struct elementary_interval *ei)
-{
- struct expr *expr;
-
- expr = constant_expr_alloc(&internal_location, tree->keytype,
- tree->byteorder, tree->keylen, NULL);
- mpz_set(expr->value, ei->left);
- expr = set_elem_expr_alloc(&internal_location, expr);
-
- if (ei->expr != NULL) {
- if (ei->expr->etype == EXPR_MAPPING) {
- interval_expr_copy(expr, ei->expr->left);
- expr = mapping_expr_alloc(&ei->expr->location, expr,
- expr_get(ei->expr->right));
- } else {
- interval_expr_copy(expr, ei->expr);
- }
- }
-
- if (ei->flags & EI_F_INTERVAL_END)
- expr->flags |= EXPR_F_INTERVAL_END;
- if (ei->flags & EI_F_INTERVAL_OPEN)
- expr->elem_flags |= NFTNL_SET_ELEM_F_INTERVAL_OPEN;
-
- compound_expr_add(set, expr);
-}
-
-int set_to_intervals(struct list_head *errs, struct set *set,
- struct expr *init, bool add, unsigned int debug_mask,
- bool merge, struct output_ctx *octx)
-{
- struct expr *catchall = NULL, *i, *in, *key;
- struct elementary_interval *ei, *next;
- struct seg_tree tree;
- LIST_HEAD(list);
-
- list_for_each_entry_safe(i, in, &init->expressions, list) {
- if (i->etype == EXPR_MAPPING)
- key = i->left->key;
- else if (i->etype == EXPR_SET_ELEM)
- key = i->key;
- else
- continue;
-
- if (key->etype == EXPR_SET_ELEM_CATCHALL) {
- init->size--;
- catchall = i;
- list_del(&i->list);
- break;
- }
- }
-
- seg_tree_init(&tree, set, init, debug_mask);
- if (set_to_segtree(errs, set, init, &tree, add, merge) < 0)
- return -1;
- segtree_linearize(&list, set, init, &tree, add, merge);
-
- init->size = 0;
- list_for_each_entry_safe(ei, next, &list, list) {
- if (segtree_debug(tree.debug_mask)) {
- pr_gmp_debug("list: [%.*Zx %.*Zx]\n",
- 2 * tree.keylen / BITS_PER_BYTE, ei->left,
- 2 * tree.keylen / BITS_PER_BYTE, ei->right);
- }
- set_insert_interval(init, &tree, ei);
- ei_destroy(ei);
- }
-
- if (segtree_debug(tree.debug_mask)) {
- expr_print(init, octx);
- pr_gmp_debug("\n");
- }
-
- if (catchall) {
- list_add_tail(&catchall->list, &init->expressions);
- init->size++;
- }
-
- return 0;
-}
-
static void set_elem_add(const struct set *set, struct expr *init, mpz_t value,
uint32_t flags, enum byteorder byteorder)
{
--
2.30.2
^ permalink raw reply related [flat|nested] 16+ messages in thread
* [PATCH nft,v4 3/7] src: remove rbtree datastructure
2022-04-12 14:47 [PATCH nft,v4 0/7] revisit overlap/automerge codebase Pablo Neira Ayuso
2022-04-12 14:47 ` [PATCH nft,v4 1/7] src: add EXPR_F_KERNEL to identify expression in the kernel Pablo Neira Ayuso
2022-04-12 14:47 ` [PATCH nft,v4 2/7] src: replace interval segment tree overlap and automerge Pablo Neira Ayuso
@ 2022-04-12 14:47 ` Pablo Neira Ayuso
2022-04-12 14:47 ` [PATCH nft,v4 4/7] mnl: update mnl_nft_setelem_del() to allow for more reuse Pablo Neira Ayuso
` (3 subsequent siblings)
6 siblings, 0 replies; 16+ messages in thread
From: Pablo Neira Ayuso @ 2022-04-12 14:47 UTC (permalink / raw)
To: netfilter-devel
Not used by anyone anymore, remove it.
Signed-off-by: Pablo Neira Ayuso <pablo@netfilter.org>
---
include/Makefile.am | 1 -
include/rbtree.h | 98 -----------
src/Makefile.am | 1 -
src/rbtree.c | 388 --------------------------------------------
4 files changed, 488 deletions(-)
delete mode 100644 include/rbtree.h
delete mode 100644 src/rbtree.c
diff --git a/include/Makefile.am b/include/Makefile.am
index 940b7fafb0b4..ff56dfe45fc5 100644
--- a/include/Makefile.am
+++ b/include/Makefile.am
@@ -17,7 +17,6 @@ noinst_HEADERS = cli.h \
mnl.h \
nftables.h \
payload.h \
- rbtree.h \
tcpopt.h \
statement.h \
ct.h \
diff --git a/include/rbtree.h b/include/rbtree.h
deleted file mode 100644
index ac65283fee5b..000000000000
--- a/include/rbtree.h
+++ /dev/null
@@ -1,98 +0,0 @@
-/*
- * Red Black Trees
- * (C) 1999 Andrea Arcangeli <andrea@suse.de>
- *
- * This program is free software; you can redistribute it and/or modify
- * it under the terms of the GNU General Public License as published by
- * the Free Software Foundation; either version 2 of the License, or
- * (at your option) any later version.
- *
- * This program is distributed in the hope that it will be useful,
- * but WITHOUT ANY WARRANTY; without even the implied warranty of
- * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
- * GNU General Public License for more details.
- *
- * You should have received a copy of the GNU General Public License
- * along with this program; if not, write to the Free Software
- * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
- *
- */
-
-#ifndef NFTABLES_RBTREE_H
-#define NFTABLES_RBTREE_H
-
-#include <stddef.h>
-
-struct rb_node
-{
- unsigned long rb_parent_color;
-#define RB_RED 0
-#define RB_BLACK 1
- struct rb_node *rb_right;
- struct rb_node *rb_left;
-};
-
-struct rb_root
-{
- struct rb_node *rb_node;
-};
-
-#define rb_parent(r) ((struct rb_node *)((r)->rb_parent_color & ~3))
-#define rb_color(r) ((r)->rb_parent_color & 1)
-#define rb_is_red(r) (!rb_color(r))
-#define rb_is_black(r) rb_color(r)
-#define rb_set_red(r) do { (r)->rb_parent_color &= ~1; } while (0)
-#define rb_set_black(r) do { (r)->rb_parent_color |= 1; } while (0)
-
-static inline void rb_set_parent(struct rb_node *rb, struct rb_node *p)
-{
- rb->rb_parent_color = (rb->rb_parent_color & 3) | (unsigned long)p;
-}
-static inline void rb_set_color(struct rb_node *rb, int color)
-{
- rb->rb_parent_color = (rb->rb_parent_color & ~1) | color;
-}
-
-#define RB_ROOT (struct rb_root) { NULL, }
-#define rb_entry(ptr, type, member) container_of(ptr, type, member)
-
-#define RB_EMPTY_ROOT(root) ((root)->rb_node == NULL)
-#define RB_EMPTY_NODE(node) (rb_parent(node) == node)
-#define RB_CLEAR_NODE(node) (rb_set_parent(node, node))
-
-extern void rb_insert_color(struct rb_node *, struct rb_root *);
-extern void rb_erase(struct rb_node *, struct rb_root *);
-
-/* Find logical next and previous nodes in a tree */
-extern struct rb_node *rb_next(struct rb_node *);
-extern struct rb_node *rb_prev(struct rb_node *);
-extern struct rb_node *rb_first(struct rb_root *);
-extern struct rb_node *rb_last(struct rb_root *);
-
-/* Fast replacement of a single node without remove/rebalance/add/rebalance */
-extern void rb_replace_node(struct rb_node *victim, struct rb_node *new,
- struct rb_root *root);
-
-static inline void rb_link_node(struct rb_node * node, struct rb_node * parent,
- struct rb_node ** rb_link)
-{
- node->rb_parent_color = (unsigned long )parent;
- node->rb_left = node->rb_right = NULL;
-
- *rb_link = node;
-}
-
-#define rb_for_each_entry(pos, root, member) \
- for ((pos) = (root)->rb_node ? \
- rb_entry(rb_first(root), typeof(*pos), member) : NULL; \
- (pos) != NULL; \
- (pos) = rb_entry(rb_next(&(pos)->member), typeof(*pos), member))
-
-#define rb_for_each_entry_safe(pos, node, next, root, member) \
- for ((node) = rb_first(root); \
- (pos) = (node) ? rb_entry((node), typeof(*pos), member) : NULL, \
- (next) = (node) ? rb_next(node) : NULL, \
- (pos) != NULL; \
- (node) = (next))
-
-#endif /* NFTABLES_RBTREE_H */
diff --git a/src/Makefile.am b/src/Makefile.am
index fe0632e7c37d..264d981e20c7 100644
--- a/src/Makefile.am
+++ b/src/Makefile.am
@@ -62,7 +62,6 @@ libnftables_la_SOURCES = \
monitor.c \
owner.c \
segtree.c \
- rbtree.c \
gmputil.c \
utils.c \
erec.c \
diff --git a/src/rbtree.c b/src/rbtree.c
deleted file mode 100644
index 325c0123398f..000000000000
--- a/src/rbtree.c
+++ /dev/null
@@ -1,388 +0,0 @@
-/*
- * Red Black Trees
- * (C) 1999 Andrea Arcangeli <andrea@suse.de>
- * (C) 2002 David Woodhouse <dwmw2@infradead.org>
- *
- * This program is free software; you can redistribute it and/or modify
- * it under the terms of the GNU General Public License as published by
- * the Free Software Foundation; either version 2 of the License, or
- * (at your option) any later version.
- *
- * This program is distributed in the hope that it will be useful,
- * but WITHOUT ANY WARRANTY; without even the implied warranty of
- * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
- * GNU General Public License for more details.
- *
- * You should have received a copy of the GNU General Public License
- * along with this program; if not, write to the Free Software
- * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
- *
- */
-
-#include <rbtree.h>
-
-static void __rb_rotate_left(struct rb_node *node, struct rb_root *root)
-{
- struct rb_node *right = node->rb_right;
- struct rb_node *parent = rb_parent(node);
-
- if ((node->rb_right = right->rb_left))
- rb_set_parent(right->rb_left, node);
- right->rb_left = node;
-
- rb_set_parent(right, parent);
-
- if (parent)
- {
- if (node == parent->rb_left)
- parent->rb_left = right;
- else
- parent->rb_right = right;
- }
- else
- root->rb_node = right;
- rb_set_parent(node, right);
-}
-
-static void __rb_rotate_right(struct rb_node *node, struct rb_root *root)
-{
- struct rb_node *left = node->rb_left;
- struct rb_node *parent = rb_parent(node);
-
- if ((node->rb_left = left->rb_right))
- rb_set_parent(left->rb_right, node);
- left->rb_right = node;
-
- rb_set_parent(left, parent);
-
- if (parent)
- {
- if (node == parent->rb_right)
- parent->rb_right = left;
- else
- parent->rb_left = left;
- }
- else
- root->rb_node = left;
- rb_set_parent(node, left);
-}
-
-void rb_insert_color(struct rb_node *node, struct rb_root *root)
-{
- struct rb_node *parent, *gparent;
-
- while ((parent = rb_parent(node)) && rb_is_red(parent))
- {
- gparent = rb_parent(parent);
-
- if (parent == gparent->rb_left)
- {
- {
- register struct rb_node *uncle = gparent->rb_right;
- if (uncle && rb_is_red(uncle))
- {
- rb_set_black(uncle);
- rb_set_black(parent);
- rb_set_red(gparent);
- node = gparent;
- continue;
- }
- }
-
- if (parent->rb_right == node)
- {
- register struct rb_node *tmp;
- __rb_rotate_left(parent, root);
- tmp = parent;
- parent = node;
- node = tmp;
- }
-
- rb_set_black(parent);
- rb_set_red(gparent);
- __rb_rotate_right(gparent, root);
- } else {
- {
- register struct rb_node *uncle = gparent->rb_left;
- if (uncle && rb_is_red(uncle))
- {
- rb_set_black(uncle);
- rb_set_black(parent);
- rb_set_red(gparent);
- node = gparent;
- continue;
- }
- }
-
- if (parent->rb_left == node)
- {
- register struct rb_node *tmp;
- __rb_rotate_right(parent, root);
- tmp = parent;
- parent = node;
- node = tmp;
- }
-
- rb_set_black(parent);
- rb_set_red(gparent);
- __rb_rotate_left(gparent, root);
- }
- }
-
- rb_set_black(root->rb_node);
-}
-
-static void __rb_erase_color(struct rb_node *node, struct rb_node *parent,
- struct rb_root *root)
-{
- struct rb_node *other;
-
- while ((!node || rb_is_black(node)) && node != root->rb_node)
- {
- if (parent->rb_left == node)
- {
- other = parent->rb_right;
- if (rb_is_red(other))
- {
- rb_set_black(other);
- rb_set_red(parent);
- __rb_rotate_left(parent, root);
- other = parent->rb_right;
- }
- if ((!other->rb_left || rb_is_black(other->rb_left)) &&
- (!other->rb_right || rb_is_black(other->rb_right)))
- {
- rb_set_red(other);
- node = parent;
- parent = rb_parent(node);
- }
- else
- {
- if (!other->rb_right || rb_is_black(other->rb_right))
- {
- struct rb_node *o_left;
- if ((o_left = other->rb_left))
- rb_set_black(o_left);
- rb_set_red(other);
- __rb_rotate_right(other, root);
- other = parent->rb_right;
- }
- rb_set_color(other, rb_color(parent));
- rb_set_black(parent);
- if (other->rb_right)
- rb_set_black(other->rb_right);
- __rb_rotate_left(parent, root);
- node = root->rb_node;
- break;
- }
- }
- else
- {
- other = parent->rb_left;
- if (rb_is_red(other))
- {
- rb_set_black(other);
- rb_set_red(parent);
- __rb_rotate_right(parent, root);
- other = parent->rb_left;
- }
- if ((!other->rb_left || rb_is_black(other->rb_left)) &&
- (!other->rb_right || rb_is_black(other->rb_right)))
- {
- rb_set_red(other);
- node = parent;
- parent = rb_parent(node);
- }
- else
- {
- if (!other->rb_left || rb_is_black(other->rb_left))
- {
- register struct rb_node *o_right;
- if ((o_right = other->rb_right))
- rb_set_black(o_right);
- rb_set_red(other);
- __rb_rotate_left(other, root);
- other = parent->rb_left;
- }
- rb_set_color(other, rb_color(parent));
- rb_set_black(parent);
- if (other->rb_left)
- rb_set_black(other->rb_left);
- __rb_rotate_right(parent, root);
- node = root->rb_node;
- break;
- }
- }
- }
- if (node)
- rb_set_black(node);
-}
-
-void rb_erase(struct rb_node *node, struct rb_root *root)
-{
- struct rb_node *child, *parent;
- int color;
-
- if (!node->rb_left)
- child = node->rb_right;
- else if (!node->rb_right)
- child = node->rb_left;
- else
- {
- struct rb_node *old = node, *left;
-
- node = node->rb_right;
- while ((left = node->rb_left) != NULL)
- node = left;
- child = node->rb_right;
- parent = rb_parent(node);
- color = rb_color(node);
-
- if (child)
- rb_set_parent(child, parent);
- if (parent == old) {
- parent->rb_right = child;
- parent = node;
- } else
- parent->rb_left = child;
-
- node->rb_parent_color = old->rb_parent_color;
- node->rb_right = old->rb_right;
- node->rb_left = old->rb_left;
-
- if (rb_parent(old))
- {
- if (rb_parent(old)->rb_left == old)
- rb_parent(old)->rb_left = node;
- else
- rb_parent(old)->rb_right = node;
- } else
- root->rb_node = node;
-
- rb_set_parent(old->rb_left, node);
- if (old->rb_right)
- rb_set_parent(old->rb_right, node);
- goto color;
- }
-
- parent = rb_parent(node);
- color = rb_color(node);
-
- if (child)
- rb_set_parent(child, parent);
- if (parent)
- {
- if (parent->rb_left == node)
- parent->rb_left = child;
- else
- parent->rb_right = child;
- }
- else
- root->rb_node = child;
-
- color:
- if (color == RB_BLACK)
- __rb_erase_color(child, parent, root);
-}
-
-/*
- * This function returns the first node (in sort order) of the tree.
- */
-struct rb_node *rb_first(struct rb_root *root)
-{
- struct rb_node *n;
-
- n = root->rb_node;
- if (!n)
- return NULL;
- while (n->rb_left)
- n = n->rb_left;
- return n;
-}
-
-struct rb_node *rb_last(struct rb_root *root)
-{
- struct rb_node *n;
-
- n = root->rb_node;
- if (!n)
- return NULL;
- while (n->rb_right)
- n = n->rb_right;
- return n;
-}
-
-struct rb_node *rb_next(struct rb_node *node)
-{
- struct rb_node *parent;
-
- if (rb_parent(node) == node)
- return NULL;
-
- /* If we have a right-hand child, go down and then left as far
- as we can. */
- if (node->rb_right) {
- node = node->rb_right;
- while (node->rb_left)
- node=node->rb_left;
- return node;
- }
-
- /* No right-hand children. Everything down and left is
- smaller than us, so any 'next' node must be in the general
- direction of our parent. Go up the tree; any time the
- ancestor is a right-hand child of its parent, keep going
- up. First time it's a left-hand child of its parent, said
- parent is our 'next' node. */
- while ((parent = rb_parent(node)) && node == parent->rb_right)
- node = parent;
-
- return parent;
-}
-
-struct rb_node *rb_prev(struct rb_node *node)
-{
- struct rb_node *parent;
-
- if (rb_parent(node) == node)
- return NULL;
-
- /* If we have a left-hand child, go down and then right as far
- as we can. */
- if (node->rb_left) {
- node = node->rb_left;
- while (node->rb_right)
- node=node->rb_right;
- return node;
- }
-
- /* No left-hand children. Go up till we find an ancestor which
- is a right-hand child of its parent */
- while ((parent = rb_parent(node)) && node == parent->rb_left)
- node = parent;
-
- return parent;
-}
-
-void rb_replace_node(struct rb_node *victim, struct rb_node *new,
- struct rb_root *root)
-{
- struct rb_node *parent = rb_parent(victim);
-
- /* Set the surrounding nodes to point to the replacement */
- if (parent) {
- if (victim == parent->rb_left)
- parent->rb_left = new;
- else
- parent->rb_right = new;
- } else {
- root->rb_node = new;
- }
- if (victim->rb_left)
- rb_set_parent(victim->rb_left, new);
- if (victim->rb_right)
- rb_set_parent(victim->rb_right, new);
-
- /* Copy the pointers/colour from the victim to the replacement */
- *new = *victim;
-}
--
2.30.2
^ permalink raw reply related [flat|nested] 16+ messages in thread
* [PATCH nft,v4 4/7] mnl: update mnl_nft_setelem_del() to allow for more reuse
2022-04-12 14:47 [PATCH nft,v4 0/7] revisit overlap/automerge codebase Pablo Neira Ayuso
` (2 preceding siblings ...)
2022-04-12 14:47 ` [PATCH nft,v4 3/7] src: remove rbtree datastructure Pablo Neira Ayuso
@ 2022-04-12 14:47 ` Pablo Neira Ayuso
2022-04-12 14:47 ` [PATCH nft,v4 5/7] intervals: add support to automerge with kernel elements Pablo Neira Ayuso
` (2 subsequent siblings)
6 siblings, 0 replies; 16+ messages in thread
From: Pablo Neira Ayuso @ 2022-04-12 14:47 UTC (permalink / raw)
To: netfilter-devel
Pass handle and element list as parameters to allow for code reuse.
Signed-off-by: Pablo Neira Ayuso <pablo@netfilter.org>
---
include/mnl.h | 3 ++-
src/mnl.c | 6 +++---
src/rule.c | 2 +-
3 files changed, 6 insertions(+), 5 deletions(-)
diff --git a/include/mnl.h b/include/mnl.h
index a4abe1ae3242..4c701d4ee6dc 100644
--- a/include/mnl.h
+++ b/include/mnl.h
@@ -62,7 +62,8 @@ struct nftnl_set_list *mnl_nft_set_dump(struct netlink_ctx *ctx, int family,
int mnl_nft_setelem_add(struct netlink_ctx *ctx, const struct set *set,
const struct expr *expr, unsigned int flags);
-int mnl_nft_setelem_del(struct netlink_ctx *ctx, const struct cmd *cmd);
+int mnl_nft_setelem_del(struct netlink_ctx *ctx, const struct handle *h,
+ 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);
struct nftnl_set *mnl_nft_setelem_get_one(struct netlink_ctx *ctx,
diff --git a/src/mnl.c b/src/mnl.c
index e83e0a16b491..7dd77be1bec0 100644
--- a/src/mnl.c
+++ b/src/mnl.c
@@ -1728,9 +1728,9 @@ int mnl_nft_setelem_flush(struct netlink_ctx *ctx, const struct cmd *cmd)
return 0;
}
-int mnl_nft_setelem_del(struct netlink_ctx *ctx, const struct cmd *cmd)
+int mnl_nft_setelem_del(struct netlink_ctx *ctx, const struct handle *h,
+ const struct expr *init)
{
- const struct handle *h = &cmd->handle;
struct nftnl_set *nls;
int err;
@@ -1748,7 +1748,7 @@ int mnl_nft_setelem_del(struct netlink_ctx *ctx, const struct cmd *cmd)
netlink_dump_set(nls, ctx);
err = mnl_nft_setelem_batch(nls, ctx->batch, NFT_MSG_DELSETELEM, 0,
- ctx->seqnum, cmd->expr, ctx);
+ ctx->seqnum, init, ctx);
nftnl_set_free(nls);
return err;
diff --git a/src/rule.c b/src/rule.c
index 89f1304b8222..44e1febf0793 100644
--- a/src/rule.c
+++ b/src/rule.c
@@ -1601,7 +1601,7 @@ static int do_delete_setelems(struct netlink_ctx *ctx, struct cmd *cmd)
set_to_intervals(set, expr, false) < 0)
return -1;
- if (mnl_nft_setelem_del(ctx, cmd) < 0)
+ if (mnl_nft_setelem_del(ctx, &cmd->handle, cmd->elem.expr) < 0)
return -1;
return 0;
--
2.30.2
^ permalink raw reply related [flat|nested] 16+ messages in thread
* [PATCH nft,v4 5/7] intervals: add support to automerge with kernel elements
2022-04-12 14:47 [PATCH nft,v4 0/7] revisit overlap/automerge codebase Pablo Neira Ayuso
` (3 preceding siblings ...)
2022-04-12 14:47 ` [PATCH nft,v4 4/7] mnl: update mnl_nft_setelem_del() to allow for more reuse Pablo Neira Ayuso
@ 2022-04-12 14:47 ` Pablo Neira Ayuso
2022-04-12 14:47 ` [PATCH nft,v4 6/7] evaluate: allow for zero length ranges Pablo Neira Ayuso
2022-04-12 14:47 ` [PATCH nft,v4 7/7] intervals: support to partial deletion with automerge Pablo Neira Ayuso
6 siblings, 0 replies; 16+ messages in thread
From: Pablo Neira Ayuso @ 2022-04-12 14:47 UTC (permalink / raw)
To: netfilter-devel
Extend the interval codebase to support for merging elements in the
kernel with userspace element updates.
Add a list of elements to be purged to cmd and set objects. These
elements representing outdated intervals are deleted before adding the
updated ranges.
This routine splices the list of userspace and kernel elements, then it
mergesorts to identify overlapping and contiguous ranges. This splice
operation is undone so the set userspace cache remains consistent.
Incrementally update the elements in the cache, this allows to remove
dd44081d91ce ("segtree: Fix add and delete of element in same batch").
Signed-off-by: Pablo Neira Ayuso <pablo@netfilter.org>
---
include/intervals.h | 3 +-
src/cache.c | 6 +
src/evaluate.c | 8 +-
src/intervals.c | 144 ++++++++++++++----
src/rule.c | 10 --
.../shell/testcases/sets/0069interval_merge_0 | 28 ++++
.../sets/dumps/0069interval_merge_0.nft | 9 ++
7 files changed, 168 insertions(+), 40 deletions(-)
create mode 100755 tests/shell/testcases/sets/0069interval_merge_0
create mode 100644 tests/shell/testcases/sets/dumps/0069interval_merge_0.nft
diff --git a/include/intervals.h b/include/intervals.h
index f69800638070..797129fc93a5 100644
--- a/include/intervals.h
+++ b/include/intervals.h
@@ -2,7 +2,8 @@
#define NFTABLES_INTERVALS_H
void set_to_range(struct expr *init);
-int set_automerge(struct list_head *msgs, struct set *set, struct expr *init);
+int set_automerge(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);
diff --git a/src/cache.c b/src/cache.c
index 8e8387f91955..fd8df884c095 100644
--- a/src/cache.c
+++ b/src/cache.c
@@ -19,6 +19,8 @@
static unsigned int evaluate_cache_add(struct cmd *cmd, unsigned int flags)
{
+ struct set *set;
+
switch (cmd->obj) {
case CMD_OBJ_TABLE:
if (!cmd->table)
@@ -29,6 +31,10 @@ static unsigned int evaluate_cache_add(struct cmd *cmd, unsigned int flags)
NFT_CACHE_SET |
NFT_CACHE_OBJECT |
NFT_CACHE_FLOWTABLE;
+ list_for_each_entry(set, &cmd->table->sets, list) {
+ if (set->automerge)
+ flags |= NFT_CACHE_SETELEM_MAYBE;
+ }
break;
case CMD_OBJ_CHAIN:
case CMD_OBJ_SET:
diff --git a/src/evaluate.c b/src/evaluate.c
index 1b20d76f8111..9951a8349249 100644
--- a/src/evaluate.c
+++ b/src/evaluate.c
@@ -1466,10 +1466,12 @@ static int interval_set_eval(struct eval_ctx *ctx, struct set *set,
switch (ctx->cmd->op) {
case CMD_CREATE:
case CMD_ADD:
- if (set->automerge)
- ret = set_automerge(ctx->msgs, set, init);
- else
+ if (set->automerge) {
+ ret = set_automerge(ctx->msgs, ctx->cmd, set, init,
+ ctx->nft->debug_mask);
+ } else {
ret = set_overlap(ctx->msgs, set, init);
+ }
break;
case CMD_DELETE:
set_to_range(init);
diff --git a/src/intervals.c b/src/intervals.c
index c6f66e634d4c..16debf9cd4be 100644
--- a/src/intervals.c
+++ b/src/intervals.c
@@ -51,11 +51,33 @@ static void setelem_expr_to_range(struct expr *expr)
}
}
-static void remove_overlapping_range(struct expr *i, struct expr *init)
+struct set_automerge_ctx {
+ struct set *set;
+ struct expr *init;
+ struct expr *purge;
+ unsigned int debug_mask;
+};
+
+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);
+ }
+ list_move_tail(&i->list, &ctx->purge->expressions);
+}
+
+static void remove_overlapping_range(struct set_automerge_ctx *ctx,
+ struct expr *prev, struct expr *i)
+{
+ if (i->flags & EXPR_F_KERNEL) {
+ purge_elem(ctx, i);
+ return;
+ }
list_del(&i->list);
expr_free(i);
- init->size--;
+ ctx->init->size--;
}
struct range {
@@ -63,20 +85,33 @@ struct range {
mpz_t high;
};
-static void merge_ranges(struct expr *prev, struct expr *i,
- struct range *prev_range, struct range *range,
- struct expr *init)
+static bool merge_ranges(struct set_automerge_ctx *ctx,
+ struct expr *prev, struct expr *i,
+ struct range *prev_range, struct range *range)
{
- expr_free(prev->key->right);
- prev->key->right = expr_get(i->key->right);
- list_del(&i->list);
- expr_free(i);
- mpz_set(prev_range->high, range->high);
- init->size--;
+ if (prev->flags & EXPR_F_KERNEL) {
+ purge_elem(ctx, prev);
+ expr_free(i->key->left);
+ i->key->left = expr_get(prev->key->left);
+ mpz_set(prev_range->high, range->high);
+ return true;
+ } else if (i->flags & EXPR_F_KERNEL) {
+ purge_elem(ctx, i);
+ expr_free(prev->key->right);
+ prev->key->right = expr_get(i->key->right);
+ mpz_set(prev_range->high, range->high);
+ } else {
+ expr_free(prev->key->right);
+ prev->key->right = expr_get(i->key->right);
+ mpz_set(prev_range->high, range->high);
+ list_del(&i->list);
+ expr_free(i);
+ ctx->init->size--;
+ }
+ return false;
}
-static void setelem_automerge(struct list_head *msgs, struct set *set,
- struct expr *init)
+static void setelem_automerge(struct set_automerge_ctx *ctx)
{
struct expr *i, *next, *prev = NULL;
struct range range, prev_range;
@@ -88,7 +123,7 @@ static void setelem_automerge(struct list_head *msgs, struct set *set,
mpz_init(range.high);
mpz_init(rop);
- list_for_each_entry_safe(i, next, &init->expressions, list) {
+ list_for_each_entry_safe(i, next, &ctx->init->expressions, list) {
if (i->key->etype == EXPR_SET_ELEM_CATCHALL)
continue;
@@ -104,16 +139,18 @@ static void setelem_automerge(struct list_head *msgs, struct set *set,
if (mpz_cmp(prev_range.low, range.low) <= 0 &&
mpz_cmp(prev_range.high, range.high) >= 0) {
- remove_overlapping_range(i, init);
+ remove_overlapping_range(ctx, prev, i);
continue;
} else if (mpz_cmp(range.low, prev_range.high) <= 0) {
- merge_ranges(prev, i, &prev_range, &range, init);
+ if (merge_ranges(ctx, prev, i, &prev_range, &range))
+ prev = i;
continue;
- } else if (set->automerge) {
+ } else if (ctx->set->automerge) {
mpz_sub(rop, range.low, prev_range.high);
/* two contiguous ranges */
if (mpz_cmp_ui(rop, 1) == 0) {
- merge_ranges(prev, i, &prev_range, &range, init);
+ if (merge_ranges(ctx, prev, i, &prev_range, &range))
+ prev = i;
continue;
}
}
@@ -157,18 +194,63 @@ void set_to_range(struct expr *init)
elem = interval_expr_key(i);
setelem_expr_to_range(elem);
}
-
- list_expr_sort(&init->expressions);
}
-int set_automerge(struct list_head *msgs, struct set *set, struct expr *init)
+int set_automerge(struct list_head *msgs, struct cmd *cmd, struct set *set,
+ struct expr *init, unsigned int debug_mask)
{
+ struct set *existing_set = set->existing_set;
+ struct set_automerge_ctx ctx = {
+ .set = set,
+ .init = init,
+ .debug_mask = debug_mask,
+ };
+ struct expr *i, *next, *clone;
+ struct cmd *purge_cmd;
+ struct handle h = {};
+
+ if (existing_set) {
+ if (existing_set->init) {
+ list_splice_init(&existing_set->init->expressions,
+ &init->expressions);
+ } else {
+ existing_set->init = set_expr_alloc(&internal_location,
+ set);
+ }
+ }
+
set_to_range(init);
+ list_expr_sort(&init->expressions);
if (set->flags & NFT_SET_MAP)
return 0;
- setelem_automerge(msgs, set, init);
+ ctx.purge = set_expr_alloc(&internal_location, set);
+
+ setelem_automerge(&ctx);
+
+ list_for_each_entry_safe(i, next, &init->expressions, list) {
+ if (i->flags & EXPR_F_KERNEL) {
+ list_move_tail(&i->list, &existing_set->init->expressions);
+ } 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);
+ }
+ clone = expr_clone(i);
+ list_add_tail(&clone->list, &existing_set->init->expressions);
+ }
+ }
+
+ if (list_empty(&ctx.purge->expressions)) {
+ expr_free(ctx.purge);
+ return 0;
+ }
+
+ handle_merge(&h, &set->handle);
+ purge_cmd = cmd_alloc(CMD_DELETE, CMD_OBJ_ELEMENTS, &h, &init->location, ctx.purge);
+ purge_cmd->elem.set = set_get(set);
+ list_add_tail(&purge_cmd->list, &cmd->list);
return 0;
}
@@ -250,21 +332,31 @@ err_out:
int set_overlap(struct list_head *msgs, struct set *set, struct expr *init)
{
struct set *existing_set = set->existing_set;
- struct expr *i, *n;
+ struct expr *i, *n, *clone;
int err;
- if (existing_set && existing_set->init) {
- list_splice_init(&existing_set->init->expressions,
- &init->expressions);
+ if (existing_set) {
+ if (existing_set->init) {
+ list_splice_init(&existing_set->init->expressions,
+ &init->expressions);
+ } else {
+ existing_set->init = set_expr_alloc(&internal_location,
+ set);
+ }
}
set_to_range(init);
+ list_expr_sort(&init->expressions);
err = setelem_overlap(msgs, set, init);
list_for_each_entry_safe(i, n, &init->expressions, list) {
if (i->flags & EXPR_F_KERNEL)
list_move_tail(&i->list, &existing_set->init->expressions);
+ else if (existing_set) {
+ clone = expr_clone(i);
+ list_add_tail(&clone->list, &existing_set->init->expressions);
+ }
}
return err;
diff --git a/src/rule.c b/src/rule.c
index 44e1febf0793..799092eb15c5 100644
--- a/src/rule.c
+++ b/src/rule.c
@@ -1476,16 +1476,6 @@ static int __do_add_elements(struct netlink_ctx *ctx, struct set *set,
if (mnl_nft_setelem_add(ctx, set, expr, flags) < 0)
return -1;
- if (!set_is_anonymous(set->flags) &&
- set->init != NULL && set->init != expr &&
- set->flags & NFT_SET_INTERVAL &&
- set->desc.field_count <= 1) {
- interval_map_decompose(expr);
- list_splice_tail_init(&expr->expressions, &set->init->expressions);
- set->init->size += expr->size;
- expr->size = 0;
- }
-
return 0;
}
diff --git a/tests/shell/testcases/sets/0069interval_merge_0 b/tests/shell/testcases/sets/0069interval_merge_0
new file mode 100755
index 000000000000..edb6422a1fc0
--- /dev/null
+++ b/tests/shell/testcases/sets/0069interval_merge_0
@@ -0,0 +1,28 @@
+#!/bin/bash
+
+set -e
+
+RULESET="table ip x {
+ set y {
+ type ipv4_addr
+ flags interval
+ auto-merge
+ elements = { 1.2.3.0, 1.2.3.255, 1.2.3.0/24, 3.3.3.3, 4.4.4.4, 4.4.4.4-4.4.4.8, 3.3.3.4, 3.3.3.5 }
+ }
+}"
+
+$NFT -f - <<< $RULESET
+
+RULESET="table ip x {
+ set y {
+ type ipv4_addr
+ flags interval
+ auto-merge
+ elements = { 1.2.4.0, 3.3.3.6, 4.4.4.0/24 }
+ }
+}"
+
+$NFT -f - <<< $RULESET
+
+$NFT add element ip x y { 1.2.3.0-1.2.4.255, 3.3.3.5, 4.4.4.1 }
+$NFT add element ip x y { 1.2.3.0-1.2.4.255, 3.3.3.5, 4.4.5.0 }
diff --git a/tests/shell/testcases/sets/dumps/0069interval_merge_0.nft b/tests/shell/testcases/sets/dumps/0069interval_merge_0.nft
new file mode 100644
index 000000000000..2d4e1706f43e
--- /dev/null
+++ b/tests/shell/testcases/sets/dumps/0069interval_merge_0.nft
@@ -0,0 +1,9 @@
+table ip x {
+ set y {
+ type ipv4_addr
+ flags interval
+ auto-merge
+ elements = { 1.2.3.0-1.2.4.255, 3.3.3.3-3.3.3.6,
+ 4.4.4.0-4.4.5.0 }
+ }
+}
--
2.30.2
^ permalink raw reply related [flat|nested] 16+ messages in thread
* [PATCH nft,v4 6/7] evaluate: allow for zero length ranges
2022-04-12 14:47 [PATCH nft,v4 0/7] revisit overlap/automerge codebase Pablo Neira Ayuso
` (4 preceding siblings ...)
2022-04-12 14:47 ` [PATCH nft,v4 5/7] intervals: add support to automerge with kernel elements Pablo Neira Ayuso
@ 2022-04-12 14:47 ` Pablo Neira Ayuso
2022-04-12 14:47 ` [PATCH nft,v4 7/7] intervals: support to partial deletion with automerge Pablo Neira Ayuso
6 siblings, 0 replies; 16+ messages in thread
From: Pablo Neira Ayuso @ 2022-04-12 14:47 UTC (permalink / raw)
To: netfilter-devel
Allow for ranges such as, eg. 30-30.
This is required by the new intervals.c code, which normalize constant,
prefix set elements to all ranges.
Signed-off-by: Pablo Neira Ayuso <pablo@netfilter.org>
---
src/evaluate.c | 2 +-
1 file changed, 1 insertion(+), 1 deletion(-)
diff --git a/src/evaluate.c b/src/evaluate.c
index 9951a8349249..c79f3429eb2a 100644
--- a/src/evaluate.c
+++ b/src/evaluate.c
@@ -1017,7 +1017,7 @@ static int expr_evaluate_range(struct eval_ctx *ctx, struct expr **expr)
left = range->left;
right = range->right;
- if (mpz_cmp(left->value, right->value) >= 0)
+ if (mpz_cmp(left->value, right->value) > 0)
return expr_error(ctx->msgs, range,
"Range has zero or negative size");
datatype_set(range, left->dtype);
--
2.30.2
^ permalink raw reply related [flat|nested] 16+ messages in thread
* [PATCH nft,v4 7/7] intervals: support to partial deletion with automerge
2022-04-12 14:47 [PATCH nft,v4 0/7] revisit overlap/automerge codebase Pablo Neira Ayuso
` (5 preceding siblings ...)
2022-04-12 14:47 ` [PATCH nft,v4 6/7] evaluate: allow for zero length ranges Pablo Neira Ayuso
@ 2022-04-12 14:47 ` Pablo Neira Ayuso
2022-04-13 12:54 ` Phil Sutter
6 siblings, 1 reply; 16+ messages in thread
From: Pablo Neira Ayuso @ 2022-04-12 14:47 UTC (permalink / raw)
To: netfilter-devel
Splice the existing set element cache with the elements to be deleted
and merge sort it. The elements to be deleted are identified by the
EXPR_F_REMOVE flag.
The set elements to be deleted is automerged in first place if the
automerge flag is set on.
There are four possible deletion scenarios:
- Exact match, eg. delete [a-b] and there is a [a-b] range in the kernel set.
- Adjust left side of range, eg. delete [a-b] from range [a-x] where x > b.
- Adjust right side of range, eg. delete [a-b] from range [x-b] where x < a.
- Split range, eg. delete [a-b] from range [x-y] where x < a and b < y.
Update nft_evaluate() to use the safe list variant since new commands
are dynamically registered to the list to update ranges.
This patch also restores the set element existence check for Linux
kernels <= 5.7.
Signed-off-by: Pablo Neira Ayuso <pablo@netfilter.org>
---
include/expression.h | 1 +
include/intervals.h | 2 +
src/evaluate.c | 3 +-
src/intervals.c | 256 +++++++++++++++++++++++++++++++++++++++++++
src/libnftables.c | 4 +-
5 files changed, 263 insertions(+), 3 deletions(-)
diff --git a/include/expression.h b/include/expression.h
index c2d67d4c88af..2c3818e89b79 100644
--- a/include/expression.h
+++ b/include/expression.h
@@ -202,6 +202,7 @@ enum expr_flags {
EXPR_F_BOOLEAN = 0x10,
EXPR_F_INTERVAL = 0x20,
EXPR_F_KERNEL = 0x40,
+ EXPR_F_REMOVE = 0x80,
};
#include <payload.h>
diff --git a/include/intervals.h b/include/intervals.h
index 797129fc93a5..964804b19dda 100644
--- a/include/intervals.h
+++ b/include/intervals.h
@@ -4,6 +4,8 @@
void set_to_range(struct expr *init);
int set_automerge(struct list_head *msgs, struct cmd *cmd, struct set *set,
struct expr *init, unsigned int debug_mask);
+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);
diff --git a/src/evaluate.c b/src/evaluate.c
index c79f3429eb2a..812f309e431a 100644
--- a/src/evaluate.c
+++ b/src/evaluate.c
@@ -1474,7 +1474,8 @@ static int interval_set_eval(struct eval_ctx *ctx, struct set *set,
}
break;
case CMD_DELETE:
- set_to_range(init);
+ ret = set_delete(ctx->msgs, ctx->cmd, set, init,
+ ctx->nft->debug_mask);
break;
case CMD_GET:
break;
diff --git a/src/intervals.c b/src/intervals.c
index 16debf9cd4be..65e0531765a6 100644
--- a/src/intervals.c
+++ b/src/intervals.c
@@ -255,6 +255,262 @@ int set_automerge(struct list_head *msgs, struct cmd *cmd, struct set *set,
return 0;
}
+static void remove_elem(struct expr *prev, struct set *set, struct expr *purge)
+{
+ struct expr *clone;
+
+ if (!(prev->flags & EXPR_F_REMOVE)) {
+ if (prev->flags & EXPR_F_KERNEL) {
+ clone = expr_clone(prev);
+ list_move_tail(&clone->list, &purge->expressions);
+ } else {
+ list_del(&prev->list);
+ expr_free(prev);
+ }
+ }
+}
+
+static void __adjust_elem_left(struct set *set, struct expr *prev, struct expr *i,
+ struct expr *init)
+{
+ 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);
+ list_move(&prev->list, &init->expressions);
+}
+
+static void adjust_elem_left(struct set *set, struct expr *prev, struct expr *i,
+ struct expr *init, struct expr *purge)
+{
+ struct expr *clone;
+
+ clone = expr_clone(prev);
+ list_move_tail(&clone->list, &purge->expressions);
+
+ remove_elem(prev, set, purge);
+ __adjust_elem_left(set, prev, i, init);
+
+ list_del(&i->list);
+ expr_free(i);
+
+ clone = expr_clone(prev);
+ list_add_tail(&clone->list, &set->existing_set->init->expressions);
+}
+
+static void __adjust_elem_right(struct set *set, struct expr *prev, struct expr *i,
+ struct expr *init)
+{
+ 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);
+ list_move(&prev->list, &init->expressions);
+}
+
+static void adjust_elem_right(struct set *set, struct expr *prev, struct expr *i,
+ struct expr *init, struct expr *purge)
+{
+ struct expr *clone;
+
+ clone = expr_clone(prev);
+ list_move_tail(&clone->list, &purge->expressions);
+
+ remove_elem(prev, set, purge);
+ __adjust_elem_right(set, prev, i, init);
+
+ list_del(&i->list);
+ expr_free(i);
+
+ clone = expr_clone(prev);
+ list_add_tail(&clone->list, &set->existing_set->init->expressions);
+}
+
+static void split_range(struct set *set, struct expr *prev, struct expr *i,
+ struct expr *init, struct expr *purge)
+{
+ struct expr *clone;
+
+ clone = expr_clone(prev);
+ list_move_tail(&clone->list, &purge->expressions);
+
+ 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);
+ list_move(&clone->list, &init->expressions);
+ clone = expr_clone(clone);
+ 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);
+ list_move(&prev->list, &init->expressions);
+ clone = expr_clone(prev);
+ list_add_tail(&clone->list, &set->existing_set->init->expressions);
+
+ list_del(&i->list);
+ expr_free(i);
+}
+
+static int setelem_adjust(struct set *set, struct expr *init, struct expr *purge,
+ struct range *prev_range, struct range *range,
+ struct expr *prev, struct expr *i)
+{
+ if (mpz_cmp(prev_range->low, range->low) == 0 &&
+ mpz_cmp(prev_range->high, range->high) > 0) {
+ if (!(prev->flags & EXPR_F_REMOVE) &&
+ i->flags & EXPR_F_REMOVE)
+ adjust_elem_left(set, prev, i, init, purge);
+ } else if (mpz_cmp(prev_range->low, range->low) < 0 &&
+ mpz_cmp(prev_range->high, range->high) == 0) {
+ if (!(prev->flags & EXPR_F_REMOVE) &&
+ i->flags & EXPR_F_REMOVE)
+ adjust_elem_right(set, prev, i, init, purge);
+ } else if (mpz_cmp(prev_range->low, range->low) < 0 &&
+ mpz_cmp(prev_range->high, range->high) > 0) {
+ if (!(prev->flags & EXPR_F_REMOVE) &&
+ i->flags & EXPR_F_REMOVE)
+ split_range(set, prev, i, init, purge);
+ } else {
+ return -1;
+ }
+
+ return 0;
+}
+
+static int setelem_delete(struct list_head *msgs, struct set *set,
+ struct expr *init, struct expr *purge,
+ struct expr *elems, unsigned int debug_mask)
+{
+ struct expr *i, *next, *prev = NULL;
+ struct range range, prev_range;
+ int err = 0;
+ mpz_t rop;
+
+ mpz_init(prev_range.low);
+ mpz_init(prev_range.high);
+ mpz_init(range.low);
+ mpz_init(range.high);
+ mpz_init(rop);
+
+ list_for_each_entry_safe(i, next, &elems->expressions, list) {
+ if (i->key->etype == EXPR_SET_ELEM_CATCHALL)
+ continue;
+
+ range_expr_value_low(range.low, i);
+ range_expr_value_high(range.high, i);
+
+ if (!prev && i->flags & EXPR_F_REMOVE) {
+ expr_error(msgs, i, "element does not exist");
+ err = -1;
+ goto err;
+ }
+
+ if (!(i->flags & EXPR_F_REMOVE)) {
+ prev = i;
+ mpz_set(prev_range.low, range.low);
+ mpz_set(prev_range.high, range.high);
+ continue;
+ }
+
+ if (mpz_cmp(prev_range.low, range.low) == 0 &&
+ mpz_cmp(prev_range.high, range.high) == 0) {
+ if (!(prev->flags & EXPR_F_REMOVE) &&
+ i->flags & EXPR_F_REMOVE) {
+ list_move_tail(&prev->list, &purge->expressions);
+ list_del(&i->list);
+ expr_free(i);
+ }
+ } else if (set->automerge &&
+ setelem_adjust(set, init, purge, &prev_range, &range, prev, i) < 0) {
+ expr_error(msgs, i, "element does not exist");
+ err = -1;
+ goto err;
+ }
+ prev = NULL;
+ }
+err:
+ mpz_clear(prev_range.low);
+ mpz_clear(prev_range.high);
+ mpz_clear(range.low);
+ mpz_clear(range.high);
+ mpz_clear(rop);
+
+ return err;
+}
+
+static void automerge_delete(struct list_head *msgs, struct set *set,
+ struct expr *init, unsigned int debug_mask)
+{
+ struct set_automerge_ctx ctx = {
+ .set = set,
+ .init = init,
+ .debug_mask = debug_mask,
+ };
+
+ ctx.purge = set_expr_alloc(&internal_location, set);
+ list_expr_sort(&init->expressions);
+ setelem_automerge(&ctx);
+ expr_free(ctx.purge);
+}
+
+/* detection for unexisting intervals already exists in Linux kernels >= 5.7. */
+int set_delete(struct list_head *msgs, struct cmd *cmd, struct set *set,
+ struct expr *init, unsigned int debug_mask)
+{
+ struct set *existing_set = set->existing_set;
+ struct expr *i, *add;
+ struct handle h = {};
+ struct cmd *add_cmd;
+ int err;
+
+ set_to_range(init);
+ if (set->automerge)
+ automerge_delete(msgs, set, init, debug_mask);
+
+ list_for_each_entry(i, &init->expressions, list)
+ i->flags |= EXPR_F_REMOVE;
+
+ set_to_range(existing_set->init);
+ list_splice_init(&init->expressions, &existing_set->init->expressions);
+
+ list_expr_sort(&existing_set->init->expressions);
+
+ add = set_expr_alloc(&internal_location, set);
+
+ err = setelem_delete(msgs, set, add, init, existing_set->init, debug_mask);
+ if (err < 0) {
+ expr_free(add);
+ return err;
+ }
+
+ if (debug_mask & NFT_DEBUG_SEGTREE) {
+ list_for_each_entry(i, &init->expressions, list)
+ gmp_printf("remove: [%Zx-%Zx]\n",
+ i->key->left->value, i->key->right->value);
+ list_for_each_entry(i, &add->expressions, list)
+ gmp_printf("add: [%Zx-%Zx]\n",
+ i->key->left->value, i->key->right->value);
+ list_for_each_entry(i, &existing_set->init->expressions, list)
+ gmp_printf("existing: [%Zx-%Zx]\n",
+ i->key->left->value, i->key->right->value);
+ }
+
+ if (list_empty(&add->expressions)) {
+ expr_free(add);
+ return 0;
+ }
+
+ handle_merge(&h, &cmd->handle);
+ add_cmd = cmd_alloc(CMD_ADD, CMD_OBJ_ELEMENTS, &h, &cmd->location, add);
+ add_cmd->elem.set = set_get(set);
+ list_add(&add_cmd->list, &cmd->list);
+
+ return 0;
+}
+
static int setelem_overlap(struct list_head *msgs, struct set *set,
struct expr *init)
{
diff --git a/src/libnftables.c b/src/libnftables.c
index dc0932bdbdd0..6a22ea093952 100644
--- a/src/libnftables.c
+++ b/src/libnftables.c
@@ -500,8 +500,8 @@ static int nft_evaluate(struct nft_ctx *nft, struct list_head *msgs,
struct list_head *cmds)
{
struct nft_cache_filter *filter;
+ struct cmd *cmd, *next;
unsigned int flags;
- struct cmd *cmd;
filter = nft_cache_filter_init();
flags = nft_cache_evaluate(nft, cmds, filter);
@@ -512,7 +512,7 @@ static int nft_evaluate(struct nft_ctx *nft, struct list_head *msgs,
nft_cache_filter_fini(filter);
- list_for_each_entry(cmd, cmds, list) {
+ list_for_each_entry_safe(cmd, next, cmds, list) {
struct eval_ctx ectx = {
.nft = nft,
.msgs = msgs,
--
2.30.2
^ permalink raw reply related [flat|nested] 16+ messages in thread
* Re: [PATCH nft,v4 7/7] intervals: support to partial deletion with automerge
2022-04-12 14:47 ` [PATCH nft,v4 7/7] intervals: support to partial deletion with automerge Pablo Neira Ayuso
@ 2022-04-13 12:54 ` Phil Sutter
2022-04-13 13:13 ` Pablo Neira Ayuso
0 siblings, 1 reply; 16+ messages in thread
From: Phil Sutter @ 2022-04-13 12:54 UTC (permalink / raw)
To: Pablo Neira Ayuso; +Cc: netfilter-devel
Hi Pablo,
On Tue, Apr 12, 2022 at 04:47:11PM +0200, Pablo Neira Ayuso wrote:
[...]
> diff --git a/src/intervals.c b/src/intervals.c
> index 16debf9cd4be..65e0531765a6 100644
> --- a/src/intervals.c
> +++ b/src/intervals.c
> @@ -255,6 +255,262 @@ int set_automerge(struct list_head *msgs, struct cmd *cmd, struct set *set,
> return 0;
> }
>
> +static void remove_elem(struct expr *prev, struct set *set, struct expr *purge)
> +{
> + struct expr *clone;
> +
> + if (!(prev->flags & EXPR_F_REMOVE)) {
Does prev->flags ever contain EXPR_F_REMOVE? (See below.)
> + if (prev->flags & EXPR_F_KERNEL) {
> + clone = expr_clone(prev);
> + list_move_tail(&clone->list, &purge->expressions);
> + } else {
> + list_del(&prev->list);
> + expr_free(prev);
> + }
> + }
> +}
> +
> +static void __adjust_elem_left(struct set *set, struct expr *prev, struct expr *i,
> + struct expr *init)
> +{
> + prev->flags &= EXPR_F_KERNEL;
This looks odd. You're intentionally stripping all flags other than
EXPR_F_KERNEL (if set)?
IIUC, you're just dropping EXPR_F_REMOVE if set. If so, explicit
'prev->flags &= ~EXPR_F_REMOVE' is more clear, no?
Maybe it's also irrelevant after all WRT above question.
> + 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);
> + list_move(&prev->list, &init->expressions);
> +}
[...]
> +static int setelem_delete(struct list_head *msgs, struct set *set,
> + struct expr *init, struct expr *purge,
> + struct expr *elems, unsigned int debug_mask)
> +{
> + struct expr *i, *next, *prev = NULL;
> + struct range range, prev_range;
> + int err = 0;
> + mpz_t rop;
> +
> + mpz_init(prev_range.low);
> + mpz_init(prev_range.high);
> + mpz_init(range.low);
> + mpz_init(range.high);
> + mpz_init(rop);
> +
> + list_for_each_entry_safe(i, next, &elems->expressions, list) {
> + if (i->key->etype == EXPR_SET_ELEM_CATCHALL)
> + continue;
> +
> + range_expr_value_low(range.low, i);
> + range_expr_value_high(range.high, i);
> +
> + if (!prev && i->flags & EXPR_F_REMOVE) {
> + expr_error(msgs, i, "element does not exist");
> + err = -1;
> + goto err;
> + }
> +
> + if (!(i->flags & EXPR_F_REMOVE)) {
> + prev = i;
> + mpz_set(prev_range.low, range.low);
> + mpz_set(prev_range.high, range.high);
> + continue;
> + }
The loop assigns to 'prev' only if EXPR_F_REMOVE is not set.
> +
> + if (mpz_cmp(prev_range.low, range.low) == 0 &&
> + mpz_cmp(prev_range.high, range.high) == 0) {
> + if (!(prev->flags & EXPR_F_REMOVE) &&
> + i->flags & EXPR_F_REMOVE) {
> + list_move_tail(&prev->list, &purge->expressions);
> + list_del(&i->list);
> + expr_free(i);
> + }
> + } else if (set->automerge &&
> + setelem_adjust(set, init, purge, &prev_range, &range, prev, i) < 0) {
> + expr_error(msgs, i, "element does not exist");
> + err = -1;
> + goto err;
> + }
> + prev = NULL;
The code above may set EXPR_F_REMOVE in 'prev', but AFAICT 'prev' is not
revisited within and cleared before next iteration.
Cheers, Phil
^ permalink raw reply [flat|nested] 16+ messages in thread
* Re: [PATCH nft,v4 7/7] intervals: support to partial deletion with automerge
2022-04-13 12:54 ` Phil Sutter
@ 2022-04-13 13:13 ` Pablo Neira Ayuso
2022-04-13 14:02 ` Phil Sutter
0 siblings, 1 reply; 16+ messages in thread
From: Pablo Neira Ayuso @ 2022-04-13 13:13 UTC (permalink / raw)
To: Phil Sutter, netfilter-devel
On Wed, Apr 13, 2022 at 02:54:34PM +0200, Phil Sutter wrote:
> Hi Pablo,
>
> On Tue, Apr 12, 2022 at 04:47:11PM +0200, Pablo Neira Ayuso wrote:
> [...]
> > diff --git a/src/intervals.c b/src/intervals.c
> > index 16debf9cd4be..65e0531765a6 100644
> > --- a/src/intervals.c
> > +++ b/src/intervals.c
> > @@ -255,6 +255,262 @@ int set_automerge(struct list_head *msgs, struct cmd *cmd, struct set *set,
> > return 0;
> > }
> >
> > +static void remove_elem(struct expr *prev, struct set *set, struct expr *purge)
> > +{
> > + struct expr *clone;
> > +
> > + if (!(prev->flags & EXPR_F_REMOVE)) {
>
> Does prev->flags ever contain EXPR_F_REMOVE? (See below.)
EXPR_F_REMOVE flag is used to specify that this element represents a
deletion.
The existing list of elements in the kernel is mixed with the list of
elements to be deleted, this list is merge-sorted, then we look for
EXPR_F_REMOVE elements that are asking for removal of elements in the
kernel.
The flag allows me to track objects, whether they are in the kernel
(EXPR_F_KERNEL), they are new (no flag) or they represent an element
that need to be removed from the kernel (EXPR_F_REMOVE).
> > + if (prev->flags & EXPR_F_KERNEL) {
> > + clone = expr_clone(prev);
> > + list_move_tail(&clone->list, &purge->expressions);
> > + } else {
> > + list_del(&prev->list);
> > + expr_free(prev);
> > + }
> > + }
> > +}
> > +
> > +static void __adjust_elem_left(struct set *set, struct expr *prev, struct expr *i,
> > + struct expr *init)
> > +{
> > + prev->flags &= EXPR_F_KERNEL;
>
> This looks odd. You're intentionally stripping all flags other than
> EXPR_F_KERNEL (if set)?
> IIUC, you're just dropping EXPR_F_REMOVE if set. If so, explicit
> 'prev->flags &= ~EXPR_F_REMOVE' is more clear, no?
> Maybe it's also irrelevant after all WRT above question.
Yes, this should be prev->flags &= ~EXPR_F_KERNEL, I'll fix it.
This element is moved to the list of elements to be added. This flag
is irrelevant though at this stage, but in case you look at the list
of elements to be added, you should not see EXPR_F_KERNEL there.
> > + 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);
> > + list_move(&prev->list, &init->expressions);
> > +}
> [...]
> > +static int setelem_delete(struct list_head *msgs, struct set *set,
> > + struct expr *init, struct expr *purge,
> > + struct expr *elems, unsigned int debug_mask)
> > +{
> > + struct expr *i, *next, *prev = NULL;
> > + struct range range, prev_range;
> > + int err = 0;
> > + mpz_t rop;
> > +
> > + mpz_init(prev_range.low);
> > + mpz_init(prev_range.high);
> > + mpz_init(range.low);
> > + mpz_init(range.high);
> > + mpz_init(rop);
> > +
> > + list_for_each_entry_safe(i, next, &elems->expressions, list) {
> > + if (i->key->etype == EXPR_SET_ELEM_CATCHALL)
> > + continue;
> > +
> > + range_expr_value_low(range.low, i);
> > + range_expr_value_high(range.high, i);
> > +
> > + if (!prev && i->flags & EXPR_F_REMOVE) {
> > + expr_error(msgs, i, "element does not exist");
> > + err = -1;
> > + goto err;
> > + }
> > +
> > + if (!(i->flags & EXPR_F_REMOVE)) {
> > + prev = i;
> > + mpz_set(prev_range.low, range.low);
> > + mpz_set(prev_range.high, range.high);
> > + continue;
> > + }
>
> The loop assigns to 'prev' only if EXPR_F_REMOVE is not set.
Yes, this annotates is a element candidate to be removed.
The list of elements is merged-sorted, coming the element with
EXPR_F_REMOVE before the element that needs to be removed.
> > + if (mpz_cmp(prev_range.low, range.low) == 0 &&
> > + mpz_cmp(prev_range.high, range.high) == 0) {
> > + if (!(prev->flags & EXPR_F_REMOVE) &&
> > + i->flags & EXPR_F_REMOVE) {
> > + list_move_tail(&prev->list, &purge->expressions);
> > + list_del(&i->list);
> > + expr_free(i);
> > + }
> > + } else if (set->automerge &&
> > + setelem_adjust(set, init, purge, &prev_range, &range, prev, i) < 0) {
> > + expr_error(msgs, i, "element does not exist");
> > + err = -1;
> > + goto err;
> > + }
> > + prev = NULL;
>
> The code above may set EXPR_F_REMOVE in 'prev', but AFAICT 'prev' is not
> revisited within and cleared before next iteration.
Yes, it is intentional. First this annotates the element to be delete,
next iteration should find a similar element with either
EXPR_F_KERNEL (if already in the kernel) or no flag if it was freshly
added in this batch.
^ permalink raw reply [flat|nested] 16+ messages in thread
* Re: [PATCH nft,v4 7/7] intervals: support to partial deletion with automerge
2022-04-13 13:13 ` Pablo Neira Ayuso
@ 2022-04-13 14:02 ` Phil Sutter
2022-04-13 14:27 ` Pablo Neira Ayuso
0 siblings, 1 reply; 16+ messages in thread
From: Phil Sutter @ 2022-04-13 14:02 UTC (permalink / raw)
To: Pablo Neira Ayuso; +Cc: netfilter-devel
On Wed, Apr 13, 2022 at 03:13:30PM +0200, Pablo Neira Ayuso wrote:
> On Wed, Apr 13, 2022 at 02:54:34PM +0200, Phil Sutter wrote:
[...]
> > > +static void __adjust_elem_left(struct set *set, struct expr *prev, struct expr *i,
> > > + struct expr *init)
> > > +{
> > > + prev->flags &= EXPR_F_KERNEL;
> >
> > This looks odd. You're intentionally stripping all flags other than
> > EXPR_F_KERNEL (if set)?
> > IIUC, you're just dropping EXPR_F_REMOVE if set. If so, explicit
> > 'prev->flags &= ~EXPR_F_REMOVE' is more clear, no?
> > Maybe it's also irrelevant after all WRT above question.
>
> Yes, this should be prev->flags &= ~EXPR_F_KERNEL, I'll fix it.
Ah, OK!
> This element is moved to the list of elements to be added. This flag
> is irrelevant though at this stage, but in case you look at the list
> of elements to be added, you should not see EXPR_F_KERNEL there.
I guess none of the flags are relevant at this point anymore since your
code cleared them all and apparently passed testing? Or none of the
relevant ones were set, which is my suspicion with EXPR_F_REMOVE.
[...]
> > > + list_for_each_entry_safe(i, next, &elems->expressions, list) {
> > > + if (i->key->etype == EXPR_SET_ELEM_CATCHALL)
> > > + continue;
> > > +
> > > + range_expr_value_low(range.low, i);
> > > + range_expr_value_high(range.high, i);
> > > +
> > > + if (!prev && i->flags & EXPR_F_REMOVE) {
> > > + expr_error(msgs, i, "element does not exist");
> > > + err = -1;
> > > + goto err;
> > > + }
> > > +
> > > + if (!(i->flags & EXPR_F_REMOVE)) {
> > > + prev = i;
> > > + mpz_set(prev_range.low, range.low);
> > > + mpz_set(prev_range.high, range.high);
> > > + continue;
> > > + }
> >
> > The loop assigns to 'prev' only if EXPR_F_REMOVE is not set.
>
> Yes, this annotates is a element candidate to be removed.
>
> The list of elements is merged-sorted, coming the element with
> EXPR_F_REMOVE before the element that needs to be removed.
The one with EXPR_F_REMOVE comes *after* the one to be removed, right?
My question again: Is it possible for 'prev' to have EXPR_F_REMOVE set?
Maybe I miss something, but to me it looks like not although the code
expects it.
Cheers, Phil
^ permalink raw reply [flat|nested] 16+ messages in thread
* Re: [PATCH nft,v4 7/7] intervals: support to partial deletion with automerge
2022-04-13 14:02 ` Phil Sutter
@ 2022-04-13 14:27 ` Pablo Neira Ayuso
2022-04-13 14:38 ` Phil Sutter
0 siblings, 1 reply; 16+ messages in thread
From: Pablo Neira Ayuso @ 2022-04-13 14:27 UTC (permalink / raw)
To: Phil Sutter, netfilter-devel
On Wed, Apr 13, 2022 at 04:02:45PM +0200, Phil Sutter wrote:
> On Wed, Apr 13, 2022 at 03:13:30PM +0200, Pablo Neira Ayuso wrote:
> > On Wed, Apr 13, 2022 at 02:54:34PM +0200, Phil Sutter wrote:
> [...]
> > > > +static void __adjust_elem_left(struct set *set, struct expr *prev, struct expr *i,
> > > > + struct expr *init)
> > > > +{
> > > > + prev->flags &= EXPR_F_KERNEL;
> > >
> > > This looks odd. You're intentionally stripping all flags other than
> > > EXPR_F_KERNEL (if set)?
> > > IIUC, you're just dropping EXPR_F_REMOVE if set. If so, explicit
> > > 'prev->flags &= ~EXPR_F_REMOVE' is more clear, no?
> > > Maybe it's also irrelevant after all WRT above question.
> >
> > Yes, this should be prev->flags &= ~EXPR_F_KERNEL, I'll fix it.
>
> Ah, OK!
>
> > This element is moved to the list of elements to be added. This flag
> > is irrelevant though at this stage, but in case you look at the list
> > of elements to be added, you should not see EXPR_F_KERNEL there.
>
> I guess none of the flags are relevant at this point anymore since your
> code cleared them all and apparently passed testing? Or none of the
> relevant ones were set, which is my suspicion with EXPR_F_REMOVE.
>
> [...]
> > > > + list_for_each_entry_safe(i, next, &elems->expressions, list) {
> > > > + if (i->key->etype == EXPR_SET_ELEM_CATCHALL)
> > > > + continue;
> > > > +
> > > > + range_expr_value_low(range.low, i);
> > > > + range_expr_value_high(range.high, i);
> > > > +
> > > > + if (!prev && i->flags & EXPR_F_REMOVE) {
> > > > + expr_error(msgs, i, "element does not exist");
> > > > + err = -1;
> > > > + goto err;
> > > > + }
> > > > +
> > > > + if (!(i->flags & EXPR_F_REMOVE)) {
> > > > + prev = i;
> > > > + mpz_set(prev_range.low, range.low);
> > > > + mpz_set(prev_range.high, range.high);
> > > > + continue;
> > > > + }
> > >
> > > The loop assigns to 'prev' only if EXPR_F_REMOVE is not set.
> >
> > Yes, this annotates is a element candidate to be removed.
> >
> > The list of elements is merged-sorted, coming the element with
> > EXPR_F_REMOVE before the element that needs to be removed.
>
> The one with EXPR_F_REMOVE comes *after* the one to be removed, right?
Right, the other way around actually.
> My question again: Is it possible for 'prev' to have EXPR_F_REMOVE set?
> Maybe I miss something, but to me it looks like not although the code
> expects it.
prev never has EXPR_F_REMOVE, so it points to an existing element.
^ permalink raw reply [flat|nested] 16+ messages in thread
* Re: [PATCH nft,v4 7/7] intervals: support to partial deletion with automerge
2022-04-13 14:27 ` Pablo Neira Ayuso
@ 2022-04-13 14:38 ` Phil Sutter
2022-04-13 14:45 ` Pablo Neira Ayuso
2022-04-13 14:47 ` Pablo Neira Ayuso
0 siblings, 2 replies; 16+ messages in thread
From: Phil Sutter @ 2022-04-13 14:38 UTC (permalink / raw)
To: Pablo Neira Ayuso; +Cc: netfilter-devel
On Wed, Apr 13, 2022 at 04:27:07PM +0200, Pablo Neira Ayuso wrote:
[...]
> > The one with EXPR_F_REMOVE comes *after* the one to be removed, right?
>
> Right, the other way around actually.
>
> > My question again: Is it possible for 'prev' to have EXPR_F_REMOVE set?
> > Maybe I miss something, but to me it looks like not although the code
> > expects it.
>
> prev never has EXPR_F_REMOVE, so it points to an existing element.
So below change should be fine?
diff --git a/src/intervals.c b/src/intervals.c
index 451bc4dd4dd45..c0077c06880ff 100644
--- a/src/intervals.c
+++ b/src/intervals.c
@@ -265,14 +265,12 @@ static void remove_elem(struct expr *prev, struct set *set, struct expr *purge)
{
struct expr *clone;
- if (!(prev->flags & EXPR_F_REMOVE)) {
- if (prev->flags & EXPR_F_KERNEL) {
- clone = expr_clone(prev);
- list_move_tail(&clone->list, &purge->expressions);
- } else {
- list_del(&prev->list);
- expr_free(prev);
- }
+ if (prev->flags & EXPR_F_KERNEL) {
+ clone = expr_clone(prev);
+ list_move_tail(&clone->list, &purge->expressions);
+ } else {
+ list_del(&prev->list);
+ expr_free(prev);
}
}
@@ -360,18 +358,15 @@ static int setelem_adjust(struct set *set, struct expr *add, struct expr *purge,
{
if (mpz_cmp(prev_range->low, range->low) == 0 &&
mpz_cmp(prev_range->high, range->high) > 0) {
- if (!(prev->flags & EXPR_F_REMOVE) &&
- i->flags & EXPR_F_REMOVE)
+ if (i->flags & EXPR_F_REMOVE)
adjust_elem_left(set, prev, i, add, purge);
} else if (mpz_cmp(prev_range->low, range->low) < 0 &&
mpz_cmp(prev_range->high, range->high) == 0) {
- if (!(prev->flags & EXPR_F_REMOVE) &&
- i->flags & EXPR_F_REMOVE)
+ if (i->flags & EXPR_F_REMOVE)
adjust_elem_right(set, prev, i, add, purge);
} else if (mpz_cmp(prev_range->low, range->low) < 0 &&
mpz_cmp(prev_range->high, range->high) > 0) {
- if (!(prev->flags & EXPR_F_REMOVE) &&
- i->flags & EXPR_F_REMOVE)
+ if (i->flags & EXPR_F_REMOVE)
split_range(set, prev, i, add, purge);
} else {
return -1;
@@ -417,8 +412,7 @@ static int setelem_delete(struct list_head *msgs, struct set *set,
if (mpz_cmp(prev_range.low, range.low) == 0 &&
mpz_cmp(prev_range.high, range.high) == 0) {
- if (!(prev->flags & EXPR_F_REMOVE) &&
- i->flags & EXPR_F_REMOVE) {
+ if (i->flags & EXPR_F_REMOVE) {
list_move_tail(&prev->list, &purge->expressions);
list_del(&i->list);
expr_free(i);
^ permalink raw reply related [flat|nested] 16+ messages in thread
* Re: [PATCH nft,v4 7/7] intervals: support to partial deletion with automerge
2022-04-13 14:38 ` Phil Sutter
@ 2022-04-13 14:45 ` Pablo Neira Ayuso
2022-04-13 14:47 ` Pablo Neira Ayuso
1 sibling, 0 replies; 16+ messages in thread
From: Pablo Neira Ayuso @ 2022-04-13 14:45 UTC (permalink / raw)
To: Phil Sutter, netfilter-devel
On Wed, Apr 13, 2022 at 04:38:02PM +0200, Phil Sutter wrote:
> On Wed, Apr 13, 2022 at 04:27:07PM +0200, Pablo Neira Ayuso wrote:
> [...]
> > > The one with EXPR_F_REMOVE comes *after* the one to be removed, right?
> >
> > Right, the other way around actually.
> >
> > > My question again: Is it possible for 'prev' to have EXPR_F_REMOVE set?
> > > Maybe I miss something, but to me it looks like not although the code
> > > expects it.
> >
> > prev never has EXPR_F_REMOVE, so it points to an existing element.
>
> So below change should be fine?
Yes, setelem_adjust() always checks for if (!(prev->flags & EXPR_F_REMOVE))
Your patch looks correct to me.
> diff --git a/src/intervals.c b/src/intervals.c
> index 451bc4dd4dd45..c0077c06880ff 100644
> --- a/src/intervals.c
> +++ b/src/intervals.c
> @@ -265,14 +265,12 @@ static void remove_elem(struct expr *prev, struct set *set, struct expr *purge)
> {
> struct expr *clone;
>
> - if (!(prev->flags & EXPR_F_REMOVE)) {
> - if (prev->flags & EXPR_F_KERNEL) {
> - clone = expr_clone(prev);
> - list_move_tail(&clone->list, &purge->expressions);
> - } else {
> - list_del(&prev->list);
> - expr_free(prev);
> - }
> + if (prev->flags & EXPR_F_KERNEL) {
> + clone = expr_clone(prev);
> + list_move_tail(&clone->list, &purge->expressions);
> + } else {
> + list_del(&prev->list);
> + expr_free(prev);
> }
> }
>
> @@ -360,18 +358,15 @@ static int setelem_adjust(struct set *set, struct expr *add, struct expr *purge,
> {
> if (mpz_cmp(prev_range->low, range->low) == 0 &&
> mpz_cmp(prev_range->high, range->high) > 0) {
> - if (!(prev->flags & EXPR_F_REMOVE) &&
> - i->flags & EXPR_F_REMOVE)
> + if (i->flags & EXPR_F_REMOVE)
> adjust_elem_left(set, prev, i, add, purge);
> } else if (mpz_cmp(prev_range->low, range->low) < 0 &&
> mpz_cmp(prev_range->high, range->high) == 0) {
> - if (!(prev->flags & EXPR_F_REMOVE) &&
> - i->flags & EXPR_F_REMOVE)
> + if (i->flags & EXPR_F_REMOVE)
> adjust_elem_right(set, prev, i, add, purge);
> } else if (mpz_cmp(prev_range->low, range->low) < 0 &&
> mpz_cmp(prev_range->high, range->high) > 0) {
> - if (!(prev->flags & EXPR_F_REMOVE) &&
> - i->flags & EXPR_F_REMOVE)
> + if (i->flags & EXPR_F_REMOVE)
> split_range(set, prev, i, add, purge);
> } else {
> return -1;
> @@ -417,8 +412,7 @@ static int setelem_delete(struct list_head *msgs, struct set *set,
>
> if (mpz_cmp(prev_range.low, range.low) == 0 &&
> mpz_cmp(prev_range.high, range.high) == 0) {
> - if (!(prev->flags & EXPR_F_REMOVE) &&
> - i->flags & EXPR_F_REMOVE) {
> + if (i->flags & EXPR_F_REMOVE) {
> list_move_tail(&prev->list, &purge->expressions);
> list_del(&i->list);
> expr_free(i);
^ permalink raw reply [flat|nested] 16+ messages in thread
* Re: [PATCH nft,v4 7/7] intervals: support to partial deletion with automerge
2022-04-13 14:38 ` Phil Sutter
2022-04-13 14:45 ` Pablo Neira Ayuso
@ 2022-04-13 14:47 ` Pablo Neira Ayuso
2022-04-13 14:54 ` Pablo Neira Ayuso
1 sibling, 1 reply; 16+ messages in thread
From: Pablo Neira Ayuso @ 2022-04-13 14:47 UTC (permalink / raw)
To: Phil Sutter, netfilter-devel
On Wed, Apr 13, 2022 at 04:38:02PM +0200, Phil Sutter wrote:
> On Wed, Apr 13, 2022 at 04:27:07PM +0200, Pablo Neira Ayuso wrote:
> [...]
> > > The one with EXPR_F_REMOVE comes *after* the one to be removed, right?
> >
> > Right, the other way around actually.
> >
> > > My question again: Is it possible for 'prev' to have EXPR_F_REMOVE set?
> > > Maybe I miss something, but to me it looks like not although the code
> > > expects it.
> >
> > prev never has EXPR_F_REMOVE, so it points to an existing element.
>
> So below change should be fine?
Wait.
> diff --git a/src/intervals.c b/src/intervals.c
> index 451bc4dd4dd45..c0077c06880ff 100644
> --- a/src/intervals.c
> +++ b/src/intervals.c
[...]
> @@ -360,18 +358,15 @@ static int setelem_adjust(struct set *set, struct expr *add, struct expr *purge,
> {
> if (mpz_cmp(prev_range->low, range->low) == 0 &&
> mpz_cmp(prev_range->high, range->high) > 0) {
> - if (!(prev->flags & EXPR_F_REMOVE) &&
> - i->flags & EXPR_F_REMOVE)
> + if (i->flags & EXPR_F_REMOVE)
This chunk is not correct.
User might ask to delete an element which does not exist.
Then, you might find two consecutive EXPR_F_REMOVE.
Only the initial chunk in this patch is fine.
^ permalink raw reply [flat|nested] 16+ messages in thread
* Re: [PATCH nft,v4 7/7] intervals: support to partial deletion with automerge
2022-04-13 14:47 ` Pablo Neira Ayuso
@ 2022-04-13 14:54 ` Pablo Neira Ayuso
0 siblings, 0 replies; 16+ messages in thread
From: Pablo Neira Ayuso @ 2022-04-13 14:54 UTC (permalink / raw)
To: Phil Sutter, netfilter-devel
On Wed, Apr 13, 2022 at 04:47:07PM +0200, Pablo Neira Ayuso wrote:
> On Wed, Apr 13, 2022 at 04:38:02PM +0200, Phil Sutter wrote:
> > On Wed, Apr 13, 2022 at 04:27:07PM +0200, Pablo Neira Ayuso wrote:
> > [...]
> > > > The one with EXPR_F_REMOVE comes *after* the one to be removed, right?
> > >
> > > Right, the other way around actually.
> > >
> > > > My question again: Is it possible for 'prev' to have EXPR_F_REMOVE set?
> > > > Maybe I miss something, but to me it looks like not although the code
> > > > expects it.
> > >
> > > prev never has EXPR_F_REMOVE, so it points to an existing element.
> >
> > So below change should be fine?
>
> Wait.
>
> > diff --git a/src/intervals.c b/src/intervals.c
> > index 451bc4dd4dd45..c0077c06880ff 100644
> > --- a/src/intervals.c
> > +++ b/src/intervals.c
> [...]
> > @@ -360,18 +358,15 @@ static int setelem_adjust(struct set *set, struct expr *add, struct expr *purge,
> > {
> > if (mpz_cmp(prev_range->low, range->low) == 0 &&
> > mpz_cmp(prev_range->high, range->high) > 0) {
> > - if (!(prev->flags & EXPR_F_REMOVE) &&
> > - i->flags & EXPR_F_REMOVE)
> > + if (i->flags & EXPR_F_REMOVE)
>
> This chunk is not correct.
>
> User might ask to delete an element which does not exist.
>
> Then, you might find two consecutive EXPR_F_REMOVE.
>
> Only the initial chunk in this patch is fine.
Wait, you mean prev is always !EXPR_F_REMOVE, then this should be
fine.
^ permalink raw reply [flat|nested] 16+ messages in thread
end of thread, other threads:[~2022-04-13 14:54 UTC | newest]
Thread overview: 16+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2022-04-12 14:47 [PATCH nft,v4 0/7] revisit overlap/automerge codebase Pablo Neira Ayuso
2022-04-12 14:47 ` [PATCH nft,v4 1/7] src: add EXPR_F_KERNEL to identify expression in the kernel Pablo Neira Ayuso
2022-04-12 14:47 ` [PATCH nft,v4 2/7] src: replace interval segment tree overlap and automerge Pablo Neira Ayuso
2022-04-12 14:47 ` [PATCH nft,v4 3/7] src: remove rbtree datastructure Pablo Neira Ayuso
2022-04-12 14:47 ` [PATCH nft,v4 4/7] mnl: update mnl_nft_setelem_del() to allow for more reuse Pablo Neira Ayuso
2022-04-12 14:47 ` [PATCH nft,v4 5/7] intervals: add support to automerge with kernel elements Pablo Neira Ayuso
2022-04-12 14:47 ` [PATCH nft,v4 6/7] evaluate: allow for zero length ranges Pablo Neira Ayuso
2022-04-12 14:47 ` [PATCH nft,v4 7/7] intervals: support to partial deletion with automerge Pablo Neira Ayuso
2022-04-13 12:54 ` Phil Sutter
2022-04-13 13:13 ` Pablo Neira Ayuso
2022-04-13 14:02 ` Phil Sutter
2022-04-13 14:27 ` Pablo Neira Ayuso
2022-04-13 14:38 ` Phil Sutter
2022-04-13 14:45 ` Pablo Neira Ayuso
2022-04-13 14:47 ` Pablo Neira Ayuso
2022-04-13 14:54 ` Pablo Neira Ayuso
This is an external index of several public inboxes,
see mirroring instructions on how to clone and mirror
all data and code used by this external index.