1 /*
   2  * CDDL HEADER START
   3  *
   4  * The contents of this file are subject to the terms of the
   5  * Common Development and Distribution License (the "License").
   6  * You may not use this file except in compliance with the License.
   7  *
   8  * You can obtain a copy of the license at usr/src/OPENSOLARIS.LICENSE
   9  * or http://www.opensolaris.org/os/licensing.
  10  * See the License for the specific language governing permissions
  11  * and limitations under the License.
  12  *
  13  * When distributing Covered Code, include this CDDL HEADER in each
  14  * file and include the License file at usr/src/OPENSOLARIS.LICENSE.
  15  * If applicable, add the following below this CDDL HEADER, with the
  16  * fields enclosed by brackets "[]" replaced with your own identifying
  17  * information: Portions Copyright [yyyy] [name of copyright owner]
  18  *
  19  * CDDL HEADER END
  20  */
  21 /*
  22  * Copyright (c) 2005, 2010, Oracle and/or its affiliates. All rights reserved.
  23  * Copyright (c) 2012, 2017 by Delphix. All rights reserved.
  24  * Copyright (c) 2014 Spectra Logic Corporation, All rights reserved.
  25  * Copyright (c) 2014 Integros [integros.com]
  26  */
  27 
  28 #include <sys/zfs_context.h>
  29 #include <sys/dbuf.h>
  30 #include <sys/dnode.h>
  31 #include <sys/dmu.h>
  32 #include <sys/dmu_impl.h>
  33 #include <sys/dmu_tx.h>
  34 #include <sys/dmu_objset.h>
  35 #include <sys/dsl_dir.h>
  36 #include <sys/dsl_dataset.h>
  37 #include <sys/spa.h>
  38 #include <sys/zio.h>
  39 #include <sys/dmu_zfetch.h>
  40 #include <sys/range_tree.h>
  41 
  42 static kmem_cache_t *dnode_cache;
  43 /*
  44  * Define DNODE_STATS to turn on statistic gathering. By default, it is only
  45  * turned on when DEBUG is also defined.
  46  */
  47 #ifdef  DEBUG
  48 #define DNODE_STATS
  49 #endif  /* DEBUG */
  50 
  51 #ifdef  DNODE_STATS
  52 #define DNODE_STAT_ADD(stat)                    ((stat)++)
  53 #else
  54 #define DNODE_STAT_ADD(stat)                    /* nothing */
  55 #endif  /* DNODE_STATS */
  56 
  57 static dnode_phys_t dnode_phys_zero;
  58 
  59 int zfs_default_bs = SPA_MINBLOCKSHIFT;
  60 int zfs_default_ibs = DN_MAX_INDBLKSHIFT;
  61 
  62 static kmem_cbrc_t dnode_move(void *, void *, size_t, void *);
  63 
  64 static int
  65 dbuf_compare(const void *x1, const void *x2)
  66 {
  67         const dmu_buf_impl_t *d1 = x1;
  68         const dmu_buf_impl_t *d2 = x2;
  69 
  70         if (d1->db_level < d2->db_level) {
  71                 return (-1);
  72         }
  73         if (d1->db_level > d2->db_level) {
  74                 return (1);
  75         }
  76 
  77         if (d1->db_blkid < d2->db_blkid) {
  78                 return (-1);
  79         }
  80         if (d1->db_blkid > d2->db_blkid) {
  81                 return (1);
  82         }
  83 
  84         if (d1->db_state == DB_SEARCH) {
  85                 ASSERT3S(d2->db_state, !=, DB_SEARCH);
  86                 return (-1);
  87         } else if (d2->db_state == DB_SEARCH) {
  88                 ASSERT3S(d1->db_state, !=, DB_SEARCH);
  89                 return (1);
  90         }
  91 
  92         if ((uintptr_t)d1 < (uintptr_t)d2) {
  93                 return (-1);
  94         }
  95         if ((uintptr_t)d1 > (uintptr_t)d2) {
  96                 return (1);
  97         }
  98         return (0);
  99 }
 100 
 101 /* ARGSUSED */
 102 static int
 103 dnode_cons(void *arg, void *unused, int kmflag)
 104 {
 105         dnode_t *dn = arg;
 106         int i;
 107 
 108         rw_init(&dn->dn_struct_rwlock, NULL, RW_DEFAULT, NULL);
 109         mutex_init(&dn->dn_mtx, NULL, MUTEX_DEFAULT, NULL);
 110         mutex_init(&dn->dn_dbufs_mtx, NULL, MUTEX_DEFAULT, NULL);
 111         cv_init(&dn->dn_notxholds, NULL, CV_DEFAULT, NULL);
 112 
 113         /*
 114          * Every dbuf has a reference, and dropping a tracked reference is
 115          * O(number of references), so don't track dn_holds.
 116          */
 117         refcount_create_untracked(&dn->dn_holds);
 118         refcount_create(&dn->dn_tx_holds);
 119         list_link_init(&dn->dn_link);
 120 
 121         bzero(&dn->dn_next_nblkptr[0], sizeof (dn->dn_next_nblkptr));
 122         bzero(&dn->dn_next_nlevels[0], sizeof (dn->dn_next_nlevels));
 123         bzero(&dn->dn_next_indblkshift[0], sizeof (dn->dn_next_indblkshift));
 124         bzero(&dn->dn_next_bonustype[0], sizeof (dn->dn_next_bonustype));
 125         bzero(&dn->dn_rm_spillblk[0], sizeof (dn->dn_rm_spillblk));
 126         bzero(&dn->dn_next_bonuslen[0], sizeof (dn->dn_next_bonuslen));
 127         bzero(&dn->dn_next_blksz[0], sizeof (dn->dn_next_blksz));
 128 
 129         for (i = 0; i < TXG_SIZE; i++) {
 130                 list_link_init(&dn->dn_dirty_link[i]);
 131                 dn->dn_free_ranges[i] = NULL;
 132                 list_create(&dn->dn_dirty_records[i],
 133                     sizeof (dbuf_dirty_record_t),
 134                     offsetof(dbuf_dirty_record_t, dr_dirty_node));
 135         }
 136 
 137         dn->dn_allocated_txg = 0;
 138         dn->dn_free_txg = 0;
 139         dn->dn_assigned_txg = 0;
 140         dn->dn_dirtyctx = 0;
 141         dn->dn_dirtyctx_firstset = NULL;
 142         dn->dn_bonus = NULL;
 143         dn->dn_have_spill = B_FALSE;
 144         dn->dn_zio = NULL;
 145         dn->dn_oldused = 0;
 146         dn->dn_oldflags = 0;
 147         dn->dn_olduid = 0;
 148         dn->dn_oldgid = 0;
 149         dn->dn_newuid = 0;
 150         dn->dn_newgid = 0;
 151         dn->dn_id_flags = 0;
 152 
 153         dn->dn_dbufs_count = 0;
 154         avl_create(&dn->dn_dbufs, dbuf_compare, sizeof (dmu_buf_impl_t),
 155             offsetof(dmu_buf_impl_t, db_link));
 156 
 157         dn->dn_moved = 0;
 158         return (0);
 159 }
 160 
 161 /* ARGSUSED */
 162 static void
 163 dnode_dest(void *arg, void *unused)
 164 {
 165         int i;
 166         dnode_t *dn = arg;
 167 
 168         rw_destroy(&dn->dn_struct_rwlock);
 169         mutex_destroy(&dn->dn_mtx);
 170         mutex_destroy(&dn->dn_dbufs_mtx);
 171         cv_destroy(&dn->dn_notxholds);
 172         refcount_destroy(&dn->dn_holds);
 173         refcount_destroy(&dn->dn_tx_holds);
 174         ASSERT(!list_link_active(&dn->dn_link));
 175 
 176         for (i = 0; i < TXG_SIZE; i++) {
 177                 ASSERT(!list_link_active(&dn->dn_dirty_link[i]));
 178                 ASSERT3P(dn->dn_free_ranges[i], ==, NULL);
 179                 list_destroy(&dn->dn_dirty_records[i]);
 180                 ASSERT0(dn->dn_next_nblkptr[i]);
 181                 ASSERT0(dn->dn_next_nlevels[i]);
 182                 ASSERT0(dn->dn_next_indblkshift[i]);
 183                 ASSERT0(dn->dn_next_bonustype[i]);
 184                 ASSERT0(dn->dn_rm_spillblk[i]);
 185                 ASSERT0(dn->dn_next_bonuslen[i]);
 186                 ASSERT0(dn->dn_next_blksz[i]);
 187         }
 188 
 189         ASSERT0(dn->dn_allocated_txg);
 190         ASSERT0(dn->dn_free_txg);
 191         ASSERT0(dn->dn_assigned_txg);
 192         ASSERT0(dn->dn_dirtyctx);
 193         ASSERT3P(dn->dn_dirtyctx_firstset, ==, NULL);
 194         ASSERT3P(dn->dn_bonus, ==, NULL);
 195         ASSERT(!dn->dn_have_spill);
 196         ASSERT3P(dn->dn_zio, ==, NULL);
 197         ASSERT0(dn->dn_oldused);
 198         ASSERT0(dn->dn_oldflags);
 199         ASSERT0(dn->dn_olduid);
 200         ASSERT0(dn->dn_oldgid);
 201         ASSERT0(dn->dn_newuid);
 202         ASSERT0(dn->dn_newgid);
 203         ASSERT0(dn->dn_id_flags);
 204 
 205         ASSERT0(dn->dn_dbufs_count);
 206         avl_destroy(&dn->dn_dbufs);
 207 }
 208 
 209 void
 210 dnode_init(void)
 211 {
 212         ASSERT(dnode_cache == NULL);
 213         dnode_cache = kmem_cache_create("dnode_t",
 214             sizeof (dnode_t),
 215             0, dnode_cons, dnode_dest, NULL, NULL, NULL, 0);
 216         kmem_cache_set_move(dnode_cache, dnode_move);
 217 }
 218 
 219 void
 220 dnode_fini(void)
 221 {
 222         kmem_cache_destroy(dnode_cache);
 223         dnode_cache = NULL;
 224 }
 225 
 226 
 227 #ifdef ZFS_DEBUG
 228 void
 229 dnode_verify(dnode_t *dn)
 230 {
 231         int drop_struct_lock = FALSE;
 232 
 233         ASSERT(dn->dn_phys);
 234         ASSERT(dn->dn_objset);
 235         ASSERT(dn->dn_handle->dnh_dnode == dn);
 236 
 237         ASSERT(DMU_OT_IS_VALID(dn->dn_phys->dn_type));
 238 
 239         if (!(zfs_flags & ZFS_DEBUG_DNODE_VERIFY))
 240                 return;
 241 
 242         if (!RW_WRITE_HELD(&dn->dn_struct_rwlock)) {
 243                 rw_enter(&dn->dn_struct_rwlock, RW_READER);
 244                 drop_struct_lock = TRUE;
 245         }
 246         if (dn->dn_phys->dn_type != DMU_OT_NONE || dn->dn_allocated_txg != 0) {
 247                 int i;
 248                 ASSERT3U(dn->dn_indblkshift, >=, 0);
 249                 ASSERT3U(dn->dn_indblkshift, <=, SPA_MAXBLOCKSHIFT);
 250                 if (dn->dn_datablkshift) {
 251                         ASSERT3U(dn->dn_datablkshift, >=, SPA_MINBLOCKSHIFT);
 252                         ASSERT3U(dn->dn_datablkshift, <=, SPA_MAXBLOCKSHIFT);
 253                         ASSERT3U(1<<dn->dn_datablkshift, ==, dn->dn_datablksz);
 254                 }
 255                 ASSERT3U(dn->dn_nlevels, <=, 30);
 256                 ASSERT(DMU_OT_IS_VALID(dn->dn_type));
 257                 ASSERT3U(dn->dn_nblkptr, >=, 1);
 258                 ASSERT3U(dn->dn_nblkptr, <=, DN_MAX_NBLKPTR);
 259                 ASSERT3U(dn->dn_bonuslen, <=, DN_MAX_BONUSLEN);
 260                 ASSERT3U(dn->dn_datablksz, ==,
 261                     dn->dn_datablkszsec << SPA_MINBLOCKSHIFT);
 262                 ASSERT3U(ISP2(dn->dn_datablksz), ==, dn->dn_datablkshift != 0);
 263                 ASSERT3U((dn->dn_nblkptr - 1) * sizeof (blkptr_t) +
 264                     dn->dn_bonuslen, <=, DN_MAX_BONUSLEN);
 265                 for (i = 0; i < TXG_SIZE; i++) {
 266                         ASSERT3U(dn->dn_next_nlevels[i], <=, dn->dn_nlevels);
 267                 }
 268         }
 269         if (dn->dn_phys->dn_type != DMU_OT_NONE)
 270                 ASSERT3U(dn->dn_phys->dn_nlevels, <=, dn->dn_nlevels);
 271         ASSERT(DMU_OBJECT_IS_SPECIAL(dn->dn_object) || dn->dn_dbuf != NULL);
 272         if (dn->dn_dbuf != NULL) {
 273                 ASSERT3P(dn->dn_phys, ==,
 274                     (dnode_phys_t *)dn->dn_dbuf->db.db_data +
 275                     (dn->dn_object % (dn->dn_dbuf->db.db_size >> DNODE_SHIFT)));
 276         }
 277         if (drop_struct_lock)
 278                 rw_exit(&dn->dn_struct_rwlock);
 279 }
 280 #endif
 281 
 282 void
 283 dnode_byteswap(dnode_phys_t *dnp)
 284 {
 285         uint64_t *buf64 = (void*)&dnp->dn_blkptr;
 286         int i;
 287 
 288         if (dnp->dn_type == DMU_OT_NONE) {
 289                 bzero(dnp, sizeof (dnode_phys_t));
 290                 return;
 291         }
 292 
 293         dnp->dn_datablkszsec = BSWAP_16(dnp->dn_datablkszsec);
 294         dnp->dn_bonuslen = BSWAP_16(dnp->dn_bonuslen);
 295         dnp->dn_maxblkid = BSWAP_64(dnp->dn_maxblkid);
 296         dnp->dn_used = BSWAP_64(dnp->dn_used);
 297 
 298         /*
 299          * dn_nblkptr is only one byte, so it's OK to read it in either
 300          * byte order.  We can't read dn_bouslen.
 301          */
 302         ASSERT(dnp->dn_indblkshift <= SPA_MAXBLOCKSHIFT);
 303         ASSERT(dnp->dn_nblkptr <= DN_MAX_NBLKPTR);
 304         for (i = 0; i < dnp->dn_nblkptr * sizeof (blkptr_t)/8; i++)
 305                 buf64[i] = BSWAP_64(buf64[i]);
 306 
 307         /*
 308          * OK to check dn_bonuslen for zero, because it won't matter if
 309          * we have the wrong byte order.  This is necessary because the
 310          * dnode dnode is smaller than a regular dnode.
 311          */
 312         if (dnp->dn_bonuslen != 0) {
 313                 /*
 314                  * Note that the bonus length calculated here may be
 315                  * longer than the actual bonus buffer.  This is because
 316                  * we always put the bonus buffer after the last block
 317                  * pointer (instead of packing it against the end of the
 318                  * dnode buffer).
 319                  */
 320                 int off = (dnp->dn_nblkptr-1) * sizeof (blkptr_t);
 321                 size_t len = DN_MAX_BONUSLEN - off;
 322                 ASSERT(DMU_OT_IS_VALID(dnp->dn_bonustype));
 323                 dmu_object_byteswap_t byteswap =
 324                     DMU_OT_BYTESWAP(dnp->dn_bonustype);
 325                 dmu_ot_byteswap[byteswap].ob_func(dnp->dn_bonus + off, len);
 326         }
 327 
 328         /* Swap SPILL block if we have one */
 329         if (dnp->dn_flags & DNODE_FLAG_SPILL_BLKPTR)
 330                 byteswap_uint64_array(&dnp->dn_spill, sizeof (blkptr_t));
 331 
 332 }
 333 
 334 void
 335 dnode_buf_byteswap(void *vbuf, size_t size)
 336 {
 337         dnode_phys_t *buf = vbuf;
 338         int i;
 339 
 340         ASSERT3U(sizeof (dnode_phys_t), ==, (1<<DNODE_SHIFT));
 341         ASSERT((size & (sizeof (dnode_phys_t)-1)) == 0);
 342 
 343         size >>= DNODE_SHIFT;
 344         for (i = 0; i < size; i++) {
 345                 dnode_byteswap(buf);
 346                 buf++;
 347         }
 348 }
 349 
 350 void
 351 dnode_setbonuslen(dnode_t *dn, int newsize, dmu_tx_t *tx)
 352 {
 353         ASSERT3U(refcount_count(&dn->dn_holds), >=, 1);
 354 
 355         dnode_setdirty(dn, tx);
 356         rw_enter(&dn->dn_struct_rwlock, RW_WRITER);
 357         ASSERT3U(newsize, <=, DN_MAX_BONUSLEN -
 358             (dn->dn_nblkptr-1) * sizeof (blkptr_t));
 359         dn->dn_bonuslen = newsize;
 360         if (newsize == 0)
 361                 dn->dn_next_bonuslen[tx->tx_txg & TXG_MASK] = DN_ZERO_BONUSLEN;
 362         else
 363                 dn->dn_next_bonuslen[tx->tx_txg & TXG_MASK] = dn->dn_bonuslen;
 364         rw_exit(&dn->dn_struct_rwlock);
 365 }
 366 
 367 void
 368 dnode_setbonus_type(dnode_t *dn, dmu_object_type_t newtype, dmu_tx_t *tx)
 369 {
 370         ASSERT3U(refcount_count(&dn->dn_holds), >=, 1);
 371         dnode_setdirty(dn, tx);
 372         rw_enter(&dn->dn_struct_rwlock, RW_WRITER);
 373         dn->dn_bonustype = newtype;
 374         dn->dn_next_bonustype[tx->tx_txg & TXG_MASK] = dn->dn_bonustype;
 375         rw_exit(&dn->dn_struct_rwlock);
 376 }
 377 
 378 void
 379 dnode_rm_spill(dnode_t *dn, dmu_tx_t *tx)
 380 {
 381         ASSERT3U(refcount_count(&dn->dn_holds), >=, 1);
 382         ASSERT(RW_WRITE_HELD(&dn->dn_struct_rwlock));
 383         dnode_setdirty(dn, tx);
 384         dn->dn_rm_spillblk[tx->tx_txg&TXG_MASK] = DN_KILL_SPILLBLK;
 385         dn->dn_have_spill = B_FALSE;
 386 }
 387 
 388 static void
 389 dnode_setdblksz(dnode_t *dn, int size)
 390 {
 391         ASSERT0(P2PHASE(size, SPA_MINBLOCKSIZE));
 392         ASSERT3U(size, <=, SPA_MAXBLOCKSIZE);
 393         ASSERT3U(size, >=, SPA_MINBLOCKSIZE);
 394         ASSERT3U(size >> SPA_MINBLOCKSHIFT, <,
 395             1<<(sizeof (dn->dn_phys->dn_datablkszsec) * 8));
 396         dn->dn_datablksz = size;
 397         dn->dn_datablkszsec = size >> SPA_MINBLOCKSHIFT;
 398         dn->dn_datablkshift = ISP2(size) ? highbit64(size - 1) : 0;
 399 }
 400 
 401 static dnode_t *
 402 dnode_create(objset_t *os, dnode_phys_t *dnp, dmu_buf_impl_t *db,
 403     uint64_t object, dnode_handle_t *dnh)
 404 {
 405         dnode_t *dn;
 406 
 407         dn = kmem_cache_alloc(dnode_cache, KM_SLEEP);
 408         ASSERT(!POINTER_IS_VALID(dn->dn_objset));
 409         dn->dn_moved = 0;
 410 
 411         /*
 412          * Defer setting dn_objset until the dnode is ready to be a candidate
 413          * for the dnode_move() callback.
 414          */
 415         dn->dn_object = object;
 416         dn->dn_dbuf = db;
 417         dn->dn_handle = dnh;
 418         dn->dn_phys = dnp;
 419 
 420         if (dnp->dn_datablkszsec) {
 421                 dnode_setdblksz(dn, dnp->dn_datablkszsec << SPA_MINBLOCKSHIFT);
 422         } else {
 423                 dn->dn_datablksz = 0;
 424                 dn->dn_datablkszsec = 0;
 425                 dn->dn_datablkshift = 0;
 426         }
 427         dn->dn_indblkshift = dnp->dn_indblkshift;
 428         dn->dn_nlevels = dnp->dn_nlevels;
 429         dn->dn_type = dnp->dn_type;
 430         dn->dn_nblkptr = dnp->dn_nblkptr;
 431         dn->dn_checksum = dnp->dn_checksum;
 432         dn->dn_compress = dnp->dn_compress;
 433         dn->dn_bonustype = dnp->dn_bonustype;
 434         dn->dn_bonuslen = dnp->dn_bonuslen;
 435         dn->dn_maxblkid = dnp->dn_maxblkid;
 436         dn->dn_have_spill = ((dnp->dn_flags & DNODE_FLAG_SPILL_BLKPTR) != 0);
 437         dn->dn_id_flags = 0;
 438 
 439         dmu_zfetch_init(&dn->dn_zfetch, dn);
 440 
 441         ASSERT(DMU_OT_IS_VALID(dn->dn_phys->dn_type));
 442 
 443         mutex_enter(&os->os_lock);
 444         if (dnh->dnh_dnode != NULL) {
 445                 /* Lost the allocation race. */
 446                 mutex_exit(&os->os_lock);
 447                 kmem_cache_free(dnode_cache, dn);
 448                 return (dnh->dnh_dnode);
 449         }
 450 
 451         /*
 452          * Exclude special dnodes from os_dnodes so an empty os_dnodes
 453          * signifies that the special dnodes have no references from
 454          * their children (the entries in os_dnodes).  This allows
 455          * dnode_destroy() to easily determine if the last child has
 456          * been removed and then complete eviction of the objset.
 457          */
 458         if (!DMU_OBJECT_IS_SPECIAL(object))
 459                 list_insert_head(&os->os_dnodes, dn);
 460         membar_producer();
 461 
 462         /*
 463          * Everything else must be valid before assigning dn_objset
 464          * makes the dnode eligible for dnode_move().
 465          */
 466         dn->dn_objset = os;
 467 
 468         dnh->dnh_dnode = dn;
 469         mutex_exit(&os->os_lock);
 470 
 471         arc_space_consume(sizeof (dnode_t), ARC_SPACE_OTHER);
 472         return (dn);
 473 }
 474 
 475 /*
 476  * Caller must be holding the dnode handle, which is released upon return.
 477  */
 478 static void
 479 dnode_destroy(dnode_t *dn)
 480 {
 481         objset_t *os = dn->dn_objset;
 482         boolean_t complete_os_eviction = B_FALSE;
 483 
 484         ASSERT((dn->dn_id_flags & DN_ID_NEW_EXIST) == 0);
 485 
 486         mutex_enter(&os->os_lock);
 487         POINTER_INVALIDATE(&dn->dn_objset);
 488         if (!DMU_OBJECT_IS_SPECIAL(dn->dn_object)) {
 489                 list_remove(&os->os_dnodes, dn);
 490                 complete_os_eviction =
 491                     list_is_empty(&os->os_dnodes) &&
 492                     list_link_active(&os->os_evicting_node);
 493         }
 494         mutex_exit(&os->os_lock);
 495 
 496         /* the dnode can no longer move, so we can release the handle */
 497         zrl_remove(&dn->dn_handle->dnh_zrlock);
 498 
 499         dn->dn_allocated_txg = 0;
 500         dn->dn_free_txg = 0;
 501         dn->dn_assigned_txg = 0;
 502 
 503         dn->dn_dirtyctx = 0;
 504         if (dn->dn_dirtyctx_firstset != NULL) {
 505                 kmem_free(dn->dn_dirtyctx_firstset, 1);
 506                 dn->dn_dirtyctx_firstset = NULL;
 507         }
 508         if (dn->dn_bonus != NULL) {
 509                 mutex_enter(&dn->dn_bonus->db_mtx);
 510                 dbuf_destroy(dn->dn_bonus);
 511                 dn->dn_bonus = NULL;
 512         }
 513         dn->dn_zio = NULL;
 514 
 515         dn->dn_have_spill = B_FALSE;
 516         dn->dn_oldused = 0;
 517         dn->dn_oldflags = 0;
 518         dn->dn_olduid = 0;
 519         dn->dn_oldgid = 0;
 520         dn->dn_newuid = 0;
 521         dn->dn_newgid = 0;
 522         dn->dn_id_flags = 0;
 523 
 524         dmu_zfetch_fini(&dn->dn_zfetch);
 525         kmem_cache_free(dnode_cache, dn);
 526         arc_space_return(sizeof (dnode_t), ARC_SPACE_OTHER);
 527 
 528         if (complete_os_eviction)
 529                 dmu_objset_evict_done(os);
 530 }
 531 
 532 void
 533 dnode_allocate(dnode_t *dn, dmu_object_type_t ot, int blocksize, int ibs,
 534     dmu_object_type_t bonustype, int bonuslen, dmu_tx_t *tx)
 535 {
 536         int i;
 537 
 538         ASSERT3U(blocksize, <=,
 539             spa_maxblocksize(dmu_objset_spa(dn->dn_objset)));
 540         if (blocksize == 0)
 541                 blocksize = 1 << zfs_default_bs;
 542         else
 543                 blocksize = P2ROUNDUP(blocksize, SPA_MINBLOCKSIZE);
 544 
 545         if (ibs == 0)
 546                 ibs = zfs_default_ibs;
 547 
 548         ibs = MIN(MAX(ibs, DN_MIN_INDBLKSHIFT), DN_MAX_INDBLKSHIFT);
 549 
 550         dprintf("os=%p obj=%llu txg=%llu blocksize=%d ibs=%d\n", dn->dn_objset,
 551             dn->dn_object, tx->tx_txg, blocksize, ibs);
 552 
 553         ASSERT(dn->dn_type == DMU_OT_NONE);
 554         ASSERT(bcmp(dn->dn_phys, &dnode_phys_zero, sizeof (dnode_phys_t)) == 0);
 555         ASSERT(dn->dn_phys->dn_type == DMU_OT_NONE);
 556         ASSERT(ot != DMU_OT_NONE);
 557         ASSERT(DMU_OT_IS_VALID(ot));
 558         ASSERT((bonustype == DMU_OT_NONE && bonuslen == 0) ||
 559             (bonustype == DMU_OT_SA && bonuslen == 0) ||
 560             (bonustype != DMU_OT_NONE && bonuslen != 0));
 561         ASSERT(DMU_OT_IS_VALID(bonustype));
 562         ASSERT3U(bonuslen, <=, DN_MAX_BONUSLEN);
 563         ASSERT(dn->dn_type == DMU_OT_NONE);
 564         ASSERT0(dn->dn_maxblkid);
 565         ASSERT0(dn->dn_allocated_txg);
 566         ASSERT0(dn->dn_assigned_txg);
 567         ASSERT(refcount_is_zero(&dn->dn_tx_holds));
 568         ASSERT3U(refcount_count(&dn->dn_holds), <=, 1);
 569         ASSERT(avl_is_empty(&dn->dn_dbufs));
 570 
 571         for (i = 0; i < TXG_SIZE; i++) {
 572                 ASSERT0(dn->dn_next_nblkptr[i]);
 573                 ASSERT0(dn->dn_next_nlevels[i]);
 574                 ASSERT0(dn->dn_next_indblkshift[i]);
 575                 ASSERT0(dn->dn_next_bonuslen[i]);
 576                 ASSERT0(dn->dn_next_bonustype[i]);
 577                 ASSERT0(dn->dn_rm_spillblk[i]);
 578                 ASSERT0(dn->dn_next_blksz[i]);
 579                 ASSERT(!list_link_active(&dn->dn_dirty_link[i]));
 580                 ASSERT3P(list_head(&dn->dn_dirty_records[i]), ==, NULL);
 581                 ASSERT3P(dn->dn_free_ranges[i], ==, NULL);
 582         }
 583 
 584         dn->dn_type = ot;
 585         dnode_setdblksz(dn, blocksize);
 586         dn->dn_indblkshift = ibs;
 587         dn->dn_nlevels = 1;
 588         if (bonustype == DMU_OT_SA) /* Maximize bonus space for SA */
 589                 dn->dn_nblkptr = 1;
 590         else
 591                 dn->dn_nblkptr = 1 +
 592                     ((DN_MAX_BONUSLEN - bonuslen) >> SPA_BLKPTRSHIFT);
 593         dn->dn_bonustype = bonustype;
 594         dn->dn_bonuslen = bonuslen;
 595         dn->dn_checksum = ZIO_CHECKSUM_INHERIT;
 596         dn->dn_compress = ZIO_COMPRESS_INHERIT;
 597         dn->dn_dirtyctx = 0;
 598 
 599         dn->dn_free_txg = 0;
 600         if (dn->dn_dirtyctx_firstset) {
 601                 kmem_free(dn->dn_dirtyctx_firstset, 1);
 602                 dn->dn_dirtyctx_firstset = NULL;
 603         }
 604 
 605         dn->dn_allocated_txg = tx->tx_txg;
 606         dn->dn_id_flags = 0;
 607 
 608         dnode_setdirty(dn, tx);
 609         dn->dn_next_indblkshift[tx->tx_txg & TXG_MASK] = ibs;
 610         dn->dn_next_bonuslen[tx->tx_txg & TXG_MASK] = dn->dn_bonuslen;
 611         dn->dn_next_bonustype[tx->tx_txg & TXG_MASK] = dn->dn_bonustype;
 612         dn->dn_next_blksz[tx->tx_txg & TXG_MASK] = dn->dn_datablksz;
 613 }
 614 
 615 void
 616 dnode_reallocate(dnode_t *dn, dmu_object_type_t ot, int blocksize,
 617     dmu_object_type_t bonustype, int bonuslen, dmu_tx_t *tx)
 618 {
 619         int nblkptr;
 620 
 621         ASSERT3U(blocksize, >=, SPA_MINBLOCKSIZE);
 622         ASSERT3U(blocksize, <=,
 623             spa_maxblocksize(dmu_objset_spa(dn->dn_objset)));
 624         ASSERT0(blocksize % SPA_MINBLOCKSIZE);
 625         ASSERT(dn->dn_object != DMU_META_DNODE_OBJECT || dmu_tx_private_ok(tx));
 626         ASSERT(tx->tx_txg != 0);
 627         ASSERT((bonustype == DMU_OT_NONE && bonuslen == 0) ||
 628             (bonustype != DMU_OT_NONE && bonuslen != 0) ||
 629             (bonustype == DMU_OT_SA && bonuslen == 0));
 630         ASSERT(DMU_OT_IS_VALID(bonustype));
 631         ASSERT3U(bonuslen, <=, DN_MAX_BONUSLEN);
 632 
 633         /* clean up any unreferenced dbufs */
 634         dnode_evict_dbufs(dn);
 635 
 636         dn->dn_id_flags = 0;
 637 
 638         rw_enter(&dn->dn_struct_rwlock, RW_WRITER);
 639         dnode_setdirty(dn, tx);
 640         if (dn->dn_datablksz != blocksize) {
 641                 /* change blocksize */
 642                 ASSERT(dn->dn_maxblkid == 0 &&
 643                     (BP_IS_HOLE(&dn->dn_phys->dn_blkptr[0]) ||
 644                     dnode_block_freed(dn, 0)));
 645                 dnode_setdblksz(dn, blocksize);
 646                 dn->dn_next_blksz[tx->tx_txg&TXG_MASK] = blocksize;
 647         }
 648         if (dn->dn_bonuslen != bonuslen)
 649                 dn->dn_next_bonuslen[tx->tx_txg&TXG_MASK] = bonuslen;
 650 
 651         if (bonustype == DMU_OT_SA) /* Maximize bonus space for SA */
 652                 nblkptr = 1;
 653         else
 654                 nblkptr = 1 + ((DN_MAX_BONUSLEN - bonuslen) >> SPA_BLKPTRSHIFT);
 655         if (dn->dn_bonustype != bonustype)
 656                 dn->dn_next_bonustype[tx->tx_txg&TXG_MASK] = bonustype;
 657         if (dn->dn_nblkptr != nblkptr)
 658                 dn->dn_next_nblkptr[tx->tx_txg&TXG_MASK] = nblkptr;
 659         if (dn->dn_phys->dn_flags & DNODE_FLAG_SPILL_BLKPTR) {
 660                 dbuf_rm_spill(dn, tx);
 661                 dnode_rm_spill(dn, tx);
 662         }
 663         rw_exit(&dn->dn_struct_rwlock);
 664 
 665         /* change type */
 666         dn->dn_type = ot;
 667 
 668         /* change bonus size and type */
 669         mutex_enter(&dn->dn_mtx);
 670         dn->dn_bonustype = bonustype;
 671         dn->dn_bonuslen = bonuslen;
 672         dn->dn_nblkptr = nblkptr;
 673         dn->dn_checksum = ZIO_CHECKSUM_INHERIT;
 674         dn->dn_compress = ZIO_COMPRESS_INHERIT;
 675         ASSERT3U(dn->dn_nblkptr, <=, DN_MAX_NBLKPTR);
 676 
 677         /* fix up the bonus db_size */
 678         if (dn->dn_bonus) {
 679                 dn->dn_bonus->db.db_size =
 680                     DN_MAX_BONUSLEN - (dn->dn_nblkptr-1) * sizeof (blkptr_t);
 681                 ASSERT(dn->dn_bonuslen <= dn->dn_bonus->db.db_size);
 682         }
 683 
 684         dn->dn_allocated_txg = tx->tx_txg;
 685         mutex_exit(&dn->dn_mtx);
 686 }
 687 
 688 #ifdef  DNODE_STATS
 689 static struct {
 690         uint64_t dms_dnode_invalid;
 691         uint64_t dms_dnode_recheck1;
 692         uint64_t dms_dnode_recheck2;
 693         uint64_t dms_dnode_special;
 694         uint64_t dms_dnode_handle;
 695         uint64_t dms_dnode_rwlock;
 696         uint64_t dms_dnode_active;
 697 } dnode_move_stats;
 698 #endif  /* DNODE_STATS */
 699 
 700 static void
 701 dnode_move_impl(dnode_t *odn, dnode_t *ndn)
 702 {
 703         int i;
 704 
 705         ASSERT(!RW_LOCK_HELD(&odn->dn_struct_rwlock));
 706         ASSERT(MUTEX_NOT_HELD(&odn->dn_mtx));
 707         ASSERT(MUTEX_NOT_HELD(&odn->dn_dbufs_mtx));
 708         ASSERT(!RW_LOCK_HELD(&odn->dn_zfetch.zf_rwlock));
 709 
 710         /* Copy fields. */
 711         ndn->dn_objset = odn->dn_objset;
 712         ndn->dn_object = odn->dn_object;
 713         ndn->dn_dbuf = odn->dn_dbuf;
 714         ndn->dn_handle = odn->dn_handle;
 715         ndn->dn_phys = odn->dn_phys;
 716         ndn->dn_type = odn->dn_type;
 717         ndn->dn_bonuslen = odn->dn_bonuslen;
 718         ndn->dn_bonustype = odn->dn_bonustype;
 719         ndn->dn_nblkptr = odn->dn_nblkptr;
 720         ndn->dn_checksum = odn->dn_checksum;
 721         ndn->dn_compress = odn->dn_compress;
 722         ndn->dn_nlevels = odn->dn_nlevels;
 723         ndn->dn_indblkshift = odn->dn_indblkshift;
 724         ndn->dn_datablkshift = odn->dn_datablkshift;
 725         ndn->dn_datablkszsec = odn->dn_datablkszsec;
 726         ndn->dn_datablksz = odn->dn_datablksz;
 727         ndn->dn_maxblkid = odn->dn_maxblkid;
 728         bcopy(&odn->dn_next_nblkptr[0], &ndn->dn_next_nblkptr[0],
 729             sizeof (odn->dn_next_nblkptr));
 730         bcopy(&odn->dn_next_nlevels[0], &ndn->dn_next_nlevels[0],
 731             sizeof (odn->dn_next_nlevels));
 732         bcopy(&odn->dn_next_indblkshift[0], &ndn->dn_next_indblkshift[0],
 733             sizeof (odn->dn_next_indblkshift));
 734         bcopy(&odn->dn_next_bonustype[0], &ndn->dn_next_bonustype[0],
 735             sizeof (odn->dn_next_bonustype));
 736         bcopy(&odn->dn_rm_spillblk[0], &ndn->dn_rm_spillblk[0],
 737             sizeof (odn->dn_rm_spillblk));
 738         bcopy(&odn->dn_next_bonuslen[0], &ndn->dn_next_bonuslen[0],
 739             sizeof (odn->dn_next_bonuslen));
 740         bcopy(&odn->dn_next_blksz[0], &ndn->dn_next_blksz[0],
 741             sizeof (odn->dn_next_blksz));
 742         for (i = 0; i < TXG_SIZE; i++) {
 743                 list_move_tail(&ndn->dn_dirty_records[i],
 744                     &odn->dn_dirty_records[i]);
 745         }
 746         bcopy(&odn->dn_free_ranges[0], &ndn->dn_free_ranges[0],
 747             sizeof (odn->dn_free_ranges));
 748         ndn->dn_allocated_txg = odn->dn_allocated_txg;
 749         ndn->dn_free_txg = odn->dn_free_txg;
 750         ndn->dn_assigned_txg = odn->dn_assigned_txg;
 751         ndn->dn_dirtyctx = odn->dn_dirtyctx;
 752         ndn->dn_dirtyctx_firstset = odn->dn_dirtyctx_firstset;
 753         ASSERT(refcount_count(&odn->dn_tx_holds) == 0);
 754         refcount_transfer(&ndn->dn_holds, &odn->dn_holds);
 755         ASSERT(avl_is_empty(&ndn->dn_dbufs));
 756         avl_swap(&ndn->dn_dbufs, &odn->dn_dbufs);
 757         ndn->dn_dbufs_count = odn->dn_dbufs_count;
 758         ndn->dn_bonus = odn->dn_bonus;
 759         ndn->dn_have_spill = odn->dn_have_spill;
 760         ndn->dn_zio = odn->dn_zio;
 761         ndn->dn_oldused = odn->dn_oldused;
 762         ndn->dn_oldflags = odn->dn_oldflags;
 763         ndn->dn_olduid = odn->dn_olduid;
 764         ndn->dn_oldgid = odn->dn_oldgid;
 765         ndn->dn_newuid = odn->dn_newuid;
 766         ndn->dn_newgid = odn->dn_newgid;
 767         ndn->dn_id_flags = odn->dn_id_flags;
 768         dmu_zfetch_init(&ndn->dn_zfetch, NULL);
 769         list_move_tail(&ndn->dn_zfetch.zf_stream, &odn->dn_zfetch.zf_stream);
 770         ndn->dn_zfetch.zf_dnode = odn->dn_zfetch.zf_dnode;
 771 
 772         /*
 773          * Update back pointers. Updating the handle fixes the back pointer of
 774          * every descendant dbuf as well as the bonus dbuf.
 775          */
 776         ASSERT(ndn->dn_handle->dnh_dnode == odn);
 777         ndn->dn_handle->dnh_dnode = ndn;
 778         if (ndn->dn_zfetch.zf_dnode == odn) {
 779                 ndn->dn_zfetch.zf_dnode = ndn;
 780         }
 781 
 782         /*
 783          * Invalidate the original dnode by clearing all of its back pointers.
 784          */
 785         odn->dn_dbuf = NULL;
 786         odn->dn_handle = NULL;
 787         avl_create(&odn->dn_dbufs, dbuf_compare, sizeof (dmu_buf_impl_t),
 788             offsetof(dmu_buf_impl_t, db_link));
 789         odn->dn_dbufs_count = 0;
 790         odn->dn_bonus = NULL;
 791         odn->dn_zfetch.zf_dnode = NULL;
 792 
 793         /*
 794          * Set the low bit of the objset pointer to ensure that dnode_move()
 795          * recognizes the dnode as invalid in any subsequent callback.
 796          */
 797         POINTER_INVALIDATE(&odn->dn_objset);
 798 
 799         /*
 800          * Satisfy the destructor.
 801          */
 802         for (i = 0; i < TXG_SIZE; i++) {
 803                 list_create(&odn->dn_dirty_records[i],
 804                     sizeof (dbuf_dirty_record_t),
 805                     offsetof(dbuf_dirty_record_t, dr_dirty_node));
 806                 odn->dn_free_ranges[i] = NULL;
 807                 odn->dn_next_nlevels[i] = 0;
 808                 odn->dn_next_indblkshift[i] = 0;
 809                 odn->dn_next_bonustype[i] = 0;
 810                 odn->dn_rm_spillblk[i] = 0;
 811                 odn->dn_next_bonuslen[i] = 0;
 812                 odn->dn_next_blksz[i] = 0;
 813         }
 814         odn->dn_allocated_txg = 0;
 815         odn->dn_free_txg = 0;
 816         odn->dn_assigned_txg = 0;
 817         odn->dn_dirtyctx = 0;
 818         odn->dn_dirtyctx_firstset = NULL;
 819         odn->dn_have_spill = B_FALSE;
 820         odn->dn_zio = NULL;
 821         odn->dn_oldused = 0;
 822         odn->dn_oldflags = 0;
 823         odn->dn_olduid = 0;
 824         odn->dn_oldgid = 0;
 825         odn->dn_newuid = 0;
 826         odn->dn_newgid = 0;
 827         odn->dn_id_flags = 0;
 828 
 829         /*
 830          * Mark the dnode.
 831          */
 832         ndn->dn_moved = 1;
 833         odn->dn_moved = (uint8_t)-1;
 834 }
 835 
 836 #ifdef  _KERNEL
 837 /*ARGSUSED*/
 838 static kmem_cbrc_t
 839 dnode_move(void *buf, void *newbuf, size_t size, void *arg)
 840 {
 841         dnode_t *odn = buf, *ndn = newbuf;
 842         objset_t *os;
 843         int64_t refcount;
 844         uint32_t dbufs;
 845 
 846         /*
 847          * The dnode is on the objset's list of known dnodes if the objset
 848          * pointer is valid. We set the low bit of the objset pointer when
 849          * freeing the dnode to invalidate it, and the memory patterns written
 850          * by kmem (baddcafe and deadbeef) set at least one of the two low bits.
 851          * A newly created dnode sets the objset pointer last of all to indicate
 852          * that the dnode is known and in a valid state to be moved by this
 853          * function.
 854          */
 855         os = odn->dn_objset;
 856         if (!POINTER_IS_VALID(os)) {
 857                 DNODE_STAT_ADD(dnode_move_stats.dms_dnode_invalid);
 858                 return (KMEM_CBRC_DONT_KNOW);
 859         }
 860 
 861         /*
 862          * Ensure that the objset does not go away during the move.
 863          */
 864         rw_enter(&os_lock, RW_WRITER);
 865         if (os != odn->dn_objset) {
 866                 rw_exit(&os_lock);
 867                 DNODE_STAT_ADD(dnode_move_stats.dms_dnode_recheck1);
 868                 return (KMEM_CBRC_DONT_KNOW);
 869         }
 870 
 871         /*
 872          * If the dnode is still valid, then so is the objset. We know that no
 873          * valid objset can be freed while we hold os_lock, so we can safely
 874          * ensure that the objset remains in use.
 875          */
 876         mutex_enter(&os->os_lock);
 877 
 878         /*
 879          * Recheck the objset pointer in case the dnode was removed just before
 880          * acquiring the lock.
 881          */
 882         if (os != odn->dn_objset) {
 883                 mutex_exit(&os->os_lock);
 884                 rw_exit(&os_lock);
 885                 DNODE_STAT_ADD(dnode_move_stats.dms_dnode_recheck2);
 886                 return (KMEM_CBRC_DONT_KNOW);
 887         }
 888 
 889         /*
 890          * At this point we know that as long as we hold os->os_lock, the dnode
 891          * cannot be freed and fields within the dnode can be safely accessed.
 892          * The objset listing this dnode cannot go away as long as this dnode is
 893          * on its list.
 894          */
 895         rw_exit(&os_lock);
 896         if (DMU_OBJECT_IS_SPECIAL(odn->dn_object)) {
 897                 mutex_exit(&os->os_lock);
 898                 DNODE_STAT_ADD(dnode_move_stats.dms_dnode_special);
 899                 return (KMEM_CBRC_NO);
 900         }
 901         ASSERT(odn->dn_dbuf != NULL); /* only "special" dnodes have no parent */
 902 
 903         /*
 904          * Lock the dnode handle to prevent the dnode from obtaining any new
 905          * holds. This also prevents the descendant dbufs and the bonus dbuf
 906          * from accessing the dnode, so that we can discount their holds. The
 907          * handle is safe to access because we know that while the dnode cannot
 908          * go away, neither can its handle. Once we hold dnh_zrlock, we can
 909          * safely move any dnode referenced only by dbufs.
 910          */
 911         if (!zrl_tryenter(&odn->dn_handle->dnh_zrlock)) {
 912                 mutex_exit(&os->os_lock);
 913                 DNODE_STAT_ADD(dnode_move_stats.dms_dnode_handle);
 914                 return (KMEM_CBRC_LATER);
 915         }
 916 
 917         /*
 918          * Ensure a consistent view of the dnode's holds and the dnode's dbufs.
 919          * We need to guarantee that there is a hold for every dbuf in order to
 920          * determine whether the dnode is actively referenced. Falsely matching
 921          * a dbuf to an active hold would lead to an unsafe move. It's possible
 922          * that a thread already having an active dnode hold is about to add a
 923          * dbuf, and we can't compare hold and dbuf counts while the add is in
 924          * progress.
 925          */
 926         if (!rw_tryenter(&odn->dn_struct_rwlock, RW_WRITER)) {
 927                 zrl_exit(&odn->dn_handle->dnh_zrlock);
 928                 mutex_exit(&os->os_lock);
 929                 DNODE_STAT_ADD(dnode_move_stats.dms_dnode_rwlock);
 930                 return (KMEM_CBRC_LATER);
 931         }
 932 
 933         /*
 934          * A dbuf may be removed (evicted) without an active dnode hold. In that
 935          * case, the dbuf count is decremented under the handle lock before the
 936          * dbuf's hold is released. This order ensures that if we count the hold
 937          * after the dbuf is removed but before its hold is released, we will
 938          * treat the unmatched hold as active and exit safely. If we count the
 939          * hold before the dbuf is removed, the hold is discounted, and the
 940          * removal is blocked until the move completes.
 941          */
 942         refcount = refcount_count(&odn->dn_holds);
 943         ASSERT(refcount >= 0);
 944         dbufs = odn->dn_dbufs_count;
 945 
 946         /* We can't have more dbufs than dnode holds. */
 947         ASSERT3U(dbufs, <=, refcount);
 948         DTRACE_PROBE3(dnode__move, dnode_t *, odn, int64_t, refcount,
 949             uint32_t, dbufs);
 950 
 951         if (refcount > dbufs) {
 952                 rw_exit(&odn->dn_struct_rwlock);
 953                 zrl_exit(&odn->dn_handle->dnh_zrlock);
 954                 mutex_exit(&os->os_lock);
 955                 DNODE_STAT_ADD(dnode_move_stats.dms_dnode_active);
 956                 return (KMEM_CBRC_LATER);
 957         }
 958 
 959         rw_exit(&odn->dn_struct_rwlock);
 960 
 961         /*
 962          * At this point we know that anyone with a hold on the dnode is not
 963          * actively referencing it. The dnode is known and in a valid state to
 964          * move. We're holding the locks needed to execute the critical section.
 965          */
 966         dnode_move_impl(odn, ndn);
 967 
 968         list_link_replace(&odn->dn_link, &ndn->dn_link);
 969         /* If the dnode was safe to move, the refcount cannot have changed. */
 970         ASSERT(refcount == refcount_count(&ndn->dn_holds));
 971         ASSERT(dbufs == ndn->dn_dbufs_count);
 972         zrl_exit(&ndn->dn_handle->dnh_zrlock); /* handle has moved */
 973         mutex_exit(&os->os_lock);
 974 
 975         return (KMEM_CBRC_YES);
 976 }
 977 #endif  /* _KERNEL */
 978 
 979 void
 980 dnode_special_close(dnode_handle_t *dnh)
 981 {
 982         dnode_t *dn = dnh->dnh_dnode;
 983 
 984         /*
 985          * Wait for final references to the dnode to clear.  This can
 986          * only happen if the arc is asyncronously evicting state that
 987          * has a hold on this dnode while we are trying to evict this
 988          * dnode.
 989          */
 990         while (refcount_count(&dn->dn_holds) > 0)
 991                 delay(1);
 992         ASSERT(dn->dn_dbuf == NULL ||
 993             dmu_buf_get_user(&dn->dn_dbuf->db) == NULL);
 994         zrl_add(&dnh->dnh_zrlock);
 995         dnode_destroy(dn); /* implicit zrl_remove() */
 996         zrl_destroy(&dnh->dnh_zrlock);
 997         dnh->dnh_dnode = NULL;
 998 }
 999 
