[RFC PATCH 00/23] Add subcluster allocation to qcow2

[Alberto Garcia]

Hi,

this series adds a new feature to the qcow2 on-disk format called
"Extended L2 Entries", which allows us to do subcluster allocation.

This cover letter explains the reasons behind this proposal, the
changes to the on-disk format, test results and pending work. If you
are curious you can also have a look at previous discussions about
this feature:

   https://lists.gnu.org/archive/html/qemu-block/2017-04/msg00178.html
   https://lists.gnu.org/archive/html/qemu-block/2019-06/msg01155.html

This is the first proper version of the patches, and I believe that
the implementation is complete. However since I'm proposing a change
to the on-disk format I'm labeling this as RFC because I'm expecting
some debate. I'll remove the RFC tag and add more tests in future
revisions.

=== Problem ===

A qcow2 image is divided into units of constant size called clusters,
and among other things it contains metadata that maps guest addresses
to host addresses (the so-called L1 and L2 tables).

There are two basic problems that result from this:

1) Reading from or writing to a qcow2 image involves reading the
   corresponding entry on the L2 table that maps the guest address to
   the host address. This is very slow because it involves two I/O
   operations: one on the L2 table and the other one on the actual
   data cluster.

2) A cluster is the smallest unit of allocation. Therefore writing a
   mere 512 bytes to an empty disk requires allocating a complete
   cluster and filling it with zeroes (or with data from the backing
   image if there is one). This wastes more disk space and also has a
   negative impact on I/O.

Problem (1) can be solved by caching the L2 tables in memory. The
maximum amount of disk space used by L2 tables depends on the virtual
disk size and the cluster size:

   max_l2_size = virtual_disk_size * 8 / cluster_size

Because of this, the only way to reduce the size of the L2 tables is
by increasing the cluster size (which can be any power of two between
512 bytes and 2 MB). But then we hit problem (2): I/O is slower and
more disk space is wasted.

=== The proposal ===

The proposal is to extend the qcow2 format by allowing subcluster
allocation. The on-disk format remains essentially the same, except
that each data cluster is internally divided into 32 subclusters of
equal size.

The way it works in practice is with a new optional feature called
"Extended L2 Entries", that needs to be enabled when an image is
created. With this, each entry on an L2 table is accompanied by a
bitmap indicating the allocation state of each one of the subclusters
for that cluster. The size of an L2 entry doubles from 64 to 128 bits.

Other than L2 entries, all other data structures remain unchanged, but
for data clusters the smallest unit of allocation is now the
subcluster. Reference counting is still at the cluster level, because
there is no way to reference individual subclusters. Copy-on-write on
internal snapshots needs to copy complete clusters, so that scenario
would not benefit from this change.

I see two main use cases for this feature:

a) The qcow2 image is not too large / the L2 cache is not a problem,
   but you want to increase the allocation performance. In this case
   you can have a 128KB cluster with 4KB subclusters (with 4KB being a
   common block size in ext4 and other filesystems)

b) The qcow2 image is very large and you want to save metadata space
   in order to have a smaller L2 cache. In this case you can go for
   the maximum cluster size (2MB) but you want to have smaller
   subclusters to increase the allocation performance and optimize the
   disk usage.

=== Changes to the on-disk format ===

An L2 entry is 64 bits wide, with this format (for uncompressed
clusters):

63    56 55    48 47    40 39    32 31    24 23    16 15     8 7      0
00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000
**<----> <--------------------------------------------------><------->*
  Rsrved              host cluster offset of data             Reserved
  (6 bits)                (47 bits)                           (8 bits)

    bit 63: refcount == 1   (QCOW_OFLAG_COPIED)
    bit 62: compressed = 1  (QCOW_OFLAG_COMPRESSED)
    bit  0: all zeros       (QCOW_OFLAG_ZERO)

If Extended L2 Entries are enabled, bit 0 becomes reserved and must be
unset, and this 64-bit bitmap follows the entry:

63    56 55    48 47    40 39    32 31    24 23    16 15     8 7      0
00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000
<---------------------------------> <--------------------------------->
     subcluster reads as zeros            subcluster is allocated
             (32 bits)                           (32 bits)

