xref: /illumos-gate/usr/src/uts/common/fs/zfs/zap_leaf.c (revision b24ab6762772a3f6a89393947930c7fa61306783)
1 /*
2  * CDDL HEADER START
3  *
4  * The contents of this file are subject to the terms of the
5  * Common Development and Distribution License (the "License").
6  * You may not use this file except in compliance with the License.
7  *
8  * You can obtain a copy of the license at usr/src/OPENSOLARIS.LICENSE
9  * or http://www.opensolaris.org/os/licensing.
10  * See the License for the specific language governing permissions
11  * and limitations under the License.
12  *
13  * When distributing Covered Code, include this CDDL HEADER in each
14  * file and include the License file at usr/src/OPENSOLARIS.LICENSE.
15  * If applicable, add the following below this CDDL HEADER, with the
16  * fields enclosed by brackets "[]" replaced with your own identifying
17  * information: Portions Copyright [yyyy] [name of copyright owner]
18  *
19  * CDDL HEADER END
20  */
21 /*
22  * Copyright 2009 Sun Microsystems, Inc.  All rights reserved.
23  * Use is subject to license terms.
24  */
25 
26 /*
27  * The 512-byte leaf is broken into 32 16-byte chunks.
28  * chunk number n means l_chunk[n], even though the header precedes it.
29  * the names are stored null-terminated.
30  */
31 
32 #include <sys/zio.h>
33 #include <sys/spa.h>
34 #include <sys/dmu.h>
35 #include <sys/zfs_context.h>
36 #include <sys/fs/zfs.h>
37 #include <sys/zap.h>
38 #include <sys/zap_impl.h>
39 #include <sys/zap_leaf.h>
40 
41 static uint16_t *zap_leaf_rehash_entry(zap_leaf_t *l, uint16_t entry);
42 
43 #define	CHAIN_END 0xffff /* end of the chunk chain */
44 
45 /* half the (current) minimum block size */
46 #define	MAX_ARRAY_BYTES (8<<10)
47 
48 #define	LEAF_HASH(l, h) \
49 	((ZAP_LEAF_HASH_NUMENTRIES(l)-1) & \
50 	((h) >> (64 - ZAP_LEAF_HASH_SHIFT(l)-(l)->l_phys->l_hdr.lh_prefix_len)))
51 
52 #define	LEAF_HASH_ENTPTR(l, h) (&(l)->l_phys->l_hash[LEAF_HASH(l, h)])
53 
54 
55 static void
56 zap_memset(void *a, int c, size_t n)
57 {
58 	char *cp = a;
59 	char *cpend = cp + n;
60 
61 	while (cp < cpend)
62 		*cp++ = c;
63 }
64 
65 static void
66 stv(int len, void *addr, uint64_t value)
67 {
68 	switch (len) {
69 	case 1:
70 		*(uint8_t *)addr = value;
71 		return;
72 	case 2:
73 		*(uint16_t *)addr = value;
74 		return;
75 	case 4:
76 		*(uint32_t *)addr = value;
77 		return;
78 	case 8:
79 		*(uint64_t *)addr = value;
80 		return;
81 	}
82 	ASSERT(!"bad int len");
83 }
84 
85 static uint64_t
86 ldv(int len, const void *addr)
87 {
88 	switch (len) {
89 	case 1:
90 		return (*(uint8_t *)addr);
91 	case 2:
92 		return (*(uint16_t *)addr);
93 	case 4:
94 		return (*(uint32_t *)addr);
95 	case 8:
96 		return (*(uint64_t *)addr);
97 	}
98 	ASSERT(!"bad int len");
99 	return (0xFEEDFACEDEADBEEFULL);
100 }
101 
102 void
103 zap_leaf_byteswap(zap_leaf_phys_t *buf, int size)
104 {
105 	int i;
106 	zap_leaf_t l;
107 	l.l_bs = highbit(size)-1;
108 	l.l_phys = buf;
109 
110 	buf->l_hdr.lh_block_type = 	BSWAP_64(buf->l_hdr.lh_block_type);
111 	buf->l_hdr.lh_prefix = 		BSWAP_64(buf->l_hdr.lh_prefix);
112 	buf->l_hdr.lh_magic = 		BSWAP_32(buf->l_hdr.lh_magic);
113 	buf->l_hdr.lh_nfree = 		BSWAP_16(buf->l_hdr.lh_nfree);
114 	buf->l_hdr.lh_nentries = 	BSWAP_16(buf->l_hdr.lh_nentries);
115 	buf->l_hdr.lh_prefix_len = 	BSWAP_16(buf->l_hdr.lh_prefix_len);
116 	buf->l_hdr.lh_freelist = 	BSWAP_16(buf->l_hdr.lh_freelist);
117 
118 	for (i = 0; i < ZAP_LEAF_HASH_NUMENTRIES(&l); i++)
119 		buf->l_hash[i] = BSWAP_16(buf->l_hash[i]);
120 
121 	for (i = 0; i < ZAP_LEAF_NUMCHUNKS(&l); i++) {
122 		zap_leaf_chunk_t *lc = &ZAP_LEAF_CHUNK(&l, i);
123 		struct zap_leaf_entry *le;
124 
125 		switch (lc->l_free.lf_type) {
126 		case ZAP_CHUNK_ENTRY:
127 			le = &lc->l_entry;
128 
129 			le->le_type =		BSWAP_8(le->le_type);
130 			le->le_int_size =	BSWAP_8(le->le_int_size);
131 			le->le_next =		BSWAP_16(le->le_next);
132 			le->le_name_chunk =	BSWAP_16(le->le_name_chunk);
133 			le->le_name_length =	BSWAP_16(le->le_name_length);
134 			le->le_value_chunk =	BSWAP_16(le->le_value_chunk);
135 			le->le_value_length =	BSWAP_16(le->le_value_length);
136 			le->le_cd =		BSWAP_32(le->le_cd);
137 			le->le_hash =		BSWAP_64(le->le_hash);
138 			break;
139 		case ZAP_CHUNK_FREE:
140 			lc->l_free.lf_type =	BSWAP_8(lc->l_free.lf_type);
141 			lc->l_free.lf_next =	BSWAP_16(lc->l_free.lf_next);
142 			break;
143 		case ZAP_CHUNK_ARRAY:
144 			lc->l_array.la_type =	BSWAP_8(lc->l_array.la_type);
145 			lc->l_array.la_next =	BSWAP_16(lc->l_array.la_next);
146 			/* la_array doesn't need swapping */
147 			break;
148 		default:
149 			ASSERT(!"bad leaf type");
150 		}
151 	}
152 }
153 
154 void
155 zap_leaf_init(zap_leaf_t *l, boolean_t sort)
156 {
157 	int i;
158 
159 	l->l_bs = highbit(l->l_dbuf->db_size)-1;
160 	zap_memset(&l->l_phys->l_hdr, 0, sizeof (struct zap_leaf_header));
161 	zap_memset(l->l_phys->l_hash, CHAIN_END, 2*ZAP_LEAF_HASH_NUMENTRIES(l));
162 	for (i = 0; i < ZAP_LEAF_NUMCHUNKS(l); i++) {
163 		ZAP_LEAF_CHUNK(l, i).l_free.lf_type = ZAP_CHUNK_FREE;
164 		ZAP_LEAF_CHUNK(l, i).l_free.lf_next = i+1;
165 	}
166 	ZAP_LEAF_CHUNK(l, ZAP_LEAF_NUMCHUNKS(l)-1).l_free.lf_next = CHAIN_END;
167 	l->l_phys->l_hdr.lh_block_type = ZBT_LEAF;
168 	l->l_phys->l_hdr.lh_magic = ZAP_LEAF_MAGIC;
169 	l->l_phys->l_hdr.lh_nfree = ZAP_LEAF_NUMCHUNKS(l);
170 	if (sort)
171 		l->l_phys->l_hdr.lh_flags |= ZLF_ENTRIES_CDSORTED;
172 }
173 
174 /*
175  * Routines which manipulate leaf chunks (l_chunk[]).
176  */
177 
178 static uint16_t
179 zap_leaf_chunk_alloc(zap_leaf_t *l)
180 {
181 	int chunk;
182 
183 	ASSERT(l->l_phys->l_hdr.lh_nfree > 0);
184 
185 	chunk = l->l_phys->l_hdr.lh_freelist;
186 	ASSERT3U(chunk, <, ZAP_LEAF_NUMCHUNKS(l));
187 	ASSERT3U(ZAP_LEAF_CHUNK(l, chunk).l_free.lf_type, ==, ZAP_CHUNK_FREE);
188 
189 	l->l_phys->l_hdr.lh_freelist = ZAP_LEAF_CHUNK(l, chunk).l_free.lf_next;
190 
191 	l->l_phys->l_hdr.lh_nfree--;
192 
193 	return (chunk);
194 }
195 
196 static void
197 zap_leaf_chunk_free(zap_leaf_t *l, uint16_t chunk)
198 {
199 	struct zap_leaf_free *zlf = &ZAP_LEAF_CHUNK(l, chunk).l_free;
200 	ASSERT3U(l->l_phys->l_hdr.lh_nfree, <, ZAP_LEAF_NUMCHUNKS(l));
201 	ASSERT3U(chunk, <, ZAP_LEAF_NUMCHUNKS(l));
202 	ASSERT(zlf->lf_type != ZAP_CHUNK_FREE);
203 
204 	zlf->lf_type = ZAP_CHUNK_FREE;
205 	zlf->lf_next = l->l_phys->l_hdr.lh_freelist;
206 	bzero(zlf->lf_pad, sizeof (zlf->lf_pad)); /* help it to compress */
207 	l->l_phys->l_hdr.lh_freelist = chunk;
208 
209 	l->l_phys->l_hdr.lh_nfree++;
210 }
211 
212 /*
213  * Routines which manipulate leaf arrays (zap_leaf_array type chunks).
214  */
215 
216 static uint16_t
217 zap_leaf_array_create(zap_leaf_t *l, const char *buf,
218 	int integer_size, int num_integers)
219 {
220 	uint16_t chunk_head;
221 	uint16_t *chunkp = &chunk_head;
222 	int byten = 0;
223 	uint64_t value;
224 	int shift = (integer_size-1)*8;
225 	int len = num_integers;
226 
227 	ASSERT3U(num_integers * integer_size, <, MAX_ARRAY_BYTES);
228 
229 	while (len > 0) {
230 		uint16_t chunk = zap_leaf_chunk_alloc(l);
231 		struct zap_leaf_array *la = &ZAP_LEAF_CHUNK(l, chunk).l_array;
232 		int i;
233 
234 		la->la_type = ZAP_CHUNK_ARRAY;
235 		for (i = 0; i < ZAP_LEAF_ARRAY_BYTES; i++) {
236 			if (byten == 0)
237 				value = ldv(integer_size, buf);
238 			la->la_array[i] = value >> shift;
239 			value <<= 8;
240 			if (++byten == integer_size) {
241 				byten = 0;
242 				buf += integer_size;
243 				if (--len == 0)
244 					break;
245 			}
246 		}
247 
248 		*chunkp = chunk;
249 		chunkp = &la->la_next;
250 	}
251 	*chunkp = CHAIN_END;
252 
253 	return (chunk_head);
254 }
255 
256 static void
257 zap_leaf_array_free(zap_leaf_t *l, uint16_t *chunkp)
258 {
259 	uint16_t chunk = *chunkp;
260 
261 	*chunkp = CHAIN_END;
262 
263 	while (chunk != CHAIN_END) {
264 		int nextchunk = ZAP_LEAF_CHUNK(l, chunk).l_array.la_next;
265 		ASSERT3U(ZAP_LEAF_CHUNK(l, chunk).l_array.la_type, ==,
266 		    ZAP_CHUNK_ARRAY);
267 		zap_leaf_chunk_free(l, chunk);
268 		chunk = nextchunk;
269 	}
270 }
271 
272 /* array_len and buf_len are in integers, not bytes */
273 static void
274 zap_leaf_array_read(zap_leaf_t *l, uint16_t chunk,
275     int array_int_len, int array_len, int buf_int_len, uint64_t buf_len,
276     void *buf)
277 {
278 	int len = MIN(array_len, buf_len);
279 	int byten = 0;
280 	uint64_t value = 0;
281 	char *p = buf;
282 
283 	ASSERT3U(array_int_len, <=, buf_int_len);
284 
285 	/* Fast path for one 8-byte integer */
286 	if (array_int_len == 8 && buf_int_len == 8 && len == 1) {
287 		struct zap_leaf_array *la = &ZAP_LEAF_CHUNK(l, chunk).l_array;
288 		uint8_t *ip = la->la_array;
289 		uint64_t *buf64 = buf;
290 
291 		*buf64 = (uint64_t)ip[0] << 56 | (uint64_t)ip[1] << 48 |
292 		    (uint64_t)ip[2] << 40 | (uint64_t)ip[3] << 32 |
293 		    (uint64_t)ip[4] << 24 | (uint64_t)ip[5] << 16 |
294 		    (uint64_t)ip[6] << 8 | (uint64_t)ip[7];
295 		return;
296 	}
297 
298 	/* Fast path for an array of 1-byte integers (eg. the entry name) */
299 	if (array_int_len == 1 && buf_int_len == 1 &&
300 	    buf_len > array_len + ZAP_LEAF_ARRAY_BYTES) {
301 		while (chunk != CHAIN_END) {
302 			struct zap_leaf_array *la =
303 			    &ZAP_LEAF_CHUNK(l, chunk).l_array;
304 			bcopy(la->la_array, p, ZAP_LEAF_ARRAY_BYTES);
305 			p += ZAP_LEAF_ARRAY_BYTES;
306 			chunk = la->la_next;
307 		}
308 		return;
309 	}
310 
311 	while (len > 0) {
312 		struct zap_leaf_array *la = &ZAP_LEAF_CHUNK(l, chunk).l_array;
313 		int i;
314 
315 		ASSERT3U(chunk, <, ZAP_LEAF_NUMCHUNKS(l));
316 		for (i = 0; i < ZAP_LEAF_ARRAY_BYTES && len > 0; i++) {
317 			value = (value << 8) | la->la_array[i];
318 			byten++;
319 			if (byten == array_int_len) {
320 				stv(buf_int_len, p, value);
321 				byten = 0;
322 				len--;
323 				if (len == 0)
324 					return;
325 				p += buf_int_len;
326 			}
327 		}
328 		chunk = la->la_next;
329 	}
330 }
331 
332 /*
333  * array_len is actual len in bytes (not encoded le_value_length).
334  * namenorm is null-terminated.
335  */
336 static boolean_t
337 zap_leaf_array_match(zap_leaf_t *l, zap_name_t *zn, int chunk, int array_len)
338 {
339 	int bseen = 0;
340 
341 	if (zap_getflags(zn->zn_zap) & ZAP_FLAG_UINT64_KEY) {
342 		uint64_t *thiskey;
343 		boolean_t match;
344 
345 		ASSERT(zn->zn_key_intlen == sizeof (*thiskey));
346 		thiskey = kmem_alloc(array_len * sizeof (*thiskey), KM_SLEEP);
347 
348 		zap_leaf_array_read(l, chunk, sizeof (*thiskey), array_len,
349 		    sizeof (*thiskey), array_len, thiskey);
350 		match = bcmp(thiskey, zn->zn_key_orig,
351 		    array_len * sizeof (*thiskey)) == 0;
352 		kmem_free(thiskey, array_len * sizeof (*thiskey));
353 		return (match);
354 	}
355 
356 	if (zn->zn_matchtype == MT_FIRST) {
357 		char *thisname = kmem_alloc(array_len, KM_SLEEP);
358 		boolean_t match;
359 
360 		zap_leaf_array_read(l, chunk, sizeof (char), array_len,
361 		    sizeof (char), array_len, thisname);
362 		match = zap_match(zn, thisname);
363 		kmem_free(thisname, array_len);
364 		return (match);
365 	}
366 
367 	/*
368 	 * Fast path for exact matching.
369 	 * First check that the lengths match, so that we don't read
370 	 * past the end of the zn_key_orig array.
371 	 */
372 	if (array_len != zn->zn_key_orig_len)
373 		return (B_FALSE);
374 	while (bseen < array_len) {
375 		struct zap_leaf_array *la = &ZAP_LEAF_CHUNK(l, chunk).l_array;
376 		int toread = MIN(array_len - bseen, ZAP_LEAF_ARRAY_BYTES);
377 		ASSERT3U(chunk, <, ZAP_LEAF_NUMCHUNKS(l));
378 		if (bcmp(la->la_array, (char *)zn->zn_key_orig + bseen, toread))
379 			break;
380 		chunk = la->la_next;
381 		bseen += toread;
382 	}
383 	return (bseen == array_len);
384 }
385 
386 /*
387  * Routines which manipulate leaf entries.
388  */
389 
390 int
391 zap_leaf_lookup(zap_leaf_t *l, zap_name_t *zn, zap_entry_handle_t *zeh)
392 {
393 	uint16_t *chunkp;
394 	struct zap_leaf_entry *le;
395 
396 	ASSERT3U(l->l_phys->l_hdr.lh_magic, ==, ZAP_LEAF_MAGIC);
397 
398 again:
399 	for (chunkp = LEAF_HASH_ENTPTR(l, zn->zn_hash);
400 	    *chunkp != CHAIN_END; chunkp = &le->le_next) {
401 		uint16_t chunk = *chunkp;
402 		le = ZAP_LEAF_ENTRY(l, chunk);
403 
404 		ASSERT3U(chunk, <, ZAP_LEAF_NUMCHUNKS(l));
405 		ASSERT3U(le->le_type, ==, ZAP_CHUNK_ENTRY);
406 
407 		if (le->le_hash != zn->zn_hash)
408 			continue;
409 
410 		/*
411 		 * NB: the entry chain is always sorted by cd on
412 		 * normalized zap objects, so this will find the
413 		 * lowest-cd match for MT_FIRST.
414 		 */
415 		ASSERT(zn->zn_matchtype == MT_EXACT ||
416 		    (l->l_phys->l_hdr.lh_flags & ZLF_ENTRIES_CDSORTED));
417 		if (zap_leaf_array_match(l, zn, le->le_name_chunk,
418 		    le->le_name_length)) {
419 			zeh->zeh_num_integers = le->le_value_length;
420 			zeh->zeh_integer_size = le->le_int_size;
421 			zeh->zeh_cd = le->le_cd;
422 			zeh->zeh_hash = le->le_hash;
423 			zeh->zeh_chunkp = chunkp;
424 			zeh->zeh_leaf = l;
425 			return (0);
426 		}
427 	}
428 
429 	/*
430 	 * NB: we could of course do this in one pass, but that would be
431 	 * a pain.  We'll see if MT_BEST is even used much.
432 	 */
433 	if (zn->zn_matchtype == MT_BEST) {
434 		zn->zn_matchtype = MT_FIRST;
435 		goto again;
436 	}
437 
438 	return (ENOENT);
439 }
440 
441 /* Return (h1,cd1 >= h2,cd2) */
442 #define	HCD_GTEQ(h1, cd1, h2, cd2) \
443 	((h1 > h2) ? TRUE : ((h1 == h2 && cd1 >= cd2) ? TRUE : FALSE))
444 
445 int
446 zap_leaf_lookup_closest(zap_leaf_t *l,
447     uint64_t h, uint32_t cd, zap_entry_handle_t *zeh)
448 {
449 	uint16_t chunk;
450 	uint64_t besth = -1ULL;
451 	uint32_t bestcd = -1U;
452 	uint16_t bestlh = ZAP_LEAF_HASH_NUMENTRIES(l)-1;
453 	uint16_t lh;
454 	struct zap_leaf_entry *le;
455 
456 	ASSERT3U(l->l_phys->l_hdr.lh_magic, ==, ZAP_LEAF_MAGIC);
457 
458 	for (lh = LEAF_HASH(l, h); lh <= bestlh; lh++) {
459 		for (chunk = l->l_phys->l_hash[lh];
460 		    chunk != CHAIN_END; chunk = le->le_next) {
461 			le = ZAP_LEAF_ENTRY(l, chunk);
462 
463 			ASSERT3U(chunk, <, ZAP_LEAF_NUMCHUNKS(l));
464 			ASSERT3U(le->le_type, ==, ZAP_CHUNK_ENTRY);
465 
466 			if (HCD_GTEQ(le->le_hash, le->le_cd, h, cd) &&
467 			    HCD_GTEQ(besth, bestcd, le->le_hash, le->le_cd)) {
468 				ASSERT3U(bestlh, >=, lh);
469 				bestlh = lh;
470 				besth = le->le_hash;
471 				bestcd = le->le_cd;
472 
473 				zeh->zeh_num_integers = le->le_value_length;
474 				zeh->zeh_integer_size = le->le_int_size;
475 				zeh->zeh_cd = le->le_cd;
476 				zeh->zeh_hash = le->le_hash;
477 				zeh->zeh_fakechunk = chunk;
478 				zeh->zeh_chunkp = &zeh->zeh_fakechunk;
479 				zeh->zeh_leaf = l;
480 			}
481 		}
482 	}
483 
484 	return (bestcd == -1U ? ENOENT : 0);
485 }
486 
487 int
488 zap_entry_read(const zap_entry_handle_t *zeh,
489     uint8_t integer_size, uint64_t num_integers, void *buf)
490 {
491 	struct zap_leaf_entry *le =
492 	    ZAP_LEAF_ENTRY(zeh->zeh_leaf, *zeh->zeh_chunkp);
493 	ASSERT3U(le->le_type, ==, ZAP_CHUNK_ENTRY);
494 
495 	if (le->le_int_size > integer_size)
496 		return (EINVAL);
497 
498 	zap_leaf_array_read(zeh->zeh_leaf, le->le_value_chunk, le->le_int_size,
499 	    le->le_value_length, integer_size, num_integers, buf);
500 
501 	if (zeh->zeh_num_integers > num_integers)
502 		return (EOVERFLOW);
503 	return (0);
504 
505 }
506 
507 int
508 zap_entry_read_name(zap_t *zap, const zap_entry_handle_t *zeh, uint16_t buflen,
509     char *buf)
510 {
511 	struct zap_leaf_entry *le =
512 	    ZAP_LEAF_ENTRY(zeh->zeh_leaf, *zeh->zeh_chunkp);
513 	ASSERT3U(le->le_type, ==, ZAP_CHUNK_ENTRY);
514 
515 	if (zap_getflags(zap) & ZAP_FLAG_UINT64_KEY) {
516 		zap_leaf_array_read(zeh->zeh_leaf, le->le_name_chunk, 8,
517 		    le->le_name_length, 8, buflen / 8, buf);
518 	} else {
519 		zap_leaf_array_read(zeh->zeh_leaf, le->le_name_chunk, 1,
520 		    le->le_name_length, 1, buflen, buf);
521 	}
522 	if (le->le_name_length > buflen)
523 		return (EOVERFLOW);
524 	return (0);
525 }
526 
527 int
528 zap_entry_update(zap_entry_handle_t *zeh,
529 	uint8_t integer_size, uint64_t num_integers, const void *buf)
530 {
531 	int delta_chunks;
532 	zap_leaf_t *l = zeh->zeh_leaf;
533 	struct zap_leaf_entry *le = ZAP_LEAF_ENTRY(l, *zeh->zeh_chunkp);
534 
535 	delta_chunks = ZAP_LEAF_ARRAY_NCHUNKS(num_integers * integer_size) -
536 	    ZAP_LEAF_ARRAY_NCHUNKS(le->le_value_length * le->le_int_size);
537 
538 	if ((int)l->l_phys->l_hdr.lh_nfree < delta_chunks)
539 		return (EAGAIN);
540 
541 	/*
542 	 * We should search other chained leaves (via
543 	 * zap_entry_remove,create?) otherwise returning EAGAIN will
544 	 * just send us into an infinite loop if we have to chain
545 	 * another leaf block, rather than being able to split this
546 	 * block.
547 	 */
548 
549 	zap_leaf_array_free(l, &le->le_value_chunk);
550 	le->le_value_chunk =
551 	    zap_leaf_array_create(l, buf, integer_size, num_integers);
552 	le->le_value_length = num_integers;
553 	le->le_int_size = integer_size;
554 	return (0);
555 }
556 
557 void
558 zap_entry_remove(zap_entry_handle_t *zeh)
559 {
560 	uint16_t entry_chunk;
561 	struct zap_leaf_entry *le;
562 	zap_leaf_t *l = zeh->zeh_leaf;
563 
564 	ASSERT3P(zeh->zeh_chunkp, !=, &zeh->zeh_fakechunk);
565 
566 	entry_chunk = *zeh->zeh_chunkp;
567 	le = ZAP_LEAF_ENTRY(l, entry_chunk);
568 	ASSERT3U(le->le_type, ==, ZAP_CHUNK_ENTRY);
569 
570 	zap_leaf_array_free(l, &le->le_name_chunk);
571 	zap_leaf_array_free(l, &le->le_value_chunk);
572 
573 	*zeh->zeh_chunkp = le->le_next;
574 	zap_leaf_chunk_free(l, entry_chunk);
575 
576 	l->l_phys->l_hdr.lh_nentries--;
577 }
578 
579 int
580 zap_entry_create(zap_leaf_t *l, zap_name_t *zn, uint32_t cd,
581     uint8_t integer_size, uint64_t num_integers, const void *buf,
582     zap_entry_handle_t *zeh)
583 {
584 	uint16_t chunk;
585 	uint16_t *chunkp;
586 	struct zap_leaf_entry *le;
587 	uint64_t valuelen;
588 	int numchunks;
589 	uint64_t h = zn->zn_hash;
590 
591 	valuelen = integer_size * num_integers;
592 
593 	numchunks = 1 +
594 	    ZAP_LEAF_ARRAY_NCHUNKS(zn->zn_key_orig_len * zn->zn_key_intlen) +
595 	    ZAP_LEAF_ARRAY_NCHUNKS(valuelen);
596 	if (numchunks > ZAP_LEAF_NUMCHUNKS(l))
597 		return (E2BIG);
598 
599 	if (cd == ZAP_NEED_CD) {
600 		/* find the lowest unused cd */
601 		if (l->l_phys->l_hdr.lh_flags & ZLF_ENTRIES_CDSORTED) {
602 			cd = 0;
603 
604 			for (chunk = *LEAF_HASH_ENTPTR(l, h);
605 			    chunk != CHAIN_END; chunk = le->le_next) {
606 				le = ZAP_LEAF_ENTRY(l, chunk);
607 				if (le->le_cd > cd)
608 					break;
609 				if (le->le_hash == h) {
610 					ASSERT3U(cd, ==, le->le_cd);
611 					cd++;
612 				}
613 			}
614 		} else {
615 			/* old unsorted format; do it the O(n^2) way */
616 			for (cd = 0; ; cd++) {
617 				for (chunk = *LEAF_HASH_ENTPTR(l, h);
618 				    chunk != CHAIN_END; chunk = le->le_next) {
619 					le = ZAP_LEAF_ENTRY(l, chunk);
620 					if (le->le_hash == h &&
621 					    le->le_cd == cd) {
622 						break;
623 					}
624 				}
625 				/* If this cd is not in use, we are good. */
626 				if (chunk == CHAIN_END)
627 					break;
628 			}
629 		}
630 		/*
631 		 * We would run out of space in a block before we could
632 		 * store enough entries to run out of CD values.
633 		 */
634 		ASSERT3U(cd, <, zap_maxcd(zn->zn_zap));
635 	}
636 
637 	if (l->l_phys->l_hdr.lh_nfree < numchunks)
638 		return (EAGAIN);
639 
640 	/* make the entry */
641 	chunk = zap_leaf_chunk_alloc(l);
642 	le = ZAP_LEAF_ENTRY(l, chunk);
643 	le->le_type = ZAP_CHUNK_ENTRY;
644 	le->le_name_chunk = zap_leaf_array_create(l, zn->zn_key_orig,
645 	    zn->zn_key_intlen, zn->zn_key_orig_len);
646 	le->le_name_length = zn->zn_key_orig_len;
647 	le->le_value_chunk =
648 	    zap_leaf_array_create(l, buf, integer_size, num_integers);
649 	le->le_value_length = num_integers;
650 	le->le_int_size = integer_size;
651 	le->le_hash = h;
652 	le->le_cd = cd;
653 
654 	/* link it into the hash chain */
655 	/* XXX if we did the search above, we could just use that */
656 	chunkp = zap_leaf_rehash_entry(l, chunk);
657 
658 	l->l_phys->l_hdr.lh_nentries++;
659 
660 	zeh->zeh_leaf = l;
661 	zeh->zeh_num_integers = num_integers;
662 	zeh->zeh_integer_size = le->le_int_size;
663 	zeh->zeh_cd = le->le_cd;
664 	zeh->zeh_hash = le->le_hash;
665 	zeh->zeh_chunkp = chunkp;
666 
667 	return (0);
668 }
669 
670 /*
671  * Determine if there is another entry with the same normalized form.
672  * For performance purposes, either zn or name must be provided (the
673  * other can be NULL).  Note, there usually won't be any hash
674  * conflicts, in which case we don't need the concatenated/normalized
675  * form of the name.  But all callers have one of these on hand anyway,
676  * so might as well take advantage.  A cleaner but slower interface
677  * would accept neither argument, and compute the normalized name as
678  * needed (using zap_name_alloc(zap_entry_read_name(zeh))).
679  */
680 boolean_t
681 zap_entry_normalization_conflict(zap_entry_handle_t *zeh, zap_name_t *zn,
682     const char *name, zap_t *zap)
683 {
684 	uint64_t chunk;
685 	struct zap_leaf_entry *le;
686 	boolean_t allocdzn = B_FALSE;
687 
688 	if (zap->zap_normflags == 0)
689 		return (B_FALSE);
690 
691 	for (chunk = *LEAF_HASH_ENTPTR(zeh->zeh_leaf, zeh->zeh_hash);
692 	    chunk != CHAIN_END; chunk = le->le_next) {
693 		le = ZAP_LEAF_ENTRY(zeh->zeh_leaf, chunk);
694 		if (le->le_hash != zeh->zeh_hash)
695 			continue;
696 		if (le->le_cd == zeh->zeh_cd)
697 			continue;
698 
699 		if (zn == NULL) {
700 			zn = zap_name_alloc(zap, name, MT_FIRST);
701 			allocdzn = B_TRUE;
702 		}
703 		if (zap_leaf_array_match(zeh->zeh_leaf, zn,
704 		    le->le_name_chunk, le->le_name_length)) {
705 			if (allocdzn)
706 				zap_name_free(zn);
707 			return (B_TRUE);
708 		}
709 	}
710 	if (allocdzn)
711 		zap_name_free(zn);
712 	return (B_FALSE);
713 }
714 
715 /*
716  * Routines for transferring entries between leafs.
717  */
718 
719 static uint16_t *
720 zap_leaf_rehash_entry(zap_leaf_t *l, uint16_t entry)
721 {
722 	struct zap_leaf_entry *le = ZAP_LEAF_ENTRY(l, entry);
723 	struct zap_leaf_entry *le2;
724 	uint16_t *chunkp;
725 
726 	/*
727 	 * keep the entry chain sorted by cd
728 	 * NB: this will not cause problems for unsorted leafs, though
729 	 * it is unnecessary there.
730 	 */
731 	for (chunkp = LEAF_HASH_ENTPTR(l, le->le_hash);
732 	    *chunkp != CHAIN_END; chunkp = &le2->le_next) {
733 		le2 = ZAP_LEAF_ENTRY(l, *chunkp);
734 		if (le2->le_cd > le->le_cd)
735 			break;
736 	}
737 
738 	le->le_next = *chunkp;
739 	*chunkp = entry;
740 	return (chunkp);
741 }
742 
743 static uint16_t
744 zap_leaf_transfer_array(zap_leaf_t *l, uint16_t chunk, zap_leaf_t *nl)
745 {
746 	uint16_t new_chunk;
747 	uint16_t *nchunkp = &new_chunk;
748 
749 	while (chunk != CHAIN_END) {
750 		uint16_t nchunk = zap_leaf_chunk_alloc(nl);
751 		struct zap_leaf_array *nla =
752 		    &ZAP_LEAF_CHUNK(nl, nchunk).l_array;
753 		struct zap_leaf_array *la =
754 		    &ZAP_LEAF_CHUNK(l, chunk).l_array;
755 		int nextchunk = la->la_next;
756 
757 		ASSERT3U(chunk, <, ZAP_LEAF_NUMCHUNKS(l));
758 		ASSERT3U(nchunk, <, ZAP_LEAF_NUMCHUNKS(l));
759 
760 		*nla = *la; /* structure assignment */
761 
762 		zap_leaf_chunk_free(l, chunk);
763 		chunk = nextchunk;
764 		*nchunkp = nchunk;
765 		nchunkp = &nla->la_next;
766 	}
767 	*nchunkp = CHAIN_END;
768 	return (new_chunk);
769 }
770 
771 static void
772 zap_leaf_transfer_entry(zap_leaf_t *l, int entry, zap_leaf_t *nl)
773 {
774 	struct zap_leaf_entry *le, *nle;
775 	uint16_t chunk;
776 
777 	le = ZAP_LEAF_ENTRY(l, entry);
778 	ASSERT3U(le->le_type, ==, ZAP_CHUNK_ENTRY);
779 
780 	chunk = zap_leaf_chunk_alloc(nl);
781 	nle = ZAP_LEAF_ENTRY(nl, chunk);
782 	*nle = *le; /* structure assignment */
783 
784 	(void) zap_leaf_rehash_entry(nl, chunk);
785 
786 	nle->le_name_chunk = zap_leaf_transfer_array(l, le->le_name_chunk, nl);
787 	nle->le_value_chunk =
788 	    zap_leaf_transfer_array(l, le->le_value_chunk, nl);
789 
790 	zap_leaf_chunk_free(l, entry);
791 
792 	l->l_phys->l_hdr.lh_nentries--;
793 	nl->l_phys->l_hdr.lh_nentries++;
794 }
795 
796 /*
797  * Transfer the entries whose hash prefix ends in 1 to the new leaf.
798  */
799 void
800 zap_leaf_split(zap_leaf_t *l, zap_leaf_t *nl, boolean_t sort)
801 {
802 	int i;
803 	int bit = 64 - 1 - l->l_phys->l_hdr.lh_prefix_len;
804 
805 	/* set new prefix and prefix_len */
806 	l->l_phys->l_hdr.lh_prefix <<= 1;
807 	l->l_phys->l_hdr.lh_prefix_len++;
808 	nl->l_phys->l_hdr.lh_prefix = l->l_phys->l_hdr.lh_prefix | 1;
809 	nl->l_phys->l_hdr.lh_prefix_len = l->l_phys->l_hdr.lh_prefix_len;
810 
811 	/* break existing hash chains */
812 	zap_memset(l->l_phys->l_hash, CHAIN_END, 2*ZAP_LEAF_HASH_NUMENTRIES(l));
813 
814 	if (sort)
815 		l->l_phys->l_hdr.lh_flags |= ZLF_ENTRIES_CDSORTED;
816 
817 	/*
818 	 * Transfer entries whose hash bit 'bit' is set to nl; rehash
819 	 * the remaining entries
820 	 *
821 	 * NB: We could find entries via the hashtable instead. That
822 	 * would be O(hashents+numents) rather than O(numblks+numents),
823 	 * but this accesses memory more sequentially, and when we're
824 	 * called, the block is usually pretty full.
825 	 */
826 	for (i = 0; i < ZAP_LEAF_NUMCHUNKS(l); i++) {
827 		struct zap_leaf_entry *le = ZAP_LEAF_ENTRY(l, i);
828 		if (le->le_type != ZAP_CHUNK_ENTRY)
829 			continue;
830 
831 		if (le->le_hash & (1ULL << bit))
832 			zap_leaf_transfer_entry(l, i, nl);
833 		else
834 			(void) zap_leaf_rehash_entry(l, i);
835 	}
836 }
837 
838 void
839 zap_leaf_stats(zap_t *zap, zap_leaf_t *l, zap_stats_t *zs)
840 {
841 	int i, n;
842 
843 	n = zap->zap_f.zap_phys->zap_ptrtbl.zt_shift -
844 	    l->l_phys->l_hdr.lh_prefix_len;
845 	n = MIN(n, ZAP_HISTOGRAM_SIZE-1);
846 	zs->zs_leafs_with_2n_pointers[n]++;
847 
848 
849 	n = l->l_phys->l_hdr.lh_nentries/5;
850 	n = MIN(n, ZAP_HISTOGRAM_SIZE-1);
851 	zs->zs_blocks_with_n5_entries[n]++;
852 
853 	n = ((1<<FZAP_BLOCK_SHIFT(zap)) -
854 	    l->l_phys->l_hdr.lh_nfree * (ZAP_LEAF_ARRAY_BYTES+1))*10 /
855 	    (1<<FZAP_BLOCK_SHIFT(zap));
856 	n = MIN(n, ZAP_HISTOGRAM_SIZE-1);
857 	zs->zs_blocks_n_tenths_full[n]++;
858 
859 	for (i = 0; i < ZAP_LEAF_HASH_NUMENTRIES(l); i++) {
860 		int nentries = 0;
861 		int chunk = l->l_phys->l_hash[i];
862 
863 		while (chunk != CHAIN_END) {
864 			struct zap_leaf_entry *le =
865 			    ZAP_LEAF_ENTRY(l, chunk);
866 
867 			n = 1 + ZAP_LEAF_ARRAY_NCHUNKS(le->le_name_length) +
868 			    ZAP_LEAF_ARRAY_NCHUNKS(le->le_value_length *
869 			    le->le_int_size);
870 			n = MIN(n, ZAP_HISTOGRAM_SIZE-1);
871 			zs->zs_entries_using_n_chunks[n]++;
872 
873 			chunk = le->le_next;
874 			nentries++;
875 		}
876 
877 		n = nentries;
878 		n = MIN(n, ZAP_HISTOGRAM_SIZE-1);
879 		zs->zs_buckets_with_n_entries[n]++;
880 	}
881 }
882