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     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, 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, void *tag, zap_t **zapp)
 583 {
 584         dmu_buf_t *db;
 585
 586         int err = dmu_buf_hold_by_dnode(dn, 0, tag, &db, DMU_READ_NO_PREFETCH);
 587         if (err != 0) {
 588                 return (err);
 589         }
 590 #ifdef ZFS_DEBUG
 591         {
 592                 dmu_object_info_t doi;
 593                 dmu_object_info_from_db(db, &doi);
 594                 ASSERT3U(DMU_OT_BYTESWAP(doi.doi_type), ==, DMU_BSWAP_ZAP);
 595         }
 596 #endif
 597
 598         err = zap_lockdir_impl(db, tag, tx, lti, fatreader, adding, zapp);
 599         if (err != 0) {
 600                 dmu_buf_rele(db, tag);
 601         }
 602         return (err);
 603 }
 604
 605 int
 606 zap_lockdir(objset_t *os, uint64_t obj, dmu_tx_t *tx,
 607     krw_t lti, boolean_t fatreader, boolean_t adding, void *tag, zap_t **zapp)
 608 {
 609         dmu_buf_t *db;
 610
 611         int err = dmu_buf_hold(os, obj, 0, tag, &db, DMU_READ_NO_PREFETCH);
 612         if (err != 0)
 613                 return (err);
 614 #ifdef ZFS_DEBUG
 615         {
 616                 dmu_object_info_t doi;
 617                 dmu_object_info_from_db(db, &doi);
 618                 ASSERT3U(DMU_OT_BYTESWAP(doi.doi_type), ==, DMU_BSWAP_ZAP);
 619         }
 620 #endif
 621         err = zap_lockdir_impl(db, tag, tx, lti, fatreader, adding, zapp);
 622         if (err != 0)
 623                 dmu_buf_rele(db, tag);
 624         return (err);
 625 }
 626
 627 void
 628 zap_unlockdir(zap_t *zap, void *tag)
 629 {
 630         rw_exit(&zap->zap_rwlock);
 631         dmu_buf_rele(zap->zap_dbuf, tag);
 632 }
 633
 634 static int
 635 mzap_upgrade(zap_t **zapp, void *tag, dmu_tx_t *tx, zap_flags_t flags)
 636 {
 637         int err = 0;
 638         zap_t *zap = *zapp;
 639
 640         ASSERT(RW_WRITE_HELD(&zap->zap_rwlock));
 641
 642         int sz = zap->zap_dbuf->db_size;
 643         mzap_phys_t *mzp = vmem_alloc(sz, KM_SLEEP);
 644         memcpy(mzp, zap->zap_dbuf->db_data, sz);
 645         int nchunks = zap->zap_m.zap_num_chunks;
 646
 647         if (!flags) {
 648                 err = dmu_object_set_blocksize(zap->zap_objset, zap->zap_object,
 649                     1ULL << fzap_default_block_shift, 0, tx);
 650                 if (err != 0) {
 651                         vmem_free(mzp, sz);
 652                         return (err);
 653                 }
 654         }
 655
 656         dprintf("upgrading obj=%llu with %u chunks\n",
 657             (u_longlong_t)zap->zap_object, nchunks);
 658         /* XXX destroy the avl later, so we can use the stored hash value */
 659         mze_destroy(zap);
 660
 661         fzap_upgrade(zap, tx, flags);
 662
 663         for (int i = 0; i < nchunks; i++) {
 664                 mzap_ent_phys_t *mze = &mzp->mz_chunk[i];
 665                 if (mze->mze_name[0] == 0)
 666                         continue;
 667                 dprintf("adding %s=%llu\n",
 668                     mze->mze_name, (u_longlong_t)mze->mze_value);
 669                 zap_name_t *zn = zap_name_alloc(zap, mze->mze_name, 0);
 670                 /* If we fail here, we would end up losing entries */
 671                 VERIFY0(fzap_add_cd(zn, 8, 1, &mze->mze_value, mze->mze_cd,
 672                     tag, tx));
 673                 zap = zn->zn_zap;       /* fzap_add_cd() may change zap */
 674                 zap_name_free(zn);
 675         }
 676         vmem_free(mzp, sz);
 677         *zapp = zap;
 678         return (0);
 679 }
 680
 681 /*
 682  * The "normflags" determine the behavior of the matchtype_t which is
 683  * passed to zap_lookup_norm().  Names which have the same normalized
 684  * version will be stored with the same hash value, and therefore we can
 685  * perform normalization-insensitive lookups.  We can be Unicode form-
 686  * insensitive and/or case-insensitive.  The following flags are valid for
 687  * "normflags":
 688  *
 689  * U8_TEXTPREP_NFC
 690  * U8_TEXTPREP_NFD
 691  * U8_TEXTPREP_NFKC
 692  * U8_TEXTPREP_NFKD
 693  * U8_TEXTPREP_TOUPPER
 694  *
 695  * The *_NF* (Normalization Form) flags are mutually exclusive; at most one
 696  * of them may be supplied.
 697  */
 698 void
 699 mzap_create_impl(dnode_t *dn, int normflags, zap_flags_t flags, dmu_tx_t *tx)
 700 {
 701         dmu_buf_t *db;
 702
 703         VERIFY0(dmu_buf_hold_by_dnode(dn, 0, FTAG, &db, DMU_READ_NO_PREFETCH));
 704
 705         dmu_buf_will_dirty(db, tx);
 706         mzap_phys_t *zp = db->db_data;
 707         zp->mz_block_type = ZBT_MICRO;
 708         zp->mz_salt =
 709             ((uintptr_t)db ^ (uintptr_t)tx ^ (dn->dn_object << 1)) | 1ULL;
 710         zp->mz_normflags = normflags;
 711
 712         if (flags != 0) {
 713                 zap_t *zap;
 714                 /* Only fat zap supports flags; upgrade immediately. */
 715                 VERIFY0(zap_lockdir_impl(db, FTAG, tx, RW_WRITER,
 716                     B_FALSE, B_FALSE, &zap));
 717                 VERIFY0(mzap_upgrade(&zap, FTAG, tx, flags));
 718                 zap_unlockdir(zap, FTAG);
 719         } else {
 720                 dmu_buf_rele(db, FTAG);
 721         }
 722 }
 723
 724 static uint64_t
 725 zap_create_impl(objset_t *os, int normflags, zap_flags_t flags,
 726     dmu_object_type_t ot, int leaf_blockshift, int indirect_blockshift,
 727     dmu_object_type_t bonustype, int bonuslen, int dnodesize,
 728     dnode_t **allocated_dnode, void *tag, dmu_tx_t *tx)
 729 {
 730         uint64_t obj;
 731
 732         ASSERT3U(DMU_OT_BYTESWAP(ot), ==, DMU_BSWAP_ZAP);
 733
 734         if (allocated_dnode == NULL) {
 735                 dnode_t *dn;
 736                 obj = dmu_object_alloc_hold(os, ot, 1ULL << leaf_blockshift,
 737                     indirect_blockshift, bonustype, bonuslen, dnodesize,
 738                     &dn, FTAG, tx);
 739                 mzap_create_impl(dn, normflags, flags, tx);
 740                 dnode_rele(dn, FTAG);
 741         } else {
 742                 obj = dmu_object_alloc_hold(os, ot, 1ULL << leaf_blockshift,
 743                     indirect_blockshift, bonustype, bonuslen, dnodesize,
 744                     allocated_dnode, tag, tx);
 745                 mzap_create_impl(*allocated_dnode, normflags, flags, tx);
 746         }
 747
 748         return (obj);
 749 }
 750
 751 int
 752 zap_create_claim(objset_t *os, uint64_t obj, dmu_object_type_t ot,
 753     dmu_object_type_t bonustype, int bonuslen, dmu_tx_t *tx)
 754 {
 755         return (zap_create_claim_dnsize(os, obj, ot, bonustype, bonuslen,
 756             0, tx));
 757 }
 758
 759 int
 760 zap_create_claim_dnsize(objset_t *os, uint64_t obj, dmu_object_type_t ot,
 761     dmu_object_type_t bonustype, int bonuslen, int dnodesize, dmu_tx_t *tx)
 762 {
 763         return (zap_create_claim_norm_dnsize(os, obj,
 764             0, ot, bonustype, bonuslen, dnodesize, tx));
 765 }
 766
 767 int
 768 zap_create_claim_norm(objset_t *os, uint64_t obj, int normflags,
 769     dmu_object_type_t ot,
 770     dmu_object_type_t bonustype, int bonuslen, dmu_tx_t *tx)
 771 {
 772         return (zap_create_claim_norm_dnsize(os, obj, normflags, ot, bonustype,
 773             bonuslen, 0, tx));
 774 }
 775
 776 int
 777 zap_create_claim_norm_dnsize(objset_t *os, uint64_t obj, int normflags,
 778     dmu_object_type_t ot, dmu_object_type_t bonustype, int bonuslen,
 779     int dnodesize, dmu_tx_t *tx)
 780 {
 781         dnode_t *dn;
 782         int error;
 783
 784         ASSERT3U(DMU_OT_BYTESWAP(ot), ==, DMU_BSWAP_ZAP);
 785         error = dmu_object_claim_dnsize(os, obj, ot, 0, bonustype, bonuslen,
 786             dnodesize, tx);
 787         if (error != 0)
 788                 return (error);
 789
 790         error = dnode_hold(os, obj, FTAG, &dn);
 791         if (error != 0)
 792                 return (error);
 793
 794         mzap_create_impl(dn, normflags, 0, tx);
 795
 796         dnode_rele(dn, FTAG);
 797
 798         return (0);
 799 }
 800
 801 uint64_t
 802 zap_create(objset_t *os, dmu_object_type_t ot,
 803     dmu_object_type_t bonustype, int bonuslen, dmu_tx_t *tx)
 804 {
 805         return (zap_create_norm(os, 0, ot, bonustype, bonuslen, tx));
 806 }
 807
 808 uint64_t
 809 zap_create_dnsize(objset_t *os, dmu_object_type_t ot,
 810     dmu_object_type_t bonustype, int bonuslen, int dnodesize, dmu_tx_t *tx)
 811 {
 812         return (zap_create_norm_dnsize(os, 0, ot, bonustype, bonuslen,
 813             dnodesize, tx));
 814 }
 815
 816 uint64_t
 817 zap_create_norm(objset_t *os, int normflags, dmu_object_type_t ot,
 818     dmu_object_type_t bonustype, int bonuslen, dmu_tx_t *tx)
 819 {
 820         return (zap_create_norm_dnsize(os, normflags, ot, bonustype, bonuslen,
 821             0, tx));
 822 }
 823
 824 uint64_t
 825 zap_create_norm_dnsize(objset_t *os, int normflags, dmu_object_type_t ot,
 826     dmu_object_type_t bonustype, int bonuslen, int dnodesize, dmu_tx_t *tx)
 827 {
 828         return (zap_create_impl(os, normflags, 0, ot, 0, 0,
 829             bonustype, bonuslen, dnodesize, NULL, NULL, tx));
 830 }
 831
 832 uint64_t
 833 zap_create_flags(objset_t *os, int normflags, zap_flags_t flags,
 834     dmu_object_type_t ot, int leaf_blockshift, int indirect_blockshift,
 835     dmu_object_type_t bonustype, int bonuslen, dmu_tx_t *tx)
 836 {
 837         return (zap_create_flags_dnsize(os, normflags, flags, ot,
 838             leaf_blockshift, indirect_blockshift, bonustype, bonuslen, 0, tx));
 839 }
 840
 841 uint64_t
 842 zap_create_flags_dnsize(objset_t *os, int normflags, zap_flags_t flags,
 843     dmu_object_type_t ot, int leaf_blockshift, int indirect_blockshift,
 844     dmu_object_type_t bonustype, int bonuslen, int dnodesize, dmu_tx_t *tx)
 845 {
 846         return (zap_create_impl(os, normflags, flags, ot, leaf_blockshift,
 847             indirect_blockshift, bonustype, bonuslen, dnodesize, NULL, NULL,
 848             tx));
 849 }
 850
 851 /*
 852  * Create a zap object and return a pointer to the newly allocated dnode via
 853  * the allocated_dnode argument.  The returned dnode will be held and the
 854  * caller is responsible for releasing the hold by calling dnode_rele().
 855  */
 856 uint64_t
 857 zap_create_hold(objset_t *os, int normflags, zap_flags_t flags,
 858     dmu_object_type_t ot, int leaf_blockshift, int indirect_blockshift,
 859     dmu_object_type_t bonustype, int bonuslen, int dnodesize,
 860     dnode_t **allocated_dnode, void *tag, dmu_tx_t *tx)
 861 {
 862         return (zap_create_impl(os, normflags, flags, ot, leaf_blockshift,
 863             indirect_blockshift, bonustype, bonuslen, dnodesize,
 864             allocated_dnode, tag, tx));
 865 }
 866
 867 int
 868 zap_destroy(objset_t *os, uint64_t zapobj, dmu_tx_t *tx)
 869 {
 870         /*
 871          * dmu_object_free will free the object number and free the
 872          * data.  Freeing the data will cause our pageout function to be
 873          * called, which will destroy our data (zap_leaf_t's and zap_t).
 874          */
 875
 876         return (dmu_object_free(os, zapobj, tx));
 877 }
 878
 879 void
 880 zap_evict_sync(void *dbu)
 881 {
 882         zap_t *zap = dbu;
 883
 884         rw_destroy(&zap->zap_rwlock);
 885
 886         if (zap->zap_ismicro)
 887                 mze_destroy(zap);
 888         else
 889                 mutex_destroy(&zap->zap_f.zap_num_entries_mtx);
 890
 891         kmem_free(zap, sizeof (zap_t));
 892 }
 893
 894 int
 895 zap_count(objset_t *os, uint64_t zapobj, uint64_t *count)
 896 {
 897         zap_t *zap;
 898
 899         int err =
 900             zap_lockdir(os, zapobj, NULL, RW_READER, TRUE, FALSE, FTAG, &zap);
 901         if (err != 0)
 902                 return (err);
 903         if (!zap->zap_ismicro) {
 904                 err = fzap_count(zap, count);
 905         } else {
 906                 *count = zap->zap_m.zap_num_entries;
 907         }
 908         zap_unlockdir(zap, FTAG);
 909         return (err);
 910 }
 911
 912 /*
 913  * zn may be NULL; if not specified, it will be computed if needed.
 914  * See also the comment above zap_entry_normalization_conflict().
 915  */
 916 static boolean_t
 917 mzap_normalization_conflict(zap_t *zap, zap_name_t *zn, mzap_ent_t *mze)
 918 {
 919         int direction = AVL_BEFORE;
 920         boolean_t allocdzn = B_FALSE;
 921
 922         if (zap->zap_normflags == 0)
 923                 return (B_FALSE);
 924
 925 again:
 926         for (mzap_ent_t *other = avl_walk(&zap->zap_m.zap_avl, mze, direction);
 927             other && other->mze_hash == mze->mze_hash;
 928             other = avl_walk(&zap->zap_m.zap_avl, other, direction)) {
 929
 930                 if (zn == NULL) {
 931                         zn = zap_name_alloc(zap, MZE_PHYS(zap, mze)->mze_name,
 932                             MT_NORMALIZE);
 933                         allocdzn = B_TRUE;
 934                 }
 935                 if (zap_match(zn, MZE_PHYS(zap, other)->mze_name)) {
 936                         if (allocdzn)
 937                                 zap_name_free(zn);
 938                         return (B_TRUE);
 939                 }
 940         }
 941
 942         if (direction == AVL_BEFORE) {
 943                 direction = AVL_AFTER;
 944                 goto again;
 945         }
 946
 947         if (allocdzn)
 948                 zap_name_free(zn);
 949         return (B_FALSE);
 950 }
 951
 952 /*
 953  * Routines for manipulating attributes.
 954  */
 955
 956 int
 957 zap_lookup(objset_t *os, uint64_t zapobj, const char *name,
 958     uint64_t integer_size, uint64_t num_integers, void *buf)
 959 {
 960         return (zap_lookup_norm(os, zapobj, name, integer_size,
 961             num_integers, buf, 0, NULL, 0, NULL));
 962 }
 963
 964 static int
 965 zap_lookup_impl(zap_t *zap, const char *name,
 966     uint64_t integer_size, uint64_t num_integers, void *buf,
 967     matchtype_t mt, char *realname, int rn_len,
 968     boolean_t *ncp)
 969 {
 970         int err = 0;
 971
 972         zap_name_t *zn = zap_name_alloc(zap, name, mt);
 973         if (zn == NULL)
 974                 return (SET_ERROR(ENOTSUP));
 975
 976         if (!zap->zap_ismicro) {
 977                 err = fzap_lookup(zn, integer_size, num_integers, buf,
 978                     realname, rn_len, ncp);
 979         } else {
 980                 mzap_ent_t *mze = mze_find(zn);
 981                 if (mze == NULL) {
 982                         err = SET_ERROR(ENOENT);
 983                 } else {
 984                         if (num_integers < 1) {
 985                                 err = SET_ERROR(EOVERFLOW);
 986                         } else if (integer_size != 8) {
 987                                 err = SET_ERROR(EINVAL);
 988                         } else {
 989                                 *(uint64_t *)buf =
 990                                     MZE_PHYS(zap, mze)->mze_value;
 991                                 (void) strlcpy(realname,
 992                                     MZE_PHYS(zap, mze)->mze_name, rn_len);
 993                                 if (ncp) {
 994                                         *ncp = mzap_normalization_conflict(zap,
 995                                             zn, mze);
 996                                 }
 997                         }
 998                 }
 999         }
1000         zap_name_free(zn);
1001         return (err);
1002 }
1003
1004 int
1005 zap_lookup_norm(objset_t *os, uint64_t zapobj, const char *name,
1006     uint64_t integer_size, uint64_t num_integers, void *buf,
1007     matchtype_t mt, char *realname, int rn_len,
1008     boolean_t *ncp)
1009 {
1010         zap_t *zap;
1011
1012         int err =
1013             zap_lockdir(os, zapobj, NULL, RW_READER, TRUE, FALSE, FTAG, &zap);
1014         if (err != 0)
1015                 return (err);
1016         err = zap_lookup_impl(zap, name, integer_size,
1017             num_integers, buf, mt, realname, rn_len, ncp);
1018         zap_unlockdir(zap, FTAG);
1019         return (err);
1020 }
1021
1022 int
1023 zap_prefetch(objset_t *os, uint64_t zapobj, const char *name)
1024 {
1025         zap_t *zap;
1026         int err;
1027         zap_name_t *zn;
1028
1029         err = zap_lockdir(os, zapobj, NULL, RW_READER, TRUE, FALSE, FTAG, &zap);
1030         if (err)
1031                 return (err);
1032         zn = zap_name_alloc(zap, name, 0);
1033         if (zn == NULL) {
1034                 zap_unlockdir(zap, FTAG);
1035                 return (SET_ERROR(ENOTSUP));
1036         }
1037
1038         fzap_prefetch(zn);
1039         zap_name_free(zn);
1040         zap_unlockdir(zap, FTAG);
1041         return (err);
1042 }
1043
1044 int
1045 zap_lookup_by_dnode(dnode_t *dn, const char *name,
1046     uint64_t integer_size, uint64_t num_integers, void *buf)
1047 {
1048         return (zap_lookup_norm_by_dnode(dn, name, integer_size,
1049             num_integers, buf, 0, NULL, 0, NULL));
1050 }
1051
1052 int
1053 zap_lookup_norm_by_dnode(dnode_t *dn, const char *name,
1054     uint64_t integer_size, uint64_t num_integers, void *buf,
1055     matchtype_t mt, char *realname, int rn_len,
1056     boolean_t *ncp)
1057 {
1058         zap_t *zap;
1059
1060         int err = zap_lockdir_by_dnode(dn, NULL, RW_READER, TRUE, FALSE,
1061             FTAG, &zap);
1062         if (err != 0)
1063                 return (err);
1064         err = zap_lookup_impl(zap, name, integer_size,
1065             num_integers, buf, mt, realname, rn_len, ncp);
1066         zap_unlockdir(zap, FTAG);
1067         return (err);
1068 }
1069
1070 int
1071 zap_prefetch_uint64(objset_t *os, uint64_t zapobj, const uint64_t *key,
1072     int key_numints)
1073 {
1074         zap_t *zap;
1075
1076         int err =
1077             zap_lockdir(os, zapobj, NULL, RW_READER, TRUE, FALSE, FTAG, &zap);
1078         if (err != 0)
1079                 return (err);
1080         zap_name_t *zn = zap_name_alloc_uint64(zap, key, key_numints);
1081         if (zn == NULL) {
1082                 zap_unlockdir(zap, FTAG);
1083                 return (SET_ERROR(ENOTSUP));
1084         }
1085
1086         fzap_prefetch(zn);
1087         zap_name_free(zn);
1088         zap_unlockdir(zap, FTAG);
1089         return (err);
1090 }
1091
1092 int
1093 zap_lookup_uint64(objset_t *os, uint64_t zapobj, const uint64_t *key,
1094     int key_numints, uint64_t integer_size, uint64_t num_integers, void *buf)
1095 {
1096         zap_t *zap;
1097
1098         int err =
1099             zap_lockdir(os, zapobj, NULL, RW_READER, TRUE, FALSE, FTAG, &zap);
1100         if (err != 0)
1101                 return (err);
1102         zap_name_t *zn = zap_name_alloc_uint64(zap, key, key_numints);
1103         if (zn == NULL) {
1104                 zap_unlockdir(zap, FTAG);
1105                 return (SET_ERROR(ENOTSUP));
1106         }
1107
1108         err = fzap_lookup(zn, integer_size, num_integers, buf,
1109             NULL, 0, NULL);
1110         zap_name_free(zn);
1111         zap_unlockdir(zap, FTAG);
1112         return (err);
1113 }
1114
1115 int
1116 zap_contains(objset_t *os, uint64_t zapobj, const char *name)
1117 {
1118         int err = zap_lookup_norm(os, zapobj, name, 0,
1119             0, NULL, 0, NULL, 0, NULL);
1120         if (err == EOVERFLOW || err == EINVAL)
1121                 err = 0; /* found, but skipped reading the value */
1122         return (err);
1123 }
1124
1125 int
1126 zap_length(objset_t *os, uint64_t zapobj, const char *name,
1127     uint64_t *integer_size, uint64_t *num_integers)
1128 {
1129         zap_t *zap;
1130
1131         int err =
1132             zap_lockdir(os, zapobj, NULL, RW_READER, TRUE, FALSE, FTAG, &zap);
1133         if (err != 0)
1134                 return (err);
1135         zap_name_t *zn = zap_name_alloc(zap, name, 0);
1136         if (zn == NULL) {
1137                 zap_unlockdir(zap, FTAG);
1138                 return (SET_ERROR(ENOTSUP));
1139         }
1140         if (!zap->zap_ismicro) {
1141                 err = fzap_length(zn, integer_size, num_integers);
1142         } else {
1143                 mzap_ent_t *mze = mze_find(zn);
1144                 if (mze == NULL) {
1145                         err = SET_ERROR(ENOENT);
1146                 } else {
1147                         if (integer_size)
1148                                 *integer_size = 8;
1149                         if (num_integers)
1150                                 *num_integers = 1;
1151                 }
1152         }
1153         zap_name_free(zn);
1154         zap_unlockdir(zap, FTAG);
1155         return (err);
1156 }
1157
1158 int
1159 zap_length_uint64(objset_t *os, uint64_t zapobj, const uint64_t *key,
1160     int key_numints, uint64_t *integer_size, uint64_t *num_integers)
1161 {
1162         zap_t *zap;
1163
1164         int err =
1165             zap_lockdir(os, zapobj, NULL, RW_READER, TRUE, FALSE, FTAG, &zap);
1166         if (err != 0)
1167                 return (err);
1168         zap_name_t *zn = zap_name_alloc_uint64(zap, key, key_numints);
1169         if (zn == NULL) {
1170                 zap_unlockdir(zap, FTAG);
1171                 return (SET_ERROR(ENOTSUP));
1172         }
1173         err = fzap_length(zn, integer_size, num_integers);
1174         zap_name_free(zn);
1175         zap_unlockdir(zap, FTAG);
1176         return (err);
1177 }
1178
1179 static void
1180 mzap_addent(zap_name_t *zn, uint64_t value)
1181 {
1182         zap_t *zap = zn->zn_zap;
1183         int start = zap->zap_m.zap_alloc_next;
1184
1185         ASSERT(RW_WRITE_HELD(&zap->zap_rwlock));
1186
1187 #ifdef ZFS_DEBUG
1188         for (int i = 0; i < zap->zap_m.zap_num_chunks; i++) {
1189                 mzap_ent_phys_t *mze = &zap_m_phys(zap)->mz_chunk[i];
1190                 ASSERT(strcmp(zn->zn_key_orig, mze->mze_name) != 0);
1191         }
1192 #endif
1193
1194         uint32_t cd = mze_find_unused_cd(zap, zn->zn_hash);
1195         /* given the limited size of the microzap, this can't happen */
1196         ASSERT(cd < zap_maxcd(zap));
1197
1198 again:
1199         for (int i = start; i < zap->zap_m.zap_num_chunks; i++) {
1200                 mzap_ent_phys_t *mze = &zap_m_phys(zap)->mz_chunk[i];
1201                 if (mze->mze_name[0] == 0) {
1202                         mze->mze_value = value;
1203                         mze->mze_cd = cd;
1204                         (void) strlcpy(mze->mze_name, zn->zn_key_orig,
1205                             sizeof (mze->mze_name));
1206                         zap->zap_m.zap_num_entries++;
1207                         zap->zap_m.zap_alloc_next = i+1;
1208                         if (zap->zap_m.zap_alloc_next ==
1209                             zap->zap_m.zap_num_chunks)
1210                                 zap->zap_m.zap_alloc_next = 0;
1211                         mze_insert(zap, i, zn->zn_hash);
1212                         return;
1213                 }
1214         }
1215         if (start != 0) {
1216                 start = 0;
1217                 goto again;
1218         }
1219         cmn_err(CE_PANIC, "out of entries!");
1220 }
1221
1222 static int
1223 zap_add_impl(zap_t *zap, const char *key,
1224     int integer_size, uint64_t num_integers,
1225     const void *val, dmu_tx_t *tx, void *tag)
1226 {
1227         const uint64_t *intval = val;
1228         int err = 0;
1229
1230         zap_name_t *zn = zap_name_alloc(zap, key, 0);
1231         if (zn == NULL) {
1232                 zap_unlockdir(zap, tag);
1233                 return (SET_ERROR(ENOTSUP));
1234         }
1235         if (!zap->zap_ismicro) {
1236                 err = fzap_add(zn, integer_size, num_integers, val, tag, tx);
1237                 zap = zn->zn_zap;       /* fzap_add() may change zap */
1238         } else if (integer_size != 8 || num_integers != 1 ||
1239             strlen(key) >= MZAP_NAME_LEN ||
1240             !mze_canfit_fzap_leaf(zn, zn->zn_hash)) {
1241                 err = mzap_upgrade(&zn->zn_zap, tag, tx, 0);
1242                 if (err == 0) {
1243                         err = fzap_add(zn, integer_size, num_integers, val,
1244                             tag, tx);
1245                 }
1246                 zap = zn->zn_zap;       /* fzap_add() may change zap */
1247         } else {
1248                 if (mze_find(zn) != NULL) {
1249                         err = SET_ERROR(EEXIST);
1250                 } else {
1251                         mzap_addent(zn, *intval);
1252                 }
1253         }
1254         ASSERT(zap == zn->zn_zap);
1255         zap_name_free(zn);
1256         if (zap != NULL)        /* may be NULL if fzap_add() failed */
1257                 zap_unlockdir(zap, tag);
1258         return (err);
1259 }
1260
1261 int
1262 zap_add(objset_t *os, uint64_t zapobj, const char *key,
1263     int integer_size, uint64_t num_integers,
1264     const void *val, dmu_tx_t *tx)
1265 {
1266         zap_t *zap;
1267         int err;
1268
1269         err = zap_lockdir(os, zapobj, tx, RW_WRITER, TRUE, TRUE, FTAG, &zap);
1270         if (err != 0)
1271                 return (err);
1272         err = zap_add_impl(zap, key, integer_size, num_integers, val, tx, FTAG);
1273         /* zap_add_impl() calls zap_unlockdir() */
1274         return (err);
1275 }
1276
1277 int
1278 zap_add_by_dnode(dnode_t *dn, const char *key,
1279     int integer_size, uint64_t num_integers,
1280     const void *val, dmu_tx_t *tx)
1281 {
1282         zap_t *zap;
1283         int err;
1284
1285         err = zap_lockdir_by_dnode(dn, tx, RW_WRITER, TRUE, TRUE, FTAG, &zap);
1286         if (err != 0)
1287                 return (err);
1288         err = zap_add_impl(zap, key, integer_size, num_integers, val, tx, FTAG);
1289         /* zap_add_impl() calls zap_unlockdir() */
1290         return (err);
1291 }
1292
1293 int
1294 zap_add_uint64(objset_t *os, uint64_t zapobj, const uint64_t *key,
1295     int key_numints, int integer_size, uint64_t num_integers,
1296     const void *val, dmu_tx_t *tx)
1297 {
1298         zap_t *zap;
1299
1300         int err =
1301             zap_lockdir(os, zapobj, tx, RW_WRITER, TRUE, TRUE, FTAG, &zap);
1302         if (err != 0)
1303                 return (err);
1304         zap_name_t *zn = zap_name_alloc_uint64(zap, key, key_numints);
1305         if (zn == NULL) {
1306                 zap_unlockdir(zap, FTAG);
1307                 return (SET_ERROR(ENOTSUP));
1308         }
1309         err = fzap_add(zn, integer_size, num_integers, val, FTAG, tx);
1310         zap = zn->zn_zap;       /* fzap_add() may change zap */
1311         zap_name_free(zn);
1312         if (zap != NULL)        /* may be NULL if fzap_add() failed */
1313                 zap_unlockdir(zap, FTAG);
1314         return (err);
1315 }
1316
1317 int
1318 zap_update(objset_t *os, uint64_t zapobj, const char *name,
1319     int integer_size, uint64_t num_integers, const void *val, dmu_tx_t *tx)
1320 {
1321         zap_t *zap;
1322         const uint64_t *intval = val;
1323
1324         int err =
1325             zap_lockdir(os, zapobj, tx, RW_WRITER, TRUE, TRUE, FTAG, &zap);
1326         if (err != 0)
1327                 return (err);
1328         zap_name_t *zn = zap_name_alloc(zap, name, 0);
1329         if (zn == NULL) {
1330                 zap_unlockdir(zap, FTAG);
1331                 return (SET_ERROR(ENOTSUP));
1332         }
1333         if (!zap->zap_ismicro) {
1334                 err = fzap_update(zn, integer_size, num_integers, val,
1335                     FTAG, tx);
1336                 zap = zn->zn_zap;       /* fzap_update() may change zap */
1337         } else if (integer_size != 8 || num_integers != 1 ||
1338             strlen(name) >= MZAP_NAME_LEN) {
1339                 dprintf("upgrading obj %llu: intsz=%u numint=%llu name=%s\n",
1340                     (u_longlong_t)zapobj, integer_size,
1341                     (u_longlong_t)num_integers, name);
1342                 err = mzap_upgrade(&zn->zn_zap, FTAG, tx, 0);
1343                 if (err == 0) {
1344                         err = fzap_update(zn, integer_size, num_integers,
1345                             val, FTAG, tx);
1346                 }
1347                 zap = zn->zn_zap;       /* fzap_update() may change zap */
1348         } else {
1349                 mzap_ent_t *mze = mze_find(zn);
1350                 if (mze != NULL) {
1351                         MZE_PHYS(zap, mze)->mze_value = *intval;
1352                 } else {
1353                         mzap_addent(zn, *intval);
1354                 }
1355         }
1356         ASSERT(zap == zn->zn_zap);
1357         zap_name_free(zn);
1358         if (zap != NULL)        /* may be NULL if fzap_upgrade() failed */
1359                 zap_unlockdir(zap, FTAG);
1360         return (err);
1361 }
1362
1363 int
1364 zap_update_uint64(objset_t *os, uint64_t zapobj, const uint64_t *key,
1365     int key_numints,
1366     int integer_size, uint64_t num_integers, const void *val, dmu_tx_t *tx)
1367 {
1368         zap_t *zap;
1369
1370         int err =
1371             zap_lockdir(os, zapobj, tx, RW_WRITER, TRUE, TRUE, FTAG, &zap);
1372         if (err != 0)
1373                 return (err);
1374         zap_name_t *zn = zap_name_alloc_uint64(zap, key, key_numints);
1375         if (zn == NULL) {
1376                 zap_unlockdir(zap, FTAG);
1377                 return (SET_ERROR(ENOTSUP));
1378         }
1379         err = fzap_update(zn, integer_size, num_integers, val, FTAG, tx);
1380         zap = zn->zn_zap;       /* fzap_update() may change zap */
1381         zap_name_free(zn);
1382         if (zap != NULL)        /* may be NULL if fzap_upgrade() failed */
1383                 zap_unlockdir(zap, FTAG);
1384         return (err);
1385 }
1386
1387 int
1388 zap_remove(objset_t *os, uint64_t zapobj, const char *name, dmu_tx_t *tx)
1389 {
1390         return (zap_remove_norm(os, zapobj, name, 0, tx));
1391 }
1392
1393 static int
1394 zap_remove_impl(zap_t *zap, const char *name,
1395     matchtype_t mt, dmu_tx_t *tx)
1396 {
1397         int err = 0;
1398
1399         zap_name_t *zn = zap_name_alloc(zap, name, mt);
1400         if (zn == NULL)
1401                 return (SET_ERROR(ENOTSUP));
1402         if (!zap->zap_ismicro) {
1403                 err = fzap_remove(zn, tx);
1404         } else {
1405                 mzap_ent_t *mze = mze_find(zn);
1406                 if (mze == NULL) {
1407                         err = SET_ERROR(ENOENT);
1408                 } else {
1409                         zap->zap_m.zap_num_entries--;
1410                         memset(&zap_m_phys(zap)->mz_chunk[mze->mze_chunkid], 0,
1411                             sizeof (mzap_ent_phys_t));
1412                         mze_remove(zap, mze);
1413                 }
1414         }
1415         zap_name_free(zn);
1416         return (err);
1417 }
1418
1419 int
1420 zap_remove_norm(objset_t *os, uint64_t zapobj, const char *name,
1421     matchtype_t mt, dmu_tx_t *tx)
1422 {
1423         zap_t *zap;
1424         int err;
1425
1426         err = zap_lockdir(os, zapobj, tx, RW_WRITER, TRUE, FALSE, FTAG, &zap);
1427         if (err)
1428                 return (err);
1429         err = zap_remove_impl(zap, name, mt, tx);
1430         zap_unlockdir(zap, FTAG);
1431         return (err);
1432 }
1433
1434 int
1435 zap_remove_by_dnode(dnode_t *dn, const char *name, dmu_tx_t *tx)
1436 {
1437         zap_t *zap;
1438         int err;
1439
1440         err = zap_lockdir_by_dnode(dn, tx, RW_WRITER, TRUE, FALSE, FTAG, &zap);
1441         if (err)
1442                 return (err);
1443         err = zap_remove_impl(zap, name, 0, tx);
1444         zap_unlockdir(zap, FTAG);
1445         return (err);
1446 }
1447
1448 int
1449 zap_remove_uint64(objset_t *os, uint64_t zapobj, const uint64_t *key,
1450     int key_numints, dmu_tx_t *tx)
1451 {
1452         zap_t *zap;
1453
1454         int err =
1455             zap_lockdir(os, zapobj, tx, RW_WRITER, TRUE, FALSE, FTAG, &zap);
1456         if (err != 0)
1457                 return (err);
1458         zap_name_t *zn = zap_name_alloc_uint64(zap, key, key_numints);
1459         if (zn == NULL) {
1460                 zap_unlockdir(zap, FTAG);
1461                 return (SET_ERROR(ENOTSUP));
1462         }
1463         err = fzap_remove(zn, tx);
1464         zap_name_free(zn);
1465         zap_unlockdir(zap, FTAG);
1466         return (err);
1467 }
1468
1469 /*
1470  * Routines for iterating over the attributes.
1471  */
1472
1473 static void
1474 zap_cursor_init_impl(zap_cursor_t *zc, objset_t *os, uint64_t zapobj,
1475     uint64_t serialized, boolean_t prefetch)
1476 {
1477         zc->zc_objset = os;
1478         zc->zc_zap = NULL;
1479         zc->zc_leaf = NULL;
1480         zc->zc_zapobj = zapobj;
1481         zc->zc_serialized = serialized;
1482         zc->zc_hash = 0;
1483         zc->zc_cd = 0;
1484         zc->zc_prefetch = prefetch;
1485 }
1486 void
1487 zap_cursor_init_serialized(zap_cursor_t *zc, objset_t *os, uint64_t zapobj,
1488     uint64_t serialized)
1489 {
1490         zap_cursor_init_impl(zc, os, zapobj, serialized, B_TRUE);
1491 }
1492
1493 /*
1494  * Initialize a cursor at the beginning of the ZAP object.  The entire
1495  * ZAP object will be prefetched.
1496  */
1497 void
1498 zap_cursor_init(zap_cursor_t *zc, objset_t *os, uint64_t zapobj)
1499 {
1500         zap_cursor_init_impl(zc, os, zapobj, 0, B_TRUE);
1501 }
1502
1503 /*
1504  * Initialize a cursor at the beginning, but request that we not prefetch
1505  * the entire ZAP object.
1506  */
1507 void
1508 zap_cursor_init_noprefetch(zap_cursor_t *zc, objset_t *os, uint64_t zapobj)
1509 {
1510         zap_cursor_init_impl(zc, os, zapobj, 0, B_FALSE);
1511 }
1512
1513 void
1514 zap_cursor_fini(zap_cursor_t *zc)
1515 {
1516         if (zc->zc_zap) {
1517                 rw_enter(&zc->zc_zap->zap_rwlock, RW_READER);
1518                 zap_unlockdir(zc->zc_zap, NULL);
1519                 zc->zc_zap = NULL;
1520         }
1521         if (zc->zc_leaf) {
1522                 rw_enter(&zc->zc_leaf->l_rwlock, RW_READER);
1523                 zap_put_leaf(zc->zc_leaf);
1524                 zc->zc_leaf = NULL;
1525         }
1526         zc->zc_objset = NULL;
1527 }
1528
1529 uint64_t
1530 zap_cursor_serialize(zap_cursor_t *zc)
1531 {
1532         if (zc->zc_hash == -1ULL)
1533                 return (-1ULL);
1534         if (zc->zc_zap == NULL)
1535                 return (zc->zc_serialized);
1536         ASSERT((zc->zc_hash & zap_maxcd(zc->zc_zap)) == 0);
1537         ASSERT(zc->zc_cd < zap_maxcd(zc->zc_zap));
1538
1539         /*
1540          * We want to keep the high 32 bits of the cursor zero if we can, so
1541          * that 32-bit programs can access this.  So usually use a small
1542          * (28-bit) hash value so we can fit 4 bits of cd into the low 32-bits
1543          * of the cursor.
1544          *
1545          * [ collision differentiator | zap_hashbits()-bit hash value ]
1546          */
1547         return ((zc->zc_hash >> (64 - zap_hashbits(zc->zc_zap))) |
1548             ((uint64_t)zc->zc_cd << zap_hashbits(zc->zc_zap)));
1549 }
1550
1551 int
1552 zap_cursor_retrieve(zap_cursor_t *zc, zap_attribute_t *za)
1553 {
1554         int err;
1555
1556         if (zc->zc_hash == -1ULL)
1557                 return (SET_ERROR(ENOENT));
1558
1559         if (zc->zc_zap == NULL) {
1560                 int hb;
1561                 err = zap_lockdir(zc->zc_objset, zc->zc_zapobj, NULL,
1562                     RW_READER, TRUE, FALSE, NULL, &zc->zc_zap);
1563                 if (err != 0)
1564                         return (err);
1565
1566                 /*
1567                  * To support zap_cursor_init_serialized, advance, retrieve,
1568                  * we must add to the existing zc_cd, which may already
1569                  * be 1 due to the zap_cursor_advance.
1570                  */
1571                 ASSERT(zc->zc_hash == 0);
1572                 hb = zap_hashbits(zc->zc_zap);
1573                 zc->zc_hash = zc->zc_serialized << (64 - hb);
1574                 zc->zc_cd += zc->zc_serialized >> hb;
1575                 if (zc->zc_cd >= zap_maxcd(zc->zc_zap)) /* corrupt serialized */
1576                         zc->zc_cd = 0;
1577         } else {
1578                 rw_enter(&zc->zc_zap->zap_rwlock, RW_READER);
1579         }
1580         if (!zc->zc_zap->zap_ismicro) {
1581                 err = fzap_cursor_retrieve(zc->zc_zap, zc, za);
1582         } else {
1583                 avl_index_t idx;
1584                 mzap_ent_t mze_tofind;
1585
1586                 mze_tofind.mze_hash = zc->zc_hash;
1587                 mze_tofind.mze_cd = zc->zc_cd;
1588
1589                 mzap_ent_t *mze =
1590                     avl_find(&zc->zc_zap->zap_m.zap_avl, &mze_tofind, &idx);
1591                 if (mze == NULL) {
1592                         mze = avl_nearest(&zc->zc_zap->zap_m.zap_avl,
1593                             idx, AVL_AFTER);
1594                 }
1595                 if (mze) {
1596                         mzap_ent_phys_t *mzep = MZE_PHYS(zc->zc_zap, mze);
1597                         ASSERT3U(mze->mze_cd, ==, mzep->mze_cd);
1598                         za->za_normalization_conflict =
1599                             mzap_normalization_conflict(zc->zc_zap, NULL, mze);
1600                         za->za_integer_length = 8;
1601                         za->za_num_integers = 1;
1602                         za->za_first_integer = mzep->mze_value;
1603                         (void) strlcpy(za->za_name, mzep->mze_name,
1604                             sizeof (za->za_name));
1605                         zc->zc_hash = mze->mze_hash;
1606                         zc->zc_cd = mze->mze_cd;
1607                         err = 0;
1608                 } else {
1609                         zc->zc_hash = -1ULL;
1610                         err = SET_ERROR(ENOENT);
1611                 }
1612         }
1613         rw_exit(&zc->zc_zap->zap_rwlock);
1614         return (err);
1615 }
1616
1617 void
1618 zap_cursor_advance(zap_cursor_t *zc)
1619 {
1620         if (zc->zc_hash == -1ULL)
1621                 return;
1622         zc->zc_cd++;
1623 }
1624
1625 int
1626 zap_get_stats(objset_t *os, uint64_t zapobj, zap_stats_t *zs)
1627 {
1628         zap_t *zap;
1629
1630         int err =
1631             zap_lockdir(os, zapobj, NULL, RW_READER, TRUE, FALSE, FTAG, &zap);
1632         if (err != 0)
1633                 return (err);
1634
1635         memset(zs, 0, sizeof (zap_stats_t));
1636
1637         if (zap->zap_ismicro) {
1638                 zs->zs_blocksize = zap->zap_dbuf->db_size;
1639                 zs->zs_num_entries = zap->zap_m.zap_num_entries;
1640                 zs->zs_num_blocks = 1;
1641         } else {
1642                 fzap_get_stats(zap, zs);
1643         }
1644         zap_unlockdir(zap, FTAG);
1645         return (0);
1646 }
1647
1648 #if defined(_KERNEL)
1649 EXPORT_SYMBOL(zap_create);
1650 EXPORT_SYMBOL(zap_create_dnsize);
1651 EXPORT_SYMBOL(zap_create_norm);
1652 EXPORT_SYMBOL(zap_create_norm_dnsize);
1653 EXPORT_SYMBOL(zap_create_flags);
1654 EXPORT_SYMBOL(zap_create_flags_dnsize);
1655 EXPORT_SYMBOL(zap_create_claim);
1656 EXPORT_SYMBOL(zap_create_claim_norm);
1657 EXPORT_SYMBOL(zap_create_claim_norm_dnsize);
1658 EXPORT_SYMBOL(zap_create_hold);
1659 EXPORT_SYMBOL(zap_destroy);
1660 EXPORT_SYMBOL(zap_lookup);
1661 EXPORT_SYMBOL(zap_lookup_by_dnode);
1662 EXPORT_SYMBOL(zap_lookup_norm);
1663 EXPORT_SYMBOL(zap_lookup_uint64);
1664 EXPORT_SYMBOL(zap_contains);
1665 EXPORT_SYMBOL(zap_prefetch);
1666 EXPORT_SYMBOL(zap_prefetch_uint64);
1667 EXPORT_SYMBOL(zap_add);
1668 EXPORT_SYMBOL(zap_add_by_dnode);
1669 EXPORT_SYMBOL(zap_add_uint64);
1670 EXPORT_SYMBOL(zap_update);
1671 EXPORT_SYMBOL(zap_update_uint64);
1672 EXPORT_SYMBOL(zap_length);
1673 EXPORT_SYMBOL(zap_length_uint64);
1674 EXPORT_SYMBOL(zap_remove);
1675 EXPORT_SYMBOL(zap_remove_by_dnode);
1676 EXPORT_SYMBOL(zap_remove_norm);
1677 EXPORT_SYMBOL(zap_remove_uint64);
1678 EXPORT_SYMBOL(zap_count);
1679 EXPORT_SYMBOL(zap_value_search);
1680 EXPORT_SYMBOL(zap_join);
1681 EXPORT_SYMBOL(zap_join_increment);
1682 EXPORT_SYMBOL(zap_add_int);
1683 EXPORT_SYMBOL(zap_remove_int);
1684 EXPORT_SYMBOL(zap_lookup_int);
1685 EXPORT_SYMBOL(zap_increment_int);
1686 EXPORT_SYMBOL(zap_add_int_key);
1687 EXPORT_SYMBOL(zap_lookup_int_key);
1688 EXPORT_SYMBOL(zap_increment);
1689 EXPORT_SYMBOL(zap_cursor_init);
1690 EXPORT_SYMBOL(zap_cursor_fini);
1691 EXPORT_SYMBOL(zap_cursor_retrieve);
1692 EXPORT_SYMBOL(zap_cursor_advance);
1693 EXPORT_SYMBOL(zap_cursor_serialize);
1694 EXPORT_SYMBOL(zap_cursor_init_serialized);
1695 EXPORT_SYMBOL(zap_get_stats);
1696 #endif