drivers/md/dm-exception-store.c

   1 /*
   2  * dm-snapshot.c
   3  *
   4  * Copyright (C) 2001-2002 Sistina Software (UK) Limited.
   5  *
   6  * This file is released under the GPL.
   7  */
   8
   9 #include "dm.h"
  10 #include "dm-snap.h"
  11 #include "dm-io.h"
  12 #include "kcopyd.h"
  13
  14 #include <linux/mm.h>
  15 #include <linux/pagemap.h>
  16 #include <linux/vmalloc.h>
  17 #include <linux/slab.h>
  18
  19 #define DM_MSG_PREFIX "snapshots"
  20 #define DM_CHUNK_SIZE_DEFAULT_SECTORS 32        /* 16KB */
  21
  22 /*-----------------------------------------------------------------
  23  * Persistent snapshots, by persistent we mean that the snapshot
  24  * will survive a reboot.
  25  *---------------------------------------------------------------*/
  26
  27 /*
  28  * We need to store a record of which parts of the origin have
  29  * been copied to the snapshot device.  The snapshot code
  30  * requires that we copy exception chunks to chunk aligned areas
  31  * of the COW store.  It makes sense therefore, to store the
  32  * metadata in chunk size blocks.
  33  *
  34  * There is no backward or forward compatibility implemented,
  35  * snapshots with different disk versions than the kernel will
  36  * not be usable.  It is expected that "lvcreate" will blank out
  37  * the start of a fresh COW device before calling the snapshot
  38  * constructor.
  39  *
  40  * The first chunk of the COW device just contains the header.
  41  * After this there is a chunk filled with exception metadata,
  42  * followed by as many exception chunks as can fit in the
  43  * metadata areas.
  44  *
  45  * All on disk structures are in little-endian format.  The end
  46  * of the exceptions info is indicated by an exception with a
  47  * new_chunk of 0, which is invalid since it would point to the
  48  * header chunk.
  49  */
  50
  51 /*
  52  * Magic for persistent snapshots: "SnAp" - Feeble isn't it.
  53  */
  54 #define SNAP_MAGIC 0x70416e53
  55
  56 /*
  57  * The on-disk version of the metadata.
  58  */
  59 #define SNAPSHOT_DISK_VERSION 1
  60
  61 struct disk_header {
  62         uint32_t magic;
  63
  64         /*
  65          * Is this snapshot valid.  There is no way of recovering
  66          * an invalid snapshot.
  67          */
  68         uint32_t valid;
  69
  70         /*
  71          * Simple, incrementing version. no backward
  72          * compatibility.
  73          */
  74         uint32_t version;
  75
  76         /* In sectors */
  77         uint32_t chunk_size;
  78 };
  79
  80 struct disk_exception {
  81         uint64_t old_chunk;
  82         uint64_t new_chunk;
  83 };
  84
  85 struct commit_callback {
  86         void (*callback)(void *, int success);
  87         void *context;
  88 };
  89
  90 /*
  91  * The top level structure for a persistent exception store.
  92  */
  93 struct pstore {
  94         struct dm_snapshot *snap;       /* up pointer to my snapshot */
  95         int version;
  96         int valid;
  97         uint32_t exceptions_per_area;
  98
  99         /*
 100          * Now that we have an asynchronous kcopyd there is no
 101          * need for large chunk sizes, so it wont hurt to have a
 102          * whole chunks worth of metadata in memory at once.
 103          */
 104         void *area;
 105
 106         /*
 107          * Used to keep track of which metadata area the data in
 108          * 'chunk' refers to.
 109          */
 110         uint32_t current_area;
 111
 112         /*
 113          * The next free chunk for an exception.
 114          */
 115         uint32_t next_free;
 116
 117         /*
 118          * The index of next free exception in the current
 119          * metadata area.
 120          */
 121         uint32_t current_committed;
 122
 123         atomic_t pending_count;
 124         uint32_t callback_count;
 125         struct commit_callback *callbacks;
 126 };
 127
 128 static inline unsigned int sectors_to_pages(unsigned int sectors)
 129 {
 130         return sectors / (PAGE_SIZE >> 9);
 131 }
 132
 133 static int alloc_area(struct pstore *ps)
 134 {
 135         int r = -ENOMEM;
 136         size_t len;
 137
 138         len = ps->snap->chunk_size << SECTOR_SHIFT;
 139
 140         /*
 141          * Allocate the chunk_size block of memory that will hold
 142          * a single metadata area.
 143          */
 144         ps->area = vmalloc(len);
 145         if (!ps->area)
 146                 return r;
 147
 148         return 0;
 149 }
 150
 151 static void free_area(struct pstore *ps)
 152 {
 153         vfree(ps->area);
 154         ps->area = NULL;
 155 }
 156
 157 /*
 158  * Read or write a chunk aligned and sized block of data from a device.
 159  */
 160 static int chunk_io(struct pstore *ps, uint32_t chunk, int rw)
 161 {
 162         struct io_region where;
 163         unsigned long bits;
 164
 165         where.bdev = ps->snap->cow->bdev;
 166         where.sector = ps->snap->chunk_size * chunk;
 167         where.count = ps->snap->chunk_size;
 168
 169         return dm_io_sync_vm(1, &where, rw, ps->area, &bits);
 170 }
 171
 172 /*
 173  * Read or write a metadata area.  Remembering to skip the first
 174  * chunk which holds the header.
 175  */
 176 static int area_io(struct pstore *ps, uint32_t area, int rw)
 177 {
 178         int r;
 179         uint32_t chunk;
 180
 181         /* convert a metadata area index to a chunk index */
 182         chunk = 1 + ((ps->exceptions_per_area + 1) * area);
 183
 184         r = chunk_io(ps, chunk, rw);
 185         if (r)
 186                 return r;
 187
 188         ps->current_area = area;
 189         return 0;
 190 }
 191
 192 static int zero_area(struct pstore *ps, uint32_t area)
 193 {
 194         memset(ps->area, 0, ps->snap->chunk_size << SECTOR_SHIFT);
 195         return area_io(ps, area, WRITE);
 196 }
 197
 198 static int read_header(struct pstore *ps, int *new_snapshot)
 199 {
 200         int r;
 201         struct disk_header *dh;
 202         chunk_t chunk_size;
 203         int chunk_size_supplied = 1;
 204
 205         /*
 206          * Use default chunk size (or hardsect_size, if larger) if none supplied
 207          */
 208         if (!ps->snap->chunk_size) {
 209                 ps->snap->chunk_size = max(DM_CHUNK_SIZE_DEFAULT_SECTORS,
 210                     bdev_hardsect_size(ps->snap->cow->bdev) >> 9);
 211                 ps->snap->chunk_mask = ps->snap->chunk_size - 1;
 212                 ps->snap->chunk_shift = ffs(ps->snap->chunk_size) - 1;
 213                 chunk_size_supplied = 0;
 214         }
 215
 216         r = dm_io_get(sectors_to_pages(ps->snap->chunk_size));
 217         if (r)
 218                 return r;
 219
 220         r = alloc_area(ps);
 221         if (r)
 222                 goto bad1;
 223
 224         r = chunk_io(ps, 0, READ);
 225         if (r)
 226                 goto bad2;
 227
 228         dh = (struct disk_header *) ps->area;
 229
 230         if (le32_to_cpu(dh->magic) == 0) {
 231                 *new_snapshot = 1;
 232                 return 0;
 233         }
 234
 235         if (le32_to_cpu(dh->magic) != SNAP_MAGIC) {
 236                 DMWARN("Invalid or corrupt snapshot");
 237                 r = -ENXIO;
 238                 goto bad2;
 239         }
 240
 241         *new_snapshot = 0;
 242         ps->valid = le32_to_cpu(dh->valid);
 243         ps->version = le32_to_cpu(dh->version);
 244         chunk_size = le32_to_cpu(dh->chunk_size);
 245
 246         if (!chunk_size_supplied || ps->snap->chunk_size == chunk_size)
 247                 return 0;
 248
 249         DMWARN("chunk size %llu in device metadata overrides "
 250                "table chunk size of %llu.",
 251                (unsigned long long)chunk_size,
 252                (unsigned long long)ps->snap->chunk_size);
 253
 254         /* We had a bogus chunk_size. Fix stuff up. */
 255         dm_io_put(sectors_to_pages(ps->snap->chunk_size));
 256         free_area(ps);
 257
 258         ps->snap->chunk_size = chunk_size;
 259         ps->snap->chunk_mask = chunk_size - 1;
 260         ps->snap->chunk_shift = ffs(chunk_size) - 1;
 261
 262         r = dm_io_get(sectors_to_pages(chunk_size));
 263         if (r)
 264                 return r;
 265
 266         r = alloc_area(ps);
 267         if (r)
 268                 goto bad1;
 269
 270         return 0;
 271
 272 bad2:
 273         free_area(ps);
 274 bad1:
 275         dm_io_put(sectors_to_pages(ps->snap->chunk_size));
 276         return r;
 277 }
 278
 279 static int write_header(struct pstore *ps)
 280 {
 281         struct disk_header *dh;
 282
 283         memset(ps->area, 0, ps->snap->chunk_size << SECTOR_SHIFT);
 284
 285         dh = (struct disk_header *) ps->area;
 286         dh->magic = cpu_to_le32(SNAP_MAGIC);
 287         dh->valid = cpu_to_le32(ps->valid);
 288         dh->version = cpu_to_le32(ps->version);
 289         dh->chunk_size = cpu_to_le32(ps->snap->chunk_size);
 290
 291         return chunk_io(ps, 0, WRITE);
 292 }
 293
 294 /*
 295  * Access functions for the disk exceptions, these do the endian conversions.
 296  */
 297 static struct disk_exception *get_exception(struct pstore *ps, uint32_t index)
 298 {
 299         if (index >= ps->exceptions_per_area)
 300                 return NULL;
 301
 302         return ((struct disk_exception *) ps->area) + index;
 303 }
 304
 305 static int read_exception(struct pstore *ps,
 306                           uint32_t index, struct disk_exception *result)
 307 {
 308         struct disk_exception *e;
 309
 310         e = get_exception(ps, index);
 311         if (!e)
 312                 return -EINVAL;
 313
 314         /* copy it */
 315         result->old_chunk = le64_to_cpu(e->old_chunk);
 316         result->new_chunk = le64_to_cpu(e->new_chunk);
 317
 318         return 0;
 319 }
 320
 321 static int write_exception(struct pstore *ps,
 322                            uint32_t index, struct disk_exception *de)
 323 {
 324         struct disk_exception *e;
 325
 326         e = get_exception(ps, index);
 327         if (!e)
 328                 return -EINVAL;
 329
 330         /* copy it */
 331         e->old_chunk = cpu_to_le64(de->old_chunk);
 332         e->new_chunk = cpu_to_le64(de->new_chunk);
 333
 334         return 0;
 335 }
 336
 337 /*
 338  * Registers the exceptions that are present in the current area.
 339  * 'full' is filled in to indicate if the area has been
 340  * filled.
 341  */
 342 static int insert_exceptions(struct pstore *ps, int *full)
 343 {
 344         int r;
 345         unsigned int i;
 346         struct disk_exception de;
 347
 348         /* presume the area is full */
 349         *full = 1;
 350
 351         for (i = 0; i < ps->exceptions_per_area; i++) {
 352                 r = read_exception(ps, i, &de);
 353
 354                 if (r)
 355                         return r;
 356
 357                 /*
 358                  * If the new_chunk is pointing at the start of
 359                  * the COW device, where the first metadata area
 360                  * is we know that we've hit the end of the
 361                  * exceptions.  Therefore the area is not full.
 362                  */
 363                 if (de.new_chunk == 0LL) {
 364                         ps->current_committed = i;
 365                         *full = 0;
 366                         break;
 367                 }
 368
 369                 /*
 370                  * Keep track of the start of the free chunks.
 371                  */
 372                 if (ps->next_free <= de.new_chunk)
 373                         ps->next_free = de.new_chunk + 1;
 374
 375                 /*
 376                  * Otherwise we add the exception to the snapshot.
 377                  */
 378                 r = dm_add_exception(ps->snap, de.old_chunk, de.new_chunk);
 379                 if (r)
 380                         return r;
 381         }
 382
 383         return 0;
 384 }
 385
 386 static int read_exceptions(struct pstore *ps)
 387 {
 388         uint32_t area;
 389         int r, full = 1;
 390
 391         /*
 392          * Keeping reading chunks and inserting exceptions until
 393          * we find a partially full area.
 394          */
 395         for (area = 0; full; area++) {
 396                 r = area_io(ps, area, READ);
 397                 if (r)
 398                         return r;
 399
 400                 r = insert_exceptions(ps, &full);
 401                 if (r)
 402                         return r;
 403         }
 404
 405         return 0;
 406 }
 407
 408 static inline struct pstore *get_info(struct exception_store *store)
 409 {
 410         return (struct pstore *) store->context;
 411 }
 412
 413 static void persistent_fraction_full(struct exception_store *store,
 414                                      sector_t *numerator, sector_t *denominator)
 415 {
 416         *numerator = get_info(store)->next_free * store->snap->chunk_size;
 417         *denominator = get_dev_size(store->snap->cow->bdev);
 418 }
 419
 420 static void persistent_destroy(struct exception_store *store)
 421 {
 422         struct pstore *ps = get_info(store);
 423
 424         dm_io_put(sectors_to_pages(ps->snap->chunk_size));
 425         vfree(ps->callbacks);
 426         free_area(ps);
 427         kfree(ps);
 428 }
 429
 430 static int persistent_read_metadata(struct exception_store *store)
 431 {
 432         int r, new_snapshot;
 433         struct pstore *ps = get_info(store);
 434
 435         /*
 436          * Read the snapshot header.
 437          */
 438         r = read_header(ps, &new_snapshot);
 439         if (r)
 440                 return r;
 441
 442         /*
 443          * Now we know correct chunk_size, complete the initialisation.
 444          */
 445         ps->exceptions_per_area = (ps->snap->chunk_size << SECTOR_SHIFT) /
 446                                   sizeof(struct disk_exception);
 447         ps->callbacks = dm_vcalloc(ps->exceptions_per_area,
 448                         sizeof(*ps->callbacks));
 449         if (!ps->callbacks)
 450                 return -ENOMEM;
 451
 452         /*
 453          * Do we need to setup a new snapshot ?
 454          */
 455         if (new_snapshot) {
 456                 r = write_header(ps);
 457                 if (r) {
 458                         DMWARN("write_header failed");
 459                         return r;
 460                 }
 461
 462                 r = zero_area(ps, 0);
 463                 if (r) {
 464                         DMWARN("zero_area(0) failed");
 465                         return r;
 466                 }
 467
 468         } else {
 469                 /*
 470                  * Sanity checks.
 471                  */
 472                 if (!ps->valid) {
 473                         DMWARN("snapshot is marked invalid");
 474                         return -EINVAL;
 475                 }
 476
 477                 if (ps->version != SNAPSHOT_DISK_VERSION) {
 478                         DMWARN("unable to handle snapshot disk version %d",
 479                                ps->version);
 480                         return -EINVAL;
 481                 }
 482
 483                 /*
 484                  * Read the metadata.
 485                  */
 486                 r = read_exceptions(ps);
 487                 if (r)
 488                         return r;
 489         }
 490
 491         return 0;
 492 }
 493
 494 static int persistent_prepare(struct exception_store *store,
 495                               struct exception *e)
 496 {
 497         struct pstore *ps = get_info(store);
 498         uint32_t stride;
 499         sector_t size = get_dev_size(store->snap->cow->bdev);
 500
 501         /* Is there enough room ? */
 502         if (size < ((ps->next_free + 1) * store->snap->chunk_size))
 503                 return -ENOSPC;
 504
 505         e->new_chunk = ps->next_free;
 506
 507         /*
 508          * Move onto the next free pending, making sure to take
 509          * into account the location of the metadata chunks.
 510          */
 511         stride = (ps->exceptions_per_area + 1);
 512         if ((++ps->next_free % stride) == 1)
 513                 ps->next_free++;
 514
 515         atomic_inc(&ps->pending_count);
 516         return 0;
 517 }
 518
 519 static void persistent_commit(struct exception_store *store,
 520                               struct exception *e,
 521                               void (*callback) (void *, int success),
 522                               void *callback_context)
 523 {
 524         int r;
 525         unsigned int i;
 526         struct pstore *ps = get_info(store);
 527         struct disk_exception de;
 528         struct commit_callback *cb;
 529
 530         de.old_chunk = e->old_chunk;
 531         de.new_chunk = e->new_chunk;
 532         write_exception(ps, ps->current_committed++, &de);
 533
 534         /*
 535          * Add the callback to the back of the array.  This code
 536          * is the only place where the callback array is
 537          * manipulated, and we know that it will never be called
 538          * multiple times concurrently.
 539          */
 540         cb = ps->callbacks + ps->callback_count++;
 541         cb->callback = callback;
 542         cb->context = callback_context;
 543
 544         /*
 545          * If there are no more exceptions in flight, or we have
 546          * filled this metadata area we commit the exceptions to
 547          * disk.
 548          */
 549         if (atomic_dec_and_test(&ps->pending_count) ||
 550             (ps->current_committed == ps->exceptions_per_area)) {
 551                 r = area_io(ps, ps->current_area, WRITE);
 552                 if (r)
 553                         ps->valid = 0;
 554
 555                 for (i = 0; i < ps->callback_count; i++) {
 556                         cb = ps->callbacks + i;
 557                         cb->callback(cb->context, r == 0 ? 1 : 0);
 558                 }
 559
 560                 ps->callback_count = 0;
 561         }
 562
 563         /*
 564          * Have we completely filled the current area ?
 565          */
 566         if (ps->current_committed == ps->exceptions_per_area) {
 567                 ps->current_committed = 0;
 568                 r = zero_area(ps, ps->current_area + 1);
 569                 if (r)
 570                         ps->valid = 0;
 571         }
 572 }
 573
 574 static void persistent_drop(struct exception_store *store)
 575 {
 576         struct pstore *ps = get_info(store);
 577
 578         ps->valid = 0;
 579         if (write_header(ps))
 580                 DMWARN("write header failed");
 581 }
 582
 583 int dm_create_persistent(struct exception_store *store)
 584 {
 585         struct pstore *ps;
 586
 587         /* allocate the pstore */
 588         ps = kmalloc(sizeof(*ps), GFP_KERNEL);
 589         if (!ps)
 590                 return -ENOMEM;
 591
 592         ps->snap = store->snap;
 593         ps->valid = 1;
 594         ps->version = SNAPSHOT_DISK_VERSION;
 595         ps->area = NULL;
 596         ps->next_free = 2;      /* skipping the header and first area */
 597         ps->current_committed = 0;
 598
 599         ps->callback_count = 0;
 600         atomic_set(&ps->pending_count, 0);
 601         ps->callbacks = NULL;
 602
 603         store->destroy = persistent_destroy;
 604         store->read_metadata = persistent_read_metadata;
 605         store->prepare_exception = persistent_prepare;
 606         store->commit_exception = persistent_commit;
 607         store->drop_snapshot = persistent_drop;
 608         store->fraction_full = persistent_fraction_full;
 609         store->context = ps;
 610
 611         return 0;
 612 }
 613
 614 /*-----------------------------------------------------------------
 615  * Implementation of the store for non-persistent snapshots.
 616  *---------------------------------------------------------------*/
 617 struct transient_c {
 618         sector_t next_free;
 619 };
 620
 621 static void transient_destroy(struct exception_store *store)
 622 {
 623         kfree(store->context);
 624 }
 625
 626 static int transient_read_metadata(struct exception_store *store)
 627 {
 628         return 0;
 629 }
 630
 631 static int transient_prepare(struct exception_store *store, struct exception *e)
 632 {
 633         struct transient_c *tc = (struct transient_c *) store->context;
 634         sector_t size = get_dev_size(store->snap->cow->bdev);
 635
 636         if (size < (tc->next_free + store->snap->chunk_size))
 637                 return -1;
 638
 639         e->new_chunk = sector_to_chunk(store->snap, tc->next_free);
 640         tc->next_free += store->snap->chunk_size;
 641
 642         return 0;
 643 }
 644
 645 static void transient_commit(struct exception_store *store,
 646                       struct exception *e,
 647                       void (*callback) (void *, int success),
 648                       void *callback_context)
 649 {
 650         /* Just succeed */
 651         callback(callback_context, 1);
 652 }
 653
 654 static void transient_fraction_full(struct exception_store *store,
 655                                     sector_t *numerator, sector_t *denominator)
 656 {
 657         *numerator = ((struct transient_c *) store->context)->next_free;
 658         *denominator = get_dev_size(store->snap->cow->bdev);
 659 }
 660
 661 int dm_create_transient(struct exception_store *store)
 662 {
 663         struct transient_c *tc;
 664
 665         store->destroy = transient_destroy;
 666         store->read_metadata = transient_read_metadata;
 667         store->prepare_exception = transient_prepare;
 668         store->commit_exception = transient_commit;
 669         store->drop_snapshot = NULL;
 670         store->fraction_full = transient_fraction_full;
 671
 672         tc = kmalloc(sizeof(struct transient_c), GFP_KERNEL);
 673         if (!tc)
 674                 return -ENOMEM;
 675
 676         tc->next_free = 0;
 677         store->context = tc;
 678
 679         return 0;
 680 }