rbtree: Add some necessary condition checks

From: Zhi Yong Wu <[email protected]>

Signed-off-by Zhi Yong Wu <[email protected]>

---
 include/linux/rbtree_augmented.h | 3 ++-
 lib/rbtree.c                     | 5 +++--
 2 files changed, 5 insertions(+), 3 deletions(-)

Quoted 7 lines · On Fri, Aug 23, 2013 at 7:45 AM, <[email protected]> wrote:

From: Zhi Yong Wu <[email protected]>

Signed-off-by Zhi Yong Wu <[email protected]>

---
 include/linux/rbtree_augmented.h | 3 ++-
 lib/rbtree.c                     | 5 +++--
 2 files changed, 5 insertions(+), 3 deletions(-)

So, you are saying that the checks are necessary, but you are not saying why.

The way I see it, the checks are *not* necessary, because the rbtree invariants guarantee them to be true. The only way for the checks to fail would be if people directly manipulate the rbtrees without going through the proper APIs, and if they do that then I think they're on their own. So to me, I think it's the same situation as dereferencing a pointer without checking if it's NULL, because you know it should never be NULL - which in my eyes is perfectly acceptable.

If you really feel this is a problem, you should explain why. I would also prefer if any checks you add could be limited to debug builds.

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

Quoted 11 lines · Michel Lespinasse

Quoted 7 lines · On Fri, Aug 23, 2013 at 7:45 AM, <[email protected]> wrote:

From: Zhi Yong Wu <[email protected]>

Signed-off-by Zhi Yong Wu <[email protected]>

---
 include/linux/rbtree_augmented.h | 3 ++-
 lib/rbtree.c                     | 5 +++--
 2 files changed, 5 insertions(+), 3 deletions(-)

So, you are saying that the checks are necessary, but you are not saying why.

Quoted 7 lines

The way I see it, the checks are *not* necessary, because the rbtree invariants guarantee them to be true. The only way for the checks to fail would be if people directly manipulate the rbtrees without going through the proper APIs, and if they do that then I think they're on their own. So to me, I think it's the same situation as dereferencing a pointer without checking if it's NULL, because you know it should never be NULL - which in my eyes is perfectly acceptable.

In my patchset, some rbtree APIs to be invoked, and I think that those rbtree APIs are used corrently, Below is the pointer of its code:
https://github.com/wuzhy/kernel/compare/torvalds:master...hot_tracking
But I hit some issues when using compilebench to do perf benchmark. compile dir kernel-7 691MB in 8.92 seconds (77.53 MB/s)

include/linux/rbtree_augmented.h +0 -0

index fea49b5..7d19770 100644

Quoted 19 lines · Zhi Yong Wu

Quoted 11 lines · Michel Lespinasse

Quoted 7 lines · On Fri, Aug 23, 2013 at 7:45 AM, <[email protected]> wrote:

From: Zhi Yong Wu <[email protected]>

Signed-off-by Zhi Yong Wu <[email protected]>

---
 include/linux/rbtree_augmented.h | 3 ++-
 lib/rbtree.c                     | 5 +++--
 2 files changed, 5 insertions(+), 3 deletions(-)

So, you are saying that the checks are necessary, but you are not saying why.

Quoted 7 lines

The way I see it, the checks are *not* necessary, because the rbtree invariants guarantee them to be true. The only way for the checks to fail would be if people directly manipulate the rbtrees without going through the proper APIs, and if they do that then I think they're on their own. So to me, I think it's the same situation as dereferencing a pointer without checking if it's NULL, because you know it should never be NULL - which in my eyes is perfectly acceptable.

Quoted 5 lines

In my patchset, some rbtree APIs to be invoked, and I think that those rbtree APIs are used corrently, Below is the pointer of its code:
https://github.com/wuzhy/kernel/compare/torvalds:master...hot_tracking
But I hit some issues when using compilebench to do perf benchmark. compile dir kernel-7 691MB in 8.92 seconds (77.53 MB/s)

Thanks for the link - I now better understand where you are coming from with these fixes.

Going back to the original message:

Quoted 12 lines

include/linux/rbtree_augmented.h +2 -1

index fea49b5..7d19770 100644
@@ -199,7 +199,8 @@ __rb_erase_augmented(struct rb_node *node, struct rb_root *root,
                }
 
                successor->rb_left = tmp = node->rb_left;
-               rb_set_parent(tmp, successor);
+               if (tmp)
+                       rb_set_parent(tmp, successor);
 

