stand/libsa/zfs/zfsimpl.c

   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 }