Re: [PATCH 3/4] snapshot: take advantage of new relations

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

 



On Fri, Oct 07, 2011 at 06:05:56PM -0600, Eric Blake wrote:
> Among other improvements, virDomainSnapshotForEachDescendant is
> changed from iterative O(n^2) to recursive O(n).  A bit better
> than the O(n^3) implementation in virsh snapshot-list!
> 
> * src/conf/domain_conf.c (virDomainSnapshotObjListNum)
> (virDomainSnapshotObjListNumFrom)
> (virDomainSnapshotObjeListGetNames, virDomainSnapshotForEachChild)
> (virDomainSnapshotForEachDescendant): Optimize.
> (virDomainSnapshotActOnDescendant): Tweak.
> (virDomainSnapshotActOnChild, virDomainSnapshotMarkDescendant):
> Delete, now that they are unused.
> ---
>  src/conf/domain_conf.c |  148 ++++++++++++++----------------------------------
>  1 files changed, 43 insertions(+), 105 deletions(-)
> 
> diff --git a/src/conf/domain_conf.c b/src/conf/domain_conf.c
> index d4e127d..e77257a 100644
> --- a/src/conf/domain_conf.c
> +++ b/src/conf/domain_conf.c
> @@ -12163,10 +12163,21 @@ int virDomainSnapshotObjListGetNames(virDomainSnapshotObjListPtr snapshots,
>                                       char **const names, int maxnames,
>                                       unsigned int flags)
>  {
> -    struct virDomainSnapshotNameData data = { 0, 0, maxnames, names, flags };
> +    struct virDomainSnapshotNameData data = { 0, 0, maxnames, names, 0 };
>      int i;
> 
> -    virHashForEach(snapshots->objs, virDomainSnapshotObjListCopyNames, &data);
> +    data.flags = flags & ~VIR_DOMAIN_SNAPSHOT_LIST_ROOTS;
> +
> +    if (!(flags & VIR_DOMAIN_SNAPSHOT_LIST_ROOTS)) {
> +        virHashForEach(snapshots->objs, virDomainSnapshotObjListCopyNames,
> +                       &data);
> +    } else {
> +        virDomainSnapshotObjPtr root = snapshots->first_root;
> +        while (root) {
> +            virDomainSnapshotObjListCopyNames(root, root->def->name, &data);
> +            root = root->sibling;
> +        }
> +    }
>      if (data.oom) {
>          virReportOOMError();
>          goto cleanup;
> @@ -12231,9 +12242,21 @@ static void virDomainSnapshotObjListCount(void *payload,
>  int virDomainSnapshotObjListNum(virDomainSnapshotObjListPtr snapshots,
>                                  unsigned int flags)
>  {
> -    struct virDomainSnapshotNumData data = { 0, flags };
> +    struct virDomainSnapshotNumData data = { 0, 0 };
> 
> -    virHashForEach(snapshots->objs, virDomainSnapshotObjListCount, &data);
> +    data.flags = flags & ~VIR_DOMAIN_SNAPSHOT_LIST_ROOTS;
> +
> +    if (!(flags & VIR_DOMAIN_SNAPSHOT_LIST_ROOTS)) {
> +        virHashForEach(snapshots->objs, virDomainSnapshotObjListCount, &data);
> +    } else if (data.flags) {
> +        virDomainSnapshotObjPtr root = snapshots->first_root;
> +        while (root) {
> +            virDomainSnapshotObjListCount(root, root->def->name, &data);
> +            root = root->sibling;
> +        }

  I was just wondering if a data structure with a meta-root snapshot
and unifying first_root as a first_children on that meta-root wouldn't
lead to simpler code overall.

> +    } else {
> +        data.count = snapshots->nroots;
> +    }
> 
>      return data.count;
>  }
> @@ -12251,9 +12274,11 @@ virDomainSnapshotObjListNumFrom(virDomainSnapshotObjPtr snapshot,
>          virDomainSnapshotForEachDescendant(snapshots, snapshot,
>                                             virDomainSnapshotObjListCount,
>                                             &data);
> -    else
> +    else if (data.flags)
>          virDomainSnapshotForEachChild(snapshots, snapshot,
>                                        virDomainSnapshotObjListCount, &data);
> +    else
> +        data.count = snapshot->nchildren;
> 
>      return data.count;
>  }
> @@ -12271,97 +12296,23 @@ void virDomainSnapshotObjListRemove(virDomainSnapshotObjListPtr snapshots,
>      virHashRemoveEntry(snapshots->objs, snapshot->def->name);
>  }
> 
> -struct snapshot_act_on_child {
> -    char *parent;
> -    int number;
> -    virHashIterator iter;
> -    void *data;
> -};
> -
> -static void
> -virDomainSnapshotActOnChild(void *payload,
> -                            const void *name,
> -                            void *data)
> -{
> -    virDomainSnapshotObjPtr obj = payload;
> -    struct snapshot_act_on_child *curr = data;
> -
> -    if (obj->def->parent && STREQ(curr->parent, obj->def->parent)) {
> -        curr->number++;
> -        if (curr->iter)
> -            (curr->iter)(payload, name, curr->data);
> -    }
> -}
> -
>  /* Run iter(data) on all direct children of snapshot, while ignoring all
>   * other entries in snapshots.  Return the number of children
>   * visited.  No particular ordering is guaranteed.  */
>  int
> -virDomainSnapshotForEachChild(virDomainSnapshotObjListPtr snapshots,
> +virDomainSnapshotForEachChild(virDomainSnapshotObjListPtr snapshots ATTRIBUTE_UNUSED,
>                                virDomainSnapshotObjPtr snapshot,
>                                virHashIterator iter,
>                                void *data)
>  {
> -    struct snapshot_act_on_child act;
> +    virDomainSnapshotObjPtr child = snapshot->first_child;
> 
> -    act.parent = snapshot->def->name;
> -    act.number = 0;
> -    act.iter = iter;
> -    act.data = data;
> -    virHashForEach(snapshots->objs, virDomainSnapshotActOnChild, &act);
> -
> -    return act.number;
> -}
> -typedef enum {
> -    MARK_NONE,       /* No relation determined yet */
> -    MARK_DESCENDANT, /* Descendant of target */
> -    MARK_OTHER,      /* Not a descendant of target */
> -} snapshot_mark;
> -
> -struct snapshot_mark_descendant {
> -    const char *name; /* Parent's name on round 1, NULL on other rounds.  */
> -    virDomainSnapshotObjListPtr snapshots;
> -    bool marked; /* True if descendants were found in this round */
> -};
> -
> -/* To be called in a loop until no more descendants are found.
> - * Additionally marking known unrelated snapshots reduces the number
> - * of total hash searches needed.  */
> -static void
> -virDomainSnapshotMarkDescendant(void *payload,
> -                                const void *name ATTRIBUTE_UNUSED,
> -                                void *data)
> -{
> -    virDomainSnapshotObjPtr obj = payload;
> -    struct snapshot_mark_descendant *curr = data;
> -    virDomainSnapshotObjPtr parent = NULL;
> -
> -    /* Learned on a previous pass.  */
> -    if (obj->mark)
> -        return;
> -
> -    if (curr->name) {
> -        /* First round can only find root nodes and direct children.  */
> -        if (!obj->def->parent) {
> -            obj->mark = MARK_OTHER;
> -        } else if (STREQ(obj->def->parent, curr->name)) {
> -            obj->mark = MARK_DESCENDANT;
> -            curr->marked = true;
> -        }
> -    } else {
> -        /* All remaining rounds propagate marks from parents to children.  */
> -        parent = virDomainSnapshotFindByName(curr->snapshots, obj->def->parent);
> -        if (!parent) {
> -            VIR_WARN("snapshot hash table is inconsistent!");
> -            obj->mark = MARK_OTHER;
> -            return;
> -        }
> -        if (parent->mark) {
> -            obj->mark = parent->mark;
> -            if (obj->mark == MARK_DESCENDANT)
> -                curr->marked = true;
> -        }
> +    while (child) {
> +        (iter)(child, child->def->name, data);
> +        child = child->sibling;
>      }
> +
> +    return snapshot->nchildren;
>  }
> 
>  struct snapshot_act_on_descendant {
> @@ -12378,40 +12329,27 @@ virDomainSnapshotActOnDescendant(void *payload,
>      virDomainSnapshotObjPtr obj = payload;
>      struct snapshot_act_on_descendant *curr = data;
> 
> -    if (obj->mark == MARK_DESCENDANT) {
> -        curr->number++;
> -        (curr->iter)(payload, name, curr->data);
> -    }
> -    obj->mark = MARK_NONE;
> +    curr->number++;
> +    (curr->iter)(payload, name, curr->data);
> +    virDomainSnapshotForEachDescendant(NULL, obj, curr->iter, curr->data);
>  }
> 
>  /* Run iter(data) on all descendants of snapshot, while ignoring all
>   * other entries in snapshots.  Return the number of descendants
>   * visited.  No particular ordering is guaranteed.  */
>  int
> -virDomainSnapshotForEachDescendant(virDomainSnapshotObjListPtr snapshots,
> +virDomainSnapshotForEachDescendant(virDomainSnapshotObjListPtr snapshots ATTRIBUTE_UNUSED,
>                                     virDomainSnapshotObjPtr snapshot,
>                                     virHashIterator iter,
>                                     void *data)
>  {
> -    struct snapshot_mark_descendant mark;
>      struct snapshot_act_on_descendant act;
> 
> -    /* virHashForEach does not support nested traversal, so we must
> -     * instead iterate until no more snapshots get marked.  We
> -     * guarantee that on exit, all marks have been cleared again.  */
> -    mark.name = snapshot->def->name;
> -    mark.snapshots = snapshots;
> -    mark.marked = true;
> -    while (mark.marked) {
> -        mark.marked = false;
> -        virHashForEach(snapshots->objs, virDomainSnapshotMarkDescendant, &mark);
> -        mark.name = NULL;
> -    }
>      act.number = 0;
>      act.iter = iter;
>      act.data = data;
> -    virHashForEach(snapshots->objs, virDomainSnapshotActOnDescendant, &act);
> +    virDomainSnapshotForEachChild(NULL, snapshot,
> +                                  virDomainSnapshotActOnDescendant, &act);
> 
>      return act.number;
>  }

  ACK,

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


[Index of Archives]     [Virt Tools]     [Libvirt Users]     [Lib OS Info]     [Fedora Users]     [Fedora Desktop]     [Fedora SELinux]     [Big List of Linux Books]     [Yosemite News]     [KDE Users]     [Fedora Tools]