dm btree: factor out need_insert() helper

[karo-tx-linux.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 0e09aef43998ac250cc296122247875eed23ceb2..ea3d3b656fd0a1f8f55a0bcb0285bf4a94f6c38d 100644 (file)
--- a/drivers/md/persistent-data/dm-btree.c
+++ b/drivers/md/persistent-data/dm-btree.c
@@ -63,6 +63,11 @@ int lower_bound(struct btree_node *n, uint64_t key)
        return bsearch(n, key, 0);
 }
 
+static int upper_bound(struct btree_node *n, uint64_t key)
+{
+       return bsearch(n, key, 1);
+}
+
 void inc_children(struct dm_transaction_manager *tm, struct btree_node *n,
                  struct dm_btree_value_type *vt)
 {
@@ -141,7 +146,9 @@ int dm_btree_empty(struct dm_btree_info *info, dm_block_t *root)
        n->header.value_size = cpu_to_le32(info->value_type.size);
 
        *root = dm_block_location(b);
-       return unlock_block(info, b);
+       unlock_block(info, b);
+
+       return 0;
 }
 EXPORT_SYMBOL_GPL(dm_btree_empty);
 
@@ -250,6 +257,16 @@ 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;
@@ -306,9 +323,13 @@ int dm_btree_del(struct dm_btree_info *info, dm_block_t root)
                        pop_frame(s);
                }
        }
-
 out:
+       if (r) {
+               /* cleanup all frames of del_stack */
+               unlock_all_frames(s);
+       }
        kfree(s);
+
        return r;
 }
 EXPORT_SYMBOL_GPL(dm_btree_del);
@@ -390,6 +411,82 @@ int dm_btree_lookup(struct dm_btree_info *info, dm_block_t root,
 }
 EXPORT_SYMBOL_GPL(dm_btree_lookup);
 
+static int dm_btree_lookup_next_single(struct dm_btree_info *info, dm_block_t root,
+                                      uint64_t key, uint64_t *rkey, void *value_le)
+{
+       int r, i;
+       uint32_t flags, nr_entries;
+       struct dm_block *node;
+       struct btree_node *n;
+
+       r = bn_read_lock(info, root, &node);
+       if (r)
+               return r;
+
+       n = dm_block_data(node);
+       flags = le32_to_cpu(n->header.flags);
+       nr_entries = le32_to_cpu(n->header.nr_entries);
+
+       if (flags & INTERNAL_NODE) {
+               i = lower_bound(n, key);
+               if (i < 0 || i >= nr_entries) {
+                       r = -ENODATA;
+                       goto out;
+               }
+
+               r = dm_btree_lookup_next_single(info, value64(n, i), key, rkey, value_le);
+               if (r == -ENODATA && i < (nr_entries - 1)) {
+                       i++;
+                       r = dm_btree_lookup_next_single(info, value64(n, i), key, rkey, value_le);
+               }
+
+       } else {
+               i = upper_bound(n, key);
+               if (i < 0 || i >= nr_entries) {
+                       r = -ENODATA;
+                       goto out;
+               }
+
+               *rkey = le64_to_cpu(n->keys[i]);
+               memcpy(value_le, value_ptr(n, i), info->value_type.size);
+       }
+out:
+       dm_tm_unlock(info->tm, node);
+       return r;
+}
+
+int dm_btree_lookup_next(struct dm_btree_info *info, dm_block_t root,
+                        uint64_t *keys, uint64_t *rkey, void *value_le)
+{
+       unsigned level;
+       int r = -ENODATA;
+       __le64 internal_value_le;
+       struct ro_spine spine;
+
+       init_ro_spine(&spine, info);
+       for (level = 0; level < info->levels - 1u; level++) {
+               r = btree_lookup_raw(&spine, root, keys[level],
+                                    lower_bound, rkey,
+                                    &internal_value_le, sizeof(uint64_t));
+               if (r)
+                       goto out;
+
+               if (*rkey != keys[level]) {
+                       r = -ENODATA;
+                       goto out;
+               }
+
+               root = le64_to_cpu(internal_value_le);
+       }
+
+       r = dm_btree_lookup_next_single(info, root, keys[level], rkey, value_le);
+out:
+       exit_ro_spine(&spine);
+       return r;
+}
+
+EXPORT_SYMBOL_GPL(dm_btree_lookup_next);
+
 /*
  * Splits a node by creating a sibling node and shifting half the nodes
  * contents across.  Assumes there is a parent node, and it has room for
@@ -471,8 +568,10 @@ static int btree_split_sibling(struct shadow_spine *s, unsigned parent_index,
 
        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);
@@ -655,12 +754,19 @@ static int btree_insert_raw(struct shadow_spine *s, dm_block_t root,
        return 0;
 }
 
+static bool need_insert(struct btree_node *node, uint64_t *keys,
+                       unsigned level, unsigned index)
+{
+        return ((index >= le32_to_cpu(node->header.nr_entries)) ||
+               (le64_to_cpu(node->keys[index]) != keys[level]));
+}
+
 static int insert(struct dm_btree_info *info, dm_block_t root,
                  uint64_t *keys, void *value, dm_block_t *new_root,
                  int *inserted)
                  __dm_written_to_disk(value)
 {
-       int r, need_insert;
+       int r;
        unsigned level, index = -1, last_level = info->levels - 1;
        dm_block_t block = root;
        struct shadow_spine spine;
@@ -676,10 +782,8 @@ static int insert(struct dm_btree_info *info, dm_block_t root,
                        goto bad;
 
                n = dm_block_data(shadow_current(&spine));
-               need_insert = ((index >= le32_to_cpu(n->header.nr_entries)) ||
-                              (le64_to_cpu(n->keys[index]) != keys[level]));
 
-               if (need_insert) {
+               if (need_insert(n, keys, level, index)) {
                        dm_block_t new_tree;
                        __le64 new_le;
 
@@ -706,10 +810,8 @@ static int insert(struct dm_btree_info *info, dm_block_t root,
                goto bad;
 
        n = dm_block_data(shadow_current(&spine));
-       need_insert = ((index >= le32_to_cpu(n->header.nr_entries)) ||
-                      (le64_to_cpu(n->keys[index]) != keys[level]));
 
-       if (need_insert) {
+       if (need_insert(n, keys, level, index)) {
                if (inserted)
                        *inserted = 1;