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 /* 23 * Copyright (c) 2009, 2010, Oracle and/or its affiliates. All rights reserved. 24 * Copyright (c) 2012, 2015 by Delphix. All rights reserved. 25 */ 26 27 #include <sys/zfs_context.h> 28 #include <sys/spa.h> 29 #include <sys/spa_impl.h> 30 #include <sys/zio.h> 31 #include <sys/ddt.h> 32 #include <sys/zap.h> 33 #include <sys/dmu_tx.h> 34 #include <sys/arc.h> 35 #include <sys/dsl_pool.h> 36 #include <sys/zio_checksum.h> 37 #include <sys/zio_compress.h> 38 #include <sys/dsl_scan.h> 39 40 /* 41 * Enable/disable prefetching of dedup-ed blocks which are going to be freed. 42 */ 43 int zfs_dedup_prefetch = 1; 44 45 SYSCTL_DECL(_vfs_zfs); 46 SYSCTL_NODE(_vfs_zfs, OID_AUTO, dedup, CTLFLAG_RW, 0, "ZFS DEDUP"); 47 SYSCTL_INT(_vfs_zfs_dedup, OID_AUTO, prefetch, CTLFLAG_RWTUN, &zfs_dedup_prefetch, 48 0, "Enable/disable prefetching of dedup-ed blocks which are going to be freed"); 49 50 static const ddt_ops_t *ddt_ops[DDT_TYPES] = { 51 &ddt_zap_ops, 52 }; 53 54 static const char *ddt_class_name[DDT_CLASSES] = { 55 "ditto", 56 "duplicate", 57 "unique", 58 }; 59 60 static void 61 ddt_object_create(ddt_t *ddt, enum ddt_type type, enum ddt_class class, 62 dmu_tx_t *tx) 63 { 64 spa_t *spa = ddt->ddt_spa; 65 objset_t *os = ddt->ddt_os; 66 uint64_t *objectp = &ddt->ddt_object[type][class]; 67 boolean_t prehash = zio_checksum_table[ddt->ddt_checksum].ci_flags & 68 ZCHECKSUM_FLAG_DEDUP; 69 char name[DDT_NAMELEN]; 70 71 ddt_object_name(ddt, type, class, name); 72 73 ASSERT(*objectp == 0); 74 VERIFY(ddt_ops[type]->ddt_op_create(os, objectp, tx, prehash) == 0); 75 ASSERT(*objectp != 0); 76 77 VERIFY(zap_add(os, DMU_POOL_DIRECTORY_OBJECT, name, 78 sizeof (uint64_t), 1, objectp, tx) == 0); 79 80 VERIFY(zap_add(os, spa->spa_ddt_stat_object, name, 81 sizeof (uint64_t), sizeof (ddt_histogram_t) / sizeof (uint64_t), 82 &ddt->ddt_histogram[type][class], tx) == 0); 83 } 84 85 static void 86 ddt_object_destroy(ddt_t *ddt, enum ddt_type type, enum ddt_class class, 87 dmu_tx_t *tx) 88 { 89 spa_t *spa = ddt->ddt_spa; 90 objset_t *os = ddt->ddt_os; 91 uint64_t *objectp = &ddt->ddt_object[type][class]; 92 uint64_t count; 93 char name[DDT_NAMELEN]; 94 95 ddt_object_name(ddt, type, class, name); 96 97 ASSERT(*objectp != 0); 98 VERIFY(ddt_object_count(ddt, type, class, &count) == 0 && count == 0); 99 ASSERT(ddt_histogram_empty(&ddt->ddt_histogram[type][class])); 100 VERIFY(zap_remove(os, DMU_POOL_DIRECTORY_OBJECT, name, tx) == 0); 101 VERIFY(zap_remove(os, spa->spa_ddt_stat_object, name, tx) == 0); 102 VERIFY(ddt_ops[type]->ddt_op_destroy(os, *objectp, tx) == 0); 103 bzero(&ddt->ddt_object_stats[type][class], sizeof (ddt_object_t)); 104 105 *objectp = 0; 106 } 107 108 static int 109 ddt_object_load(ddt_t *ddt, enum ddt_type type, enum ddt_class class) 110 { 111 ddt_object_t *ddo = &ddt->ddt_object_stats[type][class]; 112 dmu_object_info_t doi; 113 uint64_t count; 114 char name[DDT_NAMELEN]; 115 int error; 116 117 ddt_object_name(ddt, type, class, name); 118 119 error = zap_lookup(ddt->ddt_os, DMU_POOL_DIRECTORY_OBJECT, name, 120 sizeof (uint64_t), 1, &ddt->ddt_object[type][class]); 121 122 if (error != 0) 123 return (error); 124 125 VERIFY0(zap_lookup(ddt->ddt_os, ddt->ddt_spa->spa_ddt_stat_object, name, 126 sizeof (uint64_t), sizeof (ddt_histogram_t) / sizeof (uint64_t), 127 &ddt->ddt_histogram[type][class])); 128 129 /* 130 * Seed the cached statistics. 131 */ 132 VERIFY(ddt_object_info(ddt, type, class, &doi) == 0); 133 134 error = ddt_object_count(ddt, type, class, &count); 135 if (error) 136 return error; 137 138 ddo->ddo_count = count; 139 ddo->ddo_dspace = doi.doi_physical_blocks_512 << 9; 140 ddo->ddo_mspace = doi.doi_fill_count * doi.doi_data_block_size; 141 142 return (0); 143 } 144 145 static void 146 ddt_object_sync(ddt_t *ddt, enum ddt_type type, enum ddt_class class, 147 dmu_tx_t *tx) 148 { 149 ddt_object_t *ddo = &ddt->ddt_object_stats[type][class]; 150 dmu_object_info_t doi; 151 uint64_t count; 152 char name[DDT_NAMELEN]; 153 154 ddt_object_name(ddt, type, class, name); 155 156 VERIFY(zap_update(ddt->ddt_os, ddt->ddt_spa->spa_ddt_stat_object, name, 157 sizeof (uint64_t), sizeof (ddt_histogram_t) / sizeof (uint64_t), 158 &ddt->ddt_histogram[type][class], tx) == 0); 159 160 /* 161 * Cache DDT statistics; this is the only time they'll change. 162 */ 163 VERIFY(ddt_object_info(ddt, type, class, &doi) == 0); 164 VERIFY(ddt_object_count(ddt, type, class, &count) == 0); 165 166 ddo->ddo_count = count; 167 ddo->ddo_dspace = doi.doi_physical_blocks_512 << 9; 168 ddo->ddo_mspace = doi.doi_fill_count * doi.doi_data_block_size; 169 } 170 171 static int 172 ddt_object_lookup(ddt_t *ddt, enum ddt_type type, enum ddt_class class, 173 ddt_entry_t *dde) 174 { 175 if (!ddt_object_exists(ddt, type, class)) 176 return (SET_ERROR(ENOENT)); 177 178 return (ddt_ops[type]->ddt_op_lookup(ddt->ddt_os, 179 ddt->ddt_object[type][class], dde)); 180 } 181 182 static void 183 ddt_object_prefetch(ddt_t *ddt, enum ddt_type type, enum ddt_class class, 184 ddt_entry_t *dde) 185 { 186 if (!ddt_object_exists(ddt, type, class)) 187 return; 188 189 ddt_ops[type]->ddt_op_prefetch(ddt->ddt_os, 190 ddt->ddt_object[type][class], dde); 191 } 192 193 int 194 ddt_object_update(ddt_t *ddt, enum ddt_type type, enum ddt_class class, 195 ddt_entry_t *dde, dmu_tx_t *tx) 196 { 197 ASSERT(ddt_object_exists(ddt, type, class)); 198 199 return (ddt_ops[type]->ddt_op_update(ddt->ddt_os, 200 ddt->ddt_object[type][class], dde, tx)); 201 } 202 203 static int 204 ddt_object_remove(ddt_t *ddt, enum ddt_type type, enum ddt_class class, 205 ddt_entry_t *dde, dmu_tx_t *tx) 206 { 207 ASSERT(ddt_object_exists(ddt, type, class)); 208 209 return (ddt_ops[type]->ddt_op_remove(ddt->ddt_os, 210 ddt->ddt_object[type][class], dde, tx)); 211 } 212 213 int 214 ddt_object_walk(ddt_t *ddt, enum ddt_type type, enum ddt_class class, 215 uint64_t *walk, ddt_entry_t *dde) 216 { 217 ASSERT(ddt_object_exists(ddt, type, class)); 218 219 return (ddt_ops[type]->ddt_op_walk(ddt->ddt_os, 220 ddt->ddt_object[type][class], dde, walk)); 221 } 222 223 int 224 ddt_object_count(ddt_t *ddt, enum ddt_type type, enum ddt_class class, uint64_t *count) 225 { 226 ASSERT(ddt_object_exists(ddt, type, class)); 227 228 return (ddt_ops[type]->ddt_op_count(ddt->ddt_os, 229 ddt->ddt_object[type][class], count)); 230 } 231 232 int 233 ddt_object_info(ddt_t *ddt, enum ddt_type type, enum ddt_class class, 234 dmu_object_info_t *doi) 235 { 236 if (!ddt_object_exists(ddt, type, class)) 237 return (SET_ERROR(ENOENT)); 238 239 return (dmu_object_info(ddt->ddt_os, ddt->ddt_object[type][class], 240 doi)); 241 } 242 243 boolean_t 244 ddt_object_exists(ddt_t *ddt, enum ddt_type type, enum ddt_class class) 245 { 246 return (!!ddt->ddt_object[type][class]); 247 } 248 249 void 250 ddt_object_name(ddt_t *ddt, enum ddt_type type, enum ddt_class class, 251 char *name) 252 { 253 (void) sprintf(name, DMU_POOL_DDT, 254 zio_checksum_table[ddt->ddt_checksum].ci_name, 255 ddt_ops[type]->ddt_op_name, ddt_class_name[class]); 256 } 257 258 void 259 ddt_bp_fill(const ddt_phys_t *ddp, blkptr_t *bp, uint64_t txg) 260 { 261 ASSERT(txg != 0); 262 263 for (int d = 0; d < SPA_DVAS_PER_BP; d++) 264 bp->blk_dva[d] = ddp->ddp_dva[d]; 265 BP_SET_BIRTH(bp, txg, ddp->ddp_phys_birth); 266 } 267 268 void 269 ddt_bp_create(enum zio_checksum checksum, 270 const ddt_key_t *ddk, const ddt_phys_t *ddp, blkptr_t *bp) 271 { 272 BP_ZERO(bp); 273 274 if (ddp != NULL) 275 ddt_bp_fill(ddp, bp, ddp->ddp_phys_birth); 276 277 bp->blk_cksum = ddk->ddk_cksum; 278 bp->blk_fill = 1; 279 280 BP_SET_LSIZE(bp, DDK_GET_LSIZE(ddk)); 281 BP_SET_PSIZE(bp, DDK_GET_PSIZE(ddk)); 282 BP_SET_COMPRESS(bp, DDK_GET_COMPRESS(ddk)); 283 BP_SET_CHECKSUM(bp, checksum); 284 BP_SET_TYPE(bp, DMU_OT_DEDUP); 285 BP_SET_LEVEL(bp, 0); 286 BP_SET_DEDUP(bp, 0); 287 BP_SET_BYTEORDER(bp, ZFS_HOST_BYTEORDER); 288 } 289 290 void 291 ddt_key_fill(ddt_key_t *ddk, const blkptr_t *bp) 292 { 293 ddk->ddk_cksum = bp->blk_cksum; 294 ddk->ddk_prop = 0; 295 296 DDK_SET_LSIZE(ddk, BP_GET_LSIZE(bp)); 297 DDK_SET_PSIZE(ddk, BP_GET_PSIZE(bp)); 298 DDK_SET_COMPRESS(ddk, BP_GET_COMPRESS(bp)); 299 } 300 301 void 302 ddt_phys_fill(ddt_phys_t *ddp, const blkptr_t *bp) 303 { 304 ASSERT(ddp->ddp_phys_birth == 0); 305 306 for (int d = 0; d < SPA_DVAS_PER_BP; d++) 307 ddp->ddp_dva[d] = bp->blk_dva[d]; 308 ddp->ddp_phys_birth = BP_PHYSICAL_BIRTH(bp); 309 } 310 311 void 312 ddt_phys_clear(ddt_phys_t *ddp) 313 { 314 bzero(ddp, sizeof (*ddp)); 315 } 316 317 void 318 ddt_phys_addref(ddt_phys_t *ddp) 319 { 320 ddp->ddp_refcnt++; 321 } 322 323 void 324 ddt_phys_decref(ddt_phys_t *ddp) 325 { 326 ASSERT((int64_t)ddp->ddp_refcnt > 0); 327 ddp->ddp_refcnt--; 328 } 329 330 void 331 ddt_phys_free(ddt_t *ddt, ddt_key_t *ddk, ddt_phys_t *ddp, uint64_t txg) 332 { 333 blkptr_t blk; 334 335 ddt_bp_create(ddt->ddt_checksum, ddk, ddp, &blk); 336 ddt_phys_clear(ddp); 337 zio_free(ddt->ddt_spa, txg, &blk); 338 } 339 340 ddt_phys_t * 341 ddt_phys_select(const ddt_entry_t *dde, const blkptr_t *bp) 342 { 343 ddt_phys_t *ddp = (ddt_phys_t *)dde->dde_phys; 344 345 for (int p = 0; p < DDT_PHYS_TYPES; p++, ddp++) { 346 if (DVA_EQUAL(BP_IDENTITY(bp), &ddp->ddp_dva[0]) && 347 BP_PHYSICAL_BIRTH(bp) == ddp->ddp_phys_birth) 348 return (ddp); 349 } 350 return (NULL); 351 } 352 353 uint64_t 354 ddt_phys_total_refcnt(const ddt_entry_t *dde) 355 { 356 uint64_t refcnt = 0; 357 358 for (int p = DDT_PHYS_SINGLE; p <= DDT_PHYS_TRIPLE; p++) 359 refcnt += dde->dde_phys[p].ddp_refcnt; 360 361 return (refcnt); 362 } 363 364 static void 365 ddt_stat_generate(ddt_t *ddt, ddt_entry_t *dde, ddt_stat_t *dds) 366 { 367 spa_t *spa = ddt->ddt_spa; 368 ddt_phys_t *ddp = dde->dde_phys; 369 ddt_key_t *ddk = &dde->dde_key; 370 uint64_t lsize = DDK_GET_LSIZE(ddk); 371 uint64_t psize = DDK_GET_PSIZE(ddk); 372 373 bzero(dds, sizeof (*dds)); 374 375 for (int p = 0; p < DDT_PHYS_TYPES; p++, ddp++) { 376 uint64_t dsize = 0; 377 uint64_t refcnt = ddp->ddp_refcnt; 378 379 if (ddp->ddp_phys_birth == 0) 380 continue; 381 382 for (int d = 0; d < SPA_DVAS_PER_BP; d++) 383 dsize += dva_get_dsize_sync(spa, &ddp->ddp_dva[d]); 384 385 dds->dds_blocks += 1; 386 dds->dds_lsize += lsize; 387 dds->dds_psize += psize; 388 dds->dds_dsize += dsize; 389 390 dds->dds_ref_blocks += refcnt; 391 dds->dds_ref_lsize += lsize * refcnt; 392 dds->dds_ref_psize += psize * refcnt; 393 dds->dds_ref_dsize += dsize * refcnt; 394 } 395 } 396 397 void 398 ddt_stat_add(ddt_stat_t *dst, const ddt_stat_t *src, uint64_t neg) 399 { 400 const uint64_t *s = (const uint64_t *)src; 401 uint64_t *d = (uint64_t *)dst; 402 uint64_t *d_end = (uint64_t *)(dst + 1); 403 404 ASSERT(neg == 0 || neg == -1ULL); /* add or subtract */ 405 406 while (d < d_end) 407 *d++ += (*s++ ^ neg) - neg; 408 } 409 410 static void 411 ddt_stat_update(ddt_t *ddt, ddt_entry_t *dde, uint64_t neg) 412 { 413 ddt_stat_t dds; 414 ddt_histogram_t *ddh; 415 int bucket; 416 417 ddt_stat_generate(ddt, dde, &dds); 418 419 bucket = highbit64(dds.dds_ref_blocks) - 1; 420 ASSERT(bucket >= 0); 421 422 ddh = &ddt->ddt_histogram[dde->dde_type][dde->dde_class]; 423 424 ddt_stat_add(&ddh->ddh_stat[bucket], &dds, neg); 425 } 426 427 void 428 ddt_histogram_add(ddt_histogram_t *dst, const ddt_histogram_t *src) 429 { 430 for (int h = 0; h < 64; h++) 431 ddt_stat_add(&dst->ddh_stat[h], &src->ddh_stat[h], 0); 432 } 433 434 void 435 ddt_histogram_stat(ddt_stat_t *dds, const ddt_histogram_t *ddh) 436 { 437 bzero(dds, sizeof (*dds)); 438 439 for (int h = 0; h < 64; h++) 440 ddt_stat_add(dds, &ddh->ddh_stat[h], 0); 441 } 442 443 boolean_t 444 ddt_histogram_empty(const ddt_histogram_t *ddh) 445 { 446 const uint64_t *s = (const uint64_t *)ddh; 447 const uint64_t *s_end = (const uint64_t *)(ddh + 1); 448 449 while (s < s_end) 450 if (*s++ != 0) 451 return (B_FALSE); 452 453 return (B_TRUE); 454 } 455 456 void 457 ddt_get_dedup_object_stats(spa_t *spa, ddt_object_t *ddo_total) 458 { 459 /* Sum the statistics we cached in ddt_object_sync(). */ 460 for (enum zio_checksum c = 0; c < ZIO_CHECKSUM_FUNCTIONS; c++) { 461 ddt_t *ddt = spa->spa_ddt[c]; 462 for (enum ddt_type type = 0; type < DDT_TYPES; type++) { 463 for (enum ddt_class class = 0; class < DDT_CLASSES; 464 class++) { 465 ddt_object_t *ddo = 466 &ddt->ddt_object_stats[type][class]; 467 ddo_total->ddo_count += ddo->ddo_count; 468 ddo_total->ddo_dspace += ddo->ddo_dspace; 469 ddo_total->ddo_mspace += ddo->ddo_mspace; 470 } 471 } 472 } 473 474 /* ... and compute the averages. */ 475 if (ddo_total->ddo_count != 0) { 476 ddo_total->ddo_dspace /= ddo_total->ddo_count; 477 ddo_total->ddo_mspace /= ddo_total->ddo_count; 478 } 479 } 480 481 void 482 ddt_get_dedup_histogram(spa_t *spa, ddt_histogram_t *ddh) 483 { 484 for (enum zio_checksum c = 0; c < ZIO_CHECKSUM_FUNCTIONS; c++) { 485 ddt_t *ddt = spa->spa_ddt[c]; 486 for (enum ddt_type type = 0; type < DDT_TYPES; type++) { 487 for (enum ddt_class class = 0; class < DDT_CLASSES; 488 class++) { 489 ddt_histogram_add(ddh, 490 &ddt->ddt_histogram_cache[type][class]); 491 } 492 } 493 } 494 } 495 496 void 497 ddt_get_dedup_stats(spa_t *spa, ddt_stat_t *dds_total) 498 { 499 ddt_histogram_t *ddh_total; 500 501 ddh_total = kmem_zalloc(sizeof (ddt_histogram_t), KM_SLEEP); 502 ddt_get_dedup_histogram(spa, ddh_total); 503 ddt_histogram_stat(dds_total, ddh_total); 504 kmem_free(ddh_total, sizeof (ddt_histogram_t)); 505 } 506 507 uint64_t 508 ddt_get_dedup_dspace(spa_t *spa) 509 { 510 ddt_stat_t dds_total = { 0 }; 511 512 ddt_get_dedup_stats(spa, &dds_total); 513 return (dds_total.dds_ref_dsize - dds_total.dds_dsize); 514 } 515 516 uint64_t 517 ddt_get_pool_dedup_ratio(spa_t *spa) 518 { 519 ddt_stat_t dds_total = { 0 }; 520 521 ddt_get_dedup_stats(spa, &dds_total); 522 if (dds_total.dds_dsize == 0) 523 return (100); 524 525 return (dds_total.dds_ref_dsize * 100 / dds_total.dds_dsize); 526 } 527 528 int 529 ddt_ditto_copies_needed(ddt_t *ddt, ddt_entry_t *dde, ddt_phys_t *ddp_willref) 530 { 531 spa_t *spa = ddt->ddt_spa; 532 uint64_t total_refcnt = 0; 533 uint64_t ditto = spa->spa_dedup_ditto; 534 int total_copies = 0; 535 int desired_copies = 0; 536 537 for (int p = DDT_PHYS_SINGLE; p <= DDT_PHYS_TRIPLE; p++) { 538 ddt_phys_t *ddp = &dde->dde_phys[p]; 539 zio_t *zio = dde->dde_lead_zio[p]; 540 uint64_t refcnt = ddp->ddp_refcnt; /* committed refs */ 541 if (zio != NULL) 542 refcnt += zio->io_parent_count; /* pending refs */ 543 if (ddp == ddp_willref) 544 refcnt++; /* caller's ref */ 545 if (refcnt != 0) { 546 total_refcnt += refcnt; 547 total_copies += p; 548 } 549 } 550 551 if (ditto == 0 || ditto > UINT32_MAX) 552 ditto = UINT32_MAX; 553 554 if (total_refcnt >= 1) 555 desired_copies++; 556 if (total_refcnt >= ditto) 557 desired_copies++; 558 if (total_refcnt >= ditto * ditto) 559 desired_copies++; 560 561 return (MAX(desired_copies, total_copies) - total_copies); 562 } 563 564 int 565 ddt_ditto_copies_present(ddt_entry_t *dde) 566 { 567 ddt_phys_t *ddp = &dde->dde_phys[DDT_PHYS_DITTO]; 568 dva_t *dva = ddp->ddp_dva; 569 int copies = 0 - DVA_GET_GANG(dva); 570 571 for (int d = 0; d < SPA_DVAS_PER_BP; d++, dva++) 572 if (DVA_IS_VALID(dva)) 573 copies++; 574 575 ASSERT(copies >= 0 && copies < SPA_DVAS_PER_BP); 576 577 return (copies); 578 } 579 580 size_t 581 ddt_compress(void *src, uchar_t *dst, size_t s_len, size_t d_len) 582 { 583 uchar_t *version = dst++; 584 int cpfunc = ZIO_COMPRESS_ZLE; 585 zio_compress_info_t *ci = &zio_compress_table[cpfunc]; 586 size_t c_len; 587 588 ASSERT(d_len >= s_len + 1); /* no compression plus version byte */ 589 590 c_len = ci->ci_compress(src, dst, s_len, d_len - 1, ci->ci_level); 591 592 if (c_len == s_len) { 593 cpfunc = ZIO_COMPRESS_OFF; 594 bcopy(src, dst, s_len); 595 } 596 597 *version = cpfunc; 598 /* CONSTCOND */ 599 if (ZFS_HOST_BYTEORDER) 600 *version |= DDT_COMPRESS_BYTEORDER_MASK; 601 602 return (c_len + 1); 603 } 604 605 void 606 ddt_decompress(uchar_t *src, void *dst, size_t s_len, size_t d_len) 607 { 608 uchar_t version = *src++; 609 int cpfunc = version & DDT_COMPRESS_FUNCTION_MASK; 610 zio_compress_info_t *ci = &zio_compress_table[cpfunc]; 611 612 if (ci->ci_decompress != NULL) 613 (void) ci->ci_decompress(src, dst, s_len, d_len, ci->ci_level); 614 else 615 bcopy(src, dst, d_len); 616 617 if (((version & DDT_COMPRESS_BYTEORDER_MASK) != 0) != 618 (ZFS_HOST_BYTEORDER != 0)) 619 byteswap_uint64_array(dst, d_len); 620 } 621 622 ddt_t * 623 ddt_select_by_checksum(spa_t *spa, enum zio_checksum c) 624 { 625 return (spa->spa_ddt[c]); 626 } 627 628 ddt_t * 629 ddt_select(spa_t *spa, const blkptr_t *bp) 630 { 631 return (spa->spa_ddt[BP_GET_CHECKSUM(bp)]); 632 } 633 634 void 635 ddt_enter(ddt_t *ddt) 636 { 637 mutex_enter(&ddt->ddt_lock); 638 } 639 640 void 641 ddt_exit(ddt_t *ddt) 642 { 643 mutex_exit(&ddt->ddt_lock); 644 } 645 646 static ddt_entry_t * 647 ddt_alloc(const ddt_key_t *ddk) 648 { 649 ddt_entry_t *dde; 650 651 dde = kmem_zalloc(sizeof (ddt_entry_t), KM_SLEEP); 652 cv_init(&dde->dde_cv, NULL, CV_DEFAULT, NULL); 653 654 dde->dde_key = *ddk; 655 656 return (dde); 657 } 658 659 static void 660 ddt_free(ddt_entry_t *dde) 661 { 662 ASSERT(!dde->dde_loading); 663 664 for (int p = 0; p < DDT_PHYS_TYPES; p++) 665 ASSERT(dde->dde_lead_zio[p] == NULL); 666 667 if (dde->dde_repair_data != NULL) 668 zio_buf_free(dde->dde_repair_data, 669 DDK_GET_PSIZE(&dde->dde_key)); 670 671 cv_destroy(&dde->dde_cv); 672 kmem_free(dde, sizeof (*dde)); 673 } 674 675 void 676 ddt_remove(ddt_t *ddt, ddt_entry_t *dde) 677 { 678 ASSERT(MUTEX_HELD(&ddt->ddt_lock)); 679 680 avl_remove(&ddt->ddt_tree, dde); 681 ddt_free(dde); 682 } 683 684 ddt_entry_t * 685 ddt_lookup(ddt_t *ddt, const blkptr_t *bp, boolean_t add) 686 { 687 ddt_entry_t *dde, dde_search; 688 enum ddt_type type; 689 enum ddt_class class; 690 avl_index_t where; 691 int error; 692 693 ASSERT(MUTEX_HELD(&ddt->ddt_lock)); 694 695 ddt_key_fill(&dde_search.dde_key, bp); 696 697 dde = avl_find(&ddt->ddt_tree, &dde_search, &where); 698 if (dde == NULL) { 699 if (!add) 700 return (NULL); 701 dde = ddt_alloc(&dde_search.dde_key); 702 avl_insert(&ddt->ddt_tree, dde, where); 703 } 704 705 while (dde->dde_loading) 706 cv_wait(&dde->dde_cv, &ddt->ddt_lock); 707 708 if (dde->dde_loaded) 709 return (dde); 710 711 dde->dde_loading = B_TRUE; 712 713 ddt_exit(ddt); 714 715 error = ENOENT; 716 717 for (type = 0; type < DDT_TYPES; type++) { 718 for (class = 0; class < DDT_CLASSES; class++) { 719 error = ddt_object_lookup(ddt, type, class, dde); 720 if (error != ENOENT) 721 break; 722 } 723 if (error != ENOENT) 724 break; 725 } 726 727 ASSERT(error == 0 || error == ENOENT); 728 729 ddt_enter(ddt); 730 731 ASSERT(dde->dde_loaded == B_FALSE); 732 ASSERT(dde->dde_loading == B_TRUE); 733 734 dde->dde_type = type; /* will be DDT_TYPES if no entry found */ 735 dde->dde_class = class; /* will be DDT_CLASSES if no entry found */ 736 dde->dde_loaded = B_TRUE; 737 dde->dde_loading = B_FALSE; 738 739 if (error == 0) 740 ddt_stat_update(ddt, dde, -1ULL); 741 742 cv_broadcast(&dde->dde_cv); 743 744 return (dde); 745 } 746 747 void 748 ddt_prefetch(spa_t *spa, const blkptr_t *bp) 749 { 750 ddt_t *ddt; 751 ddt_entry_t dde; 752 753 if (!zfs_dedup_prefetch || bp == NULL || !BP_GET_DEDUP(bp)) 754 return; 755 756 /* 757 * We only remove the DDT once all tables are empty and only 758 * prefetch dedup blocks when there are entries in the DDT. 759 * Thus no locking is required as the DDT can't disappear on us. 760 */ 761 ddt = ddt_select(spa, bp); 762 ddt_key_fill(&dde.dde_key, bp); 763 764 for (enum ddt_type type = 0; type < DDT_TYPES; type++) { 765 for (enum ddt_class class = 0; class < DDT_CLASSES; class++) { 766 ddt_object_prefetch(ddt, type, class, &dde); 767 } 768 } 769 } 770 771 int 772 ddt_entry_compare(const void *x1, const void *x2) 773 { 774 const ddt_entry_t *dde1 = x1; 775 const ddt_entry_t *dde2 = x2; 776 const uint64_t *u1 = (const uint64_t *)&dde1->dde_key; 777 const uint64_t *u2 = (const uint64_t *)&dde2->dde_key; 778 779 for (int i = 0; i < DDT_KEY_WORDS; i++) { 780 if (u1[i] < u2[i]) 781 return (-1); 782 if (u1[i] > u2[i]) 783 return (1); 784 } 785 786 return (0); 787 } 788 789 static ddt_t * 790 ddt_table_alloc(spa_t *spa, enum zio_checksum c) 791 { 792 ddt_t *ddt; 793 794 ddt = kmem_zalloc(sizeof (*ddt), KM_SLEEP); 795 796 mutex_init(&ddt->ddt_lock, NULL, MUTEX_DEFAULT, NULL); 797 avl_create(&ddt->ddt_tree, ddt_entry_compare, 798 sizeof (ddt_entry_t), offsetof(ddt_entry_t, dde_node)); 799 avl_create(&ddt->ddt_repair_tree, ddt_entry_compare, 800 sizeof (ddt_entry_t), offsetof(ddt_entry_t, dde_node)); 801 ddt->ddt_checksum = c; 802 ddt->ddt_spa = spa; 803 ddt->ddt_os = spa->spa_meta_objset; 804 805 return (ddt); 806 } 807 808 static void 809 ddt_table_free(ddt_t *ddt) 810 { 811 ASSERT(avl_numnodes(&ddt->ddt_tree) == 0); 812 ASSERT(avl_numnodes(&ddt->ddt_repair_tree) == 0); 813 avl_destroy(&ddt->ddt_tree); 814 avl_destroy(&ddt->ddt_repair_tree); 815 mutex_destroy(&ddt->ddt_lock); 816 kmem_free(ddt, sizeof (*ddt)); 817 } 818 819 void 820 ddt_create(spa_t *spa) 821 { 822 spa->spa_dedup_checksum = ZIO_DEDUPCHECKSUM; 823 824 for (enum zio_checksum c = 0; c < ZIO_CHECKSUM_FUNCTIONS; c++) 825 spa->spa_ddt[c] = ddt_table_alloc(spa, c); 826 } 827 828 int 829 ddt_load(spa_t *spa) 830 { 831 int error; 832 833 ddt_create(spa); 834 835 error = zap_lookup(spa->spa_meta_objset, DMU_POOL_DIRECTORY_OBJECT, 836 DMU_POOL_DDT_STATS, sizeof (uint64_t), 1, 837 &spa->spa_ddt_stat_object); 838 839 if (error) 840 return (error == ENOENT ? 0 : error); 841 842 for (enum zio_checksum c = 0; c < ZIO_CHECKSUM_FUNCTIONS; c++) { 843 ddt_t *ddt = spa->spa_ddt[c]; 844 for (enum ddt_type type = 0; type < DDT_TYPES; type++) { 845 for (enum ddt_class class = 0; class < DDT_CLASSES; 846 class++) { 847 error = ddt_object_load(ddt, type, class); 848 if (error != 0 && error != ENOENT) 849 return (error); 850 } 851 } 852 853 /* 854 * Seed the cached histograms. 855 */ 856 bcopy(ddt->ddt_histogram, &ddt->ddt_histogram_cache, 857 sizeof (ddt->ddt_histogram)); 858 } 859 860 return (0); 861 } 862 863 void 864 ddt_unload(spa_t *spa) 865 { 866 for (enum zio_checksum c = 0; c < ZIO_CHECKSUM_FUNCTIONS; c++) { 867 if (spa->spa_ddt[c]) { 868 ddt_table_free(spa->spa_ddt[c]); 869 spa->spa_ddt[c] = NULL; 870 } 871 } 872 } 873 874 boolean_t 875 ddt_class_contains(spa_t *spa, enum ddt_class max_class, const blkptr_t *bp) 876 { 877 ddt_t *ddt; 878 ddt_entry_t dde; 879 880 if (!BP_GET_DEDUP(bp)) 881 return (B_FALSE); 882 883 if (max_class == DDT_CLASS_UNIQUE) 884 return (B_TRUE); 885 886 ddt = spa->spa_ddt[BP_GET_CHECKSUM(bp)]; 887 888 ddt_key_fill(&dde.dde_key, bp); 889 890 for (enum ddt_type type = 0; type < DDT_TYPES; type++) 891 for (enum ddt_class class = 0; class <= max_class; class++) 892 if (ddt_object_lookup(ddt, type, class, &dde) == 0) 893 return (B_TRUE); 894 895 return (B_FALSE); 896 } 897 898 ddt_entry_t * 899 ddt_repair_start(ddt_t *ddt, const blkptr_t *bp) 900 { 901 ddt_key_t ddk; 902 ddt_entry_t *dde; 903 904 ddt_key_fill(&ddk, bp); 905 906 dde = ddt_alloc(&ddk); 907 908 for (enum ddt_type type = 0; type < DDT_TYPES; type++) { 909 for (enum ddt_class class = 0; class < DDT_CLASSES; class++) { 910 /* 911 * We can only do repair if there are multiple copies 912 * of the block. For anything in the UNIQUE class, 913 * there's definitely only one copy, so don't even try. 914 */ 915 if (class != DDT_CLASS_UNIQUE && 916 ddt_object_lookup(ddt, type, class, dde) == 0) 917 return (dde); 918 } 919 } 920 921 bzero(dde->dde_phys, sizeof (dde->dde_phys)); 922 923 return (dde); 924 } 925 926 void 927 ddt_repair_done(ddt_t *ddt, ddt_entry_t *dde) 928 { 929 avl_index_t where; 930 931 ddt_enter(ddt); 932 933 if (dde->dde_repair_data != NULL && spa_writeable(ddt->ddt_spa) && 934 avl_find(&ddt->ddt_repair_tree, dde, &where) == NULL) 935 avl_insert(&ddt->ddt_repair_tree, dde, where); 936 else 937 ddt_free(dde); 938 939 ddt_exit(ddt); 940 } 941 942 static void 943 ddt_repair_entry_done(zio_t *zio) 944 { 945 ddt_entry_t *rdde = zio->io_private; 946 947 ddt_free(rdde); 948 } 949 950 static void 951 ddt_repair_entry(ddt_t *ddt, ddt_entry_t *dde, ddt_entry_t *rdde, zio_t *rio) 952 { 953 ddt_phys_t *ddp = dde->dde_phys; 954 ddt_phys_t *rddp = rdde->dde_phys; 955 ddt_key_t *ddk = &dde->dde_key; 956 ddt_key_t *rddk = &rdde->dde_key; 957 zio_t *zio; 958 blkptr_t blk; 959 960 zio = zio_null(rio, rio->io_spa, NULL, 961 ddt_repair_entry_done, rdde, rio->io_flags); 962 963 for (int p = 0; p < DDT_PHYS_TYPES; p++, ddp++, rddp++) { 964 if (ddp->ddp_phys_birth == 0 || 965 ddp->ddp_phys_birth != rddp->ddp_phys_birth || 966 bcmp(ddp->ddp_dva, rddp->ddp_dva, sizeof (ddp->ddp_dva))) 967 continue; 968 ddt_bp_create(ddt->ddt_checksum, ddk, ddp, &blk); 969 zio_nowait(zio_rewrite(zio, zio->io_spa, 0, &blk, 970 rdde->dde_repair_data, DDK_GET_PSIZE(rddk), NULL, NULL, 971 ZIO_PRIORITY_SYNC_WRITE, ZIO_DDT_CHILD_FLAGS(zio), NULL)); 972 } 973 974 zio_nowait(zio); 975 } 976 977 static void 978 ddt_repair_table(ddt_t *ddt, zio_t *rio) 979 { 980 spa_t *spa = ddt->ddt_spa; 981 ddt_entry_t *dde, *rdde_next, *rdde; 982 avl_tree_t *t = &ddt->ddt_repair_tree; 983 blkptr_t blk; 984 985 if (spa_sync_pass(spa) > 1) 986 return; 987 988 ddt_enter(ddt); 989 for (rdde = avl_first(t); rdde != NULL; rdde = rdde_next) { 990 rdde_next = AVL_NEXT(t, rdde); 991 avl_remove(&ddt->ddt_repair_tree, rdde); 992 ddt_exit(ddt); 993 ddt_bp_create(ddt->ddt_checksum, &rdde->dde_key, NULL, &blk); 994 dde = ddt_repair_start(ddt, &blk); 995 ddt_repair_entry(ddt, dde, rdde, rio); 996 ddt_repair_done(ddt, dde); 997 ddt_enter(ddt); 998 } 999 ddt_exit(ddt); 1000 } 1001 1002 static void 1003 ddt_sync_entry(ddt_t *ddt, ddt_entry_t *dde, dmu_tx_t *tx, uint64_t txg) 1004 { 1005 dsl_pool_t *dp = ddt->ddt_spa->spa_dsl_pool; 1006 ddt_phys_t *ddp = dde->dde_phys; 1007 ddt_key_t *ddk = &dde->dde_key; 1008 enum ddt_type otype = dde->dde_type; 1009 enum ddt_type ntype = DDT_TYPE_CURRENT; 1010 enum ddt_class oclass = dde->dde_class; 1011 enum ddt_class nclass; 1012 uint64_t total_refcnt = 0; 1013 1014 ASSERT(dde->dde_loaded); 1015 ASSERT(!dde->dde_loading); 1016 1017 for (int p = 0; p < DDT_PHYS_TYPES; p++, ddp++) { 1018 ASSERT(dde->dde_lead_zio[p] == NULL); 1019 ASSERT((int64_t)ddp->ddp_refcnt >= 0); 1020 if (ddp->ddp_phys_birth == 0) { 1021 ASSERT(ddp->ddp_refcnt == 0); 1022 continue; 1023 } 1024 if (p == DDT_PHYS_DITTO) { 1025 if (ddt_ditto_copies_needed(ddt, dde, NULL) == 0) 1026 ddt_phys_free(ddt, ddk, ddp, txg); 1027 continue; 1028 } 1029 if (ddp->ddp_refcnt == 0) 1030 ddt_phys_free(ddt, ddk, ddp, txg); 1031 total_refcnt += ddp->ddp_refcnt; 1032 } 1033 1034 if (dde->dde_phys[DDT_PHYS_DITTO].ddp_phys_birth != 0) 1035 nclass = DDT_CLASS_DITTO; 1036 else if (total_refcnt > 1) 1037 nclass = DDT_CLASS_DUPLICATE; 1038 else 1039 nclass = DDT_CLASS_UNIQUE; 1040 1041 if (otype != DDT_TYPES && 1042 (otype != ntype || oclass != nclass || total_refcnt == 0)) { 1043 VERIFY(ddt_object_remove(ddt, otype, oclass, dde, tx) == 0); 1044 ASSERT(ddt_object_lookup(ddt, otype, oclass, dde) == ENOENT); 1045 } 1046 1047 if (total_refcnt != 0) { 1048 dde->dde_type = ntype; 1049 dde->dde_class = nclass; 1050 ddt_stat_update(ddt, dde, 0); 1051 if (!ddt_object_exists(ddt, ntype, nclass)) 1052 ddt_object_create(ddt, ntype, nclass, tx); 1053 VERIFY(ddt_object_update(ddt, ntype, nclass, dde, tx) == 0); 1054 1055 /* 1056 * If the class changes, the order that we scan this bp 1057 * changes. If it decreases, we could miss it, so 1058 * scan it right now. (This covers both class changing 1059 * while we are doing ddt_walk(), and when we are 1060 * traversing.) 1061 */ 1062 if (nclass < oclass) { 1063 dsl_scan_ddt_entry(dp->dp_scan, 1064 ddt->ddt_checksum, dde, tx); 1065 } 1066 } 1067 } 1068 1069 static void 1070 ddt_sync_table(ddt_t *ddt, dmu_tx_t *tx, uint64_t txg) 1071 { 1072 spa_t *spa = ddt->ddt_spa; 1073 ddt_entry_t *dde; 1074 void *cookie = NULL; 1075 1076 if (avl_numnodes(&ddt->ddt_tree) == 0) 1077 return; 1078 1079 ASSERT(spa->spa_uberblock.ub_version >= SPA_VERSION_DEDUP); 1080 1081 if (spa->spa_ddt_stat_object == 0) { 1082 spa->spa_ddt_stat_object = zap_create_link(ddt->ddt_os, 1083 DMU_OT_DDT_STATS, DMU_POOL_DIRECTORY_OBJECT, 1084 DMU_POOL_DDT_STATS, tx); 1085 } 1086 1087 while ((dde = avl_destroy_nodes(&ddt->ddt_tree, &cookie)) != NULL) { 1088 ddt_sync_entry(ddt, dde, tx, txg); 1089 ddt_free(dde); 1090 } 1091 1092 for (enum ddt_type type = 0; type < DDT_TYPES; type++) { 1093 uint64_t add, count = 0; 1094 for (enum ddt_class class = 0; class < DDT_CLASSES; class++) { 1095 if (ddt_object_exists(ddt, type, class)) { 1096 ddt_object_sync(ddt, type, class, tx); 1097 VERIFY(ddt_object_count(ddt, type, class, 1098 &add) == 0); 1099 count += add; 1100 } 1101 } 1102 for (enum ddt_class class = 0; class < DDT_CLASSES; class++) { 1103 if (count == 0 && ddt_object_exists(ddt, type, class)) 1104 ddt_object_destroy(ddt, type, class, tx); 1105 } 1106 } 1107 1108 bcopy(ddt->ddt_histogram, &ddt->ddt_histogram_cache, 1109 sizeof (ddt->ddt_histogram)); 1110 } 1111 1112 void 1113 ddt_sync(spa_t *spa, uint64_t txg) 1114 { 1115 dmu_tx_t *tx; 1116 zio_t *rio = zio_root(spa, NULL, NULL, 1117 ZIO_FLAG_CANFAIL | ZIO_FLAG_SPECULATIVE); 1118 1119 ASSERT(spa_syncing_txg(spa) == txg); 1120 1121 tx = dmu_tx_create_assigned(spa->spa_dsl_pool, txg); 1122 1123 for (enum zio_checksum c = 0; c < ZIO_CHECKSUM_FUNCTIONS; c++) { 1124 ddt_t *ddt = spa->spa_ddt[c]; 1125 if (ddt == NULL) 1126 continue; 1127 ddt_sync_table(ddt, tx, txg); 1128 ddt_repair_table(ddt, rio); 1129 } 1130 1131 (void) zio_wait(rio); 1132 1133 dmu_tx_commit(tx); 1134 } 1135 1136 int 1137 ddt_walk(spa_t *spa, ddt_bookmark_t *ddb, ddt_entry_t *dde) 1138 { 1139 do { 1140 do { 1141 do { 1142 ddt_t *ddt = spa->spa_ddt[ddb->ddb_checksum]; 1143 int error = ENOENT; 1144 if (ddt_object_exists(ddt, ddb->ddb_type, 1145 ddb->ddb_class)) { 1146 error = ddt_object_walk(ddt, 1147 ddb->ddb_type, ddb->ddb_class, 1148 &ddb->ddb_cursor, dde); 1149 } 1150 dde->dde_type = ddb->ddb_type; 1151 dde->dde_class = ddb->ddb_class; 1152 if (error == 0) 1153 return (0); 1154 if (error != ENOENT) 1155 return (error); 1156 ddb->ddb_cursor = 0; 1157 } while (++ddb->ddb_checksum < ZIO_CHECKSUM_FUNCTIONS); 1158 ddb->ddb_checksum = 0; 1159 } while (++ddb->ddb_type < DDT_TYPES); 1160 ddb->ddb_type = 0; 1161 } while (++ddb->ddb_class < DDT_CLASSES); 1162 1163 return (SET_ERROR(ENOENT)); 1164 } 1165
Indexes created Fri Jun 12 00:25:51 UTC 2026