/*

 * 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.

 */

/*

 * This file contains the top half of the zfs directory structure

 * implementation. The bottom half is in zap_leaf.c.

 *

 * The zdir is an extendable hash data structure. There is a table of

 * pointers to buckets (zap_t->zd_data->zd_leafs). The buckets are

 * each a constant size and hold a variable number of directory entries.

 * The buckets (aka "leaf nodes") are implemented in zap_leaf.c.

 *

 * The pointer table holds a power of 2 number of pointers.

 * (1<<zap_t->zd_data->zd_phys->zd_prefix_len).  The bucket pointed to

 * by the pointer at index i in the table holds entries whose hash value

 * has a zd_prefix_len - bit prefix

 */

#include <sys/spa.h>

#include <sys/dmu.h>

#include <sys/zfs_context.h>

#include <sys/zfs_znode.h>

#include <sys/fs/zfs.h>

#include <sys/zap.h>

#include <sys/refcount.h>

#include <sys/zap_impl.h>

#include <sys/zap_leaf.h>

int fzap_default_block_shift = 14; /* 16k blocksize */

static void zap_leaf_pageout(dmu_buf_t *db, void *vl);

static uint64_t zap_allocate_blocks(zap_t *zap, int nblocks);

void

fzap_byteswap(void *vbuf, size_t size)

{

	uint64_t block_type;

	block_type = *(uint64_t *)vbuf;

	if (block_type == ZBT_LEAF || block_type == BSWAP_64(ZBT_LEAF))

		zap_leaf_byteswap(vbuf, size);

	else {

		/* it's a ptrtbl block */

		byteswap_uint64_array(vbuf, size);

	}

}

void

fzap_upgrade(zap_t *zap, dmu_tx_t *tx, zap_flags_t flags)

{

	dmu_buf_t *db;

	zap_leaf_t *l;

	int i;

	zap_phys_t *zp;

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

	zap->zap_ismicro = FALSE;

	(void) dmu_buf_update_user(zap->zap_dbuf, zap, zap,

	    &zap->zap_f.zap_phys, zap_evict);

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

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

	zp = zap->zap_f.zap_phys;

	/*

	 * explicitly zero it since it might be coming from an

	 * initialized microzap

	 */

	bzero(zap->zap_dbuf->db_data, zap->zap_dbuf->db_size);

	zp->zap_block_type = ZBT_HEADER;

	zp->zap_magic = ZAP_MAGIC;

	zp->zap_ptrtbl.zt_shift = ZAP_EMBEDDED_PTRTBL_SHIFT(zap);

	zp->zap_freeblk = 2;		/* block 1 will be the first leaf */

	zp->zap_num_leafs = 1;

	zp->zap_num_entries = 0;

	zp->zap_salt = zap->zap_salt;

	zp->zap_normflags = zap->zap_normflags;

	zp->zap_flags = flags;

	/* block 1 will be the first leaf */

	for (i = 0; i < (1<<zp->zap_ptrtbl.zt_shift); i++)

		ZAP_EMBEDDED_PTRTBL_ENT(zap, i) = 1;

	/*

	 * set up block 1 - the first leaf

	 */

	VERIFY(0 == dmu_buf_hold(zap->zap_objset, zap->zap_object,

	    1<<FZAP_BLOCK_SHIFT(zap), FTAG, &db, DMU_READ_NO_PREFETCH));

	dmu_buf_will_dirty(db, tx);

	l = kmem_zalloc(sizeof (zap_leaf_t), KM_SLEEP);

	l->l_dbuf = db;

	l->l_phys = db->db_data;

	zap_leaf_init(l, zp->zap_normflags != 0);

	kmem_free(l, sizeof (zap_leaf_t));

	dmu_buf_rele(db, FTAG);

}

static int

zap_tryupgradedir(zap_t *zap, dmu_tx_t *tx)

{

	if (RW_WRITE_HELD(&zap->zap_rwlock))

		return (1);

	if (rw_tryupgrade(&zap->zap_rwlock)) {

		dmu_buf_will_dirty(zap->zap_dbuf, tx);

		return (1);

	}

	return (0);

}

/*

 * Generic routines for dealing with the pointer & cookie tables.

 */

static int

zap_table_grow(zap_t *zap, zap_table_phys_t *tbl,

    void (*transfer_func)(const uint64_t *src, uint64_t *dst, int n),

    dmu_tx_t *tx)

