/* * Copyright (C) 2012 Red Hat, Inc. * * This file is released under the GPL. */ #include "dm-array.h"#include "dm-space-map.h"#include "dm-transaction-manager.h" #include <linux/export.h>#include <linux/device-mapper.h> #define DM_MSG_PREFIX "array" /*----------------------------------------------------------------*/ /* * The array is implemented as a fully populated btree, which points to * blocks that contain the packed values.  This is more space efficient * than just using a btree since we don't store 1 key per value. */struct array_block {	__le32 csum;	__le32 max_entries;	__le32 nr_entries;	__le32 value_size;	__le64 blocknr; /* Block this node is supposed to live in. */} __packed; /*----------------------------------------------------------------*/ /* * Validator methods.  As usual we calculate a checksum, and also write the * block location into the header (paranoia about ssds remapping areas by * mistake). */#define CSUM_XOR 595846735 static void array_block_prepare_for_write(struct dm_block_validator *v,					  struct dm_block *b,					  size_t size_of_block){	struct array_block *bh_le = dm_block_data(b); 	bh_le->blocknr = cpu_to_le64(dm_block_location(b));	bh_le->csum = cpu_to_le32(dm_bm_checksum(&bh_le->max_entries,						 size_of_block - sizeof(__le32),						 CSUM_XOR));} static int array_block_check(struct dm_block_validator *v,			     struct dm_block *b,			     size_t size_of_block){	struct array_block *bh_le = dm_block_data(b);	__le32 csum_disk; 	if (dm_block_location(b) != le64_to_cpu(bh_le->blocknr)) {		DMERR_LIMIT("array_block_check failed: blocknr %llu != wanted %llu",			    (unsigned long long) le64_to_cpu(bh_le->blocknr),			    (unsigned long long) dm_block_location(b));		return -ENOTBLK;	} 	csum_disk = cpu_to_le32(dm_bm_checksum(&bh_le->max_entries,					       size_of_block - sizeof(__le32),					       CSUM_XOR));	if (csum_disk != bh_le->csum) {		DMERR_LIMIT("array_block_check failed: csum %u != wanted %u",			    (unsigned) le32_to_cpu(csum_disk),			    (unsigned) le32_to_cpu(bh_le->csum));		return -EILSEQ;	} 	return 0;} static struct dm_block_validator array_validator = {	.name = "array",	.prepare_for_write = array_block_prepare_for_write,	.check = array_block_check}; /*----------------------------------------------------------------*/ /* * Functions for manipulating the array blocks. */ /* * Returns a pointer to a value within an array block. * * index - The index into _this_ specific block. */static void *element_at(struct dm_array_info *info, struct array_block *ab,			unsigned index){	unsigned char *entry = (unsigned char *) (ab + 1); 	entry += index * info->value_type.size; 	return entry;} /* * Utility function that calls one of the value_type methods on every value * in an array block. */static void on_entries(struct dm_array_info *info, struct array_block *ab,		       void (*fn)(void *, const void *)){	unsigned i, nr_entries = le32_to_cpu(ab->nr_entries); 	for (i = 0; i < nr_entries; i++)		fn(info->value_type.context, element_at(info, ab, i));} /* * Increment every value in an array block. */static void inc_ablock_entries(struct dm_array_info *info, struct array_block *ab){	struct dm_btree_value_type *vt = &info->value_type; 	if (vt->inc)		on_entries(info, ab, vt->inc);} /* * Decrement every value in an array block. */static void dec_ablock_entries(struct dm_array_info *info, struct array_block *ab){	struct dm_btree_value_type *vt = &info->value_type; 	if (vt->dec)		on_entries(info, ab, vt->dec);} /* * Each array block can hold this many values. */static uint32_t calc_max_entries(size_t value_size, size_t size_of_block){	return (size_of_block - sizeof(struct array_block)) / value_size;} /* * Allocate a new array block.  The caller will need to unlock block. */static int alloc_ablock(struct dm_array_info *info, size_t size_of_block,			uint32_t max_entries,			struct dm_block **block, struct array_block **ab){	int r; 	r = dm_tm_new_block(info->btree_info.tm, &array_validator, block);	if (r)		return r; 	(*ab) = dm_block_data(*block);	(*ab)->max_entries = cpu_to_le32(max_entries);	(*ab)->nr_entries = cpu_to_le32(0);	(*ab)->value_size = cpu_to_le32(info->value_type.size); 	return 0;} /* * Pad an array block out with a particular value.  Every instance will * cause an increment of the value_type.  new_nr must always be more than * the current number of entries. */static void fill_ablock(struct dm_array_info *info, struct array_block *ab,			const void *value, unsigned new_nr){	unsigned i;	uint32_t nr_entries;	struct dm_btree_value_type *vt = &info->value_type; 	BUG_ON(new_nr > le32_to_cpu(ab->max_entries));	BUG_ON(new_nr < le32_to_cpu(ab->nr_entries)); 	nr_entries = le32_to_cpu(ab->nr_entries);	for (i = nr_entries; i < new_nr; i++) {		if (vt->inc)			vt->inc(vt->context, value);		memcpy(element_at(info, ab, i), value, vt->size);	}	ab->nr_entries = cpu_to_le32(new_nr);} /* * Remove some entries from the back of an array block.  Every value * removed will be decremented.  new_nr must be <= the current number of * entries. */static void trim_ablock(struct dm_array_info *info, struct array_block *ab,			unsigned new_nr){	unsigned i;	uint32_t nr_entries;	struct dm_btree_value_type *vt = &info->value_type; 	BUG_ON(new_nr > le32_to_cpu(ab->max_entries));	BUG_ON(new_nr > le32_to_cpu(ab->nr_entries)); 	nr_entries = le32_to_cpu(ab->nr_entries);	for (i = nr_entries; i > new_nr; i--)		if (vt->dec)			vt->dec(vt->context, element_at(info, ab, i - 1));	ab->nr_entries = cpu_to_le32(new_nr);} /* * Read locks a block, and coerces it to an array block.  The caller must * unlock 'block' when finished. */static int get_ablock(struct dm_array_info *info, dm_block_t b,		      struct dm_block **block, struct array_block **ab){	int r; 	r = dm_tm_read_lock(info->btree_info.tm, b, &array_validator, block);	if (r)		return r; 	*ab = dm_block_data(*block);	return 0;} /* * Unlocks an array block. */static void unlock_ablock(struct dm_array_info *info, struct dm_block *block){	dm_tm_unlock(info->btree_info.tm, block);} /*----------------------------------------------------------------*/ /* * Btree manipulation. */ /* * Looks up an array block in the btree, and then read locks it. * * index is the index of the index of the array_block, (ie. the array index * / max_entries). */static int lookup_ablock(struct dm_array_info *info, dm_block_t root,			 unsigned index, struct dm_block **block,			 struct array_block **ab){	int r;	uint64_t key = index;	__le64 block_le; 	r = dm_btree_lookup(&info->btree_info, root, &key, &block_le);	if (r)		return r; 	return get_ablock(info, le64_to_cpu(block_le), block, ab);} /* * Insert an array block into the btree.  The block is _not_ unlocked. */static int insert_ablock(struct dm_array_info *info, uint64_t index,			 struct dm_block *block, dm_block_t *root){	__le64 block_le = cpu_to_le64(dm_block_location(block)); 	__dm_bless_for_disk(block_le);	return dm_btree_insert(&info->btree_info, *root, &index, &block_le, root);} /*----------------------------------------------------------------*/ static int __shadow_ablock(struct dm_array_info *info, dm_block_t b,			   struct dm_block **block, struct array_block **ab){	int inc;	int r = dm_tm_shadow_block(info->btree_info.tm, b,				   &array_validator, block, &inc);	if (r)		return r; 	*ab = dm_block_data(*block);	if (inc)		inc_ablock_entries(info, *ab); 	return 0;} /* * The shadow op will often be a noop.  Only insert if it really * copied data. */static int __reinsert_ablock(struct dm_array_info *info, unsigned index,			     struct dm_block *block, dm_block_t b,			     dm_block_t *root){	int r = 0; 	if (dm_block_location(block) != b) {		/*		 * dm_tm_shadow_block will have already decremented the old		 * block, but it is still referenced by the btree.  We		 * increment to stop the insert decrementing it below zero		 * when overwriting the old value.		 */		dm_tm_inc(info->btree_info.tm, b);		r = insert_ablock(info, index, block, root);	} 	return r;} /* * Looks up an array block in the btree.  Then shadows it, and updates the * btree to point to this new shadow.  'root' is an input/output parameter * for both the current root block, and the new one. */static int shadow_ablock(struct dm_array_info *info, dm_block_t *root,			 unsigned index, struct dm_block **block,			 struct array_block **ab){	int r;	uint64_t key = index;	dm_block_t b;	__le64 block_le; 	r = dm_btree_lookup(&info->btree_info, *root, &key, &block_le);	if (r)		return r;	b = le64_to_cpu(block_le); 	r = __shadow_ablock(info, b, block, ab);	if (r)		return r; 	return __reinsert_ablock(info, index, *block, b, root);} /* * Allocate an new array block, and fill it with some values. */static int insert_new_ablock(struct dm_array_info *info, size_t size_of_block,			     uint32_t max_entries,			     unsigned block_index, uint32_t nr,			     const void *value, dm_block_t *root){	int r;	struct dm_block *block;	struct array_block *ab; 	r = alloc_ablock(info, size_of_block, max_entries, &block, &ab);	if (r)		return r; 	fill_ablock(info, ab, value, nr);	r = insert_ablock(info, block_index, block, root);	unlock_ablock(info, block); 	return r;} static int insert_full_ablocks(struct dm_array_info *info, size_t size_of_block,			       unsigned begin_block, unsigned end_block,			       unsigned max_entries, const void *value,			       dm_block_t *root){	int r = 0; 	for (; !r && begin_block != end_block; begin_block++)		r = insert_new_ablock(info, size_of_block, max_entries, begin_block, max_entries, value, root); 	return r;} /* * There are a bunch of functions involved with resizing an array.  This * structure holds information that commonly needed by them.  Purely here * to reduce parameter count. */struct resize {	/*	 * Describes the array.	 */	struct dm_array_info *info; 	/*	 * The current root of the array.  This gets updated.	 */	dm_block_t root; 	/*	 * Metadata block size.  Used to calculate the nr entries in an	 * array block.	 */	size_t size_of_block; 	/*	 * Maximum nr entries in an array block.	 */	unsigned max_entries; 	/*	 * nr of completely full blocks in the array.	 *	 * 'old' refers to before the resize, 'new' after.	 */	unsigned old_nr_full_blocks, new_nr_full_blocks; 	/*	 * Number of entries in the final block.  0 iff only full blocks in	 * the array.	 */	unsigned old_nr_entries_in_last_block, new_nr_entries_in_last_block; 	/*	 * The default value used when growing the array.	 */	const void *value;}; /* * Removes a consecutive set of array blocks from the btree.  The values * in block are decremented as a side effect of the btree remove. * * begin_index - the index of the first array block to remove. * end_index - the one-past-the-end value.  ie. this block is not removed. */static int drop_blocks(struct resize *resize, unsigned begin_index,		       unsigned end_index){	int r; 	while (begin_index != end_index) {		uint64_t key = begin_index++;		r = dm_btree_remove(&resize->info->btree_info, resize->root,				    &key, &resize->root);		if (r)			return r;	} 	return 0;} /* * Calculates how many blocks are needed for the array. */static unsigned total_nr_blocks_needed(unsigned nr_full_blocks,				       unsigned nr_entries_in_last_block){	return nr_full_blocks + (nr_entries_in_last_block ? 1 : 0);} /* * Shrink an array. */static int shrink(struct resize *resize){	int r;	unsigned begin, end;	struct dm_block *block;	struct array_block *ab; 	/*	 * Lose some blocks from the back?	 */	if (resize->new_nr_full_blocks < resize->old_nr_full_blocks) {		begin = total_nr_blocks_needed(resize->new_nr_full_blocks,					       resize->new_nr_entries_in_last_block);		end = total_nr_blocks_needed(resize->old_nr_full_blocks,					     resize->old_nr_entries_in_last_block); 		r = drop_blocks(resize, begin, end);		if (r)			return r;	} 	/*	 * Trim the new tail block	 */	if (resize->new_nr_entries_in_last_block) {		r = shadow_ablock(resize->info, &resize->root,				  resize->new_nr_full_blocks, &block, &ab);		if (r)			return r; 		trim_ablock(resize->info, ab, resize->new_nr_entries_in_last_block);		unlock_ablock(resize->info, block);	} 	return 0;}

Lines 1–500 of 985. Load more