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

From: Roland Dreier
Date: Wed Jun 06 2012 - 19:36:25 EST


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/