dm-btree-internal.h 3.1 KB
Newer Older
J
Joe Thornber 已提交
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38
/*
 * 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;

39
struct btree_node {
J
Joe Thornber 已提交
40 41 42 43 44
	struct node_header header;
	__le64 keys[0];
} __packed;


45
void inc_children(struct dm_transaction_manager *tm, struct btree_node *n,
J
Joe Thornber 已提交
46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66
		  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);
67
void ro_pop(struct ro_spine *s);
68
struct btree_node *ro_node(struct ro_spine *s);
J
Joe Thornber 已提交
69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101

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.
 */
102
static inline __le64 *key_ptr(struct btree_node *n, uint32_t index)
J
Joe Thornber 已提交
103 104 105 106
{
	return n->keys + index;
}

107
static inline void *value_base(struct btree_node *n)
J
Joe Thornber 已提交
108 109 110 111
{
	return &n->keys[le32_to_cpu(n->header.max_entries)];
}

112
static inline void *value_ptr(struct btree_node *n, uint32_t index)
J
Joe Thornber 已提交
113
{
114
	uint32_t value_size = le32_to_cpu(n->header.value_size);
J
Joe Thornber 已提交
115 116 117 118 119 120
	return value_base(n) + (value_size * index);
}

/*
 * Assumes the values are suitably-aligned and converts to core format.
 */
121
static inline uint64_t value64(struct btree_node *n, uint32_t index)
J
Joe Thornber 已提交
122 123 124 125 126 127 128 129 130
{
	__le64 *values_le = value_base(n);

	return le64_to_cpu(values_le[index]);
}

/*
 * Searching for a key within a single node.
 */
131
int lower_bound(struct btree_node *n, uint64_t key);
J
Joe Thornber 已提交
132 133 134 135

extern struct dm_block_validator btree_node_validator;

#endif	/* DM_BTREE_INTERNAL_H */