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 --- block.c | 116 +++++++++++++++++++++++++++++++++++++++++++++++++++++----------- 1 file changed, 96 insertions(+), 20 deletions(-) (limited to 'block.c') diff --git a/block.c b/block.c index e5af4cdae9..cbcc4c15a0 100644 --- a/block.c +++ b/block.c @@ -2054,7 +2054,9 @@ static bool bdrv_a_allow_b(BdrvChild *a, BdrvChild *b, Error **errp) return false; } -static bool bdrv_parent_perms_conflict(BlockDriverState *bs, Error **errp) +static bool bdrv_parent_perms_conflict(BlockDriverState *bs, + GSList *ignore_children, + Error **errp) { BdrvChild *a, *b; @@ -2064,8 +2066,12 @@ static bool bdrv_parent_perms_conflict(BlockDriverState *bs, Error **errp) * directions. */ QLIST_FOREACH(a, &bs->parents, next_parent) { + if (g_slist_find(ignore_children, a)) { + continue; + } + QLIST_FOREACH(b, &bs->parents, next_parent) { - if (a == b) { + if (a == b || g_slist_find(ignore_children, b)) { continue; } @@ -2094,6 +2100,40 @@ static void bdrv_child_perm(BlockDriverState *bs, BlockDriverState *child_bs, } } +/* + * Adds the whole subtree of @bs (including @bs itself) to the @list (except for + * nodes that are already in the @list, of course) so that final list is + * topologically sorted. Return the result (GSList @list object is updated, so + * don't use old reference after function call). + * + * On function start @list must be already topologically sorted and for any node + * in the @list the whole subtree of the node must be in the @list as well. The + * simplest way to satisfy this criteria: use only result of + * bdrv_topological_dfs() or NULL as @list parameter. + */ +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; @@ -2158,10 +2198,10 @@ 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; @@ -2226,21 +2266,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; +} + +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); - 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); + for ( ; list; list = list->next) { + bs = list->data; + + if (bs != root) { + if (bdrv_parent_perms_conflict(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; @@ -2250,10 +2312,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; @@ -2268,11 +2328,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; @@ -2298,7 +2366,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); } } @@ -2411,7 +2487,7 @@ static int bdrv_refresh_perms(BlockDriverState *bs, Error **errp) int ret; uint64_t perm, shared_perm; - if (bdrv_parent_perms_conflict(bs, errp)) { + if (bdrv_parent_perms_conflict(bs, NULL, errp)) { return -EPERM; } bdrv_get_cumulative_perm(bs, &perm, &shared_perm); -- cgit v1.2.3