diff options
Diffstat (limited to 'fs/btrfs/ctree.c')
-rw-r--r-- | fs/btrfs/ctree.c | 3450 |
1 files changed, 3450 insertions, 0 deletions
diff --git a/fs/btrfs/ctree.c b/fs/btrfs/ctree.c new file mode 100644 index 000000000000..50aea8cb653a --- /dev/null +++ b/fs/btrfs/ctree.c | |||
@@ -0,0 +1,3450 @@ | |||
1 | /* | ||
2 | * Copyright (C) 2007 Oracle. All rights reserved. | ||
3 | * | ||
4 | * This program is free software; you can redistribute it and/or | ||
5 | * modify it under the terms of the GNU General Public | ||
6 | * License v2 as published by the Free Software Foundation. | ||
7 | * | ||
8 | * This program is distributed in the hope that it will be useful, | ||
9 | * but WITHOUT ANY WARRANTY; without even the implied warranty of | ||
10 | * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU | ||
11 | * General Public License for more details. | ||
12 | * | ||
13 | * You should have received a copy of the GNU General Public | ||
14 | * License along with this program; if not, write to the | ||
15 | * Free Software Foundation, Inc., 59 Temple Place - Suite 330, | ||
16 | * Boston, MA 021110-1307, USA. | ||
17 | */ | ||
18 | |||
19 | #include <linux/sched.h> | ||
20 | #include "ctree.h" | ||
21 | #include "disk-io.h" | ||
22 | #include "transaction.h" | ||
23 | #include "print-tree.h" | ||
24 | #include "locking.h" | ||
25 | |||
26 | static int split_node(struct btrfs_trans_handle *trans, struct btrfs_root | ||
27 | *root, struct btrfs_path *path, int level); | ||
28 | static int split_leaf(struct btrfs_trans_handle *trans, struct btrfs_root | ||
29 | *root, struct btrfs_key *ins_key, | ||
30 | struct btrfs_path *path, int data_size, int extend); | ||
31 | static int push_node_left(struct btrfs_trans_handle *trans, | ||
32 | struct btrfs_root *root, struct extent_buffer *dst, | ||
33 | struct extent_buffer *src, int empty); | ||
34 | static int balance_node_right(struct btrfs_trans_handle *trans, | ||
35 | struct btrfs_root *root, | ||
36 | struct extent_buffer *dst_buf, | ||
37 | struct extent_buffer *src_buf); | ||
38 | static int del_ptr(struct btrfs_trans_handle *trans, struct btrfs_root *root, | ||
39 | struct btrfs_path *path, int level, int slot); | ||
40 | |||
41 | inline void btrfs_init_path(struct btrfs_path *p) | ||
42 | { | ||
43 | memset(p, 0, sizeof(*p)); | ||
44 | } | ||
45 | |||
46 | struct btrfs_path *btrfs_alloc_path(void) | ||
47 | { | ||
48 | struct btrfs_path *path; | ||
49 | path = kmem_cache_alloc(btrfs_path_cachep, GFP_NOFS); | ||
50 | if (path) { | ||
51 | btrfs_init_path(path); | ||
52 | path->reada = 1; | ||
53 | } | ||
54 | return path; | ||
55 | } | ||
56 | |||
57 | void btrfs_free_path(struct btrfs_path *p) | ||
58 | { | ||
59 | btrfs_release_path(NULL, p); | ||
60 | kmem_cache_free(btrfs_path_cachep, p); | ||
61 | } | ||
62 | |||
63 | void noinline btrfs_release_path(struct btrfs_root *root, struct btrfs_path *p) | ||
64 | { | ||
65 | int i; | ||
66 | |||
67 | for (i = 0; i < BTRFS_MAX_LEVEL; i++) { | ||
68 | p->slots[i] = 0; | ||
69 | if (!p->nodes[i]) | ||
70 | continue; | ||
71 | if (p->locks[i]) { | ||
72 | btrfs_tree_unlock(p->nodes[i]); | ||
73 | p->locks[i] = 0; | ||
74 | } | ||
75 | free_extent_buffer(p->nodes[i]); | ||
76 | p->nodes[i] = NULL; | ||
77 | } | ||
78 | } | ||
79 | |||
80 | struct extent_buffer *btrfs_root_node(struct btrfs_root *root) | ||
81 | { | ||
82 | struct extent_buffer *eb; | ||
83 | spin_lock(&root->node_lock); | ||
84 | eb = root->node; | ||
85 | extent_buffer_get(eb); | ||
86 | spin_unlock(&root->node_lock); | ||
87 | return eb; | ||
88 | } | ||
89 | |||
90 | struct extent_buffer *btrfs_lock_root_node(struct btrfs_root *root) | ||
91 | { | ||
92 | struct extent_buffer *eb; | ||
93 | |||
94 | while(1) { | ||
95 | eb = btrfs_root_node(root); | ||
96 | btrfs_tree_lock(eb); | ||
97 | |||
98 | spin_lock(&root->node_lock); | ||
99 | if (eb == root->node) { | ||
100 | spin_unlock(&root->node_lock); | ||
101 | break; | ||
102 | } | ||
103 | spin_unlock(&root->node_lock); | ||
104 | |||
105 | btrfs_tree_unlock(eb); | ||
106 | free_extent_buffer(eb); | ||
107 | } | ||
108 | return eb; | ||
109 | } | ||
110 | |||
111 | static void add_root_to_dirty_list(struct btrfs_root *root) | ||
112 | { | ||
113 | if (root->track_dirty && list_empty(&root->dirty_list)) { | ||
114 | list_add(&root->dirty_list, | ||
115 | &root->fs_info->dirty_cowonly_roots); | ||
116 | } | ||
117 | } | ||
118 | |||
119 | int btrfs_copy_root(struct btrfs_trans_handle *trans, | ||
120 | struct btrfs_root *root, | ||
121 | struct extent_buffer *buf, | ||
122 | struct extent_buffer **cow_ret, u64 new_root_objectid) | ||
123 | { | ||
124 | struct extent_buffer *cow; | ||
125 | u32 nritems; | ||
126 | int ret = 0; | ||
127 | int level; | ||
128 | struct btrfs_root *new_root; | ||
129 | |||
130 | new_root = kmalloc(sizeof(*new_root), GFP_NOFS); | ||
131 | if (!new_root) | ||
132 | return -ENOMEM; | ||
133 | |||
134 | memcpy(new_root, root, sizeof(*new_root)); | ||
135 | new_root->root_key.objectid = new_root_objectid; | ||
136 | |||
137 | WARN_ON(root->ref_cows && trans->transid != | ||
138 | root->fs_info->running_transaction->transid); | ||
139 | WARN_ON(root->ref_cows && trans->transid != root->last_trans); | ||
140 | |||
141 | level = btrfs_header_level(buf); | ||
142 | nritems = btrfs_header_nritems(buf); | ||
143 | |||
144 | cow = btrfs_alloc_free_block(trans, new_root, buf->len, 0, | ||
145 | new_root_objectid, trans->transid, | ||
146 | level, buf->start, 0); | ||
147 | if (IS_ERR(cow)) { | ||
148 | kfree(new_root); | ||
149 | return PTR_ERR(cow); | ||
150 | } | ||
151 | |||
152 | copy_extent_buffer(cow, buf, 0, 0, cow->len); | ||
153 | btrfs_set_header_bytenr(cow, cow->start); | ||
154 | btrfs_set_header_generation(cow, trans->transid); | ||
155 | btrfs_set_header_owner(cow, new_root_objectid); | ||
156 | btrfs_clear_header_flag(cow, BTRFS_HEADER_FLAG_WRITTEN); | ||
157 | |||
158 | WARN_ON(btrfs_header_generation(buf) > trans->transid); | ||
159 | ret = btrfs_inc_ref(trans, new_root, buf, cow, NULL); | ||
160 | kfree(new_root); | ||
161 | |||
162 | if (ret) | ||
163 | return ret; | ||
164 | |||
165 | btrfs_mark_buffer_dirty(cow); | ||
166 | *cow_ret = cow; | ||
167 | return 0; | ||
168 | } | ||
169 | |||
170 | int noinline __btrfs_cow_block(struct btrfs_trans_handle *trans, | ||
171 | struct btrfs_root *root, | ||
172 | struct extent_buffer *buf, | ||
173 | struct extent_buffer *parent, int parent_slot, | ||
174 | struct extent_buffer **cow_ret, | ||
175 | u64 search_start, u64 empty_size, | ||
176 | u64 prealloc_dest) | ||
177 | { | ||
178 | u64 parent_start; | ||
179 | struct extent_buffer *cow; | ||
180 | u32 nritems; | ||
181 | int ret = 0; | ||
182 | int different_trans = 0; | ||
183 | int level; | ||
184 | int unlock_orig = 0; | ||
185 | |||
186 | if (*cow_ret == buf) | ||
187 | unlock_orig = 1; | ||
188 | |||
189 | WARN_ON(!btrfs_tree_locked(buf)); | ||
190 | |||
191 | if (parent) | ||
192 | parent_start = parent->start; | ||
193 | else | ||
194 | parent_start = 0; | ||
195 | |||
196 | WARN_ON(root->ref_cows && trans->transid != | ||
197 | root->fs_info->running_transaction->transid); | ||
198 | WARN_ON(root->ref_cows && trans->transid != root->last_trans); | ||
199 | |||
200 | level = btrfs_header_level(buf); | ||
201 | nritems = btrfs_header_nritems(buf); | ||
202 | |||
203 | if (prealloc_dest) { | ||
204 | struct btrfs_key ins; | ||
205 | |||
206 | ins.objectid = prealloc_dest; | ||
207 | ins.offset = buf->len; | ||
208 | ins.type = BTRFS_EXTENT_ITEM_KEY; | ||
209 | |||
210 | ret = btrfs_alloc_reserved_extent(trans, root, parent_start, | ||
211 | root->root_key.objectid, | ||
212 | trans->transid, level, 0, | ||
213 | &ins); | ||
214 | BUG_ON(ret); | ||
215 | cow = btrfs_init_new_buffer(trans, root, prealloc_dest, | ||
216 | buf->len); | ||
217 | } else { | ||
218 | cow = btrfs_alloc_free_block(trans, root, buf->len, | ||
219 | parent_start, | ||
220 | root->root_key.objectid, | ||
221 | trans->transid, level, | ||
222 | search_start, empty_size); | ||
223 | } | ||
224 | if (IS_ERR(cow)) | ||
225 | return PTR_ERR(cow); | ||
226 | |||
227 | copy_extent_buffer(cow, buf, 0, 0, cow->len); | ||
228 | btrfs_set_header_bytenr(cow, cow->start); | ||
229 | btrfs_set_header_generation(cow, trans->transid); | ||
230 | btrfs_set_header_owner(cow, root->root_key.objectid); | ||
231 | btrfs_clear_header_flag(cow, BTRFS_HEADER_FLAG_WRITTEN); | ||
232 | |||
233 | WARN_ON(btrfs_header_generation(buf) > trans->transid); | ||
234 | if (btrfs_header_generation(buf) != trans->transid) { | ||
235 | u32 nr_extents; | ||
236 | different_trans = 1; | ||
237 | ret = btrfs_inc_ref(trans, root, buf, cow, &nr_extents); | ||
238 | if (ret) | ||
239 | return ret; | ||
240 | |||
241 | ret = btrfs_cache_ref(trans, root, buf, nr_extents); | ||
242 | WARN_ON(ret); | ||
243 | } else { | ||
244 | ret = btrfs_update_ref(trans, root, buf, cow, 0, nritems); | ||
245 | if (ret) | ||
246 | return ret; | ||
247 | clean_tree_block(trans, root, buf); | ||
248 | } | ||
249 | |||
250 | if (buf == root->node) { | ||
251 | WARN_ON(parent && parent != buf); | ||
252 | |||
253 | spin_lock(&root->node_lock); | ||
254 | root->node = cow; | ||
255 | extent_buffer_get(cow); | ||
256 | spin_unlock(&root->node_lock); | ||
257 | |||
258 | if (buf != root->commit_root) { | ||
259 | btrfs_free_extent(trans, root, buf->start, | ||
260 | buf->len, buf->start, | ||
261 | root->root_key.objectid, | ||
262 | btrfs_header_generation(buf), | ||
263 | 0, 0, 1); | ||
264 | } | ||
265 | free_extent_buffer(buf); | ||
266 | add_root_to_dirty_list(root); | ||
267 | } else { | ||
268 | btrfs_set_node_blockptr(parent, parent_slot, | ||
269 | cow->start); | ||
270 | WARN_ON(trans->transid == 0); | ||
271 | btrfs_set_node_ptr_generation(parent, parent_slot, | ||
272 | trans->transid); | ||
273 | btrfs_mark_buffer_dirty(parent); | ||
274 | WARN_ON(btrfs_header_generation(parent) != trans->transid); | ||
275 | btrfs_free_extent(trans, root, buf->start, buf->len, | ||
276 | parent_start, btrfs_header_owner(parent), | ||
277 | btrfs_header_generation(parent), 0, 0, 1); | ||
278 | } | ||
279 | if (unlock_orig) | ||
280 | btrfs_tree_unlock(buf); | ||
281 | free_extent_buffer(buf); | ||
282 | btrfs_mark_buffer_dirty(cow); | ||
283 | *cow_ret = cow; | ||
284 | return 0; | ||
285 | } | ||
286 | |||
287 | int noinline btrfs_cow_block(struct btrfs_trans_handle *trans, | ||
288 | struct btrfs_root *root, struct extent_buffer *buf, | ||
289 | struct extent_buffer *parent, int parent_slot, | ||
290 | struct extent_buffer **cow_ret, u64 prealloc_dest) | ||
291 | { | ||
292 | u64 search_start; | ||
293 | u64 header_trans; | ||
294 | int ret; | ||
295 | |||
296 | if (trans->transaction != root->fs_info->running_transaction) { | ||
297 | printk(KERN_CRIT "trans %Lu running %Lu\n", trans->transid, | ||
298 | root->fs_info->running_transaction->transid); | ||
299 | WARN_ON(1); | ||
300 | } | ||
301 | if (trans->transid != root->fs_info->generation) { | ||
302 | printk(KERN_CRIT "trans %Lu running %Lu\n", trans->transid, | ||
303 | root->fs_info->generation); | ||
304 | WARN_ON(1); | ||
305 | } | ||
306 | |||
307 | header_trans = btrfs_header_generation(buf); | ||
308 | spin_lock(&root->fs_info->hash_lock); | ||
309 | if (header_trans == trans->transid && | ||
310 | !btrfs_header_flag(buf, BTRFS_HEADER_FLAG_WRITTEN)) { | ||
311 | *cow_ret = buf; | ||
312 | spin_unlock(&root->fs_info->hash_lock); | ||
313 | WARN_ON(prealloc_dest); | ||
314 | return 0; | ||
315 | } | ||
316 | spin_unlock(&root->fs_info->hash_lock); | ||
317 | search_start = buf->start & ~((u64)(1024 * 1024 * 1024) - 1); | ||
318 | ret = __btrfs_cow_block(trans, root, buf, parent, | ||
319 | parent_slot, cow_ret, search_start, 0, | ||
320 | prealloc_dest); | ||
321 | return ret; | ||
322 | } | ||
323 | |||
324 | static int close_blocks(u64 blocknr, u64 other, u32 blocksize) | ||
325 | { | ||
326 | if (blocknr < other && other - (blocknr + blocksize) < 32768) | ||
327 | return 1; | ||
328 | if (blocknr > other && blocknr - (other + blocksize) < 32768) | ||
329 | return 1; | ||
330 | return 0; | ||
331 | } | ||
332 | |||
333 | /* | ||
334 | * compare two keys in a memcmp fashion | ||
335 | */ | ||
336 | static int comp_keys(struct btrfs_disk_key *disk, struct btrfs_key *k2) | ||
337 | { | ||
338 | struct btrfs_key k1; | ||
339 | |||
340 | btrfs_disk_key_to_cpu(&k1, disk); | ||
341 | |||
342 | if (k1.objectid > k2->objectid) | ||
343 | return 1; | ||
344 | if (k1.objectid < k2->objectid) | ||
345 | return -1; | ||
346 | if (k1.type > k2->type) | ||
347 | return 1; | ||
348 | if (k1.type < k2->type) | ||
349 | return -1; | ||
350 | if (k1.offset > k2->offset) | ||
351 | return 1; | ||
352 | if (k1.offset < k2->offset) | ||
353 | return -1; | ||
354 | return 0; | ||
355 | } | ||
356 | |||
357 | |||
358 | int btrfs_realloc_node(struct btrfs_trans_handle *trans, | ||
359 | struct btrfs_root *root, struct extent_buffer *parent, | ||
360 | int start_slot, int cache_only, u64 *last_ret, | ||
361 | struct btrfs_key *progress) | ||
362 | { | ||
363 | struct extent_buffer *cur; | ||
364 | u64 blocknr; | ||
365 | u64 gen; | ||
366 | u64 search_start = *last_ret; | ||
367 | u64 last_block = 0; | ||
368 | u64 other; | ||
369 | u32 parent_nritems; | ||
370 | int end_slot; | ||
371 | int i; | ||
372 | int err = 0; | ||
373 | int parent_level; | ||
374 | int uptodate; | ||
375 | u32 blocksize; | ||
376 | int progress_passed = 0; | ||
377 | struct btrfs_disk_key disk_key; | ||
378 | |||
379 | parent_level = btrfs_header_level(parent); | ||
380 | if (cache_only && parent_level != 1) | ||
381 | return 0; | ||
382 | |||
383 | if (trans->transaction != root->fs_info->running_transaction) { | ||
384 | printk(KERN_CRIT "trans %Lu running %Lu\n", trans->transid, | ||
385 | root->fs_info->running_transaction->transid); | ||
386 | WARN_ON(1); | ||
387 | } | ||
388 | if (trans->transid != root->fs_info->generation) { | ||
389 | printk(KERN_CRIT "trans %Lu running %Lu\n", trans->transid, | ||
390 | root->fs_info->generation); | ||
391 | WARN_ON(1); | ||
392 | } | ||
393 | |||
394 | parent_nritems = btrfs_header_nritems(parent); | ||
395 | blocksize = btrfs_level_size(root, parent_level - 1); | ||
396 | end_slot = parent_nritems; | ||
397 | |||
398 | if (parent_nritems == 1) | ||
399 | return 0; | ||
400 | |||
401 | for (i = start_slot; i < end_slot; i++) { | ||
402 | int close = 1; | ||
403 | |||
404 | if (!parent->map_token) { | ||
405 | map_extent_buffer(parent, | ||
406 | btrfs_node_key_ptr_offset(i), | ||
407 | sizeof(struct btrfs_key_ptr), | ||
408 | &parent->map_token, &parent->kaddr, | ||
409 | &parent->map_start, &parent->map_len, | ||
410 | KM_USER1); | ||
411 | } | ||
412 | btrfs_node_key(parent, &disk_key, i); | ||
413 | if (!progress_passed && comp_keys(&disk_key, progress) < 0) | ||
414 | continue; | ||
415 | |||
416 | progress_passed = 1; | ||
417 | blocknr = btrfs_node_blockptr(parent, i); | ||
418 | gen = btrfs_node_ptr_generation(parent, i); | ||
419 | if (last_block == 0) | ||
420 | last_block = blocknr; | ||
421 | |||
422 | if (i > 0) { | ||
423 | other = btrfs_node_blockptr(parent, i - 1); | ||
424 | close = close_blocks(blocknr, other, blocksize); | ||
425 | } | ||
426 | if (!close && i < end_slot - 2) { | ||
427 | other = btrfs_node_blockptr(parent, i + 1); | ||
428 | close = close_blocks(blocknr, other, blocksize); | ||
429 | } | ||
430 | if (close) { | ||
431 | last_block = blocknr; | ||
432 | continue; | ||
433 | } | ||
434 | if (parent->map_token) { | ||
435 | unmap_extent_buffer(parent, parent->map_token, | ||
436 | KM_USER1); | ||
437 | parent->map_token = NULL; | ||
438 | } | ||
439 | |||
440 | cur = btrfs_find_tree_block(root, blocknr, blocksize); | ||
441 | if (cur) | ||
442 | uptodate = btrfs_buffer_uptodate(cur, gen); | ||
443 | else | ||
444 | uptodate = 0; | ||
445 | if (!cur || !uptodate) { | ||
446 | if (cache_only) { | ||
447 | free_extent_buffer(cur); | ||
448 | continue; | ||
449 | } | ||
450 | if (!cur) { | ||
451 | cur = read_tree_block(root, blocknr, | ||
452 | blocksize, gen); | ||
453 | } else if (!uptodate) { | ||
454 | btrfs_read_buffer(cur, gen); | ||
455 | } | ||
456 | } | ||
457 | if (search_start == 0) | ||
458 | search_start = last_block; | ||
459 | |||
460 | btrfs_tree_lock(cur); | ||
461 | err = __btrfs_cow_block(trans, root, cur, parent, i, | ||
462 | &cur, search_start, | ||
463 | min(16 * blocksize, | ||
464 | (end_slot - i) * blocksize), 0); | ||
465 | if (err) { | ||
466 | btrfs_tree_unlock(cur); | ||
467 | free_extent_buffer(cur); | ||
468 | break; | ||
469 | } | ||
470 | search_start = cur->start; | ||
471 | last_block = cur->start; | ||
472 | *last_ret = search_start; | ||
473 | btrfs_tree_unlock(cur); | ||
474 | free_extent_buffer(cur); | ||
475 | } | ||
476 | if (parent->map_token) { | ||
477 | unmap_extent_buffer(parent, parent->map_token, | ||
478 | KM_USER1); | ||
479 | parent->map_token = NULL; | ||
480 | } | ||
481 | return err; | ||
482 | } | ||
483 | |||
484 | /* | ||
485 | * The leaf data grows from end-to-front in the node. | ||
486 | * this returns the address of the start of the last item, | ||
487 | * which is the stop of the leaf data stack | ||
488 | */ | ||
489 | static inline unsigned int leaf_data_end(struct btrfs_root *root, | ||
490 | struct extent_buffer *leaf) | ||
491 | { | ||
492 | u32 nr = btrfs_header_nritems(leaf); | ||
493 | if (nr == 0) | ||
494 | return BTRFS_LEAF_DATA_SIZE(root); | ||
495 | return btrfs_item_offset_nr(leaf, nr - 1); | ||
496 | } | ||
497 | |||
498 | static int check_node(struct btrfs_root *root, struct btrfs_path *path, | ||
499 | int level) | ||
500 | { | ||
501 | struct extent_buffer *parent = NULL; | ||
502 | struct extent_buffer *node = path->nodes[level]; | ||
503 | struct btrfs_disk_key parent_key; | ||
504 | struct btrfs_disk_key node_key; | ||
505 | int parent_slot; | ||
506 | int slot; | ||
507 | struct btrfs_key cpukey; | ||
508 | u32 nritems = btrfs_header_nritems(node); | ||
509 | |||
510 | if (path->nodes[level + 1]) | ||
511 | parent = path->nodes[level + 1]; | ||
512 | |||
513 | slot = path->slots[level]; | ||
514 | BUG_ON(nritems == 0); | ||
515 | if (parent) { | ||
516 | parent_slot = path->slots[level + 1]; | ||
517 | btrfs_node_key(parent, &parent_key, parent_slot); | ||
518 | btrfs_node_key(node, &node_key, 0); | ||
519 | BUG_ON(memcmp(&parent_key, &node_key, | ||
520 | sizeof(struct btrfs_disk_key))); | ||
521 | BUG_ON(btrfs_node_blockptr(parent, parent_slot) != | ||
522 | btrfs_header_bytenr(node)); | ||
523 | } | ||
524 | BUG_ON(nritems > BTRFS_NODEPTRS_PER_BLOCK(root)); | ||
525 | if (slot != 0) { | ||
526 | btrfs_node_key_to_cpu(node, &cpukey, slot - 1); | ||
527 | btrfs_node_key(node, &node_key, slot); | ||
528 | BUG_ON(comp_keys(&node_key, &cpukey) <= 0); | ||
529 | } | ||
530 | if (slot < nritems - 1) { | ||
531 | btrfs_node_key_to_cpu(node, &cpukey, slot + 1); | ||
532 | btrfs_node_key(node, &node_key, slot); | ||
533 | BUG_ON(comp_keys(&node_key, &cpukey) >= 0); | ||
534 | } | ||
535 | return 0; | ||
536 | } | ||
537 | |||
538 | static int check_leaf(struct btrfs_root *root, struct btrfs_path *path, | ||
539 | int level) | ||
540 | { | ||
541 | struct extent_buffer *leaf = path->nodes[level]; | ||
542 | struct extent_buffer *parent = NULL; | ||
543 | int parent_slot; | ||
544 | struct btrfs_key cpukey; | ||
545 | struct btrfs_disk_key parent_key; | ||
546 | struct btrfs_disk_key leaf_key; | ||
547 | int slot = path->slots[0]; | ||
548 | |||
549 | u32 nritems = btrfs_header_nritems(leaf); | ||
550 | |||
551 | if (path->nodes[level + 1]) | ||
552 | parent = path->nodes[level + 1]; | ||
553 | |||
554 | if (nritems == 0) | ||
555 | return 0; | ||
556 | |||
557 | if (parent) { | ||
558 | parent_slot = path->slots[level + 1]; | ||
559 | btrfs_node_key(parent, &parent_key, parent_slot); | ||
560 | btrfs_item_key(leaf, &leaf_key, 0); | ||
561 | |||
562 | BUG_ON(memcmp(&parent_key, &leaf_key, | ||
563 | sizeof(struct btrfs_disk_key))); | ||
564 | BUG_ON(btrfs_node_blockptr(parent, parent_slot) != | ||
565 | btrfs_header_bytenr(leaf)); | ||
566 | } | ||
567 | #if 0 | ||
568 | for (i = 0; nritems > 1 && i < nritems - 2; i++) { | ||
569 | btrfs_item_key_to_cpu(leaf, &cpukey, i + 1); | ||
570 | btrfs_item_key(leaf, &leaf_key, i); | ||
571 | if (comp_keys(&leaf_key, &cpukey) >= 0) { | ||
572 | btrfs_print_leaf(root, leaf); | ||
573 | printk("slot %d offset bad key\n", i); | ||
574 | BUG_ON(1); | ||
575 | } | ||
576 | if (btrfs_item_offset_nr(leaf, i) != | ||
577 | btrfs_item_end_nr(leaf, i + 1)) { | ||
578 | btrfs_print_leaf(root, leaf); | ||
579 | printk("slot %d offset bad\n", i); | ||
580 | BUG_ON(1); | ||
581 | } | ||
582 | if (i == 0) { | ||
583 | if (btrfs_item_offset_nr(leaf, i) + | ||
584 | btrfs_item_size_nr(leaf, i) != | ||
585 | BTRFS_LEAF_DATA_SIZE(root)) { | ||
586 | btrfs_print_leaf(root, leaf); | ||
587 | printk("slot %d first offset bad\n", i); | ||
588 | BUG_ON(1); | ||
589 | } | ||
590 | } | ||
591 | } | ||
592 | if (nritems > 0) { | ||
593 | if (btrfs_item_size_nr(leaf, nritems - 1) > 4096) { | ||
594 | btrfs_print_leaf(root, leaf); | ||
595 | printk("slot %d bad size \n", nritems - 1); | ||
596 | BUG_ON(1); | ||
597 | } | ||
598 | } | ||
599 | #endif | ||
600 | if (slot != 0 && slot < nritems - 1) { | ||
601 | btrfs_item_key(leaf, &leaf_key, slot); | ||
602 | btrfs_item_key_to_cpu(leaf, &cpukey, slot - 1); | ||
603 | if (comp_keys(&leaf_key, &cpukey) <= 0) { | ||
604 | btrfs_print_leaf(root, leaf); | ||
605 | printk("slot %d offset bad key\n", slot); | ||
606 | BUG_ON(1); | ||
607 | } | ||
608 | if (btrfs_item_offset_nr(leaf, slot - 1) != | ||
609 | btrfs_item_end_nr(leaf, slot)) { | ||
610 | btrfs_print_leaf(root, leaf); | ||
611 | printk("slot %d offset bad\n", slot); | ||
612 | BUG_ON(1); | ||
613 | } | ||
614 | } | ||
615 | if (slot < nritems - 1) { | ||
616 | btrfs_item_key(leaf, &leaf_key, slot); | ||
617 | btrfs_item_key_to_cpu(leaf, &cpukey, slot + 1); | ||
618 | BUG_ON(comp_keys(&leaf_key, &cpukey) >= 0); | ||
619 | if (btrfs_item_offset_nr(leaf, slot) != | ||
620 | btrfs_item_end_nr(leaf, slot + 1)) { | ||
621 | btrfs_print_leaf(root, leaf); | ||
622 | printk("slot %d offset bad\n", slot); | ||
623 | BUG_ON(1); | ||
624 | } | ||
625 | } | ||
626 | BUG_ON(btrfs_item_offset_nr(leaf, 0) + | ||
627 | btrfs_item_size_nr(leaf, 0) != BTRFS_LEAF_DATA_SIZE(root)); | ||
628 | return 0; | ||
629 | } | ||
630 | |||
631 | static int noinline check_block(struct btrfs_root *root, | ||
632 | struct btrfs_path *path, int level) | ||
633 | { | ||
634 | u64 found_start; | ||
635 | return 0; | ||
636 | if (btrfs_header_level(path->nodes[level]) != level) | ||
637 | printk("warning: bad level %Lu wanted %d found %d\n", | ||
638 | path->nodes[level]->start, level, | ||
639 | btrfs_header_level(path->nodes[level])); | ||
640 | found_start = btrfs_header_bytenr(path->nodes[level]); | ||
641 | if (found_start != path->nodes[level]->start) { | ||
642 | printk("warning: bad bytentr %Lu found %Lu\n", | ||
643 | path->nodes[level]->start, found_start); | ||
644 | } | ||
645 | #if 0 | ||
646 | struct extent_buffer *buf = path->nodes[level]; | ||
647 | |||
648 | if (memcmp_extent_buffer(buf, root->fs_info->fsid, | ||
649 | (unsigned long)btrfs_header_fsid(buf), | ||
650 | BTRFS_FSID_SIZE)) { | ||
651 | printk("warning bad block %Lu\n", buf->start); | ||
652 | return 1; | ||
653 | } | ||
654 | #endif | ||
655 | if (level == 0) | ||
656 | return check_leaf(root, path, level); | ||
657 | return check_node(root, path, level); | ||
658 | } | ||
659 | |||
660 | /* | ||
661 | * search for key in the extent_buffer. The items start at offset p, | ||
662 | * and they are item_size apart. There are 'max' items in p. | ||
663 | * | ||
664 | * the slot in the array is returned via slot, and it points to | ||
665 | * the place where you would insert key if it is not found in | ||
666 | * the array. | ||
667 | * | ||
668 | * slot may point to max if the key is bigger than all of the keys | ||
669 | */ | ||
670 | static noinline int generic_bin_search(struct extent_buffer *eb, | ||
671 | unsigned long p, | ||
672 | int item_size, struct btrfs_key *key, | ||
673 | int max, int *slot) | ||
674 | { | ||
675 | int low = 0; | ||
676 | int high = max; | ||
677 | int mid; | ||
678 | int ret; | ||
679 | struct btrfs_disk_key *tmp = NULL; | ||
680 | struct btrfs_disk_key unaligned; | ||
681 | unsigned long offset; | ||
682 | char *map_token = NULL; | ||
683 | char *kaddr = NULL; | ||
684 | unsigned long map_start = 0; | ||
685 | unsigned long map_len = 0; | ||
686 | int err; | ||
687 | |||
688 | while(low < high) { | ||
689 | mid = (low + high) / 2; | ||
690 | offset = p + mid * item_size; | ||
691 | |||
692 | if (!map_token || offset < map_start || | ||
693 | (offset + sizeof(struct btrfs_disk_key)) > | ||
694 | map_start + map_len) { | ||
695 | if (map_token) { | ||
696 | unmap_extent_buffer(eb, map_token, KM_USER0); | ||
697 | map_token = NULL; | ||
698 | } | ||
699 | err = map_extent_buffer(eb, offset, | ||
700 | sizeof(struct btrfs_disk_key), | ||
701 | &map_token, &kaddr, | ||
702 | &map_start, &map_len, KM_USER0); | ||
703 | |||
704 | if (!err) { | ||
705 | tmp = (struct btrfs_disk_key *)(kaddr + offset - | ||
706 | map_start); | ||
707 | } else { | ||
708 | read_extent_buffer(eb, &unaligned, | ||
709 | offset, sizeof(unaligned)); | ||
710 | tmp = &unaligned; | ||
711 | } | ||
712 | |||
713 | } else { | ||
714 | tmp = (struct btrfs_disk_key *)(kaddr + offset - | ||
715 | map_start); | ||
716 | } | ||
717 | ret = comp_keys(tmp, key); | ||
718 | |||
719 | if (ret < 0) | ||
720 | low = mid + 1; | ||
721 | else if (ret > 0) | ||
722 | high = mid; | ||
723 | else { | ||
724 | *slot = mid; | ||
725 | if (map_token) | ||
726 | unmap_extent_buffer(eb, map_token, KM_USER0); | ||
727 | return 0; | ||
728 | } | ||
729 | } | ||
730 | *slot = low; | ||
731 | if (map_token) | ||
732 | unmap_extent_buffer(eb, map_token, KM_USER0); | ||
733 | return 1; | ||
734 | } | ||
735 | |||
736 | /* | ||
737 | * simple bin_search frontend that does the right thing for | ||
738 | * leaves vs nodes | ||
739 | */ | ||
740 | static int bin_search(struct extent_buffer *eb, struct btrfs_key *key, | ||
741 | int level, int *slot) | ||
742 | { | ||
743 | if (level == 0) { | ||
744 | return generic_bin_search(eb, | ||
745 | offsetof(struct btrfs_leaf, items), | ||
746 | sizeof(struct btrfs_item), | ||
747 | key, btrfs_header_nritems(eb), | ||
748 | slot); | ||
749 | } else { | ||
750 | return generic_bin_search(eb, | ||
751 | offsetof(struct btrfs_node, ptrs), | ||
752 | sizeof(struct btrfs_key_ptr), | ||
753 | key, btrfs_header_nritems(eb), | ||
754 | slot); | ||
755 | } | ||
756 | return -1; | ||
757 | } | ||
758 | |||
759 | static noinline struct extent_buffer *read_node_slot(struct btrfs_root *root, | ||
760 | struct extent_buffer *parent, int slot) | ||
761 | { | ||
762 | int level = btrfs_header_level(parent); | ||
763 | if (slot < 0) | ||
764 | return NULL; | ||
765 | if (slot >= btrfs_header_nritems(parent)) | ||
766 | return NULL; | ||
767 | |||
768 | BUG_ON(level == 0); | ||
769 | |||
770 | return read_tree_block(root, btrfs_node_blockptr(parent, slot), | ||
771 | btrfs_level_size(root, level - 1), | ||
772 | btrfs_node_ptr_generation(parent, slot)); | ||
773 | } | ||
774 | |||
775 | static noinline int balance_level(struct btrfs_trans_handle *trans, | ||
776 | struct btrfs_root *root, | ||
777 | struct btrfs_path *path, int level) | ||
778 | { | ||
779 | struct extent_buffer *right = NULL; | ||
780 | struct extent_buffer *mid; | ||
781 | struct extent_buffer *left = NULL; | ||
782 | struct extent_buffer *parent = NULL; | ||
783 | int ret = 0; | ||
784 | int wret; | ||
785 | int pslot; | ||
786 | int orig_slot = path->slots[level]; | ||
787 | int err_on_enospc = 0; | ||
788 | u64 orig_ptr; | ||
789 | |||
790 | if (level == 0) | ||
791 | return 0; | ||
792 | |||
793 | mid = path->nodes[level]; | ||
794 | WARN_ON(!path->locks[level]); | ||
795 | WARN_ON(btrfs_header_generation(mid) != trans->transid); | ||
796 | |||
797 | orig_ptr = btrfs_node_blockptr(mid, orig_slot); | ||
798 | |||
799 | if (level < BTRFS_MAX_LEVEL - 1) | ||
800 | parent = path->nodes[level + 1]; | ||
801 | pslot = path->slots[level + 1]; | ||
802 | |||
803 | /* | ||
804 | * deal with the case where there is only one pointer in the root | ||
805 | * by promoting the node below to a root | ||
806 | */ | ||
807 | if (!parent) { | ||
808 | struct extent_buffer *child; | ||
809 | |||
810 | if (btrfs_header_nritems(mid) != 1) | ||
811 | return 0; | ||
812 | |||
813 | /* promote the child to a root */ | ||
814 | child = read_node_slot(root, mid, 0); | ||
815 | btrfs_tree_lock(child); | ||
816 | BUG_ON(!child); | ||
817 | ret = btrfs_cow_block(trans, root, child, mid, 0, &child, 0); | ||
818 | BUG_ON(ret); | ||
819 | |||
820 | spin_lock(&root->node_lock); | ||
821 | root->node = child; | ||
822 | spin_unlock(&root->node_lock); | ||
823 | |||
824 | ret = btrfs_update_extent_ref(trans, root, child->start, | ||
825 | mid->start, child->start, | ||
826 | root->root_key.objectid, | ||
827 | trans->transid, level - 1, 0); | ||
828 | BUG_ON(ret); | ||
829 | |||
830 | add_root_to_dirty_list(root); | ||
831 | btrfs_tree_unlock(child); | ||
832 | path->locks[level] = 0; | ||
833 | path->nodes[level] = NULL; | ||
834 | clean_tree_block(trans, root, mid); | ||
835 | btrfs_tree_unlock(mid); | ||
836 | /* once for the path */ | ||
837 | free_extent_buffer(mid); | ||
838 | ret = btrfs_free_extent(trans, root, mid->start, mid->len, | ||
839 | mid->start, root->root_key.objectid, | ||
840 | btrfs_header_generation(mid), 0, 0, 1); | ||
841 | /* once for the root ptr */ | ||
842 | free_extent_buffer(mid); | ||
843 | return ret; | ||
844 | } | ||
845 | if (btrfs_header_nritems(mid) > | ||
846 | BTRFS_NODEPTRS_PER_BLOCK(root) / 4) | ||
847 | return 0; | ||
848 | |||
849 | if (btrfs_header_nritems(mid) < 2) | ||
850 | err_on_enospc = 1; | ||
851 | |||
852 | left = read_node_slot(root, parent, pslot - 1); | ||
853 | if (left) { | ||
854 | btrfs_tree_lock(left); | ||
855 | wret = btrfs_cow_block(trans, root, left, | ||
856 | parent, pslot - 1, &left, 0); | ||
857 | if (wret) { | ||
858 | ret = wret; | ||
859 | goto enospc; | ||
860 | } | ||
861 | } | ||
862 | right = read_node_slot(root, parent, pslot + 1); | ||
863 | if (right) { | ||
864 | btrfs_tree_lock(right); | ||
865 | wret = btrfs_cow_block(trans, root, right, | ||
866 | parent, pslot + 1, &right, 0); | ||
867 | if (wret) { | ||
868 | ret = wret; | ||
869 | goto enospc; | ||
870 | } | ||
871 | } | ||
872 | |||
873 | /* first, try to make some room in the middle buffer */ | ||
874 | if (left) { | ||
875 | orig_slot += btrfs_header_nritems(left); | ||
876 | wret = push_node_left(trans, root, left, mid, 1); | ||
877 | if (wret < 0) | ||
878 | ret = wret; | ||
879 | if (btrfs_header_nritems(mid) < 2) | ||
880 | err_on_enospc = 1; | ||
881 | } | ||
882 | |||
883 | /* | ||
884 | * then try to empty the right most buffer into the middle | ||
885 | */ | ||
886 | if (right) { | ||
887 | wret = push_node_left(trans, root, mid, right, 1); | ||
888 | if (wret < 0 && wret != -ENOSPC) | ||
889 | ret = wret; | ||
890 | if (btrfs_header_nritems(right) == 0) { | ||
891 | u64 bytenr = right->start; | ||
892 | u64 generation = btrfs_header_generation(parent); | ||
893 | u32 blocksize = right->len; | ||
894 | |||
895 | clean_tree_block(trans, root, right); | ||
896 | btrfs_tree_unlock(right); | ||
897 | free_extent_buffer(right); | ||
898 | right = NULL; | ||
899 | wret = del_ptr(trans, root, path, level + 1, pslot + | ||
900 | 1); | ||
901 | if (wret) | ||
902 | ret = wret; | ||
903 | wret = btrfs_free_extent(trans, root, bytenr, | ||
904 | blocksize, parent->start, | ||
905 | btrfs_header_owner(parent), | ||
906 | generation, 0, 0, 1); | ||
907 | if (wret) | ||
908 | ret = wret; | ||
909 | } else { | ||
910 | struct btrfs_disk_key right_key; | ||
911 | btrfs_node_key(right, &right_key, 0); | ||
912 | btrfs_set_node_key(parent, &right_key, pslot + 1); | ||
913 | btrfs_mark_buffer_dirty(parent); | ||
914 | } | ||
915 | } | ||
916 | if (btrfs_header_nritems(mid) == 1) { | ||
917 | /* | ||
918 | * we're not allowed to leave a node with one item in the | ||
919 | * tree during a delete. A deletion from lower in the tree | ||
920 | * could try to delete the only pointer in this node. | ||
921 | * So, pull some keys from the left. | ||
922 | * There has to be a left pointer at this point because | ||
923 | * otherwise we would have pulled some pointers from the | ||
924 | * right | ||
925 | */ | ||
926 | BUG_ON(!left); | ||
927 | wret = balance_node_right(trans, root, mid, left); | ||
928 | if (wret < 0) { | ||
929 | ret = wret; | ||
930 | goto enospc; | ||
931 | } | ||
932 | if (wret == 1) { | ||
933 | wret = push_node_left(trans, root, left, mid, 1); | ||
934 | if (wret < 0) | ||
935 | ret = wret; | ||
936 | } | ||
937 | BUG_ON(wret == 1); | ||
938 | } | ||
939 | if (btrfs_header_nritems(mid) == 0) { | ||
940 | /* we've managed to empty the middle node, drop it */ | ||
941 | u64 root_gen = btrfs_header_generation(parent); | ||
942 | u64 bytenr = mid->start; | ||
943 | u32 blocksize = mid->len; | ||
944 | |||
945 | clean_tree_block(trans, root, mid); | ||
946 | btrfs_tree_unlock(mid); | ||
947 | free_extent_buffer(mid); | ||
948 | mid = NULL; | ||
949 | wret = del_ptr(trans, root, path, level + 1, pslot); | ||
950 | if (wret) | ||
951 | ret = wret; | ||
952 | wret = btrfs_free_extent(trans, root, bytenr, blocksize, | ||
953 | parent->start, | ||
954 | btrfs_header_owner(parent), | ||
955 | root_gen, 0, 0, 1); | ||
956 | if (wret) | ||
957 | ret = wret; | ||
958 | } else { | ||
959 | /* update the parent key to reflect our changes */ | ||
960 | struct btrfs_disk_key mid_key; | ||
961 | btrfs_node_key(mid, &mid_key, 0); | ||
962 | btrfs_set_node_key(parent, &mid_key, pslot); | ||
963 | btrfs_mark_buffer_dirty(parent); | ||
964 | } | ||
965 | |||
966 | /* update the path */ | ||
967 | if (left) { | ||
968 | if (btrfs_header_nritems(left) > orig_slot) { | ||
969 | extent_buffer_get(left); | ||
970 | /* left was locked after cow */ | ||
971 | path->nodes[level] = left; | ||
972 | path->slots[level + 1] -= 1; | ||
973 | path->slots[level] = orig_slot; | ||
974 | if (mid) { | ||
975 | btrfs_tree_unlock(mid); | ||
976 | free_extent_buffer(mid); | ||
977 | } | ||
978 | } else { | ||
979 | orig_slot -= btrfs_header_nritems(left); | ||
980 | path->slots[level] = orig_slot; | ||
981 | } | ||
982 | } | ||
983 | /* double check we haven't messed things up */ | ||
984 | check_block(root, path, level); | ||
985 | if (orig_ptr != | ||
986 | btrfs_node_blockptr(path->nodes[level], path->slots[level])) | ||
987 | BUG(); | ||
988 | enospc: | ||
989 | if (right) { | ||
990 | btrfs_tree_unlock(right); | ||
991 | free_extent_buffer(right); | ||
992 | } | ||
993 | if (left) { | ||
994 | if (path->nodes[level] != left) | ||
995 | btrfs_tree_unlock(left); | ||
996 | free_extent_buffer(left); | ||
997 | } | ||
998 | return ret; | ||
999 | } | ||
1000 | |||
1001 | /* returns zero if the push worked, non-zero otherwise */ | ||
1002 | static int noinline push_nodes_for_insert(struct btrfs_trans_handle *trans, | ||
1003 | struct btrfs_root *root, | ||
1004 | struct btrfs_path *path, int level) | ||
1005 | { | ||
1006 | struct extent_buffer *right = NULL; | ||
1007 | struct extent_buffer *mid; | ||
1008 | struct extent_buffer *left = NULL; | ||
1009 | struct extent_buffer *parent = NULL; | ||
1010 | int ret = 0; | ||
1011 | int wret; | ||
1012 | int pslot; | ||
1013 | int orig_slot = path->slots[level]; | ||
1014 | u64 orig_ptr; | ||
1015 | |||
1016 | if (level == 0) | ||
1017 | return 1; | ||
1018 | |||
1019 | mid = path->nodes[level]; | ||
1020 | WARN_ON(btrfs_header_generation(mid) != trans->transid); | ||
1021 | orig_ptr = btrfs_node_blockptr(mid, orig_slot); | ||
1022 | |||
1023 | if (level < BTRFS_MAX_LEVEL - 1) | ||
1024 | parent = path->nodes[level + 1]; | ||
1025 | pslot = path->slots[level + 1]; | ||
1026 | |||
1027 | if (!parent) | ||
1028 | return 1; | ||
1029 | |||
1030 | left = read_node_slot(root, parent, pslot - 1); | ||
1031 | |||
1032 | /* first, try to make some room in the middle buffer */ | ||
1033 | if (left) { | ||
1034 | u32 left_nr; | ||
1035 | |||
1036 | btrfs_tree_lock(left); | ||
1037 | left_nr = btrfs_header_nritems(left); | ||
1038 | if (left_nr >= BTRFS_NODEPTRS_PER_BLOCK(root) - 1) { | ||
1039 | wret = 1; | ||
1040 | } else { | ||
1041 | ret = btrfs_cow_block(trans, root, left, parent, | ||
1042 | pslot - 1, &left, 0); | ||
1043 | if (ret) | ||
1044 | wret = 1; | ||
1045 | else { | ||
1046 | wret = push_node_left(trans, root, | ||
1047 | left, mid, 0); | ||
1048 | } | ||
1049 | } | ||
1050 | if (wret < 0) | ||
1051 | ret = wret; | ||
1052 | if (wret == 0) { | ||
1053 | struct btrfs_disk_key disk_key; | ||
1054 | orig_slot += left_nr; | ||
1055 | btrfs_node_key(mid, &disk_key, 0); | ||
1056 | btrfs_set_node_key(parent, &disk_key, pslot); | ||
1057 | btrfs_mark_buffer_dirty(parent); | ||
1058 | if (btrfs_header_nritems(left) > orig_slot) { | ||
1059 | path->nodes[level] = left; | ||
1060 | path->slots[level + 1] -= 1; | ||
1061 | path->slots[level] = orig_slot; | ||
1062 | btrfs_tree_unlock(mid); | ||
1063 | free_extent_buffer(mid); | ||
1064 | } else { | ||
1065 | orig_slot -= | ||
1066 | btrfs_header_nritems(left); | ||
1067 | path->slots[level] = orig_slot; | ||
1068 | btrfs_tree_unlock(left); | ||
1069 | free_extent_buffer(left); | ||
1070 | } | ||
1071 | return 0; | ||
1072 | } | ||
1073 | btrfs_tree_unlock(left); | ||
1074 | free_extent_buffer(left); | ||
1075 | } | ||
1076 | right = read_node_slot(root, parent, pslot + 1); | ||
1077 | |||
1078 | /* | ||
1079 | * then try to empty the right most buffer into the middle | ||
1080 | */ | ||
1081 | if (right) { | ||
1082 | u32 right_nr; | ||
1083 | btrfs_tree_lock(right); | ||
1084 | right_nr = btrfs_header_nritems(right); | ||
1085 | if (right_nr >= BTRFS_NODEPTRS_PER_BLOCK(root) - 1) { | ||
1086 | wret = 1; | ||
1087 | } else { | ||
1088 | ret = btrfs_cow_block(trans, root, right, | ||
1089 | parent, pslot + 1, | ||
1090 | &right, 0); | ||
1091 | if (ret) | ||
1092 | wret = 1; | ||
1093 | else { | ||
1094 | wret = balance_node_right(trans, root, | ||
1095 | right, mid); | ||
1096 | } | ||
1097 | } | ||
1098 | if (wret < 0) | ||
1099 | ret = wret; | ||
1100 | if (wret == 0) { | ||
1101 | struct btrfs_disk_key disk_key; | ||
1102 | |||
1103 | btrfs_node_key(right, &disk_key, 0); | ||
1104 | btrfs_set_node_key(parent, &disk_key, pslot + 1); | ||
1105 | btrfs_mark_buffer_dirty(parent); | ||
1106 | |||
1107 | if (btrfs_header_nritems(mid) <= orig_slot) { | ||
1108 | path->nodes[level] = right; | ||
1109 | path->slots[level + 1] += 1; | ||
1110 | path->slots[level] = orig_slot - | ||
1111 | btrfs_header_nritems(mid); | ||
1112 | btrfs_tree_unlock(mid); | ||
1113 | free_extent_buffer(mid); | ||
1114 | } else { | ||
1115 | btrfs_tree_unlock(right); | ||
1116 | free_extent_buffer(right); | ||
1117 | } | ||
1118 | return 0; | ||
1119 | } | ||
1120 | btrfs_tree_unlock(right); | ||
1121 | free_extent_buffer(right); | ||
1122 | } | ||
1123 | return 1; | ||
1124 | } | ||
1125 | |||
1126 | /* | ||
1127 | * readahead one full node of leaves | ||
1128 | */ | ||
1129 | static noinline void reada_for_search(struct btrfs_root *root, | ||
1130 | struct btrfs_path *path, | ||
1131 | int level, int slot, u64 objectid) | ||
1132 | { | ||
1133 | struct extent_buffer *node; | ||
1134 | struct btrfs_disk_key disk_key; | ||
1135 | u32 nritems; | ||
1136 | u64 search; | ||
1137 | u64 lowest_read; | ||
1138 | u64 highest_read; | ||
1139 | u64 nread = 0; | ||
1140 | int direction = path->reada; | ||
1141 | struct extent_buffer *eb; | ||
1142 | u32 nr; | ||
1143 | u32 blocksize; | ||
1144 | u32 nscan = 0; | ||
1145 | |||
1146 | if (level != 1) | ||
1147 | return; | ||
1148 | |||
1149 | if (!path->nodes[level]) | ||
1150 | return; | ||
1151 | |||
1152 | node = path->nodes[level]; | ||
1153 | |||
1154 | search = btrfs_node_blockptr(node, slot); | ||
1155 | blocksize = btrfs_level_size(root, level - 1); | ||
1156 | eb = btrfs_find_tree_block(root, search, blocksize); | ||
1157 | if (eb) { | ||
1158 | free_extent_buffer(eb); | ||
1159 | return; | ||
1160 | } | ||
1161 | |||
1162 | highest_read = search; | ||
1163 | lowest_read = search; | ||
1164 | |||
1165 | nritems = btrfs_header_nritems(node); | ||
1166 | nr = slot; | ||
1167 | while(1) { | ||
1168 | if (direction < 0) { | ||
1169 | if (nr == 0) | ||
1170 | break; | ||
1171 | nr--; | ||
1172 | } else if (direction > 0) { | ||
1173 | nr++; | ||
1174 | if (nr >= nritems) | ||
1175 | break; | ||
1176 | } | ||
1177 | if (path->reada < 0 && objectid) { | ||
1178 | btrfs_node_key(node, &disk_key, nr); | ||
1179 | if (btrfs_disk_key_objectid(&disk_key) != objectid) | ||
1180 | break; | ||
1181 | } | ||
1182 | search = btrfs_node_blockptr(node, nr); | ||
1183 | if ((search >= lowest_read && search <= highest_read) || | ||
1184 | (search < lowest_read && lowest_read - search <= 32768) || | ||
1185 | (search > highest_read && search - highest_read <= 32768)) { | ||
1186 | readahead_tree_block(root, search, blocksize, | ||
1187 | btrfs_node_ptr_generation(node, nr)); | ||
1188 | nread += blocksize; | ||
1189 | } | ||
1190 | nscan++; | ||
1191 | if (path->reada < 2 && (nread > (256 * 1024) || nscan > 32)) | ||
1192 | break; | ||
1193 | if(nread > (1024 * 1024) || nscan > 128) | ||
1194 | break; | ||
1195 | |||
1196 | if (search < lowest_read) | ||
1197 | lowest_read = search; | ||
1198 | if (search > highest_read) | ||
1199 | highest_read = search; | ||
1200 | } | ||
1201 | } | ||
1202 | |||
1203 | static noinline void unlock_up(struct btrfs_path *path, int level, | ||
1204 | int lowest_unlock) | ||
1205 | { | ||
1206 | int i; | ||
1207 | int skip_level = level; | ||
1208 | int no_skips = 0; | ||
1209 | struct extent_buffer *t; | ||
1210 | |||
1211 | for (i = level; i < BTRFS_MAX_LEVEL; i++) { | ||
1212 | if (!path->nodes[i]) | ||
1213 | break; | ||
1214 | if (!path->locks[i]) | ||
1215 | break; | ||
1216 | if (!no_skips && path->slots[i] == 0) { | ||
1217 | skip_level = i + 1; | ||
1218 | continue; | ||
1219 | } | ||
1220 | if (!no_skips && path->keep_locks) { | ||
1221 | u32 nritems; | ||
1222 | t = path->nodes[i]; | ||
1223 | nritems = btrfs_header_nritems(t); | ||
1224 | if (nritems < 1 || path->slots[i] >= nritems - 1) { | ||
1225 | skip_level = i + 1; | ||
1226 | continue; | ||
1227 | } | ||
1228 | } | ||
1229 | if (skip_level < i && i >= lowest_unlock) | ||
1230 | no_skips = 1; | ||
1231 | |||
1232 | t = path->nodes[i]; | ||
1233 | if (i >= lowest_unlock && i > skip_level && path->locks[i]) { | ||
1234 | btrfs_tree_unlock(t); | ||
1235 | path->locks[i] = 0; | ||
1236 | } | ||
1237 | } | ||
1238 | } | ||
1239 | |||
1240 | /* | ||
1241 | * look for key in the tree. path is filled in with nodes along the way | ||
1242 | * if key is found, we return zero and you can find the item in the leaf | ||
1243 | * level of the path (level 0) | ||
1244 | * | ||
1245 | * If the key isn't found, the path points to the slot where it should | ||
1246 | * be inserted, and 1 is returned. If there are other errors during the | ||
1247 | * search a negative error number is returned. | ||
1248 | * | ||
1249 | * if ins_len > 0, nodes and leaves will be split as we walk down the | ||
1250 | * tree. if ins_len < 0, nodes will be merged as we walk down the tree (if | ||
1251 | * possible) | ||
1252 | */ | ||
1253 | int btrfs_search_slot(struct btrfs_trans_handle *trans, struct btrfs_root | ||
1254 | *root, struct btrfs_key *key, struct btrfs_path *p, int | ||
1255 | ins_len, int cow) | ||
1256 | { | ||
1257 | struct extent_buffer *b; | ||
1258 | struct extent_buffer *tmp; | ||
1259 | int slot; | ||
1260 | int ret; | ||
1261 | int level; | ||
1262 | int should_reada = p->reada; | ||
1263 | int lowest_unlock = 1; | ||
1264 | int blocksize; | ||
1265 | u8 lowest_level = 0; | ||
1266 | u64 blocknr; | ||
1267 | u64 gen; | ||
1268 | struct btrfs_key prealloc_block; | ||
1269 | |||
1270 | lowest_level = p->lowest_level; | ||
1271 | WARN_ON(lowest_level && ins_len); | ||
1272 | WARN_ON(p->nodes[0] != NULL); | ||
1273 | WARN_ON(cow && root == root->fs_info->extent_root && | ||
1274 | !mutex_is_locked(&root->fs_info->alloc_mutex)); | ||
1275 | if (ins_len < 0) | ||
1276 | lowest_unlock = 2; | ||
1277 | |||
1278 | prealloc_block.objectid = 0; | ||
1279 | |||
1280 | again: | ||
1281 | if (p->skip_locking) | ||
1282 | b = btrfs_root_node(root); | ||
1283 | else | ||
1284 | b = btrfs_lock_root_node(root); | ||
1285 | |||
1286 | while (b) { | ||
1287 | level = btrfs_header_level(b); | ||
1288 | |||
1289 | /* | ||
1290 | * setup the path here so we can release it under lock | ||
1291 | * contention with the cow code | ||
1292 | */ | ||
1293 | p->nodes[level] = b; | ||
1294 | if (!p->skip_locking) | ||
1295 | p->locks[level] = 1; | ||
1296 | |||
1297 | if (cow) { | ||
1298 | int wret; | ||
1299 | |||
1300 | /* is a cow on this block not required */ | ||
1301 | spin_lock(&root->fs_info->hash_lock); | ||
1302 | if (btrfs_header_generation(b) == trans->transid && | ||
1303 | !btrfs_header_flag(b, BTRFS_HEADER_FLAG_WRITTEN)) { | ||
1304 | spin_unlock(&root->fs_info->hash_lock); | ||
1305 | goto cow_done; | ||
1306 | } | ||
1307 | spin_unlock(&root->fs_info->hash_lock); | ||
1308 | |||
1309 | /* ok, we have to cow, is our old prealloc the right | ||
1310 | * size? | ||
1311 | */ | ||
1312 | if (prealloc_block.objectid && | ||
1313 | prealloc_block.offset != b->len) { | ||
1314 | btrfs_free_reserved_extent(root, | ||
1315 | prealloc_block.objectid, | ||
1316 | prealloc_block.offset); | ||
1317 | prealloc_block.objectid = 0; | ||
1318 | } | ||
1319 | |||
1320 | /* | ||
1321 | * for higher level blocks, try not to allocate blocks | ||
1322 | * with the block and the parent locks held. | ||
1323 | */ | ||
1324 | if (level > 1 && !prealloc_block.objectid && | ||
1325 | btrfs_path_lock_waiting(p, level)) { | ||
1326 | u32 size = b->len; | ||
1327 | u64 hint = b->start; | ||
1328 | |||
1329 | btrfs_release_path(root, p); | ||
1330 | ret = btrfs_reserve_extent(trans, root, | ||
1331 | size, size, 0, | ||
1332 | hint, (u64)-1, | ||
1333 | &prealloc_block, 0); | ||
1334 | BUG_ON(ret); | ||
1335 | goto again; | ||
1336 | } | ||
1337 | |||
1338 | wret = btrfs_cow_block(trans, root, b, | ||
1339 | p->nodes[level + 1], | ||
1340 | p->slots[level + 1], | ||
1341 | &b, prealloc_block.objectid); | ||
1342 | prealloc_block.objectid = 0; | ||
1343 | if (wret) { | ||
1344 | free_extent_buffer(b); | ||
1345 | ret = wret; | ||
1346 | goto done; | ||
1347 | } | ||
1348 | } | ||
1349 | cow_done: | ||
1350 | BUG_ON(!cow && ins_len); | ||
1351 | if (level != btrfs_header_level(b)) | ||
1352 | WARN_ON(1); | ||
1353 | level = btrfs_header_level(b); | ||
1354 | |||
1355 | p->nodes[level] = b; | ||
1356 | if (!p->skip_locking) | ||
1357 | p->locks[level] = 1; | ||
1358 | |||
1359 | ret = check_block(root, p, level); | ||
1360 | if (ret) { | ||
1361 | ret = -1; | ||
1362 | goto done; | ||
1363 | } | ||
1364 | |||
1365 | ret = bin_search(b, key, level, &slot); | ||
1366 | if (level != 0) { | ||
1367 | if (ret && slot > 0) | ||
1368 | slot -= 1; | ||
1369 | p->slots[level] = slot; | ||
1370 | if (ins_len > 0 && btrfs_header_nritems(b) >= | ||
1371 | BTRFS_NODEPTRS_PER_BLOCK(root) - 3) { | ||
1372 | int sret = split_node(trans, root, p, level); | ||
1373 | BUG_ON(sret > 0); | ||
1374 | if (sret) { | ||
1375 | ret = sret; | ||
1376 | goto done; | ||
1377 | } | ||
1378 | b = p->nodes[level]; | ||
1379 | slot = p->slots[level]; | ||
1380 | } else if (ins_len < 0) { | ||
1381 | int sret = balance_level(trans, root, p, | ||
1382 | level); | ||
1383 | if (sret) { | ||
1384 | ret = sret; | ||
1385 | goto done; | ||
1386 | } | ||
1387 | b = p->nodes[level]; | ||
1388 | if (!b) { | ||
1389 | btrfs_release_path(NULL, p); | ||
1390 | goto again; | ||
1391 | } | ||
1392 | slot = p->slots[level]; | ||
1393 | BUG_ON(btrfs_header_nritems(b) == 1); | ||
1394 | } | ||
1395 | unlock_up(p, level, lowest_unlock); | ||
1396 | |||
1397 | /* this is only true while dropping a snapshot */ | ||
1398 | if (level == lowest_level) { | ||
1399 | break; | ||
1400 | } | ||
1401 | |||
1402 | blocknr = btrfs_node_blockptr(b, slot); | ||
1403 | gen = btrfs_node_ptr_generation(b, slot); | ||
1404 | blocksize = btrfs_level_size(root, level - 1); | ||
1405 | |||
1406 | tmp = btrfs_find_tree_block(root, blocknr, blocksize); | ||
1407 | if (tmp && btrfs_buffer_uptodate(tmp, gen)) { | ||
1408 | b = tmp; | ||
1409 | } else { | ||
1410 | /* | ||
1411 | * reduce lock contention at high levels | ||
1412 | * of the btree by dropping locks before | ||
1413 | * we read. | ||
1414 | */ | ||
1415 | if (level > 1) { | ||
1416 | btrfs_release_path(NULL, p); | ||
1417 | if (tmp) | ||
1418 | free_extent_buffer(tmp); | ||
1419 | if (should_reada) | ||
1420 | reada_for_search(root, p, | ||
1421 | level, slot, | ||
1422 | key->objectid); | ||
1423 | |||
1424 | tmp = read_tree_block(root, blocknr, | ||
1425 | blocksize, gen); | ||
1426 | if (tmp) | ||
1427 | free_extent_buffer(tmp); | ||
1428 | goto again; | ||
1429 | } else { | ||
1430 | if (tmp) | ||
1431 | free_extent_buffer(tmp); | ||
1432 | if (should_reada) | ||
1433 | reada_for_search(root, p, | ||
1434 | level, slot, | ||
1435 | key->objectid); | ||
1436 | b = read_node_slot(root, b, slot); | ||
1437 | } | ||
1438 | } | ||
1439 | if (!p->skip_locking) | ||
1440 | btrfs_tree_lock(b); | ||
1441 | } else { | ||
1442 | p->slots[level] = slot; | ||
1443 | if (ins_len > 0 && btrfs_leaf_free_space(root, b) < | ||
1444 | sizeof(struct btrfs_item) + ins_len) { | ||
1445 | int sret = split_leaf(trans, root, key, | ||
1446 | p, ins_len, ret == 0); | ||
1447 | BUG_ON(sret > 0); | ||
1448 | if (sret) { | ||
1449 | ret = sret; | ||
1450 | goto done; | ||
1451 | } | ||
1452 | } | ||
1453 | unlock_up(p, level, lowest_unlock); | ||
1454 | goto done; | ||
1455 | } | ||
1456 | } | ||
1457 | ret = 1; | ||
1458 | done: | ||
1459 | if (prealloc_block.objectid) { | ||
1460 | btrfs_free_reserved_extent(root, | ||
1461 | prealloc_block.objectid, | ||
1462 | prealloc_block.offset); | ||
1463 | } | ||
1464 | |||
1465 | return ret; | ||
1466 | } | ||
1467 | |||
1468 | /* | ||
1469 | * adjust the pointers going up the tree, starting at level | ||
1470 | * making sure the right key of each node is points to 'key'. | ||
1471 | * This is used after shifting pointers to the left, so it stops | ||
1472 | * fixing up pointers when a given leaf/node is not in slot 0 of the | ||
1473 | * higher levels | ||
1474 | * | ||
1475 | * If this fails to write a tree block, it returns -1, but continues | ||
1476 | * fixing up the blocks in ram so the tree is consistent. | ||
1477 | */ | ||
1478 | static int fixup_low_keys(struct btrfs_trans_handle *trans, | ||
1479 | struct btrfs_root *root, struct btrfs_path *path, | ||
1480 | struct btrfs_disk_key *key, int level) | ||
1481 | { | ||
1482 | int i; | ||
1483 | int ret = 0; | ||
1484 | struct extent_buffer *t; | ||
1485 | |||
1486 | for (i = level; i < BTRFS_MAX_LEVEL; i++) { | ||
1487 | int tslot = path->slots[i]; | ||
1488 | if (!path->nodes[i]) | ||
1489 | break; | ||
1490 | t = path->nodes[i]; | ||
1491 | btrfs_set_node_key(t, key, tslot); | ||
1492 | btrfs_mark_buffer_dirty(path->nodes[i]); | ||
1493 | if (tslot != 0) | ||
1494 | break; | ||
1495 | } | ||
1496 | return ret; | ||
1497 | } | ||
1498 | |||
1499 | /* | ||
1500 | * update item key. | ||
1501 | * | ||
1502 | * This function isn't completely safe. It's the caller's responsibility | ||
1503 | * that the new key won't break the order | ||
1504 | */ | ||
1505 | int btrfs_set_item_key_safe(struct btrfs_trans_handle *trans, | ||
1506 | struct btrfs_root *root, struct btrfs_path *path, | ||
1507 | struct btrfs_key *new_key) | ||
1508 | { | ||
1509 | struct btrfs_disk_key disk_key; | ||
1510 | struct extent_buffer *eb; | ||
1511 | int slot; | ||
1512 | |||
1513 | eb = path->nodes[0]; | ||
1514 | slot = path->slots[0]; | ||
1515 | if (slot > 0) { | ||
1516 | btrfs_item_key(eb, &disk_key, slot - 1); | ||
1517 | if (comp_keys(&disk_key, new_key) >= 0) | ||
1518 | return -1; | ||
1519 | } | ||
1520 | if (slot < btrfs_header_nritems(eb) - 1) { | ||
1521 | btrfs_item_key(eb, &disk_key, slot + 1); | ||
1522 | if (comp_keys(&disk_key, new_key) <= 0) | ||
1523 | return -1; | ||
1524 | } | ||
1525 | |||
1526 | btrfs_cpu_key_to_disk(&disk_key, new_key); | ||
1527 | btrfs_set_item_key(eb, &disk_key, slot); | ||
1528 | btrfs_mark_buffer_dirty(eb); | ||
1529 | if (slot == 0) | ||
1530 | fixup_low_keys(trans, root, path, &disk_key, 1); | ||
1531 | return 0; | ||
1532 | } | ||
1533 | |||
1534 | /* | ||
1535 | * try to push data from one node into the next node left in the | ||
1536 | * tree. | ||
1537 | * | ||
1538 | * returns 0 if some ptrs were pushed left, < 0 if there was some horrible | ||
1539 | * error, and > 0 if there was no room in the left hand block. | ||
1540 | */ | ||
1541 | static int push_node_left(struct btrfs_trans_handle *trans, | ||
1542 | struct btrfs_root *root, struct extent_buffer *dst, | ||
1543 | struct extent_buffer *src, int empty) | ||
1544 | { | ||
1545 | int push_items = 0; | ||
1546 | int src_nritems; | ||
1547 | int dst_nritems; | ||
1548 | int ret = 0; | ||
1549 | |||
1550 | src_nritems = btrfs_header_nritems(src); | ||
1551 | dst_nritems = btrfs_header_nritems(dst); | ||
1552 | push_items = BTRFS_NODEPTRS_PER_BLOCK(root) - dst_nritems; | ||
1553 | WARN_ON(btrfs_header_generation(src) != trans->transid); | ||
1554 | WARN_ON(btrfs_header_generation(dst) != trans->transid); | ||
1555 | |||
1556 | if (!empty && src_nritems <= 8) | ||
1557 | return 1; | ||
1558 | |||
1559 | if (push_items <= 0) { | ||
1560 | return 1; | ||
1561 | } | ||
1562 | |||
1563 | if (empty) { | ||
1564 | push_items = min(src_nritems, push_items); | ||
1565 | if (push_items < src_nritems) { | ||
1566 | /* leave at least 8 pointers in the node if | ||
1567 | * we aren't going to empty it | ||
1568 | */ | ||
1569 | if (src_nritems - push_items < 8) { | ||
1570 | if (push_items <= 8) | ||
1571 | return 1; | ||
1572 | push_items -= 8; | ||
1573 | } | ||
1574 | } | ||
1575 | } else | ||
1576 | push_items = min(src_nritems - 8, push_items); | ||
1577 | |||
1578 | copy_extent_buffer(dst, src, | ||
1579 | btrfs_node_key_ptr_offset(dst_nritems), | ||
1580 | btrfs_node_key_ptr_offset(0), | ||
1581 | push_items * sizeof(struct btrfs_key_ptr)); | ||
1582 | |||
1583 | if (push_items < src_nritems) { | ||
1584 | memmove_extent_buffer(src, btrfs_node_key_ptr_offset(0), | ||
1585 | btrfs_node_key_ptr_offset(push_items), | ||
1586 | (src_nritems - push_items) * | ||
1587 | sizeof(struct btrfs_key_ptr)); | ||
1588 | } | ||
1589 | btrfs_set_header_nritems(src, src_nritems - push_items); | ||
1590 | btrfs_set_header_nritems(dst, dst_nritems + push_items); | ||
1591 | btrfs_mark_buffer_dirty(src); | ||
1592 | btrfs_mark_buffer_dirty(dst); | ||
1593 | |||
1594 | ret = btrfs_update_ref(trans, root, src, dst, dst_nritems, push_items); | ||
1595 | BUG_ON(ret); | ||
1596 | |||
1597 | return ret; | ||
1598 | } | ||
1599 | |||
1600 | /* | ||
1601 | * try to push data from one node into the next node right in the | ||
1602 | * tree. | ||
1603 | * | ||
1604 | * returns 0 if some ptrs were pushed, < 0 if there was some horrible | ||
1605 | * error, and > 0 if there was no room in the right hand block. | ||
1606 | * | ||
1607 | * this will only push up to 1/2 the contents of the left node over | ||
1608 | */ | ||
1609 | static int balance_node_right(struct btrfs_trans_handle *trans, | ||
1610 | struct btrfs_root *root, | ||
1611 | struct extent_buffer *dst, | ||
1612 | struct extent_buffer *src) | ||
1613 | { | ||
1614 | int push_items = 0; | ||
1615 | int max_push; | ||
1616 | int src_nritems; | ||
1617 | int dst_nritems; | ||
1618 | int ret = 0; | ||
1619 | |||
1620 | WARN_ON(btrfs_header_generation(src) != trans->transid); | ||
1621 | WARN_ON(btrfs_header_generation(dst) != trans->transid); | ||
1622 | |||
1623 | src_nritems = btrfs_header_nritems(src); | ||
1624 | dst_nritems = btrfs_header_nritems(dst); | ||
1625 | push_items = BTRFS_NODEPTRS_PER_BLOCK(root) - dst_nritems; | ||
1626 | if (push_items <= 0) { | ||
1627 | return 1; | ||
1628 | } | ||
1629 | |||
1630 | if (src_nritems < 4) { | ||
1631 | return 1; | ||
1632 | } | ||
1633 | |||
1634 | max_push = src_nritems / 2 + 1; | ||
1635 | /* don't try to empty the node */ | ||
1636 | if (max_push >= src_nritems) { | ||
1637 | return 1; | ||
1638 | } | ||
1639 | |||
1640 | if (max_push < push_items) | ||
1641 | push_items = max_push; | ||
1642 | |||
1643 | memmove_extent_buffer(dst, btrfs_node_key_ptr_offset(push_items), | ||
1644 | btrfs_node_key_ptr_offset(0), | ||
1645 | (dst_nritems) * | ||
1646 | sizeof(struct btrfs_key_ptr)); | ||
1647 | |||
1648 | copy_extent_buffer(dst, src, | ||
1649 | btrfs_node_key_ptr_offset(0), | ||
1650 | btrfs_node_key_ptr_offset(src_nritems - push_items), | ||
1651 | push_items * sizeof(struct btrfs_key_ptr)); | ||
1652 | |||
1653 | btrfs_set_header_nritems(src, src_nritems - push_items); | ||
1654 | btrfs_set_header_nritems(dst, dst_nritems + push_items); | ||
1655 | |||
1656 | btrfs_mark_buffer_dirty(src); | ||
1657 | btrfs_mark_buffer_dirty(dst); | ||
1658 | |||
1659 | ret = btrfs_update_ref(trans, root, src, dst, 0, push_items); | ||
1660 | BUG_ON(ret); | ||
1661 | |||
1662 | return ret; | ||
1663 | } | ||
1664 | |||
1665 | /* | ||
1666 | * helper function to insert a new root level in the tree. | ||
1667 | * A new node is allocated, and a single item is inserted to | ||
1668 | * point to the existing root | ||
1669 | * | ||
1670 | * returns zero on success or < 0 on failure. | ||
1671 | */ | ||
1672 | static int noinline insert_new_root(struct btrfs_trans_handle *trans, | ||
1673 | struct btrfs_root *root, | ||
1674 | struct btrfs_path *path, int level) | ||
1675 | { | ||
1676 | u64 lower_gen; | ||
1677 | struct extent_buffer *lower; | ||
1678 | struct extent_buffer *c; | ||
1679 | struct extent_buffer *old; | ||
1680 | struct btrfs_disk_key lower_key; | ||
1681 | int ret; | ||
1682 | |||
1683 | BUG_ON(path->nodes[level]); | ||
1684 | BUG_ON(path->nodes[level-1] != root->node); | ||
1685 | |||
1686 | lower = path->nodes[level-1]; | ||
1687 | if (level == 1) | ||
1688 | btrfs_item_key(lower, &lower_key, 0); | ||
1689 | else | ||
1690 | btrfs_node_key(lower, &lower_key, 0); | ||
1691 | |||
1692 | c = btrfs_alloc_free_block(trans, root, root->nodesize, 0, | ||
1693 | root->root_key.objectid, trans->transid, | ||
1694 | level, root->node->start, 0); | ||
1695 | if (IS_ERR(c)) | ||
1696 | return PTR_ERR(c); | ||
1697 | |||
1698 | memset_extent_buffer(c, 0, 0, root->nodesize); | ||
1699 | btrfs_set_header_nritems(c, 1); | ||
1700 | btrfs_set_header_level(c, level); | ||
1701 | btrfs_set_header_bytenr(c, c->start); | ||
1702 | btrfs_set_header_generation(c, trans->transid); | ||
1703 | btrfs_set_header_owner(c, root->root_key.objectid); | ||
1704 | |||
1705 | write_extent_buffer(c, root->fs_info->fsid, | ||
1706 | (unsigned long)btrfs_header_fsid(c), | ||
1707 | BTRFS_FSID_SIZE); | ||
1708 | |||
1709 | write_extent_buffer(c, root->fs_info->chunk_tree_uuid, | ||
1710 | (unsigned long)btrfs_header_chunk_tree_uuid(c), | ||
1711 | BTRFS_UUID_SIZE); | ||
1712 | |||
1713 | btrfs_set_node_key(c, &lower_key, 0); | ||
1714 | btrfs_set_node_blockptr(c, 0, lower->start); | ||
1715 | lower_gen = btrfs_header_generation(lower); | ||
1716 | WARN_ON(lower_gen != trans->transid); | ||
1717 | |||
1718 | btrfs_set_node_ptr_generation(c, 0, lower_gen); | ||
1719 | |||
1720 | btrfs_mark_buffer_dirty(c); | ||
1721 | |||
1722 | spin_lock(&root->node_lock); | ||
1723 | old = root->node; | ||
1724 | root->node = c; | ||
1725 | spin_unlock(&root->node_lock); | ||
1726 | |||
1727 | ret = btrfs_update_extent_ref(trans, root, lower->start, | ||
1728 | lower->start, c->start, | ||
1729 | root->root_key.objectid, | ||
1730 | trans->transid, level - 1, 0); | ||
1731 | BUG_ON(ret); | ||
1732 | |||
1733 | /* the super has an extra ref to root->node */ | ||
1734 | free_extent_buffer(old); | ||
1735 | |||
1736 | add_root_to_dirty_list(root); | ||
1737 | extent_buffer_get(c); | ||
1738 | path->nodes[level] = c; | ||
1739 | path->locks[level] = 1; | ||
1740 | path->slots[level] = 0; | ||
1741 | return 0; | ||
1742 | } | ||
1743 | |||
1744 | /* | ||
1745 | * worker function to insert a single pointer in a node. | ||
1746 | * the node should have enough room for the pointer already | ||
1747 | * | ||
1748 | * slot and level indicate where you want the key to go, and | ||
1749 | * blocknr is the block the key points to. | ||
1750 | * | ||
1751 | * returns zero on success and < 0 on any error | ||
1752 | */ | ||
1753 | static int insert_ptr(struct btrfs_trans_handle *trans, struct btrfs_root | ||
1754 | *root, struct btrfs_path *path, struct btrfs_disk_key | ||
1755 | *key, u64 bytenr, int slot, int level) | ||
1756 | { | ||
1757 | struct extent_buffer *lower; | ||
1758 | int nritems; | ||
1759 | |||
1760 | BUG_ON(!path->nodes[level]); | ||
1761 | lower = path->nodes[level]; | ||
1762 | nritems = btrfs_header_nritems(lower); | ||
1763 | if (slot > nritems) | ||
1764 | BUG(); | ||
1765 | if (nritems == BTRFS_NODEPTRS_PER_BLOCK(root)) | ||
1766 | BUG(); | ||
1767 | if (slot != nritems) { | ||
1768 | memmove_extent_buffer(lower, | ||
1769 | btrfs_node_key_ptr_offset(slot + 1), | ||
1770 | btrfs_node_key_ptr_offset(slot), | ||
1771 | (nritems - slot) * sizeof(struct btrfs_key_ptr)); | ||
1772 | } | ||
1773 | btrfs_set_node_key(lower, key, slot); | ||
1774 | btrfs_set_node_blockptr(lower, slot, bytenr); | ||
1775 | WARN_ON(trans->transid == 0); | ||
1776 | btrfs_set_node_ptr_generation(lower, slot, trans->transid); | ||
1777 | btrfs_set_header_nritems(lower, nritems + 1); | ||
1778 | btrfs_mark_buffer_dirty(lower); | ||
1779 | return 0; | ||
1780 | } | ||
1781 | |||
1782 | /* | ||
1783 | * split the node at the specified level in path in two. | ||
1784 | * The path is corrected to point to the appropriate node after the split | ||
1785 | * | ||
1786 | * Before splitting this tries to make some room in the node by pushing | ||
1787 | * left and right, if either one works, it returns right away. | ||
1788 | * | ||
1789 | * returns 0 on success and < 0 on failure | ||
1790 | */ | ||
1791 | static noinline int split_node(struct btrfs_trans_handle *trans, | ||
1792 | struct btrfs_root *root, | ||
1793 | struct btrfs_path *path, int level) | ||
1794 | { | ||
1795 | struct extent_buffer *c; | ||
1796 | struct extent_buffer *split; | ||
1797 | struct btrfs_disk_key disk_key; | ||
1798 | int mid; | ||
1799 | int ret; | ||
1800 | int wret; | ||
1801 | u32 c_nritems; | ||
1802 | |||
1803 | c = path->nodes[level]; | ||
1804 | WARN_ON(btrfs_header_generation(c) != trans->transid); | ||
1805 | if (c == root->node) { | ||
1806 | /* trying to split the root, lets make a new one */ | ||
1807 | ret = insert_new_root(trans, root, path, level + 1); | ||
1808 | if (ret) | ||
1809 | return ret; | ||
1810 | } else { | ||
1811 | ret = push_nodes_for_insert(trans, root, path, level); | ||
1812 | c = path->nodes[level]; | ||
1813 | if (!ret && btrfs_header_nritems(c) < | ||
1814 | BTRFS_NODEPTRS_PER_BLOCK(root) - 3) | ||
1815 | return 0; | ||
1816 | if (ret < 0) | ||
1817 | return ret; | ||
1818 | } | ||
1819 | |||
1820 | c_nritems = btrfs_header_nritems(c); | ||
1821 | |||
1822 | split = btrfs_alloc_free_block(trans, root, root->nodesize, | ||
1823 | path->nodes[level + 1]->start, | ||
1824 | root->root_key.objectid, | ||
1825 | trans->transid, level, c->start, 0); | ||
1826 | if (IS_ERR(split)) | ||
1827 | return PTR_ERR(split); | ||
1828 | |||
1829 | btrfs_set_header_flags(split, btrfs_header_flags(c)); | ||
1830 | btrfs_set_header_level(split, btrfs_header_level(c)); | ||
1831 | btrfs_set_header_bytenr(split, split->start); | ||
1832 | btrfs_set_header_generation(split, trans->transid); | ||
1833 | btrfs_set_header_owner(split, root->root_key.objectid); | ||
1834 | btrfs_set_header_flags(split, 0); | ||
1835 | write_extent_buffer(split, root->fs_info->fsid, | ||
1836 | (unsigned long)btrfs_header_fsid(split), | ||
1837 | BTRFS_FSID_SIZE); | ||
1838 | write_extent_buffer(split, root->fs_info->chunk_tree_uuid, | ||
1839 | (unsigned long)btrfs_header_chunk_tree_uuid(split), | ||
1840 | BTRFS_UUID_SIZE); | ||
1841 | |||
1842 | mid = (c_nritems + 1) / 2; | ||
1843 | |||
1844 | copy_extent_buffer(split, c, | ||
1845 | btrfs_node_key_ptr_offset(0), | ||
1846 | btrfs_node_key_ptr_offset(mid), | ||
1847 | (c_nritems - mid) * sizeof(struct btrfs_key_ptr)); | ||
1848 | btrfs_set_header_nritems(split, c_nritems - mid); | ||
1849 | btrfs_set_header_nritems(c, mid); | ||
1850 | ret = 0; | ||
1851 | |||
1852 | btrfs_mark_buffer_dirty(c); | ||
1853 | btrfs_mark_buffer_dirty(split); | ||
1854 | |||
1855 | btrfs_node_key(split, &disk_key, 0); | ||
1856 | wret = insert_ptr(trans, root, path, &disk_key, split->start, | ||
1857 | path->slots[level + 1] + 1, | ||
1858 | level + 1); | ||
1859 | if (wret) | ||
1860 | ret = wret; | ||
1861 | |||
1862 | ret = btrfs_update_ref(trans, root, c, split, 0, c_nritems - mid); | ||
1863 | BUG_ON(ret); | ||
1864 | |||
1865 | if (path->slots[level] >= mid) { | ||
1866 | path->slots[level] -= mid; | ||
1867 | btrfs_tree_unlock(c); | ||
1868 | free_extent_buffer(c); | ||
1869 | path->nodes[level] = split; | ||
1870 | path->slots[level + 1] += 1; | ||
1871 | } else { | ||
1872 | btrfs_tree_unlock(split); | ||
1873 | free_extent_buffer(split); | ||
1874 | } | ||
1875 | return ret; | ||
1876 | } | ||
1877 | |||
1878 | /* | ||
1879 | * how many bytes are required to store the items in a leaf. start | ||
1880 | * and nr indicate which items in the leaf to check. This totals up the | ||
1881 | * space used both by the item structs and the item data | ||
1882 | */ | ||
1883 | static int leaf_space_used(struct extent_buffer *l, int start, int nr) | ||
1884 | { | ||
1885 | int data_len; | ||
1886 | int nritems = btrfs_header_nritems(l); | ||
1887 | int end = min(nritems, start + nr) - 1; | ||
1888 | |||
1889 | if (!nr) | ||
1890 | return 0; | ||
1891 | data_len = btrfs_item_end_nr(l, start); | ||
1892 | data_len = data_len - btrfs_item_offset_nr(l, end); | ||
1893 | data_len += sizeof(struct btrfs_item) * nr; | ||
1894 | WARN_ON(data_len < 0); | ||
1895 | return data_len; | ||
1896 | } | ||
1897 | |||
1898 | /* | ||
1899 | * The space between the end of the leaf items and | ||
1900 | * the start of the leaf data. IOW, how much room | ||
1901 | * the leaf has left for both items and data | ||
1902 | */ | ||
1903 | int noinline btrfs_leaf_free_space(struct btrfs_root *root, | ||
1904 | struct extent_buffer *leaf) | ||
1905 | { | ||
1906 | int nritems = btrfs_header_nritems(leaf); | ||
1907 | int ret; | ||
1908 | ret = BTRFS_LEAF_DATA_SIZE(root) - leaf_space_used(leaf, 0, nritems); | ||
1909 | if (ret < 0) { | ||
1910 | printk("leaf free space ret %d, leaf data size %lu, used %d nritems %d\n", | ||
1911 | ret, (unsigned long) BTRFS_LEAF_DATA_SIZE(root), | ||
1912 | leaf_space_used(leaf, 0, nritems), nritems); | ||
1913 | } | ||
1914 | return ret; | ||
1915 | } | ||
1916 | |||
1917 | /* | ||
1918 | * push some data in the path leaf to the right, trying to free up at | ||
1919 | * least data_size bytes. returns zero if the push worked, nonzero otherwise | ||
1920 | * | ||
1921 | * returns 1 if the push failed because the other node didn't have enough | ||
1922 | * room, 0 if everything worked out and < 0 if there were major errors. | ||
1923 | */ | ||
1924 | static int push_leaf_right(struct btrfs_trans_handle *trans, struct btrfs_root | ||
1925 | *root, struct btrfs_path *path, int data_size, | ||
1926 | int empty) | ||
1927 | { | ||
1928 | struct extent_buffer *left = path->nodes[0]; | ||
1929 | struct extent_buffer *right; | ||
1930 | struct extent_buffer *upper; | ||
1931 | struct btrfs_disk_key disk_key; | ||
1932 | int slot; | ||
1933 | u32 i; | ||
1934 | int free_space; | ||
1935 | int push_space = 0; | ||
1936 | int push_items = 0; | ||
1937 | struct btrfs_item *item; | ||
1938 | u32 left_nritems; | ||
1939 | u32 nr; | ||
1940 | u32 right_nritems; | ||
1941 | u32 data_end; | ||
1942 | u32 this_item_size; | ||
1943 | int ret; | ||
1944 | |||
1945 | slot = path->slots[1]; | ||
1946 | if (!path->nodes[1]) { | ||
1947 | return 1; | ||
1948 | } | ||
1949 | upper = path->nodes[1]; | ||
1950 | if (slot >= btrfs_header_nritems(upper) - 1) | ||
1951 | return 1; | ||
1952 | |||
1953 | WARN_ON(!btrfs_tree_locked(path->nodes[1])); | ||
1954 | |||
1955 | right = read_node_slot(root, upper, slot + 1); | ||
1956 | btrfs_tree_lock(right); | ||
1957 | free_space = btrfs_leaf_free_space(root, right); | ||
1958 | if (free_space < data_size + sizeof(struct btrfs_item)) | ||
1959 | goto out_unlock; | ||
1960 | |||
1961 | /* cow and double check */ | ||
1962 | ret = btrfs_cow_block(trans, root, right, upper, | ||
1963 | slot + 1, &right, 0); | ||
1964 | if (ret) | ||
1965 | goto out_unlock; | ||
1966 | |||
1967 | free_space = btrfs_leaf_free_space(root, right); | ||
1968 | if (free_space < data_size + sizeof(struct btrfs_item)) | ||
1969 | goto out_unlock; | ||
1970 | |||
1971 | left_nritems = btrfs_header_nritems(left); | ||
1972 | if (left_nritems == 0) | ||
1973 | goto out_unlock; | ||
1974 | |||
1975 | if (empty) | ||
1976 | nr = 0; | ||
1977 | else | ||
1978 | nr = 1; | ||
1979 | |||
1980 | if (path->slots[0] >= left_nritems) | ||
1981 | push_space += data_size + sizeof(*item); | ||
1982 | |||
1983 | i = left_nritems - 1; | ||
1984 | while (i >= nr) { | ||
1985 | item = btrfs_item_nr(left, i); | ||
1986 | |||
1987 | if (!empty && push_items > 0) { | ||
1988 | if (path->slots[0] > i) | ||
1989 | break; | ||
1990 | if (path->slots[0] == i) { | ||
1991 | int space = btrfs_leaf_free_space(root, left); | ||
1992 | if (space + push_space * 2 > free_space) | ||
1993 | break; | ||
1994 | } | ||
1995 | } | ||
1996 | |||
1997 | if (path->slots[0] == i) | ||
1998 | push_space += data_size + sizeof(*item); | ||
1999 | |||
2000 | if (!left->map_token) { | ||
2001 | map_extent_buffer(left, (unsigned long)item, | ||
2002 | sizeof(struct btrfs_item), | ||
2003 | &left->map_token, &left->kaddr, | ||
2004 | &left->map_start, &left->map_len, | ||
2005 | KM_USER1); | ||
2006 | } | ||
2007 | |||
2008 | this_item_size = btrfs_item_size(left, item); | ||
2009 | if (this_item_size + sizeof(*item) + push_space > free_space) | ||
2010 | break; | ||
2011 | |||
2012 | push_items++; | ||
2013 | push_space += this_item_size + sizeof(*item); | ||
2014 | if (i == 0) | ||
2015 | break; | ||
2016 | i--; | ||
2017 | } | ||
2018 | if (left->map_token) { | ||
2019 | unmap_extent_buffer(left, left->map_token, KM_USER1); | ||
2020 | left->map_token = NULL; | ||
2021 | } | ||
2022 | |||
2023 | if (push_items == 0) | ||
2024 | goto out_unlock; | ||
2025 | |||
2026 | if (!empty && push_items == left_nritems) | ||
2027 | WARN_ON(1); | ||
2028 | |||
2029 | /* push left to right */ | ||
2030 | right_nritems = btrfs_header_nritems(right); | ||
2031 | |||
2032 | push_space = btrfs_item_end_nr(left, left_nritems - push_items); | ||
2033 | push_space -= leaf_data_end(root, left); | ||
2034 | |||
2035 | /* make room in the right data area */ | ||
2036 | data_end = leaf_data_end(root, right); | ||
2037 | memmove_extent_buffer(right, | ||
2038 | btrfs_leaf_data(right) + data_end - push_space, | ||
2039 | btrfs_leaf_data(right) + data_end, | ||
2040 | BTRFS_LEAF_DATA_SIZE(root) - data_end); | ||
2041 | |||
2042 | /* copy from the left data area */ | ||
2043 | copy_extent_buffer(right, left, btrfs_leaf_data(right) + | ||
2044 | BTRFS_LEAF_DATA_SIZE(root) - push_space, | ||
2045 | btrfs_leaf_data(left) + leaf_data_end(root, left), | ||
2046 | push_space); | ||
2047 | |||
2048 | memmove_extent_buffer(right, btrfs_item_nr_offset(push_items), | ||
2049 | btrfs_item_nr_offset(0), | ||
2050 | right_nritems * sizeof(struct btrfs_item)); | ||
2051 | |||
2052 | /* copy the items from left to right */ | ||
2053 | copy_extent_buffer(right, left, btrfs_item_nr_offset(0), | ||
2054 | btrfs_item_nr_offset(left_nritems - push_items), | ||
2055 | push_items * sizeof(struct btrfs_item)); | ||
2056 | |||
2057 | /* update the item pointers */ | ||
2058 | right_nritems += push_items; | ||
2059 | btrfs_set_header_nritems(right, right_nritems); | ||
2060 | push_space = BTRFS_LEAF_DATA_SIZE(root); | ||
2061 | for (i = 0; i < right_nritems; i++) { | ||
2062 | item = btrfs_item_nr(right, i); | ||
2063 | if (!right->map_token) { | ||
2064 | map_extent_buffer(right, (unsigned long)item, | ||
2065 | sizeof(struct btrfs_item), | ||
2066 | &right->map_token, &right->kaddr, | ||
2067 | &right->map_start, &right->map_len, | ||
2068 | KM_USER1); | ||
2069 | } | ||
2070 | push_space -= btrfs_item_size(right, item); | ||
2071 | btrfs_set_item_offset(right, item, push_space); | ||
2072 | } | ||
2073 | |||
2074 | if (right->map_token) { | ||
2075 | unmap_extent_buffer(right, right->map_token, KM_USER1); | ||
2076 | right->map_token = NULL; | ||
2077 | } | ||
2078 | left_nritems -= push_items; | ||
2079 | btrfs_set_header_nritems(left, left_nritems); | ||
2080 | |||
2081 | if (left_nritems) | ||
2082 | btrfs_mark_buffer_dirty(left); | ||
2083 | btrfs_mark_buffer_dirty(right); | ||
2084 | |||
2085 | ret = btrfs_update_ref(trans, root, left, right, 0, push_items); | ||
2086 | BUG_ON(ret); | ||
2087 | |||
2088 | btrfs_item_key(right, &disk_key, 0); | ||
2089 | btrfs_set_node_key(upper, &disk_key, slot + 1); | ||
2090 | btrfs_mark_buffer_dirty(upper); | ||
2091 | |||
2092 | /* then fixup the leaf pointer in the path */ | ||
2093 | if (path->slots[0] >= left_nritems) { | ||
2094 | path->slots[0] -= left_nritems; | ||
2095 | if (btrfs_header_nritems(path->nodes[0]) == 0) | ||
2096 | clean_tree_block(trans, root, path->nodes[0]); | ||
2097 | btrfs_tree_unlock(path->nodes[0]); | ||
2098 | free_extent_buffer(path->nodes[0]); | ||
2099 | path->nodes[0] = right; | ||
2100 | path->slots[1] += 1; | ||
2101 | } else { | ||
2102 | btrfs_tree_unlock(right); | ||
2103 | free_extent_buffer(right); | ||
2104 | } | ||
2105 | return 0; | ||
2106 | |||
2107 | out_unlock: | ||
2108 | btrfs_tree_unlock(right); | ||
2109 | free_extent_buffer(right); | ||
2110 | return 1; | ||
2111 | } | ||
2112 | |||
2113 | /* | ||
2114 | * push some data in the path leaf to the left, trying to free up at | ||
2115 | * least data_size bytes. returns zero if the push worked, nonzero otherwise | ||
2116 | */ | ||
2117 | static int push_leaf_left(struct btrfs_trans_handle *trans, struct btrfs_root | ||
2118 | *root, struct btrfs_path *path, int data_size, | ||
2119 | int empty) | ||
2120 | { | ||
2121 | struct btrfs_disk_key disk_key; | ||
2122 | struct extent_buffer *right = path->nodes[0]; | ||
2123 | struct extent_buffer *left; | ||
2124 | int slot; | ||
2125 | int i; | ||
2126 | int free_space; | ||
2127 | int push_space = 0; | ||
2128 | int push_items = 0; | ||
2129 | struct btrfs_item *item; | ||
2130 | u32 old_left_nritems; | ||
2131 | u32 right_nritems; | ||
2132 | u32 nr; | ||
2133 | int ret = 0; | ||
2134 | int wret; | ||
2135 | u32 this_item_size; | ||
2136 | u32 old_left_item_size; | ||
2137 | |||
2138 | slot = path->slots[1]; | ||
2139 | if (slot == 0) | ||
2140 | return 1; | ||
2141 | if (!path->nodes[1]) | ||
2142 | return 1; | ||
2143 | |||
2144 | right_nritems = btrfs_header_nritems(right); | ||
2145 | if (right_nritems == 0) { | ||
2146 | return 1; | ||
2147 | } | ||
2148 | |||
2149 | WARN_ON(!btrfs_tree_locked(path->nodes[1])); | ||
2150 | |||
2151 | left = read_node_slot(root, path->nodes[1], slot - 1); | ||
2152 | btrfs_tree_lock(left); | ||
2153 | free_space = btrfs_leaf_free_space(root, left); | ||
2154 | if (free_space < data_size + sizeof(struct btrfs_item)) { | ||
2155 | ret = 1; | ||
2156 | goto out; | ||
2157 | } | ||
2158 | |||
2159 | /* cow and double check */ | ||
2160 | ret = btrfs_cow_block(trans, root, left, | ||
2161 | path->nodes[1], slot - 1, &left, 0); | ||
2162 | if (ret) { | ||
2163 | /* we hit -ENOSPC, but it isn't fatal here */ | ||
2164 | ret = 1; | ||
2165 | goto out; | ||
2166 | } | ||
2167 | |||
2168 | free_space = btrfs_leaf_free_space(root, left); | ||
2169 | if (free_space < data_size + sizeof(struct btrfs_item)) { | ||
2170 | ret = 1; | ||
2171 | goto out; | ||
2172 | } | ||
2173 | |||
2174 | if (empty) | ||
2175 | nr = right_nritems; | ||
2176 | else | ||
2177 | nr = right_nritems - 1; | ||
2178 | |||
2179 | for (i = 0; i < nr; i++) { | ||
2180 | item = btrfs_item_nr(right, i); | ||
2181 | if (!right->map_token) { | ||
2182 | map_extent_buffer(right, (unsigned long)item, | ||
2183 | sizeof(struct btrfs_item), | ||
2184 | &right->map_token, &right->kaddr, | ||
2185 | &right->map_start, &right->map_len, | ||
2186 | KM_USER1); | ||
2187 | } | ||
2188 | |||
2189 | if (!empty && push_items > 0) { | ||
2190 | if (path->slots[0] < i) | ||
2191 | break; | ||
2192 | if (path->slots[0] == i) { | ||
2193 | int space = btrfs_leaf_free_space(root, right); | ||
2194 | if (space + push_space * 2 > free_space) | ||
2195 | break; | ||
2196 | } | ||
2197 | } | ||
2198 | |||
2199 | if (path->slots[0] == i) | ||
2200 | push_space += data_size + sizeof(*item); | ||
2201 | |||
2202 | this_item_size = btrfs_item_size(right, item); | ||
2203 | if (this_item_size + sizeof(*item) + push_space > free_space) | ||
2204 | break; | ||
2205 | |||
2206 | push_items++; | ||
2207 | push_space += this_item_size + sizeof(*item); | ||
2208 | } | ||
2209 | |||
2210 | if (right->map_token) { | ||
2211 | unmap_extent_buffer(right, right->map_token, KM_USER1); | ||
2212 | right->map_token = NULL; | ||
2213 | } | ||
2214 | |||
2215 | if (push_items == 0) { | ||
2216 | ret = 1; | ||
2217 | goto out; | ||
2218 | } | ||
2219 | if (!empty && push_items == btrfs_header_nritems(right)) | ||
2220 | WARN_ON(1); | ||
2221 | |||
2222 | /* push data from right to left */ | ||
2223 | copy_extent_buffer(left, right, | ||
2224 | btrfs_item_nr_offset(btrfs_header_nritems(left)), | ||
2225 | btrfs_item_nr_offset(0), | ||
2226 | push_items * sizeof(struct btrfs_item)); | ||
2227 | |||
2228 | push_space = BTRFS_LEAF_DATA_SIZE(root) - | ||
2229 | btrfs_item_offset_nr(right, push_items -1); | ||
2230 | |||
2231 | copy_extent_buffer(left, right, btrfs_leaf_data(left) + | ||
2232 | leaf_data_end(root, left) - push_space, | ||
2233 | btrfs_leaf_data(right) + | ||
2234 | btrfs_item_offset_nr(right, push_items - 1), | ||
2235 | push_space); | ||
2236 | old_left_nritems = btrfs_header_nritems(left); | ||
2237 | BUG_ON(old_left_nritems < 0); | ||
2238 | |||
2239 | old_left_item_size = btrfs_item_offset_nr(left, old_left_nritems - 1); | ||
2240 | for (i = old_left_nritems; i < old_left_nritems + push_items; i++) { | ||
2241 | u32 ioff; | ||
2242 | |||
2243 | item = btrfs_item_nr(left, i); | ||
2244 | if (!left->map_token) { | ||
2245 | map_extent_buffer(left, (unsigned long)item, | ||
2246 | sizeof(struct btrfs_item), | ||
2247 | &left->map_token, &left->kaddr, | ||
2248 | &left->map_start, &left->map_len, | ||
2249 | KM_USER1); | ||
2250 | } | ||
2251 | |||
2252 | ioff = btrfs_item_offset(left, item); | ||
2253 | btrfs_set_item_offset(left, item, | ||
2254 | ioff - (BTRFS_LEAF_DATA_SIZE(root) - old_left_item_size)); | ||
2255 | } | ||
2256 | btrfs_set_header_nritems(left, old_left_nritems + push_items); | ||
2257 | if (left->map_token) { | ||
2258 | unmap_extent_buffer(left, left->map_token, KM_USER1); | ||
2259 | left->map_token = NULL; | ||
2260 | } | ||
2261 | |||
2262 | /* fixup right node */ | ||
2263 | if (push_items > right_nritems) { | ||
2264 | printk("push items %d nr %u\n", push_items, right_nritems); | ||
2265 | WARN_ON(1); | ||
2266 | } | ||
2267 | |||
2268 | if (push_items < right_nritems) { | ||
2269 | push_space = btrfs_item_offset_nr(right, push_items - 1) - | ||
2270 | leaf_data_end(root, right); | ||
2271 | memmove_extent_buffer(right, btrfs_leaf_data(right) + | ||
2272 | BTRFS_LEAF_DATA_SIZE(root) - push_space, | ||
2273 | btrfs_leaf_data(right) + | ||
2274 | leaf_data_end(root, right), push_space); | ||
2275 | |||
2276 | memmove_extent_buffer(right, btrfs_item_nr_offset(0), | ||
2277 | btrfs_item_nr_offset(push_items), | ||
2278 | (btrfs_header_nritems(right) - push_items) * | ||
2279 | sizeof(struct btrfs_item)); | ||
2280 | } | ||
2281 | right_nritems -= push_items; | ||
2282 | btrfs_set_header_nritems(right, right_nritems); | ||
2283 | push_space = BTRFS_LEAF_DATA_SIZE(root); | ||
2284 | for (i = 0; i < right_nritems; i++) { | ||
2285 | item = btrfs_item_nr(right, i); | ||
2286 | |||
2287 | if (!right->map_token) { | ||
2288 | map_extent_buffer(right, (unsigned long)item, | ||
2289 | sizeof(struct btrfs_item), | ||
2290 | &right->map_token, &right->kaddr, | ||
2291 | &right->map_start, &right->map_len, | ||
2292 | KM_USER1); | ||
2293 | } | ||
2294 | |||
2295 | push_space = push_space - btrfs_item_size(right, item); | ||
2296 | btrfs_set_item_offset(right, item, push_space); | ||
2297 | } | ||
2298 | if (right->map_token) { | ||
2299 | unmap_extent_buffer(right, right->map_token, KM_USER1); | ||
2300 | right->map_token = NULL; | ||
2301 | } | ||
2302 | |||
2303 | btrfs_mark_buffer_dirty(left); | ||
2304 | if (right_nritems) | ||
2305 | btrfs_mark_buffer_dirty(right); | ||
2306 | |||
2307 | ret = btrfs_update_ref(trans, root, right, left, | ||
2308 | old_left_nritems, push_items); | ||
2309 | BUG_ON(ret); | ||
2310 | |||
2311 | btrfs_item_key(right, &disk_key, 0); | ||
2312 | wret = fixup_low_keys(trans, root, path, &disk_key, 1); | ||
2313 | if (wret) | ||
2314 | ret = wret; | ||
2315 | |||
2316 | /* then fixup the leaf pointer in the path */ | ||
2317 | if (path->slots[0] < push_items) { | ||
2318 | path->slots[0] += old_left_nritems; | ||
2319 | if (btrfs_header_nritems(path->nodes[0]) == 0) | ||
2320 | clean_tree_block(trans, root, path->nodes[0]); | ||
2321 | btrfs_tree_unlock(path->nodes[0]); | ||
2322 | free_extent_buffer(path->nodes[0]); | ||
2323 | path->nodes[0] = left; | ||
2324 | path->slots[1] -= 1; | ||
2325 | } else { | ||
2326 | btrfs_tree_unlock(left); | ||
2327 | free_extent_buffer(left); | ||
2328 | path->slots[0] -= push_items; | ||
2329 | } | ||
2330 | BUG_ON(path->slots[0] < 0); | ||
2331 | return ret; | ||
2332 | out: | ||
2333 | btrfs_tree_unlock(left); | ||
2334 | free_extent_buffer(left); | ||
2335 | return ret; | ||
2336 | } | ||
2337 | |||
2338 | /* | ||
2339 | * split the path's leaf in two, making sure there is at least data_size | ||
2340 | * available for the resulting leaf level of the path. | ||
2341 | * | ||
2342 | * returns 0 if all went well and < 0 on failure. | ||
2343 | */ | ||
2344 | static noinline int split_leaf(struct btrfs_trans_handle *trans, | ||
2345 | struct btrfs_root *root, | ||
2346 | struct btrfs_key *ins_key, | ||
2347 | struct btrfs_path *path, int data_size, | ||
2348 | int extend) | ||
2349 | { | ||
2350 | struct extent_buffer *l; | ||
2351 | u32 nritems; | ||
2352 | int mid; | ||
2353 | int slot; | ||
2354 | struct extent_buffer *right; | ||
2355 | int space_needed = data_size + sizeof(struct btrfs_item); | ||
2356 | int data_copy_size; | ||
2357 | int rt_data_off; | ||
2358 | int i; | ||
2359 | int ret = 0; | ||
2360 | int wret; | ||
2361 | int double_split; | ||
2362 | int num_doubles = 0; | ||
2363 | struct btrfs_disk_key disk_key; | ||
2364 | |||
2365 | if (extend) | ||
2366 | space_needed = data_size; | ||
2367 | |||
2368 | /* first try to make some room by pushing left and right */ | ||
2369 | if (ins_key->type != BTRFS_DIR_ITEM_KEY) { | ||
2370 | wret = push_leaf_right(trans, root, path, data_size, 0); | ||
2371 | if (wret < 0) { | ||
2372 | return wret; | ||
2373 | } | ||
2374 | if (wret) { | ||
2375 | wret = push_leaf_left(trans, root, path, data_size, 0); | ||
2376 | if (wret < 0) | ||
2377 | return wret; | ||
2378 | } | ||
2379 | l = path->nodes[0]; | ||
2380 | |||
2381 | /* did the pushes work? */ | ||
2382 | if (btrfs_leaf_free_space(root, l) >= space_needed) | ||
2383 | return 0; | ||
2384 | } | ||
2385 | |||
2386 | if (!path->nodes[1]) { | ||
2387 | ret = insert_new_root(trans, root, path, 1); | ||
2388 | if (ret) | ||
2389 | return ret; | ||
2390 | } | ||
2391 | again: | ||
2392 | double_split = 0; | ||
2393 | l = path->nodes[0]; | ||
2394 | slot = path->slots[0]; | ||
2395 | nritems = btrfs_header_nritems(l); | ||
2396 | mid = (nritems + 1)/ 2; | ||
2397 | |||
2398 | right = btrfs_alloc_free_block(trans, root, root->leafsize, | ||
2399 | path->nodes[1]->start, | ||
2400 | root->root_key.objectid, | ||
2401 | trans->transid, 0, l->start, 0); | ||
2402 | if (IS_ERR(right)) { | ||
2403 | BUG_ON(1); | ||
2404 | return PTR_ERR(right); | ||
2405 | } | ||
2406 | |||
2407 | memset_extent_buffer(right, 0, 0, sizeof(struct btrfs_header)); | ||
2408 | btrfs_set_header_bytenr(right, right->start); | ||
2409 | btrfs_set_header_generation(right, trans->transid); | ||
2410 | btrfs_set_header_owner(right, root->root_key.objectid); | ||
2411 | btrfs_set_header_level(right, 0); | ||
2412 | write_extent_buffer(right, root->fs_info->fsid, | ||
2413 | (unsigned long)btrfs_header_fsid(right), | ||
2414 | BTRFS_FSID_SIZE); | ||
2415 | |||
2416 | write_extent_buffer(right, root->fs_info->chunk_tree_uuid, | ||
2417 | (unsigned long)btrfs_header_chunk_tree_uuid(right), | ||
2418 | BTRFS_UUID_SIZE); | ||
2419 | if (mid <= slot) { | ||
2420 | if (nritems == 1 || | ||
2421 | leaf_space_used(l, mid, nritems - mid) + space_needed > | ||
2422 | BTRFS_LEAF_DATA_SIZE(root)) { | ||
2423 | if (slot >= nritems) { | ||
2424 | btrfs_cpu_key_to_disk(&disk_key, ins_key); | ||
2425 | btrfs_set_header_nritems(right, 0); | ||
2426 | wret = insert_ptr(trans, root, path, | ||
2427 | &disk_key, right->start, | ||
2428 | path->slots[1] + 1, 1); | ||
2429 | if (wret) | ||
2430 | ret = wret; | ||
2431 | |||
2432 | btrfs_tree_unlock(path->nodes[0]); | ||
2433 | free_extent_buffer(path->nodes[0]); | ||
2434 | path->nodes[0] = right; | ||
2435 | path->slots[0] = 0; | ||
2436 | path->slots[1] += 1; | ||
2437 | btrfs_mark_buffer_dirty(right); | ||
2438 | return ret; | ||
2439 | } | ||
2440 | mid = slot; | ||
2441 | if (mid != nritems && | ||
2442 | leaf_space_used(l, mid, nritems - mid) + | ||
2443 | space_needed > BTRFS_LEAF_DATA_SIZE(root)) { | ||
2444 | double_split = 1; | ||
2445 | } | ||
2446 | } | ||
2447 | } else { | ||
2448 | if (leaf_space_used(l, 0, mid + 1) + space_needed > | ||
2449 | BTRFS_LEAF_DATA_SIZE(root)) { | ||
2450 | if (!extend && slot == 0) { | ||
2451 | btrfs_cpu_key_to_disk(&disk_key, ins_key); | ||
2452 | btrfs_set_header_nritems(right, 0); | ||
2453 | wret = insert_ptr(trans, root, path, | ||
2454 | &disk_key, | ||
2455 | right->start, | ||
2456 | path->slots[1], 1); | ||
2457 | if (wret) | ||
2458 | ret = wret; | ||
2459 | btrfs_tree_unlock(path->nodes[0]); | ||
2460 | free_extent_buffer(path->nodes[0]); | ||
2461 | path->nodes[0] = right; | ||
2462 | path->slots[0] = 0; | ||
2463 | if (path->slots[1] == 0) { | ||
2464 | wret = fixup_low_keys(trans, root, | ||
2465 | path, &disk_key, 1); | ||
2466 | if (wret) | ||
2467 | ret = wret; | ||
2468 | } | ||
2469 | btrfs_mark_buffer_dirty(right); | ||
2470 | return ret; | ||
2471 | } else if (extend && slot == 0) { | ||
2472 | mid = 1; | ||
2473 | } else { | ||
2474 | mid = slot; | ||
2475 | if (mid != nritems && | ||
2476 | leaf_space_used(l, mid, nritems - mid) + | ||
2477 | space_needed > BTRFS_LEAF_DATA_SIZE(root)) { | ||
2478 | double_split = 1; | ||
2479 | } | ||
2480 | } | ||
2481 | } | ||
2482 | } | ||
2483 | nritems = nritems - mid; | ||
2484 | btrfs_set_header_nritems(right, nritems); | ||
2485 | data_copy_size = btrfs_item_end_nr(l, mid) - leaf_data_end(root, l); | ||
2486 | |||
2487 | copy_extent_buffer(right, l, btrfs_item_nr_offset(0), | ||
2488 | btrfs_item_nr_offset(mid), | ||
2489 | nritems * sizeof(struct btrfs_item)); | ||
2490 | |||
2491 | copy_extent_buffer(right, l, | ||
2492 | btrfs_leaf_data(right) + BTRFS_LEAF_DATA_SIZE(root) - | ||
2493 | data_copy_size, btrfs_leaf_data(l) + | ||
2494 | leaf_data_end(root, l), data_copy_size); | ||
2495 | |||
2496 | rt_data_off = BTRFS_LEAF_DATA_SIZE(root) - | ||
2497 | btrfs_item_end_nr(l, mid); | ||
2498 | |||
2499 | for (i = 0; i < nritems; i++) { | ||
2500 | struct btrfs_item *item = btrfs_item_nr(right, i); | ||
2501 | u32 ioff; | ||
2502 | |||
2503 | if (!right->map_token) { | ||
2504 | map_extent_buffer(right, (unsigned long)item, | ||
2505 | sizeof(struct btrfs_item), | ||
2506 | &right->map_token, &right->kaddr, | ||
2507 | &right->map_start, &right->map_len, | ||
2508 | KM_USER1); | ||
2509 | } | ||
2510 | |||
2511 | ioff = btrfs_item_offset(right, item); | ||
2512 | btrfs_set_item_offset(right, item, ioff + rt_data_off); | ||
2513 | } | ||
2514 | |||
2515 | if (right->map_token) { | ||
2516 | unmap_extent_buffer(right, right->map_token, KM_USER1); | ||
2517 | right->map_token = NULL; | ||
2518 | } | ||
2519 | |||
2520 | btrfs_set_header_nritems(l, mid); | ||
2521 | ret = 0; | ||
2522 | btrfs_item_key(right, &disk_key, 0); | ||
2523 | wret = insert_ptr(trans, root, path, &disk_key, right->start, | ||
2524 | path->slots[1] + 1, 1); | ||
2525 | if (wret) | ||
2526 | ret = wret; | ||
2527 | |||
2528 | btrfs_mark_buffer_dirty(right); | ||
2529 | btrfs_mark_buffer_dirty(l); | ||
2530 | BUG_ON(path->slots[0] != slot); | ||
2531 | |||
2532 | ret = btrfs_update_ref(trans, root, l, right, 0, nritems); | ||
2533 | BUG_ON(ret); | ||
2534 | |||
2535 | if (mid <= slot) { | ||
2536 | btrfs_tree_unlock(path->nodes[0]); | ||
2537 | free_extent_buffer(path->nodes[0]); | ||
2538 | path->nodes[0] = right; | ||
2539 | path->slots[0] -= mid; | ||
2540 | path->slots[1] += 1; | ||
2541 | } else { | ||
2542 | btrfs_tree_unlock(right); | ||
2543 | free_extent_buffer(right); | ||
2544 | } | ||
2545 | |||
2546 | BUG_ON(path->slots[0] < 0); | ||
2547 | |||
2548 | if (double_split) { | ||
2549 | BUG_ON(num_doubles != 0); | ||
2550 | num_doubles++; | ||
2551 | goto again; | ||
2552 | } | ||
2553 | return ret; | ||
2554 | } | ||
2555 | |||
2556 | int btrfs_truncate_item(struct btrfs_trans_handle *trans, | ||
2557 | struct btrfs_root *root, | ||
2558 | struct btrfs_path *path, | ||
2559 | u32 new_size, int from_end) | ||
2560 | { | ||
2561 | int ret = 0; | ||
2562 | int slot; | ||
2563 | int slot_orig; | ||
2564 | struct extent_buffer *leaf; | ||
2565 | struct btrfs_item *item; | ||
2566 | u32 nritems; | ||
2567 | unsigned int data_end; | ||
2568 | unsigned int old_data_start; | ||
2569 | unsigned int old_size; | ||
2570 | unsigned int size_diff; | ||
2571 | int i; | ||
2572 | |||
2573 | slot_orig = path->slots[0]; | ||
2574 | leaf = path->nodes[0]; | ||
2575 | slot = path->slots[0]; | ||
2576 | |||
2577 | old_size = btrfs_item_size_nr(leaf, slot); | ||
2578 | if (old_size == new_size) | ||
2579 | return 0; | ||
2580 | |||
2581 | nritems = btrfs_header_nritems(leaf); | ||
2582 | data_end = leaf_data_end(root, leaf); | ||
2583 | |||
2584 | old_data_start = btrfs_item_offset_nr(leaf, slot); | ||
2585 | |||
2586 | size_diff = old_size - new_size; | ||
2587 | |||
2588 | BUG_ON(slot < 0); | ||
2589 | BUG_ON(slot >= nritems); | ||
2590 | |||
2591 | /* | ||
2592 | * item0..itemN ... dataN.offset..dataN.size .. data0.size | ||
2593 | */ | ||
2594 | /* first correct the data pointers */ | ||
2595 | for (i = slot; i < nritems; i++) { | ||
2596 | u32 ioff; | ||
2597 | item = btrfs_item_nr(leaf, i); | ||
2598 | |||
2599 | if (!leaf->map_token) { | ||
2600 | map_extent_buffer(leaf, (unsigned long)item, | ||
2601 | sizeof(struct btrfs_item), | ||
2602 | &leaf->map_token, &leaf->kaddr, | ||
2603 | &leaf->map_start, &leaf->map_len, | ||
2604 | KM_USER1); | ||
2605 | } | ||
2606 | |||
2607 | ioff = btrfs_item_offset(leaf, item); | ||
2608 | btrfs_set_item_offset(leaf, item, ioff + size_diff); | ||
2609 | } | ||
2610 | |||
2611 | if (leaf->map_token) { | ||
2612 | unmap_extent_buffer(leaf, leaf->map_token, KM_USER1); | ||
2613 | leaf->map_token = NULL; | ||
2614 | } | ||
2615 | |||
2616 | /* shift the data */ | ||
2617 | if (from_end) { | ||
2618 | memmove_extent_buffer(leaf, btrfs_leaf_data(leaf) + | ||
2619 | data_end + size_diff, btrfs_leaf_data(leaf) + | ||
2620 | data_end, old_data_start + new_size - data_end); | ||
2621 | } else { | ||
2622 | struct btrfs_disk_key disk_key; | ||
2623 | u64 offset; | ||
2624 | |||
2625 | btrfs_item_key(leaf, &disk_key, slot); | ||
2626 | |||
2627 | if (btrfs_disk_key_type(&disk_key) == BTRFS_EXTENT_DATA_KEY) { | ||
2628 | unsigned long ptr; | ||
2629 | struct btrfs_file_extent_item *fi; | ||
2630 | |||
2631 | fi = btrfs_item_ptr(leaf, slot, | ||
2632 | struct btrfs_file_extent_item); | ||
2633 | fi = (struct btrfs_file_extent_item *)( | ||
2634 | (unsigned long)fi - size_diff); | ||
2635 | |||
2636 | if (btrfs_file_extent_type(leaf, fi) == | ||
2637 | BTRFS_FILE_EXTENT_INLINE) { | ||
2638 | ptr = btrfs_item_ptr_offset(leaf, slot); | ||
2639 | memmove_extent_buffer(leaf, ptr, | ||
2640 | (unsigned long)fi, | ||
2641 | offsetof(struct btrfs_file_extent_item, | ||
2642 | disk_bytenr)); | ||
2643 | } | ||
2644 | } | ||
2645 | |||
2646 | memmove_extent_buffer(leaf, btrfs_leaf_data(leaf) + | ||
2647 | data_end + size_diff, btrfs_leaf_data(leaf) + | ||
2648 | data_end, old_data_start - data_end); | ||
2649 | |||
2650 | offset = btrfs_disk_key_offset(&disk_key); | ||
2651 | btrfs_set_disk_key_offset(&disk_key, offset + size_diff); | ||
2652 | btrfs_set_item_key(leaf, &disk_key, slot); | ||
2653 | if (slot == 0) | ||
2654 | fixup_low_keys(trans, root, path, &disk_key, 1); | ||
2655 | } | ||
2656 | |||
2657 | item = btrfs_item_nr(leaf, slot); | ||
2658 | btrfs_set_item_size(leaf, item, new_size); | ||
2659 | btrfs_mark_buffer_dirty(leaf); | ||
2660 | |||
2661 | ret = 0; | ||
2662 | if (btrfs_leaf_free_space(root, leaf) < 0) { | ||
2663 | btrfs_print_leaf(root, leaf); | ||
2664 | BUG(); | ||
2665 | } | ||
2666 | return ret; | ||
2667 | } | ||
2668 | |||
2669 | int btrfs_extend_item(struct btrfs_trans_handle *trans, | ||
2670 | struct btrfs_root *root, struct btrfs_path *path, | ||
2671 | u32 data_size) | ||
2672 | { | ||
2673 | int ret = 0; | ||
2674 | int slot; | ||
2675 | int slot_orig; | ||
2676 | struct extent_buffer *leaf; | ||
2677 | struct btrfs_item *item; | ||
2678 | u32 nritems; | ||
2679 | unsigned int data_end; | ||
2680 | unsigned int old_data; | ||
2681 | unsigned int old_size; | ||
2682 | int i; | ||
2683 | |||
2684 | slot_orig = path->slots[0]; | ||
2685 | leaf = path->nodes[0]; | ||
2686 | |||
2687 | nritems = btrfs_header_nritems(leaf); | ||
2688 | data_end = leaf_data_end(root, leaf); | ||
2689 | |||
2690 | if (btrfs_leaf_free_space(root, leaf) < data_size) { | ||
2691 | btrfs_print_leaf(root, leaf); | ||
2692 | BUG(); | ||
2693 | } | ||
2694 | slot = path->slots[0]; | ||
2695 | old_data = btrfs_item_end_nr(leaf, slot); | ||
2696 | |||
2697 | BUG_ON(slot < 0); | ||
2698 | if (slot >= nritems) { | ||
2699 | btrfs_print_leaf(root, leaf); | ||
2700 | printk("slot %d too large, nritems %d\n", slot, nritems); | ||
2701 | BUG_ON(1); | ||
2702 | } | ||
2703 | |||
2704 | /* | ||
2705 | * item0..itemN ... dataN.offset..dataN.size .. data0.size | ||
2706 | */ | ||
2707 | /* first correct the data pointers */ | ||
2708 | for (i = slot; i < nritems; i++) { | ||
2709 | u32 ioff; | ||
2710 | item = btrfs_item_nr(leaf, i); | ||
2711 | |||
2712 | if (!leaf->map_token) { | ||
2713 | map_extent_buffer(leaf, (unsigned long)item, | ||
2714 | sizeof(struct btrfs_item), | ||
2715 | &leaf->map_token, &leaf->kaddr, | ||
2716 | &leaf->map_start, &leaf->map_len, | ||
2717 | KM_USER1); | ||
2718 | } | ||
2719 | ioff = btrfs_item_offset(leaf, item); | ||
2720 | btrfs_set_item_offset(leaf, item, ioff - data_size); | ||
2721 | } | ||
2722 | |||
2723 | if (leaf->map_token) { | ||
2724 | unmap_extent_buffer(leaf, leaf->map_token, KM_USER1); | ||
2725 | leaf->map_token = NULL; | ||
2726 | } | ||
2727 | |||
2728 | /* shift the data */ | ||
2729 | memmove_extent_buffer(leaf, btrfs_leaf_data(leaf) + | ||
2730 | data_end - data_size, btrfs_leaf_data(leaf) + | ||
2731 | data_end, old_data - data_end); | ||
2732 | |||
2733 | data_end = old_data; | ||
2734 | old_size = btrfs_item_size_nr(leaf, slot); | ||
2735 | item = btrfs_item_nr(leaf, slot); | ||
2736 | btrfs_set_item_size(leaf, item, old_size + data_size); | ||
2737 | btrfs_mark_buffer_dirty(leaf); | ||
2738 | |||
2739 | ret = 0; | ||
2740 | if (btrfs_leaf_free_space(root, leaf) < 0) { | ||
2741 | btrfs_print_leaf(root, leaf); | ||
2742 | BUG(); | ||
2743 | } | ||
2744 | return ret; | ||
2745 | } | ||
2746 | |||
2747 | /* | ||
2748 | * Given a key and some data, insert an item into the tree. | ||
2749 | * This does all the path init required, making room in the tree if needed. | ||
2750 | */ | ||
2751 | int btrfs_insert_empty_items(struct btrfs_trans_handle *trans, | ||
2752 | struct btrfs_root *root, | ||
2753 | struct btrfs_path *path, | ||
2754 | struct btrfs_key *cpu_key, u32 *data_size, | ||
2755 | int nr) | ||
2756 | { | ||
2757 | struct extent_buffer *leaf; | ||
2758 | struct btrfs_item *item; | ||
2759 | int ret = 0; | ||
2760 | int slot; | ||
2761 | int slot_orig; | ||
2762 | int i; | ||
2763 | u32 nritems; | ||
2764 | u32 total_size = 0; | ||
2765 | u32 total_data = 0; | ||
2766 | unsigned int data_end; | ||
2767 | struct btrfs_disk_key disk_key; | ||
2768 | |||
2769 | for (i = 0; i < nr; i++) { | ||
2770 | total_data += data_size[i]; | ||
2771 | } | ||
2772 | |||
2773 | total_size = total_data + (nr * sizeof(struct btrfs_item)); | ||
2774 | ret = btrfs_search_slot(trans, root, cpu_key, path, total_size, 1); | ||
2775 | if (ret == 0) | ||
2776 | return -EEXIST; | ||
2777 | if (ret < 0) | ||
2778 | goto out; | ||
2779 | |||
2780 | slot_orig = path->slots[0]; | ||
2781 | leaf = path->nodes[0]; | ||
2782 | |||
2783 | nritems = btrfs_header_nritems(leaf); | ||
2784 | data_end = leaf_data_end(root, leaf); | ||
2785 | |||
2786 | if (btrfs_leaf_free_space(root, leaf) < total_size) { | ||
2787 | btrfs_print_leaf(root, leaf); | ||
2788 | printk("not enough freespace need %u have %d\n", | ||
2789 | total_size, btrfs_leaf_free_space(root, leaf)); | ||
2790 | BUG(); | ||
2791 | } | ||
2792 | |||
2793 | slot = path->slots[0]; | ||
2794 | BUG_ON(slot < 0); | ||
2795 | |||
2796 | if (slot != nritems) { | ||
2797 | unsigned int old_data = btrfs_item_end_nr(leaf, slot); | ||
2798 | |||
2799 | if (old_data < data_end) { | ||
2800 | btrfs_print_leaf(root, leaf); | ||
2801 | printk("slot %d old_data %d data_end %d\n", | ||
2802 | slot, old_data, data_end); | ||
2803 | BUG_ON(1); | ||
2804 | } | ||
2805 | /* | ||
2806 | * item0..itemN ... dataN.offset..dataN.size .. data0.size | ||
2807 | */ | ||
2808 | /* first correct the data pointers */ | ||
2809 | WARN_ON(leaf->map_token); | ||
2810 | for (i = slot; i < nritems; i++) { | ||
2811 | u32 ioff; | ||
2812 | |||
2813 | item = btrfs_item_nr(leaf, i); | ||
2814 | if (!leaf->map_token) { | ||
2815 | map_extent_buffer(leaf, (unsigned long)item, | ||
2816 | sizeof(struct btrfs_item), | ||
2817 | &leaf->map_token, &leaf->kaddr, | ||
2818 | &leaf->map_start, &leaf->map_len, | ||
2819 | KM_USER1); | ||
2820 | } | ||
2821 | |||
2822 | ioff = btrfs_item_offset(leaf, item); | ||
2823 | btrfs_set_item_offset(leaf, item, ioff - total_data); | ||
2824 | } | ||
2825 | if (leaf->map_token) { | ||
2826 | unmap_extent_buffer(leaf, leaf->map_token, KM_USER1); | ||
2827 | leaf->map_token = NULL; | ||
2828 | } | ||
2829 | |||
2830 | /* shift the items */ | ||
2831 | memmove_extent_buffer(leaf, btrfs_item_nr_offset(slot + nr), | ||
2832 | btrfs_item_nr_offset(slot), | ||
2833 | (nritems - slot) * sizeof(struct btrfs_item)); | ||
2834 | |||
2835 | /* shift the data */ | ||
2836 | memmove_extent_buffer(leaf, btrfs_leaf_data(leaf) + | ||
2837 | data_end - total_data, btrfs_leaf_data(leaf) + | ||
2838 | data_end, old_data - data_end); | ||
2839 | data_end = old_data; | ||
2840 | } | ||
2841 | |||
2842 | /* setup the item for the new data */ | ||
2843 | for (i = 0; i < nr; i++) { | ||
2844 | btrfs_cpu_key_to_disk(&disk_key, cpu_key + i); | ||
2845 | btrfs_set_item_key(leaf, &disk_key, slot + i); | ||
2846 | item = btrfs_item_nr(leaf, slot + i); | ||
2847 | btrfs_set_item_offset(leaf, item, data_end - data_size[i]); | ||
2848 | data_end -= data_size[i]; | ||
2849 | btrfs_set_item_size(leaf, item, data_size[i]); | ||
2850 | } | ||
2851 | btrfs_set_header_nritems(leaf, nritems + nr); | ||
2852 | btrfs_mark_buffer_dirty(leaf); | ||
2853 | |||
2854 | ret = 0; | ||
2855 | if (slot == 0) { | ||
2856 | btrfs_cpu_key_to_disk(&disk_key, cpu_key); | ||
2857 | ret = fixup_low_keys(trans, root, path, &disk_key, 1); | ||
2858 | } | ||
2859 | |||
2860 | if (btrfs_leaf_free_space(root, leaf) < 0) { | ||
2861 | btrfs_print_leaf(root, leaf); | ||
2862 | BUG(); | ||
2863 | } | ||
2864 | out: | ||
2865 | return ret; | ||
2866 | } | ||
2867 | |||
2868 | /* | ||
2869 | * Given a key and some data, insert an item into the tree. | ||
2870 | * This does all the path init required, making room in the tree if needed. | ||
2871 | */ | ||
2872 | int btrfs_insert_item(struct btrfs_trans_handle *trans, struct btrfs_root | ||
2873 | *root, struct btrfs_key *cpu_key, void *data, u32 | ||
2874 | data_size) | ||
2875 | { | ||
2876 | int ret = 0; | ||
2877 | struct btrfs_path *path; | ||
2878 | struct extent_buffer *leaf; | ||
2879 | unsigned long ptr; | ||
2880 | |||
2881 | path = btrfs_alloc_path(); | ||
2882 | BUG_ON(!path); | ||
2883 | ret = btrfs_insert_empty_item(trans, root, path, cpu_key, data_size); | ||
2884 | if (!ret) { | ||
2885 | leaf = path->nodes[0]; | ||
2886 | ptr = btrfs_item_ptr_offset(leaf, path->slots[0]); | ||
2887 | write_extent_buffer(leaf, data, ptr, data_size); | ||
2888 | btrfs_mark_buffer_dirty(leaf); | ||
2889 | } | ||
2890 | btrfs_free_path(path); | ||
2891 | return ret; | ||
2892 | } | ||
2893 | |||
2894 | /* | ||
2895 | * delete the pointer from a given node. | ||
2896 | * | ||
2897 | * If the delete empties a node, the node is removed from the tree, | ||
2898 | * continuing all the way the root if required. The root is converted into | ||
2899 | * a leaf if all the nodes are emptied. | ||
2900 | */ | ||
2901 | static int del_ptr(struct btrfs_trans_handle *trans, struct btrfs_root *root, | ||
2902 | struct btrfs_path *path, int level, int slot) | ||
2903 | { | ||
2904 | struct extent_buffer *parent = path->nodes[level]; | ||
2905 | u32 nritems; | ||
2906 | int ret = 0; | ||
2907 | int wret; | ||
2908 | |||
2909 | nritems = btrfs_header_nritems(parent); | ||
2910 | if (slot != nritems -1) { | ||
2911 | memmove_extent_buffer(parent, | ||
2912 | btrfs_node_key_ptr_offset(slot), | ||
2913 | btrfs_node_key_ptr_offset(slot + 1), | ||
2914 | sizeof(struct btrfs_key_ptr) * | ||
2915 | (nritems - slot - 1)); | ||
2916 | } | ||
2917 | nritems--; | ||
2918 | btrfs_set_header_nritems(parent, nritems); | ||
2919 | if (nritems == 0 && parent == root->node) { | ||
2920 | BUG_ON(btrfs_header_level(root->node) != 1); | ||
2921 | /* just turn the root into a leaf and break */ | ||
2922 | btrfs_set_header_level(root->node, 0); | ||
2923 | } else if (slot == 0) { | ||
2924 | struct btrfs_disk_key disk_key; | ||
2925 | |||
2926 | btrfs_node_key(parent, &disk_key, 0); | ||
2927 | wret = fixup_low_keys(trans, root, path, &disk_key, level + 1); | ||
2928 | if (wret) | ||
2929 | ret = wret; | ||
2930 | } | ||
2931 | btrfs_mark_buffer_dirty(parent); | ||
2932 | return ret; | ||
2933 | } | ||
2934 | |||
2935 | /* | ||
2936 | * delete the item at the leaf level in path. If that empties | ||
2937 | * the leaf, remove it from the tree | ||
2938 | */ | ||
2939 | int btrfs_del_items(struct btrfs_trans_handle *trans, struct btrfs_root *root, | ||
2940 | struct btrfs_path *path, int slot, int nr) | ||
2941 | { | ||
2942 | struct extent_buffer *leaf; | ||
2943 | struct btrfs_item *item; | ||
2944 | int last_off; | ||
2945 | int dsize = 0; | ||
2946 | int ret = 0; | ||
2947 | int wret; | ||
2948 | int i; | ||
2949 | u32 nritems; | ||
2950 | |||
2951 | leaf = path->nodes[0]; | ||
2952 | last_off = btrfs_item_offset_nr(leaf, slot + nr - 1); | ||
2953 | |||
2954 | for (i = 0; i < nr; i++) | ||
2955 | dsize += btrfs_item_size_nr(leaf, slot + i); | ||
2956 | |||
2957 | nritems = btrfs_header_nritems(leaf); | ||
2958 | |||
2959 | if (slot + nr != nritems) { | ||
2960 | int data_end = leaf_data_end(root, leaf); | ||
2961 | |||
2962 | memmove_extent_buffer(leaf, btrfs_leaf_data(leaf) + | ||
2963 | data_end + dsize, | ||
2964 | btrfs_leaf_data(leaf) + data_end, | ||
2965 | last_off - data_end); | ||
2966 | |||
2967 | for (i = slot + nr; i < nritems; i++) { | ||
2968 | u32 ioff; | ||
2969 | |||
2970 | item = btrfs_item_nr(leaf, i); | ||
2971 | if (!leaf->map_token) { | ||
2972 | map_extent_buffer(leaf, (unsigned long)item, | ||
2973 | sizeof(struct btrfs_item), | ||
2974 | &leaf->map_token, &leaf->kaddr, | ||
2975 | &leaf->map_start, &leaf->map_len, | ||
2976 | KM_USER1); | ||
2977 | } | ||
2978 | ioff = btrfs_item_offset(leaf, item); | ||
2979 | btrfs_set_item_offset(leaf, item, ioff + dsize); | ||
2980 | } | ||
2981 | |||
2982 | if (leaf->map_token) { | ||
2983 | unmap_extent_buffer(leaf, leaf->map_token, KM_USER1); | ||
2984 | leaf->map_token = NULL; | ||
2985 | } | ||
2986 | |||
2987 | memmove_extent_buffer(leaf, btrfs_item_nr_offset(slot), | ||
2988 | btrfs_item_nr_offset(slot + nr), | ||
2989 | sizeof(struct btrfs_item) * | ||
2990 | (nritems - slot - nr)); | ||
2991 | } | ||
2992 | btrfs_set_header_nritems(leaf, nritems - nr); | ||
2993 | nritems -= nr; | ||
2994 | |||
2995 | /* delete the leaf if we've emptied it */ | ||
2996 | if (nritems == 0) { | ||
2997 | if (leaf == root->node) { | ||
2998 | btrfs_set_header_level(leaf, 0); | ||
2999 | } else { | ||
3000 | u64 root_gen = btrfs_header_generation(path->nodes[1]); | ||
3001 | wret = del_ptr(trans, root, path, 1, path->slots[1]); | ||
3002 | if (wret) | ||
3003 | ret = wret; | ||
3004 | wret = btrfs_free_extent(trans, root, | ||
3005 | leaf->start, leaf->len, | ||
3006 | path->nodes[1]->start, | ||
3007 | btrfs_header_owner(path->nodes[1]), | ||
3008 | root_gen, 0, 0, 1); | ||
3009 | if (wret) | ||
3010 | ret = wret; | ||
3011 | } | ||
3012 | } else { | ||
3013 | int used = leaf_space_used(leaf, 0, nritems); | ||
3014 | if (slot == 0) { | ||
3015 | struct btrfs_disk_key disk_key; | ||
3016 | |||
3017 | btrfs_item_key(leaf, &disk_key, 0); | ||
3018 | wret = fixup_low_keys(trans, root, path, | ||
3019 | &disk_key, 1); | ||
3020 | if (wret) | ||
3021 | ret = wret; | ||
3022 | } | ||
3023 | |||
3024 | /* delete the leaf if it is mostly empty */ | ||
3025 | if (used < BTRFS_LEAF_DATA_SIZE(root) / 4) { | ||
3026 | /* push_leaf_left fixes the path. | ||
3027 | * make sure the path still points to our leaf | ||
3028 | * for possible call to del_ptr below | ||
3029 | */ | ||
3030 | slot = path->slots[1]; | ||
3031 | extent_buffer_get(leaf); | ||
3032 | |||
3033 | wret = push_leaf_left(trans, root, path, 1, 1); | ||
3034 | if (wret < 0 && wret != -ENOSPC) | ||
3035 | ret = wret; | ||
3036 | |||
3037 | if (path->nodes[0] == leaf && | ||
3038 | btrfs_header_nritems(leaf)) { | ||
3039 | wret = push_leaf_right(trans, root, path, 1, 1); | ||
3040 | if (wret < 0 && wret != -ENOSPC) | ||
3041 | ret = wret; | ||
3042 | } | ||
3043 | |||
3044 | if (btrfs_header_nritems(leaf) == 0) { | ||
3045 | u64 root_gen; | ||
3046 | u64 bytenr = leaf->start; | ||
3047 | u32 blocksize = leaf->len; | ||
3048 | |||
3049 | root_gen = btrfs_header_generation( | ||
3050 | path->nodes[1]); | ||
3051 | |||
3052 | wret = del_ptr(trans, root, path, 1, slot); | ||
3053 | if (wret) | ||
3054 | ret = wret; | ||
3055 | |||
3056 | free_extent_buffer(leaf); | ||
3057 | wret = btrfs_free_extent(trans, root, bytenr, | ||
3058 | blocksize, path->nodes[1]->start, | ||
3059 | btrfs_header_owner(path->nodes[1]), | ||
3060 | root_gen, 0, 0, 1); | ||
3061 | if (wret) | ||
3062 | ret = wret; | ||
3063 | } else { | ||
3064 | /* if we're still in the path, make sure | ||
3065 | * we're dirty. Otherwise, one of the | ||
3066 | * push_leaf functions must have already | ||
3067 | * dirtied this buffer | ||
3068 | */ | ||
3069 | if (path->nodes[0] == leaf) | ||
3070 | btrfs_mark_buffer_dirty(leaf); | ||
3071 | free_extent_buffer(leaf); | ||
3072 | } | ||
3073 | } else { | ||
3074 | btrfs_mark_buffer_dirty(leaf); | ||
3075 | } | ||
3076 | } | ||
3077 | return ret; | ||
3078 | } | ||
3079 | |||
3080 | /* | ||
3081 | * search the tree again to find a leaf with lesser keys | ||
3082 | * returns 0 if it found something or 1 if there are no lesser leaves. | ||
3083 | * returns < 0 on io errors. | ||
3084 | */ | ||
3085 | int btrfs_prev_leaf(struct btrfs_root *root, struct btrfs_path *path) | ||
3086 | { | ||
3087 | struct btrfs_key key; | ||
3088 | struct btrfs_disk_key found_key; | ||
3089 | int ret; | ||
3090 | |||
3091 | btrfs_item_key_to_cpu(path->nodes[0], &key, 0); | ||
3092 | |||
3093 | if (key.offset > 0) | ||
3094 | key.offset--; | ||
3095 | else if (key.type > 0) | ||
3096 | key.type--; | ||
3097 | else if (key.objectid > 0) | ||
3098 | key.objectid--; | ||
3099 | else | ||
3100 | return 1; | ||
3101 | |||
3102 | btrfs_release_path(root, path); | ||
3103 | ret = btrfs_search_slot(NULL, root, &key, path, 0, 0); | ||
3104 | if (ret < 0) | ||
3105 | return ret; | ||
3106 | btrfs_item_key(path->nodes[0], &found_key, 0); | ||
3107 | ret = comp_keys(&found_key, &key); | ||
3108 | if (ret < 0) | ||
3109 | return 0; | ||
3110 | return 1; | ||
3111 | } | ||
3112 | |||
3113 | /* | ||
3114 | * A helper function to walk down the tree starting at min_key, and looking | ||
3115 | * for nodes or leaves that are either in cache or have a minimum | ||
3116 | * transaction id. This is used by the btree defrag code, but could | ||
3117 | * also be used to search for blocks that have changed since a given | ||
3118 | * transaction id. | ||
3119 | * | ||
3120 | * This does not cow, but it does stuff the starting key it finds back | ||
3121 | * into min_key, so you can call btrfs_search_slot with cow=1 on the | ||
3122 | * key and get a writable path. | ||
3123 | * | ||
3124 | * This does lock as it descends, and path->keep_locks should be set | ||
3125 | * to 1 by the caller. | ||
3126 | * | ||
3127 | * This honors path->lowest_level to prevent descent past a given level | ||
3128 | * of the tree. | ||
3129 | * | ||
3130 | * returns zero if something useful was found, < 0 on error and 1 if there | ||
3131 | * was nothing in the tree that matched the search criteria. | ||
3132 | */ | ||
3133 | int btrfs_search_forward(struct btrfs_root *root, struct btrfs_key *min_key, | ||
3134 | struct btrfs_key *max_key, | ||
3135 | struct btrfs_path *path, int cache_only, | ||
3136 | u64 min_trans) | ||
3137 | { | ||
3138 | struct extent_buffer *cur; | ||
3139 | struct btrfs_key found_key; | ||
3140 | int slot; | ||
3141 | int sret; | ||
3142 | u32 nritems; | ||
3143 | int level; | ||
3144 | int ret = 1; | ||
3145 | |||
3146 | again: | ||
3147 | cur = btrfs_lock_root_node(root); | ||
3148 | level = btrfs_header_level(cur); | ||
3149 | WARN_ON(path->nodes[level]); | ||
3150 | path->nodes[level] = cur; | ||
3151 | path->locks[level] = 1; | ||
3152 | |||
3153 | if (btrfs_header_generation(cur) < min_trans) { | ||
3154 | ret = 1; | ||
3155 | goto out; | ||
3156 | } | ||
3157 | while(1) { | ||
3158 | nritems = btrfs_header_nritems(cur); | ||
3159 | level = btrfs_header_level(cur); | ||
3160 | sret = bin_search(cur, min_key, level, &slot); | ||
3161 | |||
3162 | /* at level = 0, we're done, setup the path and exit */ | ||
3163 | if (level == 0) { | ||
3164 | if (slot >= nritems) | ||
3165 | goto find_next_key; | ||
3166 | ret = 0; | ||
3167 | path->slots[level] = slot; | ||
3168 | btrfs_item_key_to_cpu(cur, &found_key, slot); | ||
3169 | goto out; | ||
3170 | } | ||
3171 | if (sret && slot > 0) | ||
3172 | slot--; | ||
3173 | /* | ||
3174 | * check this node pointer against the cache_only and | ||
3175 | * min_trans parameters. If it isn't in cache or is too | ||
3176 | * old, skip to the next one. | ||
3177 | */ | ||
3178 | while(slot < nritems) { | ||
3179 | u64 blockptr; | ||
3180 | u64 gen; | ||
3181 | struct extent_buffer *tmp; | ||
3182 | struct btrfs_disk_key disk_key; | ||
3183 | |||
3184 | blockptr = btrfs_node_blockptr(cur, slot); | ||
3185 | gen = btrfs_node_ptr_generation(cur, slot); | ||
3186 | if (gen < min_trans) { | ||
3187 | slot++; | ||
3188 | continue; | ||
3189 | } | ||
3190 | if (!cache_only) | ||
3191 | break; | ||
3192 | |||
3193 | if (max_key) { | ||
3194 | btrfs_node_key(cur, &disk_key, slot); | ||
3195 | if (comp_keys(&disk_key, max_key) >= 0) { | ||
3196 | ret = 1; | ||
3197 | goto out; | ||
3198 | } | ||
3199 | } | ||
3200 | |||
3201 | tmp = btrfs_find_tree_block(root, blockptr, | ||
3202 | btrfs_level_size(root, level - 1)); | ||
3203 | |||
3204 | if (tmp && btrfs_buffer_uptodate(tmp, gen)) { | ||
3205 | free_extent_buffer(tmp); | ||
3206 | break; | ||
3207 | } | ||
3208 | if (tmp) | ||
3209 | free_extent_buffer(tmp); | ||
3210 | slot++; | ||
3211 | } | ||
3212 | find_next_key: | ||
3213 | /* | ||
3214 | * we didn't find a candidate key in this node, walk forward | ||
3215 | * and find another one | ||
3216 | */ | ||
3217 | if (slot >= nritems) { | ||
3218 | path->slots[level] = slot; | ||
3219 | sret = btrfs_find_next_key(root, path, min_key, level, | ||
3220 | cache_only, min_trans); | ||
3221 | if (sret == 0) { | ||
3222 | btrfs_release_path(root, path); | ||
3223 | goto again; | ||
3224 | } else { | ||
3225 | goto out; | ||
3226 | } | ||
3227 | } | ||
3228 | /* save our key for returning back */ | ||
3229 | btrfs_node_key_to_cpu(cur, &found_key, slot); | ||
3230 | path->slots[level] = slot; | ||
3231 | if (level == path->lowest_level) { | ||
3232 | ret = 0; | ||
3233 | unlock_up(path, level, 1); | ||
3234 | goto out; | ||
3235 | } | ||
3236 | cur = read_node_slot(root, cur, slot); | ||
3237 | |||
3238 | btrfs_tree_lock(cur); | ||
3239 | path->locks[level - 1] = 1; | ||
3240 | path->nodes[level - 1] = cur; | ||
3241 | unlock_up(path, level, 1); | ||
3242 | } | ||
3243 | out: | ||
3244 | if (ret == 0) | ||
3245 | memcpy(min_key, &found_key, sizeof(found_key)); | ||
3246 | return ret; | ||
3247 | } | ||
3248 | |||
3249 | /* | ||
3250 | * this is similar to btrfs_next_leaf, but does not try to preserve | ||
3251 | * and fixup the path. It looks for and returns the next key in the | ||
3252 | * tree based on the current path and the cache_only and min_trans | ||
3253 | * parameters. | ||
3254 | * | ||
3255 | * 0 is returned if another key is found, < 0 if there are any errors | ||
3256 | * and 1 is returned if there are no higher keys in the tree | ||
3257 | * | ||
3258 | * path->keep_locks should be set to 1 on the search made before | ||
3259 | * calling this function. | ||
3260 | */ | ||
3261 | int btrfs_find_next_key(struct btrfs_root *root, struct btrfs_path *path, | ||
3262 | struct btrfs_key *key, int lowest_level, | ||
3263 | int cache_only, u64 min_trans) | ||
3264 | { | ||
3265 | int level = lowest_level; | ||
3266 | int slot; | ||
3267 | struct extent_buffer *c; | ||
3268 | |||
3269 | while(level < BTRFS_MAX_LEVEL) { | ||
3270 | if (!path->nodes[level]) | ||
3271 | return 1; | ||
3272 | |||
3273 | slot = path->slots[level] + 1; | ||
3274 | c = path->nodes[level]; | ||
3275 | next: | ||
3276 | if (slot >= btrfs_header_nritems(c)) { | ||
3277 | level++; | ||
3278 | if (level == BTRFS_MAX_LEVEL) { | ||
3279 | return 1; | ||
3280 | } | ||
3281 | continue; | ||
3282 | } | ||
3283 | if (level == 0) | ||
3284 | btrfs_item_key_to_cpu(c, key, slot); | ||
3285 | else { | ||
3286 | u64 blockptr = btrfs_node_blockptr(c, slot); | ||
3287 | u64 gen = btrfs_node_ptr_generation(c, slot); | ||
3288 | |||
3289 | if (cache_only) { | ||
3290 | struct extent_buffer *cur; | ||
3291 | cur = btrfs_find_tree_block(root, blockptr, | ||
3292 | btrfs_level_size(root, level - 1)); | ||
3293 | if (!cur || !btrfs_buffer_uptodate(cur, gen)) { | ||
3294 | slot++; | ||
3295 | if (cur) | ||
3296 | free_extent_buffer(cur); | ||
3297 | goto next; | ||
3298 | } | ||
3299 | free_extent_buffer(cur); | ||
3300 | } | ||
3301 | if (gen < min_trans) { | ||
3302 | slot++; | ||
3303 | goto next; | ||
3304 | } | ||
3305 | btrfs_node_key_to_cpu(c, key, slot); | ||
3306 | } | ||
3307 | return 0; | ||
3308 | } | ||
3309 | return 1; | ||
3310 | } | ||
3311 | |||
3312 | /* | ||
3313 | * search the tree again to find a leaf with greater keys | ||
3314 | * returns 0 if it found something or 1 if there are no greater leaves. | ||
3315 | * returns < 0 on io errors. | ||
3316 | */ | ||
3317 | int btrfs_next_leaf(struct btrfs_root *root, struct btrfs_path *path) | ||
3318 | { | ||
3319 | int slot; | ||
3320 | int level = 1; | ||
3321 | struct extent_buffer *c; | ||
3322 | struct extent_buffer *next = NULL; | ||
3323 | struct btrfs_key key; | ||
3324 | u32 nritems; | ||
3325 | int ret; | ||
3326 | |||
3327 | nritems = btrfs_header_nritems(path->nodes[0]); | ||
3328 | if (nritems == 0) { | ||
3329 | return 1; | ||
3330 | } | ||
3331 | |||
3332 | btrfs_item_key_to_cpu(path->nodes[0], &key, nritems - 1); | ||
3333 | |||
3334 | btrfs_release_path(root, path); | ||
3335 | path->keep_locks = 1; | ||
3336 | ret = btrfs_search_slot(NULL, root, &key, path, 0, 0); | ||
3337 | path->keep_locks = 0; | ||
3338 | |||
3339 | if (ret < 0) | ||
3340 | return ret; | ||
3341 | |||
3342 | nritems = btrfs_header_nritems(path->nodes[0]); | ||
3343 | /* | ||
3344 | * by releasing the path above we dropped all our locks. A balance | ||
3345 | * could have added more items next to the key that used to be | ||
3346 | * at the very end of the block. So, check again here and | ||
3347 | * advance the path if there are now more items available. | ||
3348 | */ | ||
3349 | if (nritems > 0 && path->slots[0] < nritems - 1) { | ||
3350 | path->slots[0]++; | ||
3351 | goto done; | ||
3352 | } | ||
3353 | |||
3354 | while(level < BTRFS_MAX_LEVEL) { | ||
3355 | if (!path->nodes[level]) | ||
3356 | return 1; | ||
3357 | |||
3358 | slot = path->slots[level] + 1; | ||
3359 | c = path->nodes[level]; | ||
3360 | if (slot >= btrfs_header_nritems(c)) { | ||
3361 | level++; | ||
3362 | if (level == BTRFS_MAX_LEVEL) { | ||
3363 | return 1; | ||
3364 | } | ||
3365 | continue; | ||
3366 | } | ||
3367 | |||
3368 | if (next) { | ||
3369 | btrfs_tree_unlock(next); | ||
3370 | free_extent_buffer(next); | ||
3371 | } | ||
3372 | |||
3373 | if (level == 1 && (path->locks[1] || path->skip_locking) && | ||
3374 | path->reada) | ||
3375 | reada_for_search(root, path, level, slot, 0); | ||
3376 | |||
3377 | next = read_node_slot(root, c, slot); | ||
3378 | if (!path->skip_locking) { | ||
3379 | WARN_ON(!btrfs_tree_locked(c)); | ||
3380 | btrfs_tree_lock(next); | ||
3381 | } | ||
3382 | break; | ||
3383 | } | ||
3384 | path->slots[level] = slot; | ||
3385 | while(1) { | ||
3386 | level--; | ||
3387 | c = path->nodes[level]; | ||
3388 | if (path->locks[level]) | ||
3389 | btrfs_tree_unlock(c); | ||
3390 | free_extent_buffer(c); | ||
3391 | path->nodes[level] = next; | ||
3392 | path->slots[level] = 0; | ||
3393 | if (!path->skip_locking) | ||
3394 | path->locks[level] = 1; | ||
3395 | if (!level) | ||
3396 | break; | ||
3397 | if (level == 1 && path->locks[1] && path->reada) | ||
3398 | reada_for_search(root, path, level, slot, 0); | ||
3399 | next = read_node_slot(root, next, 0); | ||
3400 | if (!path->skip_locking) { | ||
3401 | WARN_ON(!btrfs_tree_locked(path->nodes[level])); | ||
3402 | btrfs_tree_lock(next); | ||
3403 | } | ||
3404 | } | ||
3405 | done: | ||
3406 | unlock_up(path, 0, 1); | ||
3407 | return 0; | ||
3408 | } | ||
3409 | |||
3410 | /* | ||
3411 | * this uses btrfs_prev_leaf to walk backwards in the tree, and keeps | ||
3412 | * searching until it gets past min_objectid or finds an item of 'type' | ||
3413 | * | ||
3414 | * returns 0 if something is found, 1 if nothing was found and < 0 on error | ||
3415 | */ | ||
3416 | int btrfs_previous_item(struct btrfs_root *root, | ||
3417 | struct btrfs_path *path, u64 min_objectid, | ||
3418 | int type) | ||
3419 | { | ||
3420 | struct btrfs_key found_key; | ||
3421 | struct extent_buffer *leaf; | ||
3422 | u32 nritems; | ||
3423 | int ret; | ||
3424 | |||
3425 | while(1) { | ||
3426 | if (path->slots[0] == 0) { | ||
3427 | ret = btrfs_prev_leaf(root, path); | ||
3428 | if (ret != 0) | ||
3429 | return ret; | ||
3430 | } else { | ||
3431 | path->slots[0]--; | ||
3432 | } | ||
3433 | leaf = path->nodes[0]; | ||
3434 | nritems = btrfs_header_nritems(leaf); | ||
3435 | if (nritems == 0) | ||
3436 | return 1; | ||
3437 | if (path->slots[0] == nritems) | ||
3438 | path->slots[0]--; | ||
3439 | |||
3440 | btrfs_item_key_to_cpu(leaf, &found_key, path->slots[0]); | ||
3441 | if (found_key.type == type) | ||
3442 | return 0; | ||
3443 | if (found_key.objectid < min_objectid) | ||
3444 | break; | ||
3445 | if (found_key.objectid == min_objectid && | ||
3446 | found_key.type < type) | ||
3447 | break; | ||
3448 | } | ||
3449 | return 1; | ||
3450 | } | ||