[v5,00/31] Add subcluster allocation to qcow2

Hi,

here's the new version of the patches to add subcluster allocation
support to qcow2.

Please refer to the cover letter of the first version for a full
description of the patches:

   https://lists.gnu.org/archive/html/qemu-block/2019-10/msg00983.html

Important changes here:

- I fixed hopefully all of the issues mentioned in the previous
  review. Thanks to everyone who contributed.

- There's now support for partial zeroing of clusters (i.e. at the
  subcluster level).

- Many more tests.

- QCOW_OFLAG_ZERO is simply ignored now and not considered a sign of a
  corrupt image anymore. I hesitated about this, but we could still
  add that check later. I think there's a case for adding a new
  QCOW2_CLUSTER_INVALID type and include this and other scenarios that
  we already consider corrupt (for example: clusters with unaligned
  offsets). We would need to see if for 'qemu-img check' adding
  QCOW2_CLUSTER_INVALID complicates things or not. But I think that
  all is material for its own series.

And I think that's all. See below for the detailed list of changes,
and thanks again for the feedback.

Berto

v5:
- Patch 01: Fix indentation [Max], add trace event [Vladimir]
- Patch 02: Add host_cluster_offset variable [Vladirmir]
- Patch 05: Have separate l2_entry and cluster_offset variables [Vladimir]
- Patch 06: Only context changes due to patch 05
- Patch 11: New patch
- Patch 13: Change documentation of get_l2_entry()
- Patch 14: Add QCOW_OFLAG_SUB_{ALLOC,ZERO}_RANGE [Eric] and rewrite
            the other macros.
            Ignore QCOW_OFLAG_ZERO on images with subclusters
            (i.e. don't treat them as corrupted).
- Patch 15: New patch
- Patch 19: Optimize cow by skipping all leading and trailing zero and
            unallocated subclusters [Vladimir]
            Return 0 on success [Vladimir]
            Squash patch that updated handle_dependencies() [Vladirmir]
- Patch 20: Call count_contiguous_subclusters() after the main switch
            in qcow2_get_host_offset() [Vladimir]
            Add assertion and remove goto statement [Vladimir]
- Patch 21: Rewrite algorithm.
- Patch 22: Rewrite algorithm.
- Patch 24: Replace loop with the _RANGE macros from patch 14 [Eric]
- Patch 27: New patch
- Patch 28: Update version number and expected output from tests.
- Patch 31: Add many more new tests

v4: https://lists.gnu.org/archive/html/qemu-block/2020-03/msg00966.html
v3: https://lists.gnu.org/archive/html/qemu-block/2019-12/msg00587.html
v2: https://lists.gnu.org/archive/html/qemu-block/2019-10/msg01642.html
v1: https://lists.gnu.org/archive/html/qemu-block/2019-10/msg00983.html

Output of git backport-diff against v4:

Key:
[----] : patches are identical
[####] : number of functional differences between upstream/downstream patch
[down] : patch is downstream-only
The flags [FC] indicate (F)unctional and (C)ontextual differences, respectively

001/31:[0005] [FC] 'qcow2: Make Qcow2AioTask store the full host offset'
002/31:[0018] [FC] 'qcow2: Convert qcow2_get_cluster_offset() into qcow2_get_host_offset()'
003/31:[----] [--] 'qcow2: Add calculate_l2_meta()'
004/31:[----] [--] 'qcow2: Split cluster_needs_cow() out of count_cow_clusters()'
005/31:[0038] [FC] 'qcow2: Process QCOW2_CLUSTER_ZERO_ALLOC clusters in handle_copied()'
006/31:[0004] [FC] 'qcow2: Add get_l2_entry() and set_l2_entry()'
007/31:[----] [--] 'qcow2: Document the Extended L2 Entries feature'
008/31:[----] [--] 'qcow2: Add dummy has_subclusters() function'
009/31:[----] [--] 'qcow2: Add subcluster-related fields to BDRVQcow2State'
010/31:[----] [--] 'qcow2: Add offset_to_sc_index()'
011/31:[down] 'qcow2: Add offset_into_subcluster() and size_to_subclusters()'
012/31:[----] [--] 'qcow2: Add l2_entry_size()'
013/31:[0003] [FC] 'qcow2: Update get/set_l2_entry() and add get/set_l2_bitmap()'
014/31:[0023] [FC] 'qcow2: Add QCow2SubclusterType and qcow2_get_subcluster_type()'
015/31:[down] 'qcow2: Add qcow2_cluster_is_allocated()'
016/31:[----] [--] 'qcow2: Add cluster type parameter to qcow2_get_host_offset()'
017/31:[----] [--] 'qcow2: Replace QCOW2_CLUSTER_* with QCOW2_SUBCLUSTER_*'
018/31:[----] [--] 'qcow2: Handle QCOW2_SUBCLUSTER_UNALLOCATED_ALLOC'
019/31:[0066] [FC] 'qcow2: Add subcluster support to calculate_l2_meta()'
020/31:[0022] [FC] 'qcow2: Add subcluster support to qcow2_get_host_offset()'
021/31:[0040] [FC] 'qcow2: Add subcluster support to zero_in_l2_slice()'
022/31:[0061] [FC] 'qcow2: Add subcluster support to discard_in_l2_slice()'
023/31:[----] [--] 'qcow2: Add subcluster support to check_refcounts_l2()'
024/31:[0019] [FC] 'qcow2: Update L2 bitmap in qcow2_alloc_cluster_link_l2()'
025/31:[----] [--] 'qcow2: Clear the L2 bitmap when allocating a compressed cluster'
026/31:[----] [--] 'qcow2: Add subcluster support to handle_alloc_space()'
027/31:[down] 'qcow2: Add subcluster support to qcow2_co_pwrite_zeroes()'
028/31:[0105] [FC] 'qcow2: Add the 'extended_l2' option and the QCOW2_INCOMPAT_EXTL2 bit'
029/31:[----] [-C] 'qcow2: Assert that expand_zero_clusters_in_l1() does not support subclusters'
030/31:[----] [--] 'qcow2: Add subcluster support to qcow2_measure()'
031/31:[0694] [FC] 'iotests: Add tests for qcow2 images with extended L2 entries'

Alberto Garcia (31):
  qcow2: Make Qcow2AioTask store the full host offset
  qcow2: Convert qcow2_get_cluster_offset() into qcow2_get_host_offset()
  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 offset_into_subcluster() and size_to_subclusters()
  qcow2: Add l2_entry_size()
  qcow2: Update get/set_l2_entry() and add get/set_l2_bitmap()
  qcow2: Add QCow2SubclusterType and qcow2_get_subcluster_type()
  qcow2: Add qcow2_cluster_is_allocated()
  qcow2: Add cluster type parameter to qcow2_get_host_offset()
  qcow2: Replace QCOW2_CLUSTER_* with QCOW2_SUBCLUSTER_*
  qcow2: Handle QCOW2_SUBCLUSTER_UNALLOCATED_ALLOC
  qcow2: Add subcluster support to calculate_l2_meta()
  qcow2: Add subcluster support to qcow2_get_host_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: Update L2 bitmap in qcow2_alloc_cluster_link_l2()
  qcow2: Clear the L2 bitmap when allocating a compressed cluster
  qcow2: Add subcluster support to handle_alloc_space()
  qcow2: Add subcluster support to qcow2_co_pwrite_zeroes()
  qcow2: Add the 'extended_l2' option and the QCOW2_INCOMPAT_EXTL2 bit
  qcow2: Assert that expand_zero_clusters_in_l1() does not support
    subclusters
  qcow2: Add subcluster support to qcow2_measure()
  iotests: Add tests for qcow2 images with extended L2 entries

 docs/interop/qcow2.txt           |  68 ++-
 docs/qcow2-cache.txt             |  19 +-
 qapi/block-core.json             |   7 +
 block/qcow2.h                    | 204 ++++++-
 include/block/block_int.h        |   1 +
 block/qcow2-cluster.c            | 892 ++++++++++++++++++++-----------
 block/qcow2-refcount.c           |  38 +-
 block/qcow2.c                    | 283 ++++++----
 block/trace-events               |   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           |   6 +
 tests/qemu-iotests/061.out       |  25 +-
 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/271           | 664 +++++++++++++++++++++++
 tests/qemu-iotests/271.out       | 519 ++++++++++++++++++
 tests/qemu-iotests/274.out       |  49 +-
 tests/qemu-iotests/280.out       |   2 +-
 tests/qemu-iotests/common.filter |   1 +
 tests/qemu-iotests/group         |   1 +
 31 files changed, 2459 insertions(+), 574 deletions(-)
 create mode 100755 tests/qemu-iotests/271
 create mode 100644 tests/qemu-iotests/271.out