From patchwork Sat Feb 23 19:20:39 2019 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Vladimir Sementsov-Ogievskiy X-Patchwork-Id: 10827593 Return-Path: Received: from mail.wl.linuxfoundation.org (pdx-wl-mail.web.codeaurora.org [172.30.200.125]) by pdx-korg-patchwork-2.web.codeaurora.org (Postfix) with ESMTP id 947241399 for ; Sat, 23 Feb 2019 19:22:28 +0000 (UTC) Received: from mail.wl.linuxfoundation.org (localhost [127.0.0.1]) by mail.wl.linuxfoundation.org (Postfix) with ESMTP id 7E0062CC33 for ; Sat, 23 Feb 2019 19:22:28 +0000 (UTC) Received: by mail.wl.linuxfoundation.org (Postfix, from userid 486) id 6E94B2CC87; Sat, 23 Feb 2019 19:22:28 +0000 (UTC) X-Spam-Checker-Version: SpamAssassin 3.3.1 (2010-03-16) on pdx-wl-mail.web.codeaurora.org X-Spam-Level: X-Spam-Status: No, score=-2.9 required=2.0 tests=BAYES_00,MAILING_LIST_MULTI autolearn=ham version=3.3.1 Received: from lists.gnu.org (lists.gnu.org [209.51.188.17]) (using TLSv1 with cipher AES256-SHA (256/256 bits)) (No client certificate requested) by mail.wl.linuxfoundation.org (Postfix) with ESMTPS id CF4372CC33 for ; Sat, 23 Feb 2019 19:22:27 +0000 (UTC) Received: from localhost ([127.0.0.1]:41746 helo=lists.gnu.org) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1gxcsV-0006qb-4D for patchwork-qemu-devel@patchwork.kernel.org; Sat, 23 Feb 2019 14:22:27 -0500 Received: from eggs.gnu.org ([209.51.188.92]:54718) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1gxcr1-0005re-8i for qemu-devel@nongnu.org; Sat, 23 Feb 2019 14:20:56 -0500 Received: from Debian-exim by eggs.gnu.org with spam-scanned (Exim 4.71) (envelope-from ) id 1gxcqx-00021v-Ob for qemu-devel@nongnu.org; Sat, 23 Feb 2019 14:20:53 -0500 Received: from relay.sw.ru ([185.231.240.75]:59146) by eggs.gnu.org with esmtps (TLS1.0:DHE_RSA_AES_256_CBC_SHA1:32) (Exim 4.71) (envelope-from ) id 1gxcqr-0001z5-N0; Sat, 23 Feb 2019 14:20:47 -0500 Received: from [10.28.8.145] (helo=kvm.sw.ru) by relay.sw.ru with esmtp (Exim 4.91) (envelope-from ) id 1gxcqo-0004OX-0z; Sat, 23 Feb 2019 22:20:42 +0300 From: Vladimir Sementsov-Ogievskiy To: qemu-devel@nongnu.org, qemu-block@nongnu.org Date: Sat, 23 Feb 2019 22:20:39 +0300 Message-Id: <20190223192041.289782-2-vsementsov@virtuozzo.com> X-Mailer: git-send-email 2.18.0 In-Reply-To: <20190223192041.289782-1-vsementsov@virtuozzo.com> References: <20190223192041.289782-1-vsementsov@virtuozzo.com> X-detected-operating-system: by eggs.gnu.org: GNU/Linux 3.x X-Received-From: 185.231.240.75 Subject: [Qemu-devel] [PATCH v6 1/3] block: improve should_update_child X-BeenThere: qemu-devel@nongnu.org X-Mailman-Version: 2.1.21 Precedence: list List-Id: List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Cc: kwolf@redhat.com, vsementsov@virtuozzo.com, den@virtuozzo.com, mreitz@redhat.com Errors-To: qemu-devel-bounces+patchwork-qemu-devel=patchwork.kernel.org@nongnu.org Sender: "Qemu-devel" X-Virus-Scanned: ClamAV using ClamSMTP 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 --- 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,