12:05 a.m.
While working to add new API for bulk dumpxml/redefine, and turn
virDomainSnapshotObjList into a base class for sharing with
checkpoints, I realized how trivial it would be to take advantage of
information already present on the server, instead of using a lot of
CPU time with 'virsh snapshot-list --tree' to reconstruct a DAG on
the client side.
Eric Blake (5):
snapshots: Add flag to guarantee topological sort
snapshots: Support topological visits
test: Support topological visits
qemu: Support topological visits
virsh: Add snapshot-list --topological
include/libvirt/libvirt-domain-snapshot.h | 4 +++
src/conf/snapshot_conf.c | 15 +++++---
src/libvirt-domain-snapshot.c | 42 ++++++++++++++++++++++-
src/qemu/qemu_driver.c | 6 ++++
src/test/test_driver.c | 6 ++++
tools/virsh-snapshot.c | 16 +++++++--
tools/virsh.pod | 7 +++-
7 files changed, 86 insertions(+), 10 deletions(-)
--
2.20.1
12:05 a.m.
New subject: [libvirt] [PATCH 1/5] snapshots: Add flag to guarantee topological sort
When doing REDEFINE on multiple snapshot metadata XML descriptions, we
require that a child cannot be redefined before its parent. Since
libvirt already tracks a DAG, it is more convenient if we can ensure
that virDomainListAllSnapshots() and friends have a way to return data
in an order that we can directly reuse, rather than having to
post-process the data ourselves to reconstruct the DAG.
Add VIR_DOMAIN_SNAPSHOT_LIST_TOPOLOGICAL as our new guarantee (well, a
guarantee at the time of the API call conclusion; there's always a
possible TOCTTOU race where someone redefining snapshots in between
the API results and the client actually using the list might render
the list out-of-date). Four listing APIs are directly benefitted by
the new flag; additionally, since we document that the older racy
ListNames interfaces should be sized by using the same flags on their
Num counterparts, the Num interfaces must document when they accept
(and ignore) the flag.
Signed-off-by: Eric Blake <eblake(a)redhat.com>
---
include/libvirt/libvirt-domain-snapshot.h | 4 +++
src/libvirt-domain-snapshot.c | 42 ++++++++++++++++++++++-
2 files changed, 45 insertions(+), 1 deletion(-)
diff --git a/include/libvirt/libvirt-domain-snapshot.h
b/include/libvirt/libvirt-domain-snapshot.h
index d9b689abbd..602e5def59 100644
--- a/include/libvirt/libvirt-domain-snapshot.h
+++ b/include/libvirt/libvirt-domain-snapshot.h
@@ -135,6 +135,10 @@ typedef enum {
VIR_DOMAIN_SNAPSHOT_LIST_EXTERNAL = (1 << 9), /* Filter by snapshots
that use files external
to disk images */
+
+ VIR_DOMAIN_SNAPSHOT_LIST_TOPOLOGICAL = (1 << 10), /* Ensure parents occur
+ before children in
+ the resulting list */
} virDomainSnapshotListFlags;
/* Return the number of snapshots for this domain */
diff --git a/src/libvirt-domain-snapshot.c b/src/libvirt-domain-snapshot.c
index 11d84289f8..d133c84933 100644
--- a/src/libvirt-domain-snapshot.c
+++ b/src/libvirt-domain-snapshot.c
@@ -1,7 +1,7 @@
/*
* libvirt-domain-snapshot.c: entry points for virDomainSnapshotPtr APIs
*
- * Copyright (C) 2006-2014 Red Hat, Inc.
+ * Copyright (C) 2006-2019 Red Hat, Inc.
*
* This library is free software; you can redistribute it and/or
* modify it under the terms of the GNU Lesser General Public
@@ -298,6 +298,10 @@ virDomainSnapshotGetXMLDesc(virDomainSnapshotPtr snapshot,
*
* Provides the number of domain snapshots for this domain.
*
+ * This function will accept VIR_DOMAIN_SNAPSHOT_LIST_TOPOLOGICAL in
+ * @flags only if virDomainSnapshotListNames() can honor it, although
+ * the flag has no other effect here.
+ *
* By default, this command covers all snapshots; it is also possible to
* limit things to just snapshots with no parents, when @flags includes
* VIR_DOMAIN_SNAPSHOT_LIST_ROOTS. Additional filters are provided in
@@ -369,6 +373,14 @@ virDomainSnapshotNum(virDomainPtr domain, unsigned int flags)
* their names in @names. The value to use for @nameslen can be determined
* by virDomainSnapshotNum() with the same @flags.
*
+ * If @flags contains VIR_DOMAIN_SNAPSHOT_LIST_TOPOLOGICAL, and no
+ * other connection is modifying snapshots, then it is guaranteed that
+ * for any snapshot in the resulting list, then no snapshots later in
+ * the list can be reached by a sequence of
+ * virDomainSnapshotGetParent() starting from that snapshot;
+ * otherwise, the order of snapshots in the resulting list is
+ * unspecified.
+ *
* By default, this command covers all snapshots; it is also possible to
* limit things to just snapshots with no parents, when @flags includes
* VIR_DOMAIN_SNAPSHOT_LIST_ROOTS. Additional filters are provided in
@@ -457,6 +469,14 @@ virDomainSnapshotListNames(virDomainPtr domain, char **names, int
nameslen,
* an array to store those objects. This API solves the race inherent in
* virDomainSnapshotListNames().
*
+ * If @flags contains VIR_DOMAIN_SNAPSHOT_LIST_TOPOLOGICAL and @snaps
+ * is non-NULL, and no other connection is modifying snapshots, then
+ * it is guaranteed that for any snapshot in the resulting list, no
+ * snapshots later in the list can be reached by a sequence of
+ * virDomainSnapshotGetParent() starting from that snapshot;
+ * otherwise, the order of snapshots in the resulting list is
+ * unspecified.
+ *
* By default, this command covers all snapshots; it is also possible to
* limit things to just snapshots with no parents, when @flags includes
* VIR_DOMAIN_SNAPSHOT_LIST_ROOTS. Additional filters are provided in
@@ -533,6 +553,10 @@ virDomainListAllSnapshots(virDomainPtr domain, virDomainSnapshotPtr
**snaps,
*
* Provides the number of child snapshots for this domain snapshot.
*
+ * This function will accept VIR_DOMAIN_SNAPSHOT_LIST_TOPOLOGICAL in
+ * @flags only if virDomainSnapshotListChildrenNames() can honor it,
+ * although the flag has no other effect here.
+ *
* By default, this command covers only direct children; it is also possible
* to expand things to cover all descendants, when @flags includes
* VIR_DOMAIN_SNAPSHOT_LIST_DESCENDANTS. Also, some filters are provided in
@@ -605,6 +629,14 @@ virDomainSnapshotNumChildren(virDomainSnapshotPtr snapshot, unsigned
int flags)
* @nameslen can be determined by virDomainSnapshotNumChildren() with
* the same @flags.
*
+ * If @flags lacks VIR_DOMAIN_SNAPSHOT_LIST_DESCENDANTS or contains
+ * VIR_DOMAIN_SNAPSHOT_LIST_TOPOLOGICAL, and no other connection is
+ * modifying snapshots, then it is guaranteed that for any snapshot in
+ * the resulting list, no snapshots later in the list can be reached
+ * by a sequence of virDomainSnapshotGetParent() starting from that
+ * snapshot; otherwise, the order of snapshots in the resulting list
+ * is unspecified.
+ *
* By default, this command covers only direct children; it is also possible
* to expand things to cover all descendants, when @flags includes
* VIR_DOMAIN_SNAPSHOT_LIST_DESCENDANTS. Also, some filters are provided in
@@ -697,6 +729,14 @@ virDomainSnapshotListChildrenNames(virDomainSnapshotPtr snapshot,
* snapshot, and allocate an array to store those objects. This API solves
* the race inherent in virDomainSnapshotListChildrenNames().
*
+ * If @flags lacks VIR_DOMAIN_SNAPSHOT_LIST_DESCENDANTS or contains
+ * VIR_DOMAIN_SNAPSHOT_LIST_TOPOLOGICAL, @snaps is non-NULL, and no
+ * other connection is modifying snapshots, then it is guaranteed that
+ * for any snapshot in the resulting list, no snapshots later in the
+ * list can be reached by a sequence of virDomainSnapshotGetParent()
+ * starting from that snapshot; otherwise, the order of snapshots in
+ * the resulting list is unspecified.
+ *
* By default, this command covers only direct children; it is also possible
* to expand things to cover all descendants, when @flags includes
* VIR_DOMAIN_SNAPSHOT_LIST_DESCENDANTS. Also, some filters are provided in
--
2.20.1
11:03 a.m.
New subject: [libvirt] [PATCH 1/5] snapshots: Add flag to guarantee topological sort
On Fri, Mar 08, 2019 at 12:05:08AM -0600, Eric Blake wrote:
When doing REDEFINE on multiple snapshot metadata XML descriptions,
we
require that a child cannot be redefined before its parent. Since
libvirt already tracks a DAG, it is more convenient if we can ensure
that virDomainListAllSnapshots() and friends have a way to return data
in an order that we can directly reuse, rather than having to
post-process the data ourselves to reconstruct the DAG.
Add VIR_DOMAIN_SNAPSHOT_LIST_TOPOLOGICAL as our new guarantee (well, a
guarantee at the time of the API call conclusion; there's always a
possible TOCTTOU race where someone redefining snapshots in between
the API results and the client actually using the list might render
the list out-of-date). Four listing APIs are directly benefitted by
the new flag; additionally, since we document that the older racy
ListNames interfaces should be sized by using the same flags on their
Num counterparts, the Num interfaces must document when they accept
(and ignore) the flag.
I'd rather deal with that by not introducing the new flag to the old
APIs. The ListAll APIs were introduced back in 2012 and are even older
than the minimum QEMU version we support.
Signed-off-by: Eric Blake <eblake(a)redhat.com>
---
include/libvirt/libvirt-domain-snapshot.h | 4 +++
src/libvirt-domain-snapshot.c | 42 ++++++++++++++++++++++-
2 files changed, 45 insertions(+), 1 deletion(-)
diff --git a/include/libvirt/libvirt-domain-snapshot.h
b/include/libvirt/libvirt-domain-snapshot.h
index d9b689abbd..602e5def59 100644
--- a/include/libvirt/libvirt-domain-snapshot.h
+++ b/include/libvirt/libvirt-domain-snapshot.h
@@ -135,6 +135,10 @@ typedef enum {
VIR_DOMAIN_SNAPSHOT_LIST_EXTERNAL = (1 << 9), /* Filter by snapshots
that use files external
to disk images */
+
+ VIR_DOMAIN_SNAPSHOT_LIST_TOPOLOGICAL = (1 << 10), /* Ensure parents occur
+ before children in
+ the resulting list */
} virDomainSnapshotListFlags;
/* Return the number of snapshots for this domain */
diff --git a/src/libvirt-domain-snapshot.c b/src/libvirt-domain-snapshot.c
index 11d84289f8..d133c84933 100644
--- a/src/libvirt-domain-snapshot.c
+++ b/src/libvirt-domain-snapshot.c
@@ -1,7 +1,7 @@
/*
* libvirt-domain-snapshot.c: entry points for virDomainSnapshotPtr APIs
*
- * Copyright (C) 2006-2014 Red Hat, Inc.
+ * Copyright (C) 2006-2019 Red Hat, Inc.
*
* This library is free software; you can redistribute it and/or
* modify it under the terms of the GNU Lesser General Public
So only these two hunks would be needed:
@@ -457,6 +469,14 @@ virDomainSnapshotListNames(virDomainPtr domain,
char **names, int nameslen,
* an array to store those objects. This API solves the race inherent in
* virDomainSnapshotListNames().
*
+ * If @flags contains VIR_DOMAIN_SNAPSHOT_LIST_TOPOLOGICAL and @snaps
+ * is non-NULL, and no other connection is modifying snapshots, then
+ * it is guaranteed that for any snapshot in the resulting list, no
+ * snapshots later in the list can be reached by a sequence of
+ * virDomainSnapshotGetParent() starting from that snapshot;
+ * otherwise, the order of snapshots in the resulting list is
+ * unspecified.
+ *
* By default, this command covers all snapshots; it is also possible to
* limit things to just snapshots with no parents, when @flags includes
* VIR_DOMAIN_SNAPSHOT_LIST_ROOTS. Additional filters are provided in
@@ -697,6 +729,14 @@
virDomainSnapshotListChildrenNames(virDomainSnapshotPtr snapshot,
* snapshot, and allocate an array to store those objects. This API solves
* the race inherent in virDomainSnapshotListChildrenNames().
*
+ * If @flags lacks VIR_DOMAIN_SNAPSHOT_LIST_DESCENDANTS or contains
+ * VIR_DOMAIN_SNAPSHOT_LIST_TOPOLOGICAL, @snaps is non-NULL, and no
+ * other connection is modifying snapshots, then it is guaranteed that
+ * for any snapshot in the resulting list, no snapshots later in the
+ * list can be reached by a sequence of virDomainSnapshotGetParent()
+ * starting from that snapshot; otherwise, the order of snapshots in
+ * the resulting list is unspecified.
+ *
* By default, this command covers only direct children; it is also possible
* to expand things to cover all descendants, when @flags includes
* VIR_DOMAIN_SNAPSHOT_LIST_DESCENDANTS. Also, some filters are provided in
Reviewed-by: Ján Tomko <jtomko(a)redhat.com>
Jano
11:10 a.m.
New subject: [libvirt] [PATCH 1/5] snapshots: Add flag to guarantee topological sort
On 3/12/19 11:03 AM, Ján Tomko wrote:
On Fri, Mar 08, 2019 at 12:05:08AM -0600, Eric Blake wrote:
> When doing REDEFINE on multiple snapshot metadata XML descriptions, we
> require that a child cannot be redefined before its parent. Since
> libvirt already tracks a DAG, it is more convenient if we can ensure
> that virDomainListAllSnapshots() and friends have a way to return data
> in an order that we can directly reuse, rather than having to
> post-process the data ourselves to reconstruct the DAG.
>
> Add VIR_DOMAIN_SNAPSHOT_LIST_TOPOLOGICAL as our new guarantee (well, a
> guarantee at the time of the API call conclusion; there's always a
> possible TOCTTOU race where someone redefining snapshots in between
> the API results and the client actually using the list might render
> the list out-of-date). Four listing APIs are directly benefitted by
> the new flag; additionally, since we document that the older racy
> ListNames interfaces should be sized by using the same flags on their
> Num counterparts, the Num interfaces must document when they accept
> (and ignore) the flag.
>
I'd rather deal with that by not introducing the new flag to the old
APIs. The ListAll APIs were introduced back in 2012 and are even older
than the minimum QEMU version we support.
It's easy enough (in later patches) to NOT accept the new flag in the
virCheckFlags() macro for the implementation of those functions. On the
other hand, it's trivial to support. But if you don't like new flags to
old APIs, even though the old and new APIs share a common enum, I can
make that change.
Reviewed-by: Ján Tomko <jtomko(a)redhat.com>
Jano
--
Eric Blake, Principal Software Engineer
Red Hat, Inc. +1-919-301-3226
Virtualization: qemu.org | libvirt.org
12:27 p.m.
New subject: [libvirt] [PATCH 1/5] snapshots: Add flag to guarantee topological sort
On Tue, Mar 12, 2019 at 05:03:32PM +0100, Ján Tomko wrote:
On Fri, Mar 08, 2019 at 12:05:08AM -0600, Eric Blake wrote:
> When doing REDEFINE on multiple snapshot metadata XML descriptions, we
> require that a child cannot be redefined before its parent. Since
> libvirt already tracks a DAG, it is more convenient if we can ensure
> that virDomainListAllSnapshots() and friends have a way to return data
> in an order that we can directly reuse, rather than having to
> post-process the data ourselves to reconstruct the DAG.
>
> Add VIR_DOMAIN_SNAPSHOT_LIST_TOPOLOGICAL as our new guarantee (well, a
> guarantee at the time of the API call conclusion; there's always a
> possible TOCTTOU race where someone redefining snapshots in between
> the API results and the client actually using the list might render
> the list out-of-date). Four listing APIs are directly benefitted by
> the new flag; additionally, since we document that the older racy
> ListNames interfaces should be sized by using the same flags on their
> Num counterparts, the Num interfaces must document when they accept
> (and ignore) the flag.
>
I'd rather deal with that by not introducing the new flag to the old
APIs. The ListAll APIs were introduced back in 2012 and are even older
than the minimum QEMU version we support.
I don't much like that idea. The existing virDomainSnapshotListFlags
constants apply to all the APIs. Special casing the new enum constant
so that it only applies to some of the APIs is needlessly creating an
inconsistency for no obvious benefit.
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 :|
12:32 p.m.
New subject: [libvirt] [PATCH 1/5] snapshots: Add flag to guarantee topological sort
On Fri, Mar 08, 2019 at 12:05:08AM -0600, Eric Blake wrote:
When doing REDEFINE on multiple snapshot metadata XML descriptions,
we
require that a child cannot be redefined before its parent. Since
libvirt already tracks a DAG, it is more convenient if we can ensure
that virDomainListAllSnapshots() and friends have a way to return data
in an order that we can directly reuse, rather than having to
post-process the data ourselves to reconstruct the DAG.
Add VIR_DOMAIN_SNAPSHOT_LIST_TOPOLOGICAL as our new guarantee (well, a
guarantee at the time of the API call conclusion; there's always a
possible TOCTTOU race where someone redefining snapshots in between
the API results and the client actually using the list might render
the list out-of-date). Four listing APIs are directly benefitted by
the new flag; additionally, since we document that the older racy
ListNames interfaces should be sized by using the same flags on their
Num counterparts, the Num interfaces must document when they accept
(and ignore) the flag.
Signed-off-by: Eric Blake <eblake(a)redhat.com>
---
include/libvirt/libvirt-domain-snapshot.h | 4 +++
src/libvirt-domain-snapshot.c | 42 ++++++++++++++++++++++-
2 files changed, 45 insertions(+), 1 deletion(-)
Reviewed-by: Daniel P. Berrangé <berrange(a)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 :|
12:05 a.m.
New subject: [libvirt] [PATCH 2/5] snapshots: Support topological visits
Wire up support for VIR_DOMAIN_SNAPSHOT_LIST_TOPOLOGICAL in the
domain-agnostic support code.
Clients of snapshot_conf were previously getting a depth-first search
on anything that used virDomainSnapshotForEachDescendant(); but a
switch to a breadth-first search will give a topological search.
With that change, we now always have a topological sort for
virDomainSnapshotListAllChildren(); then with one more tweak, we
can get a topological rather than a faster random hash visit
for virDomainListAllSnapshots().
Note that virDomainSnapshotForEach() still uses a random hash
visit; we could change that signature to take a tri-state for
random, depth-first, or breadth-first visit if we ever had clients
that cared about the distinctions, but for now, none of the
drivers seem to care.
Signed-off-by: Eric Blake <eblake(a)redhat.com>
---
src/conf/snapshot_conf.c | 15 ++++++++++-----
1 file changed, 10 insertions(+), 5 deletions(-)
diff --git a/src/conf/snapshot_conf.c b/src/conf/snapshot_conf.c
index 224f3e6ca1..e2c91a5072 100644
--- a/src/conf/snapshot_conf.c
+++ b/src/conf/snapshot_conf.c
@@ -1213,9 +1213,10 @@ virDomainSnapshotObjListGetNames(virDomainSnapshotObjListPtr
snapshots,
from = &snapshots->metaroot;
}
- /* We handle LIST_ROOT/LIST_DESCENDANTS directly, mask that bit
- * out to determine when we must use the filter callback. */
- data.flags &= ~VIR_DOMAIN_SNAPSHOT_LIST_DESCENDANTS;
+ /* We handle LIST_ROOT/LIST_DESCENDANTS and LIST_TOPOLOGICAL directly,
+ * mask those bits out to determine when we must use the filter callback. */
+ data.flags &= ~(VIR_DOMAIN_SNAPSHOT_LIST_DESCENDANTS |
+ VIR_DOMAIN_SNAPSHOT_LIST_TOPOLOGICAL);
/* If this common code is being used, we assume that all snapshots
* have metadata, and thus can handle METADATA up front as an
@@ -1240,7 +1241,11 @@ virDomainSnapshotObjListGetNames(virDomainSnapshotObjListPtr
snapshots,
data.flags &= ~VIR_DOMAIN_SNAPSHOT_FILTERS_LOCATION;
if (flags & VIR_DOMAIN_SNAPSHOT_LIST_DESCENDANTS) {
- if (from->def)
+ /* We could just always do a topological visit; but it is
+ * possible to optimize for less stack usage and time when a
+ * simpler full hashtable visit or counter will do. */
+ if (from->def || (names &&
+ (flags & VIR_DOMAIN_SNAPSHOT_LIST_TOPOLOGICAL)))
virDomainSnapshotForEachDescendant(from,
virDomainSnapshotObjListCopyNames,
&data);
@@ -1327,10 +1332,10 @@ virDomainSnapshotActOnDescendant(void *payload,
virDomainSnapshotObjPtr obj = payload;
struct snapshot_act_on_descendant *curr = data;
+ (curr->iter)(payload, name, curr->data);
curr->number += 1 + virDomainSnapshotForEachDescendant(obj,
curr->iter,
curr->data);
- (curr->iter)(payload, name, curr->data);
return 0;
}
--
2.20.1
11:03 a.m.
New subject: [libvirt] [PATCH 2/5] snapshots: Support topological visits
On Fri, Mar 08, 2019 at 12:05:09AM -0600, Eric Blake wrote:
Wire up support for VIR_DOMAIN_SNAPSHOT_LIST_TOPOLOGICAL in the
domain-agnostic support code.
Clients of snapshot_conf were previously getting a depth-first search
on anything that used virDomainSnapshotForEachDescendant(); but a
switch to a breadth-first search will give a topological search.
With that change, we now always have a topological sort for
virDomainSnapshotListAllChildren(); then with one more tweak, we
can get a topological rather than a faster random hash visit
for virDomainListAllSnapshots().
Note that virDomainSnapshotForEach() still uses a random hash
visit; we could change that signature to take a tri-state for
random, depth-first, or breadth-first visit if we ever had clients
that cared about the distinctions, but for now, none of the
drivers seem to care.
Signed-off-by: Eric Blake <eblake(a)redhat.com>
---
src/conf/snapshot_conf.c | 15 ++++++++++-----
1 file changed, 10 insertions(+), 5 deletions(-)
Reviewed-by: Ján Tomko <jtomko(a)redhat.com>
Jano
12:32 p.m.
New subject: [libvirt] [PATCH 2/5] snapshots: Support topological visits
On Fri, Mar 08, 2019 at 12:05:09AM -0600, Eric Blake wrote:
Wire up support for VIR_DOMAIN_SNAPSHOT_LIST_TOPOLOGICAL in the
domain-agnostic support code.
Clients of snapshot_conf were previously getting a depth-first search
on anything that used virDomainSnapshotForEachDescendant(); but a
switch to a breadth-first search will give a topological search.
With that change, we now always have a topological sort for
virDomainSnapshotListAllChildren(); then with one more tweak, we
can get a topological rather than a faster random hash visit
for virDomainListAllSnapshots().
Note that virDomainSnapshotForEach() still uses a random hash
visit; we could change that signature to take a tri-state for
random, depth-first, or breadth-first visit if we ever had clients
that cared about the distinctions, but for now, none of the
drivers seem to care.
Signed-off-by: Eric Blake <eblake(a)redhat.com>
---
src/conf/snapshot_conf.c | 15 ++++++++++-----
1 file changed, 10 insertions(+), 5 deletions(-)
Reviewed-by: Daniel P. Berrangé <berrange(a)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 :|
12:05 a.m.
New subject: [libvirt] [PATCH 3/5] test: Support topological visits
snapshot_conf does all the hard work, the test driver just has to
accept the new flag.
Signed-off-by: Eric Blake <eblake(a)redhat.com>
---
src/test/test_driver.c | 6 ++++++
1 file changed, 6 insertions(+)
diff --git a/src/test/test_driver.c b/src/test/test_driver.c
index ef754658f3..02cd4f4d07 100644
--- a/src/test/test_driver.c
+++ b/src/test/test_driver.c
@@ -5960,6 +5960,7 @@ testDomainSnapshotNum(virDomainPtr domain, unsigned int flags)
int n;
virCheckFlags(VIR_DOMAIN_SNAPSHOT_LIST_ROOTS |
+ VIR_DOMAIN_SNAPSHOT_LIST_TOPOLOGICAL |
VIR_DOMAIN_SNAPSHOT_FILTERS_ALL, -1);
if (!(vm = testDomObjFromDomain(domain)))
@@ -5981,6 +5982,7 @@ testDomainSnapshotListNames(virDomainPtr domain,
int n;
virCheckFlags(VIR_DOMAIN_SNAPSHOT_LIST_ROOTS |
+ VIR_DOMAIN_SNAPSHOT_LIST_TOPOLOGICAL |
VIR_DOMAIN_SNAPSHOT_FILTERS_ALL, -1);
if (!(vm = testDomObjFromDomain(domain)))
@@ -6002,6 +6004,7 @@ testDomainListAllSnapshots(virDomainPtr domain,
int n;
virCheckFlags(VIR_DOMAIN_SNAPSHOT_LIST_ROOTS |
+ VIR_DOMAIN_SNAPSHOT_LIST_TOPOLOGICAL |
VIR_DOMAIN_SNAPSHOT_FILTERS_ALL, -1);
if (!(vm = testDomObjFromDomain(domain)))
@@ -6024,6 +6027,7 @@ testDomainSnapshotListChildrenNames(virDomainSnapshotPtr snapshot,
int n = -1;
virCheckFlags(VIR_DOMAIN_SNAPSHOT_LIST_DESCENDANTS |
+ VIR_DOMAIN_SNAPSHOT_LIST_TOPOLOGICAL |
VIR_DOMAIN_SNAPSHOT_FILTERS_ALL, -1);
if (!(vm = testDomObjFromSnapshot(snapshot)))
@@ -6049,6 +6053,7 @@ testDomainSnapshotNumChildren(virDomainSnapshotPtr snapshot,
int n = -1;
virCheckFlags(VIR_DOMAIN_SNAPSHOT_LIST_DESCENDANTS |
+ VIR_DOMAIN_SNAPSHOT_LIST_TOPOLOGICAL |
VIR_DOMAIN_SNAPSHOT_FILTERS_ALL, -1);
if (!(vm = testDomObjFromSnapshot(snapshot)))
@@ -6074,6 +6079,7 @@ testDomainSnapshotListAllChildren(virDomainSnapshotPtr snapshot,
int n = -1;
virCheckFlags(VIR_DOMAIN_SNAPSHOT_LIST_DESCENDANTS |
+ VIR_DOMAIN_SNAPSHOT_LIST_TOPOLOGICAL |
VIR_DOMAIN_SNAPSHOT_FILTERS_ALL, -1);
if (!(vm = testDomObjFromSnapshot(snapshot)))
--
2.20.1
11:04 a.m.
New subject: [libvirt] [PATCH 3/5] test: Support topological visits
On Fri, Mar 08, 2019 at 12:05:10AM -0600, Eric Blake wrote:
snapshot_conf does all the hard work, the test driver just has to
accept the new flag.
Signed-off-by: Eric Blake <eblake(a)redhat.com>
---
src/test/test_driver.c | 6 ++++++
1 file changed, 6 insertions(+)
diff --git a/src/test/test_driver.c b/src/test/test_driver.c
index ef754658f3..02cd4f4d07 100644
--- a/src/test/test_driver.c
+++ b/src/test/test_driver.c
@@ -5960,6 +5960,7 @@ testDomainSnapshotNum(virDomainPtr domain, unsigned int flags)
int n;
virCheckFlags(VIR_DOMAIN_SNAPSHOT_LIST_ROOTS |
+ VIR_DOMAIN_SNAPSHOT_LIST_TOPOLOGICAL |
VIR_DOMAIN_SNAPSHOT_FILTERS_ALL, -1);
if (!(vm = testDomObjFromDomain(domain)))
@@ -5981,6 +5982,7 @@ testDomainSnapshotListNames(virDomainPtr domain,
int n;
virCheckFlags(VIR_DOMAIN_SNAPSHOT_LIST_ROOTS |
+ VIR_DOMAIN_SNAPSHOT_LIST_TOPOLOGICAL |
VIR_DOMAIN_SNAPSHOT_FILTERS_ALL, -1);
if (!(vm = testDomObjFromDomain(domain)))
@@ -6002,6 +6004,7 @@ testDomainListAllSnapshots(virDomainPtr domain,
int n;
virCheckFlags(VIR_DOMAIN_SNAPSHOT_LIST_ROOTS |
+ VIR_DOMAIN_SNAPSHOT_LIST_TOPOLOGICAL |
VIR_DOMAIN_SNAPSHOT_FILTERS_ALL, -1);
if (!(vm = testDomObjFromDomain(domain)))
@@ -6024,6 +6027,7 @@ testDomainSnapshotListChildrenNames(virDomainSnapshotPtr snapshot,
int n = -1;
virCheckFlags(VIR_DOMAIN_SNAPSHOT_LIST_DESCENDANTS |
+ VIR_DOMAIN_SNAPSHOT_LIST_TOPOLOGICAL |
VIR_DOMAIN_SNAPSHOT_FILTERS_ALL, -1);
if (!(vm = testDomObjFromSnapshot(snapshot)))
@@ -6049,6 +6053,7 @@ testDomainSnapshotNumChildren(virDomainSnapshotPtr snapshot,
int n = -1;
virCheckFlags(VIR_DOMAIN_SNAPSHOT_LIST_DESCENDANTS |
+ VIR_DOMAIN_SNAPSHOT_LIST_TOPOLOGICAL |
VIR_DOMAIN_SNAPSHOT_FILTERS_ALL, -1);
if (!(vm = testDomObjFromSnapshot(snapshot)))
@@ -6074,6 +6079,7 @@ testDomainSnapshotListAllChildren(virDomainSnapshotPtr snapshot,
int n = -1;
virCheckFlags(VIR_DOMAIN_SNAPSHOT_LIST_DESCENDANTS |
+ VIR_DOMAIN_SNAPSHOT_LIST_TOPOLOGICAL |
VIR_DOMAIN_SNAPSHOT_FILTERS_ALL, -1);
if (!(vm = testDomObjFromSnapshot(snapshot)))
I'd rather drop the non-ListAll versions.
Regardless:
Reviewed-by: Ján Tomko <jtomko(a)redhat.com>
Jano
12:29 p.m.
New subject: [libvirt] [PATCH 3/5] test: Support topological visits
On Tue, Mar 12, 2019 at 05:04:37PM +0100, Ján Tomko wrote:
On Fri, Mar 08, 2019 at 12:05:10AM -0600, Eric Blake wrote:
> snapshot_conf does all the hard work, the test driver just has to
> accept the new flag.
>
> Signed-off-by: Eric Blake <eblake(a)redhat.com>
> ---
> src/test/test_driver.c | 6 ++++++
> 1 file changed, 6 insertions(+)
>
> diff --git a/src/test/test_driver.c b/src/test/test_driver.c
> index ef754658f3..02cd4f4d07 100644
> --- a/src/test/test_driver.c
> +++ b/src/test/test_driver.c
> @@ -5960,6 +5960,7 @@ testDomainSnapshotNum(virDomainPtr domain, unsigned int
flags)
> int n;
>
> virCheckFlags(VIR_DOMAIN_SNAPSHOT_LIST_ROOTS |
> + VIR_DOMAIN_SNAPSHOT_LIST_TOPOLOGICAL |
> VIR_DOMAIN_SNAPSHOT_FILTERS_ALL, -1);
>
> if (!(vm = testDomObjFromDomain(domain)))
> @@ -5981,6 +5982,7 @@ testDomainSnapshotListNames(virDomainPtr domain,
> int n;
>
> virCheckFlags(VIR_DOMAIN_SNAPSHOT_LIST_ROOTS |
> + VIR_DOMAIN_SNAPSHOT_LIST_TOPOLOGICAL |
> VIR_DOMAIN_SNAPSHOT_FILTERS_ALL, -1);
>
> if (!(vm = testDomObjFromDomain(domain)))
> @@ -6002,6 +6004,7 @@ testDomainListAllSnapshots(virDomainPtr domain,
> int n;
>
> virCheckFlags(VIR_DOMAIN_SNAPSHOT_LIST_ROOTS |
> + VIR_DOMAIN_SNAPSHOT_LIST_TOPOLOGICAL |
> VIR_DOMAIN_SNAPSHOT_FILTERS_ALL, -1);
>
> if (!(vm = testDomObjFromDomain(domain)))
> @@ -6024,6 +6027,7 @@ testDomainSnapshotListChildrenNames(virDomainSnapshotPtr
snapshot,
> int n = -1;
>
> virCheckFlags(VIR_DOMAIN_SNAPSHOT_LIST_DESCENDANTS |
> + VIR_DOMAIN_SNAPSHOT_LIST_TOPOLOGICAL |
> VIR_DOMAIN_SNAPSHOT_FILTERS_ALL, -1);
>
> if (!(vm = testDomObjFromSnapshot(snapshot)))
> @@ -6049,6 +6053,7 @@ testDomainSnapshotNumChildren(virDomainSnapshotPtr snapshot,
> int n = -1;
>
> virCheckFlags(VIR_DOMAIN_SNAPSHOT_LIST_DESCENDANTS |
> + VIR_DOMAIN_SNAPSHOT_LIST_TOPOLOGICAL |
> VIR_DOMAIN_SNAPSHOT_FILTERS_ALL, -1);
>
> if (!(vm = testDomObjFromSnapshot(snapshot)))
> @@ -6074,6 +6079,7 @@ testDomainSnapshotListAllChildren(virDomainSnapshotPtr
snapshot,
> int n = -1;
>
> virCheckFlags(VIR_DOMAIN_SNAPSHOT_LIST_DESCENDANTS |
> + VIR_DOMAIN_SNAPSHOT_LIST_TOPOLOGICAL |
> VIR_DOMAIN_SNAPSHOT_FILTERS_ALL, -1);
>
> if (!(vm = testDomObjFromSnapshot(snapshot)))
I'd rather drop the non-ListAll versions.
Dropping them neeedlessly creates an inconsistency in the APIs. Right
now it is clear that all the APIs accept all the enums constants.
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 :|
12:33 p.m.
New subject: [libvirt] [PATCH 3/5] test: Support topological visits
On Fri, Mar 08, 2019 at 12:05:10AM -0600, Eric Blake wrote:
snapshot_conf does all the hard work, the test driver just has to
accept the new flag.
Signed-off-by: Eric Blake <eblake(a)redhat.com>
---
src/test/test_driver.c | 6 ++++++
1 file changed, 6 insertions(+)
Reviewed-by: Daniel P. Berrangé <berrange(a)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 :|
12:05 a.m.
New subject: [libvirt] [PATCH 4/5] qemu: Support topological visits
snapshot_conf does all the hard work, the qemu driver just has to
accept the new flag.
Signed-off-by: Eric Blake <eblake(a)redhat.com>
---
src/qemu/qemu_driver.c | 6 ++++++
1 file changed, 6 insertions(+)
diff --git a/src/qemu/qemu_driver.c b/src/qemu/qemu_driver.c
index 205e544d92..e461fb51b0 100644
--- a/src/qemu/qemu_driver.c
+++ b/src/qemu/qemu_driver.c
@@ -15972,6 +15972,7 @@ qemuDomainSnapshotListNames(virDomainPtr domain,
int n = -1;
virCheckFlags(VIR_DOMAIN_SNAPSHOT_LIST_ROOTS |
+ VIR_DOMAIN_SNAPSHOT_LIST_TOPOLOGICAL |
VIR_DOMAIN_SNAPSHOT_FILTERS_ALL, -1);
if (!(vm = qemuDomObjFromDomain(domain)))
@@ -15997,6 +15998,7 @@ qemuDomainSnapshotNum(virDomainPtr domain,
int n = -1;
virCheckFlags(VIR_DOMAIN_SNAPSHOT_LIST_ROOTS |
+ VIR_DOMAIN_SNAPSHOT_LIST_TOPOLOGICAL |
VIR_DOMAIN_SNAPSHOT_FILTERS_ALL, -1);
if (!(vm = qemuDomObjFromDomain(domain)))
@@ -16022,6 +16024,7 @@ qemuDomainListAllSnapshots(virDomainPtr domain,
int n = -1;
virCheckFlags(VIR_DOMAIN_SNAPSHOT_LIST_ROOTS |
+ VIR_DOMAIN_SNAPSHOT_LIST_TOPOLOGICAL |
VIR_DOMAIN_SNAPSHOT_FILTERS_ALL, -1);
if (!(vm = qemuDomObjFromDomain(domain)))
@@ -16049,6 +16052,7 @@ qemuDomainSnapshotListChildrenNames(virDomainSnapshotPtr
snapshot,
int n = -1;
virCheckFlags(VIR_DOMAIN_SNAPSHOT_LIST_DESCENDANTS |
+ VIR_DOMAIN_SNAPSHOT_LIST_TOPOLOGICAL |
VIR_DOMAIN_SNAPSHOT_FILTERS_ALL, -1);
if (!(vm = qemuDomObjFromSnapshot(snapshot)))
@@ -16078,6 +16082,7 @@ qemuDomainSnapshotNumChildren(virDomainSnapshotPtr snapshot,
int n = -1;
virCheckFlags(VIR_DOMAIN_SNAPSHOT_LIST_DESCENDANTS |
+ VIR_DOMAIN_SNAPSHOT_LIST_TOPOLOGICAL |
VIR_DOMAIN_SNAPSHOT_FILTERS_ALL, -1);
if (!(vm = qemuDomObjFromSnapshot(snapshot)))
@@ -16107,6 +16112,7 @@ qemuDomainSnapshotListAllChildren(virDomainSnapshotPtr snapshot,
int n = -1;
virCheckFlags(VIR_DOMAIN_SNAPSHOT_LIST_DESCENDANTS |
+ VIR_DOMAIN_SNAPSHOT_LIST_TOPOLOGICAL |
VIR_DOMAIN_SNAPSHOT_FILTERS_ALL, -1);
if (!(vm = qemuDomObjFromSnapshot(snapshot)))
--
2.20.1
11:04 a.m.
New subject: [libvirt] [PATCH 4/5] qemu: Support topological visits
On Fri, Mar 08, 2019 at 12:05:11AM -0600, Eric Blake wrote:
snapshot_conf does all the hard work, the qemu driver just has to
accept the new flag.
Signed-off-by: Eric Blake <eblake(a)redhat.com>
---
src/qemu/qemu_driver.c | 6 ++++++
1 file changed, 6 insertions(+)
Same here.
Reviewed-by: Ján Tomko <jtomko(a)redhat.com>
Jano
12:33 p.m.
New subject: [libvirt] [PATCH 4/5] qemu: Support topological visits
On Fri, Mar 08, 2019 at 12:05:11AM -0600, Eric Blake wrote:
snapshot_conf does all the hard work, the qemu driver just has to
accept the new flag.
Signed-off-by: Eric Blake <eblake(a)redhat.com>
---
src/qemu/qemu_driver.c | 6 ++++++
1 file changed, 6 insertions(+)
Reviewed-by: Daniel P. Berrangé <berrange(a)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 :|
12:05 a.m.
New subject: [libvirt] [PATCH 5/5] virsh: Add snapshot-list --topological
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(a)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? */
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;
diff --git a/tools/virsh.pod b/tools/virsh.pod
index 5759a396d4..66e2bf24ec 100644
--- a/tools/virsh.pod
+++ b/tools/virsh.pod
@@ -4726,7 +4726,7 @@ Output basic information about a named <snapshot>, or the
current snapshot
with I<--current>.
=item B<snapshot-list> I<domain> [I<--metadata>]
[I<--no-metadata>]
-[{I<--parent> | I<--roots> | [{I<--tree> | I<--name>}]}]
+[{I<--parent> | I<--roots> | [{I<--tree> | I<--name>}]}]
[I<--topological>]
[{[I<--from>] B<snapshot> | I<--current>} [I<--descendants>]]
[I<--leaves>] [I<--no-leaves>] [I<--inactive>] [I<--active>]
[I<--disk-only>] [I<--internal>] [I<--external>]
@@ -4734,6 +4734,11 @@ with I<--current>.
List all of the available snapshots for the given domain, defaulting
to show columns for the snapshot name, creation time, and domain state.
+Normally, table form output is sorted by snapshot name; using
+I<--topological> instead sorts so that no child is listed before its
+ancestors (although there may be more than one possible ordering with
+this property).
+
If I<--parent> is specified, add a column to the output table giving
the name of the parent of each snapshot. If I<--roots> is specified,
the list will be filtered to just snapshots that have no parents.
--
2.20.1
11:05 a.m.
New subject: [libvirt] [PATCH 5/5] virsh: Add snapshot-list --topological
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(a)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(a)redhat.com>
Jano
12:36 p.m.
New subject: [libvirt] [PATCH 5/5] virsh: Add snapshot-list --topological
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(a)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(a)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 :|
10:29 a.m.
[resending with widened cc, since Jan reviewed my bulk import patches
that are built on top of this]
On 3/8/19 12:05 AM, Eric Blake wrote:
While working to add new API for bulk dumpxml/redefine, and turn
virDomainSnapshotObjList into a base class for sharing with
checkpoints, I realized how trivial it would be to take advantage of
information already present on the server, instead of using a lot of
CPU time with 'virsh snapshot-list --tree' to reconstruct a DAG on
the client side.
Eric Blake (5):
snapshots: Add flag to guarantee topological sort
snapshots: Support topological visits
test: Support topological visits
qemu: Support topological visits
virsh: Add snapshot-list --topological
include/libvirt/libvirt-domain-snapshot.h | 4 +++
src/conf/snapshot_conf.c | 15 +++++---
src/libvirt-domain-snapshot.c | 42 ++++++++++++++++++++++-
src/qemu/qemu_driver.c | 6 ++++
src/test/test_driver.c | 6 ++++
tools/virsh-snapshot.c | 16 +++++++--
tools/virsh.pod | 7 +++-
7 files changed, 86 insertions(+), 10 deletions(-)
--
Eric Blake, Principal Software Engineer
Red Hat, Inc. +1-919-301-3226
Virtualization: qemu.org | libvirt.org
2083
days inactive
2087
days old
19 comments
3 participants
participants (3)
-
Daniel P. Berrangé -
Eric Blake -
Ján Tomko