1 /*
2  * Copyright (C) 2011 Red Hat, Inc.
3  *
4  * This file is released under the GPL.
5  */
6 
7 #include "dm-space-map-common.h"
8 #include "dm-transaction-manager.h"
9 
10 #include <linux/bitops.h>
11 #include <linux/device-mapper.h>
12 
13 #define DM_MSG_PREFIX "space map common"
14 
15 /*----------------------------------------------------------------*/
16 
17 /*
18  * Index validator.
19  */
20 #define INDEX_CSUM_XOR 160478
21 
22 static void index_prepare_for_write(struct dm_block_validator *v,
23 				    struct dm_block *b,
24 				    size_t block_size)
25 {
26 	struct disk_metadata_index *mi_le = dm_block_data(b);
27 
28 	mi_le->blocknr = cpu_to_le64(dm_block_location(b));
29 	mi_le->csum = cpu_to_le32(dm_bm_checksum(&mi_le->padding,
30 						 block_size - sizeof(__le32),
31 						 INDEX_CSUM_XOR));
32 }
33 
34 static int index_check(struct dm_block_validator *v,
35 		       struct dm_block *b,
36 		       size_t block_size)
37 {
38 	struct disk_metadata_index *mi_le = dm_block_data(b);
39 	__le32 csum_disk;
40 
41 	if (dm_block_location(b) != le64_to_cpu(mi_le->blocknr)) {
42 		DMERR_LIMIT("index_check failed: blocknr %llu != wanted %llu",
43 			    le64_to_cpu(mi_le->blocknr), dm_block_location(b));
44 		return -ENOTBLK;
45 	}
46 
47 	csum_disk = cpu_to_le32(dm_bm_checksum(&mi_le->padding,
48 					       block_size - sizeof(__le32),
49 					       INDEX_CSUM_XOR));
50 	if (csum_disk != mi_le->csum) {
51 		DMERR_LIMIT("index_check failed: csum %u != wanted %u",
52 			    le32_to_cpu(csum_disk), le32_to_cpu(mi_le->csum));
53 		return -EILSEQ;
54 	}
55 
56 	return 0;
57 }
58 
59 static struct dm_block_validator index_validator = {
60 	.name = "index",
61 	.prepare_for_write = index_prepare_for_write,
62 	.check = index_check
63 };
64 
65 /*----------------------------------------------------------------*/
66 
67 /*
68  * Bitmap validator
69  */
70 #define BITMAP_CSUM_XOR 240779
71 
72 static void dm_bitmap_prepare_for_write(struct dm_block_validator *v,
73 					struct dm_block *b,
74 					size_t block_size)
75 {
76 	struct disk_bitmap_header *disk_header = dm_block_data(b);
77 
78 	disk_header->blocknr = cpu_to_le64(dm_block_location(b));
79 	disk_header->csum = cpu_to_le32(dm_bm_checksum(&disk_header->not_used,
80 						       block_size - sizeof(__le32),
81 						       BITMAP_CSUM_XOR));
82 }
83 
84 static int dm_bitmap_check(struct dm_block_validator *v,
85 			   struct dm_block *b,
86 			   size_t block_size)
87 {
88 	struct disk_bitmap_header *disk_header = dm_block_data(b);
89 	__le32 csum_disk;
90 
91 	if (dm_block_location(b) != le64_to_cpu(disk_header->blocknr)) {
92 		DMERR_LIMIT("bitmap check failed: blocknr %llu != wanted %llu",
93 			    le64_to_cpu(disk_header->blocknr), dm_block_location(b));
94 		return -ENOTBLK;
95 	}
96 
97 	csum_disk = cpu_to_le32(dm_bm_checksum(&disk_header->not_used,
98 					       block_size - sizeof(__le32),
99 					       BITMAP_CSUM_XOR));
100 	if (csum_disk != disk_header->csum) {
101 		DMERR_LIMIT("bitmap check failed: csum %u != wanted %u",
102 			    le32_to_cpu(csum_disk), le32_to_cpu(disk_header->csum));
103 		return -EILSEQ;
104 	}
105 
106 	return 0;
107 }
108 
109 static struct dm_block_validator dm_sm_bitmap_validator = {
110 	.name = "sm_bitmap",
111 	.prepare_for_write = dm_bitmap_prepare_for_write,
112 	.check = dm_bitmap_check,
113 };
114 
115 /*----------------------------------------------------------------*/
116 
117 #define ENTRIES_PER_WORD 32
118 #define ENTRIES_SHIFT	5
119 
120 static void *dm_bitmap_data(struct dm_block *b)
121 {
122 	return dm_block_data(b) + sizeof(struct disk_bitmap_header);
123 }
124 
125 #define WORD_MASK_HIGH 0xAAAAAAAAAAAAAAAAULL
126 
127 static unsigned dm_bitmap_word_used(void *addr, unsigned b)
128 {
129 	__le64 *words_le = addr;
130 	__le64 *w_le = words_le + (b >> ENTRIES_SHIFT);
131 
132 	uint64_t bits = le64_to_cpu(*w_le);
133 	uint64_t mask = (bits + WORD_MASK_HIGH + 1) & WORD_MASK_HIGH;
134 
135 	return !(~bits & mask);
136 }
137 
138 static unsigned sm_lookup_bitmap(void *addr, unsigned b)
139 {
140 	__le64 *words_le = addr;
141 	__le64 *w_le = words_le + (b >> ENTRIES_SHIFT);
142 	unsigned hi, lo;
143 
144 	b = (b & (ENTRIES_PER_WORD - 1)) << 1;
145 	hi = !!test_bit_le(b, (void *) w_le);
146 	lo = !!test_bit_le(b + 1, (void *) w_le);
147 	return (hi << 1) | lo;
148 }
149 
150 static void sm_set_bitmap(void *addr, unsigned b, unsigned val)
151 {
152 	__le64 *words_le = addr;
153 	__le64 *w_le = words_le + (b >> ENTRIES_SHIFT);
154 
155 	b = (b & (ENTRIES_PER_WORD - 1)) << 1;
156 
157 	if (val & 2)
158 		__set_bit_le(b, (void *) w_le);
159 	else
160 		__clear_bit_le(b, (void *) w_le);
161 
162 	if (val & 1)
163 		__set_bit_le(b + 1, (void *) w_le);
164 	else
165 		__clear_bit_le(b + 1, (void *) w_le);
166 }
167 
168 static int sm_find_free(void *addr, unsigned begin, unsigned end,
169 			unsigned *result)
170 {
171 	while (begin < end) {
172 		if (!(begin & (ENTRIES_PER_WORD - 1)) &&
173 		    dm_bitmap_word_used(addr, begin)) {
174 			begin += ENTRIES_PER_WORD;
175 			continue;
176 		}
177 
178 		if (!sm_lookup_bitmap(addr, begin)) {
179 			*result = begin;
180 			return 0;
181 		}
182 
183 		begin++;
184 	}
185 
186 	return -ENOSPC;
187 }
188 
189 /*----------------------------------------------------------------*/
190 
191 static int sm_ll_init(struct ll_disk *ll, struct dm_transaction_manager *tm)
192 {
193 	memset(ll, 0, sizeof(struct ll_disk));
194 
195 	ll->tm = tm;
196 
197 	ll->bitmap_info.tm = tm;
198 	ll->bitmap_info.levels = 1;
199 
200 	/*
201 	 * Because the new bitmap blocks are created via a shadow
202 	 * operation, the old entry has already had its reference count
203 	 * decremented and we don't need the btree to do any bookkeeping.
204 	 */
205 	ll->bitmap_info.value_type.size = sizeof(struct disk_index_entry);
206 	ll->bitmap_info.value_type.inc = NULL;
207 	ll->bitmap_info.value_type.dec = NULL;
208 	ll->bitmap_info.value_type.equal = NULL;
209 
210 	ll->ref_count_info.tm = tm;
211 	ll->ref_count_info.levels = 1;
212 	ll->ref_count_info.value_type.size = sizeof(uint32_t);
213 	ll->ref_count_info.value_type.inc = NULL;
214 	ll->ref_count_info.value_type.dec = NULL;
215 	ll->ref_count_info.value_type.equal = NULL;
216 
217 	ll->block_size = dm_bm_block_size(dm_tm_get_bm(tm));
218 
219 	if (ll->block_size > (1 << 30)) {
220 		DMERR("block size too big to hold bitmaps");
221 		return -EINVAL;
222 	}
223 
224 	ll->entries_per_block = (ll->block_size - sizeof(struct disk_bitmap_header)) *
225 		ENTRIES_PER_BYTE;
226 	ll->nr_blocks = 0;
227 	ll->bitmap_root = 0;
228 	ll->ref_count_root = 0;
229 	ll->bitmap_index_changed = false;
230 
231 	return 0;
232 }
233 
234 int sm_ll_extend(struct ll_disk *ll, dm_block_t extra_blocks)
235 {
236 	int r;
237 	dm_block_t i, nr_blocks, nr_indexes;
238 	unsigned old_blocks, blocks;
239 
240 	nr_blocks = ll->nr_blocks + extra_blocks;
241 	old_blocks = dm_sector_div_up(ll->nr_blocks, ll->entries_per_block);
242 	blocks = dm_sector_div_up(nr_blocks, ll->entries_per_block);
243 
244 	nr_indexes = dm_sector_div_up(nr_blocks, ll->entries_per_block);
245 	if (nr_indexes > ll->max_entries(ll)) {
246 		DMERR("space map too large");
247 		return -EINVAL;
248 	}
249 
250 	/*
251 	 * We need to set this before the dm_tm_new_block() call below.
252 	 */
253 	ll->nr_blocks = nr_blocks;
254 	for (i = old_blocks; i < blocks; i++) {
255 		struct dm_block *b;
256 		struct disk_index_entry idx;
257 
258 		r = dm_tm_new_block(ll->tm, &dm_sm_bitmap_validator, &b);
259 		if (r < 0)
260 			return r;
261 
262 		idx.blocknr = cpu_to_le64(dm_block_location(b));
263 
264 		dm_tm_unlock(ll->tm, b);
265 
266 		idx.nr_free = cpu_to_le32(ll->entries_per_block);
267 		idx.none_free_before = 0;
268 
269 		r = ll->save_ie(ll, i, &idx);
270 		if (r < 0)
271 			return r;
272 	}
273 
274 	return 0;
275 }
276 
277 int sm_ll_lookup_bitmap(struct ll_disk *ll, dm_block_t b, uint32_t *result)
278 {
279 	int r;
280 	dm_block_t index = b;
281 	struct disk_index_entry ie_disk;
282 	struct dm_block *blk;
283 
284 	b = do_div(index, ll->entries_per_block);
285 	r = ll->load_ie(ll, index, &ie_disk);
286 	if (r < 0)
287 		return r;
288 
289 	r = dm_tm_read_lock(ll->tm, le64_to_cpu(ie_disk.blocknr),
290 			    &dm_sm_bitmap_validator, &blk);
291 	if (r < 0)
292 		return r;
293 
294 	*result = sm_lookup_bitmap(dm_bitmap_data(blk), b);
295 
296 	dm_tm_unlock(ll->tm, blk);
297 
298 	return 0;
299 }
300 
301 static int sm_ll_lookup_big_ref_count(struct ll_disk *ll, dm_block_t b,
302 				      uint32_t *result)
303 {
304 	__le32 le_rc;
305 	int r;
306 
307 	r = dm_btree_lookup(&ll->ref_count_info, ll->ref_count_root, &b, &le_rc);
308 	if (r < 0)
309 		return r;
310 
311 	*result = le32_to_cpu(le_rc);
312 
313 	return r;
314 }
315 
316 int sm_ll_lookup(struct ll_disk *ll, dm_block_t b, uint32_t *result)
317 {
318 	int r = sm_ll_lookup_bitmap(ll, b, result);
319 
320 	if (r)
321 		return r;
322 
323 	if (*result != 3)
324 		return r;
325 
326 	return sm_ll_lookup_big_ref_count(ll, b, result);
327 }
328 
329 int sm_ll_find_free_block(struct ll_disk *ll, dm_block_t begin,
330 			  dm_block_t end, dm_block_t *result)
331 {
332 	int r;
333 	struct disk_index_entry ie_disk;
334 	dm_block_t i, index_begin = begin;
335 	dm_block_t index_end = dm_sector_div_up(end, ll->entries_per_block);
336 
337 	/*
338 	 * FIXME: Use shifts
339 	 */
340 	begin = do_div(index_begin, ll->entries_per_block);
341 	end = do_div(end, ll->entries_per_block);
342 
343 	for (i = index_begin; i < index_end; i++, begin = 0) {
344 		struct dm_block *blk;
345 		unsigned position;
346 		uint32_t bit_end;
347 
348 		r = ll->load_ie(ll, i, &ie_disk);
349 		if (r < 0)
350 			return r;
351 
352 		if (le32_to_cpu(ie_disk.nr_free) == 0)
353 			continue;
354 
355 		r = dm_tm_read_lock(ll->tm, le64_to_cpu(ie_disk.blocknr),
356 				    &dm_sm_bitmap_validator, &blk);
357 		if (r < 0)
358 			return r;
359 
360 		bit_end = (i == index_end - 1) ?  end : ll->entries_per_block;
361 
362 		r = sm_find_free(dm_bitmap_data(blk),
363 				 max_t(unsigned, begin, le32_to_cpu(ie_disk.none_free_before)),
364 				 bit_end, &position);
365 		if (r == -ENOSPC) {
366 			/*
367 			 * This might happen because we started searching
368 			 * part way through the bitmap.
369 			 */
370 			dm_tm_unlock(ll->tm, blk);
371 			continue;
372 
373 		} else if (r < 0) {
374 			dm_tm_unlock(ll->tm, blk);
375 			return r;
376 		}
377 
378 		dm_tm_unlock(ll->tm, blk);
379 
380 		*result = i * ll->entries_per_block + (dm_block_t) position;
381 		return 0;
382 	}
383 
384 	return -ENOSPC;
385 }
386 
387 static int sm_ll_mutate(struct ll_disk *ll, dm_block_t b,
388 			int (*mutator)(void *context, uint32_t old, uint32_t *new),
389 			void *context, enum allocation_event *ev)
390 {
391 	int r;
392 	uint32_t bit, old, ref_count;
393 	struct dm_block *nb;
394 	dm_block_t index = b;
395 	struct disk_index_entry ie_disk;
396 	void *bm_le;
397 	int inc;
398 
399 	bit = do_div(index, ll->entries_per_block);
400 	r = ll->load_ie(ll, index, &ie_disk);
401 	if (r < 0)
402 		return r;
403 
404 	r = dm_tm_shadow_block(ll->tm, le64_to_cpu(ie_disk.blocknr),
405 			       &dm_sm_bitmap_validator, &nb, &inc);
406 	if (r < 0) {
407 		DMERR("dm_tm_shadow_block() failed");
408 		return r;
409 	}
410 	ie_disk.blocknr = cpu_to_le64(dm_block_location(nb));
411 
412 	bm_le = dm_bitmap_data(nb);
413 	old = sm_lookup_bitmap(bm_le, bit);
414 
415 	if (old > 2) {
416 		r = sm_ll_lookup_big_ref_count(ll, b, &old);
417 		if (r < 0) {
418 			dm_tm_unlock(ll->tm, nb);
419 			return r;
420 		}
421 	}
422 
423 	r = mutator(context, old, &ref_count);
424 	if (r) {
425 		dm_tm_unlock(ll->tm, nb);
426 		return r;
427 	}
428 
429 	if (ref_count <= 2) {
430 		sm_set_bitmap(bm_le, bit, ref_count);
431 
432 		dm_tm_unlock(ll->tm, nb);
433 
434 		if (old > 2) {
435 			r = dm_btree_remove(&ll->ref_count_info,
436 					    ll->ref_count_root,
437 					    &b, &ll->ref_count_root);
438 			if (r)
439 				return r;
440 		}
441 
442 	} else {
443 		__le32 le_rc = cpu_to_le32(ref_count);
444 
445 		sm_set_bitmap(bm_le, bit, 3);
446 		dm_tm_unlock(ll->tm, nb);
447 
448 		__dm_bless_for_disk(&le_rc);
449 		r = dm_btree_insert(&ll->ref_count_info, ll->ref_count_root,
450 				    &b, &le_rc, &ll->ref_count_root);
451 		if (r < 0) {
452 			DMERR("ref count insert failed");
453 			return r;
454 		}
455 	}
456 
457 	if (ref_count && !old) {
458 		*ev = SM_ALLOC;
459 		ll->nr_allocated++;
460 		le32_add_cpu(&ie_disk.nr_free, -1);
461 		if (le32_to_cpu(ie_disk.none_free_before) == bit)
462 			ie_disk.none_free_before = cpu_to_le32(bit + 1);
463 
464 	} else if (old && !ref_count) {
465 		*ev = SM_FREE;
466 		ll->nr_allocated--;
467 		le32_add_cpu(&ie_disk.nr_free, 1);
468 		ie_disk.none_free_before = cpu_to_le32(min(le32_to_cpu(ie_disk.none_free_before), bit));
469 	} else
470 		*ev = SM_NONE;
471 
472 	return ll->save_ie(ll, index, &ie_disk);
473 }
474 
475 static int set_ref_count(void *context, uint32_t old, uint32_t *new)
476 {
477 	*new = *((uint32_t *) context);
478 	return 0;
479 }
480 
481 int sm_ll_insert(struct ll_disk *ll, dm_block_t b,
482 		 uint32_t ref_count, enum allocation_event *ev)
483 {
484 	return sm_ll_mutate(ll, b, set_ref_count, &ref_count, ev);
485 }
486 
487 static int inc_ref_count(void *context, uint32_t old, uint32_t *new)
488 {
489 	*new = old + 1;
490 	return 0;
491 }
492 
493 int sm_ll_inc(struct ll_disk *ll, dm_block_t b, enum allocation_event *ev)
494 {
495 	return sm_ll_mutate(ll, b, inc_ref_count, NULL, ev);
496 }
497 
498 static int dec_ref_count(void *context, uint32_t old, uint32_t *new)
499 {
500 	if (!old) {
501 		DMERR_LIMIT("unable to decrement a reference count below 0");
502 		return -EINVAL;
503 	}
504 
505 	*new = old - 1;
506 	return 0;
507 }
508 
509 int sm_ll_dec(struct ll_disk *ll, dm_block_t b, enum allocation_event *ev)
510 {
511 	return sm_ll_mutate(ll, b, dec_ref_count, NULL, ev);
512 }
513 
514 int sm_ll_commit(struct ll_disk *ll)
515 {
516 	int r = 0;
517 
518 	if (ll->bitmap_index_changed) {
519 		r = ll->commit(ll);
520 		if (!r)
521 			ll->bitmap_index_changed = false;
522 	}
523 
524 	return r;
525 }
526 
527 /*----------------------------------------------------------------*/
528 
529 static int metadata_ll_load_ie(struct ll_disk *ll, dm_block_t index,
530 			       struct disk_index_entry *ie)
531 {
532 	memcpy(ie, ll->mi_le.index + index, sizeof(*ie));
533 	return 0;
534 }
535 
536 static int metadata_ll_save_ie(struct ll_disk *ll, dm_block_t index,
537 			       struct disk_index_entry *ie)
538 {
539 	ll->bitmap_index_changed = true;
540 	memcpy(ll->mi_le.index + index, ie, sizeof(*ie));
541 	return 0;
542 }
543 
544 static int metadata_ll_init_index(struct ll_disk *ll)
545 {
546 	int r;
547 	struct dm_block *b;
548 
549 	r = dm_tm_new_block(ll->tm, &index_validator, &b);
550 	if (r < 0)
551 		return r;
552 
553 	ll->bitmap_root = dm_block_location(b);
554 
555 	dm_tm_unlock(ll->tm, b);
556 
557 	return 0;
558 }
559 
560 static int metadata_ll_open(struct ll_disk *ll)
561 {
562 	int r;
563 	struct dm_block *block;
564 
565 	r = dm_tm_read_lock(ll->tm, ll->bitmap_root,
566 			    &index_validator, &block);
567 	if (r)
568 		return r;
569 
570 	memcpy(&ll->mi_le, dm_block_data(block), sizeof(ll->mi_le));
571 	dm_tm_unlock(ll->tm, block);
572 
573 	return 0;
574 }
575 
576 static dm_block_t metadata_ll_max_entries(struct ll_disk *ll)
577 {
578 	return MAX_METADATA_BITMAPS;
579 }
580 
581 static int metadata_ll_commit(struct ll_disk *ll)
582 {
583 	int r, inc;
584 	struct dm_block *b;
585 
586 	r = dm_tm_shadow_block(ll->tm, ll->bitmap_root, &index_validator, &b, &inc);
587 	if (r)
588 		return r;
589 
590 	memcpy(dm_block_data(b), &ll->mi_le, sizeof(ll->mi_le));
591 	ll->bitmap_root = dm_block_location(b);
592 
593 	dm_tm_unlock(ll->tm, b);
594 
595 	return 0;
596 }
597 
598 int sm_ll_new_metadata(struct ll_disk *ll, struct dm_transaction_manager *tm)
599 {
600 	int r;
601 
602 	r = sm_ll_init(ll, tm);
603 	if (r < 0)
604 		return r;
605 
606 	ll->load_ie = metadata_ll_load_ie;
607 	ll->save_ie = metadata_ll_save_ie;
608 	ll->init_index = metadata_ll_init_index;
609 	ll->open_index = metadata_ll_open;
610 	ll->max_entries = metadata_ll_max_entries;
611 	ll->commit = metadata_ll_commit;
612 
613 	ll->nr_blocks = 0;
614 	ll->nr_allocated = 0;
615 
616 	r = ll->init_index(ll);
617 	if (r < 0)
618 		return r;
619 
620 	r = dm_btree_empty(&ll->ref_count_info, &ll->ref_count_root);
621 	if (r < 0)
622 		return r;
623 
624 	return 0;
625 }
626 
627 int sm_ll_open_metadata(struct ll_disk *ll, struct dm_transaction_manager *tm,
628 			void *root_le, size_t len)
629 {
630 	int r;
631 	struct disk_sm_root smr;
632 
633 	if (len < sizeof(struct disk_sm_root)) {
634 		DMERR("sm_metadata root too small");
635 		return -ENOMEM;
636 	}
637 
638 	/*
639 	 * We don't know the alignment of the root_le buffer, so need to
640 	 * copy into a new structure.
641 	 */
642 	memcpy(&smr, root_le, sizeof(smr));
643 
644 	r = sm_ll_init(ll, tm);
645 	if (r < 0)
646 		return r;
647 
648 	ll->load_ie = metadata_ll_load_ie;
649 	ll->save_ie = metadata_ll_save_ie;
650 	ll->init_index = metadata_ll_init_index;
651 	ll->open_index = metadata_ll_open;
652 	ll->max_entries = metadata_ll_max_entries;
653 	ll->commit = metadata_ll_commit;
654 
655 	ll->nr_blocks = le64_to_cpu(smr.nr_blocks);
656 	ll->nr_allocated = le64_to_cpu(smr.nr_allocated);
657 	ll->bitmap_root = le64_to_cpu(smr.bitmap_root);
658 	ll->ref_count_root = le64_to_cpu(smr.ref_count_root);
659 
660 	return ll->open_index(ll);
661 }
662 
663 /*----------------------------------------------------------------*/
664 
665 static int disk_ll_load_ie(struct ll_disk *ll, dm_block_t index,
666 			   struct disk_index_entry *ie)
667 {
668 	return dm_btree_lookup(&ll->bitmap_info, ll->bitmap_root, &index, ie);
669 }
670 
671 static int disk_ll_save_ie(struct ll_disk *ll, dm_block_t index,
672 			   struct disk_index_entry *ie)
673 {
674 	__dm_bless_for_disk(ie);
675 	return dm_btree_insert(&ll->bitmap_info, ll->bitmap_root,
676 			       &index, ie, &ll->bitmap_root);
677 }
678 
679 static int disk_ll_init_index(struct ll_disk *ll)
680 {
681 	return dm_btree_empty(&ll->bitmap_info, &ll->bitmap_root);
682 }
683 
684 static int disk_ll_open(struct ll_disk *ll)
685 {
686 	/* nothing to do */
687 	return 0;
688 }
689 
690 static dm_block_t disk_ll_max_entries(struct ll_disk *ll)
691 {
692 	return -1ULL;
693 }
694 
695 static int disk_ll_commit(struct ll_disk *ll)
696 {
697 	return 0;
698 }
699 
700 int sm_ll_new_disk(struct ll_disk *ll, struct dm_transaction_manager *tm)
701 {
702 	int r;
703 
704 	r = sm_ll_init(ll, tm);
705 	if (r < 0)
706 		return r;
707 
708 	ll->load_ie = disk_ll_load_ie;
709 	ll->save_ie = disk_ll_save_ie;
710 	ll->init_index = disk_ll_init_index;
711 	ll->open_index = disk_ll_open;
712 	ll->max_entries = disk_ll_max_entries;
713 	ll->commit = disk_ll_commit;
714 
715 	ll->nr_blocks = 0;
716 	ll->nr_allocated = 0;
717 
718 	r = ll->init_index(ll);
719 	if (r < 0)
720 		return r;
721 
722 	r = dm_btree_empty(&ll->ref_count_info, &ll->ref_count_root);
723 	if (r < 0)
724 		return r;
725 
726 	return 0;
727 }
728 
729 int sm_ll_open_disk(struct ll_disk *ll, struct dm_transaction_manager *tm,
730 		    void *root_le, size_t len)
731 {
732 	int r;
733 	struct disk_sm_root *smr = root_le;
734 
735 	if (len < sizeof(struct disk_sm_root)) {
736 		DMERR("sm_metadata root too small");
737 		return -ENOMEM;
738 	}
739 
740 	r = sm_ll_init(ll, tm);
741 	if (r < 0)
742 		return r;
743 
744 	ll->load_ie = disk_ll_load_ie;
745 	ll->save_ie = disk_ll_save_ie;
746 	ll->init_index = disk_ll_init_index;
747 	ll->open_index = disk_ll_open;
748 	ll->max_entries = disk_ll_max_entries;
749 	ll->commit = disk_ll_commit;
750 
751 	ll->nr_blocks = le64_to_cpu(smr->nr_blocks);
752 	ll->nr_allocated = le64_to_cpu(smr->nr_allocated);
753 	ll->bitmap_root = le64_to_cpu(smr->bitmap_root);
754 	ll->ref_count_root = le64_to_cpu(smr->ref_count_root);
755 
756 	return ll->open_index(ll);
757 }
758 
759 /*----------------------------------------------------------------*/
760