[Qemu-devel] [PATCH v3 00/12] qcow2: Add new overlap check functions

[Qemu-devel] [PATCH v3 00/12] qcow2: Add new overlap check functions

[Max Reitz]

As has been requested, this series adds new overlap check functions to
the qcow2 code. My local branch is called "qcow2-improved-overlap-v1",
but I am not so sure whether it is actually an improvement; that is left
for you to decide, dear reviewers.

See patch 1 for an explanation of why this series exists and what it
does. Patch 1 is basically the core of this series, the rest just
employs the functions introduced there.

In a later patch, we may want to change the meaning of the "constant"
overlap checking option to mean the same as "cached", which is
everything except for inactive L2 tables. This series does make
checking for overlaps with inactive L2 tables at runtime just as cheap
as everything else (constant time plus caching), but using these checks
means qemu has to read all the snapshot L1 tables when opening a qcow2
file. This does not take long, of course, but it does result in a bit of
overhead so I did not want to enable it by default.

I think just enabling all overlap checks by default after this series
should be fine and useful, though.


For benchmarks, please see my cover letter for v2:
http://lists.nongnu.org/archive/html/qemu-devel/2014-11/msg03430.html

I'll just quote the (fixed) tl;dr here:

* CPU usage at runtime decreased by 15000 to 27500 percent on
  overlap-check-heavy tasks
* No additional performance problems at loading time (in theory has the
  same runtime complexity as a single overlap check right now; in
  practice I could not find any problems)
* Decent RAM usage (170 kB for a 1 TB image with 64 kB clusters; 170 MB
  for a 1 PB image etc. pp.)


v3:
- Patch 1:
  - s/few memory/little memory/ [Eric]
  - s/2014/2015/ [Eric]
  - s/of a or a/of or a/ [Eric]
  - Use nb_clusters_minus_one instead of nb_clusters, because
    nb_clusters == 0 is invalid [Eric]
  - Drop cached_windows_index [Stefan]
  - Reset current_nb_clusters to 1 when a new range starts in the
    algorithm which rebuilds the fragment list from the bitmap
    representation
- Patch 3: Added a TODO comment that the user should be able to override
  the default cache size limit
- Patch 8: As the patch "qcow2: Buffer L1 table in snapshot refcount
  update" has been dropped, this patch was changed to no longer rely on
  it
- Patch 11: Replaced the size limit for a snapshot's L1 table by
  QCOW_MAX_L1_SIZE (was: INT_MAX / sizeof(uint64_t)) [Eric]


git-backport-diff against v2:

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/12:[0026] [FC] 'qcow2: Add new overlap check functions'
002/12:[----] [--] 'qcow2: Pull up overlap check option evaluation'
003/12:[0001] [FC] 'qcow2: Create metadata list'
004/12:[----] [--] 'qcow2/overlaps: Protect image header'
005/12:[----] [--] 'qcow2/overlaps: Protect refcount table'
006/12:[----] [--] 'qcow2/overlaps: Protect refcount blocks'
007/12:[----] [--] 'qcow2/overlaps: Protect active L1 table'
008/12:[0002] [FC] 'qcow2/overlaps: Protect active L2 tables'
009/12:[----] [--] 'qcow2/overlaps: Protect snapshot table'
010/12:[----] [--] 'qcow2/overlaps: Protect inactive L1 tables'
011/12:[0002] [FC] 'qcow2/overlaps: Protect inactive L2 tables'
012/12:[----] [--] 'qcow2: Use new metadata overlap check function'


Max Reitz (12):
  qcow2: Add new overlap check functions
  qcow2: Pull up overlap check option evaluation
  qcow2: Create metadata list
  qcow2/overlaps: Protect image header
  qcow2/overlaps: Protect refcount table
  qcow2/overlaps: Protect refcount blocks
  qcow2/overlaps: Protect active L1 table
  qcow2/overlaps: Protect active L2 tables
  qcow2/overlaps: Protect snapshot table
  qcow2/overlaps: Protect inactive L1 tables
  qcow2/overlaps: Protect inactive L2 tables
  qcow2: Use new metadata overlap check function

 block/Makefile.objs    |   3 +-
 block/qcow2-cluster.c  |  13 ++
 block/qcow2-overlap.c  | 396 +++++++++++++++++++++++++++++++++++++++++++++++++
 block/qcow2-refcount.c | 202 ++++++++++---------------
 block/qcow2-snapshot.c | 105 ++++++++++++-
 block/qcow2.c          | 131 ++++++++++------
 block/qcow2.h          |  13 ++
 7 files changed, 691 insertions(+), 172 deletions(-)
 create mode 100644 block/qcow2-overlap.c

-- 
2.1.0

[Qemu-devel] [PATCH v3 01/12] qcow2: Add new overlap check functions

[Max Reitz]

The existing qcow2 metadata overlap detection function used existing
structures to determine the location of the image metadata, from plain
fields such as l1_table_offset and l1_size in the BDRVQcowState, over
image structures in memory such as the L1 table for the L2 tables'
positions, or it even read the required data directly from disk for
every requested check, such as the snapshot L1 tables for the inactive
L2 tables' positions.

These new functions instead keep a dedicated structure for keeping track
of the metadata positions in memory. It consists of two parts: First,
there is one structure which is basically a list of all metadata
structures. Each entry has a bitmask of types (because some metadata
structures may actually overlap, such as active and inactive L2 tables),
a number of clusters occupied and the offset from the previous entry in
clusters. This structure requires relatively little memory, but checking
a certain point may take relatively long. Each entry is called a
"fragment".

Therefore, there is another representation which is a bitmap, or rather
a bytemap, of metadata types. The previously described list is split
into multiple windows with each describing a constant number of clusters
(WINDOW_SIZE). If the list is to be queried or changed, the respective
window is selected in constant time and the bitmap is generated from the
fragments belonging to the window. This bitmap can then be queried in
constant time and easily be changed.

Because the bitmap representation requires more memory, it is only used
as a cache. Whenever a window is removed from the cache, the fragment
list will be rebuilt from the bitmap if the latter has been modified.
Therefore, the fragment list is only used as the background
representation to save memory, whereas the bitmap is used whenever
possible.

Regarding the size of the fragment list in memory: As one refcount block
can handle cluster_size / 2 entries and one L2 table can handle
cluster_size / 8 entries, for a qcow2 image with the standard cluster
size of 64 kB, there is a ratio of data to metadata of about 1/6000
(1/32768 refblocks and 1/8192 L2 tables) if one ignores the fact that
not every cluster requires an L2 table entry. The refcount table and the
L1 table is generally negligible. At the worst, each metadata cluster
requires its own entry in the fragment list; each entry takes up four
bytes, therefore, at the worst, the fragment list should take up (for an
image with 64 kB clusters) (4 B) / (64 kB * 6000) of the image size,
which is about 1.e-8 (i.e., 11 kB for a 1 TB image, or 11 MB for a 1 PB
image).

Signed-off-by: Max Reitz <mreitz@redhat.com>
---
 block/Makefile.objs   |   3 +-
 block/qcow2-overlap.c | 400 ++++++++++++++++++++++++++++++++++++++++++++++++++
 block/qcow2.h         |  13 ++
 3 files changed, 415 insertions(+), 1 deletion(-)
 create mode 100644 block/qcow2-overlap.c

diff --git a/block/Makefile.objs b/block/Makefile.objs
index db2933e..f7df121 100644
--- a/block/Makefile.objs
+++ b/block/Makefile.objs
@@ -1,5 +1,6 @@
 block-obj-y += raw_bsd.o qcow.o vdi.o vmdk.o cloop.o dmg.o bochs.o vpc.o vvfat.o
-block-obj-y += qcow2.o qcow2-refcount.o qcow2-cluster.o qcow2-snapshot.o qcow2-cache.o
+block-obj-y += qcow2.o qcow2-refcount.o qcow2-cluster.o qcow2-snapshot.o
+block-obj-y += qcow2-cache.o qcow2-overlap.o
 block-obj-y += qed.o qed-gencb.o qed-l2-cache.o qed-table.o qed-cluster.o
 block-obj-y += qed-check.o
 block-obj-$(CONFIG_VHDX) += vhdx.o vhdx-endian.o vhdx-log.o
