1 /*- 2 * SPDX-License-Identifier: BSD-2-Clause 3 * 4 * Copyright (c) 2022 The FreeBSD Foundation 5 * 6 * This software was developed by Mark Johnston under sponsorship from 7 * the FreeBSD Foundation. 8 * 9 * Redistribution and use in source and binary forms, with or without 10 * modification, are permitted provided that the following conditions are 11 * met: 12 * 1. Redistributions of source code must retain the above copyright 13 * notice, this list of conditions and the following disclaimer. 14 * 2. Redistributions in binary form must reproduce the above copyright 15 * notice, this list of conditions and the following disclaimer in 16 * the documentation and/or other materials provided with the distribution. 17 * 18 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND 19 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 20 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 21 * ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE 22 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 23 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS 24 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 25 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 26 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY 27 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 28 * SUCH DAMAGE. 29 */ 30 31 #include <sys/types.h> 32 #include <sys/endian.h> 33 34 #include <assert.h> 35 #include <stddef.h> 36 #include <stdlib.h> 37 #include <string.h> 38 39 #include <util.h> 40 41 #include "makefs.h" 42 #include "zfs.h" 43 44 typedef struct zfs_zap_entry { 45 char *name; /* entry key, private copy */ 46 uint64_t hash; /* key hash */ 47 union { 48 uint8_t *valp; 49 uint16_t *val16p; 50 uint32_t *val32p; 51 uint64_t *val64p; 52 }; /* entry value, an integer array */ 53 uint64_t val64; /* embedded value for a common case */ 54 size_t intsz; /* array element size; 1, 2, 4 or 8 */ 55 size_t intcnt; /* array size */ 56 STAILQ_ENTRY(zfs_zap_entry) next; 57 } zfs_zap_entry_t; 58 59 struct zfs_zap { 60 STAILQ_HEAD(, zfs_zap_entry) kvps; 61 uint64_t hashsalt; /* key hash input */ 62 unsigned long kvpcnt; /* number of key-value pairs */ 63 unsigned long chunks; /* count of chunks needed for fat ZAP */ 64 bool micro; /* can this be a micro ZAP? */ 65 66 dnode_phys_t *dnode; /* backpointer */ 67 zfs_objset_t *os; /* backpointer */ 68 }; 69 70 static uint16_t 71 zap_entry_chunks(zfs_zap_entry_t *ent) 72 { 73 return (1 + howmany(strlen(ent->name) + 1, ZAP_LEAF_ARRAY_BYTES) + 74 howmany(ent->intsz * ent->intcnt, ZAP_LEAF_ARRAY_BYTES)); 75 } 76 77 static uint64_t 78 zap_hash(uint64_t salt, const char *name) 79 { 80 static uint64_t crc64_table[256]; 81 const uint64_t crc64_poly = 0xC96C5795D7870F42UL; 82 const uint8_t *cp; 83 uint64_t crc; 84 uint8_t c; 85 86 assert(salt != 0); 87 if (crc64_table[128] == 0) { 88 for (int i = 0; i < 256; i++) { 89 uint64_t *t; 90 91 t = crc64_table + i; 92 *t = i; 93 for (int j = 8; j > 0; j--) 94 *t = (*t >> 1) ^ (-(*t & 1) & crc64_poly); 95 } 96 } 97 assert(crc64_table[128] == crc64_poly); 98 99 for (cp = (const uint8_t *)name, crc = salt; (c = *cp) != '\0'; cp++) 100 crc = (crc >> 8) ^ crc64_table[(crc ^ c) & 0xFF]; 101 102 /* 103 * Only use 28 bits, since we need 4 bits in the cookie for the 104 * collision differentiator. We MUST use the high bits, since 105 * those are the ones that we first pay attention to when 106 * choosing the bucket. 107 */ 108 crc &= ~((1ULL << (64 - ZAP_HASHBITS)) - 1); 109 110 return (crc); 111 } 112 113 zfs_zap_t * 114 zap_alloc(zfs_objset_t *os, dnode_phys_t *dnode) 115 { 116 zfs_zap_t *zap; 117 118 zap = ecalloc(1, sizeof(*zap)); 119 STAILQ_INIT(&zap->kvps); 120 zap->hashsalt = ((uint64_t)random() << 32) | random(); 121 zap->micro = true; 122 zap->kvpcnt = 0; 123 zap->chunks = 0; 124 zap->dnode = dnode; 125 zap->os = os; 126 return (zap); 127 } 128 129 void 130 zap_add(zfs_zap_t *zap, const char *name, size_t intsz, size_t intcnt, 131 const uint8_t *val) 132 { 133 zfs_zap_entry_t *ent; 134 135 assert(intsz == 1 || intsz == 2 || intsz == 4 || intsz == 8); 136 assert(strlen(name) + 1 <= ZAP_MAXNAMELEN); 137 assert(intcnt <= ZAP_MAXVALUELEN && intcnt * intsz <= ZAP_MAXVALUELEN); 138 139 ent = ecalloc(1, sizeof(*ent)); 140 ent->name = estrdup(name); 141 ent->hash = zap_hash(zap->hashsalt, ent->name); 142 ent->intsz = intsz; 143 ent->intcnt = intcnt; 144 if (intsz == sizeof(uint64_t) && intcnt == 1) { 145 /* 146 * Micro-optimization to elide a memory allocation in that most 147 * common case where this is a directory entry. 148 */ 149 ent->val64p = &ent->val64; 150 } else { 151 ent->valp = ecalloc(intcnt, intsz); 152 } 153 memcpy(ent->valp, val, intcnt * intsz); 154 zap->kvpcnt++; 155 zap->chunks += zap_entry_chunks(ent); 156 STAILQ_INSERT_TAIL(&zap->kvps, ent, next); 157 158 if (zap->micro && (intcnt != 1 || intsz != sizeof(uint64_t) || 159 strlen(name) + 1 > MZAP_NAME_LEN || zap->kvpcnt > MZAP_ENT_MAX)) 160 zap->micro = false; 161 } 162 163 void 164 zap_add_uint64(zfs_zap_t *zap, const char *name, uint64_t val) 165 { 166 zap_add(zap, name, sizeof(uint64_t), 1, (uint8_t *)&val); 167 } 168 169 void 170 zap_add_uint64_self(zfs_zap_t *zap, uint64_t val) 171 { 172 char name[32]; 173 174 snprintf(name, sizeof(name), "%jx", (uintmax_t)val); 175 zap_add(zap, name, sizeof(uint64_t), 1, (uint8_t *)&val); 176 } 177 178 void 179 zap_add_string(zfs_zap_t *zap, const char *name, const char *val) 180 { 181 zap_add(zap, name, 1, strlen(val) + 1, val); 182 } 183 184 bool 185 zap_entry_exists(zfs_zap_t *zap, const char *name) 186 { 187 zfs_zap_entry_t *ent; 188 189 STAILQ_FOREACH(ent, &zap->kvps, next) { 190 if (strcmp(ent->name, name) == 0) 191 return (true); 192 } 193 return (false); 194 } 195 196 static void 197 zap_micro_write(zfs_opt_t *zfs, zfs_zap_t *zap) 198 { 199 dnode_phys_t *dnode; 200 zfs_zap_entry_t *ent; 201 mzap_phys_t *mzap; 202 mzap_ent_phys_t *ment; 203 off_t bytes, loc; 204 205 memset(zfs->filebuf, 0, sizeof(zfs->filebuf)); 206 mzap = (mzap_phys_t *)&zfs->filebuf[0]; 207 mzap->mz_block_type = ZBT_MICRO; 208 mzap->mz_salt = zap->hashsalt; 209 mzap->mz_normflags = 0; 210 211 bytes = sizeof(*mzap) + (zap->kvpcnt - 1) * sizeof(*ment); 212 assert(bytes <= (off_t)MZAP_MAX_BLKSZ); 213 214 ment = &mzap->mz_chunk[0]; 215 STAILQ_FOREACH(ent, &zap->kvps, next) { 216 memcpy(&ment->mze_value, ent->valp, ent->intsz * ent->intcnt); 217 ment->mze_cd = 0; /* XXX-MJ */ 218 strlcpy(ment->mze_name, ent->name, sizeof(ment->mze_name)); 219 ment++; 220 } 221 222 loc = objset_space_alloc(zfs, zap->os, &bytes); 223 224 dnode = zap->dnode; 225 dnode->dn_maxblkid = 0; 226 dnode->dn_datablkszsec = bytes >> MINBLOCKSHIFT; 227 228 vdev_pwrite_dnode_data(zfs, dnode, zfs->filebuf, bytes, loc); 229 } 230 231 /* 232 * Write some data to the fat ZAP leaf chunk starting at index "li". 233 * 234 * Note that individual integers in the value may be split among consecutive 235 * leaves. 236 */ 237 static void 238 zap_fat_write_array_chunk(zap_leaf_t *l, uint16_t li, size_t sz, 239 const uint8_t *val) 240 { 241 struct zap_leaf_array *la; 242 243 assert(sz <= ZAP_MAXVALUELEN); 244 245 for (uint16_t n, resid = sz; resid > 0; resid -= n, val += n, li++) { 246 n = MIN(resid, ZAP_LEAF_ARRAY_BYTES); 247 248 la = &ZAP_LEAF_CHUNK(l, li).l_array; 249 assert(la->la_type == ZAP_CHUNK_FREE); 250 la->la_type = ZAP_CHUNK_ARRAY; 251 memcpy(la->la_array, val, n); 252 la->la_next = li + 1; 253 } 254 la->la_next = 0xffff; 255 } 256 257 /* 258 * Find the shortest hash prefix length which lets us distribute keys without 259 * overflowing a leaf block. This is not (space) optimal, but is simple, and 260 * directories large enough to overflow a single 128KB leaf block are uncommon. 261 */ 262 static unsigned int 263 zap_fat_write_prefixlen(zfs_zap_t *zap, zap_leaf_t *l) 264 { 265 zfs_zap_entry_t *ent; 266 unsigned int prefixlen; 267 268 if (zap->chunks <= ZAP_LEAF_NUMCHUNKS(l)) { 269 /* 270 * All chunks will fit in a single leaf block. 271 */ 272 return (0); 273 } 274 275 for (prefixlen = 1; prefixlen < (unsigned int)l->l_bs; prefixlen++) { 276 uint32_t *leafchunks; 277 278 leafchunks = ecalloc(1u << prefixlen, sizeof(*leafchunks)); 279 STAILQ_FOREACH(ent, &zap->kvps, next) { 280 uint64_t li; 281 uint16_t chunks; 282 283 li = ZAP_HASH_IDX(ent->hash, prefixlen); 284 285 chunks = zap_entry_chunks(ent); 286 if (ZAP_LEAF_NUMCHUNKS(l) - leafchunks[li] < chunks) { 287 /* 288 * Not enough space, grow the prefix and retry. 289 */ 290 break; 291 } 292 leafchunks[li] += chunks; 293 } 294 free(leafchunks); 295 296 if (ent == NULL) { 297 /* 298 * Everything fits, we're done. 299 */ 300 break; 301 } 302 } 303 304 /* 305 * If this fails, then we need to expand the pointer table. For now 306 * this situation is unhandled since it is hard to trigger. 307 */ 308 assert(prefixlen < (unsigned int)l->l_bs); 309 310 return (prefixlen); 311 } 312 313 /* 314 * Initialize a fat ZAP leaf block. 315 */ 316 static void 317 zap_fat_write_leaf_init(zap_leaf_t *l, uint64_t prefix, int prefixlen) 318 { 319 zap_leaf_phys_t *leaf; 320 321 leaf = l->l_phys; 322 323 leaf->l_hdr.lh_block_type = ZBT_LEAF; 324 leaf->l_hdr.lh_magic = ZAP_LEAF_MAGIC; 325 leaf->l_hdr.lh_nfree = ZAP_LEAF_NUMCHUNKS(l); 326 leaf->l_hdr.lh_prefix = prefix; 327 leaf->l_hdr.lh_prefix_len = prefixlen; 328 329 /* Initialize the leaf hash table. */ 330 assert(leaf->l_hdr.lh_nfree < 0xffff); 331 memset(leaf->l_hash, 0xff, 332 ZAP_LEAF_HASH_NUMENTRIES(l) * sizeof(*leaf->l_hash)); 333 334 /* Initialize the leaf chunks. */ 335 for (uint16_t i = 0; i < ZAP_LEAF_NUMCHUNKS(l); i++) { 336 struct zap_leaf_free *lf; 337 338 lf = &ZAP_LEAF_CHUNK(l, i).l_free; 339 lf->lf_type = ZAP_CHUNK_FREE; 340 if (i + 1 == ZAP_LEAF_NUMCHUNKS(l)) 341 lf->lf_next = 0xffff; 342 else 343 lf->lf_next = i + 1; 344 } 345 } 346 347 static void 348 zap_fat_write(zfs_opt_t *zfs, zfs_zap_t *zap) 349 { 350 struct dnode_cursor *c; 351 zap_leaf_t l; 352 zap_phys_t *zaphdr; 353 struct zap_table_phys *zt; 354 zfs_zap_entry_t *ent; 355 dnode_phys_t *dnode; 356 uint8_t *leafblks; 357 uint64_t lblkcnt, *ptrhasht; 358 off_t loc, blksz; 359 size_t blkshift; 360 unsigned int prefixlen; 361 int ptrcnt; 362 363 /* 364 * For simplicity, always use the largest block size. This should be ok 365 * since most directories will be micro ZAPs, but it's space inefficient 366 * for small ZAPs and might need to be revisited. 367 */ 368 blkshift = MAXBLOCKSHIFT; 369 blksz = (off_t)1 << blkshift; 370 371 /* 372 * Embedded pointer tables give up to 8192 entries. This ought to be 373 * enough for anything except massive directories. 374 */ 375 ptrcnt = (blksz / 2) / sizeof(uint64_t); 376 377 memset(zfs->filebuf, 0, sizeof(zfs->filebuf)); 378 zaphdr = (zap_phys_t *)&zfs->filebuf[0]; 379 zaphdr->zap_block_type = ZBT_HEADER; 380 zaphdr->zap_magic = ZAP_MAGIC; 381 zaphdr->zap_num_entries = zap->kvpcnt; 382 zaphdr->zap_salt = zap->hashsalt; 383 384 l.l_bs = blkshift; 385 l.l_phys = NULL; 386 387 zt = &zaphdr->zap_ptrtbl; 388 zt->zt_blk = 0; 389 zt->zt_numblks = 0; 390 zt->zt_shift = flsll(ptrcnt) - 1; 391 zt->zt_nextblk = 0; 392 zt->zt_blks_copied = 0; 393 394 /* 395 * How many leaf blocks do we need? Initialize them and update the 396 * header. 397 */ 398 prefixlen = zap_fat_write_prefixlen(zap, &l); 399 lblkcnt = (uint64_t)1 << prefixlen; 400 leafblks = ecalloc(lblkcnt, blksz); 401 for (unsigned int li = 0; li < lblkcnt; li++) { 402 l.l_phys = (zap_leaf_phys_t *)(leafblks + li * blksz); 403 zap_fat_write_leaf_init(&l, li, prefixlen); 404 } 405 zaphdr->zap_num_leafs = lblkcnt; 406 zaphdr->zap_freeblk = lblkcnt + 1; 407 408 /* 409 * For each entry, figure out which leaf block it belongs to based on 410 * the upper bits of its hash, allocate chunks from that leaf, and fill 411 * them out. 412 */ 413 ptrhasht = (uint64_t *)(&zfs->filebuf[0] + blksz / 2); 414 STAILQ_FOREACH(ent, &zap->kvps, next) { 415 struct zap_leaf_entry *le; 416 uint16_t *lptr; 417 uint64_t hi, li; 418 uint16_t namelen, nchunks, nnamechunks, nvalchunks; 419 420 hi = ZAP_HASH_IDX(ent->hash, zt->zt_shift); 421 li = ZAP_HASH_IDX(ent->hash, prefixlen); 422 assert(ptrhasht[hi] == 0 || ptrhasht[hi] == li + 1); 423 ptrhasht[hi] = li + 1; 424 l.l_phys = (zap_leaf_phys_t *)(leafblks + li * blksz); 425 426 namelen = strlen(ent->name) + 1; 427 428 /* 429 * How many leaf chunks do we need for this entry? 430 */ 431 nnamechunks = howmany(namelen, ZAP_LEAF_ARRAY_BYTES); 432 nvalchunks = howmany(ent->intcnt, 433 ZAP_LEAF_ARRAY_BYTES / ent->intsz); 434 nchunks = 1 + nnamechunks + nvalchunks; 435 436 /* 437 * Allocate a run of free leaf chunks for this entry, 438 * potentially extending a hash chain. 439 */ 440 assert(l.l_phys->l_hdr.lh_nfree >= nchunks); 441 l.l_phys->l_hdr.lh_nfree -= nchunks; 442 l.l_phys->l_hdr.lh_nentries++; 443 lptr = ZAP_LEAF_HASH_ENTPTR(&l, ent->hash); 444 while (*lptr != 0xffff) { 445 assert(*lptr < ZAP_LEAF_NUMCHUNKS(&l)); 446 le = ZAP_LEAF_ENTRY(&l, *lptr); 447 assert(le->le_type == ZAP_CHUNK_ENTRY); 448 le->le_cd++; 449 lptr = &le->le_next; 450 } 451 *lptr = l.l_phys->l_hdr.lh_freelist; 452 l.l_phys->l_hdr.lh_freelist += nchunks; 453 assert(l.l_phys->l_hdr.lh_freelist <= 454 ZAP_LEAF_NUMCHUNKS(&l)); 455 if (l.l_phys->l_hdr.lh_freelist == 456 ZAP_LEAF_NUMCHUNKS(&l)) 457 l.l_phys->l_hdr.lh_freelist = 0xffff; 458 459 /* 460 * Integer values must be stored in big-endian format. 461 */ 462 switch (ent->intsz) { 463 case 1: 464 break; 465 case 2: 466 for (uint16_t *v = ent->val16p; 467 v - ent->val16p < (ptrdiff_t)ent->intcnt; 468 v++) 469 *v = htobe16(*v); 470 break; 471 case 4: 472 for (uint32_t *v = ent->val32p; 473 v - ent->val32p < (ptrdiff_t)ent->intcnt; 474 v++) 475 *v = htobe32(*v); 476 break; 477 case 8: 478 for (uint64_t *v = ent->val64p; 479 v - ent->val64p < (ptrdiff_t)ent->intcnt; 480 v++) 481 *v = htobe64(*v); 482 break; 483 default: 484 assert(0); 485 } 486 487 /* 488 * Finally, write out the leaf chunks for this entry. 489 */ 490 le = ZAP_LEAF_ENTRY(&l, *lptr); 491 assert(le->le_type == ZAP_CHUNK_FREE); 492 le->le_type = ZAP_CHUNK_ENTRY; 493 le->le_next = 0xffff; 494 le->le_name_chunk = *lptr + 1; 495 le->le_name_numints = namelen; 496 le->le_value_chunk = *lptr + 1 + nnamechunks; 497 le->le_value_intlen = ent->intsz; 498 le->le_value_numints = ent->intcnt; 499 le->le_hash = ent->hash; 500 zap_fat_write_array_chunk(&l, *lptr + 1, namelen, ent->name); 501 zap_fat_write_array_chunk(&l, *lptr + 1 + nnamechunks, 502 ent->intcnt * ent->intsz, ent->valp); 503 } 504 505 /* 506 * Initialize unused slots of the pointer table. 507 */ 508 for (int i = 0; i < ptrcnt; i++) 509 if (ptrhasht[i] == 0) 510 ptrhasht[i] = (i >> (zt->zt_shift - prefixlen)) + 1; 511 512 /* 513 * Write the whole thing to disk. 514 */ 515 dnode = zap->dnode; 516 dnode->dn_datablkszsec = blksz >> MINBLOCKSHIFT; 517 dnode->dn_maxblkid = lblkcnt + 1; 518 519 c = dnode_cursor_init(zfs, zap->os, zap->dnode, 520 (lblkcnt + 1) * blksz, blksz); 521 522 loc = objset_space_alloc(zfs, zap->os, &blksz); 523 vdev_pwrite_dnode_indir(zfs, dnode, 0, 1, zfs->filebuf, blksz, loc, 524 dnode_cursor_next(zfs, c, 0)); 525 526 for (uint64_t i = 0; i < lblkcnt; i++) { 527 loc = objset_space_alloc(zfs, zap->os, &blksz); 528 vdev_pwrite_dnode_indir(zfs, dnode, 0, 1, leafblks + i * blksz, 529 blksz, loc, dnode_cursor_next(zfs, c, (i + 1) * blksz)); 530 } 531 532 dnode_cursor_finish(zfs, c); 533 534 free(leafblks); 535 } 536 537 void 538 zap_write(zfs_opt_t *zfs, zfs_zap_t *zap) 539 { 540 zfs_zap_entry_t *ent; 541 542 if (zap->micro) { 543 zap_micro_write(zfs, zap); 544 } else { 545 assert(!STAILQ_EMPTY(&zap->kvps)); 546 assert(zap->kvpcnt > 0); 547 zap_fat_write(zfs, zap); 548 } 549 550 while ((ent = STAILQ_FIRST(&zap->kvps)) != NULL) { 551 STAILQ_REMOVE_HEAD(&zap->kvps, next); 552 if (ent->val64p != &ent->val64) 553 free(ent->valp); 554 free(ent->name); 555 free(ent); 556 } 557 free(zap); 558 } 559