/*
 * snapshot_conf.c: domain snapshot XML processing
 *
 * Copyright (C) 2006-2012 Red Hat, Inc.
 * Copyright (C) 2006-2008 Daniel P. Berrange
 *
 * This library is free software; you can redistribute it and/or
 * modify it under the terms of the GNU Lesser General Public
 * License as published by the Free Software Foundation; either
 * version 2.1 of the License, or (at your option) any later version.
 *
 * This library is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
 * Lesser General Public License for more details.
 *
 * You should have received a copy of the GNU Lesser General Public
 * License along with this library.  If not, see
 * <http://www.gnu.org/licenses/>.
 *
 * Author: Eric Blake <eblake@redhat.com>
 */

#include <config.h>

#include <fcntl.h>
#include <sys/stat.h>
#include <sys/time.h>
#include <unistd.h>

#include "internal.h"
#include "bitmap.h"
#include "buf.h"
#include "count-one-bits.h"
#include "datatypes.h"
#include "domain_conf.h"
#include "logging.h"
#include "memory.h"
#include "netdev_bandwidth_conf.h"
#include "netdev_vport_profile_conf.h"
#include "nwfilter_conf.h"
#include "secret_conf.h"
#include "snapshot_conf.h"
#include "storage_file.h"
#include "util.h"
#include "uuid.h"
#include "virfile.h"
#include "virterror_internal.h"
#include "xml.h"

#define VIR_FROM_THIS VIR_FROM_DOMAIN_SNAPSHOT

VIR_ENUM_IMPL(virDomainSnapshotLocation, VIR_DOMAIN_SNAPSHOT_LOCATION_LAST,
              "default",
              "no",
              "internal",
              "external")

/* virDomainSnapshotState is really virDomainState plus one extra state */
VIR_ENUM_IMPL(virDomainSnapshotState, VIR_DOMAIN_SNAPSHOT_STATE_LAST,
              "nostate",
              "running",
              "blocked",
              "paused",
              "shutdown",
              "shutoff",
              "crashed",
              "pmsuspended",
              "disk-snapshot")

struct _virDomainSnapshotObjList {
    /* name string -> virDomainSnapshotObj  mapping
     * for O(1), lockless lookup-by-name */
    virHashTable *objs;

    virDomainSnapshotObj metaroot; /* Special parent of all root snapshots */
};

/* Snapshot Def functions */
static void
virDomainSnapshotDiskDefClear(virDomainSnapshotDiskDefPtr disk)
{
    VIR_FREE(disk->name);
    VIR_FREE(disk->file);
}

void virDomainSnapshotDefFree(virDomainSnapshotDefPtr def)
{
    int i;

    if (!def)
        return;

    VIR_FREE(def->name);
    VIR_FREE(def->description);
    VIR_FREE(def->parent);
    VIR_FREE(def->file);
    for (i = 0; i < def->ndisks; i++)
        virDomainSnapshotDiskDefClear(&def->disks[i]);
    VIR_FREE(def->disks);
    virDomainDefFree(def->dom);
    VIR_FREE(def);
}

static int
virDomainSnapshotDiskDefParseXML(xmlNodePtr node,
                                 virDomainSnapshotDiskDefPtr def)
{
    int ret = -1;
    char *snapshot = NULL;
    xmlNodePtr cur;

    def->name = virXMLPropString(node, "name");
    if (!def->name) {
        virReportError(VIR_ERR_INTERNAL_ERROR, "%s",
                       _("missing name from disk snapshot element"));
        goto cleanup;
    }

    snapshot = virXMLPropString(node, "snapshot");
    if (snapshot) {
        def->snapshot = virDomainSnapshotLocationTypeFromString(snapshot);
        if (def->snapshot <= 0) {
            virReportError(VIR_ERR_INTERNAL_ERROR,
                           _("unknown disk snapshot setting '%s'"),
                           snapshot);
            goto cleanup;
        }
    }

    cur = node->children;
    while (cur) {
        if (cur->type == XML_ELEMENT_NODE) {
            if (!def->file &&
                xmlStrEqual(cur->name, BAD_CAST "source")) {
                def->file = virXMLPropString(cur, "file");
            } else if (!def->format &&
                       xmlStrEqual(cur->name, BAD_CAST "driver")) {
                char *driver = virXMLPropString(cur, "type");
                def->format = virStorageFileFormatTypeFromString(driver);
                if (def->format <= 0) {
                    virReportError(VIR_ERR_INTERNAL_ERROR,
                                   _("unknown disk snapshot driver '%s'"),
                                   driver);
                    VIR_FREE(driver);
                    goto cleanup;
                }
                VIR_FREE(driver);
            }
        }
        cur = cur->next;
    }

    if (!def->snapshot && (def->file || def->format))
        def->snapshot = VIR_DOMAIN_SNAPSHOT_LOCATION_EXTERNAL;

    ret = 0;
cleanup:
    VIR_FREE(snapshot);
    if (ret < 0)
        virDomainSnapshotDiskDefClear(def);
    return ret;
}

