[mirror_ubuntu-artful-kernel.git] / drivers / md / persistent-data / dm-btree-internal.h

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

#ifndef DM_BTREE_INTERNAL_H
#define DM_BTREE_INTERNAL_H

#include "dm-btree.h"

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

/*
 * We'll need 2 accessor functions for n->csum and n->blocknr
 * to support dm-btree-spine.c in that case.
 */

enum node_flags {
	INTERNAL_NODE = 1,
	LEAF_NODE = 1 << 1
};

/*
 * Every btree node begins with this structure.  Make sure it's a multiple
 * of 8-bytes in size, otherwise the 64bit keys will be mis-aligned.
 */
struct node_header {
	__le32 csum;
	__le32 flags;
	__le64 blocknr; /* Block this node is supposed to live in. */

	__le32 nr_entries;
	__le32 max_entries;
	__le32 value_size;
	__le32 padding;
} __packed;

struct btree_node {
	struct node_header header;
	__le64 keys[0];
} __packed;


void inc_children(struct dm_transaction_manager *tm, struct btree_node *n,
		  struct dm_btree_value_type *vt);

int new_block(struct dm_btree_info *info, struct dm_block **result);
int unlock_block(struct dm_btree_info *info, struct dm_block *b);

/*
 * Spines keep track of the rolling locks.  There are 2 variants, read-only
 * and one that uses shadowing.  These are separate structs to allow the
 * type checker to spot misuse, for example accidentally calling read_lock
 * on a shadow spine.
 */
struct ro_spine {
	struct dm_btree_info *info;

	int count;
	struct dm_block *nodes[2];
};

void init_ro_spine(struct ro_spine *s, struct dm_btree_info *info);
int exit_ro_spine(struct ro_spine *s);
int ro_step(struct ro_spine *s, dm_block_t new_child);
void ro_pop(struct ro_spine *s);
struct btree_node *ro_node(struct ro_spine *s);

struct shadow_spine {
	struct dm_btree_info *info;

	int count;
	struct dm_block *nodes[2];

	dm_block_t root;
};

void init_shadow_spine(struct shadow_spine *s, struct dm_btree_info *info);
int exit_shadow_spine(struct shadow_spine *s);

int shadow_step(struct shadow_spine *s, dm_block_t b,
		struct dm_btree_value_type *vt);

/*
 * The spine must have at least one entry before calling this.
 */
struct dm_block *shadow_current(struct shadow_spine *s);

/*
 * The spine must have at least two entries before calling this.
 */
struct dm_block *shadow_parent(struct shadow_spine *s);

int shadow_has_parent(struct shadow_spine *s);

int shadow_root(struct shadow_spine *s);

/*
 * Some inlines.
 */
static inline __le64 *key_ptr(struct btree_node *n, uint32_t index)
{
	return n->keys + index;
}

static inline void *value_base(struct btree_node *n)
{
	return &n->keys[le32_to_cpu(n->header.max_entries)];
}

static inline void *value_ptr(struct btree_node *n, uint32_t index)
{
	uint32_t value_size = le32_to_cpu(n->header.value_size);
	return value_base(n) + (value_size * index);
}

/*
 * Assumes the values are suitably-aligned and converts to core format.
 */
static inline uint64_t value64(struct btree_node *n, uint32_t index)
{
	__le64 *values_le = value_base(n);

	return le64_to_cpu(values_le[index]);
}

/*
 * Searching for a key within a single node.
 */
int lower_bound(struct btree_node *n, uint64_t key);

extern struct dm_block_validator btree_node_validator;

#endif	/* DM_BTREE_INTERNAL_H */
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	#ifndef DM_BTREE_INTERNAL_H
	8	#define DM_BTREE_INTERNAL_H
	9
	10	#include "dm-btree.h"
	11
	12	/----------------------------------------------------------------/
	13
	14	/*
	15	* We'll need 2 accessor functions for n->csum and n->blocknr
	16	* to support dm-btree-spine.c in that case.
	17	*/
	18
	19	enum node_flags {
	20	INTERNAL_NODE = 1,
	21	LEAF_NODE = 1 << 1
	22	};
	23
	24	/*
	25	* Every btree node begins with this structure. Make sure it's a multiple
	26	* of 8-bytes in size, otherwise the 64bit keys will be mis-aligned.
	27	*/
	28	struct node_header {
	29	__le32 csum;
	30	__le32 flags;
	31	__le64 blocknr; /* Block this node is supposed to live in. */
	32
	33	__le32 nr_entries;
	34	__le32 max_entries;
	35	__le32 value_size;
	36	__le32 padding;
	37	} __packed;
	38
