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