/*

 * CDDL HEADER START

 *

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

 *

 * 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

 */

/*

 * Use is subject to license terms.

 */

#pragma ident	"%Z%%M%	%I%	%E% SMI"

/*

 * The 512-byte leaf is broken into 32 16-byte chunks.

 * chunk number n means l_chunk[n], even though the header precedes it.

 * the names are stored null-terminated.

 */

#include <sys/zfs_context.h>

#include <sys/zap.h>

#include <sys/zap_impl.h>

#include <sys/zap_leaf.h>

#include <sys/spa.h>

#include <sys/dmu.h>

#define	CHAIN_END 0xffff /* end of the chunk chain */

#define	MAX_ARRAY_BYTES (8<<10)

#define	NCHUNKS(bytes) (((bytes)+ZAP_LEAF_ARRAY_BYTES-1)/ZAP_LEAF_ARRAY_BYTES)

/*

 * XXX This will >> by a negative number when

 * lh_prefix_len > 64-ZAP_LEAF_HASH_SHIFT.

 */

#define	LEAF_HASH(l, h) \

#define	LEAF_HASH_ENTPTR(l, h) (&(l)->l_phys->l_hash[LEAF_HASH(l, h)])

/* #define	MEMCHECK */

static void

zap_memset(void *a, int c, size_t n)

{

	char *cp = a;

	char *cpend = cp + n;

	while (cp < cpend)

		*cp++ = c;

}

static void

stv(int len, void *addr, uint64_t value)

{

	switch (len) {

	case 1:

		*(uint8_t *)addr = value;

		return;

	case 2:

		*(uint16_t *)addr = value;

		return;

	case 4:

		*(uint32_t *)addr = value;

		return;

	case 8:

		*(uint64_t *)addr = value;

		return;

	}

	ASSERT(!"bad int len");

}

static uint64_t

ldv(int len, const void *addr)

{

	switch (len) {

	case 1:

		return (*(uint8_t *)addr);

	case 2:

		return (*(uint16_t *)addr);

	case 4:

		return (*(uint32_t *)addr);

	case 8:

		return (*(uint64_t *)addr);

	}

	ASSERT(!"bad int len");

	return (0xFEEDFACEDEADBEEF);

}

void

{

	int i;

	buf->l_hdr.lhr_block_type = 	BSWAP_64(buf->l_hdr.lhr_block_type);

	buf->l_hdr.lhr_next = 		BSWAP_64(buf->l_hdr.lhr_next);

	buf->l_hdr.lhr_prefix = 	BSWAP_64(buf->l_hdr.lhr_prefix);

	buf->l_hdr.lhr_magic = 		BSWAP_32(buf->l_hdr.lhr_magic);

	buf->l_hdr.lhr_nfree = 		BSWAP_16(buf->l_hdr.lhr_nfree);

	buf->l_hdr.lhr_nentries = 	BSWAP_16(buf->l_hdr.lhr_nentries);

	buf->l_hdr.lhr_prefix_len = 	BSWAP_16(buf->l_hdr.lhr_prefix_len);

	buf->l_hdr.lh_freelist = 	BSWAP_16(buf->l_hdr.lh_freelist);

		buf->l_hash[i] = BSWAP_16(buf->l_hash[i]);

		struct zap_leaf_entry *le;

			le->le_type = BSWAP_8(le->le_type);

			le->le_int_size = BSWAP_8(le->le_int_size);

			le->le_next = BSWAP_16(le->le_next);

			le->le_name_chunk = BSWAP_16(le->le_name_chunk);

			le->le_name_length = BSWAP_16(le->le_name_length);

			le->le_value_chunk = BSWAP_16(le->le_value_chunk);

			le->le_value_length = BSWAP_16(le->le_value_length);

			le->le_cd = BSWAP_32(le->le_cd);

			le->le_hash = BSWAP_64(le->le_hash);

			break;

			break;

			/* la_array doesn't need swapping */

			break;

		default:

			ASSERT(!"bad leaf type");

		}

	}

}

void

zap_leaf_init(zap_leaf_t *l)

{

	int i;

	zap_memset(&l->l_phys->l_hdr, 0, sizeof (struct zap_leaf_header));

	}

	l->lh_block_type = ZBT_LEAF;

	l->lh_magic = ZAP_LEAF_MAGIC;

}

zap_leaf_t *

zap_leaf_chainmore(zap_leaf_t *l, zap_leaf_t *nl)

