path: root/drivers/md/persistent-data/dm-array.c

/*
 * 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))
{
	unsigned nr_entries = le32_to_cpu(ab->nr_entries);
	fn(info->value_type.context, element_at(info, ab, 0), nr_entries);
}

/*
 * 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)
{
	uint32_t nr_entries, delta, i;
	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);
	delta = new_nr - nr_entries;
	if (vt->inc)
		vt->inc(vt->context, value, delta);
	for (i = nr_entries; i < new_nr; i++)
		memcpy(element_at(info, ab, i),