[libvirt] [PATCH 0/4] snapshot: optimize qemu relationship traversal
After working with ESX and VBox, I realized that a tweak to how snapshot relationships are stored would speed things up from O(n^2) to O(n). The hash table must be kept for name lookup, but the speedup comes by tracking relationships with each snapshot rather than crawling the entire hash table rebuilding those relations for every operation that needs particular relations. Eric Blake (4): snapshot: framework for more efficient relation traversal snapshot: track qemu snapshot relations snapshot: take advantage of new relations snapshot: drop dead parameters src/conf/domain_conf.c | 266 +++++++++++++++++++++++++--------------------- src/conf/domain_conf.h | 22 ++-- src/libvirt_private.syms | 3 +- src/qemu/qemu_driver.c | 84 +++++++++++---- 4 files changed, 224 insertions(+), 151 deletions(-) -- 1.7.4.4
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. * 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; +}; + +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; -- 1.7.4.4
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@veillard.com | Rpmfind RPM search engine http://rpmfind.net/ http://veillard.com/ | virtualization library http://libvirt.org/
On 10/09/2011 08:37 PM, Daniel Veillard wrote:
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 :-)
See patch 3/4. When no other flags are present, virDomainSnapshotNumChildren only needs to read the nchildren member [and virDomainSnapshotNum with LIST_ROOTS the nroots member] (for O(1) operation), rather than walk the list of first_child/sibling (for O(n) operation). You are correct that virDomainSnapshotListChildrenNames has to walk the list, but since at least one API can benefit from not walking the list, we might as well track both pieces of information.
+ +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)
Indeed, although it is a callback function only used by virDomainSnapshotUpdateRelations. Here's what I'll add: /* Callback when iterating over a hash table of snapshots, where all * snapshots start with no metadata. For each snapshot with a parent, * set the parent metadata field, and update the parent's list of * children. Set the error flag if a parent is not found or would * cause a circular chain. */
Okay, just wondering about the usefulness of nchidren/nroot :-)
Did I manage to explain it?
ACK
I'll wait on your feedback regarding whether I should attempt the meta-root concept now, or just push as-is and save a meta-root concept for later patches. -- Eric Blake eblake@redhat.com +1-801-349-2682 Libvirt virtualization library http://libvirt.org
On Mon, Oct 10, 2011 at 04:09:07PM -0600, Eric Blake wrote:
On 10/09/2011 08:37 PM, Daniel Veillard wrote:
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 :-)
See patch 3/4. When no other flags are present, virDomainSnapshotNumChildren only needs to read the nchildren member [and virDomainSnapshotNum with LIST_ROOTS the nroots member] (for O(1) operation), rather than walk the list of first_child/sibling (for O(n) operation). You are correct that virDomainSnapshotListChildrenNames has to walk the list, but since at least one API can benefit from not walking the list, we might as well track both pieces of information.
Okay, agreed then, I was just wondering if more 'canonical' code and data would lead to simpler code and hence easier to debug in case of trouble, but we are already in the optimization phase, so fine :-)
+ +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)
Indeed, although it is a callback function only used by virDomainSnapshotUpdateRelations. Here's what I'll add:
/* Callback when iterating over a hash table of snapshots, where all * snapshots start with no metadata. For each snapshot with a parent, * set the parent metadata field, and update the parent's list of * children. Set the error flag if a parent is not found or would * cause a circular chain. */
Okay, just wondering about the usefulness of nchidren/nroot :-)
Did I manage to explain it?
yes, certainly :-)
ACK
I'll wait on your feedback regarding whether I should attempt the meta-root concept now, or just push as-is and save a meta-root concept for later patches.
Just push now and let see if the meta root patch actually lead to better code. Daniel -- Daniel Veillard | libxml Gnome XML XSLT toolkit http://xmlsoft.org/ daniel@veillard.com | Rpmfind RPM search engine http://rpmfind.net/ http://veillard.com/ | virtualization library http://libvirt.org/
On 10/10/2011 08:39 PM, Daniel Veillard wrote:
Okay, agreed then, I was just wondering if more 'canonical' code and data would lead to simpler code and hence easier to debug in case of trouble, but we are already in the optimization phase, so fine :-)
ACK
I'll wait on your feedback regarding whether I should attempt the meta-root concept now, or just push as-is and save a meta-root concept for later patches.
Just push now and let see if the meta root patch actually lead to better code.
I've now pushed 1-4, and am working up a meta-root patch to see if it looks worthwhile (I'll post it once I get it tested, whether or not I recommend using or dropping it). -- Eric Blake eblake@redhat.com +1-801-349-2682 Libvirt virtualization library http://libvirt.org
Maintain the parent/child relationships of all qemu snapshots. * src/qemu/qemu_driver.c (qemuDomainSnapshotLoad): Populate relationships after loading. (qemuDomainSnapshotCreateXML): Set relations on creation; tweak redefinition to reuse existing object. (qemuDomainSnapshotReparentChildren, qemuDomainSnapshotDelete): Clear relations on delete. --- src/qemu/qemu_driver.c | 72 ++++++++++++++++++++++++++++++++++++++--------- 1 files changed, 58 insertions(+), 14 deletions(-) diff --git a/src/qemu/qemu_driver.c b/src/qemu/qemu_driver.c index 5db67b8..501a3fc 100644 --- a/src/qemu/qemu_driver.c +++ b/src/qemu/qemu_driver.c @@ -376,6 +376,10 @@ static void qemuDomainSnapshotLoad(void *payload, vm->current_snapshot = NULL; } + if (virDomainSnapshotUpdateRelations(&vm->snapshots) < 0) + VIR_ERROR(_("Snapshots have inconsistent relations for domain %s"), + vm->def->name); + /* FIXME: qemu keeps internal track of snapshots. We can get access * to this info via the "info snapshots" monitor command for running * domains, or via "qemu-img snapshot -l" for shutoff domains. It would @@ -9148,6 +9152,7 @@ qemuDomainSnapshotCreateXML(virDomainPtr domain, virDomainSnapshotDefPtr def = NULL; bool update_current = true; unsigned int parse_flags = 0; + virDomainSnapshotObjPtr other = NULL; virCheckFlags(VIR_DOMAIN_SNAPSHOT_CREATE_REDEFINE | VIR_DOMAIN_SNAPSHOT_CREATE_CURRENT | @@ -9190,8 +9195,6 @@ qemuDomainSnapshotCreateXML(virDomainPtr domain, goto cleanup; if (flags & VIR_DOMAIN_SNAPSHOT_CREATE_REDEFINE) { - virDomainSnapshotObjPtr other = NULL; - /* Prevent circular chains */ if (def->parent) { if (STREQ(def->name, def->parent)) { @@ -9267,7 +9270,12 @@ qemuDomainSnapshotCreateXML(virDomainPtr domain, update_current = true; vm->current_snapshot = NULL; } - virDomainSnapshotObjListRemove(&vm->snapshots, other); + /* Drop and rebuild the parent relationship, but keep all + * child relations by reusing snap. */ + virDomainSnapshotDropParent(&vm->snapshots, other); + virDomainSnapshotDefFree(other->def); + other->def = NULL; + snap = other; } if (def->state == VIR_DOMAIN_DISK_SNAPSHOT && def->dom) { if (virDomainSnapshotAlignDisks(def, @@ -9309,7 +9317,9 @@ qemuDomainSnapshotCreateXML(virDomainPtr domain, } } - if (!(snap = virDomainSnapshotAssignDef(&vm->snapshots, def))) + if (snap) + snap->def = def; + else if (!(snap = virDomainSnapshotAssignDef(&vm->snapshots, def))) goto cleanup; def = NULL; @@ -9366,11 +9376,25 @@ cleanup: if (vm) { if (snapshot && !(flags & VIR_DOMAIN_SNAPSHOT_CREATE_NO_METADATA)) { if (qemuDomainSnapshotWriteMetadata(vm, snap, - driver->snapshotDir) < 0) + driver->snapshotDir) < 0) { VIR_WARN("unable to save metadata for snapshot %s", snap->def->name); - else if (update_current) - vm->current_snapshot = snap; + } else { + if (update_current) + vm->current_snapshot = snap; + if (snap->def->parent) { + other = virDomainSnapshotFindByName(&vm->snapshots, + snap->def->parent); + snap->parent = other; + other->nchildren++; + snap->sibling = other->first_child; + other->first_child = snap; + } else { + vm->snapshots.nroots++; + snap->sibling = vm->snapshots.first_root; + vm->snapshots.first_root = snap; + } + } } else if (snap) { virDomainSnapshotObjListRemove(&vm->snapshots, snap); } @@ -10062,9 +10086,10 @@ cleanup: struct snap_reparent { struct qemud_driver *driver; - const char *parent; + virDomainSnapshotObjPtr parent; virDomainObjPtr vm; int err; + virDomainSnapshotObjPtr last; }; static void @@ -10080,9 +10105,10 @@ qemuDomainSnapshotReparentChildren(void *payload, } VIR_FREE(snap->def->parent); + snap->parent = rep->parent; - if (rep->parent != NULL) { - snap->def->parent = strdup(rep->parent); + if (rep->parent) { + snap->def->parent = strdup(rep->parent->def->name); if (snap->def->parent == NULL) { virReportOOMError(); @@ -10091,6 +10117,9 @@ qemuDomainSnapshotReparentChildren(void *payload, } } + if (!snap->sibling) + rep->last = snap; + rep->err = qemuDomainSnapshotWriteMetadata(rep->vm, snap, rep->driver->snapshotDir); } @@ -10175,22 +10204,37 @@ static int qemuDomainSnapshotDelete(virDomainSnapshotPtr snapshot, } vm->current_snapshot = snap; } - } else { + } else if (snap->nchildren) { rep.driver = driver; - rep.parent = snap->def->parent; + rep.parent = snap->parent; rep.vm = vm; rep.err = 0; + rep.last = NULL; virDomainSnapshotForEachChild(&vm->snapshots, snap, qemuDomainSnapshotReparentChildren, &rep); if (rep.err < 0) goto endjob; + /* Can't modify siblings during ForEachChild, so do it now. */ + if (snap->parent) { + snap->parent->nchildren += snap->nchildren; + rep.last->sibling = snap->parent->first_child; + snap->parent->first_child = snap->first_child; + } else { + vm->snapshots.nroots += snap->nchildren; + rep.last->sibling = vm->snapshots.first_root; + vm->snapshots.first_root = snap->first_child; + } } - if (flags & VIR_DOMAIN_SNAPSHOT_DELETE_CHILDREN_ONLY) + if (flags & VIR_DOMAIN_SNAPSHOT_DELETE_CHILDREN_ONLY) { + snap->nchildren = 0; + snap->first_child = NULL; ret = 0; - else + } else { + virDomainSnapshotDropParent(&vm->snapshots, snap); ret = qemuDomainSnapshotDiscard(driver, vm, snap, true, metadata_only); + } endjob: if (qemuDomainObjEndJob(driver, vm) == 0) -- 1.7.4.4
On Fri, Oct 07, 2011 at 06:05:55PM -0600, Eric Blake wrote:
Maintain the parent/child relationships of all qemu snapshots.
* src/qemu/qemu_driver.c (qemuDomainSnapshotLoad): Populate relationships after loading. (qemuDomainSnapshotCreateXML): Set relations on creation; tweak redefinition to reuse existing object. (qemuDomainSnapshotReparentChildren, qemuDomainSnapshotDelete): Clear relations on delete. --- src/qemu/qemu_driver.c | 72 ++++++++++++++++++++++++++++++++++++++--------- 1 files changed, 58 insertions(+), 14 deletions(-)
diff --git a/src/qemu/qemu_driver.c b/src/qemu/qemu_driver.c index 5db67b8..501a3fc 100644 --- a/src/qemu/qemu_driver.c +++ b/src/qemu/qemu_driver.c @@ -376,6 +376,10 @@ static void qemuDomainSnapshotLoad(void *payload, vm->current_snapshot = NULL; }
+ if (virDomainSnapshotUpdateRelations(&vm->snapshots) < 0) + VIR_ERROR(_("Snapshots have inconsistent relations for domain %s"), + vm->def->name); +
Hum, so we error out but continue with possibly inconsistent metadata, isn't that risky ? What would be the cost or failing the load here and consequences of lack of metadata ?
/* FIXME: qemu keeps internal track of snapshots. We can get access * to this info via the "info snapshots" monitor command for running * domains, or via "qemu-img snapshot -l" for shutoff domains. It would @@ -9148,6 +9152,7 @@ qemuDomainSnapshotCreateXML(virDomainPtr domain, virDomainSnapshotDefPtr def = NULL; bool update_current = true; unsigned int parse_flags = 0; + virDomainSnapshotObjPtr other = NULL;
virCheckFlags(VIR_DOMAIN_SNAPSHOT_CREATE_REDEFINE | VIR_DOMAIN_SNAPSHOT_CREATE_CURRENT | @@ -9190,8 +9195,6 @@ qemuDomainSnapshotCreateXML(virDomainPtr domain, goto cleanup;
if (flags & VIR_DOMAIN_SNAPSHOT_CREATE_REDEFINE) { - virDomainSnapshotObjPtr other = NULL; - /* Prevent circular chains */ if (def->parent) { if (STREQ(def->name, def->parent)) { @@ -9267,7 +9270,12 @@ qemuDomainSnapshotCreateXML(virDomainPtr domain, update_current = true; vm->current_snapshot = NULL; } - virDomainSnapshotObjListRemove(&vm->snapshots, other); + /* Drop and rebuild the parent relationship, but keep all + * child relations by reusing snap. */ + virDomainSnapshotDropParent(&vm->snapshots, other); + virDomainSnapshotDefFree(other->def); + other->def = NULL; + snap = other; } if (def->state == VIR_DOMAIN_DISK_SNAPSHOT && def->dom) { if (virDomainSnapshotAlignDisks(def, @@ -9309,7 +9317,9 @@ qemuDomainSnapshotCreateXML(virDomainPtr domain, } }
- if (!(snap = virDomainSnapshotAssignDef(&vm->snapshots, def))) + if (snap) + snap->def = def; + else if (!(snap = virDomainSnapshotAssignDef(&vm->snapshots, def))) goto cleanup; def = NULL;
@@ -9366,11 +9376,25 @@ cleanup: if (vm) { if (snapshot && !(flags & VIR_DOMAIN_SNAPSHOT_CREATE_NO_METADATA)) { if (qemuDomainSnapshotWriteMetadata(vm, snap, - driver->snapshotDir) < 0) + driver->snapshotDir) < 0) { VIR_WARN("unable to save metadata for snapshot %s", snap->def->name); - else if (update_current) - vm->current_snapshot = snap; + } else { + if (update_current) + vm->current_snapshot = snap; + if (snap->def->parent) { + other = virDomainSnapshotFindByName(&vm->snapshots, + snap->def->parent); + snap->parent = other; + other->nchildren++; + snap->sibling = other->first_child; + other->first_child = snap; + } else { + vm->snapshots.nroots++; + snap->sibling = vm->snapshots.first_root; + vm->snapshots.first_root = snap; + } + } } else if (snap) { virDomainSnapshotObjListRemove(&vm->snapshots, snap); } @@ -10062,9 +10086,10 @@ cleanup:
struct snap_reparent { struct qemud_driver *driver; - const char *parent; + virDomainSnapshotObjPtr parent; virDomainObjPtr vm; int err; + virDomainSnapshotObjPtr last; };
static void @@ -10080,9 +10105,10 @@ qemuDomainSnapshotReparentChildren(void *payload, }
VIR_FREE(snap->def->parent); + snap->parent = rep->parent;
- if (rep->parent != NULL) { - snap->def->parent = strdup(rep->parent); + if (rep->parent) { + snap->def->parent = strdup(rep->parent->def->name);
if (snap->def->parent == NULL) { virReportOOMError(); @@ -10091,6 +10117,9 @@ qemuDomainSnapshotReparentChildren(void *payload, } }
+ if (!snap->sibling) + rep->last = snap; + rep->err = qemuDomainSnapshotWriteMetadata(rep->vm, snap, rep->driver->snapshotDir); } @@ -10175,22 +10204,37 @@ static int qemuDomainSnapshotDelete(virDomainSnapshotPtr snapshot, } vm->current_snapshot = snap; } - } else { + } else if (snap->nchildren) { rep.driver = driver; - rep.parent = snap->def->parent; + rep.parent = snap->parent; rep.vm = vm; rep.err = 0; + rep.last = NULL; virDomainSnapshotForEachChild(&vm->snapshots, snap, qemuDomainSnapshotReparentChildren, &rep); if (rep.err < 0) goto endjob; + /* Can't modify siblings during ForEachChild, so do it now. */ + if (snap->parent) { + snap->parent->nchildren += snap->nchildren; + rep.last->sibling = snap->parent->first_child; + snap->parent->first_child = snap->first_child; + } else { + vm->snapshots.nroots += snap->nchildren; + rep.last->sibling = vm->snapshots.first_root; + vm->snapshots.first_root = snap->first_child; + } }
- if (flags & VIR_DOMAIN_SNAPSHOT_DELETE_CHILDREN_ONLY) + if (flags & VIR_DOMAIN_SNAPSHOT_DELETE_CHILDREN_ONLY) { + snap->nchildren = 0; + snap->first_child = NULL; ret = 0; - else + } else { + virDomainSnapshotDropParent(&vm->snapshots, snap); ret = qemuDomainSnapshotDiscard(driver, vm, snap, true, metadata_only); + }
endjob: if (qemuDomainObjEndJob(driver, vm) == 0)
Okay, the main problem is making sure we keep the metadata on all operations that are needed, Load/Create/Delete and Reparent sounds right, ACK, Daniel -- Daniel Veillard | libxml Gnome XML XSLT toolkit http://xmlsoft.org/ daniel@veillard.com | Rpmfind RPM search engine http://rpmfind.net/ http://veillard.com/ | virtualization library http://libvirt.org/
On 10/09/2011 08:43 PM, Daniel Veillard wrote:
On Fri, Oct 07, 2011 at 06:05:55PM -0600, Eric Blake wrote:
Maintain the parent/child relationships of all qemu snapshots.
* src/qemu/qemu_driver.c (qemuDomainSnapshotLoad): Populate relationships after loading. (qemuDomainSnapshotCreateXML): Set relations on creation; tweak redefinition to reuse existing object. (qemuDomainSnapshotReparentChildren, qemuDomainSnapshotDelete): Clear relations on delete. --- src/qemu/qemu_driver.c | 72 ++++++++++++++++++++++++++++++++++++++--------- 1 files changed, 58 insertions(+), 14 deletions(-)
diff --git a/src/qemu/qemu_driver.c b/src/qemu/qemu_driver.c index 5db67b8..501a3fc 100644 --- a/src/qemu/qemu_driver.c +++ b/src/qemu/qemu_driver.c @@ -376,6 +376,10 @@ static void qemuDomainSnapshotLoad(void *payload, vm->current_snapshot = NULL; }
+ if (virDomainSnapshotUpdateRelations(&vm->snapshots)< 0) + VIR_ERROR(_("Snapshots have inconsistent relations for domain %s"), + vm->def->name); +
Hum, so we error out but continue with possibly inconsistent metadata, isn't that risky ? What would be the cost or failing the load here and consequences of lack of metadata ?
With just patch 2/4, the consequence of ignoring inconsistent metadata is that things fall back to searching the entire hash table, which will repeat the inconsistent checks, but possibly infloop (it's hard to say for sure, because it's quite a bit of code to audit). With patch 3/4 added, ignoring inconsistent metadata will mean that all consistent snapshots will still be visited, while the inconsistent ones can still be looked up by name but cannot be traversed (they act as if they have no parent or children). I did prove to myself that using _only_ libvirt APIs to modify the hierarchy, then the metadata will always be consistent. I think (but did not prove) that the code will not segv, but inconsistent data still has the possibility of triggering an infloop. On the other hand, the only way to get inconsistent metadata is to manually modify files under /etc/libvirt or /var/run/libvirt, which we already discourage, so I'm not too worried - if someone can manage to get libvirtd hung on an infloop by going behind libvirt's back, that's their fault, not libvirt's. But if you are worried, I could go one step further and refuse to load the snapshot hierarchy altogether if inconsistent data was found in any of the snapshot xml files, and make commands like virDomainSnapshotNum return failure when it detected that snapshot metadata could not be loaded.
Okay, the main problem is making sure we keep the metadata on all operations that are needed, Load/Create/Delete and Reparent sounds right,
Yes, I double-checked, and all code that registered or removed a snapshot, or which modified the metadata file of a snapshot, takes care to update the new metadata fields correctly. -- Eric Blake eblake@redhat.com +1-801-349-2682 Libvirt virtualization library http://libvirt.org
On Mon, Oct 10, 2011 at 03:58:27PM -0600, Eric Blake wrote:
On 10/09/2011 08:43 PM, Daniel Veillard wrote:
On Fri, Oct 07, 2011 at 06:05:55PM -0600, Eric Blake wrote:
Maintain the parent/child relationships of all qemu snapshots.
* src/qemu/qemu_driver.c (qemuDomainSnapshotLoad): Populate relationships after loading. (qemuDomainSnapshotCreateXML): Set relations on creation; tweak redefinition to reuse existing object. (qemuDomainSnapshotReparentChildren, qemuDomainSnapshotDelete): Clear relations on delete. --- src/qemu/qemu_driver.c | 72 ++++++++++++++++++++++++++++++++++++++--------- 1 files changed, 58 insertions(+), 14 deletions(-)
diff --git a/src/qemu/qemu_driver.c b/src/qemu/qemu_driver.c index 5db67b8..501a3fc 100644 --- a/src/qemu/qemu_driver.c +++ b/src/qemu/qemu_driver.c @@ -376,6 +376,10 @@ static void qemuDomainSnapshotLoad(void *payload, vm->current_snapshot = NULL; }
+ if (virDomainSnapshotUpdateRelations(&vm->snapshots)< 0) + VIR_ERROR(_("Snapshots have inconsistent relations for domain %s"), + vm->def->name); +
Hum, so we error out but continue with possibly inconsistent metadata, isn't that risky ? What would be the cost or failing the load here and consequences of lack of metadata ?
With just patch 2/4, the consequence of ignoring inconsistent metadata is that things fall back to searching the entire hash table, which will repeat the inconsistent checks, but possibly infloop (it's hard to say for sure, because it's quite a bit of code to audit). With patch 3/4 added, ignoring inconsistent metadata will mean that all consistent snapshots will still be visited, while the inconsistent ones can still be looked up by name but cannot be traversed (they act as if they have no parent or children). I did prove to myself that using _only_ libvirt APIs to modify the hierarchy, then the metadata will always be consistent.
I think (but did not prove) that the code will not segv, but inconsistent data still has the possibility of triggering an infloop. On the other hand, the only way to get inconsistent metadata is to manually modify files under /etc/libvirt or /var/run/libvirt, which we already discourage, so I'm not too worried - if someone can manage to get libvirtd hung on an infloop by going behind libvirt's back, that's their fault, not libvirt's.
yeah, that's what I'm worrying about mostly.
But if you are worried, I could go one step further and refuse to load the snapshot hierarchy altogether if inconsistent data was found in any of the snapshot xml files, and make commands like virDomainSnapshotNum return failure when it detected that snapshot metadata could not be loaded.
Maybe we could 'just' add some test case in TCK or another test suite trying to exhibit behaviour for some simpe case like parent snapshot data gone missing or this kind of things.
Okay, the main problem is making sure we keep the metadata on all operations that are needed, Load/Create/Delete and Reparent sounds right,
Yes, I double-checked, and all code that registered or removed a snapshot, or which modified the metadata file of a snapshot, takes care to update the new metadata fields correctly.
Yes that was my conclusion too after the patch set review, but you have a far better view of the whole thing than me :-) Daniel -- Daniel Veillard | libxml Gnome XML XSLT toolkit http://xmlsoft.org/ daniel@veillard.com | Rpmfind RPM search engine http://rpmfind.net/ http://veillard.com/ | virtualization library http://libvirt.org/
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; + } + } 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; } -- 1.7.4.4
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@veillard.com | Rpmfind RPM search engine http://rpmfind.net/ http://veillard.com/ | virtualization library http://libvirt.org/
On 10/09/2011 09:02 PM, Daniel Veillard wrote:
+ 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.
Possibly. In fact, ESX does just that. Should I respin this patch series to factor that in on first commit, or do it as a followup commit? -- Eric Blake eblake@redhat.com +1-801-349-2682 Libvirt virtualization library http://libvirt.org
On Mon, Oct 10, 2011 at 03:51:36PM -0600, Eric Blake wrote:
On 10/09/2011 09:02 PM, Daniel Veillard wrote:
+ 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.
Possibly. In fact, ESX does just that. Should I respin this patch series to factor that in on first commit, or do it as a followup commit?
IMHO a followup is fine, that should be fairly mechanical and allow us to actually see if this is a better approach or not (counting - vs + lines should make this clear :-) Daniel -- Daniel Veillard | libxml Gnome XML XSLT toolkit http://xmlsoft.org/ daniel@veillard.com | Rpmfind RPM search engine http://rpmfind.net/ http://veillard.com/ | virtualization library http://libvirt.org/
The previous optimizations lead to some follow-on cleanups. * src/conf/domain_conf.c (virDomainSnapshotForEachChild) (virDomainSnapshotForEachDescendant): Drop dead parameter. (virDomainSnapshotActOnDescendant) (virDomainSnapshotObjListNumFrom) (virDomainSnapshotObjListGetNamesFrom): Update callers. * src/qemu/qemu_driver.c (qemuDomainSnapshotNumChildren) (qemuDomainSnapshotListChildrenNames, qemuDomainSnapshotDelete): Likewise. * src/conf/domain_conf.h: Update prototypes. --- src/conf/domain_conf.c | 20 ++++++++------------ src/conf/domain_conf.h | 11 ++--------- src/qemu/qemu_driver.c | 12 +++++------- 3 files changed, 15 insertions(+), 28 deletions(-) diff --git a/src/conf/domain_conf.c b/src/conf/domain_conf.c index e77257a..d52a79f 100644 --- a/src/conf/domain_conf.c +++ b/src/conf/domain_conf.c @@ -12192,7 +12192,6 @@ cleanup: } int virDomainSnapshotObjListGetNamesFrom(virDomainSnapshotObjPtr snapshot, - virDomainSnapshotObjListPtr snapshots, char **const names, int maxnames, unsigned int flags) { @@ -12202,11 +12201,11 @@ int virDomainSnapshotObjListGetNamesFrom(virDomainSnapshotObjPtr snapshot, data.flags = flags & ~VIR_DOMAIN_SNAPSHOT_LIST_DESCENDANTS; if (flags & VIR_DOMAIN_SNAPSHOT_LIST_DESCENDANTS) - virDomainSnapshotForEachDescendant(snapshots, snapshot, + virDomainSnapshotForEachDescendant(snapshot, virDomainSnapshotObjListCopyNames, &data); else - virDomainSnapshotForEachChild(snapshots, snapshot, + virDomainSnapshotForEachChild(snapshot, virDomainSnapshotObjListCopyNames, &data); if (data.oom) { @@ -12263,7 +12262,6 @@ int virDomainSnapshotObjListNum(virDomainSnapshotObjListPtr snapshots, int virDomainSnapshotObjListNumFrom(virDomainSnapshotObjPtr snapshot, - virDomainSnapshotObjListPtr snapshots, unsigned int flags) { struct virDomainSnapshotNumData data = { 0, 0 }; @@ -12271,11 +12269,11 @@ virDomainSnapshotObjListNumFrom(virDomainSnapshotObjPtr snapshot, data.flags = flags & ~VIR_DOMAIN_SNAPSHOT_LIST_DESCENDANTS; if (flags & VIR_DOMAIN_SNAPSHOT_LIST_DESCENDANTS) - virDomainSnapshotForEachDescendant(snapshots, snapshot, + virDomainSnapshotForEachDescendant(snapshot, virDomainSnapshotObjListCount, &data); else if (data.flags) - virDomainSnapshotForEachChild(snapshots, snapshot, + virDomainSnapshotForEachChild(snapshot, virDomainSnapshotObjListCount, &data); else data.count = snapshot->nchildren; @@ -12300,8 +12298,7 @@ void virDomainSnapshotObjListRemove(virDomainSnapshotObjListPtr snapshots, * other entries in snapshots. Return the number of children * visited. No particular ordering is guaranteed. */ int -virDomainSnapshotForEachChild(virDomainSnapshotObjListPtr snapshots ATTRIBUTE_UNUSED, - virDomainSnapshotObjPtr snapshot, +virDomainSnapshotForEachChild(virDomainSnapshotObjPtr snapshot, virHashIterator iter, void *data) { @@ -12331,15 +12328,14 @@ virDomainSnapshotActOnDescendant(void *payload, curr->number++; (curr->iter)(payload, name, curr->data); - virDomainSnapshotForEachDescendant(NULL, obj, curr->iter, curr->data); + virDomainSnapshotForEachDescendant(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 ATTRIBUTE_UNUSED, - virDomainSnapshotObjPtr snapshot, +virDomainSnapshotForEachDescendant(virDomainSnapshotObjPtr snapshot, virHashIterator iter, void *data) { @@ -12348,7 +12344,7 @@ virDomainSnapshotForEachDescendant(virDomainSnapshotObjListPtr snapshots ATTRIBU act.number = 0; act.iter = iter; act.data = data; - virDomainSnapshotForEachChild(NULL, snapshot, + virDomainSnapshotForEachChild(snapshot, virDomainSnapshotActOnDescendant, &act); return act.number; diff --git a/src/conf/domain_conf.h b/src/conf/domain_conf.h index 9b3870a..ce93215 100644 --- a/src/conf/domain_conf.h +++ b/src/conf/domain_conf.h @@ -1464,9 +1464,6 @@ struct _virDomainSnapshotObj { 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. */ }; typedef struct _virDomainSnapshotObjList virDomainSnapshotObjList; @@ -1508,22 +1505,18 @@ int virDomainSnapshotObjListGetNames(virDomainSnapshotObjListPtr snapshots, int virDomainSnapshotObjListNum(virDomainSnapshotObjListPtr snapshots, unsigned int flags); int virDomainSnapshotObjListGetNamesFrom(virDomainSnapshotObjPtr snapshot, - virDomainSnapshotObjListPtr snapshots, char **const names, int maxnames, unsigned int flags); int virDomainSnapshotObjListNumFrom(virDomainSnapshotObjPtr snapshot, - virDomainSnapshotObjListPtr snapshots, unsigned int flags); virDomainSnapshotObjPtr virDomainSnapshotFindByName(const virDomainSnapshotObjListPtr snapshots, const char *name); void virDomainSnapshotObjListRemove(virDomainSnapshotObjListPtr snapshots, virDomainSnapshotObjPtr snapshot); -int virDomainSnapshotForEachChild(virDomainSnapshotObjListPtr snapshots, - virDomainSnapshotObjPtr snapshot, +int virDomainSnapshotForEachChild(virDomainSnapshotObjPtr snapshot, virHashIterator iter, void *data); -int virDomainSnapshotForEachDescendant(virDomainSnapshotObjListPtr snapshots, - virDomainSnapshotObjPtr snapshot, +int virDomainSnapshotForEachDescendant(virDomainSnapshotObjPtr snapshot, virHashIterator iter, void *data); int virDomainSnapshotUpdateRelations(virDomainSnapshotObjListPtr snapshots); diff --git a/src/qemu/qemu_driver.c b/src/qemu/qemu_driver.c index 501a3fc..7a134e3 100644 --- a/src/qemu/qemu_driver.c +++ b/src/qemu/qemu_driver.c @@ -9502,8 +9502,7 @@ qemuDomainSnapshotListChildrenNames(virDomainSnapshotPtr snapshot, goto cleanup; } - n = virDomainSnapshotObjListGetNamesFrom(snap, &vm->snapshots, - names, nameslen, flags); + n = virDomainSnapshotObjListGetNamesFrom(snap, names, nameslen, flags); cleanup: if (vm) @@ -9546,7 +9545,7 @@ qemuDomainSnapshotNumChildren(virDomainSnapshotPtr snapshot, * VIR_DOMAIN_SNAPSHOT_LIST_METADATA makes no difference to our * answer. */ - n = virDomainSnapshotObjListNumFrom(snap, &vm->snapshots, flags); + n = virDomainSnapshotObjListNumFrom(snap, flags); cleanup: if (vm) @@ -10163,7 +10162,7 @@ static int qemuDomainSnapshotDelete(virDomainSnapshotPtr snapshot, snap->def->state == VIR_DOMAIN_DISK_SNAPSHOT) external++; if (flags & VIR_DOMAIN_SNAPSHOT_DELETE_CHILDREN) - virDomainSnapshotForEachDescendant(&vm->snapshots, snap, + virDomainSnapshotForEachDescendant(snap, qemuDomainSnapshotCountExternal, &external); if (external) { @@ -10184,8 +10183,7 @@ static int qemuDomainSnapshotDelete(virDomainSnapshotPtr snapshot, rem.metadata_only = metadata_only; rem.err = 0; rem.current = false; - virDomainSnapshotForEachDescendant(&vm->snapshots, - snap, + virDomainSnapshotForEachDescendant(snap, qemuDomainSnapshotDiscardAll, &rem); if (rem.err < 0) @@ -10210,7 +10208,7 @@ static int qemuDomainSnapshotDelete(virDomainSnapshotPtr snapshot, rep.vm = vm; rep.err = 0; rep.last = NULL; - virDomainSnapshotForEachChild(&vm->snapshots, snap, + virDomainSnapshotForEachChild(snap, qemuDomainSnapshotReparentChildren, &rep); if (rep.err < 0) -- 1.7.4.4
On Fri, Oct 07, 2011 at 06:05:57PM -0600, Eric Blake wrote:
The previous optimizations lead to some follow-on cleanups.
* src/conf/domain_conf.c (virDomainSnapshotForEachChild) (virDomainSnapshotForEachDescendant): Drop dead parameter. (virDomainSnapshotActOnDescendant) (virDomainSnapshotObjListNumFrom) (virDomainSnapshotObjListGetNamesFrom): Update callers. * src/qemu/qemu_driver.c (qemuDomainSnapshotNumChildren) (qemuDomainSnapshotListChildrenNames, qemuDomainSnapshotDelete): Likewise. * src/conf/domain_conf.h: Update prototypes. --- src/conf/domain_conf.c | 20 ++++++++------------ src/conf/domain_conf.h | 11 ++--------- src/qemu/qemu_driver.c | 12 +++++------- 3 files changed, 15 insertions(+), 28 deletions(-)
diff --git a/src/conf/domain_conf.c b/src/conf/domain_conf.c index e77257a..d52a79f 100644 --- a/src/conf/domain_conf.c +++ b/src/conf/domain_conf.c @@ -12192,7 +12192,6 @@ cleanup: }
int virDomainSnapshotObjListGetNamesFrom(virDomainSnapshotObjPtr snapshot, - virDomainSnapshotObjListPtr snapshots, char **const names, int maxnames, unsigned int flags) { @@ -12202,11 +12201,11 @@ int virDomainSnapshotObjListGetNamesFrom(virDomainSnapshotObjPtr snapshot, data.flags = flags & ~VIR_DOMAIN_SNAPSHOT_LIST_DESCENDANTS;
if (flags & VIR_DOMAIN_SNAPSHOT_LIST_DESCENDANTS) - virDomainSnapshotForEachDescendant(snapshots, snapshot, + virDomainSnapshotForEachDescendant(snapshot, virDomainSnapshotObjListCopyNames, &data); else - virDomainSnapshotForEachChild(snapshots, snapshot, + virDomainSnapshotForEachChild(snapshot, virDomainSnapshotObjListCopyNames, &data);
if (data.oom) { @@ -12263,7 +12262,6 @@ int virDomainSnapshotObjListNum(virDomainSnapshotObjListPtr snapshots,
int virDomainSnapshotObjListNumFrom(virDomainSnapshotObjPtr snapshot, - virDomainSnapshotObjListPtr snapshots, unsigned int flags) { struct virDomainSnapshotNumData data = { 0, 0 }; @@ -12271,11 +12269,11 @@ virDomainSnapshotObjListNumFrom(virDomainSnapshotObjPtr snapshot, data.flags = flags & ~VIR_DOMAIN_SNAPSHOT_LIST_DESCENDANTS;
if (flags & VIR_DOMAIN_SNAPSHOT_LIST_DESCENDANTS) - virDomainSnapshotForEachDescendant(snapshots, snapshot, + virDomainSnapshotForEachDescendant(snapshot, virDomainSnapshotObjListCount, &data); else if (data.flags) - virDomainSnapshotForEachChild(snapshots, snapshot, + virDomainSnapshotForEachChild(snapshot, virDomainSnapshotObjListCount, &data); else data.count = snapshot->nchildren; @@ -12300,8 +12298,7 @@ void virDomainSnapshotObjListRemove(virDomainSnapshotObjListPtr snapshots, * other entries in snapshots. Return the number of children * visited. No particular ordering is guaranteed. */ int -virDomainSnapshotForEachChild(virDomainSnapshotObjListPtr snapshots ATTRIBUTE_UNUSED, - virDomainSnapshotObjPtr snapshot, +virDomainSnapshotForEachChild(virDomainSnapshotObjPtr snapshot, virHashIterator iter, void *data) { @@ -12331,15 +12328,14 @@ virDomainSnapshotActOnDescendant(void *payload,
curr->number++; (curr->iter)(payload, name, curr->data); - virDomainSnapshotForEachDescendant(NULL, obj, curr->iter, curr->data); + virDomainSnapshotForEachDescendant(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 ATTRIBUTE_UNUSED, - virDomainSnapshotObjPtr snapshot, +virDomainSnapshotForEachDescendant(virDomainSnapshotObjPtr snapshot, virHashIterator iter, void *data) { @@ -12348,7 +12344,7 @@ virDomainSnapshotForEachDescendant(virDomainSnapshotObjListPtr snapshots ATTRIBU act.number = 0; act.iter = iter; act.data = data; - virDomainSnapshotForEachChild(NULL, snapshot, + virDomainSnapshotForEachChild(snapshot, virDomainSnapshotActOnDescendant, &act);
return act.number; diff --git a/src/conf/domain_conf.h b/src/conf/domain_conf.h index 9b3870a..ce93215 100644 --- a/src/conf/domain_conf.h +++ b/src/conf/domain_conf.h @@ -1464,9 +1464,6 @@ struct _virDomainSnapshotObj { 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. */ };
typedef struct _virDomainSnapshotObjList virDomainSnapshotObjList; @@ -1508,22 +1505,18 @@ int virDomainSnapshotObjListGetNames(virDomainSnapshotObjListPtr snapshots, int virDomainSnapshotObjListNum(virDomainSnapshotObjListPtr snapshots, unsigned int flags); int virDomainSnapshotObjListGetNamesFrom(virDomainSnapshotObjPtr snapshot, - virDomainSnapshotObjListPtr snapshots, char **const names, int maxnames, unsigned int flags); int virDomainSnapshotObjListNumFrom(virDomainSnapshotObjPtr snapshot, - virDomainSnapshotObjListPtr snapshots, unsigned int flags); virDomainSnapshotObjPtr virDomainSnapshotFindByName(const virDomainSnapshotObjListPtr snapshots, const char *name); void virDomainSnapshotObjListRemove(virDomainSnapshotObjListPtr snapshots, virDomainSnapshotObjPtr snapshot); -int virDomainSnapshotForEachChild(virDomainSnapshotObjListPtr snapshots, - virDomainSnapshotObjPtr snapshot, +int virDomainSnapshotForEachChild(virDomainSnapshotObjPtr snapshot, virHashIterator iter, void *data); -int virDomainSnapshotForEachDescendant(virDomainSnapshotObjListPtr snapshots, - virDomainSnapshotObjPtr snapshot, +int virDomainSnapshotForEachDescendant(virDomainSnapshotObjPtr snapshot, virHashIterator iter, void *data); int virDomainSnapshotUpdateRelations(virDomainSnapshotObjListPtr snapshots); diff --git a/src/qemu/qemu_driver.c b/src/qemu/qemu_driver.c index 501a3fc..7a134e3 100644 --- a/src/qemu/qemu_driver.c +++ b/src/qemu/qemu_driver.c @@ -9502,8 +9502,7 @@ qemuDomainSnapshotListChildrenNames(virDomainSnapshotPtr snapshot, goto cleanup; }
- n = virDomainSnapshotObjListGetNamesFrom(snap, &vm->snapshots, - names, nameslen, flags); + n = virDomainSnapshotObjListGetNamesFrom(snap, names, nameslen, flags);
cleanup: if (vm) @@ -9546,7 +9545,7 @@ qemuDomainSnapshotNumChildren(virDomainSnapshotPtr snapshot, * VIR_DOMAIN_SNAPSHOT_LIST_METADATA makes no difference to our * answer. */
- n = virDomainSnapshotObjListNumFrom(snap, &vm->snapshots, flags); + n = virDomainSnapshotObjListNumFrom(snap, flags);
cleanup: if (vm) @@ -10163,7 +10162,7 @@ static int qemuDomainSnapshotDelete(virDomainSnapshotPtr snapshot, snap->def->state == VIR_DOMAIN_DISK_SNAPSHOT) external++; if (flags & VIR_DOMAIN_SNAPSHOT_DELETE_CHILDREN) - virDomainSnapshotForEachDescendant(&vm->snapshots, snap, + virDomainSnapshotForEachDescendant(snap, qemuDomainSnapshotCountExternal, &external); if (external) { @@ -10184,8 +10183,7 @@ static int qemuDomainSnapshotDelete(virDomainSnapshotPtr snapshot, rem.metadata_only = metadata_only; rem.err = 0; rem.current = false; - virDomainSnapshotForEachDescendant(&vm->snapshots, - snap, + virDomainSnapshotForEachDescendant(snap, qemuDomainSnapshotDiscardAll, &rem); if (rem.err < 0) @@ -10210,7 +10208,7 @@ static int qemuDomainSnapshotDelete(virDomainSnapshotPtr snapshot, rep.vm = vm; rep.err = 0; rep.last = NULL; - virDomainSnapshotForEachChild(&vm->snapshots, snap, + virDomainSnapshotForEachChild(snap, qemuDomainSnapshotReparentChildren, &rep); if (rep.err < 0)
ACK, Daniel -- Daniel Veillard | libxml Gnome XML XSLT toolkit http://xmlsoft.org/ daniel@veillard.com | Rpmfind RPM search engine http://rpmfind.net/ http://veillard.com/ | virtualization library http://libvirt.org/
On 10/07/2011 06:05 PM, Eric Blake wrote:
After working with ESX and VBox, I realized that a tweak to how snapshot relationships are stored would speed things up from O(n^2) to O(n). The hash table must be kept for name lookup, but the speedup comes by tracking relationships with each snapshot rather than crawling the entire hash table rebuilding those relations for every operation that needs particular relations.
This series requires a prereq review of: https://www.redhat.com/archives/libvir-list/2011-September/msg01326.html -- Eric Blake eblake@redhat.com +1-801-349-2682 Libvirt virtualization library http://libvirt.org
On Fri, Oct 07, 2011 at 06:05:53PM -0600, Eric Blake wrote:
After working with ESX and VBox, I realized that a tweak to how snapshot relationships are stored would speed things up from O(n^2) to O(n). The hash table must be kept for name lookup, but the
So we went from 0(n^3) to O(n), sounds good :-)
speedup comes by tracking relationships with each snapshot rather than crawling the entire hash table rebuilding those relations for every operation that needs particular relations.
As long as we are sure there is no risk of stale relationship metadata, this sounds proper ... Daniel -- Daniel Veillard | libxml Gnome XML XSLT toolkit http://xmlsoft.org/ daniel@veillard.com | Rpmfind RPM search engine http://rpmfind.net/ http://veillard.com/ | virtualization library http://libvirt.org/
participants (2)
-
Daniel Veillard -
Eric Blake