fs/zfs/zap_leaf.c

	zap_leaf.c revision 9621b9b1b5a73bcacf144283477ff14c5845d6c4
/*
 * CDDL HEADER START
 *
 * The contents of this file are subject to the terms of the
 * Common Development and Distribution License, Version 1.0 only
 * (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 2005 Sun Microsystems, Inc.  All rights reserved.
 * 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 */

/* somewhat arbitrary, could go up to around 100k ... */
#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) \
    ((ZAP_LEAF_HASH_NUMENTRIES-1) & \
        ((h) >> (64 - ZAP_LEAF_HASH_SHIFT-(l)->lh_prefix_len)))

#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
zap_leaf_byteswap(zap_leaf_phys_t *buf)
{
    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);

    for (i = 0; i < ZAP_LEAF_HASH_NUMENTRIES; i++)
        buf->l_hash[i] = BSWAP_16(buf->l_hash[i]);

    for (i = 0; i < ZAP_LEAF_NUMCHUNKS; i++) {
        struct zap_leaf_entry *le;

        switch (buf->l_chunk[i].l_free.lf_type) {
        case ZAP_LEAF_ENTRY:
            le = &buf->l_chunk[i].l_entry;

            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;
        case ZAP_LEAF_FREE:
            buf->l_chunk[i].l_free.lf_type =
                BSWAP_8(buf->l_chunk[i].l_free.lf_type);
            buf->l_chunk[i].l_free.lf_next =
                BSWAP_16(buf->l_chunk[i].l_free.lf_next);
            break;
        case ZAP_LEAF_ARRAY:
            /* zap_leaf_array */
            buf->l_chunk[i].l_array.la_type =
                BSWAP_8(buf->l_chunk[i].l_array.la_type);
            buf->l_chunk[i].l_array.la_next =
                BSWAP_16(buf->l_chunk[i].l_array.la_next);
            /* la_array doesn't need swapping */
            break;
        default:
            ASSERT(!"bad leaf type");
        }
    }
}

void
zap_leaf_init(zap_leaf_t *l)
{
    int i;

    ASSERT3U(sizeof (zap_leaf_phys_t), ==, l->l_dbuf->db_size);
    zap_memset(&l->l_phys->l_hdr, 0, sizeof (struct zap_leaf_header));
    zap_memset(&l->l_phys->l_hash, CHAIN_END, sizeof (l->l_phys->l_hash));
    for (i = 0; i < ZAP_LEAF_NUMCHUNKS; i++) {
        l->l_phys->l_chunk[i].l_free.lf_type = ZAP_LEAF_FREE;
        l->l_phys->l_chunk[i].l_free.lf_next = i+1;
    }
    l->l_phys->l_chunk[ZAP_LEAF_NUMCHUNKS-1].l_free.lf_next = CHAIN_END;
    l->lh_block_type = ZBT_LEAF;
    l->lh_magic = ZAP_LEAF_MAGIC;
    l->lh_nfree = ZAP_LEAF_NUMCHUNKS;
}

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;
    ASSERT3U(chunk, <, ZAP_LEAF_NUMCHUNKS);
    ASSERT3U(l->l_phys->l_chunk[chunk].l_free.lf_type, ==, ZAP_LEAF_FREE);

    l->l_phys->l_hdr.lh_freelist = l->l_phys->l_chunk[chunk].l_free.lf_next;

#ifdef MEMCHECK
    zap_memset(&l->l_phys->l_chunk[chunk], 0xa1,
        sizeof (l->l_phys->l_chunk[chunk]));
#endif

    l->lh_nfree--;

    return (chunk);
}

