From e09b41010ba33a20a87472ee821fa407a5b8da36 Mon Sep 17 00:00:00 2001 From: José Pekkarinen Date: Mon, 11 Apr 2016 10:41:07 +0300 Subject: These changes are the raw update to linux-4.4.6-rt14. Kernel sources are taken from kernel.org, and rt patch from the rt wiki download page. MIME-Version: 1.0 Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: 8bit During the rebasing, the following patch collided: Force tick interrupt and get rid of softirq magic(I70131fb85). Collisions have been removed because its logic was found on the source already. Change-Id: I7f57a4081d9deaa0d9ccfc41a6c8daccdee3b769 Signed-off-by: José Pekkarinen --- kernel/drivers/md/persistent-data/dm-array.c | 4 +- .../drivers/md/persistent-data/dm-block-manager.c | 18 +- .../drivers/md/persistent-data/dm-block-manager.h | 3 +- .../drivers/md/persistent-data/dm-btree-internal.h | 8 +- .../drivers/md/persistent-data/dm-btree-remove.c | 217 +++++++++++++++------ kernel/drivers/md/persistent-data/dm-btree-spine.c | 57 ++++-- kernel/drivers/md/persistent-data/dm-btree.c | 120 ++++++++++-- kernel/drivers/md/persistent-data/dm-btree.h | 17 ++ .../md/persistent-data/dm-space-map-common.c | 32 +-- .../md/persistent-data/dm-space-map-metadata.c | 29 ++- .../md/persistent-data/dm-transaction-manager.c | 4 +- .../md/persistent-data/dm-transaction-manager.h | 2 +- 12 files changed, 380 insertions(+), 131 deletions(-) (limited to 'kernel/drivers/md/persistent-data') diff --git a/kernel/drivers/md/persistent-data/dm-array.c b/kernel/drivers/md/persistent-data/dm-array.c index e64b61ad0..431a03067 100644 --- a/kernel/drivers/md/persistent-data/dm-array.c +++ b/kernel/drivers/md/persistent-data/dm-array.c @@ -233,9 +233,9 @@ static int get_ablock(struct dm_array_info *info, dm_block_t b, /* * Unlocks an array block. */ -static int unlock_ablock(struct dm_array_info *info, struct dm_block *block) +static void unlock_ablock(struct dm_array_info *info, struct dm_block *block) { - return dm_tm_unlock(info->btree_info.tm, block); + dm_tm_unlock(info->btree_info.tm, block); } /*----------------------------------------------------------------*/ diff --git a/kernel/drivers/md/persistent-data/dm-block-manager.c b/kernel/drivers/md/persistent-data/dm-block-manager.c index 087411c95..f2393ba83 100644 --- a/kernel/drivers/md/persistent-data/dm-block-manager.c +++ b/kernel/drivers/md/persistent-data/dm-block-manager.c @@ -454,7 +454,7 @@ int dm_bm_read_lock(struct dm_block_manager *bm, dm_block_t b, int r; p = dm_bufio_read(bm->bufio, b, (struct dm_buffer **) result); - if (unlikely(IS_ERR(p))) + if (IS_ERR(p)) return PTR_ERR(p); aux = dm_bufio_get_aux_data(to_buffer(*result)); @@ -490,7 +490,7 @@ int dm_bm_write_lock(struct dm_block_manager *bm, return -EPERM; p = dm_bufio_read(bm->bufio, b, (struct dm_buffer **) result); - if (unlikely(IS_ERR(p))) + if (IS_ERR(p)) return PTR_ERR(p); aux = dm_bufio_get_aux_data(to_buffer(*result)); @@ -523,7 +523,7 @@ int dm_bm_read_try_lock(struct dm_block_manager *bm, int r; p = dm_bufio_get(bm->bufio, b, (struct dm_buffer **) result); - if (unlikely(IS_ERR(p))) + if (IS_ERR(p)) return PTR_ERR(p); if (unlikely(!p)) return -EWOULDBLOCK; @@ -559,7 +559,7 @@ int dm_bm_write_lock_zero(struct dm_block_manager *bm, return -EPERM; p = dm_bufio_new(bm->bufio, b, (struct dm_buffer **) result); - if (unlikely(IS_ERR(p))) + if (IS_ERR(p)) return PTR_ERR(p); memset(p, 0, dm_bm_block_size(bm)); @@ -578,7 +578,7 @@ int dm_bm_write_lock_zero(struct dm_block_manager *bm, } EXPORT_SYMBOL_GPL(dm_bm_write_lock_zero); -int dm_bm_unlock(struct dm_block *b) +void dm_bm_unlock(struct dm_block *b) { struct buffer_aux *aux; aux = dm_bufio_get_aux_data(to_buffer(b)); @@ -590,8 +590,6 @@ int dm_bm_unlock(struct dm_block *b) bl_up_read(&aux->lock); dm_bufio_release(to_buffer(b)); - - return 0; } EXPORT_SYMBOL_GPL(dm_bm_unlock); @@ -609,6 +607,12 @@ void dm_bm_prefetch(struct dm_block_manager *bm, dm_block_t b) dm_bufio_prefetch(bm->bufio, b, 1); } +bool dm_bm_is_read_only(struct dm_block_manager *bm) +{ + return bm->read_only; +} +EXPORT_SYMBOL_GPL(dm_bm_is_read_only); + void dm_bm_set_read_only(struct dm_block_manager *bm) { bm->read_only = true; diff --git a/kernel/drivers/md/persistent-data/dm-block-manager.h b/kernel/drivers/md/persistent-data/dm-block-manager.h index 1b95dfc17..3627d1b76 100644 --- a/kernel/drivers/md/persistent-data/dm-block-manager.h +++ b/kernel/drivers/md/persistent-data/dm-block-manager.h @@ -94,7 +94,7 @@ int dm_bm_write_lock_zero(struct dm_block_manager *bm, dm_block_t b, struct dm_block_validator *v, struct dm_block **result); -int dm_bm_unlock(struct dm_block *b); +void dm_bm_unlock(struct dm_block *b); /* * It's a common idiom to have a superblock that should be committed last. @@ -123,6 +123,7 @@ void dm_bm_prefetch(struct dm_block_manager *bm, dm_block_t b); * Additionally you should not use dm_bm_unlock_move, however no error will * be returned if you do. */ +bool dm_bm_is_read_only(struct dm_block_manager *bm); void dm_bm_set_read_only(struct dm_block_manager *bm); void dm_bm_set_read_write(struct dm_block_manager *bm); diff --git a/kernel/drivers/md/persistent-data/dm-btree-internal.h b/kernel/drivers/md/persistent-data/dm-btree-internal.h index bf2b80d5c..a240990a7 100644 --- a/kernel/drivers/md/persistent-data/dm-btree-internal.h +++ b/kernel/drivers/md/persistent-data/dm-btree-internal.h @@ -52,7 +52,7 @@ void inc_children(struct dm_transaction_manager *tm, struct btree_node *n, struct dm_btree_value_type *vt); int new_block(struct dm_btree_info *info, struct dm_block **result); -int unlock_block(struct dm_btree_info *info, struct dm_block *b); +void unlock_block(struct dm_btree_info *info, struct dm_block *b); /* * Spines keep track of the rolling locks. There are 2 variants, read-only @@ -138,4 +138,10 @@ int lower_bound(struct btree_node *n, uint64_t key); extern struct dm_block_validator btree_node_validator; +/* + * Value type for upper levels of multi-level btrees. + */ +extern void init_le64_type(struct dm_transaction_manager *tm, + struct dm_btree_value_type *vt); + #endif /* DM_BTREE_INTERNAL_H */ diff --git a/kernel/drivers/md/persistent-data/dm-btree-remove.c b/kernel/drivers/md/persistent-data/dm-btree-remove.c index a03178e91..21ea537bd 100644 --- a/kernel/drivers/md/persistent-data/dm-btree-remove.c +++ b/kernel/drivers/md/persistent-data/dm-btree-remove.c @@ -165,9 +165,9 @@ static int init_child(struct dm_btree_info *info, struct dm_btree_value_type *vt return 0; } -static int exit_child(struct dm_btree_info *info, struct child *c) +static void exit_child(struct dm_btree_info *info, struct child *c) { - return dm_tm_unlock(info->tm, c->block); + dm_tm_unlock(info->tm, c->block); } static void shift(struct btree_node *left, struct btree_node *right, int count) @@ -249,13 +249,10 @@ static int rebalance2(struct shadow_spine *s, struct dm_btree_info *info, __rebalance2(info, parent, &left, &right); - r = exit_child(info, &left); - if (r) { - exit_child(info, &right); - return r; - } + exit_child(info, &left); + exit_child(info, &right); - return exit_child(info, &right); + return 0; } /* @@ -301,11 +298,16 @@ static void redistribute3(struct dm_btree_info *info, struct btree_node *parent, { int s; uint32_t max_entries = le32_to_cpu(left->header.max_entries); - unsigned target = (nr_left + nr_center + nr_right) / 3; - BUG_ON(target > max_entries); + unsigned total = nr_left + nr_center + nr_right; + unsigned target_right = total / 3; + unsigned remainder = (target_right * 3) != total; + unsigned target_left = target_right + remainder; + + BUG_ON(target_left > max_entries); + BUG_ON(target_right > max_entries); if (nr_left < nr_right) { - s = nr_left - target; + s = nr_left - target_left; if (s < 0 && nr_center < -s) { /* not enough in central node */ @@ -316,10 +318,10 @@ static void redistribute3(struct dm_btree_info *info, struct btree_node *parent, } else shift(left, center, s); - shift(center, right, target - nr_right); + shift(center, right, target_right - nr_right); } else { - s = target - nr_right; + s = target_right - nr_right; if (s > 0 && nr_center < s) { /* not enough in central node */ shift(center, right, nr_center); @@ -329,7 +331,7 @@ static void redistribute3(struct dm_btree_info *info, struct btree_node *parent, } else shift(center, right, s); - shift(left, center, nr_left - target); + shift(left, center, nr_left - target_left); } *key_ptr(parent, c->index) = center->keys[0]; @@ -389,49 +391,18 @@ static int rebalance3(struct shadow_spine *s, struct dm_btree_info *info, __rebalance3(info, parent, &left, ¢er, &right); - r = exit_child(info, &left); - if (r) { - exit_child(info, ¢er); - exit_child(info, &right); - return r; - } - - r = exit_child(info, ¢er); - if (r) { - exit_child(info, &right); - return r; - } - - r = exit_child(info, &right); - if (r) - return r; + exit_child(info, &left); + exit_child(info, ¢er); + exit_child(info, &right); return 0; } -static int get_nr_entries(struct dm_transaction_manager *tm, - dm_block_t b, uint32_t *result) -{ - int r; - struct dm_block *block; - struct btree_node *n; - - r = dm_tm_read_lock(tm, b, &btree_node_validator, &block); - if (r) - return r; - - n = dm_block_data(block); - *result = le32_to_cpu(n->header.nr_entries); - - return dm_tm_unlock(tm, block); -} - static int rebalance_children(struct shadow_spine *s, struct dm_btree_info *info, struct dm_btree_value_type *vt, uint64_t key) { int i, r, has_left_sibling, has_right_sibling; - uint32_t child_entries; struct btree_node *n; n = dm_block_data(shadow_current(s)); @@ -446,9 +417,7 @@ static int rebalance_children(struct shadow_spine *s, memcpy(n, dm_block_data(child), dm_bm_block_size(dm_tm_get_bm(info->tm))); - r = dm_tm_unlock(info->tm, child); - if (r) - return r; + dm_tm_unlock(info->tm, child); dm_tm_dec(info->tm, dm_block_location(child)); return 0; @@ -458,10 +427,6 @@ static int rebalance_children(struct shadow_spine *s, if (i < 0) return -ENODATA; - r = get_nr_entries(info->tm, value64(n, i), &child_entries); - if (r) - return r; - has_left_sibling = i > 0; has_right_sibling = i < (le32_to_cpu(n->header.nr_entries) - 1); @@ -544,14 +509,6 @@ static int remove_raw(struct shadow_spine *s, struct dm_btree_info *info, return r; } -static struct dm_btree_value_type le64_type = { - .context = NULL, - .size = sizeof(__le64), - .inc = NULL, - .dec = NULL, - .equal = NULL -}; - int dm_btree_remove(struct dm_btree_info *info, dm_block_t root, uint64_t *keys, dm_block_t *new_root) { @@ -559,12 +516,14 @@ int dm_btree_remove(struct dm_btree_info *info, dm_block_t root, int index = 0, r = 0; struct shadow_spine spine; struct btree_node *n; + struct dm_btree_value_type le64_vt; + init_le64_type(info->tm, &le64_vt); init_shadow_spine(&spine, info); for (level = 0; level < info->levels; level++) { r = remove_raw(&spine, info, (level == last_level ? - &info->value_type : &le64_type), + &info->value_type : &le64_vt), root, keys[level], (unsigned *)&index); if (r < 0) break; @@ -590,3 +549,133 @@ int dm_btree_remove(struct dm_btree_info *info, dm_block_t root, return r; } EXPORT_SYMBOL_GPL(dm_btree_remove); + +/*----------------------------------------------------------------*/ + +static int remove_nearest(struct shadow_spine *s, struct dm_btree_info *info, + struct dm_btree_value_type *vt, dm_block_t root, + uint64_t key, int *index) +{ + int i = *index, r; + struct btree_node *n; + + for (;;) { + r = shadow_step(s, root, vt); + if (r < 0) + break; + + /* + * We have to patch up the parent node, ugly, but I don't + * see a way to do this automatically as part of the spine + * op. + */ + if (shadow_has_parent(s)) { + __le64 location = cpu_to_le64(dm_block_location(shadow_current(s))); + memcpy(value_ptr(dm_block_data(shadow_parent(s)), i), + &location, sizeof(__le64)); + } + + n = dm_block_data(shadow_current(s)); + + if (le32_to_cpu(n->header.flags) & LEAF_NODE) { + *index = lower_bound(n, key); + return 0; + } + + r = rebalance_children(s, info, vt, key); + if (r) + break; + + n = dm_block_data(shadow_current(s)); + if (le32_to_cpu(n->header.flags) & LEAF_NODE) { + *index = lower_bound(n, key); + return 0; + } + + i = lower_bound(n, key); + + /* + * We know the key is present, or else + * rebalance_children would have returned + * -ENODATA + */ + root = value64(n, i); + } + + return r; +} + +static int remove_one(struct dm_btree_info *info, dm_block_t root, + uint64_t *keys, uint64_t end_key, + dm_block_t *new_root, unsigned *nr_removed) +{ + unsigned level, last_level = info->levels - 1; + int index = 0, r = 0; + struct shadow_spine spine; + struct btree_node *n; + struct dm_btree_value_type le64_vt; + uint64_t k; + + init_le64_type(info->tm, &le64_vt); + init_shadow_spine(&spine, info); + for (level = 0; level < last_level; level++) { + r = remove_raw(&spine, info, &le64_vt, + root, keys[level], (unsigned *) &index); + if (r < 0) + goto out; + + n = dm_block_data(shadow_current(&spine)); + root = value64(n, index); + } + + r = remove_nearest(&spine, info, &info->value_type, + root, keys[last_level], &index); + if (r < 0) + goto out; + + n = dm_block_data(shadow_current(&spine)); + + if (index < 0) + index = 0; + + if (index >= le32_to_cpu(n->header.nr_entries)) { + r = -ENODATA; + goto out; + } + + k = le64_to_cpu(n->keys[index]); + if (k >= keys[last_level] && k < end_key) { + if (info->value_type.dec) + info->value_type.dec(info->value_type.context, + value_ptr(n, index)); + + delete_at(n, index); + keys[last_level] = k + 1ull; + + } else + r = -ENODATA; + +out: + *new_root = shadow_root(&spine); + exit_shadow_spine(&spine); + + return r; +} + +int dm_btree_remove_leaves(struct dm_btree_info *info, dm_block_t root, + uint64_t *first_key, uint64_t end_key, + dm_block_t *new_root, unsigned *nr_removed) +{ + int r; + + *nr_removed = 0; + do { + r = remove_one(info, root, first_key, end_key, &root, nr_removed); + if (!r) + (*nr_removed)++; + } while (!r); + + *new_root = root; + return r == -ENODATA ? 0 : r; +} +EXPORT_SYMBOL_GPL(dm_btree_remove_leaves); diff --git a/kernel/drivers/md/persistent-data/dm-btree-spine.c b/kernel/drivers/md/persistent-data/dm-btree-spine.c index 1b5e13ec7..b27b8091a 100644 --- a/kernel/drivers/md/persistent-data/dm-btree-spine.c +++ b/kernel/drivers/md/persistent-data/dm-btree-spine.c @@ -117,9 +117,9 @@ int new_block(struct dm_btree_info *info, struct dm_block **result) return dm_tm_new_block(info->tm, &btree_node_validator, result); } -int unlock_block(struct dm_btree_info *info, struct dm_block *b) +void unlock_block(struct dm_btree_info *info, struct dm_block *b) { - return dm_tm_unlock(info->tm, b); + dm_tm_unlock(info->tm, b); } /*----------------------------------------------------------------*/ @@ -137,9 +137,7 @@ int exit_ro_spine(struct ro_spine *s) int r = 0, i; for (i = 0; i < s->count; i++) { - int r2 = unlock_block(s->info, s->nodes[i]); - if (r2 < 0) - r = r2; + unlock_block(s->info, s->nodes[i]); } return r; @@ -150,9 +148,7 @@ int ro_step(struct ro_spine *s, dm_block_t new_child) int r; if (s->count == 2) { - r = unlock_block(s->info, s->nodes[0]); - if (r < 0) - return r; + unlock_block(s->info, s->nodes[0]); s->nodes[0] = s->nodes[1]; s->count--; } @@ -194,9 +190,7 @@ int exit_shadow_spine(struct shadow_spine *s) int r = 0, i; for (i = 0; i < s->count; i++) { - int r2 = unlock_block(s->info, s->nodes[i]); - if (r2 < 0) - r = r2; + unlock_block(s->info, s->nodes[i]); } return r; @@ -208,9 +202,7 @@ int shadow_step(struct shadow_spine *s, dm_block_t b, int r; if (s->count == 2) { - r = unlock_block(s->info, s->nodes[0]); - if (r < 0) - return r; + unlock_block(s->info, s->nodes[0]); s->nodes[0] = s->nodes[1]; s->count--; } @@ -249,3 +241,40 @@ int shadow_root(struct shadow_spine *s) { return s->root; } + +static void le64_inc(void *context, const void *value_le) +{ + struct dm_transaction_manager *tm = context; + __le64 v_le; + + memcpy(&v_le, value_le, sizeof(v_le)); + dm_tm_inc(tm, le64_to_cpu(v_le)); +} + +static void le64_dec(void *context, const void *value_le) +{ + struct dm_transaction_manager *tm = context; + __le64 v_le; + + memcpy(&v_le, value_le, sizeof(v_le)); + dm_tm_dec(tm, le64_to_cpu(v_le)); +} + +static int le64_equal(void *context, const void *value1_le, const void *value2_le) +{ + __le64 v1_le, v2_le; + + memcpy(&v1_le, value1_le, sizeof(v1_le)); + memcpy(&v2_le, value2_le, sizeof(v2_le)); + return v1_le == v2_le; +} + +void init_le64_type(struct dm_transaction_manager *tm, + struct dm_btree_value_type *vt) +{ + vt->context = tm; + vt->size = sizeof(__le64); + vt->inc = le64_inc; + vt->dec = le64_dec; + vt->equal = le64_equal; +} diff --git a/kernel/drivers/md/persistent-data/dm-btree.c b/kernel/drivers/md/persistent-data/dm-btree.c index fdd3793e2..b1ced58eb 100644 --- a/kernel/drivers/md/persistent-data/dm-btree.c +++ b/kernel/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 @@ -420,8 +517,8 @@ EXPORT_SYMBOL_GPL(dm_btree_lookup); * * Where A* is a shadow of A. */ -static int btree_split_sibling(struct shadow_spine *s, dm_block_t root, - unsigned parent_index, uint64_t key) +static int btree_split_sibling(struct shadow_spine *s, unsigned parent_index, + uint64_t key) { int r; size_t size; @@ -471,8 +568,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); @@ -523,7 +622,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; } @@ -625,7 +724,7 @@ static int btree_insert_raw(struct shadow_spine *s, dm_block_t root, if (top) r = btree_split_beneath(s, key); else - r = btree_split_sibling(s, root, i, key); + r = btree_split_sibling(s, i, key); if (r < 0) return r; @@ -667,12 +766,7 @@ static int insert(struct dm_btree_info *info, dm_block_t root, 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++) { diff --git a/kernel/drivers/md/persistent-data/dm-btree.h b/kernel/drivers/md/persistent-data/dm-btree.h index dacfc3418..c74301fa5 100644 --- a/kernel/drivers/md/persistent-data/dm-btree.h +++ b/kernel/drivers/md/persistent-data/dm-btree.h @@ -109,6 +109,13 @@ int dm_btree_del(struct dm_btree_info *info, dm_block_t root); int dm_btree_lookup(struct dm_btree_info *info, dm_block_t root, uint64_t *keys, void *value_le); +/* + * Tries to find the first key where the bottom level key is >= to that + * given. Useful for skipping empty sections of the btree. + */ +int dm_btree_lookup_next(struct dm_btree_info *info, dm_block_t root, + uint64_t *keys, uint64_t *rkey, void *value_le); + /* * Insertion (or overwrite an existing value). O(ln(n)) */ @@ -134,6 +141,16 @@ int dm_btree_insert_notify(struct dm_btree_info *info, dm_block_t root, int dm_btree_remove(struct dm_btree_info *info, dm_block_t root, uint64_t *keys, dm_block_t *new_root); +/* + * Removes a _contiguous_ run of values starting from 'keys' and not + * reaching keys2 (where keys2 is keys with the final key replaced with + * 'end_key'). 'end_key' is the one-past-the-end value. 'keys' may be + * altered. + */ +int dm_btree_remove_leaves(struct dm_btree_info *info, dm_block_t root, + uint64_t *keys, uint64_t end_key, + dm_block_t *new_root, unsigned *nr_removed); + /* * Returns < 0 on failure. Otherwise the number of key entries that have * been filled out. Remember trees can have zero entries, and as such have diff --git a/kernel/drivers/md/persistent-data/dm-space-map-common.c b/kernel/drivers/md/persistent-data/dm-space-map-common.c index aacbe70c2..306d2e450 100644 --- a/kernel/drivers/md/persistent-data/dm-space-map-common.c +++ b/kernel/drivers/md/persistent-data/dm-space-map-common.c @@ -259,9 +259,7 @@ int sm_ll_extend(struct ll_disk *ll, dm_block_t extra_blocks) idx.blocknr = cpu_to_le64(dm_block_location(b)); - r = dm_tm_unlock(ll->tm, b); - if (r < 0) - return r; + dm_tm_unlock(ll->tm, b); idx.nr_free = cpu_to_le32(ll->entries_per_block); idx.none_free_before = 0; @@ -293,7 +291,9 @@ int sm_ll_lookup_bitmap(struct ll_disk *ll, dm_block_t b, uint32_t *result) *result = sm_lookup_bitmap(dm_bitmap_data(blk), b); - return dm_tm_unlock(ll->tm, blk); + dm_tm_unlock(ll->tm, blk); + + return 0; } static int sm_ll_lookup_big_ref_count(struct ll_disk *ll, dm_block_t b, @@ -373,9 +373,7 @@ int sm_ll_find_free_block(struct ll_disk *ll, dm_block_t begin, return r; } - r = dm_tm_unlock(ll->tm, blk); - if (r < 0) - return r; + dm_tm_unlock(ll->tm, blk); *result = i * ll->entries_per_block + (dm_block_t) position; return 0; @@ -429,9 +427,7 @@ static int sm_ll_mutate(struct ll_disk *ll, dm_block_t b, if (ref_count <= 2) { sm_set_bitmap(bm_le, bit, ref_count); - r = dm_tm_unlock(ll->tm, nb); - if (r < 0) - return r; + dm_tm_unlock(ll->tm, nb); if (old > 2) { r = dm_btree_remove(&ll->ref_count_info, @@ -445,9 +441,7 @@ static int sm_ll_mutate(struct ll_disk *ll, dm_block_t b, __le32 le_rc = cpu_to_le32(ref_count); sm_set_bitmap(bm_le, bit, 3); - r = dm_tm_unlock(ll->tm, nb); - if (r < 0) - return r; + dm_tm_unlock(ll->tm, nb); __dm_bless_for_disk(&le_rc); r = dm_btree_insert(&ll->ref_count_info, ll->ref_count_root, @@ -556,7 +550,9 @@ static int metadata_ll_init_index(struct ll_disk *ll) memcpy(dm_block_data(b), &ll->mi_le, sizeof(ll->mi_le)); ll->bitmap_root = dm_block_location(b); - return dm_tm_unlock(ll->tm, b); + dm_tm_unlock(ll->tm, b); + + return 0; } static int metadata_ll_open(struct ll_disk *ll) @@ -570,7 +566,9 @@ static int metadata_ll_open(struct ll_disk *ll) return r; memcpy(&ll->mi_le, dm_block_data(block), sizeof(ll->mi_le)); - return dm_tm_unlock(ll->tm, block); + dm_tm_unlock(ll->tm, block); + + return 0; } static dm_block_t metadata_ll_max_entries(struct ll_disk *ll) @@ -590,7 +588,9 @@ static int metadata_ll_commit(struct ll_disk *ll) memcpy(dm_block_data(b), &ll->mi_le, sizeof(ll->mi_le)); ll->bitmap_root = dm_block_location(b); - return dm_tm_unlock(ll->tm, b); + dm_tm_unlock(ll->tm, b); + + return 0; } int sm_ll_new_metadata(struct ll_disk *ll, struct dm_transaction_manager *tm) diff --git a/kernel/drivers/md/persistent-data/dm-space-map-metadata.c b/kernel/drivers/md/persistent-data/dm-space-map-metadata.c index 53091295f..7e4400559 100644 --- a/kernel/drivers/md/persistent-data/dm-space-map-metadata.c +++ b/kernel/drivers/md/persistent-data/dm-space-map-metadata.c @@ -136,7 +136,7 @@ static int brb_push(struct bop_ring_buffer *brb, return 0; } -static int brb_pop(struct bop_ring_buffer *brb, struct block_op *result) +static int brb_peek(struct bop_ring_buffer *brb, struct block_op *result) { struct block_op *bop; @@ -147,6 +147,14 @@ static int brb_pop(struct bop_ring_buffer *brb, struct block_op *result) result->type = bop->type; result->block = bop->block; + return 0; +} + +static int brb_pop(struct bop_ring_buffer *brb) +{ + if (brb_empty(brb)) + return -ENODATA; + brb->begin = brb_next(brb, brb->begin); return 0; @@ -211,7 +219,7 @@ static int apply_bops(struct sm_metadata *smm) while (!brb_empty(&smm->uncommitted)) { struct block_op bop; - r = brb_pop(&smm->uncommitted, &bop); + r = brb_peek(&smm->uncommitted, &bop); if (r) { DMERR("bug in bop ring buffer"); break; @@ -220,6 +228,8 @@ static int apply_bops(struct sm_metadata *smm) r = commit_bop(smm, &bop); if (r) break; + + brb_pop(&smm->uncommitted); } return r; @@ -683,7 +693,6 @@ static struct dm_space_map bootstrap_ops = { static int sm_metadata_extend(struct dm_space_map *sm, dm_block_t extra_blocks) { int r, i; - enum allocation_event ev; struct sm_metadata *smm = container_of(sm, struct sm_metadata, sm); dm_block_t old_len = smm->ll.nr_blocks; @@ -705,11 +714,12 @@ static int sm_metadata_extend(struct dm_space_map *sm, dm_block_t extra_blocks) * allocate any new blocks. */ do { - for (i = old_len; !r && i < smm->begin; i++) { - r = sm_ll_inc(&smm->ll, i, &ev); - if (r) - goto out; - } + for (i = old_len; !r && i < smm->begin; i++) + r = add_bop(smm, BOP_INC, i); + + if (r) + goto out; + old_len = smm->begin; r = apply_bops(smm); @@ -754,7 +764,6 @@ int dm_sm_metadata_create(struct dm_space_map *sm, { int r; dm_block_t i; - enum allocation_event ev; struct sm_metadata *smm = container_of(sm, struct sm_metadata, sm); smm->begin = superblock + 1; @@ -782,7 +791,7 @@ int dm_sm_metadata_create(struct dm_space_map *sm, * allocated blocks that they were built from. */ for (i = superblock; !r && i < smm->begin; i++) - r = sm_ll_inc(&smm->ll, i, &ev); + r = add_bop(smm, BOP_INC, i); if (r) return r; diff --git a/kernel/drivers/md/persistent-data/dm-transaction-manager.c b/kernel/drivers/md/persistent-data/dm-transaction-manager.c index 9cb797d80..abe2c5dd0 100644 --- a/kernel/drivers/md/persistent-data/dm-transaction-manager.c +++ b/kernel/drivers/md/persistent-data/dm-transaction-manager.c @@ -342,9 +342,9 @@ int dm_tm_read_lock(struct dm_transaction_manager *tm, dm_block_t b, } EXPORT_SYMBOL_GPL(dm_tm_read_lock); -int dm_tm_unlock(struct dm_transaction_manager *tm, struct dm_block *b) +void dm_tm_unlock(struct dm_transaction_manager *tm, struct dm_block *b) { - return dm_bm_unlock(b); + dm_bm_unlock(b); } EXPORT_SYMBOL_GPL(dm_tm_unlock); diff --git a/kernel/drivers/md/persistent-data/dm-transaction-manager.h b/kernel/drivers/md/persistent-data/dm-transaction-manager.h index 2e0d4d66f..f3a18be68 100644 --- a/kernel/drivers/md/persistent-data/dm-transaction-manager.h +++ b/kernel/drivers/md/persistent-data/dm-transaction-manager.h @@ -94,7 +94,7 @@ int dm_tm_read_lock(struct dm_transaction_manager *tm, dm_block_t b, struct dm_block_validator *v, struct dm_block **result); -int dm_tm_unlock(struct dm_transaction_manager *tm, struct dm_block *b); +void dm_tm_unlock(struct dm_transaction_manager *tm, struct dm_block *b); /* * Functions for altering the reference count of a block directly. -- cgit 1.2.3-korg