Print this page
NEX-3562 filename normalization doesn't work for removes (sync with upstream)
6328 Fix cstyle errors in zfs codebase (fix studio)
6328 Fix cstyle errors in zfs codebase
Reviewed by: Matthew Ahrens <mahrens@delphix.com>
Reviewed by: Alex Reece <alex@delphix.com>
Reviewed by: Richard Elling <Richard.Elling@RichardElling.com>
Reviewed by: Jorgen Lundman <lundman@lundman.net>
Approved by: Robert Mustacchi <rm@joyent.com>
NEX-3329 libnsl: set_up_connection() over TCP does not adhere the specified timeout
Reviewed by: Dan Fields <dan.fields@nexenta.com>
NEX-3521 CLONE - Port NEX-3209 normalization=formD and casesensitivity=mixed behaves improperly, squashing case
Reviewed by: Jean McCormack <jean.mccormack@nexenta.com>
Reviewed by: Saso Kiselkov <saso.kiselkov@nexenta.com>
Reviewed by: Dan Fields <dan.fields@nexenta.com>
NEX-3591 SMB3 signing (hdrchk)
NEX-3719 CLONE - Port NEX-3517 Eliminate the unused MT_BEST code to simplify normalization & case.
Reviewed by: Jean McCormack <jean.mccormack@nexenta.com>
Reviewed by: Josef 'Jeff' Sipek <josef.sipek@nexenta.com>
Remaining fixes for the illumos merge
| Split |
Close |
| Expand all |
| Collapse all |
--- old/usr/src/uts/common/fs/zfs/zap_leaf.c
+++ new/usr/src/uts/common/fs/zfs/zap_leaf.c
1 1 /*
2 2 * CDDL HEADER START
3 3 *
4 4 * The contents of this file are subject to the terms of the
5 5 * Common Development and Distribution License (the "License").
6 6 * You may not use this file except in compliance with the License.
7 7 *
8 8 * You can obtain a copy of the license at usr/src/OPENSOLARIS.LICENSE
9 9 * or http://www.opensolaris.org/os/licensing.
10 10 * See the License for the specific language governing permissions
11 11 * and limitations under the License.
12 12 *
13 13 * When distributing Covered Code, include this CDDL HEADER in each
14 14 * file and include the License file at usr/src/OPENSOLARIS.LICENSE.
15 15 * If applicable, add the following below this CDDL HEADER, with the
16 16 * fields enclosed by brackets "[]" replaced with your own identifying
17 17 * information: Portions Copyright [yyyy] [name of copyright owner]
18 18 *
19 19 * CDDL HEADER END
20 20 */
21 21
22 22 /*
23 23 * Copyright (c) 2005, 2010, Oracle and/or its affiliates. All rights reserved.
24 24 * Copyright (c) 2013, 2015 by Delphix. All rights reserved.
25 25 * Copyright 2017 Nexenta Systems, Inc.
26 26 */
27 27
28 28 /*
29 29 * The 512-byte leaf is broken into 32 16-byte chunks.
30 30 * chunk number n means l_chunk[n], even though the header precedes it.
31 31 * the names are stored null-terminated.
32 32 */
33 33
34 34 #include <sys/zio.h>
35 35 #include <sys/spa.h>
36 36 #include <sys/dmu.h>
37 37 #include <sys/zfs_context.h>
38 38 #include <sys/fs/zfs.h>
39 39 #include <sys/zap.h>
40 40 #include <sys/zap_impl.h>
41 41 #include <sys/zap_leaf.h>
42 42 #include <sys/arc.h>
43 43
44 44 static uint16_t *zap_leaf_rehash_entry(zap_leaf_t *l, uint16_t entry);
45 45
46 46 #define CHAIN_END 0xffff /* end of the chunk chain */
47 47
48 48 /* half the (current) minimum block size */
49 49 #define MAX_ARRAY_BYTES (8<<10)
50 50
51 51 #define LEAF_HASH(l, h) \
52 52 ((ZAP_LEAF_HASH_NUMENTRIES(l)-1) & \
53 53 ((h) >> \
54 54 (64 - ZAP_LEAF_HASH_SHIFT(l) - zap_leaf_phys(l)->l_hdr.lh_prefix_len)))
55 55
56 56 #define LEAF_HASH_ENTPTR(l, h) (&zap_leaf_phys(l)->l_hash[LEAF_HASH(l, h)])
57 57
58 58 extern inline zap_leaf_phys_t *zap_leaf_phys(zap_leaf_t *l);
59 59
60 60 static void
61 61 zap_memset(void *a, int c, size_t n)
62 62 {
63 63 char *cp = a;
64 64 char *cpend = cp + n;
65 65
66 66 while (cp < cpend)
67 67 *cp++ = c;
68 68 }
69 69
70 70 static void
71 71 stv(int len, void *addr, uint64_t value)
72 72 {
73 73 switch (len) {
74 74 case 1:
75 75 *(uint8_t *)addr = value;
76 76 return;
77 77 case 2:
78 78 *(uint16_t *)addr = value;
79 79 return;
80 80 case 4:
81 81 *(uint32_t *)addr = value;
82 82 return;
83 83 case 8:
84 84 *(uint64_t *)addr = value;
85 85 return;
86 86 }
87 87 ASSERT(!"bad int len");
88 88 }
89 89
90 90 static uint64_t
91 91 ldv(int len, const void *addr)
92 92 {
93 93 switch (len) {
94 94 case 1:
95 95 return (*(uint8_t *)addr);
96 96 case 2:
97 97 return (*(uint16_t *)addr);
98 98 case 4:
99 99 return (*(uint32_t *)addr);
100 100 case 8:
101 101 return (*(uint64_t *)addr);
102 102 }
103 103 ASSERT(!"bad int len");
104 104 return (0xFEEDFACEDEADBEEFULL);
105 105 }
106 106
107 107 void
108 108 zap_leaf_byteswap(zap_leaf_phys_t *buf, int size)
109 109 {
110 110 int i;
111 111 zap_leaf_t l;
112 112 dmu_buf_t l_dbuf;
113 113
114 114 l_dbuf.db_data = buf;
115 115 l.l_bs = highbit64(size) - 1;
116 116 l.l_dbuf = &l_dbuf;
117 117
118 118 buf->l_hdr.lh_block_type = BSWAP_64(buf->l_hdr.lh_block_type);
119 119 buf->l_hdr.lh_prefix = BSWAP_64(buf->l_hdr.lh_prefix);
120 120 buf->l_hdr.lh_magic = BSWAP_32(buf->l_hdr.lh_magic);
121 121 buf->l_hdr.lh_nfree = BSWAP_16(buf->l_hdr.lh_nfree);
122 122 buf->l_hdr.lh_nentries = BSWAP_16(buf->l_hdr.lh_nentries);
123 123 buf->l_hdr.lh_prefix_len = BSWAP_16(buf->l_hdr.lh_prefix_len);
124 124 buf->l_hdr.lh_freelist = BSWAP_16(buf->l_hdr.lh_freelist);
125 125
126 126 for (i = 0; i < ZAP_LEAF_HASH_NUMENTRIES(&l); i++)
127 127 buf->l_hash[i] = BSWAP_16(buf->l_hash[i]);
128 128
129 129 for (i = 0; i < ZAP_LEAF_NUMCHUNKS(&l); i++) {
130 130 zap_leaf_chunk_t *lc = &ZAP_LEAF_CHUNK(&l, i);
131 131 struct zap_leaf_entry *le;
132 132
133 133 switch (lc->l_free.lf_type) {
134 134 case ZAP_CHUNK_ENTRY:
135 135 le = &lc->l_entry;
136 136
137 137 le->le_type = BSWAP_8(le->le_type);
138 138 le->le_value_intlen = BSWAP_8(le->le_value_intlen);
139 139 le->le_next = BSWAP_16(le->le_next);
140 140 le->le_name_chunk = BSWAP_16(le->le_name_chunk);
141 141 le->le_name_numints = BSWAP_16(le->le_name_numints);
142 142 le->le_value_chunk = BSWAP_16(le->le_value_chunk);
143 143 le->le_value_numints = BSWAP_16(le->le_value_numints);
144 144 le->le_cd = BSWAP_32(le->le_cd);
145 145 le->le_hash = BSWAP_64(le->le_hash);
146 146 break;
147 147 case ZAP_CHUNK_FREE:
148 148 lc->l_free.lf_type = BSWAP_8(lc->l_free.lf_type);
149 149 lc->l_free.lf_next = BSWAP_16(lc->l_free.lf_next);
150 150 break;
151 151 case ZAP_CHUNK_ARRAY:
152 152 lc->l_array.la_type = BSWAP_8(lc->l_array.la_type);
153 153 lc->l_array.la_next = BSWAP_16(lc->l_array.la_next);
154 154 /* la_array doesn't need swapping */
155 155 break;
156 156 default:
157 157 ASSERT(!"bad leaf type");
158 158 }
159 159 }
160 160 }
161 161
162 162 void
163 163 zap_leaf_init(zap_leaf_t *l, boolean_t sort)
164 164 {
165 165 int i;
166 166
167 167 l->l_bs = highbit64(l->l_dbuf->db_size) - 1;
168 168 zap_memset(&zap_leaf_phys(l)->l_hdr, 0,
169 169 sizeof (struct zap_leaf_header));
170 170 zap_memset(zap_leaf_phys(l)->l_hash, CHAIN_END,
171 171 2*ZAP_LEAF_HASH_NUMENTRIES(l));
172 172 for (i = 0; i < ZAP_LEAF_NUMCHUNKS(l); i++) {
173 173 ZAP_LEAF_CHUNK(l, i).l_free.lf_type = ZAP_CHUNK_FREE;
174 174 ZAP_LEAF_CHUNK(l, i).l_free.lf_next = i+1;
175 175 }
176 176 ZAP_LEAF_CHUNK(l, ZAP_LEAF_NUMCHUNKS(l)-1).l_free.lf_next = CHAIN_END;
177 177 zap_leaf_phys(l)->l_hdr.lh_block_type = ZBT_LEAF;
178 178 zap_leaf_phys(l)->l_hdr.lh_magic = ZAP_LEAF_MAGIC;
179 179 zap_leaf_phys(l)->l_hdr.lh_nfree = ZAP_LEAF_NUMCHUNKS(l);
180 180 if (sort)
181 181 zap_leaf_phys(l)->l_hdr.lh_flags |= ZLF_ENTRIES_CDSORTED;
182 182 }
183 183
184 184 /*
185 185 * Routines which manipulate leaf chunks (l_chunk[]).
186 186 */
187 187
188 188 static uint16_t
189 189 zap_leaf_chunk_alloc(zap_leaf_t *l)
190 190 {
191 191 int chunk;
192 192
193 193 ASSERT(zap_leaf_phys(l)->l_hdr.lh_nfree > 0);
194 194
195 195 chunk = zap_leaf_phys(l)->l_hdr.lh_freelist;
196 196 ASSERT3U(chunk, <, ZAP_LEAF_NUMCHUNKS(l));
197 197 ASSERT3U(ZAP_LEAF_CHUNK(l, chunk).l_free.lf_type, ==, ZAP_CHUNK_FREE);
198 198
199 199 zap_leaf_phys(l)->l_hdr.lh_freelist =
200 200 ZAP_LEAF_CHUNK(l, chunk).l_free.lf_next;
201 201
202 202 zap_leaf_phys(l)->l_hdr.lh_nfree--;
203 203
204 204 return (chunk);
205 205 }
206 206
207 207 static void
208 208 zap_leaf_chunk_free(zap_leaf_t *l, uint16_t chunk)
209 209 {
210 210 struct zap_leaf_free *zlf = &ZAP_LEAF_CHUNK(l, chunk).l_free;
211 211 ASSERT3U(zap_leaf_phys(l)->l_hdr.lh_nfree, <, ZAP_LEAF_NUMCHUNKS(l));
212 212 ASSERT3U(chunk, <, ZAP_LEAF_NUMCHUNKS(l));
213 213 ASSERT(zlf->lf_type != ZAP_CHUNK_FREE);
214 214
215 215 zlf->lf_type = ZAP_CHUNK_FREE;
216 216 zlf->lf_next = zap_leaf_phys(l)->l_hdr.lh_freelist;
217 217 bzero(zlf->lf_pad, sizeof (zlf->lf_pad)); /* help it to compress */
218 218 zap_leaf_phys(l)->l_hdr.lh_freelist = chunk;
219 219
220 220 zap_leaf_phys(l)->l_hdr.lh_nfree++;
221 221 }
222 222
223 223 /*
224 224 * Routines which manipulate leaf arrays (zap_leaf_array type chunks).
225 225 */
226 226
227 227 static uint16_t
228 228 zap_leaf_array_create(zap_leaf_t *l, const char *buf,
229 229 int integer_size, int num_integers)
230 230 {
231 231 uint16_t chunk_head;
232 232 uint16_t *chunkp = &chunk_head;
233 233 int byten = 0;
234 234 uint64_t value = 0;
235 235 int shift = (integer_size-1)*8;
236 236 int len = num_integers;
237 237
238 238 ASSERT3U(num_integers * integer_size, <, MAX_ARRAY_BYTES);
239 239
240 240 while (len > 0) {
241 241 uint16_t chunk = zap_leaf_chunk_alloc(l);
242 242 struct zap_leaf_array *la = &ZAP_LEAF_CHUNK(l, chunk).l_array;
243 243 int i;
244 244
245 245 la->la_type = ZAP_CHUNK_ARRAY;
246 246 for (i = 0; i < ZAP_LEAF_ARRAY_BYTES; i++) {
247 247 if (byten == 0)
248 248 value = ldv(integer_size, buf);
249 249 la->la_array[i] = value >> shift;
250 250 value <<= 8;
251 251 if (++byten == integer_size) {
252 252 byten = 0;
253 253 buf += integer_size;
254 254 if (--len == 0)
255 255 break;
256 256 }
257 257 }
258 258
259 259 *chunkp = chunk;
260 260 chunkp = &la->la_next;
261 261 }
262 262 *chunkp = CHAIN_END;
263 263
264 264 return (chunk_head);
265 265 }
266 266
267 267 static void
268 268 zap_leaf_array_free(zap_leaf_t *l, uint16_t *chunkp)
269 269 {
270 270 uint16_t chunk = *chunkp;
271 271
272 272 *chunkp = CHAIN_END;
273 273
274 274 while (chunk != CHAIN_END) {
275 275 int nextchunk = ZAP_LEAF_CHUNK(l, chunk).l_array.la_next;
276 276 ASSERT3U(ZAP_LEAF_CHUNK(l, chunk).l_array.la_type, ==,
277 277 ZAP_CHUNK_ARRAY);
278 278 zap_leaf_chunk_free(l, chunk);
279 279 chunk = nextchunk;
280 280 }
281 281 }
282 282
283 283 /* array_len and buf_len are in integers, not bytes */
284 284 static void
285 285 zap_leaf_array_read(zap_leaf_t *l, uint16_t chunk,
286 286 int array_int_len, int array_len, int buf_int_len, uint64_t buf_len,
287 287 void *buf)
288 288 {
289 289 int len = MIN(array_len, buf_len);
290 290 int byten = 0;
291 291 uint64_t value = 0;
292 292 char *p = buf;
293 293
294 294 ASSERT3U(array_int_len, <=, buf_int_len);
295 295
296 296 /* Fast path for one 8-byte integer */
297 297 if (array_int_len == 8 && buf_int_len == 8 && len == 1) {
298 298 struct zap_leaf_array *la = &ZAP_LEAF_CHUNK(l, chunk).l_array;
299 299 uint8_t *ip = la->la_array;
300 300 uint64_t *buf64 = buf;
301 301
302 302 *buf64 = (uint64_t)ip[0] << 56 | (uint64_t)ip[1] << 48 |
303 303 (uint64_t)ip[2] << 40 | (uint64_t)ip[3] << 32 |
304 304 (uint64_t)ip[4] << 24 | (uint64_t)ip[5] << 16 |
305 305 (uint64_t)ip[6] << 8 | (uint64_t)ip[7];
306 306 return;
307 307 }
308 308
309 309 /* Fast path for an array of 1-byte integers (eg. the entry name) */
310 310 if (array_int_len == 1 && buf_int_len == 1 &&
311 311 buf_len > array_len + ZAP_LEAF_ARRAY_BYTES) {
312 312 while (chunk != CHAIN_END) {
313 313 struct zap_leaf_array *la =
314 314 &ZAP_LEAF_CHUNK(l, chunk).l_array;
315 315 bcopy(la->la_array, p, ZAP_LEAF_ARRAY_BYTES);
316 316 p += ZAP_LEAF_ARRAY_BYTES;
317 317 chunk = la->la_next;
318 318 }
319 319 return;
320 320 }
321 321
322 322 while (len > 0) {
323 323 struct zap_leaf_array *la = &ZAP_LEAF_CHUNK(l, chunk).l_array;
324 324 int i;
325 325
326 326 ASSERT3U(chunk, <, ZAP_LEAF_NUMCHUNKS(l));
327 327 for (i = 0; i < ZAP_LEAF_ARRAY_BYTES && len > 0; i++) {
328 328 value = (value << 8) | la->la_array[i];
329 329 byten++;
330 330 if (byten == array_int_len) {
331 331 stv(buf_int_len, p, value);
332 332 byten = 0;
333 333 len--;
334 334 if (len == 0)
335 335 return;
336 336 p += buf_int_len;
337 337 }
338 338 }
339 339 chunk = la->la_next;
340 340 }
341 341 }
342 342
343 343 static boolean_t
344 344 zap_leaf_array_match(zap_leaf_t *l, zap_name_t *zn,
345 345 int chunk, int array_numints)
346 346 {
347 347 int bseen = 0;
348 348
349 349 if (zap_getflags(zn->zn_zap) & ZAP_FLAG_UINT64_KEY) {
350 350 uint64_t *thiskey;
351 351 boolean_t match;
352 352
353 353 ASSERT(zn->zn_key_intlen == sizeof (*thiskey));
354 354 thiskey = kmem_alloc(array_numints * sizeof (*thiskey),
355 355 KM_SLEEP);
356 356
357 357 zap_leaf_array_read(l, chunk, sizeof (*thiskey), array_numints,
358 358 sizeof (*thiskey), array_numints, thiskey);
359 359 match = bcmp(thiskey, zn->zn_key_orig,
360 360 array_numints * sizeof (*thiskey)) == 0;
361 361 kmem_free(thiskey, array_numints * sizeof (*thiskey));
362 362 return (match);
363 363 }
364 364
365 365 ASSERT(zn->zn_key_intlen == 1);
366 366 if (zn->zn_matchtype & MT_NORMALIZE) {
367 367 char *thisname = kmem_alloc(array_numints, KM_SLEEP);
368 368 boolean_t match;
369 369
370 370 zap_leaf_array_read(l, chunk, sizeof (char), array_numints,
371 371 sizeof (char), array_numints, thisname);
372 372 match = zap_match(zn, thisname);
373 373 kmem_free(thisname, array_numints);
374 374 return (match);
375 375 }
376 376
377 377 /*
378 378 * Fast path for exact matching.
379 379 * First check that the lengths match, so that we don't read
380 380 * past the end of the zn_key_orig array.
381 381 */
382 382 if (array_numints != zn->zn_key_orig_numints)
383 383 return (B_FALSE);
384 384 while (bseen < array_numints) {
385 385 struct zap_leaf_array *la = &ZAP_LEAF_CHUNK(l, chunk).l_array;
386 386 int toread = MIN(array_numints - bseen, ZAP_LEAF_ARRAY_BYTES);
387 387 ASSERT3U(chunk, <, ZAP_LEAF_NUMCHUNKS(l));
388 388 if (bcmp(la->la_array, (char *)zn->zn_key_orig + bseen, toread))
389 389 break;
390 390 chunk = la->la_next;
391 391 bseen += toread;
392 392 }
393 393 return (bseen == array_numints);
394 394 }
395 395
396 396 /*
397 397 * Routines which manipulate leaf entries.
398 398 */
399 399
400 400 int
401 401 zap_leaf_lookup(zap_leaf_t *l, zap_name_t *zn, zap_entry_handle_t *zeh)
402 402 {
403 403 uint16_t *chunkp;
404 404 struct zap_leaf_entry *le;
405 405
406 406 ASSERT3U(zap_leaf_phys(l)->l_hdr.lh_magic, ==, ZAP_LEAF_MAGIC);
407 407
408 408 for (chunkp = LEAF_HASH_ENTPTR(l, zn->zn_hash);
409 409 *chunkp != CHAIN_END; chunkp = &le->le_next) {
410 410 uint16_t chunk = *chunkp;
411 411 le = ZAP_LEAF_ENTRY(l, chunk);
412 412
413 413 ASSERT3U(chunk, <, ZAP_LEAF_NUMCHUNKS(l));
414 414 ASSERT3U(le->le_type, ==, ZAP_CHUNK_ENTRY);
415 415
416 416 if (le->le_hash != zn->zn_hash)
417 417 continue;
418 418
419 419 /*
420 420 * NB: the entry chain is always sorted by cd on
421 421 * normalized zap objects, so this will find the
422 422 * lowest-cd match for MT_NORMALIZE.
423 423 */
424 424 ASSERT((zn->zn_matchtype == 0) ||
425 425 (zap_leaf_phys(l)->l_hdr.lh_flags & ZLF_ENTRIES_CDSORTED));
426 426 if (zap_leaf_array_match(l, zn, le->le_name_chunk,
427 427 le->le_name_numints)) {
428 428 zeh->zeh_num_integers = le->le_value_numints;
429 429 zeh->zeh_integer_size = le->le_value_intlen;
430 430 zeh->zeh_cd = le->le_cd;
431 431 zeh->zeh_hash = le->le_hash;
432 432 zeh->zeh_chunkp = chunkp;
433 433 zeh->zeh_leaf = l;
434 434 return (0);
435 435 }
436 436 }
437 437
438 438 return (SET_ERROR(ENOENT));
439 439 }
440 440
441 441 /* Return (h1,cd1 >= h2,cd2) */
442 442 #define HCD_GTEQ(h1, cd1, h2, cd2) \
443 443 ((h1 > h2) ? TRUE : ((h1 == h2 && cd1 >= cd2) ? TRUE : FALSE))
444 444
445 445 int
446 446 zap_leaf_lookup_closest(zap_leaf_t *l,
447 447 uint64_t h, uint32_t cd, zap_entry_handle_t *zeh)
448 448 {
449 449 uint16_t chunk;
450 450 uint64_t besth = -1ULL;
451 451 uint32_t bestcd = -1U;
452 452 uint16_t bestlh = ZAP_LEAF_HASH_NUMENTRIES(l)-1;
453 453 uint16_t lh;
454 454 struct zap_leaf_entry *le;
455 455
456 456 ASSERT3U(zap_leaf_phys(l)->l_hdr.lh_magic, ==, ZAP_LEAF_MAGIC);
457 457
458 458 for (lh = LEAF_HASH(l, h); lh <= bestlh; lh++) {
459 459 for (chunk = zap_leaf_phys(l)->l_hash[lh];
460 460 chunk != CHAIN_END; chunk = le->le_next) {
461 461 le = ZAP_LEAF_ENTRY(l, chunk);
462 462
463 463 ASSERT3U(chunk, <, ZAP_LEAF_NUMCHUNKS(l));
464 464 ASSERT3U(le->le_type, ==, ZAP_CHUNK_ENTRY);
465 465
466 466 if (HCD_GTEQ(le->le_hash, le->le_cd, h, cd) &&
467 467 HCD_GTEQ(besth, bestcd, le->le_hash, le->le_cd)) {
468 468 ASSERT3U(bestlh, >=, lh);
469 469 bestlh = lh;
470 470 besth = le->le_hash;
471 471 bestcd = le->le_cd;
472 472
473 473 zeh->zeh_num_integers = le->le_value_numints;
474 474 zeh->zeh_integer_size = le->le_value_intlen;
475 475 zeh->zeh_cd = le->le_cd;
476 476 zeh->zeh_hash = le->le_hash;
477 477 zeh->zeh_fakechunk = chunk;
478 478 zeh->zeh_chunkp = &zeh->zeh_fakechunk;
479 479 zeh->zeh_leaf = l;
480 480 }
481 481 }
482 482 }
483 483
484 484 return (bestcd == -1U ? ENOENT : 0);
485 485 }
486 486
487 487 int
488 488 zap_entry_read(const zap_entry_handle_t *zeh,
489 489 uint8_t integer_size, uint64_t num_integers, void *buf)
490 490 {
491 491 struct zap_leaf_entry *le =
492 492 ZAP_LEAF_ENTRY(zeh->zeh_leaf, *zeh->zeh_chunkp);
493 493 ASSERT3U(le->le_type, ==, ZAP_CHUNK_ENTRY);
494 494
495 495 if (le->le_value_intlen > integer_size)
496 496 return (SET_ERROR(EINVAL));
497 497
498 498 zap_leaf_array_read(zeh->zeh_leaf, le->le_value_chunk,
499 499 le->le_value_intlen, le->le_value_numints,
500 500 integer_size, num_integers, buf);
501 501
502 502 if (zeh->zeh_num_integers > num_integers)
503 503 return (SET_ERROR(EOVERFLOW));
504 504 return (0);
505 505
506 506 }
507 507
508 508 int
509 509 zap_entry_read_name(zap_t *zap, const zap_entry_handle_t *zeh, uint16_t buflen,
510 510 char *buf)
511 511 {
512 512 struct zap_leaf_entry *le =
513 513 ZAP_LEAF_ENTRY(zeh->zeh_leaf, *zeh->zeh_chunkp);
514 514 ASSERT3U(le->le_type, ==, ZAP_CHUNK_ENTRY);
515 515
516 516 if (zap_getflags(zap) & ZAP_FLAG_UINT64_KEY) {
517 517 zap_leaf_array_read(zeh->zeh_leaf, le->le_name_chunk, 8,
518 518 le->le_name_numints, 8, buflen / 8, buf);
519 519 } else {
520 520 zap_leaf_array_read(zeh->zeh_leaf, le->le_name_chunk, 1,
521 521 le->le_name_numints, 1, buflen, buf);
522 522 }
523 523 if (le->le_name_numints > buflen)
524 524 return (SET_ERROR(EOVERFLOW));
525 525 return (0);
526 526 }
527 527
528 528 int
529 529 zap_entry_update(zap_entry_handle_t *zeh,
530 530 uint8_t integer_size, uint64_t num_integers, const void *buf)
531 531 {
532 532 int delta_chunks;
533 533 zap_leaf_t *l = zeh->zeh_leaf;
534 534 struct zap_leaf_entry *le = ZAP_LEAF_ENTRY(l, *zeh->zeh_chunkp);
535 535
536 536 delta_chunks = ZAP_LEAF_ARRAY_NCHUNKS(num_integers * integer_size) -
537 537 ZAP_LEAF_ARRAY_NCHUNKS(le->le_value_numints * le->le_value_intlen);
538 538
539 539 if ((int)zap_leaf_phys(l)->l_hdr.lh_nfree < delta_chunks)
540 540 return (SET_ERROR(EAGAIN));
541 541
542 542 zap_leaf_array_free(l, &le->le_value_chunk);
543 543 le->le_value_chunk =
544 544 zap_leaf_array_create(l, buf, integer_size, num_integers);
545 545 le->le_value_numints = num_integers;
546 546 le->le_value_intlen = integer_size;
547 547 return (0);
548 548 }
549 549
550 550 void
551 551 zap_entry_remove(zap_entry_handle_t *zeh)
552 552 {
553 553 uint16_t entry_chunk;
554 554 struct zap_leaf_entry *le;
555 555 zap_leaf_t *l = zeh->zeh_leaf;
556 556
557 557 ASSERT3P(zeh->zeh_chunkp, !=, &zeh->zeh_fakechunk);
558 558
559 559 entry_chunk = *zeh->zeh_chunkp;
560 560 le = ZAP_LEAF_ENTRY(l, entry_chunk);
561 561 ASSERT3U(le->le_type, ==, ZAP_CHUNK_ENTRY);
562 562
563 563 zap_leaf_array_free(l, &le->le_name_chunk);
564 564 zap_leaf_array_free(l, &le->le_value_chunk);
565 565
566 566 *zeh->zeh_chunkp = le->le_next;
567 567 zap_leaf_chunk_free(l, entry_chunk);
568 568
569 569 zap_leaf_phys(l)->l_hdr.lh_nentries--;
570 570 }
571 571
572 572 int
573 573 zap_entry_create(zap_leaf_t *l, zap_name_t *zn, uint32_t cd,
574 574 uint8_t integer_size, uint64_t num_integers, const void *buf,
575 575 zap_entry_handle_t *zeh)
576 576 {
577 577 uint16_t chunk;
578 578 uint16_t *chunkp;
|
↓ open down ↓ |
578 lines elided |
↑ open up ↑ |
579 579 struct zap_leaf_entry *le;
580 580 uint64_t valuelen;
581 581 int numchunks;
582 582 uint64_t h = zn->zn_hash;
583 583
584 584 valuelen = integer_size * num_integers;
585 585
586 586 numchunks = 1 + ZAP_LEAF_ARRAY_NCHUNKS(zn->zn_key_orig_numints *
587 587 zn->zn_key_intlen) + ZAP_LEAF_ARRAY_NCHUNKS(valuelen);
588 588 if (numchunks > ZAP_LEAF_NUMCHUNKS(l))
589 - return (E2BIG);
589 + return (SET_ERROR(E2BIG));
590 590
591 591 if (cd == ZAP_NEED_CD) {
592 592 /* find the lowest unused cd */
593 593 if (zap_leaf_phys(l)->l_hdr.lh_flags & ZLF_ENTRIES_CDSORTED) {
594 594 cd = 0;
595 595
596 596 for (chunk = *LEAF_HASH_ENTPTR(l, h);
597 597 chunk != CHAIN_END; chunk = le->le_next) {
598 598 le = ZAP_LEAF_ENTRY(l, chunk);
599 599 if (le->le_cd > cd)
600 600 break;
601 601 if (le->le_hash == h) {
602 602 ASSERT3U(cd, ==, le->le_cd);
603 603 cd++;
604 604 }
605 605 }
606 606 } else {
607 607 /* old unsorted format; do it the O(n^2) way */
608 608 for (cd = 0; ; cd++) {
609 609 for (chunk = *LEAF_HASH_ENTPTR(l, h);
610 610 chunk != CHAIN_END; chunk = le->le_next) {
611 611 le = ZAP_LEAF_ENTRY(l, chunk);
612 612 if (le->le_hash == h &&
613 613 le->le_cd == cd) {
614 614 break;
615 615 }
616 616 }
617 617 /* If this cd is not in use, we are good. */
618 618 if (chunk == CHAIN_END)
619 619 break;
620 620 }
621 621 }
622 622 /*
623 623 * We would run out of space in a block before we could
624 624 * store enough entries to run out of CD values.
625 625 */
626 626 ASSERT3U(cd, <, zap_maxcd(zn->zn_zap));
627 627 }
628 628
629 629 if (zap_leaf_phys(l)->l_hdr.lh_nfree < numchunks)
630 630 return (SET_ERROR(EAGAIN));
631 631
632 632 /* make the entry */
633 633 chunk = zap_leaf_chunk_alloc(l);
634 634 le = ZAP_LEAF_ENTRY(l, chunk);
635 635 le->le_type = ZAP_CHUNK_ENTRY;
636 636 le->le_name_chunk = zap_leaf_array_create(l, zn->zn_key_orig,
637 637 zn->zn_key_intlen, zn->zn_key_orig_numints);
638 638 le->le_name_numints = zn->zn_key_orig_numints;
639 639 le->le_value_chunk =
640 640 zap_leaf_array_create(l, buf, integer_size, num_integers);
641 641 le->le_value_numints = num_integers;
642 642 le->le_value_intlen = integer_size;
643 643 le->le_hash = h;
644 644 le->le_cd = cd;
645 645
646 646 /* link it into the hash chain */
647 647 /* XXX if we did the search above, we could just use that */
648 648 chunkp = zap_leaf_rehash_entry(l, chunk);
649 649
650 650 zap_leaf_phys(l)->l_hdr.lh_nentries++;
651 651
652 652 zeh->zeh_leaf = l;
653 653 zeh->zeh_num_integers = num_integers;
654 654 zeh->zeh_integer_size = le->le_value_intlen;
655 655 zeh->zeh_cd = le->le_cd;
656 656 zeh->zeh_hash = le->le_hash;
657 657 zeh->zeh_chunkp = chunkp;
658 658
659 659 return (0);
660 660 }
661 661
662 662 /*
663 663 * Determine if there is another entry with the same normalized form.
664 664 * For performance purposes, either zn or name must be provided (the
665 665 * other can be NULL). Note, there usually won't be any hash
666 666 * conflicts, in which case we don't need the concatenated/normalized
667 667 * form of the name. But all callers have one of these on hand anyway,
668 668 * so might as well take advantage. A cleaner but slower interface
669 669 * would accept neither argument, and compute the normalized name as
670 670 * needed (using zap_name_alloc(zap_entry_read_name(zeh))).
671 671 */
672 672 boolean_t
673 673 zap_entry_normalization_conflict(zap_entry_handle_t *zeh, zap_name_t *zn,
674 674 const char *name, zap_t *zap)
675 675 {
676 676 uint64_t chunk;
677 677 struct zap_leaf_entry *le;
678 678 boolean_t allocdzn = B_FALSE;
679 679
680 680 if (zap->zap_normflags == 0)
681 681 return (B_FALSE);
682 682
683 683 for (chunk = *LEAF_HASH_ENTPTR(zeh->zeh_leaf, zeh->zeh_hash);
684 684 chunk != CHAIN_END; chunk = le->le_next) {
685 685 le = ZAP_LEAF_ENTRY(zeh->zeh_leaf, chunk);
686 686 if (le->le_hash != zeh->zeh_hash)
687 687 continue;
688 688 if (le->le_cd == zeh->zeh_cd)
689 689 continue;
690 690
691 691 if (zn == NULL) {
692 692 zn = zap_name_alloc(zap, name, MT_NORMALIZE);
693 693 allocdzn = B_TRUE;
694 694 }
695 695 if (zap_leaf_array_match(zeh->zeh_leaf, zn,
696 696 le->le_name_chunk, le->le_name_numints)) {
697 697 if (allocdzn)
698 698 zap_name_free(zn);
699 699 return (B_TRUE);
700 700 }
701 701 }
702 702 if (allocdzn)
703 703 zap_name_free(zn);
704 704 return (B_FALSE);
705 705 }
706 706
707 707 /*
708 708 * Routines for transferring entries between leafs.
709 709 */
710 710
711 711 static uint16_t *
712 712 zap_leaf_rehash_entry(zap_leaf_t *l, uint16_t entry)
713 713 {
714 714 struct zap_leaf_entry *le = ZAP_LEAF_ENTRY(l, entry);
715 715 struct zap_leaf_entry *le2;
716 716 uint16_t *chunkp;
717 717
718 718 /*
719 719 * keep the entry chain sorted by cd
720 720 * NB: this will not cause problems for unsorted leafs, though
721 721 * it is unnecessary there.
722 722 */
723 723 for (chunkp = LEAF_HASH_ENTPTR(l, le->le_hash);
724 724 *chunkp != CHAIN_END; chunkp = &le2->le_next) {
725 725 le2 = ZAP_LEAF_ENTRY(l, *chunkp);
726 726 if (le2->le_cd > le->le_cd)
727 727 break;
728 728 }
729 729
730 730 le->le_next = *chunkp;
731 731 *chunkp = entry;
732 732 return (chunkp);
733 733 }
734 734
735 735 static uint16_t
736 736 zap_leaf_transfer_array(zap_leaf_t *l, uint16_t chunk, zap_leaf_t *nl)
737 737 {
738 738 uint16_t new_chunk;
739 739 uint16_t *nchunkp = &new_chunk;
740 740
741 741 while (chunk != CHAIN_END) {
742 742 uint16_t nchunk = zap_leaf_chunk_alloc(nl);
743 743 struct zap_leaf_array *nla =
744 744 &ZAP_LEAF_CHUNK(nl, nchunk).l_array;
745 745 struct zap_leaf_array *la =
746 746 &ZAP_LEAF_CHUNK(l, chunk).l_array;
747 747 int nextchunk = la->la_next;
748 748
749 749 ASSERT3U(chunk, <, ZAP_LEAF_NUMCHUNKS(l));
750 750 ASSERT3U(nchunk, <, ZAP_LEAF_NUMCHUNKS(l));
751 751
752 752 *nla = *la; /* structure assignment */
753 753
754 754 zap_leaf_chunk_free(l, chunk);
755 755 chunk = nextchunk;
756 756 *nchunkp = nchunk;
757 757 nchunkp = &nla->la_next;
758 758 }
759 759 *nchunkp = CHAIN_END;
760 760 return (new_chunk);
761 761 }
762 762
763 763 static void
764 764 zap_leaf_transfer_entry(zap_leaf_t *l, int entry, zap_leaf_t *nl)
765 765 {
766 766 struct zap_leaf_entry *le, *nle;
767 767 uint16_t chunk;
768 768
769 769 le = ZAP_LEAF_ENTRY(l, entry);
770 770 ASSERT3U(le->le_type, ==, ZAP_CHUNK_ENTRY);
771 771
772 772 chunk = zap_leaf_chunk_alloc(nl);
773 773 nle = ZAP_LEAF_ENTRY(nl, chunk);
774 774 *nle = *le; /* structure assignment */
775 775
776 776 (void) zap_leaf_rehash_entry(nl, chunk);
777 777
778 778 nle->le_name_chunk = zap_leaf_transfer_array(l, le->le_name_chunk, nl);
779 779 nle->le_value_chunk =
780 780 zap_leaf_transfer_array(l, le->le_value_chunk, nl);
781 781
782 782 zap_leaf_chunk_free(l, entry);
783 783
784 784 zap_leaf_phys(l)->l_hdr.lh_nentries--;
785 785 zap_leaf_phys(nl)->l_hdr.lh_nentries++;
786 786 }
787 787
788 788 /*
789 789 * Transfer the entries whose hash prefix ends in 1 to the new leaf.
790 790 */
791 791 void
792 792 zap_leaf_split(zap_leaf_t *l, zap_leaf_t *nl, boolean_t sort)
793 793 {
794 794 int i;
795 795 int bit = 64 - 1 - zap_leaf_phys(l)->l_hdr.lh_prefix_len;
796 796
797 797 /* set new prefix and prefix_len */
798 798 zap_leaf_phys(l)->l_hdr.lh_prefix <<= 1;
799 799 zap_leaf_phys(l)->l_hdr.lh_prefix_len++;
800 800 zap_leaf_phys(nl)->l_hdr.lh_prefix =
801 801 zap_leaf_phys(l)->l_hdr.lh_prefix | 1;
802 802 zap_leaf_phys(nl)->l_hdr.lh_prefix_len =
803 803 zap_leaf_phys(l)->l_hdr.lh_prefix_len;
804 804
805 805 /* break existing hash chains */
806 806 zap_memset(zap_leaf_phys(l)->l_hash, CHAIN_END,
807 807 2*ZAP_LEAF_HASH_NUMENTRIES(l));
808 808
809 809 if (sort)
810 810 zap_leaf_phys(l)->l_hdr.lh_flags |= ZLF_ENTRIES_CDSORTED;
811 811
812 812 /*
813 813 * Transfer entries whose hash bit 'bit' is set to nl; rehash
814 814 * the remaining entries
815 815 *
816 816 * NB: We could find entries via the hashtable instead. That
817 817 * would be O(hashents+numents) rather than O(numblks+numents),
818 818 * but this accesses memory more sequentially, and when we're
819 819 * called, the block is usually pretty full.
820 820 */
821 821 for (i = 0; i < ZAP_LEAF_NUMCHUNKS(l); i++) {
822 822 struct zap_leaf_entry *le = ZAP_LEAF_ENTRY(l, i);
823 823 if (le->le_type != ZAP_CHUNK_ENTRY)
824 824 continue;
825 825
826 826 if (le->le_hash & (1ULL << bit))
827 827 zap_leaf_transfer_entry(l, i, nl);
828 828 else
829 829 (void) zap_leaf_rehash_entry(l, i);
830 830 }
831 831 }
832 832
833 833 void
834 834 zap_leaf_stats(zap_t *zap, zap_leaf_t *l, zap_stats_t *zs)
835 835 {
836 836 int i, n;
837 837
838 838 n = zap_f_phys(zap)->zap_ptrtbl.zt_shift -
839 839 zap_leaf_phys(l)->l_hdr.lh_prefix_len;
840 840 n = MIN(n, ZAP_HISTOGRAM_SIZE-1);
841 841 zs->zs_leafs_with_2n_pointers[n]++;
842 842
843 843
844 844 n = zap_leaf_phys(l)->l_hdr.lh_nentries/5;
845 845 n = MIN(n, ZAP_HISTOGRAM_SIZE-1);
846 846 zs->zs_blocks_with_n5_entries[n]++;
847 847
848 848 n = ((1<<FZAP_BLOCK_SHIFT(zap)) -
849 849 zap_leaf_phys(l)->l_hdr.lh_nfree * (ZAP_LEAF_ARRAY_BYTES+1))*10 /
850 850 (1<<FZAP_BLOCK_SHIFT(zap));
851 851 n = MIN(n, ZAP_HISTOGRAM_SIZE-1);
852 852 zs->zs_blocks_n_tenths_full[n]++;
853 853
854 854 for (i = 0; i < ZAP_LEAF_HASH_NUMENTRIES(l); i++) {
855 855 int nentries = 0;
856 856 int chunk = zap_leaf_phys(l)->l_hash[i];
857 857
858 858 while (chunk != CHAIN_END) {
859 859 struct zap_leaf_entry *le =
860 860 ZAP_LEAF_ENTRY(l, chunk);
861 861
862 862 n = 1 + ZAP_LEAF_ARRAY_NCHUNKS(le->le_name_numints) +
863 863 ZAP_LEAF_ARRAY_NCHUNKS(le->le_value_numints *
864 864 le->le_value_intlen);
865 865 n = MIN(n, ZAP_HISTOGRAM_SIZE-1);
866 866 zs->zs_entries_using_n_chunks[n]++;
867 867
868 868 chunk = le->le_next;
869 869 nentries++;
870 870 }
871 871
872 872 n = nentries;
873 873 n = MIN(n, ZAP_HISTOGRAM_SIZE-1);
874 874 zs->zs_buckets_with_n_entries[n]++;
875 875 }
876 876 }
|
↓ open down ↓ |
277 lines elided |
↑ open up ↑ |
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX