drivers/md/dm-thin-metadata.c

   1 /*
   2  * Copyright (C) 2011 Red Hat, Inc.
   3  *
   4  * This file is released under the GPL.
   5  */
   6
   7 #include "dm-thin-metadata.h"
   8 #include "persistent-data/dm-btree.h"
   9 #include "persistent-data/dm-space-map.h"
  10 #include "persistent-data/dm-space-map-disk.h"
  11 #include "persistent-data/dm-transaction-manager.h"
  12
  13 #include <linux/list.h>
  14 #include <linux/device-mapper.h>
  15 #include <linux/workqueue.h>
  16
  17 /*--------------------------------------------------------------------------
  18  * As far as the metadata goes, there is:
  19  *
  20  * - A superblock in block zero, taking up fewer than 512 bytes for
  21  *   atomic writes.
  22  *
  23  * - A space map managing the metadata blocks.
  24  *
  25  * - A space map managing the data blocks.
  26  *
  27  * - A btree mapping our internal thin dev ids onto struct disk_device_details.
  28  *
  29  * - A hierarchical btree, with 2 levels which effectively maps (thin
  30  *   dev id, virtual block) -> block_time.  Block time is a 64-bit
  31  *   field holding the time in the low 24 bits, and block in the top 48
  32  *   bits.
  33  *
  34  * BTrees consist solely of btree_nodes, that fill a block.  Some are
  35  * internal nodes, as such their values are a __le64 pointing to other
  36  * nodes.  Leaf nodes can store data of any reasonable size (ie. much
  37  * smaller than the block size).  The nodes consist of the header,
  38  * followed by an array of keys, followed by an array of values.  We have
  39  * to binary search on the keys so they're all held together to help the
  40  * cpu cache.
  41  *
  42  * Space maps have 2 btrees:
  43  *
  44  * - One maps a uint64_t onto a struct index_entry.  Which points to a
  45  *   bitmap block, and has some details about how many free entries there
  46  *   are etc.
  47  *
  48  * - The bitmap blocks have a header (for the checksum).  Then the rest
  49  *   of the block is pairs of bits.  With the meaning being:
  50  *
  51  *   0 - ref count is 0
  52  *   1 - ref count is 1
  53  *   2 - ref count is 2
  54  *   3 - ref count is higher than 2
  55  *
  56  * - If the count is higher than 2 then the ref count is entered in a
  57  *   second btree that directly maps the block_address to a uint32_t ref
  58  *   count.
  59  *
  60  * The space map metadata variant doesn't have a bitmaps btree.  Instead
  61  * it has one single blocks worth of index_entries.  This avoids
  62  * recursive issues with the bitmap btree needing to allocate space in
  63  * order to insert.  With a small data block size such as 64k the
  64  * metadata support data devices that are hundreds of terrabytes.
  65  *
  66  * The space maps allocate space linearly from front to back.  Space that
  67  * is freed in a transaction is never recycled within that transaction.
  68  * To try and avoid fragmenting _free_ space the allocator always goes
  69  * back and fills in gaps.
  70  *
  71  * All metadata io is in THIN_METADATA_BLOCK_SIZE sized/aligned chunks
  72  * from the block manager.
  73  *--------------------------------------------------------------------------*/
  74
  75 #define DM_MSG_PREFIX   "thin metadata"
  76
  77 #define THIN_SUPERBLOCK_MAGIC 27022010
  78 #define THIN_SUPERBLOCK_LOCATION 0
  79 #define THIN_VERSION 1
  80 #define THIN_METADATA_CACHE_SIZE 64
  81 #define SECTOR_TO_BLOCK_SHIFT 3
  82
  83 /*
  84  * For btree insert:
  85  *  3 for btree insert +
  86  *  2 for btree lookup used within space map
  87  * For btree remove:
  88  *  2 for shadow spine +
  89  *  4 for rebalance 3 child node
  90  */
  91 #define THIN_MAX_CONCURRENT_LOCKS 6
  92
  93 /* This should be plenty */
  94 #define SPACE_MAP_ROOT_SIZE 128
  95
  96 /*
  97  * Little endian on-disk superblock and device details.
  98  */
  99 struct thin_disk_superblock {
 100         __le32 csum;    /* Checksum of superblock except for this field. */
 101         __le32 flags;
 102         __le64 blocknr; /* This block number, dm_block_t. */
 103
 104         __u8 uuid[16];
 105         __le64 magic;
 106         __le32 version;
 107         __le32 time;
 108
 109         __le64 trans_id;
 110
 111         /*
 112          * Root held by userspace transactions.
 113          */
 114         __le64 held_root;
 115
 116         __u8 data_space_map_root[SPACE_MAP_ROOT_SIZE];
 117         __u8 metadata_space_map_root[SPACE_MAP_ROOT_SIZE];
 118
 119         /*
 120          * 2-level btree mapping (dev_id, (dev block, time)) -> data block
 121          */
 122         __le64 data_mapping_root;
 123
 124         /*
 125          * Device detail root mapping dev_id -> device_details
 126          */
 127         __le64 device_details_root;
 128
 129         __le32 data_block_size;         /* In 512-byte sectors. */
 130
 131         __le32 metadata_block_size;     /* In 512-byte sectors. */
 132         __le64 metadata_nr_blocks;
 133
 134         __le32 compat_flags;
 135         __le32 compat_ro_flags;
 136         __le32 incompat_flags;
 137 } __packed;
 138
 139 struct disk_device_details {
 140         __le64 mapped_blocks;
 141         __le64 transaction_id;          /* When created. */
 142         __le32 creation_time;
 143         __le32 snapshotted_time;
 144 } __packed;
 145
 146 struct dm_pool_metadata {
 147         struct hlist_node hash;
 148
 149         struct block_device *bdev;
 150         struct dm_block_manager *bm;
 151         struct dm_space_map *metadata_sm;
 152         struct dm_space_map *data_sm;
 153         struct dm_transaction_manager *tm;
 154         struct dm_transaction_manager *nb_tm;
 155
 156         /*
 157          * Two-level btree.
 158          * First level holds thin_dev_t.
 159          * Second level holds mappings.
 160          */
 161         struct dm_btree_info info;
 162
 163         /*
 164          * Non-blocking version of the above.
 165          */
 166         struct dm_btree_info nb_info;
 167
 168         /*
 169          * Just the top level for deleting whole devices.
 170          */
 171         struct dm_btree_info tl_info;
 172
 173         /*
 174          * Just the bottom level for creating new devices.
 175          */
 176         struct dm_btree_info bl_info;
 177
 178         /*
 179          * Describes the device details btree.
 180          */
 181         struct dm_btree_info details_info;
 182
 183         struct rw_semaphore root_lock;
 184         uint32_t time;
 185         int need_commit;
 186         dm_block_t root;
 187         dm_block_t details_root;
 188         struct list_head thin_devices;
 189         uint64_t trans_id;
 190         unsigned long flags;
 191         sector_t data_block_size;
 192 };
 193
 194 struct dm_thin_device {
 195         struct list_head list;
 196         struct dm_pool_metadata *pmd;
 197         dm_thin_id id;
 198
 199         int open_count;
 200         int changed;
 201         uint64_t mapped_blocks;
 202         uint64_t transaction_id;
 203         uint32_t creation_time;
 204         uint32_t snapshotted_time;
 205 };
 206
 207 /*----------------------------------------------------------------
 208  * superblock validator
 209  *--------------------------------------------------------------*/
 210
 211 #define SUPERBLOCK_CSUM_XOR 160774
 212
 213 static void sb_prepare_for_write(struct dm_block_validator *v,
 214                                  struct dm_block *b,
 215                                  size_t block_size)
 216 {
 217         struct thin_disk_superblock *disk_super = dm_block_data(b);
 218
 219         disk_super->blocknr = cpu_to_le64(dm_block_location(b));
 220         disk_super->csum = cpu_to_le32(dm_bm_checksum(&disk_super->flags,
 221                                                       block_size - sizeof(__le32),
 222                                                       SUPERBLOCK_CSUM_XOR));
 223 }
 224
 225 static int sb_check(struct dm_block_validator *v,
 226                     struct dm_block *b,
 227                     size_t block_size)
 228 {
 229         struct thin_disk_superblock *disk_super = dm_block_data(b);
 230         __le32 csum_le;
 231
 232         if (dm_block_location(b) != le64_to_cpu(disk_super->blocknr)) {
 233                 DMERR("sb_check failed: blocknr %llu: "
 234                       "wanted %llu", le64_to_cpu(disk_super->blocknr),
 235                       (unsigned long long)dm_block_location(b));
 236                 return -ENOTBLK;
 237         }
 238
 239         if (le64_to_cpu(disk_super->magic) != THIN_SUPERBLOCK_MAGIC) {
 240                 DMERR("sb_check failed: magic %llu: "
 241                       "wanted %llu", le64_to_cpu(disk_super->magic),
 242                       (unsigned long long)THIN_SUPERBLOCK_MAGIC);
 243                 return -EILSEQ;
 244         }
 245
 246         csum_le = cpu_to_le32(dm_bm_checksum(&disk_super->flags,
 247                                              block_size - sizeof(__le32),
 248                                              SUPERBLOCK_CSUM_XOR));
 249         if (csum_le != disk_super->csum) {
 250                 DMERR("sb_check failed: csum %u: wanted %u",
 251                       le32_to_cpu(csum_le), le32_to_cpu(disk_super->csum));
 252                 return -EILSEQ;
 253         }
 254
 255         return 0;
 256 }
 257
 258 static struct dm_block_validator sb_validator = {
 259         .name = "superblock",
 260         .prepare_for_write = sb_prepare_for_write,
 261         .check = sb_check
 262 };
 263
 264 /*----------------------------------------------------------------
 265  * Methods for the btree value types
 266  *--------------------------------------------------------------*/
 267
 268 static uint64_t pack_block_time(dm_block_t b, uint32_t t)
 269 {
 270         return (b << 24) | t;
 271 }
 272
 273 static void unpack_block_time(uint64_t v, dm_block_t *b, uint32_t *t)
 274 {
 275         *b = v >> 24;
 276         *t = v & ((1 << 24) - 1);
 277 }
 278
 279 static void data_block_inc(void *context, void *value_le)
 280 {
 281         struct dm_space_map *sm = context;
 282         __le64 v_le;
 283         uint64_t b;
 284         uint32_t t;
 285
 286         memcpy(&v_le, value_le, sizeof(v_le));
 287         unpack_block_time(le64_to_cpu(v_le), &b, &t);
 288         dm_sm_inc_block(sm, b);
 289 }
 290
 291 static void data_block_dec(void *context, void *value_le)
 292 {
 293         struct dm_space_map *sm = context;
 294         __le64 v_le;
 295         uint64_t b;
 296         uint32_t t;
 297
 298         memcpy(&v_le, value_le, sizeof(v_le));
 299         unpack_block_time(le64_to_cpu(v_le), &b, &t);
 300         dm_sm_dec_block(sm, b);
 301 }
 302
 303 static int data_block_equal(void *context, void *value1_le, void *value2_le)
 304 {
 305         __le64 v1_le, v2_le;
 306         uint64_t b1, b2;
 307         uint32_t t;
 308
 309         memcpy(&v1_le, value1_le, sizeof(v1_le));
 310         memcpy(&v2_le, value2_le, sizeof(v2_le));
 311         unpack_block_time(le64_to_cpu(v1_le), &b1, &t);
 312         unpack_block_time(le64_to_cpu(v2_le), &b2, &t);
 313
 314         return b1 == b2;
 315 }
 316
 317 static void subtree_inc(void *context, void *value)
 318 {
 319         struct dm_btree_info *info = context;
 320         __le64 root_le;
 321         uint64_t root;
 322
 323         memcpy(&root_le, value, sizeof(root_le));
 324         root = le64_to_cpu(root_le);
 325         dm_tm_inc(info->tm, root);
 326 }
 327
 328 static void subtree_dec(void *context, void *value)
 329 {
 330         struct dm_btree_info *info = context;
 331         __le64 root_le;
 332         uint64_t root;
 333
 334         memcpy(&root_le, value, sizeof(root_le));
 335         root = le64_to_cpu(root_le);
 336         if (dm_btree_del(info, root))
 337                 DMERR("btree delete failed\n");
 338 }
 339
 340 static int subtree_equal(void *context, void *value1_le, void *value2_le)
 341 {
 342         __le64 v1_le, v2_le;
 343         memcpy(&v1_le, value1_le, sizeof(v1_le));
 344         memcpy(&v2_le, value2_le, sizeof(v2_le));
 345
 346         return v1_le == v2_le;
 347 }
 348
 349 /*----------------------------------------------------------------*/
 350
 351 static int superblock_all_zeroes(struct dm_block_manager *bm, int *result)
 352 {
 353         int r;
 354         unsigned i;
 355         struct dm_block *b;
 356         __le64 *data_le, zero = cpu_to_le64(0);
 357         unsigned block_size = dm_bm_block_size(bm) / sizeof(__le64);
 358
 359         /*
 360          * We can't use a validator here - it may be all zeroes.
 361          */
 362         r = dm_bm_read_lock(bm, THIN_SUPERBLOCK_LOCATION, NULL, &b);
 363         if (r)
 364                 return r;
 365
 366         data_le = dm_block_data(b);
 367         *result = 1;
 368         for (i = 0; i < block_size; i++) {
 369                 if (data_le[i] != zero) {
 370                         *result = 0;
 371                         break;
 372                 }
 373         }
 374
 375         return dm_bm_unlock(b);
 376 }
 377
 378 static int init_pmd(struct dm_pool_metadata *pmd,
 379                     struct dm_block_manager *bm,
 380                     dm_block_t nr_blocks, int create)
 381 {
 382         int r;
 383         struct dm_space_map *sm, *data_sm;
 384         struct dm_transaction_manager *tm;
 385         struct dm_block *sblock;
 386
 387         if (create) {
 388                 r = dm_tm_create_with_sm(bm, THIN_SUPERBLOCK_LOCATION,
 389                                          &sb_validator, &tm, &sm, &sblock);
 390                 if (r < 0) {
 391                         DMERR("tm_create_with_sm failed");
 392                         return r;
 393                 }
 394
 395                 data_sm = dm_sm_disk_create(tm, nr_blocks);
 396                 if (IS_ERR(data_sm)) {
 397                         DMERR("sm_disk_create failed");
 398                         dm_tm_unlock(tm, sblock);
 399                         r = PTR_ERR(data_sm);
 400                         goto bad;
 401                 }
 402         } else {
 403                 struct thin_disk_superblock *disk_super = NULL;
 404                 size_t space_map_root_offset =
 405                         offsetof(struct thin_disk_superblock, metadata_space_map_root);
 406
 407                 r = dm_tm_open_with_sm(bm, THIN_SUPERBLOCK_LOCATION,
 408                                        &sb_validator, space_map_root_offset,
 409                                        SPACE_MAP_ROOT_SIZE, &tm, &sm, &sblock);
 410                 if (r < 0) {
 411                         DMERR("tm_open_with_sm failed");
 412                         return r;
 413                 }
 414
 415                 disk_super = dm_block_data(sblock);
 416                 data_sm = dm_sm_disk_open(tm, disk_super->data_space_map_root,
 417                                           sizeof(disk_super->data_space_map_root));
 418                 if (IS_ERR(data_sm)) {
 419                         DMERR("sm_disk_open failed");
 420                         r = PTR_ERR(data_sm);
 421                         goto bad;
 422                 }
 423         }
 424
 425
 426         r = dm_tm_unlock(tm, sblock);
 427         if (r < 0) {
 428                 DMERR("couldn't unlock superblock");
 429                 goto bad_data_sm;
 430         }
 431
 432         pmd->bm = bm;
 433         pmd->metadata_sm = sm;
 434         pmd->data_sm = data_sm;
 435         pmd->tm = tm;
 436         pmd->nb_tm = dm_tm_create_non_blocking_clone(tm);
 437         if (!pmd->nb_tm) {
 438                 DMERR("could not create clone tm");
 439                 r = -ENOMEM;
 440                 goto bad_data_sm;
 441         }
 442
 443         pmd->info.tm = tm;
 444         pmd->info.levels = 2;
 445         pmd->info.value_type.context = pmd->data_sm;
 446         pmd->info.value_type.size = sizeof(__le64);
 447         pmd->info.value_type.inc = data_block_inc;
 448         pmd->info.value_type.dec = data_block_dec;
 449         pmd->info.value_type.equal = data_block_equal;
 450
 451         memcpy(&pmd->nb_info, &pmd->info, sizeof(pmd->nb_info));
 452         pmd->nb_info.tm = pmd->nb_tm;
 453
 454         pmd->tl_info.tm = tm;
 455         pmd->tl_info.levels = 1;
 456         pmd->tl_info.value_type.context = &pmd->info;
 457         pmd->tl_info.value_type.size = sizeof(__le64);
 458         pmd->tl_info.value_type.inc = subtree_inc;
 459         pmd->tl_info.value_type.dec = subtree_dec;
 460         pmd->tl_info.value_type.equal = subtree_equal;
 461
 462         pmd->bl_info.tm = tm;
 463         pmd->bl_info.levels = 1;
 464         pmd->bl_info.value_type.context = pmd->data_sm;
 465         pmd->bl_info.value_type.size = sizeof(__le64);
 466         pmd->bl_info.value_type.inc = data_block_inc;
 467         pmd->bl_info.value_type.dec = data_block_dec;
 468         pmd->bl_info.value_type.equal = data_block_equal;
 469
 470         pmd->details_info.tm = tm;
 471         pmd->details_info.levels = 1;
 472         pmd->details_info.value_type.context = NULL;
 473         pmd->details_info.value_type.size = sizeof(struct disk_device_details);
 474         pmd->details_info.value_type.inc = NULL;
 475         pmd->details_info.value_type.dec = NULL;
 476         pmd->details_info.value_type.equal = NULL;
 477
 478         pmd->root = 0;
 479
 480         init_rwsem(&pmd->root_lock);
 481         pmd->time = 0;
 482         pmd->need_commit = 0;
 483         pmd->details_root = 0;
 484         pmd->trans_id = 0;
 485         pmd->flags = 0;
 486         INIT_LIST_HEAD(&pmd->thin_devices);
 487
 488         return 0;
 489
 490 bad_data_sm:
 491         dm_sm_destroy(data_sm);
 492 bad:
 493         dm_tm_destroy(tm);
 494         dm_sm_destroy(sm);
 495
 496         return r;
 497 }
 498
 499 static int __begin_transaction(struct dm_pool_metadata *pmd)
 500 {
 501         int r;
 502         u32 features;
 503         struct thin_disk_superblock *disk_super;
 504         struct dm_block *sblock;
 505
 506         /*
 507          * __maybe_commit_transaction() resets these
 508          */
 509         WARN_ON(pmd->need_commit);
 510
 511         /*
 512          * We re-read the superblock every time.  Shouldn't need to do this
 513          * really.
 514          */
 515         r = dm_bm_read_lock(pmd->bm, THIN_SUPERBLOCK_LOCATION,
 516                             &sb_validator, &sblock);
 517         if (r)
 518                 return r;
 519
 520         disk_super = dm_block_data(sblock);
 521         pmd->time = le32_to_cpu(disk_super->time);
 522         pmd->root = le64_to_cpu(disk_super->data_mapping_root);
 523         pmd->details_root = le64_to_cpu(disk_super->device_details_root);
 524         pmd->trans_id = le64_to_cpu(disk_super->trans_id);
 525         pmd->flags = le32_to_cpu(disk_super->flags);
 526         pmd->data_block_size = le32_to_cpu(disk_super->data_block_size);
 527
 528         features = le32_to_cpu(disk_super->incompat_flags) & ~THIN_FEATURE_INCOMPAT_SUPP;
 529         if (features) {
 530                 DMERR("could not access metadata due to "
 531                       "unsupported optional features (%lx).",
 532                       (unsigned long)features);
 533                 r = -EINVAL;
 534                 goto out;
 535         }
 536
 537         /*
 538          * Check for read-only metadata to skip the following RDWR checks.
 539          */
 540         if (get_disk_ro(pmd->bdev->bd_disk))
 541                 goto out;
 542
 543         features = le32_to_cpu(disk_super->compat_ro_flags) & ~THIN_FEATURE_COMPAT_RO_SUPP;
 544         if (features) {
 545                 DMERR("could not access metadata RDWR due to "
 546                       "unsupported optional features (%lx).",
 547                       (unsigned long)features);
 548                 r = -EINVAL;
 549         }
 550
 551 out:
 552         dm_bm_unlock(sblock);
 553         return r;
 554 }
 555
 556 static int __write_changed_details(struct dm_pool_metadata *pmd)
 557 {
 558         int r;
 559         struct dm_thin_device *td, *tmp;
 560         struct disk_device_details details;
 561         uint64_t key;
 562
 563         list_for_each_entry_safe(td, tmp, &pmd->thin_devices, list) {
 564                 if (!td->changed)
 565                         continue;
 566
 567                 key = td->id;
 568
 569                 details.mapped_blocks = cpu_to_le64(td->mapped_blocks);
 570                 details.transaction_id = cpu_to_le64(td->transaction_id);
 571                 details.creation_time = cpu_to_le32(td->creation_time);
 572                 details.snapshotted_time = cpu_to_le32(td->snapshotted_time);
 573                 __dm_bless_for_disk(&details);
 574
 575                 r = dm_btree_insert(&pmd->details_info, pmd->details_root,
 576                                     &key, &details, &pmd->details_root);
 577                 if (r)
 578                         return r;
 579
 580                 if (td->open_count)
 581                         td->changed = 0;
 582                 else {
 583                         list_del(&td->list);
 584                         kfree(td);
 585                 }
 586
 587                 pmd->need_commit = 1;
 588         }
 589
 590         return 0;
 591 }
 592
 593 static int __commit_transaction(struct dm_pool_metadata *pmd)
 594 {
 595         /*
 596          * FIXME: Associated pool should be made read-only on failure.
 597          */
 598         int r;
 599         size_t metadata_len, data_len;
 600         struct thin_disk_superblock *disk_super;
 601         struct dm_block *sblock;
 602
 603         /*
 604          * We need to know if the thin_disk_superblock exceeds a 512-byte sector.
 605          */
 606         BUILD_BUG_ON(sizeof(struct thin_disk_superblock) > 512);
 607
 608         r = __write_changed_details(pmd);
 609         if (r < 0)
 610                 goto out;
 611
 612         if (!pmd->need_commit)
 613                 goto out;
 614
 615         r = dm_sm_commit(pmd->data_sm);
 616         if (r < 0)
 617                 goto out;
 618
 619         r = dm_tm_pre_commit(pmd->tm);
 620         if (r < 0)
 621                 goto out;
 622
 623         r = dm_sm_root_size(pmd->metadata_sm, &metadata_len);
 624         if (r < 0)
 625                 goto out;
 626
 627         r = dm_sm_root_size(pmd->metadata_sm, &data_len);
 628         if (r < 0)
 629                 goto out;
 630
 631         r = dm_bm_write_lock(pmd->bm, THIN_SUPERBLOCK_LOCATION,
 632                              &sb_validator, &sblock);
 633         if (r)
 634                 goto out;
 635
 636         disk_super = dm_block_data(sblock);
 637         disk_super->time = cpu_to_le32(pmd->time);
 638         disk_super->data_mapping_root = cpu_to_le64(pmd->root);
 639         disk_super->device_details_root = cpu_to_le64(pmd->details_root);
 640         disk_super->trans_id = cpu_to_le64(pmd->trans_id);
 641         disk_super->flags = cpu_to_le32(pmd->flags);
 642
 643         r = dm_sm_copy_root(pmd->metadata_sm, &disk_super->metadata_space_map_root,
 644                             metadata_len);
 645         if (r < 0)
 646                 goto out_locked;
 647
 648         r = dm_sm_copy_root(pmd->data_sm, &disk_super->data_space_map_root,
 649                             data_len);
 650         if (r < 0)
 651                 goto out_locked;
 652
 653         r = dm_tm_commit(pmd->tm, sblock);
 654         if (!r)
 655                 pmd->need_commit = 0;
 656
 657 out:
 658         return r;
 659
 660 out_locked:
 661         dm_bm_unlock(sblock);
 662         return r;
 663 }
 664
 665 struct dm_pool_metadata *dm_pool_metadata_open(struct block_device *bdev,
 666                                                sector_t data_block_size)
 667 {
 668         int r;
 669         struct thin_disk_superblock *disk_super;
 670         struct dm_pool_metadata *pmd;
 671         sector_t bdev_size = i_size_read(bdev->bd_inode) >> SECTOR_SHIFT;
 672         struct dm_block_manager *bm;
 673         int create;
 674         struct dm_block *sblock;
 675
 676         pmd = kmalloc(sizeof(*pmd), GFP_KERNEL);
 677         if (!pmd) {
 678                 DMERR("could not allocate metadata struct");
 679                 return ERR_PTR(-ENOMEM);
 680         }
 681
 682         bm = dm_block_manager_create(bdev, THIN_METADATA_BLOCK_SIZE,
 683                                      THIN_METADATA_CACHE_SIZE,
 684                                      THIN_MAX_CONCURRENT_LOCKS);
 685         if (!bm) {
 686                 DMERR("could not create block manager");
 687                 kfree(pmd);
 688                 return ERR_PTR(-ENOMEM);
 689         }
 690
 691         r = superblock_all_zeroes(bm, &create);
 692         if (r) {
 693                 dm_block_manager_destroy(bm);
 694                 kfree(pmd);
 695                 return ERR_PTR(r);
 696         }
 697
 698
 699         r = init_pmd(pmd, bm, 0, create);
 700         if (r) {
 701                 dm_block_manager_destroy(bm);
 702                 kfree(pmd);
 703                 return ERR_PTR(r);
 704         }
 705         pmd->bdev = bdev;
 706
 707         if (!create) {
 708                 r = __begin_transaction(pmd);
 709                 if (r < 0)
 710                         goto bad;
 711                 return pmd;
 712         }
 713
 714         /*
 715          * Create.
 716          */
 717         r = dm_bm_write_lock(pmd->bm, THIN_SUPERBLOCK_LOCATION,
 718                              &sb_validator, &sblock);
 719         if (r)
 720                 goto bad;
 721
 722         disk_super = dm_block_data(sblock);
 723         disk_super->magic = cpu_to_le64(THIN_SUPERBLOCK_MAGIC);
 724         disk_super->version = cpu_to_le32(THIN_VERSION);
 725         disk_super->time = 0;
 726         disk_super->metadata_block_size = cpu_to_le32(THIN_METADATA_BLOCK_SIZE >> SECTOR_SHIFT);
 727         disk_super->metadata_nr_blocks = cpu_to_le64(bdev_size >> SECTOR_TO_BLOCK_SHIFT);
 728         disk_super->data_block_size = cpu_to_le32(data_block_size);
 729
 730         r = dm_bm_unlock(sblock);
 731         if (r < 0)
 732                 goto bad;
 733
 734         r = dm_btree_empty(&pmd->info, &pmd->root);
 735         if (r < 0)
 736                 goto bad;
 737
 738         r = dm_btree_empty(&pmd->details_info, &pmd->details_root);
 739         if (r < 0) {
 740                 DMERR("couldn't create devices root");
 741                 goto bad;
 742         }
 743
 744         pmd->flags = 0;
 745         pmd->need_commit = 1;
 746         r = dm_pool_commit_metadata(pmd);
 747         if (r < 0) {
 748                 DMERR("%s: dm_pool_commit_metadata() failed, error = %d",
 749                       __func__, r);
 750                 goto bad;
 751         }
 752
 753         return pmd;
 754
 755 bad:
 756         if (dm_pool_metadata_close(pmd) < 0)
 757                 DMWARN("%s: dm_pool_metadata_close() failed.", __func__);
 758         return ERR_PTR(r);
 759 }
 760
 761 int dm_pool_metadata_close(struct dm_pool_metadata *pmd)
 762 {
 763         int r;
 764         unsigned open_devices = 0;
 765         struct dm_thin_device *td, *tmp;
 766
 767         down_read(&pmd->root_lock);
 768         list_for_each_entry_safe(td, tmp, &pmd->thin_devices, list) {
 769                 if (td->open_count)
 770                         open_devices++;
 771                 else {
 772                         list_del(&td->list);
 773                         kfree(td);
 774                 }
 775         }
 776         up_read(&pmd->root_lock);
 777
 778         if (open_devices) {
 779                 DMERR("attempt to close pmd when %u device(s) are still open",
 780                        open_devices);
 781                 return -EBUSY;
 782         }
 783
 784         r = __commit_transaction(pmd);
 785         if (r < 0)
 786                 DMWARN("%s: __commit_transaction() failed, error = %d",
 787                        __func__, r);
 788
 789         dm_tm_destroy(pmd->tm);
 790         dm_tm_destroy(pmd->nb_tm);
 791         dm_block_manager_destroy(pmd->bm);
 792         dm_sm_destroy(pmd->metadata_sm);
 793         dm_sm_destroy(pmd->data_sm);
 794         kfree(pmd);
 795
 796         return 0;
 797 }
 798
 799 /*
 800  * __open_device: Returns @td corresponding to device with id @dev,
 801  * creating it if @create is set and incrementing @td->open_count.
 802  * On failure, @td is undefined.
 803  */
 804 static int __open_device(struct dm_pool_metadata *pmd,
 805                          dm_thin_id dev, int create,
 806                          struct dm_thin_device **td)
 807 {
 808         int r, changed = 0;
 809         struct dm_thin_device *td2;
 810         uint64_t key = dev;
 811         struct disk_device_details details_le;
 812
 813         /*
 814          * If the device is already open, return it.
 815          */
 816         list_for_each_entry(td2, &pmd->thin_devices, list)
 817                 if (td2->id == dev) {
 818                         /*
 819                          * May not create an already-open device.
 820                          */
 821                         if (create)
 822                                 return -EEXIST;
 823
 824                         td2->open_count++;
 825                         *td = td2;
 826                         return 0;
 827                 }
 828
 829         /*
 830          * Check the device exists.
 831          */
 832         r = dm_btree_lookup(&pmd->details_info, pmd->details_root,
 833                             &key, &details_le);
 834         if (r) {
 835                 if (r != -ENODATA || !create)
 836                         return r;
 837
 838                 /*
 839                  * Create new device.
 840                  */
 841                 changed = 1;
 842                 details_le.mapped_blocks = 0;
 843                 details_le.transaction_id = cpu_to_le64(pmd->trans_id);
 844                 details_le.creation_time = cpu_to_le32(pmd->time);
 845                 details_le.snapshotted_time = cpu_to_le32(pmd->time);
 846         }
 847
 848         *td = kmalloc(sizeof(**td), GFP_NOIO);
 849         if (!*td)
 850                 return -ENOMEM;
 851
 852         (*td)->pmd = pmd;
 853         (*td)->id = dev;
 854         (*td)->open_count = 1;
 855         (*td)->changed = changed;
 856         (*td)->mapped_blocks = le64_to_cpu(details_le.mapped_blocks);
 857         (*td)->transaction_id = le64_to_cpu(details_le.transaction_id);
 858         (*td)->creation_time = le32_to_cpu(details_le.creation_time);
 859         (*td)->snapshotted_time = le32_to_cpu(details_le.snapshotted_time);
 860
 861         list_add(&(*td)->list, &pmd->thin_devices);
 862
 863         return 0;
 864 }
 865
 866 static void __close_device(struct dm_thin_device *td)
 867 {
 868         --td->open_count;
 869 }
 870
 871 static int __create_thin(struct dm_pool_metadata *pmd,
 872                          dm_thin_id dev)
 873 {
 874         int r;
 875         dm_block_t dev_root;
 876         uint64_t key = dev;
 877         struct disk_device_details details_le;
 878         struct dm_thin_device *td;
 879         __le64 value;
 880
 881         r = dm_btree_lookup(&pmd->details_info, pmd->details_root,
 882                             &key, &details_le);
 883         if (!r)
 884                 return -EEXIST;
 885
 886         /*
 887          * Create an empty btree for the mappings.
 888          */
 889         r = dm_btree_empty(&pmd->bl_info, &dev_root);
 890         if (r)
 891                 return r;
 892
 893         /*
 894          * Insert it into the main mapping tree.
 895          */
 896         value = cpu_to_le64(dev_root);
 897         __dm_bless_for_disk(&value);
 898         r = dm_btree_insert(&pmd->tl_info, pmd->root, &key, &value, &pmd->root);
 899         if (r) {
 900                 dm_btree_del(&pmd->bl_info, dev_root);
 901                 return r;
 902         }
 903
 904         r = __open_device(pmd, dev, 1, &td);
 905         if (r) {
 906                 dm_btree_remove(&pmd->tl_info, pmd->root, &key, &pmd->root);
 907                 dm_btree_del(&pmd->bl_info, dev_root);
 908                 return r;
 909         }
 910         __close_device(td);
 911
 912         return r;
 913 }
 914
 915 int dm_pool_create_thin(struct dm_pool_metadata *pmd, dm_thin_id dev)
 916 {
 917         int r;
 918
 919         down_write(&pmd->root_lock);
 920         r = __create_thin(pmd, dev);
 921         up_write(&pmd->root_lock);
 922
 923         return r;
 924 }
 925
 926 static int __set_snapshot_details(struct dm_pool_metadata *pmd,
 927                                   struct dm_thin_device *snap,
 928                                   dm_thin_id origin, uint32_t time)
 929 {
 930         int r;
 931         struct dm_thin_device *td;
 932
 933         r = __open_device(pmd, origin, 0, &td);
 934         if (r)
 935                 return r;
 936
 937         td->changed = 1;
 938         td->snapshotted_time = time;
 939
 940         snap->mapped_blocks = td->mapped_blocks;
 941         snap->snapshotted_time = time;
 942         __close_device(td);
 943
 944         return 0;
 945 }
 946
 947 static int __create_snap(struct dm_pool_metadata *pmd,
 948                          dm_thin_id dev, dm_thin_id origin)
 949 {
 950         int r;
 951         dm_block_t origin_root;
 952         uint64_t key = origin, dev_key = dev;
 953         struct dm_thin_device *td;
 954         struct disk_device_details details_le;
 955         __le64 value;
 956
 957         /* check this device is unused */
 958         r = dm_btree_lookup(&pmd->details_info, pmd->details_root,
 959                             &dev_key, &details_le);
 960         if (!r)
 961                 return -EEXIST;
 962
 963         /* find the mapping tree for the origin */
 964         r = dm_btree_lookup(&pmd->tl_info, pmd->root, &key, &value);
 965         if (r)
 966                 return r;
 967         origin_root = le64_to_cpu(value);
 968
 969         /* clone the origin, an inc will do */
 970         dm_tm_inc(pmd->tm, origin_root);
 971
 972         /* insert into the main mapping tree */
 973         value = cpu_to_le64(origin_root);
 974         __dm_bless_for_disk(&value);
 975         key = dev;
 976         r = dm_btree_insert(&pmd->tl_info, pmd->root, &key, &value, &pmd->root);
 977         if (r) {
 978                 dm_tm_dec(pmd->tm, origin_root);
 979                 return r;
 980         }
 981
 982         pmd->time++;
 983
 984         r = __open_device(pmd, dev, 1, &td);
 985         if (r)
 986                 goto bad;
 987
 988         r = __set_snapshot_details(pmd, td, origin, pmd->time);
 989         __close_device(td);
 990
 991         if (r)
 992                 goto bad;
 993
 994         return 0;
 995
 996 bad:
 997         dm_btree_remove(&pmd->tl_info, pmd->root, &key, &pmd->root);
 998         dm_btree_remove(&pmd->details_info, pmd->details_root,
 999                         &key, &pmd->details_root);
1000         return r;
1001 }
1002
1003 int dm_pool_create_snap(struct dm_pool_metadata *pmd,
1004                                  dm_thin_id dev,
1005                                  dm_thin_id origin)
1006 {
1007         int r;
1008
1009         down_write(&pmd->root_lock);
1010         r = __create_snap(pmd, dev, origin);
1011         up_write(&pmd->root_lock);
1012
1013         return r;
1014 }
1015
1016 static int __delete_device(struct dm_pool_metadata *pmd, dm_thin_id dev)
1017 {
1018         int r;
1019         uint64_t key = dev;
1020         struct dm_thin_device *td;
1021
1022         /* TODO: failure should mark the transaction invalid */
1023         r = __open_device(pmd, dev, 0, &td);
1024         if (r)
1025                 return r;
1026
1027         if (td->open_count > 1) {
1028                 __close_device(td);
1029                 return -EBUSY;
1030         }
1031
1032         list_del(&td->list);
1033         kfree(td);
1034         r = dm_btree_remove(&pmd->details_info, pmd->details_root,
1035                             &key, &pmd->details_root);
1036         if (r)
1037                 return r;
1038
1039         r = dm_btree_remove(&pmd->tl_info, pmd->root, &key, &pmd->root);
1040         if (r)
1041                 return r;
1042
1043         pmd->need_commit = 1;
1044
1045         return 0;
1046 }
1047
1048 int dm_pool_delete_thin_device(struct dm_pool_metadata *pmd,
1049                                dm_thin_id dev)
1050 {
1051         int r;
1052
1053         down_write(&pmd->root_lock);
1054         r = __delete_device(pmd, dev);
1055         up_write(&pmd->root_lock);
1056
1057         return r;
1058 }
1059
1060 int dm_pool_set_metadata_transaction_id(struct dm_pool_metadata *pmd,
1061                                         uint64_t current_id,
1062                                         uint64_t new_id)
1063 {
1064         down_write(&pmd->root_lock);
1065         if (pmd->trans_id != current_id) {
1066                 up_write(&pmd->root_lock);
1067                 DMERR("mismatched transaction id");
1068                 return -EINVAL;
1069         }
1070
1071         pmd->trans_id = new_id;
1072         pmd->need_commit = 1;
1073         up_write(&pmd->root_lock);
1074
1075         return 0;
1076 }
1077
1078 int dm_pool_get_metadata_transaction_id(struct dm_pool_metadata *pmd,
1079                                         uint64_t *result)
1080 {
1081         down_read(&pmd->root_lock);
1082         *result = pmd->trans_id;
1083         up_read(&pmd->root_lock);
1084
1085         return 0;
1086 }
1087
1088 static int __get_held_metadata_root(struct dm_pool_metadata *pmd,
1089                                     dm_block_t *result)
1090 {
1091         int r;
1092         struct thin_disk_superblock *disk_super;
1093         struct dm_block *sblock;
1094
1095         r = dm_bm_write_lock(pmd->bm, THIN_SUPERBLOCK_LOCATION,
1096                              &sb_validator, &sblock);
1097         if (r)
1098                 return r;
1099
1100         disk_super = dm_block_data(sblock);
1101         *result = le64_to_cpu(disk_super->held_root);
1102
1103         return dm_bm_unlock(sblock);
1104 }
1105
1106 int dm_pool_get_held_metadata_root(struct dm_pool_metadata *pmd,
1107                                    dm_block_t *result)
1108 {
1109         int r;
1110
1111         down_read(&pmd->root_lock);
1112         r = __get_held_metadata_root(pmd, result);
1113         up_read(&pmd->root_lock);
1114
1115         return r;
1116 }
1117
1118 int dm_pool_open_thin_device(struct dm_pool_metadata *pmd, dm_thin_id dev,
1119                              struct dm_thin_device **td)
1120 {
1121         int r;
1122
1123         down_write(&pmd->root_lock);
1124         r = __open_device(pmd, dev, 0, td);
1125         up_write(&pmd->root_lock);
1126
1127         return r;
1128 }
1129
1130 int dm_pool_close_thin_device(struct dm_thin_device *td)
1131 {
1132         down_write(&td->pmd->root_lock);
1133         __close_device(td);
1134         up_write(&td->pmd->root_lock);
1135
1136         return 0;
1137 }
1138
1139 dm_thin_id dm_thin_dev_id(struct dm_thin_device *td)
1140 {
1141         return td->id;
1142 }
1143
1144 static int __snapshotted_since(struct dm_thin_device *td, uint32_t time)
1145 {
1146         return td->snapshotted_time > time;
1147 }
1148
1149 int dm_thin_find_block(struct dm_thin_device *td, dm_block_t block,
1150                        int can_block, struct dm_thin_lookup_result *result)
1151 {
1152         int r;
1153         uint64_t block_time = 0;
1154         __le64 value;
1155         struct dm_pool_metadata *pmd = td->pmd;
1156         dm_block_t keys[2] = { td->id, block };
1157
1158         if (can_block) {
1159                 down_read(&pmd->root_lock);
1160                 r = dm_btree_lookup(&pmd->info, pmd->root, keys, &value);
1161                 if (!r)
1162                         block_time = le64_to_cpu(value);
1163                 up_read(&pmd->root_lock);
1164
1165         } else if (down_read_trylock(&pmd->root_lock)) {
1166                 r = dm_btree_lookup(&pmd->nb_info, pmd->root, keys, &value);
1167                 if (!r)
1168                         block_time = le64_to_cpu(value);
1169                 up_read(&pmd->root_lock);
1170
1171         } else
1172                 return -EWOULDBLOCK;
1173
1174         if (!r) {
1175                 dm_block_t exception_block;
1176                 uint32_t exception_time;
1177                 unpack_block_time(block_time, &exception_block,
1178                                   &exception_time);
1179                 result->block = exception_block;
1180                 result->shared = __snapshotted_since(td, exception_time);
1181         }
1182
1183         return r;
1184 }
1185
1186 static int __insert(struct dm_thin_device *td, dm_block_t block,
1187                     dm_block_t data_block)
1188 {
1189         int r, inserted;
1190         __le64 value;
1191         struct dm_pool_metadata *pmd = td->pmd;
1192         dm_block_t keys[2] = { td->id, block };
1193
1194         pmd->need_commit = 1;
1195         value = cpu_to_le64(pack_block_time(data_block, pmd->time));
1196         __dm_bless_for_disk(&value);
1197
1198         r = dm_btree_insert_notify(&pmd->info, pmd->root, keys, &value,
1199                                    &pmd->root, &inserted);
1200         if (r)
1201                 return r;
1202
1203         if (inserted) {
1204                 td->mapped_blocks++;
1205                 td->changed = 1;
1206         }
1207
1208         return 0;
1209 }
1210
1211 int dm_thin_insert_block(struct dm_thin_device *td, dm_block_t block,
1212                          dm_block_t data_block)
1213 {
1214         int r;
1215
1216         down_write(&td->pmd->root_lock);
1217         r = __insert(td, block, data_block);
1218         up_write(&td->pmd->root_lock);
1219
1220         return r;
1221 }
1222
1223 static int __remove(struct dm_thin_device *td, dm_block_t block)
1224 {
1225         int r;
1226         struct dm_pool_metadata *pmd = td->pmd;
1227         dm_block_t keys[2] = { td->id, block };
1228
1229         r = dm_btree_remove(&pmd->info, pmd->root, keys, &pmd->root);
1230         if (r)
1231                 return r;
1232
1233         td->mapped_blocks--;
1234         td->changed = 1;
1235         pmd->need_commit = 1;
1236
1237         return 0;
1238 }
1239
1240 int dm_thin_remove_block(struct dm_thin_device *td, dm_block_t block)
1241 {
1242         int r;
1243
1244         down_write(&td->pmd->root_lock);
1245         r = __remove(td, block);
1246         up_write(&td->pmd->root_lock);
1247
1248         return r;
1249 }
1250
1251 int dm_pool_alloc_data_block(struct dm_pool_metadata *pmd, dm_block_t *result)
1252 {
1253         int r;
1254
1255         down_write(&pmd->root_lock);
1256
1257         r = dm_sm_new_block(pmd->data_sm, result);
1258         pmd->need_commit = 1;
1259
1260         up_write(&pmd->root_lock);
1261
1262         return r;
1263 }
1264
1265 int dm_pool_commit_metadata(struct dm_pool_metadata *pmd)
1266 {
1267         int r;
1268
1269         down_write(&pmd->root_lock);
1270
1271         r = __commit_transaction(pmd);
1272         if (r <= 0)
1273                 goto out;
1274
1275         /*
1276          * Open the next transaction.
1277          */
1278         r = __begin_transaction(pmd);
1279 out:
1280         up_write(&pmd->root_lock);
1281         return r;
1282 }
1283
1284 int dm_pool_get_free_block_count(struct dm_pool_metadata *pmd, dm_block_t *result)
1285 {
1286         int r;
1287
1288         down_read(&pmd->root_lock);
1289         r = dm_sm_get_nr_free(pmd->data_sm, result);
1290         up_read(&pmd->root_lock);
1291
1292         return r;
1293 }
1294
1295 int dm_pool_get_free_metadata_block_count(struct dm_pool_metadata *pmd,
1296                                           dm_block_t *result)
1297 {
1298         int r;
1299
1300         down_read(&pmd->root_lock);
1301         r = dm_sm_get_nr_free(pmd->metadata_sm, result);
1302         up_read(&pmd->root_lock);
1303
1304         return r;
1305 }
1306
1307 int dm_pool_get_metadata_dev_size(struct dm_pool_metadata *pmd,
1308                                   dm_block_t *result)
1309 {
1310         int r;
1311
1312         down_read(&pmd->root_lock);
1313         r = dm_sm_get_nr_blocks(pmd->metadata_sm, result);
1314         up_read(&pmd->root_lock);
1315
1316         return r;
1317 }
1318
1319 int dm_pool_get_data_block_size(struct dm_pool_metadata *pmd, sector_t *result)
1320 {
1321         down_read(&pmd->root_lock);
1322         *result = pmd->data_block_size;
1323         up_read(&pmd->root_lock);
1324
1325         return 0;
1326 }
1327
1328 int dm_pool_get_data_dev_size(struct dm_pool_metadata *pmd, dm_block_t *result)
1329 {
1330         int r;
1331
1332         down_read(&pmd->root_lock);
1333         r = dm_sm_get_nr_blocks(pmd->data_sm, result);
1334         up_read(&pmd->root_lock);
1335
1336         return r;
1337 }
1338
1339 int dm_thin_get_mapped_count(struct dm_thin_device *td, dm_block_t *result)
1340 {
1341         struct dm_pool_metadata *pmd = td->pmd;
1342
1343         down_read(&pmd->root_lock);
1344         *result = td->mapped_blocks;
1345         up_read(&pmd->root_lock);
1346
1347         return 0;
1348 }
1349
1350 static int __highest_block(struct dm_thin_device *td, dm_block_t *result)
1351 {
1352         int r;
1353         __le64 value_le;
1354         dm_block_t thin_root;
1355         struct dm_pool_metadata *pmd = td->pmd;
1356
1357         r = dm_btree_lookup(&pmd->tl_info, pmd->root, &td->id, &value_le);
1358         if (r)
1359                 return r;
1360
1361         thin_root = le64_to_cpu(value_le);
1362
1363         return dm_btree_find_highest_key(&pmd->bl_info, thin_root, result);
1364 }
1365
1366 int dm_thin_get_highest_mapped_block(struct dm_thin_device *td,
1367                                      dm_block_t *result)
1368 {
1369         int r;
1370         struct dm_pool_metadata *pmd = td->pmd;
1371
1372         down_read(&pmd->root_lock);
1373         r = __highest_block(td, result);
1374         up_read(&pmd->root_lock);
1375
1376         return r;
1377 }
1378
1379 static int __resize_data_dev(struct dm_pool_metadata *pmd, dm_block_t new_count)
1380 {
1381         int r;
1382         dm_block_t old_count;
1383
1384         r = dm_sm_get_nr_blocks(pmd->data_sm, &old_count);
1385         if (r)
1386                 return r;
1387
1388         if (new_count == old_count)
1389                 return 0;
1390
1391         if (new_count < old_count) {
1392                 DMERR("cannot reduce size of data device");
1393                 return -EINVAL;
1394         }
1395
1396         r = dm_sm_extend(pmd->data_sm, new_count - old_count);
1397         if (!r)
1398                 pmd->need_commit = 1;
1399
1400         return r;
1401 }
1402
1403 int dm_pool_resize_data_dev(struct dm_pool_metadata *pmd, dm_block_t new_count)
1404 {
1405         int r;
1406
1407         down_write(&pmd->root_lock);
1408         r = __resize_data_dev(pmd, new_count);
1409         up_write(&pmd->root_lock);
1410
1411         return r;
1412 }