Print this page
1869 "zfs holds" is O(n^2)

Split Close
Expand all
Collapse all
          --- old/usr/src/cmd/zfs/zfs_main.c
          +++ new/usr/src/cmd/zfs/zfs_main.c
↓ open down ↓ 5354 lines elided ↑ open up ↑
5355 5355   * Release a user-hold with the given tag from the list of snapshots.
5356 5356   */
5357 5357  static int
5358 5358  zfs_do_release(int argc, char **argv)
5359 5359  {
5360 5360          return (zfs_do_hold_rele_impl(argc, argv, B_FALSE));
5361 5361  }
5362 5362  
5363 5363  typedef struct holds_cbdata {
5364 5364          boolean_t       cb_recursive;
5365      -        const char      *cb_snapname;
     5365 +        const char      **cb_snapnames;
     5366 +        char            **cb_argv_filt;
     5367 +        size_t          cb_argc_filt;
     5368 +        size_t          cb_idx;
5366 5369          nvlist_t        **cb_nvlp;
5367 5370          size_t          cb_max_namelen;
5368 5371          size_t          cb_max_taglen;
5369 5372  } holds_cbdata_t;
5370 5373  
5371 5374  #define STRFTIME_FMT_STR "%a %b %e %k:%M %Y"
5372 5375  #define DATETIME_BUF_LEN (32)
5373 5376  /*
5374 5377   *
5375 5378   */
↓ open down ↓ 48 lines elided ↑ open up ↑
5424 5427  static int
5425 5428  holds_callback(zfs_handle_t *zhp, void *data)
5426 5429  {
5427 5430          holds_cbdata_t *cbp = data;
5428 5431          nvlist_t *top_nvl = *cbp->cb_nvlp;
5429 5432          nvlist_t *nvl = NULL;
5430 5433          nvpair_t *nvp = NULL;
5431 5434          const char *zname = zfs_get_name(zhp);
5432 5435          size_t znamelen = strnlen(zname, ZFS_MAXNAMELEN);
5433 5436  
5434      -        if (cbp->cb_recursive) {
5435      -                const char *snapname;
     5437 +        /*
     5438 +         * If not a snapshot then we are running recursive and it
     5439 +         * might be one of the arguments. In this case we have to bump
     5440 +         * the index so we know which snapname to match the
     5441 +         * descendants of this argument against.
     5442 +         *
     5443 +         * In any case we skip this zfs handle because we know it is
     5444 +         * not a hold.
     5445 +         */
     5446 +        if (zfs_get_type(zhp) != ZFS_TYPE_SNAPSHOT) {
     5447 +                if ((cbp->cb_idx < cbp->cb_argc_filt)
     5448 +                    && (strcmp(cbp->cb_argv_filt[cbp->cb_idx], zname) == 0)) {
     5449 +                        cbp->cb_idx++;
     5450 +                }
     5451 +                return (0);
     5452 +        }
     5453 +
     5454 +        if (cbp->cb_recursive == B_TRUE) {
5436 5455                  char *delim  = strchr(zname, '@');
5437      -                if (delim == NULL)
5438      -                        return (0);
     5456 +                const char *snapname = delim + 1;
5439 5457  
5440      -                snapname = delim + 1;
5441      -                if (strcmp(cbp->cb_snapname, snapname))
     5458 +                /*
     5459 +                 * The snapshot name of this descendent doesn't match,
     5460 +                 * skip it.
     5461 +                 */
     5462 +                if (strcmp(cbp->cb_snapnames[cbp->cb_idx - 1], snapname) != 0) {
5442 5463                          return (0);
     5464 +                }
5443 5465          }
5444 5466  
     5467 +        /*
     5468 +         * In this case we know two things are true.
     5469 +         *
     5470 +         * 1. That zhp is a snapshot.
     5471 +         *
     5472 +         * 2. If a recursive listing then zhp is descendent of the
     5473 +         *    user argument with a snapshot name that matches.
     5474 +         *
     5475 +         * In this case, gegrab the holds on the snapshot and add them
     5476 +         * to list.
     5477 +         */
5445 5478          if (zfs_get_holds(zhp, &nvl) != 0)
5446 5479                  return (-1);
5447 5480  
5448 5481          if (znamelen > cbp->cb_max_namelen)
5449 5482                  cbp->cb_max_namelen  = znamelen;
5450 5483  
5451 5484          while ((nvp = nvlist_next_nvpair(nvl, nvp)) != NULL) {
5452 5485                  const char *tag = nvpair_name(nvp);
5453 5486                  size_t taglen = strnlen(tag, MAXNAMELEN);
5454 5487                  if (taglen > cbp->cb_max_taglen)
↓ open down ↓ 6 lines elided ↑ open up ↑
5461 5494  /*
5462 5495   * zfs holds [-r] <snap> ...
5463 5496   *
5464 5497   *      -r      Recursively hold
5465 5498   */
5466 5499  static int
5467 5500  zfs_do_holds(int argc, char **argv)
5468 5501  {
5469 5502          int errors = 0;
5470 5503          int c;
5471      -        int i;
     5504 +        char **argv_filt;
     5505 +        int argc_filt = 0;
     5506 +        const char **snapnames;
5472 5507          boolean_t scripted = B_FALSE;
5473 5508          boolean_t recursive = B_FALSE;
5474 5509          const char *opts = "rH";
5475 5510          nvlist_t *nvl;
5476 5511  
5477 5512          int types = ZFS_TYPE_SNAPSHOT;
5478 5513          holds_cbdata_t cb = { 0 };
5479 5514  
5480 5515          int limit = 0;
5481 5516          int ret = 0;
↓ open down ↓ 8 lines elided ↑ open up ↑
5490 5525                  case 'H':
5491 5526                          scripted = B_TRUE;
5492 5527                          break;
5493 5528                  case '?':
5494 5529                          (void) fprintf(stderr, gettext("invalid option '%c'\n"),
5495 5530                              optopt);
5496 5531                          usage(B_FALSE);
5497 5532                  }
5498 5533          }
5499 5534  
5500      -        if (recursive) {
5501      -                types |= ZFS_TYPE_FILESYSTEM | ZFS_TYPE_VOLUME;
5502      -                flags |= ZFS_ITER_RECURSE;
5503      -        }
5504      -
5505 5535          argc -= optind;
5506 5536          argv += optind;
5507 5537  
5508 5538          /* check number of arguments */
5509 5539          if (argc < 1)
5510 5540                  usage(B_FALSE);
5511 5541  
5512 5542          if (nvlist_alloc(&nvl, NV_UNIQUE_NAME, 0) != 0)
5513 5543                  nomem();
5514 5544  
5515      -        for (i = 0; i < argc; ++i) {
     5545 +        if ((argv_filt = malloc(sizeof (char *) * argc)) == NULL)
     5546 +                nomem();
     5547 +
     5548 +        if ((snapnames = malloc(sizeof (char *) * argc)) == NULL)
     5549 +                nomem();
     5550 +
     5551 +        cb.cb_nvlp = &nvl;
     5552 +        cb.cb_recursive = B_FALSE;
     5553 +        cb.cb_idx = 0;
     5554 +
     5555 +        if (recursive == B_TRUE) {
     5556 +                types |= ZFS_TYPE_FILESYSTEM | ZFS_TYPE_VOLUME;
     5557 +                flags |= ZFS_ITER_RECURSE;
     5558 +                cb.cb_recursive = B_TRUE;
     5559 +                cb.cb_snapnames = malloc(sizeof (char *) * argc);
     5560 +
     5561 +                if (cb.cb_snapnames == NULL)
     5562 +                        nomem();
     5563 +        }
     5564 +
     5565 +        /*
     5566 +         * Filter out non-snapshot arguments. Store pointers to valid
     5567 +         * arguments in argv_filt. The total count of valid arguments
     5568 +         * is stored in argc_filt.
     5569 +         */
     5570 +        for (int i = 0; i < argc; i++) {
5516 5571                  char *snapshot = argv[i];
5517      -                const char *delim;
5518      -                const char *snapname;
     5572 +                const char *delim  = strchr(snapshot, '@');
5519 5573  
5520      -                delim = strchr(snapshot, '@');
5521 5574                  if (delim == NULL) {
5522 5575                          (void) fprintf(stderr,
5523 5576                              gettext("'%s' is not a snapshot\n"), snapshot);
5524 5577                          ++errors;
5525 5578                          continue;
5526 5579                  }
5527      -                snapname = delim + 1;
5528      -                if (recursive)
5529      -                        snapshot[delim - snapshot] = '\0';
5530      -
5531      -                cb.cb_recursive = recursive;
5532      -                cb.cb_snapname = snapname;
5533      -                cb.cb_nvlp = &nvl;
5534 5580  
5535 5581                  /*
5536      -                 *  1. collect holds data, set format options
     5582 +                 * If running a recusive (-r) listing then the
     5583 +                 * arguments to zfs_for_each() must each be stripped
     5584 +                 * of their snapshot suffix. Furthermore, when
     5585 +                 * descending down for a particular argument, only
     5586 +                 * snapshots with the same name as the original
     5587 +                 * argument should be returned. Since we just stripped
     5588 +                 * the snapname from the arguments they need to be
     5589 +                 * kept track of somewhere else. This is the purpose
     5590 +                 * of snapnames. As zfs_for_each() iterates the list
     5591 +                 * the callback uses cb_argv_filt and cb_snapnames to
     5592 +                 * make sure that only descendents of the same
     5593 +                 * snapname are listed.
     5594 +                 *
     5595 +                 * If this is confusing then it only means you are
     5596 +                 * human. The behavior of "zfs holds -r" is very odd.
     5597 +                 *
     5598 +                 * For example, given a filesystem layout like so:
     5599 +                 *
     5600 +                 * rpool/foo
     5601 +                 * rpool/foo@1
     5602 +                 * rpool/foo/bar
     5603 +                 * rpool/foo/bar@1
     5604 +                 * rpool/foo/bar@2
     5605 +                 * rpool/baz
     5606 +                 * rpool/baz@1
     5607 +                 * rpool/baz@2
     5608 +                 * rpool/baz/blah
     5609 +                 * rpool/baz/blah@2
     5610 +                 *
     5611 +                 * "zfs holds -r rpool/foo@1 rpool/baz@2" should list
     5612 +                 * holds for:
     5613 +                 *
     5614 +                 * rpool/foo@1
     5615 +                 * rpool/foo/bar@1
     5616 +                 * rpool/baz@2
     5617 +                 * rpool/baz/blah@2
5537 5618                   */
5538      -                ret = zfs_for_each(argc, argv, flags, types, NULL, NULL, limit,
5539      -                    holds_callback, &cb);
5540      -                if (ret != 0)
5541      -                        ++errors;
     5619 +                if (recursive == B_TRUE) {
     5620 +                        const char *snapname = delim + 1;
     5621 +                        snapshot[delim - snapshot] = '\0';
     5622 +                        snapnames[argc_filt] = snapname;
     5623 +                }
     5624 +
     5625 +                argv_filt[argc_filt++] = snapshot;
5542 5626          }
5543 5627  
     5628 +        if (argc_filt == 0)
     5629 +                return (0 != errors);
     5630 +
     5631 +        cb.cb_argv_filt = argv_filt;
     5632 +        cb.cb_argc_filt = argc_filt;
     5633 +        cb.cb_snapnames = snapnames;
     5634 +
     5635 +        /*
     5636 +         *  1. collect holds data, set format options
     5637 +         */
     5638 +        ret = zfs_for_each(argc_filt, argv_filt, flags, types, NULL, NULL,
     5639 +            limit, holds_callback, &cb);
     5640 +        if (ret != 0)
     5641 +                ++errors;
     5642 +
5544 5643          /*
5545 5644           *  2. print holds data
5546 5645           */
5547 5646          print_holds(scripted, cb.cb_max_namelen, cb.cb_max_taglen, nvl);
5548 5647  
5549 5648          if (nvlist_empty(nvl))
5550 5649                  (void) printf(gettext("no datasets available\n"));
5551 5650  
5552 5651          nvlist_free(nvl);
     5652 +        free(snapnames);
     5653 +        free(argv_filt);
5553 5654  
5554 5655          return (0 != errors);
5555 5656  }
5556 5657  
5557 5658  #define CHECK_SPINNER 30
5558 5659  #define SPINNER_TIME 3          /* seconds */
5559 5660  #define MOUNT_TIME 5            /* seconds */
5560 5661  
5561 5662  static int
5562 5663  get_one_dataset(zfs_handle_t *zhp, void *data)
↓ open down ↓ 1320 lines elided ↑ open up ↑
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX