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