drivers/md/dm-zoned-metadata.c

   1 /*
   2  * Copyright (C) 2017 Western Digital Corporation or its affiliates.
   3  *
   4  * This file is released under the GPL.
   5  */
   6
   7 #include "dm-zoned.h"
   8
   9 #include <linux/module.h>
  10 #include <linux/crc32.h>
  11
  12 #define DM_MSG_PREFIX           "zoned metadata"
  13
  14 /*
  15  * Metadata version.
  16  */
  17 #define DMZ_META_VER    1
  18
  19 /*
  20  * On-disk super block magic.
  21  */
  22 #define DMZ_MAGIC       ((((unsigned int)('D')) << 24) | \
  23                          (((unsigned int)('Z')) << 16) | \
  24                          (((unsigned int)('B')) <<  8) | \
  25                          ((unsigned int)('D')))
  26
  27 /*
  28  * On disk super block.
  29  * This uses only 512 B but uses on disk a full 4KB block. This block is
  30  * followed on disk by the mapping table of chunks to zones and the bitmap
  31  * blocks indicating zone block validity.
  32  * The overall resulting metadata format is:
  33  *    (1) Super block (1 block)
  34  *    (2) Chunk mapping table (nr_map_blocks)
  35  *    (3) Bitmap blocks (nr_bitmap_blocks)
  36  * All metadata blocks are stored in conventional zones, starting from the
  37  * the first conventional zone found on disk.
  38  */
  39 struct dmz_super {
  40         /* Magic number */
  41         __le32          magic;                  /*   4 */
  42
  43         /* Metadata version number */
  44         __le32          version;                /*   8 */
  45
  46         /* Generation number */
  47         __le64          gen;                    /*  16 */
  48
  49         /* This block number */
  50         __le64          sb_block;               /*  24 */
  51
  52         /* The number of metadata blocks, including this super block */
  53         __le32          nr_meta_blocks;         /*  28 */
  54
  55         /* The number of sequential zones reserved for reclaim */
  56         __le32          nr_reserved_seq;        /*  32 */
  57
  58         /* The number of entries in the mapping table */
  59         __le32          nr_chunks;              /*  36 */
  60
  61         /* The number of blocks used for the chunk mapping table */
  62         __le32          nr_map_blocks;          /*  40 */
  63
  64         /* The number of blocks used for the block bitmaps */
  65         __le32          nr_bitmap_blocks;       /*  44 */
  66
  67         /* Checksum */
  68         __le32          crc;                    /*  48 */
  69
  70         /* Padding to full 512B sector */
  71         u8              reserved[464];          /* 512 */
  72 };
  73
  74 /*
  75  * Chunk mapping entry: entries are indexed by chunk number
  76  * and give the zone ID (dzone_id) mapping the chunk on disk.
  77  * This zone may be sequential or random. If it is a sequential
  78  * zone, a second zone (bzone_id) used as a write buffer may
  79  * also be specified. This second zone will always be a randomly
  80  * writeable zone.
  81  */
  82 struct dmz_map {
  83         __le32                  dzone_id;
  84         __le32                  bzone_id;
  85 };
  86
  87 /*
  88  * Chunk mapping table metadata: 512 8-bytes entries per 4KB block.
  89  */
  90 #define DMZ_MAP_ENTRIES         (DMZ_BLOCK_SIZE / sizeof(struct dmz_map))
  91 #define DMZ_MAP_ENTRIES_SHIFT   (ilog2(DMZ_MAP_ENTRIES))
  92 #define DMZ_MAP_ENTRIES_MASK    (DMZ_MAP_ENTRIES - 1)
  93 #define DMZ_MAP_UNMAPPED        UINT_MAX
  94
  95 /*
  96  * Meta data block descriptor (for cached metadata blocks).
  97  */
  98 struct dmz_mblock {
  99         struct rb_node          node;
 100         struct list_head        link;
 101         sector_t                no;
 102         atomic_t                ref;
 103         unsigned long           state;
 104         struct page             *page;
 105         void                    *data;
 106 };
 107
 108 /*
 109  * Metadata block state flags.
 110  */
 111 enum {
 112         DMZ_META_DIRTY,
 113         DMZ_META_READING,
 114         DMZ_META_WRITING,
 115         DMZ_META_ERROR,
 116 };
 117
 118 /*
 119  * Super block information (one per metadata set).
 120  */
 121 struct dmz_sb {
 122         sector_t                block;
 123         struct dmz_mblock       *mblk;
 124         struct dmz_super        *sb;
 125 };
 126
 127 /*
 128  * In-memory metadata.
 129  */
 130 struct dmz_metadata {
 131         struct dmz_dev          *dev;
 132
 133         sector_t                zone_bitmap_size;
 134         unsigned int            zone_nr_bitmap_blocks;
 135
 136         unsigned int            nr_bitmap_blocks;
 137         unsigned int            nr_map_blocks;
 138
 139         unsigned int            nr_useable_zones;
 140         unsigned int            nr_meta_blocks;
 141         unsigned int            nr_meta_zones;
 142         unsigned int            nr_data_zones;
 143         unsigned int            nr_rnd_zones;
 144         unsigned int            nr_reserved_seq;
 145         unsigned int            nr_chunks;
 146
 147         /* Zone information array */
 148         struct dm_zone          *zones;
 149
 150         struct dm_zone          *sb_zone;
 151         struct dmz_sb           sb[2];
 152         unsigned int            mblk_primary;
 153         u64                     sb_gen;
 154         unsigned int            min_nr_mblks;
 155         unsigned int            max_nr_mblks;
 156         atomic_t                nr_mblks;
 157         struct rw_semaphore     mblk_sem;
 158         struct mutex            mblk_flush_lock;
 159         spinlock_t              mblk_lock;
 160         struct rb_root          mblk_rbtree;
 161         struct list_head        mblk_lru_list;
 162         struct list_head        mblk_dirty_list;
 163         struct shrinker         mblk_shrinker;
 164
 165         /* Zone allocation management */
 166         struct mutex            map_lock;
 167         struct dmz_mblock       **map_mblk;
 168         unsigned int            nr_rnd;
 169         atomic_t                unmap_nr_rnd;
 170         struct list_head        unmap_rnd_list;
 171         struct list_head        map_rnd_list;
 172
 173         unsigned int            nr_seq;
 174         atomic_t                unmap_nr_seq;
 175         struct list_head        unmap_seq_list;
 176         struct list_head        map_seq_list;
 177
 178         atomic_t                nr_reserved_seq_zones;
 179         struct list_head        reserved_seq_zones_list;
 180
 181         wait_queue_head_t       free_wq;
 182 };
 183
 184 /*
 185  * Various accessors
 186  */
 187 unsigned int dmz_id(struct dmz_metadata *zmd, struct dm_zone *zone)
 188 {
 189         return ((unsigned int)(zone - zmd->zones));
 190 }
 191
 192 sector_t dmz_start_sect(struct dmz_metadata *zmd, struct dm_zone *zone)
 193 {
 194         return (sector_t)dmz_id(zmd, zone) << zmd->dev->zone_nr_sectors_shift;
 195 }
 196
 197 sector_t dmz_start_block(struct dmz_metadata *zmd, struct dm_zone *zone)
 198 {
 199         return (sector_t)dmz_id(zmd, zone) << zmd->dev->zone_nr_blocks_shift;
 200 }
 201
 202 unsigned int dmz_nr_chunks(struct dmz_metadata *zmd)
 203 {
 204         return zmd->nr_chunks;
 205 }
 206
 207 unsigned int dmz_nr_rnd_zones(struct dmz_metadata *zmd)
 208 {
 209         return zmd->nr_rnd;
 210 }
 211
 212 unsigned int dmz_nr_unmap_rnd_zones(struct dmz_metadata *zmd)
 213 {
 214         return atomic_read(&zmd->unmap_nr_rnd);
 215 }
 216
 217 /*
 218  * Lock/unlock mapping table.
 219  * The map lock also protects all the zone lists.
 220  */
 221 void dmz_lock_map(struct dmz_metadata *zmd)
 222 {
 223         mutex_lock(&zmd->map_lock);
 224 }
 225
 226 void dmz_unlock_map(struct dmz_metadata *zmd)
 227 {
 228         mutex_unlock(&zmd->map_lock);
 229 }
 230
 231 /*
 232  * Lock/unlock metadata access. This is a "read" lock on a semaphore
 233  * that prevents metadata flush from running while metadata are being
 234  * modified. The actual metadata write mutual exclusion is achieved with
 235  * the map lock and zone styate management (active and reclaim state are
 236  * mutually exclusive).
 237  */
 238 void dmz_lock_metadata(struct dmz_metadata *zmd)
 239 {
 240         down_read(&zmd->mblk_sem);
 241 }
 242
 243 void dmz_unlock_metadata(struct dmz_metadata *zmd)
 244 {
 245         up_read(&zmd->mblk_sem);
 246 }
 247
 248 /*
 249  * Lock/unlock flush: prevent concurrent executions
 250  * of dmz_flush_metadata as well as metadata modification in reclaim
 251  * while flush is being executed.
 252  */
 253 void dmz_lock_flush(struct dmz_metadata *zmd)
 254 {
 255         mutex_lock(&zmd->mblk_flush_lock);
 256 }
 257
 258 void dmz_unlock_flush(struct dmz_metadata *zmd)
 259 {
 260         mutex_unlock(&zmd->mblk_flush_lock);
 261 }
 262
 263 /*
 264  * Allocate a metadata block.
 265  */
 266 static struct dmz_mblock *dmz_alloc_mblock(struct dmz_metadata *zmd,
 267                                            sector_t mblk_no)
 268 {
 269         struct dmz_mblock *mblk = NULL;
 270
 271         /* See if we can reuse cached blocks */
 272         if (zmd->max_nr_mblks && atomic_read(&zmd->nr_mblks) > zmd->max_nr_mblks) {
 273                 spin_lock(&zmd->mblk_lock);
 274                 mblk = list_first_entry_or_null(&zmd->mblk_lru_list,
 275                                                 struct dmz_mblock, link);
 276                 if (mblk) {
 277                         list_del_init(&mblk->link);
 278                         rb_erase(&mblk->node, &zmd->mblk_rbtree);
 279                         mblk->no = mblk_no;
 280                 }
 281                 spin_unlock(&zmd->mblk_lock);
 282                 if (mblk)
 283                         return mblk;
 284         }
 285
 286         /* Allocate a new block */
 287         mblk = kmalloc(sizeof(struct dmz_mblock), GFP_NOIO);
 288         if (!mblk)
 289                 return NULL;
 290
 291         mblk->page = alloc_page(GFP_NOIO);
 292         if (!mblk->page) {
 293                 kfree(mblk);
 294                 return NULL;
 295         }
 296
 297         RB_CLEAR_NODE(&mblk->node);
 298         INIT_LIST_HEAD(&mblk->link);
 299         atomic_set(&mblk->ref, 0);
 300         mblk->state = 0;
 301         mblk->no = mblk_no;
 302         mblk->data = page_address(mblk->page);
 303
 304         atomic_inc(&zmd->nr_mblks);
 305
 306         return mblk;
 307 }
 308
 309 /*
 310  * Free a metadata block.
 311  */
 312 static void dmz_free_mblock(struct dmz_metadata *zmd, struct dmz_mblock *mblk)
 313 {
 314         __free_pages(mblk->page, 0);
 315         kfree(mblk);
 316
 317         atomic_dec(&zmd->nr_mblks);
 318 }
 319
 320 /*
 321  * Insert a metadata block in the rbtree.
 322  */
 323 static void dmz_insert_mblock(struct dmz_metadata *zmd, struct dmz_mblock *mblk)
 324 {
 325         struct rb_root *root = &zmd->mblk_rbtree;
 326         struct rb_node **new = &(root->rb_node), *parent = NULL;
 327         struct dmz_mblock *b;
 328
 329         /* Figure out where to put the new node */
 330         while (*new) {
 331                 b = container_of(*new, struct dmz_mblock, node);
 332                 parent = *new;
 333                 new = (b->no < mblk->no) ? &((*new)->rb_left) : &((*new)->rb_right);
 334         }
 335
 336         /* Add new node and rebalance tree */
 337         rb_link_node(&mblk->node, parent, new);
 338         rb_insert_color(&mblk->node, root);
 339 }
 340
 341 /*
 342  * Lookup a metadata block in the rbtree.
 343  */
 344 static struct dmz_mblock *dmz_lookup_mblock(struct dmz_metadata *zmd,
 345                                             sector_t mblk_no)
 346 {
 347         struct rb_root *root = &zmd->mblk_rbtree;
 348         struct rb_node *node = root->rb_node;
 349         struct dmz_mblock *mblk;
 350
 351         while (node) {
 352                 mblk = container_of(node, struct dmz_mblock, node);
 353                 if (mblk->no == mblk_no)
 354                         return mblk;
 355                 node = (mblk->no < mblk_no) ? node->rb_left : node->rb_right;
 356         }
 357
 358         return NULL;
 359 }
 360
 361 /*
 362  * Metadata block BIO end callback.
 363  */
 364 static void dmz_mblock_bio_end_io(struct bio *bio)
 365 {
 366         struct dmz_mblock *mblk = bio->bi_private;
 367         int flag;
 368
 369         if (bio->bi_status)
 370                 set_bit(DMZ_META_ERROR, &mblk->state);
 371
 372         if (bio_op(bio) == REQ_OP_WRITE)
 373                 flag = DMZ_META_WRITING;
 374         else
 375                 flag = DMZ_META_READING;
 376
 377         clear_bit_unlock(flag, &mblk->state);
 378         smp_mb__after_atomic();
 379         wake_up_bit(&mblk->state, flag);
 380
 381         bio_put(bio);
 382 }
 383
 384 /*
 385  * Read a metadata block from disk.
 386  */
 387 static struct dmz_mblock *dmz_fetch_mblock(struct dmz_metadata *zmd,
 388                                            sector_t mblk_no)
 389 {
 390         struct dmz_mblock *mblk;
 391         sector_t block = zmd->sb[zmd->mblk_primary].block + mblk_no;
 392         struct bio *bio;
 393
 394         /* Get block and insert it */
 395         mblk = dmz_alloc_mblock(zmd, mblk_no);
 396         if (!mblk)
 397                 return NULL;
 398
 399         spin_lock(&zmd->mblk_lock);
 400         atomic_inc(&mblk->ref);
 401         set_bit(DMZ_META_READING, &mblk->state);
 402         dmz_insert_mblock(zmd, mblk);
 403         spin_unlock(&zmd->mblk_lock);
 404
 405         bio = bio_alloc(GFP_NOIO, 1);
 406         if (!bio) {
 407                 dmz_free_mblock(zmd, mblk);
 408                 return NULL;
 409         }
 410
 411         bio->bi_iter.bi_sector = dmz_blk2sect(block);
 412         bio->bi_bdev = zmd->dev->bdev;
 413         bio->bi_private = mblk;
 414         bio->bi_end_io = dmz_mblock_bio_end_io;
 415         bio_set_op_attrs(bio, REQ_OP_READ, REQ_META | REQ_PRIO);
 416         bio_add_page(bio, mblk->page, DMZ_BLOCK_SIZE, 0);
 417         submit_bio(bio);
 418
 419         return mblk;
 420 }
 421
 422 /*
 423  * Free metadata blocks.
 424  */
 425 static unsigned long dmz_shrink_mblock_cache(struct dmz_metadata *zmd,
 426                                              unsigned long limit)
 427 {
 428         struct dmz_mblock *mblk;
 429         unsigned long count = 0;
 430
 431         if (!zmd->max_nr_mblks)
 432                 return 0;
 433
 434         while (!list_empty(&zmd->mblk_lru_list) &&
 435                atomic_read(&zmd->nr_mblks) > zmd->min_nr_mblks &&
 436                count < limit) {
 437                 mblk = list_first_entry(&zmd->mblk_lru_list,
 438                                         struct dmz_mblock, link);
 439                 list_del_init(&mblk->link);
 440                 rb_erase(&mblk->node, &zmd->mblk_rbtree);
 441                 dmz_free_mblock(zmd, mblk);
 442                 count++;
 443         }
 444
 445         return count;
 446 }
 447
 448 /*
 449  * For mblock shrinker: get the number of unused metadata blocks in the cache.
 450  */
 451 static unsigned long dmz_mblock_shrinker_count(struct shrinker *shrink,
 452                                                struct shrink_control *sc)
 453 {
 454         struct dmz_metadata *zmd = container_of(shrink, struct dmz_metadata, mblk_shrinker);
 455
 456         return atomic_read(&zmd->nr_mblks);
 457 }
 458
 459 /*
 460  * For mblock shrinker: scan unused metadata blocks and shrink the cache.
 461  */
 462 static unsigned long dmz_mblock_shrinker_scan(struct shrinker *shrink,
 463                                               struct shrink_control *sc)
 464 {
 465         struct dmz_metadata *zmd = container_of(shrink, struct dmz_metadata, mblk_shrinker);
 466         unsigned long count;
 467
 468         spin_lock(&zmd->mblk_lock);
 469         count = dmz_shrink_mblock_cache(zmd, sc->nr_to_scan);
 470         spin_unlock(&zmd->mblk_lock);
 471
 472         return count ? count : SHRINK_STOP;
 473 }
 474
 475 /*
 476  * Release a metadata block.
 477  */
 478 static void dmz_release_mblock(struct dmz_metadata *zmd,
 479                                struct dmz_mblock *mblk)
 480 {
 481
 482         if (!mblk)
 483                 return;
 484
 485         spin_lock(&zmd->mblk_lock);
 486
 487         if (atomic_dec_and_test(&mblk->ref)) {
 488                 if (test_bit(DMZ_META_ERROR, &mblk->state)) {
 489                         rb_erase(&mblk->node, &zmd->mblk_rbtree);
 490                         dmz_free_mblock(zmd, mblk);
 491                 } else if (!test_bit(DMZ_META_DIRTY, &mblk->state)) {
 492                         list_add_tail(&mblk->link, &zmd->mblk_lru_list);
 493                         dmz_shrink_mblock_cache(zmd, 1);
 494                 }
 495         }
 496
 497         spin_unlock(&zmd->mblk_lock);
 498 }
 499
 500 /*
 501  * Get a metadata block from the rbtree. If the block
 502  * is not present, read it from disk.
 503  */
 504 static struct dmz_mblock *dmz_get_mblock(struct dmz_metadata *zmd,
 505                                          sector_t mblk_no)
 506 {
 507         struct dmz_mblock *mblk;
 508
 509         /* Check rbtree */
 510         spin_lock(&zmd->mblk_lock);
 511         mblk = dmz_lookup_mblock(zmd, mblk_no);
 512         if (mblk) {
 513                 /* Cache hit: remove block from LRU list */
 514                 if (atomic_inc_return(&mblk->ref) == 1 &&
 515                     !test_bit(DMZ_META_DIRTY, &mblk->state))
 516                         list_del_init(&mblk->link);
 517         }
 518         spin_unlock(&zmd->mblk_lock);
 519
 520         if (!mblk) {
 521                 /* Cache miss: read the block from disk */
 522                 mblk = dmz_fetch_mblock(zmd, mblk_no);
 523                 if (!mblk)
 524                         return ERR_PTR(-ENOMEM);
 525         }
 526
 527         /* Wait for on-going read I/O and check for error */
 528         wait_on_bit_io(&mblk->state, DMZ_META_READING,
 529                        TASK_UNINTERRUPTIBLE);
 530         if (test_bit(DMZ_META_ERROR, &mblk->state)) {
 531                 dmz_release_mblock(zmd, mblk);
 532                 return ERR_PTR(-EIO);
 533         }
 534
 535         return mblk;
 536 }
 537
 538 /*
 539  * Mark a metadata block dirty.
 540  */
 541 static void dmz_dirty_mblock(struct dmz_metadata *zmd, struct dmz_mblock *mblk)
 542 {
 543         spin_lock(&zmd->mblk_lock);
 544         if (!test_and_set_bit(DMZ_META_DIRTY, &mblk->state))
 545                 list_add_tail(&mblk->link, &zmd->mblk_dirty_list);
 546         spin_unlock(&zmd->mblk_lock);
 547 }
 548
 549 /*
 550  * Issue a metadata block write BIO.
 551  */
 552 static void dmz_write_mblock(struct dmz_metadata *zmd, struct dmz_mblock *mblk,
 553                              unsigned int set)
 554 {
 555         sector_t block = zmd->sb[set].block + mblk->no;
 556         struct bio *bio;
 557
 558         bio = bio_alloc(GFP_NOIO, 1);
 559         if (!bio) {
 560                 set_bit(DMZ_META_ERROR, &mblk->state);
 561                 return;
 562         }
 563
 564         set_bit(DMZ_META_WRITING, &mblk->state);
 565
 566         bio->bi_iter.bi_sector = dmz_blk2sect(block);
 567         bio->bi_bdev = zmd->dev->bdev;
 568         bio->bi_private = mblk;
 569         bio->bi_end_io = dmz_mblock_bio_end_io;
 570         bio_set_op_attrs(bio, REQ_OP_WRITE, REQ_META | REQ_PRIO);
 571         bio_add_page(bio, mblk->page, DMZ_BLOCK_SIZE, 0);
 572         submit_bio(bio);
 573 }
 574
 575 /*
 576  * Read/write a metadata block.
 577  */
 578 static int dmz_rdwr_block(struct dmz_metadata *zmd, int op, sector_t block,
 579                           struct page *page)
 580 {
 581         struct bio *bio;
 582         int ret;
 583
 584         bio = bio_alloc(GFP_NOIO, 1);
 585         if (!bio)
 586                 return -ENOMEM;
 587
 588         bio->bi_iter.bi_sector = dmz_blk2sect(block);
 589         bio->bi_bdev = zmd->dev->bdev;
 590         bio_set_op_attrs(bio, op, REQ_SYNC | REQ_META | REQ_PRIO);
 591         bio_add_page(bio, page, DMZ_BLOCK_SIZE, 0);
 592         ret = submit_bio_wait(bio);
 593         bio_put(bio);
 594
 595         return ret;
 596 }
 597
 598 /*
 599  * Write super block of the specified metadata set.
 600  */
 601 static int dmz_write_sb(struct dmz_metadata *zmd, unsigned int set)
 602 {
 603         sector_t block = zmd->sb[set].block;
 604         struct dmz_mblock *mblk = zmd->sb[set].mblk;
 605         struct dmz_super *sb = zmd->sb[set].sb;
 606         u64 sb_gen = zmd->sb_gen + 1;
 607         int ret;
 608
 609         sb->magic = cpu_to_le32(DMZ_MAGIC);
 610         sb->version = cpu_to_le32(DMZ_META_VER);
 611
 612         sb->gen = cpu_to_le64(sb_gen);
 613
 614         sb->sb_block = cpu_to_le64(block);
 615         sb->nr_meta_blocks = cpu_to_le32(zmd->nr_meta_blocks);
 616         sb->nr_reserved_seq = cpu_to_le32(zmd->nr_reserved_seq);
 617         sb->nr_chunks = cpu_to_le32(zmd->nr_chunks);
 618
 619         sb->nr_map_blocks = cpu_to_le32(zmd->nr_map_blocks);
 620         sb->nr_bitmap_blocks = cpu_to_le32(zmd->nr_bitmap_blocks);
 621
 622         sb->crc = 0;
 623         sb->crc = cpu_to_le32(crc32_le(sb_gen, (unsigned char *)sb, DMZ_BLOCK_SIZE));
 624
 625         ret = dmz_rdwr_block(zmd, REQ_OP_WRITE, block, mblk->page);
 626         if (ret == 0)
 627                 ret = blkdev_issue_flush(zmd->dev->bdev, GFP_NOIO, NULL);
 628
 629         return ret;
 630 }
 631
 632 /*
 633  * Write dirty metadata blocks to the specified set.
 634  */
 635 static int dmz_write_dirty_mblocks(struct dmz_metadata *zmd,
 636                                    struct list_head *write_list,
 637                                    unsigned int set)
 638 {
 639         struct dmz_mblock *mblk;
 640         struct blk_plug plug;
 641         int ret = 0;
 642
 643         /* Issue writes */
 644         blk_start_plug(&plug);
 645         list_for_each_entry(mblk, write_list, link)
 646                 dmz_write_mblock(zmd, mblk, set);
 647         blk_finish_plug(&plug);
 648
 649         /* Wait for completion */
 650         list_for_each_entry(mblk, write_list, link) {
 651                 wait_on_bit_io(&mblk->state, DMZ_META_WRITING,
 652                                TASK_UNINTERRUPTIBLE);
 653                 if (test_bit(DMZ_META_ERROR, &mblk->state)) {
 654                         clear_bit(DMZ_META_ERROR, &mblk->state);
 655                         ret = -EIO;
 656                 }
 657         }
 658
 659         /* Flush drive cache (this will also sync data) */
 660         if (ret == 0)
 661                 ret = blkdev_issue_flush(zmd->dev->bdev, GFP_NOIO, NULL);
 662
 663         return ret;
 664 }
 665
 666 /*
 667  * Log dirty metadata blocks.
 668  */
 669 static int dmz_log_dirty_mblocks(struct dmz_metadata *zmd,
 670                                  struct list_head *write_list)
 671 {
 672         unsigned int log_set = zmd->mblk_primary ^ 0x1;
 673         int ret;
 674
 675         /* Write dirty blocks to the log */
 676         ret = dmz_write_dirty_mblocks(zmd, write_list, log_set);
 677         if (ret)
 678                 return ret;
 679
 680         /*
 681          * No error so far: now validate the log by updating the
 682          * log index super block generation.
 683          */
 684         ret = dmz_write_sb(zmd, log_set);
 685         if (ret)
 686                 return ret;
 687
 688         return 0;
 689 }
 690
 691 /*
 692  * Flush dirty metadata blocks.
 693  */
 694 int dmz_flush_metadata(struct dmz_metadata *zmd)
 695 {
 696         struct dmz_mblock *mblk;
 697         struct list_head write_list;
 698         int ret;
 699
 700         if (WARN_ON(!zmd))
 701                 return 0;
 702
 703         INIT_LIST_HEAD(&write_list);
 704
 705         /*
 706          * Make sure that metadata blocks are stable before logging: take
 707          * the write lock on the metadata semaphore to prevent target BIOs
 708          * from modifying metadata.
 709          */
 710         down_write(&zmd->mblk_sem);
 711
 712         /*
 713          * This is called from the target flush work and reclaim work.
 714          * Concurrent execution is not allowed.
 715          */
 716         dmz_lock_flush(zmd);
 717
 718         /* Get dirty blocks */
 719         spin_lock(&zmd->mblk_lock);
 720         list_splice_init(&zmd->mblk_dirty_list, &write_list);
 721         spin_unlock(&zmd->mblk_lock);
 722
 723         /* If there are no dirty metadata blocks, just flush the device cache */
 724         if (list_empty(&write_list)) {
 725                 ret = blkdev_issue_flush(zmd->dev->bdev, GFP_NOIO, NULL);
 726                 goto out;
 727         }
 728
 729         /*
 730          * The primary metadata set is still clean. Keep it this way until
 731          * all updates are successful in the secondary set. That is, use
 732          * the secondary set as a log.
 733          */
 734         ret = dmz_log_dirty_mblocks(zmd, &write_list);
 735         if (ret)
 736                 goto out;
 737
 738         /*
 739          * The log is on disk. It is now safe to update in place
 740          * in the primary metadata set.
 741          */
 742         ret = dmz_write_dirty_mblocks(zmd, &write_list, zmd->mblk_primary);
 743         if (ret)
 744                 goto out;
 745
 746         ret = dmz_write_sb(zmd, zmd->mblk_primary);
 747         if (ret)
 748                 goto out;
 749
 750         while (!list_empty(&write_list)) {
 751                 mblk = list_first_entry(&write_list, struct dmz_mblock, link);
 752                 list_del_init(&mblk->link);
 753
 754                 spin_lock(&zmd->mblk_lock);
 755                 clear_bit(DMZ_META_DIRTY, &mblk->state);
 756                 if (atomic_read(&mblk->ref) == 0)
 757                         list_add_tail(&mblk->link, &zmd->mblk_lru_list);
 758                 spin_unlock(&zmd->mblk_lock);
 759         }
 760
 761         zmd->sb_gen++;
 762 out:
 763         if (ret && !list_empty(&write_list)) {
 764                 spin_lock(&zmd->mblk_lock);
 765                 list_splice(&write_list, &zmd->mblk_dirty_list);
 766                 spin_unlock(&zmd->mblk_lock);
 767         }
 768
 769         dmz_unlock_flush(zmd);
 770         up_write(&zmd->mblk_sem);
 771
 772         return ret;
 773 }
 774
 775 /*
 776  * Check super block.
 777  */
 778 static int dmz_check_sb(struct dmz_metadata *zmd, struct dmz_super *sb)
 779 {
 780         unsigned int nr_meta_zones, nr_data_zones;
 781         struct dmz_dev *dev = zmd->dev;
 782         u32 crc, stored_crc;
 783         u64 gen;
 784
 785         gen = le64_to_cpu(sb->gen);
 786         stored_crc = le32_to_cpu(sb->crc);
 787         sb->crc = 0;
 788         crc = crc32_le(gen, (unsigned char *)sb, DMZ_BLOCK_SIZE);
 789         if (crc != stored_crc) {
 790                 dmz_dev_err(dev, "Invalid checksum (needed 0x%08x, got 0x%08x)",
 791                             crc, stored_crc);
 792                 return -ENXIO;
 793         }
 794
 795         if (le32_to_cpu(sb->magic) != DMZ_MAGIC) {
 796                 dmz_dev_err(dev, "Invalid meta magic (needed 0x%08x, got 0x%08x)",
 797                             DMZ_MAGIC, le32_to_cpu(sb->magic));
 798                 return -ENXIO;
 799         }
 800
 801         if (le32_to_cpu(sb->version) != DMZ_META_VER) {
 802                 dmz_dev_err(dev, "Invalid meta version (needed %d, got %d)",
 803                             DMZ_META_VER, le32_to_cpu(sb->version));
 804                 return -ENXIO;
 805         }
 806
 807         nr_meta_zones = (le32_to_cpu(sb->nr_meta_blocks) + dev->zone_nr_blocks - 1)
 808                 >> dev->zone_nr_blocks_shift;
 809         if (!nr_meta_zones ||
 810             nr_meta_zones >= zmd->nr_rnd_zones) {
 811                 dmz_dev_err(dev, "Invalid number of metadata blocks");
 812                 return -ENXIO;
 813         }
 814
 815         if (!le32_to_cpu(sb->nr_reserved_seq) ||
 816             le32_to_cpu(sb->nr_reserved_seq) >= (zmd->nr_useable_zones - nr_meta_zones)) {
 817                 dmz_dev_err(dev, "Invalid number of reserved sequential zones");
 818                 return -ENXIO;
 819         }
 820
 821         nr_data_zones = zmd->nr_useable_zones -
 822                 (nr_meta_zones * 2 + le32_to_cpu(sb->nr_reserved_seq));
 823         if (le32_to_cpu(sb->nr_chunks) > nr_data_zones) {
 824                 dmz_dev_err(dev, "Invalid number of chunks %u / %u",
 825                             le32_to_cpu(sb->nr_chunks), nr_data_zones);
 826                 return -ENXIO;
 827         }
 828
 829         /* OK */
 830         zmd->nr_meta_blocks = le32_to_cpu(sb->nr_meta_blocks);
 831         zmd->nr_reserved_seq = le32_to_cpu(sb->nr_reserved_seq);
 832         zmd->nr_chunks = le32_to_cpu(sb->nr_chunks);
 833         zmd->nr_map_blocks = le32_to_cpu(sb->nr_map_blocks);
 834         zmd->nr_bitmap_blocks = le32_to_cpu(sb->nr_bitmap_blocks);
 835         zmd->nr_meta_zones = nr_meta_zones;
 836         zmd->nr_data_zones = nr_data_zones;
 837
 838         return 0;
 839 }
 840
 841 /*
 842  * Read the first or second super block from disk.
 843  */
 844 static int dmz_read_sb(struct dmz_metadata *zmd, unsigned int set)
 845 {
 846         return dmz_rdwr_block(zmd, REQ_OP_READ, zmd->sb[set].block,
 847                               zmd->sb[set].mblk->page);
 848 }
 849
 850 /*
 851  * Determine the position of the secondary super blocks on disk.
 852  * This is used only if a corruption of the primary super block
 853  * is detected.
 854  */
 855 static int dmz_lookup_secondary_sb(struct dmz_metadata *zmd)
 856 {
 857         unsigned int zone_nr_blocks = zmd->dev->zone_nr_blocks;
 858         struct dmz_mblock *mblk;
 859         int i;
 860
 861         /* Allocate a block */
 862         mblk = dmz_alloc_mblock(zmd, 0);
 863         if (!mblk)
 864                 return -ENOMEM;
 865
 866         zmd->sb[1].mblk = mblk;
 867         zmd->sb[1].sb = mblk->data;
 868
 869         /* Bad first super block: search for the second one */
 870         zmd->sb[1].block = zmd->sb[0].block + zone_nr_blocks;
 871         for (i = 0; i < zmd->nr_rnd_zones - 1; i++) {
 872                 if (dmz_read_sb(zmd, 1) != 0)
 873                         break;
 874                 if (le32_to_cpu(zmd->sb[1].sb->magic) == DMZ_MAGIC)
 875                         return 0;
 876                 zmd->sb[1].block += zone_nr_blocks;
 877         }
 878
 879         dmz_free_mblock(zmd, mblk);
 880         zmd->sb[1].mblk = NULL;
 881
 882         return -EIO;
 883 }
 884
 885 /*
 886  * Read the first or second super block from disk.
 887  */
 888 static int dmz_get_sb(struct dmz_metadata *zmd, unsigned int set)
 889 {
 890         struct dmz_mblock *mblk;
 891         int ret;
 892
 893         /* Allocate a block */
 894         mblk = dmz_alloc_mblock(zmd, 0);
 895         if (!mblk)
 896                 return -ENOMEM;
 897
 898         zmd->sb[set].mblk = mblk;
 899         zmd->sb[set].sb = mblk->data;
 900
 901         /* Read super block */
 902         ret = dmz_read_sb(zmd, set);
 903         if (ret) {
 904                 dmz_free_mblock(zmd, mblk);
 905                 zmd->sb[set].mblk = NULL;
 906                 return ret;
 907         }
 908
 909         return 0;
 910 }
 911
 912 /*
 913  * Recover a metadata set.
 914  */
 915 static int dmz_recover_mblocks(struct dmz_metadata *zmd, unsigned int dst_set)
 916 {
 917         unsigned int src_set = dst_set ^ 0x1;
 918         struct page *page;
 919         int i, ret;
 920
 921         dmz_dev_warn(zmd->dev, "Metadata set %u invalid: recovering", dst_set);
 922
 923         if (dst_set == 0)
 924                 zmd->sb[0].block = dmz_start_block(zmd, zmd->sb_zone);
 925         else {
 926                 zmd->sb[1].block = zmd->sb[0].block +
 927                         (zmd->nr_meta_zones << zmd->dev->zone_nr_blocks_shift);
 928         }
 929
 930         page = alloc_page(GFP_NOIO);
 931         if (!page)
 932                 return -ENOMEM;
 933
 934         /* Copy metadata blocks */
 935         for (i = 1; i < zmd->nr_meta_blocks; i++) {
 936                 ret = dmz_rdwr_block(zmd, REQ_OP_READ,
 937                                      zmd->sb[src_set].block + i, page);
 938                 if (ret)
 939                         goto out;
 940                 ret = dmz_rdwr_block(zmd, REQ_OP_WRITE,
 941                                      zmd->sb[dst_set].block + i, page);
 942                 if (ret)
 943                         goto out;
 944         }
 945
 946         /* Finalize with the super block */
 947         if (!zmd->sb[dst_set].mblk) {
 948                 zmd->sb[dst_set].mblk = dmz_alloc_mblock(zmd, 0);
 949                 if (!zmd->sb[dst_set].mblk) {
 950                         ret = -ENOMEM;
 951                         goto out;
 952                 }
 953                 zmd->sb[dst_set].sb = zmd->sb[dst_set].mblk->data;
 954         }
 955
 956         ret = dmz_write_sb(zmd, dst_set);
 957 out:
 958         __free_pages(page, 0);
 959
 960         return ret;
 961 }
 962
 963 /*
 964  * Get super block from disk.
 965  */
 966 static int dmz_load_sb(struct dmz_metadata *zmd)
 967 {
 968         bool sb_good[2] = {false, false};
 969         u64 sb_gen[2] = {0, 0};
 970         int ret;
 971
 972         /* Read and check the primary super block */
 973         zmd->sb[0].block = dmz_start_block(zmd, zmd->sb_zone);
 974         ret = dmz_get_sb(zmd, 0);
 975         if (ret) {
 976                 dmz_dev_err(zmd->dev, "Read primary super block failed");
 977                 return ret;
 978         }
 979
 980         ret = dmz_check_sb(zmd, zmd->sb[0].sb);
 981
 982         /* Read and check secondary super block */
 983         if (ret == 0) {
 984                 sb_good[0] = true;
 985                 zmd->sb[1].block = zmd->sb[0].block +
 986                         (zmd->nr_meta_zones << zmd->dev->zone_nr_blocks_shift);
 987                 ret = dmz_get_sb(zmd, 1);
 988         } else
 989                 ret = dmz_lookup_secondary_sb(zmd);
 990
 991         if (ret) {
 992                 dmz_dev_err(zmd->dev, "Read secondary super block failed");
 993                 return ret;
 994         }
 995
 996         ret = dmz_check_sb(zmd, zmd->sb[1].sb);
 997         if (ret == 0)
 998                 sb_good[1] = true;
 999
1000         /* Use highest generation sb first */
1001         if (!sb_good[0] && !sb_good[1]) {
1002                 dmz_dev_err(zmd->dev, "No valid super block found");
1003                 return -EIO;
1004         }
1005
1006         if (sb_good[0])
1007                 sb_gen[0] = le64_to_cpu(zmd->sb[0].sb->gen);
1008         else
1009                 ret = dmz_recover_mblocks(zmd, 0);
1010
1011         if (sb_good[1])
1012                 sb_gen[1] = le64_to_cpu(zmd->sb[1].sb->gen);
1013         else
1014                 ret = dmz_recover_mblocks(zmd, 1);
1015
1016         if (ret) {
1017                 dmz_dev_err(zmd->dev, "Recovery failed");
1018                 return -EIO;
1019         }
1020
1021         if (sb_gen[0] >= sb_gen[1]) {
1022                 zmd->sb_gen = sb_gen[0];
1023                 zmd->mblk_primary = 0;
1024         } else {
1025                 zmd->sb_gen = sb_gen[1];
1026                 zmd->mblk_primary = 1;
1027         }
1028
1029         dmz_dev_debug(zmd->dev, "Using super block %u (gen %llu)",
1030                       zmd->mblk_primary, zmd->sb_gen);
1031
1032         return 0;
1033 }
1034
1035 /*
1036  * Initialize a zone descriptor.
1037  */
1038 static int dmz_init_zone(struct dmz_metadata *zmd, struct dm_zone *zone,
1039                          struct blk_zone *blkz)
1040 {
1041         struct dmz_dev *dev = zmd->dev;
1042
1043         /* Ignore the eventual last runt (smaller) zone */
1044         if (blkz->len != dev->zone_nr_sectors) {
1045                 if (blkz->start + blkz->len == dev->capacity)
1046                         return 0;
1047                 return -ENXIO;
1048         }
1049
1050         INIT_LIST_HEAD(&zone->link);
1051         atomic_set(&zone->refcount, 0);
1052         zone->chunk = DMZ_MAP_UNMAPPED;
1053
1054         if (blkz->type == BLK_ZONE_TYPE_CONVENTIONAL) {
1055                 set_bit(DMZ_RND, &zone->flags);
1056                 zmd->nr_rnd_zones++;
1057         } else if (blkz->type == BLK_ZONE_TYPE_SEQWRITE_REQ ||
1058                    blkz->type == BLK_ZONE_TYPE_SEQWRITE_PREF) {
1059                 set_bit(DMZ_SEQ, &zone->flags);
1060         } else
1061                 return -ENXIO;
1062
1063         if (blkz->cond == BLK_ZONE_COND_OFFLINE)
1064                 set_bit(DMZ_OFFLINE, &zone->flags);
1065         else if (blkz->cond == BLK_ZONE_COND_READONLY)
1066                 set_bit(DMZ_READ_ONLY, &zone->flags);
1067
1068         if (dmz_is_rnd(zone))
1069                 zone->wp_block = 0;
1070         else
1071                 zone->wp_block = dmz_sect2blk(blkz->wp - blkz->start);
1072
1073         if (!dmz_is_offline(zone) && !dmz_is_readonly(zone)) {
1074                 zmd->nr_useable_zones++;
1075                 if (dmz_is_rnd(zone)) {
1076                         zmd->nr_rnd_zones++;
1077                         if (!zmd->sb_zone) {
1078                                 /* Super block zone */
1079                                 zmd->sb_zone = zone;
1080                         }
1081                 }
1082         }
1083
1084         return 0;
1085 }
1086
1087 /*
1088  * Free zones descriptors.
1089  */
1090 static void dmz_drop_zones(struct dmz_metadata *zmd)
1091 {
1092         kfree(zmd->zones);
1093         zmd->zones = NULL;
1094 }
1095
1096 /*
1097  * The size of a zone report in number of zones.
1098  * This results in 4096*64B=256KB report zones commands.
1099  */
1100 #define DMZ_REPORT_NR_ZONES     4096
1101
1102 /*
1103  * Allocate and initialize zone descriptors using the zone
1104  * information from disk.
1105  */
1106 static int dmz_init_zones(struct dmz_metadata *zmd)
1107 {
1108         struct dmz_dev *dev = zmd->dev;
1109         struct dm_zone *zone;
1110         struct blk_zone *blkz;
1111         unsigned int nr_blkz;
1112         sector_t sector = 0;
1113         int i, ret = 0;
1114
1115         /* Init */
1116         zmd->zone_bitmap_size = dev->zone_nr_blocks >> 3;
1117         zmd->zone_nr_bitmap_blocks = zmd->zone_bitmap_size >> DMZ_BLOCK_SHIFT;
1118
1119         /* Allocate zone array */
1120         zmd->zones = kcalloc(dev->nr_zones, sizeof(struct dm_zone), GFP_KERNEL);
1121         if (!zmd->zones)
1122                 return -ENOMEM;
1123
1124         dmz_dev_info(dev, "Using %zu B for zone information",
1125                      sizeof(struct dm_zone) * dev->nr_zones);
1126
1127         /* Get zone information */
1128         nr_blkz = DMZ_REPORT_NR_ZONES;
1129         blkz = kcalloc(nr_blkz, sizeof(struct blk_zone), GFP_KERNEL);
1130         if (!blkz) {
1131                 ret = -ENOMEM;
1132                 goto out;
1133         }
1134
1135         /*
1136          * Get zone information and initialize zone descriptors.
1137          * At the same time, determine where the super block
1138          * should be: first block of the first randomly writable
1139          * zone.
1140          */
1141         zone = zmd->zones;
1142         while (sector < dev->capacity) {
1143                 /* Get zone information */
1144                 nr_blkz = DMZ_REPORT_NR_ZONES;
1145                 ret = blkdev_report_zones(dev->bdev, sector, blkz,
1146                                           &nr_blkz, GFP_KERNEL);
1147                 if (ret) {
1148                         dmz_dev_err(dev, "Report zones failed %d", ret);
1149                         goto out;
1150                 }
1151
1152                 /* Process report */
1153                 for (i = 0; i < nr_blkz; i++) {
1154                         ret = dmz_init_zone(zmd, zone, &blkz[i]);
1155                         if (ret)
1156                                 goto out;
1157                         sector += dev->zone_nr_sectors;
1158                         zone++;
1159                 }
1160         }
1161
1162         /* The entire zone configuration of the disk should now be known */
1163         if (sector < dev->capacity) {
1164                 dmz_dev_err(dev, "Failed to get correct zone information");
1165                 ret = -ENXIO;
1166         }
1167 out:
1168         kfree(blkz);
1169         if (ret)
1170                 dmz_drop_zones(zmd);
1171
1172         return ret;
1173 }
1174
1175 /*
1176  * Update a zone information.
1177  */
1178 static int dmz_update_zone(struct dmz_metadata *zmd, struct dm_zone *zone)
1179 {
1180         unsigned int nr_blkz = 1;
1181         struct blk_zone blkz;
1182         int ret;
1183
1184         /* Get zone information from disk */
1185         ret = blkdev_report_zones(zmd->dev->bdev, dmz_start_sect(zmd, zone),
1186                                   &blkz, &nr_blkz, GFP_NOIO);
1187         if (ret) {
1188                 dmz_dev_err(zmd->dev, "Get zone %u report failed",
1189                             dmz_id(zmd, zone));
1190                 return ret;
1191         }
1192
1193         clear_bit(DMZ_OFFLINE, &zone->flags);
1194         clear_bit(DMZ_READ_ONLY, &zone->flags);
1195         if (blkz.cond == BLK_ZONE_COND_OFFLINE)
1196                 set_bit(DMZ_OFFLINE, &zone->flags);
1197         else if (blkz.cond == BLK_ZONE_COND_READONLY)
1198                 set_bit(DMZ_READ_ONLY, &zone->flags);
1199
1200         if (dmz_is_seq(zone))
1201                 zone->wp_block = dmz_sect2blk(blkz.wp - blkz.start);
1202         else
1203                 zone->wp_block = 0;
1204
1205         return 0;
1206 }
1207
1208 /*
1209  * Check a zone write pointer position when the zone is marked
1210  * with the sequential write error flag.
1211  */
1212 static int dmz_handle_seq_write_err(struct dmz_metadata *zmd,
1213                                     struct dm_zone *zone)
1214 {
1215         unsigned int wp = 0;
1216         int ret;
1217
1218         wp = zone->wp_block;
1219         ret = dmz_update_zone(zmd, zone);
1220         if (ret)
1221                 return ret;
1222
1223         dmz_dev_warn(zmd->dev, "Processing zone %u write error (zone wp %u/%u)",
1224                      dmz_id(zmd, zone), zone->wp_block, wp);
1225
1226         if (zone->wp_block < wp) {
1227                 dmz_invalidate_blocks(zmd, zone, zone->wp_block,
1228                                       wp - zone->wp_block);
1229         }
1230
1231         return 0;
1232 }
1233
1234 static struct dm_zone *dmz_get(struct dmz_metadata *zmd, unsigned int zone_id)
1235 {
1236         return &zmd->zones[zone_id];
1237 }
1238
1239 /*
1240  * Reset a zone write pointer.
1241  */
1242 static int dmz_reset_zone(struct dmz_metadata *zmd, struct dm_zone *zone)
1243 {
1244         int ret;
1245
1246         /*
1247          * Ignore offline zones, read only zones,
1248          * and conventional zones.
1249          */
1250         if (dmz_is_offline(zone) ||
1251             dmz_is_readonly(zone) ||
1252             dmz_is_rnd(zone))
1253                 return 0;
1254
1255         if (!dmz_is_empty(zone) || dmz_seq_write_err(zone)) {
1256                 struct dmz_dev *dev = zmd->dev;
1257
1258                 ret = blkdev_reset_zones(dev->bdev,
1259                                          dmz_start_sect(zmd, zone),
1260                                          dev->zone_nr_sectors, GFP_NOIO);
1261                 if (ret) {
1262                         dmz_dev_err(dev, "Reset zone %u failed %d",
1263                                     dmz_id(zmd, zone), ret);
1264                         return ret;
1265                 }
1266         }
1267
1268         /* Clear write error bit and rewind write pointer position */
1269         clear_bit(DMZ_SEQ_WRITE_ERR, &zone->flags);
1270         zone->wp_block = 0;
1271
1272         return 0;
1273 }
1274
1275 static void dmz_get_zone_weight(struct dmz_metadata *zmd, struct dm_zone *zone);
1276
1277 /*
1278  * Initialize chunk mapping.
1279  */
1280 static int dmz_load_mapping(struct dmz_metadata *zmd)
1281 {
1282         struct dmz_dev *dev = zmd->dev;
1283         struct dm_zone *dzone, *bzone;
1284         struct dmz_mblock *dmap_mblk = NULL;
1285         struct dmz_map *dmap;
1286         unsigned int i = 0, e = 0, chunk = 0;
1287         unsigned int dzone_id;
1288         unsigned int bzone_id;
1289
1290         /* Metadata block array for the chunk mapping table */
1291         zmd->map_mblk = kcalloc(zmd->nr_map_blocks,
1292                                 sizeof(struct dmz_mblk *), GFP_KERNEL);
1293         if (!zmd->map_mblk)
1294                 return -ENOMEM;
1295
1296         /* Get chunk mapping table blocks and initialize zone mapping */
1297         while (chunk < zmd->nr_chunks) {
1298                 if (!dmap_mblk) {
1299                         /* Get mapping block */
1300                         dmap_mblk = dmz_get_mblock(zmd, i + 1);
1301                         if (IS_ERR(dmap_mblk))
1302                                 return PTR_ERR(dmap_mblk);
1303                         zmd->map_mblk[i] = dmap_mblk;
1304                         dmap = (struct dmz_map *) dmap_mblk->data;
1305                         i++;
1306                         e = 0;
1307                 }
1308
1309                 /* Check data zone */
1310                 dzone_id = le32_to_cpu(dmap[e].dzone_id);
1311                 if (dzone_id == DMZ_MAP_UNMAPPED)
1312                         goto next;
1313
1314                 if (dzone_id >= dev->nr_zones) {
1315                         dmz_dev_err(dev, "Chunk %u mapping: invalid data zone ID %u",
1316                                     chunk, dzone_id);
1317                         return -EIO;
1318                 }
1319
1320                 dzone = dmz_get(zmd, dzone_id);
1321                 set_bit(DMZ_DATA, &dzone->flags);
1322                 dzone->chunk = chunk;
1323                 dmz_get_zone_weight(zmd, dzone);
1324
1325                 if (dmz_is_rnd(dzone))
1326                         list_add_tail(&dzone->link, &zmd->map_rnd_list);
1327                 else
1328                         list_add_tail(&dzone->link, &zmd->map_seq_list);
1329
1330                 /* Check buffer zone */
1331                 bzone_id = le32_to_cpu(dmap[e].bzone_id);
1332                 if (bzone_id == DMZ_MAP_UNMAPPED)
1333                         goto next;
1334
1335                 if (bzone_id >= dev->nr_zones) {
1336                         dmz_dev_err(dev, "Chunk %u mapping: invalid buffer zone ID %u",
1337                                     chunk, bzone_id);
1338                         return -EIO;
1339                 }
1340
1341                 bzone = dmz_get(zmd, bzone_id);
1342                 if (!dmz_is_rnd(bzone)) {
1343                         dmz_dev_err(dev, "Chunk %u mapping: invalid buffer zone %u",
1344                                     chunk, bzone_id);
1345                         return -EIO;
1346                 }
1347
1348                 set_bit(DMZ_DATA, &bzone->flags);
1349                 set_bit(DMZ_BUF, &bzone->flags);
1350                 bzone->chunk = chunk;
1351                 bzone->bzone = dzone;
1352                 dzone->bzone = bzone;
1353                 dmz_get_zone_weight(zmd, bzone);
1354                 list_add_tail(&bzone->link, &zmd->map_rnd_list);
1355 next:
1356                 chunk++;
1357                 e++;
1358                 if (e >= DMZ_MAP_ENTRIES)
1359                         dmap_mblk = NULL;
1360         }
1361
1362         /*
1363          * At this point, only meta zones and mapped data zones were
1364          * fully initialized. All remaining zones are unmapped data
1365          * zones. Finish initializing those here.
1366          */
1367         for (i = 0; i < dev->nr_zones; i++) {
1368                 dzone = dmz_get(zmd, i);
1369                 if (dmz_is_meta(dzone))
1370                         continue;
1371
1372                 if (dmz_is_rnd(dzone))
1373                         zmd->nr_rnd++;
1374                 else
1375                         zmd->nr_seq++;
1376
1377                 if (dmz_is_data(dzone)) {
1378                         /* Already initialized */
1379                         continue;
1380                 }
1381
1382                 /* Unmapped data zone */
1383                 set_bit(DMZ_DATA, &dzone->flags);
1384                 dzone->chunk = DMZ_MAP_UNMAPPED;
1385                 if (dmz_is_rnd(dzone)) {
1386                         list_add_tail(&dzone->link, &zmd->unmap_rnd_list);
1387                         atomic_inc(&zmd->unmap_nr_rnd);
1388                 } else if (atomic_read(&zmd->nr_reserved_seq_zones) < zmd->nr_reserved_seq) {
1389                         list_add_tail(&dzone->link, &zmd->reserved_seq_zones_list);
1390                         atomic_inc(&zmd->nr_reserved_seq_zones);
1391                         zmd->nr_seq--;
1392                 } else {
1393                         list_add_tail(&dzone->link, &zmd->unmap_seq_list);
1394                         atomic_inc(&zmd->unmap_nr_seq);
1395                 }
1396         }
1397
1398         return 0;
1399 }
1400
1401 /*
1402  * Set a data chunk mapping.
1403  */
1404 static void dmz_set_chunk_mapping(struct dmz_metadata *zmd, unsigned int chunk,
1405                                   unsigned int dzone_id, unsigned int bzone_id)
1406 {
1407         struct dmz_mblock *dmap_mblk = zmd->map_mblk[chunk >> DMZ_MAP_ENTRIES_SHIFT];
1408         struct dmz_map *dmap = (struct dmz_map *) dmap_mblk->data;
1409         int map_idx = chunk & DMZ_MAP_ENTRIES_MASK;
1410
1411         dmap[map_idx].dzone_id = cpu_to_le32(dzone_id);
1412         dmap[map_idx].bzone_id = cpu_to_le32(bzone_id);
1413         dmz_dirty_mblock(zmd, dmap_mblk);
1414 }
1415
1416 /*
1417  * The list of mapped zones is maintained in LRU order.
1418  * This rotates a zone at the end of its map list.
1419  */
1420 static void __dmz_lru_zone(struct dmz_metadata *zmd, struct dm_zone *zone)
1421 {
1422         if (list_empty(&zone->link))
1423                 return;
1424
1425         list_del_init(&zone->link);
1426         if (dmz_is_seq(zone)) {
1427                 /* LRU rotate sequential zone */
1428                 list_add_tail(&zone->link, &zmd->map_seq_list);
1429         } else {
1430                 /* LRU rotate random zone */
1431                 list_add_tail(&zone->link, &zmd->map_rnd_list);
1432         }
1433 }
1434
1435 /*
1436  * The list of mapped random zones is maintained
1437  * in LRU order. This rotates a zone at the end of the list.
1438  */
1439 static void dmz_lru_zone(struct dmz_metadata *zmd, struct dm_zone *zone)
1440 {
1441         __dmz_lru_zone(zmd, zone);
1442         if (zone->bzone)
1443                 __dmz_lru_zone(zmd, zone->bzone);
1444 }
1445
1446 /*
1447  * Wait for any zone to be freed.
1448  */
1449 static void dmz_wait_for_free_zones(struct dmz_metadata *zmd)
1450 {
1451         DEFINE_WAIT(wait);
1452
1453         prepare_to_wait(&zmd->free_wq, &wait, TASK_UNINTERRUPTIBLE);
1454         dmz_unlock_map(zmd);
1455         dmz_unlock_metadata(zmd);
1456
1457         io_schedule_timeout(HZ);
1458
1459         dmz_lock_metadata(zmd);
1460         dmz_lock_map(zmd);
1461         finish_wait(&zmd->free_wq, &wait);
1462 }
1463
1464 /*
1465  * Lock a zone for reclaim (set the zone RECLAIM bit).
1466  * Returns false if the zone cannot be locked or if it is already locked
1467  * and 1 otherwise.
1468  */
1469 int dmz_lock_zone_reclaim(struct dm_zone *zone)
1470 {
1471         /* Active zones cannot be reclaimed */
1472         if (dmz_is_active(zone))
1473                 return 0;
1474
1475         return !test_and_set_bit(DMZ_RECLAIM, &zone->flags);
1476 }
1477
1478 /*
1479  * Clear a zone reclaim flag.
1480  */
1481 void dmz_unlock_zone_reclaim(struct dm_zone *zone)
1482 {
1483         WARN_ON(dmz_is_active(zone));
1484         WARN_ON(!dmz_in_reclaim(zone));
1485
1486         clear_bit_unlock(DMZ_RECLAIM, &zone->flags);
1487         smp_mb__after_atomic();
1488         wake_up_bit(&zone->flags, DMZ_RECLAIM);
1489 }
1490
1491 /*
1492  * Wait for a zone reclaim to complete.
1493  */
1494 static void dmz_wait_for_reclaim(struct dmz_metadata *zmd, struct dm_zone *zone)
1495 {
1496         dmz_unlock_map(zmd);
1497         dmz_unlock_metadata(zmd);
1498         wait_on_bit_timeout(&zone->flags, DMZ_RECLAIM, TASK_UNINTERRUPTIBLE, HZ);
1499         dmz_lock_metadata(zmd);
1500         dmz_lock_map(zmd);
1501 }
1502
1503 /*
1504  * Select a random write zone for reclaim.
1505  */
1506 static struct dm_zone *dmz_get_rnd_zone_for_reclaim(struct dmz_metadata *zmd)
1507 {
1508         struct dm_zone *dzone = NULL;
1509         struct dm_zone *zone;
1510
1511         if (list_empty(&zmd->map_rnd_list))
1512                 return NULL;
1513
1514         list_for_each_entry(zone, &zmd->map_rnd_list, link) {
1515                 if (dmz_is_buf(zone))
1516                         dzone = zone->bzone;
1517                 else
1518                         dzone = zone;
1519                 if (dmz_lock_zone_reclaim(dzone))
1520                         return dzone;
1521         }
1522
1523         return NULL;
1524 }
1525
1526 /*
1527  * Select a buffered sequential zone for reclaim.
1528  */
1529 static struct dm_zone *dmz_get_seq_zone_for_reclaim(struct dmz_metadata *zmd)
1530 {
1531         struct dm_zone *zone;
1532
1533         if (list_empty(&zmd->map_seq_list))
1534                 return NULL;
1535
1536         list_for_each_entry(zone, &zmd->map_seq_list, link) {
1537                 if (!zone->bzone)
1538                         continue;
1539                 if (dmz_lock_zone_reclaim(zone))
1540                         return zone;
1541         }
1542
1543         return NULL;
1544 }
1545
1546 /*
1547  * Select a zone for reclaim.
1548  */
1549 struct dm_zone *dmz_get_zone_for_reclaim(struct dmz_metadata *zmd)
1550 {
1551         struct dm_zone *zone;
1552
1553         /*
1554          * Search for a zone candidate to reclaim: 2 cases are possible.
1555          * (1) There is no free sequential zones. Then a random data zone
1556          *     cannot be reclaimed. So choose a sequential zone to reclaim so
1557          *     that afterward a random zone can be reclaimed.
1558          * (2) At least one free sequential zone is available, then choose
1559          *     the oldest random zone (data or buffer) that can be locked.
1560          */
1561         dmz_lock_map(zmd);
1562         if (list_empty(&zmd->reserved_seq_zones_list))
1563                 zone = dmz_get_seq_zone_for_reclaim(zmd);
1564         else
1565                 zone = dmz_get_rnd_zone_for_reclaim(zmd);
1566         dmz_unlock_map(zmd);
1567
1568         return zone;
1569 }
1570
1571 /*
1572  * Activate a zone (increment its reference count).
1573  */
1574 void dmz_activate_zone(struct dm_zone *zone)
1575 {
1576         set_bit(DMZ_ACTIVE, &zone->flags);
1577         atomic_inc(&zone->refcount);
1578 }
1579
1580 /*
1581  * Deactivate a zone. This decrement the zone reference counter
1582  * and clears the active state of the zone once the count reaches 0,
1583  * indicating that all BIOs to the zone have completed. Returns
1584  * true if the zone was deactivated.
1585  */
1586 void dmz_deactivate_zone(struct dm_zone *zone)
1587 {
1588         if (atomic_dec_and_test(&zone->refcount)) {
1589                 WARN_ON(!test_bit(DMZ_ACTIVE, &zone->flags));
1590                 clear_bit_unlock(DMZ_ACTIVE, &zone->flags);
1591                 smp_mb__after_atomic();
1592         }
1593 }
1594
1595 /*
1596  * Get the zone mapping a chunk, if the chunk is mapped already.
1597  * If no mapping exist and the operation is WRITE, a zone is
1598  * allocated and used to map the chunk.
1599  * The zone returned will be set to the active state.
1600  */
1601 struct dm_zone *dmz_get_chunk_mapping(struct dmz_metadata *zmd, unsigned int chunk, int op)
1602 {
1603         struct dmz_mblock *dmap_mblk = zmd->map_mblk[chunk >> DMZ_MAP_ENTRIES_SHIFT];
1604         struct dmz_map *dmap = (struct dmz_map *) dmap_mblk->data;
1605         int dmap_idx = chunk & DMZ_MAP_ENTRIES_MASK;
1606         unsigned int dzone_id;
1607         struct dm_zone *dzone = NULL;
1608         int ret = 0;
1609
1610         dmz_lock_map(zmd);
1611 again:
1612         /* Get the chunk mapping */
1613         dzone_id = le32_to_cpu(dmap[dmap_idx].dzone_id);
1614         if (dzone_id == DMZ_MAP_UNMAPPED) {
1615                 /*
1616                  * Read or discard in unmapped chunks are fine. But for
1617                  * writes, we need a mapping, so get one.
1618                  */
1619                 if (op != REQ_OP_WRITE)
1620                         goto out;
1621
1622                 /* Alloate a random zone */
1623                 dzone = dmz_alloc_zone(zmd, DMZ_ALLOC_RND);
1624                 if (!dzone) {
1625                         dmz_wait_for_free_zones(zmd);
1626                         goto again;
1627                 }
1628
1629                 dmz_map_zone(zmd, dzone, chunk);
1630
1631         } else {
1632                 /* The chunk is already mapped: get the mapping zone */
1633                 dzone = dmz_get(zmd, dzone_id);
1634                 if (dzone->chunk != chunk) {
1635                         dzone = ERR_PTR(-EIO);
1636                         goto out;
1637                 }
1638
1639                 /* Repair write pointer if the sequential dzone has error */
1640                 if (dmz_seq_write_err(dzone)) {
1641                         ret = dmz_handle_seq_write_err(zmd, dzone);
1642                         if (ret) {
1643                                 dzone = ERR_PTR(-EIO);
1644                                 goto out;
1645                         }
1646                         clear_bit(DMZ_SEQ_WRITE_ERR, &dzone->flags);
1647                 }
1648         }
1649
1650         /*
1651          * If the zone is being reclaimed, the chunk mapping may change
1652          * to a different zone. So wait for reclaim and retry. Otherwise,
1653          * activate the zone (this will prevent reclaim from touching it).
1654          */
1655         if (dmz_in_reclaim(dzone)) {
1656                 dmz_wait_for_reclaim(zmd, dzone);
1657                 goto again;
1658         }
1659         dmz_activate_zone(dzone);
1660         dmz_lru_zone(zmd, dzone);
1661 out:
1662         dmz_unlock_map(zmd);
1663
1664         return dzone;
1665 }
1666
1667 /*
1668  * Write and discard change the block validity of data zones and their buffer
1669  * zones. Check here that valid blocks are still present. If all blocks are
1670  * invalid, the zones can be unmapped on the fly without waiting for reclaim
1671  * to do it.
1672  */
1673 void dmz_put_chunk_mapping(struct dmz_metadata *zmd, struct dm_zone *dzone)
1674 {
1675         struct dm_zone *bzone;
1676
1677         dmz_lock_map(zmd);
1678
1679         bzone = dzone->bzone;
1680         if (bzone) {
1681                 if (dmz_weight(bzone))
1682                         dmz_lru_zone(zmd, bzone);
1683                 else {
1684                         /* Empty buffer zone: reclaim it */
1685                         dmz_unmap_zone(zmd, bzone);
1686                         dmz_free_zone(zmd, bzone);
1687                         bzone = NULL;
1688                 }
1689         }
1690
1691         /* Deactivate the data zone */
1692         dmz_deactivate_zone(dzone);
1693         if (dmz_is_active(dzone) || bzone || dmz_weight(dzone))
1694                 dmz_lru_zone(zmd, dzone);
1695         else {
1696                 /* Unbuffered inactive empty data zone: reclaim it */
1697                 dmz_unmap_zone(zmd, dzone);
1698                 dmz_free_zone(zmd, dzone);
1699         }
1700
1701         dmz_unlock_map(zmd);
1702 }
1703
1704 /*
1705  * Allocate and map a random zone to buffer a chunk
1706  * already mapped to a sequential zone.
1707  */
1708 struct dm_zone *dmz_get_chunk_buffer(struct dmz_metadata *zmd,
1709                                      struct dm_zone *dzone)
1710 {
1711         struct dm_zone *bzone;
1712
1713         dmz_lock_map(zmd);
1714 again:
1715         bzone = dzone->bzone;
1716         if (bzone)
1717                 goto out;
1718
1719         /* Alloate a random zone */
1720         bzone = dmz_alloc_zone(zmd, DMZ_ALLOC_RND);
1721         if (!bzone) {
1722                 dmz_wait_for_free_zones(zmd);
1723                 goto again;
1724         }
1725
1726         /* Update the chunk mapping */
1727         dmz_set_chunk_mapping(zmd, dzone->chunk, dmz_id(zmd, dzone),
1728                               dmz_id(zmd, bzone));
1729
1730         set_bit(DMZ_BUF, &bzone->flags);
1731         bzone->chunk = dzone->chunk;
1732         bzone->bzone = dzone;
1733         dzone->bzone = bzone;
1734         list_add_tail(&bzone->link, &zmd->map_rnd_list);
1735 out:
1736         dmz_unlock_map(zmd);
1737
1738         return bzone;
1739 }
1740
1741 /*
1742  * Get an unmapped (free) zone.
1743  * This must be called with the mapping lock held.
1744  */
1745 struct dm_zone *dmz_alloc_zone(struct dmz_metadata *zmd, unsigned long flags)
1746 {
1747         struct list_head *list;
1748         struct dm_zone *zone;
1749
1750         if (flags & DMZ_ALLOC_RND)
1751                 list = &zmd->unmap_rnd_list;
1752         else
1753                 list = &zmd->unmap_seq_list;
1754 again:
1755         if (list_empty(list)) {
1756                 /*
1757                  * No free zone: if this is for reclaim, allow using the
1758                  * reserved sequential zones.
1759                  */
1760                 if (!(flags & DMZ_ALLOC_RECLAIM) ||
1761                     list_empty(&zmd->reserved_seq_zones_list))
1762                         return NULL;
1763
1764                 zone = list_first_entry(&zmd->reserved_seq_zones_list,
1765                                         struct dm_zone, link);
1766                 list_del_init(&zone->link);
1767                 atomic_dec(&zmd->nr_reserved_seq_zones);
1768                 return zone;
1769         }
1770
1771         zone = list_first_entry(list, struct dm_zone, link);
1772         list_del_init(&zone->link);
1773
1774         if (dmz_is_rnd(zone))
1775                 atomic_dec(&zmd->unmap_nr_rnd);
1776         else
1777                 atomic_dec(&zmd->unmap_nr_seq);
1778
1779         if (dmz_is_offline(zone)) {
1780                 dmz_dev_warn(zmd->dev, "Zone %u is offline", dmz_id(zmd, zone));
1781                 zone = NULL;
1782                 goto again;
1783         }
1784
1785         return zone;
1786 }
1787
1788 /*
1789  * Free a zone.
1790  * This must be called with the mapping lock held.
1791  */
1792 void dmz_free_zone(struct dmz_metadata *zmd, struct dm_zone *zone)
1793 {
1794         /* If this is a sequential zone, reset it */
1795         if (dmz_is_seq(zone))
1796                 dmz_reset_zone(zmd, zone);
1797
1798         /* Return the zone to its type unmap list */
1799         if (dmz_is_rnd(zone)) {
1800                 list_add_tail(&zone->link, &zmd->unmap_rnd_list);
1801                 atomic_inc(&zmd->unmap_nr_rnd);
1802         } else if (atomic_read(&zmd->nr_reserved_seq_zones) <
1803                    zmd->nr_reserved_seq) {
1804                 list_add_tail(&zone->link, &zmd->reserved_seq_zones_list);
1805                 atomic_inc(&zmd->nr_reserved_seq_zones);
1806         } else {
1807                 list_add_tail(&zone->link, &zmd->unmap_seq_list);
1808                 atomic_inc(&zmd->unmap_nr_seq);
1809         }
1810
1811         wake_up_all(&zmd->free_wq);
1812 }
1813
1814 /*
1815  * Map a chunk to a zone.
1816  * This must be called with the mapping lock held.
1817  */
1818 void dmz_map_zone(struct dmz_metadata *zmd, struct dm_zone *dzone,
1819                   unsigned int chunk)
1820 {
1821         /* Set the chunk mapping */
1822         dmz_set_chunk_mapping(zmd, chunk, dmz_id(zmd, dzone),
1823                               DMZ_MAP_UNMAPPED);
1824         dzone->chunk = chunk;
1825         if (dmz_is_rnd(dzone))
1826                 list_add_tail(&dzone->link, &zmd->map_rnd_list);
1827         else
1828                 list_add_tail(&dzone->link, &zmd->map_seq_list);
1829 }
1830
1831 /*
1832  * Unmap a zone.
1833  * This must be called with the mapping lock held.
1834  */
1835 void dmz_unmap_zone(struct dmz_metadata *zmd, struct dm_zone *zone)
1836 {
1837         unsigned int chunk = zone->chunk;
1838         unsigned int dzone_id;
1839
1840         if (chunk == DMZ_MAP_UNMAPPED) {
1841                 /* Already unmapped */
1842                 return;
1843         }
1844
1845         if (test_and_clear_bit(DMZ_BUF, &zone->flags)) {
1846                 /*
1847                  * Unmapping the chunk buffer zone: clear only
1848                  * the chunk buffer mapping
1849                  */
1850                 dzone_id = dmz_id(zmd, zone->bzone);
1851                 zone->bzone->bzone = NULL;
1852                 zone->bzone = NULL;
1853
1854         } else {
1855                 /*
1856                  * Unmapping the chunk data zone: the zone must
1857                  * not be buffered.
1858                  */
1859                 if (WARN_ON(zone->bzone)) {
1860                         zone->bzone->bzone = NULL;
1861                         zone->bzone = NULL;
1862                 }
1863                 dzone_id = DMZ_MAP_UNMAPPED;
1864         }
1865
1866         dmz_set_chunk_mapping(zmd, chunk, dzone_id, DMZ_MAP_UNMAPPED);
1867
1868         zone->chunk = DMZ_MAP_UNMAPPED;
1869         list_del_init(&zone->link);
1870 }
1871
1872 /*
1873  * Set @nr_bits bits in @bitmap starting from @bit.
1874  * Return the number of bits changed from 0 to 1.
1875  */
1876 static unsigned int dmz_set_bits(unsigned long *bitmap,
1877                                  unsigned int bit, unsigned int nr_bits)
1878 {
1879         unsigned long *addr;
1880         unsigned int end = bit + nr_bits;
1881         unsigned int n = 0;
1882
1883         while (bit < end) {
1884                 if (((bit & (BITS_PER_LONG - 1)) == 0) &&
1885                     ((end - bit) >= BITS_PER_LONG)) {
1886                         /* Try to set the whole word at once */
1887                         addr = bitmap + BIT_WORD(bit);
1888                         if (*addr == 0) {
1889                                 *addr = ULONG_MAX;
1890                                 n += BITS_PER_LONG;
1891                                 bit += BITS_PER_LONG;
1892                                 continue;
1893                         }
1894                 }
1895
1896                 if (!test_and_set_bit(bit, bitmap))
1897                         n++;
1898                 bit++;
1899         }
1900
1901         return n;
1902 }
1903
1904 /*
1905  * Get the bitmap block storing the bit for chunk_block in zone.
1906  */
1907 static struct dmz_mblock *dmz_get_bitmap(struct dmz_metadata *zmd,
1908                                          struct dm_zone *zone,
1909                                          sector_t chunk_block)
1910 {
1911         sector_t bitmap_block = 1 + zmd->nr_map_blocks +
1912                 (sector_t)(dmz_id(zmd, zone) * zmd->zone_nr_bitmap_blocks) +
1913                 (chunk_block >> DMZ_BLOCK_SHIFT_BITS);
1914
1915         return dmz_get_mblock(zmd, bitmap_block);
1916 }
1917
1918 /*
1919  * Copy the valid blocks bitmap of from_zone to the bitmap of to_zone.
1920  */
1921 int dmz_copy_valid_blocks(struct dmz_metadata *zmd, struct dm_zone *from_zone,
1922                           struct dm_zone *to_zone)
1923 {
1924         struct dmz_mblock *from_mblk, *to_mblk;
1925         sector_t chunk_block = 0;
1926
1927         /* Get the zones bitmap blocks */
1928         while (chunk_block < zmd->dev->zone_nr_blocks) {
1929                 from_mblk = dmz_get_bitmap(zmd, from_zone, chunk_block);
1930                 if (IS_ERR(from_mblk))
1931                         return PTR_ERR(from_mblk);
1932                 to_mblk = dmz_get_bitmap(zmd, to_zone, chunk_block);
1933                 if (IS_ERR(to_mblk)) {
1934                         dmz_release_mblock(zmd, from_mblk);
1935                         return PTR_ERR(to_mblk);
1936                 }
1937
1938                 memcpy(to_mblk->data, from_mblk->data, DMZ_BLOCK_SIZE);
1939                 dmz_dirty_mblock(zmd, to_mblk);
1940
1941                 dmz_release_mblock(zmd, to_mblk);
1942                 dmz_release_mblock(zmd, from_mblk);
1943
1944                 chunk_block += DMZ_BLOCK_SIZE_BITS;
1945         }
1946
1947         to_zone->weight = from_zone->weight;
1948
1949         return 0;
1950 }
1951
1952 /*
1953  * Merge the valid blocks bitmap of from_zone into the bitmap of to_zone,
1954  * starting from chunk_block.
1955  */
1956 int dmz_merge_valid_blocks(struct dmz_metadata *zmd, struct dm_zone *from_zone,
1957                            struct dm_zone *to_zone, sector_t chunk_block)
1958 {
1959         unsigned int nr_blocks;
1960         int ret;
1961
1962         /* Get the zones bitmap blocks */
1963         while (chunk_block < zmd->dev->zone_nr_blocks) {
1964                 /* Get a valid region from the source zone */
1965                 ret = dmz_first_valid_block(zmd, from_zone, &chunk_block);
1966                 if (ret <= 0)
1967                         return ret;
1968
1969                 nr_blocks = ret;
1970                 ret = dmz_validate_blocks(zmd, to_zone, chunk_block, nr_blocks);
1971                 if (ret)
1972                         return ret;
1973
1974                 chunk_block += nr_blocks;
1975         }
1976
1977         return 0;
1978 }
1979
1980 /*
1981  * Validate all the blocks in the range [block..block+nr_blocks-1].
1982  */
1983 int dmz_validate_blocks(struct dmz_metadata *zmd, struct dm_zone *zone,
1984                         sector_t chunk_block, unsigned int nr_blocks)
1985 {
1986         unsigned int count, bit, nr_bits;
1987         unsigned int zone_nr_blocks = zmd->dev->zone_nr_blocks;
1988         struct dmz_mblock *mblk;
1989         unsigned int n = 0;
1990
1991         dmz_dev_debug(zmd->dev, "=> VALIDATE zone %u, block %llu, %u blocks",
1992                       dmz_id(zmd, zone), (unsigned long long)chunk_block,
1993                       nr_blocks);
1994
1995         WARN_ON(chunk_block + nr_blocks > zone_nr_blocks);
1996
1997         while (nr_blocks) {
1998                 /* Get bitmap block */
1999                 mblk = dmz_get_bitmap(zmd, zone, chunk_block);
2000                 if (IS_ERR(mblk))
2001                         return PTR_ERR(mblk);
2002
2003                 /* Set bits */
2004                 bit = chunk_block & DMZ_BLOCK_MASK_BITS;
2005                 nr_bits = min(nr_blocks, DMZ_BLOCK_SIZE_BITS - bit);
2006
2007                 count = dmz_set_bits((unsigned long *)mblk->data, bit, nr_bits);
2008                 if (count) {
2009                         dmz_dirty_mblock(zmd, mblk);
2010                         n += count;
2011                 }
2012                 dmz_release_mblock(zmd, mblk);
2013
2014                 nr_blocks -= nr_bits;
2015                 chunk_block += nr_bits;
2016         }
2017
2018         if (likely(zone->weight + n <= zone_nr_blocks))
2019                 zone->weight += n;
2020         else {
2021                 dmz_dev_warn(zmd->dev, "Zone %u: weight %u should be <= %u",
2022                              dmz_id(zmd, zone), zone->weight,
2023                              zone_nr_blocks - n);
2024                 zone->weight = zone_nr_blocks;
2025         }
2026
2027         return 0;
2028 }
2029
2030 /*
2031  * Clear nr_bits bits in bitmap starting from bit.
2032  * Return the number of bits cleared.
2033  */
2034 static int dmz_clear_bits(unsigned long *bitmap, int bit, int nr_bits)
2035 {
2036         unsigned long *addr;
2037         int end = bit + nr_bits;
2038         int n = 0;
2039
2040         while (bit < end) {
2041                 if (((bit & (BITS_PER_LONG - 1)) == 0) &&
2042                     ((end - bit) >= BITS_PER_LONG)) {
2043                         /* Try to clear whole word at once */
2044                         addr = bitmap + BIT_WORD(bit);
2045                         if (*addr == ULONG_MAX) {
2046                                 *addr = 0;
2047                                 n += BITS_PER_LONG;
2048                                 bit += BITS_PER_LONG;
2049                                 continue;
2050                         }
2051                 }
2052
2053                 if (test_and_clear_bit(bit, bitmap))
2054                         n++;
2055                 bit++;
2056         }
2057
2058         return n;
2059 }
2060
2061 /*
2062  * Invalidate all the blocks in the range [block..block+nr_blocks-1].
2063  */
2064 int dmz_invalidate_blocks(struct dmz_metadata *zmd, struct dm_zone *zone,
2065                           sector_t chunk_block, unsigned int nr_blocks)
2066 {
2067         unsigned int count, bit, nr_bits;
2068         struct dmz_mblock *mblk;
2069         unsigned int n = 0;
2070
2071         dmz_dev_debug(zmd->dev, "=> INVALIDATE zone %u, block %llu, %u blocks",
2072                       dmz_id(zmd, zone), (u64)chunk_block, nr_blocks);
2073
2074         WARN_ON(chunk_block + nr_blocks > zmd->dev->zone_nr_blocks);
2075
2076         while (nr_blocks) {
2077                 /* Get bitmap block */
2078                 mblk = dmz_get_bitmap(zmd, zone, chunk_block);
2079                 if (IS_ERR(mblk))
2080                         return PTR_ERR(mblk);
2081
2082                 /* Clear bits */
2083                 bit = chunk_block & DMZ_BLOCK_MASK_BITS;
2084                 nr_bits = min(nr_blocks, DMZ_BLOCK_SIZE_BITS - bit);
2085
2086                 count = dmz_clear_bits((unsigned long *)mblk->data,
2087                                        bit, nr_bits);
2088                 if (count) {
2089                         dmz_dirty_mblock(zmd, mblk);
2090                         n += count;
2091                 }
2092                 dmz_release_mblock(zmd, mblk);
2093
2094                 nr_blocks -= nr_bits;
2095                 chunk_block += nr_bits;
2096         }
2097
2098         if (zone->weight >= n)
2099                 zone->weight -= n;
2100         else {
2101                 dmz_dev_warn(zmd->dev, "Zone %u: weight %u should be >= %u",
2102                              dmz_id(zmd, zone), zone->weight, n);
2103                 zone->weight = 0;
2104         }
2105
2106         return 0;
2107 }
2108
2109 /*
2110  * Get a block bit value.
2111  */
2112 static int dmz_test_block(struct dmz_metadata *zmd, struct dm_zone *zone,
2113                           sector_t chunk_block)
2114 {
2115         struct dmz_mblock *mblk;
2116         int ret;
2117
2118         WARN_ON(chunk_block >= zmd->dev->zone_nr_blocks);
2119
2120         /* Get bitmap block */
2121         mblk = dmz_get_bitmap(zmd, zone, chunk_block);
2122         if (IS_ERR(mblk))
2123                 return PTR_ERR(mblk);
2124
2125         /* Get offset */
2126         ret = test_bit(chunk_block & DMZ_BLOCK_MASK_BITS,
2127                        (unsigned long *) mblk->data) != 0;
2128
2129         dmz_release_mblock(zmd, mblk);
2130
2131         return ret;
2132 }
2133
2134 /*
2135  * Return the number of blocks from chunk_block to the first block with a bit
2136  * value specified by set. Search at most nr_blocks blocks from chunk_block.
2137  */
2138 static int dmz_to_next_set_block(struct dmz_metadata *zmd, struct dm_zone *zone,
2139                                  sector_t chunk_block, unsigned int nr_blocks,
2140                                  int set)
2141 {
2142         struct dmz_mblock *mblk;
2143         unsigned int bit, set_bit, nr_bits;
2144         unsigned long *bitmap;
2145         int n = 0;
2146
2147         WARN_ON(chunk_block + nr_blocks > zmd->dev->zone_nr_blocks);
2148
2149         while (nr_blocks) {
2150                 /* Get bitmap block */
2151                 mblk = dmz_get_bitmap(zmd, zone, chunk_block);
2152                 if (IS_ERR(mblk))
2153                         return PTR_ERR(mblk);
2154
2155                 /* Get offset */
2156                 bitmap = (unsigned long *) mblk->data;
2157                 bit = chunk_block & DMZ_BLOCK_MASK_BITS;
2158                 nr_bits = min(nr_blocks, DMZ_BLOCK_SIZE_BITS - bit);
2159                 if (set)
2160                         set_bit = find_next_bit(bitmap, DMZ_BLOCK_SIZE_BITS, bit);
2161                 else
2162                         set_bit = find_next_zero_bit(bitmap, DMZ_BLOCK_SIZE_BITS, bit);
2163                 dmz_release_mblock(zmd, mblk);
2164
2165                 n += set_bit - bit;
2166                 if (set_bit < DMZ_BLOCK_SIZE_BITS)
2167                         break;
2168
2169                 nr_blocks -= nr_bits;
2170                 chunk_block += nr_bits;
2171         }
2172
2173         return n;
2174 }
2175
2176 /*
2177  * Test if chunk_block is valid. If it is, the number of consecutive
2178  * valid blocks from chunk_block will be returned.
2179  */
2180 int dmz_block_valid(struct dmz_metadata *zmd, struct dm_zone *zone,
2181                     sector_t chunk_block)
2182 {
2183         int valid;
2184
2185         valid = dmz_test_block(zmd, zone, chunk_block);
2186         if (valid <= 0)
2187                 return valid;
2188
2189         /* The block is valid: get the number of valid blocks from block */
2190         return dmz_to_next_set_block(zmd, zone, chunk_block,
2191                                      zmd->dev->zone_nr_blocks - chunk_block, 0);
2192 }
2193
2194 /*
2195  * Find the first valid block from @chunk_block in @zone.
2196  * If such a block is found, its number is returned using
2197  * @chunk_block and the total number of valid blocks from @chunk_block
2198  * is returned.
2199  */
2200 int dmz_first_valid_block(struct dmz_metadata *zmd, struct dm_zone *zone,
2201                           sector_t *chunk_block)
2202 {
2203         sector_t start_block = *chunk_block;
2204         int ret;
2205
2206         ret = dmz_to_next_set_block(zmd, zone, start_block,
2207                                     zmd->dev->zone_nr_blocks - start_block, 1);
2208         if (ret < 0)
2209                 return ret;
2210
2211         start_block += ret;
2212         *chunk_block = start_block;
2213
2214         return dmz_to_next_set_block(zmd, zone, start_block,
2215                                      zmd->dev->zone_nr_blocks - start_block, 0);
2216 }
2217
2218 /*
2219  * Count the number of bits set starting from bit up to bit + nr_bits - 1.
2220  */
2221 static int dmz_count_bits(void *bitmap, int bit, int nr_bits)
2222 {
2223         unsigned long *addr;
2224         int end = bit + nr_bits;
2225         int n = 0;
2226
2227         while (bit < end) {
2228                 if (((bit & (BITS_PER_LONG - 1)) == 0) &&
2229                     ((end - bit) >= BITS_PER_LONG)) {
2230                         addr = (unsigned long *)bitmap + BIT_WORD(bit);
2231                         if (*addr == ULONG_MAX) {
2232                                 n += BITS_PER_LONG;
2233                                 bit += BITS_PER_LONG;
2234                                 continue;
2235                         }
2236                 }
2237
2238                 if (test_bit(bit, bitmap))
2239                         n++;
2240                 bit++;
2241         }
2242
2243         return n;
2244 }
2245
2246 /*
2247  * Get a zone weight.
2248  */
2249 static void dmz_get_zone_weight(struct dmz_metadata *zmd, struct dm_zone *zone)
2250 {
2251         struct dmz_mblock *mblk;
2252         sector_t chunk_block = 0;
2253         unsigned int bit, nr_bits;
2254         unsigned int nr_blocks = zmd->dev->zone_nr_blocks;
2255         void *bitmap;
2256         int n = 0;
2257
2258         while (nr_blocks) {
2259                 /* Get bitmap block */
2260                 mblk = dmz_get_bitmap(zmd, zone, chunk_block);
2261                 if (IS_ERR(mblk)) {
2262                         n = 0;
2263                         break;
2264                 }
2265
2266                 /* Count bits in this block */
2267                 bitmap = mblk->data;
2268                 bit = chunk_block & DMZ_BLOCK_MASK_BITS;
2269                 nr_bits = min(nr_blocks, DMZ_BLOCK_SIZE_BITS - bit);
2270                 n += dmz_count_bits(bitmap, bit, nr_bits);
2271
2272                 dmz_release_mblock(zmd, mblk);
2273
2274                 nr_blocks -= nr_bits;
2275                 chunk_block += nr_bits;
2276         }
2277
2278         zone->weight = n;
2279 }
2280
2281 /*
2282  * Cleanup the zoned metadata resources.
2283  */
2284 static void dmz_cleanup_metadata(struct dmz_metadata *zmd)
2285 {
2286         struct rb_root *root;
2287         struct dmz_mblock *mblk, *next;
2288         int i;
2289
2290         /* Release zone mapping resources */
2291         if (zmd->map_mblk) {
2292                 for (i = 0; i < zmd->nr_map_blocks; i++)
2293                         dmz_release_mblock(zmd, zmd->map_mblk[i]);
2294                 kfree(zmd->map_mblk);
2295                 zmd->map_mblk = NULL;
2296         }
2297
2298         /* Release super blocks */
2299         for (i = 0; i < 2; i++) {
2300                 if (zmd->sb[i].mblk) {
2301                         dmz_free_mblock(zmd, zmd->sb[i].mblk);
2302                         zmd->sb[i].mblk = NULL;
2303                 }
2304         }
2305
2306         /* Free cached blocks */
2307         while (!list_empty(&zmd->mblk_dirty_list)) {
2308                 mblk = list_first_entry(&zmd->mblk_dirty_list,
2309                                         struct dmz_mblock, link);
2310                 dmz_dev_warn(zmd->dev, "mblock %llu still in dirty list (ref %u)",
2311                              (u64)mblk->no, atomic_read(&mblk->ref));
2312                 list_del_init(&mblk->link);
2313                 rb_erase(&mblk->node, &zmd->mblk_rbtree);
2314                 dmz_free_mblock(zmd, mblk);
2315         }
2316
2317         while (!list_empty(&zmd->mblk_lru_list)) {
2318                 mblk = list_first_entry(&zmd->mblk_lru_list,
2319                                         struct dmz_mblock, link);
2320                 list_del_init(&mblk->link);
2321                 rb_erase(&mblk->node, &zmd->mblk_rbtree);
2322                 dmz_free_mblock(zmd, mblk);
2323         }
2324
2325         /* Sanity checks: the mblock rbtree should now be empty */
2326         root = &zmd->mblk_rbtree;
2327         rbtree_postorder_for_each_entry_safe(mblk, next, root, node) {
2328                 dmz_dev_warn(zmd->dev, "mblock %llu ref %u still in rbtree",
2329                              (u64)mblk->no, atomic_read(&mblk->ref));
2330                 atomic_set(&mblk->ref, 0);
2331                 dmz_free_mblock(zmd, mblk);
2332         }
2333
2334         /* Free the zone descriptors */
2335         dmz_drop_zones(zmd);
2336 }
2337
2338 /*
2339  * Initialize the zoned metadata.
2340  */
2341 int dmz_ctr_metadata(struct dmz_dev *dev, struct dmz_metadata **metadata)
2342 {
2343         struct dmz_metadata *zmd;
2344         unsigned int i, zid;
2345         struct dm_zone *zone;
2346         int ret;
2347
2348         zmd = kzalloc(sizeof(struct dmz_metadata), GFP_KERNEL);
2349         if (!zmd)
2350                 return -ENOMEM;
2351
2352         zmd->dev = dev;
2353         zmd->mblk_rbtree = RB_ROOT;
2354         init_rwsem(&zmd->mblk_sem);
2355         mutex_init(&zmd->mblk_flush_lock);
2356         spin_lock_init(&zmd->mblk_lock);
2357         INIT_LIST_HEAD(&zmd->mblk_lru_list);
2358         INIT_LIST_HEAD(&zmd->mblk_dirty_list);
2359
2360         mutex_init(&zmd->map_lock);
2361         atomic_set(&zmd->unmap_nr_rnd, 0);
2362         INIT_LIST_HEAD(&zmd->unmap_rnd_list);
2363         INIT_LIST_HEAD(&zmd->map_rnd_list);
2364
2365         atomic_set(&zmd->unmap_nr_seq, 0);
2366         INIT_LIST_HEAD(&zmd->unmap_seq_list);
2367         INIT_LIST_HEAD(&zmd->map_seq_list);
2368
2369         atomic_set(&zmd->nr_reserved_seq_zones, 0);
2370         INIT_LIST_HEAD(&zmd->reserved_seq_zones_list);
2371
2372         init_waitqueue_head(&zmd->free_wq);
2373
2374         /* Initialize zone descriptors */
2375         ret = dmz_init_zones(zmd);
2376         if (ret)
2377                 goto err;
2378
2379         /* Get super block */
2380         ret = dmz_load_sb(zmd);
2381         if (ret)
2382                 goto err;
2383
2384         /* Set metadata zones starting from sb_zone */
2385         zid = dmz_id(zmd, zmd->sb_zone);
2386         for (i = 0; i < zmd->nr_meta_zones << 1; i++) {
2387                 zone = dmz_get(zmd, zid + i);
2388                 if (!dmz_is_rnd(zone))
2389                         goto err;
2390                 set_bit(DMZ_META, &zone->flags);
2391         }
2392
2393         /* Load mapping table */
2394         ret = dmz_load_mapping(zmd);
2395         if (ret)
2396                 goto err;
2397
2398         /*
2399          * Cache size boundaries: allow at least 2 super blocks, the chunk map
2400          * blocks and enough blocks to be able to cache the bitmap blocks of
2401          * up to 16 zones when idle (min_nr_mblks). Otherwise, if busy, allow
2402          * the cache to add 512 more metadata blocks.
2403          */
2404         zmd->min_nr_mblks = 2 + zmd->nr_map_blocks + zmd->zone_nr_bitmap_blocks * 16;
2405         zmd->max_nr_mblks = zmd->min_nr_mblks + 512;
2406         zmd->mblk_shrinker.count_objects = dmz_mblock_shrinker_count;
2407         zmd->mblk_shrinker.scan_objects = dmz_mblock_shrinker_scan;
2408         zmd->mblk_shrinker.seeks = DEFAULT_SEEKS;
2409
2410         /* Metadata cache shrinker */
2411         ret = register_shrinker(&zmd->mblk_shrinker);
2412         if (ret) {
2413                 dmz_dev_err(dev, "Register metadata cache shrinker failed");
2414                 goto err;
2415         }
2416
2417         dmz_dev_info(dev, "Host-%s zoned block device",
2418                      bdev_zoned_model(dev->bdev) == BLK_ZONED_HA ?
2419                      "aware" : "managed");
2420         dmz_dev_info(dev, "  %llu 512-byte logical sectors",
2421                      (u64)dev->capacity);
2422         dmz_dev_info(dev, "  %u zones of %llu 512-byte logical sectors",
2423                      dev->nr_zones, (u64)dev->zone_nr_sectors);
2424         dmz_dev_info(dev, "  %u metadata zones",
2425                      zmd->nr_meta_zones * 2);
2426         dmz_dev_info(dev, "  %u data zones for %u chunks",
2427                      zmd->nr_data_zones, zmd->nr_chunks);
2428         dmz_dev_info(dev, "    %u random zones (%u unmapped)",
2429                      zmd->nr_rnd, atomic_read(&zmd->unmap_nr_rnd));
2430         dmz_dev_info(dev, "    %u sequential zones (%u unmapped)",
2431                      zmd->nr_seq, atomic_read(&zmd->unmap_nr_seq));
2432         dmz_dev_info(dev, "  %u reserved sequential data zones",
2433                      zmd->nr_reserved_seq);
2434
2435         dmz_dev_debug(dev, "Format:");
2436         dmz_dev_debug(dev, "%u metadata blocks per set (%u max cache)",
2437                       zmd->nr_meta_blocks, zmd->max_nr_mblks);
2438         dmz_dev_debug(dev, "  %u data zone mapping blocks",
2439                       zmd->nr_map_blocks);
2440         dmz_dev_debug(dev, "  %u bitmap blocks",
2441                       zmd->nr_bitmap_blocks);
2442
2443         *metadata = zmd;
2444
2445         return 0;
2446 err:
2447         dmz_cleanup_metadata(zmd);
2448         kfree(zmd);
2449         *metadata = NULL;
2450
2451         return ret;
2452 }
2453
2454 /*
2455  * Cleanup the zoned metadata resources.
2456  */
2457 void dmz_dtr_metadata(struct dmz_metadata *zmd)
2458 {
2459         unregister_shrinker(&zmd->mblk_shrinker);
2460         dmz_cleanup_metadata(zmd);
2461         kfree(zmd);
2462 }
2463
2464 /*
2465  * Check zone information on resume.
2466  */
2467 int dmz_resume_metadata(struct dmz_metadata *zmd)
2468 {
2469         struct dmz_dev *dev = zmd->dev;
2470         struct dm_zone *zone;
2471         sector_t wp_block;
2472         unsigned int i;
2473         int ret;
2474
2475         /* Check zones */
2476         for (i = 0; i < dev->nr_zones; i++) {
2477                 zone = dmz_get(zmd, i);
2478                 if (!zone) {
2479                         dmz_dev_err(dev, "Unable to get zone %u", i);
2480                         return -EIO;
2481                 }
2482
2483                 wp_block = zone->wp_block;
2484
2485                 ret = dmz_update_zone(zmd, zone);
2486                 if (ret) {
2487                         dmz_dev_err(dev, "Broken zone %u", i);
2488                         return ret;
2489                 }
2490
2491                 if (dmz_is_offline(zone)) {
2492                         dmz_dev_warn(dev, "Zone %u is offline", i);
2493                         continue;
2494                 }
2495
2496                 /* Check write pointer */
2497                 if (!dmz_is_seq(zone))
2498                         zone->wp_block = 0;
2499                 else if (zone->wp_block != wp_block) {
2500                         dmz_dev_err(dev, "Zone %u: Invalid wp (%llu / %llu)",
2501                                     i, (u64)zone->wp_block, (u64)wp_block);
2502                         zone->wp_block = wp_block;
2503                         dmz_invalidate_blocks(zmd, zone, zone->wp_block,
2504                                               dev->zone_nr_blocks - zone->wp_block);
2505                 }
2506         }
2507
2508         return 0;
2509 }