{

	nl->lh_prefix = l->lh_prefix;

	nl->lh_prefix_len = l->lh_prefix_len;

	nl->l_next = l->l_next;

	l->l_next = nl;

	nl->lh_next = l->lh_next;

	l->lh_next = nl->l_blkid;

	return (nl);

}

/*

 * Routines which manipulate leaf chunks (l_chunk[]).

 */

static uint16_t

zap_leaf_chunk_alloc(zap_leaf_t *l)

{

	int chunk;

	ASSERT(l->lh_nfree > 0);

	chunk = l->l_phys->l_hdr.lh_freelist;

#ifdef MEMCHECK

#endif

	l->lh_nfree--;

	return (chunk);

}

static void

zap_leaf_chunk_free(zap_leaf_t *l, uint16_t chunk)

{

#ifdef MEMCHECK

#endif

	zlf->lf_next = l->l_phys->l_hdr.lh_freelist;

	bzero(zlf->lf_pad, sizeof (zlf->lf_pad)); /* help it to compress */

	l->l_phys->l_hdr.lh_freelist = chunk;

	l->lh_nfree++;

}

/*

 * Routines which manipulate leaf arrays (zap_leaf_array type chunks).

 */

static uint16_t

zap_leaf_array_create(const zap_entry_handle_t *zeh, const char *buf,

	int integer_size, int num_integers)

{

	uint16_t chunk_head;

	uint16_t *chunkp = &chunk_head;

	int byten = 0;

	uint64_t value;

	int shift = (integer_size-1)*8;

	int len = num_integers;

	zap_leaf_t *l = zeh->zeh_found_leaf;

	ASSERT3U(num_integers * integer_size, <, MAX_ARRAY_BYTES);

	while (len > 0) {

		uint16_t chunk = zap_leaf_chunk_alloc(l);

		int i;

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

			if (byten == 0)

				value = ldv(integer_size, buf);

			la->la_array[i] = (value & (0xff << shift)) >> shift;

			value <<= 8;

			if (++byten == integer_size) {

				byten = 0;

				buf += integer_size;

				if (--len == 0)

					break;

			}

		}

		*chunkp = chunk;

		chunkp = &la->la_next;

	}

	*chunkp = CHAIN_END;

	return (chunk_head);

}

static void

zap_leaf_array_free(zap_entry_handle_t *zeh, uint16_t *chunkp)

{

	uint16_t chunk = *chunkp;

	zap_leaf_t *l = zeh->zeh_found_leaf;

	*chunkp = CHAIN_END;

	while (chunk != CHAIN_END) {

		zap_leaf_chunk_free(l, chunk);

		chunk = nextchunk;

	}

}

/* array_len and buf_len are in integers, not bytes */

static void

zap_leaf_array_read(const zap_entry_handle_t *zeh, uint16_t chunk,

    int array_int_len, int array_len, int buf_int_len, uint64_t buf_len,

    char *buf)

{

	int len = MIN(array_len, buf_len);

	int byten = 0;

	uint64_t value = 0;

	zap_leaf_t *l = zeh->zeh_found_leaf;

	ASSERT3U(array_int_len, <=, buf_int_len);

	/* Fast path for one 8-byte integer */

	if (array_int_len == 8 && buf_int_len == 8 && len == 1) {

		uint8_t *ip = la->la_array;

		uint64_t *buf64 = (uint64_t *)buf;

		*buf64 = (uint64_t)ip[0] << 56 | (uint64_t)ip[1] << 48 |

		    (uint64_t)ip[2] << 40 | (uint64_t)ip[3] << 32 |

		    (uint64_t)ip[4] << 24 | (uint64_t)ip[5] << 16 |

		    (uint64_t)ip[6] << 8 | (uint64_t)ip[7];

		return;

	}

	/* Fast path for an array of 1-byte integers (eg. the entry name) */

	if (array_int_len == 1 && buf_int_len == 1 &&

	    buf_len > array_len + ZAP_LEAF_ARRAY_BYTES) {

		while (chunk != CHAIN_END) {

			struct zap_leaf_array *la =

			bcopy(la->la_array, buf, ZAP_LEAF_ARRAY_BYTES);

			buf += ZAP_LEAF_ARRAY_BYTES;

			chunk = la->la_next;

		}

		return;

	}

	while (len > 0) {

		int i;

		for (i = 0; i < ZAP_LEAF_ARRAY_BYTES && len > 0; i++) {

			value = (value << 8) | la->la_array[i];

			byten++;

			if (byten == array_int_len) {

				stv(buf_int_len, buf, value);

				byten = 0;

				len--;

				if (len == 0)

					return;

				buf += buf_int_len;

			}

		}

		chunk = la->la_next;

	}

}