All this applies to uncompressed clusters. Compressed clusters are not
divided into subclusters, the cluster descriptor remains exactly the
same, and the 64-bit bitmap is not used (i.e. all bits are always 0).

=== Test results ===

I made all tests on an SSD drive, writing to an empty qcow2 image with
a fully populated 40GB backing image, performing random writes using
fio with a block size of 4KB. I ran the tests with all available
cluster sizes starting from 4KB.

It's important to point out that once a cluster has been completely
allocated then having subclusters offers no performance benefit. For
this reason the size of the image for these tests (40GB) was chosen to
be large enough to guarantee that there are always new clusters being
allocated. This is therefore a worst-case scenario (or best-case for
this feature, if you want).

Subcluster sizes are in brackets:

|-----------------+----------------+-----------------|
|   Cluster size  | subclusters=on | subclusters=off |
|-----------------+----------------+-----------------|
|    4 KB ( N/A ) |            N/A |         95 IOPS |
|    8 KB ( N/A ) |            N/A |        599 IOPS |
|   16 KB (512 B) |      4129 IOPS |       3597 IOPS |
|   32 KB  (1 KB) |     11255 IOPS |       2642 IOPS |
|   64 KB  (2 KB) |     13341 IOPS |       1671 IOPS |
|  128 KB  (4 KB) |     12391 IOPS |        870 IOPS |
|  256 KB  (8 KB) |      9645 IOPS |        566 IOPS |
|  512 KB (16 KB) |      4960 IOPS |        359 IOPS |
| 1024 KB (32 KB) |      2732 IOPS |        215 IOPS |
| 2048 KB (64 KB) |      1630 IOPS |        214 IOPS |
|-----------------+----------------+-----------------|

Here are the same tests, but without any backing image:

|-----------------+----------------+-----------------|
|   Cluster size  | subclusters=on | subclusters=off |
|-----------------+----------------+-----------------|
|    4 KB ( N/A ) |            N/A |         93 IOPS |
|    8 KB ( N/A ) |            N/A |        539 IOPS |
|   16 KB (512 B) |      4174 IOPS |       7598 IOPS |
|   32 KB  (1 KB) |     11326 IOPS |      11957 IOPS |
|   64 KB  (2 KB) |     13516 IOPS |      13375 IOPS |
|  128 KB  (4 KB) |     12435 IOPS |      13274 IOPS |
|  256 KB  (8 KB) |     12071 IOPS |      14174 IOPS |
|  512 KB (16 KB) |     12169 IOPS |      14343 IOPS |
| 1024 KB (32 KB) |     12307 IOPS |      14622 IOPS |
| 2048 KB (64 KB) |     12784 IOPS |      14574 IOPS |
|-----------------+----------------+-----------------|

Some comments about the results:

- The smallest allowed cluster size for an image with subclusters is
  16 KB (in this case the subclusters size is 512 bytes), hence the
  missing values in the 4 KB and 8 KB rows.

- In images with a backing file: allocation is much faster when
  subclusters are enabled. As expected, images with a cluster size of
  64KB perform similar to images with a subcluster size of 64KB. When
  there is no copy-on-write involved (subcluster size <= 4KB) then the
  maximum performance is achieved.

- In images without a backing file: Since commit c8bb23cbdb when empty
  clusters are allocated for the first time they are filled with
  zeroes using an efficient method (typically fallocate() with
  FALLOC_FL_ZERO_RANGE). This is so fast that having subclusters here
  is actually a bit slower in most cases (although it still saves disk
  space).

- The 16 KB cluster / 512 byte subcluster case is quite slow.
  I haven't debugged this but I suspect that this is because new
  clusters need to be allocated all the time, and also L2 and refcount
  tables are very small and need to grow all the time. The same pattern
  can be seen in images without subclusters.

=== To do ===

A couple of things are missing from this series:

- The ability to efficiently zero individual subclusters using
  qcow2_co_pwrite_zeroes(). At the moment only full clusters can be
  zeroed with this method.

