6:09 p.m.
Given a list of snapshots and their parents, finding all descendants
requires a hairy traversal. This code is O(n^3); it could maybe be
made to scale O(n^2) with the use of a hash table, but that costs more
memory. Hopefully there aren't too many people with a hierarchy
so large as to approach REMOTE_DOMAIN_SNAPSHOT_LIST_NAMES_MAX (1024).
* tools/virsh.c (cmdSnapshotList): Add final fallback.
---
v2: rebase around ctl flag
tools/virsh.c | 67 +++++++++++++++++++++++++++++++++++++++++++++++++++------
1 files changed, 60 insertions(+), 7 deletions(-)
diff --git a/tools/virsh.c b/tools/virsh.c
index b2523d3..ec6f854 100644
--- a/tools/virsh.c
+++ b/tools/virsh.c
@@ -13133,6 +13133,7 @@ cmdSnapshotList(vshControl *ctl, const vshCmd *cmd)
bool tree = vshCommandOptBool(cmd, "tree");
const char *from = NULL;
virDomainSnapshotPtr start = NULL;
+ int start_index = -1;
bool descendants = false;
if (vshCommandOptString(cmd, "from", &from) < 0) {
@@ -13187,10 +13188,8 @@ cmdSnapshotList(vshControl *ctl, const vshCmd *cmd)
numsnaps = ctl->useSnapshotOld ? -1 :
virDomainSnapshotNumChildren(start, flags);
if (numsnaps < 0) {
- /* XXX also want to emulate --descendants without --tree */
- if ((!descendants || tree) &&
- (ctl->useSnapshotOld ||
- last_error->code == VIR_ERR_NO_SUPPORT)) {
+ if (ctl->useSnapshotOld ||
+ last_error->code == VIR_ERR_NO_SUPPORT) {
/* We can emulate --from. */
virFreeError(last_error);
last_error = NULL;
@@ -13269,6 +13268,11 @@ cmdSnapshotList(vshControl *ctl, const vshCmd *cmd)
if (tree || ctl->useSnapshotOld) {
parents = vshCalloc(ctl, sizeof(char *), actual);
for (i = (from && !ctl->useSnapshotOld); i < actual; i++) {
+ if (ctl->useSnapshotOld && STREQ(names[i], from)) {
+ start_index = i;
+ continue;
+ }
+
/* free up memory from previous iterations of the loop */
if (snapshot)
virDomainSnapshotFree(snapshot);
@@ -13302,12 +13306,61 @@ cmdSnapshotList(vshControl *ctl, const vshCmd *cmd)
goto cleanup;
} else {
if (ctl->useSnapshotOld && descendants) {
- /* XXX emulate --descendants as well */
- goto cleanup;
+ bool changed = false;
+
+ /* Make multiple passes over the list - first pass NULLs
+ * out all roots except start, remaining passes NULL out
+ * any entry whose parent is not still in list. Also, we
+ * NULL out parent when name is known to be in list.
+ * Sorry, this is O(n^3) - hope your hierarchy isn't huge. */
+ if (start_index < 0) {
+ vshError(ctl, _("snapshot %s disappeared from list"), from);
+ goto cleanup;
+ }
+ for (i = 0; i < actual; i++) {
+ if (i == start_index)
+ continue;
+ if (!parents[i]) {
+ VIR_FREE(names[i]);
+ } else if (STREQ(parents[i], from)) {
+ VIR_FREE(parents[i]);
+ changed = true;
+ }
+ }
+ if (!changed) {
+ ret = true;
+ goto cleanup;
+ }
+ while (changed) {
+ changed = false;
+ for (i = 0; i < actual; i++) {
+ bool found = false;
+ int j;
+
+ if (!names[i] || !parents[i])
+ continue;
+ for (j = 0; j < actual; j++) {
+ if (!names[j] || i == j)
+ continue;
+ if (STREQ(parents[i], names[j])) {
+ found = true;
+ if (!parents[j])
+ VIR_FREE(parents[i]);
+ break;
+ }
+ }
+ if (!found) {
+ changed = true;
+ VIR_FREE(names[i]);
+ }
+ }
+ }
+ VIR_FREE(names[start_index]);
}
for (i = 0; i < actual; i++) {
- if (ctl->useSnapshotOld && STRNEQ_NULLABLE(parents[i], from))
+ if (ctl->useSnapshotOld &&
+ (descendants ? !names[i] : STRNEQ_NULLABLE(parents[i], from)))
continue;
/* free up memory from previous iterations of the loop */
--
1.7.4.4