[linux-2.6-block.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;
	}

	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;
	}

	ll->nr_blocks = nr_blocks;
	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
	248	for (i = old_blocks; i < blocks; i++) {
	249	struct dm_block *b;
	250	struct disk_index_entry idx;
	251
	252	r = dm_tm_new_block(ll->tm, &dm_sm_bitmap_validator, &b);
	253	if (r < 0)
	254	return r;
	255	idx.blocknr = cpu_to_le64(dm_block_location(b));
	256
	257	r = dm_tm_unlock(ll->tm, b);
	258	if (r < 0)
	259	return r;
	260
	261	idx.nr_free = cpu_to_le32(ll->entries_per_block);
	262	idx.none_free_before = 0;
	263
	264	r = ll->save_ie(ll, i, &idx);
	265	if (r < 0)
	266	return r;
	267	}
	268
	269	ll->nr_blocks = nr_blocks;
	270	return 0;
	271	}
	272
	273	int sm_ll_lookup_bitmap(struct ll_disk ll, dm_block_t b, uint32_t result)
	274	{
	275	int r;
	276	dm_block_t index = b;
	277	struct disk_index_entry ie_disk;
	278	struct dm_block *blk;
	279
	280	b = do_div(index, ll->entries_per_block);
	281	r = ll->load_ie(ll, index, &ie_disk);
	282	if (r < 0)
	283	return r;
	284
	285	r = dm_tm_read_lock(ll->tm, le64_to_cpu(ie_disk.blocknr),
	286	&dm_sm_bitmap_validator, &blk);
	287	if (r < 0)
	288	return r;
	289
	290	*result = sm_lookup_bitmap(dm_bitmap_data(blk), b);
	291
292	return dm_tm_unlock(ll->tm, blk);
293	}
294
f722063e JT	295	static int sm_ll_lookup_big_ref_count(struct ll_disk *ll, dm_block_t b,
f722063e JT	296	uint32_t *result)
3241b1d3 JT	297	{
3241b1d3 JT	298	__le32 le_rc;
f722063e	299	int r;
3241b1d3 JT	300
	301	r = dm_btree_lookup(&ll->ref_count_info, ll->ref_count_root, &b, &le_rc);
	302	if (r < 0)
	303	return r;
	304
	305	*result = le32_to_cpu(le_rc);
	306
	307	return r;
	308	}
	309
f722063e JT	310	int sm_ll_lookup(struct ll_disk ll, dm_block_t b, uint32_t result)
	311	{
	312	int r = sm_ll_lookup_bitmap(ll, b, result);
	313
	314	if (r)
	315	return r;
	316
	317	if (*result != 3)
	318	return r;
	319
	320	return sm_ll_lookup_big_ref_count(ll, b, result);
	321	}
	322
3241b1d3 JT	323	int sm_ll_find_free_block(struct ll_disk *ll, dm_block_t begin,
	324	dm_block_t end, dm_block_t *result)
	325	{
	326	int r;
	327	struct disk_index_entry ie_disk;
	328	dm_block_t i, index_begin = begin;
	329	dm_block_t index_end = dm_sector_div_up(end, ll->entries_per_block);
	330
	331	/*
	332	* FIXME: Use shifts
	333	*/
	334	begin = do_div(index_begin, ll->entries_per_block);
	335	end = do_div(end, ll->entries_per_block);
	336
	337	for (i = index_begin; i < index_end; i++, begin = 0) {
	338	struct dm_block *blk;
	339	unsigned position;
	340	uint32_t bit_end;
	341
	342	r = ll->load_ie(ll, i, &ie_disk);
	343	if (r < 0)
	344	return r;
	345
	346	if (le32_to_cpu(ie_disk.nr_free) == 0)
	347	continue;
	348
	349	r = dm_tm_read_lock(ll->tm, le64_to_cpu(ie_disk.blocknr),
	350	&dm_sm_bitmap_validator, &blk);
	351	if (r < 0)
	352	return r;
	353
	354	bit_end = (i == index_end - 1) ? end : ll->entries_per_block;
	355
	356	r = sm_find_free(dm_bitmap_data(blk),
	357	max_t(unsigned, begin, le32_to_cpu(ie_disk.none_free_before)),
	358	bit_end, &position);
	359	if (r == -ENOSPC) {
	360	/*
	361	* This might happen because we started searching
	362	* part way through the bitmap.
	363	*/
	364	dm_tm_unlock(ll->tm, blk);
	365	continue;
	366
	367	} else if (r < 0) {
	368	dm_tm_unlock(ll->tm, blk);
	369	return r;
	370	}
	371
	372	r = dm_tm_unlock(ll->tm, blk);
	373	if (r < 0)
	374	return r;
	375
	376	result = i ll->entries_per_block + (dm_block_t) position;
	377	return 0;
	378	}
	379
	380	return -ENOSPC;
	381	}
	382
