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 *))
 112 {
 113         unsigned i, nr_entries = le32_to_cpu(ab->nr_entries);
 114
 115         for (i = 0; i < nr_entries; i++)
 116                 fn(info->value_type.context, element_at(info, ab, i));
 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 new_nr)
 177 {
 178         unsigned i;
 179         uint32_t nr_entries;
 180         struct dm_btree_value_type *vt = &info->value_type;
 181
 182         BUG_ON(new_nr > le32_to_cpu(ab->max_entries));
 183         BUG_ON(new_nr < le32_to_cpu(ab->nr_entries));
 184
 185         nr_entries = le32_to_cpu(ab->nr_entries);
 186         for (i = nr_entries; i < new_nr; i++) {
 187                 if (vt->inc)
 188                         vt->inc(vt->context, value);
 189                 memcpy(element_at(info, ab, i), value, vt->size);
 190         }
 191         ab->nr_entries = cpu_to_le32(new_nr);
 192 }
 193
 194 /*
 195  * Remove some entries from the back of an array block.  Every value
 196  * removed will be decremented.  new_nr must be <= the current number of
 197  * entries.
 198  */
 199 static void trim_ablock(struct dm_array_info *info, struct array_block *ab,
 200                         unsigned new_nr)
 201 {
 202         unsigned i;
 203         uint32_t nr_entries;
 204         struct dm_btree_value_type *vt = &info->value_type;
 205
 206         BUG_ON(new_nr > le32_to_cpu(ab->max_entries));
 207         BUG_ON(new_nr > le32_to_cpu(ab->nr_entries));
 208
 209         nr_entries = le32_to_cpu(ab->nr_entries);
 210         for (i = nr_entries; i > new_nr; i--)
 211                 if (vt->dec)
 212                         vt->dec(vt->context, element_at(info, ab, i - 1));
 213         ab->nr_entries = cpu_to_le32(new_nr);
 214 }
 215
 216 /*
 217  * Read locks a block, and coerces it to an array block.  The caller must
 218  * unlock 'block' when finished.
 219  */
 220 static int get_ablock(struct dm_array_info *info, dm_block_t b,
 221                       struct dm_block **block, struct array_block **ab)
 222 {
 223         int r;
 224
 225         r = dm_tm_read_lock(info->btree_info.tm, b, &array_validator, block);
 226         if (r)
 227                 return r;
 228
 229         *ab = dm_block_data(*block);
 230         return 0;
 231 }
 232
 233 /*
 234  * Unlocks an array block.
 235  */
 236 static void unlock_ablock(struct dm_array_info *info, struct dm_block *block)
 237 {
 238         dm_tm_unlock(info->btree_info.tm, block);
 239 }
 240
 241 /*----------------------------------------------------------------*/
 242
 243 /*
 244  * Btree manipulation.
 245  */
 246
 247 /*
 248  * Looks up an array block in the btree, and then read locks it.
 249  *
 250  * index is the index of the index of the array_block, (ie. the array index
 251  * / max_entries).
 252  */
 253 static int lookup_ablock(struct dm_array_info *info, dm_block_t root,
 254                          unsigned index, struct dm_block **block,
 255                          struct array_block **ab)
 256 {
 257         int r;
 258         uint64_t key = index;
 259         __le64 block_le;
 260
 261         r = dm_btree_lookup(&info->btree_info, root, &key, &block_le);
 262         if (r)
 263                 return r;
 264
 265         return get_ablock(info, le64_to_cpu(block_le), block, ab);
 266 }
 267
 268 /*
 269  * Insert an array block into the btree.  The block is _not_ unlocked.
 270  */
 271 static int insert_ablock(struct dm_array_info *info, uint64_t index,
 272                          struct dm_block *block, dm_block_t *root)
 273 {
 274         __le64 block_le = cpu_to_le64(dm_block_location(block));
 275
 276         __dm_bless_for_disk(block_le);
 277         return dm_btree_insert(&info->btree_info, *root, &index, &block_le, root);
 278 }
 279
 280 /*
 281  * Looks up an array block in the btree.  Then shadows it, and updates the
 282  * btree to point to this new shadow.  'root' is an input/output parameter
 283  * for both the current root block, and the new one.
 284  */
 285 static int shadow_ablock(struct dm_array_info *info, dm_block_t *root,
 286                          unsigned index, struct dm_block **block,
 287                          struct array_block **ab)
 288 {
 289         int r, inc;
 290         uint64_t key = index;
 291         dm_block_t b;
 292         __le64 block_le;
 293
 294         /*
 295          * lookup
 296          */
 297         r = dm_btree_lookup(&info->btree_info, *root, &key, &block_le);
 298         if (r)
 299                 return r;
 300         b = le64_to_cpu(block_le);
 301
 302         /*
 303          * shadow
 304          */
 305         r = dm_tm_shadow_block(info->btree_info.tm, b,
 306                                &array_validator, block, &inc);
 307         if (r)
 308                 return r;
 309
 310         *ab = dm_block_data(*block);
 311         if (inc)
 312                 inc_ablock_entries(info, *ab);
 313
 314         /*
 315          * Reinsert.
 316          *
 317          * The shadow op will often be a noop.  Only insert if it really
 318          * copied data.
 319          */
 320         if (dm_block_location(*block) != b) {
 321                 /*
 322                  * dm_tm_shadow_block will have already decremented the old
 323                  * block, but it is still referenced by the btree.  We
 324                  * increment to stop the insert decrementing it below zero
 325                  * when overwriting the old value.
 326                  */
 327                 dm_tm_inc(info->btree_info.tm, b);
 328                 r = insert_ablock(info, index, *block, root);
 329         }
 330
 331         return r;
 332 }
 333
 334 /*
 335  * Allocate an new array block, and fill it with some values.
 336  */
 337 static int insert_new_ablock(struct dm_array_info *info, size_t size_of_block,
 338                              uint32_t max_entries,
 339                              unsigned block_index, uint32_t nr,
 340                              const void *value, dm_block_t *root)
 341 {
 342         int r;
 343         struct dm_block *block;
 344         struct array_block *ab;
 345
 346         r = alloc_ablock(info, size_of_block, max_entries, &block, &ab);
 347         if (r)
 348                 return r;
 349
 350         fill_ablock(info, ab, value, nr);
 351         r = insert_ablock(info, block_index, block, root);
 352         unlock_ablock(info, block);
 353
 354         return r;
 355 }
 356
 357 static int insert_full_ablocks(struct dm_array_info *info, size_t size_of_block,
 358                                unsigned begin_block, unsigned end_block,
 359                                unsigned max_entries, const void *value,
 360                                dm_block_t *root)
 361 {
 362         int r = 0;
 363
 364         for (; !r && begin_block != end_block; begin_block++)
 365                 r = insert_new_ablock(info, size_of_block, max_entries, begin_block, max_entries, value, root);
 366
 367         return r;
 368 }
 369
 370 /*
 371  * There are a bunch of functions involved with resizing an array.  This
 372  * structure holds information that commonly needed by them.  Purely here
 373  * to reduce parameter count.
 374  */
 375 struct resize {
 376         /*
 377          * Describes the array.
 378          */
 379         struct dm_array_info *info;
 380
 381         /*
 382          * The current root of the array.  This gets updated.
 383          */
 384         dm_block_t root;
 385
 386         /*
 387          * Metadata block size.  Used to calculate the nr entries in an
 388          * array block.
 389          */
 390         size_t size_of_block;
 391
 392         /*
 393          * Maximum nr entries in an array block.
 394          */
 395         unsigned max_entries;
 396
 397         /*
 398          * nr of completely full blocks in the array.
 399          *
 400          * 'old' refers to before the resize, 'new' after.
 401          */
 402         unsigned old_nr_full_blocks, new_nr_full_blocks;
 403
 404         /*
 405          * Number of entries in the final block.  0 iff only full blocks in
 406          * the array.
 407          */
 408         unsigned old_nr_entries_in_last_block, new_nr_entries_in_last_block;
 409
 410         /*
 411          * The default value used when growing the array.
 412          */
 413         const void *value;
 414 };
 415
 416 /*
 417  * Removes a consecutive set of array blocks from the btree.  The values
 418  * in block are decremented as a side effect of the btree remove.
 419  *
 420  * begin_index - the index of the first array block to remove.
 421  * end_index - the one-past-the-end value.  ie. this block is not removed.
 422  */
 423 static int drop_blocks(struct resize *resize, unsigned begin_index,
 424                        unsigned end_index)
 425 {
 426         int r;
 427
 428         while (begin_index != end_index) {
 429                 uint64_t key = begin_index++;
 430                 r = dm_btree_remove(&resize->info->btree_info, resize->root,
 431                                     &key, &resize->root);
 432                 if (r)
 433                         return r;
 434         }
 435
 436         return 0;
 437 }
 438
 439 /*
 440  * Calculates how many blocks are needed for the array.
 441  */
 442 static unsigned total_nr_blocks_needed(unsigned nr_full_blocks,
 443                                        unsigned nr_entries_in_last_block)
 444 {
 445         return nr_full_blocks + (nr_entries_in_last_block ? 1 : 0);
 446 }
 447
 448 /*
 449  * Shrink an array.
 450  */
 451 static int shrink(struct resize *resize)
 452 {
 453         int r;
 454         unsigned begin, end;
 455         struct dm_block *block;
 456         struct array_block *ab;
 457
 458         /*
 459          * Lose some blocks from the back?
 460          */
 461         if (resize->new_nr_full_blocks < resize->old_nr_full_blocks) {
 462                 begin = total_nr_blocks_needed(resize->new_nr_full_blocks,
 463                                                resize->new_nr_entries_in_last_block);
 464                 end = total_nr_blocks_needed(resize->old_nr_full_blocks,
 465                                              resize->old_nr_entries_in_last_block);
 466
 467                 r = drop_blocks(resize, begin, end);
 468                 if (r)
 469                         return r;
 470         }
 471
 472         /*
 473          * Trim the new tail block
 474          */
 475         if (resize->new_nr_entries_in_last_block) {
 476                 r = shadow_ablock(resize->info, &resize->root,
 477                                   resize->new_nr_full_blocks, &block, &ab);
 478                 if (r)
 479                         return r;
 480
 481                 trim_ablock(resize->info, ab, resize->new_nr_entries_in_last_block);
 482                 unlock_ablock(resize->info, block);
 483         }
 484
 485         return 0;
 486 }
 487
 488 /*
 489  * Grow an array.
 490  */
 491 static int grow_extend_tail_block(struct resize *resize, uint32_t new_nr_entries)
 492 {
 493         int r;
 494         struct dm_block *block;
 495         struct array_block *ab;
 496
 497         r = shadow_ablock(resize->info, &resize->root,
 498                           resize->old_nr_full_blocks, &block, &ab);
 499         if (r)
 500                 return r;
 501
 502         fill_ablock(resize->info, ab, resize->value, new_nr_entries);
 503         unlock_ablock(resize->info, block);
 504
 505         return r;
 506 }
 507
 508 static int grow_add_tail_block(struct resize *resize)
 509 {
 510         return insert_new_ablock(resize->info, resize->size_of_block,
 511                                  resize->max_entries,
 512                                  resize->new_nr_full_blocks,
 513                                  resize->new_nr_entries_in_last_block,
 514                                  resize->value, &resize->root);
 515 }
 516
 517 static int grow_needs_more_blocks(struct resize *resize)
 518 {
 519         int r;
 520         unsigned old_nr_blocks = resize->old_nr_full_blocks;
 521
 522         if (resize->old_nr_entries_in_last_block > 0) {
 523                 old_nr_blocks++;
 524
 525                 r = grow_extend_tail_block(resize, resize->max_entries);
 526                 if (r)
 527                         return r;
 528         }
 529
 530         r = insert_full_ablocks(resize->info, resize->size_of_block,
 531                                 old_nr_blocks,
 532                                 resize->new_nr_full_blocks,
 533                                 resize->max_entries, resize->value,
 534                                 &resize->root);
 535         if (r)
 536                 return r;
 537
 538         if (resize->new_nr_entries_in_last_block)
 539                 r = grow_add_tail_block(resize);
 540
 541         return r;
 542 }
 543
 544 static int grow(struct resize *resize)
 545 {
 546         if (resize->new_nr_full_blocks > resize->old_nr_full_blocks)
 547                 return grow_needs_more_blocks(resize);
 548
 549         else if (resize->old_nr_entries_in_last_block)
 550                 return grow_extend_tail_block(resize, resize->new_nr_entries_in_last_block);
 551
 552         else
 553                 return grow_add_tail_block(resize);
 554 }
 555
 556 /*----------------------------------------------------------------*/
 557
 558 /*
 559  * These are the value_type functions for the btree elements, which point
 560  * to array blocks.
 561  */
 562 static void block_inc(void *context, const void *value)
 563 {
 564         __le64 block_le;
 565         struct dm_array_info *info = context;
 566
 567         memcpy(&block_le, value, sizeof(block_le));
 568         dm_tm_inc(info->btree_info.tm, le64_to_cpu(block_le));
 569 }
 570
 571 static void block_dec(void *context, const void *value)
 572 {
 573         int r;
 574         uint64_t b;
 575         __le64 block_le;
 576         uint32_t ref_count;
 577         struct dm_block *block;
 578         struct array_block *ab;
 579         struct dm_array_info *info = context;
 580
 581         memcpy(&block_le, value, sizeof(block_le));
 582         b = le64_to_cpu(block_le);
 583
 584         r = dm_tm_ref(info->btree_info.tm, b, &ref_count);
 585         if (r) {
 586                 DMERR_LIMIT("couldn't get reference count for block %llu",
 587                             (unsigned long long) b);
 588                 return;
 589         }
 590
 591         if (ref_count == 1) {
 592                 /*
 593                  * We're about to drop the last reference to this ablock.
 594                  * So we need to decrement the ref count of the contents.
 595                  */
 596                 r = get_ablock(info, b, &block, &ab);
 597                 if (r) {
 598                         DMERR_LIMIT("couldn't get array block %llu",
 599                                     (unsigned long long) b);
 600                         return;
 601                 }
 602
 603                 dec_ablock_entries(info, ab);
 604                 unlock_ablock(info, block);
 605         }
 606
 607         dm_tm_dec(info->btree_info.tm, b);
 608 }
 609
 610 static int block_equal(void *context, const void *value1, const void *value2)
 611 {
 612         return !memcmp(value1, value2, sizeof(__le64));
 613 }
 614
 615 /*----------------------------------------------------------------*/
 616
 617 void dm_array_info_init(struct dm_array_info *info,
 618                         struct dm_transaction_manager *tm,
 619                         struct dm_btree_value_type *vt)
 620 {
 621         struct dm_btree_value_type *bvt = &info->btree_info.value_type;
 622
 623         memcpy(&info->value_type, vt, sizeof(info->value_type));
 624         info->btree_info.tm = tm;
 625         info->btree_info.levels = 1;
 626
 627         bvt->context = info;
 628         bvt->size = sizeof(__le64);
 629         bvt->inc = block_inc;
 630         bvt->dec = block_dec;
 631         bvt->equal = block_equal;
 632 }
 633 EXPORT_SYMBOL_GPL(dm_array_info_init);
 634
 635 int dm_array_empty(struct dm_array_info *info, dm_block_t *root)
 636 {
 637         return dm_btree_empty(&info->btree_info, root);
 638 }
 639 EXPORT_SYMBOL_GPL(dm_array_empty);
 640
 641 static int array_resize(struct dm_array_info *info, dm_block_t root,
 642                         uint32_t old_size, uint32_t new_size,
 643                         const void *value, dm_block_t *new_root)
 644 {
 645         int r;
 646         struct resize resize;
 647
 648         if (old_size == new_size) {
 649                 *new_root = root;
 650                 return 0;
 651         }
 652
 653         resize.info = info;
 654         resize.root = root;
 655         resize.size_of_block = dm_bm_block_size(dm_tm_get_bm(info->btree_info.tm));
 656         resize.max_entries = calc_max_entries(info->value_type.size,
 657                                               resize.size_of_block);
 658
 659         resize.old_nr_full_blocks = old_size / resize.max_entries;
 660         resize.old_nr_entries_in_last_block = old_size % resize.max_entries;
 661         resize.new_nr_full_blocks = new_size / resize.max_entries;
 662         resize.new_nr_entries_in_last_block = new_size % resize.max_entries;
 663         resize.value = value;
 664
 665         r = ((new_size > old_size) ? grow : shrink)(&resize);
 666         if (r)
 667                 return r;
 668
 669         *new_root = resize.root;
 670         return 0;
 671 }
 672
 673 int dm_array_resize(struct dm_array_info *info, dm_block_t root,
 674                     uint32_t old_size, uint32_t new_size,
 675                     const void *value, dm_block_t *new_root)
 676                     __dm_written_to_disk(value)
 677 {
 678         int r = array_resize(info, root, old_size, new_size, value, new_root);
 679         __dm_unbless_for_disk(value);
 680         return r;
 681 }
 682 EXPORT_SYMBOL_GPL(dm_array_resize);
 683
 684 int dm_array_del(struct dm_array_info *info, dm_block_t root)
 685 {
 686         return dm_btree_del(&info->btree_info, root);
 687 }
 688 EXPORT_SYMBOL_GPL(dm_array_del);
 689
 690 int dm_array_get_value(struct dm_array_info *info, dm_block_t root,
 691                        uint32_t index, void *value_le)
 692 {
 693         int r;
 694         struct dm_block *block;
 695         struct array_block *ab;
 696         size_t size_of_block;
 697         unsigned entry, max_entries;
 698
 699         size_of_block = dm_bm_block_size(dm_tm_get_bm(info->btree_info.tm));
 700         max_entries = calc_max_entries(info->value_type.size, size_of_block);
 701
 702         r = lookup_ablock(info, root, index / max_entries, &block, &ab);
 703         if (r)
 704                 return r;
 705
 706         entry = index % max_entries;
 707         if (entry >= le32_to_cpu(ab->nr_entries))
 708                 r = -ENODATA;
 709         else
 710                 memcpy(value_le, element_at(info, ab, entry),
 711                        info->value_type.size);
 712
 713         unlock_ablock(info, block);
 714         return r;
 715 }
 716 EXPORT_SYMBOL_GPL(dm_array_get_value);
 717
 718 static int array_set_value(struct dm_array_info *info, dm_block_t root,
 719                            uint32_t index, const void *value, dm_block_t *new_root)
 720 {
 721         int r;
 722         struct dm_block *block;
 723         struct array_block *ab;
 724         size_t size_of_block;
 725         unsigned max_entries;
 726         unsigned entry;
 727         void *old_value;
 728         struct dm_btree_value_type *vt = &info->value_type;
 729
 730         size_of_block = dm_bm_block_size(dm_tm_get_bm(info->btree_info.tm));
 731         max_entries = calc_max_entries(info->value_type.size, size_of_block);
 732
 733         r = shadow_ablock(info, &root, index / max_entries, &block, &ab);
 734         if (r)
 735                 return r;
 736         *new_root = root;
 737
 738         entry = index % max_entries;
 739         if (entry >= le32_to_cpu(ab->nr_entries)) {
 740                 r = -ENODATA;
 741                 goto out;
 742         }
 743
 744         old_value = element_at(info, ab, entry);
 745         if (vt->dec &&
 746             (!vt->equal || !vt->equal(vt->context, old_value, value))) {
 747                 vt->dec(vt->context, old_value);
 748                 if (vt->inc)
 749                         vt->inc(vt->context, value);
 750         }
 751
 752         memcpy(old_value, value, info->value_type.size);
 753
 754 out:
 755         unlock_ablock(info, block);
 756         return r;
 757 }
 758
 759 int dm_array_set_value(struct dm_array_info *info, dm_block_t root,
 760                  uint32_t index, const void *value, dm_block_t *new_root)
 761                  __dm_written_to_disk(value)
 762 {
 763         int r;
 764
 765         r = array_set_value(info, root, index, value, new_root);
 766         __dm_unbless_for_disk(value);
 767         return r;
 768 }
 769 EXPORT_SYMBOL_GPL(dm_array_set_value);
 770
 771 struct walk_info {
 772         struct dm_array_info *info;
 773         int (*fn)(void *context, uint64_t key, void *leaf);
 774         void *context;
 775 };
 776
 777 static int walk_ablock(void *context, uint64_t *keys, void *leaf)
 778 {
 779         struct walk_info *wi = context;
 780
 781         int r;
 782         unsigned i;
 783         __le64 block_le;
 784         unsigned nr_entries, max_entries;
 785         struct dm_block *block;
 786         struct array_block *ab;
 787
 788         memcpy(&block_le, leaf, sizeof(block_le));
 789         r = get_ablock(wi->info, le64_to_cpu(block_le), &block, &ab);
 790         if (r)
 791                 return r;
 792
 793         max_entries = le32_to_cpu(ab->max_entries);
 794         nr_entries = le32_to_cpu(ab->nr_entries);
 795         for (i = 0; i < nr_entries; i++) {
 796                 r = wi->fn(wi->context, keys[0] * max_entries + i,
 797                            element_at(wi->info, ab, i));
 798
 799                 if (r)
 800                         break;
 801         }
 802
 803         unlock_ablock(wi->info, block);
 804         return r;
 805 }
 806
 807 int dm_array_walk(struct dm_array_info *info, dm_block_t root,
 808                   int (*fn)(void *, uint64_t key, void *leaf),
 809                   void *context)
 810 {
 811         struct walk_info wi;
 812
 813         wi.info = info;
 814         wi.fn = fn;
 815         wi.context = context;
 816
 817         return dm_btree_walk(&info->btree_info, root, walk_ablock, &wi);
 818 }
 819 EXPORT_SYMBOL_GPL(dm_array_walk);
 820
 821 /*----------------------------------------------------------------*/