drivers/md/dm-bow.c

   1 /*
   2  * Copyright (C) 2018 Google Limited.
   3  *
   4  * This file is released under the GPL.
   5  */
   6
   7 #include "dm.h"
   8 #include "dm-core.h"
   9
  10 #include <linux/crc32.h>
  11 #include <linux/dm-bufio.h>
  12 #include <linux/module.h>
  13
  14 #define DM_MSG_PREFIX "bow"
  15
  16 struct log_entry {
  17         u64 source;
  18         u64 dest;
  19         u32 size;
  20         u32 checksum;
  21 } __packed;
  22
  23 struct log_sector {
  24         u32 magic;
  25         u16 header_version;
  26         u16 header_size;
  27         u32 block_size;
  28         u32 count;
  29         u32 sequence;
  30         sector_t sector0;
  31         struct log_entry entries[];
  32 } __packed;
  33
  34 /*
  35  * MAGIC is BOW in ascii
  36  */
  37 #define MAGIC 0x00574f42
  38 #define HEADER_VERSION 0x0100
  39
  40 /*
  41  * A sorted set of ranges representing the state of the data on the device.
  42  * Use an rb_tree for fast lookup of a given sector
  43  * Consecutive ranges are always of different type - operations on this
  44  * set must merge matching consecutive ranges.
  45  *
  46  * Top range is always of type TOP
  47  */
  48 struct bow_range {
  49         struct rb_node          node;
  50         sector_t                sector;
  51         enum {
  52                 INVALID,        /* Type not set */
  53                 SECTOR0,        /* First sector - holds log record */
  54                 SECTOR0_CURRENT,/* Live contents of sector0 */
  55                 UNCHANGED,      /* Original contents */
  56                 TRIMMED,        /* Range has been trimmed */
  57                 CHANGED,        /* Range has been changed */
  58                 BACKUP,         /* Range is being used as a backup */
  59                 TOP,            /* Final range - sector is size of device */
  60         } type;
  61         struct list_head        trimmed_list; /* list of TRIMMED ranges */
  62 };
  63
  64 static const char * const readable_type[] = {
  65         "Invalid",
  66         "Sector0",
  67         "Sector0_current",
  68         "Unchanged",
  69         "Free",
  70         "Changed",
  71         "Backup",
  72         "Top",
  73 };
  74
  75 enum state {
  76         TRIM,
  77         CHECKPOINT,
  78         COMMITTED,
  79 };
  80
  81 struct bow_context {
  82         struct dm_dev *dev;
  83         u32 block_size;
  84         u32 block_shift;
  85         struct workqueue_struct *workqueue;
  86         struct dm_bufio_client *bufio;
  87         struct mutex ranges_lock; /* Hold to access this struct and/or ranges */
  88         struct rb_root ranges;
  89         struct dm_kobject_holder kobj_holder;   /* for sysfs attributes */
  90         atomic_t state; /* One of the enum state values above */
  91         u64 trims_total;
  92         struct log_sector *log_sector;
  93         struct list_head trimmed_list;
  94         bool forward_trims;
  95 };
  96
  97 sector_t range_top(struct bow_range *br)
  98 {
  99         return container_of(rb_next(&br->node), struct bow_range, node)
 100                 ->sector;
 101 }
 102
 103 u64 range_size(struct bow_range *br)
 104 {
 105         return (range_top(br) - br->sector) * SECTOR_SIZE;
 106 }
 107
 108 static sector_t bvec_top(struct bvec_iter *bi_iter)
 109 {
 110         return bi_iter->bi_sector + bi_iter->bi_size / SECTOR_SIZE;
 111 }
 112
 113 /*
 114  * Find the first range that overlaps with bi_iter
 115  * bi_iter is set to the size of the overlapping sub-range
 116  */
 117 static struct bow_range *find_first_overlapping_range(struct rb_root *ranges,
 118                                                       struct bvec_iter *bi_iter)
 119 {
 120         struct rb_node *node = ranges->rb_node;
 121         struct bow_range *br;
 122
 123         while (node) {
 124                 br = container_of(node, struct bow_range, node);
 125
 126                 if (br->sector <= bi_iter->bi_sector
 127                     && bi_iter->bi_sector < range_top(br))
 128                         break;
 129
 130                 if (bi_iter->bi_sector < br->sector)
 131                         node = node->rb_left;
 132                 else
 133                         node = node->rb_right;
 134         }
 135
 136         WARN_ON(!node);
 137         if (!node)
 138                 return NULL;
 139
 140         if (range_top(br) - bi_iter->bi_sector
 141             < bi_iter->bi_size >> SECTOR_SHIFT)
 142                 bi_iter->bi_size = (range_top(br) - bi_iter->bi_sector)
 143                         << SECTOR_SHIFT;
 144
 145         return br;
 146 }
 147
 148 void add_before(struct rb_root *ranges, struct bow_range *new_br,
 149                 struct bow_range *existing)
 150 {
 151         struct rb_node *parent = &(existing->node);
 152         struct rb_node **link = &(parent->rb_left);
 153
 154         while (*link) {
 155                 parent = *link;
 156                 link = &((*link)->rb_right);
 157         }
 158
 159         rb_link_node(&new_br->node, parent, link);
 160         rb_insert_color(&new_br->node, ranges);
 161 }
 162
 163 /*
 164  * Given a range br returned by find_first_overlapping_range, split br into a
 165  * leading range, a range matching the bi_iter and a trailing range.
 166  * Leading and trailing may end up size 0 and will then be deleted. The
 167  * new range matching the bi_iter is then returned and should have its type
 168  * and type specific fields populated.
 169  * If bi_iter runs off the end of the range, bi_iter is truncated accordingly
 170  */
 171 static int split_range(struct bow_context *bc, struct bow_range **br,
 172                        struct bvec_iter *bi_iter)
 173 {
 174         struct bow_range *new_br;
 175
 176         if (bi_iter->bi_sector < (*br)->sector) {
 177                 WARN_ON(true);
 178                 return BLK_STS_IOERR;
 179         }
 180
 181         if (bi_iter->bi_sector > (*br)->sector) {
 182                 struct bow_range *leading_br =
 183                         kzalloc(sizeof(*leading_br), GFP_KERNEL);
 184
 185                 if (!leading_br)
 186                         return BLK_STS_RESOURCE;
 187
 188                 *leading_br = **br;
 189                 if (leading_br->type == TRIMMED)
 190                         list_add(&leading_br->trimmed_list, &bc->trimmed_list);
 191
 192                 add_before(&bc->ranges, leading_br, *br);
 193                 (*br)->sector = bi_iter->bi_sector;
 194         }
 195
 196         if (bvec_top(bi_iter) >= range_top(*br)) {
 197                 bi_iter->bi_size = (range_top(*br) - (*br)->sector)
 198                                         * SECTOR_SIZE;
 199                 return BLK_STS_OK;
 200         }
 201
 202         /* new_br will be the beginning, existing br will be the tail */
 203         new_br = kzalloc(sizeof(*new_br), GFP_KERNEL);
 204         if (!new_br)
 205                 return BLK_STS_RESOURCE;
 206
 207         new_br->sector = (*br)->sector;
 208         (*br)->sector = bvec_top(bi_iter);
 209         add_before(&bc->ranges, new_br, *br);
 210         *br = new_br;
 211
 212         return BLK_STS_OK;
 213 }
 214
 215 /*
 216  * Sets type of a range. May merge range into surrounding ranges
 217  * Since br may be invalidated, always sets br to NULL to prevent
 218  * usage after this is called
 219  */
 220 static void set_type(struct bow_context *bc, struct bow_range **br, int type)
 221 {
 222         struct bow_range *prev = container_of(rb_prev(&(*br)->node),
 223                                                       struct bow_range, node);
 224         struct bow_range *next = container_of(rb_next(&(*br)->node),
 225                                                       struct bow_range, node);
 226
 227         if ((*br)->type == TRIMMED) {
 228                 bc->trims_total -= range_size(*br);
 229                 list_del(&(*br)->trimmed_list);
 230         }
 231
 232         if (type == TRIMMED) {
 233                 bc->trims_total += range_size(*br);
 234                 list_add(&(*br)->trimmed_list, &bc->trimmed_list);
 235         }
 236
 237         (*br)->type = type;
 238
 239         if (next->type == type) {
 240                 if (type == TRIMMED)
 241                         list_del(&next->trimmed_list);
 242                 rb_erase(&next->node, &bc->ranges);
 243                 kfree(next);
 244         }
 245
 246         if (prev->type == type) {
 247                 if (type == TRIMMED)
 248                         list_del(&(*br)->trimmed_list);
 249                 rb_erase(&(*br)->node, &bc->ranges);
 250                 kfree(*br);
 251         }
 252
 253         *br = NULL;
 254 }
 255
 256 static struct bow_range *find_free_range(struct bow_context *bc)
 257 {
 258         if (list_empty(&bc->trimmed_list)) {
 259                 DMERR("Unable to find free space to back up to");
 260                 return NULL;
 261         }
 262
 263         return list_first_entry(&bc->trimmed_list, struct bow_range,
 264                                 trimmed_list);
 265 }
 266
 267 static sector_t sector_to_page(struct bow_context const *bc, sector_t sector)
 268 {
 269         WARN_ON((sector & (((sector_t)1 << (bc->block_shift - SECTOR_SHIFT)) - 1))
 270                 != 0);
 271         return sector >> (bc->block_shift - SECTOR_SHIFT);
 272 }
 273
 274 static int copy_data(struct bow_context const *bc,
 275                      struct bow_range *source, struct bow_range *dest,
 276                      u32 *checksum)
 277 {
 278         int i;
 279
 280         if (range_size(source) != range_size(dest)) {
 281                 WARN_ON(1);
 282                 return BLK_STS_IOERR;
 283         }
 284
 285         if (checksum)
 286                 *checksum = sector_to_page(bc, source->sector);
 287
 288         for (i = 0; i < range_size(source) >> bc->block_shift; ++i) {
 289                 struct dm_buffer *read_buffer, *write_buffer;
 290                 u8 *read, *write;
 291                 sector_t page = sector_to_page(bc, source->sector) + i;
 292
 293                 read = dm_bufio_read(bc->bufio, page, &read_buffer);
 294                 if (IS_ERR(read)) {
 295                         DMERR("Cannot read page %llu",
 296                               (unsigned long long)page);
 297                         return PTR_ERR(read);
 298                 }
 299
 300                 if (checksum)
 301                         *checksum = crc32(*checksum, read, bc->block_size);
 302
 303                 write = dm_bufio_new(bc->bufio,
 304                                      sector_to_page(bc, dest->sector) + i,
 305                                      &write_buffer);
 306                 if (IS_ERR(write)) {
 307                         DMERR("Cannot write sector");
 308                         dm_bufio_release(read_buffer);
 309                         return PTR_ERR(write);
 310                 }
 311
 312                 memcpy(write, read, bc->block_size);
 313
 314                 dm_bufio_mark_buffer_dirty(write_buffer);
 315                 dm_bufio_release(write_buffer);
 316                 dm_bufio_release(read_buffer);
 317         }
 318
 319         dm_bufio_write_dirty_buffers(bc->bufio);
 320         return BLK_STS_OK;
 321 }
 322
 323 /****** logging functions ******/
 324
 325 static int add_log_entry(struct bow_context *bc, sector_t source, sector_t dest,
 326                          unsigned int size, u32 checksum);
 327
 328 static int backup_log_sector(struct bow_context *bc)
 329 {
 330         struct bow_range *first_br, *free_br;
 331         struct bvec_iter bi_iter;
 332         u32 checksum = 0;
 333         int ret;
 334
 335         first_br = container_of(rb_first(&bc->ranges), struct bow_range, node);
 336
 337         if (first_br->type != SECTOR0) {
 338                 WARN_ON(1);
 339                 return BLK_STS_IOERR;
 340         }
 341
 342         if (range_size(first_br) != bc->block_size) {
 343                 WARN_ON(1);
 344                 return BLK_STS_IOERR;
 345         }
 346
 347         free_br = find_free_range(bc);
 348         /* No space left - return this error to userspace */
 349         if (!free_br)
 350                 return BLK_STS_NOSPC;
 351         bi_iter.bi_sector = free_br->sector;
 352         bi_iter.bi_size = bc->block_size;
 353         ret = split_range(bc, &free_br, &bi_iter);
 354         if (ret)
 355                 return ret;
 356         if (bi_iter.bi_size != bc->block_size) {
 357                 WARN_ON(1);
 358                 return BLK_STS_IOERR;
 359         }
 360
 361         ret = copy_data(bc, first_br, free_br, &checksum);
 362         if (ret)
 363                 return ret;
 364
 365         bc->log_sector->count = 0;
 366         bc->log_sector->sequence++;
 367         ret = add_log_entry(bc, first_br->sector, free_br->sector,
 368                             range_size(first_br), checksum);
 369         if (ret)
 370                 return ret;
 371
 372         set_type(bc, &free_br, BACKUP);
 373         return BLK_STS_OK;
 374 }
 375
 376 static int add_log_entry(struct bow_context *bc, sector_t source, sector_t dest,
 377                          unsigned int size, u32 checksum)
 378 {
 379         struct dm_buffer *sector_buffer;
 380         u8 *sector;
 381
 382         if (sizeof(struct log_sector)
 383             + sizeof(struct log_entry) * (bc->log_sector->count + 1)
 384                 > bc->block_size) {
 385                 int ret = backup_log_sector(bc);
 386
 387                 if (ret)
 388                         return ret;
 389         }
 390
 391         sector = dm_bufio_new(bc->bufio, 0, &sector_buffer);
 392         if (IS_ERR(sector)) {
 393                 DMERR("Cannot write boot sector");
 394                 dm_bufio_release(sector_buffer);
 395                 return BLK_STS_NOSPC;
 396         }
 397
 398         bc->log_sector->entries[bc->log_sector->count].source = source;
 399         bc->log_sector->entries[bc->log_sector->count].dest = dest;
 400         bc->log_sector->entries[bc->log_sector->count].size = size;
 401         bc->log_sector->entries[bc->log_sector->count].checksum = checksum;
 402         bc->log_sector->count++;
 403
 404         memcpy(sector, bc->log_sector, bc->block_size);
 405         dm_bufio_mark_buffer_dirty(sector_buffer);
 406         dm_bufio_release(sector_buffer);
 407         dm_bufio_write_dirty_buffers(bc->bufio);
 408         return BLK_STS_OK;
 409 }
 410
 411 static int prepare_log(struct bow_context *bc)
 412 {
 413         struct bow_range *free_br, *first_br;
 414         struct bvec_iter bi_iter;
 415         u32 checksum = 0;
 416         int ret;
 417
 418         /* Carve out first sector as log sector */
 419         first_br = container_of(rb_first(&bc->ranges), struct bow_range, node);
 420         if (first_br->type != UNCHANGED) {
 421                 WARN_ON(1);
 422                 return BLK_STS_IOERR;
 423         }
 424
 425         if (range_size(first_br) < bc->block_size) {
 426                 WARN_ON(1);
 427                 return BLK_STS_IOERR;
 428         }
 429         bi_iter.bi_sector = 0;
 430         bi_iter.bi_size = bc->block_size;
 431         ret = split_range(bc, &first_br, &bi_iter);
 432         if (ret)
 433                 return ret;
 434         first_br->type = SECTOR0;
 435         if (range_size(first_br) != bc->block_size) {
 436                 WARN_ON(1);
 437                 return BLK_STS_IOERR;
 438         }
 439
 440         /* Find free sector for active sector0 reads/writes */
 441         free_br = find_free_range(bc);
 442         if (!free_br)
 443                 return BLK_STS_NOSPC;
 444         bi_iter.bi_sector = free_br->sector;
 445         bi_iter.bi_size = bc->block_size;
 446         ret = split_range(bc, &free_br, &bi_iter);
 447         if (ret)
 448                 return ret;
 449
 450         /* Copy data */
 451         ret = copy_data(bc, first_br, free_br, NULL);
 452         if (ret)
 453                 return ret;
 454
 455         bc->log_sector->sector0 = free_br->sector;
 456
 457         set_type(bc, &free_br, SECTOR0_CURRENT);
 458
 459         /* Find free sector to back up original sector zero */
 460         free_br = find_free_range(bc);
 461         if (!free_br)
 462                 return BLK_STS_NOSPC;
 463         bi_iter.bi_sector = free_br->sector;
 464         bi_iter.bi_size = bc->block_size;
 465         ret = split_range(bc, &free_br, &bi_iter);
 466         if (ret)
 467                 return ret;
 468
 469         /* Back up */
 470         ret = copy_data(bc, first_br, free_br, &checksum);
 471         if (ret)
 472                 return ret;
 473
 474         /*
 475          * Set up our replacement boot sector - it will get written when we
 476          * add the first log entry, which we do immediately
 477          */
 478         bc->log_sector->magic = MAGIC;
 479         bc->log_sector->header_version = HEADER_VERSION;
 480         bc->log_sector->header_size = sizeof(*bc->log_sector);
 481         bc->log_sector->block_size = bc->block_size;
 482         bc->log_sector->count = 0;
 483         bc->log_sector->sequence = 0;
 484
 485         /* Add log entry */
 486         ret = add_log_entry(bc, first_br->sector, free_br->sector,
 487                             range_size(first_br), checksum);
 488         if (ret)
 489                 return ret;
 490
 491         set_type(bc, &free_br, BACKUP);
 492         return BLK_STS_OK;
 493 }
 494
 495 static struct bow_range *find_sector0_current(struct bow_context *bc)
 496 {
 497         struct bvec_iter bi_iter;
 498
 499         bi_iter.bi_sector = bc->log_sector->sector0;
 500         bi_iter.bi_size = bc->block_size;
 501         return find_first_overlapping_range(&bc->ranges, &bi_iter);
 502 }
 503
 504 /****** sysfs interface functions ******/
 505
 506 static ssize_t state_show(struct kobject *kobj, struct kobj_attribute *attr,
 507                           char *buf)
 508 {
 509         struct bow_context *bc = container_of(kobj, struct bow_context,
 510                                               kobj_holder.kobj);
 511
 512         return scnprintf(buf, PAGE_SIZE, "%d\n", atomic_read(&bc->state));
 513 }
 514
 515 static ssize_t state_store(struct kobject *kobj, struct kobj_attribute *attr,
 516                            const char *buf, size_t count)
 517 {
 518         struct bow_context *bc = container_of(kobj, struct bow_context,
 519                                               kobj_holder.kobj);
 520         enum state state, original_state;
 521         int ret;
 522
 523         state = buf[0] - '0';
 524         if (state < TRIM || state > COMMITTED) {
 525                 DMERR("State value %d out of range", state);
 526                 return -EINVAL;
 527         }
 528
 529         mutex_lock(&bc->ranges_lock);
 530         original_state = atomic_read(&bc->state);
 531         if (state != original_state + 1) {
 532                 DMERR("Invalid state change from %d to %d",
 533                       original_state, state);
 534                 ret = -EINVAL;
 535                 goto bad;
 536         }
 537
 538         DMINFO("Switching to state %s", state == CHECKPOINT ? "Checkpoint"
 539                : state == COMMITTED ? "Committed" : "Unknown");
 540
 541         if (state == CHECKPOINT) {
 542                 ret = prepare_log(bc);
 543                 if (ret) {
 544                         DMERR("Failed to switch to checkpoint state");
 545                         goto bad;
 546                 }
 547         } else if (state == COMMITTED) {
 548                 struct bow_range *br = find_sector0_current(bc);
 549                 struct bow_range *sector0_br =
 550                         container_of(rb_first(&bc->ranges), struct bow_range,
 551                                      node);
 552
 553                 ret = copy_data(bc, br, sector0_br, 0);
 554                 if (ret) {
 555                         DMERR("Failed to switch to committed state");
 556                         goto bad;
 557                 }
 558         }
 559         atomic_inc(&bc->state);
 560         ret = count;
 561
 562 bad:
 563         mutex_unlock(&bc->ranges_lock);
 564         return ret;
 565 }
 566
 567 static ssize_t free_show(struct kobject *kobj, struct kobj_attribute *attr,
 568                           char *buf)
 569 {
 570         struct bow_context *bc = container_of(kobj, struct bow_context,
 571                                               kobj_holder.kobj);
 572         u64 trims_total;
 573
 574         mutex_lock(&bc->ranges_lock);
 575         trims_total = bc->trims_total;
 576         mutex_unlock(&bc->ranges_lock);
 577
 578         return scnprintf(buf, PAGE_SIZE, "%llu\n", trims_total);
 579 }
 580
 581 static struct kobj_attribute attr_state = __ATTR_RW(state);
 582 static struct kobj_attribute attr_free = __ATTR_RO(free);
 583
 584 static struct attribute *bow_attrs[] = {
 585         &attr_state.attr,
 586         &attr_free.attr,
 587         NULL
 588 };
 589
 590 static struct kobj_type bow_ktype = {
 591         .sysfs_ops = &kobj_sysfs_ops,
 592         .default_attrs = bow_attrs,
 593         .release = dm_kobject_release
 594 };
 595
 596 /****** constructor/destructor ******/
 597
 598 static void dm_bow_dtr(struct dm_target *ti)
 599 {
 600         struct bow_context *bc = (struct bow_context *) ti->private;
 601         struct kobject *kobj;
 602
 603         if (bc->workqueue)
 604                 destroy_workqueue(bc->workqueue);
 605         if (bc->bufio)
 606                 dm_bufio_client_destroy(bc->bufio);
 607
 608         kobj = &bc->kobj_holder.kobj;
 609         if (kobj->state_initialized) {
 610                 kobject_put(kobj);
 611                 wait_for_completion(dm_get_completion_from_kobject(kobj));
 612         }
 613
 614         while (rb_first(&bc->ranges)) {
 615                 struct bow_range *br = container_of(rb_first(&bc->ranges),
 616                                               struct bow_range, node);
 617
 618                 rb_erase(&br->node, &bc->ranges);
 619                 kfree(br);
 620         }
 621
 622         mutex_destroy(&bc->ranges_lock);
 623         kfree(bc->log_sector);
 624         kfree(bc);
 625 }
 626
 627 static void dm_bow_io_hints(struct dm_target *ti, struct queue_limits *limits)
 628 {
 629         struct bow_context *bc = ti->private;
 630         const unsigned int block_size = bc->block_size;
 631
 632         limits->logical_block_size =
 633                 max_t(unsigned int, limits->logical_block_size, block_size);
 634         limits->physical_block_size =
 635                 max_t(unsigned int, limits->physical_block_size, block_size);
 636         limits->io_min = max_t(unsigned int, limits->io_min, block_size);
 637
 638         if (limits->max_discard_sectors == 0) {
 639                 limits->discard_granularity = 1 << 12;
 640                 limits->max_hw_discard_sectors = 1 << 15;
 641                 limits->max_discard_sectors = 1 << 15;
 642                 bc->forward_trims = false;
 643         } else {
 644                 limits->discard_granularity = 1 << 12;
 645                 bc->forward_trims = true;
 646         }
 647 }
 648
 649 static int dm_bow_ctr_optional(struct dm_target *ti, unsigned int argc, char **argv)
 650 {
 651         struct bow_context *bc = ti->private;
 652         struct dm_arg_set as;
 653         static const struct dm_arg _args[] = {
 654                 {0, 1, "Invalid number of feature args"},
 655         };
 656         unsigned int opt_params;
 657         const char *opt_string;
 658         int err;
 659         char dummy;
 660
 661         as.argc = argc;
 662         as.argv = argv;
 663
 664         err = dm_read_arg_group(_args, &as, &opt_params, &ti->error);
 665         if (err)
 666                 return err;
 667
 668         while (opt_params--) {
 669                 opt_string = dm_shift_arg(&as);
 670                 if (!opt_string) {
 671                         ti->error = "Not enough feature arguments";
 672                         return -EINVAL;
 673                 }
 674
 675                 if (sscanf(opt_string, "block_size:%u%c",
 676                                         &bc->block_size, &dummy) == 1) {
 677                         if (bc->block_size < SECTOR_SIZE ||
 678                             bc->block_size > 4096 ||
 679                             !is_power_of_2(bc->block_size)) {
 680                                 ti->error = "Invalid block_size";
 681                                 return -EINVAL;
 682                         }
 683                 } else {
 684                         ti->error = "Invalid feature arguments";
 685                         return -EINVAL;
 686                 }
 687         }
 688
 689         return 0;
 690 }
 691
 692 static int dm_bow_ctr(struct dm_target *ti, unsigned int argc, char **argv)
 693 {
 694         struct bow_context *bc;
 695         struct bow_range *br;
 696         int ret;
 697         struct mapped_device *md = dm_table_get_md(ti->table);
 698
 699         if (argc < 1) {
 700                 ti->error = "Invalid argument count";
 701                 return -EINVAL;
 702         }
 703
 704         bc = kzalloc(sizeof(*bc), GFP_KERNEL);
 705         if (!bc) {
 706                 ti->error = "Cannot allocate bow context";
 707                 return -ENOMEM;
 708         }
 709
 710         ti->num_flush_bios = 1;
 711         ti->num_discard_bios = 1;
 712         ti->num_write_same_bios = 1;
 713         ti->private = bc;
 714
 715         ret = dm_get_device(ti, argv[0], dm_table_get_mode(ti->table),
 716                             &bc->dev);
 717         if (ret) {
 718                 ti->error = "Device lookup failed";
 719                 goto bad;
 720         }
 721
 722         bc->block_size =
 723                 bdev_get_queue(bc->dev->bdev)->limits.logical_block_size;
 724         if (argc > 1) {
 725                 ret = dm_bow_ctr_optional(ti, argc - 1, &argv[1]);
 726                 if (ret)
 727                         goto bad;
 728         }
 729
 730         bc->block_shift = ilog2(bc->block_size);
 731         bc->log_sector = kzalloc(bc->block_size, GFP_KERNEL);
 732         if (!bc->log_sector) {
 733                 ti->error = "Cannot allocate log sector";
 734                 goto bad;
 735         }
 736
 737         init_completion(&bc->kobj_holder.completion);
 738         ret = kobject_init_and_add(&bc->kobj_holder.kobj, &bow_ktype,
 739                                    &disk_to_dev(dm_disk(md))->kobj, "%s",
 740                                    "bow");
 741         if (ret) {
 742                 ti->error = "Cannot create sysfs node";
 743                 goto bad;
 744         }
 745
 746         mutex_init(&bc->ranges_lock);
 747         bc->ranges = RB_ROOT;
 748         bc->bufio = dm_bufio_client_create(bc->dev->bdev, bc->block_size, 1, 0,
 749                                            NULL, NULL);
 750         if (IS_ERR(bc->bufio)) {
 751                 ti->error = "Cannot initialize dm-bufio";
 752                 ret = PTR_ERR(bc->bufio);
 753                 bc->bufio = NULL;
 754                 goto bad;
 755         }
 756
 757         bc->workqueue = alloc_workqueue("dm-bow",
 758                                         WQ_CPU_INTENSIVE | WQ_MEM_RECLAIM
 759                                         | WQ_UNBOUND, num_online_cpus());
 760         if (!bc->workqueue) {
 761                 ti->error = "Cannot allocate workqueue";
 762                 ret = -ENOMEM;
 763                 goto bad;
 764         }
 765
 766         INIT_LIST_HEAD(&bc->trimmed_list);
 767
 768         br = kzalloc(sizeof(*br), GFP_KERNEL);
 769         if (!br) {
 770                 ti->error = "Cannot allocate ranges";
 771                 ret = -ENOMEM;
 772                 goto bad;
 773         }
 774
 775         br->sector = ti->len;
 776         br->type = TOP;
 777         rb_link_node(&br->node, NULL, &bc->ranges.rb_node);
 778         rb_insert_color(&br->node, &bc->ranges);
 779
 780         br = kzalloc(sizeof(*br), GFP_KERNEL);
 781         if (!br) {
 782                 ti->error = "Cannot allocate ranges";
 783                 ret = -ENOMEM;
 784                 goto bad;
 785         }
 786
 787         br->sector = 0;
 788         br->type = UNCHANGED;
 789         rb_link_node(&br->node, bc->ranges.rb_node,
 790                      &bc->ranges.rb_node->rb_left);
 791         rb_insert_color(&br->node, &bc->ranges);
 792
 793         ti->discards_supported = true;
 794
 795         return 0;
 796
 797 bad:
 798         dm_bow_dtr(ti);
 799         return ret;
 800 }
 801
 802 /****** Handle writes ******/
 803
 804 static int prepare_unchanged_range(struct bow_context *bc, struct bow_range *br,
 805                                    struct bvec_iter *bi_iter,
 806                                    bool record_checksum)
 807 {
 808         struct bow_range *backup_br;
 809         struct bvec_iter backup_bi;
 810         sector_t log_source, log_dest;
 811         unsigned int log_size;
 812         u32 checksum = 0;
 813         int ret;
 814         int original_type;
 815         sector_t sector0;
 816
 817         /* Find a free range */
 818         backup_br = find_free_range(bc);
 819         if (!backup_br)
 820                 return BLK_STS_NOSPC;
 821
 822         /* Carve out a backup range. This may be smaller than the br given */
 823         backup_bi.bi_sector = backup_br->sector;
 824         backup_bi.bi_size = min(range_size(backup_br), (u64) bi_iter->bi_size);
 825         ret = split_range(bc, &backup_br, &backup_bi);
 826         if (ret)
 827                 return ret;
 828
 829         /*
 830          * Carve out a changed range. This will not be smaller than the backup
 831          * br since the backup br is smaller than the source range and iterator
 832          */
 833         bi_iter->bi_size = backup_bi.bi_size;
 834         ret = split_range(bc, &br, bi_iter);
 835         if (ret)
 836                 return ret;
 837         if (range_size(br) != range_size(backup_br)) {
 838                 WARN_ON(1);
 839                 return BLK_STS_IOERR;
 840         }
 841
 842
 843         /* Copy data over */
 844         ret = copy_data(bc, br, backup_br, record_checksum ? &checksum : NULL);
 845         if (ret)
 846                 return ret;
 847
 848         /* Add an entry to the log */
 849         log_source = br->sector;
 850         log_dest = backup_br->sector;
 851         log_size = range_size(br);
 852
 853         /*
 854          * Set the types. Note that since set_type also amalgamates ranges
 855          * we have to set both sectors to their final type before calling
 856          * set_type on either
 857          */
 858         original_type = br->type;
 859         sector0 = backup_br->sector;
 860         bc->trims_total -= range_size(backup_br);
 861         if (backup_br->type == TRIMMED)
 862                 list_del(&backup_br->trimmed_list);
 863         backup_br->type = br->type == SECTOR0_CURRENT ? SECTOR0_CURRENT
 864                                                       : BACKUP;
 865         br->type = CHANGED;
 866         set_type(bc, &backup_br, backup_br->type);
 867
 868         /*
 869          * Add the log entry after marking the backup sector, since adding a log
 870          * can cause another backup
 871          */
 872         ret = add_log_entry(bc, log_source, log_dest, log_size, checksum);
 873         if (ret) {
 874                 br->type = original_type;
 875                 return ret;
 876         }
 877
 878         /* Now it is safe to mark this backup successful */
 879         if (original_type == SECTOR0_CURRENT)
 880                 bc->log_sector->sector0 = sector0;
 881
 882         set_type(bc, &br, br->type);
 883         return ret;
 884 }
 885
 886 static int prepare_free_range(struct bow_context *bc, struct bow_range *br,
 887                               struct bvec_iter *bi_iter)
 888 {
 889         int ret;
 890
 891         ret = split_range(bc, &br, bi_iter);
 892         if (ret)
 893                 return ret;
 894         set_type(bc, &br, CHANGED);
 895         return BLK_STS_OK;
 896 }
 897
 898 static int prepare_changed_range(struct bow_context *bc, struct bow_range *br,
 899                                  struct bvec_iter *bi_iter)
 900 {
 901         /* Nothing to do ... */
 902         return BLK_STS_OK;
 903 }
 904
 905 static int prepare_one_range(struct bow_context *bc,
 906                              struct bvec_iter *bi_iter)
 907 {
 908         struct bow_range *br = find_first_overlapping_range(&bc->ranges,
 909                                                             bi_iter);
 910         switch (br->type) {
 911         case CHANGED:
 912                 return prepare_changed_range(bc, br, bi_iter);
 913
 914         case TRIMMED:
 915                 return prepare_free_range(bc, br, bi_iter);
 916
 917         case UNCHANGED:
 918         case BACKUP:
 919                 return prepare_unchanged_range(bc, br, bi_iter, true);
 920
 921         /*
 922          * We cannot track the checksum for the active sector0, since it
 923          * may change at any point.
 924          */
 925         case SECTOR0_CURRENT:
 926                 return prepare_unchanged_range(bc, br, bi_iter, false);
 927
 928         case SECTOR0:   /* Handled in the dm_bow_map */
 929         case TOP:       /* Illegal - top is off the end of the device */
 930         default:
 931                 WARN_ON(1);
 932                 return BLK_STS_IOERR;
 933         }
 934 }
 935
 936 struct write_work {
 937         struct work_struct work;
 938         struct bow_context *bc;
 939         struct bio *bio;
 940 };
 941
 942 static void bow_write(struct work_struct *work)
 943 {
 944         struct write_work *ww = container_of(work, struct write_work, work);
 945         struct bow_context *bc = ww->bc;
 946         struct bio *bio = ww->bio;
 947         struct bvec_iter bi_iter = bio->bi_iter;
 948         int ret = BLK_STS_OK;
 949
 950         kfree(ww);
 951
 952         mutex_lock(&bc->ranges_lock);
 953         do {
 954                 ret = prepare_one_range(bc, &bi_iter);
 955                 bi_iter.bi_sector += bi_iter.bi_size / SECTOR_SIZE;
 956                 bi_iter.bi_size = bio->bi_iter.bi_size
 957                         - (bi_iter.bi_sector - bio->bi_iter.bi_sector)
 958                           * SECTOR_SIZE;
 959         } while (!ret && bi_iter.bi_size);
 960
 961         mutex_unlock(&bc->ranges_lock);
 962
 963         if (!ret) {
 964                 bio_set_dev(bio, bc->dev->bdev);
 965                 submit_bio(bio);
 966         } else {
 967                 DMERR("Write failure with error %d", -ret);
 968                 bio->bi_status = ret;
 969                 bio_endio(bio);
 970         }
 971 }
 972
 973 static int queue_write(struct bow_context *bc, struct bio *bio)
 974 {
 975         struct write_work *ww = kmalloc(sizeof(*ww), GFP_NOIO | __GFP_NORETRY
 976                                         | __GFP_NOMEMALLOC | __GFP_NOWARN);
 977         if (!ww) {
 978                 DMERR("Failed to allocate write_work");
 979                 return -ENOMEM;
 980         }
 981
 982         INIT_WORK(&ww->work, bow_write);
 983         ww->bc = bc;
 984         ww->bio = bio;
 985         queue_work(bc->workqueue, &ww->work);
 986         return DM_MAPIO_SUBMITTED;
 987 }
 988
 989 static int handle_sector0(struct bow_context *bc, struct bio *bio)
 990 {
 991         int ret = DM_MAPIO_REMAPPED;
 992
 993         if (bio->bi_iter.bi_size > bc->block_size) {
 994                 struct bio * split = bio_split(bio,
 995                                                bc->block_size >> SECTOR_SHIFT,
 996                                                GFP_NOIO,
 997                                                &fs_bio_set);
 998                 if (!split) {
 999                         DMERR("Failed to split bio");
1000                         bio->bi_status = BLK_STS_RESOURCE;
1001                         bio_endio(bio);
1002                         return DM_MAPIO_SUBMITTED;
1003                 }
1004
1005                 bio_chain(split, bio);
1006                 split->bi_iter.bi_sector = bc->log_sector->sector0;
1007                 bio_set_dev(split, bc->dev->bdev);
1008                 submit_bio(split);
1009
1010                 if (bio_data_dir(bio) == WRITE)
1011                         ret = queue_write(bc, bio);
1012         } else {
1013                 bio->bi_iter.bi_sector = bc->log_sector->sector0;
1014         }
1015
1016         return ret;
1017 }
1018
1019 static int add_trim(struct bow_context *bc, struct bio *bio)
1020 {
1021         struct bow_range *br;
1022         struct bvec_iter bi_iter = bio->bi_iter;
1023
1024         DMDEBUG("add_trim: %llu, %u",
1025                 (unsigned long long)bio->bi_iter.bi_sector,
1026                 bio->bi_iter.bi_size);
1027
1028         do {
1029                 br = find_first_overlapping_range(&bc->ranges, &bi_iter);
1030
1031                 switch (br->type) {
1032                 case UNCHANGED:
1033                         if (!split_range(bc, &br, &bi_iter))
1034                                 set_type(bc, &br, TRIMMED);
1035                         break;
1036
1037                 case TRIMMED:
1038                         /* Nothing to do */
1039                         break;
1040
1041                 default:
1042                         /* No other case is legal in TRIM state */
1043                         WARN_ON(true);
1044                         break;
1045                 }
1046
1047                 bi_iter.bi_sector += bi_iter.bi_size / SECTOR_SIZE;
1048                 bi_iter.bi_size = bio->bi_iter.bi_size
1049                         - (bi_iter.bi_sector - bio->bi_iter.bi_sector)
1050                           * SECTOR_SIZE;
1051
1052         } while (bi_iter.bi_size);
1053
1054         bio_endio(bio);
1055         return DM_MAPIO_SUBMITTED;
1056 }
1057
1058 static int remove_trim(struct bow_context *bc, struct bio *bio)
1059 {
1060         struct bow_range *br;
1061         struct bvec_iter bi_iter = bio->bi_iter;
1062
1063         DMDEBUG("remove_trim: %llu, %u",
1064                 (unsigned long long)bio->bi_iter.bi_sector,
1065                 bio->bi_iter.bi_size);
1066
1067         do {
1068                 br = find_first_overlapping_range(&bc->ranges, &bi_iter);
1069
1070                 switch (br->type) {
1071                 case UNCHANGED:
1072                         /* Nothing to do */
1073                         break;
1074
1075                 case TRIMMED:
1076                         if (!split_range(bc, &br, &bi_iter))
1077                                 set_type(bc, &br, UNCHANGED);
1078                         break;
1079
1080                 default:
1081                         /* No other case is legal in TRIM state */
1082                         WARN_ON(true);
1083                         break;
1084                 }
1085
1086                 bi_iter.bi_sector += bi_iter.bi_size / SECTOR_SIZE;
1087                 bi_iter.bi_size = bio->bi_iter.bi_size
1088                         - (bi_iter.bi_sector - bio->bi_iter.bi_sector)
1089                           * SECTOR_SIZE;
1090
1091         } while (bi_iter.bi_size);
1092
1093         return DM_MAPIO_REMAPPED;
1094 }
1095
1096 int remap_unless_illegal_trim(struct bow_context *bc, struct bio *bio)
1097 {
1098         if (!bc->forward_trims && bio_op(bio) == REQ_OP_DISCARD) {
1099                 bio->bi_status = BLK_STS_NOTSUPP;
1100                 bio_endio(bio);
1101                 return DM_MAPIO_SUBMITTED;
1102         } else {
1103                 bio_set_dev(bio, bc->dev->bdev);
1104                 return DM_MAPIO_REMAPPED;
1105         }
1106 }
1107
1108 /****** dm interface ******/
1109
1110 static int dm_bow_map(struct dm_target *ti, struct bio *bio)
1111 {
1112         int ret = DM_MAPIO_REMAPPED;
1113         struct bow_context *bc = ti->private;
1114
1115         if (likely(bc->state.counter == COMMITTED))
1116                 return remap_unless_illegal_trim(bc, bio);
1117
1118         if (bio_data_dir(bio) == READ && bio->bi_iter.bi_sector != 0)
1119                 return remap_unless_illegal_trim(bc, bio);
1120
1121         if (atomic_read(&bc->state) != COMMITTED) {
1122                 enum state state;
1123
1124                 mutex_lock(&bc->ranges_lock);
1125                 state = atomic_read(&bc->state);
1126                 if (state == TRIM) {
1127                         if (bio_op(bio) == REQ_OP_DISCARD)
1128                                 ret = add_trim(bc, bio);
1129                         else if (bio_data_dir(bio) == WRITE)
1130                                 ret = remove_trim(bc, bio);
1131                         else
1132                                 /* pass-through */;
1133                 } else if (state == CHECKPOINT) {
1134                         if (bio->bi_iter.bi_sector == 0)
1135                                 ret = handle_sector0(bc, bio);
1136                         else if (bio_data_dir(bio) == WRITE)
1137                                 ret = queue_write(bc, bio);
1138                         else
1139                                 /* pass-through */;
1140                 } else {
1141                         /* pass-through */
1142                 }
1143                 mutex_unlock(&bc->ranges_lock);
1144         }
1145
1146         if (ret == DM_MAPIO_REMAPPED)
1147                 return remap_unless_illegal_trim(bc, bio);
1148
1149         return ret;
1150 }
1151
1152 static void dm_bow_tablestatus(struct dm_target *ti, char *result,
1153                                unsigned int maxlen)
1154 {
1155         char *end = result + maxlen;
1156         struct bow_context *bc = ti->private;
1157         struct rb_node *i;
1158         int trimmed_list_length = 0;
1159         int trimmed_range_count = 0;
1160         struct bow_range *br;
1161
1162         if (maxlen == 0)
1163                 return;
1164         result[0] = 0;
1165
1166         list_for_each_entry(br, &bc->trimmed_list, trimmed_list)
1167                 if (br->type == TRIMMED) {
1168                         ++trimmed_list_length;
1169                 } else {
1170                         scnprintf(result, end - result,
1171                                   "ERROR: non-trimmed entry in trimmed_list");
1172                         return;
1173                 }
1174
1175         if (!rb_first(&bc->ranges)) {
1176                 scnprintf(result, end - result, "ERROR: Empty ranges");
1177                 return;
1178         }
1179
1180         if (container_of(rb_first(&bc->ranges), struct bow_range, node)
1181             ->sector) {
1182                 scnprintf(result, end - result,
1183                          "ERROR: First range does not start at sector 0");
1184                 return;
1185         }
1186
1187         for (i = rb_first(&bc->ranges); i; i = rb_next(i)) {
1188                 struct bow_range *br = container_of(i, struct bow_range, node);
1189
1190                 result += scnprintf(result, end - result, "%s: %llu",
1191                                     readable_type[br->type],
1192                                     (unsigned long long)br->sector);
1193                 if (result >= end)
1194                         return;
1195
1196                 result += scnprintf(result, end - result, "\n");
1197                 if (result >= end)
1198                         return;
1199
1200                 if (br->type == TRIMMED)
1201                         ++trimmed_range_count;
1202
1203                 if (br->type == TOP) {
1204                         if (br->sector != ti->len) {
1205                                 scnprintf(result, end - result,
1206                                          "\nERROR: Top sector is incorrect");
1207                         }
1208
1209                         if (&br->node != rb_last(&bc->ranges)) {
1210                                 scnprintf(result, end - result,
1211                                           "\nERROR: Top sector is not last");
1212                         }
1213
1214                         break;
1215                 }
1216
1217                 if (!rb_next(i)) {
1218                         scnprintf(result, end - result,
1219                                   "\nERROR: Last range not of type TOP");
1220                         return;
1221                 }
1222
1223                 if (br->sector > range_top(br)) {
1224                         scnprintf(result, end - result,
1225                                   "\nERROR: sectors out of order");
1226                         return;
1227                 }
1228         }
1229
1230         if (trimmed_range_count != trimmed_list_length)
1231                 scnprintf(result, end - result,
1232                           "\nERROR: not all trimmed ranges in trimmed list");
1233 }
1234
1235 static void dm_bow_status(struct dm_target *ti, status_type_t type,
1236                           unsigned int status_flags, char *result,
1237                           unsigned int maxlen)
1238 {
1239         switch (type) {
1240         case STATUSTYPE_INFO:
1241         default:
1242                 if (maxlen)
1243                         result[0] = 0;
1244                 break;
1245
1246         case STATUSTYPE_TABLE:
1247                 dm_bow_tablestatus(ti, result, maxlen);
1248                 break;
1249         }
1250 }
1251
1252 int dm_bow_prepare_ioctl(struct dm_target *ti, struct block_device **bdev)
1253 {
1254         struct bow_context *bc = ti->private;
1255         struct dm_dev *dev = bc->dev;
1256
1257         *bdev = dev->bdev;
1258         /* Only pass ioctls through if the device sizes match exactly. */
1259         return ti->len != i_size_read(dev->bdev->bd_inode) >> SECTOR_SHIFT;
1260 }
1261
1262 static int dm_bow_iterate_devices(struct dm_target *ti,
1263                                   iterate_devices_callout_fn fn, void *data)
1264 {
1265         struct bow_context *bc = ti->private;
1266
1267         return fn(ti, bc->dev, 0, ti->len, data);
1268 }
1269
1270 static struct target_type bow_target = {
1271         .name   = "bow",
1272         .version = {1, 2, 0},
1273         .module = THIS_MODULE,
1274         .ctr    = dm_bow_ctr,
1275         .dtr    = dm_bow_dtr,
1276         .map    = dm_bow_map,
1277         .status = dm_bow_status,
1278         .prepare_ioctl  = dm_bow_prepare_ioctl,
1279         .iterate_devices = dm_bow_iterate_devices,
1280         .io_hints = dm_bow_io_hints,
1281 };
1282
1283 int __init dm_bow_init(void)
1284 {
1285         int r = dm_register_target(&bow_target);
1286
1287         if (r < 0)
1288                 DMERR("registering bow failed %d", r);
1289         return r;
1290 }
1291
1292 void dm_bow_exit(void)
1293 {
1294         dm_unregister_target(&bow_target);
1295 }
1296
1297 MODULE_LICENSE("GPL");
1298
1299 module_init(dm_bow_init);
1300 module_exit(dm_bow_exit);