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