[deliverable/linux.git] / drivers / md / persistent-data / dm-space-map-common.c

/*
 * Copyright (C) 2011 Red Hat, Inc.
 *
 * This file is released under the GPL.
 */

#include "dm-space-map-common.h"
#include "dm-transaction-manager.h"

#include <linux/bitops.h>
#include <linux/device-mapper.h>

#define DM_MSG_PREFIX "space map common"

/*----------------------------------------------------------------*/

/*
 * Index validator.
 */
#define INDEX_CSUM_XOR 160478

static void index_prepare_for_write(struct dm_block_validator *v,
				    struct dm_block *b,
				    size_t block_size)
{
	struct disk_metadata_index *mi_le = dm_block_data(b);

	mi_le->blocknr = cpu_to_le64(dm_block_location(b));
	mi_le->csum = cpu_to_le32(dm_bm_checksum(&mi_le->padding,
						 block_size - sizeof(__le32),
						 INDEX_CSUM_XOR));
}

static int index_check(struct dm_block_validator *v,
		       struct dm_block *b,
		       size_t block_size)
{
	struct disk_metadata_index *mi_le = dm_block_data(b);
	__le32 csum_disk;

	if (dm_block_location(b) != le64_to_cpu(mi_le->blocknr)) {
		DMERR_LIMIT("index_check failed: blocknr %llu != wanted %llu",
			    le64_to_cpu(mi_le->blocknr), dm_block_location(b));
		return -ENOTBLK;
	}

	csum_disk = cpu_to_le32(dm_bm_checksum(&mi_le->padding,
					       block_size - sizeof(__le32),
					       INDEX_CSUM_XOR));
	if (csum_disk != mi_le->csum) {
		DMERR_LIMIT("index_check failed: csum %u != wanted %u",
			    le32_to_cpu(csum_disk), le32_to_cpu(mi_le->csum));
		return -EILSEQ;
	}

	return 0;
}

static struct dm_block_validator index_validator = {
	.name = "index",
	.prepare_for_write = index_prepare_for_write,
	.check = index_check
};

/*----------------------------------------------------------------*/

/*
 * Bitmap validator
 */
#define BITMAP_CSUM_XOR 240779

static void bitmap_prepare_for_write(struct dm_block_validator *v,
				     struct dm_block *b,
				     size_t block_size)
{
	struct disk_bitmap_header *disk_header = dm_block_data(b);

	disk_header->blocknr = cpu_to_le64(dm_block_location(b));
	disk_header->csum = cpu_to_le32(dm_bm_checksum(&disk_header->not_used,
						       block_size - sizeof(__le32),
						       BITMAP_CSUM_XOR));
}

static int bitmap_check(struct dm_block_validator *v,
			struct dm_block *b,
			size_t block_size)
{
	struct disk_bitmap_header *disk_header = dm_block_data(b);
	__le32 csum_disk;

	if (dm_block_location(b) != le64_to_cpu(disk_header->blocknr)) {
		DMERR_LIMIT("bitmap check failed: blocknr %llu != wanted %llu",
			    le64_to_cpu(disk_header->blocknr), dm_block_location(b));
		return -ENOTBLK;
	}

	csum_disk = cpu_to_le32(dm_bm_checksum(&disk_header->not_used,
					       block_size - sizeof(__le32),
					       BITMAP_CSUM_XOR));
	if (csum_disk != disk_header->csum) {
		DMERR_LIMIT("bitmap check failed: csum %u != wanted %u",
			    le32_to_cpu(csum_disk), le32_to_cpu(disk_header->csum));
		return -EILSEQ;
	}

	return 0;
}

static struct dm_block_validator dm_sm_bitmap_validator = {
	.name = "sm_bitmap",
	.prepare_for_write = bitmap_prepare_for_write,
	.check = bitmap_check
};

/*----------------------------------------------------------------*/

#define ENTRIES_PER_WORD 32
#define ENTRIES_SHIFT	5

static void *dm_bitmap_data(struct dm_block *b)
{
	return dm_block_data(b) + sizeof(struct disk_bitmap_header);
}

#define WORD_MASK_HIGH 0xAAAAAAAAAAAAAAAAULL

static unsigned bitmap_word_used(void *addr, unsigned b)
{
	__le64 *words_le = addr;
	__le64 *w_le = words_le + (b >> ENTRIES_SHIFT);

	uint64_t bits = le64_to_cpu(*w_le);
	uint64_t mask = (bits + WORD_MASK_HIGH + 1) & WORD_MASK_HIGH;

	return !(~bits & mask);
}

static unsigned sm_lookup_bitmap(void *addr, unsigned b)
{
	__le64 *words_le = addr;
	__le64 *w_le = words_le + (b >> ENTRIES_SHIFT);
	unsigned hi, lo;

	b = (b & (ENTRIES_PER_WORD - 1)) << 1;
	hi = !!test_bit_le(b, (void *) w_le);
	lo = !!test_bit_le(b + 1, (void *) w_le);
	return (hi << 1) | lo;
}

static void sm_set_bitmap(void *addr, unsigned b, unsigned val)
{
	__le64 *words_le = addr;
	__le64 *w_le = words_le + (b >> ENTRIES_SHIFT);

	b = (b & (ENTRIES_PER_WORD - 1)) << 1;

	if (val & 2)
		__set_bit_le(b, (void *) w_le);
	else
		__clear_bit_le(b, (void *) w_le);

	if (val & 1)
		__set_bit_le(b + 1, (void *) w_le);
	else
		__clear_bit_le(b + 1, (void *) w_le);
}

