From owner-svn-src-all@freebsd.org Wed Mar 8 13:39:23 2017 Return-Path: Delivered-To: svn-src-all@mailman.ysv.freebsd.org Received: from mx1.freebsd.org (mx1.freebsd.org [IPv6:2001:1900:2254:206a::19:1]) by mailman.ysv.freebsd.org (Postfix) with ESMTP id 7C19ECFBD8F; Wed, 8 Mar 2017 13:39:23 +0000 (UTC) (envelope-from avg@FreeBSD.org) Received: from repo.freebsd.org (repo.freebsd.org [IPv6:2610:1c1:1:6068::e6a:0]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (Client did not present a certificate) by mx1.freebsd.org (Postfix) with ESMTPS id 2F5F31D7F; Wed, 8 Mar 2017 13:39:23 +0000 (UTC) (envelope-from avg@FreeBSD.org) Received: from repo.freebsd.org ([127.0.1.37]) by repo.freebsd.org (8.15.2/8.15.2) with ESMTP id v28DdMs8064074; Wed, 8 Mar 2017 13:39:22 GMT (envelope-from avg@FreeBSD.org) Received: (from avg@localhost) by repo.freebsd.org (8.15.2/8.15.2/Submit) id v28DdMHB064073; Wed, 8 Mar 2017 13:39:22 GMT (envelope-from avg@FreeBSD.org) Message-Id: <201703081339.v28DdMHB064073@repo.freebsd.org> X-Authentication-Warning: repo.freebsd.org: avg set sender to avg@FreeBSD.org using -f From: Andriy Gapon Date: Wed, 8 Mar 2017 13:39:22 +0000 (UTC) To: src-committers@freebsd.org, svn-src-all@freebsd.org, svn-src-vendor@freebsd.org Subject: svn commit: r314910 - vendor-sys/illumos/dist/uts/common/fs/zfs X-SVN-Group: vendor-sys MIME-Version: 1.0 Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: 8bit X-BeenThere: svn-src-all@freebsd.org X-Mailman-Version: 2.1.23 Precedence: list List-Id: "SVN commit messages for the entire src tree \(except for " user" and " projects" \)" List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Wed, 08 Mar 2017 13:39:23 -0000 Author: avg Date: Wed Mar 8 13:39:22 2017 New Revision: 314910 URL: https://svnweb.freebsd.org/changeset/base/314910 Log: 7843 get_clones_stat() is suboptimal for lots of clones illumos/illumos-gate@c5bde7273ef861a8dc54cfb9abe48d56062177da https://github.com/illumos/illumos-gate/commit/c5bde7273ef861a8dc54cfb9abe48d56062177da https://www.illumos.org/issues/7843 get_clones_stat() could be very slow if a snapshot has many (thousands) clones. Clone names are added to an nvlist that's created with NV_UNIQUE_NAME. So, each time a new name is appended to the list, the whole list is searched linearly to see if that name is not already in the list. That results in the quadratic complexity. That should be easy to fix as we know in advance that we should not get any duplicate names, so we can drop NV_UNIQUE_NAME when creating the list. Reviewed by: Pavel Zakharov Reviewed by: Matthew Ahrens Approved by: Dan McDonald Author: Andriy Gapon Modified: vendor-sys/illumos/dist/uts/common/fs/zfs/dsl_dataset.c Modified: vendor-sys/illumos/dist/uts/common/fs/zfs/dsl_dataset.c ============================================================================== --- vendor-sys/illumos/dist/uts/common/fs/zfs/dsl_dataset.c Wed Mar 8 13:09:12 2017 (r314909) +++ vendor-sys/illumos/dist/uts/common/fs/zfs/dsl_dataset.c Wed Mar 8 13:39:22 2017 (r314910) @@ -1725,11 +1725,22 @@ get_clones_stat(dsl_dataset_t *ds, nvlis zap_cursor_t zc; zap_attribute_t za; nvlist_t *propval = fnvlist_alloc(); - nvlist_t *val = fnvlist_alloc(); + nvlist_t *val; ASSERT(dsl_pool_config_held(ds->ds_dir->dd_pool)); /* + * We use nvlist_alloc() instead of fnvlist_alloc() because the + * latter would allocate the list with NV_UNIQUE_NAME flag. + * As a result, every time a clone name is appended to the list + * it would be (linearly) searched for for a duplicate name. + * We already know that all clone names must be unique and we + * want avoid the quadratic complexity of double-checking that + * because we can have a large number of clones. + */ + VERIFY0(nvlist_alloc(&val, 0, KM_SLEEP)); + + /* * There may be missing entries in ds_next_clones_obj * due to a bug in a previous version of the code. * Only trust it if it has the right number of entries.