{

	uint64_t b, newblk;

	dmu_buf_t *db_old, *db_new;

	int err;

	int bs = FZAP_BLOCK_SHIFT(zap);

	int hepb = 1<<(bs-4);

	/* hepb = half the number of entries in a block */

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

	ASSERT(tbl->zt_blk != 0);

	ASSERT(tbl->zt_numblks > 0);

	if (tbl->zt_nextblk != 0) {

		newblk = tbl->zt_nextblk;

	} else {

		newblk = zap_allocate_blocks(zap, tbl->zt_numblks * 2);

		tbl->zt_nextblk = newblk;

		ASSERT3U(tbl->zt_blks_copied, ==, 0);

		dmu_prefetch(zap->zap_objset, zap->zap_object,

		    tbl->zt_blk << bs, tbl->zt_numblks << bs);

	}

	/*

	 * Copy the ptrtbl from the old to new location.

	 */

	b = tbl->zt_blks_copied;

	err = dmu_buf_hold(zap->zap_objset, zap->zap_object,

	    (tbl->zt_blk + b) << bs, FTAG, &db_old, DMU_READ_NO_PREFETCH);

	if (err)

		return (err);

	/* first half of entries in old[b] go to new[2*b+0] */

	VERIFY(0 == dmu_buf_hold(zap->zap_objset, zap->zap_object,

	    (newblk + 2*b+0) << bs, FTAG, &db_new, DMU_READ_NO_PREFETCH));

	dmu_buf_will_dirty(db_new, tx);

	transfer_func(db_old->db_data, db_new->db_data, hepb);

	dmu_buf_rele(db_new, FTAG);

	/* second half of entries in old[b] go to new[2*b+1] */

	VERIFY(0 == dmu_buf_hold(zap->zap_objset, zap->zap_object,

	    (newblk + 2*b+1) << bs, FTAG, &db_new, DMU_READ_NO_PREFETCH));

	dmu_buf_will_dirty(db_new, tx);

	transfer_func((uint64_t *)db_old->db_data + hepb,

	    db_new->db_data, hepb);

	dmu_buf_rele(db_new, FTAG);

	dmu_buf_rele(db_old, FTAG);

	tbl->zt_blks_copied++;

	dprintf("copied block %llu of %llu\n",

	    tbl->zt_blks_copied, tbl->zt_numblks);

	if (tbl->zt_blks_copied == tbl->zt_numblks) {

		(void) dmu_free_range(zap->zap_objset, zap->zap_object,

		    tbl->zt_blk << bs, tbl->zt_numblks << bs, tx);

		tbl->zt_blk = newblk;

		tbl->zt_numblks *= 2;

		tbl->zt_shift++;

		tbl->zt_nextblk = 0;

		tbl->zt_blks_copied = 0;

		dprintf("finished; numblocks now %llu (%lluk entries)\n",

		    tbl->zt_numblks, 1<<(tbl->zt_shift-10));

	}

	return (0);

}

static int

zap_table_store(zap_t *zap, zap_table_phys_t *tbl, uint64_t idx, uint64_t val,

    dmu_tx_t *tx)

{

	int err;

	uint64_t blk, off;

	int bs = FZAP_BLOCK_SHIFT(zap);

	dmu_buf_t *db;

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

	ASSERT(tbl->zt_blk != 0);

	dprintf("storing %llx at index %llx\n", val, idx);

	blk = idx >> (bs-3);

	off = idx & ((1<<(bs-3))-1);

	err = dmu_buf_hold(zap->zap_objset, zap->zap_object,

	    (tbl->zt_blk + blk) << bs, FTAG, &db, DMU_READ_NO_PREFETCH);

	if (err)

		return (err);

	dmu_buf_will_dirty(db, tx);

	if (tbl->zt_nextblk != 0) {

		uint64_t idx2 = idx * 2;

		uint64_t blk2 = idx2 >> (bs-3);

		uint64_t off2 = idx2 & ((1<<(bs-3))-1);

		dmu_buf_t *db2;

		err = dmu_buf_hold(zap->zap_objset, zap->zap_object,

		    (tbl->zt_nextblk + blk2) << bs, FTAG, &db2,

		    DMU_READ_NO_PREFETCH);

		if (err) {

			dmu_buf_rele(db, FTAG);

			return (err);

		}

		dmu_buf_will_dirty(db2, tx);

		((uint64_t *)db2->db_data)[off2] = val;

		((uint64_t *)db2->db_data)[off2+1] = val;

		dmu_buf_rele(db2, FTAG);

	}

	((uint64_t *)db->db_data)[off] = val;

	dmu_buf_rele(db, FTAG);

	return (0);

}

static int

