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         bio = bio_alloc_bioset(GFP_KERNEL, max_io, cache->bio_set);
 581         if (unlikely(!bio)) {
 582                 DMERR("Out of memory bio_alloc_bioset");
 583                 return -ENOMEM;
 584         }
 585         bio->bi_private = &waiter;
 586         bio->bi_destructor = bootcache_bio_destructor;
 587         p = cache->sectors.pages;
 588         for (i = 0; i < chunks_to_read; i++) {
 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                         break;
 613                 }
 614                 p = start_page;
 615                 for (j = 0; j < max_io; j++, p++) {
 616                         if (p == cache->sectors.nextpage)
 617                                 break;
 618                         p->is_filled = 1;
 619                 }
 620                 sector += pages_to_sectors(j);
 621         }
 622         bio->bi_private = cache;
 623         bio_put(bio);
 624         atomic_set(&cache->state, BC_FILLED);
 625         return rc;
 626 }
 627
 628 static void bootcache_dev_read_end(struct bio *bio, int error)
 629 {
 630         struct bootcache_waiter *waiter = bio->bi_private;
 631
 632         if (unlikely(error)) {
 633                 waiter->error = error;
 634                 DMERR("Error occurred in bootcache_dev_read: %d (%llx, %x)",
 635                       error, (u64)bio->bi_sector, bio->bi_size);
 636         }
 637         complete(&waiter->completion);
 638 }
 639
 640 static int bootcache_dev_read(struct bootcache *cache, void *data,
 641                                 int len, u64 sector)
 642 {
 643         struct bootcache_waiter waiter;
 644         struct bio *bio;
 645         struct bio_vec *bvec;
 646         int pages_to_read = (len + PAGE_SIZE - 1) >> PAGE_SHIFT;
 647         int max_io = cache->max_io;
 648         int num_pages;
 649         int bytes_to_copy;
 650         int i;
 651         int rc = 0;
 652         int pages_read;
 653         u8 *dst = data;
 654         u8 *src;
 655
 656         if (pages_to_read < max_io)
 657                 num_pages = pages_to_read;
 658         else
 659                 num_pages = max_io;
 660         bio = bio_alloc_bioset(GFP_KERNEL, num_pages, cache->bio_set);
 661         if (unlikely(!bio)) {
 662                 DMERR("Out of memory bio_alloc_bioset");
 663                 return -ENOMEM;
 664         }
 665         bvec = bio->bi_io_vec;
 666         for (i = 0; i < num_pages; i++, bvec++)
 667                 bvec->bv_page = alloc_page(GFP_KERNEL);
 668         bio->bi_private = &waiter;
 669         bio->bi_destructor = bootcache_bio_destructor;
 670         pages_read = 0;
 671         while (len) {
 672                 if (pages_to_read < max_io)
 673                         max_io = pages_to_read;
 674                 bio->bi_idx = 0;
 675                 bio->bi_bdev = cache->dev->bdev;
 676                 bio->bi_end_io = bootcache_dev_read_end;
 677                 bio->bi_rw = 0;
 678                 bio->bi_sector = sector;
 679                 bvec = bio->bi_io_vec;
 680                 for (i = 0; i < max_io; i++, bvec++) {
 681                         bvec->bv_offset = 0;
 682                         bvec->bv_len = PAGE_SIZE;
 683                 }
 684                 pages_to_read -= max_io;
 685                 bio->bi_size = max_io * PAGE_SIZE;
 686                 bio->bi_vcnt = max_io;
 687
 688                 init_completion(&waiter.completion);
 689                 waiter.error = 0;
 690                 generic_make_request(bio);
 691                 wait_for_completion(&waiter.completion);
 692                 if (waiter.error) {
 693                         rc = waiter.error;
 694                         goto exit;
 695                 }
 696                 for (i = 0; i < max_io; i++) {
 697                         bytes_to_copy = (len < PAGE_SIZE) ? len : PAGE_SIZE;
 698                         src = kmap_atomic(bio_iovec_idx(bio, i)->bv_page);
 699                         memcpy(dst, src, bytes_to_copy);
 700                         kunmap_atomic(src);
 701                         len -= bytes_to_copy;
 702                         if (!len)
 703                                 break;
 704                         dst += bytes_to_copy;
 705                 }
 706                 sector += pages_to_sectors(max_io);
 707         }
 708 exit:
 709         bvec = bio->bi_io_vec;
 710         for (i = 0; i < num_pages; i++, bvec++)
 711                 __free_pages(bvec->bv_page, 0);
 712         bio->bi_private = cache;
 713         bio_put(bio);
 714         return rc;
 715 }
 716
 717 static int is_valid_hdr(struct bootcache *cache, struct bootcache_hdr *hdr)
 718 {
 719         u64 max_sectors;
 720         u64 max_meta_sectors;
 721
 722         if (hdr->magic != BOOTCACHE_MAGIC)
 723                 return 0;
 724         if (hdr->version != BOOTCACHE_VERSION)
 725                 return 0;
 726         if (hdr->max_sectors != cache->hdr.max_sectors)
 727                 return 0;
 728         if (hdr->max_hw_sectors != cache->hdr.max_hw_sectors)
 729                 return 0;
 730         if (strncmp(hdr->date, __DATE__, strlen(__DATE__) + 1) != 0)
 731                 return 0;
 732         if (strncmp(hdr->time, __TIME__, strlen(__TIME__) + 1) != 0)
 733                 return 0;
 734         if (strncmp(hdr->signature, cache->hdr.signature,
 735                         sizeof(hdr->signature)) != 0)
 736                 return 0;
 737         /*
 738          * Check sanity:
 739          * Can't have any more meta sectors than it takes to map
 740          * the remaining parition space for bootcache.
 741          */
 742         max_sectors = to_sector(i_size_read(cache->dev->bdev->bd_inode))
 743                         - cache->args.cache_start;
 744         max_meta_sectors = to_sector(round_up(
 745                 sectors_to_pages(max_sectors) * sizeof(u64), SECTOR_SIZE));
 746         if (hdr->sectors_meta > max_meta_sectors) {
 747                 DMERR("too many meta sectors %lld", (u64)hdr->sectors_meta);
 748                 return 0;
 749         }
 750         if (hdr->sectors_data > max_sectors - hdr->sectors_meta - 1) {
 751                 DMERR("bootcache too big %lld", (u64)hdr->sectors_data);
 752                 return 0;
 753         }
 754         return 1;
 755 }
 756
 757 static int read_trace(struct bootcache *cache)
 758 {
 759         int size_trace;
 760         int rc;
 761         int i;
 762         int j;
 763         int sum = 0;
 764
 765         size_trace = sizeof(*cache->trace) * cache->hdr.num_trace_recs;
 766         cache->trace = kzalloc(size_trace, GFP_KERNEL);
 767         if (!cache->trace) {
 768                 DMERR("read_trace out of memory");
 769                 return -ENOMEM;
 770         }
 771         rc = bootcache_dev_read(cache, cache->trace, size_trace,
 772                         cache->hdr.sector + SECTORS_PER_PAGE);
 773         if (rc) {
 774                 DMERR("bootcache_dev_read trace %d", rc);
 775                 return rc;
 776         }
 777         for (i = 0; i < cache->hdr.num_trace_recs; i++) {
 778                 struct bootcache_trace *tr;
 779                 tr = &cache->trace[i];
 780                 for (j = 0; j < tr->count; j += SECTORS_PER_PAGE) {
 781                         bootcache_new_chunk(&cache->sectors, tr->sector + j);
 782                         ++sum;
 783                 }
 784         }
 785         return 0;
 786 }
 787
 788 /**
 789  * bootcache_start:
 790  *
 791  * Reads the bootcache header from disk, checks if it is valid
 792  * if valid:
 793  *   read the sector trace from disk
 794  *   build hash table for sector trace on page boundaries
 795  *   begin reading in sectors to be cached
 796  * else:
 797  *   setup to capture trace of sectors
 798  *
 799  * on error: by pass boot cache
 800  */
 801 static void bootcache_start(struct work_struct *work)
 802 {
 803         struct bootcache *cache = container_of(work, struct bootcache,
 804                                                 work.work);
 805         struct bootcache_hdr hdr;
 806         int rc;
 807
 808         rc = bootcache_dev_read(cache, &hdr, sizeof(hdr), cache->hdr.sector);
 809         if (rc) {
 810                 DMERR("bootcache_dev_read hdr %d", rc);
 811                 goto error;
 812         }
 813         if (is_valid_hdr(cache, &hdr)) {
 814                 cache->is_valid = 1;
 815                 memcpy(&cache->hdr, &hdr, sizeof(cache->hdr));
 816                 rc = build_sector_map(&cache->sectors,
 817                                 sectors_to_pages(cache->hdr.sectors_data));
 818                 if (rc)
 819                         goto error;
 820                 rc = read_trace(cache);
 821                 if (rc)
 822                         goto error;
 823                 atomic_set(&cache->state, BC_FILLING);
 824                 rc = bootcache_read_sectors(cache);
 825                 if (rc)
 826                         goto error;
 827         } else {
 828                 atomic_set(&cache->state, BC_TRACING);
 829                 cache->trace = kzalloc(sizeof(*cache->trace) *
 830                                         cache->args.max_trace, GFP_KERNEL);
 831                 if (!cache->trace) {
 832                         DMERR("cache->trace out of memory");
 833                         goto error;
 834                 }
 835         }
 836 exit:
 837         complete_all(&cache->init_complete);
 838         return;
 839 error:
 840         DMERR("error occured starting bootcache, setting to by pass mode");
 841         atomic_set(&cache->state, BC_BYPASS);
 842         cache->is_valid = 0;
 843         goto exit;
 844 }
 845
 846 /**
 847  * bootcache_max_io determines the maximum number of pages that can
 848  * be passed in one read request to the underlying device.
 849  * @cache:           the max_sectors and max_hw_sectors must
 850  *                   be filled in.
 851  * @proposed_max_io: maxium number of pages the caller wants
 852  *                   to read at a time.
 853  *
 854  * Returns maximum number of pages that can be read but
 855  * no more than proposed_max_io
 856  */
 857 static u32 bootcache_max_io(struct bootcache *cache, u32 proposed_max_io)
 858 {
 859         u32 max_sectors;
 860         u32 max_pages;
 861
 862         max_sectors = min(cache->hdr.max_sectors, cache->hdr.max_hw_sectors);
 863         max_pages = sectors_to_pages(max_sectors);
 864         if (proposed_max_io < max_pages)
 865                 max_pages = proposed_max_io;
 866         return max_pages;
 867 }
 868
 869 static void bootcache_init_hdr(struct bootcache_hdr *hdr, u64 cache_start,
 870                         struct block_device *bdev, const char *signature)
 871 {
 872         hdr->sector = cache_start;
 873         hdr->magic = BOOTCACHE_MAGIC;
 874         hdr->version = BOOTCACHE_VERSION;
 875         hdr->state = BC_INIT;
 876         hdr->alignment = PAGE_SIZE;
 877         hdr->max_hw_sectors = queue_max_hw_sectors(bdev_get_queue(bdev));
 878         hdr->max_sectors = queue_max_sectors(bdev_get_queue(bdev));
 879         strncpy(hdr->date, __DATE__, sizeof(hdr->date));
 880         strncpy(hdr->time, __TIME__, sizeof(hdr->time));
 881         strncpy(hdr->signature, signature, sizeof(hdr->signature));
 882 }
 883
 884 /**
 885  * match_dev_by_uuid - callback for finding a partition using its uuid
 886  * @dev:        device passed in by the caller
 887  * @uuid_data:  opaque pointer to a uuid packed by part_pack_uuid().
 888  *
 889  * Returns 1 if the device matches, and 0 otherwise.
 890  */
 891 static int match_dev_by_uuid(struct device *dev, void *uuid_data)
 892 {
 893         u8 *uuid = uuid_data;
 894         struct hd_struct *part = dev_to_part(dev);
 895
 896         if (!part->info)
 897                 goto no_match;
 898
 899         if (memcmp(uuid, part->info->uuid, sizeof(part->info->uuid)))
 900                 goto no_match;
 901
 902         return 1;
 903 no_match:
 904         return 0;
 905 }
 906
 907 /**
 908  * dm_get_device_by_uuid: claim a device using its UUID
 909  * @ti:                 current dm_target
 910  * @uuid_string:        36 byte UUID hex encoded
 911  *                      (xxxxxxxx-xxxx-xxxx-xxxx-xxxxxxxxxxxx)
 912  * @dev_start:          offset in sectors passed to dm_get_device
 913  * @dev_len:            length in sectors passed to dm_get_device
 914  * @dm_dev:             dm_dev to populate
 915  *
 916  * Wraps dm_get_device allowing it to use a unique partition id
 917  * to find a given partition on any drive. This code is based on
 918  * printk_all_partitions in that it walks all of the registered
 919  * block devices.
 920  *
 921  * N.B., uuid_string is not checked for safety just strlen().
 922  */
 923 static int dm_get_device_by_uuid(struct dm_target *ti, const char *uuid_str,
 924                              sector_t dev_start, sector_t dev_len,
 925                              struct dm_dev **dm_dev)
 926 {
 927         struct device *dev = NULL;
 928         dev_t devt = 0;
 929         char devt_buf[BDEVT_SIZE];
 930         u8 uuid[16];
 931         size_t uuid_length = strlen(uuid_str);
 932
 933         if (uuid_length < 36)
 934                 goto bad_uuid;
 935         /* Pack the requested UUID in the expected format. */
 936         part_pack_uuid(uuid_str, uuid);
 937
 938         dev = class_find_device(&block_class, NULL, uuid, &match_dev_by_uuid);
 939         if (!dev)
 940                 goto found_nothing;
 941
 942         devt = dev->devt;
 943         put_device(dev);
 944
 945         /* The caller may specify +/-%u after the UUID if they want a partition
 946          * before or after the one identified.
 947          */
 948         if (uuid_length > 36) {
 949                 unsigned int part_offset;
 950                 char sign;
 951                 unsigned minor = MINOR(devt);
 952                 if (sscanf(uuid_str + 36, "%c%u", &sign, &part_offset) == 2) {
 953                         if (sign == '+') {
 954                                 minor += part_offset;
 955                         } else if (sign == '-') {
 956                                 minor -= part_offset;
 957                         } else {
 958                                 DMWARN("Trailing characters after UUID: %s\n",
 959                                         uuid_str);
 960                         }
 961                         devt = MKDEV(MAJOR(devt), minor);
 962                 }
 963         }
 964
 965         /* Construct the dev name to pass to dm_get_device.  dm_get_device
 966          * doesn't support being passed a dev_t.
 967          */
 968         snprintf(devt_buf, sizeof(devt_buf), "%u:%u",
 969                 MAJOR(devt), MINOR(devt));
 970
 971         /* TODO(wad) to make this generic we could also pass in the mode. */
 972         if (!dm_get_device(ti, devt_buf, dm_table_get_mode(ti->table), dm_dev))
 973                 return 0;
 974
 975         ti->error = "Failed to acquire device";
 976         DMDEBUG("Failed to acquire discovered device %s", devt_buf);
 977         return -1;
 978 bad_uuid:
 979         ti->error = "Bad UUID";
 980         DMDEBUG("Supplied value '%s' is an invalid UUID", uuid_str);
 981         return -1;
 982 found_nothing:
 983         DMDEBUG("No matching partition for GUID: %s", uuid_str);
 984         ti->error = "No matching GUID";
 985         return -1;
 986 }
 987
 988 static int bootcache_get_device(
 989         struct dm_target *ti,
 990         const char *devname,
 991         sector_t dev_start,
 992         sector_t dev_len,
 993         struct dm_dev **dm_dev)
 994 {
 995         do {
 996                 /* Try the normal path first since if everything is ready, it
 997                  * will be the fastest.
 998                  */
 999                 if (!dm_get_device(ti, devname,
1000                                    dm_table_get_mode(ti->table), dm_dev))
1001                         return 0;
1002
1003                 /* Try the device by partition UUID */
1004                 if (!dm_get_device_by_uuid(ti, devname, dev_start, dev_len,
1005                                            dm_dev))
1006                         return 0;
1007
1008                 /* No need to be too aggressive since this is a slow path. */
1009                 msleep(500);
1010         } while (driver_probe_done() != 0 || *dm_dev == NULL);
1011         async_synchronize_full();
1012         return -1;
1013 }
1014
1015 /**
1016  * bootcache_ctr - Construct a boot cache
1017  * @ti:   Target being created
1018  * @argc: Number of elements in argv
1019  * @argv: Vector of arguments - All arguments are positional, this
1020  *              means that to set a particular argument, all of its
1021  *              predecessors must be present.
1022  *
1023  * Accepts the folowing parametes [defaults in brackets]:
1024  * @device:      Device being cached. The boot cache is alsoe stored here.
1025  * @cache_start: Sector start on the device for the boot cache.
1026  * @signature:   Signature to determine if cache is valid.
1027  * @size_limit:  In sectors, max size reads to include in cache [128]
1028  * @max_trace:   Number of entries in block trace made during boot [8192]
1029  * @max_pages:   Maximum number of pages to cache in memory [50000]
1030  *
1031  * Argument list:
1032  * [<dev> [<cache_start> [<sig> [<size_limit> [<max_trace> [<max_limit>]]]]]]
1033  *
1034  * Example:
1035  * 0f5dbd05-c063-a848-a296-b8b8c2c24b28+1 1741200 10e8...78 80 64000 60000
1036  */
1037 static int bootcache_ctr(struct dm_target *ti, unsigned argc, char **argv)
1038 {
1039         struct bootcache *cache = NULL;
1040         const char *signature = NULL;
1041         const char *device = NULL;
1042         u64 cache_start = 0;
1043         u64 max_pages = DEFAULT_MAX_PAGES;
1044         u64 size_limit = DEFAULT_SIZE_LIMIT;
1045         u64 max_trace  = DEFAULT_MAX_TRACE;
1046         int rc = 0;
1047
1048         if (argc > 0)
1049                 device = argv[0];
1050         if (argc > 1)
1051                 if (strict_strtoull(argv[1], 10, &cache_start)) {
1052                         ti->error = "Invalid cache_start";
1053                         return -EINVAL;
1054                 }
1055         if (argc > 2)
1056                 signature = argv[2];
1057         if (argc > 3)
1058                 if (strict_strtoull(argv[3], 10, &size_limit)) {
1059                         ti->error = "Invalid size_limit";
1060                         return -EINVAL;
1061                 }
1062         if (argc > 4)
1063                 if (strict_strtoull(argv[4], 10, &max_trace)) {
1064                         ti->error = "Invalid max_trace";
1065                         return -EINVAL;
1066                 }
1067         if (argc > 5)
1068                 if (strict_strtoull(argv[5], 10, &max_pages)) {
1069                         ti->error = "Invalid max_pages";
1070                         return -EINVAL;
1071                 }
1072
1073 #define NEEDARG(n) \
1074         if (!(n)) { \
1075                 ti->error = "Missing argument: " #n; \
1076                 return -EINVAL; \
1077         }
1078
1079         NEEDARG(device);
1080         NEEDARG(signature);
1081         NEEDARG(cache_start);
1082
1083 #undef NEEDARG
1084         if ((dm_table_get_mode(ti->table) & DEV_MODE) != DEV_MODE) {
1085                 ti->error = "Must be created read only.";
1086                 return -EINVAL;
1087         }
1088
1089         cache = kzalloc(sizeof(*cache), GFP_KERNEL);
1090         if (!cache)
1091                 goto bad_cache;
1092         init_completion(&cache->init_complete);
1093         cache->ti = ti;
1094
1095         strlcpy(cache->args.device, device, sizeof(cache->args.device));
1096         strlcpy(cache->args.signature, signature,
1097                 sizeof(cache->args.signature));
1098         cache->args.cache_start = cache_start;
1099         cache->args.max_pages = max_pages;
1100         cache->args.size_limit = size_limit;
1101         if (max_trace > MAX_TRACE) {
1102                 DMWARN("max_trace too large %llu, setting to %d\n",
1103                         max_trace, MAX_TRACE);
1104                 max_trace = MAX_TRACE;
1105         }
1106         cache->args.max_trace = max_trace;
1107
1108         cache->begin = ti->begin;
1109         cache->len   = ti->len;
1110
1111         atomic_set(&cache->state, BC_INIT);
1112         kref_init(&cache->kref);
1113         mutex_init(&cache->cache_lock);
1114         spin_lock_init(&cache->trace_lock);
1115
1116         /* For the name, use the device default with / changed to _ */
1117         cache->name = dm_disk(dm_table_get_md(ti->table))->disk_name;
1118
1119         if (bootcache_init_sysfs(cache, ti))
1120                 goto bad_sysfs;
1121
1122         rc = bootcache_get_device(ti, device,
1123                 ti->begin, ti->len, &cache->dev);
1124         if (rc) {
1125                 DMERR("Failed to acquire device '%s': %d", device, rc);
1126                 ti->error = "Device lookup failed";
1127                 goto bad_dev;
1128         }
1129
1130         bootcache_init_hdr(&cache->hdr, cache_start,
1131                                 cache->dev->bdev, signature);
1132         cache->max_io = bootcache_max_io(cache, BIO_MAX_PAGES);
1133
1134         /* Allocate the bioset used for request padding */
1135         cache->bio_set = bioset_create(cache->max_io * 4, 0);
1136         if (!cache->bio_set) {
1137                 ti->error = "Cannot allocate verity bioset";
1138                 goto bad_bio_set;
1139         }
1140
1141         ti->num_flush_requests = 1;
1142         ti->private = cache;
1143
1144         {
1145                 char vdev[BDEVNAME_SIZE];
1146                 bdevname(cache->dev->bdev, vdev);
1147                 DMINFO("dev:%s", vdev);
1148         }
1149         INIT_WORK(&cache->work.work, bootcache_start);
1150         schedule_work(&cache->work.work);
1151
1152         DMINFO("cache:%p", cache);
1153         return 0;
1154
1155 bad_bio_set:
1156         dm_put_device(ti, cache->dev);
1157 bad_dev:
1158         bootcache_remove_all_files(cache);
1159 bad_sysfs:
1160         kfree(cache);   /* hash is not secret so no need to zero */
1161 bad_cache:
1162         return -EINVAL;
1163 }
1164
1165 static int bootcache_status(struct dm_target *ti, status_type_t type,
1166                                 char *result, uint maxlen)
1167 {
1168         struct bootcache *cache = (struct bootcache *) ti->private;
1169         uint sz = 0;
1170         char vdev[BDEVNAME_SIZE];
1171
1172         switch (type) {
1173         case STATUSTYPE_INFO:
1174                 DMEMIT("%u %u %u",
1175                        cache->stats.num_requests,
1176                        cache->stats.num_hits,
1177                        cache->stats.overlapped);
1178                 break;
1179
1180         case STATUSTYPE_TABLE:
1181                 bdevname(cache->dev->bdev, vdev);
1182                 DMEMIT("/dev/%s signature=%s cache_start=%llu max_pages=%llu"
1183                         " size_limit=%llu max_trace=%llu\n",
1184                         vdev,
1185                         cache->args.signature,
1186                         cache->args.cache_start,
1187                         cache->args.max_pages,
1188                         cache->args.size_limit,
1189                         cache->args.max_trace);
1190                 break;
1191         }
1192         return 0;
1193 }
1194
1195 static void bootcache_dtr(struct dm_target *ti)
1196 {
1197         /*
1198          * Doesn't have to clean-up the meta files in sysfs
1199          * because the device mapper has already done it.
1200          */
1201         struct bootcache *cache = (struct bootcache *)ti->private;
1202
1203         DMDEBUG("Destroying bio set");
1204         bioset_free(cache->bio_set);
1205
1206         DMDEBUG("Putting dev");
1207         dm_put_device(ti, cache->dev);
1208
1209         DMDEBUG("Destroying config");
1210         kfree(cache);
1211 }
1212
1213 static int bootcache_map(struct dm_target *ti, struct bio *bio,
1214                         union map_info *map_context)
1215 {
1216         bootcache_read(ti->private, bio);
1217         return DM_MAPIO_SUBMITTED;
1218 }
1219
1220 static int bootcache_merge(struct dm_target *ti, struct bvec_merge_data *bvm,
1221                                 struct bio_vec *biovec, int max_size)
1222 {
1223         struct bootcache *cache = ti->private;
1224         struct request_queue *q = bdev_get_queue(cache->dev->bdev);
1225
1226         if (!q->merge_bvec_fn)
1227                 return max_size;
1228
1229         bvm->bi_bdev = cache->dev->bdev;
1230         bvm->bi_sector = cache->begin +
1231                                 bvm->bi_sector - ti->begin;
1232
1233         /* Optionally, this could just return 0 to stick to single pages. */
1234         return min(max_size, q->merge_bvec_fn(q, bvm, biovec));
1235 }
1236
1237 static int bootcache_iterate_devices(struct dm_target *ti,
1238                                 iterate_devices_callout_fn fn, void *data)
1239 {
1240         struct bootcache *cache = ti->private;
1241
1242         return fn(ti, cache->dev, cache->begin, ti->len, data);
1243 }
1244
1245 static void bootcache_io_hints(struct dm_target *ti,
1246                             struct queue_limits *limits)
1247 {
1248         limits->logical_block_size = PAGE_SIZE;
1249         limits->physical_block_size = PAGE_SIZE;
1250         blk_limits_io_min(limits, PAGE_SIZE);
1251 }
1252
1253 static struct target_type bootcache_target = {
1254         .name   = "bootcache",
1255         .version = {0, 1, 0},
1256         .module = THIS_MODULE,
1257         .ctr    = bootcache_ctr,
1258         .dtr    = bootcache_dtr,
1259         .map    = bootcache_map,
1260         .merge  = bootcache_merge,
1261         .status = bootcache_status,
1262         .iterate_devices = bootcache_iterate_devices,
1263         .io_hints = bootcache_io_hints,
1264 };
1265
1266 static int __init dm_bootcache_init(void)
1267 {
1268         int rc = -ENOMEM;
1269
1270         rc = dm_register_target(&bootcache_target);
1271         if (rc < 0) {
1272                 DMERR("register failed %d", rc);
1273                 goto register_failed;
1274         }
1275
1276         DMINFO("version %u.%u.%u loaded", bootcache_target.version[0],
1277                bootcache_target.version[1], bootcache_target.version[2]);
1278
1279         return rc;
1280
1281 register_failed:
1282         return rc;
1283 }
1284
1285 static void __exit dm_bootcache_exit(void)
1286 {
1287         dm_unregister_target(&bootcache_target);
1288 }
1289
1290 module_init(dm_bootcache_init);
1291 module_exit(dm_bootcache_exit);
1292
1293 MODULE_AUTHOR("Paul Taysom <taysom@chromium.org>");
1294 MODULE_DESCRIPTION(DM_NAME "read cache");
1295 MODULE_LICENSE("GPL");