2 * Copyright (C) 2001-2002 Sistina Software (UK) Limited.
3 * Copyright (C) 2006-2008 Red Hat GmbH
5 * This file is released under the GPL.
8 #include "dm-exception-store.h"
11 #include <linux/pagemap.h>
12 #include <linux/vmalloc.h>
13 #include <linux/export.h>
14 #include <linux/slab.h>
15 #include <linux/dm-io.h>
17 #define DM_MSG_PREFIX "persistent snapshot"
18 #define DM_CHUNK_SIZE_DEFAULT_SECTORS 32 /* 16KB */
20 /*-----------------------------------------------------------------
21 * Persistent snapshots, by persistent we mean that the snapshot
22 * will survive a reboot.
23 *---------------------------------------------------------------*/
26 * We need to store a record of which parts of the origin have
27 * been copied to the snapshot device. The snapshot code
28 * requires that we copy exception chunks to chunk aligned areas
29 * of the COW store. It makes sense therefore, to store the
30 * metadata in chunk size blocks.
32 * There is no backward or forward compatibility implemented,
33 * snapshots with different disk versions than the kernel will
34 * not be usable. It is expected that "lvcreate" will blank out
35 * the start of a fresh COW device before calling the snapshot
38 * The first chunk of the COW device just contains the header.
39 * After this there is a chunk filled with exception metadata,
40 * followed by as many exception chunks as can fit in the
43 * All on disk structures are in little-endian format. The end
44 * of the exceptions info is indicated by an exception with a
45 * new_chunk of 0, which is invalid since it would point to the
50 * Magic for persistent snapshots: "SnAp" - Feeble isn't it.
52 #define SNAP_MAGIC 0x70416e53
55 * The on-disk version of the metadata.
57 #define SNAPSHOT_DISK_VERSION 1
59 #define NUM_SNAPSHOT_HDR_CHUNKS 1
65 * Is this snapshot valid. There is no way of recovering
66 * an invalid snapshot.
71 * Simple, incrementing version. no backward
80 struct disk_exception {
85 struct core_exception {
90 struct commit_callback {
91 void (*callback)(void *, int success);
96 * The top level structure for a persistent exception store.
99 struct dm_exception_store *store;
102 uint32_t exceptions_per_area;
105 * Now that we have an asynchronous kcopyd there is no
106 * need for large chunk sizes, so it wont hurt to have a
107 * whole chunks worth of metadata in memory at once.
112 * An area of zeros used to clear the next area.
117 * An area used for header. The header can be written
118 * concurrently with metadata (when invalidating the snapshot),
119 * so it needs a separate buffer.
124 * Used to keep track of which metadata area the data in
127 chunk_t current_area;
130 * The next free chunk for an exception.
132 * When creating exceptions, all the chunks here and above are
133 * free. It holds the next chunk to be allocated. On rare
134 * occasions (e.g. after a system crash) holes can be left in
135 * the exception store because chunks can be committed out of
138 * When merging exceptions, it does not necessarily mean all the
139 * chunks here and above are free. It holds the value it would
140 * have held if all chunks had been committed in order of
141 * allocation. Consequently the value may occasionally be
142 * slightly too low, but since it's only used for 'status' and
143 * it can never reach its minimum value too early this doesn't
150 * The index of next free exception in the current
153 uint32_t current_committed;
155 atomic_t pending_count;
156 uint32_t callback_count;
157 struct commit_callback *callbacks;
158 struct dm_io_client *io_client;
160 struct workqueue_struct *metadata_wq;
163 static int alloc_area(struct pstore *ps)
168 len = ps->store->chunk_size << SECTOR_SHIFT;
171 * Allocate the chunk_size block of memory that will hold
172 * a single metadata area.
174 ps->area = vmalloc(len);
178 ps->zero_area = vzalloc(len);
182 ps->header_area = vmalloc(len);
183 if (!ps->header_area)
184 goto err_header_area;
189 vfree(ps->zero_area);
198 static void free_area(struct pstore *ps)
205 vfree(ps->zero_area);
206 ps->zero_area = NULL;
209 vfree(ps->header_area);
210 ps->header_area = NULL;
214 struct dm_io_region *where;
215 struct dm_io_request *io_req;
216 struct work_struct work;
220 static void do_metadata(struct work_struct *work)
222 struct mdata_req *req = container_of(work, struct mdata_req, work);
224 req->result = dm_io(req->io_req, 1, req->where, NULL);
228 * Read or write a chunk aligned and sized block of data from a device.
230 static int chunk_io(struct pstore *ps, void *area, chunk_t chunk, int rw,
233 struct dm_io_region where = {
234 .bdev = dm_snap_cow(ps->store->snap)->bdev,
235 .sector = ps->store->chunk_size * chunk,
236 .count = ps->store->chunk_size,
238 struct dm_io_request io_req = {
240 .mem.type = DM_IO_VMA,
242 .client = ps->io_client,
245 struct mdata_req req;
248 return dm_io(&io_req, 1, &where, NULL);
251 req.io_req = &io_req;
254 * Issue the synchronous I/O from a different thread
255 * to avoid generic_make_request recursion.
257 INIT_WORK_ONSTACK(&req.work, do_metadata);
258 queue_work(ps->metadata_wq, &req.work);
259 flush_workqueue(ps->metadata_wq);
260 destroy_work_on_stack(&req.work);
266 * Convert a metadata area index to a chunk index.
268 static chunk_t area_location(struct pstore *ps, chunk_t area)
270 return NUM_SNAPSHOT_HDR_CHUNKS + ((ps->exceptions_per_area + 1) * area);
273 static void skip_metadata(struct pstore *ps)
275 uint32_t stride = ps->exceptions_per_area + 1;
276 chunk_t next_free = ps->next_free;
277 if (sector_div(next_free, stride) == NUM_SNAPSHOT_HDR_CHUNKS)
282 * Read or write a metadata area. Remembering to skip the first
283 * chunk which holds the header.
285 static int area_io(struct pstore *ps, int rw)
290 chunk = area_location(ps, ps->current_area);
292 r = chunk_io(ps, ps->area, chunk, rw, 0);
299 static void zero_memory_area(struct pstore *ps)
301 memset(ps->area, 0, ps->store->chunk_size << SECTOR_SHIFT);
304 static int zero_disk_area(struct pstore *ps, chunk_t area)
306 return chunk_io(ps, ps->zero_area, area_location(ps, area), WRITE, 0);
309 static int read_header(struct pstore *ps, int *new_snapshot)
312 struct disk_header *dh;
314 int chunk_size_supplied = 1;
318 * Use default chunk size (or logical_block_size, if larger)
321 if (!ps->store->chunk_size) {
322 ps->store->chunk_size = max(DM_CHUNK_SIZE_DEFAULT_SECTORS,
323 bdev_logical_block_size(dm_snap_cow(ps->store->snap)->
325 ps->store->chunk_mask = ps->store->chunk_size - 1;
326 ps->store->chunk_shift = ffs(ps->store->chunk_size) - 1;
327 chunk_size_supplied = 0;
330 ps->io_client = dm_io_client_create();
331 if (IS_ERR(ps->io_client))
332 return PTR_ERR(ps->io_client);
338 r = chunk_io(ps, ps->header_area, 0, READ, 1);
342 dh = ps->header_area;
344 if (le32_to_cpu(dh->magic) == 0) {
349 if (le32_to_cpu(dh->magic) != SNAP_MAGIC) {
350 DMWARN("Invalid or corrupt snapshot");
356 ps->valid = le32_to_cpu(dh->valid);
357 ps->version = le32_to_cpu(dh->version);
358 chunk_size = le32_to_cpu(dh->chunk_size);
360 if (ps->store->chunk_size == chunk_size)
363 if (chunk_size_supplied)
364 DMWARN("chunk size %u in device metadata overrides "
365 "table chunk size of %u.",
366 chunk_size, ps->store->chunk_size);
368 /* We had a bogus chunk_size. Fix stuff up. */
371 r = dm_exception_store_set_chunk_size(ps->store, chunk_size,
374 DMERR("invalid on-disk chunk size %u: %s.",
375 chunk_size, chunk_err);
387 static int write_header(struct pstore *ps)
389 struct disk_header *dh;
391 memset(ps->header_area, 0, ps->store->chunk_size << SECTOR_SHIFT);
393 dh = ps->header_area;
394 dh->magic = cpu_to_le32(SNAP_MAGIC);
395 dh->valid = cpu_to_le32(ps->valid);
396 dh->version = cpu_to_le32(ps->version);
397 dh->chunk_size = cpu_to_le32(ps->store->chunk_size);
399 return chunk_io(ps, ps->header_area, 0, WRITE, 1);
403 * Access functions for the disk exceptions, these do the endian conversions.
405 static struct disk_exception *get_exception(struct pstore *ps, uint32_t index)
407 BUG_ON(index >= ps->exceptions_per_area);
409 return ((struct disk_exception *) ps->area) + index;
412 static void read_exception(struct pstore *ps,
413 uint32_t index, struct core_exception *result)
415 struct disk_exception *de = get_exception(ps, index);
418 result->old_chunk = le64_to_cpu(de->old_chunk);
419 result->new_chunk = le64_to_cpu(de->new_chunk);
422 static void write_exception(struct pstore *ps,
423 uint32_t index, struct core_exception *e)
425 struct disk_exception *de = get_exception(ps, index);
428 de->old_chunk = cpu_to_le64(e->old_chunk);
429 de->new_chunk = cpu_to_le64(e->new_chunk);
432 static void clear_exception(struct pstore *ps, uint32_t index)
434 struct disk_exception *de = get_exception(ps, index);
442 * Registers the exceptions that are present in the current area.
443 * 'full' is filled in to indicate if the area has been
446 static int insert_exceptions(struct pstore *ps,
447 int (*callback)(void *callback_context,
448 chunk_t old, chunk_t new),
449 void *callback_context,
454 struct core_exception e;
456 /* presume the area is full */
459 for (i = 0; i < ps->exceptions_per_area; i++) {
460 read_exception(ps, i, &e);
463 * If the new_chunk is pointing at the start of
464 * the COW device, where the first metadata area
465 * is we know that we've hit the end of the
466 * exceptions. Therefore the area is not full.
468 if (e.new_chunk == 0LL) {
469 ps->current_committed = i;
475 * Keep track of the start of the free chunks.
477 if (ps->next_free <= e.new_chunk)
478 ps->next_free = e.new_chunk + 1;
481 * Otherwise we add the exception to the snapshot.
483 r = callback(callback_context, e.old_chunk, e.new_chunk);
491 static int read_exceptions(struct pstore *ps,
492 int (*callback)(void *callback_context, chunk_t old,
494 void *callback_context)
499 * Keeping reading chunks and inserting exceptions until
500 * we find a partially full area.
502 for (ps->current_area = 0; full; ps->current_area++) {
503 r = area_io(ps, READ);
507 r = insert_exceptions(ps, callback, callback_context, &full);
519 static struct pstore *get_info(struct dm_exception_store *store)
521 return (struct pstore *) store->context;
524 static void persistent_usage(struct dm_exception_store *store,
525 sector_t *total_sectors,
526 sector_t *sectors_allocated,
527 sector_t *metadata_sectors)
529 struct pstore *ps = get_info(store);
531 *sectors_allocated = ps->next_free * store->chunk_size;
532 *total_sectors = get_dev_size(dm_snap_cow(store->snap)->bdev);
535 * First chunk is the fixed header.
536 * Then there are (ps->current_area + 1) metadata chunks, each one
537 * separated from the next by ps->exceptions_per_area data chunks.
539 *metadata_sectors = (ps->current_area + 1 + NUM_SNAPSHOT_HDR_CHUNKS) *
543 static void persistent_dtr(struct dm_exception_store *store)
545 struct pstore *ps = get_info(store);
547 destroy_workqueue(ps->metadata_wq);
549 /* Created in read_header */
551 dm_io_client_destroy(ps->io_client);
554 /* Allocated in persistent_read_metadata */
556 vfree(ps->callbacks);
561 static int persistent_read_metadata(struct dm_exception_store *store,
562 int (*callback)(void *callback_context,
563 chunk_t old, chunk_t new),
564 void *callback_context)
566 int r, uninitialized_var(new_snapshot);
567 struct pstore *ps = get_info(store);
570 * Read the snapshot header.
572 r = read_header(ps, &new_snapshot);
577 * Now we know correct chunk_size, complete the initialisation.
579 ps->exceptions_per_area = (ps->store->chunk_size << SECTOR_SHIFT) /
580 sizeof(struct disk_exception);
581 ps->callbacks = dm_vcalloc(ps->exceptions_per_area,
582 sizeof(*ps->callbacks));
587 * Do we need to setup a new snapshot ?
590 r = write_header(ps);
592 DMWARN("write_header failed");
596 ps->current_area = 0;
597 zero_memory_area(ps);
598 r = zero_disk_area(ps, 0);
600 DMWARN("zero_disk_area(0) failed");
606 if (ps->version != SNAPSHOT_DISK_VERSION) {
607 DMWARN("unable to handle snapshot disk version %d",
613 * Metadata are valid, but snapshot is invalidated
621 r = read_exceptions(ps, callback, callback_context);
626 static int persistent_prepare_exception(struct dm_exception_store *store,
627 struct dm_exception *e)
629 struct pstore *ps = get_info(store);
630 sector_t size = get_dev_size(dm_snap_cow(store->snap)->bdev);
632 /* Is there enough room ? */
633 if (size < ((ps->next_free + 1) * store->chunk_size))
636 e->new_chunk = ps->next_free;
639 * Move onto the next free pending, making sure to take
640 * into account the location of the metadata chunks.
645 atomic_inc(&ps->pending_count);
649 static void persistent_commit_exception(struct dm_exception_store *store,
650 struct dm_exception *e,
651 void (*callback) (void *, int success),
652 void *callback_context)
655 struct pstore *ps = get_info(store);
656 struct core_exception ce;
657 struct commit_callback *cb;
659 ce.old_chunk = e->old_chunk;
660 ce.new_chunk = e->new_chunk;
661 write_exception(ps, ps->current_committed++, &ce);
664 * Add the callback to the back of the array. This code
665 * is the only place where the callback array is
666 * manipulated, and we know that it will never be called
667 * multiple times concurrently.
669 cb = ps->callbacks + ps->callback_count++;
670 cb->callback = callback;
671 cb->context = callback_context;
674 * If there are exceptions in flight and we have not yet
675 * filled this metadata area there's nothing more to do.
677 if (!atomic_dec_and_test(&ps->pending_count) &&
678 (ps->current_committed != ps->exceptions_per_area))
682 * If we completely filled the current area, then wipe the next one.
684 if ((ps->current_committed == ps->exceptions_per_area) &&
685 zero_disk_area(ps, ps->current_area + 1))
689 * Commit exceptions to disk.
691 if (ps->valid && area_io(ps, WRITE_FLUSH_FUA))
695 * Advance to the next area if this one is full.
697 if (ps->current_committed == ps->exceptions_per_area) {
698 ps->current_committed = 0;
700 zero_memory_area(ps);
703 for (i = 0; i < ps->callback_count; i++) {
704 cb = ps->callbacks + i;
705 cb->callback(cb->context, ps->valid);
708 ps->callback_count = 0;
711 static int persistent_prepare_merge(struct dm_exception_store *store,
712 chunk_t *last_old_chunk,
713 chunk_t *last_new_chunk)
715 struct pstore *ps = get_info(store);
716 struct core_exception ce;
721 * When current area is empty, move back to preceding area.
723 if (!ps->current_committed) {
727 if (!ps->current_area)
731 r = area_io(ps, READ);
734 ps->current_committed = ps->exceptions_per_area;
737 read_exception(ps, ps->current_committed - 1, &ce);
738 *last_old_chunk = ce.old_chunk;
739 *last_new_chunk = ce.new_chunk;
742 * Find number of consecutive chunks within the current area,
745 for (nr_consecutive = 1; nr_consecutive < ps->current_committed;
747 read_exception(ps, ps->current_committed - 1 - nr_consecutive,
749 if (ce.old_chunk != *last_old_chunk - nr_consecutive ||
750 ce.new_chunk != *last_new_chunk - nr_consecutive)
754 return nr_consecutive;
757 static int persistent_commit_merge(struct dm_exception_store *store,
761 struct pstore *ps = get_info(store);
763 BUG_ON(nr_merged > ps->current_committed);
765 for (i = 0; i < nr_merged; i++)
766 clear_exception(ps, ps->current_committed - 1 - i);
768 r = area_io(ps, WRITE_FLUSH_FUA);
772 ps->current_committed -= nr_merged;
775 * At this stage, only persistent_usage() uses ps->next_free, so
776 * we make no attempt to keep ps->next_free strictly accurate
777 * as exceptions may have been committed out-of-order originally.
778 * Once a snapshot has become merging, we set it to the value it
779 * would have held had all the exceptions been committed in order.
781 * ps->current_area does not get reduced by prepare_merge() until
782 * after commit_merge() has removed the nr_merged previous exceptions.
784 ps->next_free = area_location(ps, ps->current_area) +
785 ps->current_committed + 1;
790 static void persistent_drop_snapshot(struct dm_exception_store *store)
792 struct pstore *ps = get_info(store);
795 if (write_header(ps))
796 DMWARN("write header failed");
799 static int persistent_ctr(struct dm_exception_store *store,
800 unsigned argc, char **argv)
804 /* allocate the pstore */
805 ps = kzalloc(sizeof(*ps), GFP_KERNEL);
811 ps->version = SNAPSHOT_DISK_VERSION;
813 ps->zero_area = NULL;
814 ps->header_area = NULL;
815 ps->next_free = NUM_SNAPSHOT_HDR_CHUNKS + 1; /* header and 1st area */
816 ps->current_committed = 0;
818 ps->callback_count = 0;
819 atomic_set(&ps->pending_count, 0);
820 ps->callbacks = NULL;
822 ps->metadata_wq = alloc_workqueue("ksnaphd", WQ_MEM_RECLAIM, 0);
823 if (!ps->metadata_wq) {
825 DMERR("couldn't start header metadata update thread");
834 static unsigned persistent_status(struct dm_exception_store *store,
835 status_type_t status, char *result,
841 case STATUSTYPE_INFO:
843 case STATUSTYPE_TABLE:
844 DMEMIT(" P %llu", (unsigned long long)store->chunk_size);
850 static struct dm_exception_store_type _persistent_type = {
851 .name = "persistent",
852 .module = THIS_MODULE,
853 .ctr = persistent_ctr,
854 .dtr = persistent_dtr,
855 .read_metadata = persistent_read_metadata,
856 .prepare_exception = persistent_prepare_exception,
857 .commit_exception = persistent_commit_exception,
858 .prepare_merge = persistent_prepare_merge,
859 .commit_merge = persistent_commit_merge,
860 .drop_snapshot = persistent_drop_snapshot,
861 .usage = persistent_usage,
862 .status = persistent_status,
865 static struct dm_exception_store_type _persistent_compat_type = {
867 .module = THIS_MODULE,
868 .ctr = persistent_ctr,
869 .dtr = persistent_dtr,
870 .read_metadata = persistent_read_metadata,
871 .prepare_exception = persistent_prepare_exception,
872 .commit_exception = persistent_commit_exception,
873 .prepare_merge = persistent_prepare_merge,
874 .commit_merge = persistent_commit_merge,
875 .drop_snapshot = persistent_drop_snapshot,
876 .usage = persistent_usage,
877 .status = persistent_status,
880 int dm_persistent_snapshot_init(void)
884 r = dm_exception_store_type_register(&_persistent_type);
886 DMERR("Unable to register persistent exception store type");
890 r = dm_exception_store_type_register(&_persistent_compat_type);
892 DMERR("Unable to register old-style persistent exception "
894 dm_exception_store_type_unregister(&_persistent_type);
901 void dm_persistent_snapshot_exit(void)
903 dm_exception_store_type_unregister(&_persistent_type);
904 dm_exception_store_type_unregister(&_persistent_compat_type);