/* flags is bitwise-or of virDomainSnapshotParseFlags.
 * If flags does not include VIR_DOMAIN_SNAPSHOT_PARSE_REDEFINE, then
 * caps and expectedVirtTypes are ignored.
 */
virDomainSnapshotDefPtr
virDomainSnapshotDefParseString(const char *xmlStr,
                                virCapsPtr caps,
                                unsigned int expectedVirtTypes,
                                unsigned int flags)
{
    xmlXPathContextPtr ctxt = NULL;
    xmlDocPtr xml = NULL;
    virDomainSnapshotDefPtr def = NULL;
    virDomainSnapshotDefPtr ret = NULL;
    xmlNodePtr *nodes = NULL;
    int i;
    char *creation = NULL, *state = NULL;
    struct timeval tv;
    int active;
    char *tmp;
    int keepBlanksDefault = xmlKeepBlanksDefault(0);
    char *memorySnapshot = NULL;
    char *memoryFile = NULL;
    bool offline = !!(flags & VIR_DOMAIN_SNAPSHOT_PARSE_OFFLINE);

    xml = virXMLParseCtxt(NULL, xmlStr, _("(domain_snapshot)"), &ctxt);
    if (!xml) {
        xmlKeepBlanksDefault(keepBlanksDefault);
        return NULL;
    }
    xmlKeepBlanksDefault(keepBlanksDefault);

    if (VIR_ALLOC(def) < 0) {
        virReportOOMError();
        goto cleanup;
    }

    if (!xmlStrEqual(ctxt->node->name, BAD_CAST "domainsnapshot")) {
        virReportError(VIR_ERR_XML_ERROR, "%s", _("domainsnapshot"));
        goto cleanup;
    }

    gettimeofday(&tv, NULL);

    def->name = virXPathString("string(./name)", ctxt);
    if (def->name == NULL) {
        if (flags & VIR_DOMAIN_SNAPSHOT_PARSE_REDEFINE) {
            virReportError(VIR_ERR_XML_ERROR, "%s",
                           _("a redefined snapshot must have a name"));
            goto cleanup;
        }
        if (virAsprintf(&def->name, "%lld", (long long)tv.tv_sec) < 0) {
            virReportOOMError();
            goto cleanup;
        }
    }

    def->description = virXPathString("string(./description)", ctxt);

    if (flags & VIR_DOMAIN_SNAPSHOT_PARSE_REDEFINE) {
        if (virXPathLongLong("string(./creationTime)", ctxt,
                             &def->creationTime) < 0) {
            virReportError(VIR_ERR_INTERNAL_ERROR, "%s",
                           _("missing creationTime from existing snapshot"));
            goto cleanup;
        }

        def->parent = virXPathString("string(./parent/name)", ctxt);

        state = virXPathString("string(./state)", ctxt);
        if (state == NULL) {
            /* there was no state in an existing snapshot; this
             * should never happen
             */
            virReportError(VIR_ERR_XML_ERROR, "%s",
                           _("missing state from existing snapshot"));
            goto cleanup;
        }
        def->state = virDomainSnapshotStateTypeFromString(state);
        if (def->state < 0) {
            virReportError(VIR_ERR_XML_ERROR,
                           _("Invalid state '%s' in domain snapshot XML"),
                           state);
            goto cleanup;
        }
        offline = (def->state == VIR_DOMAIN_SHUTOFF ||
                   def->state == VIR_DOMAIN_DISK_SNAPSHOT);

        /* Older snapshots were created with just <domain>/<uuid>, and
         * lack domain/@type.  In that case, leave dom NULL, and
         * clients will have to decide between best effort
         * initialization or outright failure.  */
        if ((tmp = virXPathString("string(./domain/@type)", ctxt))) {
            xmlNodePtr domainNode = virXPathNode("./domain", ctxt);

            VIR_FREE(tmp);
            if (!domainNode) {
                virReportError(VIR_ERR_INTERNAL_ERROR, "%s",
                               _("missing domain in snapshot"));
                goto cleanup;
            }
            def->dom = virDomainDefParseNode(caps, xml, domainNode,
                                             expectedVirtTypes,
                                             (VIR_DOMAIN_XML_INACTIVE |
                                              VIR_DOMAIN_XML_SECURE));
            if (!def->dom)
                goto cleanup;
        } else {
            VIR_WARN("parsing older snapshot that lacks domain");
        }
    } else {
        def->creationTime = tv.tv_sec;
    }

    memorySnapshot = virXPathString("string(./memory/@snapshot)", ctxt);
    memoryFile = virXPathString("string(./memory/@file)", ctxt);
    if (memorySnapshot) {
        def->memory = virDomainSnapshotLocationTypeFromString(memorySnapshot);
        if (def->memory <= 0) {
            virReportError(VIR_ERR_XML_ERROR,
                           _("unknown memory snapshot setting '%s'"),
                           memorySnapshot);
            goto cleanup;
        }
        if (memoryFile &&
            def->memory != VIR_DOMAIN_SNAPSHOT_LOCATION_EXTERNAL) {
            virReportError(VIR_ERR_XML_ERROR,
                           _("memory filename '%s' requires external snapshot"),
                           memoryFile);
            goto cleanup;
        }
        if (!memoryFile &&
            def->memory == VIR_DOMAIN_SNAPSHOT_LOCATION_EXTERNAL) {
            virReportError(VIR_ERR_XML_ERROR, "%s",
                           _("external memory snapshots require a filename"));
            goto cleanup;
        }
    } else if (memoryFile) {
        def->memory = VIR_DOMAIN_SNAPSHOT_LOCATION_EXTERNAL;
    } else if (flags & VIR_DOMAIN_SNAPSHOT_PARSE_REDEFINE) {
        def->memory = (offline ?
                       VIR_DOMAIN_SNAPSHOT_LOCATION_NONE :
                       VIR_DOMAIN_SNAPSHOT_LOCATION_INTERNAL);
    }
    if (offline && def->memory &&
        def->memory != VIR_DOMAIN_SNAPSHOT_LOCATION_NONE) {
        virReportError(VIR_ERR_XML_ERROR, "%s",
                       _("memory state cannot be saved with offline snapshot"));
        goto cleanup;
    }
    def->file = memoryFile;
    memoryFile = NULL;

    if ((i = virXPathNodeSet("./disks/*", ctxt, &nodes)) < 0)
        goto cleanup;
    if (flags & VIR_DOMAIN_SNAPSHOT_PARSE_DISKS) {
        def->ndisks = i;
        if (def->ndisks && VIR_ALLOC_N(def->disks, def->ndisks) < 0) {
            virReportOOMError();
            goto cleanup;
        }
        for (i = 0; i < def->ndisks; i++) {
            if (virDomainSnapshotDiskDefParseXML(nodes[i], &def->disks[i]) < 0)
                goto cleanup;
        }
        VIR_FREE(nodes);
    } else if (i) {
        virReportError(VIR_ERR_ARGUMENT_UNSUPPORTED, "%s",
                       _("unable to handle disk requests in snapshot"));
        goto cleanup;
    }

    if (flags & VIR_DOMAIN_SNAPSHOT_PARSE_INTERNAL) {
        if (virXPathInt("string(./active)", ctxt, &active) < 0) {
            virReportError(VIR_ERR_INTERNAL_ERROR, "%s",
                           _("Could not find 'active' element"));
            goto cleanup;
        }
        def->current = active != 0;
    }

    ret = def;

cleanup:
    VIR_FREE(creation);
    VIR_FREE(state);
    VIR_FREE(nodes);
    VIR_FREE(memorySnapshot);
    VIR_FREE(memoryFile);
    xmlXPathFreeContext(ctxt);
    if (ret == NULL)
        virDomainSnapshotDefFree(def);
    xmlFreeDoc(xml);

    return ret;
}

