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
array_block_prepare_for_write(struct dm_block_validator * v,struct dm_block * b,size_t size_of_block)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
array_block_check(struct dm_block_validator * v,struct dm_block * b,size_t size_of_block)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 */
element_at(struct dm_array_info * info,struct array_block * ab,unsigned index)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 */
on_entries(struct dm_array_info * info,struct array_block * ab,void (* fn)(void *,const void *,unsigned))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 */
inc_ablock_entries(struct dm_array_info * info,struct array_block * ab)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 */
dec_ablock_entries(struct dm_array_info * info,struct array_block * ab)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 */
calc_max_entries(size_t value_size,size_t size_of_block)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 */
alloc_ablock(struct dm_array_info * info,size_t size_of_block,uint32_t max_entries,struct dm_block ** block,struct array_block ** ab)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 */
fill_ablock(struct dm_array_info * info,struct array_block * ab,const void * value,unsigned new_nr)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 */
trim_ablock(struct dm_array_info * info,struct array_block * ab,unsigned new_nr)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 */
get_ablock(struct dm_array_info * info,dm_block_t b,struct dm_block ** block,struct array_block ** ab)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 */
unlock_ablock(struct dm_array_info * info,struct dm_block * block)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 */
lookup_ablock(struct dm_array_info * info,dm_block_t root,unsigned index,struct dm_block ** block,struct array_block ** ab)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 */
insert_ablock(struct dm_array_info * info,uint64_t index,struct dm_block * block,dm_block_t * root)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
__shadow_ablock(struct dm_array_info * info,dm_block_t b,struct dm_block ** block,struct array_block ** ab)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 */
__reinsert_ablock(struct dm_array_info * info,unsigned index,struct dm_block * block,dm_block_t b,dm_block_t * root)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 */
shadow_ablock(struct dm_array_info * info,dm_block_t * root,unsigned index,struct dm_block ** block,struct array_block ** ab)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 */
insert_new_ablock(struct dm_array_info * info,size_t size_of_block,uint32_t max_entries,unsigned block_index,uint32_t nr,const void * value,dm_block_t * root)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
insert_full_ablocks(struct dm_array_info * info,size_t size_of_block,unsigned begin_block,unsigned end_block,unsigned max_entries,const void * value,dm_block_t * root)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 */
drop_blocks(struct resize * resize,unsigned begin_index,unsigned end_index)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 */
total_nr_blocks_needed(unsigned nr_full_blocks,unsigned nr_entries_in_last_block)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 */
shrink(struct resize * resize)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 */
grow_extend_tail_block(struct resize * resize,uint32_t new_nr_entries)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
grow_add_tail_block(struct resize * resize)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
grow_needs_more_blocks(struct resize * resize)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
grow(struct resize * resize)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 */
block_inc(void * context,const void * value,unsigned count)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
__block_dec(void * context,const void * value)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
block_dec(void * context,const void * value,unsigned count)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
block_equal(void * context,const void * value1,const void * value2)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
dm_array_info_init(struct dm_array_info * info,struct dm_transaction_manager * tm,struct dm_btree_value_type * vt)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
dm_array_empty(struct dm_array_info * info,dm_block_t * root)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
array_resize(struct dm_array_info * info,dm_block_t root,uint32_t old_size,uint32_t new_size,const void * value,dm_block_t * new_root)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
dm_array_resize(struct dm_array_info * info,dm_block_t root,uint32_t old_size,uint32_t new_size,const void * value,dm_block_t * new_root)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
populate_ablock_with_values(struct dm_array_info * info,struct array_block * ab,value_fn fn,void * context,unsigned base,unsigned new_nr)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
dm_array_new(struct dm_array_info * info,dm_block_t * root,uint32_t size,value_fn fn,void * context)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
dm_array_del(struct dm_array_info * info,dm_block_t root)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
dm_array_get_value(struct dm_array_info * info,dm_block_t root,uint32_t index,void * value_le)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
array_set_value(struct dm_array_info * info,dm_block_t root,uint32_t index,const void * value,dm_block_t * new_root)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
dm_array_set_value(struct dm_array_info * info,dm_block_t root,uint32_t index,const void * value,dm_block_t * new_root)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
walk_ablock(void * context,uint64_t * keys,void * leaf)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
dm_array_walk(struct dm_array_info * info,dm_block_t root,int (* fn)(void *,uint64_t key,void * leaf),void * context)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
load_ablock(struct dm_array_cursor * c)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
dm_array_cursor_begin(struct dm_array_info * info,dm_block_t root,struct dm_array_cursor * c)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
dm_array_cursor_end(struct dm_array_cursor * c)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
dm_array_cursor_next(struct dm_array_cursor * c)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
dm_array_cursor_skip(struct dm_array_cursor * c,uint32_t count)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
dm_array_cursor_get_value(struct dm_array_cursor * c,void ** value_le)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 /*----------------------------------------------------------------*/
1011