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