| rjw | 1f88458 | 2022-01-06 17:20:42 +0800 | [diff] [blame] | 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 | |
| 39 | struct btree_node { |
| 40 | struct node_header header; |
| 41 | __le64 keys[0]; |
| 42 | } __packed; |
| 43 | |
| 44 | |
| 45 | /* |
| 46 | * Locks a block using the btree node validator. |
| 47 | */ |
| 48 | int bn_read_lock(struct dm_btree_info *info, dm_block_t b, |
| 49 | struct dm_block **result); |
| 50 | |
| 51 | void inc_children(struct dm_transaction_manager *tm, struct btree_node *n, |
| 52 | struct dm_btree_value_type *vt); |
| 53 | |
| 54 | int new_block(struct dm_btree_info *info, struct dm_block **result); |
| 55 | void 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 | */ |
| 63 | struct ro_spine { |
| 64 | struct dm_btree_info *info; |
| 65 | |
| 66 | int count; |
| 67 | struct dm_block *nodes[2]; |
| 68 | }; |
| 69 | |
| 70 | void init_ro_spine(struct ro_spine *s, struct dm_btree_info *info); |
| 71 | int exit_ro_spine(struct ro_spine *s); |
| 72 | int ro_step(struct ro_spine *s, dm_block_t new_child); |
| 73 | void ro_pop(struct ro_spine *s); |
| 74 | struct btree_node *ro_node(struct ro_spine *s); |
| 75 | |
| 76 | struct 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 | |
| 85 | void init_shadow_spine(struct shadow_spine *s, struct dm_btree_info *info); |
| 86 | int exit_shadow_spine(struct shadow_spine *s); |
| 87 | |
| 88 | int 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 | */ |
| 94 | struct dm_block *shadow_current(struct shadow_spine *s); |
| 95 | |
| 96 | /* |
| 97 | * The spine must have at least two entries before calling this. |
| 98 | */ |
| 99 | struct dm_block *shadow_parent(struct shadow_spine *s); |
| 100 | |
| 101 | int shadow_has_parent(struct shadow_spine *s); |
| 102 | |
| 103 | int shadow_root(struct shadow_spine *s); |
| 104 | |
| 105 | /* |
| 106 | * Some inlines. |
| 107 | */ |
| 108 | static inline __le64 *key_ptr(struct btree_node *n, uint32_t index) |
| 109 | { |
| 110 | return n->keys + index; |
| 111 | } |
| 112 | |
| 113 | static inline void *value_base(struct btree_node *n) |
| 114 | { |
| 115 | return &n->keys[le32_to_cpu(n->header.max_entries)]; |
| 116 | } |
| 117 | |
| 118 | static 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 | */ |
| 127 | static 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 | */ |
| 137 | int lower_bound(struct btree_node *n, uint64_t key); |
| 138 | |
| 139 | extern struct dm_block_validator btree_node_validator; |
| 140 | |
| 141 | /* |
| 142 | * Value type for upper levels of multi-level btrees. |
| 143 | */ |
| 144 | extern void init_le64_type(struct dm_transaction_manager *tm, |
| 145 | struct dm_btree_value_type *vt); |
| 146 | |
| 147 | #endif /* DM_BTREE_INTERNAL_H */ |