f722063e	383	static int sm_ll_mutate(struct ll_disk *ll, dm_block_t b,
5b564d80	384	int (mutator)(void context, uint32_t old, uint32_t *new),
f722063e	385	void context, enum allocation_event ev)
3241b1d3 JT	386	{
3241b1d3 JT	387	int r;
f722063e	388	uint32_t bit, old, ref_count;
3241b1d3 JT	389	struct dm_block *nb;
	390	dm_block_t index = b;
	391	struct disk_index_entry ie_disk;
	392	void *bm_le;
	393	int inc;
	394
	395	bit = do_div(index, ll->entries_per_block);
	396	r = ll->load_ie(ll, index, &ie_disk);
	397	if (r < 0)
	398	return r;
	399
	400	r = dm_tm_shadow_block(ll->tm, le64_to_cpu(ie_disk.blocknr),
	401	&dm_sm_bitmap_validator, &nb, &inc);
	402	if (r < 0) {
	403	DMERR("dm_tm_shadow_block() failed");
	404	return r;
	405	}
	406	ie_disk.blocknr = cpu_to_le64(dm_block_location(nb));
	407
	408	bm_le = dm_bitmap_data(nb);
	409	old = sm_lookup_bitmap(bm_le, bit);
	410
f722063e JT	411	if (old > 2) {
f722063e JT	412	r = sm_ll_lookup_big_ref_count(ll, b, &old);
5b564d80 JT	413	if (r < 0) {
5b564d80 JT	414	dm_tm_unlock(ll->tm, nb);
f722063e	415	return r;
5b564d80	416	}
f722063e JT	417	}
f722063e JT	418
5b564d80 JT	419	r = mutator(context, old, &ref_count);
	420	if (r) {
	421	dm_tm_unlock(ll->tm, nb);
	422	return r;
	423	}
f722063e	424
3241b1d3 JT	425	if (ref_count <= 2) {
	426	sm_set_bitmap(bm_le, bit, ref_count);
	427
	428	r = dm_tm_unlock(ll->tm, nb);
	429	if (r < 0)
	430	return r;
	431
3241b1d3 JT	432	if (old > 2) {
	433	r = dm_btree_remove(&ll->ref_count_info,
	434	ll->ref_count_root,
	435	&b, &ll->ref_count_root);
	436	if (r)
	437	return r;
	438	}
3241b1d3 JT	439
	440	} else {
	441	__le32 le_rc = cpu_to_le32(ref_count);
	442
	443	sm_set_bitmap(bm_le, bit, 3);
	444	r = dm_tm_unlock(ll->tm, nb);
	445	if (r < 0)
	446	return r;
	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++;
0bcf0879	460	le32_add_cpu(&ie_disk.nr_free, -1);
3241b1d3 JT	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--;
0bcf0879	467	le32_add_cpu(&ie_disk.nr_free, 1);
3241b1d3 JT	468	ie_disk.none_free_before = cpu_to_le32(min(le32_to_cpu(ie_disk.none_free_before), bit));
	469	}
	470
	471	return ll->save_ie(ll, index, &ie_disk);
	472	}
	473
5b564d80	474	static int set_ref_count(void context, uint32_t old, uint32_t new)
3241b1d3	475	{
5b564d80 JT	476	new = ((uint32_t *) context);
5b564d80 JT	477	return 0;
f722063e	478	}
3241b1d3	479
f722063e JT	480	int sm_ll_insert(struct ll_disk *ll, dm_block_t b,
	481	uint32_t ref_count, enum allocation_event *ev)
	482	{
	483	return sm_ll_mutate(ll, b, set_ref_count, &ref_count, ev);
3241b1d3 JT	484	}
3241b1d3 JT	485
5b564d80	486	static int inc_ref_count(void context, uint32_t old, uint32_t new)
3241b1d3	487	{
5b564d80 JT	488	*new = old + 1;
5b564d80 JT	489	return 0;
f722063e	490	}
3241b1d3	491
f722063e JT	492	int sm_ll_inc(struct ll_disk ll, dm_block_t b, enum allocation_event ev)
	493	{
	494	return sm_ll_mutate(ll, b, inc_ref_count, NULL, ev);
	495	}
