1
2
3
4
5
6#include <linux/sched.h>
7#include <linux/slab.h>
8#include <linux/rbtree.h>
9#include <linux/mm.h>
10#include "ctree.h"
11#include "disk-io.h"
12#include "transaction.h"
13#include "print-tree.h"
14#include "locking.h"
15#include "volumes.h"
16#include "qgroup.h"
17#include "tree-mod-log.h"
18
19static int split_node(struct btrfs_trans_handle *trans, struct btrfs_root
20 *root, struct btrfs_path *path, int level);
21static int split_leaf(struct btrfs_trans_handle *trans, struct btrfs_root *root,
22 const struct btrfs_key *ins_key, struct btrfs_path *path,
23 int data_size, int extend);
24static int push_node_left(struct btrfs_trans_handle *trans,
25 struct extent_buffer *dst,
26 struct extent_buffer *src, int empty);
27static int balance_node_right(struct btrfs_trans_handle *trans,
28 struct extent_buffer *dst_buf,
29 struct extent_buffer *src_buf);
30static void del_ptr(struct btrfs_root *root, struct btrfs_path *path,
31 int level, int slot);
32
33static const struct btrfs_csums {
34 u16 size;
35 const char name[10];
36 const char driver[12];
37} btrfs_csums[] = {
38 [BTRFS_CSUM_TYPE_CRC32] = { .size = 4, .name = "crc32c" },
39 [BTRFS_CSUM_TYPE_XXHASH] = { .size = 8, .name = "xxhash64" },
40 [BTRFS_CSUM_TYPE_SHA256] = { .size = 32, .name = "sha256" },
41 [BTRFS_CSUM_TYPE_BLAKE2] = { .size = 32, .name = "blake2b",
42 .driver = "blake2b-256" },
43};
44
45int btrfs_super_csum_size(const struct btrfs_super_block *s)
46{
47 u16 t = btrfs_super_csum_type(s);
48
49
50
51 return btrfs_csums[t].size;
52}
53
54const char *btrfs_super_csum_name(u16 csum_type)
55{
56
57 return btrfs_csums[csum_type].name;
58}
59
60
61
62
63
64const char *btrfs_super_csum_driver(u16 csum_type)
65{
66
67 return btrfs_csums[csum_type].driver[0] ?
68 btrfs_csums[csum_type].driver :
69 btrfs_csums[csum_type].name;
70}
71
72size_t __attribute_const__ btrfs_get_num_csums(void)
73{
74 return ARRAY_SIZE(btrfs_csums);
75}
76
77struct btrfs_path *btrfs_alloc_path(void)
78{
79 return kmem_cache_zalloc(btrfs_path_cachep, GFP_NOFS);
80}
81
82
83void btrfs_free_path(struct btrfs_path *p)
84{
85 if (!p)
86 return;
87 btrfs_release_path(p);
88 kmem_cache_free(btrfs_path_cachep, p);
89}
90
91
92
93
94
95
96
97noinline void btrfs_release_path(struct btrfs_path *p)
98{
99 int i;
100
101 for (i = 0; i < BTRFS_MAX_LEVEL; i++) {
102 p->slots[i] = 0;
103 if (!p->nodes[i])
104 continue;
105 if (p->locks[i]) {
106 btrfs_tree_unlock_rw(p->nodes[i], p->locks[i]);
107 p->locks[i] = 0;
108 }
109 free_extent_buffer(p->nodes[i]);
110 p->nodes[i] = NULL;
111 }
112}
113
114
115
116
117
118
119
120
121
122
123
124struct extent_buffer *btrfs_root_node(struct btrfs_root *root)
125{
126 struct extent_buffer *eb;
127
128 while (1) {
129 rcu_read_lock();
130 eb = rcu_dereference(root->node);
131
132
133
134
135
136
137
138 if (atomic_inc_not_zero(&eb->refs)) {
139 rcu_read_unlock();
140 break;
141 }
142 rcu_read_unlock();
143 synchronize_rcu();
144 }
145 return eb;
146}
147
148
149
150
151
152
153static void add_root_to_dirty_list(struct btrfs_root *root)
154{
155 struct btrfs_fs_info *fs_info = root->fs_info;
156
157 if (test_bit(BTRFS_ROOT_DIRTY, &root->state) ||
158 !test_bit(BTRFS_ROOT_TRACK_DIRTY, &root->state))
159 return;
160
161 spin_lock(&fs_info->trans_lock);
162 if (!test_and_set_bit(BTRFS_ROOT_DIRTY, &root->state)) {
163
164 if (root->root_key.objectid == BTRFS_EXTENT_TREE_OBJECTID)
165 list_move_tail(&root->dirty_list,
166 &fs_info->dirty_cowonly_roots);
167 else
168 list_move(&root->dirty_list,
169 &fs_info->dirty_cowonly_roots);
170 }
171 spin_unlock(&fs_info->trans_lock);
172}
173
174
175
176
177
178
179int btrfs_copy_root(struct btrfs_trans_handle *trans,
180 struct btrfs_root *root,
181 struct extent_buffer *buf,
182 struct extent_buffer **cow_ret, u64 new_root_objectid)
183{
184 struct btrfs_fs_info *fs_info = root->fs_info;
185 struct extent_buffer *cow;
186 int ret = 0;
187 int level;
188 struct btrfs_disk_key disk_key;
189
190 WARN_ON(test_bit(BTRFS_ROOT_SHAREABLE, &root->state) &&
191 trans->transid != fs_info->running_transaction->transid);
192 WARN_ON(test_bit(BTRFS_ROOT_SHAREABLE, &root->state) &&
193 trans->transid != root->last_trans);
194
195 level = btrfs_header_level(buf);
196 if (level == 0)
197 btrfs_item_key(buf, &disk_key, 0);
198 else
199 btrfs_node_key(buf, &disk_key, 0);
200
201 cow = btrfs_alloc_tree_block(trans, root, 0, new_root_objectid,
202 &disk_key, level, buf->start, 0,
203 BTRFS_NESTING_NEW_ROOT);
204 if (IS_ERR(cow))
205 return PTR_ERR(cow);
206
207 copy_extent_buffer_full(cow, buf);
208 btrfs_set_header_bytenr(cow, cow->start);
209 btrfs_set_header_generation(cow, trans->transid);
210 btrfs_set_header_backref_rev(cow, BTRFS_MIXED_BACKREF_REV);
211 btrfs_clear_header_flag(cow, BTRFS_HEADER_FLAG_WRITTEN |
212 BTRFS_HEADER_FLAG_RELOC);
213 if (new_root_objectid == BTRFS_TREE_RELOC_OBJECTID)
214 btrfs_set_header_flag(cow, BTRFS_HEADER_FLAG_RELOC);
215 else
216 btrfs_set_header_owner(cow, new_root_objectid);
217
218 write_extent_buffer_fsid(cow, fs_info->fs_devices->metadata_uuid);
219
220 WARN_ON(btrfs_header_generation(buf) > trans->transid);
221 if (new_root_objectid == BTRFS_TREE_RELOC_OBJECTID)
222 ret = btrfs_inc_ref(trans, root, cow, 1);
223 else
224 ret = btrfs_inc_ref(trans, root, cow, 0);
225 if (ret) {
226 btrfs_tree_unlock(cow);
227 free_extent_buffer(cow);
228 btrfs_abort_transaction(trans, ret);
229 return ret;
230 }
231
232 btrfs_mark_buffer_dirty(cow);
233 *cow_ret = cow;
234 return 0;
235}
236
237
238
239
240int btrfs_block_can_be_shared(struct btrfs_root *root,
241 struct extent_buffer *buf)
242{
243
244
245
246
247
248 if (test_bit(BTRFS_ROOT_SHAREABLE, &root->state) &&
249 buf != root->node && buf != root->commit_root &&
250 (btrfs_header_generation(buf) <=
251 btrfs_root_last_snapshot(&root->root_item) ||
252 btrfs_header_flag(buf, BTRFS_HEADER_FLAG_RELOC)))
253 return 1;
254
255 return 0;
256}
257
258static noinline int update_ref_for_cow(struct btrfs_trans_handle *trans,
259 struct btrfs_root *root,
260 struct extent_buffer *buf,
261 struct extent_buffer *cow,
262 int *last_ref)
263{
264 struct btrfs_fs_info *fs_info = root->fs_info;
265 u64 refs;
266 u64 owner;
267 u64 flags;
268 u64 new_flags = 0;
269 int ret;
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288 if (btrfs_block_can_be_shared(root, buf)) {
289 ret = btrfs_lookup_extent_info(trans, fs_info, buf->start,
290 btrfs_header_level(buf), 1,
291 &refs, &flags);
292 if (ret)
293 return ret;
294 if (refs == 0) {
295 ret = -EROFS;
296 btrfs_handle_fs_error(fs_info, ret, NULL);
297 return ret;
298 }
299 } else {
300 refs = 1;
301 if (root->root_key.objectid == BTRFS_TREE_RELOC_OBJECTID ||
302 btrfs_header_backref_rev(buf) < BTRFS_MIXED_BACKREF_REV)
303 flags = BTRFS_BLOCK_FLAG_FULL_BACKREF;
304 else
305 flags = 0;
306 }
307
308 owner = btrfs_header_owner(buf);
309 BUG_ON(owner == BTRFS_TREE_RELOC_OBJECTID &&
310 !(flags & BTRFS_BLOCK_FLAG_FULL_BACKREF));
311
312 if (refs > 1) {
313 if ((owner == root->root_key.objectid ||
314 root->root_key.objectid == BTRFS_TREE_RELOC_OBJECTID) &&
315 !(flags & BTRFS_BLOCK_FLAG_FULL_BACKREF)) {
316 ret = btrfs_inc_ref(trans, root, buf, 1);
317 if (ret)
318 return ret;
319
320 if (root->root_key.objectid ==
321 BTRFS_TREE_RELOC_OBJECTID) {
322 ret = btrfs_dec_ref(trans, root, buf, 0);
323 if (ret)
324 return ret;
325 ret = btrfs_inc_ref(trans, root, cow, 1);
326 if (ret)
327 return ret;
328 }
329 new_flags |= BTRFS_BLOCK_FLAG_FULL_BACKREF;
330 } else {
331
332 if (root->root_key.objectid ==
333 BTRFS_TREE_RELOC_OBJECTID)
334 ret = btrfs_inc_ref(trans, root, cow, 1);
335 else
336 ret = btrfs_inc_ref(trans, root, cow, 0);
337 if (ret)
338 return ret;
339 }
340 if (new_flags != 0) {
341 int level = btrfs_header_level(buf);
342
343 ret = btrfs_set_disk_extent_flags(trans, buf,
344 new_flags, level, 0);
345 if (ret)
346 return ret;
347 }
348 } else {
349 if (flags & BTRFS_BLOCK_FLAG_FULL_BACKREF) {
350 if (root->root_key.objectid ==
351 BTRFS_TREE_RELOC_OBJECTID)
352 ret = btrfs_inc_ref(trans, root, cow, 1);
353 else
354 ret = btrfs_inc_ref(trans, root, cow, 0);
355 if (ret)
356 return ret;
357 ret = btrfs_dec_ref(trans, root, buf, 1);
358 if (ret)
359 return ret;
360 }
361 btrfs_clean_tree_block(buf);
362 *last_ref = 1;
363 }
364 return 0;
365}
366
367
368
369
370
371
372
373
374
375
376
377
378
379static noinline int __btrfs_cow_block(struct btrfs_trans_handle *trans,
380 struct btrfs_root *root,
381 struct extent_buffer *buf,
382 struct extent_buffer *parent, int parent_slot,
383 struct extent_buffer **cow_ret,
384 u64 search_start, u64 empty_size,
385 enum btrfs_lock_nesting nest)
386{
387 struct btrfs_fs_info *fs_info = root->fs_info;
388 struct btrfs_disk_key disk_key;
389 struct extent_buffer *cow;
390 int level, ret;
391 int last_ref = 0;
392 int unlock_orig = 0;
393 u64 parent_start = 0;
394
395 if (*cow_ret == buf)
396 unlock_orig = 1;
397
398 btrfs_assert_tree_locked(buf);
399
400 WARN_ON(test_bit(BTRFS_ROOT_SHAREABLE, &root->state) &&
401 trans->transid != fs_info->running_transaction->transid);
402 WARN_ON(test_bit(BTRFS_ROOT_SHAREABLE, &root->state) &&
403 trans->transid != root->last_trans);
404
405 level = btrfs_header_level(buf);
406
407 if (level == 0)
408 btrfs_item_key(buf, &disk_key, 0);
409 else
410 btrfs_node_key(buf, &disk_key, 0);
411
412 if ((root->root_key.objectid == BTRFS_TREE_RELOC_OBJECTID) && parent)
413 parent_start = parent->start;
414
415 cow = btrfs_alloc_tree_block(trans, root, parent_start,
416 root->root_key.objectid, &disk_key, level,
417 search_start, empty_size, nest);
418 if (IS_ERR(cow))
419 return PTR_ERR(cow);
420
421
422
423 copy_extent_buffer_full(cow, buf);
424 btrfs_set_header_bytenr(cow, cow->start);
425 btrfs_set_header_generation(cow, trans->transid);
426 btrfs_set_header_backref_rev(cow, BTRFS_MIXED_BACKREF_REV);
427 btrfs_clear_header_flag(cow, BTRFS_HEADER_FLAG_WRITTEN |
428 BTRFS_HEADER_FLAG_RELOC);
429 if (root->root_key.objectid == BTRFS_TREE_RELOC_OBJECTID)
430 btrfs_set_header_flag(cow, BTRFS_HEADER_FLAG_RELOC);
431 else
432 btrfs_set_header_owner(cow, root->root_key.objectid);
433
434 write_extent_buffer_fsid(cow, fs_info->fs_devices->metadata_uuid);
435
436 ret = update_ref_for_cow(trans, root, buf, cow, &last_ref);
437 if (ret) {
438 btrfs_tree_unlock(cow);
439 free_extent_buffer(cow);
440 btrfs_abort_transaction(trans, ret);
441 return ret;
442 }
443
444 if (test_bit(BTRFS_ROOT_SHAREABLE, &root->state)) {
445 ret = btrfs_reloc_cow_block(trans, root, buf, cow);
446 if (ret) {
447 btrfs_tree_unlock(cow);
448 free_extent_buffer(cow);
449 btrfs_abort_transaction(trans, ret);
450 return ret;
451 }
452 }
453
454 if (buf == root->node) {
455 WARN_ON(parent && parent != buf);
456 if (root->root_key.objectid == BTRFS_TREE_RELOC_OBJECTID ||
457 btrfs_header_backref_rev(buf) < BTRFS_MIXED_BACKREF_REV)
458 parent_start = buf->start;
459
460 atomic_inc(&cow->refs);
461 ret = btrfs_tree_mod_log_insert_root(root->node, cow, true);
462 BUG_ON(ret < 0);
463 rcu_assign_pointer(root->node, cow);
464
465 btrfs_free_tree_block(trans, root, buf, parent_start,
466 last_ref);
467 free_extent_buffer(buf);
468 add_root_to_dirty_list(root);
469 } else {
470 WARN_ON(trans->transid != btrfs_header_generation(parent));
471 btrfs_tree_mod_log_insert_key(parent, parent_slot,
472 BTRFS_MOD_LOG_KEY_REPLACE, GFP_NOFS);
473 btrfs_set_node_blockptr(parent, parent_slot,
474 cow->start);
475 btrfs_set_node_ptr_generation(parent, parent_slot,
476 trans->transid);
477 btrfs_mark_buffer_dirty(parent);
478 if (last_ref) {
479 ret = btrfs_tree_mod_log_free_eb(buf);
480 if (ret) {
481 btrfs_tree_unlock(cow);
482 free_extent_buffer(cow);
483 btrfs_abort_transaction(trans, ret);
484 return ret;
485 }
486 }
487 btrfs_free_tree_block(trans, root, buf, parent_start,
488 last_ref);
489 }
490 if (unlock_orig)
491 btrfs_tree_unlock(buf);
492 free_extent_buffer_stale(buf);
493 btrfs_mark_buffer_dirty(cow);
494 *cow_ret = cow;
495 return 0;
496}
497
498static inline int should_cow_block(struct btrfs_trans_handle *trans,
499 struct btrfs_root *root,
500 struct extent_buffer *buf)
501{
502 if (btrfs_is_testing(root->fs_info))
503 return 0;
504
505
506 smp_mb__before_atomic();
507
508
509
510
511
512
513
514
515
516
517
518
519 if (btrfs_header_generation(buf) == trans->transid &&
520 !btrfs_header_flag(buf, BTRFS_HEADER_FLAG_WRITTEN) &&
521 !(root->root_key.objectid != BTRFS_TREE_RELOC_OBJECTID &&
522 btrfs_header_flag(buf, BTRFS_HEADER_FLAG_RELOC)) &&
523 !test_bit(BTRFS_ROOT_FORCE_COW, &root->state))
524 return 0;
525 return 1;
526}
527
528
529
530
531
532
533noinline int btrfs_cow_block(struct btrfs_trans_handle *trans,
534 struct btrfs_root *root, struct extent_buffer *buf,
535 struct extent_buffer *parent, int parent_slot,
536 struct extent_buffer **cow_ret,
537 enum btrfs_lock_nesting nest)
538{
539 struct btrfs_fs_info *fs_info = root->fs_info;
540 u64 search_start;
541 int ret;
542
543 if (test_bit(BTRFS_ROOT_DELETING, &root->state))
544 btrfs_err(fs_info,
545 "COW'ing blocks on a fs root that's being dropped");
546
547 if (trans->transaction != fs_info->running_transaction)
548 WARN(1, KERN_CRIT "trans %llu running %llu\n",
549 trans->transid,
550 fs_info->running_transaction->transid);
551
552 if (trans->transid != fs_info->generation)
553 WARN(1, KERN_CRIT "trans %llu running %llu\n",
554 trans->transid, fs_info->generation);
555
556 if (!should_cow_block(trans, root, buf)) {
557 *cow_ret = buf;
558 return 0;
559 }
560
561 search_start = buf->start & ~((u64)SZ_1G - 1);
562
563
564
565
566
567
568
569 btrfs_qgroup_trace_subtree_after_cow(trans, root, buf);
570 ret = __btrfs_cow_block(trans, root, buf, parent,
571 parent_slot, cow_ret, search_start, 0, nest);
572
573 trace_btrfs_cow_block(root, buf, *cow_ret);
574
575 return ret;
576}
577ALLOW_ERROR_INJECTION(btrfs_cow_block, ERRNO);
578
579
580
581
582
583static int close_blocks(u64 blocknr, u64 other, u32 blocksize)
584{
585 if (blocknr < other && other - (blocknr + blocksize) < 32768)
586 return 1;
587 if (blocknr > other && blocknr - (other + blocksize) < 32768)
588 return 1;
589 return 0;
590}
591
592#ifdef __LITTLE_ENDIAN
593
594
595
596
597
598static int comp_keys(const struct btrfs_disk_key *disk_key,
599 const struct btrfs_key *k2)
600{
601 const struct btrfs_key *k1 = (const struct btrfs_key *)disk_key;
602
603 return btrfs_comp_cpu_keys(k1, k2);
604}
605
606#else
607
608
609
610
611static int comp_keys(const struct btrfs_disk_key *disk,
612 const struct btrfs_key *k2)
613{
614 struct btrfs_key k1;
615
616 btrfs_disk_key_to_cpu(&k1, disk);
617
618 return btrfs_comp_cpu_keys(&k1, k2);
619}
620#endif
621
622
623
624
625int __pure btrfs_comp_cpu_keys(const struct btrfs_key *k1, const struct btrfs_key *k2)
626{
627 if (k1->objectid > k2->objectid)
628 return 1;
629 if (k1->objectid < k2->objectid)
630 return -1;
631 if (k1->type > k2->type)
632 return 1;
633 if (k1->type < k2->type)
634 return -1;
635 if (k1->offset > k2->offset)
636 return 1;
637 if (k1->offset < k2->offset)
638 return -1;
639 return 0;
640}
641
642
643
644
645
646
647int btrfs_realloc_node(struct btrfs_trans_handle *trans,
648 struct btrfs_root *root, struct extent_buffer *parent,
649 int start_slot, u64 *last_ret,
650 struct btrfs_key *progress)
651{
652 struct btrfs_fs_info *fs_info = root->fs_info;
653 struct extent_buffer *cur;
654 u64 blocknr;
655 u64 search_start = *last_ret;
656 u64 last_block = 0;
657 u64 other;
658 u32 parent_nritems;
659 int end_slot;
660 int i;
661 int err = 0;
662 u32 blocksize;
663 int progress_passed = 0;
664 struct btrfs_disk_key disk_key;
665
666 WARN_ON(trans->transaction != fs_info->running_transaction);
667 WARN_ON(trans->transid != fs_info->generation);
668
669 parent_nritems = btrfs_header_nritems(parent);
670 blocksize = fs_info->nodesize;
671 end_slot = parent_nritems - 1;
672
673 if (parent_nritems <= 1)
674 return 0;
675
676 for (i = start_slot; i <= end_slot; i++) {
677 int close = 1;
678
679 btrfs_node_key(parent, &disk_key, i);
680 if (!progress_passed && comp_keys(&disk_key, progress) < 0)
681 continue;
682
683 progress_passed = 1;
684 blocknr = btrfs_node_blockptr(parent, i);
685 if (last_block == 0)
686 last_block = blocknr;
687
688 if (i > 0) {
689 other = btrfs_node_blockptr(parent, i - 1);
690 close = close_blocks(blocknr, other, blocksize);
691 }
692 if (!close && i < end_slot) {
693 other = btrfs_node_blockptr(parent, i + 1);
694 close = close_blocks(blocknr, other, blocksize);
695 }
696 if (close) {
697 last_block = blocknr;
698 continue;
699 }
700
701 cur = btrfs_read_node_slot(parent, i);
702 if (IS_ERR(cur))
703 return PTR_ERR(cur);
704 if (search_start == 0)
705 search_start = last_block;
706
707 btrfs_tree_lock(cur);
708 err = __btrfs_cow_block(trans, root, cur, parent, i,
709 &cur, search_start,
710 min(16 * blocksize,
711 (end_slot - i) * blocksize),
712 BTRFS_NESTING_COW);
713 if (err) {
714 btrfs_tree_unlock(cur);
715 free_extent_buffer(cur);
716 break;
717 }
718 search_start = cur->start;
719 last_block = cur->start;
720 *last_ret = search_start;
721 btrfs_tree_unlock(cur);
722 free_extent_buffer(cur);
723 }
724 return err;
725}
726
727
728
729
730
731
732
733
734
735
736
737static noinline int generic_bin_search(struct extent_buffer *eb,
738 unsigned long p, int item_size,
739 const struct btrfs_key *key,
740 int max, int *slot)
741{
742 int low = 0;
743 int high = max;
744 int ret;
745 const int key_size = sizeof(struct btrfs_disk_key);
746
747 if (low > high) {
748 btrfs_err(eb->fs_info,
749 "%s: low (%d) > high (%d) eb %llu owner %llu level %d",
750 __func__, low, high, eb->start,
751 btrfs_header_owner(eb), btrfs_header_level(eb));
752 return -EINVAL;
753 }
754
755 while (low < high) {
756 unsigned long oip;
757 unsigned long offset;
758 struct btrfs_disk_key *tmp;
759 struct btrfs_disk_key unaligned;
760 int mid;
761
762 mid = (low + high) / 2;
763 offset = p + mid * item_size;
764 oip = offset_in_page(offset);
765
766 if (oip + key_size <= PAGE_SIZE) {
767 const unsigned long idx = get_eb_page_index(offset);
768 char *kaddr = page_address(eb->pages[idx]);
769
770 oip = get_eb_offset_in_page(eb, offset);
771 tmp = (struct btrfs_disk_key *)(kaddr + oip);
772 } else {
773 read_extent_buffer(eb, &unaligned, offset, key_size);
774 tmp = &unaligned;
775 }
776
777 ret = comp_keys(tmp, key);
778
779 if (ret < 0)
780 low = mid + 1;
781 else if (ret > 0)
782 high = mid;
783 else {
784 *slot = mid;
785 return 0;
786 }
787 }
788 *slot = low;
789 return 1;
790}
791
792
793
794
795
796int btrfs_bin_search(struct extent_buffer *eb, const struct btrfs_key *key,
797 int *slot)
798{
799 if (btrfs_header_level(eb) == 0)
800 return generic_bin_search(eb,
801 offsetof(struct btrfs_leaf, items),
802 sizeof(struct btrfs_item),
803 key, btrfs_header_nritems(eb),
804 slot);
805 else
806 return generic_bin_search(eb,
807 offsetof(struct btrfs_node, ptrs),
808 sizeof(struct btrfs_key_ptr),
809 key, btrfs_header_nritems(eb),
810 slot);
811}
812
813static void root_add_used(struct btrfs_root *root, u32 size)
814{
815 spin_lock(&root->accounting_lock);
816 btrfs_set_root_used(&root->root_item,
817 btrfs_root_used(&root->root_item) + size);
818 spin_unlock(&root->accounting_lock);
819}
820
821static void root_sub_used(struct btrfs_root *root, u32 size)
822{
823 spin_lock(&root->accounting_lock);
824 btrfs_set_root_used(&root->root_item,
825 btrfs_root_used(&root->root_item) - size);
826 spin_unlock(&root->accounting_lock);
827}
828
829
830
831
832struct extent_buffer *btrfs_read_node_slot(struct extent_buffer *parent,
833 int slot)
834{
835 int level = btrfs_header_level(parent);
836 struct extent_buffer *eb;
837 struct btrfs_key first_key;
838
839 if (slot < 0 || slot >= btrfs_header_nritems(parent))
840 return ERR_PTR(-ENOENT);
841
842 BUG_ON(level == 0);
843
844 btrfs_node_key_to_cpu(parent, &first_key, slot);
845 eb = read_tree_block(parent->fs_info, btrfs_node_blockptr(parent, slot),
846 btrfs_header_owner(parent),
847 btrfs_node_ptr_generation(parent, slot),
848 level - 1, &first_key);
849 if (!IS_ERR(eb) && !extent_buffer_uptodate(eb)) {
850 free_extent_buffer(eb);
851 eb = ERR_PTR(-EIO);
852 }
853
854 return eb;
855}
856
857
858
859
860
861
862static noinline int balance_level(struct btrfs_trans_handle *trans,
863 struct btrfs_root *root,
864 struct btrfs_path *path, int level)
865{
866 struct btrfs_fs_info *fs_info = root->fs_info;
867 struct extent_buffer *right = NULL;
868 struct extent_buffer *mid;
869 struct extent_buffer *left = NULL;
870 struct extent_buffer *parent = NULL;
871 int ret = 0;
872 int wret;
873 int pslot;
874 int orig_slot = path->slots[level];
875 u64 orig_ptr;
876
877 ASSERT(level > 0);
878
879 mid = path->nodes[level];
880
881 WARN_ON(path->locks[level] != BTRFS_WRITE_LOCK);
882 WARN_ON(btrfs_header_generation(mid) != trans->transid);
883
884 orig_ptr = btrfs_node_blockptr(mid, orig_slot);
885
886 if (level < BTRFS_MAX_LEVEL - 1) {
887 parent = path->nodes[level + 1];
888 pslot = path->slots[level + 1];
889 }
890
891
892
893
894
895 if (!parent) {
896 struct extent_buffer *child;
897
898 if (btrfs_header_nritems(mid) != 1)
899 return 0;
900
901
902 child = btrfs_read_node_slot(mid, 0);
903 if (IS_ERR(child)) {
904 ret = PTR_ERR(child);
905 btrfs_handle_fs_error(fs_info, ret, NULL);
906 goto enospc;
907 }
908
909 btrfs_tree_lock(child);
910 ret = btrfs_cow_block(trans, root, child, mid, 0, &child,
911 BTRFS_NESTING_COW);
912 if (ret) {
913 btrfs_tree_unlock(child);
914 free_extent_buffer(child);
915 goto enospc;
916 }
917
918 ret = btrfs_tree_mod_log_insert_root(root->node, child, true);
919 BUG_ON(ret < 0);
920 rcu_assign_pointer(root->node, child);
921
922 add_root_to_dirty_list(root);
923 btrfs_tree_unlock(child);
924
925 path->locks[level] = 0;
926 path->nodes[level] = NULL;
927 btrfs_clean_tree_block(mid);
928 btrfs_tree_unlock(mid);
929
930 free_extent_buffer(mid);
931
932 root_sub_used(root, mid->len);
933 btrfs_free_tree_block(trans, root, mid, 0, 1);
934
935 free_extent_buffer_stale(mid);
936 return 0;
937 }
938 if (btrfs_header_nritems(mid) >
939 BTRFS_NODEPTRS_PER_BLOCK(fs_info) / 4)
940 return 0;
941
942 left = btrfs_read_node_slot(parent, pslot - 1);
943 if (IS_ERR(left))
944 left = NULL;
945
946 if (left) {
947 __btrfs_tree_lock(left, BTRFS_NESTING_LEFT);
948 wret = btrfs_cow_block(trans, root, left,
949 parent, pslot - 1, &left,
950 BTRFS_NESTING_LEFT_COW);
951 if (wret) {
952 ret = wret;
953 goto enospc;
954 }
955 }
956
957 right = btrfs_read_node_slot(parent, pslot + 1);
958 if (IS_ERR(right))
959 right = NULL;
960
961 if (right) {
962 __btrfs_tree_lock(right, BTRFS_NESTING_RIGHT);
963 wret = btrfs_cow_block(trans, root, right,
964 parent, pslot + 1, &right,
965 BTRFS_NESTING_RIGHT_COW);
966 if (wret) {
967 ret = wret;
968 goto enospc;
969 }
970 }
971
972
973 if (left) {
974 orig_slot += btrfs_header_nritems(left);
975 wret = push_node_left(trans, left, mid, 1);
976 if (wret < 0)
977 ret = wret;
978 }
979
980
981
982
983 if (right) {
984 wret = push_node_left(trans, mid, right, 1);
985 if (wret < 0 && wret != -ENOSPC)
986 ret = wret;
987 if (btrfs_header_nritems(right) == 0) {
988 btrfs_clean_tree_block(right);
989 btrfs_tree_unlock(right);
990 del_ptr(root, path, level + 1, pslot + 1);
991 root_sub_used(root, right->len);
992 btrfs_free_tree_block(trans, root, right, 0, 1);
993 free_extent_buffer_stale(right);
994 right = NULL;
995 } else {
996 struct btrfs_disk_key right_key;
997 btrfs_node_key(right, &right_key, 0);
998 ret = btrfs_tree_mod_log_insert_key(parent, pslot + 1,
999 BTRFS_MOD_LOG_KEY_REPLACE, GFP_NOFS);
1000 BUG_ON(ret < 0);
1001 btrfs_set_node_key(parent, &right_key, pslot + 1);
1002 btrfs_mark_buffer_dirty(parent);
1003 }
1004 }
1005 if (btrfs_header_nritems(mid) == 1) {
1006
1007
1008
1009
1010
1011
1012
1013
1014
1015 if (!left) {
1016 ret = -EROFS;
1017 btrfs_handle_fs_error(fs_info, ret, NULL);
1018 goto enospc;
1019 }
1020 wret = balance_node_right(trans, mid, left);
1021 if (wret < 0) {
1022 ret = wret;
1023 goto enospc;
1024 }
1025 if (wret == 1) {
1026 wret = push_node_left(trans, left, mid, 1);
1027 if (wret < 0)
1028 ret = wret;
1029 }
1030 BUG_ON(wret == 1);
1031 }
1032 if (btrfs_header_nritems(mid) == 0) {
1033 btrfs_clean_tree_block(mid);
1034 btrfs_tree_unlock(mid);
1035 del_ptr(root, path, level + 1, pslot);
1036 root_sub_used(root, mid->len);
1037 btrfs_free_tree_block(trans, root, mid, 0, 1);
1038 free_extent_buffer_stale(mid);
1039 mid = NULL;
1040 } else {
1041
1042 struct btrfs_disk_key mid_key;
1043 btrfs_node_key(mid, &mid_key, 0);
1044 ret = btrfs_tree_mod_log_insert_key(parent, pslot,
1045 BTRFS_MOD_LOG_KEY_REPLACE, GFP_NOFS);
1046 BUG_ON(ret < 0);
1047 btrfs_set_node_key(parent, &mid_key, pslot);
1048 btrfs_mark_buffer_dirty(parent);
1049 }
1050
1051
1052 if (left) {
1053 if (btrfs_header_nritems(left) > orig_slot) {
1054 atomic_inc(&left->refs);
1055
1056 path->nodes[level] = left;
1057 path->slots[level + 1] -= 1;
1058 path->slots[level] = orig_slot;
1059 if (mid) {
1060 btrfs_tree_unlock(mid);
1061 free_extent_buffer(mid);
1062 }
1063 } else {
1064 orig_slot -= btrfs_header_nritems(left);
1065 path->slots[level] = orig_slot;
1066 }
1067 }
1068
1069 if (orig_ptr !=
1070 btrfs_node_blockptr(path->nodes[level], path->slots[level]))
1071 BUG();
1072enospc:
1073 if (right) {
1074 btrfs_tree_unlock(right);
1075 free_extent_buffer(right);
1076 }
1077 if (left) {
1078 if (path->nodes[level] != left)
1079 btrfs_tree_unlock(left);
1080 free_extent_buffer(left);
1081 }
1082 return ret;
1083}
1084
1085
1086
1087
1088
1089static noinline int push_nodes_for_insert(struct btrfs_trans_handle *trans,
1090 struct btrfs_root *root,
1091 struct btrfs_path *path, int level)
1092{
1093 struct btrfs_fs_info *fs_info = root->fs_info;
1094 struct extent_buffer *right = NULL;
1095 struct extent_buffer *mid;
1096 struct extent_buffer *left = NULL;
1097 struct extent_buffer *parent = NULL;
1098 int ret = 0;
1099 int wret;
1100 int pslot;
1101 int orig_slot = path->slots[level];
1102
1103 if (level == 0)
1104 return 1;
1105
1106 mid = path->nodes[level];
1107 WARN_ON(btrfs_header_generation(mid) != trans->transid);
1108
1109 if (level < BTRFS_MAX_LEVEL - 1) {
1110 parent = path->nodes[level + 1];
1111 pslot = path->slots[level + 1];
1112 }
1113
1114 if (!parent)
1115 return 1;
1116
1117 left = btrfs_read_node_slot(parent, pslot - 1);
1118 if (IS_ERR(left))
1119 left = NULL;
1120
1121
1122 if (left) {
1123 u32 left_nr;
1124
1125 __btrfs_tree_lock(left, BTRFS_NESTING_LEFT);
1126
1127 left_nr = btrfs_header_nritems(left);
1128 if (left_nr >= BTRFS_NODEPTRS_PER_BLOCK(fs_info) - 1) {
1129 wret = 1;
1130 } else {
1131 ret = btrfs_cow_block(trans, root, left, parent,
1132 pslot - 1, &left,
1133 BTRFS_NESTING_LEFT_COW);
1134 if (ret)
1135 wret = 1;
1136 else {
1137 wret = push_node_left(trans, left, mid, 0);
1138 }
1139 }
1140 if (wret < 0)
1141 ret = wret;
1142 if (wret == 0) {
1143 struct btrfs_disk_key disk_key;
1144 orig_slot += left_nr;
1145 btrfs_node_key(mid, &disk_key, 0);
1146 ret = btrfs_tree_mod_log_insert_key(parent, pslot,
1147 BTRFS_MOD_LOG_KEY_REPLACE, GFP_NOFS);
1148 BUG_ON(ret < 0);
1149 btrfs_set_node_key(parent, &disk_key, pslot);
1150 btrfs_mark_buffer_dirty(parent);
1151 if (btrfs_header_nritems(left) > orig_slot) {
1152 path->nodes[level] = left;
1153 path->slots[level + 1] -= 1;
1154 path->slots[level] = orig_slot;
1155 btrfs_tree_unlock(mid);
1156 free_extent_buffer(mid);
1157 } else {
1158 orig_slot -=
1159 btrfs_header_nritems(left);
1160 path->slots[level] = orig_slot;
1161 btrfs_tree_unlock(left);
1162 free_extent_buffer(left);
1163 }
1164 return 0;
1165 }
1166 btrfs_tree_unlock(left);
1167 free_extent_buffer(left);
1168 }
1169 right = btrfs_read_node_slot(parent, pslot + 1);
1170 if (IS_ERR(right))
1171 right = NULL;
1172
1173
1174
1175
1176 if (right) {
1177 u32 right_nr;
1178
1179 __btrfs_tree_lock(right, BTRFS_NESTING_RIGHT);
1180
1181 right_nr = btrfs_header_nritems(right);
1182 if (right_nr >= BTRFS_NODEPTRS_PER_BLOCK(fs_info) - 1) {
1183 wret = 1;
1184 } else {
1185 ret = btrfs_cow_block(trans, root, right,
1186 parent, pslot + 1,
1187 &right, BTRFS_NESTING_RIGHT_COW);
1188 if (ret)
1189 wret = 1;
1190 else {
1191 wret = balance_node_right(trans, right, mid);
1192 }
1193 }
1194 if (wret < 0)
1195 ret = wret;
1196 if (wret == 0) {
1197 struct btrfs_disk_key disk_key;
1198
1199 btrfs_node_key(right, &disk_key, 0);
1200 ret = btrfs_tree_mod_log_insert_key(parent, pslot + 1,
1201 BTRFS_MOD_LOG_KEY_REPLACE, GFP_NOFS);
1202 BUG_ON(ret < 0);
1203 btrfs_set_node_key(parent, &disk_key, pslot + 1);
1204 btrfs_mark_buffer_dirty(parent);
1205
1206 if (btrfs_header_nritems(mid) <= orig_slot) {
1207 path->nodes[level] = right;
1208 path->slots[level + 1] += 1;
1209 path->slots[level] = orig_slot -
1210 btrfs_header_nritems(mid);
1211 btrfs_tree_unlock(mid);
1212 free_extent_buffer(mid);
1213 } else {
1214 btrfs_tree_unlock(right);
1215 free_extent_buffer(right);
1216 }
1217 return 0;
1218 }
1219 btrfs_tree_unlock(right);
1220 free_extent_buffer(right);
1221 }
1222 return 1;
1223}
1224
1225
1226
1227
1228
1229static void reada_for_search(struct btrfs_fs_info *fs_info,
1230 struct btrfs_path *path,
1231 int level, int slot, u64 objectid)
1232{
1233 struct extent_buffer *node;
1234 struct btrfs_disk_key disk_key;
1235 u32 nritems;
1236 u64 search;
1237 u64 target;
1238 u64 nread = 0;
1239 u64 nread_max;
1240 struct extent_buffer *eb;
1241 u32 nr;
1242 u32 blocksize;
1243 u32 nscan = 0;
1244
1245 if (level != 1 && path->reada != READA_FORWARD_ALWAYS)
1246 return;
1247
1248 if (!path->nodes[level])
1249 return;
1250
1251 node = path->nodes[level];
1252
1253
1254
1255
1256
1257
1258 if (path->reada == READA_FORWARD_ALWAYS) {
1259 if (level > 1)
1260 nread_max = node->fs_info->nodesize;
1261 else
1262 nread_max = SZ_128K;
1263 } else {
1264 nread_max = SZ_64K;
1265 }
1266
1267 search = btrfs_node_blockptr(node, slot);
1268 blocksize = fs_info->nodesize;
1269 eb = find_extent_buffer(fs_info, search);
1270 if (eb) {
1271 free_extent_buffer(eb);
1272 return;
1273 }
1274
1275 target = search;
1276
1277 nritems = btrfs_header_nritems(node);
1278 nr = slot;
1279
1280 while (1) {
1281 if (path->reada == READA_BACK) {
1282 if (nr == 0)
1283 break;
1284 nr--;
1285 } else if (path->reada == READA_FORWARD ||
1286 path->reada == READA_FORWARD_ALWAYS) {
1287 nr++;
1288 if (nr >= nritems)
1289 break;
1290 }
1291 if (path->reada == READA_BACK && objectid) {
1292 btrfs_node_key(node, &disk_key, nr);
1293 if (btrfs_disk_key_objectid(&disk_key) != objectid)
1294 break;
1295 }
1296 search = btrfs_node_blockptr(node, nr);
1297 if (path->reada == READA_FORWARD_ALWAYS ||
1298 (search <= target && target - search <= 65536) ||
1299 (search > target && search - target <= 65536)) {
1300 btrfs_readahead_node_child(node, nr);
1301 nread += blocksize;
1302 }
1303 nscan++;
1304 if (nread > nread_max || nscan > 32)
1305 break;
1306 }
1307}
1308
1309static noinline void reada_for_balance(struct btrfs_path *path, int level)
1310{
1311 struct extent_buffer *parent;
1312 int slot;
1313 int nritems;
1314
1315 parent = path->nodes[level + 1];
1316 if (!parent)
1317 return;
1318
1319 nritems = btrfs_header_nritems(parent);
1320 slot = path->slots[level + 1];
1321
1322 if (slot > 0)
1323 btrfs_readahead_node_child(parent, slot - 1);
1324 if (slot + 1 < nritems)
1325 btrfs_readahead_node_child(parent, slot + 1);
1326}
1327
1328
1329
1330
1331
1332
1333
1334
1335
1336
1337
1338
1339
1340
1341
1342static noinline void unlock_up(struct btrfs_path *path, int level,
1343 int lowest_unlock, int min_write_lock_level,
1344 int *write_lock_level)
1345{
1346 int i;
1347 int skip_level = level;
1348 int no_skips = 0;
1349 struct extent_buffer *t;
1350
1351 for (i = level; i < BTRFS_MAX_LEVEL; i++) {
1352 if (!path->nodes[i])
1353 break;
1354 if (!path->locks[i])
1355 break;
1356 if (!no_skips && path->slots[i] == 0) {
1357 skip_level = i + 1;
1358 continue;
1359 }
1360 if (!no_skips && path->keep_locks) {
1361 u32 nritems;
1362 t = path->nodes[i];
1363 nritems = btrfs_header_nritems(t);
1364 if (nritems < 1 || path->slots[i] >= nritems - 1) {
1365 skip_level = i + 1;
1366 continue;
1367 }
1368 }
1369 if (skip_level < i && i >= lowest_unlock)
1370 no_skips = 1;
1371
1372 t = path->nodes[i];
1373 if (i >= lowest_unlock && i > skip_level) {
1374 btrfs_tree_unlock_rw(t, path->locks[i]);
1375 path->locks[i] = 0;
1376 if (write_lock_level &&
1377 i > min_write_lock_level &&
1378 i <= *write_lock_level) {
1379 *write_lock_level = i - 1;
1380 }
1381 }
1382 }
1383}
1384
1385
1386
1387
1388
1389
1390
1391
1392
1393static int
1394read_block_for_search(struct btrfs_root *root, struct btrfs_path *p,
1395 struct extent_buffer **eb_ret, int level, int slot,
1396 const struct btrfs_key *key)
1397{
1398 struct btrfs_fs_info *fs_info = root->fs_info;
1399 u64 blocknr;
1400 u64 gen;
1401 struct extent_buffer *tmp;
1402 struct btrfs_key first_key;
1403 int ret;
1404 int parent_level;
1405
1406 blocknr = btrfs_node_blockptr(*eb_ret, slot);
1407 gen = btrfs_node_ptr_generation(*eb_ret, slot);
1408 parent_level = btrfs_header_level(*eb_ret);
1409 btrfs_node_key_to_cpu(*eb_ret, &first_key, slot);
1410
1411 tmp = find_extent_buffer(fs_info, blocknr);
1412 if (tmp) {
1413 if (p->reada == READA_FORWARD_ALWAYS)
1414 reada_for_search(fs_info, p, level, slot, key->objectid);
1415
1416
1417 if (btrfs_buffer_uptodate(tmp, gen, 1) > 0) {
1418
1419
1420
1421
1422
1423 if (btrfs_verify_level_key(tmp,
1424 parent_level - 1, &first_key, gen)) {
1425 free_extent_buffer(tmp);
1426 return -EUCLEAN;
1427 }
1428 *eb_ret = tmp;
1429 return 0;
1430 }
1431
1432
1433 ret = btrfs_read_buffer(tmp, gen, parent_level - 1, &first_key);
1434 if (!ret) {
1435 *eb_ret = tmp;
1436 return 0;
1437 }
1438 free_extent_buffer(tmp);
1439 btrfs_release_path(p);
1440 return -EIO;
1441 }
1442
1443
1444
1445
1446
1447
1448
1449
1450 btrfs_unlock_up_safe(p, level + 1);
1451
1452 if (p->reada != READA_NONE)
1453 reada_for_search(fs_info, p, level, slot, key->objectid);
1454
1455 ret = -EAGAIN;
1456 tmp = read_tree_block(fs_info, blocknr, root->root_key.objectid,
1457 gen, parent_level - 1, &first_key);
1458 if (!IS_ERR(tmp)) {
1459
1460
1461
1462
1463
1464
1465 if (!extent_buffer_uptodate(tmp))
1466 ret = -EIO;
1467 free_extent_buffer(tmp);
1468 } else {
1469 ret = PTR_ERR(tmp);
1470 }
1471
1472 btrfs_release_path(p);
1473 return ret;
1474}
1475
1476
1477
1478
1479
1480
1481
1482
1483
1484
1485static int
1486setup_nodes_for_search(struct btrfs_trans_handle *trans,
1487 struct btrfs_root *root, struct btrfs_path *p,
1488 struct extent_buffer *b, int level, int ins_len,
1489 int *write_lock_level)
1490{
1491 struct btrfs_fs_info *fs_info = root->fs_info;
1492 int ret = 0;
1493
1494 if ((p->search_for_split || ins_len > 0) && btrfs_header_nritems(b) >=
1495 BTRFS_NODEPTRS_PER_BLOCK(fs_info) - 3) {
1496
1497 if (*write_lock_level < level + 1) {
1498 *write_lock_level = level + 1;
1499 btrfs_release_path(p);
1500 return -EAGAIN;
1501 }
1502
1503 reada_for_balance(p, level);
1504 ret = split_node(trans, root, p, level);
1505
1506 b = p->nodes[level];
1507 } else if (ins_len < 0 && btrfs_header_nritems(b) <
1508 BTRFS_NODEPTRS_PER_BLOCK(fs_info) / 2) {
1509
1510 if (*write_lock_level < level + 1) {
1511 *write_lock_level = level + 1;
1512 btrfs_release_path(p);
1513 return -EAGAIN;
1514 }
1515
1516 reada_for_balance(p, level);
1517 ret = balance_level(trans, root, p, level);
1518 if (ret)
1519 return ret;
1520
1521 b = p->nodes[level];
1522 if (!b) {
1523 btrfs_release_path(p);
1524 return -EAGAIN;
1525 }
1526 BUG_ON(btrfs_header_nritems(b) == 1);
1527 }
1528 return ret;
1529}
1530
1531int btrfs_find_item(struct btrfs_root *fs_root, struct btrfs_path *path,
1532 u64 iobjectid, u64 ioff, u8 key_type,
1533 struct btrfs_key *found_key)
1534{
1535 int ret;
1536 struct btrfs_key key;
1537 struct extent_buffer *eb;
1538
1539 ASSERT(path);
1540 ASSERT(found_key);
1541
1542 key.type = key_type;
1543 key.objectid = iobjectid;
1544 key.offset = ioff;
1545
1546 ret = btrfs_search_slot(NULL, fs_root, &key, path, 0, 0);
1547 if (ret < 0)
1548 return ret;
1549
1550 eb = path->nodes[0];
1551 if (ret && path->slots[0] >= btrfs_header_nritems(eb)) {
1552 ret = btrfs_next_leaf(fs_root, path);
1553 if (ret)
1554 return ret;
1555 eb = path->nodes[0];
1556 }
1557
1558 btrfs_item_key_to_cpu(eb, found_key, path->slots[0]);
1559 if (found_key->type != key.type ||
1560 found_key->objectid != key.objectid)
1561 return 1;
1562
1563 return 0;
1564}
1565
1566static struct extent_buffer *btrfs_search_slot_get_root(struct btrfs_root *root,
1567 struct btrfs_path *p,
1568 int write_lock_level)
1569{
1570 struct btrfs_fs_info *fs_info = root->fs_info;
1571 struct extent_buffer *b;
1572 int root_lock;
1573 int level = 0;
1574
1575
1576 root_lock = BTRFS_READ_LOCK;
1577
1578 if (p->search_commit_root) {
1579
1580
1581
1582
1583
1584
1585
1586
1587
1588 if (p->need_commit_sem) {
1589 down_read(&fs_info->commit_root_sem);
1590 b = btrfs_clone_extent_buffer(root->commit_root);
1591 up_read(&fs_info->commit_root_sem);
1592 if (!b)
1593 return ERR_PTR(-ENOMEM);
1594
1595 } else {
1596 b = root->commit_root;
1597 atomic_inc(&b->refs);
1598 }
1599 level = btrfs_header_level(b);
1600
1601
1602
1603
1604 ASSERT(p->skip_locking == 1);
1605
1606 goto out;
1607 }
1608
1609 if (p->skip_locking) {
1610 b = btrfs_root_node(root);
1611 level = btrfs_header_level(b);
1612 goto out;
1613 }
1614
1615
1616
1617
1618
1619 if (write_lock_level < BTRFS_MAX_LEVEL) {
1620
1621
1622
1623
1624 b = btrfs_read_lock_root_node(root);
1625 level = btrfs_header_level(b);
1626 if (level > write_lock_level)
1627 goto out;
1628
1629
1630 btrfs_tree_read_unlock(b);
1631 free_extent_buffer(b);
1632 }
1633
1634 b = btrfs_lock_root_node(root);
1635 root_lock = BTRFS_WRITE_LOCK;
1636
1637
1638 level = btrfs_header_level(b);
1639
1640out:
1641 p->nodes[level] = b;
1642 if (!p->skip_locking)
1643 p->locks[level] = root_lock;
1644
1645
1646
1647 return b;
1648}
1649
1650
1651
1652
1653
1654
1655
1656
1657
1658
1659
1660
1661
1662
1663
1664
1665
1666
1667
1668
1669
1670
1671
1672
1673
1674
1675
1676
1677
1678
1679
1680
1681
1682int btrfs_search_slot(struct btrfs_trans_handle *trans, struct btrfs_root *root,
1683 const struct btrfs_key *key, struct btrfs_path *p,
1684 int ins_len, int cow)
1685{
1686 struct extent_buffer *b;
1687 int slot;
1688 int ret;
1689 int err;
1690 int level;
1691 int lowest_unlock = 1;
1692
1693 int write_lock_level = 0;
1694 u8 lowest_level = 0;
1695 int min_write_lock_level;
1696 int prev_cmp;
1697
1698 lowest_level = p->lowest_level;
1699 WARN_ON(lowest_level && ins_len > 0);
1700 WARN_ON(p->nodes[0] != NULL);
1701 BUG_ON(!cow && ins_len);
1702
1703 if (ins_len < 0) {
1704 lowest_unlock = 2;
1705
1706
1707
1708
1709
1710 write_lock_level = 2;
1711 } else if (ins_len > 0) {
1712
1713
1714
1715
1716 write_lock_level = 1;
1717 }
1718
1719 if (!cow)
1720 write_lock_level = -1;
1721
1722 if (cow && (p->keep_locks || p->lowest_level))
1723 write_lock_level = BTRFS_MAX_LEVEL;
1724
1725 min_write_lock_level = write_lock_level;
1726
1727again:
1728 prev_cmp = -1;
1729 b = btrfs_search_slot_get_root(root, p, write_lock_level);
1730 if (IS_ERR(b)) {
1731 ret = PTR_ERR(b);
1732 goto done;
1733 }
1734
1735 while (b) {
1736 int dec = 0;
1737
1738 level = btrfs_header_level(b);
1739
1740 if (cow) {
1741 bool last_level = (level == (BTRFS_MAX_LEVEL - 1));
1742
1743
1744
1745
1746
1747
1748 if (!should_cow_block(trans, root, b))
1749 goto cow_done;
1750
1751
1752
1753
1754
1755 if (level > write_lock_level ||
1756 (level + 1 > write_lock_level &&
1757 level + 1 < BTRFS_MAX_LEVEL &&
1758 p->nodes[level + 1])) {
1759 write_lock_level = level + 1;
1760 btrfs_release_path(p);
1761 goto again;
1762 }
1763
1764 if (last_level)
1765 err = btrfs_cow_block(trans, root, b, NULL, 0,
1766 &b,
1767 BTRFS_NESTING_COW);
1768 else
1769 err = btrfs_cow_block(trans, root, b,
1770 p->nodes[level + 1],
1771 p->slots[level + 1], &b,
1772 BTRFS_NESTING_COW);
1773 if (err) {
1774 ret = err;
1775 goto done;
1776 }
1777 }
1778cow_done:
1779 p->nodes[level] = b;
1780
1781
1782
1783
1784
1785
1786
1787
1788
1789
1790
1791
1792
1793
1794
1795
1796 if (!ins_len && !p->keep_locks) {
1797 int u = level + 1;
1798
1799 if (u < BTRFS_MAX_LEVEL && p->locks[u]) {
1800 btrfs_tree_unlock_rw(p->nodes[u], p->locks[u]);
1801 p->locks[u] = 0;
1802 }
1803 }
1804
1805
1806
1807
1808
1809
1810
1811
1812
1813 if (prev_cmp == 0) {
1814 slot = 0;
1815 ret = 0;
1816 } else {
1817 ret = btrfs_bin_search(b, key, &slot);
1818 prev_cmp = ret;
1819 if (ret < 0)
1820 goto done;
1821 }
1822
1823 if (level == 0) {
1824 p->slots[level] = slot;
1825
1826
1827
1828
1829
1830
1831
1832
1833
1834
1835 if (ret == 0 && ins_len > 0 && !p->search_for_extension) {
1836 ASSERT(ins_len >= sizeof(struct btrfs_item));
1837 ins_len -= sizeof(struct btrfs_item);
1838 }
1839 if (ins_len > 0 &&
1840 btrfs_leaf_free_space(b) < ins_len) {
1841 if (write_lock_level < 1) {
1842 write_lock_level = 1;
1843 btrfs_release_path(p);
1844 goto again;
1845 }
1846
1847 err = split_leaf(trans, root, key,
1848 p, ins_len, ret == 0);
1849
1850 BUG_ON(err > 0);
1851 if (err) {
1852 ret = err;
1853 goto done;
1854 }
1855 }
1856 if (!p->search_for_split)
1857 unlock_up(p, level, lowest_unlock,
1858 min_write_lock_level, NULL);
1859 goto done;
1860 }
1861 if (ret && slot > 0) {
1862 dec = 1;
1863 slot--;
1864 }
1865 p->slots[level] = slot;
1866 err = setup_nodes_for_search(trans, root, p, b, level, ins_len,
1867 &write_lock_level);
1868 if (err == -EAGAIN)
1869 goto again;
1870 if (err) {
1871 ret = err;
1872 goto done;
1873 }
1874 b = p->nodes[level];
1875 slot = p->slots[level];
1876
1877
1878
1879
1880
1881
1882 if (slot == 0 && ins_len && write_lock_level < level + 1) {
1883 write_lock_level = level + 1;
1884 btrfs_release_path(p);
1885 goto again;
1886 }
1887
1888 unlock_up(p, level, lowest_unlock, min_write_lock_level,
1889 &write_lock_level);
1890
1891 if (level == lowest_level) {
1892 if (dec)
1893 p->slots[level]++;
1894 goto done;
1895 }
1896
1897 err = read_block_for_search(root, p, &b, level, slot, key);
1898 if (err == -EAGAIN)
1899 goto again;
1900 if (err) {
1901 ret = err;
1902 goto done;
1903 }
1904
1905 if (!p->skip_locking) {
1906 level = btrfs_header_level(b);
1907 if (level <= write_lock_level) {
1908 btrfs_tree_lock(b);
1909 p->locks[level] = BTRFS_WRITE_LOCK;
1910 } else {
1911 btrfs_tree_read_lock(b);
1912 p->locks[level] = BTRFS_READ_LOCK;
1913 }
1914 p->nodes[level] = b;
1915 }
1916 }
1917 ret = 1;
1918done:
1919 if (ret < 0 && !p->skip_release_on_error)
1920 btrfs_release_path(p);
1921 return ret;
1922}
1923ALLOW_ERROR_INJECTION(btrfs_search_slot, ERRNO);
1924
1925
1926
1927
1928
1929
1930
1931
1932
1933
1934
1935
1936int btrfs_search_old_slot(struct btrfs_root *root, const struct btrfs_key *key,
1937 struct btrfs_path *p, u64 time_seq)
1938{
1939 struct btrfs_fs_info *fs_info = root->fs_info;
1940 struct extent_buffer *b;
1941 int slot;
1942 int ret;
1943 int err;
1944 int level;
1945 int lowest_unlock = 1;
1946 u8 lowest_level = 0;
1947
1948 lowest_level = p->lowest_level;
1949 WARN_ON(p->nodes[0] != NULL);
1950
1951 if (p->search_commit_root) {
1952 BUG_ON(time_seq);
1953 return btrfs_search_slot(NULL, root, key, p, 0, 0);
1954 }
1955
1956again:
1957 b = btrfs_get_old_root(root, time_seq);
1958 if (!b) {
1959 ret = -EIO;
1960 goto done;
1961 }
1962 level = btrfs_header_level(b);
1963 p->locks[level] = BTRFS_READ_LOCK;
1964
1965 while (b) {
1966 int dec = 0;
1967
1968 level = btrfs_header_level(b);
1969 p->nodes[level] = b;
1970
1971
1972
1973
1974
1975
1976
1977 btrfs_unlock_up_safe(p, level + 1);
1978
1979 ret = btrfs_bin_search(b, key, &slot);
1980 if (ret < 0)
1981 goto done;
1982
1983 if (level == 0) {
1984 p->slots[level] = slot;
1985 unlock_up(p, level, lowest_unlock, 0, NULL);
1986 goto done;
1987 }
1988
1989 if (ret && slot > 0) {
1990 dec = 1;
1991 slot--;
1992 }
1993 p->slots[level] = slot;
1994 unlock_up(p, level, lowest_unlock, 0, NULL);
1995
1996 if (level == lowest_level) {
1997 if (dec)
1998 p->slots[level]++;
1999 goto done;
2000 }
2001
2002 err = read_block_for_search(root, p, &b, level, slot, key);
2003 if (err == -EAGAIN)
2004 goto again;
2005 if (err) {
2006 ret = err;
2007 goto done;
2008 }
2009
2010 level = btrfs_header_level(b);
2011 btrfs_tree_read_lock(b);
2012 b = btrfs_tree_mod_log_rewind(fs_info, p, b, time_seq);
2013 if (!b) {
2014 ret = -ENOMEM;
2015 goto done;
2016 }
2017 p->locks[level] = BTRFS_READ_LOCK;
2018 p->nodes[level] = b;
2019 }
2020 ret = 1;
2021done:
2022 if (ret < 0)
2023 btrfs_release_path(p);
2024
2025 return ret;
2026}
2027
2028
2029
2030
2031
2032
2033
2034
2035
2036
2037
2038
2039
2040int btrfs_search_slot_for_read(struct btrfs_root *root,
2041 const struct btrfs_key *key,
2042 struct btrfs_path *p, int find_higher,
2043 int return_any)
2044{
2045 int ret;
2046 struct extent_buffer *leaf;
2047
2048again:
2049 ret = btrfs_search_slot(NULL, root, key, p, 0, 0);
2050 if (ret <= 0)
2051 return ret;
2052
2053
2054
2055
2056
2057
2058
2059 leaf = p->nodes[0];
2060
2061 if (find_higher) {
2062 if (p->slots[0] >= btrfs_header_nritems(leaf)) {
2063 ret = btrfs_next_leaf(root, p);
2064 if (ret <= 0)
2065 return ret;
2066 if (!return_any)
2067 return 1;
2068
2069
2070
2071
2072 return_any = 0;
2073 find_higher = 0;
2074 btrfs_release_path(p);
2075 goto again;
2076 }
2077 } else {
2078 if (p->slots[0] == 0) {
2079 ret = btrfs_prev_leaf(root, p);
2080 if (ret < 0)
2081 return ret;
2082 if (!ret) {
2083 leaf = p->nodes[0];
2084 if (p->slots[0] == btrfs_header_nritems(leaf))
2085 p->slots[0]--;
2086 return 0;
2087 }
2088 if (!return_any)
2089 return 1;
2090
2091
2092
2093
2094 return_any = 0;
2095 find_higher = 1;
2096 btrfs_release_path(p);
2097 goto again;
2098 } else {
2099 --p->slots[0];
2100 }
2101 }
2102 return 0;
2103}
2104
2105
2106
2107
2108
2109
2110
2111
2112
2113static void fixup_low_keys(struct btrfs_path *path,
2114 struct btrfs_disk_key *key, int level)
2115{
2116 int i;
2117 struct extent_buffer *t;
2118 int ret;
2119
2120 for (i = level; i < BTRFS_MAX_LEVEL; i++) {
2121 int tslot = path->slots[i];
2122
2123 if (!path->nodes[i])
2124 break;
2125 t = path->nodes[i];
2126 ret = btrfs_tree_mod_log_insert_key(t, tslot,
2127 BTRFS_MOD_LOG_KEY_REPLACE, GFP_ATOMIC);
2128 BUG_ON(ret < 0);
2129 btrfs_set_node_key(t, key, tslot);
2130 btrfs_mark_buffer_dirty(path->nodes[i]);
2131 if (tslot != 0)
2132 break;
2133 }
2134}
2135
2136
2137
2138
2139
2140
2141
2142void btrfs_set_item_key_safe(struct btrfs_fs_info *fs_info,
2143 struct btrfs_path *path,
2144 const struct btrfs_key *new_key)
2145{
2146 struct btrfs_disk_key disk_key;
2147 struct extent_buffer *eb;
2148 int slot;
2149
2150 eb = path->nodes[0];
2151 slot = path->slots[0];
2152 if (slot > 0) {
2153 btrfs_item_key(eb, &disk_key, slot - 1);
2154 if (unlikely(comp_keys(&disk_key, new_key) >= 0)) {
2155 btrfs_crit(fs_info,
2156 "slot %u key (%llu %u %llu) new key (%llu %u %llu)",
2157 slot, btrfs_disk_key_objectid(&disk_key),
2158 btrfs_disk_key_type(&disk_key),
2159 btrfs_disk_key_offset(&disk_key),
2160 new_key->objectid, new_key->type,
2161 new_key->offset);
2162 btrfs_print_leaf(eb);
2163 BUG();
2164 }
2165 }
2166 if (slot < btrfs_header_nritems(eb) - 1) {
2167 btrfs_item_key(eb, &disk_key, slot + 1);
2168 if (unlikely(comp_keys(&disk_key, new_key) <= 0)) {
2169 btrfs_crit(fs_info,
2170 "slot %u key (%llu %u %llu) new key (%llu %u %llu)",
2171 slot, btrfs_disk_key_objectid(&disk_key),
2172 btrfs_disk_key_type(&disk_key),
2173 btrfs_disk_key_offset(&disk_key),
2174 new_key->objectid, new_key->type,
2175 new_key->offset);
2176 btrfs_print_leaf(eb);
2177 BUG();
2178 }
2179 }
2180
2181 btrfs_cpu_key_to_disk(&disk_key, new_key);
2182 btrfs_set_item_key(eb, &disk_key, slot);
2183 btrfs_mark_buffer_dirty(eb);
2184 if (slot == 0)
2185 fixup_low_keys(path, &disk_key, 1);
2186}
2187
2188
2189
2190
2191
2192
2193
2194
2195
2196
2197
2198
2199
2200
2201
2202
2203
2204
2205
2206
2207
2208static bool check_sibling_keys(struct extent_buffer *left,
2209 struct extent_buffer *right)
2210{
2211 struct btrfs_key left_last;
2212 struct btrfs_key right_first;
2213 int level = btrfs_header_level(left);
2214 int nr_left = btrfs_header_nritems(left);
2215 int nr_right = btrfs_header_nritems(right);
2216
2217
2218 if (!nr_left || !nr_right)
2219 return false;
2220
2221 if (level) {
2222 btrfs_node_key_to_cpu(left, &left_last, nr_left - 1);
2223 btrfs_node_key_to_cpu(right, &right_first, 0);
2224 } else {
2225 btrfs_item_key_to_cpu(left, &left_last, nr_left - 1);
2226 btrfs_item_key_to_cpu(right, &right_first, 0);
2227 }
2228
2229 if (btrfs_comp_cpu_keys(&left_last, &right_first) >= 0) {
2230 btrfs_crit(left->fs_info,
2231"bad key order, sibling blocks, left last (%llu %u %llu) right first (%llu %u %llu)",
2232 left_last.objectid, left_last.type,
2233 left_last.offset, right_first.objectid,
2234 right_first.type, right_first.offset);
2235 return true;
2236 }
2237 return false;
2238}
2239
2240
2241
2242
2243
2244
2245
2246
2247static int push_node_left(struct btrfs_trans_handle *trans,
2248 struct extent_buffer *dst,
2249 struct extent_buffer *src, int empty)
2250{
2251 struct btrfs_fs_info *fs_info = trans->fs_info;
2252 int push_items = 0;
2253 int src_nritems;
2254 int dst_nritems;
2255 int ret = 0;
2256
2257 src_nritems = btrfs_header_nritems(src);
2258 dst_nritems = btrfs_header_nritems(dst);
2259 push_items = BTRFS_NODEPTRS_PER_BLOCK(fs_info) - dst_nritems;
2260 WARN_ON(btrfs_header_generation(src) != trans->transid);
2261 WARN_ON(btrfs_header_generation(dst) != trans->transid);
2262
2263 if (!empty && src_nritems <= 8)
2264 return 1;
2265
2266 if (push_items <= 0)
2267 return 1;
2268
2269 if (empty) {
2270 push_items = min(src_nritems, push_items);
2271 if (push_items < src_nritems) {
2272
2273
2274
2275 if (src_nritems - push_items < 8) {
2276 if (push_items <= 8)
2277 return 1;
2278 push_items -= 8;
2279 }
2280 }
2281 } else
2282 push_items = min(src_nritems - 8, push_items);
2283
2284
2285 if (check_sibling_keys(dst, src)) {
2286 ret = -EUCLEAN;
2287 btrfs_abort_transaction(trans, ret);
2288 return ret;
2289 }
2290 ret = btrfs_tree_mod_log_eb_copy(dst, src, dst_nritems, 0, push_items);
2291 if (ret) {
2292 btrfs_abort_transaction(trans, ret);
2293 return ret;
2294 }
2295 copy_extent_buffer(dst, src,
2296 btrfs_node_key_ptr_offset(dst_nritems),
2297 btrfs_node_key_ptr_offset(0),
2298 push_items * sizeof(struct btrfs_key_ptr));
2299
2300 if (push_items < src_nritems) {
2301
2302
2303
2304
2305 memmove_extent_buffer(src, btrfs_node_key_ptr_offset(0),
2306 btrfs_node_key_ptr_offset(push_items),
2307 (src_nritems - push_items) *
2308 sizeof(struct btrfs_key_ptr));
2309 }
2310 btrfs_set_header_nritems(src, src_nritems - push_items);
2311 btrfs_set_header_nritems(dst, dst_nritems + push_items);
2312 btrfs_mark_buffer_dirty(src);
2313 btrfs_mark_buffer_dirty(dst);
2314
2315 return ret;
2316}
2317
2318
2319
2320
2321
2322
2323
2324
2325
2326
2327static int balance_node_right(struct btrfs_trans_handle *trans,
2328 struct extent_buffer *dst,
2329 struct extent_buffer *src)
2330{
2331 struct btrfs_fs_info *fs_info = trans->fs_info;
2332 int push_items = 0;
2333 int max_push;
2334 int src_nritems;
2335 int dst_nritems;
2336 int ret = 0;
2337
2338 WARN_ON(btrfs_header_generation(src) != trans->transid);
2339 WARN_ON(btrfs_header_generation(dst) != trans->transid);
2340
2341 src_nritems = btrfs_header_nritems(src);
2342 dst_nritems = btrfs_header_nritems(dst);
2343 push_items = BTRFS_NODEPTRS_PER_BLOCK(fs_info) - dst_nritems;
2344 if (push_items <= 0)
2345 return 1;
2346
2347 if (src_nritems < 4)
2348 return 1;
2349
2350 max_push = src_nritems / 2 + 1;
2351
2352 if (max_push >= src_nritems)
2353 return 1;
2354
2355 if (max_push < push_items)
2356 push_items = max_push;
2357
2358
2359 if (check_sibling_keys(src, dst)) {
2360 ret = -EUCLEAN;
2361 btrfs_abort_transaction(trans, ret);
2362 return ret;
2363 }
2364 ret = btrfs_tree_mod_log_insert_move(dst, push_items, 0, dst_nritems);
2365 BUG_ON(ret < 0);
2366 memmove_extent_buffer(dst, btrfs_node_key_ptr_offset(push_items),
2367 btrfs_node_key_ptr_offset(0),
2368 (dst_nritems) *
2369 sizeof(struct btrfs_key_ptr));
2370
2371 ret = btrfs_tree_mod_log_eb_copy(dst, src, 0, src_nritems - push_items,
2372 push_items);
2373 if (ret) {
2374 btrfs_abort_transaction(trans, ret);
2375 return ret;
2376 }
2377 copy_extent_buffer(dst, src,
2378 btrfs_node_key_ptr_offset(0),
2379 btrfs_node_key_ptr_offset(src_nritems - push_items),
2380 push_items * sizeof(struct btrfs_key_ptr));
2381
2382 btrfs_set_header_nritems(src, src_nritems - push_items);
2383 btrfs_set_header_nritems(dst, dst_nritems + push_items);
2384
2385 btrfs_mark_buffer_dirty(src);
2386 btrfs_mark_buffer_dirty(dst);
2387
2388 return ret;
2389}
2390
2391
2392
2393
2394
2395
2396
2397
2398static noinline int insert_new_root(struct btrfs_trans_handle *trans,
2399 struct btrfs_root *root,
2400 struct btrfs_path *path, int level)
2401{
2402 struct btrfs_fs_info *fs_info = root->fs_info;
2403 u64 lower_gen;
2404 struct extent_buffer *lower;
2405 struct extent_buffer *c;
2406 struct extent_buffer *old;
2407 struct btrfs_disk_key lower_key;
2408 int ret;
2409
2410 BUG_ON(path->nodes[level]);
2411 BUG_ON(path->nodes[level-1] != root->node);
2412
2413 lower = path->nodes[level-1];
2414 if (level == 1)
2415 btrfs_item_key(lower, &lower_key, 0);
2416 else
2417 btrfs_node_key(lower, &lower_key, 0);
2418
2419 c = btrfs_alloc_tree_block(trans, root, 0, root->root_key.objectid,
2420 &lower_key, level, root->node->start, 0,
2421 BTRFS_NESTING_NEW_ROOT);
2422 if (IS_ERR(c))
2423 return PTR_ERR(c);
2424
2425 root_add_used(root, fs_info->nodesize);
2426
2427 btrfs_set_header_nritems(c, 1);
2428 btrfs_set_node_key(c, &lower_key, 0);
2429 btrfs_set_node_blockptr(c, 0, lower->start);
2430 lower_gen = btrfs_header_generation(lower);
2431 WARN_ON(lower_gen != trans->transid);
2432
2433 btrfs_set_node_ptr_generation(c, 0, lower_gen);
2434
2435 btrfs_mark_buffer_dirty(c);
2436
2437 old = root->node;
2438 ret = btrfs_tree_mod_log_insert_root(root->node, c, false);
2439 BUG_ON(ret < 0);
2440 rcu_assign_pointer(root->node, c);
2441
2442
2443 free_extent_buffer(old);
2444
2445 add_root_to_dirty_list(root);
2446 atomic_inc(&c->refs);
2447 path->nodes[level] = c;
2448 path->locks[level] = BTRFS_WRITE_LOCK;
2449 path->slots[level] = 0;
2450 return 0;
2451}
2452
2453
2454
2455
2456
2457
2458
2459
2460static void insert_ptr(struct btrfs_trans_handle *trans,
2461 struct btrfs_path *path,
2462 struct btrfs_disk_key *key, u64 bytenr,
2463 int slot, int level)
2464{
2465 struct extent_buffer *lower;
2466 int nritems;
2467 int ret;
2468
2469 BUG_ON(!path->nodes[level]);
2470 btrfs_assert_tree_locked(path->nodes[level]);
2471 lower = path->nodes[level];
2472 nritems = btrfs_header_nritems(lower);
2473 BUG_ON(slot > nritems);
2474 BUG_ON(nritems == BTRFS_NODEPTRS_PER_BLOCK(trans->fs_info));
2475 if (slot != nritems) {
2476 if (level) {
2477 ret = btrfs_tree_mod_log_insert_move(lower, slot + 1,
2478 slot, nritems - slot);
2479 BUG_ON(ret < 0);
2480 }
2481 memmove_extent_buffer(lower,
2482 btrfs_node_key_ptr_offset(slot + 1),
2483 btrfs_node_key_ptr_offset(slot),
2484 (nritems - slot) * sizeof(struct btrfs_key_ptr));
2485 }
2486 if (level) {
2487 ret = btrfs_tree_mod_log_insert_key(lower, slot,
2488 BTRFS_MOD_LOG_KEY_ADD, GFP_NOFS);
2489 BUG_ON(ret < 0);
2490 }
2491 btrfs_set_node_key(lower, key, slot);
2492 btrfs_set_node_blockptr(lower, slot, bytenr);
2493 WARN_ON(trans->transid == 0);
2494 btrfs_set_node_ptr_generation(lower, slot, trans->transid);
2495 btrfs_set_header_nritems(lower, nritems + 1);
2496 btrfs_mark_buffer_dirty(lower);
2497}
2498
2499
2500
2501
2502
2503
2504
2505
2506
2507
2508static noinline int split_node(struct btrfs_trans_handle *trans,
2509 struct btrfs_root *root,
2510 struct btrfs_path *path, int level)
2511{
2512 struct btrfs_fs_info *fs_info = root->fs_info;
2513 struct extent_buffer *c;
2514 struct extent_buffer *split;
2515 struct btrfs_disk_key disk_key;
2516 int mid;
2517 int ret;
2518 u32 c_nritems;
2519
2520 c = path->nodes[level];
2521 WARN_ON(btrfs_header_generation(c) != trans->transid);
2522 if (c == root->node) {
2523
2524
2525
2526
2527
2528
2529
2530
2531
2532
2533 ret = insert_new_root(trans, root, path, level + 1);
2534 if (ret)
2535 return ret;
2536 } else {
2537 ret = push_nodes_for_insert(trans, root, path, level);
2538 c = path->nodes[level];
2539 if (!ret && btrfs_header_nritems(c) <
2540 BTRFS_NODEPTRS_PER_BLOCK(fs_info) - 3)
2541 return 0;
2542 if (ret < 0)
2543 return ret;
2544 }
2545
2546 c_nritems = btrfs_header_nritems(c);
2547 mid = (c_nritems + 1) / 2;
2548 btrfs_node_key(c, &disk_key, mid);
2549
2550 split = btrfs_alloc_tree_block(trans, root, 0, root->root_key.objectid,
2551 &disk_key, level, c->start, 0,
2552 BTRFS_NESTING_SPLIT);
2553 if (IS_ERR(split))
2554 return PTR_ERR(split);
2555
2556 root_add_used(root, fs_info->nodesize);
2557 ASSERT(btrfs_header_level(c) == level);
2558
2559 ret = btrfs_tree_mod_log_eb_copy(split, c, 0, mid, c_nritems - mid);
2560 if (ret) {
2561 btrfs_abort_transaction(trans, ret);
2562 return ret;
2563 }
2564 copy_extent_buffer(split, c,
2565 btrfs_node_key_ptr_offset(0),
2566 btrfs_node_key_ptr_offset(mid),
2567 (c_nritems - mid) * sizeof(struct btrfs_key_ptr));
2568 btrfs_set_header_nritems(split, c_nritems - mid);
2569 btrfs_set_header_nritems(c, mid);
2570
2571 btrfs_mark_buffer_dirty(c);
2572 btrfs_mark_buffer_dirty(split);
2573
2574 insert_ptr(trans, path, &disk_key, split->start,
2575 path->slots[level + 1] + 1, level + 1);
2576
2577 if (path->slots[level] >= mid) {
2578 path->slots[level] -= mid;
2579 btrfs_tree_unlock(c);
2580 free_extent_buffer(c);
2581 path->nodes[level] = split;
2582 path->slots[level + 1] += 1;
2583 } else {
2584 btrfs_tree_unlock(split);
2585 free_extent_buffer(split);
2586 }
2587 return 0;
2588}
2589
2590
2591
2592
2593
2594
2595static int leaf_space_used(struct extent_buffer *l, int start, int nr)
2596{
2597 struct btrfs_item *start_item;
2598 struct btrfs_item *end_item;
2599 int data_len;
2600 int nritems = btrfs_header_nritems(l);
2601 int end = min(nritems, start + nr) - 1;
2602
2603 if (!nr)
2604 return 0;
2605 start_item = btrfs_item_nr(start);
2606 end_item = btrfs_item_nr(end);
2607 data_len = btrfs_item_offset(l, start_item) +
2608 btrfs_item_size(l, start_item);
2609 data_len = data_len - btrfs_item_offset(l, end_item);
2610 data_len += sizeof(struct btrfs_item) * nr;
2611 WARN_ON(data_len < 0);
2612 return data_len;
2613}
2614
2615
2616
2617
2618
2619
2620noinline int btrfs_leaf_free_space(struct extent_buffer *leaf)
2621{
2622 struct btrfs_fs_info *fs_info = leaf->fs_info;
2623 int nritems = btrfs_header_nritems(leaf);
2624 int ret;
2625
2626 ret = BTRFS_LEAF_DATA_SIZE(fs_info) - leaf_space_used(leaf, 0, nritems);
2627 if (ret < 0) {
2628 btrfs_crit(fs_info,
2629 "leaf free space ret %d, leaf data size %lu, used %d nritems %d",
2630 ret,
2631 (unsigned long) BTRFS_LEAF_DATA_SIZE(fs_info),
2632 leaf_space_used(leaf, 0, nritems), nritems);
2633 }
2634 return ret;
2635}
2636
2637
2638
2639
2640
2641static noinline int __push_leaf_right(struct btrfs_path *path,
2642 int data_size, int empty,
2643 struct extent_buffer *right,
2644 int free_space, u32 left_nritems,
2645 u32 min_slot)
2646{
2647 struct btrfs_fs_info *fs_info = right->fs_info;
2648 struct extent_buffer *left = path->nodes[0];
2649 struct extent_buffer *upper = path->nodes[1];
2650 struct btrfs_map_token token;
2651 struct btrfs_disk_key disk_key;
2652 int slot;
2653 u32 i;
2654 int push_space = 0;
2655 int push_items = 0;
2656 struct btrfs_item *item;
2657 u32 nr;
2658 u32 right_nritems;
2659 u32 data_end;
2660 u32 this_item_size;
2661
2662 if (empty)
2663 nr = 0;
2664 else
2665 nr = max_t(u32, 1, min_slot);
2666
2667 if (path->slots[0] >= left_nritems)
2668 push_space += data_size;
2669
2670 slot = path->slots[1];
2671 i = left_nritems - 1;
2672 while (i >= nr) {
2673 item = btrfs_item_nr(i);
2674
2675 if (!empty && push_items > 0) {
2676 if (path->slots[0] > i)
2677 break;
2678 if (path->slots[0] == i) {
2679 int space = btrfs_leaf_free_space(left);
2680
2681 if (space + push_space * 2 > free_space)
2682 break;
2683 }
2684 }
2685
2686 if (path->slots[0] == i)
2687 push_space += data_size;
2688
2689 this_item_size = btrfs_item_size(left, item);
2690 if (this_item_size + sizeof(*item) + push_space > free_space)
2691 break;
2692
2693 push_items++;
2694 push_space += this_item_size + sizeof(*item);
2695 if (i == 0)
2696 break;
2697 i--;
2698 }
2699
2700 if (push_items == 0)
2701 goto out_unlock;
2702
2703 WARN_ON(!empty && push_items == left_nritems);
2704
2705
2706 right_nritems = btrfs_header_nritems(right);
2707
2708 push_space = btrfs_item_end_nr(left, left_nritems - push_items);
2709 push_space -= leaf_data_end(left);
2710
2711
2712 data_end = leaf_data_end(right);
2713 memmove_extent_buffer(right,
2714 BTRFS_LEAF_DATA_OFFSET + data_end - push_space,
2715 BTRFS_LEAF_DATA_OFFSET + data_end,
2716 BTRFS_LEAF_DATA_SIZE(fs_info) - data_end);
2717
2718
2719 copy_extent_buffer(right, left, BTRFS_LEAF_DATA_OFFSET +
2720 BTRFS_LEAF_DATA_SIZE(fs_info) - push_space,
2721 BTRFS_LEAF_DATA_OFFSET + leaf_data_end(left),
2722 push_space);
2723
2724 memmove_extent_buffer(right, btrfs_item_nr_offset(push_items),
2725 btrfs_item_nr_offset(0),
2726 right_nritems * sizeof(struct btrfs_item));
2727
2728
2729 copy_extent_buffer(right, left, btrfs_item_nr_offset(0),
2730 btrfs_item_nr_offset(left_nritems - push_items),
2731 push_items * sizeof(struct btrfs_item));
2732
2733
2734 btrfs_init_map_token(&token, right);
2735 right_nritems += push_items;
2736 btrfs_set_header_nritems(right, right_nritems);
2737 push_space = BTRFS_LEAF_DATA_SIZE(fs_info);
2738 for (i = 0; i < right_nritems; i++) {
2739 item = btrfs_item_nr(i);
2740 push_space -= btrfs_token_item_size(&token, item);
2741 btrfs_set_token_item_offset(&token, item, push_space);
2742 }
2743
2744 left_nritems -= push_items;
2745 btrfs_set_header_nritems(left, left_nritems);
2746
2747 if (left_nritems)
2748 btrfs_mark_buffer_dirty(left);
2749 else
2750 btrfs_clean_tree_block(left);
2751
2752 btrfs_mark_buffer_dirty(right);
2753
2754 btrfs_item_key(right, &disk_key, 0);
2755 btrfs_set_node_key(upper, &disk_key, slot + 1);
2756 btrfs_mark_buffer_dirty(upper);
2757
2758
2759 if (path->slots[0] >= left_nritems) {
2760 path->slots[0] -= left_nritems;
2761 if (btrfs_header_nritems(path->nodes[0]) == 0)
2762 btrfs_clean_tree_block(path->nodes[0]);
2763 btrfs_tree_unlock(path->nodes[0]);
2764 free_extent_buffer(path->nodes[0]);
2765 path->nodes[0] = right;
2766 path->slots[1] += 1;
2767 } else {
2768 btrfs_tree_unlock(right);
2769 free_extent_buffer(right);
2770 }
2771 return 0;
2772
2773out_unlock:
2774 btrfs_tree_unlock(right);
2775 free_extent_buffer(right);
2776 return 1;
2777}
2778
2779
2780
2781
2782
2783
2784
2785
2786
2787
2788
2789static int push_leaf_right(struct btrfs_trans_handle *trans, struct btrfs_root
2790 *root, struct btrfs_path *path,
2791 int min_data_size, int data_size,
2792 int empty, u32 min_slot)
2793{
2794 struct extent_buffer *left = path->nodes[0];
2795 struct extent_buffer *right;
2796 struct extent_buffer *upper;
2797 int slot;
2798 int free_space;
2799 u32 left_nritems;
2800 int ret;
2801
2802 if (!path->nodes[1])
2803 return 1;
2804
2805 slot = path->slots[1];
2806 upper = path->nodes[1];
2807 if (slot >= btrfs_header_nritems(upper) - 1)
2808 return 1;
2809
2810 btrfs_assert_tree_locked(path->nodes[1]);
2811
2812 right = btrfs_read_node_slot(upper, slot + 1);
2813
2814
2815
2816
2817 if (IS_ERR(right))
2818 return 1;
2819
2820 __btrfs_tree_lock(right, BTRFS_NESTING_RIGHT);
2821
2822 free_space = btrfs_leaf_free_space(right);
2823 if (free_space < data_size)
2824 goto out_unlock;
2825
2826
2827 ret = btrfs_cow_block(trans, root, right, upper,
2828 slot + 1, &right, BTRFS_NESTING_RIGHT_COW);
2829 if (ret)
2830 goto out_unlock;
2831
2832 free_space = btrfs_leaf_free_space(right);
2833 if (free_space < data_size)
2834 goto out_unlock;
2835
2836 left_nritems = btrfs_header_nritems(left);
2837 if (left_nritems == 0)
2838 goto out_unlock;
2839
2840 if (check_sibling_keys(left, right)) {
2841 ret = -EUCLEAN;
2842 btrfs_tree_unlock(right);
2843 free_extent_buffer(right);
2844 return ret;
2845 }
2846 if (path->slots[0] == left_nritems && !empty) {
2847
2848
2849
2850
2851 btrfs_tree_unlock(left);
2852 free_extent_buffer(left);
2853 path->nodes[0] = right;
2854 path->slots[0] = 0;
2855 path->slots[1]++;
2856 return 0;
2857 }
2858
2859 return __push_leaf_right(path, min_data_size, empty,
2860 right, free_space, left_nritems, min_slot);
2861out_unlock:
2862 btrfs_tree_unlock(right);
2863 free_extent_buffer(right);
2864 return 1;
2865}
2866
2867
2868
2869
2870
2871
2872
2873
2874
2875static noinline int __push_leaf_left(struct btrfs_path *path, int data_size,
2876 int empty, struct extent_buffer *left,
2877 int free_space, u32 right_nritems,
2878 u32 max_slot)
2879{
2880 struct btrfs_fs_info *fs_info = left->fs_info;
2881 struct btrfs_disk_key disk_key;
2882 struct extent_buffer *right = path->nodes[0];
2883 int i;
2884 int push_space = 0;
2885 int push_items = 0;
2886 struct btrfs_item *item;
2887 u32 old_left_nritems;
2888 u32 nr;
2889 int ret = 0;
2890 u32 this_item_size;
2891 u32 old_left_item_size;
2892 struct btrfs_map_token token;
2893
2894 if (empty)
2895 nr = min(right_nritems, max_slot);
2896 else
2897 nr = min(right_nritems - 1, max_slot);
2898
2899 for (i = 0; i < nr; i++) {
2900 item = btrfs_item_nr(i);
2901
2902 if (!empty && push_items > 0) {
2903 if (path->slots[0] < i)
2904 break;
2905 if (path->slots[0] == i) {
2906 int space = btrfs_leaf_free_space(right);
2907
2908 if (space + push_space * 2 > free_space)
2909 break;
2910 }
2911 }
2912
2913 if (path->slots[0] == i)
2914 push_space += data_size;
2915
2916 this_item_size = btrfs_item_size(right, item);
2917 if (this_item_size + sizeof(*item) + push_space > free_space)
2918 break;
2919
2920 push_items++;
2921 push_space += this_item_size + sizeof(*item);
2922 }
2923
2924 if (push_items == 0) {
2925 ret = 1;
2926 goto out;
2927 }
2928 WARN_ON(!empty && push_items == btrfs_header_nritems(right));
2929
2930
2931 copy_extent_buffer(left, right,
2932 btrfs_item_nr_offset(btrfs_header_nritems(left)),
2933 btrfs_item_nr_offset(0),
2934 push_items * sizeof(struct btrfs_item));
2935
2936 push_space = BTRFS_LEAF_DATA_SIZE(fs_info) -
2937 btrfs_item_offset_nr(right, push_items - 1);
2938
2939 copy_extent_buffer(left, right, BTRFS_LEAF_DATA_OFFSET +
2940 leaf_data_end(left) - push_space,
2941 BTRFS_LEAF_DATA_OFFSET +
2942 btrfs_item_offset_nr(right, push_items - 1),
2943 push_space);
2944 old_left_nritems = btrfs_header_nritems(left);
2945 BUG_ON(old_left_nritems <= 0);
2946
2947 btrfs_init_map_token(&token, left);
2948 old_left_item_size = btrfs_item_offset_nr(left, old_left_nritems - 1);
2949 for (i = old_left_nritems; i < old_left_nritems + push_items; i++) {
2950 u32 ioff;
2951
2952 item = btrfs_item_nr(i);
2953
2954 ioff = btrfs_token_item_offset(&token, item);
2955 btrfs_set_token_item_offset(&token, item,
2956 ioff - (BTRFS_LEAF_DATA_SIZE(fs_info) - old_left_item_size));
2957 }
2958 btrfs_set_header_nritems(left, old_left_nritems + push_items);
2959
2960
2961 if (push_items > right_nritems)
2962 WARN(1, KERN_CRIT "push items %d nr %u\n", push_items,
2963 right_nritems);
2964
2965 if (push_items < right_nritems) {
2966 push_space = btrfs_item_offset_nr(right, push_items - 1) -
2967 leaf_data_end(right);
2968 memmove_extent_buffer(right, BTRFS_LEAF_DATA_OFFSET +
2969 BTRFS_LEAF_DATA_SIZE(fs_info) - push_space,
2970 BTRFS_LEAF_DATA_OFFSET +
2971 leaf_data_end(right), push_space);
2972
2973 memmove_extent_buffer(right, btrfs_item_nr_offset(0),
2974 btrfs_item_nr_offset(push_items),
2975 (btrfs_header_nritems(right) - push_items) *
2976 sizeof(struct btrfs_item));
2977 }
2978
2979 btrfs_init_map_token(&token, right);
2980 right_nritems -= push_items;
2981 btrfs_set_header_nritems(right, right_nritems);
2982 push_space = BTRFS_LEAF_DATA_SIZE(fs_info);
2983 for (i = 0; i < right_nritems; i++) {
2984 item = btrfs_item_nr(i);
2985
2986 push_space = push_space - btrfs_token_item_size(&token, item);
2987 btrfs_set_token_item_offset(&token, item, push_space);
2988 }
2989
2990 btrfs_mark_buffer_dirty(left);
2991 if (right_nritems)
2992 btrfs_mark_buffer_dirty(right);
2993 else
2994 btrfs_clean_tree_block(right);
2995
2996 btrfs_item_key(right, &disk_key, 0);
2997 fixup_low_keys(path, &disk_key, 1);
2998
2999
3000 if (path->slots[0] < push_items) {
3001 path->slots[0] += old_left_nritems;
3002 btrfs_tree_unlock(path->nodes[0]);
3003 free_extent_buffer(path->nodes[0]);
3004 path->nodes[0] = left;
3005 path->slots[1] -= 1;
3006 } else {
3007 btrfs_tree_unlock(left);
3008 free_extent_buffer(left);
3009 path->slots[0] -= push_items;
3010 }
3011 BUG_ON(path->slots[0] < 0);
3012 return ret;
3013out:
3014 btrfs_tree_unlock(left);
3015 free_extent_buffer(left);
3016 return ret;
3017}
3018
3019
3020
3021
3022
3023
3024
3025
3026
3027static int push_leaf_left(struct btrfs_trans_handle *trans, struct btrfs_root
3028 *root, struct btrfs_path *path, int min_data_size,
3029 int data_size, int empty, u32 max_slot)
3030{
3031 struct extent_buffer *right = path->nodes[0];
3032 struct extent_buffer *left;
3033 int slot;
3034 int free_space;
3035 u32 right_nritems;
3036 int ret = 0;
3037
3038 slot = path->slots[1];
3039 if (slot == 0)
3040 return 1;
3041 if (!path->nodes[1])
3042 return 1;
3043
3044 right_nritems = btrfs_header_nritems(right);
3045 if (right_nritems == 0)
3046 return 1;
3047
3048 btrfs_assert_tree_locked(path->nodes[1]);
3049
3050 left = btrfs_read_node_slot(path->nodes[1], slot - 1);
3051
3052
3053
3054
3055 if (IS_ERR(left))
3056 return 1;
3057
3058 __btrfs_tree_lock(left, BTRFS_NESTING_LEFT);
3059
3060 free_space = btrfs_leaf_free_space(left);
3061 if (free_space < data_size) {
3062 ret = 1;
3063 goto out;
3064 }
3065
3066
3067 ret = btrfs_cow_block(trans, root, left,
3068 path->nodes[1], slot - 1, &left,
3069 BTRFS_NESTING_LEFT_COW);
3070 if (ret) {
3071
3072 if (ret == -ENOSPC)
3073 ret = 1;
3074 goto out;
3075 }
3076
3077 free_space = btrfs_leaf_free_space(left);
3078 if (free_space < data_size) {
3079 ret = 1;
3080 goto out;
3081 }
3082
3083 if (check_sibling_keys(left, right)) {
3084 ret = -EUCLEAN;
3085 goto out;
3086 }
3087 return __push_leaf_left(path, min_data_size,
3088 empty, left, free_space, right_nritems,
3089 max_slot);
3090out:
3091 btrfs_tree_unlock(left);
3092 free_extent_buffer(left);
3093 return ret;
3094}
3095
3096
3097
3098
3099
3100static noinline void copy_for_split(struct btrfs_trans_handle *trans,
3101 struct btrfs_path *path,
3102 struct extent_buffer *l,
3103 struct extent_buffer *right,
3104 int slot, int mid, int nritems)
3105{
3106 struct btrfs_fs_info *fs_info = trans->fs_info;
3107 int data_copy_size;
3108 int rt_data_off;
3109 int i;
3110 struct btrfs_disk_key disk_key;
3111 struct btrfs_map_token token;
3112
3113 nritems = nritems - mid;
3114 btrfs_set_header_nritems(right, nritems);
3115 data_copy_size = btrfs_item_end_nr(l, mid) - leaf_data_end(l);
3116
3117 copy_extent_buffer(right, l, btrfs_item_nr_offset(0),
3118 btrfs_item_nr_offset(mid),
3119 nritems * sizeof(struct btrfs_item));
3120
3121 copy_extent_buffer(right, l,
3122 BTRFS_LEAF_DATA_OFFSET + BTRFS_LEAF_DATA_SIZE(fs_info) -
3123 data_copy_size, BTRFS_LEAF_DATA_OFFSET +
3124 leaf_data_end(l), data_copy_size);
3125
3126 rt_data_off = BTRFS_LEAF_DATA_SIZE(fs_info) - btrfs_item_end_nr(l, mid);
3127
3128 btrfs_init_map_token(&token, right);
3129 for (i = 0; i < nritems; i++) {
3130 struct btrfs_item *item = btrfs_item_nr(i);
3131 u32 ioff;
3132
3133 ioff = btrfs_token_item_offset(&token, item);
3134 btrfs_set_token_item_offset(&token, item, ioff + rt_data_off);
3135 }
3136
3137 btrfs_set_header_nritems(l, mid);
3138 btrfs_item_key(right, &disk_key, 0);
3139 insert_ptr(trans, path, &disk_key, right->start, path->slots[1] + 1, 1);
3140
3141 btrfs_mark_buffer_dirty(right);
3142 btrfs_mark_buffer_dirty(l);
3143 BUG_ON(path->slots[0] != slot);
3144
3145 if (mid <= slot) {
3146 btrfs_tree_unlock(path->nodes[0]);
3147 free_extent_buffer(path->nodes[0]);
3148 path->nodes[0] = right;
3149 path->slots[0] -= mid;
3150 path->slots[1] += 1;
3151 } else {
3152 btrfs_tree_unlock(right);
3153 free_extent_buffer(right);
3154 }
3155
3156 BUG_ON(path->slots[0] < 0);
3157}
3158
3159
3160
3161
3162
3163
3164
3165
3166
3167
3168
3169static noinline int push_for_double_split(struct btrfs_trans_handle *trans,
3170 struct btrfs_root *root,
3171 struct btrfs_path *path,
3172 int data_size)
3173{
3174 int ret;
3175 int progress = 0;
3176 int slot;
3177 u32 nritems;
3178 int space_needed = data_size;
3179
3180 slot = path->slots[0];
3181 if (slot < btrfs_header_nritems(path->nodes[0]))
3182 space_needed -= btrfs_leaf_free_space(path->nodes[0]);
3183
3184
3185
3186
3187
3188 ret = push_leaf_right(trans, root, path, 1, space_needed, 0, slot);
3189 if (ret < 0)
3190 return ret;
3191
3192 if (ret == 0)
3193 progress++;
3194
3195 nritems = btrfs_header_nritems(path->nodes[0]);
3196
3197
3198
3199
3200 if (path->slots[0] == 0 || path->slots[0] == nritems)
3201 return 0;
3202
3203 if (btrfs_leaf_free_space(path->nodes[0]) >= data_size)
3204 return 0;
3205
3206
3207 slot = path->slots[0];
3208 space_needed = data_size;
3209 if (slot > 0)
3210 space_needed -= btrfs_leaf_free_space(path->nodes[0]);
3211 ret = push_leaf_left(trans, root, path, 1, space_needed, 0, slot);
3212 if (ret < 0)
3213 return ret;
3214
3215 if (ret == 0)
3216 progress++;
3217
3218 if (progress)
3219 return 0;
3220 return 1;
3221}
3222
3223
3224
3225
3226
3227
3228
3229static noinline int split_leaf(struct btrfs_trans_handle *trans,
3230 struct btrfs_root *root,
3231 const struct btrfs_key *ins_key,
3232 struct btrfs_path *path, int data_size,
3233 int extend)
3234{
3235 struct btrfs_disk_key disk_key;
3236 struct extent_buffer *l;
3237 u32 nritems;
3238 int mid;
3239 int slot;
3240 struct extent_buffer *right;
3241 struct btrfs_fs_info *fs_info = root->fs_info;
3242 int ret = 0;
3243 int wret;
3244 int split;
3245 int num_doubles = 0;
3246 int tried_avoid_double = 0;
3247
3248 l = path->nodes[0];
3249 slot = path->slots[0];
3250 if (extend && data_size + btrfs_item_size_nr(l, slot) +
3251 sizeof(struct btrfs_item) > BTRFS_LEAF_DATA_SIZE(fs_info))
3252 return -EOVERFLOW;
3253
3254
3255 if (data_size && path->nodes[1]) {
3256 int space_needed = data_size;
3257
3258 if (slot < btrfs_header_nritems(l))
3259 space_needed -= btrfs_leaf_free_space(l);
3260
3261 wret = push_leaf_right(trans, root, path, space_needed,
3262 space_needed, 0, 0);
3263 if (wret < 0)
3264 return wret;
3265 if (wret) {
3266 space_needed = data_size;
3267 if (slot > 0)
3268 space_needed -= btrfs_leaf_free_space(l);
3269 wret = push_leaf_left(trans, root, path, space_needed,
3270 space_needed, 0, (u32)-1);
3271 if (wret < 0)
3272 return wret;
3273 }
3274 l = path->nodes[0];
3275
3276
3277 if (btrfs_leaf_free_space(l) >= data_size)
3278 return 0;
3279 }
3280
3281 if (!path->nodes[1]) {
3282 ret = insert_new_root(trans, root, path, 1);
3283 if (ret)
3284 return ret;
3285 }
3286again:
3287 split = 1;
3288 l = path->nodes[0];
3289 slot = path->slots[0];
3290 nritems = btrfs_header_nritems(l);
3291 mid = (nritems + 1) / 2;
3292
3293 if (mid <= slot) {
3294 if (nritems == 1 ||
3295 leaf_space_used(l, mid, nritems - mid) + data_size >
3296 BTRFS_LEAF_DATA_SIZE(fs_info)) {
3297 if (slot >= nritems) {
3298 split = 0;
3299 } else {
3300 mid = slot;
3301 if (mid != nritems &&
3302 leaf_space_used(l, mid, nritems - mid) +
3303 data_size > BTRFS_LEAF_DATA_SIZE(fs_info)) {
3304 if (data_size && !tried_avoid_double)
3305 goto push_for_double;
3306 split = 2;
3307 }
3308 }
3309 }
3310 } else {
3311 if (leaf_space_used(l, 0, mid) + data_size >
3312 BTRFS_LEAF_DATA_SIZE(fs_info)) {
3313 if (!extend && data_size && slot == 0) {
3314 split = 0;
3315 } else if ((extend || !data_size) && slot == 0) {
3316 mid = 1;
3317 } else {
3318 mid = slot;
3319 if (mid != nritems &&
3320 leaf_space_used(l, mid, nritems - mid) +
3321 data_size > BTRFS_LEAF_DATA_SIZE(fs_info)) {
3322 if (data_size && !tried_avoid_double)
3323 goto push_for_double;
3324 split = 2;
3325 }
3326 }
3327 }
3328 }
3329
3330 if (split == 0)
3331 btrfs_cpu_key_to_disk(&disk_key, ins_key);
3332 else
3333 btrfs_item_key(l, &disk_key, mid);
3334
3335
3336
3337
3338
3339
3340
3341
3342
3343 right = btrfs_alloc_tree_block(trans, root, 0, root->root_key.objectid,
3344 &disk_key, 0, l->start, 0,
3345 num_doubles ? BTRFS_NESTING_NEW_ROOT :
3346 BTRFS_NESTING_SPLIT);
3347 if (IS_ERR(right))
3348 return PTR_ERR(right);
3349
3350 root_add_used(root, fs_info->nodesize);
3351
3352 if (split == 0) {
3353 if (mid <= slot) {
3354 btrfs_set_header_nritems(right, 0);
3355 insert_ptr(trans, path, &disk_key,
3356 right->start, path->slots[1] + 1, 1);
3357 btrfs_tree_unlock(path->nodes[0]);
3358 free_extent_buffer(path->nodes[0]);
3359 path->nodes[0] = right;
3360 path->slots[0] = 0;
3361 path->slots[1] += 1;
3362 } else {
3363 btrfs_set_header_nritems(right, 0);
3364 insert_ptr(trans, path, &disk_key,
3365 right->start, path->slots[1], 1);
3366 btrfs_tree_unlock(path->nodes[0]);
3367 free_extent_buffer(path->nodes[0]);
3368 path->nodes[0] = right;
3369 path->slots[0] = 0;
3370 if (path->slots[1] == 0)
3371 fixup_low_keys(path, &disk_key, 1);
3372 }
3373
3374
3375
3376
3377
3378 return ret;
3379 }
3380
3381 copy_for_split(trans, path, l, right, slot, mid, nritems);
3382
3383 if (split == 2) {
3384 BUG_ON(num_doubles != 0);
3385 num_doubles++;
3386 goto again;
3387 }
3388
3389 return 0;
3390
3391push_for_double:
3392 push_for_double_split(trans, root, path, data_size);
3393 tried_avoid_double = 1;
3394 if (btrfs_leaf_free_space(path->nodes[0]) >= data_size)
3395 return 0;
3396 goto again;
3397}
3398
3399static noinline int setup_leaf_for_split(struct btrfs_trans_handle *trans,
3400 struct btrfs_root *root,
3401 struct btrfs_path *path, int ins_len)
3402{
3403 struct btrfs_key key;
3404 struct extent_buffer *leaf;
3405 struct btrfs_file_extent_item *fi;
3406 u64 extent_len = 0;
3407 u32 item_size;
3408 int ret;
3409
3410 leaf = path->nodes[0];
3411 btrfs_item_key_to_cpu(leaf, &key, path->slots[0]);
3412
3413 BUG_ON(key.type != BTRFS_EXTENT_DATA_KEY &&
3414 key.type != BTRFS_EXTENT_CSUM_KEY);
3415
3416 if (btrfs_leaf_free_space(leaf) >= ins_len)
3417 return 0;
3418
3419 item_size = btrfs_item_size_nr(leaf, path->slots[0]);
3420 if (key.type == BTRFS_EXTENT_DATA_KEY) {
3421 fi = btrfs_item_ptr(leaf, path->slots[0],
3422 struct btrfs_file_extent_item);
3423 extent_len = btrfs_file_extent_num_bytes(leaf, fi);
3424 }
3425 btrfs_release_path(path);
3426
3427 path->keep_locks = 1;
3428 path->search_for_split = 1;
3429 ret = btrfs_search_slot(trans, root, &key, path, 0, 1);
3430 path->search_for_split = 0;
3431 if (ret > 0)
3432 ret = -EAGAIN;
3433 if (ret < 0)
3434 goto err;
3435
3436 ret = -EAGAIN;
3437 leaf = path->nodes[0];
3438
3439 if (item_size != btrfs_item_size_nr(leaf, path->slots[0]))
3440 goto err;
3441
3442
3443 if (btrfs_leaf_free_space(path->nodes[0]) >= ins_len)
3444 goto err;
3445
3446 if (key.type == BTRFS_EXTENT_DATA_KEY) {
3447 fi = btrfs_item_ptr(leaf, path->slots[0],
3448 struct btrfs_file_extent_item);
3449 if (extent_len != btrfs_file_extent_num_bytes(leaf, fi))
3450 goto err;
3451 }
3452
3453 ret = split_leaf(trans, root, &key, path, ins_len, 1);
3454 if (ret)
3455 goto err;
3456
3457 path->keep_locks = 0;
3458 btrfs_unlock_up_safe(path, 1);
3459 return 0;
3460err:
3461 path->keep_locks = 0;
3462 return ret;
3463}
3464
3465static noinline int split_item(struct btrfs_path *path,
3466 const struct btrfs_key *new_key,
3467 unsigned long split_offset)
3468{
3469 struct extent_buffer *leaf;
3470 struct btrfs_item *item;
3471 struct btrfs_item *new_item;
3472 int slot;
3473 char *buf;
3474 u32 nritems;
3475 u32 item_size;
3476 u32 orig_offset;
3477 struct btrfs_disk_key disk_key;
3478
3479 leaf = path->nodes[0];
3480 BUG_ON(btrfs_leaf_free_space(leaf) < sizeof(struct btrfs_item));
3481
3482 item = btrfs_item_nr(path->slots[0]);
3483 orig_offset = btrfs_item_offset(leaf, item);
3484 item_size = btrfs_item_size(leaf, item);
3485
3486 buf = kmalloc(item_size, GFP_NOFS);
3487 if (!buf)
3488 return -ENOMEM;
3489
3490 read_extent_buffer(leaf, buf, btrfs_item_ptr_offset(leaf,
3491 path->slots[0]), item_size);
3492
3493 slot = path->slots[0] + 1;
3494 nritems = btrfs_header_nritems(leaf);
3495 if (slot != nritems) {
3496
3497 memmove_extent_buffer(leaf, btrfs_item_nr_offset(slot + 1),
3498 btrfs_item_nr_offset(slot),
3499 (nritems - slot) * sizeof(struct btrfs_item));
3500 }
3501
3502 btrfs_cpu_key_to_disk(&disk_key, new_key);
3503 btrfs_set_item_key(leaf, &disk_key, slot);
3504
3505 new_item = btrfs_item_nr(slot);
3506
3507 btrfs_set_item_offset(leaf, new_item, orig_offset);
3508 btrfs_set_item_size(leaf, new_item, item_size - split_offset);
3509
3510 btrfs_set_item_offset(leaf, item,
3511 orig_offset + item_size - split_offset);
3512 btrfs_set_item_size(leaf, item, split_offset);
3513
3514 btrfs_set_header_nritems(leaf, nritems + 1);
3515
3516
3517 write_extent_buffer(leaf, buf,
3518 btrfs_item_ptr_offset(leaf, path->slots[0]),
3519 split_offset);
3520
3521
3522 write_extent_buffer(leaf, buf + split_offset,
3523 btrfs_item_ptr_offset(leaf, slot),
3524 item_size - split_offset);
3525 btrfs_mark_buffer_dirty(leaf);
3526
3527 BUG_ON(btrfs_leaf_free_space(leaf) < 0);
3528 kfree(buf);
3529 return 0;
3530}
3531
3532
3533
3534
3535
3536
3537
3538
3539
3540
3541
3542
3543
3544
3545
3546
3547int btrfs_split_item(struct btrfs_trans_handle *trans,
3548 struct btrfs_root *root,
3549 struct btrfs_path *path,
3550 const struct btrfs_key *new_key,
3551 unsigned long split_offset)
3552{
3553 int ret;
3554 ret = setup_leaf_for_split(trans, root, path,
3555 sizeof(struct btrfs_item));
3556 if (ret)
3557 return ret;
3558
3559 ret = split_item(path, new_key, split_offset);
3560 return ret;
3561}
3562
3563
3564
3565
3566
3567
3568
3569
3570
3571int btrfs_duplicate_item(struct btrfs_trans_handle *trans,
3572 struct btrfs_root *root,
3573 struct btrfs_path *path,
3574 const struct btrfs_key *new_key)
3575{
3576 struct extent_buffer *leaf;
3577 int ret;
3578 u32 item_size;
3579
3580 leaf = path->nodes[0];
3581 item_size = btrfs_item_size_nr(leaf, path->slots[0]);
3582 ret = setup_leaf_for_split(trans, root, path,
3583 item_size + sizeof(struct btrfs_item));
3584 if (ret)
3585 return ret;
3586
3587 path->slots[0]++;
3588 setup_items_for_insert(root, path, new_key, &item_size, 1);
3589 leaf = path->nodes[0];
3590 memcpy_extent_buffer(leaf,
3591 btrfs_item_ptr_offset(leaf, path->slots[0]),
3592 btrfs_item_ptr_offset(leaf, path->slots[0] - 1),
3593 item_size);
3594 return 0;
3595}
3596
3597
3598
3599
3600
3601
3602
3603void btrfs_truncate_item(struct btrfs_path *path, u32 new_size, int from_end)
3604{
3605 int slot;
3606 struct extent_buffer *leaf;
3607 struct btrfs_item *item;
3608 u32 nritems;
3609 unsigned int data_end;
3610 unsigned int old_data_start;
3611 unsigned int old_size;
3612 unsigned int size_diff;
3613 int i;
3614 struct btrfs_map_token token;
3615
3616 leaf = path->nodes[0];
3617 slot = path->slots[0];
3618
3619 old_size = btrfs_item_size_nr(leaf, slot);
3620 if (old_size == new_size)
3621 return;
3622
3623 nritems = btrfs_header_nritems(leaf);
3624 data_end = leaf_data_end(leaf);
3625
3626 old_data_start = btrfs_item_offset_nr(leaf, slot);
3627
3628 size_diff = old_size - new_size;
3629
3630 BUG_ON(slot < 0);
3631 BUG_ON(slot >= nritems);
3632
3633
3634
3635
3636
3637 btrfs_init_map_token(&token, leaf);
3638 for (i = slot; i < nritems; i++) {
3639 u32 ioff;
3640 item = btrfs_item_nr(i);
3641
3642 ioff = btrfs_token_item_offset(&token, item);
3643 btrfs_set_token_item_offset(&token, item, ioff + size_diff);
3644 }
3645
3646
3647 if (from_end) {
3648 memmove_extent_buffer(leaf, BTRFS_LEAF_DATA_OFFSET +
3649 data_end + size_diff, BTRFS_LEAF_DATA_OFFSET +
3650 data_end, old_data_start + new_size - data_end);
3651 } else {
3652 struct btrfs_disk_key disk_key;
3653 u64 offset;
3654
3655 btrfs_item_key(leaf, &disk_key, slot);
3656
3657 if (btrfs_disk_key_type(&disk_key) == BTRFS_EXTENT_DATA_KEY) {
3658 unsigned long ptr;
3659 struct btrfs_file_extent_item *fi;
3660
3661 fi = btrfs_item_ptr(leaf, slot,
3662 struct btrfs_file_extent_item);
3663 fi = (struct btrfs_file_extent_item *)(
3664 (unsigned long)fi - size_diff);
3665
3666 if (btrfs_file_extent_type(leaf, fi) ==
3667 BTRFS_FILE_EXTENT_INLINE) {
3668 ptr = btrfs_item_ptr_offset(leaf, slot);
3669 memmove_extent_buffer(leaf, ptr,
3670 (unsigned long)fi,
3671 BTRFS_FILE_EXTENT_INLINE_DATA_START);
3672 }
3673 }
3674
3675 memmove_extent_buffer(leaf, BTRFS_LEAF_DATA_OFFSET +
3676 data_end + size_diff, BTRFS_LEAF_DATA_OFFSET +
3677 data_end, old_data_start - data_end);
3678
3679 offset = btrfs_disk_key_offset(&disk_key);
3680 btrfs_set_disk_key_offset(&disk_key, offset + size_diff);
3681 btrfs_set_item_key(leaf, &disk_key, slot);
3682 if (slot == 0)
3683 fixup_low_keys(path, &disk_key, 1);
3684 }
3685
3686 item = btrfs_item_nr(slot);
3687 btrfs_set_item_size(leaf, item, new_size);
3688 btrfs_mark_buffer_dirty(leaf);
3689
3690 if (btrfs_leaf_free_space(leaf) < 0) {
3691 btrfs_print_leaf(leaf);
3692 BUG();
3693 }
3694}
3695
3696
3697
3698
3699void btrfs_extend_item(struct btrfs_path *path, u32 data_size)
3700{
3701 int slot;
3702 struct extent_buffer *leaf;
3703 struct btrfs_item *item;
3704 u32 nritems;
3705 unsigned int data_end;
3706 unsigned int old_data;
3707 unsigned int old_size;
3708 int i;
3709 struct btrfs_map_token token;
3710
3711 leaf = path->nodes[0];
3712
3713 nritems = btrfs_header_nritems(leaf);
3714 data_end = leaf_data_end(leaf);
3715
3716 if (btrfs_leaf_free_space(leaf) < data_size) {
3717 btrfs_print_leaf(leaf);
3718 BUG();
3719 }
3720 slot = path->slots[0];
3721 old_data = btrfs_item_end_nr(leaf, slot);
3722
3723 BUG_ON(slot < 0);
3724 if (slot >= nritems) {
3725 btrfs_print_leaf(leaf);
3726 btrfs_crit(leaf->fs_info, "slot %d too large, nritems %d",
3727 slot, nritems);
3728 BUG();
3729 }
3730
3731
3732
3733
3734
3735 btrfs_init_map_token(&token, leaf);
3736 for (i = slot; i < nritems; i++) {
3737 u32 ioff;
3738 item = btrfs_item_nr(i);
3739
3740 ioff = btrfs_token_item_offset(&token, item);
3741 btrfs_set_token_item_offset(&token, item, ioff - data_size);
3742 }
3743
3744
3745 memmove_extent_buffer(leaf, BTRFS_LEAF_DATA_OFFSET +
3746 data_end - data_size, BTRFS_LEAF_DATA_OFFSET +
3747 data_end, old_data - data_end);
3748
3749 data_end = old_data;
3750 old_size = btrfs_item_size_nr(leaf, slot);
3751 item = btrfs_item_nr(slot);
3752 btrfs_set_item_size(leaf, item, old_size + data_size);
3753 btrfs_mark_buffer_dirty(leaf);
3754
3755 if (btrfs_leaf_free_space(leaf) < 0) {
3756 btrfs_print_leaf(leaf);
3757 BUG();
3758 }
3759}
3760
3761
3762
3763
3764
3765
3766
3767
3768
3769
3770
3771
3772void setup_items_for_insert(struct btrfs_root *root, struct btrfs_path *path,
3773 const struct btrfs_key *cpu_key, u32 *data_size,
3774 int nr)
3775{
3776 struct btrfs_fs_info *fs_info = root->fs_info;
3777 struct btrfs_item *item;
3778 int i;
3779 u32 nritems;
3780 unsigned int data_end;
3781 struct btrfs_disk_key disk_key;
3782 struct extent_buffer *leaf;
3783 int slot;
3784 struct btrfs_map_token token;
3785 u32 total_size;
3786 u32 total_data = 0;
3787
3788 for (i = 0; i < nr; i++)
3789 total_data += data_size[i];
3790 total_size = total_data + (nr * sizeof(struct btrfs_item));
3791
3792 if (path->slots[0] == 0) {
3793 btrfs_cpu_key_to_disk(&disk_key, cpu_key);
3794 fixup_low_keys(path, &disk_key, 1);
3795 }
3796 btrfs_unlock_up_safe(path, 1);
3797
3798 leaf = path->nodes[0];
3799 slot = path->slots[0];
3800
3801 nritems = btrfs_header_nritems(leaf);
3802 data_end = leaf_data_end(leaf);
3803
3804 if (btrfs_leaf_free_space(leaf) < total_size) {
3805 btrfs_print_leaf(leaf);
3806 btrfs_crit(fs_info, "not enough freespace need %u have %d",
3807 total_size, btrfs_leaf_free_space(leaf));
3808 BUG();
3809 }
3810
3811 btrfs_init_map_token(&token, leaf);
3812 if (slot != nritems) {
3813 unsigned int old_data = btrfs_item_end_nr(leaf, slot);
3814
3815 if (old_data < data_end) {
3816 btrfs_print_leaf(leaf);
3817 btrfs_crit(fs_info,
3818 "item at slot %d with data offset %u beyond data end of leaf %u",
3819 slot, old_data, data_end);
3820 BUG();
3821 }
3822
3823
3824
3825
3826 for (i = slot; i < nritems; i++) {
3827 u32 ioff;
3828
3829 item = btrfs_item_nr(i);
3830 ioff = btrfs_token_item_offset(&token, item);
3831 btrfs_set_token_item_offset(&token, item,
3832 ioff - total_data);
3833 }
3834
3835 memmove_extent_buffer(leaf, btrfs_item_nr_offset(slot + nr),
3836 btrfs_item_nr_offset(slot),
3837 (nritems - slot) * sizeof(struct btrfs_item));
3838
3839
3840 memmove_extent_buffer(leaf, BTRFS_LEAF_DATA_OFFSET +
3841 data_end - total_data, BTRFS_LEAF_DATA_OFFSET +
3842 data_end, old_data - data_end);
3843 data_end = old_data;
3844 }
3845
3846
3847 for (i = 0; i < nr; i++) {
3848 btrfs_cpu_key_to_disk(&disk_key, cpu_key + i);
3849 btrfs_set_item_key(leaf, &disk_key, slot + i);
3850 item = btrfs_item_nr(slot + i);
3851 data_end -= data_size[i];
3852 btrfs_set_token_item_offset(&token, item, data_end);
3853 btrfs_set_token_item_size(&token, item, data_size[i]);
3854 }
3855
3856 btrfs_set_header_nritems(leaf, nritems + nr);
3857 btrfs_mark_buffer_dirty(leaf);
3858
3859 if (btrfs_leaf_free_space(leaf) < 0) {
3860 btrfs_print_leaf(leaf);
3861 BUG();
3862 }
3863}
3864
3865
3866
3867
3868
3869int btrfs_insert_empty_items(struct btrfs_trans_handle *trans,
3870 struct btrfs_root *root,
3871 struct btrfs_path *path,
3872 const struct btrfs_key *cpu_key, u32 *data_size,
3873 int nr)
3874{
3875 int ret = 0;
3876 int slot;
3877 int i;
3878 u32 total_size = 0;
3879 u32 total_data = 0;
3880
3881 for (i = 0; i < nr; i++)
3882 total_data += data_size[i];
3883
3884 total_size = total_data + (nr * sizeof(struct btrfs_item));
3885 ret = btrfs_search_slot(trans, root, cpu_key, path, total_size, 1);
3886 if (ret == 0)
3887 return -EEXIST;
3888 if (ret < 0)
3889 return ret;
3890
3891 slot = path->slots[0];
3892 BUG_ON(slot < 0);
3893
3894 setup_items_for_insert(root, path, cpu_key, data_size, nr);
3895 return 0;
3896}
3897
3898
3899
3900
3901
3902int btrfs_insert_item(struct btrfs_trans_handle *trans, struct btrfs_root *root,
3903 const struct btrfs_key *cpu_key, void *data,
3904 u32 data_size)
3905{
3906 int ret = 0;
3907 struct btrfs_path *path;
3908 struct extent_buffer *leaf;
3909 unsigned long ptr;
3910
3911 path = btrfs_alloc_path();
3912 if (!path)
3913 return -ENOMEM;
3914 ret = btrfs_insert_empty_item(trans, root, path, cpu_key, data_size);
3915 if (!ret) {
3916 leaf = path->nodes[0];
3917 ptr = btrfs_item_ptr_offset(leaf, path->slots[0]);
3918 write_extent_buffer(leaf, data, ptr, data_size);
3919 btrfs_mark_buffer_dirty(leaf);
3920 }
3921 btrfs_free_path(path);
3922 return ret;
3923}
3924
3925
3926
3927
3928
3929
3930
3931static void del_ptr(struct btrfs_root *root, struct btrfs_path *path,
3932 int level, int slot)
3933{
3934 struct extent_buffer *parent = path->nodes[level];
3935 u32 nritems;
3936 int ret;
3937
3938 nritems = btrfs_header_nritems(parent);
3939 if (slot != nritems - 1) {
3940 if (level) {
3941 ret = btrfs_tree_mod_log_insert_move(parent, slot,
3942 slot + 1, nritems - slot - 1);
3943 BUG_ON(ret < 0);
3944 }
3945 memmove_extent_buffer(parent,
3946 btrfs_node_key_ptr_offset(slot),
3947 btrfs_node_key_ptr_offset(slot + 1),
3948 sizeof(struct btrfs_key_ptr) *
3949 (nritems - slot - 1));
3950 } else if (level) {
3951 ret = btrfs_tree_mod_log_insert_key(parent, slot,
3952 BTRFS_MOD_LOG_KEY_REMOVE, GFP_NOFS);
3953 BUG_ON(ret < 0);
3954 }
3955
3956 nritems--;
3957 btrfs_set_header_nritems(parent, nritems);
3958 if (nritems == 0 && parent == root->node) {
3959 BUG_ON(btrfs_header_level(root->node) != 1);
3960
3961 btrfs_set_header_level(root->node, 0);
3962 } else if (slot == 0) {
3963 struct btrfs_disk_key disk_key;
3964
3965 btrfs_node_key(parent, &disk_key, 0);
3966 fixup_low_keys(path, &disk_key, level + 1);
3967 }
3968 btrfs_mark_buffer_dirty(parent);
3969}
3970
3971
3972
3973
3974
3975
3976
3977
3978
3979
3980
3981static noinline void btrfs_del_leaf(struct btrfs_trans_handle *trans,
3982 struct btrfs_root *root,
3983 struct btrfs_path *path,
3984 struct extent_buffer *leaf)
3985{
3986 WARN_ON(btrfs_header_generation(leaf) != trans->transid);
3987 del_ptr(root, path, 1, path->slots[1]);
3988
3989
3990
3991
3992
3993 btrfs_unlock_up_safe(path, 0);
3994
3995 root_sub_used(root, leaf->len);
3996
3997 atomic_inc(&leaf->refs);
3998 btrfs_free_tree_block(trans, root, leaf, 0, 1);
3999 free_extent_buffer_stale(leaf);
4000}
4001
4002
4003
4004
4005int btrfs_del_items(struct btrfs_trans_handle *trans, struct btrfs_root *root,
4006 struct btrfs_path *path, int slot, int nr)
4007{
4008 struct btrfs_fs_info *fs_info = root->fs_info;
4009 struct extent_buffer *leaf;
4010 struct btrfs_item *item;
4011 u32 last_off;
4012 u32 dsize = 0;
4013 int ret = 0;
4014 int wret;
4015 int i;
4016 u32 nritems;
4017
4018 leaf = path->nodes[0];
4019 last_off = btrfs_item_offset_nr(leaf, slot + nr - 1);
4020
4021 for (i = 0; i < nr; i++)
4022 dsize += btrfs_item_size_nr(leaf, slot + i);
4023
4024 nritems = btrfs_header_nritems(leaf);
4025
4026 if (slot + nr != nritems) {
4027 int data_end = leaf_data_end(leaf);
4028 struct btrfs_map_token token;
4029
4030 memmove_extent_buffer(leaf, BTRFS_LEAF_DATA_OFFSET +
4031 data_end + dsize,
4032 BTRFS_LEAF_DATA_OFFSET + data_end,
4033 last_off - data_end);
4034
4035 btrfs_init_map_token(&token, leaf);
4036 for (i = slot + nr; i < nritems; i++) {
4037 u32 ioff;
4038
4039 item = btrfs_item_nr(i);
4040 ioff = btrfs_token_item_offset(&token, item);
4041 btrfs_set_token_item_offset(&token, item, ioff + dsize);
4042 }
4043
4044 memmove_extent_buffer(leaf, btrfs_item_nr_offset(slot),
4045 btrfs_item_nr_offset(slot + nr),
4046 sizeof(struct btrfs_item) *
4047 (nritems - slot - nr));
4048 }
4049 btrfs_set_header_nritems(leaf, nritems - nr);
4050 nritems -= nr;
4051
4052
4053 if (nritems == 0) {
4054 if (leaf == root->node) {
4055 btrfs_set_header_level(leaf, 0);
4056 } else {
4057 btrfs_clean_tree_block(leaf);
4058 btrfs_del_leaf(trans, root, path, leaf);
4059 }
4060 } else {
4061 int used = leaf_space_used(leaf, 0, nritems);
4062 if (slot == 0) {
4063 struct btrfs_disk_key disk_key;
4064
4065 btrfs_item_key(leaf, &disk_key, 0);
4066 fixup_low_keys(path, &disk_key, 1);
4067 }
4068
4069
4070 if (used < BTRFS_LEAF_DATA_SIZE(fs_info) / 3) {
4071
4072
4073
4074
4075 slot = path->slots[1];
4076 atomic_inc(&leaf->refs);
4077
4078 wret = push_leaf_left(trans, root, path, 1, 1,
4079 1, (u32)-1);
4080 if (wret < 0 && wret != -ENOSPC)
4081 ret = wret;
4082
4083 if (path->nodes[0] == leaf &&
4084 btrfs_header_nritems(leaf)) {
4085 wret = push_leaf_right(trans, root, path, 1,
4086 1, 1, 0);
4087 if (wret < 0 && wret != -ENOSPC)
4088 ret = wret;
4089 }
4090
4091 if (btrfs_header_nritems(leaf) == 0) {
4092 path->slots[1] = slot;
4093 btrfs_del_leaf(trans, root, path, leaf);
4094 free_extent_buffer(leaf);
4095 ret = 0;
4096 } else {
4097
4098
4099
4100
4101
4102 if (path->nodes[0] == leaf)
4103 btrfs_mark_buffer_dirty(leaf);
4104 free_extent_buffer(leaf);
4105 }
4106 } else {
4107 btrfs_mark_buffer_dirty(leaf);
4108 }
4109 }
4110 return ret;
4111}
4112
4113
4114
4115
4116
4117
4118
4119
4120
4121int btrfs_prev_leaf(struct btrfs_root *root, struct btrfs_path *path)
4122{
4123 struct btrfs_key key;
4124 struct btrfs_disk_key found_key;
4125 int ret;
4126
4127 btrfs_item_key_to_cpu(path->nodes[0], &key, 0);
4128
4129 if (key.offset > 0) {
4130 key.offset--;
4131 } else if (key.type > 0) {
4132 key.type--;
4133 key.offset = (u64)-1;
4134 } else if (key.objectid > 0) {
4135 key.objectid--;
4136 key.type = (u8)-1;
4137 key.offset = (u64)-1;
4138 } else {
4139 return 1;
4140 }
4141
4142 btrfs_release_path(path);
4143 ret = btrfs_search_slot(NULL, root, &key, path, 0, 0);
4144 if (ret < 0)
4145 return ret;
4146 btrfs_item_key(path->nodes[0], &found_key, 0);
4147 ret = comp_keys(&found_key, &key);
4148
4149
4150
4151
4152
4153
4154
4155
4156
4157
4158 if (ret <= 0)
4159 return 0;
4160 return 1;
4161}
4162
4163
4164
4165
4166
4167
4168
4169
4170
4171
4172
4173
4174
4175
4176
4177
4178
4179
4180
4181
4182int btrfs_search_forward(struct btrfs_root *root, struct btrfs_key *min_key,
4183 struct btrfs_path *path,
4184 u64 min_trans)
4185{
4186 struct extent_buffer *cur;
4187 struct btrfs_key found_key;
4188 int slot;
4189 int sret;
4190 u32 nritems;
4191 int level;
4192 int ret = 1;
4193 int keep_locks = path->keep_locks;
4194
4195 path->keep_locks = 1;
4196again:
4197 cur = btrfs_read_lock_root_node(root);
4198 level = btrfs_header_level(cur);
4199 WARN_ON(path->nodes[level]);
4200 path->nodes[level] = cur;
4201 path->locks[level] = BTRFS_READ_LOCK;
4202
4203 if (btrfs_header_generation(cur) < min_trans) {
4204 ret = 1;
4205 goto out;
4206 }
4207 while (1) {
4208 nritems = btrfs_header_nritems(cur);
4209 level = btrfs_header_level(cur);
4210 sret = btrfs_bin_search(cur, min_key, &slot);
4211 if (sret < 0) {
4212 ret = sret;
4213 goto out;
4214 }
4215
4216
4217 if (level == path->lowest_level) {
4218 if (slot >= nritems)
4219 goto find_next_key;
4220 ret = 0;
4221 path->slots[level] = slot;
4222 btrfs_item_key_to_cpu(cur, &found_key, slot);
4223 goto out;
4224 }
4225 if (sret && slot > 0)
4226 slot--;
4227
4228
4229
4230
4231 while (slot < nritems) {
4232 u64 gen;
4233
4234 gen = btrfs_node_ptr_generation(cur, slot);
4235 if (gen < min_trans) {
4236 slot++;
4237 continue;
4238 }
4239 break;
4240 }
4241find_next_key:
4242
4243
4244
4245
4246 if (slot >= nritems) {
4247 path->slots[level] = slot;
4248 sret = btrfs_find_next_key(root, path, min_key, level,
4249 min_trans);
4250 if (sret == 0) {
4251 btrfs_release_path(path);
4252 goto again;
4253 } else {
4254 goto out;
4255 }
4256 }
4257
4258 btrfs_node_key_to_cpu(cur, &found_key, slot);
4259 path->slots[level] = slot;
4260 if (level == path->lowest_level) {
4261 ret = 0;
4262 goto out;
4263 }
4264 cur = btrfs_read_node_slot(cur, slot);
4265 if (IS_ERR(cur)) {
4266 ret = PTR_ERR(cur);
4267 goto out;
4268 }
4269
4270 btrfs_tree_read_lock(cur);
4271
4272 path->locks[level - 1] = BTRFS_READ_LOCK;
4273 path->nodes[level - 1] = cur;
4274 unlock_up(path, level, 1, 0, NULL);
4275 }
4276out:
4277 path->keep_locks = keep_locks;
4278 if (ret == 0) {
4279 btrfs_unlock_up_safe(path, path->lowest_level + 1);
4280 memcpy(min_key, &found_key, sizeof(found_key));
4281 }
4282 return ret;
4283}
4284
4285
4286
4287
4288
4289
4290
4291
4292
4293
4294
4295
4296int btrfs_find_next_key(struct btrfs_root *root, struct btrfs_path *path,
4297 struct btrfs_key *key, int level, u64 min_trans)
4298{
4299 int slot;
4300 struct extent_buffer *c;
4301
4302 WARN_ON(!path->keep_locks && !path->skip_locking);
4303 while (level < BTRFS_MAX_LEVEL) {
4304 if (!path->nodes[level])
4305 return 1;
4306
4307 slot = path->slots[level] + 1;
4308 c = path->nodes[level];
4309next:
4310 if (slot >= btrfs_header_nritems(c)) {
4311 int ret;
4312 int orig_lowest;
4313 struct btrfs_key cur_key;
4314 if (level + 1 >= BTRFS_MAX_LEVEL ||
4315 !path->nodes[level + 1])
4316 return 1;
4317
4318 if (path->locks[level + 1] || path->skip_locking) {
4319 level++;
4320 continue;
4321 }
4322
4323 slot = btrfs_header_nritems(c) - 1;
4324 if (level == 0)
4325 btrfs_item_key_to_cpu(c, &cur_key, slot);
4326 else
4327 btrfs_node_key_to_cpu(c, &cur_key, slot);
4328
4329 orig_lowest = path->lowest_level;
4330 btrfs_release_path(path);
4331 path->lowest_level = level;
4332 ret = btrfs_search_slot(NULL, root, &cur_key, path,
4333 0, 0);
4334 path->lowest_level = orig_lowest;
4335 if (ret < 0)
4336 return ret;
4337
4338 c = path->nodes[level];
4339 slot = path->slots[level];
4340 if (ret == 0)
4341 slot++;
4342 goto next;
4343 }
4344
4345 if (level == 0)
4346 btrfs_item_key_to_cpu(c, key, slot);
4347 else {
4348 u64 gen = btrfs_node_ptr_generation(c, slot);
4349
4350 if (gen < min_trans) {
4351 slot++;
4352 goto next;
4353 }
4354 btrfs_node_key_to_cpu(c, key, slot);
4355 }
4356 return 0;
4357 }
4358 return 1;
4359}
4360
4361
4362
4363
4364
4365
4366int btrfs_next_leaf(struct btrfs_root *root, struct btrfs_path *path)
4367{
4368 return btrfs_next_old_leaf(root, path, 0);
4369}
4370
4371int btrfs_next_old_leaf(struct btrfs_root *root, struct btrfs_path *path,
4372 u64 time_seq)
4373{
4374 int slot;
4375 int level;
4376 struct extent_buffer *c;
4377 struct extent_buffer *next;
4378 struct btrfs_key key;
4379 u32 nritems;
4380 int ret;
4381 int i;
4382
4383 nritems = btrfs_header_nritems(path->nodes[0]);
4384 if (nritems == 0)
4385 return 1;
4386
4387 btrfs_item_key_to_cpu(path->nodes[0], &key, nritems - 1);
4388again:
4389 level = 1;
4390 next = NULL;
4391 btrfs_release_path(path);
4392
4393 path->keep_locks = 1;
4394
4395 if (time_seq)
4396 ret = btrfs_search_old_slot(root, &key, path, time_seq);
4397 else
4398 ret = btrfs_search_slot(NULL, root, &key, path, 0, 0);
4399 path->keep_locks = 0;
4400
4401 if (ret < 0)
4402 return ret;
4403
4404 nritems = btrfs_header_nritems(path->nodes[0]);
4405
4406
4407
4408
4409
4410
4411 if (nritems > 0 && path->slots[0] < nritems - 1) {
4412 if (ret == 0)
4413 path->slots[0]++;
4414 ret = 0;
4415 goto done;
4416 }
4417
4418
4419
4420
4421
4422
4423
4424
4425
4426
4427
4428
4429
4430
4431 if (nritems > 0 && ret > 0 && path->slots[0] == nritems - 1) {
4432 ret = 0;
4433 goto done;
4434 }
4435
4436 while (level < BTRFS_MAX_LEVEL) {
4437 if (!path->nodes[level]) {
4438 ret = 1;
4439 goto done;
4440 }
4441
4442 slot = path->slots[level] + 1;
4443 c = path->nodes[level];
4444 if (slot >= btrfs_header_nritems(c)) {
4445 level++;
4446 if (level == BTRFS_MAX_LEVEL) {
4447 ret = 1;
4448 goto done;
4449 }
4450 continue;
4451 }
4452
4453
4454
4455
4456
4457
4458
4459 for (i = 0; i < level; i++) {
4460 if (path->locks[level]) {
4461 btrfs_tree_read_unlock(path->nodes[i]);
4462 path->locks[i] = 0;
4463 }
4464 free_extent_buffer(path->nodes[i]);
4465 path->nodes[i] = NULL;
4466 }
4467
4468 next = c;
4469 ret = read_block_for_search(root, path, &next, level,
4470 slot, &key);
4471 if (ret == -EAGAIN)
4472 goto again;
4473
4474 if (ret < 0) {
4475 btrfs_release_path(path);
4476 goto done;
4477 }
4478
4479 if (!path->skip_locking) {
4480 ret = btrfs_try_tree_read_lock(next);
4481 if (!ret && time_seq) {
4482
4483
4484
4485
4486
4487
4488
4489 free_extent_buffer(next);
4490 btrfs_release_path(path);
4491 cond_resched();
4492 goto again;
4493 }
4494 if (!ret)
4495 btrfs_tree_read_lock(next);
4496 }
4497 break;
4498 }
4499 path->slots[level] = slot;
4500 while (1) {
4501 level--;
4502 path->nodes[level] = next;
4503 path->slots[level] = 0;
4504 if (!path->skip_locking)
4505 path->locks[level] = BTRFS_READ_LOCK;
4506 if (!level)
4507 break;
4508
4509 ret = read_block_for_search(root, path, &next, level,
4510 0, &key);
4511 if (ret == -EAGAIN)
4512 goto again;
4513
4514 if (ret < 0) {
4515 btrfs_release_path(path);
4516 goto done;
4517 }
4518
4519 if (!path->skip_locking)
4520 btrfs_tree_read_lock(next);
4521 }
4522 ret = 0;
4523done:
4524 unlock_up(path, 0, 1, 0, NULL);
4525
4526 return ret;
4527}
4528
4529
4530
4531
4532
4533
4534
4535int btrfs_previous_item(struct btrfs_root *root,
4536 struct btrfs_path *path, u64 min_objectid,
4537 int type)
4538{
4539 struct btrfs_key found_key;
4540 struct extent_buffer *leaf;
4541 u32 nritems;
4542 int ret;
4543
4544 while (1) {
4545 if (path->slots[0] == 0) {
4546 ret = btrfs_prev_leaf(root, path);
4547 if (ret != 0)
4548 return ret;
4549 } else {
4550 path->slots[0]--;
4551 }
4552 leaf = path->nodes[0];
4553 nritems = btrfs_header_nritems(leaf);
4554 if (nritems == 0)
4555 return 1;
4556 if (path->slots[0] == nritems)
4557 path->slots[0]--;
4558
4559 btrfs_item_key_to_cpu(leaf, &found_key, path->slots[0]);
4560 if (found_key.objectid < min_objectid)
4561 break;
4562 if (found_key.type == type)
4563 return 0;
4564 if (found_key.objectid == min_objectid &&
4565 found_key.type < type)
4566 break;
4567 }
4568 return 1;
4569}
4570
4571
4572
4573
4574
4575
4576
4577int btrfs_previous_extent_item(struct btrfs_root *root,
4578 struct btrfs_path *path, u64 min_objectid)
4579{
4580 struct btrfs_key found_key;
4581 struct extent_buffer *leaf;
4582 u32 nritems;
4583 int ret;
4584
4585 while (1) {
4586 if (path->slots[0] == 0) {
4587 ret = btrfs_prev_leaf(root, path);
4588 if (ret != 0)
4589 return ret;
4590 } else {
4591 path->slots[0]--;
4592 }
4593 leaf = path->nodes[0];
4594 nritems = btrfs_header_nritems(leaf);
4595 if (nritems == 0)
4596 return 1;
4597 if (path->slots[0] == nritems)
4598 path->slots[0]--;
4599
4600 btrfs_item_key_to_cpu(leaf, &found_key, path->slots[0]);
4601 if (found_key.objectid < min_objectid)
4602 break;
4603 if (found_key.type == BTRFS_EXTENT_ITEM_KEY ||
4604 found_key.type == BTRFS_METADATA_ITEM_KEY)
4605 return 0;
4606 if (found_key.objectid == min_objectid &&
4607 found_key.type < BTRFS_EXTENT_ITEM_KEY)
4608 break;
4609 }
4610 return 1;
4611}
4612