static void
zap_leaf_chunk_free(zap_leaf_t *l, uint16_t chunk)
{
    struct zap_leaf_free *zlf = &l->l_phys->l_chunk[chunk].l_free;
    ASSERT3U(l->lh_nfree, <, ZAP_LEAF_NUMCHUNKS);
    ASSERT3U(chunk, <, ZAP_LEAF_NUMCHUNKS);
    ASSERT(zlf->lf_type != ZAP_LEAF_FREE);

#ifdef MEMCHECK
    zap_memset(&l->l_phys->l_chunk[chunk], 0xf4,
        sizeof (l->l_phys->l_chunk[chunk]));
#endif

    zlf->lf_type = ZAP_LEAF_FREE;
    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);
        struct zap_leaf_array *la = &l->l_phys->l_chunk[chunk].l_array;
        int i;

        la->la_type = ZAP_LEAF_ARRAY;
        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) {
        int nextchunk = l->l_phys->l_chunk[chunk].l_array.la_next;
        ASSERT3U(l->l_phys->l_chunk[chunk].l_array.la_type, ==,
            ZAP_LEAF_ARRAY);
        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) {
        struct zap_leaf_array *la = &l->l_phys->l_chunk[chunk].l_array;
        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 =
                &l->l_phys->l_chunk[chunk].l_array;
            bcopy(la->la_array, buf, ZAP_LEAF_ARRAY_BYTES);
            buf += ZAP_LEAF_ARRAY_BYTES;
            chunk = la->la_next;
        }
        return;
    }

    while (len > 0) {
        struct zap_leaf_array *la = &l->l_phys->l_chunk[chunk].l_array;
        int i;

        ASSERT3U(chunk, <, ZAP_LEAF_NUMCHUNKS);
        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) {
        struct zap_leaf_array *la = &l->l_phys->l_chunk[chunk].l_array;
        int toread = MIN(array_len - bseen, ZAP_LEAF_ARRAY_BYTES);
        ASSERT3U(chunk, <, ZAP_LEAF_NUMCHUNKS);
        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;
        le = &l->l_phys->l_chunk[chunk].l_entry;

        ASSERT3U(chunk, <, ZAP_LEAF_NUMCHUNKS);
        ASSERT3U(le->le_type, ==, ZAP_LEAF_ENTRY);

        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 bestlh = ZAP_LEAF_HASH_NUMENTRIES-1;
    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) {
            le = &l->l_phys->l_chunk[chunk].l_entry;

            ASSERT3U(chunk, <, ZAP_LEAF_NUMCHUNKS);
            ASSERT3U(le->le_type, ==, ZAP_LEAF_ENTRY);

            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)
{
    struct zap_leaf_entry *le;

    le = &zeh->zeh_found_leaf->l_phys->l_chunk[*zeh->zeh_chunkp].l_entry;
    ASSERT3U(le->le_type, ==, ZAP_LEAF_ENTRY);

    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)
{
    struct zap_leaf_entry *le;

    le = &zeh->zeh_found_leaf->l_phys->l_chunk[*zeh->zeh_chunkp].l_entry;
    ASSERT3U(le->le_type, ==, ZAP_LEAF_ENTRY);

    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);
}

int
zap_entry_update(zap_entry_handle_t *zeh,
    uint8_t integer_size, uint64_t num_integers, const void *buf)
{
    int delta_chunks;
    struct zap_leaf_entry *le;
    le = &zeh->zeh_found_leaf->l_phys->l_chunk[*zeh->zeh_chunkp].l_entry;

    delta_chunks = NCHUNKS(num_integers * integer_size) -
        NCHUNKS(le->le_value_length * le->le_int_size);

    if (zeh->zeh_found_leaf->lh_nfree < delta_chunks)
        return (EAGAIN);

    /*
     * We should search other chained leaves (via
     * zap_entry_remove,create?) otherwise returning EAGAIN will
     * just send us into an infinite loop if we have to chain
     * another leaf block, rather than being able to split this
     * block.
     */

    zap_leaf_array_free(zeh, &le->le_value_chunk);
    le->le_value_chunk =
        zap_leaf_array_create(zeh, buf, integer_size, num_integers);
    le->le_value_length = (num_integers*integer_size > MAX_ARRAY_BYTES) ?
        (MAX_ARRAY_BYTES + 1) : (num_integers);
    le->le_int_size = integer_size;
    return (0);
}

