module/zfs/zap.c

   1 /*
   2  * CDDL HEADER START
   3  *
   4  * The contents of this file are subject to the terms of the
   5  * Common Development and Distribution License (the "License").
   6  * You may not use this file except in compliance with the License.
   7  *
   8  * You can obtain a copy of the license at usr/src/OPENSOLARIS.LICENSE
   9  * or http://www.opensolaris.org/os/licensing.
  10  * See the License for the specific language governing permissions
  11  * and limitations under the License.
  12  *
  13  * When distributing Covered Code, include this CDDL HEADER in each
  14  * file and include the License file at usr/src/OPENSOLARIS.LICENSE.
  15  * If applicable, add the following below this CDDL HEADER, with the
  16  * fields enclosed by brackets "[]" replaced with your own identifying
  17  * information: Portions Copyright [yyyy] [name of copyright owner]
  18  *
  19  * CDDL HEADER END
  20  */
  21 /*
  22  * Copyright 2009 Sun Microsystems, Inc.  All rights reserved.
  23  * Use is subject to license terms.
  24  */
  25
  26 /*
  27  * This file contains the top half of the zfs directory structure
  28  * implementation. The bottom half is in zap_leaf.c.
  29  *
  30  * The zdir is an extendable hash data structure. There is a table of
  31  * pointers to buckets (zap_t->zd_data->zd_leafs). The buckets are
  32  * each a constant size and hold a variable number of directory entries.
  33  * The buckets (aka "leaf nodes") are implemented in zap_leaf.c.
  34  *
  35  * The pointer table holds a power of 2 number of pointers.
  36  * (1<<zap_t->zd_data->zd_phys->zd_prefix_len).  The bucket pointed to
  37  * by the pointer at index i in the table holds entries whose hash value
  38  * has a zd_prefix_len - bit prefix
  39  */
  40
  41 #include <sys/spa.h>
  42 #include <sys/dmu.h>
  43 #include <sys/zfs_context.h>
  44 #include <sys/zfs_znode.h>
  45 #include <sys/fs/zfs.h>
  46 #include <sys/zap.h>
  47 #include <sys/refcount.h>
  48 #include <sys/zap_impl.h>
  49 #include <sys/zap_leaf.h>
  50
  51 int fzap_default_block_shift = 14; /* 16k blocksize */
  52
  53 static void zap_leaf_pageout(dmu_buf_t *db, void *vl);
  54 static uint64_t zap_allocate_blocks(zap_t *zap, int nblocks);
  55
  56
  57 void
  58 fzap_byteswap(void *vbuf, size_t size)
  59 {
  60         uint64_t block_type;
  61
  62         block_type = *(uint64_t *)vbuf;
  63
  64         if (block_type == ZBT_LEAF || block_type == BSWAP_64(ZBT_LEAF))
  65                 zap_leaf_byteswap(vbuf, size);
  66         else {
  67                 /* it's a ptrtbl block */
  68                 byteswap_uint64_array(vbuf, size);
  69         }
  70 }
  71
  72 void
  73 fzap_upgrade(zap_t *zap, dmu_tx_t *tx)
  74 {
  75         dmu_buf_t *db;
  76         zap_leaf_t *l;
  77         int i;
  78         zap_phys_t *zp;
  79
  80         ASSERT(RW_WRITE_HELD(&zap->zap_rwlock));
  81         zap->zap_ismicro = FALSE;
  82
  83         (void) dmu_buf_update_user(zap->zap_dbuf, zap, zap,
  84             &zap->zap_f.zap_phys, zap_evict);
  85
  86         mutex_init(&zap->zap_f.zap_num_entries_mtx, 0, 0, 0);
  87         zap->zap_f.zap_block_shift = highbit(zap->zap_dbuf->db_size) - 1;
  88
  89         zp = zap->zap_f.zap_phys;
  90         /*
  91          * explicitly zero it since it might be coming from an
  92          * initialized microzap
  93          */
  94         bzero(zap->zap_dbuf->db_data, zap->zap_dbuf->db_size);
  95         zp->zap_block_type = ZBT_HEADER;
  96         zp->zap_magic = ZAP_MAGIC;
  97
  98         zp->zap_ptrtbl.zt_shift = ZAP_EMBEDDED_PTRTBL_SHIFT(zap);
  99
 100         zp->zap_freeblk = 2;            /* block 1 will be the first leaf */
 101         zp->zap_num_leafs = 1;
 102         zp->zap_num_entries = 0;
 103         zp->zap_salt = zap->zap_salt;
 104         zp->zap_normflags = zap->zap_normflags;
 105
 106         /* block 1 will be the first leaf */
 107         for (i = 0; i < (1<<zp->zap_ptrtbl.zt_shift); i++)
 108                 ZAP_EMBEDDED_PTRTBL_ENT(zap, i) = 1;
 109
 110         /*
 111          * set up block 1 - the first leaf
 112          */
 113         VERIFY(0 == dmu_buf_hold(zap->zap_objset, zap->zap_object,
 114             1<<FZAP_BLOCK_SHIFT(zap), FTAG, &db));
 115         dmu_buf_will_dirty(db, tx);
 116
 117         l = kmem_zalloc(sizeof (zap_leaf_t), KM_SLEEP);
 118         l->l_dbuf = db;
 119         l->l_phys = db->db_data;
 120
 121         zap_leaf_init(l, zp->zap_normflags != 0);
 122
 123         kmem_free(l, sizeof (zap_leaf_t));
 124         dmu_buf_rele(db, FTAG);
 125 }
 126
 127 static int
 128 zap_tryupgradedir(zap_t *zap, dmu_tx_t *tx)
 129 {
 130         if (RW_WRITE_HELD(&zap->zap_rwlock))
 131                 return (1);
 132         if (rw_tryupgrade(&zap->zap_rwlock)) {
 133                 dmu_buf_will_dirty(zap->zap_dbuf, tx);
 134                 return (1);
 135         }
 136         return (0);
 137 }
 138
 139 /*
 140  * Generic routines for dealing with the pointer & cookie tables.
 141  */
 142
 143 static int
 144 zap_table_grow(zap_t *zap, zap_table_phys_t *tbl,
 145     void (*transfer_func)(const uint64_t *src, uint64_t *dst, int n),
 146     dmu_tx_t *tx)
 147 {
 148         uint64_t b, newblk;
 149         dmu_buf_t *db_old, *db_new;
 150         int err;
 151         int bs = FZAP_BLOCK_SHIFT(zap);
 152         int hepb = 1<<(bs-4);
 153         /* hepb = half the number of entries in a block */
 154
 155         ASSERT(RW_WRITE_HELD(&zap->zap_rwlock));
 156         ASSERT(tbl->zt_blk != 0);
 157         ASSERT(tbl->zt_numblks > 0);
 158
 159         if (tbl->zt_nextblk != 0) {
 160                 newblk = tbl->zt_nextblk;
 161         } else {
 162                 newblk = zap_allocate_blocks(zap, tbl->zt_numblks * 2);
 163                 tbl->zt_nextblk = newblk;
 164                 ASSERT3U(tbl->zt_blks_copied, ==, 0);
 165                 dmu_prefetch(zap->zap_objset, zap->zap_object,
 166                     tbl->zt_blk << bs, tbl->zt_numblks << bs);
 167         }
 168
 169         /*
 170          * Copy the ptrtbl from the old to new location.
 171          */
 172
 173         b = tbl->zt_blks_copied;
 174         err = dmu_buf_hold(zap->zap_objset, zap->zap_object,
 175             (tbl->zt_blk + b) << bs, FTAG, &db_old);
 176         if (err)
 177                 return (err);
 178
 179         /* first half of entries in old[b] go to new[2*b+0] */
 180         VERIFY(0 == dmu_buf_hold(zap->zap_objset, zap->zap_object,
 181             (newblk + 2*b+0) << bs, FTAG, &db_new));
 182         dmu_buf_will_dirty(db_new, tx);
 183         transfer_func(db_old->db_data, db_new->db_data, hepb);
 184         dmu_buf_rele(db_new, FTAG);
 185
 186         /* second half of entries in old[b] go to new[2*b+1] */
 187         VERIFY(0 == dmu_buf_hold(zap->zap_objset, zap->zap_object,
 188             (newblk + 2*b+1) << bs, FTAG, &db_new));
 189         dmu_buf_will_dirty(db_new, tx);
 190         transfer_func((uint64_t *)db_old->db_data + hepb,
 191             db_new->db_data, hepb);
 192         dmu_buf_rele(db_new, FTAG);
 193
 194         dmu_buf_rele(db_old, FTAG);
 195
 196         tbl->zt_blks_copied++;
 197
 198         dprintf("copied block %llu of %llu\n",
 199             tbl->zt_blks_copied, tbl->zt_numblks);
 200
 201         if (tbl->zt_blks_copied == tbl->zt_numblks) {
 202                 (void) dmu_free_range(zap->zap_objset, zap->zap_object,
 203                     tbl->zt_blk << bs, tbl->zt_numblks << bs, tx);
 204
 205                 tbl->zt_blk = newblk;
 206                 tbl->zt_numblks *= 2;
 207                 tbl->zt_shift++;
 208                 tbl->zt_nextblk = 0;
 209                 tbl->zt_blks_copied = 0;
 210
 211                 dprintf("finished; numblocks now %llu (%lluk entries)\n",
 212                     tbl->zt_numblks, 1<<(tbl->zt_shift-10));
 213         }
 214
 215         return (0);
 216 }
 217
 218 static int
 219 zap_table_store(zap_t *zap, zap_table_phys_t *tbl, uint64_t idx, uint64_t val,
 220     dmu_tx_t *tx)
 221 {
 222         int err;
 223         uint64_t blk, off;
 224         int bs = FZAP_BLOCK_SHIFT(zap);
 225         dmu_buf_t *db;
 226
 227         ASSERT(RW_LOCK_HELD(&zap->zap_rwlock));
 228         ASSERT(tbl->zt_blk != 0);
 229
 230         dprintf("storing %llx at index %llx\n", val, idx);
 231
 232         blk = idx >> (bs-3);
 233         off = idx & ((1<<(bs-3))-1);
 234
 235         err = dmu_buf_hold(zap->zap_objset, zap->zap_object,
 236             (tbl->zt_blk + blk) << bs, FTAG, &db);
 237         if (err)
 238                 return (err);
 239         dmu_buf_will_dirty(db, tx);
 240
 241         if (tbl->zt_nextblk != 0) {
 242                 uint64_t idx2 = idx * 2;
 243                 uint64_t blk2 = idx2 >> (bs-3);
 244                 uint64_t off2 = idx2 & ((1<<(bs-3))-1);
 245                 dmu_buf_t *db2;
 246
 247                 err = dmu_buf_hold(zap->zap_objset, zap->zap_object,
 248                     (tbl->zt_nextblk + blk2) << bs, FTAG, &db2);
 249                 if (err) {
 250                         dmu_buf_rele(db, FTAG);
 251                         return (err);
 252                 }
 253                 dmu_buf_will_dirty(db2, tx);
 254                 ((uint64_t *)db2->db_data)[off2] = val;
 255                 ((uint64_t *)db2->db_data)[off2+1] = val;
 256                 dmu_buf_rele(db2, FTAG);
 257         }
 258
 259         ((uint64_t *)db->db_data)[off] = val;
 260         dmu_buf_rele(db, FTAG);
 261
 262         return (0);
 263 }
 264
 265 static int
 266 zap_table_load(zap_t *zap, zap_table_phys_t *tbl, uint64_t idx, uint64_t *valp)
 267 {
 268         uint64_t blk, off;
 269         int err;
 270         dmu_buf_t *db;
 271         int bs = FZAP_BLOCK_SHIFT(zap);
 272
 273         ASSERT(RW_LOCK_HELD(&zap->zap_rwlock));
 274
 275         blk = idx >> (bs-3);
 276         off = idx & ((1<<(bs-3))-1);
 277
 278         err = dmu_buf_hold(zap->zap_objset, zap->zap_object,
 279             (tbl->zt_blk + blk) << bs, FTAG, &db);
 280         if (err)
 281                 return (err);
 282         *valp = ((uint64_t *)db->db_data)[off];
 283         dmu_buf_rele(db, FTAG);
 284
 285         if (tbl->zt_nextblk != 0) {
 286                 /*
 287                  * read the nextblk for the sake of i/o error checking,
 288                  * so that zap_table_load() will catch errors for
 289                  * zap_table_store.
 290                  */
 291                 blk = (idx*2) >> (bs-3);
 292
 293                 err = dmu_buf_hold(zap->zap_objset, zap->zap_object,
 294                     (tbl->zt_nextblk + blk) << bs, FTAG, &db);
 295                 dmu_buf_rele(db, FTAG);
 296         }
 297         return (err);
 298 }
 299
 300 /*
 301  * Routines for growing the ptrtbl.
 302  */
 303
 304 static void
 305 zap_ptrtbl_transfer(const uint64_t *src, uint64_t *dst, int n)
 306 {
 307         int i;
 308         for (i = 0; i < n; i++) {
 309                 uint64_t lb = src[i];
 310                 dst[2*i+0] = lb;
 311                 dst[2*i+1] = lb;
 312         }
 313 }
 314
 315 static int
 316 zap_grow_ptrtbl(zap_t *zap, dmu_tx_t *tx)
 317 {
 318         /* In case things go horribly wrong. */
 319         if (zap->zap_f.zap_phys->zap_ptrtbl.zt_shift >= ZAP_HASHBITS-2)
 320                 return (ENOSPC);
 321
 322         if (zap->zap_f.zap_phys->zap_ptrtbl.zt_numblks == 0) {
 323                 /*
 324                  * We are outgrowing the "embedded" ptrtbl (the one
 325                  * stored in the header block).  Give it its own entire
 326                  * block, which will double the size of the ptrtbl.
 327                  */
 328                 uint64_t newblk;
 329                 dmu_buf_t *db_new;
 330                 int err;
 331
 332                 ASSERT3U(zap->zap_f.zap_phys->zap_ptrtbl.zt_shift, ==,
 333                     ZAP_EMBEDDED_PTRTBL_SHIFT(zap));
 334                 ASSERT3U(zap->zap_f.zap_phys->zap_ptrtbl.zt_blk, ==, 0);
 335
 336                 newblk = zap_allocate_blocks(zap, 1);
 337                 err = dmu_buf_hold(zap->zap_objset, zap->zap_object,
 338                     newblk << FZAP_BLOCK_SHIFT(zap), FTAG, &db_new);
 339                 if (err)
 340                         return (err);
 341                 dmu_buf_will_dirty(db_new, tx);
 342                 zap_ptrtbl_transfer(&ZAP_EMBEDDED_PTRTBL_ENT(zap, 0),
 343                     db_new->db_data, 1 << ZAP_EMBEDDED_PTRTBL_SHIFT(zap));
 344                 dmu_buf_rele(db_new, FTAG);
 345
 346                 zap->zap_f.zap_phys->zap_ptrtbl.zt_blk = newblk;
 347                 zap->zap_f.zap_phys->zap_ptrtbl.zt_numblks = 1;
 348                 zap->zap_f.zap_phys->zap_ptrtbl.zt_shift++;
 349
 350                 ASSERT3U(1ULL << zap->zap_f.zap_phys->zap_ptrtbl.zt_shift, ==,
 351                     zap->zap_f.zap_phys->zap_ptrtbl.zt_numblks <<
 352                     (FZAP_BLOCK_SHIFT(zap)-3));
 353
 354                 return (0);
 355         } else {
 356                 return (zap_table_grow(zap, &zap->zap_f.zap_phys->zap_ptrtbl,
 357                     zap_ptrtbl_transfer, tx));
 358         }
 359 }
 360
 361 static void
 362 zap_increment_num_entries(zap_t *zap, int delta, dmu_tx_t *tx)
 363 {
 364         dmu_buf_will_dirty(zap->zap_dbuf, tx);
 365         mutex_enter(&zap->zap_f.zap_num_entries_mtx);
 366         ASSERT(delta > 0 || zap->zap_f.zap_phys->zap_num_entries >= -delta);
 367         zap->zap_f.zap_phys->zap_num_entries += delta;
 368         mutex_exit(&zap->zap_f.zap_num_entries_mtx);
 369 }
 370
 371 static uint64_t
 372 zap_allocate_blocks(zap_t *zap, int nblocks)
 373 {
 374         uint64_t newblk;
 375         ASSERT(RW_WRITE_HELD(&zap->zap_rwlock));
 376         newblk = zap->zap_f.zap_phys->zap_freeblk;
 377         zap->zap_f.zap_phys->zap_freeblk += nblocks;
 378         return (newblk);
 379 }
 380
 381 static zap_leaf_t *
 382 zap_create_leaf(zap_t *zap, dmu_tx_t *tx)
 383 {
 384         void *winner;
 385         zap_leaf_t *l = kmem_alloc(sizeof (zap_leaf_t), KM_SLEEP);
 386
 387         ASSERT(RW_WRITE_HELD(&zap->zap_rwlock));
 388
 389         rw_init(&l->l_rwlock, 0, 0, 0);
 390         rw_enter(&l->l_rwlock, RW_WRITER);
 391         l->l_blkid = zap_allocate_blocks(zap, 1);
 392         l->l_dbuf = NULL;
 393         l->l_phys = NULL;
 394
 395         VERIFY(0 == dmu_buf_hold(zap->zap_objset, zap->zap_object,
 396             l->l_blkid << FZAP_BLOCK_SHIFT(zap), NULL, &l->l_dbuf));
 397         winner = dmu_buf_set_user(l->l_dbuf, l, &l->l_phys, zap_leaf_pageout);
 398         ASSERT(winner == NULL);
 399         dmu_buf_will_dirty(l->l_dbuf, tx);
 400
 401         zap_leaf_init(l, zap->zap_normflags != 0);
 402
 403         zap->zap_f.zap_phys->zap_num_leafs++;
 404
 405         return (l);
 406 }
 407
 408 int
 409 fzap_count(zap_t *zap, uint64_t *count)
 410 {
 411         ASSERT(!zap->zap_ismicro);
 412         mutex_enter(&zap->zap_f.zap_num_entries_mtx); /* unnecessary */
 413         *count = zap->zap_f.zap_phys->zap_num_entries;
 414         mutex_exit(&zap->zap_f.zap_num_entries_mtx);
 415         return (0);
 416 }
 417
 418 /*
 419  * Routines for obtaining zap_leaf_t's
 420  */
 421
 422 void
 423 zap_put_leaf(zap_leaf_t *l)
 424 {
 425         rw_exit(&l->l_rwlock);
 426         dmu_buf_rele(l->l_dbuf, NULL);
 427 }
 428
 429 _NOTE(ARGSUSED(0))
 430 static void
 431 zap_leaf_pageout(dmu_buf_t *db, void *vl)
 432 {
 433         zap_leaf_t *l = vl;
 434
 435         rw_destroy(&l->l_rwlock);
 436         kmem_free(l, sizeof (zap_leaf_t));
 437 }
 438
 439 static zap_leaf_t *
 440 zap_open_leaf(uint64_t blkid, dmu_buf_t *db)
 441 {
 442         zap_leaf_t *l, *winner;
 443
 444         ASSERT(blkid != 0);
 445
 446         l = kmem_alloc(sizeof (zap_leaf_t), KM_SLEEP);
 447         rw_init(&l->l_rwlock, 0, 0, 0);
 448         rw_enter(&l->l_rwlock, RW_WRITER);
 449         l->l_blkid = blkid;
 450         l->l_bs = highbit(db->db_size)-1;
 451         l->l_dbuf = db;
 452         l->l_phys = NULL;
 453
 454         winner = dmu_buf_set_user(db, l, &l->l_phys, zap_leaf_pageout);
 455
 456         rw_exit(&l->l_rwlock);
 457         if (winner != NULL) {
 458                 /* someone else set it first */
 459                 zap_leaf_pageout(NULL, l);
 460                 l = winner;
 461         }
 462
 463         /*
 464          * lhr_pad was previously used for the next leaf in the leaf
 465          * chain.  There should be no chained leafs (as we have removed
 466          * support for them).
 467          */
 468         ASSERT3U(l->l_phys->l_hdr.lh_pad1, ==, 0);
 469
 470         /*
 471          * There should be more hash entries than there can be
 472          * chunks to put in the hash table
 473          */
 474         ASSERT3U(ZAP_LEAF_HASH_NUMENTRIES(l), >, ZAP_LEAF_NUMCHUNKS(l) / 3);
 475
 476         /* The chunks should begin at the end of the hash table */
 477         ASSERT3P(&ZAP_LEAF_CHUNK(l, 0), ==,
 478             &l->l_phys->l_hash[ZAP_LEAF_HASH_NUMENTRIES(l)]);
 479
 480         /* The chunks should end at the end of the block */
 481         ASSERT3U((uintptr_t)&ZAP_LEAF_CHUNK(l, ZAP_LEAF_NUMCHUNKS(l)) -
 482             (uintptr_t)l->l_phys, ==, l->l_dbuf->db_size);
 483
 484         return (l);
 485 }
 486
 487 static int
 488 zap_get_leaf_byblk(zap_t *zap, uint64_t blkid, dmu_tx_t *tx, krw_t lt,
 489     zap_leaf_t **lp)
 490 {
 491         dmu_buf_t *db;
 492         zap_leaf_t *l;
 493         int bs = FZAP_BLOCK_SHIFT(zap);
 494         int err;
 495
 496         ASSERT(RW_LOCK_HELD(&zap->zap_rwlock));
 497
 498         err = dmu_buf_hold(zap->zap_objset, zap->zap_object,
 499             blkid << bs, NULL, &db);
 500         if (err)
 501                 return (err);
 502
 503         ASSERT3U(db->db_object, ==, zap->zap_object);
 504         ASSERT3U(db->db_offset, ==, blkid << bs);
 505         ASSERT3U(db->db_size, ==, 1 << bs);
 506         ASSERT(blkid != 0);
 507
 508         l = dmu_buf_get_user(db);
 509
 510         if (l == NULL)
 511                 l = zap_open_leaf(blkid, db);
 512
 513         rw_enter(&l->l_rwlock, lt);
 514         /*
 515          * Must lock before dirtying, otherwise l->l_phys could change,
 516          * causing ASSERT below to fail.
 517          */
 518         if (lt == RW_WRITER)
 519                 dmu_buf_will_dirty(db, tx);
 520         ASSERT3U(l->l_blkid, ==, blkid);
 521         ASSERT3P(l->l_dbuf, ==, db);
 522         ASSERT3P(l->l_phys, ==, l->l_dbuf->db_data);
 523         ASSERT3U(l->l_phys->l_hdr.lh_block_type, ==, ZBT_LEAF);
 524         ASSERT3U(l->l_phys->l_hdr.lh_magic, ==, ZAP_LEAF_MAGIC);
 525
 526         *lp = l;
 527         return (0);
 528 }
 529
 530 static int
 531 zap_idx_to_blk(zap_t *zap, uint64_t idx, uint64_t *valp)
 532 {
 533         ASSERT(RW_LOCK_HELD(&zap->zap_rwlock));
 534
 535         if (zap->zap_f.zap_phys->zap_ptrtbl.zt_numblks == 0) {
 536                 ASSERT3U(idx, <,
 537                     (1ULL << zap->zap_f.zap_phys->zap_ptrtbl.zt_shift));
 538                 *valp = ZAP_EMBEDDED_PTRTBL_ENT(zap, idx);
 539                 return (0);
 540         } else {
 541                 return (zap_table_load(zap, &zap->zap_f.zap_phys->zap_ptrtbl,
 542                     idx, valp));
 543         }
 544 }
 545
 546 static int
 547 zap_set_idx_to_blk(zap_t *zap, uint64_t idx, uint64_t blk, dmu_tx_t *tx)
 548 {
 549         ASSERT(tx != NULL);
 550         ASSERT(RW_WRITE_HELD(&zap->zap_rwlock));
 551
 552         if (zap->zap_f.zap_phys->zap_ptrtbl.zt_blk == 0) {
 553                 ZAP_EMBEDDED_PTRTBL_ENT(zap, idx) = blk;
 554                 return (0);
 555         } else {
 556                 return (zap_table_store(zap, &zap->zap_f.zap_phys->zap_ptrtbl,
 557                     idx, blk, tx));
 558         }
 559 }
 560
 561 static int
 562 zap_deref_leaf(zap_t *zap, uint64_t h, dmu_tx_t *tx, krw_t lt, zap_leaf_t **lp)
 563 {
 564         uint64_t idx, blk;
 565         int err;
 566
 567         ASSERT(zap->zap_dbuf == NULL ||
 568             zap->zap_f.zap_phys == zap->zap_dbuf->db_data);
 569         ASSERT3U(zap->zap_f.zap_phys->zap_magic, ==, ZAP_MAGIC);
 570         idx = ZAP_HASH_IDX(h, zap->zap_f.zap_phys->zap_ptrtbl.zt_shift);
 571         err = zap_idx_to_blk(zap, idx, &blk);
 572         if (err != 0)
 573                 return (err);
 574         err = zap_get_leaf_byblk(zap, blk, tx, lt, lp);
 575
 576         ASSERT(err || ZAP_HASH_IDX(h, (*lp)->l_phys->l_hdr.lh_prefix_len) ==
 577             (*lp)->l_phys->l_hdr.lh_prefix);
 578         return (err);
 579 }
 580
 581 static int
 582 zap_expand_leaf(zap_name_t *zn, zap_leaf_t *l, dmu_tx_t *tx, zap_leaf_t **lp)
 583 {
 584         zap_t *zap = zn->zn_zap;
 585         uint64_t hash = zn->zn_hash;
 586         zap_leaf_t *nl;
 587         int prefix_diff, i, err;
 588         uint64_t sibling;
 589         int old_prefix_len = l->l_phys->l_hdr.lh_prefix_len;
 590
 591         ASSERT3U(old_prefix_len, <=, zap->zap_f.zap_phys->zap_ptrtbl.zt_shift);
 592         ASSERT(RW_LOCK_HELD(&zap->zap_rwlock));
 593
 594         ASSERT3U(ZAP_HASH_IDX(hash, old_prefix_len), ==,
 595             l->l_phys->l_hdr.lh_prefix);
 596
 597         if (zap_tryupgradedir(zap, tx) == 0 ||
 598             old_prefix_len == zap->zap_f.zap_phys->zap_ptrtbl.zt_shift) {
 599                 /* We failed to upgrade, or need to grow the pointer table */
 600                 objset_t *os = zap->zap_objset;
 601                 uint64_t object = zap->zap_object;
 602
 603                 zap_put_leaf(l);
 604                 zap_unlockdir(zap);
 605                 err = zap_lockdir(os, object, tx, RW_WRITER,
 606                     FALSE, FALSE, &zn->zn_zap);
 607                 zap = zn->zn_zap;
 608                 if (err)
 609                         return (err);
 610                 ASSERT(!zap->zap_ismicro);
 611
 612                 while (old_prefix_len ==
 613                     zap->zap_f.zap_phys->zap_ptrtbl.zt_shift) {
 614                         err = zap_grow_ptrtbl(zap, tx);
 615                         if (err)
 616                                 return (err);
 617                 }
 618
 619                 err = zap_deref_leaf(zap, hash, tx, RW_WRITER, &l);
 620                 if (err)
 621                         return (err);
 622
 623                 if (l->l_phys->l_hdr.lh_prefix_len != old_prefix_len) {
 624                         /* it split while our locks were down */
 625                         *lp = l;
 626                         return (0);
 627                 }
 628         }
 629         ASSERT(RW_WRITE_HELD(&zap->zap_rwlock));
 630         ASSERT3U(old_prefix_len, <, zap->zap_f.zap_phys->zap_ptrtbl.zt_shift);
 631         ASSERT3U(ZAP_HASH_IDX(hash, old_prefix_len), ==,
 632             l->l_phys->l_hdr.lh_prefix);
 633
 634         prefix_diff = zap->zap_f.zap_phys->zap_ptrtbl.zt_shift -
 635             (old_prefix_len + 1);
 636         sibling = (ZAP_HASH_IDX(hash, old_prefix_len + 1) | 1) << prefix_diff;
 637
 638         /* check for i/o errors before doing zap_leaf_split */
 639         for (i = 0; i < (1ULL<<prefix_diff); i++) {
 640                 uint64_t blk;
 641                 err = zap_idx_to_blk(zap, sibling+i, &blk);
 642                 if (err)
 643                         return (err);
 644                 ASSERT3U(blk, ==, l->l_blkid);
 645         }
 646
 647         nl = zap_create_leaf(zap, tx);
 648         zap_leaf_split(l, nl, zap->zap_normflags != 0);
 649
 650         /* set sibling pointers */
 651         for (i = 0; i < (1ULL<<prefix_diff); i++) {
 652                 err = zap_set_idx_to_blk(zap, sibling+i, nl->l_blkid, tx);
 653                 ASSERT3U(err, ==, 0); /* we checked for i/o errors above */
 654         }
 655
 656         if (hash & (1ULL << (64 - l->l_phys->l_hdr.lh_prefix_len))) {
 657                 /* we want the sibling */
 658                 zap_put_leaf(l);
 659                 *lp = nl;
 660         } else {
 661                 zap_put_leaf(nl);
 662                 *lp = l;
 663         }
 664
 665         return (0);
 666 }
 667
 668 static void
 669 zap_put_leaf_maybe_grow_ptrtbl(zap_name_t *zn, zap_leaf_t *l, dmu_tx_t *tx)
 670 {
 671         zap_t *zap = zn->zn_zap;
 672         int shift = zap->zap_f.zap_phys->zap_ptrtbl.zt_shift;
 673         int leaffull = (l->l_phys->l_hdr.lh_prefix_len == shift &&
 674             l->l_phys->l_hdr.lh_nfree < ZAP_LEAF_LOW_WATER);
 675
 676         zap_put_leaf(l);
 677
 678         if (leaffull || zap->zap_f.zap_phys->zap_ptrtbl.zt_nextblk) {
 679                 int err;
 680
 681                 /*
 682                  * We are in the middle of growing the pointer table, or
 683                  * this leaf will soon make us grow it.
 684                  */
 685                 if (zap_tryupgradedir(zap, tx) == 0) {
 686                         objset_t *os = zap->zap_objset;
 687                         uint64_t zapobj = zap->zap_object;
 688
 689                         zap_unlockdir(zap);
 690                         err = zap_lockdir(os, zapobj, tx,
 691                             RW_WRITER, FALSE, FALSE, &zn->zn_zap);
 692                         zap = zn->zn_zap;
 693                         if (err)
 694                                 return;
 695                 }
 696
 697                 /* could have finished growing while our locks were down */
 698                 if (zap->zap_f.zap_phys->zap_ptrtbl.zt_shift == shift)
 699                         (void) zap_grow_ptrtbl(zap, tx);
 700         }
 701 }
 702
 703
 704 static int
 705 fzap_checksize(const char *name, uint64_t integer_size, uint64_t num_integers)
 706 {
 707         if (name && strlen(name) > ZAP_MAXNAMELEN)
 708                 return (E2BIG);
 709
 710         /* Only integer sizes supported by C */
 711         switch (integer_size) {
 712         case 1:
 713         case 2:
 714         case 4:
 715         case 8:
 716                 break;
 717         default:
 718                 return (EINVAL);
 719         }
 720
 721         if (integer_size * num_integers > ZAP_MAXVALUELEN)
 722                 return (E2BIG);
 723
 724         return (0);
 725 }
 726
 727 /*
 728  * Routines for manipulating attributes.
 729  */
 730 int
 731 fzap_lookup(zap_name_t *zn,
 732     uint64_t integer_size, uint64_t num_integers, void *buf,
 733     char *realname, int rn_len, boolean_t *ncp)
 734 {
 735         zap_leaf_t *l;
 736         int err;
 737         zap_entry_handle_t zeh;
 738
 739         err = fzap_checksize(zn->zn_name_orij, integer_size, num_integers);
 740         if (err != 0)
 741                 return (err);
 742
 743         err = zap_deref_leaf(zn->zn_zap, zn->zn_hash, NULL, RW_READER, &l);
 744         if (err != 0)
 745                 return (err);
 746         err = zap_leaf_lookup(l, zn, &zeh);
 747         if (err == 0) {
 748                 err = zap_entry_read(&zeh, integer_size, num_integers, buf);
 749                 (void) zap_entry_read_name(&zeh, rn_len, realname);
 750                 if (ncp) {
 751                         *ncp = zap_entry_normalization_conflict(&zeh,
 752                             zn, NULL, zn->zn_zap);
 753                 }
 754         }
 755
 756         zap_put_leaf(l);
 757         return (err);
 758 }
 759
 760 int
 761 fzap_add_cd(zap_name_t *zn,
 762     uint64_t integer_size, uint64_t num_integers,
 763     const void *val, uint32_t cd, dmu_tx_t *tx)
 764 {
 765         zap_leaf_t *l;
 766         int err;
 767         zap_entry_handle_t zeh;
 768         zap_t *zap = zn->zn_zap;
 769
 770         ASSERT(RW_LOCK_HELD(&zap->zap_rwlock));
 771         ASSERT(!zap->zap_ismicro);
 772         ASSERT(fzap_checksize(zn->zn_name_orij,
 773             integer_size, num_integers) == 0);
 774
 775         err = zap_deref_leaf(zap, zn->zn_hash, tx, RW_WRITER, &l);
 776         if (err != 0)
 777                 return (err);
 778 retry:
 779         err = zap_leaf_lookup(l, zn, &zeh);
 780         if (err == 0) {
 781                 err = EEXIST;
 782                 goto out;
 783         }
 784         if (err != ENOENT)
 785                 goto out;
 786
 787         err = zap_entry_create(l, zn->zn_name_orij, zn->zn_hash, cd,
 788             integer_size, num_integers, val, &zeh);
 789
 790         if (err == 0) {
 791                 zap_increment_num_entries(zap, 1, tx);
 792         } else if (err == EAGAIN) {
 793                 err = zap_expand_leaf(zn, l, tx, &l);
 794                 zap = zn->zn_zap;       /* zap_expand_leaf() may change zap */
 795                 if (err == 0)
 796                         goto retry;
 797         }
 798
 799 out:
 800         if (zap != NULL)
 801                 zap_put_leaf_maybe_grow_ptrtbl(zn, l, tx);
 802         return (err);
 803 }
 804
 805 int
 806 fzap_add(zap_name_t *zn,
 807     uint64_t integer_size, uint64_t num_integers,
 808     const void *val, dmu_tx_t *tx)
 809 {
 810         int err = fzap_checksize(zn->zn_name_orij, integer_size, num_integers);
 811         if (err != 0)
 812                 return (err);
 813
 814         return (fzap_add_cd(zn, integer_size, num_integers,
 815             val, ZAP_MAXCD, tx));
 816 }
 817
 818 int
 819 fzap_update(zap_name_t *zn,
 820     int integer_size, uint64_t num_integers, const void *val, dmu_tx_t *tx)
 821 {
 822         zap_leaf_t *l;
 823         int err, create;
 824         zap_entry_handle_t zeh;
 825         zap_t *zap = zn->zn_zap;
 826
 827         ASSERT(RW_LOCK_HELD(&zap->zap_rwlock));
 828         err = fzap_checksize(zn->zn_name_orij, integer_size, num_integers);
 829         if (err != 0)
 830                 return (err);
 831
 832         err = zap_deref_leaf(zap, zn->zn_hash, tx, RW_WRITER, &l);
 833         if (err != 0)
 834                 return (err);
 835 retry:
 836         err = zap_leaf_lookup(l, zn, &zeh);
 837         create = (err == ENOENT);
 838         ASSERT(err == 0 || err == ENOENT);
 839
 840         if (create) {
 841                 err = zap_entry_create(l, zn->zn_name_orij, zn->zn_hash,
 842                     ZAP_MAXCD, integer_size, num_integers, val, &zeh);
 843                 if (err == 0)
 844                         zap_increment_num_entries(zap, 1, tx);
 845         } else {
 846                 err = zap_entry_update(&zeh, integer_size, num_integers, val);
 847         }
 848
 849         if (err == EAGAIN) {
 850                 err = zap_expand_leaf(zn, l, tx, &l);
 851                 zap = zn->zn_zap;       /* zap_expand_leaf() may change zap */
 852                 if (err == 0)
 853                         goto retry;
 854         }
 855
 856         if (zap != NULL)
 857                 zap_put_leaf_maybe_grow_ptrtbl(zn, l, tx);
 858         return (err);
 859 }
 860
 861 int
 862 fzap_length(zap_name_t *zn,
 863     uint64_t *integer_size, uint64_t *num_integers)
 864 {
 865         zap_leaf_t *l;
 866         int err;
 867         zap_entry_handle_t zeh;
 868
 869         err = zap_deref_leaf(zn->zn_zap, zn->zn_hash, NULL, RW_READER, &l);
 870         if (err != 0)
 871                 return (err);
 872         err = zap_leaf_lookup(l, zn, &zeh);
 873         if (err != 0)
 874                 goto out;
 875
 876         if (integer_size)
 877                 *integer_size = zeh.zeh_integer_size;
 878         if (num_integers)
 879                 *num_integers = zeh.zeh_num_integers;
 880 out:
 881         zap_put_leaf(l);
 882         return (err);
 883 }
 884
 885 int
 886 fzap_remove(zap_name_t *zn, dmu_tx_t *tx)
 887 {
 888         zap_leaf_t *l;
 889         int err;
 890         zap_entry_handle_t zeh;
 891
 892         err = zap_deref_leaf(zn->zn_zap, zn->zn_hash, tx, RW_WRITER, &l);
 893         if (err != 0)
 894                 return (err);
 895         err = zap_leaf_lookup(l, zn, &zeh);
 896         if (err == 0) {
 897                 zap_entry_remove(&zeh);
 898                 zap_increment_num_entries(zn->zn_zap, -1, tx);
 899         }
 900         zap_put_leaf(l);
 901         return (err);
 902 }
 903
 904 /*
 905  * Helper functions for consumers.
 906  */
 907
 908 int
 909 zap_value_search(objset_t *os, uint64_t zapobj, uint64_t value, uint64_t mask,
 910     char *name)
 911 {
 912         zap_cursor_t zc;
 913         zap_attribute_t *za;
 914         int err;
 915
 916         if (mask == 0)
 917                 mask = -1ULL;
 918
 919         za = kmem_alloc(sizeof (zap_attribute_t), KM_SLEEP);
 920         for (zap_cursor_init(&zc, os, zapobj);
 921             (err = zap_cursor_retrieve(&zc, za)) == 0;
 922             zap_cursor_advance(&zc)) {
 923                 if ((za->za_first_integer & mask) == (value & mask)) {
 924                         (void) strcpy(name, za->za_name);
 925                         break;
 926                 }
 927         }
 928         zap_cursor_fini(&zc);
 929         kmem_free(za, sizeof (zap_attribute_t));
 930         return (err);
 931 }
 932
 933 int
 934 zap_join(objset_t *os, uint64_t fromobj, uint64_t intoobj, dmu_tx_t *tx)
 935 {
 936         zap_cursor_t zc;
 937         zap_attribute_t za;
 938         int err;
 939
 940         for (zap_cursor_init(&zc, os, fromobj);
 941             zap_cursor_retrieve(&zc, &za) == 0;
 942             (void) zap_cursor_advance(&zc)) {
 943                 if (za.za_integer_length != 8 || za.za_num_integers != 1)
 944                         return (EINVAL);
 945                 err = zap_add(os, intoobj, za.za_name,
 946                     8, 1, &za.za_first_integer, tx);
 947                 if (err)
 948                         return (err);
 949         }
 950         zap_cursor_fini(&zc);
 951         return (0);
 952 }
 953
 954 int
 955 zap_add_int(objset_t *os, uint64_t obj, uint64_t value, dmu_tx_t *tx)
 956 {
 957         char name[20];
 958
 959         (void) snprintf(name, sizeof (name), "%llx", (longlong_t)value);
 960         return (zap_add(os, obj, name, 8, 1, &value, tx));
 961 }
 962
 963 int
 964 zap_remove_int(objset_t *os, uint64_t obj, uint64_t value, dmu_tx_t *tx)
 965 {
 966         char name[20];
 967
 968         (void) snprintf(name, sizeof (name), "%llx", (longlong_t)value);
 969         return (zap_remove(os, obj, name, tx));
 970 }
 971
 972 int
 973 zap_lookup_int(objset_t *os, uint64_t obj, uint64_t value)
 974 {
 975         char name[20];
 976
 977         (void) snprintf(name, sizeof (name), "%llx", (longlong_t)value);
 978         return (zap_lookup(os, obj, name, 8, 1, &value));
 979 }
 980
 981 /*
 982  * Routines for iterating over the attributes.
 983  */
 984
 985 int
 986 fzap_cursor_retrieve(zap_t *zap, zap_cursor_t *zc, zap_attribute_t *za)
 987 {
 988         int err = ENOENT;
 989         zap_entry_handle_t zeh;
 990         zap_leaf_t *l;
 991
 992         /* retrieve the next entry at or after zc_hash/zc_cd */
 993         /* if no entry, return ENOENT */
 994
 995         if (zc->zc_leaf &&
 996             (ZAP_HASH_IDX(zc->zc_hash,
 997             zc->zc_leaf->l_phys->l_hdr.lh_prefix_len) !=
 998             zc->zc_leaf->l_phys->l_hdr.lh_prefix)) {
 999                 rw_enter(&zc->zc_leaf->l_rwlock, RW_READER);
1000                 zap_put_leaf(zc->zc_leaf);
1001                 zc->zc_leaf = NULL;
1002         }
1003
1004 again:
1005         if (zc->zc_leaf == NULL) {
1006                 err = zap_deref_leaf(zap, zc->zc_hash, NULL, RW_READER,
1007                     &zc->zc_leaf);
1008                 if (err != 0)
1009                         return (err);
1010         } else {
1011                 rw_enter(&zc->zc_leaf->l_rwlock, RW_READER);
1012         }
1013         l = zc->zc_leaf;
1014
1015         err = zap_leaf_lookup_closest(l, zc->zc_hash, zc->zc_cd, &zeh);
1016
1017         if (err == ENOENT) {
1018                 uint64_t nocare =
1019                     (1ULL << (64 - l->l_phys->l_hdr.lh_prefix_len)) - 1;
1020                 zc->zc_hash = (zc->zc_hash & ~nocare) + nocare + 1;
1021                 zc->zc_cd = 0;
1022                 if (l->l_phys->l_hdr.lh_prefix_len == 0 || zc->zc_hash == 0) {
1023                         zc->zc_hash = -1ULL;
1024                 } else {
1025                         zap_put_leaf(zc->zc_leaf);
1026                         zc->zc_leaf = NULL;
1027                         goto again;
1028                 }
1029         }
1030
1031         if (err == 0) {
1032                 zc->zc_hash = zeh.zeh_hash;
1033                 zc->zc_cd = zeh.zeh_cd;
1034                 za->za_integer_length = zeh.zeh_integer_size;
1035                 za->za_num_integers = zeh.zeh_num_integers;
1036                 if (zeh.zeh_num_integers == 0) {
1037                         za->za_first_integer = 0;
1038                 } else {
1039                         err = zap_entry_read(&zeh, 8, 1, &za->za_first_integer);
1040                         ASSERT(err == 0 || err == EOVERFLOW);
1041                 }
1042                 err = zap_entry_read_name(&zeh,
1043                     sizeof (za->za_name), za->za_name);
1044                 ASSERT(err == 0);
1045
1046                 za->za_normalization_conflict =
1047                     zap_entry_normalization_conflict(&zeh,
1048                     NULL, za->za_name, zap);
1049         }
1050         rw_exit(&zc->zc_leaf->l_rwlock);
1051         return (err);
1052 }
1053
1054
1055 static void
1056 zap_stats_ptrtbl(zap_t *zap, uint64_t *tbl, int len, zap_stats_t *zs)
1057 {
1058         int i, err;
1059         uint64_t lastblk = 0;
1060
1061         /*
1062          * NB: if a leaf has more pointers than an entire ptrtbl block
1063          * can hold, then it'll be accounted for more than once, since
1064          * we won't have lastblk.
1065          */
1066         for (i = 0; i < len; i++) {
1067                 zap_leaf_t *l;
1068
1069                 if (tbl[i] == lastblk)
1070                         continue;
1071                 lastblk = tbl[i];
1072
1073                 err = zap_get_leaf_byblk(zap, tbl[i], NULL, RW_READER, &l);
1074                 if (err == 0) {
1075                         zap_leaf_stats(zap, l, zs);
1076                         zap_put_leaf(l);
1077                 }
1078         }
1079 }
1080
1081 void
1082 fzap_get_stats(zap_t *zap, zap_stats_t *zs)
1083 {
1084         int bs = FZAP_BLOCK_SHIFT(zap);
1085         zs->zs_blocksize = 1ULL << bs;
1086
1087         /*
1088          * Set zap_phys_t fields
1089          */
1090         zs->zs_num_leafs = zap->zap_f.zap_phys->zap_num_leafs;
1091         zs->zs_num_entries = zap->zap_f.zap_phys->zap_num_entries;
1092         zs->zs_num_blocks = zap->zap_f.zap_phys->zap_freeblk;
1093         zs->zs_block_type = zap->zap_f.zap_phys->zap_block_type;
1094         zs->zs_magic = zap->zap_f.zap_phys->zap_magic;
1095         zs->zs_salt = zap->zap_f.zap_phys->zap_salt;
1096
1097         /*
1098          * Set zap_ptrtbl fields
1099          */
1100         zs->zs_ptrtbl_len = 1ULL << zap->zap_f.zap_phys->zap_ptrtbl.zt_shift;
1101         zs->zs_ptrtbl_nextblk = zap->zap_f.zap_phys->zap_ptrtbl.zt_nextblk;
1102         zs->zs_ptrtbl_blks_copied =
1103             zap->zap_f.zap_phys->zap_ptrtbl.zt_blks_copied;
1104         zs->zs_ptrtbl_zt_blk = zap->zap_f.zap_phys->zap_ptrtbl.zt_blk;
1105         zs->zs_ptrtbl_zt_numblks = zap->zap_f.zap_phys->zap_ptrtbl.zt_numblks;
1106         zs->zs_ptrtbl_zt_shift = zap->zap_f.zap_phys->zap_ptrtbl.zt_shift;
1107
1108         if (zap->zap_f.zap_phys->zap_ptrtbl.zt_numblks == 0) {
1109                 /* the ptrtbl is entirely in the header block. */
1110                 zap_stats_ptrtbl(zap, &ZAP_EMBEDDED_PTRTBL_ENT(zap, 0),
1111                     1 << ZAP_EMBEDDED_PTRTBL_SHIFT(zap), zs);
1112         } else {
1113                 int b;
1114
1115                 dmu_prefetch(zap->zap_objset, zap->zap_object,
1116                     zap->zap_f.zap_phys->zap_ptrtbl.zt_blk << bs,
1117                     zap->zap_f.zap_phys->zap_ptrtbl.zt_numblks << bs);
1118
1119                 for (b = 0; b < zap->zap_f.zap_phys->zap_ptrtbl.zt_numblks;
1120                     b++) {
1121                         dmu_buf_t *db;
1122                         int err;
1123
1124                         err = dmu_buf_hold(zap->zap_objset, zap->zap_object,
1125                             (zap->zap_f.zap_phys->zap_ptrtbl.zt_blk + b) << bs,
1126                             FTAG, &db);
1127                         if (err == 0) {
1128                                 zap_stats_ptrtbl(zap, db->db_data,
1129                                     1<<(bs-3), zs);
1130                                 dmu_buf_rele(db, FTAG);
1131                         }
1132                 }
1133         }
1134 }
1135
1136 int
1137 fzap_count_write(zap_name_t *zn, int add, uint64_t *towrite,
1138     uint64_t *tooverwrite)
1139 {
1140         zap_t *zap = zn->zn_zap;
1141         zap_leaf_t *l;
1142         int err;
1143
1144         /*
1145          * Account for the header block of the fatzap.
1146          */
1147         if (!add && dmu_buf_freeable(zap->zap_dbuf)) {
1148                 tooverwrite += zap->zap_dbuf->db_size;
1149         } else {
1150                 towrite += zap->zap_dbuf->db_size;
1151         }
1152
1153         /*
1154          * Account for the pointer table blocks.
1155          * If we are adding we need to account for the following cases :
1156          * - If the pointer table is embedded, this operation could force an
1157          *   external pointer table.
1158          * - If this already has an external pointer table this operation
1159          *   could extend the table.
1160          */
1161         if (add) {
1162                 if (zap->zap_f.zap_phys->zap_ptrtbl.zt_blk == 0)
1163                         towrite += zap->zap_dbuf->db_size;
1164                 else
1165                         towrite += (zap->zap_dbuf->db_size * 3);
1166         }
1167
1168         /*
1169          * Now, check if the block containing leaf is freeable
1170          * and account accordingly.
1171          */
1172         err = zap_deref_leaf(zap, zn->zn_hash, NULL, RW_READER, &l);
1173         if (err != 0) {
1174                 return (err);
1175         }
1176
1177         if (!add && dmu_buf_freeable(l->l_dbuf)) {
1178                 tooverwrite += l->l_dbuf->db_size;
1179         } else {
1180                 /*
1181                  * If this an add operation, the leaf block could split.
1182                  * Hence, we need to account for an additional leaf block.
1183                  */
1184                 towrite += (add ? 2 : 1) * l->l_dbuf->db_size;
1185         }
1186
1187         zap_put_leaf(l);
1188         return (0);
1189 }