static int sm_find_free(void *addr, unsigned begin, unsigned end,
			unsigned *result)
{
	while (begin < end) {
		if (!(begin & (ENTRIES_PER_WORD - 1)) &&
		    bitmap_word_used(addr, begin)) {
			begin += ENTRIES_PER_WORD;
			continue;
		}

		if (!sm_lookup_bitmap(addr, begin)) {
			*result = begin;
			return 0;
		}

		begin++;
	}

	return -ENOSPC;
}

/*----------------------------------------------------------------*/

static int sm_ll_init(struct ll_disk *ll, struct dm_transaction_manager *tm)
{
	ll->tm = tm;

	ll->bitmap_info.tm = tm;
	ll->bitmap_info.levels = 1;

	/*
	 * Because the new bitmap blocks are created via a shadow
	 * operation, the old entry has already had its reference count
	 * decremented and we don't need the btree to do any bookkeeping.
	 */
	ll->bitmap_info.value_type.size = sizeof(struct disk_index_entry);
	ll->bitmap_info.value_type.inc = NULL;
	ll->bitmap_info.value_type.dec = NULL;
	ll->bitmap_info.value_type.equal = NULL;

	ll->ref_count_info.tm = tm;
	ll->ref_count_info.levels = 1;
	ll->ref_count_info.value_type.size = sizeof(uint32_t);
	ll->ref_count_info.value_type.inc = NULL;
	ll->ref_count_info.value_type.dec = NULL;
	ll->ref_count_info.value_type.equal = NULL;

	ll->block_size = dm_bm_block_size(dm_tm_get_bm(tm));

	if (ll->block_size > (1 << 30)) {
		DMERR("block size too big to hold bitmaps");
		return -EINVAL;
	}

	ll->entries_per_block = (ll->block_size - sizeof(struct disk_bitmap_header)) *
		ENTRIES_PER_BYTE;
	ll->nr_blocks = 0;
	ll->bitmap_root = 0;
	ll->ref_count_root = 0;
	ll->bitmap_index_changed = false;

	return 0;
}

int sm_ll_extend(struct ll_disk *ll, dm_block_t extra_blocks)
{
	int r;
	dm_block_t i, nr_blocks, nr_indexes;
	unsigned old_blocks, blocks;

	nr_blocks = ll->nr_blocks + extra_blocks;
	old_blocks = dm_sector_div_up(ll->nr_blocks, ll->entries_per_block);
	blocks = dm_sector_div_up(nr_blocks, ll->entries_per_block);

	nr_indexes = dm_sector_div_up(nr_blocks, ll->entries_per_block);
	if (nr_indexes > ll->max_entries(ll)) {
		DMERR("space map too large");
		return -EINVAL;
	}

	/*
	 * We need to set this before the dm_tm_new_block() call below.
	 */
	ll->nr_blocks = nr_blocks;
	for (i = old_blocks; i < blocks; i++) {
		struct dm_block *b;
		struct disk_index_entry idx;

		r = dm_tm_new_block(ll->tm, &dm_sm_bitmap_validator, &b);
		if (r < 0)
			return r;

		idx.blocknr = cpu_to_le64(dm_block_location(b));

		r = dm_tm_unlock(ll->tm, b);
		if (r < 0)
			return r;

		idx.nr_free = cpu_to_le32(ll->entries_per_block);
		idx.none_free_before = 0;

		r = ll->save_ie(ll, i, &idx);
		if (r < 0)
			return r;
	}

	return 0;
}

int sm_ll_lookup_bitmap(struct ll_disk *ll, dm_block_t b, uint32_t *result)
{
	int r;
	dm_block_t index = b;
	struct disk_index_entry ie_disk;
	struct dm_block *blk;

	b = do_div(index, ll->entries_per_block);
	r = ll->load_ie(ll, index, &ie_disk);
	if (r < 0)
		return r;

	r = dm_tm_read_lock(ll->tm, le64_to_cpu(ie_disk.blocknr),
			    &dm_sm_bitmap_validator, &blk);
	if (r < 0)
		return r;

	*result = sm_lookup_bitmap(dm_bitmap_data(blk), b);

	return dm_tm_unlock(ll->tm, blk);
}

static int sm_ll_lookup_big_ref_count(struct ll_disk *ll, dm_block_t b,
				      uint32_t *result)
{
	__le32 le_rc;
	int r;

	r = dm_btree_lookup(&ll->ref_count_info, ll->ref_count_root, &b, &le_rc);
	if (r < 0)
		return r;

	*result = le32_to_cpu(le_rc);

	return r;
}

int sm_ll_lookup(struct ll_disk *ll, dm_block_t b, uint32_t *result)
{
	int r = sm_ll_lookup_bitmap(ll, b, result);

	if (r)
		return r;

	if (*result != 3)
		return r;

	return sm_ll_lookup_big_ref_count(ll, b, result);
}