void
zap_entry_remove(zap_entry_handle_t *zeh)
{
    uint16_t entry_chunk;
    struct zap_leaf_entry *le;
    zap_leaf_t *l = zeh->zeh_found_leaf;

    ASSERT3P(zeh->zeh_chunkp, !=, &zeh->zeh_fakechunk);

    entry_chunk = *zeh->zeh_chunkp;
    le = &l->l_phys->l_chunk[entry_chunk].l_entry;
    ASSERT3U(le->le_type, ==, ZAP_LEAF_ENTRY);

    zap_leaf_array_free(zeh, &le->le_name_chunk);
    zap_leaf_array_free(zeh, &le->le_value_chunk);

    *zeh->zeh_chunkp = le->le_next;
    zap_leaf_chunk_free(l, entry_chunk);

    l->lh_nentries--;
}

int
zap_entry_create(zap_leaf_t *l, const char *name, uint64_t h, uint32_t cd,
    uint8_t integer_size, uint64_t num_integers, const void *buf,
    zap_entry_handle_t *zeh)
{
    uint16_t chunk;
    uint16_t *chunkp;
    struct zap_leaf_entry *le;
    uint64_t namelen, valuelen;
    int numchunks;

    valuelen = integer_size * num_integers;
    namelen = strlen(name) + 1;
    ASSERT(namelen >= 2);

    zeh->zeh_head_leaf = l;

    if (namelen > MAXNAMELEN)
        return (ENAMETOOLONG);
    /* find the first leaf in the chain that has sufficient free space */
    numchunks = 1 + NCHUNKS(namelen) + NCHUNKS(valuelen);
    if (numchunks > ZAP_LEAF_NUMCHUNKS)
        return (E2BIG);

    if (cd == ZAP_MAXCD) {
        for (cd = 0; cd < ZAP_MAXCD; cd++) {
            zap_leaf_t *ll;
            for (ll = l; ll; ll = ll->l_next) {
                for (chunk = *LEAF_HASH_ENTPTR(ll, h);
                    chunk != CHAIN_END; chunk = le->le_next) {
                    le = &ll->l_phys->l_chunk
                        [chunk].l_entry;
                    if (le->le_hash == h &&
                        le->le_cd == cd) {
                        break;
                    }
                }
                /*
                 * if this cd is in use, no need to
                 * check more chained leafs
                 */
                if (chunk != CHAIN_END)
                    break;
            }
            /* If this cd is not in use, we are good. */
            if (chunk == CHAIN_END)
                break;
        }
        /* If we tried all the cd's, we lose. */
        if (cd == ZAP_MAXCD)
            return (ENOSPC);
    }

    for (; l; l = l->l_next)
        if (l->lh_nfree >= numchunks)
            break;
    if (l == NULL)
        return (EAGAIN);

    zeh->zeh_found_leaf = l;

    /* make the entry */
    chunk = zap_leaf_chunk_alloc(l);
    le = &l->l_phys->l_chunk[chunk].l_entry;
    le->le_type = ZAP_LEAF_ENTRY;
    le->le_name_chunk = zap_leaf_array_create(zeh, name, 1, namelen);
    le->le_name_length = namelen;
    le->le_value_chunk =
        zap_leaf_array_create(zeh, buf, integer_size, num_integers);
    le->le_value_length = (num_integers*integer_size > MAX_ARRAY_BYTES) ?
        (MAX_ARRAY_BYTES + 1) : (num_integers);
    le->le_int_size = integer_size;
    le->le_hash = h;
    le->le_cd = cd;

    /* link it into the hash chain */
    chunkp = LEAF_HASH_ENTPTR(l, h);
    le->le_next = *chunkp;
    *chunkp = chunk;

    l->lh_nentries++;

    zeh->zeh_num_integers = num_integers;
    zeh->zeh_integer_size = le->le_int_size;
    zeh->zeh_cd = le->le_cd;
    zeh->zeh_hash = le->le_hash;
    zeh->zeh_chunkp = chunkp;

    return (0);
}

/*
 * Routines for transferring entries between leafs.
 */

static void
zap_leaf_rehash_entry(zap_leaf_t *l, uint16_t entry)
{
    struct zap_leaf_entry *le = &l->l_phys->l_chunk[entry].l_entry;
    uint16_t *ptr = LEAF_HASH_ENTPTR(l, le->le_hash);
    le->le_next = *ptr;
    *ptr = entry;
}

