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.
26 * The 512-byte leaf is broken into 32 16-byte chunks.
27 * chunk number n means l_chunk[n], even though the header precedes it.
28 * the names are stored null-terminated.
34 #include <sys/zfs_context.h>
35 #include <sys/fs/zfs.h>
37 #include <sys/zap_impl.h>
38 #include <sys/zap_leaf.h>
41 static uint16_t *zap_leaf_rehash_entry(zap_leaf_t
*l
, uint16_t entry
);
43 #define CHAIN_END 0xffff /* end of the chunk chain */
45 /* half the (current) minimum block size */
46 #define MAX_ARRAY_BYTES (8<<10)
48 #define LEAF_HASH(l, h) \
49 ((ZAP_LEAF_HASH_NUMENTRIES(l)-1) & \
50 ((h) >> (64 - ZAP_LEAF_HASH_SHIFT(l)-(l)->l_phys->l_hdr.lh_prefix_len)))
52 #define LEAF_HASH_ENTPTR(l, h) (&(l)->l_phys->l_hash[LEAF_HASH(l, h)])
56 zap_memset(void *a
, int c
, size_t n
)
66 stv(int len
, void *addr
, uint64_t value
)
70 *(uint8_t *)addr
= value
;
73 *(uint16_t *)addr
= value
;
76 *(uint32_t *)addr
= value
;
79 *(uint64_t *)addr
= value
;
82 ASSERT(!"bad int len");
86 ldv(int len
, const void *addr
)
90 return (*(uint8_t *)addr
);
92 return (*(uint16_t *)addr
);
94 return (*(uint32_t *)addr
);
96 return (*(uint64_t *)addr
);
98 ASSERT(!"bad int len");
99 return (0xFEEDFACEDEADBEEFULL
);
103 zap_leaf_byteswap(zap_leaf_phys_t
*buf
, int size
)
107 l
.l_bs
= highbit(size
)-1;
110 buf
->l_hdr
.lh_block_type
= BSWAP_64(buf
->l_hdr
.lh_block_type
);
111 buf
->l_hdr
.lh_prefix
= BSWAP_64(buf
->l_hdr
.lh_prefix
);
112 buf
->l_hdr
.lh_magic
= BSWAP_32(buf
->l_hdr
.lh_magic
);
113 buf
->l_hdr
.lh_nfree
= BSWAP_16(buf
->l_hdr
.lh_nfree
);
114 buf
->l_hdr
.lh_nentries
= BSWAP_16(buf
->l_hdr
.lh_nentries
);
115 buf
->l_hdr
.lh_prefix_len
= BSWAP_16(buf
->l_hdr
.lh_prefix_len
);
116 buf
->l_hdr
.lh_freelist
= BSWAP_16(buf
->l_hdr
.lh_freelist
);
118 for (i
= 0; i
< ZAP_LEAF_HASH_NUMENTRIES(&l
); i
++)
119 buf
->l_hash
[i
] = BSWAP_16(buf
->l_hash
[i
]);
121 for (i
= 0; i
< ZAP_LEAF_NUMCHUNKS(&l
); i
++) {
122 zap_leaf_chunk_t
*lc
= &ZAP_LEAF_CHUNK(&l
, i
);
123 struct zap_leaf_entry
*le
;
125 switch (lc
->l_free
.lf_type
) {
126 case ZAP_CHUNK_ENTRY
:
129 le
->le_type
= BSWAP_8(le
->le_type
);
130 le
->le_value_intlen
= BSWAP_8(le
->le_value_intlen
);
131 le
->le_next
= BSWAP_16(le
->le_next
);
132 le
->le_name_chunk
= BSWAP_16(le
->le_name_chunk
);
133 le
->le_name_numints
= BSWAP_16(le
->le_name_numints
);
134 le
->le_value_chunk
= BSWAP_16(le
->le_value_chunk
);
135 le
->le_value_numints
= BSWAP_16(le
->le_value_numints
);
136 le
->le_cd
= BSWAP_32(le
->le_cd
);
137 le
->le_hash
= BSWAP_64(le
->le_hash
);
140 lc
->l_free
.lf_type
= BSWAP_8(lc
->l_free
.lf_type
);
141 lc
->l_free
.lf_next
= BSWAP_16(lc
->l_free
.lf_next
);
143 case ZAP_CHUNK_ARRAY
:
144 lc
->l_array
.la_type
= BSWAP_8(lc
->l_array
.la_type
);
145 lc
->l_array
.la_next
= BSWAP_16(lc
->l_array
.la_next
);
146 /* la_array doesn't need swapping */
149 ASSERT(!"bad leaf type");
155 zap_leaf_init(zap_leaf_t
*l
, boolean_t sort
)
159 l
->l_bs
= highbit(l
->l_dbuf
->db_size
)-1;
160 zap_memset(&l
->l_phys
->l_hdr
, 0, sizeof (struct zap_leaf_header
));
161 zap_memset(l
->l_phys
->l_hash
, CHAIN_END
, 2*ZAP_LEAF_HASH_NUMENTRIES(l
));
162 for (i
= 0; i
< ZAP_LEAF_NUMCHUNKS(l
); i
++) {
163 ZAP_LEAF_CHUNK(l
, i
).l_free
.lf_type
= ZAP_CHUNK_FREE
;
164 ZAP_LEAF_CHUNK(l
, i
).l_free
.lf_next
= i
+1;
166 ZAP_LEAF_CHUNK(l
, ZAP_LEAF_NUMCHUNKS(l
)-1).l_free
.lf_next
= CHAIN_END
;
167 l
->l_phys
->l_hdr
.lh_block_type
= ZBT_LEAF
;
168 l
->l_phys
->l_hdr
.lh_magic
= ZAP_LEAF_MAGIC
;
169 l
->l_phys
->l_hdr
.lh_nfree
= ZAP_LEAF_NUMCHUNKS(l
);
171 l
->l_phys
->l_hdr
.lh_flags
|= ZLF_ENTRIES_CDSORTED
;
175 * Routines which manipulate leaf chunks (l_chunk[]).
179 zap_leaf_chunk_alloc(zap_leaf_t
*l
)
183 ASSERT(l
->l_phys
->l_hdr
.lh_nfree
> 0);
185 chunk
= l
->l_phys
->l_hdr
.lh_freelist
;
186 ASSERT3U(chunk
, <, ZAP_LEAF_NUMCHUNKS(l
));
187 ASSERT3U(ZAP_LEAF_CHUNK(l
, chunk
).l_free
.lf_type
, ==, ZAP_CHUNK_FREE
);
189 l
->l_phys
->l_hdr
.lh_freelist
= ZAP_LEAF_CHUNK(l
, chunk
).l_free
.lf_next
;
191 l
->l_phys
->l_hdr
.lh_nfree
--;
197 zap_leaf_chunk_free(zap_leaf_t
*l
, uint16_t chunk
)
199 struct zap_leaf_free
*zlf
= &ZAP_LEAF_CHUNK(l
, chunk
).l_free
;
200 ASSERT3U(l
->l_phys
->l_hdr
.lh_nfree
, <, ZAP_LEAF_NUMCHUNKS(l
));
201 ASSERT3U(chunk
, <, ZAP_LEAF_NUMCHUNKS(l
));
202 ASSERT(zlf
->lf_type
!= ZAP_CHUNK_FREE
);
204 zlf
->lf_type
= ZAP_CHUNK_FREE
;
205 zlf
->lf_next
= l
->l_phys
->l_hdr
.lh_freelist
;
206 bzero(zlf
->lf_pad
, sizeof (zlf
->lf_pad
)); /* help it to compress */
207 l
->l_phys
->l_hdr
.lh_freelist
= chunk
;
209 l
->l_phys
->l_hdr
.lh_nfree
++;
213 * Routines which manipulate leaf arrays (zap_leaf_array type chunks).
217 zap_leaf_array_create(zap_leaf_t
*l
, const char *buf
,
218 int integer_size
, int num_integers
)
221 uint16_t *chunkp
= &chunk_head
;
224 int shift
= (integer_size
-1)*8;
225 int len
= num_integers
;
227 ASSERT3U(num_integers
* integer_size
, <, MAX_ARRAY_BYTES
);
230 uint16_t chunk
= zap_leaf_chunk_alloc(l
);
231 struct zap_leaf_array
*la
= &ZAP_LEAF_CHUNK(l
, chunk
).l_array
;
234 la
->la_type
= ZAP_CHUNK_ARRAY
;
235 for (i
= 0; i
< ZAP_LEAF_ARRAY_BYTES
; i
++) {
237 value
= ldv(integer_size
, buf
);
238 la
->la_array
[i
] = value
>> shift
;
240 if (++byten
== integer_size
) {
249 chunkp
= &la
->la_next
;
257 zap_leaf_array_free(zap_leaf_t
*l
, uint16_t *chunkp
)
259 uint16_t chunk
= *chunkp
;
263 while (chunk
!= CHAIN_END
) {
264 int nextchunk
= ZAP_LEAF_CHUNK(l
, chunk
).l_array
.la_next
;
265 ASSERT3U(ZAP_LEAF_CHUNK(l
, chunk
).l_array
.la_type
, ==,
267 zap_leaf_chunk_free(l
, chunk
);
272 /* array_len and buf_len are in integers, not bytes */
274 zap_leaf_array_read(zap_leaf_t
*l
, uint16_t chunk
,
275 int array_int_len
, int array_len
, int buf_int_len
, uint64_t buf_len
,
278 int len
= MIN(array_len
, buf_len
);
283 ASSERT3U(array_int_len
, <=, buf_int_len
);
285 /* Fast path for one 8-byte integer */
286 if (array_int_len
== 8 && buf_int_len
== 8 && len
== 1) {
287 struct zap_leaf_array
*la
= &ZAP_LEAF_CHUNK(l
, chunk
).l_array
;
288 uint8_t *ip
= la
->la_array
;
289 uint64_t *buf64
= buf
;
291 *buf64
= (uint64_t)ip
[0] << 56 | (uint64_t)ip
[1] << 48 |
292 (uint64_t)ip
[2] << 40 | (uint64_t)ip
[3] << 32 |
293 (uint64_t)ip
[4] << 24 | (uint64_t)ip
[5] << 16 |
294 (uint64_t)ip
[6] << 8 | (uint64_t)ip
[7];
298 /* Fast path for an array of 1-byte integers (eg. the entry name) */
299 if (array_int_len
== 1 && buf_int_len
== 1 &&
300 buf_len
> array_len
+ ZAP_LEAF_ARRAY_BYTES
) {
301 while (chunk
!= CHAIN_END
) {
302 struct zap_leaf_array
*la
=
303 &ZAP_LEAF_CHUNK(l
, chunk
).l_array
;
304 bcopy(la
->la_array
, p
, ZAP_LEAF_ARRAY_BYTES
);
305 p
+= ZAP_LEAF_ARRAY_BYTES
;
312 struct zap_leaf_array
*la
= &ZAP_LEAF_CHUNK(l
, chunk
).l_array
;
315 ASSERT3U(chunk
, <, ZAP_LEAF_NUMCHUNKS(l
));
316 for (i
= 0; i
< ZAP_LEAF_ARRAY_BYTES
&& len
> 0; i
++) {
317 value
= (value
<< 8) | la
->la_array
[i
];
319 if (byten
== array_int_len
) {
320 stv(buf_int_len
, p
, value
);
333 zap_leaf_array_match(zap_leaf_t
*l
, zap_name_t
*zn
,
334 int chunk
, int array_numints
)
338 if (zap_getflags(zn
->zn_zap
) & ZAP_FLAG_UINT64_KEY
) {
342 ASSERT(zn
->zn_key_intlen
== sizeof (*thiskey
));
343 thiskey
= kmem_alloc(array_numints
* sizeof (*thiskey
),
346 zap_leaf_array_read(l
, chunk
, sizeof (*thiskey
), array_numints
,
347 sizeof (*thiskey
), array_numints
, thiskey
);
348 match
= bcmp(thiskey
, zn
->zn_key_orig
,
349 array_numints
* sizeof (*thiskey
)) == 0;
350 kmem_free(thiskey
, array_numints
* sizeof (*thiskey
));
354 ASSERT(zn
->zn_key_intlen
== 1);
355 if (zn
->zn_matchtype
== MT_FIRST
) {
356 char *thisname
= kmem_alloc(array_numints
, KM_PUSHPAGE
);
359 zap_leaf_array_read(l
, chunk
, sizeof (char), array_numints
,
360 sizeof (char), array_numints
, thisname
);
361 match
= zap_match(zn
, thisname
);
362 kmem_free(thisname
, array_numints
);
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.
371 if (array_numints
!= zn
->zn_key_orig_numints
)
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
))
382 return (bseen
== array_numints
);
386 * Routines which manipulate leaf entries.
390 zap_leaf_lookup(zap_leaf_t
*l
, zap_name_t
*zn
, zap_entry_handle_t
*zeh
)
393 struct zap_leaf_entry
*le
;
395 ASSERT3U(l
->l_phys
->l_hdr
.lh_magic
, ==, ZAP_LEAF_MAGIC
);
398 for (chunkp
= LEAF_HASH_ENTPTR(l
, zn
->zn_hash
);
399 *chunkp
!= CHAIN_END
; chunkp
= &le
->le_next
) {
400 uint16_t chunk
= *chunkp
;
401 le
= ZAP_LEAF_ENTRY(l
, chunk
);
403 ASSERT3U(chunk
, <, ZAP_LEAF_NUMCHUNKS(l
));
404 ASSERT3U(le
->le_type
, ==, ZAP_CHUNK_ENTRY
);
406 if (le
->le_hash
!= zn
->zn_hash
)
410 * NB: the entry chain is always sorted by cd on
411 * normalized zap objects, so this will find the
412 * lowest-cd match for MT_FIRST.
414 ASSERT(zn
->zn_matchtype
== MT_EXACT
||
415 (l
->l_phys
->l_hdr
.lh_flags
& ZLF_ENTRIES_CDSORTED
));
416 if (zap_leaf_array_match(l
, zn
, le
->le_name_chunk
,
417 le
->le_name_numints
)) {
418 zeh
->zeh_num_integers
= le
->le_value_numints
;
419 zeh
->zeh_integer_size
= le
->le_value_intlen
;
420 zeh
->zeh_cd
= le
->le_cd
;
421 zeh
->zeh_hash
= le
->le_hash
;
422 zeh
->zeh_chunkp
= chunkp
;
429 * NB: we could of course do this in one pass, but that would be
430 * a pain. We'll see if MT_BEST is even used much.
432 if (zn
->zn_matchtype
== MT_BEST
) {
433 zn
->zn_matchtype
= MT_FIRST
;
440 /* Return (h1,cd1 >= h2,cd2) */
441 #define HCD_GTEQ(h1, cd1, h2, cd2) \
442 ((h1 > h2) ? TRUE : ((h1 == h2 && cd1 >= cd2) ? TRUE : FALSE))
445 zap_leaf_lookup_closest(zap_leaf_t
*l
,
446 uint64_t h
, uint32_t cd
, zap_entry_handle_t
*zeh
)
449 uint64_t besth
= -1ULL;
450 uint32_t bestcd
= -1U;
451 uint16_t bestlh
= ZAP_LEAF_HASH_NUMENTRIES(l
)-1;
453 struct zap_leaf_entry
*le
;
455 ASSERT3U(l
->l_phys
->l_hdr
.lh_magic
, ==, ZAP_LEAF_MAGIC
);
457 for (lh
= LEAF_HASH(l
, h
); lh
<= bestlh
; lh
++) {
458 for (chunk
= l
->l_phys
->l_hash
[lh
];
459 chunk
!= CHAIN_END
; chunk
= le
->le_next
) {
460 le
= ZAP_LEAF_ENTRY(l
, chunk
);
462 ASSERT3U(chunk
, <, ZAP_LEAF_NUMCHUNKS(l
));
463 ASSERT3U(le
->le_type
, ==, ZAP_CHUNK_ENTRY
);
465 if (HCD_GTEQ(le
->le_hash
, le
->le_cd
, h
, cd
) &&
466 HCD_GTEQ(besth
, bestcd
, le
->le_hash
, le
->le_cd
)) {
467 ASSERT3U(bestlh
, >=, lh
);
472 zeh
->zeh_num_integers
= le
->le_value_numints
;
473 zeh
->zeh_integer_size
= le
->le_value_intlen
;
474 zeh
->zeh_cd
= le
->le_cd
;
475 zeh
->zeh_hash
= le
->le_hash
;
476 zeh
->zeh_fakechunk
= chunk
;
477 zeh
->zeh_chunkp
= &zeh
->zeh_fakechunk
;
483 return (bestcd
== -1U ? ENOENT
: 0);
487 zap_entry_read(const zap_entry_handle_t
*zeh
,
488 uint8_t integer_size
, uint64_t num_integers
, void *buf
)
490 struct zap_leaf_entry
*le
=
491 ZAP_LEAF_ENTRY(zeh
->zeh_leaf
, *zeh
->zeh_chunkp
);
492 ASSERT3U(le
->le_type
, ==, ZAP_CHUNK_ENTRY
);
494 if (le
->le_value_intlen
> integer_size
)
497 zap_leaf_array_read(zeh
->zeh_leaf
, le
->le_value_chunk
,
498 le
->le_value_intlen
, le
->le_value_numints
,
499 integer_size
, num_integers
, buf
);
501 if (zeh
->zeh_num_integers
> num_integers
)
508 zap_entry_read_name(zap_t
*zap
, const zap_entry_handle_t
*zeh
, uint16_t buflen
,
511 struct zap_leaf_entry
*le
=
512 ZAP_LEAF_ENTRY(zeh
->zeh_leaf
, *zeh
->zeh_chunkp
);
513 ASSERT3U(le
->le_type
, ==, ZAP_CHUNK_ENTRY
);
515 if (zap_getflags(zap
) & ZAP_FLAG_UINT64_KEY
) {
516 zap_leaf_array_read(zeh
->zeh_leaf
, le
->le_name_chunk
, 8,
517 le
->le_name_numints
, 8, buflen
/ 8, buf
);
519 zap_leaf_array_read(zeh
->zeh_leaf
, le
->le_name_chunk
, 1,
520 le
->le_name_numints
, 1, buflen
, buf
);
522 if (le
->le_name_numints
> buflen
)
528 zap_entry_update(zap_entry_handle_t
*zeh
,
529 uint8_t integer_size
, uint64_t num_integers
, const void *buf
)
532 zap_leaf_t
*l
= zeh
->zeh_leaf
;
533 struct zap_leaf_entry
*le
= ZAP_LEAF_ENTRY(l
, *zeh
->zeh_chunkp
);
535 delta_chunks
= ZAP_LEAF_ARRAY_NCHUNKS(num_integers
* integer_size
) -
536 ZAP_LEAF_ARRAY_NCHUNKS(le
->le_value_numints
* le
->le_value_intlen
);
538 if ((int)l
->l_phys
->l_hdr
.lh_nfree
< delta_chunks
)
541 zap_leaf_array_free(l
, &le
->le_value_chunk
);
543 zap_leaf_array_create(l
, buf
, integer_size
, num_integers
);
544 le
->le_value_numints
= num_integers
;
545 le
->le_value_intlen
= integer_size
;
550 zap_entry_remove(zap_entry_handle_t
*zeh
)
552 uint16_t entry_chunk
;
553 struct zap_leaf_entry
*le
;
554 zap_leaf_t
*l
= zeh
->zeh_leaf
;
556 ASSERT3P(zeh
->zeh_chunkp
, !=, &zeh
->zeh_fakechunk
);
558 entry_chunk
= *zeh
->zeh_chunkp
;
559 le
= ZAP_LEAF_ENTRY(l
, entry_chunk
);
560 ASSERT3U(le
->le_type
, ==, ZAP_CHUNK_ENTRY
);
562 zap_leaf_array_free(l
, &le
->le_name_chunk
);
563 zap_leaf_array_free(l
, &le
->le_value_chunk
);
565 *zeh
->zeh_chunkp
= le
->le_next
;
566 zap_leaf_chunk_free(l
, entry_chunk
);
568 l
->l_phys
->l_hdr
.lh_nentries
--;
572 zap_entry_create(zap_leaf_t
*l
, zap_name_t
*zn
, uint32_t cd
,
573 uint8_t integer_size
, uint64_t num_integers
, const void *buf
,
574 zap_entry_handle_t
*zeh
)
578 struct zap_leaf_entry
*le
;
581 uint64_t h
= zn
->zn_hash
;
583 valuelen
= integer_size
* num_integers
;
585 numchunks
= 1 + ZAP_LEAF_ARRAY_NCHUNKS(zn
->zn_key_orig_numints
*
586 zn
->zn_key_intlen
) + ZAP_LEAF_ARRAY_NCHUNKS(valuelen
);
587 if (numchunks
> ZAP_LEAF_NUMCHUNKS(l
))
590 if (cd
== ZAP_NEED_CD
) {
591 /* find the lowest unused cd */
592 if (l
->l_phys
->l_hdr
.lh_flags
& ZLF_ENTRIES_CDSORTED
) {
595 for (chunk
= *LEAF_HASH_ENTPTR(l
, h
);
596 chunk
!= CHAIN_END
; chunk
= le
->le_next
) {
597 le
= ZAP_LEAF_ENTRY(l
, chunk
);
600 if (le
->le_hash
== h
) {
601 ASSERT3U(cd
, ==, le
->le_cd
);
606 /* old unsorted format; do it the O(n^2) way */
607 for (cd
= 0; ; cd
++) {
608 for (chunk
= *LEAF_HASH_ENTPTR(l
, h
);
609 chunk
!= CHAIN_END
; chunk
= le
->le_next
) {
610 le
= ZAP_LEAF_ENTRY(l
, chunk
);
611 if (le
->le_hash
== h
&&
616 /* If this cd is not in use, we are good. */
617 if (chunk
== CHAIN_END
)
622 * We would run out of space in a block before we could
623 * store enough entries to run out of CD values.
625 ASSERT3U(cd
, <, zap_maxcd(zn
->zn_zap
));
628 if (l
->l_phys
->l_hdr
.lh_nfree
< numchunks
)
632 chunk
= zap_leaf_chunk_alloc(l
);
633 le
= ZAP_LEAF_ENTRY(l
, chunk
);
634 le
->le_type
= ZAP_CHUNK_ENTRY
;
635 le
->le_name_chunk
= zap_leaf_array_create(l
, zn
->zn_key_orig
,
636 zn
->zn_key_intlen
, zn
->zn_key_orig_numints
);
637 le
->le_name_numints
= zn
->zn_key_orig_numints
;
639 zap_leaf_array_create(l
, buf
, integer_size
, num_integers
);
640 le
->le_value_numints
= num_integers
;
641 le
->le_value_intlen
= integer_size
;
645 /* link it into the hash chain */
646 /* XXX if we did the search above, we could just use that */
647 chunkp
= zap_leaf_rehash_entry(l
, chunk
);
649 l
->l_phys
->l_hdr
.lh_nentries
++;
652 zeh
->zeh_num_integers
= num_integers
;
653 zeh
->zeh_integer_size
= le
->le_value_intlen
;
654 zeh
->zeh_cd
= le
->le_cd
;
655 zeh
->zeh_hash
= le
->le_hash
;
656 zeh
->zeh_chunkp
= chunkp
;
662 * Determine if there is another entry with the same normalized form.
663 * For performance purposes, either zn or name must be provided (the
664 * other can be NULL). Note, there usually won't be any hash
665 * conflicts, in which case we don't need the concatenated/normalized
666 * form of the name. But all callers have one of these on hand anyway,
667 * so might as well take advantage. A cleaner but slower interface
668 * would accept neither argument, and compute the normalized name as
669 * needed (using zap_name_alloc(zap_entry_read_name(zeh))).
672 zap_entry_normalization_conflict(zap_entry_handle_t
*zeh
, zap_name_t
*zn
,
673 const char *name
, zap_t
*zap
)
676 struct zap_leaf_entry
*le
;
677 boolean_t allocdzn
= B_FALSE
;
679 if (zap
->zap_normflags
== 0)
682 for (chunk
= *LEAF_HASH_ENTPTR(zeh
->zeh_leaf
, zeh
->zeh_hash
);
683 chunk
!= CHAIN_END
; chunk
= le
->le_next
) {
684 le
= ZAP_LEAF_ENTRY(zeh
->zeh_leaf
, chunk
);
685 if (le
->le_hash
!= zeh
->zeh_hash
)
687 if (le
->le_cd
== zeh
->zeh_cd
)
691 zn
= zap_name_alloc(zap
, name
, MT_FIRST
);
694 if (zap_leaf_array_match(zeh
->zeh_leaf
, zn
,
695 le
->le_name_chunk
, le
->le_name_numints
)) {
707 * Routines for transferring entries between leafs.
711 zap_leaf_rehash_entry(zap_leaf_t
*l
, uint16_t entry
)
713 struct zap_leaf_entry
*le
= ZAP_LEAF_ENTRY(l
, entry
);
714 struct zap_leaf_entry
*le2
;
718 * keep the entry chain sorted by cd
719 * NB: this will not cause problems for unsorted leafs, though
720 * it is unnecessary there.
722 for (chunkp
= LEAF_HASH_ENTPTR(l
, le
->le_hash
);
723 *chunkp
!= CHAIN_END
; chunkp
= &le2
->le_next
) {
724 le2
= ZAP_LEAF_ENTRY(l
, *chunkp
);
725 if (le2
->le_cd
> le
->le_cd
)
729 le
->le_next
= *chunkp
;
735 zap_leaf_transfer_array(zap_leaf_t
*l
, uint16_t chunk
, zap_leaf_t
*nl
)
738 uint16_t *nchunkp
= &new_chunk
;
740 while (chunk
!= CHAIN_END
) {
741 uint16_t nchunk
= zap_leaf_chunk_alloc(nl
);
742 struct zap_leaf_array
*nla
=
743 &ZAP_LEAF_CHUNK(nl
, nchunk
).l_array
;
744 struct zap_leaf_array
*la
=
745 &ZAP_LEAF_CHUNK(l
, chunk
).l_array
;
746 int nextchunk
= la
->la_next
;
748 ASSERT3U(chunk
, <, ZAP_LEAF_NUMCHUNKS(l
));
749 ASSERT3U(nchunk
, <, ZAP_LEAF_NUMCHUNKS(l
));
751 *nla
= *la
; /* structure assignment */
753 zap_leaf_chunk_free(l
, chunk
);
756 nchunkp
= &nla
->la_next
;
758 *nchunkp
= CHAIN_END
;
763 zap_leaf_transfer_entry(zap_leaf_t
*l
, int entry
, zap_leaf_t
*nl
)
765 struct zap_leaf_entry
*le
, *nle
;
768 le
= ZAP_LEAF_ENTRY(l
, entry
);
769 ASSERT3U(le
->le_type
, ==, ZAP_CHUNK_ENTRY
);
771 chunk
= zap_leaf_chunk_alloc(nl
);
772 nle
= ZAP_LEAF_ENTRY(nl
, chunk
);
773 *nle
= *le
; /* structure assignment */
775 (void) zap_leaf_rehash_entry(nl
, chunk
);
777 nle
->le_name_chunk
= zap_leaf_transfer_array(l
, le
->le_name_chunk
, nl
);
778 nle
->le_value_chunk
=
779 zap_leaf_transfer_array(l
, le
->le_value_chunk
, nl
);
781 zap_leaf_chunk_free(l
, entry
);
783 l
->l_phys
->l_hdr
.lh_nentries
--;
784 nl
->l_phys
->l_hdr
.lh_nentries
++;
788 * Transfer the entries whose hash prefix ends in 1 to the new leaf.
791 zap_leaf_split(zap_leaf_t
*l
, zap_leaf_t
*nl
, boolean_t sort
)
794 int bit
= 64 - 1 - l
->l_phys
->l_hdr
.lh_prefix_len
;
796 /* set new prefix and prefix_len */
797 l
->l_phys
->l_hdr
.lh_prefix
<<= 1;
798 l
->l_phys
->l_hdr
.lh_prefix_len
++;
799 nl
->l_phys
->l_hdr
.lh_prefix
= l
->l_phys
->l_hdr
.lh_prefix
| 1;
800 nl
->l_phys
->l_hdr
.lh_prefix_len
= l
->l_phys
->l_hdr
.lh_prefix_len
;
802 /* break existing hash chains */
803 zap_memset(l
->l_phys
->l_hash
, CHAIN_END
, 2*ZAP_LEAF_HASH_NUMENTRIES(l
));
806 l
->l_phys
->l_hdr
.lh_flags
|= ZLF_ENTRIES_CDSORTED
;
809 * Transfer entries whose hash bit 'bit' is set to nl; rehash
810 * the remaining entries
812 * NB: We could find entries via the hashtable instead. That
813 * would be O(hashents+numents) rather than O(numblks+numents),
814 * but this accesses memory more sequentially, and when we're
815 * called, the block is usually pretty full.
817 for (i
= 0; i
< ZAP_LEAF_NUMCHUNKS(l
); i
++) {
818 struct zap_leaf_entry
*le
= ZAP_LEAF_ENTRY(l
, i
);
819 if (le
->le_type
!= ZAP_CHUNK_ENTRY
)
822 if (le
->le_hash
& (1ULL << bit
))
823 zap_leaf_transfer_entry(l
, i
, nl
);
825 (void) zap_leaf_rehash_entry(l
, i
);
830 zap_leaf_stats(zap_t
*zap
, zap_leaf_t
*l
, zap_stats_t
*zs
)
834 n
= zap
->zap_f
.zap_phys
->zap_ptrtbl
.zt_shift
-
835 l
->l_phys
->l_hdr
.lh_prefix_len
;
836 n
= MIN(n
, ZAP_HISTOGRAM_SIZE
-1);
837 zs
->zs_leafs_with_2n_pointers
[n
]++;
840 n
= l
->l_phys
->l_hdr
.lh_nentries
/5;
841 n
= MIN(n
, ZAP_HISTOGRAM_SIZE
-1);
842 zs
->zs_blocks_with_n5_entries
[n
]++;
844 n
= ((1<<FZAP_BLOCK_SHIFT(zap
)) -
845 l
->l_phys
->l_hdr
.lh_nfree
* (ZAP_LEAF_ARRAY_BYTES
+1))*10 /
846 (1<<FZAP_BLOCK_SHIFT(zap
));
847 n
= MIN(n
, ZAP_HISTOGRAM_SIZE
-1);
848 zs
->zs_blocks_n_tenths_full
[n
]++;
850 for (i
= 0; i
< ZAP_LEAF_HASH_NUMENTRIES(l
); i
++) {
852 int chunk
= l
->l_phys
->l_hash
[i
];
854 while (chunk
!= CHAIN_END
) {
855 struct zap_leaf_entry
*le
=
856 ZAP_LEAF_ENTRY(l
, chunk
);
858 n
= 1 + ZAP_LEAF_ARRAY_NCHUNKS(le
->le_name_numints
) +
859 ZAP_LEAF_ARRAY_NCHUNKS(le
->le_value_numints
*
860 le
->le_value_intlen
);
861 n
= MIN(n
, ZAP_HISTOGRAM_SIZE
-1);
862 zs
->zs_entries_using_n_chunks
[n
]++;
869 n
= MIN(n
, ZAP_HISTOGRAM_SIZE
-1);
870 zs
->zs_buckets_with_n_entries
[n
]++;