static int
disksorter(const void *a, const void *b)
{
    const virDomainSnapshotDiskDef *diska = a;
    const virDomainSnapshotDiskDef *diskb = b;

    /* Integer overflow shouldn't be a problem here.  */
    return diska->index - diskb->index;
}

/* Align def->disks to def->domain.  Sort the list of def->disks,
 * filling in any missing disks or snapshot state defaults given by
 * the domain, with a fallback to a passed in default.  Convert paths
 * to disk targets for uniformity.  Issue an error and return -1 if
 * any def->disks[n]->name appears more than once or does not map to
 * dom->disks.  If require_match, also ensure that there is no
 * conflicting requests for both internal and external snapshots.  */
int
virDomainSnapshotAlignDisks(virDomainSnapshotDefPtr def,
                            int default_snapshot,
                            bool require_match)
{
    int ret = -1;
    virBitmapPtr map = NULL;
    int i;
    int ndisks;
    bool inuse;

    if (!def->dom) {
        virReportError(VIR_ERR_INTERNAL_ERROR, "%s",
                       _("missing domain in snapshot"));
        goto cleanup;
    }

    if (def->ndisks > def->dom->ndisks) {
        virReportError(VIR_ERR_CONFIG_UNSUPPORTED, "%s",
                       _("too many disk snapshot requests for domain"));
        goto cleanup;
    }

    /* Unlikely to have a guest without disks but technically possible.  */
    if (!def->dom->ndisks) {
        ret = 0;
        goto cleanup;
    }

    if (!(map = virBitmapNew(def->dom->ndisks))) {
        virReportOOMError();
        goto cleanup;
    }

    /* Double check requested disks.  */
    for (i = 0; i < def->ndisks; i++) {
        virDomainSnapshotDiskDefPtr disk = &def->disks[i];
        int idx = virDomainDiskIndexByName(def->dom, disk->name, false);
        int disk_snapshot;

        if (idx < 0) {
            virReportError(VIR_ERR_CONFIG_UNSUPPORTED,
                           _("no disk named '%s'"), disk->name);
            goto cleanup;
        }

        if (virBitmapGetBit(map, idx, &inuse) < 0 || inuse) {
            virReportError(VIR_ERR_CONFIG_UNSUPPORTED,
                           _("disk '%s' specified twice"),
                           disk->name);
            goto cleanup;
        }
        ignore_value(virBitmapSetBit(map, idx));
        disk->index = idx;

        disk_snapshot = def->dom->disks[idx]->snapshot;
        if (!disk->snapshot) {
            if (disk_snapshot &&
                (!require_match ||
                 disk_snapshot == VIR_DOMAIN_SNAPSHOT_LOCATION_NONE))
                disk->snapshot = disk_snapshot;
            else
                disk->snapshot = default_snapshot;
        } else if (require_match &&
                   disk->snapshot != default_snapshot &&
                   !(disk->snapshot == VIR_DOMAIN_SNAPSHOT_LOCATION_NONE &&
                     disk_snapshot == VIR_DOMAIN_SNAPSHOT_LOCATION_NONE)) {
            const char *tmp;

            tmp = virDomainSnapshotLocationTypeToString(default_snapshot);
            virReportError(VIR_ERR_CONFIG_UNSUPPORTED,
                           _("disk '%s' must use snapshot mode '%s'"),
                           disk->name, tmp);
            goto cleanup;
        }
        if (disk->file &&
            disk->snapshot != VIR_DOMAIN_SNAPSHOT_LOCATION_EXTERNAL) {
            virReportError(VIR_ERR_CONFIG_UNSUPPORTED,
                           _("file '%s' for disk '%s' requires "
                             "use of external snapshot mode"),
                           disk->file, disk->name);
            goto cleanup;
        }
        if (STRNEQ(disk->name, def->dom->disks[idx]->dst)) {
            VIR_FREE(disk->name);
            if (!(disk->name = strdup(def->dom->disks[idx]->dst))) {
                virReportOOMError();
                goto cleanup;
            }
        }
    }

    /* Provide defaults for all remaining disks.  */
    ndisks = def->ndisks;
    if (VIR_EXPAND_N(def->disks, def->ndisks,
                     def->dom->ndisks - def->ndisks) < 0) {
        virReportOOMError();
        goto cleanup;
    }

    for (i = 0; i < def->dom->ndisks; i++) {
        virDomainSnapshotDiskDefPtr disk;

        ignore_value(virBitmapGetBit(map, i, &inuse));
        if (inuse)
            continue;
        disk = &def->disks[ndisks++];
        if (!(disk->name = strdup(def->dom->disks[i]->dst))) {
            virReportOOMError();
            goto cleanup;
        }
        disk->index = i;
        disk->snapshot = def->dom->disks[i]->snapshot;
        if (!disk->snapshot)
            disk->snapshot = default_snapshot;
    }

    qsort(&def->disks[0], def->ndisks, sizeof(def->disks[0]), disksorter);

    /* Generate any default external file names, but only if the
     * backing file is a regular file.  */
    for (i = 0; i < def->ndisks; i++) {
        virDomainSnapshotDiskDefPtr disk = &def->disks[i];

        if (disk->snapshot == VIR_DOMAIN_SNAPSHOT_LOCATION_EXTERNAL &&
            !disk->file) {
            const char *original = def->dom->disks[i]->src;
            const char *tmp;
            struct stat sb;

            if (!original) {
                virReportError(VIR_ERR_CONFIG_UNSUPPORTED,
                               _("cannot generate external snapshot name "
                                 "for disk '%s' without source"),
                               disk->name);
                goto cleanup;
            }
            if (stat(original, &sb) < 0 || !S_ISREG(sb.st_mode)) {
                virReportError(VIR_ERR_CONFIG_UNSUPPORTED,
                               _("source for disk '%s' is not a regular "
                                 "file; refusing to generate external "
                                 "snapshot name"),
                               disk->name);
                goto cleanup;
            }

            tmp = strrchr(original, '.');
            if (!tmp || strchr(tmp, '/')) {
                ignore_value(virAsprintf(&disk->file, "%s.%s",
                                         original, def->name));
            } else {
                if ((tmp - original) > INT_MAX) {
                    virReportError(VIR_ERR_INTERNAL_ERROR, "%s",
                                   _("integer overflow"));
                    goto cleanup;
                }
                ignore_value(virAsprintf(&disk->file, "%.*s.%s",
                                         (int) (tmp - original), original,
                                         def->name));
            }
            if (!disk->file) {
                virReportOOMError();
                goto cleanup;
            }
        }
    }

    ret = 0;

cleanup:
    virBitmapFree(map);
    return ret;
}

