granicus.if.org Git - zfs/blob - module/zfs/dnode.c

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