intervals: support to partial deletion with automerge

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>

2 files changed, 3 insertions, 0 deletions

diff --git a/include/expression.h b/include/expression.h
index c2d67d4c..2c3818e8 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 797129fc..964804b1 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);