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