int sm_ll_find_free_block(struct ll_disk *ll, dm_block_t begin,
			  dm_block_t end, dm_block_t *result)
{
	int r;
	struct disk_index_entry ie_disk;
	dm_block_t i, index_begin = begin;
	dm_block_t index_end = dm_sector_div_up(end, ll->entries_per_block);

	/*
	 * FIXME: Use shifts
	 */
	begin = do_div(index_begin, ll->entries_per_block);
	end = do_div(end, ll->entries_per_block);

	for (i = index_begin; i < index_end; i++, begin = 0) {
		struct dm_block *blk;
		unsigned position;
		uint32_t bit_end;

		r = ll->load_ie(ll, i, &ie_disk);
		if (r < 0)
			return r;

		if (le32_to_cpu(ie_disk.nr_free) == 0)
			continue;

		r = dm_tm_read_lock(ll->tm, le64_to_cpu(ie_disk.blocknr),
				    &dm_sm_bitmap_validator, &blk);
		if (r < 0)
			return r;

		bit_end = (i == index_end - 1) ?  end : ll->entries_per_block;

		r = sm_find_free(dm_bitmap_data(blk),
				 max_t(unsigned, begin, le32_to_cpu(ie_disk.none_free_before)),
				 bit_end, &position);
		if (r == -ENOSPC) {
			/*
			 * This might happen because we started searching
			 * part way through the bitmap.
			 */
			dm_tm_unlock(ll->tm, blk);
			continue;

		} else if (r < 0) {
			dm_tm_unlock(ll->tm, blk);
			return r;
		}

		r = dm_tm_unlock(ll->tm, blk);
		if (r < 0)
			return r;

		*result = i * ll->entries_per_block + (dm_block_t) position;
		return 0;
	}

	return -ENOSPC;
}

static int sm_ll_mutate(struct ll_disk *ll, dm_block_t b,
			int (*mutator)(void *context, uint32_t old, uint32_t *new),
			void *context, enum allocation_event *ev)
{
	int r;
	uint32_t bit, old, ref_count;
	struct dm_block *nb;
	dm_block_t index = b;
	struct disk_index_entry ie_disk;
	void *bm_le;
	int inc;

	bit = do_div(index, ll->entries_per_block);
	r = ll->load_ie(ll, index, &ie_disk);
	if (r < 0)
		return r;

	r = dm_tm_shadow_block(ll->tm, le64_to_cpu(ie_disk.blocknr),
			       &dm_sm_bitmap_validator, &nb, &inc);
	if (r < 0) {
		DMERR("dm_tm_shadow_block() failed");
		return r;
	}
	ie_disk.blocknr = cpu_to_le64(dm_block_location(nb));

	bm_le = dm_bitmap_data(nb);
	old = sm_lookup_bitmap(bm_le, bit);

	if (old > 2) {
		r = sm_ll_lookup_big_ref_count(ll, b, &old);
		if (r < 0) {
			dm_tm_unlock(ll->tm, nb);
			return r;
		}
	}

	r = mutator(context, old, &ref_count);
	if (r) {
		dm_tm_unlock(ll->tm, nb);
		return r;
	}

	if (ref_count <= 2) {
		sm_set_bitmap(bm_le, bit, ref_count);

		r = dm_tm_unlock(ll->tm, nb);
		if (r < 0)
			return r;

		if (old > 2) {
			r = dm_btree_remove(&ll->ref_count_info,
					    ll->ref_count_root,
					    &b, &ll->ref_count_root);
			if (r)
				return r;
		}

	} else {
		__le32 le_rc = cpu_to_le32(ref_count);

		sm_set_bitmap(bm_le, bit, 3);
		r = dm_tm_unlock(ll->tm, nb);
		if (r < 0)
			return r;

		__dm_bless_for_disk(&le_rc);
		r = dm_btree_insert(&ll->ref_count_info, ll->ref_count_root,
				    &b, &le_rc, &ll->ref_count_root);
		if (r < 0) {
			DMERR("ref count insert failed");
			return r;
		}
	}

	if (ref_count && !old) {
		*ev = SM_ALLOC;
		ll->nr_allocated++;
		le32_add_cpu(&ie_disk.nr_free, -1);
		if (le32_to_cpu(ie_disk.none_free_before) == bit)
			ie_disk.none_free_before = cpu_to_le32(bit + 1);

	} else if (old && !ref_count) {
		*ev = SM_FREE;
		ll->nr_allocated--;
		le32_add_cpu(&ie_disk.nr_free, 1);
		ie_disk.none_free_before = cpu_to_le32(min(le32_to_cpu(ie_disk.none_free_before), bit));
	}

	return ll->save_ie(ll, index, &ie_disk);
}

static int set_ref_count(void *context, uint32_t old, uint32_t *new)
{
	*new = *((uint32_t *) context);
	return 0;
}

int sm_ll_insert(struct ll_disk *ll, dm_block_t b,
		 uint32_t ref_count, enum allocation_event *ev)
{
	return sm_ll_mutate(ll, b, set_ref_count, &ref_count, ev);
}

static int inc_ref_count(void *context, uint32_t old, uint32_t *new)
{
	*new = old + 1;
	return 0;
}

int sm_ll_inc(struct ll_disk *ll, dm_block_t b, enum allocation_event *ev)
{
	return sm_ll_mutate(ll, b, inc_ref_count, NULL, ev);
}

static int dec_ref_count(void *context, uint32_t old, uint32_t *new)
{
	if (!old) {
		DMERR_LIMIT("unable to decrement a reference count below 0");
		return -EINVAL;
	}

	*new = old - 1;
	return 0;
}

