[libvirt] [PATCH 5/5] virsh: Add snapshot-list --topological
Ján Tomko
jtomko at redhat.com
Tue Mar 12 16:05:50 UTC 2019
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>
More information about the libvir-list
mailing list