static void
zap_leaf_rehash_entries(zap_leaf_t *l)
{
    int i;

    if (l->lh_nentries == 0)
        return;

    /* break existing hash chains */
    zap_memset(l->l_phys->l_hash, CHAIN_END, sizeof (l->l_phys->l_hash));

    for (i = 0; i < ZAP_LEAF_NUMCHUNKS; i++) {
        struct zap_leaf_entry *le = &l->l_phys->l_chunk[i].l_entry;
        if (le->le_type != ZAP_LEAF_ENTRY)
            continue;
        zap_leaf_rehash_entry(l, i);
    }
}

static uint16_t
zap_leaf_transfer_array(zap_leaf_t *l, uint16_t chunk, zap_leaf_t *nl)
{
    uint16_t new_chunk;
    uint16_t *nchunkp = &new_chunk;

    while (chunk != CHAIN_END) {
        uint16_t nchunk = zap_leaf_chunk_alloc(nl);
        struct zap_leaf_array *nla =
            &nl->l_phys->l_chunk[nchunk].l_array;
        struct zap_leaf_array *la =
            &l->l_phys->l_chunk[chunk].l_array;
        int nextchunk = la->la_next;

        ASSERT3U(chunk, <, ZAP_LEAF_NUMCHUNKS);
        ASSERT3U(nchunk, <, ZAP_LEAF_NUMCHUNKS);

        *nla = *la;

        zap_leaf_chunk_free(l, chunk);
        chunk = nextchunk;
        *nchunkp = nchunk;
        nchunkp = &nla->la_next;
    }
    *nchunkp = CHAIN_END;
    return (new_chunk);
}

static void
zap_leaf_transfer_entry(zap_t *zap, zap_leaf_t *l, int entry, zap_leaf_t *nhl,
    dmu_tx_t *tx)
{
    zap_leaf_t *nl;
    struct zap_leaf_entry *le, *nle;
    uint16_t chunk, nchunks;

    le = &l->l_phys->l_chunk[entry].l_entry;
    ASSERT3U(le->le_type, ==, ZAP_LEAF_ENTRY);

    /* find a leaf in the destination leaf chain with enough free space */
    nchunks = 1 + NCHUNKS(le->le_name_length) +
        NCHUNKS(le->le_value_length * le->le_int_size);
    for (nl = nhl; nl; nl = nl->l_next)
        if (nl->lh_nfree >= nchunks)
            break;
    if (nl == NULL) {
        nl = zap_leaf_chainmore(nhl, zap_create_leaf(zap, tx));
        dprintf("transfer_entry: chaining leaf %x/%d\n",
            nl->lh_prefix, nl->lh_prefix_len);
    }

    chunk = zap_leaf_chunk_alloc(nl);
    nle = &nl->l_phys->l_chunk[chunk].l_entry;
    *nle = *le;

    zap_leaf_rehash_entry(nl, chunk);

    nle->le_name_chunk = zap_leaf_transfer_array(l, le->le_name_chunk, nl);
    nle->le_value_chunk =
        zap_leaf_transfer_array(l, le->le_value_chunk, nl);

    zap_leaf_chunk_free(l, entry);

    l->lh_nentries--;
    nl->lh_nentries++;
}

/*
 * Transfer entries whose hash bit 'bit' is 1 to nl1, and 0 to nl0.
 * Ignore leaf chaining in source (l), but chain in destinations.
 * We'll re-chain all the entries in l as we go along.
 */
