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