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, 2016 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
)
115 l_dbuf
.db_data
= buf
;
116 l
.l_bs
= highbit64(size
) - 1;
119 buf
->l_hdr
.lh_block_type
= BSWAP_64(buf
->l_hdr
.lh_block_type
);
120 buf
->l_hdr
.lh_prefix
= BSWAP_64(buf
->l_hdr
.lh_prefix
);
121 buf
->l_hdr
.lh_magic
= BSWAP_32(buf
->l_hdr
.lh_magic
);
122 buf
->l_hdr
.lh_nfree
= BSWAP_16(buf
->l_hdr
.lh_nfree
);
123 buf
->l_hdr
.lh_nentries
= BSWAP_16(buf
->l_hdr
.lh_nentries
);
124 buf
->l_hdr
.lh_prefix_len
= BSWAP_16(buf
->l_hdr
.lh_prefix_len
);
125 buf
->l_hdr
.lh_freelist
= BSWAP_16(buf
->l_hdr
.lh_freelist
);
127 for (int i
= 0; i
< ZAP_LEAF_HASH_NUMENTRIES(&l
); i
++)
128 buf
->l_hash
[i
] = BSWAP_16(buf
->l_hash
[i
]);
130 for (int i
= 0; i
< ZAP_LEAF_NUMCHUNKS(&l
); i
++) {
131 zap_leaf_chunk_t
*lc
= &ZAP_LEAF_CHUNK(&l
, i
);
132 struct zap_leaf_entry
*le
;
134 switch (lc
->l_free
.lf_type
) {
135 case ZAP_CHUNK_ENTRY
:
138 le
->le_type
= BSWAP_8(le
->le_type
);
139 le
->le_value_intlen
= BSWAP_8(le
->le_value_intlen
);
140 le
->le_next
= BSWAP_16(le
->le_next
);
141 le
->le_name_chunk
= BSWAP_16(le
->le_name_chunk
);
142 le
->le_name_numints
= BSWAP_16(le
->le_name_numints
);
143 le
->le_value_chunk
= BSWAP_16(le
->le_value_chunk
);
144 le
->le_value_numints
= BSWAP_16(le
->le_value_numints
);
145 le
->le_cd
= BSWAP_32(le
->le_cd
);
146 le
->le_hash
= BSWAP_64(le
->le_hash
);
149 lc
->l_free
.lf_type
= BSWAP_8(lc
->l_free
.lf_type
);
150 lc
->l_free
.lf_next
= BSWAP_16(lc
->l_free
.lf_next
);
152 case ZAP_CHUNK_ARRAY
:
153 lc
->l_array
.la_type
= BSWAP_8(lc
->l_array
.la_type
);
154 lc
->l_array
.la_next
= BSWAP_16(lc
->l_array
.la_next
);
155 /* la_array doesn't need swapping */
158 cmn_err(CE_PANIC
, "bad leaf type %d",
165 zap_leaf_init(zap_leaf_t
*l
, boolean_t sort
)
167 l
->l_bs
= highbit64(l
->l_dbuf
->db_size
) - 1;
168 zap_memset(&zap_leaf_phys(l
)->l_hdr
, 0,
169 sizeof (struct zap_leaf_header
));
170 zap_memset(zap_leaf_phys(l
)->l_hash
, CHAIN_END
,
171 2*ZAP_LEAF_HASH_NUMENTRIES(l
));
172 for (int i
= 0; i
< ZAP_LEAF_NUMCHUNKS(l
); i
++) {
173 ZAP_LEAF_CHUNK(l
, i
).l_free
.lf_type
= ZAP_CHUNK_FREE
;
174 ZAP_LEAF_CHUNK(l
, i
).l_free
.lf_next
= i
+1;
176 ZAP_LEAF_CHUNK(l
, ZAP_LEAF_NUMCHUNKS(l
)-1).l_free
.lf_next
= CHAIN_END
;
177 zap_leaf_phys(l
)->l_hdr
.lh_block_type
= ZBT_LEAF
;
178 zap_leaf_phys(l
)->l_hdr
.lh_magic
= ZAP_LEAF_MAGIC
;
179 zap_leaf_phys(l
)->l_hdr
.lh_nfree
= ZAP_LEAF_NUMCHUNKS(l
);
181 zap_leaf_phys(l
)->l_hdr
.lh_flags
|= ZLF_ENTRIES_CDSORTED
;
185 * Routines which manipulate leaf chunks (l_chunk[]).
189 zap_leaf_chunk_alloc(zap_leaf_t
*l
)
191 ASSERT(zap_leaf_phys(l
)->l_hdr
.lh_nfree
> 0);
193 int chunk
= zap_leaf_phys(l
)->l_hdr
.lh_freelist
;
194 ASSERT3U(chunk
, <, ZAP_LEAF_NUMCHUNKS(l
));
195 ASSERT3U(ZAP_LEAF_CHUNK(l
, chunk
).l_free
.lf_type
, ==, ZAP_CHUNK_FREE
);
197 zap_leaf_phys(l
)->l_hdr
.lh_freelist
=
198 ZAP_LEAF_CHUNK(l
, chunk
).l_free
.lf_next
;
200 zap_leaf_phys(l
)->l_hdr
.lh_nfree
--;
206 zap_leaf_chunk_free(zap_leaf_t
*l
, uint16_t chunk
)
208 struct zap_leaf_free
*zlf
= &ZAP_LEAF_CHUNK(l
, chunk
).l_free
;
209 ASSERT3U(zap_leaf_phys(l
)->l_hdr
.lh_nfree
, <, ZAP_LEAF_NUMCHUNKS(l
));
210 ASSERT3U(chunk
, <, ZAP_LEAF_NUMCHUNKS(l
));
211 ASSERT(zlf
->lf_type
!= ZAP_CHUNK_FREE
);
213 zlf
->lf_type
= ZAP_CHUNK_FREE
;
214 zlf
->lf_next
= zap_leaf_phys(l
)->l_hdr
.lh_freelist
;
215 bzero(zlf
->lf_pad
, sizeof (zlf
->lf_pad
)); /* help it to compress */
216 zap_leaf_phys(l
)->l_hdr
.lh_freelist
= chunk
;
218 zap_leaf_phys(l
)->l_hdr
.lh_nfree
++;
222 * Routines which manipulate leaf arrays (zap_leaf_array type chunks).
226 zap_leaf_array_create(zap_leaf_t
*l
, const char *buf
,
227 int integer_size
, int num_integers
)
230 uint16_t *chunkp
= &chunk_head
;
233 int shift
= (integer_size
- 1) * 8;
234 int len
= num_integers
;
236 ASSERT3U(num_integers
* integer_size
, <, MAX_ARRAY_BYTES
);
239 uint16_t chunk
= zap_leaf_chunk_alloc(l
);
240 struct zap_leaf_array
*la
= &ZAP_LEAF_CHUNK(l
, chunk
).l_array
;
242 la
->la_type
= ZAP_CHUNK_ARRAY
;
243 for (int i
= 0; i
< ZAP_LEAF_ARRAY_BYTES
; i
++) {
245 value
= ldv(integer_size
, buf
);
246 la
->la_array
[i
] = value
>> shift
;
248 if (++byten
== integer_size
) {
257 chunkp
= &la
->la_next
;
265 zap_leaf_array_free(zap_leaf_t
*l
, uint16_t *chunkp
)
267 uint16_t chunk
= *chunkp
;
271 while (chunk
!= CHAIN_END
) {
272 int nextchunk
= ZAP_LEAF_CHUNK(l
, chunk
).l_array
.la_next
;
273 ASSERT3U(ZAP_LEAF_CHUNK(l
, chunk
).l_array
.la_type
, ==,
275 zap_leaf_chunk_free(l
, chunk
);
280 /* array_len and buf_len are in integers, not bytes */
282 zap_leaf_array_read(zap_leaf_t
*l
, uint16_t chunk
,
283 int array_int_len
, int array_len
, int buf_int_len
, uint64_t buf_len
,
286 int len
= MIN(array_len
, buf_len
);
291 ASSERT3U(array_int_len
, <=, buf_int_len
);
293 /* Fast path for one 8-byte integer */
294 if (array_int_len
== 8 && buf_int_len
== 8 && len
== 1) {
295 struct zap_leaf_array
*la
= &ZAP_LEAF_CHUNK(l
, chunk
).l_array
;
296 uint8_t *ip
= la
->la_array
;
297 uint64_t *buf64
= buf
;
299 *buf64
= (uint64_t)ip
[0] << 56 | (uint64_t)ip
[1] << 48 |
300 (uint64_t)ip
[2] << 40 | (uint64_t)ip
[3] << 32 |
301 (uint64_t)ip
[4] << 24 | (uint64_t)ip
[5] << 16 |
302 (uint64_t)ip
[6] << 8 | (uint64_t)ip
[7];
306 /* Fast path for an array of 1-byte integers (eg. the entry name) */
307 if (array_int_len
== 1 && buf_int_len
== 1 &&
308 buf_len
> array_len
+ ZAP_LEAF_ARRAY_BYTES
) {
309 while (chunk
!= CHAIN_END
) {
310 struct zap_leaf_array
*la
=
311 &ZAP_LEAF_CHUNK(l
, chunk
).l_array
;
312 bcopy(la
->la_array
, p
, ZAP_LEAF_ARRAY_BYTES
);
313 p
+= ZAP_LEAF_ARRAY_BYTES
;
320 struct zap_leaf_array
*la
= &ZAP_LEAF_CHUNK(l
, chunk
).l_array
;
322 ASSERT3U(chunk
, <, ZAP_LEAF_NUMCHUNKS(l
));
323 for (int i
= 0; i
< ZAP_LEAF_ARRAY_BYTES
&& len
> 0; i
++) {
324 value
= (value
<< 8) | la
->la_array
[i
];
326 if (byten
== array_int_len
) {
327 stv(buf_int_len
, p
, value
);
340 zap_leaf_array_match(zap_leaf_t
*l
, zap_name_t
*zn
,
341 int chunk
, int array_numints
)
345 if (zap_getflags(zn
->zn_zap
) & ZAP_FLAG_UINT64_KEY
) {
347 kmem_alloc(array_numints
* sizeof (*thiskey
), KM_SLEEP
);
348 ASSERT(zn
->zn_key_intlen
== sizeof (*thiskey
));
350 zap_leaf_array_read(l
, chunk
, sizeof (*thiskey
), array_numints
,
351 sizeof (*thiskey
), array_numints
, thiskey
);
352 boolean_t match
= bcmp(thiskey
, zn
->zn_key_orig
,
353 array_numints
* sizeof (*thiskey
)) == 0;
354 kmem_free(thiskey
, array_numints
* sizeof (*thiskey
));
358 ASSERT(zn
->zn_key_intlen
== 1);
359 if (zn
->zn_matchtype
& MT_NORMALIZE
) {
360 char *thisname
= kmem_alloc(array_numints
, KM_SLEEP
);
362 zap_leaf_array_read(l
, chunk
, sizeof (char), array_numints
,
363 sizeof (char), array_numints
, thisname
);
364 boolean_t match
= zap_match(zn
, thisname
);
365 kmem_free(thisname
, array_numints
);
370 * Fast path for exact matching.
371 * First check that the lengths match, so that we don't read
372 * past the end of the zn_key_orig array.
374 if (array_numints
!= zn
->zn_key_orig_numints
)
376 while (bseen
< array_numints
) {
377 struct zap_leaf_array
*la
= &ZAP_LEAF_CHUNK(l
, chunk
).l_array
;
378 int toread
= MIN(array_numints
- bseen
, ZAP_LEAF_ARRAY_BYTES
);
379 ASSERT3U(chunk
, <, ZAP_LEAF_NUMCHUNKS(l
));
380 if (bcmp(la
->la_array
, (char *)zn
->zn_key_orig
+ bseen
, toread
))
385 return (bseen
== array_numints
);
389 * Routines which manipulate leaf entries.
393 zap_leaf_lookup(zap_leaf_t
*l
, zap_name_t
*zn
, zap_entry_handle_t
*zeh
)
395 struct zap_leaf_entry
*le
;
397 ASSERT3U(zap_leaf_phys(l
)->l_hdr
.lh_magic
, ==, ZAP_LEAF_MAGIC
);
399 for (uint16_t *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
);
404 ASSERT3U(chunk
, <, ZAP_LEAF_NUMCHUNKS(l
));
405 ASSERT3U(le
->le_type
, ==, ZAP_CHUNK_ENTRY
);
407 if (le
->le_hash
!= zn
->zn_hash
)
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_NORMALIZE.
415 ASSERT((zn
->zn_matchtype
== 0) ||
416 (zap_leaf_phys(l
)->l_hdr
.lh_flags
& ZLF_ENTRIES_CDSORTED
));
417 if (zap_leaf_array_match(l
, zn
, le
->le_name_chunk
,
418 le
->le_name_numints
)) {
419 zeh
->zeh_num_integers
= le
->le_value_numints
;
420 zeh
->zeh_integer_size
= le
->le_value_intlen
;
421 zeh
->zeh_cd
= le
->le_cd
;
422 zeh
->zeh_hash
= le
->le_hash
;
423 zeh
->zeh_chunkp
= chunkp
;
429 return (SET_ERROR(ENOENT
));
432 /* Return (h1,cd1 >= h2,cd2) */
433 #define HCD_GTEQ(h1, cd1, h2, cd2) \
434 ((h1 > h2) ? TRUE : ((h1 == h2 && cd1 >= cd2) ? TRUE : FALSE))
437 zap_leaf_lookup_closest(zap_leaf_t
*l
,
438 uint64_t h
, uint32_t cd
, zap_entry_handle_t
*zeh
)
440 uint64_t besth
= -1ULL;
441 uint32_t bestcd
= -1U;
442 uint16_t bestlh
= ZAP_LEAF_HASH_NUMENTRIES(l
)-1;
443 struct zap_leaf_entry
*le
;
445 ASSERT3U(zap_leaf_phys(l
)->l_hdr
.lh_magic
, ==, ZAP_LEAF_MAGIC
);
447 for (uint16_t lh
= LEAF_HASH(l
, h
); lh
<= bestlh
; lh
++) {
448 for (uint16_t chunk
= zap_leaf_phys(l
)->l_hash
[lh
];
449 chunk
!= CHAIN_END
; chunk
= le
->le_next
) {
450 le
= ZAP_LEAF_ENTRY(l
, chunk
);
452 ASSERT3U(chunk
, <, ZAP_LEAF_NUMCHUNKS(l
));
453 ASSERT3U(le
->le_type
, ==, ZAP_CHUNK_ENTRY
);
455 if (HCD_GTEQ(le
->le_hash
, le
->le_cd
, h
, cd
) &&
456 HCD_GTEQ(besth
, bestcd
, le
->le_hash
, le
->le_cd
)) {
457 ASSERT3U(bestlh
, >=, lh
);
462 zeh
->zeh_num_integers
= le
->le_value_numints
;
463 zeh
->zeh_integer_size
= le
->le_value_intlen
;
464 zeh
->zeh_cd
= le
->le_cd
;
465 zeh
->zeh_hash
= le
->le_hash
;
466 zeh
->zeh_fakechunk
= chunk
;
467 zeh
->zeh_chunkp
= &zeh
->zeh_fakechunk
;
473 return (bestcd
== -1U ? ENOENT
: 0);
477 zap_entry_read(const zap_entry_handle_t
*zeh
,
478 uint8_t integer_size
, uint64_t num_integers
, void *buf
)
480 struct zap_leaf_entry
*le
=
481 ZAP_LEAF_ENTRY(zeh
->zeh_leaf
, *zeh
->zeh_chunkp
);
482 ASSERT3U(le
->le_type
, ==, ZAP_CHUNK_ENTRY
);
484 if (le
->le_value_intlen
> integer_size
)
485 return (SET_ERROR(EINVAL
));
487 zap_leaf_array_read(zeh
->zeh_leaf
, le
->le_value_chunk
,
488 le
->le_value_intlen
, le
->le_value_numints
,
489 integer_size
, num_integers
, buf
);
491 if (zeh
->zeh_num_integers
> num_integers
)
492 return (SET_ERROR(EOVERFLOW
));
498 zap_entry_read_name(zap_t
*zap
, const zap_entry_handle_t
*zeh
, uint16_t buflen
,
501 struct zap_leaf_entry
*le
=
502 ZAP_LEAF_ENTRY(zeh
->zeh_leaf
, *zeh
->zeh_chunkp
);
503 ASSERT3U(le
->le_type
, ==, ZAP_CHUNK_ENTRY
);
505 if (zap_getflags(zap
) & ZAP_FLAG_UINT64_KEY
) {
506 zap_leaf_array_read(zeh
->zeh_leaf
, le
->le_name_chunk
, 8,
507 le
->le_name_numints
, 8, buflen
/ 8, buf
);
509 zap_leaf_array_read(zeh
->zeh_leaf
, le
->le_name_chunk
, 1,
510 le
->le_name_numints
, 1, buflen
, buf
);
512 if (le
->le_name_numints
> buflen
)
513 return (SET_ERROR(EOVERFLOW
));
518 zap_entry_update(zap_entry_handle_t
*zeh
,
519 uint8_t integer_size
, uint64_t num_integers
, const void *buf
)
521 zap_leaf_t
*l
= zeh
->zeh_leaf
;
522 struct zap_leaf_entry
*le
= ZAP_LEAF_ENTRY(l
, *zeh
->zeh_chunkp
);
524 int delta_chunks
= ZAP_LEAF_ARRAY_NCHUNKS(num_integers
* integer_size
) -
525 ZAP_LEAF_ARRAY_NCHUNKS(le
->le_value_numints
* le
->le_value_intlen
);
527 if ((int)zap_leaf_phys(l
)->l_hdr
.lh_nfree
< delta_chunks
)
528 return (SET_ERROR(EAGAIN
));
530 zap_leaf_array_free(l
, &le
->le_value_chunk
);
532 zap_leaf_array_create(l
, buf
, integer_size
, num_integers
);
533 le
->le_value_numints
= num_integers
;
534 le
->le_value_intlen
= integer_size
;
539 zap_entry_remove(zap_entry_handle_t
*zeh
)
541 zap_leaf_t
*l
= zeh
->zeh_leaf
;
543 ASSERT3P(zeh
->zeh_chunkp
, !=, &zeh
->zeh_fakechunk
);
545 uint16_t entry_chunk
= *zeh
->zeh_chunkp
;
546 struct zap_leaf_entry
*le
= ZAP_LEAF_ENTRY(l
, entry_chunk
);
547 ASSERT3U(le
->le_type
, ==, ZAP_CHUNK_ENTRY
);
549 zap_leaf_array_free(l
, &le
->le_name_chunk
);
550 zap_leaf_array_free(l
, &le
->le_value_chunk
);
552 *zeh
->zeh_chunkp
= le
->le_next
;
553 zap_leaf_chunk_free(l
, entry_chunk
);
555 zap_leaf_phys(l
)->l_hdr
.lh_nentries
--;
559 zap_entry_create(zap_leaf_t
*l
, zap_name_t
*zn
, uint32_t cd
,
560 uint8_t integer_size
, uint64_t num_integers
, const void *buf
,
561 zap_entry_handle_t
*zeh
)
564 struct zap_leaf_entry
*le
;
565 uint64_t h
= zn
->zn_hash
;
567 uint64_t valuelen
= integer_size
* num_integers
;
569 int numchunks
= 1 + ZAP_LEAF_ARRAY_NCHUNKS(zn
->zn_key_orig_numints
*
570 zn
->zn_key_intlen
) + ZAP_LEAF_ARRAY_NCHUNKS(valuelen
);
571 if (numchunks
> ZAP_LEAF_NUMCHUNKS(l
))
572 return (SET_ERROR(E2BIG
));
574 if (cd
== ZAP_NEED_CD
) {
575 /* find the lowest unused cd */
576 if (zap_leaf_phys(l
)->l_hdr
.lh_flags
& ZLF_ENTRIES_CDSORTED
) {
579 for (chunk
= *LEAF_HASH_ENTPTR(l
, h
);
580 chunk
!= CHAIN_END
; chunk
= le
->le_next
) {
581 le
= ZAP_LEAF_ENTRY(l
, chunk
);
584 if (le
->le_hash
== h
) {
585 ASSERT3U(cd
, ==, le
->le_cd
);
590 /* old unsorted format; do it the O(n^2) way */
591 for (cd
= 0; ; cd
++) {
592 for (chunk
= *LEAF_HASH_ENTPTR(l
, h
);
593 chunk
!= CHAIN_END
; chunk
= le
->le_next
) {
594 le
= ZAP_LEAF_ENTRY(l
, chunk
);
595 if (le
->le_hash
== h
&&
600 /* If this cd is not in use, we are good. */
601 if (chunk
== CHAIN_END
)
606 * We would run out of space in a block before we could
607 * store enough entries to run out of CD values.
609 ASSERT3U(cd
, <, zap_maxcd(zn
->zn_zap
));
612 if (zap_leaf_phys(l
)->l_hdr
.lh_nfree
< numchunks
)
613 return (SET_ERROR(EAGAIN
));
616 chunk
= zap_leaf_chunk_alloc(l
);
617 le
= ZAP_LEAF_ENTRY(l
, chunk
);
618 le
->le_type
= ZAP_CHUNK_ENTRY
;
619 le
->le_name_chunk
= zap_leaf_array_create(l
, zn
->zn_key_orig
,
620 zn
->zn_key_intlen
, zn
->zn_key_orig_numints
);
621 le
->le_name_numints
= zn
->zn_key_orig_numints
;
623 zap_leaf_array_create(l
, buf
, integer_size
, num_integers
);
624 le
->le_value_numints
= num_integers
;
625 le
->le_value_intlen
= integer_size
;
629 /* link it into the hash chain */
630 /* XXX if we did the search above, we could just use that */
631 uint16_t *chunkp
= zap_leaf_rehash_entry(l
, chunk
);
633 zap_leaf_phys(l
)->l_hdr
.lh_nentries
++;
636 zeh
->zeh_num_integers
= num_integers
;
637 zeh
->zeh_integer_size
= le
->le_value_intlen
;
638 zeh
->zeh_cd
= le
->le_cd
;
639 zeh
->zeh_hash
= le
->le_hash
;
640 zeh
->zeh_chunkp
= chunkp
;
646 * Determine if there is another entry with the same normalized form.
647 * For performance purposes, either zn or name must be provided (the
648 * other can be NULL). Note, there usually won't be any hash
649 * conflicts, in which case we don't need the concatenated/normalized
650 * form of the name. But all callers have one of these on hand anyway,
651 * so might as well take advantage. A cleaner but slower interface
652 * would accept neither argument, and compute the normalized name as
653 * needed (using zap_name_alloc(zap_entry_read_name(zeh))).
656 zap_entry_normalization_conflict(zap_entry_handle_t
*zeh
, zap_name_t
*zn
,
657 const char *name
, zap_t
*zap
)
659 struct zap_leaf_entry
*le
;
660 boolean_t allocdzn
= B_FALSE
;
662 if (zap
->zap_normflags
== 0)
665 for (uint16_t chunk
= *LEAF_HASH_ENTPTR(zeh
->zeh_leaf
, zeh
->zeh_hash
);
666 chunk
!= CHAIN_END
; chunk
= le
->le_next
) {
667 le
= ZAP_LEAF_ENTRY(zeh
->zeh_leaf
, chunk
);
668 if (le
->le_hash
!= zeh
->zeh_hash
)
670 if (le
->le_cd
== zeh
->zeh_cd
)
674 zn
= zap_name_alloc(zap
, name
, MT_NORMALIZE
);
677 if (zap_leaf_array_match(zeh
->zeh_leaf
, zn
,
678 le
->le_name_chunk
, le
->le_name_numints
)) {
690 * Routines for transferring entries between leafs.
694 zap_leaf_rehash_entry(zap_leaf_t
*l
, uint16_t entry
)
696 struct zap_leaf_entry
*le
= ZAP_LEAF_ENTRY(l
, entry
);
697 struct zap_leaf_entry
*le2
;
701 * keep the entry chain sorted by cd
702 * NB: this will not cause problems for unsorted leafs, though
703 * it is unnecessary there.
705 for (chunkp
= LEAF_HASH_ENTPTR(l
, le
->le_hash
);
706 *chunkp
!= CHAIN_END
; chunkp
= &le2
->le_next
) {
707 le2
= ZAP_LEAF_ENTRY(l
, *chunkp
);
708 if (le2
->le_cd
> le
->le_cd
)
712 le
->le_next
= *chunkp
;
718 zap_leaf_transfer_array(zap_leaf_t
*l
, uint16_t chunk
, zap_leaf_t
*nl
)
721 uint16_t *nchunkp
= &new_chunk
;
723 while (chunk
!= CHAIN_END
) {
724 uint16_t nchunk
= zap_leaf_chunk_alloc(nl
);
725 struct zap_leaf_array
*nla
=
726 &ZAP_LEAF_CHUNK(nl
, nchunk
).l_array
;
727 struct zap_leaf_array
*la
=
728 &ZAP_LEAF_CHUNK(l
, chunk
).l_array
;
729 int nextchunk
= la
->la_next
;
731 ASSERT3U(chunk
, <, ZAP_LEAF_NUMCHUNKS(l
));
732 ASSERT3U(nchunk
, <, ZAP_LEAF_NUMCHUNKS(l
));
734 *nla
= *la
; /* structure assignment */
736 zap_leaf_chunk_free(l
, chunk
);
739 nchunkp
= &nla
->la_next
;
741 *nchunkp
= CHAIN_END
;
746 zap_leaf_transfer_entry(zap_leaf_t
*l
, int entry
, zap_leaf_t
*nl
)
748 struct zap_leaf_entry
*le
= ZAP_LEAF_ENTRY(l
, entry
);
749 ASSERT3U(le
->le_type
, ==, ZAP_CHUNK_ENTRY
);
751 uint16_t chunk
= zap_leaf_chunk_alloc(nl
);
752 struct zap_leaf_entry
*nle
= ZAP_LEAF_ENTRY(nl
, chunk
);
753 *nle
= *le
; /* structure assignment */
755 (void) zap_leaf_rehash_entry(nl
, chunk
);
757 nle
->le_name_chunk
= zap_leaf_transfer_array(l
, le
->le_name_chunk
, nl
);
758 nle
->le_value_chunk
=
759 zap_leaf_transfer_array(l
, le
->le_value_chunk
, nl
);
761 zap_leaf_chunk_free(l
, entry
);
763 zap_leaf_phys(l
)->l_hdr
.lh_nentries
--;
764 zap_leaf_phys(nl
)->l_hdr
.lh_nentries
++;
768 * Transfer the entries whose hash prefix ends in 1 to the new leaf.
771 zap_leaf_split(zap_leaf_t
*l
, zap_leaf_t
*nl
, boolean_t sort
)
773 int bit
= 64 - 1 - zap_leaf_phys(l
)->l_hdr
.lh_prefix_len
;
775 /* set new prefix and prefix_len */
776 zap_leaf_phys(l
)->l_hdr
.lh_prefix
<<= 1;
777 zap_leaf_phys(l
)->l_hdr
.lh_prefix_len
++;
778 zap_leaf_phys(nl
)->l_hdr
.lh_prefix
=
779 zap_leaf_phys(l
)->l_hdr
.lh_prefix
| 1;
780 zap_leaf_phys(nl
)->l_hdr
.lh_prefix_len
=
781 zap_leaf_phys(l
)->l_hdr
.lh_prefix_len
;
783 /* break existing hash chains */
784 zap_memset(zap_leaf_phys(l
)->l_hash
, CHAIN_END
,
785 2*ZAP_LEAF_HASH_NUMENTRIES(l
));
788 zap_leaf_phys(l
)->l_hdr
.lh_flags
|= ZLF_ENTRIES_CDSORTED
;
791 * Transfer entries whose hash bit 'bit' is set to nl; rehash
792 * the remaining entries
794 * NB: We could find entries via the hashtable instead. That
795 * would be O(hashents+numents) rather than O(numblks+numents),
796 * but this accesses memory more sequentially, and when we're
797 * called, the block is usually pretty full.
799 for (int i
= 0; i
< ZAP_LEAF_NUMCHUNKS(l
); i
++) {
800 struct zap_leaf_entry
*le
= ZAP_LEAF_ENTRY(l
, i
);
801 if (le
->le_type
!= ZAP_CHUNK_ENTRY
)
804 if (le
->le_hash
& (1ULL << bit
))
805 zap_leaf_transfer_entry(l
, i
, nl
);
807 (void) zap_leaf_rehash_entry(l
, i
);
812 zap_leaf_stats(zap_t
*zap
, zap_leaf_t
*l
, zap_stats_t
*zs
)
814 int n
= zap_f_phys(zap
)->zap_ptrtbl
.zt_shift
-
815 zap_leaf_phys(l
)->l_hdr
.lh_prefix_len
;
816 n
= MIN(n
, ZAP_HISTOGRAM_SIZE
-1);
817 zs
->zs_leafs_with_2n_pointers
[n
]++;
820 n
= zap_leaf_phys(l
)->l_hdr
.lh_nentries
/5;
821 n
= MIN(n
, ZAP_HISTOGRAM_SIZE
-1);
822 zs
->zs_blocks_with_n5_entries
[n
]++;
824 n
= ((1<<FZAP_BLOCK_SHIFT(zap
)) -
825 zap_leaf_phys(l
)->l_hdr
.lh_nfree
* (ZAP_LEAF_ARRAY_BYTES
+1))*10 /
826 (1<<FZAP_BLOCK_SHIFT(zap
));
827 n
= MIN(n
, ZAP_HISTOGRAM_SIZE
-1);
828 zs
->zs_blocks_n_tenths_full
[n
]++;
830 for (int i
= 0; i
< ZAP_LEAF_HASH_NUMENTRIES(l
); i
++) {
832 int chunk
= zap_leaf_phys(l
)->l_hash
[i
];
834 while (chunk
!= CHAIN_END
) {
835 struct zap_leaf_entry
*le
=
836 ZAP_LEAF_ENTRY(l
, chunk
);
838 n
= 1 + ZAP_LEAF_ARRAY_NCHUNKS(le
->le_name_numints
) +
839 ZAP_LEAF_ARRAY_NCHUNKS(le
->le_value_numints
*
840 le
->le_value_intlen
);
841 n
= MIN(n
, ZAP_HISTOGRAM_SIZE
-1);
842 zs
->zs_entries_using_n_chunks
[n
]++;
849 n
= MIN(n
, ZAP_HISTOGRAM_SIZE
-1);
850 zs
->zs_buckets_with_n_entries
[n
]++;