[PATCH 0/3] remove kvm's use of augmented rbtree

[PATCH 0/3] remove kvm's use of augmented rbtree

[Michel Lespinasse]

On Thu, Nov 22, 2012 at 9:49 PM, Michel Lespinasse <walken@google.com> wrote:
> On Thu, Nov 22, 2012 at 9:14 AM, Sasha Levin <sasha.levin@oracle.com> 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.

[PATCH 1/3] kvm: ensure non-overlapping intervals in rb_int_insert()

[Michel Lespinasse]

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 <walken@google.com>

---
 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

[PATCH 2/3] kvm: rb_int_search_single simplification

[Michel Lespinasse]

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 <walken@google.com>

---
 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

[PATCH 3/3] kvm: remove max_high field in rb_int_node structure

[Michel Lespinasse]

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 <walken@google.com>

---
 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

Re: [PATCH 0/3] remove kvm's use of augmented rbtree

[Sasha Levin]

On Sat, Nov 24, 2012 at 9:40 PM, Michel Lespinasse <walken@google.com> wrote:
> On Thu, Nov 22, 2012 at 9:49 PM, Michel Lespinasse <walken@google.com> wrote:
>> On Thu, Nov 22, 2012 at 9:14 AM, Sasha Levin <sasha.levin@oracle.com> 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

Re: [PATCH 0/3] remove kvm's use of augmented rbtree

[Sasha Levin]

Ping?

On Sun, Nov 25, 2012 at 5:14 PM, Sasha Levin <levinsasha928@gmail.com> wrote:
> On Sat, Nov 24, 2012 at 9:40 PM, Michel Lespinasse <walken@google.com> wrote:
>> On Thu, Nov 22, 2012 at 9:49 PM, Michel Lespinasse <walken@google.com> wrote:
>>> On Thu, Nov 22, 2012 at 9:14 AM, Sasha Levin <sasha.levin@oracle.com> 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

Re: [PATCH 0/3] remove kvm's use of augmented rbtree

[Michel Lespinasse]

On Mon, Dec 10, 2012 at 8:22 AM, Sasha Levin <levinsasha928@gmail.com> wrote:
> Ping?

Hey Sasha,

There seems to have been some confusion here. After your last message,
I expected *you* to take the patches and push them towards kvm tree.
But, I guess you were waiting for Pekka's reply first ? Or did you
expect me to go push the patches ?

If it helps, I could push this through Andrew's -mm tree; however I
think it would make the most sense if these could reach linus's tree
through a kvm merge rather than through Andrew's -mm...

> On Sun, Nov 25, 2012 at 5:14 PM, Sasha Levin <levinsasha928@gmail.com> wrote:
>> On Sat, Nov 24, 2012 at 9:40 PM, Michel Lespinasse <walken@google.com> wrote:
>>> On Thu, Nov 22, 2012 at 9:49 PM, Michel Lespinasse <walken@google.com> wrote:
>>>> On Thu, Nov 22, 2012 at 9:14 AM, Sasha Levin <sasha.levin@oracle.com> 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



-- 
Michel "Walken" Lespinasse
A program is never fully debugged until the last user dies.

Re: [PATCH 0/3] remove kvm's use of augmented rbtree

[Sasha Levin]

On 12/10/2012 04:50 PM, Michel Lespinasse wrote:
> On Mon, Dec 10, 2012 at 8:22 AM, Sasha Levin <levinsasha928@gmail.com> wrote:
>> Ping?
> 
> Hey Sasha,
> 
> There seems to have been some confusion here. After your last message,
> I expected *you* to take the patches and push them towards kvm tree.
> But, I guess you were waiting for Pekka's reply first ? Or did you
> expect me to go push the patches ?
> 
> If it helps, I could push this through Andrew's -mm tree; however I
> think it would make the most sense if these could reach linus's tree
> through a kvm merge rather than through Andrew's -mm...

Ah, no, Pekka is the one taking care of the KVM tools tree, so I'm we're waiting
for him to take a look at the patches and take them if they look fine to him :)


Thanks,
Sasha

Re: [PATCH 0/3] remove kvm's use of augmented rbtree

[Pekka Enberg]

On Mon, Dec 10, 2012 at 11:57 PM, Sasha Levin <sasha.levin@oracle.com> wrote:
> On 12/10/2012 04:50 PM, Michel Lespinasse wrote:
>> On Mon, Dec 10, 2012 at 8:22 AM, Sasha Levin <levinsasha928@gmail.com> wrote:
>>> Ping?
>>
>> Hey Sasha,
>>
>> There seems to have been some confusion here. After your last message,
>> I expected *you* to take the patches and push them towards kvm tree.
>> But, I guess you were waiting for Pekka's reply first ? Or did you
>> expect me to go push the patches ?
>>
>> If it helps, I could push this through Andrew's -mm tree; however I
>> think it would make the most sense if these could reach linus's tree
>> through a kvm merge rather than through Andrew's -mm...
>
> Ah, no, Pekka is the one taking care of the KVM tools tree, so I'm we're waiting
> for him to take a look at the patches and take them if they look fine to him :)

Applied, thanks guys!