summaryrefslogtreecommitdiffstats
path: root/src
diff options
context:
space:
mode:
authorPablo Neira Ayuso <pablo@netfilter.org>2018-02-23 10:36:27 +0100
committerPablo Neira Ayuso <pablo@netfilter.org>2018-02-25 19:50:23 +0100
commit4d6ad0f310d6cc3a1d776d32d9d7d678017c6dd7 (patch)
tree0bd70d1925789be0cadc5e2135fba303eebb89ec /src
parent2018bb82f71d57d777b121af96138359ee6b857e (diff)
segtree: check for overlapping elements at insertion
This speeds up element overlap checks quite a bit. Fixes: https://bugzilla.netfilter.org/show_bug.cgi?id=1228 Signed-off-by: Pablo Neira Ayuso <pablo@netfilter.org>
Diffstat (limited to 'src')
-rw-r--r--src/segtree.c60
1 files changed, 16 insertions, 44 deletions
diff --git a/src/segtree.c b/src/segtree.c
index d2c4efaa..1c23d4b8 100644
--- a/src/segtree.c
+++ b/src/segtree.c
@@ -182,7 +182,8 @@ static bool segtree_debug(unsigned int debug_mask)
* be ordered by descending interval size, meaning the new interval never
* extends over more than two existing intervals.
*/
-static void ei_insert(struct seg_tree *tree, struct elementary_interval *new)
+static int ei_insert(struct list_head *msgs, struct seg_tree *tree,
+ struct elementary_interval *new, bool merge)
{
struct elementary_interval *lei, *rei;
mpz_t p;
@@ -199,6 +200,8 @@ static void ei_insert(struct seg_tree *tree, struct elementary_interval *new)
pr_gmp_debug("insert: [%Zx %Zx]\n", new->left, new->right);
if (lei != NULL && rei != NULL && lei == rei) {
+ if (!merge)
+ goto err;
/*
* The new interval is entirely contained in the same interval,
* split it into two parts:
@@ -220,6 +223,8 @@ static void ei_insert(struct seg_tree *tree, struct elementary_interval *new)
ei_destroy(lei);
} else {
if (lei != NULL) {
+ if (!merge)
+ goto err;
/*
* Left endpoint is within lei, adjust it so we have:
*
@@ -238,6 +243,8 @@ static void ei_insert(struct seg_tree *tree, struct elementary_interval *new)
}
}
if (rei != NULL) {
+ if (!merge)
+ goto err;
/*
* Right endpoint is within rei, adjust it so we have:
*
@@ -260,6 +267,11 @@ static void ei_insert(struct seg_tree *tree, struct elementary_interval *new)
__ei_insert(tree, new);
mpz_clear(p);
+
+ return 0;
+err:
+ return expr_binary_error(msgs, lei->expr, new->expr,
+ "conflicting intervals specified");
}
/*
@@ -292,18 +304,6 @@ static int interval_cmp(const void *p1, const void *p2)
return ret;
}
-static bool interval_conflict(const struct elementary_interval *e1,
- const struct elementary_interval *e2)
-{
- if (mpz_cmp(e1->left, e2->left) <= 0 &&
- mpz_cmp(e1->right, e2->left) >= 0 &&
- mpz_cmp(e1->size, e2->size) == 0 &&
- !expr_cmp(e1->expr->right, e2->expr->right))
- return true;
- else
- return false;
-}
-
static unsigned int expr_to_intervals(const struct expr *set,
unsigned int keylen,
struct elementary_interval **intervals)
@@ -375,23 +375,6 @@ static int set_overlap(struct list_head *msgs, const struct set *set,
return 0;
}
-static int intervals_overlap(struct list_head *msgs,
- struct elementary_interval **intervals,
- unsigned int keylen)
-{
- unsigned int i, j;
-
- for (i = 0; i < keylen - 1; i++) {
- for (j = i + 1; j < keylen; j++) {
- if (interval_overlap(intervals[i], intervals[j]))
- return expr_error(msgs, intervals[j]->expr,
- "interval overlaps with previous one");
- }
- }
-
- return 0;
-}
-
static int set_to_segtree(struct list_head *msgs, struct set *set,
struct expr *init, struct seg_tree *tree,
bool add, bool merge)
@@ -412,12 +395,6 @@ static int set_to_segtree(struct list_head *msgs, struct set *set,
n = expr_to_intervals(init, tree->keylen, intervals);
- if (add && !merge) {
- err = intervals_overlap(msgs, intervals, n);
- if (err < 0)
- return err;
- }
-
list_for_each_entry_safe(i, next, &init->expressions, list) {
list_del(&i->list);
expr_free(i);
@@ -432,14 +409,9 @@ static int set_to_segtree(struct list_head *msgs, struct set *set,
* Insert elements into tree
*/
for (n = 0; n < init->size; n++) {
- if (init->set_flags & NFT_SET_MAP &&
- n < init->size - 1 &&
- interval_conflict(intervals[n], intervals[n+1]))
- return expr_binary_error(msgs,
- intervals[n]->expr,
- intervals[n+1]->expr,
- "conflicting intervals specified");
- ei_insert(tree, intervals[n]);
+ err = ei_insert(msgs, tree, intervals[n], merge);
+ if (err < 0)
+ return err;
}
return 0;