From nobody Mon Feb 9 01:21:04 2026 Delivered-To: importer@patchew.org Received-SPF: pass (zoho.com: domain of redhat.com designates 209.132.183.28 as permitted sender) client-ip=209.132.183.28; envelope-from=libvir-list-bounces@redhat.com; helo=mx1.redhat.com; Authentication-Results: mx.zohomail.com; spf=pass (zoho.com: domain of redhat.com designates 209.132.183.28 as permitted sender) smtp.mailfrom=libvir-list-bounces@redhat.com; dmarc=pass(p=none dis=none) header.from=redhat.com Return-Path: Received: from mx1.redhat.com (mx1.redhat.com [209.132.183.28]) by mx.zohomail.com with SMTPS id 155202531495613.263357987337145; Thu, 7 Mar 2019 22:08:34 -0800 (PST) Received: from smtp.corp.redhat.com (int-mx06.intmail.prod.int.phx2.redhat.com [10.5.11.16]) (using TLSv1.2 with cipher AECDH-AES256-SHA (256/256 bits)) (No client certificate requested) by mx1.redhat.com (Postfix) with ESMTPS id 36CB4307EA90; Fri, 8 Mar 2019 06:08:33 +0000 (UTC) Received: from colo-mx.corp.redhat.com (colo-mx01.intmail.prod.int.phx2.redhat.com [10.5.11.20]) by smtp.corp.redhat.com (Postfix) with ESMTPS id 0B0A65C5FD; Fri, 8 Mar 2019 06:08:33 +0000 (UTC) Received: from lists01.pubmisc.prod.ext.phx2.redhat.com (lists01.pubmisc.prod.ext.phx2.redhat.com [10.5.19.33]) by colo-mx.corp.redhat.com (Postfix) with ESMTP id B3A85181A135; Fri, 8 Mar 2019 06:08:32 +0000 (UTC) Received: from smtp.corp.redhat.com (int-mx02.intmail.prod.int.phx2.redhat.com [10.5.11.12]) by lists01.pubmisc.prod.ext.phx2.redhat.com (8.13.8/8.13.8) with ESMTP id x2865JQX017331 for ; Fri, 8 Mar 2019 01:05:19 -0500 Received: by smtp.corp.redhat.com (Postfix) id 084E760C5F; Fri, 8 Mar 2019 06:05:19 +0000 (UTC) Received: from blue.redhat.com (ovpn-118-35.phx2.redhat.com [10.3.118.35]) by smtp.corp.redhat.com (Postfix) with ESMTP id BE41E60BE5 for ; Fri, 8 Mar 2019 06:05:18 +0000 (UTC) From: Eric Blake To: libvir-list@redhat.com Date: Fri, 8 Mar 2019 00:05:12 -0600 Message-Id: <20190308060512.17733-6-eblake@redhat.com> In-Reply-To: <20190308060512.17733-1-eblake@redhat.com> References: <20190308060512.17733-1-eblake@redhat.com> MIME-Version: 1.0 X-Scanned-By: MIMEDefang 2.79 on 10.5.11.12 X-loop: libvir-list@redhat.com Subject: [libvirt] [PATCH 5/5] virsh: Add snapshot-list --topological X-BeenThere: libvir-list@redhat.com X-Mailman-Version: 2.1.12 Precedence: junk List-Id: Development discussions about the libvirt library & tools List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Content-Transfer-Encoding: quoted-printable Sender: libvir-list-bounces@redhat.com Errors-To: libvir-list-bounces@redhat.com X-Scanned-By: MIMEDefang 2.79 on 10.5.11.16 X-Greylist: Sender IP whitelisted, not delayed by milter-greylist-4.5.16 (mx1.redhat.com [10.5.110.44]); Fri, 08 Mar 2019 06:08:33 +0000 (UTC) Content-Type: text/plain; charset="utf-8" To some extent, virsh already has a (shockingly naive [1]) client-side topological sorter with the --tree option. But as a series of REDEFINE calls must be presented in topological order, it's worth letting the server do the work for us. [1] The XXX comment about O(n^3) in virshSnapshotListCollect() is telling; https://en.wikipedia.org/wiki/Topological_sorting is an interesting resource for anyone motivated to use a more elegant algorithm than brute force. For now, I am purposefully NOT implementing virsh fallback code to provide a topological sort when the flag was rejected as unsupported; we can worry about that down the road if users actually demonstrate that they use new virsh but old libvirt to even need the fallback. The test driver makes it easy to test: $ virsh -c test:///default ' snapshot-create-as test a snapshot-create-as test c snapshot-create-as test b snapshot-list test snapshot-list test --topological snapshot-list test --descendants a snapshot-list test --descendants a --topological snapshot-list test --tree snapshot-list test --tree --topological ' Without --topological, virsh does client-side sorting alphabetically, and lists 'b' before 'c' (even though 'c' is the parent of 'b'); with the flag, virsh skips sorting, and you can now see that the server handed back data in a correct ordering. As shown here with a simple linear chain, there isn't any other possible ordering, and --tree mode doesn't seem to care whether --topological is used. But it is possible to compose more complicated DAGs with multiple children to a parent (representing reverting back to a snapshot then creating more snapshots along those divergent execution timelines), where it may become possible to observe non-deterministic behavior when --topological is in use, but even so, the result will still be topologically correct. Signed-off-by: Eric Blake Reviewed-by: J=C3=A1n Tomko --- tools/virsh-snapshot.c | 16 +++++++++++++--- tools/virsh.pod | 7 ++++++- 2 files changed, 19 insertions(+), 4 deletions(-) diff --git a/tools/virsh-snapshot.c b/tools/virsh-snapshot.c index 025321c58e..31153f5b10 100644 --- a/tools/virsh-snapshot.c +++ b/tools/virsh-snapshot.c @@ -1272,7 +1272,9 @@ virshSnapshotListCollect(vshControl *ctl, virDomainPt= r dom, * still in list. We mark known descendants by clearing * snaps[i].parents. Sorry, this is O(n^3) - hope your * hierarchy isn't huge. XXX Is it worth making O(n^2 log n) - * by using qsort and bsearch? */ + * by using qsort and bsearch? Or even a linear topological + * sort such as Kahn's algorithm? Should we emulate + * --topological for older libvirt that lacked the flag? */ if (start_index < 0) { vshError(ctl, _("snapshot %s disappeared from list"), fromname= ); goto cleanup; @@ -1351,8 +1353,9 @@ virshSnapshotListCollect(vshControl *ctl, virDomainPt= r dom, } } } - qsort(snaplist->snaps, snaplist->nsnaps, sizeof(*snaplist->snaps), - virshSnapSorter); + if (!(orig_flags & VIR_DOMAIN_SNAPSHOT_LIST_TOPOLOGICAL)) + qsort(snaplist->snaps, snaplist->nsnaps, sizeof(*snaplist->snaps), + virshSnapSorter); snaplist->nsnaps -=3D deleted; VIR_STEAL_PTR(ret, snaplist); @@ -1451,6 +1454,10 @@ static const vshCmdOptDef opts_snapshot_list[] =3D { .type =3D VSH_OT_BOOL, .help =3D N_("list snapshot names only") }, + {.name =3D "topological", + .type =3D VSH_OT_BOOL, + .help =3D N_("sort list topologically rather than by name"), + }, {.name =3D NULL} }; @@ -1512,6 +1519,9 @@ cmdSnapshotList(vshControl *ctl, const vshCmd *cmd) FILTER("external", EXTERNAL); #undef FILTER + if (vshCommandOptBool(cmd, "topological")) + flags |=3D VIR_DOMAIN_SNAPSHOT_LIST_TOPOLOGICAL; + if (roots) flags |=3D VIR_DOMAIN_SNAPSHOT_LIST_ROOTS; diff --git a/tools/virsh.pod b/tools/virsh.pod index 5759a396d4..66e2bf24ec 100644 --- a/tools/virsh.pod +++ b/tools/virsh.pod @@ -4726,7 +4726,7 @@ Output basic information about a named , or= the current snapshot with I<--current>. =3Ditem B I [I<--metadata>] [I<--no-metadata>] -[{I<--parent> | I<--roots> | [{I<--tree> | I<--name>}]}] +[{I<--parent> | I<--roots> | [{I<--tree> | I<--name>}]}] [I<--topological>] [{[I<--from>] B | I<--current>} [I<--descendants>]] [I<--leaves>] [I<--no-leaves>] [I<--inactive>] [I<--active>] [I<--disk-only>] [I<--internal>] [I<--external>] @@ -4734,6 +4734,11 @@ with I<--current>. List all of the available snapshots for the given domain, defaulting to show columns for the snapshot name, creation time, and domain state. +Normally, table form output is sorted by snapshot name; using +I<--topological> instead sorts so that no child is listed before its +ancestors (although there may be more than one possible ordering with +this property). + If I<--parent> is specified, add a column to the output table giving the name of the parent of each snapshot. If I<--roots> is specified, the list will be filtered to just snapshots that have no parents. --=20 2.20.1 -- libvir-list mailing list libvir-list@redhat.com https://www.redhat.com/mailman/listinfo/libvir-list