dm snapshot: combine consecutive exceptions in memory
Provided sector_t is 64 bits, reduce the in-memory footprint of the
snapshot exception table by the simple method of using unused bits of
the chunk number to combine consecutive entries.
Signed-off-by: Milan Broz <mbroz@redhat.com>
Signed-off-by: Alasdair G Kergon <agk@redhat.com>
diff --git a/drivers/md/dm-snap.c b/drivers/md/dm-snap.c
index fad8465..ae24eab 100644
--- a/drivers/md/dm-snap.c
+++ b/drivers/md/dm-snap.c
@@ -213,11 +213,15 @@
/*
* Implementation of the exception hash tables.
+ * The lowest hash_shift bits of the chunk number are ignored, allowing
+ * some consecutive chunks to be grouped together.
*/
-static int init_exception_table(struct exception_table *et, uint32_t size)
+static int init_exception_table(struct exception_table *et, uint32_t size,
+ unsigned hash_shift)
{
unsigned int i;
+ et->hash_shift = hash_shift;
et->hash_mask = size - 1;
et->table = dm_vcalloc(size, sizeof(struct list_head));
if (!et->table)
@@ -248,7 +252,7 @@
static uint32_t exception_hash(struct exception_table *et, chunk_t chunk)
{
- return chunk & et->hash_mask;
+ return (chunk >> et->hash_shift) & et->hash_mask;
}
static void insert_exception(struct exception_table *eh,
@@ -275,7 +279,8 @@
slot = &et->table[exception_hash(et, chunk)];
list_for_each_entry (e, slot, hash_list)
- if (e->old_chunk == chunk)
+ if (chunk >= e->old_chunk &&
+ chunk <= e->old_chunk + dm_consecutive_chunk_count(e))
return e;
return NULL;
@@ -307,6 +312,49 @@
mempool_free(pe, pending_pool);
}
+static void insert_completed_exception(struct dm_snapshot *s,
+ struct dm_snap_exception *new_e)
+{
+ struct exception_table *eh = &s->complete;
+ struct list_head *l;
+ struct dm_snap_exception *e = NULL;
+
+ l = &eh->table[exception_hash(eh, new_e->old_chunk)];
+
+ /* Add immediately if this table doesn't support consecutive chunks */
+ if (!eh->hash_shift)
+ goto out;
+
+ /* List is ordered by old_chunk */
+ list_for_each_entry_reverse(e, l, hash_list) {
+ /* Insert after an existing chunk? */
+ if (new_e->old_chunk == (e->old_chunk +
+ dm_consecutive_chunk_count(e) + 1) &&
+ new_e->new_chunk == (dm_chunk_number(e->new_chunk) +
+ dm_consecutive_chunk_count(e) + 1)) {
+ dm_consecutive_chunk_count_inc(e);
+ free_exception(new_e);
+ return;
+ }
+
+ /* Insert before an existing chunk? */
+ if (new_e->old_chunk == (e->old_chunk - 1) &&
+ new_e->new_chunk == (dm_chunk_number(e->new_chunk) - 1)) {
+ dm_consecutive_chunk_count_inc(e);
+ e->old_chunk--;
+ e->new_chunk--;
+ free_exception(new_e);
+ return;
+ }
+
+ if (new_e->old_chunk > e->old_chunk)
+ break;
+ }
+
+out:
+ list_add(&new_e->hash_list, e ? &e->hash_list : l);
+}
+
int dm_add_exception(struct dm_snapshot *s, chunk_t old, chunk_t new)
{
struct dm_snap_exception *e;
@@ -316,8 +364,12 @@
return -ENOMEM;
e->old_chunk = old;
+
+ /* Consecutive_count is implicitly initialised to zero */
e->new_chunk = new;
- insert_exception(&s->complete, e);
+
+ insert_completed_exception(s, e);
+
return 0;
}
@@ -352,7 +404,8 @@
hash_size = min(hash_size, max_buckets);
hash_size = rounddown_pow_of_two(hash_size);
- if (init_exception_table(&s->complete, hash_size))
+ if (init_exception_table(&s->complete, hash_size,
+ DM_CHUNK_CONSECUTIVE_BITS))
return -ENOMEM;
/*
@@ -363,7 +416,7 @@
if (hash_size < 64)
hash_size = 64;
- if (init_exception_table(&s->pending, hash_size)) {
+ if (init_exception_table(&s->pending, hash_size, 0)) {
exit_exception_table(&s->complete, exception_cache);
return -ENOMEM;
}
@@ -722,7 +775,7 @@
* Add a proper exception, and remove the
* in-flight exception from the list.
*/
- insert_exception(&s->complete, e);
+ insert_completed_exception(s, e);
out:
remove_exception(&pe->e);
@@ -856,11 +909,12 @@
}
static void remap_exception(struct dm_snapshot *s, struct dm_snap_exception *e,
- struct bio *bio)
+ struct bio *bio, chunk_t chunk)
{
bio->bi_bdev = s->cow->bdev;
- bio->bi_sector = chunk_to_sector(s, e->new_chunk) +
- (bio->bi_sector & s->chunk_mask);
+ bio->bi_sector = chunk_to_sector(s, dm_chunk_number(e->new_chunk) +
+ (chunk - e->old_chunk)) +
+ (bio->bi_sector & s->chunk_mask);
}
static int snapshot_map(struct dm_target *ti, struct bio *bio,
@@ -891,7 +945,7 @@
/* If the block is already remapped - use that, else remap it */
e = lookup_exception(&s->complete, chunk);
if (e) {
- remap_exception(s, e, bio);
+ remap_exception(s, e, bio, chunk);
goto out_unlock;
}
@@ -908,7 +962,7 @@
goto out_unlock;
}
- remap_exception(s, &pe->e, bio);
+ remap_exception(s, &pe->e, bio, chunk);
bio_list_add(&pe->snapshot_bios, bio);
r = DM_MAPIO_SUBMITTED;
@@ -1196,7 +1250,7 @@
static struct target_type origin_target = {
.name = "snapshot-origin",
- .version = {1, 5, 0},
+ .version = {1, 6, 0},
.module = THIS_MODULE,
.ctr = origin_ctr,
.dtr = origin_dtr,
@@ -1207,7 +1261,7 @@
static struct target_type snapshot_target = {
.name = "snapshot",
- .version = {1, 5, 0},
+ .version = {1, 6, 0},
.module = THIS_MODULE,
.ctr = snapshot_ctr,
.dtr = snapshot_dtr,