char *virDomainSnapshotDefFormat(const char *domain_uuid,
                                 virDomainSnapshotDefPtr def,
                                 unsigned int flags,
                                 int internal)
{
    virBuffer buf = VIR_BUFFER_INITIALIZER;
    int i;

    virCheckFlags(VIR_DOMAIN_XML_SECURE |
                  VIR_DOMAIN_XML_UPDATE_CPU, NULL);

    flags |= VIR_DOMAIN_XML_INACTIVE;

    virBufferAddLit(&buf, "<domainsnapshot>\n");
    virBufferEscapeString(&buf, "  <name>%s</name>\n", def->name);
    if (def->description)
        virBufferEscapeString(&buf, "  <description>%s</description>\n",
                              def->description);
    virBufferAsprintf(&buf, "  <state>%s</state>\n",
                      virDomainSnapshotStateTypeToString(def->state));
    if (def->parent) {
        virBufferAddLit(&buf, "  <parent>\n");
        virBufferEscapeString(&buf, "    <name>%s</name>\n", def->parent);
        virBufferAddLit(&buf, "  </parent>\n");
    }
    virBufferAsprintf(&buf, "  <creationTime>%lld</creationTime>\n",
                      def->creationTime);
    if (def->memory) {
        virBufferAsprintf(&buf, "  <memory snapshot='%s'",
                          virDomainSnapshotLocationTypeToString(def->memory));
        virBufferEscapeString(&buf, " file='%s'", def->file);
        virBufferAddLit(&buf, "/>\n");
    }
    if (def->ndisks) {
        virBufferAddLit(&buf, "  <disks>\n");
        for (i = 0; i < def->ndisks; i++) {
            virDomainSnapshotDiskDefPtr disk = &def->disks[i];

            if (!disk->name)
                continue;

            virBufferEscapeString(&buf, "    <disk name='%s'", disk->name);
            if (disk->snapshot)
                virBufferAsprintf(&buf, " snapshot='%s'",
                                  virDomainSnapshotLocationTypeToString(disk->snapshot));
            if (disk->file || disk->format > 0) {
                virBufferAddLit(&buf, ">\n");
                if (disk->format > 0)
                    virBufferEscapeString(&buf, "      <driver type='%s'/>\n",
                                          virStorageFileFormatTypeToString(
                                              disk->format));
                if (disk->file)
                    virBufferEscapeString(&buf, "      <source file='%s'/>\n",
                                          disk->file);
                virBufferAddLit(&buf, "    </disk>\n");
            } else {
                virBufferAddLit(&buf, "/>\n");
            }
        }
        virBufferAddLit(&buf, "  </disks>\n");
    }
    if (def->dom) {
        virBufferAdjustIndent(&buf, 2);
        if (virDomainDefFormatInternal(def->dom, flags, &buf) < 0) {
            virBufferFreeAndReset(&buf);
            return NULL;
        }
        virBufferAdjustIndent(&buf, -2);
    } else if (domain_uuid) {
        virBufferAddLit(&buf, "  <domain>\n");
        virBufferAsprintf(&buf, "    <uuid>%s</uuid>\n", domain_uuid);
        virBufferAddLit(&buf, "  </domain>\n");
    }
    if (internal)
        virBufferAsprintf(&buf, "  <active>%d</active>\n", def->current);
    virBufferAddLit(&buf, "</domainsnapshot>\n");

    if (virBufferError(&buf)) {
        virBufferFreeAndReset(&buf);
        virReportOOMError();
        return NULL;
    }

    return virBufferContentAndReset(&buf);
}