static void
zap_leaf_transfer_entries(zap_t *zap, zap_leaf_t *l,
    zap_leaf_t *nl0, zap_leaf_t *nl1, int bit, dmu_tx_t *tx)
{
    int i;

    ASSERT(bit < 64 && bit >= 0);
    /* break existing hash chains */
    zap_memset(l->l_phys->l_hash, CHAIN_END, sizeof (l->l_phys->l_hash));

    if (nl0 != l)
        zap_leaf_rehash_entries(nl0);
    if (nl1 != nl0)
        zap_leaf_rehash_entries(nl1);

    for (i = 0; i < ZAP_LEAF_NUMCHUNKS; i++) {
        struct zap_leaf_entry *le = &l->l_phys->l_chunk[i].l_entry;
        if (le->le_type != ZAP_LEAF_ENTRY)
            continue;

        /*
         * We could find entries via hashtable instead. That
         * would be O(hashents+numents) rather than
         * O(numblks+numents), but this accesses memory more
         * sequentially, and when we're called, the block is
         * usually pretty full.
         */

        if (le->le_hash & (1ULL << bit)) {
            zap_leaf_transfer_entry(zap, l, i, nl1, tx);
        } else {
            if (nl0 == l)
                zap_leaf_rehash_entry(l, i);
            else
                zap_leaf_transfer_entry(zap, l, i, nl0, tx);
        }
    }

}

/*
 * nl will contain the entries whose hash prefix ends in 1
 * handles leaf chaining
 */
zap_leaf_t *
zap_leaf_split(zap_t *zap, zap_leaf_t *hl, dmu_tx_t *tx)
{
    zap_leaf_t *l = hl;
    int bit = 64 - 1 - hl->lh_prefix_len;
    zap_leaf_t *nl = zap_create_leaf(zap, tx);

    /* set new prefix and prefix_len */
    hl->lh_prefix <<= 1;
    hl->lh_prefix_len++;
    nl->lh_prefix = hl->lh_prefix | 1;
    nl->lh_prefix_len = hl->lh_prefix_len;

    /* transfer odd entries from first leaf in hl chain to nl */
    zap_leaf_transfer_entries(zap, hl, hl, nl, bit, tx);

    /* take rest of chain off hl */
    l = hl->l_next;
    hl->l_next = NULL;
    hl->lh_next = 0;

    /* transfer even entries from hl chain back to hl, odd entries to nl */
    while (l) {
        zap_leaf_t *next = l->l_next;
        zap_leaf_transfer_entries(zap, l, hl, nl, bit, tx);
        zap_destroy_leaf(zap, l, tx);
        l = next;
    }

    return (nl);
}

void
zap_stats_leaf(zap_t *zap, zap_leaf_t *l, zap_stats_t *zs)
{
    int n, nchained = 0;

    n = zap->zap_f.zap_phys->zap_ptrtbl.zt_shift - l->lh_prefix_len;
    n = MIN(n, ZAP_HISTOGRAM_SIZE-1);
    zs->zs_leafs_with_2n_pointers[n]++;

    do {
        int i;

        n = l->lh_nentries/5;
        n = MIN(n, ZAP_HISTOGRAM_SIZE-1);
        zs->zs_blocks_with_n5_entries[n]++;

        n = ((1<<ZAP_BLOCK_SHIFT) -
            l->lh_nfree * (ZAP_LEAF_ARRAY_BYTES+1))*10 /
            (1<<ZAP_BLOCK_SHIFT);
        n = MIN(n, ZAP_HISTOGRAM_SIZE-1);
        zs->zs_blocks_n_tenths_full[n]++;

        for (i = 0; i < ZAP_LEAF_HASH_NUMENTRIES; i++) {
            int nentries = 0;
            int chunk = l->l_phys->l_hash[i];

            while (chunk != CHAIN_END) {
                struct zap_leaf_entry *le =
                    &l->l_phys->l_chunk[chunk].l_entry;

                n = 1 + NCHUNKS(le->le_name_length) +
                    NCHUNKS(le->le_value_length *
                    le->le_int_size);
                n = MIN(n, ZAP_HISTOGRAM_SIZE-1);
                zs->zs_entries_using_n_chunks[n]++;

                chunk = le->le_next;
                nentries++;
            }

            n = nentries;
            n = MIN(n, ZAP_HISTOGRAM_SIZE-1);
            zs->zs_buckets_with_n_entries[n]++;
        }

        nchained++;
        l = l->l_next;
    } while (l);

    n = nchained-1;
    n = MIN(n, ZAP_HISTOGRAM_SIZE-1);
    zs->zs_leafs_with_n_chained[n]++;
}