550929fa	39	struct btree_node {
3241b1d3 JT	40	struct node_header header;
	41	__le64 keys[0];
	42	} __packed;
	43
	44
550929fa	45	void inc_children(struct dm_transaction_manager tm, struct btree_node n,
3241b1d3 JT	46	struct dm_btree_value_type *vt);
	47
	48	int new_block(struct dm_btree_info info, struct dm_block *result);
	49	int unlock_block(struct dm_btree_info info, struct dm_block b);
	50
	51	/*
	52	* Spines keep track of the rolling locks. There are 2 variants, read-only
	53	* and one that uses shadowing. These are separate structs to allow the
	54	* type checker to spot misuse, for example accidentally calling read_lock
	55	* on a shadow spine.
	56	*/
	57	struct ro_spine {
	58	struct dm_btree_info *info;
	59
	60	int count;
	61	struct dm_block *nodes[2];
	62	};
	63
	64	void init_ro_spine(struct ro_spine s, struct dm_btree_info info);
	65	int exit_ro_spine(struct ro_spine *s);
	66	int ro_step(struct ro_spine *s, dm_block_t new_child);
4e7f1f90	67	void ro_pop(struct ro_spine *s);
550929fa	68	struct btree_node ro_node(struct ro_spine s);
3241b1d3 JT	69
	70	struct shadow_spine {
	71	struct dm_btree_info *info;
	72
	73	int count;
	74	struct dm_block *nodes[2];
	75
	76	dm_block_t root;
	77	};
	78
	79	void init_shadow_spine(struct shadow_spine s, struct dm_btree_info info);
	80	int exit_shadow_spine(struct shadow_spine *s);
	81
	82	int shadow_step(struct shadow_spine *s, dm_block_t b,
	83	struct dm_btree_value_type *vt);
	84
	85	/*
	86	* The spine must have at least one entry before calling this.
	87	*/
	88	struct dm_block shadow_current(struct shadow_spine s);
	89
	90	/*
	91	* The spine must have at least two entries before calling this.
	92	*/
	93	struct dm_block shadow_parent(struct shadow_spine s);
	94
	95	int shadow_has_parent(struct shadow_spine *s);
	96
	97	int shadow_root(struct shadow_spine *s);
	98
	99	/*
	100	* Some inlines.
	101	*/
550929fa	102	static inline __le64 key_ptr(struct btree_node n, uint32_t index)
3241b1d3 JT	103	{
	104	return n->keys + index;
	105	}
	106
550929fa	107	static inline void value_base(struct btree_node n)
3241b1d3 JT	108	{
	109	return &n->keys[le32_to_cpu(n->header.max_entries)];
	110	}
	111
550929fa	112	static inline void value_ptr(struct btree_node n, uint32_t index)
3241b1d3	113	{
a3aefb39	114	uint32_t value_size = le32_to_cpu(n->header.value_size);
3241b1d3 JT	115	return value_base(n) + (value_size * index);
	116	}
	117
	118	/*
	119	* Assumes the values are suitably-aligned and converts to core format.
	120	*/
550929fa	121	static inline uint64_t value64(struct btree_node *n, uint32_t index)
3241b1d3 JT	122	{
	123	__le64 *values_le = value_base(n);
	124
	125	return le64_to_cpu(values_le[index]);
	126	}
	127
	128	/*
	129	* Searching for a key within a single node.
	130	*/
550929fa	131	int lower_bound(struct btree_node *n, uint64_t key);
3241b1d3 JT	132
	133	extern struct dm_block_validator btree_node_validator;
	134
	135	#endif /* DM_BTREE_INTERNAL_H */