drivers/md/persistent-data/dm-space-map-disk.c

   1 /*
   2  * Copyright (C) 2011 Red Hat, Inc. All rights reserved.
   3  *
   4  * This file is released under the GPL.
   5  */
   6
   7 #include "dm-space-map-common.h"
   8 #include "dm-space-map-disk.h"
   9 #include "dm-space-map.h"
  10 #include "dm-transaction-manager.h"
  11
  12 #include <linux/list.h>
  13 #include <linux/slab.h>
  14 #include <linux/bitops.h>
  15 #include <linux/module.h>
  16 #include <linux/device-mapper.h>
  17
  18 #define DM_MSG_PREFIX "space map disk"
  19
  20 /*
  21  * Bitmap validator
  22  */
  23 static void bitmap_prepare_for_write(struct dm_block_validator *v,
  24                                      struct dm_block *b,
  25                                      size_t block_size)
  26 {
  27         struct disk_bitmap_header *disk_header = dm_block_data(b);
  28
  29         disk_header->blocknr = cpu_to_le64(dm_block_location(b));
  30         disk_header->csum = cpu_to_le32(dm_block_csum_data(&disk_header->not_used, block_size - sizeof(__le32)));
  31 }
  32
  33 static int bitmap_check(struct dm_block_validator *v,
  34                         struct dm_block *b,
  35                         size_t block_size)
  36 {
  37         struct disk_bitmap_header *disk_header = dm_block_data(b);
  38         __le32 csum_disk;
  39
  40         if (dm_block_location(b) != le64_to_cpu(disk_header->blocknr)) {
  41                 DMERR("bitmap check failed blocknr %llu wanted %llu",
  42                       le64_to_cpu(disk_header->blocknr), dm_block_location(b));
  43                 return -ENOTBLK;
  44         }
  45
  46         csum_disk = cpu_to_le32(dm_block_csum_data(&disk_header->not_used, block_size - sizeof(__le32)));
  47         if (csum_disk != disk_header->csum) {
  48                 DMERR("bitmap check failed csum %u wanted %u",
  49                       le32_to_cpu(csum_disk), le32_to_cpu(disk_header->csum));
  50                 return -EILSEQ;
  51         }
  52
  53         return 0;
  54 }
  55
  56 struct dm_block_validator dm_sm_bitmap_validator = {
  57         .name = "sm_bitmap",
  58         .prepare_for_write = bitmap_prepare_for_write,
  59         .check = bitmap_check
  60 };
  61
  62 /*----------------------------------------------------------------*/
  63
  64 #define ENTRIES_PER_WORD 32
  65 #define ENTRIES_SHIFT   5
  66
  67 void *dm_bitmap_data(struct dm_block *b)
  68 {
  69         return dm_block_data(b) + sizeof(struct disk_bitmap_header);
  70 }
  71
  72 #define WORD_MASK_LOW 0x5555555555555555ULL
  73 #define WORD_MASK_HIGH 0xAAAAAAAAAAAAAAAAULL
  74 #define WORD_MASK_ALL 0xFFFFFFFFFFFFFFFFULL
  75
  76 static unsigned bitmap_word_used(void *addr, unsigned b)
  77 {
  78         __le64 *words_le = addr;
  79         __le64 *w_le = words_le + (b >> ENTRIES_SHIFT);
  80
  81         uint64_t bits = le64_to_cpu(*w_le);
  82
  83         return ((bits & WORD_MASK_LOW) == WORD_MASK_LOW ||
  84                 (bits & WORD_MASK_HIGH) == WORD_MASK_HIGH ||
  85                 (bits & WORD_MASK_ALL) == WORD_MASK_ALL);
  86 }
  87
  88 unsigned sm_lookup_bitmap(void *addr, unsigned b)
  89 {
  90         __le64 *words_le = addr;
  91         __le64 *w_le = words_le + (b >> ENTRIES_SHIFT);
  92
  93         b = (b & (ENTRIES_PER_WORD - 1)) << 1;
  94
  95         return (!!test_bit_le(b, (void *) w_le) << 1) |
  96                 (!!test_bit_le(b + 1, (void *) w_le));
  97 }
  98
  99 void sm_set_bitmap(void *addr, unsigned b, unsigned val)
 100 {
 101         __le64 *words_le = addr;
 102         __le64 *w_le = words_le + (b >> ENTRIES_SHIFT);
 103
 104         b = (b & (ENTRIES_PER_WORD - 1)) << 1;
 105
 106         if (val & 2)
 107                 __set_bit_le(b, (void *) w_le);
 108         else
 109                 __clear_bit_le(b, (void *) w_le);
 110
 111         if (val & 1)
 112                 __set_bit_le(b + 1, (void *) w_le);
 113         else
 114                 __clear_bit_le(b + 1, (void *) w_le);
 115 }
 116
 117 int sm_find_free(void *addr, unsigned begin, unsigned end,
 118                  unsigned *result)
 119 {
 120         while (begin < end) {
 121                 if (!(begin & (ENTRIES_PER_WORD - 1)) &&
 122                     bitmap_word_used(addr, begin)) {
 123                         begin += ENTRIES_PER_WORD;
 124                         continue;
 125                 }
 126
 127                 if (!sm_lookup_bitmap(addr, begin)) {
 128                         *result = begin;
 129                         return 0;
 130                 }
 131
 132                 begin++;
 133         }
 134
 135         return -ENOSPC;
 136 }
 137
 138 static int disk_ll_init(struct ll_disk *io, struct dm_transaction_manager *tm)
 139 {
 140         io->tm = tm;
 141         io->bitmap_info.tm = tm;
 142         io->bitmap_info.levels = 1;
 143
 144         /*
 145          * Because the new bitmap blocks are created via a shadow
 146          * operation, the old entry has already had its reference count
 147          * decremented and we don't need the btree to do any bookkeeping.
 148          */
 149         io->bitmap_info.value_type.size = sizeof(struct disk_index_entry);
 150         io->bitmap_info.value_type.inc = NULL;
 151         io->bitmap_info.value_type.dec = NULL;
 152         io->bitmap_info.value_type.equal = NULL;
 153
 154         io->ref_count_info.tm = tm;
 155         io->ref_count_info.levels = 1;
 156         io->ref_count_info.value_type.size = sizeof(uint32_t);
 157         io->ref_count_info.value_type.inc = NULL;
 158         io->ref_count_info.value_type.dec = NULL;
 159         io->ref_count_info.value_type.equal = NULL;
 160
 161         io->block_size = dm_bm_block_size(dm_tm_get_bm(tm));
 162
 163         if (io->block_size > (1 << 30)) {
 164                 DMERR("block size too big to hold bitmaps");
 165                 return -EINVAL;
 166         }
 167
 168         io->entries_per_block = (io->block_size - sizeof(struct disk_bitmap_header)) *
 169                                 ENTRIES_PER_BYTE;
 170         io->nr_blocks = 0;
 171         io->bitmap_root = 0;
 172         io->ref_count_root = 0;
 173
 174         return 0;
 175 }
 176
 177 static int disk_ll_new(struct ll_disk *io, struct dm_transaction_manager *tm)
 178 {
 179         int r;
 180
 181         r = disk_ll_init(io, tm);
 182         if (r < 0)
 183                 return r;
 184
 185         io->nr_blocks = 0;
 186         io->nr_allocated = 0;
 187         r = dm_btree_create(&io->bitmap_info, &io->bitmap_root);
 188         if (r < 0)
 189                 return r;
 190
 191         r = dm_btree_create(&io->ref_count_info, &io->ref_count_root);
 192         if (r < 0) {
 193                 dm_btree_destroy(&io->bitmap_info, io->bitmap_root);
 194                 return r;
 195         }
 196
 197         return 0;
 198 }
 199
 200 static int disk_ll_extend(struct ll_disk *io, dm_block_t extra_blocks)
 201 {
 202         int r;
 203         dm_block_t i, nr_blocks;
 204         unsigned old_blocks, blocks;
 205
 206         nr_blocks = io->nr_blocks + extra_blocks;
 207         old_blocks = dm_sector_div_up(io->nr_blocks, io->entries_per_block);
 208         blocks = dm_sector_div_up(nr_blocks, io->entries_per_block);
 209
 210         for (i = old_blocks; i < blocks; i++) {
 211                 struct dm_block *b;
 212                 struct disk_index_entry idx;
 213
 214                 r = dm_tm_new_block(io->tm, &dm_sm_bitmap_validator, &b);
 215                 if (r < 0)
 216                         return r;
 217                 idx.blocknr = cpu_to_le64(dm_block_location(b));
 218
 219                 r = dm_tm_unlock(io->tm, b);
 220                 if (r < 0)
 221                         return r;
 222
 223                 idx.nr_free = cpu_to_le32(io->entries_per_block);
 224                 idx.none_free_before = 0;
 225                 __dm_bless_for_disk(&idx);
 226
 227                 r = dm_btree_insert(&io->bitmap_info, io->bitmap_root,
 228                                     &i, &idx, &io->bitmap_root);
 229                 if (r < 0)
 230                         return r;
 231         }
 232
 233         io->nr_blocks = nr_blocks;
 234         return 0;
 235 }
 236
 237 static int disk_ll_open(struct ll_disk *ll, struct dm_transaction_manager *tm,
 238                         void *root_le, size_t len)
 239 {
 240         int r;
 241         struct disk_sm_root *smr = root_le;
 242
 243         if (len < sizeof(struct disk_sm_root)) {
 244                 DMERR("sm_disk root too small");
 245                 return -ENOMEM;
 246         }
 247
 248         r = disk_ll_init(ll, tm);
 249         if (r < 0)
 250                 return r;
 251
 252         ll->nr_blocks = le64_to_cpu(smr->nr_blocks);
 253         ll->nr_allocated = le64_to_cpu(smr->nr_allocated);
 254         ll->bitmap_root = le64_to_cpu(smr->bitmap_root);
 255         ll->ref_count_root = le64_to_cpu(smr->ref_count_root);
 256
 257         return 0;
 258 }
 259
 260 static int disk_ll_lookup_bitmap(struct ll_disk *io, dm_block_t b, uint32_t *result)
 261 {
 262         int r;
 263         dm_block_t index = b;
 264         struct disk_index_entry ie_disk;
 265         struct dm_block *blk;
 266
 267         do_div(index, io->entries_per_block);
 268         r = dm_btree_lookup(&io->bitmap_info, io->bitmap_root, &index, &ie_disk);
 269         if (r < 0)
 270                 return r;
 271
 272         r = dm_tm_read_lock(io->tm, le64_to_cpu(ie_disk.blocknr), &dm_sm_bitmap_validator, &blk);
 273         if (r < 0)
 274                 return r;
 275
 276         *result = sm_lookup_bitmap(dm_bitmap_data(blk), do_div(b, io->entries_per_block));
 277
 278         return dm_tm_unlock(io->tm, blk);
 279 }
 280
 281 static int disk_ll_lookup(struct ll_disk *io, dm_block_t b, uint32_t *result)
 282 {
 283         __le32 rc_le;
 284         int r = disk_ll_lookup_bitmap(io, b, result);
 285
 286         if (r)
 287                 return r;
 288
 289         if (*result != 3)
 290                 return r;
 291
 292         r = dm_btree_lookup(&io->ref_count_info, io->ref_count_root, &b, &rc_le);
 293         if (r < 0)
 294                 return r;
 295
 296         *result = le32_to_cpu(rc_le);
 297
 298         return r;
 299 }
 300
 301 static int disk_ll_find_free_block(struct ll_disk *io, dm_block_t begin,
 302                                    dm_block_t end, dm_block_t *result)
 303 {
 304         int r;
 305         struct disk_index_entry ie_disk;
 306         dm_block_t i, index_begin = begin;
 307         dm_block_t index_end = dm_sector_div_up(end, io->entries_per_block);
 308
 309         begin = do_div(index_begin, io->entries_per_block);
 310
 311         for (i = index_begin; i < index_end; i++, begin = 0) {
 312                 struct dm_block *blk;
 313                 unsigned position;
 314                 uint32_t bit_end;
 315
 316                 r = dm_btree_lookup(&io->bitmap_info, io->bitmap_root, &i, &ie_disk);
 317                 if (r < 0)
 318                         return r;
 319
 320                 if (le32_to_cpu(ie_disk.nr_free) <= 0)
 321                         continue;
 322
 323                 r = dm_tm_read_lock(io->tm, le64_to_cpu(ie_disk.blocknr),
 324                                     &dm_sm_bitmap_validator, &blk);
 325                 if (r < 0)
 326                         return r;
 327
 328                 bit_end = (i == index_end - 1) ?
 329                         do_div(end, io->entries_per_block) : io->entries_per_block;
 330
 331                 r = sm_find_free(dm_bitmap_data(blk),
 332                                  max((unsigned)begin, (unsigned)le32_to_cpu(ie_disk.none_free_before)),
 333                                  bit_end, &position);
 334                 if (r < 0) {
 335                         dm_tm_unlock(io->tm, blk);
 336                         continue;
 337                 }
 338
 339                 r = dm_tm_unlock(io->tm, blk);
 340                 if (r < 0)
 341                         return r;
 342
 343                 *result = i * io->entries_per_block + (dm_block_t) position;
 344
 345                 return 0;
 346         }
 347
 348         return -ENOSPC;
 349 }
 350
 351 static int disk_ll_insert(struct ll_disk *io, dm_block_t b, uint32_t ref_count)
 352 {
 353         int r;
 354         uint32_t bit, old;
 355         struct dm_block *nb;
 356         dm_block_t index = b;
 357         struct disk_index_entry ie_disk;
 358         void *bm_le;
 359         int inc;
 360
 361         do_div(index, io->entries_per_block);
 362         r = dm_btree_lookup(&io->bitmap_info, io->bitmap_root, &index, &ie_disk);
 363         if (r < 0)
 364                 return r;
 365
 366         r = dm_tm_shadow_block(io->tm, le64_to_cpu(ie_disk.blocknr),
 367                                &dm_sm_bitmap_validator, &nb, &inc);
 368         if (r < 0) {
 369                 DMERR("dm_tm_shadow_block() failed");
 370                 return r;
 371         }
 372         ie_disk.blocknr = cpu_to_le64(dm_block_location(nb));
 373
 374         bm_le = dm_bitmap_data(nb);
 375         bit = do_div(b, io->entries_per_block);
 376         old = sm_lookup_bitmap(bm_le, bit);
 377
 378         if (ref_count <= 2) {
 379                 sm_set_bitmap(bm_le, bit, ref_count);
 380
 381                 if (old > 2) {
 382                         r = dm_btree_remove(&io->ref_count_info, io->ref_count_root,
 383                                             &b, &io->ref_count_root);
 384                         if (r) {
 385                                 dm_tm_unlock(io->tm, nb);
 386                                 return r;
 387                         }
 388                 }
 389         } else {
 390                 __le32 rc_le = cpu_to_le32(ref_count);
 391
 392                 __dm_bless_for_disk(&rc_le);
 393
 394                 sm_set_bitmap(bm_le, bit, 3);
 395                 r = dm_btree_insert(&io->ref_count_info, io->ref_count_root,
 396                                     &b, &rc_le, &io->ref_count_root);
 397                 if (r < 0) {
 398                         dm_tm_unlock(io->tm, nb);
 399                         DMERR("ref count insert failed");
 400                         return r;
 401                 }
 402         }
 403
 404         r = dm_tm_unlock(io->tm, nb);
 405         if (r < 0)
 406                 return r;
 407
 408         if (ref_count && !old) {
 409                 io->nr_allocated++;
 410                 ie_disk.nr_free = cpu_to_le32(le32_to_cpu(ie_disk.nr_free) - 1);
 411                 if (le32_to_cpu(ie_disk.none_free_before) == b)
 412                         ie_disk.none_free_before = cpu_to_le32(b + 1);
 413
 414         } else if (old && !ref_count) {
 415                 io->nr_allocated--;
 416                 ie_disk.nr_free = cpu_to_le32(le32_to_cpu(ie_disk.nr_free) + 1);
 417                 ie_disk.none_free_before = cpu_to_le32(min((dm_block_t) le32_to_cpu(ie_disk.none_free_before), b));
 418         }
 419
 420         __dm_bless_for_disk(&ie_disk);
 421
 422         r = dm_btree_insert(&io->bitmap_info, io->bitmap_root, &index, &ie_disk, &io->bitmap_root);
 423         if (r < 0)
 424                 return r;
 425
 426         return 0;
 427 }
 428
 429 static int disk_ll_inc(struct ll_disk *ll, dm_block_t b)
 430 {
 431         int r;
 432         uint32_t rc;
 433
 434         r = disk_ll_lookup(ll, b, &rc);
 435         if (r)
 436                 return r;
 437
 438         return disk_ll_insert(ll, b, rc + 1);
 439 }
 440
 441 static int disk_ll_dec(struct ll_disk *ll, dm_block_t b)
 442 {
 443         int r;
 444         uint32_t rc;
 445
 446         r = disk_ll_lookup(ll, b, &rc);
 447         if (r)
 448                 return r;
 449
 450         if (!rc)
 451                 return -EINVAL;
 452
 453         return disk_ll_insert(ll, b, rc - 1);
 454 }
 455
 456 /*--------------------------------------------------------------*/
 457
 458 /*
 459  * Space map interface.
 460  */
 461 struct sm_disk {
 462         struct dm_space_map sm;
 463
 464         struct ll_disk ll;
 465 };
 466
 467 static void sm_disk_destroy(struct dm_space_map *sm)
 468 {
 469         struct sm_disk *smd = container_of(sm, struct sm_disk, sm);
 470
 471         kfree(smd);
 472 }
 473
 474 static int sm_disk_extend(struct dm_space_map *sm, dm_block_t extra_blocks)
 475 {
 476         struct sm_disk *smd = container_of(sm, struct sm_disk, sm);
 477
 478         return disk_ll_extend(&smd->ll, extra_blocks);
 479 }
 480
 481 static int sm_disk_get_nr_blocks(struct dm_space_map *sm, dm_block_t *count)
 482 {
 483         struct sm_disk *smd = container_of(sm, struct sm_disk, sm);
 484
 485         *count = smd->ll.nr_blocks;
 486
 487         return 0;
 488 }
 489
 490 static int sm_disk_get_nr_free(struct dm_space_map *sm, dm_block_t *count)
 491 {
 492         struct sm_disk *smd = container_of(sm, struct sm_disk, sm);
 493
 494         *count = smd->ll.nr_blocks - smd->ll.nr_allocated;
 495
 496         return 0;
 497 }
 498
 499 static int sm_disk_get_count(struct dm_space_map *sm, dm_block_t b,
 500                              uint32_t *result)
 501 {
 502         struct sm_disk *smd = container_of(sm, struct sm_disk, sm);
 503
 504         return disk_ll_lookup(&smd->ll, b, result);
 505 }
 506
 507 static int sm_disk_count_is_more_than_one(struct dm_space_map *sm, dm_block_t b,
 508                                           int *result)
 509 {
 510         int r;
 511         uint32_t count;
 512
 513         r = sm_disk_get_count(sm, b, &count);
 514         if (r)
 515                 return r;
 516
 517         return count > 1;
 518 }
 519
 520 static int sm_disk_set_count(struct dm_space_map *sm, dm_block_t b,
 521                              uint32_t count)
 522 {
 523         struct sm_disk *smd = container_of(sm, struct sm_disk, sm);
 524
 525         return disk_ll_insert(&smd->ll, b, count);
 526 }
 527
 528 static int sm_disk_inc_block(struct dm_space_map *sm, dm_block_t b)
 529 {
 530         struct sm_disk *smd = container_of(sm, struct sm_disk, sm);
 531
 532         return disk_ll_inc(&smd->ll, b);
 533 }
 534
 535 static int sm_disk_dec_block(struct dm_space_map *sm, dm_block_t b)
 536 {
 537         struct sm_disk *smd = container_of(sm, struct sm_disk, sm);
 538
 539         return disk_ll_dec(&smd->ll, b);
 540 }
 541
 542 static int sm_disk_new_block(struct dm_space_map *sm, dm_block_t *b)
 543 {
 544         int r;
 545         struct sm_disk *smd = container_of(sm, struct sm_disk, sm);
 546
 547         /*
 548          * FIXME: We should start the search where we left off.
 549          */
 550         r = disk_ll_find_free_block(&smd->ll, 0, smd->ll.nr_blocks, b);
 551         if (r)
 552                 return r;
 553
 554         return disk_ll_inc(&smd->ll, *b);
 555 }
 556
 557 static int sm_disk_commit(struct dm_space_map *sm)
 558 {
 559         return 0;
 560 }
 561
 562 static int sm_disk_root_size(struct dm_space_map *sm, size_t *result)
 563 {
 564         *result = sizeof(struct disk_sm_root);
 565
 566         return 0;
 567 }
 568
 569 static int sm_disk_copy_root(struct dm_space_map *sm, void *where_le, size_t max)
 570 {
 571         struct sm_disk *smd = container_of(sm, struct sm_disk, sm);
 572         struct disk_sm_root root_le;
 573
 574         root_le.nr_blocks = cpu_to_le64(smd->ll.nr_blocks);
 575         root_le.nr_allocated = cpu_to_le64(smd->ll.nr_allocated);
 576         root_le.bitmap_root = cpu_to_le64(smd->ll.bitmap_root);
 577         root_le.ref_count_root = cpu_to_le64(smd->ll.ref_count_root);
 578
 579         if (max < sizeof(root_le))
 580                 return -ENOSPC;
 581
 582         memcpy(where_le, &root_le, sizeof(root_le));
 583
 584         return 0;
 585 }
 586
 587 /*----------------------------------------------------------------*/
 588
 589 static struct dm_space_map ops = {
 590         .destroy = sm_disk_destroy,
 591         .extend = sm_disk_extend,
 592         .get_nr_blocks = sm_disk_get_nr_blocks,
 593         .get_nr_free = sm_disk_get_nr_free,
 594         .get_count = sm_disk_get_count,
 595         .count_is_more_than_one = sm_disk_count_is_more_than_one,
 596         .set_count = sm_disk_set_count,
 597         .inc_block = sm_disk_inc_block,
 598         .dec_block = sm_disk_dec_block,
 599         .new_block = sm_disk_new_block,
 600         .commit = sm_disk_commit,
 601         .root_size = sm_disk_root_size,
 602         .copy_root = sm_disk_copy_root
 603 };
 604
 605 struct dm_space_map *dm_sm_disk_create(struct dm_transaction_manager *tm,
 606                                        dm_block_t nr_blocks)
 607 {
 608         int r;
 609         struct sm_disk *smd;
 610
 611         smd = kmalloc(sizeof(*smd), GFP_KERNEL);
 612         if (!smd)
 613                 return ERR_PTR(-ENOMEM);
 614
 615         memcpy(&smd->sm, &ops, sizeof(smd->sm));
 616
 617         r = disk_ll_new(&smd->ll, tm);
 618         if (r)
 619                 goto bad;
 620
 621         r = disk_ll_extend(&smd->ll, nr_blocks);
 622         if (r)
 623                 goto bad;
 624
 625         r = sm_disk_commit(&smd->sm);
 626         if (r)
 627                 goto bad;
 628
 629         return &smd->sm;
 630
 631 bad:
 632         kfree(smd);
 633         return ERR_PTR(r);
 634 }
 635 EXPORT_SYMBOL_GPL(dm_sm_disk_create);
 636
 637 struct dm_space_map *dm_sm_disk_open(struct dm_transaction_manager *tm,
 638                                      void *root_le, size_t len)
 639 {
 640         int r;
 641         struct sm_disk *smd;
 642
 643         smd = kmalloc(sizeof(*smd), GFP_KERNEL);
 644         if (!smd)
 645                 return ERR_PTR(-ENOMEM);
 646
 647         memcpy(&smd->sm, &ops, sizeof(smd->sm));
 648
 649         r = disk_ll_open(&smd->ll, tm, root_le, len);
 650         if (r)
 651                 goto bad;
 652
 653         r = sm_disk_commit(&smd->sm);
 654         if (r)
 655                 goto bad;
 656
 657         return &smd->sm;
 658
 659 bad:
 660         kfree(smd);
 661         return ERR_PTR(r);
 662 }
 663 EXPORT_SYMBOL_GPL(dm_sm_disk_open);