1 // SPDX-License-Identifier: CDDL-1.0
2 /*
3 * This file and its contents are supplied under the terms of the
4 * Common Development and Distribution License ("CDDL"), version 1.0.
5 * You may only use this file in accordance with the terms of version
6 * 1.0 of the CDDL.
7 *
8 * A full copy of the text of the CDDL should have accompanied this
9 * source. A copy of the CDDL is also available via the Internet at
10 * https://opensource.org/license/CDDL-1.0.
11 */
12
13 /*
14 * Copyright (c) 2005, 2010, Oracle and/or its affiliates. All rights reserved.
15 * Copyright (c) 2011, 2018 by Delphix. All rights reserved.
16 * Copyright (c) 2014 Spectra Logic Corporation, All rights reserved.
17 * Copyright 2017 Nexenta Systems, Inc.
18 * Copyright (c) 2024, Klara, Inc.
19 * Copyright (c) 2026, TrueNAS.
20 */
21
22 #include <sys/zfs_context.h>
23 #include <sys/dmu.h>
24 #include <sys/dnode.h>
25 #include <sys/dsl_dataset.h>
26 #include <sys/zap.h>
27 #include <sys/zap_impl.h>
28
29 static kmem_cache_t *zap_name_cache;
30 static kmem_cache_t *zap_attr_cache;
31 static kmem_cache_t *zap_name_long_cache;
32 static kmem_cache_t *zap_attr_long_cache;
33
34 /* Setup/teardown caches. Part of the public interface in zap.h. */
35 void
zap_init(void)36 zap_init(void)
37 {
38 zap_name_cache = kmem_cache_create("zap_name",
39 sizeof (zap_name_t) + ZAP_MAXNAMELEN, 0, NULL, NULL,
40 NULL, NULL, NULL, 0);
41
42 zap_attr_cache = kmem_cache_create("zap_attr_cache",
43 sizeof (zap_attribute_t) + ZAP_MAXNAMELEN, 0, NULL,
44 NULL, NULL, NULL, NULL, 0);
45
46 zap_name_long_cache = kmem_cache_create("zap_name_long",
47 sizeof (zap_name_t) + ZAP_MAXNAMELEN_NEW, 0, NULL, NULL,
48 NULL, NULL, NULL, 0);
49
50 zap_attr_long_cache = kmem_cache_create("zap_attr_long_cache",
51 sizeof (zap_attribute_t) + ZAP_MAXNAMELEN_NEW, 0, NULL,
52 NULL, NULL, NULL, NULL, 0);
53 }
54
55 void
zap_fini(void)56 zap_fini(void)
57 {
58 kmem_cache_destroy(zap_name_cache);
59 kmem_cache_destroy(zap_attr_cache);
60 kmem_cache_destroy(zap_name_long_cache);
61 kmem_cache_destroy(zap_attr_long_cache);
62 }
63
64 static int
zap_normalize(zap_t * zap,const char * name,char * namenorm,int normflags,size_t outlen)65 zap_normalize(zap_t *zap, const char *name, char *namenorm, int normflags,
66 size_t outlen)
67 {
68 ASSERT(!(zap_getflags(zap) & ZAP_FLAG_UINT64_KEY));
69
70 size_t inlen = strlen(name) + 1;
71
72 int err = 0;
73 (void) u8_textprep_str((char *)name, &inlen, namenorm, &outlen,
74 normflags | U8_TEXTPREP_IGNORE_NULL | U8_TEXTPREP_IGNORE_INVALID,
75 U8_UNICODE_LATEST, &err);
76
77 return (err);
78 }
79
80 zap_name_t *
zap_name_alloc(zap_t * zap,boolean_t longname)81 zap_name_alloc(zap_t *zap, boolean_t longname)
82 {
83 kmem_cache_t *cache = longname ? zap_name_long_cache : zap_name_cache;
84 zap_name_t *zn = kmem_cache_alloc(cache, KM_SLEEP);
85
86 zn->zn_zap = zap;
87 zn->zn_normbuf_len = longname ? ZAP_MAXNAMELEN_NEW : ZAP_MAXNAMELEN;
88 return (zn);
89 }
90
91 zap_name_t *
zap_name_alloc_str(zap_t * zap,const char * key,matchtype_t mt)92 zap_name_alloc_str(zap_t *zap, const char *key, matchtype_t mt)
93 {
94 size_t key_len = strlen(key) + 1;
95 zap_name_t *zn = zap_name_alloc(zap, (key_len > ZAP_MAXNAMELEN));
96 if (zap_name_init_str(zn, key, mt) != 0) {
97 zap_name_free(zn);
98 return (NULL);
99 }
100 return (zn);
101 }
102
103 zap_name_t *
zap_name_alloc_uint64(zap_t * zap,const uint64_t * key,int numints)104 zap_name_alloc_uint64(zap_t *zap, const uint64_t *key, int numints)
105 {
106 zap_name_t *zn = kmem_cache_alloc(zap_name_cache, KM_SLEEP);
107
108 ASSERT0(zap->zap_normflags);
109 zn->zn_zap = zap;
110 zn->zn_key_intlen = sizeof (*key);
111 zn->zn_key_orig = zn->zn_key_norm = key;
112 zn->zn_key_orig_numints = zn->zn_key_norm_numints = numints;
113 zn->zn_matchtype = 0;
114 zn->zn_normbuf_len = ZAP_MAXNAMELEN;
115
116 zn->zn_hash = zap_hash(zn);
117 return (zn);
118 }
119
120 void
zap_name_free(zap_name_t * zn)121 zap_name_free(zap_name_t *zn)
122 {
123 if (zn->zn_normbuf_len == ZAP_MAXNAMELEN) {
124 kmem_cache_free(zap_name_cache, zn);
125 } else {
126 ASSERT3U(zn->zn_normbuf_len, ==, ZAP_MAXNAMELEN_NEW);
127 kmem_cache_free(zap_name_long_cache, zn);
128 }
129 }
130
131 int
zap_name_init_str(zap_name_t * zn,const char * key,matchtype_t mt)132 zap_name_init_str(zap_name_t *zn, const char *key, matchtype_t mt)
133 {
134 zap_t *zap = zn->zn_zap;
135 size_t key_len = strlen(key) + 1;
136
137 /* Make sure zn is allocated for longname if key is long */
138 IMPLY(key_len > ZAP_MAXNAMELEN,
139 zn->zn_normbuf_len == ZAP_MAXNAMELEN_NEW);
140
141 zn->zn_key_intlen = sizeof (*key);
142 zn->zn_key_orig = key;
143 zn->zn_key_orig_numints = key_len;
144 zn->zn_matchtype = mt;
145 zn->zn_normflags = zap->zap_normflags;
146
147 /*
148 * If we're dealing with a case sensitive lookup on a mixed or
149 * insensitive fs, remove U8_TEXTPREP_TOUPPER or the lookup
150 * will fold case to all caps overriding the lookup request.
151 */
152 if (mt & MT_MATCH_CASE)
153 zn->zn_normflags &= ~U8_TEXTPREP_TOUPPER;
154
155 if (zap->zap_normflags) {
156 /*
157 * We *must* use zap_normflags because this normalization is
158 * what the hash is computed from.
159 */
160 if (zap_normalize(zap, key, zn->zn_normbuf,
161 zap->zap_normflags, zn->zn_normbuf_len) != 0)
162 return (SET_ERROR(ENOTSUP));
163 zn->zn_key_norm = zn->zn_normbuf;
164 zn->zn_key_norm_numints = strlen(zn->zn_key_norm) + 1;
165 } else {
166 if (mt != 0)
167 return (SET_ERROR(ENOTSUP));
168 zn->zn_key_norm = zn->zn_key_orig;
169 zn->zn_key_norm_numints = zn->zn_key_orig_numints;
170 }
171
172 zn->zn_hash = zap_hash(zn);
173
174 if (zap->zap_normflags != zn->zn_normflags) {
175 /*
176 * We *must* use zn_normflags because this normalization is
177 * what the matching is based on. (Not the hash!)
178 */
179 if (zap_normalize(zap, key, zn->zn_normbuf,
180 zn->zn_normflags, zn->zn_normbuf_len) != 0)
181 return (SET_ERROR(ENOTSUP));
182 zn->zn_key_norm_numints = strlen(zn->zn_key_norm) + 1;
183 }
184
185 return (0);
186 }
187
188 boolean_t
zap_match(zap_name_t * zn,const char * matchname)189 zap_match(zap_name_t *zn, const char *matchname)
190 {
191 boolean_t res = B_FALSE;
192 ASSERT(!(zap_getflags(zn->zn_zap) & ZAP_FLAG_UINT64_KEY));
193
194 if (zn->zn_matchtype & MT_NORMALIZE) {
195 size_t namelen = zn->zn_normbuf_len;
196 char normbuf[ZAP_MAXNAMELEN];
197 char *norm = normbuf;
198
199 /*
200 * Cannot allocate this on-stack as it exceed the stack-limit of
201 * 1024.
202 */
203 if (namelen > ZAP_MAXNAMELEN)
204 norm = kmem_alloc(namelen, KM_SLEEP);
205
206 if (zap_normalize(zn->zn_zap, matchname, norm,
207 zn->zn_normflags, namelen) != 0) {
208 res = B_FALSE;
209 } else {
210 res = (strcmp(zn->zn_key_norm, norm) == 0);
211 }
212 if (norm != normbuf)
213 kmem_free(norm, namelen);
214 } else {
215 res = (strcmp(zn->zn_key_orig, matchname) == 0);
216 }
217 return (res);
218 }
219
220 uint64_t
zap_hash(zap_name_t * zn)221 zap_hash(zap_name_t *zn)
222 {
223 zap_t *zap = zn->zn_zap;
224 uint64_t h = 0;
225
226 if (zap_getflags(zap) & ZAP_FLAG_PRE_HASHED_KEY) {
227 ASSERT(zap_getflags(zap) & ZAP_FLAG_UINT64_KEY);
228 h = *(uint64_t *)zn->zn_key_orig;
229 } else {
230 h = zap->zap_salt;
231 ASSERT(h != 0);
232 ASSERT(zfs_crc64_table[128] == ZFS_CRC64_POLY);
233
234 if (zap_getflags(zap) & ZAP_FLAG_UINT64_KEY) {
235 const uint64_t *wp = zn->zn_key_norm;
236
237 ASSERT(zn->zn_key_intlen == 8);
238 for (int i = 0; i < zn->zn_key_norm_numints;
239 wp++, i++) {
240 uint64_t word = *wp;
241
242 for (int j = 0; j < 8; j++) {
243 h = (h >> 8) ^
244 zfs_crc64_table[(h ^ word) & 0xFF];
245 word >>= NBBY;
246 }
247 }
248 } else {
249 const uint8_t *cp = zn->zn_key_norm;
250
251 /*
252 * We previously stored the terminating null on
253 * disk, but didn't hash it, so we need to
254 * continue to not hash it. (The
255 * zn_key_*_numints includes the terminating
256 * null for non-binary keys.)
257 */
258 int len = zn->zn_key_norm_numints - 1;
259
260 ASSERT(zn->zn_key_intlen == 1);
261 for (int i = 0; i < len; cp++, i++) {
262 h = (h >> 8) ^
263 zfs_crc64_table[(h ^ *cp) & 0xFF];
264 }
265 }
266 }
267 /*
268 * Don't use all 64 bits, since we need some in the cookie for
269 * the collision differentiator. We MUST use the high bits,
270 * since those are the ones that we first pay attention to when
271 * choosing the bucket.
272 */
273 h &= ~((1ULL << (64 - zap_hashbits(zap))) - 1);
274
275 return (h);
276 }
277
278 static int
zap_lock_impl(dnode_t * dn,dmu_buf_t * db,dmu_tx_t * tx,krw_t lti,boolean_t fatreader,boolean_t adding,zap_t ** zapp)279 zap_lock_impl(dnode_t *dn, dmu_buf_t *db, dmu_tx_t *tx,
280 krw_t lti, boolean_t fatreader, boolean_t adding, zap_t **zapp)
281 {
282 ASSERT0(db->db_offset);
283 objset_t *os = dmu_buf_get_objset(db);
284 uint64_t obj = db->db_object;
285
286 *zapp = NULL;
287
288 if (DMU_OT_BYTESWAP(dn->dn_type) != DMU_BSWAP_ZAP)
289 return (SET_ERROR(EINVAL));
290
291 zap_t *zap = dmu_buf_get_user(db);
292 if (zap == NULL) {
293 zap = mzap_open(db);
294 if (zap == NULL) {
295 /*
296 * mzap_open() didn't like what it saw on-disk.
297 * Check for corruption!
298 */
299 return (SET_ERROR(EIO));
300 }
301 }
302
303 /*
304 * We're checking zap_ismicro without the lock held, in order to
305 * tell what type of lock we want. Once we have some sort of
306 * lock, see if it really is the right type. In practice this
307 * can only be different if it was upgraded from micro to fat,
308 * and micro wanted WRITER but fat only needs READER.
309 */
310 krw_t lt = (!zap->zap_ismicro && fatreader) ? RW_READER : lti;
311 rw_enter(&zap->zap_rwlock, lt);
312 if (lt != ((!zap->zap_ismicro && fatreader) ? RW_READER : lti)) {
313 /* it was upgraded, now we only need reader */
314 ASSERT(lt == RW_WRITER);
315 ASSERT(RW_READER ==
316 ((!zap->zap_ismicro && fatreader) ? RW_READER : lti));
317 rw_downgrade(&zap->zap_rwlock);
318 lt = RW_READER;
319 }
320
321 zap->zap_objset = os;
322 zap->zap_dnode = dn;
323
324 if (lt == RW_WRITER)
325 dmu_buf_will_dirty(db, tx);
326
327 ASSERT3P(zap->zap_dbuf, ==, db);
328
329 ASSERT(!zap->zap_ismicro ||
330 zap->zap_m.zap_num_entries <= zap->zap_m.zap_num_chunks);
331 if (zap->zap_ismicro && tx && adding &&
332 zap->zap_m.zap_num_entries == zap->zap_m.zap_num_chunks) {
333 uint64_t newsz = db->db_size + SPA_MINBLOCKSIZE;
334 if (newsz > zap_get_micro_max_size(dmu_objset_spa(os))) {
335 dprintf("upgrading obj %llu: num_entries=%u\n",
336 (u_longlong_t)obj, zap->zap_m.zap_num_entries);
337 *zapp = zap;
338 int err = mzap_upgrade(zapp, tx, 0);
339 if (err != 0)
340 rw_exit(&zap->zap_rwlock);
341 return (err);
342 }
343 VERIFY0(dmu_object_set_blocksize(os, obj, newsz, 0, tx));
344 zap->zap_m.zap_num_chunks =
345 db->db_size / MZAP_ENT_LEN - 1;
346
347 if (newsz > SPA_OLD_MAXBLOCKSIZE) {
348 dsl_dataset_t *ds = dmu_objset_ds(os);
349 if (!dsl_dataset_feature_is_active(ds,
350 SPA_FEATURE_LARGE_MICROZAP)) {
351 /*
352 * A microzap just grew beyond the old limit
353 * for the first time, so we have to ensure the
354 * feature flag is activated.
355 * zap_get_micro_max_size() won't let us get
356 * here if the feature is not enabled, so we
357 * don't need any other checks beforehand.
358 *
359 * Since we're in open context, we can't
360 * activate the feature directly, so we instead
361 * flag it on the dataset for next sync.
362 */
363 dsl_dataset_dirty(ds, tx);
364 mutex_enter(&ds->ds_lock);
365 ds->ds_feature_activation
366 [SPA_FEATURE_LARGE_MICROZAP] =
367 (void *)B_TRUE;
368 mutex_exit(&ds->ds_lock);
369 }
370 }
371 }
372
373 *zapp = zap;
374 return (0);
375 }
376
377 int
zap_lock_by_dnode(dnode_t * dn,dmu_tx_t * tx,krw_t lti,boolean_t fatreader,boolean_t adding,const void * tag,zap_t ** zapp)378 zap_lock_by_dnode(dnode_t *dn, dmu_tx_t *tx,
379 krw_t lti, boolean_t fatreader, boolean_t adding, const void *tag,
380 zap_t **zapp)
381 {
382 dmu_buf_t *db;
383 int err;
384
385 err = dmu_buf_hold_by_dnode(dn, 0, tag, &db, DMU_READ_NO_PREFETCH);
386 if (err != 0)
387 return (err);
388 err = zap_lock_impl(dn, db, tx, lti, fatreader, adding, zapp);
389 if (err != 0)
390 dmu_buf_rele(db, tag);
391 else
392 VERIFY(dnode_add_ref(dn, tag));
393 return (err);
394 }
395
396 int
zap_lock(objset_t * os,uint64_t obj,dmu_tx_t * tx,krw_t lti,boolean_t fatreader,boolean_t adding,const void * tag,zap_t ** zapp)397 zap_lock(objset_t *os, uint64_t obj, dmu_tx_t *tx,
398 krw_t lti, boolean_t fatreader, boolean_t adding, const void *tag,
399 zap_t **zapp)
400 {
401 dnode_t *dn;
402 int err;
403
404 err = dnode_hold(os, obj, tag, &dn);
405 if (err != 0)
406 return (err);
407 err = zap_lock_by_dnode(dn, tx, lti, fatreader, adding, tag, zapp);
408 dnode_rele(dn, tag);
409 return (err);
410 }
411
412 void
zap_unlock(zap_t * zap,const void * tag)413 zap_unlock(zap_t *zap, const void *tag)
414 {
415 rw_exit(&zap->zap_rwlock);
416 dnode_rele(zap->zap_dnode, tag);
417 dmu_buf_rele(zap->zap_dbuf, tag);
418 }
419
420 int
zap_lock_try_upgrade(zap_t * zap,dmu_tx_t * tx)421 zap_lock_try_upgrade(zap_t *zap, dmu_tx_t *tx)
422 {
423 if (RW_WRITE_HELD(&zap->zap_rwlock))
424 /* Already have writer, nothing to do. */
425 return (1);
426
427 /* Try to upgrade the lock in-place. */
428 if (rw_tryupgrade(&zap->zap_rwlock)) {
429 /*
430 * Got it, mark buffer dirty, since we only do that in
431 * zap_lock_impl() for writer.
432 */
433 dmu_buf_will_dirty(zap->zap_dbuf, tx);
434 return (1);
435 }
436
437 return (0);
438 }
439
440 void
zap_lock_upgrade(zap_t * zap,dmu_tx_t * tx)441 zap_lock_upgrade(zap_t *zap, dmu_tx_t *tx)
442 {
443 if (zap_lock_try_upgrade(zap, tx))
444 return;
445
446 /*
447 * It's safe to drop the lock here because we still have a hold on
448 * zap_dbuf, which prevents the dbuf being evicted and the zap_t being
449 * deallocated.
450 */
451 rw_exit(&zap->zap_rwlock);
452
453 rw_enter(&zap->zap_rwlock, RW_WRITER);
454 dmu_buf_will_dirty(zap->zap_dbuf, tx);
455 }
456
457 void
zap_evict_sync(void * dbu)458 zap_evict_sync(void *dbu)
459 {
460 zap_t *zap = dbu;
461
462 rw_destroy(&zap->zap_rwlock);
463
464 if (zap->zap_ismicro)
465 mze_destroy(zap);
466 else
467 mutex_destroy(&zap->zap_f.zap_num_entries_mtx);
468
469 kmem_free(zap, sizeof (zap_t));
470 }
471
472 uint64_t
zap_getflags(zap_t * zap)473 zap_getflags(zap_t *zap)
474 {
475 if (zap->zap_ismicro)
476 return (0);
477 return (zap_f_phys(zap)->zap_flags);
478 }
479
480 int
zap_hashbits(zap_t * zap)481 zap_hashbits(zap_t *zap)
482 {
483 if (zap_getflags(zap) & ZAP_FLAG_HASH64)
484 return (48);
485 else
486 return (28);
487 }
488
489 uint32_t
zap_maxcd(zap_t * zap)490 zap_maxcd(zap_t *zap)
491 {
492 if (zap_getflags(zap) & ZAP_FLAG_HASH64)
493 return ((1<<16)-1);
494 else
495 return (-1U);
496 }
497
498 /* DNU byteswap callback for DMU_BSWAP_ZAP, see dmu_ot_byteswap. */
499 void
zap_byteswap(void * buf,size_t size)500 zap_byteswap(void *buf, size_t size)
501 {
502 uint64_t block_type = *(uint64_t *)buf;
503
504 if (block_type == ZBT_MICRO || block_type == BSWAP_64(ZBT_MICRO)) {
505 /* ASSERT(magic == ZAP_LEAF_MAGIC); */
506 mzap_byteswap(buf, size);
507 } else {
508 fzap_byteswap(buf, size);
509 }
510 }
511
512 /*
513 * Cursor attribute allocator/free. Part of the public interface in zap.h,
514 * in this file to get access to the kmem caches.
515 */
516 static zap_attribute_t *
zap_attribute_alloc_impl(boolean_t longname)517 zap_attribute_alloc_impl(boolean_t longname)
518 {
519 zap_attribute_t *za;
520
521 za = kmem_cache_alloc((longname)? zap_attr_long_cache : zap_attr_cache,
522 KM_SLEEP);
523 za->za_name_len = (longname)? ZAP_MAXNAMELEN_NEW : ZAP_MAXNAMELEN;
524 return (za);
525 }
526
527 zap_attribute_t *
zap_attribute_alloc(void)528 zap_attribute_alloc(void)
529 {
530 return (zap_attribute_alloc_impl(B_FALSE));
531 }
532
533 zap_attribute_t *
zap_attribute_long_alloc(void)534 zap_attribute_long_alloc(void)
535 {
536 return (zap_attribute_alloc_impl(B_TRUE));
537 }
538
539 void
zap_attribute_free(zap_attribute_t * za)540 zap_attribute_free(zap_attribute_t *za)
541 {
542 if (za->za_name_len == ZAP_MAXNAMELEN) {
543 kmem_cache_free(zap_attr_cache, za);
544 } else {
545 ASSERT3U(za->za_name_len, ==, ZAP_MAXNAMELEN_NEW);
546 kmem_cache_free(zap_attr_long_cache, za);
547 }
548 }
549