projects / GitHub / mt8127 / android_kernel_alcatel_ttab.git / blame
? search:
summary | shortlog | log | commit | commitdiff | tree
blob | blame (incremental) | history | HEAD
Btrfs: remove dead code
[GitHub/mt8127/android_kernel_alcatel_ttab.git] / fs / btrfs / ctree.c
CommitLineData
6cbd5570 1/*
d352ac68 2 * Copyright (C) 2007,2008 Oracle. All rights reserved.
6cbd5570
CM		 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
a6b6e75e 19#include <linux/sched.h>
eb60ceac
CM		 20#include "ctree.h"
21#include "disk-io.h"
7f5c1516 22#include "transaction.h"
5f39d397 23#include "print-tree.h"
925baedd 24#include "locking.h"
9a8dd150 25
e089f05c
CM		 26static int split_node(struct btrfs_trans_handle *trans, struct btrfs_root
27 *root, struct btrfs_path *path, int level);
28static int split_leaf(struct btrfs_trans_handle *trans, struct btrfs_root
d4dbff95 29 *root, struct btrfs_key *ins_key,
cc0c5538 30 struct btrfs_path *path, int data_size, int extend);
5f39d397
CM		 31static int push_node_left(struct btrfs_trans_handle *trans,
32 struct btrfs_root *root, struct extent_buffer *dst,
971a1f66 33 struct extent_buffer *src, int empty);
5f39d397
CM		 34static 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);
e089f05c
CM		 38static int del_ptr(struct btrfs_trans_handle *trans, struct btrfs_root *root,
39 struct btrfs_path *path, int level, int slot);
d97e63b6 40
df24a2b9 41struct btrfs_path *btrfs_alloc_path(void)
2c90e5d6 42{
df24a2b9 43 struct btrfs_path *path;
e00f7308
JM		 44 path = kmem_cache_zalloc(btrfs_path_cachep, GFP_NOFS);
45 if (path)
2cc58cf2 46 path->reada = 1;
df24a2b9 47 return path;
2c90e5d6
CM		 48}
49
b4ce94de
CM		 50/*
51 * set all locked nodes in the path to blocking locks. This should
52 * be done before scheduling
53 */
54noinline void btrfs_set_path_blocking(struct btrfs_path *p)
55{
56 int i;
57 for (i = 0; i < BTRFS_MAX_LEVEL; i++) {
58 if (p->nodes[i] && p->locks[i])
59 btrfs_set_lock_blocking(p->nodes[i]);
60 }
61}
62
63/*
64 * reset all the locked nodes in the patch to spinning locks.
4008c04a
CM		 65 *
66 * held is used to keep lockdep happy, when lockdep is enabled
67 * we set held to a blocking lock before we go around and
68 * retake all the spinlocks in the path. You can safely use NULL
69 * for held
b4ce94de 70 */
4008c04a
CM		 71noinline void btrfs_clear_path_blocking(struct btrfs_path *p,
72 struct extent_buffer *held)
b4ce94de
CM		 73{
74 int i;
4008c04a
CM		 75
76#ifdef CONFIG_DEBUG_LOCK_ALLOC
77 /* lockdep really cares that we take all of these spinlocks
78 * in the right order. If any of the locks in the path are not
79 * currently blocking, it is going to complain. So, make really
80 * really sure by forcing the path to blocking before we clear
81 * the path blocking.
82 */
83 if (held)
84 btrfs_set_lock_blocking(held);
85 btrfs_set_path_blocking(p);
86#endif
87
88 for (i = BTRFS_MAX_LEVEL - 1; i >= 0; i--) {
b4ce94de
CM		 89 if (p->nodes[i] && p->locks[i])
90 btrfs_clear_lock_blocking(p->nodes[i]);
91 }
4008c04a
CM		 92
93#ifdef CONFIG_DEBUG_LOCK_ALLOC
94 if (held)
95 btrfs_clear_lock_blocking(held);
96#endif
b4ce94de
CM		 97}
98
d352ac68 99/* this also releases the path */
df24a2b9 100void btrfs_free_path(struct btrfs_path *p)
be0e5c09 101{
df24a2b9
CM		 102 btrfs_release_path(NULL, p);
103 kmem_cache_free(btrfs_path_cachep, p);
be0e5c09
CM		 104}
105
d352ac68
CM		 106/*
107 * path release drops references on the extent buffers in the path
108 * and it drops any locks held by this path
109 *
110 * It is safe to call this on paths that no locks or extent buffers held.
111 */
d397712b 112noinline void btrfs_release_path(struct btrfs_root *root, struct btrfs_path *p)
eb60ceac
CM		 113{
114 int i;
a2135011 115
234b63a0 116 for (i = 0; i < BTRFS_MAX_LEVEL; i++) {
3f157a2f 117 p->slots[i] = 0;
eb60ceac 118 if (!p->nodes[i])
925baedd
CM		 119 continue;
120 if (p->locks[i]) {
121 btrfs_tree_unlock(p->nodes[i]);
122 p->locks[i] = 0;
123 }
5f39d397 124 free_extent_buffer(p->nodes[i]);
3f157a2f 125 p->nodes[i] = NULL;
eb60ceac
CM		 126 }
127}
128
d352ac68
CM		 129/*
130 * safely gets a reference on the root node of a tree. A lock
131 * is not taken, so a concurrent writer may put a different node
132 * at the root of the tree. See btrfs_lock_root_node for the
133 * looping required.
134 *
135 * The extent buffer returned by this has a reference taken, so
136 * it won't disappear. It may stop being the root of the tree
137 * at any time because there are no locks held.
138 */
925baedd
CM		 139struct extent_buffer *btrfs_root_node(struct btrfs_root *root)
140{
141 struct extent_buffer *eb;
142 spin_lock(&root->node_lock);
143 eb = root->node;
144 extent_buffer_get(eb);
145 spin_unlock(&root->node_lock);
146 return eb;
147}
148
d352ac68
CM		 149/* loop around taking references on and locking the root node of the
150 * tree until you end up with a lock on the root. A locked buffer
151 * is returned, with a reference held.
152 */
925baedd
CM		 153struct extent_buffer *btrfs_lock_root_node(struct btrfs_root *root)
154{
155 struct extent_buffer *eb;
156
d397712b 157 while (1) {
925baedd
CM		 158 eb = btrfs_root_node(root);
159 btrfs_tree_lock(eb);
160
161 spin_lock(&root->node_lock);
162 if (eb == root->node) {
163 spin_unlock(&root->node_lock);
164 break;
165 }
166 spin_unlock(&root->node_lock);
167
168 btrfs_tree_unlock(eb);
169 free_extent_buffer(eb);
170 }
171 return eb;
172}
173
d352ac68
CM		 174/* cowonly root (everything not a reference counted cow subvolume), just get
175 * put onto a simple dirty list. transaction.c walks this to make sure they
176 * get properly updated on disk.
177 */
0b86a832
CM		 178static void add_root_to_dirty_list(struct btrfs_root *root)
179{
180 if (root->track_dirty && list_empty(&root->dirty_list)) {
181 list_add(&root->dirty_list,
182 &root->fs_info->dirty_cowonly_roots);
183 }
184}
185
d352ac68
CM		 186/*
187 * used by snapshot creation to make a copy of a root for a tree with
188 * a given objectid. The buffer with the new root node is returned in
189 * cow_ret, and this func returns zero on success or a negative error code.
190 */
be20aa9d
CM		 191int btrfs_copy_root(struct btrfs_trans_handle *trans,
192 struct btrfs_root *root,
193 struct extent_buffer *buf,
194 struct extent_buffer **cow_ret, u64 new_root_objectid)
195{
196 struct extent_buffer *cow;
197 u32 nritems;
198 int ret = 0;
199 int level;
4aec2b52 200 struct btrfs_root *new_root;
be20aa9d 201
4aec2b52
CM		 202 new_root = kmalloc(sizeof(*new_root), GFP_NOFS);
203 if (!new_root)
204 return -ENOMEM;
205
206 memcpy(new_root, root, sizeof(*new_root));
207 new_root->root_key.objectid = new_root_objectid;
be20aa9d
CM		 208
209 WARN_ON(root->ref_cows && trans->transid !=
210 root->fs_info->running_transaction->transid);
211 WARN_ON(root->ref_cows && trans->transid != root->last_trans);
212
213 level = btrfs_header_level(buf);
214 nritems = btrfs_header_nritems(buf);
31840ae1
ZY		 215
216 cow = btrfs_alloc_free_block(trans, new_root, buf->len, 0,
217 new_root_objectid, trans->transid,
218 level, buf->start, 0);
4aec2b52
CM		 219 if (IS_ERR(cow)) {
220 kfree(new_root);
be20aa9d 221 return PTR_ERR(cow);
4aec2b52 222 }
be20aa9d
CM		 223
224 copy_extent_buffer(cow, buf, 0, 0, cow->len);
225 btrfs_set_header_bytenr(cow, cow->start);
226 btrfs_set_header_generation(cow, trans->transid);
227 btrfs_set_header_owner(cow, new_root_objectid);
63b10fc4 228 btrfs_clear_header_flag(cow, BTRFS_HEADER_FLAG_WRITTEN);
be20aa9d 229
2b82032c
YZ		 230 write_extent_buffer(cow, root->fs_info->fsid,
231 (unsigned long)btrfs_header_fsid(cow),
232 BTRFS_FSID_SIZE);
233
be20aa9d 234 WARN_ON(btrfs_header_generation(buf) > trans->transid);
31840ae1 235 ret = btrfs_inc_ref(trans, new_root, buf, cow, NULL);
4aec2b52
CM		 236 kfree(new_root);
237
be20aa9d
CM		 238 if (ret)
239 return ret;
240
241 btrfs_mark_buffer_dirty(cow);
242 *cow_ret = cow;
243 return 0;
244}
245
d352ac68 246/*
d397712b
CM		 247 * does the dirty work in cow of a single block. The parent block (if
248 * supplied) is updated to point to the new cow copy. The new buffer is marked
249 * dirty and returned locked. If you modify the block it needs to be marked
250 * dirty again.
d352ac68
CM		 251 *
252 * search_start -- an allocation hint for the new block
253 *
d397712b
CM		 254 * empty_size -- a hint that you plan on doing more cow. This is the size in
255 * bytes the allocator should try to find free next to the block it returns.
256 * This is just a hint and may be ignored by the allocator.
d352ac68 257 */
d397712b 258static noinline int __btrfs_cow_block(struct btrfs_trans_handle *trans,
5f39d397
CM		 259 struct btrfs_root *root,
260 struct extent_buffer *buf,
261 struct extent_buffer *parent, int parent_slot,
262 struct extent_buffer **cow_ret,
9fa8cfe7 263 u64 search_start, u64 empty_size)
02217ed2 264{
31840ae1 265 u64 parent_start;
5f39d397 266 struct extent_buffer *cow;
7bb86316 267 u32 nritems;
6702ed49 268 int ret = 0;
7bb86316 269 int level;
925baedd 270 int unlock_orig = 0;
7bb86316 271
925baedd
CM		 272 if (*cow_ret == buf)
273 unlock_orig = 1;
274
b9447ef8 275 btrfs_assert_tree_locked(buf);
925baedd 276
31840ae1
ZY		 277 if (parent)
278 parent_start = parent->start;
279 else
280 parent_start = 0;
281
7bb86316
CM		 282 WARN_ON(root->ref_cows && trans->transid !=
283 root->fs_info->running_transaction->transid);
6702ed49 284 WARN_ON(root->ref_cows && trans->transid != root->last_trans);
5f39d397 285
7bb86316
CM		 286 level = btrfs_header_level(buf);
287 nritems = btrfs_header_nritems(buf);
31840ae1 288
9fa8cfe7
CM		 289 cow = btrfs_alloc_free_block(trans, root, buf->len,
290 parent_start, root->root_key.objectid,
291 trans->transid, level,
292 search_start, empty_size);
54aa1f4d
CM		 293 if (IS_ERR(cow))
294 return PTR_ERR(cow);
6702ed49 295
b4ce94de
CM		 296 /* cow is set to blocking by btrfs_init_new_buffer */
297
5f39d397 298 copy_extent_buffer(cow, buf, 0, 0, cow->len);
db94535d 299 btrfs_set_header_bytenr(cow, cow->start);
5f39d397
CM		 300 btrfs_set_header_generation(cow, trans->transid);
301 btrfs_set_header_owner(cow, root->root_key.objectid);
63b10fc4 302 btrfs_clear_header_flag(cow, BTRFS_HEADER_FLAG_WRITTEN);
6702ed49 303
2b82032c
YZ		 304 write_extent_buffer(cow, root->fs_info->fsid,
305 (unsigned long)btrfs_header_fsid(cow),
306 BTRFS_FSID_SIZE);
307
5f39d397
CM		 308 WARN_ON(btrfs_header_generation(buf) > trans->transid);
309 if (btrfs_header_generation(buf) != trans->transid) {
31840ae1 310 u32 nr_extents;
31840ae1 311 ret = btrfs_inc_ref(trans, root, buf, cow, &nr_extents);
6702ed49
CM		 312 if (ret)
313 return ret;
31840ae1
ZY		 314
315 ret = btrfs_cache_ref(trans, root, buf, nr_extents);
316 WARN_ON(ret);
1a40e23b
ZY		 317 } else if (btrfs_header_owner(buf) == BTRFS_TREE_RELOC_OBJECTID) {
318 /*
319 * There are only two places that can drop reference to
320 * tree blocks owned by living reloc trees, one is here,
f82d02d9 321 * the other place is btrfs_drop_subtree. In both places,
1a40e23b
ZY		 322 * we check reference count while tree block is locked.
323 * Furthermore, if reference count is one, it won't get
324 * increased by someone else.
325 */
326 u32 refs;
327 ret = btrfs_lookup_extent_ref(trans, root, buf->start,
328 buf->len, &refs);
329 BUG_ON(ret);
330 if (refs == 1) {
331 ret = btrfs_update_ref(trans, root, buf, cow,
332 0, nritems);
333 clean_tree_block(trans, root, buf);
334 } else {
335 ret = btrfs_inc_ref(trans, root, buf, cow, NULL);
336 }
337 BUG_ON(ret);
6702ed49 338 } else {
31840ae1
ZY		 339 ret = btrfs_update_ref(trans, root, buf, cow, 0, nritems);
340 if (ret)
341 return ret;
6702ed49
CM		 342 clean_tree_block(trans, root, buf);
343 }
344
1a40e23b 345 if (root->root_key.objectid == BTRFS_TREE_RELOC_OBJECTID) {
1a40e23b
ZY		 346 ret = btrfs_reloc_tree_cache_ref(trans, root, cow, buf->start);
347 WARN_ON(ret);
348 }
349
02217ed2 350 if (buf == root->node) {
925baedd 351 WARN_ON(parent && parent != buf);
925baedd
CM		 352
353 spin_lock(&root->node_lock);
02217ed2 354 root->node = cow;
5f39d397 355 extent_buffer_get(cow);
925baedd
CM		 356 spin_unlock(&root->node_lock);
357
2c90e5d6 358 if (buf != root->commit_root) {
db94535d 359 btrfs_free_extent(trans, root, buf->start,
31840ae1
ZY		 360 buf->len, buf->start,
361 root->root_key.objectid,
362 btrfs_header_generation(buf),
3bb1a1bc 363 level, 1);
2c90e5d6 364 }
5f39d397 365 free_extent_buffer(buf);
0b86a832 366 add_root_to_dirty_list(root);
02217ed2 367 } else {
5f39d397 368 btrfs_set_node_blockptr(parent, parent_slot,
db94535d 369 cow->start);
74493f7a
CM		 370 WARN_ON(trans->transid == 0);
371 btrfs_set_node_ptr_generation(parent, parent_slot,
372 trans->transid);
d6025579 373 btrfs_mark_buffer_dirty(parent);
5f39d397 374 WARN_ON(btrfs_header_generation(parent) != trans->transid);
7bb86316 375 btrfs_free_extent(trans, root, buf->start, buf->len,
31840ae1 376 parent_start, btrfs_header_owner(parent),
3bb1a1bc 377 btrfs_header_generation(parent), level, 1);
02217ed2 378 }
925baedd
CM		 379 if (unlock_orig)
380 btrfs_tree_unlock(buf);
5f39d397 381 free_extent_buffer(buf);
ccd467d6 382 btrfs_mark_buffer_dirty(cow);
2c90e5d6 383 *cow_ret = cow;
02217ed2
CM		 384 return 0;
385}
386
d352ac68
CM		 387/*
388 * cows a single block, see __btrfs_cow_block for the real work.
389 * This version of it has extra checks so that a block isn't cow'd more than
390 * once per transaction, as long as it hasn't been written yet
391 */
d397712b 392noinline int btrfs_cow_block(struct btrfs_trans_handle *trans,
5f39d397
CM		 393 struct btrfs_root *root, struct extent_buffer *buf,
394 struct extent_buffer *parent, int parent_slot,
9fa8cfe7 395 struct extent_buffer **cow_ret)
6702ed49
CM		 396{
397 u64 search_start;
f510cfec 398 int ret;
dc17ff8f 399
6702ed49 400 if (trans->transaction != root->fs_info->running_transaction) {
d397712b
CM		 401 printk(KERN_CRIT "trans %llu running %llu\n",
402 (unsigned long long)trans->transid,
403 (unsigned long long)
6702ed49
CM		 404 root->fs_info->running_transaction->transid);
405 WARN_ON(1);
406 }
407 if (trans->transid != root->fs_info->generation) {
d397712b
CM		 408 printk(KERN_CRIT "trans %llu running %llu\n",
409 (unsigned long long)trans->transid,
410 (unsigned long long)root->fs_info->generation);
6702ed49
CM		 411 WARN_ON(1);
412 }
dc17ff8f 413
5b21f2ed
ZY		 414 if (btrfs_header_generation(buf) == trans->transid &&
415 btrfs_header_owner(buf) == root->root_key.objectid &&
63b10fc4 416 !btrfs_header_flag(buf, BTRFS_HEADER_FLAG_WRITTEN)) {
6702ed49
CM		 417 *cow_ret = buf;
418 return 0;
419 }
c487685d 420
0b86a832 421 search_start = buf->start & ~((u64)(1024 * 1024 * 1024) - 1);
b4ce94de
CM		 422
423 if (parent)
424 btrfs_set_lock_blocking(parent);
425 btrfs_set_lock_blocking(buf);
426
f510cfec 427 ret = __btrfs_cow_block(trans, root, buf, parent,
9fa8cfe7 428 parent_slot, cow_ret, search_start, 0);
f510cfec 429 return ret;
6702ed49
CM		 430}
431
d352ac68
CM		 432/*
433 * helper function for defrag to decide if two blocks pointed to by a
434 * node are actually close by
435 */
6b80053d 436static int close_blocks(u64 blocknr, u64 other, u32 blocksize)
6702ed49 437{
6b80053d 438 if (blocknr < other && other - (blocknr + blocksize) < 32768)
6702ed49 439 return 1;
6b80053d 440 if (blocknr > other && blocknr - (other + blocksize) < 32768)
6702ed49
CM		 441 return 1;
442 return 0;
443}
444
081e9573
CM		 445/*
446 * compare two keys in a memcmp fashion
447 */
448static int comp_keys(struct btrfs_disk_key *disk, struct btrfs_key *k2)
449{
450 struct btrfs_key k1;
451
452 btrfs_disk_key_to_cpu(&k1, disk);
453
454 if (k1.objectid > k2->objectid)
455 return 1;
456 if (k1.objectid < k2->objectid)
457 return -1;
458 if (k1.type > k2->type)
459 return 1;
460 if (k1.type < k2->type)
461 return -1;
462 if (k1.offset > k2->offset)
463 return 1;
464 if (k1.offset < k2->offset)
465 return -1;
466 return 0;
467}
468
f3465ca4
JB		 469/*
470 * same as comp_keys only with two btrfs_key's
471 */
472static int comp_cpu_keys(struct btrfs_key *k1, struct btrfs_key *k2)
473{
474 if (k1->objectid > k2->objectid)
475 return 1;
476 if (k1->objectid < k2->objectid)
477 return -1;
478 if (k1->type > k2->type)
479 return 1;
480 if (k1->type < k2->type)
481 return -1;
482 if (k1->offset > k2->offset)
483 return 1;
484 if (k1->offset < k2->offset)
485 return -1;
486 return 0;
487}
081e9573 488
d352ac68
CM		 489/*
490 * this is used by the defrag code to go through all the
491 * leaves pointed to by a node and reallocate them so that
492 * disk order is close to key order
493 */
6702ed49 494int btrfs_realloc_node(struct btrfs_trans_handle *trans,
5f39d397 495 struct btrfs_root *root, struct extent_buffer *parent,
a6b6e75e
CM		 496 int start_slot, int cache_only, u64 *last_ret,
497 struct btrfs_key *progress)
6702ed49 498{
6b80053d 499 struct extent_buffer *cur;
6702ed49 500 u64 blocknr;
ca7a79ad 501 u64 gen;
e9d0b13b
CM		 502 u64 search_start = *last_ret;
503 u64 last_block = 0;
6702ed49
CM		 504 u64 other;
505 u32 parent_nritems;
6702ed49
CM		 506 int end_slot;
507 int i;
508 int err = 0;
f2183bde 509 int parent_level;
6b80053d
CM		 510 int uptodate;
511 u32 blocksize;
081e9573
CM		 512 int progress_passed = 0;
513 struct btrfs_disk_key disk_key;
6702ed49 514
5708b959
CM		 515 parent_level = btrfs_header_level(parent);
516 if (cache_only && parent_level != 1)
517 return 0;
518
d397712b 519 if (trans->transaction != root->fs_info->running_transaction)
6702ed49 520 WARN_ON(1);
d397712b 521 if (trans->transid != root->fs_info->generation)
6702ed49 522 WARN_ON(1);
86479a04 523
6b80053d 524 parent_nritems = btrfs_header_nritems(parent);
6b80053d 525 blocksize = btrfs_level_size(root, parent_level - 1);
6702ed49
CM		 526 end_slot = parent_nritems;
527
528 if (parent_nritems == 1)
529 return 0;
530
b4ce94de
CM		 531 btrfs_set_lock_blocking(parent);
532
6702ed49
CM		 533 for (i = start_slot; i < end_slot; i++) {
534 int close = 1;
a6b6e75e 535
5708b959
CM		 536 if (!parent->map_token) {
537 map_extent_buffer(parent,
538 btrfs_node_key_ptr_offset(i),
539 sizeof(struct btrfs_key_ptr),
540 &parent->map_token, &parent->kaddr,
541 &parent->map_start, &parent->map_len,
542 KM_USER1);
543 }
081e9573
CM		 544 btrfs_node_key(parent, &disk_key, i);
545 if (!progress_passed && comp_keys(&disk_key, progress) < 0)
546 continue;
547
548 progress_passed = 1;
6b80053d 549 blocknr = btrfs_node_blockptr(parent, i);
ca7a79ad 550 gen = btrfs_node_ptr_generation(parent, i);
e9d0b13b
CM		 551 if (last_block == 0)
552 last_block = blocknr;
5708b959 553
6702ed49 554 if (i > 0) {
6b80053d
CM		 555 other = btrfs_node_blockptr(parent, i - 1);
556 close = close_blocks(blocknr, other, blocksize);
6702ed49 557 }
0ef3e66b 558 if (!close && i < end_slot - 2) {
6b80053d
CM		 559 other = btrfs_node_blockptr(parent, i + 1);
560 close = close_blocks(blocknr, other, blocksize);
6702ed49 561 }
e9d0b13b
CM		 562 if (close) {
563 last_block = blocknr;
6702ed49 564 continue;
e9d0b13b 565 }
5708b959
CM		 566 if (parent->map_token) {
567 unmap_extent_buffer(parent, parent->map_token,
568 KM_USER1);
569 parent->map_token = NULL;
570 }
6702ed49 571
6b80053d
CM		 572 cur = btrfs_find_tree_block(root, blocknr, blocksize);
573 if (cur)
1259ab75 574 uptodate = btrfs_buffer_uptodate(cur, gen);
6b80053d
CM		 575 else
576 uptodate = 0;
5708b959 577 if (!cur || !uptodate) {
6702ed49 578 if (cache_only) {
6b80053d 579 free_extent_buffer(cur);
6702ed49
CM		 580 continue;
581 }
6b80053d
CM		 582 if (!cur) {
583 cur = read_tree_block(root, blocknr,
ca7a79ad 584 blocksize, gen);
6b80053d 585 } else if (!uptodate) {
ca7a79ad 586 btrfs_read_buffer(cur, gen);
f2183bde 587 }
6702ed49 588 }
e9d0b13b 589 if (search_start == 0)
6b80053d 590 search_start = last_block;
e9d0b13b 591
e7a84565 592 btrfs_tree_lock(cur);
b4ce94de 593 btrfs_set_lock_blocking(cur);
6b80053d 594 err = __btrfs_cow_block(trans, root, cur, parent, i,
e7a84565 595 &cur, search_start,
6b80053d 596 min(16 * blocksize,
9fa8cfe7 597 (end_slot - i) * blocksize));
252c38f0 598 if (err) {
e7a84565 599 btrfs_tree_unlock(cur);
6b80053d 600 free_extent_buffer(cur);
6702ed49 601 break;
252c38f0 602 }
e7a84565
CM		 603 search_start = cur->start;
604 last_block = cur->start;
f2183bde 605 *last_ret = search_start;
e7a84565
CM		 606 btrfs_tree_unlock(cur);
607 free_extent_buffer(cur);
6702ed49 608 }
5708b959
CM		 609 if (parent->map_token) {
610 unmap_extent_buffer(parent, parent->map_token,
611 KM_USER1);
612 parent->map_token = NULL;
613 }
6702ed49
CM		 614 return err;
615}
616
74123bd7
CM		 617/*
618 * The leaf data grows from end-to-front in the node.
619 * this returns the address of the start of the last item,
620 * which is the stop of the leaf data stack
621 */
123abc88 622static inline unsigned int leaf_data_end(struct btrfs_root *root,
5f39d397 623 struct extent_buffer *leaf)
be0e5c09 624{
5f39d397 625 u32 nr = btrfs_header_nritems(leaf);
be0e5c09 626 if (nr == 0)
123abc88 627 return BTRFS_LEAF_DATA_SIZE(root);
5f39d397 628 return btrfs_item_offset_nr(leaf, nr - 1);
be0e5c09
CM		 629}
630
d352ac68
CM		 631/*
632 * extra debugging checks to make sure all the items in a key are
633 * well formed and in the proper order
634 */
123abc88
CM		 635static int check_node(struct btrfs_root *root, struct btrfs_path *path,
636 int level)
aa5d6bed 637{
5f39d397
CM		 638 struct extent_buffer *parent = NULL;
639 struct extent_buffer *node = path->nodes[level];
640 struct btrfs_disk_key parent_key;
641 struct btrfs_disk_key node_key;
aa5d6bed 642 int parent_slot;
8d7be552
CM		 643 int slot;
644 struct btrfs_key cpukey;
5f39d397 645 u32 nritems = btrfs_header_nritems(node);
aa5d6bed
CM		 646
647 if (path->nodes[level + 1])
5f39d397 648 parent = path->nodes[level + 1];
a1f39630 649
8d7be552 650 slot = path->slots[level];
7518a238
CM		 651 BUG_ON(nritems == 0);
652 if (parent) {
a1f39630 653 parent_slot = path->slots[level + 1];
5f39d397
CM		 654 btrfs_node_key(parent, &parent_key, parent_slot);
655 btrfs_node_key(node, &node_key, 0);
656 BUG_ON(memcmp(&parent_key, &node_key,
e2fa7227 657 sizeof(struct btrfs_disk_key)));
1d4f8a0c 658 BUG_ON(btrfs_node_blockptr(parent, parent_slot) !=
db94535d 659 btrfs_header_bytenr(node));
aa5d6bed 660 }
123abc88 661 BUG_ON(nritems > BTRFS_NODEPTRS_PER_BLOCK(root));
8d7be552 662 if (slot != 0) {
5f39d397
CM		 663 btrfs_node_key_to_cpu(node, &cpukey, slot - 1);
664 btrfs_node_key(node, &node_key, slot);
665 BUG_ON(comp_keys(&node_key, &cpukey) <= 0);
8d7be552
CM		 666 }
667 if (slot < nritems - 1) {
5f39d397
CM		 668 btrfs_node_key_to_cpu(node, &cpukey, slot + 1);
669 btrfs_node_key(node, &node_key, slot);
670 BUG_ON(comp_keys(&node_key, &cpukey) >= 0);
aa5d6bed
CM		 671 }
672 return 0;
673}
674
d352ac68
CM		 675/*
676 * extra checking to make sure all the items in a leaf are
677 * well formed and in the proper order
678 */
123abc88
CM		 679static int check_leaf(struct btrfs_root *root, struct btrfs_path *path,
680 int level)
aa5d6bed 681{
5f39d397
CM		 682 struct extent_buffer *leaf = path->nodes[level];
683 struct extent_buffer *parent = NULL;
aa5d6bed 684 int parent_slot;
8d7be552 685 struct btrfs_key cpukey;
5f39d397
CM		 686 struct btrfs_disk_key parent_key;
687 struct btrfs_disk_key leaf_key;
688 int slot = path->slots[0];
8d7be552 689
5f39d397 690 u32 nritems = btrfs_header_nritems(leaf);
aa5d6bed
CM		 691
692 if (path->nodes[level + 1])
5f39d397 693 parent = path->nodes[level + 1];
7518a238
CM		 694
695 if (nritems == 0)
696 return 0;
697
698 if (parent) {
a1f39630 699 parent_slot = path->slots[level + 1];
5f39d397
CM		 700 btrfs_node_key(parent, &parent_key, parent_slot);
701 btrfs_item_key(leaf, &leaf_key, 0);
6702ed49 702
5f39d397 703 BUG_ON(memcmp(&parent_key, &leaf_key,
e2fa7227 704 sizeof(struct btrfs_disk_key)));
1d4f8a0c 705 BUG_ON(btrfs_node_blockptr(parent, parent_slot) !=
db94535d 706 btrfs_header_bytenr(leaf));
5f39d397 707 }
5f39d397
CM		 708 if (slot != 0 && slot < nritems - 1) {
709 btrfs_item_key(leaf, &leaf_key, slot);
710 btrfs_item_key_to_cpu(leaf, &cpukey, slot - 1);
711 if (comp_keys(&leaf_key, &cpukey) <= 0) {
712 btrfs_print_leaf(root, leaf);
d397712b 713 printk(KERN_CRIT "slot %d offset bad key\n", slot);
5f39d397
CM		 714 BUG_ON(1);
715 }
716 if (btrfs_item_offset_nr(leaf, slot - 1) !=
717 btrfs_item_end_nr(leaf, slot)) {
718 btrfs_print_leaf(root, leaf);
d397712b 719 printk(KERN_CRIT "slot %d offset bad\n", slot);
5f39d397
CM		 720 BUG_ON(1);
721 }
8d7be552
CM		 722 }
723 if (slot < nritems - 1) {
5f39d397
CM		 724 btrfs_item_key(leaf, &leaf_key, slot);
725 btrfs_item_key_to_cpu(leaf, &cpukey, slot + 1);
726 BUG_ON(comp_keys(&leaf_key, &cpukey) >= 0);
727 if (btrfs_item_offset_nr(leaf, slot) !=
728 btrfs_item_end_nr(leaf, slot + 1)) {
729 btrfs_print_leaf(root, leaf);
d397712b 730 printk(KERN_CRIT "slot %d offset bad\n", slot);
5f39d397
CM		 731 BUG_ON(1);
732 }
aa5d6bed 733 }
5f39d397
CM		 734 BUG_ON(btrfs_item_offset_nr(leaf, 0) +
735 btrfs_item_size_nr(leaf, 0) != BTRFS_LEAF_DATA_SIZE(root));
aa5d6bed
CM		 736 return 0;
737}
738
d397712b 739static noinline int check_block(struct btrfs_root *root,
98ed5174 740 struct btrfs_path *path, int level)
aa5d6bed 741{
85d824c4 742 return 0;
aa5d6bed 743 if (level == 0)
123abc88
CM		 744 return check_leaf(root, path, level);
745 return check_node(root, path, level);
aa5d6bed
CM		 746}
747
74123bd7 748/*
5f39d397
CM		 749 * search for key in the extent_buffer. The items start at offset p,
750 * and they are item_size apart. There are 'max' items in p.
751 *
74123bd7
CM		 752 * the slot in the array is returned via slot, and it points to
753 * the place where you would insert key if it is not found in
754 * the array.
755 *
756 * slot may point to max if the key is bigger than all of the keys
757 */
e02119d5
CM		 758static noinline int generic_bin_search(struct extent_buffer *eb,
759 unsigned long p,
760 int item_size, struct btrfs_key *key,
761 int max, int *slot)
be0e5c09
CM		 762{
763 int low = 0;
764 int high = max;
765 int mid;
766 int ret;
479965d6 767 struct btrfs_disk_key *tmp = NULL;
5f39d397
CM		 768 struct btrfs_disk_key unaligned;
769 unsigned long offset;
770 char *map_token = NULL;
771 char *kaddr = NULL;
772 unsigned long map_start = 0;
773 unsigned long map_len = 0;
479965d6 774 int err;
be0e5c09 775
d397712b 776 while (low < high) {
be0e5c09 777 mid = (low + high) / 2;
5f39d397
CM		 778 offset = p + mid * item_size;
779
780 if (!map_token || offset < map_start ||
781 (offset + sizeof(struct btrfs_disk_key)) >
782 map_start + map_len) {
479965d6 783 if (map_token) {
5f39d397 784 unmap_extent_buffer(eb, map_token, KM_USER0);
479965d6
CM		 785 map_token = NULL;
786 }
934d375b
CM		 787
788 err = map_private_extent_buffer(eb, offset,
479965d6
CM		 789 sizeof(struct btrfs_disk_key),
790 &map_token, &kaddr,
791 &map_start, &map_len, KM_USER0);
792
793 if (!err) {
794 tmp = (struct btrfs_disk_key *)(kaddr + offset -
795 map_start);
796 } else {
797 read_extent_buffer(eb, &unaligned,
798 offset, sizeof(unaligned));
799 tmp = &unaligned;
800 }
5f39d397 801
5f39d397
CM		 802 } else {
803 tmp = (struct btrfs_disk_key *)(kaddr + offset -
804 map_start);
805 }
be0e5c09
CM		 806 ret = comp_keys(tmp, key);
807
808 if (ret < 0)
809 low = mid + 1;
810 else if (ret > 0)
811 high = mid;
812 else {
813 *slot = mid;
479965d6
CM		 814 if (map_token)
815 unmap_extent_buffer(eb, map_token, KM_USER0);
be0e5c09
CM		 816 return 0;
817 }
818 }
819 *slot = low;
5f39d397
CM		 820 if (map_token)
821 unmap_extent_buffer(eb, map_token, KM_USER0);
be0e5c09
CM		 822 return 1;
823}
824
97571fd0
CM		 825/*
826 * simple bin_search frontend that does the right thing for
827 * leaves vs nodes
828 */
5f39d397
CM		 829static int bin_search(struct extent_buffer *eb, struct btrfs_key *key,
830 int level, int *slot)
be0e5c09 831{
5f39d397
CM		 832 if (level == 0) {
833 return generic_bin_search(eb,
834 offsetof(struct btrfs_leaf, items),
0783fcfc 835 sizeof(struct btrfs_item),
5f39d397 836 key, btrfs_header_nritems(eb),
7518a238 837 slot);
be0e5c09 838 } else {
5f39d397
CM		 839 return generic_bin_search(eb,
840 offsetof(struct btrfs_node, ptrs),
123abc88 841 sizeof(struct btrfs_key_ptr),
5f39d397 842 key, btrfs_header_nritems(eb),
7518a238 843 slot);
be0e5c09
CM		 844 }
845 return -1;
846}
847
d352ac68
CM		 848/* given a node and slot number, this reads the blocks it points to. The
849 * extent buffer is returned with a reference taken (but unlocked).
850 * NULL is returned on error.
851 */
e02119d5 852static noinline struct extent_buffer *read_node_slot(struct btrfs_root *root,
5f39d397 853 struct extent_buffer *parent, int slot)
bb803951 854{
ca7a79ad 855 int level = btrfs_header_level(parent);
bb803951
CM		 856 if (slot < 0)
857 return NULL;
5f39d397 858 if (slot >= btrfs_header_nritems(parent))
bb803951 859 return NULL;
ca7a79ad
CM		 860
861 BUG_ON(level == 0);
862
db94535d 863 return read_tree_block(root, btrfs_node_blockptr(parent, slot),
ca7a79ad
CM		 864 btrfs_level_size(root, level - 1),
865 btrfs_node_ptr_generation(parent, slot));
bb803951
CM		 866}
867
d352ac68
CM		 868/*
869 * node level balancing, used to make sure nodes are in proper order for
870 * item deletion. We balance from the top down, so we have to make sure
871 * that a deletion won't leave an node completely empty later on.
872 */
e02119d5 873static noinline int balance_level(struct btrfs_trans_handle *trans,
98ed5174
CM		 874 struct btrfs_root *root,
875 struct btrfs_path *path, int level)
bb803951 876{
5f39d397
CM		 877 struct extent_buffer *right = NULL;
878 struct extent_buffer *mid;
879 struct extent_buffer *left = NULL;
880 struct extent_buffer *parent = NULL;
bb803951
CM		 881 int ret = 0;
882 int wret;
883 int pslot;
bb803951 884 int orig_slot = path->slots[level];
54aa1f4d 885 int err_on_enospc = 0;
79f95c82 886 u64 orig_ptr;
bb803951
CM		 887
888 if (level == 0)
889 return 0;
890
5f39d397 891 mid = path->nodes[level];
b4ce94de 892
925baedd 893 WARN_ON(!path->locks[level]);
7bb86316
CM		 894 WARN_ON(btrfs_header_generation(mid) != trans->transid);
895
1d4f8a0c 896 orig_ptr = btrfs_node_blockptr(mid, orig_slot);
79f95c82 897
234b63a0 898 if (level < BTRFS_MAX_LEVEL - 1)
5f39d397 899 parent = path->nodes[level + 1];
bb803951
CM		 900 pslot = path->slots[level + 1];
901
40689478
CM		 902 /*
903 * deal with the case where there is only one pointer in the root
904 * by promoting the node below to a root
905 */
5f39d397
CM		 906 if (!parent) {
907 struct extent_buffer *child;
bb803951 908
5f39d397 909 if (btrfs_header_nritems(mid) != 1)
bb803951
CM		 910 return 0;
911
912 /* promote the child to a root */
5f39d397 913 child = read_node_slot(root, mid, 0);
7951f3ce 914 BUG_ON(!child);
925baedd 915 btrfs_tree_lock(child);
b4ce94de 916 btrfs_set_lock_blocking(child);
9fa8cfe7 917 ret = btrfs_cow_block(trans, root, child, mid, 0, &child);
2f375ab9
Y		 918 BUG_ON(ret);
919
925baedd 920 spin_lock(&root->node_lock);
bb803951 921 root->node = child;
925baedd
CM		 922 spin_unlock(&root->node_lock);
923
31840ae1 924 ret = btrfs_update_extent_ref(trans, root, child->start,
56bec294 925 child->len,
31840ae1
ZY		 926 mid->start, child->start,
927 root->root_key.objectid,
3bb1a1bc 928 trans->transid, level - 1);
31840ae1
ZY		 929 BUG_ON(ret);
930
0b86a832 931 add_root_to_dirty_list(root);
925baedd 932 btrfs_tree_unlock(child);
b4ce94de 933
925baedd 934 path->locks[level] = 0;
bb803951 935 path->nodes[level] = NULL;
5f39d397 936 clean_tree_block(trans, root, mid);
925baedd 937 btrfs_tree_unlock(mid);
bb803951 938 /* once for the path */
5f39d397 939 free_extent_buffer(mid);
7bb86316 940 ret = btrfs_free_extent(trans, root, mid->start, mid->len,
31840ae1 941 mid->start, root->root_key.objectid,
3bb1a1bc
YZ		 942 btrfs_header_generation(mid),
943 level, 1);
bb803951 944 /* once for the root ptr */
5f39d397 945 free_extent_buffer(mid);
db94535d 946 return ret;
bb803951 947 }
5f39d397 948 if (btrfs_header_nritems(mid) >
123abc88 949 BTRFS_NODEPTRS_PER_BLOCK(root) / 4)
bb803951
CM		 950 return 0;
951
a4b6e07d
CM		 952 if (trans->transaction->delayed_refs.flushing &&
953 btrfs_header_nritems(mid) > 2)
954 return 0;
955
5f39d397 956 if (btrfs_header_nritems(mid) < 2)
54aa1f4d
CM		 957 err_on_enospc = 1;
958
5f39d397
CM		 959 left = read_node_slot(root, parent, pslot - 1);
960 if (left) {
925baedd 961 btrfs_tree_lock(left);
b4ce94de 962 btrfs_set_lock_blocking(left);
5f39d397 963 wret = btrfs_cow_block(trans, root, left,
9fa8cfe7 964 parent, pslot - 1, &left);
54aa1f4d
CM		 965 if (wret) {
966 ret = wret;
967 goto enospc;
968 }
2cc58cf2 969 }
5f39d397
CM		 970 right = read_node_slot(root, parent, pslot + 1);
971 if (right) {
925baedd 972 btrfs_tree_lock(right);
b4ce94de 973 btrfs_set_lock_blocking(right);
5f39d397 974 wret = btrfs_cow_block(trans, root, right,
9fa8cfe7 975 parent, pslot + 1, &right);
2cc58cf2
CM		 976 if (wret) {
977 ret = wret;
978 goto enospc;
979 }
980 }
981
982 /* first, try to make some room in the middle buffer */
5f39d397
CM		 983 if (left) {
984 orig_slot += btrfs_header_nritems(left);
bce4eae9 985 wret = push_node_left(trans, root, left, mid, 1);
79f95c82
CM		 986 if (wret < 0)
987 ret = wret;
5f39d397 988 if (btrfs_header_nritems(mid) < 2)
54aa1f4d 989 err_on_enospc = 1;
bb803951 990 }
79f95c82
CM		 991
992 /*
993 * then try to empty the right most buffer into the middle
994 */
5f39d397 995 if (right) {
971a1f66 996 wret = push_node_left(trans, root, mid, right, 1);
54aa1f4d 997 if (wret < 0 && wret != -ENOSPC)
79f95c82 998 ret = wret;
5f39d397 999 if (btrfs_header_nritems(right) == 0) {
db94535d 1000 u64 bytenr = right->start;
7bb86316 1001 u64 generation = btrfs_header_generation(parent);
db94535d
CM		 1002 u32 blocksize = right->len;
1003
5f39d397 1004 clean_tree_block(trans, root, right);
925baedd 1005 btrfs_tree_unlock(right);
5f39d397 1006 free_extent_buffer(right);
bb803951 1007 right = NULL;
e089f05c
CM		 1008 wret = del_ptr(trans, root, path, level + 1, pslot +
1009 1);
bb803951
CM		 1010 if (wret)
1011 ret = wret;
db94535d 1012 wret = btrfs_free_extent(trans, root, bytenr,
31840ae1 1013 blocksize, parent->start,
7bb86316 1014 btrfs_header_owner(parent),
3bb1a1bc 1015 generation, level, 1);
bb803951
CM		 1016 if (wret)
1017 ret = wret;
1018 } else {
5f39d397
CM		 1019 struct btrfs_disk_key right_key;
1020 btrfs_node_key(right, &right_key, 0);
1021 btrfs_set_node_key(parent, &right_key, pslot + 1);
1022 btrfs_mark_buffer_dirty(parent);
bb803951
CM		 1023 }
1024 }
5f39d397 1025 if (btrfs_header_nritems(mid) == 1) {
79f95c82
CM		 1026 /*
1027 * we're not allowed to leave a node with one item in the
1028 * tree during a delete. A deletion from lower in the tree
1029 * could try to delete the only pointer in this node.
1030 * So, pull some keys from the left.
1031 * There has to be a left pointer at this point because
1032 * otherwise we would have pulled some pointers from the
1033 * right
1034 */
5f39d397
CM		 1035 BUG_ON(!left);
1036 wret = balance_node_right(trans, root, mid, left);
54aa1f4d 1037 if (wret < 0) {
79f95c82 1038 ret = wret;
54aa1f4d
CM		 1039 goto enospc;
1040 }
bce4eae9
CM		 1041 if (wret == 1) {
1042 wret = push_node_left(trans, root, left, mid, 1);
1043 if (wret < 0)
1044 ret = wret;
1045 }
79f95c82
CM		 1046 BUG_ON(wret == 1);
1047 }
5f39d397 1048 if (btrfs_header_nritems(mid) == 0) {
79f95c82 1049 /* we've managed to empty the middle node, drop it */
7bb86316 1050 u64 root_gen = btrfs_header_generation(parent);
db94535d
CM		 1051 u64 bytenr = mid->start;
1052 u32 blocksize = mid->len;
925baedd 1053
5f39d397 1054 clean_tree_block(trans, root, mid);
925baedd 1055 btrfs_tree_unlock(mid);
5f39d397 1056 free_extent_buffer(mid);
bb803951 1057 mid = NULL;
e089f05c 1058 wret = del_ptr(trans, root, path, level + 1, pslot);
bb803951
CM		 1059 if (wret)
1060 ret = wret;
7bb86316 1061 wret = btrfs_free_extent(trans, root, bytenr, blocksize,
31840ae1 1062 parent->start,
7bb86316 1063 btrfs_header_owner(parent),
3bb1a1bc 1064 root_gen, level, 1);
bb803951
CM		 1065 if (wret)
1066 ret = wret;
79f95c82
CM		 1067 } else {
1068 /* update the parent key to reflect our changes */
5f39d397
CM		 1069 struct btrfs_disk_key mid_key;
1070 btrfs_node_key(mid, &mid_key, 0);
1071 btrfs_set_node_key(parent, &mid_key, pslot);
1072 btrfs_mark_buffer_dirty(parent);
79f95c82 1073 }
bb803951 1074
79f95c82 1075 /* update the path */
5f39d397
CM		 1076 if (left) {
1077 if (btrfs_header_nritems(left) > orig_slot) {
1078 extent_buffer_get(left);
925baedd 1079 /* left was locked after cow */
5f39d397 1080 path->nodes[level] = left;
bb803951
CM		 1081 path->slots[level + 1] -= 1;
1082 path->slots[level] = orig_slot;
925baedd
CM		 1083 if (mid) {
1084 btrfs_tree_unlock(mid);
5f39d397 1085 free_extent_buffer(mid);
925baedd 1086 }
bb803951 1087 } else {
5f39d397 1088 orig_slot -= btrfs_header_nritems(left);
bb803951
CM		 1089 path->slots[level] = orig_slot;
1090 }
1091 }
79f95c82 1092 /* double check we haven't messed things up */
123abc88 1093 check_block(root, path, level);
e20d96d6 1094 if (orig_ptr !=
5f39d397 1095 btrfs_node_blockptr(path->nodes[level], path->slots[level]))
79f95c82 1096 BUG();
54aa1f4d 1097enospc:
925baedd
CM		 1098 if (right) {
1099 btrfs_tree_unlock(right);
5f39d397 1100 free_extent_buffer(right);
925baedd
CM		 1101 }
1102 if (left) {
1103 if (path->nodes[level] != left)
1104 btrfs_tree_unlock(left);
5f39d397 1105 free_extent_buffer(left);
925baedd 1106 }
bb803951
CM		 1107 return ret;
1108}
1109
d352ac68
CM		 1110/* Node balancing for insertion. Here we only split or push nodes around
1111 * when they are completely full. This is also done top down, so we
1112 * have to be pessimistic.
1113 */
d397712b 1114static noinline int push_nodes_for_insert(struct btrfs_trans_handle *trans,
98ed5174
CM		 1115 struct btrfs_root *root,
1116 struct btrfs_path *path, int level)
e66f709b 1117{
5f39d397
CM		 1118 struct extent_buffer *right = NULL;
1119 struct extent_buffer *mid;
1120 struct extent_buffer *left = NULL;
1121 struct extent_buffer *parent = NULL;
e66f709b
CM		 1122 int ret = 0;
1123 int wret;
1124 int pslot;
1125 int orig_slot = path->slots[level];
1126 u64 orig_ptr;
1127
1128 if (level == 0)
1129 return 1;
1130
5f39d397 1131 mid = path->nodes[level];
7bb86316 1132 WARN_ON(btrfs_header_generation(mid) != trans->transid);
e66f709b
CM		 1133 orig_ptr = btrfs_node_blockptr(mid, orig_slot);
1134
1135 if (level < BTRFS_MAX_LEVEL - 1)
5f39d397 1136 parent = path->nodes[level + 1];
e66f709b
CM		 1137 pslot = path->slots[level + 1];
1138
5f39d397 1139 if (!parent)
e66f709b 1140 return 1;
e66f709b 1141
5f39d397 1142 left = read_node_slot(root, parent, pslot - 1);
e66f709b
CM		 1143
1144 /* first, try to make some room in the middle buffer */
5f39d397 1145 if (left) {
e66f709b 1146 u32 left_nr;
925baedd
CM		 1147
1148 btrfs_tree_lock(left);
b4ce94de
CM		 1149 btrfs_set_lock_blocking(left);
1150
5f39d397 1151 left_nr = btrfs_header_nritems(left);
33ade1f8
CM		 1152 if (left_nr >= BTRFS_NODEPTRS_PER_BLOCK(root) - 1) {
1153 wret = 1;
1154 } else {
5f39d397 1155 ret = btrfs_cow_block(trans, root, left, parent,
9fa8cfe7 1156 pslot - 1, &left);
54aa1f4d
CM		 1157 if (ret)
1158 wret = 1;
1159 else {
54aa1f4d 1160 wret = push_node_left(trans, root,
971a1f66 1161 left, mid, 0);
54aa1f4d 1162 }
33ade1f8 1163 }
e66f709b
CM		 1164 if (wret < 0)
1165 ret = wret;
1166 if (wret == 0) {
5f39d397 1167 struct btrfs_disk_key disk_key;
e66f709b 1168 orig_slot += left_nr;
5f39d397
CM		 1169 btrfs_node_key(mid, &disk_key, 0);
1170 btrfs_set_node_key(parent, &disk_key, pslot);
1171 btrfs_mark_buffer_dirty(parent);
1172 if (btrfs_header_nritems(left) > orig_slot) {
1173 path->nodes[level] = left;
e66f709b
CM		 1174 path->slots[level + 1] -= 1;
1175 path->slots[level] = orig_slot;
925baedd 1176 btrfs_tree_unlock(mid);
5f39d397 1177 free_extent_buffer(mid);
e66f709b
CM		 1178 } else {
1179 orig_slot -=
5f39d397 1180 btrfs_header_nritems(left);
e66f709b 1181 path->slots[level] = orig_slot;
925baedd 1182 btrfs_tree_unlock(left);
5f39d397 1183 free_extent_buffer(left);
e66f709b 1184 }
e66f709b
CM		 1185 return 0;
1186 }
925baedd 1187 btrfs_tree_unlock(left);
5f39d397 1188 free_extent_buffer(left);
e66f709b 1189 }
925baedd 1190 right = read_node_slot(root, parent, pslot + 1);
e66f709b
CM		 1191
1192 /*
1193 * then try to empty the right most buffer into the middle
1194 */
5f39d397 1195 if (right) {
33ade1f8 1196 u32 right_nr;
b4ce94de 1197
925baedd 1198 btrfs_tree_lock(right);
b4ce94de
CM		 1199 btrfs_set_lock_blocking(right);
1200
5f39d397 1201 right_nr = btrfs_header_nritems(right);
33ade1f8
CM		 1202 if (right_nr >= BTRFS_NODEPTRS_PER_BLOCK(root) - 1) {
1203 wret = 1;
1204 } else {
5f39d397
CM		 1205 ret = btrfs_cow_block(trans, root, right,
1206 parent, pslot + 1,
9fa8cfe7 1207 &right);
54aa1f4d
CM		 1208 if (ret)
1209 wret = 1;
1210 else {
54aa1f4d 1211 wret = balance_node_right(trans, root,
5f39d397 1212 right, mid);
54aa1f4d 1213 }
33ade1f8 1214 }
e66f709b
CM		 1215 if (wret < 0)
1216 ret = wret;
1217 if (wret == 0) {
5f39d397
CM		 1218 struct btrfs_disk_key disk_key;
1219
1220 btrfs_node_key(right, &disk_key, 0);
1221 btrfs_set_node_key(parent, &disk_key, pslot + 1);
1222 btrfs_mark_buffer_dirty(parent);
1223
1224 if (btrfs_header_nritems(mid) <= orig_slot) {
1225 path->nodes[level] = right;
e66f709b
CM		 1226 path->slots[level + 1] += 1;
1227 path->slots[level] = orig_slot -
5f39d397 1228 btrfs_header_nritems(mid);
925baedd 1229 btrfs_tree_unlock(mid);
5f39d397 1230 free_extent_buffer(mid);
e66f709b 1231 } else {
925baedd 1232 btrfs_tree_unlock(right);
5f39d397 1233 free_extent_buffer(right);
e66f709b 1234 }
e66f709b
CM		 1235 return 0;
1236 }
925baedd 1237 btrfs_tree_unlock(right);
5f39d397 1238 free_extent_buffer(right);
e66f709b 1239 }
e66f709b
CM		 1240 return 1;
1241}
1242
3c69faec 1243/*
d352ac68
CM		 1244 * readahead one full node of leaves, finding things that are close
1245 * to the block in 'slot', and triggering ra on them.
3c69faec 1246 */
c8c42864
CM		 1247static void reada_for_search(struct btrfs_root *root,
1248 struct btrfs_path *path,
1249 int level, int slot, u64 objectid)
3c69faec 1250{
5f39d397 1251 struct extent_buffer *node;
01f46658 1252 struct btrfs_disk_key disk_key;
3c69faec 1253 u32 nritems;
3c69faec 1254 u64 search;
a7175319 1255 u64 target;
6b80053d 1256 u64 nread = 0;
3c69faec 1257 int direction = path->reada;
5f39d397 1258 struct extent_buffer *eb;
6b80053d
CM		 1259 u32 nr;
1260 u32 blocksize;
1261 u32 nscan = 0;
db94535d 1262
a6b6e75e 1263 if (level != 1)
6702ed49
CM		 1264 return;
1265
1266 if (!path->nodes[level])
3c69faec
CM		 1267 return;
1268
5f39d397 1269 node = path->nodes[level];
925baedd 1270
3c69faec 1271 search = btrfs_node_blockptr(node, slot);
6b80053d
CM		 1272 blocksize = btrfs_level_size(root, level - 1);
1273 eb = btrfs_find_tree_block(root, search, blocksize);
5f39d397
CM		 1274 if (eb) {
1275 free_extent_buffer(eb);
3c69faec
CM		 1276 return;
1277 }
1278
a7175319 1279 target = search;
6b80053d 1280
5f39d397 1281 nritems = btrfs_header_nritems(node);
6b80053d 1282 nr = slot;
d397712b 1283 while (1) {
6b80053d
CM		 1284 if (direction < 0) {
1285 if (nr == 0)
1286 break;
1287 nr--;
1288 } else if (direction > 0) {
1289 nr++;
1290 if (nr >= nritems)
1291 break;
3c69faec 1292 }
01f46658
CM		 1293 if (path->reada < 0 && objectid) {
1294 btrfs_node_key(node, &disk_key, nr);
1295 if (btrfs_disk_key_objectid(&disk_key) != objectid)
1296 break;
1297 }
6b80053d 1298 search = btrfs_node_blockptr(node, nr);
a7175319
CM		 1299 if ((search <= target && target - search <= 65536) ||
1300 (search > target && search - target <= 65536)) {
ca7a79ad
CM		 1301 readahead_tree_block(root, search, blocksize,
1302 btrfs_node_ptr_generation(node, nr));
6b80053d
CM		 1303 nread += blocksize;
1304 }
1305 nscan++;
a7175319 1306 if ((nread > 65536 || nscan > 32))
6b80053d 1307 break;
3c69faec
CM		 1308 }
1309}
925baedd 1310
b4ce94de
CM		 1311/*
1312 * returns -EAGAIN if it had to drop the path, or zero if everything was in
1313 * cache
1314 */
1315static noinline int reada_for_balance(struct btrfs_root *root,
1316 struct btrfs_path *path, int level)
1317{
1318 int slot;
1319 int nritems;
1320 struct extent_buffer *parent;
1321 struct extent_buffer *eb;
1322 u64 gen;
1323 u64 block1 = 0;
1324 u64 block2 = 0;
1325 int ret = 0;
1326 int blocksize;
1327
1328 parent = path->nodes[level - 1];
1329 if (!parent)
1330 return 0;
1331
1332 nritems = btrfs_header_nritems(parent);
1333 slot = path->slots[level];
1334 blocksize = btrfs_level_size(root, level);
1335
1336 if (slot > 0) {
1337 block1 = btrfs_node_blockptr(parent, slot - 1);
1338 gen = btrfs_node_ptr_generation(parent, slot - 1);
1339 eb = btrfs_find_tree_block(root, block1, blocksize);
1340 if (eb && btrfs_buffer_uptodate(eb, gen))
1341 block1 = 0;
1342 free_extent_buffer(eb);
1343 }
1344 if (slot < nritems) {
1345 block2 = btrfs_node_blockptr(parent, slot + 1);
1346 gen = btrfs_node_ptr_generation(parent, slot + 1);
1347 eb = btrfs_find_tree_block(root, block2, blocksize);
1348 if (eb && btrfs_buffer_uptodate(eb, gen))
1349 block2 = 0;
1350 free_extent_buffer(eb);
1351 }
1352 if (block1 || block2) {
1353 ret = -EAGAIN;
1354 btrfs_release_path(root, path);
1355 if (block1)
1356 readahead_tree_block(root, block1, blocksize, 0);
1357 if (block2)
1358 readahead_tree_block(root, block2, blocksize, 0);
1359
1360 if (block1) {
1361 eb = read_tree_block(root, block1, blocksize, 0);
1362 free_extent_buffer(eb);
1363 }
1364 if (block1) {
1365 eb = read_tree_block(root, block2, blocksize, 0);
1366 free_extent_buffer(eb);
1367 }
1368 }
1369 return ret;
1370}
1371
1372
d352ac68 1373/*
d397712b
CM		 1374 * when we walk down the tree, it is usually safe to unlock the higher layers
1375 * in the tree. The exceptions are when our path goes through slot 0, because
1376 * operations on the tree might require changing key pointers higher up in the
1377 * tree.
d352ac68 1378 *
d397712b
CM		 1379 * callers might also have set path->keep_locks, which tells this code to keep
1380 * the lock if the path points to the last slot in the block. This is part of
1381 * walking through the tree, and selecting the next slot in the higher block.
d352ac68 1382 *
d397712b
CM		 1383 * lowest_unlock sets the lowest level in the tree we're allowed to unlock. so
1384 * if lowest_unlock is 1, level 0 won't be unlocked
d352ac68 1385 */
e02119d5
CM		 1386static noinline void unlock_up(struct btrfs_path *path, int level,
1387 int lowest_unlock)
925baedd
CM		 1388{
1389 int i;
1390 int skip_level = level;
051e1b9f 1391 int no_skips = 0;
925baedd
CM		 1392 struct extent_buffer *t;
1393
1394 for (i = level; i < BTRFS_MAX_LEVEL; i++) {
1395 if (!path->nodes[i])
1396 break;
1397 if (!path->locks[i])
1398 break;
051e1b9f 1399 if (!no_skips && path->slots[i] == 0) {
925baedd
CM		 1400 skip_level = i + 1;
1401 continue;
1402 }
051e1b9f 1403 if (!no_skips && path->keep_locks) {
925baedd
CM		 1404 u32 nritems;
1405 t = path->nodes[i];
1406 nritems = btrfs_header_nritems(t);
051e1b9f 1407 if (nritems < 1 || path->slots[i] >= nritems - 1) {
925baedd
CM		 1408 skip_level = i + 1;
1409 continue;
1410 }
1411 }
051e1b9f
CM		 1412 if (skip_level < i && i >= lowest_unlock)
1413 no_skips = 1;
1414
925baedd
CM		 1415 t = path->nodes[i];
1416 if (i >= lowest_unlock && i > skip_level && path->locks[i]) {
1417 btrfs_tree_unlock(t);
1418 path->locks[i] = 0;
1419 }
1420 }
1421}
1422
b4ce94de
CM		 1423/*
1424 * This releases any locks held in the path starting at level and
1425 * going all the way up to the root.
1426 *
1427 * btrfs_search_slot will keep the lock held on higher nodes in a few
1428 * corner cases, such as COW of the block at slot zero in the node. This
1429 * ignores those rules, and it should only be called when there are no
1430 * more updates to be done higher up in the tree.
1431 */
1432noinline void btrfs_unlock_up_safe(struct btrfs_path *path, int level)
1433{
1434 int i;
1435
1436 if (path->keep_locks || path->lowest_level)
1437 return;
1438
1439 for (i = level; i < BTRFS_MAX_LEVEL; i++) {
1440 if (!path->nodes[i])
12f4dacc 1441 continue;
b4ce94de 1442 if (!path->locks[i])
12f4dacc 1443 continue;
b4ce94de
CM		 1444 btrfs_tree_unlock(path->nodes[i]);
1445 path->locks[i] = 0;
1446 }
1447}
1448
c8c42864
CM		 1449/*
1450 * helper function for btrfs_search_slot. The goal is to find a block
1451 * in cache without setting the path to blocking. If we find the block
1452 * we return zero and the path is unchanged.
1453 *
1454 * If we can't find the block, we set the path blocking and do some
1455 * reada. -EAGAIN is returned and the search must be repeated.
1456 */
1457static int
1458read_block_for_search(struct btrfs_trans_handle *trans,
1459 struct btrfs_root *root, struct btrfs_path *p,
1460 struct extent_buffer **eb_ret, int level, int slot,
1461 struct btrfs_key *key)
1462{
1463 u64 blocknr;
1464 u64 gen;
1465 u32 blocksize;
1466 struct extent_buffer *b = *eb_ret;
1467 struct extent_buffer *tmp;
1468
1469 blocknr = btrfs_node_blockptr(b, slot);
1470 gen = btrfs_node_ptr_generation(b, slot);
1471 blocksize = btrfs_level_size(root, level - 1);
1472
1473 tmp = btrfs_find_tree_block(root, blocknr, blocksize);
1474 if (tmp && btrfs_buffer_uptodate(tmp, gen)) {
1475 *eb_ret = tmp;
1476 return 0;
1477 }
1478
1479 /*
1480 * reduce lock contention at high levels
1481 * of the btree by dropping locks before
1482 * we read.
1483 */
1484 btrfs_release_path(NULL, p);
1485 if (tmp)
1486 free_extent_buffer(tmp);
1487 if (p->reada)
1488 reada_for_search(root, p, level, slot, key->objectid);
1489
1490 tmp = read_tree_block(root, blocknr, blocksize, gen);
1491 if (tmp)
1492 free_extent_buffer(tmp);
1493 return -EAGAIN;
1494}
1495
1496/*
1497 * helper function for btrfs_search_slot. This does all of the checks
1498 * for node-level blocks and does any balancing required based on
1499 * the ins_len.
1500 *
1501 * If no extra work was required, zero is returned. If we had to
1502 * drop the path, -EAGAIN is returned and btrfs_search_slot must
1503 * start over
1504 */
1505static int
1506setup_nodes_for_search(struct btrfs_trans_handle *trans,
1507 struct btrfs_root *root, struct btrfs_path *p,
1508 struct extent_buffer *b, int level, int ins_len)
1509{
1510 int ret;
1511 if ((p->search_for_split || ins_len > 0) && btrfs_header_nritems(b) >=
1512 BTRFS_NODEPTRS_PER_BLOCK(root) - 3) {
1513 int sret;
1514
1515 sret = reada_for_balance(root, p, level);
1516 if (sret)
1517 goto again;
1518
1519 btrfs_set_path_blocking(p);
1520 sret = split_node(trans, root, p, level);
1521 btrfs_clear_path_blocking(p, NULL);
1522
1523 BUG_ON(sret > 0);
1524 if (sret) {
1525 ret = sret;
1526 goto done;
1527 }
1528 b = p->nodes[level];
1529 } else if (ins_len < 0 && btrfs_header_nritems(b) <
1530 BTRFS_NODEPTRS_PER_BLOCK(root) / 4) {
1531 int sret;
1532
1533 sret = reada_for_balance(root, p, level);
1534 if (sret)
1535 goto again;
1536
1537 btrfs_set_path_blocking(p);
1538 sret = balance_level(trans, root, p, level);
1539 btrfs_clear_path_blocking(p, NULL);
1540
1541 if (sret) {
1542 ret = sret;
1543 goto done;
1544 }
1545 b = p->nodes[level];
1546 if (!b) {
1547 btrfs_release_path(NULL, p);
1548 goto again;
1549 }
1550 BUG_ON(btrfs_header_nritems(b) == 1);
1551 }
1552 return 0;
1553
1554again:
1555 ret = -EAGAIN;
1556done:
1557 return ret;
1558}
1559
74123bd7
CM		 1560/*
1561 * look for key in the tree. path is filled in with nodes along the way
1562 * if key is found, we return zero and you can find the item in the leaf
1563 * level of the path (level 0)
1564 *
1565 * If the key isn't found, the path points to the slot where it should
aa5d6bed
CM		 1566 * be inserted, and 1 is returned. If there are other errors during the
1567 * search a negative error number is returned.
97571fd0
CM		 1568 *
1569 * if ins_len > 0, nodes and leaves will be split as we walk down the
1570 * tree. if ins_len < 0, nodes will be merged as we walk down the tree (if
1571 * possible)
74123bd7 1572 */
e089f05c
CM		 1573int btrfs_search_slot(struct btrfs_trans_handle *trans, struct btrfs_root
1574 *root, struct btrfs_key *key, struct btrfs_path *p, int
1575 ins_len, int cow)
be0e5c09 1576{
5f39d397 1577 struct extent_buffer *b;
be0e5c09
CM		 1578 int slot;
1579 int ret;
1580 int level;
925baedd 1581 int lowest_unlock = 1;
9f3a7427
CM		 1582 u8 lowest_level = 0;
1583
6702ed49 1584 lowest_level = p->lowest_level;
323ac95b 1585 WARN_ON(lowest_level && ins_len > 0);
22b0ebda 1586 WARN_ON(p->nodes[0] != NULL);
25179201 1587
925baedd
CM		 1588 if (ins_len < 0)
1589 lowest_unlock = 2;
65b51a00 1590
bb803951 1591again:
5cd57b2c
CM		 1592 if (p->skip_locking)
1593 b = btrfs_root_node(root);
1594 else
1595 b = btrfs_lock_root_node(root);
925baedd 1596
eb60ceac 1597 while (b) {
5f39d397 1598 level = btrfs_header_level(b);
65b51a00
CM		 1599
1600 /*
1601 * setup the path here so we can release it under lock
1602 * contention with the cow code
1603 */
1604 p->nodes[level] = b;
1605 if (!p->skip_locking)
1606 p->locks[level] = 1;
1607
02217ed2
CM		 1608 if (cow) {
1609 int wret;
65b51a00 1610
c8c42864
CM		 1611 /*
1612 * if we don't really need to cow this block
1613 * then we don't want to set the path blocking,
1614 * so we test it here
1615 */
65b51a00 1616 if (btrfs_header_generation(b) == trans->transid &&
5b21f2ed 1617 btrfs_header_owner(b) == root->root_key.objectid &&
65b51a00 1618 !btrfs_header_flag(b, BTRFS_HEADER_FLAG_WRITTEN)) {
65b51a00
CM		 1619 goto cow_done;
1620 }
b4ce94de
CM		 1621 btrfs_set_path_blocking(p);
1622
e20d96d6
CM		 1623 wret = btrfs_cow_block(trans, root, b,
1624 p->nodes[level + 1],
9fa8cfe7 1625 p->slots[level + 1], &b);
54aa1f4d 1626 if (wret) {
5f39d397 1627 free_extent_buffer(b);
65b51a00
CM		 1628 ret = wret;
1629 goto done;
54aa1f4d 1630 }
02217ed2 1631 }
65b51a00 1632cow_done:
02217ed2 1633 BUG_ON(!cow && ins_len);
5f39d397 1634 if (level != btrfs_header_level(b))
2c90e5d6 1635 WARN_ON(1);
5f39d397 1636 level = btrfs_header_level(b);
65b51a00 1637
eb60ceac 1638 p->nodes[level] = b;
5cd57b2c
CM		 1639 if (!p->skip_locking)
1640 p->locks[level] = 1;
65b51a00 1641
4008c04a 1642 btrfs_clear_path_blocking(p, NULL);
b4ce94de
CM		 1643
1644 /*
1645 * we have a lock on b and as long as we aren't changing
1646 * the tree, there is no way to for the items in b to change.
1647 * It is safe to drop the lock on our parent before we
1648 * go through the expensive btree search on b.
1649 *
1650 * If cow is true, then we might be changing slot zero,
1651 * which may require changing the parent. So, we can't
1652 * drop the lock until after we know which slot we're
1653 * operating on.
1654 */
1655 if (!cow)
1656 btrfs_unlock_up_safe(p, level + 1);
1657
123abc88 1658 ret = check_block(root, p, level);
65b51a00
CM		 1659 if (ret) {
1660 ret = -1;
1661 goto done;
1662 }
925baedd 1663
5f39d397 1664 ret = bin_search(b, key, level, &slot);
b4ce94de 1665
5f39d397 1666 if (level != 0) {
be0e5c09
CM		 1667 if (ret && slot > 0)
1668 slot -= 1;
1669 p->slots[level] = slot;
c8c42864
CM		 1670 ret = setup_nodes_for_search(trans, root, p, b, level,
1671 ins_len);
1672 if (ret == -EAGAIN)
1673 goto again;
1674 else if (ret)
1675 goto done;
1676 b = p->nodes[level];
1677 slot = p->slots[level];
b4ce94de 1678
f9efa9c7
CM		 1679 unlock_up(p, level, lowest_unlock);
1680
9f3a7427 1681 /* this is only true while dropping a snapshot */
925baedd 1682 if (level == lowest_level) {
5b21f2ed
ZY		 1683 ret = 0;
1684 goto done;
925baedd 1685 }
ca7a79ad 1686
c8c42864
CM		 1687 ret = read_block_for_search(trans, root, p,
1688 &b, level, slot, key);
1689 if (ret == -EAGAIN)
1690 goto again;
594a24eb 1691
b4ce94de
CM		 1692 if (!p->skip_locking) {
1693 int lret;
1694
4008c04a 1695 btrfs_clear_path_blocking(p, NULL);
b4ce94de
CM		 1696 lret = btrfs_try_spin_lock(b);
1697
1698 if (!lret) {
1699 btrfs_set_path_blocking(p);
1700 btrfs_tree_lock(b);
4008c04a 1701 btrfs_clear_path_blocking(p, b);
b4ce94de
CM		 1702 }
1703 }
be0e5c09
CM		 1704 } else {
1705 p->slots[level] = slot;
87b29b20
YZ		 1706 if (ins_len > 0 &&
1707 btrfs_leaf_free_space(root, b) < ins_len) {
b4ce94de
CM		 1708 int sret;
1709
1710 btrfs_set_path_blocking(p);
1711 sret = split_leaf(trans, root, key,
cc0c5538 1712 p, ins_len, ret == 0);
4008c04a 1713 btrfs_clear_path_blocking(p, NULL);
b4ce94de 1714
5c680ed6 1715 BUG_ON(sret > 0);
65b51a00
CM		 1716 if (sret) {
1717 ret = sret;
1718 goto done;
1719 }
5c680ed6 1720 }
459931ec
CM		 1721 if (!p->search_for_split)
1722 unlock_up(p, level, lowest_unlock);
65b51a00 1723 goto done;
be0e5c09
CM		 1724 }
1725 }
65b51a00
CM		 1726 ret = 1;
1727done:
b4ce94de
CM		 1728 /*
1729 * we don't really know what they plan on doing with the path
1730 * from here on, so for now just mark it as blocking
1731 */
b9473439
CM		 1732 if (!p->leave_spinning)
1733 btrfs_set_path_blocking(p);
65b51a00 1734 return ret;
be0e5c09
CM		 1735}
1736
1a40e23b
ZY		 1737int btrfs_merge_path(struct btrfs_trans_handle *trans,
1738 struct btrfs_root *root,
1739 struct btrfs_key *node_keys,
1740 u64 *nodes, int lowest_level)
1741{
1742 struct extent_buffer *eb;
1743 struct extent_buffer *parent;
1744 struct btrfs_key key;
1745 u64 bytenr;
1746 u64 generation;
1747 u32 blocksize;
1748 int level;
1749 int slot;
1750 int key_match;
1751 int ret;
1752
1753 eb = btrfs_lock_root_node(root);
9fa8cfe7 1754 ret = btrfs_cow_block(trans, root, eb, NULL, 0, &eb);
1a40e23b
ZY		 1755 BUG_ON(ret);
1756
b4ce94de
CM		 1757 btrfs_set_lock_blocking(eb);
1758
1a40e23b
ZY		 1759 parent = eb;
1760 while (1) {
1761 level = btrfs_header_level(parent);
1762 if (level == 0 || level <= lowest_level)
1763 break;
1764
1765 ret = bin_search(parent, &node_keys[lowest_level], level,
1766 &slot);
1767 if (ret && slot > 0)
1768 slot--;
1769
1770 bytenr = btrfs_node_blockptr(parent, slot);
1771 if (nodes[level - 1] == bytenr)
1772 break;
1773
1774 blocksize = btrfs_level_size(root, level - 1);
1775 generation = btrfs_node_ptr_generation(parent, slot);
1776 btrfs_node_key_to_cpu(eb, &key, slot);
1777 key_match = !memcmp(&key, &node_keys[level - 1], sizeof(key));
1778
f82d02d9
YZ		 1779 if (generation == trans->transid) {
1780 eb = read_tree_block(root, bytenr, blocksize,
1781 generation);
1782 btrfs_tree_lock(eb);
b4ce94de 1783 btrfs_set_lock_blocking(eb);
f82d02d9
YZ		 1784 }
1785
1a40e23b
ZY		 1786 /*
1787 * if node keys match and node pointer hasn't been modified
1788 * in the running transaction, we can merge the path. for
f82d02d9
YZ		 1789 * blocks owened by reloc trees, the node pointer check is
1790 * skipped, this is because these blocks are fully controlled
1791 * by the space balance code, no one else can modify them.
1a40e23b
ZY		 1792 */
1793 if (!nodes[level - 1] || !key_match ||
1794 (generation == trans->transid &&
f82d02d9
YZ		 1795 btrfs_header_owner(eb) != BTRFS_TREE_RELOC_OBJECTID)) {
1796 if (level == 1 || level == lowest_level + 1) {
1797 if (generation == trans->transid) {
1798 btrfs_tree_unlock(eb);
1799 free_extent_buffer(eb);
1800 }
1a40e23b 1801 break;
f82d02d9 1802 }
1a40e23b 1803
f82d02d9
YZ		 1804 if (generation != trans->transid) {
1805 eb = read_tree_block(root, bytenr, blocksize,
1806 generation);
1807 btrfs_tree_lock(eb);
b4ce94de 1808 btrfs_set_lock_blocking(eb);
f82d02d9 1809 }
1a40e23b
ZY		 1810
1811 ret = btrfs_cow_block(trans, root, eb, parent, slot,
9fa8cfe7 1812 &eb);
1a40e23b
ZY		 1813 BUG_ON(ret);
1814
f82d02d9
YZ		 1815 if (root->root_key.objectid ==
1816 BTRFS_TREE_RELOC_OBJECTID) {
1817 if (!nodes[level - 1]) {
1818 nodes[level - 1] = eb->start;
1819 memcpy(&node_keys[level - 1], &key,
1820 sizeof(node_keys[0]));
1821 } else {
1822 WARN_ON(1);
1823 }
1824 }
1825
1a40e23b
ZY		 1826 btrfs_tree_unlock(parent);
1827 free_extent_buffer(parent);
1828 parent = eb;
1829 continue;
1830 }
1831
1a40e23b
ZY		 1832 btrfs_set_node_blockptr(parent, slot, nodes[level - 1]);
1833 btrfs_set_node_ptr_generation(parent, slot, trans->transid);
1834 btrfs_mark_buffer_dirty(parent);
1835
1836 ret = btrfs_inc_extent_ref(trans, root,
1837 nodes[level - 1],
1838 blocksize, parent->start,
1839 btrfs_header_owner(parent),
1840 btrfs_header_generation(parent),
3bb1a1bc 1841 level - 1);
1a40e23b 1842 BUG_ON(ret);
1a40e23b 1843
f82d02d9
YZ		 1844 /*
1845 * If the block was created in the running transaction,
1846 * it's possible this is the last reference to it, so we
1847 * should drop the subtree.
1848 */
1a40e23b 1849 if (generation == trans->transid) {
f82d02d9
YZ		 1850 ret = btrfs_drop_subtree(trans, root, eb, parent);
1851 BUG_ON(ret);
1a40e23b
ZY		 1852 btrfs_tree_unlock(eb);
1853 free_extent_buffer(eb);
f82d02d9
YZ		 1854 } else {
1855 ret = btrfs_free_extent(trans, root, bytenr,
1856 blocksize, parent->start,
1857 btrfs_header_owner(parent),
1858 btrfs_header_generation(parent),
1859 level - 1, 1);
1860 BUG_ON(ret);
1a40e23b
ZY		 1861 }
1862 break;
1863 }
1864 btrfs_tree_unlock(parent);
1865 free_extent_buffer(parent);
1866 return 0;
1867}
1868
74123bd7
CM		 1869/*
1870 * adjust the pointers going up the tree, starting at level
1871 * making sure the right key of each node is points to 'key'.
1872 * This is used after shifting pointers to the left, so it stops
1873 * fixing up pointers when a given leaf/node is not in slot 0 of the
1874 * higher levels
aa5d6bed
CM		 1875 *
1876 * If this fails to write a tree block, it returns -1, but continues
1877 * fixing up the blocks in ram so the tree is consistent.
74123bd7 1878 */
5f39d397
CM		 1879static int fixup_low_keys(struct btrfs_trans_handle *trans,
1880 struct btrfs_root *root, struct btrfs_path *path,
1881 struct btrfs_disk_key *key, int level)
be0e5c09
CM		 1882{
1883 int i;
aa5d6bed 1884 int ret = 0;
5f39d397
CM		 1885 struct extent_buffer *t;
1886
234b63a0 1887 for (i = level; i < BTRFS_MAX_LEVEL; i++) {
be0e5c09 1888 int tslot = path->slots[i];
eb60ceac 1889 if (!path->nodes[i])
be0e5c09 1890 break;
5f39d397
CM		 1891 t = path->nodes[i];
1892 btrfs_set_node_key(t, key, tslot);
d6025579 1893 btrfs_mark_buffer_dirty(path->nodes[i]);
be0e5c09
CM		 1894 if (tslot != 0)
1895 break;
1896 }
aa5d6bed 1897 return ret;
be0e5c09
CM		 1898}
1899
31840ae1
ZY		 1900/*
1901 * update item key.
1902 *
1903 * This function isn't completely safe. It's the caller's responsibility
1904 * that the new key won't break the order
1905 */
1906int btrfs_set_item_key_safe(struct btrfs_trans_handle *trans,
1907 struct btrfs_root *root, struct btrfs_path *path,
1908 struct btrfs_key *new_key)
1909{
1910 struct btrfs_disk_key disk_key;
1911 struct extent_buffer *eb;
1912 int slot;
1913
1914 eb = path->nodes[0];
1915 slot = path->slots[0];
1916 if (slot > 0) {
1917 btrfs_item_key(eb, &disk_key, slot - 1);
1918 if (comp_keys(&disk_key, new_key) >= 0)
1919 return -1;
1920 }
1921 if (slot < btrfs_header_nritems(eb) - 1) {
1922 btrfs_item_key(eb, &disk_key, slot + 1);
1923 if (comp_keys(&disk_key, new_key) <= 0)
1924 return -1;
1925 }
1926
1927 btrfs_cpu_key_to_disk(&disk_key, new_key);
1928 btrfs_set_item_key(eb, &disk_key, slot);
1929 btrfs_mark_buffer_dirty(eb);
1930 if (slot == 0)
1931 fixup_low_keys(trans, root, path, &disk_key, 1);
1932 return 0;
1933}
1934
74123bd7
CM		 1935/*
1936 * try to push data from one node into the next node left in the
79f95c82 1937 * tree.
aa5d6bed
CM		 1938 *
1939 * returns 0 if some ptrs were pushed left, < 0 if there was some horrible
1940 * error, and > 0 if there was no room in the left hand block.
74123bd7 1941 */
98ed5174
CM		 1942static int push_node_left(struct btrfs_trans_handle *trans,
1943 struct btrfs_root *root, struct extent_buffer *dst,
971a1f66 1944 struct extent_buffer *src, int empty)
be0e5c09 1945{
be0e5c09 1946 int push_items = 0;
bb803951
CM		 1947 int src_nritems;
1948 int dst_nritems;
aa5d6bed 1949 int ret = 0;
be0e5c09 1950
5f39d397
CM		 1951 src_nritems = btrfs_header_nritems(src);
1952 dst_nritems = btrfs_header_nritems(dst);
123abc88 1953 push_items = BTRFS_NODEPTRS_PER_BLOCK(root) - dst_nritems;
7bb86316
CM		 1954 WARN_ON(btrfs_header_generation(src) != trans->transid);
1955 WARN_ON(btrfs_header_generation(dst) != trans->transid);
54aa1f4d 1956
bce4eae9 1957 if (!empty && src_nritems <= 8)
971a1f66
CM		 1958 return 1;
1959
d397712b 1960 if (push_items <= 0)
be0e5c09
CM		 1961 return 1;
1962
bce4eae9 1963 if (empty) {
971a1f66 1964 push_items = min(src_nritems, push_items);
bce4eae9
CM		 1965 if (push_items < src_nritems) {
1966 /* leave at least 8 pointers in the node if
1967 * we aren't going to empty it
1968 */
1969 if (src_nritems - push_items < 8) {
1970 if (push_items <= 8)
1971 return 1;
1972 push_items -= 8;
1973 }
1974 }
1975 } else
1976 push_items = min(src_nritems - 8, push_items);
79f95c82 1977
5f39d397
CM		 1978 copy_extent_buffer(dst, src,
1979 btrfs_node_key_ptr_offset(dst_nritems),
1980 btrfs_node_key_ptr_offset(0),
d397712b 1981 push_items * sizeof(struct btrfs_key_ptr));
5f39d397 1982
bb803951 1983 if (push_items < src_nritems) {
5f39d397
CM		 1984 memmove_extent_buffer(src, btrfs_node_key_ptr_offset(0),
1985 btrfs_node_key_ptr_offset(push_items),
1986 (src_nritems - push_items) *
1987 sizeof(struct btrfs_key_ptr));
1988 }
1989 btrfs_set_header_nritems(src, src_nritems - push_items);
1990 btrfs_set_header_nritems(dst, dst_nritems + push_items);
1991 btrfs_mark_buffer_dirty(src);
1992 btrfs_mark_buffer_dirty(dst);
31840ae1
ZY		 1993
1994 ret = btrfs_update_ref(trans, root, src, dst, dst_nritems, push_items);
1995 BUG_ON(ret);
1996
79f95c82
CM		 1997 return ret;
1998}
1999
2000/*
2001 * try to push data from one node into the next node right in the
2002 * tree.
2003 *
2004 * returns 0 if some ptrs were pushed, < 0 if there was some horrible
2005 * error, and > 0 if there was no room in the right hand block.
2006 *
2007 * this will only push up to 1/2 the contents of the left node over
2008 */
5f39d397
CM		 2009static int balance_node_right(struct btrfs_trans_handle *trans,
2010 struct btrfs_root *root,
2011 struct extent_buffer *dst,
2012 struct extent_buffer *src)
79f95c82 2013{
79f95c82
CM		 2014 int push_items = 0;
2015 int max_push;
2016 int src_nritems;
2017 int dst_nritems;
2018 int ret = 0;
79f95c82 2019
7bb86316
CM		 2020 WARN_ON(btrfs_header_generation(src) != trans->transid);
2021 WARN_ON(btrfs_header_generation(dst) != trans->transid);
2022
5f39d397
CM		 2023 src_nritems = btrfs_header_nritems(src);
2024 dst_nritems = btrfs_header_nritems(dst);
123abc88 2025 push_items = BTRFS_NODEPTRS_PER_BLOCK(root) - dst_nritems;
d397712b 2026 if (push_items <= 0)
79f95c82 2027 return 1;
bce4eae9 2028
d397712b 2029 if (src_nritems < 4)
bce4eae9 2030 return 1;
79f95c82
CM		 2031
2032 max_push = src_nritems / 2 + 1;
2033 /* don't try to empty the node */
d397712b 2034 if (max_push >= src_nritems)
79f95c82 2035 return 1;
252c38f0 2036
79f95c82
CM		 2037 if (max_push < push_items)
2038 push_items = max_push;
2039
5f39d397
CM		 2040 memmove_extent_buffer(dst, btrfs_node_key_ptr_offset(push_items),
2041 btrfs_node_key_ptr_offset(0),
2042 (dst_nritems) *
2043 sizeof(struct btrfs_key_ptr));
d6025579 2044
5f39d397
CM		 2045 copy_extent_buffer(dst, src,
2046 btrfs_node_key_ptr_offset(0),
2047 btrfs_node_key_ptr_offset(src_nritems - push_items),
d397712b 2048 push_items * sizeof(struct btrfs_key_ptr));
79f95c82 2049
5f39d397
CM		 2050 btrfs_set_header_nritems(src, src_nritems - push_items);
2051 btrfs_set_header_nritems(dst, dst_nritems + push_items);
79f95c82 2052
5f39d397
CM		 2053 btrfs_mark_buffer_dirty(src);
2054 btrfs_mark_buffer_dirty(dst);
31840ae1
ZY		 2055
2056 ret = btrfs_update_ref(trans, root, src, dst, 0, push_items);
2057 BUG_ON(ret);
2058
aa5d6bed 2059 return ret;
be0e5c09
CM		 2060}
2061
97571fd0
CM		 2062/*
2063 * helper function to insert a new root level in the tree.
2064 * A new node is allocated, and a single item is inserted to
2065 * point to the existing root
aa5d6bed
CM		 2066 *
2067 * returns zero on success or < 0 on failure.
97571fd0 2068 */
d397712b 2069static noinline int insert_new_root(struct btrfs_trans_handle *trans,
5f39d397
CM		 2070 struct btrfs_root *root,
2071 struct btrfs_path *path, int level)
5c680ed6 2072{
7bb86316 2073 u64 lower_gen;
5f39d397
CM		 2074 struct extent_buffer *lower;
2075 struct extent_buffer *c;
925baedd 2076 struct extent_buffer *old;
5f39d397 2077 struct btrfs_disk_key lower_key;
31840ae1 2078 int ret;
5c680ed6
CM		 2079
2080 BUG_ON(path->nodes[level]);
2081 BUG_ON(path->nodes[level-1] != root->node);
2082
7bb86316
CM		 2083 lower = path->nodes[level-1];
2084 if (level == 1)
2085 btrfs_item_key(lower, &lower_key, 0);
2086 else
2087 btrfs_node_key(lower, &lower_key, 0);
2088
31840ae1
ZY		 2089 c = btrfs_alloc_free_block(trans, root, root->nodesize, 0,
2090 root->root_key.objectid, trans->transid,
ad3d81ba 2091 level, root->node->start, 0);
5f39d397
CM		 2092 if (IS_ERR(c))
2093 return PTR_ERR(c);
925baedd 2094
5f39d397
CM		 2095 memset_extent_buffer(c, 0, 0, root->nodesize);
2096 btrfs_set_header_nritems(c, 1);
2097 btrfs_set_header_level(c, level);
db94535d 2098 btrfs_set_header_bytenr(c, c->start);
5f39d397
CM		 2099 btrfs_set_header_generation(c, trans->transid);
2100 btrfs_set_header_owner(c, root->root_key.objectid);
5f39d397
CM		 2101
2102 write_extent_buffer(c, root->fs_info->fsid,
2103 (unsigned long)btrfs_header_fsid(c),
2104 BTRFS_FSID_SIZE);
e17cade2
CM		 2105
2106 write_extent_buffer(c, root->fs_info->chunk_tree_uuid,
2107 (unsigned long)btrfs_header_chunk_tree_uuid(c),
2108 BTRFS_UUID_SIZE);
2109
5f39d397 2110 btrfs_set_node_key(c, &lower_key, 0);
db94535d 2111 btrfs_set_node_blockptr(c, 0, lower->start);
7bb86316 2112 lower_gen = btrfs_header_generation(lower);
31840ae1 2113 WARN_ON(lower_gen != trans->transid);
7bb86316
CM		 2114
2115 btrfs_set_node_ptr_generation(c, 0, lower_gen);
d5719762 2116
5f39d397 2117 btrfs_mark_buffer_dirty(c);
d5719762 2118
925baedd
CM		 2119 spin_lock(&root->node_lock);
2120 old = root->node;
5f39d397 2121 root->node = c;
925baedd
CM		 2122 spin_unlock(&root->node_lock);
2123
31840ae1 2124 ret = btrfs_update_extent_ref(trans, root, lower->start,
56bec294 2125 lower->len, lower->start, c->start,
31840ae1 2126 root->root_key.objectid,
3bb1a1bc 2127 trans->transid, level - 1);
31840ae1
ZY		 2128 BUG_ON(ret);
2129
925baedd
CM		 2130 /* the super has an extra ref to root->node */
2131 free_extent_buffer(old);
2132
0b86a832 2133 add_root_to_dirty_list(root);
5f39d397
CM		 2134 extent_buffer_get(c);
2135 path->nodes[level] = c;
925baedd 2136 path->locks[level] = 1;
5c680ed6
CM		 2137 path->slots[level] = 0;
2138 return 0;
2139}
2140
74123bd7
CM		 2141/*
2142 * worker function to insert a single pointer in a node.
2143 * the node should have enough room for the pointer already
97571fd0 2144 *
74123bd7
CM		 2145 * slot and level indicate where you want the key to go, and
2146 * blocknr is the block the key points to.
aa5d6bed
CM		 2147 *
2148 * returns zero on success and < 0 on any error
74123bd7 2149 */
e089f05c
CM		 2150static int insert_ptr(struct btrfs_trans_handle *trans, struct btrfs_root
2151 *root, struct btrfs_path *path, struct btrfs_disk_key
db94535d 2152 *key, u64 bytenr, int slot, int level)
74123bd7 2153{
5f39d397 2154 struct extent_buffer *lower;
74123bd7 2155 int nritems;
5c680ed6
CM		 2156
2157 BUG_ON(!path->nodes[level]);
5f39d397
CM		 2158 lower = path->nodes[level];
2159 nritems = btrfs_header_nritems(lower);
74123bd7
CM		 2160 if (slot > nritems)
2161 BUG();
123abc88 2162 if (nritems == BTRFS_NODEPTRS_PER_BLOCK(root))
74123bd7
CM		 2163 BUG();
2164 if (slot != nritems) {
5f39d397
CM		 2165 memmove_extent_buffer(lower,
2166 btrfs_node_key_ptr_offset(slot + 1),
2167 btrfs_node_key_ptr_offset(slot),
d6025579 2168 (nritems - slot) * sizeof(struct btrfs_key_ptr));
74123bd7 2169 }
5f39d397 2170 btrfs_set_node_key(lower, key, slot);
db94535d 2171 btrfs_set_node_blockptr(lower, slot, bytenr);
74493f7a
CM		 2172 WARN_ON(trans->transid == 0);
2173 btrfs_set_node_ptr_generation(lower, slot, trans->transid);
5f39d397
CM		 2174 btrfs_set_header_nritems(lower, nritems + 1);
2175 btrfs_mark_buffer_dirty(lower);
74123bd7
CM		 2176 return 0;
2177}
2178
97571fd0
CM		 2179/*
2180 * split the node at the specified level in path in two.
2181 * The path is corrected to point to the appropriate node after the split
2182 *
2183 * Before splitting this tries to make some room in the node by pushing
2184 * left and right, if either one works, it returns right away.
aa5d6bed
CM		 2185 *
2186 * returns 0 on success and < 0 on failure
97571fd0 2187 */
e02119d5
CM		 2188static noinline int split_node(struct btrfs_trans_handle *trans,
2189 struct btrfs_root *root,
2190 struct btrfs_path *path, int level)
be0e5c09 2191{
5f39d397
CM		 2192 struct extent_buffer *c;
2193 struct extent_buffer *split;
2194 struct btrfs_disk_key disk_key;
be0e5c09 2195 int mid;
5c680ed6 2196 int ret;
aa5d6bed 2197 int wret;
7518a238 2198 u32 c_nritems;
eb60ceac 2199
5f39d397 2200 c = path->nodes[level];
7bb86316 2201 WARN_ON(btrfs_header_generation(c) != trans->transid);
5f39d397 2202 if (c == root->node) {
5c680ed6 2203 /* trying to split the root, lets make a new one */
e089f05c 2204 ret = insert_new_root(trans, root, path, level + 1);
5c680ed6
CM		 2205 if (ret)
2206 return ret;
a4b6e07d 2207 } else if (!trans->transaction->delayed_refs.flushing) {
e66f709b 2208 ret = push_nodes_for_insert(trans, root, path, level);
5f39d397
CM		 2209 c = path->nodes[level];
2210 if (!ret && btrfs_header_nritems(c) <
c448acf0 2211 BTRFS_NODEPTRS_PER_BLOCK(root) - 3)
e66f709b 2212 return 0;
54aa1f4d
CM		 2213 if (ret < 0)
2214 return ret;
be0e5c09 2215 }
e66f709b 2216
5f39d397 2217 c_nritems = btrfs_header_nritems(c);
7bb86316 2218
925baedd 2219 split = btrfs_alloc_free_block(trans, root, root->nodesize,
31840ae1
ZY		 2220 path->nodes[level + 1]->start,
2221 root->root_key.objectid,
2222 trans->transid, level, c->start, 0);
5f39d397
CM		 2223 if (IS_ERR(split))
2224 return PTR_ERR(split);
2225
2226 btrfs_set_header_flags(split, btrfs_header_flags(c));
2227 btrfs_set_header_level(split, btrfs_header_level(c));
db94535d 2228 btrfs_set_header_bytenr(split, split->start);
5f39d397
CM		 2229 btrfs_set_header_generation(split, trans->transid);
2230 btrfs_set_header_owner(split, root->root_key.objectid);
63b10fc4 2231 btrfs_set_header_flags(split, 0);
5f39d397
CM		 2232 write_extent_buffer(split, root->fs_info->fsid,
2233 (unsigned long)btrfs_header_fsid(split),
2234 BTRFS_FSID_SIZE);
e17cade2
CM		 2235 write_extent_buffer(split, root->fs_info->chunk_tree_uuid,
2236 (unsigned long)btrfs_header_chunk_tree_uuid(split),
2237 BTRFS_UUID_SIZE);
54aa1f4d 2238
7518a238 2239 mid = (c_nritems + 1) / 2;
5f39d397
CM		 2240
2241 copy_extent_buffer(split, c,
2242 btrfs_node_key_ptr_offset(0),
2243 btrfs_node_key_ptr_offset(mid),
2244 (c_nritems - mid) * sizeof(struct btrfs_key_ptr));
2245 btrfs_set_header_nritems(split, c_nritems - mid);
2246 btrfs_set_header_nritems(c, mid);
aa5d6bed
CM		 2247 ret = 0;
2248
5f39d397
CM		 2249 btrfs_mark_buffer_dirty(c);
2250 btrfs_mark_buffer_dirty(split);
2251
2252 btrfs_node_key(split, &disk_key, 0);
db94535d 2253 wret = insert_ptr(trans, root, path, &disk_key, split->start,
5f39d397 2254 path->slots[level + 1] + 1,
123abc88 2255 level + 1);
aa5d6bed
CM		 2256 if (wret)
2257 ret = wret;
2258
31840ae1
ZY		 2259 ret = btrfs_update_ref(trans, root, c, split, 0, c_nritems - mid);
2260 BUG_ON(ret);
2261
5de08d7d 2262 if (path->slots[level] >= mid) {
5c680ed6 2263 path->slots[level] -= mid;
925baedd 2264 btrfs_tree_unlock(c);
5f39d397
CM		 2265 free_extent_buffer(c);
2266 path->nodes[level] = split;
5c680ed6
CM		 2267 path->slots[level + 1] += 1;
2268 } else {
925baedd 2269 btrfs_tree_unlock(split);
5f39d397 2270 free_extent_buffer(split);
be0e5c09 2271 }
aa5d6bed 2272 return ret;
be0e5c09
CM		 2273}
2274
74123bd7
CM		 2275/*
2276 * how many bytes are required to store the items in a leaf. start
2277 * and nr indicate which items in the leaf to check. This totals up the
2278 * space used both by the item structs and the item data
2279 */
5f39d397 2280static int leaf_space_used(struct extent_buffer *l, int start, int nr)
be0e5c09
CM		 2281{
2282 int data_len;
5f39d397 2283 int nritems = btrfs_header_nritems(l);
d4dbff95 2284 int end = min(nritems, start + nr) - 1;
be0e5c09
CM		 2285
2286 if (!nr)
2287 return 0;
5f39d397
CM		 2288 data_len = btrfs_item_end_nr(l, start);
2289 data_len = data_len - btrfs_item_offset_nr(l, end);
0783fcfc 2290 data_len += sizeof(struct btrfs_item) * nr;
d4dbff95 2291 WARN_ON(data_len < 0);
be0e5c09
CM		 2292 return data_len;
2293}
2294
d4dbff95
CM		 2295/*
2296 * The space between the end of the leaf items and
2297 * the start of the leaf data. IOW, how much room
2298 * the leaf has left for both items and data
2299 */
d397712b 2300noinline int btrfs_leaf_free_space(struct btrfs_root *root,
e02119d5 2301 struct extent_buffer *leaf)
d4dbff95 2302{
5f39d397
CM		 2303 int nritems = btrfs_header_nritems(leaf);
2304 int ret;
2305 ret = BTRFS_LEAF_DATA_SIZE(root) - leaf_space_used(leaf, 0, nritems);
2306 if (ret < 0) {
d397712b
CM		 2307 printk(KERN_CRIT "leaf free space ret %d, leaf data size %lu, "
2308 "used %d nritems %d\n",
ae2f5411 2309 ret, (unsigned long) BTRFS_LEAF_DATA_SIZE(root),
5f39d397
CM		 2310 leaf_space_used(leaf, 0, nritems), nritems);
2311 }
2312 return ret;
d4dbff95
CM		 2313}
2314
44871b1b
CM		 2315static noinline int __push_leaf_right(struct btrfs_trans_handle *trans,
2316 struct btrfs_root *root,
2317 struct btrfs_path *path,
2318 int data_size, int empty,
2319 struct extent_buffer *right,
2320 int free_space, u32 left_nritems)
00ec4c51 2321{
5f39d397 2322 struct extent_buffer *left = path->nodes[0];
44871b1b 2323 struct extent_buffer *upper = path->nodes[1];
5f39d397 2324 struct btrfs_disk_key disk_key;
00ec4c51 2325 int slot;
34a38218 2326 u32 i;
00ec4c51
CM		 2327 int push_space = 0;
2328 int push_items = 0;
0783fcfc 2329 struct btrfs_item *item;
34a38218 2330 u32 nr;
7518a238 2331 u32 right_nritems;
5f39d397 2332 u32 data_end;
db94535d 2333 u32 this_item_size;
54aa1f4d 2334 int ret;
00ec4c51 2335
34a38218
CM		 2336 if (empty)
2337 nr = 0;
2338 else
2339 nr = 1;
2340
31840ae1 2341 if (path->slots[0] >= left_nritems)
87b29b20 2342 push_space += data_size;
31840ae1 2343
44871b1b 2344 slot = path->slots[1];
34a38218
CM		 2345 i = left_nritems - 1;
2346 while (i >= nr) {
5f39d397 2347 item = btrfs_item_nr(left, i);
db94535d 2348
31840ae1
ZY		 2349 if (!empty && push_items > 0) {
2350 if (path->slots[0] > i)
2351 break;
2352 if (path->slots[0] == i) {
2353 int space = btrfs_leaf_free_space(root, left);
2354 if (space + push_space * 2 > free_space)
2355 break;
2356 }
2357 }
2358
00ec4c51 2359 if (path->slots[0] == i)
87b29b20 2360 push_space += data_size;
db94535d
CM		 2361
2362 if (!left->map_token) {
2363 map_extent_buffer(left, (unsigned long)item,
2364 sizeof(struct btrfs_item),
2365 &left->map_token, &left->kaddr,
2366 &left->map_start, &left->map_len,
2367 KM_USER1);
2368 }
2369
2370 this_item_size = btrfs_item_size(left, item);
2371 if (this_item_size + sizeof(*item) + push_space > free_space)
00ec4c51 2372 break;
31840ae1 2373
00ec4c51 2374 push_items++;
db94535d 2375 push_space += this_item_size + sizeof(*item);
34a38218
CM		 2376 if (i == 0)
2377 break;
2378 i--;
db94535d
CM		 2379 }
2380 if (left->map_token) {
2381 unmap_extent_buffer(left, left->map_token, KM_USER1);
2382 left->map_token = NULL;
00ec4c51 2383 }
5f39d397 2384
925baedd
CM		 2385 if (push_items == 0)
2386 goto out_unlock;
5f39d397 2387
34a38218 2388 if (!empty && push_items == left_nritems)
a429e513 2389 WARN_ON(1);
5f39d397 2390
00ec4c51 2391 /* push left to right */
5f39d397 2392 right_nritems = btrfs_header_nritems(right);
34a38218 2393
5f39d397 2394 push_space = btrfs_item_end_nr(left, left_nritems - push_items);
123abc88 2395 push_space -= leaf_data_end(root, left);
5f39d397 2396
00ec4c51 2397 /* make room in the right data area */
5f39d397
CM		 2398 data_end = leaf_data_end(root, right);
2399 memmove_extent_buffer(right,
2400 btrfs_leaf_data(right) + data_end - push_space,
2401 btrfs_leaf_data(right) + data_end,
2402 BTRFS_LEAF_DATA_SIZE(root) - data_end);
2403
00ec4c51 2404 /* copy from the left data area */
5f39d397 2405 copy_extent_buffer(right, left, btrfs_leaf_data(right) +
d6025579
CM		 2406 BTRFS_LEAF_DATA_SIZE(root) - push_space,
2407 btrfs_leaf_data(left) + leaf_data_end(root, left),
2408 push_space);
5f39d397
CM		 2409
2410 memmove_extent_buffer(right, btrfs_item_nr_offset(push_items),
2411 btrfs_item_nr_offset(0),
2412 right_nritems * sizeof(struct btrfs_item));
2413
00ec4c51 2414 /* copy the items from left to right */
5f39d397
CM		 2415 copy_extent_buffer(right, left, btrfs_item_nr_offset(0),
2416 btrfs_item_nr_offset(left_nritems - push_items),
2417 push_items * sizeof(struct btrfs_item));
00ec4c51
CM		 2418
2419 /* update the item pointers */
7518a238 2420 right_nritems += push_items;
5f39d397 2421 btrfs_set_header_nritems(right, right_nritems);
123abc88 2422 push_space = BTRFS_LEAF_DATA_SIZE(root);
7518a238 2423 for (i = 0; i < right_nritems; i++) {
5f39d397 2424 item = btrfs_item_nr(right, i);
db94535d
CM		 2425 if (!right->map_token) {
2426 map_extent_buffer(right, (unsigned long)item,
2427 sizeof(struct btrfs_item),
2428 &right->map_token, &right->kaddr,
2429 &right->map_start, &right->map_len,
2430 KM_USER1);
2431 }
2432 push_space -= btrfs_item_size(right, item);
2433 btrfs_set_item_offset(right, item, push_space);
2434 }
2435
2436 if (right->map_token) {
2437 unmap_extent_buffer(right, right->map_token, KM_USER1);
2438 right->map_token = NULL;
00ec4c51 2439 }
7518a238 2440 left_nritems -= push_items;
5f39d397 2441 btrfs_set_header_nritems(left, left_nritems);
00ec4c51 2442
34a38218
CM		 2443 if (left_nritems)
2444 btrfs_mark_buffer_dirty(left);
5f39d397 2445 btrfs_mark_buffer_dirty(right);
a429e513 2446
31840ae1
ZY		 2447 ret = btrfs_update_ref(trans, root, left, right, 0, push_items);
2448 BUG_ON(ret);
2449
5f39d397
CM		 2450 btrfs_item_key(right, &disk_key, 0);
2451 btrfs_set_node_key(upper, &disk_key, slot + 1);
d6025579 2452 btrfs_mark_buffer_dirty(upper);
02217ed2 2453
00ec4c51 2454 /* then fixup the leaf pointer in the path */
7518a238
CM		 2455 if (path->slots[0] >= left_nritems) {
2456 path->slots[0] -= left_nritems;
925baedd
CM		 2457 if (btrfs_header_nritems(path->nodes[0]) == 0)
2458 clean_tree_block(trans, root, path->nodes[0]);
2459 btrfs_tree_unlock(path->nodes[0]);
5f39d397
CM		 2460 free_extent_buffer(path->nodes[0]);
2461 path->nodes[0] = right;
00ec4c51
CM		 2462 path->slots[1] += 1;
2463 } else {
925baedd 2464 btrfs_tree_unlock(right);
5f39d397 2465 free_extent_buffer(right);
00ec4c51
CM		 2466 }
2467 return 0;
925baedd
CM		 2468
2469out_unlock:
2470 btrfs_tree_unlock(right);
2471 free_extent_buffer(right);
2472 return 1;
00ec4c51 2473}
925baedd 2474
44871b1b
CM		 2475/*
2476 * push some data in the path leaf to the right, trying to free up at
2477 * least data_size bytes. returns zero if the push worked, nonzero otherwise
2478 *
2479 * returns 1 if the push failed because the other node didn't have enough
2480 * room, 0 if everything worked out and < 0 if there were major errors.
2481 */
2482static int push_leaf_right(struct btrfs_trans_handle *trans, struct btrfs_root
2483 *root, struct btrfs_path *path, int data_size,
2484 int empty)
2485{
2486 struct extent_buffer *left = path->nodes[0];
2487 struct extent_buffer *right;
2488 struct extent_buffer *upper;
2489 int slot;
2490 int free_space;
2491 u32 left_nritems;
2492 int ret;
2493
2494 if (!path->nodes[1])
2495 return 1;
2496
2497 slot = path->slots[1];
2498 upper = path->nodes[1];
2499 if (slot >= btrfs_header_nritems(upper) - 1)
2500 return 1;
2501
2502 btrfs_assert_tree_locked(path->nodes[1]);
2503
2504 right = read_node_slot(root, upper, slot + 1);
2505 btrfs_tree_lock(right);
2506 btrfs_set_lock_blocking(right);
2507
2508 free_space = btrfs_leaf_free_space(root, right);
2509 if (free_space < data_size)
2510 goto out_unlock;
2511
2512 /* cow and double check */
2513 ret = btrfs_cow_block(trans, root, right, upper,
2514 slot + 1, &right);
2515 if (ret)
2516 goto out_unlock;
2517
2518 free_space = btrfs_leaf_free_space(root, right);
2519 if (free_space < data_size)
2520 goto out_unlock;
2521
2522 left_nritems = btrfs_header_nritems(left);
2523 if (left_nritems == 0)
2524 goto out_unlock;
2525
2526 return __push_leaf_right(trans, root, path, data_size, empty,
2527 right, free_space, left_nritems);
2528out_unlock:
2529 btrfs_tree_unlock(right);
2530 free_extent_buffer(right);
2531 return 1;
2532}
2533
74123bd7
CM		 2534/*
2535 * push some data in the path leaf to the left, trying to free up at
2536 * least data_size bytes. returns zero if the push worked, nonzero otherwise
2537 */
44871b1b
CM		 2538static noinline int __push_leaf_left(struct btrfs_trans_handle *trans,
2539 struct btrfs_root *root,
2540 struct btrfs_path *path, int data_size,
2541 int empty, struct extent_buffer *left,
2542 int free_space, int right_nritems)
be0e5c09 2543{
5f39d397
CM		 2544 struct btrfs_disk_key disk_key;
2545 struct extent_buffer *right = path->nodes[0];
be0e5c09
CM		 2546 int slot;
2547 int i;
be0e5c09
CM		 2548 int push_space = 0;
2549 int push_items = 0;
0783fcfc 2550 struct btrfs_item *item;
7518a238 2551 u32 old_left_nritems;
34a38218 2552 u32 nr;
aa5d6bed
CM		 2553 int ret = 0;
2554 int wret;
db94535d
CM		 2555 u32 this_item_size;
2556 u32 old_left_item_size;
be0e5c09
CM		 2557
2558 slot = path->slots[1];
02217ed2 2559
34a38218
CM		 2560 if (empty)
2561 nr = right_nritems;
2562 else
2563 nr = right_nritems - 1;
2564
2565 for (i = 0; i < nr; i++) {
5f39d397 2566 item = btrfs_item_nr(right, i);
db94535d
CM		 2567 if (!right->map_token) {
2568 map_extent_buffer(right, (unsigned long)item,
2569 sizeof(struct btrfs_item),
2570 &right->map_token, &right->kaddr,
2571 &right->map_start, &right->map_len,
2572 KM_USER1);
2573 }
2574
31840ae1
ZY		 2575 if (!empty && push_items > 0) {
2576 if (path->slots[0] < i)
2577 break;
2578 if (path->slots[0] == i) {
2579 int space = btrfs_leaf_free_space(root, right);
2580 if (space + push_space * 2 > free_space)
2581 break;
2582 }
2583 }
2584
be0e5c09 2585 if (path->slots[0] == i)
87b29b20 2586 push_space += data_size;
db94535d
CM		 2587
2588 this_item_size = btrfs_item_size(right, item);
2589 if (this_item_size + sizeof(*item) + push_space > free_space)
be0e5c09 2590 break;
db94535d 2591
be0e5c09 2592 push_items++;
db94535d
CM		 2593 push_space += this_item_size + sizeof(*item);
2594 }
2595
2596 if (right->map_token) {
2597 unmap_extent_buffer(right, right->map_token, KM_USER1);
2598 right->map_token = NULL;
be0e5c09 2599 }
db94535d 2600
be0e5c09 2601 if (push_items == 0) {
925baedd
CM		 2602 ret = 1;
2603 goto out;
be0e5c09 2604 }
34a38218 2605 if (!empty && push_items == btrfs_header_nritems(right))
a429e513 2606 WARN_ON(1);
5f39d397 2607
be0e5c09 2608 /* push data from right to left */
5f39d397
CM		 2609 copy_extent_buffer(left, right,
2610 btrfs_item_nr_offset(btrfs_header_nritems(left)),
2611 btrfs_item_nr_offset(0),
2612 push_items * sizeof(struct btrfs_item));
2613
123abc88 2614 push_space = BTRFS_LEAF_DATA_SIZE(root) -
d397712b 2615 btrfs_item_offset_nr(right, push_items - 1);
5f39d397
CM		 2616
2617 copy_extent_buffer(left, right, btrfs_leaf_data(left) +
d6025579
CM		 2618 leaf_data_end(root, left) - push_space,
2619 btrfs_leaf_data(right) +
5f39d397 2620 btrfs_item_offset_nr(right, push_items - 1),
d6025579 2621 push_space);
5f39d397 2622 old_left_nritems = btrfs_header_nritems(left);
87b29b20 2623 BUG_ON(old_left_nritems <= 0);
eb60ceac 2624
db94535d 2625 old_left_item_size = btrfs_item_offset_nr(left, old_left_nritems - 1);
0783fcfc 2626 for (i = old_left_nritems; i < old_left_nritems + push_items; i++) {
5f39d397 2627 u32 ioff;
db94535d 2628
5f39d397 2629 item = btrfs_item_nr(left, i);
db94535d
CM		 2630 if (!left->map_token) {
2631 map_extent_buffer(left, (unsigned long)item,
2632 sizeof(struct btrfs_item),
2633 &left->map_token, &left->kaddr,
2634 &left->map_start, &left->map_len,
2635 KM_USER1);
2636 }
2637
5f39d397
CM		 2638 ioff = btrfs_item_offset(left, item);
2639 btrfs_set_item_offset(left, item,
db94535d 2640 ioff - (BTRFS_LEAF_DATA_SIZE(root) - old_left_item_size));
be0e5c09 2641 }
5f39d397 2642 btrfs_set_header_nritems(left, old_left_nritems + push_items);
db94535d
CM		 2643 if (left->map_token) {
2644 unmap_extent_buffer(left, left->map_token, KM_USER1);
2645 left->map_token = NULL;
2646 }
be0e5c09
CM		 2647
2648 /* fixup right node */
34a38218 2649 if (push_items > right_nritems) {
d397712b
CM		 2650 printk(KERN_CRIT "push items %d nr %u\n", push_items,
2651 right_nritems);
34a38218
CM		 2652 WARN_ON(1);
2653 }
2654
2655 if (push_items < right_nritems) {
2656 push_space = btrfs_item_offset_nr(right, push_items - 1) -
2657 leaf_data_end(root, right);
2658 memmove_extent_buffer(right, btrfs_leaf_data(right) +
2659 BTRFS_LEAF_DATA_SIZE(root) - push_space,
2660 btrfs_leaf_data(right) +
2661 leaf_data_end(root, right), push_space);
2662
2663 memmove_extent_buffer(right, btrfs_item_nr_offset(0),
5f39d397
CM		 2664 btrfs_item_nr_offset(push_items),
2665 (btrfs_header_nritems(right) - push_items) *
2666 sizeof(struct btrfs_item));
34a38218 2667 }
eef1c494
Y		 2668 right_nritems -= push_items;
2669 btrfs_set_header_nritems(right, right_nritems);
123abc88 2670 push_space = BTRFS_LEAF_DATA_SIZE(root);
5f39d397
CM		 2671 for (i = 0; i < right_nritems; i++) {
2672 item = btrfs_item_nr(right, i);
db94535d
CM		 2673
2674 if (!right->map_token) {
2675 map_extent_buffer(right, (unsigned long)item,
2676 sizeof(struct btrfs_item),
2677 &right->map_token, &right->kaddr,
2678 &right->map_start, &right->map_len,
2679 KM_USER1);
2680 }
2681
2682 push_space = push_space - btrfs_item_size(right, item);
2683 btrfs_set_item_offset(right, item, push_space);
2684 }
2685 if (right->map_token) {
2686 unmap_extent_buffer(right, right->map_token, KM_USER1);
2687 right->map_token = NULL;
be0e5c09 2688 }
eb60ceac 2689
5f39d397 2690 btrfs_mark_buffer_dirty(left);
34a38218
CM		 2691 if (right_nritems)
2692 btrfs_mark_buffer_dirty(right);
098f59c2 2693
31840ae1
ZY		 2694 ret = btrfs_update_ref(trans, root, right, left,
2695 old_left_nritems, push_items);
2696 BUG_ON(ret);
2697
5f39d397
CM		 2698 btrfs_item_key(right, &disk_key, 0);
2699 wret = fixup_low_keys(trans, root, path, &disk_key, 1);
aa5d6bed
CM		 2700 if (wret)
2701 ret = wret;
be0e5c09
CM		 2702
2703 /* then fixup the leaf pointer in the path */
2704 if (path->slots[0] < push_items) {
2705 path->slots[0] += old_left_nritems;
925baedd
CM		 2706 if (btrfs_header_nritems(path->nodes[0]) == 0)
2707 clean_tree_block(trans, root, path->nodes[0]);
2708 btrfs_tree_unlock(path->nodes[0]);
5f39d397
CM		 2709 free_extent_buffer(path->nodes[0]);
2710 path->nodes[0] = left;
be0e5c09
CM		 2711 path->slots[1] -= 1;
2712 } else {
925baedd 2713 btrfs_tree_unlock(left);
5f39d397 2714 free_extent_buffer(left);
be0e5c09
CM		 2715 path->slots[0] -= push_items;
2716 }
eb60ceac 2717 BUG_ON(path->slots[0] < 0);
aa5d6bed 2718 return ret;
925baedd
CM		 2719out:
2720 btrfs_tree_unlock(left);
2721 free_extent_buffer(left);
2722 return ret;
be0e5c09
CM		 2723}
2724
44871b1b
CM		 2725/*
2726 * push some data in the path leaf to the left, trying to free up at
2727 * least data_size bytes. returns zero if the push worked, nonzero otherwise
2728 */
2729static int push_leaf_left(struct btrfs_trans_handle *trans, struct btrfs_root
2730 *root, struct btrfs_path *path, int data_size,
2731 int empty)
2732{
2733 struct extent_buffer *right = path->nodes[0];
2734 struct extent_buffer *left;
2735 int slot;
2736 int free_space;
2737 u32 right_nritems;
2738 int ret = 0;
2739
2740 slot = path->slots[1];
2741 if (slot == 0)
2742 return 1;
2743 if (!path->nodes[1])
2744 return 1;
2745
2746 right_nritems = btrfs_header_nritems(right);
2747 if (right_nritems == 0)
2748 return 1;
2749
2750 btrfs_assert_tree_locked(path->nodes[1]);
2751
2752 left = read_node_slot(root, path->nodes[1], slot - 1);
2753 btrfs_tree_lock(left);
2754 btrfs_set_lock_blocking(left);
2755
2756 free_space = btrfs_leaf_free_space(root, left);
2757 if (free_space < data_size) {
2758 ret = 1;
2759 goto out;
2760 }
2761
2762 /* cow and double check */
2763 ret = btrfs_cow_block(trans, root, left,
2764 path->nodes[1], slot - 1, &left);
2765 if (ret) {
2766 /* we hit -ENOSPC, but it isn't fatal here */
2767 ret = 1;
2768 goto out;
2769 }
2770
2771 free_space = btrfs_leaf_free_space(root, left);
2772 if (free_space < data_size) {
2773 ret = 1;
2774 goto out;
2775 }
2776
2777 return __push_leaf_left(trans, root, path, data_size,
2778 empty, left, free_space, right_nritems);
2779out:
2780 btrfs_tree_unlock(left);
2781 free_extent_buffer(left);
2782 return ret;
2783}
2784
2785/*
2786 * split the path's leaf in two, making sure there is at least data_size
2787 * available for the resulting leaf level of the path.
2788 *
2789 * returns 0 if all went well and < 0 on failure.
2790 */
2791static noinline int copy_for_split(struct btrfs_trans_handle *trans,
2792 struct btrfs_root *root,
2793 struct btrfs_path *path,
2794 struct extent_buffer *l,
2795 struct extent_buffer *right,
2796 int slot, int mid, int nritems)
2797{
2798 int data_copy_size;
2799 int rt_data_off;
2800 int i;
2801 int ret = 0;
2802 int wret;
2803 struct btrfs_disk_key disk_key;
2804
2805 nritems = nritems - mid;
2806 btrfs_set_header_nritems(right, nritems);
2807 data_copy_size = btrfs_item_end_nr(l, mid) - leaf_data_end(root, l);
2808
2809 copy_extent_buffer(right, l, btrfs_item_nr_offset(0),
2810 btrfs_item_nr_offset(mid),
2811 nritems * sizeof(struct btrfs_item));
2812
2813 copy_extent_buffer(right, l,
2814 btrfs_leaf_data(right) + BTRFS_LEAF_DATA_SIZE(root) -
2815 data_copy_size, btrfs_leaf_data(l) +
2816 leaf_data_end(root, l), data_copy_size);
2817
2818 rt_data_off = BTRFS_LEAF_DATA_SIZE(root) -
2819 btrfs_item_end_nr(l, mid);
2820
2821 for (i = 0; i < nritems; i++) {
2822 struct btrfs_item *item = btrfs_item_nr(right, i);
2823 u32 ioff;
2824
2825 if (!right->map_token) {
2826 map_extent_buffer(right, (unsigned long)item,
2827 sizeof(struct btrfs_item),
2828 &right->map_token, &right->kaddr,
2829 &right->map_start, &right->map_len,
2830 KM_USER1);
2831 }
2832
2833 ioff = btrfs_item_offset(right, item);
2834 btrfs_set_item_offset(right, item, ioff + rt_data_off);
2835 }
2836
2837 if (right->map_token) {
2838 unmap_extent_buffer(right, right->map_token, KM_USER1);
2839 right->map_token = NULL;
2840 }
2841
2842 btrfs_set_header_nritems(l, mid);
2843 ret = 0;
2844 btrfs_item_key(right, &disk_key, 0);
2845 wret = insert_ptr(trans, root, path, &disk_key, right->start,
2846 path->slots[1] + 1, 1);
2847 if (wret)
2848 ret = wret;
2849
2850 btrfs_mark_buffer_dirty(right);
2851 btrfs_mark_buffer_dirty(l);
2852 BUG_ON(path->slots[0] != slot);
2853
2854 ret = btrfs_update_ref(trans, root, l, right, 0, nritems);
2855 BUG_ON(ret);
2856
2857 if (mid <= slot) {
2858 btrfs_tree_unlock(path->nodes[0]);
2859 free_extent_buffer(path->nodes[0]);
2860 path->nodes[0] = right;
2861 path->slots[0] -= mid;
2862 path->slots[1] += 1;
2863 } else {
2864 btrfs_tree_unlock(right);
2865 free_extent_buffer(right);
2866 }
2867
2868 BUG_ON(path->slots[0] < 0);
2869
2870 return ret;
2871}
2872
74123bd7
CM		 2873/*
2874 * split the path's leaf in two, making sure there is at least data_size
2875 * available for the resulting leaf level of the path.
aa5d6bed
CM		 2876 *
2877 * returns 0 if all went well and < 0 on failure.
74123bd7 2878 */
e02119d5
CM		 2879static noinline int split_leaf(struct btrfs_trans_handle *trans,
2880 struct btrfs_root *root,
2881 struct btrfs_key *ins_key,
2882 struct btrfs_path *path, int data_size,
2883 int extend)
be0e5c09 2884{
5f39d397 2885 struct extent_buffer *l;
7518a238 2886 u32 nritems;
eb60ceac
CM		 2887 int mid;
2888 int slot;
5f39d397 2889 struct extent_buffer *right;
d4dbff95 2890 int ret = 0;
aa5d6bed 2891 int wret;
cc0c5538
CM		 2892 int double_split;
2893 int num_doubles = 0;
aa5d6bed 2894
40689478 2895 /* first try to make some room by pushing left and right */
a4b6e07d
CM		 2896 if (data_size && ins_key->type != BTRFS_DIR_ITEM_KEY &&
2897 !trans->transaction->delayed_refs.flushing) {
34a38218 2898 wret = push_leaf_right(trans, root, path, data_size, 0);
d397712b 2899 if (wret < 0)
eaee50e8 2900 return wret;
3685f791 2901 if (wret) {
34a38218 2902 wret = push_leaf_left(trans, root, path, data_size, 0);
3685f791
CM		 2903 if (wret < 0)
2904 return wret;
2905 }
2906 l = path->nodes[0];
aa5d6bed 2907
3685f791 2908 /* did the pushes work? */
87b29b20 2909 if (btrfs_leaf_free_space(root, l) >= data_size)
3685f791 2910 return 0;
3326d1b0 2911 }
aa5d6bed 2912
5c680ed6 2913 if (!path->nodes[1]) {
e089f05c 2914 ret = insert_new_root(trans, root, path, 1);
5c680ed6
CM		 2915 if (ret)
2916 return ret;
2917 }
cc0c5538
CM		 2918again:
2919 double_split = 0;
2920 l = path->nodes[0];
eb60ceac 2921 slot = path->slots[0];
5f39d397 2922 nritems = btrfs_header_nritems(l);
d397712b 2923 mid = (nritems + 1) / 2;
54aa1f4d 2924
925baedd 2925 right = btrfs_alloc_free_block(trans, root, root->leafsize,
31840ae1
ZY		 2926 path->nodes[1]->start,
2927 root->root_key.objectid,
2928 trans->transid, 0, l->start, 0);
cea9e445
CM		 2929 if (IS_ERR(right)) {
2930 BUG_ON(1);
5f39d397 2931 return PTR_ERR(right);
cea9e445 2932 }
5f39d397
CM		 2933
2934 memset_extent_buffer(right, 0, 0, sizeof(struct btrfs_header));
db94535d 2935 btrfs_set_header_bytenr(right, right->start);
5f39d397
CM		 2936 btrfs_set_header_generation(right, trans->transid);
2937 btrfs_set_header_owner(right, root->root_key.objectid);
2938 btrfs_set_header_level(right, 0);
2939 write_extent_buffer(right, root->fs_info->fsid,
2940 (unsigned long)btrfs_header_fsid(right),
2941 BTRFS_FSID_SIZE);
e17cade2
CM		 2942
2943 write_extent_buffer(right, root->fs_info->chunk_tree_uuid,
2944 (unsigned long)btrfs_header_chunk_tree_uuid(right),
2945 BTRFS_UUID_SIZE);
44871b1b 2946
d4dbff95
CM		 2947 if (mid <= slot) {
2948 if (nritems == 1 ||
87b29b20 2949 leaf_space_used(l, mid, nritems - mid) + data_size >
d4dbff95
CM		 2950 BTRFS_LEAF_DATA_SIZE(root)) {
2951 if (slot >= nritems) {
44871b1b
CM		 2952 struct btrfs_disk_key disk_key;
2953
d4dbff95 2954 btrfs_cpu_key_to_disk(&disk_key, ins_key);
5f39d397 2955 btrfs_set_header_nritems(right, 0);
d4dbff95 2956 wret = insert_ptr(trans, root, path,
db94535d 2957 &disk_key, right->start,
d4dbff95
CM		 2958 path->slots[1] + 1, 1);
2959 if (wret)
2960 ret = wret;
925baedd
CM		 2961
2962 btrfs_tree_unlock(path->nodes[0]);
5f39d397
CM		 2963 free_extent_buffer(path->nodes[0]);
2964 path->nodes[0] = right;
d4dbff95
CM		 2965 path->slots[0] = 0;
2966 path->slots[1] += 1;
0ef8b242 2967 btrfs_mark_buffer_dirty(right);
d4dbff95
CM		 2968 return ret;
2969 }
2970 mid = slot;
3326d1b0
CM		 2971 if (mid != nritems &&
2972 leaf_space_used(l, mid, nritems - mid) +
87b29b20 2973 data_size > BTRFS_LEAF_DATA_SIZE(root)) {
3326d1b0
CM		 2974 double_split = 1;
2975 }
d4dbff95
CM		 2976 }
2977 } else {
87b29b20 2978 if (leaf_space_used(l, 0, mid) + data_size >
d4dbff95 2979 BTRFS_LEAF_DATA_SIZE(root)) {
459931ec 2980 if (!extend && data_size && slot == 0) {
44871b1b
CM		 2981 struct btrfs_disk_key disk_key;
2982
d4dbff95 2983 btrfs_cpu_key_to_disk(&disk_key, ins_key);
5f39d397 2984 btrfs_set_header_nritems(right, 0);
d4dbff95
CM		 2985 wret = insert_ptr(trans, root, path,
2986 &disk_key,
db94535d 2987 right->start,
098f59c2 2988 path->slots[1], 1);
d4dbff95
CM		 2989 if (wret)
2990 ret = wret;
925baedd 2991 btrfs_tree_unlock(path->nodes[0]);
5f39d397
CM		 2992 free_extent_buffer(path->nodes[0]);
2993 path->nodes[0] = right;
d4dbff95 2994 path->slots[0] = 0;
a429e513
CM		 2995 if (path->slots[1] == 0) {
2996 wret = fixup_low_keys(trans, root,
d397712b 2997 path, &disk_key, 1);
a429e513
CM		 2998 if (wret)
2999 ret = wret;
3000 }
0ef8b242 3001 btrfs_mark_buffer_dirty(right);
d4dbff95 3002 return ret;
459931ec 3003 } else if ((extend || !data_size) && slot == 0) {
cc0c5538
CM		 3004 mid = 1;
3005 } else {
3006 mid = slot;
3007 if (mid != nritems &&
3008 leaf_space_used(l, mid, nritems - mid) +
87b29b20 3009 data_size > BTRFS_LEAF_DATA_SIZE(root)) {
cc0c5538
CM		 3010 double_split = 1;
3011 }
5ee78ac7 3012 }
d4dbff95
CM		 3013 }
3014 }
74123bd7 3015
44871b1b 3016 ret = copy_for_split(trans, root, path, l, right, slot, mid, nritems);
31840ae1
ZY		 3017 BUG_ON(ret);
3018
cc0c5538
CM		 3019 if (double_split) {
3020 BUG_ON(num_doubles != 0);
3021 num_doubles++;
3022 goto again;
a429e513 3023 }
44871b1b 3024
be0e5c09
CM		 3025 return ret;
3026}
3027
459931ec
CM		 3028/*
3029 * This function splits a single item into two items,
3030 * giving 'new_key' to the new item and splitting the
3031 * old one at split_offset (from the start of the item).
3032 *
3033 * The path may be released by this operation. After
3034 * the split, the path is pointing to the old item. The
3035 * new item is going to be in the same node as the old one.
3036 *
3037 * Note, the item being split must be smaller enough to live alone on
3038 * a tree block with room for one extra struct btrfs_item
3039 *
3040 * This allows us to split the item in place, keeping a lock on the
3041 * leaf the entire time.
3042 */
3043int btrfs_split_item(struct btrfs_trans_handle *trans,
3044 struct btrfs_root *root,
3045 struct btrfs_path *path,
3046 struct btrfs_key *new_key,
3047 unsigned long split_offset)
3048{
3049 u32 item_size;
3050 struct extent_buffer *leaf;
3051 struct btrfs_key orig_key;
3052 struct btrfs_item *item;
3053 struct btrfs_item *new_item;
3054 int ret = 0;
3055 int slot;
3056 u32 nritems;
3057 u32 orig_offset;
3058 struct btrfs_disk_key disk_key;
3059 char *buf;
3060
3061 leaf = path->nodes[0];
3062 btrfs_item_key_to_cpu(leaf, &orig_key, path->slots[0]);
3063 if (btrfs_leaf_free_space(root, leaf) >= sizeof(struct btrfs_item))
3064 goto split;
3065
3066 item_size = btrfs_item_size_nr(leaf, path->slots[0]);
3067 btrfs_release_path(root, path);
3068
3069 path->search_for_split = 1;
3070 path->keep_locks = 1;
3071
3072 ret = btrfs_search_slot(trans, root, &orig_key, path, 0, 1);
3073 path->search_for_split = 0;
3074
3075 /* if our item isn't there or got smaller, return now */
3076 if (ret != 0 || item_size != btrfs_item_size_nr(path->nodes[0],
3077 path->slots[0])) {
3078 path->keep_locks = 0;
3079 return -EAGAIN;
3080 }
3081
b9473439 3082 btrfs_set_path_blocking(path);
87b29b20
YZ		 3083 ret = split_leaf(trans, root, &orig_key, path,
3084 sizeof(struct btrfs_item), 1);
459931ec
CM		 3085 path->keep_locks = 0;
3086 BUG_ON(ret);
3087
b9473439
CM		 3088 btrfs_unlock_up_safe(path, 1);
3089 leaf = path->nodes[0];
3090 BUG_ON(btrfs_leaf_free_space(root, leaf) < sizeof(struct btrfs_item));
3091
3092split:
b4ce94de
CM		 3093 /*
3094 * make sure any changes to the path from split_leaf leave it
3095 * in a blocking state
3096 */
3097 btrfs_set_path_blocking(path);
3098
459931ec
CM		 3099 item = btrfs_item_nr(leaf, path->slots[0]);
3100 orig_offset = btrfs_item_offset(leaf, item);
3101 item_size = btrfs_item_size(leaf, item);
3102
459931ec
CM		 3103 buf = kmalloc(item_size, GFP_NOFS);
3104 read_extent_buffer(leaf, buf, btrfs_item_ptr_offset(leaf,
3105 path->slots[0]), item_size);
3106 slot = path->slots[0] + 1;
3107 leaf = path->nodes[0];
3108
3109 nritems = btrfs_header_nritems(leaf);
3110
3111 if (slot != nritems) {
3112 /* shift the items */
3113 memmove_extent_buffer(leaf, btrfs_item_nr_offset(slot + 1),
3114 btrfs_item_nr_offset(slot),
3115 (nritems - slot) * sizeof(struct btrfs_item));
3116
3117 }
3118
3119 btrfs_cpu_key_to_disk(&disk_key, new_key);
3120 btrfs_set_item_key(leaf, &disk_key, slot);
3121
3122 new_item = btrfs_item_nr(leaf, slot);
3123
3124 btrfs_set_item_offset(leaf, new_item, orig_offset);
3125 btrfs_set_item_size(leaf, new_item, item_size - split_offset);
3126
3127 btrfs_set_item_offset(leaf, item,
3128 orig_offset + item_size - split_offset);
3129 btrfs_set_item_size(leaf, item, split_offset);
3130
3131 btrfs_set_header_nritems(leaf, nritems + 1);
3132
3133 /* write the data for the start of the original item */
3134 write_extent_buffer(leaf, buf,
3135 btrfs_item_ptr_offset(leaf, path->slots[0]),
3136 split_offset);
3137
3138 /* write the data for the new item */
3139 write_extent_buffer(leaf, buf + split_offset,
3140 btrfs_item_ptr_offset(leaf, slot),
3141 item_size - split_offset);
3142 btrfs_mark_buffer_dirty(leaf);
3143
3144 ret = 0;
3145 if (btrfs_leaf_free_space(root, leaf) < 0) {
3146 btrfs_print_leaf(root, leaf);
3147 BUG();
3148 }
3149 kfree(buf);
3150 return ret;
3151}
3152
d352ac68
CM		 3153/*
3154 * make the item pointed to by the path smaller. new_size indicates
3155 * how small to make it, and from_end tells us if we just chop bytes
3156 * off the end of the item or if we shift the item to chop bytes off
3157 * the front.
3158 */
b18c6685
CM		 3159int btrfs_truncate_item(struct btrfs_trans_handle *trans,
3160 struct btrfs_root *root,
3161 struct btrfs_path *path,
179e29e4 3162 u32 new_size, int from_end)
b18c6685
CM		 3163{
3164 int ret = 0;
3165 int slot;
3166 int slot_orig;
5f39d397
CM		 3167 struct extent_buffer *leaf;
3168 struct btrfs_item *item;
b18c6685
CM		 3169 u32 nritems;
3170 unsigned int data_end;
3171 unsigned int old_data_start;
3172 unsigned int old_size;
3173 unsigned int size_diff;
3174 int i;
3175
3176 slot_orig = path->slots[0];
5f39d397 3177 leaf = path->nodes[0];
179e29e4
CM		 3178 slot = path->slots[0];
3179
3180 old_size = btrfs_item_size_nr(leaf, slot);
3181 if (old_size == new_size)
3182 return 0;
b18c6685 3183
5f39d397 3184 nritems = btrfs_header_nritems(leaf);
b18c6685
CM		 3185 data_end = leaf_data_end(root, leaf);
3186
5f39d397 3187 old_data_start = btrfs_item_offset_nr(leaf, slot);
179e29e4 3188
b18c6685
CM		 3189 size_diff = old_size - new_size;
3190
3191 BUG_ON(slot < 0);
3192 BUG_ON(slot >= nritems);
3193
3194 /*
3195 * item0..itemN ... dataN.offset..dataN.size .. data0.size
3196 */
3197 /* first correct the data pointers */
3198 for (i = slot; i < nritems; i++) {
5f39d397
CM		 3199 u32 ioff;
3200 item = btrfs_item_nr(leaf, i);
db94535d
CM		 3201
3202 if (!leaf->map_token) {
3203 map_extent_buffer(leaf, (unsigned long)item,
3204 sizeof(struct btrfs_item),
3205 &leaf->map_token, &leaf->kaddr,
3206 &leaf->map_start, &leaf->map_len,
3207 KM_USER1);
3208 }
3209
5f39d397
CM		 3210 ioff = btrfs_item_offset(leaf, item);
3211 btrfs_set_item_offset(leaf, item, ioff + size_diff);
b18c6685 3212 }
db94535d
CM		 3213
3214 if (leaf->map_token) {
3215 unmap_extent_buffer(leaf, leaf->map_token, KM_USER1);
3216 leaf->map_token = NULL;
3217 }
3218
b18c6685 3219 /* shift the data */
179e29e4
CM		 3220 if (from_end) {
3221 memmove_extent_buffer(leaf, btrfs_leaf_data(leaf) +
3222 data_end + size_diff, btrfs_leaf_data(leaf) +
3223 data_end, old_data_start + new_size - data_end);
3224 } else {
3225 struct btrfs_disk_key disk_key;
3226 u64 offset;
3227
3228 btrfs_item_key(leaf, &disk_key, slot);
3229
3230 if (btrfs_disk_key_type(&disk_key) == BTRFS_EXTENT_DATA_KEY) {
3231 unsigned long ptr;
3232 struct btrfs_file_extent_item *fi;
3233
3234 fi = btrfs_item_ptr(leaf, slot,
3235 struct btrfs_file_extent_item);
3236 fi = (struct btrfs_file_extent_item *)(
3237 (unsigned long)fi - size_diff);
3238
3239 if (btrfs_file_extent_type(leaf, fi) ==
3240 BTRFS_FILE_EXTENT_INLINE) {
3241 ptr = btrfs_item_ptr_offset(leaf, slot);
3242 memmove_extent_buffer(leaf, ptr,
d397712b
CM		 3243 (unsigned long)fi,
3244 offsetof(struct btrfs_file_extent_item,
179e29e4
CM		 3245 disk_bytenr));
3246 }
3247 }
3248
3249 memmove_extent_buffer(leaf, btrfs_leaf_data(leaf) +
3250 data_end + size_diff, btrfs_leaf_data(leaf) +
3251 data_end, old_data_start - data_end);
3252
3253 offset = btrfs_disk_key_offset(&disk_key);
3254 btrfs_set_disk_key_offset(&disk_key, offset + size_diff);
3255 btrfs_set_item_key(leaf, &disk_key, slot);
3256 if (slot == 0)
3257 fixup_low_keys(trans, root, path, &disk_key, 1);
3258 }
5f39d397
CM		 3259
3260 item = btrfs_item_nr(leaf, slot);
3261 btrfs_set_item_size(leaf, item, new_size);
3262 btrfs_mark_buffer_dirty(leaf);
b18c6685
CM		 3263
3264 ret = 0;
5f39d397
CM		 3265 if (btrfs_leaf_free_space(root, leaf) < 0) {
3266 btrfs_print_leaf(root, leaf);
b18c6685 3267 BUG();
5f39d397 3268 }
b18c6685
CM		 3269 return ret;
3270}
3271
d352ac68
CM		 3272/*
3273 * make the item pointed to by the path bigger, data_size is the new size.
3274 */
5f39d397
CM		 3275int btrfs_extend_item(struct btrfs_trans_handle *trans,
3276 struct btrfs_root *root, struct btrfs_path *path,
3277 u32 data_size)
6567e837
CM		 3278{
3279 int ret = 0;
3280 int slot;
3281 int slot_orig;
5f39d397
CM		 3282 struct extent_buffer *leaf;
3283 struct btrfs_item *item;
6567e837
CM		 3284 u32 nritems;
3285 unsigned int data_end;
3286 unsigned int old_data;
3287 unsigned int old_size;
3288 int i;
3289
3290 slot_orig = path->slots[0];
5f39d397 3291 leaf = path->nodes[0];
6567e837 3292
5f39d397 3293 nritems = btrfs_header_nritems(leaf);
6567e837
CM		 3294 data_end = leaf_data_end(root, leaf);
3295
5f39d397
CM		 3296 if (btrfs_leaf_free_space(root, leaf) < data_size) {
3297 btrfs_print_leaf(root, leaf);
6567e837 3298 BUG();
5f39d397 3299 }
6567e837 3300 slot = path->slots[0];
5f39d397 3301 old_data = btrfs_item_end_nr(leaf, slot);
6567e837
CM		 3302
3303 BUG_ON(slot < 0);
3326d1b0
CM		 3304 if (slot >= nritems) {
3305 btrfs_print_leaf(root, leaf);
d397712b
CM		 3306 printk(KERN_CRIT "slot %d too large, nritems %d\n",
3307 slot, nritems);
3326d1b0
CM		 3308 BUG_ON(1);
3309 }
6567e837
CM		 3310
3311 /*
3312 * item0..itemN ... dataN.offset..dataN.size .. data0.size
3313 */
3314 /* first correct the data pointers */
3315 for (i = slot; i < nritems; i++) {
5f39d397
CM		 3316 u32 ioff;
3317 item = btrfs_item_nr(leaf, i);
db94535d
CM		 3318
3319 if (!leaf->map_token) {
3320 map_extent_buffer(leaf, (unsigned long)item,
3321 sizeof(struct btrfs_item),
3322 &leaf->map_token, &leaf->kaddr,
3323 &leaf->map_start, &leaf->map_len,
3324 KM_USER1);
3325 }
5f39d397
CM		 3326 ioff = btrfs_item_offset(leaf, item);
3327 btrfs_set_item_offset(leaf, item, ioff - data_size);
6567e837 3328 }
5f39d397 3329
db94535d
CM		 3330 if (leaf->map_token) {
3331 unmap_extent_buffer(leaf, leaf->map_token, KM_USER1);
3332 leaf->map_token = NULL;
3333 }
3334
6567e837 3335 /* shift the data */
5f39d397 3336 memmove_extent_buffer(leaf, btrfs_leaf_data(leaf) +
6567e837
CM		 3337 data_end - data_size, btrfs_leaf_data(leaf) +
3338 data_end, old_data - data_end);
5f39d397 3339
6567e837 3340 data_end = old_data;
5f39d397
CM		 3341 old_size = btrfs_item_size_nr(leaf, slot);
3342 item = btrfs_item_nr(leaf, slot);
3343 btrfs_set_item_size(leaf, item, old_size + data_size);
3344 btrfs_mark_buffer_dirty(leaf);
6567e837
CM		 3345
3346 ret = 0;
5f39d397
CM		 3347 if (btrfs_leaf_free_space(root, leaf) < 0) {
3348 btrfs_print_leaf(root, leaf);
6567e837 3349 BUG();
5f39d397 3350 }
6567e837
CM		 3351 return ret;
3352}
3353
f3465ca4
JB		 3354/*
3355 * Given a key and some data, insert items into the tree.
3356 * This does all the path init required, making room in the tree if needed.
3357 * Returns the number of keys that were inserted.
3358 */
3359int btrfs_insert_some_items(struct btrfs_trans_handle *trans,
3360 struct btrfs_root *root,
3361 struct btrfs_path *path,
3362 struct btrfs_key *cpu_key, u32 *data_size,
3363 int nr)
3364{
3365 struct extent_buffer *leaf;
3366 struct btrfs_item *item;
3367 int ret = 0;
3368 int slot;
f3465ca4
JB		 3369 int i;
3370 u32 nritems;
3371 u32 total_data = 0;
3372 u32 total_size = 0;
3373 unsigned int data_end;
3374 struct btrfs_disk_key disk_key;
3375 struct btrfs_key found_key;
3376
87b29b20
YZ		 3377 for (i = 0; i < nr; i++) {
3378 if (total_size + data_size[i] + sizeof(struct btrfs_item) >
3379 BTRFS_LEAF_DATA_SIZE(root)) {
3380 break;
3381 nr = i;
3382 }
f3465ca4 3383 total_data += data_size[i];
87b29b20
YZ		 3384 total_size += data_size[i] + sizeof(struct btrfs_item);
3385 }
3386 BUG_ON(nr == 0);
f3465ca4 3387
f3465ca4
JB		 3388 ret = btrfs_search_slot(trans, root, cpu_key, path, total_size, 1);
3389 if (ret == 0)
3390 return -EEXIST;
3391 if (ret < 0)
3392 goto out;
3393
f3465ca4
JB		 3394 leaf = path->nodes[0];
3395
3396 nritems = btrfs_header_nritems(leaf);
3397 data_end = leaf_data_end(root, leaf);
3398
3399 if (btrfs_leaf_free_space(root, leaf) < total_size) {
3400 for (i = nr; i >= 0; i--) {
3401 total_data -= data_size[i];
3402 total_size -= data_size[i] + sizeof(struct btrfs_item);
3403 if (total_size < btrfs_leaf_free_space(root, leaf))
3404 break;
3405 }
3406 nr = i;
3407 }
3408
3409 slot = path->slots[0];
3410 BUG_ON(slot < 0);
3411
3412 if (slot != nritems) {
3413 unsigned int old_data = btrfs_item_end_nr(leaf, slot);
3414
3415 item = btrfs_item_nr(leaf, slot);
3416 btrfs_item_key_to_cpu(leaf, &found_key, slot);
3417
3418 /* figure out how many keys we can insert in here */
3419 total_data = data_size[0];
3420 for (i = 1; i < nr; i++) {
3421 if (comp_cpu_keys(&found_key, cpu_key + i) <= 0)
3422 break;
3423 total_data += data_size[i];
3424 }
3425 nr = i;
3426
3427 if (old_data < data_end) {
3428 btrfs_print_leaf(root, leaf);
d397712b 3429 printk(KERN_CRIT "slot %d old_data %d data_end %d\n",
f3465ca4
JB		 3430 slot, old_data, data_end);
3431 BUG_ON(1);
3432 }
3433 /*
3434 * item0..itemN ... dataN.offset..dataN.size .. data0.size
3435 */
3436 /* first correct the data pointers */
3437 WARN_ON(leaf->map_token);
3438 for (i = slot; i < nritems; i++) {
3439 u32 ioff;
3440
3441 item = btrfs_item_nr(leaf, i);
3442 if (!leaf->map_token) {
3443 map_extent_buffer(leaf, (unsigned long)item,
3444 sizeof(struct btrfs_item),
3445 &leaf->map_token, &leaf->kaddr,
3446 &leaf->map_start, &leaf->map_len,
3447 KM_USER1);
3448 }
3449
3450 ioff = btrfs_item_offset(leaf, item);
3451 btrfs_set_item_offset(leaf, item, ioff - total_data);
3452 }
3453 if (leaf->map_token) {
3454 unmap_extent_buffer(leaf, leaf->map_token, KM_USER1);
3455 leaf->map_token = NULL;
3456 }
3457
3458 /* shift the items */
3459 memmove_extent_buffer(leaf, btrfs_item_nr_offset(slot + nr),
3460 btrfs_item_nr_offset(slot),
3461 (nritems - slot) * sizeof(struct btrfs_item));
3462
3463 /* shift the data */
3464 memmove_extent_buffer(leaf, btrfs_leaf_data(leaf) +
3465 data_end - total_data, btrfs_leaf_data(leaf) +
3466 data_end, old_data - data_end);
3467 data_end = old_data;
3468 } else {
3469 /*
3470 * this sucks but it has to be done, if we are inserting at
3471 * the end of the leaf only insert 1 of the items, since we
3472 * have no way of knowing whats on the next leaf and we'd have
3473 * to drop our current locks to figure it out
3474 */
3475 nr = 1;
3476 }
3477
3478 /* setup the item for the new data */
3479 for (i = 0; i < nr; i++) {
3480 btrfs_cpu_key_to_disk(&disk_key, cpu_key + i);
3481 btrfs_set_item_key(leaf, &disk_key, slot + i);
3482 item = btrfs_item_nr(leaf, slot + i);
3483 btrfs_set_item_offset(leaf, item, data_end - data_size[i]);
3484 data_end -= data_size[i];
3485 btrfs_set_item_size(leaf, item, data_size[i]);
3486 }
3487 btrfs_set_header_nritems(leaf, nritems + nr);
3488 btrfs_mark_buffer_dirty(leaf);
3489
3490 ret = 0;
3491 if (slot == 0) {
3492 btrfs_cpu_key_to_disk(&disk_key, cpu_key);
3493 ret = fixup_low_keys(trans, root, path, &disk_key, 1);
3494 }
3495
3496 if (btrfs_leaf_free_space(root, leaf) < 0) {
3497 btrfs_print_leaf(root, leaf);
3498 BUG();
3499 }
3500out:
3501 if (!ret)
3502 ret = nr;
3503 return ret;
3504}
3505
74123bd7 3506/*
44871b1b
CM		 3507 * this is a helper for btrfs_insert_empty_items, the main goal here is
3508 * to save stack depth by doing the bulk of the work in a function
3509 * that doesn't call btrfs_search_slot
74123bd7 3510 */
44871b1b
CM		 3511static noinline_for_stack int
3512setup_items_for_insert(struct btrfs_trans_handle *trans,
3513 struct btrfs_root *root, struct btrfs_path *path,
3514 struct btrfs_key *cpu_key, u32 *data_size,
3515 u32 total_data, u32 total_size, int nr)
be0e5c09 3516{
5f39d397 3517 struct btrfs_item *item;
9c58309d 3518 int i;
7518a238 3519 u32 nritems;
be0e5c09 3520 unsigned int data_end;
e2fa7227 3521 struct btrfs_disk_key disk_key;
44871b1b
CM		 3522 int ret;
3523 struct extent_buffer *leaf;
3524 int slot;
e2fa7227 3525
5f39d397 3526 leaf = path->nodes[0];
44871b1b 3527 slot = path->slots[0];
74123bd7 3528
5f39d397 3529 nritems = btrfs_header_nritems(leaf);
123abc88 3530 data_end = leaf_data_end(root, leaf);
eb60ceac 3531
f25956cc 3532 if (btrfs_leaf_free_space(root, leaf) < total_size) {
3326d1b0 3533 btrfs_print_leaf(root, leaf);
d397712b 3534 printk(KERN_CRIT "not enough freespace need %u have %d\n",
9c58309d 3535 total_size, btrfs_leaf_free_space(root, leaf));
be0e5c09 3536 BUG();
d4dbff95 3537 }
5f39d397 3538
be0e5c09 3539 if (slot != nritems) {
5f39d397 3540 unsigned int old_data = btrfs_item_end_nr(leaf, slot);
be0e5c09 3541
5f39d397
CM		 3542 if (old_data < data_end) {
3543 btrfs_print_leaf(root, leaf);
d397712b 3544 printk(KERN_CRIT "slot %d old_data %d data_end %d\n",
5f39d397
CM		 3545 slot, old_data, data_end);
3546 BUG_ON(1);
3547 }
be0e5c09
CM		 3548 /*
3549 * item0..itemN ... dataN.offset..dataN.size .. data0.size
3550 */
3551 /* first correct the data pointers */
db94535d 3552 WARN_ON(leaf->map_token);
0783fcfc 3553 for (i = slot; i < nritems; i++) {
5f39d397 3554 u32 ioff;
db94535d 3555
5f39d397 3556 item = btrfs_item_nr(leaf, i);
db94535d
CM		 3557 if (!leaf->map_token) {
3558 map_extent_buffer(leaf, (unsigned long)item,
3559 sizeof(struct btrfs_item),
3560 &leaf->map_token, &leaf->kaddr,
3561 &leaf->map_start, &leaf->map_len,
3562 KM_USER1);
3563 }
3564
5f39d397 3565 ioff = btrfs_item_offset(leaf, item);
9c58309d 3566 btrfs_set_item_offset(leaf, item, ioff - total_data);
0783fcfc 3567 }
db94535d
CM		 3568 if (leaf->map_token) {
3569 unmap_extent_buffer(leaf, leaf->map_token, KM_USER1);
3570 leaf->map_token = NULL;
3571 }
be0e5c09
CM		 3572
3573 /* shift the items */
9c58309d 3574 memmove_extent_buffer(leaf, btrfs_item_nr_offset(slot + nr),
5f39d397 3575 btrfs_item_nr_offset(slot),
d6025579 3576 (nritems - slot) * sizeof(struct btrfs_item));
be0e5c09
CM		 3577
3578 /* shift the data */
5f39d397 3579 memmove_extent_buffer(leaf, btrfs_leaf_data(leaf) +
9c58309d 3580 data_end - total_data, btrfs_leaf_data(leaf) +
d6025579 3581 data_end, old_data - data_end);
be0e5c09
CM		 3582 data_end = old_data;
3583 }
5f39d397 3584
62e2749e 3585 /* setup the item for the new data */
9c58309d
CM		 3586 for (i = 0; i < nr; i++) {
3587 btrfs_cpu_key_to_disk(&disk_key, cpu_key + i);
3588 btrfs_set_item_key(leaf, &disk_key, slot + i);
3589 item = btrfs_item_nr(leaf, slot + i);
3590 btrfs_set_item_offset(leaf, item, data_end - data_size[i]);
3591 data_end -= data_size[i];
3592 btrfs_set_item_size(leaf, item, data_size[i]);
3593 }
44871b1b 3594
9c58309d 3595 btrfs_set_header_nritems(leaf, nritems + nr);
aa5d6bed
CM		 3596
3597 ret = 0;
5a01a2e3 3598 if (slot == 0) {
44871b1b 3599 struct btrfs_disk_key disk_key;
5a01a2e3 3600 btrfs_cpu_key_to_disk(&disk_key, cpu_key);
e089f05c 3601 ret = fixup_low_keys(trans, root, path, &disk_key, 1);
5a01a2e3 3602 }
b9473439
CM		 3603 btrfs_unlock_up_safe(path, 1);
3604 btrfs_mark_buffer_dirty(leaf);
aa5d6bed 3605
5f39d397
CM		 3606 if (btrfs_leaf_free_space(root, leaf) < 0) {
3607 btrfs_print_leaf(root, leaf);
be0e5c09 3608 BUG();
5f39d397 3609 }
44871b1b
CM		 3610 return ret;
3611}
3612
3613/*
3614 * Given a key and some data, insert items into the tree.
3615 * This does all the path init required, making room in the tree if needed.
3616 */
3617int btrfs_insert_empty_items(struct btrfs_trans_handle *trans,
3618 struct btrfs_root *root,
3619 struct btrfs_path *path,
3620 struct btrfs_key *cpu_key, u32 *data_size,
3621 int nr)
3622{
3623 struct extent_buffer *leaf;
3624 int ret = 0;
3625 int slot;
3626 int i;
3627 u32 total_size = 0;
3628 u32 total_data = 0;
3629
3630 for (i = 0; i < nr; i++)
3631 total_data += data_size[i];
3632
3633 total_size = total_data + (nr * sizeof(struct btrfs_item));
3634 ret = btrfs_search_slot(trans, root, cpu_key, path, total_size, 1);
3635 if (ret == 0)
3636 return -EEXIST;
3637 if (ret < 0)
3638 goto out;
3639
3640 leaf = path->nodes[0];
3641 slot = path->slots[0];
3642 BUG_ON(slot < 0);
3643
3644 ret = setup_items_for_insert(trans, root, path, cpu_key, data_size,
3645 total_data, total_size, nr);
3646
ed2ff2cb 3647out:
62e2749e
CM		 3648 return ret;
3649}
3650
3651/*
3652 * Given a key and some data, insert an item into the tree.
3653 * This does all the path init required, making room in the tree if needed.
3654 */
e089f05c
CM		 3655int btrfs_insert_item(struct btrfs_trans_handle *trans, struct btrfs_root
3656 *root, struct btrfs_key *cpu_key, void *data, u32
3657 data_size)
62e2749e
CM		 3658{
3659 int ret = 0;
2c90e5d6 3660 struct btrfs_path *path;
5f39d397
CM		 3661 struct extent_buffer *leaf;
3662 unsigned long ptr;
62e2749e 3663
2c90e5d6
CM		 3664 path = btrfs_alloc_path();
3665 BUG_ON(!path);
2c90e5d6 3666 ret = btrfs_insert_empty_item(trans, root, path, cpu_key, data_size);
62e2749e 3667 if (!ret) {
5f39d397
CM		 3668 leaf = path->nodes[0];
3669 ptr = btrfs_item_ptr_offset(leaf, path->slots[0]);
3670 write_extent_buffer(leaf, data, ptr, data_size);
3671 btrfs_mark_buffer_dirty(leaf);
62e2749e 3672 }
2c90e5d6 3673 btrfs_free_path(path);
aa5d6bed 3674 return ret;
be0e5c09
CM		 3675}
3676
74123bd7 3677/*
5de08d7d 3678 * delete the pointer from a given node.
74123bd7 3679 *
d352ac68
CM		 3680 * the tree should have been previously balanced so the deletion does not
3681 * empty a node.
74123bd7 3682 */
e089f05c
CM		 3683static int del_ptr(struct btrfs_trans_handle *trans, struct btrfs_root *root,
3684 struct btrfs_path *path, int level, int slot)
be0e5c09 3685{
5f39d397 3686 struct extent_buffer *parent = path->nodes[level];
7518a238 3687 u32 nritems;
aa5d6bed 3688 int ret = 0;
bb803951 3689 int wret;
be0e5c09 3690
5f39d397 3691 nritems = btrfs_header_nritems(parent);
d397712b 3692 if (slot != nritems - 1) {
5f39d397
CM		 3693 memmove_extent_buffer(parent,
3694 btrfs_node_key_ptr_offset(slot),
3695 btrfs_node_key_ptr_offset(slot + 1),
d6025579
CM		 3696 sizeof(struct btrfs_key_ptr) *
3697 (nritems - slot - 1));
bb803951 3698 }
7518a238 3699 nritems--;
5f39d397 3700 btrfs_set_header_nritems(parent, nritems);
7518a238 3701 if (nritems == 0 && parent == root->node) {
5f39d397 3702 BUG_ON(btrfs_header_level(root->node) != 1);
bb803951 3703 /* just turn the root into a leaf and break */
5f39d397 3704 btrfs_set_header_level(root->node, 0);
bb803951 3705 } else if (slot == 0) {
5f39d397
CM		 3706 struct btrfs_disk_key disk_key;
3707
3708 btrfs_node_key(parent, &disk_key, 0);
3709 wret = fixup_low_keys(trans, root, path, &disk_key, level + 1);
0f70abe2
CM		 3710 if (wret)
3711 ret = wret;
be0e5c09 3712 }
d6025579 3713 btrfs_mark_buffer_dirty(parent);
aa5d6bed 3714 return ret;
be0e5c09
CM		 3715}
3716
323ac95b
CM		 3717/*
3718 * a helper function to delete the leaf pointed to by path->slots[1] and
3719 * path->nodes[1]. bytenr is the node block pointer, but since the callers
3720 * already know it, it is faster to have them pass it down than to
3721 * read it out of the node again.
3722 *
3723 * This deletes the pointer in path->nodes[1] and frees the leaf
3724 * block extent. zero is returned if it all worked out, < 0 otherwise.
3725 *
3726 * The path must have already been setup for deleting the leaf, including
3727 * all the proper balancing. path->nodes[1] must be locked.
3728 */
3729noinline int btrfs_del_leaf(struct btrfs_trans_handle *trans,
3730 struct btrfs_root *root,
3731 struct btrfs_path *path, u64 bytenr)
3732{
3733 int ret;
3734 u64 root_gen = btrfs_header_generation(path->nodes[1]);
4d081c41
CM		 3735 u64 parent_start = path->nodes[1]->start;
3736 u64 parent_owner = btrfs_header_owner(path->nodes[1]);
323ac95b
CM		 3737
3738 ret = del_ptr(trans, root, path, 1, path->slots[1]);
3739 if (ret)
3740 return ret;
3741
4d081c41
CM		 3742 /*
3743 * btrfs_free_extent is expensive, we want to make sure we
3744 * aren't holding any locks when we call it
3745 */
3746 btrfs_unlock_up_safe(path, 0);
3747
323ac95b
CM		 3748 ret = btrfs_free_extent(trans, root, bytenr,
3749 btrfs_level_size(root, 0),
4d081c41 3750 parent_start, parent_owner,
3bb1a1bc 3751 root_gen, 0, 1);
323ac95b
CM		 3752 return ret;
3753}
74123bd7
CM		 3754/*
3755 * delete the item at the leaf level in path. If that empties
3756 * the leaf, remove it from the tree
3757 */
85e21bac
CM		 3758int btrfs_del_items(struct btrfs_trans_handle *trans, struct btrfs_root *root,
3759 struct btrfs_path *path, int slot, int nr)
be0e5c09 3760{
5f39d397
CM		 3761 struct extent_buffer *leaf;
3762 struct btrfs_item *item;
85e21bac
CM		 3763 int last_off;
3764 int dsize = 0;
aa5d6bed
CM		 3765 int ret = 0;
3766 int wret;
85e21bac 3767 int i;
7518a238 3768 u32 nritems;
be0e5c09 3769
5f39d397 3770 leaf = path->nodes[0];
85e21bac
CM		 3771 last_off = btrfs_item_offset_nr(leaf, slot + nr - 1);
3772
3773 for (i = 0; i < nr; i++)
3774 dsize += btrfs_item_size_nr(leaf, slot + i);
3775
5f39d397 3776 nritems = btrfs_header_nritems(leaf);
be0e5c09 3777
85e21bac 3778 if (slot + nr != nritems) {
123abc88 3779 int data_end = leaf_data_end(root, leaf);
5f39d397
CM		 3780
3781 memmove_extent_buffer(leaf, btrfs_leaf_data(leaf) +
d6025579
CM		 3782 data_end + dsize,
3783 btrfs_leaf_data(leaf) + data_end,
85e21bac 3784 last_off - data_end);
5f39d397 3785
85e21bac 3786 for (i = slot + nr; i < nritems; i++) {
5f39d397 3787 u32 ioff;
db94535d 3788
5f39d397 3789 item = btrfs_item_nr(leaf, i);
db94535d
CM		 3790 if (!leaf->map_token) {
3791 map_extent_buffer(leaf, (unsigned long)item,
3792 sizeof(struct btrfs_item),
3793 &leaf->map_token, &leaf->kaddr,
3794 &leaf->map_start, &leaf->map_len,
3795 KM_USER1);
3796 }
5f39d397
CM		 3797 ioff = btrfs_item_offset(leaf, item);
3798 btrfs_set_item_offset(leaf, item, ioff + dsize);
0783fcfc 3799 }
db94535d
CM		 3800
3801 if (leaf->map_token) {
3802 unmap_extent_buffer(leaf, leaf->map_token, KM_USER1);
3803 leaf->map_token = NULL;
3804 }
3805
5f39d397 3806 memmove_extent_buffer(leaf, btrfs_item_nr_offset(slot),
85e21bac 3807 btrfs_item_nr_offset(slot + nr),
d6025579 3808 sizeof(struct btrfs_item) *
85e21bac 3809 (nritems - slot - nr));
be0e5c09 3810 }
85e21bac
CM		 3811 btrfs_set_header_nritems(leaf, nritems - nr);
3812 nritems -= nr;
5f39d397 3813
74123bd7 3814 /* delete the leaf if we've emptied it */
7518a238 3815 if (nritems == 0) {
5f39d397
CM		 3816 if (leaf == root->node) {
3817 btrfs_set_header_level(leaf, 0);
9a8dd150 3818 } else {
323ac95b
CM		 3819 ret = btrfs_del_leaf(trans, root, path, leaf->start);
3820 BUG_ON(ret);
9a8dd150 3821 }
be0e5c09 3822 } else {
7518a238 3823 int used = leaf_space_used(leaf, 0, nritems);
aa5d6bed 3824 if (slot == 0) {
5f39d397
CM		 3825 struct btrfs_disk_key disk_key;
3826
3827 btrfs_item_key(leaf, &disk_key, 0);
e089f05c 3828 wret = fixup_low_keys(trans, root, path,
5f39d397 3829 &disk_key, 1);
aa5d6bed
CM		 3830 if (wret)
3831 ret = wret;
3832 }
aa5d6bed 3833
74123bd7 3834 /* delete the leaf if it is mostly empty */
a4b6e07d
CM		 3835 if (used < BTRFS_LEAF_DATA_SIZE(root) / 4 &&
3836 !trans->transaction->delayed_refs.flushing) {
be0e5c09
CM		 3837 /* push_leaf_left fixes the path.
3838 * make sure the path still points to our leaf
3839 * for possible call to del_ptr below
3840 */
4920c9ac 3841 slot = path->slots[1];
5f39d397
CM		 3842 extent_buffer_get(leaf);
3843
b9473439 3844 btrfs_set_path_blocking(path);
85e21bac 3845 wret = push_leaf_left(trans, root, path, 1, 1);
54aa1f4d 3846 if (wret < 0 && wret != -ENOSPC)
aa5d6bed 3847 ret = wret;
5f39d397
CM		 3848
3849 if (path->nodes[0] == leaf &&
3850 btrfs_header_nritems(leaf)) {
85e21bac 3851 wret = push_leaf_right(trans, root, path, 1, 1);
54aa1f4d 3852 if (wret < 0 && wret != -ENOSPC)
aa5d6bed
CM		 3853 ret = wret;
3854 }
5f39d397
CM		 3855
3856 if (btrfs_header_nritems(leaf) == 0) {
323ac95b 3857 path->slots[1] = slot;
d397712b
CM		 3858 ret = btrfs_del_leaf(trans, root, path,
3859 leaf->start);
323ac95b 3860 BUG_ON(ret);
5f39d397 3861 free_extent_buffer(leaf);
5de08d7d 3862 } else {
925baedd
CM		 3863 /* if we're still in the path, make sure
3864 * we're dirty. Otherwise, one of the
3865 * push_leaf functions must have already
3866 * dirtied this buffer
3867 */
3868 if (path->nodes[0] == leaf)
3869 btrfs_mark_buffer_dirty(leaf);
5f39d397 3870 free_extent_buffer(leaf);
be0e5c09 3871 }
d5719762 3872 } else {
5f39d397 3873 btrfs_mark_buffer_dirty(leaf);
be0e5c09
CM		 3874 }
3875 }
aa5d6bed 3876 return ret;
be0e5c09
CM		 3877}
3878
7bb86316 3879/*
925baedd 3880 * search the tree again to find a leaf with lesser keys
7bb86316
CM		 3881 * returns 0 if it found something or 1 if there are no lesser leaves.
3882 * returns < 0 on io errors.
d352ac68
CM		 3883 *
3884 * This may release the path, and so you may lose any locks held at the
3885 * time you call it.
7bb86316
CM		 3886 */
3887int btrfs_prev_leaf(struct btrfs_root *root, struct btrfs_path *path)
3888{
925baedd
CM		 3889 struct btrfs_key key;
3890 struct btrfs_disk_key found_key;
3891 int ret;
7bb86316 3892
925baedd 3893 btrfs_item_key_to_cpu(path->nodes[0], &key, 0);
7bb86316 3894
925baedd
CM		 3895 if (key.offset > 0)
3896 key.offset--;
3897 else if (key.type > 0)
3898 key.type--;
3899 else if (key.objectid > 0)
3900 key.objectid--;
3901 else
3902 return 1;
7bb86316 3903
925baedd
CM		 3904 btrfs_release_path(root, path);
3905 ret = btrfs_search_slot(NULL, root, &key, path, 0, 0);
3906 if (ret < 0)
3907 return ret;
3908 btrfs_item_key(path->nodes[0], &found_key, 0);
3909 ret = comp_keys(&found_key, &key);
3910 if (ret < 0)
3911 return 0;
3912 return 1;
7bb86316
CM		 3913}
3914
3f157a2f
CM		 3915/*
3916 * A helper function to walk down the tree starting at min_key, and looking
3917 * for nodes or leaves that are either in cache or have a minimum
d352ac68 3918 * transaction id. This is used by the btree defrag code, and tree logging
3f157a2f
CM		 3919 *
3920 * This does not cow, but it does stuff the starting key it finds back
3921 * into min_key, so you can call btrfs_search_slot with cow=1 on the
3922 * key and get a writable path.
3923 *
3924 * This does lock as it descends, and path->keep_locks should be set
3925 * to 1 by the caller.
3926 *
3927 * This honors path->lowest_level to prevent descent past a given level
3928 * of the tree.
3929 *
d352ac68
CM		 3930 * min_trans indicates the oldest transaction that you are interested
3931 * in walking through. Any nodes or leaves older than min_trans are
3932 * skipped over (without reading them).
3933 *
3f157a2f
CM		 3934 * returns zero if something useful was found, < 0 on error and 1 if there
3935 * was nothing in the tree that matched the search criteria.
3936 */
3937int btrfs_search_forward(struct btrfs_root *root, struct btrfs_key *min_key,
e02119d5 3938 struct btrfs_key *max_key,
3f157a2f
CM		 3939 struct btrfs_path *path, int cache_only,
3940 u64 min_trans)
3941{
3942 struct extent_buffer *cur;
3943 struct btrfs_key found_key;
3944 int slot;
9652480b 3945 int sret;
3f157a2f
CM		 3946 u32 nritems;
3947 int level;
3948 int ret = 1;
3949
934d375b 3950 WARN_ON(!path->keep_locks);
3f157a2f
CM		 3951again:
3952 cur = btrfs_lock_root_node(root);
3953 level = btrfs_header_level(cur);
e02119d5 3954 WARN_ON(path->nodes[level]);
3f157a2f
CM		 3955 path->nodes[level] = cur;
3956 path->locks[level] = 1;
3957
3958 if (btrfs_header_generation(cur) < min_trans) {
3959 ret = 1;
3960 goto out;
3961 }
d397712b 3962 while (1) {
3f157a2f
CM		 3963 nritems = btrfs_header_nritems(cur);
3964 level = btrfs_header_level(cur);
9652480b 3965 sret = bin_search(cur, min_key, level, &slot);
3f157a2f 3966
323ac95b
CM		 3967 /* at the lowest level, we're done, setup the path and exit */
3968 if (level == path->lowest_level) {
e02119d5
CM		 3969 if (slot >= nritems)
3970 goto find_next_key;
3f157a2f
CM		 3971 ret = 0;
3972 path->slots[level] = slot;
3973 btrfs_item_key_to_cpu(cur, &found_key, slot);
3974 goto out;
3975 }
9652480b
Y		 3976 if (sret && slot > 0)
3977 slot--;
3f157a2f
CM		 3978 /*
3979 * check this node pointer against the cache_only and
3980 * min_trans parameters. If it isn't in cache or is too
3981 * old, skip to the next one.
3982 */
d397712b 3983 while (slot < nritems) {
3f157a2f
CM		 3984 u64 blockptr;
3985 u64 gen;
3986 struct extent_buffer *tmp;
e02119d5
CM		 3987 struct btrfs_disk_key disk_key;
3988
3f157a2f
CM		 3989 blockptr = btrfs_node_blockptr(cur, slot);
3990 gen = btrfs_node_ptr_generation(cur, slot);
3991 if (gen < min_trans) {
3992 slot++;
3993 continue;
3994 }
3995 if (!cache_only)
3996 break;
3997
e02119d5
CM		 3998 if (max_key) {
3999 btrfs_node_key(cur, &disk_key, slot);
4000 if (comp_keys(&disk_key, max_key) >= 0) {
4001 ret = 1;
4002 goto out;
4003 }
4004 }
4005
3f157a2f
CM		 4006 tmp = btrfs_find_tree_block(root, blockptr,
4007 btrfs_level_size(root, level - 1));
4008
4009 if (tmp && btrfs_buffer_uptodate(tmp, gen)) {
4010 free_extent_buffer(tmp);
4011 break;
4012 }
4013 if (tmp)
4014 free_extent_buffer(tmp);
4015 slot++;
4016 }
e02119d5 4017find_next_key:
3f157a2f
CM		 4018 /*
4019 * we didn't find a candidate key in this node, walk forward
4020 * and find another one
4021 */
4022 if (slot >= nritems) {
e02119d5 4023 path->slots[level] = slot;
b4ce94de 4024 btrfs_set_path_blocking(path);
e02119d5 4025 sret = btrfs_find_next_key(root, path, min_key, level,
3f157a2f 4026 cache_only, min_trans);
e02119d5 4027 if (sret == 0) {
3f157a2f
CM		 4028 btrfs_release_path(root, path);
4029 goto again;
4030 } else {
4031 goto out;
4032 }
4033 }
4034 /* save our key for returning back */
4035 btrfs_node_key_to_cpu(cur, &found_key, slot);
4036 path->slots[level] = slot;
4037 if (level == path->lowest_level) {
4038 ret = 0;
4039 unlock_up(path, level, 1);
4040 goto out;
4041 }
b4ce94de 4042 btrfs_set_path_blocking(path);
3f157a2f
CM		 4043 cur = read_node_slot(root, cur, slot);
4044
4045 btrfs_tree_lock(cur);
b4ce94de 4046
3f157a2f
CM		 4047 path->locks[level - 1] = 1;
4048 path->nodes[level - 1] = cur;
4049 unlock_up(path, level, 1);
4008c04a 4050 btrfs_clear_path_blocking(path, NULL);
3f157a2f
CM		 4051 }
4052out:
4053 if (ret == 0)
4054 memcpy(min_key, &found_key, sizeof(found_key));
b4ce94de 4055 btrfs_set_path_blocking(path);
3f157a2f
CM		 4056 return ret;
4057}
4058
4059/*
4060 * this is similar to btrfs_next_leaf, but does not try to preserve
4061 * and fixup the path. It looks for and returns the next key in the
4062 * tree based on the current path and the cache_only and min_trans
4063 * parameters.
4064 *
4065 * 0 is returned if another key is found, < 0 if there are any errors
4066 * and 1 is returned if there are no higher keys in the tree
4067 *
4068 * path->keep_locks should be set to 1 on the search made before
4069 * calling this function.
4070 */
e7a84565 4071int btrfs_find_next_key(struct btrfs_root *root, struct btrfs_path *path,
3f157a2f
CM		 4072 struct btrfs_key *key, int lowest_level,
4073 int cache_only, u64 min_trans)
e7a84565
CM		 4074{
4075 int level = lowest_level;
4076 int slot;
4077 struct extent_buffer *c;
4078
934d375b 4079 WARN_ON(!path->keep_locks);
d397712b 4080 while (level < BTRFS_MAX_LEVEL) {
e7a84565
CM		 4081 if (!path->nodes[level])
4082 return 1;
4083
4084 slot = path->slots[level] + 1;
4085 c = path->nodes[level];
3f157a2f 4086next:
e7a84565
CM		 4087 if (slot >= btrfs_header_nritems(c)) {
4088 level++;
d397712b 4089 if (level == BTRFS_MAX_LEVEL)
e7a84565 4090 return 1;
e7a84565
CM		 4091 continue;
4092 }
4093 if (level == 0)
4094 btrfs_item_key_to_cpu(c, key, slot);
3f157a2f
CM		 4095 else {
4096 u64 blockptr = btrfs_node_blockptr(c, slot);
4097 u64 gen = btrfs_node_ptr_generation(c, slot);
4098
4099 if (cache_only) {
4100 struct extent_buffer *cur;
4101 cur = btrfs_find_tree_block(root, blockptr,
4102 btrfs_level_size(root, level - 1));
4103 if (!cur || !btrfs_buffer_uptodate(cur, gen)) {
4104 slot++;
4105 if (cur)
4106 free_extent_buffer(cur);
4107 goto next;
4108 }
4109 free_extent_buffer(cur);
4110 }
4111 if (gen < min_trans) {
4112 slot++;
4113 goto next;
4114 }
e7a84565 4115 btrfs_node_key_to_cpu(c, key, slot);
3f157a2f 4116 }
e7a84565
CM		 4117 return 0;
4118 }
4119 return 1;
4120}
4121
97571fd0 4122/*
925baedd 4123 * search the tree again to find a leaf with greater keys
0f70abe2
CM		 4124 * returns 0 if it found something or 1 if there are no greater leaves.
4125 * returns < 0 on io errors.
97571fd0 4126 */
234b63a0 4127int btrfs_next_leaf(struct btrfs_root *root, struct btrfs_path *path)
d97e63b6
CM		 4128{
4129 int slot;
8e73f275 4130 int level;
5f39d397 4131 struct extent_buffer *c;
8e73f275 4132 struct extent_buffer *next;
925baedd
CM		 4133 struct btrfs_key key;
4134 u32 nritems;
4135 int ret;
8e73f275
CM		 4136 int old_spinning = path->leave_spinning;
4137 int force_blocking = 0;
925baedd
CM		 4138
4139 nritems = btrfs_header_nritems(path->nodes[0]);
d397712b 4140 if (nritems == 0)
925baedd 4141 return 1;
925baedd 4142
8e73f275
CM		 4143 /*
4144 * we take the blocks in an order that upsets lockdep. Using
4145 * blocking mode is the only way around it.
4146 */
4147#ifdef CONFIG_DEBUG_LOCK_ALLOC
4148 force_blocking = 1;
4149#endif
925baedd 4150
8e73f275
CM		 4151 btrfs_item_key_to_cpu(path->nodes[0], &key, nritems - 1);
4152again:
4153 level = 1;
4154 next = NULL;
925baedd 4155 btrfs_release_path(root, path);
8e73f275 4156
a2135011 4157 path->keep_locks = 1;
8e73f275
CM		 4158
4159 if (!force_blocking)
4160 path->leave_spinning = 1;
4161
925baedd
CM		 4162 ret = btrfs_search_slot(NULL, root, &key, path, 0, 0);
4163 path->keep_locks = 0;
4164
4165 if (ret < 0)
4166 return ret;
4167
a2135011 4168 nritems = btrfs_header_nritems(path->nodes[0]);
168fd7d2
CM		 4169 /*
4170 * by releasing the path above we dropped all our locks. A balance
4171 * could have added more items next to the key that used to be
4172 * at the very end of the block. So, check again here and
4173 * advance the path if there are now more items available.
4174 */
a2135011 4175 if (nritems > 0 && path->slots[0] < nritems - 1) {
168fd7d2 4176 path->slots[0]++;
8e73f275 4177 ret = 0;
925baedd
CM		 4178 goto done;
4179 }
d97e63b6 4180
d397712b 4181 while (level < BTRFS_MAX_LEVEL) {
8e73f275
CM		 4182 if (!path->nodes[level]) {
4183 ret = 1;
4184 goto done;
4185 }
5f39d397 4186
d97e63b6
CM		 4187 slot = path->slots[level] + 1;
4188 c = path->nodes[level];
5f39d397 4189 if (slot >= btrfs_header_nritems(c)) {
d97e63b6 4190 level++;
8e73f275
CM		 4191 if (level == BTRFS_MAX_LEVEL) {
4192 ret = 1;
4193 goto done;
4194 }
d97e63b6
CM		 4195 continue;
4196 }
5f39d397 4197
925baedd
CM		 4198 if (next) {
4199 btrfs_tree_unlock(next);
5f39d397 4200 free_extent_buffer(next);
925baedd 4201 }
5f39d397 4202
8e73f275
CM		 4203 next = c;
4204 ret = read_block_for_search(NULL, root, path, &next, level,
4205 slot, &key);
4206 if (ret == -EAGAIN)
4207 goto again;
5f39d397 4208
5cd57b2c 4209 if (!path->skip_locking) {
8e73f275
CM		 4210 ret = btrfs_try_spin_lock(next);
4211 if (!ret) {
4212 btrfs_set_path_blocking(path);
4213 btrfs_tree_lock(next);
4214 if (!force_blocking)
4215 btrfs_clear_path_blocking(path, next);
4216 }
4217 if (force_blocking)
4218 btrfs_set_lock_blocking(next);
5cd57b2c 4219 }
d97e63b6
CM		 4220 break;
4221 }
4222 path->slots[level] = slot;
d397712b 4223 while (1) {
d97e63b6
CM		 4224 level--;
4225 c = path->nodes[level];
925baedd
CM		 4226 if (path->locks[level])
4227 btrfs_tree_unlock(c);
8e73f275 4228
5f39d397 4229 free_extent_buffer(c);
d97e63b6
CM		 4230 path->nodes[level] = next;
4231 path->slots[level] = 0;
a74a4b97
CM		 4232 if (!path->skip_locking)
4233 path->locks[level] = 1;
8e73f275 4234
d97e63b6
CM		 4235 if (!level)
4236 break;
b4ce94de 4237
8e73f275
CM		 4238 ret = read_block_for_search(NULL, root, path, &next, level,
4239 0, &key);
4240 if (ret == -EAGAIN)
4241 goto again;
4242
5cd57b2c 4243 if (!path->skip_locking) {
b9447ef8 4244 btrfs_assert_tree_locked(path->nodes[level]);
8e73f275
CM		 4245 ret = btrfs_try_spin_lock(next);
4246 if (!ret) {
4247 btrfs_set_path_blocking(path);
4248 btrfs_tree_lock(next);
4249 if (!force_blocking)
4250 btrfs_clear_path_blocking(path, next);
4251 }
4252 if (force_blocking)
4253 btrfs_set_lock_blocking(next);
5cd57b2c 4254 }
d97e63b6 4255 }
8e73f275 4256 ret = 0;
925baedd
CM		 4257done:
4258 unlock_up(path, 0, 1);
8e73f275
CM		 4259 path->leave_spinning = old_spinning;
4260 if (!old_spinning)
4261 btrfs_set_path_blocking(path);
4262
4263 return ret;
d97e63b6 4264}
0b86a832 4265
3f157a2f
CM		 4266/*
4267 * this uses btrfs_prev_leaf to walk backwards in the tree, and keeps
4268 * searching until it gets past min_objectid or finds an item of 'type'
4269 *
4270 * returns 0 if something is found, 1 if nothing was found and < 0 on error
4271 */
0b86a832
CM		 4272int btrfs_previous_item(struct btrfs_root *root,
4273 struct btrfs_path *path, u64 min_objectid,
4274 int type)
4275{
4276 struct btrfs_key found_key;
4277 struct extent_buffer *leaf;
e02119d5 4278 u32 nritems;
0b86a832
CM		 4279 int ret;
4280
d397712b 4281 while (1) {
0b86a832 4282 if (path->slots[0] == 0) {
b4ce94de 4283 btrfs_set_path_blocking(path);
0b86a832
CM		 4284 ret = btrfs_prev_leaf(root, path);
4285 if (ret != 0)
4286 return ret;
4287 } else {
4288 path->slots[0]--;
4289 }
4290 leaf = path->nodes[0];
e02119d5
CM		 4291 nritems = btrfs_header_nritems(leaf);
4292 if (nritems == 0)
4293 return 1;
4294 if (path->slots[0] == nritems)
4295 path->slots[0]--;
4296
0b86a832
CM		 4297 btrfs_item_key_to_cpu(leaf, &found_key, path->slots[0]);
4298 if (found_key.type == type)
4299 return 0;
e02119d5
CM		 4300 if (found_key.objectid < min_objectid)
4301 break;
4302 if (found_key.objectid == min_objectid &&
4303 found_key.type < type)
4304 break;
0b86a832
CM		 4305 }
4306 return 1;
4307}
kernel source for telekom puls (alcatel/mediatek)