[Qemu-devel] [PATCH 0/3] block: fix graph modification

[Qemu-devel] [PATCH 0/3] block: fix graph modification

[Vladimir Sementsov-Ogievskiy]

Hi all.

I've found two problems during my developing of backup-top filter.
The first one was already discussed in context of backup-top series,
so, here is patch 01 taken from it, previously it was
03 of [PATCH v5 00/11] backup-top filter driver for backup
(https://lists.gnu.org/archive/html/qemu-devel/2018-12/msg06218.html)
so, here it is marked v6, and it was changed a lot:
 v6: rewrite using GHashTable and GQueue for efficient BFS.

02 is a new fix of bug I've found today, and 03 is a test for both
fixed bugs.

Vladimir Sementsov-Ogievskiy (3):
  block: improve should_update_child
  block: fix bdrv_check_perm for non-tree subgraph
  tests: add test-bdrv-graph-mod

 include/block/block_int.h   |   5 +
 block.c                     |  70 +++++++++++--
 tests/test-bdrv-graph-mod.c | 198 ++++++++++++++++++++++++++++++++++++
 tests/Makefile.include      |   2 +
 4 files changed, 268 insertions(+), 7 deletions(-)
 create mode 100644 tests/test-bdrv-graph-mod.c

-- 
2.18.0

[Qemu-devel] [PATCH v6 1/3] block: improve should_update_child

[Vladimir Sementsov-Ogievskiy]

As it already said in the comment, we don't want to create loops in
parent->child relations. So, when we try to append @to to @c, we should
check that @c is not in @to children subtree, and we should check it
recursively, not only the first level. The patch provides BFS-based
search, to check the relations.

This is needed for further fleecing-hook filter usage: we need to
append it to source, when the hook is already a parent of target, and
source may be in a backing chain of target (fleecing-scheme). So, on
appending, the hook should not became a child (direct or through
children subtree) of the target.

Signed-off-by: Vladimir Sementsov-Ogievskiy <vsementsov@virtuozzo.com>
---

v6: rewrite using GHashTable and GQueue for efficient BFS.

 block.c | 43 +++++++++++++++++++++++++++++++++++++------
 1 file changed, 37 insertions(+), 6 deletions(-)

diff --git a/block.c b/block.c
index 4ad0e90d7e..d7c2ff655c 100644
--- a/block.c
+++ b/block.c
@@ -3542,7 +3542,9 @@ void bdrv_close_all(void)
 
 static bool should_update_child(BdrvChild *c, BlockDriverState *to)
 {
-    BdrvChild *to_c;
+    GQueue *queue;
+    GHashTable *found;
+    bool ret;
 
     if (c->role->stay_at_node) {
         return false;
@@ -3578,14 +3580,43 @@ static bool should_update_child(BdrvChild *c, BlockDriverState *to)
      * if A is a child of B, that means we cannot replace A by B there
      * because that would create a loop.  Silently detaching A from B
      * is also not really an option.  So overall just leaving A in
-     * place there is the most sensible choice. */
-    QLIST_FOREACH(to_c, &to->children, next) {
-        if (to_c == c) {
-            return false;
+     * place there is the most sensible choice.
+     *
+     * We would also create a loop in any cases where @c is only
+     * indirectly referenced by @to. Prevent this by returning false
+     * if @c is found (by breadth-first search) anywhere in the whole
+     * subtree of @to.
+     */
+
+    ret = true;
+    found = g_hash_table_new(NULL, NULL);
+    g_hash_table_add(found, to);
+    queue = g_queue_new();
+    g_queue_push_tail(queue, to);
+
+    while (!g_queue_is_empty(queue)) {
+        BlockDriverState *v = g_queue_pop_head(queue);
+        BdrvChild *c2;
+
+        QLIST_FOREACH(c2, &v->children, next) {
+            if (c2 == c) {
+                ret = false;
+                break;
+            }
+
+            if (g_hash_table_contains(found, c2->bs)) {
+                continue;
+            }
+
+            g_queue_push_tail(queue, c2->bs);
+            g_hash_table_add(found, c2->bs);
         }
     }
 
-    return true;
+    g_queue_free(queue);
+    g_hash_table_destroy(found);
+
+    return ret;
 }
 
 void bdrv_replace_node(BlockDriverState *from, BlockDriverState *to,
-- 
2.18.0

[Qemu-devel] [PATCH 2/3] block: fix bdrv_check_perm for non-tree subgraph

[Vladimir Sementsov-Ogievskiy]

bdrv_check_perm in it's recursion checks each node in context of new
permissions for one parent, because of nature of DFS. It works well,
while children subgraph of top-most updated node is a tree, i.e. it
doesn't have any kind of loops. But if we have a loop (not oriented,
of course), i.e. we have two different ways from top-node to some
child-node, then bdrv_check_perm will do wrong thing:

  top
  | \
  |  |
  v  v
  A  B
  |  |
  v  v
  node

It will once check new permissions of node in context of new A
permissions and old B permissions and once visa-versa. It's a wrong way
and may lead to corruption of permission system. We may start with
no-permissions and all-shared for both A->node and B->node relations
and finish up with non shared write permission for both ways.

The following commit will add a test, which shows this bug.

To fix this situation, let's really set BdrvChild permissions during
bdrv_check_perm procedure. And we are happy here, as check-perm is
already written in transaction manner, so we just need to restore
backed-up permissions in _abort.

Signed-off-by: Vladimir Sementsov-Ogievskiy <vsementsov@virtuozzo.com>
---

Thing to discuss:
in bdrv_child_abort_perm_update(), should we include
"bdrv_abort_perm_update(c->bs);" into "if"? Or not? Anyway, if yes,
it'd better be additional patch, as it may be other bug. Or, all
things are prepared for abort even if check was not called for this
particular child?

 include/block/block_int.h |  5 +++++
 block.c                   | 27 ++++++++++++++++++++++++++-
 2 files changed, 31 insertions(+), 1 deletion(-)

diff --git a/include/block/block_int.h b/include/block/block_int.h
index 0075bafd10..8437df85a2 100644
--- a/include/block/block_int.h
+++ b/include/block/block_int.h
@@ -662,6 +662,11 @@ struct BdrvChild {
      */
     uint64_t shared_perm;
 
+    /* backup of permissions during permission update procedure */
+    bool has_backup_perm;
+    uint64_t backup_perm;
+    uint64_t backup_shared_perm;
+
     QLIST_ENTRY(BdrvChild) next;
     QLIST_ENTRY(BdrvChild) next_parent;
 };
diff --git a/block.c b/block.c
index d7c2ff655c..ab98e64305 100644
--- a/block.c
+++ b/block.c
@@ -1954,13 +1954,32 @@ static int bdrv_child_check_perm(BdrvChild *c, BlockReopenQueue *q,
     ret = bdrv_check_update_perm(c->bs, q, perm, shared, ignore_children, errp);
     g_slist_free(ignore_children);
 
-    return ret;
+    if (ret < 0) {
+        return ret;
+    }
+
+    if (!c->has_backup_perm) {
+        c->has_backup_perm = true;
+        c->backup_perm = c->perm;
+        c->backup_shared_perm = c->shared_perm;
+    }
+    /*
+     * Note: it's OK if c->has_backup_perm was already set, as we can find the
+     * same child twice during check_perm procedure
+     */
+
+    c->perm = perm;
+    c->shared_perm = shared;
+
+    return 0;
 }
 
 static void bdrv_child_set_perm(BdrvChild *c, uint64_t perm, uint64_t shared)
 {
     uint64_t cumulative_perms, cumulative_shared_perms;
 
+    c->has_backup_perm = false;
+
     c->perm = perm;
     c->shared_perm = shared;
 
@@ -1971,6 +1990,12 @@ static void bdrv_child_set_perm(BdrvChild *c, uint64_t perm, uint64_t shared)
 
 static void bdrv_child_abort_perm_update(BdrvChild *c)
 {
+    if (c->has_backup_perm) {
+        c->perm = c->backup_perm;
+        c->shared_perm = c->backup_shared_perm;
+        c->has_backup_perm = false;
+    }
+
     bdrv_abort_perm_update(c->bs);
 }
 
-- 
2.18.0

[Qemu-devel] [PATCH 3/3] tests: add test-bdrv-graph-mod

[Vladimir Sementsov-Ogievskiy]

Add two tests of node graph modification.

Signed-off-by: Vladimir Sementsov-Ogievskiy <vsementsov@virtuozzo.com>
---
 tests/test-bdrv-graph-mod.c | 198 ++++++++++++++++++++++++++++++++++++
 tests/Makefile.include      |   2 +
 2 files changed, 200 insertions(+)
 create mode 100644 tests/test-bdrv-graph-mod.c

diff --git a/tests/test-bdrv-graph-mod.c b/tests/test-bdrv-graph-mod.c
new file mode 100644
index 0000000000..458dfa6661
--- /dev/null
+++ b/tests/test-bdrv-graph-mod.c
@@ -0,0 +1,198 @@
+/*
+ * Block node graph modifications tests
+ *
+ * Copyright (c) 2019 Virtuozzo International GmbH. All rights reserved.
+ *
+ * This program is free software; you can redistribute it and/or modify
+ * it under the terms of the GNU General Public License as published by
+ * the Free Software Foundation; either version 2 of the License, or
+ * (at your option) any later version.
+ *
+ * This program is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with this program.  If not, see <http://www.gnu.org/licenses/>.
+ *
+ */
+
+#include "qemu/osdep.h"
+#include "qapi/error.h"
+#include "block/block_int.h"
+#include "sysemu/block-backend.h"
+
+static BlockDriver bdrv_pass_through = {
+    .format_name = "pass-through",
+    .bdrv_child_perm = bdrv_filter_default_perms,
+};
+
+static void no_perm_default_perms(BlockDriverState *bs, BdrvChild *c,
+                                         const BdrvChildRole *role,
+                                         BlockReopenQueue *reopen_queue,
+                                         uint64_t perm, uint64_t shared,
+                                         uint64_t *nperm, uint64_t *nshared)
+{
+    *nperm = 0;
+    *nshared = BLK_PERM_ALL;
+}
+
+static BlockDriver bdrv_no_perm = {
+    .format_name = "no-perm",
+    .bdrv_child_perm = no_perm_default_perms,
+};
+
+static BlockDriverState *no_perm_node(const char *name)
+{
+    return bdrv_new_open_driver(&bdrv_no_perm, name, BDRV_O_RDWR, &error_abort);
+}
+
+static BlockDriverState *pass_through_node(const char *name)
+{
+    return bdrv_new_open_driver(&bdrv_pass_through, name,
+                                BDRV_O_RDWR, &error_abort);
+}
+
+/*
+ * test_update_perm_tree
+ *
+ * When checking node for a possibility to update permissions, it's subtree
+ * should be correctly checked too. New permissions for each node should be
+ * calculated and checked in context of permissions of other nodes. If we
+ * check new permissions of the node only in context of old permissions of
+ * its neighbors, we can finish up with wrong permission graph.
+ *
+ * This test firstly create the following graph:
+ *                                +--------+
+ *                                |  root  |
+ *                                +--------+
+ *                                    |
+ *                                    | perm: write, read
+ *                                    | shared: except write
+ *                                    v
+ *  +-------------------+           +----------------+
+ *  | passtrough filter |---------->|  null-co node  |
+ *  +-------------------+           +----------------+
+ *
+ *
+ * and then, tries to append filter under node. Expected behavior: fail.
+ * Otherwise we'll get the following picture, with two BdrvChild'ren, having
+ * write permission to one node, without actually sharing it.
+ *
+ *                     +--------+
+ *                     |  root  |
+ *                     +--------+
+ *                         |
+ *                         | perm: write, read
+ *                         | shared: except write
+ *                         v
+ *                +-------------------+
+ *                | passtrough filter |
+ *                +-------------------+
+ *                       |   |
+ *     perm: write, read |   | perm: write, read
+ *  shared: except write |   | shared: except write
+ *                       v   v
+ *                +----------------+
+ *                |  null co node  |
+ *                +----------------+
+ */
+static void test_update_perm_tree(void)
+{
+    Error *local_err = NULL;
+
+    BlockBackend *root = blk_new(BLK_PERM_WRITE | BLK_PERM_CONSISTENT_READ,
+                                 BLK_PERM_ALL & ~BLK_PERM_WRITE);
+    BlockDriverState *bs = no_perm_node("node");
+    BlockDriverState *filter = pass_through_node("filter");
+
+    blk_insert_bs(root, bs, &error_abort);
+
+    bdrv_attach_child(filter, bs, "child", &child_file, &error_abort);
+
+    bdrv_append(filter, bs, &local_err);
+
+    g_assert_nonnull(local_err);
+
+    bdrv_unref(bs);
+    blk_unref(root);
+}
+
+/*
+ * test_should_update_child
+ *
+ * Test that bdrv_replace_node, and concretely should_update_child
+ * do the right thing, i.e. not creating loops on the graph.
+ *
+ * The test does the following:
+ * 1. initial graph:
+ *
+ *   +------+          +--------+
+ *   | root |          | filter |
+ *   +------+          +--------+
+ *      |                  |
+ *  root|            target|
+ *      v                  v
+ *   +------+          +--------+
+ *   | node |<---------| target |
+ *   +------+  backing +--------+
+ *
+ * 2. Append @filter above @node. If should_update_child works correctly,
+ * it understands, that backing child of @target should not be updated,
+ * as it will create a loop on node graph. Resulting picture should
+ * be the left one, not the right:
+ *
+ *     +------+                            +------+
+ *     | root |                            | root |
+ *     +------+                            +------+
+ *        |                                   |
+ *    root|                               root|
+ *        v                                   v
+ *    +--------+   target                 +--------+   target
+ *    | filter |--------------+           | filter |--------------+
+ *    +--------+              |           +--------+              |
+ *        |                   |               |  ^                v
+ * backing|                   |        backing|  |           +--------+
+ *        v                   v               |  +-----------| target |
+ *     +------+          +--------+           v      backing +--------+
+ *     | node |<---------| target |        +------+
+ *     +------+  backing +--------+        | node |
+ *                                         +------+
+ *
+ *    (good picture)                       (bad picture)
+ *
+ */
+static void test_should_update_child(void)
+{
+    BlockBackend *root = blk_new(0, BLK_PERM_ALL);
+    BlockDriverState *bs = no_perm_node("node");
+    BlockDriverState *filter = no_perm_node("filter");
+    BlockDriverState *target = no_perm_node("target");
+
+    blk_insert_bs(root, bs, &error_abort);
+
+    bdrv_set_backing_hd(target, bs, &error_abort);
+
+    g_assert(target->backing->bs == bs);
+    bdrv_attach_child(filter, target, "target", &child_file, &error_abort);
+    bdrv_append(filter, bs, &error_abort);
+    g_assert(target->backing->bs == bs);
+
+    bdrv_unref(bs);
+    blk_unref(root);
+}
+
+int main(int argc, char *argv[])
+{
+    bdrv_init();
+    qemu_init_main_loop(&error_abort);
+
+    g_test_init(&argc, &argv, NULL);
+
+    g_test_add_func("/bdrv-graph-mod/update-perm-tree", test_update_perm_tree);
+    g_test_add_func("/bdrv-graph-mod/should-update-child",
+                    test_should_update_child);
+
+    return g_test_run();
+}
diff --git a/tests/Makefile.include b/tests/Makefile.include
index b39e989f72..992378e031 100644
--- a/tests/Makefile.include
+++ b/tests/Makefile.include
@@ -70,6 +70,7 @@ check-unit-y += tests/test-throttle$(EXESUF)
 check-unit-y += tests/test-thread-pool$(EXESUF)
 check-unit-y += tests/test-hbitmap$(EXESUF)
 check-unit-y += tests/test-bdrv-drain$(EXESUF)
+check-unit-y += tests/test-bdrv-graph-mod$(EXESUF)
 check-unit-y += tests/test-blockjob$(EXESUF)
 check-unit-y += tests/test-blockjob-txn$(EXESUF)
 check-unit-y += tests/test-block-backend$(EXESUF)
@@ -555,6 +556,7 @@ tests/test-aio$(EXESUF): tests/test-aio.o $(test-block-obj-y)
 tests/test-aio-multithread$(EXESUF): tests/test-aio-multithread.o $(test-block-obj-y)
 tests/test-throttle$(EXESUF): tests/test-throttle.o $(test-block-obj-y)
 tests/test-bdrv-drain$(EXESUF): tests/test-bdrv-drain.o $(test-block-obj-y) $(test-util-obj-y)
+tests/test-bdrv-graph-mod$(EXESUF): tests/test-bdrv-graph-mod.o $(test-block-obj-y) $(test-util-obj-y)
 tests/test-blockjob$(EXESUF): tests/test-blockjob.o $(test-block-obj-y) $(test-util-obj-y)
 tests/test-blockjob-txn$(EXESUF): tests/test-blockjob-txn.o $(test-block-obj-y) $(test-util-obj-y)
 tests/test-block-backend$(EXESUF): tests/test-block-backend.o $(test-block-obj-y) $(test-util-obj-y)
-- 
2.18.0

Re: [Qemu-devel] [PATCH 0/3] block: fix graph modification

[Kevin Wolf]

Am 23.02.2019 um 20:20 hat Vladimir Sementsov-Ogievskiy geschrieben:
> Hi all.
> 
> I've found two problems during my developing of backup-top filter.
> The first one was already discussed in context of backup-top series,
> so, here is patch 01 taken from it, previously it was
> 03 of [PATCH v5 00/11] backup-top filter driver for backup
> (https://lists.gnu.org/archive/html/qemu-devel/2018-12/msg06218.html)
> so, here it is marked v6, and it was changed a lot:
>  v6: rewrite using GHashTable and GQueue for efficient BFS.
> 
> 02 is a new fix of bug I've found today, and 03 is a test for both
> fixed bugs.

Thanks, applied to the block branch.

Kevin