On Sun, Feb 12, 2012 at 01:21:36AM +0100, Andrea Righi wrote:
> Add a generic infrastructure to efficiently keep track of intervals.
>
> An interval is represented by a triplet (start, end, type). The values
> (start, end) define the bounds of the range. The type is a generic
> property associated to the interval. The interpretation of the type is
> left to the user.
>
> Multiple intervals associated to the same object are stored in an
> interval tree (augmented rbtree) [1], with tree ordered on starting
> address. The tree cannot contain multiple entries of different
> interval types which overlap; in case of overlapping intervals new
> inserted intervals overwrite the old ones (completely or in part, in the
> second case the old interval is shrunk or split accordingly).
>
> Reference:
> [1] "Introduction to Algorithms" by Cormen, Leiserson, Rivest and Stein
>
> Signed-off-by: Andrea Righi <andrea@xxxxxxxxxxxxxxx>
> ---
For those who are interested, I've an extra patch for this part (must be
applied on top of the previous one): there's a bug fix and some
improvements.
I'll include the following fix in the next version of the
POSIX_FADV_NOREUSE patch set (sorry for this, but the whole patch set is
still totally experimental, especially the kinterval part, I also plan
to add a proper documentation and a sample test case in the samples/ dir
if we think it'll be useful).
Thanks,
-Andrea
---
From: Andrea Righi <andrea@xxxxxxxxxxxxxxx>
Subject: [PATCH] kinterval: fix interval boundaries and optimize insertion/removal
Use the right notation [start, end) instead of [start, end] for interval
boundaries, so now an interval does not include its endpoint. This is
the natural way to define a memory range (i.e, 0-4096 = all bytes
between 0 and 4095 included) and it makes easier to reuse this code also
for other similar cases.
Moreover, optimize insertion and removal code to be actually O(log(n)).
Signed-off-by: Andrea Righi <andrea@xxxxxxxxxxxxxxx>
---
include/linux/kinterval.h | 2 +-
lib/kinterval.c | 135 ++++++++++++++++++++++++++++-----------------
2 files changed, 86 insertions(+), 51 deletions(-)
diff --git a/include/linux/kinterval.h b/include/linux/kinterval.h
index 8152265..7a505f4 100644
--- a/include/linux/kinterval.h
+++ b/include/linux/kinterval.h
@@ -114,7 +114,7 @@ long kinterval_lookup_range(struct rb_root *root, u64 start, u64 end);
*/
static inline long kinterval_lookup(struct rb_root *root, u64 addr)
{
- return kinterval_lookup_range(root, addr, addr);
+ return kinterval_lookup_range(root, addr, addr + 1);
}
/**
diff --git a/lib/kinterval.c b/lib/kinterval.c
index 2a9d463..28ee627 100644
--- a/lib/kinterval.c
+++ b/lib/kinterval.c
@@ -31,7 +31,7 @@ static struct kmem_cache *kinterval_cachep __read_mostly;
static bool is_interval_overlapping(struct kinterval *node, u64 start, u64 end)
{
- return !(node->start > end || node->end < start);
+ return !(node->start >= end || node->end <= start);
}
static u64 get_subtree_max_end(struct rb_node *node)
@@ -76,23 +76,65 @@ static struct kinterval *
kinterval_rb_lowest_match(struct rb_root *root, u64 start, u64 end)
{
struct rb_node *node = root->rb_node;
- struct kinterval *lower_range = NULL;
+ struct kinterval *lowest_match = NULL;
while (node) {
struct kinterval *range = rb_entry(node, struct kinterval, rb);
if (get_subtree_max_end(node->rb_left) > start) {
+ /* Lowest overlap if any must be on the left side */
node = node->rb_left;
} else if (is_interval_overlapping(range, start, end)) {
- lower_range = range;
+ lowest_match = range;
break;
} else if (start >= range->start) {
+ /* Lowest overlap if any must be on the right side */
node = node->rb_right;
} else {
break;
}
}
- return lower_range;
+ return lowest_match;
+}
+
+/*
+ * Merge two adjacent intervals, if they can be merged next is removed from the
+ * tree.
+ */
+static void kinterval_rb_merge_node(struct rb_root *root,
+ struct kinterval *prev, struct kinterval *next)
+{
+ struct rb_node *deepest;
+
+ if (prev && prev->type == next->type && prev->end == next->start) {
+ prev->end = next->end;
+ deepest = rb_augment_erase_begin(&next->rb);
+ rb_erase(&next->rb, root);
+ rb_augment_erase_end(deepest,
+ kinterval_rb_augment_cb, NULL);
+ kmem_cache_free(kinterval_cachep, next);
+ }
+}
+
+/*
+ * Try to merge a new inserted interval with the previous and the next
+ * interval.
+ */
+static void kinterval_rb_merge(struct rb_root *root, struct kinterval *new)
+{
+ struct kinterval *next, *prev;
+ struct rb_node *node;
+
+ node = rb_prev(&new->rb);
+ prev = node ? rb_entry(node, struct kinterval, rb) : NULL;
+
+ node = rb_next(&new->rb);
+ next = node ? rb_entry(node, struct kinterval, rb) : NULL;
+
+ if (next)
+ kinterval_rb_merge_node(root, new, next);
+ if (prev)
+ kinterval_rb_merge_node(root, prev, new);
}
static void
@@ -114,32 +156,8 @@ kinterval_rb_insert(struct rb_root *root, struct kinterval *new)
rb_link_node(&new->rb, parent, node);
rb_insert_color(&new->rb, root);
rb_augment_insert(&new->rb, kinterval_rb_augment_cb, NULL);
-}
-/* Merge adjacent intervals */
-static void kinterval_rb_merge(struct rb_root *root)
-{
- struct kinterval *next, *prev = NULL;
- struct rb_node *node, *deepest;
-
- node = rb_first(root);
- while (node) {
- next = rb_entry(node, struct kinterval, rb);
- node = rb_next(&next->rb);
-
- if (prev && prev->type == next->type &&
- prev->end == (next->start - 1) &&
- prev->end < next->start) {
- prev->end = next->end;
- deepest = rb_augment_erase_begin(&next->rb);
- rb_erase(&next->rb, root);
- rb_augment_erase_end(deepest,
- kinterval_rb_augment_cb, NULL);
- kmem_cache_free(kinterval_cachep, next);
- } else {
- prev = next;
- }
- }
+ kinterval_rb_merge(root, new);
}
static int kinterval_rb_check_add(struct rb_root *root,
@@ -148,16 +166,17 @@ static int kinterval_rb_check_add(struct rb_root *root,
struct kinterval *old;
struct rb_node *node, *deepest;
- node = rb_first(root);
+ old = kinterval_rb_lowest_match(root, new->start, new->end);
+ node = old ? &old->rb : NULL;
+
while (node) {
old = rb_entry(node, struct kinterval, rb);
+ node = rb_next(&old->rb);
+
/* Check all the possible matches within the range */
- if (old->start > new->end)
+ if (old->start >= new->end)
break;
- node = rb_next(&old->rb);
- if (!is_interval_overlapping(old, new->start, new->end))
- continue;
/*
* Interval is overlapping another one, shrink the old interval
* accordingly.
@@ -206,8 +225,12 @@ static int kinterval_rb_check_add(struct rb_root *root,
* new old
* |___________|_______|
*/
+ deepest = rb_augment_erase_begin(&old->rb);
rb_erase(&old->rb, root);
+ rb_augment_erase_end(deepest, kinterval_rb_augment_cb,
+ NULL);
old->start = new->end + 1;
+ old->subtree_max_end = old->end;
kinterval_rb_insert(root, old);
break;
} else if (new->start >= old->start && new->end >= old->end) {
@@ -230,7 +253,7 @@ static int kinterval_rb_check_add(struct rb_root *root,
rb_erase(&old->rb, root);
rb_augment_erase_end(deepest, kinterval_rb_augment_cb,
NULL);
- old->end = new->start - 1;
+ old->end = new->start;
old->subtree_max_end = old->end;
kinterval_rb_insert(root, old);
} else if (new->start >= old->start && new->end <= old->end) {
@@ -261,13 +284,17 @@ static int kinterval_rb_check_add(struct rb_root *root,
if (unlikely(!prev))
return -ENOMEM;
+ deepest = rb_augment_erase_begin(&old->rb);
rb_erase(&old->rb, root);
+ rb_augment_erase_end(deepest, kinterval_rb_augment_cb,
+ NULL);
prev->start = old->start;
- old->start = new->end + 1;
- prev->end = new->start - 1;
+ old->start = new->end;
+ prev->end = new->start;
prev->type = old->type;
+ old->subtree_max_end = old->end;
kinterval_rb_insert(root, old);
new->subtree_max_end = new->end;
@@ -280,7 +307,6 @@ static int kinterval_rb_check_add(struct rb_root *root,
}
new->subtree_max_end = new->end;
kinterval_rb_insert(root, new);
- kinterval_rb_merge(root);
return 0;
}
@@ -291,7 +317,7 @@ int kinterval_add(struct rb_root *root, u64 start, u64 end,
struct kinterval *range;
int ret;
- if (end < start)
+ if (end <= start)
return -EINVAL;
range = kmem_cache_zalloc(kinterval_cachep, flags);
if (unlikely(!range))
@@ -314,16 +340,17 @@ static int kinterval_rb_check_del(struct rb_root *root,
struct kinterval *old;
struct rb_node *node, *deepest;
- node = rb_first(root);
+ old = kinterval_rb_lowest_match(root, start, end);
+ node = old ? &old->rb : NULL;
+
while (node) {
old = rb_entry(node, struct kinterval, rb);
+ node = rb_next(&old->rb);
+
/* Check all the possible matches within the range */
- if (old->start > end)
+ if (old->start >= end)
break;
- node = rb_next(&old->rb);
- if (!is_interval_overlapping(old, start, end))
- continue;
if (start <= old->start && end >= old->end) {
/*
* Completely erase the old range:
@@ -354,8 +381,12 @@ static int kinterval_rb_check_del(struct rb_root *root,
* old
* |_______|
*/
+ deepest = rb_augment_erase_begin(&old->rb);
rb_erase(&old->rb, root);
- old->start = end + 1;
+ rb_augment_erase_end(deepest, kinterval_rb_augment_cb,
+ NULL);
+ old->start = end;
+ old->subtree_max_end = old->end;
kinterval_rb_insert(root, old);
break;
} else if (start >= old->start && end >= old->end) {
@@ -378,7 +409,7 @@ static int kinterval_rb_check_del(struct rb_root *root,
rb_erase(&old->rb, root);
rb_augment_erase_end(deepest, kinterval_rb_augment_cb,
NULL);
- old->end = start - 1;
+ old->end = start;
old->subtree_max_end = old->end;
kinterval_rb_insert(root, old);
} else if (start >= old->start && end <= old->end) {
@@ -403,13 +434,17 @@ static int kinterval_rb_check_del(struct rb_root *root,
if (unlikely(!prev))
return -ENOMEM;
+ deepest = rb_augment_erase_begin(&old->rb);
rb_erase(&old->rb, root);
+ rb_augment_erase_end(deepest, kinterval_rb_augment_cb,
+ NULL);
prev->start = old->start;
- old->start = end + 1;
- prev->end = start - 1;
+ old->start = end;
+ prev->end = start;
prev->type = old->type;
+ old->subtree_max_end = old->end;
kinterval_rb_insert(root, old);
prev->subtree_max_end = prev->end;
@@ -422,7 +457,7 @@ static int kinterval_rb_check_del(struct rb_root *root,
int kinterval_del(struct rb_root *root, u64 start, u64 end, gfp_t flags)
{
- if (end < start)
+ if (end <= start)
return -EINVAL;
return kinterval_rb_check_del(root, start, end, flags);
}
@@ -451,7 +486,7 @@ long kinterval_lookup_range(struct rb_root *root, u64 start, u64 end)
{
struct kinterval *range;
- if (end < start)
+ if (end <= start)
return -EINVAL;
range = kinterval_rb_lowest_match(root, start, end);
return range ? range->type : -ENOENT;
--
1.7.5.4
--
To unsubscribe from this list: send the line "unsubscribe linux-fsdevel" in
the body of a message to majordomo@xxxxxxxxxxxxxxx
More majordomo info at http://vger.kernel.org/majordomo-info.html
