xref: /illumos-gate/usr/src/uts/common/fs/zfs/zap_leaf.c (revision 5ad82045)
1fa9e4066Sahrens /*
2fa9e4066Sahrens  * CDDL HEADER START
3fa9e4066Sahrens  *
4fa9e4066Sahrens  * The contents of this file are subject to the terms of the
5f65e61c0Sahrens  * Common Development and Distribution License (the "License").
6f65e61c0Sahrens  * You may not use this file except in compliance with the License.
7fa9e4066Sahrens  *
8fa9e4066Sahrens  * You can obtain a copy of the license at usr/src/OPENSOLARIS.LICENSE
9fa9e4066Sahrens  * or http://www.opensolaris.org/os/licensing.
10fa9e4066Sahrens  * See the License for the specific language governing permissions
11fa9e4066Sahrens  * and limitations under the License.
12fa9e4066Sahrens  *
13fa9e4066Sahrens  * When distributing Covered Code, include this CDDL HEADER in each
14fa9e4066Sahrens  * file and include the License file at usr/src/OPENSOLARIS.LICENSE.
15fa9e4066Sahrens  * If applicable, add the following below this CDDL HEADER, with the
16fa9e4066Sahrens  * fields enclosed by brackets "[]" replaced with your own identifying
17fa9e4066Sahrens  * information: Portions Copyright [yyyy] [name of copyright owner]
18fa9e4066Sahrens  *
19fa9e4066Sahrens  * CDDL HEADER END
20fa9e4066Sahrens  */
21fa9e4066Sahrens /*
22f65e61c0Sahrens  * Copyright 2006 Sun Microsystems, Inc.  All rights reserved.
23fa9e4066Sahrens  * Use is subject to license terms.
24fa9e4066Sahrens  */
25fa9e4066Sahrens 
26fa9e4066Sahrens #pragma ident	"%Z%%M%	%I%	%E% SMI"
27fa9e4066Sahrens 
28fa9e4066Sahrens /*
29fa9e4066Sahrens  * The 512-byte leaf is broken into 32 16-byte chunks.
30fa9e4066Sahrens  * chunk number n means l_chunk[n], even though the header precedes it.
31fa9e4066Sahrens  * the names are stored null-terminated.
32fa9e4066Sahrens  */
33fa9e4066Sahrens 
34fa9e4066Sahrens #include <sys/zfs_context.h>
35fa9e4066Sahrens #include <sys/zap.h>
36fa9e4066Sahrens #include <sys/zap_impl.h>
37fa9e4066Sahrens #include <sys/zap_leaf.h>
38fa9e4066Sahrens #include <sys/spa.h>
39fa9e4066Sahrens #include <sys/dmu.h>
40fa9e4066Sahrens 
41fa9e4066Sahrens #define	CHAIN_END 0xffff /* end of the chunk chain */
42fa9e4066Sahrens 
43f65e61c0Sahrens /* half the (current) minimum block size */
44fa9e4066Sahrens #define	MAX_ARRAY_BYTES (8<<10)
45fa9e4066Sahrens 
46fa9e4066Sahrens #define	LEAF_HASH(l, h) \
47f65e61c0Sahrens 	((ZAP_LEAF_HASH_NUMENTRIES(l)-1) & \
4866328dd3Sahrens 	((h) >> (64 - ZAP_LEAF_HASH_SHIFT(l)-(l)->l_phys->l_hdr.lh_prefix_len)))
49fa9e4066Sahrens 
50fa9e4066Sahrens #define	LEAF_HASH_ENTPTR(l, h) (&(l)->l_phys->l_hash[LEAF_HASH(l, h)])
51fa9e4066Sahrens 
52fa9e4066Sahrens 
53fa9e4066Sahrens static void
54fa9e4066Sahrens zap_memset(void *a, int c, size_t n)
55fa9e4066Sahrens {
56fa9e4066Sahrens 	char *cp = a;
57fa9e4066Sahrens 	char *cpend = cp + n;
58fa9e4066Sahrens 
59fa9e4066Sahrens 	while (cp < cpend)
60fa9e4066Sahrens 		*cp++ = c;
61fa9e4066Sahrens }
62fa9e4066Sahrens 
63fa9e4066Sahrens static void
64fa9e4066Sahrens stv(int len, void *addr, uint64_t value)
65fa9e4066Sahrens {
66fa9e4066Sahrens 	switch (len) {
67fa9e4066Sahrens 	case 1:
68fa9e4066Sahrens 		*(uint8_t *)addr = value;
69fa9e4066Sahrens 		return;
70fa9e4066Sahrens 	case 2:
71fa9e4066Sahrens 		*(uint16_t *)addr = value;
72fa9e4066Sahrens 		return;
73fa9e4066Sahrens 	case 4:
74fa9e4066Sahrens 		*(uint32_t *)addr = value;
75fa9e4066Sahrens 		return;
76fa9e4066Sahrens 	case 8:
77fa9e4066Sahrens 		*(uint64_t *)addr = value;
78fa9e4066Sahrens 		return;
79fa9e4066Sahrens 	}
80fa9e4066Sahrens 	ASSERT(!"bad int len");
81fa9e4066Sahrens }
82fa9e4066Sahrens 
83fa9e4066Sahrens static uint64_t
84fa9e4066Sahrens ldv(int len, const void *addr)
85fa9e4066Sahrens {
86fa9e4066Sahrens 	switch (len) {
87fa9e4066Sahrens 	case 1:
88fa9e4066Sahrens 		return (*(uint8_t *)addr);
89fa9e4066Sahrens 	case 2:
90fa9e4066Sahrens 		return (*(uint16_t *)addr);
91fa9e4066Sahrens 	case 4:
92fa9e4066Sahrens 		return (*(uint32_t *)addr);
93fa9e4066Sahrens 	case 8:
94fa9e4066Sahrens 		return (*(uint64_t *)addr);
95fa9e4066Sahrens 	}
96fa9e4066Sahrens 	ASSERT(!"bad int len");
97*5ad82045Snd 	return (0xFEEDFACEDEADBEEFULL);
98fa9e4066Sahrens }
99fa9e4066Sahrens 
100fa9e4066Sahrens void
101f65e61c0Sahrens zap_leaf_byteswap(zap_leaf_phys_t *buf, int size)
102fa9e4066Sahrens {
103fa9e4066Sahrens 	int i;
104f65e61c0Sahrens 	zap_leaf_t l;
105f65e61c0Sahrens 	l.l_bs = highbit(size)-1;
106f65e61c0Sahrens 	l.l_phys = buf;
107fa9e4066Sahrens 
10866328dd3Sahrens 	buf->l_hdr.lh_block_type = 	BSWAP_64(buf->l_hdr.lh_block_type);
10966328dd3Sahrens 	buf->l_hdr.lh_prefix = 		BSWAP_64(buf->l_hdr.lh_prefix);
11066328dd3Sahrens 	buf->l_hdr.lh_magic = 		BSWAP_32(buf->l_hdr.lh_magic);
11166328dd3Sahrens 	buf->l_hdr.lh_nfree = 		BSWAP_16(buf->l_hdr.lh_nfree);
11266328dd3Sahrens 	buf->l_hdr.lh_nentries = 	BSWAP_16(buf->l_hdr.lh_nentries);
11366328dd3Sahrens 	buf->l_hdr.lh_prefix_len = 	BSWAP_16(buf->l_hdr.lh_prefix_len);
114fa9e4066Sahrens 	buf->l_hdr.lh_freelist = 	BSWAP_16(buf->l_hdr.lh_freelist);
115fa9e4066Sahrens 
116f65e61c0Sahrens 	for (i = 0; i < ZAP_LEAF_HASH_NUMENTRIES(&l); i++)
117fa9e4066Sahrens 		buf->l_hash[i] = BSWAP_16(buf->l_hash[i]);
118fa9e4066Sahrens 
119f65e61c0Sahrens 	for (i = 0; i < ZAP_LEAF_NUMCHUNKS(&l); i++) {
120f65e61c0Sahrens 		zap_leaf_chunk_t *lc = &ZAP_LEAF_CHUNK(&l, i);
121fa9e4066Sahrens 		struct zap_leaf_entry *le;
122fa9e4066Sahrens 
123f65e61c0Sahrens 		switch (lc->l_free.lf_type) {
124f65e61c0Sahrens 		case ZAP_CHUNK_ENTRY:
125f65e61c0Sahrens 			le = &lc->l_entry;
126fa9e4066Sahrens 
12766328dd3Sahrens 			le->le_type =		BSWAP_8(le->le_type);
12866328dd3Sahrens 			le->le_int_size =	BSWAP_8(le->le_int_size);
12966328dd3Sahrens 			le->le_next =		BSWAP_16(le->le_next);
13066328dd3Sahrens 			le->le_name_chunk =	BSWAP_16(le->le_name_chunk);
13166328dd3Sahrens 			le->le_name_length =	BSWAP_16(le->le_name_length);
13266328dd3Sahrens 			le->le_value_chunk =	BSWAP_16(le->le_value_chunk);
13366328dd3Sahrens 			le->le_value_length =	BSWAP_16(le->le_value_length);
13466328dd3Sahrens 			le->le_cd =		BSWAP_32(le->le_cd);
13566328dd3Sahrens 			le->le_hash =		BSWAP_64(le->le_hash);
136fa9e4066Sahrens 			break;
137f65e61c0Sahrens 		case ZAP_CHUNK_FREE:
13866328dd3Sahrens 			lc->l_free.lf_type =	BSWAP_8(lc->l_free.lf_type);
13966328dd3Sahrens 			lc->l_free.lf_next =	BSWAP_16(lc->l_free.lf_next);
140fa9e4066Sahrens 			break;
141f65e61c0Sahrens 		case ZAP_CHUNK_ARRAY:
14266328dd3Sahrens 			lc->l_array.la_type =	BSWAP_8(lc->l_array.la_type);
14366328dd3Sahrens 			lc->l_array.la_next =	BSWAP_16(lc->l_array.la_next);
144fa9e4066Sahrens 			/* la_array doesn't need swapping */
145fa9e4066Sahrens 			break;
146fa9e4066Sahrens 		default:
147fa9e4066Sahrens 			ASSERT(!"bad leaf type");
148fa9e4066Sahrens 		}
149fa9e4066Sahrens 	}
150fa9e4066Sahrens }
151fa9e4066Sahrens 
152fa9e4066Sahrens void
153fa9e4066Sahrens zap_leaf_init(zap_leaf_t *l)
154fa9e4066Sahrens {
155fa9e4066Sahrens 	int i;
156fa9e4066Sahrens 
157f65e61c0Sahrens 	l->l_bs = highbit(l->l_dbuf->db_size)-1;
158fa9e4066Sahrens 	zap_memset(&l->l_phys->l_hdr, 0, sizeof (struct zap_leaf_header));
159f65e61c0Sahrens 	zap_memset(l->l_phys->l_hash, CHAIN_END, 2*ZAP_LEAF_HASH_NUMENTRIES(l));
160f65e61c0Sahrens 	for (i = 0; i < ZAP_LEAF_NUMCHUNKS(l); i++) {
161f65e61c0Sahrens 		ZAP_LEAF_CHUNK(l, i).l_free.lf_type = ZAP_CHUNK_FREE;
162f65e61c0Sahrens 		ZAP_LEAF_CHUNK(l, i).l_free.lf_next = i+1;
163fa9e4066Sahrens 	}
164f65e61c0Sahrens 	ZAP_LEAF_CHUNK(l, ZAP_LEAF_NUMCHUNKS(l)-1).l_free.lf_next = CHAIN_END;
16566328dd3Sahrens 	l->l_phys->l_hdr.lh_block_type = ZBT_LEAF;
16666328dd3Sahrens 	l->l_phys->l_hdr.lh_magic = ZAP_LEAF_MAGIC;
16766328dd3Sahrens 	l->l_phys->l_hdr.lh_nfree = ZAP_LEAF_NUMCHUNKS(l);
168fa9e4066Sahrens }
169fa9e4066Sahrens 
170fa9e4066Sahrens /*
171fa9e4066Sahrens  * Routines which manipulate leaf chunks (l_chunk[]).
172fa9e4066Sahrens  */
173fa9e4066Sahrens 
174fa9e4066Sahrens static uint16_t
175fa9e4066Sahrens zap_leaf_chunk_alloc(zap_leaf_t *l)
176fa9e4066Sahrens {
177fa9e4066Sahrens 	int chunk;
178fa9e4066Sahrens 
17966328dd3Sahrens 	ASSERT(l->l_phys->l_hdr.lh_nfree > 0);
180fa9e4066Sahrens 
181fa9e4066Sahrens 	chunk = l->l_phys->l_hdr.lh_freelist;
182f65e61c0Sahrens 	ASSERT3U(chunk, <, ZAP_LEAF_NUMCHUNKS(l));
183f65e61c0Sahrens 	ASSERT3U(ZAP_LEAF_CHUNK(l, chunk).l_free.lf_type, ==, ZAP_CHUNK_FREE);
184fa9e4066Sahrens 
185f65e61c0Sahrens 	l->l_phys->l_hdr.lh_freelist = ZAP_LEAF_CHUNK(l, chunk).l_free.lf_next;
186fa9e4066Sahrens 
18766328dd3Sahrens 	l->l_phys->l_hdr.lh_nfree--;
188fa9e4066Sahrens 
189fa9e4066Sahrens 	return (chunk);
190fa9e4066Sahrens }
191fa9e4066Sahrens 
192fa9e4066Sahrens static void
193fa9e4066Sahrens zap_leaf_chunk_free(zap_leaf_t *l, uint16_t chunk)
194fa9e4066Sahrens {
195f65e61c0Sahrens 	struct zap_leaf_free *zlf = &ZAP_LEAF_CHUNK(l, chunk).l_free;
19666328dd3Sahrens 	ASSERT3U(l->l_phys->l_hdr.lh_nfree, <, ZAP_LEAF_NUMCHUNKS(l));
197f65e61c0Sahrens 	ASSERT3U(chunk, <, ZAP_LEAF_NUMCHUNKS(l));
198f65e61c0Sahrens 	ASSERT(zlf->lf_type != ZAP_CHUNK_FREE);
199fa9e4066Sahrens 
200f65e61c0Sahrens 	zlf->lf_type = ZAP_CHUNK_FREE;
201fa9e4066Sahrens 	zlf->lf_next = l->l_phys->l_hdr.lh_freelist;
202fa9e4066Sahrens 	bzero(zlf->lf_pad, sizeof (zlf->lf_pad)); /* help it to compress */
203fa9e4066Sahrens 	l->l_phys->l_hdr.lh_freelist = chunk;
204fa9e4066Sahrens 
20566328dd3Sahrens 	l->l_phys->l_hdr.lh_nfree++;
206fa9e4066Sahrens }
207fa9e4066Sahrens 
208fa9e4066Sahrens /*
209fa9e4066Sahrens  * Routines which manipulate leaf arrays (zap_leaf_array type chunks).
210fa9e4066Sahrens  */
211fa9e4066Sahrens 
212fa9e4066Sahrens static uint16_t
21366328dd3Sahrens zap_leaf_array_create(zap_leaf_t *l, const char *buf,
214fa9e4066Sahrens 	int integer_size, int num_integers)
215fa9e4066Sahrens {
216fa9e4066Sahrens 	uint16_t chunk_head;
217fa9e4066Sahrens 	uint16_t *chunkp = &chunk_head;
218fa9e4066Sahrens 	int byten = 0;
219fa9e4066Sahrens 	uint64_t value;
220fa9e4066Sahrens 	int shift = (integer_size-1)*8;
221fa9e4066Sahrens 	int len = num_integers;
222fa9e4066Sahrens 
223fa9e4066Sahrens 	ASSERT3U(num_integers * integer_size, <, MAX_ARRAY_BYTES);
224fa9e4066Sahrens 
225fa9e4066Sahrens 	while (len > 0) {
226fa9e4066Sahrens 		uint16_t chunk = zap_leaf_chunk_alloc(l);
227f65e61c0Sahrens 		struct zap_leaf_array *la = &ZAP_LEAF_CHUNK(l, chunk).l_array;
228fa9e4066Sahrens 		int i;
229fa9e4066Sahrens 
230f65e61c0Sahrens 		la->la_type = ZAP_CHUNK_ARRAY;
231fa9e4066Sahrens 		for (i = 0; i < ZAP_LEAF_ARRAY_BYTES; i++) {
232fa9e4066Sahrens 			if (byten == 0)
233fa9e4066Sahrens 				value = ldv(integer_size, buf);
234fa9e4066Sahrens 			la->la_array[i] = (value & (0xff << shift)) >> shift;
235fa9e4066Sahrens 			value <<= 8;
236fa9e4066Sahrens 			if (++byten == integer_size) {
237fa9e4066Sahrens 				byten = 0;
238fa9e4066Sahrens 				buf += integer_size;
239fa9e4066Sahrens 				if (--len == 0)
240fa9e4066Sahrens 					break;
241fa9e4066Sahrens 			}
242fa9e4066Sahrens 		}
243fa9e4066Sahrens 
244fa9e4066Sahrens 		*chunkp = chunk;
245fa9e4066Sahrens 		chunkp = &la->la_next;
246fa9e4066Sahrens 	}
247fa9e4066Sahrens 	*chunkp = CHAIN_END;
248fa9e4066Sahrens 
249fa9e4066Sahrens 	return (chunk_head);
250fa9e4066Sahrens }
251fa9e4066Sahrens 
252fa9e4066Sahrens static void
25366328dd3Sahrens zap_leaf_array_free(zap_leaf_t *l, uint16_t *chunkp)
254fa9e4066Sahrens {
255fa9e4066Sahrens 	uint16_t chunk = *chunkp;
256fa9e4066Sahrens 
257fa9e4066Sahrens 	*chunkp = CHAIN_END;
258fa9e4066Sahrens 
259fa9e4066Sahrens 	while (chunk != CHAIN_END) {
260f65e61c0Sahrens 		int nextchunk = ZAP_LEAF_CHUNK(l, chunk).l_array.la_next;
261f65e61c0Sahrens 		ASSERT3U(ZAP_LEAF_CHUNK(l, chunk).l_array.la_type, ==,
262f65e61c0Sahrens 		    ZAP_CHUNK_ARRAY);
263fa9e4066Sahrens 		zap_leaf_chunk_free(l, chunk);
264fa9e4066Sahrens 		chunk = nextchunk;
265fa9e4066Sahrens 	}
266fa9e4066Sahrens }
267fa9e4066Sahrens 
268fa9e4066Sahrens /* array_len and buf_len are in integers, not bytes */
269fa9e4066Sahrens static void
27066328dd3Sahrens zap_leaf_array_read(zap_leaf_t *l, uint16_t chunk,
271fa9e4066Sahrens     int array_int_len, int array_len, int buf_int_len, uint64_t buf_len,
272fa9e4066Sahrens     char *buf)
273fa9e4066Sahrens {
274fa9e4066Sahrens 	int len = MIN(array_len, buf_len);
275fa9e4066Sahrens 	int byten = 0;
276fa9e4066Sahrens 	uint64_t value = 0;
277fa9e4066Sahrens 
278fa9e4066Sahrens 	ASSERT3U(array_int_len, <=, buf_int_len);
279fa9e4066Sahrens 
28087e5029aSahrens 	/* Fast path for one 8-byte integer */
28187e5029aSahrens 	if (array_int_len == 8 && buf_int_len == 8 && len == 1) {
282f65e61c0Sahrens 		struct zap_leaf_array *la = &ZAP_LEAF_CHUNK(l, chunk).l_array;
2839621b9b1Sbonwick 		uint8_t *ip = la->la_array;
28487e5029aSahrens 		uint64_t *buf64 = (uint64_t *)buf;
2859621b9b1Sbonwick 
2869621b9b1Sbonwick 		*buf64 = (uint64_t)ip[0] << 56 | (uint64_t)ip[1] << 48 |
2879621b9b1Sbonwick 		    (uint64_t)ip[2] << 40 | (uint64_t)ip[3] << 32 |
2889621b9b1Sbonwick 		    (uint64_t)ip[4] << 24 | (uint64_t)ip[5] << 16 |
2899621b9b1Sbonwick 		    (uint64_t)ip[6] << 8 | (uint64_t)ip[7];
29087e5029aSahrens 		return;
29187e5029aSahrens 	}
29287e5029aSahrens 
29387e5029aSahrens 	/* Fast path for an array of 1-byte integers (eg. the entry name) */
29487e5029aSahrens 	if (array_int_len == 1 && buf_int_len == 1 &&
29587e5029aSahrens 	    buf_len > array_len + ZAP_LEAF_ARRAY_BYTES) {
29687e5029aSahrens 		while (chunk != CHAIN_END) {
29787e5029aSahrens 			struct zap_leaf_array *la =
298f65e61c0Sahrens 			    &ZAP_LEAF_CHUNK(l, chunk).l_array;
29987e5029aSahrens 			bcopy(la->la_array, buf, ZAP_LEAF_ARRAY_BYTES);
30087e5029aSahrens 			buf += ZAP_LEAF_ARRAY_BYTES;
30187e5029aSahrens 			chunk = la->la_next;
30287e5029aSahrens 		}
30387e5029aSahrens 		return;
30487e5029aSahrens 	}
30587e5029aSahrens 
306fa9e4066Sahrens 	while (len > 0) {
307f65e61c0Sahrens 		struct zap_leaf_array *la = &ZAP_LEAF_CHUNK(l, chunk).l_array;
308fa9e4066Sahrens 		int i;
309fa9e4066Sahrens 
310f65e61c0Sahrens 		ASSERT3U(chunk, <, ZAP_LEAF_NUMCHUNKS(l));
311fa9e4066Sahrens 		for (i = 0; i < ZAP_LEAF_ARRAY_BYTES && len > 0; i++) {
312fa9e4066Sahrens 			value = (value << 8) | la->la_array[i];
313fa9e4066Sahrens 			byten++;
314fa9e4066Sahrens 			if (byten == array_int_len) {
315fa9e4066Sahrens 				stv(buf_int_len, buf, value);
316fa9e4066Sahrens 				byten = 0;
317fa9e4066Sahrens 				len--;
318fa9e4066Sahrens 				if (len == 0)
319fa9e4066Sahrens 					return;
320fa9e4066Sahrens 				buf += buf_int_len;
321fa9e4066Sahrens 			}
322fa9e4066Sahrens 		}
323fa9e4066Sahrens 		chunk = la->la_next;
324fa9e4066Sahrens 	}
325fa9e4066Sahrens }
326fa9e4066Sahrens 
327fa9e4066Sahrens /*
328fa9e4066Sahrens  * Only to be used on 8-bit arrays.
329fa9e4066Sahrens  * array_len is actual len in bytes (not encoded le_value_length).
330fa9e4066Sahrens  * buf is null-terminated.
331fa9e4066Sahrens  */
332fa9e4066Sahrens static int
33366328dd3Sahrens zap_leaf_array_equal(zap_leaf_t *l, int chunk,
334fa9e4066Sahrens     int array_len, const char *buf)
335fa9e4066Sahrens {
336fa9e4066Sahrens 	int bseen = 0;
337fa9e4066Sahrens 
338fa9e4066Sahrens 	while (bseen < array_len) {
339f65e61c0Sahrens 		struct zap_leaf_array *la = &ZAP_LEAF_CHUNK(l, chunk).l_array;
340fa9e4066Sahrens 		int toread = MIN(array_len - bseen, ZAP_LEAF_ARRAY_BYTES);
341f65e61c0Sahrens 		ASSERT3U(chunk, <, ZAP_LEAF_NUMCHUNKS(l));
342fa9e4066Sahrens 		if (bcmp(la->la_array, buf + bseen, toread))
343fa9e4066Sahrens 			break;
344fa9e4066Sahrens 		chunk = la->la_next;
345fa9e4066Sahrens 		bseen += toread;
346fa9e4066Sahrens 	}
347fa9e4066Sahrens 	return (bseen == array_len);
348fa9e4066Sahrens }
349fa9e4066Sahrens 
350fa9e4066Sahrens /*
351fa9e4066Sahrens  * Routines which manipulate leaf entries.
352fa9e4066Sahrens  */
353fa9e4066Sahrens 
354fa9e4066Sahrens int
355fa9e4066Sahrens zap_leaf_lookup(zap_leaf_t *l,
356fa9e4066Sahrens     const char *name, uint64_t h, zap_entry_handle_t *zeh)
357fa9e4066Sahrens {
358fa9e4066Sahrens 	uint16_t *chunkp;
359fa9e4066Sahrens 	struct zap_leaf_entry *le;
360fa9e4066Sahrens 
36166328dd3Sahrens 	ASSERT3U(l->l_phys->l_hdr.lh_magic, ==, ZAP_LEAF_MAGIC);
362fa9e4066Sahrens 
363fa9e4066Sahrens 	for (chunkp = LEAF_HASH_ENTPTR(l, h);
364fa9e4066Sahrens 	    *chunkp != CHAIN_END; chunkp = &le->le_next) {
365fa9e4066Sahrens 		uint16_t chunk = *chunkp;
366f65e61c0Sahrens 		le = ZAP_LEAF_ENTRY(l, chunk);
367fa9e4066Sahrens 
368f65e61c0Sahrens 		ASSERT3U(chunk, <, ZAP_LEAF_NUMCHUNKS(l));
369f65e61c0Sahrens 		ASSERT3U(le->le_type, ==, ZAP_CHUNK_ENTRY);
370fa9e4066Sahrens 
371fa9e4066Sahrens 		if (le->le_hash != h)
372fa9e4066Sahrens 			continue;
373fa9e4066Sahrens 
37466328dd3Sahrens 		if (zap_leaf_array_equal(l, le->le_name_chunk,
375fa9e4066Sahrens 		    le->le_name_length, name)) {
376fa9e4066Sahrens 			zeh->zeh_num_integers = le->le_value_length;
377fa9e4066Sahrens 			zeh->zeh_integer_size = le->le_int_size;
378fa9e4066Sahrens 			zeh->zeh_cd = le->le_cd;
379fa9e4066Sahrens 			zeh->zeh_hash = le->le_hash;
380fa9e4066Sahrens 			zeh->zeh_chunkp = chunkp;
38166328dd3Sahrens 			zeh->zeh_leaf = l;
382fa9e4066Sahrens 			return (0);
383fa9e4066Sahrens 		}
384fa9e4066Sahrens 	}
385fa9e4066Sahrens 
386fa9e4066Sahrens 	return (ENOENT);
387fa9e4066Sahrens }
388fa9e4066Sahrens 
389fa9e4066Sahrens /* Return (h1,cd1 >= h2,cd2) */
39087e5029aSahrens #define	HCD_GTEQ(h1, cd1, h2, cd2) \
39187e5029aSahrens 	((h1 > h2) ? TRUE : ((h1 == h2 && cd1 >= cd2) ? TRUE : FALSE))
392fa9e4066Sahrens 
393fa9e4066Sahrens int
394fa9e4066Sahrens zap_leaf_lookup_closest(zap_leaf_t *l,
395fa9e4066Sahrens     uint64_t h, uint32_t cd, zap_entry_handle_t *zeh)
396fa9e4066Sahrens {
397fa9e4066Sahrens 	uint16_t chunk;
398fa9e4066Sahrens 	uint64_t besth = -1ULL;
399fa9e4066Sahrens 	uint32_t bestcd = ZAP_MAXCD;
400f65e61c0Sahrens 	uint16_t bestlh = ZAP_LEAF_HASH_NUMENTRIES(l)-1;
401fa9e4066Sahrens 	uint16_t lh;
402fa9e4066Sahrens 	struct zap_leaf_entry *le;
403fa9e4066Sahrens 
40466328dd3Sahrens 	ASSERT3U(l->l_phys->l_hdr.lh_magic, ==, ZAP_LEAF_MAGIC);
405fa9e4066Sahrens 
406fa9e4066Sahrens 	for (lh = LEAF_HASH(l, h); lh <= bestlh; lh++) {
407fa9e4066Sahrens 		for (chunk = l->l_phys->l_hash[lh];
408fa9e4066Sahrens 		    chunk != CHAIN_END; chunk = le->le_next) {
409f65e61c0Sahrens 			le = ZAP_LEAF_ENTRY(l, chunk);
410fa9e4066Sahrens 
411f65e61c0Sahrens 			ASSERT3U(chunk, <, ZAP_LEAF_NUMCHUNKS(l));
412f65e61c0Sahrens 			ASSERT3U(le->le_type, ==, ZAP_CHUNK_ENTRY);
413fa9e4066Sahrens 
41487e5029aSahrens 			if (HCD_GTEQ(le->le_hash, le->le_cd, h, cd) &&
41587e5029aSahrens 			    HCD_GTEQ(besth, bestcd, le->le_hash, le->le_cd)) {
416fa9e4066Sahrens 				ASSERT3U(bestlh, >=, lh);
417fa9e4066Sahrens 				bestlh = lh;
418fa9e4066Sahrens 				besth = le->le_hash;
419fa9e4066Sahrens 				bestcd = le->le_cd;
420fa9e4066Sahrens 
421fa9e4066Sahrens 				zeh->zeh_num_integers = le->le_value_length;
422fa9e4066Sahrens 				zeh->zeh_integer_size = le->le_int_size;
423fa9e4066Sahrens 				zeh->zeh_cd = le->le_cd;
424fa9e4066Sahrens 				zeh->zeh_hash = le->le_hash;
425fa9e4066Sahrens 				zeh->zeh_fakechunk = chunk;
426fa9e4066Sahrens 				zeh->zeh_chunkp = &zeh->zeh_fakechunk;
42766328dd3Sahrens 				zeh->zeh_leaf = l;
428fa9e4066Sahrens 			}
429fa9e4066Sahrens 		}
430fa9e4066Sahrens 	}
431fa9e4066Sahrens 
432fa9e4066Sahrens 	return (bestcd == ZAP_MAXCD ? ENOENT : 0);
433fa9e4066Sahrens }
434fa9e4066Sahrens 
435fa9e4066Sahrens int
436fa9e4066Sahrens zap_entry_read(const zap_entry_handle_t *zeh,
437fa9e4066Sahrens     uint8_t integer_size, uint64_t num_integers, void *buf)
438fa9e4066Sahrens {
439f65e61c0Sahrens 	struct zap_leaf_entry *le =
44066328dd3Sahrens 	    ZAP_LEAF_ENTRY(zeh->zeh_leaf, *zeh->zeh_chunkp);
441f65e61c0Sahrens 	ASSERT3U(le->le_type, ==, ZAP_CHUNK_ENTRY);
442fa9e4066Sahrens 
443fa9e4066Sahrens 	if (le->le_int_size > integer_size)
444fa9e4066Sahrens 		return (EINVAL);
445fa9e4066Sahrens 
44666328dd3Sahrens 	zap_leaf_array_read(zeh->zeh_leaf, le->le_value_chunk, le->le_int_size,
447fa9e4066Sahrens 	    le->le_value_length, integer_size, num_integers, buf);
448fa9e4066Sahrens 
449fa9e4066Sahrens 	if (zeh->zeh_num_integers > num_integers)
450fa9e4066Sahrens 		return (EOVERFLOW);
451fa9e4066Sahrens 	return (0);
452fa9e4066Sahrens 
453fa9e4066Sahrens }
454fa9e4066Sahrens 
455fa9e4066Sahrens int
456fa9e4066Sahrens zap_entry_read_name(const zap_entry_handle_t *zeh, uint16_t buflen, char *buf)
457fa9e4066Sahrens {
458f65e61c0Sahrens 	struct zap_leaf_entry *le =
45966328dd3Sahrens 	    ZAP_LEAF_ENTRY(zeh->zeh_leaf, *zeh->zeh_chunkp);
460f65e61c0Sahrens 	ASSERT3U(le->le_type, ==, ZAP_CHUNK_ENTRY);
461fa9e4066Sahrens 
46266328dd3Sahrens 	zap_leaf_array_read(zeh->zeh_leaf, le->le_name_chunk, 1,
463fa9e4066Sahrens 	    le->le_name_length, 1, buflen, buf);
464fa9e4066Sahrens 	if (le->le_name_length > buflen)
465fa9e4066Sahrens 		return (EOVERFLOW);
466fa9e4066Sahrens 	return (0);
467fa9e4066Sahrens }
468fa9e4066Sahrens 
469fa9e4066Sahrens int
470fa9e4066Sahrens zap_entry_update(zap_entry_handle_t *zeh,
471fa9e4066Sahrens 	uint8_t integer_size, uint64_t num_integers, const void *buf)
472fa9e4066Sahrens {
473fa9e4066Sahrens 	int delta_chunks;
47466328dd3Sahrens 	zap_leaf_t *l = zeh->zeh_leaf;
47566328dd3Sahrens 	struct zap_leaf_entry *le = ZAP_LEAF_ENTRY(l, *zeh->zeh_chunkp);
476fa9e4066Sahrens 
47766328dd3Sahrens 	delta_chunks = ZAP_LEAF_ARRAY_NCHUNKS(num_integers * integer_size) -
47866328dd3Sahrens 	    ZAP_LEAF_ARRAY_NCHUNKS(le->le_value_length * le->le_int_size);
479fa9e4066Sahrens 
48066328dd3Sahrens 	if ((int)l->l_phys->l_hdr.lh_nfree < delta_chunks)
481fa9e4066Sahrens 		return (EAGAIN);
482fa9e4066Sahrens 
483fa9e4066Sahrens 	/*
484fa9e4066Sahrens 	 * We should search other chained leaves (via
485fa9e4066Sahrens 	 * zap_entry_remove,create?) otherwise returning EAGAIN will
486fa9e4066Sahrens 	 * just send us into an infinite loop if we have to chain
487fa9e4066Sahrens 	 * another leaf block, rather than being able to split this
488fa9e4066Sahrens 	 * block.
489fa9e4066Sahrens 	 */
490fa9e4066Sahrens 
49166328dd3Sahrens 	zap_leaf_array_free(l, &le->le_value_chunk);
492fa9e4066Sahrens 	le->le_value_chunk =
49366328dd3Sahrens 	    zap_leaf_array_create(l, buf, integer_size, num_integers);
494f65e61c0Sahrens 	le->le_value_length = num_integers;
495fa9e4066Sahrens 	le->le_int_size = integer_size;
496fa9e4066Sahrens 	return (0);
497fa9e4066Sahrens }
498fa9e4066Sahrens 
499fa9e4066Sahrens void
500fa9e4066Sahrens zap_entry_remove(zap_entry_handle_t *zeh)
501fa9e4066Sahrens {
502fa9e4066Sahrens 	uint16_t entry_chunk;
503fa9e4066Sahrens 	struct zap_leaf_entry *le;
50466328dd3Sahrens 	zap_leaf_t *l = zeh->zeh_leaf;
505fa9e4066Sahrens 
506fa9e4066Sahrens 	ASSERT3P(zeh->zeh_chunkp, !=, &zeh->zeh_fakechunk);
507fa9e4066Sahrens 
508fa9e4066Sahrens 	entry_chunk = *zeh->zeh_chunkp;
509f65e61c0Sahrens 	le = ZAP_LEAF_ENTRY(l, entry_chunk);
510f65e61c0Sahrens 	ASSERT3U(le->le_type, ==, ZAP_CHUNK_ENTRY);
511fa9e4066Sahrens 
51266328dd3Sahrens 	zap_leaf_array_free(l, &le->le_name_chunk);
51366328dd3Sahrens 	zap_leaf_array_free(l, &le->le_value_chunk);
514fa9e4066Sahrens 
515fa9e4066Sahrens 	*zeh->zeh_chunkp = le->le_next;
516fa9e4066Sahrens 	zap_leaf_chunk_free(l, entry_chunk);
517fa9e4066Sahrens 
51866328dd3Sahrens 	l->l_phys->l_hdr.lh_nentries--;
519fa9e4066Sahrens }
520fa9e4066Sahrens 
521fa9e4066Sahrens int
522fa9e4066Sahrens zap_entry_create(zap_leaf_t *l, const char *name, uint64_t h, uint32_t cd,
523fa9e4066Sahrens     uint8_t integer_size, uint64_t num_integers, const void *buf,
524fa9e4066Sahrens     zap_entry_handle_t *zeh)
525fa9e4066Sahrens {
526fa9e4066Sahrens 	uint16_t chunk;
527fa9e4066Sahrens 	uint16_t *chunkp;
528fa9e4066Sahrens 	struct zap_leaf_entry *le;
529fa9e4066Sahrens 	uint64_t namelen, valuelen;
530fa9e4066Sahrens 	int numchunks;
531fa9e4066Sahrens 
532fa9e4066Sahrens 	valuelen = integer_size * num_integers;
533fa9e4066Sahrens 	namelen = strlen(name) + 1;
534fa9e4066Sahrens 	ASSERT(namelen >= 2);
535fa9e4066Sahrens 
53666328dd3Sahrens 	numchunks = 1 + ZAP_LEAF_ARRAY_NCHUNKS(namelen) +
53766328dd3Sahrens 	    ZAP_LEAF_ARRAY_NCHUNKS(valuelen);
538f65e61c0Sahrens 	if (numchunks > ZAP_LEAF_NUMCHUNKS(l))
539fa9e4066Sahrens 		return (E2BIG);
540fa9e4066Sahrens 
541fa9e4066Sahrens 	if (cd == ZAP_MAXCD) {
542fa9e4066Sahrens 		for (cd = 0; cd < ZAP_MAXCD; cd++) {
54366328dd3Sahrens 			for (chunk = *LEAF_HASH_ENTPTR(l, h);
54466328dd3Sahrens 			    chunk != CHAIN_END; chunk = le->le_next) {
54566328dd3Sahrens 				le = ZAP_LEAF_ENTRY(l, chunk);
54666328dd3Sahrens 				if (le->le_hash == h &&
54766328dd3Sahrens 				    le->le_cd == cd) {
548fa9e4066Sahrens 					break;
54966328dd3Sahrens 				}
550fa9e4066Sahrens 			}
551fa9e4066Sahrens 			/* If this cd is not in use, we are good. */
552fa9e4066Sahrens 			if (chunk == CHAIN_END)
553fa9e4066Sahrens 				break;
554fa9e4066Sahrens 		}
555fa9e4066Sahrens 		/* If we tried all the cd's, we lose. */
556fa9e4066Sahrens 		if (cd == ZAP_MAXCD)
557fa9e4066Sahrens 			return (ENOSPC);
558fa9e4066Sahrens 	}
559fa9e4066Sahrens 
56066328dd3Sahrens 	if (l->l_phys->l_hdr.lh_nfree < numchunks)
561fa9e4066Sahrens 		return (EAGAIN);
562fa9e4066Sahrens 
563fa9e4066Sahrens 	/* make the entry */
564fa9e4066Sahrens 	chunk = zap_leaf_chunk_alloc(l);
565f65e61c0Sahrens 	le = ZAP_LEAF_ENTRY(l, chunk);
566f65e61c0Sahrens 	le->le_type = ZAP_CHUNK_ENTRY;
56766328dd3Sahrens 	le->le_name_chunk = zap_leaf_array_create(l, name, 1, namelen);
568fa9e4066Sahrens 	le->le_name_length = namelen;
569fa9e4066Sahrens 	le->le_value_chunk =
57066328dd3Sahrens 	    zap_leaf_array_create(l, buf, integer_size, num_integers);
571f65e61c0Sahrens 	le->le_value_length = num_integers;
572fa9e4066Sahrens 	le->le_int_size = integer_size;
573fa9e4066Sahrens 	le->le_hash = h;
574fa9e4066Sahrens 	le->le_cd = cd;
575fa9e4066Sahrens 
576fa9e4066Sahrens 	/* link it into the hash chain */
577fa9e4066Sahrens 	chunkp = LEAF_HASH_ENTPTR(l, h);
578fa9e4066Sahrens 	le->le_next = *chunkp;
579fa9e4066Sahrens 	*chunkp = chunk;
580fa9e4066Sahrens 
58166328dd3Sahrens 	l->l_phys->l_hdr.lh_nentries++;
582fa9e4066Sahrens 
58366328dd3Sahrens 	zeh->zeh_leaf = l;
584fa9e4066Sahrens 	zeh->zeh_num_integers = num_integers;
585fa9e4066Sahrens 	zeh->zeh_integer_size = le->le_int_size;
586fa9e4066Sahrens 	zeh->zeh_cd = le->le_cd;
587fa9e4066Sahrens 	zeh->zeh_hash = le->le_hash;
588fa9e4066Sahrens 	zeh->zeh_chunkp = chunkp;
589fa9e4066Sahrens 
590fa9e4066Sahrens 	return (0);
591fa9e4066Sahrens }
592fa9e4066Sahrens 
593fa9e4066Sahrens /*
594fa9e4066Sahrens  * Routines for transferring entries between leafs.
595fa9e4066Sahrens  */
596fa9e4066Sahrens 
597fa9e4066Sahrens static void
598fa9e4066Sahrens zap_leaf_rehash_entry(zap_leaf_t *l, uint16_t entry)
599fa9e4066Sahrens {
600f65e61c0Sahrens 	struct zap_leaf_entry *le = ZAP_LEAF_ENTRY(l, entry);
601fa9e4066Sahrens 	uint16_t *ptr = LEAF_HASH_ENTPTR(l, le->le_hash);
602fa9e4066Sahrens 	le->le_next = *ptr;
603fa9e4066Sahrens 	*ptr = entry;
604fa9e4066Sahrens }
605fa9e4066Sahrens 
606fa9e4066Sahrens static uint16_t
607fa9e4066Sahrens zap_leaf_transfer_array(zap_leaf_t *l, uint16_t chunk, zap_leaf_t *nl)
608fa9e4066Sahrens {
609fa9e4066Sahrens 	uint16_t new_chunk;
610fa9e4066Sahrens 	uint16_t *nchunkp = &new_chunk;
611fa9e4066Sahrens 
612fa9e4066Sahrens 	while (chunk != CHAIN_END) {
613fa9e4066Sahrens 		uint16_t nchunk = zap_leaf_chunk_alloc(nl);
614fa9e4066Sahrens 		struct zap_leaf_array *nla =
615f65e61c0Sahrens 		    &ZAP_LEAF_CHUNK(nl, nchunk).l_array;
616fa9e4066Sahrens 		struct zap_leaf_array *la =
617f65e61c0Sahrens 		    &ZAP_LEAF_CHUNK(l, chunk).l_array;
618fa9e4066Sahrens 		int nextchunk = la->la_next;
619fa9e4066Sahrens 
620f65e61c0Sahrens 		ASSERT3U(chunk, <, ZAP_LEAF_NUMCHUNKS(l));
621f65e61c0Sahrens 		ASSERT3U(nchunk, <, ZAP_LEAF_NUMCHUNKS(l));
622fa9e4066Sahrens 
62366328dd3Sahrens 		*nla = *la; /* structure assignment */
624fa9e4066Sahrens 
625fa9e4066Sahrens 		zap_leaf_chunk_free(l, chunk);
626fa9e4066Sahrens 		chunk = nextchunk;
627fa9e4066Sahrens 		*nchunkp = nchunk;
628fa9e4066Sahrens 		nchunkp = &nla->la_next;
629fa9e4066Sahrens 	}
630fa9e4066Sahrens 	*nchunkp = CHAIN_END;
631fa9e4066Sahrens 	return (new_chunk);
632fa9e4066Sahrens }
633fa9e4066Sahrens 
634fa9e4066Sahrens static void
63566328dd3Sahrens zap_leaf_transfer_entry(zap_leaf_t *l, int entry, zap_leaf_t *nl)
636fa9e4066Sahrens {
637fa9e4066Sahrens 	struct zap_leaf_entry *le, *nle;
63866328dd3Sahrens 	uint16_t chunk;
639fa9e4066Sahrens 
640f65e61c0Sahrens 	le = ZAP_LEAF_ENTRY(l, entry);
641f65e61c0Sahrens 	ASSERT3U(le->le_type, ==, ZAP_CHUNK_ENTRY);
642fa9e4066Sahrens 
643fa9e4066Sahrens 	chunk = zap_leaf_chunk_alloc(nl);
644f65e61c0Sahrens 	nle = ZAP_LEAF_ENTRY(nl, chunk);
64566328dd3Sahrens 	*nle = *le; /* structure assignment */
646fa9e4066Sahrens 
647fa9e4066Sahrens 	zap_leaf_rehash_entry(nl, chunk);
648fa9e4066Sahrens 
649fa9e4066Sahrens 	nle->le_name_chunk = zap_leaf_transfer_array(l, le->le_name_chunk, nl);
650fa9e4066Sahrens 	nle->le_value_chunk =
651fa9e4066Sahrens 	    zap_leaf_transfer_array(l, le->le_value_chunk, nl);
652fa9e4066Sahrens 
653fa9e4066Sahrens 	zap_leaf_chunk_free(l, entry);
654fa9e4066Sahrens 
65566328dd3Sahrens 	l->l_phys->l_hdr.lh_nentries--;
65666328dd3Sahrens 	nl->l_phys->l_hdr.lh_nentries++;
657fa9e4066Sahrens }
658fa9e4066Sahrens 
659fa9e4066Sahrens /*
66066328dd3Sahrens  * Transfer the entries whose hash prefix ends in 1 to the new leaf.
661fa9e4066Sahrens  */
66266328dd3Sahrens void
66366328dd3Sahrens zap_leaf_split(zap_leaf_t *l, zap_leaf_t *nl)
664fa9e4066Sahrens {
665fa9e4066Sahrens 	int i;
66666328dd3Sahrens 	int bit = 64 - 1 - l->l_phys->l_hdr.lh_prefix_len;
66766328dd3Sahrens 
66866328dd3Sahrens 	/* set new prefix and prefix_len */
66966328dd3Sahrens 	l->l_phys->l_hdr.lh_prefix <<= 1;
67066328dd3Sahrens 	l->l_phys->l_hdr.lh_prefix_len++;
67166328dd3Sahrens 	nl->l_phys->l_hdr.lh_prefix = l->l_phys->l_hdr.lh_prefix | 1;
67266328dd3Sahrens 	nl->l_phys->l_hdr.lh_prefix_len = l->l_phys->l_hdr.lh_prefix_len;
673fa9e4066Sahrens 
674fa9e4066Sahrens 	/* break existing hash chains */
675f65e61c0Sahrens 	zap_memset(l->l_phys->l_hash, CHAIN_END, 2*ZAP_LEAF_HASH_NUMENTRIES(l));
676fa9e4066Sahrens 
67766328dd3Sahrens 	/*
67866328dd3Sahrens 	 * Transfer entries whose hash bit 'bit' is set to nl; rehash
67966328dd3Sahrens 	 * the remaining entries
68066328dd3Sahrens 	 *
68166328dd3Sahrens 	 * NB: We could find entries via the hashtable instead. That
68266328dd3Sahrens 	 * would be O(hashents+numents) rather than O(numblks+numents),
68366328dd3Sahrens 	 * but this accesses memory more sequentially, and when we're
68466328dd3Sahrens 	 * called, the block is usually pretty full.
68566328dd3Sahrens 	 */
686f65e61c0Sahrens 	for (i = 0; i < ZAP_LEAF_NUMCHUNKS(l); i++) {
687f65e61c0Sahrens 		struct zap_leaf_entry *le = ZAP_LEAF_ENTRY(l, i);
688f65e61c0Sahrens 		if (le->le_type != ZAP_CHUNK_ENTRY)
689fa9e4066Sahrens 			continue;
690fa9e4066Sahrens 
69166328dd3Sahrens 		if (le->le_hash & (1ULL << bit))
69266328dd3Sahrens 			zap_leaf_transfer_entry(l, i, nl);
69366328dd3Sahrens 		else
69466328dd3Sahrens 			zap_leaf_rehash_entry(l, i);
695fa9e4066Sahrens 	}
696fa9e4066Sahrens }
697fa9e4066Sahrens 
698fa9e4066Sahrens void
69966328dd3Sahrens zap_leaf_stats(zap_t *zap, zap_leaf_t *l, zap_stats_t *zs)
700fa9e4066Sahrens {
70166328dd3Sahrens 	int i, n;
702fa9e4066Sahrens 
70366328dd3Sahrens 	n = zap->zap_f.zap_phys->zap_ptrtbl.zt_shift -
70466328dd3Sahrens 	    l->l_phys->l_hdr.lh_prefix_len;
705fa9e4066Sahrens 	n = MIN(n, ZAP_HISTOGRAM_SIZE-1);
706fa9e4066Sahrens 	zs->zs_leafs_with_2n_pointers[n]++;
707fa9e4066Sahrens 
708fa9e4066Sahrens 
70966328dd3Sahrens 	n = l->l_phys->l_hdr.lh_nentries/5;
71066328dd3Sahrens 	n = MIN(n, ZAP_HISTOGRAM_SIZE-1);
71166328dd3Sahrens 	zs->zs_blocks_with_n5_entries[n]++;
712fa9e4066Sahrens 
71366328dd3Sahrens 	n = ((1<<FZAP_BLOCK_SHIFT(zap)) -
71466328dd3Sahrens 	    l->l_phys->l_hdr.lh_nfree * (ZAP_LEAF_ARRAY_BYTES+1))*10 /
71566328dd3Sahrens 	    (1<<FZAP_BLOCK_SHIFT(zap));
71666328dd3Sahrens 	n = MIN(n, ZAP_HISTOGRAM_SIZE-1);
71766328dd3Sahrens 	zs->zs_blocks_n_tenths_full[n]++;
718fa9e4066Sahrens 
71966328dd3Sahrens 	for (i = 0; i < ZAP_LEAF_HASH_NUMENTRIES(l); i++) {
72066328dd3Sahrens 		int nentries = 0;
72166328dd3Sahrens 		int chunk = l->l_phys->l_hash[i];
722fa9e4066Sahrens 
72366328dd3Sahrens 		while (chunk != CHAIN_END) {
72466328dd3Sahrens 			struct zap_leaf_entry *le =
72566328dd3Sahrens 			    ZAP_LEAF_ENTRY(l, chunk);
726fa9e4066Sahrens 
72766328dd3Sahrens 			n = 1 + ZAP_LEAF_ARRAY_NCHUNKS(le->le_name_length) +
72866328dd3Sahrens 			    ZAP_LEAF_ARRAY_NCHUNKS(le->le_value_length *
72966328dd3Sahrens 				le->le_int_size);
730fa9e4066Sahrens 			n = MIN(n, ZAP_HISTOGRAM_SIZE-1);
73166328dd3Sahrens 			zs->zs_entries_using_n_chunks[n]++;
732fa9e4066Sahrens 
73366328dd3Sahrens 			chunk = le->le_next;
73466328dd3Sahrens 			nentries++;
73566328dd3Sahrens 		}
736fa9e4066Sahrens 
73766328dd3Sahrens 		n = nentries;
73866328dd3Sahrens 		n = MIN(n, ZAP_HISTOGRAM_SIZE-1);
73966328dd3Sahrens 		zs->zs_buckets_with_n_entries[n]++;
74066328dd3Sahrens 	}
741fa9e4066Sahrens }
742