- Alternatively we could get rid of the individual "all zeroes" bits
  altogether and have 64 subclusters per cluster. We would still have
  the QCOW_OFLAG_ZERO bit in the standard cluster descriptor.

- The number of subclusters per cluster is always 32. It would be
  trivial to allow configuring this, but I don't see any use case.

- Tests: I have a few written that I'll add in future revisions of
  this series.

- handle_alloc_space() works at the subclusters level. That is, if you
  have an unallocated 2MB cluster with 64KB subclusters, no backing
  image and you write 4KB of data, QEMU won't write zeroes to the
  affected subcluster(s) and will use handle_alloc_space() instead.
  The other subclusters won't be touched and will remain unallocated.
  This behavior is consistent with how subclusters work and saves disk
  space, but offers slightly lower performance (see test results
  above). Theoretically we could offer a setting to configure this,
  but I'm not convinced that this is very useful.

===========================

As usual, feedback is welcome,

Berto

Alberto Garcia (23):
  qcow2: Add calculate_l2_meta()
  qcow2: Split cluster_needs_cow() out of count_cow_clusters()
  qcow2: Process QCOW2_CLUSTER_ZERO_ALLOC clusters in handle_copied()
  qcow2: Add get_l2_entry() and set_l2_entry()
  qcow2: Document the Extended L2 Entries feature
  qcow2: Add dummy has_subclusters() function
  qcow2: Add subcluster-related fields to BDRVQcow2State
  qcow2: Add offset_to_sc_index()
  qcow2: Add l2_entry_size()
  qcow2: Update get/set_l2_entry() and add get/set_l2_bitmap()
  qcow2: Add qcow2_get_subcluster_type()
  qcow2: Handle QCOW2_CLUSTER_UNALLOCATED_SUBCLUSTER
  qcow2: Add subcluster support to calculate_l2_meta()
  qcow2: Add subcluster support to qcow2_get_cluster_offset()
  qcow2: Add subcluster support to zero_in_l2_slice()
  qcow2: Add subcluster support to discard_in_l2_slice()
  qcow2: Add subcluster support to check_refcounts_l2()
  qcow2: Add subcluster support to expand_zero_clusters_in_l1()
  qcow2: Fix offset calculation in handle_dependencies()
  qcow2: Update L2 bitmap in qcow2_alloc_cluster_link_l2()
  qcow2: Add subcluster support to handle_alloc_space()
  qcow2: Restrict qcow2_co_pwrite_zeroes() to full clusters only
  qcow2: Add the 'extended_l2' option and the QCOW2_INCOMPAT_EXTL2 bit

 block/qcow2-cluster.c            | 547 ++++++++++++++++++++-----------
 block/qcow2-refcount.c           |  38 ++-
 block/qcow2.c                    |  83 ++++-
 block/qcow2.h                    | 121 ++++++-
 docs/interop/qcow2.txt           |  68 +++-
 docs/qcow2-cache.txt             |  19 +-
 include/block/block_int.h        |   1 +
 qapi/block-core.json             |   2 +
 tests/qemu-iotests/031.out       |   8 +-
 tests/qemu-iotests/036.out       |   4 +-
 tests/qemu-iotests/049.out       | 102 +++---
 tests/qemu-iotests/060.out       |   1 +
 tests/qemu-iotests/061.out       |  20 +-
 tests/qemu-iotests/065           |  18 +-
 tests/qemu-iotests/082.out       |  48 ++-
 tests/qemu-iotests/085.out       |  38 +--
 tests/qemu-iotests/144.out       |   4 +-
 tests/qemu-iotests/182.out       |   2 +-
 tests/qemu-iotests/185.out       |   8 +-
 tests/qemu-iotests/198.out       |   2 +
 tests/qemu-iotests/206.out       |   4 +
 tests/qemu-iotests/242.out       |   5 +
 tests/qemu-iotests/255.out       |   8 +-
 tests/qemu-iotests/common.filter |   1 +
 24 files changed, 817 insertions(+), 335 deletions(-)

-- 
2.20.1