2N/A * The contents of this file are subject to the terms of the 2N/A * Common Development and Distribution License (the "License"). 2N/A * You may not use this file except in compliance with the License. 2N/A * See the License for the specific language governing permissions 2N/A * and limitations under the License. 2N/A * When distributing Covered Code, include this CDDL HEADER in each 2N/A * If applicable, add the following below this CDDL HEADER, with the 2N/A * fields enclosed by brackets "[]" replaced with your own identifying 2N/A * information: Portions Copyright [yyyy] [name of copyright owner] 2N/A * Copyright (c) 2005, 2012, Oracle and/or its affiliates. All rights reserved. 2N/A * Iterate over all children of the current object. This includes the normal 2N/A * dataset hierarchy, but also arbitrary hierarchies due to clones. We want to 2N/A * walk all datasets in the pool, and construct a directed graph of the form: 2N/A * @yesterday ----> foo 2N/A * In order to construct this graph, we have to walk every dataset in the pool, 2N/A * because the clone parent is stored as a property of the child, not the 2N/A * parent. The parent only keeps track of the number of clones. 2N/A * In the normal case (without clones) this would be rather expensive. To avoid 2N/A * unnecessary computation, we first try a walk of the subtree hierarchy 2N/A * starting from the initial node. At each dataset, we construct a node in the 2N/A * graph and an edge leading from its parent. If we don't see any snapshots 2N/A * with a non-zero clone count, then we are finished. 2N/A * If we do find a cloned snapshot, then we finish the walk of the current 2N/A * subtree, but indicate that we need to do a complete walk. We then perform a 2N/A * global walk of all datasets, avoiding the subtree we already processed. 2N/A * At the end of this, we'll end up with a directed graph of all relevant (and 2N/A * possible some irrelevant) datasets in the system. We need to both find our 2N/A * limiting subgraph and determine a safe ordering in which to destroy the 2N/A * datasets. We do a topological ordering of our graph starting at our target 2N/A * dataset, and then walk the results in reverse. 2N/A * It's possible for the graph to have cycles if, for example, the user renames 2N/A * a clone to be the parent of its origin snapshot. The user can request to 2N/A * generate an error in this case, or ignore the cycle and continue. 2N/A * When removing datasets, we want to destroy the snapshots in chronological 2N/A * order (because this is the most efficient method). In order to accomplish 2N/A * this, we store the creation transaction group with each vertex and keep each 2N/A * vertex's edges sorted according to this value. The topological sort will 2N/A * automatically walk the snapshots in the correct order. 2N/A * Vertex structure. Indexed by dataset name, this structure maintains a list 2N/A * of edges to other vertices. 2N/A * Edge structure. Simply maintains a pointer to the destination vertex. There 2N/A * is no need to store the source vertex, since we only use edges in the context 2N/A * of the source vertex. 2N/A * Graph structure. Vertices are maintained in a hash indexed by dataset name. 2N/A * Allocate a new edge pointing to the target vertex. 2N/A * Allocate a new vertex with the given name. 2N/A * Destroy a vertex. Frees up any associated edges. 2N/A * Given a vertex, add an edge to the destination vertex. 2N/A * Sort the given vertex edges according to the creation txg of each vertex. 2N/A * Construct a new graph object. We allow the size to be specified as a 2N/A * parameter so in the future we can size the hash according to the number of 2N/A * datasets in the pool. 2N/A * Destroy a graph object. We have to iterate over all the hash chains, 2N/A * destroying each vertex in the process. 2N/A * Graph hash function. Classic bernstein k=33 hash function, taken from 2N/A * Given a dataset name, finds the associated vertex, creating it if necessary. 2N/A * Given two dataset names, create an edge between them. For the source vertex, 2N/A * mark 'zv_visited' to indicate that we have seen this vertex, and not simply 2N/A * created it as a destination of another edge. If 'dest' is NULL, then this 2N/A * is an individual vertex (i.e. the starting vertex), so don't add an edge. 2N/A * An errno value of ESRCH indicates normal completion. 2N/A * If ENOENT is returned, then the underlying dataset 2N/A * has been removed since we obtained the handle. 2N/A * Iterate over all children of the given dataset, adding any vertices 2N/A * as necessary. Returns -1 if there was an error, or 0 otherwise. 2N/A * This is a simple recursive algorithm - the ZFS namespace typically 2N/A * is very flat. We manually invoke the necessary ioctl() calls to 2N/A * avoid the overhead and additional semantics of zfs_open(). 2N/A * Look up the source vertex, and avoid it if we've seen it before. 2N/A * Iterate over all children 2N/A * Count origins only if they are contained in the graph 2N/A * Add an edge between the parent and the child. 2N/A * Recursively visit child 2N/A * Now iterate over all snapshots. 2N/A * Add an edge between the parent and the child. 2N/A * Now iterate over all shares. 2N/A * Add an edge between the parent and the child. 2N/A * Returns false if there are no snapshots with dependent clones in this 2N/A * subtree or if all of those clones are also in this subtree. Returns 2N/A * true if there is an error or there are external dependents. 2N/A * Check whether this dataset is a clone or has clones since 2N/A * iterate_children() only checks the children. 2N/A * Construct a complete graph of all necessary vertices. First, iterate over 2N/A * only our object's children. If no cloned snapshots are found, or all of 2N/A * the cloned snapshots are in this subtree then return a graph of the subtree. 2N/A * Otherwise, start at the root of the pool and iterate over all datasets. 2N/A * Determine pool name and try again. 2N/A * Given a graph, do a recursive topological sort into the given array. This is 2N/A * really just a depth first search, so that the deepest nodes appear first. 2N/A * hijack the 'zv_visited' marker to avoid visiting the same vertex twice. 2N/A * If we've already seen this vertex as part of our depth-first 2N/A * search, then we have a cyclic dependency, and we must return 2N/A "recursive dependency at '%s'"),
2N/A "cannot determine dependent datasets")));
2N/A * If we've already processed this as part of the topological 2N/A * sort, then don't bother doing so again. 2N/A /* avoid doing a search if we don't have to */ 2N/A /* we may have visited this in the course of the above */ 2N/A * The only public interface for this file. Do the dirty work of constructing a 2N/A * child list for the given object. Construct the graph, do the toplogical 2N/A * sort, and then return the array of strings to the caller. 2N/A * The 'allowrecursion' parameter controls behavior when cycles are found. If 2N/A * it is set, the the cycle is ignored and the results returned as if the cycle 2N/A * did not exist. If it is not set, then the routine will generate an error if 2N/A * Get rid of the last entry, which is our starting vertex and not 2N/A * strictly a dependent.