include/linux/rbtree_augmented.h __rb_erase_augmented(struct rb_node *node, struct rb_root *root, · line 206

Quoted 2 lines

include/linux/rbtree_augmented.h +0 -0

                pc = node->__rb_parent_color;
                tmp = __rb_parent(pc);

Note that node->rb_left was already fetched at the top of __rb_erase_augmented(), and was checked to be non-NULL at the time - otherwise we would have executed 'Case 1' in that function. So, you

are not expected to find tmp == NULL here.

lib/rbtree.c ____rb_erase_color(struct rb_node *parent, struct rb_root *root, · line 220

Quoted 13 lines

lib/rbtree.c +1 -1

index c0e31fe..2cb01ba 100644
@@ -214,7 +214,7 @@ ____rb_erase_color(struct rb_node *parent, struct rb_root *root,
                 */
                sibling = parent->rb_right;
                if (node != sibling) {  /* node == parent->rb_left */
-                       if (rb_is_red(sibling)) {
+                       if (sibling && rb_is_red(sibling)) {
                                /*
                                 * Case 1 - left rotate at parent
                                 *

Note the loop invariants quoted just above:

/*
* Loop invariants:
* - node is black (or NULL on first iteration)
* - node is not the root (parent is not NULL)
* - All leaf paths going through parent and node have a
* black node count that is 1 lower than other leaf paths.
*/

Because of these, each path from sibling to a leaf must include at least one black node, which implies that sibling can't be NULL - or to put it another way, if sibling is null then the expected invariants were violated before we even got there.

lib/rbtree.c ____rb_erase_color(struct rb_node *parent, struct rb_root *root, · line 233

Quoted 11 lines

lib/rbtree.c +2 -1

@@ -226,7 +226,8 @@ ____rb_erase_color(struct rb_node *parent, struct rb_root *root,
                                 */
                                parent->rb_right = tmp1 = sibling->rb_left;
                                sibling->rb_left = parent;
-                               rb_set_parent_color(tmp1, parent, RB_BLACK);
+                               if (tmp1)
+                                       rb_set_parent_color(tmp1, parent, RB_BLACK);
                                __rb_rotate_set_parents(parent, sibling, root,
                                                        RB_RED);
                                augment_rotate(parent, sibling);

This is actually the same invariant here - each path from sibling to a leaf must include at least one black node, and sibling is now known to be red, so it must have two black children.

Now I had a quick look at your code and I couldn't tell at which point the invariants are violated. However I did notice a couple suspicious things in the very first patch (f5c8f2b256d87ac0bf789a787e6b795ac0c736e8):

1- In both hot_range_tree_free() and and hot_tree_exit(), you try to destroy rb trees by iterating on each node with rb_next() and then

freeing them. Note that rb_next() can reference prior nodes, which have already been freed in your scheme, so that seems quite unsafe.

The simplest fix would be to do a full rb_erase() on each node before

freeing it. (you may be able to avoid rebalancing the tree here as you're going to destroy it all, but if you really have that need it would be better to come up with a new API to cover it rather than hardcode it where you need it - I think it's easiest to start with the simple dumb fix of using rb_erase).

2- I did not look long enough to understand the locking, but it wasn't clear to me if you lock the rbtrees when doing rb_erase() on them (while I could more clearly see that you do it for insertions).

I'm really not sure if either of these will fix the issues you're seeing, though. What I would try next would be to add explicit rbtree invariant checks before and after rbtree manipulations, like what the check() function does in lib/rbtree_test.c, to see at which point do they get broken.

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

Quoted 17 lines · Michel Lespinasse

Thanks for the link - I now better understand where you are coming from with these fixes.

Going back to the original message:

Quoted 12 lines

include/linux/rbtree_augmented.h +2 -1

index fea49b5..7d19770 100644
@@ -199,7 +199,8 @@ __rb_erase_augmented(struct rb_node *node, struct rb_root *root,
                }
 
                successor->rb_left = tmp = node->rb_left;
-               rb_set_parent(tmp, successor);
+               if (tmp)
+                       rb_set_parent(tmp, successor);
 

Quoted 6 lines

include/linux/rbtree_augmented.h __rb_erase_augmented(struct rb_node *node, struct rb_root *root, · line 206

Quoted 2 lines

include/linux/rbtree_augmented.h +0 -0

                pc = node->__rb_parent_color;
                tmp = __rb_parent(pc);

Note that node->rb_left was already fetched at the top of __rb_erase_augmented(), and was checked to be non-NULL at the time - otherwise we would have executed 'Case 1' in that function. So, you

If 'Case 1' is executed, this line of code is also done, how about the result? 'Case 1' seems *not* to change node->rb_left at all.

Quoted 24 lines

lib/rbtree.c ____rb_erase_color(struct rb_node *parent, struct rb_root *root, · line 220

Quoted 13 lines

lib/rbtree.c +1 -1

index c0e31fe..2cb01ba 100644
@@ -214,7 +214,7 @@ ____rb_erase_color(struct rb_node *parent, struct rb_root *root,
                 */
                sibling = parent->rb_right;
                if (node != sibling) {  /* node == parent->rb_left */
-                       if (rb_is_red(sibling)) {
+                       if (sibling && rb_is_red(sibling)) {
                                /*
                                 * Case 1 - left rotate at parent
                                 *

Note the loop invariants quoted just above:

/*
* Loop invariants:
* - node is black (or NULL on first iteration)
* - node is not the root (parent is not NULL)
* - All leaf paths going through parent and node have a
* black node count that is 1 lower than other leaf paths.
*/

Quoted 4 lines

Because of these, each path from sibling to a leaf must include at least one black node, which implies that sibling can't be NULL - or to put it another way, if sibling is null then the expected invariants were violated before we even got there.

In theory, i can understand what you mean, But don't know why and where it got violated.

Quoted 7 lines

Now I had a quick look at your code and I couldn't tell at which point the invariants are violated. However I did notice a couple suspicious things in the very first patch (f5c8f2b256d87ac0bf789a787e6b795ac0c736e8):

1- In both hot_range_tree_free() and and hot_tree_exit(), you try to destroy rb trees by iterating on each node with rb_next() and then

yes, but this item may not been freed immediately, You can know each item has its ref count.

Quoted 2 lines

freeing them. Note that rb_next() can reference prior nodes, which have already been freed in your scheme, so that seems quite unsafe.

I checked rb_next() function, and found that if its prior nodes are freed, is this node's parent not NULL?

Quoted 1 line

The simplest fix would be to do a full rb_erase() on each node before

full rb_erase()? sorry, i don't get what you mean. Do you mean we should erase all nodes from rbtree, then begin to free them? If yes, how to iterate them? If no, can you elaborate it?

Quoted 3 lines

2- I did not look long enough to understand the locking, but it wasn't clear to me if you lock the rbtrees when doing rb_erase() on them (while I could more clearly see that you do it for insertions).

Yes, it get locking when doing rb_erase() or rb_insert(). You can see there are multiple functions maybe rbtree at the same time. To sync them, we need to lock the rbtree.

Quoted 5 lines

I'm really not sure if either of these will fix the issues you're seeing, though. What I would try next would be to add explicit rbtree invariant checks before and after rbtree manipulations, like what the check() function does in lib/rbtree_test.c, to see at which point do they get broken.

Great, any progress so far? :)

Quoted 24 lines · Zhi Yong Wu

Quoted 23 lines · Michel Lespinasse

Thanks for the link - I now better understand where you are coming from with these fixes.

Going back to the original message:

Quoted 5 lines

include/linux/rbtree_augmented.h +0 -0

index fea49b5..7d19770 100644

include/linux/rbtree_augmented.h __rb_erase_augmented(struct rb_node *node, struct rb_root *root, · line 206

Quoted 9 lines

include/linux/rbtree_augmented.h +2 -1

@@ -199,7 +199,8 @@ __rb_erase_augmented(struct rb_node *node, struct rb_root *root,
                }
 
                successor->rb_left = tmp = node->rb_left;
-               rb_set_parent(tmp, successor);
+               if (tmp)
+                       rb_set_parent(tmp, successor);
 
                pc = node->__rb_parent_color;
                tmp = __rb_parent(pc);

Note that node->rb_left was already fetched at the top of __rb_erase_augmented(), and was checked to be non-NULL at the time - otherwise we would have executed 'Case 1' in that function. So, you

Quoted 2 lines

If 'Case 1' is executed, this line of code is also done, how about the result? 'Case 1' seems *not* to change node->rb_left at all.

Wait, I believe this line of code is executed only in Case 2 and Case 3 ?

Quoted 29 lines

Quoted 29 lines

Quoted 6 lines

lib/rbtree.c +0 -0

index c0e31fe..2cb01ba 100644

lib/rbtree.c ____rb_erase_color(struct rb_node *parent, struct rb_root *root, · line 220

Quoted 8 lines

lib/rbtree.c +1 -1

@@ -214,7 +214,7 @@ ____rb_erase_color(struct rb_node *parent, struct rb_root *root,
                 */
                sibling = parent->rb_right;
                if (node != sibling) {  /* node == parent->rb_left */
-                       if (rb_is_red(sibling)) {
+                       if (sibling && rb_is_red(sibling)) {
                                /*
                                 * Case 1 - left rotate at parent
                                 *

Note the loop invariants quoted just above:

/*
* Loop invariants:
* - node is black (or NULL on first iteration)
* - node is not the root (parent is not NULL)
* - All leaf paths going through parent and node have a
* black node count that is 1 lower than other leaf paths.
*/

Because of these, each path from sibling to a leaf must include at least one black node, which implies that sibling can't be NULL - or to put it another way, if sibling is null then the expected invariants were violated before we even got there.

Quoted 2 lines

In theory, i can understand what you mean, But don't know why and where it got violated.

Same here. My point is, I don't think we can fix the issue without answering that question.

Quoted 6 lines

Quoted 6 lines

Now I had a quick look at your code and I couldn't tell at which point the invariants are violated. However I did notice a couple suspicious things in the very first patch (f5c8f2b256d87ac0bf789a787e6b795ac0c736e8):

Quoted 4 lines

Quoted 2 lines

1- In both hot_range_tree_free() and and hot_tree_exit(), you try to destroy rb trees by iterating on each node with rb_next() and then

yes, but this item may not been freed immediately, You can know each item has its ref count.

Are items guaranteed to have another refcount than the one we're dropping ?

Quoted 5 lines

Quoted 3 lines

freeing them. Note that rb_next() can reference prior nodes, which have already been freed in your scheme, so that seems quite unsafe.

I checked rb_next() function, and found that if its prior nodes are freed, is this node's parent not NULL?

No, if the parent was freed with just a put() operation, the child will still have a pointer to it. This is why I suggested using rb_erase() on each node before freeing them, so that we don't keep pointers to freed nodes.

Quoted 5 lines

Quoted 2 lines

The simplest fix would be to do a full rb_erase() on each node before

full rb_erase()? sorry, i don't get what you mean. Do you mean we should erase all nodes from rbtree, then begin to free them? If yes, how to iterate them? If no, can you elaborate it?

No, I meant to call rb_erase() on each individual node right before the corresponding put() operation.

Quoted 7 lines

Quoted 4 lines

2- I did not look long enough to understand the locking, but it wasn't clear to me if you lock the rbtrees when doing rb_erase() on them (while I could more clearly see that you do it for insertions).

Yes, it get locking when doing rb_erase() or rb_insert(). You can see there are multiple functions maybe rbtree at the same time. To sync them, we need to lock the rbtree.

Yes, agree we need to lock rbtree in all such operations. I just wasn't able to determine if it's done around rb_erase() calls, but it definitely needs to be.

Quoted 6 lines

Quoted 5 lines

I'm really not sure if either of these will fix the issues you're seeing, though. What I would try next would be to add explicit rbtree invariant checks before and after rbtree manipulations, like what the check() function does in lib/rbtree_test.c, to see at which point do they get broken.

Great, any progress so far? :)

Unfortunately no.

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

Quoted 18 lines · Zhi Yong Wu

Quoted 17 lines · Michel Lespinasse

Thanks for the link - I now better understand where you are coming from with these fixes.

Going back to the original message:

Quoted 12 lines

include/linux/rbtree_augmented.h +2 -1

index fea49b5..7d19770 100644
@@ -199,7 +199,8 @@ __rb_erase_augmented(struct rb_node *node, struct rb_root *root,
                }
 
                successor->rb_left = tmp = node->rb_left;
-               rb_set_parent(tmp, successor);
+               if (tmp)
+                       rb_set_parent(tmp, successor);
 

Quoted 8 lines

Quoted 6 lines

include/linux/rbtree_augmented.h __rb_erase_augmented(struct rb_node *node, struct rb_root *root, · line 206

Quoted 2 lines

include/linux/rbtree_augmented.h +0 -0

                pc = node->__rb_parent_color;
                tmp = __rb_parent(pc);

Note that node->rb_left was already fetched at the top of __rb_erase_augmented(), and was checked to be non-NULL at the time - otherwise we would have executed 'Case 1' in that function. So, you

If 'Case 1' is executed, this line of code is also done, how about the result? 'Case 1' seems *not* to change node->rb_left at all.

Wait, I believe this line of code is executed only in Case 2 and Case 3 ?

Quoted 24 lines

Quoted 24 lines

lib/rbtree.c ____rb_erase_color(struct rb_node *parent, struct rb_root *root, · line 220

Quoted 13 lines

lib/rbtree.c +1 -1

index c0e31fe..2cb01ba 100644
@@ -214,7 +214,7 @@ ____rb_erase_color(struct rb_node *parent, struct rb_root *root,
                 */
                sibling = parent->rb_right;
                if (node != sibling) {  /* node == parent->rb_left */
-                       if (rb_is_red(sibling)) {
+                       if (sibling && rb_is_red(sibling)) {
                                /*
                                 * Case 1 - left rotate at parent
                                 *

Note the loop invariants quoted just above:

/*
* Loop invariants:
* - node is black (or NULL on first iteration)
* - node is not the root (parent is not NULL)
* - All leaf paths going through parent and node have a
* black node count that is 1 lower than other leaf paths.
*/

Quoted 6 lines

Quoted 4 lines

Because of these, each path from sibling to a leaf must include at least one black node, which implies that sibling can't be NULL - or to put it another way, if sibling is null then the expected invariants were violated before we even got there.

In theory, i can understand what you mean, But don't know why and where it got violated.

Same here. My point is, I don't think we can fix the issue without answering that question.

Quoted 9 lines

Quoted 7 lines

Now I had a quick look at your code and I couldn't tell at which point the invariants are violated. However I did notice a couple suspicious things in the very first patch (f5c8f2b256d87ac0bf789a787e6b795ac0c736e8):

1- In both hot_range_tree_free() and and hot_tree_exit(), you try to destroy rb trees by iterating on each node with rb_next() and then

yes, but this item may not been freed immediately, You can know each item has its ref count.

Are items guaranteed to have another refcount than the one we're dropping ?

Quoted 4 lines

Quoted 2 lines

freeing them. Note that rb_next() can reference prior nodes, which have already been freed in your scheme, so that seems quite unsafe.

I checked rb_next() function, and found that if its prior nodes are freed, is this node's parent not NULL?

No, if the parent was freed with just a put() operation, the child will still have a pointer to it. This is why I suggested using rb_erase() on each node before freeing them, so that we don't keep pointers to freed nodes.

Quoted 4 lines

Quoted 1 line

The simplest fix would be to do a full rb_erase() on each node before

full rb_erase()? sorry, i don't get what you mean. Do you mean we should erase all nodes from rbtree, then begin to free them? If yes, how to iterate them? If no, can you elaborate it?

No, I meant to call rb_erase() on each individual node right before the corresponding put() operation.

Quoted 7 lines

Quoted 4 lines

2- I did not look long enough to understand the locking, but it wasn't clear to me if you lock the rbtrees when doing rb_erase() on them (while I could more clearly see that you do it for insertions).

Yes, it get locking when doing rb_erase() or rb_insert(). You can see there are multiple functions maybe rbtree at the same time. To sync them, we need to lock the rbtree.

Yes, agree we need to lock rbtree in all such operations. I just wasn't able to determine if it's done around rb_erase() calls, but it

definitely needs to be.

Quoted 6 lines

Quoted 5 lines

I'm really not sure if either of these will fix the issues you're seeing, though. What I would try next would be to add explicit rbtree invariant checks before and after rbtree manipulations, like what the check() function does in lib/rbtree_test.c, to see at which point do they get broken.

Great, any progress so far? :)

Unfortunately no.

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

Quoted 19 lines · Zhi Yong Wu

Quoted 11 lines · Michel Lespinasse

Quoted 7 lines · On Fri, Aug 23, 2013 at 7:45 AM, <[email protected]> wrote:

From: Zhi Yong Wu <[email protected]>

Signed-off-by Zhi Yong Wu <[email protected]>

---
 include/linux/rbtree_augmented.h | 3 ++-
 lib/rbtree.c                     | 5 +++--
 2 files changed, 5 insertions(+), 3 deletions(-)

So, you are saying that the checks are necessary, but you are not saying why.

Quoted 7 lines

The way I see it, the checks are *not* necessary, because the rbtree invariants guarantee them to be true. The only way for the checks to fail would be if people directly manipulate the rbtrees without going through the proper APIs, and if they do that then I think they're on their own. So to me, I think it's the same situation as dereferencing a pointer without checking if it's NULL, because you know it should never be NULL - which in my eyes is perfectly acceptable.

Quoted 5 lines

In my patchset, some rbtree APIs to be invoked, and I think that those rbtree APIs are used corrently, Below is the pointer of its code:
https://github.com/wuzhy/kernel/compare/torvalds:master...hot_tracking
But I hit some issues when using compilebench to do perf benchmark. compile dir kernel-7 691MB in 8.92 seconds (77.53 MB/s)

Thanks for the link - I now better understand where you are coming from with these fixes.

Going back to the original message:

Quoted 5 lines

include/linux/rbtree_augmented.h +0 -0

index fea49b5..7d19770 100644

include/linux/rbtree_augmented.h __rb_erase_augmented(struct rb_node *node, struct rb_root *root, · line 206

Quoted 9 lines

include/linux/rbtree_augmented.h +2 -1

@@ -199,7 +199,8 @@ __rb_erase_augmented(struct rb_node *node, struct rb_root *root,
                }
 
                successor->rb_left = tmp = node->rb_left;
-               rb_set_parent(tmp, successor);
+               if (tmp)
+                       rb_set_parent(tmp, successor);
 
                pc = node->__rb_parent_color;
                tmp = __rb_parent(pc);

Note that node->rb_left was already fetched at the top of __rb_erase_augmented(), and was checked to be non-NULL at the time - otherwise we would have executed 'Case 1' in that function. So, you are not expected to find tmp == NULL here.

lib/rbtree.c ____rb_erase_color(struct rb_node *parent, struct rb_root *root, · line 220

Quoted 13 lines

lib/rbtree.c +1 -1

index c0e31fe..2cb01ba 100644
@@ -214,7 +214,7 @@ ____rb_erase_color(struct rb_node *parent, struct rb_root *root,
                 */
                sibling = parent->rb_right;
                if (node != sibling) {  /* node == parent->rb_left */
-                       if (rb_is_red(sibling)) {
+                       if (sibling && rb_is_red(sibling)) {
                                /*
                                 * Case 1 - left rotate at parent
                                 *

Note the loop invariants quoted just above:

/*
* Loop invariants:
* - node is black (or NULL on first iteration)
* - node is not the root (parent is not NULL)
* - All leaf paths going through parent and node have a
* black node count that is 1 lower than other leaf paths.
*/

Because of these, each path from sibling to a leaf must include at least one black node, which implies that sibling can't be NULL - or to put it another way, if sibling is null then the expected invariants were violated before we even got there.

lib/rbtree.c ____rb_erase_color(struct rb_node *parent, struct rb_root *root, · line 233

Quoted 10 lines

lib/rbtree.c +2 -1

@@ -226,7 +226,8 @@ ____rb_erase_color(struct rb_node *parent, struct rb_root *root,
                                 */
                                parent->rb_right = tmp1 = sibling->rb_left;
                                sibling->rb_left = parent;
-                               rb_set_parent_color(tmp1, parent, RB_BLACK);
+                               if (tmp1)
+                                       rb_set_parent_color(tmp1, parent, RB_BLACK);
                                __rb_rotate_set_parents(parent, sibling, root,
                                                        RB_RED);
                                augment_rotate(parent, sibling);

This is actually the same invariant here - each path from sibling to a leaf must include at least one black node, and sibling is now known to be red, so it must have two black children.

Now I had a quick look at your code and I couldn't tell at which point the invariants are violated. However I did notice a couple suspicious things in the very first patch (f5c8f2b256d87ac0bf789a787e6b795ac0c736e8):

1- In both hot_range_tree_free() and and hot_tree_exit(), you try to destroy rb trees by iterating on each node with rb_next() and then freeing them. Note that rb_next() can reference prior nodes, which have already been freed in your scheme, so that seems quite unsafe.

The simplest fix would be to do a full rb_erase() on each node before freeing it. (you may be able to avoid rebalancing the tree here as you're going to destroy it all, but if you really have that need it would be better to come up with a new API to cover it rather than hardcode it where you need it - I think it's easiest to start with the simple dumb fix of using rb_erase).

2- I did not look long enough to understand the locking, but it wasn't clear to me if you lock the rbtrees when doing rb_erase() on them (while I could more clearly see that you do it for insertions).

I'm really not sure if either of these will fix the issues you're seeing, though. What I would try next would be to add explicit rbtree invariant checks before and after rbtree manipulations, like what the check() function does in lib/rbtree_test.c, to see at which point do they get broken.

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

Quoted 80 lines · Michel Lespinasse

Quoted 19 lines · Zhi Yong Wu

Quoted 11 lines · Michel Lespinasse

Quoted 7 lines · On Fri, Aug 23, 2013 at 7:45 AM, <[email protected]> wrote:

From: Zhi Yong Wu <[email protected]>

Signed-off-by Zhi Yong Wu <[email protected]>

---
 include/linux/rbtree_augmented.h | 3 ++-
 lib/rbtree.c                     | 5 +++--
 2 files changed, 5 insertions(+), 3 deletions(-)

So, you are saying that the checks are necessary, but you are not saying why.

Quoted 7 lines

The way I see it, the checks are *not* necessary, because the rbtree invariants guarantee them to be true. The only way for the checks to fail would be if people directly manipulate the rbtrees without going through the proper APIs, and if they do that then I think they're on their own. So to me, I think it's the same situation as dereferencing a pointer without checking if it's NULL, because you know it should never be NULL - which in my eyes is perfectly acceptable.

Quoted 5 lines

In my patchset, some rbtree APIs to be invoked, and I think that those rbtree APIs are used corrently, Below is the pointer of its code:
https://github.com/wuzhy/kernel/compare/torvalds:master...hot_tracking
But I hit some issues when using compilebench to do perf benchmark. compile dir kernel-7 691MB in 8.92 seconds (77.53 MB/s)

Thanks for the link - I now better understand where you are coming from with these fixes.

Going back to the original message:

Quoted 5 lines

include/linux/rbtree_augmented.h +0 -0

index fea49b5..7d19770 100644

include/linux/rbtree_augmented.h __rb_erase_augmented(struct rb_node *node, struct rb_root *root, · line 206

Quoted 9 lines

include/linux/rbtree_augmented.h +2 -1

@@ -199,7 +199,8 @@ __rb_erase_augmented(struct rb_node *node, struct rb_root *root,
                }
 
                successor->rb_left = tmp = node->rb_left;
-               rb_set_parent(tmp, successor);
+               if (tmp)
+                       rb_set_parent(tmp, successor);
 
                pc = node->__rb_parent_color;
                tmp = __rb_parent(pc);

Note that node->rb_left was already fetched at the top of __rb_erase_augmented(), and was checked to be non-NULL at the time - otherwise we would have executed 'Case 1' in that function. So, you are not expected to find tmp == NULL here.

lib/rbtree.c ____rb_erase_color(struct rb_node *parent, struct rb_root *root, · line 220

Quoted 13 lines

lib/rbtree.c +1 -1

index c0e31fe..2cb01ba 100644
@@ -214,7 +214,7 @@ ____rb_erase_color(struct rb_node *parent, struct rb_root *root,
                 */
                sibling = parent->rb_right;
                if (node != sibling) {  /* node == parent->rb_left */
-                       if (rb_is_red(sibling)) {
+                       if (sibling && rb_is_red(sibling)) {
                                /*
                                 * Case 1 - left rotate at parent
                                 *

Note the loop invariants quoted just above:

/*
* Loop invariants:
* - node is black (or NULL on first iteration)
* - node is not the root (parent is not NULL)
* - All leaf paths going through parent and node have a
* black node count that is 1 lower than other leaf paths.
*/

Because of these, each path from sibling to a leaf must include at least one black node, which implies that sibling can't be NULL - or to put it another way, if sibling is null then the expected invariants were violated before we even got there.

Quoted 14 lines

lib/rbtree.c ____rb_erase_color(struct rb_node *parent, struct rb_root *root, · line 233

Quoted 10 lines

lib/rbtree.c +2 -1

@@ -226,7 +226,8 @@ ____rb_erase_color(struct rb_node *parent, struct rb_root *root,
                                 */
                                parent->rb_right = tmp1 = sibling->rb_left;
                                sibling->rb_left = parent;
-                               rb_set_parent_color(tmp1, parent, RB_BLACK);
+                               if (tmp1)
+                                       rb_set_parent_color(tmp1, parent, RB_BLACK);
                                __rb_rotate_set_parents(parent, sibling, root,
                                                        RB_RED);
                                augment_rotate(parent, sibling);

This is actually the same invariant here - each path from sibling to a leaf must include at least one black node, and sibling is now known to be red, so it must have two black children.

If sibling is red, it can be made sure to have two non-null black children?

but my patchset sometimes trigger red sibling to have no non-null black children. Do you know what reason usually cause this? You know rbtree code is very tricky.

Quoted 33 lines

Now I had a quick look at your code and I couldn't tell at which point the invariants are violated. However I did notice a couple suspicious things in the very first patch (f5c8f2b256d87ac0bf789a787e6b795ac0c736e8):

1- In both hot_range_tree_free() and and hot_tree_exit(), you try to destroy rb trees by iterating on each node with rb_next() and then freeing them. Note that rb_next() can reference prior nodes, which have already been freed in your scheme, so that seems quite unsafe.

The simplest fix would be to do a full rb_erase() on each node before freeing it. (you may be able to avoid rebalancing the tree here as you're going to destroy it all, but if you really have that need it would be better to come up with a new API to cover it rather than hardcode it where you need it - I think it's easiest to start with the simple dumb fix of using rb_erase).

2- I did not look long enough to understand the locking, but it wasn't clear to me if you lock the rbtrees when doing rb_erase() on them (while I could more clearly see that you do it for insertions).

I'm really not sure if either of these will fix the issues you're seeing, though. What I would try next would be to add explicit rbtree invariant checks before and after rbtree manipulations, like what the check() function does in lib/rbtree_test.c, to see at which point do they get broken.

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

Quoted 95 lines · Zhi Yong Wu

Quoted 94 lines · Michel Lespinasse

Quoted 19 lines · Zhi Yong Wu

Quoted 11 lines · Michel Lespinasse

Quoted 7 lines · On Fri, Aug 23, 2013 at 7:45 AM, <[email protected]> wrote:

From: Zhi Yong Wu <[email protected]>

Signed-off-by Zhi Yong Wu <[email protected]>

---
 include/linux/rbtree_augmented.h | 3 ++-
 lib/rbtree.c                     | 5 +++--
 2 files changed, 5 insertions(+), 3 deletions(-)

So, you are saying that the checks are necessary, but you are not saying why.

Quoted 7 lines

The way I see it, the checks are *not* necessary, because the rbtree invariants guarantee them to be true. The only way for the checks to fail would be if people directly manipulate the rbtrees without going through the proper APIs, and if they do that then I think they're on their own. So to me, I think it's the same situation as dereferencing a pointer without checking if it's NULL, because you know it should never be NULL - which in my eyes is perfectly acceptable.

Quoted 5 lines

In my patchset, some rbtree APIs to be invoked, and I think that those rbtree APIs are used corrently, Below is the pointer of its code:
https://github.com/wuzhy/kernel/compare/torvalds:master...hot_tracking
But I hit some issues when using compilebench to do perf benchmark. compile dir kernel-7 691MB in 8.92 seconds (77.53 MB/s)

Thanks for the link - I now better understand where you are coming from with these fixes.

Going back to the original message:

Quoted 5 lines

include/linux/rbtree_augmented.h +0 -0

index fea49b5..7d19770 100644

include/linux/rbtree_augmented.h __rb_erase_augmented(struct rb_node *node, struct rb_root *root, · line 206

Quoted 9 lines

include/linux/rbtree_augmented.h +2 -1

@@ -199,7 +199,8 @@ __rb_erase_augmented(struct rb_node *node, struct rb_root *root,
                }
 
                successor->rb_left = tmp = node->rb_left;
-               rb_set_parent(tmp, successor);
+               if (tmp)
+                       rb_set_parent(tmp, successor);
 
                pc = node->__rb_parent_color;
                tmp = __rb_parent(pc);

Note that node->rb_left was already fetched at the top of __rb_erase_augmented(), and was checked to be non-NULL at the time - otherwise we would have executed 'Case 1' in that function. So, you are not expected to find tmp == NULL here.

lib/rbtree.c ____rb_erase_color(struct rb_node *parent, struct rb_root *root, · line 220

Quoted 13 lines

lib/rbtree.c +1 -1

index c0e31fe..2cb01ba 100644
@@ -214,7 +214,7 @@ ____rb_erase_color(struct rb_node *parent, struct rb_root *root,
                 */
                sibling = parent->rb_right;
                if (node != sibling) {  /* node == parent->rb_left */
-                       if (rb_is_red(sibling)) {
+                       if (sibling && rb_is_red(sibling)) {
                                /*
                                 * Case 1 - left rotate at parent
                                 *

Note the loop invariants quoted just above:

/*
* Loop invariants:
* - node is black (or NULL on first iteration)
* - node is not the root (parent is not NULL)
* - All leaf paths going through parent and node have a
* black node count that is 1 lower than other leaf paths.
*/

Because of these, each path from sibling to a leaf must include at least one black node, which implies that sibling can't be NULL - or to put it another way, if sibling is null then the expected invariants were violated before we even got there.

lib/rbtree.c ____rb_erase_color(struct rb_node *parent, struct rb_root *root, · line 233

Quoted 10 lines

lib/rbtree.c +2 -1

@@ -226,7 +226,8 @@ ____rb_erase_color(struct rb_node *parent, struct rb_root *root,
                                 */
                                parent->rb_right = tmp1 = sibling->rb_left;
                                sibling->rb_left = parent;
-                               rb_set_parent_color(tmp1, parent, RB_BLACK);
+                               if (tmp1)
+                                       rb_set_parent_color(tmp1, parent, RB_BLACK);
                                __rb_rotate_set_parents(parent, sibling, root,
                                                        RB_RED);
                                augment_rotate(parent, sibling);

This is actually the same invariant here - each path from sibling to a leaf must include at least one black node, and sibling is now known to be red, so it must have two black children.

Quoted 2 lines

If sibling is red, it can be made sure to have two non-null black children?

This is guaranteed by cases 1 and 2 in __rb_insert().

Quoted 4 lines

but my patchset sometimes trigger red sibling to have no non-null black children. Do you know what reason usually cause this? You know rbtree code is very tricky.

I haven't looked at your code, but a good way of verifying the tree integrity is running rbtree_test.

Thanks,
Davidlohr

Quoted 36 lines

Quoted 33 lines

Now I had a quick look at your code and I couldn't tell at which point the invariants are violated. However I did notice a couple suspicious things in the very first patch (f5c8f2b256d87ac0bf789a787e6b795ac0c736e8):

1- In both hot_range_tree_free() and and hot_tree_exit(), you try to destroy rb trees by iterating on each node with rb_next() and then freeing them. Note that rb_next() can reference prior nodes, which have already been freed in your scheme, so that seems quite unsafe.

The simplest fix would be to do a full rb_erase() on each node before freeing it. (you may be able to avoid rebalancing the tree here as you're going to destroy it all, but if you really have that need it would be better to come up with a new API to cover it rather than hardcode it where you need it - I think it's easiest to start with the simple dumb fix of using rb_erase).

2- I did not look long enough to understand the locking, but it wasn't clear to me if you lock the rbtrees when doing rb_erase() on them (while I could more clearly see that you do it for insertions).

I'm really not sure if either of these will fix the issues you're seeing, though. What I would try next would be to add explicit rbtree invariant checks before and after rbtree manipulations, like what the check() function does in lib/rbtree_test.c, to see at which point do they get broken.

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

Quoted 96 lines · Davidlohr Bueso

Quoted 95 lines · Zhi Yong Wu

Quoted 94 lines · Michel Lespinasse

Quoted 19 lines · Zhi Yong Wu

Quoted 11 lines · Michel Lespinasse

Quoted 7 lines · On Fri, Aug 23, 2013 at 7:45 AM, <[email protected]> wrote:

From: Zhi Yong Wu <[email protected]>

Signed-off-by Zhi Yong Wu <[email protected]>

---
 include/linux/rbtree_augmented.h | 3 ++-
 lib/rbtree.c                     | 5 +++--
 2 files changed, 5 insertions(+), 3 deletions(-)

So, you are saying that the checks are necessary, but you are not saying why.

Quoted 7 lines

The way I see it, the checks are *not* necessary, because the rbtree invariants guarantee them to be true. The only way for the checks to fail would be if people directly manipulate the rbtrees without going through the proper APIs, and if they do that then I think they're on their own. So to me, I think it's the same situation as dereferencing a pointer without checking if it's NULL, because you know it should never be NULL - which in my eyes is perfectly acceptable.

Quoted 5 lines

In my patchset, some rbtree APIs to be invoked, and I think that those rbtree APIs are used corrently, Below is the pointer of its code:
https://github.com/wuzhy/kernel/compare/torvalds:master...hot_tracking
But I hit some issues when using compilebench to do perf benchmark. compile dir kernel-7 691MB in 8.92 seconds (77.53 MB/s)

Thanks for the link - I now better understand where you are coming from with these fixes.

Going back to the original message:

Quoted 5 lines

include/linux/rbtree_augmented.h +0 -0

index fea49b5..7d19770 100644

include/linux/rbtree_augmented.h __rb_erase_augmented(struct rb_node *node, struct rb_root *root, · line 206

Quoted 9 lines

include/linux/rbtree_augmented.h +2 -1

@@ -199,7 +199,8 @@ __rb_erase_augmented(struct rb_node *node, struct rb_root *root,
                }
 
                successor->rb_left = tmp = node->rb_left;
-               rb_set_parent(tmp, successor);
+               if (tmp)
+                       rb_set_parent(tmp, successor);
 
                pc = node->__rb_parent_color;
                tmp = __rb_parent(pc);

Note that node->rb_left was already fetched at the top of __rb_erase_augmented(), and was checked to be non-NULL at the time - otherwise we would have executed 'Case 1' in that function. So, you are not expected to find tmp == NULL here.

lib/rbtree.c ____rb_erase_color(struct rb_node *parent, struct rb_root *root, · line 220

Quoted 13 lines

lib/rbtree.c +1 -1

index c0e31fe..2cb01ba 100644
@@ -214,7 +214,7 @@ ____rb_erase_color(struct rb_node *parent, struct rb_root *root,
                 */
                sibling = parent->rb_right;
                if (node != sibling) {  /* node == parent->rb_left */
-                       if (rb_is_red(sibling)) {
+                       if (sibling && rb_is_red(sibling)) {
                                /*
                                 * Case 1 - left rotate at parent
                                 *

Note the loop invariants quoted just above:

/*
* Loop invariants:
* - node is black (or NULL on first iteration)
* - node is not the root (parent is not NULL)
* - All leaf paths going through parent and node have a
* black node count that is 1 lower than other leaf paths.
*/

Because of these, each path from sibling to a leaf must include at least one black node, which implies that sibling can't be NULL - or to put it another way, if sibling is null then the expected invariants were violated before we even got there.

lib/rbtree.c ____rb_erase_color(struct rb_node *parent, struct rb_root *root, · line 233

Quoted 10 lines

lib/rbtree.c +2 -1

@@ -226,7 +226,8 @@ ____rb_erase_color(struct rb_node *parent, struct rb_root *root,
                                 */
                                parent->rb_right = tmp1 = sibling->rb_left;
                                sibling->rb_left = parent;
-                               rb_set_parent_color(tmp1, parent, RB_BLACK);
+                               if (tmp1)
+                                       rb_set_parent_color(tmp1, parent, RB_BLACK);
                                __rb_rotate_set_parents(parent, sibling, root,
                                                        RB_RED);
                                augment_rotate(parent, sibling);

This is actually the same invariant here - each path from sibling to a leaf must include at least one black node, and sibling is now known to be red, so it must have two black children.

Quoted 4 lines

Quoted 2 lines

If sibling is red, it can be made sure to have two non-null black children?

This is guaranteed by cases 1 and 2 in __rb_insert().

ah, but this code is very tricky.

Quoted 7 lines

Quoted 4 lines

but my patchset sometimes trigger red sibling to have no non-null black children. Do you know what reason usually cause this? You know rbtree code is very tricky.

I haven't looked at your code, but a good way of verifying the tree integrity is running rbtree_test.

rbtree_test seem to be not available for my patchset.

my perf testing
is super large scale, and it will try to create 1,0000,000 rb_nodes, while rbtree_test try to verify the rbtree when every rb_node is reserted or erased. This will cause my perf testing to be running very very slowly.

Quoted 97 lines · Zhi Yong Wu

Quoted 96 lines · Davidlohr Bueso

Quoted 95 lines · Zhi Yong Wu

Quoted 94 lines · Michel Lespinasse

Quoted 19 lines · Zhi Yong Wu

Quoted 11 lines · Michel Lespinasse

Quoted 7 lines · On Fri, Aug 23, 2013 at 7:45 AM, <[email protected]> wrote:

From: Zhi Yong Wu <[email protected]>

Signed-off-by Zhi Yong Wu <[email protected]>

---
 include/linux/rbtree_augmented.h | 3 ++-
 lib/rbtree.c                     | 5 +++--
 2 files changed, 5 insertions(+), 3 deletions(-)

So, you are saying that the checks are necessary, but you are not saying why.

Quoted 7 lines

The way I see it, the checks are *not* necessary, because the rbtree invariants guarantee them to be true. The only way for the checks to fail would be if people directly manipulate the rbtrees without going through the proper APIs, and if they do that then I think they're on their own. So to me, I think it's the same situation as dereferencing a pointer without checking if it's NULL, because you know it should never be NULL - which in my eyes is perfectly acceptable.

Quoted 5 lines

In my patchset, some rbtree APIs to be invoked, and I think that those rbtree APIs are used corrently, Below is the pointer of its code:
https://github.com/wuzhy/kernel/compare/torvalds:master...hot_tracking
But I hit some issues when using compilebench to do perf benchmark. compile dir kernel-7 691MB in 8.92 seconds (77.53 MB/s)

Thanks for the link - I now better understand where you are coming from with these fixes.

Going back to the original message:

Quoted 5 lines

include/linux/rbtree_augmented.h +0 -0

index fea49b5..7d19770 100644

include/linux/rbtree_augmented.h __rb_erase_augmented(struct rb_node *node, struct rb_root *root, · line 206

Quoted 9 lines

include/linux/rbtree_augmented.h +2 -1

@@ -199,7 +199,8 @@ __rb_erase_augmented(struct rb_node *node, struct rb_root *root,
                }
 
                successor->rb_left = tmp = node->rb_left;
-               rb_set_parent(tmp, successor);
+               if (tmp)
+                       rb_set_parent(tmp, successor);
 
                pc = node->__rb_parent_color;
                tmp = __rb_parent(pc);

Note that node->rb_left was already fetched at the top of __rb_erase_augmented(), and was checked to be non-NULL at the time - otherwise we would have executed 'Case 1' in that function. So, you are not expected to find tmp == NULL here.

lib/rbtree.c ____rb_erase_color(struct rb_node *parent, struct rb_root *root, · line 220

Quoted 13 lines

lib/rbtree.c +1 -1

index c0e31fe..2cb01ba 100644
@@ -214,7 +214,7 @@ ____rb_erase_color(struct rb_node *parent, struct rb_root *root,
                 */
                sibling = parent->rb_right;
                if (node != sibling) {  /* node == parent->rb_left */
-                       if (rb_is_red(sibling)) {
+                       if (sibling && rb_is_red(sibling)) {
                                /*
                                 * Case 1 - left rotate at parent
                                 *

Note the loop invariants quoted just above:

/*
* Loop invariants:
* - node is black (or NULL on first iteration)
* - node is not the root (parent is not NULL)
* - All leaf paths going through parent and node have a
* black node count that is 1 lower than other leaf paths.
*/

Because of these, each path from sibling to a leaf must include at least one black node, which implies that sibling can't be NULL - or to put it another way, if sibling is null then the expected invariants were violated before we even got there.

lib/rbtree.c ____rb_erase_color(struct rb_node *parent, struct rb_root *root, · line 233

Quoted 10 lines

lib/rbtree.c +2 -1

@@ -226,7 +226,8 @@ ____rb_erase_color(struct rb_node *parent, struct rb_root *root,
                                 */
                                parent->rb_right = tmp1 = sibling->rb_left;
                                sibling->rb_left = parent;
-                               rb_set_parent_color(tmp1, parent, RB_BLACK);
+                               if (tmp1)
+                                       rb_set_parent_color(tmp1, parent, RB_BLACK);
                                __rb_rotate_set_parents(parent, sibling, root,
                                                        RB_RED);
                                augment_rotate(parent, sibling);

This is actually the same invariant here - each path from sibling to a leaf must include at least one black node, and sibling is now known to be red, so it must have two black children.

Quoted 6 lines

Quoted 4 lines

Quoted 2 lines

If sibling is red, it can be made sure to have two non-null black children?

This is guaranteed by cases 1 and 2 in __rb_insert().

ah, but this code is very tricky.

While it's not trivial, it is a lot more readable than a whole bunch of red-black tree implementations out there - not to mention optimized.

AFAICT by the thread, you have yet to provide a case where, by properly using the rbtree API, the tree implementation does not comply.

Quoted 5 lines

Quoted 5 lines

Quoted 4 lines

but my patchset sometimes trigger red sibling to have no non-null black children. Do you know what reason usually cause this? You know rbtree code is very tricky.

Quoted 3 lines

Quoted 2 lines

I haven't looked at your code, but a good way of verifying the tree integrity is running rbtree_test.

rbtree_test seem to be not available for my patchset.

Why not? Is this an older kernel you're dealing with?

Quoted 7 lines

my perf testing
is super large scale, and it will try to create 1,0000,000 rb_nodes, while rbtree_test try to verify the rbtree when every rb_node is reserted or erased. This will cause my perf testing to be running very very slowly.

May I ask what you are attempting to do here? Are you trying to stress

the kernel's rbtree implementation?

Well, performance isn't a concern when doing this kind of testing. Yes, the tree integrity verification (check() calls) is done when inserting and deleting every node, which is the whole purpose of such tests. I admit that the rbtree_test module is a bit limited as to user options -
ie: making the amount of nodes be a parameter is on my todo list. That said, the check() function does properly test the rbtree properties, and so far it complies.

Thanks,
Davidlohr