/*

 * CDDL HEADER START

 *

 * The contents of this file are subject to the terms of the

 * Common Development and Distribution License (the "License").

 * You may not use this file except in compliance with the License.

 *

 * You can obtain a copy of the license at usr/src/OPENSOLARIS.LICENSE

 * or http://www.opensolaris.org/os/licensing.

 * See the License for the specific language governing permissions

 * and limitations under the License.

 *

 * When distributing Covered Code, include this CDDL HEADER in each

 * file and include the License file at usr/src/OPENSOLARIS.LICENSE.

 * If applicable, add the following below this CDDL HEADER, with the

 * fields enclosed by brackets "[]" replaced with your own identifying

 * information: Portions Copyright [yyyy] [name of copyright owner]

 *

 * CDDL HEADER END

 */

/*

 * Copyright (c) 2005, 2010, Oracle and/or its affiliates. All rights reserved.

 */

#include <sys/zio.h>

#include <sys/spa.h>

#include <sys/dmu.h>

#include <sys/zfs_context.h>

#include <sys/zap.h>

#include <sys/refcount.h>

#include <sys/zap_impl.h>

#include <sys/zap_leaf.h>

#include <sys/avl.h>

#include <sys/arc.h>

#ifdef _KERNEL

#include <sys/sunddi.h>

#endif

static int mzap_upgrade(zap_t **zapp, dmu_tx_t *tx, zap_flags_t flags);

uint64_t

zap_getflags(zap_t *zap)

{

	if (zap->zap_ismicro)

		return (0);

	return (zap->zap_u.zap_fat.zap_phys->zap_flags);

}

int

zap_hashbits(zap_t *zap)

{

	if (zap_getflags(zap) & ZAP_FLAG_HASH64)

		return (48);

	else

		return (28);

}

uint32_t

zap_maxcd(zap_t *zap)

{

	if (zap_getflags(zap) & ZAP_FLAG_HASH64)

		return ((1<<16)-1);

	else

		return (-1U);

}

static uint64_t

zap_hash(zap_name_t *zn)

{

	zap_t *zap = zn->zn_zap;

	uint64_t h = 0;

	if (zap_getflags(zap) & ZAP_FLAG_PRE_HASHED_KEY) {

		ASSERT(zap_getflags(zap) & ZAP_FLAG_UINT64_KEY);

		h = *(uint64_t *)zn->zn_key_orig;

	} else {

		h = zap->zap_salt;

		ASSERT(h != 0);

		ASSERT(zfs_crc64_table[128] == ZFS_CRC64_POLY);

		if (zap_getflags(zap) & ZAP_FLAG_UINT64_KEY) {

			int i;

			const uint64_t *wp = zn->zn_key_norm;

			ASSERT(zn->zn_key_intlen == 8);

			for (i = 0; i < zn->zn_key_norm_numints; wp++, i++) {

				int j;

				uint64_t word = *wp;

				for (j = 0; j < zn->zn_key_intlen; j++) {

					h = (h >> 8) ^

					    zfs_crc64_table[(h ^ word) & 0xFF];

					word >>= NBBY;

				}

			}

		} else {

			int i, len;

			const uint8_t *cp = zn->zn_key_norm;

			/*

			 * We previously stored the terminating null on

			 * disk, but didn't hash it, so we need to

			 * continue to not hash it.  (The

			 * zn_key_*_numints includes the terminating

			 * null for non-binary keys.)

			 */

			len = zn->zn_key_norm_numints - 1;

			ASSERT(zn->zn_key_intlen == 1);

			for (i = 0; i < len; cp++, i++) {

				h = (h >> 8) ^

				    zfs_crc64_table[(h ^ *cp) & 0xFF];

			}

		}

	}

	/*

	 * Don't use all 64 bits, since we need some in the cookie for

	 * the collision differentiator.  We MUST use the high bits,

	 * since those are the ones that we first pay attention to when

	 * chosing the bucket.

	 */

	h &= ~((1ULL << (64 - zap_hashbits(zap))) - 1);

	return (h);

}

static int

zap_normalize(zap_t *zap, const char *name, char *namenorm)

{

	size_t inlen, outlen;

	int err;

	ASSERT(!(zap_getflags(zap) & ZAP_FLAG_UINT64_KEY));

	inlen = strlen(name) + 1;

	outlen = ZAP_MAXNAMELEN;

	err = 0;

	(void) u8_textprep_str((char *)name, &inlen, namenorm, &outlen,

	    zap->zap_normflags | U8_TEXTPREP_IGNORE_NULL |

	    U8_TEXTPREP_IGNORE_INVALID, U8_UNICODE_LATEST, &err);

	return (err);

}

