xref: /illumos-gate/usr/src/uts/common/fs/zfs/zap_micro.c (revision 720d1aa11ffe42c822fb6151fb4ae83194389942)
1 /*
2  * CDDL HEADER START
3  *
4  * The contents of this file are subject to the terms of the
5  * Common Development and Distribution License (the "License").
6  * You may not use this file except in compliance with the License.
7  *
8  * You can obtain a copy of the license at usr/src/OPENSOLARIS.LICENSE
9  * or http://www.opensolaris.org/os/licensing.
10  * See the License for the specific language governing permissions
11  * and limitations under the License.
12  *
13  * When distributing Covered Code, include this CDDL HEADER in each
14  * file and include the License file at usr/src/OPENSOLARIS.LICENSE.
15  * If applicable, add the following below this CDDL HEADER, with the
16  * fields enclosed by brackets "[]" replaced with your own identifying
17  * information: Portions Copyright [yyyy] [name of copyright owner]
18  *
19  * CDDL HEADER END
20  */
21 /*
22  * Copyright 2009 Sun Microsystems, Inc.  All rights reserved.
23  * Use is subject to license terms.
24  */
25 
26 #include <sys/spa.h>
27 #include <sys/dmu.h>
28 #include <sys/zfs_context.h>
29 #include <sys/zap.h>
30 #include <sys/refcount.h>
31 #include <sys/zap_impl.h>
32 #include <sys/zap_leaf.h>
33 #include <sys/avl.h>
34 
35 #ifdef _KERNEL
36 #include <sys/sunddi.h>
37 #endif
38 
39 static int mzap_upgrade(zap_t **zapp, dmu_tx_t *tx);
40 
41 
42 static uint64_t
43 zap_hash(zap_t *zap, const char *normname)
44 {
45 	const uint8_t *cp;
46 	uint8_t c;
47 	uint64_t crc = zap->zap_salt;
48 
49 	/* NB: name must already be normalized, if necessary */
50 
51 	ASSERT(crc != 0);
52 	ASSERT(zfs_crc64_table[128] == ZFS_CRC64_POLY);
53 	for (cp = (const uint8_t *)normname; (c = *cp) != '\0'; cp++) {
54 		crc = (crc >> 8) ^ zfs_crc64_table[(crc ^ c) & 0xFF];
55 	}
56 
57 	/*
58 	 * Only use 28 bits, since we need 4 bits in the cookie for the
59 	 * collision differentiator.  We MUST use the high bits, since
60 	 * those are the ones that we first pay attention to when
61 	 * chosing the bucket.
62 	 */
63 	crc &= ~((1ULL << (64 - ZAP_HASHBITS)) - 1);
64 
65 	return (crc);
66 }
67 
68 static int
69 zap_normalize(zap_t *zap, const char *name, char *namenorm)
70 {
71 	size_t inlen, outlen;
72 	int err;
73 
74 	inlen = strlen(name) + 1;
75 	outlen = ZAP_MAXNAMELEN;
76 
77 	err = 0;
78 	(void) u8_textprep_str((char *)name, &inlen, namenorm, &outlen,
79 	    zap->zap_normflags | U8_TEXTPREP_IGNORE_NULL |
80 	    U8_TEXTPREP_IGNORE_INVALID, U8_UNICODE_LATEST, &err);
81 
82 	return (err);
83 }
84 
85 boolean_t
86 zap_match(zap_name_t *zn, const char *matchname)
87 {
88 	if (zn->zn_matchtype == MT_FIRST) {
89 		char norm[ZAP_MAXNAMELEN];
90 
91 		if (zap_normalize(zn->zn_zap, matchname, norm) != 0)
92 			return (B_FALSE);
93 
94 		return (strcmp(zn->zn_name_norm, norm) == 0);
95 	} else {
96 		/* MT_BEST or MT_EXACT */
97 		return (strcmp(zn->zn_name_orij, matchname) == 0);
98 	}
99 }
100 
101 void
102 zap_name_free(zap_name_t *zn)
103 {
104 	kmem_free(zn, sizeof (zap_name_t));
105 }
106 
107 /* XXX combine this with zap_lockdir()? */
108 zap_name_t *
109 zap_name_alloc(zap_t *zap, const char *name, matchtype_t mt)
110 {
111 	zap_name_t *zn = kmem_alloc(sizeof (zap_name_t), KM_SLEEP);
112 
113 	zn->zn_zap = zap;
114 	zn->zn_name_orij = name;
115 	zn->zn_matchtype = mt;
116 	if (zap->zap_normflags) {
117 		if (zap_normalize(zap, name, zn->zn_normbuf) != 0) {
118 			zap_name_free(zn);
119 			return (NULL);
120 		}
121 		zn->zn_name_norm = zn->zn_normbuf;
122 	} else {
123 		if (mt != MT_EXACT) {
124 			zap_name_free(zn);
125 			return (NULL);
126 		}
127 		zn->zn_name_norm = zn->zn_name_orij;
128 	}
129 
130 	zn->zn_hash = zap_hash(zap, zn->zn_name_norm);
131 	return (zn);
132 }
133 
134 static void
135 mzap_byteswap(mzap_phys_t *buf, size_t size)
136 {
137 	int i, max;
138 	buf->mz_block_type = BSWAP_64(buf->mz_block_type);
139 	buf->mz_salt = BSWAP_64(buf->mz_salt);
140 	buf->mz_normflags = BSWAP_64(buf->mz_normflags);
141 	max = (size / MZAP_ENT_LEN) - 1;
142 	for (i = 0; i < max; i++) {
143 		buf->mz_chunk[i].mze_value =
144 		    BSWAP_64(buf->mz_chunk[i].mze_value);
145 		buf->mz_chunk[i].mze_cd =
146 		    BSWAP_32(buf->mz_chunk[i].mze_cd);
147 	}
148 }
149 
150 void
151 zap_byteswap(void *buf, size_t size)
152 {
153 	uint64_t block_type;
154 
155 	block_type = *(uint64_t *)buf;
156 
157 	if (block_type == ZBT_MICRO || block_type == BSWAP_64(ZBT_MICRO)) {
158 		/* ASSERT(magic == ZAP_LEAF_MAGIC); */
159 		mzap_byteswap(buf, size);
160 	} else {
161 		fzap_byteswap(buf, size);
162 	}
163 }
164 
165 static int
166 mze_compare(const void *arg1, const void *arg2)
167 {
168 	const mzap_ent_t *mze1 = arg1;
169 	const mzap_ent_t *mze2 = arg2;
170 
171 	if (mze1->mze_hash > mze2->mze_hash)
172 		return (+1);
173 	if (mze1->mze_hash < mze2->mze_hash)
174 		return (-1);
175 	if (mze1->mze_phys.mze_cd > mze2->mze_phys.mze_cd)
176 		return (+1);
177 	if (mze1->mze_phys.mze_cd < mze2->mze_phys.mze_cd)
178 		return (-1);
179 	return (0);
180 }
181 
182 static void
183 mze_insert(zap_t *zap, int chunkid, uint64_t hash, mzap_ent_phys_t *mzep)
184 {
185 	mzap_ent_t *mze;
186 
187 	ASSERT(zap->zap_ismicro);
188 	ASSERT(RW_WRITE_HELD(&zap->zap_rwlock));
189 	ASSERT(mzep->mze_cd < ZAP_MAXCD);
190 
191 	mze = kmem_alloc(sizeof (mzap_ent_t), KM_SLEEP);
192 	mze->mze_chunkid = chunkid;
193 	mze->mze_hash = hash;
194 	mze->mze_phys = *mzep;
195 	avl_add(&zap->zap_m.zap_avl, mze);
196 }
197 
198 static mzap_ent_t *
199 mze_find(zap_name_t *zn)
200 {
201 	mzap_ent_t mze_tofind;
202 	mzap_ent_t *mze;
203 	avl_index_t idx;
204 	avl_tree_t *avl = &zn->zn_zap->zap_m.zap_avl;
205 
206 	ASSERT(zn->zn_zap->zap_ismicro);
207 	ASSERT(RW_LOCK_HELD(&zn->zn_zap->zap_rwlock));
208 
209 	if (strlen(zn->zn_name_norm) >= sizeof (mze_tofind.mze_phys.mze_name))
210 		return (NULL);
211 
212 	mze_tofind.mze_hash = zn->zn_hash;
213 	mze_tofind.mze_phys.mze_cd = 0;
214 
215 again:
216 	mze = avl_find(avl, &mze_tofind, &idx);
217 	if (mze == NULL)
218 		mze = avl_nearest(avl, idx, AVL_AFTER);
219 	for (; mze && mze->mze_hash == zn->zn_hash; mze = AVL_NEXT(avl, mze)) {
220 		if (zap_match(zn, mze->mze_phys.mze_name))
221 			return (mze);
222 	}
223 	if (zn->zn_matchtype == MT_BEST) {
224 		zn->zn_matchtype = MT_FIRST;
225 		goto again;
226 	}
227 	return (NULL);
228 }
229 
230 static uint32_t
231 mze_find_unused_cd(zap_t *zap, uint64_t hash)
232 {
233 	mzap_ent_t mze_tofind;
234 	mzap_ent_t *mze;
235 	avl_index_t idx;
236 	avl_tree_t *avl = &zap->zap_m.zap_avl;
237 	uint32_t cd;
238 
239 	ASSERT(zap->zap_ismicro);
240 	ASSERT(RW_LOCK_HELD(&zap->zap_rwlock));
241 
242 	mze_tofind.mze_hash = hash;
243 	mze_tofind.mze_phys.mze_cd = 0;
244 
245 	cd = 0;
246 	for (mze = avl_find(avl, &mze_tofind, &idx);
247 	    mze && mze->mze_hash == hash; mze = AVL_NEXT(avl, mze)) {
248 		if (mze->mze_phys.mze_cd != cd)
249 			break;
250 		cd++;
251 	}
252 
253 	return (cd);
254 }
255 
256 static void
257 mze_remove(zap_t *zap, mzap_ent_t *mze)
258 {
259 	ASSERT(zap->zap_ismicro);
260 	ASSERT(RW_WRITE_HELD(&zap->zap_rwlock));
261 
262 	avl_remove(&zap->zap_m.zap_avl, mze);
263 	kmem_free(mze, sizeof (mzap_ent_t));
264 }
265 
266 static void
267 mze_destroy(zap_t *zap)
268 {
269 	mzap_ent_t *mze;
270 	void *avlcookie = NULL;
271 
272 	while (mze = avl_destroy_nodes(&zap->zap_m.zap_avl, &avlcookie))
273 		kmem_free(mze, sizeof (mzap_ent_t));
274 	avl_destroy(&zap->zap_m.zap_avl);
275 }
276 
277 static zap_t *
278 mzap_open(objset_t *os, uint64_t obj, dmu_buf_t *db)
279 {
280 	zap_t *winner;
281 	zap_t *zap;
282 	int i;
283 
284 	ASSERT3U(MZAP_ENT_LEN, ==, sizeof (mzap_ent_phys_t));
285 
286 	zap = kmem_zalloc(sizeof (zap_t), KM_SLEEP);
287 	rw_init(&zap->zap_rwlock, 0, 0, 0);
288 	rw_enter(&zap->zap_rwlock, RW_WRITER);
289 	zap->zap_objset = os;
290 	zap->zap_object = obj;
291 	zap->zap_dbuf = db;
292 
293 	if (*(uint64_t *)db->db_data != ZBT_MICRO) {
294 		mutex_init(&zap->zap_f.zap_num_entries_mtx, 0, 0, 0);
295 		zap->zap_f.zap_block_shift = highbit(db->db_size) - 1;
296 	} else {
297 		zap->zap_ismicro = TRUE;
298 	}
299 
300 	/*
301 	 * Make sure that zap_ismicro is set before we let others see
302 	 * it, because zap_lockdir() checks zap_ismicro without the lock
303 	 * held.
304 	 */
305 	winner = dmu_buf_set_user(db, zap, &zap->zap_m.zap_phys, zap_evict);
306 
307 	if (winner != NULL) {
308 		rw_exit(&zap->zap_rwlock);
309 		rw_destroy(&zap->zap_rwlock);
310 		if (!zap->zap_ismicro)
311 			mutex_destroy(&zap->zap_f.zap_num_entries_mtx);
312 		kmem_free(zap, sizeof (zap_t));
313 		return (winner);
314 	}
315 
316 	if (zap->zap_ismicro) {
317 		zap->zap_salt = zap->zap_m.zap_phys->mz_salt;
318 		zap->zap_normflags = zap->zap_m.zap_phys->mz_normflags;
319 		zap->zap_m.zap_num_chunks = db->db_size / MZAP_ENT_LEN - 1;
320 		avl_create(&zap->zap_m.zap_avl, mze_compare,
321 		    sizeof (mzap_ent_t), offsetof(mzap_ent_t, mze_node));
322 
323 		for (i = 0; i < zap->zap_m.zap_num_chunks; i++) {
324 			mzap_ent_phys_t *mze =
325 			    &zap->zap_m.zap_phys->mz_chunk[i];
326 			if (mze->mze_name[0]) {
327 				zap_name_t *zn;
328 
329 				zap->zap_m.zap_num_entries++;
330 				zn = zap_name_alloc(zap, mze->mze_name,
331 				    MT_EXACT);
332 				mze_insert(zap, i, zn->zn_hash, mze);
333 				zap_name_free(zn);
334 			}
335 		}
336 	} else {
337 		zap->zap_salt = zap->zap_f.zap_phys->zap_salt;
338 		zap->zap_normflags = zap->zap_f.zap_phys->zap_normflags;
339 
340 		ASSERT3U(sizeof (struct zap_leaf_header), ==,
341 		    2*ZAP_LEAF_CHUNKSIZE);
342 
343 		/*
344 		 * The embedded pointer table should not overlap the
345 		 * other members.
346 		 */
347 		ASSERT3P(&ZAP_EMBEDDED_PTRTBL_ENT(zap, 0), >,
348 		    &zap->zap_f.zap_phys->zap_salt);
349 
350 		/*
351 		 * The embedded pointer table should end at the end of
352 		 * the block
353 		 */
354 		ASSERT3U((uintptr_t)&ZAP_EMBEDDED_PTRTBL_ENT(zap,
355 		    1<<ZAP_EMBEDDED_PTRTBL_SHIFT(zap)) -
356 		    (uintptr_t)zap->zap_f.zap_phys, ==,
357 		    zap->zap_dbuf->db_size);
358 	}
359 	rw_exit(&zap->zap_rwlock);
360 	return (zap);
361 }
362 
363 int
364 zap_lockdir(objset_t *os, uint64_t obj, dmu_tx_t *tx,
365     krw_t lti, boolean_t fatreader, boolean_t adding, zap_t **zapp)
366 {
367 	zap_t *zap;
368 	dmu_buf_t *db;
369 	krw_t lt;
370 	int err;
371 
372 	*zapp = NULL;
373 
374 	err = dmu_buf_hold(os, obj, 0, NULL, &db);
375 	if (err)
376 		return (err);
377 
378 #ifdef ZFS_DEBUG
379 	{
380 		dmu_object_info_t doi;
381 		dmu_object_info_from_db(db, &doi);
382 		ASSERT(dmu_ot[doi.doi_type].ot_byteswap == zap_byteswap);
383 	}
384 #endif
385 
386 	zap = dmu_buf_get_user(db);
387 	if (zap == NULL)
388 		zap = mzap_open(os, obj, db);
389 
390 	/*
391 	 * We're checking zap_ismicro without the lock held, in order to
392 	 * tell what type of lock we want.  Once we have some sort of
393 	 * lock, see if it really is the right type.  In practice this
394 	 * can only be different if it was upgraded from micro to fat,
395 	 * and micro wanted WRITER but fat only needs READER.
396 	 */
397 	lt = (!zap->zap_ismicro && fatreader) ? RW_READER : lti;
398 	rw_enter(&zap->zap_rwlock, lt);
399 	if (lt != ((!zap->zap_ismicro && fatreader) ? RW_READER : lti)) {
400 		/* it was upgraded, now we only need reader */
401 		ASSERT(lt == RW_WRITER);
402 		ASSERT(RW_READER ==
403 		    (!zap->zap_ismicro && fatreader) ? RW_READER : lti);
404 		rw_downgrade(&zap->zap_rwlock);
405 		lt = RW_READER;
406 	}
407 
408 	zap->zap_objset = os;
409 
410 	if (lt == RW_WRITER)
411 		dmu_buf_will_dirty(db, tx);
412 
413 	ASSERT3P(zap->zap_dbuf, ==, db);
414 
415 	ASSERT(!zap->zap_ismicro ||
416 	    zap->zap_m.zap_num_entries <= zap->zap_m.zap_num_chunks);
417 	if (zap->zap_ismicro && tx && adding &&
418 	    zap->zap_m.zap_num_entries == zap->zap_m.zap_num_chunks) {
419 		uint64_t newsz = db->db_size + SPA_MINBLOCKSIZE;
420 		if (newsz > MZAP_MAX_BLKSZ) {
421 			dprintf("upgrading obj %llu: num_entries=%u\n",
422 			    obj, zap->zap_m.zap_num_entries);
423 			*zapp = zap;
424 			return (mzap_upgrade(zapp, tx));
425 		}
426 		err = dmu_object_set_blocksize(os, obj, newsz, 0, tx);
427 		ASSERT3U(err, ==, 0);
428 		zap->zap_m.zap_num_chunks =
429 		    db->db_size / MZAP_ENT_LEN - 1;
430 	}
431 
432 	*zapp = zap;
433 	return (0);
434 }
435 
436 void
437 zap_unlockdir(zap_t *zap)
438 {
439 	rw_exit(&zap->zap_rwlock);
440 	dmu_buf_rele(zap->zap_dbuf, NULL);
441 }
442 
443 static int
444 mzap_upgrade(zap_t **zapp, dmu_tx_t *tx)
445 {
446 	mzap_phys_t *mzp;
447 	int i, sz, nchunks, err;
448 	zap_t *zap = *zapp;
449 
450 	ASSERT(RW_WRITE_HELD(&zap->zap_rwlock));
451 
452 	sz = zap->zap_dbuf->db_size;
453 	mzp = kmem_alloc(sz, KM_SLEEP);
454 	bcopy(zap->zap_dbuf->db_data, mzp, sz);
455 	nchunks = zap->zap_m.zap_num_chunks;
456 
457 	err = dmu_object_set_blocksize(zap->zap_objset, zap->zap_object,
458 	    1ULL << fzap_default_block_shift, 0, tx);
459 	if (err) {
460 		kmem_free(mzp, sz);
461 		return (err);
462 	}
463 
464 	dprintf("upgrading obj=%llu with %u chunks\n",
465 	    zap->zap_object, nchunks);
466 	/* XXX destroy the avl later, so we can use the stored hash value */
467 	mze_destroy(zap);
468 
469 	fzap_upgrade(zap, tx);
470 
471 	for (i = 0; i < nchunks; i++) {
472 		int err;
473 		mzap_ent_phys_t *mze = &mzp->mz_chunk[i];
474 		zap_name_t *zn;
475 		if (mze->mze_name[0] == 0)
476 			continue;
477 		dprintf("adding %s=%llu\n",
478 		    mze->mze_name, mze->mze_value);
479 		zn = zap_name_alloc(zap, mze->mze_name, MT_EXACT);
480 		err = fzap_add_cd(zn, 8, 1, &mze->mze_value, mze->mze_cd, tx);
481 		zap = zn->zn_zap;	/* fzap_add_cd() may change zap */
482 		zap_name_free(zn);
483 		if (err)
484 			break;
485 	}
486 	kmem_free(mzp, sz);
487 	*zapp = zap;
488 	return (err);
489 }
490 
491 static void
492 mzap_create_impl(objset_t *os, uint64_t obj, int normflags, dmu_tx_t *tx)
493 {
494 	dmu_buf_t *db;
495 	mzap_phys_t *zp;
496 
497 	VERIFY(0 == dmu_buf_hold(os, obj, 0, FTAG, &db));
498 
499 #ifdef ZFS_DEBUG
500 	{
501 		dmu_object_info_t doi;
502 		dmu_object_info_from_db(db, &doi);
503 		ASSERT(dmu_ot[doi.doi_type].ot_byteswap == zap_byteswap);
504 	}
505 #endif
506 
507 	dmu_buf_will_dirty(db, tx);
508 	zp = db->db_data;
509 	zp->mz_block_type = ZBT_MICRO;
510 	zp->mz_salt = ((uintptr_t)db ^ (uintptr_t)tx ^ (obj << 1)) | 1ULL;
511 	zp->mz_normflags = normflags;
512 	dmu_buf_rele(db, FTAG);
513 }
514 
515 int
516 zap_create_claim(objset_t *os, uint64_t obj, dmu_object_type_t ot,
517     dmu_object_type_t bonustype, int bonuslen, dmu_tx_t *tx)
518 {
519 	return (zap_create_claim_norm(os, obj,
520 	    0, ot, bonustype, bonuslen, tx));
521 }
522 
523 int
524 zap_create_claim_norm(objset_t *os, uint64_t obj, int normflags,
525     dmu_object_type_t ot,
526     dmu_object_type_t bonustype, int bonuslen, dmu_tx_t *tx)
527 {
528 	int err;
529 
530 	err = dmu_object_claim(os, obj, ot, 0, bonustype, bonuslen, tx);
531 	if (err != 0)
532 		return (err);
533 	mzap_create_impl(os, obj, normflags, tx);
534 	return (0);
535 }
536 
537 uint64_t
538 zap_create(objset_t *os, dmu_object_type_t ot,
539     dmu_object_type_t bonustype, int bonuslen, dmu_tx_t *tx)
540 {
541 	return (zap_create_norm(os, 0, ot, bonustype, bonuslen, tx));
542 }
543 
544 uint64_t
545 zap_create_norm(objset_t *os, int normflags, dmu_object_type_t ot,
546     dmu_object_type_t bonustype, int bonuslen, dmu_tx_t *tx)
547 {
548 	uint64_t obj = dmu_object_alloc(os, ot, 0, bonustype, bonuslen, tx);
549 
550 	mzap_create_impl(os, obj, normflags, tx);
551 	return (obj);
552 }
553 
554 int
555 zap_destroy(objset_t *os, uint64_t zapobj, dmu_tx_t *tx)
556 {
557 	/*
558 	 * dmu_object_free will free the object number and free the
559 	 * data.  Freeing the data will cause our pageout function to be
560 	 * called, which will destroy our data (zap_leaf_t's and zap_t).
561 	 */
562 
563 	return (dmu_object_free(os, zapobj, tx));
564 }
565 
566 _NOTE(ARGSUSED(0))
567 void
568 zap_evict(dmu_buf_t *db, void *vzap)
569 {
570 	zap_t *zap = vzap;
571 
572 	rw_destroy(&zap->zap_rwlock);
573 
574 	if (zap->zap_ismicro)
575 		mze_destroy(zap);
576 	else
577 		mutex_destroy(&zap->zap_f.zap_num_entries_mtx);
578 
579 	kmem_free(zap, sizeof (zap_t));
580 }
581 
582 int
583 zap_count(objset_t *os, uint64_t zapobj, uint64_t *count)
584 {
585 	zap_t *zap;
586 	int err;
587 
588 	err = zap_lockdir(os, zapobj, NULL, RW_READER, TRUE, FALSE, &zap);
589 	if (err)
590 		return (err);
591 	if (!zap->zap_ismicro) {
592 		err = fzap_count(zap, count);
593 	} else {
594 		*count = zap->zap_m.zap_num_entries;
595 	}
596 	zap_unlockdir(zap);
597 	return (err);
598 }
599 
600 /*
601  * zn may be NULL; if not specified, it will be computed if needed.
602  * See also the comment above zap_entry_normalization_conflict().
603  */
604 static boolean_t
605 mzap_normalization_conflict(zap_t *zap, zap_name_t *zn, mzap_ent_t *mze)
606 {
607 	mzap_ent_t *other;
608 	int direction = AVL_BEFORE;
609 	boolean_t allocdzn = B_FALSE;
610 
611 	if (zap->zap_normflags == 0)
612 		return (B_FALSE);
613 
614 again:
615 	for (other = avl_walk(&zap->zap_m.zap_avl, mze, direction);
616 	    other && other->mze_hash == mze->mze_hash;
617 	    other = avl_walk(&zap->zap_m.zap_avl, other, direction)) {
618 
619 		if (zn == NULL) {
620 			zn = zap_name_alloc(zap, mze->mze_phys.mze_name,
621 			    MT_FIRST);
622 			allocdzn = B_TRUE;
623 		}
624 		if (zap_match(zn, other->mze_phys.mze_name)) {
625 			if (allocdzn)
626 				zap_name_free(zn);
627 			return (B_TRUE);
628 		}
629 	}
630 
631 	if (direction == AVL_BEFORE) {
632 		direction = AVL_AFTER;
633 		goto again;
634 	}
635 
636 	if (allocdzn)
637 		zap_name_free(zn);
638 	return (B_FALSE);
639 }
640 
641 /*
642  * Routines for manipulating attributes.
643  */
644 
645 int
646 zap_lookup(objset_t *os, uint64_t zapobj, const char *name,
647     uint64_t integer_size, uint64_t num_integers, void *buf)
648 {
649 	return (zap_lookup_norm(os, zapobj, name, integer_size,
650 	    num_integers, buf, MT_EXACT, NULL, 0, NULL));
651 }
652 
653 int
654 zap_lookup_norm(objset_t *os, uint64_t zapobj, const char *name,
655     uint64_t integer_size, uint64_t num_integers, void *buf,
656     matchtype_t mt, char *realname, int rn_len,
657     boolean_t *ncp)
658 {
659 	zap_t *zap;
660 	int err;
661 	mzap_ent_t *mze;
662 	zap_name_t *zn;
663 
664 	err = zap_lockdir(os, zapobj, NULL, RW_READER, TRUE, FALSE, &zap);
665 	if (err)
666 		return (err);
667 	zn = zap_name_alloc(zap, name, mt);
668 	if (zn == NULL) {
669 		zap_unlockdir(zap);
670 		return (ENOTSUP);
671 	}
672 
673 	if (!zap->zap_ismicro) {
674 		err = fzap_lookup(zn, integer_size, num_integers, buf,
675 		    realname, rn_len, ncp);
676 	} else {
677 		mze = mze_find(zn);
678 		if (mze == NULL) {
679 			err = ENOENT;
680 		} else {
681 			if (num_integers < 1) {
682 				err = EOVERFLOW;
683 			} else if (integer_size != 8) {
684 				err = EINVAL;
685 			} else {
686 				*(uint64_t *)buf = mze->mze_phys.mze_value;
687 				(void) strlcpy(realname,
688 				    mze->mze_phys.mze_name, rn_len);
689 				if (ncp) {
690 					*ncp = mzap_normalization_conflict(zap,
691 					    zn, mze);
692 				}
693 			}
694 		}
695 	}
696 	zap_name_free(zn);
697 	zap_unlockdir(zap);
698 	return (err);
699 }
700 
701 int
702 zap_length(objset_t *os, uint64_t zapobj, const char *name,
703     uint64_t *integer_size, uint64_t *num_integers)
704 {
705 	zap_t *zap;
706 	int err;
707 	mzap_ent_t *mze;
708 	zap_name_t *zn;
709 
710 	err = zap_lockdir(os, zapobj, NULL, RW_READER, TRUE, FALSE, &zap);
711 	if (err)
712 		return (err);
713 	zn = zap_name_alloc(zap, name, MT_EXACT);
714 	if (zn == NULL) {
715 		zap_unlockdir(zap);
716 		return (ENOTSUP);
717 	}
718 	if (!zap->zap_ismicro) {
719 		err = fzap_length(zn, integer_size, num_integers);
720 	} else {
721 		mze = mze_find(zn);
722 		if (mze == NULL) {
723 			err = ENOENT;
724 		} else {
725 			if (integer_size)
726 				*integer_size = 8;
727 			if (num_integers)
728 				*num_integers = 1;
729 		}
730 	}
731 	zap_name_free(zn);
732 	zap_unlockdir(zap);
733 	return (err);
734 }
735 
736 static void
737 mzap_addent(zap_name_t *zn, uint64_t value)
738 {
739 	int i;
740 	zap_t *zap = zn->zn_zap;
741 	int start = zap->zap_m.zap_alloc_next;
742 	uint32_t cd;
743 
744 	dprintf("obj=%llu %s=%llu\n", zap->zap_object,
745 	    zn->zn_name_orij, value);
746 	ASSERT(RW_WRITE_HELD(&zap->zap_rwlock));
747 
748 #ifdef ZFS_DEBUG
749 	for (i = 0; i < zap->zap_m.zap_num_chunks; i++) {
750 		mzap_ent_phys_t *mze = &zap->zap_m.zap_phys->mz_chunk[i];
751 		ASSERT(strcmp(zn->zn_name_orij, mze->mze_name) != 0);
752 	}
753 #endif
754 
755 	cd = mze_find_unused_cd(zap, zn->zn_hash);
756 	/* given the limited size of the microzap, this can't happen */
757 	ASSERT(cd != ZAP_MAXCD);
758 
759 again:
760 	for (i = start; i < zap->zap_m.zap_num_chunks; i++) {
761 		mzap_ent_phys_t *mze = &zap->zap_m.zap_phys->mz_chunk[i];
762 		if (mze->mze_name[0] == 0) {
763 			mze->mze_value = value;
764 			mze->mze_cd = cd;
765 			(void) strcpy(mze->mze_name, zn->zn_name_orij);
766 			zap->zap_m.zap_num_entries++;
767 			zap->zap_m.zap_alloc_next = i+1;
768 			if (zap->zap_m.zap_alloc_next ==
769 			    zap->zap_m.zap_num_chunks)
770 				zap->zap_m.zap_alloc_next = 0;
771 			mze_insert(zap, i, zn->zn_hash, mze);
772 			return;
773 		}
774 	}
775 	if (start != 0) {
776 		start = 0;
777 		goto again;
778 	}
779 	ASSERT(!"out of entries!");
780 }
781 
782 int
783 zap_add(objset_t *os, uint64_t zapobj, const char *name,
784     int integer_size, uint64_t num_integers,
785     const void *val, dmu_tx_t *tx)
786 {
787 	zap_t *zap;
788 	int err;
789 	mzap_ent_t *mze;
790 	const uint64_t *intval = val;
791 	zap_name_t *zn;
792 
793 	err = zap_lockdir(os, zapobj, tx, RW_WRITER, TRUE, TRUE, &zap);
794 	if (err)
795 		return (err);
796 	zn = zap_name_alloc(zap, name, MT_EXACT);
797 	if (zn == NULL) {
798 		zap_unlockdir(zap);
799 		return (ENOTSUP);
800 	}
801 	if (!zap->zap_ismicro) {
802 		err = fzap_add(zn, integer_size, num_integers, val, tx);
803 		zap = zn->zn_zap;	/* fzap_add() may change zap */
804 	} else if (integer_size != 8 || num_integers != 1 ||
805 	    strlen(name) >= MZAP_NAME_LEN) {
806 		dprintf("upgrading obj %llu: intsz=%u numint=%llu name=%s\n",
807 		    zapobj, integer_size, num_integers, name);
808 		err = mzap_upgrade(&zn->zn_zap, tx);
809 		if (err == 0)
810 			err = fzap_add(zn, integer_size, num_integers, val, tx);
811 		zap = zn->zn_zap;	/* fzap_add() may change zap */
812 	} else {
813 		mze = mze_find(zn);
814 		if (mze != NULL) {
815 			err = EEXIST;
816 		} else {
817 			mzap_addent(zn, *intval);
818 		}
819 	}
820 	ASSERT(zap == zn->zn_zap);
821 	zap_name_free(zn);
822 	if (zap != NULL)	/* may be NULL if fzap_add() failed */
823 		zap_unlockdir(zap);
824 	return (err);
825 }
826 
827 int
828 zap_update(objset_t *os, uint64_t zapobj, const char *name,
829     int integer_size, uint64_t num_integers, const void *val, dmu_tx_t *tx)
830 {
831 	zap_t *zap;
832 	mzap_ent_t *mze;
833 	const uint64_t *intval = val;
834 	zap_name_t *zn;
835 	int err;
836 
837 	err = zap_lockdir(os, zapobj, tx, RW_WRITER, TRUE, TRUE, &zap);
838 	if (err)
839 		return (err);
840 	zn = zap_name_alloc(zap, name, MT_EXACT);
841 	if (zn == NULL) {
842 		zap_unlockdir(zap);
843 		return (ENOTSUP);
844 	}
845 	if (!zap->zap_ismicro) {
846 		err = fzap_update(zn, integer_size, num_integers, val, tx);
847 		zap = zn->zn_zap;	/* fzap_update() may change zap */
848 	} else if (integer_size != 8 || num_integers != 1 ||
849 	    strlen(name) >= MZAP_NAME_LEN) {
850 		dprintf("upgrading obj %llu: intsz=%u numint=%llu name=%s\n",
851 		    zapobj, integer_size, num_integers, name);
852 		err = mzap_upgrade(&zn->zn_zap, tx);
853 		if (err == 0)
854 			err = fzap_update(zn, integer_size, num_integers,
855 			    val, tx);
856 		zap = zn->zn_zap;	/* fzap_update() may change zap */
857 	} else {
858 		mze = mze_find(zn);
859 		if (mze != NULL) {
860 			mze->mze_phys.mze_value = *intval;
861 			zap->zap_m.zap_phys->mz_chunk
862 			    [mze->mze_chunkid].mze_value = *intval;
863 		} else {
864 			mzap_addent(zn, *intval);
865 		}
866 	}
867 	ASSERT(zap == zn->zn_zap);
868 	zap_name_free(zn);
869 	if (zap != NULL)	/* may be NULL if fzap_upgrade() failed */
870 		zap_unlockdir(zap);
871 	return (err);
872 }
873 
874 int
875 zap_remove(objset_t *os, uint64_t zapobj, const char *name, dmu_tx_t *tx)
876 {
877 	return (zap_remove_norm(os, zapobj, name, MT_EXACT, tx));
878 }
879 
880 int
881 zap_remove_norm(objset_t *os, uint64_t zapobj, const char *name,
882     matchtype_t mt, dmu_tx_t *tx)
883 {
884 	zap_t *zap;
885 	int err;
886 	mzap_ent_t *mze;
887 	zap_name_t *zn;
888 
889 	err = zap_lockdir(os, zapobj, tx, RW_WRITER, TRUE, FALSE, &zap);
890 	if (err)
891 		return (err);
892 	zn = zap_name_alloc(zap, name, mt);
893 	if (zn == NULL) {
894 		zap_unlockdir(zap);
895 		return (ENOTSUP);
896 	}
897 	if (!zap->zap_ismicro) {
898 		err = fzap_remove(zn, tx);
899 	} else {
900 		mze = mze_find(zn);
901 		if (mze == NULL) {
902 			err = ENOENT;
903 		} else {
904 			zap->zap_m.zap_num_entries--;
905 			bzero(&zap->zap_m.zap_phys->mz_chunk[mze->mze_chunkid],
906 			    sizeof (mzap_ent_phys_t));
907 			mze_remove(zap, mze);
908 		}
909 	}
910 	zap_name_free(zn);
911 	zap_unlockdir(zap);
912 	return (err);
913 }
914 
915 /*
916  * Routines for iterating over the attributes.
917  */
918 
919 /*
920  * We want to keep the high 32 bits of the cursor zero if we can, so
921  * that 32-bit programs can access this.  So use a small hash value so
922  * we can fit 4 bits of cd into the 32-bit cursor.
923  *
924  * [ 4 zero bits | 32-bit collision differentiator | 28-bit hash value ]
925  */
926 void
927 zap_cursor_init_serialized(zap_cursor_t *zc, objset_t *os, uint64_t zapobj,
928     uint64_t serialized)
929 {
930 	zc->zc_objset = os;
931 	zc->zc_zap = NULL;
932 	zc->zc_leaf = NULL;
933 	zc->zc_zapobj = zapobj;
934 	if (serialized == -1ULL) {
935 		zc->zc_hash = -1ULL;
936 		zc->zc_cd = 0;
937 	} else {
938 		zc->zc_hash = serialized << (64-ZAP_HASHBITS);
939 		zc->zc_cd = serialized >> ZAP_HASHBITS;
940 		if (zc->zc_cd >= ZAP_MAXCD) /* corrupt serialized */
941 			zc->zc_cd = 0;
942 	}
943 }
944 
945 void
946 zap_cursor_init(zap_cursor_t *zc, objset_t *os, uint64_t zapobj)
947 {
948 	zap_cursor_init_serialized(zc, os, zapobj, 0);
949 }
950 
951 void
952 zap_cursor_fini(zap_cursor_t *zc)
953 {
954 	if (zc->zc_zap) {
955 		rw_enter(&zc->zc_zap->zap_rwlock, RW_READER);
956 		zap_unlockdir(zc->zc_zap);
957 		zc->zc_zap = NULL;
958 	}
959 	if (zc->zc_leaf) {
960 		rw_enter(&zc->zc_leaf->l_rwlock, RW_READER);
961 		zap_put_leaf(zc->zc_leaf);
962 		zc->zc_leaf = NULL;
963 	}
964 	zc->zc_objset = NULL;
965 }
966 
967 uint64_t
968 zap_cursor_serialize(zap_cursor_t *zc)
969 {
970 	if (zc->zc_hash == -1ULL)
971 		return (-1ULL);
972 	ASSERT((zc->zc_hash & (ZAP_MAXCD-1)) == 0);
973 	ASSERT(zc->zc_cd < ZAP_MAXCD);
974 	return ((zc->zc_hash >> (64-ZAP_HASHBITS)) |
975 	    ((uint64_t)zc->zc_cd << ZAP_HASHBITS));
976 }
977 
978 int
979 zap_cursor_retrieve(zap_cursor_t *zc, zap_attribute_t *za)
980 {
981 	int err;
982 	avl_index_t idx;
983 	mzap_ent_t mze_tofind;
984 	mzap_ent_t *mze;
985 
986 	if (zc->zc_hash == -1ULL)
987 		return (ENOENT);
988 
989 	if (zc->zc_zap == NULL) {
990 		err = zap_lockdir(zc->zc_objset, zc->zc_zapobj, NULL,
991 		    RW_READER, TRUE, FALSE, &zc->zc_zap);
992 		if (err)
993 			return (err);
994 	} else {
995 		rw_enter(&zc->zc_zap->zap_rwlock, RW_READER);
996 	}
997 	if (!zc->zc_zap->zap_ismicro) {
998 		err = fzap_cursor_retrieve(zc->zc_zap, zc, za);
999 	} else {
1000 		err = ENOENT;
1001 
1002 		mze_tofind.mze_hash = zc->zc_hash;
1003 		mze_tofind.mze_phys.mze_cd = zc->zc_cd;
1004 
1005 		mze = avl_find(&zc->zc_zap->zap_m.zap_avl, &mze_tofind, &idx);
1006 		if (mze == NULL) {
1007 			mze = avl_nearest(&zc->zc_zap->zap_m.zap_avl,
1008 			    idx, AVL_AFTER);
1009 		}
1010 		if (mze) {
1011 			ASSERT(0 == bcmp(&mze->mze_phys,
1012 			    &zc->zc_zap->zap_m.zap_phys->mz_chunk
1013 			    [mze->mze_chunkid], sizeof (mze->mze_phys)));
1014 
1015 			za->za_normalization_conflict =
1016 			    mzap_normalization_conflict(zc->zc_zap, NULL, mze);
1017 			za->za_integer_length = 8;
1018 			za->za_num_integers = 1;
1019 			za->za_first_integer = mze->mze_phys.mze_value;
1020 			(void) strcpy(za->za_name, mze->mze_phys.mze_name);
1021 			zc->zc_hash = mze->mze_hash;
1022 			zc->zc_cd = mze->mze_phys.mze_cd;
1023 			err = 0;
1024 		} else {
1025 			zc->zc_hash = -1ULL;
1026 		}
1027 	}
1028 	rw_exit(&zc->zc_zap->zap_rwlock);
1029 	return (err);
1030 }
1031 
1032 void
1033 zap_cursor_advance(zap_cursor_t *zc)
1034 {
1035 	if (zc->zc_hash == -1ULL)
1036 		return;
1037 	zc->zc_cd++;
1038 	if (zc->zc_cd >= ZAP_MAXCD) {
1039 		zc->zc_cd = 0;
1040 		zc->zc_hash += 1ULL<<(64-ZAP_HASHBITS);
1041 		if (zc->zc_hash == 0) /* EOF */
1042 			zc->zc_hash = -1ULL;
1043 	}
1044 }
1045 
1046 int
1047 zap_get_stats(objset_t *os, uint64_t zapobj, zap_stats_t *zs)
1048 {
1049 	int err;
1050 	zap_t *zap;
1051 
1052 	err = zap_lockdir(os, zapobj, NULL, RW_READER, TRUE, FALSE, &zap);
1053 	if (err)
1054 		return (err);
1055 
1056 	bzero(zs, sizeof (zap_stats_t));
1057 
1058 	if (zap->zap_ismicro) {
1059 		zs->zs_blocksize = zap->zap_dbuf->db_size;
1060 		zs->zs_num_entries = zap->zap_m.zap_num_entries;
1061 		zs->zs_num_blocks = 1;
1062 	} else {
1063 		fzap_get_stats(zap, zs);
1064 	}
1065 	zap_unlockdir(zap);
1066 	return (0);
1067 }
1068 
1069 int
1070 zap_count_write(objset_t *os, uint64_t zapobj, const char *name, int add,
1071     uint64_t *towrite, uint64_t *tooverwrite)
1072 {
1073 	zap_t *zap;
1074 	int err = 0;
1075 
1076 
1077 	/*
1078 	 * Since, we don't have a name, we cannot figure out which blocks will
1079 	 * be affected in this operation. So, account for the worst case :
1080 	 * - 3 blocks overwritten: target leaf, ptrtbl block, header block
1081 	 * - 4 new blocks written if adding:
1082 	 * 	- 2 blocks for possibly split leaves,
1083 	 * 	- 2 grown ptrtbl blocks
1084 	 *
1085 	 * This also accomodates the case where an add operation to a fairly
1086 	 * large microzap results in a promotion to fatzap.
1087 	 */
1088 	if (name == NULL) {
1089 		*towrite += (3 + (add ? 4 : 0)) * SPA_MAXBLOCKSIZE;
1090 		return (err);
1091 	}
1092 
1093 	/*
1094 	 * We lock the zap with adding ==  FALSE. Because, if we pass
1095 	 * the actual value of add, it could trigger a mzap_upgrade().
1096 	 * At present we are just evaluating the possibility of this operation
1097 	 * and hence we donot want to trigger an upgrade.
1098 	 */
1099 	err = zap_lockdir(os, zapobj, NULL, RW_READER, TRUE, FALSE, &zap);
1100 	if (err)
1101 		return (err);
1102 
1103 	if (!zap->zap_ismicro) {
1104 		zap_name_t *zn = zap_name_alloc(zap, name, MT_EXACT);
1105 		if (zn) {
1106 			err = fzap_count_write(zn, add, towrite,
1107 			    tooverwrite);
1108 			zap_name_free(zn);
1109 		} else {
1110 			/*
1111 			 * We treat this case as similar to (name == NULL)
1112 			 */
1113 			*towrite += (3 + (add ? 4 : 0)) * SPA_MAXBLOCKSIZE;
1114 		}
1115 	} else {
1116 		/*
1117 		 * We are here if (name != NULL) and this is a micro-zap.
1118 		 * We account for the header block depending on whether it
1119 		 * is freeable.
1120 		 *
1121 		 * Incase of an add-operation it is hard to find out
1122 		 * if this add will promote this microzap to fatzap.
1123 		 * Hence, we consider the worst case and account for the
1124 		 * blocks assuming this microzap would be promoted to a
1125 		 * fatzap.
1126 		 *
1127 		 * 1 block overwritten  : header block
1128 		 * 4 new blocks written : 2 new split leaf, 2 grown
1129 		 *			ptrtbl blocks
1130 		 */
1131 		if (dmu_buf_freeable(zap->zap_dbuf))
1132 			*tooverwrite += SPA_MAXBLOCKSIZE;
1133 		else
1134 			*towrite += SPA_MAXBLOCKSIZE;
1135 
1136 		if (add) {
1137 			*towrite += 4 * SPA_MAXBLOCKSIZE;
1138 		}
1139 	}
1140 
1141 	zap_unlockdir(zap);
1142 	return (err);
1143 }
1144