1 // SPDX-License-Identifier: GPL-2.0-only
2 /*
3  * Copyright (C) 2011 Red Hat, Inc.
4  *
5  * This file is released under the GPL.
6  */
7 
8 #include "dm-space-map-common.h"
9 #include "dm-transaction-manager.h"
10 #include "dm-btree-internal.h"
11 #include "dm-persistent-data-internal.h"
12 
13 #include <linux/bitops.h>
14 #include <linux/device-mapper.h>
15 
16 #define DM_MSG_PREFIX "space map common"
17 
18 /*----------------------------------------------------------------*/
19 
20 /*
21  * Index validator.
22  */
23 #define INDEX_CSUM_XOR 160478
24 
25 static void index_prepare_for_write(struct dm_block_validator *v,
26 				    struct dm_block *b,
27 				    size_t block_size)
28 {
29 	struct disk_metadata_index *mi_le = dm_block_data(b);
30 
31 	mi_le->blocknr = cpu_to_le64(dm_block_location(b));
32 	mi_le->csum = cpu_to_le32(dm_bm_checksum(&mi_le->padding,
33 						 block_size - sizeof(__le32),
34 						 INDEX_CSUM_XOR));
35 }
36 
37 static int index_check(struct dm_block_validator *v,
38 		       struct dm_block *b,
39 		       size_t block_size)
40 {
41 	struct disk_metadata_index *mi_le = dm_block_data(b);
42 	__le32 csum_disk;
43 
44 	if (dm_block_location(b) != le64_to_cpu(mi_le->blocknr)) {
45 		DMERR_LIMIT("%s failed: blocknr %llu != wanted %llu", __func__,
46 			    le64_to_cpu(mi_le->blocknr), dm_block_location(b));
47 		return -ENOTBLK;
48 	}
49 
50 	csum_disk = cpu_to_le32(dm_bm_checksum(&mi_le->padding,
51 					       block_size - sizeof(__le32),
52 					       INDEX_CSUM_XOR));
53 	if (csum_disk != mi_le->csum) {
54 		DMERR_LIMIT("i%s failed: csum %u != wanted %u", __func__,
55 			    le32_to_cpu(csum_disk), le32_to_cpu(mi_le->csum));
56 		return -EILSEQ;
57 	}
58 
59 	return 0;
60 }
61 
62 static struct dm_block_validator index_validator = {
63 	.name = "index",
64 	.prepare_for_write = index_prepare_for_write,
65 	.check = index_check
66 };
67 
68 /*----------------------------------------------------------------*/
69 
70 /*
71  * Bitmap validator
72  */
73 #define BITMAP_CSUM_XOR 240779
74 
75 static void dm_bitmap_prepare_for_write(struct dm_block_validator *v,
76 					struct dm_block *b,
77 					size_t block_size)
78 {
79 	struct disk_bitmap_header *disk_header = dm_block_data(b);
80 
81 	disk_header->blocknr = cpu_to_le64(dm_block_location(b));
82 	disk_header->csum = cpu_to_le32(dm_bm_checksum(&disk_header->not_used,
83 						       block_size - sizeof(__le32),
84 						       BITMAP_CSUM_XOR));
85 }
86 
87 static int dm_bitmap_check(struct dm_block_validator *v,
88 			   struct dm_block *b,
89 			   size_t block_size)
90 {
91 	struct disk_bitmap_header *disk_header = dm_block_data(b);
92 	__le32 csum_disk;
93 
94 	if (dm_block_location(b) != le64_to_cpu(disk_header->blocknr)) {
95 		DMERR_LIMIT("bitmap check failed: blocknr %llu != wanted %llu",
96 			    le64_to_cpu(disk_header->blocknr), dm_block_location(b));
97 		return -ENOTBLK;
98 	}
99 
100 	csum_disk = cpu_to_le32(dm_bm_checksum(&disk_header->not_used,
101 					       block_size - sizeof(__le32),
102 					       BITMAP_CSUM_XOR));
103 	if (csum_disk != disk_header->csum) {
104 		DMERR_LIMIT("bitmap check failed: csum %u != wanted %u",
105 			    le32_to_cpu(csum_disk), le32_to_cpu(disk_header->csum));
106 		return -EILSEQ;
107 	}
108 
109 	return 0;
110 }
111 
112 static struct dm_block_validator dm_sm_bitmap_validator = {
113 	.name = "sm_bitmap",
114 	.prepare_for_write = dm_bitmap_prepare_for_write,
115 	.check = dm_bitmap_check,
116 };
117 
118 /*----------------------------------------------------------------*/
119 
120 #define ENTRIES_PER_WORD 32
121 #define ENTRIES_SHIFT	5
122 
123 static void *dm_bitmap_data(struct dm_block *b)
124 {
125 	return dm_block_data(b) + sizeof(struct disk_bitmap_header);
126 }
127 
128 #define WORD_MASK_HIGH 0xAAAAAAAAAAAAAAAAULL
129 
130 static unsigned int dm_bitmap_word_used(void *addr, unsigned int b)
131 {
132 	__le64 *words_le = addr;
133 	__le64 *w_le = words_le + (b >> ENTRIES_SHIFT);
134 
135 	uint64_t bits = le64_to_cpu(*w_le);
136 	uint64_t mask = (bits + WORD_MASK_HIGH + 1) & WORD_MASK_HIGH;
137 
138 	return !(~bits & mask);
139 }
140 
141 static unsigned int sm_lookup_bitmap(void *addr, unsigned int b)
142 {
143 	__le64 *words_le = addr;
144 	__le64 *w_le = words_le + (b >> ENTRIES_SHIFT);
145 	unsigned int hi, lo;
146 
147 	b = (b & (ENTRIES_PER_WORD - 1)) << 1;
148 	hi = !!test_bit_le(b, (void *) w_le);
149 	lo = !!test_bit_le(b + 1, (void *) w_le);
150 	return (hi << 1) | lo;
151 }
152 
153 static void sm_set_bitmap(void *addr, unsigned int b, unsigned int val)
154 {
155 	__le64 *words_le = addr;
156 	__le64 *w_le = words_le + (b >> ENTRIES_SHIFT);
157 
158 	b = (b & (ENTRIES_PER_WORD - 1)) << 1;
159 
160 	if (val & 2)
161 		__set_bit_le(b, (void *) w_le);
162 	else
163 		__clear_bit_le(b, (void *) w_le);
164 
165 	if (val & 1)
166 		__set_bit_le(b + 1, (void *) w_le);
167 	else
168 		__clear_bit_le(b + 1, (void *) w_le);
169 }
170 
171 static int sm_find_free(void *addr, unsigned int begin, unsigned int end,
172 			unsigned int *result)
173 {
174 	while (begin < end) {
175 		if (!(begin & (ENTRIES_PER_WORD - 1)) &&
176 		    dm_bitmap_word_used(addr, begin)) {
177 			begin += ENTRIES_PER_WORD;
178 			continue;
179 		}
180 
181 		if (!sm_lookup_bitmap(addr, begin)) {
182 			*result = begin;
183 			return 0;
184 		}
185 
186 		begin++;
187 	}
188 
189 	return -ENOSPC;
190 }
191 
192 /*----------------------------------------------------------------*/
193 
194 static int sm_ll_init(struct ll_disk *ll, struct dm_transaction_manager *tm)
195 {
196 	memset(ll, 0, sizeof(struct ll_disk));
197 
198 	ll->tm = tm;
199 
200 	ll->bitmap_info.tm = tm;
201 	ll->bitmap_info.levels = 1;
202 
203 	/*
204 	 * Because the new bitmap blocks are created via a shadow
205 	 * operation, the old entry has already had its reference count
206 	 * decremented and we don't need the btree to do any bookkeeping.
207 	 */
208 	ll->bitmap_info.value_type.size = sizeof(struct disk_index_entry);
209 	ll->bitmap_info.value_type.inc = NULL;
210 	ll->bitmap_info.value_type.dec = NULL;
211 	ll->bitmap_info.value_type.equal = NULL;
212 
213 	ll->ref_count_info.tm = tm;
214 	ll->ref_count_info.levels = 1;
215 	ll->ref_count_info.value_type.size = sizeof(uint32_t);
216 	ll->ref_count_info.value_type.inc = NULL;
217 	ll->ref_count_info.value_type.dec = NULL;
218 	ll->ref_count_info.value_type.equal = NULL;
219 
220 	ll->block_size = dm_bm_block_size(dm_tm_get_bm(tm));
221 
222 	if (ll->block_size > (1 << 30)) {
223 		DMERR("block size too big to hold bitmaps");
224 		return -EINVAL;
225 	}
226 
227 	ll->entries_per_block = (ll->block_size - sizeof(struct disk_bitmap_header)) *
228 		ENTRIES_PER_BYTE;
229 	ll->nr_blocks = 0;
230 	ll->bitmap_root = 0;
231 	ll->ref_count_root = 0;
232 	ll->bitmap_index_changed = false;
233 
234 	return 0;
235 }
236 
237 int sm_ll_extend(struct ll_disk *ll, dm_block_t extra_blocks)
238 {
239 	int r;
240 	dm_block_t i, nr_blocks, nr_indexes;
241 	unsigned int old_blocks, blocks;
242 
243 	nr_blocks = ll->nr_blocks + extra_blocks;
244 	old_blocks = dm_sector_div_up(ll->nr_blocks, ll->entries_per_block);
245 	blocks = dm_sector_div_up(nr_blocks, ll->entries_per_block);
246 
247 	nr_indexes = dm_sector_div_up(nr_blocks, ll->entries_per_block);
248 	if (nr_indexes > ll->max_entries(ll)) {
249 		DMERR("space map too large");
250 		return -EINVAL;
251 	}
252 
253 	/*
254 	 * We need to set this before the dm_tm_new_block() call below.
255 	 */
256 	ll->nr_blocks = nr_blocks;
257 	for (i = old_blocks; i < blocks; i++) {
258 		struct dm_block *b;
259 		struct disk_index_entry idx;
260 
261 		r = dm_tm_new_block(ll->tm, &dm_sm_bitmap_validator, &b);
262 		if (r < 0)
263 			return r;
264 
265 		idx.blocknr = cpu_to_le64(dm_block_location(b));
266 
267 		dm_tm_unlock(ll->tm, b);
268 
269 		idx.nr_free = cpu_to_le32(ll->entries_per_block);
270 		idx.none_free_before = 0;
271 
272 		r = ll->save_ie(ll, i, &idx);
273 		if (r < 0)
274 			return r;
275 	}
276 
277 	return 0;
278 }
279 
280 int sm_ll_lookup_bitmap(struct ll_disk *ll, dm_block_t b, uint32_t *result)
281 {
282 	int r;
283 	dm_block_t index = b;
284 	struct disk_index_entry ie_disk;
285 	struct dm_block *blk;
286 
287 	if (b >= ll->nr_blocks) {
288 		DMERR_LIMIT("metadata block out of bounds");
289 		return -EINVAL;
290 	}
291 
292 	b = do_div(index, ll->entries_per_block);
293 	r = ll->load_ie(ll, index, &ie_disk);
294 	if (r < 0)
295 		return r;
296 
297 	r = dm_tm_read_lock(ll->tm, le64_to_cpu(ie_disk.blocknr),
298 			    &dm_sm_bitmap_validator, &blk);
299 	if (r < 0)
300 		return r;
301 
302 	*result = sm_lookup_bitmap(dm_bitmap_data(blk), b);
303 
304 	dm_tm_unlock(ll->tm, blk);
305 
306 	return 0;
307 }
308 
309 static int sm_ll_lookup_big_ref_count(struct ll_disk *ll, dm_block_t b,
310 				      uint32_t *result)
311 {
312 	__le32 le_rc;
313 	int r;
314 
315 	r = dm_btree_lookup(&ll->ref_count_info, ll->ref_count_root, &b, &le_rc);
316 	if (r < 0)
317 		return r;
318 
319 	*result = le32_to_cpu(le_rc);
320 
321 	return r;
322 }
323 
324 int sm_ll_lookup(struct ll_disk *ll, dm_block_t b, uint32_t *result)
325 {
326 	int r = sm_ll_lookup_bitmap(ll, b, result);
327 
328 	if (r)
329 		return r;
330 
331 	if (*result != 3)
332 		return r;
333 
334 	return sm_ll_lookup_big_ref_count(ll, b, result);
335 }
336 
337 int sm_ll_find_free_block(struct ll_disk *ll, dm_block_t begin,
338 			  dm_block_t end, dm_block_t *result)
339 {
340 	int r;
341 	struct disk_index_entry ie_disk;
342 	dm_block_t i, index_begin = begin;
343 	dm_block_t index_end = dm_sector_div_up(end, ll->entries_per_block);
344 
345 	/*
346 	 * FIXME: Use shifts
347 	 */
348 	begin = do_div(index_begin, ll->entries_per_block);
349 	end = do_div(end, ll->entries_per_block);
350 	if (end == 0)
351 		end = ll->entries_per_block;
352 
353 	for (i = index_begin; i < index_end; i++, begin = 0) {
354 		struct dm_block *blk;
355 		unsigned int position;
356 		uint32_t bit_end;
357 
358 		r = ll->load_ie(ll, i, &ie_disk);
359 		if (r < 0)
360 			return r;
361 
362 		if (le32_to_cpu(ie_disk.nr_free) == 0)
363 			continue;
364 
365 		r = dm_tm_read_lock(ll->tm, le64_to_cpu(ie_disk.blocknr),
366 				    &dm_sm_bitmap_validator, &blk);
367 		if (r < 0)
368 			return r;
369 
370 		bit_end = (i == index_end - 1) ?  end : ll->entries_per_block;
371 
372 		r = sm_find_free(dm_bitmap_data(blk),
373 				 max_t(unsigned int, begin, le32_to_cpu(ie_disk.none_free_before)),
374 				 bit_end, &position);
375 		if (r == -ENOSPC) {
376 			/*
377 			 * This might happen because we started searching
378 			 * part way through the bitmap.
379 			 */
380 			dm_tm_unlock(ll->tm, blk);
381 			continue;
382 		}
383 
384 		dm_tm_unlock(ll->tm, blk);
385 
386 		*result = i * ll->entries_per_block + (dm_block_t) position;
387 		return 0;
388 	}
389 
390 	return -ENOSPC;
391 }
392 
393 int sm_ll_find_common_free_block(struct ll_disk *old_ll, struct ll_disk *new_ll,
394 				 dm_block_t begin, dm_block_t end, dm_block_t *b)
395 {
396 	int r;
397 	uint32_t count;
398 
399 	do {
400 		r = sm_ll_find_free_block(new_ll, begin, new_ll->nr_blocks, b);
401 		if (r)
402 			break;
403 
404 		/* double check this block wasn't used in the old transaction */
405 		if (*b >= old_ll->nr_blocks)
406 			count = 0;
407 		else {
408 			r = sm_ll_lookup(old_ll, *b, &count);
409 			if (r)
410 				break;
411 
412 			if (count)
413 				begin = *b + 1;
414 		}
415 	} while (count);
416 
417 	return r;
418 }
419 
420 /*----------------------------------------------------------------*/
421 
422 int sm_ll_insert(struct ll_disk *ll, dm_block_t b,
423 		 uint32_t ref_count, int32_t *nr_allocations)
424 {
425 	int r;
426 	uint32_t bit, old;
427 	struct dm_block *nb;
428 	dm_block_t index = b;
429 	struct disk_index_entry ie_disk;
430 	void *bm_le;
431 	int inc;
432 
433 	bit = do_div(index, ll->entries_per_block);
434 	r = ll->load_ie(ll, index, &ie_disk);
435 	if (r < 0)
436 		return r;
437 
438 	r = dm_tm_shadow_block(ll->tm, le64_to_cpu(ie_disk.blocknr),
439 			       &dm_sm_bitmap_validator, &nb, &inc);
440 	if (r < 0) {
441 		DMERR("dm_tm_shadow_block() failed");
442 		return r;
443 	}
444 	ie_disk.blocknr = cpu_to_le64(dm_block_location(nb));
445 	bm_le = dm_bitmap_data(nb);
446 
447 	old = sm_lookup_bitmap(bm_le, bit);
448 	if (old > 2) {
449 		r = sm_ll_lookup_big_ref_count(ll, b, &old);
450 		if (r < 0) {
451 			dm_tm_unlock(ll->tm, nb);
452 			return r;
453 		}
454 	}
455 
456 	if (r) {
457 		dm_tm_unlock(ll->tm, nb);
458 		return r;
459 	}
460 
461 	if (ref_count <= 2) {
462 		sm_set_bitmap(bm_le, bit, ref_count);
463 		dm_tm_unlock(ll->tm, nb);
464 
465 		if (old > 2) {
466 			r = dm_btree_remove(&ll->ref_count_info,
467 					    ll->ref_count_root,
468 					    &b, &ll->ref_count_root);
469 			if (r)
470 				return r;
471 		}
472 
473 	} else {
474 		__le32 le_rc = cpu_to_le32(ref_count);
475 
476 		sm_set_bitmap(bm_le, bit, 3);
477 		dm_tm_unlock(ll->tm, nb);
478 
479 		__dm_bless_for_disk(&le_rc);
480 		r = dm_btree_insert(&ll->ref_count_info, ll->ref_count_root,
481 				    &b, &le_rc, &ll->ref_count_root);
482 		if (r < 0) {
483 			DMERR("ref count insert failed");
484 			return r;
485 		}
486 	}
487 
488 	if (ref_count && !old) {
489 		*nr_allocations = 1;
490 		ll->nr_allocated++;
491 		le32_add_cpu(&ie_disk.nr_free, -1);
492 		if (le32_to_cpu(ie_disk.none_free_before) == bit)
493 			ie_disk.none_free_before = cpu_to_le32(bit + 1);
494 
495 	} else if (old && !ref_count) {
496 		*nr_allocations = -1;
497 		ll->nr_allocated--;
498 		le32_add_cpu(&ie_disk.nr_free, 1);
499 		ie_disk.none_free_before = cpu_to_le32(min(le32_to_cpu(ie_disk.none_free_before), bit));
500 	} else
501 		*nr_allocations = 0;
502 
503 	return ll->save_ie(ll, index, &ie_disk);
504 }
505 
506 /*----------------------------------------------------------------*/
507 
508 /*
509  * Holds useful intermediate results for the range based inc and dec
510  * operations.
511  */
512 struct inc_context {
513 	struct disk_index_entry ie_disk;
514 	struct dm_block *bitmap_block;
515 	void *bitmap;
516 
517 	struct dm_block *overflow_leaf;
518 };
519 
520 static inline void init_inc_context(struct inc_context *ic)
521 {
522 	ic->bitmap_block = NULL;
523 	ic->bitmap = NULL;
524 	ic->overflow_leaf = NULL;
525 }
526 
527 static inline void exit_inc_context(struct ll_disk *ll, struct inc_context *ic)
528 {
529 	if (ic->bitmap_block)
530 		dm_tm_unlock(ll->tm, ic->bitmap_block);
531 	if (ic->overflow_leaf)
532 		dm_tm_unlock(ll->tm, ic->overflow_leaf);
533 }
534 
535 static inline void reset_inc_context(struct ll_disk *ll, struct inc_context *ic)
536 {
537 	exit_inc_context(ll, ic);
538 	init_inc_context(ic);
539 }
540 
541 /*
542  * Confirms a btree node contains a particular key at an index.
543  */
544 static bool contains_key(struct btree_node *n, uint64_t key, int index)
545 {
546 	return index >= 0 &&
547 		index < le32_to_cpu(n->header.nr_entries) &&
548 		le64_to_cpu(n->keys[index]) == key;
549 }
550 
551 static int __sm_ll_inc_overflow(struct ll_disk *ll, dm_block_t b, struct inc_context *ic)
552 {
553 	int r;
554 	int index;
555 	struct btree_node *n;
556 	__le32 *v_ptr;
557 	uint32_t rc;
558 
559 	/*
560 	 * bitmap_block needs to be unlocked because getting the
561 	 * overflow_leaf may need to allocate, and thus use the space map.
562 	 */
563 	reset_inc_context(ll, ic);
564 
565 	r = btree_get_overwrite_leaf(&ll->ref_count_info, ll->ref_count_root,
566 				     b, &index, &ll->ref_count_root, &ic->overflow_leaf);
567 	if (r < 0)
568 		return r;
569 
570 	n = dm_block_data(ic->overflow_leaf);
571 
572 	if (!contains_key(n, b, index)) {
573 		DMERR("overflow btree is missing an entry");
574 		return -EINVAL;
575 	}
576 
577 	v_ptr = value_ptr(n, index);
578 	rc = le32_to_cpu(*v_ptr) + 1;
579 	*v_ptr = cpu_to_le32(rc);
580 
581 	return 0;
582 }
583 
584 static int sm_ll_inc_overflow(struct ll_disk *ll, dm_block_t b, struct inc_context *ic)
585 {
586 	int index;
587 	struct btree_node *n;
588 	__le32 *v_ptr;
589 	uint32_t rc;
590 
591 	/*
592 	 * Do we already have the correct overflow leaf?
593 	 */
594 	if (ic->overflow_leaf) {
595 		n = dm_block_data(ic->overflow_leaf);
596 		index = lower_bound(n, b);
597 		if (contains_key(n, b, index)) {
598 			v_ptr = value_ptr(n, index);
599 			rc = le32_to_cpu(*v_ptr) + 1;
600 			*v_ptr = cpu_to_le32(rc);
601 
602 			return 0;
603 		}
604 	}
605 
606 	return __sm_ll_inc_overflow(ll, b, ic);
607 }
608 
609 static inline int shadow_bitmap(struct ll_disk *ll, struct inc_context *ic)
610 {
611 	int r, inc;
612 
613 	r = dm_tm_shadow_block(ll->tm, le64_to_cpu(ic->ie_disk.blocknr),
614 			       &dm_sm_bitmap_validator, &ic->bitmap_block, &inc);
615 	if (r < 0) {
616 		DMERR("dm_tm_shadow_block() failed");
617 		return r;
618 	}
619 	ic->ie_disk.blocknr = cpu_to_le64(dm_block_location(ic->bitmap_block));
620 	ic->bitmap = dm_bitmap_data(ic->bitmap_block);
621 	return 0;
622 }
623 
624 /*
625  * Once shadow_bitmap has been called, which always happens at the start of inc/dec,
626  * we can reopen the bitmap with a simple write lock, rather than re calling
627  * dm_tm_shadow_block().
628  */
629 static inline int ensure_bitmap(struct ll_disk *ll, struct inc_context *ic)
630 {
631 	if (!ic->bitmap_block) {
632 		int r = dm_bm_write_lock(dm_tm_get_bm(ll->tm), le64_to_cpu(ic->ie_disk.blocknr),
633 					 &dm_sm_bitmap_validator, &ic->bitmap_block);
634 		if (r) {
635 			DMERR("unable to re-get write lock for bitmap");
636 			return r;
637 		}
638 		ic->bitmap = dm_bitmap_data(ic->bitmap_block);
639 	}
640 
641 	return 0;
642 }
643 
644 /*
645  * Loops round incrementing entries in a single bitmap.
646  */
647 static inline int sm_ll_inc_bitmap(struct ll_disk *ll, dm_block_t b,
648 				   uint32_t bit, uint32_t bit_end,
649 				   int32_t *nr_allocations, dm_block_t *new_b,
650 				   struct inc_context *ic)
651 {
652 	int r;
653 	__le32 le_rc;
654 	uint32_t old;
655 
656 	for (; bit != bit_end; bit++, b++) {
657 		/*
658 		 * We only need to drop the bitmap if we need to find a new btree
659 		 * leaf for the overflow.  So if it was dropped last iteration,
660 		 * we now re-get it.
661 		 */
662 		r = ensure_bitmap(ll, ic);
663 		if (r)
664 			return r;
665 
666 		old = sm_lookup_bitmap(ic->bitmap, bit);
667 		switch (old) {
668 		case 0:
669 			/* inc bitmap, adjust nr_allocated */
670 			sm_set_bitmap(ic->bitmap, bit, 1);
671 			(*nr_allocations)++;
672 			ll->nr_allocated++;
673 			le32_add_cpu(&ic->ie_disk.nr_free, -1);
674 			if (le32_to_cpu(ic->ie_disk.none_free_before) == bit)
675 				ic->ie_disk.none_free_before = cpu_to_le32(bit + 1);
676 			break;
677 
678 		case 1:
679 			/* inc bitmap */
680 			sm_set_bitmap(ic->bitmap, bit, 2);
681 			break;
682 
683 		case 2:
684 			/* inc bitmap and insert into overflow */
685 			sm_set_bitmap(ic->bitmap, bit, 3);
686 			reset_inc_context(ll, ic);
687 
688 			le_rc = cpu_to_le32(3);
689 			__dm_bless_for_disk(&le_rc);
690 			r = dm_btree_insert(&ll->ref_count_info, ll->ref_count_root,
691 					    &b, &le_rc, &ll->ref_count_root);
692 			if (r < 0) {
693 				DMERR("ref count insert failed");
694 				return r;
695 			}
696 			break;
697 
698 		default:
699 			/*
700 			 * inc within the overflow tree only.
701 			 */
702 			r = sm_ll_inc_overflow(ll, b, ic);
703 			if (r < 0)
704 				return r;
705 		}
706 	}
707 
708 	*new_b = b;
709 	return 0;
710 }
711 
712 /*
713  * Finds a bitmap that contains entries in the block range, and increments
714  * them.
715  */
716 static int __sm_ll_inc(struct ll_disk *ll, dm_block_t b, dm_block_t e,
717 		       int32_t *nr_allocations, dm_block_t *new_b)
718 {
719 	int r;
720 	struct inc_context ic;
721 	uint32_t bit, bit_end;
722 	dm_block_t index = b;
723 
724 	init_inc_context(&ic);
725 
726 	bit = do_div(index, ll->entries_per_block);
727 	r = ll->load_ie(ll, index, &ic.ie_disk);
728 	if (r < 0)
729 		return r;
730 
731 	r = shadow_bitmap(ll, &ic);
732 	if (r)
733 		return r;
734 
735 	bit_end = min(bit + (e - b), (dm_block_t) ll->entries_per_block);
736 	r = sm_ll_inc_bitmap(ll, b, bit, bit_end, nr_allocations, new_b, &ic);
737 
738 	exit_inc_context(ll, &ic);
739 
740 	if (r)
741 		return r;
742 
743 	return ll->save_ie(ll, index, &ic.ie_disk);
744 }
745 
746 int sm_ll_inc(struct ll_disk *ll, dm_block_t b, dm_block_t e,
747 	      int32_t *nr_allocations)
748 {
749 	*nr_allocations = 0;
750 	while (b != e) {
751 		int r = __sm_ll_inc(ll, b, e, nr_allocations, &b);
752 
753 		if (r)
754 			return r;
755 	}
756 
757 	return 0;
758 }
759 
760 /*----------------------------------------------------------------*/
761 
762 static int __sm_ll_del_overflow(struct ll_disk *ll, dm_block_t b,
763 				struct inc_context *ic)
764 {
765 	reset_inc_context(ll, ic);
766 	return dm_btree_remove(&ll->ref_count_info, ll->ref_count_root,
767 			       &b, &ll->ref_count_root);
768 }
769 
770 static int __sm_ll_dec_overflow(struct ll_disk *ll, dm_block_t b,
771 				struct inc_context *ic, uint32_t *old_rc)
772 {
773 	int r;
774 	int index = -1;
775 	struct btree_node *n;
776 	__le32 *v_ptr;
777 	uint32_t rc;
778 
779 	reset_inc_context(ll, ic);
780 	r = btree_get_overwrite_leaf(&ll->ref_count_info, ll->ref_count_root,
781 				     b, &index, &ll->ref_count_root, &ic->overflow_leaf);
782 	if (r < 0)
783 		return r;
784 
785 	n = dm_block_data(ic->overflow_leaf);
786 
787 	if (!contains_key(n, b, index)) {
788 		DMERR("overflow btree is missing an entry");
789 		return -EINVAL;
790 	}
791 
792 	v_ptr = value_ptr(n, index);
793 	rc = le32_to_cpu(*v_ptr);
794 	*old_rc = rc;
795 
796 	if (rc == 3)
797 		return __sm_ll_del_overflow(ll, b, ic);
798 
799 	rc--;
800 	*v_ptr = cpu_to_le32(rc);
801 	return 0;
802 }
803 
804 static int sm_ll_dec_overflow(struct ll_disk *ll, dm_block_t b,
805 			      struct inc_context *ic, uint32_t *old_rc)
806 {
807 	/*
808 	 * Do we already have the correct overflow leaf?
809 	 */
810 	if (ic->overflow_leaf) {
811 		int index;
812 		struct btree_node *n;
813 		__le32 *v_ptr;
814 		uint32_t rc;
815 
816 		n = dm_block_data(ic->overflow_leaf);
817 		index = lower_bound(n, b);
818 		if (contains_key(n, b, index)) {
819 			v_ptr = value_ptr(n, index);
820 			rc = le32_to_cpu(*v_ptr);
821 			*old_rc = rc;
822 
823 			if (rc > 3) {
824 				rc--;
825 				*v_ptr = cpu_to_le32(rc);
826 				return 0;
827 			} else {
828 				return __sm_ll_del_overflow(ll, b, ic);
829 			}
830 
831 		}
832 	}
833 
834 	return __sm_ll_dec_overflow(ll, b, ic, old_rc);
835 }
836 
837 /*
838  * Loops round incrementing entries in a single bitmap.
839  */
840 static inline int sm_ll_dec_bitmap(struct ll_disk *ll, dm_block_t b,
841 				   uint32_t bit, uint32_t bit_end,
842 				   struct inc_context *ic,
843 				   int32_t *nr_allocations, dm_block_t *new_b)
844 {
845 	int r;
846 	uint32_t old;
847 
848 	for (; bit != bit_end; bit++, b++) {
849 		/*
850 		 * We only need to drop the bitmap if we need to find a new btree
851 		 * leaf for the overflow.  So if it was dropped last iteration,
852 		 * we now re-get it.
853 		 */
854 		r = ensure_bitmap(ll, ic);
855 		if (r)
856 			return r;
857 
858 		old = sm_lookup_bitmap(ic->bitmap, bit);
859 		switch (old) {
860 		case 0:
861 			DMERR("unable to decrement block");
862 			return -EINVAL;
863 
864 		case 1:
865 			/* dec bitmap */
866 			sm_set_bitmap(ic->bitmap, bit, 0);
867 			(*nr_allocations)--;
868 			ll->nr_allocated--;
869 			le32_add_cpu(&ic->ie_disk.nr_free, 1);
870 			ic->ie_disk.none_free_before =
871 				cpu_to_le32(min(le32_to_cpu(ic->ie_disk.none_free_before), bit));
872 			break;
873 
874 		case 2:
875 			/* dec bitmap and insert into overflow */
876 			sm_set_bitmap(ic->bitmap, bit, 1);
877 			break;
878 
879 		case 3:
880 			r = sm_ll_dec_overflow(ll, b, ic, &old);
881 			if (r < 0)
882 				return r;
883 
884 			if (old == 3) {
885 				r = ensure_bitmap(ll, ic);
886 				if (r)
887 					return r;
888 
889 				sm_set_bitmap(ic->bitmap, bit, 2);
890 			}
891 			break;
892 		}
893 	}
894 
895 	*new_b = b;
896 	return 0;
897 }
898 
899 static int __sm_ll_dec(struct ll_disk *ll, dm_block_t b, dm_block_t e,
900 		       int32_t *nr_allocations, dm_block_t *new_b)
901 {
902 	int r;
903 	uint32_t bit, bit_end;
904 	struct inc_context ic;
905 	dm_block_t index = b;
906 
907 	init_inc_context(&ic);
908 
909 	bit = do_div(index, ll->entries_per_block);
910 	r = ll->load_ie(ll, index, &ic.ie_disk);
911 	if (r < 0)
912 		return r;
913 
914 	r = shadow_bitmap(ll, &ic);
915 	if (r)
916 		return r;
917 
918 	bit_end = min(bit + (e - b), (dm_block_t) ll->entries_per_block);
919 	r = sm_ll_dec_bitmap(ll, b, bit, bit_end, &ic, nr_allocations, new_b);
920 	exit_inc_context(ll, &ic);
921 
922 	if (r)
923 		return r;
924 
925 	return ll->save_ie(ll, index, &ic.ie_disk);
926 }
927 
928 int sm_ll_dec(struct ll_disk *ll, dm_block_t b, dm_block_t e,
929 	      int32_t *nr_allocations)
930 {
931 	*nr_allocations = 0;
932 	while (b != e) {
933 		int r = __sm_ll_dec(ll, b, e, nr_allocations, &b);
934 
935 		if (r)
936 			return r;
937 	}
938 
939 	return 0;
940 }
941 
942 /*----------------------------------------------------------------*/
943 
944 int sm_ll_commit(struct ll_disk *ll)
945 {
946 	int r = 0;
947 
948 	if (ll->bitmap_index_changed) {
949 		r = ll->commit(ll);
950 		if (!r)
951 			ll->bitmap_index_changed = false;
952 	}
953 
954 	return r;
955 }
956 
957 /*----------------------------------------------------------------*/
958 
959 static int metadata_ll_load_ie(struct ll_disk *ll, dm_block_t index,
960 			       struct disk_index_entry *ie)
961 {
962 	memcpy(ie, ll->mi_le.index + index, sizeof(*ie));
963 	return 0;
964 }
965 
966 static int metadata_ll_save_ie(struct ll_disk *ll, dm_block_t index,
967 			       struct disk_index_entry *ie)
968 {
969 	ll->bitmap_index_changed = true;
970 	memcpy(ll->mi_le.index + index, ie, sizeof(*ie));
971 	return 0;
972 }
973 
974 static int metadata_ll_init_index(struct ll_disk *ll)
975 {
976 	int r;
977 	struct dm_block *b;
978 
979 	r = dm_tm_new_block(ll->tm, &index_validator, &b);
980 	if (r < 0)
981 		return r;
982 
983 	ll->bitmap_root = dm_block_location(b);
984 
985 	dm_tm_unlock(ll->tm, b);
986 
987 	return 0;
988 }
989 
990 static int metadata_ll_open(struct ll_disk *ll)
991 {
992 	int r;
993 	struct dm_block *block;
994 
995 	r = dm_tm_read_lock(ll->tm, ll->bitmap_root,
996 			    &index_validator, &block);
997 	if (r)
998 		return r;
999 
1000 	memcpy(&ll->mi_le, dm_block_data(block), sizeof(ll->mi_le));
1001 	dm_tm_unlock(ll->tm, block);
1002 
1003 	return 0;
1004 }
1005 
1006 static dm_block_t metadata_ll_max_entries(struct ll_disk *ll)
1007 {
1008 	return MAX_METADATA_BITMAPS;
1009 }
1010 
1011 static int metadata_ll_commit(struct ll_disk *ll)
1012 {
1013 	int r, inc;
1014 	struct dm_block *b;
1015 
1016 	r = dm_tm_shadow_block(ll->tm, ll->bitmap_root, &index_validator, &b, &inc);
1017 	if (r)
1018 		return r;
1019 
1020 	memcpy(dm_block_data(b), &ll->mi_le, sizeof(ll->mi_le));
1021 	ll->bitmap_root = dm_block_location(b);
1022 
1023 	dm_tm_unlock(ll->tm, b);
1024 
1025 	return 0;
1026 }
1027 
1028 int sm_ll_new_metadata(struct ll_disk *ll, struct dm_transaction_manager *tm)
1029 {
1030 	int r;
1031 
1032 	r = sm_ll_init(ll, tm);
1033 	if (r < 0)
1034 		return r;
1035 
1036 	ll->load_ie = metadata_ll_load_ie;
1037 	ll->save_ie = metadata_ll_save_ie;
1038 	ll->init_index = metadata_ll_init_index;
1039 	ll->open_index = metadata_ll_open;
1040 	ll->max_entries = metadata_ll_max_entries;
1041 	ll->commit = metadata_ll_commit;
1042 
1043 	ll->nr_blocks = 0;
1044 	ll->nr_allocated = 0;
1045 
1046 	r = ll->init_index(ll);
1047 	if (r < 0)
1048 		return r;
1049 
1050 	r = dm_btree_empty(&ll->ref_count_info, &ll->ref_count_root);
1051 	if (r < 0)
1052 		return r;
1053 
1054 	return 0;
1055 }
1056 
1057 int sm_ll_open_metadata(struct ll_disk *ll, struct dm_transaction_manager *tm,
1058 			void *root_le, size_t len)
1059 {
1060 	int r;
1061 	struct disk_sm_root smr;
1062 
1063 	if (len < sizeof(struct disk_sm_root)) {
1064 		DMERR("sm_metadata root too small");
1065 		return -ENOMEM;
1066 	}
1067 
1068 	/*
1069 	 * We don't know the alignment of the root_le buffer, so need to
1070 	 * copy into a new structure.
1071 	 */
1072 	memcpy(&smr, root_le, sizeof(smr));
1073 
1074 	r = sm_ll_init(ll, tm);
1075 	if (r < 0)
1076 		return r;
1077 
1078 	ll->load_ie = metadata_ll_load_ie;
1079 	ll->save_ie = metadata_ll_save_ie;
1080 	ll->init_index = metadata_ll_init_index;
1081 	ll->open_index = metadata_ll_open;
1082 	ll->max_entries = metadata_ll_max_entries;
1083 	ll->commit = metadata_ll_commit;
1084 
1085 	ll->nr_blocks = le64_to_cpu(smr.nr_blocks);
1086 	ll->nr_allocated = le64_to_cpu(smr.nr_allocated);
1087 	ll->bitmap_root = le64_to_cpu(smr.bitmap_root);
1088 	ll->ref_count_root = le64_to_cpu(smr.ref_count_root);
1089 
1090 	return ll->open_index(ll);
1091 }
1092 
1093 /*----------------------------------------------------------------*/
1094 
1095 static inline int ie_cache_writeback(struct ll_disk *ll, struct ie_cache *iec)
1096 {
1097 	iec->dirty = false;
1098 	__dm_bless_for_disk(iec->ie);
1099 	return dm_btree_insert(&ll->bitmap_info, ll->bitmap_root,
1100 			       &iec->index, &iec->ie, &ll->bitmap_root);
1101 }
1102 
1103 static inline unsigned int hash_index(dm_block_t index)
1104 {
1105 	return dm_hash_block(index, IE_CACHE_MASK);
1106 }
1107 
1108 static int disk_ll_load_ie(struct ll_disk *ll, dm_block_t index,
1109 			   struct disk_index_entry *ie)
1110 {
1111 	int r;
1112 	unsigned int h = hash_index(index);
1113 	struct ie_cache *iec = ll->ie_cache + h;
1114 
1115 	if (iec->valid) {
1116 		if (iec->index == index) {
1117 			memcpy(ie, &iec->ie, sizeof(*ie));
1118 			return 0;
1119 		}
1120 
1121 		if (iec->dirty) {
1122 			r = ie_cache_writeback(ll, iec);
1123 			if (r)
1124 				return r;
1125 		}
1126 	}
1127 
1128 	r = dm_btree_lookup(&ll->bitmap_info, ll->bitmap_root, &index, ie);
1129 	if (!r) {
1130 		iec->valid = true;
1131 		iec->dirty = false;
1132 		iec->index = index;
1133 		memcpy(&iec->ie, ie, sizeof(*ie));
1134 	}
1135 
1136 	return r;
1137 }
1138 
1139 static int disk_ll_save_ie(struct ll_disk *ll, dm_block_t index,
1140 			   struct disk_index_entry *ie)
1141 {
1142 	int r;
1143 	unsigned int h = hash_index(index);
1144 	struct ie_cache *iec = ll->ie_cache + h;
1145 
1146 	ll->bitmap_index_changed = true;
1147 	if (iec->valid) {
1148 		if (iec->index == index) {
1149 			memcpy(&iec->ie, ie, sizeof(*ie));
1150 			iec->dirty = true;
1151 			return 0;
1152 		}
1153 
1154 		if (iec->dirty) {
1155 			r = ie_cache_writeback(ll, iec);
1156 			if (r)
1157 				return r;
1158 		}
1159 	}
1160 
1161 	iec->valid = true;
1162 	iec->dirty = true;
1163 	iec->index = index;
1164 	memcpy(&iec->ie, ie, sizeof(*ie));
1165 	return 0;
1166 }
1167 
1168 static int disk_ll_init_index(struct ll_disk *ll)
1169 {
1170 	unsigned int i;
1171 
1172 	for (i = 0; i < IE_CACHE_SIZE; i++) {
1173 		struct ie_cache *iec = ll->ie_cache + i;
1174 
1175 		iec->valid = false;
1176 		iec->dirty = false;
1177 	}
1178 	return dm_btree_empty(&ll->bitmap_info, &ll->bitmap_root);
1179 }
1180 
1181 static int disk_ll_open(struct ll_disk *ll)
1182 {
1183 	return 0;
1184 }
1185 
1186 static dm_block_t disk_ll_max_entries(struct ll_disk *ll)
1187 {
1188 	return -1ULL;
1189 }
1190 
1191 static int disk_ll_commit(struct ll_disk *ll)
1192 {
1193 	int r = 0;
1194 	unsigned int i;
1195 
1196 	for (i = 0; i < IE_CACHE_SIZE; i++) {
1197 		struct ie_cache *iec = ll->ie_cache + i;
1198 
1199 		if (iec->valid && iec->dirty)
1200 			r = ie_cache_writeback(ll, iec);
1201 	}
1202 
1203 	return r;
1204 }
1205 
1206 int sm_ll_new_disk(struct ll_disk *ll, struct dm_transaction_manager *tm)
1207 {
1208 	int r;
1209 
1210 	r = sm_ll_init(ll, tm);
1211 	if (r < 0)
1212 		return r;
1213 
1214 	ll->load_ie = disk_ll_load_ie;
1215 	ll->save_ie = disk_ll_save_ie;
1216 	ll->init_index = disk_ll_init_index;
1217 	ll->open_index = disk_ll_open;
1218 	ll->max_entries = disk_ll_max_entries;
1219 	ll->commit = disk_ll_commit;
1220 
1221 	ll->nr_blocks = 0;
1222 	ll->nr_allocated = 0;
1223 
1224 	r = ll->init_index(ll);
1225 	if (r < 0)
1226 		return r;
1227 
1228 	r = dm_btree_empty(&ll->ref_count_info, &ll->ref_count_root);
1229 	if (r < 0)
1230 		return r;
1231 
1232 	return 0;
1233 }
1234 
1235 int sm_ll_open_disk(struct ll_disk *ll, struct dm_transaction_manager *tm,
1236 		    void *root_le, size_t len)
1237 {
1238 	int r;
1239 	struct disk_sm_root *smr = root_le;
1240 
1241 	if (len < sizeof(struct disk_sm_root)) {
1242 		DMERR("sm_metadata root too small");
1243 		return -ENOMEM;
1244 	}
1245 
1246 	r = sm_ll_init(ll, tm);
1247 	if (r < 0)
1248 		return r;
1249 
1250 	ll->load_ie = disk_ll_load_ie;
1251 	ll->save_ie = disk_ll_save_ie;
1252 	ll->init_index = disk_ll_init_index;
1253 	ll->open_index = disk_ll_open;
1254 	ll->max_entries = disk_ll_max_entries;
1255 	ll->commit = disk_ll_commit;
1256 
1257 	ll->nr_blocks = le64_to_cpu(smr->nr_blocks);
1258 	ll->nr_allocated = le64_to_cpu(smr->nr_allocated);
1259 	ll->bitmap_root = le64_to_cpu(smr->bitmap_root);
1260 	ll->ref_count_root = le64_to_cpu(smr->ref_count_root);
1261 
1262 	return ll->open_index(ll);
1263 }
1264 
1265 /*----------------------------------------------------------------*/
1266