7:05 p.m.
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
7:05 p.m.
New subject: [libvirt] [PATCH 1/4] snapshot: framework for more efficient relation traversal
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
9:37 p.m.
New subject: [libvirt] [PATCH 1/4] snapshot: framework for more efficient relation traversal
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(a)veillard.com | Rpmfind RPM search engine http://rpmfind.net/
http://veillard.com/ | virtualization library http://libvirt.org/
5:09 p.m.
New subject: [libvirt] [PATCH 1/4] snapshot: framework for more efficient relation traversal
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(a)redhat.com +1-801-349-2682
Libvirt virtualization library http://libvirt.org
9:39 p.m.
New subject: [libvirt] [PATCH 1/4] snapshot: framework for more efficient relation traversal
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(a)veillard.com | Rpmfind RPM search engine http://rpmfind.net/
http://veillard.com/ | virtualization library http://libvirt.org/
6:45 p.m.
New subject: [libvirt] [PATCH 1/4] snapshot: framework for more efficient relation traversal
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(a)redhat.com +1-801-349-2682
Libvirt virtualization library http://libvirt.org
7:05 p.m.
New subject: [libvirt] [PATCH 2/4] snapshot: track qemu snapshot relations
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
9:43 p.m.
New subject: [libvirt] [PATCH 2/4] snapshot: track qemu snapshot relations
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(a)veillard.com | Rpmfind RPM search engine http://rpmfind.net/
http://veillard.com/ | virtualization library http://libvirt.org/
4:58 p.m.
New subject: [libvirt] [PATCH 2/4] snapshot: track qemu snapshot relations
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(a)redhat.com +1-801-349-2682
Libvirt virtualization library http://libvirt.org
9:37 p.m.
New subject: [libvirt] [PATCH 2/4] snapshot: track qemu snapshot relations
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(a)veillard.com | Rpmfind RPM search engine http://rpmfind.net/
http://veillard.com/ | virtualization library http://libvirt.org/
7:05 p.m.
New subject: [libvirt] [PATCH 3/4] snapshot: take advantage of new relations
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
10:02 p.m.
New subject: [libvirt] [PATCH 3/4] snapshot: take advantage of new relations
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(a)veillard.com | Rpmfind RPM search engine http://rpmfind.net/
http://veillard.com/ | virtualization library http://libvirt.org/
4:51 p.m.
New subject: [libvirt] [PATCH 3/4] snapshot: take advantage of new relations
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(a)redhat.com +1-801-349-2682
Libvirt virtualization library http://libvirt.org
9:34 p.m.
New subject: [libvirt] [PATCH 3/4] snapshot: take advantage of new relations
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(a)veillard.com | Rpmfind RPM search engine http://rpmfind.net/
http://veillard.com/ | virtualization library http://libvirt.org/
7:05 p.m.
New subject: [libvirt] [PATCH 4/4] snapshot: drop dead parameters
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
10:03 p.m.
New subject: [libvirt] [PATCH 4/4] snapshot: drop dead parameters
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(a)veillard.com | Rpmfind RPM search engine http://rpmfind.net/
http://veillard.com/ | virtualization library http://libvirt.org/
7:13 p.m.
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(a)redhat.com +1-801-349-2682
Libvirt virtualization library http://libvirt.org
9:26 p.m.
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(a)veillard.com | Rpmfind RPM search engine http://rpmfind.net/
http://veillard.com/ | virtualization library http://libvirt.org/
4821
days inactive
4824
days old
17 comments
2 participants
participants (2)
-
Daniel Veillard -
Eric Blake