qcow2: Patch for shrinking qcow2 disk image

This patch is the realization of new function qcow2_shrink_l1_and_l2_table. This function will shrink/discard l1 and l2 table when do qcow2 shrinking.

Signed-off-by Jun Li <[email protected]>

---
v5:
Do some modifications based on MAX's suggestion. Thanks for MAX.
In v5, do l2 shrinking firstly, then do l1 shrinking in function qcow2_shrink_l1_and_l2_table. As do l1 shrinking need to allocate some clusters for new l1 table, so in v5 it can re-use the freed clusters come from l2 shrinking.

v4:
Add deal with COW clusters in l2 table. When using COW, some of (l2_entry >>
s->cluster_bits) will larger than s->refcount_table_size, so need to discard this l2_entry.

v3:
Fixed host cluster leak.

---
  block/qcow2-cluster.c | 182 ++++++++++++++++++++++++++++++++++++++++++++++++++
  block/qcow2.c         |  37 +++++++++-
  block/qcow2.h         |   2 +
  3 files changed, 218 insertions(+), 3 deletions(-)

block/qcow2-cluster.c +3 -0

index 4d888c7..28d2d62 100644
@@ -29,6 +29,9 @@
  #include "block/qcow2.h"
  #include "trace.h"
 
+static int l2_load(BlockDriverState *bs, uint64_t l2_offset,
+                   uint64_t **l2_table);
+
  int qcow2_grow_l1_table(BlockDriverState *bs, uint64_t min_size,
                          bool exact_size)
  {

block/qcow2-cluster.c +25 -0

+    uint64_t *new_l1_table;
+    int64_t new_l1_table_offset;
+    int64_t old_l1_table_offset, old_l1_size;
+    uint8_t data[12];
+    uint64_t l2_offset;
+    uint64_t *l2_table, l2_entry;
+    int64_t l2_free_entry; /* The entry of l2 table need to free from */
+    uint64_t *old_l1_table = s->l1_table;
+    int num = s->l1_size - new_l1_size;
+
+    assert(new_l1_size <= s->l1_size);
+    while ((num >= -1) && (s->l1_size + num - 1 >= 0)) {
+        l2_free_entry = 0;
+        l2_offset = old_l1_table[s->l1_size + num - 1] & L1E_OFFSET_MASK;
+
+        if (l2_offset == 0) {
+            goto retry;
+        }
+
+        if (num == 0) {
+            if (new_l2_index == 0) {
+                goto retry;
+            }
+            l2_free_entry = new_l2_index;
+        }

block/qcow2-cluster.c +43 -0

+                    goto free_cluster;
+                } else {
+                    continue;
+                }
+            }
+
+            /* Deal with COW clusters in l2 table when num == 0 */
+            if (i <= l2_free_entry - 1) {
+                if (l2_entry >= boundary_size) {
+                    goto free_cluster;
+                }
+                continue;
+            }
+
+            switch (qcow2_get_cluster_type(l2_entry)) {
+            case QCOW2_CLUSTER_UNALLOCATED:
+                if (!bs->backing_hd) {
+                    continue;
+                }
+                break;
+
+            case QCOW2_CLUSTER_ZERO:
+                continue;
+
+            case QCOW2_CLUSTER_NORMAL:
+            case QCOW2_CLUSTER_COMPRESSED:
+                break;
+
+            default:
+                abort();
+            }
+
+        free_cluster:
+            qcow2_cache_entry_mark_dirty(s->l2_table_cache, l2_table);
+
+            if (s->qcow_version >= 3) {
+                l2_table[i] = cpu_to_be64(QCOW_OFLAG_ZERO);
+            } else {
+                l2_table[i] = cpu_to_be64(0);
+            }
+
+            /* Then decrease the refcount */
+            qcow2_free_any_clusters(bs, l2_entry, 1, QCOW2_DISCARD_MAX);

block/qcow2-cluster.c +17 -0

+        }
+    retry:
+        num--;
+    }
+
+    new_l1_size2 = sizeof(uint64_t) * new_l1_size;
+    new_l1_table = qemu_try_blockalign(bs->file,
+                                       align_offset(new_l1_size2, 512));
+    if (new_l1_table == NULL) {
+        return -ENOMEM;
+    }
+    memset(new_l1_table, 0, align_offset(new_l1_size2, 512));
+
+    /* shrinking l1 table */
+    memcpy(new_l1_table, s->l1_table, new_l1_size2);
+
+    /* write new table (align to cluster) */

block/qcow2-cluster.c +25 -0

+
+    /* the L1 position has not yet been updated, so these clusters must
+     * indeed be completely free */
+    ret = qcow2_pre_write_overlap_check(bs, 0, new_l1_table_offset,
+                                        new_l1_size2);
+
+    if (ret < 0) {
+        goto fail;
+    }
+
+    BLKDBG_EVENT(bs->file, BLKDBG_L1_GROW_WRITE_TABLE);
+
+    for (i = 0; i < new_l1_size; i++) {
+        new_l1_table[i] = cpu_to_be64(new_l1_table[i]);
+    }
+
+    ret = bdrv_pwrite_sync(bs->file, new_l1_table_offset,
+                           new_l1_table, new_l1_size2);
+    if (ret < 0) {
+        goto fail;
+    }
+
+    for (i = 0; i < new_l1_size; i++) {
+        new_l1_table[i] = be64_to_cpu(new_l1_table[i]);
+    }

block/qcow2-cluster.c +17 -0

