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