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