+
+    qemu_vfree(s->l1_table);
+    old_l1_table_offset = s->l1_table_offset;
+    s->l1_table_offset = new_l1_table_offset;
+    s->l1_table = new_l1_table;
+    old_l1_size = s->l1_size;
+    s->l1_size = new_l1_size;
+    qcow2_free_clusters(bs, old_l1_table_offset, old_l1_size * sizeof(uint64_t),
+                        QCOW2_DISCARD_OTHER);
+    return 0;
+ fail:
+    qemu_vfree(new_l1_table);
+    qcow2_free_clusters(bs, new_l1_table_offset, new_l1_size2,
+                        QCOW2_DISCARD_OTHER);
+    return ret;
+}
+
  /*
   * l2_load
   *

block/qcow2.c +7 -3

index d031515..d2b0dfe 100644
@@ -2111,10 +2111,41 @@ static int qcow2_truncate(BlockDriverState *bs, int64_t offset)
          return -ENOTSUP;
      }
 
-    /* shrinking is currently not supported */
+    /* shrinking image */
      if (offset < bs->total_sectors * 512) {
-        error_report("qcow2 doesn't support shrinking images yet");
-        return -ENOTSUP;
+        /* As l1 table, l2 table, refcount table, refcount block table
+         * and file header of the qcow2 image need to use some clusters,
+         * so should subtract these metadata from offset.
+         */
+        int64_t nb_l1 = DIV_ROUND_UP((uint64_t)s->l1_size * sizeof(uint64_t),
+                                     s->cluster_size);

block/qcow2.c +7 -0

+        int new_l2_index = offset_to_l2_index(s, offset_for_shrink);
+
+        new_l1_size = size_to_l1(s, offset_for_shrink);
+        ret = qcow2_shrink_l1_and_l2_table(bs, new_l1_size, new_l2_index,
+                                           offset);
+        if (ret < 0) {
+            return ret;

block/qcow2.c +0 -0

      }
 
      new_l1_size = size_to_l1(s, offset);

block/qcow2.h +0 -0

index 577ccd1..be1237d 100644

Second, why are you truncating the file to offset if offset is smaller than actual_size? That is always wrong. You are blindly assuming:
(1) that the image consists of only data and no metadata, because you're using the guest disk size (offset) to shrink the host file
(2) that all that data is tightly packed at the beginning of the file

(1) is obviously wrong. (2) is wrong as well, because clusters may be spread all over the host file. We would need defragmentation to solve that issue.

Therefore, to shorten the host file, you'd need to walk through the image and find the highest *host* cluster actually in use. Then you can truncate to after that cluster. However, I'd strongly advise against that because it doesn't bring any actual benefit.

So, as for what I think we do need to do when shrinking (and keep in
mind: The offset given to qcow2_truncate() is the guest size! NOT the host image size!):

(1) Determine the first L2 table and the first entry in the table which will lie beyond the new guest disk size.
(2) Discard all clusters beginning from there.
(3) Discard all L2 tables which are then completely empty.

(4) Update the header size.

And that's it. We can either speed up step (2) by implementing it manually, or we just use bdrv_discard() on the qcow2 BDS (in the simplest case: bdrv_discard(bs, DIV_ROUND_UP(offset, BDRV_SECTOR_SIZE), bs->total_sectors - DIV_ROUND_UP(offset, BDRV_SECTOR_SIZE));.

We can incorporate step (3) by extending qcow2_discard_clusters() to free L2 tables when they are empty after discard_single_l2(). But we don't even have to that now. It's an optimization we can go about later.

There is one advantage:
- It's extremely simple. It's literally below ten lines of code.

I think the advantage far outweighs the disadvantage. But I may be wrong. What do you think?

Quoted 36 lines · Jun Li

This patch is the realization of new function qcow2_shrink_l1_and_l2_table. This function will shrink/discard l1 and l2 table when do qcow2 shrinking.

Signed-off-by Jun Li <[email protected]>

---
v5:
Do some modifications based on MAX's suggestion. Thanks for MAX.
In v5, do l2 shrinking firstly, then do l1 shrinking in function qcow2_shrink_l1_and_l2_table. As do l1 shrinking need to allocate some clusters for new l1 table, so in v5 it can re-use the freed clusters come from l2 shrinking.

v4:
Add deal with COW clusters in l2 table. When using COW, some of (l2_entry >>
s->cluster_bits) will larger than s->refcount_table_size, so need to discard this l2_entry.

v3:
Fixed host cluster leak.

---
 block/qcow2-cluster.c | 182 ++++++++++++++++++++++++++++++++++++++++++++++++++
 block/qcow2.c         |  37 +++++++++-
 block/qcow2.h         |   2 +
 3 files changed, 218 insertions(+), 3 deletions(-)

block/qcow2-cluster.c +3 -0

index 4d888c7..28d2d62 100644
@@ -29,6 +29,9 @@
 #include "block/qcow2.h"
 #include "trace.h"
+static int l2_load(BlockDriverState *bs, uint64_t l2_offset,
+                   uint64_t **l2_table);
+
 int qcow2_grow_l1_table(BlockDriverState *bs, uint64_t min_size,
                         bool exact_size)
 {

block/qcow2-cluster.c int qcow2_grow_l1_table(BlockDriverState *bs, uint64_t min_size, · line 144

Quoted 7 lines

block/qcow2-cluster.c +5 -0

@@ -135,6 +138,185 @@ int qcow2_grow_l1_table(BlockDriverState *bs, uint64_t min_size,
     return ret;
 }
+int qcow2_shrink_l1_and_l2_table(BlockDriverState *bs, uint64_t new_l1_size,
+                                 int new_l2_index, int64_t boundary_size)
+{
+    BDRVQcowState *s = bs->opaque;
+    int new_l1_size2, ret, i;

gcc gives me a warning (which is made an error by -Werror) here due to uninitialized use of "ret". "ret" is not necessarily set in the while () loop and there are some "goto fail"s afterwards which do not set it.

Quoted 25 lines

block/qcow2-cluster.c +25 -0

+    uint64_t *new_l1_table;
+    int64_t new_l1_table_offset;
+    int64_t old_l1_table_offset, old_l1_size;
+    uint8_t data[12];
+    uint64_t l2_offset;
+    uint64_t *l2_table, l2_entry;
+    int64_t l2_free_entry; /* The entry of l2 table need to free from */
+    uint64_t *old_l1_table = s->l1_table;
+    int num = s->l1_size - new_l1_size;
+
+    assert(new_l1_size <= s->l1_size);
+    while ((num >= -1) && (s->l1_size + num - 1 >= 0)) {
+        l2_free_entry = 0;
+        l2_offset = old_l1_table[s->l1_size + num - 1] & L1E_OFFSET_MASK;
+
+        if (l2_offset == 0) {
+            goto retry;
+        }
+
+        if (num == 0) {
+            if (new_l2_index == 0) {
+                goto retry;
+            }
+            l2_free_entry = new_l2_index;
+        }

block/qcow2-cluster.c int qcow2_grow_l1_table(BlockDriverState *bs, uint64_t min_size, · line 180

Quoted 10 lines

block/qcow2-cluster.c +10 -0

+
+        /* load l2_table into cache */
+        ret = l2_load(bs, l2_offset, &l2_table);
+
+        if (ret < 0) {
+            return ret;
+        }
+
+        for (i = s->l2_size - 1; i >= 0; i--) {
+            l2_entry = be64_to_cpu(l2_table[i]);

& L2E_OFFSET_MASK is missing. OFLAG_COPIED will break this without.

block/qcow2-cluster.c int qcow2_grow_l1_table(BlockDriverState *bs, uint64_t min_size, · line 187

Quoted 7 lines

block/qcow2-cluster.c +7 -0

+
+            /* Due to COW, the clusters in l2 table will
+             * not in sequential order, so there will be
+             * some l2_entry >= boundary_size when perform shrinking.
+             */
+            if (num == -1) {
+                if (l2_entry >= boundary_size) {

boundary_size is set to "offset" by the caller. "offset" is the guest disk size. l2_entry (or should be) a host offset. They are not comparable.

Quoted 43 lines

block/qcow2-cluster.c +43 -0

+                    goto free_cluster;
+                } else {
+                    continue;
+                }
+            }
+
+            /* Deal with COW clusters in l2 table when num == 0 */
+            if (i <= l2_free_entry - 1) {
+                if (l2_entry >= boundary_size) {
+                    goto free_cluster;
+                }
+                continue;
+            }
+
+            switch (qcow2_get_cluster_type(l2_entry)) {
+            case QCOW2_CLUSTER_UNALLOCATED:
+                if (!bs->backing_hd) {
+                    continue;
+                }
+                break;
+
+            case QCOW2_CLUSTER_ZERO:
+                continue;
+
+            case QCOW2_CLUSTER_NORMAL:
+            case QCOW2_CLUSTER_COMPRESSED:
+                break;
+
+            default:
+                abort();
+            }
+
+        free_cluster:
+            qcow2_cache_entry_mark_dirty(s->l2_table_cache, l2_table);
+
+            if (s->qcow_version >= 3) {
+                l2_table[i] = cpu_to_be64(QCOW_OFLAG_ZERO);
+            } else {
+                l2_table[i] = cpu_to_be64(0);
+            }
+
+            /* Then decrease the refcount */
+            qcow2_free_any_clusters(bs, l2_entry, 1, QCOW2_DISCARD_MAX);

block/qcow2-cluster.c int qcow2_grow_l1_table(BlockDriverState *bs, uint64_t min_size, · line 240

Quoted 10 lines

block/qcow2-cluster.c +10 -0

+        }
+
+        ret = qcow2_cache_put(bs, s->l2_table_cache, (void **) &l2_table);
+        if (ret < 0) {
+            return ret;
+        }
+        if (l2_free_entry == 0 && num != -1) {
+            qemu_vfree(l2_table);
+            qcow2_free_clusters(bs, l2_offset, s->cluster_size - 1,
+                                QCOW2_DISCARD_OTHER);

You should probably flush the L2 cache before you do that.

Quoted 17 lines

block/qcow2-cluster.c +17 -0

+        }
+    retry:
+        num--;
+    }
+
+    new_l1_size2 = sizeof(uint64_t) * new_l1_size;
+    new_l1_table = qemu_try_blockalign(bs->file,
+                                       align_offset(new_l1_size2, 512));
+    if (new_l1_table == NULL) {
+        return -ENOMEM;
+    }
+    memset(new_l1_table, 0, align_offset(new_l1_size2, 512));
+
+    /* shrinking l1 table */
+    memcpy(new_l1_table, s->l1_table, new_l1_size2);
+
+    /* write new table (align to cluster) */

block/qcow2-cluster.c int qcow2_grow_l1_table(BlockDriverState *bs, uint64_t min_size, · line 267

Quoted 10 lines

block/qcow2-cluster.c +10 -0

+    new_l1_table_offset = qcow2_alloc_clusters(bs, new_l1_size2);
+
+    if ((new_l1_table_offset) >= boundary_size) {
+        goto fail;
+    }
+
+    ret = qcow2_cache_flush(bs, s->refcount_block_cache);
+    if (ret < 0) {
+        goto fail;
+    }

You don't need to flush the refblock cache.

Quoted 25 lines

block/qcow2-cluster.c +25 -0

+
+    /* the L1 position has not yet been updated, so these clusters must
+     * indeed be completely free */
+    ret = qcow2_pre_write_overlap_check(bs, 0, new_l1_table_offset,
+                                        new_l1_size2);
+
+    if (ret < 0) {
+        goto fail;
+    }
+
+    BLKDBG_EVENT(bs->file, BLKDBG_L1_GROW_WRITE_TABLE);
+
+    for (i = 0; i < new_l1_size; i++) {
+        new_l1_table[i] = cpu_to_be64(new_l1_table[i]);
+    }
+
+    ret = bdrv_pwrite_sync(bs->file, new_l1_table_offset,
+                           new_l1_table, new_l1_size2);
+    if (ret < 0) {
+        goto fail;
+    }
+
+    for (i = 0; i < new_l1_size; i++) {
+        new_l1_table[i] = be64_to_cpu(new_l1_table[i]);
+    }

block/qcow2-cluster.c int qcow2_grow_l1_table(BlockDriverState *bs, uint64_t min_size, · line 302

Quoted 10 lines

block/qcow2-cluster.c +10 -0

+
+    /* set new table */
+    BLKDBG_EVENT(bs->file, BLKDBG_L1_GROW_ACTIVATE_TABLE);
+    cpu_to_be32w((uint32_t *)data, new_l1_size);
+    stq_be_p(data + 4, new_l1_table_offset);
+    ret = bdrv_pwrite_sync(bs->file, offsetof(QCowHeader, l1_size),
+                           data, sizeof(data));
+    if (ret < 0) {
+        goto fail;
+    }

I understand your intent with writing a new L1 table. But I don't see the need. With 64 kB clusters, a 64 kB L1 table can serve an image with 4 TB guest size (8192 L2 tables, each having 8192 entries). I don't think we'll gain a lot from shrinking the L1 table. It's too much effort.

Quoted 38 lines

block/qcow2-cluster.c +17 -0

+
+    qemu_vfree(s->l1_table);
+    old_l1_table_offset = s->l1_table_offset;
+    s->l1_table_offset = new_l1_table_offset;
+    s->l1_table = new_l1_table;
+    old_l1_size = s->l1_size;
+    s->l1_size = new_l1_size;
+    qcow2_free_clusters(bs, old_l1_table_offset, old_l1_size * sizeof(uint64_t),
+                        QCOW2_DISCARD_OTHER);
+    return 0;
+ fail:
+    qemu_vfree(new_l1_table);
+    qcow2_free_clusters(bs, new_l1_table_offset, new_l1_size2,
+                        QCOW2_DISCARD_OTHER);
+    return ret;
+}
+
 /*
  * l2_load
  *

block/qcow2.c +7 -3

index d031515..d2b0dfe 100644
@@ -2111,10 +2111,41 @@ static int qcow2_truncate(BlockDriverState *bs, int64_t offset)
         return -ENOTSUP;
     }
-    /* shrinking is currently not supported */
+    /* shrinking image */
     if (offset < bs->total_sectors * 512) {
-        error_report("qcow2 doesn't support shrinking images yet");
-        return -ENOTSUP;
+        /* As l1 table, l2 table, refcount table, refcount block table
+         * and file header of the qcow2 image need to use some clusters,
+         * so should subtract these metadata from offset.
+         */
+        int64_t nb_l1 = DIV_ROUND_UP((uint64_t)s->l1_size * sizeof(uint64_t),
+                                     s->cluster_size);

block/qcow2.c static int qcow2_truncate(BlockDriverState *bs, int64_t offset) · line 2130

Quoted 10 lines

block/qcow2.c +10 -0

+        int64_t nb_l2 = DIV_ROUND_UP(offset, (uint64_t)s->l2_size <<
+                                     s->cluster_bits);
+        int64_t nb_refcount_block_table = DIV_ROUND_UP(offset, (uint64_t)
+                                                       s->cluster_size <<
+                                                       s->refcount_block_bits);
+        int64_t nb_refcount_table = DIV_ROUND_UP(nb_refcount_block_table << 3,
+                                                 s->cluster_size);
+        int64_t total_nb = 2 * nb_l2 + nb_l1 + nb_refcount_block_table +
+                           nb_refcount_table + 1;
+        int64_t offset_for_shrink = offset - (total_nb << s->cluster_bits);

Okay, what does total_nb have to do with offset?

total_nb is some host value. offset is a guest value. Don't mix them.

Quoted 7 lines

block/qcow2.c +7 -0

+        int new_l2_index = offset_to_l2_index(s, offset_for_shrink);
+
+        new_l1_size = size_to_l1(s, offset_for_shrink);
+        ret = qcow2_shrink_l1_and_l2_table(bs, new_l1_size, new_l2_index,
+                                           offset);
+        if (ret < 0) {
+            return ret;

block/qcow2.c static int qcow2_truncate(BlockDriverState *bs, int64_t offset) · line 2148

Quoted 10 lines

block/qcow2.c +10 -0

+        }
+
+        int64_t actual_size = bdrv_get_allocated_file_size(bs);
+
+        if (offset < actual_size) {
+            ret = bdrv_truncate(bs->file, offset);
+            if (ret < 0) {
+                return ret;
+            }
+        }

actual_size is not some offset you can use. It's the number of bytes allocated in the file. The file can contain holes. Therefore, comparing an offset against actual_size is wrong. Second, offset is the guest disk size, actual_size is the host disk size. They are not comparable.

Second, why are you truncating the file to offset if offset is smaller than actual_size? That is always wrong. You are blindly assuming:
(1) that the image consists of only data and no metadata, because you're using the guest disk size (offset) to shrink the host file
(2) that all that data is tightly packed at the beginning of the file

(1) is obviously wrong. (2) is wrong as well, because clusters may be spread all over the host file. We would need defragmentation to solve that issue.

Therefore, to shorten the host file, you'd need to walk through the image and find the highest *host* cluster actually in use. Then you can truncate to after that cluster. However, I'd strongly advise against that because it doesn't bring any actual benefit.

Today's file systems support holes. Just discard all the clusters which get freed during shrinking, that will free up all that space. No need to defragment, no need to truncate. Yes, the file will look larger than it actually is, but nobody should care. We will need defragmentation to tackle that issue.

Quoted 7 lines

block/qcow2.c +0 -0

     }
     new_l1_size = size_to_l1(s, offset);

block/qcow2.h +0 -0

index 577ccd1..be1237d 100644

block/qcow2.h int qcow2_pre_write_overlap_check(BlockDriverState *bs, int ign, int64_t offset, · line 523

Quoted 8 lines

block/qcow2.h +2 -0

@@ -516,6 +516,8 @@ int qcow2_pre_write_overlap_check(BlockDriverState *bs, int ign, int64_t offset,
 /* qcow2-cluster.c functions */
 int qcow2_grow_l1_table(BlockDriverState *bs, uint64_t min_size,
                         bool exact_size);
+int qcow2_shrink_l1_and_l2_table(BlockDriverState *bs, uint64_t new_l1_size,
+                                 int new_l2_index, int64_t boundary_size);
 int qcow2_write_l1_entry(BlockDriverState *bs, int l1_index);
 void qcow2_l2_cache_reset(BlockDriverState *bs);
 int qcow2_decompress_cluster(BlockDriverState *bs, uint64_t cluster_offset);

So, as for what I think we do need to do when shrinking (and keep in mind:
The offset given to qcow2_truncate() is the guest size! NOT the host image size!):

(1) Determine the first L2 table and the first entry in the table which will lie beyond the new guest disk size.

(2) Discard all clusters beginning from there.
(3) Discard all L2 tables which are then completely empty.
(4) Update the header size.

And that's it. We can either speed up step (2) by implementing it manually, or we just use bdrv_discard() on the qcow2 BDS (in the simplest case:
bdrv_discard(bs, DIV_ROUND_UP(offset, BDRV_SECTOR_SIZE), bs->total_sectors - DIV_ROUND_UP(offset, BDRV_SECTOR_SIZE));.

We can incorporate step (3) by extending qcow2_discard_clusters() to free L2 tables when they are empty after discard_single_l2(). But we don't even have to that now. It's an optimization we can go about later.

So, we can do (1), (2) and (3) in a single step: Just one bdrv_discard() call. But it's probably better to use qcow2_discard_clusters() instead and set the full_discard parameter to true.

So: qcow2_discard_clusters(bs, offset, bs->total_sectors - offset / BDRV_SECTOR_SIZE, true);. Then update the guest disk size field in the header. And we're done.

There are four problems with this approach:
- qcow2_discard_clusters() might be slower than optimal. I personally don't care at all.
- If "bs->total_sectors * BDRV_SECTOR_SIZE - offset" is greater than INT_MAX, this won't work. Trivially solvable by encapsulating the qcow2_discard_clusters() call in a loop which limits nb_clusters to INT_MAX / BDRV_SECTOR_SIZE.
- The L1 table is not resized. Should not matter in practice at all.

- The file is not truncated. Does not matter either (because holes in the file are good enough), and we can't actually solve this problem without defragmentation anyway.

There is one advantage:
- It's extremely simple. It's literally below ten lines of code.

I think the advantage far outweighs the disadvantage. But I may be wrong. What do you think?

Quoted 6 lines · Max Reitz

So, as for what I think we do need to do when shrinking (and keep in mind:
The offset given to qcow2_truncate() is the guest size! NOT the host image size!):

(1) Determine the first L2 table and the first entry in the table which will lie beyond the new guest disk size.

Here is not correct always. Due to the COW, using offset to calculate the first entry of the first L2 table will be incorrect.

What I have done for this scenario:
(1) if the first entry is the first entry of the L2 table, so will scan "the previous L2 table"("the previous L2 table" location is in front of "L2 table" in L1 table). If the entry of previous L2 table is larger than offset, will discard this entry, too.
(2) If the first entry is not the first entry of the L2 table, still to scan the whole L2 table to make sure no entry is beyond offset.

Quoted 3 lines

(2) Discard all clusters beginning from there.
(3) Discard all L2 tables which are then completely empty.
(4) Update the header size.

For this patch current's realizion, have include above 4 steps I think. Current patch, also have another step 5.
(5) truncate the file.

Here I think we also should add discard refcount table and refcount block table when they are completely empty.

Quoted 17 lines

And that's it. We can either speed up step (2) by implementing it manually, or we just use bdrv_discard() on the qcow2 BDS (in the simplest case:
bdrv_discard(bs, DIV_ROUND_UP(offset, BDRV_SECTOR_SIZE), bs->total_sectors - DIV_ROUND_UP(offset, BDRV_SECTOR_SIZE));.

We can incorporate step (3) by extending qcow2_discard_clusters() to free L2 tables when they are empty after discard_single_l2(). But we don't even have to that now. It's an optimization we can go about later.

So, we can do (1), (2) and (3) in a single step: Just one bdrv_discard() call. But it's probably better to use qcow2_discard_clusters() instead and set the full_discard parameter to true.

So: qcow2_discard_clusters(bs, offset, bs->total_sectors - offset / BDRV_SECTOR_SIZE, true);. Then update the guest disk size field in the header. And we're done.

Quoted 8 lines

There are four problems with this approach:
- qcow2_discard_clusters() might be slower than optimal. I personally don't care at all.
- If "bs->total_sectors * BDRV_SECTOR_SIZE - offset" is greater than INT_MAX, this won't work. Trivially solvable by encapsulating the qcow2_discard_clusters() call in a loop which limits nb_clusters to INT_MAX / BDRV_SECTOR_SIZE.
- The L1 table is not resized. Should not matter in practice at all.

Yes, agree with you.

Quoted 7 lines

- The file is not truncated. Does not matter either (because holes in the file are good enough), and we can't actually solve this problem without defragmentation anyway.

There is one advantage:
- It's extremely simple. It's literally below ten lines of code.

Quoted 2 lines

I think the advantage far outweighs the disadvantage. But I may be wrong. What do you think?

Hi max,

Sorry for so late to reply as I am so busy recently. I think let's have an
agreement on how to realize qcow2 shrinking first, then type code is better.

Another issue, as gmail can not be used in current China, I have to use this email to reply. :)

Quoted 9 lines · Jun Li

Quoted 6 lines · Max Reitz

So, as for what I think we do need to do when shrinking (and keep in mind:
The offset given to qcow2_truncate() is the guest size! NOT the host image size!):

(1) Determine the first L2 table and the first entry in the table which will lie beyond the new guest disk size.

Here is not correct always. Due to the COW, using offset to calculate the first entry of the first L2 table will be incorrect.

Again: This is *not* about the host disk size or the host offset of some cluster, but about the *guest* disk size.

Let's make up an example. You have a 2 GB disk but you want to resize it to 1.25 GB. The cluster size is 64 kB, therefore we have 2 GB / 64 kB = 32,768 data clusters (as long as there aren't any internal snapshots, which is a prerequisite for resizing qcow2 images).

Every L2 table contains 65,536 / 8 = 8,192 entries; there are thus 32,768 / 8,192 = 4 L2 tables.

As you can see, one can directly derive the number of data clusters and L2 tables from the guest disk size (as long as there aren't any internal snapshots).

So of course we can do the same for the target disk size: 1.25 GB / 64 kB = 20,480 data clusters; 20,480 / 8,192 = 2.5 L2 tables, therefore we need three L2 tables but only half of the last one (4,096 entries).

We know that every cluster references somewhere after that limit (that is, every entry in the fourth L2 table and every entry starting with index 4,096 in the third L2 table) is a data cluster with a guest offset somewhere beyond 1.25 GB, so we don't need it anymore.

Thus, we simply discard all those data clusters and after that we can discard the fourth L2 table. That's it.

If we really want to we can calculate the highest cluster host offset in use and truncate the image accordingly. But that's optional, see the last point in my "problems with this approach" list (having discarded the clusters should save us all the space already). Furthermore, as I'm saying in that list, to really solve this issue, we'd need qcow2 defragmentation.

Quoted 8 lines

What I have done for this scenario:
(1) if the first entry is the first entry of the L2 table, so will scan "the previous L2 table"("the previous L2 table" location is in front of "L2 table" in L1 table). If the entry of previous L2 table is larger than offset, will discard this entry, too.
(2) If the first entry is not the first entry of the L2 table, still to scan the whole L2 table to make sure no entry is beyond offset.

Quoted 6 lines

Quoted 3 lines

(2) Discard all clusters beginning from there.
(3) Discard all L2 tables which are then completely empty.
(4) Update the header size.

For this patch current's realizion, have include above 4 steps I think. Current patch, also have another step 5.
(5) truncate the file.

As I wrote above, you can do that but it shouldn't matter much because the discarded clusters should not use any disk space.

Quoted 37 lines

Here I think we also should add discard refcount table and refcount block table when they are completely empty.

Quoted 17 lines

And that's it. We can either speed up step (2) by implementing it manually, or we just use bdrv_discard() on the qcow2 BDS (in the simplest case:
bdrv_discard(bs, DIV_ROUND_UP(offset, BDRV_SECTOR_SIZE), bs->total_sectors - DIV_ROUND_UP(offset, BDRV_SECTOR_SIZE));.

We can incorporate step (3) by extending qcow2_discard_clusters() to free L2 tables when they are empty after discard_single_l2(). But we don't even have to that now. It's an optimization we can go about later.

So, we can do (1), (2) and (3) in a single step: Just one bdrv_discard() call. But it's probably better to use qcow2_discard_clusters() instead and set the full_discard parameter to true.

So: qcow2_discard_clusters(bs, offset, bs->total_sectors - offset / BDRV_SECTOR_SIZE, true);. Then update the guest disk size field in the header. And we're done.

Quoted 8 lines

There are four problems with this approach:
- qcow2_discard_clusters() might be slower than optimal. I personally don't care at all.
- If "bs->total_sectors * BDRV_SECTOR_SIZE - offset" is greater than INT_MAX, this won't work. Trivially solvable by encapsulating the qcow2_discard_clusters() call in a loop which limits nb_clusters to INT_MAX / BDRV_SECTOR_SIZE.
- The L1 table is not resized. Should not matter in practice at all.

Yes, agree with you.

Quoted 7 lines

- The file is not truncated. Does not matter either (because holes in the file are good enough), and we can't actually solve this problem without defragmentation anyway.

There is one advantage:
- It's extremely simple. It's literally below ten lines of code.

Quoted 6 lines

Quoted 2 lines

I think the advantage far outweighs the disadvantage. But I may be wrong. What do you think?

Hi max,

Sorry for so late to reply as I am so busy recently. I think let's have an
agreement on how to realize qcow2 shrinking first, then type code is better.

Yes, this will probably be for the best. :-)

Quoted 2 lines

Another issue, as gmail can not be used in current China, I have to use this email to reply. :)

No problem.

Max

Quoted 21 lines · Max Reitz

Quoted 9 lines · Jun Li

Quoted 6 lines · Max Reitz

So, as for what I think we do need to do when shrinking (and keep in mind:
The offset given to qcow2_truncate() is the guest size! NOT the host image size!):

(1) Determine the first L2 table and the first entry in the table which will lie beyond the new guest disk size.

Here is not correct always. Due to the COW, using offset to calculate the first entry of the first L2 table will be incorrect.

Again: This is *not* about the host disk size or the host offset of some cluster, but about the *guest* disk size.

Let's make up an example. You have a 2 GB disk but you want to resize it to 1.25 GB. The cluster size is 64 kB, therefore we have 2 GB / 64 kB = 32,768 data clusters (as long as there aren't any internal snapshots, which is a prerequisite for resizing qcow2 images).

Every L2 table contains 65,536 / 8 = 8,192 entries; there are thus 32,768 / 8,192 = 4 L2 tables.

Quoted 8 lines

As you can see, one can directly derive the number of data clusters and L2 tables from the guest disk size (as long as there aren't any internal snapshots).

So of course we can do the same for the target disk size: 1.25 GB / 64 kB = 20,480 data clusters; 20,480 / 8,192 = 2.5 L2 tables, therefore we need three L2 tables but only half of the last one (4,096 entries).

Sorry, last time is my mis-understanding. If do not use qcow2_truncate(), I think don't existing above issue.

For my original thought, I want to say:
Sometimes the second L2 table will contain some entry, the pointer in this entry will point to a cluster which address is larger than 1.25 GB.

So if not use qcow2_truncate(), won't discard above cluster which address is larger than 1.25 GB.

But I still have another worry.

Suppose "virtual size" and "disk size" are all 2G. After we resize it to 1.25G, seems we will get "virtual size" is 1.25G but "disk size" is still 2G

if do not use "qcow2_truncate()" to truncate the file(Yes, I know use qcow2_truncate is not a resolution). This seems strange, not so perfect.

Quoted 8 lines

We know that every cluster references somewhere after that limit (that is, every entry in the fourth L2 table and every entry starting with index 4,096 in the third L2 table) is a data cluster with a guest offset somewhere beyond 1.25 GB, so we don't need it anymore.

Thus, we simply discard all those data clusters and after that we can discard the fourth L2 table. That's it.

Quoted 6 lines

If we really want to we can calculate the highest cluster host offset in use and truncate the image accordingly. But that's optional, see the last point in my "problems with this approach" list (having discarded the clusters should save us all the space already). Furthermore, as I'm saying in that list, to really solve this issue, we'd need qcow2 defragmentation.

Do we already have "qcow2 defragmentation" realization?

Jun Li

Quoted 30 lines · Jun Li

Quoted 29 lines · Max Reitz

Quoted 9 lines · Jun Li

Quoted 6 lines · Max Reitz

So, as for what I think we do need to do when shrinking (and keep in mind:
The offset given to qcow2_truncate() is the guest size! NOT the host image size!):

(1) Determine the first L2 table and the first entry in the table which will lie beyond the new guest disk size.

Here is not correct always. Due to the COW, using offset to calculate the first entry of the first L2 table will be incorrect.

Again: This is *not* about the host disk size or the host offset of some cluster, but about the *guest* disk size.

Let's make up an example. You have a 2 GB disk but you want to resize it to 1.25 GB. The cluster size is 64 kB, therefore we have 2 GB / 64 kB = 32,768 data clusters (as long as there aren't any internal snapshots, which is a prerequisite for resizing qcow2 images).

Every L2 table contains 65,536 / 8 = 8,192 entries; there are thus 32,768 / 8,192 = 4 L2 tables.

As you can see, one can directly derive the number of data clusters and L2 tables from the guest disk size (as long as there aren't any internal snapshots).

So of course we can do the same for the target disk size: 1.25 GB / 64 kB = 20,480 data clusters; 20,480 / 8,192 = 2.5 L2 tables, therefore we need three L2 tables but only half of the last one (4,096 entries).

Quoted 6 lines

Sorry, last time is my mis-understanding. If do not use qcow2_truncate(), I think don't existing above issue.

For my original thought, I want to say:
Sometimes the second L2 table will contain some entry, the pointer in this entry will point to a cluster which address is larger than 1.25 GB.

Correct.

Quoted 2 lines

So if not use qcow2_truncate(), won't discard above cluster which address is larger than 1.25 GB.

I'm sorry, I can't really follow what you are trying to say here, so I'll just try to reply with things that may or may not be what you wanted to talk about.

If you are using qemu-img resize and thus subsequently qcow2_truncate() to shrink an image, you cannot expect the image to shrink to the specified file length, for several reasons.

First, if you shrink it to 1 GB, but only half of that is actually used, the image might of course very well have a length below 1 GB.

Second, there is metadata overhead. So if you are changing the guest disk size to 1 GB (all of which is occupied), the host file size will exceed 1 GB because of that overhead.

Third, I keep repeating myself here, but file length is not file size. So you may observe a file length of 10 GB or more because the clusters are spread all over the image file. This is something we'd have to combat with defragmentation; but the question is whether we really need to (see below for more on that). The point is that it doesn't matter whether the image has a file length of 10 GB; the file size will be around 1 GB anyway.

Quoted 4 lines

But I still have another worry.

Suppose "virtual size" and "disk size" are all 2G. After we resize it to 1.25G, seems we will get "virtual size" is 1.25G but "disk size" is still 2G

No, it won't. I can prove it to you:

$ qemu-img create -f qcow2 test.qcow2 64M
$ qemu-io -c 'write 0 64M' test.qcow2
$ qemu-img info test.qcow2
...
disk size: 64M
...

Okay, so far it's just what we'd expect. Now let's implement my proposal for
truncation: Let's assume the image should be shrinked to 32 MB, so we discard all clusters starting at 32 MB (guest offset) (which is 64 MB - 32 MB = 32 MB of data):

$ qemu-io -c 'discard 32M 32M' test.qcow2
$ qemu-img info test.qcow2
...
disk size: 32M
...

Great!

Quoted 11 lines

if do not use "qcow2_truncate()" to truncate the file(Yes, I know use qcow2_truncate is not a resolution). This seems strange, not so perfect.

Quoted 8 lines

We know that every cluster references somewhere after that limit (that is, every entry in the fourth L2 table and every entry starting with index 4,096 in the third L2 table) is a data cluster with a guest offset somewhere beyond 1.25 GB, so we don't need it anymore.

Thus, we simply discard all those data clusters and after that we can discard the fourth L2 table. That's it.

Quoted 7 lines

Quoted 6 lines

If we really want to we can calculate the highest cluster host offset in use and truncate the image accordingly. But that's optional, see the last point in my "problems with this approach" list (having discarded the clusters should save us all the space already). Furthermore, as I'm saying in that list, to really solve this issue, we'd need qcow2 defragmentation.

Do we already have "qcow2 defragmentation" realization?

No, we don't. The only way to defragment a qcow2 image right now is using qemu-img convert to create a (defragmented) copy and then delete the old image, which has the disadvantage of temporarily requiring double the disk space and being an offline operation.

So far, nobody has implemented online defragmentation, mainly for two
reasons: It would probably be pretty complicated (it'd probably need to be a block job which links into a pretty low-level function provided by qcow2 (defragment_some_clusters or something)) and second, so far there has been little demand. Disk space is not an issue (as said before), because it doesn't really matter to a modern file system whether your file has a length of 100 MB of 100 GB; that's just some number. What really matters is how much of that space is actually used; and if all unused clusters are discarded, there won't be any space used for them (well, maybe there is some metadata overhead, but that should be negligible).

There are a couple of reasons why you'd want to defragment an image:

First, it makes you feel better. I can relate to that, but it's not a real reason.

Second, it may improve performance: The guest may expect consecutive reads to be fast; but if the clusters are sprinkled all over the host, consecutive guest reads no longer necessarily translate to consecutive reads on the host (same for writes, of course). Defragmentation would probably fix that, but if you want to rely on this, you'd better use preallocated image files.

Third, it looks better. People expect the file length to be raw indicator of the file size. However, for me this is related to "it makes you feel better", because this also is not a really good reason.

Fourth, using a non-modern file system may let your file size explode because suddenly, file length is actually equal to the file size. But I think, in this case you should just use a better file system.

I don't know whether "cp" copies holes in files; its manpage says it does create sparse images, but I don't know how well it works; but I just assume it works well enough.

Max

Quoted 1 line

Jun Li

When every item of refcount block is NULL, free refcount block and reset the corresponding item of refcount table with NULL. At the same time, put this cluster to s->free_cluster_index.

Signed-off-by Jun Li <[email protected]>

---
v5:
Just instead write_reftable_entry with bdrv_pwrite_sync. As write_reftable_entry has deleted from the source code.

v4:
Do not change anything for this commit id.

v3:
Add handle self-describing refcount blocks.

---
  block/qcow2-refcount.c | 49 ++++++++++++++++++++++++++++++++++++++++++++++++-
  1 file changed, 48 insertions(+), 1 deletion(-)

block/qcow2-refcount.c +5 -0

+
+                /* update refcount table */
+                s->refcount_table[refcount_table_index] = 0;
+                uint64_t data64 = cpu_to_be64(0);
+                ret = bdrv_pwrite_sync(bs->file,

Quoted 8 lines · Jun Li

When every item of refcount block is NULL, free refcount block and reset the
corresponding item of refcount table with NULL. At the same time, put this
cluster to s->free_cluster_index.

Signed-off-by Jun Li <[email protected]>

---

Quoted 10 lines

block/qcow2-refcount.c +6 -0

+        refcount_table_index = cluster_index >> s->refcount_block_bits;
+
+        uint64_t refcount_block_offset =
+            s->refcount_table[refcount_table_index] & REFT_OFFSET_MASK;
+
+        int64_t self_block_index = refcount_block_offset >>

s->cluster_bits;
+ int self_block_index2 = (refcount_block_offset >>
s->cluster_bits) &
+ ((1 << s->refcount_block_bits) - 1);

You are assuming here that every refblock is described by itself. While that may be true for QEMU's current qcow2 driver, it's by no means defined that way.

So, about this whole patch: I'm not sure whether we need it in this series but I remember you saying that it's actually worth it, so I'm trusting you.

Second, I somehow don't like iterating over the whole refblock for each refcount updated or at least for each refcount set to 0. There are 32768 entries per refblock with 16 bit refcounts and 64 kB clusters. Therefore, when freeing all clusters referenced by a refblock (and if that refblock doesn't have any free entries yet), we will loop over 16384 entries (in average) before noticing there are still entries with a non-zero refcount, and that we will do 32768 times (okay, 32767, because you're assuming a refblock always contains its own refcount). I think that a bit much. But I don't have any idea to fix this other than keeping the number of entries per refblock with refcount != 0 in a table in memory (which is probably not too bad, but not too nice either).

Add qemu-iotests for qcow2 shrinking.
e.g:

$ ./check -qcow2 110

Signed-off-by Jun Li <[email protected]>

---
  tests/qemu-iotests/110     | 76 ++++++++++++++++++++++++++++++++++++++++++++++
  tests/qemu-iotests/110.out | 13 ++++++++
  tests/qemu-iotests/group   |  1 +
  3 files changed, 90 insertions(+)

create mode 100755 tests/qemu-iotests/110
create mode 100644 tests/qemu-iotests/110.out

tests/qemu-iotests/110 new file +47 -0

new file mode 100755
index 0000000..c2145a2
@@ -0,0 +1,76 @@
+#!/bin/bash
+#
+# Tests qcow2 shrinking
+#
+# Copyright (C) 2014 Jun Li ([email protected])
+#
+# This program is free software; you can redistribute it and/or modify
+# it under the terms of the GNU General Public License as published by
+# the Free Software Foundation; either version 2 of the License, or
+# (at your option) any later version.
+#
+# This program is distributed in the hope that it will be useful,
+# but WITHOUT ANY WARRANTY; without even the implied warranty of
+# MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+# GNU General Public License for more details.
+#
+# You should have received a copy of the GNU General Public License
+# along with this program.  If not, see <http://www.gnu.org/licenses/>.
+#
+
+# creator
[email protected]
+
+seq="$(basename $0)"
+echo "QA output created by $seq"
+
+here="$PWD"
+tmp=/tmp/$$
+status=1       # failure is the default!
+
+_cleanup()
+{
+    _cleanup_test_img
+}
+trap "_cleanup; exit \$status" 0 1 2 3 15
+
+# get standard environment, filters and checks
+. ./common.rc
+. ./common.filter
+. ./common.pattern
+
+_supported_fmt qcow2
+_supported_proto file
+_supported_os Linux
+
+
+# Setup test basic parameters

tests/qemu-iotests/110 new file +8 -0

+
+# success, all done
+echo "*** done"
+
+# Cleanup
+_cleanup_test_img
+
+status=0

tests/qemu-iotests/110.out new file +13 -0

new file mode 100644
index 0000000..e54388b
@@ -0,0 +1,13 @@
+QA output created by 110
+
+=== Test qcow2 shrinking ===
+
+Formatting 'TEST_DIR/t.IMGFMT', fmt=IMGFMT size=524288000
+=== IO: pattern 110
+wrote 524288000/524288000 bytes at offset 0
+500 MiB, X ops; XX:XX:XX.X (XXX YYY/sec and XXX ops/sec)
+Image resized.
+No errors were found on the image.
+Image resized.
+No errors were found on the image.
+*** done

tests/qemu-iotests/group +1 -0

index 9bbd5d3..de467ff 100644
@@ -109,3 +109,4 @@
  105 rw auto quick
  107 rw auto quick
  108 rw auto quick
+110 rw auto quick

v5:
Add qemu-iotests for qcow2 shrinking. Do some modifications based on MAX's suggestions in v4.

v4:
Add deal with COW clusters in l2 table. When using COW, some of (l2_entry >>
s->cluster_bits) will larger than s->refcount_table_size, so need to discard this l2_entry.

v3:
Fixed host cluster leak.

In file block/qcow2.c, just using ftruncate to fix host cluster leak.

In file block/qcow2-cluster.c, just re-copy qcow2_grow_l1_table to realize qcow2_shrink_l1_and_l2_table.

In file block/qcow2-refcount.c, also update the realization to handle self-describing refcount blocks in function update_refcount.

Thanks.

Jun Li (3):
qcow2: Add qcow2_shrink_l1_and_l2_table for qcow2 shrinking
qcow2: add update refcount table realization for update_refcount
qcow2: Add qemu-iotests for qcow2 shrinking

 block/qcow2-cluster.c      | 182 +++++++++++++++++++++++++++++++++++++++++++++
 block/qcow2-refcount.c     |  49 +++++++++++-
 block/qcow2.c              |  37 ++++++++-
 block/qcow2.h              |   2 +
 tests/qemu-iotests/110     |  76 +++++++++++++++++++
 tests/qemu-iotests/110.out |  13 ++++
 tests/qemu-iotests/group   |   1 +
 7 files changed, 356 insertions(+), 4 deletions(-)
 create mode 100755 tests/qemu-iotests/110
 create mode 100644 tests/qemu-iotests/110.out

Signature · 1 line

1.9.3

Ping Stefan and Kevin,

Could anyone help to review this version of patch ? Thx.