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.
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.
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]
23 * Copyright (c) 2005, 2010, Oracle and/or its affiliates. All rights reserved.
24 * Copyright (c) 2013, 2015 by Delphix. All rights reserved.
25 * Copyright 2017 Nexenta Systems, Inc.
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.
37 #include <sys/zfs_context.h>
38 #include <sys/fs/zfs.h>
40 #include <sys/zap_impl.h>
41 #include <sys/zap_leaf.h>
44 static uint16_t *zap_leaf_rehash_entry(zap_leaf_t
*l
, uint16_t entry
);
46 #define CHAIN_END 0xffff /* end of the chunk chain */
48 /* half the (current) minimum block size */
49 #define MAX_ARRAY_BYTES (8<<10)
51 #define LEAF_HASH(l, h) \
52 ((ZAP_LEAF_HASH_NUMENTRIES(l)-1) & \
54 (64 - ZAP_LEAF_HASH_SHIFT(l) - zap_leaf_phys(l)->l_hdr.lh_prefix_len)))
56 #define LEAF_HASH_ENTPTR(l, h) (&zap_leaf_phys(l)->l_hash[LEAF_HASH(l, h)])
58 extern inline zap_leaf_phys_t
*zap_leaf_phys(zap_leaf_t
*l
);
61 zap_memset(void *a
, int c
, size_t n
)
71 stv(int len
, void *addr
, uint64_t value
)
75 *(uint8_t *)addr
= value
;
78 *(uint16_t *)addr
= value
;
81 *(uint32_t *)addr
= value
;
84 *(uint64_t *)addr
= value
;
87 cmn_err(CE_PANIC
, "bad int len %d", len
);
92 ldv(int len
, const void *addr
)
96 return (*(uint8_t *)addr
);
98 return (*(uint16_t *)addr
);
100 return (*(uint32_t *)addr
);
102 return (*(uint64_t *)addr
);
104 cmn_err(CE_PANIC
, "bad int len %d", len
);
106 return (0xFEEDFACEDEADBEEFULL
);
110 zap_leaf_byteswap(zap_leaf_phys_t
*buf
, int size
)
116 l_dbuf
.db_data
= buf
;
117 l
.l_bs
= highbit64(size
) - 1;
120 buf
->l_hdr
.lh_block_type
= BSWAP_64(buf
->l_hdr
.lh_block_type
);
121 buf
->l_hdr
.lh_prefix
= BSWAP_64(buf
->l_hdr
.lh_prefix
);
122 buf
->l_hdr
.lh_magic
= BSWAP_32(buf
->l_hdr
.lh_magic
);
123 buf
->l_hdr
.lh_nfree
= BSWAP_16(buf
->l_hdr
.lh_nfree
);
124 buf
->l_hdr
.lh_nentries
= BSWAP_16(buf
->l_hdr
.lh_nentries
);
125 buf
->l_hdr
.lh_prefix_len
= BSWAP_16(buf
->l_hdr
.lh_prefix_len
);
126 buf
->l_hdr
.lh_freelist
= BSWAP_16(buf
->l_hdr
.lh_freelist
);
128 for (i
= 0; i
< ZAP_LEAF_HASH_NUMENTRIES(&l
); i
++)
129 buf
->l_hash
[i
] = BSWAP_16(buf
->l_hash
[i
]);
131 for (i
= 0; i
< ZAP_LEAF_NUMCHUNKS(&l
); i
++) {
132 zap_leaf_chunk_t
*lc
= &ZAP_LEAF_CHUNK(&l
, i
);
133 struct zap_leaf_entry
*le
;
135 switch (lc
->l_free
.lf_type
) {
136 case ZAP_CHUNK_ENTRY
:
139 le
->le_type
= BSWAP_8(le
->le_type
);
140 le
->le_value_intlen
= BSWAP_8(le
->le_value_intlen
);
141 le
->le_next
= BSWAP_16(le
->le_next
);
142 le
->le_name_chunk
= BSWAP_16(le
->le_name_chunk
);
143 le
->le_name_numints
= BSWAP_16(le
->le_name_numints
);
144 le
->le_value_chunk
= BSWAP_16(le
->le_value_chunk
);
145 le
->le_value_numints
= BSWAP_16(le
->le_value_numints
);
146 le
->le_cd
= BSWAP_32(le
->le_cd
);
147 le
->le_hash
= BSWAP_64(le
->le_hash
);
150 lc
->l_free
.lf_type
= BSWAP_8(lc
->l_free
.lf_type
);
151 lc
->l_free
.lf_next
= BSWAP_16(lc
->l_free
.lf_next
);
153 case ZAP_CHUNK_ARRAY
:
154 lc
->l_array
.la_type
= BSWAP_8(lc
->l_array
.la_type
);
155 lc
->l_array
.la_next
= BSWAP_16(lc
->l_array
.la_next
);
156 /* la_array doesn't need swapping */
159 cmn_err(CE_PANIC
, "bad leaf type %d",
166 zap_leaf_init(zap_leaf_t
*l
, boolean_t sort
)
170 l
->l_bs
= highbit64(l
->l_dbuf
->db_size
) - 1;
171 zap_memset(&zap_leaf_phys(l
)->l_hdr
, 0,
172 sizeof (struct zap_leaf_header
));
173 zap_memset(zap_leaf_phys(l
)->l_hash
, CHAIN_END
,
174 2*ZAP_LEAF_HASH_NUMENTRIES(l
));
175 for (i
= 0; i
< ZAP_LEAF_NUMCHUNKS(l
); i
++) {
176 ZAP_LEAF_CHUNK(l
, i
).l_free
.lf_type
= ZAP_CHUNK_FREE
;
177 ZAP_LEAF_CHUNK(l
, i
).l_free
.lf_next
= i
+1;
179 ZAP_LEAF_CHUNK(l
, ZAP_LEAF_NUMCHUNKS(l
)-1).l_free
.lf_next
= CHAIN_END
;
180 zap_leaf_phys(l
)->l_hdr
.lh_block_type
= ZBT_LEAF
;
181 zap_leaf_phys(l
)->l_hdr
.lh_magic
= ZAP_LEAF_MAGIC
;
182 zap_leaf_phys(l
)->l_hdr
.lh_nfree
= ZAP_LEAF_NUMCHUNKS(l
);
184 zap_leaf_phys(l
)->l_hdr
.lh_flags
|= ZLF_ENTRIES_CDSORTED
;
188 * Routines which manipulate leaf chunks (l_chunk[]).
192 zap_leaf_chunk_alloc(zap_leaf_t
*l
)
196 ASSERT(zap_leaf_phys(l
)->l_hdr
.lh_nfree
> 0);
198 chunk
= zap_leaf_phys(l
)->l_hdr
.lh_freelist
;
199 ASSERT3U(chunk
, <, ZAP_LEAF_NUMCHUNKS(l
));
200 ASSERT3U(ZAP_LEAF_CHUNK(l
, chunk
).l_free
.lf_type
, ==, ZAP_CHUNK_FREE
);
202 zap_leaf_phys(l
)->l_hdr
.lh_freelist
=
203 ZAP_LEAF_CHUNK(l
, chunk
).l_free
.lf_next
;
205 zap_leaf_phys(l
)->l_hdr
.lh_nfree
--;
211 zap_leaf_chunk_free(zap_leaf_t
*l
, uint16_t chunk
)
213 struct zap_leaf_free
*zlf
= &ZAP_LEAF_CHUNK(l
, chunk
).l_free
;
214 ASSERT3U(zap_leaf_phys(l
)->l_hdr
.lh_nfree
, <, ZAP_LEAF_NUMCHUNKS(l
));
215 ASSERT3U(chunk
, <, ZAP_LEAF_NUMCHUNKS(l
));
216 ASSERT(zlf
->lf_type
!= ZAP_CHUNK_FREE
);
218 zlf
->lf_type
= ZAP_CHUNK_FREE
;
219 zlf
->lf_next
= zap_leaf_phys(l
)->l_hdr
.lh_freelist
;
220 bzero(zlf
->lf_pad
, sizeof (zlf
->lf_pad
)); /* help it to compress */
221 zap_leaf_phys(l
)->l_hdr
.lh_freelist
= chunk
;
223 zap_leaf_phys(l
)->l_hdr
.lh_nfree
++;
227 * Routines which manipulate leaf arrays (zap_leaf_array type chunks).
231 zap_leaf_array_create(zap_leaf_t
*l
, const char *buf
,
232 int integer_size
, int num_integers
)
235 uint16_t *chunkp
= &chunk_head
;
238 int shift
= (integer_size
-1)*8;
239 int len
= num_integers
;
241 ASSERT3U(num_integers
* integer_size
, <, MAX_ARRAY_BYTES
);
244 uint16_t chunk
= zap_leaf_chunk_alloc(l
);
245 struct zap_leaf_array
*la
= &ZAP_LEAF_CHUNK(l
, chunk
).l_array
;
248 la
->la_type
= ZAP_CHUNK_ARRAY
;
249 for (i
= 0; i
< ZAP_LEAF_ARRAY_BYTES
; i
++) {
251 value
= ldv(integer_size
, buf
);
252 la
->la_array
[i
] = value
>> shift
;
254 if (++byten
== integer_size
) {
263 chunkp
= &la
->la_next
;
271 zap_leaf_array_free(zap_leaf_t
*l
, uint16_t *chunkp
)
273 uint16_t chunk
= *chunkp
;
277 while (chunk
!= CHAIN_END
) {
278 int nextchunk
= ZAP_LEAF_CHUNK(l
, chunk
).l_array
.la_next
;
279 ASSERT3U(ZAP_LEAF_CHUNK(l
, chunk
).l_array
.la_type
, ==,
281 zap_leaf_chunk_free(l
, chunk
);
286 /* array_len and buf_len are in integers, not bytes */
288 zap_leaf_array_read(zap_leaf_t
*l
, uint16_t chunk
,
289 int array_int_len
, int array_len
, int buf_int_len
, uint64_t buf_len
,
292 int len
= MIN(array_len
, buf_len
);
297 ASSERT3U(array_int_len
, <=, buf_int_len
);
299 /* Fast path for one 8-byte integer */
300 if (array_int_len
== 8 && buf_int_len
== 8 && len
== 1) {
301 struct zap_leaf_array
*la
= &ZAP_LEAF_CHUNK(l
, chunk
).l_array
;
302 uint8_t *ip
= la
->la_array
;
303 uint64_t *buf64
= buf
;
305 *buf64
= (uint64_t)ip
[0] << 56 | (uint64_t)ip
[1] << 48 |
306 (uint64_t)ip
[2] << 40 | (uint64_t)ip
[3] << 32 |
307 (uint64_t)ip
[4] << 24 | (uint64_t)ip
[5] << 16 |
308 (uint64_t)ip
[6] << 8 | (uint64_t)ip
[7];
312 /* Fast path for an array of 1-byte integers (eg. the entry name) */
313 if (array_int_len
== 1 && buf_int_len
== 1 &&
314 buf_len
> array_len
+ ZAP_LEAF_ARRAY_BYTES
) {
315 while (chunk
!= CHAIN_END
) {
316 struct zap_leaf_array
*la
=
317 &ZAP_LEAF_CHUNK(l
, chunk
).l_array
;
318 bcopy(la
->la_array
, p
, ZAP_LEAF_ARRAY_BYTES
);
319 p
+= ZAP_LEAF_ARRAY_BYTES
;
326 struct zap_leaf_array
*la
= &ZAP_LEAF_CHUNK(l
, chunk
).l_array
;
329 ASSERT3U(chunk
, <, ZAP_LEAF_NUMCHUNKS(l
));
330 for (i
= 0; i
< ZAP_LEAF_ARRAY_BYTES
&& len
> 0; i
++) {
331 value
= (value
<< 8) | la
->la_array
[i
];
333 if (byten
== array_int_len
) {
334 stv(buf_int_len
, p
, value
);
347 zap_leaf_array_match(zap_leaf_t
*l
, zap_name_t
*zn
,
348 int chunk
, int array_numints
)
352 if (zap_getflags(zn
->zn_zap
) & ZAP_FLAG_UINT64_KEY
) {
356 ASSERT(zn
->zn_key_intlen
== sizeof (*thiskey
));
357 thiskey
= kmem_alloc(array_numints
* sizeof (*thiskey
),
360 zap_leaf_array_read(l
, chunk
, sizeof (*thiskey
), array_numints
,
361 sizeof (*thiskey
), array_numints
, thiskey
);
362 match
= bcmp(thiskey
, zn
->zn_key_orig
,
363 array_numints
* sizeof (*thiskey
)) == 0;
364 kmem_free(thiskey
, array_numints
* sizeof (*thiskey
));
368 ASSERT(zn
->zn_key_intlen
== 1);
369 if (zn
->zn_matchtype
& MT_NORMALIZE
) {
370 char *thisname
= kmem_alloc(array_numints
, KM_SLEEP
);
373 zap_leaf_array_read(l
, chunk
, sizeof (char), array_numints
,
374 sizeof (char), array_numints
, thisname
);
375 match
= zap_match(zn
, thisname
);
376 kmem_free(thisname
, array_numints
);
381 * Fast path for exact matching.
382 * First check that the lengths match, so that we don't read
383 * past the end of the zn_key_orig array.
385 if (array_numints
!= zn
->zn_key_orig_numints
)
387 while (bseen
< array_numints
) {
388 struct zap_leaf_array
*la
= &ZAP_LEAF_CHUNK(l
, chunk
).l_array
;
389 int toread
= MIN(array_numints
- bseen
, ZAP_LEAF_ARRAY_BYTES
);
390 ASSERT3U(chunk
, <, ZAP_LEAF_NUMCHUNKS(l
));
391 if (bcmp(la
->la_array
, (char *)zn
->zn_key_orig
+ bseen
, toread
))
396 return (bseen
== array_numints
);
400 * Routines which manipulate leaf entries.
404 zap_leaf_lookup(zap_leaf_t
*l
, zap_name_t
*zn
, zap_entry_handle_t
*zeh
)
407 struct zap_leaf_entry
*le
;
409 ASSERT3U(zap_leaf_phys(l
)->l_hdr
.lh_magic
, ==, ZAP_LEAF_MAGIC
);
411 for (chunkp
= LEAF_HASH_ENTPTR(l
, zn
->zn_hash
);
412 *chunkp
!= CHAIN_END
; chunkp
= &le
->le_next
) {
413 uint16_t chunk
= *chunkp
;
414 le
= ZAP_LEAF_ENTRY(l
, chunk
);
416 ASSERT3U(chunk
, <, ZAP_LEAF_NUMCHUNKS(l
));
417 ASSERT3U(le
->le_type
, ==, ZAP_CHUNK_ENTRY
);
419 if (le
->le_hash
!= zn
->zn_hash
)
423 * NB: the entry chain is always sorted by cd on
424 * normalized zap objects, so this will find the
425 * lowest-cd match for MT_NORMALIZE.
427 ASSERT((zn
->zn_matchtype
== 0) ||
428 (zap_leaf_phys(l
)->l_hdr
.lh_flags
& ZLF_ENTRIES_CDSORTED
));
429 if (zap_leaf_array_match(l
, zn
, le
->le_name_chunk
,
430 le
->le_name_numints
)) {
431 zeh
->zeh_num_integers
= le
->le_value_numints
;
432 zeh
->zeh_integer_size
= le
->le_value_intlen
;
433 zeh
->zeh_cd
= le
->le_cd
;
434 zeh
->zeh_hash
= le
->le_hash
;
435 zeh
->zeh_chunkp
= chunkp
;
441 return (SET_ERROR(ENOENT
));
444 /* Return (h1,cd1 >= h2,cd2) */
445 #define HCD_GTEQ(h1, cd1, h2, cd2) \
446 ((h1 > h2) ? TRUE : ((h1 == h2 && cd1 >= cd2) ? TRUE : FALSE))
449 zap_leaf_lookup_closest(zap_leaf_t
*l
,
450 uint64_t h
, uint32_t cd
, zap_entry_handle_t
*zeh
)
453 uint64_t besth
= -1ULL;
454 uint32_t bestcd
= -1U;
455 uint16_t bestlh
= ZAP_LEAF_HASH_NUMENTRIES(l
)-1;
457 struct zap_leaf_entry
*le
;
459 ASSERT3U(zap_leaf_phys(l
)->l_hdr
.lh_magic
, ==, ZAP_LEAF_MAGIC
);
461 for (lh
= LEAF_HASH(l
, h
); lh
<= bestlh
; lh
++) {
462 for (chunk
= zap_leaf_phys(l
)->l_hash
[lh
];
463 chunk
!= CHAIN_END
; chunk
= le
->le_next
) {
464 le
= ZAP_LEAF_ENTRY(l
, chunk
);
466 ASSERT3U(chunk
, <, ZAP_LEAF_NUMCHUNKS(l
));
467 ASSERT3U(le
->le_type
, ==, ZAP_CHUNK_ENTRY
);
469 if (HCD_GTEQ(le
->le_hash
, le
->le_cd
, h
, cd
) &&
470 HCD_GTEQ(besth
, bestcd
, le
->le_hash
, le
->le_cd
)) {
471 ASSERT3U(bestlh
, >=, lh
);
476 zeh
->zeh_num_integers
= le
->le_value_numints
;
477 zeh
->zeh_integer_size
= le
->le_value_intlen
;
478 zeh
->zeh_cd
= le
->le_cd
;
479 zeh
->zeh_hash
= le
->le_hash
;
480 zeh
->zeh_fakechunk
= chunk
;
481 zeh
->zeh_chunkp
= &zeh
->zeh_fakechunk
;
487 return (bestcd
== -1U ? ENOENT
: 0);
491 zap_entry_read(const zap_entry_handle_t
*zeh
,
492 uint8_t integer_size
, uint64_t num_integers
, void *buf
)
494 struct zap_leaf_entry
*le
=
495 ZAP_LEAF_ENTRY(zeh
->zeh_leaf
, *zeh
->zeh_chunkp
);
496 ASSERT3U(le
->le_type
, ==, ZAP_CHUNK_ENTRY
);
498 if (le
->le_value_intlen
> integer_size
)
499 return (SET_ERROR(EINVAL
));
501 zap_leaf_array_read(zeh
->zeh_leaf
, le
->le_value_chunk
,
502 le
->le_value_intlen
, le
->le_value_numints
,
503 integer_size
, num_integers
, buf
);
505 if (zeh
->zeh_num_integers
> num_integers
)
506 return (SET_ERROR(EOVERFLOW
));
512 zap_entry_read_name(zap_t
*zap
, const zap_entry_handle_t
*zeh
, uint16_t buflen
,
515 struct zap_leaf_entry
*le
=
516 ZAP_LEAF_ENTRY(zeh
->zeh_leaf
, *zeh
->zeh_chunkp
);
517 ASSERT3U(le
->le_type
, ==, ZAP_CHUNK_ENTRY
);
519 if (zap_getflags(zap
) & ZAP_FLAG_UINT64_KEY
) {
520 zap_leaf_array_read(zeh
->zeh_leaf
, le
->le_name_chunk
, 8,
521 le
->le_name_numints
, 8, buflen
/ 8, buf
);
523 zap_leaf_array_read(zeh
->zeh_leaf
, le
->le_name_chunk
, 1,
524 le
->le_name_numints
, 1, buflen
, buf
);
526 if (le
->le_name_numints
> buflen
)
527 return (SET_ERROR(EOVERFLOW
));
532 zap_entry_update(zap_entry_handle_t
*zeh
,
533 uint8_t integer_size
, uint64_t num_integers
, const void *buf
)
536 zap_leaf_t
*l
= zeh
->zeh_leaf
;
537 struct zap_leaf_entry
*le
= ZAP_LEAF_ENTRY(l
, *zeh
->zeh_chunkp
);
539 delta_chunks
= ZAP_LEAF_ARRAY_NCHUNKS(num_integers
* integer_size
) -
540 ZAP_LEAF_ARRAY_NCHUNKS(le
->le_value_numints
* le
->le_value_intlen
);
542 if ((int)zap_leaf_phys(l
)->l_hdr
.lh_nfree
< delta_chunks
)
543 return (SET_ERROR(EAGAIN
));
545 zap_leaf_array_free(l
, &le
->le_value_chunk
);
547 zap_leaf_array_create(l
, buf
, integer_size
, num_integers
);
548 le
->le_value_numints
= num_integers
;
549 le
->le_value_intlen
= integer_size
;
554 zap_entry_remove(zap_entry_handle_t
*zeh
)
556 uint16_t entry_chunk
;
557 struct zap_leaf_entry
*le
;
558 zap_leaf_t
*l
= zeh
->zeh_leaf
;
560 ASSERT3P(zeh
->zeh_chunkp
, !=, &zeh
->zeh_fakechunk
);
562 entry_chunk
= *zeh
->zeh_chunkp
;
563 le
= ZAP_LEAF_ENTRY(l
, entry_chunk
);
564 ASSERT3U(le
->le_type
, ==, ZAP_CHUNK_ENTRY
);
566 zap_leaf_array_free(l
, &le
->le_name_chunk
);
567 zap_leaf_array_free(l
, &le
->le_value_chunk
);
569 *zeh
->zeh_chunkp
= le
->le_next
;
570 zap_leaf_chunk_free(l
, entry_chunk
);
572 zap_leaf_phys(l
)->l_hdr
.lh_nentries
--;
576 zap_entry_create(zap_leaf_t
*l
, zap_name_t
*zn
, uint32_t cd
,
577 uint8_t integer_size
, uint64_t num_integers
, const void *buf
,
578 zap_entry_handle_t
*zeh
)
582 struct zap_leaf_entry
*le
;
585 uint64_t h
= zn
->zn_hash
;
587 valuelen
= integer_size
* num_integers
;
589 numchunks
= 1 + ZAP_LEAF_ARRAY_NCHUNKS(zn
->zn_key_orig_numints
*
590 zn
->zn_key_intlen
) + ZAP_LEAF_ARRAY_NCHUNKS(valuelen
);
591 if (numchunks
> ZAP_LEAF_NUMCHUNKS(l
))
594 if (cd
== ZAP_NEED_CD
) {
595 /* find the lowest unused cd */
596 if (zap_leaf_phys(l
)->l_hdr
.lh_flags
& ZLF_ENTRIES_CDSORTED
) {
599 for (chunk
= *LEAF_HASH_ENTPTR(l
, h
);
600 chunk
!= CHAIN_END
; chunk
= le
->le_next
) {
601 le
= ZAP_LEAF_ENTRY(l
, chunk
);
604 if (le
->le_hash
== h
) {
605 ASSERT3U(cd
, ==, le
->le_cd
);
610 /* old unsorted format; do it the O(n^2) way */
611 for (cd
= 0; ; cd
++) {
612 for (chunk
= *LEAF_HASH_ENTPTR(l
, h
);
613 chunk
!= CHAIN_END
; chunk
= le
->le_next
) {
614 le
= ZAP_LEAF_ENTRY(l
, chunk
);
615 if (le
->le_hash
== h
&&
620 /* If this cd is not in use, we are good. */
621 if (chunk
== CHAIN_END
)
626 * We would run out of space in a block before we could
627 * store enough entries to run out of CD values.
629 ASSERT3U(cd
, <, zap_maxcd(zn
->zn_zap
));
632 if (zap_leaf_phys(l
)->l_hdr
.lh_nfree
< numchunks
)
633 return (SET_ERROR(EAGAIN
));
636 chunk
= zap_leaf_chunk_alloc(l
);
637 le
= ZAP_LEAF_ENTRY(l
, chunk
);
638 le
->le_type
= ZAP_CHUNK_ENTRY
;
639 le
->le_name_chunk
= zap_leaf_array_create(l
, zn
->zn_key_orig
,
640 zn
->zn_key_intlen
, zn
->zn_key_orig_numints
);
641 le
->le_name_numints
= zn
->zn_key_orig_numints
;
643 zap_leaf_array_create(l
, buf
, integer_size
, num_integers
);
644 le
->le_value_numints
= num_integers
;
645 le
->le_value_intlen
= integer_size
;
649 /* link it into the hash chain */
650 /* XXX if we did the search above, we could just use that */
651 chunkp
= zap_leaf_rehash_entry(l
, chunk
);
653 zap_leaf_phys(l
)->l_hdr
.lh_nentries
++;
656 zeh
->zeh_num_integers
= num_integers
;
657 zeh
->zeh_integer_size
= le
->le_value_intlen
;
658 zeh
->zeh_cd
= le
->le_cd
;
659 zeh
->zeh_hash
= le
->le_hash
;
660 zeh
->zeh_chunkp
= chunkp
;
666 * Determine if there is another entry with the same normalized form.
667 * For performance purposes, either zn or name must be provided (the
668 * other can be NULL). Note, there usually won't be any hash
669 * conflicts, in which case we don't need the concatenated/normalized
670 * form of the name. But all callers have one of these on hand anyway,
671 * so might as well take advantage. A cleaner but slower interface
672 * would accept neither argument, and compute the normalized name as
673 * needed (using zap_name_alloc(zap_entry_read_name(zeh))).
676 zap_entry_normalization_conflict(zap_entry_handle_t
*zeh
, zap_name_t
*zn
,
677 const char *name
, zap_t
*zap
)
680 struct zap_leaf_entry
*le
;
681 boolean_t allocdzn
= B_FALSE
;
683 if (zap
->zap_normflags
== 0)
686 for (chunk
= *LEAF_HASH_ENTPTR(zeh
->zeh_leaf
, zeh
->zeh_hash
);
687 chunk
!= CHAIN_END
; chunk
= le
->le_next
) {
688 le
= ZAP_LEAF_ENTRY(zeh
->zeh_leaf
, chunk
);
689 if (le
->le_hash
!= zeh
->zeh_hash
)
691 if (le
->le_cd
== zeh
->zeh_cd
)
695 zn
= zap_name_alloc(zap
, name
, MT_NORMALIZE
);
698 if (zap_leaf_array_match(zeh
->zeh_leaf
, zn
,
699 le
->le_name_chunk
, le
->le_name_numints
)) {
711 * Routines for transferring entries between leafs.
715 zap_leaf_rehash_entry(zap_leaf_t
*l
, uint16_t entry
)
717 struct zap_leaf_entry
*le
= ZAP_LEAF_ENTRY(l
, entry
);
718 struct zap_leaf_entry
*le2
;
722 * keep the entry chain sorted by cd
723 * NB: this will not cause problems for unsorted leafs, though
724 * it is unnecessary there.
726 for (chunkp
= LEAF_HASH_ENTPTR(l
, le
->le_hash
);
727 *chunkp
!= CHAIN_END
; chunkp
= &le2
->le_next
) {
728 le2
= ZAP_LEAF_ENTRY(l
, *chunkp
);
729 if (le2
->le_cd
> le
->le_cd
)
733 le
->le_next
= *chunkp
;
739 zap_leaf_transfer_array(zap_leaf_t
*l
, uint16_t chunk
, zap_leaf_t
*nl
)
742 uint16_t *nchunkp
= &new_chunk
;
744 while (chunk
!= CHAIN_END
) {
745 uint16_t nchunk
= zap_leaf_chunk_alloc(nl
);
746 struct zap_leaf_array
*nla
=
747 &ZAP_LEAF_CHUNK(nl
, nchunk
).l_array
;
748 struct zap_leaf_array
*la
=
749 &ZAP_LEAF_CHUNK(l
, chunk
).l_array
;
750 int nextchunk
= la
->la_next
;
752 ASSERT3U(chunk
, <, ZAP_LEAF_NUMCHUNKS(l
));
753 ASSERT3U(nchunk
, <, ZAP_LEAF_NUMCHUNKS(l
));
755 *nla
= *la
; /* structure assignment */
757 zap_leaf_chunk_free(l
, chunk
);
760 nchunkp
= &nla
->la_next
;
762 *nchunkp
= CHAIN_END
;
767 zap_leaf_transfer_entry(zap_leaf_t
*l
, int entry
, zap_leaf_t
*nl
)
769 struct zap_leaf_entry
*le
, *nle
;
772 le
= ZAP_LEAF_ENTRY(l
, entry
);
773 ASSERT3U(le
->le_type
, ==, ZAP_CHUNK_ENTRY
);
775 chunk
= zap_leaf_chunk_alloc(nl
);
776 nle
= ZAP_LEAF_ENTRY(nl
, chunk
);
777 *nle
= *le
; /* structure assignment */
779 (void) zap_leaf_rehash_entry(nl
, chunk
);
781 nle
->le_name_chunk
= zap_leaf_transfer_array(l
, le
->le_name_chunk
, nl
);
782 nle
->le_value_chunk
=
783 zap_leaf_transfer_array(l
, le
->le_value_chunk
, nl
);
785 zap_leaf_chunk_free(l
, entry
);
787 zap_leaf_phys(l
)->l_hdr
.lh_nentries
--;
788 zap_leaf_phys(nl
)->l_hdr
.lh_nentries
++;
792 * Transfer the entries whose hash prefix ends in 1 to the new leaf.
795 zap_leaf_split(zap_leaf_t
*l
, zap_leaf_t
*nl
, boolean_t sort
)
798 int bit
= 64 - 1 - zap_leaf_phys(l
)->l_hdr
.lh_prefix_len
;
800 /* set new prefix and prefix_len */
801 zap_leaf_phys(l
)->l_hdr
.lh_prefix
<<= 1;
802 zap_leaf_phys(l
)->l_hdr
.lh_prefix_len
++;
803 zap_leaf_phys(nl
)->l_hdr
.lh_prefix
=
804 zap_leaf_phys(l
)->l_hdr
.lh_prefix
| 1;
805 zap_leaf_phys(nl
)->l_hdr
.lh_prefix_len
=
806 zap_leaf_phys(l
)->l_hdr
.lh_prefix_len
;
808 /* break existing hash chains */
809 zap_memset(zap_leaf_phys(l
)->l_hash
, CHAIN_END
,
810 2*ZAP_LEAF_HASH_NUMENTRIES(l
));
813 zap_leaf_phys(l
)->l_hdr
.lh_flags
|= ZLF_ENTRIES_CDSORTED
;
816 * Transfer entries whose hash bit 'bit' is set to nl; rehash
817 * the remaining entries
819 * NB: We could find entries via the hashtable instead. That
820 * would be O(hashents+numents) rather than O(numblks+numents),
821 * but this accesses memory more sequentially, and when we're
822 * called, the block is usually pretty full.
824 for (i
= 0; i
< ZAP_LEAF_NUMCHUNKS(l
); i
++) {
825 struct zap_leaf_entry
*le
= ZAP_LEAF_ENTRY(l
, i
);
826 if (le
->le_type
!= ZAP_CHUNK_ENTRY
)
829 if (le
->le_hash
& (1ULL << bit
))
830 zap_leaf_transfer_entry(l
, i
, nl
);
832 (void) zap_leaf_rehash_entry(l
, i
);
837 zap_leaf_stats(zap_t
*zap
, zap_leaf_t
*l
, zap_stats_t
*zs
)
841 n
= zap_f_phys(zap
)->zap_ptrtbl
.zt_shift
-
842 zap_leaf_phys(l
)->l_hdr
.lh_prefix_len
;
843 n
= MIN(n
, ZAP_HISTOGRAM_SIZE
-1);
844 zs
->zs_leafs_with_2n_pointers
[n
]++;
847 n
= zap_leaf_phys(l
)->l_hdr
.lh_nentries
/5;
848 n
= MIN(n
, ZAP_HISTOGRAM_SIZE
-1);
849 zs
->zs_blocks_with_n5_entries
[n
]++;
851 n
= ((1<<FZAP_BLOCK_SHIFT(zap
)) -
852 zap_leaf_phys(l
)->l_hdr
.lh_nfree
* (ZAP_LEAF_ARRAY_BYTES
+1))*10 /
853 (1<<FZAP_BLOCK_SHIFT(zap
));
854 n
= MIN(n
, ZAP_HISTOGRAM_SIZE
-1);
855 zs
->zs_blocks_n_tenths_full
[n
]++;
857 for (i
= 0; i
< ZAP_LEAF_HASH_NUMENTRIES(l
); i
++) {
859 int chunk
= zap_leaf_phys(l
)->l_hash
[i
];
861 while (chunk
!= CHAIN_END
) {
862 struct zap_leaf_entry
*le
=
863 ZAP_LEAF_ENTRY(l
, chunk
);
865 n
= 1 + ZAP_LEAF_ARRAY_NCHUNKS(le
->le_name_numints
) +
866 ZAP_LEAF_ARRAY_NCHUNKS(le
->le_value_numints
*
867 le
->le_value_intlen
);
868 n
= MIN(n
, ZAP_HISTOGRAM_SIZE
-1);
869 zs
->zs_entries_using_n_chunks
[n
]++;
876 n
= MIN(n
, ZAP_HISTOGRAM_SIZE
-1);
877 zs
->zs_buckets_with_n_entries
[n
]++;