src: replace interval segment tree overlap and automerge

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>

1 files changed, 0 insertions, 651 deletions

diff --git a/src/segtree.c b/src/segtree.c
index 6f723175..4602becc 100644
--- a/src/segtree.c
+++ b/src/segtree.c
@@ -19,56 +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 enum byteorder get_key_byteorder(const struct expr *e)
 {
@@ -91,522 +41,6 @@ static enum byteorder get_key_byteorder(const struct expr *e)
 	return BYTEORDER_INVALID;
 }
 
-static void seg_tree_init(struct seg_tree *tree, const struct set *set,
-			  struct expr *init, unsigned int debug_mask)
-{
-	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 = get_key_byteorder(set->key);
-	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)
 {
 	if (src->comment)
@@ -619,91 +53,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);
-	if (tree->byteorder == BYTEORDER_HOST_ENDIAN)
-		mpz_switch_byteorder(expr->value, expr->len / BITS_PER_BYTE);
-
-	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)
 {