boolean_t

zap_match(zap_name_t *zn, const char *matchname)

{

	ASSERT(!(zap_getflags(zn->zn_zap) & ZAP_FLAG_UINT64_KEY));

	if (zn->zn_matchtype == MT_FIRST) {

		char norm[ZAP_MAXNAMELEN];

		if (zap_normalize(zn->zn_zap, matchname, norm) != 0)

			return (B_FALSE);

		return (strcmp(zn->zn_key_norm, norm) == 0);

	} else {

		/* MT_BEST or MT_EXACT */

		return (strcmp(zn->zn_key_orig, matchname) == 0);

	}

}

void

zap_name_free(zap_name_t *zn)

{

	kmem_free(zn, sizeof (zap_name_t));

}

zap_name_t *

zap_name_alloc(zap_t *zap, const char *key, matchtype_t mt)

{

	zap_name_t *zn = kmem_alloc(sizeof (zap_name_t), KM_SLEEP);

	zn->zn_zap = zap;

	zn->zn_key_intlen = sizeof (*key);

	zn->zn_key_orig = key;

	zn->zn_key_orig_numints = strlen(zn->zn_key_orig) + 1;

	zn->zn_matchtype = mt;

	if (zap->zap_normflags) {

		if (zap_normalize(zap, key, zn->zn_normbuf) != 0) {

			zap_name_free(zn);

			return (NULL);

		}

		zn->zn_key_norm = zn->zn_normbuf;

		zn->zn_key_norm_numints = strlen(zn->zn_key_norm) + 1;

	} else {

		if (mt != MT_EXACT) {

			zap_name_free(zn);

			return (NULL);

		}

		zn->zn_key_norm = zn->zn_key_orig;

		zn->zn_key_norm_numints = zn->zn_key_orig_numints;

	}

	zn->zn_hash = zap_hash(zn);

	return (zn);

}

zap_name_t *

zap_name_alloc_uint64(zap_t *zap, const uint64_t *key, int numints)

{

	zap_name_t *zn = kmem_alloc(sizeof (zap_name_t), KM_SLEEP);

	ASSERT(zap->zap_normflags == 0);

	zn->zn_zap = zap;

	zn->zn_key_intlen = sizeof (*key);

	zn->zn_key_orig = zn->zn_key_norm = key;

	zn->zn_key_orig_numints = zn->zn_key_norm_numints = numints;

	zn->zn_matchtype = MT_EXACT;

	zn->zn_hash = zap_hash(zn);

	return (zn);

}

static void

mzap_byteswap(mzap_phys_t *buf, size_t size)

{

	int i, max;

	buf->mz_block_type = BSWAP_64(buf->mz_block_type);

	buf->mz_salt = BSWAP_64(buf->mz_salt);

	buf->mz_normflags = BSWAP_64(buf->mz_normflags);

	max = (size / MZAP_ENT_LEN) - 1;

	for (i = 0; i < max; i++) {

		buf->mz_chunk[i].mze_value =

		    BSWAP_64(buf->mz_chunk[i].mze_value);

		buf->mz_chunk[i].mze_cd =

		    BSWAP_32(buf->mz_chunk[i].mze_cd);

	}

}

void

zap_byteswap(void *buf, size_t size)

{

	uint64_t block_type;

	block_type = *(uint64_t *)buf;

	if (block_type == ZBT_MICRO || block_type == BSWAP_64(ZBT_MICRO)) {

		/* ASSERT(magic == ZAP_LEAF_MAGIC); */

		mzap_byteswap(buf, size);

	} else {

		fzap_byteswap(buf, size);

	}

}

static int

mze_compare(const void *arg1, const void *arg2)

{

	const mzap_ent_t *mze1 = arg1;

	const mzap_ent_t *mze2 = arg2;

	if (mze1->mze_hash > mze2->mze_hash)

		return (+1);

	if (mze1->mze_hash < mze2->mze_hash)

		return (-1);

	if (mze1->mze_cd > mze2->mze_cd)

		return (+1);

	if (mze1->mze_cd < mze2->mze_cd)

		return (-1);

	return (0);

}

static void

mze_insert(zap_t *zap, int chunkid, uint64_t hash)

