svn commit: r269223 - vendor-sys/illumos/dist/common/avl vendor-sys/illumos/dist/uts/common/fs/zfs vendor-sys/illumos/dist/uts/common/fs/zfs/sys vendor-sys/illumos/dist/uts/common/sys vendor/illumo...
Author: delphij Date: Tue Jul 29 07:08:32 2014 New Revision: 269223 URL: http://svnweb.freebsd.org/changeset/base/269223 Log: 4873 zvol unmap calls can take a very long time for larger datasets Reviewed by: George Wilson Reviewed by: Matthew Ahrens Reviewed by: Paul Dagnelie Reviewed by: Basil Crow Reviewed by: Dan McDonald Approved by: Robert Mustacchi illumos/illumos-gate@0f6d88aded0d165f5954688a9b13bac76c38da84 Modified: vendor/illumos/dist/common/avl/avl.c Changes in other areas also in this revision: Modified: vendor-sys/illumos/dist/common/avl/avl.c vendor-sys/illumos/dist/uts/common/fs/zfs/dbuf.c vendor-sys/illumos/dist/uts/common/fs/zfs/dnode.c vendor-sys/illumos/dist/uts/common/fs/zfs/dnode_sync.c vendor-sys/illumos/dist/uts/common/fs/zfs/sys/dbuf.h vendor-sys/illumos/dist/uts/common/fs/zfs/sys/dnode.h vendor-sys/illumos/dist/uts/common/sys/avl.h Modified: vendor/illumos/dist/common/avl/avl.c == --- vendor/illumos/dist/common/avl/avl.cTue Jul 29 06:57:13 2014 (r269222) +++ vendor/illumos/dist/common/avl/avl.cTue Jul 29 07:08:32 2014 (r269223) @@ -24,6 +24,10 @@ */ /* + * Copyright (c) 2014 by Delphix. All rights reserved. + */ + +/* * AVL - generic AVL tree implementation for kernel use * * A complete description of AVL trees can be found in many CS textbooks. @@ -37,7 +41,7 @@ * insertion and deletion relatively efficiently. Searching the tree is * still a fast operation, roughly O(log(N)). * - * The key to insertion and deletion is a set of tree maniuplations called + * The key to insertion and deletion is a set of tree manipulations called * rotations, which bring unbalanced subtrees back into the semi-balanced state. * * This implementation of AVL trees has the following peculiarities: @@ -45,7 +49,7 @@ * - The AVL specific data structures are physically embedded as fields * in the "using" data structures. To maintain generality the code * must constantly translate between "avl_node_t *" and containing - * data structure "void *"s by adding/subracting the avl_offset. + * data structure "void *"s by adding/subtracting the avl_offset. * * - Since the AVL data is always embedded in other structures, there is * no locking or memory allocation in the AVL routines. This must be @@ -85,6 +89,12 @@ * is a modified "avl_node_t *". The bottom bit (normally 0 for a * pointer) is set to indicate if that the new node has a value greater * than the value of the indicated "avl_node_t *". + * + * Note - in addition to userland (e.g. libavl and libutil) and the kernel + * (e.g. genunix), avl.c is compiled into ld.so and kmdb's genunix module, + * which each have their own compilation environments and subsequent + * requirements. Each of these environments must be considered when adding + * dependencies from avl.c. */ #include @@ -94,7 +104,7 @@ #include /* - * Small arrays to translate between balance (or diff) values and child indeces. + * Small arrays to translate between balance (or diff) values and child indices. * * Code that deals with binary tree data structures will randomly use * left and right children when examining a tree. C "if()" statements @@ -114,7 +124,8 @@ static const int avl_balance2child[] = * * - If there is a left child, go to it, then to it's rightmost descendant. * - * - otherwise we return thru parent nodes until we've come from a right child. + * - otherwise we return through parent nodes until we've come from a right + * child. * * Return Value: * NULL - if at the end of the nodes @@ -863,6 +874,24 @@ avl_update(avl_tree_t *t, void *obj) return (B_FALSE); } +void +avl_swap(avl_tree_t *tree1, avl_tree_t *tree2) +{ + avl_node_t *temp_node; + ulong_t temp_numnodes; + + ASSERT3P(tree1->avl_compar, ==, tree2->avl_compar); + ASSERT3U(tree1->avl_offset, ==, tree2->avl_offset); + ASSERT3U(tree1->avl_size, ==, tree2->avl_size); + + temp_node = tree1->avl_root; + temp_numnodes = tree1->avl_numnodes; + tree1->avl_root = tree2->avl_root; + tree1->avl_numnodes = tree2->avl_numnodes; + tree2->avl_root = temp_node; + tree2->avl_numnodes = temp_numnodes; +} + /* * initialize a new AVL tree */ @@ -919,7 +948,7 @@ avl_is_empty(avl_tree_t *tree) /* * Post-order tree walk used to visit all tree nodes and destroy the tree - * in post order. This is used for destroying a tree w/o paying any cost + * in post order. This is used for destroying a tree without paying any cost * for rebalancing it. * * example: ___ svn-src-all@freebsd.org mailing list http://lists.freebsd.org/mailman/listinfo/svn-src-all To unsubscribe, send any mail to "svn-src-all-unsubscr...@freebsd.org"
svn commit: r269223 - vendor-sys/illumos/dist/common/avl vendor-sys/illumos/dist/uts/common/fs/zfs vendor-sys/illumos/dist/uts/common/fs/zfs/sys vendor-sys/illumos/dist/uts/common/sys vendor/illumo...
Author: delphij Date: Tue Jul 29 07:08:32 2014 New Revision: 269223 URL: http://svnweb.freebsd.org/changeset/base/269223 Log: 4873 zvol unmap calls can take a very long time for larger datasets Reviewed by: George Wilson Reviewed by: Matthew Ahrens Reviewed by: Paul Dagnelie Reviewed by: Basil Crow Reviewed by: Dan McDonald Approved by: Robert Mustacchi illumos/illumos-gate@0f6d88aded0d165f5954688a9b13bac76c38da84 Modified: vendor-sys/illumos/dist/common/avl/avl.c vendor-sys/illumos/dist/uts/common/fs/zfs/dbuf.c vendor-sys/illumos/dist/uts/common/fs/zfs/dnode.c vendor-sys/illumos/dist/uts/common/fs/zfs/dnode_sync.c vendor-sys/illumos/dist/uts/common/fs/zfs/sys/dbuf.h vendor-sys/illumos/dist/uts/common/fs/zfs/sys/dnode.h vendor-sys/illumos/dist/uts/common/sys/avl.h Changes in other areas also in this revision: Modified: vendor/illumos/dist/common/avl/avl.c Modified: vendor-sys/illumos/dist/common/avl/avl.c == --- vendor-sys/illumos/dist/common/avl/avl.cTue Jul 29 06:57:13 2014 (r269222) +++ vendor-sys/illumos/dist/common/avl/avl.cTue Jul 29 07:08:32 2014 (r269223) @@ -24,6 +24,10 @@ */ /* + * Copyright (c) 2014 by Delphix. All rights reserved. + */ + +/* * AVL - generic AVL tree implementation for kernel use * * A complete description of AVL trees can be found in many CS textbooks. @@ -85,6 +89,12 @@ * is a modified "avl_node_t *". The bottom bit (normally 0 for a * pointer) is set to indicate if that the new node has a value greater * than the value of the indicated "avl_node_t *". + * + * Note - in addition to userland (e.g. libavl and libutil) and the kernel + * (e.g. genunix), avl.c is compiled into ld.so and kmdb's genunix module, + * which each have their own compilation environments and subsequent + * requirements. Each of these environments must be considered when adding + * dependencies from avl.c. */ #include @@ -864,6 +874,24 @@ avl_update(avl_tree_t *t, void *obj) return (B_FALSE); } +void +avl_swap(avl_tree_t *tree1, avl_tree_t *tree2) +{ + avl_node_t *temp_node; + ulong_t temp_numnodes; + + ASSERT3P(tree1->avl_compar, ==, tree2->avl_compar); + ASSERT3U(tree1->avl_offset, ==, tree2->avl_offset); + ASSERT3U(tree1->avl_size, ==, tree2->avl_size); + + temp_node = tree1->avl_root; + temp_numnodes = tree1->avl_numnodes; + tree1->avl_root = tree2->avl_root; + tree1->avl_numnodes = tree2->avl_numnodes; + tree2->avl_root = temp_node; + tree2->avl_numnodes = temp_numnodes; +} + /* * initialize a new AVL tree */ Modified: vendor-sys/illumos/dist/uts/common/fs/zfs/dbuf.c == --- vendor-sys/illumos/dist/uts/common/fs/zfs/dbuf.cTue Jul 29 06:57:13 2014(r269222) +++ vendor-sys/illumos/dist/uts/common/fs/zfs/dbuf.cTue Jul 29 07:08:32 2014(r269223) @@ -69,6 +69,9 @@ dbuf_cons(void *vdb, void *unused, int k mutex_init(&db->db_mtx, NULL, MUTEX_DEFAULT, NULL); cv_init(&db->db_changed, NULL, CV_DEFAULT, NULL); refcount_create(&db->db_holds); + + db->db_creation = gethrtime(); + return (0); } @@ -330,7 +333,7 @@ dbuf_verify(dmu_buf_impl_t *db) ASSERT3U(db->db_level, <, dn->dn_nlevels); ASSERT(db->db_blkid == DMU_BONUS_BLKID || db->db_blkid == DMU_SPILL_BLKID || - !list_is_empty(&dn->dn_dbufs)); + !avl_is_empty(&dn->dn_dbufs)); } if (db->db_blkid == DMU_BONUS_BLKID) { ASSERT(dn != NULL); @@ -803,18 +806,30 @@ dbuf_unoverride(dbuf_dirty_record_t *dr) * receive; see comment below for details. */ void -dbuf_free_range(dnode_t *dn, uint64_t start, uint64_t end, dmu_tx_t *tx) +dbuf_free_range(dnode_t *dn, uint64_t start_blkid, uint64_t end_blkid, +dmu_tx_t *tx) { - dmu_buf_impl_t *db, *db_next; + dmu_buf_impl_t *db, *db_next, db_search; uint64_t txg = tx->tx_txg; + avl_index_t where; - if (end > dn->dn_maxblkid && (end != DMU_SPILL_BLKID)) - end = dn->dn_maxblkid; - dprintf_dnode(dn, "start=%llu end=%llu\n", start, end); + if (end_blkid > dn->dn_maxblkid && (end_blkid != DMU_SPILL_BLKID)) + end_blkid = dn->dn_maxblkid; + dprintf_dnode(dn, "start=%llu end=%llu\n", start_blkid, end_blkid); + + db_search.db_level = 0; + db_search.db_blkid = start_blkid; + db_search.db_creation = 0; mutex_enter(&dn->dn_dbufs_mtx); - if (start >= dn->dn_unlisted_l0_blkid * dn->dn_datablksz) { + if (start_blkid >= dn->dn_unlisted_l0_blkid) { /* There can't be any dbufs in this range; no need to search. */ +#ifdef DEBUG + db = avl_find(&dn->dn_dbufs, &db_search, &wh