From bd57f8f7f82822b76c55268593f3db49922be4dd Mon Sep 17 00:00:00 2001 From: Vladimir Sementsov-Ogievskiy Date: Wed, 28 Apr 2021 18:17:41 +0300 Subject: block: use topological sort for permission update Rewrite bdrv_check_perm(), bdrv_abort_perm_update() and bdrv_set_perm() to update nodes in topological sort order instead of simple DFS. With topologically sorted nodes, we update a node only when all its parents already updated. With DFS it's not so. Consider the following example: A -+ | | | v | B | | v | C<-+ A is parent for B and C, B is parent for C. Obviously, to update permissions, we should go in order A B C, so, when we update C, all parent permissions already updated. But with current approach (simple recursion) we can update in sequence A C B C (C is updated twice). On first update of C, we consider old B permissions, so doing wrong thing. If it succeed, all is OK, on second C update we will finish with correct graph. But if the wrong thing failed, we break the whole process for no reason (it's possible that updated B permission will be less strict, but we will never check it). Also new approach gives a way to simultaneously and correctly update several nodes, we just need to run bdrv_topological_dfs() several times to add all nodes and their subtrees into one topologically sorted list (next patch will update bdrv_replace_node() in this manner). Test test_parallel_perm_update() is now passing, so move it out of debugging "if". We also need to support ignore_children in bdrv_parent_perms_conflict() For test 283 order of conflicting parents check is changed. Note also that in bdrv_check_perm() we don't check for parents conflict at root bs, as we may be in the middle of permission update in bdrv_reopen_multiple(). bdrv_reopen_multiple() will be updated soon. Signed-off-by: Vladimir Sementsov-Ogievskiy Reviewed-by: Kevin Wolf Message-Id: <20210428151804.439460-14-vsementsov@virtuozzo.com> Signed-off-by: Kevin Wolf --- tests/qemu-iotests/283.out | 2 +- tests/unit/test-bdrv-graph-mod.c | 4 ++-- 2 files changed, 3 insertions(+), 3 deletions(-) (limited to 'tests') diff --git a/tests/qemu-iotests/283.out b/tests/qemu-iotests/283.out index 37c3505..73eb751 100644 --- a/tests/qemu-iotests/283.out +++ b/tests/qemu-iotests/283.out @@ -5,7 +5,7 @@ {"execute": "blockdev-add", "arguments": {"driver": "blkdebug", "image": "base", "node-name": "other", "take-child-perms": ["write"]}} {"return": {}} {"execute": "blockdev-backup", "arguments": {"device": "source", "sync": "full", "target": "target"}} -{"error": {"class": "GenericError", "desc": "Cannot set permissions for backup-top filter: Conflicts with use by other as 'image', which uses 'write' on base"}} +{"error": {"class": "GenericError", "desc": "Cannot set permissions for backup-top filter: Conflicts with use by source as 'image', which does not allow 'write' on base"}} === backup-top should be gone after job-finalize === diff --git a/tests/unit/test-bdrv-graph-mod.c b/tests/unit/test-bdrv-graph-mod.c index a6064b1..e64e81a 100644 --- a/tests/unit/test-bdrv-graph-mod.c +++ b/tests/unit/test-bdrv-graph-mod.c @@ -406,12 +406,12 @@ int main(int argc, char *argv[]) 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); + g_test_add_func("/bdrv-graph-mod/parallel-perm-update", + test_parallel_perm_update); if (debug) { g_test_add_func("/bdrv-graph-mod/parallel-exclusive-write", test_parallel_exclusive_write); - g_test_add_func("/bdrv-graph-mod/parallel-perm-update", - test_parallel_perm_update); g_test_add_func("/bdrv-graph-mod/append-greedy-filter", test_append_greedy_filter); } -- cgit v1.1