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

[Qemu-devel] [PATCH 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.

I have yet to do benchmarks to test whether this series actually
improves things, but judging from the iotests it at least does not slow
things down (which it did at one time during development, particularily
test 044 is good for testing this, so this actually has some
significance to it).

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.


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  | 404 +++++++++++++++++++++++++++++++++++++++++++++++++
 block/qcow2-refcount.c | 202 ++++++++++---------------
 block/qcow2-snapshot.c | 105 ++++++++++++-
 block/qcow2.c          | 130 ++++++++++------
 block/qcow2.h          |  13 ++
 7 files changed, 698 insertions(+), 172 deletions(-)
 create mode 100644 block/qcow2-overlap.c

-- 
1.9.3

[Qemu-devel] [PATCH 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 few 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 | 408 ++++++++++++++++++++++++++++++++++++++++++++++++++
 block/qcow2.h         |  13 ++
 3 files changed, 423 insertions(+), 1 deletion(-)
 create mode 100644 block/qcow2-overlap.c

diff --git a/block/Makefile.objs b/block/Makefile.objs
index 04b0e43..8d9c73d 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..21d1d3c
--- /dev/null
+++ b/block/qcow2-overlap.c
@@ -0,0 +1,408 @@
+/*
+ * QCOW2 runtime metadata overlap detection
+ *
+ * Copyright (c) 2014 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 a 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;
+    /* 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;
+
+    /* Index in Qcow2MetadataList::cached_windows */
+    int cached_windows_index;
+} 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, current_relative_start = 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 is a uint8_t, so
+             * current_nb_clusters may not exceed 255 */
+            if (bitmap_i < WINDOW_SIZE &&
+                current_types == window->bitmap[bitmap_i] &&
+                current_nb_clusters < 255)
+            {
+                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    = current_nb_clusters,
+                        .relative_start = current_relative_start
+                    };
+
+                    current_relative_start = 0;
+                } else if (!current_types) {
+                    current_relative_start = current_nb_clusters;
+                }
+
+                current_nb_clusters = 0;
+                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->cached_windows_index = cache_i;
+
+    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);
+    }
+
+    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)
+{
+    int 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
-- 
1.9.3

[Qemu-devel] [PATCH 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>
---
 block/qcow2.c | 96 +++++++++++++++++++++++++++++------------------------------
 1 file changed, 48 insertions(+), 48 deletions(-)

diff --git a/block/qcow2.c b/block/qcow2.c
index d120494..ed88d69 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);
@@ -931,46 +971,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;
 
-- 
1.9.3

[Qemu-devel] [PATCH 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 | 10 ++++++++++
 1 file changed, 10 insertions(+)

diff --git a/block/qcow2.c b/block/qcow2.c
index ed88d69..f80f9ed 100644
--- a/block/qcow2.c
+++ b/block/qcow2.c
@@ -744,6 +744,13 @@ static int qcow2_open(BlockDriverState *bs, QDict *options, int flags,
                               overlap_check_template & (1 << i)) << i;
     }
 
+    if (s->overlap_check) {
+        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 */
@@ -1006,6 +1013,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;
 }
 
@@ -1444,6 +1452,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)
-- 
1.9.3

