drivers/md/dm-bootcache.c

   1 /*
   2  * Copyright 2012 Google, Inc.
   3  *
   4  * This software is licensed under the terms of the GNU General Public
   5  * License version 2, as published by the Free Software Foundation, and
   6  * may be copied, distributed, and modified under those terms.
   7  *
   8  * This program is distributed in the hope that it will be useful,
   9  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  10  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  11  * GNU General Public License for more details.
  12  */
  13 /*
  14  * The boot cache device mapper reads a set of contiguously stored sectors.
  15  * These sectors are copies of the sectors read during an earlier boot. Only
  16  * small reads (less than some number of sectors) are selected for the cache,
  17  * since this results in the highest benefit.
  18  *
  19  * The data for the boot cache consists of three sections:
  20  * a header, the sector trace and the cache sectors.
  21  * These are stored after the file system in the same partition.
  22  *
  23  * The boot cache is created by separate user process that reads a
  24  * sector trace created if the boot cache is invalid.
  25  */
  26 #include <linux/async.h>
  27 #include <linux/atomic.h>
  28 #include <linux/delay.h>
  29 #include <linux/device-mapper.h>
  30 #include <linux/kernel.h>
  31 #include <linux/module.h>
  32 #include <linux/mutex.h>
  33 #include <linux/sched.h>
  34 #include <linux/slab.h>
  35 #include <linux/workqueue.h>
  36 #include "dm.h"
  37
  38 #include "dm-bootcache.h"
  39
  40 #define DM_MSG_PREFIX "bootcache"
  41
  42 #define DEFAULT_MAX_PAGES       50000
  43 #define DEFAULT_SIZE_LIMIT      128
  44 #define DEFAULT_MAX_TRACE       (1 << 13)
  45 #define MAX_TRACE               (1 << 20)
  46 #define DEV_MODE                FMODE_READ
  47 #define SECTOR_SIZE             (1 << SECTOR_SHIFT)
  48 #define SECTORS_PER_PAGE        (PAGE_SIZE / SECTOR_SIZE)
  49 #define MAX_DEVICE_NAME         (1 << 8)
  50
  51
  52 enum bc_state {
  53         BC_INIT = 1,
  54         BC_TRACING,
  55         BC_FILLING,
  56         BC_FILLED,
  57         BC_BYPASS
  58 };
  59
  60 struct bootcache_waiter {
  61         struct completion completion;
  62         int error;
  63 };
  64
  65 struct bootcache_args {
  66         /* Device being cached. The boot cache also stores its cache here. */
  67         char device[MAX_DEVICE_NAME];
  68
  69         /* Identifies the data on the device. eg root hex digest from verity */
  70         char signature[MAX_SIGNATURE];
  71
  72         /* Sector start of cache on device */
  73         u64 cache_start;
  74
  75         /* Max num of pages to cache */
  76         u64 max_pages;
  77
  78         /* Reads this size or larger will not be cached */
  79         u64 size_limit;
  80
  81         /* Maximum number of trace records to collect */
  82         u64 max_trace;
  83 };
  84
  85 struct bootcache_stats {
  86         unsigned num_requests;     /* Read requests */
  87         unsigned num_hits;         /* Number of hits */
  88         unsigned overlapped;       /* Blocks used while reading rest */
  89 };
  90
  91 struct bootcache_page {
  92         struct bootcache_page *next;
  93         struct page *page;
  94         u64 sector;     /* first sector in set of sectors in this page */
  95         bool is_filled;
  96 };
  97
  98 struct bootcache_sector_map {
  99         u32     num_buckets;    /* Number of buckets for hash */
 100         u32     num_pages;      /* Number of pages of sectors */
 101         struct bootcache_page *pages;   /* Cache of pages of sectors */
 102         struct bootcache_page *nextpage;/* Next page entry to add */
 103         struct bootcache_page **bucket; /* Hash buckets */
 104 };
 105
 106 struct bootcache {
 107         const char      *name;          /* Taken from device being cached */
 108         struct bootcache_stats  stats;
 109         struct bootcache_args   args;
 110         sector_t        begin;  /* Beginning sector of underlying device */
 111         sector_t        len;    /* Length in sectors of underlying device */
 112         atomic_t        state;  /* Cache state - needs atomic read */
 113         spinlock_t      trace_lock;     /* Spin lock for trace table */
 114         struct bootcache_trace  *trace; /* Trace of blocks read during boot */
 115         u32             trace_next;     /* Next element to fill for tracing */
 116         u32             max_io;         /* Max pages we can read/write */
 117         bool            is_valid;       /* The cache is valid */
 118         bool            is_free;        /* The cache data has been freed */
 119         struct kref     kref;           /* Protects in-flight operations */
 120         struct dm_target        *ti;    /* Device in device mapper */
 121         struct bio_set  *bio_set;       /* Set of bios for reading blocks */
 122         struct dm_dev   *dev;           /* Device for both cache and data */
 123         struct delayed_work     work;   /* Work that needs a thread */
 124         struct mutex    cache_lock;     /* Locks everything in cache struct */
 125         struct completion       init_complete;  /* Wait for initialization */
 126         struct bootcache_sector_map sectors;    /* Table of pages of sectors */
 127         /* Sysfs files for managing the block cache */
 128         struct bin_attribute valid;     /* 1 -> valid 0 -> build cache */
 129         struct bin_attribute free;      /* Write '1' to free cache */
 130         struct bin_attribute header;    /* Content for bootcache header */
 131         struct bin_attribute blocktrace;/* Trace of blocks accessed */
 132         /* Computed hdr to be compared with on disk header. */
 133         struct bootcache_hdr hdr;
 134 };
 135
 136 static inline u64 bytes_to_pages(u64 bytes)
 137 {
 138         return (bytes + PAGE_SIZE - 1) >> PAGE_SHIFT;
 139 }
 140
 141 static inline u64 sectors_to_pages(u64 sectors)
 142 {
 143         return sectors >> (PAGE_SHIFT - SECTOR_SHIFT);
 144 }
 145
 146 static inline u64 pages_to_sectors(u64 pages)
 147 {
 148         return pages << (PAGE_SHIFT - SECTOR_SHIFT);
 149 }
 150
 151 static void bootcache_bio_destructor(struct bio *bio)
 152 {
 153         struct bootcache *cache = bio->bi_private;
 154
 155         bio_free(bio, cache->bio_set);
 156 }
 157
 158 static inline struct bootcache_page **bootcache_hash(
 159                                         struct bootcache_sector_map *map,
 160                                         u64 sector)
 161 {
 162         return &map->bucket[(u32)sector % map->num_buckets];
 163 }
 164
 165 static struct bootcache_page *bootcache_get_chunk(
 166                                         struct bootcache_sector_map *map,
 167                                         u64 sector)
 168 {
 169         struct bootcache_page *next;
 170
 171         next = *bootcache_hash(map, sector);
 172         while (next) {
 173                 if (sector == next->sector) {
 174                         if (next->is_filled)
 175                                 return next;
 176                         else
 177                                 return NULL;
 178                 }
 179                 next = next->next;
 180         }
 181         return next;
 182 }
 183
 184 struct bootcache_page *bootcache_new_chunk(struct bootcache_sector_map *map,
 185                                         u64 sector)
 186 {
 187         struct bootcache_page **bucket = bootcache_hash(map, sector);
 188         struct bootcache_page *p;
 189
 190         if (map->nextpage == &map->pages[map->num_pages]) {
 191                 DMWARN("block cache full");
 192                 return NULL;
 193         }
 194         p = map->nextpage++;
 195         p->page = alloc_page(GFP_KERNEL);
 196         p->sector = sector;
 197         p->next = *bucket;
 198         *bucket = p;
 199         return p;
 200 }
 201
 202 static int build_sector_map(struct bootcache_sector_map *map, u32 num_pages)
 203 {
 204         map->num_pages = num_pages;
 205         map->num_buckets = num_pages * 3 / 2;
 206         map->bucket = kzalloc(map->num_buckets * sizeof(*map->bucket),
 207                                 GFP_KERNEL);
 208         if (!map->bucket) {
 209                 DMERR("build_sector_maps kzalloc buckets");
 210                 return -ENOMEM;
 211         }
 212         map->pages = kzalloc(num_pages * sizeof(*map->pages), GFP_KERNEL);
 213         if (!map->pages) {
 214                 kfree(map->bucket);
 215                 DMERR("build_sector_maps kzalloc pages");
 216                 return -ENOMEM;
 217         }
 218         map->nextpage = map->pages;
 219         return 0;
 220 }
 221
 222 static void bootcache_free_sector_map(struct bootcache_sector_map *map)
 223 {
 224         struct bootcache_page *p;
 225
 226         for (p = map->pages; p < map->nextpage; p++)
 227                 if (p->page)
 228                         __free_pages(p->page, 0);
 229         kfree(map->pages);
 230         kfree(map->bucket);
 231         map->pages = NULL;
 232         map->bucket = NULL;
 233         map->nextpage = 0;
 234 }
 235
 236 static int bootcache_create_bin_file(struct bootcache *cache,
 237         struct bin_attribute *attr, char *name, ssize_t size,
 238         ssize_t (*read)(struct file *, struct kobject *,
 239                         struct bin_attribute *, char *, loff_t, size_t),
 240         ssize_t (*write)(struct file *, struct kobject *,
 241                         struct bin_attribute *, char *, loff_t, size_t))
 242 {
 243         int rc = 0;
 244
 245         if (attr->attr.name)
 246                 return -EEXIST;
 247         attr->attr.name = name;
 248         attr->attr.mode = write ? 0644 : 0444;
 249         attr->size = size;
 250         attr->read = read;
 251         attr->write = write;
 252
 253         rc = sysfs_create_bin_file(dm_kobject(dm_table_get_md(
 254                                         cache->ti->table)), attr);
 255         if (rc)
 256                 DMERR("sysfs_create_bin_file %s: %d", name, rc);
 257         return rc;
 258 }
 259
 260 /*
 261  * bootcache_remove_bin_file uses the file name as flag
 262  * to determine if the sysfs file has been created.
 263  */
 264 static void bootcache_remove_bin_file(struct bootcache *cache,
 265         struct bin_attribute *attr)
 266 {
 267         if (attr->attr.name) {
 268                 sysfs_remove_bin_file(dm_kobject(dm_table_get_md(
 269                                         cache->ti->table)), attr);
 270                 attr->attr.name = NULL;
 271         }
 272 }
 273
 274 /*
 275  * bootcache_remove_all_files removes all the sysfs files
 276  * that have been created and only the ones that have been
 277  * craeted.
 278  */
 279 static void bootcache_remove_all_files(struct bootcache *cache)
 280 {
 281         bootcache_remove_bin_file(cache,  &cache->blocktrace);
 282         bootcache_remove_bin_file(cache,  &cache->header);
 283         bootcache_remove_bin_file(cache,  &cache->free);
 284         bootcache_remove_bin_file(cache,  &cache->valid);
 285 }
 286
 287 static void bootcache_free_resources(struct kref *kref)
 288 {
 289         struct bootcache *cache = container_of(kref, struct bootcache,
 290                                                 kref);
 291         /* Will hang if we try to remove cache->free here */
 292         bootcache_remove_bin_file(cache,  &cache->blocktrace);
 293         bootcache_remove_bin_file(cache,  &cache->header);
 294         bootcache_remove_bin_file(cache,  &cache->valid);
 295         bootcache_free_sector_map(&cache->sectors);
 296         kfree(cache->trace);
 297         cache->trace  = NULL;
 298 }
 299
 300 /*
 301  * bootcache_get_ino returns the inode number of the bio if it has one.
 302  * If not, it returns 0, an illegal inode number.
 303  * When the bio is sent down for I/O, these fields don't change
 304  * while the I/O is pending.
 305  */
 306 static unsigned long bootcache_get_ino(struct bio *bio)
 307 {
 308         if (!bio)
 309                 return 0;
 310         if (!bio->bi_io_vec)
 311                 return 0;
 312         if (!bio->bi_io_vec->bv_page)
 313                 return 0;
 314         if (!bio->bi_io_vec->bv_page->mapping)
 315                 return 0;
 316         if (!bio->bi_io_vec->bv_page->mapping->host)
 317                 return 0;
 318         return bio->bi_io_vec->bv_page->mapping->host->i_ino;
 319 }
 320
 321 static void bootcache_record(struct bootcache *cache, struct bio *bio)
 322 {
 323         u64 sector = bio->bi_sector;
 324         u64 count = to_sector(bio->bi_size);
 325         struct bootcache_trace *tr;
 326
 327         if (!cache->trace)
 328                 return;
 329         spin_lock(&cache->trace_lock);
 330         if (cache->trace_next < cache->args.max_trace) {
 331                 tr = &cache->trace[cache->trace_next];
 332                 tr->sector = sector;
 333                 tr->count = count;
 334                 tr->ino = bootcache_get_ino(bio);
 335                 ++cache->trace_next;
 336         }
 337         spin_unlock(&cache->trace_lock);
 338 }
 339
 340 static bool is_in_cache(struct bootcache *cache, struct bio *bio)
 341 {
 342         u64 sector = bio->bi_sector;
 343         u32 count = bytes_to_pages(bio->bi_size);
 344         u32 i;
 345
 346         for (i = 0; i < count; i++, sector += SECTORS_PER_PAGE) {
 347                 if (!bootcache_get_chunk(&cache->sectors, sector))
 348                         return 0;
 349         }
 350         ++cache->stats.num_hits;
 351         return 1;
 352 }
 353
 354 static void bootcache_read_from_cache(struct bootcache *cache, struct bio *bio)
 355 {
 356         struct bootcache_page *bp;
 357         u64 sector = bio->bi_sector;
 358         u32 count = bytes_to_pages(bio->bi_size);
 359         u8 *dst;
 360         u8 *src;
 361         u32 i;
 362
 363         for (i = 0; i < count; i++, sector += SECTORS_PER_PAGE) {
 364                 bp = bootcache_get_chunk(&cache->sectors, sector);
 365                 if (!bp) {
 366                         /*
 367                          * Should have found it because we just
 368                          * looked for it before calling this code
 369                          */
 370                         DMCRIT("Didn't find block %llx", sector);
 371                         BUG();
 372                 }
 373                 dst = kmap_atomic(bio_iovec_idx(bio, i)->bv_page);
 374                 src = kmap_atomic(bp->page);
 375                 memcpy(dst, src, PAGE_SIZE);
 376                 kunmap_atomic(src);
 377                 kunmap_atomic(dst);
 378         }
 379         set_bit(BIO_UPTODATE, &bio->bi_flags);
 380         bio->bi_end_io(bio, 0);
 381 }
 382
 383 static void bootcache_read(struct bootcache *cache, struct bio *bio)
 384 {
 385         int state;
 386
 387         bio->bi_bdev = cache->dev->bdev;
 388         /* Only record reads below the given size */
 389         if ((atomic_read(&cache->state) == BC_BYPASS) ||
 390                 (to_sector(bio->bi_size) > cache->args.size_limit)) {
 391                 generic_make_request(bio);
 392                 return;
 393         }
 394         kref_get(&cache->kref);
 395 try_again:
 396         state = atomic_read(&cache->state);
 397         switch (state) {
 398         case BC_INIT:
 399                 wait_for_completion(&cache->init_complete);
 400                 goto try_again;
 401         case BC_TRACING:
 402                 bootcache_record(cache, bio);
 403                 generic_make_request(bio);
 404                 break;
 405         case BC_FILLING:
 406                 ++cache->stats.overlapped;
 407                 /* FALLTHRU */
 408         case BC_FILLED:
 409                 if (is_in_cache(cache, bio))
 410                         bootcache_read_from_cache(cache, bio);
 411                 else
 412                         generic_make_request(bio);
 413                 break;
 414         case BC_BYPASS:
 415                 generic_make_request(bio);
 416                 break;
 417         default:
 418                 DMCRIT("unknown state %d", state);
 419                 BUG();
 420                 break;
 421         }
 422         ++cache->stats.num_requests;
 423         if (cache->stats.num_requests % 1000 == 0) {
 424                 DMINFO("hits = %u / %u",
 425                         cache->stats.num_hits,
 426                         cache->stats.num_requests);
 427         }
 428         kref_put(&cache->kref, bootcache_free_resources);
 429 }
 430
 431 static ssize_t valid_read(struct file *file, struct kobject *kobp,
 432                                 struct bin_attribute *bin_attr, char *buf,
 433                                 loff_t pos, size_t count)
 434 {
 435         struct bootcache *cache = container_of(bin_attr, struct bootcache,
 436                                                 valid);
 437
 438         if (pos > 0 || count == 0)
 439                 return 0;
 440         buf[0] = cache->is_valid ? '1' : '0';
 441         return 1;
 442 }
 443
 444 static ssize_t free_read(struct file *file, struct kobject *kobp,
 445                                 struct bin_attribute *bin_attr, char *buf,
 446                                 loff_t pos, size_t count)
 447 {
 448         struct bootcache *cache = container_of(bin_attr, struct bootcache,
 449                                                 free);
 450
 451         if (pos > 0 || count == 0)
 452                 return 0;
 453         buf[0] = cache->is_free ? '1' : '0';
 454         return 1;
 455 }
 456
 457 static ssize_t free_write(struct file *file, struct kobject *kobp,
 458                                 struct bin_attribute *bin_attr, char *buf,
 459                                 loff_t pos, size_t count)
 460 {
 461         struct bootcache *cache = container_of(bin_attr, struct bootcache,
 462                                                 free);
 463         ssize_t err = 0;
 464
 465         mutex_lock(&cache->cache_lock);
 466         if (cache->is_free) {
 467                 err = 0;
 468                 goto exit;
 469         }
 470         atomic_set(&cache->state, BC_BYPASS);
 471         /*
 472          * Once BC_BYPASS is set, the system
 473          * should drain quickly.
 474          */
 475         kref_put(&cache->kref, bootcache_free_resources);
 476         cache->is_free = 1;
 477         /* Tell caller we wrote everything */
 478         err = count;
 479 exit:
 480         mutex_unlock(&cache->cache_lock);
 481         return err;
 482 }
 483
 484 static ssize_t header_read(struct file *file, struct kobject *kobp,
 485                                 struct bin_attribute *bin_attr, char *buf,
 486                                 loff_t pos, size_t count)
 487 {
 488         struct bootcache *cache = container_of(bin_attr, struct bootcache,
 489                                                 header);
 490
 491         return memory_read_from_buffer(buf, count, &pos, &cache->hdr,
 492                                         sizeof(cache->hdr));
 493 }
 494
 495 static ssize_t blocktrace_read(struct file *file, struct kobject *kobp,
 496                                 struct bin_attribute *bin_attr, char *buf,
 497                                 loff_t pos, size_t count)
 498 {
 499         struct bootcache *cache = container_of(bin_attr, struct bootcache,
 500                                                 blocktrace);
 501         char *data;
 502         size_t next, size;
 503         ssize_t err = 0;
 504
 505         kref_get(&cache->kref);
 506         if (atomic_read(&cache->state) != BC_TRACING) {
 507                 err = -ENODEV;
 508                 goto exit;
 509         }
 510         data = (char *)cache->trace;
 511
 512         spin_lock(&cache->trace_lock);
 513         next = cache->trace_next;
 514         spin_unlock(&cache->trace_lock);
 515
 516         size = next * sizeof(struct bootcache_trace);
 517
 518         err = memory_read_from_buffer(buf, count, &pos, data, size);
 519 exit:
 520         kref_put(&cache->kref, bootcache_free_resources);
 521         return err;
 522 }
 523
 524 static int bootcache_init_sysfs(struct bootcache *cache, struct dm_target *ti)
 525 {
 526         int rc;
 527
 528         rc = bootcache_create_bin_file(cache, &cache->valid, "valid",
 529                                         3, valid_read, NULL);
 530         if (rc)
 531                 goto error;
 532         rc = bootcache_create_bin_file(cache, &cache->free, "free",
 533                                         3, free_read, free_write);
 534         if (rc)
 535                 goto error;
 536         rc = bootcache_create_bin_file(cache, &cache->header, "header",
 537                                         sizeof(cache->hdr), header_read, NULL);
 538         if (rc)
 539                 goto error;
 540         rc = bootcache_create_bin_file(cache, &cache->blocktrace, "blocktrace",
 541                         cache->args.max_trace * sizeof(struct bootcache_trace),
 542                         blocktrace_read, NULL);
 543         if (rc)
 544                 goto error;
 545         return rc;
 546 error:
 547         bootcache_remove_all_files(cache);
 548         return rc;
 549 }
 550
 551 static void bootcache_read_sectors_end(struct bio *bio, int error)
 552 {
 553         struct bootcache_waiter *waiter = bio->bi_private;
 554
 555         if (unlikely(error)) {
 556                 waiter->error = error;
 557                 DMERR("Error occurred in bootcache_read_sectors:"
 558                         " %d (%llx, %x)",
 559                         error, (u64)bio->bi_sector, bio->bi_size);
 560         }
 561         complete(&waiter->completion);
 562 }
 563
 564 static int bootcache_read_sectors(struct bootcache *cache)
 565 {
 566         struct bootcache_waiter waiter;
 567         struct bio *bio;
 568         struct bootcache_page *p;
 569         struct bootcache_page *start_page;
 570         struct bio_vec *bvec;
 571         sector_t sector = cache->args.cache_start + cache->hdr.sectors_meta +
 572                                 SECTORS_PER_PAGE;
 573         u32 max_io = cache->max_io;
 574         u32 numpages = cache->sectors.num_pages;
 575         u32 chunks_to_read = (numpages + max_io - 1) / max_io;
 576         int i;
 577         int j;
 578         int rc = 0;
 579
 580         p = cache->sectors.pages;
 581         for (i = 0; i < chunks_to_read; i++) {
 582                 bio = bio_alloc_bioset(GFP_KERNEL, max_io, cache->bio_set);
 583                 if (unlikely(!bio)) {
 584                         DMERR("Out of memory bio_alloc_bioset");
 585                         return -ENOMEM;
 586                 }
 587                 bio->bi_private = &waiter;
 588                 bio->bi_destructor = bootcache_bio_destructor;
 589                 bio->bi_idx = 0;
 590                 bio->bi_bdev = cache->dev->bdev;
 591                 bio->bi_end_io = bootcache_read_sectors_end;
 592                 bio->bi_rw = 0;
 593                 bio->bi_sector = sector;
 594                 bvec = bio->bi_io_vec;
 595                 start_page = p;
 596                 for (j = 0; j < max_io; j++, bvec++, p++) {
 597                         if (p == cache->sectors.nextpage)
 598                                 break;
 599                         bvec->bv_page = p->page;
 600                         bvec->bv_offset = 0;
 601                         bvec->bv_len = PAGE_SIZE;
 602                 }
 603                 bio->bi_size = j * PAGE_SIZE;
 604                 bio->bi_vcnt = j;
 605
 606                 init_completion(&waiter.completion);
 607                 waiter.error = 0;
 608                 generic_make_request(bio);
 609                 wait_for_completion(&waiter.completion);
 610                 if (waiter.error) {
 611                         rc = waiter.error;
 612                         bio->bi_private = cache;
 613                         bio_put(bio);
 614                         break;
 615                 }
 616                 p = start_page;
 617                 for (j = 0; j < max_io; j++, p++) {
 618                         if (p == cache->sectors.nextpage)
 619                                 break;
 620                         p->is_filled = 1;
 621                 }
 622                 sector += pages_to_sectors(j);
 623                 bio->bi_private = cache;
 624                 bio_put(bio);
 625         }
 626         atomic_set(&cache->state, BC_FILLED);
 627         return rc;
 628 }
 629
 630 static void bootcache_dev_read_end(struct bio *bio, int error)
 631 {
 632         struct bootcache_waiter *waiter = bio->bi_private;
 633
 634         if (unlikely(error)) {
 635                 waiter->error = error;
 636                 DMERR("Error occurred in bootcache_dev_read: %d (%llx, %x)",
 637                       error, (u64)bio->bi_sector, bio->bi_size);
 638         }
 639         complete(&waiter->completion);
 640 }
 641
 642 static int bootcache_dev_read(struct bootcache *cache, void *data,
 643                                 int len, u64 sector)
 644 {
 645         struct bootcache_waiter waiter;
 646         struct bio *bio;
 647         struct bio_vec *bvec;
 648         int pages_to_read = (len + PAGE_SIZE - 1) >> PAGE_SHIFT;
 649         int max_io = cache->max_io;
 650         int bytes_to_copy;
 651         int i;
 652         int rc = 0;
 653         int pages_read;
 654         u8 *dst = data;
 655         u8 *src;
 656
 657         pages_read = 0;
 658         while (len) {
 659                 if (pages_to_read < max_io)
 660                         max_io = pages_to_read;
 661                 bio = bio_alloc_bioset(GFP_KERNEL, max_io, cache->bio_set);
 662                 if (unlikely(!bio)) {
 663                         DMERR("Out of memory bio_alloc_bioset");
 664                         return -ENOMEM;
 665                 }
 666                 bvec = bio->bi_io_vec;
 667                 for (i = 0; i < max_io; i++, bvec++)
 668                         bvec->bv_page = alloc_page(GFP_KERNEL);
 669                 bio->bi_private = &waiter;
 670                 bio->bi_destructor = bootcache_bio_destructor;
 671                 bio->bi_idx = 0;
 672                 bio->bi_bdev = cache->dev->bdev;
 673                 bio->bi_end_io = bootcache_dev_read_end;
 674                 bio->bi_rw = 0;
 675                 bio->bi_sector = sector;
 676                 bvec = bio->bi_io_vec;
 677                 for (i = 0; i < max_io; i++, bvec++) {
 678                         bvec->bv_offset = 0;
 679                         bvec->bv_len = PAGE_SIZE;
 680                 }
 681                 pages_to_read -= max_io;
 682                 bio->bi_size = max_io * PAGE_SIZE;
 683                 bio->bi_vcnt = max_io;
 684
 685                 init_completion(&waiter.completion);
 686                 waiter.error = 0;
 687                 generic_make_request(bio);
 688                 wait_for_completion(&waiter.completion);
 689                 if (waiter.error) {
 690                         rc = waiter.error;
 691                         goto error;
 692                 }
 693                 for (i = 0; i < max_io; i++) {
 694                         bytes_to_copy = min(len, (int)PAGE_SIZE);
 695                         src = kmap_atomic(bio_iovec_idx(bio, i)->bv_page);
 696                         memcpy(dst, src, bytes_to_copy);
 697                         kunmap_atomic(src);
 698                         len -= bytes_to_copy;
 699                         if (!len)
 700                                 break;
 701                         dst += bytes_to_copy;
 702                 }
 703                 sector += pages_to_sectors(max_io);
 704                 bvec = bio->bi_io_vec;
 705                 for (i = 0; i < max_io; i++, bvec++)
 706                         __free_pages(bvec->bv_page, 0);
 707                 bio->bi_private = cache;
 708                 bio_put(bio);
 709         }
 710         return rc;
 711 error:
 712         bvec = bio->bi_io_vec;
 713         for (i = 0; i < max_io; i++, bvec++)
 714                 __free_pages(bvec->bv_page, 0);
 715         bio->bi_private = cache;
 716         bio_put(bio);
 717         return rc;
 718 }
 719
 720 static int is_valid_hdr(struct bootcache *cache, struct bootcache_hdr *hdr)
 721 {
 722         u64 max_sectors;
 723         u64 max_meta_sectors;
 724
 725         if (hdr->magic != BOOTCACHE_MAGIC)
 726                 return 0;
 727         if (hdr->version != BOOTCACHE_VERSION)
 728                 return 0;
 729         if (hdr->max_sectors != cache->hdr.max_sectors)
 730                 return 0;
 731         if (hdr->max_hw_sectors != cache->hdr.max_hw_sectors)
 732                 return 0;
 733         if (strncmp(hdr->date, __DATE__, strlen(__DATE__) + 1) != 0)
 734                 return 0;
 735         if (strncmp(hdr->time, __TIME__, strlen(__TIME__) + 1) != 0)
 736                 return 0;
 737         if (strncmp(hdr->signature, cache->hdr.signature,
 738                         sizeof(hdr->signature)) != 0)
 739                 return 0;
 740         /*
 741          * Check sanity:
 742          * Can't have any more meta sectors than it takes to map
 743          * the remaining parition space for bootcache.
 744          */
 745         max_sectors = to_sector(i_size_read(cache->dev->bdev->bd_inode))
 746                         - cache->args.cache_start;
 747         max_meta_sectors = to_sector(round_up(
 748                 sectors_to_pages(max_sectors) * sizeof(u64), SECTOR_SIZE));
 749         if (hdr->sectors_meta > max_meta_sectors) {
 750                 DMERR("too many meta sectors %lld", (u64)hdr->sectors_meta);
 751                 return 0;
 752         }
 753         if (hdr->sectors_data > max_sectors - hdr->sectors_meta - 1) {
 754                 DMERR("bootcache too big %lld", (u64)hdr->sectors_data);
 755                 return 0;
 756         }
 757         return 1;
 758 }
 759
 760 static int read_trace(struct bootcache *cache)
 761 {
 762         int size_trace;
 763         int rc;
 764         int i;
 765         int j;
 766         int sum = 0;
 767
 768         size_trace = sizeof(*cache->trace) * cache->hdr.num_trace_recs;
 769         cache->trace = kzalloc(size_trace, GFP_KERNEL);
 770         if (!cache->trace) {
 771                 DMERR("read_trace out of memory");
 772                 return -ENOMEM;
 773         }
 774         rc = bootcache_dev_read(cache, cache->trace, size_trace,
 775                         cache->hdr.sector + SECTORS_PER_PAGE);
 776         if (rc) {
 777                 DMERR("bootcache_dev_read trace %d", rc);
 778                 return rc;
 779         }
 780         for (i = 0; i < cache->hdr.num_trace_recs; i++) {
 781                 struct bootcache_trace *tr;
 782                 tr = &cache->trace[i];
 783                 for (j = 0; j < tr->count; j += SECTORS_PER_PAGE) {
 784                         bootcache_new_chunk(&cache->sectors, tr->sector + j);
 785                         ++sum;
 786                 }
 787         }
 788         return 0;
 789 }
 790
 791 /**
 792  * bootcache_start:
 793  *
 794  * Reads the bootcache header from disk, checks if it is valid
 795  * if valid:
 796  *   read the sector trace from disk
 797  *   build hash table for sector trace on page boundaries
 798  *   begin reading in sectors to be cached
 799  * else:
 800  *   setup to capture trace of sectors
 801  *
 802  * on error: by pass boot cache
 803  */
 804 static void bootcache_start(struct work_struct *work)
 805 {
 806         struct bootcache *cache = container_of(work, struct bootcache,
 807                                                 work.work);
 808         struct bootcache_hdr hdr;
 809         int rc;
 810
 811         rc = bootcache_dev_read(cache, &hdr, sizeof(hdr), cache->hdr.sector);
 812         if (rc) {
 813                 DMERR("bootcache_dev_read hdr %d", rc);
 814                 goto error;
 815         }
 816         if (is_valid_hdr(cache, &hdr)) {
 817                 cache->is_valid = 1;
 818                 memcpy(&cache->hdr, &hdr, sizeof(cache->hdr));
 819                 rc = build_sector_map(&cache->sectors,
 820                                 sectors_to_pages(cache->hdr.sectors_data));
 821                 if (rc)
 822                         goto error;
 823                 rc = read_trace(cache);
 824                 if (rc)
 825                         goto error;
 826                 atomic_set(&cache->state, BC_FILLING);
 827                 rc = bootcache_read_sectors(cache);
 828                 if (rc)
 829                         goto error;
 830         } else {
 831                 atomic_set(&cache->state, BC_TRACING);
 832                 cache->trace = kzalloc(sizeof(*cache->trace) *
 833                                         cache->args.max_trace, GFP_KERNEL);
 834                 if (!cache->trace) {
 835                         DMERR("cache->trace out of memory");
 836                         goto error;
 837                 }
 838         }
 839 exit:
 840         complete_all(&cache->init_complete);
 841         return;
 842 error:
 843         DMERR("error occured starting bootcache, setting to by pass mode");
 844         atomic_set(&cache->state, BC_BYPASS);
 845         cache->is_valid = 0;
 846         goto exit;
 847 }
 848
 849 /**
 850  * bootcache_max_io determines the maximum number of pages that can
 851  * be passed in one read request to the underlying device.
 852  * @cache:           the max_sectors and max_hw_sectors must
 853  *                   be filled in.
 854  * @proposed_max_io: maxium number of pages the caller wants
 855  *                   to read at a time.
 856  *
 857  * Returns maximum number of pages that can be read but
 858  * no more than proposed_max_io
 859  */
 860 static u32 bootcache_max_io(struct bootcache *cache, u32 proposed_max_io)
 861 {
 862         u32 max_sectors;
 863         u32 max_pages;
 864
 865         max_sectors = min(cache->hdr.max_sectors, cache->hdr.max_hw_sectors);
 866         max_pages = sectors_to_pages(max_sectors);
 867         if (proposed_max_io < max_pages)
 868                 max_pages = proposed_max_io;
 869         return max_pages;
 870 }
 871
 872 static void bootcache_init_hdr(struct bootcache_hdr *hdr, u64 cache_start,
 873                         struct block_device *bdev, const char *signature)
 874 {
 875         hdr->sector = cache_start;
 876         hdr->magic = BOOTCACHE_MAGIC;
 877         hdr->version = BOOTCACHE_VERSION;
 878         hdr->state = BC_INIT;
 879         hdr->alignment = PAGE_SIZE;
 880         hdr->max_hw_sectors = queue_max_hw_sectors(bdev_get_queue(bdev));
 881         hdr->max_sectors = queue_max_sectors(bdev_get_queue(bdev));
 882         strncpy(hdr->date, __DATE__, sizeof(hdr->date));
 883         strncpy(hdr->time, __TIME__, sizeof(hdr->time));
 884         strncpy(hdr->signature, signature, sizeof(hdr->signature));
 885 }
 886
 887 /**
 888  * match_dev_by_uuid - callback for finding a partition using its uuid
 889  * @dev:        device passed in by the caller
 890  * @uuid_data:  opaque pointer to a uuid packed by part_pack_uuid().
 891  *
 892  * Returns 1 if the device matches, and 0 otherwise.
 893  */
 894 static int match_dev_by_uuid(struct device *dev, void *uuid_data)
 895 {
 896         u8 *uuid = uuid_data;
 897         struct hd_struct *part = dev_to_part(dev);
 898
 899         if (!part->info)
 900                 goto no_match;
 901
 902         if (memcmp(uuid, part->info->uuid, sizeof(part->info->uuid)))
 903                 goto no_match;
 904
 905         return 1;
 906 no_match:
 907         return 0;
 908 }
 909
 910 /**
 911  * dm_get_device_by_uuid: claim a device using its UUID
 912  * @ti:                 current dm_target
 913  * @uuid_string:        36 byte UUID hex encoded
 914  *                      (xxxxxxxx-xxxx-xxxx-xxxx-xxxxxxxxxxxx)
 915  * @dev_start:          offset in sectors passed to dm_get_device
 916  * @dev_len:            length in sectors passed to dm_get_device
 917  * @dm_dev:             dm_dev to populate
 918  *
 919  * Wraps dm_get_device allowing it to use a unique partition id
 920  * to find a given partition on any drive. This code is based on
 921  * printk_all_partitions in that it walks all of the registered
 922  * block devices.
 923  *
 924  * N.B., uuid_string is not checked for safety just strlen().
 925  */
 926 static int dm_get_device_by_uuid(struct dm_target *ti, const char *uuid_str,
 927                              sector_t dev_start, sector_t dev_len,
 928                              struct dm_dev **dm_dev)
 929 {
 930         struct device *dev = NULL;
 931         dev_t devt = 0;
 932         char devt_buf[BDEVT_SIZE];
 933         u8 uuid[16];
 934         size_t uuid_length = strlen(uuid_str);
 935
 936         if (uuid_length < 36)
 937                 goto bad_uuid;
 938         /* Pack the requested UUID in the expected format. */
 939         part_pack_uuid(uuid_str, uuid);
 940
 941         dev = class_find_device(&block_class, NULL, uuid, &match_dev_by_uuid);
 942         if (!dev)
 943                 goto found_nothing;
 944
 945         devt = dev->devt;
 946         put_device(dev);
 947
 948         /* The caller may specify +/-%u after the UUID if they want a partition
 949          * before or after the one identified.
 950          */
 951         if (uuid_length > 36) {
 952                 unsigned int part_offset;
 953                 char sign;
 954                 unsigned minor = MINOR(devt);
 955                 if (sscanf(uuid_str + 36, "%c%u", &sign, &part_offset) == 2) {
 956                         if (sign == '+') {
 957                                 minor += part_offset;
 958                         } else if (sign == '-') {
 959                                 minor -= part_offset;
 960                         } else {
 961                                 DMWARN("Trailing characters after UUID: %s\n",
 962                                         uuid_str);
 963                         }
 964                         devt = MKDEV(MAJOR(devt), minor);
 965                 }
 966         }
 967
 968         /* Construct the dev name to pass to dm_get_device.  dm_get_device
 969          * doesn't support being passed a dev_t.
 970          */
 971         snprintf(devt_buf, sizeof(devt_buf), "%u:%u",
 972                 MAJOR(devt), MINOR(devt));
 973
 974         /* TODO(wad) to make this generic we could also pass in the mode. */
 975         if (!dm_get_device(ti, devt_buf, dm_table_get_mode(ti->table), dm_dev))
 976                 return 0;
 977
 978         ti->error = "Failed to acquire device";
 979         DMDEBUG("Failed to acquire discovered device %s", devt_buf);
 980         return -1;
 981 bad_uuid:
 982         ti->error = "Bad UUID";
 983         DMDEBUG("Supplied value '%s' is an invalid UUID", uuid_str);
 984         return -1;
 985 found_nothing:
 986         DMDEBUG("No matching partition for GUID: %s", uuid_str);
 987         ti->error = "No matching GUID";
 988         return -1;
 989 }
 990
 991 static int bootcache_get_device(
 992         struct dm_target *ti,
 993         const char *devname,
 994         sector_t dev_start,
 995         sector_t dev_len,
 996         struct dm_dev **dm_dev)
 997 {
 998         do {
 999                 /* Try the normal path first since if everything is ready, it
1000                  * will be the fastest.
1001                  */
1002                 if (!dm_get_device(ti, devname,
1003                                    dm_table_get_mode(ti->table), dm_dev))
1004                         return 0;
1005
1006                 /* Try the device by partition UUID */
1007                 if (!dm_get_device_by_uuid(ti, devname, dev_start, dev_len,
1008                                            dm_dev))
1009                         return 0;
1010
1011                 /* No need to be too aggressive since this is a slow path. */
1012                 msleep(500);
1013         } while (driver_probe_done() != 0 || *dm_dev == NULL);
1014         async_synchronize_full();
1015         return -1;
1016 }
1017
1018 /**
1019  * bootcache_ctr - Construct a boot cache
1020  * @ti:   Target being created
1021  * @argc: Number of elements in argv
1022  * @argv: Vector of arguments - All arguments are positional, this
1023  *              means that to set a particular argument, all of its
1024  *              predecessors must be present.
1025  *
1026  * Accepts the folowing parametes [defaults in brackets]:
1027  * @device:      Device being cached. The boot cache is alsoe stored here.
1028  * @cache_start: Sector start on the device for the boot cache.
1029  * @signature:   Signature to determine if cache is valid.
1030  * @size_limit:  In sectors, max size reads to include in cache [128]
1031  * @max_trace:   Number of entries in block trace made during boot [8192]
1032  * @max_pages:   Maximum number of pages to cache in memory [50000]
1033  *
1034  * Argument list:
1035  * [<dev> [<cache_start> [<sig> [<size_limit> [<max_trace> [<max_limit>]]]]]]
1036  *
1037  * Example:
1038  * 0f5dbd05-c063-a848-a296-b8b8c2c24b28+1 1741200 10e8...78 80 64000 60000
1039  */
1040 static int bootcache_ctr(struct dm_target *ti, unsigned argc, char **argv)
1041 {
1042         struct bootcache *cache = NULL;
1043         const char *signature = NULL;
1044         const char *device = NULL;
1045         u64 cache_start = 0;
1046         u64 max_pages = DEFAULT_MAX_PAGES;
1047         u64 size_limit = DEFAULT_SIZE_LIMIT;
1048         u64 max_trace  = DEFAULT_MAX_TRACE;
1049         int rc = 0;
1050
1051         if (argc > 0)
1052                 device = argv[0];
1053         if (argc > 1)
1054                 if (strict_strtoull(argv[1], 10, &cache_start)) {
1055                         ti->error = "Invalid cache_start";
1056                         return -EINVAL;
1057                 }
1058         if (argc > 2)
1059                 signature = argv[2];
1060         if (argc > 3)
1061                 if (strict_strtoull(argv[3], 10, &size_limit)) {
1062                         ti->error = "Invalid size_limit";
1063                         return -EINVAL;
1064                 }
1065         if (argc > 4)
1066                 if (strict_strtoull(argv[4], 10, &max_trace)) {
1067                         ti->error = "Invalid max_trace";
1068                         return -EINVAL;
1069                 }
1070         if (argc > 5)
1071                 if (strict_strtoull(argv[5], 10, &max_pages)) {
1072                         ti->error = "Invalid max_pages";
1073                         return -EINVAL;
1074                 }
1075
1076 #define NEEDARG(n) \
1077         if (!(n)) { \
1078                 ti->error = "Missing argument: " #n; \
1079                 return -EINVAL; \
1080         }
1081
1082         NEEDARG(device);
1083         NEEDARG(signature);
1084         NEEDARG(cache_start);
1085
1086 #undef NEEDARG
1087         if ((dm_table_get_mode(ti->table) & DEV_MODE) != DEV_MODE) {
1088                 ti->error = "Must be created read only.";
1089                 return -EINVAL;
1090         }
1091
1092         cache = kzalloc(sizeof(*cache), GFP_KERNEL);
1093         if (!cache)
1094                 goto bad_cache;
1095         init_completion(&cache->init_complete);
1096         cache->ti = ti;
1097
1098         strlcpy(cache->args.device, device, sizeof(cache->args.device));
1099         strlcpy(cache->args.signature, signature,
1100                 sizeof(cache->args.signature));
1101         cache->args.cache_start = cache_start;
1102         cache->args.max_pages = max_pages;
1103         cache->args.size_limit = size_limit;
1104         if (max_trace > MAX_TRACE) {
1105                 DMWARN("max_trace too large %llu, setting to %d\n",
1106                         max_trace, MAX_TRACE);
1107                 max_trace = MAX_TRACE;
1108         }
1109         cache->args.max_trace = max_trace;
1110
1111         cache->begin = ti->begin;
1112         cache->len   = ti->len;
1113
1114         atomic_set(&cache->state, BC_INIT);
1115         kref_init(&cache->kref);
1116         mutex_init(&cache->cache_lock);
1117         spin_lock_init(&cache->trace_lock);
1118
1119         /* For the name, use the device default with / changed to _ */
1120         cache->name = dm_disk(dm_table_get_md(ti->table))->disk_name;
1121
1122         if (bootcache_init_sysfs(cache, ti))
1123                 goto bad_sysfs;
1124
1125         rc = bootcache_get_device(ti, device,
1126                 ti->begin, ti->len, &cache->dev);
1127         if (rc) {
1128                 DMERR("Failed to acquire device '%s': %d", device, rc);
1129                 ti->error = "Device lookup failed";
1130                 goto bad_dev;
1131         }
1132
1133         bootcache_init_hdr(&cache->hdr, cache_start,
1134                                 cache->dev->bdev, signature);
1135         cache->max_io = bootcache_max_io(cache, BIO_MAX_PAGES);
1136
1137         /* Allocate the bioset used for request padding */
1138         cache->bio_set = bioset_create(cache->max_io * 4, 0);
1139         if (!cache->bio_set) {
1140                 ti->error = "Cannot allocate verity bioset";
1141                 goto bad_bio_set;
1142         }
1143
1144         ti->num_flush_requests = 1;
1145         ti->private = cache;
1146
1147         {
1148                 char vdev[BDEVNAME_SIZE];
1149                 bdevname(cache->dev->bdev, vdev);
1150                 DMINFO("dev:%s", vdev);
1151         }
1152         INIT_WORK(&cache->work.work, bootcache_start);
1153         schedule_work(&cache->work.work);
1154
1155         DMINFO("cache:%p", cache);
1156         return 0;
1157
1158 bad_bio_set:
1159         dm_put_device(ti, cache->dev);
1160 bad_dev:
1161         bootcache_remove_all_files(cache);
1162 bad_sysfs:
1163         kfree(cache);   /* hash is not secret so no need to zero */
1164 bad_cache:
1165         return -EINVAL;
1166 }
1167
1168 static int bootcache_status(struct dm_target *ti, status_type_t type,
1169                                 char *result, uint maxlen)
1170 {
1171         struct bootcache *cache = (struct bootcache *) ti->private;
1172         uint sz = 0;
1173         char vdev[BDEVNAME_SIZE];
1174
1175         switch (type) {
1176         case STATUSTYPE_INFO:
1177                 DMEMIT("%u %u %u",
1178                        cache->stats.num_requests,
1179                        cache->stats.num_hits,
1180                        cache->stats.overlapped);
1181                 break;
1182
1183         case STATUSTYPE_TABLE:
1184                 bdevname(cache->dev->bdev, vdev);
1185                 DMEMIT("/dev/%s signature=%s cache_start=%llu max_pages=%llu"
1186                         " size_limit=%llu max_trace=%llu\n",
1187                         vdev,
1188                         cache->args.signature,
1189                         cache->args.cache_start,
1190                         cache->args.max_pages,
1191                         cache->args.size_limit,
1192                         cache->args.max_trace);
1193                 break;
1194         }
1195         return 0;
1196 }
1197
1198 static void bootcache_dtr(struct dm_target *ti)
1199 {
1200         /*
1201          * Doesn't have to clean-up the meta files in sysfs
1202          * because the device mapper has already done it.
1203          */
1204         struct bootcache *cache = (struct bootcache *)ti->private;
1205
1206         DMDEBUG("Destroying bio set");
1207         bioset_free(cache->bio_set);
1208
1209         DMDEBUG("Putting dev");
1210         dm_put_device(ti, cache->dev);
1211
1212         DMDEBUG("Destroying config");
1213         kfree(cache);
1214 }
1215
1216 static int bootcache_map(struct dm_target *ti, struct bio *bio,
1217                         union map_info *map_context)
1218 {
1219         bootcache_read(ti->private, bio);
1220         return DM_MAPIO_SUBMITTED;
1221 }
1222
1223 static int bootcache_merge(struct dm_target *ti, struct bvec_merge_data *bvm,
1224                                 struct bio_vec *biovec, int max_size)
1225 {
1226         struct bootcache *cache = ti->private;
1227         struct request_queue *q = bdev_get_queue(cache->dev->bdev);
1228
1229         if (!q->merge_bvec_fn)
1230                 return max_size;
1231
1232         bvm->bi_bdev = cache->dev->bdev;
1233         bvm->bi_sector = cache->begin +
1234                                 bvm->bi_sector - ti->begin;
1235
1236         /* Optionally, this could just return 0 to stick to single pages. */
1237         return min(max_size, q->merge_bvec_fn(q, bvm, biovec));
1238 }
1239
1240 static int bootcache_iterate_devices(struct dm_target *ti,
1241                                 iterate_devices_callout_fn fn, void *data)
1242 {
1243         struct bootcache *cache = ti->private;
1244
1245         return fn(ti, cache->dev, cache->begin, ti->len, data);
1246 }
1247
1248 static void bootcache_io_hints(struct dm_target *ti,
1249                             struct queue_limits *limits)
1250 {
1251         limits->logical_block_size = PAGE_SIZE;
1252         limits->physical_block_size = PAGE_SIZE;
1253         blk_limits_io_min(limits, PAGE_SIZE);
1254 }
1255
1256 static struct target_type bootcache_target = {
1257         .name   = "bootcache",
1258         .version = {0, 1, 0},
1259         .module = THIS_MODULE,
1260         .ctr    = bootcache_ctr,
1261         .dtr    = bootcache_dtr,
1262         .map    = bootcache_map,
1263         .merge  = bootcache_merge,
1264         .status = bootcache_status,
1265         .iterate_devices = bootcache_iterate_devices,
1266         .io_hints = bootcache_io_hints,
1267 };
1268
1269 static int __init dm_bootcache_init(void)
1270 {
1271         int rc = -ENOMEM;
1272
1273         rc = dm_register_target(&bootcache_target);
1274         if (rc < 0) {
1275                 DMERR("register failed %d", rc);
1276                 goto register_failed;
1277         }
1278
1279         DMINFO("version %u.%u.%u loaded", bootcache_target.version[0],
1280                bootcache_target.version[1], bootcache_target.version[2]);
1281
1282         return rc;
1283
1284 register_failed:
1285         return rc;
1286 }
1287
1288 static void __exit dm_bootcache_exit(void)
1289 {
1290         dm_unregister_target(&bootcache_target);
1291 }
1292
1293 module_init(dm_bootcache_init);
1294 module_exit(dm_bootcache_exit);
1295
1296 MODULE_AUTHOR("Paul Taysom <taysom@chromium.org>");
1297 MODULE_DESCRIPTION(DM_NAME "read cache");
1298 MODULE_LICENSE("GPL");