1
2
3
4
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
20
21
22
23struct array_block {
24 __le32 csum;
25 __le32 max_entries;
26 __le32 nr_entries;
27 __le32 value_size;
28 __le64 blocknr;
29} __packed;
30
31
32
33
34
35
36
37
38#define CSUM_XOR 595846735
39
40static 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
52static 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
79static 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
89
90
91
92
93
94
95
96static 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
108
109
110static 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
121
122static 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
132
133static 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
143
144static 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
151
152static 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
172
173
174
175static 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
196
197
198
199static 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
218
219
220static 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
235
236static int unlock_ablock(struct dm_array_info *info, struct dm_block *block)
237{
238 return dm_tm_unlock(info->btree_info.tm, block);
239}
240
241
242
243
244
245
246
247
248
249
250
251
252
253static 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
270
271static 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
282
283
284
285static 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
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
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
316
317
318
319
320 if (dm_block_location(*block) != b)
321 r = insert_ablock(info, index, *block, root);
322
323 return r;
324}
325
326
327
328
329static int insert_new_ablock(struct dm_array_info *info, size_t size_of_block,
330 uint32_t max_entries,
331 unsigned block_index, uint32_t nr,
332 const void *value, dm_block_t *root)
333{
334 int r;
335 struct dm_block *block;
336 struct array_block *ab;
337
338 r = alloc_ablock(info, size_of_block, max_entries, &block, &ab);
339 if (r)
340 return r;
341
342 fill_ablock(info, ab, value, nr);
343 r = insert_ablock(info, block_index, block, root);
344 unlock_ablock(info, block);
345
346 return r;
347}
348
349static int insert_full_ablocks(struct dm_array_info *info, size_t size_of_block,
350 unsigned begin_block, unsigned end_block,
351 unsigned max_entries, const void *value,
352 dm_block_t *root)
353{
354 int r = 0;
355
356 for (; !r && begin_block != end_block; begin_block++)
357 r = insert_new_ablock(info, size_of_block, max_entries, begin_block, max_entries, value, root);
358
359 return r;
360}
361
362
363
364
365
366
367struct resize {
368
369
370
371 struct dm_array_info *info;
372
373
374
375
376 dm_block_t root;
377
378
379
380
381
382 size_t size_of_block;
383
384
385
386
387 unsigned max_entries;
388
389
390
391
392
393
394 unsigned old_nr_full_blocks, new_nr_full_blocks;
395
396
397
398
399
400 unsigned old_nr_entries_in_last_block, new_nr_entries_in_last_block;
401
402
403
404
405 const void *value;
406};
407
408
409
410
411
412
413
414
415static int drop_blocks(struct resize *resize, unsigned begin_index,
416 unsigned end_index)
417{
418 int r;
419
420 while (begin_index != end_index) {
421 uint64_t key = begin_index++;
422 r = dm_btree_remove(&resize->info->btree_info, resize->root,
423 &key, &resize->root);
424 if (r)
425 return r;
426 }
427
428 return 0;
429}
430
431
432
433
434static unsigned total_nr_blocks_needed(unsigned nr_full_blocks,
435 unsigned nr_entries_in_last_block)
436{
437 return nr_full_blocks + (nr_entries_in_last_block ? 1 : 0);
438}
439
440
441
442
443static int shrink(struct resize *resize)
444{
445 int r;
446 unsigned begin, end;
447 struct dm_block *block;
448 struct array_block *ab;
449
450
451
452
453 if (resize->new_nr_full_blocks < resize->old_nr_full_blocks) {
454 begin = total_nr_blocks_needed(resize->new_nr_full_blocks,
455 resize->new_nr_entries_in_last_block);
456 end = total_nr_blocks_needed(resize->old_nr_full_blocks,
457 resize->old_nr_entries_in_last_block);
458
459 r = drop_blocks(resize, begin, end);
460 if (r)
461 return r;
462 }
463
464
465
466
467 if (resize->new_nr_entries_in_last_block) {
468 r = shadow_ablock(resize->info, &resize->root,
469 resize->new_nr_full_blocks, &block, &ab);
470 if (r)
471 return r;
472
473 trim_ablock(resize->info, ab, resize->new_nr_entries_in_last_block);
474 unlock_ablock(resize->info, block);
475 }
476
477 return 0;
478}
479
480
481
482
483static int grow_extend_tail_block(struct resize *resize, uint32_t new_nr_entries)
484{
485 int r;
486 struct dm_block *block;
487 struct array_block *ab;
488
489 r = shadow_ablock(resize->info, &resize->root,
490 resize->old_nr_full_blocks, &block, &ab);
491 if (r)
492 return r;
493
494 fill_ablock(resize->info, ab, resize->value, new_nr_entries);
495 unlock_ablock(resize->info, block);
496
497 return r;
498}
499
500static int grow_add_tail_block(struct resize *resize)
501{
502 return insert_new_ablock(resize->info, resize->size_of_block,
503 resize->max_entries,
504 resize->new_nr_full_blocks,
505 resize->new_nr_entries_in_last_block,
506 resize->value, &resize->root);
507}
508
509static int grow_needs_more_blocks(struct resize *resize)
510{
511 int r;
512
513 if (resize->old_nr_entries_in_last_block > 0) {
514 r = grow_extend_tail_block(resize, resize->max_entries);
515 if (r)
516 return r;
517 }
518
519 r = insert_full_ablocks(resize->info, resize->size_of_block,
520 resize->old_nr_full_blocks,
521 resize->new_nr_full_blocks,
522 resize->max_entries, resize->value,
523 &resize->root);
524 if (r)
525 return r;
526
527 if (resize->new_nr_entries_in_last_block)
528 r = grow_add_tail_block(resize);
529
530 return r;
531}
532
533static int grow(struct resize *resize)
534{
535 if (resize->new_nr_full_blocks > resize->old_nr_full_blocks)
536 return grow_needs_more_blocks(resize);
537
538 else if (resize->old_nr_entries_in_last_block)
539 return grow_extend_tail_block(resize, resize->new_nr_entries_in_last_block);
540
541 else
542 return grow_add_tail_block(resize);
543}
544
545
546
547
548
549
550
551static void block_inc(void *context, const void *value)
552{
553 __le64 block_le;
554 struct dm_array_info *info = context;
555
556 memcpy(&block_le, value, sizeof(block_le));
557 dm_tm_inc(info->btree_info.tm, le64_to_cpu(block_le));
558}
559
560static void block_dec(void *context, const void *value)
561{
562 int r;
563 uint64_t b;
564 __le64 block_le;
565 uint32_t ref_count;
566 struct dm_block *block;
567 struct array_block *ab;
568 struct dm_array_info *info = context;
569
570 memcpy(&block_le, value, sizeof(block_le));
571 b = le64_to_cpu(block_le);
572
573 r = dm_tm_ref(info->btree_info.tm, b, &ref_count);
574 if (r) {
575 DMERR_LIMIT("couldn't get reference count for block %llu",
576 (unsigned long long) b);
577 return;
578 }
579
580 if (ref_count == 1) {
581
582
583
584
585 r = get_ablock(info, b, &block, &ab);
586 if (r) {
587 DMERR_LIMIT("couldn't get array block %llu",
588 (unsigned long long) b);
589 return;
590 }
591
592 dec_ablock_entries(info, ab);
593 unlock_ablock(info, block);
594 }
595
596 dm_tm_dec(info->btree_info.tm, b);
597}
598
599static int block_equal(void *context, const void *value1, const void *value2)
600{
601 return !memcmp(value1, value2, sizeof(__le64));
602}
603
604
605
606void dm_array_info_init(struct dm_array_info *info,
607 struct dm_transaction_manager *tm,
608 struct dm_btree_value_type *vt)
609{
610 struct dm_btree_value_type *bvt = &info->btree_info.value_type;
611
612 memcpy(&info->value_type, vt, sizeof(info->value_type));
613 info->btree_info.tm = tm;
614 info->btree_info.levels = 1;
615
616 bvt->context = info;
617 bvt->size = sizeof(__le64);
618 bvt->inc = block_inc;
619 bvt->dec = block_dec;
620 bvt->equal = block_equal;
621}
622EXPORT_SYMBOL_GPL(dm_array_info_init);
623
624int dm_array_empty(struct dm_array_info *info, dm_block_t *root)
625{
626 return dm_btree_empty(&info->btree_info, root);
627}
628EXPORT_SYMBOL_GPL(dm_array_empty);
629
630static int array_resize(struct dm_array_info *info, dm_block_t root,
631 uint32_t old_size, uint32_t new_size,
632 const void *value, dm_block_t *new_root)
633{
634 int r;
635 struct resize resize;
636
637 if (old_size == new_size)
638 return 0;
639
640 resize.info = info;
641 resize.root = root;
642 resize.size_of_block = dm_bm_block_size(dm_tm_get_bm(info->btree_info.tm));
643 resize.max_entries = calc_max_entries(info->value_type.size,
644 resize.size_of_block);
645
646 resize.old_nr_full_blocks = old_size / resize.max_entries;
647 resize.old_nr_entries_in_last_block = old_size % resize.max_entries;
648 resize.new_nr_full_blocks = new_size / resize.max_entries;
649 resize.new_nr_entries_in_last_block = new_size % resize.max_entries;
650 resize.value = value;
651
652 r = ((new_size > old_size) ? grow : shrink)(&resize);
653 if (r)
654 return r;
655
656 *new_root = resize.root;
657 return 0;
658}
659
660int dm_array_resize(struct dm_array_info *info, dm_block_t root,
661 uint32_t old_size, uint32_t new_size,
662 const void *value, dm_block_t *new_root)
663 __dm_written_to_disk(value)
664{
665 int r = array_resize(info, root, old_size, new_size, value, new_root);
666 __dm_unbless_for_disk(value);
667 return r;
668}
669EXPORT_SYMBOL_GPL(dm_array_resize);
670
671int dm_array_del(struct dm_array_info *info, dm_block_t root)
672{
673 return dm_btree_del(&info->btree_info, root);
674}
675EXPORT_SYMBOL_GPL(dm_array_del);
676
677int dm_array_get_value(struct dm_array_info *info, dm_block_t root,
678 uint32_t index, void *value_le)
679{
680 int r;
681 struct dm_block *block;
682 struct array_block *ab;
683 size_t size_of_block;
684 unsigned entry, max_entries;
685
686 size_of_block = dm_bm_block_size(dm_tm_get_bm(info->btree_info.tm));
687 max_entries = calc_max_entries(info->value_type.size, size_of_block);
688
689 r = lookup_ablock(info, root, index / max_entries, &block, &ab);
690 if (r)
691 return r;
692
693 entry = index % max_entries;
694 if (entry >= le32_to_cpu(ab->nr_entries))
695 r = -ENODATA;
696 else
697 memcpy(value_le, element_at(info, ab, entry),
698 info->value_type.size);
699
700 unlock_ablock(info, block);
701 return r;
702}
703EXPORT_SYMBOL_GPL(dm_array_get_value);
704
705static int array_set_value(struct dm_array_info *info, dm_block_t root,
706 uint32_t index, const void *value, dm_block_t *new_root)
707{
708 int r;
709 struct dm_block *block;
710 struct array_block *ab;
711 size_t size_of_block;
712 unsigned max_entries;
713 unsigned entry;
714 void *old_value;
715 struct dm_btree_value_type *vt = &info->value_type;
716
717 size_of_block = dm_bm_block_size(dm_tm_get_bm(info->btree_info.tm));
718 max_entries = calc_max_entries(info->value_type.size, size_of_block);
719
720 r = shadow_ablock(info, &root, index / max_entries, &block, &ab);
721 if (r)
722 return r;
723 *new_root = root;
724
725 entry = index % max_entries;
726 if (entry >= le32_to_cpu(ab->nr_entries)) {
727 r = -ENODATA;
728 goto out;
729 }
730
731 old_value = element_at(info, ab, entry);
732 if (vt->dec &&
733 (!vt->equal || !vt->equal(vt->context, old_value, value))) {
734 vt->dec(vt->context, old_value);
735 if (vt->inc)
736 vt->inc(vt->context, value);
737 }
738
739 memcpy(old_value, value, info->value_type.size);
740
741out:
742 unlock_ablock(info, block);
743 return r;
744}
745
746int dm_array_set_value(struct dm_array_info *info, dm_block_t root,
747 uint32_t index, const void *value, dm_block_t *new_root)
748 __dm_written_to_disk(value)
749{
750 int r;
751
752 r = array_set_value(info, root, index, value, new_root);
753 __dm_unbless_for_disk(value);
754 return r;
755}
756EXPORT_SYMBOL_GPL(dm_array_set_value);
757
758struct walk_info {
759 struct dm_array_info *info;
760 int (*fn)(void *context, uint64_t key, void *leaf);
761 void *context;
762};
763
764static int walk_ablock(void *context, uint64_t *keys, void *leaf)
765{
766 struct walk_info *wi = context;
767
768 int r;
769 unsigned i;
770 __le64 block_le;
771 unsigned nr_entries, max_entries;
772 struct dm_block *block;
773 struct array_block *ab;
774
775 memcpy(&block_le, leaf, sizeof(block_le));
776 r = get_ablock(wi->info, le64_to_cpu(block_le), &block, &ab);
777 if (r)
778 return r;
779
780 max_entries = le32_to_cpu(ab->max_entries);
781 nr_entries = le32_to_cpu(ab->nr_entries);
782 for (i = 0; i < nr_entries; i++) {
783 r = wi->fn(wi->context, keys[0] * max_entries + i,
784 element_at(wi->info, ab, i));
785
786 if (r)
787 break;
788 }
789
790 unlock_ablock(wi->info, block);
791 return r;
792}
793
794int dm_array_walk(struct dm_array_info *info, dm_block_t root,
795 int (*fn)(void *, uint64_t key, void *leaf),
796 void *context)
797{
798 struct walk_info wi;
799
800 wi.info = info;
801 wi.fn = fn;
802 wi.context = context;
803
804 return dm_btree_walk(&info->btree_info, root, walk_ablock, &wi);
805}
806EXPORT_SYMBOL_GPL(dm_array_walk);
807
808
809