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