/* Snapshot Obj functions */
static virDomainSnapshotObjPtr virDomainSnapshotObjNew(void)
{
    virDomainSnapshotObjPtr snapshot;

    if (VIR_ALLOC(snapshot) < 0) {
        virReportOOMError();
        return NULL;
    }

    VIR_DEBUG("obj=%p", snapshot);

    return snapshot;
}

static void virDomainSnapshotObjFree(virDomainSnapshotObjPtr snapshot)
{
    if (!snapshot)
        return;

    VIR_DEBUG("obj=%p", snapshot);

    virDomainSnapshotDefFree(snapshot->def);
    VIR_FREE(snapshot);
}

virDomainSnapshotObjPtr virDomainSnapshotAssignDef(virDomainSnapshotObjListPtr snapshots,
                                                   const virDomainSnapshotDefPtr def)
{
    virDomainSnapshotObjPtr snap;

    if (virHashLookup(snapshots->objs, def->name) != NULL) {
        virReportError(VIR_ERR_INTERNAL_ERROR,
                       _("unexpected domain snapshot %s already exists"),
                       def->name);
        return NULL;
    }

    if (!(snap = virDomainSnapshotObjNew()))
        return NULL;
    snap->def = def;

    if (virHashAddEntry(snapshots->objs, snap->def->name, snap) < 0) {
        VIR_FREE(snap);
        return NULL;
    }

    return snap;
}

