[libvirt] [PATCH 2.7/4] snapshot: virsh fallback for snapshot-list --descendants --from

[Eric Blake]

On 09/29/2011 04:39 PM, 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.
> ---
>
> Applies anywhere after 2.6/4; same story about testing before 3/4.
>

I realized after sending the email that I can squash this in for fewer 
passes of the outer loop for slightly faster performance (borrowing 
ideas from how virDomainSnapshotForEachDescendant tackled the same 
problem of finding descendants by using two separate marks).

diff --git i/tools/virsh.c w/tools/virsh.c
index 4fbd1a8..9f3b4dc 100644
--- i/tools/virsh.c
+++ w/tools/virsh.c
@@ -13281,11 +13281,12 @@ cmdSnapshotList(vshControl *ctl, const vshCmd 
*cmd)
          goto cleanup;
      } else {
          if (emulate_from && descendants) {
-            bool changed = true;
+            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.
+             * 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);
@@ -13294,8 +13295,16 @@ cmdSnapshotList(vshControl *ctl, const vshCmd *cmd)
              for (i = 0; i < actual; i++) {
                  if (i == start_index)
                      continue;
-                if (!parents[i])
+                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;
@@ -13303,13 +13312,15 @@ cmdSnapshotList(vshControl *ctl, const vshCmd 
*cmd)
                      bool found = false;
                      int j;

-                    if (!names[i] || i == start_index)
+                    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;
                          }
                      }


-- 
Eric Blake   eblake at redhat.com    +1-801-349-2682
Libvirt virtualization library http://libvirt.org