sys/contrib/openzfs/module/zfs/zap_micro.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 /*
  23  * Copyright (c) 2005, 2010, Oracle and/or its affiliates. All rights reserved.
  24  * Copyright (c) 2011, 2018 by Delphix. All rights reserved.
  25  * Copyright (c) 2014 Spectra Logic Corporation, All rights reserved.
  26  * Copyright 2017 Nexenta Systems, Inc.
  27  */
  28
  29 #include <sys/zio.h>
  30 #include <sys/spa.h>
  31 #include <sys/dmu.h>
  32 #include <sys/zfs_context.h>
  33 #include <sys/zap.h>
  34 #include <sys/zap_impl.h>
  35 #include <sys/zap_leaf.h>
  36 #include <sys/avl.h>
  37 #include <sys/arc.h>
  38 #include <sys/dmu_objset.h>
  39
  40 #ifdef _KERNEL
  41 #include <sys/sunddi.h>
  42 #endif
  43
  44 static int mzap_upgrade(zap_t **zapp,
  45     const void *tag, dmu_tx_t *tx, zap_flags_t flags);
  46
  47 uint64_t
  48 zap_getflags(zap_t *zap)
  49 {
  50         if (zap->zap_ismicro)
  51                 return (0);
  52         return (zap_f_phys(zap)->zap_flags);
  53 }
  54
  55 int
  56 zap_hashbits(zap_t *zap)
  57 {
  58         if (zap_getflags(zap) & ZAP_FLAG_HASH64)
  59                 return (48);
  60         else
  61                 return (28);
  62 }
  63
  64 uint32_t
  65 zap_maxcd(zap_t *zap)
  66 {
  67         if (zap_getflags(zap) & ZAP_FLAG_HASH64)
  68                 return ((1<<16)-1);
  69         else
  70                 return (-1U);
  71 }
  72
  73 static uint64_t
  74 zap_hash(zap_name_t *zn)
  75 {
  76         zap_t *zap = zn->zn_zap;
  77         uint64_t h = 0;
  78
  79         if (zap_getflags(zap) & ZAP_FLAG_PRE_HASHED_KEY) {
  80                 ASSERT(zap_getflags(zap) & ZAP_FLAG_UINT64_KEY);
  81                 h = *(uint64_t *)zn->zn_key_orig;
  82         } else {
  83                 h = zap->zap_salt;
  84                 ASSERT(h != 0);
  85                 ASSERT(zfs_crc64_table[128] == ZFS_CRC64_POLY);
  86
  87                 if (zap_getflags(zap) & ZAP_FLAG_UINT64_KEY) {
  88                         const uint64_t *wp = zn->zn_key_norm;
  89
  90                         ASSERT(zn->zn_key_intlen == 8);
  91                         for (int i = 0; i < zn->zn_key_norm_numints;
  92                             wp++, i++) {
  93                                 uint64_t word = *wp;
  94
  95                                 for (int j = 0; j < zn->zn_key_intlen; j++) {
  96                                         h = (h >> 8) ^
  97                                             zfs_crc64_table[(h ^ word) & 0xFF];
  98                                         word >>= NBBY;
  99                                 }
 100                         }
 101                 } else {
 102                         const uint8_t *cp = zn->zn_key_norm;
 103
 104                         /*
 105                          * We previously stored the terminating null on
 106                          * disk, but didn't hash it, so we need to
 107                          * continue to not hash it.  (The
 108                          * zn_key_*_numints includes the terminating
 109                          * null for non-binary keys.)
 110                          */
 111                         int len = zn->zn_key_norm_numints - 1;
 112
 113                         ASSERT(zn->zn_key_intlen == 1);
 114                         for (int i = 0; i < len; cp++, i++) {
 115                                 h = (h >> 8) ^
 116                                     zfs_crc64_table[(h ^ *cp) & 0xFF];
 117                         }
 118                 }
 119         }
 120         /*
 121          * Don't use all 64 bits, since we need some in the cookie for
 122          * the collision differentiator.  We MUST use the high bits,
 123          * since those are the ones that we first pay attention to when
 124          * choosing the bucket.
 125          */
 126         h &= ~((1ULL << (64 - zap_hashbits(zap))) - 1);
 127
 128         return (h);
 129 }
 130
 131 static int
 132 zap_normalize(zap_t *zap, const char *name, char *namenorm, int normflags)
 133 {
 134         ASSERT(!(zap_getflags(zap) & ZAP_FLAG_UINT64_KEY));
 135
 136         size_t inlen = strlen(name) + 1;
 137         size_t outlen = ZAP_MAXNAMELEN;
 138
 139         int err = 0;
 140         (void) u8_textprep_str((char *)name, &inlen, namenorm, &outlen,
 141             normflags | U8_TEXTPREP_IGNORE_NULL | U8_TEXTPREP_IGNORE_INVALID,
 142             U8_UNICODE_LATEST, &err);
 143
 144         return (err);
 145 }
 146
 147 boolean_t
 148 zap_match(zap_name_t *zn, const char *matchname)
 149 {
 150         ASSERT(!(zap_getflags(zn->zn_zap) & ZAP_FLAG_UINT64_KEY));
 151
 152         if (zn->zn_matchtype & MT_NORMALIZE) {
 153                 char norm[ZAP_MAXNAMELEN];
 154
 155                 if (zap_normalize(zn->zn_zap, matchname, norm,
 156                     zn->zn_normflags) != 0)
 157                         return (B_FALSE);
 158
 159                 return (strcmp(zn->zn_key_norm, norm) == 0);
 160         } else {
 161                 return (strcmp(zn->zn_key_orig, matchname) == 0);
 162         }
 163 }
 164
 165 void
 166 zap_name_free(zap_name_t *zn)
 167 {
 168         kmem_free(zn, sizeof (zap_name_t));
 169 }
 170
 171 zap_name_t *
 172 zap_name_alloc(zap_t *zap, const char *key, matchtype_t mt)
 173 {
 174         zap_name_t *zn = kmem_alloc(sizeof (zap_name_t), KM_SLEEP);
 175
 176         zn->zn_zap = zap;
 177         zn->zn_key_intlen = sizeof (*key);
 178         zn->zn_key_orig = key;
 179         zn->zn_key_orig_numints = strlen(zn->zn_key_orig) + 1;
 180         zn->zn_matchtype = mt;
 181         zn->zn_normflags = zap->zap_normflags;
 182
 183         /*
 184          * If we're dealing with a case sensitive lookup on a mixed or
 185          * insensitive fs, remove U8_TEXTPREP_TOUPPER or the lookup
 186          * will fold case to all caps overriding the lookup request.
 187          */
 188         if (mt & MT_MATCH_CASE)
 189                 zn->zn_normflags &= ~U8_TEXTPREP_TOUPPER;
 190
 191         if (zap->zap_normflags) {
 192                 /*
 193                  * We *must* use zap_normflags because this normalization is
 194                  * what the hash is computed from.
 195                  */
 196                 if (zap_normalize(zap, key, zn->zn_normbuf,
 197                     zap->zap_normflags) != 0) {
 198                         zap_name_free(zn);
 199                         return (NULL);
 200                 }
 201                 zn->zn_key_norm = zn->zn_normbuf;
 202                 zn->zn_key_norm_numints = strlen(zn->zn_key_norm) + 1;
 203         } else {
 204                 if (mt != 0) {
 205                         zap_name_free(zn);
 206                         return (NULL);
 207                 }
 208                 zn->zn_key_norm = zn->zn_key_orig;
 209                 zn->zn_key_norm_numints = zn->zn_key_orig_numints;
 210         }
 211
 212         zn->zn_hash = zap_hash(zn);
 213
 214         if (zap->zap_normflags != zn->zn_normflags) {
 215                 /*
 216                  * We *must* use zn_normflags because this normalization is
 217                  * what the matching is based on.  (Not the hash!)
 218                  */
 219                 if (zap_normalize(zap, key, zn->zn_normbuf,
 220                     zn->zn_normflags) != 0) {
 221                         zap_name_free(zn);
 222                         return (NULL);
 223                 }
 224                 zn->zn_key_norm_numints = strlen(zn->zn_key_norm) + 1;
 225         }
 226
 227         return (zn);
 228 }
 229
 230 static zap_name_t *
 231 zap_name_alloc_uint64(zap_t *zap, const uint64_t *key, int numints)
 232 {
 233         zap_name_t *zn = kmem_alloc(sizeof (zap_name_t), KM_SLEEP);
 234
 235         ASSERT(zap->zap_normflags == 0);
 236         zn->zn_zap = zap;
 237         zn->zn_key_intlen = sizeof (*key);
 238         zn->zn_key_orig = zn->zn_key_norm = key;
 239         zn->zn_key_orig_numints = zn->zn_key_norm_numints = numints;
 240         zn->zn_matchtype = 0;
 241
 242         zn->zn_hash = zap_hash(zn);
 243         return (zn);
 244 }
 245
 246 static void
 247 mzap_byteswap(mzap_phys_t *buf, size_t size)
 248 {
 249         buf->mz_block_type = BSWAP_64(buf->mz_block_type);
 250         buf->mz_salt = BSWAP_64(buf->mz_salt);
 251         buf->mz_normflags = BSWAP_64(buf->mz_normflags);
 252         int max = (size / MZAP_ENT_LEN) - 1;
 253         for (int i = 0; i < max; i++) {
 254                 buf->mz_chunk[i].mze_value =
 255                     BSWAP_64(buf->mz_chunk[i].mze_value);
 256                 buf->mz_chunk[i].mze_cd =
 257                     BSWAP_32(buf->mz_chunk[i].mze_cd);
 258         }
 259 }
 260
 261 void
 262 zap_byteswap(void *buf, size_t size)
 263 {
 264         uint64_t block_type = *(uint64_t *)buf;
 265
 266         if (block_type == ZBT_MICRO || block_type == BSWAP_64(ZBT_MICRO)) {
 267                 /* ASSERT(magic == ZAP_LEAF_MAGIC); */
 268                 mzap_byteswap(buf, size);
 269         } else {
 270                 fzap_byteswap(buf, size);
 271         }
 272 }
 273
 274 static int
 275 mze_compare(const void *arg1, const void *arg2)
 276 {
 277         const mzap_ent_t *mze1 = arg1;
 278         const mzap_ent_t *mze2 = arg2;
 279
 280         int cmp = TREE_CMP(mze1->mze_hash, mze2->mze_hash);
 281         if (likely(cmp))
 282                 return (cmp);
 283
 284         return (TREE_CMP(mze1->mze_cd, mze2->mze_cd));
 285 }
 286
 287 static void
 288 mze_insert(zap_t *zap, int chunkid, uint64_t hash)
 289 {
 290         ASSERT(zap->zap_ismicro);
 291         ASSERT(RW_WRITE_HELD(&zap->zap_rwlock));
 292
 293         mzap_ent_t *mze = kmem_alloc(sizeof (mzap_ent_t), KM_SLEEP);
 294         mze->mze_chunkid = chunkid;
 295         mze->mze_hash = hash;
 296         mze->mze_cd = MZE_PHYS(zap, mze)->mze_cd;
 297         ASSERT(MZE_PHYS(zap, mze)->mze_name[0] != 0);
 298         avl_add(&zap->zap_m.zap_avl, mze);
 299 }
 300
 301 static mzap_ent_t *
 302 mze_find(zap_name_t *zn)
 303 {
 304         mzap_ent_t mze_tofind;
 305         mzap_ent_t *mze;
 306         avl_index_t idx;
 307         avl_tree_t *avl = &zn->zn_zap->zap_m.zap_avl;
 308
 309         ASSERT(zn->zn_zap->zap_ismicro);
 310         ASSERT(RW_LOCK_HELD(&zn->zn_zap->zap_rwlock));
 311
 312         mze_tofind.mze_hash = zn->zn_hash;
 313         mze_tofind.mze_cd = 0;
 314
 315         mze = avl_find(avl, &mze_tofind, &idx);
 316         if (mze == NULL)
 317                 mze = avl_nearest(avl, idx, AVL_AFTER);
 318         for (; mze && mze->mze_hash == zn->zn_hash; mze = AVL_NEXT(avl, mze)) {
 319                 ASSERT3U(mze->mze_cd, ==, MZE_PHYS(zn->zn_zap, mze)->mze_cd);
 320                 if (zap_match(zn, MZE_PHYS(zn->zn_zap, mze)->mze_name))
 321                         return (mze);
 322         }
 323
 324         return (NULL);
 325 }
 326
 327 static uint32_t
 328 mze_find_unused_cd(zap_t *zap, uint64_t hash)
 329 {
 330         mzap_ent_t mze_tofind;
 331         avl_index_t idx;
 332         avl_tree_t *avl = &zap->zap_m.zap_avl;
 333
 334         ASSERT(zap->zap_ismicro);
 335         ASSERT(RW_LOCK_HELD(&zap->zap_rwlock));
 336
 337         mze_tofind.mze_hash = hash;
 338         mze_tofind.mze_cd = 0;
 339
 340         uint32_t cd = 0;
 341         for (mzap_ent_t *mze = avl_find(avl, &mze_tofind, &idx);
 342             mze && mze->mze_hash == hash; mze = AVL_NEXT(avl, mze)) {
 343                 if (mze->mze_cd != cd)
 344                         break;
 345                 cd++;
 346         }
 347
 348         return (cd);
 349 }
 350
 351 /*
 352  * Each mzap entry requires at max : 4 chunks
 353  * 3 chunks for names + 1 chunk for value.
 354  */
 355 #define MZAP_ENT_CHUNKS (1 + ZAP_LEAF_ARRAY_NCHUNKS(MZAP_NAME_LEN) + \
 356         ZAP_LEAF_ARRAY_NCHUNKS(sizeof (uint64_t)))
 357
 358 /*
 359  * Check if the current entry keeps the colliding entries under the fatzap leaf
 360  * size.
 361  */
 362 static boolean_t
 363 mze_canfit_fzap_leaf(zap_name_t *zn, uint64_t hash)
 364 {
 365         zap_t *zap = zn->zn_zap;
 366         mzap_ent_t mze_tofind;
 367         mzap_ent_t *mze;
 368         avl_index_t idx;
 369         avl_tree_t *avl = &zap->zap_m.zap_avl;
 370         uint32_t mzap_ents = 0;
 371
 372         mze_tofind.mze_hash = hash;
 373         mze_tofind.mze_cd = 0;
 374
 375         for (mze = avl_find(avl, &mze_tofind, &idx);
 376             mze && mze->mze_hash == hash; mze = AVL_NEXT(avl, mze)) {
 377                 mzap_ents++;
 378         }
 379
 380         /* Include the new entry being added */
 381         mzap_ents++;
 382
 383         return (ZAP_LEAF_NUMCHUNKS_DEF > (mzap_ents * MZAP_ENT_CHUNKS));
 384 }
 385
 386 static void
 387 mze_remove(zap_t *zap, mzap_ent_t *mze)
 388 {
 389         ASSERT(zap->zap_ismicro);
 390         ASSERT(RW_WRITE_HELD(&zap->zap_rwlock));
 391
 392         avl_remove(&zap->zap_m.zap_avl, mze);
 393         kmem_free(mze, sizeof (mzap_ent_t));
 394 }
 395
 396 static void
 397 mze_destroy(zap_t *zap)
 398 {
 399         mzap_ent_t *mze;
 400         void *avlcookie = NULL;
 401
 402         while ((mze = avl_destroy_nodes(&zap->zap_m.zap_avl, &avlcookie)))
 403                 kmem_free(mze, sizeof (mzap_ent_t));
 404         avl_destroy(&zap->zap_m.zap_avl);
 405 }
 406
 407 static zap_t *
 408 mzap_open(objset_t *os, uint64_t obj, dmu_buf_t *db)
 409 {
 410         zap_t *winner;
 411         uint64_t *zap_hdr = (uint64_t *)db->db_data;
 412         uint64_t zap_block_type = zap_hdr[0];
 413         uint64_t zap_magic = zap_hdr[1];
 414
 415         ASSERT3U(MZAP_ENT_LEN, ==, sizeof (mzap_ent_phys_t));
 416
 417         zap_t *zap = kmem_zalloc(sizeof (zap_t), KM_SLEEP);
 418         rw_init(&zap->zap_rwlock, NULL, RW_DEFAULT, NULL);
 419         rw_enter(&zap->zap_rwlock, RW_WRITER);
 420         zap->zap_objset = os;
 421         zap->zap_object = obj;
 422         zap->zap_dbuf = db;
 423
 424         if (zap_block_type != ZBT_MICRO) {
 425                 mutex_init(&zap->zap_f.zap_num_entries_mtx, 0, MUTEX_DEFAULT,
 426                     0);
 427                 zap->zap_f.zap_block_shift = highbit64(db->db_size) - 1;
 428                 if (zap_block_type != ZBT_HEADER || zap_magic != ZAP_MAGIC) {
 429                         winner = NULL;  /* No actual winner here... */
 430                         goto handle_winner;
 431                 }
 432         } else {
 433                 zap->zap_ismicro = TRUE;
 434         }
 435
 436         /*
 437          * Make sure that zap_ismicro is set before we let others see
 438          * it, because zap_lockdir() checks zap_ismicro without the lock
 439          * held.
 440          */
 441         dmu_buf_init_user(&zap->zap_dbu, zap_evict_sync, NULL, &zap->zap_dbuf);
 442         winner = dmu_buf_set_user(db, &zap->zap_dbu);
 443
 444         if (winner != NULL)
 445                 goto handle_winner;
 446
 447         if (zap->zap_ismicro) {
 448                 zap->zap_salt = zap_m_phys(zap)->mz_salt;
 449                 zap->zap_normflags = zap_m_phys(zap)->mz_normflags;
 450                 zap->zap_m.zap_num_chunks = db->db_size / MZAP_ENT_LEN - 1;
 451                 avl_create(&zap->zap_m.zap_avl, mze_compare,
 452                     sizeof (mzap_ent_t), offsetof(mzap_ent_t, mze_node));
 453
 454                 for (int i = 0; i < zap->zap_m.zap_num_chunks; i++) {
 455                         mzap_ent_phys_t *mze =
 456                             &zap_m_phys(zap)->mz_chunk[i];
 457                         if (mze->mze_name[0]) {
 458                                 zap_name_t *zn;
 459
 460                                 zap->zap_m.zap_num_entries++;
 461                                 zn = zap_name_alloc(zap, mze->mze_name, 0);
 462                                 mze_insert(zap, i, zn->zn_hash);
 463                                 zap_name_free(zn);
 464                         }
 465                 }
 466         } else {
 467                 zap->zap_salt = zap_f_phys(zap)->zap_salt;
 468                 zap->zap_normflags = zap_f_phys(zap)->zap_normflags;
 469
 470                 ASSERT3U(sizeof (struct zap_leaf_header), ==,
 471                     2*ZAP_LEAF_CHUNKSIZE);
 472
 473                 /*
 474                  * The embedded pointer table should not overlap the
 475                  * other members.
 476                  */
 477                 ASSERT3P(&ZAP_EMBEDDED_PTRTBL_ENT(zap, 0), >,
 478                     &zap_f_phys(zap)->zap_salt);
 479
 480                 /*
 481                  * The embedded pointer table should end at the end of
 482                  * the block
 483                  */
 484                 ASSERT3U((uintptr_t)&ZAP_EMBEDDED_PTRTBL_ENT(zap,
 485                     1<<ZAP_EMBEDDED_PTRTBL_SHIFT(zap)) -
 486                     (uintptr_t)zap_f_phys(zap), ==,
 487                     zap->zap_dbuf->db_size);
 488         }
 489         rw_exit(&zap->zap_rwlock);
 490         return (zap);
 491
 492 handle_winner:
 493         rw_exit(&zap->zap_rwlock);
 494         rw_destroy(&zap->zap_rwlock);
 495         if (!zap->zap_ismicro)
 496                 mutex_destroy(&zap->zap_f.zap_num_entries_mtx);
 497         kmem_free(zap, sizeof (zap_t));
 498         return (winner);
 499 }
 500
 501 /*
 502  * This routine "consumes" the caller's hold on the dbuf, which must
 503  * have the specified tag.
 504  */
 505 static int
 506 zap_lockdir_impl(dmu_buf_t *db, const void *tag, dmu_tx_t *tx,
 507     krw_t lti, boolean_t fatreader, boolean_t adding, zap_t **zapp)
 508 {
 509         ASSERT0(db->db_offset);
 510         objset_t *os = dmu_buf_get_objset(db);
 511         uint64_t obj = db->db_object;
 512         dmu_object_info_t doi;
 513
 514         *zapp = NULL;
 515
 516         dmu_object_info_from_db(db, &doi);
 517         if (DMU_OT_BYTESWAP(doi.doi_type) != DMU_BSWAP_ZAP)
 518                 return (SET_ERROR(EINVAL));
 519
 520         zap_t *zap = dmu_buf_get_user(db);
 521         if (zap == NULL) {
 522                 zap = mzap_open(os, obj, db);
 523                 if (zap == NULL) {
 524                         /*
 525                          * mzap_open() didn't like what it saw on-disk.
 526                          * Check for corruption!
 527                          */
 528                         return (SET_ERROR(EIO));
 529                 }
 530         }
 531
 532         /*
 533          * We're checking zap_ismicro without the lock held, in order to
 534          * tell what type of lock we want.  Once we have some sort of
 535          * lock, see if it really is the right type.  In practice this
 536          * can only be different if it was upgraded from micro to fat,
 537          * and micro wanted WRITER but fat only needs READER.
 538          */
 539         krw_t lt = (!zap->zap_ismicro && fatreader) ? RW_READER : lti;
 540         rw_enter(&zap->zap_rwlock, lt);
 541         if (lt != ((!zap->zap_ismicro && fatreader) ? RW_READER : lti)) {
 542                 /* it was upgraded, now we only need reader */
 543                 ASSERT(lt == RW_WRITER);
 544                 ASSERT(RW_READER ==
 545                     ((!zap->zap_ismicro && fatreader) ? RW_READER : lti));
 546                 rw_downgrade(&zap->zap_rwlock);
 547                 lt = RW_READER;
 548         }
 549
 550         zap->zap_objset = os;
 551
 552         if (lt == RW_WRITER)
 553                 dmu_buf_will_dirty(db, tx);
 554
 555         ASSERT3P(zap->zap_dbuf, ==, db);
 556
 557         ASSERT(!zap->zap_ismicro ||
 558             zap->zap_m.zap_num_entries <= zap->zap_m.zap_num_chunks);
 559         if (zap->zap_ismicro && tx && adding &&
 560             zap->zap_m.zap_num_entries == zap->zap_m.zap_num_chunks) {
 561                 uint64_t newsz = db->db_size + SPA_MINBLOCKSIZE;
 562                 if (newsz > MZAP_MAX_BLKSZ) {
 563                         dprintf("upgrading obj %llu: num_entries=%u\n",
 564                             (u_longlong_t)obj, zap->zap_m.zap_num_entries);
 565                         *zapp = zap;
 566                         int err = mzap_upgrade(zapp, tag, tx, 0);
 567                         if (err != 0)
 568                                 rw_exit(&zap->zap_rwlock);
 569                         return (err);
 570                 }
 571                 VERIFY0(dmu_object_set_blocksize(os, obj, newsz, 0, tx));
 572                 zap->zap_m.zap_num_chunks =
 573                     db->db_size / MZAP_ENT_LEN - 1;
 574         }
 575
 576         *zapp = zap;
 577         return (0);
 578 }
 579
 580 static int
 581 zap_lockdir_by_dnode(dnode_t *dn, dmu_tx_t *tx,
 582     krw_t lti, boolean_t fatreader, boolean_t adding, const void *tag,
 583     zap_t **zapp)
 584 {
 585         dmu_buf_t *db;
 586
 587         int err = dmu_buf_hold_by_dnode(dn, 0, tag, &db, DMU_READ_NO_PREFETCH);
 588         if (err != 0) {
 589                 return (err);
 590         }
 591 #ifdef ZFS_DEBUG
 592         {
 593                 dmu_object_info_t doi;
 594                 dmu_object_info_from_db(db, &doi);
 595                 ASSERT3U(DMU_OT_BYTESWAP(doi.doi_type), ==, DMU_BSWAP_ZAP);
 596         }
 597 #endif
 598
 599         err = zap_lockdir_impl(db, tag, tx, lti, fatreader, adding, zapp);
 600         if (err != 0) {
 601                 dmu_buf_rele(db, tag);
 602         }
 603         return (err);
 604 }
 605
 606 int
 607 zap_lockdir(objset_t *os, uint64_t obj, dmu_tx_t *tx,
 608     krw_t lti, boolean_t fatreader, boolean_t adding, const void *tag,
 609     zap_t **zapp)
 610 {
 611         dmu_buf_t *db;
 612
 613         int err = dmu_buf_hold(os, obj, 0, tag, &db, DMU_READ_NO_PREFETCH);
 614         if (err != 0)
 615                 return (err);
 616 #ifdef ZFS_DEBUG
 617         {
 618                 dmu_object_info_t doi;
 619                 dmu_object_info_from_db(db, &doi);
 620                 ASSERT3U(DMU_OT_BYTESWAP(doi.doi_type), ==, DMU_BSWAP_ZAP);
 621         }
 622 #endif
 623         err = zap_lockdir_impl(db, tag, tx, lti, fatreader, adding, zapp);
 624         if (err != 0)
 625                 dmu_buf_rele(db, tag);
 626         return (err);
 627 }
 628
 629 void
 630 zap_unlockdir(zap_t *zap, const void *tag)
 631 {
 632         rw_exit(&zap->zap_rwlock);
 633         dmu_buf_rele(zap->zap_dbuf, tag);
 634 }
 635
 636 static int
 637 mzap_upgrade(zap_t **zapp, const void *tag, dmu_tx_t *tx, zap_flags_t flags)
 638 {
 639         int err = 0;
 640         zap_t *zap = *zapp;
 641
 642         ASSERT(RW_WRITE_HELD(&zap->zap_rwlock));
 643
 644         int sz = zap->zap_dbuf->db_size;
 645         mzap_phys_t *mzp = vmem_alloc(sz, KM_SLEEP);
 646         memcpy(mzp, zap->zap_dbuf->db_data, sz);
 647         int nchunks = zap->zap_m.zap_num_chunks;
 648
 649         if (!flags) {
 650                 err = dmu_object_set_blocksize(zap->zap_objset, zap->zap_object,
 651                     1ULL << fzap_default_block_shift, 0, tx);
 652                 if (err != 0) {
 653                         vmem_free(mzp, sz);
 654                         return (err);
 655                 }
 656         }
 657
 658         dprintf("upgrading obj=%llu with %u chunks\n",
 659             (u_longlong_t)zap->zap_object, nchunks);
 660         /* XXX destroy the avl later, so we can use the stored hash value */
 661         mze_destroy(zap);
 662
 663         fzap_upgrade(zap, tx, flags);
 664
 665         for (int i = 0; i < nchunks; i++) {
 666                 mzap_ent_phys_t *mze = &mzp->mz_chunk[i];
 667                 if (mze->mze_name[0] == 0)
 668                         continue;
 669                 dprintf("adding %s=%llu\n",
 670                     mze->mze_name, (u_longlong_t)mze->mze_value);
 671                 zap_name_t *zn = zap_name_alloc(zap, mze->mze_name, 0);
 672                 /* If we fail here, we would end up losing entries */
 673                 VERIFY0(fzap_add_cd(zn, 8, 1, &mze->mze_value, mze->mze_cd,
 674                     tag, tx));
 675                 zap = zn->zn_zap;       /* fzap_add_cd() may change zap */
 676                 zap_name_free(zn);
 677         }
 678         vmem_free(mzp, sz);
 679         *zapp = zap;
 680         return (0);
 681 }
 682
 683 /*
 684  * The "normflags" determine the behavior of the matchtype_t which is
 685  * passed to zap_lookup_norm().  Names which have the same normalized
 686  * version will be stored with the same hash value, and therefore we can
 687  * perform normalization-insensitive lookups.  We can be Unicode form-
 688  * insensitive and/or case-insensitive.  The following flags are valid for
 689  * "normflags":
 690  *
 691  * U8_TEXTPREP_NFC
 692  * U8_TEXTPREP_NFD
 693  * U8_TEXTPREP_NFKC
 694  * U8_TEXTPREP_NFKD
 695  * U8_TEXTPREP_TOUPPER
 696  *
 697  * The *_NF* (Normalization Form) flags are mutually exclusive; at most one
 698  * of them may be supplied.
 699  */
 700 void
 701 mzap_create_impl(dnode_t *dn, int normflags, zap_flags_t flags, dmu_tx_t *tx)
 702 {
 703         dmu_buf_t *db;
 704
 705         VERIFY0(dmu_buf_hold_by_dnode(dn, 0, FTAG, &db, DMU_READ_NO_PREFETCH));
 706
 707         dmu_buf_will_dirty(db, tx);
 708         mzap_phys_t *zp = db->db_data;
 709         zp->mz_block_type = ZBT_MICRO;
 710         zp->mz_salt =
 711             ((uintptr_t)db ^ (uintptr_t)tx ^ (dn->dn_object << 1)) | 1ULL;
 712         zp->mz_normflags = normflags;
 713
 714         if (flags != 0) {
 715                 zap_t *zap;
 716                 /* Only fat zap supports flags; upgrade immediately. */
 717                 VERIFY0(zap_lockdir_impl(db, FTAG, tx, RW_WRITER,
 718                     B_FALSE, B_FALSE, &zap));
 719                 VERIFY0(mzap_upgrade(&zap, FTAG, tx, flags));
 720                 zap_unlockdir(zap, FTAG);
 721         } else {
 722                 dmu_buf_rele(db, FTAG);
 723         }
 724 }
 725
 726 static uint64_t
 727 zap_create_impl(objset_t *os, int normflags, zap_flags_t flags,
 728     dmu_object_type_t ot, int leaf_blockshift, int indirect_blockshift,
 729     dmu_object_type_t bonustype, int bonuslen, int dnodesize,
 730     dnode_t **allocated_dnode, const void *tag, dmu_tx_t *tx)
 731 {
 732         uint64_t obj;
 733
 734         ASSERT3U(DMU_OT_BYTESWAP(ot), ==, DMU_BSWAP_ZAP);
 735
 736         if (allocated_dnode == NULL) {
 737                 dnode_t *dn;
 738                 obj = dmu_object_alloc_hold(os, ot, 1ULL << leaf_blockshift,
 739                     indirect_blockshift, bonustype, bonuslen, dnodesize,
 740                     &dn, FTAG, tx);
 741                 mzap_create_impl(dn, normflags, flags, tx);
 742                 dnode_rele(dn, FTAG);
 743         } else {
 744                 obj = dmu_object_alloc_hold(os, ot, 1ULL << leaf_blockshift,
 745                     indirect_blockshift, bonustype, bonuslen, dnodesize,
 746                     allocated_dnode, tag, tx);
 747                 mzap_create_impl(*allocated_dnode, normflags, flags, tx);
 748         }
 749
 750         return (obj);
 751 }
 752
 753 int
 754 zap_create_claim(objset_t *os, uint64_t obj, dmu_object_type_t ot,
 755     dmu_object_type_t bonustype, int bonuslen, dmu_tx_t *tx)
 756 {
 757         return (zap_create_claim_dnsize(os, obj, ot, bonustype, bonuslen,
 758             0, tx));
 759 }
 760
 761 int
 762 zap_create_claim_dnsize(objset_t *os, uint64_t obj, dmu_object_type_t ot,
 763     dmu_object_type_t bonustype, int bonuslen, int dnodesize, dmu_tx_t *tx)
 764 {
 765         return (zap_create_claim_norm_dnsize(os, obj,
 766             0, ot, bonustype, bonuslen, dnodesize, tx));
 767 }
 768
 769 int
 770 zap_create_claim_norm(objset_t *os, uint64_t obj, int normflags,
 771     dmu_object_type_t ot,
 772     dmu_object_type_t bonustype, int bonuslen, dmu_tx_t *tx)
 773 {
 774         return (zap_create_claim_norm_dnsize(os, obj, normflags, ot, bonustype,
 775             bonuslen, 0, tx));
 776 }
 777
 778 int
 779 zap_create_claim_norm_dnsize(objset_t *os, uint64_t obj, int normflags,
 780     dmu_object_type_t ot, dmu_object_type_t bonustype, int bonuslen,
 781     int dnodesize, dmu_tx_t *tx)
 782 {
 783         dnode_t *dn;
 784         int error;
 785
 786         ASSERT3U(DMU_OT_BYTESWAP(ot), ==, DMU_BSWAP_ZAP);
 787         error = dmu_object_claim_dnsize(os, obj, ot, 0, bonustype, bonuslen,
 788             dnodesize, tx);
 789         if (error != 0)
 790                 return (error);
 791
 792         error = dnode_hold(os, obj, FTAG, &dn);
 793         if (error != 0)
 794                 return (error);
 795
 796         mzap_create_impl(dn, normflags, 0, tx);
 797
 798         dnode_rele(dn, FTAG);
 799
 800         return (0);
 801 }
 802
 803 uint64_t
 804 zap_create(objset_t *os, dmu_object_type_t ot,
 805     dmu_object_type_t bonustype, int bonuslen, dmu_tx_t *tx)
 806 {
 807         return (zap_create_norm(os, 0, ot, bonustype, bonuslen, tx));
 808 }
 809
 810 uint64_t
 811 zap_create_dnsize(objset_t *os, dmu_object_type_t ot,
 812     dmu_object_type_t bonustype, int bonuslen, int dnodesize, dmu_tx_t *tx)
 813 {
 814         return (zap_create_norm_dnsize(os, 0, ot, bonustype, bonuslen,
 815             dnodesize, tx));
 816 }
 817
 818 uint64_t
 819 zap_create_norm(objset_t *os, int normflags, dmu_object_type_t ot,
 820     dmu_object_type_t bonustype, int bonuslen, dmu_tx_t *tx)
 821 {
 822         return (zap_create_norm_dnsize(os, normflags, ot, bonustype, bonuslen,
 823             0, tx));
 824 }
 825
 826 uint64_t
 827 zap_create_norm_dnsize(objset_t *os, int normflags, dmu_object_type_t ot,
 828     dmu_object_type_t bonustype, int bonuslen, int dnodesize, dmu_tx_t *tx)
 829 {
 830         return (zap_create_impl(os, normflags, 0, ot, 0, 0,
 831             bonustype, bonuslen, dnodesize, NULL, NULL, tx));
 832 }
 833
 834 uint64_t
 835 zap_create_flags(objset_t *os, int normflags, zap_flags_t flags,
 836     dmu_object_type_t ot, int leaf_blockshift, int indirect_blockshift,
 837     dmu_object_type_t bonustype, int bonuslen, dmu_tx_t *tx)
 838 {
 839         return (zap_create_flags_dnsize(os, normflags, flags, ot,
 840             leaf_blockshift, indirect_blockshift, bonustype, bonuslen, 0, tx));
 841 }
 842
 843 uint64_t
 844 zap_create_flags_dnsize(objset_t *os, int normflags, zap_flags_t flags,
 845     dmu_object_type_t ot, int leaf_blockshift, int indirect_blockshift,
 846     dmu_object_type_t bonustype, int bonuslen, int dnodesize, dmu_tx_t *tx)
 847 {
 848         return (zap_create_impl(os, normflags, flags, ot, leaf_blockshift,
 849             indirect_blockshift, bonustype, bonuslen, dnodesize, NULL, NULL,
 850             tx));
 851 }
 852
 853 /*
 854  * Create a zap object and return a pointer to the newly allocated dnode via
 855  * the allocated_dnode argument.  The returned dnode will be held and the
 856  * caller is responsible for releasing the hold by calling dnode_rele().
 857  */
 858 uint64_t
 859 zap_create_hold(objset_t *os, int normflags, zap_flags_t flags,
 860     dmu_object_type_t ot, int leaf_blockshift, int indirect_blockshift,
 861     dmu_object_type_t bonustype, int bonuslen, int dnodesize,
 862     dnode_t **allocated_dnode, const void *tag, dmu_tx_t *tx)
 863 {
 864         return (zap_create_impl(os, normflags, flags, ot, leaf_blockshift,
 865             indirect_blockshift, bonustype, bonuslen, dnodesize,
 866             allocated_dnode, tag, tx));
 867 }
 868
 869 int
 870 zap_destroy(objset_t *os, uint64_t zapobj, dmu_tx_t *tx)
 871 {
 872         /*
 873          * dmu_object_free will free the object number and free the
 874          * data.  Freeing the data will cause our pageout function to be
 875          * called, which will destroy our data (zap_leaf_t's and zap_t).
 876          */
 877
 878         return (dmu_object_free(os, zapobj, tx));
 879 }
 880
 881 void
 882 zap_evict_sync(void *dbu)
 883 {
 884         zap_t *zap = dbu;
 885
 886         rw_destroy(&zap->zap_rwlock);
 887
 888         if (zap->zap_ismicro)
 889                 mze_destroy(zap);
 890         else
 891                 mutex_destroy(&zap->zap_f.zap_num_entries_mtx);
 892
 893         kmem_free(zap, sizeof (zap_t));
 894 }
 895
 896 int
 897 zap_count(objset_t *os, uint64_t zapobj, uint64_t *count)
 898 {
 899         zap_t *zap;
 900
 901         int err =
 902             zap_lockdir(os, zapobj, NULL, RW_READER, TRUE, FALSE, FTAG, &zap);
 903         if (err != 0)
 904                 return (err);
 905         if (!zap->zap_ismicro) {
 906                 err = fzap_count(zap, count);
 907         } else {
 908                 *count = zap->zap_m.zap_num_entries;
 909         }
 910         zap_unlockdir(zap, FTAG);
 911         return (err);
 912 }
 913
 914 /*
 915  * zn may be NULL; if not specified, it will be computed if needed.
 916  * See also the comment above zap_entry_normalization_conflict().
 917  */
 918 static boolean_t
 919 mzap_normalization_conflict(zap_t *zap, zap_name_t *zn, mzap_ent_t *mze)
 920 {
 921         int direction = AVL_BEFORE;
 922         boolean_t allocdzn = B_FALSE;
 923
 924         if (zap->zap_normflags == 0)
 925                 return (B_FALSE);
 926
 927 again:
 928         for (mzap_ent_t *other = avl_walk(&zap->zap_m.zap_avl, mze, direction);
 929             other && other->mze_hash == mze->mze_hash;
 930             other = avl_walk(&zap->zap_m.zap_avl, other, direction)) {
 931
 932                 if (zn == NULL) {
 933                         zn = zap_name_alloc(zap, MZE_PHYS(zap, mze)->mze_name,
 934                             MT_NORMALIZE);
 935                         allocdzn = B_TRUE;
 936                 }
 937                 if (zap_match(zn, MZE_PHYS(zap, other)->mze_name)) {
 938                         if (allocdzn)
 939                                 zap_name_free(zn);
 940                         return (B_TRUE);
 941                 }
 942         }
 943
 944         if (direction == AVL_BEFORE) {
 945                 direction = AVL_AFTER;
 946                 goto again;
 947         }
 948
 949         if (allocdzn)
 950                 zap_name_free(zn);
 951         return (B_FALSE);
 952 }
 953
 954 /*
 955  * Routines for manipulating attributes.
 956  */
 957
 958 int
 959 zap_lookup(objset_t *os, uint64_t zapobj, const char *name,
 960     uint64_t integer_size, uint64_t num_integers, void *buf)
 961 {
 962         return (zap_lookup_norm(os, zapobj, name, integer_size,
 963             num_integers, buf, 0, NULL, 0, NULL));
 964 }
 965
 966 static int
 967 zap_lookup_impl(zap_t *zap, const char *name,
 968     uint64_t integer_size, uint64_t num_integers, void *buf,
 969     matchtype_t mt, char *realname, int rn_len,
 970     boolean_t *ncp)
 971 {
 972         int err = 0;
 973
 974         zap_name_t *zn = zap_name_alloc(zap, name, mt);
 975         if (zn == NULL)
 976                 return (SET_ERROR(ENOTSUP));
 977
 978         if (!zap->zap_ismicro) {
 979                 err = fzap_lookup(zn, integer_size, num_integers, buf,
 980                     realname, rn_len, ncp);
 981         } else {
 982                 mzap_ent_t *mze = mze_find(zn);
 983                 if (mze == NULL) {
 984                         err = SET_ERROR(ENOENT);
 985                 } else {
 986                         if (num_integers < 1) {
 987                                 err = SET_ERROR(EOVERFLOW);
 988                         } else if (integer_size != 8) {
 989                                 err = SET_ERROR(EINVAL);
 990                         } else {
 991                                 *(uint64_t *)buf =
 992                                     MZE_PHYS(zap, mze)->mze_value;
 993                                 (void) strlcpy(realname,
 994                                     MZE_PHYS(zap, mze)->mze_name, rn_len);
 995                                 if (ncp) {
 996                                         *ncp = mzap_normalization_conflict(zap,
 997                                             zn, mze);
 998                                 }
 999                         }
1000                 }
1001         }
1002         zap_name_free(zn);
1003         return (err);
1004 }
1005
1006 int
1007 zap_lookup_norm(objset_t *os, uint64_t zapobj, const char *name,
1008     uint64_t integer_size, uint64_t num_integers, void *buf,
1009     matchtype_t mt, char *realname, int rn_len,
1010     boolean_t *ncp)
1011 {
1012         zap_t *zap;
1013
1014         int err =
1015             zap_lockdir(os, zapobj, NULL, RW_READER, TRUE, FALSE, FTAG, &zap);
1016         if (err != 0)
1017                 return (err);
1018         err = zap_lookup_impl(zap, name, integer_size,
1019             num_integers, buf, mt, realname, rn_len, ncp);
1020         zap_unlockdir(zap, FTAG);
1021         return (err);
1022 }
1023
1024 int
1025 zap_prefetch(objset_t *os, uint64_t zapobj, const char *name)
1026 {
1027         zap_t *zap;
1028         int err;
1029         zap_name_t *zn;
1030
1031         err = zap_lockdir(os, zapobj, NULL, RW_READER, TRUE, FALSE, FTAG, &zap);
1032         if (err)
1033                 return (err);
1034         zn = zap_name_alloc(zap, name, 0);
1035         if (zn == NULL) {
1036                 zap_unlockdir(zap, FTAG);
1037                 return (SET_ERROR(ENOTSUP));
1038         }
1039
1040         fzap_prefetch(zn);
1041         zap_name_free(zn);
1042         zap_unlockdir(zap, FTAG);
1043         return (err);
1044 }
1045
1046 int
1047 zap_lookup_by_dnode(dnode_t *dn, const char *name,
1048     uint64_t integer_size, uint64_t num_integers, void *buf)
1049 {
1050         return (zap_lookup_norm_by_dnode(dn, name, integer_size,
1051             num_integers, buf, 0, NULL, 0, NULL));
1052 }
1053
1054 int
1055 zap_lookup_norm_by_dnode(dnode_t *dn, const char *name,
1056     uint64_t integer_size, uint64_t num_integers, void *buf,
1057     matchtype_t mt, char *realname, int rn_len,
1058     boolean_t *ncp)
1059 {
1060         zap_t *zap;
1061
1062         int err = zap_lockdir_by_dnode(dn, NULL, RW_READER, TRUE, FALSE,
1063             FTAG, &zap);
1064         if (err != 0)
1065                 return (err);
1066         err = zap_lookup_impl(zap, name, integer_size,
1067             num_integers, buf, mt, realname, rn_len, ncp);
1068         zap_unlockdir(zap, FTAG);
1069         return (err);
1070 }
1071
1072 int
1073 zap_prefetch_uint64(objset_t *os, uint64_t zapobj, const uint64_t *key,
1074     int key_numints)
1075 {
1076         zap_t *zap;
1077
1078         int err =
1079             zap_lockdir(os, zapobj, NULL, RW_READER, TRUE, FALSE, FTAG, &zap);
1080         if (err != 0)
1081                 return (err);
1082         zap_name_t *zn = zap_name_alloc_uint64(zap, key, key_numints);
1083         if (zn == NULL) {
1084                 zap_unlockdir(zap, FTAG);
1085                 return (SET_ERROR(ENOTSUP));
1086         }
1087
1088         fzap_prefetch(zn);
1089         zap_name_free(zn);
1090         zap_unlockdir(zap, FTAG);
1091         return (err);
1092 }
1093
1094 int
1095 zap_lookup_uint64(objset_t *os, uint64_t zapobj, const uint64_t *key,
1096     int key_numints, uint64_t integer_size, uint64_t num_integers, void *buf)
1097 {
1098         zap_t *zap;
1099
1100         int err =
1101             zap_lockdir(os, zapobj, NULL, RW_READER, TRUE, FALSE, FTAG, &zap);
1102         if (err != 0)
1103                 return (err);
1104         zap_name_t *zn = zap_name_alloc_uint64(zap, key, key_numints);
1105         if (zn == NULL) {
1106                 zap_unlockdir(zap, FTAG);
1107                 return (SET_ERROR(ENOTSUP));
1108         }
1109
1110         err = fzap_lookup(zn, integer_size, num_integers, buf,
1111             NULL, 0, NULL);
1112         zap_name_free(zn);
1113         zap_unlockdir(zap, FTAG);
1114         return (err);
1115 }
1116
1117 int
1118 zap_contains(objset_t *os, uint64_t zapobj, const char *name)
1119 {
1120         int err = zap_lookup_norm(os, zapobj, name, 0,
1121             0, NULL, 0, NULL, 0, NULL);
1122         if (err == EOVERFLOW || err == EINVAL)
1123                 err = 0; /* found, but skipped reading the value */
1124         return (err);
1125 }
1126
1127 int
1128 zap_length(objset_t *os, uint64_t zapobj, const char *name,
1129     uint64_t *integer_size, uint64_t *num_integers)
1130 {
1131         zap_t *zap;
1132
1133         int err =
1134             zap_lockdir(os, zapobj, NULL, RW_READER, TRUE, FALSE, FTAG, &zap);
1135         if (err != 0)
1136                 return (err);
1137         zap_name_t *zn = zap_name_alloc(zap, name, 0);
1138         if (zn == NULL) {
1139                 zap_unlockdir(zap, FTAG);
1140                 return (SET_ERROR(ENOTSUP));
1141         }
1142         if (!zap->zap_ismicro) {
1143                 err = fzap_length(zn, integer_size, num_integers);
1144         } else {
1145                 mzap_ent_t *mze = mze_find(zn);
1146                 if (mze == NULL) {
1147                         err = SET_ERROR(ENOENT);
1148                 } else {
1149                         if (integer_size)
1150                                 *integer_size = 8;
1151                         if (num_integers)
1152                                 *num_integers = 1;
1153                 }
1154         }
1155         zap_name_free(zn);
1156         zap_unlockdir(zap, FTAG);
1157         return (err);
1158 }
1159
1160 int
1161 zap_length_uint64(objset_t *os, uint64_t zapobj, const uint64_t *key,
1162     int key_numints, uint64_t *integer_size, uint64_t *num_integers)
1163 {
1164         zap_t *zap;
1165
1166         int err =
1167             zap_lockdir(os, zapobj, NULL, RW_READER, TRUE, FALSE, FTAG, &zap);
1168         if (err != 0)
1169                 return (err);
1170         zap_name_t *zn = zap_name_alloc_uint64(zap, key, key_numints);
1171         if (zn == NULL) {
1172                 zap_unlockdir(zap, FTAG);
1173                 return (SET_ERROR(ENOTSUP));
1174         }
1175         err = fzap_length(zn, integer_size, num_integers);
1176         zap_name_free(zn);
1177         zap_unlockdir(zap, FTAG);
1178         return (err);
1179 }
1180
1181 static void
1182 mzap_addent(zap_name_t *zn, uint64_t value)
1183 {
1184         zap_t *zap = zn->zn_zap;
1185         int start = zap->zap_m.zap_alloc_next;
1186
1187         ASSERT(RW_WRITE_HELD(&zap->zap_rwlock));
1188
1189 #ifdef ZFS_DEBUG
1190         for (int i = 0; i < zap->zap_m.zap_num_chunks; i++) {
1191                 mzap_ent_phys_t *mze = &zap_m_phys(zap)->mz_chunk[i];
1192                 ASSERT(strcmp(zn->zn_key_orig, mze->mze_name) != 0);
1193         }
1194 #endif
1195
1196         uint32_t cd = mze_find_unused_cd(zap, zn->zn_hash);
1197         /* given the limited size of the microzap, this can't happen */
1198         ASSERT(cd < zap_maxcd(zap));
1199
1200 again:
1201         for (int i = start; i < zap->zap_m.zap_num_chunks; i++) {
1202                 mzap_ent_phys_t *mze = &zap_m_phys(zap)->mz_chunk[i];
1203                 if (mze->mze_name[0] == 0) {
1204                         mze->mze_value = value;
1205                         mze->mze_cd = cd;
1206                         (void) strlcpy(mze->mze_name, zn->zn_key_orig,
1207                             sizeof (mze->mze_name));
1208                         zap->zap_m.zap_num_entries++;
1209                         zap->zap_m.zap_alloc_next = i+1;
1210                         if (zap->zap_m.zap_alloc_next ==
1211                             zap->zap_m.zap_num_chunks)
1212                                 zap->zap_m.zap_alloc_next = 0;
1213                         mze_insert(zap, i, zn->zn_hash);
1214                         return;
1215                 }
1216         }
1217         if (start != 0) {
1218                 start = 0;
1219                 goto again;
1220         }
1221         cmn_err(CE_PANIC, "out of entries!");
1222 }
1223
1224 static int
1225 zap_add_impl(zap_t *zap, const char *key,
1226     int integer_size, uint64_t num_integers,
1227     const void *val, dmu_tx_t *tx, const void *tag)
1228 {
1229         const uint64_t *intval = val;
1230         int err = 0;
1231
1232         zap_name_t *zn = zap_name_alloc(zap, key, 0);
1233         if (zn == NULL) {
1234                 zap_unlockdir(zap, tag);
1235                 return (SET_ERROR(ENOTSUP));
1236         }
1237         if (!zap->zap_ismicro) {
1238                 err = fzap_add(zn, integer_size, num_integers, val, tag, tx);
1239                 zap = zn->zn_zap;       /* fzap_add() may change zap */
1240         } else if (integer_size != 8 || num_integers != 1 ||
1241             strlen(key) >= MZAP_NAME_LEN ||
1242             !mze_canfit_fzap_leaf(zn, zn->zn_hash)) {
1243                 err = mzap_upgrade(&zn->zn_zap, tag, tx, 0);
1244                 if (err == 0) {
1245                         err = fzap_add(zn, integer_size, num_integers, val,
1246                             tag, tx);
1247                 }
1248                 zap = zn->zn_zap;       /* fzap_add() may change zap */
1249         } else {
1250                 if (mze_find(zn) != NULL) {
1251                         err = SET_ERROR(EEXIST);
1252                 } else {
1253                         mzap_addent(zn, *intval);
1254                 }
1255         }
1256         ASSERT(zap == zn->zn_zap);
1257         zap_name_free(zn);
1258         if (zap != NULL)        /* may be NULL if fzap_add() failed */
1259                 zap_unlockdir(zap, tag);
1260         return (err);
1261 }
1262
1263 int
1264 zap_add(objset_t *os, uint64_t zapobj, const char *key,
1265     int integer_size, uint64_t num_integers,
1266     const void *val, dmu_tx_t *tx)
1267 {
1268         zap_t *zap;
1269         int err;
1270
1271         err = zap_lockdir(os, zapobj, tx, RW_WRITER, TRUE, TRUE, FTAG, &zap);
1272         if (err != 0)
1273                 return (err);
1274         err = zap_add_impl(zap, key, integer_size, num_integers, val, tx, FTAG);
1275         /* zap_add_impl() calls zap_unlockdir() */
1276         return (err);
1277 }
1278
1279 int
1280 zap_add_by_dnode(dnode_t *dn, const char *key,
1281     int integer_size, uint64_t num_integers,
1282     const void *val, dmu_tx_t *tx)
1283 {
1284         zap_t *zap;
1285         int err;
1286
1287         err = zap_lockdir_by_dnode(dn, tx, RW_WRITER, TRUE, TRUE, FTAG, &zap);
1288         if (err != 0)
1289                 return (err);
1290         err = zap_add_impl(zap, key, integer_size, num_integers, val, tx, FTAG);
1291         /* zap_add_impl() calls zap_unlockdir() */
1292         return (err);
1293 }
1294
1295 int
1296 zap_add_uint64(objset_t *os, uint64_t zapobj, const uint64_t *key,
1297     int key_numints, int integer_size, uint64_t num_integers,
1298     const void *val, dmu_tx_t *tx)
1299 {
1300         zap_t *zap;
1301
1302         int err =
1303             zap_lockdir(os, zapobj, tx, RW_WRITER, TRUE, TRUE, FTAG, &zap);
1304         if (err != 0)
1305                 return (err);
1306         zap_name_t *zn = zap_name_alloc_uint64(zap, key, key_numints);
1307         if (zn == NULL) {
1308                 zap_unlockdir(zap, FTAG);
1309                 return (SET_ERROR(ENOTSUP));
1310         }
1311         err = fzap_add(zn, integer_size, num_integers, val, FTAG, tx);
1312         zap = zn->zn_zap;       /* fzap_add() may change zap */
1313         zap_name_free(zn);
1314         if (zap != NULL)        /* may be NULL if fzap_add() failed */
1315                 zap_unlockdir(zap, FTAG);
1316         return (err);
1317 }
1318
1319 int
1320 zap_update(objset_t *os, uint64_t zapobj, const char *name,
1321     int integer_size, uint64_t num_integers, const void *val, dmu_tx_t *tx)
1322 {
1323         zap_t *zap;
1324         const uint64_t *intval = val;
1325
1326         int err =
1327             zap_lockdir(os, zapobj, tx, RW_WRITER, TRUE, TRUE, FTAG, &zap);
1328         if (err != 0)
1329                 return (err);
1330         zap_name_t *zn = zap_name_alloc(zap, name, 0);
1331         if (zn == NULL) {
1332                 zap_unlockdir(zap, FTAG);
1333                 return (SET_ERROR(ENOTSUP));
1334         }
1335         if (!zap->zap_ismicro) {
1336                 err = fzap_update(zn, integer_size, num_integers, val,
1337                     FTAG, tx);
1338                 zap = zn->zn_zap;       /* fzap_update() may change zap */
1339         } else if (integer_size != 8 || num_integers != 1 ||
1340             strlen(name) >= MZAP_NAME_LEN) {
1341                 dprintf("upgrading obj %llu: intsz=%u numint=%llu name=%s\n",
1342                     (u_longlong_t)zapobj, integer_size,
1343                     (u_longlong_t)num_integers, name);
1344                 err = mzap_upgrade(&zn->zn_zap, FTAG, tx, 0);
1345                 if (err == 0) {
1346                         err = fzap_update(zn, integer_size, num_integers,
1347                             val, FTAG, tx);
1348                 }
1349                 zap = zn->zn_zap;       /* fzap_update() may change zap */
1350         } else {
1351                 mzap_ent_t *mze = mze_find(zn);
1352                 if (mze != NULL) {
1353                         MZE_PHYS(zap, mze)->mze_value = *intval;
1354                 } else {
1355                         mzap_addent(zn, *intval);
1356                 }
1357         }
1358         ASSERT(zap == zn->zn_zap);
1359         zap_name_free(zn);
1360         if (zap != NULL)        /* may be NULL if fzap_upgrade() failed */
1361                 zap_unlockdir(zap, FTAG);
1362         return (err);
1363 }
1364
1365 int
1366 zap_update_uint64(objset_t *os, uint64_t zapobj, const uint64_t *key,
1367     int key_numints,
1368     int integer_size, uint64_t num_integers, const void *val, dmu_tx_t *tx)
1369 {
1370         zap_t *zap;
1371
1372         int err =
1373             zap_lockdir(os, zapobj, tx, RW_WRITER, TRUE, TRUE, FTAG, &zap);
1374         if (err != 0)
1375                 return (err);
1376         zap_name_t *zn = zap_name_alloc_uint64(zap, key, key_numints);
1377         if (zn == NULL) {
1378                 zap_unlockdir(zap, FTAG);
1379                 return (SET_ERROR(ENOTSUP));
1380         }
1381         err = fzap_update(zn, integer_size, num_integers, val, FTAG, tx);
1382         zap = zn->zn_zap;       /* fzap_update() may change zap */
1383         zap_name_free(zn);
1384         if (zap != NULL)        /* may be NULL if fzap_upgrade() failed */
1385                 zap_unlockdir(zap, FTAG);
1386         return (err);
1387 }
1388
1389 int
1390 zap_remove(objset_t *os, uint64_t zapobj, const char *name, dmu_tx_t *tx)
1391 {
1392         return (zap_remove_norm(os, zapobj, name, 0, tx));
1393 }
1394
1395 static int
1396 zap_remove_impl(zap_t *zap, const char *name,
1397     matchtype_t mt, dmu_tx_t *tx)
1398 {
1399         int err = 0;
1400
1401         zap_name_t *zn = zap_name_alloc(zap, name, mt);
1402         if (zn == NULL)
1403                 return (SET_ERROR(ENOTSUP));
1404         if (!zap->zap_ismicro) {
1405                 err = fzap_remove(zn, tx);
1406         } else {
1407                 mzap_ent_t *mze = mze_find(zn);
1408                 if (mze == NULL) {
1409                         err = SET_ERROR(ENOENT);
1410                 } else {
1411                         zap->zap_m.zap_num_entries--;
1412                         memset(&zap_m_phys(zap)->mz_chunk[mze->mze_chunkid], 0,
1413                             sizeof (mzap_ent_phys_t));
1414                         mze_remove(zap, mze);
1415                 }
1416         }
1417         zap_name_free(zn);
1418         return (err);
1419 }
1420
1421 int
1422 zap_remove_norm(objset_t *os, uint64_t zapobj, const char *name,
1423     matchtype_t mt, dmu_tx_t *tx)
1424 {
1425         zap_t *zap;
1426         int err;
1427
1428         err = zap_lockdir(os, zapobj, tx, RW_WRITER, TRUE, FALSE, FTAG, &zap);
1429         if (err)
1430                 return (err);
1431         err = zap_remove_impl(zap, name, mt, tx);
1432         zap_unlockdir(zap, FTAG);
1433         return (err);
1434 }
1435
1436 int
1437 zap_remove_by_dnode(dnode_t *dn, const char *name, dmu_tx_t *tx)
1438 {
1439         zap_t *zap;
1440         int err;
1441
1442         err = zap_lockdir_by_dnode(dn, tx, RW_WRITER, TRUE, FALSE, FTAG, &zap);
1443         if (err)
1444                 return (err);
1445         err = zap_remove_impl(zap, name, 0, tx);
1446         zap_unlockdir(zap, FTAG);
1447         return (err);
1448 }
1449
1450 int
1451 zap_remove_uint64(objset_t *os, uint64_t zapobj, const uint64_t *key,
1452     int key_numints, dmu_tx_t *tx)
1453 {
1454         zap_t *zap;
1455
1456         int err =
1457             zap_lockdir(os, zapobj, tx, RW_WRITER, TRUE, FALSE, FTAG, &zap);
1458         if (err != 0)
1459                 return (err);
1460         zap_name_t *zn = zap_name_alloc_uint64(zap, key, key_numints);
1461         if (zn == NULL) {
1462                 zap_unlockdir(zap, FTAG);
1463                 return (SET_ERROR(ENOTSUP));
1464         }
1465         err = fzap_remove(zn, tx);
1466         zap_name_free(zn);
1467         zap_unlockdir(zap, FTAG);
1468         return (err);
1469 }
1470
1471 /*
1472  * Routines for iterating over the attributes.
1473  */
1474
1475 static void
1476 zap_cursor_init_impl(zap_cursor_t *zc, objset_t *os, uint64_t zapobj,
1477     uint64_t serialized, boolean_t prefetch)
1478 {
1479         zc->zc_objset = os;
1480         zc->zc_zap = NULL;
1481         zc->zc_leaf = NULL;
1482         zc->zc_zapobj = zapobj;
1483         zc->zc_serialized = serialized;
1484         zc->zc_hash = 0;
1485         zc->zc_cd = 0;
1486         zc->zc_prefetch = prefetch;
1487 }
1488 void
1489 zap_cursor_init_serialized(zap_cursor_t *zc, objset_t *os, uint64_t zapobj,
1490     uint64_t serialized)
1491 {
1492         zap_cursor_init_impl(zc, os, zapobj, serialized, B_TRUE);
1493 }
1494
1495 /*
1496  * Initialize a cursor at the beginning of the ZAP object.  The entire
1497  * ZAP object will be prefetched.
1498  */
1499 void
1500 zap_cursor_init(zap_cursor_t *zc, objset_t *os, uint64_t zapobj)
1501 {
1502         zap_cursor_init_impl(zc, os, zapobj, 0, B_TRUE);
1503 }
1504
1505 /*
1506  * Initialize a cursor at the beginning, but request that we not prefetch
1507  * the entire ZAP object.
1508  */
1509 void
1510 zap_cursor_init_noprefetch(zap_cursor_t *zc, objset_t *os, uint64_t zapobj)
1511 {
1512         zap_cursor_init_impl(zc, os, zapobj, 0, B_FALSE);
1513 }
1514
1515 void
1516 zap_cursor_fini(zap_cursor_t *zc)
1517 {
1518         if (zc->zc_zap) {
1519                 rw_enter(&zc->zc_zap->zap_rwlock, RW_READER);
1520                 zap_unlockdir(zc->zc_zap, NULL);
1521                 zc->zc_zap = NULL;
1522         }
1523         if (zc->zc_leaf) {
1524                 rw_enter(&zc->zc_leaf->l_rwlock, RW_READER);
1525                 zap_put_leaf(zc->zc_leaf);
1526                 zc->zc_leaf = NULL;
1527         }
1528         zc->zc_objset = NULL;
1529 }
1530
1531 uint64_t
1532 zap_cursor_serialize(zap_cursor_t *zc)
1533 {
1534         if (zc->zc_hash == -1ULL)
1535                 return (-1ULL);
1536         if (zc->zc_zap == NULL)
1537                 return (zc->zc_serialized);
1538         ASSERT((zc->zc_hash & zap_maxcd(zc->zc_zap)) == 0);
1539         ASSERT(zc->zc_cd < zap_maxcd(zc->zc_zap));
1540
1541         /*
1542          * We want to keep the high 32 bits of the cursor zero if we can, so
1543          * that 32-bit programs can access this.  So usually use a small
1544          * (28-bit) hash value so we can fit 4 bits of cd into the low 32-bits
1545          * of the cursor.
1546          *
1547          * [ collision differentiator | zap_hashbits()-bit hash value ]
1548          */
1549         return ((zc->zc_hash >> (64 - zap_hashbits(zc->zc_zap))) |
1550             ((uint64_t)zc->zc_cd << zap_hashbits(zc->zc_zap)));
1551 }
1552
1553 int
1554 zap_cursor_retrieve(zap_cursor_t *zc, zap_attribute_t *za)
1555 {
1556         int err;
1557
1558         if (zc->zc_hash == -1ULL)
1559                 return (SET_ERROR(ENOENT));
1560
1561         if (zc->zc_zap == NULL) {
1562                 int hb;
1563                 err = zap_lockdir(zc->zc_objset, zc->zc_zapobj, NULL,
1564                     RW_READER, TRUE, FALSE, NULL, &zc->zc_zap);
1565                 if (err != 0)
1566                         return (err);
1567
1568                 /*
1569                  * To support zap_cursor_init_serialized, advance, retrieve,
1570                  * we must add to the existing zc_cd, which may already
1571                  * be 1 due to the zap_cursor_advance.
1572                  */
1573                 ASSERT(zc->zc_hash == 0);
1574                 hb = zap_hashbits(zc->zc_zap);
1575                 zc->zc_hash = zc->zc_serialized << (64 - hb);
1576                 zc->zc_cd += zc->zc_serialized >> hb;
1577                 if (zc->zc_cd >= zap_maxcd(zc->zc_zap)) /* corrupt serialized */
1578                         zc->zc_cd = 0;
1579         } else {
1580                 rw_enter(&zc->zc_zap->zap_rwlock, RW_READER);
1581         }
1582         if (!zc->zc_zap->zap_ismicro) {
1583                 err = fzap_cursor_retrieve(zc->zc_zap, zc, za);
1584         } else {
1585                 avl_index_t idx;
1586                 mzap_ent_t mze_tofind;
1587
1588                 mze_tofind.mze_hash = zc->zc_hash;
1589                 mze_tofind.mze_cd = zc->zc_cd;
1590
1591                 mzap_ent_t *mze =
1592                     avl_find(&zc->zc_zap->zap_m.zap_avl, &mze_tofind, &idx);
1593                 if (mze == NULL) {
1594                         mze = avl_nearest(&zc->zc_zap->zap_m.zap_avl,
1595                             idx, AVL_AFTER);
1596                 }
1597                 if (mze) {
1598                         mzap_ent_phys_t *mzep = MZE_PHYS(zc->zc_zap, mze);
1599                         ASSERT3U(mze->mze_cd, ==, mzep->mze_cd);
1600                         za->za_normalization_conflict =
1601                             mzap_normalization_conflict(zc->zc_zap, NULL, mze);
1602                         za->za_integer_length = 8;
1603                         za->za_num_integers = 1;
1604                         za->za_first_integer = mzep->mze_value;
1605                         (void) strlcpy(za->za_name, mzep->mze_name,
1606                             sizeof (za->za_name));
1607                         zc->zc_hash = mze->mze_hash;
1608                         zc->zc_cd = mze->mze_cd;
1609                         err = 0;
1610                 } else {
1611                         zc->zc_hash = -1ULL;
1612                         err = SET_ERROR(ENOENT);
1613                 }
1614         }
1615         rw_exit(&zc->zc_zap->zap_rwlock);
1616         return (err);
1617 }
1618
1619 void
1620 zap_cursor_advance(zap_cursor_t *zc)
1621 {
1622         if (zc->zc_hash == -1ULL)
1623                 return;
1624         zc->zc_cd++;
1625 }
1626
1627 int
1628 zap_get_stats(objset_t *os, uint64_t zapobj, zap_stats_t *zs)
1629 {
1630         zap_t *zap;
1631
1632         int err =
1633             zap_lockdir(os, zapobj, NULL, RW_READER, TRUE, FALSE, FTAG, &zap);
1634         if (err != 0)
1635                 return (err);
1636
1637         memset(zs, 0, sizeof (zap_stats_t));
1638
1639         if (zap->zap_ismicro) {
1640                 zs->zs_blocksize = zap->zap_dbuf->db_size;
1641                 zs->zs_num_entries = zap->zap_m.zap_num_entries;
1642                 zs->zs_num_blocks = 1;
1643         } else {
1644                 fzap_get_stats(zap, zs);
1645         }
1646         zap_unlockdir(zap, FTAG);
1647         return (0);
1648 }
1649
1650 #if defined(_KERNEL)
1651 EXPORT_SYMBOL(zap_create);
1652 EXPORT_SYMBOL(zap_create_dnsize);
1653 EXPORT_SYMBOL(zap_create_norm);
1654 EXPORT_SYMBOL(zap_create_norm_dnsize);
1655 EXPORT_SYMBOL(zap_create_flags);
1656 EXPORT_SYMBOL(zap_create_flags_dnsize);
1657 EXPORT_SYMBOL(zap_create_claim);
1658 EXPORT_SYMBOL(zap_create_claim_norm);
1659 EXPORT_SYMBOL(zap_create_claim_norm_dnsize);
1660 EXPORT_SYMBOL(zap_create_hold);
1661 EXPORT_SYMBOL(zap_destroy);
1662 EXPORT_SYMBOL(zap_lookup);
1663 EXPORT_SYMBOL(zap_lookup_by_dnode);
1664 EXPORT_SYMBOL(zap_lookup_norm);
1665 EXPORT_SYMBOL(zap_lookup_uint64);
1666 EXPORT_SYMBOL(zap_contains);
1667 EXPORT_SYMBOL(zap_prefetch);
1668 EXPORT_SYMBOL(zap_prefetch_uint64);
1669 EXPORT_SYMBOL(zap_add);
1670 EXPORT_SYMBOL(zap_add_by_dnode);
1671 EXPORT_SYMBOL(zap_add_uint64);
1672 EXPORT_SYMBOL(zap_update);
1673 EXPORT_SYMBOL(zap_update_uint64);
1674 EXPORT_SYMBOL(zap_length);
1675 EXPORT_SYMBOL(zap_length_uint64);
1676 EXPORT_SYMBOL(zap_remove);
1677 EXPORT_SYMBOL(zap_remove_by_dnode);
1678 EXPORT_SYMBOL(zap_remove_norm);
1679 EXPORT_SYMBOL(zap_remove_uint64);
1680 EXPORT_SYMBOL(zap_count);
1681 EXPORT_SYMBOL(zap_value_search);
1682 EXPORT_SYMBOL(zap_join);
1683 EXPORT_SYMBOL(zap_join_increment);
1684 EXPORT_SYMBOL(zap_add_int);
1685 EXPORT_SYMBOL(zap_remove_int);
1686 EXPORT_SYMBOL(zap_lookup_int);
1687 EXPORT_SYMBOL(zap_increment_int);
1688 EXPORT_SYMBOL(zap_add_int_key);
1689 EXPORT_SYMBOL(zap_lookup_int_key);
1690 EXPORT_SYMBOL(zap_increment);
1691 EXPORT_SYMBOL(zap_cursor_init);
1692 EXPORT_SYMBOL(zap_cursor_fini);
1693 EXPORT_SYMBOL(zap_cursor_retrieve);
1694 EXPORT_SYMBOL(zap_cursor_advance);
1695 EXPORT_SYMBOL(zap_cursor_serialize);
1696 EXPORT_SYMBOL(zap_cursor_init_serialized);
1697 EXPORT_SYMBOL(zap_get_stats);
1698 #endif