/* Snapshot Obj List functions */
static void
virDomainSnapshotObjListDataFree(void *payload,
                                 const void *name ATTRIBUTE_UNUSED)
{
    virDomainSnapshotObjPtr obj = payload;

    virDomainSnapshotObjFree(obj);
}

virDomainSnapshotObjListPtr
virDomainSnapshotObjListNew(void)
{
    virDomainSnapshotObjListPtr snapshots;
    if (VIR_ALLOC(snapshots) < 0) {
        virReportOOMError();
        return NULL;
    }
    snapshots->objs = virHashCreate(50, virDomainSnapshotObjListDataFree);
    if (!snapshots->objs) {
        VIR_FREE(snapshots);
        return NULL;
    }
    return snapshots;
}

void
virDomainSnapshotObjListFree(virDomainSnapshotObjListPtr snapshots)
{
    if (!snapshots)
        return;
    virHashFree(snapshots->objs);
    VIR_FREE(snapshots);
}

struct virDomainSnapshotNameData {
    char **const names;
    int maxnames;
    unsigned int flags;
    int count;
    bool error;
};

static void virDomainSnapshotObjListCopyNames(void *payload,
                                              const void *name ATTRIBUTE_UNUSED,
                                              void *opaque)
{
    virDomainSnapshotObjPtr obj = payload;
    struct virDomainSnapshotNameData *data = opaque;

    if (data->error)
        return;
    /* Caller already sanitized flags.  Filtering on DESCENDANTS was
     * done by choice of iteration in the caller.  */
    if ((data->flags & VIR_DOMAIN_SNAPSHOT_LIST_LEAVES) && obj->nchildren)
        return;
    if ((data->flags & VIR_DOMAIN_SNAPSHOT_LIST_NO_LEAVES) && !obj->nchildren)
        return;

    if (data->flags & VIR_DOMAIN_SNAPSHOT_FILTERS_STATUS) {
        if (!(data->flags & VIR_DOMAIN_SNAPSHOT_LIST_INACTIVE) &&
            obj->def->state == VIR_DOMAIN_SHUTOFF)
            return;
        if (!(data->flags & VIR_DOMAIN_SNAPSHOT_LIST_DISK_ONLY) &&
            obj->def->state == VIR_DOMAIN_DISK_SNAPSHOT)
            return;
        if (!(data->flags & VIR_DOMAIN_SNAPSHOT_LIST_ACTIVE) &&
            obj->def->state != VIR_DOMAIN_SHUTOFF &&
            obj->def->state != VIR_DOMAIN_DISK_SNAPSHOT)
            return;
    }

    if ((data->flags & VIR_DOMAIN_SNAPSHOT_LIST_INTERNAL) &&
        virDomainSnapshotIsExternal(obj))
        return;
    if ((data->flags & VIR_DOMAIN_SNAPSHOT_LIST_EXTERNAL) &&
        !virDomainSnapshotIsExternal(obj))
        return;

    if (data->names && data->count < data->maxnames &&
        !(data->names[data->count] = strdup(obj->def->name))) {
        data->error = true;
        virReportOOMError();
        return;
    }
    data->count++;
}

