14.01.2019 17:32, Max Reitz wrote: > On 29.12.18 13:20, Vladimir Sementsov-Ogievskiy wrote: >> 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 <vsement...@virtuozzo.com> >> --- >> block.c | 33 ++++++++++++++++++++++++++++----- >> 1 file changed, 28 insertions(+), 5 deletions(-) > > Just two technical details: > >> diff --git a/block.c b/block.c >> index 4f5ff2cc12..8f04f293da 100644 >> --- a/block.c >> +++ b/block.c >> @@ -3536,7 +3536,7 @@ void bdrv_close_all(void) >> >> static bool should_update_child(BdrvChild *c, BlockDriverState *to) >> { >> - BdrvChild *to_c; >> + GList *queue = NULL, *pos; > > GSList should be sufficient, I think. > >> >> if (c->role->stay_at_node) { >> return false; >> @@ -3572,13 +3572,36 @@ 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. >> + */ >> + >> + pos = queue = g_list_append(queue, to); >> + while (pos) { >> + BlockDriverState *v = pos->data; >> + BdrvChild *c2; >> + >> + QLIST_FOREACH(c2, &v->children, next) { >> + if (c2 == c) { >> + g_list_free(queue); >> + return false; >> + } >> + >> + if (g_list_find(queue, c2->bs)) { >> + continue; >> + } >> + >> + queue = g_list_append(queue, c2->bs); > > Appending to pos should be a bit quicker, I presume. (And you can > probably ignore the result, or just assert that the first argument was > returned.)
So, even better is to use GQueue, strange that I didn't. > > Max > >> } >> + >> + pos = pos->next; >> } >> >> + g_list_free(queue); >> return true; >> } >> >> > > -- Best regards, Vladimir