diff --git a/block/qcow2-overlap.c b/block/qcow2-overlap.c
new file mode 100644
index 0000000..3e5c873
--- /dev/null
+++ b/block/qcow2-overlap.c
@@ -0,0 +1,400 @@
+/*
+ * QCOW2 runtime metadata overlap detection
+ *
+ * Copyright (c) 2015 Max Reitz <mreitz@redhat.com>
+ *
+ * Permission is hereby granted, free of charge, to any person obtaining a copy
+ * of this software and associated documentation files (the "Software"), to deal
+ * in the Software without restriction, including without limitation the rights
+ * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
+ * copies of the Software, and to permit persons to whom the Software is
+ * furnished to do so, subject to the following conditions:
+ *
+ * The above copyright notice and this permission notice shall be included in
+ * all copies or substantial portions of the Software.
+ *
+ * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
+ * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
+ * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL
+ * THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
+ * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
+ * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
+ * THE SOFTWARE.
+ */
+
+#include "block/block_int.h"
+#include "qemu-common.h"
+#include "qemu/range.h"
+#include "qcow2.h"
+
+/* Number of clusters which are covered by each metadata window;
+ * note that this may not exceed 2^16 as long as
+ * Qcow2MetadataFragment::relative_start is a uint16_t */
+#define WINDOW_SIZE 4096
+
+/* Describes a fragment of or a whole metadata range; does not necessarily
+ * describe the whole range because it needs to be split on window boundaries */
+typedef struct Qcow2MetadataFragment {
+    /* Bitmask of QCow2MetadataOverlap values */
+    uint8_t types;
+    uint8_t nb_clusters_minus_one;
+    /* Number of clusters between the start of the window and this range */
+    uint16_t relative_start;
+} QEMU_PACKED Qcow2MetadataFragment;
+
+typedef struct Qcow2MetadataWindow {
+    Qcow2MetadataFragment *fragments;
+    int nb_fragments, fragments_array_size;
+
+    /* If not NULL, this is an expanded version of the "RLE" version given by
+     * the fragments array; there are WINDOW_SIZE entries */
+    uint8_t *bitmap;
+    bool bitmap_modified;
+
+    /* Time of last access */
+    unsigned age;
+} Qcow2MetadataWindow;
+
+struct Qcow2MetadataList {
+    Qcow2MetadataWindow *windows;
+    uint64_t nb_windows;
+
+    unsigned current_age;
+
+    /* Index into the windows array */
+    int *cached_windows;
+    size_t nb_cached_windows;
+};
+
+/**
+ * Destroys the cached window bitmap. If it has been modified, the fragment list
+ * will be rebuilt accordingly.
+ */
+static void destroy_window_bitmap(Qcow2MetadataList *mdl,
+                                  Qcow2MetadataWindow *window)
+{
+    if (!window->bitmap) {
+        return;
+    }
+
+    if (window->bitmap_modified) {
+        int bitmap_i, fragment_i = 0;
+        QCow2MetadataOverlap current_types = 0;
+        int current_nb_clusters = 0;
+
+        /* Rebuild the fragment list; the case bitmap_i == WINDOW_SIZE is for
+         * entering the last fragment at the bitmap end */
+
+        for (bitmap_i = 0; bitmap_i <= WINDOW_SIZE; bitmap_i++) {
+            /* Qcow2MetadataFragment::nb_clusters_minus_one is a uint8_t, so
+             * current_nb_clusters may not exceed 256 */
+            if (bitmap_i < WINDOW_SIZE &&
+                current_types == window->bitmap[bitmap_i] &&
+                current_nb_clusters < 256)
+            {
+                current_nb_clusters++;
+            } else {
+                if (current_types && current_nb_clusters) {
+                    if (fragment_i >= window->fragments_array_size) {
+                        window->fragments_array_size =
+                            3 * window->fragments_array_size / 2 + 1;
+
+                        /* new_nb_fragments should be small enough, and there is
+                         * nothing we can do on failure anyway, so do not use
+                         * g_try_renew() here */
+                        window->fragments =
+                            g_renew(Qcow2MetadataFragment, window->fragments,
+                                    window->fragments_array_size);
+                    }
+
+                    window->fragments[fragment_i++] = (Qcow2MetadataFragment){
+                        .types                 = current_types,
+                        .nb_clusters_minus_one = current_nb_clusters - 1,
+                        .relative_start        = bitmap_i - current_nb_clusters,
+                    };
+                }
+
+                current_nb_clusters = 1;
+                if (bitmap_i < WINDOW_SIZE) {
+                    current_types = window->bitmap[bitmap_i];
+                }
+            }
+        }
+
+        window->nb_fragments = fragment_i;
+    }
+
+    g_free(window->bitmap);
+    window->bitmap = NULL;
+}
+
+/**
+ * Creates a bitmap from the fragment list.
+ */
+static void build_window_bitmap(Qcow2MetadataList *mdl,
+                                Qcow2MetadataWindow *window)
+{
+    int cache_i, oldest_cache_i = -1, i;
+    unsigned oldest_cache_age = 0;
+
+    for (cache_i = 0; cache_i < mdl->nb_cached_windows; cache_i++) {
+        unsigned age;
+
+        if (mdl->cached_windows[cache_i] < 0) {
+            break;
+        }
+
+        age = mdl->current_age - mdl->windows[mdl->cached_windows[cache_i]].age;
+        if (age > oldest_cache_age) {
+            oldest_cache_age = age;
+            oldest_cache_i = cache_i;
+        }
+    }
+
+    if (cache_i >= mdl->nb_cached_windows) {
+        destroy_window_bitmap(mdl,
+            &mdl->windows[mdl->cached_windows[oldest_cache_i]]);
+        cache_i = oldest_cache_i;
+    }
+
+    assert(cache_i >= 0);
+    mdl->cached_windows[cache_i] = window - mdl->windows;
+
+    window->age = mdl->current_age++;
+
+    window->bitmap = g_new0(uint8_t, WINDOW_SIZE);
+
+    for (i = 0; i < window->nb_fragments; i++) {
+        Qcow2MetadataFragment *fragment = &window->fragments[i];
+
+        memset(&window->bitmap[fragment->relative_start], fragment->types,
+               fragment->nb_clusters_minus_one + 1);
+    }
+
+    window->bitmap_modified = false;
+}
+
+/**
+ * Enters a new range into the metadata list.
+ */
+void qcow2_metadata_list_enter(BlockDriverState *bs, uint64_t offset,
+                               int nb_clusters, QCow2MetadataOverlap types)
+{
+    BDRVQcowState *s = bs->opaque;
+    uint64_t start_cluster = offset >> s->cluster_bits;
+    uint64_t end_cluster = start_cluster + nb_clusters;
+    uint64_t current_cluster = start_cluster;
+
+    types &= s->overlap_check;
+    if (!types) {
+        return;
+    }
+
+    if (offset_into_cluster(s, offset)) {
+        /* Do not enter apparently broken metadata ranges */
+        return;
+    }
+
+    while (current_cluster < end_cluster) {
+        int bitmap_i;
+        int bitmap_i_start = current_cluster % WINDOW_SIZE;
+        int bitmap_i_end = MIN(WINDOW_SIZE,
+                               end_cluster - current_cluster + bitmap_i_start);
+        uint64_t window_i = current_cluster / WINDOW_SIZE;
+        Qcow2MetadataWindow *window;
+
+        if (window_i >= s->metadata_list->nb_windows) {
+            /* This should not be happening too often, so it is fine to resize
+             * the array to exactly the required size */
+            Qcow2MetadataWindow *new_windows;
+
+            new_windows = g_try_renew(Qcow2MetadataWindow,
+                                      s->metadata_list->windows,
+                                      window_i + 1);
+            if (!new_windows) {
+                return;
+            }
+
+            memset(new_windows + s->metadata_list->nb_windows, 0,
+                   (window_i + 1 - s->metadata_list->nb_windows) *
+                   sizeof(Qcow2MetadataWindow));
+
+            s->metadata_list->windows = new_windows;
+            s->metadata_list->nb_windows = window_i + 1;
+        }
+
+        window = &s->metadata_list->windows[window_i];
+        if (!window->bitmap) {
+            build_window_bitmap(s->metadata_list, window);
+        }
+
+        for (bitmap_i = bitmap_i_start; bitmap_i < bitmap_i_end; bitmap_i++) {
+            window->bitmap[bitmap_i] |= types;
+        }
+
+        window->age = s->metadata_list->current_age++;
+        window->bitmap_modified = true;
+
+        /* Go to the next window */
+        current_cluster += WINDOW_SIZE - bitmap_i_start;
+    }
+}
+
+/**
+ * Removes a range of the given types from the metadata list.
+ */
+void qcow2_metadata_list_remove(BlockDriverState *bs, uint64_t offset,
+                                int nb_clusters, QCow2MetadataOverlap types)
+{
+    BDRVQcowState *s = bs->opaque;
+    uint64_t start_cluster = offset >> s->cluster_bits;
+    uint64_t end_cluster = start_cluster + nb_clusters;
+    uint64_t current_cluster = start_cluster;
+
+    types &= s->overlap_check;
+    if (!types) {
+        return;
+    }
+
+    if (offset_into_cluster(s, offset)) {
+        /* Try to remove even broken metadata ranges */
+        end_cluster++;
+    }
+
+    while (current_cluster < end_cluster) {
+        int bitmap_i;
+        int bitmap_i_start = current_cluster % WINDOW_SIZE;
+        int bitmap_i_end = MIN(WINDOW_SIZE,
+                               end_cluster - current_cluster + bitmap_i_start);
+        uint64_t window_i = current_cluster / WINDOW_SIZE;
+        Qcow2MetadataWindow *window;
+
+        /* If the list is too small, there is no metadata structure here;
+         * because window_i will only grow, we can abort here */
+        if (window_i >= s->metadata_list->nb_windows) {
+            return;
+        }
+
+        window = &s->metadata_list->windows[window_i];
+        if (!window->bitmap) {
+            build_window_bitmap(s->metadata_list, window);
+        }
+
+        for (bitmap_i = bitmap_i_start; bitmap_i < bitmap_i_end; bitmap_i++) {
+            window->bitmap[bitmap_i] &= ~types;
+        }
+
+        window->age = s->metadata_list->current_age++;
+        window->bitmap_modified = true;
+
+        /* Go to the next window */
+        current_cluster += WINDOW_SIZE - bitmap_i_start;
+    }
+}
+
+static int single_check_metadata_overlap(Qcow2MetadataList *mdl, int ign,
+                                         uint64_t cluster)
+{
+    uint64_t window_i = cluster / WINDOW_SIZE;
+    int bitmap_i = cluster % WINDOW_SIZE;
+    Qcow2MetadataWindow *window;
+
+    if (window_i >= mdl->nb_windows) {
+        return 0;
+    }
+    window = &mdl->windows[window_i];
+
+    if (!window->bitmap) {
+        build_window_bitmap(mdl, window);
+    }
+
+    window->age = mdl->current_age++;
+
+    return window->bitmap[bitmap_i] & ~ign;
+}
+
+/* This will replace qcow2_check_metadata_overlap() */
+static int check_metadata_overlap(BlockDriverState *bs, int ign, int64_t offset,
+                                  int64_t size) __attribute__((used));
+
+static int check_metadata_overlap(BlockDriverState *bs, int ign, int64_t offset,
+                                  int64_t size)
+{
+    BDRVQcowState *s = bs->opaque;
+    uint64_t start_cluster = offset >> s->cluster_bits;
+    uint64_t end_cluster = DIV_ROUND_UP(offset + size, s->cluster_size);
+    uint64_t current_cluster;
+    int ret = 0;
+
+    for (current_cluster = start_cluster; current_cluster < end_cluster;
+         current_cluster++)
+    {
+        ret |= single_check_metadata_overlap(s->metadata_list, ign,
+                                             current_cluster);
+    }
+
+    return ret;
+}
+
+int qcow2_create_empty_metadata_list(BlockDriverState *bs, size_t cache_size,
+                                     Error **errp)
+{
+    BDRVQcowState *s = bs->opaque;
+    int ret;
+    size_t cache_entries, i;
+
+    s->metadata_list = g_new0(Qcow2MetadataList, 1);
+    s->metadata_list->nb_windows = bs->total_sectors / s->cluster_sectors
+                                                     / WINDOW_SIZE;
+    s->metadata_list->windows = g_try_new0(Qcow2MetadataWindow,
+                                           s->metadata_list->nb_windows);
+    if (s->metadata_list->nb_windows && !s->metadata_list->windows) {
+        error_setg(errp, "Could not allocate metadata overlap check windows");
+        ret = -ENOMEM;
+        goto fail;
+    }
+
+    cache_entries = cache_size
+                  / (WINDOW_SIZE + sizeof(*s->metadata_list->cached_windows));
+    if (!cache_entries) {
+        cache_entries = 1;
+    }
+
+    s->metadata_list->nb_cached_windows = cache_entries;
+    s->metadata_list->cached_windows = g_try_new(int, cache_entries);
+    if (!s->metadata_list->cached_windows) {
+        error_setg(errp, "Could not allocate metadata overlap cache pointers");
+        ret = -ENOMEM;
+        goto fail;
+    }
+    for (i = 0; i < s->metadata_list->nb_cached_windows; i++) {
+        s->metadata_list->cached_windows[i] = -1;
+    }
+
+    return 0;
+
+fail:
+    qcow2_metadata_list_destroy(bs);
+    return ret;
+}
+
+void qcow2_metadata_list_destroy(BlockDriverState *bs)
+{
+    BDRVQcowState *s = bs->opaque;
+    uint64_t i;
+
+    if (s->metadata_list && s->metadata_list->windows) {
+        for (i = 0; i < s->metadata_list->nb_windows; i++) {
+            Qcow2MetadataWindow *window = &s->metadata_list->windows[i];
+
+            destroy_window_bitmap(s->metadata_list, window);
+            g_free(window->fragments);
+        }
+
+        g_free(s->metadata_list->cached_windows);
+        g_free(s->metadata_list->windows);
+    }
+
+    g_free(s->metadata_list);
+    s->metadata_list = NULL;
+}
diff --git a/block/qcow2.h b/block/qcow2.h
index 6e39a1b..8dd5a0a 100644
--- a/block/qcow2.h
+++ b/block/qcow2.h
@@ -159,6 +159,9 @@ typedef struct QCowSnapshot {
 struct Qcow2Cache;
 typedef struct Qcow2Cache Qcow2Cache;
 
+struct Qcow2MetadataList;
+typedef struct Qcow2MetadataList Qcow2MetadataList;
+
 typedef struct Qcow2UnknownHeaderExtension {
     uint32_t magic;
     uint32_t len;
@@ -261,6 +264,7 @@ typedef struct BDRVQcowState {
 
     bool discard_passthrough[QCOW2_DISCARD_MAX];
 
+    Qcow2MetadataList *metadata_list;
     int overlap_check; /* bitmask of Qcow2MetadataOverlap values */
     bool signaled_corruption;
 
@@ -576,4 +580,13 @@ int qcow2_cache_get_empty(BlockDriverState *bs, Qcow2Cache *c, uint64_t offset,
     void **table);
 int qcow2_cache_put(BlockDriverState *bs, Qcow2Cache *c, void **table);
 
+/* qcow2-overlap.c functions */
+int qcow2_create_empty_metadata_list(BlockDriverState *bs, size_t cache_size,
+                                     Error **errp);
+void qcow2_metadata_list_destroy(BlockDriverState *bs);
+void qcow2_metadata_list_enter(BlockDriverState *bs, uint64_t offset,
+                               int nb_clusters, QCow2MetadataOverlap type);
+void qcow2_metadata_list_remove(BlockDriverState *bs, uint64_t offset,
+                                int nb_clusters, QCow2MetadataOverlap type);
+
 #endif
-- 
2.1.0

[Qemu-devel] [PATCH v3 02/12] qcow2: Pull up overlap check option evaluation

[Max Reitz]

Pull up the absorption of the qcow2-relevant command line options and
the evaluation of the overlap check options in qcow2_open().

Signed-off-by: Max Reitz <mreitz@redhat.com>
Reviewed-by: Eric Blake <eblake@redhat.com>
---
 block/qcow2.c | 96 +++++++++++++++++++++++++++++------------------------------
 1 file changed, 48 insertions(+), 48 deletions(-)

diff --git a/block/qcow2.c b/block/qcow2.c
index 7e614d7..421c2e7 100644
--- a/block/qcow2.c
+++ b/block/qcow2.c
@@ -696,6 +696,54 @@ static int qcow2_open(BlockDriverState *bs, QDict *options, int flags,
         bs->encrypted = 1;
     }
 
+    opts = qemu_opts_create(&qcow2_runtime_opts, NULL, 0, &error_abort);
+    qemu_opts_absorb_qdict(opts, options, &local_err);
+    if (local_err) {
+        error_propagate(errp, local_err);
+        ret = -EINVAL;
+        goto fail;
+    }
+
+    opt_overlap_check = qemu_opt_get(opts, QCOW2_OPT_OVERLAP);
+    opt_overlap_check_template = qemu_opt_get(opts, QCOW2_OPT_OVERLAP_TEMPLATE);
+    if (opt_overlap_check_template && opt_overlap_check &&
+        strcmp(opt_overlap_check_template, opt_overlap_check))
+    {
+        error_setg(errp, "Conflicting values for qcow2 options '"
+                   QCOW2_OPT_OVERLAP "' ('%s') and '" QCOW2_OPT_OVERLAP_TEMPLATE
+                   "' ('%s')", opt_overlap_check, opt_overlap_check_template);
+        ret = -EINVAL;
+        goto fail;
+    }
+    if (!opt_overlap_check) {
+        opt_overlap_check = opt_overlap_check_template ?: "cached";
+    }
+
+    if (!strcmp(opt_overlap_check, "none")) {
+        overlap_check_template = 0;
+    } else if (!strcmp(opt_overlap_check, "constant")) {
+        overlap_check_template = QCOW2_OL_CONSTANT;
+    } else if (!strcmp(opt_overlap_check, "cached")) {
+        overlap_check_template = QCOW2_OL_CACHED;
+    } else if (!strcmp(opt_overlap_check, "all")) {
+        overlap_check_template = QCOW2_OL_ALL;
+    } else {
+        error_setg(errp, "Unsupported value '%s' for qcow2 option "
+                   "'overlap-check'. Allowed are either of the following: "
+                   "none, constant, cached, all", opt_overlap_check);
+        ret = -EINVAL;
+        goto fail;
+    }
+
+    s->overlap_check = 0;
+    for (i = 0; i < QCOW2_OL_MAX_BITNR; i++) {
+        /* overlap-check defines a template bitmask, but every flag may be
+         * overwritten through the associated boolean option */
+        s->overlap_check |=
+            qemu_opt_get_bool(opts, overlap_bool_option_names[i],
+                              overlap_check_template & (1 << i)) << i;
+    }
+
     s->l2_bits = s->cluster_bits - 3; /* L2 is always one cluster */
     s->l2_size = 1 << s->l2_bits;
     /* 2^(s->refcount_order - 3) is the refcount width in bytes */
@@ -791,14 +839,6 @@ static int qcow2_open(BlockDriverState *bs, QDict *options, int flags,
     }
 
     /* get L2 table/refcount block cache size from command line options */
-    opts = qemu_opts_create(&qcow2_runtime_opts, NULL, 0, &error_abort);
-    qemu_opts_absorb_qdict(opts, options, &local_err);
-    if (local_err) {
-        error_propagate(errp, local_err);
-        ret = -EINVAL;
-        goto fail;
-    }
-
     read_cache_sizes(opts, &l2_cache_size, &refcount_cache_size, &local_err);
     if (local_err) {
         error_propagate(errp, local_err);
@@ -932,46 +972,6 @@ static int qcow2_open(BlockDriverState *bs, QDict *options, int flags,
     s->discard_passthrough[QCOW2_DISCARD_OTHER] =
         qemu_opt_get_bool(opts, QCOW2_OPT_DISCARD_OTHER, false);
 
-    opt_overlap_check = qemu_opt_get(opts, QCOW2_OPT_OVERLAP);
-    opt_overlap_check_template = qemu_opt_get(opts, QCOW2_OPT_OVERLAP_TEMPLATE);
-    if (opt_overlap_check_template && opt_overlap_check &&
-        strcmp(opt_overlap_check_template, opt_overlap_check))
-    {
-        error_setg(errp, "Conflicting values for qcow2 options '"
-                   QCOW2_OPT_OVERLAP "' ('%s') and '" QCOW2_OPT_OVERLAP_TEMPLATE
-                   "' ('%s')", opt_overlap_check, opt_overlap_check_template);
-        ret = -EINVAL;
-        goto fail;
-    }
-    if (!opt_overlap_check) {
-        opt_overlap_check = opt_overlap_check_template ?: "cached";
-    }
-
-    if (!strcmp(opt_overlap_check, "none")) {
-        overlap_check_template = 0;
-    } else if (!strcmp(opt_overlap_check, "constant")) {
-        overlap_check_template = QCOW2_OL_CONSTANT;
-    } else if (!strcmp(opt_overlap_check, "cached")) {
-        overlap_check_template = QCOW2_OL_CACHED;
-    } else if (!strcmp(opt_overlap_check, "all")) {
-        overlap_check_template = QCOW2_OL_ALL;
-    } else {
-        error_setg(errp, "Unsupported value '%s' for qcow2 option "
-                   "'overlap-check'. Allowed are either of the following: "
-                   "none, constant, cached, all", opt_overlap_check);
-        ret = -EINVAL;
-        goto fail;
-    }
-
-    s->overlap_check = 0;
-    for (i = 0; i < QCOW2_OL_MAX_BITNR; i++) {
-        /* overlap-check defines a template bitmask, but every flag may be
-         * overwritten through the associated boolean option */
-        s->overlap_check |=
-            qemu_opt_get_bool(opts, overlap_bool_option_names[i],
-                              overlap_check_template & (1 << i)) << i;
-    }
-
     qemu_opts_del(opts);
     opts = NULL;
 
-- 
2.1.0

[Qemu-devel] [PATCH v3 03/12] qcow2: Create metadata list

[Max Reitz]

Create and destroy the metadata list on creation and destruction of a
qcow2 BDS, respectively. Skip creation if no overlap checks should be
performed.

Signed-off-by: Max Reitz <mreitz@redhat.com>
---
 block/qcow2.c | 11 +++++++++++
 1 file changed, 11 insertions(+)

diff --git a/block/qcow2.c b/block/qcow2.c
index 421c2e7..81016d8 100644
--- a/block/qcow2.c
+++ b/block/qcow2.c
@@ -744,6 +744,14 @@ static int qcow2_open(BlockDriverState *bs, QDict *options, int flags,
                               overlap_check_template & (1 << i)) << i;
     }
 
+    if (s->overlap_check) {
+        /* TODO: Let the user override this default */
+        ret = qcow2_create_empty_metadata_list(bs, 65536, errp);
+        if (ret < 0) {
+            goto fail;
+        }
+    }
+
     s->l2_bits = s->cluster_bits - 3; /* L2 is always one cluster */
     s->l2_size = 1 << s->l2_bits;
     /* 2^(s->refcount_order - 3) is the refcount width in bytes */
@@ -1007,6 +1015,7 @@ static int qcow2_open(BlockDriverState *bs, QDict *options, int flags,
     }
     g_free(s->cluster_cache);
     qemu_vfree(s->cluster_data);
+    qcow2_metadata_list_destroy(bs);
     return ret;
 }
 
@@ -1458,6 +1467,8 @@ static void qcow2_close(BlockDriverState *bs)
     qemu_vfree(s->cluster_data);
     qcow2_refcount_close(bs);
     qcow2_free_snapshots(bs);
+
+    qcow2_metadata_list_destroy(bs);
 }
 
 static void qcow2_invalidate_cache(BlockDriverState *bs, Error **errp)
-- 
2.1.0

[Qemu-devel] [PATCH v3 04/12] qcow2/overlaps: Protect image header

[Max Reitz]

Enter the image header into the metadata list to protect it against
accidental modifications.

Signed-off-by: Max Reitz <mreitz@redhat.com>
Reviewed-by: Eric Blake <eblake@redhat.com>
---
 block/qcow2.c | 2 ++
 1 file changed, 2 insertions(+)

diff --git a/block/qcow2.c b/block/qcow2.c
index 81016d8..b61dab5 100644
--- a/block/qcow2.c
+++ b/block/qcow2.c
@@ -752,6 +752,8 @@ static int qcow2_open(BlockDriverState *bs, QDict *options, int flags,
         }
     }
 
+    qcow2_metadata_list_enter(bs, 0, 1, QCOW2_OL_MAIN_HEADER);
+
     s->l2_bits = s->cluster_bits - 3; /* L2 is always one cluster */
     s->l2_size = 1 << s->l2_bits;
     /* 2^(s->refcount_order - 3) is the refcount width in bytes */
-- 
2.1.0

[Qemu-devel] [PATCH v3 05/12] qcow2/overlaps: Protect refcount table

[Max Reitz]

Keep track of the refcount table in the metadata list to protect it
against accidental modifications.

Signed-off-by: Max Reitz <mreitz@redhat.com>
Reviewed-by: Eric Blake <eblake@redhat.com>
---
 block/qcow2-refcount.c | 18 ++++++++++++++++++
 block/qcow2.c          |  4 ++++
 2 files changed, 22 insertions(+)

diff --git a/block/qcow2-refcount.c b/block/qcow2-refcount.c
index 9b80ca7..ea08673 100644
--- a/block/qcow2-refcount.c
+++ b/block/qcow2-refcount.c
@@ -433,6 +433,14 @@ static int alloc_refcount_block(BlockDriverState *bs,
     s->refcount_table_size = table_size;
     s->refcount_table_offset = table_offset;
 
+    qcow2_metadata_list_remove(bs, old_table_offset,
+                               size_to_clusters(s, old_table_size *
+                                                   sizeof(uint64_t)),
+                               QCOW2_OL_REFCOUNT_TABLE);
+
+    qcow2_metadata_list_enter(bs, table_offset, table_clusters,
+                              QCOW2_OL_REFCOUNT_TABLE);
+
     /* Free old table. */
     qcow2_free_clusters(bs, old_table_offset, old_table_size * sizeof(uint64_t),
                         QCOW2_DISCARD_OTHER);
@@ -1948,6 +1956,16 @@ write_refblocks:
         goto fail;
     }
 
+    qcow2_metadata_list_remove(bs, s->refcount_table_offset,
+                               size_to_clusters(s, s->refcount_table_size
+                                                   * sizeof(uint64_t)),
+                               QCOW2_OL_REFCOUNT_TABLE);
+
+    qcow2_metadata_list_enter(bs, reftable_offset,
+                              size_to_clusters(s, reftable_size *
+                                                  sizeof(uint64_t)),
+                              QCOW2_OL_REFCOUNT_TABLE);
+
     for (refblock_index = 0; refblock_index < reftable_size; refblock_index++) {
         be64_to_cpus(&on_disk_reftable[refblock_index]);
     }
diff --git a/block/qcow2.c b/block/qcow2.c
index b61dab5..e9f4824 100644
--- a/block/qcow2.c
+++ b/block/qcow2.c
@@ -780,6 +780,10 @@ static int qcow2_open(BlockDriverState *bs, QDict *options, int flags,
         error_setg(errp, "Invalid reference count table offset");
         goto fail;
     }
+    qcow2_metadata_list_enter(bs, s->refcount_table_offset,
+                              size_to_clusters(s, s->refcount_table_size *
+                                                  sizeof(uint64_t)),
+                              QCOW2_OL_REFCOUNT_TABLE);
 
     /* Snapshot table offset/length */
     if (header.nb_snapshots > QCOW_MAX_SNAPSHOTS) {
-- 
2.1.0

[Qemu-devel] [PATCH v3 06/12] qcow2/overlaps: Protect refcount blocks

[Max Reitz]

Keep track of the refcount blocks in the metadata list to protect them
against accidental modifications.

Signed-off-by: Max Reitz <mreitz@redhat.com>
Reviewed-by: Eric Blake <eblake@redhat.com>
---
 block/qcow2-refcount.c | 38 +++++++++++++++++++++++++++++++++++++-
 1 file changed, 37 insertions(+), 1 deletion(-)

diff --git a/block/qcow2-refcount.c b/block/qcow2-refcount.c
index ea08673..a785027 100644
--- a/block/qcow2-refcount.c
+++ b/block/qcow2-refcount.c
@@ -57,8 +57,16 @@ int qcow2_refcount_init(BlockDriverState *bs)
         if (ret < 0) {
             goto fail;
         }
-        for(i = 0; i < s->refcount_table_size; i++)
+        for (i = 0; i < s->refcount_table_size; i++) {
+            uint64_t refblock_offset;
+
             be64_to_cpus(&s->refcount_table[i]);
+            refblock_offset = s->refcount_table[i] & REFT_OFFSET_MASK;
+            if (refblock_offset) {
+                qcow2_metadata_list_enter(bs, refblock_offset, 1,
+                                          QCOW2_OL_REFCOUNT_BLOCK);
+            }
+        }
     }
     return 0;
  fail:
@@ -302,6 +310,7 @@ static int alloc_refcount_block(BlockDriverState *bs,
         }
 
         s->refcount_table[refcount_table_index] = new_block;
+        qcow2_metadata_list_enter(bs, new_block, 1, QCOW2_OL_REFCOUNT_BLOCK);
 
         /* The new refcount block may be where the caller intended to put its
          * data, so let it restart the search. */
@@ -363,6 +372,7 @@ static int alloc_refcount_block(BlockDriverState *bs,
     uint64_t table_offset = meta_offset + blocks_clusters * s->cluster_size;
     uint64_t *new_table = g_try_new0(uint64_t, table_size);
     uint16_t *new_blocks = g_try_malloc0(blocks_clusters * s->cluster_size);
+    uint64_t block_index;
 
     assert(table_size > 0 && blocks_clusters > 0);
     if (new_table == NULL || new_blocks == NULL) {
@@ -441,6 +451,12 @@ static int alloc_refcount_block(BlockDriverState *bs,
     qcow2_metadata_list_enter(bs, table_offset, table_clusters,
                               QCOW2_OL_REFCOUNT_TABLE);
 
+    for (block_index = 0; block_index < blocks_clusters; block_index++) {
+        qcow2_metadata_list_enter(bs, meta_offset +
+                                  (block_index << s->cluster_bits), 1,
+                                  QCOW2_OL_REFCOUNT_BLOCK);
+    }
+
     /* Free old table. */
     qcow2_free_clusters(bs, old_table_offset, old_table_size * sizeof(uint64_t),
                         QCOW2_DISCARD_OTHER);
@@ -1961,14 +1977,34 @@ write_refblocks:
                                                    * sizeof(uint64_t)),
                                QCOW2_OL_REFCOUNT_TABLE);
 
+    for (refblock_index = 0; refblock_index < s->refcount_table_size;
+         refblock_index++)
+    {
+        uint64_t refblock_offset = s->refcount_table[refblock_index] &
+                                   REFT_OFFSET_MASK;
+        if (refblock_offset) {
+            qcow2_metadata_list_remove(bs, refblock_offset, 1,
+                                       QCOW2_OL_REFCOUNT_BLOCK);
+        }
+    }
+
     qcow2_metadata_list_enter(bs, reftable_offset,
                               size_to_clusters(s, reftable_size *
                                                   sizeof(uint64_t)),
                               QCOW2_OL_REFCOUNT_TABLE);
 
     for (refblock_index = 0; refblock_index < reftable_size; refblock_index++) {
+        uint64_t refblock_offset;
+
         be64_to_cpus(&on_disk_reftable[refblock_index]);
+
+        refblock_offset = on_disk_reftable[refblock_index] & REFT_OFFSET_MASK;
+        if (refblock_offset) {
+            qcow2_metadata_list_enter(bs, refblock_offset, 1,
+                                      QCOW2_OL_REFCOUNT_BLOCK);
+        }
     }
+
     s->refcount_table = on_disk_reftable;
     s->refcount_table_offset = reftable_offset;
     s->refcount_table_size = reftable_size;
-- 
2.1.0

[Qemu-devel] [PATCH v3 07/12] qcow2/overlaps: Protect active L1 table

[Max Reitz]

Keep track of the active L1 table in the metadata list to protect it
against accidental modifications.

Signed-off-by: Max Reitz <mreitz@redhat.com>
Reviewed-by: Eric Blake <eblake@redhat.com>
---
 block/qcow2-cluster.c  | 11 +++++++++++
 block/qcow2-snapshot.c | 10 ++++++++++
 block/qcow2.c          |  4 ++++
 3 files changed, 25 insertions(+)

diff --git a/block/qcow2-cluster.c b/block/qcow2-cluster.c
index 183177d..bc93c00 100644
--- a/block/qcow2-cluster.c
+++ b/block/qcow2-cluster.c
@@ -125,6 +125,17 @@ int qcow2_grow_l1_table(BlockDriverState *bs, uint64_t min_size,
     s->l1_table = new_l1_table;
     old_l1_size = s->l1_size;
     s->l1_size = new_l1_size;
+
+    qcow2_metadata_list_remove(bs, old_l1_table_offset,
+                               size_to_clusters(s, old_l1_size *
+                                                   sizeof(uint64_t)),
+                               QCOW2_OL_ACTIVE_L1);
+
+    qcow2_metadata_list_enter(bs, s->l1_table_offset,
+                              size_to_clusters(s, s->l1_size *
+                                                  sizeof(uint64_t)),
+                              QCOW2_OL_ACTIVE_L1);
+
     qcow2_free_clusters(bs, old_l1_table_offset, old_l1_size * sizeof(uint64_t),
                         QCOW2_DISCARD_OTHER);
     return 0;
diff --git a/block/qcow2-snapshot.c b/block/qcow2-snapshot.c
index 5b3903c..41ea053 100644
--- a/block/qcow2-snapshot.c
+++ b/block/qcow2-snapshot.c
@@ -720,6 +720,11 @@ int qcow2_snapshot_load_tmp(BlockDriverState *bs,
         return ret;
     }
 
+    qcow2_metadata_list_remove(bs, s->l1_table_offset,
+                               size_to_clusters(s, s->l1_size *
+                                                   sizeof(uint64_t)),
+                               QCOW2_OL_ACTIVE_L1);
+
     /* Switch the L1 table */
     qemu_vfree(s->l1_table);
 
@@ -731,5 +736,10 @@ int qcow2_snapshot_load_tmp(BlockDriverState *bs,
         be64_to_cpus(&s->l1_table[i]);
     }
 
+    qcow2_metadata_list_enter(bs, s->l1_table_offset,
+                              size_to_clusters(s, s->l1_size *
+                                                  sizeof(uint64_t)),
+                              QCOW2_OL_ACTIVE_L1);
+
     return 0;
 }
diff --git a/block/qcow2.c b/block/qcow2.c
index e9f4824..f285555 100644
--- a/block/qcow2.c
+++ b/block/qcow2.c
@@ -832,6 +832,10 @@ static int qcow2_open(BlockDriverState *bs, QDict *options, int flags,
     }
     s->l1_table_offset = header.l1_table_offset;
 
+    qcow2_metadata_list_enter(bs, s->l1_table_offset,
+                              size_to_clusters(s, s->l1_size *
+                                                  sizeof(uint64_t)),
+                              QCOW2_OL_ACTIVE_L1);
 
     if (s->l1_size > 0) {
         s->l1_table = qemu_try_blockalign(bs->file,
-- 
2.1.0

[Qemu-devel] [PATCH v3 08/12] qcow2/overlaps: Protect active L2 tables

[Max Reitz]

Keep track of the active L2 tables in the metadata list to protect them
against accidental modifications.

Signed-off-by: Max Reitz <mreitz@redhat.com>
---
 block/qcow2-cluster.c  |  2 ++
 block/qcow2-refcount.c |  6 ++++++
 block/qcow2-snapshot.c | 21 +++++++++++++++++++++
 block/qcow2.c          |  8 +++++++-
 4 files changed, 36 insertions(+), 1 deletion(-)

diff --git a/block/qcow2-cluster.c b/block/qcow2-cluster.c
index bc93c00..88dd4f0 100644
--- a/block/qcow2-cluster.c
+++ b/block/qcow2-cluster.c
@@ -288,6 +288,8 @@ static int l2_allocate(BlockDriverState *bs, int l1_index, uint64_t **table)
         goto fail;
     }
 
+    qcow2_metadata_list_enter(bs, l2_offset, 1, QCOW2_OL_ACTIVE_L2);
+
     *table = l2_table;
     trace_qcow2_l2_allocate_done(bs, l1_index, 0);
     return 0;
diff --git a/block/qcow2-refcount.c b/block/qcow2-refcount.c
index a785027..6255ed2 100644
--- a/block/qcow2-refcount.c
+++ b/block/qcow2-refcount.c
@@ -1043,6 +1043,12 @@ int qcow2_update_snapshot_refcount(BlockDriverState *bs,
             if (addend != 0) {
                 refcount = qcow2_update_cluster_refcount(bs, l2_offset >>
                         s->cluster_bits, addend, QCOW2_DISCARD_SNAPSHOT);
+                if (addend < 0) {
+                    if (!l1_allocated) {
+                        qcow2_metadata_list_remove(bs, l2_offset, 1,
+                                                   QCOW2_OL_ACTIVE_L2);
+                    }
+                }
             } else {
                 refcount = qcow2_get_refcount(bs, l2_offset >> s->cluster_bits);
             }
diff --git a/block/qcow2-snapshot.c b/block/qcow2-snapshot.c
index 41ea053..d83a939 100644
--- a/block/qcow2-snapshot.c
+++ b/block/qcow2-snapshot.c
@@ -561,6 +561,13 @@ int qcow2_snapshot_goto(BlockDriverState *bs, const char *snapshot_id)
     g_free(sn_l1_table);
     sn_l1_table = NULL;
 
+    for (i = 0; i < s->l1_size; i++) {
+        uint64_t l2_offset = s->l1_table[i] & L1E_OFFSET_MASK;
+        if (l2_offset) {
+            qcow2_metadata_list_enter(bs, l2_offset, 1, QCOW2_OL_ACTIVE_L2);
+        }
+    }
+
     /*
      * Update QCOW_OFLAG_COPIED in the active L1 table (it may have changed
      * when we decreased the refcount of the old snapshot.
@@ -725,6 +732,13 @@ int qcow2_snapshot_load_tmp(BlockDriverState *bs,
                                                    sizeof(uint64_t)),
                                QCOW2_OL_ACTIVE_L1);
 
+    for (i = 0; i < s->l1_size; i++) {
+        uint64_t l2_offset = s->l1_table[i] & L1E_OFFSET_MASK;
+        if (l2_offset) {
+            qcow2_metadata_list_remove(bs, l2_offset, 1, QCOW2_OL_ACTIVE_L2);
+        }
+    }
+
     /* Switch the L1 table */
     qemu_vfree(s->l1_table);
 
@@ -741,5 +755,12 @@ int qcow2_snapshot_load_tmp(BlockDriverState *bs,
                                                   sizeof(uint64_t)),
                               QCOW2_OL_ACTIVE_L1);
 
+    for (i = 0; i < s->l1_size; i++) {
+        uint64_t l2_offset = s->l1_table[i] & L1E_OFFSET_MASK;
+        if (l2_offset) {
+            qcow2_metadata_list_enter(bs, l2_offset, 1, QCOW2_OL_ACTIVE_L2);
+        }
+    }
+
     return 0;
 }
diff --git a/block/qcow2.c b/block/qcow2.c
index f285555..8225ca2 100644
--- a/block/qcow2.c
+++ b/block/qcow2.c
@@ -851,8 +851,14 @@ static int qcow2_open(BlockDriverState *bs, QDict *options, int flags,
             error_setg_errno(errp, -ret, "Could not read L1 table");
             goto fail;
         }
-        for(i = 0;i < s->l1_size; i++) {
+        for (i = 0; i < s->l1_size; i++) {
+            uint64_t l2_offset;
+
             be64_to_cpus(&s->l1_table[i]);
+            l2_offset = s->l1_table[i] & L1E_OFFSET_MASK;
+            if (l2_offset) {
+                qcow2_metadata_list_enter(bs, l2_offset, 1, QCOW2_OL_ACTIVE_L2);
+            }
         }
     }
 
-- 
2.1.0

[Qemu-devel] [PATCH v3 09/12] qcow2/overlaps: Protect snapshot table

[Max Reitz]

Keep track of the snapshot table in the metadata list to protect it
against accidental modifications.

Signed-off-by: Max Reitz <mreitz@redhat.com>
Reviewed-by: Eric Blake <eblake@redhat.com>
---
 block/qcow2-snapshot.c | 10 ++++++++++
 block/qcow2.c          |  6 ++++++
 2 files changed, 16 insertions(+)

diff --git a/block/qcow2-snapshot.c b/block/qcow2-snapshot.c
index d83a939..c32d889 100644
--- a/block/qcow2-snapshot.c
+++ b/block/qcow2-snapshot.c
@@ -262,8 +262,18 @@ static int qcow2_write_snapshots(BlockDriverState *bs)
     /* free the old snapshot table */
     qcow2_free_clusters(bs, s->snapshots_offset, s->snapshots_size,
                         QCOW2_DISCARD_SNAPSHOT);
+
+    qcow2_metadata_list_remove(bs, s->snapshots_offset,
+                               size_to_clusters(s, s->snapshots_size),
+                               QCOW2_OL_SNAPSHOT_TABLE);
+
     s->snapshots_offset = snapshots_offset;
     s->snapshots_size = snapshots_size;
+
+    qcow2_metadata_list_enter(bs, s->snapshots_offset,
+                              size_to_clusters(s, s->snapshots_size),
+                              QCOW2_OL_SNAPSHOT_TABLE);
+
     return 0;
 
 fail:
diff --git a/block/qcow2.c b/block/qcow2.c
index 8225ca2..1e9b29a 100644
--- a/block/qcow2.c
+++ b/block/qcow2.c
@@ -799,6 +799,12 @@ static int qcow2_open(BlockDriverState *bs, QDict *options, int flags,
         error_setg(errp, "Invalid snapshot table offset");
         goto fail;
     }
+    if (header.nb_snapshots) {
+        qcow2_metadata_list_enter(bs, header.snapshots_offset,
+                                  size_to_clusters(s, header.nb_snapshots *
+                                                   sizeof(QCowSnapshotHeader)),
+                                  QCOW2_OL_SNAPSHOT_TABLE);
+    }
 
     /* read the level 1 table */
     if (header.l1_size > QCOW_MAX_L1_SIZE) {
-- 
2.1.0

[Qemu-devel] [PATCH v3 10/12] qcow2/overlaps: Protect inactive L1 tables

[Max Reitz]

Keep track of the inactive L1 tables in the metadata list to protect
them against accidental modifications.

Signed-off-by: Max Reitz <mreitz@redhat.com>
Reviewed-by: Eric Blake <eblake@redhat.com>
---
 block/qcow2-snapshot.c | 25 +++++++++++++++++++++++++
 1 file changed, 25 insertions(+)

diff --git a/block/qcow2-snapshot.c b/block/qcow2-snapshot.c
index c32d889..b3122d8 100644
--- a/block/qcow2-snapshot.c
+++ b/block/qcow2-snapshot.c
@@ -121,6 +121,21 @@ int qcow2_read_snapshots(BlockDriverState *bs)
             ret = -EFBIG;
             goto fail;
         }
+
+        if (!(s->overlap_check & QCOW2_OL_INACTIVE_L1)) {
+            continue;
+        }
+
+        if (sn->l1_size > INT_MAX / sizeof(uint64_t)) {
+            /* Do not fail opening the image because a snapshot is broken which
+             * might not be used anyway */
+            continue;
+        }
+
+        qcow2_metadata_list_enter(bs, sn->l1_table_offset,
+                                  size_to_clusters(s, sn->l1_size *
+                                                      sizeof(uint64_t)),
+                                  QCOW2_OL_INACTIVE_L1);
     }
 
     assert(offset - s->snapshots_offset <= INT_MAX);
@@ -416,6 +431,11 @@ int qcow2_snapshot_create(BlockDriverState *bs, QEMUSnapshotInfo *sn_info)
     g_free(l1_table);
     l1_table = NULL;
 
+    qcow2_metadata_list_enter(bs, sn->l1_table_offset,
+                              size_to_clusters(s, sn->l1_size *
+                                                  sizeof(uint64_t)),
+                              QCOW2_OL_INACTIVE_L1);
+
     /*
      * Increase the refcounts of all clusters and make sure everything is
      * stable on disk before updating the snapshot table to contain a pointer
@@ -636,6 +656,11 @@ int qcow2_snapshot_delete(BlockDriverState *bs,
     g_free(sn.id_str);
     g_free(sn.name);
 
+    qcow2_metadata_list_remove(bs, sn.l1_table_offset,
+                               size_to_clusters(s, sn.l1_size *
+                                                   sizeof(uint64_t)),
+                               QCOW2_OL_INACTIVE_L1);
+
     /*
      * Now decrease the refcounts of clusters referenced by the snapshot and
      * free the L1 table.
-- 
2.1.0

[Qemu-devel] [PATCH v3 11/12] qcow2/overlaps: Protect inactive L2 tables

[Max Reitz]

Keep track of the inactive L2 tables in the metadata list to protect
them against accidental modifications.

Signed-off-by: Max Reitz <mreitz@redhat.com>
---
 block/qcow2-refcount.c | 20 ++++++++++++++++++++
 block/qcow2-snapshot.c | 43 ++++++++++++++++++++++++++++++++++++++++---
 2 files changed, 60 insertions(+), 3 deletions(-)

diff --git a/block/qcow2-refcount.c b/block/qcow2-refcount.c
index 6255ed2..f092a57 100644
--- a/block/qcow2-refcount.c
+++ b/block/qcow2-refcount.c
@@ -1045,8 +1045,28 @@ int qcow2_update_snapshot_refcount(BlockDriverState *bs,
                         s->cluster_bits, addend, QCOW2_DISCARD_SNAPSHOT);
                 if (addend < 0) {
                     if (!l1_allocated) {
+                        /* This is easy */
                         qcow2_metadata_list_remove(bs, l2_offset, 1,
                                                    QCOW2_OL_ACTIVE_L2);
+                    } else {
+                        /* If refcount == 0, this is, too. If refcount > 1, we
+                         * know that there must be some other inactive L2
+                         * reference; and for refcount == 1, if this is an
+                         * active L2 table, this was the last inactive L2
+                         * reference. */
+                        bool remove;
+                        if (refcount == 0) {
+                            remove = true;
+                        } else if (refcount == 1) {
+                            remove = qcow2_check_metadata_overlap(bs,
+                                ~QCOW2_OL_ACTIVE_L2, l2_offset,s->cluster_size);
+                        } else {
+                            remove = false;
+                        }
+                        if (remove) {
+                            qcow2_metadata_list_remove(bs, l2_offset, 1,
+                                                       QCOW2_OL_INACTIVE_L2);
+                        }
                     }
                 }
             } else {
diff --git a/block/qcow2-snapshot.c b/block/qcow2-snapshot.c
index b3122d8..65f979e 100644
--- a/block/qcow2-snapshot.c
+++ b/block/qcow2-snapshot.c
@@ -46,9 +46,10 @@ int qcow2_read_snapshots(BlockDriverState *bs)
     QCowSnapshotHeader h;
     QCowSnapshotExtraData extra;
     QCowSnapshot *sn;
-    int i, id_str_size, name_size;
+    int i, j, id_str_size, name_size;
     int64_t offset;
     uint32_t extra_data_size;
+    uint64_t *l1_table;
     int ret;
 
     if (!s->nb_snapshots) {
@@ -122,11 +123,12 @@ int qcow2_read_snapshots(BlockDriverState *bs)
             goto fail;
         }
 
-        if (!(s->overlap_check & QCOW2_OL_INACTIVE_L1)) {
+        if (!(s->overlap_check & (QCOW2_OL_INACTIVE_L1 | QCOW2_OL_INACTIVE_L2)))
+        {
             continue;
         }
 
-        if (sn->l1_size > INT_MAX / sizeof(uint64_t)) {
+        if (sn->l1_size > QCOW_MAX_L1_SIZE) {
             /* Do not fail opening the image because a snapshot is broken which
              * might not be used anyway */
             continue;
@@ -136,6 +138,34 @@ int qcow2_read_snapshots(BlockDriverState *bs)
                                   size_to_clusters(s, sn->l1_size *
                                                       sizeof(uint64_t)),
                                   QCOW2_OL_INACTIVE_L1);
+
+        if (!(s->overlap_check & QCOW2_OL_INACTIVE_L2)) {
+            continue;
+        }
+
+        l1_table = qemu_try_blockalign(bs->file,
+                                       sn->l1_size * sizeof(uint64_t));
+        if (!l1_table) {
+            /* Do not fail opening the image just because a snapshot's L2 tables
+             * cannot be covered by the overlap checks */
+            continue;
+        }
+
+        ret = bdrv_pread(bs->file, sn->l1_table_offset, l1_table,
+                         sn->l1_size * sizeof(uint64_t));
+        if (ret < 0) {
+            qemu_vfree(l1_table);
+            continue;
+        }
+        for (j = 0; j < sn->l1_size; j++) {
+            uint64_t l2_offset = be64_to_cpu(l1_table[j]) & L1E_OFFSET_MASK;
+            if (l2_offset) {
+                qcow2_metadata_list_enter(bs, l2_offset, 1,
+                                          QCOW2_OL_INACTIVE_L2);
+            }
+        }
+
+        qemu_vfree(l1_table);
     }
 
     assert(offset - s->snapshots_offset <= INT_MAX);
@@ -436,6 +466,13 @@ int qcow2_snapshot_create(BlockDriverState *bs, QEMUSnapshotInfo *sn_info)
                                                   sizeof(uint64_t)),
                               QCOW2_OL_INACTIVE_L1);
 
