[PATCH 1/2] btree: Fix tree corruption in btree_get_prev()

[PATCH 1/2] btree: Fix tree corruption in btree_get_prev()

[Roland Dreier]

From: Roland Dreier <roland@purestorage.com>

The memory the parameter __key points to is used as an iterator in
btree_get_prev(), so if we save off a bkey() pointer in retry_key and
then assign that to __key, we'll end up corrupting the btree internals
when we do eg

	longcpy(__key, bkey(geo, node, i), geo->keylen);

to return the key value.  What we should do instead is use longcpy() to
copy the key value that retry_key points to __key.

This can cause a btree to get corrupted by seemingly read-only
operations such as btree_for_each_safe.

Acked-by: Joern Engel <joern@logfs.org>
Cc: <stable@vger.kernel.org>
Signed-off-by: Roland Dreier <roland@purestorage.com>
---
 lib/btree.c |    2 +-
 1 file changed, 1 insertion(+), 1 deletion(-)

diff --git a/lib/btree.c b/lib/btree.c
index e5ec1e9..b6e889b 100644
--- a/lib/btree.c
+++ b/lib/btree.c
@@ -351,7 +351,7 @@ retry:
 	}
 miss:
 	if (retry_key) {
-		__key = retry_key;
+		longcpy(__key, retry_key, geo->keylen);
 		retry_key = NULL;
 		goto retry;
 	}
-- 
1.7.9.5

[PATCH 2/2] btree: Catch NULL value before it does harm

[Roland Dreier]

From: Joern Engel <joern@logfs.org>

Storing NULL values in the btree is illegal and can lead to memory
corruption and possible other fun as well.  Catch it on insert, instead
of waiting for the inevitable.

Signed-off-by: Joern Engel <joern@logfs.org>
Signed-off-by: Roland Dreier <roland@purestorage.com>
---
 lib/btree.c |    1 +
 1 file changed, 1 insertion(+)

diff --git a/lib/btree.c b/lib/btree.c
index b6e889b..bd6d4b4 100644
--- a/lib/btree.c
+++ b/lib/btree.c
@@ -509,6 +509,7 @@ retry:
 int btree_insert(struct btree_head *head, struct btree_geo *geo,
 		unsigned long *key, void *val, gfp_t gfp)
 {
+	BUG_ON(!val);
 	return btree_insert_level(head, geo, key, val, 1, gfp);
 }
 EXPORT_SYMBOL_GPL(btree_insert);
-- 
1.7.9.5

Re: [PATCH 1/2] btree: Fix tree corruption in btree_get_prev()

[Andrew Morton]

On Wed,  6 Jun 2012 10:17:26 -0700
Roland Dreier <roland@kernel.org> wrote:

> From: Roland Dreier <roland@purestorage.com>
> 
> The memory the parameter __key points to is used as an iterator in
> btree_get_prev(), so if we save off a bkey() pointer in retry_key and
> then assign that to __key, we'll end up corrupting the btree internals
> when we do eg
> 
> 	longcpy(__key, bkey(geo, node, i), geo->keylen);
> 
> to return the key value.  What we should do instead is use longcpy() to
> copy the key value that retry_key points to __key.
> 
> This can cause a btree to get corrupted by seemingly read-only
> operations such as btree_for_each_safe.
> 
> Acked-by: Joern Engel <joern@logfs.org>
> Cc: <stable@vger.kernel.org>
> Signed-off-by: Roland Dreier <roland@purestorage.com>
> ---
>  lib/btree.c |    2 +-
>  1 file changed, 1 insertion(+), 1 deletion(-)
> 
> diff --git a/lib/btree.c b/lib/btree.c
> index e5ec1e9..b6e889b 100644
> --- a/lib/btree.c
> +++ b/lib/btree.c
> @@ -351,7 +351,7 @@ retry:
>  	}
>  miss:
>  	if (retry_key) {
> -		__key = retry_key;
> +		longcpy(__key, retry_key, geo->keylen);
>  		retry_key = NULL;
>  		goto retry;
>  	}

Fair enough.

I think we can do this to save a few cycles?

--- a/lib/btree.c~btree-fix-tree-corruption-in-btree_get_prev-fix
+++ a/lib/btree.c
@@ -319,8 +319,8 @@ void *btree_get_prev(struct btree_head *
 
 	if (head->height == 0)
 		return NULL;
-retry:
 	longcpy(key, __key, geo->keylen);
+retry:
 	dec_key(geo, key);
 
 	node = head->node;
@@ -351,7 +351,7 @@ retry:
 	}
 miss:
 	if (retry_key) {
-		longcpy(__key, retry_key, geo->keylen);
+		longcpy(key, retry_key, geo->keylen);
 		retry_key = NULL;
 		goto retry;
 	}
