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