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