On Thu, Nov 22, 2012 at 9:49 PM, Michel Lespinasse <[email protected]> wrote:
> On Thu, Nov 22, 2012 at 9:14 AM, Sasha Levin <[email protected]> wrote:
>> The following patch fixed the problem for me:
>>
>> diff --git a/include/linux/rbtree_augmented.h b/include/linux/rbtree_augmented.h
>> index 214caa3..5cfdca6 100644
>> --- a/include/linux/rbtree_augmented.h
>> +++ b/include/linux/rbtree_augmented.h
>> @@ -47,6 +47,7 @@ rb_insert_augmented(struct rb_node *node, struct rb_root *root,
>> const struct rb_augment_callbacks *augment)
>> {
>> __rb_insert_augmented(node, root, augment->rotate);
>> + augment->propagate(node, NULL);
>> }
>
> This would work, but would slow down all sites which already take care
> of updating the augmented information before calling
> rb_insert_augmented, so please don't do that.
>
> The simplest fix would be to add the propagate call where your
> rb_insert_augmented() call site is; the better fix would be to do the
> update incrementally as you search down the tree for the insertion
> point; and the best fix may be to just avoid duplicating that code and
> use interval_tree.h (if your keys are longs) or
> interval_tree_generic.h to generate the proper insert / remove
> functions.
So I had a quick look at linux-next, and my understanding is that the
rbtree-interval API in kvm always stores non-overlapping intervals.
Based on this, the use of augmented rbtrees isn't really justified; it
is just as easy to use a simple rbtree of intervals sorted by the
addresses they cover.
This patchset was generated against the current linux-next. I only
verified that kvm still compiled; obviously this would need more
testing. On the other hand, there are currently some correctness
issues in kvm's implementatin of rbtree intervals, so I think this
simplification should be beneficial.
Michel Lespinasse (3):
kvm: ensure non-overlapping intervals in rb_int_insert()
kvm: rb_int_search_single simplification
kvm: remove max_high field in rb_int_node structure
tools/kvm/include/kvm/rbtree-interval.h | 13 +++--
tools/kvm/util/rbtree-interval.c | 86 ++++---------------------------
2 files changed, 18 insertions(+), 81 deletions(-)
Sasha, could you please check my logic and apply this to the kvm tree ?
Thanks,
--
Michel "Walken" Lespinasse
A program is never fully debugged until the last user dies.
The rbtree interval API is designed for handling non-overlapping intervals;
modify rb_int_insert() to guarantee this property is maintained by
returning -EEXIST when attempting to insert a new interval that overlaps
an existing interval.
Also fix an issue where the computation of 'result' could trigger an
integer overflow which would break the rbtree ordering.
Signed-off-by: Michel Lespinasse <[email protected]>
---
tools/kvm/util/rbtree-interval.c | 10 +++++-----
1 files changed, 5 insertions(+), 5 deletions(-)
diff --git a/tools/kvm/util/rbtree-interval.c b/tools/kvm/util/rbtree-interval.c
index d7fa96a06a92..fd69252bea02 100644
--- a/tools/kvm/util/rbtree-interval.c
+++ b/tools/kvm/util/rbtree-interval.c
@@ -99,13 +99,13 @@ int rb_int_insert(struct rb_root *root, struct rb_int_node *i_node)
struct rb_node **node = &root->rb_node, *parent = NULL;
while (*node) {
- int result = i_node->low - rb_int(*node)->low;
+ struct rb_int_node *cur = rb_int(*node);
parent = *node;
- if (result < 0)
- node = &((*node)->rb_left);
- else if (result > 0)
- node = &((*node)->rb_right);
+ if (i_node->high <= cur->low)
+ node = &cur->node.rb_left;
+ else if (cur->high <= i_node->low)
+ node = &cur->node.rb_right;
else
return -EEXIST;
}
--
1.7.7.3
As the rbtree intervals are not overlapping, rb_int_search_single can
trivially be implemented without making use of the max_high field.
Signed-off-by: Michel Lespinasse <[email protected]>
---
tools/kvm/util/rbtree-interval.c | 18 +++++-------------
1 files changed, 5 insertions(+), 13 deletions(-)
diff --git a/tools/kvm/util/rbtree-interval.c b/tools/kvm/util/rbtree-interval.c
index fd69252bea02..740ff0d87536 100644
--- a/tools/kvm/util/rbtree-interval.c
+++ b/tools/kvm/util/rbtree-interval.c
@@ -5,27 +5,19 @@
struct rb_int_node *rb_int_search_single(struct rb_root *root, u64 point)
{
struct rb_node *node = root->rb_node;
- struct rb_node *lowest = NULL;
while (node) {
struct rb_int_node *cur = rb_int(node);
- if (node->rb_left && (rb_int(node->rb_left)->max_high > point)) {
+ if (point < cur->low)
node = node->rb_left;
- } else if (cur->low <= point && cur->high > point) {
- lowest = node;
- break;
- } else if (point > cur->low) {
+ else if (cur->high <= point)
node = node->rb_right;
- } else {
- break;
- }
+ else
+ return cur;
}
- if (lowest == NULL)
- return NULL;
-
- return rb_int(lowest);
+ return NULL;
}
struct rb_int_node *rb_int_search_range(struct rb_root *root, u64 low, u64 high)
--
1.7.7.3
Since nothing depends on the max_high field values anymore, we can just
remove the field and the code that was used to maintain it.
Signed-off-by: Michel Lespinasse <[email protected]>
---
tools/kvm/include/kvm/rbtree-interval.h | 13 ++++---
tools/kvm/util/rbtree-interval.c | 58 +------------------------------
2 files changed, 8 insertions(+), 63 deletions(-)
diff --git a/tools/kvm/include/kvm/rbtree-interval.h b/tools/kvm/include/kvm/rbtree-interval.h
index fb2102ab33a6..730eb5e8551d 100644
--- a/tools/kvm/include/kvm/rbtree-interval.h
+++ b/tools/kvm/include/kvm/rbtree-interval.h
@@ -1,20 +1,17 @@
#ifndef KVM__INTERVAL_RBTREE_H
#define KVM__INTERVAL_RBTREE_H
-#include <linux/rbtree_augmented.h>
+#include <linux/rbtree.h>
#include <linux/types.h>
#define RB_INT_INIT(l, h) \
- (struct rb_int_node){.low = l, .high = h, .max_high = h}
+ (struct rb_int_node){.low = l, .high = h}
#define rb_int(n) rb_entry(n, struct rb_int_node, node)
struct rb_int_node {
struct rb_node node;
u64 low;
u64 high;
-
- /* max_high will store the highest high of it's 2 children. */
- u64 max_high;
};
/* Return the rb_int_node interval in which 'point' is located. */
@@ -24,6 +21,10 @@ struct rb_int_node *rb_int_search_single(struct rb_root *root, u64 point);
struct rb_int_node *rb_int_search_range(struct rb_root *root, u64 low, u64 high);
int rb_int_insert(struct rb_root *root, struct rb_int_node *data);
-void rb_int_erase(struct rb_root *root, struct rb_int_node *node);
+
+static inline void rb_int_erase(struct rb_root *root, struct rb_int_node *node)
+{
+ rb_erase(&node->node, root);
+}
#endif
diff --git a/tools/kvm/util/rbtree-interval.c b/tools/kvm/util/rbtree-interval.c
index 740ff0d87536..3630a6d80d6e 100644
--- a/tools/kvm/util/rbtree-interval.c
+++ b/tools/kvm/util/rbtree-interval.c
@@ -35,57 +35,6 @@ struct rb_int_node *rb_int_search_range(struct rb_root *root, u64 low, u64 high)
return range;
}
-/*
- * Update a node after it has been linked into the tree:
- */
-static void propagate_callback(struct rb_node *node, struct rb_node *stop)
-{
- struct rb_int_node *i_node;
-
- if (node == stop)
- return;
-
- i_node = rb_int(node);
- i_node->max_high = i_node->high;
-
- if (node->rb_left)
- i_node->max_high = max(i_node->max_high, rb_int(node->rb_left)->max_high);
- if (node->rb_right)
- i_node->max_high = max(i_node->max_high, rb_int(node->rb_right)->max_high);
-}
-
-/*
- * Copy the extra data to a new node:
- */
-static void copy_callback(struct rb_node *node_old, struct rb_node *node_new)
-{
- struct rb_int_node *i_node_old = rb_int(node_old);
- struct rb_int_node *i_node_new = rb_int(node_new);
-
- i_node_new->low = i_node_old->low;
- i_node_new->high = i_node_old->high;
-
- i_node_new->max_high = i_node_old->max_high;
-}
-
-/*
- * Update after tree rotation:
- */
-static void rotate_callback(struct rb_node *node_old, struct rb_node *node_new)
-{
- propagate_callback(node_old, NULL);
- propagate_callback(node_new, NULL);
-}
-
-/*
- * All augmented rbtree callbacks:
- */
-struct rb_augment_callbacks callbacks = {
- .propagate = propagate_callback,
- .copy = copy_callback,
- .rotate = rotate_callback,
-};
-
int rb_int_insert(struct rb_root *root, struct rb_int_node *i_node)
{
struct rb_node **node = &root->rb_node, *parent = NULL;
@@ -103,12 +52,7 @@ int rb_int_insert(struct rb_root *root, struct rb_int_node *i_node)
}
rb_link_node(&i_node->node, parent, node);
- rb_insert_augmented(&i_node->node, root, &callbacks);
+ rb_insert_color(&i_node->node, root);
return 0;
}
-
-void rb_int_erase(struct rb_root *root, struct rb_int_node *node)
-{
- rb_erase_augmented(&node->node, root, &callbacks);
-}
--
1.7.7.3
On Sat, Nov 24, 2012 at 9:40 PM, Michel Lespinasse <[email protected]> wrote:
> On Thu, Nov 22, 2012 at 9:49 PM, Michel Lespinasse <[email protected]> wrote:
>> On Thu, Nov 22, 2012 at 9:14 AM, Sasha Levin <[email protected]> wrote:
>>> The following patch fixed the problem for me:
>>>
>>> diff --git a/include/linux/rbtree_augmented.h b/include/linux/rbtree_augmented.h
>>> index 214caa3..5cfdca6 100644
>>> --- a/include/linux/rbtree_augmented.h
>>> +++ b/include/linux/rbtree_augmented.h
>>> @@ -47,6 +47,7 @@ rb_insert_augmented(struct rb_node *node, struct rb_root *root,
>>> const struct rb_augment_callbacks *augment)
>>> {
>>> __rb_insert_augmented(node, root, augment->rotate);
>>> + augment->propagate(node, NULL);
>>> }
>>
>> This would work, but would slow down all sites which already take care
>> of updating the augmented information before calling
>> rb_insert_augmented, so please don't do that.
>>
>> The simplest fix would be to add the propagate call where your
>> rb_insert_augmented() call site is; the better fix would be to do the
>> update incrementally as you search down the tree for the insertion
>> point; and the best fix may be to just avoid duplicating that code and
>> use interval_tree.h (if your keys are longs) or
>> interval_tree_generic.h to generate the proper insert / remove
>> functions.
>
> So I had a quick look at linux-next, and my understanding is that the
> rbtree-interval API in kvm always stores non-overlapping intervals.
> Based on this, the use of augmented rbtrees isn't really justified; it
> is just as easy to use a simple rbtree of intervals sorted by the
> addresses they cover.
>
> This patchset was generated against the current linux-next. I only
> verified that kvm still compiled; obviously this would need more
> testing. On the other hand, there are currently some correctness
> issues in kvm's implementatin of rbtree intervals, so I think this
> simplification should be beneficial.
>
> Michel Lespinasse (3):
> kvm: ensure non-overlapping intervals in rb_int_insert()
> kvm: rb_int_search_single simplification
> kvm: remove max_high field in rb_int_node structure
>
> tools/kvm/include/kvm/rbtree-interval.h | 13 +++--
> tools/kvm/util/rbtree-interval.c | 86 ++++---------------------------
> 2 files changed, 18 insertions(+), 81 deletions(-)
>
> Sasha, could you please check my logic and apply this to the kvm tree ?
When I've initially added the interval tree I figured we might need to
allow overlapping for future arches which might need it. Since we now
have extra 2 arches I guess we don't really need it. So I guess we're
fine with removing it.
Pekka?
Thanks,
Sasha