1 // SPDX-License-Identifier: GPL-2.0-only
3 * Copyright (C) 2019 Arrikto, Inc. All Rights Reserved.
8 #include <linux/slab.h>
9 #include <linux/rwsem.h>
10 #include <linux/bitops.h>
11 #include <linux/bitmap.h>
12 #include <linux/device-mapper.h>
14 #include "persistent-data/dm-bitset.h"
15 #include "persistent-data/dm-space-map.h"
16 #include "persistent-data/dm-block-manager.h"
17 #include "persistent-data/dm-transaction-manager.h"
19 #include "dm-clone-metadata.h"
21 #define DM_MSG_PREFIX "clone metadata"
23 #define SUPERBLOCK_LOCATION 0
24 #define SUPERBLOCK_MAGIC 0x8af27f64
25 #define SUPERBLOCK_CSUM_XOR 257649492
27 #define DM_CLONE_MAX_CONCURRENT_LOCKS 5
31 /* Min and max dm-clone metadata versions supported */
32 #define DM_CLONE_MIN_METADATA_VERSION 1
33 #define DM_CLONE_MAX_METADATA_VERSION 1
36 * On-disk metadata layout
38 struct superblock_disk {
47 __u8 metadata_space_map_root[SPACE_MAP_ROOT_SIZE];
56 * Region and Dirty bitmaps.
58 * dm-clone logically splits the source and destination devices in regions of
59 * fixed size. The destination device's regions are gradually hydrated, i.e.,
60 * we copy (clone) the source's regions to the destination device. Eventually,
61 * all regions will get hydrated and all I/O will be served from the
64 * We maintain an on-disk bitmap which tracks the state of each of the
65 * destination device's regions, i.e., whether they are hydrated or not.
67 * To save constantly doing look ups on disk we keep an in core copy of the
68 * on-disk bitmap, the region_map.
70 * To further reduce metadata I/O overhead we use a second bitmap, the dmap
71 * (dirty bitmap), which tracks the dirty words, i.e. longs, of the region_map.
73 * When a region finishes hydrating dm-clone calls
74 * dm_clone_set_region_hydrated(), or for discard requests
75 * dm_clone_cond_set_range(), which sets the corresponding bits in region_map
78 * During a metadata commit we scan the dmap for dirty region_map words (longs)
79 * and update accordingly the on-disk metadata. Thus, we don't have to flush to
80 * disk the whole region_map. We can just flush the dirty region_map words.
82 * We use a dirty bitmap, which is smaller than the original region_map, to
83 * reduce the amount of memory accesses during a metadata commit. As dm-bitset
84 * accesses the on-disk bitmap in 64-bit word granularity, there is no
85 * significant benefit in tracking the dirty region_map bits with a smaller
88 * We could update directly the on-disk bitmap, when dm-clone calls either
89 * dm_clone_set_region_hydrated() or dm_clone_cond_set_range(), buts this
90 * inserts significant metadata I/O overhead in dm-clone's I/O path. Also, as
91 * these two functions don't block, we can call them in interrupt context,
92 * e.g., in a hooked overwrite bio's completion routine, and further reduce the
93 * I/O completion latency.
95 * We maintain two dirty bitmaps. During a metadata commit we atomically swap
96 * the currently used dmap with the unused one. This allows the metadata update
97 * functions to run concurrently with an ongoing commit.
100 unsigned long *dirty_words;
101 unsigned int changed;
104 struct dm_clone_metadata {
105 /* The metadata block device */
106 struct block_device *bdev;
108 sector_t target_size;
109 sector_t region_size;
110 unsigned long nr_regions;
111 unsigned long nr_words;
113 /* Spinlock protecting the region and dirty bitmaps. */
114 spinlock_t bitmap_lock;
115 struct dirty_map dmap[2];
116 struct dirty_map *current_dmap;
119 * In core copy of the on-disk bitmap to save constantly doing look ups
122 unsigned long *region_map;
124 /* Protected by bitmap_lock */
125 unsigned int read_only;
127 struct dm_block_manager *bm;
128 struct dm_space_map *sm;
129 struct dm_transaction_manager *tm;
131 struct rw_semaphore lock;
133 struct dm_disk_bitset bitset_info;
134 dm_block_t bitset_root;
137 * Reading the space map root can fail, so we read it into this
138 * buffer before the superblock is locked and updated.
140 __u8 metadata_space_map_root[SPACE_MAP_ROOT_SIZE];
142 bool hydration_done:1;
146 /*---------------------------------------------------------------------------*/
149 * Superblock validation.
151 static void sb_prepare_for_write(struct dm_block_validator *v,
152 struct dm_block *b, size_t sb_block_size)
154 struct superblock_disk *sb;
157 sb = dm_block_data(b);
158 sb->blocknr = cpu_to_le64(dm_block_location(b));
160 csum = dm_bm_checksum(&sb->flags, sb_block_size - sizeof(__le32),
161 SUPERBLOCK_CSUM_XOR);
162 sb->csum = cpu_to_le32(csum);
165 static int sb_check(struct dm_block_validator *v, struct dm_block *b,
166 size_t sb_block_size)
168 struct superblock_disk *sb;
169 u32 csum, metadata_version;
171 sb = dm_block_data(b);
173 if (dm_block_location(b) != le64_to_cpu(sb->blocknr)) {
174 DMERR("Superblock check failed: blocknr %llu, expected %llu",
175 le64_to_cpu(sb->blocknr),
176 (unsigned long long)dm_block_location(b));
180 if (le64_to_cpu(sb->magic) != SUPERBLOCK_MAGIC) {
181 DMERR("Superblock check failed: magic %llu, expected %llu",
182 le64_to_cpu(sb->magic),
183 (unsigned long long)SUPERBLOCK_MAGIC);
187 csum = dm_bm_checksum(&sb->flags, sb_block_size - sizeof(__le32),
188 SUPERBLOCK_CSUM_XOR);
189 if (sb->csum != cpu_to_le32(csum)) {
190 DMERR("Superblock check failed: checksum %u, expected %u",
191 csum, le32_to_cpu(sb->csum));
195 /* Check metadata version */
196 metadata_version = le32_to_cpu(sb->version);
197 if (metadata_version < DM_CLONE_MIN_METADATA_VERSION ||
198 metadata_version > DM_CLONE_MAX_METADATA_VERSION) {
199 DMERR("Clone metadata version %u found, but only versions between %u and %u supported.",
200 metadata_version, DM_CLONE_MIN_METADATA_VERSION,
201 DM_CLONE_MAX_METADATA_VERSION);
208 static struct dm_block_validator sb_validator = {
209 .name = "superblock",
210 .prepare_for_write = sb_prepare_for_write,
215 * Check if the superblock is formatted or not. We consider the superblock to
216 * be formatted in case we find non-zero bytes in it.
218 static int __superblock_all_zeroes(struct dm_block_manager *bm, bool *formatted)
221 unsigned int i, nr_words;
222 struct dm_block *sblock;
223 __le64 *data_le, zero = cpu_to_le64(0);
226 * We don't use a validator here because the superblock could be all
229 r = dm_bm_read_lock(bm, SUPERBLOCK_LOCATION, NULL, &sblock);
231 DMERR("Failed to read_lock superblock");
235 data_le = dm_block_data(sblock);
238 /* This assumes that the block size is a multiple of 8 bytes */
239 BUG_ON(dm_bm_block_size(bm) % sizeof(__le64));
240 nr_words = dm_bm_block_size(bm) / sizeof(__le64);
241 for (i = 0; i < nr_words; i++) {
242 if (data_le[i] != zero) {
248 dm_bm_unlock(sblock);
253 /*---------------------------------------------------------------------------*/
256 * Low-level metadata handling.
258 static inline int superblock_read_lock(struct dm_clone_metadata *cmd,
259 struct dm_block **sblock)
261 return dm_bm_read_lock(cmd->bm, SUPERBLOCK_LOCATION, &sb_validator, sblock);
264 static inline int superblock_write_lock(struct dm_clone_metadata *cmd,
265 struct dm_block **sblock)
267 return dm_bm_write_lock(cmd->bm, SUPERBLOCK_LOCATION, &sb_validator, sblock);
270 static inline int superblock_write_lock_zero(struct dm_clone_metadata *cmd,
271 struct dm_block **sblock)
273 return dm_bm_write_lock_zero(cmd->bm, SUPERBLOCK_LOCATION, &sb_validator, sblock);
276 static int __copy_sm_root(struct dm_clone_metadata *cmd)
281 r = dm_sm_root_size(cmd->sm, &root_size);
285 return dm_sm_copy_root(cmd->sm, &cmd->metadata_space_map_root, root_size);
288 /* Save dm-clone metadata in superblock */
289 static void __prepare_superblock(struct dm_clone_metadata *cmd,
290 struct superblock_disk *sb)
292 sb->flags = cpu_to_le32(0UL);
294 /* FIXME: UUID is currently unused */
295 memset(sb->uuid, 0, sizeof(sb->uuid));
297 sb->magic = cpu_to_le64(SUPERBLOCK_MAGIC);
298 sb->version = cpu_to_le32(DM_CLONE_MAX_METADATA_VERSION);
300 /* Save the metadata space_map root */
301 memcpy(&sb->metadata_space_map_root, &cmd->metadata_space_map_root,
302 sizeof(cmd->metadata_space_map_root));
304 sb->region_size = cpu_to_le64(cmd->region_size);
305 sb->target_size = cpu_to_le64(cmd->target_size);
306 sb->bitset_root = cpu_to_le64(cmd->bitset_root);
309 static int __open_metadata(struct dm_clone_metadata *cmd)
312 struct dm_block *sblock;
313 struct superblock_disk *sb;
315 r = superblock_read_lock(cmd, &sblock);
318 DMERR("Failed to read_lock superblock");
322 sb = dm_block_data(sblock);
324 /* Verify that target_size and region_size haven't changed. */
325 if (cmd->region_size != le64_to_cpu(sb->region_size) ||
326 cmd->target_size != le64_to_cpu(sb->target_size)) {
327 DMERR("Region and/or target size don't match the ones in metadata");
332 r = dm_tm_open_with_sm(cmd->bm, SUPERBLOCK_LOCATION,
333 sb->metadata_space_map_root,
334 sizeof(sb->metadata_space_map_root),
338 DMERR("dm_tm_open_with_sm failed");
342 dm_disk_bitset_init(cmd->tm, &cmd->bitset_info);
343 cmd->bitset_root = le64_to_cpu(sb->bitset_root);
346 dm_bm_unlock(sblock);
351 static int __format_metadata(struct dm_clone_metadata *cmd)
354 struct dm_block *sblock;
355 struct superblock_disk *sb;
357 r = dm_tm_create_with_sm(cmd->bm, SUPERBLOCK_LOCATION, &cmd->tm, &cmd->sm);
359 DMERR("Failed to create transaction manager");
363 dm_disk_bitset_init(cmd->tm, &cmd->bitset_info);
365 r = dm_bitset_empty(&cmd->bitset_info, &cmd->bitset_root);
367 DMERR("Failed to create empty on-disk bitset");
371 r = dm_bitset_resize(&cmd->bitset_info, cmd->bitset_root, 0,
372 cmd->nr_regions, false, &cmd->bitset_root);
374 DMERR("Failed to resize on-disk bitset to %lu entries", cmd->nr_regions);
378 /* Flush to disk all blocks, except the superblock */
379 r = dm_tm_pre_commit(cmd->tm);
381 DMERR("dm_tm_pre_commit failed");
385 r = __copy_sm_root(cmd);
387 DMERR("__copy_sm_root failed");
391 r = superblock_write_lock_zero(cmd, &sblock);
393 DMERR("Failed to write_lock superblock");
397 sb = dm_block_data(sblock);
398 __prepare_superblock(cmd, sb);
399 r = dm_tm_commit(cmd->tm, sblock);
401 DMERR("Failed to commit superblock");
408 dm_sm_destroy(cmd->sm);
409 dm_tm_destroy(cmd->tm);
414 static int __open_or_format_metadata(struct dm_clone_metadata *cmd, bool may_format_device)
417 bool formatted = false;
419 r = __superblock_all_zeroes(cmd->bm, &formatted);
424 return may_format_device ? __format_metadata(cmd) : -EPERM;
426 return __open_metadata(cmd);
429 static int __create_persistent_data_structures(struct dm_clone_metadata *cmd,
430 bool may_format_device)
434 /* Create block manager */
435 cmd->bm = dm_block_manager_create(cmd->bdev,
436 DM_CLONE_METADATA_BLOCK_SIZE << SECTOR_SHIFT,
437 DM_CLONE_MAX_CONCURRENT_LOCKS);
438 if (IS_ERR(cmd->bm)) {
439 DMERR("Failed to create block manager");
440 return PTR_ERR(cmd->bm);
443 r = __open_or_format_metadata(cmd, may_format_device);
445 dm_block_manager_destroy(cmd->bm);
450 static void __destroy_persistent_data_structures(struct dm_clone_metadata *cmd)
452 dm_sm_destroy(cmd->sm);
453 dm_tm_destroy(cmd->tm);
454 dm_block_manager_destroy(cmd->bm);
457 /*---------------------------------------------------------------------------*/
459 static size_t bitmap_size(unsigned long nr_bits)
461 return BITS_TO_LONGS(nr_bits) * sizeof(long);
464 static int dirty_map_init(struct dm_clone_metadata *cmd)
466 cmd->dmap[0].changed = 0;
467 cmd->dmap[0].dirty_words = kvzalloc(bitmap_size(cmd->nr_words), GFP_KERNEL);
469 if (!cmd->dmap[0].dirty_words) {
470 DMERR("Failed to allocate dirty bitmap");
474 cmd->dmap[1].changed = 0;
475 cmd->dmap[1].dirty_words = kvzalloc(bitmap_size(cmd->nr_words), GFP_KERNEL);
477 if (!cmd->dmap[1].dirty_words) {
478 DMERR("Failed to allocate dirty bitmap");
479 kvfree(cmd->dmap[0].dirty_words);
483 cmd->current_dmap = &cmd->dmap[0];
488 static void dirty_map_exit(struct dm_clone_metadata *cmd)
490 kvfree(cmd->dmap[0].dirty_words);
491 kvfree(cmd->dmap[1].dirty_words);
494 static int __load_bitset_in_core(struct dm_clone_metadata *cmd)
498 struct dm_bitset_cursor c;
500 /* Flush bitset cache */
501 r = dm_bitset_flush(&cmd->bitset_info, cmd->bitset_root, &cmd->bitset_root);
505 r = dm_bitset_cursor_begin(&cmd->bitset_info, cmd->bitset_root, cmd->nr_regions, &c);
510 if (dm_bitset_cursor_get_value(&c))
511 __set_bit(i, cmd->region_map);
513 __clear_bit(i, cmd->region_map);
515 if (i >= (cmd->nr_regions - 1))
518 r = dm_bitset_cursor_next(&c);
524 dm_bitset_cursor_end(&c);
529 struct dm_clone_metadata *dm_clone_metadata_open(struct block_device *bdev,
530 sector_t target_size,
531 sector_t region_size)
534 struct dm_clone_metadata *cmd;
536 cmd = kzalloc(sizeof(*cmd), GFP_KERNEL);
538 DMERR("Failed to allocate memory for dm-clone metadata");
539 return ERR_PTR(-ENOMEM);
543 cmd->target_size = target_size;
544 cmd->region_size = region_size;
545 cmd->nr_regions = dm_sector_div_up(cmd->target_size, cmd->region_size);
546 cmd->nr_words = BITS_TO_LONGS(cmd->nr_regions);
548 init_rwsem(&cmd->lock);
549 spin_lock_init(&cmd->bitmap_lock);
551 cmd->fail_io = false;
552 cmd->hydration_done = false;
554 cmd->region_map = kvmalloc(bitmap_size(cmd->nr_regions), GFP_KERNEL);
555 if (!cmd->region_map) {
556 DMERR("Failed to allocate memory for region bitmap");
561 r = __create_persistent_data_structures(cmd, true);
563 goto out_with_region_map;
565 r = __load_bitset_in_core(cmd);
567 DMERR("Failed to load on-disk region map");
571 r = dirty_map_init(cmd);
575 if (bitmap_full(cmd->region_map, cmd->nr_regions))
576 cmd->hydration_done = true;
581 __destroy_persistent_data_structures(cmd);
584 kvfree(cmd->region_map);
592 void dm_clone_metadata_close(struct dm_clone_metadata *cmd)
595 __destroy_persistent_data_structures(cmd);
598 kvfree(cmd->region_map);
602 bool dm_clone_is_hydration_done(struct dm_clone_metadata *cmd)
604 return cmd->hydration_done;
607 bool dm_clone_is_region_hydrated(struct dm_clone_metadata *cmd, unsigned long region_nr)
609 return dm_clone_is_hydration_done(cmd) || test_bit(region_nr, cmd->region_map);
612 bool dm_clone_is_range_hydrated(struct dm_clone_metadata *cmd,
613 unsigned long start, unsigned long nr_regions)
617 if (dm_clone_is_hydration_done(cmd))
620 bit = find_next_zero_bit(cmd->region_map, cmd->nr_regions, start);
622 return (bit >= (start + nr_regions));
625 unsigned long dm_clone_nr_of_hydrated_regions(struct dm_clone_metadata *cmd)
627 return bitmap_weight(cmd->region_map, cmd->nr_regions);
630 unsigned long dm_clone_find_next_unhydrated_region(struct dm_clone_metadata *cmd,
633 return find_next_zero_bit(cmd->region_map, cmd->nr_regions, start);
636 static int __update_metadata_word(struct dm_clone_metadata *cmd, unsigned long word)
639 unsigned long index = word * BITS_PER_LONG;
640 unsigned long max_index = min(cmd->nr_regions, (word + 1) * BITS_PER_LONG);
642 while (index < max_index) {
643 if (test_bit(index, cmd->region_map)) {
644 r = dm_bitset_set_bit(&cmd->bitset_info, cmd->bitset_root,
645 index, &cmd->bitset_root);
648 DMERR("dm_bitset_set_bit failed");
658 static int __metadata_commit(struct dm_clone_metadata *cmd)
661 struct dm_block *sblock;
662 struct superblock_disk *sb;
664 /* Flush bitset cache */
665 r = dm_bitset_flush(&cmd->bitset_info, cmd->bitset_root, &cmd->bitset_root);
667 DMERR("dm_bitset_flush failed");
671 /* Flush to disk all blocks, except the superblock */
672 r = dm_tm_pre_commit(cmd->tm);
674 DMERR("dm_tm_pre_commit failed");
678 /* Save the space map root in cmd->metadata_space_map_root */
679 r = __copy_sm_root(cmd);
681 DMERR("__copy_sm_root failed");
685 /* Lock the superblock */
686 r = superblock_write_lock_zero(cmd, &sblock);
688 DMERR("Failed to write_lock superblock");
692 /* Save the metadata in superblock */
693 sb = dm_block_data(sblock);
694 __prepare_superblock(cmd, sb);
696 /* Unlock superblock and commit it to disk */
697 r = dm_tm_commit(cmd->tm, sblock);
699 DMERR("Failed to commit superblock");
704 * FIXME: Find a more efficient way to check if the hydration is done.
706 if (bitmap_full(cmd->region_map, cmd->nr_regions))
707 cmd->hydration_done = true;
712 static int __flush_dmap(struct dm_clone_metadata *cmd, struct dirty_map *dmap)
715 unsigned long word, flags;
719 word = find_next_bit(dmap->dirty_words, cmd->nr_words, word);
721 if (word == cmd->nr_words)
724 r = __update_metadata_word(cmd, word);
729 __clear_bit(word, dmap->dirty_words);
731 } while (word < cmd->nr_words);
733 r = __metadata_commit(cmd);
738 /* Update the changed flag */
739 spin_lock_irqsave(&cmd->bitmap_lock, flags);
741 spin_unlock_irqrestore(&cmd->bitmap_lock, flags);
746 int dm_clone_metadata_commit(struct dm_clone_metadata *cmd)
750 struct dirty_map *dmap, *next_dmap;
752 down_write(&cmd->lock);
754 if (cmd->fail_io || dm_bm_is_read_only(cmd->bm))
757 /* Get current dirty bitmap */
758 dmap = cmd->current_dmap;
760 /* Get next dirty bitmap */
761 next_dmap = (dmap == &cmd->dmap[0]) ? &cmd->dmap[1] : &cmd->dmap[0];
764 * The last commit failed, so we don't have a clean dirty-bitmap to
767 if (WARN_ON(next_dmap->changed)) {
772 /* Swap dirty bitmaps */
773 spin_lock_irqsave(&cmd->bitmap_lock, flags);
774 cmd->current_dmap = next_dmap;
775 spin_unlock_irqrestore(&cmd->bitmap_lock, flags);
778 * No one is accessing the old dirty bitmap anymore, so we can flush
781 r = __flush_dmap(cmd, dmap);
783 up_write(&cmd->lock);
788 int dm_clone_set_region_hydrated(struct dm_clone_metadata *cmd, unsigned long region_nr)
791 struct dirty_map *dmap;
792 unsigned long word, flags;
794 word = region_nr / BITS_PER_LONG;
796 spin_lock_irqsave(&cmd->bitmap_lock, flags);
798 if (cmd->read_only) {
803 dmap = cmd->current_dmap;
805 __set_bit(word, dmap->dirty_words);
806 __set_bit(region_nr, cmd->region_map);
810 spin_unlock_irqrestore(&cmd->bitmap_lock, flags);
815 int dm_clone_cond_set_range(struct dm_clone_metadata *cmd, unsigned long start,
816 unsigned long nr_regions)
819 struct dirty_map *dmap;
820 unsigned long word, region_nr, flags;
822 spin_lock_irqsave(&cmd->bitmap_lock, flags);
824 if (cmd->read_only) {
829 dmap = cmd->current_dmap;
830 for (region_nr = start; region_nr < (start + nr_regions); region_nr++) {
831 if (!test_bit(region_nr, cmd->region_map)) {
832 word = region_nr / BITS_PER_LONG;
833 __set_bit(word, dmap->dirty_words);
834 __set_bit(region_nr, cmd->region_map);
839 spin_unlock_irqrestore(&cmd->bitmap_lock, flags);
845 * WARNING: This must not be called concurrently with either
846 * dm_clone_set_region_hydrated() or dm_clone_cond_set_range(), as it changes
847 * cmd->region_map without taking the cmd->bitmap_lock spinlock. The only
848 * exception is after setting the metadata to read-only mode, using
849 * dm_clone_metadata_set_read_only().
851 * We don't take the spinlock because __load_bitset_in_core() does I/O, so it
854 int dm_clone_reload_in_core_bitset(struct dm_clone_metadata *cmd)
858 down_write(&cmd->lock);
863 r = __load_bitset_in_core(cmd);
865 up_write(&cmd->lock);
870 bool dm_clone_changed_this_transaction(struct dm_clone_metadata *cmd)
875 spin_lock_irqsave(&cmd->bitmap_lock, flags);
876 r = cmd->dmap[0].changed || cmd->dmap[1].changed;
877 spin_unlock_irqrestore(&cmd->bitmap_lock, flags);
882 int dm_clone_metadata_abort(struct dm_clone_metadata *cmd)
886 down_write(&cmd->lock);
888 if (cmd->fail_io || dm_bm_is_read_only(cmd->bm))
891 __destroy_persistent_data_structures(cmd);
893 r = __create_persistent_data_structures(cmd, false);
895 /* If something went wrong we can neither write nor read the metadata */
899 up_write(&cmd->lock);
904 void dm_clone_metadata_set_read_only(struct dm_clone_metadata *cmd)
908 down_write(&cmd->lock);
910 spin_lock_irqsave(&cmd->bitmap_lock, flags);
912 spin_unlock_irqrestore(&cmd->bitmap_lock, flags);
915 dm_bm_set_read_only(cmd->bm);
917 up_write(&cmd->lock);
920 void dm_clone_metadata_set_read_write(struct dm_clone_metadata *cmd)
924 down_write(&cmd->lock);
926 spin_lock_irqsave(&cmd->bitmap_lock, flags);
928 spin_unlock_irqrestore(&cmd->bitmap_lock, flags);
931 dm_bm_set_read_write(cmd->bm);
933 up_write(&cmd->lock);
936 int dm_clone_get_free_metadata_block_count(struct dm_clone_metadata *cmd,
941 down_read(&cmd->lock);
944 r = dm_sm_get_nr_free(cmd->sm, result);
951 int dm_clone_get_metadata_dev_size(struct dm_clone_metadata *cmd,
956 down_read(&cmd->lock);
959 r = dm_sm_get_nr_blocks(cmd->sm, result);