xref: /freebsd/stand/libsa/zfs/zfsimpl.c (revision 20bd59416dcacbd2b776fe49dfa193900f303287)
1 /*-
2  * Copyright (c) 2007 Doug Rabson
3  * All rights reserved.
4  *
5  * Redistribution and use in source and binary forms, with or without
6  * modification, are permitted provided that the following conditions
7  * are met:
8  * 1. Redistributions of source code must retain the above copyright
9  *    notice, this list of conditions and the following disclaimer.
10  * 2. Redistributions in binary form must reproduce the above copyright
11  *    notice, this list of conditions and the following disclaimer in the
12  *    documentation and/or other materials provided with the distribution.
13  *
14  * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND
15  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
16  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
17  * ARE DISCLAIMED.  IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE
18  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
19  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
20  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
21  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
22  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
23  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
24  * SUCH DAMAGE.
25  */
26 
27 #include <sys/cdefs.h>
28 __FBSDID("$FreeBSD$");
29 
30 /*
31  *	Stand-alone ZFS file reader.
32  */
33 
34 #include <sys/endian.h>
35 #include <sys/stat.h>
36 #include <sys/stdint.h>
37 #include <sys/list.h>
38 
39 #include "zfsimpl.h"
40 #include "zfssubr.c"
41 
42 
43 struct zfsmount {
44 	const spa_t	*spa;
45 	objset_phys_t	objset;
46 	uint64_t	rootobj;
47 };
48 static struct zfsmount zfsmount __unused;
49 
50 /*
51  * The indirect_child_t represents the vdev that we will read from, when we
52  * need to read all copies of the data (e.g. for scrub or reconstruction).
53  * For plain (non-mirror) top-level vdevs (i.e. is_vdev is not a mirror),
54  * ic_vdev is the same as is_vdev.  However, for mirror top-level vdevs,
55  * ic_vdev is a child of the mirror.
56  */
57 typedef struct indirect_child {
58 	void *ic_data;
59 	vdev_t *ic_vdev;
60 } indirect_child_t;
61 
62 /*
63  * The indirect_split_t represents one mapped segment of an i/o to the
64  * indirect vdev. For non-split (contiguously-mapped) blocks, there will be
65  * only one indirect_split_t, with is_split_offset==0 and is_size==io_size.
66  * For split blocks, there will be several of these.
67  */
68 typedef struct indirect_split {
69 	list_node_t is_node; /* link on iv_splits */
70 
71 	/*
72 	 * is_split_offset is the offset into the i/o.
73 	 * This is the sum of the previous splits' is_size's.
74 	 */
75 	uint64_t is_split_offset;
76 
77 	vdev_t *is_vdev; /* top-level vdev */
78 	uint64_t is_target_offset; /* offset on is_vdev */
79 	uint64_t is_size;
80 	int is_children; /* number of entries in is_child[] */
81 
82 	/*
83 	 * is_good_child is the child that we are currently using to
84 	 * attempt reconstruction.
85 	 */
86 	int is_good_child;
87 
88 	indirect_child_t is_child[1]; /* variable-length */
89 } indirect_split_t;
90 
91 /*
92  * The indirect_vsd_t is associated with each i/o to the indirect vdev.
93  * It is the "Vdev-Specific Data" in the zio_t's io_vsd.
94  */
95 typedef struct indirect_vsd {
96 	boolean_t iv_split_block;
97 	boolean_t iv_reconstruct;
98 
99 	list_t iv_splits; /* list of indirect_split_t's */
100 } indirect_vsd_t;
101 
102 /*
103  * List of all vdevs, chained through v_alllink.
104  */
105 static vdev_list_t zfs_vdevs;
106 
107  /*
108  * List of ZFS features supported for read
109  */
110 static const char *features_for_read[] = {
111 	"org.illumos:lz4_compress",
112 	"com.delphix:hole_birth",
113 	"com.delphix:extensible_dataset",
114 	"com.delphix:embedded_data",
115 	"org.open-zfs:large_blocks",
116 	"org.illumos:sha512",
117 	"org.illumos:skein",
118 	"org.zfsonlinux:large_dnode",
119 	"com.joyent:multi_vdev_crash_dump",
120 	"com.delphix:spacemap_histogram",
121 	"com.delphix:zpool_checkpoint",
122 	"com.delphix:spacemap_v2",
123 	"com.datto:encryption",
124 	"org.zfsonlinux:allocation_classes",
125 	"com.datto:resilver_defer",
126 	"com.delphix:device_removal",
127 	"com.delphix:obsolete_counts",
128 	NULL
129 };
130 
131 /*
132  * List of all pools, chained through spa_link.
133  */
134 static spa_list_t zfs_pools;
135 
136 static const dnode_phys_t *dnode_cache_obj;
137 static uint64_t dnode_cache_bn;
138 static char *dnode_cache_buf;
139 static char *zap_scratch;
140 static char *zfs_temp_buf, *zfs_temp_end, *zfs_temp_ptr;
141 
142 #define TEMP_SIZE	(1024 * 1024)
143 
144 static int zio_read(const spa_t *spa, const blkptr_t *bp, void *buf);
145 static int zfs_get_root(const spa_t *spa, uint64_t *objid);
146 static int zfs_rlookup(const spa_t *spa, uint64_t objnum, char *result);
147 static int zap_lookup(const spa_t *spa, const dnode_phys_t *dnode,
148     const char *name, uint64_t integer_size, uint64_t num_integers,
149     void *value);
150 static int objset_get_dnode(const spa_t *, const objset_phys_t *, uint64_t,
151     dnode_phys_t *);
152 static int dnode_read(const spa_t *, const dnode_phys_t *, off_t, void *,
153     size_t);
154 static int vdev_indirect_read(vdev_t *, const blkptr_t *, void *, off_t,
155     size_t);
156 static int vdev_mirror_read(vdev_t *, const blkptr_t *, void *, off_t, size_t);
157 vdev_indirect_mapping_t *vdev_indirect_mapping_open(spa_t *, objset_phys_t *,
158     uint64_t);
159 vdev_indirect_mapping_entry_phys_t *
160     vdev_indirect_mapping_duplicate_adjacent_entries(vdev_t *, uint64_t,
161     uint64_t, uint64_t *);
162 
163 static void
164 zfs_init(void)
165 {
166 	STAILQ_INIT(&zfs_vdevs);
167 	STAILQ_INIT(&zfs_pools);
168 
169 	zfs_temp_buf = malloc(TEMP_SIZE);
170 	zfs_temp_end = zfs_temp_buf + TEMP_SIZE;
171 	zfs_temp_ptr = zfs_temp_buf;
172 	dnode_cache_buf = malloc(SPA_MAXBLOCKSIZE);
173 	zap_scratch = malloc(SPA_MAXBLOCKSIZE);
174 
175 	zfs_init_crc();
176 }
177 
178 static void *
179 zfs_alloc(size_t size)
180 {
181 	char *ptr;
182 
183 	if (zfs_temp_ptr + size > zfs_temp_end) {
184 		panic("ZFS: out of temporary buffer space");
185 	}
186 	ptr = zfs_temp_ptr;
187 	zfs_temp_ptr += size;
188 
189 	return (ptr);
190 }
191 
192 static void
193 zfs_free(void *ptr, size_t size)
194 {
195 
196 	zfs_temp_ptr -= size;
197 	if (zfs_temp_ptr != ptr) {
198 		panic("ZFS: zfs_alloc()/zfs_free() mismatch");
199 	}
200 }
201 
202 static int
203 xdr_int(const unsigned char **xdr, int *ip)
204 {
205 	*ip = be32dec(*xdr);
206 	(*xdr) += 4;
207 	return (0);
208 }
209 
210 static int
211 xdr_u_int(const unsigned char **xdr, u_int *ip)
212 {
213 	*ip = be32dec(*xdr);
214 	(*xdr) += 4;
215 	return (0);
216 }
217 
218 static int
219 xdr_uint64_t(const unsigned char **xdr, uint64_t *lp)
220 {
221 	u_int hi, lo;
222 
223 	xdr_u_int(xdr, &hi);
224 	xdr_u_int(xdr, &lo);
225 	*lp = (((uint64_t) hi) << 32) | lo;
226 	return (0);
227 }
228 
229 static int
230 nvlist_find(const unsigned char *nvlist, const char *name, int type,
231 	    int *elementsp, void *valuep)
232 {
233 	const unsigned char *p, *pair;
234 	int junk;
235 	int encoded_size, decoded_size;
236 
237 	p = nvlist;
238 	xdr_int(&p, &junk);
239 	xdr_int(&p, &junk);
240 
241 	pair = p;
242 	xdr_int(&p, &encoded_size);
243 	xdr_int(&p, &decoded_size);
244 	while (encoded_size && decoded_size) {
245 		int namelen, pairtype, elements;
246 		const char *pairname;
247 
248 		xdr_int(&p, &namelen);
249 		pairname = (const char*) p;
250 		p += roundup(namelen, 4);
251 		xdr_int(&p, &pairtype);
252 
253 		if (!memcmp(name, pairname, namelen) && type == pairtype) {
254 			xdr_int(&p, &elements);
255 			if (elementsp)
256 				*elementsp = elements;
257 			if (type == DATA_TYPE_UINT64) {
258 				xdr_uint64_t(&p, (uint64_t *) valuep);
259 				return (0);
260 			} else if (type == DATA_TYPE_STRING) {
261 				int len;
262 				xdr_int(&p, &len);
263 				(*(const char**) valuep) = (const char*) p;
264 				return (0);
265 			} else if (type == DATA_TYPE_NVLIST
266 				   || type == DATA_TYPE_NVLIST_ARRAY) {
267 				(*(const unsigned char**) valuep) =
268 					 (const unsigned char*) p;
269 				return (0);
270 			} else {
271 				return (EIO);
272 			}
273 		} else {
274 			/*
275 			 * Not the pair we are looking for, skip to the next one.
276 			 */
277 			p = pair + encoded_size;
278 		}
279 
280 		pair = p;
281 		xdr_int(&p, &encoded_size);
282 		xdr_int(&p, &decoded_size);
283 	}
284 
285 	return (EIO);
286 }
287 
288 static int
289 nvlist_check_features_for_read(const unsigned char *nvlist)
290 {
291 	const unsigned char *p, *pair;
292 	int junk;
293 	int encoded_size, decoded_size;
294 	int rc;
295 
296 	rc = 0;
297 
298 	p = nvlist;
299 	xdr_int(&p, &junk);
300 	xdr_int(&p, &junk);
301 
302 	pair = p;
303 	xdr_int(&p, &encoded_size);
304 	xdr_int(&p, &decoded_size);
305 	while (encoded_size && decoded_size) {
306 		int namelen, pairtype;
307 		const char *pairname;
308 		int i, found;
309 
310 		found = 0;
311 
312 		xdr_int(&p, &namelen);
313 		pairname = (const char*) p;
314 		p += roundup(namelen, 4);
315 		xdr_int(&p, &pairtype);
316 
317 		for (i = 0; features_for_read[i] != NULL; i++) {
318 			if (!memcmp(pairname, features_for_read[i], namelen)) {
319 				found = 1;
320 				break;
321 			}
322 		}
323 
324 		if (!found) {
325 			printf("ZFS: unsupported feature: %s\n", pairname);
326 			rc = EIO;
327 		}
328 
329 		p = pair + encoded_size;
330 
331 		pair = p;
332 		xdr_int(&p, &encoded_size);
333 		xdr_int(&p, &decoded_size);
334 	}
335 
336 	return (rc);
337 }
338 
339 /*
340  * Return the next nvlist in an nvlist array.
341  */
342 static const unsigned char *
343 nvlist_next(const unsigned char *nvlist)
344 {
345 	const unsigned char *p, *pair;
346 	int junk;
347 	int encoded_size, decoded_size;
348 
349 	p = nvlist;
350 	xdr_int(&p, &junk);
351 	xdr_int(&p, &junk);
352 
353 	pair = p;
354 	xdr_int(&p, &encoded_size);
355 	xdr_int(&p, &decoded_size);
356 	while (encoded_size && decoded_size) {
357 		p = pair + encoded_size;
358 
359 		pair = p;
360 		xdr_int(&p, &encoded_size);
361 		xdr_int(&p, &decoded_size);
362 	}
363 
364 	return p;
365 }
366 
367 #ifdef TEST
368 
369 static const unsigned char *
370 nvlist_print(const unsigned char *nvlist, unsigned int indent)
371 {
372 	static const char* typenames[] = {
373 		"DATA_TYPE_UNKNOWN",
374 		"DATA_TYPE_BOOLEAN",
375 		"DATA_TYPE_BYTE",
376 		"DATA_TYPE_INT16",
377 		"DATA_TYPE_UINT16",
378 		"DATA_TYPE_INT32",
379 		"DATA_TYPE_UINT32",
380 		"DATA_TYPE_INT64",
381 		"DATA_TYPE_UINT64",
382 		"DATA_TYPE_STRING",
383 		"DATA_TYPE_BYTE_ARRAY",
384 		"DATA_TYPE_INT16_ARRAY",
385 		"DATA_TYPE_UINT16_ARRAY",
386 		"DATA_TYPE_INT32_ARRAY",
387 		"DATA_TYPE_UINT32_ARRAY",
388 		"DATA_TYPE_INT64_ARRAY",
389 		"DATA_TYPE_UINT64_ARRAY",
390 		"DATA_TYPE_STRING_ARRAY",
391 		"DATA_TYPE_HRTIME",
392 		"DATA_TYPE_NVLIST",
393 		"DATA_TYPE_NVLIST_ARRAY",
394 		"DATA_TYPE_BOOLEAN_VALUE",
395 		"DATA_TYPE_INT8",
396 		"DATA_TYPE_UINT8",
397 		"DATA_TYPE_BOOLEAN_ARRAY",
398 		"DATA_TYPE_INT8_ARRAY",
399 		"DATA_TYPE_UINT8_ARRAY"
400 	};
401 
402 	unsigned int i, j;
403 	const unsigned char *p, *pair;
404 	int junk;
405 	int encoded_size, decoded_size;
406 
407 	p = nvlist;
408 	xdr_int(&p, &junk);
409 	xdr_int(&p, &junk);
410 
411 	pair = p;
412 	xdr_int(&p, &encoded_size);
413 	xdr_int(&p, &decoded_size);
414 	while (encoded_size && decoded_size) {
415 		int namelen, pairtype, elements;
416 		const char *pairname;
417 
418 		xdr_int(&p, &namelen);
419 		pairname = (const char*) p;
420 		p += roundup(namelen, 4);
421 		xdr_int(&p, &pairtype);
422 
423 		for (i = 0; i < indent; i++)
424 			printf(" ");
425 		printf("%s %s", typenames[pairtype], pairname);
426 
427 		xdr_int(&p, &elements);
428 		switch (pairtype) {
429 		case DATA_TYPE_UINT64: {
430 			uint64_t val;
431 			xdr_uint64_t(&p, &val);
432 			printf(" = 0x%jx\n", (uintmax_t)val);
433 			break;
434 		}
435 
436 		case DATA_TYPE_STRING: {
437 			int len;
438 			xdr_int(&p, &len);
439 			printf(" = \"%s\"\n", p);
440 			break;
441 		}
442 
443 		case DATA_TYPE_NVLIST:
444 			printf("\n");
445 			nvlist_print(p, indent + 1);
446 			break;
447 
448 		case DATA_TYPE_NVLIST_ARRAY:
449 			for (j = 0; j < elements; j++) {
450 				printf("[%d]\n", j);
451 				p = nvlist_print(p, indent + 1);
452 				if (j != elements - 1) {
453 					for (i = 0; i < indent; i++)
454 						printf(" ");
455 					printf("%s %s", typenames[pairtype], pairname);
456 				}
457 			}
458 			break;
459 
460 		default:
461 			printf("\n");
462 		}
463 
464 		p = pair + encoded_size;
465 
466 		pair = p;
467 		xdr_int(&p, &encoded_size);
468 		xdr_int(&p, &decoded_size);
469 	}
470 
471 	return p;
472 }
473 
474 #endif
475 
476 static int
477 vdev_read_phys(vdev_t *vdev, const blkptr_t *bp, void *buf,
478     off_t offset, size_t size)
479 {
480 	size_t psize;
481 	int rc;
482 
483 	if (!vdev->v_phys_read)
484 		return (EIO);
485 
486 	if (bp) {
487 		psize = BP_GET_PSIZE(bp);
488 	} else {
489 		psize = size;
490 	}
491 
492 	/*printf("ZFS: reading %zu bytes at 0x%jx to %p\n", psize, (uintmax_t)offset, buf);*/
493 	rc = vdev->v_phys_read(vdev, vdev->v_read_priv, offset, buf, psize);
494 	if (rc)
495 		return (rc);
496 	if (bp != NULL)
497 		return (zio_checksum_verify(vdev->spa, bp, buf));
498 
499 	return (0);
500 }
501 
502 typedef struct remap_segment {
503 	vdev_t *rs_vd;
504 	uint64_t rs_offset;
505 	uint64_t rs_asize;
506 	uint64_t rs_split_offset;
507 	list_node_t rs_node;
508 } remap_segment_t;
509 
510 static remap_segment_t *
511 rs_alloc(vdev_t *vd, uint64_t offset, uint64_t asize, uint64_t split_offset)
512 {
513 	remap_segment_t *rs = malloc(sizeof (remap_segment_t));
514 
515 	if (rs != NULL) {
516 		rs->rs_vd = vd;
517 		rs->rs_offset = offset;
518 		rs->rs_asize = asize;
519 		rs->rs_split_offset = split_offset;
520 	}
521 
522 	return (rs);
523 }
524 
525 vdev_indirect_mapping_t *
526 vdev_indirect_mapping_open(spa_t *spa, objset_phys_t *os,
527     uint64_t mapping_object)
528 {
529 	vdev_indirect_mapping_t *vim;
530 	vdev_indirect_mapping_phys_t *vim_phys;
531 	int rc;
532 
533 	vim = calloc(1, sizeof (*vim));
534 	if (vim == NULL)
535 		return (NULL);
536 
537 	vim->vim_dn = calloc(1, sizeof (*vim->vim_dn));
538 	if (vim->vim_dn == NULL) {
539 		free(vim);
540 		return (NULL);
541 	}
542 
543 	rc = objset_get_dnode(spa, os, mapping_object, vim->vim_dn);
544 	if (rc != 0) {
545 		free(vim->vim_dn);
546 		free(vim);
547 		return (NULL);
548 	}
549 
550 	vim->vim_spa = spa;
551 	vim->vim_phys = malloc(sizeof (*vim->vim_phys));
552 	if (vim->vim_phys == NULL) {
553 		free(vim->vim_dn);
554 		free(vim);
555 		return (NULL);
556 	}
557 
558 	vim_phys = (vdev_indirect_mapping_phys_t *)DN_BONUS(vim->vim_dn);
559 	*vim->vim_phys = *vim_phys;
560 
561 	vim->vim_objset = os;
562 	vim->vim_object = mapping_object;
563 	vim->vim_entries = NULL;
564 
565 	vim->vim_havecounts =
566 	    (vim->vim_dn->dn_bonuslen > VDEV_INDIRECT_MAPPING_SIZE_V0);
567 	return (vim);
568 }
569 
570 /*
571  * Compare an offset with an indirect mapping entry; there are three
572  * possible scenarios:
573  *
574  *     1. The offset is "less than" the mapping entry; meaning the
575  *        offset is less than the source offset of the mapping entry. In
576  *        this case, there is no overlap between the offset and the
577  *        mapping entry and -1 will be returned.
578  *
579  *     2. The offset is "greater than" the mapping entry; meaning the
580  *        offset is greater than the mapping entry's source offset plus
581  *        the entry's size. In this case, there is no overlap between
582  *        the offset and the mapping entry and 1 will be returned.
583  *
584  *        NOTE: If the offset is actually equal to the entry's offset
585  *        plus size, this is considered to be "greater" than the entry,
586  *        and this case applies (i.e. 1 will be returned). Thus, the
587  *        entry's "range" can be considered to be inclusive at its
588  *        start, but exclusive at its end: e.g. [src, src + size).
589  *
590  *     3. The last case to consider is if the offset actually falls
591  *        within the mapping entry's range. If this is the case, the
592  *        offset is considered to be "equal to" the mapping entry and
593  *        0 will be returned.
594  *
595  *        NOTE: If the offset is equal to the entry's source offset,
596  *        this case applies and 0 will be returned. If the offset is
597  *        equal to the entry's source plus its size, this case does
598  *        *not* apply (see "NOTE" above for scenario 2), and 1 will be
599  *        returned.
600  */
601 static int
602 dva_mapping_overlap_compare(const void *v_key, const void *v_array_elem)
603 {
604 	const uint64_t *key = v_key;
605 	const vdev_indirect_mapping_entry_phys_t *array_elem =
606 	    v_array_elem;
607 	uint64_t src_offset = DVA_MAPPING_GET_SRC_OFFSET(array_elem);
608 
609 	if (*key < src_offset) {
610 		return (-1);
611 	} else if (*key < src_offset + DVA_GET_ASIZE(&array_elem->vimep_dst)) {
612 		return (0);
613 	} else {
614 		return (1);
615 	}
616 }
617 
618 /*
619  * Return array entry.
620  */
621 static vdev_indirect_mapping_entry_phys_t *
622 vdev_indirect_mapping_entry(vdev_indirect_mapping_t *vim, uint64_t index)
623 {
624 	uint64_t size;
625 	off_t offset = 0;
626 	int rc;
627 
628 	if (vim->vim_phys->vimp_num_entries == 0)
629 		return (NULL);
630 
631 	if (vim->vim_entries == NULL) {
632 		uint64_t bsize;
633 
634 		bsize = vim->vim_dn->dn_datablkszsec << SPA_MINBLOCKSHIFT;
635 		size = vim->vim_phys->vimp_num_entries *
636 		    sizeof (*vim->vim_entries);
637 		if (size > bsize) {
638 			size = bsize / sizeof (*vim->vim_entries);
639 			size *= sizeof (*vim->vim_entries);
640 		}
641 		vim->vim_entries = malloc(size);
642 		if (vim->vim_entries == NULL)
643 			return (NULL);
644 		vim->vim_num_entries = size / sizeof (*vim->vim_entries);
645 		offset = index * sizeof (*vim->vim_entries);
646 	}
647 
648 	/* We have data in vim_entries */
649 	if (offset == 0) {
650 		if (index >= vim->vim_entry_offset &&
651 		    index <= vim->vim_entry_offset + vim->vim_num_entries) {
652 			index -= vim->vim_entry_offset;
653 			return (&vim->vim_entries[index]);
654 		}
655 		offset = index * sizeof (*vim->vim_entries);
656 	}
657 
658 	vim->vim_entry_offset = index;
659 	size = vim->vim_num_entries * sizeof (*vim->vim_entries);
660 	rc = dnode_read(vim->vim_spa, vim->vim_dn, offset, vim->vim_entries,
661 	    size);
662 	if (rc != 0) {
663 		/* Read error, invalidate vim_entries. */
664 		free(vim->vim_entries);
665 		vim->vim_entries = NULL;
666 		return (NULL);
667 	}
668 	index -= vim->vim_entry_offset;
669 	return (&vim->vim_entries[index]);
670 }
671 
672 /*
673  * Returns the mapping entry for the given offset.
674  *
675  * It's possible that the given offset will not be in the mapping table
676  * (i.e. no mapping entries contain this offset), in which case, the
677  * return value value depends on the "next_if_missing" parameter.
678  *
679  * If the offset is not found in the table and "next_if_missing" is
680  * B_FALSE, then NULL will always be returned. The behavior is intended
681  * to allow consumers to get the entry corresponding to the offset
682  * parameter, iff the offset overlaps with an entry in the table.
683  *
684  * If the offset is not found in the table and "next_if_missing" is
685  * B_TRUE, then the entry nearest to the given offset will be returned,
686  * such that the entry's source offset is greater than the offset
687  * passed in (i.e. the "next" mapping entry in the table is returned, if
688  * the offset is missing from the table). If there are no entries whose
689  * source offset is greater than the passed in offset, NULL is returned.
690  */
691 static vdev_indirect_mapping_entry_phys_t *
692 vdev_indirect_mapping_entry_for_offset(vdev_indirect_mapping_t *vim,
693     uint64_t offset)
694 {
695 	ASSERT(vim->vim_phys->vimp_num_entries > 0);
696 
697 	vdev_indirect_mapping_entry_phys_t *entry;
698 
699 	uint64_t last = vim->vim_phys->vimp_num_entries - 1;
700 	uint64_t base = 0;
701 
702 	/*
703 	 * We don't define these inside of the while loop because we use
704 	 * their value in the case that offset isn't in the mapping.
705 	 */
706 	uint64_t mid;
707 	int result;
708 
709 	while (last >= base) {
710 		mid = base + ((last - base) >> 1);
711 
712 		entry = vdev_indirect_mapping_entry(vim, mid);
713 		if (entry == NULL)
714 			break;
715 		result = dva_mapping_overlap_compare(&offset, entry);
716 
717 		if (result == 0) {
718 			break;
719 		} else if (result < 0) {
720 			last = mid - 1;
721 		} else {
722 			base = mid + 1;
723 		}
724 	}
725 	return (entry);
726 }
727 
728 /*
729  * Given an indirect vdev and an extent on that vdev, it duplicates the
730  * physical entries of the indirect mapping that correspond to the extent
731  * to a new array and returns a pointer to it. In addition, copied_entries
732  * is populated with the number of mapping entries that were duplicated.
733  *
734  * Finally, since we are doing an allocation, it is up to the caller to
735  * free the array allocated in this function.
736  */
737 vdev_indirect_mapping_entry_phys_t *
738 vdev_indirect_mapping_duplicate_adjacent_entries(vdev_t *vd, uint64_t offset,
739     uint64_t asize, uint64_t *copied_entries)
740 {
741 	vdev_indirect_mapping_entry_phys_t *duplicate_mappings = NULL;
742 	vdev_indirect_mapping_t *vim = vd->v_mapping;
743 	uint64_t entries = 0;
744 
745 	vdev_indirect_mapping_entry_phys_t *first_mapping =
746 	    vdev_indirect_mapping_entry_for_offset(vim, offset);
747 	ASSERT3P(first_mapping, !=, NULL);
748 
749 	vdev_indirect_mapping_entry_phys_t *m = first_mapping;
750 	while (asize > 0) {
751 		uint64_t size = DVA_GET_ASIZE(&m->vimep_dst);
752 		uint64_t inner_offset = offset - DVA_MAPPING_GET_SRC_OFFSET(m);
753 		uint64_t inner_size = MIN(asize, size - inner_offset);
754 
755 		offset += inner_size;
756 		asize -= inner_size;
757 		entries++;
758 		m++;
759 	}
760 
761 	size_t copy_length = entries * sizeof (*first_mapping);
762 	duplicate_mappings = malloc(copy_length);
763 	if (duplicate_mappings != NULL)
764 		bcopy(first_mapping, duplicate_mappings, copy_length);
765 	else
766 		entries = 0;
767 
768 	*copied_entries = entries;
769 
770 	return (duplicate_mappings);
771 }
772 
773 static vdev_t *
774 vdev_lookup_top(spa_t *spa, uint64_t vdev)
775 {
776 	vdev_t *rvd;
777 
778 	STAILQ_FOREACH(rvd, &spa->spa_vdevs, v_childlink)
779 		if (rvd->v_id == vdev)
780 			break;
781 
782 	return (rvd);
783 }
784 
785 /*
786  * This is a callback for vdev_indirect_remap() which allocates an
787  * indirect_split_t for each split segment and adds it to iv_splits.
788  */
789 static void
790 vdev_indirect_gather_splits(uint64_t split_offset, vdev_t *vd, uint64_t offset,
791     uint64_t size, void *arg)
792 {
793 	int n = 1;
794 	zio_t *zio = arg;
795 	indirect_vsd_t *iv = zio->io_vsd;
796 
797 	if (vd->v_read == vdev_indirect_read)
798 		return;
799 
800 	if (vd->v_read == vdev_mirror_read)
801 		n = vd->v_nchildren;
802 
803 	indirect_split_t *is =
804 	    malloc(offsetof(indirect_split_t, is_child[n]));
805 	if (is == NULL) {
806 		zio->io_error = ENOMEM;
807 		return;
808 	}
809 	bzero(is, offsetof(indirect_split_t, is_child[n]));
810 
811 	is->is_children = n;
812 	is->is_size = size;
813 	is->is_split_offset = split_offset;
814 	is->is_target_offset = offset;
815 	is->is_vdev = vd;
816 
817 	/*
818 	 * Note that we only consider multiple copies of the data for
819 	 * *mirror* vdevs.  We don't for "replacing" or "spare" vdevs, even
820 	 * though they use the same ops as mirror, because there's only one
821 	 * "good" copy under the replacing/spare.
822 	 */
823 	if (vd->v_read == vdev_mirror_read) {
824 		int i = 0;
825 		vdev_t *kid;
826 
827 		STAILQ_FOREACH(kid, &vd->v_children, v_childlink) {
828 			is->is_child[i++].ic_vdev = kid;
829 		}
830 	} else {
831 		is->is_child[0].ic_vdev = vd;
832 	}
833 
834 	list_insert_tail(&iv->iv_splits, is);
835 }
836 
837 static void
838 vdev_indirect_remap(vdev_t *vd, uint64_t offset, uint64_t asize, void *arg)
839 {
840 	list_t stack;
841 	spa_t *spa = vd->spa;
842 	zio_t *zio = arg;
843 
844 	list_create(&stack, sizeof (remap_segment_t),
845 	    offsetof(remap_segment_t, rs_node));
846 
847 	for (remap_segment_t *rs = rs_alloc(vd, offset, asize, 0);
848 	    rs != NULL; rs = list_remove_head(&stack)) {
849 		vdev_t *v = rs->rs_vd;
850 		uint64_t num_entries = 0;
851 		/* vdev_indirect_mapping_t *vim = v->v_mapping; */
852 		vdev_indirect_mapping_entry_phys_t *mapping =
853 		    vdev_indirect_mapping_duplicate_adjacent_entries(v,
854 		    rs->rs_offset, rs->rs_asize, &num_entries);
855 
856 		for (uint64_t i = 0; i < num_entries; i++) {
857 			vdev_indirect_mapping_entry_phys_t *m = &mapping[i];
858 			uint64_t size = DVA_GET_ASIZE(&m->vimep_dst);
859 			uint64_t dst_offset = DVA_GET_OFFSET(&m->vimep_dst);
860 			uint64_t dst_vdev = DVA_GET_VDEV(&m->vimep_dst);
861 			uint64_t inner_offset = rs->rs_offset -
862 			    DVA_MAPPING_GET_SRC_OFFSET(m);
863 			uint64_t inner_size =
864 			    MIN(rs->rs_asize, size - inner_offset);
865 			vdev_t *dst_v = vdev_lookup_top(spa, dst_vdev);
866 
867 			if (dst_v->v_read == vdev_indirect_read) {
868 				list_insert_head(&stack,
869 				    rs_alloc(dst_v, dst_offset + inner_offset,
870 				    inner_size, rs->rs_split_offset));
871 			}
872 			vdev_indirect_gather_splits(rs->rs_split_offset, dst_v,
873 			    dst_offset + inner_offset,
874 			    inner_size, arg);
875 
876 			/*
877 			 * vdev_indirect_gather_splits can have memory
878 			 * allocation error, we can not recover from it.
879 			 */
880 			if (zio->io_error != 0)
881 				break;
882 
883 			rs->rs_offset += inner_size;
884 			rs->rs_asize -= inner_size;
885 			rs->rs_split_offset += inner_size;
886 		}
887 
888 		free(mapping);
889 		free(rs);
890 		if (zio->io_error != 0)
891 			break;
892 	}
893 
894 	list_destroy(&stack);
895 }
896 
897 static void
898 vdev_indirect_map_free(zio_t *zio)
899 {
900 	indirect_vsd_t *iv = zio->io_vsd;
901 	indirect_split_t *is;
902 
903 	while ((is = list_head(&iv->iv_splits)) != NULL) {
904 		for (int c = 0; c < is->is_children; c++) {
905 			indirect_child_t *ic = &is->is_child[c];
906 			free(ic->ic_data);
907 		}
908 		list_remove(&iv->iv_splits, is);
909 		free(is);
910 	}
911 	free(iv);
912 }
913 
914 static int
915 vdev_indirect_read(vdev_t *vdev, const blkptr_t *bp, void *buf,
916     off_t offset, size_t bytes)
917 {
918 	zio_t zio = { 0 };
919 	spa_t *spa = vdev->spa;
920 	indirect_vsd_t *iv = malloc(sizeof (*iv));
921 	indirect_split_t *first;
922 	int rc = EIO;
923 
924 	if (iv == NULL)
925 		return (ENOMEM);
926 	bzero(iv, sizeof (*iv));
927 
928 	list_create(&iv->iv_splits,
929 	    sizeof (indirect_split_t), offsetof(indirect_split_t, is_node));
930 
931 	zio.io_spa = spa;
932 	zio.io_bp = (blkptr_t *)bp;
933 	zio.io_data = buf;
934 	zio.io_size = bytes;
935 	zio.io_offset = offset;
936 	zio.io_vd = vdev;
937 	zio.io_vsd = iv;
938 
939 	if (vdev->v_mapping == NULL) {
940 		vdev_indirect_config_t *vic;
941 
942 		vic = &vdev->vdev_indirect_config;
943 		vdev->v_mapping = vdev_indirect_mapping_open(spa,
944 		    &spa->spa_mos, vic->vic_mapping_object);
945 	}
946 
947 	vdev_indirect_remap(vdev, offset, bytes, &zio);
948 	if (zio.io_error != 0)
949 		return (zio.io_error);
950 
951 	first = list_head(&iv->iv_splits);
952 	if (first->is_size == zio.io_size) {
953 		/*
954 		 * This is not a split block; we are pointing to the entire
955 		 * data, which will checksum the same as the original data.
956 		 * Pass the BP down so that the child i/o can verify the
957 		 * checksum, and try a different location if available
958 		 * (e.g. on a mirror).
959 		 *
960 		 * While this special case could be handled the same as the
961 		 * general (split block) case, doing it this way ensures
962 		 * that the vast majority of blocks on indirect vdevs
963 		 * (which are not split) are handled identically to blocks
964 		 * on non-indirect vdevs.  This allows us to be less strict
965 		 * about performance in the general (but rare) case.
966 		 */
967 		rc = first->is_vdev->v_read(first->is_vdev, zio.io_bp,
968 		    zio.io_data, first->is_target_offset, bytes);
969 	} else {
970 		iv->iv_split_block = B_TRUE;
971 		/*
972 		 * Read one copy of each split segment, from the
973 		 * top-level vdev.  Since we don't know the
974 		 * checksum of each split individually, the child
975 		 * zio can't ensure that we get the right data.
976 		 * E.g. if it's a mirror, it will just read from a
977 		 * random (healthy) leaf vdev.  We have to verify
978 		 * the checksum in vdev_indirect_io_done().
979 		 */
980 		for (indirect_split_t *is = list_head(&iv->iv_splits);
981 		    is != NULL; is = list_next(&iv->iv_splits, is)) {
982 			char *ptr = zio.io_data;
983 
984 			rc = is->is_vdev->v_read(is->is_vdev, zio.io_bp,
985 			    ptr + is->is_split_offset, is->is_target_offset,
986 			    is->is_size);
987 		}
988 		if (zio_checksum_verify(spa, zio.io_bp, zio.io_data))
989 			rc = ECKSUM;
990 		else
991 			rc = 0;
992 	}
993 
994 	vdev_indirect_map_free(&zio);
995 	if (rc == 0)
996 		rc = zio.io_error;
997 
998 	return (rc);
999 }
1000 
1001 static int
1002 vdev_disk_read(vdev_t *vdev, const blkptr_t *bp, void *buf,
1003     off_t offset, size_t bytes)
1004 {
1005 
1006 	return (vdev_read_phys(vdev, bp, buf,
1007 		offset + VDEV_LABEL_START_SIZE, bytes));
1008 }
1009 
1010 
1011 static int
1012 vdev_mirror_read(vdev_t *vdev, const blkptr_t *bp, void *buf,
1013     off_t offset, size_t bytes)
1014 {
1015 	vdev_t *kid;
1016 	int rc;
1017 
1018 	rc = EIO;
1019 	STAILQ_FOREACH(kid, &vdev->v_children, v_childlink) {
1020 		if (kid->v_state != VDEV_STATE_HEALTHY)
1021 			continue;
1022 		rc = kid->v_read(kid, bp, buf, offset, bytes);
1023 		if (!rc)
1024 			return (0);
1025 	}
1026 
1027 	return (rc);
1028 }
1029 
1030 static int
1031 vdev_replacing_read(vdev_t *vdev, const blkptr_t *bp, void *buf,
1032     off_t offset, size_t bytes)
1033 {
1034 	vdev_t *kid;
1035 
1036 	/*
1037 	 * Here we should have two kids:
1038 	 * First one which is the one we are replacing and we can trust
1039 	 * only this one to have valid data, but it might not be present.
1040 	 * Second one is that one we are replacing with. It is most likely
1041 	 * healthy, but we can't trust it has needed data, so we won't use it.
1042 	 */
1043 	kid = STAILQ_FIRST(&vdev->v_children);
1044 	if (kid == NULL)
1045 		return (EIO);
1046 	if (kid->v_state != VDEV_STATE_HEALTHY)
1047 		return (EIO);
1048 	return (kid->v_read(kid, bp, buf, offset, bytes));
1049 }
1050 
1051 static vdev_t *
1052 vdev_find(uint64_t guid)
1053 {
1054 	vdev_t *vdev;
1055 
1056 	STAILQ_FOREACH(vdev, &zfs_vdevs, v_alllink)
1057 		if (vdev->v_guid == guid)
1058 			return (vdev);
1059 
1060 	return (0);
1061 }
1062 
1063 static vdev_t *
1064 vdev_create(uint64_t guid, vdev_read_t *_read)
1065 {
1066 	vdev_t *vdev;
1067 	vdev_indirect_config_t *vic;
1068 
1069 	vdev = malloc(sizeof(vdev_t));
1070 	memset(vdev, 0, sizeof(vdev_t));
1071 	STAILQ_INIT(&vdev->v_children);
1072 	vdev->v_guid = guid;
1073 	vdev->v_state = VDEV_STATE_OFFLINE;
1074 	vdev->v_read = _read;
1075 
1076 	vic = &vdev->vdev_indirect_config;
1077 	vic->vic_prev_indirect_vdev = UINT64_MAX;
1078 	STAILQ_INSERT_TAIL(&zfs_vdevs, vdev, v_alllink);
1079 
1080 	return (vdev);
1081 }
1082 
1083 static int
1084 vdev_init_from_nvlist(const unsigned char *nvlist, vdev_t *pvdev,
1085     vdev_t **vdevp, int is_newer)
1086 {
1087 	int rc;
1088 	uint64_t guid, id, ashift, nparity;
1089 	const char *type;
1090 	const char *path;
1091 	vdev_t *vdev, *kid;
1092 	const unsigned char *kids;
1093 	int nkids, i, is_new;
1094 	uint64_t is_offline, is_faulted, is_degraded, is_removed, isnt_present;
1095 
1096 	if (nvlist_find(nvlist, ZPOOL_CONFIG_GUID, DATA_TYPE_UINT64,
1097 	    NULL, &guid)
1098 	    || nvlist_find(nvlist, ZPOOL_CONFIG_ID, DATA_TYPE_UINT64, NULL, &id)
1099 	    || nvlist_find(nvlist, ZPOOL_CONFIG_TYPE, DATA_TYPE_STRING,
1100 	    NULL, &type)) {
1101 		printf("ZFS: can't find vdev details\n");
1102 		return (ENOENT);
1103 	}
1104 
1105 	if (strcmp(type, VDEV_TYPE_MIRROR)
1106 	    && strcmp(type, VDEV_TYPE_DISK)
1107 #ifdef ZFS_TEST
1108 	    && strcmp(type, VDEV_TYPE_FILE)
1109 #endif
1110 	    && strcmp(type, VDEV_TYPE_RAIDZ)
1111 	    && strcmp(type, VDEV_TYPE_INDIRECT)
1112 	    && strcmp(type, VDEV_TYPE_REPLACING)) {
1113 		printf("ZFS: can only boot from disk, mirror, raidz1, raidz2 and raidz3 vdevs\n");
1114 		return (EIO);
1115 	}
1116 
1117 	is_offline = is_removed = is_faulted = is_degraded = isnt_present = 0;
1118 
1119 	nvlist_find(nvlist, ZPOOL_CONFIG_OFFLINE, DATA_TYPE_UINT64, NULL,
1120 			&is_offline);
1121 	nvlist_find(nvlist, ZPOOL_CONFIG_REMOVED, DATA_TYPE_UINT64, NULL,
1122 			&is_removed);
1123 	nvlist_find(nvlist, ZPOOL_CONFIG_FAULTED, DATA_TYPE_UINT64, NULL,
1124 			&is_faulted);
1125 	nvlist_find(nvlist, ZPOOL_CONFIG_DEGRADED, DATA_TYPE_UINT64, NULL,
1126 			&is_degraded);
1127 	nvlist_find(nvlist, ZPOOL_CONFIG_NOT_PRESENT, DATA_TYPE_UINT64, NULL,
1128 			&isnt_present);
1129 
1130 	vdev = vdev_find(guid);
1131 	if (!vdev) {
1132 		is_new = 1;
1133 
1134 		if (!strcmp(type, VDEV_TYPE_MIRROR))
1135 			vdev = vdev_create(guid, vdev_mirror_read);
1136 		else if (!strcmp(type, VDEV_TYPE_RAIDZ))
1137 			vdev = vdev_create(guid, vdev_raidz_read);
1138 		else if (!strcmp(type, VDEV_TYPE_REPLACING))
1139 			vdev = vdev_create(guid, vdev_replacing_read);
1140 		else if (!strcmp(type, VDEV_TYPE_INDIRECT)) {
1141 			vdev_indirect_config_t *vic;
1142 
1143 			vdev = vdev_create(guid, vdev_indirect_read);
1144 			vdev->v_state = VDEV_STATE_HEALTHY;
1145 			vic = &vdev->vdev_indirect_config;
1146 
1147 			nvlist_find(nvlist,
1148 			    ZPOOL_CONFIG_INDIRECT_OBJECT, DATA_TYPE_UINT64,
1149 			    NULL, &vic->vic_mapping_object);
1150 			nvlist_find(nvlist,
1151 			    ZPOOL_CONFIG_INDIRECT_BIRTHS, DATA_TYPE_UINT64,
1152 			    NULL, &vic->vic_births_object);
1153 			nvlist_find(nvlist,
1154 			    ZPOOL_CONFIG_PREV_INDIRECT_VDEV, DATA_TYPE_UINT64,
1155 			    NULL, &vic->vic_prev_indirect_vdev);
1156 		} else
1157 			vdev = vdev_create(guid, vdev_disk_read);
1158 
1159 		vdev->v_id = id;
1160 		vdev->v_top = pvdev != NULL ? pvdev : vdev;
1161 		if (nvlist_find(nvlist, ZPOOL_CONFIG_ASHIFT,
1162 			DATA_TYPE_UINT64, NULL, &ashift) == 0) {
1163 			vdev->v_ashift = ashift;
1164 		} else {
1165 			vdev->v_ashift = 0;
1166 		}
1167 		if (nvlist_find(nvlist, ZPOOL_CONFIG_NPARITY,
1168 			DATA_TYPE_UINT64, NULL, &nparity) == 0) {
1169 			vdev->v_nparity = nparity;
1170 		} else {
1171 			vdev->v_nparity = 0;
1172 		}
1173 		if (nvlist_find(nvlist, ZPOOL_CONFIG_PATH,
1174 				DATA_TYPE_STRING, NULL, &path) == 0) {
1175 			if (strncmp(path, "/dev/", 5) == 0)
1176 				path += 5;
1177 			vdev->v_name = strdup(path);
1178 		} else {
1179 			char *name;
1180 
1181 			if (!strcmp(type, "raidz")) {
1182 				if (vdev->v_nparity < 1 ||
1183 				    vdev->v_nparity > 3) {
1184 					printf("ZFS: can only boot from disk, "
1185 					    "mirror, raidz1, raidz2 and raidz3 "
1186 					    "vdevs\n");
1187 					return (EIO);
1188 				}
1189 				asprintf(&name, "%s%d-%jd", type,
1190 				    vdev->v_nparity, id);
1191 			} else {
1192 				asprintf(&name, "%s-%jd", type, id);
1193 			}
1194 			if (name == NULL)
1195 				return (ENOMEM);
1196 			vdev->v_name = name;
1197 		}
1198 	} else {
1199 		is_new = 0;
1200 	}
1201 
1202 	if (is_new || is_newer) {
1203 		/*
1204 		 * This is either new vdev or we've already seen this vdev,
1205 		 * but from an older vdev label, so let's refresh its state
1206 		 * from the newer label.
1207 		 */
1208 		if (is_offline)
1209 			vdev->v_state = VDEV_STATE_OFFLINE;
1210 		else if (is_removed)
1211 			vdev->v_state = VDEV_STATE_REMOVED;
1212 		else if (is_faulted)
1213 			vdev->v_state = VDEV_STATE_FAULTED;
1214 		else if (is_degraded)
1215 			vdev->v_state = VDEV_STATE_DEGRADED;
1216 		else if (isnt_present)
1217 			vdev->v_state = VDEV_STATE_CANT_OPEN;
1218 	}
1219 
1220 	rc = nvlist_find(nvlist, ZPOOL_CONFIG_CHILDREN, DATA_TYPE_NVLIST_ARRAY,
1221 	    &nkids, &kids);
1222 	/*
1223 	 * Its ok if we don't have any kids.
1224 	 */
1225 	if (rc == 0) {
1226 		vdev->v_nchildren = nkids;
1227 		for (i = 0; i < nkids; i++) {
1228 			rc = vdev_init_from_nvlist(kids, vdev, &kid, is_newer);
1229 			if (rc)
1230 				return (rc);
1231 			if (is_new)
1232 				STAILQ_INSERT_TAIL(&vdev->v_children, kid,
1233 						   v_childlink);
1234 			kids = nvlist_next(kids);
1235 		}
1236 	} else {
1237 		vdev->v_nchildren = 0;
1238 	}
1239 
1240 	if (vdevp)
1241 		*vdevp = vdev;
1242 	return (0);
1243 }
1244 
1245 static void
1246 vdev_set_state(vdev_t *vdev)
1247 {
1248 	vdev_t *kid;
1249 	int good_kids;
1250 	int bad_kids;
1251 
1252 	/*
1253 	 * A mirror or raidz is healthy if all its kids are healthy. A
1254 	 * mirror is degraded if any of its kids is healthy; a raidz
1255 	 * is degraded if at most nparity kids are offline.
1256 	 */
1257 	if (STAILQ_FIRST(&vdev->v_children)) {
1258 		good_kids = 0;
1259 		bad_kids = 0;
1260 		STAILQ_FOREACH(kid, &vdev->v_children, v_childlink) {
1261 			if (kid->v_state == VDEV_STATE_HEALTHY)
1262 				good_kids++;
1263 			else
1264 				bad_kids++;
1265 		}
1266 		if (bad_kids == 0) {
1267 			vdev->v_state = VDEV_STATE_HEALTHY;
1268 		} else {
1269 			if (vdev->v_read == vdev_mirror_read) {
1270 				if (good_kids) {
1271 					vdev->v_state = VDEV_STATE_DEGRADED;
1272 				} else {
1273 					vdev->v_state = VDEV_STATE_OFFLINE;
1274 				}
1275 			} else if (vdev->v_read == vdev_raidz_read) {
1276 				if (bad_kids > vdev->v_nparity) {
1277 					vdev->v_state = VDEV_STATE_OFFLINE;
1278 				} else {
1279 					vdev->v_state = VDEV_STATE_DEGRADED;
1280 				}
1281 			}
1282 		}
1283 	}
1284 }
1285 
1286 static spa_t *
1287 spa_find_by_guid(uint64_t guid)
1288 {
1289 	spa_t *spa;
1290 
1291 	STAILQ_FOREACH(spa, &zfs_pools, spa_link)
1292 		if (spa->spa_guid == guid)
1293 			return (spa);
1294 
1295 	return (0);
1296 }
1297 
1298 static spa_t *
1299 spa_find_by_name(const char *name)
1300 {
1301 	spa_t *spa;
1302 
1303 	STAILQ_FOREACH(spa, &zfs_pools, spa_link)
1304 		if (!strcmp(spa->spa_name, name))
1305 			return (spa);
1306 
1307 	return (0);
1308 }
1309 
1310 #ifdef BOOT2
1311 static spa_t *
1312 spa_get_primary(void)
1313 {
1314 
1315 	return (STAILQ_FIRST(&zfs_pools));
1316 }
1317 
1318 static vdev_t *
1319 spa_get_primary_vdev(const spa_t *spa)
1320 {
1321 	vdev_t *vdev;
1322 	vdev_t *kid;
1323 
1324 	if (spa == NULL)
1325 		spa = spa_get_primary();
1326 	if (spa == NULL)
1327 		return (NULL);
1328 	vdev = STAILQ_FIRST(&spa->spa_vdevs);
1329 	if (vdev == NULL)
1330 		return (NULL);
1331 	for (kid = STAILQ_FIRST(&vdev->v_children); kid != NULL;
1332 	     kid = STAILQ_FIRST(&vdev->v_children))
1333 		vdev = kid;
1334 	return (vdev);
1335 }
1336 #endif
1337 
1338 static spa_t *
1339 spa_create(uint64_t guid, const char *name)
1340 {
1341 	spa_t *spa;
1342 
1343 	if ((spa = calloc(1, sizeof(spa_t))) == NULL)
1344 		return (NULL);
1345 	if ((spa->spa_name = strdup(name)) == NULL) {
1346 		free(spa);
1347 		return (NULL);
1348 	}
1349 	STAILQ_INIT(&spa->spa_vdevs);
1350 	spa->spa_guid = guid;
1351 	STAILQ_INSERT_TAIL(&zfs_pools, spa, spa_link);
1352 
1353 	return (spa);
1354 }
1355 
1356 static const char *
1357 state_name(vdev_state_t state)
1358 {
1359 	static const char* names[] = {
1360 		"UNKNOWN",
1361 		"CLOSED",
1362 		"OFFLINE",
1363 		"REMOVED",
1364 		"CANT_OPEN",
1365 		"FAULTED",
1366 		"DEGRADED",
1367 		"ONLINE"
1368 	};
1369 	return names[state];
1370 }
1371 
1372 #ifdef BOOT2
1373 
1374 #define pager_printf printf
1375 
1376 #else
1377 
1378 static int
1379 pager_printf(const char *fmt, ...)
1380 {
1381 	char line[80];
1382 	va_list args;
1383 
1384 	va_start(args, fmt);
1385 	vsprintf(line, fmt, args);
1386 	va_end(args);
1387 
1388 	return (pager_output(line));
1389 }
1390 
1391 #endif
1392 
1393 #define STATUS_FORMAT	"        %s %s\n"
1394 
1395 static int
1396 print_state(int indent, const char *name, vdev_state_t state)
1397 {
1398 	char buf[512];
1399 	int i;
1400 
1401 	buf[0] = 0;
1402 	for (i = 0; i < indent; i++)
1403 		strcat(buf, "  ");
1404 	strcat(buf, name);
1405 
1406 	return (pager_printf(STATUS_FORMAT, buf, state_name(state)));
1407 }
1408 
1409 static int
1410 vdev_status(vdev_t *vdev, int indent)
1411 {
1412 	vdev_t *kid;
1413 	int ret;
1414 	ret = print_state(indent, vdev->v_name, vdev->v_state);
1415 	if (ret != 0)
1416 		return (ret);
1417 
1418 	STAILQ_FOREACH(kid, &vdev->v_children, v_childlink) {
1419 		ret = vdev_status(kid, indent + 1);
1420 		if (ret != 0)
1421 			return (ret);
1422 	}
1423 	return (ret);
1424 }
1425 
1426 static int
1427 spa_status(spa_t *spa)
1428 {
1429 	static char bootfs[ZFS_MAXNAMELEN];
1430 	uint64_t rootid;
1431 	vdev_t *vdev;
1432 	int good_kids, bad_kids, degraded_kids, ret;
1433 	vdev_state_t state;
1434 
1435 	ret = pager_printf("  pool: %s\n", spa->spa_name);
1436 	if (ret != 0)
1437 		return (ret);
1438 
1439 	if (zfs_get_root(spa, &rootid) == 0 &&
1440 	    zfs_rlookup(spa, rootid, bootfs) == 0) {
1441 		if (bootfs[0] == '\0')
1442 			ret = pager_printf("bootfs: %s\n", spa->spa_name);
1443 		else
1444 			ret = pager_printf("bootfs: %s/%s\n", spa->spa_name,
1445 			    bootfs);
1446 		if (ret != 0)
1447 			return (ret);
1448 	}
1449 	ret = pager_printf("config:\n\n");
1450 	if (ret != 0)
1451 		return (ret);
1452 	ret = pager_printf(STATUS_FORMAT, "NAME", "STATE");
1453 	if (ret != 0)
1454 		return (ret);
1455 
1456 	good_kids = 0;
1457 	degraded_kids = 0;
1458 	bad_kids = 0;
1459 	STAILQ_FOREACH(vdev, &spa->spa_vdevs, v_childlink) {
1460 		if (vdev->v_state == VDEV_STATE_HEALTHY)
1461 			good_kids++;
1462 		else if (vdev->v_state == VDEV_STATE_DEGRADED)
1463 			degraded_kids++;
1464 		else
1465 			bad_kids++;
1466 	}
1467 
1468 	state = VDEV_STATE_CLOSED;
1469 	if (good_kids > 0 && (degraded_kids + bad_kids) == 0)
1470 		state = VDEV_STATE_HEALTHY;
1471 	else if ((good_kids + degraded_kids) > 0)
1472 		state = VDEV_STATE_DEGRADED;
1473 
1474 	ret = print_state(0, spa->spa_name, state);
1475 	if (ret != 0)
1476 		return (ret);
1477 	STAILQ_FOREACH(vdev, &spa->spa_vdevs, v_childlink) {
1478 		ret = vdev_status(vdev, 1);
1479 		if (ret != 0)
1480 			return (ret);
1481 	}
1482 	return (ret);
1483 }
1484 
1485 static int
1486 spa_all_status(void)
1487 {
1488 	spa_t *spa;
1489 	int first = 1, ret = 0;
1490 
1491 	STAILQ_FOREACH(spa, &zfs_pools, spa_link) {
1492 		if (!first) {
1493 			ret = pager_printf("\n");
1494 			if (ret != 0)
1495 				return (ret);
1496 		}
1497 		first = 0;
1498 		ret = spa_status(spa);
1499 		if (ret != 0)
1500 			return (ret);
1501 	}
1502 	return (ret);
1503 }
1504 
1505 static uint64_t
1506 vdev_label_offset(uint64_t psize, int l, uint64_t offset)
1507 {
1508 	uint64_t label_offset;
1509 
1510 	if (l < VDEV_LABELS / 2)
1511 		label_offset = 0;
1512 	else
1513 		label_offset = psize - VDEV_LABELS * sizeof (vdev_label_t);
1514 
1515 	return (offset + l * sizeof (vdev_label_t) + label_offset);
1516 }
1517 
1518 static int
1519 vdev_probe(vdev_phys_read_t *_read, void *read_priv, spa_t **spap)
1520 {
1521 	vdev_t vtmp;
1522 	vdev_phys_t *vdev_label = (vdev_phys_t *) zap_scratch;
1523 	vdev_phys_t *tmp_label;
1524 	spa_t *spa;
1525 	vdev_t *vdev, *top_vdev, *pool_vdev;
1526 	off_t off;
1527 	blkptr_t bp;
1528 	const unsigned char *nvlist = NULL;
1529 	uint64_t val;
1530 	uint64_t guid;
1531 	uint64_t best_txg = 0;
1532 	uint64_t pool_txg, pool_guid;
1533 	uint64_t psize;
1534 	const char *pool_name;
1535 	const unsigned char *vdevs;
1536 	const unsigned char *features;
1537 	int i, l, rc, is_newer;
1538 	char *upbuf;
1539 	const struct uberblock *up;
1540 
1541 	/*
1542 	 * Load the vdev label and figure out which
1543 	 * uberblock is most current.
1544 	 */
1545 	memset(&vtmp, 0, sizeof(vtmp));
1546 	vtmp.v_phys_read = _read;
1547 	vtmp.v_read_priv = read_priv;
1548 	psize = P2ALIGN(ldi_get_size(read_priv),
1549 	    (uint64_t)sizeof (vdev_label_t));
1550 
1551 	/* Test for minimum pool size. */
1552 	if (psize < SPA_MINDEVSIZE)
1553 		return (EIO);
1554 
1555 	tmp_label = zfs_alloc(sizeof(vdev_phys_t));
1556 
1557 	for (l = 0; l < VDEV_LABELS; l++) {
1558 		off = vdev_label_offset(psize, l,
1559 		    offsetof(vdev_label_t, vl_vdev_phys));
1560 
1561 		BP_ZERO(&bp);
1562 		BP_SET_LSIZE(&bp, sizeof(vdev_phys_t));
1563 		BP_SET_PSIZE(&bp, sizeof(vdev_phys_t));
1564 		BP_SET_CHECKSUM(&bp, ZIO_CHECKSUM_LABEL);
1565 		BP_SET_COMPRESS(&bp, ZIO_COMPRESS_OFF);
1566 		DVA_SET_OFFSET(BP_IDENTITY(&bp), off);
1567 		ZIO_SET_CHECKSUM(&bp.blk_cksum, off, 0, 0, 0);
1568 
1569 		if (vdev_read_phys(&vtmp, &bp, tmp_label, off, 0))
1570 			continue;
1571 
1572 		if (tmp_label->vp_nvlist[0] != NV_ENCODE_XDR)
1573 			continue;
1574 
1575 		nvlist = (const unsigned char *) tmp_label->vp_nvlist + 4;
1576 		if (nvlist_find(nvlist, ZPOOL_CONFIG_POOL_TXG,
1577 		    DATA_TYPE_UINT64, NULL, &pool_txg) != 0)
1578 			continue;
1579 
1580 		if (best_txg <= pool_txg) {
1581 			best_txg = pool_txg;
1582 			memcpy(vdev_label, tmp_label, sizeof (vdev_phys_t));
1583 		}
1584 	}
1585 
1586 	zfs_free(tmp_label, sizeof (vdev_phys_t));
1587 
1588 	if (best_txg == 0)
1589 		return (EIO);
1590 
1591 	if (vdev_label->vp_nvlist[0] != NV_ENCODE_XDR)
1592 		return (EIO);
1593 
1594 	nvlist = (const unsigned char *) vdev_label->vp_nvlist + 4;
1595 
1596 	if (nvlist_find(nvlist, ZPOOL_CONFIG_VERSION, DATA_TYPE_UINT64,
1597 	    NULL, &val) != 0) {
1598 		return (EIO);
1599 	}
1600 
1601 	if (!SPA_VERSION_IS_SUPPORTED(val)) {
1602 		printf("ZFS: unsupported ZFS version %u (should be %u)\n",
1603 		    (unsigned) val, (unsigned) SPA_VERSION);
1604 		return (EIO);
1605 	}
1606 
1607 	/* Check ZFS features for read */
1608 	if (nvlist_find(nvlist, ZPOOL_CONFIG_FEATURES_FOR_READ,
1609 	    DATA_TYPE_NVLIST, NULL, &features) == 0 &&
1610 	    nvlist_check_features_for_read(features) != 0) {
1611 		return (EIO);
1612 	}
1613 
1614 	if (nvlist_find(nvlist, ZPOOL_CONFIG_POOL_STATE, DATA_TYPE_UINT64,
1615 	    NULL, &val) != 0) {
1616 		return (EIO);
1617 	}
1618 
1619 	if (val == POOL_STATE_DESTROYED) {
1620 		/* We don't boot only from destroyed pools. */
1621 		return (EIO);
1622 	}
1623 
1624 	if (nvlist_find(nvlist, ZPOOL_CONFIG_POOL_TXG, DATA_TYPE_UINT64,
1625 	    NULL, &pool_txg) != 0 ||
1626 	    nvlist_find(nvlist, ZPOOL_CONFIG_POOL_GUID, DATA_TYPE_UINT64,
1627 	    NULL, &pool_guid) != 0 ||
1628 	    nvlist_find(nvlist, ZPOOL_CONFIG_POOL_NAME, DATA_TYPE_STRING,
1629 	    NULL, &pool_name) != 0) {
1630 		/*
1631 		 * Cache and spare devices end up here - just ignore
1632 		 * them.
1633 		 */
1634 		/*printf("ZFS: can't find pool details\n");*/
1635 		return (EIO);
1636 	}
1637 
1638 	if (nvlist_find(nvlist, ZPOOL_CONFIG_IS_LOG, DATA_TYPE_UINT64,
1639 	    NULL, &val) == 0 && val != 0) {
1640 		return (EIO);
1641 	}
1642 
1643 	/*
1644 	 * Create the pool if this is the first time we've seen it.
1645 	 */
1646 	spa = spa_find_by_guid(pool_guid);
1647 	if (spa == NULL) {
1648 		spa = spa_create(pool_guid, pool_name);
1649 		if (spa == NULL)
1650 			return (ENOMEM);
1651 	}
1652 	if (pool_txg > spa->spa_txg) {
1653 		spa->spa_txg = pool_txg;
1654 		is_newer = 1;
1655 	} else {
1656 		is_newer = 0;
1657 	}
1658 
1659 	/*
1660 	 * Get the vdev tree and create our in-core copy of it.
1661 	 * If we already have a vdev with this guid, this must
1662 	 * be some kind of alias (overlapping slices, dangerously dedicated
1663 	 * disks etc).
1664 	 */
1665 	if (nvlist_find(nvlist, ZPOOL_CONFIG_GUID, DATA_TYPE_UINT64,
1666 	    NULL, &guid) != 0) {
1667 		return (EIO);
1668 	}
1669 	vdev = vdev_find(guid);
1670 	if (vdev && vdev->v_phys_read)	/* Has this vdev already been inited? */
1671 		return (EIO);
1672 
1673 	if (nvlist_find(nvlist, ZPOOL_CONFIG_VDEV_TREE, DATA_TYPE_NVLIST,
1674 	    NULL, &vdevs)) {
1675 		return (EIO);
1676 	}
1677 
1678 	rc = vdev_init_from_nvlist(vdevs, NULL, &top_vdev, is_newer);
1679 	if (rc != 0)
1680 		return (rc);
1681 
1682 	/*
1683 	 * Add the toplevel vdev to the pool if its not already there.
1684 	 */
1685 	STAILQ_FOREACH(pool_vdev, &spa->spa_vdevs, v_childlink)
1686 		if (top_vdev == pool_vdev)
1687 			break;
1688 	if (!pool_vdev && top_vdev) {
1689 		top_vdev->spa = spa;
1690 		STAILQ_INSERT_TAIL(&spa->spa_vdevs, top_vdev, v_childlink);
1691 	}
1692 
1693 	/*
1694 	 * We should already have created an incomplete vdev for this
1695 	 * vdev. Find it and initialise it with our read proc.
1696 	 */
1697 	vdev = vdev_find(guid);
1698 	if (vdev) {
1699 		vdev->v_phys_read = _read;
1700 		vdev->v_read_priv = read_priv;
1701 		vdev->v_state = VDEV_STATE_HEALTHY;
1702 	} else {
1703 		printf("ZFS: inconsistent nvlist contents\n");
1704 		return (EIO);
1705 	}
1706 
1707 	/*
1708 	 * Re-evaluate top-level vdev state.
1709 	 */
1710 	vdev_set_state(top_vdev);
1711 
1712 	/*
1713 	 * Ok, we are happy with the pool so far. Lets find
1714 	 * the best uberblock and then we can actually access
1715 	 * the contents of the pool.
1716 	 */
1717 	upbuf = zfs_alloc(VDEV_UBERBLOCK_SIZE(vdev));
1718 	up = (const struct uberblock *)upbuf;
1719 	for (l = 0; l < VDEV_LABELS; l++) {
1720 		for (i = 0; i < VDEV_UBERBLOCK_COUNT(vdev); i++) {
1721 			off = vdev_label_offset(psize, l,
1722 			    VDEV_UBERBLOCK_OFFSET(vdev, i));
1723 			BP_ZERO(&bp);
1724 			DVA_SET_OFFSET(&bp.blk_dva[0], off);
1725 			BP_SET_LSIZE(&bp, VDEV_UBERBLOCK_SIZE(vdev));
1726 			BP_SET_PSIZE(&bp, VDEV_UBERBLOCK_SIZE(vdev));
1727 			BP_SET_CHECKSUM(&bp, ZIO_CHECKSUM_LABEL);
1728 			BP_SET_COMPRESS(&bp, ZIO_COMPRESS_OFF);
1729 			ZIO_SET_CHECKSUM(&bp.blk_cksum, off, 0, 0, 0);
1730 
1731 			if (vdev_read_phys(vdev, &bp, upbuf, off, 0))
1732 				continue;
1733 
1734 			if (up->ub_magic != UBERBLOCK_MAGIC)
1735 				continue;
1736 			if (up->ub_txg < spa->spa_txg)
1737 				continue;
1738 			if (up->ub_txg > spa->spa_uberblock.ub_txg ||
1739 			    (up->ub_txg == spa->spa_uberblock.ub_txg &&
1740 			    up->ub_timestamp >
1741 			    spa->spa_uberblock.ub_timestamp)) {
1742 				spa->spa_uberblock = *up;
1743 			}
1744 		}
1745 	}
1746 	zfs_free(upbuf, VDEV_UBERBLOCK_SIZE(vdev));
1747 
1748 	vdev->spa = spa;
1749 	if (spap != NULL)
1750 		*spap = spa;
1751 	return (0);
1752 }
1753 
1754 static int
1755 ilog2(int n)
1756 {
1757 	int v;
1758 
1759 	for (v = 0; v < 32; v++)
1760 		if (n == (1 << v))
1761 			return v;
1762 	return -1;
1763 }
1764 
1765 static int
1766 zio_read_gang(const spa_t *spa, const blkptr_t *bp, void *buf)
1767 {
1768 	blkptr_t gbh_bp;
1769 	zio_gbh_phys_t zio_gb;
1770 	char *pbuf;
1771 	int i;
1772 
1773 	/* Artificial BP for gang block header. */
1774 	gbh_bp = *bp;
1775 	BP_SET_PSIZE(&gbh_bp, SPA_GANGBLOCKSIZE);
1776 	BP_SET_LSIZE(&gbh_bp, SPA_GANGBLOCKSIZE);
1777 	BP_SET_CHECKSUM(&gbh_bp, ZIO_CHECKSUM_GANG_HEADER);
1778 	BP_SET_COMPRESS(&gbh_bp, ZIO_COMPRESS_OFF);
1779 	for (i = 0; i < SPA_DVAS_PER_BP; i++)
1780 		DVA_SET_GANG(&gbh_bp.blk_dva[i], 0);
1781 
1782 	/* Read gang header block using the artificial BP. */
1783 	if (zio_read(spa, &gbh_bp, &zio_gb))
1784 		return (EIO);
1785 
1786 	pbuf = buf;
1787 	for (i = 0; i < SPA_GBH_NBLKPTRS; i++) {
1788 		blkptr_t *gbp = &zio_gb.zg_blkptr[i];
1789 
1790 		if (BP_IS_HOLE(gbp))
1791 			continue;
1792 		if (zio_read(spa, gbp, pbuf))
1793 			return (EIO);
1794 		pbuf += BP_GET_PSIZE(gbp);
1795 	}
1796 
1797 	if (zio_checksum_verify(spa, bp, buf))
1798 		return (EIO);
1799 	return (0);
1800 }
1801 
1802 static int
1803 zio_read(const spa_t *spa, const blkptr_t *bp, void *buf)
1804 {
1805 	int cpfunc = BP_GET_COMPRESS(bp);
1806 	uint64_t align, size;
1807 	void *pbuf;
1808 	int i, error;
1809 
1810 	/*
1811 	 * Process data embedded in block pointer
1812 	 */
1813 	if (BP_IS_EMBEDDED(bp)) {
1814 		ASSERT(BPE_GET_ETYPE(bp) == BP_EMBEDDED_TYPE_DATA);
1815 
1816 		size = BPE_GET_PSIZE(bp);
1817 		ASSERT(size <= BPE_PAYLOAD_SIZE);
1818 
1819 		if (cpfunc != ZIO_COMPRESS_OFF)
1820 			pbuf = zfs_alloc(size);
1821 		else
1822 			pbuf = buf;
1823 
1824 		decode_embedded_bp_compressed(bp, pbuf);
1825 		error = 0;
1826 
1827 		if (cpfunc != ZIO_COMPRESS_OFF) {
1828 			error = zio_decompress_data(cpfunc, pbuf,
1829 			    size, buf, BP_GET_LSIZE(bp));
1830 			zfs_free(pbuf, size);
1831 		}
1832 		if (error != 0)
1833 			printf("ZFS: i/o error - unable to decompress block pointer data, error %d\n",
1834 			    error);
1835 		return (error);
1836 	}
1837 
1838 	error = EIO;
1839 
1840 	for (i = 0; i < SPA_DVAS_PER_BP; i++) {
1841 		const dva_t *dva = &bp->blk_dva[i];
1842 		vdev_t *vdev;
1843 		int vdevid;
1844 		off_t offset;
1845 
1846 		if (!dva->dva_word[0] && !dva->dva_word[1])
1847 			continue;
1848 
1849 		vdevid = DVA_GET_VDEV(dva);
1850 		offset = DVA_GET_OFFSET(dva);
1851 		STAILQ_FOREACH(vdev, &spa->spa_vdevs, v_childlink) {
1852 			if (vdev->v_id == vdevid)
1853 				break;
1854 		}
1855 		if (!vdev || !vdev->v_read)
1856 			continue;
1857 
1858 		size = BP_GET_PSIZE(bp);
1859 		if (vdev->v_read == vdev_raidz_read) {
1860 			align = 1ULL << vdev->v_top->v_ashift;
1861 			if (P2PHASE(size, align) != 0)
1862 				size = P2ROUNDUP(size, align);
1863 		}
1864 		if (size != BP_GET_PSIZE(bp) || cpfunc != ZIO_COMPRESS_OFF)
1865 			pbuf = zfs_alloc(size);
1866 		else
1867 			pbuf = buf;
1868 
1869 		if (DVA_GET_GANG(dva))
1870 			error = zio_read_gang(spa, bp, pbuf);
1871 		else
1872 			error = vdev->v_read(vdev, bp, pbuf, offset, size);
1873 		if (error == 0) {
1874 			if (cpfunc != ZIO_COMPRESS_OFF)
1875 				error = zio_decompress_data(cpfunc, pbuf,
1876 				    BP_GET_PSIZE(bp), buf, BP_GET_LSIZE(bp));
1877 			else if (size != BP_GET_PSIZE(bp))
1878 				bcopy(pbuf, buf, BP_GET_PSIZE(bp));
1879 		}
1880 		if (buf != pbuf)
1881 			zfs_free(pbuf, size);
1882 		if (error == 0)
1883 			break;
1884 	}
1885 	if (error != 0)
1886 		printf("ZFS: i/o error - all block copies unavailable\n");
1887 	return (error);
1888 }
1889 
1890 static int
1891 dnode_read(const spa_t *spa, const dnode_phys_t *dnode, off_t offset, void *buf, size_t buflen)
1892 {
1893 	int ibshift = dnode->dn_indblkshift - SPA_BLKPTRSHIFT;
1894 	int bsize = dnode->dn_datablkszsec << SPA_MINBLOCKSHIFT;
1895 	int nlevels = dnode->dn_nlevels;
1896 	int i, rc;
1897 
1898 	if (bsize > SPA_MAXBLOCKSIZE) {
1899 		printf("ZFS: I/O error - blocks larger than %llu are not "
1900 		    "supported\n", SPA_MAXBLOCKSIZE);
1901 		return (EIO);
1902 	}
1903 
1904 	/*
1905 	 * Note: bsize may not be a power of two here so we need to do an
1906 	 * actual divide rather than a bitshift.
1907 	 */
1908 	while (buflen > 0) {
1909 		uint64_t bn = offset / bsize;
1910 		int boff = offset % bsize;
1911 		int ibn;
1912 		const blkptr_t *indbp;
1913 		blkptr_t bp;
1914 
1915 		if (bn > dnode->dn_maxblkid)
1916 			return (EIO);
1917 
1918 		if (dnode == dnode_cache_obj && bn == dnode_cache_bn)
1919 			goto cached;
1920 
1921 		indbp = dnode->dn_blkptr;
1922 		for (i = 0; i < nlevels; i++) {
1923 			/*
1924 			 * Copy the bp from the indirect array so that
1925 			 * we can re-use the scratch buffer for multi-level
1926 			 * objects.
1927 			 */
1928 			ibn = bn >> ((nlevels - i - 1) * ibshift);
1929 			ibn &= ((1 << ibshift) - 1);
1930 			bp = indbp[ibn];
1931 			if (BP_IS_HOLE(&bp)) {
1932 				memset(dnode_cache_buf, 0, bsize);
1933 				break;
1934 			}
1935 			rc = zio_read(spa, &bp, dnode_cache_buf);
1936 			if (rc)
1937 				return (rc);
1938 			indbp = (const blkptr_t *) dnode_cache_buf;
1939 		}
1940 		dnode_cache_obj = dnode;
1941 		dnode_cache_bn = bn;
1942 	cached:
1943 
1944 		/*
1945 		 * The buffer contains our data block. Copy what we
1946 		 * need from it and loop.
1947 		 */
1948 		i = bsize - boff;
1949 		if (i > buflen) i = buflen;
1950 		memcpy(buf, &dnode_cache_buf[boff], i);
1951 		buf = ((char*) buf) + i;
1952 		offset += i;
1953 		buflen -= i;
1954 	}
1955 
1956 	return (0);
1957 }
1958 
1959 /*
1960  * Lookup a value in a microzap directory. Assumes that the zap
1961  * scratch buffer contains the directory contents.
1962  */
1963 static int
1964 mzap_lookup(const dnode_phys_t *dnode, const char *name, uint64_t *value)
1965 {
1966 	const mzap_phys_t *mz;
1967 	const mzap_ent_phys_t *mze;
1968 	size_t size;
1969 	int chunks, i;
1970 
1971 	/*
1972 	 * Microzap objects use exactly one block. Read the whole
1973 	 * thing.
1974 	 */
1975 	size = dnode->dn_datablkszsec * 512;
1976 
1977 	mz = (const mzap_phys_t *) zap_scratch;
1978 	chunks = size / MZAP_ENT_LEN - 1;
1979 
1980 	for (i = 0; i < chunks; i++) {
1981 		mze = &mz->mz_chunk[i];
1982 		if (!strcmp(mze->mze_name, name)) {
1983 			*value = mze->mze_value;
1984 			return (0);
1985 		}
1986 	}
1987 
1988 	return (ENOENT);
1989 }
1990 
1991 /*
1992  * Compare a name with a zap leaf entry. Return non-zero if the name
1993  * matches.
1994  */
1995 static int
1996 fzap_name_equal(const zap_leaf_t *zl, const zap_leaf_chunk_t *zc, const char *name)
1997 {
1998 	size_t namelen;
1999 	const zap_leaf_chunk_t *nc;
2000 	const char *p;
2001 
2002 	namelen = zc->l_entry.le_name_numints;
2003 
2004 	nc = &ZAP_LEAF_CHUNK(zl, zc->l_entry.le_name_chunk);
2005 	p = name;
2006 	while (namelen > 0) {
2007 		size_t len;
2008 		len = namelen;
2009 		if (len > ZAP_LEAF_ARRAY_BYTES)
2010 			len = ZAP_LEAF_ARRAY_BYTES;
2011 		if (memcmp(p, nc->l_array.la_array, len))
2012 			return (0);
2013 		p += len;
2014 		namelen -= len;
2015 		nc = &ZAP_LEAF_CHUNK(zl, nc->l_array.la_next);
2016 	}
2017 
2018 	return 1;
2019 }
2020 
2021 /*
2022  * Extract a uint64_t value from a zap leaf entry.
2023  */
2024 static uint64_t
2025 fzap_leaf_value(const zap_leaf_t *zl, const zap_leaf_chunk_t *zc)
2026 {
2027 	const zap_leaf_chunk_t *vc;
2028 	int i;
2029 	uint64_t value;
2030 	const uint8_t *p;
2031 
2032 	vc = &ZAP_LEAF_CHUNK(zl, zc->l_entry.le_value_chunk);
2033 	for (i = 0, value = 0, p = vc->l_array.la_array; i < 8; i++) {
2034 		value = (value << 8) | p[i];
2035 	}
2036 
2037 	return value;
2038 }
2039 
2040 static void
2041 stv(int len, void *addr, uint64_t value)
2042 {
2043 	switch (len) {
2044 	case 1:
2045 		*(uint8_t *)addr = value;
2046 		return;
2047 	case 2:
2048 		*(uint16_t *)addr = value;
2049 		return;
2050 	case 4:
2051 		*(uint32_t *)addr = value;
2052 		return;
2053 	case 8:
2054 		*(uint64_t *)addr = value;
2055 		return;
2056 	}
2057 }
2058 
2059 /*
2060  * Extract a array from a zap leaf entry.
2061  */
2062 static void
2063 fzap_leaf_array(const zap_leaf_t *zl, const zap_leaf_chunk_t *zc,
2064     uint64_t integer_size, uint64_t num_integers, void *buf)
2065 {
2066 	uint64_t array_int_len = zc->l_entry.le_value_intlen;
2067 	uint64_t value = 0;
2068 	uint64_t *u64 = buf;
2069 	char *p = buf;
2070 	int len = MIN(zc->l_entry.le_value_numints, num_integers);
2071 	int chunk = zc->l_entry.le_value_chunk;
2072 	int byten = 0;
2073 
2074 	if (integer_size == 8 && len == 1) {
2075 		*u64 = fzap_leaf_value(zl, zc);
2076 		return;
2077 	}
2078 
2079 	while (len > 0) {
2080 		struct zap_leaf_array *la = &ZAP_LEAF_CHUNK(zl, chunk).l_array;
2081 		int i;
2082 
2083 		ASSERT3U(chunk, <, ZAP_LEAF_NUMCHUNKS(zl));
2084 		for (i = 0; i < ZAP_LEAF_ARRAY_BYTES && len > 0; i++) {
2085 			value = (value << 8) | la->la_array[i];
2086 			byten++;
2087 			if (byten == array_int_len) {
2088 				stv(integer_size, p, value);
2089 				byten = 0;
2090 				len--;
2091 				if (len == 0)
2092 					return;
2093 				p += integer_size;
2094 			}
2095 		}
2096 		chunk = la->la_next;
2097 	}
2098 }
2099 
2100 /*
2101  * Lookup a value in a fatzap directory. Assumes that the zap scratch
2102  * buffer contains the directory header.
2103  */
2104 static int
2105 fzap_lookup(const spa_t *spa, const dnode_phys_t *dnode, const char *name,
2106     uint64_t integer_size, uint64_t num_integers, void *value)
2107 {
2108 	int bsize = dnode->dn_datablkszsec << SPA_MINBLOCKSHIFT;
2109 	zap_phys_t zh = *(zap_phys_t *) zap_scratch;
2110 	fat_zap_t z;
2111 	uint64_t *ptrtbl;
2112 	uint64_t hash;
2113 	int rc;
2114 
2115 	if (zh.zap_magic != ZAP_MAGIC)
2116 		return (EIO);
2117 
2118 	z.zap_block_shift = ilog2(bsize);
2119 	z.zap_phys = (zap_phys_t *) zap_scratch;
2120 
2121 	/*
2122 	 * Figure out where the pointer table is and read it in if necessary.
2123 	 */
2124 	if (zh.zap_ptrtbl.zt_blk) {
2125 		rc = dnode_read(spa, dnode, zh.zap_ptrtbl.zt_blk * bsize,
2126 			       zap_scratch, bsize);
2127 		if (rc)
2128 			return (rc);
2129 		ptrtbl = (uint64_t *) zap_scratch;
2130 	} else {
2131 		ptrtbl = &ZAP_EMBEDDED_PTRTBL_ENT(&z, 0);
2132 	}
2133 
2134 	hash = zap_hash(zh.zap_salt, name);
2135 
2136 	zap_leaf_t zl;
2137 	zl.l_bs = z.zap_block_shift;
2138 
2139 	off_t off = ptrtbl[hash >> (64 - zh.zap_ptrtbl.zt_shift)] << zl.l_bs;
2140 	zap_leaf_chunk_t *zc;
2141 
2142 	rc = dnode_read(spa, dnode, off, zap_scratch, bsize);
2143 	if (rc)
2144 		return (rc);
2145 
2146 	zl.l_phys = (zap_leaf_phys_t *) zap_scratch;
2147 
2148 	/*
2149 	 * Make sure this chunk matches our hash.
2150 	 */
2151 	if (zl.l_phys->l_hdr.lh_prefix_len > 0
2152 	    && zl.l_phys->l_hdr.lh_prefix
2153 	    != hash >> (64 - zl.l_phys->l_hdr.lh_prefix_len))
2154 		return (ENOENT);
2155 
2156 	/*
2157 	 * Hash within the chunk to find our entry.
2158 	 */
2159 	int shift = (64 - ZAP_LEAF_HASH_SHIFT(&zl) - zl.l_phys->l_hdr.lh_prefix_len);
2160 	int h = (hash >> shift) & ((1 << ZAP_LEAF_HASH_SHIFT(&zl)) - 1);
2161 	h = zl.l_phys->l_hash[h];
2162 	if (h == 0xffff)
2163 		return (ENOENT);
2164 	zc = &ZAP_LEAF_CHUNK(&zl, h);
2165 	while (zc->l_entry.le_hash != hash) {
2166 		if (zc->l_entry.le_next == 0xffff) {
2167 			zc = NULL;
2168 			break;
2169 		}
2170 		zc = &ZAP_LEAF_CHUNK(&zl, zc->l_entry.le_next);
2171 	}
2172 	if (fzap_name_equal(&zl, zc, name)) {
2173 		if (zc->l_entry.le_value_intlen * zc->l_entry.le_value_numints >
2174 		    integer_size * num_integers)
2175 			return (E2BIG);
2176 		fzap_leaf_array(&zl, zc, integer_size, num_integers, value);
2177 		return (0);
2178 	}
2179 
2180 	return (ENOENT);
2181 }
2182 
2183 /*
2184  * Lookup a name in a zap object and return its value as a uint64_t.
2185  */
2186 static int
2187 zap_lookup(const spa_t *spa, const dnode_phys_t *dnode, const char *name,
2188     uint64_t integer_size, uint64_t num_integers, void *value)
2189 {
2190 	int rc;
2191 	uint64_t zap_type;
2192 	size_t size = dnode->dn_datablkszsec << SPA_MINBLOCKSHIFT;
2193 
2194 	rc = dnode_read(spa, dnode, 0, zap_scratch, size);
2195 	if (rc)
2196 		return (rc);
2197 
2198 	zap_type = *(uint64_t *) zap_scratch;
2199 	if (zap_type == ZBT_MICRO)
2200 		return mzap_lookup(dnode, name, value);
2201 	else if (zap_type == ZBT_HEADER) {
2202 		return fzap_lookup(spa, dnode, name, integer_size,
2203 		    num_integers, value);
2204 	}
2205 	printf("ZFS: invalid zap_type=%d\n", (int)zap_type);
2206 	return (EIO);
2207 }
2208 
2209 /*
2210  * List a microzap directory. Assumes that the zap scratch buffer contains
2211  * the directory contents.
2212  */
2213 static int
2214 mzap_list(const dnode_phys_t *dnode, int (*callback)(const char *, uint64_t))
2215 {
2216 	const mzap_phys_t *mz;
2217 	const mzap_ent_phys_t *mze;
2218 	size_t size;
2219 	int chunks, i, rc;
2220 
2221 	/*
2222 	 * Microzap objects use exactly one block. Read the whole
2223 	 * thing.
2224 	 */
2225 	size = dnode->dn_datablkszsec * 512;
2226 	mz = (const mzap_phys_t *) zap_scratch;
2227 	chunks = size / MZAP_ENT_LEN - 1;
2228 
2229 	for (i = 0; i < chunks; i++) {
2230 		mze = &mz->mz_chunk[i];
2231 		if (mze->mze_name[0]) {
2232 			rc = callback(mze->mze_name, mze->mze_value);
2233 			if (rc != 0)
2234 				return (rc);
2235 		}
2236 	}
2237 
2238 	return (0);
2239 }
2240 
2241 /*
2242  * List a fatzap directory. Assumes that the zap scratch buffer contains
2243  * the directory header.
2244  */
2245 static int
2246 fzap_list(const spa_t *spa, const dnode_phys_t *dnode, int (*callback)(const char *, uint64_t))
2247 {
2248 	int bsize = dnode->dn_datablkszsec << SPA_MINBLOCKSHIFT;
2249 	zap_phys_t zh = *(zap_phys_t *) zap_scratch;
2250 	fat_zap_t z;
2251 	int i, j, rc;
2252 
2253 	if (zh.zap_magic != ZAP_MAGIC)
2254 		return (EIO);
2255 
2256 	z.zap_block_shift = ilog2(bsize);
2257 	z.zap_phys = (zap_phys_t *) zap_scratch;
2258 
2259 	/*
2260 	 * This assumes that the leaf blocks start at block 1. The
2261 	 * documentation isn't exactly clear on this.
2262 	 */
2263 	zap_leaf_t zl;
2264 	zl.l_bs = z.zap_block_shift;
2265 	for (i = 0; i < zh.zap_num_leafs; i++) {
2266 		off_t off = (i + 1) << zl.l_bs;
2267 		char name[256], *p;
2268 		uint64_t value;
2269 
2270 		if (dnode_read(spa, dnode, off, zap_scratch, bsize))
2271 			return (EIO);
2272 
2273 		zl.l_phys = (zap_leaf_phys_t *) zap_scratch;
2274 
2275 		for (j = 0; j < ZAP_LEAF_NUMCHUNKS(&zl); j++) {
2276 			zap_leaf_chunk_t *zc, *nc;
2277 			int namelen;
2278 
2279 			zc = &ZAP_LEAF_CHUNK(&zl, j);
2280 			if (zc->l_entry.le_type != ZAP_CHUNK_ENTRY)
2281 				continue;
2282 			namelen = zc->l_entry.le_name_numints;
2283 			if (namelen > sizeof(name))
2284 				namelen = sizeof(name);
2285 
2286 			/*
2287 			 * Paste the name back together.
2288 			 */
2289 			nc = &ZAP_LEAF_CHUNK(&zl, zc->l_entry.le_name_chunk);
2290 			p = name;
2291 			while (namelen > 0) {
2292 				int len;
2293 				len = namelen;
2294 				if (len > ZAP_LEAF_ARRAY_BYTES)
2295 					len = ZAP_LEAF_ARRAY_BYTES;
2296 				memcpy(p, nc->l_array.la_array, len);
2297 				p += len;
2298 				namelen -= len;
2299 				nc = &ZAP_LEAF_CHUNK(&zl, nc->l_array.la_next);
2300 			}
2301 
2302 			/*
2303 			 * Assume the first eight bytes of the value are
2304 			 * a uint64_t.
2305 			 */
2306 			value = fzap_leaf_value(&zl, zc);
2307 
2308 			//printf("%s 0x%jx\n", name, (uintmax_t)value);
2309 			rc = callback((const char *)name, value);
2310 			if (rc != 0)
2311 				return (rc);
2312 		}
2313 	}
2314 
2315 	return (0);
2316 }
2317 
2318 static int zfs_printf(const char *name, uint64_t value __unused)
2319 {
2320 
2321 	printf("%s\n", name);
2322 
2323 	return (0);
2324 }
2325 
2326 /*
2327  * List a zap directory.
2328  */
2329 static int
2330 zap_list(const spa_t *spa, const dnode_phys_t *dnode)
2331 {
2332 	uint64_t zap_type;
2333 	size_t size = dnode->dn_datablkszsec * 512;
2334 
2335 	if (dnode_read(spa, dnode, 0, zap_scratch, size))
2336 		return (EIO);
2337 
2338 	zap_type = *(uint64_t *) zap_scratch;
2339 	if (zap_type == ZBT_MICRO)
2340 		return mzap_list(dnode, zfs_printf);
2341 	else
2342 		return fzap_list(spa, dnode, zfs_printf);
2343 }
2344 
2345 static int
2346 objset_get_dnode(const spa_t *spa, const objset_phys_t *os, uint64_t objnum, dnode_phys_t *dnode)
2347 {
2348 	off_t offset;
2349 
2350 	offset = objnum * sizeof(dnode_phys_t);
2351 	return dnode_read(spa, &os->os_meta_dnode, offset,
2352 		dnode, sizeof(dnode_phys_t));
2353 }
2354 
2355 static int
2356 mzap_rlookup(const spa_t *spa, const dnode_phys_t *dnode, char *name, uint64_t value)
2357 {
2358 	const mzap_phys_t *mz;
2359 	const mzap_ent_phys_t *mze;
2360 	size_t size;
2361 	int chunks, i;
2362 
2363 	/*
2364 	 * Microzap objects use exactly one block. Read the whole
2365 	 * thing.
2366 	 */
2367 	size = dnode->dn_datablkszsec * 512;
2368 
2369 	mz = (const mzap_phys_t *) zap_scratch;
2370 	chunks = size / MZAP_ENT_LEN - 1;
2371 
2372 	for (i = 0; i < chunks; i++) {
2373 		mze = &mz->mz_chunk[i];
2374 		if (value == mze->mze_value) {
2375 			strcpy(name, mze->mze_name);
2376 			return (0);
2377 		}
2378 	}
2379 
2380 	return (ENOENT);
2381 }
2382 
2383 static void
2384 fzap_name_copy(const zap_leaf_t *zl, const zap_leaf_chunk_t *zc, char *name)
2385 {
2386 	size_t namelen;
2387 	const zap_leaf_chunk_t *nc;
2388 	char *p;
2389 
2390 	namelen = zc->l_entry.le_name_numints;
2391 
2392 	nc = &ZAP_LEAF_CHUNK(zl, zc->l_entry.le_name_chunk);
2393 	p = name;
2394 	while (namelen > 0) {
2395 		size_t len;
2396 		len = namelen;
2397 		if (len > ZAP_LEAF_ARRAY_BYTES)
2398 			len = ZAP_LEAF_ARRAY_BYTES;
2399 		memcpy(p, nc->l_array.la_array, len);
2400 		p += len;
2401 		namelen -= len;
2402 		nc = &ZAP_LEAF_CHUNK(zl, nc->l_array.la_next);
2403 	}
2404 
2405 	*p = '\0';
2406 }
2407 
2408 static int
2409 fzap_rlookup(const spa_t *spa, const dnode_phys_t *dnode, char *name, uint64_t value)
2410 {
2411 	int bsize = dnode->dn_datablkszsec << SPA_MINBLOCKSHIFT;
2412 	zap_phys_t zh = *(zap_phys_t *) zap_scratch;
2413 	fat_zap_t z;
2414 	int i, j;
2415 
2416 	if (zh.zap_magic != ZAP_MAGIC)
2417 		return (EIO);
2418 
2419 	z.zap_block_shift = ilog2(bsize);
2420 	z.zap_phys = (zap_phys_t *) zap_scratch;
2421 
2422 	/*
2423 	 * This assumes that the leaf blocks start at block 1. The
2424 	 * documentation isn't exactly clear on this.
2425 	 */
2426 	zap_leaf_t zl;
2427 	zl.l_bs = z.zap_block_shift;
2428 	for (i = 0; i < zh.zap_num_leafs; i++) {
2429 		off_t off = (i + 1) << zl.l_bs;
2430 
2431 		if (dnode_read(spa, dnode, off, zap_scratch, bsize))
2432 			return (EIO);
2433 
2434 		zl.l_phys = (zap_leaf_phys_t *) zap_scratch;
2435 
2436 		for (j = 0; j < ZAP_LEAF_NUMCHUNKS(&zl); j++) {
2437 			zap_leaf_chunk_t *zc;
2438 
2439 			zc = &ZAP_LEAF_CHUNK(&zl, j);
2440 			if (zc->l_entry.le_type != ZAP_CHUNK_ENTRY)
2441 				continue;
2442 			if (zc->l_entry.le_value_intlen != 8 ||
2443 			    zc->l_entry.le_value_numints != 1)
2444 				continue;
2445 
2446 			if (fzap_leaf_value(&zl, zc) == value) {
2447 				fzap_name_copy(&zl, zc, name);
2448 				return (0);
2449 			}
2450 		}
2451 	}
2452 
2453 	return (ENOENT);
2454 }
2455 
2456 static int
2457 zap_rlookup(const spa_t *spa, const dnode_phys_t *dnode, char *name, uint64_t value)
2458 {
2459 	int rc;
2460 	uint64_t zap_type;
2461 	size_t size = dnode->dn_datablkszsec * 512;
2462 
2463 	rc = dnode_read(spa, dnode, 0, zap_scratch, size);
2464 	if (rc)
2465 		return (rc);
2466 
2467 	zap_type = *(uint64_t *) zap_scratch;
2468 	if (zap_type == ZBT_MICRO)
2469 		return mzap_rlookup(spa, dnode, name, value);
2470 	else
2471 		return fzap_rlookup(spa, dnode, name, value);
2472 }
2473 
2474 static int
2475 zfs_rlookup(const spa_t *spa, uint64_t objnum, char *result)
2476 {
2477 	char name[256];
2478 	char component[256];
2479 	uint64_t dir_obj, parent_obj, child_dir_zapobj;
2480 	dnode_phys_t child_dir_zap, dataset, dir, parent;
2481 	dsl_dir_phys_t *dd;
2482 	dsl_dataset_phys_t *ds;
2483 	char *p;
2484 	int len;
2485 
2486 	p = &name[sizeof(name) - 1];
2487 	*p = '\0';
2488 
2489 	if (objset_get_dnode(spa, &spa->spa_mos, objnum, &dataset)) {
2490 		printf("ZFS: can't find dataset %ju\n", (uintmax_t)objnum);
2491 		return (EIO);
2492 	}
2493 	ds = (dsl_dataset_phys_t *)&dataset.dn_bonus;
2494 	dir_obj = ds->ds_dir_obj;
2495 
2496 	for (;;) {
2497 		if (objset_get_dnode(spa, &spa->spa_mos, dir_obj, &dir) != 0)
2498 			return (EIO);
2499 		dd = (dsl_dir_phys_t *)&dir.dn_bonus;
2500 
2501 		/* Actual loop condition. */
2502 		parent_obj  = dd->dd_parent_obj;
2503 		if (parent_obj == 0)
2504 			break;
2505 
2506 		if (objset_get_dnode(spa, &spa->spa_mos, parent_obj, &parent) != 0)
2507 			return (EIO);
2508 		dd = (dsl_dir_phys_t *)&parent.dn_bonus;
2509 		child_dir_zapobj = dd->dd_child_dir_zapobj;
2510 		if (objset_get_dnode(spa, &spa->spa_mos, child_dir_zapobj, &child_dir_zap) != 0)
2511 			return (EIO);
2512 		if (zap_rlookup(spa, &child_dir_zap, component, dir_obj) != 0)
2513 			return (EIO);
2514 
2515 		len = strlen(component);
2516 		p -= len;
2517 		memcpy(p, component, len);
2518 		--p;
2519 		*p = '/';
2520 
2521 		/* Actual loop iteration. */
2522 		dir_obj = parent_obj;
2523 	}
2524 
2525 	if (*p != '\0')
2526 		++p;
2527 	strcpy(result, p);
2528 
2529 	return (0);
2530 }
2531 
2532 static int
2533 zfs_lookup_dataset(const spa_t *spa, const char *name, uint64_t *objnum)
2534 {
2535 	char element[256];
2536 	uint64_t dir_obj, child_dir_zapobj;
2537 	dnode_phys_t child_dir_zap, dir;
2538 	dsl_dir_phys_t *dd;
2539 	const char *p, *q;
2540 
2541 	if (objset_get_dnode(spa, &spa->spa_mos, DMU_POOL_DIRECTORY_OBJECT, &dir))
2542 		return (EIO);
2543 	if (zap_lookup(spa, &dir, DMU_POOL_ROOT_DATASET, sizeof (dir_obj),
2544 	    1, &dir_obj))
2545 		return (EIO);
2546 
2547 	p = name;
2548 	for (;;) {
2549 		if (objset_get_dnode(spa, &spa->spa_mos, dir_obj, &dir))
2550 			return (EIO);
2551 		dd = (dsl_dir_phys_t *)&dir.dn_bonus;
2552 
2553 		while (*p == '/')
2554 			p++;
2555 		/* Actual loop condition #1. */
2556 		if (*p == '\0')
2557 			break;
2558 
2559 		q = strchr(p, '/');
2560 		if (q) {
2561 			memcpy(element, p, q - p);
2562 			element[q - p] = '\0';
2563 			p = q + 1;
2564 		} else {
2565 			strcpy(element, p);
2566 			p += strlen(p);
2567 		}
2568 
2569 		child_dir_zapobj = dd->dd_child_dir_zapobj;
2570 		if (objset_get_dnode(spa, &spa->spa_mos, child_dir_zapobj, &child_dir_zap) != 0)
2571 			return (EIO);
2572 
2573 		/* Actual loop condition #2. */
2574 		if (zap_lookup(spa, &child_dir_zap, element, sizeof (dir_obj),
2575 		    1, &dir_obj) != 0)
2576 			return (ENOENT);
2577 	}
2578 
2579 	*objnum = dd->dd_head_dataset_obj;
2580 	return (0);
2581 }
2582 
2583 #ifndef BOOT2
2584 static int
2585 zfs_list_dataset(const spa_t *spa, uint64_t objnum/*, int pos, char *entry*/)
2586 {
2587 	uint64_t dir_obj, child_dir_zapobj;
2588 	dnode_phys_t child_dir_zap, dir, dataset;
2589 	dsl_dataset_phys_t *ds;
2590 	dsl_dir_phys_t *dd;
2591 
2592 	if (objset_get_dnode(spa, &spa->spa_mos, objnum, &dataset)) {
2593 		printf("ZFS: can't find dataset %ju\n", (uintmax_t)objnum);
2594 		return (EIO);
2595 	}
2596 	ds = (dsl_dataset_phys_t *) &dataset.dn_bonus;
2597 	dir_obj = ds->ds_dir_obj;
2598 
2599 	if (objset_get_dnode(spa, &spa->spa_mos, dir_obj, &dir)) {
2600 		printf("ZFS: can't find dirobj %ju\n", (uintmax_t)dir_obj);
2601 		return (EIO);
2602 	}
2603 	dd = (dsl_dir_phys_t *)&dir.dn_bonus;
2604 
2605 	child_dir_zapobj = dd->dd_child_dir_zapobj;
2606 	if (objset_get_dnode(spa, &spa->spa_mos, child_dir_zapobj, &child_dir_zap) != 0) {
2607 		printf("ZFS: can't find child zap %ju\n", (uintmax_t)dir_obj);
2608 		return (EIO);
2609 	}
2610 
2611 	return (zap_list(spa, &child_dir_zap) != 0);
2612 }
2613 
2614 int
2615 zfs_callback_dataset(const spa_t *spa, uint64_t objnum, int (*callback)(const char *, uint64_t))
2616 {
2617 	uint64_t dir_obj, child_dir_zapobj, zap_type;
2618 	dnode_phys_t child_dir_zap, dir, dataset;
2619 	dsl_dataset_phys_t *ds;
2620 	dsl_dir_phys_t *dd;
2621 	int err;
2622 
2623 	err = objset_get_dnode(spa, &spa->spa_mos, objnum, &dataset);
2624 	if (err != 0) {
2625 		printf("ZFS: can't find dataset %ju\n", (uintmax_t)objnum);
2626 		return (err);
2627 	}
2628 	ds = (dsl_dataset_phys_t *) &dataset.dn_bonus;
2629 	dir_obj = ds->ds_dir_obj;
2630 
2631 	err = objset_get_dnode(spa, &spa->spa_mos, dir_obj, &dir);
2632 	if (err != 0) {
2633 		printf("ZFS: can't find dirobj %ju\n", (uintmax_t)dir_obj);
2634 		return (err);
2635 	}
2636 	dd = (dsl_dir_phys_t *)&dir.dn_bonus;
2637 
2638 	child_dir_zapobj = dd->dd_child_dir_zapobj;
2639 	err = objset_get_dnode(spa, &spa->spa_mos, child_dir_zapobj, &child_dir_zap);
2640 	if (err != 0) {
2641 		printf("ZFS: can't find child zap %ju\n", (uintmax_t)dir_obj);
2642 		return (err);
2643 	}
2644 
2645 	err = dnode_read(spa, &child_dir_zap, 0, zap_scratch, child_dir_zap.dn_datablkszsec * 512);
2646 	if (err != 0)
2647 		return (err);
2648 
2649 	zap_type = *(uint64_t *) zap_scratch;
2650 	if (zap_type == ZBT_MICRO)
2651 		return mzap_list(&child_dir_zap, callback);
2652 	else
2653 		return fzap_list(spa, &child_dir_zap, callback);
2654 }
2655 #endif
2656 
2657 /*
2658  * Find the object set given the object number of its dataset object
2659  * and return its details in *objset
2660  */
2661 static int
2662 zfs_mount_dataset(const spa_t *spa, uint64_t objnum, objset_phys_t *objset)
2663 {
2664 	dnode_phys_t dataset;
2665 	dsl_dataset_phys_t *ds;
2666 
2667 	if (objset_get_dnode(spa, &spa->spa_mos, objnum, &dataset)) {
2668 		printf("ZFS: can't find dataset %ju\n", (uintmax_t)objnum);
2669 		return (EIO);
2670 	}
2671 
2672 	ds = (dsl_dataset_phys_t *) &dataset.dn_bonus;
2673 	if (zio_read(spa, &ds->ds_bp, objset)) {
2674 		printf("ZFS: can't read object set for dataset %ju\n",
2675 		    (uintmax_t)objnum);
2676 		return (EIO);
2677 	}
2678 
2679 	return (0);
2680 }
2681 
2682 /*
2683  * Find the object set pointed to by the BOOTFS property or the root
2684  * dataset if there is none and return its details in *objset
2685  */
2686 static int
2687 zfs_get_root(const spa_t *spa, uint64_t *objid)
2688 {
2689 	dnode_phys_t dir, propdir;
2690 	uint64_t props, bootfs, root;
2691 
2692 	*objid = 0;
2693 
2694 	/*
2695 	 * Start with the MOS directory object.
2696 	 */
2697 	if (objset_get_dnode(spa, &spa->spa_mos, DMU_POOL_DIRECTORY_OBJECT, &dir)) {
2698 		printf("ZFS: can't read MOS object directory\n");
2699 		return (EIO);
2700 	}
2701 
2702 	/*
2703 	 * Lookup the pool_props and see if we can find a bootfs.
2704 	 */
2705 	if (zap_lookup(spa, &dir, DMU_POOL_PROPS, sizeof (props), 1, &props) == 0
2706 	     && objset_get_dnode(spa, &spa->spa_mos, props, &propdir) == 0
2707 	     && zap_lookup(spa, &propdir, "bootfs", sizeof (bootfs), 1, &bootfs) == 0
2708 	     && bootfs != 0)
2709 	{
2710 		*objid = bootfs;
2711 		return (0);
2712 	}
2713 	/*
2714 	 * Lookup the root dataset directory
2715 	 */
2716 	if (zap_lookup(spa, &dir, DMU_POOL_ROOT_DATASET, sizeof (root), 1, &root)
2717 	    || objset_get_dnode(spa, &spa->spa_mos, root, &dir)) {
2718 		printf("ZFS: can't find root dsl_dir\n");
2719 		return (EIO);
2720 	}
2721 
2722 	/*
2723 	 * Use the information from the dataset directory's bonus buffer
2724 	 * to find the dataset object and from that the object set itself.
2725 	 */
2726 	dsl_dir_phys_t *dd = (dsl_dir_phys_t *) &dir.dn_bonus;
2727 	*objid = dd->dd_head_dataset_obj;
2728 	return (0);
2729 }
2730 
2731 static int
2732 zfs_mount(const spa_t *spa, uint64_t rootobj, struct zfsmount *mount)
2733 {
2734 
2735 	mount->spa = spa;
2736 
2737 	/*
2738 	 * Find the root object set if not explicitly provided
2739 	 */
2740 	if (rootobj == 0 && zfs_get_root(spa, &rootobj)) {
2741 		printf("ZFS: can't find root filesystem\n");
2742 		return (EIO);
2743 	}
2744 
2745 	if (zfs_mount_dataset(spa, rootobj, &mount->objset)) {
2746 		printf("ZFS: can't open root filesystem\n");
2747 		return (EIO);
2748 	}
2749 
2750 	mount->rootobj = rootobj;
2751 
2752 	return (0);
2753 }
2754 
2755 /*
2756  * callback function for feature name checks.
2757  */
2758 static int
2759 check_feature(const char *name, uint64_t value)
2760 {
2761 	int i;
2762 
2763 	if (value == 0)
2764 		return (0);
2765 	if (name[0] == '\0')
2766 		return (0);
2767 
2768 	for (i = 0; features_for_read[i] != NULL; i++) {
2769 		if (strcmp(name, features_for_read[i]) == 0)
2770 			return (0);
2771 	}
2772 	printf("ZFS: unsupported feature: %s\n", name);
2773 	return (EIO);
2774 }
2775 
2776 /*
2777  * Checks whether the MOS features that are active are supported.
2778  */
2779 static int
2780 check_mos_features(const spa_t *spa)
2781 {
2782 	dnode_phys_t dir;
2783 	uint64_t objnum, zap_type;
2784 	size_t size;
2785 	int rc;
2786 
2787 	if ((rc = objset_get_dnode(spa, &spa->spa_mos, DMU_OT_OBJECT_DIRECTORY,
2788 	    &dir)) != 0)
2789 		return (rc);
2790 	if ((rc = zap_lookup(spa, &dir, DMU_POOL_FEATURES_FOR_READ,
2791 	    sizeof (objnum), 1, &objnum)) != 0) {
2792 		/*
2793 		 * It is older pool without features. As we have already
2794 		 * tested the label, just return without raising the error.
2795 		 */
2796 		return (0);
2797 	}
2798 
2799 	if ((rc = objset_get_dnode(spa, &spa->spa_mos, objnum, &dir)) != 0)
2800 		return (rc);
2801 
2802 	if (dir.dn_type != DMU_OTN_ZAP_METADATA)
2803 		return (EIO);
2804 
2805 	size = dir.dn_datablkszsec * 512;
2806 	if (dnode_read(spa, &dir, 0, zap_scratch, size))
2807 		return (EIO);
2808 
2809 	zap_type = *(uint64_t *) zap_scratch;
2810 	if (zap_type == ZBT_MICRO)
2811 		rc = mzap_list(&dir, check_feature);
2812 	else
2813 		rc = fzap_list(spa, &dir, check_feature);
2814 
2815 	return (rc);
2816 }
2817 
2818 static int
2819 load_nvlist(spa_t *spa, uint64_t obj, unsigned char **value)
2820 {
2821 	dnode_phys_t dir;
2822 	size_t size;
2823 	int rc;
2824 	unsigned char *nv;
2825 
2826 	*value = NULL;
2827 	if ((rc = objset_get_dnode(spa, &spa->spa_mos, obj, &dir)) != 0)
2828 		return (rc);
2829 	if (dir.dn_type != DMU_OT_PACKED_NVLIST &&
2830 	    dir.dn_bonustype != DMU_OT_PACKED_NVLIST_SIZE) {
2831 		return (EIO);
2832 	}
2833 
2834 	if (dir.dn_bonuslen != sizeof (uint64_t))
2835 		return (EIO);
2836 
2837 	size = *(uint64_t *)DN_BONUS(&dir);
2838 	nv = malloc(size);
2839 	if (nv == NULL)
2840 		return (ENOMEM);
2841 
2842 	rc = dnode_read(spa, &dir, 0, nv, size);
2843 	if (rc != 0) {
2844 		free(nv);
2845 		nv = NULL;
2846 		return (rc);
2847 	}
2848 	*value = nv;
2849 	return (rc);
2850 }
2851 
2852 static int
2853 zfs_spa_init(spa_t *spa)
2854 {
2855 	dnode_phys_t dir;
2856 	uint64_t config_object;
2857 	unsigned char *nvlist;
2858 	char *type;
2859 	const unsigned char *nv;
2860 	int nkids, rc;
2861 
2862 	if (zio_read(spa, &spa->spa_uberblock.ub_rootbp, &spa->spa_mos)) {
2863 		printf("ZFS: can't read MOS of pool %s\n", spa->spa_name);
2864 		return (EIO);
2865 	}
2866 	if (spa->spa_mos.os_type != DMU_OST_META) {
2867 		printf("ZFS: corrupted MOS of pool %s\n", spa->spa_name);
2868 		return (EIO);
2869 	}
2870 
2871 	if (objset_get_dnode(spa, &spa->spa_mos, DMU_POOL_DIRECTORY_OBJECT,
2872 	    &dir)) {
2873 		printf("ZFS: failed to read pool %s directory object\n",
2874 		    spa->spa_name);
2875 		return (EIO);
2876 	}
2877 	/* this is allowed to fail, older pools do not have salt */
2878 	rc = zap_lookup(spa, &dir, DMU_POOL_CHECKSUM_SALT, 1,
2879 	    sizeof (spa->spa_cksum_salt.zcs_bytes),
2880 	    spa->spa_cksum_salt.zcs_bytes);
2881 
2882 	rc = check_mos_features(spa);
2883 	if (rc != 0) {
2884 		printf("ZFS: pool %s is not supported\n", spa->spa_name);
2885 		return (rc);
2886 	}
2887 
2888 	rc = zap_lookup(spa, &dir, DMU_POOL_CONFIG,
2889 	    sizeof (config_object), 1, &config_object);
2890 	if (rc != 0) {
2891 		printf("ZFS: can not read MOS %s\n", DMU_POOL_CONFIG);
2892 		return (EIO);
2893 	}
2894 	rc = load_nvlist(spa, config_object, &nvlist);
2895 	if (rc != 0)
2896 		return (rc);
2897 
2898 	/* Update vdevs from MOS config. */
2899 	if (nvlist_find(nvlist + 4, ZPOOL_CONFIG_VDEV_TREE, DATA_TYPE_NVLIST,
2900 	    NULL, &nv)) {
2901 		rc = EIO;
2902 		goto done;
2903 	}
2904 
2905 	if (nvlist_find(nv, ZPOOL_CONFIG_TYPE, DATA_TYPE_STRING,
2906             NULL, &type)) {
2907 		printf("ZFS: can't find vdev details\n");
2908 		rc = ENOENT;
2909 		goto done;
2910 	}
2911 	if (strcmp(type, VDEV_TYPE_ROOT) != 0) {
2912 		rc = ENOENT;
2913 		goto done;
2914 	}
2915 
2916 	rc = nvlist_find(nv, ZPOOL_CONFIG_CHILDREN, DATA_TYPE_NVLIST_ARRAY,
2917             &nkids, &nv);
2918 	if (rc != 0)
2919 		goto done;
2920 
2921 	for (int i = 0; i < nkids; i++) {
2922 		vdev_t *vd, *prev, *kid = NULL;
2923 		rc = vdev_init_from_nvlist(nv, NULL, &kid, 0);
2924 		if (rc != 0) {
2925 			printf("vdev_init_from_nvlist: %d\n", rc);
2926 			break;
2927 		}
2928 		kid->spa = spa;
2929 		prev = NULL;
2930 		STAILQ_FOREACH(vd, &spa->spa_vdevs, v_childlink) {
2931 			/* Already present? */
2932 			if (kid->v_id == vd->v_id) {
2933 				kid = NULL;
2934 				break;
2935 			}
2936 			if (vd->v_id > kid->v_id) {
2937 				if (prev == NULL) {
2938 					STAILQ_INSERT_HEAD(&spa->spa_vdevs,
2939 					    kid, v_childlink);
2940 				} else {
2941 					STAILQ_INSERT_AFTER(&spa->spa_vdevs,
2942 					    prev, kid, v_childlink);
2943 				}
2944 				kid = NULL;
2945 				break;
2946 			}
2947 			prev = vd;
2948 		}
2949 		if (kid != NULL)
2950 			STAILQ_INSERT_TAIL(&spa->spa_vdevs, kid, v_childlink);
2951 		nv = nvlist_next(nv);
2952 	}
2953 	rc = 0;
2954 done:
2955 	free(nvlist);
2956 	return (rc);
2957 }
2958 
2959 static int
2960 zfs_dnode_stat(const spa_t *spa, dnode_phys_t *dn, struct stat *sb)
2961 {
2962 
2963 	if (dn->dn_bonustype != DMU_OT_SA) {
2964 		znode_phys_t *zp = (znode_phys_t *)dn->dn_bonus;
2965 
2966 		sb->st_mode = zp->zp_mode;
2967 		sb->st_uid = zp->zp_uid;
2968 		sb->st_gid = zp->zp_gid;
2969 		sb->st_size = zp->zp_size;
2970 	} else {
2971 		sa_hdr_phys_t *sahdrp;
2972 		int hdrsize;
2973 		size_t size = 0;
2974 		void *buf = NULL;
2975 
2976 		if (dn->dn_bonuslen != 0)
2977 			sahdrp = (sa_hdr_phys_t *)DN_BONUS(dn);
2978 		else {
2979 			if ((dn->dn_flags & DNODE_FLAG_SPILL_BLKPTR) != 0) {
2980 				blkptr_t *bp = DN_SPILL_BLKPTR(dn);
2981 				int error;
2982 
2983 				size = BP_GET_LSIZE(bp);
2984 				buf = zfs_alloc(size);
2985 				error = zio_read(spa, bp, buf);
2986 				if (error != 0) {
2987 					zfs_free(buf, size);
2988 					return (error);
2989 				}
2990 				sahdrp = buf;
2991 			} else {
2992 				return (EIO);
2993 			}
2994 		}
2995 		hdrsize = SA_HDR_SIZE(sahdrp);
2996 		sb->st_mode = *(uint64_t *)((char *)sahdrp + hdrsize +
2997 		    SA_MODE_OFFSET);
2998 		sb->st_uid = *(uint64_t *)((char *)sahdrp + hdrsize +
2999 		    SA_UID_OFFSET);
3000 		sb->st_gid = *(uint64_t *)((char *)sahdrp + hdrsize +
3001 		    SA_GID_OFFSET);
3002 		sb->st_size = *(uint64_t *)((char *)sahdrp + hdrsize +
3003 		    SA_SIZE_OFFSET);
3004 		if (buf != NULL)
3005 			zfs_free(buf, size);
3006 	}
3007 
3008 	return (0);
3009 }
3010 
3011 static int
3012 zfs_dnode_readlink(const spa_t *spa, dnode_phys_t *dn, char *path, size_t psize)
3013 {
3014 	int rc = 0;
3015 
3016 	if (dn->dn_bonustype == DMU_OT_SA) {
3017 		sa_hdr_phys_t *sahdrp = NULL;
3018 		size_t size = 0;
3019 		void *buf = NULL;
3020 		int hdrsize;
3021 		char *p;
3022 
3023 		if (dn->dn_bonuslen != 0)
3024 			sahdrp = (sa_hdr_phys_t *)DN_BONUS(dn);
3025 		else {
3026 			blkptr_t *bp;
3027 
3028 			if ((dn->dn_flags & DNODE_FLAG_SPILL_BLKPTR) == 0)
3029 				return (EIO);
3030 			bp = DN_SPILL_BLKPTR(dn);
3031 
3032 			size = BP_GET_LSIZE(bp);
3033 			buf = zfs_alloc(size);
3034 			rc = zio_read(spa, bp, buf);
3035 			if (rc != 0) {
3036 				zfs_free(buf, size);
3037 				return (rc);
3038 			}
3039 			sahdrp = buf;
3040 		}
3041 		hdrsize = SA_HDR_SIZE(sahdrp);
3042 		p = (char *)((uintptr_t)sahdrp + hdrsize + SA_SYMLINK_OFFSET);
3043 		memcpy(path, p, psize);
3044 		if (buf != NULL)
3045 			zfs_free(buf, size);
3046 		return (0);
3047 	}
3048 	/*
3049 	 * Second test is purely to silence bogus compiler
3050 	 * warning about accessing past the end of dn_bonus.
3051 	 */
3052 	if (psize + sizeof(znode_phys_t) <= dn->dn_bonuslen &&
3053 	    sizeof(znode_phys_t) <= sizeof(dn->dn_bonus)) {
3054 		memcpy(path, &dn->dn_bonus[sizeof(znode_phys_t)], psize);
3055 	} else {
3056 		rc = dnode_read(spa, dn, 0, path, psize);
3057 	}
3058 	return (rc);
3059 }
3060 
3061 struct obj_list {
3062 	uint64_t		objnum;
3063 	STAILQ_ENTRY(obj_list)	entry;
3064 };
3065 
3066 /*
3067  * Lookup a file and return its dnode.
3068  */
3069 static int
3070 zfs_lookup(const struct zfsmount *mount, const char *upath, dnode_phys_t *dnode)
3071 {
3072 	int rc;
3073 	uint64_t objnum;
3074 	const spa_t *spa;
3075 	dnode_phys_t dn;
3076 	const char *p, *q;
3077 	char element[256];
3078 	char path[1024];
3079 	int symlinks_followed = 0;
3080 	struct stat sb;
3081 	struct obj_list *entry, *tentry;
3082 	STAILQ_HEAD(, obj_list) on_cache = STAILQ_HEAD_INITIALIZER(on_cache);
3083 
3084 	spa = mount->spa;
3085 	if (mount->objset.os_type != DMU_OST_ZFS) {
3086 		printf("ZFS: unexpected object set type %ju\n",
3087 		    (uintmax_t)mount->objset.os_type);
3088 		return (EIO);
3089 	}
3090 
3091 	if ((entry = malloc(sizeof(struct obj_list))) == NULL)
3092 		return (ENOMEM);
3093 
3094 	/*
3095 	 * Get the root directory dnode.
3096 	 */
3097 	rc = objset_get_dnode(spa, &mount->objset, MASTER_NODE_OBJ, &dn);
3098 	if (rc) {
3099 		free(entry);
3100 		return (rc);
3101 	}
3102 
3103 	rc = zap_lookup(spa, &dn, ZFS_ROOT_OBJ, sizeof (objnum), 1, &objnum);
3104 	if (rc) {
3105 		free(entry);
3106 		return (rc);
3107 	}
3108 	entry->objnum = objnum;
3109 	STAILQ_INSERT_HEAD(&on_cache, entry, entry);
3110 
3111 	rc = objset_get_dnode(spa, &mount->objset, objnum, &dn);
3112 	if (rc != 0)
3113 		goto done;
3114 
3115 	p = upath;
3116 	while (p && *p) {
3117 		rc = objset_get_dnode(spa, &mount->objset, objnum, &dn);
3118 		if (rc != 0)
3119 			goto done;
3120 
3121 		while (*p == '/')
3122 			p++;
3123 		if (*p == '\0')
3124 			break;
3125 		q = p;
3126 		while (*q != '\0' && *q != '/')
3127 			q++;
3128 
3129 		/* skip dot */
3130 		if (p + 1 == q && p[0] == '.') {
3131 			p++;
3132 			continue;
3133 		}
3134 		/* double dot */
3135 		if (p + 2 == q && p[0] == '.' && p[1] == '.') {
3136 			p += 2;
3137 			if (STAILQ_FIRST(&on_cache) ==
3138 			    STAILQ_LAST(&on_cache, obj_list, entry)) {
3139 				rc = ENOENT;
3140 				goto done;
3141 			}
3142 			entry = STAILQ_FIRST(&on_cache);
3143 			STAILQ_REMOVE_HEAD(&on_cache, entry);
3144 			free(entry);
3145 			objnum = (STAILQ_FIRST(&on_cache))->objnum;
3146 			continue;
3147 		}
3148 		if (q - p + 1 > sizeof(element)) {
3149 			rc = ENAMETOOLONG;
3150 			goto done;
3151 		}
3152 		memcpy(element, p, q - p);
3153 		element[q - p] = 0;
3154 		p = q;
3155 
3156 		if ((rc = zfs_dnode_stat(spa, &dn, &sb)) != 0)
3157 			goto done;
3158 		if (!S_ISDIR(sb.st_mode)) {
3159 			rc = ENOTDIR;
3160 			goto done;
3161 		}
3162 
3163 		rc = zap_lookup(spa, &dn, element, sizeof (objnum), 1, &objnum);
3164 		if (rc)
3165 			goto done;
3166 		objnum = ZFS_DIRENT_OBJ(objnum);
3167 
3168 		if ((entry = malloc(sizeof(struct obj_list))) == NULL) {
3169 			rc = ENOMEM;
3170 			goto done;
3171 		}
3172 		entry->objnum = objnum;
3173 		STAILQ_INSERT_HEAD(&on_cache, entry, entry);
3174 		rc = objset_get_dnode(spa, &mount->objset, objnum, &dn);
3175 		if (rc)
3176 			goto done;
3177 
3178 		/*
3179 		 * Check for symlink.
3180 		 */
3181 		rc = zfs_dnode_stat(spa, &dn, &sb);
3182 		if (rc)
3183 			goto done;
3184 		if (S_ISLNK(sb.st_mode)) {
3185 			if (symlinks_followed > 10) {
3186 				rc = EMLINK;
3187 				goto done;
3188 			}
3189 			symlinks_followed++;
3190 
3191 			/*
3192 			 * Read the link value and copy the tail of our
3193 			 * current path onto the end.
3194 			 */
3195 			if (sb.st_size + strlen(p) + 1 > sizeof(path)) {
3196 				rc = ENAMETOOLONG;
3197 				goto done;
3198 			}
3199 			strcpy(&path[sb.st_size], p);
3200 
3201 			rc = zfs_dnode_readlink(spa, &dn, path, sb.st_size);
3202 			if (rc != 0)
3203 				goto done;
3204 
3205 			/*
3206 			 * Restart with the new path, starting either at
3207 			 * the root or at the parent depending whether or
3208 			 * not the link is relative.
3209 			 */
3210 			p = path;
3211 			if (*p == '/') {
3212 				while (STAILQ_FIRST(&on_cache) !=
3213 				    STAILQ_LAST(&on_cache, obj_list, entry)) {
3214 					entry = STAILQ_FIRST(&on_cache);
3215 					STAILQ_REMOVE_HEAD(&on_cache, entry);
3216 					free(entry);
3217 				}
3218 			} else {
3219 				entry = STAILQ_FIRST(&on_cache);
3220 				STAILQ_REMOVE_HEAD(&on_cache, entry);
3221 				free(entry);
3222 			}
3223 			objnum = (STAILQ_FIRST(&on_cache))->objnum;
3224 		}
3225 	}
3226 
3227 	*dnode = dn;
3228 done:
3229 	STAILQ_FOREACH_SAFE(entry, &on_cache, entry, tentry)
3230 		free(entry);
3231 	return (rc);
3232 }
3233