2 * Copyright (C) 2012 Red Hat, Inc.
4 * This file is released under the GPL.
8 #include "dm-space-map.h"
9 #include "dm-transaction-manager.h"
11 #include <linux/export.h>
12 #include <linux/device-mapper.h>
14 #define DM_MSG_PREFIX "array"
16 /*----------------------------------------------------------------*/
19 * The array is implemented as a fully populated btree, which points to
20 * blocks that contain the packed values. This is more space efficient
21 * than just using a btree since we don't store 1 key per value.
28 __le64 blocknr; /* Block this node is supposed to live in. */
31 /*----------------------------------------------------------------*/
34 * Validator methods. As usual we calculate a checksum, and also write the
35 * block location into the header (paranoia about ssds remapping areas by
38 #define CSUM_XOR 595846735
40 static void array_block_prepare_for_write(struct dm_block_validator *v,
44 struct array_block *bh_le = dm_block_data(b);
46 bh_le->blocknr = cpu_to_le64(dm_block_location(b));
47 bh_le->csum = cpu_to_le32(dm_bm_checksum(&bh_le->max_entries,
48 size_of_block - sizeof(__le32),
52 static int array_block_check(struct dm_block_validator *v,
56 struct array_block *bh_le = dm_block_data(b);
59 if (dm_block_location(b) != le64_to_cpu(bh_le->blocknr)) {
60 DMERR_LIMIT("array_block_check failed: blocknr %llu != wanted %llu",
61 (unsigned long long) le64_to_cpu(bh_le->blocknr),
62 (unsigned long long) dm_block_location(b));
66 csum_disk = cpu_to_le32(dm_bm_checksum(&bh_le->max_entries,
67 size_of_block - sizeof(__le32),
69 if (csum_disk != bh_le->csum) {
70 DMERR_LIMIT("array_block_check failed: csum %u != wanted %u",
71 (unsigned) le32_to_cpu(csum_disk),
72 (unsigned) le32_to_cpu(bh_le->csum));
79 static struct dm_block_validator array_validator = {
81 .prepare_for_write = array_block_prepare_for_write,
82 .check = array_block_check
85 /*----------------------------------------------------------------*/
88 * Functions for manipulating the array blocks.
92 * Returns a pointer to a value within an array block.
94 * index - The index into _this_ specific block.
96 static void *element_at(struct dm_array_info *info, struct array_block *ab,
99 unsigned char *entry = (unsigned char *) (ab + 1);
101 entry += index * info->value_type.size;
107 * Utility function that calls one of the value_type methods on every value
110 static void on_entries(struct dm_array_info *info, struct array_block *ab,
111 void (*fn)(void *, const void *))
113 unsigned i, nr_entries = le32_to_cpu(ab->nr_entries);
115 for (i = 0; i < nr_entries; i++)
116 fn(info->value_type.context, element_at(info, ab, i));
120 * Increment every value in an array block.
122 static void inc_ablock_entries(struct dm_array_info *info, struct array_block *ab)
124 struct dm_btree_value_type *vt = &info->value_type;
127 on_entries(info, ab, vt->inc);
131 * Decrement every value in an array block.
133 static void dec_ablock_entries(struct dm_array_info *info, struct array_block *ab)
135 struct dm_btree_value_type *vt = &info->value_type;
138 on_entries(info, ab, vt->dec);
142 * Each array block can hold this many values.
144 static uint32_t calc_max_entries(size_t value_size, size_t size_of_block)
146 return (size_of_block - sizeof(struct array_block)) / value_size;
150 * Allocate a new array block. The caller will need to unlock block.
152 static int alloc_ablock(struct dm_array_info *info, size_t size_of_block,
153 uint32_t max_entries,
154 struct dm_block **block, struct array_block **ab)
158 r = dm_tm_new_block(info->btree_info.tm, &array_validator, block);
162 (*ab) = dm_block_data(*block);
163 (*ab)->max_entries = cpu_to_le32(max_entries);
164 (*ab)->nr_entries = cpu_to_le32(0);
165 (*ab)->value_size = cpu_to_le32(info->value_type.size);
171 * Pad an array block out with a particular value. Every instance will
172 * cause an increment of the value_type. new_nr must always be more than
173 * the current number of entries.
175 static void fill_ablock(struct dm_array_info *info, struct array_block *ab,
176 const void *value, unsigned new_nr)
180 struct dm_btree_value_type *vt = &info->value_type;
182 BUG_ON(new_nr > le32_to_cpu(ab->max_entries));
183 BUG_ON(new_nr < le32_to_cpu(ab->nr_entries));
185 nr_entries = le32_to_cpu(ab->nr_entries);
186 for (i = nr_entries; i < new_nr; i++) {
188 vt->inc(vt->context, value);
189 memcpy(element_at(info, ab, i), value, vt->size);
191 ab->nr_entries = cpu_to_le32(new_nr);
195 * Remove some entries from the back of an array block. Every value
196 * removed will be decremented. new_nr must be <= the current number of
199 static void trim_ablock(struct dm_array_info *info, struct array_block *ab,
204 struct dm_btree_value_type *vt = &info->value_type;
206 BUG_ON(new_nr > le32_to_cpu(ab->max_entries));
207 BUG_ON(new_nr > le32_to_cpu(ab->nr_entries));
209 nr_entries = le32_to_cpu(ab->nr_entries);
210 for (i = nr_entries; i > new_nr; i--)
212 vt->dec(vt->context, element_at(info, ab, i - 1));
213 ab->nr_entries = cpu_to_le32(new_nr);
217 * Read locks a block, and coerces it to an array block. The caller must
218 * unlock 'block' when finished.
220 static int get_ablock(struct dm_array_info *info, dm_block_t b,
221 struct dm_block **block, struct array_block **ab)
225 r = dm_tm_read_lock(info->btree_info.tm, b, &array_validator, block);
229 *ab = dm_block_data(*block);
234 * Unlocks an array block.
236 static void unlock_ablock(struct dm_array_info *info, struct dm_block *block)
238 dm_tm_unlock(info->btree_info.tm, block);
241 /*----------------------------------------------------------------*/
244 * Btree manipulation.
248 * Looks up an array block in the btree, and then read locks it.
250 * index is the index of the index of the array_block, (ie. the array index
253 static int lookup_ablock(struct dm_array_info *info, dm_block_t root,
254 unsigned index, struct dm_block **block,
255 struct array_block **ab)
258 uint64_t key = index;
261 r = dm_btree_lookup(&info->btree_info, root, &key, &block_le);
265 return get_ablock(info, le64_to_cpu(block_le), block, ab);
269 * Insert an array block into the btree. The block is _not_ unlocked.
271 static int insert_ablock(struct dm_array_info *info, uint64_t index,
272 struct dm_block *block, dm_block_t *root)
274 __le64 block_le = cpu_to_le64(dm_block_location(block));
276 __dm_bless_for_disk(block_le);
277 return dm_btree_insert(&info->btree_info, *root, &index, &block_le, root);
280 /*----------------------------------------------------------------*/
282 static int __shadow_ablock(struct dm_array_info *info, dm_block_t b,
283 struct dm_block **block, struct array_block **ab)
286 int r = dm_tm_shadow_block(info->btree_info.tm, b,
287 &array_validator, block, &inc);
291 *ab = dm_block_data(*block);
293 inc_ablock_entries(info, *ab);
299 * The shadow op will often be a noop. Only insert if it really
302 static int __reinsert_ablock(struct dm_array_info *info, unsigned index,
303 struct dm_block *block, dm_block_t b,
308 if (dm_block_location(block) != b) {
310 * dm_tm_shadow_block will have already decremented the old
311 * block, but it is still referenced by the btree. We
312 * increment to stop the insert decrementing it below zero
313 * when overwriting the old value.
315 dm_tm_inc(info->btree_info.tm, b);
316 r = insert_ablock(info, index, block, root);
323 * Looks up an array block in the btree. Then shadows it, and updates the
324 * btree to point to this new shadow. 'root' is an input/output parameter
325 * for both the current root block, and the new one.
327 static int shadow_ablock(struct dm_array_info *info, dm_block_t *root,
328 unsigned index, struct dm_block **block,
329 struct array_block **ab)
332 uint64_t key = index;
336 r = dm_btree_lookup(&info->btree_info, *root, &key, &block_le);
339 b = le64_to_cpu(block_le);
341 r = __shadow_ablock(info, b, block, ab);
345 return __reinsert_ablock(info, index, *block, b, root);
349 * Allocate an new array block, and fill it with some values.
351 static int insert_new_ablock(struct dm_array_info *info, size_t size_of_block,
352 uint32_t max_entries,
353 unsigned block_index, uint32_t nr,
354 const void *value, dm_block_t *root)
357 struct dm_block *block;
358 struct array_block *ab;
360 r = alloc_ablock(info, size_of_block, max_entries, &block, &ab);
364 fill_ablock(info, ab, value, nr);
365 r = insert_ablock(info, block_index, block, root);
366 unlock_ablock(info, block);
371 static int insert_full_ablocks(struct dm_array_info *info, size_t size_of_block,
372 unsigned begin_block, unsigned end_block,
373 unsigned max_entries, const void *value,
378 for (; !r && begin_block != end_block; begin_block++)
379 r = insert_new_ablock(info, size_of_block, max_entries, begin_block, max_entries, value, root);
385 * There are a bunch of functions involved with resizing an array. This
386 * structure holds information that commonly needed by them. Purely here
387 * to reduce parameter count.
391 * Describes the array.
393 struct dm_array_info *info;
396 * The current root of the array. This gets updated.
401 * Metadata block size. Used to calculate the nr entries in an
404 size_t size_of_block;
407 * Maximum nr entries in an array block.
409 unsigned max_entries;
412 * nr of completely full blocks in the array.
414 * 'old' refers to before the resize, 'new' after.
416 unsigned old_nr_full_blocks, new_nr_full_blocks;
419 * Number of entries in the final block. 0 iff only full blocks in
422 unsigned old_nr_entries_in_last_block, new_nr_entries_in_last_block;
425 * The default value used when growing the array.
431 * Removes a consecutive set of array blocks from the btree. The values
432 * in block are decremented as a side effect of the btree remove.
434 * begin_index - the index of the first array block to remove.
435 * end_index - the one-past-the-end value. ie. this block is not removed.
437 static int drop_blocks(struct resize *resize, unsigned begin_index,
442 while (begin_index != end_index) {
443 uint64_t key = begin_index++;
444 r = dm_btree_remove(&resize->info->btree_info, resize->root,
445 &key, &resize->root);
454 * Calculates how many blocks are needed for the array.
456 static unsigned total_nr_blocks_needed(unsigned nr_full_blocks,
457 unsigned nr_entries_in_last_block)
459 return nr_full_blocks + (nr_entries_in_last_block ? 1 : 0);
465 static int shrink(struct resize *resize)
469 struct dm_block *block;
470 struct array_block *ab;
473 * Lose some blocks from the back?
475 if (resize->new_nr_full_blocks < resize->old_nr_full_blocks) {
476 begin = total_nr_blocks_needed(resize->new_nr_full_blocks,
477 resize->new_nr_entries_in_last_block);
478 end = total_nr_blocks_needed(resize->old_nr_full_blocks,
479 resize->old_nr_entries_in_last_block);
481 r = drop_blocks(resize, begin, end);
487 * Trim the new tail block
489 if (resize->new_nr_entries_in_last_block) {
490 r = shadow_ablock(resize->info, &resize->root,
491 resize->new_nr_full_blocks, &block, &ab);
495 trim_ablock(resize->info, ab, resize->new_nr_entries_in_last_block);
496 unlock_ablock(resize->info, block);
505 static int grow_extend_tail_block(struct resize *resize, uint32_t new_nr_entries)
508 struct dm_block *block;
509 struct array_block *ab;
511 r = shadow_ablock(resize->info, &resize->root,
512 resize->old_nr_full_blocks, &block, &ab);
516 fill_ablock(resize->info, ab, resize->value, new_nr_entries);
517 unlock_ablock(resize->info, block);
522 static int grow_add_tail_block(struct resize *resize)
524 return insert_new_ablock(resize->info, resize->size_of_block,
526 resize->new_nr_full_blocks,
527 resize->new_nr_entries_in_last_block,
528 resize->value, &resize->root);
531 static int grow_needs_more_blocks(struct resize *resize)
534 unsigned old_nr_blocks = resize->old_nr_full_blocks;
536 if (resize->old_nr_entries_in_last_block > 0) {
539 r = grow_extend_tail_block(resize, resize->max_entries);
544 r = insert_full_ablocks(resize->info, resize->size_of_block,
546 resize->new_nr_full_blocks,
547 resize->max_entries, resize->value,
552 if (resize->new_nr_entries_in_last_block)
553 r = grow_add_tail_block(resize);
558 static int grow(struct resize *resize)
560 if (resize->new_nr_full_blocks > resize->old_nr_full_blocks)
561 return grow_needs_more_blocks(resize);
563 else if (resize->old_nr_entries_in_last_block)
564 return grow_extend_tail_block(resize, resize->new_nr_entries_in_last_block);
567 return grow_add_tail_block(resize);
570 /*----------------------------------------------------------------*/
573 * These are the value_type functions for the btree elements, which point
576 static void block_inc(void *context, const void *value)
579 struct dm_array_info *info = context;
581 memcpy(&block_le, value, sizeof(block_le));
582 dm_tm_inc(info->btree_info.tm, le64_to_cpu(block_le));
585 static void block_dec(void *context, const void *value)
591 struct dm_block *block;
592 struct array_block *ab;
593 struct dm_array_info *info = context;
595 memcpy(&block_le, value, sizeof(block_le));
596 b = le64_to_cpu(block_le);
598 r = dm_tm_ref(info->btree_info.tm, b, &ref_count);
600 DMERR_LIMIT("couldn't get reference count for block %llu",
601 (unsigned long long) b);
605 if (ref_count == 1) {
607 * We're about to drop the last reference to this ablock.
608 * So we need to decrement the ref count of the contents.
610 r = get_ablock(info, b, &block, &ab);
612 DMERR_LIMIT("couldn't get array block %llu",
613 (unsigned long long) b);
617 dec_ablock_entries(info, ab);
618 unlock_ablock(info, block);
621 dm_tm_dec(info->btree_info.tm, b);
624 static int block_equal(void *context, const void *value1, const void *value2)
626 return !memcmp(value1, value2, sizeof(__le64));
629 /*----------------------------------------------------------------*/
631 void dm_array_info_init(struct dm_array_info *info,
632 struct dm_transaction_manager *tm,
633 struct dm_btree_value_type *vt)
635 struct dm_btree_value_type *bvt = &info->btree_info.value_type;
637 memcpy(&info->value_type, vt, sizeof(info->value_type));
638 info->btree_info.tm = tm;
639 info->btree_info.levels = 1;
642 bvt->size = sizeof(__le64);
643 bvt->inc = block_inc;
644 bvt->dec = block_dec;
645 bvt->equal = block_equal;
647 EXPORT_SYMBOL_GPL(dm_array_info_init);
649 int dm_array_empty(struct dm_array_info *info, dm_block_t *root)
651 return dm_btree_empty(&info->btree_info, root);
653 EXPORT_SYMBOL_GPL(dm_array_empty);
655 static int array_resize(struct dm_array_info *info, dm_block_t root,
656 uint32_t old_size, uint32_t new_size,
657 const void *value, dm_block_t *new_root)
660 struct resize resize;
662 if (old_size == new_size) {
669 resize.size_of_block = dm_bm_block_size(dm_tm_get_bm(info->btree_info.tm));
670 resize.max_entries = calc_max_entries(info->value_type.size,
671 resize.size_of_block);
673 resize.old_nr_full_blocks = old_size / resize.max_entries;
674 resize.old_nr_entries_in_last_block = old_size % resize.max_entries;
675 resize.new_nr_full_blocks = new_size / resize.max_entries;
676 resize.new_nr_entries_in_last_block = new_size % resize.max_entries;
677 resize.value = value;
679 r = ((new_size > old_size) ? grow : shrink)(&resize);
683 *new_root = resize.root;
687 int dm_array_resize(struct dm_array_info *info, dm_block_t root,
688 uint32_t old_size, uint32_t new_size,
689 const void *value, dm_block_t *new_root)
690 __dm_written_to_disk(value)
692 int r = array_resize(info, root, old_size, new_size, value, new_root);
693 __dm_unbless_for_disk(value);
696 EXPORT_SYMBOL_GPL(dm_array_resize);
698 static int populate_ablock_with_values(struct dm_array_info *info, struct array_block *ab,
699 value_fn fn, void *context, unsigned base, unsigned new_nr)
703 struct dm_btree_value_type *vt = &info->value_type;
705 BUG_ON(le32_to_cpu(ab->nr_entries));
706 BUG_ON(new_nr > le32_to_cpu(ab->max_entries));
708 for (i = 0; i < new_nr; i++) {
709 r = fn(base + i, element_at(info, ab, i), context);
714 vt->inc(vt->context, element_at(info, ab, i));
717 ab->nr_entries = cpu_to_le32(new_nr);
721 int dm_array_new(struct dm_array_info *info, dm_block_t *root,
722 uint32_t size, value_fn fn, void *context)
725 struct dm_block *block;
726 struct array_block *ab;
727 unsigned block_index, end_block, size_of_block, max_entries;
729 r = dm_array_empty(info, root);
733 size_of_block = dm_bm_block_size(dm_tm_get_bm(info->btree_info.tm));
734 max_entries = calc_max_entries(info->value_type.size, size_of_block);
735 end_block = dm_div_up(size, max_entries);
737 for (block_index = 0; block_index != end_block; block_index++) {
738 r = alloc_ablock(info, size_of_block, max_entries, &block, &ab);
742 r = populate_ablock_with_values(info, ab, fn, context,
743 block_index * max_entries,
744 min(max_entries, size));
746 unlock_ablock(info, block);
750 r = insert_ablock(info, block_index, block, root);
751 unlock_ablock(info, block);
760 EXPORT_SYMBOL_GPL(dm_array_new);
762 int dm_array_del(struct dm_array_info *info, dm_block_t root)
764 return dm_btree_del(&info->btree_info, root);
766 EXPORT_SYMBOL_GPL(dm_array_del);
768 int dm_array_get_value(struct dm_array_info *info, dm_block_t root,
769 uint32_t index, void *value_le)
772 struct dm_block *block;
773 struct array_block *ab;
774 size_t size_of_block;
775 unsigned entry, max_entries;
777 size_of_block = dm_bm_block_size(dm_tm_get_bm(info->btree_info.tm));
778 max_entries = calc_max_entries(info->value_type.size, size_of_block);
780 r = lookup_ablock(info, root, index / max_entries, &block, &ab);
784 entry = index % max_entries;
785 if (entry >= le32_to_cpu(ab->nr_entries))
788 memcpy(value_le, element_at(info, ab, entry),
789 info->value_type.size);
791 unlock_ablock(info, block);
794 EXPORT_SYMBOL_GPL(dm_array_get_value);
796 static int array_set_value(struct dm_array_info *info, dm_block_t root,
797 uint32_t index, const void *value, dm_block_t *new_root)
800 struct dm_block *block;
801 struct array_block *ab;
802 size_t size_of_block;
803 unsigned max_entries;
806 struct dm_btree_value_type *vt = &info->value_type;
808 size_of_block = dm_bm_block_size(dm_tm_get_bm(info->btree_info.tm));
809 max_entries = calc_max_entries(info->value_type.size, size_of_block);
811 r = shadow_ablock(info, &root, index / max_entries, &block, &ab);
816 entry = index % max_entries;
817 if (entry >= le32_to_cpu(ab->nr_entries)) {
822 old_value = element_at(info, ab, entry);
824 (!vt->equal || !vt->equal(vt->context, old_value, value))) {
825 vt->dec(vt->context, old_value);
827 vt->inc(vt->context, value);
830 memcpy(old_value, value, info->value_type.size);
833 unlock_ablock(info, block);
837 int dm_array_set_value(struct dm_array_info *info, dm_block_t root,
838 uint32_t index, const void *value, dm_block_t *new_root)
839 __dm_written_to_disk(value)
843 r = array_set_value(info, root, index, value, new_root);
844 __dm_unbless_for_disk(value);
847 EXPORT_SYMBOL_GPL(dm_array_set_value);
850 struct dm_array_info *info;
851 int (*fn)(void *context, uint64_t key, void *leaf);
855 static int walk_ablock(void *context, uint64_t *keys, void *leaf)
857 struct walk_info *wi = context;
862 unsigned nr_entries, max_entries;
863 struct dm_block *block;
864 struct array_block *ab;
866 memcpy(&block_le, leaf, sizeof(block_le));
867 r = get_ablock(wi->info, le64_to_cpu(block_le), &block, &ab);
871 max_entries = le32_to_cpu(ab->max_entries);
872 nr_entries = le32_to_cpu(ab->nr_entries);
873 for (i = 0; i < nr_entries; i++) {
874 r = wi->fn(wi->context, keys[0] * max_entries + i,
875 element_at(wi->info, ab, i));
881 unlock_ablock(wi->info, block);
885 int dm_array_walk(struct dm_array_info *info, dm_block_t root,
886 int (*fn)(void *, uint64_t key, void *leaf),
893 wi.context = context;
895 return dm_btree_walk(&info->btree_info, root, walk_ablock, &wi);
897 EXPORT_SYMBOL_GPL(dm_array_walk);
899 /*----------------------------------------------------------------*/
901 static int load_ablock(struct dm_array_cursor *c)
908 unlock_ablock(c->info, c->block);
914 r = dm_btree_cursor_get_value(&c->cursor, &key, &value_le);
916 DMERR("dm_btree_cursor_get_value failed");
917 dm_btree_cursor_end(&c->cursor);
920 r = get_ablock(c->info, le64_to_cpu(value_le), &c->block, &c->ab);
922 DMERR("get_ablock failed");
923 dm_btree_cursor_end(&c->cursor);
930 int dm_array_cursor_begin(struct dm_array_info *info, dm_block_t root,
931 struct dm_array_cursor *c)
935 memset(c, 0, sizeof(*c));
937 r = dm_btree_cursor_begin(&info->btree_info, root, true, &c->cursor);
939 DMERR("couldn't create btree cursor");
943 return load_ablock(c);
945 EXPORT_SYMBOL_GPL(dm_array_cursor_begin);
947 void dm_array_cursor_end(struct dm_array_cursor *c)
950 unlock_ablock(c->info, c->block);
951 dm_btree_cursor_end(&c->cursor);
954 EXPORT_SYMBOL_GPL(dm_array_cursor_end);
956 int dm_array_cursor_next(struct dm_array_cursor *c)
965 if (c->index >= le32_to_cpu(c->ab->nr_entries)) {
966 r = dm_btree_cursor_next(&c->cursor);
977 EXPORT_SYMBOL_GPL(dm_array_cursor_next);
979 int dm_array_cursor_skip(struct dm_array_cursor *c, uint32_t count)
984 uint32_t remaining = le32_to_cpu(c->ab->nr_entries) - c->index;
986 if (count < remaining) {
992 r = dm_array_cursor_next(c);
998 EXPORT_SYMBOL_GPL(dm_array_cursor_skip);
1000 void dm_array_cursor_get_value(struct dm_array_cursor *c, void **value_le)
1002 *value_le = element_at(c->info, c->ab, c->index);
1004 EXPORT_SYMBOL_GPL(dm_array_cursor_get_value);
1006 /*----------------------------------------------------------------*/