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