int sm_ll_dec(struct ll_disk *ll, dm_block_t b, enum allocation_event *ev)
{
	return sm_ll_mutate(ll, b, dec_ref_count, NULL, ev);
}

int sm_ll_commit(struct ll_disk *ll)
{
	int r = 0;

	if (ll->bitmap_index_changed) {
		r = ll->commit(ll);
		if (!r)
			ll->bitmap_index_changed = false;
	}

	return r;
}

/*----------------------------------------------------------------*/

static int metadata_ll_load_ie(struct ll_disk *ll, dm_block_t index,
			       struct disk_index_entry *ie)
{
	memcpy(ie, ll->mi_le.index + index, sizeof(*ie));
	return 0;
}

static int metadata_ll_save_ie(struct ll_disk *ll, dm_block_t index,
			       struct disk_index_entry *ie)
{
	ll->bitmap_index_changed = true;
	memcpy(ll->mi_le.index + index, ie, sizeof(*ie));
	return 0;
}

static int metadata_ll_init_index(struct ll_disk *ll)
{
	int r;
	struct dm_block *b;

	r = dm_tm_new_block(ll->tm, &index_validator, &b);
	if (r < 0)
		return r;

	memcpy(dm_block_data(b), &ll->mi_le, sizeof(ll->mi_le));
	ll->bitmap_root = dm_block_location(b);

	return dm_tm_unlock(ll->tm, b);
}

static int metadata_ll_open(struct ll_disk *ll)
{
	int r;
	struct dm_block *block;

	r = dm_tm_read_lock(ll->tm, ll->bitmap_root,
			    &index_validator, &block);
	if (r)
		return r;

	memcpy(&ll->mi_le, dm_block_data(block), sizeof(ll->mi_le));
	return dm_tm_unlock(ll->tm, block);
}

static dm_block_t metadata_ll_max_entries(struct ll_disk *ll)
{
	return MAX_METADATA_BITMAPS;
}

static int metadata_ll_commit(struct ll_disk *ll)
{
	int r, inc;
	struct dm_block *b;

	r = dm_tm_shadow_block(ll->tm, ll->bitmap_root, &index_validator, &b, &inc);
	if (r)
		return r;

	memcpy(dm_block_data(b), &ll->mi_le, sizeof(ll->mi_le));
	ll->bitmap_root = dm_block_location(b);

	return dm_tm_unlock(ll->tm, b);
}

int sm_ll_new_metadata(struct ll_disk *ll, struct dm_transaction_manager *tm)
{
	int r;

	r = sm_ll_init(ll, tm);
	if (r < 0)
		return r;

	ll->load_ie = metadata_ll_load_ie;
	ll->save_ie = metadata_ll_save_ie;
	ll->init_index = metadata_ll_init_index;
	ll->open_index = metadata_ll_open;
	ll->max_entries = metadata_ll_max_entries;
	ll->commit = metadata_ll_commit;

	ll->nr_blocks = 0;
	ll->nr_allocated = 0;

	r = ll->init_index(ll);
	if (r < 0)
		return r;

	r = dm_btree_empty(&ll->ref_count_info, &ll->ref_count_root);
	if (r < 0)
		return r;

	return 0;
}

int sm_ll_open_metadata(struct ll_disk *ll, struct dm_transaction_manager *tm,
			void *root_le, size_t len)
{
	int r;
	struct disk_sm_root *smr = root_le;

	if (len < sizeof(struct disk_sm_root)) {
		DMERR("sm_metadata root too small");
		return -ENOMEM;
	}

	r = sm_ll_init(ll, tm);
	if (r < 0)
		return r;

	ll->load_ie = metadata_ll_load_ie;
	ll->save_ie = metadata_ll_save_ie;
	ll->init_index = metadata_ll_init_index;
	ll->open_index = metadata_ll_open;
	ll->max_entries = metadata_ll_max_entries;
	ll->commit = metadata_ll_commit;

	ll->nr_blocks = le64_to_cpu(smr->nr_blocks);
	ll->nr_allocated = le64_to_cpu(smr->nr_allocated);
	ll->bitmap_root = le64_to_cpu(smr->bitmap_root);
	ll->ref_count_root = le64_to_cpu(smr->ref_count_root);

	return ll->open_index(ll);
}

/*----------------------------------------------------------------*/

static int disk_ll_load_ie(struct ll_disk *ll, dm_block_t index,
			   struct disk_index_entry *ie)
{
	return dm_btree_lookup(&ll->bitmap_info, ll->bitmap_root, &index, ie);
}

static int disk_ll_save_ie(struct ll_disk *ll, dm_block_t index,
			   struct disk_index_entry *ie)
{
	__dm_bless_for_disk(ie);
	return dm_btree_insert(&ll->bitmap_info, ll->bitmap_root,
			       &index, ie, &ll->bitmap_root);
}

static int disk_ll_init_index(struct ll_disk *ll)
{
	return dm_btree_empty(&ll->bitmap_info, &ll->bitmap_root);
}

static int disk_ll_open(struct ll_disk *ll)
{
	/* nothing to do */
	return 0;
}

static dm_block_t disk_ll_max_entries(struct ll_disk *ll)
{
	return -1ULL;
}

static int disk_ll_commit(struct ll_disk *ll)
{
	return 0;
}

