summaryrefslogtreecommitdiffstats
path: root/src
diff options
context:
space:
mode:
authorPablo Neira Ayuso <pablo@netfilter.org>2016-04-22 19:15:34 +0200
committerPablo Neira Ayuso <pablo@netfilter.org>2016-04-27 12:31:58 +0200
commit8d6628ce724e1d01f03b788f60455cce2a4f77aa (patch)
tree3b0ea55c86d8d358048b2db0a3485fc734ef3179 /src
parent4cee1339c61da246aa7b385457318eba88c4a28a (diff)
segtree: add interval overlap detection for dynamic updates
Make sure the new intervals that we want to add are not overlapping with any of the existing ones. Signed-off-by: Pablo Neira Ayuso <pablo@netfilter.org>
Diffstat (limited to 'src')
-rw-r--r--src/segtree.c55
1 files changed, 52 insertions, 3 deletions
diff --git a/src/segtree.c b/src/segtree.c
index 8ac05466..cd300d79 100644
--- a/src/segtree.c
+++ b/src/segtree.c
@@ -327,12 +327,61 @@ static unsigned int expr_to_intervals(const struct expr *set,
return n;
}
-static int set_to_segtree(struct list_head *msgs, struct expr *init,
- struct seg_tree *tree)
+/* 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)
+{
+ 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)
+{
+ struct elementary_interval *new_intervals[init->size];
+ struct elementary_interval *intervals[set->init->size];
+ unsigned int n, m, i, j;
+
+ n = expr_to_intervals(init, keylen, new_intervals);
+ m = expr_to_intervals(set->init, keylen, intervals);
+
+ for (i = 0; i < n; i++) {
+ for (j = 0; j < m; j++) {
+ if (interval_overlap(new_intervals[i], intervals[j]))
+ return expr_error(msgs,
+ new_intervals[i]->expr,
+ "interval overlaps with an existing one");
+ }
+ }
+
+ return 0;
+}
+
+static int set_to_segtree(struct list_head *msgs, struct set *set,
+ struct expr *init, struct seg_tree *tree, bool add)
{
struct elementary_interval *intervals[init->size];
struct expr *i, *next;
unsigned int n;
+ int err;
+
+ /* We are updating an existing set with new elements, check if the new
+ * interval overlaps with any of the existing ones.
+ */
+ if (add && set->init != init) {
+ err = set_overlap(msgs, set, init, tree->keylen);
+ if (err < 0)
+ return err;
+ }
n = expr_to_intervals(init, tree->keylen, intervals);
@@ -491,7 +540,7 @@ int set_to_intervals(struct list_head *errs, struct set *set,
LIST_HEAD(list);
seg_tree_init(&tree, set, init);
- if (set_to_segtree(errs, init, &tree) < 0)
+ if (set_to_segtree(errs, set, init, &tree, add) < 0)
return -1;
segtree_linearize(&list, set, init, &tree, add);