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