int sm_ll_new_disk(struct ll_disk *ll, struct dm_transaction_manager *tm)
{
	int r;

	r = sm_ll_init(ll, tm);
	if (r < 0)
		return r;

	ll->load_ie = disk_ll_load_ie;
	ll->save_ie = disk_ll_save_ie;
	ll->init_index = disk_ll_init_index;
	ll->open_index = disk_ll_open;
	ll->max_entries = disk_ll_max_entries;
	ll->commit = disk_ll_commit;

	ll->nr_blocks = 0;
	ll->nr_allocated = 0;

	r = ll->init_index(ll);
	if (r < 0)
		return r;

	r = dm_btree_empty(&ll->ref_count_info, &ll->ref_count_root);
	if (r < 0)
		return r;

	return 0;
}

int sm_ll_open_disk(struct ll_disk *ll, struct dm_transaction_manager *tm,
		    void *root_le, size_t len)
{
	int r;
	struct disk_sm_root *smr = root_le;

	if (len < sizeof(struct disk_sm_root)) {
		DMERR("sm_metadata root too small");
		return -ENOMEM;
	}

	r = sm_ll_init(ll, tm);
	if (r < 0)
		return r;

	ll->load_ie = disk_ll_load_ie;
	ll->save_ie = disk_ll_save_ie;
	ll->init_index = disk_ll_init_index;
	ll->open_index = disk_ll_open;
	ll->max_entries = disk_ll_max_entries;
	ll->commit = disk_ll_commit;

	ll->nr_blocks = le64_to_cpu(smr->nr_blocks);
	ll->nr_allocated = le64_to_cpu(smr->nr_allocated);
	ll->bitmap_root = le64_to_cpu(smr->bitmap_root);
	ll->ref_count_root = le64_to_cpu(smr->ref_count_root);

	return ll->open_index(ll);
}