[Qemu-devel] [PATCH 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>
---
 block/qcow2.c | 2 ++
 1 file changed, 2 insertions(+)

diff --git a/block/qcow2.c b/block/qcow2.c
index f80f9ed..19ac2df 100644
--- a/block/qcow2.c
+++ b/block/qcow2.c
@@ -751,6 +751,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 */
-- 
1.9.3

[Qemu-devel] [PATCH 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>
---
 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 9afdb40..97c28da 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 19ac2df..1644421 100644
--- a/block/qcow2.c
+++ b/block/qcow2.c
@@ -779,6 +779,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) {
-- 
1.9.3

[Qemu-devel] [PATCH 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>
---
 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 97c28da..1d76652 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;
-- 
1.9.3

[Qemu-devel] [PATCH 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>
---
 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 df0b2c9..131e5b2 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 1644421..775cb39 100644
--- a/block/qcow2.c
+++ b/block/qcow2.c
@@ -831,6 +831,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,
-- 
1.9.3

[Qemu-devel] [PATCH 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 131e5b2..b749941 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 1d76652..6cf73e9 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 775cb39..d0950fc 100644
--- a/block/qcow2.c
+++ b/block/qcow2.c
@@ -850,8 +850,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);
+            }
         }
     }
 
-- 
1.9.3

[Qemu-devel] [PATCH 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>
---
 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 d0950fc..468090d 100644
--- a/block/qcow2.c
+++ b/block/qcow2.c
@@ -798,6 +798,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) {
-- 
1.9.3

[Qemu-devel] [PATCH 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>
---
 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.
-- 
1.9.3

[Qemu-devel] [PATCH 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 | 41 +++++++++++++++++++++++++++++++++++++++--
 2 files changed, 59 insertions(+), 2 deletions(-)

diff --git a/block/qcow2-refcount.c b/block/qcow2-refcount.c
index 6cf73e9..0c203d3 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..800c7d3 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,7 +123,8 @@ 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;
         }
 
@@ -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
-- 
1.9.3

[Qemu-devel] [PATCH 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 21d1d3c..cd401fe 100644
--- a/block/qcow2-overlap.c
+++ b/block/qcow2-overlap.c
@@ -321,12 +321,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 0c203d3..edff9ee 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",
-- 
1.9.3

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

[Max Reitz]

On 2014-11-03 at 18:04, 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.
>
> I have yet to do benchmarks to test whether this series actually
> improves things, but judging from the iotests it at least does not slow
> things down (which it did at one time during development, particularily
> test 044 is good for testing this, so this actually has some
> significance to it).
>
> 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.

Sorry Benoît, I mistyped your address. Maybe I should learn how to use 
abbreviations with git send-email some time...

Max

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

[Max Reitz]

On 2014-11-03 at 18:04, 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.
>
> I have yet to do benchmarks to test whether this series actually
> improves things, but judging from the iotests it at least does not slow
> things down (which it did at one time during development, particularily
> test 044 is good for testing this, so this actually has some
> significance to it).
>
> 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.

Rejoice, for I return with benchmarks; the kind of benchmarks which 
always show the result I want them to show, which I should be known for 
by now.

First, I basically tried the setup from last time only this time I 
didn't care about the in-VM I/O performance but just use perf record -g 
to record the amount of cycles used by the overlap check. This worked 
somehow, but bonnie++ (which I used as the in-VM benchmark tool) does 
some different tests, both reading and writing and writing with 
different sizes, so the result is not that bad there.

So I did what's absolutely worst for the overlap checks: dd if=/dev/zero 
of=/dev/vda bs=65536 oflag=direct (even worse would be cluster_size=512 
and bs=512, but I wanted to get the test over with today, so I just went 
for 64k). The image was a 1G qcow2 image in tmpfs with ten snapshots 
(each having 128 MB of data, all pointing to the same data clusters 
which are different from the active clusters) just because having 
internal snapshots makes the overlap checks even more CPU intensive, of 
course.

I ran dd 42 times in a row (for i in $(seq 1 42); do ...; done) and 
started up perf record just after I hit enter and canceled it just 
before the last dd exited.

I don't remember the exact numbers, but for the currently existing 
overlap check function (using the default of overlap-check=cached), it 
used about 13.5 % in the first run, 10.5 % in the second and (this I do 
know) 12.41 % in the third run.

With these patches applied, I had 0.08 % in the first run with 
overlap-check=cached and 0.09 % in the second run with overlap-check=all.

(all percentages are referring to the fraction of cycles used by 
qcow2_check_metadata_overlap())

So this series apparently is actually worth it. I could yet do another 
benchmark where I test what happens if the cache is too small, which 
means that the range list representation has to be converted to the 
bitmap all the time and vice versa. The biggest problem with that would 
be to somehow fit the image into tmpfs (if it's not in tmpfs, I don't 
want to do CPU benchmarks)...

Max