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

[Daniel P. Berrangé]

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.

I think that's fine. IMHO the only time we need to provide fallbacks
in virsh is if we change existing functionality to use new APIs.
This is new functionality, so requiring a connection to a new libvirtd
is perfectly normal practice.

> 
> 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? */

I'd not bother with this sentance about --topological. At most it will
encourage someone to implement this in the future which I would consider
a waste of their time :-)

With that dropped

  Reviewed-by: Daniel P. Berrangé <berrange at redhat.com>


Regards,
Daniel
-- 
|: https://berrange.com      -o-    https://www.flickr.com/photos/dberrange :|
|: https://libvirt.org         -o-            https://fstop138.berrange.com :|
|: https://entangle-photo.org    -o-    https://www.instagram.com/dberrange :|