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]
22 * Copyright (c) 2005, 2010, Oracle and/or its affiliates. All rights reserved.
23 * Copyright (c) 2013, 2014 by Delphix. All rights reserved.
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.
35 #include <sys/zfs_context.h>
36 #include <sys/fs/zfs.h>
38 #include <sys/zap_impl.h>
39 #include <sys/zap_leaf.h>
42 static uint16_t *zap_leaf_rehash_entry(zap_leaf_t
*l
, uint16_t entry
);
44 #define CHAIN_END 0xffff /* end of the chunk chain */
46 /* half the (current) minimum block size */
47 #define MAX_ARRAY_BYTES (8<<10)
49 #define LEAF_HASH(l, h) \
50 ((ZAP_LEAF_HASH_NUMENTRIES(l)-1) & \
52 (64 - ZAP_LEAF_HASH_SHIFT(l) - zap_leaf_phys(l)->l_hdr.lh_prefix_len)))
54 #define LEAF_HASH_ENTPTR(l, h) (&zap_leaf_phys(l)->l_hash[LEAF_HASH(l, h)])
56 extern inline zap_leaf_phys_t
*zap_leaf_phys(zap_leaf_t
*l
);
59 zap_memset(void *a
, int c
, size_t n
)
69 stv(int len
, void *addr
, uint64_t value
)
73 *(uint8_t *)addr
= value
;
76 *(uint16_t *)addr
= value
;
79 *(uint32_t *)addr
= value
;
82 *(uint64_t *)addr
= value
;
85 cmn_err(CE_PANIC
, "bad int len %d", len
);
90 ldv(int len
, const void *addr
)
94 return (*(uint8_t *)addr
);
96 return (*(uint16_t *)addr
);
98 return (*(uint32_t *)addr
);
100 return (*(uint64_t *)addr
);
102 cmn_err(CE_PANIC
, "bad int len %d", len
);
104 return (0xFEEDFACEDEADBEEFULL
);
108 zap_leaf_byteswap(zap_leaf_phys_t
*buf
, int size
)
114 l_dbuf
.db_data
= buf
;
115 l
.l_bs
= highbit64(size
) - 1;
118 buf
->l_hdr
.lh_block_type
= BSWAP_64(buf
->l_hdr
.lh_block_type
);
119 buf
->l_hdr
.lh_prefix
= BSWAP_64(buf
->l_hdr
.lh_prefix
);
120 buf
->l_hdr
.lh_magic
= BSWAP_32(buf
->l_hdr
.lh_magic
);
121 buf
->l_hdr
.lh_nfree
= BSWAP_16(buf
->l_hdr
.lh_nfree
);
122 buf
->l_hdr
.lh_nentries
= BSWAP_16(buf
->l_hdr
.lh_nentries
);
123 buf
->l_hdr
.lh_prefix_len
= BSWAP_16(buf
->l_hdr
.lh_prefix_len
);
124 buf
->l_hdr
.lh_freelist
= BSWAP_16(buf
->l_hdr
.lh_freelist
);
126 for (i
= 0; i
< ZAP_LEAF_HASH_NUMENTRIES(&l
); i
++)
127 buf
->l_hash
[i
] = BSWAP_16(buf
->l_hash
[i
]);
129 for (i
= 0; i
< ZAP_LEAF_NUMCHUNKS(&l
); i
++) {
130 zap_leaf_chunk_t
*lc
= &ZAP_LEAF_CHUNK(&l
, i
);
131 struct zap_leaf_entry
*le
;
133 switch (lc
->l_free
.lf_type
) {
134 case ZAP_CHUNK_ENTRY
:
137 le
->le_type
= BSWAP_8(le
->le_type
);
138 le
->le_value_intlen
= BSWAP_8(le
->le_value_intlen
);
139 le
->le_next
= BSWAP_16(le
->le_next
);
140 le
->le_name_chunk
= BSWAP_16(le
->le_name_chunk
);
141 le
->le_name_numints
= BSWAP_16(le
->le_name_numints
);
142 le
->le_value_chunk
= BSWAP_16(le
->le_value_chunk
);
143 le
->le_value_numints
= BSWAP_16(le
->le_value_numints
);
144 le
->le_cd
= BSWAP_32(le
->le_cd
);
145 le
->le_hash
= BSWAP_64(le
->le_hash
);
148 lc
->l_free
.lf_type
= BSWAP_8(lc
->l_free
.lf_type
);
149 lc
->l_free
.lf_next
= BSWAP_16(lc
->l_free
.lf_next
);
151 case ZAP_CHUNK_ARRAY
:
152 lc
->l_array
.la_type
= BSWAP_8(lc
->l_array
.la_type
);
153 lc
->l_array
.la_next
= BSWAP_16(lc
->l_array
.la_next
);
154 /* la_array doesn't need swapping */
157 cmn_err(CE_PANIC
, "bad leaf type %d",
164 zap_leaf_init(zap_leaf_t
*l
, boolean_t sort
)
168 l
->l_bs
= highbit64(l
->l_dbuf
->db_size
) - 1;
169 zap_memset(&zap_leaf_phys(l
)->l_hdr
, 0,
170 sizeof (struct zap_leaf_header
));
171 zap_memset(zap_leaf_phys(l
)->l_hash
, CHAIN_END
,
172 2*ZAP_LEAF_HASH_NUMENTRIES(l
));
173 for (i
= 0; i
< ZAP_LEAF_NUMCHUNKS(l
); i
++) {
174 ZAP_LEAF_CHUNK(l
, i
).l_free
.lf_type
= ZAP_CHUNK_FREE
;
175 ZAP_LEAF_CHUNK(l
, i
).l_free
.lf_next
= i
+1;
177 ZAP_LEAF_CHUNK(l
, ZAP_LEAF_NUMCHUNKS(l
)-1).l_free
.lf_next
= CHAIN_END
;
178 zap_leaf_phys(l
)->l_hdr
.lh_block_type
= ZBT_LEAF
;
179 zap_leaf_phys(l
)->l_hdr
.lh_magic
= ZAP_LEAF_MAGIC
;
180 zap_leaf_phys(l
)->l_hdr
.lh_nfree
= ZAP_LEAF_NUMCHUNKS(l
);
182 zap_leaf_phys(l
)->l_hdr
.lh_flags
|= ZLF_ENTRIES_CDSORTED
;
186 * Routines which manipulate leaf chunks (l_chunk[]).
190 zap_leaf_chunk_alloc(zap_leaf_t
*l
)
194 ASSERT(zap_leaf_phys(l
)->l_hdr
.lh_nfree
> 0);
196 chunk
= zap_leaf_phys(l
)->l_hdr
.lh_freelist
;
197 ASSERT3U(chunk
, <, ZAP_LEAF_NUMCHUNKS(l
));
198 ASSERT3U(ZAP_LEAF_CHUNK(l
, chunk
).l_free
.lf_type
, ==, ZAP_CHUNK_FREE
);
200 zap_leaf_phys(l
)->l_hdr
.lh_freelist
=
201 ZAP_LEAF_CHUNK(l
, chunk
).l_free
.lf_next
;
203 zap_leaf_phys(l
)->l_hdr
.lh_nfree
--;
209 zap_leaf_chunk_free(zap_leaf_t
*l
, uint16_t chunk
)
211 struct zap_leaf_free
*zlf
= &ZAP_LEAF_CHUNK(l
, chunk
).l_free
;
212 ASSERT3U(zap_leaf_phys(l
)->l_hdr
.lh_nfree
, <, ZAP_LEAF_NUMCHUNKS(l
));
213 ASSERT3U(chunk
, <, ZAP_LEAF_NUMCHUNKS(l
));
214 ASSERT(zlf
->lf_type
!= ZAP_CHUNK_FREE
);
216 zlf
->lf_type
= ZAP_CHUNK_FREE
;
217 zlf
->lf_next
= zap_leaf_phys(l
)->l_hdr
.lh_freelist
;
218 bzero(zlf
->lf_pad
, sizeof (zlf
->lf_pad
)); /* help it to compress */
219 zap_leaf_phys(l
)->l_hdr
.lh_freelist
= chunk
;
221 zap_leaf_phys(l
)->l_hdr
.lh_nfree
++;
225 * Routines which manipulate leaf arrays (zap_leaf_array type chunks).
229 zap_leaf_array_create(zap_leaf_t
*l
, const char *buf
,
230 int integer_size
, int num_integers
)
233 uint16_t *chunkp
= &chunk_head
;
236 int shift
= (integer_size
-1)*8;
237 int len
= num_integers
;
239 ASSERT3U(num_integers
* integer_size
, <, MAX_ARRAY_BYTES
);
242 uint16_t chunk
= zap_leaf_chunk_alloc(l
);
243 struct zap_leaf_array
*la
= &ZAP_LEAF_CHUNK(l
, chunk
).l_array
;
246 la
->la_type
= ZAP_CHUNK_ARRAY
;
247 for (i
= 0; i
< ZAP_LEAF_ARRAY_BYTES
; i
++) {
249 value
= ldv(integer_size
, buf
);
250 la
->la_array
[i
] = value
>> shift
;
252 if (++byten
== integer_size
) {
261 chunkp
= &la
->la_next
;
269 zap_leaf_array_free(zap_leaf_t
*l
, uint16_t *chunkp
)
271 uint16_t chunk
= *chunkp
;
275 while (chunk
!= CHAIN_END
) {
276 int nextchunk
= ZAP_LEAF_CHUNK(l
, chunk
).l_array
.la_next
;
277 ASSERT3U(ZAP_LEAF_CHUNK(l
, chunk
).l_array
.la_type
, ==,
279 zap_leaf_chunk_free(l
, chunk
);
284 /* array_len and buf_len are in integers, not bytes */
286 zap_leaf_array_read(zap_leaf_t
*l
, uint16_t chunk
,
287 int array_int_len
, int array_len
, int buf_int_len
, uint64_t buf_len
,
290 int len
= MIN(array_len
, buf_len
);
295 ASSERT3U(array_int_len
, <=, buf_int_len
);
297 /* Fast path for one 8-byte integer */
298 if (array_int_len
== 8 && buf_int_len
== 8 && len
== 1) {
299 struct zap_leaf_array
*la
= &ZAP_LEAF_CHUNK(l
, chunk
).l_array
;
300 uint8_t *ip
= la
->la_array
;
301 uint64_t *buf64
= buf
;
303 *buf64
= (uint64_t)ip
[0] << 56 | (uint64_t)ip
[1] << 48 |
304 (uint64_t)ip
[2] << 40 | (uint64_t)ip
[3] << 32 |
305 (uint64_t)ip
[4] << 24 | (uint64_t)ip
[5] << 16 |
306 (uint64_t)ip
[6] << 8 | (uint64_t)ip
[7];
310 /* Fast path for an array of 1-byte integers (eg. the entry name) */
311 if (array_int_len
== 1 && buf_int_len
== 1 &&
312 buf_len
> array_len
+ ZAP_LEAF_ARRAY_BYTES
) {
313 while (chunk
!= CHAIN_END
) {
314 struct zap_leaf_array
*la
=
315 &ZAP_LEAF_CHUNK(l
, chunk
).l_array
;
316 bcopy(la
->la_array
, p
, ZAP_LEAF_ARRAY_BYTES
);
317 p
+= ZAP_LEAF_ARRAY_BYTES
;
324 struct zap_leaf_array
*la
= &ZAP_LEAF_CHUNK(l
, chunk
).l_array
;
327 ASSERT3U(chunk
, <, ZAP_LEAF_NUMCHUNKS(l
));
328 for (i
= 0; i
< ZAP_LEAF_ARRAY_BYTES
&& len
> 0; i
++) {
329 value
= (value
<< 8) | la
->la_array
[i
];
331 if (byten
== array_int_len
) {
332 stv(buf_int_len
, p
, value
);
345 zap_leaf_array_match(zap_leaf_t
*l
, zap_name_t
*zn
,
346 int chunk
, int array_numints
)
350 if (zap_getflags(zn
->zn_zap
) & ZAP_FLAG_UINT64_KEY
) {
354 ASSERT(zn
->zn_key_intlen
== sizeof (*thiskey
));
355 thiskey
= kmem_alloc(array_numints
* sizeof (*thiskey
),
358 zap_leaf_array_read(l
, chunk
, sizeof (*thiskey
), array_numints
,
359 sizeof (*thiskey
), array_numints
, thiskey
);
360 match
= bcmp(thiskey
, zn
->zn_key_orig
,
361 array_numints
* sizeof (*thiskey
)) == 0;
362 kmem_free(thiskey
, array_numints
* sizeof (*thiskey
));
366 ASSERT(zn
->zn_key_intlen
== 1);
367 if (zn
->zn_matchtype
== MT_FIRST
) {
368 char *thisname
= kmem_alloc(array_numints
, KM_SLEEP
);
371 zap_leaf_array_read(l
, chunk
, sizeof (char), array_numints
,
372 sizeof (char), array_numints
, thisname
);
373 match
= zap_match(zn
, thisname
);
374 kmem_free(thisname
, array_numints
);
379 * Fast path for exact matching.
380 * First check that the lengths match, so that we don't read
381 * past the end of the zn_key_orig array.
383 if (array_numints
!= zn
->zn_key_orig_numints
)
385 while (bseen
< array_numints
) {
386 struct zap_leaf_array
*la
= &ZAP_LEAF_CHUNK(l
, chunk
).l_array
;
387 int toread
= MIN(array_numints
- bseen
, ZAP_LEAF_ARRAY_BYTES
);
388 ASSERT3U(chunk
, <, ZAP_LEAF_NUMCHUNKS(l
));
389 if (bcmp(la
->la_array
, (char *)zn
->zn_key_orig
+ bseen
, toread
))
394 return (bseen
== array_numints
);
398 * Routines which manipulate leaf entries.
402 zap_leaf_lookup(zap_leaf_t
*l
, zap_name_t
*zn
, zap_entry_handle_t
*zeh
)
405 struct zap_leaf_entry
*le
;
407 ASSERT3U(zap_leaf_phys(l
)->l_hdr
.lh_magic
, ==, ZAP_LEAF_MAGIC
);
410 for (chunkp
= LEAF_HASH_ENTPTR(l
, zn
->zn_hash
);
411 *chunkp
!= CHAIN_END
; chunkp
= &le
->le_next
) {
412 uint16_t chunk
= *chunkp
;
413 le
= ZAP_LEAF_ENTRY(l
, chunk
);
415 ASSERT3U(chunk
, <, ZAP_LEAF_NUMCHUNKS(l
));
416 ASSERT3U(le
->le_type
, ==, ZAP_CHUNK_ENTRY
);
418 if (le
->le_hash
!= zn
->zn_hash
)
422 * NB: the entry chain is always sorted by cd on
423 * normalized zap objects, so this will find the
424 * lowest-cd match for MT_FIRST.
426 ASSERT(zn
->zn_matchtype
== MT_EXACT
||
427 (zap_leaf_phys(l
)->l_hdr
.lh_flags
& ZLF_ENTRIES_CDSORTED
));
428 if (zap_leaf_array_match(l
, zn
, le
->le_name_chunk
,
429 le
->le_name_numints
)) {
430 zeh
->zeh_num_integers
= le
->le_value_numints
;
431 zeh
->zeh_integer_size
= le
->le_value_intlen
;
432 zeh
->zeh_cd
= le
->le_cd
;
433 zeh
->zeh_hash
= le
->le_hash
;
434 zeh
->zeh_chunkp
= chunkp
;
441 * NB: we could of course do this in one pass, but that would be
442 * a pain. We'll see if MT_BEST is even used much.
444 if (zn
->zn_matchtype
== MT_BEST
) {
445 zn
->zn_matchtype
= MT_FIRST
;
449 return (SET_ERROR(ENOENT
));
452 /* Return (h1,cd1 >= h2,cd2) */
453 #define HCD_GTEQ(h1, cd1, h2, cd2) \
454 ((h1 > h2) ? TRUE : ((h1 == h2 && cd1 >= cd2) ? TRUE : FALSE))
457 zap_leaf_lookup_closest(zap_leaf_t
*l
,
458 uint64_t h
, uint32_t cd
, zap_entry_handle_t
*zeh
)
461 uint64_t besth
= -1ULL;
462 uint32_t bestcd
= -1U;
463 uint16_t bestlh
= ZAP_LEAF_HASH_NUMENTRIES(l
)-1;
465 struct zap_leaf_entry
*le
;
467 ASSERT3U(zap_leaf_phys(l
)->l_hdr
.lh_magic
, ==, ZAP_LEAF_MAGIC
);
469 for (lh
= LEAF_HASH(l
, h
); lh
<= bestlh
; lh
++) {
470 for (chunk
= zap_leaf_phys(l
)->l_hash
[lh
];
471 chunk
!= CHAIN_END
; chunk
= le
->le_next
) {
472 le
= ZAP_LEAF_ENTRY(l
, chunk
);
474 ASSERT3U(chunk
, <, ZAP_LEAF_NUMCHUNKS(l
));
475 ASSERT3U(le
->le_type
, ==, ZAP_CHUNK_ENTRY
);
477 if (HCD_GTEQ(le
->le_hash
, le
->le_cd
, h
, cd
) &&
478 HCD_GTEQ(besth
, bestcd
, le
->le_hash
, le
->le_cd
)) {
479 ASSERT3U(bestlh
, >=, lh
);
484 zeh
->zeh_num_integers
= le
->le_value_numints
;
485 zeh
->zeh_integer_size
= le
->le_value_intlen
;
486 zeh
->zeh_cd
= le
->le_cd
;
487 zeh
->zeh_hash
= le
->le_hash
;
488 zeh
->zeh_fakechunk
= chunk
;
489 zeh
->zeh_chunkp
= &zeh
->zeh_fakechunk
;
495 return (bestcd
== -1U ? ENOENT
: 0);
499 zap_entry_read(const zap_entry_handle_t
*zeh
,
500 uint8_t integer_size
, uint64_t num_integers
, void *buf
)
502 struct zap_leaf_entry
*le
=
503 ZAP_LEAF_ENTRY(zeh
->zeh_leaf
, *zeh
->zeh_chunkp
);
504 ASSERT3U(le
->le_type
, ==, ZAP_CHUNK_ENTRY
);
506 if (le
->le_value_intlen
> integer_size
)
507 return (SET_ERROR(EINVAL
));
509 zap_leaf_array_read(zeh
->zeh_leaf
, le
->le_value_chunk
,
510 le
->le_value_intlen
, le
->le_value_numints
,
511 integer_size
, num_integers
, buf
);
513 if (zeh
->zeh_num_integers
> num_integers
)
514 return (SET_ERROR(EOVERFLOW
));
520 zap_entry_read_name(zap_t
*zap
, const zap_entry_handle_t
*zeh
, uint16_t buflen
,
523 struct zap_leaf_entry
*le
=
524 ZAP_LEAF_ENTRY(zeh
->zeh_leaf
, *zeh
->zeh_chunkp
);
525 ASSERT3U(le
->le_type
, ==, ZAP_CHUNK_ENTRY
);
527 if (zap_getflags(zap
) & ZAP_FLAG_UINT64_KEY
) {
528 zap_leaf_array_read(zeh
->zeh_leaf
, le
->le_name_chunk
, 8,
529 le
->le_name_numints
, 8, buflen
/ 8, buf
);
531 zap_leaf_array_read(zeh
->zeh_leaf
, le
->le_name_chunk
, 1,
532 le
->le_name_numints
, 1, buflen
, buf
);
534 if (le
->le_name_numints
> buflen
)
535 return (SET_ERROR(EOVERFLOW
));
540 zap_entry_update(zap_entry_handle_t
*zeh
,
541 uint8_t integer_size
, uint64_t num_integers
, const void *buf
)
544 zap_leaf_t
*l
= zeh
->zeh_leaf
;
545 struct zap_leaf_entry
*le
= ZAP_LEAF_ENTRY(l
, *zeh
->zeh_chunkp
);
547 delta_chunks
= ZAP_LEAF_ARRAY_NCHUNKS(num_integers
* integer_size
) -
548 ZAP_LEAF_ARRAY_NCHUNKS(le
->le_value_numints
* le
->le_value_intlen
);
550 if ((int)zap_leaf_phys(l
)->l_hdr
.lh_nfree
< delta_chunks
)
551 return (SET_ERROR(EAGAIN
));
553 zap_leaf_array_free(l
, &le
->le_value_chunk
);
555 zap_leaf_array_create(l
, buf
, integer_size
, num_integers
);
556 le
->le_value_numints
= num_integers
;
557 le
->le_value_intlen
= integer_size
;
562 zap_entry_remove(zap_entry_handle_t
*zeh
)
564 uint16_t entry_chunk
;
565 struct zap_leaf_entry
*le
;
566 zap_leaf_t
*l
= zeh
->zeh_leaf
;
568 ASSERT3P(zeh
->zeh_chunkp
, !=, &zeh
->zeh_fakechunk
);
570 entry_chunk
= *zeh
->zeh_chunkp
;
571 le
= ZAP_LEAF_ENTRY(l
, entry_chunk
);
572 ASSERT3U(le
->le_type
, ==, ZAP_CHUNK_ENTRY
);
574 zap_leaf_array_free(l
, &le
->le_name_chunk
);
575 zap_leaf_array_free(l
, &le
->le_value_chunk
);
577 *zeh
->zeh_chunkp
= le
->le_next
;
578 zap_leaf_chunk_free(l
, entry_chunk
);
580 zap_leaf_phys(l
)->l_hdr
.lh_nentries
--;
584 zap_entry_create(zap_leaf_t
*l
, zap_name_t
*zn
, uint32_t cd
,
585 uint8_t integer_size
, uint64_t num_integers
, const void *buf
,
586 zap_entry_handle_t
*zeh
)
590 struct zap_leaf_entry
*le
;
593 uint64_t h
= zn
->zn_hash
;
595 valuelen
= integer_size
* num_integers
;
597 numchunks
= 1 + ZAP_LEAF_ARRAY_NCHUNKS(zn
->zn_key_orig_numints
*
598 zn
->zn_key_intlen
) + ZAP_LEAF_ARRAY_NCHUNKS(valuelen
);
599 if (numchunks
> ZAP_LEAF_NUMCHUNKS(l
))
602 if (cd
== ZAP_NEED_CD
) {
603 /* find the lowest unused cd */
604 if (zap_leaf_phys(l
)->l_hdr
.lh_flags
& ZLF_ENTRIES_CDSORTED
) {
607 for (chunk
= *LEAF_HASH_ENTPTR(l
, h
);
608 chunk
!= CHAIN_END
; chunk
= le
->le_next
) {
609 le
= ZAP_LEAF_ENTRY(l
, chunk
);
612 if (le
->le_hash
== h
) {
613 ASSERT3U(cd
, ==, le
->le_cd
);
618 /* old unsorted format; do it the O(n^2) way */
619 for (cd
= 0; ; cd
++) {
620 for (chunk
= *LEAF_HASH_ENTPTR(l
, h
);
621 chunk
!= CHAIN_END
; chunk
= le
->le_next
) {
622 le
= ZAP_LEAF_ENTRY(l
, chunk
);
623 if (le
->le_hash
== h
&&
628 /* If this cd is not in use, we are good. */
629 if (chunk
== CHAIN_END
)
634 * We would run out of space in a block before we could
635 * store enough entries to run out of CD values.
637 ASSERT3U(cd
, <, zap_maxcd(zn
->zn_zap
));
640 if (zap_leaf_phys(l
)->l_hdr
.lh_nfree
< numchunks
)
641 return (SET_ERROR(EAGAIN
));
644 chunk
= zap_leaf_chunk_alloc(l
);
645 le
= ZAP_LEAF_ENTRY(l
, chunk
);
646 le
->le_type
= ZAP_CHUNK_ENTRY
;
647 le
->le_name_chunk
= zap_leaf_array_create(l
, zn
->zn_key_orig
,
648 zn
->zn_key_intlen
, zn
->zn_key_orig_numints
);
649 le
->le_name_numints
= zn
->zn_key_orig_numints
;
651 zap_leaf_array_create(l
, buf
, integer_size
, num_integers
);
652 le
->le_value_numints
= num_integers
;
653 le
->le_value_intlen
= integer_size
;
657 /* link it into the hash chain */
658 /* XXX if we did the search above, we could just use that */
659 chunkp
= zap_leaf_rehash_entry(l
, chunk
);
661 zap_leaf_phys(l
)->l_hdr
.lh_nentries
++;
664 zeh
->zeh_num_integers
= num_integers
;
665 zeh
->zeh_integer_size
= le
->le_value_intlen
;
666 zeh
->zeh_cd
= le
->le_cd
;
667 zeh
->zeh_hash
= le
->le_hash
;
668 zeh
->zeh_chunkp
= chunkp
;
674 * Determine if there is another entry with the same normalized form.
675 * For performance purposes, either zn or name must be provided (the
676 * other can be NULL). Note, there usually won't be any hash
677 * conflicts, in which case we don't need the concatenated/normalized
678 * form of the name. But all callers have one of these on hand anyway,
679 * so might as well take advantage. A cleaner but slower interface
680 * would accept neither argument, and compute the normalized name as
681 * needed (using zap_name_alloc(zap_entry_read_name(zeh))).
684 zap_entry_normalization_conflict(zap_entry_handle_t
*zeh
, zap_name_t
*zn
,
685 const char *name
, zap_t
*zap
)
688 struct zap_leaf_entry
*le
;
689 boolean_t allocdzn
= B_FALSE
;
691 if (zap
->zap_normflags
== 0)
694 for (chunk
= *LEAF_HASH_ENTPTR(zeh
->zeh_leaf
, zeh
->zeh_hash
);
695 chunk
!= CHAIN_END
; chunk
= le
->le_next
) {
696 le
= ZAP_LEAF_ENTRY(zeh
->zeh_leaf
, chunk
);
697 if (le
->le_hash
!= zeh
->zeh_hash
)
699 if (le
->le_cd
== zeh
->zeh_cd
)
703 zn
= zap_name_alloc(zap
, name
, MT_FIRST
);
706 if (zap_leaf_array_match(zeh
->zeh_leaf
, zn
,
707 le
->le_name_chunk
, le
->le_name_numints
)) {
719 * Routines for transferring entries between leafs.
723 zap_leaf_rehash_entry(zap_leaf_t
*l
, uint16_t entry
)
725 struct zap_leaf_entry
*le
= ZAP_LEAF_ENTRY(l
, entry
);
726 struct zap_leaf_entry
*le2
;
730 * keep the entry chain sorted by cd
731 * NB: this will not cause problems for unsorted leafs, though
732 * it is unnecessary there.
734 for (chunkp
= LEAF_HASH_ENTPTR(l
, le
->le_hash
);
735 *chunkp
!= CHAIN_END
; chunkp
= &le2
->le_next
) {
736 le2
= ZAP_LEAF_ENTRY(l
, *chunkp
);
737 if (le2
->le_cd
> le
->le_cd
)
741 le
->le_next
= *chunkp
;
747 zap_leaf_transfer_array(zap_leaf_t
*l
, uint16_t chunk
, zap_leaf_t
*nl
)
750 uint16_t *nchunkp
= &new_chunk
;
752 while (chunk
!= CHAIN_END
) {
753 uint16_t nchunk
= zap_leaf_chunk_alloc(nl
);
754 struct zap_leaf_array
*nla
=
755 &ZAP_LEAF_CHUNK(nl
, nchunk
).l_array
;
756 struct zap_leaf_array
*la
=
757 &ZAP_LEAF_CHUNK(l
, chunk
).l_array
;
758 int nextchunk
= la
->la_next
;
760 ASSERT3U(chunk
, <, ZAP_LEAF_NUMCHUNKS(l
));
761 ASSERT3U(nchunk
, <, ZAP_LEAF_NUMCHUNKS(l
));
763 *nla
= *la
; /* structure assignment */
765 zap_leaf_chunk_free(l
, chunk
);
768 nchunkp
= &nla
->la_next
;
770 *nchunkp
= CHAIN_END
;
775 zap_leaf_transfer_entry(zap_leaf_t
*l
, int entry
, zap_leaf_t
*nl
)
777 struct zap_leaf_entry
*le
, *nle
;
780 le
= ZAP_LEAF_ENTRY(l
, entry
);
781 ASSERT3U(le
->le_type
, ==, ZAP_CHUNK_ENTRY
);
783 chunk
= zap_leaf_chunk_alloc(nl
);
784 nle
= ZAP_LEAF_ENTRY(nl
, chunk
);
785 *nle
= *le
; /* structure assignment */
787 (void) zap_leaf_rehash_entry(nl
, chunk
);
789 nle
->le_name_chunk
= zap_leaf_transfer_array(l
, le
->le_name_chunk
, nl
);
790 nle
->le_value_chunk
=
791 zap_leaf_transfer_array(l
, le
->le_value_chunk
, nl
);
793 zap_leaf_chunk_free(l
, entry
);
795 zap_leaf_phys(l
)->l_hdr
.lh_nentries
--;
796 zap_leaf_phys(nl
)->l_hdr
.lh_nentries
++;
800 * Transfer the entries whose hash prefix ends in 1 to the new leaf.
803 zap_leaf_split(zap_leaf_t
*l
, zap_leaf_t
*nl
, boolean_t sort
)
806 int bit
= 64 - 1 - zap_leaf_phys(l
)->l_hdr
.lh_prefix_len
;
808 /* set new prefix and prefix_len */
809 zap_leaf_phys(l
)->l_hdr
.lh_prefix
<<= 1;
810 zap_leaf_phys(l
)->l_hdr
.lh_prefix_len
++;
811 zap_leaf_phys(nl
)->l_hdr
.lh_prefix
=
812 zap_leaf_phys(l
)->l_hdr
.lh_prefix
| 1;
813 zap_leaf_phys(nl
)->l_hdr
.lh_prefix_len
=
814 zap_leaf_phys(l
)->l_hdr
.lh_prefix_len
;
816 /* break existing hash chains */
817 zap_memset(zap_leaf_phys(l
)->l_hash
, CHAIN_END
,
818 2*ZAP_LEAF_HASH_NUMENTRIES(l
));
821 zap_leaf_phys(l
)->l_hdr
.lh_flags
|= ZLF_ENTRIES_CDSORTED
;
824 * Transfer entries whose hash bit 'bit' is set to nl; rehash
825 * the remaining entries
827 * NB: We could find entries via the hashtable instead. That
828 * would be O(hashents+numents) rather than O(numblks+numents),
829 * but this accesses memory more sequentially, and when we're
830 * called, the block is usually pretty full.
832 for (i
= 0; i
< ZAP_LEAF_NUMCHUNKS(l
); i
++) {
833 struct zap_leaf_entry
*le
= ZAP_LEAF_ENTRY(l
, i
);
834 if (le
->le_type
!= ZAP_CHUNK_ENTRY
)
837 if (le
->le_hash
& (1ULL << bit
))
838 zap_leaf_transfer_entry(l
, i
, nl
);
840 (void) zap_leaf_rehash_entry(l
, i
);
845 zap_leaf_stats(zap_t
*zap
, zap_leaf_t
*l
, zap_stats_t
*zs
)
849 n
= zap_f_phys(zap
)->zap_ptrtbl
.zt_shift
-
850 zap_leaf_phys(l
)->l_hdr
.lh_prefix_len
;
851 n
= MIN(n
, ZAP_HISTOGRAM_SIZE
-1);
852 zs
->zs_leafs_with_2n_pointers
[n
]++;
855 n
= zap_leaf_phys(l
)->l_hdr
.lh_nentries
/5;
856 n
= MIN(n
, ZAP_HISTOGRAM_SIZE
-1);
857 zs
->zs_blocks_with_n5_entries
[n
]++;
859 n
= ((1<<FZAP_BLOCK_SHIFT(zap
)) -
860 zap_leaf_phys(l
)->l_hdr
.lh_nfree
* (ZAP_LEAF_ARRAY_BYTES
+1))*10 /
861 (1<<FZAP_BLOCK_SHIFT(zap
));
862 n
= MIN(n
, ZAP_HISTOGRAM_SIZE
-1);
863 zs
->zs_blocks_n_tenths_full
[n
]++;
865 for (i
= 0; i
< ZAP_LEAF_HASH_NUMENTRIES(l
); i
++) {
867 int chunk
= zap_leaf_phys(l
)->l_hash
[i
];
869 while (chunk
!= CHAIN_END
) {
870 struct zap_leaf_entry
*le
=
871 ZAP_LEAF_ENTRY(l
, chunk
);
873 n
= 1 + ZAP_LEAF_ARRAY_NCHUNKS(le
->le_name_numints
) +
874 ZAP_LEAF_ARRAY_NCHUNKS(le
->le_value_numints
*
875 le
->le_value_intlen
);
876 n
= MIN(n
, ZAP_HISTOGRAM_SIZE
-1);
877 zs
->zs_entries_using_n_chunks
[n
]++;
884 n
= MIN(n
, ZAP_HISTOGRAM_SIZE
-1);
885 zs
->zs_buckets_with_n_entries
[n
]++;