1 789 ahrens /* 2 789 ahrens * CDDL HEADER START 3 789 ahrens * 4 789 ahrens * The contents of this file are subject to the terms of the 5 1544 eschrock * Common Development and Distribution License (the "License"). 6 1544 eschrock * You may not use this file except in compliance with the License. 7 789 ahrens * 8 789 ahrens * You can obtain a copy of the license at usr/src/OPENSOLARIS.LICENSE 9 789 ahrens * or http://www.opensolaris.org/os/licensing. 10 789 ahrens * See the License for the specific language governing permissions 11 789 ahrens * and limitations under the License. 12 789 ahrens * 13 789 ahrens * When distributing Covered Code, include this CDDL HEADER in each 14 789 ahrens * file and include the License file at usr/src/OPENSOLARIS.LICENSE. 15 789 ahrens * If applicable, add the following below this CDDL HEADER, with the 16 789 ahrens * fields enclosed by brackets "[]" replaced with your own identifying 17 789 ahrens * information: Portions Copyright [yyyy] [name of copyright owner] 18 789 ahrens * 19 789 ahrens * CDDL HEADER END 20 789 ahrens */ 21 789 ahrens /* 22 9396 Matthew * Copyright 2009 Sun Microsystems, Inc. All rights reserved. 23 789 ahrens * Use is subject to license terms. 24 789 ahrens */ 25 789 ahrens 26 789 ahrens /* 27 789 ahrens * Iterate over all children of the current object. This includes the normal 28 789 ahrens * dataset hierarchy, but also arbitrary hierarchies due to clones. We want to 29 789 ahrens * walk all datasets in the pool, and construct a directed graph of the form: 30 789 ahrens * 31 789 ahrens * home 32 789 ahrens * | 33 789 ahrens * +----+----+ 34 789 ahrens * | | 35 789 ahrens * v v ws 36 789 ahrens * bar baz | 37 789 ahrens * | | 38 789 ahrens * v v 39 789 ahrens * @yesterday ----> foo 40 789 ahrens * 41 789 ahrens * In order to construct this graph, we have to walk every dataset in the pool, 42 789 ahrens * because the clone parent is stored as a property of the child, not the 43 789 ahrens * parent. The parent only keeps track of the number of clones. 44 789 ahrens * 45 789 ahrens * In the normal case (without clones) this would be rather expensive. To avoid 46 789 ahrens * unnecessary computation, we first try a walk of the subtree hierarchy 47 789 ahrens * starting from the initial node. At each dataset, we construct a node in the 48 789 ahrens * graph and an edge leading from its parent. If we don't see any snapshots 49 789 ahrens * with a non-zero clone count, then we are finished. 50 789 ahrens * 51 789 ahrens * If we do find a cloned snapshot, then we finish the walk of the current 52 789 ahrens * subtree, but indicate that we need to do a complete walk. We then perform a 53 789 ahrens * global walk of all datasets, avoiding the subtree we already processed. 54 789 ahrens * 55 789 ahrens * At the end of this, we'll end up with a directed graph of all relevant (and 56 789 ahrens * possible some irrelevant) datasets in the system. We need to both find our 57 789 ahrens * limiting subgraph and determine a safe ordering in which to destroy the 58 789 ahrens * datasets. We do a topological ordering of our graph starting at our target 59 789 ahrens * dataset, and then walk the results in reverse. 60 789 ahrens * 61 2474 eschrock * It's possible for the graph to have cycles if, for example, the user renames 62 2474 eschrock * a clone to be the parent of its origin snapshot. The user can request to 63 2474 eschrock * generate an error in this case, or ignore the cycle and continue. 64 2474 eschrock * 65 789 ahrens * When removing datasets, we want to destroy the snapshots in chronological 66 789 ahrens * order (because this is the most efficient method). In order to accomplish 67 789 ahrens * this, we store the creation transaction group with each vertex and keep each 68 789 ahrens * vertex's edges sorted according to this value. The topological sort will 69 789 ahrens * automatically walk the snapshots in the correct order. 70 789 ahrens */ 71 789 ahrens 72 789 ahrens #include <assert.h> 73 2474 eschrock #include <libintl.h> 74 789 ahrens #include <stdio.h> 75 789 ahrens #include <stdlib.h> 76 789 ahrens #include <string.h> 77 789 ahrens #include <strings.h> 78 789 ahrens #include <unistd.h> 79 789 ahrens 80 789 ahrens #include <libzfs.h> 81 789 ahrens 82 789 ahrens #include "libzfs_impl.h" 83 789 ahrens #include "zfs_namecheck.h" 84 789 ahrens 85 789 ahrens #define MIN_EDGECOUNT 4 86 789 ahrens 87 789 ahrens /* 88 789 ahrens * Vertex structure. Indexed by dataset name, this structure maintains a list 89 789 ahrens * of edges to other vertices. 90 789 ahrens */ 91 789 ahrens struct zfs_edge; 92 789 ahrens typedef struct zfs_vertex { 93 789 ahrens char zv_dataset[ZFS_MAXNAMELEN]; 94 789 ahrens struct zfs_vertex *zv_next; 95 789 ahrens int zv_visited; 96 789 ahrens uint64_t zv_txg; 97 789 ahrens struct zfs_edge **zv_edges; 98 789 ahrens int zv_edgecount; 99 789 ahrens int zv_edgealloc; 100 789 ahrens } zfs_vertex_t; 101 2474 eschrock 102 2474 eschrock enum { 103 2474 eschrock VISIT_SEEN = 1, 104 2474 eschrock VISIT_SORT_PRE, 105 2474 eschrock VISIT_SORT_POST 106 2474 eschrock }; 107 789 ahrens 108 789 ahrens /* 109 789 ahrens * Edge structure. Simply maintains a pointer to the destination vertex. There 110 789 ahrens * is no need to store the source vertex, since we only use edges in the context 111 789 ahrens * of the source vertex. 112 789 ahrens */ 113 789 ahrens typedef struct zfs_edge { 114 789 ahrens zfs_vertex_t *ze_dest; 115 789 ahrens struct zfs_edge *ze_next; 116 789 ahrens } zfs_edge_t; 117 789 ahrens 118 789 ahrens #define ZFS_GRAPH_SIZE 1027 /* this could be dynamic some day */ 119 789 ahrens 120 789 ahrens /* 121 789 ahrens * Graph structure. Vertices are maintained in a hash indexed by dataset name. 122 789 ahrens */ 123 789 ahrens typedef struct zfs_graph { 124 789 ahrens zfs_vertex_t **zg_hash; 125 789 ahrens size_t zg_size; 126 789 ahrens size_t zg_nvertex; 127 6027 rm160521 const char *zg_root; 128 6027 rm160521 int zg_clone_count; 129 789 ahrens } zfs_graph_t; 130 789 ahrens 131 789 ahrens /* 132 789 ahrens * Allocate a new edge pointing to the target vertex. 133 789 ahrens */ 134 789 ahrens static zfs_edge_t * 135 2082 eschrock zfs_edge_create(libzfs_handle_t *hdl, zfs_vertex_t *dest) 136 789 ahrens { 137 2082 eschrock zfs_edge_t *zep = zfs_alloc(hdl, sizeof (zfs_edge_t)); 138 2082 eschrock 139 2082 eschrock if (zep == NULL) 140 2082 eschrock return (NULL); 141 789 ahrens 142 789 ahrens zep->ze_dest = dest; 143 789 ahrens 144 789 ahrens return (zep); 145 789 ahrens } 146 789 ahrens 147 789 ahrens /* 148 789 ahrens * Destroy an edge. 149 789 ahrens */ 150 789 ahrens static void 151 789 ahrens zfs_edge_destroy(zfs_edge_t *zep) 152 789 ahrens { 153 789 ahrens free(zep); 154 789 ahrens } 155 789 ahrens 156 789 ahrens /* 157 789 ahrens * Allocate a new vertex with the given name. 158 789 ahrens */ 159 789 ahrens static zfs_vertex_t * 160 2082 eschrock zfs_vertex_create(libzfs_handle_t *hdl, const char *dataset) 161 789 ahrens { 162 2082 eschrock zfs_vertex_t *zvp = zfs_alloc(hdl, sizeof (zfs_vertex_t)); 163 2082 eschrock 164 2082 eschrock if (zvp == NULL) 165 2082 eschrock return (NULL); 166 789 ahrens 167 789 ahrens assert(strlen(dataset) < ZFS_MAXNAMELEN); 168 789 ahrens 169 789 ahrens (void) strlcpy(zvp->zv_dataset, dataset, sizeof (zvp->zv_dataset)); 170 789 ahrens 171 2082 eschrock if ((zvp->zv_edges = zfs_alloc(hdl, 172 2082 eschrock MIN_EDGECOUNT * sizeof (void *))) == NULL) { 173 2082 eschrock free(zvp); 174 2082 eschrock return (NULL); 175 2082 eschrock } 176 2082 eschrock 177 789 ahrens zvp->zv_edgealloc = MIN_EDGECOUNT; 178 789 ahrens 179 789 ahrens return (zvp); 180 789 ahrens } 181 789 ahrens 182 789 ahrens /* 183 789 ahrens * Destroy a vertex. Frees up any associated edges. 184 789 ahrens */ 185 789 ahrens static void 186 789 ahrens zfs_vertex_destroy(zfs_vertex_t *zvp) 187 789 ahrens { 188 789 ahrens int i; 189 789 ahrens 190 789 ahrens for (i = 0; i < zvp->zv_edgecount; i++) 191 789 ahrens zfs_edge_destroy(zvp->zv_edges[i]); 192 789 ahrens 193 789 ahrens free(zvp->zv_edges); 194 789 ahrens free(zvp); 195 789 ahrens } 196 789 ahrens 197 789 ahrens /* 198 789 ahrens * Given a vertex, add an edge to the destination vertex. 199 789 ahrens */ 200 2082 eschrock static int 201 2082 eschrock zfs_vertex_add_edge(libzfs_handle_t *hdl, zfs_vertex_t *zvp, 202 2082 eschrock zfs_vertex_t *dest) 203 789 ahrens { 204 2082 eschrock zfs_edge_t *zep = zfs_edge_create(hdl, dest); 205 2082 eschrock 206 2082 eschrock if (zep == NULL) 207 2082 eschrock return (-1); 208 789 ahrens 209 789 ahrens if (zvp->zv_edgecount == zvp->zv_edgealloc) { 210 2676 eschrock void *ptr; 211 2082 eschrock 212 2676 eschrock if ((ptr = zfs_realloc(hdl, zvp->zv_edges, 213 2676 eschrock zvp->zv_edgealloc * sizeof (void *), 214 2676 eschrock zvp->zv_edgealloc * 2 * sizeof (void *))) == NULL) 215 2082 eschrock return (-1); 216 789 ahrens 217 2676 eschrock zvp->zv_edges = ptr; 218 789 ahrens zvp->zv_edgealloc *= 2; 219 789 ahrens } 220 789 ahrens 221 789 ahrens zvp->zv_edges[zvp->zv_edgecount++] = zep; 222 2082 eschrock 223 2082 eschrock return (0); 224 789 ahrens } 225 789 ahrens 226 789 ahrens static int 227 789 ahrens zfs_edge_compare(const void *a, const void *b) 228 789 ahrens { 229 789 ahrens const zfs_edge_t *ea = *((zfs_edge_t **)a); 230 789 ahrens const zfs_edge_t *eb = *((zfs_edge_t **)b); 231 789 ahrens 232 789 ahrens if (ea->ze_dest->zv_txg < eb->ze_dest->zv_txg) 233 789 ahrens return (-1); 234 789 ahrens if (ea->ze_dest->zv_txg > eb->ze_dest->zv_txg) 235 789 ahrens return (1); 236 789 ahrens return (0); 237 789 ahrens } 238 789 ahrens 239 789 ahrens /* 240 789 ahrens * Sort the given vertex edges according to the creation txg of each vertex. 241 789 ahrens */ 242 789 ahrens static void 243 789 ahrens zfs_vertex_sort_edges(zfs_vertex_t *zvp) 244 789 ahrens { 245 789 ahrens if (zvp->zv_edgecount == 0) 246 789 ahrens return; 247 789 ahrens 248 789 ahrens qsort(zvp->zv_edges, zvp->zv_edgecount, sizeof (void *), 249 789 ahrens zfs_edge_compare); 250 789 ahrens } 251 789 ahrens 252 789 ahrens /* 253 789 ahrens * Construct a new graph object. We allow the size to be specified as a 254 789 ahrens * parameter so in the future we can size the hash according to the number of 255 789 ahrens * datasets in the pool. 256 789 ahrens */ 257 789 ahrens static zfs_graph_t * 258 6027 rm160521 zfs_graph_create(libzfs_handle_t *hdl, const char *dataset, size_t size) 259 789 ahrens { 260 2082 eschrock zfs_graph_t *zgp = zfs_alloc(hdl, sizeof (zfs_graph_t)); 261 2082 eschrock 262 2082 eschrock if (zgp == NULL) 263 2082 eschrock return (NULL); 264 789 ahrens 265 789 ahrens zgp->zg_size = size; 266 2082 eschrock if ((zgp->zg_hash = zfs_alloc(hdl, 267 2082 eschrock size * sizeof (zfs_vertex_t *))) == NULL) { 268 2082 eschrock free(zgp); 269 2082 eschrock return (NULL); 270 2082 eschrock } 271 6027 rm160521 272 6027 rm160521 zgp->zg_root = dataset; 273 6027 rm160521 zgp->zg_clone_count = 0; 274 789 ahrens 275 789 ahrens return (zgp); 276 789 ahrens } 277 789 ahrens 278 789 ahrens /* 279 789 ahrens * Destroy a graph object. We have to iterate over all the hash chains, 280 789 ahrens * destroying each vertex in the process. 281 789 ahrens */ 282 789 ahrens static void 283 789 ahrens zfs_graph_destroy(zfs_graph_t *zgp) 284 789 ahrens { 285 789 ahrens int i; 286 789 ahrens zfs_vertex_t *current, *next; 287 789 ahrens 288 789 ahrens for (i = 0; i < zgp->zg_size; i++) { 289 789 ahrens current = zgp->zg_hash[i]; 290 789 ahrens while (current != NULL) { 291 789 ahrens next = current->zv_next; 292 789 ahrens zfs_vertex_destroy(current); 293 789 ahrens current = next; 294 789 ahrens } 295 789 ahrens } 296 789 ahrens 297 789 ahrens free(zgp->zg_hash); 298 789 ahrens free(zgp); 299 789 ahrens } 300 789 ahrens 301 789 ahrens /* 302 789 ahrens * Graph hash function. Classic bernstein k=33 hash function, taken from 303 789 ahrens * usr/src/cmd/sgs/tools/common/strhash.c 304 789 ahrens */ 305 789 ahrens static size_t 306 789 ahrens zfs_graph_hash(zfs_graph_t *zgp, const char *str) 307 789 ahrens { 308 789 ahrens size_t hash = 5381; 309 789 ahrens int c; 310 789 ahrens 311 789 ahrens while ((c = *str++) != 0) 312 789 ahrens hash = ((hash << 5) + hash) + c; /* hash * 33 + c */ 313 789 ahrens 314 789 ahrens return (hash % zgp->zg_size); 315 789 ahrens } 316 789 ahrens 317 789 ahrens /* 318 789 ahrens * Given a dataset name, finds the associated vertex, creating it if necessary. 319 789 ahrens */ 320 789 ahrens static zfs_vertex_t * 321 2082 eschrock zfs_graph_lookup(libzfs_handle_t *hdl, zfs_graph_t *zgp, const char *dataset, 322 2082 eschrock uint64_t txg) 323 789 ahrens { 324 789 ahrens size_t idx = zfs_graph_hash(zgp, dataset); 325 789 ahrens zfs_vertex_t *zvp; 326 789 ahrens 327 789 ahrens for (zvp = zgp->zg_hash[idx]; zvp != NULL; zvp = zvp->zv_next) { 328 789 ahrens if (strcmp(zvp->zv_dataset, dataset) == 0) { 329 789 ahrens if (zvp->zv_txg == 0) 330 789 ahrens zvp->zv_txg = txg; 331 789 ahrens return (zvp); 332 789 ahrens } 333 789 ahrens } 334 789 ahrens 335 2082 eschrock if ((zvp = zfs_vertex_create(hdl, dataset)) == NULL) 336 2082 eschrock return (NULL); 337 2082 eschrock 338 789 ahrens zvp->zv_next = zgp->zg_hash[idx]; 339 789 ahrens zvp->zv_txg = txg; 340 789 ahrens zgp->zg_hash[idx] = zvp; 341 789 ahrens zgp->zg_nvertex++; 342 789 ahrens 343 789 ahrens return (zvp); 344 789 ahrens } 345 789 ahrens 346 789 ahrens /* 347 789 ahrens * Given two dataset names, create an edge between them. For the source vertex, 348 789 ahrens * mark 'zv_visited' to indicate that we have seen this vertex, and not simply 349 789 ahrens * created it as a destination of another edge. If 'dest' is NULL, then this 350 789 ahrens * is an individual vertex (i.e. the starting vertex), so don't add an edge. 351 789 ahrens */ 352 2082 eschrock static int 353 2082 eschrock zfs_graph_add(libzfs_handle_t *hdl, zfs_graph_t *zgp, const char *source, 354 2082 eschrock const char *dest, uint64_t txg) 355 789 ahrens { 356 789 ahrens zfs_vertex_t *svp, *dvp; 357 789 ahrens 358 2082 eschrock if ((svp = zfs_graph_lookup(hdl, zgp, source, 0)) == NULL) 359 2082 eschrock return (-1); 360 2474 eschrock svp->zv_visited = VISIT_SEEN; 361 789 ahrens if (dest != NULL) { 362 2082 eschrock dvp = zfs_graph_lookup(hdl, zgp, dest, txg); 363 2082 eschrock if (dvp == NULL) 364 2082 eschrock return (-1); 365 2082 eschrock if (zfs_vertex_add_edge(hdl, svp, dvp) != 0) 366 2082 eschrock return (-1); 367 789 ahrens } 368 2082 eschrock 369 2082 eschrock return (0); 370 789 ahrens } 371 789 ahrens 372 789 ahrens /* 373 6027 rm160521 * Iterate over all children of the given dataset, adding any vertices 374 6027 rm160521 * as necessary. Returns -1 if there was an error, or 0 otherwise. 375 6027 rm160521 * This is a simple recursive algorithm - the ZFS namespace typically 376 6027 rm160521 * is very flat. We manually invoke the necessary ioctl() calls to 377 6027 rm160521 * avoid the overhead and additional semantics of zfs_open(). 378 789 ahrens */ 379 789 ahrens static int 380 2082 eschrock iterate_children(libzfs_handle_t *hdl, zfs_graph_t *zgp, const char *dataset) 381 789 ahrens { 382 789 ahrens zfs_cmd_t zc = { 0 }; 383 789 ahrens zfs_vertex_t *zvp; 384 789 ahrens 385 789 ahrens /* 386 789 ahrens * Look up the source vertex, and avoid it if we've seen it before. 387 789 ahrens */ 388 2082 eschrock zvp = zfs_graph_lookup(hdl, zgp, dataset, 0); 389 2082 eschrock if (zvp == NULL) 390 2082 eschrock return (-1); 391 2474 eschrock if (zvp->zv_visited == VISIT_SEEN) 392 789 ahrens return (0); 393 2474 eschrock 394 2474 eschrock /* 395 6027 rm160521 * Iterate over all children 396 2474 eschrock */ 397 789 ahrens for ((void) strlcpy(zc.zc_name, dataset, sizeof (zc.zc_name)); 398 2082 eschrock ioctl(hdl->libzfs_fd, ZFS_IOC_DATASET_LIST_NEXT, &zc) == 0; 399 789 ahrens (void) strlcpy(zc.zc_name, dataset, sizeof (zc.zc_name))) { 400 789 ahrens /* 401 789 ahrens * Get statistics for this dataset, to determine the type of the 402 789 ahrens * dataset and clone statistics. If this fails, the dataset has 403 789 ahrens * since been removed, and we're pretty much screwed anyway. 404 789 ahrens */ 405 6027 rm160521 zc.zc_objset_stats.dds_origin[0] = '\0'; 406 2082 eschrock if (ioctl(hdl->libzfs_fd, ZFS_IOC_OBJSET_STATS, &zc) != 0) 407 789 ahrens continue; 408 6027 rm160521 409 6027 rm160521 if (zc.zc_objset_stats.dds_origin[0] != '\0') { 410 6027 rm160521 if (zfs_graph_add(hdl, zgp, 411 6027 rm160521 zc.zc_objset_stats.dds_origin, zc.zc_name, 412 6027 rm160521 zc.zc_objset_stats.dds_creation_txg) != 0) 413 6027 rm160521 return (-1); 414 6027 rm160521 /* 415 6027 rm160521 * Count origins only if they are contained in the graph 416 6027 rm160521 */ 417 6027 rm160521 if (isa_child_of(zc.zc_objset_stats.dds_origin, 418 6027 rm160521 zgp->zg_root)) 419 6027 rm160521 zgp->zg_clone_count--; 420 6027 rm160521 } 421 789 ahrens 422 789 ahrens /* 423 789 ahrens * Add an edge between the parent and the child. 424 789 ahrens */ 425 2082 eschrock if (zfs_graph_add(hdl, zgp, dataset, zc.zc_name, 426 2082 eschrock zc.zc_objset_stats.dds_creation_txg) != 0) 427 2082 eschrock return (-1); 428 789 ahrens 429 789 ahrens /* 430 6027 rm160521 * Recursively visit child 431 789 ahrens */ 432 6027 rm160521 if (iterate_children(hdl, zgp, zc.zc_name)) 433 2082 eschrock return (-1); 434 789 ahrens } 435 789 ahrens 436 789 ahrens /* 437 789 ahrens * Now iterate over all snapshots. 438 789 ahrens */ 439 789 ahrens bzero(&zc, sizeof (zc)); 440 789 ahrens 441 789 ahrens for ((void) strlcpy(zc.zc_name, dataset, sizeof (zc.zc_name)); 442 2082 eschrock ioctl(hdl->libzfs_fd, ZFS_IOC_SNAPSHOT_LIST_NEXT, &zc) == 0; 443 789 ahrens (void) strlcpy(zc.zc_name, dataset, sizeof (zc.zc_name))) { 444 789 ahrens 445 789 ahrens /* 446 789 ahrens * Get statistics for this dataset, to determine the type of the 447 789 ahrens * dataset and clone statistics. If this fails, the dataset has 448 789 ahrens * since been removed, and we're pretty much screwed anyway. 449 789 ahrens */ 450 2082 eschrock if (ioctl(hdl->libzfs_fd, ZFS_IOC_OBJSET_STATS, &zc) != 0) 451 789 ahrens continue; 452 789 ahrens 453 789 ahrens /* 454 789 ahrens * Add an edge between the parent and the child. 455 789 ahrens */ 456 2082 eschrock if (zfs_graph_add(hdl, zgp, dataset, zc.zc_name, 457 2082 eschrock zc.zc_objset_stats.dds_creation_txg) != 0) 458 2082 eschrock return (-1); 459 789 ahrens 460 6027 rm160521 zgp->zg_clone_count += zc.zc_objset_stats.dds_num_clones; 461 789 ahrens } 462 789 ahrens 463 2474 eschrock zvp->zv_visited = VISIT_SEEN; 464 789 ahrens 465 6027 rm160521 return (0); 466 789 ahrens } 467 789 ahrens 468 789 ahrens /* 469 6027 rm160521 * Returns false if there are no snapshots with dependent clones in this 470 6027 rm160521 * subtree or if all of those clones are also in this subtree. Returns 471 6027 rm160521 * true if there is an error or there are external dependents. 472 6027 rm160521 */ 473 6027 rm160521 static boolean_t 474 6027 rm160521 external_dependents(libzfs_handle_t *hdl, zfs_graph_t *zgp, const char *dataset) 475 6027 rm160521 { 476 6027 rm160521 zfs_cmd_t zc = { 0 }; 477 6027 rm160521 478 6027 rm160521 /* 479 6027 rm160521 * Check whether this dataset is a clone or has clones since 480 6027 rm160521 * iterate_children() only checks the children. 481 6027 rm160521 */ 482 6027 rm160521 (void) strlcpy(zc.zc_name, dataset, sizeof (zc.zc_name)); 483 6027 rm160521 if (ioctl(hdl->libzfs_fd, ZFS_IOC_OBJSET_STATS, &zc) != 0) 484 6027 rm160521 return (B_TRUE); 485 6027 rm160521 486 6027 rm160521 if (zc.zc_objset_stats.dds_origin[0] != '\0') { 487 6027 rm160521 if (zfs_graph_add(hdl, zgp, 488 6027 rm160521 zc.zc_objset_stats.dds_origin, zc.zc_name, 489 6027 rm160521 zc.zc_objset_stats.dds_creation_txg) != 0) 490 6027 rm160521 return (B_TRUE); 491 6027 rm160521 if (isa_child_of(zc.zc_objset_stats.dds_origin, dataset)) 492 6027 rm160521 zgp->zg_clone_count--; 493 6027 rm160521 } 494 6027 rm160521 495 6027 rm160521 if ((zc.zc_objset_stats.dds_num_clones) || 496 6027 rm160521 iterate_children(hdl, zgp, dataset)) 497 6027 rm160521 return (B_TRUE); 498 6027 rm160521 499 6027 rm160521 return (zgp->zg_clone_count != 0); 500 6027 rm160521 } 501 6027 rm160521 502 6027 rm160521 /* 503 6027 rm160521 * Construct a complete graph of all necessary vertices. First, iterate over 504 6027 rm160521 * only our object's children. If no cloned snapshots are found, or all of 505 6027 rm160521 * the cloned snapshots are in this subtree then return a graph of the subtree. 506 6027 rm160521 * Otherwise, start at the root of the pool and iterate over all datasets. 507 789 ahrens */ 508 789 ahrens static zfs_graph_t * 509 2082 eschrock construct_graph(libzfs_handle_t *hdl, const char *dataset) 510 789 ahrens { 511 6027 rm160521 zfs_graph_t *zgp = zfs_graph_create(hdl, dataset, ZFS_GRAPH_SIZE); 512 2082 eschrock int ret = 0; 513 2082 eschrock 514 2082 eschrock if (zgp == NULL) 515 2082 eschrock return (zgp); 516 789 ahrens 517 6027 rm160521 if ((strchr(dataset, '/') == NULL) || 518 6027 rm160521 (external_dependents(hdl, zgp, dataset))) { 519 789 ahrens /* 520 789 ahrens * Determine pool name and try again. 521 789 ahrens */ 522 6148 rm160521 int len = strcspn(dataset, "/@") + 1; 523 6148 rm160521 char *pool = zfs_alloc(hdl, len); 524 789 ahrens 525 6148 rm160521 if (pool == NULL) { 526 6148 rm160521 zfs_graph_destroy(zgp); 527 6148 rm160521 return (NULL); 528 6148 rm160521 } 529 6148 rm160521 (void) strlcpy(pool, dataset, len); 530 789 ahrens 531 6148 rm160521 if (iterate_children(hdl, zgp, pool) == -1 || 532 6148 rm160521 zfs_graph_add(hdl, zgp, pool, NULL, 0) != 0) { 533 789 ahrens free(pool); 534 6148 rm160521 zfs_graph_destroy(zgp); 535 6148 rm160521 return (NULL); 536 789 ahrens } 537 6148 rm160521 free(pool); 538 789 ahrens } 539 2082 eschrock 540 2082 eschrock if (ret == -1 || zfs_graph_add(hdl, zgp, dataset, NULL, 0) != 0) { 541 2082 eschrock zfs_graph_destroy(zgp); 542 2082 eschrock return (NULL); 543 2082 eschrock } 544 789 ahrens 545 789 ahrens return (zgp); 546 789 ahrens } 547 789 ahrens 548 789 ahrens /* 549 789 ahrens * Given a graph, do a recursive topological sort into the given array. This is 550 789 ahrens * really just a depth first search, so that the deepest nodes appear first. 551 789 ahrens * hijack the 'zv_visited' marker to avoid visiting the same vertex twice. 552 789 ahrens */ 553 2082 eschrock static int 554 2474 eschrock topo_sort(libzfs_handle_t *hdl, boolean_t allowrecursion, char **result, 555 2474 eschrock size_t *idx, zfs_vertex_t *zgv) 556 789 ahrens { 557 789 ahrens int i; 558 789 ahrens 559 2474 eschrock if (zgv->zv_visited == VISIT_SORT_PRE && !allowrecursion) { 560 2474 eschrock /* 561 2474 eschrock * If we've already seen this vertex as part of our depth-first 562 2474 eschrock * search, then we have a cyclic dependency, and we must return 563 2474 eschrock * an error. 564 2474 eschrock */ 565 2474 eschrock zfs_error_aux(hdl, dgettext(TEXT_DOMAIN, 566 2474 eschrock "recursive dependency at '%s'"), 567 2474 eschrock zgv->zv_dataset); 568 2474 eschrock return (zfs_error(hdl, EZFS_RECURSIVE, 569 2474 eschrock dgettext(TEXT_DOMAIN, 570 2474 eschrock "cannot determine dependent datasets"))); 571 2474 eschrock } else if (zgv->zv_visited >= VISIT_SORT_PRE) { 572 2474 eschrock /* 573 2474 eschrock * If we've already processed this as part of the topological 574 2474 eschrock * sort, then don't bother doing so again. 575 2474 eschrock */ 576 2474 eschrock return (0); 577 2474 eschrock } 578 2474 eschrock 579 2474 eschrock zgv->zv_visited = VISIT_SORT_PRE; 580 2474 eschrock 581 789 ahrens /* avoid doing a search if we don't have to */ 582 789 ahrens zfs_vertex_sort_edges(zgv); 583 2082 eschrock for (i = 0; i < zgv->zv_edgecount; i++) { 584 2474 eschrock if (topo_sort(hdl, allowrecursion, result, idx, 585 2474 eschrock zgv->zv_edges[i]->ze_dest) != 0) 586 2082 eschrock return (-1); 587 2082 eschrock } 588 789 ahrens 589 789 ahrens /* we may have visited this in the course of the above */ 590 2474 eschrock if (zgv->zv_visited == VISIT_SORT_POST) 591 2082 eschrock return (0); 592 789 ahrens 593 2082 eschrock if ((result[*idx] = zfs_alloc(hdl, 594 2082 eschrock strlen(zgv->zv_dataset) + 1)) == NULL) 595 2082 eschrock return (-1); 596 2082 eschrock 597 789 ahrens (void) strcpy(result[*idx], zgv->zv_dataset); 598 789 ahrens *idx += 1; 599 2474 eschrock zgv->zv_visited = VISIT_SORT_POST; 600 2082 eschrock return (0); 601 789 ahrens } 602 789 ahrens 603 789 ahrens /* 604 789 ahrens * The only public interface for this file. Do the dirty work of constructing a 605 789 ahrens * child list for the given object. Construct the graph, do the toplogical 606 789 ahrens * sort, and then return the array of strings to the caller. 607 2474 eschrock * 608 2474 eschrock * The 'allowrecursion' parameter controls behavior when cycles are found. If 609 2474 eschrock * it is set, the the cycle is ignored and the results returned as if the cycle 610 2474 eschrock * did not exist. If it is not set, then the routine will generate an error if 611 2474 eschrock * a cycle is found. 612 789 ahrens */ 613 2474 eschrock int 614 2474 eschrock get_dependents(libzfs_handle_t *hdl, boolean_t allowrecursion, 615 2474 eschrock const char *dataset, char ***result, size_t *count) 616 789 ahrens { 617 789 ahrens zfs_graph_t *zgp; 618 789 ahrens zfs_vertex_t *zvp; 619 789 ahrens 620 2082 eschrock if ((zgp = construct_graph(hdl, dataset)) == NULL) 621 2474 eschrock return (-1); 622 789 ahrens 623 2474 eschrock if ((*result = zfs_alloc(hdl, 624 2082 eschrock zgp->zg_nvertex * sizeof (char *))) == NULL) { 625 2082 eschrock zfs_graph_destroy(zgp); 626 2474 eschrock return (-1); 627 2082 eschrock } 628 2082 eschrock 629 2082 eschrock if ((zvp = zfs_graph_lookup(hdl, zgp, dataset, 0)) == NULL) { 630 2474 eschrock free(*result); 631 2082 eschrock zfs_graph_destroy(zgp); 632 2474 eschrock return (-1); 633 2082 eschrock } 634 789 ahrens 635 789 ahrens *count = 0; 636 2474 eschrock if (topo_sort(hdl, allowrecursion, *result, count, zvp) != 0) { 637 2474 eschrock free(*result); 638 2082 eschrock zfs_graph_destroy(zgp); 639 2474 eschrock return (-1); 640 2082 eschrock } 641 789 ahrens 642 789 ahrens /* 643 789 ahrens * Get rid of the last entry, which is our starting vertex and not 644 789 ahrens * strictly a dependent. 645 789 ahrens */ 646 789 ahrens assert(*count > 0); 647 2474 eschrock free((*result)[*count - 1]); 648 789 ahrens (*count)--; 649 789 ahrens 650 789 ahrens zfs_graph_destroy(zgp); 651 789 ahrens 652 2474 eschrock return (0); 653 789 ahrens } 654
Indexes created Thu Nov 26 06:23:54 UTC 2009
Terms of Use |
Privacy |
Trademarks |
Copyright Policy |
Site Guidelines |
Help
Your use of this web site or any of its content or software indicates your agreement to be bound by these Terms of Use.
Copyright © 1995-2008 Sun Microsystems, Inc.