{

	mzap_ent_t *mze;

	ASSERT(zap->zap_ismicro);

	ASSERT(RW_WRITE_HELD(&zap->zap_rwlock));

	mze = kmem_alloc(sizeof (mzap_ent_t), KM_SLEEP);

	mze->mze_chunkid = chunkid;

	mze->mze_hash = hash;

	mze->mze_cd = MZE_PHYS(zap, mze)->mze_cd;

	ASSERT(MZE_PHYS(zap, mze)->mze_name[0] != 0);

	avl_add(&zap->zap_m.zap_avl, mze);

}

static mzap_ent_t *

mze_find(zap_name_t *zn)

{

	mzap_ent_t mze_tofind;

	mzap_ent_t *mze;

	avl_index_t idx;

	avl_tree_t *avl = &zn->zn_zap->zap_m.zap_avl;

	ASSERT(zn->zn_zap->zap_ismicro);

	ASSERT(RW_LOCK_HELD(&zn->zn_zap->zap_rwlock));

	mze_tofind.mze_hash = zn->zn_hash;

	mze_tofind.mze_cd = 0;

again:

	mze = avl_find(avl, &mze_tofind, &idx);

	if (mze == NULL)

		mze = avl_nearest(avl, idx, AVL_AFTER);

	for (; mze && mze->mze_hash == zn->zn_hash; mze = AVL_NEXT(avl, mze)) {

		ASSERT3U(mze->mze_cd, ==, MZE_PHYS(zn->zn_zap, mze)->mze_cd);

		if (zap_match(zn, MZE_PHYS(zn->zn_zap, mze)->mze_name))

			return (mze);

	}

	if (zn->zn_matchtype == MT_BEST) {

		zn->zn_matchtype = MT_FIRST;

		goto again;

	}

	return (NULL);

}

static uint32_t

mze_find_unused_cd(zap_t *zap, uint64_t hash)

{

	mzap_ent_t mze_tofind;

	mzap_ent_t *mze;

	avl_index_t idx;

	avl_tree_t *avl = &zap->zap_m.zap_avl;

	uint32_t cd;

	ASSERT(zap->zap_ismicro);

	ASSERT(RW_LOCK_HELD(&zap->zap_rwlock));

	mze_tofind.mze_hash = hash;

	mze_tofind.mze_cd = 0;

	cd = 0;

	for (mze = avl_find(avl, &mze_tofind, &idx);

	    mze && mze->mze_hash == hash; mze = AVL_NEXT(avl, mze)) {

		if (mze->mze_cd != cd)

			break;

		cd++;

	}

	return (cd);

}

static void

mze_remove(zap_t *zap, mzap_ent_t *mze)

{

	ASSERT(zap->zap_ismicro);

	ASSERT(RW_WRITE_HELD(&zap->zap_rwlock));

	avl_remove(&zap->zap_m.zap_avl, mze);

	kmem_free(mze, sizeof (mzap_ent_t));

}

static void

mze_destroy(zap_t *zap)

{

	mzap_ent_t *mze;

	void *avlcookie = NULL;

	while (mze = avl_destroy_nodes(&zap->zap_m.zap_avl, &avlcookie))

		kmem_free(mze, sizeof (mzap_ent_t));

	avl_destroy(&zap->zap_m.zap_avl);

}

static zap_t *

mzap_open(objset_t *os, uint64_t obj, dmu_buf_t *db)

