]> git.proxmox.com Git - mirror_zfs-debian.git/blob - module/zfs/zap_leaf.c
projects / mirror_zfs-debian.git / blob
? search:
summary | shortlog | log | commit | commitdiff | tree
blame | history | raw | HEAD
Switch KM_SLEEP to KM_PUSHPAGE
[mirror_zfs-debian.git] / module / zfs / zap_leaf.c
1 /*
2 * CDDL HEADER START
3 *
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.
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 /*
22 * Copyright (c) 2005, 2010, Oracle and/or its affiliates. All rights reserved.
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
31 #include <sys/zio.h>
32 #include <sys/spa.h>
33 #include <sys/dmu.h>
34 #include <sys/zfs_context.h>
35 #include <sys/fs/zfs.h>
36 #include <sys/zap.h>
37 #include <sys/zap_impl.h>
38 #include <sys/zap_leaf.h>
39 #include <sys/arc.h>
40
41 static uint16_t *zap_leaf_rehash_entry(zap_leaf_t *l, uint16_t entry);
42
43 #define CHAIN_END 0xffff /* end of the chunk chain */
44
45 /* half the (current) minimum block size */
46 #define MAX_ARRAY_BYTES (8<<10)
47
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)))
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");
99 return (0xFEEDFACEDEADBEEFULL);
100 }
101
102 void
103 zap_leaf_byteswap(zap_leaf_phys_t *buf, int size)
104 {
105 int i;
106 zap_leaf_t l;
107 l.l_bs = highbit(size)-1;
108 l.l_phys = buf;
109
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);
117
118 for (i = 0; i < ZAP_LEAF_HASH_NUMENTRIES(&l); i++)
119 buf->l_hash[i] = BSWAP_16(buf->l_hash[i]);
120
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;
124
125 switch (lc->l_free.lf_type) {
126 case ZAP_CHUNK_ENTRY:
127 le = &lc->l_entry;
128
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);
138 break;
139 case ZAP_CHUNK_FREE:
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);
142 break;
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 */
147 break;
148 default:
149 ASSERT(!"bad leaf type");
150 }
151 }
152 }
153
154 void
155 zap_leaf_init(zap_leaf_t *l, boolean_t sort)
156 {
157 int i;
158
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;
165 }
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);
170 if (sort)
171 l->l_phys->l_hdr.lh_flags |= ZLF_ENTRIES_CDSORTED;
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
183 ASSERT(l->l_phys->l_hdr.lh_nfree > 0);
184
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);
188
189 l->l_phys->l_hdr.lh_freelist = ZAP_LEAF_CHUNK(l, chunk).l_free.lf_next;
190
191 l->l_phys->l_hdr.lh_nfree--;
192
193 return (chunk);
194 }
195
196 static void
197 zap_leaf_chunk_free(zap_leaf_t *l, uint16_t chunk)
198 {
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);
203
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;
208
209 l->l_phys->l_hdr.lh_nfree++;
210 }
211
212 /*
213 * Routines which manipulate leaf arrays (zap_leaf_array type chunks).
214 */
215
216 static uint16_t
217 zap_leaf_array_create(zap_leaf_t *l, const char *buf,
218 int integer_size, int num_integers)
219 {
220 uint16_t chunk_head;
221 uint16_t *chunkp = &chunk_head;
222 int byten = 0;
223 uint64_t value = 0;
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);
231 struct zap_leaf_array *la = &ZAP_LEAF_CHUNK(l, chunk).l_array;
232 int i;
233
234 la->la_type = ZAP_CHUNK_ARRAY;
235 for (i = 0; i < ZAP_LEAF_ARRAY_BYTES; i++) {
236 if (byten == 0)
237 value = ldv(integer_size, buf);
238 la->la_array[i] = value >> shift;
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
257 zap_leaf_array_free(zap_leaf_t *l, uint16_t *chunkp)
258 {
259 uint16_t chunk = *chunkp;
260
261 *chunkp = CHAIN_END;
262
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, ==,
266 ZAP_CHUNK_ARRAY);
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
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,
276 void *buf)
277 {
278 int len = MIN(array_len, buf_len);
279 int byten = 0;
280 uint64_t value = 0;
281 char *p = buf;
282
283 ASSERT3U(array_int_len, <=, buf_int_len);
284
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;
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];
295 return;
296 }
297
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;
306 chunk = la->la_next;
307 }
308 return;
309 }
310
311 while (len > 0) {
312 struct zap_leaf_array *la = &ZAP_LEAF_CHUNK(l, chunk).l_array;
313 int i;
314
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];
318 byten++;
319 if (byten == array_int_len) {
320 stv(buf_int_len, p, value);
321 byten = 0;
322 len--;
323 if (len == 0)
324 return;
325 p += buf_int_len;
326 }
327 }
328 chunk = la->la_next;
329 }
330 }
331
332 static boolean_t
333 zap_leaf_array_match(zap_leaf_t *l, zap_name_t *zn,
334 int chunk, int array_numints)
335 {
336 int bseen = 0;
337
338 if (zap_getflags(zn->zn_zap) & ZAP_FLAG_UINT64_KEY) {
339 uint64_t *thiskey;
340 boolean_t match;
341
342 ASSERT(zn->zn_key_intlen == sizeof (*thiskey));
343 thiskey = kmem_alloc(array_numints * sizeof (*thiskey),
344 KM_PUSHPAGE);
345
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));
351 return (match);
352 }
353
354 ASSERT(zn->zn_key_intlen == 1);
355 if (zn->zn_matchtype == MT_FIRST) {
356 char *thisname = kmem_alloc(array_numints, KM_PUSHPAGE);
357 boolean_t match;
358
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);
363 return (match);
364 }
365
366 /*
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.
370 */
371 if (array_numints != zn->zn_key_orig_numints)
372 return (B_FALSE);
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))
378 break;
379 chunk = la->la_next;
380 bseen += toread;
381 }
382 return (bseen == array_numints);
383 }
384
385 /*
386 * Routines which manipulate leaf entries.
387 */
388
389 int
390 zap_leaf_lookup(zap_leaf_t *l, zap_name_t *zn, zap_entry_handle_t *zeh)
391 {
392 uint16_t *chunkp;
393 struct zap_leaf_entry *le;
394
395 ASSERT3U(l->l_phys->l_hdr.lh_magic, ==, ZAP_LEAF_MAGIC);
396
397 again:
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);
402
403 ASSERT3U(chunk, <, ZAP_LEAF_NUMCHUNKS(l));
404 ASSERT3U(le->le_type, ==, ZAP_CHUNK_ENTRY);
405
406 if (le->le_hash != zn->zn_hash)
407 continue;
408
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,
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;
423 zeh->zeh_leaf = l;
424 return (0);
425 }
426 }
427
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
437 return (ENOENT);
438 }
439
440 /* Return (h1,cd1 >= h2,cd2) */
441 #define HCD_GTEQ(h1, cd1, h2, cd2) \
442 ((h1 > h2) ? TRUE : ((h1 == h2 && cd1 >= cd2) ? TRUE : FALSE))
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;
450 uint32_t bestcd = -1U;
451 uint16_t bestlh = ZAP_LEAF_HASH_NUMENTRIES(l)-1;
452 uint16_t lh;
453 struct zap_leaf_entry *le;
454
455 ASSERT3U(l->l_phys->l_hdr.lh_magic, ==, ZAP_LEAF_MAGIC);
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) {
460 le = ZAP_LEAF_ENTRY(l, chunk);
461
462 ASSERT3U(chunk, <, ZAP_LEAF_NUMCHUNKS(l));
463 ASSERT3U(le->le_type, ==, ZAP_CHUNK_ENTRY);
464
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);
468 bestlh = lh;
469 besth = le->le_hash;
470 bestcd = le->le_cd;
471
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;
478 zeh->zeh_leaf = l;
479 }
480 }
481 }
482
483 return (bestcd == -1U ? ENOENT : 0);
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 {
490 struct zap_leaf_entry *le =
491 ZAP_LEAF_ENTRY(zeh->zeh_leaf, *zeh->zeh_chunkp);
492 ASSERT3U(le->le_type, ==, ZAP_CHUNK_ENTRY);
493
494 if (le->le_value_intlen > integer_size)
495 return (EINVAL);
496
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);
500
501 if (zeh->zeh_num_integers > num_integers)
502 return (EOVERFLOW);
503 return (0);
504
505 }
506
507 int
508 zap_entry_read_name(zap_t *zap, const zap_entry_handle_t *zeh, uint16_t buflen,
509 char *buf)
510 {
511 struct zap_leaf_entry *le =
512 ZAP_LEAF_ENTRY(zeh->zeh_leaf, *zeh->zeh_chunkp);
513 ASSERT3U(le->le_type, ==, ZAP_CHUNK_ENTRY);
514
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);
518 } else {
519 zap_leaf_array_read(zeh->zeh_leaf, le->le_name_chunk, 1,
520 le->le_name_numints, 1, buflen, buf);
521 }
522 if (le->le_name_numints > buflen)
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;
532 zap_leaf_t *l = zeh->zeh_leaf;
533 struct zap_leaf_entry *le = ZAP_LEAF_ENTRY(l, *zeh->zeh_chunkp);
534
535 delta_chunks = ZAP_LEAF_ARRAY_NCHUNKS(num_integers * integer_size) -
536 ZAP_LEAF_ARRAY_NCHUNKS(le->le_value_numints * le->le_value_intlen);
537
538 if ((int)l->l_phys->l_hdr.lh_nfree < delta_chunks)
539 return (EAGAIN);
540
541 zap_leaf_array_free(l, &le->le_value_chunk);
542 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;
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;
554 zap_leaf_t *l = zeh->zeh_leaf;
555
556 ASSERT3P(zeh->zeh_chunkp, !=, &zeh->zeh_fakechunk);
557
558 entry_chunk = *zeh->zeh_chunkp;
559 le = ZAP_LEAF_ENTRY(l, entry_chunk);
560 ASSERT3U(le->le_type, ==, ZAP_CHUNK_ENTRY);
561
562 zap_leaf_array_free(l, &le->le_name_chunk);
563 zap_leaf_array_free(l, &le->le_value_chunk);
564
565 *zeh->zeh_chunkp = le->le_next;
566 zap_leaf_chunk_free(l, entry_chunk);
567
568 l->l_phys->l_hdr.lh_nentries--;
569 }
570
571 int
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)
575 {
576 uint16_t chunk;
577 uint16_t *chunkp;
578 struct zap_leaf_entry *le;
579 uint64_t valuelen;
580 int numchunks;
581 uint64_t h = zn->zn_hash;
582
583 valuelen = integer_size * num_integers;
584
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))
588 return (E2BIG);
589
590 if (cd == ZAP_NEED_CD) {
591 /* find the lowest unused cd */
592 if (l->l_phys->l_hdr.lh_flags & ZLF_ENTRIES_CDSORTED) {
593 cd = 0;
594
595 for (chunk = *LEAF_HASH_ENTPTR(l, h);
596 chunk != CHAIN_END; chunk = le->le_next) {
597 le = ZAP_LEAF_ENTRY(l, chunk);
598 if (le->le_cd > cd)
599 break;
600 if (le->le_hash == h) {
601 ASSERT3U(cd, ==, le->le_cd);
602 cd++;
603 }
604 }
605 } else {
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 &&
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 }
620 }
621 /*
622 * We would run out of space in a block before we could
623 * store enough entries to run out of CD values.
624 */
625 ASSERT3U(cd, <, zap_maxcd(zn->zn_zap));
626 }
627
628 if (l->l_phys->l_hdr.lh_nfree < numchunks)
629 return (EAGAIN);
630
631 /* make the entry */
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;
638 le->le_value_chunk =
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;
642 le->le_hash = h;
643 le->le_cd = cd;
644
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);
648
649 l->l_phys->l_hdr.lh_nentries++;
650
651 zeh->zeh_leaf = l;
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;
657
658 return (0);
659 }
660
661 /*
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,
695 le->le_name_chunk, le->le_name_numints)) {
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 /*
707 * Routines for transferring entries between leafs.
708 */
709
710 static uint16_t *
711 zap_leaf_rehash_entry(zap_leaf_t *l, uint16_t entry)
712 {
713 struct zap_leaf_entry *le = ZAP_LEAF_ENTRY(l, entry);
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);
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 =
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;
747
748 ASSERT3U(chunk, <, ZAP_LEAF_NUMCHUNKS(l));
749 ASSERT3U(nchunk, <, ZAP_LEAF_NUMCHUNKS(l));
750
751 *nla = *la; /* structure assignment */
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
763 zap_leaf_transfer_entry(zap_leaf_t *l, int entry, zap_leaf_t *nl)
764 {
765 struct zap_leaf_entry *le, *nle;
766 uint16_t chunk;
767
768 le = ZAP_LEAF_ENTRY(l, entry);
769 ASSERT3U(le->le_type, ==, ZAP_CHUNK_ENTRY);
770
771 chunk = zap_leaf_chunk_alloc(nl);
772 nle = ZAP_LEAF_ENTRY(nl, chunk);
773 *nle = *le; /* structure assignment */
774
775 (void) zap_leaf_rehash_entry(nl, chunk);
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
783 l->l_phys->l_hdr.lh_nentries--;
784 nl->l_phys->l_hdr.lh_nentries++;
785 }
786
787 /*
788 * Transfer the entries whose hash prefix ends in 1 to the new leaf.
789 */
790 void
791 zap_leaf_split(zap_leaf_t *l, zap_leaf_t *nl, boolean_t sort)
792 {
793 int i;
794 int bit = 64 - 1 - l->l_phys->l_hdr.lh_prefix_len;
795
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;
801
802 /* break existing hash chains */
803 zap_memset(l->l_phys->l_hash, CHAIN_END, 2*ZAP_LEAF_HASH_NUMENTRIES(l));
804
805 if (sort)
806 l->l_phys->l_hdr.lh_flags |= ZLF_ENTRIES_CDSORTED;
807
808 /*
809 * Transfer entries whose hash bit 'bit' is set to nl; rehash
810 * the remaining entries
811 *
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.
816 */
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)
820 continue;
821
822 if (le->le_hash & (1ULL << bit))
823 zap_leaf_transfer_entry(l, i, nl);
824 else
825 (void) zap_leaf_rehash_entry(l, i);
826 }
827 }
828
829 void
830 zap_leaf_stats(zap_t *zap, zap_leaf_t *l, zap_stats_t *zs)
831 {
832 int i, n;
833
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]++;
838
839
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]++;
843
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]++;
849
850 for (i = 0; i < ZAP_LEAF_HASH_NUMENTRIES(l); i++) {
851 int nentries = 0;
852 int chunk = l->l_phys->l_hash[i];
853
854 while (chunk != CHAIN_END) {
855 struct zap_leaf_entry *le =
856 ZAP_LEAF_ENTRY(l, chunk);
857
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]++;
863
864 chunk = le->le_next;
865 nentries++;
866 }
867
868 n = nentries;
869 n = MIN(n, ZAP_HISTOGRAM_SIZE-1);
870 zs->zs_buckets_with_n_entries[n]++;
871 }
872 }
Mirror of ZFSOnLinux for Debian