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
 19enum 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 */
 28struct 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} __attribute__((packed, aligned(8)));
 38
 39struct btree_node {
 40	struct node_header header;
 41	__le64 keys[];
 42} __attribute__((packed, aligned(8)));
 43
 44
 45/*
 46 * Locks a block using the btree node validator.
 47 */
 48int bn_read_lock(struct dm_btree_info *info, dm_block_t b,
 49		 struct dm_block **result);
 50
 51void inc_children(struct dm_transaction_manager *tm, struct btree_node *n,
 52		  struct dm_btree_value_type *vt);
 53
 54int new_block(struct dm_btree_info *info, struct dm_block **result);
 55void unlock_block(struct dm_btree_info *info, struct dm_block *b);
 56
 57/*
 58 * Spines keep track of the rolling locks.  There are 2 variants, read-only
 59 * and one that uses shadowing.  These are separate structs to allow the
 60 * type checker to spot misuse, for example accidentally calling read_lock
 61 * on a shadow spine.
 62 */
 63struct ro_spine {
 64	struct dm_btree_info *info;
 65
 66	int count;
 67	struct dm_block *nodes[2];
 68};
 69
 70void init_ro_spine(struct ro_spine *s, struct dm_btree_info *info);
 71void exit_ro_spine(struct ro_spine *s);
 72int ro_step(struct ro_spine *s, dm_block_t new_child);
 73void ro_pop(struct ro_spine *s);
 74struct btree_node *ro_node(struct ro_spine *s);
 75
 76struct shadow_spine {
 77	struct dm_btree_info *info;
 78
 79	int count;
 80	struct dm_block *nodes[2];
 81
 82	dm_block_t root;
 83};
 84
 85void init_shadow_spine(struct shadow_spine *s, struct dm_btree_info *info);
 86void exit_shadow_spine(struct shadow_spine *s);
 87
 88int shadow_step(struct shadow_spine *s, dm_block_t b,
 89		struct dm_btree_value_type *vt);
 90
 91/*
 92 * The spine must have at least one entry before calling this.
 93 */
 94struct dm_block *shadow_current(struct shadow_spine *s);
 95
 96/*
 97 * The spine must have at least two entries before calling this.
 98 */
 99struct dm_block *shadow_parent(struct shadow_spine *s);
100
101int shadow_has_parent(struct shadow_spine *s);
102
103dm_block_t shadow_root(struct shadow_spine *s);
104
105/*
106 * Some inlines.
107 */
108static inline __le64 *key_ptr(struct btree_node *n, uint32_t index)
109{
110	return n->keys + index;
111}
112
113static inline void *value_base(struct btree_node *n)
114{
115	return &n->keys[le32_to_cpu(n->header.max_entries)];
116}
117
118static inline void *value_ptr(struct btree_node *n, uint32_t index)
119{
120	uint32_t value_size = le32_to_cpu(n->header.value_size);
121	return value_base(n) + (value_size * index);
122}
123
124/*
125 * Assumes the values are suitably-aligned and converts to core format.
126 */
127static inline uint64_t value64(struct btree_node *n, uint32_t index)
128{
129	__le64 *values_le = value_base(n);
130
131	return le64_to_cpu(values_le[index]);
132}
133
134/*
135 * Searching for a key within a single node.
136 */
137int lower_bound(struct btree_node *n, uint64_t key);
138
139extern struct dm_block_validator btree_node_validator;
140
141/*
142 * Value type for upper levels of multi-level btrees.
143 */
144extern void init_le64_type(struct dm_transaction_manager *tm,
145			   struct dm_btree_value_type *vt);
146
147/*
148 * This returns a shadowed btree leaf that you may modify.  In practise
149 * this means overwrites only, since an insert could cause a node to
150 * be split.  Useful if you need access to the old value to calculate the
151 * new one.
152 *
153 * This only works with single level btrees.  The given key must be present in
154 * the tree, otherwise -EINVAL will be returned.
155 */
156int btree_get_overwrite_leaf(struct dm_btree_info *info, dm_block_t root,
157			     uint64_t key, int *index,
158			     dm_block_t *new_root, struct dm_block **leaf);
159
160#endif	/* DM_BTREE_INTERNAL_H */