module/zfs/ddt.c

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