On Fri, Sep 30, 2011 at 05:09:27PM -0600, Eric Blake wrote:
> 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 */
ACK, to be removed in second patch set anyway :-)
Daniel
--
Daniel Veillard | libxml Gnome XML XSLT toolkit http://xmlsoft.org/
daniel@xxxxxxxxxxxx | Rpmfind RPM search engine http://rpmfind.net/
http://veillard.com/ | virtualization library http://libvirt.org/
--
libvir-list mailing list
libvir-list@xxxxxxxxxx
https://www.redhat.com/mailman/listinfo/libvir-list