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 https://opensource.org/licenses/CDDL-1.0.
  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, 2016 by Delphix. All rights reserved.
  25  * Copyright (c) 2022 by Pawel Jakub Dawidek
  26  */
  27
  28 #include <sys/zfs_context.h>
  29 #include <sys/spa.h>
  30 #include <sys/spa_impl.h>
  31 #include <sys/zio.h>
  32 #include <sys/ddt.h>
  33 #include <sys/ddt_impl.h>
  34 #include <sys/zap.h>
  35 #include <sys/dmu_tx.h>
  36 #include <sys/arc.h>
  37 #include <sys/dsl_pool.h>
  38 #include <sys/zio_checksum.h>
  39 #include <sys/dsl_scan.h>
  40 #include <sys/abd.h>
  41
  42 static kmem_cache_t *ddt_cache;
  43 static kmem_cache_t *ddt_entry_cache;
  44
  45 /*
  46  * Enable/disable prefetching of dedup-ed blocks which are going to be freed.
  47  */
  48 int zfs_dedup_prefetch = 0;
  49
  50 static const ddt_ops_t *const ddt_ops[DDT_TYPES] = {
  51         &ddt_zap_ops,
  52 };
  53
  54 static const char *const ddt_class_name[DDT_CLASSES] = {
  55         "ditto",
  56         "duplicate",
  57         "unique",
  58 };
  59
  60 static void
  61 ddt_object_create(ddt_t *ddt, ddt_type_t type, ddt_class_t 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         ASSERT3U(*objectp, ==, 0);
  74         VERIFY0(ddt_ops[type]->ddt_op_create(os, objectp, tx, prehash));
  75         ASSERT3U(*objectp, !=, 0);
  76
  77         VERIFY0(zap_add(os, DMU_POOL_DIRECTORY_OBJECT, name,
  78             sizeof (uint64_t), 1, objectp, tx));
  79
  80         VERIFY0(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));
  83 }
  84
  85 static void
  86 ddt_object_destroy(ddt_t *ddt, ddt_type_t type, ddt_class_t 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         ASSERT3U(*objectp, !=, 0);
  98         ASSERT(ddt_histogram_empty(&ddt->ddt_histogram[type][class]));
  99         VERIFY0(ddt_object_count(ddt, type, class, &count));
 100         VERIFY0(count);
 101         VERIFY0(zap_remove(os, DMU_POOL_DIRECTORY_OBJECT, name, tx));
 102         VERIFY0(zap_remove(os, spa->spa_ddt_stat_object, name, tx));
 103         VERIFY0(ddt_ops[type]->ddt_op_destroy(os, *objectp, tx));
 104         memset(&ddt->ddt_object_stats[type][class], 0, sizeof (ddt_object_t));
 105
 106         *objectp = 0;
 107 }
 108
 109 static int
 110 ddt_object_load(ddt_t *ddt, ddt_type_t type, ddt_class_t class)
 111 {
 112         ddt_object_t *ddo = &ddt->ddt_object_stats[type][class];
 113         dmu_object_info_t doi;
 114         uint64_t count;
 115         char name[DDT_NAMELEN];
 116         int error;
 117
 118         ddt_object_name(ddt, type, class, name);
 119
 120         error = zap_lookup(ddt->ddt_os, DMU_POOL_DIRECTORY_OBJECT, name,
 121             sizeof (uint64_t), 1, &ddt->ddt_object[type][class]);
 122         if (error != 0)
 123                 return (error);
 124
 125         error = 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         if (error != 0)
 129                 return (error);
 130
 131         /*
 132          * Seed the cached statistics.
 133          */
 134         error = ddt_object_info(ddt, type, class, &doi);
 135         if (error)
 136                 return (error);
 137
 138         error = ddt_object_count(ddt, type, class, &count);
 139         if (error)
 140                 return (error);
 141
 142         ddo->ddo_count = count;
 143         ddo->ddo_dspace = doi.doi_physical_blocks_512 << 9;
 144         ddo->ddo_mspace = doi.doi_fill_count * doi.doi_data_block_size;
 145
 146         return (0);
 147 }
 148
 149 static void
 150 ddt_object_sync(ddt_t *ddt, ddt_type_t type, ddt_class_t class,
 151     dmu_tx_t *tx)
 152 {
 153         ddt_object_t *ddo = &ddt->ddt_object_stats[type][class];
 154         dmu_object_info_t doi;
 155         uint64_t count;
 156         char name[DDT_NAMELEN];
 157
 158         ddt_object_name(ddt, type, class, name);
 159
 160         VERIFY0(zap_update(ddt->ddt_os, ddt->ddt_spa->spa_ddt_stat_object, name,
 161             sizeof (uint64_t), sizeof (ddt_histogram_t) / sizeof (uint64_t),
 162             &ddt->ddt_histogram[type][class], tx));
 163
 164         /*
 165          * Cache DDT statistics; this is the only time they'll change.
 166          */
 167         VERIFY0(ddt_object_info(ddt, type, class, &doi));
 168         VERIFY0(ddt_object_count(ddt, type, class, &count));
 169
 170         ddo->ddo_count = count;
 171         ddo->ddo_dspace = doi.doi_physical_blocks_512 << 9;
 172         ddo->ddo_mspace = doi.doi_fill_count * doi.doi_data_block_size;
 173 }
 174
 175 static boolean_t
 176 ddt_object_exists(ddt_t *ddt, ddt_type_t type, ddt_class_t class)
 177 {
 178         return (!!ddt->ddt_object[type][class]);
 179 }
 180
 181 static int
 182 ddt_object_lookup(ddt_t *ddt, ddt_type_t type, ddt_class_t class,
 183     ddt_entry_t *dde)
 184 {
 185         if (!ddt_object_exists(ddt, type, class))
 186                 return (SET_ERROR(ENOENT));
 187
 188         return (ddt_ops[type]->ddt_op_lookup(ddt->ddt_os,
 189             ddt->ddt_object[type][class], &dde->dde_key,
 190             dde->dde_phys, sizeof (dde->dde_phys)));
 191 }
 192
 193 static int
 194 ddt_object_contains(ddt_t *ddt, ddt_type_t type, ddt_class_t class,
 195     const ddt_key_t *ddk)
 196 {
 197         if (!ddt_object_exists(ddt, type, class))
 198                 return (SET_ERROR(ENOENT));
 199
 200         return (ddt_ops[type]->ddt_op_contains(ddt->ddt_os,
 201             ddt->ddt_object[type][class], ddk));
 202 }
 203
 204 static void
 205 ddt_object_prefetch(ddt_t *ddt, ddt_type_t type, ddt_class_t class,
 206     const ddt_key_t *ddk)
 207 {
 208         if (!ddt_object_exists(ddt, type, class))
 209                 return;
 210
 211         ddt_ops[type]->ddt_op_prefetch(ddt->ddt_os,
 212             ddt->ddt_object[type][class], ddk);
 213 }
 214
 215 static int
 216 ddt_object_update(ddt_t *ddt, ddt_type_t type, ddt_class_t class,
 217     ddt_entry_t *dde, dmu_tx_t *tx)
 218 {
 219         ASSERT(ddt_object_exists(ddt, type, class));
 220
 221         return (ddt_ops[type]->ddt_op_update(ddt->ddt_os,
 222             ddt->ddt_object[type][class], &dde->dde_key, dde->dde_phys,
 223             sizeof (dde->dde_phys), tx));
 224 }
 225
 226 static int
 227 ddt_object_remove(ddt_t *ddt, ddt_type_t type, ddt_class_t class,
 228     const ddt_key_t *ddk, dmu_tx_t *tx)
 229 {
 230         ASSERT(ddt_object_exists(ddt, type, class));
 231
 232         return (ddt_ops[type]->ddt_op_remove(ddt->ddt_os,
 233             ddt->ddt_object[type][class], ddk, tx));
 234 }
 235
 236 int
 237 ddt_object_walk(ddt_t *ddt, ddt_type_t type, ddt_class_t class,
 238     uint64_t *walk, ddt_entry_t *dde)
 239 {
 240         ASSERT(ddt_object_exists(ddt, type, class));
 241
 242         return (ddt_ops[type]->ddt_op_walk(ddt->ddt_os,
 243             ddt->ddt_object[type][class], walk, &dde->dde_key,
 244             dde->dde_phys, sizeof (dde->dde_phys)));
 245 }
 246
 247 int
 248 ddt_object_count(ddt_t *ddt, ddt_type_t type, ddt_class_t class,
 249     uint64_t *count)
 250 {
 251         ASSERT(ddt_object_exists(ddt, type, class));
 252
 253         return (ddt_ops[type]->ddt_op_count(ddt->ddt_os,
 254             ddt->ddt_object[type][class], count));
 255 }
 256
 257 int
 258 ddt_object_info(ddt_t *ddt, ddt_type_t type, ddt_class_t class,
 259     dmu_object_info_t *doi)
 260 {
 261         if (!ddt_object_exists(ddt, type, class))
 262                 return (SET_ERROR(ENOENT));
 263
 264         return (dmu_object_info(ddt->ddt_os, ddt->ddt_object[type][class],
 265             doi));
 266 }
 267
 268 void
 269 ddt_object_name(ddt_t *ddt, ddt_type_t type, ddt_class_t class,
 270     char *name)
 271 {
 272         (void) snprintf(name, DDT_NAMELEN, DMU_POOL_DDT,
 273             zio_checksum_table[ddt->ddt_checksum].ci_name,
 274             ddt_ops[type]->ddt_op_name, ddt_class_name[class]);
 275 }
 276
 277 void
 278 ddt_bp_fill(const ddt_phys_t *ddp, blkptr_t *bp, uint64_t txg)
 279 {
 280         ASSERT3U(txg, !=, 0);
 281
 282         for (int d = 0; d < SPA_DVAS_PER_BP; d++)
 283                 bp->blk_dva[d] = ddp->ddp_dva[d];
 284         BP_SET_BIRTH(bp, txg, ddp->ddp_phys_birth);
 285 }
 286
 287 /*
 288  * The bp created via this function may be used for repairs and scrub, but it
 289  * will be missing the salt / IV required to do a full decrypting read.
 290  */
 291 void
 292 ddt_bp_create(enum zio_checksum checksum,
 293     const ddt_key_t *ddk, const ddt_phys_t *ddp, blkptr_t *bp)
 294 {
 295         BP_ZERO(bp);
 296
 297         if (ddp != NULL)
 298                 ddt_bp_fill(ddp, bp, ddp->ddp_phys_birth);
 299
 300         bp->blk_cksum = ddk->ddk_cksum;
 301
 302         BP_SET_LSIZE(bp, DDK_GET_LSIZE(ddk));
 303         BP_SET_PSIZE(bp, DDK_GET_PSIZE(ddk));
 304         BP_SET_COMPRESS(bp, DDK_GET_COMPRESS(ddk));
 305         BP_SET_CRYPT(bp, DDK_GET_CRYPT(ddk));
 306         BP_SET_FILL(bp, 1);
 307         BP_SET_CHECKSUM(bp, checksum);
 308         BP_SET_TYPE(bp, DMU_OT_DEDUP);
 309         BP_SET_LEVEL(bp, 0);
 310         BP_SET_DEDUP(bp, 1);
 311         BP_SET_BYTEORDER(bp, ZFS_HOST_BYTEORDER);
 312 }
 313
 314 void
 315 ddt_key_fill(ddt_key_t *ddk, const blkptr_t *bp)
 316 {
 317         ddk->ddk_cksum = bp->blk_cksum;
 318         ddk->ddk_prop = 0;
 319
 320         ASSERT(BP_IS_ENCRYPTED(bp) || !BP_USES_CRYPT(bp));
 321
 322         DDK_SET_LSIZE(ddk, BP_GET_LSIZE(bp));
 323         DDK_SET_PSIZE(ddk, BP_GET_PSIZE(bp));
 324         DDK_SET_COMPRESS(ddk, BP_GET_COMPRESS(bp));
 325         DDK_SET_CRYPT(ddk, BP_USES_CRYPT(bp));
 326 }
 327
 328 void
 329 ddt_phys_fill(ddt_phys_t *ddp, const blkptr_t *bp)
 330 {
 331         ASSERT0(ddp->ddp_phys_birth);
 332
 333         for (int d = 0; d < SPA_DVAS_PER_BP; d++)
 334                 ddp->ddp_dva[d] = bp->blk_dva[d];
 335         ddp->ddp_phys_birth = BP_PHYSICAL_BIRTH(bp);
 336 }
 337
 338 void
 339 ddt_phys_clear(ddt_phys_t *ddp)
 340 {
 341         memset(ddp, 0, sizeof (*ddp));
 342 }
 343
 344 void
 345 ddt_phys_addref(ddt_phys_t *ddp)
 346 {
 347         ddp->ddp_refcnt++;
 348 }
 349
 350 void
 351 ddt_phys_decref(ddt_phys_t *ddp)
 352 {
 353         if (ddp) {
 354                 ASSERT3U(ddp->ddp_refcnt, >, 0);
 355                 ddp->ddp_refcnt--;
 356         }
 357 }
 358
 359 static void
 360 ddt_phys_free(ddt_t *ddt, ddt_key_t *ddk, ddt_phys_t *ddp, uint64_t txg)
 361 {
 362         blkptr_t blk;
 363
 364         ddt_bp_create(ddt->ddt_checksum, ddk, ddp, &blk);
 365
 366         /*
 367          * We clear the dedup bit so that zio_free() will actually free the
 368          * space, rather than just decrementing the refcount in the DDT.
 369          */
 370         BP_SET_DEDUP(&blk, 0);
 371
 372         ddt_phys_clear(ddp);
 373         zio_free(ddt->ddt_spa, txg, &blk);
 374 }
 375
 376 ddt_phys_t *
 377 ddt_phys_select(const ddt_entry_t *dde, const blkptr_t *bp)
 378 {
 379         ddt_phys_t *ddp = (ddt_phys_t *)dde->dde_phys;
 380
 381         for (int p = 0; p < DDT_PHYS_TYPES; p++, ddp++) {
 382                 if (DVA_EQUAL(BP_IDENTITY(bp), &ddp->ddp_dva[0]) &&
 383                     BP_PHYSICAL_BIRTH(bp) == ddp->ddp_phys_birth)
 384                         return (ddp);
 385         }
 386         return (NULL);
 387 }
 388
 389 uint64_t
 390 ddt_phys_total_refcnt(const ddt_entry_t *dde)
 391 {
 392         uint64_t refcnt = 0;
 393
 394         for (int p = DDT_PHYS_SINGLE; p <= DDT_PHYS_TRIPLE; p++)
 395                 refcnt += dde->dde_phys[p].ddp_refcnt;
 396
 397         return (refcnt);
 398 }
 399
 400 ddt_t *
 401 ddt_select(spa_t *spa, const blkptr_t *bp)
 402 {
 403         return (spa->spa_ddt[BP_GET_CHECKSUM(bp)]);
 404 }
 405
 406 void
 407 ddt_enter(ddt_t *ddt)
 408 {
 409         mutex_enter(&ddt->ddt_lock);
 410 }
 411
 412 void
 413 ddt_exit(ddt_t *ddt)
 414 {
 415         mutex_exit(&ddt->ddt_lock);
 416 }
 417
 418 void
 419 ddt_init(void)
 420 {
 421         ddt_cache = kmem_cache_create("ddt_cache",
 422             sizeof (ddt_t), 0, NULL, NULL, NULL, NULL, NULL, 0);
 423         ddt_entry_cache = kmem_cache_create("ddt_entry_cache",
 424             sizeof (ddt_entry_t), 0, NULL, NULL, NULL, NULL, NULL, 0);
 425 }
 426
 427 void
 428 ddt_fini(void)
 429 {
 430         kmem_cache_destroy(ddt_entry_cache);
 431         kmem_cache_destroy(ddt_cache);
 432 }
 433
 434 static ddt_entry_t *
 435 ddt_alloc(const ddt_key_t *ddk)
 436 {
 437         ddt_entry_t *dde;
 438
 439         dde = kmem_cache_alloc(ddt_entry_cache, KM_SLEEP);
 440         memset(dde, 0, sizeof (ddt_entry_t));
 441         cv_init(&dde->dde_cv, NULL, CV_DEFAULT, NULL);
 442
 443         dde->dde_key = *ddk;
 444
 445         return (dde);
 446 }
 447
 448 static void
 449 ddt_free(ddt_entry_t *dde)
 450 {
 451         ASSERT(!dde->dde_loading);
 452
 453         for (int p = 0; p < DDT_PHYS_TYPES; p++)
 454                 ASSERT3P(dde->dde_lead_zio[p], ==, NULL);
 455
 456         if (dde->dde_repair_abd != NULL)
 457                 abd_free(dde->dde_repair_abd);
 458
 459         cv_destroy(&dde->dde_cv);
 460         kmem_cache_free(ddt_entry_cache, dde);
 461 }
 462
 463 void
 464 ddt_remove(ddt_t *ddt, ddt_entry_t *dde)
 465 {
 466         ASSERT(MUTEX_HELD(&ddt->ddt_lock));
 467
 468         avl_remove(&ddt->ddt_tree, dde);
 469         ddt_free(dde);
 470 }
 471
 472 ddt_entry_t *
 473 ddt_lookup(ddt_t *ddt, const blkptr_t *bp, boolean_t add)
 474 {
 475         ddt_key_t search;
 476         ddt_entry_t *dde;
 477         ddt_type_t type;
 478         ddt_class_t class;
 479         avl_index_t where;
 480         int error;
 481
 482         ASSERT(MUTEX_HELD(&ddt->ddt_lock));
 483
 484         ddt_key_fill(&search, bp);
 485
 486         dde = avl_find(&ddt->ddt_tree, &search, &where);
 487         if (dde == NULL) {
 488                 if (!add)
 489                         return (NULL);
 490                 dde = ddt_alloc(&search);
 491                 avl_insert(&ddt->ddt_tree, dde, where);
 492         }
 493
 494         while (dde->dde_loading)
 495                 cv_wait(&dde->dde_cv, &ddt->ddt_lock);
 496
 497         if (dde->dde_loaded)
 498                 return (dde);
 499
 500         dde->dde_loading = B_TRUE;
 501
 502         ddt_exit(ddt);
 503
 504         error = ENOENT;
 505
 506         for (type = 0; type < DDT_TYPES; type++) {
 507                 for (class = 0; class < DDT_CLASSES; class++) {
 508                         error = ddt_object_lookup(ddt, type, class, dde);
 509                         if (error != ENOENT) {
 510                                 ASSERT0(error);
 511                                 break;
 512                         }
 513                 }
 514                 if (error != ENOENT)
 515                         break;
 516         }
 517
 518         ddt_enter(ddt);
 519
 520         ASSERT(!dde->dde_loaded);
 521         ASSERT(dde->dde_loading);
 522
 523         dde->dde_type = type;   /* will be DDT_TYPES if no entry found */
 524         dde->dde_class = class; /* will be DDT_CLASSES if no entry found */
 525         dde->dde_loaded = B_TRUE;
 526         dde->dde_loading = B_FALSE;
 527
 528         if (error == 0)
 529                 ddt_stat_update(ddt, dde, -1ULL);
 530
 531         cv_broadcast(&dde->dde_cv);
 532
 533         return (dde);
 534 }
 535
 536 void
 537 ddt_prefetch(spa_t *spa, const blkptr_t *bp)
 538 {
 539         ddt_t *ddt;
 540         ddt_key_t ddk;
 541
 542         if (!zfs_dedup_prefetch || bp == NULL || !BP_GET_DEDUP(bp))
 543                 return;
 544
 545         /*
 546          * We only remove the DDT once all tables are empty and only
 547          * prefetch dedup blocks when there are entries in the DDT.
 548          * Thus no locking is required as the DDT can't disappear on us.
 549          */
 550         ddt = ddt_select(spa, bp);
 551         ddt_key_fill(&ddk, bp);
 552
 553         for (ddt_type_t type = 0; type < DDT_TYPES; type++) {
 554                 for (ddt_class_t class = 0; class < DDT_CLASSES; class++) {
 555                         ddt_object_prefetch(ddt, type, class, &ddk);
 556                 }
 557         }
 558 }
 559
 560 /*
 561  * Key comparison. Any struct wanting to make use of this function must have
 562  * the key as the first element.
 563  */
 564 #define DDT_KEY_CMP_LEN (sizeof (ddt_key_t) / sizeof (uint16_t))
 565
 566 typedef struct ddt_key_cmp {
 567         uint16_t        u16[DDT_KEY_CMP_LEN];
 568 } ddt_key_cmp_t;
 569
 570 int
 571 ddt_key_compare(const void *x1, const void *x2)
 572 {
 573         const ddt_key_cmp_t *k1 = (const ddt_key_cmp_t *)x1;
 574         const ddt_key_cmp_t *k2 = (const ddt_key_cmp_t *)x2;
 575         int32_t cmp = 0;
 576
 577         for (int i = 0; i < DDT_KEY_CMP_LEN; i++) {
 578                 cmp = (int32_t)k1->u16[i] - (int32_t)k2->u16[i];
 579                 if (likely(cmp))
 580                         break;
 581         }
 582
 583         return (TREE_ISIGN(cmp));
 584 }
 585
 586 static ddt_t *
 587 ddt_table_alloc(spa_t *spa, enum zio_checksum c)
 588 {
 589         ddt_t *ddt;
 590
 591         ddt = kmem_cache_alloc(ddt_cache, KM_SLEEP);
 592         memset(ddt, 0, sizeof (ddt_t));
 593
 594         mutex_init(&ddt->ddt_lock, NULL, MUTEX_DEFAULT, NULL);
 595         avl_create(&ddt->ddt_tree, ddt_key_compare,
 596             sizeof (ddt_entry_t), offsetof(ddt_entry_t, dde_node));
 597         avl_create(&ddt->ddt_repair_tree, ddt_key_compare,
 598             sizeof (ddt_entry_t), offsetof(ddt_entry_t, dde_node));
 599         ddt->ddt_checksum = c;
 600         ddt->ddt_spa = spa;
 601         ddt->ddt_os = spa->spa_meta_objset;
 602
 603         return (ddt);
 604 }
 605
 606 static void
 607 ddt_table_free(ddt_t *ddt)
 608 {
 609         ASSERT0(avl_numnodes(&ddt->ddt_tree));
 610         ASSERT0(avl_numnodes(&ddt->ddt_repair_tree));
 611         avl_destroy(&ddt->ddt_tree);
 612         avl_destroy(&ddt->ddt_repair_tree);
 613         mutex_destroy(&ddt->ddt_lock);
 614         kmem_cache_free(ddt_cache, ddt);
 615 }
 616
 617 void
 618 ddt_create(spa_t *spa)
 619 {
 620         spa->spa_dedup_checksum = ZIO_DEDUPCHECKSUM;
 621
 622         for (enum zio_checksum c = 0; c < ZIO_CHECKSUM_FUNCTIONS; c++)
 623                 spa->spa_ddt[c] = ddt_table_alloc(spa, c);
 624 }
 625
 626 int
 627 ddt_load(spa_t *spa)
 628 {
 629         int error;
 630
 631         ddt_create(spa);
 632
 633         error = zap_lookup(spa->spa_meta_objset, DMU_POOL_DIRECTORY_OBJECT,
 634             DMU_POOL_DDT_STATS, sizeof (uint64_t), 1,
 635             &spa->spa_ddt_stat_object);
 636
 637         if (error)
 638                 return (error == ENOENT ? 0 : error);
 639
 640         for (enum zio_checksum c = 0; c < ZIO_CHECKSUM_FUNCTIONS; c++) {
 641                 ddt_t *ddt = spa->spa_ddt[c];
 642                 for (ddt_type_t type = 0; type < DDT_TYPES; type++) {
 643                         for (ddt_class_t class = 0; class < DDT_CLASSES;
 644                             class++) {
 645                                 error = ddt_object_load(ddt, type, class);
 646                                 if (error != 0 && error != ENOENT)
 647                                         return (error);
 648                         }
 649                 }
 650
 651                 /*
 652                  * Seed the cached histograms.
 653                  */
 654                 memcpy(&ddt->ddt_histogram_cache, ddt->ddt_histogram,
 655                     sizeof (ddt->ddt_histogram));
 656                 spa->spa_dedup_dspace = ~0ULL;
 657         }
 658
 659         return (0);
 660 }
 661
 662 void
 663 ddt_unload(spa_t *spa)
 664 {
 665         for (enum zio_checksum c = 0; c < ZIO_CHECKSUM_FUNCTIONS; c++) {
 666                 if (spa->spa_ddt[c]) {
 667                         ddt_table_free(spa->spa_ddt[c]);
 668                         spa->spa_ddt[c] = NULL;
 669                 }
 670         }
 671 }
 672
 673 boolean_t
 674 ddt_class_contains(spa_t *spa, ddt_class_t max_class, const blkptr_t *bp)
 675 {
 676         ddt_t *ddt;
 677         ddt_key_t ddk;
 678
 679         if (!BP_GET_DEDUP(bp))
 680                 return (B_FALSE);
 681
 682         if (max_class == DDT_CLASS_UNIQUE)
 683                 return (B_TRUE);
 684
 685         ddt = spa->spa_ddt[BP_GET_CHECKSUM(bp)];
 686
 687         ddt_key_fill(&ddk, bp);
 688
 689         for (ddt_type_t type = 0; type < DDT_TYPES; type++) {
 690                 for (ddt_class_t class = 0; class <= max_class; class++) {
 691                         if (ddt_object_contains(ddt, type, class, &ddk) == 0)
 692                                 return (B_TRUE);
 693                 }
 694         }
 695
 696         return (B_FALSE);
 697 }
 698
 699 ddt_entry_t *
 700 ddt_repair_start(ddt_t *ddt, const blkptr_t *bp)
 701 {
 702         ddt_key_t ddk;
 703         ddt_entry_t *dde;
 704
 705         ddt_key_fill(&ddk, bp);
 706
 707         dde = ddt_alloc(&ddk);
 708
 709         for (ddt_type_t type = 0; type < DDT_TYPES; type++) {
 710                 for (ddt_class_t class = 0; class < DDT_CLASSES; class++) {
 711                         /*
 712                          * We can only do repair if there are multiple copies
 713                          * of the block.  For anything in the UNIQUE class,
 714                          * there's definitely only one copy, so don't even try.
 715                          */
 716                         if (class != DDT_CLASS_UNIQUE &&
 717                             ddt_object_lookup(ddt, type, class, dde) == 0)
 718                                 return (dde);
 719                 }
 720         }
 721
 722         memset(dde->dde_phys, 0, sizeof (dde->dde_phys));
 723
 724         return (dde);
 725 }
 726
 727 void
 728 ddt_repair_done(ddt_t *ddt, ddt_entry_t *dde)
 729 {
 730         avl_index_t where;
 731
 732         ddt_enter(ddt);
 733
 734         if (dde->dde_repair_abd != NULL && spa_writeable(ddt->ddt_spa) &&
 735             avl_find(&ddt->ddt_repair_tree, dde, &where) == NULL)
 736                 avl_insert(&ddt->ddt_repair_tree, dde, where);
 737         else
 738                 ddt_free(dde);
 739
 740         ddt_exit(ddt);
 741 }
 742
 743 static void
 744 ddt_repair_entry_done(zio_t *zio)
 745 {
 746         ddt_entry_t *rdde = zio->io_private;
 747
 748         ddt_free(rdde);
 749 }
 750
 751 static void
 752 ddt_repair_entry(ddt_t *ddt, ddt_entry_t *dde, ddt_entry_t *rdde, zio_t *rio)
 753 {
 754         ddt_phys_t *ddp = dde->dde_phys;
 755         ddt_phys_t *rddp = rdde->dde_phys;
 756         ddt_key_t *ddk = &dde->dde_key;
 757         ddt_key_t *rddk = &rdde->dde_key;
 758         zio_t *zio;
 759         blkptr_t blk;
 760
 761         zio = zio_null(rio, rio->io_spa, NULL,
 762             ddt_repair_entry_done, rdde, rio->io_flags);
 763
 764         for (int p = 0; p < DDT_PHYS_TYPES; p++, ddp++, rddp++) {
 765                 if (ddp->ddp_phys_birth == 0 ||
 766                     ddp->ddp_phys_birth != rddp->ddp_phys_birth ||
 767                     memcmp(ddp->ddp_dva, rddp->ddp_dva, sizeof (ddp->ddp_dva)))
 768                         continue;
 769                 ddt_bp_create(ddt->ddt_checksum, ddk, ddp, &blk);
 770                 zio_nowait(zio_rewrite(zio, zio->io_spa, 0, &blk,
 771                     rdde->dde_repair_abd, DDK_GET_PSIZE(rddk), NULL, NULL,
 772                     ZIO_PRIORITY_SYNC_WRITE, ZIO_DDT_CHILD_FLAGS(zio), NULL));
 773         }
 774
 775         zio_nowait(zio);
 776 }
 777
 778 static void
 779 ddt_repair_table(ddt_t *ddt, zio_t *rio)
 780 {
 781         spa_t *spa = ddt->ddt_spa;
 782         ddt_entry_t *dde, *rdde_next, *rdde;
 783         avl_tree_t *t = &ddt->ddt_repair_tree;
 784         blkptr_t blk;
 785
 786         if (spa_sync_pass(spa) > 1)
 787                 return;
 788
 789         ddt_enter(ddt);
 790         for (rdde = avl_first(t); rdde != NULL; rdde = rdde_next) {
 791                 rdde_next = AVL_NEXT(t, rdde);
 792                 avl_remove(&ddt->ddt_repair_tree, rdde);
 793                 ddt_exit(ddt);
 794                 ddt_bp_create(ddt->ddt_checksum, &rdde->dde_key, NULL, &blk);
 795                 dde = ddt_repair_start(ddt, &blk);
 796                 ddt_repair_entry(ddt, dde, rdde, rio);
 797                 ddt_repair_done(ddt, dde);
 798                 ddt_enter(ddt);
 799         }
 800         ddt_exit(ddt);
 801 }
 802
 803 static void
 804 ddt_sync_entry(ddt_t *ddt, ddt_entry_t *dde, dmu_tx_t *tx, uint64_t txg)
 805 {
 806         dsl_pool_t *dp = ddt->ddt_spa->spa_dsl_pool;
 807         ddt_phys_t *ddp = dde->dde_phys;
 808         ddt_key_t *ddk = &dde->dde_key;
 809         ddt_type_t otype = dde->dde_type;
 810         ddt_type_t ntype = DDT_TYPE_DEFAULT;
 811         ddt_class_t oclass = dde->dde_class;
 812         ddt_class_t nclass;
 813         uint64_t total_refcnt = 0;
 814
 815         ASSERT(dde->dde_loaded);
 816         ASSERT(!dde->dde_loading);
 817
 818         for (int p = 0; p < DDT_PHYS_TYPES; p++, ddp++) {
 819                 ASSERT3P(dde->dde_lead_zio[p], ==, NULL);
 820                 if (ddp->ddp_phys_birth == 0) {
 821                         ASSERT0(ddp->ddp_refcnt);
 822                         continue;
 823                 }
 824                 if (p == DDT_PHYS_DITTO) {
 825                         /*
 826                          * Note, we no longer create DDT-DITTO blocks, but we
 827                          * don't want to leak any written by older software.
 828                          */
 829                         ddt_phys_free(ddt, ddk, ddp, txg);
 830                         continue;
 831                 }
 832                 if (ddp->ddp_refcnt == 0)
 833                         ddt_phys_free(ddt, ddk, ddp, txg);
 834                 total_refcnt += ddp->ddp_refcnt;
 835         }
 836
 837         /* We do not create new DDT-DITTO blocks. */
 838         ASSERT0(dde->dde_phys[DDT_PHYS_DITTO].ddp_phys_birth);
 839         if (total_refcnt > 1)
 840                 nclass = DDT_CLASS_DUPLICATE;
 841         else
 842                 nclass = DDT_CLASS_UNIQUE;
 843
 844         if (otype != DDT_TYPES &&
 845             (otype != ntype || oclass != nclass || total_refcnt == 0)) {
 846                 VERIFY0(ddt_object_remove(ddt, otype, oclass, ddk, tx));
 847                 ASSERT3U(
 848                     ddt_object_contains(ddt, otype, oclass, ddk), ==, ENOENT);
 849         }
 850
 851         if (total_refcnt != 0) {
 852                 dde->dde_type = ntype;
 853                 dde->dde_class = nclass;
 854                 ddt_stat_update(ddt, dde, 0);
 855                 if (!ddt_object_exists(ddt, ntype, nclass))
 856                         ddt_object_create(ddt, ntype, nclass, tx);
 857                 VERIFY0(ddt_object_update(ddt, ntype, nclass, dde, tx));
 858
 859                 /*
 860                  * If the class changes, the order that we scan this bp
 861                  * changes.  If it decreases, we could miss it, so
 862                  * scan it right now.  (This covers both class changing
 863                  * while we are doing ddt_walk(), and when we are
 864                  * traversing.)
 865                  */
 866                 if (nclass < oclass) {
 867                         dsl_scan_ddt_entry(dp->dp_scan,
 868                             ddt->ddt_checksum, dde, tx);
 869                 }
 870         }
 871 }
 872
 873 static void
 874 ddt_sync_table(ddt_t *ddt, dmu_tx_t *tx, uint64_t txg)
 875 {
 876         spa_t *spa = ddt->ddt_spa;
 877         ddt_entry_t *dde;
 878         void *cookie = NULL;
 879
 880         if (avl_numnodes(&ddt->ddt_tree) == 0)
 881                 return;
 882
 883         ASSERT3U(spa->spa_uberblock.ub_version, >=, SPA_VERSION_DEDUP);
 884
 885         if (spa->spa_ddt_stat_object == 0) {
 886                 spa->spa_ddt_stat_object = zap_create_link(ddt->ddt_os,
 887                     DMU_OT_DDT_STATS, DMU_POOL_DIRECTORY_OBJECT,
 888                     DMU_POOL_DDT_STATS, tx);
 889         }
 890
 891         while ((dde = avl_destroy_nodes(&ddt->ddt_tree, &cookie)) != NULL) {
 892                 ddt_sync_entry(ddt, dde, tx, txg);
 893                 ddt_free(dde);
 894         }
 895
 896         for (ddt_type_t type = 0; type < DDT_TYPES; type++) {
 897                 uint64_t add, count = 0;
 898                 for (ddt_class_t class = 0; class < DDT_CLASSES; class++) {
 899                         if (ddt_object_exists(ddt, type, class)) {
 900                                 ddt_object_sync(ddt, type, class, tx);
 901                                 VERIFY0(ddt_object_count(ddt, type, class,
 902                                     &add));
 903                                 count += add;
 904                         }
 905                 }
 906                 for (ddt_class_t class = 0; class < DDT_CLASSES; class++) {
 907                         if (count == 0 && ddt_object_exists(ddt, type, class))
 908                                 ddt_object_destroy(ddt, type, class, tx);
 909                 }
 910         }
 911
 912         memcpy(&ddt->ddt_histogram_cache, ddt->ddt_histogram,
 913             sizeof (ddt->ddt_histogram));
 914         spa->spa_dedup_dspace = ~0ULL;
 915 }
 916
 917 void
 918 ddt_sync(spa_t *spa, uint64_t txg)
 919 {
 920         dsl_scan_t *scn = spa->spa_dsl_pool->dp_scan;
 921         dmu_tx_t *tx;
 922         zio_t *rio;
 923
 924         ASSERT3U(spa_syncing_txg(spa), ==, txg);
 925
 926         tx = dmu_tx_create_assigned(spa->spa_dsl_pool, txg);
 927
 928         rio = zio_root(spa, NULL, NULL,
 929             ZIO_FLAG_CANFAIL | ZIO_FLAG_SPECULATIVE | ZIO_FLAG_SELF_HEAL);
 930
 931         /*
 932          * This function may cause an immediate scan of ddt blocks (see
 933          * the comment above dsl_scan_ddt() for details). We set the
 934          * scan's root zio here so that we can wait for any scan IOs in
 935          * addition to the regular ddt IOs.
 936          */
 937         ASSERT3P(scn->scn_zio_root, ==, NULL);
 938         scn->scn_zio_root = rio;
 939
 940         for (enum zio_checksum c = 0; c < ZIO_CHECKSUM_FUNCTIONS; c++) {
 941                 ddt_t *ddt = spa->spa_ddt[c];
 942                 if (ddt == NULL)
 943                         continue;
 944                 ddt_sync_table(ddt, tx, txg);
 945                 ddt_repair_table(ddt, rio);
 946         }
 947
 948         (void) zio_wait(rio);
 949         scn->scn_zio_root = NULL;
 950
 951         dmu_tx_commit(tx);
 952 }
 953
 954 int
 955 ddt_walk(spa_t *spa, ddt_bookmark_t *ddb, ddt_entry_t *dde)
 956 {
 957         do {
 958                 do {
 959                         do {
 960                                 ddt_t *ddt = spa->spa_ddt[ddb->ddb_checksum];
 961                                 int error = ENOENT;
 962                                 if (ddt_object_exists(ddt, ddb->ddb_type,
 963                                     ddb->ddb_class)) {
 964                                         error = ddt_object_walk(ddt,
 965                                             ddb->ddb_type, ddb->ddb_class,
 966                                             &ddb->ddb_cursor, dde);
 967                                 }
 968                                 dde->dde_type = ddb->ddb_type;
 969                                 dde->dde_class = ddb->ddb_class;
 970                                 if (error == 0)
 971                                         return (0);
 972                                 if (error != ENOENT)
 973                                         return (error);
 974                                 ddb->ddb_cursor = 0;
 975                         } while (++ddb->ddb_checksum < ZIO_CHECKSUM_FUNCTIONS);
 976                         ddb->ddb_checksum = 0;
 977                 } while (++ddb->ddb_type < DDT_TYPES);
 978                 ddb->ddb_type = 0;
 979         } while (++ddb->ddb_class < DDT_CLASSES);
 980
 981         return (SET_ERROR(ENOENT));
 982 }
 983
 984 /*
 985  * This function is used by Block Cloning (brt.c) to increase reference
 986  * counter for the DDT entry if the block is already in DDT.
 987  *
 988  * Return false if the block, despite having the D bit set, is not present
 989  * in the DDT. Currently this is not possible but might be in the future.
 990  * See the comment below.
 991  */
 992 boolean_t
 993 ddt_addref(spa_t *spa, const blkptr_t *bp)
 994 {
 995         ddt_t *ddt;
 996         ddt_entry_t *dde;
 997         boolean_t result;
 998
 999         spa_config_enter(spa, SCL_ZIO, FTAG, RW_READER);
1000         ddt = ddt_select(spa, bp);
1001         ddt_enter(ddt);
1002
1003         dde = ddt_lookup(ddt, bp, B_TRUE);
1004         ASSERT3P(dde, !=, NULL);
1005
1006         if (dde->dde_type < DDT_TYPES) {
1007                 ddt_phys_t *ddp;
1008
1009                 ASSERT3S(dde->dde_class, <, DDT_CLASSES);
1010
1011                 ddp = &dde->dde_phys[BP_GET_NDVAS(bp)];
1012
1013                 /*
1014                  * This entry already existed (dde_type is real), so it must
1015                  * have refcnt >0 at the start of this txg. We are called from
1016                  * brt_pending_apply(), before frees are issued, so the refcnt
1017                  * can't be lowered yet. Therefore, it must be >0. We assert
1018                  * this because if the order of BRT and DDT interactions were
1019                  * ever to change and the refcnt was ever zero here, then
1020                  * likely further action is required to fill out the DDT entry,
1021                  * and this is a place that is likely to be missed in testing.
1022                  */
1023                 ASSERT3U(ddp->ddp_refcnt, >, 0);
1024
1025                 ddt_phys_addref(ddp);
1026                 result = B_TRUE;
1027         } else {
1028                 /*
1029                  * At the time of implementating this if the block has the
1030                  * DEDUP flag set it must exist in the DEDUP table, but
1031                  * there are many advocates that want ability to remove
1032                  * entries from DDT with refcnt=1. If this will happen,
1033                  * we may have a block with the DEDUP set, but which doesn't
1034                  * have a corresponding entry in the DDT. Be ready.
1035                  */
1036                 ASSERT3S(dde->dde_class, ==, DDT_CLASSES);
1037                 ddt_remove(ddt, dde);
1038                 result = B_FALSE;
1039         }
1040
1041         ddt_exit(ddt);
1042         spa_config_exit(spa, SCL_ZIO, FTAG);
1043
1044         return (result);
1045 }
1046
1047 ZFS_MODULE_PARAM(zfs_dedup, zfs_dedup_, prefetch, INT, ZMOD_RW,
1048         "Enable prefetching dedup-ed blks");