sys/cddl/contrib/opensolaris/uts/common/fs/zfs/dnode.c

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