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@xxxxxxxxxxxxxxxxxxxx> 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.
--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@xxxxxxxxxxxxxxx
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/