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@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@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 :|