zap_table_load(zap_t *zap, zap_table_phys_t *tbl, uint64_t idx, uint64_t *valp)

{

	uint64_t blk, off;

	int err;

	dmu_buf_t *db;

	int bs = FZAP_BLOCK_SHIFT(zap);

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

	blk = idx >> (bs-3);

	off = idx & ((1<<(bs-3))-1);

	err = dmu_buf_hold(zap->zap_objset, zap->zap_object,

	    (tbl->zt_blk + blk) << bs, FTAG, &db, DMU_READ_NO_PREFETCH);

	if (err)

		return (err);

	*valp = ((uint64_t *)db->db_data)[off];

	dmu_buf_rele(db, FTAG);

	if (tbl->zt_nextblk != 0) {

		/*

		 * read the nextblk for the sake of i/o error checking,

		 * so that zap_table_load() will catch errors for

		 * zap_table_store.

		 */

		blk = (idx*2) >> (bs-3);

		err = dmu_buf_hold(zap->zap_objset, zap->zap_object,

		    (tbl->zt_nextblk + blk) << bs, FTAG, &db,

		    DMU_READ_NO_PREFETCH);

		dmu_buf_rele(db, FTAG);

	}

	return (err);

}

/*

 * Routines for growing the ptrtbl.

 */

static void

zap_ptrtbl_transfer(const uint64_t *src, uint64_t *dst, int n)

{

	int i;

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

		uint64_t lb = src[i];

		dst[2*i+0] = lb;

		dst[2*i+1] = lb;

	}

}

static int

zap_grow_ptrtbl(zap_t *zap, dmu_tx_t *tx)

{

	/*

	 * The pointer table should never use more hash bits than we

	 * have (otherwise we'd be using useless zero bits to index it).

	 * If we are within 2 bits of running out, stop growing, since

	 * this is already an aberrant condition.

	 */

	if (zap->zap_f.zap_phys->zap_ptrtbl.zt_shift >= zap_hashbits(zap) - 2)

		return (ENOSPC);

	if (zap->zap_f.zap_phys->zap_ptrtbl.zt_numblks == 0) {

		/*

		 * We are outgrowing the "embedded" ptrtbl (the one

		 * stored in the header block).  Give it its own entire

		 * block, which will double the size of the ptrtbl.

		 */

		uint64_t newblk;

		dmu_buf_t *db_new;

		int err;

		ASSERT3U(zap->zap_f.zap_phys->zap_ptrtbl.zt_shift, ==,

		    ZAP_EMBEDDED_PTRTBL_SHIFT(zap));

		ASSERT3U(zap->zap_f.zap_phys->zap_ptrtbl.zt_blk, ==, 0);

		newblk = zap_allocate_blocks(zap, 1);

		err = dmu_buf_hold(zap->zap_objset, zap->zap_object,

		    newblk << FZAP_BLOCK_SHIFT(zap), FTAG, &db_new,

		    DMU_READ_NO_PREFETCH);

		if (err)

			return (err);

		dmu_buf_will_dirty(db_new, tx);

		zap_ptrtbl_transfer(&ZAP_EMBEDDED_PTRTBL_ENT(zap, 0),

		    db_new->db_data, 1 << ZAP_EMBEDDED_PTRTBL_SHIFT(zap));

		dmu_buf_rele(db_new, FTAG);

		zap->zap_f.zap_phys->zap_ptrtbl.zt_blk = newblk;

		zap->zap_f.zap_phys->zap_ptrtbl.zt_numblks = 1;

		zap->zap_f.zap_phys->zap_ptrtbl.zt_shift++;

		ASSERT3U(1ULL << zap->zap_f.zap_phys->zap_ptrtbl.zt_shift, ==,

		    zap->zap_f.zap_phys->zap_ptrtbl.zt_numblks <<

		    (FZAP_BLOCK_SHIFT(zap)-3));

		return (0);

	} else {

		return (zap_table_grow(zap, &zap->zap_f.zap_phys->zap_ptrtbl,

		    zap_ptrtbl_transfer, tx));

	}

}

static void

zap_increment_num_entries(zap_t *zap, int delta, dmu_tx_t *tx)

{

	dmu_buf_will_dirty(zap->zap_dbuf, tx);

	mutex_enter(&zap->zap_f.zap_num_entries_mtx);

	ASSERT(delta > 0 || zap->zap_f.zap_phys->zap_num_entries >= -delta);

	zap->zap_f.zap_phys->zap_num_entries += delta;

	mutex_exit(&zap->zap_f.zap_num_entries_mtx);

}

