projects / deliverable / linux.git / blame
? search:
summary | shortlog | log | commit | commitdiff | tree
blob | blame (incremental) | history | HEAD
Btrfs: rework qgroup accounting
[deliverable/linux.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>
bd989ba3 21#include <linux/rbtree.h>
eb60ceac
CM		 22#include "ctree.h"
23#include "disk-io.h"
7f5c1516 24#include "transaction.h"
5f39d397 25#include "print-tree.h"
925baedd 26#include "locking.h"
9a8dd150 27
e089f05c
CM		 28static int split_node(struct btrfs_trans_handle *trans, struct btrfs_root
29 *root, struct btrfs_path *path, int level);
30static int split_leaf(struct btrfs_trans_handle *trans, struct btrfs_root
d4dbff95 31 *root, struct btrfs_key *ins_key,
cc0c5538 32 struct btrfs_path *path, int data_size, int extend);
5f39d397
CM		 33static int push_node_left(struct btrfs_trans_handle *trans,
34 struct btrfs_root *root, struct extent_buffer *dst,
971a1f66 35 struct extent_buffer *src, int empty);
5f39d397
CM		 36static int balance_node_right(struct btrfs_trans_handle *trans,
37 struct btrfs_root *root,
38 struct extent_buffer *dst_buf,
39 struct extent_buffer *src_buf);
afe5fea7
TI		 40static void del_ptr(struct btrfs_root *root, struct btrfs_path *path,
41 int level, int slot);
5de865ee 42static int tree_mod_log_free_eb(struct btrfs_fs_info *fs_info,
f230475e 43 struct extent_buffer *eb);
d97e63b6 44
df24a2b9 45struct btrfs_path *btrfs_alloc_path(void)
2c90e5d6 46{
df24a2b9 47 struct btrfs_path *path;
e00f7308 48 path = kmem_cache_zalloc(btrfs_path_cachep, GFP_NOFS);
df24a2b9 49 return path;
2c90e5d6
CM		 50}
51
b4ce94de
CM		 52/*
53 * set all locked nodes in the path to blocking locks. This should
54 * be done before scheduling
55 */
56noinline void btrfs_set_path_blocking(struct btrfs_path *p)
57{
58 int i;
59 for (i = 0; i < BTRFS_MAX_LEVEL; i++) {
bd681513
CM		 60 if (!p->nodes[i] || !p->locks[i])
61 continue;
62 btrfs_set_lock_blocking_rw(p->nodes[i], p->locks[i]);
63 if (p->locks[i] == BTRFS_READ_LOCK)
64 p->locks[i] = BTRFS_READ_LOCK_BLOCKING;
65 else if (p->locks[i] == BTRFS_WRITE_LOCK)
66 p->locks[i] = BTRFS_WRITE_LOCK_BLOCKING;
b4ce94de
CM		 67 }
68}
69
70/*
71 * reset all the locked nodes in the patch to spinning locks.
4008c04a
CM		 72 *
73 * held is used to keep lockdep happy, when lockdep is enabled
74 * we set held to a blocking lock before we go around and
75 * retake all the spinlocks in the path. You can safely use NULL
76 * for held
b4ce94de 77 */
4008c04a 78noinline void btrfs_clear_path_blocking(struct btrfs_path *p,
bd681513 79 struct extent_buffer *held, int held_rw)
b4ce94de
CM		 80{
81 int i;
4008c04a
CM		 82
83#ifdef CONFIG_DEBUG_LOCK_ALLOC
84 /* lockdep really cares that we take all of these spinlocks
85 * in the right order. If any of the locks in the path are not
86 * currently blocking, it is going to complain. So, make really
87 * really sure by forcing the path to blocking before we clear
88 * the path blocking.
89 */
bd681513
CM		 90 if (held) {
91 btrfs_set_lock_blocking_rw(held, held_rw);
92 if (held_rw == BTRFS_WRITE_LOCK)
93 held_rw = BTRFS_WRITE_LOCK_BLOCKING;
94 else if (held_rw == BTRFS_READ_LOCK)
95 held_rw = BTRFS_READ_LOCK_BLOCKING;
96 }
4008c04a
CM		 97 btrfs_set_path_blocking(p);
98#endif
99
100 for (i = BTRFS_MAX_LEVEL - 1; i >= 0; i--) {
bd681513
CM		 101 if (p->nodes[i] && p->locks[i]) {
102 btrfs_clear_lock_blocking_rw(p->nodes[i], p->locks[i]);
103 if (p->locks[i] == BTRFS_WRITE_LOCK_BLOCKING)
104 p->locks[i] = BTRFS_WRITE_LOCK;
105 else if (p->locks[i] == BTRFS_READ_LOCK_BLOCKING)
106 p->locks[i] = BTRFS_READ_LOCK;
107 }
b4ce94de 108 }
4008c04a
CM		 109
110#ifdef CONFIG_DEBUG_LOCK_ALLOC
111 if (held)
bd681513 112 btrfs_clear_lock_blocking_rw(held, held_rw);
4008c04a 113#endif
b4ce94de
CM		 114}
115
d352ac68 116/* this also releases the path */
df24a2b9 117void btrfs_free_path(struct btrfs_path *p)
be0e5c09 118{
ff175d57
JJ		 119 if (!p)
120 return;
b3b4aa74 121 btrfs_release_path(p);
df24a2b9 122 kmem_cache_free(btrfs_path_cachep, p);
be0e5c09
CM		 123}
124
d352ac68
CM		 125/*
126 * path release drops references on the extent buffers in the path
127 * and it drops any locks held by this path
128 *
129 * It is safe to call this on paths that no locks or extent buffers held.
130 */
b3b4aa74 131noinline void btrfs_release_path(struct btrfs_path *p)
eb60ceac
CM		 132{
133 int i;
a2135011 134
234b63a0 135 for (i = 0; i < BTRFS_MAX_LEVEL; i++) {
3f157a2f 136 p->slots[i] = 0;
eb60ceac 137 if (!p->nodes[i])
925baedd
CM		 138 continue;
139 if (p->locks[i]) {
bd681513 140 btrfs_tree_unlock_rw(p->nodes[i], p->locks[i]);
925baedd
CM		 141 p->locks[i] = 0;
142 }
5f39d397 143 free_extent_buffer(p->nodes[i]);
3f157a2f 144 p->nodes[i] = NULL;
eb60ceac
CM		 145 }
146}
147
d352ac68
CM		 148/*
149 * safely gets a reference on the root node of a tree. A lock
150 * is not taken, so a concurrent writer may put a different node
151 * at the root of the tree. See btrfs_lock_root_node for the
152 * looping required.
153 *
154 * The extent buffer returned by this has a reference taken, so
155 * it won't disappear. It may stop being the root of the tree
156 * at any time because there are no locks held.
157 */
925baedd
CM		 158struct extent_buffer *btrfs_root_node(struct btrfs_root *root)
159{
160 struct extent_buffer *eb;
240f62c8 161
3083ee2e
JB		 162 while (1) {
163 rcu_read_lock();
164 eb = rcu_dereference(root->node);
165
166 /*
167 * RCU really hurts here, we could free up the root node because
168 * it was cow'ed but we may not get the new root node yet so do
169 * the inc_not_zero dance and if it doesn't work then
170 * synchronize_rcu and try again.
171 */
172 if (atomic_inc_not_zero(&eb->refs)) {
173 rcu_read_unlock();
174 break;
175 }
176 rcu_read_unlock();
177 synchronize_rcu();
178 }
925baedd
CM		 179 return eb;
180}
181
d352ac68
CM		 182/* loop around taking references on and locking the root node of the
183 * tree until you end up with a lock on the root. A locked buffer
184 * is returned, with a reference held.
185 */
925baedd
CM		 186struct extent_buffer *btrfs_lock_root_node(struct btrfs_root *root)
187{
188 struct extent_buffer *eb;
189
d397712b 190 while (1) {
925baedd
CM		 191 eb = btrfs_root_node(root);
192 btrfs_tree_lock(eb);
240f62c8 193 if (eb == root->node)
925baedd 194 break;
925baedd
CM		 195 btrfs_tree_unlock(eb);
196 free_extent_buffer(eb);
197 }
198 return eb;
199}
200
bd681513
CM		 201/* loop around taking references on and locking the root node of the
202 * tree until you end up with a lock on the root. A locked buffer
203 * is returned, with a reference held.
204 */
48a3b636 205static struct extent_buffer *btrfs_read_lock_root_node(struct btrfs_root *root)
bd681513
CM		 206{
207 struct extent_buffer *eb;
208
209 while (1) {
210 eb = btrfs_root_node(root);
211 btrfs_tree_read_lock(eb);
212 if (eb == root->node)
213 break;
214 btrfs_tree_read_unlock(eb);
215 free_extent_buffer(eb);
216 }
217 return eb;
218}
219
d352ac68
CM		 220/* cowonly root (everything not a reference counted cow subvolume), just get
221 * put onto a simple dirty list. transaction.c walks this to make sure they
222 * get properly updated on disk.
223 */
0b86a832
CM		 224static void add_root_to_dirty_list(struct btrfs_root *root)
225{
e5846fc6 226 spin_lock(&root->fs_info->trans_lock);
27cdeb70
MX		 227 if (test_bit(BTRFS_ROOT_TRACK_DIRTY, &root->state) &&
228 list_empty(&root->dirty_list)) {
0b86a832
CM		 229 list_add(&root->dirty_list,
230 &root->fs_info->dirty_cowonly_roots);
231 }
e5846fc6 232 spin_unlock(&root->fs_info->trans_lock);
0b86a832
CM		 233}
234
d352ac68
CM		 235/*
236 * used by snapshot creation to make a copy of a root for a tree with
237 * a given objectid. The buffer with the new root node is returned in
238 * cow_ret, and this func returns zero on success or a negative error code.
239 */
be20aa9d
CM		 240int btrfs_copy_root(struct btrfs_trans_handle *trans,
241 struct btrfs_root *root,
242 struct extent_buffer *buf,
243 struct extent_buffer **cow_ret, u64 new_root_objectid)
244{
245 struct extent_buffer *cow;
be20aa9d
CM		 246 int ret = 0;
247 int level;
5d4f98a2 248 struct btrfs_disk_key disk_key;
be20aa9d 249
27cdeb70
MX		 250 WARN_ON(test_bit(BTRFS_ROOT_REF_COWS, &root->state) &&
251 trans->transid != root->fs_info->running_transaction->transid);
252 WARN_ON(test_bit(BTRFS_ROOT_REF_COWS, &root->state) &&
253 trans->transid != root->last_trans);
be20aa9d
CM		 254
255 level = btrfs_header_level(buf);
5d4f98a2
YZ		 256 if (level == 0)
257 btrfs_item_key(buf, &disk_key, 0);
258 else
259 btrfs_node_key(buf, &disk_key, 0);
31840ae1 260
5d4f98a2
YZ		 261 cow = btrfs_alloc_free_block(trans, root, buf->len, 0,
262 new_root_objectid, &disk_key, level,
5581a51a 263 buf->start, 0);
5d4f98a2 264 if (IS_ERR(cow))
be20aa9d
CM		 265 return PTR_ERR(cow);
266
267 copy_extent_buffer(cow, buf, 0, 0, cow->len);
268 btrfs_set_header_bytenr(cow, cow->start);
269 btrfs_set_header_generation(cow, trans->transid);
5d4f98a2
YZ		 270 btrfs_set_header_backref_rev(cow, BTRFS_MIXED_BACKREF_REV);
271 btrfs_clear_header_flag(cow, BTRFS_HEADER_FLAG_WRITTEN |
272 BTRFS_HEADER_FLAG_RELOC);
273 if (new_root_objectid == BTRFS_TREE_RELOC_OBJECTID)
274 btrfs_set_header_flag(cow, BTRFS_HEADER_FLAG_RELOC);
275 else
276 btrfs_set_header_owner(cow, new_root_objectid);
be20aa9d 277
0a4e5586 278 write_extent_buffer(cow, root->fs_info->fsid, btrfs_header_fsid(),
2b82032c
YZ		 279 BTRFS_FSID_SIZE);
280
be20aa9d 281 WARN_ON(btrfs_header_generation(buf) > trans->transid);
5d4f98a2 282 if (new_root_objectid == BTRFS_TREE_RELOC_OBJECTID)
66d7e7f0 283 ret = btrfs_inc_ref(trans, root, cow, 1, 1);
5d4f98a2 284 else
66d7e7f0 285 ret = btrfs_inc_ref(trans, root, cow, 0, 1);
4aec2b52 286
be20aa9d
CM		 287 if (ret)
288 return ret;
289
290 btrfs_mark_buffer_dirty(cow);
291 *cow_ret = cow;
292 return 0;
293}
294
bd989ba3
JS		 295enum mod_log_op {
296 MOD_LOG_KEY_REPLACE,
297 MOD_LOG_KEY_ADD,
298 MOD_LOG_KEY_REMOVE,
299 MOD_LOG_KEY_REMOVE_WHILE_FREEING,
300 MOD_LOG_KEY_REMOVE_WHILE_MOVING,
301 MOD_LOG_MOVE_KEYS,
302 MOD_LOG_ROOT_REPLACE,
303};
304
305struct tree_mod_move {
306 int dst_slot;
307 int nr_items;
308};
309
310struct tree_mod_root {
311 u64 logical;
312 u8 level;
313};
314
315struct tree_mod_elem {
316 struct rb_node node;
317 u64 index; /* shifted logical */
097b8a7c 318 u64 seq;
bd989ba3
JS		 319 enum mod_log_op op;
320
321 /* this is used for MOD_LOG_KEY_* and MOD_LOG_MOVE_KEYS operations */
322 int slot;
323
324 /* this is used for MOD_LOG_KEY* and MOD_LOG_ROOT_REPLACE */
325 u64 generation;
326
327 /* those are used for op == MOD_LOG_KEY_{REPLACE,REMOVE} */
328 struct btrfs_disk_key key;
329 u64 blockptr;
330
331 /* this is used for op == MOD_LOG_MOVE_KEYS */
332 struct tree_mod_move move;
333
334 /* this is used for op == MOD_LOG_ROOT_REPLACE */
335 struct tree_mod_root old_root;
336};
337
097b8a7c 338static inline void tree_mod_log_read_lock(struct btrfs_fs_info *fs_info)
bd989ba3 339{
097b8a7c 340 read_lock(&fs_info->tree_mod_log_lock);
bd989ba3
JS		 341}
342
097b8a7c
JS		 343static inline void tree_mod_log_read_unlock(struct btrfs_fs_info *fs_info)
344{
345 read_unlock(&fs_info->tree_mod_log_lock);
346}
347
348static inline void tree_mod_log_write_lock(struct btrfs_fs_info *fs_info)
349{
350 write_lock(&fs_info->tree_mod_log_lock);
351}
352
353static inline void tree_mod_log_write_unlock(struct btrfs_fs_info *fs_info)
354{
355 write_unlock(&fs_info->tree_mod_log_lock);
356}
357
fc36ed7e 358/*
fcebe456 359 * Pull a new tree mod seq number for our operation.
fc36ed7e 360 */
fcebe456 361static inline u64 btrfs_inc_tree_mod_seq(struct btrfs_fs_info *fs_info)
fc36ed7e
JS		 362{
363 return atomic64_inc_return(&fs_info->tree_mod_seq);
364}
365
097b8a7c
JS		 366/*
367 * This adds a new blocker to the tree mod log's blocker list if the @elem
368 * passed does not already have a sequence number set. So when a caller expects
369 * to record tree modifications, it should ensure to set elem->seq to zero
370 * before calling btrfs_get_tree_mod_seq.
371 * Returns a fresh, unused tree log modification sequence number, even if no new
372 * blocker was added.
373 */
374u64 btrfs_get_tree_mod_seq(struct btrfs_fs_info *fs_info,
375 struct seq_list *elem)
bd989ba3 376{
097b8a7c 377 tree_mod_log_write_lock(fs_info);
bd989ba3 378 spin_lock(&fs_info->tree_mod_seq_lock);
097b8a7c 379 if (!elem->seq) {
fcebe456 380 elem->seq = btrfs_inc_tree_mod_seq(fs_info);
097b8a7c
JS		 381 list_add_tail(&elem->list, &fs_info->tree_mod_seq_list);
382 }
bd989ba3 383 spin_unlock(&fs_info->tree_mod_seq_lock);
097b8a7c
JS		 384 tree_mod_log_write_unlock(fs_info);
385
fcebe456 386 return elem->seq;
bd989ba3
JS		 387}
388
389void btrfs_put_tree_mod_seq(struct btrfs_fs_info *fs_info,
390 struct seq_list *elem)
391{
392 struct rb_root *tm_root;
393 struct rb_node *node;
394 struct rb_node *next;
395 struct seq_list *cur_elem;
396 struct tree_mod_elem *tm;
397 u64 min_seq = (u64)-1;
398 u64 seq_putting = elem->seq;
399
400 if (!seq_putting)
401 return;
402
bd989ba3
JS		 403 spin_lock(&fs_info->tree_mod_seq_lock);
404 list_del(&elem->list);
097b8a7c 405 elem->seq = 0;
bd989ba3
JS		 406
407 list_for_each_entry(cur_elem, &fs_info->tree_mod_seq_list, list) {
097b8a7c 408 if (cur_elem->seq < min_seq) {
bd989ba3
JS		 409 if (seq_putting > cur_elem->seq) {
410 /*
411 * blocker with lower sequence number exists, we
412 * cannot remove anything from the log
413 */
097b8a7c
JS		 414 spin_unlock(&fs_info->tree_mod_seq_lock);
415 return;
bd989ba3
JS		 416 }
417 min_seq = cur_elem->seq;
418 }
419 }
097b8a7c
JS		 420 spin_unlock(&fs_info->tree_mod_seq_lock);
421
bd989ba3
JS		 422 /*
423 * anything that's lower than the lowest existing (read: blocked)
424 * sequence number can be removed from the tree.
425 */
097b8a7c 426 tree_mod_log_write_lock(fs_info);
bd989ba3
JS		 427 tm_root = &fs_info->tree_mod_log;
428 for (node = rb_first(tm_root); node; node = next) {
429 next = rb_next(node);
430 tm = container_of(node, struct tree_mod_elem, node);
097b8a7c 431 if (tm->seq > min_seq)
bd989ba3
JS		 432 continue;
433 rb_erase(node, tm_root);
bd989ba3
JS		 434 kfree(tm);
435 }
097b8a7c 436 tree_mod_log_write_unlock(fs_info);
bd989ba3
JS		 437}
438
439/*
440 * key order of the log:
441 * index -> sequence
442 *
443 * the index is the shifted logical of the *new* root node for root replace
444 * operations, or the shifted logical of the affected block for all other
445 * operations.
5de865ee
FDBM		 446 *
447 * Note: must be called with write lock (tree_mod_log_write_lock).
bd989ba3
JS		 448 */
449static noinline int
450__tree_mod_log_insert(struct btrfs_fs_info *fs_info, struct tree_mod_elem *tm)
451{
452 struct rb_root *tm_root;
453 struct rb_node **new;
454 struct rb_node *parent = NULL;
455 struct tree_mod_elem *cur;
c8cc6341
JB		 456
457 BUG_ON(!tm);
458
fcebe456 459 tm->seq = btrfs_inc_tree_mod_seq(fs_info);
bd989ba3 460
bd989ba3
JS		 461 tm_root = &fs_info->tree_mod_log;
462 new = &tm_root->rb_node;
463 while (*new) {
464 cur = container_of(*new, struct tree_mod_elem, node);
465 parent = *new;
466 if (cur->index < tm->index)
467 new = &((*new)->rb_left);
468 else if (cur->index > tm->index)
469 new = &((*new)->rb_right);
097b8a7c 470 else if (cur->seq < tm->seq)
bd989ba3 471 new = &((*new)->rb_left);
097b8a7c 472 else if (cur->seq > tm->seq)
bd989ba3 473 new = &((*new)->rb_right);
5de865ee
FDBM		 474 else
475 return -EEXIST;
bd989ba3
JS		 476 }
477
478 rb_link_node(&tm->node, parent, new);
479 rb_insert_color(&tm->node, tm_root);
5de865ee 480 return 0;
bd989ba3
JS		 481}
482
097b8a7c
JS		 483/*
484 * Determines if logging can be omitted. Returns 1 if it can. Otherwise, it
485 * returns zero with the tree_mod_log_lock acquired. The caller must hold
486 * this until all tree mod log insertions are recorded in the rb tree and then
487 * call tree_mod_log_write_unlock() to release.
488 */
e9b7fd4d
JS		 489static inline int tree_mod_dont_log(struct btrfs_fs_info *fs_info,
490 struct extent_buffer *eb) {
491 smp_mb();
492 if (list_empty(&(fs_info)->tree_mod_seq_list))
493 return 1;
097b8a7c
JS		 494 if (eb && btrfs_header_level(eb) == 0)
495 return 1;
5de865ee
FDBM		 496
497 tree_mod_log_write_lock(fs_info);
498 if (list_empty(&(fs_info)->tree_mod_seq_list)) {
499 tree_mod_log_write_unlock(fs_info);
500 return 1;
501 }
502
e9b7fd4d
JS		 503 return 0;
504}
505
5de865ee
FDBM		 506/* Similar to tree_mod_dont_log, but doesn't acquire any locks. */
507static inline int tree_mod_need_log(const struct btrfs_fs_info *fs_info,
508 struct extent_buffer *eb)
509{
510 smp_mb();
511 if (list_empty(&(fs_info)->tree_mod_seq_list))
512 return 0;
513 if (eb && btrfs_header_level(eb) == 0)
514 return 0;
515
516 return 1;
517}
518
519static struct tree_mod_elem *
520alloc_tree_mod_elem(struct extent_buffer *eb, int slot,
521 enum mod_log_op op, gfp_t flags)
bd989ba3 522{
097b8a7c 523 struct tree_mod_elem *tm;
bd989ba3 524
c8cc6341
JB		 525 tm = kzalloc(sizeof(*tm), flags);
526 if (!tm)
5de865ee 527 return NULL;
bd989ba3
JS		 528
529 tm->index = eb->start >> PAGE_CACHE_SHIFT;
530 if (op != MOD_LOG_KEY_ADD) {
531 btrfs_node_key(eb, &tm->key, slot);
532 tm->blockptr = btrfs_node_blockptr(eb, slot);
533 }
534 tm->op = op;
535 tm->slot = slot;
536 tm->generation = btrfs_node_ptr_generation(eb, slot);
5de865ee 537 RB_CLEAR_NODE(&tm->node);
bd989ba3 538
5de865ee 539 return tm;
097b8a7c
JS		 540}
541
542static noinline int
c8cc6341
JB		 543tree_mod_log_insert_key(struct btrfs_fs_info *fs_info,
544 struct extent_buffer *eb, int slot,
545 enum mod_log_op op, gfp_t flags)
097b8a7c 546{
5de865ee
FDBM		 547 struct tree_mod_elem *tm;
548 int ret;
549
550 if (!tree_mod_need_log(fs_info, eb))
551 return 0;
552
553 tm = alloc_tree_mod_elem(eb, slot, op, flags);
554 if (!tm)
555 return -ENOMEM;
556
557 if (tree_mod_dont_log(fs_info, eb)) {
558 kfree(tm);
097b8a7c 559 return 0;
5de865ee
FDBM		 560 }
561
562 ret = __tree_mod_log_insert(fs_info, tm);
563 tree_mod_log_write_unlock(fs_info);
564 if (ret)
565 kfree(tm);
097b8a7c 566
5de865ee 567 return ret;
097b8a7c
JS		 568}
569
bd989ba3
JS		 570static noinline int
571tree_mod_log_insert_move(struct btrfs_fs_info *fs_info,
572 struct extent_buffer *eb, int dst_slot, int src_slot,
573 int nr_items, gfp_t flags)
574{
5de865ee
FDBM		 575 struct tree_mod_elem *tm = NULL;
576 struct tree_mod_elem **tm_list = NULL;
577 int ret = 0;
bd989ba3 578 int i;
5de865ee 579 int locked = 0;
bd989ba3 580
5de865ee 581 if (!tree_mod_need_log(fs_info, eb))
f395694c 582 return 0;
bd989ba3 583
5de865ee
FDBM		 584 tm_list = kzalloc(nr_items * sizeof(struct tree_mod_elem *), flags);
585 if (!tm_list)
586 return -ENOMEM;
587
588 tm = kzalloc(sizeof(*tm), flags);
589 if (!tm) {
590 ret = -ENOMEM;
591 goto free_tms;
592 }
593
594 tm->index = eb->start >> PAGE_CACHE_SHIFT;
595 tm->slot = src_slot;
596 tm->move.dst_slot = dst_slot;
597 tm->move.nr_items = nr_items;
598 tm->op = MOD_LOG_MOVE_KEYS;
599
600 for (i = 0; i + dst_slot < src_slot && i < nr_items; i++) {
601 tm_list[i] = alloc_tree_mod_elem(eb, i + dst_slot,
602 MOD_LOG_KEY_REMOVE_WHILE_MOVING, flags);
603 if (!tm_list[i]) {
604 ret = -ENOMEM;
605 goto free_tms;
606 }
607 }
608
609 if (tree_mod_dont_log(fs_info, eb))
610 goto free_tms;
611 locked = 1;
612
01763a2e
JS		 613 /*
614 * When we override something during the move, we log these removals.
615 * This can only happen when we move towards the beginning of the
616 * buffer, i.e. dst_slot < src_slot.
617 */
bd989ba3 618 for (i = 0; i + dst_slot < src_slot && i < nr_items; i++) {
5de865ee
FDBM		 619 ret = __tree_mod_log_insert(fs_info, tm_list[i]);
620 if (ret)
621 goto free_tms;
bd989ba3
JS		 622 }
623
5de865ee
FDBM		 624 ret = __tree_mod_log_insert(fs_info, tm);
625 if (ret)
626 goto free_tms;
627 tree_mod_log_write_unlock(fs_info);
628 kfree(tm_list);
f395694c 629
5de865ee
FDBM		 630 return 0;
631free_tms:
632 for (i = 0; i < nr_items; i++) {
633 if (tm_list[i] && !RB_EMPTY_NODE(&tm_list[i]->node))
634 rb_erase(&tm_list[i]->node, &fs_info->tree_mod_log);
635 kfree(tm_list[i]);
636 }
637 if (locked)
638 tree_mod_log_write_unlock(fs_info);
639 kfree(tm_list);
640 kfree(tm);
bd989ba3 641
5de865ee 642 return ret;
bd989ba3
JS		 643}
644
5de865ee
FDBM		 645static inline int
646__tree_mod_log_free_eb(struct btrfs_fs_info *fs_info,
647 struct tree_mod_elem **tm_list,
648 int nritems)
097b8a7c 649{
5de865ee 650 int i, j;
097b8a7c
JS		 651 int ret;
652
097b8a7c 653 for (i = nritems - 1; i >= 0; i--) {
5de865ee
FDBM		 654 ret = __tree_mod_log_insert(fs_info, tm_list[i]);
655 if (ret) {
656 for (j = nritems - 1; j > i; j--)
657 rb_erase(&tm_list[j]->node,
658 &fs_info->tree_mod_log);
659 return ret;
660 }
097b8a7c 661 }
5de865ee
FDBM		 662
663 return 0;
097b8a7c
JS		 664}
665
bd989ba3
JS		 666static noinline int
667tree_mod_log_insert_root(struct btrfs_fs_info *fs_info,
668 struct extent_buffer *old_root,
90f8d62e
JS		 669 struct extent_buffer *new_root, gfp_t flags,
670 int log_removal)
bd989ba3 671{
5de865ee
FDBM		 672 struct tree_mod_elem *tm = NULL;
673 struct tree_mod_elem **tm_list = NULL;
674 int nritems = 0;
675 int ret = 0;
676 int i;
bd989ba3 677
5de865ee 678 if (!tree_mod_need_log(fs_info, NULL))
097b8a7c
JS		 679 return 0;
680
5de865ee
FDBM		 681 if (log_removal && btrfs_header_level(old_root) > 0) {
682 nritems = btrfs_header_nritems(old_root);
683 tm_list = kzalloc(nritems * sizeof(struct tree_mod_elem *),
684 flags);
685 if (!tm_list) {
686 ret = -ENOMEM;
687 goto free_tms;
688 }
689 for (i = 0; i < nritems; i++) {
690 tm_list[i] = alloc_tree_mod_elem(old_root, i,
691 MOD_LOG_KEY_REMOVE_WHILE_FREEING, flags);
692 if (!tm_list[i]) {
693 ret = -ENOMEM;
694 goto free_tms;
695 }
696 }
697 }
d9abbf1c 698
c8cc6341 699 tm = kzalloc(sizeof(*tm), flags);
5de865ee
FDBM		 700 if (!tm) {
701 ret = -ENOMEM;
702 goto free_tms;
703 }
bd989ba3
JS		 704
705 tm->index = new_root->start >> PAGE_CACHE_SHIFT;
706 tm->old_root.logical = old_root->start;
707 tm->old_root.level = btrfs_header_level(old_root);
708 tm->generation = btrfs_header_generation(old_root);
709 tm->op = MOD_LOG_ROOT_REPLACE;
710
5de865ee
FDBM		 711 if (tree_mod_dont_log(fs_info, NULL))
712 goto free_tms;
713
714 if (tm_list)
715 ret = __tree_mod_log_free_eb(fs_info, tm_list, nritems);
716 if (!ret)
717 ret = __tree_mod_log_insert(fs_info, tm);
718
719 tree_mod_log_write_unlock(fs_info);
720 if (ret)
721 goto free_tms;
722 kfree(tm_list);
723
724 return ret;
725
726free_tms:
727 if (tm_list) {
728 for (i = 0; i < nritems; i++)
729 kfree(tm_list[i]);
730 kfree(tm_list);
731 }
732 kfree(tm);
733
734 return ret;
bd989ba3
JS		 735}
736
737static struct tree_mod_elem *
738__tree_mod_log_search(struct btrfs_fs_info *fs_info, u64 start, u64 min_seq,
739 int smallest)
740{
741 struct rb_root *tm_root;
742 struct rb_node *node;
743 struct tree_mod_elem *cur = NULL;
744 struct tree_mod_elem *found = NULL;
745 u64 index = start >> PAGE_CACHE_SHIFT;
746
097b8a7c 747 tree_mod_log_read_lock(fs_info);
bd989ba3
JS		 748 tm_root = &fs_info->tree_mod_log;
749 node = tm_root->rb_node;
750 while (node) {
751 cur = container_of(node, struct tree_mod_elem, node);
752 if (cur->index < index) {
753 node = node->rb_left;
754 } else if (cur->index > index) {
755 node = node->rb_right;
097b8a7c 756 } else if (cur->seq < min_seq) {
bd989ba3
JS		 757 node = node->rb_left;
758 } else if (!smallest) {
759 /* we want the node with the highest seq */
760 if (found)
097b8a7c 761 BUG_ON(found->seq > cur->seq);
bd989ba3
JS		 762 found = cur;
763 node = node->rb_left;
097b8a7c 764 } else if (cur->seq > min_seq) {
bd989ba3
JS		 765 /* we want the node with the smallest seq */
766 if (found)
097b8a7c 767 BUG_ON(found->seq < cur->seq);
bd989ba3
JS		 768 found = cur;
769 node = node->rb_right;
770 } else {
771 found = cur;
772 break;
773 }
774 }
097b8a7c 775 tree_mod_log_read_unlock(fs_info);
bd989ba3
JS		 776
777 return found;
778}
779
780/*
781 * this returns the element from the log with the smallest time sequence
782 * value that's in the log (the oldest log item). any element with a time
783 * sequence lower than min_seq will be ignored.
784 */
785static struct tree_mod_elem *
786tree_mod_log_search_oldest(struct btrfs_fs_info *fs_info, u64 start,
787 u64 min_seq)
788{
789 return __tree_mod_log_search(fs_info, start, min_seq, 1);
790}
791
792/*
793 * this returns the element from the log with the largest time sequence
794 * value that's in the log (the most recent log item). any element with
795 * a time sequence lower than min_seq will be ignored.
796 */
797static struct tree_mod_elem *
798tree_mod_log_search(struct btrfs_fs_info *fs_info, u64 start, u64 min_seq)
799{
800 return __tree_mod_log_search(fs_info, start, min_seq, 0);
801}
802
5de865ee 803static noinline int
bd989ba3
JS		 804tree_mod_log_eb_copy(struct btrfs_fs_info *fs_info, struct extent_buffer *dst,
805 struct extent_buffer *src, unsigned long dst_offset,
90f8d62e 806 unsigned long src_offset, int nr_items)
bd989ba3 807{
5de865ee
FDBM		 808 int ret = 0;
809 struct tree_mod_elem **tm_list = NULL;
810 struct tree_mod_elem **tm_list_add, **tm_list_rem;
bd989ba3 811 int i;
5de865ee 812 int locked = 0;
bd989ba3 813
5de865ee
FDBM		 814 if (!tree_mod_need_log(fs_info, NULL))
815 return 0;
bd989ba3 816
c8cc6341 817 if (btrfs_header_level(dst) == 0 && btrfs_header_level(src) == 0)
5de865ee
FDBM		 818 return 0;
819
820 tm_list = kzalloc(nr_items * 2 * sizeof(struct tree_mod_elem *),
821 GFP_NOFS);
822 if (!tm_list)
823 return -ENOMEM;
bd989ba3 824
5de865ee
FDBM		 825 tm_list_add = tm_list;
826 tm_list_rem = tm_list + nr_items;
bd989ba3 827 for (i = 0; i < nr_items; i++) {
5de865ee
FDBM		 828 tm_list_rem[i] = alloc_tree_mod_elem(src, i + src_offset,
829 MOD_LOG_KEY_REMOVE, GFP_NOFS);
830 if (!tm_list_rem[i]) {
831 ret = -ENOMEM;
832 goto free_tms;
833 }
834
835 tm_list_add[i] = alloc_tree_mod_elem(dst, i + dst_offset,
836 MOD_LOG_KEY_ADD, GFP_NOFS);
837 if (!tm_list_add[i]) {
838 ret = -ENOMEM;
839 goto free_tms;
840 }
841 }
842
843 if (tree_mod_dont_log(fs_info, NULL))
844 goto free_tms;
845 locked = 1;
846
847 for (i = 0; i < nr_items; i++) {
848 ret = __tree_mod_log_insert(fs_info, tm_list_rem[i]);
849 if (ret)
850 goto free_tms;
851 ret = __tree_mod_log_insert(fs_info, tm_list_add[i]);
852 if (ret)
853 goto free_tms;
bd989ba3 854 }
5de865ee
FDBM		 855
856 tree_mod_log_write_unlock(fs_info);
857 kfree(tm_list);
858
859 return 0;
860
861free_tms:
862 for (i = 0; i < nr_items * 2; i++) {
863 if (tm_list[i] && !RB_EMPTY_NODE(&tm_list[i]->node))
864 rb_erase(&tm_list[i]->node, &fs_info->tree_mod_log);
865 kfree(tm_list[i]);
866 }
867 if (locked)
868 tree_mod_log_write_unlock(fs_info);
869 kfree(tm_list);
870
871 return ret;
bd989ba3
JS		 872}
873
874static inline void
875tree_mod_log_eb_move(struct btrfs_fs_info *fs_info, struct extent_buffer *dst,
876 int dst_offset, int src_offset, int nr_items)
877{
878 int ret;
879 ret = tree_mod_log_insert_move(fs_info, dst, dst_offset, src_offset,
880 nr_items, GFP_NOFS);
881 BUG_ON(ret < 0);
882}
883
097b8a7c 884static noinline void
bd989ba3 885tree_mod_log_set_node_key(struct btrfs_fs_info *fs_info,
32adf090 886 struct extent_buffer *eb, int slot, int atomic)
bd989ba3
JS		 887{
888 int ret;
889
78357766 890 ret = tree_mod_log_insert_key(fs_info, eb, slot,
c8cc6341
JB		 891 MOD_LOG_KEY_REPLACE,
892 atomic ? GFP_ATOMIC : GFP_NOFS);
bd989ba3
JS		 893 BUG_ON(ret < 0);
894}
895
5de865ee 896static noinline int
097b8a7c 897tree_mod_log_free_eb(struct btrfs_fs_info *fs_info, struct extent_buffer *eb)
bd989ba3 898{
5de865ee
FDBM		 899 struct tree_mod_elem **tm_list = NULL;
900 int nritems = 0;
901 int i;
902 int ret = 0;
903
904 if (btrfs_header_level(eb) == 0)
905 return 0;
906
907 if (!tree_mod_need_log(fs_info, NULL))
908 return 0;
909
910 nritems = btrfs_header_nritems(eb);
911 tm_list = kzalloc(nritems * sizeof(struct tree_mod_elem *),
912 GFP_NOFS);
913 if (!tm_list)
914 return -ENOMEM;
915
916 for (i = 0; i < nritems; i++) {
917 tm_list[i] = alloc_tree_mod_elem(eb, i,
918 MOD_LOG_KEY_REMOVE_WHILE_FREEING, GFP_NOFS);
919 if (!tm_list[i]) {
920 ret = -ENOMEM;
921 goto free_tms;
922 }
923 }
924
e9b7fd4d 925 if (tree_mod_dont_log(fs_info, eb))
5de865ee
FDBM		 926 goto free_tms;
927
928 ret = __tree_mod_log_free_eb(fs_info, tm_list, nritems);
929 tree_mod_log_write_unlock(fs_info);
930 if (ret)
931 goto free_tms;
932 kfree(tm_list);
933
934 return 0;
935
936free_tms:
937 for (i = 0; i < nritems; i++)
938 kfree(tm_list[i]);
939 kfree(tm_list);
940
941 return ret;
bd989ba3
JS		 942}
943
097b8a7c 944static noinline void
bd989ba3 945tree_mod_log_set_root_pointer(struct btrfs_root *root,
90f8d62e
JS		 946 struct extent_buffer *new_root_node,
947 int log_removal)
bd989ba3
JS		 948{
949 int ret;
bd989ba3 950 ret = tree_mod_log_insert_root(root->fs_info, root->node,
90f8d62e 951 new_root_node, GFP_NOFS, log_removal);
bd989ba3
JS		 952 BUG_ON(ret < 0);
953}
954
5d4f98a2
YZ		 955/*
956 * check if the tree block can be shared by multiple trees
957 */
958int btrfs_block_can_be_shared(struct btrfs_root *root,
959 struct extent_buffer *buf)
960{
961 /*
962 * Tree blocks not in refernece counted trees and tree roots
963 * are never shared. If a block was allocated after the last
964 * snapshot and the block was not allocated by tree relocation,
965 * we know the block is not shared.
966 */
27cdeb70 967 if (test_bit(BTRFS_ROOT_REF_COWS, &root->state) &&
5d4f98a2
YZ		 968 buf != root->node && buf != root->commit_root &&
969 (btrfs_header_generation(buf) <=
970 btrfs_root_last_snapshot(&root->root_item) ||
971 btrfs_header_flag(buf, BTRFS_HEADER_FLAG_RELOC)))
972 return 1;
973#ifdef BTRFS_COMPAT_EXTENT_TREE_V0
27cdeb70 974 if (test_bit(BTRFS_ROOT_REF_COWS, &root->state) &&
5d4f98a2
YZ		 975 btrfs_header_backref_rev(buf) < BTRFS_MIXED_BACKREF_REV)
976 return 1;
977#endif
978 return 0;
979}
980
981static noinline int update_ref_for_cow(struct btrfs_trans_handle *trans,
982 struct btrfs_root *root,
983 struct extent_buffer *buf,
f0486c68
YZ		 984 struct extent_buffer *cow,
985 int *last_ref)
5d4f98a2
YZ		 986{
987 u64 refs;
988 u64 owner;
989 u64 flags;
990 u64 new_flags = 0;
991 int ret;
992
993 /*
994 * Backrefs update rules:
995 *
996 * Always use full backrefs for extent pointers in tree block
997 * allocated by tree relocation.
998 *
999 * If a shared tree block is no longer referenced by its owner
1000 * tree (btrfs_header_owner(buf) == root->root_key.objectid),
1001 * use full backrefs for extent pointers in tree block.
1002 *
1003 * If a tree block is been relocating
1004 * (root->root_key.objectid == BTRFS_TREE_RELOC_OBJECTID),
1005 * use full backrefs for extent pointers in tree block.
1006 * The reason for this is some operations (such as drop tree)
1007 * are only allowed for blocks use full backrefs.
1008 */
1009
1010 if (btrfs_block_can_be_shared(root, buf)) {
1011 ret = btrfs_lookup_extent_info(trans, root, buf->start,
3173a18f
JB		 1012 btrfs_header_level(buf), 1,
1013 &refs, &flags);
be1a5564
MF		 1014 if (ret)
1015 return ret;
e5df9573
MF		 1016 if (refs == 0) {
1017 ret = -EROFS;
1018 btrfs_std_error(root->fs_info, ret);
1019 return ret;
1020 }
5d4f98a2
YZ		 1021 } else {
1022 refs = 1;
1023 if (root->root_key.objectid == BTRFS_TREE_RELOC_OBJECTID ||
1024 btrfs_header_backref_rev(buf) < BTRFS_MIXED_BACKREF_REV)
1025 flags = BTRFS_BLOCK_FLAG_FULL_BACKREF;
1026 else
1027 flags = 0;
1028 }
1029
1030 owner = btrfs_header_owner(buf);
1031 BUG_ON(owner == BTRFS_TREE_RELOC_OBJECTID &&
1032 !(flags & BTRFS_BLOCK_FLAG_FULL_BACKREF));
1033
1034 if (refs > 1) {
1035 if ((owner == root->root_key.objectid ||
1036 root->root_key.objectid == BTRFS_TREE_RELOC_OBJECTID) &&
1037 !(flags & BTRFS_BLOCK_FLAG_FULL_BACKREF)) {
66d7e7f0 1038 ret = btrfs_inc_ref(trans, root, buf, 1, 1);
79787eaa 1039 BUG_ON(ret); /* -ENOMEM */
5d4f98a2
YZ		 1040
1041 if (root->root_key.objectid ==
1042 BTRFS_TREE_RELOC_OBJECTID) {
66d7e7f0 1043 ret = btrfs_dec_ref(trans, root, buf, 0, 1);
79787eaa 1044 BUG_ON(ret); /* -ENOMEM */
66d7e7f0 1045 ret = btrfs_inc_ref(trans, root, cow, 1, 1);
79787eaa 1046 BUG_ON(ret); /* -ENOMEM */
5d4f98a2
YZ		 1047 }
1048 new_flags |= BTRFS_BLOCK_FLAG_FULL_BACKREF;
1049 } else {
1050
1051 if (root->root_key.objectid ==
1052 BTRFS_TREE_RELOC_OBJECTID)
66d7e7f0 1053 ret = btrfs_inc_ref(trans, root, cow, 1, 1);
5d4f98a2 1054 else
66d7e7f0 1055 ret = btrfs_inc_ref(trans, root, cow, 0, 1);
79787eaa 1056 BUG_ON(ret); /* -ENOMEM */
5d4f98a2
YZ		 1057 }
1058 if (new_flags != 0) {
b1c79e09
JB		 1059 int level = btrfs_header_level(buf);
1060
5d4f98a2
YZ		 1061 ret = btrfs_set_disk_extent_flags(trans, root,
1062 buf->start,
1063 buf->len,
b1c79e09 1064 new_flags, level, 0);
be1a5564
MF		 1065 if (ret)
1066 return ret;
5d4f98a2
YZ		 1067 }
1068 } else {
1069 if (flags & BTRFS_BLOCK_FLAG_FULL_BACKREF) {
1070 if (root->root_key.objectid ==
1071 BTRFS_TREE_RELOC_OBJECTID)
66d7e7f0 1072 ret = btrfs_inc_ref(trans, root, cow, 1, 1);
5d4f98a2 1073 else
66d7e7f0 1074 ret = btrfs_inc_ref(trans, root, cow, 0, 1);
79787eaa 1075 BUG_ON(ret); /* -ENOMEM */
66d7e7f0 1076 ret = btrfs_dec_ref(trans, root, buf, 1, 1);
79787eaa 1077 BUG_ON(ret); /* -ENOMEM */
5d4f98a2
YZ		 1078 }
1079 clean_tree_block(trans, root, buf);
f0486c68 1080 *last_ref = 1;
5d4f98a2
YZ		 1081 }
1082 return 0;
1083}
1084
d352ac68 1085/*
d397712b
CM		 1086 * does the dirty work in cow of a single block. The parent block (if
1087 * supplied) is updated to point to the new cow copy. The new buffer is marked
1088 * dirty and returned locked. If you modify the block it needs to be marked
1089 * dirty again.
d352ac68
CM		 1090 *
1091 * search_start -- an allocation hint for the new block
1092 *
d397712b
CM		 1093 * empty_size -- a hint that you plan on doing more cow. This is the size in
1094 * bytes the allocator should try to find free next to the block it returns.
1095 * This is just a hint and may be ignored by the allocator.
d352ac68 1096 */
d397712b 1097static noinline int __btrfs_cow_block(struct btrfs_trans_handle *trans,
5f39d397
CM		 1098 struct btrfs_root *root,
1099 struct extent_buffer *buf,
1100 struct extent_buffer *parent, int parent_slot,
1101 struct extent_buffer **cow_ret,
9fa8cfe7 1102 u64 search_start, u64 empty_size)
02217ed2 1103{
5d4f98a2 1104 struct btrfs_disk_key disk_key;
5f39d397 1105 struct extent_buffer *cow;
be1a5564 1106 int level, ret;
f0486c68 1107 int last_ref = 0;
925baedd 1108 int unlock_orig = 0;
5d4f98a2 1109 u64 parent_start;
7bb86316 1110
925baedd
CM		 1111 if (*cow_ret == buf)
1112 unlock_orig = 1;
1113
b9447ef8 1114 btrfs_assert_tree_locked(buf);
925baedd 1115
27cdeb70
MX		 1116 WARN_ON(test_bit(BTRFS_ROOT_REF_COWS, &root->state) &&
1117 trans->transid != root->fs_info->running_transaction->transid);
1118 WARN_ON(test_bit(BTRFS_ROOT_REF_COWS, &root->state) &&
1119 trans->transid != root->last_trans);
5f39d397 1120
7bb86316 1121 level = btrfs_header_level(buf);
31840ae1 1122
5d4f98a2
YZ		 1123 if (level == 0)
1124 btrfs_item_key(buf, &disk_key, 0);
1125 else
1126 btrfs_node_key(buf, &disk_key, 0);
1127
1128 if (root->root_key.objectid == BTRFS_TREE_RELOC_OBJECTID) {
1129 if (parent)
1130 parent_start = parent->start;
1131 else
1132 parent_start = 0;
1133 } else
1134 parent_start = 0;
1135
1136 cow = btrfs_alloc_free_block(trans, root, buf->len, parent_start,
1137 root->root_key.objectid, &disk_key,
5581a51a 1138 level, search_start, empty_size);
54aa1f4d
CM		 1139 if (IS_ERR(cow))
1140 return PTR_ERR(cow);
6702ed49 1141
b4ce94de
CM		 1142 /* cow is set to blocking by btrfs_init_new_buffer */
1143
5f39d397 1144 copy_extent_buffer(cow, buf, 0, 0, cow->len);
db94535d 1145 btrfs_set_header_bytenr(cow, cow->start);
5f39d397 1146 btrfs_set_header_generation(cow, trans->transid);
5d4f98a2
YZ		 1147 btrfs_set_header_backref_rev(cow, BTRFS_MIXED_BACKREF_REV);
1148 btrfs_clear_header_flag(cow, BTRFS_HEADER_FLAG_WRITTEN |
1149 BTRFS_HEADER_FLAG_RELOC);
1150 if (root->root_key.objectid == BTRFS_TREE_RELOC_OBJECTID)
1151 btrfs_set_header_flag(cow, BTRFS_HEADER_FLAG_RELOC);
1152 else
1153 btrfs_set_header_owner(cow, root->root_key.objectid);
6702ed49 1154
0a4e5586 1155 write_extent_buffer(cow, root->fs_info->fsid, btrfs_header_fsid(),
2b82032c
YZ		 1156 BTRFS_FSID_SIZE);
1157
be1a5564 1158 ret = update_ref_for_cow(trans, root, buf, cow, &last_ref);
b68dc2a9 1159 if (ret) {
79787eaa 1160 btrfs_abort_transaction(trans, root, ret);
b68dc2a9
MF		 1161 return ret;
1162 }
1a40e23b 1163
27cdeb70 1164 if (test_bit(BTRFS_ROOT_REF_COWS, &root->state)) {
83d4cfd4
JB		 1165 ret = btrfs_reloc_cow_block(trans, root, buf, cow);
1166 if (ret)
1167 return ret;
1168 }
3fd0a558 1169
02217ed2 1170 if (buf == root->node) {
925baedd 1171 WARN_ON(parent && parent != buf);
5d4f98a2
YZ		 1172 if (root->root_key.objectid == BTRFS_TREE_RELOC_OBJECTID ||
1173 btrfs_header_backref_rev(buf) < BTRFS_MIXED_BACKREF_REV)
1174 parent_start = buf->start;
1175 else
1176 parent_start = 0;
925baedd 1177
5f39d397 1178 extent_buffer_get(cow);
90f8d62e 1179 tree_mod_log_set_root_pointer(root, cow, 1);
240f62c8 1180 rcu_assign_pointer(root->node, cow);
925baedd 1181
f0486c68 1182 btrfs_free_tree_block(trans, root, buf, parent_start,
5581a51a 1183 last_ref);
5f39d397 1184 free_extent_buffer(buf);
0b86a832 1185 add_root_to_dirty_list(root);
02217ed2 1186 } else {
5d4f98a2
YZ		 1187 if (root->root_key.objectid == BTRFS_TREE_RELOC_OBJECTID)
1188 parent_start = parent->start;
1189 else
1190 parent_start = 0;
1191
1192 WARN_ON(trans->transid != btrfs_header_generation(parent));
f230475e 1193 tree_mod_log_insert_key(root->fs_info, parent, parent_slot,
c8cc6341 1194 MOD_LOG_KEY_REPLACE, GFP_NOFS);
5f39d397 1195 btrfs_set_node_blockptr(parent, parent_slot,
db94535d 1196 cow->start);
74493f7a
CM		 1197 btrfs_set_node_ptr_generation(parent, parent_slot,
1198 trans->transid);
d6025579 1199 btrfs_mark_buffer_dirty(parent);
5de865ee
FDBM		 1200 if (last_ref) {
1201 ret = tree_mod_log_free_eb(root->fs_info, buf);
1202 if (ret) {
1203 btrfs_abort_transaction(trans, root, ret);
1204 return ret;
1205 }
1206 }
f0486c68 1207 btrfs_free_tree_block(trans, root, buf, parent_start,
5581a51a 1208 last_ref);
02217ed2 1209 }
925baedd
CM		 1210 if (unlock_orig)
1211 btrfs_tree_unlock(buf);
3083ee2e 1212 free_extent_buffer_stale(buf);
ccd467d6 1213 btrfs_mark_buffer_dirty(cow);
2c90e5d6 1214 *cow_ret = cow;
02217ed2
CM		 1215 return 0;
1216}
1217
5d9e75c4
JS		 1218/*
1219 * returns the logical address of the oldest predecessor of the given root.
1220 * entries older than time_seq are ignored.
1221 */
1222static struct tree_mod_elem *
1223__tree_mod_log_oldest_root(struct btrfs_fs_info *fs_info,
30b0463a 1224 struct extent_buffer *eb_root, u64 time_seq)
5d9e75c4
JS		 1225{
1226 struct tree_mod_elem *tm;
1227 struct tree_mod_elem *found = NULL;
30b0463a 1228 u64 root_logical = eb_root->start;
5d9e75c4
JS		 1229 int looped = 0;
1230
1231 if (!time_seq)
35a3621b 1232 return NULL;
5d9e75c4
JS		 1233
1234 /*
1235 * the very last operation that's logged for a root is the replacement
1236 * operation (if it is replaced at all). this has the index of the *new*
1237 * root, making it the very first operation that's logged for this root.
1238 */
1239 while (1) {
1240 tm = tree_mod_log_search_oldest(fs_info, root_logical,
1241 time_seq);
1242 if (!looped && !tm)
35a3621b 1243 return NULL;
5d9e75c4 1244 /*
28da9fb4
JS		 1245 * if there are no tree operation for the oldest root, we simply
1246 * return it. this should only happen if that (old) root is at
1247 * level 0.
5d9e75c4 1248 */
28da9fb4
JS		 1249 if (!tm)
1250 break;
5d9e75c4 1251
28da9fb4
JS		 1252 /*
1253 * if there's an operation that's not a root replacement, we
1254 * found the oldest version of our root. normally, we'll find a
1255 * MOD_LOG_KEY_REMOVE_WHILE_FREEING operation here.
1256 */
5d9e75c4
JS		 1257 if (tm->op != MOD_LOG_ROOT_REPLACE)
1258 break;
1259
1260 found = tm;
1261 root_logical = tm->old_root.logical;
5d9e75c4
JS		 1262 looped = 1;
1263 }
1264
a95236d9
JS		 1265 /* if there's no old root to return, return what we found instead */
1266 if (!found)
1267 found = tm;
1268
5d9e75c4
JS		 1269 return found;
1270}
1271
1272/*
1273 * tm is a pointer to the first operation to rewind within eb. then, all
1274 * previous operations will be rewinded (until we reach something older than
1275 * time_seq).
1276 */
1277static void
f1ca7e98
JB		 1278__tree_mod_log_rewind(struct btrfs_fs_info *fs_info, struct extent_buffer *eb,
1279 u64 time_seq, struct tree_mod_elem *first_tm)
5d9e75c4
JS		 1280{
1281 u32 n;
1282 struct rb_node *next;
1283 struct tree_mod_elem *tm = first_tm;
1284 unsigned long o_dst;
1285 unsigned long o_src;
1286 unsigned long p_size = sizeof(struct btrfs_key_ptr);
1287
1288 n = btrfs_header_nritems(eb);
f1ca7e98 1289 tree_mod_log_read_lock(fs_info);
097b8a7c 1290 while (tm && tm->seq >= time_seq) {
5d9e75c4
JS		 1291 /*
1292 * all the operations are recorded with the operator used for
1293 * the modification. as we're going backwards, we do the
1294 * opposite of each operation here.
1295 */
1296 switch (tm->op) {
1297 case MOD_LOG_KEY_REMOVE_WHILE_FREEING:
1298 BUG_ON(tm->slot < n);
1c697d4a 1299 /* Fallthrough */
95c80bb1 1300 case MOD_LOG_KEY_REMOVE_WHILE_MOVING:
4c3e6969 1301 case MOD_LOG_KEY_REMOVE:
5d9e75c4
JS		 1302 btrfs_set_node_key(eb, &tm->key, tm->slot);
1303 btrfs_set_node_blockptr(eb, tm->slot, tm->blockptr);
1304 btrfs_set_node_ptr_generation(eb, tm->slot,
1305 tm->generation);
4c3e6969 1306 n++;
5d9e75c4
JS		 1307 break;
1308 case MOD_LOG_KEY_REPLACE:
1309 BUG_ON(tm->slot >= n);
1310 btrfs_set_node_key(eb, &tm->key, tm->slot);
1311 btrfs_set_node_blockptr(eb, tm->slot, tm->blockptr);
1312 btrfs_set_node_ptr_generation(eb, tm->slot,
1313 tm->generation);
1314 break;
1315 case MOD_LOG_KEY_ADD:
19956c7e 1316 /* if a move operation is needed it's in the log */
5d9e75c4
JS		 1317 n--;
1318 break;
1319 case MOD_LOG_MOVE_KEYS:
c3193108
JS		 1320 o_dst = btrfs_node_key_ptr_offset(tm->slot);
1321 o_src = btrfs_node_key_ptr_offset(tm->move.dst_slot);
1322 memmove_extent_buffer(eb, o_dst, o_src,
5d9e75c4
JS		 1323 tm->move.nr_items * p_size);
1324 break;
1325 case MOD_LOG_ROOT_REPLACE:
1326 /*
1327 * this operation is special. for roots, this must be
1328 * handled explicitly before rewinding.
1329 * for non-roots, this operation may exist if the node
1330 * was a root: root A -> child B; then A gets empty and
1331 * B is promoted to the new root. in the mod log, we'll
1332 * have a root-replace operation for B, a tree block
1333 * that is no root. we simply ignore that operation.
1334 */
1335 break;
1336 }
1337 next = rb_next(&tm->node);
1338 if (!next)
1339 break;
1340 tm = container_of(next, struct tree_mod_elem, node);
1341 if (tm->index != first_tm->index)
1342 break;
1343 }
f1ca7e98 1344 tree_mod_log_read_unlock(fs_info);
5d9e75c4
JS		 1345 btrfs_set_header_nritems(eb, n);
1346}
1347
47fb091f
JS		 1348/*
1349 * Called with eb read locked. If the buffer cannot be rewinded, the same buffer
1350 * is returned. If rewind operations happen, a fresh buffer is returned. The
1351 * returned buffer is always read-locked. If the returned buffer is not the
1352 * input buffer, the lock on the input buffer is released and the input buffer
1353 * is freed (its refcount is decremented).
1354 */
5d9e75c4 1355static struct extent_buffer *
9ec72677
JB		 1356tree_mod_log_rewind(struct btrfs_fs_info *fs_info, struct btrfs_path *path,
1357 struct extent_buffer *eb, u64 time_seq)
5d9e75c4
JS		 1358{
1359 struct extent_buffer *eb_rewin;
1360 struct tree_mod_elem *tm;
1361
1362 if (!time_seq)
1363 return eb;
1364
1365 if (btrfs_header_level(eb) == 0)
1366 return eb;
1367
1368 tm = tree_mod_log_search(fs_info, eb->start, time_seq);
1369 if (!tm)
1370 return eb;
1371
9ec72677
JB		 1372 btrfs_set_path_blocking(path);
1373 btrfs_set_lock_blocking_rw(eb, BTRFS_READ_LOCK);
1374
5d9e75c4
JS		 1375 if (tm->op == MOD_LOG_KEY_REMOVE_WHILE_FREEING) {
1376 BUG_ON(tm->slot != 0);
1377 eb_rewin = alloc_dummy_extent_buffer(eb->start,
1378 fs_info->tree_root->nodesize);
db7f3436 1379 if (!eb_rewin) {
9ec72677 1380 btrfs_tree_read_unlock_blocking(eb);
db7f3436
JB		 1381 free_extent_buffer(eb);
1382 return NULL;
1383 }
5d9e75c4
JS		 1384 btrfs_set_header_bytenr(eb_rewin, eb->start);
1385 btrfs_set_header_backref_rev(eb_rewin,
1386 btrfs_header_backref_rev(eb));
1387 btrfs_set_header_owner(eb_rewin, btrfs_header_owner(eb));
c3193108 1388 btrfs_set_header_level(eb_rewin, btrfs_header_level(eb));
5d9e75c4
JS		 1389 } else {
1390 eb_rewin = btrfs_clone_extent_buffer(eb);
db7f3436 1391 if (!eb_rewin) {
9ec72677 1392 btrfs_tree_read_unlock_blocking(eb);
db7f3436
JB		 1393 free_extent_buffer(eb);
1394 return NULL;
1395 }
5d9e75c4
JS		 1396 }
1397
9ec72677
JB		 1398 btrfs_clear_path_blocking(path, NULL, BTRFS_READ_LOCK);
1399 btrfs_tree_read_unlock_blocking(eb);
5d9e75c4
JS		 1400 free_extent_buffer(eb);
1401
47fb091f
JS		 1402 extent_buffer_get(eb_rewin);
1403 btrfs_tree_read_lock(eb_rewin);
f1ca7e98 1404 __tree_mod_log_rewind(fs_info, eb_rewin, time_seq, tm);
57911b8b 1405 WARN_ON(btrfs_header_nritems(eb_rewin) >
2a745b14 1406 BTRFS_NODEPTRS_PER_BLOCK(fs_info->tree_root));
5d9e75c4
JS		 1407
1408 return eb_rewin;
1409}
1410
8ba97a15
JS		 1411/*
1412 * get_old_root() rewinds the state of @root's root node to the given @time_seq
1413 * value. If there are no changes, the current root->root_node is returned. If
1414 * anything changed in between, there's a fresh buffer allocated on which the
1415 * rewind operations are done. In any case, the returned buffer is read locked.
1416 * Returns NULL on error (with no locks held).
1417 */
5d9e75c4
JS		 1418static inline struct extent_buffer *
1419get_old_root(struct btrfs_root *root, u64 time_seq)
1420{
1421 struct tree_mod_elem *tm;
30b0463a
JS		 1422 struct extent_buffer *eb = NULL;
1423 struct extent_buffer *eb_root;
7bfdcf7f 1424 struct extent_buffer *old;
a95236d9 1425 struct tree_mod_root *old_root = NULL;
4325edd0 1426 u64 old_generation = 0;
a95236d9 1427 u64 logical;
834328a8 1428 u32 blocksize;
5d9e75c4 1429
30b0463a
JS		 1430 eb_root = btrfs_read_lock_root_node(root);
1431 tm = __tree_mod_log_oldest_root(root->fs_info, eb_root, time_seq);
5d9e75c4 1432 if (!tm)
30b0463a 1433 return eb_root;
5d9e75c4 1434
a95236d9
JS		 1435 if (tm->op == MOD_LOG_ROOT_REPLACE) {
1436 old_root = &tm->old_root;
1437 old_generation = tm->generation;
1438 logical = old_root->logical;
1439 } else {
30b0463a 1440 logical = eb_root->start;
a95236d9 1441 }
5d9e75c4 1442
a95236d9 1443 tm = tree_mod_log_search(root->fs_info, logical, time_seq);
834328a8 1444 if (old_root && tm && tm->op != MOD_LOG_KEY_REMOVE_WHILE_FREEING) {
30b0463a
JS		 1445 btrfs_tree_read_unlock(eb_root);
1446 free_extent_buffer(eb_root);
834328a8 1447 blocksize = btrfs_level_size(root, old_root->level);
7bfdcf7f 1448 old = read_tree_block(root, logical, blocksize, 0);
fae7f21c 1449 if (WARN_ON(!old || !extent_buffer_uptodate(old))) {
416bc658 1450 free_extent_buffer(old);
efe120a0
FH		 1451 btrfs_warn(root->fs_info,
1452 "failed to read tree block %llu from get_old_root", logical);
834328a8 1453 } else {
7bfdcf7f
LB		 1454 eb = btrfs_clone_extent_buffer(old);
1455 free_extent_buffer(old);
834328a8
JS		 1456 }
1457 } else if (old_root) {
30b0463a
JS		 1458 btrfs_tree_read_unlock(eb_root);
1459 free_extent_buffer(eb_root);
28da9fb4 1460 eb = alloc_dummy_extent_buffer(logical, root->nodesize);
834328a8 1461 } else {
9ec72677 1462 btrfs_set_lock_blocking_rw(eb_root, BTRFS_READ_LOCK);
30b0463a 1463 eb = btrfs_clone_extent_buffer(eb_root);
9ec72677 1464 btrfs_tree_read_unlock_blocking(eb_root);
30b0463a 1465 free_extent_buffer(eb_root);
834328a8
JS		 1466 }
1467
8ba97a15
JS		 1468 if (!eb)
1469 return NULL;
d6381084 1470 extent_buffer_get(eb);
8ba97a15 1471 btrfs_tree_read_lock(eb);
a95236d9 1472 if (old_root) {
5d9e75c4
JS		 1473 btrfs_set_header_bytenr(eb, eb->start);
1474 btrfs_set_header_backref_rev(eb, BTRFS_MIXED_BACKREF_REV);
30b0463a 1475 btrfs_set_header_owner(eb, btrfs_header_owner(eb_root));
a95236d9
JS		 1476 btrfs_set_header_level(eb, old_root->level);
1477 btrfs_set_header_generation(eb, old_generation);
5d9e75c4 1478 }
28da9fb4 1479 if (tm)
f1ca7e98 1480 __tree_mod_log_rewind(root->fs_info, eb, time_seq, tm);
28da9fb4
JS		 1481 else
1482 WARN_ON(btrfs_header_level(eb) != 0);
57911b8b 1483 WARN_ON(btrfs_header_nritems(eb) > BTRFS_NODEPTRS_PER_BLOCK(root));
5d9e75c4
JS		 1484
1485 return eb;
1486}
1487
5b6602e7
JS		 1488int btrfs_old_root_level(struct btrfs_root *root, u64 time_seq)
1489{
1490 struct tree_mod_elem *tm;
1491 int level;
30b0463a 1492 struct extent_buffer *eb_root = btrfs_root_node(root);
5b6602e7 1493
30b0463a 1494 tm = __tree_mod_log_oldest_root(root->fs_info, eb_root, time_seq);
5b6602e7
JS		 1495 if (tm && tm->op == MOD_LOG_ROOT_REPLACE) {
1496 level = tm->old_root.level;
1497 } else {
30b0463a 1498 level = btrfs_header_level(eb_root);
5b6602e7 1499 }
30b0463a 1500 free_extent_buffer(eb_root);
5b6602e7
JS		 1501
1502 return level;
1503}
1504
5d4f98a2
YZ		 1505static inline int should_cow_block(struct btrfs_trans_handle *trans,
1506 struct btrfs_root *root,
1507 struct extent_buffer *buf)
1508{
f1ebcc74
LB		 1509 /* ensure we can see the force_cow */
1510 smp_rmb();
1511
1512 /*
1513 * We do not need to cow a block if
1514 * 1) this block is not created or changed in this transaction;
1515 * 2) this block does not belong to TREE_RELOC tree;
1516 * 3) the root is not forced COW.
1517 *
1518 * What is forced COW:
1519 * when we create snapshot during commiting the transaction,
1520 * after we've finished coping src root, we must COW the shared
1521 * block to ensure the metadata consistency.
1522 */
5d4f98a2
YZ		 1523 if (btrfs_header_generation(buf) == trans->transid &&
1524 !btrfs_header_flag(buf, BTRFS_HEADER_FLAG_WRITTEN) &&
1525 !(root->root_key.objectid != BTRFS_TREE_RELOC_OBJECTID &&
f1ebcc74 1526 btrfs_header_flag(buf, BTRFS_HEADER_FLAG_RELOC)) &&
27cdeb70 1527 !test_bit(BTRFS_ROOT_FORCE_COW, &root->state))
5d4f98a2
YZ		 1528 return 0;
1529 return 1;
1530}
1531
d352ac68
CM		 1532/*
1533 * cows a single block, see __btrfs_cow_block for the real work.
1534 * This version of it has extra checks so that a block isn't cow'd more than
1535 * once per transaction, as long as it hasn't been written yet
1536 */
d397712b 1537noinline int btrfs_cow_block(struct btrfs_trans_handle *trans,
5f39d397
CM		 1538 struct btrfs_root *root, struct extent_buffer *buf,
1539 struct extent_buffer *parent, int parent_slot,
9fa8cfe7 1540 struct extent_buffer **cow_ret)
6702ed49
CM		 1541{
1542 u64 search_start;
f510cfec 1543 int ret;
dc17ff8f 1544
31b1a2bd
JL		 1545 if (trans->transaction != root->fs_info->running_transaction)
1546 WARN(1, KERN_CRIT "trans %llu running %llu\n",
c1c9ff7c 1547 trans->transid,
6702ed49 1548 root->fs_info->running_transaction->transid);
31b1a2bd
JL		 1549
1550 if (trans->transid != root->fs_info->generation)
1551 WARN(1, KERN_CRIT "trans %llu running %llu\n",
c1c9ff7c 1552 trans->transid, root->fs_info->generation);
dc17ff8f 1553
5d4f98a2 1554 if (!should_cow_block(trans, root, buf)) {
6702ed49
CM		 1555 *cow_ret = buf;
1556 return 0;
1557 }
c487685d 1558
0b86a832 1559 search_start = buf->start & ~((u64)(1024 * 1024 * 1024) - 1);
b4ce94de
CM		 1560
1561 if (parent)
1562 btrfs_set_lock_blocking(parent);
1563 btrfs_set_lock_blocking(buf);
1564
f510cfec 1565 ret = __btrfs_cow_block(trans, root, buf, parent,
9fa8cfe7 1566 parent_slot, cow_ret, search_start, 0);
1abe9b8a 1567
1568 trace_btrfs_cow_block(root, buf, *cow_ret);
1569
f510cfec 1570 return ret;
6702ed49
CM		 1571}
1572
d352ac68
CM		 1573/*
1574 * helper function for defrag to decide if two blocks pointed to by a
1575 * node are actually close by
1576 */
6b80053d 1577static int close_blocks(u64 blocknr, u64 other, u32 blocksize)
6702ed49 1578{
6b80053d 1579 if (blocknr < other && other - (blocknr + blocksize) < 32768)
6702ed49 1580 return 1;
6b80053d 1581 if (blocknr > other && blocknr - (other + blocksize) < 32768)
6702ed49
CM		 1582 return 1;
1583 return 0;
1584}
1585
081e9573
CM		 1586/*
1587 * compare two keys in a memcmp fashion
1588 */
1589static int comp_keys(struct btrfs_disk_key *disk, struct btrfs_key *k2)
1590{
1591 struct btrfs_key k1;
1592
1593 btrfs_disk_key_to_cpu(&k1, disk);
1594
20736aba 1595 return btrfs_comp_cpu_keys(&k1, k2);
081e9573
CM		 1596}
1597
f3465ca4
JB		 1598/*
1599 * same as comp_keys only with two btrfs_key's
1600 */
5d4f98a2 1601int btrfs_comp_cpu_keys(struct btrfs_key *k1, struct btrfs_key *k2)
f3465ca4
JB		 1602{
1603 if (k1->objectid > k2->objectid)
1604 return 1;
1605 if (k1->objectid < k2->objectid)
1606 return -1;
1607 if (k1->type > k2->type)
1608 return 1;
1609 if (k1->type < k2->type)
1610 return -1;
1611 if (k1->offset > k2->offset)
1612 return 1;
1613 if (k1->offset < k2->offset)
1614 return -1;
1615 return 0;
1616}
081e9573 1617
d352ac68
CM		 1618/*
1619 * this is used by the defrag code to go through all the
1620 * leaves pointed to by a node and reallocate them so that
1621 * disk order is close to key order
1622 */
6702ed49 1623int btrfs_realloc_node(struct btrfs_trans_handle *trans,
5f39d397 1624 struct btrfs_root *root, struct extent_buffer *parent,
de78b51a 1625 int start_slot, u64 *last_ret,
a6b6e75e 1626 struct btrfs_key *progress)
6702ed49 1627{
6b80053d 1628 struct extent_buffer *cur;
6702ed49 1629 u64 blocknr;
ca7a79ad 1630 u64 gen;
e9d0b13b
CM		 1631 u64 search_start = *last_ret;
1632 u64 last_block = 0;
6702ed49
CM		 1633 u64 other;
1634 u32 parent_nritems;
6702ed49
CM		 1635 int end_slot;
1636 int i;
1637 int err = 0;
f2183bde 1638 int parent_level;
6b80053d
CM		 1639 int uptodate;
1640 u32 blocksize;
081e9573
CM		 1641 int progress_passed = 0;
1642 struct btrfs_disk_key disk_key;
6702ed49 1643
5708b959 1644 parent_level = btrfs_header_level(parent);
5708b959 1645
6c1500f2
JL		 1646 WARN_ON(trans->transaction != root->fs_info->running_transaction);
1647 WARN_ON(trans->transid != root->fs_info->generation);
86479a04 1648
6b80053d 1649 parent_nritems = btrfs_header_nritems(parent);
6b80053d 1650 blocksize = btrfs_level_size(root, parent_level - 1);
6702ed49
CM		 1651 end_slot = parent_nritems;
1652
1653 if (parent_nritems == 1)
1654 return 0;
1655
b4ce94de
CM		 1656 btrfs_set_lock_blocking(parent);
1657
6702ed49
CM		 1658 for (i = start_slot; i < end_slot; i++) {
1659 int close = 1;
a6b6e75e 1660
081e9573
CM		 1661 btrfs_node_key(parent, &disk_key, i);
1662 if (!progress_passed && comp_keys(&disk_key, progress) < 0)
1663 continue;
1664
1665 progress_passed = 1;
6b80053d 1666 blocknr = btrfs_node_blockptr(parent, i);
ca7a79ad 1667 gen = btrfs_node_ptr_generation(parent, i);
e9d0b13b
CM		 1668 if (last_block == 0)
1669 last_block = blocknr;
5708b959 1670
6702ed49 1671 if (i > 0) {
6b80053d
CM		 1672 other = btrfs_node_blockptr(parent, i - 1);
1673 close = close_blocks(blocknr, other, blocksize);
6702ed49 1674 }
0ef3e66b 1675 if (!close && i < end_slot - 2) {
6b80053d
CM		 1676 other = btrfs_node_blockptr(parent, i + 1);
1677 close = close_blocks(blocknr, other, blocksize);
6702ed49 1678 }
e9d0b13b
CM		 1679 if (close) {
1680 last_block = blocknr;
6702ed49 1681 continue;
e9d0b13b 1682 }
6702ed49 1683
6b80053d
CM		 1684 cur = btrfs_find_tree_block(root, blocknr, blocksize);
1685 if (cur)
b9fab919 1686 uptodate = btrfs_buffer_uptodate(cur, gen, 0);
6b80053d
CM		 1687 else
1688 uptodate = 0;
5708b959 1689 if (!cur || !uptodate) {
6b80053d
CM		 1690 if (!cur) {
1691 cur = read_tree_block(root, blocknr,
ca7a79ad 1692 blocksize, gen);
416bc658
JB		 1693 if (!cur || !extent_buffer_uptodate(cur)) {
1694 free_extent_buffer(cur);
97d9a8a4 1695 return -EIO;
416bc658 1696 }
6b80053d 1697 } else if (!uptodate) {
018642a1
TI		 1698 err = btrfs_read_buffer(cur, gen);
1699 if (err) {
1700 free_extent_buffer(cur);
1701 return err;
1702 }
f2183bde 1703 }
6702ed49 1704 }
e9d0b13b 1705 if (search_start == 0)
6b80053d 1706 search_start = last_block;
e9d0b13b 1707
e7a84565 1708 btrfs_tree_lock(cur);
b4ce94de 1709 btrfs_set_lock_blocking(cur);
6b80053d 1710 err = __btrfs_cow_block(trans, root, cur, parent, i,
e7a84565 1711 &cur, search_start,
6b80053d 1712 min(16 * blocksize,
9fa8cfe7 1713 (end_slot - i) * blocksize));
252c38f0 1714 if (err) {
e7a84565 1715 btrfs_tree_unlock(cur);
6b80053d 1716 free_extent_buffer(cur);
6702ed49 1717 break;
252c38f0 1718 }
e7a84565
CM		 1719 search_start = cur->start;
1720 last_block = cur->start;
f2183bde 1721 *last_ret = search_start;
e7a84565
CM		 1722 btrfs_tree_unlock(cur);
1723 free_extent_buffer(cur);
6702ed49
CM		 1724 }
1725 return err;
1726}
1727
74123bd7
CM		 1728/*
1729 * The leaf data grows from end-to-front in the node.
1730 * this returns the address of the start of the last item,
1731 * which is the stop of the leaf data stack
1732 */
123abc88 1733static inline unsigned int leaf_data_end(struct btrfs_root *root,
5f39d397 1734 struct extent_buffer *leaf)
be0e5c09 1735{
5f39d397 1736 u32 nr = btrfs_header_nritems(leaf);
be0e5c09 1737 if (nr == 0)
123abc88 1738 return BTRFS_LEAF_DATA_SIZE(root);
5f39d397 1739 return btrfs_item_offset_nr(leaf, nr - 1);
be0e5c09
CM		 1740}
1741
aa5d6bed 1742
74123bd7 1743/*
5f39d397
CM		 1744 * search for key in the extent_buffer. The items start at offset p,
1745 * and they are item_size apart. There are 'max' items in p.
1746 *
74123bd7
CM		 1747 * the slot in the array is returned via slot, and it points to
1748 * the place where you would insert key if it is not found in
1749 * the array.
1750 *
1751 * slot may point to max if the key is bigger than all of the keys
1752 */
e02119d5
CM		 1753static noinline int generic_bin_search(struct extent_buffer *eb,
1754 unsigned long p,
1755 int item_size, struct btrfs_key *key,
1756 int max, int *slot)
be0e5c09
CM		 1757{
1758 int low = 0;
1759 int high = max;
1760 int mid;
1761 int ret;
479965d6 1762 struct btrfs_disk_key *tmp = NULL;
5f39d397
CM		 1763 struct btrfs_disk_key unaligned;
1764 unsigned long offset;
5f39d397
CM		 1765 char *kaddr = NULL;
1766 unsigned long map_start = 0;
1767 unsigned long map_len = 0;
479965d6 1768 int err;
be0e5c09 1769
d397712b 1770 while (low < high) {
be0e5c09 1771 mid = (low + high) / 2;
5f39d397
CM		 1772 offset = p + mid * item_size;
1773
a6591715 1774 if (!kaddr || offset < map_start ||
5f39d397
CM		 1775 (offset + sizeof(struct btrfs_disk_key)) >
1776 map_start + map_len) {
934d375b
CM		 1777
1778 err = map_private_extent_buffer(eb, offset,
479965d6 1779 sizeof(struct btrfs_disk_key),
a6591715 1780 &kaddr, &map_start, &map_len);
479965d6
CM		 1781
1782 if (!err) {
1783 tmp = (struct btrfs_disk_key *)(kaddr + offset -
1784 map_start);
1785 } else {
1786 read_extent_buffer(eb, &unaligned,
1787 offset, sizeof(unaligned));
1788 tmp = &unaligned;
1789 }
5f39d397 1790
5f39d397
CM		 1791 } else {
1792 tmp = (struct btrfs_disk_key *)(kaddr + offset -
1793 map_start);
1794 }
be0e5c09
CM		 1795 ret = comp_keys(tmp, key);
1796
1797 if (ret < 0)
1798 low = mid + 1;
1799 else if (ret > 0)
1800 high = mid;
1801 else {
1802 *slot = mid;
1803 return 0;
1804 }
1805 }
1806 *slot = low;
1807 return 1;
1808}
1809
97571fd0
CM		 1810/*
1811 * simple bin_search frontend that does the right thing for
1812 * leaves vs nodes
1813 */
5f39d397
CM		 1814static int bin_search(struct extent_buffer *eb, struct btrfs_key *key,
1815 int level, int *slot)
be0e5c09 1816{
f775738f 1817 if (level == 0)
5f39d397
CM		 1818 return generic_bin_search(eb,
1819 offsetof(struct btrfs_leaf, items),
0783fcfc 1820 sizeof(struct btrfs_item),
5f39d397 1821 key, btrfs_header_nritems(eb),
7518a238 1822 slot);
f775738f 1823 else
5f39d397
CM		 1824 return generic_bin_search(eb,
1825 offsetof(struct btrfs_node, ptrs),
123abc88 1826 sizeof(struct btrfs_key_ptr),
5f39d397 1827 key, btrfs_header_nritems(eb),
7518a238 1828 slot);
be0e5c09
CM		 1829}
1830
5d4f98a2
YZ		 1831int btrfs_bin_search(struct extent_buffer *eb, struct btrfs_key *key,
1832 int level, int *slot)
1833{
1834 return bin_search(eb, key, level, slot);
1835}
1836
f0486c68
YZ		 1837static void root_add_used(struct btrfs_root *root, u32 size)
1838{
1839 spin_lock(&root->accounting_lock);
1840 btrfs_set_root_used(&root->root_item,
1841 btrfs_root_used(&root->root_item) + size);
1842 spin_unlock(&root->accounting_lock);
1843}
1844
1845static void root_sub_used(struct btrfs_root *root, u32 size)
1846{
1847 spin_lock(&root->accounting_lock);
1848 btrfs_set_root_used(&root->root_item,
1849 btrfs_root_used(&root->root_item) - size);
1850 spin_unlock(&root->accounting_lock);
1851}
1852
d352ac68
CM		 1853/* given a node and slot number, this reads the blocks it points to. The
1854 * extent buffer is returned with a reference taken (but unlocked).
1855 * NULL is returned on error.
1856 */
e02119d5 1857static noinline struct extent_buffer *read_node_slot(struct btrfs_root *root,
5f39d397 1858 struct extent_buffer *parent, int slot)
bb803951 1859{
ca7a79ad 1860 int level = btrfs_header_level(parent);
416bc658
JB		 1861 struct extent_buffer *eb;
1862
bb803951
CM		 1863 if (slot < 0)
1864 return NULL;
5f39d397 1865 if (slot >= btrfs_header_nritems(parent))
bb803951 1866 return NULL;
ca7a79ad
CM		 1867
1868 BUG_ON(level == 0);
1869
416bc658
JB		 1870 eb = read_tree_block(root, btrfs_node_blockptr(parent, slot),
1871 btrfs_level_size(root, level - 1),
1872 btrfs_node_ptr_generation(parent, slot));
1873 if (eb && !extent_buffer_uptodate(eb)) {
1874 free_extent_buffer(eb);
1875 eb = NULL;
1876 }
1877
1878 return eb;
bb803951
CM		 1879}
1880
d352ac68
CM		 1881/*
1882 * node level balancing, used to make sure nodes are in proper order for
1883 * item deletion. We balance from the top down, so we have to make sure
1884 * that a deletion won't leave an node completely empty later on.
1885 */
e02119d5 1886static noinline int balance_level(struct btrfs_trans_handle *trans,
98ed5174
CM		 1887 struct btrfs_root *root,
1888 struct btrfs_path *path, int level)
bb803951 1889{
5f39d397
CM		 1890 struct extent_buffer *right = NULL;
1891 struct extent_buffer *mid;
1892 struct extent_buffer *left = NULL;
1893 struct extent_buffer *parent = NULL;
bb803951
CM		 1894 int ret = 0;
1895 int wret;
1896 int pslot;
bb803951 1897 int orig_slot = path->slots[level];
79f95c82 1898 u64 orig_ptr;
bb803951
CM		 1899
1900 if (level == 0)
1901 return 0;
1902
5f39d397 1903 mid = path->nodes[level];
b4ce94de 1904
bd681513
CM		 1905 WARN_ON(path->locks[level] != BTRFS_WRITE_LOCK &&
1906 path->locks[level] != BTRFS_WRITE_LOCK_BLOCKING);
7bb86316
CM		 1907 WARN_ON(btrfs_header_generation(mid) != trans->transid);
1908
1d4f8a0c 1909 orig_ptr = btrfs_node_blockptr(mid, orig_slot);
79f95c82 1910
a05a9bb1 1911 if (level < BTRFS_MAX_LEVEL - 1) {
5f39d397 1912 parent = path->nodes[level + 1];
a05a9bb1
LZ		 1913 pslot = path->slots[level + 1];
1914 }
bb803951 1915
40689478
CM		 1916 /*
1917 * deal with the case where there is only one pointer in the root
1918 * by promoting the node below to a root
1919 */
5f39d397
CM		 1920 if (!parent) {
1921 struct extent_buffer *child;
bb803951 1922
5f39d397 1923 if (btrfs_header_nritems(mid) != 1)
bb803951
CM		 1924 return 0;
1925
1926 /* promote the child to a root */
5f39d397 1927 child = read_node_slot(root, mid, 0);
305a26af
MF		 1928 if (!child) {
1929 ret = -EROFS;
1930 btrfs_std_error(root->fs_info, ret);
1931 goto enospc;
1932 }
1933
925baedd 1934 btrfs_tree_lock(child);
b4ce94de 1935 btrfs_set_lock_blocking(child);
9fa8cfe7 1936 ret = btrfs_cow_block(trans, root, child, mid, 0, &child);
f0486c68
YZ		 1937 if (ret) {
1938 btrfs_tree_unlock(child);
1939 free_extent_buffer(child);
1940 goto enospc;
1941 }
2f375ab9 1942
90f8d62e 1943 tree_mod_log_set_root_pointer(root, child, 1);
240f62c8 1944 rcu_assign_pointer(root->node, child);
925baedd 1945
0b86a832 1946 add_root_to_dirty_list(root);
925baedd 1947 btrfs_tree_unlock(child);
b4ce94de 1948
925baedd 1949 path->locks[level] = 0;
bb803951 1950 path->nodes[level] = NULL;
5f39d397 1951 clean_tree_block(trans, root, mid);
925baedd 1952 btrfs_tree_unlock(mid);
bb803951 1953 /* once for the path */
5f39d397 1954 free_extent_buffer(mid);
f0486c68
YZ		 1955
1956 root_sub_used(root, mid->len);
5581a51a 1957 btrfs_free_tree_block(trans, root, mid, 0, 1);
bb803951 1958 /* once for the root ptr */
3083ee2e 1959 free_extent_buffer_stale(mid);
f0486c68 1960 return 0;
bb803951 1961 }
5f39d397 1962 if (btrfs_header_nritems(mid) >
123abc88 1963 BTRFS_NODEPTRS_PER_BLOCK(root) / 4)
bb803951
CM		 1964 return 0;
1965
5f39d397
CM		 1966 left = read_node_slot(root, parent, pslot - 1);
1967 if (left) {
925baedd 1968 btrfs_tree_lock(left);
b4ce94de 1969 btrfs_set_lock_blocking(left);
5f39d397 1970 wret = btrfs_cow_block(trans, root, left,
9fa8cfe7 1971 parent, pslot - 1, &left);
54aa1f4d
CM		 1972 if (wret) {
1973 ret = wret;
1974 goto enospc;
1975 }
2cc58cf2 1976 }
5f39d397
CM		 1977 right = read_node_slot(root, parent, pslot + 1);
1978 if (right) {
925baedd 1979 btrfs_tree_lock(right);
b4ce94de 1980 btrfs_set_lock_blocking(right);
5f39d397 1981 wret = btrfs_cow_block(trans, root, right,
9fa8cfe7 1982 parent, pslot + 1, &right);
2cc58cf2
CM		 1983 if (wret) {
1984 ret = wret;
1985 goto enospc;
1986 }
1987 }
1988
1989 /* first, try to make some room in the middle buffer */
5f39d397
CM		 1990 if (left) {
1991 orig_slot += btrfs_header_nritems(left);
bce4eae9 1992 wret = push_node_left(trans, root, left, mid, 1);
79f95c82
CM		 1993 if (wret < 0)
1994 ret = wret;
bb803951 1995 }
79f95c82
CM		 1996
1997 /*
1998 * then try to empty the right most buffer into the middle
1999 */
5f39d397 2000 if (right) {
971a1f66 2001 wret = push_node_left(trans, root, mid, right, 1);
54aa1f4d 2002 if (wret < 0 && wret != -ENOSPC)
79f95c82 2003 ret = wret;
5f39d397 2004 if (btrfs_header_nritems(right) == 0) {
5f39d397 2005 clean_tree_block(trans, root, right);
925baedd 2006 btrfs_tree_unlock(right);
afe5fea7 2007 del_ptr(root, path, level + 1, pslot + 1);
f0486c68 2008 root_sub_used(root, right->len);
5581a51a 2009 btrfs_free_tree_block(trans, root, right, 0, 1);
3083ee2e 2010 free_extent_buffer_stale(right);
f0486c68 2011 right = NULL;
bb803951 2012 } else {
5f39d397
CM		 2013 struct btrfs_disk_key right_key;
2014 btrfs_node_key(right, &right_key, 0);
f230475e 2015 tree_mod_log_set_node_key(root->fs_info, parent,
32adf090 2016 pslot + 1, 0);
5f39d397
CM		 2017 btrfs_set_node_key(parent, &right_key, pslot + 1);
2018 btrfs_mark_buffer_dirty(parent);
bb803951
CM		 2019 }
2020 }
5f39d397 2021 if (btrfs_header_nritems(mid) == 1) {
79f95c82
CM		 2022 /*
2023 * we're not allowed to leave a node with one item in the
2024 * tree during a delete. A deletion from lower in the tree
2025 * could try to delete the only pointer in this node.
2026 * So, pull some keys from the left.
2027 * There has to be a left pointer at this point because
2028 * otherwise we would have pulled some pointers from the
2029 * right
2030 */
305a26af
MF		 2031 if (!left) {
2032 ret = -EROFS;
2033 btrfs_std_error(root->fs_info, ret);
2034 goto enospc;
2035 }
5f39d397 2036 wret = balance_node_right(trans, root, mid, left);
54aa1f4d 2037 if (wret < 0) {
79f95c82 2038 ret = wret;
54aa1f4d
CM		 2039 goto enospc;
2040 }
bce4eae9
CM		 2041 if (wret == 1) {
2042 wret = push_node_left(trans, root, left, mid, 1);
2043 if (wret < 0)
2044 ret = wret;
2045 }
79f95c82
CM		 2046 BUG_ON(wret == 1);
2047 }
5f39d397 2048 if (btrfs_header_nritems(mid) == 0) {
5f39d397 2049 clean_tree_block(trans, root, mid);
925baedd 2050 btrfs_tree_unlock(mid);
afe5fea7 2051 del_ptr(root, path, level + 1, pslot);
f0486c68 2052 root_sub_used(root, mid->len);
5581a51a 2053 btrfs_free_tree_block(trans, root, mid, 0, 1);
3083ee2e 2054 free_extent_buffer_stale(mid);
f0486c68 2055 mid = NULL;
79f95c82
CM		 2056 } else {
2057 /* update the parent key to reflect our changes */
5f39d397
CM		 2058 struct btrfs_disk_key mid_key;
2059 btrfs_node_key(mid, &mid_key, 0);
32adf090 2060 tree_mod_log_set_node_key(root->fs_info, parent,
f230475e 2061 pslot, 0);
5f39d397
CM		 2062 btrfs_set_node_key(parent, &mid_key, pslot);
2063 btrfs_mark_buffer_dirty(parent);
79f95c82 2064 }
bb803951 2065
79f95c82 2066 /* update the path */
5f39d397
CM		 2067 if (left) {
2068 if (btrfs_header_nritems(left) > orig_slot) {
2069 extent_buffer_get(left);
925baedd 2070 /* left was locked after cow */
5f39d397 2071 path->nodes[level] = left;
bb803951
CM		 2072 path->slots[level + 1] -= 1;
2073 path->slots[level] = orig_slot;
925baedd
CM		 2074 if (mid) {
2075 btrfs_tree_unlock(mid);
5f39d397 2076 free_extent_buffer(mid);
925baedd 2077 }
bb803951 2078 } else {
5f39d397 2079 orig_slot -= btrfs_header_nritems(left);
bb803951
CM		 2080 path->slots[level] = orig_slot;
2081 }
2082 }
79f95c82 2083 /* double check we haven't messed things up */
e20d96d6 2084 if (orig_ptr !=
5f39d397 2085 btrfs_node_blockptr(path->nodes[level], path->slots[level]))
79f95c82 2086 BUG();
54aa1f4d 2087enospc:
925baedd
CM		 2088 if (right) {
2089 btrfs_tree_unlock(right);
5f39d397 2090 free_extent_buffer(right);
925baedd
CM		 2091 }
2092 if (left) {
2093 if (path->nodes[level] != left)
2094 btrfs_tree_unlock(left);
5f39d397 2095 free_extent_buffer(left);
925baedd 2096 }
bb803951
CM		 2097 return ret;
2098}
2099
d352ac68
CM		 2100/* Node balancing for insertion. Here we only split or push nodes around
2101 * when they are completely full. This is also done top down, so we
2102 * have to be pessimistic.
2103 */
d397712b 2104static noinline int push_nodes_for_insert(struct btrfs_trans_handle *trans,
98ed5174
CM		 2105 struct btrfs_root *root,
2106 struct btrfs_path *path, int level)
e66f709b 2107{
5f39d397
CM		 2108 struct extent_buffer *right = NULL;
2109 struct extent_buffer *mid;
2110 struct extent_buffer *left = NULL;
2111 struct extent_buffer *parent = NULL;
e66f709b
CM		 2112 int ret = 0;
2113 int wret;
2114 int pslot;
2115 int orig_slot = path->slots[level];
e66f709b
CM		 2116
2117 if (level == 0)
2118 return 1;
2119
5f39d397 2120 mid = path->nodes[level];
7bb86316 2121 WARN_ON(btrfs_header_generation(mid) != trans->transid);
e66f709b 2122
a05a9bb1 2123 if (level < BTRFS_MAX_LEVEL - 1) {
5f39d397 2124 parent = path->nodes[level + 1];
a05a9bb1
LZ		 2125 pslot = path->slots[level + 1];
2126 }
e66f709b 2127
5f39d397 2128 if (!parent)
e66f709b 2129 return 1;
e66f709b 2130
5f39d397 2131 left = read_node_slot(root, parent, pslot - 1);
e66f709b
CM		 2132
2133 /* first, try to make some room in the middle buffer */
5f39d397 2134 if (left) {
e66f709b 2135 u32 left_nr;
925baedd
CM		 2136
2137 btrfs_tree_lock(left);
b4ce94de
CM		 2138 btrfs_set_lock_blocking(left);
2139
5f39d397 2140 left_nr = btrfs_header_nritems(left);
33ade1f8
CM		 2141 if (left_nr >= BTRFS_NODEPTRS_PER_BLOCK(root) - 1) {
2142 wret = 1;
2143 } else {
5f39d397 2144 ret = btrfs_cow_block(trans, root, left, parent,
9fa8cfe7 2145 pslot - 1, &left);
54aa1f4d
CM		 2146 if (ret)
2147 wret = 1;
2148 else {
54aa1f4d 2149 wret = push_node_left(trans, root,
971a1f66 2150 left, mid, 0);
54aa1f4d 2151 }
33ade1f8 2152 }
e66f709b
CM		 2153 if (wret < 0)
2154 ret = wret;
2155 if (wret == 0) {
5f39d397 2156 struct btrfs_disk_key disk_key;
e66f709b 2157 orig_slot += left_nr;
5f39d397 2158 btrfs_node_key(mid, &disk_key, 0);
f230475e 2159 tree_mod_log_set_node_key(root->fs_info, parent,
32adf090 2160 pslot, 0);
5f39d397
CM		 2161 btrfs_set_node_key(parent, &disk_key, pslot);
2162 btrfs_mark_buffer_dirty(parent);
2163 if (btrfs_header_nritems(left) > orig_slot) {
2164 path->nodes[level] = left;
e66f709b
CM		 2165 path->slots[level + 1] -= 1;
2166 path->slots[level] = orig_slot;
925baedd 2167 btrfs_tree_unlock(mid);
5f39d397 2168 free_extent_buffer(mid);
e66f709b
CM		 2169 } else {
2170 orig_slot -=
5f39d397 2171 btrfs_header_nritems(left);
e66f709b 2172 path->slots[level] = orig_slot;
925baedd 2173 btrfs_tree_unlock(left);
5f39d397 2174 free_extent_buffer(left);
e66f709b 2175 }
e66f709b
CM		 2176 return 0;
2177 }
925baedd 2178 btrfs_tree_unlock(left);
5f39d397 2179 free_extent_buffer(left);
e66f709b 2180 }
925baedd 2181 right = read_node_slot(root, parent, pslot + 1);
e66f709b
CM		 2182
2183 /*
2184 * then try to empty the right most buffer into the middle
2185 */
5f39d397 2186 if (right) {
33ade1f8 2187 u32 right_nr;
b4ce94de 2188
925baedd 2189 btrfs_tree_lock(right);
b4ce94de
CM		 2190 btrfs_set_lock_blocking(right);
2191
5f39d397 2192 right_nr = btrfs_header_nritems(right);
33ade1f8
CM		 2193 if (right_nr >= BTRFS_NODEPTRS_PER_BLOCK(root) - 1) {
2194 wret = 1;
2195 } else {
5f39d397
CM		 2196 ret = btrfs_cow_block(trans, root, right,
2197 parent, pslot + 1,
9fa8cfe7 2198 &right);
54aa1f4d
CM		 2199 if (ret)
2200 wret = 1;
2201 else {
54aa1f4d 2202 wret = balance_node_right(trans, root,
5f39d397 2203 right, mid);
54aa1f4d 2204 }
33ade1f8 2205 }
e66f709b
CM		 2206 if (wret < 0)
2207 ret = wret;
2208 if (wret == 0) {
5f39d397
CM		 2209 struct btrfs_disk_key disk_key;
2210
2211 btrfs_node_key(right, &disk_key, 0);
f230475e 2212 tree_mod_log_set_node_key(root->fs_info, parent,
32adf090 2213 pslot + 1, 0);
5f39d397
CM		 2214 btrfs_set_node_key(parent, &disk_key, pslot + 1);
2215 btrfs_mark_buffer_dirty(parent);
2216
2217 if (btrfs_header_nritems(mid) <= orig_slot) {
2218 path->nodes[level] = right;
e66f709b
CM		 2219 path->slots[level + 1] += 1;
2220 path->slots[level] = orig_slot -
5f39d397 2221 btrfs_header_nritems(mid);
925baedd 2222 btrfs_tree_unlock(mid);
5f39d397 2223 free_extent_buffer(mid);
e66f709b 2224 } else {
925baedd 2225 btrfs_tree_unlock(right);
5f39d397 2226 free_extent_buffer(right);
e66f709b 2227 }
e66f709b
CM		 2228 return 0;
2229 }
925baedd 2230 btrfs_tree_unlock(right);
5f39d397 2231 free_extent_buffer(right);
e66f709b 2232 }
e66f709b
CM		 2233 return 1;
2234}
2235
3c69faec 2236/*
d352ac68
CM		 2237 * readahead one full node of leaves, finding things that are close
2238 * to the block in 'slot', and triggering ra on them.
3c69faec 2239 */
c8c42864
CM		 2240static void reada_for_search(struct btrfs_root *root,
2241 struct btrfs_path *path,
2242 int level, int slot, u64 objectid)
3c69faec 2243{
5f39d397 2244 struct extent_buffer *node;
01f46658 2245 struct btrfs_disk_key disk_key;
3c69faec 2246 u32 nritems;
3c69faec 2247 u64 search;
a7175319 2248 u64 target;
6b80053d 2249 u64 nread = 0;
cb25c2ea 2250 u64 gen;
3c69faec 2251 int direction = path->reada;
5f39d397 2252 struct extent_buffer *eb;
6b80053d
CM		 2253 u32 nr;
2254 u32 blocksize;
2255 u32 nscan = 0;
db94535d 2256
a6b6e75e 2257 if (level != 1)
6702ed49
CM		 2258 return;
2259
2260 if (!path->nodes[level])
3c69faec
CM		 2261 return;
2262
5f39d397 2263 node = path->nodes[level];
925baedd 2264
3c69faec 2265 search = btrfs_node_blockptr(node, slot);
6b80053d
CM		 2266 blocksize = btrfs_level_size(root, level - 1);
2267 eb = btrfs_find_tree_block(root, search, blocksize);
5f39d397
CM		 2268 if (eb) {
2269 free_extent_buffer(eb);
3c69faec
CM		 2270 return;
2271 }
2272
a7175319 2273 target = search;
6b80053d 2274
5f39d397 2275 nritems = btrfs_header_nritems(node);
6b80053d 2276 nr = slot;
25b8b936 2277
d397712b 2278 while (1) {
6b80053d
CM		 2279 if (direction < 0) {
2280 if (nr == 0)
2281 break;
2282 nr--;
2283 } else if (direction > 0) {
2284 nr++;
2285 if (nr >= nritems)
2286 break;
3c69faec 2287 }
01f46658
CM		 2288 if (path->reada < 0 && objectid) {
2289 btrfs_node_key(node, &disk_key, nr);
2290 if (btrfs_disk_key_objectid(&disk_key) != objectid)
2291 break;
2292 }
6b80053d 2293 search = btrfs_node_blockptr(node, nr);
a7175319
CM		 2294 if ((search <= target && target - search <= 65536) ||
2295 (search > target && search - target <= 65536)) {
cb25c2ea 2296 gen = btrfs_node_ptr_generation(node, nr);
cb25c2ea 2297 readahead_tree_block(root, search, blocksize, gen);
6b80053d
CM		 2298 nread += blocksize;
2299 }
2300 nscan++;
a7175319 2301 if ((nread > 65536 || nscan > 32))
6b80053d 2302 break;
3c69faec
CM		 2303 }
2304}
925baedd 2305
0b08851f
JB		 2306static noinline void reada_for_balance(struct btrfs_root *root,
2307 struct btrfs_path *path, int level)
b4ce94de
CM		 2308{
2309 int slot;
2310 int nritems;
2311 struct extent_buffer *parent;
2312 struct extent_buffer *eb;
2313 u64 gen;
2314 u64 block1 = 0;
2315 u64 block2 = 0;
b4ce94de
CM		 2316 int blocksize;
2317
8c594ea8 2318 parent = path->nodes[level + 1];
b4ce94de 2319 if (!parent)
0b08851f 2320 return;
b4ce94de
CM		 2321
2322 nritems = btrfs_header_nritems(parent);
8c594ea8 2323 slot = path->slots[level + 1];
b4ce94de
CM		 2324 blocksize = btrfs_level_size(root, level);
2325
2326 if (slot > 0) {
2327 block1 = btrfs_node_blockptr(parent, slot - 1);
2328 gen = btrfs_node_ptr_generation(parent, slot - 1);
2329 eb = btrfs_find_tree_block(root, block1, blocksize);
b9fab919
CM		 2330 /*
2331 * if we get -eagain from btrfs_buffer_uptodate, we
2332 * don't want to return eagain here. That will loop
2333 * forever
2334 */
2335 if (eb && btrfs_buffer_uptodate(eb, gen, 1) != 0)
b4ce94de
CM		 2336 block1 = 0;
2337 free_extent_buffer(eb);
2338 }
8c594ea8 2339 if (slot + 1 < nritems) {
b4ce94de
CM		 2340 block2 = btrfs_node_blockptr(parent, slot + 1);
2341 gen = btrfs_node_ptr_generation(parent, slot + 1);
2342 eb = btrfs_find_tree_block(root, block2, blocksize);
b9fab919 2343 if (eb && btrfs_buffer_uptodate(eb, gen, 1) != 0)
b4ce94de
CM		 2344 block2 = 0;
2345 free_extent_buffer(eb);
2346 }
8c594ea8 2347
0b08851f
JB		 2348 if (block1)
2349 readahead_tree_block(root, block1, blocksize, 0);
2350 if (block2)
2351 readahead_tree_block(root, block2, blocksize, 0);
b4ce94de
CM		 2352}
2353
2354
d352ac68 2355/*
d397712b
CM		 2356 * when we walk down the tree, it is usually safe to unlock the higher layers
2357 * in the tree. The exceptions are when our path goes through slot 0, because
2358 * operations on the tree might require changing key pointers higher up in the
2359 * tree.
d352ac68 2360 *
d397712b
CM		 2361 * callers might also have set path->keep_locks, which tells this code to keep
2362 * the lock if the path points to the last slot in the block. This is part of
2363 * walking through the tree, and selecting the next slot in the higher block.
d352ac68 2364 *
d397712b
CM		 2365 * lowest_unlock sets the lowest level in the tree we're allowed to unlock. so
2366 * if lowest_unlock is 1, level 0 won't be unlocked
d352ac68 2367 */
e02119d5 2368static noinline void unlock_up(struct btrfs_path *path, int level,
f7c79f30
CM		 2369 int lowest_unlock, int min_write_lock_level,
2370 int *write_lock_level)
925baedd
CM		 2371{
2372 int i;
2373 int skip_level = level;
051e1b9f 2374 int no_skips = 0;
925baedd
CM		 2375 struct extent_buffer *t;
2376
2377 for (i = level; i < BTRFS_MAX_LEVEL; i++) {
2378 if (!path->nodes[i])
2379 break;
2380 if (!path->locks[i])
2381 break;
051e1b9f 2382 if (!no_skips && path->slots[i] == 0) {
925baedd
CM		 2383 skip_level = i + 1;
2384 continue;
2385 }
051e1b9f 2386 if (!no_skips && path->keep_locks) {
925baedd
CM		 2387 u32 nritems;
2388 t = path->nodes[i];
2389 nritems = btrfs_header_nritems(t);
051e1b9f 2390 if (nritems < 1 || path->slots[i] >= nritems - 1) {
925baedd
CM		 2391 skip_level = i + 1;
2392 continue;
2393 }
2394 }
051e1b9f
CM		 2395 if (skip_level < i && i >= lowest_unlock)
2396 no_skips = 1;
2397
925baedd
CM		 2398 t = path->nodes[i];
2399 if (i >= lowest_unlock && i > skip_level && path->locks[i]) {
bd681513 2400 btrfs_tree_unlock_rw(t, path->locks[i]);
925baedd 2401 path->locks[i] = 0;
f7c79f30
CM		 2402 if (write_lock_level &&
2403 i > min_write_lock_level &&
2404 i <= *write_lock_level) {
2405 *write_lock_level = i - 1;
2406 }
925baedd
CM		 2407 }
2408 }
2409}
2410
b4ce94de
CM		 2411/*
2412 * This releases any locks held in the path starting at level and
2413 * going all the way up to the root.
2414 *
2415 * btrfs_search_slot will keep the lock held on higher nodes in a few
2416 * corner cases, such as COW of the block at slot zero in the node. This
2417 * ignores those rules, and it should only be called when there are no
2418 * more updates to be done higher up in the tree.
2419 */
2420noinline void btrfs_unlock_up_safe(struct btrfs_path *path, int level)
2421{
2422 int i;
2423
09a2a8f9 2424 if (path->keep_locks)
b4ce94de
CM		 2425 return;
2426
2427 for (i = level; i < BTRFS_MAX_LEVEL; i++) {
2428 if (!path->nodes[i])
12f4dacc 2429 continue;
b4ce94de 2430 if (!path->locks[i])
12f4dacc 2431 continue;
bd681513 2432 btrfs_tree_unlock_rw(path->nodes[i], path->locks[i]);
b4ce94de
CM		 2433 path->locks[i] = 0;
2434 }
2435}
2436
c8c42864
CM		 2437/*
2438 * helper function for btrfs_search_slot. The goal is to find a block
2439 * in cache without setting the path to blocking. If we find the block
2440 * we return zero and the path is unchanged.
2441 *
2442 * If we can't find the block, we set the path blocking and do some
2443 * reada. -EAGAIN is returned and the search must be repeated.
2444 */
2445static int
2446read_block_for_search(struct btrfs_trans_handle *trans,
2447 struct btrfs_root *root, struct btrfs_path *p,
2448 struct extent_buffer **eb_ret, int level, int slot,
5d9e75c4 2449 struct btrfs_key *key, u64 time_seq)
c8c42864
CM		 2450{
2451 u64 blocknr;
2452 u64 gen;
2453 u32 blocksize;
2454 struct extent_buffer *b = *eb_ret;
2455 struct extent_buffer *tmp;
76a05b35 2456 int ret;
c8c42864
CM		 2457
2458 blocknr = btrfs_node_blockptr(b, slot);
2459 gen = btrfs_node_ptr_generation(b, slot);
2460 blocksize = btrfs_level_size(root, level - 1);
2461
2462 tmp = btrfs_find_tree_block(root, blocknr, blocksize);
cb44921a 2463 if (tmp) {
b9fab919 2464 /* first we do an atomic uptodate check */
bdf7c00e
JB		 2465 if (btrfs_buffer_uptodate(tmp, gen, 1) > 0) {
2466 *eb_ret = tmp;
2467 return 0;
2468 }
2469
2470 /* the pages were up to date, but we failed
2471 * the generation number check. Do a full
2472 * read for the generation number that is correct.
2473 * We must do this without dropping locks so
2474 * we can trust our generation number
2475 */
2476 btrfs_set_path_blocking(p);
2477
2478 /* now we're allowed to do a blocking uptodate check */
2479 ret = btrfs_read_buffer(tmp, gen);
2480 if (!ret) {
2481 *eb_ret = tmp;
2482 return 0;
cb44921a 2483 }
bdf7c00e
JB		 2484 free_extent_buffer(tmp);
2485 btrfs_release_path(p);
2486 return -EIO;
c8c42864
CM		 2487 }
2488
2489 /*
2490 * reduce lock contention at high levels
2491 * of the btree by dropping locks before
76a05b35
CM		 2492 * we read. Don't release the lock on the current
2493 * level because we need to walk this node to figure
2494 * out which blocks to read.
c8c42864 2495 */
8c594ea8
CM		 2496 btrfs_unlock_up_safe(p, level + 1);
2497 btrfs_set_path_blocking(p);
2498
cb44921a 2499 free_extent_buffer(tmp);
c8c42864
CM		 2500 if (p->reada)
2501 reada_for_search(root, p, level, slot, key->objectid);
2502
b3b4aa74 2503 btrfs_release_path(p);
76a05b35
CM		 2504
2505 ret = -EAGAIN;
5bdd3536 2506 tmp = read_tree_block(root, blocknr, blocksize, 0);
76a05b35
CM		 2507 if (tmp) {
2508 /*
2509 * If the read above didn't mark this buffer up to date,
2510 * it will never end up being up to date. Set ret to EIO now
2511 * and give up so that our caller doesn't loop forever
2512 * on our EAGAINs.
2513 */
b9fab919 2514 if (!btrfs_buffer_uptodate(tmp, 0, 0))
76a05b35 2515 ret = -EIO;
c8c42864 2516 free_extent_buffer(tmp);
76a05b35
CM		 2517 }
2518 return ret;
c8c42864
CM		 2519}
2520
2521/*
2522 * helper function for btrfs_search_slot. This does all of the checks
2523 * for node-level blocks and does any balancing required based on
2524 * the ins_len.
2525 *
2526 * If no extra work was required, zero is returned. If we had to
2527 * drop the path, -EAGAIN is returned and btrfs_search_slot must
2528 * start over
2529 */
2530static int
2531setup_nodes_for_search(struct btrfs_trans_handle *trans,
2532 struct btrfs_root *root, struct btrfs_path *p,
bd681513
CM		 2533 struct extent_buffer *b, int level, int ins_len,
2534 int *write_lock_level)
c8c42864
CM		 2535{
2536 int ret;
2537 if ((p->search_for_split || ins_len > 0) && btrfs_header_nritems(b) >=
2538 BTRFS_NODEPTRS_PER_BLOCK(root) - 3) {
2539 int sret;
2540
bd681513
CM		 2541 if (*write_lock_level < level + 1) {
2542 *write_lock_level = level + 1;
2543 btrfs_release_path(p);
2544 goto again;
2545 }
2546
c8c42864 2547 btrfs_set_path_blocking(p);
0b08851f 2548 reada_for_balance(root, p, level);
c8c42864 2549 sret = split_node(trans, root, p, level);
bd681513 2550 btrfs_clear_path_blocking(p, NULL, 0);
c8c42864
CM		 2551
2552 BUG_ON(sret > 0);
2553 if (sret) {
2554 ret = sret;
2555 goto done;
2556 }
2557 b = p->nodes[level];
2558 } else if (ins_len < 0 && btrfs_header_nritems(b) <
cfbb9308 2559 BTRFS_NODEPTRS_PER_BLOCK(root) / 2) {
c8c42864
CM		 2560 int sret;
2561
bd681513
CM		 2562 if (*write_lock_level < level + 1) {
2563 *write_lock_level = level + 1;
2564 btrfs_release_path(p);
2565 goto again;
2566 }
2567
c8c42864 2568 btrfs_set_path_blocking(p);
0b08851f 2569 reada_for_balance(root, p, level);
c8c42864 2570 sret = balance_level(trans, root, p, level);
bd681513 2571 btrfs_clear_path_blocking(p, NULL, 0);
c8c42864
CM		 2572
2573 if (sret) {
2574 ret = sret;
2575 goto done;
2576 }
2577 b = p->nodes[level];
2578 if (!b) {
b3b4aa74 2579 btrfs_release_path(p);
c8c42864
CM		 2580 goto again;
2581 }
2582 BUG_ON(btrfs_header_nritems(b) == 1);
2583 }
2584 return 0;
2585
2586again:
2587 ret = -EAGAIN;
2588done:
2589 return ret;
2590}
2591
d7396f07
FDBM		 2592static void key_search_validate(struct extent_buffer *b,
2593 struct btrfs_key *key,
2594 int level)
2595{
2596#ifdef CONFIG_BTRFS_ASSERT
2597 struct btrfs_disk_key disk_key;
2598
2599 btrfs_cpu_key_to_disk(&disk_key, key);
2600
2601 if (level == 0)
2602 ASSERT(!memcmp_extent_buffer(b, &disk_key,
2603 offsetof(struct btrfs_leaf, items[0].key),
2604 sizeof(disk_key)));
2605 else
2606 ASSERT(!memcmp_extent_buffer(b, &disk_key,
2607 offsetof(struct btrfs_node, ptrs[0].key),
2608 sizeof(disk_key)));
2609#endif
2610}
2611
2612static int key_search(struct extent_buffer *b, struct btrfs_key *key,
2613 int level, int *prev_cmp, int *slot)
2614{
2615 if (*prev_cmp != 0) {
2616 *prev_cmp = bin_search(b, key, level, slot);
2617 return *prev_cmp;
2618 }
2619
2620 key_search_validate(b, key, level);
2621 *slot = 0;
2622
2623 return 0;
2624}
2625
3f870c28 2626int btrfs_find_item(struct btrfs_root *fs_root, struct btrfs_path *found_path,
e33d5c3d
KN		 2627 u64 iobjectid, u64 ioff, u8 key_type,
2628 struct btrfs_key *found_key)
2629{
2630 int ret;
2631 struct btrfs_key key;
2632 struct extent_buffer *eb;
3f870c28 2633 struct btrfs_path *path;
e33d5c3d
KN		 2634
2635 key.type = key_type;
2636 key.objectid = iobjectid;
2637 key.offset = ioff;
2638
3f870c28
KN		 2639 if (found_path == NULL) {
2640 path = btrfs_alloc_path();
2641 if (!path)
2642 return -ENOMEM;
2643 } else
2644 path = found_path;
2645
e33d5c3d 2646 ret = btrfs_search_slot(NULL, fs_root, &key, path, 0, 0);
3f870c28
KN		 2647 if ((ret < 0) || (found_key == NULL)) {
2648 if (path != found_path)
2649 btrfs_free_path(path);
e33d5c3d 2650 return ret;
3f870c28 2651 }
e33d5c3d
KN		 2652
2653 eb = path->nodes[0];
2654 if (ret && path->slots[0] >= btrfs_header_nritems(eb)) {
2655 ret = btrfs_next_leaf(fs_root, path);
2656 if (ret)
2657 return ret;
2658 eb = path->nodes[0];
2659 }
2660
2661 btrfs_item_key_to_cpu(eb, found_key, path->slots[0]);
2662 if (found_key->type != key.type ||
2663 found_key->objectid != key.objectid)
2664 return 1;
2665
2666 return 0;
2667}
2668
74123bd7
CM		 2669/*
2670 * look for key in the tree. path is filled in with nodes along the way
2671 * if key is found, we return zero and you can find the item in the leaf
2672 * level of the path (level 0)
2673 *
2674 * If the key isn't found, the path points to the slot where it should
aa5d6bed
CM		 2675 * be inserted, and 1 is returned. If there are other errors during the
2676 * search a negative error number is returned.
97571fd0
CM		 2677 *
2678 * if ins_len > 0, nodes and leaves will be split as we walk down the
2679 * tree. if ins_len < 0, nodes will be merged as we walk down the tree (if
2680 * possible)
74123bd7 2681 */
e089f05c
CM		 2682int btrfs_search_slot(struct btrfs_trans_handle *trans, struct btrfs_root
2683 *root, struct btrfs_key *key, struct btrfs_path *p, int
2684 ins_len, int cow)
be0e5c09 2685{
5f39d397 2686 struct extent_buffer *b;
be0e5c09
CM		 2687 int slot;
2688 int ret;
33c66f43 2689 int err;
be0e5c09 2690 int level;
925baedd 2691 int lowest_unlock = 1;
bd681513
CM		 2692 int root_lock;
2693 /* everything at write_lock_level or lower must be write locked */
2694 int write_lock_level = 0;
9f3a7427 2695 u8 lowest_level = 0;
f7c79f30 2696 int min_write_lock_level;
d7396f07 2697 int prev_cmp;
9f3a7427 2698
6702ed49 2699 lowest_level = p->lowest_level;
323ac95b 2700 WARN_ON(lowest_level && ins_len > 0);
22b0ebda 2701 WARN_ON(p->nodes[0] != NULL);
eb653de1 2702 BUG_ON(!cow && ins_len);
25179201 2703
bd681513 2704 if (ins_len < 0) {
925baedd 2705 lowest_unlock = 2;
65b51a00 2706
bd681513
CM		 2707 /* when we are removing items, we might have to go up to level
2708 * two as we update tree pointers Make sure we keep write
2709 * for those levels as well
2710 */
2711 write_lock_level = 2;
2712 } else if (ins_len > 0) {
2713 /*
2714 * for inserting items, make sure we have a write lock on
2715 * level 1 so we can update keys
2716 */
2717 write_lock_level = 1;
2718 }
2719
2720 if (!cow)
2721 write_lock_level = -1;
2722
09a2a8f9 2723 if (cow && (p->keep_locks || p->lowest_level))
bd681513
CM		 2724 write_lock_level = BTRFS_MAX_LEVEL;
2725
f7c79f30
CM		 2726 min_write_lock_level = write_lock_level;
2727
bb803951 2728again:
d7396f07 2729 prev_cmp = -1;
bd681513
CM		 2730 /*
2731 * we try very hard to do read locks on the root
2732 */
2733 root_lock = BTRFS_READ_LOCK;
2734 level = 0;
5d4f98a2 2735 if (p->search_commit_root) {
bd681513
CM		 2736 /*
2737 * the commit roots are read only
2738 * so we always do read locks
2739 */
3f8a18cc
JB		 2740 if (p->need_commit_sem)
2741 down_read(&root->fs_info->commit_root_sem);
5d4f98a2
YZ		 2742 b = root->commit_root;
2743 extent_buffer_get(b);
bd681513 2744 level = btrfs_header_level(b);
3f8a18cc
JB		 2745 if (p->need_commit_sem)
2746 up_read(&root->fs_info->commit_root_sem);
5d4f98a2 2747 if (!p->skip_locking)
bd681513 2748 btrfs_tree_read_lock(b);
5d4f98a2 2749 } else {
bd681513 2750 if (p->skip_locking) {
5d4f98a2 2751 b = btrfs_root_node(root);
bd681513
CM		 2752 level = btrfs_header_level(b);
2753 } else {
2754 /* we don't know the level of the root node
2755 * until we actually have it read locked
2756 */
2757 b = btrfs_read_lock_root_node(root);
2758 level = btrfs_header_level(b);
2759 if (level <= write_lock_level) {
2760 /* whoops, must trade for write lock */
2761 btrfs_tree_read_unlock(b);
2762 free_extent_buffer(b);
2763 b = btrfs_lock_root_node(root);
2764 root_lock = BTRFS_WRITE_LOCK;
2765
2766 /* the level might have changed, check again */
2767 level = btrfs_header_level(b);
2768 }
2769 }
5d4f98a2 2770 }
bd681513
CM		 2771 p->nodes[level] = b;
2772 if (!p->skip_locking)
2773 p->locks[level] = root_lock;
925baedd 2774
eb60ceac 2775 while (b) {
5f39d397 2776 level = btrfs_header_level(b);
65b51a00
CM		 2777
2778 /*
2779 * setup the path here so we can release it under lock
2780 * contention with the cow code
2781 */
02217ed2 2782 if (cow) {
c8c42864
CM		 2783 /*
2784 * if we don't really need to cow this block
2785 * then we don't want to set the path blocking,
2786 * so we test it here
2787 */
5d4f98a2 2788 if (!should_cow_block(trans, root, b))
65b51a00 2789 goto cow_done;
5d4f98a2 2790
b4ce94de
CM		 2791 btrfs_set_path_blocking(p);
2792
bd681513
CM		 2793 /*
2794 * must have write locks on this node and the
2795 * parent
2796 */
5124e00e
JB		 2797 if (level > write_lock_level ||
2798 (level + 1 > write_lock_level &&
2799 level + 1 < BTRFS_MAX_LEVEL &&
2800 p->nodes[level + 1])) {
bd681513
CM		 2801 write_lock_level = level + 1;
2802 btrfs_release_path(p);
2803 goto again;
2804 }
2805
33c66f43
YZ		 2806 err = btrfs_cow_block(trans, root, b,
2807 p->nodes[level + 1],
2808 p->slots[level + 1], &b);
2809 if (err) {
33c66f43 2810 ret = err;
65b51a00 2811 goto done;
54aa1f4d 2812 }
02217ed2 2813 }
65b51a00 2814cow_done:
eb60ceac 2815 p->nodes[level] = b;
bd681513 2816 btrfs_clear_path_blocking(p, NULL, 0);
b4ce94de
CM		 2817
2818 /*
2819 * we have a lock on b and as long as we aren't changing
2820 * the tree, there is no way to for the items in b to change.
2821 * It is safe to drop the lock on our parent before we
2822 * go through the expensive btree search on b.
2823 *
eb653de1
FDBM		 2824 * If we're inserting or deleting (ins_len != 0), then we might
2825 * be changing slot zero, which may require changing the parent.
2826 * So, we can't drop the lock until after we know which slot
2827 * we're operating on.
b4ce94de 2828 */
eb653de1
FDBM		 2829 if (!ins_len && !p->keep_locks) {
2830 int u = level + 1;
2831
2832 if (u < BTRFS_MAX_LEVEL && p->locks[u]) {
2833 btrfs_tree_unlock_rw(p->nodes[u], p->locks[u]);
2834 p->locks[u] = 0;
2835 }
2836 }
b4ce94de 2837
d7396f07 2838 ret = key_search(b, key, level, &prev_cmp, &slot);
b4ce94de 2839
5f39d397 2840 if (level != 0) {
33c66f43
YZ		 2841 int dec = 0;
2842 if (ret && slot > 0) {
2843 dec = 1;
be0e5c09 2844 slot -= 1;
33c66f43 2845 }
be0e5c09 2846 p->slots[level] = slot;
33c66f43 2847 err = setup_nodes_for_search(trans, root, p, b, level,
bd681513 2848 ins_len, &write_lock_level);
33c66f43 2849 if (err == -EAGAIN)
c8c42864 2850 goto again;
33c66f43
YZ		 2851 if (err) {
2852 ret = err;
c8c42864 2853 goto done;
33c66f43 2854 }
c8c42864
CM		 2855 b = p->nodes[level];
2856 slot = p->slots[level];
b4ce94de 2857
bd681513
CM		 2858 /*
2859 * slot 0 is special, if we change the key
2860 * we have to update the parent pointer
2861 * which means we must have a write lock
2862 * on the parent
2863 */
eb653de1 2864 if (slot == 0 && ins_len &&
bd681513
CM		 2865 write_lock_level < level + 1) {
2866 write_lock_level = level + 1;
2867 btrfs_release_path(p);
2868 goto again;
2869 }
2870
f7c79f30
CM		 2871 unlock_up(p, level, lowest_unlock,
2872 min_write_lock_level, &write_lock_level);
f9efa9c7 2873
925baedd 2874 if (level == lowest_level) {
33c66f43
YZ		 2875 if (dec)
2876 p->slots[level]++;
5b21f2ed 2877 goto done;
925baedd 2878 }
ca7a79ad 2879
33c66f43 2880 err = read_block_for_search(trans, root, p,
5d9e75c4 2881 &b, level, slot, key, 0);
33c66f43 2882 if (err == -EAGAIN)
c8c42864 2883 goto again;
33c66f43
YZ		 2884 if (err) {
2885 ret = err;
76a05b35 2886 goto done;
33c66f43 2887 }
76a05b35 2888
b4ce94de 2889 if (!p->skip_locking) {
bd681513
CM		 2890 level = btrfs_header_level(b);
2891 if (level <= write_lock_level) {
2892 err = btrfs_try_tree_write_lock(b);
2893 if (!err) {
2894 btrfs_set_path_blocking(p);
2895 btrfs_tree_lock(b);
2896 btrfs_clear_path_blocking(p, b,
2897 BTRFS_WRITE_LOCK);
2898 }
2899 p->locks[level] = BTRFS_WRITE_LOCK;
2900 } else {
2901 err = btrfs_try_tree_read_lock(b);
2902 if (!err) {
2903 btrfs_set_path_blocking(p);
2904 btrfs_tree_read_lock(b);
2905 btrfs_clear_path_blocking(p, b,
2906 BTRFS_READ_LOCK);
2907 }
2908 p->locks[level] = BTRFS_READ_LOCK;
b4ce94de 2909 }
bd681513 2910 p->nodes[level] = b;
b4ce94de 2911 }
be0e5c09
CM		 2912 } else {
2913 p->slots[level] = slot;
87b29b20
YZ		 2914 if (ins_len > 0 &&
2915 btrfs_leaf_free_space(root, b) < ins_len) {
bd681513
CM		 2916 if (write_lock_level < 1) {
2917 write_lock_level = 1;
2918 btrfs_release_path(p);
2919 goto again;
2920 }
2921
b4ce94de 2922 btrfs_set_path_blocking(p);
33c66f43
YZ		 2923 err = split_leaf(trans, root, key,
2924 p, ins_len, ret == 0);
bd681513 2925 btrfs_clear_path_blocking(p, NULL, 0);
b4ce94de 2926
33c66f43
YZ		 2927 BUG_ON(err > 0);
2928 if (err) {
2929 ret = err;
65b51a00
CM		 2930 goto done;
2931 }
5c680ed6 2932 }
459931ec 2933 if (!p->search_for_split)
f7c79f30
CM		 2934 unlock_up(p, level, lowest_unlock,
2935 min_write_lock_level, &write_lock_level);
65b51a00 2936 goto done;
be0e5c09
CM		 2937 }
2938 }
65b51a00
CM		 2939 ret = 1;
2940done:
b4ce94de
CM		 2941 /*
2942 * we don't really know what they plan on doing with the path
2943 * from here on, so for now just mark it as blocking
2944 */
b9473439
CM		 2945 if (!p->leave_spinning)
2946 btrfs_set_path_blocking(p);
76a05b35 2947 if (ret < 0)
b3b4aa74 2948 btrfs_release_path(p);
65b51a00 2949 return ret;
be0e5c09
CM		 2950}
2951
5d9e75c4
JS		 2952/*
2953 * Like btrfs_search_slot, this looks for a key in the given tree. It uses the
2954 * current state of the tree together with the operations recorded in the tree
2955 * modification log to search for the key in a previous version of this tree, as
2956 * denoted by the time_seq parameter.
2957 *
2958 * Naturally, there is no support for insert, delete or cow operations.
2959 *
2960 * The resulting path and return value will be set up as if we called
2961 * btrfs_search_slot at that point in time with ins_len and cow both set to 0.
2962 */
2963int btrfs_search_old_slot(struct btrfs_root *root, struct btrfs_key *key,
2964 struct btrfs_path *p, u64 time_seq)
2965{
2966 struct extent_buffer *b;
2967 int slot;
2968 int ret;
2969 int err;
2970 int level;
2971 int lowest_unlock = 1;
2972 u8 lowest_level = 0;
d4b4087c 2973 int prev_cmp = -1;
5d9e75c4
JS		 2974
2975 lowest_level = p->lowest_level;
2976 WARN_ON(p->nodes[0] != NULL);
2977
2978 if (p->search_commit_root) {
2979 BUG_ON(time_seq);
2980 return btrfs_search_slot(NULL, root, key, p, 0, 0);
2981 }
2982
2983again:
5d9e75c4 2984 b = get_old_root(root, time_seq);
5d9e75c4 2985 level = btrfs_header_level(b);
5d9e75c4
JS		 2986 p->locks[level] = BTRFS_READ_LOCK;
2987
2988 while (b) {
2989 level = btrfs_header_level(b);
2990 p->nodes[level] = b;
2991 btrfs_clear_path_blocking(p, NULL, 0);
2992
2993 /*
2994 * we have a lock on b and as long as we aren't changing
2995 * the tree, there is no way to for the items in b to change.
2996 * It is safe to drop the lock on our parent before we
2997 * go through the expensive btree search on b.
2998 */
2999 btrfs_unlock_up_safe(p, level + 1);
3000
d4b4087c
JB		 3001 /*
3002 * Since we can unwind eb's we want to do a real search every
3003 * time.
3004 */
3005 prev_cmp = -1;
d7396f07 3006 ret = key_search(b, key, level, &prev_cmp, &slot);
5d9e75c4
JS		 3007
3008 if (level != 0) {
3009 int dec = 0;
3010 if (ret && slot > 0) {
3011 dec = 1;
3012 slot -= 1;
3013 }
3014 p->slots[level] = slot;
3015 unlock_up(p, level, lowest_unlock, 0, NULL);
3016
3017 if (level == lowest_level) {
3018 if (dec)
3019 p->slots[level]++;
3020 goto done;
3021 }
3022
3023 err = read_block_for_search(NULL, root, p, &b, level,
3024 slot, key, time_seq);
3025 if (err == -EAGAIN)
3026 goto again;
3027 if (err) {
3028 ret = err;
3029 goto done;
3030 }
3031
3032 level = btrfs_header_level(b);
3033 err = btrfs_try_tree_read_lock(b);
3034 if (!err) {
3035 btrfs_set_path_blocking(p);
3036 btrfs_tree_read_lock(b);
3037 btrfs_clear_path_blocking(p, b,
3038 BTRFS_READ_LOCK);
3039 }
9ec72677 3040 b = tree_mod_log_rewind(root->fs_info, p, b, time_seq);
db7f3436
JB		 3041 if (!b) {
3042 ret = -ENOMEM;
3043 goto done;
3044 }
5d9e75c4
JS		 3045 p->locks[level] = BTRFS_READ_LOCK;
3046 p->nodes[level] = b;
5d9e75c4
JS		 3047 } else {
3048 p->slots[level] = slot;
3049 unlock_up(p, level, lowest_unlock, 0, NULL);
3050 goto done;
3051 }
3052 }
3053 ret = 1;
3054done:
3055 if (!p->leave_spinning)
3056 btrfs_set_path_blocking(p);
3057 if (ret < 0)
3058 btrfs_release_path(p);
3059
3060 return ret;
3061}
3062
2f38b3e1
AJ		 3063/*
3064 * helper to use instead of search slot if no exact match is needed but
3065 * instead the next or previous item should be returned.
3066 * When find_higher is true, the next higher item is returned, the next lower
3067 * otherwise.
3068 * When return_any and find_higher are both true, and no higher item is found,
3069 * return the next lower instead.
3070 * When return_any is true and find_higher is false, and no lower item is found,
3071 * return the next higher instead.
3072 * It returns 0 if any item is found, 1 if none is found (tree empty), and
3073 * < 0 on error
3074 */
3075int btrfs_search_slot_for_read(struct btrfs_root *root,
3076 struct btrfs_key *key, struct btrfs_path *p,
3077 int find_higher, int return_any)
3078{
3079 int ret;
3080 struct extent_buffer *leaf;
3081
3082again:
3083 ret = btrfs_search_slot(NULL, root, key, p, 0, 0);
3084 if (ret <= 0)
3085 return ret;
3086 /*
3087 * a return value of 1 means the path is at the position where the
3088 * item should be inserted. Normally this is the next bigger item,
3089 * but in case the previous item is the last in a leaf, path points
3090 * to the first free slot in the previous leaf, i.e. at an invalid
3091 * item.
3092 */
3093 leaf = p->nodes[0];
3094
3095 if (find_higher) {
3096 if (p->slots[0] >= btrfs_header_nritems(leaf)) {
3097 ret = btrfs_next_leaf(root, p);
3098 if (ret <= 0)
3099 return ret;
3100 if (!return_any)
3101 return 1;
3102 /*
3103 * no higher item found, return the next
3104 * lower instead
3105 */
3106 return_any = 0;
3107 find_higher = 0;
3108 btrfs_release_path(p);
3109 goto again;
3110 }
3111 } else {
e6793769
AJ		 3112 if (p->slots[0] == 0) {
3113 ret = btrfs_prev_leaf(root, p);
3114 if (ret < 0)
3115 return ret;
3116 if (!ret) {
23c6bf6a
FDBM		 3117 leaf = p->nodes[0];
3118 if (p->slots[0] == btrfs_header_nritems(leaf))
3119 p->slots[0]--;
e6793769 3120 return 0;
2f38b3e1 3121 }
e6793769
AJ		 3122 if (!return_any)
3123 return 1;
3124 /*
3125 * no lower item found, return the next
3126 * higher instead
3127 */
3128 return_any = 0;
3129 find_higher = 1;
3130 btrfs_release_path(p);
3131 goto again;
3132 } else {
2f38b3e1
AJ		 3133 --p->slots[0];
3134 }
3135 }
3136 return 0;
3137}
3138
74123bd7
CM		 3139/*
3140 * adjust the pointers going up the tree, starting at level
3141 * making sure the right key of each node is points to 'key'.
3142 * This is used after shifting pointers to the left, so it stops
3143 * fixing up pointers when a given leaf/node is not in slot 0 of the
3144 * higher levels
aa5d6bed 3145 *
74123bd7 3146 */
d6a0a126 3147static void fixup_low_keys(struct btrfs_root *root, struct btrfs_path *path,
143bede5 3148 struct btrfs_disk_key *key, int level)
be0e5c09
CM		 3149{
3150 int i;
5f39d397
CM		 3151 struct extent_buffer *t;
3152
234b63a0 3153 for (i = level; i < BTRFS_MAX_LEVEL; i++) {
be0e5c09 3154 int tslot = path->slots[i];
eb60ceac 3155 if (!path->nodes[i])
be0e5c09 3156 break;
5f39d397 3157 t = path->nodes[i];
32adf090 3158 tree_mod_log_set_node_key(root->fs_info, t, tslot, 1);
5f39d397 3159 btrfs_set_node_key(t, key, tslot);
d6025579 3160 btrfs_mark_buffer_dirty(path->nodes[i]);
be0e5c09
CM		 3161 if (tslot != 0)
3162 break;
3163 }
3164}
3165
31840ae1
ZY		 3166/*
3167 * update item key.
3168 *
3169 * This function isn't completely safe. It's the caller's responsibility
3170 * that the new key won't break the order
3171 */
afe5fea7 3172void btrfs_set_item_key_safe(struct btrfs_root *root, struct btrfs_path *path,
143bede5 3173 struct btrfs_key *new_key)
31840ae1
ZY		 3174{
3175 struct btrfs_disk_key disk_key;
3176 struct extent_buffer *eb;
3177 int slot;
3178
3179 eb = path->nodes[0];
3180 slot = path->slots[0];
3181 if (slot > 0) {
3182 btrfs_item_key(eb, &disk_key, slot - 1);
143bede5 3183 BUG_ON(comp_keys(&disk_key, new_key) >= 0);
31840ae1
ZY		 3184 }
3185 if (slot < btrfs_header_nritems(eb) - 1) {
3186 btrfs_item_key(eb, &disk_key, slot + 1);
143bede5 3187 BUG_ON(comp_keys(&disk_key, new_key) <= 0);
31840ae1
ZY		 3188 }
3189
3190 btrfs_cpu_key_to_disk(&disk_key, new_key);
3191 btrfs_set_item_key(eb, &disk_key, slot);
3192 btrfs_mark_buffer_dirty(eb);
3193 if (slot == 0)
d6a0a126 3194 fixup_low_keys(root, path, &disk_key, 1);
31840ae1
ZY		 3195}
3196
74123bd7
CM		 3197/*
3198 * try to push data from one node into the next node left in the
79f95c82 3199 * tree.
aa5d6bed
CM		 3200 *
3201 * returns 0 if some ptrs were pushed left, < 0 if there was some horrible
3202 * error, and > 0 if there was no room in the left hand block.
74123bd7 3203 */
98ed5174
CM		 3204static int push_node_left(struct btrfs_trans_handle *trans,
3205 struct btrfs_root *root, struct extent_buffer *dst,
971a1f66 3206 struct extent_buffer *src, int empty)
be0e5c09 3207{
be0e5c09 3208 int push_items = 0;
bb803951
CM		 3209 int src_nritems;
3210 int dst_nritems;
aa5d6bed 3211 int ret = 0;
be0e5c09 3212
5f39d397
CM		 3213 src_nritems = btrfs_header_nritems(src);
3214 dst_nritems = btrfs_header_nritems(dst);
123abc88 3215 push_items = BTRFS_NODEPTRS_PER_BLOCK(root) - dst_nritems;
7bb86316
CM		 3216 WARN_ON(btrfs_header_generation(src) != trans->transid);
3217 WARN_ON(btrfs_header_generation(dst) != trans->transid);
54aa1f4d 3218
bce4eae9 3219 if (!empty && src_nritems <= 8)
971a1f66
CM		 3220 return 1;
3221
d397712b 3222 if (push_items <= 0)
be0e5c09
CM		 3223 return 1;
3224
bce4eae9 3225 if (empty) {
971a1f66 3226 push_items = min(src_nritems, push_items);
bce4eae9
CM		 3227 if (push_items < src_nritems) {
3228 /* leave at least 8 pointers in the node if
3229 * we aren't going to empty it
3230 */
3231 if (src_nritems - push_items < 8) {
3232 if (push_items <= 8)
3233 return 1;
3234 push_items -= 8;
3235 }
3236 }
3237 } else
3238 push_items = min(src_nritems - 8, push_items);
79f95c82 3239
5de865ee
FDBM		 3240 ret = tree_mod_log_eb_copy(root->fs_info, dst, src, dst_nritems, 0,
3241 push_items);
3242 if (ret) {
3243 btrfs_abort_transaction(trans, root, ret);
3244 return ret;
3245 }
5f39d397
CM		 3246 copy_extent_buffer(dst, src,
3247 btrfs_node_key_ptr_offset(dst_nritems),
3248 btrfs_node_key_ptr_offset(0),
d397712b 3249 push_items * sizeof(struct btrfs_key_ptr));
5f39d397 3250
bb803951 3251 if (push_items < src_nritems) {
57911b8b
JS		 3252 /*
3253 * don't call tree_mod_log_eb_move here, key removal was already
3254 * fully logged by tree_mod_log_eb_copy above.
3255 */
5f39d397
CM		 3256 memmove_extent_buffer(src, btrfs_node_key_ptr_offset(0),
3257 btrfs_node_key_ptr_offset(push_items),
3258 (src_nritems - push_items) *
3259 sizeof(struct btrfs_key_ptr));
3260 }
3261 btrfs_set_header_nritems(src, src_nritems - push_items);
3262 btrfs_set_header_nritems(dst, dst_nritems + push_items);
3263 btrfs_mark_buffer_dirty(src);
3264 btrfs_mark_buffer_dirty(dst);
31840ae1 3265
79f95c82
CM		 3266 return ret;
3267}
3268
3269/*
3270 * try to push data from one node into the next node right in the
3271 * tree.
3272 *
3273 * returns 0 if some ptrs were pushed, < 0 if there was some horrible
3274 * error, and > 0 if there was no room in the right hand block.
3275 *
3276 * this will only push up to 1/2 the contents of the left node over
3277 */
5f39d397
CM		 3278static int balance_node_right(struct btrfs_trans_handle *trans,
3279 struct btrfs_root *root,
3280 struct extent_buffer *dst,
3281 struct extent_buffer *src)
79f95c82 3282{
79f95c82
CM		 3283 int push_items = 0;
3284 int max_push;
3285 int src_nritems;
3286 int dst_nritems;
3287 int ret = 0;
79f95c82 3288
7bb86316
CM		 3289 WARN_ON(btrfs_header_generation(src) != trans->transid);
3290 WARN_ON(btrfs_header_generation(dst) != trans->transid);
3291
5f39d397
CM		 3292 src_nritems = btrfs_header_nritems(src);
3293 dst_nritems = btrfs_header_nritems(dst);
123abc88 3294 push_items = BTRFS_NODEPTRS_PER_BLOCK(root) - dst_nritems;
d397712b 3295 if (push_items <= 0)
79f95c82 3296 return 1;
bce4eae9 3297
d397712b 3298 if (src_nritems < 4)
bce4eae9 3299 return 1;
79f95c82
CM		 3300
3301 max_push = src_nritems / 2 + 1;
3302 /* don't try to empty the node */
d397712b 3303 if (max_push >= src_nritems)
79f95c82 3304 return 1;
252c38f0 3305
79f95c82
CM		 3306 if (max_push < push_items)
3307 push_items = max_push;
3308
f230475e 3309 tree_mod_log_eb_move(root->fs_info, dst, push_items, 0, dst_nritems);
5f39d397
CM		 3310 memmove_extent_buffer(dst, btrfs_node_key_ptr_offset(push_items),
3311 btrfs_node_key_ptr_offset(0),
3312 (dst_nritems) *
3313 sizeof(struct btrfs_key_ptr));
d6025579 3314
5de865ee
FDBM		 3315 ret = tree_mod_log_eb_copy(root->fs_info, dst, src, 0,
3316 src_nritems - push_items, push_items);
3317 if (ret) {
3318 btrfs_abort_transaction(trans, root, ret);
3319 return ret;
3320 }
5f39d397
CM		 3321 copy_extent_buffer(dst, src,
3322 btrfs_node_key_ptr_offset(0),
3323 btrfs_node_key_ptr_offset(src_nritems - push_items),
d397712b 3324 push_items * sizeof(struct btrfs_key_ptr));
79f95c82 3325
5f39d397
CM		 3326 btrfs_set_header_nritems(src, src_nritems - push_items);
3327 btrfs_set_header_nritems(dst, dst_nritems + push_items);
79f95c82 3328
5f39d397
CM		 3329 btrfs_mark_buffer_dirty(src);
3330 btrfs_mark_buffer_dirty(dst);
31840ae1 3331
aa5d6bed 3332 return ret;
be0e5c09
CM		 3333}
3334
97571fd0
CM		 3335/*
3336 * helper function to insert a new root level in the tree.
3337 * A new node is allocated, and a single item is inserted to
3338 * point to the existing root
aa5d6bed
CM		 3339 *
3340 * returns zero on success or < 0 on failure.
97571fd0 3341 */
d397712b 3342static noinline int insert_new_root(struct btrfs_trans_handle *trans,
5f39d397 3343 struct btrfs_root *root,
fdd99c72 3344 struct btrfs_path *path, int level)
5c680ed6 3345{
7bb86316 3346 u64 lower_gen;
5f39d397
CM		 3347 struct extent_buffer *lower;
3348 struct extent_buffer *c;
925baedd 3349 struct extent_buffer *old;
5f39d397 3350 struct btrfs_disk_key lower_key;
5c680ed6
CM		 3351
3352 BUG_ON(path->nodes[level]);
3353 BUG_ON(path->nodes[level-1] != root->node);
3354
7bb86316
CM		 3355 lower = path->nodes[level-1];
3356 if (level == 1)
3357 btrfs_item_key(lower, &lower_key, 0);
3358 else
3359 btrfs_node_key(lower, &lower_key, 0);
3360
31840ae1 3361 c = btrfs_alloc_free_block(trans, root, root->nodesize, 0,
5d4f98a2 3362 root->root_key.objectid, &lower_key,
5581a51a 3363 level, root->node->start, 0);
5f39d397
CM		 3364 if (IS_ERR(c))
3365 return PTR_ERR(c);
925baedd 3366
f0486c68
YZ		 3367 root_add_used(root, root->nodesize);
3368
5d4f98a2 3369 memset_extent_buffer(c, 0, 0, sizeof(struct btrfs_header));
5f39d397
CM		 3370 btrfs_set_header_nritems(c, 1);
3371 btrfs_set_header_level(c, level);
db94535d 3372 btrfs_set_header_bytenr(c, c->start);
5f39d397 3373 btrfs_set_header_generation(c, trans->transid);
5d4f98a2 3374 btrfs_set_header_backref_rev(c, BTRFS_MIXED_BACKREF_REV);
5f39d397 3375 btrfs_set_header_owner(c, root->root_key.objectid);
5f39d397 3376
0a4e5586 3377 write_extent_buffer(c, root->fs_info->fsid, btrfs_header_fsid(),
5f39d397 3378 BTRFS_FSID_SIZE);
e17cade2
CM		 3379
3380 write_extent_buffer(c, root->fs_info->chunk_tree_uuid,
b308bc2f 3381 btrfs_header_chunk_tree_uuid(c), BTRFS_UUID_SIZE);
e17cade2 3382
5f39d397 3383 btrfs_set_node_key(c, &lower_key, 0);
db94535d 3384 btrfs_set_node_blockptr(c, 0, lower->start);
7bb86316 3385 lower_gen = btrfs_header_generation(lower);
31840ae1 3386 WARN_ON(lower_gen != trans->transid);
7bb86316
CM		 3387
3388 btrfs_set_node_ptr_generation(c, 0, lower_gen);
d5719762 3389
5f39d397 3390 btrfs_mark_buffer_dirty(c);
d5719762 3391
925baedd 3392 old = root->node;
fdd99c72 3393 tree_mod_log_set_root_pointer(root, c, 0);
240f62c8 3394 rcu_assign_pointer(root->node, c);
925baedd
CM		 3395
3396 /* the super has an extra ref to root->node */
3397 free_extent_buffer(old);
3398
0b86a832 3399 add_root_to_dirty_list(root);
5f39d397
CM		 3400 extent_buffer_get(c);
3401 path->nodes[level] = c;
bd681513 3402 path->locks[level] = BTRFS_WRITE_LOCK;
5c680ed6
CM		 3403 path->slots[level] = 0;
3404 return 0;
3405}
3406
74123bd7
CM		 3407/*
3408 * worker function to insert a single pointer in a node.
3409 * the node should have enough room for the pointer already
97571fd0 3410 *
74123bd7
CM		 3411 * slot and level indicate where you want the key to go, and
3412 * blocknr is the block the key points to.
3413 */
143bede5
JM		 3414static void insert_ptr(struct btrfs_trans_handle *trans,
3415 struct btrfs_root *root, struct btrfs_path *path,
3416 struct btrfs_disk_key *key, u64 bytenr,
c3e06965 3417 int slot, int level)
74123bd7 3418{
5f39d397 3419 struct extent_buffer *lower;
74123bd7 3420 int nritems;
f3ea38da 3421 int ret;
5c680ed6
CM		 3422
3423 BUG_ON(!path->nodes[level]);
f0486c68 3424 btrfs_assert_tree_locked(path->nodes[level]);
5f39d397
CM		 3425 lower = path->nodes[level];
3426 nritems = btrfs_header_nritems(lower);
c293498b 3427 BUG_ON(slot > nritems);
143bede5 3428 BUG_ON(nritems == BTRFS_NODEPTRS_PER_BLOCK(root));
74123bd7 3429 if (slot != nritems) {
c3e06965 3430 if (level)
f3ea38da
JS		 3431 tree_mod_log_eb_move(root->fs_info, lower, slot + 1,
3432 slot, nritems - slot);
5f39d397
CM		 3433 memmove_extent_buffer(lower,
3434 btrfs_node_key_ptr_offset(slot + 1),
3435 btrfs_node_key_ptr_offset(slot),
d6025579 3436 (nritems - slot) * sizeof(struct btrfs_key_ptr));
74123bd7 3437 }
c3e06965 3438 if (level) {
f3ea38da 3439 ret = tree_mod_log_insert_key(root->fs_info, lower, slot,
c8cc6341 3440 MOD_LOG_KEY_ADD, GFP_NOFS);
f3ea38da
JS		 3441 BUG_ON(ret < 0);
3442 }
5f39d397 3443 btrfs_set_node_key(lower, key, slot);
db94535d 3444 btrfs_set_node_blockptr(lower, slot, bytenr);
74493f7a
CM		 3445 WARN_ON(trans->transid == 0);
3446 btrfs_set_node_ptr_generation(lower, slot, trans->transid);
5f39d397
CM		 3447 btrfs_set_header_nritems(lower, nritems + 1);
3448 btrfs_mark_buffer_dirty(lower);
74123bd7
CM		 3449}
3450
97571fd0
CM		 3451/*
3452 * split the node at the specified level in path in two.
3453 * The path is corrected to point to the appropriate node after the split
3454 *
3455 * Before splitting this tries to make some room in the node by pushing
3456 * left and right, if either one works, it returns right away.
aa5d6bed
CM		 3457 *
3458 * returns 0 on success and < 0 on failure
97571fd0 3459 */
e02119d5
CM		 3460static noinline int split_node(struct btrfs_trans_handle *trans,
3461 struct btrfs_root *root,
3462 struct btrfs_path *path, int level)
be0e5c09 3463{
5f39d397
CM		 3464 struct extent_buffer *c;
3465 struct extent_buffer *split;
3466 struct btrfs_disk_key disk_key;
be0e5c09 3467 int mid;
5c680ed6 3468 int ret;
7518a238 3469 u32 c_nritems;
eb60ceac 3470
5f39d397 3471 c = path->nodes[level];
7bb86316 3472 WARN_ON(btrfs_header_generation(c) != trans->transid);
5f39d397 3473 if (c == root->node) {
d9abbf1c 3474 /*
90f8d62e
JS		 3475 * trying to split the root, lets make a new one
3476 *
fdd99c72 3477 * tree mod log: We don't log_removal old root in
90f8d62e
JS		 3478 * insert_new_root, because that root buffer will be kept as a
3479 * normal node. We are going to log removal of half of the
3480 * elements below with tree_mod_log_eb_copy. We're holding a
3481 * tree lock on the buffer, which is why we cannot race with
3482 * other tree_mod_log users.
d9abbf1c 3483 */
fdd99c72 3484 ret = insert_new_root(trans, root, path, level + 1);
5c680ed6
CM		 3485 if (ret)
3486 return ret;
b3612421 3487 } else {
e66f709b 3488 ret = push_nodes_for_insert(trans, root, path, level);
5f39d397
CM		 3489 c = path->nodes[level];
3490 if (!ret && btrfs_header_nritems(c) <
c448acf0 3491 BTRFS_NODEPTRS_PER_BLOCK(root) - 3)
e66f709b 3492 return 0;
54aa1f4d
CM		 3493 if (ret < 0)
3494 return ret;
be0e5c09 3495 }
e66f709b 3496
5f39d397 3497 c_nritems = btrfs_header_nritems(c);
5d4f98a2
YZ		 3498 mid = (c_nritems + 1) / 2;
3499 btrfs_node_key(c, &disk_key, mid);
7bb86316 3500
5d4f98a2 3501 split = btrfs_alloc_free_block(trans, root, root->nodesize, 0,
31840ae1 3502 root->root_key.objectid,
5581a51a 3503 &disk_key, level, c->start, 0);
5f39d397
CM		 3504 if (IS_ERR(split))
3505 return PTR_ERR(split);
3506
f0486c68
YZ		 3507 root_add_used(root, root->nodesize);
3508
5d4f98a2 3509 memset_extent_buffer(split, 0, 0, sizeof(struct btrfs_header));
5f39d397 3510 btrfs_set_header_level(split, btrfs_header_level(c));
db94535d 3511 btrfs_set_header_bytenr(split, split->start);
5f39d397 3512 btrfs_set_header_generation(split, trans->transid);
5d4f98a2 3513 btrfs_set_header_backref_rev(split, BTRFS_MIXED_BACKREF_REV);
5f39d397
CM		 3514 btrfs_set_header_owner(split, root->root_key.objectid);
3515 write_extent_buffer(split, root->fs_info->fsid,
0a4e5586 3516 btrfs_header_fsid(), BTRFS_FSID_SIZE);
e17cade2 3517 write_extent_buffer(split, root->fs_info->chunk_tree_uuid,
b308bc2f 3518 btrfs_header_chunk_tree_uuid(split),
e17cade2 3519 BTRFS_UUID_SIZE);
54aa1f4d 3520
5de865ee
FDBM		 3521 ret = tree_mod_log_eb_copy(root->fs_info, split, c, 0,
3522 mid, c_nritems - mid);
3523 if (ret) {
3524 btrfs_abort_transaction(trans, root, ret);
3525 return ret;
3526 }
5f39d397
CM		 3527 copy_extent_buffer(split, c,
3528 btrfs_node_key_ptr_offset(0),
3529 btrfs_node_key_ptr_offset(mid),
3530 (c_nritems - mid) * sizeof(struct btrfs_key_ptr));
3531 btrfs_set_header_nritems(split, c_nritems - mid);
3532 btrfs_set_header_nritems(c, mid);
aa5d6bed
CM		 3533 ret = 0;
3534
5f39d397
CM		 3535 btrfs_mark_buffer_dirty(c);
3536 btrfs_mark_buffer_dirty(split);
3537
143bede5 3538 insert_ptr(trans, root, path, &disk_key, split->start,
c3e06965 3539 path->slots[level + 1] + 1, level + 1);
aa5d6bed 3540
5de08d7d 3541 if (path->slots[level] >= mid) {
5c680ed6 3542 path->slots[level] -= mid;
925baedd 3543 btrfs_tree_unlock(c);
5f39d397
CM		 3544 free_extent_buffer(c);
3545 path->nodes[level] = split;
5c680ed6
CM		 3546 path->slots[level + 1] += 1;
3547 } else {
925baedd 3548 btrfs_tree_unlock(split);
5f39d397 3549 free_extent_buffer(split);
be0e5c09 3550 }
aa5d6bed 3551 return ret;
be0e5c09
CM		 3552}
3553
74123bd7
CM		 3554/*
3555 * how many bytes are required to store the items in a leaf. start
3556 * and nr indicate which items in the leaf to check. This totals up the
3557 * space used both by the item structs and the item data
3558 */
5f39d397 3559static int leaf_space_used(struct extent_buffer *l, int start, int nr)
be0e5c09 3560{
41be1f3b
JB		 3561 struct btrfs_item *start_item;
3562 struct btrfs_item *end_item;
3563 struct btrfs_map_token token;
be0e5c09 3564 int data_len;
5f39d397 3565 int nritems = btrfs_header_nritems(l);
d4dbff95 3566 int end = min(nritems, start + nr) - 1;
be0e5c09
CM		 3567
3568 if (!nr)
3569 return 0;
41be1f3b 3570 btrfs_init_map_token(&token);
dd3cc16b
RK		 3571 start_item = btrfs_item_nr(start);
3572 end_item = btrfs_item_nr(end);
41be1f3b
JB		 3573 data_len = btrfs_token_item_offset(l, start_item, &token) +
3574 btrfs_token_item_size(l, start_item, &token);
3575 data_len = data_len - btrfs_token_item_offset(l, end_item, &token);
0783fcfc 3576 data_len += sizeof(struct btrfs_item) * nr;
d4dbff95 3577 WARN_ON(data_len < 0);
be0e5c09
CM		 3578 return data_len;
3579}
3580
d4dbff95
CM		 3581/*
3582 * The space between the end of the leaf items and
3583 * the start of the leaf data. IOW, how much room
3584 * the leaf has left for both items and data
3585 */
d397712b 3586noinline int btrfs_leaf_free_space(struct btrfs_root *root,
e02119d5 3587 struct extent_buffer *leaf)
d4dbff95 3588{
5f39d397
CM		 3589 int nritems = btrfs_header_nritems(leaf);
3590 int ret;
3591 ret = BTRFS_LEAF_DATA_SIZE(root) - leaf_space_used(leaf, 0, nritems);
3592 if (ret < 0) {
efe120a0
FH		 3593 btrfs_crit(root->fs_info,
3594 "leaf free space ret %d, leaf data size %lu, used %d nritems %d",
ae2f5411 3595 ret, (unsigned long) BTRFS_LEAF_DATA_SIZE(root),
5f39d397
CM		 3596 leaf_space_used(leaf, 0, nritems), nritems);
3597 }
3598 return ret;
d4dbff95
CM		 3599}
3600
99d8f83c
CM		 3601/*
3602 * min slot controls the lowest index we're willing to push to the
3603 * right. We'll push up to and including min_slot, but no lower
3604 */
44871b1b
CM		 3605static noinline int __push_leaf_right(struct btrfs_trans_handle *trans,
3606 struct btrfs_root *root,
3607 struct btrfs_path *path,
3608 int data_size, int empty,
3609 struct extent_buffer *right,
99d8f83c
CM		 3610 int free_space, u32 left_nritems,
3611 u32 min_slot)
00ec4c51 3612{
5f39d397 3613 struct extent_buffer *left = path->nodes[0];
44871b1b 3614 struct extent_buffer *upper = path->nodes[1];
cfed81a0 3615 struct btrfs_map_token token;
5f39d397 3616 struct btrfs_disk_key disk_key;
00ec4c51 3617 int slot;
34a38218 3618 u32 i;
00ec4c51
CM		 3619 int push_space = 0;
3620 int push_items = 0;
0783fcfc 3621 struct btrfs_item *item;
34a38218 3622 u32 nr;
7518a238 3623 u32 right_nritems;
5f39d397 3624 u32 data_end;
db94535d 3625 u32 this_item_size;
00ec4c51 3626
cfed81a0
CM		 3627 btrfs_init_map_token(&token);
3628
34a38218
CM		 3629 if (empty)
3630 nr = 0;
3631 else
99d8f83c 3632 nr = max_t(u32, 1, min_slot);
34a38218 3633
31840ae1 3634 if (path->slots[0] >= left_nritems)
87b29b20 3635 push_space += data_size;
31840ae1 3636
44871b1b 3637 slot = path->slots[1];
34a38218
CM		 3638 i = left_nritems - 1;
3639 while (i >= nr) {
dd3cc16b 3640 item = btrfs_item_nr(i);
db94535d 3641
31840ae1
ZY		 3642 if (!empty && push_items > 0) {
3643 if (path->slots[0] > i)
3644 break;
3645 if (path->slots[0] == i) {
3646 int space = btrfs_leaf_free_space(root, left);
3647 if (space + push_space * 2 > free_space)
3648 break;
3649 }
3650 }
3651
00ec4c51 3652 if (path->slots[0] == i)
87b29b20 3653 push_space += data_size;
db94535d 3654
db94535d
CM		 3655 this_item_size = btrfs_item_size(left, item);
3656 if (this_item_size + sizeof(*item) + push_space > free_space)
00ec4c51 3657 break;
31840ae1 3658
00ec4c51 3659 push_items++;
db94535d 3660 push_space += this_item_size + sizeof(*item);
34a38218
CM		 3661 if (i == 0)
3662 break;
3663 i--;
db94535d 3664 }
5f39d397 3665
925baedd
CM		 3666 if (push_items == 0)
3667 goto out_unlock;
5f39d397 3668
6c1500f2 3669 WARN_ON(!empty && push_items == left_nritems);
5f39d397 3670
00ec4c51 3671 /* push left to right */
5f39d397 3672 right_nritems = btrfs_header_nritems(right);
34a38218 3673
5f39d397 3674 push_space = btrfs_item_end_nr(left, left_nritems - push_items);
123abc88 3675 push_space -= leaf_data_end(root, left);
5f39d397 3676
00ec4c51 3677 /* make room in the right data area */
5f39d397
CM		 3678 data_end = leaf_data_end(root, right);
3679 memmove_extent_buffer(right,
3680 btrfs_leaf_data(right) + data_end - push_space,
3681 btrfs_leaf_data(right) + data_end,
3682 BTRFS_LEAF_DATA_SIZE(root) - data_end);
3683
00ec4c51 3684 /* copy from the left data area */
5f39d397 3685 copy_extent_buffer(right, left, btrfs_leaf_data(right) +
d6025579
CM		 3686 BTRFS_LEAF_DATA_SIZE(root) - push_space,
3687 btrfs_leaf_data(left) + leaf_data_end(root, left),
3688 push_space);
5f39d397
CM		 3689
3690 memmove_extent_buffer(right, btrfs_item_nr_offset(push_items),
3691 btrfs_item_nr_offset(0),
3692 right_nritems * sizeof(struct btrfs_item));
3693
00ec4c51 3694 /* copy the items from left to right */
5f39d397
CM		 3695 copy_extent_buffer(right, left, btrfs_item_nr_offset(0),
3696 btrfs_item_nr_offset(left_nritems - push_items),
3697 push_items * sizeof(struct btrfs_item));
00ec4c51
CM		 3698
3699 /* update the item pointers */
7518a238 3700 right_nritems += push_items;
5f39d397 3701 btrfs_set_header_nritems(right, right_nritems);
123abc88 3702 push_space = BTRFS_LEAF_DATA_SIZE(root);
7518a238 3703 for (i = 0; i < right_nritems; i++) {
dd3cc16b 3704 item = btrfs_item_nr(i);
cfed81a0
CM		 3705 push_space -= btrfs_token_item_size(right, item, &token);
3706 btrfs_set_token_item_offset(right, item, push_space, &token);
db94535d
CM		 3707 }
3708
7518a238 3709 left_nritems -= push_items;
5f39d397 3710 btrfs_set_header_nritems(left, left_nritems);
00ec4c51 3711
34a38218
CM		 3712 if (left_nritems)
3713 btrfs_mark_buffer_dirty(left);
f0486c68
YZ		 3714 else
3715 clean_tree_block(trans, root, left);
3716
5f39d397 3717 btrfs_mark_buffer_dirty(right);
a429e513 3718
5f39d397
CM		 3719 btrfs_item_key(right, &disk_key, 0);
3720 btrfs_set_node_key(upper, &disk_key, slot + 1);
d6025579 3721 btrfs_mark_buffer_dirty(upper);
02217ed2 3722
00ec4c51 3723 /* then fixup the leaf pointer in the path */
7518a238
CM		 3724 if (path->slots[0] >= left_nritems) {
3725 path->slots[0] -= left_nritems;
925baedd
CM		 3726 if (btrfs_header_nritems(path->nodes[0]) == 0)
3727 clean_tree_block(trans, root, path->nodes[0]);
3728 btrfs_tree_unlock(path->nodes[0]);
5f39d397
CM		 3729 free_extent_buffer(path->nodes[0]);
3730 path->nodes[0] = right;
00ec4c51
CM		 3731 path->slots[1] += 1;
3732 } else {
925baedd 3733 btrfs_tree_unlock(right);
5f39d397 3734 free_extent_buffer(right);
00ec4c51
CM		 3735 }
3736 return 0;
925baedd
CM		 3737
3738out_unlock:
3739 btrfs_tree_unlock(right);
3740 free_extent_buffer(right);
3741 return 1;
00ec4c51 3742}
925baedd 3743
44871b1b
CM		 3744/*
3745 * push some data in the path leaf to the right, trying to free up at
3746 * least data_size bytes. returns zero if the push worked, nonzero otherwise
3747 *
3748 * returns 1 if the push failed because the other node didn't have enough
3749 * room, 0 if everything worked out and < 0 if there were major errors.
99d8f83c
CM		 3750 *
3751 * this will push starting from min_slot to the end of the leaf. It won't
3752 * push any slot lower than min_slot
44871b1b
CM		 3753 */
3754static int push_leaf_right(struct btrfs_trans_handle *trans, struct btrfs_root
99d8f83c
CM		 3755 *root, struct btrfs_path *path,
3756 int min_data_size, int data_size,
3757 int empty, u32 min_slot)
44871b1b
CM		 3758{
3759 struct extent_buffer *left = path->nodes[0];
3760 struct extent_buffer *right;
3761 struct extent_buffer *upper;
3762 int slot;
3763 int free_space;
3764 u32 left_nritems;
3765 int ret;
3766
3767 if (!path->nodes[1])
3768 return 1;
3769
3770 slot = path->slots[1];
3771 upper = path->nodes[1];
3772 if (slot >= btrfs_header_nritems(upper) - 1)
3773 return 1;
3774
3775 btrfs_assert_tree_locked(path->nodes[1]);
3776
3777 right = read_node_slot(root, upper, slot + 1);
91ca338d
TI		 3778 if (right == NULL)
3779 return 1;
3780
44871b1b
CM		 3781 btrfs_tree_lock(right);
3782 btrfs_set_lock_blocking(right);
3783
3784 free_space = btrfs_leaf_free_space(root, right);
3785 if (free_space < data_size)
3786 goto out_unlock;
3787
3788 /* cow and double check */
3789 ret = btrfs_cow_block(trans, root, right, upper,
3790 slot + 1, &right);
3791 if (ret)
3792 goto out_unlock;
3793
3794 free_space = btrfs_leaf_free_space(root, right);
3795 if (free_space < data_size)
3796 goto out_unlock;
3797
3798 left_nritems = btrfs_header_nritems(left);
3799 if (left_nritems == 0)
3800 goto out_unlock;
3801
2ef1fed2
FDBM		 3802 if (path->slots[0] == left_nritems && !empty) {
3803 /* Key greater than all keys in the leaf, right neighbor has
3804 * enough room for it and we're not emptying our leaf to delete
3805 * it, therefore use right neighbor to insert the new item and
3806 * no need to touch/dirty our left leaft. */
3807 btrfs_tree_unlock(left);
3808 free_extent_buffer(left);
3809 path->nodes[0] = right;
3810 path->slots[0] = 0;
3811 path->slots[1]++;
3812 return 0;
3813 }
3814
99d8f83c
CM		 3815 return __push_leaf_right(trans, root, path, min_data_size, empty,
3816 right, free_space, left_nritems, min_slot);
44871b1b
CM		 3817out_unlock:
3818 btrfs_tree_unlock(right);
3819 free_extent_buffer(right);
3820 return 1;
3821}
3822
74123bd7
CM		 3823/*
3824 * push some data in the path leaf to the left, trying to free up at
3825 * least data_size bytes. returns zero if the push worked, nonzero otherwise
99d8f83c
CM		 3826 *
3827 * max_slot can put a limit on how far into the leaf we'll push items. The
3828 * item at 'max_slot' won't be touched. Use (u32)-1 to make us do all the
3829 * items
74123bd7 3830 */
44871b1b
CM		 3831static noinline int __push_leaf_left(struct btrfs_trans_handle *trans,
3832 struct btrfs_root *root,
3833 struct btrfs_path *path, int data_size,
3834 int empty, struct extent_buffer *left,
99d8f83c
CM		 3835 int free_space, u32 right_nritems,
3836 u32 max_slot)
be0e5c09 3837{
5f39d397
CM		 3838 struct btrfs_disk_key disk_key;
3839 struct extent_buffer *right = path->nodes[0];
be0e5c09 3840 int i;
be0e5c09
CM		 3841 int push_space = 0;
3842 int push_items = 0;
0783fcfc 3843 struct btrfs_item *item;
7518a238 3844 u32 old_left_nritems;
34a38218 3845 u32 nr;
aa5d6bed 3846 int ret = 0;
db94535d
CM		 3847 u32 this_item_size;
3848 u32 old_left_item_size;
cfed81a0
CM		 3849 struct btrfs_map_token token;
3850
3851 btrfs_init_map_token(&token);
be0e5c09 3852
34a38218 3853 if (empty)
99d8f83c 3854 nr = min(right_nritems, max_slot);
34a38218 3855 else
99d8f83c 3856 nr = min(right_nritems - 1, max_slot);
34a38218
CM		 3857
3858 for (i = 0; i < nr; i++) {
dd3cc16b 3859 item = btrfs_item_nr(i);
db94535d 3860
31840ae1
ZY		 3861 if (!empty && push_items > 0) {
3862 if (path->slots[0] < i)
3863 break;
3864 if (path->slots[0] == i) {
3865 int space = btrfs_leaf_free_space(root, right);
3866 if (space + push_space * 2 > free_space)
3867 break;
3868 }
3869 }
3870
be0e5c09 3871 if (path->slots[0] == i)
87b29b20 3872 push_space += data_size;
db94535d
CM		 3873
3874 this_item_size = btrfs_item_size(right, item);
3875 if (this_item_size + sizeof(*item) + push_space > free_space)
be0e5c09 3876 break;
db94535d 3877
be0e5c09 3878 push_items++;
db94535d
CM		 3879 push_space += this_item_size + sizeof(*item);
3880 }
3881
be0e5c09 3882 if (push_items == 0) {
925baedd
CM		 3883 ret = 1;
3884 goto out;
be0e5c09 3885 }
fae7f21c 3886 WARN_ON(!empty && push_items == btrfs_header_nritems(right));
5f39d397 3887
be0e5c09 3888 /* push data from right to left */
5f39d397
CM		 3889 copy_extent_buffer(left, right,
3890 btrfs_item_nr_offset(btrfs_header_nritems(left)),
3891 btrfs_item_nr_offset(0),
3892 push_items * sizeof(struct btrfs_item));
3893
123abc88 3894 push_space = BTRFS_LEAF_DATA_SIZE(root) -
d397712b 3895 btrfs_item_offset_nr(right, push_items - 1);
5f39d397
CM		 3896
3897 copy_extent_buffer(left, right, btrfs_leaf_data(left) +
d6025579
CM		 3898 leaf_data_end(root, left) - push_space,
3899 btrfs_leaf_data(right) +
5f39d397 3900 btrfs_item_offset_nr(right, push_items - 1),
d6025579 3901 push_space);
5f39d397 3902 old_left_nritems = btrfs_header_nritems(left);
87b29b20 3903 BUG_ON(old_left_nritems <= 0);
eb60ceac 3904
db94535d 3905 old_left_item_size = btrfs_item_offset_nr(left, old_left_nritems - 1);
0783fcfc 3906 for (i = old_left_nritems; i < old_left_nritems + push_items; i++) {
5f39d397 3907 u32 ioff;
db94535d 3908
dd3cc16b 3909 item = btrfs_item_nr(i);
db94535d 3910
cfed81a0
CM		 3911 ioff = btrfs_token_item_offset(left, item, &token);
3912 btrfs_set_token_item_offset(left, item,
3913 ioff - (BTRFS_LEAF_DATA_SIZE(root) - old_left_item_size),
3914 &token);
be0e5c09 3915 }
5f39d397 3916 btrfs_set_header_nritems(left, old_left_nritems + push_items);
be0e5c09
CM		 3917
3918 /* fixup right node */
31b1a2bd
JL		 3919 if (push_items > right_nritems)
3920 WARN(1, KERN_CRIT "push items %d nr %u\n", push_items,
d397712b 3921 right_nritems);
34a38218
CM		 3922
3923 if (push_items < right_nritems) {
3924 push_space = btrfs_item_offset_nr(right, push_items - 1) -
3925 leaf_data_end(root, right);
3926 memmove_extent_buffer(right, btrfs_leaf_data(right) +
3927 BTRFS_LEAF_DATA_SIZE(root) - push_space,
3928 btrfs_leaf_data(right) +
3929 leaf_data_end(root, right), push_space);
3930
3931 memmove_extent_buffer(right, btrfs_item_nr_offset(0),
5f39d397
CM		 3932 btrfs_item_nr_offset(push_items),
3933 (btrfs_header_nritems(right) - push_items) *
3934 sizeof(struct btrfs_item));
34a38218 3935 }
eef1c494
Y		 3936 right_nritems -= push_items;
3937 btrfs_set_header_nritems(right, right_nritems);
123abc88 3938 push_space = BTRFS_LEAF_DATA_SIZE(root);
5f39d397 3939 for (i = 0; i < right_nritems; i++) {
dd3cc16b 3940 item = btrfs_item_nr(i);
db94535d 3941
cfed81a0
CM		 3942 push_space = push_space - btrfs_token_item_size(right,
3943 item, &token);
3944 btrfs_set_token_item_offset(right, item, push_space, &token);
db94535d 3945 }
eb60ceac 3946
5f39d397 3947 btrfs_mark_buffer_dirty(left);
34a38218
CM		 3948 if (right_nritems)
3949 btrfs_mark_buffer_dirty(right);
f0486c68
YZ		 3950 else
3951 clean_tree_block(trans, root, right);
098f59c2 3952
5f39d397 3953 btrfs_item_key(right, &disk_key, 0);
d6a0a126 3954 fixup_low_keys(root, path, &disk_key, 1);
be0e5c09
CM		 3955
3956 /* then fixup the leaf pointer in the path */
3957 if (path->slots[0] < push_items) {
3958 path->slots[0] += old_left_nritems;
925baedd 3959 btrfs_tree_unlock(path->nodes[0]);
5f39d397
CM		 3960 free_extent_buffer(path->nodes[0]);
3961 path->nodes[0] = left;
be0e5c09
CM		 3962 path->slots[1] -= 1;
3963 } else {
925baedd 3964 btrfs_tree_unlock(left);
5f39d397 3965 free_extent_buffer(left);
be0e5c09
CM		 3966 path->slots[0] -= push_items;
3967 }
eb60ceac 3968 BUG_ON(path->slots[0] < 0);
aa5d6bed 3969 return ret;
925baedd
CM		 3970out:
3971 btrfs_tree_unlock(left);
3972 free_extent_buffer(left);
3973 return ret;
be0e5c09
CM		 3974}
3975
44871b1b
CM		 3976/*
3977 * push some data in the path leaf to the left, trying to free up at
3978 * least data_size bytes. returns zero if the push worked, nonzero otherwise
99d8f83c
CM		 3979 *
3980 * max_slot can put a limit on how far into the leaf we'll push items. The
3981 * item at 'max_slot' won't be touched. Use (u32)-1 to make us push all the
3982 * items
44871b1b
CM		 3983 */
3984static int push_leaf_left(struct btrfs_trans_handle *trans, struct btrfs_root
99d8f83c
CM		 3985 *root, struct btrfs_path *path, int min_data_size,
3986 int data_size, int empty, u32 max_slot)
44871b1b
CM		 3987{
3988 struct extent_buffer *right = path->nodes[0];
3989 struct extent_buffer *left;
3990 int slot;
3991 int free_space;
3992 u32 right_nritems;
3993 int ret = 0;
3994
3995 slot = path->slots[1];
3996 if (slot == 0)
3997 return 1;
3998 if (!path->nodes[1])
3999 return 1;
4000
4001 right_nritems = btrfs_header_nritems(right);
4002 if (right_nritems == 0)
4003 return 1;
4004
4005 btrfs_assert_tree_locked(path->nodes[1]);
4006
4007 left = read_node_slot(root, path->nodes[1], slot - 1);
91ca338d
TI		 4008 if (left == NULL)
4009 return 1;
4010
44871b1b
CM		 4011 btrfs_tree_lock(left);
4012 btrfs_set_lock_blocking(left);
4013
4014 free_space = btrfs_leaf_free_space(root, left);
4015 if (free_space < data_size) {
4016 ret = 1;
4017 goto out;
4018 }
4019
4020 /* cow and double check */
4021 ret = btrfs_cow_block(trans, root, left,
4022 path->nodes[1], slot - 1, &left);
4023 if (ret) {
4024 /* we hit -ENOSPC, but it isn't fatal here */
79787eaa
JM		 4025 if (ret == -ENOSPC)
4026 ret = 1;
44871b1b
CM		 4027 goto out;
4028 }
4029
4030 free_space = btrfs_leaf_free_space(root, left);
4031 if (free_space < data_size) {
4032 ret = 1;
4033 goto out;
4034 }
4035
99d8f83c
CM		 4036 return __push_leaf_left(trans, root, path, min_data_size,
4037 empty, left, free_space, right_nritems,
4038 max_slot);
44871b1b
CM		 4039out:
4040 btrfs_tree_unlock(left);
4041 free_extent_buffer(left);
4042 return ret;
4043}
4044
4045/*
4046 * split the path's leaf in two, making sure there is at least data_size
4047 * available for the resulting leaf level of the path.
44871b1b 4048 */
143bede5
JM		 4049static noinline void copy_for_split(struct btrfs_trans_handle *trans,
4050 struct btrfs_root *root,
4051 struct btrfs_path *path,
4052 struct extent_buffer *l,
4053 struct extent_buffer *right,
4054 int slot, int mid, int nritems)
44871b1b
CM		 4055{
4056 int data_copy_size;
4057 int rt_data_off;
4058 int i;
44871b1b 4059 struct btrfs_disk_key disk_key;
cfed81a0
CM		 4060 struct btrfs_map_token token;
4061
4062 btrfs_init_map_token(&token);
44871b1b
CM		 4063
4064 nritems = nritems - mid;
4065 btrfs_set_header_nritems(right, nritems);
4066 data_copy_size = btrfs_item_end_nr(l, mid) - leaf_data_end(root, l);
4067
4068 copy_extent_buffer(right, l, btrfs_item_nr_offset(0),
4069 btrfs_item_nr_offset(mid),
4070 nritems * sizeof(struct btrfs_item));
4071
4072 copy_extent_buffer(right, l,
4073 btrfs_leaf_data(right) + BTRFS_LEAF_DATA_SIZE(root) -
4074 data_copy_size, btrfs_leaf_data(l) +
4075 leaf_data_end(root, l), data_copy_size);
4076
4077 rt_data_off = BTRFS_LEAF_DATA_SIZE(root) -
4078 btrfs_item_end_nr(l, mid);
4079
4080 for (i = 0; i < nritems; i++) {
dd3cc16b 4081 struct btrfs_item *item = btrfs_item_nr(i);
44871b1b
CM		 4082 u32 ioff;
4083
cfed81a0
CM		 4084 ioff = btrfs_token_item_offset(right, item, &token);
4085 btrfs_set_token_item_offset(right, item,
4086 ioff + rt_data_off, &token);
44871b1b
CM		 4087 }
4088
44871b1b 4089 btrfs_set_header_nritems(l, mid);
44871b1b 4090 btrfs_item_key(right, &disk_key, 0);
143bede5 4091 insert_ptr(trans, root, path, &disk_key, right->start,
c3e06965 4092 path->slots[1] + 1, 1);
44871b1b
CM		 4093
4094 btrfs_mark_buffer_dirty(right);
4095 btrfs_mark_buffer_dirty(l);
4096 BUG_ON(path->slots[0] != slot);
4097
44871b1b
CM		 4098 if (mid <= slot) {
4099 btrfs_tree_unlock(path->nodes[0]);
4100 free_extent_buffer(path->nodes[0]);
4101 path->nodes[0] = right;
4102 path->slots[0] -= mid;
4103 path->slots[1] += 1;
4104 } else {
4105 btrfs_tree_unlock(right);
4106 free_extent_buffer(right);
4107 }
4108
4109 BUG_ON(path->slots[0] < 0);
44871b1b
CM		 4110}
4111
99d8f83c
CM		 4112/*
4113 * double splits happen when we need to insert a big item in the middle
4114 * of a leaf. A double split can leave us with 3 mostly empty leaves:
4115 * leaf: [ slots 0 - N] [ our target ] [ N + 1 - total in leaf ]
4116 * A B C
4117 *
4118 * We avoid this by trying to push the items on either side of our target
4119 * into the adjacent leaves. If all goes well we can avoid the double split
4120 * completely.
4121 */
4122static noinline int push_for_double_split(struct btrfs_trans_handle *trans,
4123 struct btrfs_root *root,
4124 struct btrfs_path *path,
4125 int data_size)
4126{
4127 int ret;
4128 int progress = 0;
4129 int slot;
4130 u32 nritems;
5a4267ca 4131 int space_needed = data_size;
99d8f83c
CM		 4132
4133 slot = path->slots[0];
5a4267ca
FDBM		 4134 if (slot < btrfs_header_nritems(path->nodes[0]))
4135 space_needed -= btrfs_leaf_free_space(root, path->nodes[0]);
99d8f83c
CM		 4136
4137 /*
4138 * try to push all the items after our slot into the
4139 * right leaf
4140 */
5a4267ca 4141 ret = push_leaf_right(trans, root, path, 1, space_needed, 0, slot);
99d8f83c
CM		 4142 if (ret < 0)
4143 return ret;
4144
4145 if (ret == 0)
4146 progress++;
4147
4148 nritems = btrfs_header_nritems(path->nodes[0]);
4149 /*
4150 * our goal is to get our slot at the start or end of a leaf. If
4151 * we've done so we're done
4152 */
4153 if (path->slots[0] == 0 || path->slots[0] == nritems)
4154 return 0;
4155
4156 if (btrfs_leaf_free_space(root, path->nodes[0]) >= data_size)
4157 return 0;
4158
4159 /* try to push all the items before our slot into the next leaf */
4160 slot = path->slots[0];
5a4267ca 4161 ret = push_leaf_left(trans, root, path, 1, space_needed, 0, slot);
99d8f83c
CM		 4162 if (ret < 0)
4163 return ret;
4164
4165 if (ret == 0)
4166 progress++;
4167
4168 if (progress)
4169 return 0;
4170 return 1;
4171}
4172
74123bd7
CM		 4173/*
4174 * split the path's leaf in two, making sure there is at least data_size
4175 * available for the resulting leaf level of the path.
aa5d6bed
CM		 4176 *
4177 * returns 0 if all went well and < 0 on failure.
74123bd7 4178 */
e02119d5
CM		 4179static noinline int split_leaf(struct btrfs_trans_handle *trans,
4180 struct btrfs_root *root,
4181 struct btrfs_key *ins_key,
4182 struct btrfs_path *path, int data_size,
4183 int extend)
be0e5c09 4184{
5d4f98a2 4185 struct btrfs_disk_key disk_key;
5f39d397 4186 struct extent_buffer *l;
7518a238 4187 u32 nritems;
eb60ceac
CM		 4188 int mid;
4189 int slot;
5f39d397 4190 struct extent_buffer *right;
d4dbff95 4191 int ret = 0;
aa5d6bed 4192 int wret;
5d4f98a2 4193 int split;
cc0c5538 4194 int num_doubles = 0;
99d8f83c 4195 int tried_avoid_double = 0;
aa5d6bed 4196
a5719521
YZ		 4197 l = path->nodes[0];
4198 slot = path->slots[0];
4199 if (extend && data_size + btrfs_item_size_nr(l, slot) +
4200 sizeof(struct btrfs_item) > BTRFS_LEAF_DATA_SIZE(root))
4201 return -EOVERFLOW;
4202
40689478 4203 /* first try to make some room by pushing left and right */
33157e05 4204 if (data_size && path->nodes[1]) {
5a4267ca
FDBM		 4205 int space_needed = data_size;
4206
4207 if (slot < btrfs_header_nritems(l))
4208 space_needed -= btrfs_leaf_free_space(root, l);
4209
4210 wret = push_leaf_right(trans, root, path, space_needed,
4211 space_needed, 0, 0);
d397712b 4212 if (wret < 0)
eaee50e8 4213 return wret;
3685f791 4214 if (wret) {
5a4267ca
FDBM		 4215 wret = push_leaf_left(trans, root, path, space_needed,
4216 space_needed, 0, (u32)-1);
3685f791
CM		 4217 if (wret < 0)
4218 return wret;
4219 }
4220 l = path->nodes[0];
aa5d6bed 4221
3685f791 4222 /* did the pushes work? */
87b29b20 4223 if (btrfs_leaf_free_space(root, l) >= data_size)
3685f791 4224 return 0;
3326d1b0 4225 }
aa5d6bed 4226
5c680ed6 4227 if (!path->nodes[1]) {
fdd99c72 4228 ret = insert_new_root(trans, root, path, 1);
5c680ed6
CM		 4229 if (ret)
4230 return ret;
4231 }
cc0c5538 4232again:
5d4f98a2 4233 split = 1;
cc0c5538 4234 l = path->nodes[0];
eb60ceac 4235 slot = path->slots[0];
5f39d397 4236 nritems = btrfs_header_nritems(l);
d397712b 4237 mid = (nritems + 1) / 2;
54aa1f4d 4238
5d4f98a2
YZ		 4239 if (mid <= slot) {
4240 if (nritems == 1 ||
4241 leaf_space_used(l, mid, nritems - mid) + data_size >
4242 BTRFS_LEAF_DATA_SIZE(root)) {
4243 if (slot >= nritems) {
4244 split = 0;
4245 } else {
4246 mid = slot;
4247 if (mid != nritems &&
4248 leaf_space_used(l, mid, nritems - mid) +
4249 data_size > BTRFS_LEAF_DATA_SIZE(root)) {
99d8f83c
CM		 4250 if (data_size && !tried_avoid_double)
4251 goto push_for_double;
5d4f98a2
YZ		 4252 split = 2;
4253 }
4254 }
4255 }
4256 } else {
4257 if (leaf_space_used(l, 0, mid) + data_size >
4258 BTRFS_LEAF_DATA_SIZE(root)) {
4259 if (!extend && data_size && slot == 0) {
4260 split = 0;
4261 } else if ((extend || !data_size) && slot == 0) {
4262 mid = 1;
4263 } else {
4264 mid = slot;
4265 if (mid != nritems &&
4266 leaf_space_used(l, mid, nritems - mid) +
4267 data_size > BTRFS_LEAF_DATA_SIZE(root)) {
99d8f83c
CM		 4268 if (data_size && !tried_avoid_double)
4269 goto push_for_double;
67871254 4270 split = 2;
5d4f98a2
YZ		 4271 }
4272 }
4273 }
4274 }
4275
4276 if (split == 0)
4277 btrfs_cpu_key_to_disk(&disk_key, ins_key);
4278 else
4279 btrfs_item_key(l, &disk_key, mid);
4280
4281 right = btrfs_alloc_free_block(trans, root, root->leafsize, 0,
31840ae1 4282 root->root_key.objectid,
5581a51a 4283 &disk_key, 0, l->start, 0);
f0486c68 4284 if (IS_ERR(right))
5f39d397 4285 return PTR_ERR(right);
f0486c68
YZ		 4286
4287 root_add_used(root, root->leafsize);
5f39d397
CM		 4288
4289 memset_extent_buffer(right, 0, 0, sizeof(struct btrfs_header));
db94535d 4290 btrfs_set_header_bytenr(right, right->start);
5f39d397 4291 btrfs_set_header_generation(right, trans->transid);
5d4f98a2 4292 btrfs_set_header_backref_rev(right, BTRFS_MIXED_BACKREF_REV);
5f39d397
CM		 4293 btrfs_set_header_owner(right, root->root_key.objectid);
4294 btrfs_set_header_level(right, 0);
4295 write_extent_buffer(right, root->fs_info->fsid,
0a4e5586 4296 btrfs_header_fsid(), BTRFS_FSID_SIZE);
e17cade2
CM		 4297
4298 write_extent_buffer(right, root->fs_info->chunk_tree_uuid,
b308bc2f 4299 btrfs_header_chunk_tree_uuid(right),
e17cade2 4300 BTRFS_UUID_SIZE);
44871b1b 4301
5d4f98a2
YZ		 4302 if (split == 0) {
4303 if (mid <= slot) {
4304 btrfs_set_header_nritems(right, 0);
143bede5 4305 insert_ptr(trans, root, path, &disk_key, right->start,
c3e06965 4306 path->slots[1] + 1, 1);
5d4f98a2
YZ		 4307 btrfs_tree_unlock(path->nodes[0]);
4308 free_extent_buffer(path->nodes[0]);
4309 path->nodes[0] = right;
4310 path->slots[0] = 0;
4311 path->slots[1] += 1;
4312 } else {
4313 btrfs_set_header_nritems(right, 0);
143bede5 4314 insert_ptr(trans, root, path, &disk_key, right->start,
c3e06965 4315 path->slots[1], 1);
5d4f98a2
YZ		 4316 btrfs_tree_unlock(path->nodes[0]);
4317 free_extent_buffer(path->nodes[0]);
4318 path->nodes[0] = right;
4319 path->slots[0] = 0;
143bede5 4320 if (path->slots[1] == 0)
d6a0a126 4321 fixup_low_keys(root, path, &disk_key, 1);
d4dbff95 4322 }
5d4f98a2
YZ		 4323 btrfs_mark_buffer_dirty(right);
4324 return ret;
d4dbff95 4325 }
74123bd7 4326
143bede5 4327 copy_for_split(trans, root, path, l, right, slot, mid, nritems);
31840ae1 4328
5d4f98a2 4329 if (split == 2) {
cc0c5538
CM		 4330 BUG_ON(num_doubles != 0);
4331 num_doubles++;
4332 goto again;
a429e513 4333 }
44871b1b 4334
143bede5 4335 return 0;
99d8f83c
CM		 4336
4337push_for_double:
4338 push_for_double_split(trans, root, path, data_size);
4339 tried_avoid_double = 1;
4340 if (btrfs_leaf_free_space(root, path->nodes[0]) >= data_size)
4341 return 0;
4342 goto again;
be0e5c09
CM		 4343}
4344
ad48fd75
YZ		 4345static noinline int setup_leaf_for_split(struct btrfs_trans_handle *trans,
4346 struct btrfs_root *root,
4347 struct btrfs_path *path, int ins_len)
459931ec 4348{
ad48fd75 4349 struct btrfs_key key;
459931ec 4350 struct extent_buffer *leaf;
ad48fd75
YZ		 4351 struct btrfs_file_extent_item *fi;
4352 u64 extent_len = 0;
4353 u32 item_size;
4354 int ret;
459931ec
CM		 4355
4356 leaf = path->nodes[0];
ad48fd75
YZ		 4357 btrfs_item_key_to_cpu(leaf, &key, path->slots[0]);
4358
4359 BUG_ON(key.type != BTRFS_EXTENT_DATA_KEY &&
4360 key.type != BTRFS_EXTENT_CSUM_KEY);
4361
4362 if (btrfs_leaf_free_space(root, leaf) >= ins_len)
4363 return 0;
459931ec
CM		 4364
4365 item_size = btrfs_item_size_nr(leaf, path->slots[0]);
ad48fd75
YZ		 4366 if (key.type == BTRFS_EXTENT_DATA_KEY) {
4367 fi = btrfs_item_ptr(leaf, path->slots[0],
4368 struct btrfs_file_extent_item);
4369 extent_len = btrfs_file_extent_num_bytes(leaf, fi);
4370 }
b3b4aa74 4371 btrfs_release_path(path);
459931ec 4372
459931ec 4373 path->keep_locks = 1;
ad48fd75
YZ		 4374 path->search_for_split = 1;
4375 ret = btrfs_search_slot(trans, root, &key, path, 0, 1);
459931ec 4376 path->search_for_split = 0;
ad48fd75
YZ		 4377 if (ret < 0)
4378 goto err;
459931ec 4379
ad48fd75
YZ		 4380 ret = -EAGAIN;
4381 leaf = path->nodes[0];
459931ec 4382 /* if our item isn't there or got smaller, return now */
ad48fd75
YZ		 4383 if (ret > 0 || item_size != btrfs_item_size_nr(leaf, path->slots[0]))
4384 goto err;
4385
109f6aef
CM		 4386 /* the leaf has changed, it now has room. return now */
4387 if (btrfs_leaf_free_space(root, path->nodes[0]) >= ins_len)
4388 goto err;
4389
ad48fd75
YZ		 4390 if (key.type == BTRFS_EXTENT_DATA_KEY) {
4391 fi = btrfs_item_ptr(leaf, path->slots[0],
4392 struct btrfs_file_extent_item);
4393 if (extent_len != btrfs_file_extent_num_bytes(leaf, fi))
4394 goto err;
459931ec
CM		 4395 }
4396
b9473439 4397 btrfs_set_path_blocking(path);
ad48fd75 4398 ret = split_leaf(trans, root, &key, path, ins_len, 1);
f0486c68
YZ		 4399 if (ret)
4400 goto err;
459931ec 4401
ad48fd75 4402 path->keep_locks = 0;
b9473439 4403 btrfs_unlock_up_safe(path, 1);
ad48fd75
YZ		 4404 return 0;
4405err:
4406 path->keep_locks = 0;
4407 return ret;
4408}
4409
4410static noinline int split_item(struct btrfs_trans_handle *trans,
4411 struct btrfs_root *root,
4412 struct btrfs_path *path,
4413 struct btrfs_key *new_key,
4414 unsigned long split_offset)
4415{
4416 struct extent_buffer *leaf;
4417 struct btrfs_item *item;
4418 struct btrfs_item *new_item;
4419 int slot;
4420 char *buf;
4421 u32 nritems;
4422 u32 item_size;
4423 u32 orig_offset;
4424 struct btrfs_disk_key disk_key;
4425
b9473439
CM		 4426 leaf = path->nodes[0];
4427 BUG_ON(btrfs_leaf_free_space(root, leaf) < sizeof(struct btrfs_item));
4428
b4ce94de
CM		 4429 btrfs_set_path_blocking(path);
4430
dd3cc16b 4431 item = btrfs_item_nr(path->slots[0]);
459931ec
CM		 4432 orig_offset = btrfs_item_offset(leaf, item);
4433 item_size = btrfs_item_size(leaf, item);
4434
459931ec 4435 buf = kmalloc(item_size, GFP_NOFS);
ad48fd75
YZ		 4436 if (!buf)
4437 return -ENOMEM;
4438
459931ec
CM		 4439 read_extent_buffer(leaf, buf, btrfs_item_ptr_offset(leaf,
4440 path->slots[0]), item_size);
459931ec 4441
ad48fd75 4442 slot = path->slots[0] + 1;
459931ec 4443 nritems = btrfs_header_nritems(leaf);
459931ec
CM		 4444 if (slot != nritems) {
4445 /* shift the items */
4446 memmove_extent_buffer(leaf, btrfs_item_nr_offset(slot + 1),
ad48fd75
YZ		 4447 btrfs_item_nr_offset(slot),
4448 (nritems - slot) * sizeof(struct btrfs_item));
459931ec
CM		 4449 }
4450
4451 btrfs_cpu_key_to_disk(&disk_key, new_key);
4452 btrfs_set_item_key(leaf, &disk_key, slot);
4453
dd3cc16b 4454 new_item = btrfs_item_nr(slot);
459931ec
CM		 4455
4456 btrfs_set_item_offset(leaf, new_item, orig_offset);
4457 btrfs_set_item_size(leaf, new_item, item_size - split_offset);
4458
4459 btrfs_set_item_offset(leaf, item,
4460 orig_offset + item_size - split_offset);
4461 btrfs_set_item_size(leaf, item, split_offset);
4462
4463 btrfs_set_header_nritems(leaf, nritems + 1);
4464
4465 /* write the data for the start of the original item */
4466 write_extent_buffer(leaf, buf,
4467 btrfs_item_ptr_offset(leaf, path->slots[0]),
4468 split_offset);
4469
4470 /* write the data for the new item */
4471 write_extent_buffer(leaf, buf + split_offset,
4472 btrfs_item_ptr_offset(leaf, slot),
4473 item_size - split_offset);
4474 btrfs_mark_buffer_dirty(leaf);
4475
ad48fd75 4476 BUG_ON(btrfs_leaf_free_space(root, leaf) < 0);
459931ec 4477 kfree(buf);
ad48fd75
YZ		 4478 return 0;
4479}
4480
4481/*
4482 * This function splits a single item into two items,
4483 * giving 'new_key' to the new item and splitting the
4484 * old one at split_offset (from the start of the item).
4485 *
4486 * The path may be released by this operation. After
4487 * the split, the path is pointing to the old item. The
4488 * new item is going to be in the same node as the old one.
4489 *
4490 * Note, the item being split must be smaller enough to live alone on
4491 * a tree block with room for one extra struct btrfs_item
4492 *
4493 * This allows us to split the item in place, keeping a lock on the
4494 * leaf the entire time.
4495 */
4496int btrfs_split_item(struct btrfs_trans_handle *trans,
4497 struct btrfs_root *root,
4498 struct btrfs_path *path,
4499 struct btrfs_key *new_key,
4500 unsigned long split_offset)
4501{
4502 int ret;
4503 ret = setup_leaf_for_split(trans, root, path,
4504 sizeof(struct btrfs_item));
4505 if (ret)
4506 return ret;
4507
4508 ret = split_item(trans, root, path, new_key, split_offset);
459931ec
CM		 4509 return ret;
4510}
4511
ad48fd75
YZ		 4512/*
4513 * This function duplicate a item, giving 'new_key' to the new item.
4514 * It guarantees both items live in the same tree leaf and the new item
4515 * is contiguous with the original item.
4516 *
4517 * This allows us to split file extent in place, keeping a lock on the
4518 * leaf the entire time.
4519 */
4520int btrfs_duplicate_item(struct btrfs_trans_handle *trans,
4521 struct btrfs_root *root,
4522 struct btrfs_path *path,
4523 struct btrfs_key *new_key)
4524{
4525 struct extent_buffer *leaf;
4526 int ret;
4527 u32 item_size;
4528
4529 leaf = path->nodes[0];
4530 item_size = btrfs_item_size_nr(leaf, path->slots[0]);
4531 ret = setup_leaf_for_split(trans, root, path,
4532 item_size + sizeof(struct btrfs_item));
4533 if (ret)
4534 return ret;
4535
4536 path->slots[0]++;
afe5fea7 4537 setup_items_for_insert(root, path, new_key, &item_size,
143bede5
JM		 4538 item_size, item_size +
4539 sizeof(struct btrfs_item), 1);
ad48fd75
YZ		 4540 leaf = path->nodes[0];
4541 memcpy_extent_buffer(leaf,
4542 btrfs_item_ptr_offset(leaf, path->slots[0]),
4543 btrfs_item_ptr_offset(leaf, path->slots[0] - 1),
4544 item_size);
4545 return 0;
4546}
4547
d352ac68
CM		 4548/*
4549 * make the item pointed to by the path smaller. new_size indicates
4550 * how small to make it, and from_end tells us if we just chop bytes
4551 * off the end of the item or if we shift the item to chop bytes off
4552 * the front.
4553 */
afe5fea7 4554void btrfs_truncate_item(struct btrfs_root *root, struct btrfs_path *path,
143bede5 4555 u32 new_size, int from_end)
b18c6685 4556{
b18c6685 4557 int slot;
5f39d397
CM		 4558 struct extent_buffer *leaf;
4559 struct btrfs_item *item;
b18c6685
CM		 4560 u32 nritems;
4561 unsigned int data_end;
4562 unsigned int old_data_start;
4563 unsigned int old_size;
4564 unsigned int size_diff;
4565 int i;
cfed81a0
CM		 4566 struct btrfs_map_token token;
4567
4568 btrfs_init_map_token(&token);
b18c6685 4569
5f39d397 4570 leaf = path->nodes[0];
179e29e4
CM		 4571 slot = path->slots[0];
4572
4573 old_size = btrfs_item_size_nr(leaf, slot);
4574 if (old_size == new_size)
143bede5 4575 return;
b18c6685 4576
5f39d397 4577 nritems = btrfs_header_nritems(leaf);
b18c6685
CM		 4578 data_end = leaf_data_end(root, leaf);
4579
5f39d397 4580 old_data_start = btrfs_item_offset_nr(leaf, slot);
179e29e4 4581
b18c6685
CM		 4582 size_diff = old_size - new_size;
4583
4584 BUG_ON(slot < 0);
4585 BUG_ON(slot >= nritems);
4586
4587 /*
4588 * item0..itemN ... dataN.offset..dataN.size .. data0.size
4589 */
4590 /* first correct the data pointers */
4591 for (i = slot; i < nritems; i++) {
5f39d397 4592 u32 ioff;
dd3cc16b 4593 item = btrfs_item_nr(i);
db94535d 4594
cfed81a0
CM		 4595 ioff = btrfs_token_item_offset(leaf, item, &token);
4596 btrfs_set_token_item_offset(leaf, item,
4597 ioff + size_diff, &token);
b18c6685 4598 }
db94535d 4599
b18c6685 4600 /* shift the data */
179e29e4
CM		 4601 if (from_end) {
4602 memmove_extent_buffer(leaf, btrfs_leaf_data(leaf) +
4603 data_end + size_diff, btrfs_leaf_data(leaf) +
4604 data_end, old_data_start + new_size - data_end);
4605 } else {
4606 struct btrfs_disk_key disk_key;
4607 u64 offset;
4608
4609 btrfs_item_key(leaf, &disk_key, slot);
4610
4611 if (btrfs_disk_key_type(&disk_key) == BTRFS_EXTENT_DATA_KEY) {
4612 unsigned long ptr;
4613 struct btrfs_file_extent_item *fi;
4614
4615 fi = btrfs_item_ptr(leaf, slot,
4616 struct btrfs_file_extent_item);
4617 fi = (struct btrfs_file_extent_item *)(
4618 (unsigned long)fi - size_diff);
4619
4620 if (btrfs_file_extent_type(leaf, fi) ==
4621 BTRFS_FILE_EXTENT_INLINE) {
4622 ptr = btrfs_item_ptr_offset(leaf, slot);
4623 memmove_extent_buffer(leaf, ptr,
d397712b
CM		 4624 (unsigned long)fi,
4625 offsetof(struct btrfs_file_extent_item,
179e29e4
CM		 4626 disk_bytenr));
4627 }
4628 }
4629
4630 memmove_extent_buffer(leaf, btrfs_leaf_data(leaf) +
4631 data_end + size_diff, btrfs_leaf_data(leaf) +
4632 data_end, old_data_start - data_end);
4633
4634 offset = btrfs_disk_key_offset(&disk_key);
4635 btrfs_set_disk_key_offset(&disk_key, offset + size_diff);
4636 btrfs_set_item_key(leaf, &disk_key, slot);
4637 if (slot == 0)
d6a0a126 4638 fixup_low_keys(root, path, &disk_key, 1);
179e29e4 4639 }
5f39d397 4640
dd3cc16b 4641 item = btrfs_item_nr(slot);
5f39d397
CM		 4642 btrfs_set_item_size(leaf, item, new_size);
4643 btrfs_mark_buffer_dirty(leaf);
b18c6685 4644
5f39d397
CM		 4645 if (btrfs_leaf_free_space(root, leaf) < 0) {
4646 btrfs_print_leaf(root, leaf);
b18c6685 4647 BUG();
5f39d397 4648 }
b18c6685
CM		 4649}
4650
d352ac68 4651/*
8f69dbd2 4652 * make the item pointed to by the path bigger, data_size is the added size.
d352ac68 4653 */
4b90c680 4654void btrfs_extend_item(struct btrfs_root *root, struct btrfs_path *path,
143bede5 4655 u32 data_size)
6567e837 4656{
6567e837 4657 int slot;
5f39d397
CM		 4658 struct extent_buffer *leaf;
4659 struct btrfs_item *item;
6567e837
CM		 4660 u32 nritems;
4661 unsigned int data_end;
4662 unsigned int old_data;
4663 unsigned int old_size;
4664 int i;
cfed81a0
CM		 4665 struct btrfs_map_token token;
4666
4667 btrfs_init_map_token(&token);
6567e837 4668
5f39d397 4669 leaf = path->nodes[0];
6567e837 4670
5f39d397 4671 nritems = btrfs_header_nritems(leaf);
6567e837
CM		 4672 data_end = leaf_data_end(root, leaf);
4673
5f39d397
CM		 4674 if (btrfs_leaf_free_space(root, leaf) < data_size) {
4675 btrfs_print_leaf(root, leaf);
6567e837 4676 BUG();
5f39d397 4677 }
6567e837 4678 slot = path->slots[0];
5f39d397 4679 old_data = btrfs_item_end_nr(leaf, slot);
6567e837
CM		 4680
4681 BUG_ON(slot < 0);
3326d1b0
CM		 4682 if (slot >= nritems) {
4683 btrfs_print_leaf(root, leaf);
efe120a0 4684 btrfs_crit(root->fs_info, "slot %d too large, nritems %d",
d397712b 4685 slot, nritems);
3326d1b0
CM		 4686 BUG_ON(1);
4687 }
6567e837
CM		 4688
4689 /*
4690 * item0..itemN ... dataN.offset..dataN.size .. data0.size
4691 */
4692 /* first correct the data pointers */
4693 for (i = slot; i < nritems; i++) {
5f39d397 4694 u32 ioff;
dd3cc16b 4695 item = btrfs_item_nr(i);
db94535d 4696
cfed81a0
CM		 4697 ioff = btrfs_token_item_offset(leaf, item, &token);
4698 btrfs_set_token_item_offset(leaf, item,
4699 ioff - data_size, &token);
6567e837 4700 }
5f39d397 4701
6567e837 4702 /* shift the data */
5f39d397 4703 memmove_extent_buffer(leaf, btrfs_leaf_data(leaf) +
6567e837
CM		 4704 data_end - data_size, btrfs_leaf_data(leaf) +
4705 data_end, old_data - data_end);
5f39d397 4706
6567e837 4707 data_end = old_data;
5f39d397 4708 old_size = btrfs_item_size_nr(leaf, slot);
dd3cc16b 4709 item = btrfs_item_nr(slot);
5f39d397
CM		 4710 btrfs_set_item_size(leaf, item, old_size + data_size);
4711 btrfs_mark_buffer_dirty(leaf);
6567e837 4712
5f39d397
CM		 4713 if (btrfs_leaf_free_space(root, leaf) < 0) {
4714 btrfs_print_leaf(root, leaf);
6567e837 4715 BUG();
5f39d397 4716 }
6567e837
CM		 4717}
4718
74123bd7 4719/*
44871b1b
CM		 4720 * this is a helper for btrfs_insert_empty_items, the main goal here is
4721 * to save stack depth by doing the bulk of the work in a function
4722 * that doesn't call btrfs_search_slot
74123bd7 4723 */
afe5fea7 4724void setup_items_for_insert(struct btrfs_root *root, struct btrfs_path *path,
143bede5
JM		 4725 struct btrfs_key *cpu_key, u32 *data_size,
4726 u32 total_data, u32 total_size, int nr)
be0e5c09 4727{
5f39d397 4728 struct btrfs_item *item;
9c58309d 4729 int i;
7518a238 4730 u32 nritems;
be0e5c09 4731 unsigned int data_end;
e2fa7227 4732 struct btrfs_disk_key disk_key;
44871b1b
CM		 4733 struct extent_buffer *leaf;
4734 int slot;
cfed81a0
CM		 4735 struct btrfs_map_token token;
4736
4737 btrfs_init_map_token(&token);
e2fa7227 4738
5f39d397 4739 leaf = path->nodes[0];
44871b1b 4740 slot = path->slots[0];
74123bd7 4741
5f39d397 4742 nritems = btrfs_header_nritems(leaf);
123abc88 4743 data_end = leaf_data_end(root, leaf);
eb60ceac 4744
f25956cc 4745 if (btrfs_leaf_free_space(root, leaf) < total_size) {
3326d1b0 4746 btrfs_print_leaf(root, leaf);
efe120a0 4747 btrfs_crit(root->fs_info, "not enough freespace need %u have %d",
9c58309d 4748 total_size, btrfs_leaf_free_space(root, leaf));
be0e5c09 4749 BUG();
d4dbff95 4750 }
5f39d397 4751
be0e5c09 4752 if (slot != nritems) {
5f39d397 4753 unsigned int old_data = btrfs_item_end_nr(leaf, slot);
be0e5c09 4754
5f39d397
CM		 4755 if (old_data < data_end) {
4756 btrfs_print_leaf(root, leaf);
efe120a0 4757 btrfs_crit(root->fs_info, "slot %d old_data %d data_end %d",
5f39d397
CM		 4758 slot, old_data, data_end);
4759 BUG_ON(1);
4760 }
be0e5c09
CM		 4761 /*
4762 * item0..itemN ... dataN.offset..dataN.size .. data0.size
4763 */
4764 /* first correct the data pointers */
0783fcfc 4765 for (i = slot; i < nritems; i++) {
5f39d397 4766 u32 ioff;
db94535d 4767
dd3cc16b 4768 item = btrfs_item_nr( i);
cfed81a0
CM		 4769 ioff = btrfs_token_item_offset(leaf, item, &token);
4770 btrfs_set_token_item_offset(leaf, item,
4771 ioff - total_data, &token);
0783fcfc 4772 }
be0e5c09 4773 /* shift the items */
9c58309d 4774 memmove_extent_buffer(leaf, btrfs_item_nr_offset(slot + nr),
5f39d397 4775 btrfs_item_nr_offset(slot),
d6025579 4776 (nritems - slot) * sizeof(struct btrfs_item));
be0e5c09
CM		 4777
4778 /* shift the data */
5f39d397 4779 memmove_extent_buffer(leaf, btrfs_leaf_data(leaf) +
9c58309d 4780 data_end - total_data, btrfs_leaf_data(leaf) +
d6025579 4781 data_end, old_data - data_end);
be0e5c09
CM		 4782 data_end = old_data;
4783 }
5f39d397 4784
62e2749e 4785 /* setup the item for the new data */
9c58309d
CM		 4786 for (i = 0; i < nr; i++) {
4787 btrfs_cpu_key_to_disk(&disk_key, cpu_key + i);
4788 btrfs_set_item_key(leaf, &disk_key, slot + i);
dd3cc16b 4789 item = btrfs_item_nr(slot + i);
cfed81a0
CM		 4790 btrfs_set_token_item_offset(leaf, item,
4791 data_end - data_size[i], &token);
9c58309d 4792 data_end -= data_size[i];
cfed81a0 4793 btrfs_set_token_item_size(leaf, item, data_size[i], &token);
9c58309d 4794 }
44871b1b 4795
9c58309d 4796 btrfs_set_header_nritems(leaf, nritems + nr);
aa5d6bed 4797
5a01a2e3
CM		 4798 if (slot == 0) {
4799 btrfs_cpu_key_to_disk(&disk_key, cpu_key);
d6a0a126 4800 fixup_low_keys(root, path, &disk_key, 1);
5a01a2e3 4801 }
b9473439
CM		 4802 btrfs_unlock_up_safe(path, 1);
4803 btrfs_mark_buffer_dirty(leaf);
aa5d6bed 4804
5f39d397
CM		 4805 if (btrfs_leaf_free_space(root, leaf) < 0) {
4806 btrfs_print_leaf(root, leaf);
be0e5c09 4807 BUG();
5f39d397 4808 }
44871b1b
CM		 4809}
4810
4811/*
4812 * Given a key and some data, insert items into the tree.
4813 * This does all the path init required, making room in the tree if needed.
4814 */
4815int btrfs_insert_empty_items(struct btrfs_trans_handle *trans,
4816 struct btrfs_root *root,
4817 struct btrfs_path *path,
4818 struct btrfs_key *cpu_key, u32 *data_size,
4819 int nr)
4820{
44871b1b
CM		 4821 int ret = 0;
4822 int slot;
4823 int i;
4824 u32 total_size = 0;
4825 u32 total_data = 0;
4826
4827 for (i = 0; i < nr; i++)
4828 total_data += data_size[i];
4829
4830 total_size = total_data + (nr * sizeof(struct btrfs_item));
4831 ret = btrfs_search_slot(trans, root, cpu_key, path, total_size, 1);
4832 if (ret == 0)
4833 return -EEXIST;
4834 if (ret < 0)
143bede5 4835 return ret;
44871b1b 4836
44871b1b
CM		 4837 slot = path->slots[0];
4838 BUG_ON(slot < 0);
4839
afe5fea7 4840 setup_items_for_insert(root, path, cpu_key, data_size,
44871b1b 4841 total_data, total_size, nr);
143bede5 4842 return 0;
62e2749e
CM		 4843}
4844
4845/*
4846 * Given a key and some data, insert an item into the tree.
4847 * This does all the path init required, making room in the tree if needed.
4848 */
e089f05c
CM		 4849int btrfs_insert_item(struct btrfs_trans_handle *trans, struct btrfs_root
4850 *root, struct btrfs_key *cpu_key, void *data, u32
4851 data_size)
62e2749e
CM		 4852{
4853 int ret = 0;
2c90e5d6 4854 struct btrfs_path *path;
5f39d397
CM		 4855 struct extent_buffer *leaf;
4856 unsigned long ptr;
62e2749e 4857
2c90e5d6 4858 path = btrfs_alloc_path();
db5b493a
TI		 4859 if (!path)
4860 return -ENOMEM;
2c90e5d6 4861 ret = btrfs_insert_empty_item(trans, root, path, cpu_key, data_size);
62e2749e 4862 if (!ret) {
5f39d397
CM		 4863 leaf = path->nodes[0];
4864 ptr = btrfs_item_ptr_offset(leaf, path->slots[0]);
4865 write_extent_buffer(leaf, data, ptr, data_size);
4866 btrfs_mark_buffer_dirty(leaf);
62e2749e 4867 }
2c90e5d6 4868 btrfs_free_path(path);
aa5d6bed 4869 return ret;
be0e5c09
CM		 4870}
4871
74123bd7 4872/*
5de08d7d 4873 * delete the pointer from a given node.
74123bd7 4874 *
d352ac68
CM		 4875 * the tree should have been previously balanced so the deletion does not
4876 * empty a node.
74123bd7 4877 */
afe5fea7
TI		 4878static void del_ptr(struct btrfs_root *root, struct btrfs_path *path,
4879 int level, int slot)
be0e5c09 4880{
5f39d397 4881 struct extent_buffer *parent = path->nodes[level];
7518a238 4882 u32 nritems;
f3ea38da 4883 int ret;
be0e5c09 4884
5f39d397 4885 nritems = btrfs_header_nritems(parent);
d397712b 4886 if (slot != nritems - 1) {
0e411ece 4887 if (level)
f3ea38da
JS		 4888 tree_mod_log_eb_move(root->fs_info, parent, slot,
4889 slot + 1, nritems - slot - 1);
5f39d397
CM		 4890 memmove_extent_buffer(parent,
4891 btrfs_node_key_ptr_offset(slot),
4892 btrfs_node_key_ptr_offset(slot + 1),
d6025579
CM		 4893 sizeof(struct btrfs_key_ptr) *
4894 (nritems - slot - 1));
57ba86c0
CM		 4895 } else if (level) {
4896 ret = tree_mod_log_insert_key(root->fs_info, parent, slot,
c8cc6341 4897 MOD_LOG_KEY_REMOVE, GFP_NOFS);
57ba86c0 4898 BUG_ON(ret < 0);
bb803951 4899 }
f3ea38da 4900
7518a238 4901 nritems--;
5f39d397 4902 btrfs_set_header_nritems(parent, nritems);
7518a238 4903 if (nritems == 0 && parent == root->node) {
5f39d397 4904 BUG_ON(btrfs_header_level(root->node) != 1);
bb803951 4905 /* just turn the root into a leaf and break */
5f39d397 4906 btrfs_set_header_level(root->node, 0);
bb803951 4907 } else if (slot == 0) {
5f39d397
CM		 4908 struct btrfs_disk_key disk_key;
4909
4910 btrfs_node_key(parent, &disk_key, 0);
d6a0a126 4911 fixup_low_keys(root, path, &disk_key, level + 1);
be0e5c09 4912 }
d6025579 4913 btrfs_mark_buffer_dirty(parent);
be0e5c09
CM		 4914}
4915
323ac95b
CM		 4916/*
4917 * a helper function to delete the leaf pointed to by path->slots[1] and
5d4f98a2 4918 * path->nodes[1].
323ac95b
CM		 4919 *
4920 * This deletes the pointer in path->nodes[1] and frees the leaf
4921 * block extent. zero is returned if it all worked out, < 0 otherwise.
4922 *
4923 * The path must have already been setup for deleting the leaf, including
4924 * all the proper balancing. path->nodes[1] must be locked.
4925 */
143bede5
JM		 4926static noinline void btrfs_del_leaf(struct btrfs_trans_handle *trans,
4927 struct btrfs_root *root,
4928 struct btrfs_path *path,
4929 struct extent_buffer *leaf)
323ac95b 4930{
5d4f98a2 4931 WARN_ON(btrfs_header_generation(leaf) != trans->transid);
afe5fea7 4932 del_ptr(root, path, 1, path->slots[1]);
323ac95b 4933
4d081c41
CM		 4934 /*
4935 * btrfs_free_extent is expensive, we want to make sure we
4936 * aren't holding any locks when we call it
4937 */
4938 btrfs_unlock_up_safe(path, 0);
4939
f0486c68
YZ		 4940 root_sub_used(root, leaf->len);
4941
3083ee2e 4942 extent_buffer_get(leaf);
5581a51a 4943 btrfs_free_tree_block(trans, root, leaf, 0, 1);
3083ee2e 4944 free_extent_buffer_stale(leaf);
323ac95b 4945}
74123bd7
CM		 4946/*
4947 * delete the item at the leaf level in path. If that empties
4948 * the leaf, remove it from the tree
4949 */
85e21bac
CM		 4950int btrfs_del_items(struct btrfs_trans_handle *trans, struct btrfs_root *root,
4951 struct btrfs_path *path, int slot, int nr)
be0e5c09 4952{
5f39d397
CM		 4953 struct extent_buffer *leaf;
4954 struct btrfs_item *item;
85e21bac
CM		 4955 int last_off;
4956 int dsize = 0;
aa5d6bed
CM		 4957 int ret = 0;
4958 int wret;
85e21bac 4959 int i;
7518a238 4960 u32 nritems;
cfed81a0
CM		 4961 struct btrfs_map_token token;
4962
4963 btrfs_init_map_token(&token);
be0e5c09 4964
5f39d397 4965 leaf = path->nodes[0];
85e21bac
CM		 4966 last_off = btrfs_item_offset_nr(leaf, slot + nr - 1);
4967
4968 for (i = 0; i < nr; i++)
4969 dsize += btrfs_item_size_nr(leaf, slot + i);
4970
5f39d397 4971 nritems = btrfs_header_nritems(leaf);
be0e5c09 4972
85e21bac 4973 if (slot + nr != nritems) {
123abc88 4974 int data_end = leaf_data_end(root, leaf);
5f39d397
CM		 4975
4976 memmove_extent_buffer(leaf, btrfs_leaf_data(leaf) +
d6025579
CM		 4977 data_end + dsize,
4978 btrfs_leaf_data(leaf) + data_end,
85e21bac 4979 last_off - data_end);
5f39d397 4980
85e21bac 4981 for (i = slot + nr; i < nritems; i++) {
5f39d397 4982 u32 ioff;
db94535d 4983
dd3cc16b 4984 item = btrfs_item_nr(i);
cfed81a0
CM		 4985 ioff = btrfs_token_item_offset(leaf, item, &token);
4986 btrfs_set_token_item_offset(leaf, item,
4987 ioff + dsize, &token);
0783fcfc 4988 }
db94535d 4989
5f39d397 4990 memmove_extent_buffer(leaf, btrfs_item_nr_offset(slot),
85e21bac 4991 btrfs_item_nr_offset(slot + nr),
d6025579 4992 sizeof(struct btrfs_item) *
85e21bac 4993 (nritems - slot - nr));
be0e5c09 4994 }
85e21bac
CM		 4995 btrfs_set_header_nritems(leaf, nritems - nr);
4996 nritems -= nr;
5f39d397 4997
74123bd7 4998 /* delete the leaf if we've emptied it */
7518a238 4999 if (nritems == 0) {
5f39d397
CM		 5000 if (leaf == root->node) {
5001 btrfs_set_header_level(leaf, 0);
9a8dd150 5002 } else {
f0486c68
YZ		 5003 btrfs_set_path_blocking(path);
5004 clean_tree_block(trans, root, leaf);
143bede5 5005 btrfs_del_leaf(trans, root, path, leaf);
9a8dd150 5006 }
be0e5c09 5007 } else {
7518a238 5008 int used = leaf_space_used(leaf, 0, nritems);
aa5d6bed 5009 if (slot == 0) {
5f39d397
CM		 5010 struct btrfs_disk_key disk_key;
5011
5012 btrfs_item_key(leaf, &disk_key, 0);
d6a0a126 5013 fixup_low_keys(root, path, &disk_key, 1);
aa5d6bed 5014 }
aa5d6bed 5015
74123bd7 5016 /* delete the leaf if it is mostly empty */
d717aa1d 5017 if (used < BTRFS_LEAF_DATA_SIZE(root) / 3) {
be0e5c09
CM		 5018 /* push_leaf_left fixes the path.
5019 * make sure the path still points to our leaf
5020 * for possible call to del_ptr below
5021 */
4920c9ac 5022 slot = path->slots[1];
5f39d397
CM		 5023 extent_buffer_get(leaf);
5024
b9473439 5025 btrfs_set_path_blocking(path);
99d8f83c
CM		 5026 wret = push_leaf_left(trans, root, path, 1, 1,
5027 1, (u32)-1);
54aa1f4d 5028 if (wret < 0 && wret != -ENOSPC)
aa5d6bed 5029 ret = wret;
5f39d397
CM		 5030
5031 if (path->nodes[0] == leaf &&
5032 btrfs_header_nritems(leaf)) {
99d8f83c
CM		 5033 wret = push_leaf_right(trans, root, path, 1,
5034 1, 1, 0);
54aa1f4d 5035 if (wret < 0 && wret != -ENOSPC)
aa5d6bed
CM		 5036 ret = wret;
5037 }
5f39d397
CM		 5038
5039 if (btrfs_header_nritems(leaf) == 0) {
323ac95b 5040 path->slots[1] = slot;
143bede5 5041 btrfs_del_leaf(trans, root, path, leaf);
5f39d397 5042 free_extent_buffer(leaf);
143bede5 5043 ret = 0;
5de08d7d 5044 } else {
925baedd
CM		 5045 /* if we're still in the path, make sure
5046 * we're dirty. Otherwise, one of the
5047 * push_leaf functions must have already
5048 * dirtied this buffer
5049 */
5050 if (path->nodes[0] == leaf)
5051 btrfs_mark_buffer_dirty(leaf);
5f39d397 5052 free_extent_buffer(leaf);
be0e5c09 5053 }
d5719762 5054 } else {
5f39d397 5055 btrfs_mark_buffer_dirty(leaf);
be0e5c09
CM		 5056 }
5057 }
aa5d6bed 5058 return ret;
be0e5c09
CM		 5059}
5060
7bb86316 5061/*
925baedd 5062 * search the tree again to find a leaf with lesser keys
7bb86316
CM		 5063 * returns 0 if it found something or 1 if there are no lesser leaves.
5064 * returns < 0 on io errors.
d352ac68
CM		 5065 *
5066 * This may release the path, and so you may lose any locks held at the
5067 * time you call it.
7bb86316 5068 */
16e7549f 5069int btrfs_prev_leaf(struct btrfs_root *root, struct btrfs_path *path)
7bb86316 5070{
925baedd
CM		 5071 struct btrfs_key key;
5072 struct btrfs_disk_key found_key;
5073 int ret;
7bb86316 5074
925baedd 5075 btrfs_item_key_to_cpu(path->nodes[0], &key, 0);
7bb86316 5076
e8b0d724 5077 if (key.offset > 0) {
925baedd 5078 key.offset--;
e8b0d724 5079 } else if (key.type > 0) {
925baedd 5080 key.type--;
e8b0d724
FDBM		 5081 key.offset = (u64)-1;
5082 } else if (key.objectid > 0) {
925baedd 5083 key.objectid--;
e8b0d724
FDBM		 5084 key.type = (u8)-1;
5085 key.offset = (u64)-1;
5086 } else {
925baedd 5087 return 1;
e8b0d724 5088 }
7bb86316 5089
b3b4aa74 5090 btrfs_release_path(path);
925baedd
CM		 5091 ret = btrfs_search_slot(NULL, root, &key, path, 0, 0);
5092 if (ret < 0)
5093 return ret;
5094 btrfs_item_key(path->nodes[0], &found_key, 0);
5095 ret = comp_keys(&found_key, &key);
5096 if (ret < 0)
5097 return 0;
5098 return 1;
7bb86316
CM		 5099}
5100
3f157a2f
CM		 5101/*
5102 * A helper function to walk down the tree starting at min_key, and looking
de78b51a
ES		 5103 * for nodes or leaves that are have a minimum transaction id.
5104 * This is used by the btree defrag code, and tree logging
3f157a2f
CM		 5105 *
5106 * This does not cow, but it does stuff the starting key it finds back
5107 * into min_key, so you can call btrfs_search_slot with cow=1 on the
5108 * key and get a writable path.
5109 *
5110 * This does lock as it descends, and path->keep_locks should be set
5111 * to 1 by the caller.
5112 *
5113 * This honors path->lowest_level to prevent descent past a given level
5114 * of the tree.
5115 *
d352ac68
CM		 5116 * min_trans indicates the oldest transaction that you are interested
5117 * in walking through. Any nodes or leaves older than min_trans are
5118 * skipped over (without reading them).
5119 *
3f157a2f
CM		 5120 * returns zero if something useful was found, < 0 on error and 1 if there
5121 * was nothing in the tree that matched the search criteria.
5122 */
5123int btrfs_search_forward(struct btrfs_root *root, struct btrfs_key *min_key,
de78b51a 5124 struct btrfs_path *path,
3f157a2f
CM		 5125 u64 min_trans)
5126{
5127 struct extent_buffer *cur;
5128 struct btrfs_key found_key;
5129 int slot;
9652480b 5130 int sret;
3f157a2f
CM		 5131 u32 nritems;
5132 int level;
5133 int ret = 1;
5134
934d375b 5135 WARN_ON(!path->keep_locks);
3f157a2f 5136again:
bd681513 5137 cur = btrfs_read_lock_root_node(root);
3f157a2f 5138 level = btrfs_header_level(cur);
e02119d5 5139 WARN_ON(path->nodes[level]);
3f157a2f 5140 path->nodes[level] = cur;
bd681513 5141 path->locks[level] = BTRFS_READ_LOCK;
3f157a2f
CM		 5142
5143 if (btrfs_header_generation(cur) < min_trans) {
5144 ret = 1;
5145 goto out;
5146 }
d397712b 5147 while (1) {
3f157a2f
CM		 5148 nritems = btrfs_header_nritems(cur);
5149 level = btrfs_header_level(cur);
9652480b 5150 sret = bin_search(cur, min_key, level, &slot);
3f157a2f 5151
323ac95b
CM		 5152 /* at the lowest level, we're done, setup the path and exit */
5153 if (level == path->lowest_level) {
e02119d5
CM		 5154 if (slot >= nritems)
5155 goto find_next_key;
3f157a2f
CM		 5156 ret = 0;
5157 path->slots[level] = slot;
5158 btrfs_item_key_to_cpu(cur, &found_key, slot);
5159 goto out;
5160 }
9652480b
Y		 5161 if (sret && slot > 0)
5162 slot--;
3f157a2f 5163 /*
de78b51a
ES		 5164 * check this node pointer against the min_trans parameters.
5165 * If it is too old, old, skip to the next one.
3f157a2f 5166 */
d397712b 5167 while (slot < nritems) {
3f157a2f 5168 u64 gen;
e02119d5 5169
3f157a2f
CM		 5170 gen = btrfs_node_ptr_generation(cur, slot);
5171 if (gen < min_trans) {
5172 slot++;
5173 continue;
5174 }
de78b51a 5175 break;
3f157a2f 5176 }
e02119d5 5177find_next_key:
3f157a2f
CM		 5178 /*
5179 * we didn't find a candidate key in this node, walk forward
5180 * and find another one
5181 */
5182 if (slot >= nritems) {
e02119d5 5183 path->slots[level] = slot;
b4ce94de 5184 btrfs_set_path_blocking(path);
e02119d5 5185 sret = btrfs_find_next_key(root, path, min_key, level,
de78b51a 5186 min_trans);
e02119d5 5187 if (sret == 0) {
b3b4aa74 5188 btrfs_release_path(path);
3f157a2f
CM		 5189 goto again;
5190 } else {
5191 goto out;
5192 }
5193 }
5194 /* save our key for returning back */
5195 btrfs_node_key_to_cpu(cur, &found_key, slot);
5196 path->slots[level] = slot;
5197 if (level == path->lowest_level) {
5198 ret = 0;
f7c79f30 5199 unlock_up(path, level, 1, 0, NULL);
3f157a2f
CM		 5200 goto out;
5201 }
b4ce94de 5202 btrfs_set_path_blocking(path);
3f157a2f 5203 cur = read_node_slot(root, cur, slot);
79787eaa 5204 BUG_ON(!cur); /* -ENOMEM */
3f157a2f 5205
bd681513 5206 btrfs_tree_read_lock(cur);
b4ce94de 5207
bd681513 5208 path->locks[level - 1] = BTRFS_READ_LOCK;
3f157a2f 5209 path->nodes[level - 1] = cur;
f7c79f30 5210 unlock_up(path, level, 1, 0, NULL);
bd681513 5211 btrfs_clear_path_blocking(path, NULL, 0);
3f157a2f
CM		 5212 }
5213out:
5214 if (ret == 0)
5215 memcpy(min_key, &found_key, sizeof(found_key));
b4ce94de 5216 btrfs_set_path_blocking(path);
3f157a2f
CM		 5217 return ret;
5218}
5219
7069830a
AB		 5220static void tree_move_down(struct btrfs_root *root,
5221 struct btrfs_path *path,
5222 int *level, int root_level)
5223{
74dd17fb 5224 BUG_ON(*level == 0);
7069830a
AB		 5225 path->nodes[*level - 1] = read_node_slot(root, path->nodes[*level],
5226 path->slots[*level]);
5227 path->slots[*level - 1] = 0;
5228 (*level)--;
5229}
5230
5231static int tree_move_next_or_upnext(struct btrfs_root *root,
5232 struct btrfs_path *path,
5233 int *level, int root_level)
5234{
5235 int ret = 0;
5236 int nritems;
5237 nritems = btrfs_header_nritems(path->nodes[*level]);
5238
5239 path->slots[*level]++;
5240
74dd17fb 5241 while (path->slots[*level] >= nritems) {
7069830a
AB		 5242 if (*level == root_level)
5243 return -1;
5244
5245 /* move upnext */
5246 path->slots[*level] = 0;
5247 free_extent_buffer(path->nodes[*level]);
5248 path->nodes[*level] = NULL;
5249 (*level)++;
5250 path->slots[*level]++;
5251
5252 nritems = btrfs_header_nritems(path->nodes[*level]);
5253 ret = 1;
5254 }
5255 return ret;
5256}
5257
5258/*
5259 * Returns 1 if it had to move up and next. 0 is returned if it moved only next
5260 * or down.
5261 */
5262static int tree_advance(struct btrfs_root *root,
5263 struct btrfs_path *path,
5264 int *level, int root_level,
5265 int allow_down,
5266 struct btrfs_key *key)
5267{
5268 int ret;
5269
5270 if (*level == 0 || !allow_down) {
5271 ret = tree_move_next_or_upnext(root, path, level, root_level);
5272 } else {
5273 tree_move_down(root, path, level, root_level);
5274 ret = 0;
5275 }
5276 if (ret >= 0) {
5277 if (*level == 0)
5278 btrfs_item_key_to_cpu(path->nodes[*level], key,
5279 path->slots[*level]);
5280 else
5281 btrfs_node_key_to_cpu(path->nodes[*level], key,
5282 path->slots[*level]);
5283 }
5284 return ret;
5285}
5286
5287static int tree_compare_item(struct btrfs_root *left_root,
5288 struct btrfs_path *left_path,
5289 struct btrfs_path *right_path,
5290 char *tmp_buf)
5291{
5292 int cmp;
5293 int len1, len2;
5294 unsigned long off1, off2;
5295
5296 len1 = btrfs_item_size_nr(left_path->nodes[0], left_path->slots[0]);
5297 len2 = btrfs_item_size_nr(right_path->nodes[0], right_path->slots[0]);
5298 if (len1 != len2)
5299 return 1;
5300
5301 off1 = btrfs_item_ptr_offset(left_path->nodes[0], left_path->slots[0]);
5302 off2 = btrfs_item_ptr_offset(right_path->nodes[0],
5303 right_path->slots[0]);
5304
5305 read_extent_buffer(left_path->nodes[0], tmp_buf, off1, len1);
5306
5307 cmp = memcmp_extent_buffer(right_path->nodes[0], tmp_buf, off2, len1);
5308 if (cmp)
5309 return 1;
5310 return 0;
5311}
5312
5313#define ADVANCE 1
5314#define ADVANCE_ONLY_NEXT -1
5315
5316/*
5317 * This function compares two trees and calls the provided callback for
5318 * every changed/new/deleted item it finds.
5319 * If shared tree blocks are encountered, whole subtrees are skipped, making
5320 * the compare pretty fast on snapshotted subvolumes.
5321 *
5322 * This currently works on commit roots only. As commit roots are read only,
5323 * we don't do any locking. The commit roots are protected with transactions.
5324 * Transactions are ended and rejoined when a commit is tried in between.
5325 *
5326 * This function checks for modifications done to the trees while comparing.
5327 * If it detects a change, it aborts immediately.
5328 */
5329int btrfs_compare_trees(struct btrfs_root *left_root,
5330 struct btrfs_root *right_root,
5331 btrfs_changed_cb_t changed_cb, void *ctx)
5332{
5333 int ret;
5334 int cmp;
7069830a
AB		 5335 struct btrfs_path *left_path = NULL;
5336 struct btrfs_path *right_path = NULL;
5337 struct btrfs_key left_key;
5338 struct btrfs_key right_key;
5339 char *tmp_buf = NULL;
5340 int left_root_level;
5341 int right_root_level;
5342 int left_level;
5343 int right_level;
5344 int left_end_reached;
5345 int right_end_reached;
5346 int advance_left;
5347 int advance_right;
5348 u64 left_blockptr;
5349 u64 right_blockptr;
6baa4293
FM		 5350 u64 left_gen;
5351 u64 right_gen;
7069830a
AB		 5352
5353 left_path = btrfs_alloc_path();
5354 if (!left_path) {
5355 ret = -ENOMEM;
5356 goto out;
5357 }
5358 right_path = btrfs_alloc_path();
5359 if (!right_path) {
5360 ret = -ENOMEM;
5361 goto out;
5362 }
5363
5364 tmp_buf = kmalloc(left_root->leafsize, GFP_NOFS);
5365 if (!tmp_buf) {
5366 ret = -ENOMEM;
5367 goto out;
5368 }
5369
5370 left_path->search_commit_root = 1;
5371 left_path->skip_locking = 1;
5372 right_path->search_commit_root = 1;
5373 right_path->skip_locking = 1;
5374
7069830a
AB		 5375 /*
5376 * Strategy: Go to the first items of both trees. Then do
5377 *
5378 * If both trees are at level 0
5379 * Compare keys of current items
5380 * If left < right treat left item as new, advance left tree
5381 * and repeat
5382 * If left > right treat right item as deleted, advance right tree
5383 * and repeat
5384 * If left == right do deep compare of items, treat as changed if
5385 * needed, advance both trees and repeat
5386 * If both trees are at the same level but not at level 0
5387 * Compare keys of current nodes/leafs
5388 * If left < right advance left tree and repeat
5389 * If left > right advance right tree and repeat
5390 * If left == right compare blockptrs of the next nodes/leafs
5391 * If they match advance both trees but stay at the same level
5392 * and repeat
5393 * If they don't match advance both trees while allowing to go
5394 * deeper and repeat
5395 * If tree levels are different
5396 * Advance the tree that needs it and repeat
5397 *
5398 * Advancing a tree means:
5399 * If we are at level 0, try to go to the next slot. If that's not
5400 * possible, go one level up and repeat. Stop when we found a level
5401 * where we could go to the next slot. We may at this point be on a
5402 * node or a leaf.
5403 *
5404 * If we are not at level 0 and not on shared tree blocks, go one
5405 * level deeper.
5406 *
5407 * If we are not at level 0 and on shared tree blocks, go one slot to
5408 * the right if possible or go up and right.
5409 */
5410
3f8a18cc 5411 down_read(&left_root->fs_info->commit_root_sem);
7069830a
AB		 5412 left_level = btrfs_header_level(left_root->commit_root);
5413 left_root_level = left_level;
5414 left_path->nodes[left_level] = left_root->commit_root;
5415 extent_buffer_get(left_path->nodes[left_level]);
5416
5417 right_level = btrfs_header_level(right_root->commit_root);
5418 right_root_level = right_level;
5419 right_path->nodes[right_level] = right_root->commit_root;
5420 extent_buffer_get(right_path->nodes[right_level]);
3f8a18cc 5421 up_read(&left_root->fs_info->commit_root_sem);
7069830a
AB		 5422
5423 if (left_level == 0)
5424 btrfs_item_key_to_cpu(left_path->nodes[left_level],
5425 &left_key, left_path->slots[left_level]);
5426 else
5427 btrfs_node_key_to_cpu(left_path->nodes[left_level],
5428 &left_key, left_path->slots[left_level]);
5429 if (right_level == 0)
5430 btrfs_item_key_to_cpu(right_path->nodes[right_level],
5431 &right_key, right_path->slots[right_level]);
5432 else
5433 btrfs_node_key_to_cpu(right_path->nodes[right_level],
5434 &right_key, right_path->slots[right_level]);
5435
5436 left_end_reached = right_end_reached = 0;
5437 advance_left = advance_right = 0;
5438
5439 while (1) {
7069830a
AB		 5440 if (advance_left && !left_end_reached) {
5441 ret = tree_advance(left_root, left_path, &left_level,
5442 left_root_level,
5443 advance_left != ADVANCE_ONLY_NEXT,
5444 &left_key);
5445 if (ret < 0)
5446 left_end_reached = ADVANCE;
5447 advance_left = 0;
5448 }
5449 if (advance_right && !right_end_reached) {
5450 ret = tree_advance(right_root, right_path, &right_level,
5451 right_root_level,
5452 advance_right != ADVANCE_ONLY_NEXT,
5453 &right_key);
5454 if (ret < 0)
5455 right_end_reached = ADVANCE;
5456 advance_right = 0;
5457 }
5458
5459 if (left_end_reached && right_end_reached) {
5460 ret = 0;
5461 goto out;
5462 } else if (left_end_reached) {
5463 if (right_level == 0) {
5464 ret = changed_cb(left_root, right_root,
5465 left_path, right_path,
5466 &right_key,
5467 BTRFS_COMPARE_TREE_DELETED,
5468 ctx);
5469 if (ret < 0)
5470 goto out;
5471 }
5472 advance_right = ADVANCE;
5473 continue;
5474 } else if (right_end_reached) {
5475 if (left_level == 0) {
5476 ret = changed_cb(left_root, right_root,
5477 left_path, right_path,
5478 &left_key,
5479 BTRFS_COMPARE_TREE_NEW,
5480 ctx);
5481 if (ret < 0)
5482 goto out;
5483 }
5484 advance_left = ADVANCE;
5485 continue;
5486 }
5487
5488 if (left_level == 0 && right_level == 0) {
5489 cmp = btrfs_comp_cpu_keys(&left_key, &right_key);
5490 if (cmp < 0) {
5491 ret = changed_cb(left_root, right_root,
5492 left_path, right_path,
5493 &left_key,
5494 BTRFS_COMPARE_TREE_NEW,
5495 ctx);
5496 if (ret < 0)
5497 goto out;
5498 advance_left = ADVANCE;
5499 } else if (cmp > 0) {
5500 ret = changed_cb(left_root, right_root,
5501 left_path, right_path,
5502 &right_key,
5503 BTRFS_COMPARE_TREE_DELETED,
5504 ctx);
5505 if (ret < 0)
5506 goto out;
5507 advance_right = ADVANCE;
5508 } else {
ba5e8f2e
JB		 5509 enum btrfs_compare_tree_result cmp;
5510
74dd17fb 5511 WARN_ON(!extent_buffer_uptodate(left_path->nodes[0]));
7069830a
AB		 5512 ret = tree_compare_item(left_root, left_path,
5513 right_path, tmp_buf);
ba5e8f2e
JB		 5514 if (ret)
5515 cmp = BTRFS_COMPARE_TREE_CHANGED;
5516 else
5517 cmp = BTRFS_COMPARE_TREE_SAME;
5518 ret = changed_cb(left_root, right_root,
5519 left_path, right_path,
5520 &left_key, cmp, ctx);
5521 if (ret < 0)
5522 goto out;
7069830a
AB		 5523 advance_left = ADVANCE;
5524 advance_right = ADVANCE;
5525 }
5526 } else if (left_level == right_level) {
5527 cmp = btrfs_comp_cpu_keys(&left_key, &right_key);
5528 if (cmp < 0) {
5529 advance_left = ADVANCE;
5530 } else if (cmp > 0) {
5531 advance_right = ADVANCE;
5532 } else {
5533 left_blockptr = btrfs_node_blockptr(
5534 left_path->nodes[left_level],
5535 left_path->slots[left_level]);
5536 right_blockptr = btrfs_node_blockptr(
5537 right_path->nodes[right_level],
5538 right_path->slots[right_level]);
6baa4293
FM		 5539 left_gen = btrfs_node_ptr_generation(
5540 left_path->nodes[left_level],
5541 left_path->slots[left_level]);
5542 right_gen = btrfs_node_ptr_generation(
5543 right_path->nodes[right_level],
5544 right_path->slots[right_level]);
5545 if (left_blockptr == right_blockptr &&
5546 left_gen == right_gen) {
7069830a
AB		 5547 /*
5548 * As we're on a shared block, don't
5549 * allow to go deeper.
5550 */
5551 advance_left = ADVANCE_ONLY_NEXT;
5552 advance_right = ADVANCE_ONLY_NEXT;
5553 } else {
5554 advance_left = ADVANCE;
5555 advance_right = ADVANCE;
5556 }
5557 }
5558 } else if (left_level < right_level) {
5559 advance_right = ADVANCE;
5560 } else {
5561 advance_left = ADVANCE;
5562 }
5563 }
5564
5565out:
5566 btrfs_free_path(left_path);
5567 btrfs_free_path(right_path);
5568 kfree(tmp_buf);
7069830a
AB		 5569 return ret;
5570}
5571
3f157a2f
CM		 5572/*
5573 * this is similar to btrfs_next_leaf, but does not try to preserve
5574 * and fixup the path. It looks for and returns the next key in the
de78b51a 5575 * tree based on the current path and the min_trans parameters.
3f157a2f
CM		 5576 *
5577 * 0 is returned if another key is found, < 0 if there are any errors
5578 * and 1 is returned if there are no higher keys in the tree
5579 *
5580 * path->keep_locks should be set to 1 on the search made before
5581 * calling this function.
5582 */
e7a84565 5583int btrfs_find_next_key(struct btrfs_root *root, struct btrfs_path *path,
de78b51a 5584 struct btrfs_key *key, int level, u64 min_trans)
e7a84565 5585{
e7a84565
CM		 5586 int slot;
5587 struct extent_buffer *c;
5588
934d375b 5589 WARN_ON(!path->keep_locks);
d397712b 5590 while (level < BTRFS_MAX_LEVEL) {
e7a84565
CM		 5591 if (!path->nodes[level])
5592 return 1;
5593
5594 slot = path->slots[level] + 1;
5595 c = path->nodes[level];
3f157a2f 5596next:
e7a84565 5597 if (slot >= btrfs_header_nritems(c)) {
33c66f43
YZ		 5598 int ret;
5599 int orig_lowest;
5600 struct btrfs_key cur_key;
5601 if (level + 1 >= BTRFS_MAX_LEVEL ||
5602 !path->nodes[level + 1])
e7a84565 5603 return 1;
33c66f43
YZ		 5604
5605 if (path->locks[level + 1]) {
5606 level++;
5607 continue;
5608 }
5609
5610 slot = btrfs_header_nritems(c) - 1;
5611 if (level == 0)
5612 btrfs_item_key_to_cpu(c, &cur_key, slot);
5613 else
5614 btrfs_node_key_to_cpu(c, &cur_key, slot);
5615
5616 orig_lowest = path->lowest_level;
b3b4aa74 5617 btrfs_release_path(path);
33c66f43
YZ		 5618 path->lowest_level = level;
5619 ret = btrfs_search_slot(NULL, root, &cur_key, path,
5620 0, 0);
5621 path->lowest_level = orig_lowest;
5622 if (ret < 0)
5623 return ret;
5624
5625 c = path->nodes[level];
5626 slot = path->slots[level];
5627 if (ret == 0)
5628 slot++;
5629 goto next;
e7a84565 5630 }
33c66f43 5631
e7a84565
CM		 5632 if (level == 0)
5633 btrfs_item_key_to_cpu(c, key, slot);
3f157a2f 5634 else {
3f157a2f
CM		 5635 u64 gen = btrfs_node_ptr_generation(c, slot);
5636
3f157a2f
CM		 5637 if (gen < min_trans) {
5638 slot++;
5639 goto next;
5640 }
e7a84565 5641 btrfs_node_key_to_cpu(c, key, slot);
3f157a2f 5642 }
e7a84565
CM		 5643 return 0;
5644 }
5645 return 1;
5646}
5647
97571fd0 5648/*
925baedd 5649 * search the tree again to find a leaf with greater keys
0f70abe2
CM		 5650 * returns 0 if it found something or 1 if there are no greater leaves.
5651 * returns < 0 on io errors.
97571fd0 5652 */
234b63a0 5653int btrfs_next_leaf(struct btrfs_root *root, struct btrfs_path *path)
3d7806ec
JS		 5654{
5655 return btrfs_next_old_leaf(root, path, 0);
5656}
5657
5658int btrfs_next_old_leaf(struct btrfs_root *root, struct btrfs_path *path,
5659 u64 time_seq)
d97e63b6
CM		 5660{
5661 int slot;
8e73f275 5662 int level;
5f39d397 5663 struct extent_buffer *c;
8e73f275 5664 struct extent_buffer *next;
925baedd
CM		 5665 struct btrfs_key key;
5666 u32 nritems;
5667 int ret;
8e73f275 5668 int old_spinning = path->leave_spinning;
bd681513 5669 int next_rw_lock = 0;
925baedd
CM		 5670
5671 nritems = btrfs_header_nritems(path->nodes[0]);
d397712b 5672 if (nritems == 0)
925baedd 5673 return 1;
925baedd 5674
8e73f275
CM		 5675 btrfs_item_key_to_cpu(path->nodes[0], &key, nritems - 1);
5676again:
5677 level = 1;
5678 next = NULL;
bd681513 5679 next_rw_lock = 0;
b3b4aa74 5680 btrfs_release_path(path);
8e73f275 5681
a2135011 5682 path->keep_locks = 1;
31533fb2 5683 path->leave_spinning = 1;
8e73f275 5684
3d7806ec
JS		 5685 if (time_seq)
5686 ret = btrfs_search_old_slot(root, &key, path, time_seq);
5687 else
5688 ret = btrfs_search_slot(NULL, root, &key, path, 0, 0);
925baedd
CM		 5689 path->keep_locks = 0;
5690
5691 if (ret < 0)
5692 return ret;
5693
a2135011 5694 nritems = btrfs_header_nritems(path->nodes[0]);
168fd7d2
CM		 5695 /*
5696 * by releasing the path above we dropped all our locks. A balance
5697 * could have added more items next to the key that used to be
5698 * at the very end of the block. So, check again here and
5699 * advance the path if there are now more items available.
5700 */
a2135011 5701 if (nritems > 0 && path->slots[0] < nritems - 1) {
e457afec
YZ		 5702 if (ret == 0)
5703 path->slots[0]++;
8e73f275 5704 ret = 0;
925baedd
CM		 5705 goto done;
5706 }
d97e63b6 5707
d397712b 5708 while (level < BTRFS_MAX_LEVEL) {
8e73f275
CM		 5709 if (!path->nodes[level]) {
5710 ret = 1;
5711 goto done;
5712 }
5f39d397 5713
d97e63b6
CM		 5714 slot = path->slots[level] + 1;
5715 c = path->nodes[level];
5f39d397 5716 if (slot >= btrfs_header_nritems(c)) {
d97e63b6 5717 level++;
8e73f275
CM		 5718 if (level == BTRFS_MAX_LEVEL) {
5719 ret = 1;
5720 goto done;
5721 }
d97e63b6
CM		 5722 continue;
5723 }
5f39d397 5724
925baedd 5725 if (next) {
bd681513 5726 btrfs_tree_unlock_rw(next, next_rw_lock);
5f39d397 5727 free_extent_buffer(next);
925baedd 5728 }
5f39d397 5729
8e73f275 5730 next = c;
bd681513 5731 next_rw_lock = path->locks[level];
8e73f275 5732 ret = read_block_for_search(NULL, root, path, &next, level,
5d9e75c4 5733 slot, &key, 0);
8e73f275
CM		 5734 if (ret == -EAGAIN)
5735 goto again;
5f39d397 5736
76a05b35 5737 if (ret < 0) {
b3b4aa74 5738 btrfs_release_path(path);
76a05b35
CM		 5739 goto done;
5740 }
5741
5cd57b2c 5742 if (!path->skip_locking) {
bd681513 5743 ret = btrfs_try_tree_read_lock(next);
d42244a0
JS		 5744 if (!ret && time_seq) {
5745 /*
5746 * If we don't get the lock, we may be racing
5747 * with push_leaf_left, holding that lock while
5748 * itself waiting for the leaf we've currently
5749 * locked. To solve this situation, we give up
5750 * on our lock and cycle.
5751 */
cf538830 5752 free_extent_buffer(next);
d42244a0
JS		 5753 btrfs_release_path(path);
5754 cond_resched();
5755 goto again;
5756 }
8e73f275
CM		 5757 if (!ret) {
5758 btrfs_set_path_blocking(path);
bd681513 5759 btrfs_tree_read_lock(next);
31533fb2 5760 btrfs_clear_path_blocking(path, next,
bd681513 5761 BTRFS_READ_LOCK);
8e73f275 5762 }
31533fb2 5763 next_rw_lock = BTRFS_READ_LOCK;
5cd57b2c 5764 }
d97e63b6
CM		 5765 break;
5766 }
5767 path->slots[level] = slot;
d397712b 5768 while (1) {
d97e63b6
CM		 5769 level--;
5770 c = path->nodes[level];
925baedd 5771 if (path->locks[level])
bd681513 5772 btrfs_tree_unlock_rw(c, path->locks[level]);
8e73f275 5773
5f39d397 5774 free_extent_buffer(c);
d97e63b6
CM		 5775 path->nodes[level] = next;
5776 path->slots[level] = 0;
a74a4b97 5777 if (!path->skip_locking)
bd681513 5778 path->locks[level] = next_rw_lock;
d97e63b6
CM		 5779 if (!level)
5780 break;
b4ce94de 5781
8e73f275 5782 ret = read_block_for_search(NULL, root, path, &next, level,
5d9e75c4 5783 0, &key, 0);
8e73f275
CM		 5784 if (ret == -EAGAIN)
5785 goto again;
5786
76a05b35 5787 if (ret < 0) {
b3b4aa74 5788 btrfs_release_path(path);
76a05b35
CM		 5789 goto done;
5790 }
5791
5cd57b2c 5792 if (!path->skip_locking) {
bd681513 5793 ret = btrfs_try_tree_read_lock(next);
8e73f275
CM		 5794 if (!ret) {
5795 btrfs_set_path_blocking(path);
bd681513 5796 btrfs_tree_read_lock(next);
31533fb2 5797 btrfs_clear_path_blocking(path, next,
bd681513
CM		 5798 BTRFS_READ_LOCK);
5799 }
31533fb2 5800 next_rw_lock = BTRFS_READ_LOCK;
5cd57b2c 5801 }
d97e63b6 5802 }
8e73f275 5803 ret = 0;
925baedd 5804done:
f7c79f30 5805 unlock_up(path, 0, 1, 0, NULL);
8e73f275
CM		 5806 path->leave_spinning = old_spinning;
5807 if (!old_spinning)
5808 btrfs_set_path_blocking(path);
5809
5810 return ret;
d97e63b6 5811}
0b86a832 5812
3f157a2f
CM		 5813/*
5814 * this uses btrfs_prev_leaf to walk backwards in the tree, and keeps
5815 * searching until it gets past min_objectid or finds an item of 'type'
5816 *
5817 * returns 0 if something is found, 1 if nothing was found and < 0 on error
5818 */
0b86a832
CM		 5819int btrfs_previous_item(struct btrfs_root *root,
5820 struct btrfs_path *path, u64 min_objectid,
5821 int type)
5822{
5823 struct btrfs_key found_key;
5824 struct extent_buffer *leaf;
e02119d5 5825 u32 nritems;
0b86a832
CM		 5826 int ret;
5827
d397712b 5828 while (1) {
0b86a832 5829 if (path->slots[0] == 0) {
b4ce94de 5830 btrfs_set_path_blocking(path);
0b86a832
CM		 5831 ret = btrfs_prev_leaf(root, path);
5832 if (ret != 0)
5833 return ret;
5834 } else {
5835 path->slots[0]--;
5836 }
5837 leaf = path->nodes[0];
e02119d5
CM		 5838 nritems = btrfs_header_nritems(leaf);
5839 if (nritems == 0)
5840 return 1;
5841 if (path->slots[0] == nritems)
5842 path->slots[0]--;
5843
0b86a832 5844 btrfs_item_key_to_cpu(leaf, &found_key, path->slots[0]);
e02119d5
CM		 5845 if (found_key.objectid < min_objectid)
5846 break;
0a4eefbb
YZ		 5847 if (found_key.type == type)
5848 return 0;
e02119d5
CM		 5849 if (found_key.objectid == min_objectid &&
5850 found_key.type < type)
5851 break;
0b86a832
CM		 5852 }
5853 return 1;
5854}
ade2e0b3
WS		 5855
5856/*
5857 * search in extent tree to find a previous Metadata/Data extent item with
5858 * min objecitd.
5859 *
5860 * returns 0 if something is found, 1 if nothing was found and < 0 on error
5861 */
5862int btrfs_previous_extent_item(struct btrfs_root *root,
5863 struct btrfs_path *path, u64 min_objectid)
5864{
5865 struct btrfs_key found_key;
5866 struct extent_buffer *leaf;
5867 u32 nritems;
5868 int ret;
5869
5870 while (1) {
5871 if (path->slots[0] == 0) {
5872 btrfs_set_path_blocking(path);
5873 ret = btrfs_prev_leaf(root, path);
5874 if (ret != 0)
5875 return ret;
5876 } else {
5877 path->slots[0]--;
5878 }
5879 leaf = path->nodes[0];
5880 nritems = btrfs_header_nritems(leaf);
5881 if (nritems == 0)
5882 return 1;
5883 if (path->slots[0] == nritems)
5884 path->slots[0]--;
5885
5886 btrfs_item_key_to_cpu(leaf, &found_key, path->slots[0]);
5887 if (found_key.objectid < min_objectid)
5888 break;
5889 if (found_key.type == BTRFS_EXTENT_ITEM_KEY ||
5890 found_key.type == BTRFS_METADATA_ITEM_KEY)
5891 return 0;
5892 if (found_key.objectid == min_objectid &&
5893 found_key.type < BTRFS_EXTENT_ITEM_KEY)
5894 break;
5895 }
5896 return 1;
5897}
Linux kernel - Deliverables
This page took 0.685356 seconds and 5 git commands to generate.