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