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