OpenSolaris_b135/lib/libzfs/common/libzfs_graph.c
/*
* CDDL HEADER START
*
* The contents of this file are subject to the terms of the
* Common Development and Distribution License (the "License").
* You may not use this file except in compliance with the License.
*
* You can obtain a copy of the license at usr/src/OPENSOLARIS.LICENSE
* or http://www.opensolaris.org/os/licensing.
* See the License for the specific language governing permissions
* and limitations under the License.
*
* When distributing Covered Code, include this CDDL HEADER in each
* file and include the License file at usr/src/OPENSOLARIS.LICENSE.
* If applicable, add the following below this CDDL HEADER, with the
* fields enclosed by brackets "[]" replaced with your own identifying
* information: Portions Copyright [yyyy] [name of copyright owner]
*
* CDDL HEADER END
*/
/*
* Copyright 2009 Sun Microsystems, Inc. All rights reserved.
* Use is subject to license terms.
*/
/*
* Iterate over all children of the current object. This includes the normal
* dataset hierarchy, but also arbitrary hierarchies due to clones. We want to
* walk all datasets in the pool, and construct a directed graph of the form:
*
* home
* |
* +----+----+
* | |
* v v ws
* bar baz |
* | |
* v v
* @yesterday ----> foo
*
* In order to construct this graph, we have to walk every dataset in the pool,
* because the clone parent is stored as a property of the child, not the
* parent. The parent only keeps track of the number of clones.
*
* In the normal case (without clones) this would be rather expensive. To avoid
* unnecessary computation, we first try a walk of the subtree hierarchy
* starting from the initial node. At each dataset, we construct a node in the
* graph and an edge leading from its parent. If we don't see any snapshots
* with a non-zero clone count, then we are finished.
*
* If we do find a cloned snapshot, then we finish the walk of the current
* subtree, but indicate that we need to do a complete walk. We then perform a
* global walk of all datasets, avoiding the subtree we already processed.
*
* At the end of this, we'll end up with a directed graph of all relevant (and
* possible some irrelevant) datasets in the system. We need to both find our
* limiting subgraph and determine a safe ordering in which to destroy the
* datasets. We do a topological ordering of our graph starting at our target
* dataset, and then walk the results in reverse.
*
* It's possible for the graph to have cycles if, for example, the user renames
* a clone to be the parent of its origin snapshot. The user can request to
* generate an error in this case, or ignore the cycle and continue.
*
* When removing datasets, we want to destroy the snapshots in chronological
* order (because this is the most efficient method). In order to accomplish
* this, we store the creation transaction group with each vertex and keep each
* vertex's edges sorted according to this value. The topological sort will
* automatically walk the snapshots in the correct order.
*/
#include <assert.h>
#include <libintl.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <strings.h>
#include <unistd.h>
#include <libzfs.h>
#include "libzfs_impl.h"
#include "zfs_namecheck.h"
#define MIN_EDGECOUNT 4
/*
* Vertex structure. Indexed by dataset name, this structure maintains a list
* of edges to other vertices.
*/
struct zfs_edge;
typedef struct zfs_vertex {
char zv_dataset[ZFS_MAXNAMELEN];
struct zfs_vertex *zv_next;
int zv_visited;
uint64_t zv_txg;
struct zfs_edge **zv_edges;
int zv_edgecount;
int zv_edgealloc;
} zfs_vertex_t;
enum {
VISIT_SEEN = 1,
VISIT_SORT_PRE,
VISIT_SORT_POST
};
/*
* Edge structure. Simply maintains a pointer to the destination vertex. There
* is no need to store the source vertex, since we only use edges in the context
* of the source vertex.
*/
typedef struct zfs_edge {
zfs_vertex_t *ze_dest;
struct zfs_edge *ze_next;
} zfs_edge_t;
#define ZFS_GRAPH_SIZE 1027 /* this could be dynamic some day */
/*
* Graph structure. Vertices are maintained in a hash indexed by dataset name.
*/
typedef struct zfs_graph {
zfs_vertex_t **zg_hash;
size_t zg_size;
size_t zg_nvertex;
const char *zg_root;
int zg_clone_count;
} zfs_graph_t;
/*
* Allocate a new edge pointing to the target vertex.
*/
static zfs_edge_t *
zfs_edge_create(libzfs_handle_t *hdl, zfs_vertex_t *dest)
{
zfs_edge_t *zep = zfs_alloc(hdl, sizeof (zfs_edge_t));
if (zep == NULL)
return (NULL);
zep->ze_dest = dest;
return (zep);
}
/*
* Destroy an edge.
*/
static void
zfs_edge_destroy(zfs_edge_t *zep)
{
free(zep);
}
/*
* Allocate a new vertex with the given name.
*/
static zfs_vertex_t *
zfs_vertex_create(libzfs_handle_t *hdl, const char *dataset)
{
zfs_vertex_t *zvp = zfs_alloc(hdl, sizeof (zfs_vertex_t));
if (zvp == NULL)
return (NULL);
assert(strlen(dataset) < ZFS_MAXNAMELEN);
(void) strlcpy(zvp->zv_dataset, dataset, sizeof (zvp->zv_dataset));
if ((zvp->zv_edges = zfs_alloc(hdl,
MIN_EDGECOUNT * sizeof (void *))) == NULL) {
free(zvp);
return (NULL);
}
zvp->zv_edgealloc = MIN_EDGECOUNT;
return (zvp);
}
/*
* Destroy a vertex. Frees up any associated edges.
*/
static void
zfs_vertex_destroy(zfs_vertex_t *zvp)
{
int i;
for (i = 0; i < zvp->zv_edgecount; i++)
zfs_edge_destroy(zvp->zv_edges[i]);
free(zvp->zv_edges);
free(zvp);
}
/*
* Given a vertex, add an edge to the destination vertex.
*/
static int
zfs_vertex_add_edge(libzfs_handle_t *hdl, zfs_vertex_t *zvp,
zfs_vertex_t *dest)
{
zfs_edge_t *zep = zfs_edge_create(hdl, dest);
if (zep == NULL)
return (-1);
if (zvp->zv_edgecount == zvp->zv_edgealloc) {
void *ptr;
if ((ptr = zfs_realloc(hdl, zvp->zv_edges,
zvp->zv_edgealloc * sizeof (void *),
zvp->zv_edgealloc * 2 * sizeof (void *))) == NULL)
return (-1);
zvp->zv_edges = ptr;
zvp->zv_edgealloc *= 2;
}
zvp->zv_edges[zvp->zv_edgecount++] = zep;
return (0);
}
static int
zfs_edge_compare(const void *a, const void *b)
{
const zfs_edge_t *ea = *((zfs_edge_t **)a);
const zfs_edge_t *eb = *((zfs_edge_t **)b);
if (ea->ze_dest->zv_txg < eb->ze_dest->zv_txg)
return (-1);
if (ea->ze_dest->zv_txg > eb->ze_dest->zv_txg)
return (1);
return (0);
}
/*
* Sort the given vertex edges according to the creation txg of each vertex.
*/
static void
zfs_vertex_sort_edges(zfs_vertex_t *zvp)
{
if (zvp->zv_edgecount == 0)
return;
qsort(zvp->zv_edges, zvp->zv_edgecount, sizeof (void *),
zfs_edge_compare);
}
/*
* Construct a new graph object. We allow the size to be specified as a
* parameter so in the future we can size the hash according to the number of
* datasets in the pool.
*/
static zfs_graph_t *
zfs_graph_create(libzfs_handle_t *hdl, const char *dataset, size_t size)
{
zfs_graph_t *zgp = zfs_alloc(hdl, sizeof (zfs_graph_t));
if (zgp == NULL)
return (NULL);
zgp->zg_size = size;
if ((zgp->zg_hash = zfs_alloc(hdl,
size * sizeof (zfs_vertex_t *))) == NULL) {
free(zgp);
return (NULL);
}
zgp->zg_root = dataset;
zgp->zg_clone_count = 0;
return (zgp);
}
/*
* Destroy a graph object. We have to iterate over all the hash chains,
* destroying each vertex in the process.
*/
static void
zfs_graph_destroy(zfs_graph_t *zgp)
{
int i;
zfs_vertex_t *current, *next;
for (i = 0; i < zgp->zg_size; i++) {
current = zgp->zg_hash[i];
while (current != NULL) {
next = current->zv_next;
zfs_vertex_destroy(current);
current = next;
}
}
free(zgp->zg_hash);
free(zgp);
}
/*
* Graph hash function. Classic bernstein k=33 hash function, taken from
* usr/src/cmd/sgs/tools/common/strhash.c
*/
static size_t
zfs_graph_hash(zfs_graph_t *zgp, const char *str)
{
size_t hash = 5381;
int c;
while ((c = *str++) != 0)
hash = ((hash << 5) + hash) + c; /* hash * 33 + c */
return (hash % zgp->zg_size);
}
/*
* Given a dataset name, finds the associated vertex, creating it if necessary.
*/
static zfs_vertex_t *
zfs_graph_lookup(libzfs_handle_t *hdl, zfs_graph_t *zgp, const char *dataset,
uint64_t txg)
{
size_t idx = zfs_graph_hash(zgp, dataset);
zfs_vertex_t *zvp;
for (zvp = zgp->zg_hash[idx]; zvp != NULL; zvp = zvp->zv_next) {
if (strcmp(zvp->zv_dataset, dataset) == 0) {
if (zvp->zv_txg == 0)
zvp->zv_txg = txg;
return (zvp);
}
}
if ((zvp = zfs_vertex_create(hdl, dataset)) == NULL)
return (NULL);
zvp->zv_next = zgp->zg_hash[idx];
zvp->zv_txg = txg;
zgp->zg_hash[idx] = zvp;
zgp->zg_nvertex++;
return (zvp);
}
/*
* Given two dataset names, create an edge between them. For the source vertex,
* mark 'zv_visited' to indicate that we have seen this vertex, and not simply
* created it as a destination of another edge. If 'dest' is NULL, then this
* is an individual vertex (i.e. the starting vertex), so don't add an edge.
*/
static int
zfs_graph_add(libzfs_handle_t *hdl, zfs_graph_t *zgp, const char *source,
const char *dest, uint64_t txg)
{
zfs_vertex_t *svp, *dvp;
if ((svp = zfs_graph_lookup(hdl, zgp, source, 0)) == NULL)
return (-1);
svp->zv_visited = VISIT_SEEN;
if (dest != NULL) {
dvp = zfs_graph_lookup(hdl, zgp, dest, txg);
if (dvp == NULL)
return (-1);
if (zfs_vertex_add_edge(hdl, svp, dvp) != 0)
return (-1);
}
return (0);
}
/*
* Iterate over all children of the given dataset, adding any vertices
* as necessary. Returns -1 if there was an error, or 0 otherwise.
* This is a simple recursive algorithm - the ZFS namespace typically
* is very flat. We manually invoke the necessary ioctl() calls to
* avoid the overhead and additional semantics of zfs_open().
*/
static int
iterate_children(libzfs_handle_t *hdl, zfs_graph_t *zgp, const char *dataset)
{
zfs_cmd_t zc = { 0 };
zfs_vertex_t *zvp;
/*
* Look up the source vertex, and avoid it if we've seen it before.
*/
zvp = zfs_graph_lookup(hdl, zgp, dataset, 0);
if (zvp == NULL)
return (-1);
if (zvp->zv_visited == VISIT_SEEN)
return (0);
/*
* Iterate over all children
*/
for ((void) strlcpy(zc.zc_name, dataset, sizeof (zc.zc_name));
ioctl(hdl->libzfs_fd, ZFS_IOC_DATASET_LIST_NEXT, &zc) == 0;
(void) strlcpy(zc.zc_name, dataset, sizeof (zc.zc_name))) {
/*
* Get statistics for this dataset, to determine the type of the
* dataset and clone statistics. If this fails, the dataset has
* since been removed, and we're pretty much screwed anyway.
*/
zc.zc_objset_stats.dds_origin[0] = '\0';
if (ioctl(hdl->libzfs_fd, ZFS_IOC_OBJSET_STATS, &zc) != 0)
continue;
if (zc.zc_objset_stats.dds_origin[0] != '\0') {
if (zfs_graph_add(hdl, zgp,
zc.zc_objset_stats.dds_origin, zc.zc_name,
zc.zc_objset_stats.dds_creation_txg) != 0)
return (-1);
/*
* Count origins only if they are contained in the graph
*/
if (isa_child_of(zc.zc_objset_stats.dds_origin,
zgp->zg_root))
zgp->zg_clone_count--;
}
/*
* Add an edge between the parent and the child.
*/
if (zfs_graph_add(hdl, zgp, dataset, zc.zc_name,
zc.zc_objset_stats.dds_creation_txg) != 0)
return (-1);
/*
* Recursively visit child
*/
if (iterate_children(hdl, zgp, zc.zc_name))
return (-1);
}
/*
* Now iterate over all snapshots.
*/
bzero(&zc, sizeof (zc));
for ((void) strlcpy(zc.zc_name, dataset, sizeof (zc.zc_name));
ioctl(hdl->libzfs_fd, ZFS_IOC_SNAPSHOT_LIST_NEXT, &zc) == 0;
(void) strlcpy(zc.zc_name, dataset, sizeof (zc.zc_name))) {
/*
* Get statistics for this dataset, to determine the type of the
* dataset and clone statistics. If this fails, the dataset has
* since been removed, and we're pretty much screwed anyway.
*/
if (ioctl(hdl->libzfs_fd, ZFS_IOC_OBJSET_STATS, &zc) != 0)
continue;
/*
* Add an edge between the parent and the child.
*/
if (zfs_graph_add(hdl, zgp, dataset, zc.zc_name,
zc.zc_objset_stats.dds_creation_txg) != 0)
return (-1);
zgp->zg_clone_count += zc.zc_objset_stats.dds_num_clones;
}
zvp->zv_visited = VISIT_SEEN;
return (0);
}
/*
* Returns false if there are no snapshots with dependent clones in this
* subtree or if all of those clones are also in this subtree. Returns
* true if there is an error or there are external dependents.
*/
static boolean_t
external_dependents(libzfs_handle_t *hdl, zfs_graph_t *zgp, const char *dataset)
{
zfs_cmd_t zc = { 0 };
/*
* Check whether this dataset is a clone or has clones since
* iterate_children() only checks the children.
*/
(void) strlcpy(zc.zc_name, dataset, sizeof (zc.zc_name));
if (ioctl(hdl->libzfs_fd, ZFS_IOC_OBJSET_STATS, &zc) != 0)
return (B_TRUE);
if (zc.zc_objset_stats.dds_origin[0] != '\0') {
if (zfs_graph_add(hdl, zgp,
zc.zc_objset_stats.dds_origin, zc.zc_name,
zc.zc_objset_stats.dds_creation_txg) != 0)
return (B_TRUE);
if (isa_child_of(zc.zc_objset_stats.dds_origin, dataset))
zgp->zg_clone_count--;
}
if ((zc.zc_objset_stats.dds_num_clones) ||
iterate_children(hdl, zgp, dataset))
return (B_TRUE);
return (zgp->zg_clone_count != 0);
}
/*
* Construct a complete graph of all necessary vertices. First, iterate over
* only our object's children. If no cloned snapshots are found, or all of
* the cloned snapshots are in this subtree then return a graph of the subtree.
* Otherwise, start at the root of the pool and iterate over all datasets.
*/
static zfs_graph_t *
construct_graph(libzfs_handle_t *hdl, const char *dataset)
{
zfs_graph_t *zgp = zfs_graph_create(hdl, dataset, ZFS_GRAPH_SIZE);
int ret = 0;
if (zgp == NULL)
return (zgp);
if ((strchr(dataset, '/') == NULL) ||
(external_dependents(hdl, zgp, dataset))) {
/*
* Determine pool name and try again.
*/
int len = strcspn(dataset, "/@") + 1;
char *pool = zfs_alloc(hdl, len);
if (pool == NULL) {
zfs_graph_destroy(zgp);
return (NULL);
}
(void) strlcpy(pool, dataset, len);
if (iterate_children(hdl, zgp, pool) == -1 ||
zfs_graph_add(hdl, zgp, pool, NULL, 0) != 0) {
free(pool);
zfs_graph_destroy(zgp);
return (NULL);
}
free(pool);
}
if (ret == -1 || zfs_graph_add(hdl, zgp, dataset, NULL, 0) != 0) {
zfs_graph_destroy(zgp);
return (NULL);
}
return (zgp);
}
/*
* Given a graph, do a recursive topological sort into the given array. This is
* really just a depth first search, so that the deepest nodes appear first.
* hijack the 'zv_visited' marker to avoid visiting the same vertex twice.
*/
static int
topo_sort(libzfs_handle_t *hdl, boolean_t allowrecursion, char **result,
size_t *idx, zfs_vertex_t *zgv)
{
int i;
if (zgv->zv_visited == VISIT_SORT_PRE && !allowrecursion) {
/*
* If we've already seen this vertex as part of our depth-first
* search, then we have a cyclic dependency, and we must return
* an error.
*/
zfs_error_aux(hdl, dgettext(TEXT_DOMAIN,
"recursive dependency at '%s'"),
zgv->zv_dataset);
return (zfs_error(hdl, EZFS_RECURSIVE,
dgettext(TEXT_DOMAIN,
"cannot determine dependent datasets")));
} else if (zgv->zv_visited >= VISIT_SORT_PRE) {
/*
* If we've already processed this as part of the topological
* sort, then don't bother doing so again.
*/
return (0);
}
zgv->zv_visited = VISIT_SORT_PRE;
/* avoid doing a search if we don't have to */
zfs_vertex_sort_edges(zgv);
for (i = 0; i < zgv->zv_edgecount; i++) {
if (topo_sort(hdl, allowrecursion, result, idx,
zgv->zv_edges[i]->ze_dest) != 0)
return (-1);
}
/* we may have visited this in the course of the above */
if (zgv->zv_visited == VISIT_SORT_POST)
return (0);
if ((result[*idx] = zfs_alloc(hdl,
strlen(zgv->zv_dataset) + 1)) == NULL)
return (-1);
(void) strcpy(result[*idx], zgv->zv_dataset);
*idx += 1;
zgv->zv_visited = VISIT_SORT_POST;
return (0);
}
/*
* The only public interface for this file. Do the dirty work of constructing a
* child list for the given object. Construct the graph, do the toplogical
* sort, and then return the array of strings to the caller.
*
* The 'allowrecursion' parameter controls behavior when cycles are found. If
* it is set, the the cycle is ignored and the results returned as if the cycle
* did not exist. If it is not set, then the routine will generate an error if
* a cycle is found.
*/
int
get_dependents(libzfs_handle_t *hdl, boolean_t allowrecursion,
const char *dataset, char ***result, size_t *count)
{
zfs_graph_t *zgp;
zfs_vertex_t *zvp;
if ((zgp = construct_graph(hdl, dataset)) == NULL)
return (-1);
if ((*result = zfs_alloc(hdl,
zgp->zg_nvertex * sizeof (char *))) == NULL) {
zfs_graph_destroy(zgp);
return (-1);
}
if ((zvp = zfs_graph_lookup(hdl, zgp, dataset, 0)) == NULL) {
free(*result);
zfs_graph_destroy(zgp);
return (-1);
}
*count = 0;
if (topo_sort(hdl, allowrecursion, *result, count, zvp) != 0) {
free(*result);
zfs_graph_destroy(zgp);
return (-1);
}
/*
* Get rid of the last entry, which is our starting vertex and not
* strictly a dependent.
*/
assert(*count > 0);
free((*result)[*count - 1]);
(*count)--;
zfs_graph_destroy(zgp);
return (0);
}