1/* SPDX-License-Identifier: GPL-2.0-only */
  2/*
  3 * Copyright (C) 2011 Red Hat, Inc.
  4 *
  5 * This file is released under the GPL.
  6 */
  7
  8#ifndef DM_BTREE_INTERNAL_H
  9#define DM_BTREE_INTERNAL_H
 10
 11#include "dm-btree.h"
 12
 13/*----------------------------------------------------------------*/
 14
 15/*
 16 * We'll need 2 accessor functions for n->csum and n->blocknr
 17 * to support dm-btree-spine.c in that case.
 18 */
 19
 20enum node_flags {
 21	INTERNAL_NODE = 1,
 22	LEAF_NODE = 1 << 1
 23};
 24
 25/*
 26 * Every btree node begins with this structure.  Make sure it's a multiple
 27 * of 8-bytes in size, otherwise the 64bit keys will be mis-aligned.
 28 */
 29struct node_header {
 30	__le32 csum;
 31	__le32 flags;
 32	__le64 blocknr; /* Block this node is supposed to live in. */
 33
 34	__le32 nr_entries;
 35	__le32 max_entries;
 36	__le32 value_size;
 37	__le32 padding;
 38} __packed __aligned(8);
 39
 40struct btree_node {
 41	struct node_header header;
 42	__le64 keys[];
 43} __packed __aligned(8);
 44
 45
 46/*
 47 * Locks a block using the btree node validator.
 48 */
 49int bn_read_lock(struct dm_btree_info *info, dm_block_t b,
 50		 struct dm_block **result);
 51
 52void inc_children(struct dm_transaction_manager *tm, struct btree_node *n,
 53		  struct dm_btree_value_type *vt);
 54
 55int new_block(struct dm_btree_info *info, struct dm_block **result);
 56void unlock_block(struct dm_btree_info *info, struct dm_block *b);
 57
 58/*
 59 * Spines keep track of the rolling locks.  There are 2 variants, read-only
 60 * and one that uses shadowing.  These are separate structs to allow the
 61 * type checker to spot misuse, for example accidentally calling read_lock
 62 * on a shadow spine.
 63 */
 64struct ro_spine {
 65	struct dm_btree_info *info;
 66
 67	int count;
 68	struct dm_block *nodes[2];
 69};
 70
 71void init_ro_spine(struct ro_spine *s, struct dm_btree_info *info);
 72void exit_ro_spine(struct ro_spine *s);
 73int ro_step(struct ro_spine *s, dm_block_t new_child);
 74void ro_pop(struct ro_spine *s);
 75struct btree_node *ro_node(struct ro_spine *s);
 76
 77struct shadow_spine {
 78	struct dm_btree_info *info;
 79
 80	int count;
 81	struct dm_block *nodes[2];
 82
 83	dm_block_t root;
 84};
 85
 86void init_shadow_spine(struct shadow_spine *s, struct dm_btree_info *info);
 87void exit_shadow_spine(struct shadow_spine *s);
 88
 89int shadow_step(struct shadow_spine *s, dm_block_t b,
 90		struct dm_btree_value_type *vt);
 91
 92/*
 93 * The spine must have at least one entry before calling this.
 94 */
 95struct dm_block *shadow_current(struct shadow_spine *s);
 96
 97/*
 98 * The spine must have at least two entries before calling this.
 99 */
100struct dm_block *shadow_parent(struct shadow_spine *s);
101
102int shadow_has_parent(struct shadow_spine *s);
103
104dm_block_t shadow_root(struct shadow_spine *s);
105
106/*
107 * Some inlines.
108 */
109static inline __le64 *key_ptr(struct btree_node *n, uint32_t index)
110{
111	return n->keys + index;
112}
113
114static inline void *value_base(struct btree_node *n)
115{
116	return &n->keys[le32_to_cpu(n->header.max_entries)];
117}
118
119static inline void *value_ptr(struct btree_node *n, uint32_t index)
120{
121	uint32_t value_size = le32_to_cpu(n->header.value_size);
122
123	return value_base(n) + (value_size * index);
124}
125
126/*
127 * Assumes the values are suitably-aligned and converts to core format.
128 */
129static inline uint64_t value64(struct btree_node *n, uint32_t index)
130{
131	__le64 *values_le = value_base(n);
132
133	return le64_to_cpu(values_le[index]);
134}
135
136/*
137 * Searching for a key within a single node.
138 */
139int lower_bound(struct btree_node *n, uint64_t key);
140
141extern struct dm_block_validator btree_node_validator;
142
143/*
144 * Value type for upper levels of multi-level btrees.
145 */
146extern void init_le64_type(struct dm_transaction_manager *tm,
147			   struct dm_btree_value_type *vt);
148
149/*
150 * This returns a shadowed btree leaf that you may modify.  In practise
151 * this means overwrites only, since an insert could cause a node to
152 * be split.  Useful if you need access to the old value to calculate the
153 * new one.
154 *
155 * This only works with single level btrees.  The given key must be present in
156 * the tree, otherwise -EINVAL will be returned.
157 */
158int btree_get_overwrite_leaf(struct dm_btree_info *info, dm_block_t root,
159			     uint64_t key, int *index,
160			     dm_block_t *new_root, struct dm_block **leaf);
161
162#endif	/* DM_BTREE_INTERNAL_H */