/*

 * Only to be used on 8-bit arrays.

 * array_len is actual len in bytes (not encoded le_value_length).

 * buf is null-terminated.

 */

static int

zap_leaf_array_equal(const zap_entry_handle_t *zeh, int chunk,

    int array_len, const char *buf)

{

	int bseen = 0;

	zap_leaf_t *l = zeh->zeh_found_leaf;

	while (bseen < array_len) {

		int toread = MIN(array_len - bseen, ZAP_LEAF_ARRAY_BYTES);

		if (bcmp(la->la_array, buf + bseen, toread))

			break;

		chunk = la->la_next;

		bseen += toread;

	}

	return (bseen == array_len);

}

/*

 * Routines which manipulate leaf entries.

 */

int

zap_leaf_lookup(zap_leaf_t *l,

    const char *name, uint64_t h, zap_entry_handle_t *zeh)

{

	uint16_t *chunkp;

	struct zap_leaf_entry *le;

	zeh->zeh_head_leaf = l;

again:

	ASSERT3U(l->lh_magic, ==, ZAP_LEAF_MAGIC);

	for (chunkp = LEAF_HASH_ENTPTR(l, h);

	    *chunkp != CHAIN_END; chunkp = &le->le_next) {

		uint16_t chunk = *chunkp;

		if (le->le_hash != h)

			continue;

		zeh->zeh_found_leaf = l;

		if (zap_leaf_array_equal(zeh, le->le_name_chunk,

		    le->le_name_length, name)) {

			zeh->zeh_num_integers = le->le_value_length;

			zeh->zeh_integer_size = le->le_int_size;

			zeh->zeh_cd = le->le_cd;

			zeh->zeh_hash = le->le_hash;

			zeh->zeh_chunkp = chunkp;

			zeh->zeh_found_leaf = l;

			return (0);

		}

	}

	if (l->l_next) {

		l = l->l_next;

		goto again;

	}

	return (ENOENT);

}

/* Return (h1,cd1 >= h2,cd2) */

#define	HCD_GTEQ(h1, cd1, h2, cd2) \

	((h1 > h2) ? TRUE : ((h1 == h2 && cd1 >= cd2) ? TRUE : FALSE))

int

zap_leaf_lookup_closest(zap_leaf_t *l,

    uint64_t h, uint32_t cd, zap_entry_handle_t *zeh)

{

	uint16_t chunk;

	uint64_t besth = -1ULL;

	uint32_t bestcd = ZAP_MAXCD;

	uint16_t lh;

	struct zap_leaf_entry *le;

	zeh->zeh_head_leaf = l;

again:

	ASSERT3U(l->lh_magic, ==, ZAP_LEAF_MAGIC);

	for (lh = LEAF_HASH(l, h); lh <= bestlh; lh++) {

		for (chunk = l->l_phys->l_hash[lh];

		    chunk != CHAIN_END; chunk = le->le_next) {

			if (HCD_GTEQ(le->le_hash, le->le_cd, h, cd) &&

			    HCD_GTEQ(besth, bestcd, le->le_hash, le->le_cd)) {

				ASSERT3U(bestlh, >=, lh);

				bestlh = lh;

				besth = le->le_hash;

				bestcd = le->le_cd;

				zeh->zeh_num_integers = le->le_value_length;

				zeh->zeh_integer_size = le->le_int_size;

				zeh->zeh_cd = le->le_cd;

				zeh->zeh_hash = le->le_hash;

				zeh->zeh_fakechunk = chunk;

				zeh->zeh_chunkp = &zeh->zeh_fakechunk;

				zeh->zeh_found_leaf = l;

			}

		}

	}

	if (l->l_next) {

		l = l->l_next;

		goto again;

	}

	return (bestcd == ZAP_MAXCD ? ENOENT : 0);

}

int

zap_entry_read(const zap_entry_handle_t *zeh,

    uint8_t integer_size, uint64_t num_integers, void *buf)

{

	if (le->le_int_size > integer_size)

		return (EINVAL);

	zap_leaf_array_read(zeh, le->le_value_chunk, le->le_int_size,

	    le->le_value_length, integer_size, num_integers, buf);

	if (zeh->zeh_num_integers > num_integers)

		return (EOVERFLOW);

	return (0);

}

int

zap_entry_read_name(const zap_entry_handle_t *zeh, uint16_t buflen, char *buf)

{

	zap_leaf_array_read(zeh, le->le_name_chunk, 1,

	    le->le_name_length, 1, buflen, buf);

	if (le->le_name_length > buflen)

		return (EOVERFLOW);

	return (0);