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