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