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