+    for (i = 0; i < s->l1_size; i++) {
+        uint64_t l2_offset = s->l1_table[i] & L1E_OFFSET_MASK;
+        if (l2_offset) {
+            qcow2_metadata_list_enter(bs, l2_offset, 1, QCOW2_OL_INACTIVE_L2);
+        }
+    }
+
     /*
      * Increase the refcounts of all clusters and make sure everything is
      * stable on disk before updating the snapshot table to contain a pointer
-- 
2.1.0

[Qemu-devel] [PATCH v3 12/12] qcow2: Use new metadata overlap check function

[Max Reitz]

Make the static new overlap check function global and drop the old
function.

Signed-off-by: Max Reitz <mreitz@redhat.com>
---
 block/qcow2-overlap.c  |   8 +---
 block/qcow2-refcount.c | 120 -------------------------------------------------
 2 files changed, 2 insertions(+), 126 deletions(-)

diff --git a/block/qcow2-overlap.c b/block/qcow2-overlap.c
index 3e5c873..3d3a2f1 100644
--- a/block/qcow2-overlap.c
+++ b/block/qcow2-overlap.c
@@ -313,12 +313,8 @@ static int single_check_metadata_overlap(Qcow2MetadataList *mdl, int ign,
     return window->bitmap[bitmap_i] & ~ign;
 }
 
-/* This will replace qcow2_check_metadata_overlap() */
-static int check_metadata_overlap(BlockDriverState *bs, int ign, int64_t offset,
-                                  int64_t size) __attribute__((used));
-
-static int check_metadata_overlap(BlockDriverState *bs, int ign, int64_t offset,
-                                  int64_t size)
+int qcow2_check_metadata_overlap(BlockDriverState *bs, int ign, int64_t offset,
+                                 int64_t size)
 {
     BDRVQcowState *s = bs->opaque;
     uint64_t start_cluster = offset >> s->cluster_bits;
diff --git a/block/qcow2-refcount.c b/block/qcow2-refcount.c
index f092a57..935cf8d 100644
--- a/block/qcow2-refcount.c
+++ b/block/qcow2-refcount.c
@@ -2168,126 +2168,6 @@ fail:
     return ret;
 }
 
