intervals: add support to automerge with kernel elements

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>

2 files changed, 37 insertions, 0 deletions

diff --git a/tests/shell/testcases/sets/0069interval_merge_0 b/tests/shell/testcases/sets/0069interval_merge_0
new file mode 100755
index 00000000..edb6422a
--- /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 00000000..2d4e1706
--- /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 }
+	}
+}