xref: /illumos-gate/usr/src/grub/grub-0.97/stage2/fsys_zfs.c (revision ae8180db892a16c89bf25609727063514ca6b719)
1 /*
2  *  GRUB  --  GRand Unified Bootloader
3  *  Copyright (C) 1999,2000,2001,2002,2003,2004  Free Software Foundation, Inc.
4  *
5  *  This program is free software; you can redistribute it and/or modify
6  *  it under the terms of the GNU General Public License as published by
7  *  the Free Software Foundation; either version 2 of the License, or
8  *  (at your option) any later version.
9  *
10  *  This program is distributed in the hope that it will be useful,
11  *  but WITHOUT ANY WARRANTY; without even the implied warranty of
12  *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
13  *  GNU General Public License for more details.
14  *
15  *  You should have received a copy of the GNU General Public License
16  *  along with this program; if not, write to the Free Software
17  *  Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
18  */
19 /*
20  * Copyright 2007 Sun Microsystems, Inc.  All rights reserved.
21  * Use is subject to license terms.
22  */
23 #pragma ident	"%Z%%M%	%I%	%E% SMI"
24 
25 /*
26  * The zfs plug-in routines for GRUB are:
27  *
28  * zfs_mount() - locates a valid uberblock of the root pool and reads
29  *		in its MOS at the memory address MOS.
30  *
31  * zfs_open() - locates a plain file object by following the MOS
32  *		and places its dnode at the memory address DNODE.
33  *
34  * zfs_read() - read in the data blocks pointed by the DNODE.
35  *
36  * ZFS_SCRATCH is used as a working area.
37  *
38  * (memory addr)   MOS      DNODE	ZFS_SCRATCH
39  *		    |         |          |
40  *	    +-------V---------V----------V---------------+
41  *   memory |       | dnode   | dnode    |  scratch      |
42  *	    |       | 512B    | 512B     |  area         |
43  *	    +--------------------------------------------+
44  */
45 
46 #ifdef	FSYS_ZFS
47 
48 #include "shared.h"
49 #include "filesys.h"
50 #include "fsys_zfs.h"
51 
52 /* cache for a file block of the currently zfs_open()-ed file */
53 static void *file_buf = NULL;
54 static uint64_t file_start = 0;
55 static uint64_t file_end = 0;
56 
57 /* cache for a dnode block */
58 static dnode_phys_t *dnode_buf = NULL;
59 static dnode_phys_t *dnode_mdn = NULL;
60 static uint64_t dnode_start = 0;
61 static uint64_t dnode_end = 0;
62 
63 static char *stackbase;
64 
65 decomp_entry_t decomp_table[ZIO_COMPRESS_FUNCTIONS] =
66 {
67 	{"noop", 0},
68 	{"on", lzjb_decompress}, 	/* ZIO_COMPRESS_ON */
69 	{"off", 0},
70 	{"lzjb", lzjb_decompress}	/* ZIO_COMPRESS_LZJB */
71 };
72 
73 /*
74  * Our own version of bcmp().
75  */
76 static int
77 zfs_bcmp(const void *s1, const void *s2, size_t n)
78 {
79 	const uchar_t *ps1 = s1;
80 	const uchar_t *ps2 = s2;
81 
82 	if (s1 != s2 && n != 0) {
83 		do {
84 			if (*ps1++ != *ps2++)
85 				return (1);
86 		} while (--n != 0);
87 	}
88 
89 	return (0);
90 }
91 
92 /*
93  * Our own version of log2().  Same thing as highbit()-1.
94  */
95 static int
96 zfs_log2(uint64_t num)
97 {
98 	int i = 0;
99 
100 	while (num > 1) {
101 		i++;
102 		num = num >> 1;
103 	}
104 
105 	return (i);
106 }
107 
108 /* Checksum Functions */
109 static void
110 zio_checksum_off(const void *buf, uint64_t size, zio_cksum_t *zcp)
111 {
112 	ZIO_SET_CHECKSUM(zcp, 0, 0, 0, 0);
113 }
114 
115 /* Checksum Table and Values */
116 zio_checksum_info_t zio_checksum_table[ZIO_CHECKSUM_FUNCTIONS] = {
117 	NULL,			NULL,			0, 0,	"inherit",
118 	NULL,			NULL,			0, 0,	"on",
119 	zio_checksum_off,	zio_checksum_off,	0, 0,	"off",
120 	zio_checksum_SHA256,	zio_checksum_SHA256,	1, 1,	"label",
121 	zio_checksum_SHA256,	zio_checksum_SHA256,	1, 1,	"gang_header",
122 	fletcher_2_native,	fletcher_2_byteswap,	0, 1,	"zilog",
123 	fletcher_2_native,	fletcher_2_byteswap,	0, 0,	"fletcher2",
124 	fletcher_4_native,	fletcher_4_byteswap,	1, 0,	"fletcher4",
125 	zio_checksum_SHA256,	zio_checksum_SHA256,	1, 0,	"SHA256",
126 };
127 
128 /*
129  * zio_checksum_verify: Provides support for checksum verification.
130  *
131  * Fletcher2, Fletcher4, and SHA256 are supported.
132  *
133  * Return:
134  * 	-1 = Failure
135  *	 0 = Success
136  */
137 static int
138 zio_checksum_verify(blkptr_t *bp, char *data, int size)
139 {
140 	zio_cksum_t zc = bp->blk_cksum;
141 	uint32_t checksum = BP_IS_GANG(bp) ? ZIO_CHECKSUM_GANG_HEADER :
142 	    BP_GET_CHECKSUM(bp);
143 	int byteswap = BP_SHOULD_BYTESWAP(bp);
144 	zio_block_tail_t *zbt = (zio_block_tail_t *)(data + size) - 1;
145 	zio_checksum_info_t *ci = &zio_checksum_table[checksum];
146 	zio_cksum_t actual_cksum, expected_cksum;
147 
148 	/* byteswap is not supported */
149 	if (byteswap)
150 		return (-1);
151 
152 	if (checksum >= ZIO_CHECKSUM_FUNCTIONS || ci->ci_func[0] == NULL)
153 		return (-1);
154 
155 	if (ci->ci_zbt) {
156 		if (checksum == ZIO_CHECKSUM_GANG_HEADER) {
157 			/*
158 			 * 'gang blocks' is not supported.
159 			 */
160 			return (-1);
161 		}
162 
163 		if (zbt->zbt_magic == BSWAP_64(ZBT_MAGIC)) {
164 			/* byte swapping is not supported */
165 			return (-1);
166 		} else {
167 			expected_cksum = zbt->zbt_cksum;
168 			zbt->zbt_cksum = zc;
169 			ci->ci_func[0](data, size, &actual_cksum);
170 			zbt->zbt_cksum = expected_cksum;
171 		}
172 		zc = expected_cksum;
173 
174 	} else {
175 		if (BP_IS_GANG(bp))
176 			return (-1);
177 		ci->ci_func[byteswap](data, size, &actual_cksum);
178 	}
179 
180 	if ((actual_cksum.zc_word[0] - zc.zc_word[0]) |
181 	    (actual_cksum.zc_word[1] - zc.zc_word[1]) |
182 	    (actual_cksum.zc_word[2] - zc.zc_word[2]) |
183 	    (actual_cksum.zc_word[3] - zc.zc_word[3]))
184 		return (-1);
185 
186 	return (0);
187 }
188 
189 /*
190  * vdev_label_offset takes "offset" (the offset within a vdev_label) and
191  * returns its physical disk offset (starting from the beginning of the vdev).
192  *
193  * Input:
194  *	psize	: Physical size of this vdev
195  *      l	: Label Number (0-3)
196  *	offset	: The offset with a vdev_label in which we want the physical
197  *		  address
198  * Return:
199  * 	Success : physical disk offset
200  * 	Failure : errnum = ERR_BAD_ARGUMENT, return value is meaningless
201  */
202 uint64_t
203 vdev_label_offset(uint64_t psize, int l, uint64_t offset)
204 {
205 	/* XXX Need to add back label support! */
206 	if (l >= VDEV_LABELS/2 || offset > sizeof (vdev_label_t)) {
207 		errnum = ERR_BAD_ARGUMENT;
208 		return (0);
209 	}
210 
211 	return (offset + l * sizeof (vdev_label_t) + (l < VDEV_LABELS / 2 ?
212 	    0 : psize - VDEV_LABELS * sizeof (vdev_label_t)));
213 
214 }
215 
216 /*
217  * vdev_uberblock_compare takes two uberblock structures and returns an integer
218  * indicating the more recent of the two.
219  * 	Return Value = 1 if ub2 is more recent
220  * 	Return Value = -1 if ub1 is more recent
221  * The most recent uberblock is determined using its transaction number and
222  * timestamp.  The uberblock with the highest transaction number is
223  * considered "newer".  If the transaction numbers of the two blocks match, the
224  * timestamps are compared to determine the "newer" of the two.
225  */
226 static int
227 vdev_uberblock_compare(uberblock_t *ub1, uberblock_t *ub2)
228 {
229 	if (ub1->ub_txg < ub2->ub_txg)
230 		return (-1);
231 	if (ub1->ub_txg > ub2->ub_txg)
232 		return (1);
233 
234 	if (ub1->ub_timestamp < ub2->ub_timestamp)
235 		return (-1);
236 	if (ub1->ub_timestamp > ub2->ub_timestamp)
237 		return (1);
238 
239 	return (0);
240 }
241 
242 /*
243  * Three pieces of information are needed to verify an uberblock: the magic
244  * number, the version number, and the checksum.
245  *
246  * Currently Implemented: version number, magic number
247  * Need to Implement: checksum
248  *
249  * Return:
250  *     0 - Success
251  *    -1 - Failure
252  */
253 static int
254 uberblock_verify(uberblock_phys_t *ub, int offset)
255 {
256 
257 	uberblock_t *uber = &ub->ubp_uberblock;
258 	blkptr_t bp;
259 
260 	BP_ZERO(&bp);
261 	BP_SET_CHECKSUM(&bp, ZIO_CHECKSUM_LABEL);
262 	BP_SET_BYTEORDER(&bp, ZFS_HOST_BYTEORDER);
263 	ZIO_SET_CHECKSUM(&bp.blk_cksum, offset, 0, 0, 0);
264 
265 	if (zio_checksum_verify(&bp, (char *)ub, UBERBLOCK_SIZE) != 0)
266 		return (-1);
267 
268 	if (uber->ub_magic == UBERBLOCK_MAGIC &&
269 	    uber->ub_version >= SPA_VERSION_1 &&
270 	    uber->ub_version <= SPA_VERSION)
271 		return (0);
272 
273 	return (-1);
274 }
275 
276 /*
277  * Find the best uberblock.
278  * Return:
279  *    Success - Pointer to the best uberblock.
280  *    Failure - NULL
281  */
282 static uberblock_phys_t *
283 find_bestub(uberblock_phys_t *ub_array, int label)
284 {
285 	uberblock_phys_t *ubbest = NULL;
286 	int i, offset;
287 
288 	for (i = 0; i < (VDEV_UBERBLOCK_RING >> VDEV_UBERBLOCK_SHIFT); i++) {
289 		offset = vdev_label_offset(0, label, VDEV_UBERBLOCK_OFFSET(i));
290 		if (errnum == ERR_BAD_ARGUMENT)
291 			return (NULL);
292 		if (uberblock_verify(&ub_array[i], offset) == 0) {
293 			if (ubbest == NULL) {
294 				ubbest = &ub_array[i];
295 			} else if (vdev_uberblock_compare(
296 			    &(ub_array[i].ubp_uberblock),
297 			    &(ubbest->ubp_uberblock)) > 0) {
298 				ubbest = &ub_array[i];
299 			}
300 		}
301 	}
302 
303 	return (ubbest);
304 }
305 
306 /*
307  * Read in a block and put its uncompressed data in buf.
308  *
309  * Return:
310  *	0 - success
311  *	errnum - failure
312  */
313 static int
314 zio_read(blkptr_t *bp, void *buf, char *stack)
315 {
316 	uint64_t offset, sector;
317 	int psize, lsize;
318 	int i, comp, cksum;
319 
320 	psize = BP_GET_PSIZE(bp);
321 	lsize = BP_GET_LSIZE(bp);
322 	comp = BP_GET_COMPRESS(bp);
323 	cksum = BP_GET_CHECKSUM(bp);
324 
325 	if ((unsigned int)comp >= ZIO_COMPRESS_FUNCTIONS ||
326 	    comp != ZIO_COMPRESS_OFF && decomp_table[comp].decomp_func == NULL)
327 		return (ERR_FSYS_CORRUPT);
328 
329 	/* pick a good dva from the block pointer */
330 	for (i = 0; i < SPA_DVAS_PER_BP; i++) {
331 
332 		if (bp->blk_dva[i].dva_word[0] == 0 &&
333 		    bp->blk_dva[i].dva_word[1] == 0)
334 			continue;
335 
336 		/* read in a block */
337 		offset = DVA_GET_OFFSET(&bp->blk_dva[i]);
338 		sector =  DVA_OFFSET_TO_PHYS_SECTOR(offset);
339 
340 		if (comp != ZIO_COMPRESS_OFF) {
341 
342 			if (devread(sector, 0, psize, stack) == 0)
343 				continue;
344 			if (zio_checksum_verify(bp, stack, psize) != 0)
345 				continue;
346 			decomp_table[comp].decomp_func(stack, buf, psize,
347 			    lsize);
348 		} else {
349 			if (devread(sector, 0, psize, buf) == 0)
350 				continue;
351 			if (zio_checksum_verify(bp, buf, psize) != 0)
352 				continue;
353 		}
354 		return (0);
355 	}
356 
357 	return (ERR_FSYS_CORRUPT);
358 }
359 
360 /*
361  * Get the block from a block id.
362  * push the block onto the stack.
363  *
364  * Return:
365  * 	0 - success
366  * 	errnum - failure
367  */
368 static int
369 dmu_read(dnode_phys_t *dn, uint64_t blkid, void *buf, char *stack)
370 {
371 	int idx, level;
372 	blkptr_t *bp_array = dn->dn_blkptr;
373 	int epbs = dn->dn_indblkshift - SPA_BLKPTRSHIFT;
374 	blkptr_t *bp, *tmpbuf;
375 
376 	bp = (blkptr_t *)stack;
377 	stack += sizeof (blkptr_t);
378 
379 	tmpbuf = (blkptr_t *)stack;
380 	stack += 1<<dn->dn_indblkshift;
381 
382 	for (level = dn->dn_nlevels - 1; level >= 0; level--) {
383 		idx = (blkid >> (epbs * level)) & ((1<<epbs)-1);
384 		*bp = bp_array[idx];
385 		if (level == 0)
386 			tmpbuf = buf;
387 		if (BP_IS_HOLE(bp)) {
388 			grub_memset(buf, 0,
389 			    dn->dn_datablkszsec << SPA_MINBLOCKSHIFT);
390 			break;
391 		} else if (errnum = zio_read(bp, tmpbuf, stack)) {
392 			return (errnum);
393 		}
394 
395 		bp_array = tmpbuf;
396 	}
397 
398 	return (0);
399 }
400 
401 /*
402  * mzap_lookup: Looks up property described by "name" and returns the value
403  * in "value".
404  *
405  * Return:
406  *	0 - success
407  *	errnum - failure
408  */
409 static int
410 mzap_lookup(mzap_phys_t *zapobj, int objsize, char *name,
411 	uint64_t *value)
412 {
413 	int i, chunks;
414 	mzap_ent_phys_t *mzap_ent = zapobj->mz_chunk;
415 
416 	chunks = objsize/MZAP_ENT_LEN - 1;
417 	for (i = 0; i < chunks; i++) {
418 		if (grub_strcmp(mzap_ent[i].mze_name, name) == 0) {
419 			*value = mzap_ent[i].mze_value;
420 			return (0);
421 		}
422 	}
423 
424 	return (ERR_FSYS_CORRUPT);
425 }
426 
427 static uint64_t
428 zap_hash(uint64_t salt, const char *name)
429 {
430 	static uint64_t table[256];
431 	const uint8_t *cp;
432 	uint8_t c;
433 	uint64_t crc = salt;
434 
435 	if (table[128] == 0) {
436 		uint64_t *ct;
437 		int i, j;
438 		for (i = 0; i < 256; i++) {
439 			for (ct = table + i, *ct = i, j = 8; j > 0; j--)
440 				*ct = (*ct >> 1) ^ (-(*ct & 1) &
441 				    ZFS_CRC64_POLY);
442 		}
443 	}
444 
445 	if (crc == 0 || table[128] != ZFS_CRC64_POLY) {
446 		errnum = ERR_FSYS_CORRUPT;
447 		return (0);
448 	}
449 
450 	for (cp = (const uint8_t *)name; (c = *cp) != '\0'; cp++)
451 		crc = (crc >> 8) ^ table[(crc ^ c) & 0xFF];
452 
453 	/*
454 	 * Only use 28 bits, since we need 4 bits in the cookie for the
455 	 * collision differentiator.  We MUST use the high bits, since
456 	 * those are the onces that we first pay attention to when
457 	 * chosing the bucket.
458 	 */
459 	crc &= ~((1ULL << (64 - ZAP_HASHBITS)) - 1);
460 
461 	return (crc);
462 }
463 
464 /*
465  * Only to be used on 8-bit arrays.
466  * array_len is actual len in bytes (not encoded le_value_length).
467  * buf is null-terminated.
468  */
469 static int
470 zap_leaf_array_equal(zap_leaf_phys_t *l, int blksft, int chunk,
471     int array_len, const char *buf)
472 {
473 	int bseen = 0;
474 
475 	while (bseen < array_len) {
476 		struct zap_leaf_array *la =
477 		    &ZAP_LEAF_CHUNK(l, blksft, chunk).l_array;
478 		int toread = MIN(array_len - bseen, ZAP_LEAF_ARRAY_BYTES);
479 
480 		if (chunk >= ZAP_LEAF_NUMCHUNKS(blksft))
481 			return (0);
482 
483 		if (zfs_bcmp(la->la_array, buf + bseen, toread) != 0)
484 			break;
485 		chunk = la->la_next;
486 		bseen += toread;
487 	}
488 	return (bseen == array_len);
489 }
490 
491 /*
492  * Given a zap_leaf_phys_t, walk thru the zap leaf chunks to get the
493  * value for the property "name".
494  *
495  * Return:
496  *	0 - success
497  *	errnum - failure
498  */
499 int
500 zap_leaf_lookup(zap_leaf_phys_t *l, int blksft, uint64_t h,
501     const char *name, uint64_t *value)
502 {
503 	uint16_t chunk;
504 	struct zap_leaf_entry *le;
505 
506 	/* Verify if this is a valid leaf block */
507 	if (l->l_hdr.lh_block_type != ZBT_LEAF)
508 		return (ERR_FSYS_CORRUPT);
509 	if (l->l_hdr.lh_magic != ZAP_LEAF_MAGIC)
510 		return (ERR_FSYS_CORRUPT);
511 
512 	for (chunk = l->l_hash[LEAF_HASH(blksft, h)];
513 	    chunk != CHAIN_END; chunk = le->le_next) {
514 
515 		if (chunk >= ZAP_LEAF_NUMCHUNKS(blksft))
516 			return (ERR_FSYS_CORRUPT);
517 
518 		le = ZAP_LEAF_ENTRY(l, blksft, chunk);
519 
520 		/* Verify the chunk entry */
521 		if (le->le_type != ZAP_CHUNK_ENTRY)
522 			return (ERR_FSYS_CORRUPT);
523 
524 		if (le->le_hash != h)
525 			continue;
526 
527 		if (zap_leaf_array_equal(l, blksft, le->le_name_chunk,
528 		    le->le_name_length, name)) {
529 
530 			struct zap_leaf_array *la;
531 			uint8_t *ip;
532 
533 			if (le->le_int_size != 8 || le->le_value_length != 1)
534 				return (ERR_FSYS_CORRUPT);
535 
536 			/* get the uint64_t property value */
537 			la = &ZAP_LEAF_CHUNK(l, blksft,
538 			    le->le_value_chunk).l_array;
539 			ip = la->la_array;
540 
541 			*value = (uint64_t)ip[0] << 56 | (uint64_t)ip[1] << 48 |
542 			    (uint64_t)ip[2] << 40 | (uint64_t)ip[3] << 32 |
543 			    (uint64_t)ip[4] << 24 | (uint64_t)ip[5] << 16 |
544 			    (uint64_t)ip[6] << 8 | (uint64_t)ip[7];
545 
546 			return (0);
547 		}
548 	}
549 
550 	return (ERR_FSYS_CORRUPT);
551 }
552 
553 /*
554  * Fat ZAP lookup
555  *
556  * Return:
557  *	0 - success
558  *	errnum - failure
559  */
560 int
561 fzap_lookup(dnode_phys_t *zap_dnode, zap_phys_t *zap,
562     char *name, uint64_t *value, char *stack)
563 {
564 	zap_leaf_phys_t *l;
565 	uint64_t hash, idx, blkid;
566 	int blksft = zfs_log2(zap_dnode->dn_datablkszsec << DNODE_SHIFT);
567 
568 	/* Verify if this is a fat zap header block */
569 	if (zap->zap_magic != (uint64_t)ZAP_MAGIC)
570 		return (ERR_FSYS_CORRUPT);
571 
572 	hash = zap_hash(zap->zap_salt, name);
573 	if (errnum)
574 		return (errnum);
575 
576 	/* get block id from index */
577 	if (zap->zap_ptrtbl.zt_numblks != 0) {
578 		/* external pointer tables not supported */
579 		return (ERR_FSYS_CORRUPT);
580 	}
581 	idx = ZAP_HASH_IDX(hash, zap->zap_ptrtbl.zt_shift);
582 	blkid = ((uint64_t *)zap)[idx + (1<<(blksft-3-1))];
583 
584 	/* Get the leaf block */
585 	l = (zap_leaf_phys_t *)stack;
586 	stack += 1<<blksft;
587 	if (errnum = dmu_read(zap_dnode, blkid, l, stack))
588 		return (errnum);
589 
590 	return (zap_leaf_lookup(l, blksft, hash, name, value));
591 }
592 
593 /*
594  * Read in the data of a zap object and find the value for a matching
595  * property name.
596  *
597  * Return:
598  *	0 - success
599  *	errnum - failure
600  */
601 static int
602 zap_lookup(dnode_phys_t *zap_dnode, char *name, uint64_t *val, char *stack)
603 {
604 	uint64_t block_type;
605 	int size;
606 	void *zapbuf;
607 
608 	/* Read in the first block of the zap object data. */
609 	zapbuf = stack;
610 	size = zap_dnode->dn_datablkszsec << SPA_MINBLOCKSHIFT;
611 	stack += size;
612 	if (errnum = dmu_read(zap_dnode, 0, zapbuf, stack))
613 		return (errnum);
614 
615 	block_type = *((uint64_t *)zapbuf);
616 
617 	if (block_type == ZBT_MICRO) {
618 		return (mzap_lookup(zapbuf, size, name, val));
619 	} else if (block_type == ZBT_HEADER) {
620 		/* this is a fat zap */
621 		return (fzap_lookup(zap_dnode, zapbuf, name,
622 		    val, stack));
623 	}
624 
625 	return (ERR_FSYS_CORRUPT);
626 }
627 
628 /*
629  * Get the dnode of an object number from the metadnode of an object set.
630  *
631  * Input
632  *	mdn - metadnode to get the object dnode
633  *	objnum - object number for the object dnode
634  *	buf - data buffer that holds the returning dnode
635  *	stack - scratch area
636  *
637  * Return:
638  *	0 - success
639  *	errnum - failure
640  */
641 static int
642 dnode_get(dnode_phys_t *mdn, uint64_t objnum, uint8_t type, dnode_phys_t *buf,
643 	char *stack)
644 {
645 	uint64_t blkid, blksz; /* the block id this object dnode is in */
646 	int epbs; /* shift of number of dnodes in a block */
647 	int idx; /* index within a block */
648 	dnode_phys_t *dnbuf;
649 
650 	blksz = mdn->dn_datablkszsec << SPA_MINBLOCKSHIFT;
651 	epbs = zfs_log2(blksz) - DNODE_SHIFT;
652 	blkid = objnum >> epbs;
653 	idx = objnum & ((1<<epbs)-1);
654 
655 	if (dnode_buf != NULL && dnode_mdn == mdn &&
656 	    objnum >= dnode_start && objnum < dnode_end) {
657 		grub_memmove(buf, &dnode_buf[idx], DNODE_SIZE);
658 		VERIFY_DN_TYPE(buf, type);
659 		return (0);
660 	}
661 
662 	if (dnode_buf && blksz == 1<<DNODE_BLOCK_SHIFT) {
663 		dnbuf = dnode_buf;
664 		dnode_mdn = mdn;
665 		dnode_start = blkid << epbs;
666 		dnode_end = (blkid + 1) << epbs;
667 	} else {
668 		dnbuf = (dnode_phys_t *)stack;
669 		stack += blksz;
670 	}
671 
672 	if (errnum = dmu_read(mdn, blkid, (char *)dnbuf, stack))
673 		return (errnum);
674 
675 	grub_memmove(buf, &dnbuf[idx], DNODE_SIZE);
676 	VERIFY_DN_TYPE(buf, type);
677 
678 	return (0);
679 }
680 
681 /*
682  * Check if this is the "menu.lst" file.
683  * str starts with '/'.
684  */
685 static int
686 is_menu_lst(char *str)
687 {
688 	char *tptr;
689 
690 	if ((tptr = grub_strstr(str, "menu.lst")) &&
691 	    (tptr[8] == '\0' || tptr[8] == ' ') &&
692 	    *(tptr-1) == '/')
693 		return (1);
694 
695 	return (0);
696 }
697 
698 /*
699  * Get the file dnode for a given file name where mdn is the meta dnode
700  * for this ZFS object set. When found, place the file dnode in dn.
701  * The 'path' argument will be mangled.
702  *
703  * Return:
704  *	0 - success
705  *	errnum - failure
706  */
707 static int
708 dnode_get_path(dnode_phys_t *mdn, char *path, dnode_phys_t *dn,
709     char *stack)
710 {
711 	uint64_t objnum, version;
712 	char *cname, ch;
713 
714 	if (errnum = dnode_get(mdn, MASTER_NODE_OBJ, DMU_OT_MASTER_NODE,
715 	    dn, stack))
716 		return (errnum);
717 
718 	if (errnum = zap_lookup(dn, ZPL_VERSION_STR, &version, stack))
719 		return (errnum);
720 	if (version > ZPL_VERSION)
721 		return (-1);
722 
723 	if (errnum = zap_lookup(dn, ZFS_ROOT_OBJ, &objnum, stack))
724 		return (errnum);
725 
726 	if (errnum = dnode_get(mdn, objnum, DMU_OT_DIRECTORY_CONTENTS,
727 	    dn, stack))
728 		return (errnum);
729 
730 	/* skip leading slashes */
731 	while (*path == '/')
732 		path++;
733 
734 	while (*path && !isspace(*path)) {
735 
736 		/* get the next component name */
737 		cname = path;
738 		while (*path && !isspace(*path) && *path != '/')
739 			path++;
740 		ch = *path;
741 		*path = 0;   /* ensure null termination */
742 
743 		if (errnum = zap_lookup(dn, cname, &objnum, stack))
744 			return (errnum);
745 
746 		objnum = ZFS_DIRENT_OBJ(objnum);
747 		if (errnum = dnode_get(mdn, objnum, 0, dn, stack))
748 			return (errnum);
749 
750 		*path = ch;
751 		while (*path == '/')
752 			path++;
753 	}
754 
755 	/* We found the dnode for this file. Verify if it is a plain file. */
756 	VERIFY_DN_TYPE(dn, DMU_OT_PLAIN_FILE_CONTENTS);
757 
758 	return (0);
759 }
760 
761 /*
762  * Get the default 'bootfs' property value from the rootpool.
763  *
764  * Return:
765  *	0 - success
766  *	errnum -failure
767  */
768 static int
769 get_default_bootfsobj(dnode_phys_t *mosmdn, uint64_t *obj, char *stack)
770 {
771 	uint64_t objnum = 0;
772 	dnode_phys_t *dn = (dnode_phys_t *)stack;
773 	stack += DNODE_SIZE;
774 
775 	if (errnum = dnode_get(mosmdn, DMU_POOL_DIRECTORY_OBJECT,
776 	    DMU_OT_OBJECT_DIRECTORY, dn, stack))
777 		return (errnum);
778 
779 	/*
780 	 * find the object number for 'pool_props', and get the dnode
781 	 * of the 'pool_props'.
782 	 */
783 	if (zap_lookup(dn, DMU_POOL_PROPS, &objnum, stack))
784 		return (ERR_FILESYSTEM_NOT_FOUND);
785 
786 	if (errnum = dnode_get(mosmdn, objnum, DMU_OT_POOL_PROPS, dn, stack))
787 		return (errnum);
788 
789 	if (zap_lookup(dn, ZPOOL_PROP_BOOTFS, &objnum, stack))
790 		return (ERR_FILESYSTEM_NOT_FOUND);
791 
792 	if (!objnum)
793 		return (ERR_FILESYSTEM_NOT_FOUND);
794 
795 	*obj = objnum;
796 	return (0);
797 }
798 
799 /*
800  * Given a MOS metadnode, get the metadnode of a given filesystem name (fsname),
801  * e.g. pool/rootfs, or a given object number (obj), e.g. the object number
802  * of pool/rootfs.
803  *
804  * If no fsname and no obj are given, return the DSL_DIR metadnode.
805  * If fsname is given, return its metadnode and its matching object number.
806  * If only obj is given, return the metadnode for this object number.
807  *
808  * Return:
809  *	0 - success
810  *	errnum - failure
811  */
812 static int
813 get_objset_mdn(dnode_phys_t *mosmdn, char *fsname, uint64_t *obj,
814     dnode_phys_t *mdn, char *stack)
815 {
816 	uint64_t objnum, headobj;
817 	char *cname, ch;
818 	blkptr_t *bp;
819 	objset_phys_t *osp;
820 
821 	if (fsname == NULL && obj) {
822 		headobj = *obj;
823 		goto skip;
824 	}
825 
826 	if (errnum = dnode_get(mosmdn, DMU_POOL_DIRECTORY_OBJECT,
827 	    DMU_OT_OBJECT_DIRECTORY, mdn, stack))
828 		return (errnum);
829 
830 	if (errnum = zap_lookup(mdn, DMU_POOL_ROOT_DATASET, &objnum,
831 	    stack))
832 		return (errnum);
833 
834 	if (errnum = dnode_get(mosmdn, objnum, DMU_OT_DSL_DIR, mdn, stack))
835 		return (errnum);
836 
837 	if (fsname == NULL) {
838 		headobj =
839 		    ((dsl_dir_phys_t *)DN_BONUS(mdn))->dd_head_dataset_obj;
840 		goto skip;
841 	}
842 
843 	/* take out the pool name */
844 	while (*fsname && !isspace(*fsname) && *fsname != '/')
845 		fsname++;
846 
847 	while (*fsname && !isspace(*fsname)) {
848 		uint64_t childobj;
849 
850 		while (*fsname == '/')
851 			fsname++;
852 
853 		cname = fsname;
854 		while (*fsname && !isspace(*fsname) && *fsname != '/')
855 			fsname++;
856 		ch = *fsname;
857 		*fsname = 0;
858 
859 		childobj =
860 		    ((dsl_dir_phys_t *)DN_BONUS(mdn))->dd_child_dir_zapobj;
861 		if (errnum = dnode_get(mosmdn, childobj,
862 		    DMU_OT_DSL_DIR_CHILD_MAP, mdn, stack))
863 			return (errnum);
864 
865 		if (zap_lookup(mdn, cname, &objnum, stack))
866 			return (ERR_FILESYSTEM_NOT_FOUND);
867 
868 		if (errnum = dnode_get(mosmdn, objnum, DMU_OT_DSL_DIR,
869 		    mdn, stack))
870 			return (errnum);
871 
872 		*fsname = ch;
873 	}
874 	headobj = ((dsl_dir_phys_t *)DN_BONUS(mdn))->dd_head_dataset_obj;
875 	if (obj)
876 		*obj = headobj;
877 
878 skip:
879 	if (errnum = dnode_get(mosmdn, headobj, DMU_OT_DSL_DATASET, mdn, stack))
880 		return (errnum);
881 
882 	/* TODO: Add snapshot support here - for fsname=snapshot-name */
883 
884 	bp = &((dsl_dataset_phys_t *)DN_BONUS(mdn))->ds_bp;
885 	osp = (objset_phys_t *)stack;
886 	stack += sizeof (objset_phys_t);
887 	if (errnum = zio_read(bp, osp, stack))
888 		return (errnum);
889 
890 	grub_memmove((char *)mdn, (char *)&osp->os_meta_dnode, DNODE_SIZE);
891 
892 	return (0);
893 }
894 
895 /*
896  * Parse the packed nvlist and search for the string value of a given name.
897  *
898  * An XDR packed nvlist is encoded as (from nvs_xdr_create) :
899  *
900  *      encoding method/host endian     (4 bytes)
901  *      nvl_version                     (4 bytes)
902  *      nvl_nvflag                      (4 bytes)
903  *	encoded nvpairs:
904  *		encoded size of the nvpair      (4 bytes)
905  *		decoded size of the nvpair      (4 bytes)
906  *		name string size                (4 bytes)
907  *		name string data                (sizeof(NV_ALIGN4(string))
908  *		data type                       (4 bytes)
909  *		# of elements in the nvpair     (4 bytes)
910  *		data
911  *      2 zero's for the last nvpair
912  *		(end of the entire list)	(8 bytes)
913  *
914  * Return:
915  *	0 - success
916  *	1 - failure
917  */
918 int
919 nvlist_lookup_value(char *nvlist, char *name, void *val, int valtype)
920 {
921 	int name_len, type, nelm, slen, encode_size;
922 	char *nvpair, *nvp_name, *strval = val;
923 	uint64_t *intval = val;
924 
925 	/* Verify if the 1st and 2nd byte in the nvlist are valid. */
926 	if (nvlist[0] != NV_ENCODE_XDR || nvlist[1] != HOST_ENDIAN)
927 		return (1);
928 
929 	/* skip the header, nvl_version, and nvl_nvflag */
930 	nvlist = nvlist + 4 * 3;
931 
932 	/*
933 	 * Loop thru the nvpair list
934 	 * The XDR representation of an integer is in big-endian byte order.
935 	 */
936 	while (encode_size = BSWAP_32(*(uint32_t *)nvlist))  {
937 
938 		nvpair = nvlist + 4 * 2; /* skip the encode/decode size */
939 
940 		name_len = BSWAP_32(*(uint32_t *)nvpair);
941 		nvpair += 4;
942 
943 		nvp_name = nvpair;
944 		nvpair = nvpair + ((name_len + 3) & ~3); /* align */
945 
946 		type = BSWAP_32(*(uint32_t *)nvpair);
947 		nvpair += 4;
948 
949 		if ((grub_strncmp(nvp_name, name, name_len) == 0) &&
950 		    type == valtype) {
951 
952 			if ((nelm = BSWAP_32(*(uint32_t *)nvpair)) != 1)
953 				return (1);
954 			nvpair += 4;
955 
956 			switch (valtype) {
957 			case DATA_TYPE_STRING:
958 				slen = BSWAP_32(*(uint32_t *)nvpair);
959 				nvpair += 4;
960 				grub_memmove(strval, nvpair, slen);
961 				strval[slen] = '\0';
962 				return (0);
963 
964 			case DATA_TYPE_UINT64:
965 				*intval = BSWAP_64(*(uint64_t *)nvpair);
966 				return (0);
967 			}
968 		}
969 
970 		nvlist += encode_size; /* goto the next nvpair */
971 	}
972 
973 	return (1);
974 }
975 
976 /*
977  * Get the pool name of the root pool from the vdev nvpair list of the label.
978  *
979  * Return:
980  *	0 - success
981  *	errnum - failure
982  */
983 int
984 get_pool_name_value(int label, char *name, void *value, int valtype,
985     char *stack)
986 {
987 	vdev_phys_t *vdev;
988 	uint64_t sector;
989 
990 	sector = (label * sizeof (vdev_label_t) + VDEV_SKIP_SIZE +
991 	    VDEV_BOOT_HEADER_SIZE) >> SPA_MINBLOCKSHIFT;
992 
993 	/* Read in the vdev name-value pair list (112K). */
994 	if (devread(sector, 0, VDEV_PHYS_SIZE, stack) == 0)
995 		return (ERR_READ);
996 
997 	vdev = (vdev_phys_t *)stack;
998 
999 	if (nvlist_lookup_value(vdev->vp_nvlist, name, value, valtype))
1000 		return (ERR_FSYS_CORRUPT);
1001 	else
1002 		return (0);
1003 }
1004 
1005 /*
1006  * zfs_mount() locates a valid uberblock of the root pool and read in its MOS
1007  * to the memory address MOS.
1008  *
1009  * Return:
1010  *	1 - success
1011  *	0 - failure
1012  */
1013 int
1014 zfs_mount(void)
1015 {
1016 	char *stack;
1017 	int label = 0;
1018 	uberblock_phys_t *ub_array, *ubbest = NULL;
1019 	objset_phys_t *osp;
1020 
1021 	/* if zfs is already mounted, don't do it again */
1022 	if (is_zfs_mount == 1)
1023 		return (1);
1024 
1025 	stackbase = ZFS_SCRATCH;
1026 	stack = stackbase;
1027 	ub_array = (uberblock_phys_t *)stack;
1028 	stack += VDEV_UBERBLOCK_RING;
1029 
1030 	osp = (objset_phys_t *)stack;
1031 	stack += sizeof (objset_phys_t);
1032 
1033 	/* XXX add back labels support? */
1034 	for (label = 0; ubbest == NULL && label < (VDEV_LABELS/2); label++) {
1035 		uint64_t sector = (label * sizeof (vdev_label_t) +
1036 		    VDEV_SKIP_SIZE + VDEV_BOOT_HEADER_SIZE +
1037 		    VDEV_PHYS_SIZE) >> SPA_MINBLOCKSHIFT;
1038 
1039 		/* Read in the uberblock ring (128K). */
1040 		if (devread(sector, 0, VDEV_UBERBLOCK_RING,
1041 		    (char *)ub_array) == 0)
1042 			continue;
1043 
1044 		if ((ubbest = find_bestub(ub_array, label)) != NULL &&
1045 		    zio_read(&ubbest->ubp_uberblock.ub_rootbp, osp, stack)
1046 		    == 0) {
1047 			uint64_t pool_state;
1048 
1049 			VERIFY_OS_TYPE(osp, DMU_OST_META);
1050 
1051 			/* Got the MOS. Save it at the memory addr MOS. */
1052 			grub_memmove(MOS, &osp->os_meta_dnode, DNODE_SIZE);
1053 
1054 			if (get_pool_name_value(label, ZPOOL_CONFIG_POOL_STATE,
1055 			    &pool_state, DATA_TYPE_UINT64, stack))
1056 				return (0);
1057 
1058 			if (pool_state == POOL_STATE_DESTROYED)
1059 				return (0);
1060 
1061 			if (get_pool_name_value(label, ZPOOL_CONFIG_POOL_NAME,
1062 			    current_rootpool, DATA_TYPE_STRING, stack))
1063 				return (0);
1064 
1065 			is_zfs_mount = 1;
1066 			return (1);
1067 		}
1068 	}
1069 
1070 	return (0);
1071 }
1072 
1073 /*
1074  * zfs_open() locates a file in the rootpool by following the
1075  * MOS and places the dnode of the file in the memory address DNODE.
1076  *
1077  * Return:
1078  *	1 - success
1079  *	0 - failure
1080  */
1081 int
1082 zfs_open(char *filename)
1083 {
1084 	char *stack;
1085 	dnode_phys_t *mdn;
1086 
1087 	file_buf = NULL;
1088 	stackbase = ZFS_SCRATCH;
1089 	stack = stackbase;
1090 
1091 	mdn = (dnode_phys_t *)stack;
1092 	stack += sizeof (dnode_phys_t);
1093 
1094 	dnode_mdn = NULL;
1095 	dnode_buf = (dnode_phys_t *)stack;
1096 	stack += 1<<DNODE_BLOCK_SHIFT;
1097 
1098 	/*
1099 	 * menu.lst is placed at the root pool filesystem level,
1100 	 * do not goto 'current_bootfs'.
1101 	 */
1102 	if (is_menu_lst(filename)) {
1103 		if (errnum = get_objset_mdn(MOS, NULL, NULL, mdn, stack))
1104 			return (0);
1105 
1106 		current_bootfs_obj = 0;
1107 	} else {
1108 		if (current_bootfs[0] == '\0') {
1109 			/* Get the default root filesystem object number */
1110 			if (errnum = get_default_bootfsobj(MOS,
1111 			    &current_bootfs_obj, stack))
1112 				return (0);
1113 
1114 			if (errnum = get_objset_mdn(MOS, NULL,
1115 			    &current_bootfs_obj, mdn, stack))
1116 				return (0);
1117 		} else {
1118 			if (errnum = get_objset_mdn(MOS,
1119 			    current_bootfs, &current_bootfs_obj, mdn, stack))
1120 				return (0);
1121 		}
1122 	}
1123 
1124 	if (dnode_get_path(mdn, filename, DNODE, stack)) {
1125 		errnum = ERR_FILE_NOT_FOUND;
1126 		return (0);
1127 	}
1128 
1129 	/* get the file size and set the file position to 0 */
1130 	filemax = ((znode_phys_t *)DN_BONUS(DNODE))->zp_size;
1131 	filepos = 0;
1132 
1133 	dnode_buf = NULL;
1134 	return (1);
1135 }
1136 
1137 /*
1138  * zfs_read reads in the data blocks pointed by the DNODE.
1139  *
1140  * Return:
1141  *	len - the length successfully read in to the buffer
1142  *	0   - failure
1143  */
1144 int
1145 zfs_read(char *buf, int len)
1146 {
1147 	char *stack;
1148 	char *tmpbuf;
1149 	int blksz, length, movesize;
1150 
1151 	if (file_buf == NULL) {
1152 		file_buf = stackbase;
1153 		stackbase += SPA_MAXBLOCKSIZE;
1154 		file_start = file_end = 0;
1155 	}
1156 	stack = stackbase;
1157 
1158 	/*
1159 	 * If offset is in memory, move it into the buffer provided and return.
1160 	 */
1161 	if (filepos >= file_start && filepos+len <= file_end) {
1162 		grub_memmove(buf, file_buf + filepos - file_start, len);
1163 		filepos += len;
1164 		return (len);
1165 	}
1166 
1167 	blksz = DNODE->dn_datablkszsec << SPA_MINBLOCKSHIFT;
1168 
1169 	/*
1170 	 * Entire Dnode is too big to fit into the space available.  We
1171 	 * will need to read it in chunks.  This could be optimized to
1172 	 * read in as large a chunk as there is space available, but for
1173 	 * now, this only reads in one data block at a time.
1174 	 */
1175 	length = len;
1176 	while (length) {
1177 		/*
1178 		 * Find requested blkid and the offset within that block.
1179 		 */
1180 		uint64_t blkid = filepos / blksz;
1181 
1182 		if (errnum = dmu_read(DNODE, blkid, file_buf, stack))
1183 			return (0);
1184 
1185 		file_start = blkid * blksz;
1186 		file_end = file_start + blksz;
1187 
1188 		movesize = MIN(length, file_end - filepos);
1189 
1190 		grub_memmove(buf, file_buf + filepos - file_start,
1191 		    movesize);
1192 		buf += movesize;
1193 		length -= movesize;
1194 		filepos += movesize;
1195 	}
1196 
1197 	return (len);
1198 }
1199 
1200 /*
1201  * No-Op
1202  */
1203 int
1204 zfs_embed(int *start_sector, int needed_sectors)
1205 {
1206 	return (1);
1207 }
1208 
1209 #endif /* FSYS_ZFS */
1210