1
2
3
4
5
6
7
8#include "btrfs.h"
9#include <log.h>
10#include <malloc.h>
11#include <memalign.h>
12
13int btrfs_comp_keys(struct btrfs_key *a, struct btrfs_key *b)
14{
15 if (a->objectid > b->objectid)
16 return 1;
17 if (a->objectid < b->objectid)
18 return -1;
19 if (a->type > b->type)
20 return 1;
21 if (a->type < b->type)
22 return -1;
23 if (a->offset > b->offset)
24 return 1;
25 if (a->offset < b->offset)
26 return -1;
27 return 0;
28}
29
30int btrfs_comp_keys_type(struct btrfs_key *a, struct btrfs_key *b)
31{
32 if (a->objectid > b->objectid)
33 return 1;
34 if (a->objectid < b->objectid)
35 return -1;
36 if (a->type > b->type)
37 return 1;
38 if (a->type < b->type)
39 return -1;
40 return 0;
41}
42
43static int generic_bin_search(void *addr, int item_size, struct btrfs_key *key,
44 int max, int *slot)
45{
46 int low = 0, high = max, mid, ret;
47 struct btrfs_key *tmp;
48
49 while (low < high) {
50 mid = (low + high) / 2;
51
52 tmp = (struct btrfs_key *) ((u8 *) addr + mid*item_size);
53 ret = btrfs_comp_keys(tmp, key);
54
55 if (ret < 0) {
56 low = mid + 1;
57 } else if (ret > 0) {
58 high = mid;
59 } else {
60 *slot = mid;
61 return 0;
62 }
63 }
64
65 *slot = low;
66 return 1;
67}
68
69int btrfs_bin_search(union btrfs_tree_node *p, struct btrfs_key *key,
70 int *slot)
71{
72 void *addr;
73 unsigned long size;
74
75 if (p->header.level) {
76 addr = p->node.ptrs;
77 size = sizeof(struct btrfs_key_ptr);
78 } else {
79 addr = p->leaf.items;
80 size = sizeof(struct btrfs_item);
81 }
82
83 return generic_bin_search(addr, size, key, p->header.nritems, slot);
84}
85
86static void clear_path(struct btrfs_path *p)
87{
88 int i;
89
90 for (i = 0; i < BTRFS_MAX_LEVEL; ++i) {
91 p->nodes[i] = NULL;
92 p->slots[i] = 0;
93 }
94}
95
96void btrfs_free_path(struct btrfs_path *p)
97{
98 int i;
99
100 for (i = 0; i < BTRFS_MAX_LEVEL; ++i) {
101 if (p->nodes[i])
102 free(p->nodes[i]);
103 }
104
105 clear_path(p);
106}
107
108static int read_tree_node(u64 physical, union btrfs_tree_node **buf)
109{
110 ALLOC_CACHE_ALIGN_BUFFER(struct btrfs_header, hdr,
111 sizeof(struct btrfs_header));
112 unsigned long size, offset = sizeof(*hdr);
113 union btrfs_tree_node *res;
114 u32 i;
115
116 if (!btrfs_devread(physical, sizeof(*hdr), hdr))
117 return -1;
118
119 btrfs_header_to_cpu(hdr);
120
121 if (hdr->level)
122 size = sizeof(struct btrfs_node)
123 + hdr->nritems * sizeof(struct btrfs_key_ptr);
124 else
125 size = btrfs_info.sb.nodesize;
126
127 res = malloc_cache_aligned(size);
128 if (!res) {
129 debug("%s: malloc failed\n", __func__);
130 return -1;
131 }
132
133 if (!btrfs_devread(physical + offset, size - offset,
134 ((u8 *) res) + offset)) {
135 free(res);
136 return -1;
137 }
138
139 memcpy(&res->header, hdr, sizeof(*hdr));
140 if (hdr->level)
141 for (i = 0; i < hdr->nritems; ++i)
142 btrfs_key_ptr_to_cpu(&res->node.ptrs[i]);
143 else
144 for (i = 0; i < hdr->nritems; ++i)
145 btrfs_item_to_cpu(&res->leaf.items[i]);
146
147 *buf = res;
148
149 return 0;
150}
151
152int btrfs_search_tree(const struct btrfs_root *root, struct btrfs_key *key,
153 struct btrfs_path *p)
154{
155 u8 lvl, prev_lvl;
156 int i, slot, ret;
157 u64 logical, physical;
158 union btrfs_tree_node *buf;
159
160 clear_path(p);
161
162 logical = root->bytenr;
163
164 for (i = 0; i < BTRFS_MAX_LEVEL; ++i) {
165 physical = btrfs_map_logical_to_physical(logical);
166 if (physical == -1ULL)
167 goto err;
168
169 if (read_tree_node(physical, &buf))
170 goto err;
171
172 lvl = buf->header.level;
173 if (i && prev_lvl != lvl + 1) {
174 printf("%s: invalid level in header at %llu\n",
175 __func__, logical);
176 goto err;
177 }
178 prev_lvl = lvl;
179
180 ret = btrfs_bin_search(buf, key, &slot);
181 if (ret < 0)
182 goto err;
183 if (ret && slot > 0 && lvl)
184 slot -= 1;
185
186 p->slots[lvl] = slot;
187 p->nodes[lvl] = buf;
188
189 if (lvl) {
190 logical = buf->node.ptrs[slot].blockptr;
191 } else {
192
193
194
195
196
197
198 if (slot >= buf->header.nritems)
199 if (btrfs_next_slot(p) < 0)
200 goto err;
201 break;
202 }
203 }
204
205 return 0;
206err:
207 btrfs_free_path(p);
208 return -1;
209}
210
211static int jump_leaf(struct btrfs_path *path, int dir)
212{
213 struct btrfs_path p;
214 u32 slot;
215 int level = 1, from_level, i;
216
217 dir = dir >= 0 ? 1 : -1;
218
219 p = *path;
220
221 while (level < BTRFS_MAX_LEVEL) {
222 if (!p.nodes[level])
223 return 1;
224
225 slot = p.slots[level];
226 if ((dir > 0 && slot + dir >= p.nodes[level]->header.nritems)
227 || (dir < 0 && !slot))
228 level++;
229 else
230 break;
231 }
232
233 if (level == BTRFS_MAX_LEVEL)
234 return 1;
235
236 p.slots[level] = slot + dir;
237 level--;
238 from_level = level;
239
240 while (level >= 0) {
241 u64 logical, physical;
242
243 slot = p.slots[level + 1];
244 logical = p.nodes[level + 1]->node.ptrs[slot].blockptr;
245 physical = btrfs_map_logical_to_physical(logical);
246 if (physical == -1ULL)
247 goto err;
248
249 if (read_tree_node(physical, &p.nodes[level]))
250 goto err;
251
252 if (dir > 0)
253 p.slots[level] = 0;
254 else
255 p.slots[level] = p.nodes[level]->header.nritems - 1;
256 level--;
257 }
258
259
260 for (i = 0; i <= from_level; ++i)
261 free(path->nodes[i]);
262
263 *path = p;
264 return 0;
265
266err:
267
268 for (i = level + 1; i <= from_level; ++i)
269 free(p.nodes[i]);
270 return -1;
271}
272
273int btrfs_prev_slot(struct btrfs_path *p)
274{
275 if (!p->slots[0])
276 return jump_leaf(p, -1);
277
278 p->slots[0]--;
279 return 0;
280}
281
282int btrfs_next_slot(struct btrfs_path *p)
283{
284 struct btrfs_leaf *leaf = &p->nodes[0]->leaf;
285
286 if (p->slots[0] + 1 >= leaf->header.nritems)
287 return jump_leaf(p, 1);
288
289 p->slots[0]++;
290 return 0;
291}
292
