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