libzfs_graph.c revision fa9e4066f08beec538e775443c5be79dd423fcab
/*
* CDDL HEADER START
*
* The contents of this file are subject to the terms of the
* Common Development and Distribution License, Version 1.0 only
* (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
* 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 2005 Sun Microsystems, Inc. All rights reserved.
* Use is subject to license terms.
*/
#pragma ident "%Z%%M% %I% %E% SMI"
/*
* 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.
*
* 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 <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;
int zv_edgecount;
int zv_edgealloc;
} zfs_vertex_t;
/*
* 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_edge_t;
/*
* Graph structure. Vertices are maintained in a hash indexed by dataset name.
*/
typedef struct zfs_graph {
} zfs_graph_t;
/*
* Allocate a new edge pointing to the target vertex.
*/
static zfs_edge_t *
{
return (zep);
}
/*
* Destroy an edge.
*/
static void
{
}
/*
* Allocate a new vertex with the given name.
*/
static zfs_vertex_t *
zfs_vertex_create(const char *dataset)
{
return (zvp);
}
/*
* Destroy a vertex. Frees up any associated edges.
*/
static void
{
int i;
for (i = 0; i < zvp->zv_edgecount; i++)
}
/*
* Given a vertex, add an edge to the destination vertex.
*/
static void
{
sizeof (void *));
zvp->zv_edgealloc * sizeof (void *));
}
}
static int
zfs_edge_compare(const void *a, const void *b)
{
return (-1);
return (1);
return (0);
}
/*
* Sort the given vertex edges according to the creation txg of each vertex.
*/
static void
{
if (zvp->zv_edgecount == 0)
return;
}
/*
* 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 *
{
return (zgp);
}
/*
* Destroy a graph object. We have to iterate over all the hash chains,
* destroying each vertex in the process.
*/
static void
{
int i;
}
}
}
/*
* Graph hash function. Classic bernstein k=33 hash function, taken from
*/
static size_t
{
int c;
while ((c = *str++) != 0)
}
/*
* Given a dataset name, finds the associated vertex, creating it if necessary.
*/
static zfs_vertex_t *
{
return (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 void
{
}
}
/*
* Iterate over all children of the given dataset, adding any vertices as
* necessary. Returns 0 if no cloned snapshots were seen, 1 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
{
int ret = 0;
/*
* Look up the source vertex, and avoid it if we've seen it before.
*/
if (zvp->zv_visited)
return (0);
/*
* Ignore private dataset names.
*/
continue;
/*
* 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.
*/
continue;
/*
* Add an edge between the parent and the child.
*/
/*
* If this dataset has a clone parent, add an appropriate edge.
*/
/*
* Iterate over all children
*/
/*
* Indicate if we found a dataset with a non-zero clone count.
*/
ret |= 1;
}
/*
* Now iterate over all snapshots.
*/
/*
* 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.
*/
continue;
/*
* Add an edge between the parent and the child.
*/
/*
* Indicate if we found a dataset with a non-zero clone count.
*/
ret |= 1;
}
return (ret);
}
/*
* Construct a complete graph of all necessary vertices. First, we iterate over
* only our object's children. If we don't find any cloned snapshots, then we
* simple return that. Otherwise, we have to start at the pool root and iterate
* over all datasets.
*/
static zfs_graph_t *
construct_graph(const char *dataset)
{
/*
* We need to explicitly check whether this dataset has clones or not,
* since iterate_children() only checks the children.
*/
/*
* Determine pool name and try again.
*/
}
}
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 void
{
int i;
/* avoid doing a search if we don't have to */
return;
for (i = 0; i < zgv->zv_edgecount; i++)
/* we may have visited this in the course of the above */
return;
*idx += 1;
}
/*
* 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.
*/
char **
{
char **result;
*count = 0;
/*
* Get rid of the last entry, which is our starting vertex and not
* strictly a dependent.
*/
(*count)--;
return (result);
}