/* * dm-snapshot.c * * Copyright (C) 2001-2002 Sistina Software (UK) Limited. * * This file is released under the GPL. */ #include <linux/blkdev.h>#include <linux/device-mapper.h>#include <linux/delay.h>#include <linux/fs.h>#include <linux/init.h>#include <linux/kdev_t.h>#include <linux/list.h>#include <linux/mempool.h>#include <linux/module.h>#include <linux/slab.h>#include <linux/vmalloc.h>#include <linux/log2.h>#include <linux/dm-kcopyd.h> #include "dm-exception-store.h" #define DM_MSG_PREFIX "snapshots" static const char dm_snapshot_merge_target_name[] = "snapshot-merge"; #define dm_target_is_snapshot_merge(ti) \ ((ti)->type->name == dm_snapshot_merge_target_name) /* * The size of the mempool used to track chunks in use. */#define MIN_IOS 256 #define DM_TRACKED_CHUNK_HASH_SIZE 16#define DM_TRACKED_CHUNK_HASH(x) ((unsigned long)(x) & \ (DM_TRACKED_CHUNK_HASH_SIZE - 1)) struct dm_exception_table { uint32_t hash_mask; unsigned hash_shift; struct list_head *table;}; struct dm_snapshot { struct rw_semaphore lock; struct dm_dev *origin; struct dm_dev *cow; struct dm_target *ti; /* List of snapshots per Origin */ struct list_head list; /* * You can't use a snapshot if this is 0 (e.g. if full). * A snapshot-merge target never clears this. */ int valid; /* Origin writes don't trigger exceptions until this is set */ int active; atomic_t pending_exceptions_count; /* Protected by "lock" */ sector_t exception_start_sequence; /* Protected by kcopyd single-threaded callback */ sector_t exception_complete_sequence; /* * A list of pending exceptions that completed out of order. * Protected by kcopyd single-threaded callback. */ struct list_head out_of_order_list; mempool_t *pending_pool; struct dm_exception_table pending; struct dm_exception_table complete; /* * pe_lock protects all pending_exception operations and access * as well as the snapshot_bios list. */ spinlock_t pe_lock; /* Chunks with outstanding reads */ spinlock_t tracked_chunk_lock; struct hlist_head tracked_chunk_hash[DM_TRACKED_CHUNK_HASH_SIZE]; /* The on disk metadata handler */ struct dm_exception_store *store; struct dm_kcopyd_client *kcopyd_client; /* Wait for events based on state_bits */ unsigned long state_bits; /* Range of chunks currently being merged. */ chunk_t first_merging_chunk; int num_merging_chunks; /* * The merge operation failed if this flag is set. * Failure modes are handled as follows: * - I/O error reading the header * => don't load the target; abort. * - Header does not have "valid" flag set * => use the origin; forget about the snapshot. * - I/O error when reading exceptions * => don't load the target; abort. * (We can't use the intermediate origin state.) * - I/O error while merging * => stop merging; set merge_failed; process I/O normally. */ int merge_failed; /* * Incoming bios that overlap with chunks being merged must wait * for them to be committed. */ struct bio_list bios_queued_during_merge;}; /* * state_bits: * RUNNING_MERGE - Merge operation is in progress. * SHUTDOWN_MERGE - Set to signal that merge needs to be stopped; * cleared afterwards. */#define RUNNING_MERGE 0#define SHUTDOWN_MERGE 1 DECLARE_DM_KCOPYD_THROTTLE_WITH_MODULE_PARM(snapshot_copy_throttle, "A percentage of time allocated for copy on write"); struct dm_dev *dm_snap_origin(struct dm_snapshot *s){ return s->origin;}EXPORT_SYMBOL(dm_snap_origin); struct dm_dev *dm_snap_cow(struct dm_snapshot *s){ return s->cow;}EXPORT_SYMBOL(dm_snap_cow); static sector_t chunk_to_sector(struct dm_exception_store *store, chunk_t chunk){ return chunk << store->chunk_shift;} static int bdev_equal(struct block_device *lhs, struct block_device *rhs){ /* * There is only ever one instance of a particular block * device so we can compare pointers safely. */ return lhs == rhs;} struct dm_snap_pending_exception { struct dm_exception e; /* * Origin buffers waiting for this to complete are held * in a bio list */ struct bio_list origin_bios; struct bio_list snapshot_bios; /* Pointer back to snapshot context */ struct dm_snapshot *snap; /* * 1 indicates the exception has already been sent to * kcopyd. */ int started; /* There was copying error. */ int copy_error; /* A sequence number, it is used for in-order completion. */ sector_t exception_sequence; struct list_head out_of_order_entry; /* * For writing a complete chunk, bypassing the copy. */ struct bio *full_bio; bio_end_io_t *full_bio_end_io; void *full_bio_private;}; /* * Hash table mapping origin volumes to lists of snapshots and * a lock to protect it */static struct kmem_cache *exception_cache;static struct kmem_cache *pending_cache; struct dm_snap_tracked_chunk { struct hlist_node node; chunk_t chunk;}; static void init_tracked_chunk(struct bio *bio){ struct dm_snap_tracked_chunk *c = dm_per_bio_data(bio, sizeof(struct dm_snap_tracked_chunk)); INIT_HLIST_NODE(&c->node);} static bool is_bio_tracked(struct bio *bio){ struct dm_snap_tracked_chunk *c = dm_per_bio_data(bio, sizeof(struct dm_snap_tracked_chunk)); return !hlist_unhashed(&c->node);} static void track_chunk(struct dm_snapshot *s, struct bio *bio, chunk_t chunk){ struct dm_snap_tracked_chunk *c = dm_per_bio_data(bio, sizeof(struct dm_snap_tracked_chunk)); c->chunk = chunk; spin_lock_irq(&s->tracked_chunk_lock); hlist_add_head(&c->node, &s->tracked_chunk_hash[DM_TRACKED_CHUNK_HASH(chunk)]); spin_unlock_irq(&s->tracked_chunk_lock);} static void stop_tracking_chunk(struct dm_snapshot *s, struct bio *bio){ struct dm_snap_tracked_chunk *c = dm_per_bio_data(bio, sizeof(struct dm_snap_tracked_chunk)); unsigned long flags; spin_lock_irqsave(&s->tracked_chunk_lock, flags); hlist_del(&c->node); spin_unlock_irqrestore(&s->tracked_chunk_lock, flags);} static int __chunk_is_tracked(struct dm_snapshot *s, chunk_t chunk){ struct dm_snap_tracked_chunk *c; int found = 0; spin_lock_irq(&s->tracked_chunk_lock); hlist_for_each_entry(c, &s->tracked_chunk_hash[DM_TRACKED_CHUNK_HASH(chunk)], node) { if (c->chunk == chunk) { found = 1; break; } } spin_unlock_irq(&s->tracked_chunk_lock); return found;} /* * This conflicting I/O is extremely improbable in the caller, * so msleep(1) is sufficient and there is no need for a wait queue. */static void __check_for_conflicting_io(struct dm_snapshot *s, chunk_t chunk){ while (__chunk_is_tracked(s, chunk)) msleep(1);} /* * One of these per registered origin, held in the snapshot_origins hash */struct origin { /* The origin device */ struct block_device *bdev; struct list_head hash_list; /* List of snapshots for this origin */ struct list_head snapshots;}; /* * Size of the hash table for origin volumes. If we make this * the size of the minors list then it should be nearly perfect */#define ORIGIN_HASH_SIZE 256#define ORIGIN_MASK 0xFFstatic struct list_head *_origins;static struct rw_semaphore _origins_lock; static DECLARE_WAIT_QUEUE_HEAD(_pending_exceptions_done);static DEFINE_SPINLOCK(_pending_exceptions_done_spinlock);static uint64_t _pending_exceptions_done_count; static int init_origin_hash(void){ int i; _origins = kmalloc(ORIGIN_HASH_SIZE * sizeof(struct list_head), GFP_KERNEL); if (!_origins) { DMERR("unable to allocate memory"); return -ENOMEM; } for (i = 0; i < ORIGIN_HASH_SIZE; i++) INIT_LIST_HEAD(_origins + i); init_rwsem(&_origins_lock); return 0;} static void exit_origin_hash(void){ kfree(_origins);} static unsigned origin_hash(struct block_device *bdev){ return bdev->bd_dev & ORIGIN_MASK;} static struct origin *__lookup_origin(struct block_device *origin){ struct list_head *ol; struct origin *o; ol = &_origins[origin_hash(origin)]; list_for_each_entry (o, ol, hash_list) if (bdev_equal(o->bdev, origin)) return o; return NULL;} static void __insert_origin(struct origin *o){ struct list_head *sl = &_origins[origin_hash(o->bdev)]; list_add_tail(&o->hash_list, sl);} /* * _origins_lock must be held when calling this function. * Returns number of snapshots registered using the supplied cow device, plus: * snap_src - a snapshot suitable for use as a source of exception handover * snap_dest - a snapshot capable of receiving exception handover. * snap_merge - an existing snapshot-merge target linked to the same origin. * There can be at most one snapshot-merge target. The parameter is optional. * * Possible return values and states of snap_src and snap_dest. * 0: NULL, NULL - first new snapshot * 1: snap_src, NULL - normal snapshot * 2: snap_src, snap_dest - waiting for handover * 2: snap_src, NULL - handed over, waiting for old to be deleted * 1: NULL, snap_dest - source got destroyed without handover */static int __find_snapshots_sharing_cow(struct dm_snapshot *snap, struct dm_snapshot **snap_src, struct dm_snapshot **snap_dest, struct dm_snapshot **snap_merge){ struct dm_snapshot *s; struct origin *o; int count = 0; int active; o = __lookup_origin(snap->origin->bdev); if (!o) goto out; list_for_each_entry(s, &o->snapshots, list) { if (dm_target_is_snapshot_merge(s->ti) && snap_merge) *snap_merge = s; if (!bdev_equal(s->cow->bdev, snap->cow->bdev)) continue; down_read(&s->lock); active = s->active; up_read(&s->lock); if (active) { if (snap_src) *snap_src = s; } else if (snap_dest) *snap_dest = s; count++; } out: return count;} /* * On success, returns 1 if this snapshot is a handover destination, * otherwise returns 0. */static int __validate_exception_handover(struct dm_snapshot *snap){ struct dm_snapshot *snap_src = NULL, *snap_dest = NULL; struct dm_snapshot *snap_merge = NULL; /* Does snapshot need exceptions handed over to it? */ if ((__find_snapshots_sharing_cow(snap, &snap_src, &snap_dest, &snap_merge) == 2) || snap_dest) { snap->ti->error = "Snapshot cow pairing for exception " "table handover failed"; return -EINVAL; } /* * If no snap_src was found, snap cannot become a handover * destination. */ if (!snap_src) return 0; /* * Non-snapshot-merge handover? */ if (!dm_target_is_snapshot_merge(snap->ti)) return 1; /* * Do not allow more than one merging snapshot. */ if (snap_merge) { snap->ti->error = "A snapshot is already merging."; return -EINVAL; } if (!snap_src->store->type->prepare_merge || !snap_src->store->type->commit_merge) { snap->ti->error = "Snapshot exception store does not " "support snapshot-merge."; return -EINVAL; } return 1;} static void __insert_snapshot(struct origin *o, struct dm_snapshot *s){ struct dm_snapshot *l; /* Sort the list according to chunk size, largest-first smallest-last */ list_for_each_entry(l, &o->snapshots, list) if (l->store->chunk_size < s->store->chunk_size) break; list_add_tail(&s->list, &l->list);} /* * Make a note of the snapshot and its origin so we can look it * up when the origin has a write on it. * * Also validate snapshot exception store handovers. * On success, returns 1 if this registration is a handover destination, * otherwise returns 0. */static int register_snapshot(struct dm_snapshot *snap){ struct origin *o, *new_o = NULL; struct block_device *bdev = snap->origin->bdev; int r = 0; new_o = kmalloc(sizeof(*new_o), GFP_KERNEL); if (!new_o) return -ENOMEM; down_write(&_origins_lock); r = __validate_exception_handover(snap); if (r < 0) { kfree(new_o); goto out; } o = __lookup_origin(bdev); if (o) kfree(new_o); else { /* New origin */ o = new_o; /* Initialise the struct */ INIT_LIST_HEAD(&o->snapshots); o->bdev = bdev;Lines 1–500 of 2366. Load more
/* * dm-snapshot.c * * Copyright (C) 2001-2002 Sistina Software (UK) Limited. * * This file is released under the GPL. */ #include <linux/blkdev.h> #include <linux/device-mapper.h> #include <linux/delay.h> #include <linux/fs.h> #include <linux/init.h> #include <linux/kdev_t.h> #include <linux/list.h> #include <linux/mempool.h> #include <linux/module.h> #include <linux/slab.h> #include <linux/vmalloc.h> #include <linux/log2.h> #include <linux/dm-kcopyd.h> #include "dm-exception-store.h" #define DM_MSG_PREFIX "snapshots" static const char dm_snapshot_merge_target_name[] = "snapshot-merge"; #define dm_target_is_snapshot_merge(ti) \ ((ti)->type->name == dm_snapshot_merge_target_name) /* * The size of the mempool used to track chunks in use. */ #define MIN_IOS 256 #define DM_TRACKED_CHUNK_HASH_SIZE 16 #define DM_TRACKED_CHUNK_HASH(x) ((unsigned long)(x) & \ (DM_TRACKED_CHUNK_HASH_SIZE - 1)) struct dm_exception_table { uint32_t hash_mask; unsigned hash_shift; struct list_head *table; }; struct dm_snapshot { struct rw_semaphore lock; struct dm_dev *origin; struct dm_dev *cow; struct dm_target *ti; /* List of snapshots per Origin */ struct list_head list; /* * You can't use a snapshot if this is 0 (e.g. if full). * A snapshot-merge target never clears this. */ int valid; /* Origin writes don't trigger exceptions until this is set */ int active; atomic_t pending_exceptions_count; /* Protected by "lock" */ sector_t exception_start_sequence; /* Protected by kcopyd single-threaded callback */ sector_t exception_complete_sequence; /* * A list of pending exceptions that completed out of order. * Protected by kcopyd single-threaded callback. */ struct list_head out_of_order_list; mempool_t *pending_pool; struct dm_exception_table pending; struct dm_exception_table complete; /* * pe_lock protects all pending_exception operations and access * as well as the snapshot_bios list. */ spinlock_t pe_lock; /* Chunks with outstanding reads */ spinlock_t tracked_chunk_lock; struct hlist_head tracked_chunk_hash[DM_TRACKED_CHUNK_HASH_SIZE]; /* The on disk metadata handler */ struct dm_exception_store *store; struct dm_kcopyd_client *kcopyd_client; /* Wait for events based on state_bits */ unsigned long state_bits; /* Range of chunks currently being merged. */ chunk_t first_merging_chunk; int num_merging_chunks; /* * The merge operation failed if this flag is set. * Failure modes are handled as follows: * - I/O error reading the header * => don't load the target; abort. * - Header does not have "valid" flag set * => use the origin; forget about the snapshot. * - I/O error when reading exceptions * => don't load the target; abort. * (We can't use the intermediate origin state.) * - I/O error while merging * => stop merging; set merge_failed; process I/O normally. */ int merge_failed; /* * Incoming bios that overlap with chunks being merged must wait * for them to be committed. */ struct bio_list bios_queued_during_merge; }; /* * state_bits: * RUNNING_MERGE - Merge operation is in progress. * SHUTDOWN_MERGE - Set to signal that merge needs to be stopped; * cleared afterwards. */ #define RUNNING_MERGE 0 #define SHUTDOWN_MERGE 1 DECLARE_DM_KCOPYD_THROTTLE_WITH_MODULE_PARM(snapshot_copy_throttle, "A percentage of time allocated for copy on write"); struct dm_dev *dm_snap_origin(struct dm_snapshot *s) { return s->origin; } EXPORT_SYMBOL(dm_snap_origin); struct dm_dev *dm_snap_cow(struct dm_snapshot *s) { return s->cow; } EXPORT_SYMBOL(dm_snap_cow); static sector_t chunk_to_sector(struct dm_exception_store *store, chunk_t chunk) { return chunk << store->chunk_shift; } static int bdev_equal(struct block_device *lhs, struct block_device *rhs) { /* * There is only ever one instance of a particular block * device so we can compare pointers safely. */ return lhs == rhs; } struct dm_snap_pending_exception { struct dm_exception e; /* * Origin buffers waiting for this to complete are held * in a bio list */ struct bio_list origin_bios; struct bio_list snapshot_bios; /* Pointer back to snapshot context */ struct dm_snapshot *snap; /* * 1 indicates the exception has already been sent to * kcopyd. */ int started; /* There was copying error. */ int copy_error; /* A sequence number, it is used for in-order completion. */ sector_t exception_sequence; struct list_head out_of_order_entry; /* * For writing a complete chunk, bypassing the copy. */ struct bio *full_bio; bio_end_io_t *full_bio_end_io; void *full_bio_private; }; /* * Hash table mapping origin volumes to lists of snapshots and * a lock to protect it */ static struct kmem_cache *exception_cache; static struct kmem_cache *pending_cache; struct dm_snap_tracked_chunk { struct hlist_node node; chunk_t chunk; }; static void init_tracked_chunk(struct bio *bio) { struct dm_snap_tracked_chunk *c = dm_per_bio_data(bio, sizeof(struct dm_snap_tracked_chunk)); INIT_HLIST_NODE(&c->node); } static bool is_bio_tracked(struct bio *bio) { struct dm_snap_tracked_chunk *c = dm_per_bio_data(bio, sizeof(struct dm_snap_tracked_chunk)); return !hlist_unhashed(&c->node); } static void track_chunk(struct dm_snapshot *s, struct bio *bio, chunk_t chunk) { struct dm_snap_tracked_chunk *c = dm_per_bio_data(bio, sizeof(struct dm_snap_tracked_chunk)); c->chunk = chunk; spin_lock_irq(&s->tracked_chunk_lock); hlist_add_head(&c->node, &s->tracked_chunk_hash[DM_TRACKED_CHUNK_HASH(chunk)]); spin_unlock_irq(&s->tracked_chunk_lock); } static void stop_tracking_chunk(struct dm_snapshot *s, struct bio *bio) { struct dm_snap_tracked_chunk *c = dm_per_bio_data(bio, sizeof(struct dm_snap_tracked_chunk)); unsigned long flags; spin_lock_irqsave(&s->tracked_chunk_lock, flags); hlist_del(&c->node); spin_unlock_irqrestore(&s->tracked_chunk_lock, flags); } static int __chunk_is_tracked(struct dm_snapshot *s, chunk_t chunk) { struct dm_snap_tracked_chunk *c; int found = 0; spin_lock_irq(&s->tracked_chunk_lock); hlist_for_each_entry(c, &s->tracked_chunk_hash[DM_TRACKED_CHUNK_HASH(chunk)], node) { if (c->chunk == chunk) { found = 1; break; } } spin_unlock_irq(&s->tracked_chunk_lock); return found; } /* * This conflicting I/O is extremely improbable in the caller, * so msleep(1) is sufficient and there is no need for a wait queue. */ static void __check_for_conflicting_io(struct dm_snapshot *s, chunk_t chunk) { while (__chunk_is_tracked(s, chunk)) msleep(1); } /* * One of these per registered origin, held in the snapshot_origins hash */ struct origin { /* The origin device */ struct block_device *bdev; struct list_head hash_list; /* List of snapshots for this origin */ struct list_head snapshots; }; /* * Size of the hash table for origin volumes. If we make this * the size of the minors list then it should be nearly perfect */ #define ORIGIN_HASH_SIZE 256 #define ORIGIN_MASK 0xFF static struct list_head *_origins; static struct rw_semaphore _origins_lock; static DECLARE_WAIT_QUEUE_HEAD(_pending_exceptions_done); static DEFINE_SPINLOCK(_pending_exceptions_done_spinlock); static uint64_t _pending_exceptions_done_count; static int init_origin_hash(void) { int i; _origins = kmalloc(ORIGIN_HASH_SIZE * sizeof(struct list_head), GFP_KERNEL); if (!_origins) { DMERR("unable to allocate memory"); return -ENOMEM; } for (i = 0; i < ORIGIN_HASH_SIZE; i++) INIT_LIST_HEAD(_origins + i); init_rwsem(&_origins_lock); return 0; } static void exit_origin_hash(void) { kfree(_origins); } static unsigned origin_hash(struct block_device *bdev) { return bdev->bd_dev & ORIGIN_MASK; } static struct origin *__lookup_origin(struct block_device *origin) { struct list_head *ol; struct origin *o; ol = &_origins[origin_hash(origin)]; list_for_each_entry (o, ol, hash_list) if (bdev_equal(o->bdev, origin)) return o; return NULL; } static void __insert_origin(struct origin *o) { struct list_head *sl = &_origins[origin_hash(o->bdev)]; list_add_tail(&o->hash_list, sl); } /* * _origins_lock must be held when calling this function. * Returns number of snapshots registered using the supplied cow device, plus: * snap_src - a snapshot suitable for use as a source of exception handover * snap_dest - a snapshot capable of receiving exception handover. * snap_merge - an existing snapshot-merge target linked to the same origin. * There can be at most one snapshot-merge target. The parameter is optional. * * Possible return values and states of snap_src and snap_dest. * 0: NULL, NULL - first new snapshot * 1: snap_src, NULL - normal snapshot * 2: snap_src, snap_dest - waiting for handover * 2: snap_src, NULL - handed over, waiting for old to be deleted * 1: NULL, snap_dest - source got destroyed without handover */ static int __find_snapshots_sharing_cow(struct dm_snapshot *snap, struct dm_snapshot **snap_src, struct dm_snapshot **snap_dest, struct dm_snapshot **snap_merge) { struct dm_snapshot *s; struct origin *o; int count = 0; int active; o = __lookup_origin(snap->origin->bdev); if (!o) goto out; list_for_each_entry(s, &o->snapshots, list) { if (dm_target_is_snapshot_merge(s->ti) && snap_merge) *snap_merge = s; if (!bdev_equal(s->cow->bdev, snap->cow->bdev)) continue; down_read(&s->lock); active = s->active; up_read(&s->lock); if (active) { if (snap_src) *snap_src = s; } else if (snap_dest) *snap_dest = s; count++; } out: return count; } /* * On success, returns 1 if this snapshot is a handover destination, * otherwise returns 0. */ static int __validate_exception_handover(struct dm_snapshot *snap) { struct dm_snapshot *snap_src = NULL, *snap_dest = NULL; struct dm_snapshot *snap_merge = NULL; /* Does snapshot need exceptions handed over to it? */ if ((__find_snapshots_sharing_cow(snap, &snap_src, &snap_dest, &snap_merge) == 2) || snap_dest) { snap->ti->error = "Snapshot cow pairing for exception " "table handover failed"; return -EINVAL; } /* * If no snap_src was found, snap cannot become a handover * destination. */ if (!snap_src) return 0; /* * Non-snapshot-merge handover? */ if (!dm_target_is_snapshot_merge(snap->ti)) return 1; /* * Do not allow more than one merging snapshot. */ if (snap_merge) { snap->ti->error = "A snapshot is already merging."; return -EINVAL; } if (!snap_src->store->type->prepare_merge || !snap_src->store->type->commit_merge) { snap->ti->error = "Snapshot exception store does not " "support snapshot-merge."; return -EINVAL; } return 1; } static void __insert_snapshot(struct origin *o, struct dm_snapshot *s) { struct dm_snapshot *l; /* Sort the list according to chunk size, largest-first smallest-last */ list_for_each_entry(l, &o->snapshots, list) if (l->store->chunk_size < s->store->chunk_size) break; list_add_tail(&s->list, &l->list); } /* * Make a note of the snapshot and its origin so we can look it * up when the origin has a write on it. * * Also validate snapshot exception store handovers. * On success, returns 1 if this registration is a handover destination, * otherwise returns 0. */ static int register_snapshot(struct dm_snapshot *snap) { struct origin *o, *new_o = NULL; struct block_device *bdev = snap->origin->bdev; int r = 0; new_o = kmalloc(sizeof(*new_o), GFP_KERNEL); if (!new_o) return -ENOMEM; down_write(&_origins_lock); r = __validate_exception_handover(snap); if (r < 0) { kfree(new_o); goto out; } o = __lookup_origin(bdev); if (o) kfree(new_o); else { /* New origin */ o = new_o; /* Initialise the struct */ INIT_LIST_HEAD(&o->snapshots); o->bdev = bdev;