summaryrefslogtreecommitdiff
path: root/drivers/md/persistent-data/dm-array.c
diff options
context:
space:
mode:
Diffstat (limited to 'drivers/md/persistent-data/dm-array.c')
-rw-r--r--drivers/md/persistent-data/dm-array.c371
1 files changed, 292 insertions, 79 deletions
diff --git a/drivers/md/persistent-data/dm-array.c b/drivers/md/persistent-data/dm-array.c
index 172147eb1d40..8f8792e55806 100644
--- a/drivers/md/persistent-data/dm-array.c
+++ b/drivers/md/persistent-data/dm-array.c
@@ -1,3 +1,4 @@
+// SPDX-License-Identifier: GPL-2.0-only
/*
* Copyright (C) 2012 Red Hat, Inc.
*
@@ -37,7 +38,7 @@ struct array_block {
*/
#define CSUM_XOR 595846735
-static void array_block_prepare_for_write(struct dm_block_validator *v,
+static void array_block_prepare_for_write(const struct dm_block_validator *v,
struct dm_block *b,
size_t size_of_block)
{
@@ -49,7 +50,7 @@ static void array_block_prepare_for_write(struct dm_block_validator *v,
CSUM_XOR));
}
-static int array_block_check(struct dm_block_validator *v,
+static int array_block_check(const struct dm_block_validator *v,
struct dm_block *b,
size_t size_of_block)
{
@@ -57,7 +58,7 @@ static int array_block_check(struct dm_block_validator *v,
__le32 csum_disk;
if (dm_block_location(b) != le64_to_cpu(bh_le->blocknr)) {
- DMERR_LIMIT("array_block_check failed: blocknr %llu != wanted %llu",
+ DMERR_LIMIT("%s failed: blocknr %llu != wanted %llu", __func__,
(unsigned long long) le64_to_cpu(bh_le->blocknr),
(unsigned long long) dm_block_location(b));
return -ENOTBLK;
@@ -67,16 +68,16 @@ static int array_block_check(struct dm_block_validator *v,
size_of_block - sizeof(__le32),
CSUM_XOR));
if (csum_disk != bh_le->csum) {
- DMERR_LIMIT("array_block_check failed: csum %u != wanted %u",
- (unsigned) le32_to_cpu(csum_disk),
- (unsigned) le32_to_cpu(bh_le->csum));
+ DMERR_LIMIT("%s failed: csum %u != wanted %u", __func__,
+ (unsigned int) le32_to_cpu(csum_disk),
+ (unsigned int) le32_to_cpu(bh_le->csum));
return -EILSEQ;
}
return 0;
}
-static struct dm_block_validator array_validator = {
+static const struct dm_block_validator array_validator = {
.name = "array",
.prepare_for_write = array_block_prepare_for_write,
.check = array_block_check
@@ -94,7 +95,7 @@ static struct dm_block_validator array_validator = {
* index - The index into _this_ specific block.
*/
static void *element_at(struct dm_array_info *info, struct array_block *ab,
- unsigned index)
+ unsigned int index)
{
unsigned char *entry = (unsigned char *) (ab + 1);
@@ -108,12 +109,11 @@ static void *element_at(struct dm_array_info *info, struct array_block *ab,
* in an array block.
*/
static void on_entries(struct dm_array_info *info, struct array_block *ab,
- void (*fn)(void *, const void *))
+ void (*fn)(void *, const void *, unsigned int))
{
- unsigned i, nr_entries = le32_to_cpu(ab->nr_entries);
+ unsigned int nr_entries = le32_to_cpu(ab->nr_entries);
- for (i = 0; i < nr_entries; i++)
- fn(info->value_type.context, element_at(info, ab, i));
+ fn(info->value_type.context, element_at(info, ab, 0), nr_entries);
}
/*
@@ -173,21 +173,20 @@ static int alloc_ablock(struct dm_array_info *info, size_t size_of_block,
* the current number of entries.
*/
static void fill_ablock(struct dm_array_info *info, struct array_block *ab,
- const void *value, unsigned new_nr)
+ const void *value, unsigned int new_nr)
{
- unsigned i;
- uint32_t nr_entries;
+ uint32_t nr_entries, delta, i;
struct dm_btree_value_type *vt = &info->value_type;
BUG_ON(new_nr > le32_to_cpu(ab->max_entries));
BUG_ON(new_nr < le32_to_cpu(ab->nr_entries));
nr_entries = le32_to_cpu(ab->nr_entries);
- for (i = nr_entries; i < new_nr; i++) {
- if (vt->inc)
- vt->inc(vt->context, value);
+ delta = new_nr - nr_entries;
+ if (vt->inc)
+ vt->inc(vt->context, value, delta);
+ for (i = nr_entries; i < new_nr; i++)
memcpy(element_at(info, ab, i), value, vt->size);
- }
ab->nr_entries = cpu_to_le32(new_nr);
}
@@ -197,19 +196,18 @@ static void fill_ablock(struct dm_array_info *info, struct array_block *ab,
* entries.
*/
static void trim_ablock(struct dm_array_info *info, struct array_block *ab,
- unsigned new_nr)
+ unsigned int new_nr)
{
- unsigned i;
- uint32_t nr_entries;
+ uint32_t nr_entries, delta;
struct dm_btree_value_type *vt = &info->value_type;
BUG_ON(new_nr > le32_to_cpu(ab->max_entries));
BUG_ON(new_nr > le32_to_cpu(ab->nr_entries));
nr_entries = le32_to_cpu(ab->nr_entries);
- for (i = nr_entries; i > new_nr; i--)
- if (vt->dec)
- vt->dec(vt->context, element_at(info, ab, i - 1));
+ delta = nr_entries - new_nr;
+ if (vt->dec)
+ vt->dec(vt->context, element_at(info, ab, new_nr - 1), delta);
ab->nr_entries = cpu_to_le32(new_nr);
}
@@ -233,9 +231,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);
}
/*----------------------------------------------------------------*/
@@ -251,7 +249,7 @@ static int unlock_ablock(struct dm_array_info *info, struct dm_block *block)
* / max_entries).
*/
static int lookup_ablock(struct dm_array_info *info, dm_block_t root,
- unsigned index, struct dm_block **block,
+ unsigned int index, struct dm_block **block,
struct array_block **ab)
{
int r;
@@ -277,50 +275,72 @@ static int insert_ablock(struct dm_array_info *info, uint64_t index,
return dm_btree_insert(&info->btree_info, *root, &index, &block_le, root);
}
+/*----------------------------------------------------------------*/
+
+static int __shadow_ablock(struct dm_array_info *info, dm_block_t b,
+ struct dm_block **block, struct array_block **ab)
+{
+ int inc;
+ int r = dm_tm_shadow_block(info->btree_info.tm, b,
+ &array_validator, block, &inc);
+ if (r)
+ return r;
+
+ *ab = dm_block_data(*block);
+ if (inc)
+ inc_ablock_entries(info, *ab);
+
+ return 0;
+}
+
+/*
+ * The shadow op will often be a noop. Only insert if it really
+ * copied data.
+ */
+static int __reinsert_ablock(struct dm_array_info *info, unsigned int index,
+ struct dm_block *block, dm_block_t b,
+ dm_block_t *root)
+{
+ int r = 0;
+
+ if (dm_block_location(block) != b) {
+ /*
+ * dm_tm_shadow_block will have already decremented the old
+ * block, but it is still referenced by the btree. We
+ * increment to stop the insert decrementing it below zero
+ * when overwriting the old value.
+ */
+ dm_tm_inc(info->btree_info.tm, b);
+ r = insert_ablock(info, index, block, root);
+ }
+
+ return r;
+}
+
/*
* Looks up an array block in the btree. Then shadows it, and updates the
* btree to point to this new shadow. 'root' is an input/output parameter
* for both the current root block, and the new one.
*/
static int shadow_ablock(struct dm_array_info *info, dm_block_t *root,
- unsigned index, struct dm_block **block,
+ unsigned int index, struct dm_block **block,
struct array_block **ab)
{
- int r, inc;
+ int r;
uint64_t key = index;
dm_block_t b;
__le64 block_le;
- /*
- * lookup
- */
r = dm_btree_lookup(&info->btree_info, *root, &key, &block_le);
if (r)
return r;
b = le64_to_cpu(block_le);
- /*
- * shadow
- */
- r = dm_tm_shadow_block(info->btree_info.tm, b,
- &array_validator, block, &inc);
+ r = __shadow_ablock(info, b, block, ab);
if (r)
return r;
- *ab = dm_block_data(*block);
- if (inc)
- inc_ablock_entries(info, *ab);
-
- /*
- * Reinsert.
- *
- * The shadow op will often be a noop. Only insert if it really
- * copied data.
- */
- if (dm_block_location(*block) != b)
- r = insert_ablock(info, index, *block, root);
-
- return r;
+ return __reinsert_ablock(info, index, *block, b, root);
}
/*
@@ -328,7 +348,7 @@ static int shadow_ablock(struct dm_array_info *info, dm_block_t *root,
*/
static int insert_new_ablock(struct dm_array_info *info, size_t size_of_block,
uint32_t max_entries,
- unsigned block_index, uint32_t nr,
+ unsigned int block_index, uint32_t nr,
const void *value, dm_block_t *root)
{
int r;
@@ -347,8 +367,8 @@ static int insert_new_ablock(struct dm_array_info *info, size_t size_of_block,
}
static int insert_full_ablocks(struct dm_array_info *info, size_t size_of_block,
- unsigned begin_block, unsigned end_block,
- unsigned max_entries, const void *value,
+ unsigned int begin_block, unsigned int end_block,
+ unsigned int max_entries, const void *value,
dm_block_t *root)
{
int r = 0;
@@ -384,20 +404,20 @@ struct resize {
/*
* Maximum nr entries in an array block.
*/
- unsigned max_entries;
+ unsigned int max_entries;
/*
* nr of completely full blocks in the array.
*
* 'old' refers to before the resize, 'new' after.
*/
- unsigned old_nr_full_blocks, new_nr_full_blocks;
+ unsigned int old_nr_full_blocks, new_nr_full_blocks;
/*
* Number of entries in the final block. 0 iff only full blocks in
* the array.
*/
- unsigned old_nr_entries_in_last_block, new_nr_entries_in_last_block;
+ unsigned int old_nr_entries_in_last_block, new_nr_entries_in_last_block;
/*
* The default value used when growing the array.
@@ -412,13 +432,14 @@ struct resize {
* begin_index - the index of the first array block to remove.
* end_index - the one-past-the-end value. ie. this block is not removed.
*/
-static int drop_blocks(struct resize *resize, unsigned begin_index,
- unsigned end_index)
+static int drop_blocks(struct resize *resize, unsigned int begin_index,
+ unsigned int end_index)
{
int r;
while (begin_index != end_index) {
uint64_t key = begin_index++;
+
r = dm_btree_remove(&resize->info->btree_info, resize->root,
&key, &resize->root);
if (r)
@@ -431,8 +452,8 @@ static int drop_blocks(struct resize *resize, unsigned begin_index,
/*
* Calculates how many blocks are needed for the array.
*/
-static unsigned total_nr_blocks_needed(unsigned nr_full_blocks,
- unsigned nr_entries_in_last_block)
+static unsigned int total_nr_blocks_needed(unsigned int nr_full_blocks,
+ unsigned int nr_entries_in_last_block)
{
return nr_full_blocks + (nr_entries_in_last_block ? 1 : 0);
}
@@ -443,7 +464,7 @@ static unsigned total_nr_blocks_needed(unsigned nr_full_blocks,
static int shrink(struct resize *resize)
{
int r;
- unsigned begin, end;
+ unsigned int begin, end;
struct dm_block *block;
struct array_block *ab;
@@ -509,15 +530,18 @@ static int grow_add_tail_block(struct resize *resize)
static int grow_needs_more_blocks(struct resize *resize)
{
int r;
+ unsigned int old_nr_blocks = resize->old_nr_full_blocks;
if (resize->old_nr_entries_in_last_block > 0) {
+ old_nr_blocks++;
+
r = grow_extend_tail_block(resize, resize->max_entries);
if (r)
return r;
}
r = insert_full_ablocks(resize->info, resize->size_of_block,
- resize->old_nr_full_blocks,
+ old_nr_blocks,
resize->new_nr_full_blocks,
resize->max_entries, resize->value,
&resize->root);
@@ -548,16 +572,17 @@ static int grow(struct resize *resize)
* These are the value_type functions for the btree elements, which point
* to array blocks.
*/
-static void block_inc(void *context, const void *value)
+static void block_inc(void *context, const void *value, unsigned int count)
{
- __le64 block_le;
+ const __le64 *block_le = value;
struct dm_array_info *info = context;
+ unsigned int i;
- memcpy(&block_le, value, sizeof(block_le));
- dm_tm_inc(info->btree_info.tm, le64_to_cpu(block_le));
+ for (i = 0; i < count; i++, block_le++)
+ dm_tm_inc(info->btree_info.tm, le64_to_cpu(*block_le));
}
-static void block_dec(void *context, const void *value)
+static void __block_dec(void *context, const void *value)
{
int r;
uint64_t b;
@@ -596,6 +621,14 @@ static void block_dec(void *context, const void *value)
dm_tm_dec(info->btree_info.tm, b);
}
+static void block_dec(void *context, const void *value, unsigned int count)
+{
+ unsigned int i;
+
+ for (i = 0; i < count; i++, value += sizeof(__le64))
+ __block_dec(context, value);
+}
+
static int block_equal(void *context, const void *value1, const void *value2)
{
return !memcmp(value1, value2, sizeof(__le64));
@@ -634,8 +667,10 @@ static int array_resize(struct dm_array_info *info, dm_block_t root,
int r;
struct resize resize;
- if (old_size == new_size)
+ if (old_size == new_size) {
+ *new_root = root;
return 0;
+ }
resize.info = info;
resize.root = root;
@@ -660,14 +695,80 @@ static int array_resize(struct dm_array_info *info, dm_block_t root,
int dm_array_resize(struct dm_array_info *info, dm_block_t root,
uint32_t old_size, uint32_t new_size,
const void *value, dm_block_t *new_root)
- __dm_written_to_disk(value)
+ __dm_written_to_disk(value)
{
int r = array_resize(info, root, old_size, new_size, value, new_root);
+
__dm_unbless_for_disk(value);
return r;
}
EXPORT_SYMBOL_GPL(dm_array_resize);
+static int populate_ablock_with_values(struct dm_array_info *info, struct array_block *ab,
+ value_fn fn, void *context,
+ unsigned int base, unsigned int new_nr)
+{
+ int r;
+ unsigned int i;
+ struct dm_btree_value_type *vt = &info->value_type;
+
+ BUG_ON(le32_to_cpu(ab->nr_entries));
+ BUG_ON(new_nr > le32_to_cpu(ab->max_entries));
+
+ for (i = 0; i < new_nr; i++) {
+ r = fn(base + i, element_at(info, ab, i), context);
+ if (r)
+ return r;
+
+ if (vt->inc)
+ vt->inc(vt->context, element_at(info, ab, i), 1);
+ }
+
+ ab->nr_entries = cpu_to_le32(new_nr);
+ return 0;
+}
+
+int dm_array_new(struct dm_array_info *info, dm_block_t *root,
+ uint32_t size, value_fn fn, void *context)
+{
+ int r;
+ struct dm_block *block;
+ struct array_block *ab;
+ unsigned int block_index, end_block, size_of_block, max_entries;
+
+ r = dm_array_empty(info, root);
+ if (r)
+ return r;
+
+ size_of_block = dm_bm_block_size(dm_tm_get_bm(info->btree_info.tm));
+ max_entries = calc_max_entries(info->value_type.size, size_of_block);
+ end_block = dm_div_up(size, max_entries);
+
+ for (block_index = 0; block_index != end_block; block_index++) {
+ r = alloc_ablock(info, size_of_block, max_entries, &block, &ab);
+ if (r)
+ break;
+
+ r = populate_ablock_with_values(info, ab, fn, context,
+ block_index * max_entries,
+ min(max_entries, size));
+ if (r) {
+ unlock_ablock(info, block);
+ break;
+ }
+
+ r = insert_ablock(info, block_index, block, root);
+ unlock_ablock(info, block);
+ if (r)
+ break;
+
+ size -= max_entries;
+ }
+
+ return r;
+}
+EXPORT_SYMBOL_GPL(dm_array_new);
+
int dm_array_del(struct dm_array_info *info, dm_block_t root)
{
return dm_btree_del(&info->btree_info, root);
@@ -681,7 +782,7 @@ int dm_array_get_value(struct dm_array_info *info, dm_block_t root,
struct dm_block *block;
struct array_block *ab;
size_t size_of_block;
- unsigned entry, max_entries;
+ unsigned int entry, max_entries;
size_of_block = dm_bm_block_size(dm_tm_get_bm(info->btree_info.tm));
max_entries = calc_max_entries(info->value_type.size, size_of_block);
@@ -709,8 +810,8 @@ static int array_set_value(struct dm_array_info *info, dm_block_t root,
struct dm_block *block;
struct array_block *ab;
size_t size_of_block;
- unsigned max_entries;
- unsigned entry;
+ unsigned int max_entries;
+ unsigned int entry;
void *old_value;
struct dm_btree_value_type *vt = &info->value_type;
@@ -731,9 +832,9 @@ static int array_set_value(struct dm_array_info *info, dm_block_t root,
old_value = element_at(info, ab, entry);
if (vt->dec &&
(!vt->equal || !vt->equal(vt->context, old_value, value))) {
- vt->dec(vt->context, old_value);
+ vt->dec(vt->context, old_value, 1);
if (vt->inc)
- vt->inc(vt->context, value);
+ vt->inc(vt->context, value, 1);
}
memcpy(old_value, value, info->value_type.size);
@@ -745,7 +846,7 @@ out:
int dm_array_set_value(struct dm_array_info *info, dm_block_t root,
uint32_t index, const void *value, dm_block_t *new_root)
- __dm_written_to_disk(value)
+ __dm_written_to_disk(value)
{
int r;
@@ -766,9 +867,9 @@ static int walk_ablock(void *context, uint64_t *keys, void *leaf)
struct walk_info *wi = context;
int r;
- unsigned i;
+ unsigned int i;
__le64 block_le;
- unsigned nr_entries, max_entries;
+ unsigned int nr_entries, max_entries;
struct dm_block *block;
struct array_block *ab;
@@ -806,3 +907,115 @@ int dm_array_walk(struct dm_array_info *info, dm_block_t root,
EXPORT_SYMBOL_GPL(dm_array_walk);
/*----------------------------------------------------------------*/
+
+static int load_ablock(struct dm_array_cursor *c)
+{
+ int r;
+ __le64 value_le;
+ uint64_t key;
+
+ if (c->block)
+ unlock_ablock(c->info, c->block);
+
+ c->index = 0;
+
+ r = dm_btree_cursor_get_value(&c->cursor, &key, &value_le);
+ if (r) {
+ DMERR("dm_btree_cursor_get_value failed");
+ goto out;
+
+ } else {
+ r = get_ablock(c->info, le64_to_cpu(value_le), &c->block, &c->ab);
+ if (r) {
+ DMERR("get_ablock failed");
+ goto out;
+ }
+ }
+
+ return 0;
+
+out:
+ dm_btree_cursor_end(&c->cursor);
+ c->block = NULL;
+ c->ab = NULL;
+ return r;
+}
+
+int dm_array_cursor_begin(struct dm_array_info *info, dm_block_t root,
+ struct dm_array_cursor *c)
+{
+ int r;
+
+ memset(c, 0, sizeof(*c));
+ c->info = info;
+ r = dm_btree_cursor_begin(&info->btree_info, root, true, &c->cursor);
+ if (r) {
+ DMERR("couldn't create btree cursor");
+ return r;
+ }
+
+ return load_ablock(c);
+}
+EXPORT_SYMBOL_GPL(dm_array_cursor_begin);
+
+void dm_array_cursor_end(struct dm_array_cursor *c)
+{
+ if (c->block)
+ unlock_ablock(c->info, c->block);
+
+ dm_btree_cursor_end(&c->cursor);
+}
+EXPORT_SYMBOL_GPL(dm_array_cursor_end);
+
+int dm_array_cursor_next(struct dm_array_cursor *c)
+{
+ int r;
+
+ if (!c->block)
+ return -ENODATA;
+
+ c->index++;
+
+ if (c->index >= le32_to_cpu(c->ab->nr_entries)) {
+ r = dm_btree_cursor_next(&c->cursor);
+ if (r)
+ return r;
+
+ r = load_ablock(c);
+ if (r)
+ return r;
+ }
+
+ return 0;
+}
+EXPORT_SYMBOL_GPL(dm_array_cursor_next);
+
+int dm_array_cursor_skip(struct dm_array_cursor *c, uint32_t count)
+{
+ int r;
+
+ do {
+ uint32_t remaining = le32_to_cpu(c->ab->nr_entries) - c->index;
+
+ if (count < remaining) {
+ c->index += count;
+ return 0;
+ }
+
+ count -= remaining;
+ c->index += (remaining - 1);
+ r = dm_array_cursor_next(c);
+
+ } while (!r);
+
+ return r;
+}
+EXPORT_SYMBOL_GPL(dm_array_cursor_skip);
+
+void dm_array_cursor_get_value(struct dm_array_cursor *c, void **value_le)
+{
+ *value_le = element_at(c->info, c->ab, c->index);
+}
+EXPORT_SYMBOL_GPL(dm_array_cursor_get_value);
+
+/*----------------------------------------------------------------*/
generated by cgit (git 2.34.1) at 2025-12-21 21:35:55 +0000