static uint64_t

zap_allocate_blocks(zap_t *zap, int nblocks)

{

	uint64_t newblk;

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

	newblk = zap->zap_f.zap_phys->zap_freeblk;

	zap->zap_f.zap_phys->zap_freeblk += nblocks;

	return (newblk);

}

static zap_leaf_t *

zap_create_leaf(zap_t *zap, dmu_tx_t *tx)

{

	void *winner;

	zap_leaf_t *l = kmem_alloc(sizeof (zap_leaf_t), KM_SLEEP);

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

	rw_init(&l->l_rwlock, 0, 0, 0);

	rw_enter(&l->l_rwlock, RW_WRITER);

	l->l_blkid = zap_allocate_blocks(zap, 1);

	l->l_dbuf = NULL;

	l->l_phys = NULL;

	VERIFY(0 == dmu_buf_hold(zap->zap_objset, zap->zap_object,

	    l->l_blkid << FZAP_BLOCK_SHIFT(zap), NULL, &l->l_dbuf,

	    DMU_READ_NO_PREFETCH));

	winner = dmu_buf_set_user(l->l_dbuf, l, &l->l_phys, zap_leaf_pageout);

	ASSERT(winner == NULL);

	dmu_buf_will_dirty(l->l_dbuf, tx);

	zap_leaf_init(l, zap->zap_normflags != 0);

	zap->zap_f.zap_phys->zap_num_leafs++;

	return (l);

}

int

fzap_count(zap_t *zap, uint64_t *count)

{

	ASSERT(!zap->zap_ismicro);

	mutex_enter(&zap->zap_f.zap_num_entries_mtx); /* unnecessary */

	*count = zap->zap_f.zap_phys->zap_num_entries;

	mutex_exit(&zap->zap_f.zap_num_entries_mtx);

	return (0);

}

/*

 * Routines for obtaining zap_leaf_t's

 */

void

zap_put_leaf(zap_leaf_t *l)

{

	rw_exit(&l->l_rwlock);

	dmu_buf_rele(l->l_dbuf, NULL);

}

_NOTE(ARGSUSED(0))

static void

zap_leaf_pageout(dmu_buf_t *db, void *vl)

{

	zap_leaf_t *l = vl;

	rw_destroy(&l->l_rwlock);

	kmem_free(l, sizeof (zap_leaf_t));

}

static zap_leaf_t *

zap_open_leaf(uint64_t blkid, dmu_buf_t *db)

{

	zap_leaf_t *l, *winner;

	ASSERT(blkid != 0);

	l = kmem_alloc(sizeof (zap_leaf_t), KM_SLEEP);

	rw_init(&l->l_rwlock, 0, 0, 0);

	rw_enter(&l->l_rwlock, RW_WRITER);

	l->l_blkid = blkid;

	l->l_bs = highbit(db->db_size)-1;

	l->l_dbuf = db;

	l->l_phys = NULL;

	winner = dmu_buf_set_user(db, l, &l->l_phys, zap_leaf_pageout);

	rw_exit(&l->l_rwlock);

	if (winner != NULL) {

		/* someone else set it first */

		zap_leaf_pageout(NULL, l);

		l = winner;

	}

	/*

	 * lhr_pad was previously used for the next leaf in the leaf

	 * chain.  There should be no chained leafs (as we have removed

	 * support for them).

	 */

	ASSERT3U(l->l_phys->l_hdr.lh_pad1, ==, 0);

	/*

	 * There should be more hash entries than there can be

	 * chunks to put in the hash table

	 */

	ASSERT3U(ZAP_LEAF_HASH_NUMENTRIES(l), >, ZAP_LEAF_NUMCHUNKS(l) / 3);

	/* The chunks should begin at the end of the hash table */

	ASSERT3P(&ZAP_LEAF_CHUNK(l, 0), ==,

	    &l->l_phys->l_hash[ZAP_LEAF_HASH_NUMENTRIES(l)]);

	/* The chunks should end at the end of the block */

	ASSERT3U((uintptr_t)&ZAP_LEAF_CHUNK(l, ZAP_LEAF_NUMCHUNKS(l)) -

	    (uintptr_t)l->l_phys, ==, l->l_dbuf->db_size);

	return (l);

}

static int

zap_get_leaf_byblk(zap_t *zap, uint64_t blkid, dmu_tx_t *tx, krw_t lt,

    zap_leaf_t **lp)

{

	dmu_buf_t *db;

	zap_leaf_t *l;

	int bs = FZAP_BLOCK_SHIFT(zap);

	int err;