projects/linux·blob master · refs

1058 lines · 25.2 KiB

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