Re: [libvirt] [PATCHv2 5/7] snapshot: virsh fallback for snapshot-list --descendants --from

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