int
virDomainSnapshotObjListGetNames(virDomainSnapshotObjListPtr snapshots,
                                 virDomainSnapshotObjPtr from,
                                 char **const names, int maxnames,
                                 unsigned int flags)
{
    struct virDomainSnapshotNameData data = { names, maxnames, flags, 0,
                                              false };
    int i;

    if (!from) {
        /* LIST_ROOTS and LIST_DESCENDANTS have the same bit value,
         * but opposite semantics.  Toggle here to get the correct
         * traversal on the metaroot.  */
        flags ^= VIR_DOMAIN_SNAPSHOT_LIST_ROOTS;
        from = &snapshots->metaroot;
    }

    /* We handle LIST_ROOT/LIST_DESCENDANTS directly, mask that bit
     * out to determine when we must use the filter callback.  */
    data.flags &= ~VIR_DOMAIN_SNAPSHOT_LIST_DESCENDANTS;

    /* If this common code is being used, we assume that all snapshots
     * have metadata, and thus can handle METADATA up front as an
     * all-or-none filter.  XXX This might not always be true, if we
     * add the ability to track qcow2 internal snapshots without the
     * use of metadata.  */
    if ((data.flags & VIR_DOMAIN_SNAPSHOT_FILTERS_METADATA) ==
        VIR_DOMAIN_SNAPSHOT_LIST_NO_METADATA)
        return 0;
    data.flags &= ~VIR_DOMAIN_SNAPSHOT_FILTERS_METADATA;

    /* For ease of coding the visitor, it is easier to zero each group
     * where all of the bits are set.  */
    if ((data.flags & VIR_DOMAIN_SNAPSHOT_FILTERS_LEAVES) ==
        VIR_DOMAIN_SNAPSHOT_FILTERS_LEAVES)
        data.flags &= ~VIR_DOMAIN_SNAPSHOT_FILTERS_LEAVES;
    if ((data.flags & VIR_DOMAIN_SNAPSHOT_FILTERS_STATUS) ==
        VIR_DOMAIN_SNAPSHOT_FILTERS_STATUS)
        data.flags &= ~VIR_DOMAIN_SNAPSHOT_FILTERS_STATUS;
    if ((data.flags & VIR_DOMAIN_SNAPSHOT_FILTERS_LOCATION) ==
        VIR_DOMAIN_SNAPSHOT_FILTERS_LOCATION)
        data.flags &= ~VIR_DOMAIN_SNAPSHOT_FILTERS_LOCATION;

    if (flags & VIR_DOMAIN_SNAPSHOT_LIST_DESCENDANTS) {
        if (from->def)
            virDomainSnapshotForEachDescendant(from,
                                               virDomainSnapshotObjListCopyNames,
                                               &data);
        else if (names || data.flags)
            virHashForEach(snapshots->objs, virDomainSnapshotObjListCopyNames,
                           &data);
        else
            data.count = virHashSize(snapshots->objs);
    } else if (names || data.flags) {
        virDomainSnapshotForEachChild(from,
                                      virDomainSnapshotObjListCopyNames, &data);
    } else {
        data.count = from->nchildren;
    }

    if (data.error) {
        for (i = 0; i < data.count; i++)
            VIR_FREE(names[i]);
        return -1;
    }

    return data.count;
}

int
virDomainSnapshotObjListNum(virDomainSnapshotObjListPtr snapshots,
                            virDomainSnapshotObjPtr from,
                            unsigned int flags)
{
    return virDomainSnapshotObjListGetNames(snapshots, from, NULL, 0, flags);
}

virDomainSnapshotObjPtr
virDomainSnapshotFindByName(const virDomainSnapshotObjListPtr snapshots,
                            const char *name)
{
    return name ? virHashLookup(snapshots->objs, name) : &snapshots->metaroot;
}

void virDomainSnapshotObjListRemove(virDomainSnapshotObjListPtr snapshots,
                                    virDomainSnapshotObjPtr snapshot)
{
    virHashRemoveEntry(snapshots->objs, snapshot->def->name);
}

