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

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