[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
[PATCH 08/21] block: use topological sort for permission update
From: |
Vladimir Sementsov-Ogievskiy |
Subject: |
[PATCH 08/21] block: use topological sort for permission update |
Date: |
Mon, 23 Nov 2020 23:12:20 +0300 |
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".
Signed-off-by: Vladimir Sementsov-Ogievskiy <vsementsov@virtuozzo.com>
---
block.c | 108 ++++++++++++++++++++++++++++--------
tests/test-bdrv-graph-mod.c | 4 +-
tests/qemu-iotests/283.out | 2 +-
3 files changed, 88 insertions(+), 26 deletions(-)
diff --git a/block.c b/block.c
index 22498b5288..56263407e8 100644
--- a/block.c
+++ b/block.c
@@ -1973,13 +1973,17 @@ static bool bdrv_a_allow_b(BdrvChild *a, BdrvChild *b,
Error **errp)
return false;
}
-static bool bdrv_check_parents_compliance(BlockDriverState *bs, Error **errp)
+static bool bdrv_check_parents_compliance(BlockDriverState *bs,
+ GSList *ignore_children,
+ Error **errp)
{
BdrvChild *a, *b;
QLIST_FOREACH(a, &bs->parents, next_parent) {
QLIST_FOREACH(b, &bs->parents, next_parent) {
- if (a == b) {
+ if (a == b || g_slist_find(ignore_children, a) ||
+ g_slist_find(ignore_children, b))
+ {
continue;
}
@@ -2012,6 +2016,29 @@ static void bdrv_child_perm(BlockDriverState *bs,
BlockDriverState *child_bs,
}
}
+static GSList *bdrv_topological_dfs(GSList *list, GHashTable *found,
+ BlockDriverState *bs)
+{
+ BdrvChild *child;
+ g_autoptr(GHashTable) local_found = NULL;
+
+ if (!found) {
+ assert(!list);
+ found = local_found = g_hash_table_new(NULL, NULL);
+ }
+
+ if (g_hash_table_contains(found, bs)) {
+ return list;
+ }
+ g_hash_table_add(found, bs);
+
+ QLIST_FOREACH(child, &bs->children, next) {
+ list = bdrv_topological_dfs(list, found, child->bs);
+ }
+
+ return g_slist_prepend(list, bs);
+}
+
static void bdrv_child_set_perm_commit(void *opaque)
{
BdrvChild *c = opaque;
@@ -2076,14 +2103,13 @@ static void bdrv_child_set_perm_safe(BdrvChild *c,
uint64_t perm,
* A call to this function must always be followed by a call to bdrv_set_perm()
* or bdrv_abort_perm_update().
*/
-static int bdrv_check_perm(BlockDriverState *bs, BlockReopenQueue *q,
- uint64_t cumulative_perms,
- uint64_t cumulative_shared_perms,
- GSList *ignore_children, Error **errp)
+static int bdrv_node_check_perm(BlockDriverState *bs, BlockReopenQueue *q,
+ uint64_t cumulative_perms,
+ uint64_t cumulative_shared_perms,
+ GSList *ignore_children, Error **errp)
{
BlockDriver *drv = bs->drv;
BdrvChild *c;
- int ret;
/* Write permissions never work with read-only images */
if ((cumulative_perms & (BLK_PERM_WRITE | BLK_PERM_WRITE_UNCHANGED)) &&
@@ -2128,8 +2154,8 @@ static int bdrv_check_perm(BlockDriverState *bs,
BlockReopenQueue *q,
}
if (drv->bdrv_check_perm) {
- ret = drv->bdrv_check_perm(bs, cumulative_perms,
- cumulative_shared_perms, errp);
+ int ret = drv->bdrv_check_perm(bs, cumulative_perms,
+ cumulative_shared_perms, errp);
if (ret < 0) {
return ret;
}
@@ -2144,21 +2170,43 @@ static int bdrv_check_perm(BlockDriverState *bs,
BlockReopenQueue *q,
/* Check all children */
QLIST_FOREACH(c, &bs->children, next) {
uint64_t cur_perm, cur_shared;
- GSList *cur_ignore_children;
bdrv_child_perm(bs, c->bs, c, c->role, q,
cumulative_perms, cumulative_shared_perms,
&cur_perm, &cur_shared);
+ bdrv_child_set_perm_safe(c, cur_perm, cur_shared, NULL);
+ }
+
+ return 0;
+}
- cur_ignore_children = g_slist_prepend(g_slist_copy(ignore_children),
c);
- ret = bdrv_check_update_perm(c->bs, q, cur_perm, cur_shared,
- cur_ignore_children, errp);
- g_slist_free(cur_ignore_children);
+static int bdrv_check_perm(BlockDriverState *bs, BlockReopenQueue *q,
+ uint64_t cumulative_perms,
+ uint64_t cumulative_shared_perms,
+ GSList *ignore_children, Error **errp)
+{
+ int ret;
+ BlockDriverState *root = bs;
+ g_autoptr(GSList) list = bdrv_topological_dfs(NULL, NULL, root);
+
+ for ( ; list; list = list->next) {
+ bs = list->data;
+
+ if (bs != root) {
+ if (!bdrv_check_parents_compliance(bs, ignore_children, errp)) {
+ return -EINVAL;
+ }
+
+ bdrv_get_cumulative_perm(bs, &cumulative_perms,
+ &cumulative_shared_perms);
+ }
+
+ ret = bdrv_node_check_perm(bs, q, cumulative_perms,
+ cumulative_shared_perms,
+ ignore_children, errp);
if (ret < 0) {
return ret;
}
-
- bdrv_child_set_perm_safe(c, cur_perm, cur_shared, NULL);
}
return 0;
@@ -2168,10 +2216,8 @@ static int bdrv_check_perm(BlockDriverState *bs,
BlockReopenQueue *q,
* Notifies drivers that after a previous bdrv_check_perm() call, the
* permission update is not performed and any preparations made for it (e.g.
* taken file locks) need to be undone.
- *
- * This function recursively notifies all child nodes.
*/
-static void bdrv_abort_perm_update(BlockDriverState *bs)
+static void bdrv_node_abort_perm_update(BlockDriverState *bs)
{
BlockDriver *drv = bs->drv;
BdrvChild *c;
@@ -2186,11 +2232,19 @@ static void bdrv_abort_perm_update(BlockDriverState *bs)
QLIST_FOREACH(c, &bs->children, next) {
bdrv_child_set_perm_abort(c);
- bdrv_abort_perm_update(c->bs);
}
}
-static void bdrv_set_perm(BlockDriverState *bs)
+static void bdrv_abort_perm_update(BlockDriverState *bs)
+{
+ g_autoptr(GSList) list = bdrv_topological_dfs(NULL, NULL, bs);
+
+ for ( ; list; list = list->next) {
+ bdrv_node_abort_perm_update((BlockDriverState *)list->data);
+ }
+}
+
+static void bdrv_node_set_perm(BlockDriverState *bs)
{
uint64_t cumulative_perms, cumulative_shared_perms;
BlockDriver *drv = bs->drv;
@@ -2216,7 +2270,15 @@ static void bdrv_set_perm(BlockDriverState *bs)
/* Update all children */
QLIST_FOREACH(c, &bs->children, next) {
bdrv_child_set_perm_commit(c);
- bdrv_set_perm(c->bs);
+ }
+}
+
+static void bdrv_set_perm(BlockDriverState *bs)
+{
+ g_autoptr(GSList) list = bdrv_topological_dfs(NULL, NULL, bs);
+
+ for ( ; list; list = list->next) {
+ bdrv_node_set_perm((BlockDriverState *)list->data);
}
}
@@ -2329,7 +2391,7 @@ static int bdrv_refresh_perms(BlockDriverState *bs, Error
**errp)
int ret;
uint64_t perm, shared_perm;
- if (!bdrv_check_parents_compliance(bs, errp)) {
+ if (!bdrv_check_parents_compliance(bs, NULL, errp)) {
return -EPERM;
}
bdrv_get_cumulative_perm(bs, &perm, &shared_perm);
diff --git a/tests/test-bdrv-graph-mod.c b/tests/test-bdrv-graph-mod.c
index 27e3361a60..594a1df58b 100644
--- a/tests/test-bdrv-graph-mod.c
+++ b/tests/test-bdrv-graph-mod.c
@@ -314,12 +314,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);
}
return g_test_run();
diff --git a/tests/qemu-iotests/283.out b/tests/qemu-iotests/283.out
index d8cff22cc1..fbb7d0f619 100644
--- a/tests/qemu-iotests/283.out
+++ b/tests/qemu-iotests/283.out
@@ -5,4 +5,4 @@
{"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"}}
--
2.21.3
- [PATCH RFC 00/21] block: update graph permissions update, Vladimir Sementsov-Ogievskiy, 2020/11/23
- [PATCH 1/2] block: make bdrv_drop_intermediate() less wrong, Vladimir Sementsov-Ogievskiy, 2020/11/23
- [PATCH 01/21] tests/test-bdrv-graph-mod: add test_parallel_exclusive_write, Vladimir Sementsov-Ogievskiy, 2020/11/23
- [PATCH 2/2] block: assert that permission commit sets same permissions, Vladimir Sementsov-Ogievskiy, 2020/11/23
- [PATCH 02/21] tests/test-bdrv-graph-mod: add test_parallel_perm_update, Vladimir Sementsov-Ogievskiy, 2020/11/23
- [PATCH 03/21] util: add transactions.c, Vladimir Sementsov-Ogievskiy, 2020/11/23
- [PATCH 04/21] block: bdrv_refresh_perms: check parents compliance, Vladimir Sementsov-Ogievskiy, 2020/11/23
- [PATCH 06/21] block: rewrite bdrv_child_try_set_perm() using bdrv_refresh_perms(), Vladimir Sementsov-Ogievskiy, 2020/11/23
- [PATCH 07/21] block: inline bdrv_child_*() permission functions calls, Vladimir Sementsov-Ogievskiy, 2020/11/23
- [PATCH 08/21] block: use topological sort for permission update,
Vladimir Sementsov-Ogievskiy <=
- [PATCH 05/21] block: refactor bdrv_child* permission functions, Vladimir Sementsov-Ogievskiy, 2020/11/23
- [PATCH 09/21] block: add bdrv_drv_set_perm transaction action, Vladimir Sementsov-Ogievskiy, 2020/11/23
- [PATCH 10/21] block: add bdrv_list_* permission update functions, Vladimir Sementsov-Ogievskiy, 2020/11/23
- [PATCH 11/21] block: add bdrv_replace_child_safe() transaction action, Vladimir Sementsov-Ogievskiy, 2020/11/23
- [PATCH 12/21] block: return value from bdrv_replace_node(), Vladimir Sementsov-Ogievskiy, 2020/11/23
- [PATCH 14/21] block: add bdrv_attach_child_noperm() transaction action, Vladimir Sementsov-Ogievskiy, 2020/11/23
- [PATCH 15/21] block: split out bdrv_replace_node_noperm(), Vladimir Sementsov-Ogievskiy, 2020/11/23
- [PATCH 13/21] block: fix bdrv_replace_node_common, Vladimir Sementsov-Ogievskiy, 2020/11/23
- [PATCH 16/21] block: bdrv_append(): don't consume reference, Vladimir Sementsov-Ogievskiy, 2020/11/23
- [PATCH 21/21] block/backup-top: drop .active, Vladimir Sementsov-Ogievskiy, 2020/11/23