dm btree: fix serious bug in btree_split_beneath()

[pandora-kernel.git] / drivers / md / persistent-data / dm-btree.c

diff --git a/drivers/md/persistent-data/dm-btree.c b/drivers/md/persistent-data/dm-btree.c
index bd1e7ff..008231f 100644 (file)
--- a/drivers/md/persistent-data/dm-btree.c
+++ b/drivers/md/persistent-data/dm-btree.c
@@ -38,7 +38,7 @@ static void array_insert(void *base, size_t elt_size, unsigned nr_elts,
 /*----------------------------------------------------------------*/
 
 /* makes the assumption that no two keys are the same. */
-static int bsearch(struct node *n, uint64_t key, int want_hi)
+static int bsearch(struct btree_node *n, uint64_t key, int want_hi)
 {
        int lo = -1, hi = le32_to_cpu(n->header.nr_entries);
 
@@ -58,12 +58,12 @@ static int bsearch(struct node *n, uint64_t key, int want_hi)
        return want_hi ? hi : lo;
 }
 
-int lower_bound(struct node *n, uint64_t key)
+int lower_bound(struct btree_node *n, uint64_t key)
 {
        return bsearch(n, key, 0);
 }
 
-void inc_children(struct dm_transaction_manager *tm, struct node *n,
+void inc_children(struct dm_transaction_manager *tm, struct btree_node *n,
                  struct dm_btree_value_type *vt)
 {
        unsigned i;
@@ -78,7 +78,7 @@ void inc_children(struct dm_transaction_manager *tm, struct node *n,
                                value_ptr(n, i, vt->size));
 }
 
-static int insert_at(size_t value_size, struct node *node, unsigned index,
+static int insert_at(size_t value_size, struct btree_node *node, unsigned index,
                      uint64_t key, void *value)
                      __dm_written_to_disk(value)
 {
@@ -123,7 +123,7 @@ int dm_btree_empty(struct dm_btree_info *info, dm_block_t *root)
 {
        int r;
        struct dm_block *b;
-       struct node *n;
+       struct btree_node *n;
        size_t block_size;
        uint32_t max_entries;
 
@@ -155,7 +155,7 @@ EXPORT_SYMBOL_GPL(dm_btree_empty);
 #define MAX_SPINE_DEPTH 64
 struct frame {
        struct dm_block *b;
-       struct node *n;
+       struct btree_node *n;
        unsigned level;
        unsigned nr_children;
        unsigned current_child;
@@ -231,12 +231,22 @@ static void pop_frame(struct del_stack *s)
        dm_tm_unlock(s->tm, f->b);
 }
 
+static void unlock_all_frames(struct del_stack *s)
+{
+       struct frame *f;
+
+       while (unprocessed_frames(s)) {
+               f = s->spine + s->top--;
+               dm_tm_unlock(s->tm, f->b);
+       }
+}
+
 int dm_btree_del(struct dm_btree_info *info, dm_block_t root)
 {
        int r;
        struct del_stack *s;
 
-       s = kmalloc(sizeof(*s), GFP_KERNEL);
+       s = kmalloc(sizeof(*s), GFP_NOIO);
        if (!s)
                return -ENOMEM;
        s->tm = info->tm;
@@ -286,9 +296,13 @@ int dm_btree_del(struct dm_btree_info *info, dm_block_t root)
                        f->current_child = f->nr_children;
                }
        }
-
 out:
+       if (r) {
+               /* cleanup all frames of del_stack */
+               unlock_all_frames(s);
+       }
        kfree(s);
+
        return r;
 }
 EXPORT_SYMBOL_GPL(dm_btree_del);
@@ -296,7 +310,7 @@ EXPORT_SYMBOL_GPL(dm_btree_del);
 /*----------------------------------------------------------------*/
 
 static int btree_lookup_raw(struct ro_spine *s, dm_block_t block, uint64_t key,
-                           int (*search_fn)(struct node *, uint64_t),
+                           int (*search_fn)(struct btree_node *, uint64_t),
                            uint64_t *result_key, void *v, size_t value_size)
 {
        int i, r;
@@ -407,7 +421,7 @@ static int btree_split_sibling(struct shadow_spine *s, dm_block_t root,
        size_t size;
        unsigned nr_left, nr_right;
        struct dm_block *left, *right, *parent;
-       struct node *ln, *rn, *pn;
+       struct btree_node *ln, *rn, *pn;
        __le64 location;
 
        left = shadow_current(s);
@@ -451,8 +465,10 @@ static int btree_split_sibling(struct shadow_spine *s, dm_block_t root,
 
        r = insert_at(sizeof(__le64), pn, parent_index + 1,
                      le64_to_cpu(rn->keys[0]), &location);
-       if (r)
+       if (r) {
+               unlock_block(s->info, right);
                return r;
+       }
 
        if (key < le64_to_cpu(rn->keys[0])) {
                unlock_block(s->info, right);
@@ -492,7 +508,7 @@ static int btree_split_beneath(struct shadow_spine *s, uint64_t key)
        size_t size;
        unsigned nr_left, nr_right;
        struct dm_block *left, *right, *new_parent;
-       struct node *pn, *ln, *rn;
+       struct btree_node *pn, *ln, *rn;
        __le64 val;
 
        new_parent = shadow_current(s);
@@ -503,7 +519,7 @@ static int btree_split_beneath(struct shadow_spine *s, uint64_t key)
 
        r = new_block(s->info, &right);
        if (r < 0) {
-               /* FIXME: put left */
+               unlock_block(s->info, left);
                return r;
        }
 
@@ -552,23 +568,8 @@ static int btree_split_beneath(struct shadow_spine *s, uint64_t key)
        pn->keys[1] = rn->keys[0];
        memcpy_disk(value_ptr(pn, 1, sizeof(__le64)), &val, sizeof(__le64));
 
-       /*
-        * rejig the spine.  This is ugly, since it knows too
-        * much about the spine
-        */
-       if (s->nodes[0] != new_parent) {
-               unlock_block(s->info, s->nodes[0]);
-               s->nodes[0] = new_parent;
-       }
-       if (key < le64_to_cpu(rn->keys[0])) {
-               unlock_block(s->info, right);
-               s->nodes[1] = left;
-       } else {
-               unlock_block(s->info, left);
-               s->nodes[1] = right;
-       }
-       s->count = 2;
-
+       unlock_block(s->info, left);
+       unlock_block(s->info, right);
        return 0;
 }
 
@@ -577,7 +578,7 @@ static int btree_insert_raw(struct shadow_spine *s, dm_block_t root,
                            uint64_t key, unsigned *index)
 {
        int r, i = *index, top = 1;
-       struct node *node;
+       struct btree_node *node;
 
        for (;;) {
                r = shadow_step(s, root, vt);
@@ -644,15 +645,10 @@ static int insert(struct dm_btree_info *info, dm_block_t root,
        unsigned level, index = -1, last_level = info->levels - 1;
        dm_block_t block = root;
        struct shadow_spine spine;
-       struct node *n;
+       struct btree_node *n;
        struct dm_btree_value_type le64_type;
 
-       le64_type.context = NULL;
-       le64_type.size = sizeof(__le64);
-       le64_type.inc = NULL;
-       le64_type.dec = NULL;
-       le64_type.equal = NULL;
-
+       init_le64_type(info->tm, &le64_type);
        init_shadow_spine(&spine, info);
 
        for (level = 0; level < (info->levels - 1); level++) {