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@xxxxxxxxxx> > --- > 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@xxxxxxxxxx> 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 :| -- libvir-list mailing list libvir-list@xxxxxxxxxx https://www.redhat.com/mailman/listinfo/libvir-list