1000 void
1001 dnode_special_open(objset_t *os, dnode_phys_t *dnp, uint64_t object,
1002     dnode_handle_t *dnh)
1003 {
1004         dnode_t *dn;
1005 
1006         dn = dnode_create(os, dnp, NULL, object, dnh);
1007         zrl_init(&dnh->dnh_zrlock);
1008         DNODE_VERIFY(dn);
1009 }
1010 
1011 static void
1012 dnode_buf_evict_async(void *dbu)
1013 {
1014         dnode_children_t *children_dnodes = dbu;
1015         int i;
1016 
1017         for (i = 0; i < children_dnodes->dnc_count; i++) {
1018                 dnode_handle_t *dnh = &children_dnodes->dnc_children[i];
1019                 dnode_t *dn;
1020 
1021                 /*
1022                  * The dnode handle lock guards against the dnode moving to
1023                  * another valid address, so there is no need here to guard
1024                  * against changes to or from NULL.
1025                  */
1026                 if (dnh->dnh_dnode == NULL) {
1027                         zrl_destroy(&dnh->dnh_zrlock);
1028                         continue;
1029                 }
1030 
1031                 zrl_add(&dnh->dnh_zrlock);
1032                 dn = dnh->dnh_dnode;
1033                 /*
1034                  * If there are holds on this dnode, then there should
1035                  * be holds on the dnode's containing dbuf as well; thus
1036                  * it wouldn't be eligible for eviction and this function
1037                  * would not have been called.
1038                  */
1039                 ASSERT(refcount_is_zero(&dn->dn_holds));
1040                 ASSERT(refcount_is_zero(&dn->dn_tx_holds));
1041 
1042                 dnode_destroy(dn); /* implicit zrl_remove() */
1043                 zrl_destroy(&dnh->dnh_zrlock);
1044                 dnh->dnh_dnode = NULL;
1045         }
1046         kmem_free(children_dnodes, sizeof (dnode_children_t) +
1047             children_dnodes->dnc_count * sizeof (dnode_handle_t));
1048 }
1049 
1050 /*
1051  * errors:
1052  * EINVAL - invalid object number.
1053  * EIO - i/o error.
1054  * succeeds even for free dnodes.
1055  */
1056 int
1057 dnode_hold_impl(objset_t *os, uint64_t object, int flag,
1058     void *tag, dnode_t **dnp)
1059 {
1060         int epb, idx, err;
1061         int drop_struct_lock = FALSE;
1062         int type;
1063         uint64_t blk;
1064         dnode_t *mdn, *dn;
1065         dmu_buf_impl_t *db;
1066         dnode_children_t *children_dnodes;
1067         dnode_handle_t *dnh;
1068 
1069         /*
1070          * If you are holding the spa config lock as writer, you shouldn't
1071          * be asking the DMU to do *anything* unless it's the root pool
1072          * which may require us to read from the root filesystem while
1073          * holding some (not all) of the locks as writer.
1074          */
1075         ASSERT(spa_config_held(os->os_spa, SCL_ALL, RW_WRITER) == 0 ||
1076             (spa_is_root(os->os_spa) &&
1077             spa_config_held(os->os_spa, SCL_STATE, RW_WRITER)));
1078 
1079         if (object == DMU_USERUSED_OBJECT || object == DMU_GROUPUSED_OBJECT) {
1080                 dn = (object == DMU_USERUSED_OBJECT) ?
1081                     DMU_USERUSED_DNODE(os) : DMU_GROUPUSED_DNODE(os);
1082                 if (dn == NULL)
1083                         return (SET_ERROR(ENOENT));
1084                 type = dn->dn_type;
1085                 if ((flag & DNODE_MUST_BE_ALLOCATED) && type == DMU_OT_NONE)
1086                         return (SET_ERROR(ENOENT));
1087                 if ((flag & DNODE_MUST_BE_FREE) && type != DMU_OT_NONE)
1088                         return (SET_ERROR(EEXIST));
1089                 DNODE_VERIFY(dn);
1090                 (void) refcount_add(&dn->dn_holds, tag);
1091                 *dnp = dn;
1092                 return (0);
1093         }
1094 
1095         if (object == 0 || object >= DN_MAX_OBJECT)
1096                 return (SET_ERROR(EINVAL));
1097 
1098         mdn = DMU_META_DNODE(os);
1099         ASSERT(mdn->dn_object == DMU_META_DNODE_OBJECT);
1100 
1101         DNODE_VERIFY(mdn);
1102 
1103         if (!RW_WRITE_HELD(&mdn->dn_struct_rwlock)) {
1104                 rw_enter(&mdn->dn_struct_rwlock, RW_READER);
1105                 drop_struct_lock = TRUE;
1106         }
1107 
1108         blk = dbuf_whichblock(mdn, 0, object * sizeof (dnode_phys_t));
1109 
1110         db = dbuf_hold(mdn, blk, FTAG);
1111         if (drop_struct_lock)
1112                 rw_exit(&mdn->dn_struct_rwlock);
1113         if (db == NULL)
1114                 return (SET_ERROR(EIO));
1115         err = dbuf_read(db, NULL, DB_RF_CANFAIL);
1116         if (err) {
1117                 dbuf_rele(db, FTAG);
1118                 return (err);
1119         }
1120 
1121         ASSERT3U(db->db.db_size, >=, 1<<DNODE_SHIFT);
1122         epb = db->db.db_size >> DNODE_SHIFT;
1123 
1124         idx = object & (epb-1);
1125 
1126         ASSERT(DB_DNODE(db)->dn_type == DMU_OT_DNODE);
1127         children_dnodes = dmu_buf_get_user(&db->db);
1128         if (children_dnodes == NULL) {
1129                 int i;
1130                 dnode_children_t *winner;
1131                 children_dnodes = kmem_zalloc(sizeof (dnode_children_t) +
1132                     epb * sizeof (dnode_handle_t), KM_SLEEP);
1133                 children_dnodes->dnc_count = epb;
1134                 dnh = &children_dnodes->dnc_children[0];
1135                 for (i = 0; i < epb; i++) {
1136                         zrl_init(&dnh[i].dnh_zrlock);
1137                 }
1138                 dmu_buf_init_user(&children_dnodes->dnc_dbu, NULL,
1139                     dnode_buf_evict_async, NULL);
1140                 winner = dmu_buf_set_user(&db->db, &children_dnodes->dnc_dbu);
1141                 if (winner != NULL) {
1142 
1143                         for (i = 0; i < epb; i++) {
1144                                 zrl_destroy(&dnh[i].dnh_zrlock);
1145                         }
1146 
1147                         kmem_free(children_dnodes, sizeof (dnode_children_t) +
1148                             epb * sizeof (dnode_handle_t));
1149                         children_dnodes = winner;
1150                 }
1151         }
1152         ASSERT(children_dnodes->dnc_count == epb);
1153 
1154         dnh = &children_dnodes->dnc_children[idx];
1155         zrl_add(&dnh->dnh_zrlock);
1156         dn = dnh->dnh_dnode;
1157         if (dn == NULL) {
1158                 dnode_phys_t *phys = (dnode_phys_t *)db->db.db_data+idx;
1159 
1160                 dn = dnode_create(os, phys, db, object, dnh);
1161         }
1162 
1163         mutex_enter(&dn->dn_mtx);
1164         type = dn->dn_type;
1165         if (dn->dn_free_txg ||
1166             ((flag & DNODE_MUST_BE_ALLOCATED) && type == DMU_OT_NONE) ||
1167             ((flag & DNODE_MUST_BE_FREE) &&
1168             (type != DMU_OT_NONE || !refcount_is_zero(&dn->dn_holds)))) {
1169                 mutex_exit(&dn->dn_mtx);
1170                 zrl_remove(&dnh->dnh_zrlock);
1171                 dbuf_rele(db, FTAG);
1172                 return (type == DMU_OT_NONE ? ENOENT : EEXIST);
1173         }
1174         if (refcount_add(&dn->dn_holds, tag) == 1)
1175                 dbuf_add_ref(db, dnh);
1176         mutex_exit(&dn->dn_mtx);
1177 
1178         /* Now we can rely on the hold to prevent the dnode from moving. */
1179         zrl_remove(&dnh->dnh_zrlock);
1180 
1181         DNODE_VERIFY(dn);
1182         ASSERT3P(dn->dn_dbuf, ==, db);
1183         ASSERT3U(dn->dn_object, ==, object);
1184         dbuf_rele(db, FTAG);
1185 
1186         *dnp = dn;
1187         return (0);
1188 }
1189 
1190 /*
1191  * Return held dnode if the object is allocated, NULL if not.
1192  */
1193 int
1194 dnode_hold(objset_t *os, uint64_t object, void *tag, dnode_t **dnp)
1195 {
1196         return (dnode_hold_impl(os, object, DNODE_MUST_BE_ALLOCATED, tag, dnp));
1197 }
1198 
1199 /*
1200  * Can only add a reference if there is already at least one
1201  * reference on the dnode.  Returns FALSE if unable to add a
1202  * new reference.
1203  */
1204 boolean_t
1205 dnode_add_ref(dnode_t *dn, void *tag)
1206 {
1207         mutex_enter(&dn->dn_mtx);
1208         if (refcount_is_zero(&dn->dn_holds)) {
1209                 mutex_exit(&dn->dn_mtx);
1210                 return (FALSE);
1211         }
1212         VERIFY(1 < refcount_add(&dn->dn_holds, tag));
1213         mutex_exit(&dn->dn_mtx);
1214         return (TRUE);
1215 }
1216 
1217 void
1218 dnode_rele(dnode_t *dn, void *tag)
1219 {
1220         mutex_enter(&dn->dn_mtx);
1221         dnode_rele_and_unlock(dn, tag);
1222 }
1223 
1224 void
1225 dnode_rele_and_unlock(dnode_t *dn, void *tag)
1226 {
1227         uint64_t refs;
1228         /* Get while the hold prevents the dnode from moving. */
1229         dmu_buf_impl_t *db = dn->dn_dbuf;
1230         dnode_handle_t *dnh = dn->dn_handle;
1231 
1232         refs = refcount_remove(&dn->dn_holds, tag);
1233         mutex_exit(&dn->dn_mtx);
1234 
1235         /*
1236          * It's unsafe to release the last hold on a dnode by dnode_rele() or
1237          * indirectly by dbuf_rele() while relying on the dnode handle to
1238          * prevent the dnode from moving, since releasing the last hold could
1239          * result in the dnode's parent dbuf evicting its dnode handles. For
1240          * that reason anyone calling dnode_rele() or dbuf_rele() without some
1241          * other direct or indirect hold on the dnode must first drop the dnode
1242          * handle.
1243          */
1244         ASSERT(refs > 0 || dnh->dnh_zrlock.zr_owner != curthread);
1245 
1246         /* NOTE: the DNODE_DNODE does not have a dn_dbuf */
1247         if (refs == 0 && db != NULL) {
1248                 /*
1249                  * Another thread could add a hold to the dnode handle in
1250                  * dnode_hold_impl() while holding the parent dbuf. Since the
1251                  * hold on the parent dbuf prevents the handle from being
1252                  * destroyed, the hold on the handle is OK. We can't yet assert
1253                  * that the handle has zero references, but that will be
1254                  * asserted anyway when the handle gets destroyed.
1255                  */
1256                 dbuf_rele(db, dnh);
1257         }
1258 }
1259 
1260 void
1261 dnode_setdirty(dnode_t *dn, dmu_tx_t *tx)
1262 {
1263         objset_t *os = dn->dn_objset;
1264         uint64_t txg = tx->tx_txg;
1265 
1266         if (DMU_OBJECT_IS_SPECIAL(dn->dn_object)) {
1267                 dsl_dataset_dirty(os->os_dsl_dataset, tx);
1268                 return;
1269         }
1270 
1271         DNODE_VERIFY(dn);
1272 
1273 #ifdef ZFS_DEBUG
1274         mutex_enter(&dn->dn_mtx);
1275         ASSERT(dn->dn_phys->dn_type || dn->dn_allocated_txg);
1276         ASSERT(dn->dn_free_txg == 0 || dn->dn_free_txg >= txg);
1277         mutex_exit(&dn->dn_mtx);
1278 #endif
1279 
1280         /*
1281          * Determine old uid/gid when necessary
1282          */
1283         dmu_objset_userquota_get_ids(dn, B_TRUE, tx);
1284 
1285         multilist_t *dirtylist = os->os_dirty_dnodes[txg & TXG_MASK];
1286         multilist_sublist_t *mls = multilist_sublist_lock_obj(dirtylist, dn);
1287 
1288         /*
1289          * If we are already marked dirty, we're done.
1290          */
1291         if (list_link_active(&dn->dn_dirty_link[txg & TXG_MASK])) {
1292                 multilist_sublist_unlock(mls);
1293                 return;
1294         }
1295 
1296         ASSERT(!refcount_is_zero(&dn->dn_holds) ||
1297             !avl_is_empty(&dn->dn_dbufs));
1298         ASSERT(dn->dn_datablksz != 0);
1299         ASSERT0(dn->dn_next_bonuslen[txg&TXG_MASK]);
1300         ASSERT0(dn->dn_next_blksz[txg&TXG_MASK]);
1301         ASSERT0(dn->dn_next_bonustype[txg&TXG_MASK]);
1302 
1303         dprintf_ds(os->os_dsl_dataset, "obj=%llu txg=%llu\n",
1304             dn->dn_object, txg);
1305 
1306         multilist_sublist_insert_head(mls, dn);
1307 
1308         multilist_sublist_unlock(mls);
1309 
1310         /*
1311          * The dnode maintains a hold on its containing dbuf as
1312          * long as there are holds on it.  Each instantiated child
1313          * dbuf maintains a hold on the dnode.  When the last child
1314          * drops its hold, the dnode will drop its hold on the
1315          * containing dbuf. We add a "dirty hold" here so that the
1316          * dnode will hang around after we finish processing its
1317          * children.
1318          */
1319         VERIFY(dnode_add_ref(dn, (void *)(uintptr_t)tx->tx_txg));
1320 
1321         (void) dbuf_dirty(dn->dn_dbuf, tx);
1322 
1323         dsl_dataset_dirty(os->os_dsl_dataset, tx);
1324 }
1325 
1326 void
1327 dnode_free(dnode_t *dn, dmu_tx_t *tx)
1328 {
1329         mutex_enter(&dn->dn_mtx);
1330         if (dn->dn_type == DMU_OT_NONE || dn->dn_free_txg) {
1331                 mutex_exit(&dn->dn_mtx);
1332                 return;
1333         }
1334         dn->dn_free_txg = tx->tx_txg;
1335         mutex_exit(&dn->dn_mtx);
1336 
1337         dnode_setdirty(dn, tx);
1338 }
1339 
1340 /*
1341  * Try to change the block size for the indicated dnode.  This can only
1342  * succeed if there are no blocks allocated or dirty beyond first block
1343  */
1344 int
1345 dnode_set_blksz(dnode_t *dn, uint64_t size, int ibs, dmu_tx_t *tx)
1346 {
1347         dmu_buf_impl_t *db;
1348         int err;
1349 
1350         ASSERT3U(size, <=, spa_maxblocksize(dmu_objset_spa(dn->dn_objset)));
1351         if (size == 0)
1352                 size = SPA_MINBLOCKSIZE;
1353         else
1354                 size = P2ROUNDUP(size, SPA_MINBLOCKSIZE);
1355 
1356         if (ibs == dn->dn_indblkshift)
1357                 ibs = 0;
1358 
1359         if (size >> SPA_MINBLOCKSHIFT == dn->dn_datablkszsec && ibs == 0)
1360                 return (0);
1361 
1362         rw_enter(&dn->dn_struct_rwlock, RW_WRITER);
1363 
1364         /* Check for any allocated blocks beyond the first */
1365         if (dn->dn_maxblkid != 0)
1366                 goto fail;
1367 
1368         mutex_enter(&dn->dn_dbufs_mtx);
1369         for (db = avl_first(&dn->dn_dbufs); db != NULL;
1370             db = AVL_NEXT(&dn->dn_dbufs, db)) {
1371                 if (db->db_blkid != 0 && db->db_blkid != DMU_BONUS_BLKID &&
1372                     db->db_blkid != DMU_SPILL_BLKID) {
1373                         mutex_exit(&dn->dn_dbufs_mtx);
1374                         goto fail;
1375                 }
1376         }
1377         mutex_exit(&dn->dn_dbufs_mtx);
1378 
1379         if (ibs && dn->dn_nlevels != 1)
1380                 goto fail;
1381 
1382         /* resize the old block */
1383         err = dbuf_hold_impl(dn, 0, 0, TRUE, FALSE, FTAG, &db);
1384         if (err == 0)
1385                 dbuf_new_size(db, size, tx);
1386         else if (err != ENOENT)
1387                 goto fail;
1388 
1389         dnode_setdblksz(dn, size);
1390         dnode_setdirty(dn, tx);
1391         dn->dn_next_blksz[tx->tx_txg&TXG_MASK] = size;
1392         if (ibs) {
1393                 dn->dn_indblkshift = ibs;
1394                 dn->dn_next_indblkshift[tx->tx_txg&TXG_MASK] = ibs;
1395         }
1396         /* rele after we have fixed the blocksize in the dnode */
1397         if (db)
1398                 dbuf_rele(db, FTAG);
1399 
1400         rw_exit(&dn->dn_struct_rwlock);
1401         return (0);
1402 
1403 fail:
1404         rw_exit(&dn->dn_struct_rwlock);
1405         return (SET_ERROR(ENOTSUP));
1406 }
1407 
1408 /* read-holding callers must not rely on the lock being continuously held */
1409 void
1410 dnode_new_blkid(dnode_t *dn, uint64_t blkid, dmu_tx_t *tx, boolean_t have_read)
1411 {
1412         uint64_t txgoff = tx->tx_txg & TXG_MASK;
1413         int epbs, new_nlevels;
1414         uint64_t sz;
1415 
1416         ASSERT(blkid != DMU_BONUS_BLKID);
1417 
1418         ASSERT(have_read ?
1419             RW_READ_HELD(&dn->dn_struct_rwlock) :
1420             RW_WRITE_HELD(&dn->dn_struct_rwlock));
1421 
1422         /*
1423          * if we have a read-lock, check to see if we need to do any work
1424          * before upgrading to a write-lock.
1425          */
1426         if (have_read) {
1427                 if (blkid <= dn->dn_maxblkid)
1428                         return;
1429 
1430                 if (!rw_tryupgrade(&dn->dn_struct_rwlock)) {
1431                         rw_exit(&dn->dn_struct_rwlock);
1432                         rw_enter(&dn->dn_struct_rwlock, RW_WRITER);
1433                 }
1434         }
1435 
1436         if (blkid <= dn->dn_maxblkid)
1437                 goto out;
1438 
1439         dn->dn_maxblkid = blkid;
1440 
1441         /*
1442          * Compute the number of levels necessary to support the new maxblkid.
1443          */
1444         new_nlevels = 1;
1445         epbs = dn->dn_indblkshift - SPA_BLKPTRSHIFT;
1446         for (sz = dn->dn_nblkptr;
1447             sz <= blkid && sz >= dn->dn_nblkptr; sz <<= epbs)
1448                 new_nlevels++;
1449 
1450         if (new_nlevels > dn->dn_nlevels) {
1451                 int old_nlevels = dn->dn_nlevels;
1452                 dmu_buf_impl_t *db;
1453                 list_t *list;
1454                 dbuf_dirty_record_t *new, *dr, *dr_next;
1455 
1456                 dn->dn_nlevels = new_nlevels;
1457 
1458                 ASSERT3U(new_nlevels, >, dn->dn_next_nlevels[txgoff]);
1459                 dn->dn_next_nlevels[txgoff] = new_nlevels;
1460 
1461                 /* dirty the left indirects */
1462                 db = dbuf_hold_level(dn, old_nlevels, 0, FTAG);
1463                 ASSERT(db != NULL);
1464                 new = dbuf_dirty(db, tx);
1465                 dbuf_rele(db, FTAG);
1466 
1467                 /* transfer the dirty records to the new indirect */
1468                 mutex_enter(&dn->dn_mtx);
1469                 mutex_enter(&new->dt.di.dr_mtx);
1470                 list = &dn->dn_dirty_records[txgoff];
1471                 for (dr = list_head(list); dr; dr = dr_next) {
1472                         dr_next = list_next(&dn->dn_dirty_records[txgoff], dr);
1473                         if (dr->dr_dbuf->db_level != new_nlevels-1 &&
1474                             dr->dr_dbuf->db_blkid != DMU_BONUS_BLKID &&
1475                             dr->dr_dbuf->db_blkid != DMU_SPILL_BLKID) {
1476                                 ASSERT(dr->dr_dbuf->db_level == old_nlevels-1);
1477                                 list_remove(&dn->dn_dirty_records[txgoff], dr);
1478                                 list_insert_tail(&new->dt.di.dr_children, dr);
1479                                 dr->dr_parent = new;
1480                         }
1481                 }
1482                 mutex_exit(&new->dt.di.dr_mtx);
1483                 mutex_exit(&dn->dn_mtx);
1484         }
1485 
1486 out:
1487         if (have_read)
1488                 rw_downgrade(&dn->dn_struct_rwlock);
1489 }
1490 
1491 static void
1492 dnode_dirty_l1(dnode_t *dn, uint64_t l1blkid, dmu_tx_t *tx)
1493 {
1494         dmu_buf_impl_t *db = dbuf_hold_level(dn, 1, l1blkid, FTAG);
1495         if (db != NULL) {
1496                 dmu_buf_will_dirty(&db->db, tx);
1497                 dbuf_rele(db, FTAG);
1498         }
1499 }
1500 
1501 void
1502 dnode_free_range(dnode_t *dn, uint64_t off, uint64_t len, dmu_tx_t *tx)
1503 {
1504         dmu_buf_impl_t *db;
1505         uint64_t blkoff, blkid, nblks;
1506         int blksz, blkshift, head, tail;
1507         int trunc = FALSE;
1508         int epbs;
1509 
1510         rw_enter(&dn->dn_struct_rwlock, RW_WRITER);
1511         blksz = dn->dn_datablksz;
1512         blkshift = dn->dn_datablkshift;
1513         epbs = dn->dn_indblkshift - SPA_BLKPTRSHIFT;
1514 
1515         if (len == DMU_OBJECT_END) {
1516                 len = UINT64_MAX - off;
1517                 trunc = TRUE;
1518         }
1519 
1520         /*
1521          * First, block align the region to free:
1522          */
1523         if (ISP2(blksz)) {
1524                 head = P2NPHASE(off, blksz);
1525                 blkoff = P2PHASE(off, blksz);
1526                 if ((off >> blkshift) > dn->dn_maxblkid)
1527                         goto out;
1528         } else {
1529                 ASSERT(dn->dn_maxblkid == 0);
1530                 if (off == 0 && len >= blksz) {
1531                         /*
1532                          * Freeing the whole block; fast-track this request.
1533                          * Note that we won't dirty any indirect blocks,
1534                          * which is fine because we will be freeing the entire
1535                          * file and thus all indirect blocks will be freed
1536                          * by free_children().
1537                          */
1538                         blkid = 0;
1539                         nblks = 1;
1540                         goto done;
1541                 } else if (off >= blksz) {
1542                         /* Freeing past end-of-data */
1543                         goto out;
1544                 } else {
1545                         /* Freeing part of the block. */
1546                         head = blksz - off;
1547                         ASSERT3U(head, >, 0);
1548                 }
1549                 blkoff = off;
1550         }
1551         /* zero out any partial block data at the start of the range */
1552         if (head) {
1553                 ASSERT3U(blkoff + head, ==, blksz);
1554                 if (len < head)
1555                         head = len;
1556                 if (dbuf_hold_impl(dn, 0, dbuf_whichblock(dn, 0, off),
1557                     TRUE, FALSE, FTAG, &db) == 0) {
1558                         caddr_t data;
1559 
1560                         /* don't dirty if it isn't on disk and isn't dirty */
1561                         if (db->db_last_dirty ||
1562                             (db->db_blkptr && !BP_IS_HOLE(db->db_blkptr))) {
1563                                 rw_exit(&dn->dn_struct_rwlock);
1564                                 dmu_buf_will_dirty(&db->db, tx);
1565                                 rw_enter(&dn->dn_struct_rwlock, RW_WRITER);
1566                                 data = db->db.db_data;
1567                                 bzero(data + blkoff, head);
1568                         }
1569                         dbuf_rele(db, FTAG);
1570                 }
1571                 off += head;
1572                 len -= head;
1573         }
1574 
1575         /* If the range was less than one block, we're done */
1576         if (len == 0)
1577                 goto out;
1578 
1579         /* If the remaining range is past end of file, we're done */
1580         if ((off >> blkshift) > dn->dn_maxblkid)
1581                 goto out;
1582 
1583         ASSERT(ISP2(blksz));
1584         if (trunc)
1585                 tail = 0;
1586         else
1587                 tail = P2PHASE(len, blksz);
1588 
1589         ASSERT0(P2PHASE(off, blksz));
1590         /* zero out any partial block data at the end of the range */
1591         if (tail) {
1592                 if (len < tail)
1593                         tail = len;
1594                 if (dbuf_hold_impl(dn, 0, dbuf_whichblock(dn, 0, off+len),
1595                     TRUE, FALSE, FTAG, &db) == 0) {
1596                         /* don't dirty if not on disk and not dirty */
1597                         if (db->db_last_dirty ||
1598                             (db->db_blkptr && !BP_IS_HOLE(db->db_blkptr))) {
1599                                 rw_exit(&dn->dn_struct_rwlock);
1600                                 dmu_buf_will_dirty(&db->db, tx);
1601                                 rw_enter(&dn->dn_struct_rwlock, RW_WRITER);
1602                                 bzero(db->db.db_data, tail);
1603                         }
1604                         dbuf_rele(db, FTAG);
1605                 }
1606                 len -= tail;
1607         }
1608 
1609         /* If the range did not include a full block, we are done */
1610         if (len == 0)
1611                 goto out;
1612 
1613         ASSERT(IS_P2ALIGNED(off, blksz));
1614         ASSERT(trunc || IS_P2ALIGNED(len, blksz));
1615         blkid = off >> blkshift;
1616         nblks = len >> blkshift;
1617         if (trunc)
1618                 nblks += 1;
1619 
1620         /*
1621          * Dirty all the indirect blocks in this range.  Note that only
1622          * the first and last indirect blocks can actually be written
1623          * (if they were partially freed) -- they must be dirtied, even if
1624          * they do not exist on disk yet.  The interior blocks will
1625          * be freed by free_children(), so they will not actually be written.
1626          * Even though these interior blocks will not be written, we
1627          * dirty them for two reasons:
1628          *
1629          *  - It ensures that the indirect blocks remain in memory until
1630          *    syncing context.  (They have already been prefetched by
1631          *    dmu_tx_hold_free(), so we don't have to worry about reading
1632          *    them serially here.)
1633          *
1634          *  - The dirty space accounting will put pressure on the txg sync
1635          *    mechanism to begin syncing, and to delay transactions if there
1636          *    is a large amount of freeing.  Even though these indirect
1637          *    blocks will not be written, we could need to write the same
1638          *    amount of space if we copy the freed BPs into deadlists.
1639          */
1640         if (dn->dn_nlevels > 1) {
1641                 uint64_t first, last;
1642 
1643                 first = blkid >> epbs;
1644                 dnode_dirty_l1(dn, first, tx);
1645                 if (trunc)
1646                         last = dn->dn_maxblkid >> epbs;
1647                 else
1648                         last = (blkid + nblks - 1) >> epbs;
1649                 if (last != first)
1650                         dnode_dirty_l1(dn, last, tx);
1651 
1652                 int shift = dn->dn_datablkshift + dn->dn_indblkshift -
1653                     SPA_BLKPTRSHIFT;
1654                 for (uint64_t i = first + 1; i < last; i++) {
1655                         /*
1656                          * Set i to the blockid of the next non-hole
1657                          * level-1 indirect block at or after i.  Note
1658                          * that dnode_next_offset() operates in terms of
1659                          * level-0-equivalent bytes.
1660                          */
1661                         uint64_t ibyte = i << shift;
1662                         int err = dnode_next_offset(dn, DNODE_FIND_HAVELOCK,
1663                             &ibyte, 2, 1, 0);
1664                         i = ibyte >> shift;
1665                         if (i >= last)
1666                                 break;
1667 
1668                         /*
1669                          * Normally we should not see an error, either
1670                          * from dnode_next_offset() or dbuf_hold_level()
1671                          * (except for ESRCH from dnode_next_offset).
1672                          * If there is an i/o error, then when we read
1673                          * this block in syncing context, it will use
1674                          * ZIO_FLAG_MUSTSUCCEED, and thus hang/panic according
1675                          * to the "failmode" property.  dnode_next_offset()
1676                          * doesn't have a flag to indicate MUSTSUCCEED.
1677                          */
1678                         if (err != 0)
1679                                 break;
1680 
1681                         dnode_dirty_l1(dn, i, tx);
1682                 }
1683         }
1684 
1685 done:
1686         /*
1687          * Add this range to the dnode range list.
1688          * We will finish up this free operation in the syncing phase.
1689          */
1690         mutex_enter(&dn->dn_mtx);
1691         int txgoff = tx->tx_txg & TXG_MASK;
1692         if (dn->dn_free_ranges[txgoff] == NULL) {
1693                 dn->dn_free_ranges[txgoff] =
1694                     range_tree_create(NULL, NULL, &dn->dn_mtx);
1695         }
1696         range_tree_clear(dn->dn_free_ranges[txgoff], blkid, nblks);
1697         range_tree_add(dn->dn_free_ranges[txgoff], blkid, nblks);
1698         dprintf_dnode(dn, "blkid=%llu nblks=%llu txg=%llu\n",
1699             blkid, nblks, tx->tx_txg);
1700         mutex_exit(&dn->dn_mtx);
1701 
1702         dbuf_free_range(dn, blkid, blkid + nblks - 1, tx);
1703         dnode_setdirty(dn, tx);
1704 out:
1705 
1706         rw_exit(&dn->dn_struct_rwlock);
1707 }
1708 
1709 static boolean_t
1710 dnode_spill_freed(dnode_t *dn)
1711 {
1712         int i;
1713 
1714         mutex_enter(&dn->dn_mtx);
1715         for (i = 0; i < TXG_SIZE; i++) {
1716                 if (dn->dn_rm_spillblk[i] == DN_KILL_SPILLBLK)
1717                         break;
1718         }
1719         mutex_exit(&dn->dn_mtx);
1720         return (i < TXG_SIZE);
1721 }
1722 
1723 /* return TRUE if this blkid was freed in a recent txg, or FALSE if it wasn't */
1724 uint64_t
1725 dnode_block_freed(dnode_t *dn, uint64_t blkid)
1726 {
1727         void *dp = spa_get_dsl(dn->dn_objset->os_spa);
1728         int i;
1729 
1730         if (blkid == DMU_BONUS_BLKID)
1731                 return (FALSE);
1732 
1733         /*
1734          * If we're in the process of opening the pool, dp will not be
1735          * set yet, but there shouldn't be anything dirty.
1736          */
1737         if (dp == NULL)
1738                 return (FALSE);
1739 
1740         if (dn->dn_free_txg)
1741                 return (TRUE);
1742 
1743         if (blkid == DMU_SPILL_BLKID)
1744                 return (dnode_spill_freed(dn));
1745 
1746         mutex_enter(&dn->dn_mtx);
1747         for (i = 0; i < TXG_SIZE; i++) {
1748                 if (dn->dn_free_ranges[i] != NULL &&
1749                     range_tree_contains(dn->dn_free_ranges[i], blkid, 1))
1750                         break;
1751         }
1752         mutex_exit(&dn->dn_mtx);
1753         return (i < TXG_SIZE);
1754 }
1755 
1756 /* call from syncing context when we actually write/free space for this dnode */
1757 void
1758 dnode_diduse_space(dnode_t *dn, int64_t delta)
1759 {
1760         uint64_t space;
1761         dprintf_dnode(dn, "dn=%p dnp=%p used=%llu delta=%lld\n",
1762             dn, dn->dn_phys,
1763             (u_longlong_t)dn->dn_phys->dn_used,
1764             (longlong_t)delta);
1765 
1766         mutex_enter(&dn->dn_mtx);
1767         space = DN_USED_BYTES(dn->dn_phys);
1768         if (delta > 0) {
1769                 ASSERT3U(space + delta, >=, space); /* no overflow */
1770         } else {
1771                 ASSERT3U(space, >=, -delta); /* no underflow */
1772         }
1773         space += delta;
1774         if (spa_version(dn->dn_objset->os_spa) < SPA_VERSION_DNODE_BYTES) {
1775                 ASSERT((dn->dn_phys->dn_flags & DNODE_FLAG_USED_BYTES) == 0);
1776                 ASSERT0(P2PHASE(space, 1<<DEV_BSHIFT));
1777                 dn->dn_phys->dn_used = space >> DEV_BSHIFT;
1778         } else {
1779                 dn->dn_phys->dn_used = space;
1780                 dn->dn_phys->dn_flags |= DNODE_FLAG_USED_BYTES;
1781         }
1782         mutex_exit(&dn->dn_mtx);
1783 }
1784 
1785 /*
1786  * Scans a block at the indicated "level" looking for a hole or data,
1787  * depending on 'flags'.
1788  *
1789  * If level > 0, then we are scanning an indirect block looking at its
1790  * pointers.  If level == 0, then we are looking at a block of dnodes.
1791  *
1792  * If we don't find what we are looking for in the block, we return ESRCH.
1793  * Otherwise, return with *offset pointing to the beginning (if searching
1794  * forwards) or end (if searching backwards) of the range covered by the
1795  * block pointer we matched on (or dnode).
1796  *
1797  * The basic search algorithm used below by dnode_next_offset() is to
1798  * use this function to search up the block tree (widen the search) until
1799  * we find something (i.e., we don't return ESRCH) and then search back
1800  * down the tree (narrow the search) until we reach our original search
1801  * level.
1802  */
1803 static int
1804 dnode_next_offset_level(dnode_t *dn, int flags, uint64_t *offset,
1805     int lvl, uint64_t blkfill, uint64_t txg)
1806 {
1807         dmu_buf_impl_t *db = NULL;
1808         void *data = NULL;
1809         uint64_t epbs = dn->dn_phys->dn_indblkshift - SPA_BLKPTRSHIFT;
1810         uint64_t epb = 1ULL << epbs;
1811         uint64_t minfill, maxfill;
1812         boolean_t hole;
1813         int i, inc, error, span;
1814 
1815         dprintf("probing object %llu offset %llx level %d of %u\n",
1816             dn->dn_object, *offset, lvl, dn->dn_phys->dn_nlevels);
1817 
1818         hole = ((flags & DNODE_FIND_HOLE) != 0);
1819         inc = (flags & DNODE_FIND_BACKWARDS) ? -1 : 1;
1820         ASSERT(txg == 0 || !hole);
1821 
1822         if (lvl == dn->dn_phys->dn_nlevels) {
1823                 error = 0;
1824                 epb = dn->dn_phys->dn_nblkptr;
1825                 data = dn->dn_phys->dn_blkptr;
1826         } else {
1827                 uint64_t blkid = dbuf_whichblock(dn, lvl, *offset);
1828                 error = dbuf_hold_impl(dn, lvl, blkid, TRUE, FALSE, FTAG, &db);
1829                 if (error) {
1830                         if (error != ENOENT)
1831                                 return (error);
1832                         if (hole)
1833                                 return (0);
1834                         /*
1835                          * This can only happen when we are searching up
1836                          * the block tree for data.  We don't really need to
1837                          * adjust the offset, as we will just end up looking
1838                          * at the pointer to this block in its parent, and its
1839                          * going to be unallocated, so we will skip over it.
1840                          */
1841                         return (SET_ERROR(ESRCH));
1842                 }
1843                 error = dbuf_read(db, NULL, DB_RF_CANFAIL | DB_RF_HAVESTRUCT);
1844                 if (error) {
1845                         dbuf_rele(db, FTAG);
1846                         return (error);
1847                 }
1848                 data = db->db.db_data;
1849         }
1850 
1851 
1852         if (db != NULL && txg != 0 && (db->db_blkptr == NULL ||
1853             db->db_blkptr->blk_birth <= txg ||
1854             BP_IS_HOLE(db->db_blkptr))) {
1855                 /*
1856                  * This can only happen when we are searching up the tree
1857                  * and these conditions mean that we need to keep climbing.
1858                  */
1859                 error = SET_ERROR(ESRCH);
1860         } else if (lvl == 0) {
1861                 dnode_phys_t *dnp = data;
1862                 span = DNODE_SHIFT;
1863                 ASSERT(dn->dn_type == DMU_OT_DNODE);
1864 
1865                 for (i = (*offset >> span) & (blkfill - 1);
1866                     i >= 0 && i < blkfill; i += inc) {
1867                         if ((dnp[i].dn_type == DMU_OT_NONE) == hole)
1868                                 break;
1869                         *offset += (1ULL << span) * inc;
1870                 }
1871                 if (i < 0 || i == blkfill)
1872                         error = SET_ERROR(ESRCH);
1873         } else {
1874                 blkptr_t *bp = data;
1875                 uint64_t start = *offset;
1876                 span = (lvl - 1) * epbs + dn->dn_datablkshift;
1877                 minfill = 0;
1878                 maxfill = blkfill << ((lvl - 1) * epbs);
1879 
1880                 if (hole)
1881                         maxfill--;
1882                 else
1883                         minfill++;
1884 
1885                 *offset = *offset >> span;
1886                 for (i = BF64_GET(*offset, 0, epbs);
1887                     i >= 0 && i < epb; i += inc) {
1888                         if (BP_GET_FILL(&bp[i]) >= minfill &&
1889                             BP_GET_FILL(&bp[i]) <= maxfill &&
1890                             (hole || bp[i].blk_birth > txg))
1891                                 break;
1892                         if (inc > 0 || *offset > 0)
1893                                 *offset += inc;
1894                 }
1895                 *offset = *offset << span;
1896                 if (inc < 0) {
1897                         /* traversing backwards; position offset at the end */
1898                         ASSERT3U(*offset, <=, start);
1899                         *offset = MIN(*offset + (1ULL << span) - 1, start);
1900                 } else if (*offset < start) {
1901                         *offset = start;
1902                 }
1903                 if (i < 0 || i >= epb)
1904                         error = SET_ERROR(ESRCH);
1905         }
1906 
1907         if (db)
1908                 dbuf_rele(db, FTAG);
1909 
1910         return (error);
1911 }
1912 
1913 /*
1914  * Find the next hole, data, or sparse region at or after *offset.
1915  * The value 'blkfill' tells us how many items we expect to find
1916  * in an L0 data block; this value is 1 for normal objects,
1917  * DNODES_PER_BLOCK for the meta dnode, and some fraction of
1918  * DNODES_PER_BLOCK when searching for sparse regions thereof.
1919  *
1920  * Examples:
1921  *
1922  * dnode_next_offset(dn, flags, offset, 1, 1, 0);
1923  *      Finds the next/previous hole/data in a file.
1924  *      Used in dmu_offset_next().
1925  *
1926  * dnode_next_offset(mdn, flags, offset, 0, DNODES_PER_BLOCK, txg);
1927  *      Finds the next free/allocated dnode an objset's meta-dnode.
1928  *      Only finds objects that have new contents since txg (ie.
1929  *      bonus buffer changes and content removal are ignored).
1930  *      Used in dmu_object_next().
1931  *
1932  * dnode_next_offset(mdn, DNODE_FIND_HOLE, offset, 2, DNODES_PER_BLOCK >> 2, 0);
1933  *      Finds the next L2 meta-dnode bp that's at most 1/4 full.
1934  *      Used in dmu_object_alloc().
1935  */
1936 int
1937 dnode_next_offset(dnode_t *dn, int flags, uint64_t *offset,
1938     int minlvl, uint64_t blkfill, uint64_t txg)
1939 {
1940         uint64_t initial_offset = *offset;
1941         int lvl, maxlvl;
1942         int error = 0;
1943 
1944         if (!(flags & DNODE_FIND_HAVELOCK))
1945                 rw_enter(&dn->dn_struct_rwlock, RW_READER);
1946 
1947         if (dn->dn_phys->dn_nlevels == 0) {
1948                 error = SET_ERROR(ESRCH);
1949                 goto out;
1950         }
1951 
1952         if (dn->dn_datablkshift == 0) {
1953                 if (*offset < dn->dn_datablksz) {
1954                         if (flags & DNODE_FIND_HOLE)
1955                                 *offset = dn->dn_datablksz;
1956                 } else {
1957                         error = SET_ERROR(ESRCH);
1958                 }
1959                 goto out;
1960         }
1961 
1962         maxlvl = dn->dn_phys->dn_nlevels;
1963 
1964         for (lvl = minlvl; lvl <= maxlvl; lvl++) {
1965                 error = dnode_next_offset_level(dn,
1966                     flags, offset, lvl, blkfill, txg);
1967                 if (error != ESRCH)
1968                         break;
1969         }
1970 
1971         while (error == 0 && --lvl >= minlvl) {
1972                 error = dnode_next_offset_level(dn,
1973                     flags, offset, lvl, blkfill, txg);
1974         }
1975 
1976         /*
1977          * There's always a "virtual hole" at the end of the object, even
1978          * if all BP's which physically exist are non-holes.
1979          */
1980         if ((flags & DNODE_FIND_HOLE) && error == ESRCH && txg == 0 &&
1981             minlvl == 1 && blkfill == 1 && !(flags & DNODE_FIND_BACKWARDS)) {
1982                 error = 0;
1983         }
1984 
1985         if (error == 0 && (flags & DNODE_FIND_BACKWARDS ?
1986             initial_offset < *offset : initial_offset > *offset))
1987                 error = SET_ERROR(ESRCH);
1988 out:
1989         if (!(flags & DNODE_FIND_HAVELOCK))
1990                 rw_exit(&dn->dn_struct_rwlock);
1991 
1992         return (error);
1993 }