int
virDomainSnapshotForEach(virDomainSnapshotObjListPtr snapshots,
                         virHashIterator iter,
                         void *data)
{
    return virHashForEach(snapshots->objs, iter, 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(virDomainSnapshotObjPtr snapshot,
                              virHashIterator iter,
                              void *data)
{
    virDomainSnapshotObjPtr child = snapshot->first_child;

    while (child) {
        virDomainSnapshotObjPtr next = child->sibling;
        (iter)(child, child->def->name, data);
        child = next;
    }

    return snapshot->nchildren;
}

struct snapshot_act_on_descendant {
    int number;
    virHashIterator iter;
    void *data;
};

static void
virDomainSnapshotActOnDescendant(void *payload,
                                 const void *name,
                                 void *data)
{
    virDomainSnapshotObjPtr obj = payload;
    struct snapshot_act_on_descendant *curr = data;

    curr->number += 1 + virDomainSnapshotForEachDescendant(obj,
                                                           curr->iter,
                                                           curr->data);
    (curr->iter)(payload, name, 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(virDomainSnapshotObjPtr snapshot,
                                   virHashIterator iter,
                                   void *data)
{
    struct snapshot_act_on_descendant act;

    act.number = 0;
    act.iter = iter;
    act.data = data;
    virDomainSnapshotForEachChild(snapshot,
                                  virDomainSnapshotActOnDescendant, &act);

    return act.number;
}

/* Struct and callback function used as a hash table callback; each call
 * inspects the pre-existing snapshot->def->parent field, and adjusts
 * the snapshot->parent field as well as the parent's child fields to
 * wire up the hierarchical relations for the given snapshot.  The error
 * indicator gets set if a parent is missing or a requested parent would
 * cause a circular parent chain.  */
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;

    obj->parent = virDomainSnapshotFindByName(curr->snapshots,
                                              obj->def->parent);
    if (!obj->parent) {
        curr->err = -1;
        obj->parent = &curr->snapshots->metaroot;
        VIR_WARN("snapshot %s lacks parent", obj->def->name);
    } else {
        tmp = obj->parent;
        while (tmp && tmp->def) {
            if (tmp == obj) {
                curr->err = -1;
                obj->parent = &curr->snapshots->metaroot;
                VIR_WARN("snapshot %s in circular chain", obj->def->name);
                break;
            }
            tmp = tmp->parent;
        }
    }
    obj->parent->nchildren++;
    obj->sibling = obj->parent->first_child;
    obj->parent->first_child = 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(virDomainSnapshotObjPtr snapshot)
{
    virDomainSnapshotObjPtr prev = NULL;
    virDomainSnapshotObjPtr curr = NULL;

    snapshot->parent->nchildren--;
    curr = snapshot->parent->first_child;
    while (curr != snapshot) {
        if (!curr) {
            VIR_WARN("inconsistent snapshot relations");
            return;
        }
        prev = curr;
        curr = curr->sibling;
    }
    if (prev)
        prev->sibling = snapshot->sibling;
    else
        snapshot->parent->first_child = snapshot->sibling;
    snapshot->parent = NULL;
    snapshot->sibling = NULL;
}

int
virDomainListSnapshots(virDomainSnapshotObjListPtr snapshots,
                       virDomainSnapshotObjPtr from,
                       virDomainPtr dom,
                       virDomainSnapshotPtr **snaps,
                       unsigned int flags)
{
    int count = virDomainSnapshotObjListNum(snapshots, from, flags);
    virDomainSnapshotPtr *list;
    char **names;
    int ret = -1;
    int i;

    if (!snaps)
        return count;
    if (VIR_ALLOC_N(names, count) < 0 ||
        VIR_ALLOC_N(list, count + 1) < 0) {
        virReportOOMError();
        goto cleanup;
    }

    if (virDomainSnapshotObjListGetNames(snapshots, from, names, count,
                                         flags) < 0)
        goto cleanup;
    for (i = 0; i < count; i++)
        if ((list[i] = virGetDomainSnapshot(dom, names[i])) == NULL)
            goto cleanup;

    ret = count;
    *snaps = list;

cleanup:
    for (i = 0; i < count; i++)
        VIR_FREE(names[i]);
    VIR_FREE(names);
    if (ret < 0 && list) {
        for (i = 0; i < count; i++)
            virObjectUnref(list[i]);
        VIR_FREE(list);
    }
    return ret;
}


bool
virDomainSnapshotIsExternal(virDomainSnapshotObjPtr snap)
{
    int i;

    if (snap->def->memory == VIR_DOMAIN_SNAPSHOT_LOCATION_EXTERNAL)
        return true;

    for (i = 0; i < snap->def->ndisks; i++) {
        if (snap->def->disks[i].snapshot == VIR_DOMAIN_SNAPSHOT_LOCATION_EXTERNAL)
            return true;
    }

    return false;
}