3241b1d3	496
5b564d80	497	static int dec_ref_count(void context, uint32_t old, uint32_t new)
f722063e	498	{
5b564d80 JT	499	if (!old) {
	500	DMERR_LIMIT("unable to decrement a reference count below 0");
	501	return -EINVAL;
	502	}
	503
	504	*new = old - 1;
	505	return 0;
f722063e	506	}
3241b1d3	507
f722063e JT	508	int sm_ll_dec(struct ll_disk ll, dm_block_t b, enum allocation_event ev)
	509	{
	510	return sm_ll_mutate(ll, b, dec_ref_count, NULL, ev);
3241b1d3 JT	511	}
	512
	513	int sm_ll_commit(struct ll_disk *ll)
	514	{
f4b90369 JT	515	int r = 0;
	516
	517	if (ll->bitmap_index_changed) {
	518	r = ll->commit(ll);
	519	if (!r)
	520	ll->bitmap_index_changed = false;
	521	}
	522
	523	return r;
3241b1d3 JT	524	}
	525
	526	/----------------------------------------------------------------/
	527
	528	static int metadata_ll_load_ie(struct ll_disk *ll, dm_block_t index,
	529	struct disk_index_entry *ie)
	530	{
	531	memcpy(ie, ll->mi_le.index + index, sizeof(*ie));
	532	return 0;
	533	}
	534
	535	static int metadata_ll_save_ie(struct ll_disk *ll, dm_block_t index,
	536	struct disk_index_entry *ie)
	537	{
f4b90369	538	ll->bitmap_index_changed = true;
3241b1d3 JT	539	memcpy(ll->mi_le.index + index, ie, sizeof(*ie));
	540	return 0;
	541	}
	542
	543	static int metadata_ll_init_index(struct ll_disk *ll)
	544	{
	545	int r;
	546	struct dm_block *b;
	547
	548	r = dm_tm_new_block(ll->tm, &index_validator, &b);
	549	if (r < 0)
	550	return r;
	551
	552	memcpy(dm_block_data(b), &ll->mi_le, sizeof(ll->mi_le));
	553	ll->bitmap_root = dm_block_location(b);
	554
	555	return dm_tm_unlock(ll->tm, b);
	556	}
	557
	558	static int metadata_ll_open(struct ll_disk *ll)
	559	{
	560	int r;
	561	struct dm_block *block;
	562
	563	r = dm_tm_read_lock(ll->tm, ll->bitmap_root,
	564	&index_validator, &block);
	565	if (r)
	566	return r;
	567
	568	memcpy(&ll->mi_le, dm_block_data(block), sizeof(ll->mi_le));
	569	return dm_tm_unlock(ll->tm, block);
	570	}
	571
	572	static dm_block_t metadata_ll_max_entries(struct ll_disk *ll)
	573	{
	574	return MAX_METADATA_BITMAPS;
	575	}
	576
	577	static int metadata_ll_commit(struct ll_disk *ll)
	578	{
	579	int r, inc;
	580	struct dm_block *b;
	581
	582	r = dm_tm_shadow_block(ll->tm, ll->bitmap_root, &index_validator, &b, &inc);
	583	if (r)
	584	return r;
	585
	586	memcpy(dm_block_data(b), &ll->mi_le, sizeof(ll->mi_le));
	587	ll->bitmap_root = dm_block_location(b);
	588
	589	return dm_tm_unlock(ll->tm, b);
	590	}
	591
	592	int sm_ll_new_metadata(struct ll_disk ll, struct dm_transaction_manager tm)
	593	{
	594	int r;
	595
	596	r = sm_ll_init(ll, tm);
	597	if (r < 0)
	598	return r;
	599
	600	ll->load_ie = metadata_ll_load_ie;
	601	ll->save_ie = metadata_ll_save_ie;
	602	ll->init_index = metadata_ll_init_index;
603	ll->open_index = metadata_ll_open;
604	ll->max_entries = metadata_ll_max_entries;
605	ll->commit = metadata_ll_commit;
606
607	ll->nr_blocks = 0;
608	ll->nr_allocated = 0;
609
610	r = ll->init_index(ll);
611	if (r < 0)
612	return r;
613
614	r = dm_btree_empty(&ll->ref_count_info, &ll->ref_count_root);
615	if (r < 0)
616	return r;
617
618	return 0;
619	}
620
621	int sm_ll_open_metadata(struct ll_disk ll, struct dm_transaction_manager tm,
622	void *root_le, size_t len)
623	{
624	int r;
625	struct disk_sm_root *smr = root_le;
626
627	if (len < sizeof(struct disk_sm_root)) {
628	DMERR("sm_metadata root too small");
629	return -ENOMEM;
630	}
631
632	r = sm_ll_init(ll, tm);
633	if (r < 0)
634	return r;
635
636	ll->load_ie = metadata_ll_load_ie;
637	ll->save_ie = metadata_ll_save_ie;
638	ll->init_index = metadata_ll_init_index;
639	ll->open_index = metadata_ll_open;
640	ll->max_entries = metadata_ll_max_entries;
641	ll->commit = metadata_ll_commit;
642
643	ll->nr_blocks = le64_to_cpu(smr->nr_blocks);
644	ll->nr_allocated = le64_to_cpu(smr->nr_allocated);
645	ll->bitmap_root = le64_to_cpu(smr->bitmap_root);
646	ll->ref_count_root = le64_to_cpu(smr->ref_count_root);
647
648	return ll->open_index(ll);
649	}
650
651	/----------------------------------------------------------------/
652
653	static int disk_ll_load_ie(struct ll_disk *ll, dm_block_t index,
654	struct disk_index_entry *ie)
655	{
656	return dm_btree_lookup(&ll->bitmap_info, ll->bitmap_root, &index, ie);
657	}
658
659	static int disk_ll_save_ie(struct ll_disk *ll, dm_block_t index,
660	struct disk_index_entry *ie)
661	{
662	__dm_bless_for_disk(ie);
663	return dm_btree_insert(&ll->bitmap_info, ll->bitmap_root,
664	&index, ie, &ll->bitmap_root);
665	}
666
667	static int disk_ll_init_index(struct ll_disk *ll)
668	{
669	return dm_btree_empty(&ll->bitmap_info, &ll->bitmap_root);
670	}
671
672	static int disk_ll_open(struct ll_disk *ll)
673	{
674	/* nothing to do */
675	return 0;
676	}
677
678	static dm_block_t disk_ll_max_entries(struct ll_disk *ll)
679	{
680	return -1ULL;
681	}
682
683	static int disk_ll_commit(struct ll_disk *ll)
684	{
685	return 0;
686	}
687
688	int sm_ll_new_disk(struct ll_disk ll, struct dm_transaction_manager tm)
689	{
690	int r;
691
692	r = sm_ll_init(ll, tm);
693	if (r < 0)
694	return r;
695
696	ll->load_ie = disk_ll_load_ie;
697	ll->save_ie = disk_ll_save_ie;
698	ll->init_index = disk_ll_init_index;
699	ll->open_index = disk_ll_open;
700	ll->max_entries = disk_ll_max_entries;
701	ll->commit = disk_ll_commit;
702
703	ll->nr_blocks = 0;
704	ll->nr_allocated = 0;
705
706	r = ll->init_index(ll);
707	if (r < 0)
708	return r;
709
710	r = dm_btree_empty(&ll->ref_count_info, &ll->ref_count_root);
711	if (r < 0)
712	return r;
713
714	return 0;
715	}
716
717	int sm_ll_open_disk(struct ll_disk ll, struct dm_transaction_manager tm,
718	void *root_le, size_t len)
719	{
720	int r;
721	struct disk_sm_root *smr = root_le;
722
723	if (len < sizeof(struct disk_sm_root)) {
724	DMERR("sm_metadata root too small");
725	return -ENOMEM;
726	}
727
728	r = sm_ll_init(ll, tm);
729	if (r < 0)
730	return r;
731
732	ll->load_ie = disk_ll_load_ie;
733	ll->save_ie = disk_ll_save_ie;
734	ll->init_index = disk_ll_init_index;
735	ll->open_index = disk_ll_open;
736	ll->max_entries = disk_ll_max_entries;
737	ll->commit = disk_ll_commit;
738
739	ll->nr_blocks = le64_to_cpu(smr->nr_blocks);
740	ll->nr_allocated = le64_to_cpu(smr->nr_allocated);
741	ll->bitmap_root = le64_to_cpu(smr->bitmap_root);
742	ll->ref_count_root = le64_to_cpu(smr->ref_count_root);
743
744	return ll->open_index(ll);
745	}
746
747	/----------------------------------------------------------------/