drivers/md/persistent-data/dm-space-map-metadata.c

   1 /*
   2  * Copyright (C) 2011 Red Hat, Inc.
   3  *
   4  * This file is released under the GPL.
   5  */
   6
   7 #include "dm-space-map.h"
   8 #include "dm-space-map-common.h"
   9 #include "dm-space-map-metadata.h"
  10
  11 #include <linux/list.h>
  12 #include <linux/slab.h>
  13 #include <linux/device-mapper.h>
  14
  15 #define DM_MSG_PREFIX "space map metadata"
  16
  17 /*----------------------------------------------------------------*/
  18
  19 /*
  20  * Space map interface.
  21  *
  22  * The low level disk format is written using the standard btree and
  23  * transaction manager.  This means that performing disk operations may
  24  * cause us to recurse into the space map in order to allocate new blocks.
  25  * For this reason we have a pool of pre-allocated blocks large enough to
  26  * service any metadata_ll_disk operation.
  27  */
  28
  29 /*
  30  * FIXME: we should calculate this based on the size of the device.
  31  * Only the metadata space map needs this functionality.
  32  */
  33 #define MAX_RECURSIVE_ALLOCATIONS 1024
  34
  35 enum block_op_type {
  36         BOP_INC,
  37         BOP_DEC
  38 };
  39
  40 struct block_op {
  41         enum block_op_type type;
  42         dm_block_t block;
  43 };
  44
  45 struct sm_metadata {
  46         struct dm_space_map sm;
  47
  48         struct ll_disk ll;
  49         struct ll_disk old_ll;
  50
  51         dm_block_t begin;
  52
  53         unsigned recursion_count;
  54         unsigned allocated_this_transaction;
  55         unsigned nr_uncommitted;
  56         struct block_op uncommitted[MAX_RECURSIVE_ALLOCATIONS];
  57 };
  58
  59 static int add_bop(struct sm_metadata *smm, enum block_op_type type, dm_block_t b)
  60 {
  61         struct block_op *op;
  62
  63         if (smm->nr_uncommitted == MAX_RECURSIVE_ALLOCATIONS) {
  64                 DMERR("too many recursive allocations");
  65                 return -ENOMEM;
  66         }
  67
  68         op = smm->uncommitted + smm->nr_uncommitted++;
  69         op->type = type;
  70         op->block = b;
  71
  72         return 0;
  73 }
  74
  75 static int commit_bop(struct sm_metadata *smm, struct block_op *op)
  76 {
  77         int r = 0;
  78         enum allocation_event ev;
  79
  80         switch (op->type) {
  81         case BOP_INC:
  82                 r = sm_ll_inc(&smm->ll, op->block, &ev);
  83                 break;
  84
  85         case BOP_DEC:
  86                 r = sm_ll_dec(&smm->ll, op->block, &ev);
  87                 break;
  88         }
  89
  90         return r;
  91 }
  92
  93 static void in(struct sm_metadata *smm)
  94 {
  95         smm->recursion_count++;
  96 }
  97
  98 static int out(struct sm_metadata *smm)
  99 {
 100         int r = 0;
 101
 102         /*
 103          * If we're not recursing then very bad things are happening.
 104          */
 105         if (!smm->recursion_count) {
 106                 DMERR("lost track of recursion depth");
 107                 return -ENOMEM;
 108         }
 109
 110         if (smm->recursion_count == 1 && smm->nr_uncommitted) {
 111                 while (smm->nr_uncommitted && !r) {
 112                         smm->nr_uncommitted--;
 113                         r = commit_bop(smm, smm->uncommitted +
 114                                        smm->nr_uncommitted);
 115                         if (r)
 116                                 break;
 117                 }
 118         }
 119
 120         smm->recursion_count--;
 121
 122         return r;
 123 }
 124
 125 /*
 126  * When using the out() function above, we often want to combine an error
 127  * code for the operation run in the recursive context with that from
 128  * out().
 129  */
 130 static int combine_errors(int r1, int r2)
 131 {
 132         return r1 ? r1 : r2;
 133 }
 134
 135 static int recursing(struct sm_metadata *smm)
 136 {
 137         return smm->recursion_count;
 138 }
 139
 140 static void sm_metadata_destroy(struct dm_space_map *sm)
 141 {
 142         struct sm_metadata *smm = container_of(sm, struct sm_metadata, sm);
 143
 144         kfree(smm);
 145 }
 146
 147 static int sm_metadata_extend(struct dm_space_map *sm, dm_block_t extra_blocks)
 148 {
 149         DMERR("doesn't support extend");
 150         return -EINVAL;
 151 }
 152
 153 static int sm_metadata_get_nr_blocks(struct dm_space_map *sm, dm_block_t *count)
 154 {
 155         struct sm_metadata *smm = container_of(sm, struct sm_metadata, sm);
 156
 157         *count = smm->ll.nr_blocks;
 158
 159         return 0;
 160 }
 161
 162 static int sm_metadata_get_nr_free(struct dm_space_map *sm, dm_block_t *count)
 163 {
 164         struct sm_metadata *smm = container_of(sm, struct sm_metadata, sm);
 165
 166         *count = smm->old_ll.nr_blocks - smm->old_ll.nr_allocated -
 167                  smm->allocated_this_transaction;
 168
 169         return 0;
 170 }
 171
 172 static int sm_metadata_get_count(struct dm_space_map *sm, dm_block_t b,
 173                                  uint32_t *result)
 174 {
 175         int r, i;
 176         struct sm_metadata *smm = container_of(sm, struct sm_metadata, sm);
 177         unsigned adjustment = 0;
 178
 179         /*
 180          * We may have some uncommitted adjustments to add.  This list
 181          * should always be really short.
 182          */
 183         for (i = 0; i < smm->nr_uncommitted; i++) {
 184                 struct block_op *op = smm->uncommitted + i;
 185
 186                 if (op->block != b)
 187                         continue;
 188
 189                 switch (op->type) {
 190                 case BOP_INC:
 191                         adjustment++;
 192                         break;
 193
 194                 case BOP_DEC:
 195                         adjustment--;
 196                         break;
 197                 }
 198         }
 199
 200         r = sm_ll_lookup(&smm->ll, b, result);
 201         if (r)
 202                 return r;
 203
 204         *result += adjustment;
 205
 206         return 0;
 207 }
 208
 209 static int sm_metadata_count_is_more_than_one(struct dm_space_map *sm,
 210                                               dm_block_t b, int *result)
 211 {
 212         int r, i, adjustment = 0;
 213         struct sm_metadata *smm = container_of(sm, struct sm_metadata, sm);
 214         uint32_t rc;
 215
 216         /*
 217          * We may have some uncommitted adjustments to add.  This list
 218          * should always be really short.
 219          */
 220         for (i = 0; i < smm->nr_uncommitted; i++) {
 221                 struct block_op *op = smm->uncommitted + i;
 222
 223                 if (op->block != b)
 224                         continue;
 225
 226                 switch (op->type) {
 227                 case BOP_INC:
 228                         adjustment++;
 229                         break;
 230
 231                 case BOP_DEC:
 232                         adjustment--;
 233                         break;
 234                 }
 235         }
 236
 237         if (adjustment > 1) {
 238                 *result = 1;
 239                 return 0;
 240         }
 241
 242         r = sm_ll_lookup_bitmap(&smm->ll, b, &rc);
 243         if (r)
 244                 return r;
 245
 246         if (rc == 3)
 247                 /*
 248                  * We err on the side of caution, and always return true.
 249                  */
 250                 *result = 1;
 251         else
 252                 *result = rc + adjustment > 1;
 253
 254         return 0;
 255 }
 256
 257 static int sm_metadata_set_count(struct dm_space_map *sm, dm_block_t b,
 258                                  uint32_t count)
 259 {
 260         int r, r2;
 261         enum allocation_event ev;
 262         struct sm_metadata *smm = container_of(sm, struct sm_metadata, sm);
 263
 264         if (smm->recursion_count) {
 265                 DMERR("cannot recurse set_count()");
 266                 return -EINVAL;
 267         }
 268
 269         in(smm);
 270         r = sm_ll_insert(&smm->ll, b, count, &ev);
 271         r2 = out(smm);
 272
 273         return combine_errors(r, r2);
 274 }
 275
 276 static int sm_metadata_inc_block(struct dm_space_map *sm, dm_block_t b)
 277 {
 278         int r, r2 = 0;
 279         enum allocation_event ev;
 280         struct sm_metadata *smm = container_of(sm, struct sm_metadata, sm);
 281
 282         if (recursing(smm))
 283                 r = add_bop(smm, BOP_INC, b);
 284         else {
 285                 in(smm);
 286                 r = sm_ll_inc(&smm->ll, b, &ev);
 287                 r2 = out(smm);
 288         }
 289
 290         return combine_errors(r, r2);
 291 }
 292
 293 static int sm_metadata_dec_block(struct dm_space_map *sm, dm_block_t b)
 294 {
 295         int r, r2 = 0;
 296         enum allocation_event ev;
 297         struct sm_metadata *smm = container_of(sm, struct sm_metadata, sm);
 298
 299         if (recursing(smm))
 300                 r = add_bop(smm, BOP_DEC, b);
 301         else {
 302                 in(smm);
 303                 r = sm_ll_dec(&smm->ll, b, &ev);
 304                 r2 = out(smm);
 305         }
 306
 307         return combine_errors(r, r2);
 308 }
 309
 310 static int sm_metadata_new_block_(struct dm_space_map *sm, dm_block_t *b)
 311 {
 312         int r, r2 = 0;
 313         enum allocation_event ev;
 314         struct sm_metadata *smm = container_of(sm, struct sm_metadata, sm);
 315
 316         r = sm_ll_find_free_block(&smm->old_ll, smm->begin, smm->old_ll.nr_blocks, b);
 317         if (r)
 318                 return r;
 319
 320         smm->begin = *b + 1;
 321
 322         if (recursing(smm))
 323                 r = add_bop(smm, BOP_INC, *b);
 324         else {
 325                 in(smm);
 326                 r = sm_ll_inc(&smm->ll, *b, &ev);
 327                 r2 = out(smm);
 328         }
 329
 330         if (!r)
 331                 smm->allocated_this_transaction++;
 332
 333         return combine_errors(r, r2);
 334 }
 335
 336 static int sm_metadata_new_block(struct dm_space_map *sm, dm_block_t *b)
 337 {
 338         int r = sm_metadata_new_block_(sm, b);
 339         if (r)
 340                 DMERR("out of metadata space");
 341         return r;
 342 }
 343
 344 static int sm_metadata_commit(struct dm_space_map *sm)
 345 {
 346         int r;
 347         struct sm_metadata *smm = container_of(sm, struct sm_metadata, sm);
 348
 349         r = sm_ll_commit(&smm->ll);
 350         if (r)
 351                 return r;
 352
 353         memcpy(&smm->old_ll, &smm->ll, sizeof(smm->old_ll));
 354         smm->begin = 0;
 355         smm->allocated_this_transaction = 0;
 356
 357         return 0;
 358 }
 359
 360 static int sm_metadata_root_size(struct dm_space_map *sm, size_t *result)
 361 {
 362         *result = sizeof(struct disk_sm_root);
 363
 364         return 0;
 365 }
 366
 367 static int sm_metadata_copy_root(struct dm_space_map *sm, void *where_le, size_t max)
 368 {
 369         struct sm_metadata *smm = container_of(sm, struct sm_metadata, sm);
 370         struct disk_sm_root root_le;
 371
 372         root_le.nr_blocks = cpu_to_le64(smm->ll.nr_blocks);
 373         root_le.nr_allocated = cpu_to_le64(smm->ll.nr_allocated);
 374         root_le.bitmap_root = cpu_to_le64(smm->ll.bitmap_root);
 375         root_le.ref_count_root = cpu_to_le64(smm->ll.ref_count_root);
 376
 377         if (max < sizeof(root_le))
 378                 return -ENOSPC;
 379
 380         memcpy(where_le, &root_le, sizeof(root_le));
 381
 382         return 0;
 383 }
 384
 385 static struct dm_space_map ops = {
 386         .destroy = sm_metadata_destroy,
 387         .extend = sm_metadata_extend,
 388         .get_nr_blocks = sm_metadata_get_nr_blocks,
 389         .get_nr_free = sm_metadata_get_nr_free,
 390         .get_count = sm_metadata_get_count,
 391         .count_is_more_than_one = sm_metadata_count_is_more_than_one,
 392         .set_count = sm_metadata_set_count,
 393         .inc_block = sm_metadata_inc_block,
 394         .dec_block = sm_metadata_dec_block,
 395         .new_block = sm_metadata_new_block,
 396         .commit = sm_metadata_commit,
 397         .root_size = sm_metadata_root_size,
 398         .copy_root = sm_metadata_copy_root
 399 };
 400
 401 /*----------------------------------------------------------------*/
 402
 403 /*
 404  * When a new space map is created that manages its own space.  We use
 405  * this tiny bootstrap allocator.
 406  */
 407 static void sm_bootstrap_destroy(struct dm_space_map *sm)
 408 {
 409 }
 410
 411 static int sm_bootstrap_extend(struct dm_space_map *sm, dm_block_t extra_blocks)
 412 {
 413         DMERR("boostrap doesn't support extend");
 414
 415         return -EINVAL;
 416 }
 417
 418 static int sm_bootstrap_get_nr_blocks(struct dm_space_map *sm, dm_block_t *count)
 419 {
 420         struct sm_metadata *smm = container_of(sm, struct sm_metadata, sm);
 421
 422         return smm->ll.nr_blocks;
 423 }
 424
 425 static int sm_bootstrap_get_nr_free(struct dm_space_map *sm, dm_block_t *count)
 426 {
 427         struct sm_metadata *smm = container_of(sm, struct sm_metadata, sm);
 428
 429         *count = smm->ll.nr_blocks - smm->begin;
 430
 431         return 0;
 432 }
 433
 434 static int sm_bootstrap_get_count(struct dm_space_map *sm, dm_block_t b,
 435                                   uint32_t *result)
 436 {
 437         struct sm_metadata *smm = container_of(sm, struct sm_metadata, sm);
 438
 439         return b < smm->begin ? 1 : 0;
 440 }
 441
 442 static int sm_bootstrap_count_is_more_than_one(struct dm_space_map *sm,
 443                                                dm_block_t b, int *result)
 444 {
 445         *result = 0;
 446
 447         return 0;
 448 }
 449
 450 static int sm_bootstrap_set_count(struct dm_space_map *sm, dm_block_t b,
 451                                   uint32_t count)
 452 {
 453         DMERR("boostrap doesn't support set_count");
 454
 455         return -EINVAL;
 456 }
 457
 458 static int sm_bootstrap_new_block(struct dm_space_map *sm, dm_block_t *b)
 459 {
 460         struct sm_metadata *smm = container_of(sm, struct sm_metadata, sm);
 461
 462         /*
 463          * We know the entire device is unused.
 464          */
 465         if (smm->begin == smm->ll.nr_blocks)
 466                 return -ENOSPC;
 467
 468         *b = smm->begin++;
 469
 470         return 0;
 471 }
 472
 473 static int sm_bootstrap_inc_block(struct dm_space_map *sm, dm_block_t b)
 474 {
 475         struct sm_metadata *smm = container_of(sm, struct sm_metadata, sm);
 476
 477         return add_bop(smm, BOP_INC, b);
 478 }
 479
 480 static int sm_bootstrap_dec_block(struct dm_space_map *sm, dm_block_t b)
 481 {
 482         struct sm_metadata *smm = container_of(sm, struct sm_metadata, sm);
 483
 484         return add_bop(smm, BOP_DEC, b);
 485 }
 486
 487 static int sm_bootstrap_commit(struct dm_space_map *sm)
 488 {
 489         return 0;
 490 }
 491
 492 static int sm_bootstrap_root_size(struct dm_space_map *sm, size_t *result)
 493 {
 494         DMERR("boostrap doesn't support root_size");
 495
 496         return -EINVAL;
 497 }
 498
 499 static int sm_bootstrap_copy_root(struct dm_space_map *sm, void *where,
 500                                   size_t max)
 501 {
 502         DMERR("boostrap doesn't support copy_root");
 503
 504         return -EINVAL;
 505 }
 506
 507 static struct dm_space_map bootstrap_ops = {
 508         .destroy = sm_bootstrap_destroy,
 509         .extend = sm_bootstrap_extend,
 510         .get_nr_blocks = sm_bootstrap_get_nr_blocks,
 511         .get_nr_free = sm_bootstrap_get_nr_free,
 512         .get_count = sm_bootstrap_get_count,
 513         .count_is_more_than_one = sm_bootstrap_count_is_more_than_one,
 514         .set_count = sm_bootstrap_set_count,
 515         .inc_block = sm_bootstrap_inc_block,
 516         .dec_block = sm_bootstrap_dec_block,
 517         .new_block = sm_bootstrap_new_block,
 518         .commit = sm_bootstrap_commit,
 519         .root_size = sm_bootstrap_root_size,
 520         .copy_root = sm_bootstrap_copy_root
 521 };
 522
 523 /*----------------------------------------------------------------*/
 524
 525 struct dm_space_map *dm_sm_metadata_init(void)
 526 {
 527         struct sm_metadata *smm;
 528
 529         smm = kmalloc(sizeof(*smm), GFP_KERNEL);
 530         if (!smm)
 531                 return ERR_PTR(-ENOMEM);
 532
 533         memcpy(&smm->sm, &ops, sizeof(smm->sm));
 534
 535         return &smm->sm;
 536 }
 537
 538 int dm_sm_metadata_create(struct dm_space_map *sm,
 539                           struct dm_transaction_manager *tm,
 540                           dm_block_t nr_blocks,
 541                           dm_block_t superblock)
 542 {
 543         int r;
 544         dm_block_t i;
 545         enum allocation_event ev;
 546         struct sm_metadata *smm = container_of(sm, struct sm_metadata, sm);
 547
 548         smm->begin = superblock + 1;
 549         smm->recursion_count = 0;
 550         smm->allocated_this_transaction = 0;
 551         smm->nr_uncommitted = 0;
 552
 553         memcpy(&smm->sm, &bootstrap_ops, sizeof(smm->sm));
 554
 555         r = sm_ll_new_metadata(&smm->ll, tm);
 556         if (r)
 557                 return r;
 558
 559         r = sm_ll_extend(&smm->ll, nr_blocks);
 560         if (r)
 561                 return r;
 562
 563         memcpy(&smm->sm, &ops, sizeof(smm->sm));
 564
 565         /*
 566          * Now we need to update the newly created data structures with the
 567          * allocated blocks that they were built from.
 568          */
 569         for (i = superblock; !r && i < smm->begin; i++)
 570                 r = sm_ll_inc(&smm->ll, i, &ev);
 571
 572         if (r)
 573                 return r;
 574
 575         return sm_metadata_commit(sm);
 576 }
 577
 578 int dm_sm_metadata_open(struct dm_space_map *sm,
 579                         struct dm_transaction_manager *tm,
 580                         void *root_le, size_t len)
 581 {
 582         int r;
 583         struct sm_metadata *smm = container_of(sm, struct sm_metadata, sm);
 584
 585         r = sm_ll_open_metadata(&smm->ll, tm, root_le, len);
 586         if (r)
 587                 return r;
 588
 589         smm->begin = 0;
 590         smm->recursion_count = 0;
 591         smm->allocated_this_transaction = 0;
 592         smm->nr_uncommitted = 0;
 593
 594         memcpy(&smm->old_ll, &smm->ll, sizeof(smm->old_ll));
 595         return 0;
 596 }