/*----------------------------------------------------------------*/
Commit	Line	Data
3241b1d3 JT	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)) {
89ddeb8c MS	42	DMERR_LIMIT("index_check failed: blocknr %llu != wanted %llu",
89ddeb8c MS	43	le64_to_cpu(mi_le->blocknr), dm_block_location(b));
3241b1d3 JT	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) {
89ddeb8c MS	51	DMERR_LIMIT("index_check failed: csum %u != wanted %u",
89ddeb8c MS	52	le32_to_cpu(csum_disk), le32_to_cpu(mi_le->csum));
3241b1d3 JT	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 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 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)) {
89ddeb8c MS	92	DMERR_LIMIT("bitmap check failed: blocknr %llu != wanted %llu",
89ddeb8c MS	93	le64_to_cpu(disk_header->blocknr), dm_block_location(b));
3241b1d3 JT	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) {
89ddeb8c MS	101	DMERR_LIMIT("bitmap check failed: csum %u != wanted %u",
89ddeb8c MS	102	le32_to_cpu(csum_disk), le32_to_cpu(disk_header->csum));
3241b1d3 JT	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 = bitmap_prepare_for_write,
	112	.check = 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 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	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	ll->tm = tm;
194
195	ll->bitmap_info.tm = tm;
196	ll->bitmap_info.levels = 1;
197
198	/*
199	* Because the new bitmap blocks are created via a shadow
200	* operation, the old entry has already had its reference count
201	* decremented and we don't need the btree to do any bookkeeping.
202	*/
203	ll->bitmap_info.value_type.size = sizeof(struct disk_index_entry);
204	ll->bitmap_info.value_type.inc = NULL;
205	ll->bitmap_info.value_type.dec = NULL;
206	ll->bitmap_info.value_type.equal = NULL;
207
208	ll->ref_count_info.tm = tm;
209	ll->ref_count_info.levels = 1;
210	ll->ref_count_info.value_type.size = sizeof(uint32_t);
211	ll->ref_count_info.value_type.inc = NULL;
212	ll->ref_count_info.value_type.dec = NULL;
213	ll->ref_count_info.value_type.equal = NULL;
214
215	ll->block_size = dm_bm_block_size(dm_tm_get_bm(tm));
216
217	if (ll->block_size > (1 << 30)) {
218	DMERR("block size too big to hold bitmaps");
219	return -EINVAL;
220	}
221
222	ll->entries_per_block = (ll->block_size - sizeof(struct disk_bitmap_header)) *
223	ENTRIES_PER_BYTE;
224	ll->nr_blocks = 0;
225	ll->bitmap_root = 0;
226	ll->ref_count_root = 0;
f4b90369	227	ll->bitmap_index_changed = false;
3241b1d3 JT	228
	229	return 0;
	230	}
	231
	232	int sm_ll_extend(struct ll_disk *ll, dm_block_t extra_blocks)
	233	{
	234	int r;
	235	dm_block_t i, nr_blocks, nr_indexes;
	236	unsigned old_blocks, blocks;
	237
	238	nr_blocks = ll->nr_blocks + extra_blocks;
	239	old_blocks = dm_sector_div_up(ll->nr_blocks, ll->entries_per_block);
	240	blocks = dm_sector_div_up(nr_blocks, ll->entries_per_block);
	241
	242	nr_indexes = dm_sector_div_up(nr_blocks, ll->entries_per_block);
	243	if (nr_indexes > ll->max_entries(ll)) {
	244	DMERR("space map too large");
	245	return -EINVAL;
	246	}
	247
12c91a5c JT	248	/*
	249	* We need to set this before the dm_tm_new_block() call below.
	250	*/
	251	ll->nr_blocks = nr_blocks;
3241b1d3 JT	252	for (i = old_blocks; i < blocks; i++) {
	253	struct dm_block *b;
	254	struct disk_index_entry idx;
	255
	256	r = dm_tm_new_block(ll->tm, &dm_sm_bitmap_validator, &b);
	257	if (r < 0)
	258	return r;
12c91a5c	259
3241b1d3 JT	260	idx.blocknr = cpu_to_le64(dm_block_location(b));
	261
	262	r = dm_tm_unlock(ll->tm, b);
	263	if (r < 0)
	264	return r;
	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
3241b1d3 JT	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	return dm_tm_unlock(ll->tm, blk);
	297	}
	298
f722063e JT	299	static int sm_ll_lookup_big_ref_count(struct ll_disk *ll, dm_block_t b,
f722063e JT	300	uint32_t *result)
3241b1d3 JT	301	{
3241b1d3 JT	302	__le32 le_rc;
f722063e	303	int r;
3241b1d3 JT	304
	305	r = dm_btree_lookup(&ll->ref_count_info, ll->ref_count_root, &b, &le_rc);
	306	if (r < 0)
	307	return r;
	308
	309	*result = le32_to_cpu(le_rc);
	310
	311	return r;
	312	}
	313
f722063e JT	314	int sm_ll_lookup(struct ll_disk ll, dm_block_t b, uint32_t result)
	315	{
	316	int r = sm_ll_lookup_bitmap(ll, b, result);
	317
	318	if (r)
	319	return r;
	320
	321	if (*result != 3)
	322	return r;
	323
	324	return sm_ll_lookup_big_ref_count(ll, b, result);
	325	}
	326
3241b1d3 JT	327	int sm_ll_find_free_block(struct ll_disk *ll, dm_block_t begin,
	328	dm_block_t end, dm_block_t *result)
	329	{
	330	int r;
	331	struct disk_index_entry ie_disk;
	332	dm_block_t i, index_begin = begin;
	333	dm_block_t index_end = dm_sector_div_up(end, ll->entries_per_block);
	334
	335	/*
	336	* FIXME: Use shifts
	337	*/
	338	begin = do_div(index_begin, ll->entries_per_block);
	339	end = do_div(end, ll->entries_per_block);
	340
	341	for (i = index_begin; i < index_end; i++, begin = 0) {
	342	struct dm_block *blk;
	343	unsigned position;
	344	uint32_t bit_end;
	345
	346	r = ll->load_ie(ll, i, &ie_disk);
	347	if (r < 0)
	348	return r;
	349
	350	if (le32_to_cpu(ie_disk.nr_free) == 0)
	351	continue;
	352
	353	r = dm_tm_read_lock(ll->tm, le64_to_cpu(ie_disk.blocknr),
	354	&dm_sm_bitmap_validator, &blk);
	355	if (r < 0)
	356	return r;
	357
	358	bit_end = (i == index_end - 1) ? end : ll->entries_per_block;
	359
	360	r = sm_find_free(dm_bitmap_data(blk),
	361	max_t(unsigned, begin, le32_to_cpu(ie_disk.none_free_before)),
	362	bit_end, &position);
	363	if (r == -ENOSPC) {
	364	/*
	365	* This might happen because we started searching
	366	* part way through the bitmap.
	367	*/
	368	dm_tm_unlock(ll->tm, blk);
	369	continue;
	370
	371	} else if (r < 0) {
	372	dm_tm_unlock(ll->tm, blk);
	373	return r;
	374	}
	375
	376	r = dm_tm_unlock(ll->tm, blk);
	377	if (r < 0)
	378	return r;
	379
	380	result = i ll->entries_per_block + (dm_block_t) position;
	381	return 0;
	382	}
	383
	384	return -ENOSPC;
	385	}
	386
f722063e	387	static int sm_ll_mutate(struct ll_disk *ll, dm_block_t b,
5b564d80	388	int (mutator)(void context, uint32_t old, uint32_t *new),
f722063e	389	void context, enum allocation_event ev)
3241b1d3 JT	390	{
3241b1d3 JT	391	int r;
f722063e	392	uint32_t bit, old, ref_count;
3241b1d3 JT	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
f722063e JT	415	if (old > 2) {
f722063e JT	416	r = sm_ll_lookup_big_ref_count(ll, b, &old);
5b564d80 JT	417	if (r < 0) {
5b564d80 JT	418	dm_tm_unlock(ll->tm, nb);
f722063e	419	return r;
5b564d80	420	}
f722063e JT	421	}
f722063e JT	422
5b564d80 JT	423	r = mutator(context, old, &ref_count);
	424	if (r) {
	425	dm_tm_unlock(ll->tm, nb);
	426	return r;
	427	}
f722063e	428
3241b1d3 JT	429	if (ref_count <= 2) {
	430	sm_set_bitmap(bm_le, bit, ref_count);
	431
	432	r = dm_tm_unlock(ll->tm, nb);
	433	if (r < 0)
	434	return r;
	435
3241b1d3 JT	436	if (old > 2) {
	437	r = dm_btree_remove(&ll->ref_count_info,
	438	ll->ref_count_root,
	439	&b, &ll->ref_count_root);
	440	if (r)
	441	return r;
	442	}
3241b1d3 JT	443
	444	} else {
	445	__le32 le_rc = cpu_to_le32(ref_count);
	446
	447	sm_set_bitmap(bm_le, bit, 3);
	448	r = dm_tm_unlock(ll->tm, nb);
	449	if (r < 0)
	450	return r;
	451
	452	__dm_bless_for_disk(&le_rc);
	453	r = dm_btree_insert(&ll->ref_count_info, ll->ref_count_root,
	454	&b, &le_rc, &ll->ref_count_root);
	455	if (r < 0) {
	456	DMERR("ref count insert failed");
	457	return r;
	458	}
	459	}
	460
	461	if (ref_count && !old) {
	462	*ev = SM_ALLOC;
	463	ll->nr_allocated++;
0bcf0879	464	le32_add_cpu(&ie_disk.nr_free, -1);
3241b1d3 JT	465	if (le32_to_cpu(ie_disk.none_free_before) == bit)
	466	ie_disk.none_free_before = cpu_to_le32(bit + 1);
	467
	468	} else if (old && !ref_count) {
	469	*ev = SM_FREE;
	470	ll->nr_allocated--;
0bcf0879	471	le32_add_cpu(&ie_disk.nr_free, 1);
3241b1d3 JT	472	ie_disk.none_free_before = cpu_to_le32(min(le32_to_cpu(ie_disk.none_free_before), bit));
	473	}
	474
	475	return ll->save_ie(ll, index, &ie_disk);
	476	}
	477
5b564d80	478	static int set_ref_count(void context, uint32_t old, uint32_t new)
3241b1d3	479	{
5b564d80 JT	480	new = ((uint32_t *) context);
5b564d80 JT	481	return 0;
f722063e	482	}
3241b1d3	483
f722063e JT	484	int sm_ll_insert(struct ll_disk *ll, dm_block_t b,
	485	uint32_t ref_count, enum allocation_event *ev)
	486	{
	487	return sm_ll_mutate(ll, b, set_ref_count, &ref_count, ev);
3241b1d3 JT	488	}
3241b1d3 JT	489
5b564d80	490	static int inc_ref_count(void context, uint32_t old, uint32_t new)
3241b1d3	491	{
5b564d80 JT	492	*new = old + 1;
5b564d80 JT	493	return 0;
f722063e	494	}
3241b1d3	495
f722063e JT	496	int sm_ll_inc(struct ll_disk ll, dm_block_t b, enum allocation_event ev)
	497	{
	498	return sm_ll_mutate(ll, b, inc_ref_count, NULL, ev);
	499	}
3241b1d3	500
5b564d80	501	static int dec_ref_count(void context, uint32_t old, uint32_t new)
f722063e	502	{
5b564d80 JT	503	if (!old) {
	504	DMERR_LIMIT("unable to decrement a reference count below 0");
	505	return -EINVAL;
	506	}
	507
	508	*new = old - 1;
	509	return 0;
f722063e	510	}
3241b1d3	511
f722063e JT	512	int sm_ll_dec(struct ll_disk ll, dm_block_t b, enum allocation_event ev)
	513	{
	514	return sm_ll_mutate(ll, b, dec_ref_count, NULL, ev);
3241b1d3 JT	515	}
	516
	517	int sm_ll_commit(struct ll_disk *ll)
	518	{
f4b90369 JT	519	int r = 0;
	520
	521	if (ll->bitmap_index_changed) {
	522	r = ll->commit(ll);
	523	if (!r)
	524	ll->bitmap_index_changed = false;
	525	}
	526
	527	return r;
3241b1d3 JT	528	}
	529
	530	/----------------------------------------------------------------/
	531
	532	static int metadata_ll_load_ie(struct ll_disk *ll, dm_block_t index,
	533	struct disk_index_entry *ie)
	534	{
	535	memcpy(ie, ll->mi_le.index + index, sizeof(*ie));
	536	return 0;
	537	}
	538
	539	static int metadata_ll_save_ie(struct ll_disk *ll, dm_block_t index,
	540	struct disk_index_entry *ie)
	541	{
f4b90369	542	ll->bitmap_index_changed = true;
3241b1d3 JT	543	memcpy(ll->mi_le.index + index, ie, sizeof(*ie));
	544	return 0;
	545	}
	546
	547	static int metadata_ll_init_index(struct ll_disk *ll)
	548	{
	549	int r;
	550	struct dm_block *b;
	551
	552	r = dm_tm_new_block(ll->tm, &index_validator, &b);
	553	if (r < 0)
	554	return r;
	555
	556	memcpy(dm_block_data(b), &ll->mi_le, sizeof(ll->mi_le));
	557	ll->bitmap_root = dm_block_location(b);
	558
	559	return dm_tm_unlock(ll->tm, b);
	560	}
	561
	562	static int metadata_ll_open(struct ll_disk *ll)
	563	{
	564	int r;
	565	struct dm_block *block;
	566
	567	r = dm_tm_read_lock(ll->tm, ll->bitmap_root,
	568	&index_validator, &block);
	569	if (r)
	570	return r;
	571
	572	memcpy(&ll->mi_le, dm_block_data(block), sizeof(ll->mi_le));
	573	return dm_tm_unlock(ll->tm, block);
	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	return dm_tm_unlock(ll->tm, b);
	594	}
	595
	596	int sm_ll_new_metadata(struct ll_disk ll, struct dm_transaction_manager tm)
	597	{
	598	int r;
	599
	600	r = sm_ll_init(ll, tm);
	601	if (r < 0)
	602	return r;
	603
	604	ll->load_ie = metadata_ll_load_ie;
	605	ll->save_ie = metadata_ll_save_ie;
	606	ll->init_index = metadata_ll_init_index;
607	ll->open_index = metadata_ll_open;
608	ll->max_entries = metadata_ll_max_entries;
609	ll->commit = metadata_ll_commit;
610
611	ll->nr_blocks = 0;
612	ll->nr_allocated = 0;
613
614	r = ll->init_index(ll);
615	if (r < 0)
616	return r;
617
618	r = dm_btree_empty(&ll->ref_count_info, &ll->ref_count_root);
619	if (r < 0)
620	return r;
621
622	return 0;
623	}
624
625	int sm_ll_open_metadata(struct ll_disk ll, struct dm_transaction_manager tm,
626	void *root_le, size_t len)
627	{
628	int r;
629	struct disk_sm_root *smr = root_le;
630
631	if (len < sizeof(struct disk_sm_root)) {
632	DMERR("sm_metadata root too small");
633	return -ENOMEM;
634	}
635
636	r = sm_ll_init(ll, tm);
637	if (r < 0)
638	return r;
639
640	ll->load_ie = metadata_ll_load_ie;
641	ll->save_ie = metadata_ll_save_ie;
642	ll->init_index = metadata_ll_init_index;
643	ll->open_index = metadata_ll_open;
644	ll->max_entries = metadata_ll_max_entries;
645	ll->commit = metadata_ll_commit;
646
647	ll->nr_blocks = le64_to_cpu(smr->nr_blocks);
648	ll->nr_allocated = le64_to_cpu(smr->nr_allocated);
649	ll->bitmap_root = le64_to_cpu(smr->bitmap_root);
650	ll->ref_count_root = le64_to_cpu(smr->ref_count_root);
651
652	return ll->open_index(ll);
653	}
654
655	/----------------------------------------------------------------/
656
657	static int disk_ll_load_ie(struct ll_disk *ll, dm_block_t index,
658	struct disk_index_entry *ie)
659	{
660	return dm_btree_lookup(&ll->bitmap_info, ll->bitmap_root, &index, ie);
661	}
662
663	static int disk_ll_save_ie(struct ll_disk *ll, dm_block_t index,
664	struct disk_index_entry *ie)
665	{
666	__dm_bless_for_disk(ie);
667	return dm_btree_insert(&ll->bitmap_info, ll->bitmap_root,
668	&index, ie, &ll->bitmap_root);
669	}
670
671	static int disk_ll_init_index(struct ll_disk *ll)
672	{
673	return dm_btree_empty(&ll->bitmap_info, &ll->bitmap_root);
674	}
675
676	static int disk_ll_open(struct ll_disk *ll)
677	{
678	/* nothing to do */
679	return 0;
680	}
681
682	static dm_block_t disk_ll_max_entries(struct ll_disk *ll)
683	{
684	return -1ULL;
685	}
686
687	static int disk_ll_commit(struct ll_disk *ll)
688	{
689	return 0;
690	}
691
692	int sm_ll_new_disk(struct ll_disk ll, struct dm_transaction_manager tm)
693	{
694	int r;
695
696	r = sm_ll_init(ll, tm);
697	if (r < 0)
698	return r;
699
700	ll->load_ie = disk_ll_load_ie;
701	ll->save_ie = disk_ll_save_ie;
702	ll->init_index = disk_ll_init_index;
703	ll->open_index = disk_ll_open;
704	ll->max_entries = disk_ll_max_entries;
705	ll->commit = disk_ll_commit;
706
707	ll->nr_blocks = 0;
708	ll->nr_allocated = 0;
709
710	r = ll->init_index(ll);
711	if (r < 0)
712	return r;
713
714	r = dm_btree_empty(&ll->ref_count_info, &ll->ref_count_root);
715	if (r < 0)
716	return r;
717
718	return 0;
719	}
720
721	int sm_ll_open_disk(struct ll_disk ll, struct dm_transaction_manager tm,
722	void *root_le, size_t len)
723	{
724	int r;
725	struct disk_sm_root *smr = root_le;
726
727	if (len < sizeof(struct disk_sm_root)) {
728	DMERR("sm_metadata root too small");
729	return -ENOMEM;
730	}
731
732	r = sm_ll_init(ll, tm);
733	if (r < 0)
734	return r;
735
736	ll->load_ie = disk_ll_load_ie;
737	ll->save_ie = disk_ll_save_ie;
738	ll->init_index = disk_ll_init_index;
739	ll->open_index = disk_ll_open;
740	ll->max_entries = disk_ll_max_entries;
741	ll->commit = disk_ll_commit;
742
743	ll->nr_blocks = le64_to_cpu(smr->nr_blocks);
744	ll->nr_allocated = le64_to_cpu(smr->nr_allocated);
745	ll->bitmap_root = le64_to_cpu(smr->bitmap_root);
746	ll->ref_count_root = le64_to_cpu(smr->ref_count_root);
747
748	return ll->open_index(ll);
749	}
750
751	/----------------------------------------------------------------/