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