_

Re: [PATCH 1/2] btree: Fix tree corruption in btree_get_prev()

[Roland Dreier]

On Wed, Jun 6, 2012 at 4:21 PM, Andrew Morton <akpm@linux-foundation.org> wrote:
> I think we can do this to save a few cycles?
>
> --- a/lib/btree.c~btree-fix-tree-corruption-in-btree_get_prev-fix
> +++ a/lib/btree.c
> @@ -319,8 +319,8 @@ void *btree_get_prev(struct btree_head *
>
>        if (head->height == 0)
>                return NULL;
> -retry:
>        longcpy(key, __key, geo->keylen);
> +retry:
>        dec_key(geo, key);
>
>        node = head->node;
> @@ -351,7 +351,7 @@ retry:
>        }
>  miss:
>        if (retry_key) {
> -               longcpy(__key, retry_key, geo->keylen);
> +               longcpy(key, retry_key, geo->keylen);
>                retry_key = NULL;
>                goto retry;
>        }

Looks reasonable to me, and passes my hacky userspace
test harness.

On the other hand, your change makes me think we don't
even need a separate iterator (and we can avoid the variable
length array declaration), ie we could do

--- a/lib/btree.c
+++ b/lib/btree.c
@@ -312,7 +312,7 @@ void *btree_get_prev(struct btree_head *head,
struct btree_geo *geo,
 {
 	int i, height;
 	unsigned long *node, *oldnode;
-	unsigned long *retry_key = NULL, key[geo->keylen];
+	unsigned long *retry_key = NULL;

 	if (keyzero(geo, __key))
 		return NULL;
@@ -320,13 +320,12 @@ void *btree_get_prev(struct btree_head *head,
struct btree_geo *geo,
 	if (head->height == 0)
 		return NULL;
 retry:
-	longcpy(key, __key, geo->keylen);
-	dec_key(geo, key);
+	dec_key(geo, __key);

 	node = head->node;
 	for (height = head->height ; height > 1; height--) {
 		for (i = 0; i < geo->no_pairs; i++)
-			if (keycmp(geo, node, i, key) <= 0)
+			if (keycmp(geo, node, i, __key) <= 0)
 				break;
 		if (i == geo->no_pairs)
 			goto miss;
@@ -341,7 +340,7 @@ retry:
 		goto miss;

 	for (i = 0; i < geo->no_pairs; i++) {
-		if (keycmp(geo, node, i, key) <= 0) {
+		if (keycmp(geo, node, i, __key) <= 0) {
 			if (bval(geo, node, i)) {
 				longcpy(__key, bkey(geo, node, i), geo->keylen);
 				return bval(geo, node, i);

but this means even if we fail and return NULL we mess with the
caller's __key.  So your way may be better.

Joern?

 - R.

Re: [PATCH 1/2] btree: Fix tree corruption in btree_get_prev()

[Roland Dreier]

On Wed, Jun 6, 2012 at 4:36 PM, Roland Dreier <roland@kernel.org> wrote:
> On the other hand, your change makes me think we don't
> even need a separate iterator (and we can avoid the variable
> length array declaration)

FWIW with that change on top of my patch, I see

add/remove: 0/0 grow/shrink: 0/1 up/down: 0/-123 (-123)
function                                     old     new   delta
btree_get_prev                               646     523    -123

on x86-64, so avoiding the variable length array is definitely
worth something.

So the issue for me is whether messing with the caller's
__key storage is OK, or if it's worth having a temporary
local variable.

 - R.

Re: [PATCH 1/2] btree: Fix tree corruption in btree_get_prev()

[Andrew Morton]

On Wed, 6 Jun 2012 17:44:20 -0700 Roland Dreier <roland@kernel.org> wrote:

> On Wed, Jun 6, 2012 at 4:36 PM, Roland Dreier <roland@kernel.org> wrote:
> > On the other hand, your change makes me think we don't
> > even need a separate iterator (and we can avoid the variable
> > length array declaration)
> 
> FWIW with that change on top of my patch, I see
> 
> add/remove: 0/0 grow/shrink: 0/1 up/down: 0/-123 (-123)
> function                                     old     new   delta
> btree_get_prev                               646     523    -123
> 
> on x86-64, so avoiding the variable length array is definitely
> worth something.
> 
> So the issue for me is whether messing with the caller's
> __key storage is OK, or if it's worth having a temporary
> local variable.
> 

Sometimes altering the caller's *__key when lookup fails is pretty rude
behavior :(

Perhaps we could add an arg to btree_get_prev(), provide it with
separate input and output key pointers?