{

	zap_t *winner;

	zap_t *zap;

	int i;

	ASSERT3U(MZAP_ENT_LEN, ==, sizeof (mzap_ent_phys_t));

	zap = kmem_zalloc(sizeof (zap_t), KM_SLEEP);

	rw_init(&zap->zap_rwlock, 0, 0, 0);

	rw_enter(&zap->zap_rwlock, RW_WRITER);

	zap->zap_objset = os;

	zap->zap_object = obj;

	zap->zap_dbuf = db;

	if (*(uint64_t *)db->db_data != ZBT_MICRO) {

		mutex_init(&zap->zap_f.zap_num_entries_mtx, 0, 0, 0);

		zap->zap_f.zap_block_shift = highbit(db->db_size) - 1;

	} else {

		zap->zap_ismicro = TRUE;

	}

	/*

	 * Make sure that zap_ismicro is set before we let others see

	 * it, because zap_lockdir() checks zap_ismicro without the lock

	 * held.

	 */

	winner = dmu_buf_set_user(db, zap, &zap->zap_m.zap_phys, zap_evict);

	if (winner != NULL) {

		rw_exit(&zap->zap_rwlock);

		rw_destroy(&zap->zap_rwlock);

		if (!zap->zap_ismicro)

			mutex_destroy(&zap->zap_f.zap_num_entries_mtx);

		kmem_free(zap, sizeof (zap_t));

		return (winner);

	}

	if (zap->zap_ismicro) {

		zap->zap_salt = zap->zap_m.zap_phys->mz_salt;

		zap->zap_normflags = zap->zap_m.zap_phys->mz_normflags;

		zap->zap_m.zap_num_chunks = db->db_size / MZAP_ENT_LEN - 1;

		avl_create(&zap->zap_m.zap_avl, mze_compare,

		    sizeof (mzap_ent_t), offsetof(mzap_ent_t, mze_node));

		for (i = 0; i < zap->zap_m.zap_num_chunks; i++) {

			mzap_ent_phys_t *mze =

			    &zap->zap_m.zap_phys->mz_chunk[i];

			if (mze->mze_name[0]) {

				zap_name_t *zn;

				zap->zap_m.zap_num_entries++;

				zn = zap_name_alloc(zap, mze->mze_name,

				    MT_EXACT);

				mze_insert(zap, i, zn->zn_hash);

				zap_name_free(zn);

			}

		}

	} else {

		zap->zap_salt = zap->zap_f.zap_phys->zap_salt;

		zap->zap_normflags = zap->zap_f.zap_phys->zap_normflags;

		ASSERT3U(sizeof (struct zap_leaf_header), ==,

		    2*ZAP_LEAF_CHUNKSIZE);

		/*

		 * The embedded pointer table should not overlap the

		 * other members.

		 */

		ASSERT3P(&ZAP_EMBEDDED_PTRTBL_ENT(zap, 0), >,

		    &zap->zap_f.zap_phys->zap_salt);

		/*

		 * The embedded pointer table should end at the end of

		 * the block

		 */

		ASSERT3U((uintptr_t)&ZAP_EMBEDDED_PTRTBL_ENT(zap,

		    1<<ZAP_EMBEDDED_PTRTBL_SHIFT(zap)) -

		    (uintptr_t)zap->zap_f.zap_phys, ==,

		    zap->zap_dbuf->db_size);

	}

	rw_exit(&zap->zap_rwlock);

	return (zap);

}

int

zap_lockdir(objset_t *os, uint64_t obj, dmu_tx_t *tx,

    krw_t lti, boolean_t fatreader, boolean_t adding, zap_t **zapp)

{

	zap_t *zap;

	dmu_buf_t *db;

	krw_t lt;

	int err;

	*zapp = NULL;

	err = dmu_buf_hold(os, obj, 0, NULL, &db, DMU_READ_NO_PREFETCH);

	if (err)

		return (err);

#ifdef ZFS_DEBUG

	{

		dmu_object_info_t doi;

		dmu_object_info_from_db(db, &doi);

	}

#endif

	zap = dmu_buf_get_user(db);

	if (zap == NULL)

		zap = mzap_open(os, obj, db);

	/*

	 * We're checking zap_ismicro without the lock held, in order to

	 * tell what type of lock we want.  Once we have some sort of

	 * lock, see if it really is the right type.  In practice this

	 * can only be different if it was upgraded from micro to fat,

	 * and micro wanted WRITER but fat only needs READER.

	 */

	lt = (!zap->zap_ismicro && fatreader) ? RW_READER : lti;

	rw_enter(&zap->zap_rwlock, lt);

	if (lt != ((!zap->zap_ismicro && fatreader) ? RW_READER : lti)) {

		/* it was upgraded, now we only need reader */

		ASSERT(lt == RW_WRITER);

		ASSERT(RW_READER ==

		    (!zap->zap_ismicro && fatreader) ? RW_READER : lti);

		rw_downgrade(&zap->zap_rwlock);

		lt = RW_READER;

	}

	zap->zap_objset = os;

	if (lt == RW_WRITER)

		dmu_buf_will_dirty(db, tx);

	ASSERT3P(zap->zap_dbuf, ==, db);

	ASSERT(!zap->zap_ismicro ||

	    zap->zap_m.zap_num_entries <= zap->zap_m.zap_num_chunks);

	if (zap->zap_ismicro && tx && adding &&

	    zap->zap_m.zap_num_entries == zap->zap_m.zap_num_chunks) {

		uint64_t newsz = db->db_size + SPA_MINBLOCKSIZE;

		if (newsz > MZAP_MAX_BLKSZ) {

			dprintf("upgrading obj %llu: num_entries=%u\n",