[libvirt] [PATCH 5/5] virsh: Add snapshot-list --topological

[Ján Tomko]

On Fri, Mar 08, 2019 at 12:05:12AM -0600, Eric Blake wrote:
>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 <eblake at redhat.com>
>---
> 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, virDomainPtr 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? */

Unrelated hunk. Also, dangerous question - why would anyone attempt
that?

>         if (start_index < 0) {
>             vshError(ctl, _("snapshot %s disappeared from list"), fromname);
>             goto cleanup;
>@@ -1351,8 +1353,9 @@ virshSnapshotListCollect(vshControl *ctl, virDomainPtr 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 -= deleted;
>
>     VIR_STEAL_PTR(ret, snaplist);
>@@ -1451,6 +1454,10 @@ static const vshCmdOptDef opts_snapshot_list[] = {
>      .type = VSH_OT_BOOL,
>      .help = N_("list snapshot names only")
>     },
>+    {.name = "topological",
>+     .type = VSH_OT_BOOL,
>+     .help = N_("sort list topologically rather than by name"),
>+    },
>
>     {.name = NULL}
> };
>@@ -1512,6 +1519,9 @@ cmdSnapshotList(vshControl *ctl, const vshCmd *cmd)
>     FILTER("external", EXTERNAL);
> #undef FILTER
>
>+    if (vshCommandOptBool(cmd, "topological"))
>+        flags |= VIR_DOMAIN_SNAPSHOT_LIST_TOPOLOGICAL;
>+
>     if (roots)
>         flags |= VIR_DOMAIN_SNAPSHOT_LIST_ROOTS;
>

Reviewed-by: Ján Tomko <jtomko at redhat.com>

Jano
-------------- next part --------------
A non-text attachment was scrubbed...
Name: signature.asc
Type: application/pgp-signature
Size: 488 bytes
Desc: not available
URL: <http://listman.redhat.com/archives/libvir-list/attachments/20190312/53fade58/attachment-0001.sig>