-#define overlaps_with(ofs, sz) \
-    ranges_overlap(offset, size, ofs, sz)
-
-/*
- * Checks if the given offset into the image file is actually free to use by
- * looking for overlaps with important metadata sections (L1/L2 tables etc.),
- * i.e. a sanity check without relying on the refcount tables.
- *
- * The ign parameter specifies what checks not to perform (being a bitmask of
- * QCow2MetadataOverlap values), i.e., what sections to ignore.
- *
- * Returns:
- * - 0 if writing to this offset will not affect the mentioned metadata
- * - a positive QCow2MetadataOverlap value indicating one overlapping section
- * - a negative value (-errno) indicating an error while performing a check,
- *   e.g. when bdrv_read failed on QCOW2_OL_INACTIVE_L2
- */
-int qcow2_check_metadata_overlap(BlockDriverState *bs, int ign, int64_t offset,
-                                 int64_t size)
-{
-    BDRVQcowState *s = bs->opaque;
-    int chk = s->overlap_check & ~ign;
-    int i, j;
-
-    if (!size) {
-        return 0;
-    }
-
-    if (chk & QCOW2_OL_MAIN_HEADER) {
-        if (offset < s->cluster_size) {
-            return QCOW2_OL_MAIN_HEADER;
-        }
-    }
-
-    /* align range to test to cluster boundaries */
-    size = align_offset(offset_into_cluster(s, offset) + size, s->cluster_size);
-    offset = start_of_cluster(s, offset);
-
-    if ((chk & QCOW2_OL_ACTIVE_L1) && s->l1_size) {
-        if (overlaps_with(s->l1_table_offset, s->l1_size * sizeof(uint64_t))) {
-            return QCOW2_OL_ACTIVE_L1;
-        }
-    }
-
-    if ((chk & QCOW2_OL_REFCOUNT_TABLE) && s->refcount_table_size) {
-        if (overlaps_with(s->refcount_table_offset,
-            s->refcount_table_size * sizeof(uint64_t))) {
-            return QCOW2_OL_REFCOUNT_TABLE;
-        }
-    }
-
-    if ((chk & QCOW2_OL_SNAPSHOT_TABLE) && s->snapshots_size) {
-        if (overlaps_with(s->snapshots_offset, s->snapshots_size)) {
-            return QCOW2_OL_SNAPSHOT_TABLE;
-        }
-    }
-
-    if ((chk & QCOW2_OL_INACTIVE_L1) && s->snapshots) {
-        for (i = 0; i < s->nb_snapshots; i++) {
-            if (s->snapshots[i].l1_size &&
-                overlaps_with(s->snapshots[i].l1_table_offset,
-                s->snapshots[i].l1_size * sizeof(uint64_t))) {
-                return QCOW2_OL_INACTIVE_L1;
-            }
-        }
-    }
-
-    if ((chk & QCOW2_OL_ACTIVE_L2) && s->l1_table) {
-        for (i = 0; i < s->l1_size; i++) {
-            if ((s->l1_table[i] & L1E_OFFSET_MASK) &&
-                overlaps_with(s->l1_table[i] & L1E_OFFSET_MASK,
-                s->cluster_size)) {
-                return QCOW2_OL_ACTIVE_L2;
-            }
-        }
-    }
-
-    if ((chk & QCOW2_OL_REFCOUNT_BLOCK) && s->refcount_table) {
-        for (i = 0; i < s->refcount_table_size; i++) {
-            if ((s->refcount_table[i] & REFT_OFFSET_MASK) &&
-                overlaps_with(s->refcount_table[i] & REFT_OFFSET_MASK,
-                s->cluster_size)) {
-                return QCOW2_OL_REFCOUNT_BLOCK;
-            }
-        }
-    }
-
-    if ((chk & QCOW2_OL_INACTIVE_L2) && s->snapshots) {
-        for (i = 0; i < s->nb_snapshots; i++) {
-            uint64_t l1_ofs = s->snapshots[i].l1_table_offset;
-            uint32_t l1_sz  = s->snapshots[i].l1_size;
-            uint64_t l1_sz2 = l1_sz * sizeof(uint64_t);
-            uint64_t *l1 = g_try_malloc(l1_sz2);
-            int ret;
-
-            if (l1_sz2 && l1 == NULL) {
-                return -ENOMEM;
-            }
-
-            ret = bdrv_pread(bs->file, l1_ofs, l1, l1_sz2);
-            if (ret < 0) {
-                g_free(l1);
-                return ret;
-            }
-
-            for (j = 0; j < l1_sz; j++) {
-                uint64_t l2_ofs = be64_to_cpu(l1[j]) & L1E_OFFSET_MASK;
-                if (l2_ofs && overlaps_with(l2_ofs, s->cluster_size)) {
-                    g_free(l1);
-                    return QCOW2_OL_INACTIVE_L2;
-                }
-            }
-
-            g_free(l1);
-        }
-    }
-
-    return 0;
-}
-
 static const char *metadata_ol_names[] = {
     [QCOW2_OL_MAIN_HEADER_BITNR]    = "qcow2_header",
     [QCOW2_OL_ACTIVE_L1_BITNR]      = "active L1 table",
-- 
2.1.0

Re: [Qemu-devel] [PATCH v3 01/12] qcow2: Add new overlap check functions

[Eric Blake]

[-- Attachment #1: Type: text/plain, Size: 985 bytes --]

On 02/09/2015 12:25 PM, Max Reitz wrote:
> The existing qcow2 metadata overlap detection function used existing
> structures to determine the location of the image metadata, from plain
> fields such as l1_table_offset and l1_size in the BDRVQcowState, over
> image structures in memory such as the L1 table for the L2 tables'
> positions, or it even read the required data directly from disk for
> every requested check, such as the snapshot L1 tables for the inactive
> L2 tables' positions.
> 
...

> 
> Signed-off-by: Max Reitz <mreitz@redhat.com>
> ---
>  block/Makefile.objs   |   3 +-
>  block/qcow2-overlap.c | 400 ++++++++++++++++++++++++++++++++++++++++++++++++++
>  block/qcow2.h         |  13 ++
>  3 files changed, 415 insertions(+), 1 deletion(-)
>  create mode 100644 block/qcow2-overlap.c
> 

Reviewed-by: Eric Blake <eblake@redhat.com>

-- 
Eric Blake   eblake redhat com    +1-919-301-3266
Libvirt virtualization library http://libvirt.org


[-- Attachment #2: OpenPGP digital signature --]
[-- Type: application/pgp-signature, Size: 604 bytes --]

Re: [Qemu-devel] [PATCH v3 03/12] qcow2: Create metadata list

[Eric Blake]

[-- Attachment #1: Type: text/plain, Size: 495 bytes --]

On 02/09/2015 12:25 PM, Max Reitz wrote:
> Create and destroy the metadata list on creation and destruction of a
> qcow2 BDS, respectively. Skip creation if no overlap checks should be
> performed.
> 
> Signed-off-by: Max Reitz <mreitz@redhat.com>
> ---
>  block/qcow2.c | 11 +++++++++++
>  1 file changed, 11 insertions(+)
> 

Reviewed-by: Eric Blake <eblake@redhat.com>

-- 
Eric Blake   eblake redhat com    +1-919-301-3266
Libvirt virtualization library http://libvirt.org


[-- Attachment #2: OpenPGP digital signature --]
[-- Type: application/pgp-signature, Size: 604 bytes --]

Re: [Qemu-devel] [PATCH v3 08/12] qcow2/overlaps: Protect active L2 tables

[Eric Blake]

[-- Attachment #1: Type: text/plain, Size: 597 bytes --]

On 02/09/2015 12:25 PM, Max Reitz wrote:
> Keep track of the active L2 tables in the metadata list to protect them
> against accidental modifications.
> 
> Signed-off-by: Max Reitz <mreitz@redhat.com>
> ---
>  block/qcow2-cluster.c  |  2 ++
>  block/qcow2-refcount.c |  6 ++++++
>  block/qcow2-snapshot.c | 21 +++++++++++++++++++++
>  block/qcow2.c          |  8 +++++++-
>  4 files changed, 36 insertions(+), 1 deletion(-)
> 

Reviewed-by: Eric Blake <eblake@redhat.com>

-- 
Eric Blake   eblake redhat com    +1-919-301-3266
Libvirt virtualization library http://libvirt.org


[-- Attachment #2: OpenPGP digital signature --]
[-- Type: application/pgp-signature, Size: 604 bytes --]

Re: [Qemu-devel] [PATCH v3 00/12] qcow2: Add new overlap check functions

[Eric Blake]

[-- Attachment #1: Type: text/plain, Size: 1302 bytes --]

On 02/09/2015 12:25 PM, Max Reitz wrote:
> As has been requested, this series adds new overlap check functions to
> the qcow2 code. My local branch is called "qcow2-improved-overlap-v1",
> but I am not so sure whether it is actually an improvement; that is left
> for you to decide, dear reviewers.
> 
> v3:
> - Patch 1:
>   - s/few memory/little memory/ [Eric]
>   - s/2014/2015/ [Eric]
>   - s/of a or a/of or a/ [Eric]
>   - Use nb_clusters_minus_one instead of nb_clusters, because
>     nb_clusters == 0 is invalid [Eric]
>   - Drop cached_windows_index [Stefan]
>   - Reset current_nb_clusters to 1 when a new range starts in the
>     algorithm which rebuilds the fragment list from the bitmap
>     representation
> - Patch 3: Added a TODO comment that the user should be able to override
>   the default cache size limit
> - Patch 8: As the patch "qcow2: Buffer L1 table in snapshot refcount
>   update" has been dropped, this patch was changed to no longer rely on
>   it
> - Patch 11: Replaced the size limit for a snapshot's L1 table by
>   QCOW_MAX_L1_SIZE (was: INT_MAX / sizeof(uint64_t)) [Eric]

On this one, it was actually Stefan that spotted it.

-- 
Eric Blake   eblake redhat com    +1-919-301-3266
Libvirt virtualization library http://libvirt.org


[-- Attachment #2: OpenPGP digital signature --]
[-- Type: application/pgp-signature, Size: 604 bytes --]

Re: [Qemu-devel] [PATCH v3 11/12] qcow2/overlaps: Protect inactive L2 tables

[Eric Blake]

[-- Attachment #1: Type: text/plain, Size: 560 bytes --]

On 02/09/2015 12:25 PM, Max Reitz wrote:
> Keep track of the inactive L2 tables in the metadata list to protect
> them against accidental modifications.
> 
> Signed-off-by: Max Reitz <mreitz@redhat.com>
> ---
>  block/qcow2-refcount.c | 20 ++++++++++++++++++++
>  block/qcow2-snapshot.c | 43 ++++++++++++++++++++++++++++++++++++++++---
>  2 files changed, 60 insertions(+), 3 deletions(-)
> 

Reviewed-by: Eric Blake <eblake@redhat.com>

-- 
Eric Blake   eblake redhat com    +1-919-301-3266
Libvirt virtualization library http://libvirt.org


[-- Attachment #2: OpenPGP digital signature --]
[-- Type: application/pgp-signature, Size: 604 bytes --]

Re: [Qemu-devel] [PATCH v3 12/12] qcow2: Use new metadata overlap check function

[Eric Blake]

[-- Attachment #1: Type: text/plain, Size: 518 bytes --]

On 02/09/2015 12:25 PM, Max Reitz wrote:
> Make the static new overlap check function global and drop the old
> function.
> 
> Signed-off-by: Max Reitz <mreitz@redhat.com>
> ---
>  block/qcow2-overlap.c  |   8 +---
>  block/qcow2-refcount.c | 120 -------------------------------------------------
>  2 files changed, 2 insertions(+), 126 deletions(-)

Reviewed-by: Eric Blake <eblake@redhat.com>

-- 
Eric Blake   eblake redhat com    +1-919-301-3266
Libvirt virtualization library http://libvirt.org


[-- Attachment #2: OpenPGP digital signature --]
[-- Type: application/pgp-signature, Size: 604 bytes --]

Re: [Qemu-devel] [PATCH v3 00/12] qcow2: Add new overlap check functions

[Max Reitz]

Ping

On 2015-02-09 at 14:25, Max Reitz wrote:
> As has been requested, this series adds new overlap check functions to
> the qcow2 code. My local branch is called "qcow2-improved-overlap-v1",
> but I am not so sure whether it is actually an improvement; that is left
> for you to decide, dear reviewers.
>
> See patch 1 for an explanation of why this series exists and what it
> does. Patch 1 is basically the core of this series, the rest just
> employs the functions introduced there.
>
> In a later patch, we may want to change the meaning of the "constant"
> overlap checking option to mean the same as "cached", which is
> everything except for inactive L2 tables. This series does make
> checking for overlaps with inactive L2 tables at runtime just as cheap
> as everything else (constant time plus caching), but using these checks
> means qemu has to read all the snapshot L1 tables when opening a qcow2
> file. This does not take long, of course, but it does result in a bit of
> overhead so I did not want to enable it by default.
>
> I think just enabling all overlap checks by default after this series
> should be fine and useful, though.
>
>
> For benchmarks, please see my cover letter for v2:
> http://lists.nongnu.org/archive/html/qemu-devel/2014-11/msg03430.html
>
> I'll just quote the (fixed) tl;dr here:
>
> * CPU usage at runtime decreased by 15000 to 27500 percent on
>    overlap-check-heavy tasks
> * No additional performance problems at loading time (in theory has the
>    same runtime complexity as a single overlap check right now; in
>    practice I could not find any problems)
> * Decent RAM usage (170 kB for a 1 TB image with 64 kB clusters; 170 MB
>    for a 1 PB image etc. pp.)
>
>
> v3:
> - Patch 1:
>    - s/few memory/little memory/ [Eric]
>    - s/2014/2015/ [Eric]
>    - s/of a or a/of or a/ [Eric]
>    - Use nb_clusters_minus_one instead of nb_clusters, because
>      nb_clusters == 0 is invalid [Eric]
>    - Drop cached_windows_index [Stefan]
>    - Reset current_nb_clusters to 1 when a new range starts in the
>      algorithm which rebuilds the fragment list from the bitmap
>      representation
> - Patch 3: Added a TODO comment that the user should be able to override
>    the default cache size limit
> - Patch 8: As the patch "qcow2: Buffer L1 table in snapshot refcount
>    update" has been dropped, this patch was changed to no longer rely on
>    it
> - Patch 11: Replaced the size limit for a snapshot's L1 table by
>    QCOW_MAX_L1_SIZE (was: INT_MAX / sizeof(uint64_t)) [Eric]
>
>
> git-backport-diff against v2:
>
> 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/12:[0026] [FC] 'qcow2: Add new overlap check functions'
> 002/12:[----] [--] 'qcow2: Pull up overlap check option evaluation'
> 003/12:[0001] [FC] 'qcow2: Create metadata list'
> 004/12:[----] [--] 'qcow2/overlaps: Protect image header'
> 005/12:[----] [--] 'qcow2/overlaps: Protect refcount table'
> 006/12:[----] [--] 'qcow2/overlaps: Protect refcount blocks'
> 007/12:[----] [--] 'qcow2/overlaps: Protect active L1 table'
> 008/12:[0002] [FC] 'qcow2/overlaps: Protect active L2 tables'
> 009/12:[----] [--] 'qcow2/overlaps: Protect snapshot table'
> 010/12:[----] [--] 'qcow2/overlaps: Protect inactive L1 tables'
> 011/12:[0002] [FC] 'qcow2/overlaps: Protect inactive L2 tables'
> 012/12:[----] [--] 'qcow2: Use new metadata overlap check function'
>
>
> Max Reitz (12):
>    qcow2: Add new overlap check functions
>    qcow2: Pull up overlap check option evaluation
>    qcow2: Create metadata list
>    qcow2/overlaps: Protect image header
>    qcow2/overlaps: Protect refcount table
>    qcow2/overlaps: Protect refcount blocks
>    qcow2/overlaps: Protect active L1 table
>    qcow2/overlaps: Protect active L2 tables
>    qcow2/overlaps: Protect snapshot table
>    qcow2/overlaps: Protect inactive L1 tables
>    qcow2/overlaps: Protect inactive L2 tables
>    qcow2: Use new metadata overlap check function
>
>   block/Makefile.objs    |   3 +-
>   block/qcow2-cluster.c  |  13 ++
>   block/qcow2-overlap.c  | 396 +++++++++++++++++++++++++++++++++++++++++++++++++
>   block/qcow2-refcount.c | 202 ++++++++++---------------
>   block/qcow2-snapshot.c | 105 ++++++++++++-
>   block/qcow2.c          | 131 ++++++++++------
>   block/qcow2.h          |  13 ++
>   7 files changed, 691 insertions(+), 172 deletions(-)
>   create mode 100644 block/qcow2-overlap.c

Re: [Qemu-devel] [PATCH v3 00/12] qcow2: Add new overlap check functions

[Max Reitz]

Pïng

On 2015-02-27 at 17:20, Max Reitz wrote:
> Ping
>
> On 2015-02-09 at 14:25, Max Reitz wrote:
>> As has been requested, this series adds new overlap check functions to
>> the qcow2 code. My local branch is called "qcow2-improved-overlap-v1",
>> but I am not so sure whether it is actually an improvement; that is left
>> for you to decide, dear reviewers.
>>
>> See patch 1 for an explanation of why this series exists and what it
>> does. Patch 1 is basically the core of this series, the rest just
>> employs the functions introduced there.
>>
>> In a later patch, we may want to change the meaning of the "constant"
>> overlap checking option to mean the same as "cached", which is
>> everything except for inactive L2 tables. This series does make
>> checking for overlaps with inactive L2 tables at runtime just as cheap
>> as everything else (constant time plus caching), but using these checks
>> means qemu has to read all the snapshot L1 tables when opening a qcow2
>> file. This does not take long, of course, but it does result in a bit of
>> overhead so I did not want to enable it by default.
>>
>> I think just enabling all overlap checks by default after this series
>> should be fine and useful, though.
>>
>>
>> For benchmarks, please see my cover letter for v2:
>> http://lists.nongnu.org/archive/html/qemu-devel/2014-11/msg03430.html
>>
>> I'll just quote the (fixed) tl;dr here:
>>
>> * CPU usage at runtime decreased by 15000 to 27500 percent on
>>    overlap-check-heavy tasks
>> * No additional performance problems at loading time (in theory has the
>>    same runtime complexity as a single overlap check right now; in
>>    practice I could not find any problems)
>> * Decent RAM usage (170 kB for a 1 TB image with 64 kB clusters; 170 MB
>>    for a 1 PB image etc. pp.)
>>
>>
>> v3:
>> - Patch 1:
>>    - s/few memory/little memory/ [Eric]
>>    - s/2014/2015/ [Eric]
>>    - s/of a or a/of or a/ [Eric]
>>    - Use nb_clusters_minus_one instead of nb_clusters, because
>>      nb_clusters == 0 is invalid [Eric]
>>    - Drop cached_windows_index [Stefan]
>>    - Reset current_nb_clusters to 1 when a new range starts in the
>>      algorithm which rebuilds the fragment list from the bitmap
>>      representation
>> - Patch 3: Added a TODO comment that the user should be able to override
>>    the default cache size limit
>> - Patch 8: As the patch "qcow2: Buffer L1 table in snapshot refcount
>>    update" has been dropped, this patch was changed to no longer rely on
>>    it
>> - Patch 11: Replaced the size limit for a snapshot's L1 table by
>>    QCOW_MAX_L1_SIZE (was: INT_MAX / sizeof(uint64_t)) [Eric]
>>
>>
>> git-backport-diff against v2:
>>
>> 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/12:[0026] [FC] 'qcow2: Add new overlap check functions'
>> 002/12:[----] [--] 'qcow2: Pull up overlap check option evaluation'
>> 003/12:[0001] [FC] 'qcow2: Create metadata list'
>> 004/12:[----] [--] 'qcow2/overlaps: Protect image header'
>> 005/12:[----] [--] 'qcow2/overlaps: Protect refcount table'
>> 006/12:[----] [--] 'qcow2/overlaps: Protect refcount blocks'
>> 007/12:[----] [--] 'qcow2/overlaps: Protect active L1 table'
>> 008/12:[0002] [FC] 'qcow2/overlaps: Protect active L2 tables'
>> 009/12:[----] [--] 'qcow2/overlaps: Protect snapshot table'
>> 010/12:[----] [--] 'qcow2/overlaps: Protect inactive L1 tables'
>> 011/12:[0002] [FC] 'qcow2/overlaps: Protect inactive L2 tables'
>> 012/12:[----] [--] 'qcow2: Use new metadata overlap check function'
>>
>>
>> Max Reitz (12):
>>    qcow2: Add new overlap check functions
>>    qcow2: Pull up overlap check option evaluation
>>    qcow2: Create metadata list
>>    qcow2/overlaps: Protect image header
>>    qcow2/overlaps: Protect refcount table
>>    qcow2/overlaps: Protect refcount blocks
>>    qcow2/overlaps: Protect active L1 table
>>    qcow2/overlaps: Protect active L2 tables
>>    qcow2/overlaps: Protect snapshot table
>>    qcow2/overlaps: Protect inactive L1 tables
>>    qcow2/overlaps: Protect inactive L2 tables
>>    qcow2: Use new metadata overlap check function
>>
>>   block/Makefile.objs    |   3 +-
>>   block/qcow2-cluster.c  |  13 ++
>>   block/qcow2-overlap.c  | 396 
>> +++++++++++++++++++++++++++++++++++++++++++++++++
>>   block/qcow2-refcount.c | 202 ++++++++++---------------
>>   block/qcow2-snapshot.c | 105 ++++++++++++-
>>   block/qcow2.c          | 131 ++++++++++------
>>   block/qcow2.h          |  13 ++
>>   7 files changed, 691 insertions(+), 172 deletions(-)
>>   create mode 100644 block/qcow2-overlap.c