drivers/md/persistent-data/dm-array.c

   1 // SPDX-License-Identifier: GPL-2.0-only
   2 /*
   3  * Copyright (C) 2012 Red Hat, Inc.
   4  *
   5  * This file is released under the GPL.
   6  */
   7
   8 #include "dm-array.h"
   9 #include "dm-space-map.h"
  10 #include "dm-transaction-manager.h"
  11
  12 #include <linux/export.h>
  13 #include <linux/device-mapper.h>
  14
  15 #define DM_MSG_PREFIX "array"
  16
  17 /*----------------------------------------------------------------*/
  18
  19 /*
  20  * The array is implemented as a fully populated btree, which points to
  21  * blocks that contain the packed values.  This is more space efficient
  22  * than just using a btree since we don't store 1 key per value.
  23  */
  24 struct array_block {
  25         __le32 csum;
  26         __le32 max_entries;
  27         __le32 nr_entries;
  28         __le32 value_size;
  29         __le64 blocknr; /* Block this node is supposed to live in. */
  30 } __packed;
  31
  32 /*----------------------------------------------------------------*/
  33
  34 /*
  35  * Validator methods.  As usual we calculate a checksum, and also write the
  36  * block location into the header (paranoia about ssds remapping areas by
  37  * mistake).
  38  */
  39 #define CSUM_XOR 595846735
  40
  41 static void array_block_prepare_for_write(const struct dm_block_validator *v,
  42                                           struct dm_block *b,
  43                                           size_t size_of_block)
  44 {
  45         struct array_block *bh_le = dm_block_data(b);
  46
  47         bh_le->blocknr = cpu_to_le64(dm_block_location(b));
  48         bh_le->csum = cpu_to_le32(dm_bm_checksum(&bh_le->max_entries,
  49                                                  size_of_block - sizeof(__le32),
  50                                                  CSUM_XOR));
  51 }
  52
  53 static int array_block_check(const struct dm_block_validator *v,
  54                              struct dm_block *b,
  55                              size_t size_of_block)
  56 {
  57         struct array_block *bh_le = dm_block_data(b);
  58         __le32 csum_disk;
  59
  60         if (dm_block_location(b) != le64_to_cpu(bh_le->blocknr)) {
  61                 DMERR_LIMIT("%s failed: blocknr %llu != wanted %llu", __func__,
  62                             (unsigned long long) le64_to_cpu(bh_le->blocknr),
  63                             (unsigned long long) dm_block_location(b));
  64                 return -ENOTBLK;
  65         }
  66
  67         csum_disk = cpu_to_le32(dm_bm_checksum(&bh_le->max_entries,
  68                                                size_of_block - sizeof(__le32),
  69                                                CSUM_XOR));
  70         if (csum_disk != bh_le->csum) {
  71                 DMERR_LIMIT("%s failed: csum %u != wanted %u", __func__,
  72                             (unsigned int) le32_to_cpu(csum_disk),
  73                             (unsigned int) le32_to_cpu(bh_le->csum));
  74                 return -EILSEQ;
  75         }
  76
  77         return 0;
  78 }
  79
  80 static const struct dm_block_validator array_validator = {
  81         .name = "array",
  82         .prepare_for_write = array_block_prepare_for_write,
  83         .check = array_block_check
  84 };
  85
  86 /*----------------------------------------------------------------*/
  87
  88 /*
  89  * Functions for manipulating the array blocks.
  90  */
  91
  92 /*
  93  * Returns a pointer to a value within an array block.
  94  *
  95  * index - The index into _this_ specific block.
  96  */
  97 static void *element_at(struct dm_array_info *info, struct array_block *ab,
  98                         unsigned int index)
  99 {
 100         unsigned char *entry = (unsigned char *) (ab + 1);
 101
 102         entry += index * info->value_type.size;
 103
 104         return entry;
 105 }
 106
 107 /*
 108  * Utility function that calls one of the value_type methods on every value
 109  * in an array block.
 110  */
 111 static void on_entries(struct dm_array_info *info, struct array_block *ab,
 112                        void (*fn)(void *, const void *, unsigned int))
 113 {
 114         unsigned int nr_entries = le32_to_cpu(ab->nr_entries);
 115
 116         fn(info->value_type.context, element_at(info, ab, 0), nr_entries);
 117 }
 118
 119 /*
 120  * Increment every value in an array block.
 121  */
 122 static void inc_ablock_entries(struct dm_array_info *info, struct array_block *ab)
 123 {
 124         struct dm_btree_value_type *vt = &info->value_type;
 125
 126         if (vt->inc)
 127                 on_entries(info, ab, vt->inc);
 128 }
 129
 130 /*
 131  * Decrement every value in an array block.
 132  */
 133 static void dec_ablock_entries(struct dm_array_info *info, struct array_block *ab)
 134 {
 135         struct dm_btree_value_type *vt = &info->value_type;
 136
 137         if (vt->dec)
 138                 on_entries(info, ab, vt->dec);
 139 }
 140
 141 /*
 142  * Each array block can hold this many values.
 143  */
 144 static uint32_t calc_max_entries(size_t value_size, size_t size_of_block)
 145 {
 146         return (size_of_block - sizeof(struct array_block)) / value_size;
 147 }
 148
 149 /*
 150  * Allocate a new array block.  The caller will need to unlock block.
 151  */
 152 static int alloc_ablock(struct dm_array_info *info, size_t size_of_block,
 153                         uint32_t max_entries,
 154                         struct dm_block **block, struct array_block **ab)
 155 {
 156         int r;
 157
 158         r = dm_tm_new_block(info->btree_info.tm, &array_validator, block);
 159         if (r)
 160                 return r;
 161
 162         (*ab) = dm_block_data(*block);
 163         (*ab)->max_entries = cpu_to_le32(max_entries);
 164         (*ab)->nr_entries = cpu_to_le32(0);
 165         (*ab)->value_size = cpu_to_le32(info->value_type.size);
 166
 167         return 0;
 168 }
 169
 170 /*
 171  * Pad an array block out with a particular value.  Every instance will
 172  * cause an increment of the value_type.  new_nr must always be more than
 173  * the current number of entries.
 174  */
 175 static void fill_ablock(struct dm_array_info *info, struct array_block *ab,
 176                         const void *value, unsigned int new_nr)
 177 {
 178         uint32_t nr_entries, delta, i;
 179         struct dm_btree_value_type *vt = &info->value_type;
 180
 181         BUG_ON(new_nr > le32_to_cpu(ab->max_entries));
 182         BUG_ON(new_nr < le32_to_cpu(ab->nr_entries));
 183
 184         nr_entries = le32_to_cpu(ab->nr_entries);
 185         delta = new_nr - nr_entries;
 186         if (vt->inc)
 187                 vt->inc(vt->context, value, delta);
 188         for (i = nr_entries; i < new_nr; i++)
 189                 memcpy(element_at(info, ab, i), value, vt->size);
 190         ab->nr_entries = cpu_to_le32(new_nr);
 191 }
 192
 193 /*
 194  * Remove some entries from the back of an array block.  Every value
 195  * removed will be decremented.  new_nr must be <= the current number of
 196  * entries.
 197  */
 198 static void trim_ablock(struct dm_array_info *info, struct array_block *ab,
 199                         unsigned int new_nr)
 200 {
 201         uint32_t nr_entries, delta;
 202         struct dm_btree_value_type *vt = &info->value_type;
 203
 204         BUG_ON(new_nr > le32_to_cpu(ab->max_entries));
 205         BUG_ON(new_nr > le32_to_cpu(ab->nr_entries));
 206
 207         nr_entries = le32_to_cpu(ab->nr_entries);
 208         delta = nr_entries - new_nr;
 209         if (vt->dec)
 210                 vt->dec(vt->context, element_at(info, ab, new_nr - 1), delta);
 211         ab->nr_entries = cpu_to_le32(new_nr);
 212 }
 213
 214 /*
 215  * Read locks a block, and coerces it to an array block.  The caller must
 216  * unlock 'block' when finished.
 217  */
 218 static int get_ablock(struct dm_array_info *info, dm_block_t b,
 219                       struct dm_block **block, struct array_block **ab)
 220 {
 221         int r;
 222
 223         r = dm_tm_read_lock(info->btree_info.tm, b, &array_validator, block);
 224         if (r)
 225                 return r;
 226
 227         *ab = dm_block_data(*block);
 228         return 0;
 229 }
 230
 231 /*
 232  * Unlocks an array block.
 233  */
 234 static void unlock_ablock(struct dm_array_info *info, struct dm_block *block)
 235 {
 236         dm_tm_unlock(info->btree_info.tm, block);
 237 }
 238
 239 /*----------------------------------------------------------------*/
 240
 241 /*
 242  * Btree manipulation.
 243  */
 244
 245 /*
 246  * Looks up an array block in the btree, and then read locks it.
 247  *
 248  * index is the index of the index of the array_block, (ie. the array index
 249  * / max_entries).
 250  */
 251 static int lookup_ablock(struct dm_array_info *info, dm_block_t root,
 252                          unsigned int index, struct dm_block **block,
 253                          struct array_block **ab)
 254 {
 255         int r;
 256         uint64_t key = index;
 257         __le64 block_le;
 258
 259         r = dm_btree_lookup(&info->btree_info, root, &key, &block_le);
 260         if (r)
 261                 return r;
 262
 263         return get_ablock(info, le64_to_cpu(block_le), block, ab);
 264 }
 265
 266 /*
 267  * Insert an array block into the btree.  The block is _not_ unlocked.
 268  */
 269 static int insert_ablock(struct dm_array_info *info, uint64_t index,
 270                          struct dm_block *block, dm_block_t *root)
 271 {
 272         __le64 block_le = cpu_to_le64(dm_block_location(block));
 273
 274         __dm_bless_for_disk(block_le);
 275         return dm_btree_insert(&info->btree_info, *root, &index, &block_le, root);
 276 }
 277
 278 /*----------------------------------------------------------------*/
 279
 280 static int __shadow_ablock(struct dm_array_info *info, dm_block_t b,
 281                            struct dm_block **block, struct array_block **ab)
 282 {
 283         int inc;
 284         int r = dm_tm_shadow_block(info->btree_info.tm, b,
 285                                    &array_validator, block, &inc);
 286         if (r)
 287                 return r;
 288
 289         *ab = dm_block_data(*block);
 290         if (inc)
 291                 inc_ablock_entries(info, *ab);
 292
 293         return 0;
 294 }
 295
 296 /*
 297  * The shadow op will often be a noop.  Only insert if it really
 298  * copied data.
 299  */
 300 static int __reinsert_ablock(struct dm_array_info *info, unsigned int index,
 301                              struct dm_block *block, dm_block_t b,
 302                              dm_block_t *root)
 303 {
 304         int r = 0;
 305
 306         if (dm_block_location(block) != b) {
 307                 /*
 308                  * dm_tm_shadow_block will have already decremented the old
 309                  * block, but it is still referenced by the btree.  We
 310                  * increment to stop the insert decrementing it below zero
 311                  * when overwriting the old value.
 312                  */
 313                 dm_tm_inc(info->btree_info.tm, b);
 314                 r = insert_ablock(info, index, block, root);
 315         }
 316
 317         return r;
 318 }
 319
 320 /*
 321  * Looks up an array block in the btree.  Then shadows it, and updates the
 322  * btree to point to this new shadow.  'root' is an input/output parameter
 323  * for both the current root block, and the new one.
 324  */
 325 static int shadow_ablock(struct dm_array_info *info, dm_block_t *root,
 326                          unsigned int index, struct dm_block **block,
 327                          struct array_block **ab)
 328 {
 329         int r;
 330         uint64_t key = index;
 331         dm_block_t b;
 332         __le64 block_le;
 333
 334         r = dm_btree_lookup(&info->btree_info, *root, &key, &block_le);
 335         if (r)
 336                 return r;
 337         b = le64_to_cpu(block_le);
 338
 339         r = __shadow_ablock(info, b, block, ab);
 340         if (r)
 341                 return r;
 342
 343         return __reinsert_ablock(info, index, *block, b, root);
 344 }
 345
 346 /*
 347  * Allocate an new array block, and fill it with some values.
 348  */
 349 static int insert_new_ablock(struct dm_array_info *info, size_t size_of_block,
 350                              uint32_t max_entries,
 351                              unsigned int block_index, uint32_t nr,
 352                              const void *value, dm_block_t *root)
 353 {
 354         int r;
 355         struct dm_block *block;
 356         struct array_block *ab;
 357
 358         r = alloc_ablock(info, size_of_block, max_entries, &block, &ab);
 359         if (r)
 360                 return r;
 361
 362         fill_ablock(info, ab, value, nr);
 363         r = insert_ablock(info, block_index, block, root);
 364         unlock_ablock(info, block);
 365
 366         return r;
 367 }
 368
 369 static int insert_full_ablocks(struct dm_array_info *info, size_t size_of_block,
 370                                unsigned int begin_block, unsigned int end_block,
 371                                unsigned int max_entries, const void *value,
 372                                dm_block_t *root)
 373 {
 374         int r = 0;
 375
 376         for (; !r && begin_block != end_block; begin_block++)
 377                 r = insert_new_ablock(info, size_of_block, max_entries, begin_block, max_entries, value, root);
 378
 379         return r;
 380 }
 381
 382 /*
 383  * There are a bunch of functions involved with resizing an array.  This
 384  * structure holds information that commonly needed by them.  Purely here
 385  * to reduce parameter count.
 386  */
 387 struct resize {
 388         /*
 389          * Describes the array.
 390          */
 391         struct dm_array_info *info;
 392
 393         /*
 394          * The current root of the array.  This gets updated.
 395          */
 396         dm_block_t root;
 397
 398         /*
 399          * Metadata block size.  Used to calculate the nr entries in an
 400          * array block.
 401          */
 402         size_t size_of_block;
 403
 404         /*
 405          * Maximum nr entries in an array block.
 406          */
 407         unsigned int max_entries;
 408
 409         /*
 410          * nr of completely full blocks in the array.
 411          *
 412          * 'old' refers to before the resize, 'new' after.
 413          */
 414         unsigned int old_nr_full_blocks, new_nr_full_blocks;
 415
 416         /*
 417          * Number of entries in the final block.  0 iff only full blocks in
 418          * the array.
 419          */
 420         unsigned int old_nr_entries_in_last_block, new_nr_entries_in_last_block;
 421
 422         /*
 423          * The default value used when growing the array.
 424          */
 425         const void *value;
 426 };
 427
 428 /*
 429  * Removes a consecutive set of array blocks from the btree.  The values
 430  * in block are decremented as a side effect of the btree remove.
 431  *
 432  * begin_index - the index of the first array block to remove.
 433  * end_index - the one-past-the-end value.  ie. this block is not removed.
 434  */
 435 static int drop_blocks(struct resize *resize, unsigned int begin_index,
 436                        unsigned int end_index)
 437 {
 438         int r;
 439
 440         while (begin_index != end_index) {
 441                 uint64_t key = begin_index++;
 442
 443                 r = dm_btree_remove(&resize->info->btree_info, resize->root,
 444                                     &key, &resize->root);
 445                 if (r)
 446                         return r;
 447         }
 448
 449         return 0;
 450 }
 451
 452 /*
 453  * Calculates how many blocks are needed for the array.
 454  */
 455 static unsigned int total_nr_blocks_needed(unsigned int nr_full_blocks,
 456                                        unsigned int nr_entries_in_last_block)
 457 {
 458         return nr_full_blocks + (nr_entries_in_last_block ? 1 : 0);
 459 }
 460
 461 /*
 462  * Shrink an array.
 463  */
 464 static int shrink(struct resize *resize)
 465 {
 466         int r;
 467         unsigned int begin, end;
 468         struct dm_block *block;
 469         struct array_block *ab;
 470
 471         /*
 472          * Lose some blocks from the back?
 473          */
 474         if (resize->new_nr_full_blocks < resize->old_nr_full_blocks) {
 475                 begin = total_nr_blocks_needed(resize->new_nr_full_blocks,
 476                                                resize->new_nr_entries_in_last_block);
 477                 end = total_nr_blocks_needed(resize->old_nr_full_blocks,
 478                                              resize->old_nr_entries_in_last_block);
 479
 480                 r = drop_blocks(resize, begin, end);
 481                 if (r)
 482                         return r;
 483         }
 484
 485         /*
 486          * Trim the new tail block
 487          */
 488         if (resize->new_nr_entries_in_last_block) {
 489                 r = shadow_ablock(resize->info, &resize->root,
 490                                   resize->new_nr_full_blocks, &block, &ab);
 491                 if (r)
 492                         return r;
 493
 494                 trim_ablock(resize->info, ab, resize->new_nr_entries_in_last_block);
 495                 unlock_ablock(resize->info, block);
 496         }
 497
 498         return 0;
 499 }
 500
 501 /*
 502  * Grow an array.
 503  */
 504 static int grow_extend_tail_block(struct resize *resize, uint32_t new_nr_entries)
 505 {
 506         int r;
 507         struct dm_block *block;
 508         struct array_block *ab;
 509
 510         r = shadow_ablock(resize->info, &resize->root,
 511                           resize->old_nr_full_blocks, &block, &ab);
 512         if (r)
 513                 return r;
 514
 515         fill_ablock(resize->info, ab, resize->value, new_nr_entries);
 516         unlock_ablock(resize->info, block);
 517
 518         return r;
 519 }
 520
 521 static int grow_add_tail_block(struct resize *resize)
 522 {
 523         return insert_new_ablock(resize->info, resize->size_of_block,
 524                                  resize->max_entries,
 525                                  resize->new_nr_full_blocks,
 526                                  resize->new_nr_entries_in_last_block,
 527                                  resize->value, &resize->root);
 528 }
 529
 530 static int grow_needs_more_blocks(struct resize *resize)
 531 {
 532         int r;
 533         unsigned int old_nr_blocks = resize->old_nr_full_blocks;
 534
 535         if (resize->old_nr_entries_in_last_block > 0) {
 536                 old_nr_blocks++;
 537
 538                 r = grow_extend_tail_block(resize, resize->max_entries);
 539                 if (r)
 540                         return r;
 541         }
 542
 543         r = insert_full_ablocks(resize->info, resize->size_of_block,
 544                                 old_nr_blocks,
 545                                 resize->new_nr_full_blocks,
 546                                 resize->max_entries, resize->value,
 547                                 &resize->root);
 548         if (r)
 549                 return r;
 550
 551         if (resize->new_nr_entries_in_last_block)
 552                 r = grow_add_tail_block(resize);
 553
 554         return r;
 555 }
 556
 557 static int grow(struct resize *resize)
 558 {
 559         if (resize->new_nr_full_blocks > resize->old_nr_full_blocks)
 560                 return grow_needs_more_blocks(resize);
 561
 562         else if (resize->old_nr_entries_in_last_block)
 563                 return grow_extend_tail_block(resize, resize->new_nr_entries_in_last_block);
 564
 565         else
 566                 return grow_add_tail_block(resize);
 567 }
 568
 569 /*----------------------------------------------------------------*/
 570
 571 /*
 572  * These are the value_type functions for the btree elements, which point
 573  * to array blocks.
 574  */
 575 static void block_inc(void *context, const void *value, unsigned int count)
 576 {
 577         const __le64 *block_le = value;
 578         struct dm_array_info *info = context;
 579         unsigned int i;
 580
 581         for (i = 0; i < count; i++, block_le++)
 582                 dm_tm_inc(info->btree_info.tm, le64_to_cpu(*block_le));
 583 }
 584
 585 static void __block_dec(void *context, const void *value)
 586 {
 587         int r;
 588         uint64_t b;
 589         __le64 block_le;
 590         uint32_t ref_count;
 591         struct dm_block *block;
 592         struct array_block *ab;
 593         struct dm_array_info *info = context;
 594
 595         memcpy(&block_le, value, sizeof(block_le));
 596         b = le64_to_cpu(block_le);
 597
 598         r = dm_tm_ref(info->btree_info.tm, b, &ref_count);
 599         if (r) {
 600                 DMERR_LIMIT("couldn't get reference count for block %llu",
 601                             (unsigned long long) b);
 602                 return;
 603         }
 604
 605         if (ref_count == 1) {
 606                 /*
 607                  * We're about to drop the last reference to this ablock.
 608                  * So we need to decrement the ref count of the contents.
 609                  */
 610                 r = get_ablock(info, b, &block, &ab);
 611                 if (r) {
 612                         DMERR_LIMIT("couldn't get array block %llu",
 613                                     (unsigned long long) b);
 614                         return;
 615                 }
 616
 617                 dec_ablock_entries(info, ab);
 618                 unlock_ablock(info, block);
 619         }
 620
 621         dm_tm_dec(info->btree_info.tm, b);
 622 }
 623
 624 static void block_dec(void *context, const void *value, unsigned int count)
 625 {
 626         unsigned int i;
 627
 628         for (i = 0; i < count; i++, value += sizeof(__le64))
 629                 __block_dec(context, value);
 630 }
 631
 632 static int block_equal(void *context, const void *value1, const void *value2)
 633 {
 634         return !memcmp(value1, value2, sizeof(__le64));
 635 }
 636
 637 /*----------------------------------------------------------------*/
 638
 639 void dm_array_info_init(struct dm_array_info *info,
 640                         struct dm_transaction_manager *tm,
 641                         struct dm_btree_value_type *vt)
 642 {
 643         struct dm_btree_value_type *bvt = &info->btree_info.value_type;
 644
 645         memcpy(&info->value_type, vt, sizeof(info->value_type));
 646         info->btree_info.tm = tm;
 647         info->btree_info.levels = 1;
 648
 649         bvt->context = info;
 650         bvt->size = sizeof(__le64);
 651         bvt->inc = block_inc;
 652         bvt->dec = block_dec;
 653         bvt->equal = block_equal;
 654 }
 655 EXPORT_SYMBOL_GPL(dm_array_info_init);
 656
 657 int dm_array_empty(struct dm_array_info *info, dm_block_t *root)
 658 {
 659         return dm_btree_empty(&info->btree_info, root);
 660 }
 661 EXPORT_SYMBOL_GPL(dm_array_empty);
 662
 663 static int array_resize(struct dm_array_info *info, dm_block_t root,
 664                         uint32_t old_size, uint32_t new_size,
 665                         const void *value, dm_block_t *new_root)
 666 {
 667         int r;
 668         struct resize resize;
 669
 670         if (old_size == new_size) {
 671                 *new_root = root;
 672                 return 0;
 673         }
 674
 675         resize.info = info;
 676         resize.root = root;
 677         resize.size_of_block = dm_bm_block_size(dm_tm_get_bm(info->btree_info.tm));
 678         resize.max_entries = calc_max_entries(info->value_type.size,
 679                                               resize.size_of_block);
 680
 681         resize.old_nr_full_blocks = old_size / resize.max_entries;
 682         resize.old_nr_entries_in_last_block = old_size % resize.max_entries;
 683         resize.new_nr_full_blocks = new_size / resize.max_entries;
 684         resize.new_nr_entries_in_last_block = new_size % resize.max_entries;
 685         resize.value = value;
 686
 687         r = ((new_size > old_size) ? grow : shrink)(&resize);
 688         if (r)
 689                 return r;
 690
 691         *new_root = resize.root;
 692         return 0;
 693 }
 694
 695 int dm_array_resize(struct dm_array_info *info, dm_block_t root,
 696                     uint32_t old_size, uint32_t new_size,
 697                     const void *value, dm_block_t *new_root)
 698         __dm_written_to_disk(value)
 699 {
 700         int r = array_resize(info, root, old_size, new_size, value, new_root);
 701
 702         __dm_unbless_for_disk(value);
 703         return r;
 704 }
 705 EXPORT_SYMBOL_GPL(dm_array_resize);
 706
 707 static int populate_ablock_with_values(struct dm_array_info *info, struct array_block *ab,
 708                                        value_fn fn, void *context,
 709                                        unsigned int base, unsigned int new_nr)
 710 {
 711         int r;
 712         unsigned int i;
 713         struct dm_btree_value_type *vt = &info->value_type;
 714
 715         BUG_ON(le32_to_cpu(ab->nr_entries));
 716         BUG_ON(new_nr > le32_to_cpu(ab->max_entries));
 717
 718         for (i = 0; i < new_nr; i++) {
 719                 r = fn(base + i, element_at(info, ab, i), context);
 720                 if (r)
 721                         return r;
 722
 723                 if (vt->inc)
 724                         vt->inc(vt->context, element_at(info, ab, i), 1);
 725         }
 726
 727         ab->nr_entries = cpu_to_le32(new_nr);
 728         return 0;
 729 }
 730
 731 int dm_array_new(struct dm_array_info *info, dm_block_t *root,
 732                  uint32_t size, value_fn fn, void *context)
 733 {
 734         int r;
 735         struct dm_block *block;
 736         struct array_block *ab;
 737         unsigned int block_index, end_block, size_of_block, max_entries;
 738
 739         r = dm_array_empty(info, root);
 740         if (r)
 741                 return r;
 742
 743         size_of_block = dm_bm_block_size(dm_tm_get_bm(info->btree_info.tm));
 744         max_entries = calc_max_entries(info->value_type.size, size_of_block);
 745         end_block = dm_div_up(size, max_entries);
 746
 747         for (block_index = 0; block_index != end_block; block_index++) {
 748                 r = alloc_ablock(info, size_of_block, max_entries, &block, &ab);
 749                 if (r)
 750                         break;
 751
 752                 r = populate_ablock_with_values(info, ab, fn, context,
 753                                                 block_index * max_entries,
 754                                                 min(max_entries, size));
 755                 if (r) {
 756                         unlock_ablock(info, block);
 757                         break;
 758                 }
 759
 760                 r = insert_ablock(info, block_index, block, root);
 761                 unlock_ablock(info, block);
 762                 if (r)
 763                         break;
 764
 765                 size -= max_entries;
 766         }
 767
 768         return r;
 769 }
 770 EXPORT_SYMBOL_GPL(dm_array_new);
 771
 772 int dm_array_del(struct dm_array_info *info, dm_block_t root)
 773 {
 774         return dm_btree_del(&info->btree_info, root);
 775 }
 776 EXPORT_SYMBOL_GPL(dm_array_del);
 777
 778 int dm_array_get_value(struct dm_array_info *info, dm_block_t root,
 779                        uint32_t index, void *value_le)
 780 {
 781         int r;
 782         struct dm_block *block;
 783         struct array_block *ab;
 784         size_t size_of_block;
 785         unsigned int entry, max_entries;
 786
 787         size_of_block = dm_bm_block_size(dm_tm_get_bm(info->btree_info.tm));
 788         max_entries = calc_max_entries(info->value_type.size, size_of_block);
 789
 790         r = lookup_ablock(info, root, index / max_entries, &block, &ab);
 791         if (r)
 792                 return r;
 793
 794         entry = index % max_entries;
 795         if (entry >= le32_to_cpu(ab->nr_entries))
 796                 r = -ENODATA;
 797         else
 798                 memcpy(value_le, element_at(info, ab, entry),
 799                        info->value_type.size);
 800
 801         unlock_ablock(info, block);
 802         return r;
 803 }
 804 EXPORT_SYMBOL_GPL(dm_array_get_value);
 805
 806 static int array_set_value(struct dm_array_info *info, dm_block_t root,
 807                            uint32_t index, const void *value, dm_block_t *new_root)
 808 {
 809         int r;
 810         struct dm_block *block;
 811         struct array_block *ab;
 812         size_t size_of_block;
 813         unsigned int max_entries;
 814         unsigned int entry;
 815         void *old_value;
 816         struct dm_btree_value_type *vt = &info->value_type;
 817
 818         size_of_block = dm_bm_block_size(dm_tm_get_bm(info->btree_info.tm));
 819         max_entries = calc_max_entries(info->value_type.size, size_of_block);
 820
 821         r = shadow_ablock(info, &root, index / max_entries, &block, &ab);
 822         if (r)
 823                 return r;
 824         *new_root = root;
 825
 826         entry = index % max_entries;
 827         if (entry >= le32_to_cpu(ab->nr_entries)) {
 828                 r = -ENODATA;
 829                 goto out;
 830         }
 831
 832         old_value = element_at(info, ab, entry);
 833         if (vt->dec &&
 834             (!vt->equal || !vt->equal(vt->context, old_value, value))) {
 835                 vt->dec(vt->context, old_value, 1);
 836                 if (vt->inc)
 837                         vt->inc(vt->context, value, 1);
 838         }
 839
 840         memcpy(old_value, value, info->value_type.size);
 841
 842 out:
 843         unlock_ablock(info, block);
 844         return r;
 845 }
 846
 847 int dm_array_set_value(struct dm_array_info *info, dm_block_t root,
 848                  uint32_t index, const void *value, dm_block_t *new_root)
 849         __dm_written_to_disk(value)
 850 {
 851         int r;
 852
 853         r = array_set_value(info, root, index, value, new_root);
 854         __dm_unbless_for_disk(value);
 855         return r;
 856 }
 857 EXPORT_SYMBOL_GPL(dm_array_set_value);
 858
 859 struct walk_info {
 860         struct dm_array_info *info;
 861         int (*fn)(void *context, uint64_t key, void *leaf);
 862         void *context;
 863 };
 864
 865 static int walk_ablock(void *context, uint64_t *keys, void *leaf)
 866 {
 867         struct walk_info *wi = context;
 868
 869         int r;
 870         unsigned int i;
 871         __le64 block_le;
 872         unsigned int nr_entries, max_entries;
 873         struct dm_block *block;
 874         struct array_block *ab;
 875
 876         memcpy(&block_le, leaf, sizeof(block_le));
 877         r = get_ablock(wi->info, le64_to_cpu(block_le), &block, &ab);
 878         if (r)
 879                 return r;
 880
 881         max_entries = le32_to_cpu(ab->max_entries);
 882         nr_entries = le32_to_cpu(ab->nr_entries);
 883         for (i = 0; i < nr_entries; i++) {
 884                 r = wi->fn(wi->context, keys[0] * max_entries + i,
 885                            element_at(wi->info, ab, i));
 886
 887                 if (r)
 888                         break;
 889         }
 890
 891         unlock_ablock(wi->info, block);
 892         return r;
 893 }
 894
 895 int dm_array_walk(struct dm_array_info *info, dm_block_t root,
 896                   int (*fn)(void *, uint64_t key, void *leaf),
 897                   void *context)
 898 {
 899         struct walk_info wi;
 900
 901         wi.info = info;
 902         wi.fn = fn;
 903         wi.context = context;
 904
 905         return dm_btree_walk(&info->btree_info, root, walk_ablock, &wi);
 906 }
 907 EXPORT_SYMBOL_GPL(dm_array_walk);
 908
 909 /*----------------------------------------------------------------*/
 910
 911 static int load_ablock(struct dm_array_cursor *c)
 912 {
 913         int r;
 914         __le64 value_le;
 915         uint64_t key;
 916
 917         if (c->block)
 918                 unlock_ablock(c->info, c->block);
 919
 920         c->block = NULL;
 921         c->ab = NULL;
 922         c->index = 0;
 923
 924         r = dm_btree_cursor_get_value(&c->cursor, &key, &value_le);
 925         if (r) {
 926                 DMERR("dm_btree_cursor_get_value failed");
 927                 dm_btree_cursor_end(&c->cursor);
 928
 929         } else {
 930                 r = get_ablock(c->info, le64_to_cpu(value_le), &c->block, &c->ab);
 931                 if (r) {
 932                         DMERR("get_ablock failed");
 933                         dm_btree_cursor_end(&c->cursor);
 934                 }
 935         }
 936
 937         return r;
 938 }
 939
 940 int dm_array_cursor_begin(struct dm_array_info *info, dm_block_t root,
 941                           struct dm_array_cursor *c)
 942 {
 943         int r;
 944
 945         memset(c, 0, sizeof(*c));
 946         c->info = info;
 947         r = dm_btree_cursor_begin(&info->btree_info, root, true, &c->cursor);
 948         if (r) {
 949                 DMERR("couldn't create btree cursor");
 950                 return r;
 951         }
 952
 953         return load_ablock(c);
 954 }
 955 EXPORT_SYMBOL_GPL(dm_array_cursor_begin);
 956
 957 void dm_array_cursor_end(struct dm_array_cursor *c)
 958 {
 959         if (c->block) {
 960                 unlock_ablock(c->info, c->block);
 961                 dm_btree_cursor_end(&c->cursor);
 962         }
 963 }
 964 EXPORT_SYMBOL_GPL(dm_array_cursor_end);
 965
 966 int dm_array_cursor_next(struct dm_array_cursor *c)
 967 {
 968         int r;
 969
 970         if (!c->block)
 971                 return -ENODATA;
 972
 973         c->index++;
 974
 975         if (c->index >= le32_to_cpu(c->ab->nr_entries)) {
 976                 r = dm_btree_cursor_next(&c->cursor);
 977                 if (r)
 978                         return r;
 979
 980                 r = load_ablock(c);
 981                 if (r)
 982                         return r;
 983         }
 984
 985         return 0;
 986 }
 987 EXPORT_SYMBOL_GPL(dm_array_cursor_next);
 988
 989 int dm_array_cursor_skip(struct dm_array_cursor *c, uint32_t count)
 990 {
 991         int r;
 992
 993         do {
 994                 uint32_t remaining = le32_to_cpu(c->ab->nr_entries) - c->index;
 995
 996                 if (count < remaining) {
 997                         c->index += count;
 998                         return 0;
 999                 }
1000
1001                 count -= remaining;
1002                 r = dm_array_cursor_next(c);
1003
1004         } while (!r);
1005
1006         return r;
1007 }
1008 EXPORT_SYMBOL_GPL(dm_array_cursor_skip);
1009
1010 void dm_array_cursor_get_value(struct dm_array_cursor *c, void **value_le)
1011 {
1012         *value_le = element_at(c->info, c->ab, c->index);
1013 }
1014 EXPORT_SYMBOL_GPL(dm_array_cursor_get_value);
1015
1016 /*----------------------------------------------------------------*/