On Fri, Oct 07, 2011 at 06:05:54PM -0600, Eric Blake wrote:
> No one was using virDomainSnapshotHasChildren, but that was an
> O(n) function. Exposing and tracking a bit more metadata for each
> snapshot will allow the same query to be made with an O(1) query
> of the member field. For single snapshot operations (create,
> delete), callers can be trusted to maintain the metadata themselves,
> but for reloading, we can't compute parents as we go since there
> is no guarantee which order things are visited in, so we also
> provide a function to refresh the relationships, and which can
> be used to detect if the user has ignored our warnings and been
> directly modifying files in /var/lib/libvirt/qemu/snapshot. This
> patch only adds metadata; later patches will actually use it.
>
> This layout intentionally hardcodes the size of each snapshot,
> by tracking sibling pointers, rather than having to deal with
> the headache of yet more memory management by directly sticking
> a child[] on each parent.
Okay, so you're using a 'first child'. But why try to maintain
'nchildren' since you can't get the list in 0(1) anyway and
need to walk the sibling. It's just redundant data to me, but maybe
I didn't understood the use :-)
> * src/conf/domain_conf.h (_virDomainSnapshotObj)
> (_virDomainSnapshotObjList): Add members.
> (virDomainSnapshotUpdateRelations, virDomainSnapshotDropParent):
> New prototypes.
> (virDomainSnapshotHasChildren): Delete.
> * src/conf/domain_conf.c (virDomainSnapshotSetRelations)
> (virDomainSnapshotUpdateRelations, virDomainSnapshotDropParent):
> New functions.
> (virDomainSnapshotHasChildren): Drop unused function.
> * src/libvirt_private.syms (domain_conf): Update exports.
> ---
> src/conf/domain_conf.c | 108 +++++++++++++++++++++++++++++++++++++++++++---
> src/conf/domain_conf.h | 13 +++++-
> src/libvirt_private.syms | 3 +-
> 3 files changed, 114 insertions(+), 10 deletions(-)
>
> diff --git a/src/conf/domain_conf.c b/src/conf/domain_conf.c
> index b9ddf26..d4e127d 100644
> --- a/src/conf/domain_conf.c
> +++ b/src/conf/domain_conf.c
> @@ -12312,13 +12312,6 @@ virDomainSnapshotForEachChild(virDomainSnapshotObjListPtr snapshots,
>
> return act.number;
> }
> -
> -int virDomainSnapshotHasChildren(virDomainSnapshotObjPtr snap,
> - virDomainSnapshotObjListPtr snapshots)
> -{
> - return virDomainSnapshotForEachChild(snapshots, snap, NULL, NULL);
> -}
> -
> typedef enum {
> MARK_NONE, /* No relation determined yet */
> MARK_DESCENDANT, /* Descendant of target */
> @@ -12423,6 +12416,107 @@ virDomainSnapshotForEachDescendant(virDomainSnapshotObjListPtr snapshots,
> return act.number;
> }
>
> +
> +struct snapshot_set_relation {
> + virDomainSnapshotObjListPtr snapshots;
> + int err;
> +};
> +
The following function isn't trivial, worth adding a comment about
expected use.
> +static void
> +virDomainSnapshotSetRelations(void *payload,
> + const void *name ATTRIBUTE_UNUSED,
> + void *data)
> +{
> + virDomainSnapshotObjPtr obj = payload;
> + struct snapshot_set_relation *curr = data;
> + virDomainSnapshotObjPtr tmp;
> +
> + if (obj->def->parent) {
> + obj->parent = virDomainSnapshotFindByName(curr->snapshots,
> + obj->def->parent);
> + if (!obj->parent) {
> + curr->err = -1;
> + VIR_WARN("snapshot %s lacks parent", obj->def->name);
> + } else {
> + tmp = obj->parent;
> + while (tmp) {
> + if (tmp == obj) {
> + curr->err = -1;
> + obj->parent = NULL;
> + VIR_WARN("snapshot %s in circular chain", obj->def->name);
> + break;
> + }
> + tmp = tmp->parent;
> + }
> + if (!tmp) {
> + obj->parent->nchildren++;
> + obj->sibling = obj->parent->first_child;
> + obj->parent->first_child = obj;
> + }
> + }
> + } else {
> + curr->snapshots->nroots++;
> + obj->sibling = curr->snapshots->first_root;
> + curr->snapshots->first_root = obj;
> + }
> +}
> +
> +/* Populate parent link and child count of all snapshots, with all
> + * relations starting as 0/NULL. Return 0 on success, -1 if a parent
> + * is missing or if a circular relationship was requested. */
> +int
> +virDomainSnapshotUpdateRelations(virDomainSnapshotObjListPtr snapshots)
> +{
> + struct snapshot_set_relation act = { snapshots, 0 };
> +
> + virHashForEach(snapshots->objs, virDomainSnapshotSetRelations, &act);
> + return act.err;
> +}
> +
> +/* Prepare to reparent or delete snapshot, by removing it from its
> + * current listed parent. Note that when bulk removing all children
> + * of a parent, it is faster to just 0 the count rather than calling
> + * this function on each child. */
> +void
> +virDomainSnapshotDropParent(virDomainSnapshotObjListPtr snapshots,
> + virDomainSnapshotObjPtr snapshot)
> +{
> + virDomainSnapshotObjPtr prev = NULL;
> + virDomainSnapshotObjPtr curr = NULL;
> + size_t *count;
> + virDomainSnapshotObjPtr *first;
> +
> + if (snapshot->parent) {
> + count = &snapshot->parent->nchildren;
> + first = &snapshot->parent->first_child;
> + } else {
> + count = &snapshots->nroots;
> + first = &snapshots->first_root;
> + }
> +
> + if (!*count || !*first) {
> + VIR_WARN("inconsistent snapshot relations");
> + return;
> + }
> + (*count)--;
> + curr = *first;
> + while (curr != snapshot) {
> + if (!curr) {
> + VIR_WARN("inconsistent snapshot relations");
> + return;
> + }
> + prev = curr;
> + curr = curr->sibling;
> + }
> + if (prev)
> + prev->sibling = snapshot->sibling;
> + else
> + *first = snapshot->sibling;
> + snapshot->parent = NULL;
> + snapshot->sibling = NULL;
> +}
> +
> +
> int virDomainChrDefForeach(virDomainDefPtr def,
> bool abortOnError,
> virDomainChrDefIterator iter,
> diff --git a/src/conf/domain_conf.h b/src/conf/domain_conf.h
> index 8765f32..9b3870a 100644
> --- a/src/conf/domain_conf.h
> +++ b/src/conf/domain_conf.h
> @@ -1460,6 +1460,11 @@ typedef virDomainSnapshotObj *virDomainSnapshotObjPtr;
> struct _virDomainSnapshotObj {
> virDomainSnapshotDefPtr def;
>
> + virDomainSnapshotObjPtr parent; /* NULL if root */
> + virDomainSnapshotObjPtr sibling; /* NULL if last child of parent */
> + size_t nchildren;
> + virDomainSnapshotObjPtr first_child; /* NULL if no children */
> +
> /* Internal use only */
> int mark; /* Used in identifying descendents. */
> };
> @@ -1470,6 +1475,9 @@ struct _virDomainSnapshotObjList {
> /* name string -> virDomainSnapshotObj mapping
> * for O(1), lockless lookup-by-name */
> virHashTable *objs;
> +
> + size_t nroots;
> + virDomainSnapshotObjPtr first_root;
> };
>
> typedef enum {
> @@ -1510,8 +1518,6 @@ virDomainSnapshotObjPtr virDomainSnapshotFindByName(const virDomainSnapshotObjLi
> const char *name);
> void virDomainSnapshotObjListRemove(virDomainSnapshotObjListPtr snapshots,
> virDomainSnapshotObjPtr snapshot);
> -int virDomainSnapshotHasChildren(virDomainSnapshotObjPtr snap,
> - virDomainSnapshotObjListPtr snapshots);
> int virDomainSnapshotForEachChild(virDomainSnapshotObjListPtr snapshots,
> virDomainSnapshotObjPtr snapshot,
> virHashIterator iter,
> @@ -1520,6 +1526,9 @@ int virDomainSnapshotForEachDescendant(virDomainSnapshotObjListPtr snapshots,
> virDomainSnapshotObjPtr snapshot,
> virHashIterator iter,
> void *data);
> +int virDomainSnapshotUpdateRelations(virDomainSnapshotObjListPtr snapshots);
> +void virDomainSnapshotDropParent(virDomainSnapshotObjListPtr snapshots,
> + virDomainSnapshotObjPtr snapshot);
>
> /* Guest VM runtime state */
> typedef struct _virDomainStateReason virDomainStateReason;
> diff --git a/src/libvirt_private.syms b/src/libvirt_private.syms
> index a17623a..49888c6 100644
> --- a/src/libvirt_private.syms
> +++ b/src/libvirt_private.syms
> @@ -410,10 +410,10 @@ virDomainSnapshotAssignDef;
> virDomainSnapshotDefFormat;
> virDomainSnapshotDefFree;
> virDomainSnapshotDefParseString;
> +virDomainSnapshotDropParent;
> virDomainSnapshotFindByName;
> virDomainSnapshotForEachChild;
> virDomainSnapshotForEachDescendant;
> -virDomainSnapshotHasChildren;
> virDomainSnapshotObjListGetNames;
> virDomainSnapshotObjListGetNamesFrom;
> virDomainSnapshotObjListNum;
> @@ -421,6 +421,7 @@ virDomainSnapshotObjListNumFrom;
> virDomainSnapshotObjListRemove;
> virDomainSnapshotStateTypeFromString;
> virDomainSnapshotStateTypeToString;
> +virDomainSnapshotUpdateRelations;
> virDomainSoundDefFree;
> virDomainSoundModelTypeFromString;
> virDomainSoundModelTypeToString;
Okay, just wondering about the usefulness of nchidren/nroot :-)
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