1 // SPDX-License-Identifier: GPL-2.0
2 /*
3 * Copyright (C) 2007,2008 Oracle. All rights reserved.
4 */
5
6 #include <linux/sched.h>
7 #include <linux/slab.h>
8 #include <linux/rbtree.h>
9 #include <linux/mm.h>
10 #include <linux/error-injection.h>
11 #include "messages.h"
12 #include "ctree.h"
13 #include "disk-io.h"
14 #include "transaction.h"
15 #include "print-tree.h"
16 #include "locking.h"
17 #include "volumes.h"
18 #include "qgroup.h"
19 #include "tree-mod-log.h"
20 #include "tree-checker.h"
21 #include "fs.h"
22 #include "accessors.h"
23 #include "extent-tree.h"
24 #include "relocation.h"
25 #include "file-item.h"
26
27 static struct kmem_cache *btrfs_path_cachep;
28
29 static int split_node(struct btrfs_trans_handle *trans, struct btrfs_root
30 *root, struct btrfs_path *path, int level);
31 static int split_leaf(struct btrfs_trans_handle *trans, struct btrfs_root *root,
32 const struct btrfs_key *ins_key, struct btrfs_path *path,
33 int data_size, int extend);
34 static int push_node_left(struct btrfs_trans_handle *trans,
35 struct extent_buffer *dst,
36 struct extent_buffer *src, int empty);
37 static int balance_node_right(struct btrfs_trans_handle *trans,
38 struct extent_buffer *dst_buf,
39 struct extent_buffer *src_buf);
40
41 static const struct btrfs_csums {
42 u16 size;
43 const char name[10];
44 const char driver[12];
45 } btrfs_csums[] = {
46 [BTRFS_CSUM_TYPE_CRC32] = { .size = 4, .name = "crc32c" },
47 [BTRFS_CSUM_TYPE_XXHASH] = { .size = 8, .name = "xxhash64" },
48 [BTRFS_CSUM_TYPE_SHA256] = { .size = 32, .name = "sha256" },
49 [BTRFS_CSUM_TYPE_BLAKE2] = { .size = 32, .name = "blake2b",
50 .driver = "blake2b-256" },
51 };
52
53 /*
54 * The leaf data grows from end-to-front in the node. this returns the address
55 * of the start of the last item, which is the stop of the leaf data stack.
56 */
57 static unsigned int leaf_data_end(const struct extent_buffer *leaf)
58 {
59 u32 nr = btrfs_header_nritems(leaf);
60
61 if (nr == 0)
62 return BTRFS_LEAF_DATA_SIZE(leaf->fs_info);
63 return btrfs_item_offset(leaf, nr - 1);
64 }
65
66 /*
67 * Move data in a @leaf (using memmove, safe for overlapping ranges).
68 *
69 * @leaf: leaf that we're doing a memmove on
70 * @dst_offset: item data offset we're moving to
71 * @src_offset: item data offset were' moving from
72 * @len: length of the data we're moving
73 *
74 * Wrapper around memmove_extent_buffer() that takes into account the header on
75 * the leaf. The btrfs_item offset's start directly after the header, so we
76 * have to adjust any offsets to account for the header in the leaf. This
77 * handles that math to simplify the callers.
78 */
79 static inline void memmove_leaf_data(const struct extent_buffer *leaf,
80 unsigned long dst_offset,
81 unsigned long src_offset,
82 unsigned long len)
83 {
84 memmove_extent_buffer(leaf, btrfs_item_nr_offset(leaf, 0) + dst_offset,
85 btrfs_item_nr_offset(leaf, 0) + src_offset, len);
86 }
87
88 /*
89 * Copy item data from @src into @dst at the given @offset.
90 *
91 * @dst: destination leaf that we're copying into
92 * @src: source leaf that we're copying from
93 * @dst_offset: item data offset we're copying to
94 * @src_offset: item data offset were' copying from
95 * @len: length of the data we're copying
96 *
97 * Wrapper around copy_extent_buffer() that takes into account the header on
98 * the leaf. The btrfs_item offset's start directly after the header, so we
99 * have to adjust any offsets to account for the header in the leaf. This
100 * handles that math to simplify the callers.
101 */
102 static inline void copy_leaf_data(const struct extent_buffer *dst,
103 const struct extent_buffer *src,
104 unsigned long dst_offset,
105 unsigned long src_offset, unsigned long len)
106 {
107 copy_extent_buffer(dst, src, btrfs_item_nr_offset(dst, 0) + dst_offset,
108 btrfs_item_nr_offset(src, 0) + src_offset, len);
109 }
110
111 /*
112 * Move items in a @leaf (using memmove).
113 *
114 * @dst: destination leaf for the items
115 * @dst_item: the item nr we're copying into
116 * @src_item: the item nr we're copying from
117 * @nr_items: the number of items to copy
118 *
119 * Wrapper around memmove_extent_buffer() that does the math to get the
120 * appropriate offsets into the leaf from the item numbers.
121 */
122 static inline void memmove_leaf_items(const struct extent_buffer *leaf,
123 int dst_item, int src_item, int nr_items)
124 {
125 memmove_extent_buffer(leaf, btrfs_item_nr_offset(leaf, dst_item),
126 btrfs_item_nr_offset(leaf, src_item),
127 nr_items * sizeof(struct btrfs_item));
128 }
129
130 /*
131 * Copy items from @src into @dst at the given @offset.
132 *
133 * @dst: destination leaf for the items
134 * @src: source leaf for the items
135 * @dst_item: the item nr we're copying into
136 * @src_item: the item nr we're copying from
137 * @nr_items: the number of items to copy
138 *
139 * Wrapper around copy_extent_buffer() that does the math to get the
140 * appropriate offsets into the leaf from the item numbers.
141 */
142 static inline void copy_leaf_items(const struct extent_buffer *dst,
143 const struct extent_buffer *src,
144 int dst_item, int src_item, int nr_items)
145 {
146 copy_extent_buffer(dst, src, btrfs_item_nr_offset(dst, dst_item),
147 btrfs_item_nr_offset(src, src_item),
148 nr_items * sizeof(struct btrfs_item));
149 }
150
151 /* This exists for btrfs-progs usages. */
152 u16 btrfs_csum_type_size(u16 type)
153 {
154 return btrfs_csums[type].size;
155 }
156
157 int btrfs_super_csum_size(const struct btrfs_super_block *s)
158 {
159 u16 t = btrfs_super_csum_type(s);
160 /*
161 * csum type is validated at mount time
162 */
163 return btrfs_csum_type_size(t);
164 }
165
166 const char *btrfs_super_csum_name(u16 csum_type)
167 {
168 /* csum type is validated at mount time */
169 return btrfs_csums[csum_type].name;
170 }
171
172 /*
173 * Return driver name if defined, otherwise the name that's also a valid driver
174 * name
175 */
176 const char *btrfs_super_csum_driver(u16 csum_type)
177 {
178 /* csum type is validated at mount time */
179 return btrfs_csums[csum_type].driver[0] ?
180 btrfs_csums[csum_type].driver :
181 btrfs_csums[csum_type].name;
182 }
183
184 size_t __attribute_const__ btrfs_get_num_csums(void)
185 {
186 return ARRAY_SIZE(btrfs_csums);
187 }
188
189 struct btrfs_path *btrfs_alloc_path(void)
190 {
191 might_sleep();
192
193 return kmem_cache_zalloc(btrfs_path_cachep, GFP_NOFS);
194 }
195
196 /* this also releases the path */
197 void btrfs_free_path(struct btrfs_path *p)
198 {
199 if (!p)
200 return;
201 btrfs_release_path(p);
202 kmem_cache_free(btrfs_path_cachep, p);
203 }
204
205 /*
206 * path release drops references on the extent buffers in the path
207 * and it drops any locks held by this path
208 *
209 * It is safe to call this on paths that no locks or extent buffers held.
210 */
211 noinline void btrfs_release_path(struct btrfs_path *p)
212 {
213 int i;
214
215 for (i = 0; i < BTRFS_MAX_LEVEL; i++) {
216 p->slots[i] = 0;
217 if (!p->nodes[i])
218 continue;
219 if (p->locks[i]) {
220 btrfs_tree_unlock_rw(p->nodes[i], p->locks[i]);
221 p->locks[i] = 0;
222 }
223 free_extent_buffer(p->nodes[i]);
224 p->nodes[i] = NULL;
225 }
226 }
227
228 /*
229 * We want the transaction abort to print stack trace only for errors where the
230 * cause could be a bug, eg. due to ENOSPC, and not for common errors that are
231 * caused by external factors.
232 */
233 bool __cold abort_should_print_stack(int error)
234 {
235 switch (error) {
236 case -EIO:
237 case -EROFS:
238 case -ENOMEM:
239 return false;
240 }
241 return true;
242 }
243
244 /*
245 * safely gets a reference on the root node of a tree. A lock
246 * is not taken, so a concurrent writer may put a different node
247 * at the root of the tree. See btrfs_lock_root_node for the
248 * looping required.
249 *
250 * The extent buffer returned by this has a reference taken, so
251 * it won't disappear. It may stop being the root of the tree
252 * at any time because there are no locks held.
253 */
254 struct extent_buffer *btrfs_root_node(struct btrfs_root *root)
255 {
256 struct extent_buffer *eb;
257
258 while (1) {
259 rcu_read_lock();
260 eb = rcu_dereference(root->node);
261
262 /*
263 * RCU really hurts here, we could free up the root node because
264 * it was COWed but we may not get the new root node yet so do
265 * the inc_not_zero dance and if it doesn't work then
266 * synchronize_rcu and try again.
267 */
268 if (atomic_inc_not_zero(&eb->refs)) {
269 rcu_read_unlock();
270 break;
271 }
272 rcu_read_unlock();
273 synchronize_rcu();
274 }
275 return eb;
276 }
277
278 /*
279 * Cowonly root (not-shareable trees, everything not subvolume or reloc roots),
280 * just get put onto a simple dirty list. Transaction walks this list to make
281 * sure they get properly updated on disk.
282 */
283 static void add_root_to_dirty_list(struct btrfs_root *root)
284 {
285 struct btrfs_fs_info *fs_info = root->fs_info;
286
287 if (test_bit(BTRFS_ROOT_DIRTY, &root->state) ||
288 !test_bit(BTRFS_ROOT_TRACK_DIRTY, &root->state))
289 return;
290
291 spin_lock(&fs_info->trans_lock);
292 if (!test_and_set_bit(BTRFS_ROOT_DIRTY, &root->state)) {
293 /* Want the extent tree to be the last on the list */
294 if (btrfs_root_id(root) == BTRFS_EXTENT_TREE_OBJECTID)
295 list_move_tail(&root->dirty_list,
296 &fs_info->dirty_cowonly_roots);
297 else
298 list_move(&root->dirty_list,
299 &fs_info->dirty_cowonly_roots);
300 }
301 spin_unlock(&fs_info->trans_lock);
302 }
303
304 /*
305 * used by snapshot creation to make a copy of a root for a tree with
306 * a given objectid. The buffer with the new root node is returned in
307 * cow_ret, and this func returns zero on success or a negative error code.
308 */
309 int btrfs_copy_root(struct btrfs_trans_handle *trans,
310 struct btrfs_root *root,
311 struct extent_buffer *buf,
312 struct extent_buffer **cow_ret, u64 new_root_objectid)
313 {
314 struct btrfs_fs_info *fs_info = root->fs_info;
315 struct extent_buffer *cow;
316 int ret = 0;
317 int level;
318 struct btrfs_disk_key disk_key;
319 u64 reloc_src_root = 0;
320
321 WARN_ON(test_bit(BTRFS_ROOT_SHAREABLE, &root->state) &&
322 trans->transid != fs_info->running_transaction->transid);
323 WARN_ON(test_bit(BTRFS_ROOT_SHAREABLE, &root->state) &&
324 trans->transid != btrfs_get_root_last_trans(root));
325
326 level = btrfs_header_level(buf);
327 if (level == 0)
328 btrfs_item_key(buf, &disk_key, 0);
329 else
330 btrfs_node_key(buf, &disk_key, 0);
331
332 if (new_root_objectid == BTRFS_TREE_RELOC_OBJECTID)
333 reloc_src_root = btrfs_header_owner(buf);
334 cow = btrfs_alloc_tree_block(trans, root, 0, new_root_objectid,
335 &disk_key, level, buf->start, 0,
336 reloc_src_root, BTRFS_NESTING_NEW_ROOT);
337 if (IS_ERR(cow))
338 return PTR_ERR(cow);
339
340 copy_extent_buffer_full(cow, buf);
341 btrfs_set_header_bytenr(cow, cow->start);
342 btrfs_set_header_generation(cow, trans->transid);
343 btrfs_set_header_backref_rev(cow, BTRFS_MIXED_BACKREF_REV);
344 btrfs_clear_header_flag(cow, BTRFS_HEADER_FLAG_WRITTEN |
345 BTRFS_HEADER_FLAG_RELOC);
346 if (new_root_objectid == BTRFS_TREE_RELOC_OBJECTID)
347 btrfs_set_header_flag(cow, BTRFS_HEADER_FLAG_RELOC);
348 else
349 btrfs_set_header_owner(cow, new_root_objectid);
350
351 write_extent_buffer_fsid(cow, fs_info->fs_devices->metadata_uuid);
352
353 WARN_ON(btrfs_header_generation(buf) > trans->transid);
354 if (new_root_objectid == BTRFS_TREE_RELOC_OBJECTID)
355 ret = btrfs_inc_ref(trans, root, cow, 1);
356 else
357 ret = btrfs_inc_ref(trans, root, cow, 0);
358 if (ret) {
359 btrfs_tree_unlock(cow);
360 free_extent_buffer(cow);
361 btrfs_abort_transaction(trans, ret);
362 return ret;
363 }
364
365 btrfs_mark_buffer_dirty(trans, cow);
366 *cow_ret = cow;
367 return 0;
368 }
369
370 /*
371 * check if the tree block can be shared by multiple trees
372 */
373 bool btrfs_block_can_be_shared(struct btrfs_trans_handle *trans,
374 struct btrfs_root *root,
375 struct extent_buffer *buf)
376 {
377 const u64 buf_gen = btrfs_header_generation(buf);
378
379 /*
380 * Tree blocks not in shareable trees and tree roots are never shared.
381 * If a block was allocated after the last snapshot and the block was
382 * not allocated by tree relocation, we know the block is not shared.
383 */
384
385 if (!test_bit(BTRFS_ROOT_SHAREABLE, &root->state))
386 return false;
387
388 if (buf == root->node)
389 return false;
390
391 if (buf_gen > btrfs_root_last_snapshot(&root->root_item) &&
392 !btrfs_header_flag(buf, BTRFS_HEADER_FLAG_RELOC))
393 return false;
394
395 if (buf != root->commit_root)
396 return true;
397
398 /*
399 * An extent buffer that used to be the commit root may still be shared
400 * because the tree height may have increased and it became a child of a
401 * higher level root. This can happen when snapshotting a subvolume
402 * created in the current transaction.
403 */
404 if (buf_gen == trans->transid)
405 return true;
406
407 return false;
408 }
409
410 static noinline int update_ref_for_cow(struct btrfs_trans_handle *trans,
411 struct btrfs_root *root,
412 struct extent_buffer *buf,
413 struct extent_buffer *cow,
414 int *last_ref)
415 {
416 struct btrfs_fs_info *fs_info = root->fs_info;
417 u64 refs;
418 u64 owner;
419 u64 flags;
420 int ret;
421
422 /*
423 * Backrefs update rules:
424 *
425 * Always use full backrefs for extent pointers in tree block
426 * allocated by tree relocation.
427 *
428 * If a shared tree block is no longer referenced by its owner
429 * tree (btrfs_header_owner(buf) == root->root_key.objectid),
430 * use full backrefs for extent pointers in tree block.
431 *
432 * If a tree block is been relocating
433 * (root->root_key.objectid == BTRFS_TREE_RELOC_OBJECTID),
434 * use full backrefs for extent pointers in tree block.
435 * The reason for this is some operations (such as drop tree)
436 * are only allowed for blocks use full backrefs.
437 */
438
439 if (btrfs_block_can_be_shared(trans, root, buf)) {
440 ret = btrfs_lookup_extent_info(trans, fs_info, buf->start,
441 btrfs_header_level(buf), 1,
442 &refs, &flags, NULL);
443 if (ret)
444 return ret;
445 if (unlikely(refs == 0)) {
446 btrfs_crit(fs_info,
447 "found 0 references for tree block at bytenr %llu level %d root %llu",
448 buf->start, btrfs_header_level(buf),
449 btrfs_root_id(root));
450 ret = -EUCLEAN;
451 btrfs_abort_transaction(trans, ret);
452 return ret;
453 }
454 } else {
455 refs = 1;
456 if (btrfs_root_id(root) == BTRFS_TREE_RELOC_OBJECTID ||
457 btrfs_header_backref_rev(buf) < BTRFS_MIXED_BACKREF_REV)
458 flags = BTRFS_BLOCK_FLAG_FULL_BACKREF;
459 else
460 flags = 0;
461 }
462
463 owner = btrfs_header_owner(buf);
464 if (unlikely(owner == BTRFS_TREE_RELOC_OBJECTID &&
465 !(flags & BTRFS_BLOCK_FLAG_FULL_BACKREF))) {
466 btrfs_crit(fs_info,
467 "found tree block at bytenr %llu level %d root %llu refs %llu flags %llx without full backref flag set",
468 buf->start, btrfs_header_level(buf),
469 btrfs_root_id(root), refs, flags);
470 ret = -EUCLEAN;
471 btrfs_abort_transaction(trans, ret);
472 return ret;
473 }
474
475 if (refs > 1) {
476 if ((owner == btrfs_root_id(root) ||
477 btrfs_root_id(root) == BTRFS_TREE_RELOC_OBJECTID) &&
478 !(flags & BTRFS_BLOCK_FLAG_FULL_BACKREF)) {
479 ret = btrfs_inc_ref(trans, root, buf, 1);
480 if (ret)
481 return ret;
482
483 if (btrfs_root_id(root) == BTRFS_TREE_RELOC_OBJECTID) {
484 ret = btrfs_dec_ref(trans, root, buf, 0);
485 if (ret)
486 return ret;
487 ret = btrfs_inc_ref(trans, root, cow, 1);
488 if (ret)
489 return ret;
490 }
491 ret = btrfs_set_disk_extent_flags(trans, buf,
492 BTRFS_BLOCK_FLAG_FULL_BACKREF);
493 if (ret)
494 return ret;
495 } else {
496
497 if (btrfs_root_id(root) == BTRFS_TREE_RELOC_OBJECTID)
498 ret = btrfs_inc_ref(trans, root, cow, 1);
499 else
500 ret = btrfs_inc_ref(trans, root, cow, 0);
501 if (ret)
502 return ret;
503 }
504 } else {
505 if (flags & BTRFS_BLOCK_FLAG_FULL_BACKREF) {
506 if (btrfs_root_id(root) == BTRFS_TREE_RELOC_OBJECTID)
507 ret = btrfs_inc_ref(trans, root, cow, 1);
508 else
509 ret = btrfs_inc_ref(trans, root, cow, 0);
510 if (ret)
511 return ret;
512 ret = btrfs_dec_ref(trans, root, buf, 1);
513 if (ret)
514 return ret;
515 }
516 btrfs_clear_buffer_dirty(trans, buf);
517 *last_ref = 1;
518 }
519 return 0;
520 }
521
522 /*
523 * does the dirty work in cow of a single block. The parent block (if
524 * supplied) is updated to point to the new cow copy. The new buffer is marked
525 * dirty and returned locked. If you modify the block it needs to be marked
526 * dirty again.
527 *
528 * search_start -- an allocation hint for the new block
529 *
530 * empty_size -- a hint that you plan on doing more cow. This is the size in
531 * bytes the allocator should try to find free next to the block it returns.
532 * This is just a hint and may be ignored by the allocator.
533 */
534 int btrfs_force_cow_block(struct btrfs_trans_handle *trans,
535 struct btrfs_root *root,
536 struct extent_buffer *buf,
537 struct extent_buffer *parent, int parent_slot,
538 struct extent_buffer **cow_ret,
539 u64 search_start, u64 empty_size,
540 enum btrfs_lock_nesting nest)
541 {
542 struct btrfs_fs_info *fs_info = root->fs_info;
543 struct btrfs_disk_key disk_key;
544 struct extent_buffer *cow;
545 int level, ret;
546 int last_ref = 0;
547 int unlock_orig = 0;
548 u64 parent_start = 0;
549 u64 reloc_src_root = 0;
550
551 if (*cow_ret == buf)
552 unlock_orig = 1;
553
554 btrfs_assert_tree_write_locked(buf);
555
556 WARN_ON(test_bit(BTRFS_ROOT_SHAREABLE, &root->state) &&
557 trans->transid != fs_info->running_transaction->transid);
558 WARN_ON(test_bit(BTRFS_ROOT_SHAREABLE, &root->state) &&
559 trans->transid != btrfs_get_root_last_trans(root));
560
561 level = btrfs_header_level(buf);
562
563 if (level == 0)
564 btrfs_item_key(buf, &disk_key, 0);
565 else
566 btrfs_node_key(buf, &disk_key, 0);
567
568 if (btrfs_root_id(root) == BTRFS_TREE_RELOC_OBJECTID) {
569 if (parent)
570 parent_start = parent->start;
571 reloc_src_root = btrfs_header_owner(buf);
572 }
573 cow = btrfs_alloc_tree_block(trans, root, parent_start,
574 btrfs_root_id(root), &disk_key, level,
575 search_start, empty_size, reloc_src_root, nest);
576 if (IS_ERR(cow))
577 return PTR_ERR(cow);
578
579 /* cow is set to blocking by btrfs_init_new_buffer */
580
581 copy_extent_buffer_full(cow, buf);
582 btrfs_set_header_bytenr(cow, cow->start);
583 btrfs_set_header_generation(cow, trans->transid);
584 btrfs_set_header_backref_rev(cow, BTRFS_MIXED_BACKREF_REV);
585 btrfs_clear_header_flag(cow, BTRFS_HEADER_FLAG_WRITTEN |
586 BTRFS_HEADER_FLAG_RELOC);
587 if (btrfs_root_id(root) == BTRFS_TREE_RELOC_OBJECTID)
588 btrfs_set_header_flag(cow, BTRFS_HEADER_FLAG_RELOC);
589 else
590 btrfs_set_header_owner(cow, btrfs_root_id(root));
591
592 write_extent_buffer_fsid(cow, fs_info->fs_devices->metadata_uuid);
593
594 ret = update_ref_for_cow(trans, root, buf, cow, &last_ref);
595 if (ret) {
596 btrfs_abort_transaction(trans, ret);
597 goto error_unlock_cow;
598 }
599
600 if (test_bit(BTRFS_ROOT_SHAREABLE, &root->state)) {
601 ret = btrfs_reloc_cow_block(trans, root, buf, cow);
602 if (ret) {
603 btrfs_abort_transaction(trans, ret);
604 goto error_unlock_cow;
605 }
606 }
607
608 if (buf == root->node) {
609 WARN_ON(parent && parent != buf);
610 if (btrfs_root_id(root) == BTRFS_TREE_RELOC_OBJECTID ||
611 btrfs_header_backref_rev(buf) < BTRFS_MIXED_BACKREF_REV)
612 parent_start = buf->start;
613
614 ret = btrfs_tree_mod_log_insert_root(root->node, cow, true);
615 if (ret < 0) {
616 btrfs_abort_transaction(trans, ret);
617 goto error_unlock_cow;
618 }
619 atomic_inc(&cow->refs);
620 rcu_assign_pointer(root->node, cow);
621
622 ret = btrfs_free_tree_block(trans, btrfs_root_id(root), buf,
623 parent_start, last_ref);
624 free_extent_buffer(buf);
625 add_root_to_dirty_list(root);
626 if (ret < 0) {
627 btrfs_abort_transaction(trans, ret);
628 goto error_unlock_cow;
629 }
630 } else {
631 WARN_ON(trans->transid != btrfs_header_generation(parent));
632 ret = btrfs_tree_mod_log_insert_key(parent, parent_slot,
633 BTRFS_MOD_LOG_KEY_REPLACE);
634 if (ret) {
635 btrfs_abort_transaction(trans, ret);
636 goto error_unlock_cow;
637 }
638 btrfs_set_node_blockptr(parent, parent_slot,
639 cow->start);
640 btrfs_set_node_ptr_generation(parent, parent_slot,
641 trans->transid);
642 btrfs_mark_buffer_dirty(trans, parent);
643 if (last_ref) {
644 ret = btrfs_tree_mod_log_free_eb(buf);
645 if (ret) {
646 btrfs_abort_transaction(trans, ret);
647 goto error_unlock_cow;
648 }
649 }
650 ret = btrfs_free_tree_block(trans, btrfs_root_id(root), buf,
651 parent_start, last_ref);
652 if (ret < 0) {
653 btrfs_abort_transaction(trans, ret);
654 goto error_unlock_cow;
655 }
656 }
657 if (unlock_orig)
658 btrfs_tree_unlock(buf);
659 free_extent_buffer_stale(buf);
660 btrfs_mark_buffer_dirty(trans, cow);
661 *cow_ret = cow;
662 return 0;
663
664 error_unlock_cow:
665 btrfs_tree_unlock(cow);
666 free_extent_buffer(cow);
667 return ret;
668 }
669
670 static inline int should_cow_block(struct btrfs_trans_handle *trans,
671 struct btrfs_root *root,
672 struct extent_buffer *buf)
673 {
674 if (btrfs_is_testing(root->fs_info))
675 return 0;
676
677 /* Ensure we can see the FORCE_COW bit */
678 smp_mb__before_atomic();
679
680 /*
681 * We do not need to cow a block if
682 * 1) this block is not created or changed in this transaction;
683 * 2) this block does not belong to TREE_RELOC tree;
684 * 3) the root is not forced COW.
685 *
686 * What is forced COW:
687 * when we create snapshot during committing the transaction,
688 * after we've finished copying src root, we must COW the shared
689 * block to ensure the metadata consistency.
690 */
691 if (btrfs_header_generation(buf) == trans->transid &&
692 !btrfs_header_flag(buf, BTRFS_HEADER_FLAG_WRITTEN) &&
693 !(btrfs_root_id(root) != BTRFS_TREE_RELOC_OBJECTID &&
694 btrfs_header_flag(buf, BTRFS_HEADER_FLAG_RELOC)) &&
695 !test_bit(BTRFS_ROOT_FORCE_COW, &root->state))
696 return 0;
697 return 1;
698 }
699
700 /*
701 * COWs a single block, see btrfs_force_cow_block() for the real work.
702 * This version of it has extra checks so that a block isn't COWed more than
703 * once per transaction, as long as it hasn't been written yet
704 */
705 int btrfs_cow_block(struct btrfs_trans_handle *trans,
706 struct btrfs_root *root, struct extent_buffer *buf,
707 struct extent_buffer *parent, int parent_slot,
708 struct extent_buffer **cow_ret,
709 enum btrfs_lock_nesting nest)
710 {
711 struct btrfs_fs_info *fs_info = root->fs_info;
712 u64 search_start;
713 int ret;
714
715 if (unlikely(test_bit(BTRFS_ROOT_DELETING, &root->state))) {
716 btrfs_abort_transaction(trans, -EUCLEAN);
717 btrfs_crit(fs_info,
718 "attempt to COW block %llu on root %llu that is being deleted",
719 buf->start, btrfs_root_id(root));
720 return -EUCLEAN;
721 }
722
723 /*
724 * COWing must happen through a running transaction, which always
725 * matches the current fs generation (it's a transaction with a state
726 * less than TRANS_STATE_UNBLOCKED). If it doesn't, then turn the fs
727 * into error state to prevent the commit of any transaction.
728 */
729 if (unlikely(trans->transaction != fs_info->running_transaction ||
730 trans->transid != fs_info->generation)) {
731 btrfs_abort_transaction(trans, -EUCLEAN);
732 btrfs_crit(fs_info,
733 "unexpected transaction when attempting to COW block %llu on root %llu, transaction %llu running transaction %llu fs generation %llu",
734 buf->start, btrfs_root_id(root), trans->transid,
735 fs_info->running_transaction->transid,
736 fs_info->generation);
737 return -EUCLEAN;
738 }
739
740 if (!should_cow_block(trans, root, buf)) {
741 *cow_ret = buf;
742 return 0;
743 }
744
745 search_start = round_down(buf->start, SZ_1G);
746
747 /*
748 * Before CoWing this block for later modification, check if it's
749 * the subtree root and do the delayed subtree trace if needed.
750 *
751 * Also We don't care about the error, as it's handled internally.
752 */
753 btrfs_qgroup_trace_subtree_after_cow(trans, root, buf);
754 ret = btrfs_force_cow_block(trans, root, buf, parent, parent_slot,
755 cow_ret, search_start, 0, nest);
756
757 trace_btrfs_cow_block(root, buf, *cow_ret);
758
759 return ret;
760 }
761 ALLOW_ERROR_INJECTION(btrfs_cow_block, ERRNO);
762
763 /*
764 * same as comp_keys only with two btrfs_key's
765 */
766 int __pure btrfs_comp_cpu_keys(const struct btrfs_key *k1, const struct btrfs_key *k2)
767 {
768 if (k1->objectid > k2->objectid)
769 return 1;
770 if (k1->objectid < k2->objectid)
771 return -1;
772 if (k1->type > k2->type)
773 return 1;
774 if (k1->type < k2->type)
775 return -1;
776 if (k1->offset > k2->offset)
777 return 1;
778 if (k1->offset < k2->offset)
779 return -1;
780 return 0;
781 }
782
783 /*
784 * Search for a key in the given extent_buffer.
785 *
786 * The lower boundary for the search is specified by the slot number @first_slot.
787 * Use a value of 0 to search over the whole extent buffer. Works for both
788 * leaves and nodes.
789 *
790 * The slot in the extent buffer is returned via @slot. If the key exists in the
791 * extent buffer, then @slot will point to the slot where the key is, otherwise
792 * it points to the slot where you would insert the key.
793 *
794 * Slot may point to the total number of items (i.e. one position beyond the last
795 * key) if the key is bigger than the last key in the extent buffer.
796 */
797 int btrfs_bin_search(struct extent_buffer *eb, int first_slot,
798 const struct btrfs_key *key, int *slot)
799 {
800 unsigned long p;
801 int item_size;
802 /*
803 * Use unsigned types for the low and high slots, so that we get a more
804 * efficient division in the search loop below.
805 */
806 u32 low = first_slot;
807 u32 high = btrfs_header_nritems(eb);
808 int ret;
809 const int key_size = sizeof(struct btrfs_disk_key);
810
811 if (unlikely(low > high)) {
812 btrfs_err(eb->fs_info,
813 "%s: low (%u) > high (%u) eb %llu owner %llu level %d",
814 __func__, low, high, eb->start,
815 btrfs_header_owner(eb), btrfs_header_level(eb));
816 return -EINVAL;
817 }
818
819 if (btrfs_header_level(eb) == 0) {
820 p = offsetof(struct btrfs_leaf, items);
821 item_size = sizeof(struct btrfs_item);
822 } else {
823 p = offsetof(struct btrfs_node, ptrs);
824 item_size = sizeof(struct btrfs_key_ptr);
825 }
826
827 while (low < high) {
828 const int unit_size = eb->folio_size;
829 unsigned long oil;
830 unsigned long offset;
831 struct btrfs_disk_key *tmp;
832 struct btrfs_disk_key unaligned;
833 int mid;
834
835 mid = (low + high) / 2;
836 offset = p + mid * item_size;
837 oil = get_eb_offset_in_folio(eb, offset);
838
839 if (oil + key_size <= unit_size) {
840 const unsigned long idx = get_eb_folio_index(eb, offset);
841 char *kaddr = folio_address(eb->folios[idx]);
842
843 oil = get_eb_offset_in_folio(eb, offset);
844 tmp = (struct btrfs_disk_key *)(kaddr + oil);
845 } else {
846 read_extent_buffer(eb, &unaligned, offset, key_size);
847 tmp = &unaligned;
848 }
849
850 ret = btrfs_comp_keys(tmp, key);
851
852 if (ret < 0)
853 low = mid + 1;
854 else if (ret > 0)
855 high = mid;
856 else {
857 *slot = mid;
858 return 0;
859 }
860 }
861 *slot = low;
862 return 1;
863 }
864
865 static void root_add_used_bytes(struct btrfs_root *root)
866 {
867 spin_lock(&root->accounting_lock);
868 btrfs_set_root_used(&root->root_item,
869 btrfs_root_used(&root->root_item) + root->fs_info->nodesize);
870 spin_unlock(&root->accounting_lock);
871 }
872
873 static void root_sub_used_bytes(struct btrfs_root *root)
874 {
875 spin_lock(&root->accounting_lock);
876 btrfs_set_root_used(&root->root_item,
877 btrfs_root_used(&root->root_item) - root->fs_info->nodesize);
878 spin_unlock(&root->accounting_lock);
879 }
880
881 /* given a node and slot number, this reads the blocks it points to. The
882 * extent buffer is returned with a reference taken (but unlocked).
883 */
884 struct extent_buffer *btrfs_read_node_slot(struct extent_buffer *parent,
885 int slot)
886 {
887 int level = btrfs_header_level(parent);
888 struct btrfs_tree_parent_check check = { 0 };
889 struct extent_buffer *eb;
890
891 if (slot < 0 || slot >= btrfs_header_nritems(parent))
892 return ERR_PTR(-ENOENT);
893
894 ASSERT(level);
895
896 check.level = level - 1;
897 check.transid = btrfs_node_ptr_generation(parent, slot);
898 check.owner_root = btrfs_header_owner(parent);
899 check.has_first_key = true;
900 btrfs_node_key_to_cpu(parent, &check.first_key, slot);
901
902 eb = read_tree_block(parent->fs_info, btrfs_node_blockptr(parent, slot),
903 &check);
904 if (IS_ERR(eb))
905 return eb;
906 if (!extent_buffer_uptodate(eb)) {
907 free_extent_buffer(eb);
908 return ERR_PTR(-EIO);
909 }
910
911 return eb;
912 }
913
914 /*
915 * node level balancing, used to make sure nodes are in proper order for
916 * item deletion. We balance from the top down, so we have to make sure
917 * that a deletion won't leave an node completely empty later on.
918 */
919 static noinline int balance_level(struct btrfs_trans_handle *trans,
920 struct btrfs_root *root,
921 struct btrfs_path *path, int level)
922 {
923 struct btrfs_fs_info *fs_info = root->fs_info;
924 struct extent_buffer *right = NULL;
925 struct extent_buffer *mid;
926 struct extent_buffer *left = NULL;
927 struct extent_buffer *parent = NULL;
928 int ret = 0;
929 int wret;
930 int pslot;
931 int orig_slot = path->slots[level];
932 u64 orig_ptr;
933
934 ASSERT(level > 0);
935
936 mid = path->nodes[level];
937
938 WARN_ON(path->locks[level] != BTRFS_WRITE_LOCK);
939 WARN_ON(btrfs_header_generation(mid) != trans->transid);
940
941 orig_ptr = btrfs_node_blockptr(mid, orig_slot);
942
943 if (level < BTRFS_MAX_LEVEL - 1) {
944 parent = path->nodes[level + 1];
945 pslot = path->slots[level + 1];
946 }
947
948 /*
949 * deal with the case where there is only one pointer in the root
950 * by promoting the node below to a root
951 */
952 if (!parent) {
953 struct extent_buffer *child;
954
955 if (btrfs_header_nritems(mid) != 1)
956 return 0;
957
958 /* promote the child to a root */
959 child = btrfs_read_node_slot(mid, 0);
960 if (IS_ERR(child)) {
961 ret = PTR_ERR(child);
962 goto out;
963 }
964
965 btrfs_tree_lock(child);
966 ret = btrfs_cow_block(trans, root, child, mid, 0, &child,
967 BTRFS_NESTING_COW);
968 if (ret) {
969 btrfs_tree_unlock(child);
970 free_extent_buffer(child);
971 goto out;
972 }
973
974 ret = btrfs_tree_mod_log_insert_root(root->node, child, true);
975 if (ret < 0) {
976 btrfs_tree_unlock(child);
977 free_extent_buffer(child);
978 btrfs_abort_transaction(trans, ret);
979 goto out;
980 }
981 rcu_assign_pointer(root->node, child);
982
983 add_root_to_dirty_list(root);
984 btrfs_tree_unlock(child);
985
986 path->locks[level] = 0;
987 path->nodes[level] = NULL;
988 btrfs_clear_buffer_dirty(trans, mid);
989 btrfs_tree_unlock(mid);
990 /* once for the path */
991 free_extent_buffer(mid);
992
993 root_sub_used_bytes(root);
994 ret = btrfs_free_tree_block(trans, btrfs_root_id(root), mid, 0, 1);
995 /* once for the root ptr */
996 free_extent_buffer_stale(mid);
997 if (ret < 0) {
998 btrfs_abort_transaction(trans, ret);
999 goto out;
1000 }
1001 return 0;
1002 }
1003 if (btrfs_header_nritems(mid) >
1004 BTRFS_NODEPTRS_PER_BLOCK(fs_info) / 4)
1005 return 0;
1006
1007 if (pslot) {
1008 left = btrfs_read_node_slot(parent, pslot - 1);
1009 if (IS_ERR(left)) {
1010 ret = PTR_ERR(left);
1011 left = NULL;
1012 goto out;
1013 }
1014
1015 btrfs_tree_lock_nested(left, BTRFS_NESTING_LEFT);
1016 wret = btrfs_cow_block(trans, root, left,
1017 parent, pslot - 1, &left,
1018 BTRFS_NESTING_LEFT_COW);
1019 if (wret) {
1020 ret = wret;
1021 goto out;
1022 }
1023 }
1024
1025 if (pslot + 1 < btrfs_header_nritems(parent)) {
1026 right = btrfs_read_node_slot(parent, pslot + 1);
1027 if (IS_ERR(right)) {
1028 ret = PTR_ERR(right);
1029 right = NULL;
1030 goto out;
1031 }
1032
1033 btrfs_tree_lock_nested(right, BTRFS_NESTING_RIGHT);
1034 wret = btrfs_cow_block(trans, root, right,
1035 parent, pslot + 1, &right,
1036 BTRFS_NESTING_RIGHT_COW);
1037 if (wret) {
1038 ret = wret;
1039 goto out;
1040 }
1041 }
1042
1043 /* first, try to make some room in the middle buffer */
1044 if (left) {
1045 orig_slot += btrfs_header_nritems(left);
1046 wret = push_node_left(trans, left, mid, 1);
1047 if (wret < 0)
1048 ret = wret;
1049 }
1050
1051 /*
1052 * then try to empty the right most buffer into the middle
1053 */
1054 if (right) {
1055 wret = push_node_left(trans, mid, right, 1);
1056 if (wret < 0 && wret != -ENOSPC)
1057 ret = wret;
1058 if (btrfs_header_nritems(right) == 0) {
1059 btrfs_clear_buffer_dirty(trans, right);
1060 btrfs_tree_unlock(right);
1061 ret = btrfs_del_ptr(trans, root, path, level + 1, pslot + 1);
1062 if (ret < 0) {
1063 free_extent_buffer_stale(right);
1064 right = NULL;
1065 goto out;
1066 }
1067 root_sub_used_bytes(root);
1068 ret = btrfs_free_tree_block(trans, btrfs_root_id(root),
1069 right, 0, 1);
1070 free_extent_buffer_stale(right);
1071 right = NULL;
1072 if (ret < 0) {
1073 btrfs_abort_transaction(trans, ret);
1074 goto out;
1075 }
1076 } else {
1077 struct btrfs_disk_key right_key;
1078 btrfs_node_key(right, &right_key, 0);
1079 ret = btrfs_tree_mod_log_insert_key(parent, pslot + 1,
1080 BTRFS_MOD_LOG_KEY_REPLACE);
1081 if (ret < 0) {
1082 btrfs_abort_transaction(trans, ret);
1083 goto out;
1084 }
1085 btrfs_set_node_key(parent, &right_key, pslot + 1);
1086 btrfs_mark_buffer_dirty(trans, parent);
1087 }
1088 }
1089 if (btrfs_header_nritems(mid) == 1) {
1090 /*
1091 * we're not allowed to leave a node with one item in the
1092 * tree during a delete. A deletion from lower in the tree
1093 * could try to delete the only pointer in this node.
1094 * So, pull some keys from the left.
1095 * There has to be a left pointer at this point because
1096 * otherwise we would have pulled some pointers from the
1097 * right
1098 */
1099 if (unlikely(!left)) {
1100 btrfs_crit(fs_info,
1101 "missing left child when middle child only has 1 item, parent bytenr %llu level %d mid bytenr %llu root %llu",
1102 parent->start, btrfs_header_level(parent),
1103 mid->start, btrfs_root_id(root));
1104 ret = -EUCLEAN;
1105 btrfs_abort_transaction(trans, ret);
1106 goto out;
1107 }
1108 wret = balance_node_right(trans, mid, left);
1109 if (wret < 0) {
1110 ret = wret;
1111 goto out;
1112 }
1113 if (wret == 1) {
1114 wret = push_node_left(trans, left, mid, 1);
1115 if (wret < 0)
1116 ret = wret;
1117 }
1118 BUG_ON(wret == 1);
1119 }
1120 if (btrfs_header_nritems(mid) == 0) {
1121 btrfs_clear_buffer_dirty(trans, mid);
1122 btrfs_tree_unlock(mid);
1123 ret = btrfs_del_ptr(trans, root, path, level + 1, pslot);
1124 if (ret < 0) {
1125 free_extent_buffer_stale(mid);
1126 mid = NULL;
1127 goto out;
1128 }
1129 root_sub_used_bytes(root);
1130 ret = btrfs_free_tree_block(trans, btrfs_root_id(root), mid, 0, 1);
1131 free_extent_buffer_stale(mid);
1132 mid = NULL;
1133 if (ret < 0) {
1134 btrfs_abort_transaction(trans, ret);
1135 goto out;
1136 }
1137 } else {
1138 /* update the parent key to reflect our changes */
1139 struct btrfs_disk_key mid_key;
1140 btrfs_node_key(mid, &mid_key, 0);
1141 ret = btrfs_tree_mod_log_insert_key(parent, pslot,
1142 BTRFS_MOD_LOG_KEY_REPLACE);
1143 if (ret < 0) {
1144 btrfs_abort_transaction(trans, ret);
1145 goto out;
1146 }
1147 btrfs_set_node_key(parent, &mid_key, pslot);
1148 btrfs_mark_buffer_dirty(trans, parent);
1149 }
1150
1151 /* update the path */
1152 if (left) {
1153 if (btrfs_header_nritems(left) > orig_slot) {
1154 atomic_inc(&left->refs);
1155 /* left was locked after cow */
1156 path->nodes[level] = left;
1157 path->slots[level + 1] -= 1;
1158 path->slots[level] = orig_slot;
1159 if (mid) {
1160 btrfs_tree_unlock(mid);
1161 free_extent_buffer(mid);
1162 }
1163 } else {
1164 orig_slot -= btrfs_header_nritems(left);
1165 path->slots[level] = orig_slot;
1166 }
1167 }
1168 /* double check we haven't messed things up */
1169 if (orig_ptr !=
1170 btrfs_node_blockptr(path->nodes[level], path->slots[level]))
1171 BUG();
1172 out:
1173 if (right) {
1174 btrfs_tree_unlock(right);
1175 free_extent_buffer(right);
1176 }
1177 if (left) {
1178 if (path->nodes[level] != left)
1179 btrfs_tree_unlock(left);
1180 free_extent_buffer(left);
1181 }
1182 return ret;
1183 }
1184
1185 /* Node balancing for insertion. Here we only split or push nodes around
1186 * when they are completely full. This is also done top down, so we
1187 * have to be pessimistic.
1188 */
1189 static noinline int push_nodes_for_insert(struct btrfs_trans_handle *trans,
1190 struct btrfs_root *root,
1191 struct btrfs_path *path, int level)
1192 {
1193 struct btrfs_fs_info *fs_info = root->fs_info;
1194 struct extent_buffer *right = NULL;
1195 struct extent_buffer *mid;
1196 struct extent_buffer *left = NULL;
1197 struct extent_buffer *parent = NULL;
1198 int ret = 0;
1199 int wret;
1200 int pslot;
1201 int orig_slot = path->slots[level];
1202
1203 if (level == 0)
1204 return 1;
1205
1206 mid = path->nodes[level];
1207 WARN_ON(btrfs_header_generation(mid) != trans->transid);
1208
1209 if (level < BTRFS_MAX_LEVEL - 1) {
1210 parent = path->nodes[level + 1];
1211 pslot = path->slots[level + 1];
1212 }
1213
1214 if (!parent)
1215 return 1;
1216
1217 /* first, try to make some room in the middle buffer */
1218 if (pslot) {
1219 u32 left_nr;
1220
1221 left = btrfs_read_node_slot(parent, pslot - 1);
1222 if (IS_ERR(left))
1223 return PTR_ERR(left);
1224
1225 btrfs_tree_lock_nested(left, BTRFS_NESTING_LEFT);
1226
1227 left_nr = btrfs_header_nritems(left);
1228 if (left_nr >= BTRFS_NODEPTRS_PER_BLOCK(fs_info) - 1) {
1229 wret = 1;
1230 } else {
1231 ret = btrfs_cow_block(trans, root, left, parent,
1232 pslot - 1, &left,
1233 BTRFS_NESTING_LEFT_COW);
1234 if (ret)
1235 wret = 1;
1236 else {
1237 wret = push_node_left(trans, left, mid, 0);
1238 }
1239 }
1240 if (wret < 0)
1241 ret = wret;
1242 if (wret == 0) {
1243 struct btrfs_disk_key disk_key;
1244 orig_slot += left_nr;
1245 btrfs_node_key(mid, &disk_key, 0);
1246 ret = btrfs_tree_mod_log_insert_key(parent, pslot,
1247 BTRFS_MOD_LOG_KEY_REPLACE);
1248 if (ret < 0) {
1249 btrfs_tree_unlock(left);
1250 free_extent_buffer(left);
1251 btrfs_abort_transaction(trans, ret);
1252 return ret;
1253 }
1254 btrfs_set_node_key(parent, &disk_key, pslot);
1255 btrfs_mark_buffer_dirty(trans, parent);
1256 if (btrfs_header_nritems(left) > orig_slot) {
1257 path->nodes[level] = left;
1258 path->slots[level + 1] -= 1;
1259 path->slots[level] = orig_slot;
1260 btrfs_tree_unlock(mid);
1261 free_extent_buffer(mid);
1262 } else {
1263 orig_slot -=
1264 btrfs_header_nritems(left);
1265 path->slots[level] = orig_slot;
1266 btrfs_tree_unlock(left);
1267 free_extent_buffer(left);
1268 }
1269 return 0;
1270 }
1271 btrfs_tree_unlock(left);
1272 free_extent_buffer(left);
1273 }
1274
1275 /*
1276 * then try to empty the right most buffer into the middle
1277 */
1278 if (pslot + 1 < btrfs_header_nritems(parent)) {
1279 u32 right_nr;
1280
1281 right = btrfs_read_node_slot(parent, pslot + 1);
1282 if (IS_ERR(right))
1283 return PTR_ERR(right);
1284
1285 btrfs_tree_lock_nested(right, BTRFS_NESTING_RIGHT);
1286
1287 right_nr = btrfs_header_nritems(right);
1288 if (right_nr >= BTRFS_NODEPTRS_PER_BLOCK(fs_info) - 1) {
1289 wret = 1;
1290 } else {
1291 ret = btrfs_cow_block(trans, root, right,
1292 parent, pslot + 1,
1293 &right, BTRFS_NESTING_RIGHT_COW);
1294 if (ret)
1295 wret = 1;
1296 else {
1297 wret = balance_node_right(trans, right, mid);
1298 }
1299 }
1300 if (wret < 0)
1301 ret = wret;
1302 if (wret == 0) {
1303 struct btrfs_disk_key disk_key;
1304
1305 btrfs_node_key(right, &disk_key, 0);
1306 ret = btrfs_tree_mod_log_insert_key(parent, pslot + 1,
1307 BTRFS_MOD_LOG_KEY_REPLACE);
1308 if (ret < 0) {
1309 btrfs_tree_unlock(right);
1310 free_extent_buffer(right);
1311 btrfs_abort_transaction(trans, ret);
1312 return ret;
1313 }
1314 btrfs_set_node_key(parent, &disk_key, pslot + 1);
1315 btrfs_mark_buffer_dirty(trans, parent);
1316
1317 if (btrfs_header_nritems(mid) <= orig_slot) {
1318 path->nodes[level] = right;
1319 path->slots[level + 1] += 1;
1320 path->slots[level] = orig_slot -
1321 btrfs_header_nritems(mid);
1322 btrfs_tree_unlock(mid);
1323 free_extent_buffer(mid);
1324 } else {
1325 btrfs_tree_unlock(right);
1326 free_extent_buffer(right);
1327 }
1328 return 0;
1329 }
1330 btrfs_tree_unlock(right);
1331 free_extent_buffer(right);
1332 }
1333 return 1;
1334 }
1335
1336 /*
1337 * readahead one full node of leaves, finding things that are close
1338 * to the block in 'slot', and triggering ra on them.
1339 */
1340 static void reada_for_search(struct btrfs_fs_info *fs_info,
1341 struct btrfs_path *path,
1342 int level, int slot, u64 objectid)
1343 {
1344 struct extent_buffer *node;
1345 struct btrfs_disk_key disk_key;
1346 u32 nritems;
1347 u64 search;
1348 u64 target;
1349 u64 nread = 0;
1350 u64 nread_max;
1351 u32 nr;
1352 u32 blocksize;
1353 u32 nscan = 0;
1354
1355 if (level != 1 && path->reada != READA_FORWARD_ALWAYS)
1356 return;
1357
1358 if (!path->nodes[level])
1359 return;
1360
1361 node = path->nodes[level];
1362
1363 /*
1364 * Since the time between visiting leaves is much shorter than the time
1365 * between visiting nodes, limit read ahead of nodes to 1, to avoid too
1366 * much IO at once (possibly random).
1367 */
1368 if (path->reada == READA_FORWARD_ALWAYS) {
1369 if (level > 1)
1370 nread_max = node->fs_info->nodesize;
1371 else
1372 nread_max = SZ_128K;
1373 } else {
1374 nread_max = SZ_64K;
1375 }
1376
1377 search = btrfs_node_blockptr(node, slot);
1378 blocksize = fs_info->nodesize;
1379 if (path->reada != READA_FORWARD_ALWAYS) {
1380 struct extent_buffer *eb;
1381
1382 eb = find_extent_buffer(fs_info, search);
1383 if (eb) {
1384 free_extent_buffer(eb);
1385 return;
1386 }
1387 }
1388
1389 target = search;
1390
1391 nritems = btrfs_header_nritems(node);
1392 nr = slot;
1393
1394 while (1) {
1395 if (path->reada == READA_BACK) {
1396 if (nr == 0)
1397 break;
1398 nr--;
1399 } else if (path->reada == READA_FORWARD ||
1400 path->reada == READA_FORWARD_ALWAYS) {
1401 nr++;
1402 if (nr >= nritems)
1403 break;
1404 }
1405 if (path->reada == READA_BACK && objectid) {
1406 btrfs_node_key(node, &disk_key, nr);
1407 if (btrfs_disk_key_objectid(&disk_key) != objectid)
1408 break;
1409 }
1410 search = btrfs_node_blockptr(node, nr);
1411 if (path->reada == READA_FORWARD_ALWAYS ||
1412 (search <= target && target - search <= 65536) ||
1413 (search > target && search - target <= 65536)) {
1414 btrfs_readahead_node_child(node, nr);
1415 nread += blocksize;
1416 }
1417 nscan++;
1418 if (nread > nread_max || nscan > 32)
1419 break;
1420 }
1421 }
1422
1423 static noinline void reada_for_balance(struct btrfs_path *path, int level)
1424 {
1425 struct extent_buffer *parent;
1426 int slot;
1427 int nritems;
1428
1429 parent = path->nodes[level + 1];
1430 if (!parent)
1431 return;
1432
1433 nritems = btrfs_header_nritems(parent);
1434 slot = path->slots[level + 1];
1435
1436 if (slot > 0)
1437 btrfs_readahead_node_child(parent, slot - 1);
1438 if (slot + 1 < nritems)
1439 btrfs_readahead_node_child(parent, slot + 1);
1440 }
1441
1442
1443 /*
1444 * when we walk down the tree, it is usually safe to unlock the higher layers
1445 * in the tree. The exceptions are when our path goes through slot 0, because
1446 * operations on the tree might require changing key pointers higher up in the
1447 * tree.
1448 *
1449 * callers might also have set path->keep_locks, which tells this code to keep
1450 * the lock if the path points to the last slot in the block. This is part of
1451 * walking through the tree, and selecting the next slot in the higher block.
1452 *
1453 * lowest_unlock sets the lowest level in the tree we're allowed to unlock. so
1454 * if lowest_unlock is 1, level 0 won't be unlocked
1455 */
1456 static noinline void unlock_up(struct btrfs_path *path, int level,
1457 int lowest_unlock, int min_write_lock_level,
1458 int *write_lock_level)
1459 {
1460 int i;
1461 int skip_level = level;
1462 bool check_skip = true;
1463
1464 for (i = level; i < BTRFS_MAX_LEVEL; i++) {
1465 if (!path->nodes[i])
1466 break;
1467 if (!path->locks[i])
1468 break;
1469
1470 if (check_skip) {
1471 if (path->slots[i] == 0) {
1472 skip_level = i + 1;
1473 continue;
1474 }
1475
1476 if (path->keep_locks) {
1477 u32 nritems;
1478
1479 nritems = btrfs_header_nritems(path->nodes[i]);
1480 if (nritems < 1 || path->slots[i] >= nritems - 1) {
1481 skip_level = i + 1;
1482 continue;
1483 }
1484 }
1485 }
1486
1487 if (i >= lowest_unlock && i > skip_level) {
1488 check_skip = false;
1489 btrfs_tree_unlock_rw(path->nodes[i], path->locks[i]);
1490 path->locks[i] = 0;
1491 if (write_lock_level &&
1492 i > min_write_lock_level &&
1493 i <= *write_lock_level) {
1494 *write_lock_level = i - 1;
1495 }
1496 }
1497 }
1498 }
1499
1500 /*
1501 * Helper function for btrfs_search_slot() and other functions that do a search
1502 * on a btree. The goal is to find a tree block in the cache (the radix tree at
1503 * fs_info->buffer_radix), but if we can't find it, or it's not up to date, read
1504 * its pages from disk.
1505 *
1506 * Returns -EAGAIN, with the path unlocked, if the caller needs to repeat the
1507 * whole btree search, starting again from the current root node.
1508 */
1509 static int
1510 read_block_for_search(struct btrfs_root *root, struct btrfs_path *p,
1511 struct extent_buffer **eb_ret, int level, int slot,
1512 const struct btrfs_key *key)
1513 {
1514 struct btrfs_fs_info *fs_info = root->fs_info;
1515 struct btrfs_tree_parent_check check = { 0 };
1516 u64 blocknr;
1517 u64 gen;
1518 struct extent_buffer *tmp;
1519 int ret;
1520 int parent_level;
1521 bool unlock_up;
1522
1523 unlock_up = ((level + 1 < BTRFS_MAX_LEVEL) && p->locks[level + 1]);
1524 blocknr = btrfs_node_blockptr(*eb_ret, slot);
1525 gen = btrfs_node_ptr_generation(*eb_ret, slot);
1526 parent_level = btrfs_header_level(*eb_ret);
1527 btrfs_node_key_to_cpu(*eb_ret, &check.first_key, slot);
1528 check.has_first_key = true;
1529 check.level = parent_level - 1;
1530 check.transid = gen;
1531 check.owner_root = btrfs_root_id(root);
1532
1533 /*
1534 * If we need to read an extent buffer from disk and we are holding locks
1535 * on upper level nodes, we unlock all the upper nodes before reading the
1536 * extent buffer, and then return -EAGAIN to the caller as it needs to
1537 * restart the search. We don't release the lock on the current level
1538 * because we need to walk this node to figure out which blocks to read.
1539 */
1540 tmp = find_extent_buffer(fs_info, blocknr);
1541 if (tmp) {
1542 if (p->reada == READA_FORWARD_ALWAYS)
1543 reada_for_search(fs_info, p, level, slot, key->objectid);
1544
1545 /* first we do an atomic uptodate check */
1546 if (btrfs_buffer_uptodate(tmp, gen, 1) > 0) {
1547 /*
1548 * Do extra check for first_key, eb can be stale due to
1549 * being cached, read from scrub, or have multiple
1550 * parents (shared tree blocks).
1551 */
1552 if (btrfs_verify_level_key(tmp,
1553 parent_level - 1, &check.first_key, gen)) {
1554 free_extent_buffer(tmp);
1555 return -EUCLEAN;
1556 }
1557 *eb_ret = tmp;
1558 return 0;
1559 }
1560
1561 if (p->nowait) {
1562 free_extent_buffer(tmp);
1563 return -EAGAIN;
1564 }
1565
1566 if (unlock_up)
1567 btrfs_unlock_up_safe(p, level + 1);
1568
1569 /* now we're allowed to do a blocking uptodate check */
1570 ret = btrfs_read_extent_buffer(tmp, &check);
1571 if (ret) {
1572 free_extent_buffer(tmp);
1573 btrfs_release_path(p);
1574 return ret;
1575 }
1576
1577 if (unlock_up)
1578 ret = -EAGAIN;
1579
1580 goto out;
1581 } else if (p->nowait) {
1582 return -EAGAIN;
1583 }
1584
1585 if (unlock_up) {
1586 btrfs_unlock_up_safe(p, level + 1);
1587 ret = -EAGAIN;
1588 } else {
1589 ret = 0;
1590 }
1591
1592 if (p->reada != READA_NONE)
1593 reada_for_search(fs_info, p, level, slot, key->objectid);
1594
1595 tmp = read_tree_block(fs_info, blocknr, &check);
1596 if (IS_ERR(tmp)) {
1597 btrfs_release_path(p);
1598 return PTR_ERR(tmp);
1599 }
1600 /*
1601 * If the read above didn't mark this buffer up to date,
1602 * it will never end up being up to date. Set ret to EIO now
1603 * and give up so that our caller doesn't loop forever
1604 * on our EAGAINs.
1605 */
1606 if (!extent_buffer_uptodate(tmp))
1607 ret = -EIO;
1608
1609 out:
1610 if (ret == 0) {
1611 *eb_ret = tmp;
1612 } else {
1613 free_extent_buffer(tmp);
1614 btrfs_release_path(p);
1615 }
1616
1617 return ret;
1618 }
1619
1620 /*
1621 * helper function for btrfs_search_slot. This does all of the checks
1622 * for node-level blocks and does any balancing required based on
1623 * the ins_len.
1624 *
1625 * If no extra work was required, zero is returned. If we had to
1626 * drop the path, -EAGAIN is returned and btrfs_search_slot must
1627 * start over
1628 */
1629 static int
1630 setup_nodes_for_search(struct btrfs_trans_handle *trans,
1631 struct btrfs_root *root, struct btrfs_path *p,
1632 struct extent_buffer *b, int level, int ins_len,
1633 int *write_lock_level)
1634 {
1635 struct btrfs_fs_info *fs_info = root->fs_info;
1636 int ret = 0;
1637
1638 if ((p->search_for_split || ins_len > 0) && btrfs_header_nritems(b) >=
1639 BTRFS_NODEPTRS_PER_BLOCK(fs_info) - 3) {
1640
1641 if (*write_lock_level < level + 1) {
1642 *write_lock_level = level + 1;
1643 btrfs_release_path(p);
1644 return -EAGAIN;
1645 }
1646
1647 reada_for_balance(p, level);
1648 ret = split_node(trans, root, p, level);
1649
1650 b = p->nodes[level];
1651 } else if (ins_len < 0 && btrfs_header_nritems(b) <
1652 BTRFS_NODEPTRS_PER_BLOCK(fs_info) / 2) {
1653
1654 if (*write_lock_level < level + 1) {
1655 *write_lock_level = level + 1;
1656 btrfs_release_path(p);
1657 return -EAGAIN;
1658 }
1659
1660 reada_for_balance(p, level);
1661 ret = balance_level(trans, root, p, level);
1662 if (ret)
1663 return ret;
1664
1665 b = p->nodes[level];
1666 if (!b) {
1667 btrfs_release_path(p);
1668 return -EAGAIN;
1669 }
1670 BUG_ON(btrfs_header_nritems(b) == 1);
1671 }
1672 return ret;
1673 }
1674
1675 int btrfs_find_item(struct btrfs_root *fs_root, struct btrfs_path *path,
1676 u64 iobjectid, u64 ioff, u8 key_type,
1677 struct btrfs_key *found_key)
1678 {
1679 int ret;
1680 struct btrfs_key key;
1681 struct extent_buffer *eb;
1682
1683 ASSERT(path);
1684 ASSERT(found_key);
1685
1686 key.type = key_type;
1687 key.objectid = iobjectid;
1688 key.offset = ioff;
1689
1690 ret = btrfs_search_slot(NULL, fs_root, &key, path, 0, 0);
1691 if (ret < 0)
1692 return ret;
1693
1694 eb = path->nodes[0];
1695 if (ret && path->slots[0] >= btrfs_header_nritems(eb)) {
1696 ret = btrfs_next_leaf(fs_root, path);
1697 if (ret)
1698 return ret;
1699 eb = path->nodes[0];
1700 }
1701
1702 btrfs_item_key_to_cpu(eb, found_key, path->slots[0]);
1703 if (found_key->type != key.type ||
1704 found_key->objectid != key.objectid)
1705 return 1;
1706
1707 return 0;
1708 }
1709
1710 static struct extent_buffer *btrfs_search_slot_get_root(struct btrfs_root *root,
1711 struct btrfs_path *p,
1712 int write_lock_level)
1713 {
1714 struct extent_buffer *b;
1715 int root_lock = 0;
1716 int level = 0;
1717
1718 if (p->search_commit_root) {
1719 b = root->commit_root;
1720 atomic_inc(&b->refs);
1721 level = btrfs_header_level(b);
1722 /*
1723 * Ensure that all callers have set skip_locking when
1724 * p->search_commit_root = 1.
1725 */
1726 ASSERT(p->skip_locking == 1);
1727
1728 goto out;
1729 }
1730
1731 if (p->skip_locking) {
1732 b = btrfs_root_node(root);
1733 level = btrfs_header_level(b);
1734 goto out;
1735 }
1736
1737 /* We try very hard to do read locks on the root */
1738 root_lock = BTRFS_READ_LOCK;
1739
1740 /*
1741 * If the level is set to maximum, we can skip trying to get the read
1742 * lock.
1743 */
1744 if (write_lock_level < BTRFS_MAX_LEVEL) {
1745 /*
1746 * We don't know the level of the root node until we actually
1747 * have it read locked
1748 */
1749 if (p->nowait) {
1750 b = btrfs_try_read_lock_root_node(root);
1751 if (IS_ERR(b))
1752 return b;
1753 } else {
1754 b = btrfs_read_lock_root_node(root);
1755 }
1756 level = btrfs_header_level(b);
1757 if (level > write_lock_level)
1758 goto out;
1759
1760 /* Whoops, must trade for write lock */
1761 btrfs_tree_read_unlock(b);
1762 free_extent_buffer(b);
1763 }
1764
1765 b = btrfs_lock_root_node(root);
1766 root_lock = BTRFS_WRITE_LOCK;
1767
1768 /* The level might have changed, check again */
1769 level = btrfs_header_level(b);
1770
1771 out:
1772 /*
1773 * The root may have failed to write out at some point, and thus is no
1774 * longer valid, return an error in this case.
1775 */
1776 if (!extent_buffer_uptodate(b)) {
1777 if (root_lock)
1778 btrfs_tree_unlock_rw(b, root_lock);
1779 free_extent_buffer(b);
1780 return ERR_PTR(-EIO);
1781 }
1782
1783 p->nodes[level] = b;
1784 if (!p->skip_locking)
1785 p->locks[level] = root_lock;
1786 /*
1787 * Callers are responsible for dropping b's references.
1788 */
1789 return b;
1790 }
1791
1792 /*
1793 * Replace the extent buffer at the lowest level of the path with a cloned
1794 * version. The purpose is to be able to use it safely, after releasing the
1795 * commit root semaphore, even if relocation is happening in parallel, the
1796 * transaction used for relocation is committed and the extent buffer is
1797 * reallocated in the next transaction.
1798 *
1799 * This is used in a context where the caller does not prevent transaction
1800 * commits from happening, either by holding a transaction handle or holding
1801 * some lock, while it's doing searches through a commit root.
1802 * At the moment it's only used for send operations.
1803 */
1804 static int finish_need_commit_sem_search(struct btrfs_path *path)
1805 {
1806 const int i = path->lowest_level;
1807 const int slot = path->slots[i];
1808 struct extent_buffer *lowest = path->nodes[i];
1809 struct extent_buffer *clone;
1810
1811 ASSERT(path->need_commit_sem);
1812
1813 if (!lowest)
1814 return 0;
1815
1816 lockdep_assert_held_read(&lowest->fs_info->commit_root_sem);
1817
1818 clone = btrfs_clone_extent_buffer(lowest);
1819 if (!clone)
1820 return -ENOMEM;
1821
1822 btrfs_release_path(path);
1823 path->nodes[i] = clone;
1824 path->slots[i] = slot;
1825
1826 return 0;
1827 }
1828
1829 static inline int search_for_key_slot(struct extent_buffer *eb,
1830 int search_low_slot,
1831 const struct btrfs_key *key,
1832 int prev_cmp,
1833 int *slot)
1834 {
1835 /*
1836 * If a previous call to btrfs_bin_search() on a parent node returned an
1837 * exact match (prev_cmp == 0), we can safely assume the target key will
1838 * always be at slot 0 on lower levels, since each key pointer
1839 * (struct btrfs_key_ptr) refers to the lowest key accessible from the
1840 * subtree it points to. Thus we can skip searching lower levels.
1841 */
1842 if (prev_cmp == 0) {
1843 *slot = 0;
1844 return 0;
1845 }
1846
1847 return btrfs_bin_search(eb, search_low_slot, key, slot);
1848 }
1849
1850 static int search_leaf(struct btrfs_trans_handle *trans,
1851 struct btrfs_root *root,
1852 const struct btrfs_key *key,
1853 struct btrfs_path *path,
1854 int ins_len,
1855 int prev_cmp)
1856 {
1857 struct extent_buffer *leaf = path->nodes[0];
1858 int leaf_free_space = -1;
1859 int search_low_slot = 0;
1860 int ret;
1861 bool do_bin_search = true;
1862
1863 /*
1864 * If we are doing an insertion, the leaf has enough free space and the
1865 * destination slot for the key is not slot 0, then we can unlock our
1866 * write lock on the parent, and any other upper nodes, before doing the
1867 * binary search on the leaf (with search_for_key_slot()), allowing other
1868 * tasks to lock the parent and any other upper nodes.
1869 */
1870 if (ins_len > 0) {
1871 /*
1872 * Cache the leaf free space, since we will need it later and it
1873 * will not change until then.
1874 */
1875 leaf_free_space = btrfs_leaf_free_space(leaf);
1876
1877 /*
1878 * !path->locks[1] means we have a single node tree, the leaf is
1879 * the root of the tree.
1880 */
1881 if (path->locks[1] && leaf_free_space >= ins_len) {
1882 struct btrfs_disk_key first_key;
1883
1884 ASSERT(btrfs_header_nritems(leaf) > 0);
1885 btrfs_item_key(leaf, &first_key, 0);
1886
1887 /*
1888 * Doing the extra comparison with the first key is cheap,
1889 * taking into account that the first key is very likely
1890 * already in a cache line because it immediately follows
1891 * the extent buffer's header and we have recently accessed
1892 * the header's level field.
1893 */
1894 ret = btrfs_comp_keys(&first_key, key);
1895 if (ret < 0) {
1896 /*
1897 * The first key is smaller than the key we want
1898 * to insert, so we are safe to unlock all upper
1899 * nodes and we have to do the binary search.
1900 *
1901 * We do use btrfs_unlock_up_safe() and not
1902 * unlock_up() because the later does not unlock
1903 * nodes with a slot of 0 - we can safely unlock
1904 * any node even if its slot is 0 since in this
1905 * case the key does not end up at slot 0 of the
1906 * leaf and there's no need to split the leaf.
1907 */
1908 btrfs_unlock_up_safe(path, 1);
1909 search_low_slot = 1;
1910 } else {
1911 /*
1912 * The first key is >= then the key we want to
1913 * insert, so we can skip the binary search as
1914 * the target key will be at slot 0.
1915 *
1916 * We can not unlock upper nodes when the key is
1917 * less than the first key, because we will need
1918 * to update the key at slot 0 of the parent node
1919 * and possibly of other upper nodes too.
1920 * If the key matches the first key, then we can
1921 * unlock all the upper nodes, using
1922 * btrfs_unlock_up_safe() instead of unlock_up()
1923 * as stated above.
1924 */
1925 if (ret == 0)
1926 btrfs_unlock_up_safe(path, 1);
1927 /*
1928 * ret is already 0 or 1, matching the result of
1929 * a btrfs_bin_search() call, so there is no need
1930 * to adjust it.
1931 */
1932 do_bin_search = false;
1933 path->slots[0] = 0;
1934 }
1935 }
1936 }
1937
1938 if (do_bin_search) {
1939 ret = search_for_key_slot(leaf, search_low_slot, key,
1940 prev_cmp, &path->slots[0]);
1941 if (ret < 0)
1942 return ret;
1943 }
1944
1945 if (ins_len > 0) {
1946 /*
1947 * Item key already exists. In this case, if we are allowed to
1948 * insert the item (for example, in dir_item case, item key
1949 * collision is allowed), it will be merged with the original
1950 * item. Only the item size grows, no new btrfs item will be
1951 * added. If search_for_extension is not set, ins_len already
1952 * accounts the size btrfs_item, deduct it here so leaf space
1953 * check will be correct.
1954 */
1955 if (ret == 0 && !path->search_for_extension) {
1956 ASSERT(ins_len >= sizeof(struct btrfs_item));
1957 ins_len -= sizeof(struct btrfs_item);
1958 }
1959
1960 ASSERT(leaf_free_space >= 0);
1961
1962 if (leaf_free_space < ins_len) {
1963 int err;
1964
1965 err = split_leaf(trans, root, key, path, ins_len,
1966 (ret == 0));
1967 ASSERT(err <= 0);
1968 if (WARN_ON(err > 0))
1969 err = -EUCLEAN;
1970 if (err)
1971 ret = err;
1972 }
1973 }
1974
1975 return ret;
1976 }
1977
1978 /*
1979 * Look for a key in a tree and perform necessary modifications to preserve
1980 * tree invariants.
1981 *
1982 * @trans: Handle of transaction, used when modifying the tree
1983 * @p: Holds all btree nodes along the search path
1984 * @root: The root node of the tree
1985 * @key: The key we are looking for
1986 * @ins_len: Indicates purpose of search:
1987 * >0 for inserts it's size of item inserted (*)
1988 * <0 for deletions
1989 * 0 for plain searches, not modifying the tree
1990 *
1991 * (*) If size of item inserted doesn't include
1992 * sizeof(struct btrfs_item), then p->search_for_extension must
1993 * be set.
1994 * @cow: boolean should CoW operations be performed. Must always be 1
1995 * when modifying the tree.
1996 *
1997 * If @ins_len > 0, nodes and leaves will be split as we walk down the tree.
1998 * If @ins_len < 0, nodes will be merged as we walk down the tree (if possible)
1999 *
2000 * If @key is found, 0 is returned and you can find the item in the leaf level
2001 * of the path (level 0)
2002 *
2003 * If @key isn't found, 1 is returned and the leaf level of the path (level 0)
2004 * points to the slot where it should be inserted
2005 *
2006 * If an error is encountered while searching the tree a negative error number
2007 * is returned
2008 */
2009 int btrfs_search_slot(struct btrfs_trans_handle *trans, struct btrfs_root *root,
2010 const struct btrfs_key *key, struct btrfs_path *p,
2011 int ins_len, int cow)
2012 {
2013 struct btrfs_fs_info *fs_info = root->fs_info;
2014 struct extent_buffer *b;
2015 int slot;
2016 int ret;
2017 int err;
2018 int level;
2019 int lowest_unlock = 1;
2020 /* everything at write_lock_level or lower must be write locked */
2021 int write_lock_level = 0;
2022 u8 lowest_level = 0;
2023 int min_write_lock_level;
2024 int prev_cmp;
2025
2026 might_sleep();
2027
2028 lowest_level = p->lowest_level;
2029 WARN_ON(lowest_level && ins_len > 0);
2030 WARN_ON(p->nodes[0] != NULL);
2031 BUG_ON(!cow && ins_len);
2032
2033 /*
2034 * For now only allow nowait for read only operations. There's no
2035 * strict reason why we can't, we just only need it for reads so it's
2036 * only implemented for reads.
2037 */
2038 ASSERT(!p->nowait || !cow);
2039
2040 if (ins_len < 0) {
2041 lowest_unlock = 2;
2042
2043 /* when we are removing items, we might have to go up to level
2044 * two as we update tree pointers Make sure we keep write
2045 * for those levels as well
2046 */
2047 write_lock_level = 2;
2048 } else if (ins_len > 0) {
2049 /*
2050 * for inserting items, make sure we have a write lock on
2051 * level 1 so we can update keys
2052 */
2053 write_lock_level = 1;
2054 }
2055
2056 if (!cow)
2057 write_lock_level = -1;
2058
2059 if (cow && (p->keep_locks || p->lowest_level))
2060 write_lock_level = BTRFS_MAX_LEVEL;
2061
2062 min_write_lock_level = write_lock_level;
2063
2064 if (p->need_commit_sem) {
2065 ASSERT(p->search_commit_root);
2066 if (p->nowait) {
2067 if (!down_read_trylock(&fs_info->commit_root_sem))
2068 return -EAGAIN;
2069 } else {
2070 down_read(&fs_info->commit_root_sem);
2071 }
2072 }
2073
2074 again:
2075 prev_cmp = -1;
2076 b = btrfs_search_slot_get_root(root, p, write_lock_level);
2077 if (IS_ERR(b)) {
2078 ret = PTR_ERR(b);
2079 goto done;
2080 }
2081
2082 while (b) {
2083 int dec = 0;
2084
2085 level = btrfs_header_level(b);
2086
2087 if (cow) {
2088 bool last_level = (level == (BTRFS_MAX_LEVEL - 1));
2089
2090 /*
2091 * if we don't really need to cow this block
2092 * then we don't want to set the path blocking,
2093 * so we test it here
2094 */
2095 if (!should_cow_block(trans, root, b))
2096 goto cow_done;
2097
2098 /*
2099 * must have write locks on this node and the
2100 * parent
2101 */
2102 if (level > write_lock_level ||
2103 (level + 1 > write_lock_level &&
2104 level + 1 < BTRFS_MAX_LEVEL &&
2105 p->nodes[level + 1])) {
2106 write_lock_level = level + 1;
2107 btrfs_release_path(p);
2108 goto again;
2109 }
2110
2111 if (last_level)
2112 err = btrfs_cow_block(trans, root, b, NULL, 0,
2113 &b,
2114 BTRFS_NESTING_COW);
2115 else
2116 err = btrfs_cow_block(trans, root, b,
2117 p->nodes[level + 1],
2118 p->slots[level + 1], &b,
2119 BTRFS_NESTING_COW);
2120 if (err) {
2121 ret = err;
2122 goto done;
2123 }
2124 }
2125 cow_done:
2126 p->nodes[level] = b;
2127
2128 /*
2129 * we have a lock on b and as long as we aren't changing
2130 * the tree, there is no way to for the items in b to change.
2131 * It is safe to drop the lock on our parent before we
2132 * go through the expensive btree search on b.
2133 *
2134 * If we're inserting or deleting (ins_len != 0), then we might
2135 * be changing slot zero, which may require changing the parent.
2136 * So, we can't drop the lock until after we know which slot
2137 * we're operating on.
2138 */
2139 if (!ins_len && !p->keep_locks) {
2140 int u = level + 1;
2141
2142 if (u < BTRFS_MAX_LEVEL && p->locks[u]) {
2143 btrfs_tree_unlock_rw(p->nodes[u], p->locks[u]);
2144 p->locks[u] = 0;
2145 }
2146 }
2147
2148 if (level == 0) {
2149 if (ins_len > 0)
2150 ASSERT(write_lock_level >= 1);
2151
2152 ret = search_leaf(trans, root, key, p, ins_len, prev_cmp);
2153 if (!p->search_for_split)
2154 unlock_up(p, level, lowest_unlock,
2155 min_write_lock_level, NULL);
2156 goto done;
2157 }
2158
2159 ret = search_for_key_slot(b, 0, key, prev_cmp, &slot);
2160 if (ret < 0)
2161 goto done;
2162 prev_cmp = ret;
2163
2164 if (ret && slot > 0) {
2165 dec = 1;
2166 slot--;
2167 }
2168 p->slots[level] = slot;
2169 err = setup_nodes_for_search(trans, root, p, b, level, ins_len,
2170 &write_lock_level);
2171 if (err == -EAGAIN)
2172 goto again;
2173 if (err) {
2174 ret = err;
2175 goto done;
2176 }
2177 b = p->nodes[level];
2178 slot = p->slots[level];
2179
2180 /*
2181 * Slot 0 is special, if we change the key we have to update
2182 * the parent pointer which means we must have a write lock on
2183 * the parent
2184 */
2185 if (slot == 0 && ins_len && write_lock_level < level + 1) {
2186 write_lock_level = level + 1;
2187 btrfs_release_path(p);
2188 goto again;
2189 }
2190
2191 unlock_up(p, level, lowest_unlock, min_write_lock_level,
2192 &write_lock_level);
2193
2194 if (level == lowest_level) {
2195 if (dec)
2196 p->slots[level]++;
2197 goto done;
2198 }
2199
2200 err = read_block_for_search(root, p, &b, level, slot, key);
2201 if (err == -EAGAIN)
2202 goto again;
2203 if (err) {
2204 ret = err;
2205 goto done;
2206 }
2207
2208 if (!p->skip_locking) {
2209 level = btrfs_header_level(b);
2210
2211 btrfs_maybe_reset_lockdep_class(root, b);
2212
2213 if (level <= write_lock_level) {
2214 btrfs_tree_lock(b);
2215 p->locks[level] = BTRFS_WRITE_LOCK;
2216 } else {
2217 if (p->nowait) {
2218 if (!btrfs_try_tree_read_lock(b)) {
2219 free_extent_buffer(b);
2220 ret = -EAGAIN;
2221 goto done;
2222 }
2223 } else {
2224 btrfs_tree_read_lock(b);
2225 }
2226 p->locks[level] = BTRFS_READ_LOCK;
2227 }
2228 p->nodes[level] = b;
2229 }
2230 }
2231 ret = 1;
2232 done:
2233 if (ret < 0 && !p->skip_release_on_error)
2234 btrfs_release_path(p);
2235
2236 if (p->need_commit_sem) {
2237 int ret2;
2238
2239 ret2 = finish_need_commit_sem_search(p);
2240 up_read(&fs_info->commit_root_sem);
2241 if (ret2)
2242 ret = ret2;
2243 }
2244
2245 return ret;
2246 }
2247 ALLOW_ERROR_INJECTION(btrfs_search_slot, ERRNO);
2248
2249 /*
2250 * Like btrfs_search_slot, this looks for a key in the given tree. It uses the
2251 * current state of the tree together with the operations recorded in the tree
2252 * modification log to search for the key in a previous version of this tree, as
2253 * denoted by the time_seq parameter.
2254 *
2255 * Naturally, there is no support for insert, delete or cow operations.
2256 *
2257 * The resulting path and return value will be set up as if we called
2258 * btrfs_search_slot at that point in time with ins_len and cow both set to 0.
2259 */
2260 int btrfs_search_old_slot(struct btrfs_root *root, const struct btrfs_key *key,
2261 struct btrfs_path *p, u64 time_seq)
2262 {
2263 struct btrfs_fs_info *fs_info = root->fs_info;
2264 struct extent_buffer *b;
2265 int slot;
2266 int ret;
2267 int err;
2268 int level;
2269 int lowest_unlock = 1;
2270 u8 lowest_level = 0;
2271
2272 lowest_level = p->lowest_level;
2273 WARN_ON(p->nodes[0] != NULL);
2274 ASSERT(!p->nowait);
2275
2276 if (p->search_commit_root) {
2277 BUG_ON(time_seq);
2278 return btrfs_search_slot(NULL, root, key, p, 0, 0);
2279 }
2280
2281 again:
2282 b = btrfs_get_old_root(root, time_seq);
2283 if (!b) {
2284 ret = -EIO;
2285 goto done;
2286 }
2287 level = btrfs_header_level(b);
2288 p->locks[level] = BTRFS_READ_LOCK;
2289
2290 while (b) {
2291 int dec = 0;
2292
2293 level = btrfs_header_level(b);
2294 p->nodes[level] = b;
2295
2296 /*
2297 * we have a lock on b and as long as we aren't changing
2298 * the tree, there is no way to for the items in b to change.
2299 * It is safe to drop the lock on our parent before we
2300 * go through the expensive btree search on b.
2301 */
2302 btrfs_unlock_up_safe(p, level + 1);
2303
2304 ret = btrfs_bin_search(b, 0, key, &slot);
2305 if (ret < 0)
2306 goto done;
2307
2308 if (level == 0) {
2309 p->slots[level] = slot;
2310 unlock_up(p, level, lowest_unlock, 0, NULL);
2311 goto done;
2312 }
2313
2314 if (ret && slot > 0) {
2315 dec = 1;
2316 slot--;
2317 }
2318 p->slots[level] = slot;
2319 unlock_up(p, level, lowest_unlock, 0, NULL);
2320
2321 if (level == lowest_level) {
2322 if (dec)
2323 p->slots[level]++;
2324 goto done;
2325 }
2326
2327 err = read_block_for_search(root, p, &b, level, slot, key);
2328 if (err == -EAGAIN)
2329 goto again;
2330 if (err) {
2331 ret = err;
2332 goto done;
2333 }
2334
2335 level = btrfs_header_level(b);
2336 btrfs_tree_read_lock(b);
2337 b = btrfs_tree_mod_log_rewind(fs_info, p, b, time_seq);
2338 if (!b) {
2339 ret = -ENOMEM;
2340 goto done;
2341 }
2342 p->locks[level] = BTRFS_READ_LOCK;
2343 p->nodes[level] = b;
2344 }
2345 ret = 1;
2346 done:
2347 if (ret < 0)
2348 btrfs_release_path(p);
2349
2350 return ret;
2351 }
2352
2353 /*
2354 * Search the tree again to find a leaf with smaller keys.
2355 * Returns 0 if it found something.
2356 * Returns 1 if there are no smaller keys.
2357 * Returns < 0 on error.
2358 *
2359 * This may release the path, and so you may lose any locks held at the
2360 * time you call it.
2361 */
2362 static int btrfs_prev_leaf(struct btrfs_root *root, struct btrfs_path *path)
2363 {
2364 struct btrfs_key key;
2365 struct btrfs_key orig_key;
2366 struct btrfs_disk_key found_key;
2367 int ret;
2368
2369 btrfs_item_key_to_cpu(path->nodes[0], &key, 0);
2370 orig_key = key;
2371
2372 if (key.offset > 0) {
2373 key.offset--;
2374 } else if (key.type > 0) {
2375 key.type--;
2376 key.offset = (u64)-1;
2377 } else if (key.objectid > 0) {
2378 key.objectid--;
2379 key.type = (u8)-1;
2380 key.offset = (u64)-1;
2381 } else {
2382 return 1;
2383 }
2384
2385 btrfs_release_path(path);
2386 ret = btrfs_search_slot(NULL, root, &key, path, 0, 0);
2387 if (ret <= 0)
2388 return ret;
2389
2390 /*
2391 * Previous key not found. Even if we were at slot 0 of the leaf we had
2392 * before releasing the path and calling btrfs_search_slot(), we now may
2393 * be in a slot pointing to the same original key - this can happen if
2394 * after we released the path, one of more items were moved from a
2395 * sibling leaf into the front of the leaf we had due to an insertion
2396 * (see push_leaf_right()).
2397 * If we hit this case and our slot is > 0 and just decrement the slot
2398 * so that the caller does not process the same key again, which may or
2399 * may not break the caller, depending on its logic.
2400 */
2401 if (path->slots[0] < btrfs_header_nritems(path->nodes[0])) {
2402 btrfs_item_key(path->nodes[0], &found_key, path->slots[0]);
2403 ret = btrfs_comp_keys(&found_key, &orig_key);
2404 if (ret == 0) {
2405 if (path->slots[0] > 0) {
2406 path->slots[0]--;
2407 return 0;
2408 }
2409 /*
2410 * At slot 0, same key as before, it means orig_key is
2411 * the lowest, leftmost, key in the tree. We're done.
2412 */
2413 return 1;
2414 }
2415 }
2416
2417 btrfs_item_key(path->nodes[0], &found_key, 0);
2418 ret = btrfs_comp_keys(&found_key, &key);
2419 /*
2420 * We might have had an item with the previous key in the tree right
2421 * before we released our path. And after we released our path, that
2422 * item might have been pushed to the first slot (0) of the leaf we
2423 * were holding due to a tree balance. Alternatively, an item with the
2424 * previous key can exist as the only element of a leaf (big fat item).
2425 * Therefore account for these 2 cases, so that our callers (like
2426 * btrfs_previous_item) don't miss an existing item with a key matching
2427 * the previous key we computed above.
2428 */
2429 if (ret <= 0)
2430 return 0;
2431 return 1;
2432 }
2433
2434 /*
2435 * helper to use instead of search slot if no exact match is needed but
2436 * instead the next or previous item should be returned.
2437 * When find_higher is true, the next higher item is returned, the next lower
2438 * otherwise.
2439 * When return_any and find_higher are both true, and no higher item is found,
2440 * return the next lower instead.
2441 * When return_any is true and find_higher is false, and no lower item is found,
2442 * return the next higher instead.
2443 * It returns 0 if any item is found, 1 if none is found (tree empty), and
2444 * < 0 on error
2445 */
2446 int btrfs_search_slot_for_read(struct btrfs_root *root,
2447 const struct btrfs_key *key,
2448 struct btrfs_path *p, int find_higher,
2449 int return_any)
2450 {
2451 int ret;
2452 struct extent_buffer *leaf;
2453
2454 again:
2455 ret = btrfs_search_slot(NULL, root, key, p, 0, 0);
2456 if (ret <= 0)
2457 return ret;
2458 /*
2459 * a return value of 1 means the path is at the position where the
2460 * item should be inserted. Normally this is the next bigger item,
2461 * but in case the previous item is the last in a leaf, path points
2462 * to the first free slot in the previous leaf, i.e. at an invalid
2463 * item.
2464 */
2465 leaf = p->nodes[0];
2466
2467 if (find_higher) {
2468 if (p->slots[0] >= btrfs_header_nritems(leaf)) {
2469 ret = btrfs_next_leaf(root, p);
2470 if (ret <= 0)
2471 return ret;
2472 if (!return_any)
2473 return 1;
2474 /*
2475 * no higher item found, return the next
2476 * lower instead
2477 */
2478 return_any = 0;
2479 find_higher = 0;
2480 btrfs_release_path(p);
2481 goto again;
2482 }
2483 } else {
2484 if (p->slots[0] == 0) {
2485 ret = btrfs_prev_leaf(root, p);
2486 if (ret < 0)
2487 return ret;
2488 if (!ret) {
2489 leaf = p->nodes[0];
2490 if (p->slots[0] == btrfs_header_nritems(leaf))
2491 p->slots[0]--;
2492 return 0;
2493 }
2494 if (!return_any)
2495 return 1;
2496 /*
2497 * no lower item found, return the next
2498 * higher instead
2499 */
2500 return_any = 0;
2501 find_higher = 1;
2502 btrfs_release_path(p);
2503 goto again;
2504 } else {
2505 --p->slots[0];
2506 }
2507 }
2508 return 0;
2509 }
2510
2511 /*
2512 * Execute search and call btrfs_previous_item to traverse backwards if the item
2513 * was not found.
2514 *
2515 * Return 0 if found, 1 if not found and < 0 if error.
2516 */
2517 int btrfs_search_backwards(struct btrfs_root *root, struct btrfs_key *key,
2518 struct btrfs_path *path)
2519 {
2520 int ret;
2521
2522 ret = btrfs_search_slot(NULL, root, key, path, 0, 0);
2523 if (ret > 0)
2524 ret = btrfs_previous_item(root, path, key->objectid, key->type);
2525
2526 if (ret == 0)
2527 btrfs_item_key_to_cpu(path->nodes[0], key, path->slots[0]);
2528
2529 return ret;
2530 }
2531
2532 /*
2533 * Search for a valid slot for the given path.
2534 *
2535 * @root: The root node of the tree.
2536 * @key: Will contain a valid item if found.
2537 * @path: The starting point to validate the slot.
2538 *
2539 * Return: 0 if the item is valid
2540 * 1 if not found
2541 * <0 if error.
2542 */
2543 int btrfs_get_next_valid_item(struct btrfs_root *root, struct btrfs_key *key,
2544 struct btrfs_path *path)
2545 {
2546 if (path->slots[0] >= btrfs_header_nritems(path->nodes[0])) {
2547 int ret;
2548
2549 ret = btrfs_next_leaf(root, path);
2550 if (ret)
2551 return ret;
2552 }
2553
2554 btrfs_item_key_to_cpu(path->nodes[0], key, path->slots[0]);
2555 return 0;
2556 }
2557
2558 /*
2559 * adjust the pointers going up the tree, starting at level
2560 * making sure the right key of each node is points to 'key'.
2561 * This is used after shifting pointers to the left, so it stops
2562 * fixing up pointers when a given leaf/node is not in slot 0 of the
2563 * higher levels
2564 *
2565 */
2566 static void fixup_low_keys(struct btrfs_trans_handle *trans,
2567 struct btrfs_path *path,
2568 struct btrfs_disk_key *key, int level)
2569 {
2570 int i;
2571 struct extent_buffer *t;
2572 int ret;
2573
2574 for (i = level; i < BTRFS_MAX_LEVEL; i++) {
2575 int tslot = path->slots[i];
2576
2577 if (!path->nodes[i])
2578 break;
2579 t = path->nodes[i];
2580 ret = btrfs_tree_mod_log_insert_key(t, tslot,
2581 BTRFS_MOD_LOG_KEY_REPLACE);
2582 BUG_ON(ret < 0);
2583 btrfs_set_node_key(t, key, tslot);
2584 btrfs_mark_buffer_dirty(trans, path->nodes[i]);
2585 if (tslot != 0)
2586 break;
2587 }
2588 }
2589
2590 /*
2591 * update item key.
2592 *
2593 * This function isn't completely safe. It's the caller's responsibility
2594 * that the new key won't break the order
2595 */
2596 void btrfs_set_item_key_safe(struct btrfs_trans_handle *trans,
2597 struct btrfs_path *path,
2598 const struct btrfs_key *new_key)
2599 {
2600 struct btrfs_fs_info *fs_info = trans->fs_info;
2601 struct btrfs_disk_key disk_key;
2602 struct extent_buffer *eb;
2603 int slot;
2604
2605 eb = path->nodes[0];
2606 slot = path->slots[0];
2607 if (slot > 0) {
2608 btrfs_item_key(eb, &disk_key, slot - 1);
2609 if (unlikely(btrfs_comp_keys(&disk_key, new_key) >= 0)) {
2610 btrfs_print_leaf(eb);
2611 btrfs_crit(fs_info,
2612 "slot %u key (%llu %u %llu) new key (%llu %u %llu)",
2613 slot, btrfs_disk_key_objectid(&disk_key),
2614 btrfs_disk_key_type(&disk_key),
2615 btrfs_disk_key_offset(&disk_key),
2616 new_key->objectid, new_key->type,
2617 new_key->offset);
2618 BUG();
2619 }
2620 }
2621 if (slot < btrfs_header_nritems(eb) - 1) {
2622 btrfs_item_key(eb, &disk_key, slot + 1);
2623 if (unlikely(btrfs_comp_keys(&disk_key, new_key) <= 0)) {
2624 btrfs_print_leaf(eb);
2625 btrfs_crit(fs_info,
2626 "slot %u key (%llu %u %llu) new key (%llu %u %llu)",
2627 slot, btrfs_disk_key_objectid(&disk_key),
2628 btrfs_disk_key_type(&disk_key),
2629 btrfs_disk_key_offset(&disk_key),
2630 new_key->objectid, new_key->type,
2631 new_key->offset);
2632 BUG();
2633 }
2634 }
2635
2636 btrfs_cpu_key_to_disk(&disk_key, new_key);
2637 btrfs_set_item_key(eb, &disk_key, slot);
2638 btrfs_mark_buffer_dirty(trans, eb);
2639 if (slot == 0)
2640 fixup_low_keys(trans, path, &disk_key, 1);
2641 }
2642
2643 /*
2644 * Check key order of two sibling extent buffers.
2645 *
2646 * Return true if something is wrong.
2647 * Return false if everything is fine.
2648 *
2649 * Tree-checker only works inside one tree block, thus the following
2650 * corruption can not be detected by tree-checker:
2651 *
2652 * Leaf @left | Leaf @right
2653 * --------------------------------------------------------------
2654 * | 1 | 2 | 3 | 4 | 5 | f6 | | 7 | 8 |
2655 *
2656 * Key f6 in leaf @left itself is valid, but not valid when the next
2657 * key in leaf @right is 7.
2658 * This can only be checked at tree block merge time.
2659 * And since tree checker has ensured all key order in each tree block
2660 * is correct, we only need to bother the last key of @left and the first
2661 * key of @right.
2662 */
2663 static bool check_sibling_keys(struct extent_buffer *left,
2664 struct extent_buffer *right)
2665 {
2666 struct btrfs_key left_last;
2667 struct btrfs_key right_first;
2668 int level = btrfs_header_level(left);
2669 int nr_left = btrfs_header_nritems(left);
2670 int nr_right = btrfs_header_nritems(right);
2671
2672 /* No key to check in one of the tree blocks */
2673 if (!nr_left || !nr_right)
2674 return false;
2675
2676 if (level) {
2677 btrfs_node_key_to_cpu(left, &left_last, nr_left - 1);
2678 btrfs_node_key_to_cpu(right, &right_first, 0);
2679 } else {
2680 btrfs_item_key_to_cpu(left, &left_last, nr_left - 1);
2681 btrfs_item_key_to_cpu(right, &right_first, 0);
2682 }
2683
2684 if (unlikely(btrfs_comp_cpu_keys(&left_last, &right_first) >= 0)) {
2685 btrfs_crit(left->fs_info, "left extent buffer:");
2686 btrfs_print_tree(left, false);
2687 btrfs_crit(left->fs_info, "right extent buffer:");
2688 btrfs_print_tree(right, false);
2689 btrfs_crit(left->fs_info,
2690 "bad key order, sibling blocks, left last (%llu %u %llu) right first (%llu %u %llu)",
2691 left_last.objectid, left_last.type,
2692 left_last.offset, right_first.objectid,
2693 right_first.type, right_first.offset);
2694 return true;
2695 }
2696 return false;
2697 }
2698
2699 /*
2700 * try to push data from one node into the next node left in the
2701 * tree.
2702 *
2703 * returns 0 if some ptrs were pushed left, < 0 if there was some horrible
2704 * error, and > 0 if there was no room in the left hand block.
2705 */
2706 static int push_node_left(struct btrfs_trans_handle *trans,
2707 struct extent_buffer *dst,
2708 struct extent_buffer *src, int empty)
2709 {
2710 struct btrfs_fs_info *fs_info = trans->fs_info;
2711 int push_items = 0;
2712 int src_nritems;
2713 int dst_nritems;
2714 int ret = 0;
2715
2716 src_nritems = btrfs_header_nritems(src);
2717 dst_nritems = btrfs_header_nritems(dst);
2718 push_items = BTRFS_NODEPTRS_PER_BLOCK(fs_info) - dst_nritems;
2719 WARN_ON(btrfs_header_generation(src) != trans->transid);
2720 WARN_ON(btrfs_header_generation(dst) != trans->transid);
2721
2722 if (!empty && src_nritems <= 8)
2723 return 1;
2724
2725 if (push_items <= 0)
2726 return 1;
2727
2728 if (empty) {
2729 push_items = min(src_nritems, push_items);
2730 if (push_items < src_nritems) {
2731 /* leave at least 8 pointers in the node if
2732 * we aren't going to empty it
2733 */
2734 if (src_nritems - push_items < 8) {
2735 if (push_items <= 8)
2736 return 1;
2737 push_items -= 8;
2738 }
2739 }
2740 } else
2741 push_items = min(src_nritems - 8, push_items);
2742
2743 /* dst is the left eb, src is the middle eb */
2744 if (check_sibling_keys(dst, src)) {
2745 ret = -EUCLEAN;
2746 btrfs_abort_transaction(trans, ret);
2747 return ret;
2748 }
2749 ret = btrfs_tree_mod_log_eb_copy(dst, src, dst_nritems, 0, push_items);
2750 if (ret) {
2751 btrfs_abort_transaction(trans, ret);
2752 return ret;
2753 }
2754 copy_extent_buffer(dst, src,
2755 btrfs_node_key_ptr_offset(dst, dst_nritems),
2756 btrfs_node_key_ptr_offset(src, 0),
2757 push_items * sizeof(struct btrfs_key_ptr));
2758
2759 if (push_items < src_nritems) {
2760 /*
2761 * btrfs_tree_mod_log_eb_copy handles logging the move, so we
2762 * don't need to do an explicit tree mod log operation for it.
2763 */
2764 memmove_extent_buffer(src, btrfs_node_key_ptr_offset(src, 0),
2765 btrfs_node_key_ptr_offset(src, push_items),
2766 (src_nritems - push_items) *
2767 sizeof(struct btrfs_key_ptr));
2768 }
2769 btrfs_set_header_nritems(src, src_nritems - push_items);
2770 btrfs_set_header_nritems(dst, dst_nritems + push_items);
2771 btrfs_mark_buffer_dirty(trans, src);
2772 btrfs_mark_buffer_dirty(trans, dst);
2773
2774 return ret;
2775 }
2776
2777 /*
2778 * try to push data from one node into the next node right in the
2779 * tree.
2780 *
2781 * returns 0 if some ptrs were pushed, < 0 if there was some horrible
2782 * error, and > 0 if there was no room in the right hand block.
2783 *
2784 * this will only push up to 1/2 the contents of the left node over
2785 */
2786 static int balance_node_right(struct btrfs_trans_handle *trans,
2787 struct extent_buffer *dst,
2788 struct extent_buffer *src)
2789 {
2790 struct btrfs_fs_info *fs_info = trans->fs_info;
2791 int push_items = 0;
2792 int max_push;
2793 int src_nritems;
2794 int dst_nritems;
2795 int ret = 0;
2796
2797 WARN_ON(btrfs_header_generation(src) != trans->transid);
2798 WARN_ON(btrfs_header_generation(dst) != trans->transid);
2799
2800 src_nritems = btrfs_header_nritems(src);
2801 dst_nritems = btrfs_header_nritems(dst);
2802 push_items = BTRFS_NODEPTRS_PER_BLOCK(fs_info) - dst_nritems;
2803 if (push_items <= 0)
2804 return 1;
2805
2806 if (src_nritems < 4)
2807 return 1;
2808
2809 max_push = src_nritems / 2 + 1;
2810 /* don't try to empty the node */
2811 if (max_push >= src_nritems)
2812 return 1;
2813
2814 if (max_push < push_items)
2815 push_items = max_push;
2816
2817 /* dst is the right eb, src is the middle eb */
2818 if (check_sibling_keys(src, dst)) {
2819 ret = -EUCLEAN;
2820 btrfs_abort_transaction(trans, ret);
2821 return ret;
2822 }
2823
2824 /*
2825 * btrfs_tree_mod_log_eb_copy handles logging the move, so we don't
2826 * need to do an explicit tree mod log operation for it.
2827 */
2828 memmove_extent_buffer(dst, btrfs_node_key_ptr_offset(dst, push_items),
2829 btrfs_node_key_ptr_offset(dst, 0),
2830 (dst_nritems) *
2831 sizeof(struct btrfs_key_ptr));
2832
2833 ret = btrfs_tree_mod_log_eb_copy(dst, src, 0, src_nritems - push_items,
2834 push_items);
2835 if (ret) {
2836 btrfs_abort_transaction(trans, ret);
2837 return ret;
2838 }
2839 copy_extent_buffer(dst, src,
2840 btrfs_node_key_ptr_offset(dst, 0),
2841 btrfs_node_key_ptr_offset(src, src_nritems - push_items),
2842 push_items * sizeof(struct btrfs_key_ptr));
2843
2844 btrfs_set_header_nritems(src, src_nritems - push_items);
2845 btrfs_set_header_nritems(dst, dst_nritems + push_items);
2846
2847 btrfs_mark_buffer_dirty(trans, src);
2848 btrfs_mark_buffer_dirty(trans, dst);
2849
2850 return ret;
2851 }
2852
2853 /*
2854 * helper function to insert a new root level in the tree.
2855 * A new node is allocated, and a single item is inserted to
2856 * point to the existing root
2857 *
2858 * returns zero on success or < 0 on failure.
2859 */
2860 static noinline int insert_new_root(struct btrfs_trans_handle *trans,
2861 struct btrfs_root *root,
2862 struct btrfs_path *path, int level)
2863 {
2864 u64 lower_gen;
2865 struct extent_buffer *lower;
2866 struct extent_buffer *c;
2867 struct extent_buffer *old;
2868 struct btrfs_disk_key lower_key;
2869 int ret;
2870
2871 BUG_ON(path->nodes[level]);
2872 BUG_ON(path->nodes[level-1] != root->node);
2873
2874 lower = path->nodes[level-1];
2875 if (level == 1)
2876 btrfs_item_key(lower, &lower_key, 0);
2877 else
2878 btrfs_node_key(lower, &lower_key, 0);
2879
2880 c = btrfs_alloc_tree_block(trans, root, 0, btrfs_root_id(root),
2881 &lower_key, level, root->node->start, 0,
2882 0, BTRFS_NESTING_NEW_ROOT);
2883 if (IS_ERR(c))
2884 return PTR_ERR(c);
2885
2886 root_add_used_bytes(root);
2887
2888 btrfs_set_header_nritems(c, 1);
2889 btrfs_set_node_key(c, &lower_key, 0);
2890 btrfs_set_node_blockptr(c, 0, lower->start);
2891 lower_gen = btrfs_header_generation(lower);
2892 WARN_ON(lower_gen != trans->transid);
2893
2894 btrfs_set_node_ptr_generation(c, 0, lower_gen);
2895
2896 btrfs_mark_buffer_dirty(trans, c);
2897
2898 old = root->node;
2899 ret = btrfs_tree_mod_log_insert_root(root->node, c, false);
2900 if (ret < 0) {
2901 int ret2;
2902
2903 ret2 = btrfs_free_tree_block(trans, btrfs_root_id(root), c, 0, 1);
2904 if (ret2 < 0)
2905 btrfs_abort_transaction(trans, ret2);
2906 btrfs_tree_unlock(c);
2907 free_extent_buffer(c);
2908 return ret;
2909 }
2910 rcu_assign_pointer(root->node, c);
2911
2912 /* the super has an extra ref to root->node */
2913 free_extent_buffer(old);
2914
2915 add_root_to_dirty_list(root);
2916 atomic_inc(&c->refs);
2917 path->nodes[level] = c;
2918 path->locks[level] = BTRFS_WRITE_LOCK;
2919 path->slots[level] = 0;
2920 return 0;
2921 }
2922
2923 /*
2924 * worker function to insert a single pointer in a node.
2925 * the node should have enough room for the pointer already
2926 *
2927 * slot and level indicate where you want the key to go, and
2928 * blocknr is the block the key points to.
2929 */
2930 static int insert_ptr(struct btrfs_trans_handle *trans,
2931 struct btrfs_path *path,
2932 struct btrfs_disk_key *key, u64 bytenr,
2933 int slot, int level)
2934 {
2935 struct extent_buffer *lower;
2936 int nritems;
2937 int ret;
2938
2939 BUG_ON(!path->nodes[level]);
2940 btrfs_assert_tree_write_locked(path->nodes[level]);
2941 lower = path->nodes[level];
2942 nritems = btrfs_header_nritems(lower);
2943 BUG_ON(slot > nritems);
2944 BUG_ON(nritems == BTRFS_NODEPTRS_PER_BLOCK(trans->fs_info));
2945 if (slot != nritems) {
2946 if (level) {
2947 ret = btrfs_tree_mod_log_insert_move(lower, slot + 1,
2948 slot, nritems - slot);
2949 if (ret < 0) {
2950 btrfs_abort_transaction(trans, ret);
2951 return ret;
2952 }
2953 }
2954 memmove_extent_buffer(lower,
2955 btrfs_node_key_ptr_offset(lower, slot + 1),
2956 btrfs_node_key_ptr_offset(lower, slot),
2957 (nritems - slot) * sizeof(struct btrfs_key_ptr));
2958 }
2959 if (level) {
2960 ret = btrfs_tree_mod_log_insert_key(lower, slot,
2961 BTRFS_MOD_LOG_KEY_ADD);
2962 if (ret < 0) {
2963 btrfs_abort_transaction(trans, ret);
2964 return ret;
2965 }
2966 }
2967 btrfs_set_node_key(lower, key, slot);
2968 btrfs_set_node_blockptr(lower, slot, bytenr);
2969 WARN_ON(trans->transid == 0);
2970 btrfs_set_node_ptr_generation(lower, slot, trans->transid);
2971 btrfs_set_header_nritems(lower, nritems + 1);
2972 btrfs_mark_buffer_dirty(trans, lower);
2973
2974 return 0;
2975 }
2976
2977 /*
2978 * split the node at the specified level in path in two.
2979 * The path is corrected to point to the appropriate node after the split
2980 *
2981 * Before splitting this tries to make some room in the node by pushing
2982 * left and right, if either one works, it returns right away.
2983 *
2984 * returns 0 on success and < 0 on failure
2985 */
2986 static noinline int split_node(struct btrfs_trans_handle *trans,
2987 struct btrfs_root *root,
2988 struct btrfs_path *path, int level)
2989 {
2990 struct btrfs_fs_info *fs_info = root->fs_info;
2991 struct extent_buffer *c;
2992 struct extent_buffer *split;
2993 struct btrfs_disk_key disk_key;
2994 int mid;
2995 int ret;
2996 u32 c_nritems;
2997
2998 c = path->nodes[level];
2999 WARN_ON(btrfs_header_generation(c) != trans->transid);
3000 if (c == root->node) {
3001 /*
3002 * trying to split the root, lets make a new one
3003 *
3004 * tree mod log: We don't log_removal old root in
3005 * insert_new_root, because that root buffer will be kept as a
3006 * normal node. We are going to log removal of half of the
3007 * elements below with btrfs_tree_mod_log_eb_copy(). We're
3008 * holding a tree lock on the buffer, which is why we cannot
3009 * race with other tree_mod_log users.
3010 */
3011 ret = insert_new_root(trans, root, path, level + 1);
3012 if (ret)
3013 return ret;
3014 } else {
3015 ret = push_nodes_for_insert(trans, root, path, level);
3016 c = path->nodes[level];
3017 if (!ret && btrfs_header_nritems(c) <
3018 BTRFS_NODEPTRS_PER_BLOCK(fs_info) - 3)
3019 return 0;
3020 if (ret < 0)
3021 return ret;
3022 }
3023
3024 c_nritems = btrfs_header_nritems(c);
3025 mid = (c_nritems + 1) / 2;
3026 btrfs_node_key(c, &disk_key, mid);
3027
3028 split = btrfs_alloc_tree_block(trans, root, 0, btrfs_root_id(root),
3029 &disk_key, level, c->start, 0,
3030 0, BTRFS_NESTING_SPLIT);
3031 if (IS_ERR(split))
3032 return PTR_ERR(split);
3033
3034 root_add_used_bytes(root);
3035 ASSERT(btrfs_header_level(c) == level);
3036
3037 ret = btrfs_tree_mod_log_eb_copy(split, c, 0, mid, c_nritems - mid);
3038 if (ret) {
3039 btrfs_tree_unlock(split);
3040 free_extent_buffer(split);
3041 btrfs_abort_transaction(trans, ret);
3042 return ret;
3043 }
3044 copy_extent_buffer(split, c,
3045 btrfs_node_key_ptr_offset(split, 0),
3046 btrfs_node_key_ptr_offset(c, mid),
3047 (c_nritems - mid) * sizeof(struct btrfs_key_ptr));
3048 btrfs_set_header_nritems(split, c_nritems - mid);
3049 btrfs_set_header_nritems(c, mid);
3050
3051 btrfs_mark_buffer_dirty(trans, c);
3052 btrfs_mark_buffer_dirty(trans, split);
3053
3054 ret = insert_ptr(trans, path, &disk_key, split->start,
3055 path->slots[level + 1] + 1, level + 1);
3056 if (ret < 0) {
3057 btrfs_tree_unlock(split);
3058 free_extent_buffer(split);
3059 return ret;
3060 }
3061
3062 if (path->slots[level] >= mid) {
3063 path->slots[level] -= mid;
3064 btrfs_tree_unlock(c);
3065 free_extent_buffer(c);
3066 path->nodes[level] = split;
3067 path->slots[level + 1] += 1;
3068 } else {
3069 btrfs_tree_unlock(split);
3070 free_extent_buffer(split);
3071 }
3072 return 0;
3073 }
3074
3075 /*
3076 * how many bytes are required to store the items in a leaf. start
3077 * and nr indicate which items in the leaf to check. This totals up the
3078 * space used both by the item structs and the item data
3079 */
3080 static int leaf_space_used(const struct extent_buffer *l, int start, int nr)
3081 {
3082 int data_len;
3083 int nritems = btrfs_header_nritems(l);
3084 int end = min(nritems, start + nr) - 1;
3085
3086 if (!nr)
3087 return 0;
3088 data_len = btrfs_item_offset(l, start) + btrfs_item_size(l, start);
3089 data_len = data_len - btrfs_item_offset(l, end);
3090 data_len += sizeof(struct btrfs_item) * nr;
3091 WARN_ON(data_len < 0);
3092 return data_len;
3093 }
3094
3095 /*
3096 * The space between the end of the leaf items and
3097 * the start of the leaf data. IOW, how much room
3098 * the leaf has left for both items and data
3099 */
3100 int btrfs_leaf_free_space(const struct extent_buffer *leaf)
3101 {
3102 struct btrfs_fs_info *fs_info = leaf->fs_info;
3103 int nritems = btrfs_header_nritems(leaf);
3104 int ret;
3105
3106 ret = BTRFS_LEAF_DATA_SIZE(fs_info) - leaf_space_used(leaf, 0, nritems);
3107 if (ret < 0) {
3108 btrfs_crit(fs_info,
3109 "leaf free space ret %d, leaf data size %lu, used %d nritems %d",
3110 ret,
3111 (unsigned long) BTRFS_LEAF_DATA_SIZE(fs_info),
3112 leaf_space_used(leaf, 0, nritems), nritems);
3113 }
3114 return ret;
3115 }
3116
3117 /*
3118 * min slot controls the lowest index we're willing to push to the
3119 * right. We'll push up to and including min_slot, but no lower
3120 */
3121 static noinline int __push_leaf_right(struct btrfs_trans_handle *trans,
3122 struct btrfs_path *path,
3123 int data_size, int empty,
3124 struct extent_buffer *right,
3125 int free_space, u32 left_nritems,
3126 u32 min_slot)
3127 {
3128 struct btrfs_fs_info *fs_info = right->fs_info;
3129 struct extent_buffer *left = path->nodes[0];
3130 struct extent_buffer *upper = path->nodes[1];
3131 struct btrfs_map_token token;
3132 struct btrfs_disk_key disk_key;
3133 int slot;
3134 u32 i;
3135 int push_space = 0;
3136 int push_items = 0;
3137 u32 nr;
3138 u32 right_nritems;
3139 u32 data_end;
3140 u32 this_item_size;
3141
3142 if (empty)
3143 nr = 0;
3144 else
3145 nr = max_t(u32, 1, min_slot);
3146
3147 if (path->slots[0] >= left_nritems)
3148 push_space += data_size;
3149
3150 slot = path->slots[1];
3151 i = left_nritems - 1;
3152 while (i >= nr) {
3153 if (!empty && push_items > 0) {
3154 if (path->slots[0] > i)
3155 break;
3156 if (path->slots[0] == i) {
3157 int space = btrfs_leaf_free_space(left);
3158
3159 if (space + push_space * 2 > free_space)
3160 break;
3161 }
3162 }
3163
3164 if (path->slots[0] == i)
3165 push_space += data_size;
3166
3167 this_item_size = btrfs_item_size(left, i);
3168 if (this_item_size + sizeof(struct btrfs_item) +
3169 push_space > free_space)
3170 break;
3171
3172 push_items++;
3173 push_space += this_item_size + sizeof(struct btrfs_item);
3174 if (i == 0)
3175 break;
3176 i--;
3177 }
3178
3179 if (push_items == 0)
3180 goto out_unlock;
3181
3182 WARN_ON(!empty && push_items == left_nritems);
3183
3184 /* push left to right */
3185 right_nritems = btrfs_header_nritems(right);
3186
3187 push_space = btrfs_item_data_end(left, left_nritems - push_items);
3188 push_space -= leaf_data_end(left);
3189
3190 /* make room in the right data area */
3191 data_end = leaf_data_end(right);
3192 memmove_leaf_data(right, data_end - push_space, data_end,
3193 BTRFS_LEAF_DATA_SIZE(fs_info) - data_end);
3194
3195 /* copy from the left data area */
3196 copy_leaf_data(right, left, BTRFS_LEAF_DATA_SIZE(fs_info) - push_space,
3197 leaf_data_end(left), push_space);
3198
3199 memmove_leaf_items(right, push_items, 0, right_nritems);
3200
3201 /* copy the items from left to right */
3202 copy_leaf_items(right, left, 0, left_nritems - push_items, push_items);
3203
3204 /* update the item pointers */
3205 btrfs_init_map_token(&token, right);
3206 right_nritems += push_items;
3207 btrfs_set_header_nritems(right, right_nritems);
3208 push_space = BTRFS_LEAF_DATA_SIZE(fs_info);
3209 for (i = 0; i < right_nritems; i++) {
3210 push_space -= btrfs_token_item_size(&token, i);
3211 btrfs_set_token_item_offset(&token, i, push_space);
3212 }
3213
3214 left_nritems -= push_items;
3215 btrfs_set_header_nritems(left, left_nritems);
3216
3217 if (left_nritems)
3218 btrfs_mark_buffer_dirty(trans, left);
3219 else
3220 btrfs_clear_buffer_dirty(trans, left);
3221
3222 btrfs_mark_buffer_dirty(trans, right);
3223
3224 btrfs_item_key(right, &disk_key, 0);
3225 btrfs_set_node_key(upper, &disk_key, slot + 1);
3226 btrfs_mark_buffer_dirty(trans, upper);
3227
3228 /* then fixup the leaf pointer in the path */
3229 if (path->slots[0] >= left_nritems) {
3230 path->slots[0] -= left_nritems;
3231 if (btrfs_header_nritems(path->nodes[0]) == 0)
3232 btrfs_clear_buffer_dirty(trans, path->nodes[0]);
3233 btrfs_tree_unlock(path->nodes[0]);
3234 free_extent_buffer(path->nodes[0]);
3235 path->nodes[0] = right;
3236 path->slots[1] += 1;
3237 } else {
3238 btrfs_tree_unlock(right);
3239 free_extent_buffer(right);
3240 }
3241 return 0;
3242
3243 out_unlock:
3244 btrfs_tree_unlock(right);
3245 free_extent_buffer(right);
3246 return 1;
3247 }
3248
3249 /*
3250 * push some data in the path leaf to the right, trying to free up at
3251 * least data_size bytes. returns zero if the push worked, nonzero otherwise
3252 *
3253 * returns 1 if the push failed because the other node didn't have enough
3254 * room, 0 if everything worked out and < 0 if there were major errors.
3255 *
3256 * this will push starting from min_slot to the end of the leaf. It won't
3257 * push any slot lower than min_slot
3258 */
3259 static int push_leaf_right(struct btrfs_trans_handle *trans, struct btrfs_root
3260 *root, struct btrfs_path *path,
3261 int min_data_size, int data_size,
3262 int empty, u32 min_slot)
3263 {
3264 struct extent_buffer *left = path->nodes[0];
3265 struct extent_buffer *right;
3266 struct extent_buffer *upper;
3267 int slot;
3268 int free_space;
3269 u32 left_nritems;
3270 int ret;
3271
3272 if (!path->nodes[1])
3273 return 1;
3274
3275 slot = path->slots[1];
3276 upper = path->nodes[1];
3277 if (slot >= btrfs_header_nritems(upper) - 1)
3278 return 1;
3279
3280 btrfs_assert_tree_write_locked(path->nodes[1]);
3281
3282 right = btrfs_read_node_slot(upper, slot + 1);
3283 if (IS_ERR(right))
3284 return PTR_ERR(right);
3285
3286 btrfs_tree_lock_nested(right, BTRFS_NESTING_RIGHT);
3287
3288 free_space = btrfs_leaf_free_space(right);
3289 if (free_space < data_size)
3290 goto out_unlock;
3291
3292 ret = btrfs_cow_block(trans, root, right, upper,
3293 slot + 1, &right, BTRFS_NESTING_RIGHT_COW);
3294 if (ret)
3295 goto out_unlock;
3296
3297 left_nritems = btrfs_header_nritems(left);
3298 if (left_nritems == 0)
3299 goto out_unlock;
3300
3301 if (check_sibling_keys(left, right)) {
3302 ret = -EUCLEAN;
3303 btrfs_abort_transaction(trans, ret);
3304 btrfs_tree_unlock(right);
3305 free_extent_buffer(right);
3306 return ret;
3307 }
3308 if (path->slots[0] == left_nritems && !empty) {
3309 /* Key greater than all keys in the leaf, right neighbor has
3310 * enough room for it and we're not emptying our leaf to delete
3311 * it, therefore use right neighbor to insert the new item and
3312 * no need to touch/dirty our left leaf. */
3313 btrfs_tree_unlock(left);
3314 free_extent_buffer(left);
3315 path->nodes[0] = right;
3316 path->slots[0] = 0;
3317 path->slots[1]++;
3318 return 0;
3319 }
3320
3321 return __push_leaf_right(trans, path, min_data_size, empty, right,
3322 free_space, left_nritems, min_slot);
3323 out_unlock:
3324 btrfs_tree_unlock(right);
3325 free_extent_buffer(right);
3326 return 1;
3327 }
3328
3329 /*
3330 * push some data in the path leaf to the left, trying to free up at
3331 * least data_size bytes. returns zero if the push worked, nonzero otherwise
3332 *
3333 * max_slot can put a limit on how far into the leaf we'll push items. The
3334 * item at 'max_slot' won't be touched. Use (u32)-1 to make us do all the
3335 * items
3336 */
3337 static noinline int __push_leaf_left(struct btrfs_trans_handle *trans,
3338 struct btrfs_path *path, int data_size,
3339 int empty, struct extent_buffer *left,
3340 int free_space, u32 right_nritems,
3341 u32 max_slot)
3342 {
3343 struct btrfs_fs_info *fs_info = left->fs_info;
3344 struct btrfs_disk_key disk_key;
3345 struct extent_buffer *right = path->nodes[0];
3346 int i;
3347 int push_space = 0;
3348 int push_items = 0;
3349 u32 old_left_nritems;
3350 u32 nr;
3351 int ret = 0;
3352 u32 this_item_size;
3353 u32 old_left_item_size;
3354 struct btrfs_map_token token;
3355
3356 if (empty)
3357 nr = min(right_nritems, max_slot);
3358 else
3359 nr = min(right_nritems - 1, max_slot);
3360
3361 for (i = 0; i < nr; i++) {
3362 if (!empty && push_items > 0) {
3363 if (path->slots[0] < i)
3364 break;
3365 if (path->slots[0] == i) {
3366 int space = btrfs_leaf_free_space(right);
3367
3368 if (space + push_space * 2 > free_space)
3369 break;
3370 }
3371 }
3372
3373 if (path->slots[0] == i)
3374 push_space += data_size;
3375
3376 this_item_size = btrfs_item_size(right, i);
3377 if (this_item_size + sizeof(struct btrfs_item) + push_space >
3378 free_space)
3379 break;
3380
3381 push_items++;
3382 push_space += this_item_size + sizeof(struct btrfs_item);
3383 }
3384
3385 if (push_items == 0) {
3386 ret = 1;
3387 goto out;
3388 }
3389 WARN_ON(!empty && push_items == btrfs_header_nritems(right));
3390
3391 /* push data from right to left */
3392 copy_leaf_items(left, right, btrfs_header_nritems(left), 0, push_items);
3393
3394 push_space = BTRFS_LEAF_DATA_SIZE(fs_info) -
3395 btrfs_item_offset(right, push_items - 1);
3396
3397 copy_leaf_data(left, right, leaf_data_end(left) - push_space,
3398 btrfs_item_offset(right, push_items - 1), push_space);
3399 old_left_nritems = btrfs_header_nritems(left);
3400 BUG_ON(old_left_nritems <= 0);
3401
3402 btrfs_init_map_token(&token, left);
3403 old_left_item_size = btrfs_item_offset(left, old_left_nritems - 1);
3404 for (i = old_left_nritems; i < old_left_nritems + push_items; i++) {
3405 u32 ioff;
3406
3407 ioff = btrfs_token_item_offset(&token, i);
3408 btrfs_set_token_item_offset(&token, i,
3409 ioff - (BTRFS_LEAF_DATA_SIZE(fs_info) - old_left_item_size));
3410 }
3411 btrfs_set_header_nritems(left, old_left_nritems + push_items);
3412
3413 /* fixup right node */
3414 if (push_items > right_nritems)
3415 WARN(1, KERN_CRIT "push items %d nr %u\n", push_items,
3416 right_nritems);
3417
3418 if (push_items < right_nritems) {
3419 push_space = btrfs_item_offset(right, push_items - 1) -
3420 leaf_data_end(right);
3421 memmove_leaf_data(right,
3422 BTRFS_LEAF_DATA_SIZE(fs_info) - push_space,
3423 leaf_data_end(right), push_space);
3424
3425 memmove_leaf_items(right, 0, push_items,
3426 btrfs_header_nritems(right) - push_items);
3427 }
3428
3429 btrfs_init_map_token(&token, right);
3430 right_nritems -= push_items;
3431 btrfs_set_header_nritems(right, right_nritems);
3432 push_space = BTRFS_LEAF_DATA_SIZE(fs_info);
3433 for (i = 0; i < right_nritems; i++) {
3434 push_space = push_space - btrfs_token_item_size(&token, i);
3435 btrfs_set_token_item_offset(&token, i, push_space);
3436 }
3437
3438 btrfs_mark_buffer_dirty(trans, left);
3439 if (right_nritems)
3440 btrfs_mark_buffer_dirty(trans, right);
3441 else
3442 btrfs_clear_buffer_dirty(trans, right);
3443
3444 btrfs_item_key(right, &disk_key, 0);
3445 fixup_low_keys(trans, path, &disk_key, 1);
3446
3447 /* then fixup the leaf pointer in the path */
3448 if (path->slots[0] < push_items) {
3449 path->slots[0] += old_left_nritems;
3450 btrfs_tree_unlock(path->nodes[0]);
3451 free_extent_buffer(path->nodes[0]);
3452 path->nodes[0] = left;
3453 path->slots[1] -= 1;
3454 } else {
3455 btrfs_tree_unlock(left);
3456 free_extent_buffer(left);
3457 path->slots[0] -= push_items;
3458 }
3459 BUG_ON(path->slots[0] < 0);
3460 return ret;
3461 out:
3462 btrfs_tree_unlock(left);
3463 free_extent_buffer(left);
3464 return ret;
3465 }
3466
3467 /*
3468 * push some data in the path leaf to the left, trying to free up at
3469 * least data_size bytes. returns zero if the push worked, nonzero otherwise
3470 *
3471 * max_slot can put a limit on how far into the leaf we'll push items. The
3472 * item at 'max_slot' won't be touched. Use (u32)-1 to make us push all the
3473 * items
3474 */
3475 static int push_leaf_left(struct btrfs_trans_handle *trans, struct btrfs_root
3476 *root, struct btrfs_path *path, int min_data_size,
3477 int data_size, int empty, u32 max_slot)
3478 {
3479 struct extent_buffer *right = path->nodes[0];
3480 struct extent_buffer *left;
3481 int slot;
3482 int free_space;
3483 u32 right_nritems;
3484 int ret = 0;
3485
3486 slot = path->slots[1];
3487 if (slot == 0)
3488 return 1;
3489 if (!path->nodes[1])
3490 return 1;
3491
3492 right_nritems = btrfs_header_nritems(right);
3493 if (right_nritems == 0)
3494 return 1;
3495
3496 btrfs_assert_tree_write_locked(path->nodes[1]);
3497
3498 left = btrfs_read_node_slot(path->nodes[1], slot - 1);
3499 if (IS_ERR(left))
3500 return PTR_ERR(left);
3501
3502 btrfs_tree_lock_nested(left, BTRFS_NESTING_LEFT);
3503
3504 free_space = btrfs_leaf_free_space(left);
3505 if (free_space < data_size) {
3506 ret = 1;
3507 goto out;
3508 }
3509
3510 ret = btrfs_cow_block(trans, root, left,
3511 path->nodes[1], slot - 1, &left,
3512 BTRFS_NESTING_LEFT_COW);
3513 if (ret) {
3514 /* we hit -ENOSPC, but it isn't fatal here */
3515 if (ret == -ENOSPC)
3516 ret = 1;
3517 goto out;
3518 }
3519
3520 if (check_sibling_keys(left, right)) {
3521 ret = -EUCLEAN;
3522 btrfs_abort_transaction(trans, ret);
3523 goto out;
3524 }
3525 return __push_leaf_left(trans, path, min_data_size, empty, left,
3526 free_space, right_nritems, max_slot);
3527 out:
3528 btrfs_tree_unlock(left);
3529 free_extent_buffer(left);
3530 return ret;
3531 }
3532
3533 /*
3534 * split the path's leaf in two, making sure there is at least data_size
3535 * available for the resulting leaf level of the path.
3536 */
3537 static noinline int copy_for_split(struct btrfs_trans_handle *trans,
3538 struct btrfs_path *path,
3539 struct extent_buffer *l,
3540 struct extent_buffer *right,
3541 int slot, int mid, int nritems)
3542 {
3543 struct btrfs_fs_info *fs_info = trans->fs_info;
3544 int data_copy_size;
3545 int rt_data_off;
3546 int i;
3547 int ret;
3548 struct btrfs_disk_key disk_key;
3549 struct btrfs_map_token token;
3550
3551 nritems = nritems - mid;
3552 btrfs_set_header_nritems(right, nritems);
3553 data_copy_size = btrfs_item_data_end(l, mid) - leaf_data_end(l);
3554
3555 copy_leaf_items(right, l, 0, mid, nritems);
3556
3557 copy_leaf_data(right, l, BTRFS_LEAF_DATA_SIZE(fs_info) - data_copy_size,
3558 leaf_data_end(l), data_copy_size);
3559
3560 rt_data_off = BTRFS_LEAF_DATA_SIZE(fs_info) - btrfs_item_data_end(l, mid);
3561
3562 btrfs_init_map_token(&token, right);
3563 for (i = 0; i < nritems; i++) {
3564 u32 ioff;
3565
3566 ioff = btrfs_token_item_offset(&token, i);
3567 btrfs_set_token_item_offset(&token, i, ioff + rt_data_off);
3568 }
3569
3570 btrfs_set_header_nritems(l, mid);
3571 btrfs_item_key(right, &disk_key, 0);
3572 ret = insert_ptr(trans, path, &disk_key, right->start, path->slots[1] + 1, 1);
3573 if (ret < 0)
3574 return ret;
3575
3576 btrfs_mark_buffer_dirty(trans, right);
3577 btrfs_mark_buffer_dirty(trans, l);
3578 BUG_ON(path->slots[0] != slot);
3579
3580 if (mid <= slot) {
3581 btrfs_tree_unlock(path->nodes[0]);
3582 free_extent_buffer(path->nodes[0]);
3583 path->nodes[0] = right;
3584 path->slots[0] -= mid;
3585 path->slots[1] += 1;
3586 } else {
3587 btrfs_tree_unlock(right);
3588 free_extent_buffer(right);
3589 }
3590
3591 BUG_ON(path->slots[0] < 0);
3592
3593 return 0;
3594 }
3595
3596 /*
3597 * double splits happen when we need to insert a big item in the middle
3598 * of a leaf. A double split can leave us with 3 mostly empty leaves:
3599 * leaf: [ slots 0 - N] [ our target ] [ N + 1 - total in leaf ]
3600 * A B C
3601 *
3602 * We avoid this by trying to push the items on either side of our target
3603 * into the adjacent leaves. If all goes well we can avoid the double split
3604 * completely.
3605 */
3606 static noinline int push_for_double_split(struct btrfs_trans_handle *trans,
3607 struct btrfs_root *root,
3608 struct btrfs_path *path,
3609 int data_size)
3610 {
3611 int ret;
3612 int progress = 0;
3613 int slot;
3614 u32 nritems;
3615 int space_needed = data_size;
3616
3617 slot = path->slots[0];
3618 if (slot < btrfs_header_nritems(path->nodes[0]))
3619 space_needed -= btrfs_leaf_free_space(path->nodes[0]);
3620
3621 /*
3622 * try to push all the items after our slot into the
3623 * right leaf
3624 */
3625 ret = push_leaf_right(trans, root, path, 1, space_needed, 0, slot);
3626 if (ret < 0)
3627 return ret;
3628
3629 if (ret == 0)
3630 progress++;
3631
3632 nritems = btrfs_header_nritems(path->nodes[0]);
3633 /*
3634 * our goal is to get our slot at the start or end of a leaf. If
3635 * we've done so we're done
3636 */
3637 if (path->slots[0] == 0 || path->slots[0] == nritems)
3638 return 0;
3639
3640 if (btrfs_leaf_free_space(path->nodes[0]) >= data_size)
3641 return 0;
3642
3643 /* try to push all the items before our slot into the next leaf */
3644 slot = path->slots[0];
3645 space_needed = data_size;
3646 if (slot > 0)
3647 space_needed -= btrfs_leaf_free_space(path->nodes[0]);
3648 ret = push_leaf_left(trans, root, path, 1, space_needed, 0, slot);
3649 if (ret < 0)
3650 return ret;
3651
3652 if (ret == 0)
3653 progress++;
3654
3655 if (progress)
3656 return 0;
3657 return 1;
3658 }
3659
3660 /*
3661 * split the path's leaf in two, making sure there is at least data_size
3662 * available for the resulting leaf level of the path.
3663 *
3664 * returns 0 if all went well and < 0 on failure.
3665 */
3666 static noinline int split_leaf(struct btrfs_trans_handle *trans,
3667 struct btrfs_root *root,
3668 const struct btrfs_key *ins_key,
3669 struct btrfs_path *path, int data_size,
3670 int extend)
3671 {
3672 struct btrfs_disk_key disk_key;
3673 struct extent_buffer *l;
3674 u32 nritems;
3675 int mid;
3676 int slot;
3677 struct extent_buffer *right;
3678 struct btrfs_fs_info *fs_info = root->fs_info;
3679 int ret = 0;
3680 int wret;
3681 int split;
3682 int num_doubles = 0;
3683 int tried_avoid_double = 0;
3684
3685 l = path->nodes[0];
3686 slot = path->slots[0];
3687 if (extend && data_size + btrfs_item_size(l, slot) +
3688 sizeof(struct btrfs_item) > BTRFS_LEAF_DATA_SIZE(fs_info))
3689 return -EOVERFLOW;
3690
3691 /* first try to make some room by pushing left and right */
3692 if (data_size && path->nodes[1]) {
3693 int space_needed = data_size;
3694
3695 if (slot < btrfs_header_nritems(l))
3696 space_needed -= btrfs_leaf_free_space(l);
3697
3698 wret = push_leaf_right(trans, root, path, space_needed,
3699 space_needed, 0, 0);
3700 if (wret < 0)
3701 return wret;
3702 if (wret) {
3703 space_needed = data_size;
3704 if (slot > 0)
3705 space_needed -= btrfs_leaf_free_space(l);
3706 wret = push_leaf_left(trans, root, path, space_needed,
3707 space_needed, 0, (u32)-1);
3708 if (wret < 0)
3709 return wret;
3710 }
3711 l = path->nodes[0];
3712
3713 /* did the pushes work? */
3714 if (btrfs_leaf_free_space(l) >= data_size)
3715 return 0;
3716 }
3717
3718 if (!path->nodes[1]) {
3719 ret = insert_new_root(trans, root, path, 1);
3720 if (ret)
3721 return ret;
3722 }
3723 again:
3724 split = 1;
3725 l = path->nodes[0];
3726 slot = path->slots[0];
3727 nritems = btrfs_header_nritems(l);
3728 mid = (nritems + 1) / 2;
3729
3730 if (mid <= slot) {
3731 if (nritems == 1 ||
3732 leaf_space_used(l, mid, nritems - mid) + data_size >
3733 BTRFS_LEAF_DATA_SIZE(fs_info)) {
3734 if (slot >= nritems) {
3735 split = 0;
3736 } else {
3737 mid = slot;
3738 if (mid != nritems &&
3739 leaf_space_used(l, mid, nritems - mid) +
3740 data_size > BTRFS_LEAF_DATA_SIZE(fs_info)) {
3741 if (data_size && !tried_avoid_double)
3742 goto push_for_double;
3743 split = 2;
3744 }
3745 }
3746 }
3747 } else {
3748 if (leaf_space_used(l, 0, mid) + data_size >
3749 BTRFS_LEAF_DATA_SIZE(fs_info)) {
3750 if (!extend && data_size && slot == 0) {
3751 split = 0;
3752 } else if ((extend || !data_size) && slot == 0) {
3753 mid = 1;
3754 } else {
3755 mid = slot;
3756 if (mid != nritems &&
3757 leaf_space_used(l, mid, nritems - mid) +
3758 data_size > BTRFS_LEAF_DATA_SIZE(fs_info)) {
3759 if (data_size && !tried_avoid_double)
3760 goto push_for_double;
3761 split = 2;
3762 }
3763 }
3764 }
3765 }
3766
3767 if (split == 0)
3768 btrfs_cpu_key_to_disk(&disk_key, ins_key);
3769 else
3770 btrfs_item_key(l, &disk_key, mid);
3771
3772 /*
3773 * We have to about BTRFS_NESTING_NEW_ROOT here if we've done a double
3774 * split, because we're only allowed to have MAX_LOCKDEP_SUBCLASSES
3775 * subclasses, which is 8 at the time of this patch, and we've maxed it
3776 * out. In the future we could add a
3777 * BTRFS_NESTING_SPLIT_THE_SPLITTENING if we need to, but for now just
3778 * use BTRFS_NESTING_NEW_ROOT.
3779 */
3780 right = btrfs_alloc_tree_block(trans, root, 0, btrfs_root_id(root),
3781 &disk_key, 0, l->start, 0, 0,
3782 num_doubles ? BTRFS_NESTING_NEW_ROOT :
3783 BTRFS_NESTING_SPLIT);
3784 if (IS_ERR(right))
3785 return PTR_ERR(right);
3786
3787 root_add_used_bytes(root);
3788
3789 if (split == 0) {
3790 if (mid <= slot) {
3791 btrfs_set_header_nritems(right, 0);
3792 ret = insert_ptr(trans, path, &disk_key,
3793 right->start, path->slots[1] + 1, 1);
3794 if (ret < 0) {
3795 btrfs_tree_unlock(right);
3796 free_extent_buffer(right);
3797 return ret;
3798 }
3799 btrfs_tree_unlock(path->nodes[0]);
3800 free_extent_buffer(path->nodes[0]);
3801 path->nodes[0] = right;
3802 path->slots[0] = 0;
3803 path->slots[1] += 1;
3804 } else {
3805 btrfs_set_header_nritems(right, 0);
3806 ret = insert_ptr(trans, path, &disk_key,
3807 right->start, path->slots[1], 1);
3808 if (ret < 0) {
3809 btrfs_tree_unlock(right);
3810 free_extent_buffer(right);
3811 return ret;
3812 }
3813 btrfs_tree_unlock(path->nodes[0]);
3814 free_extent_buffer(path->nodes[0]);
3815 path->nodes[0] = right;
3816 path->slots[0] = 0;
3817 if (path->slots[1] == 0)
3818 fixup_low_keys(trans, path, &disk_key, 1);
3819 }
3820 /*
3821 * We create a new leaf 'right' for the required ins_len and
3822 * we'll do btrfs_mark_buffer_dirty() on this leaf after copying
3823 * the content of ins_len to 'right'.
3824 */
3825 return ret;
3826 }
3827
3828 ret = copy_for_split(trans, path, l, right, slot, mid, nritems);
3829 if (ret < 0) {
3830 btrfs_tree_unlock(right);
3831 free_extent_buffer(right);
3832 return ret;
3833 }
3834
3835 if (split == 2) {
3836 BUG_ON(num_doubles != 0);
3837 num_doubles++;
3838 goto again;
3839 }
3840
3841 return 0;
3842
3843 push_for_double:
3844 push_for_double_split(trans, root, path, data_size);
3845 tried_avoid_double = 1;
3846 if (btrfs_leaf_free_space(path->nodes[0]) >= data_size)
3847 return 0;
3848 goto again;
3849 }
3850
3851 static noinline int setup_leaf_for_split(struct btrfs_trans_handle *trans,
3852 struct btrfs_root *root,
3853 struct btrfs_path *path, int ins_len)
3854 {
3855 struct btrfs_key key;
3856 struct extent_buffer *leaf;
3857 struct btrfs_file_extent_item *fi;
3858 u64 extent_len = 0;
3859 u32 item_size;
3860 int ret;
3861
3862 leaf = path->nodes[0];
3863 btrfs_item_key_to_cpu(leaf, &key, path->slots[0]);
3864
3865 BUG_ON(key.type != BTRFS_EXTENT_DATA_KEY &&
3866 key.type != BTRFS_EXTENT_CSUM_KEY);
3867
3868 if (btrfs_leaf_free_space(leaf) >= ins_len)
3869 return 0;
3870
3871 item_size = btrfs_item_size(leaf, path->slots[0]);
3872 if (key.type == BTRFS_EXTENT_DATA_KEY) {
3873 fi = btrfs_item_ptr(leaf, path->slots[0],
3874 struct btrfs_file_extent_item);
3875 extent_len = btrfs_file_extent_num_bytes(leaf, fi);
3876 }
3877 btrfs_release_path(path);
3878
3879 path->keep_locks = 1;
3880 path->search_for_split = 1;
3881 ret = btrfs_search_slot(trans, root, &key, path, 0, 1);
3882 path->search_for_split = 0;
3883 if (ret > 0)
3884 ret = -EAGAIN;
3885 if (ret < 0)
3886 goto err;
3887
3888 ret = -EAGAIN;
3889 leaf = path->nodes[0];
3890 /* if our item isn't there, return now */
3891 if (item_size != btrfs_item_size(leaf, path->slots[0]))
3892 goto err;
3893
3894 /* the leaf has changed, it now has room. return now */
3895 if (btrfs_leaf_free_space(path->nodes[0]) >= ins_len)
3896 goto err;
3897
3898 if (key.type == BTRFS_EXTENT_DATA_KEY) {
3899 fi = btrfs_item_ptr(leaf, path->slots[0],
3900 struct btrfs_file_extent_item);
3901 if (extent_len != btrfs_file_extent_num_bytes(leaf, fi))
3902 goto err;
3903 }
3904
3905 ret = split_leaf(trans, root, &key, path, ins_len, 1);
3906 if (ret)
3907 goto err;
3908
3909 path->keep_locks = 0;
3910 btrfs_unlock_up_safe(path, 1);
3911 return 0;
3912 err:
3913 path->keep_locks = 0;
3914 return ret;
3915 }
3916
3917 static noinline int split_item(struct btrfs_trans_handle *trans,
3918 struct btrfs_path *path,
3919 const struct btrfs_key *new_key,
3920 unsigned long split_offset)
3921 {
3922 struct extent_buffer *leaf;
3923 int orig_slot, slot;
3924 char *buf;
3925 u32 nritems;
3926 u32 item_size;
3927 u32 orig_offset;
3928 struct btrfs_disk_key disk_key;
3929
3930 leaf = path->nodes[0];
3931 /*
3932 * Shouldn't happen because the caller must have previously called
3933 * setup_leaf_for_split() to make room for the new item in the leaf.
3934 */
3935 if (WARN_ON(btrfs_leaf_free_space(leaf) < sizeof(struct btrfs_item)))
3936 return -ENOSPC;
3937
3938 orig_slot = path->slots[0];
3939 orig_offset = btrfs_item_offset(leaf, path->slots[0]);
3940 item_size = btrfs_item_size(leaf, path->slots[0]);
3941
3942 buf = kmalloc(item_size, GFP_NOFS);
3943 if (!buf)
3944 return -ENOMEM;
3945
3946 read_extent_buffer(leaf, buf, btrfs_item_ptr_offset(leaf,
3947 path->slots[0]), item_size);
3948
3949 slot = path->slots[0] + 1;
3950 nritems = btrfs_header_nritems(leaf);
3951 if (slot != nritems) {
3952 /* shift the items */
3953 memmove_leaf_items(leaf, slot + 1, slot, nritems - slot);
3954 }
3955
3956 btrfs_cpu_key_to_disk(&disk_key, new_key);
3957 btrfs_set_item_key(leaf, &disk_key, slot);
3958
3959 btrfs_set_item_offset(leaf, slot, orig_offset);
3960 btrfs_set_item_size(leaf, slot, item_size - split_offset);
3961
3962 btrfs_set_item_offset(leaf, orig_slot,
3963 orig_offset + item_size - split_offset);
3964 btrfs_set_item_size(leaf, orig_slot, split_offset);
3965
3966 btrfs_set_header_nritems(leaf, nritems + 1);
3967
3968 /* write the data for the start of the original item */
3969 write_extent_buffer(leaf, buf,
3970 btrfs_item_ptr_offset(leaf, path->slots[0]),
3971 split_offset);
3972
3973 /* write the data for the new item */
3974 write_extent_buffer(leaf, buf + split_offset,
3975 btrfs_item_ptr_offset(leaf, slot),
3976 item_size - split_offset);
3977 btrfs_mark_buffer_dirty(trans, leaf);
3978
3979 BUG_ON(btrfs_leaf_free_space(leaf) < 0);
3980 kfree(buf);
3981 return 0;
3982 }
3983
3984 /*
3985 * This function splits a single item into two items,
3986 * giving 'new_key' to the new item and splitting the
3987 * old one at split_offset (from the start of the item).
3988 *
3989 * The path may be released by this operation. After
3990 * the split, the path is pointing to the old item. The
3991 * new item is going to be in the same node as the old one.
3992 *
3993 * Note, the item being split must be smaller enough to live alone on
3994 * a tree block with room for one extra struct btrfs_item
3995 *
3996 * This allows us to split the item in place, keeping a lock on the
3997 * leaf the entire time.
3998 */
3999 int btrfs_split_item(struct btrfs_trans_handle *trans,
4000 struct btrfs_root *root,
4001 struct btrfs_path *path,
4002 const struct btrfs_key *new_key,
4003 unsigned long split_offset)
4004 {
4005 int ret;
4006 ret = setup_leaf_for_split(trans, root, path,
4007 sizeof(struct btrfs_item));
4008 if (ret)
4009 return ret;
4010
4011 ret = split_item(trans, path, new_key, split_offset);
4012 return ret;
4013 }
4014
4015 /*
4016 * make the item pointed to by the path smaller. new_size indicates
4017 * how small to make it, and from_end tells us if we just chop bytes
4018 * off the end of the item or if we shift the item to chop bytes off
4019 * the front.
4020 */
4021 void btrfs_truncate_item(struct btrfs_trans_handle *trans,
4022 struct btrfs_path *path, u32 new_size, int from_end)
4023 {
4024 int slot;
4025 struct extent_buffer *leaf;
4026 u32 nritems;
4027 unsigned int data_end;
4028 unsigned int old_data_start;
4029 unsigned int old_size;
4030 unsigned int size_diff;
4031 int i;
4032 struct btrfs_map_token token;
4033
4034 leaf = path->nodes[0];
4035 slot = path->slots[0];
4036
4037 old_size = btrfs_item_size(leaf, slot);
4038 if (old_size == new_size)
4039 return;
4040
4041 nritems = btrfs_header_nritems(leaf);
4042 data_end = leaf_data_end(leaf);
4043
4044 old_data_start = btrfs_item_offset(leaf, slot);
4045
4046 size_diff = old_size - new_size;
4047
4048 BUG_ON(slot < 0);
4049 BUG_ON(slot >= nritems);
4050
4051 /*
4052 * item0..itemN ... dataN.offset..dataN.size .. data0.size
4053 */
4054 /* first correct the data pointers */
4055 btrfs_init_map_token(&token, leaf);
4056 for (i = slot; i < nritems; i++) {
4057 u32 ioff;
4058
4059 ioff = btrfs_token_item_offset(&token, i);
4060 btrfs_set_token_item_offset(&token, i, ioff + size_diff);
4061 }
4062
4063 /* shift the data */
4064 if (from_end) {
4065 memmove_leaf_data(leaf, data_end + size_diff, data_end,
4066 old_data_start + new_size - data_end);
4067 } else {
4068 struct btrfs_disk_key disk_key;
4069 u64 offset;
4070
4071 btrfs_item_key(leaf, &disk_key, slot);
4072
4073 if (btrfs_disk_key_type(&disk_key) == BTRFS_EXTENT_DATA_KEY) {
4074 unsigned long ptr;
4075 struct btrfs_file_extent_item *fi;
4076
4077 fi = btrfs_item_ptr(leaf, slot,
4078 struct btrfs_file_extent_item);
4079 fi = (struct btrfs_file_extent_item *)(
4080 (unsigned long)fi - size_diff);
4081
4082 if (btrfs_file_extent_type(leaf, fi) ==
4083 BTRFS_FILE_EXTENT_INLINE) {
4084 ptr = btrfs_item_ptr_offset(leaf, slot);
4085 memmove_extent_buffer(leaf, ptr,
4086 (unsigned long)fi,
4087 BTRFS_FILE_EXTENT_INLINE_DATA_START);
4088 }
4089 }
4090
4091 memmove_leaf_data(leaf, data_end + size_diff, data_end,
4092 old_data_start - data_end);
4093
4094 offset = btrfs_disk_key_offset(&disk_key);
4095 btrfs_set_disk_key_offset(&disk_key, offset + size_diff);
4096 btrfs_set_item_key(leaf, &disk_key, slot);
4097 if (slot == 0)
4098 fixup_low_keys(trans, path, &disk_key, 1);
4099 }
4100
4101 btrfs_set_item_size(leaf, slot, new_size);
4102 btrfs_mark_buffer_dirty(trans, leaf);
4103
4104 if (btrfs_leaf_free_space(leaf) < 0) {
4105 btrfs_print_leaf(leaf);
4106 BUG();
4107 }
4108 }
4109
4110 /*
4111 * make the item pointed to by the path bigger, data_size is the added size.
4112 */
4113 void btrfs_extend_item(struct btrfs_trans_handle *trans,
4114 struct btrfs_path *path, u32 data_size)
4115 {
4116 int slot;
4117 struct extent_buffer *leaf;
4118 u32 nritems;
4119 unsigned int data_end;
4120 unsigned int old_data;
4121 unsigned int old_size;
4122 int i;
4123 struct btrfs_map_token token;
4124
4125 leaf = path->nodes[0];
4126
4127 nritems = btrfs_header_nritems(leaf);
4128 data_end = leaf_data_end(leaf);
4129
4130 if (btrfs_leaf_free_space(leaf) < data_size) {
4131 btrfs_print_leaf(leaf);
4132 BUG();
4133 }
4134 slot = path->slots[0];
4135 old_data = btrfs_item_data_end(leaf, slot);
4136
4137 BUG_ON(slot < 0);
4138 if (slot >= nritems) {
4139 btrfs_print_leaf(leaf);
4140 btrfs_crit(leaf->fs_info, "slot %d too large, nritems %d",
4141 slot, nritems);
4142 BUG();
4143 }
4144
4145 /*
4146 * item0..itemN ... dataN.offset..dataN.size .. data0.size
4147 */
4148 /* first correct the data pointers */
4149 btrfs_init_map_token(&token, leaf);
4150 for (i = slot; i < nritems; i++) {
4151 u32 ioff;
4152
4153 ioff = btrfs_token_item_offset(&token, i);
4154 btrfs_set_token_item_offset(&token, i, ioff - data_size);
4155 }
4156
4157 /* shift the data */
4158 memmove_leaf_data(leaf, data_end - data_size, data_end,
4159 old_data - data_end);
4160
4161 data_end = old_data;
4162 old_size = btrfs_item_size(leaf, slot);
4163 btrfs_set_item_size(leaf, slot, old_size + data_size);
4164 btrfs_mark_buffer_dirty(trans, leaf);
4165
4166 if (btrfs_leaf_free_space(leaf) < 0) {
4167 btrfs_print_leaf(leaf);
4168 BUG();
4169 }
4170 }
4171
4172 /*
4173 * Make space in the node before inserting one or more items.
4174 *
4175 * @trans: transaction handle
4176 * @root: root we are inserting items to
4177 * @path: points to the leaf/slot where we are going to insert new items
4178 * @batch: information about the batch of items to insert
4179 *
4180 * Main purpose is to save stack depth by doing the bulk of the work in a
4181 * function that doesn't call btrfs_search_slot
4182 */
4183 static void setup_items_for_insert(struct btrfs_trans_handle *trans,
4184 struct btrfs_root *root, struct btrfs_path *path,
4185 const struct btrfs_item_batch *batch)
4186 {
4187 struct btrfs_fs_info *fs_info = root->fs_info;
4188 int i;
4189 u32 nritems;
4190 unsigned int data_end;
4191 struct btrfs_disk_key disk_key;
4192 struct extent_buffer *leaf;
4193 int slot;
4194 struct btrfs_map_token token;
4195 u32 total_size;
4196
4197 /*
4198 * Before anything else, update keys in the parent and other ancestors
4199 * if needed, then release the write locks on them, so that other tasks
4200 * can use them while we modify the leaf.
4201 */
4202 if (path->slots[0] == 0) {
4203 btrfs_cpu_key_to_disk(&disk_key, &batch->keys[0]);
4204 fixup_low_keys(trans, path, &disk_key, 1);
4205 }
4206 btrfs_unlock_up_safe(path, 1);
4207
4208 leaf = path->nodes[0];
4209 slot = path->slots[0];
4210
4211 nritems = btrfs_header_nritems(leaf);
4212 data_end = leaf_data_end(leaf);
4213 total_size = batch->total_data_size + (batch->nr * sizeof(struct btrfs_item));
4214
4215 if (btrfs_leaf_free_space(leaf) < total_size) {
4216 btrfs_print_leaf(leaf);
4217 btrfs_crit(fs_info, "not enough freespace need %u have %d",
4218 total_size, btrfs_leaf_free_space(leaf));
4219 BUG();
4220 }
4221
4222 btrfs_init_map_token(&token, leaf);
4223 if (slot != nritems) {
4224 unsigned int old_data = btrfs_item_data_end(leaf, slot);
4225
4226 if (old_data < data_end) {
4227 btrfs_print_leaf(leaf);
4228 btrfs_crit(fs_info,
4229 "item at slot %d with data offset %u beyond data end of leaf %u",
4230 slot, old_data, data_end);
4231 BUG();
4232 }
4233 /*
4234 * item0..itemN ... dataN.offset..dataN.size .. data0.size
4235 */
4236 /* first correct the data pointers */
4237 for (i = slot; i < nritems; i++) {
4238 u32 ioff;
4239
4240 ioff = btrfs_token_item_offset(&token, i);
4241 btrfs_set_token_item_offset(&token, i,
4242 ioff - batch->total_data_size);
4243 }
4244 /* shift the items */
4245 memmove_leaf_items(leaf, slot + batch->nr, slot, nritems - slot);
4246
4247 /* shift the data */
4248 memmove_leaf_data(leaf, data_end - batch->total_data_size,
4249 data_end, old_data - data_end);
4250 data_end = old_data;
4251 }
4252
4253 /* setup the item for the new data */
4254 for (i = 0; i < batch->nr; i++) {
4255 btrfs_cpu_key_to_disk(&disk_key, &batch->keys[i]);
4256 btrfs_set_item_key(leaf, &disk_key, slot + i);
4257 data_end -= batch->data_sizes[i];
4258 btrfs_set_token_item_offset(&token, slot + i, data_end);
4259 btrfs_set_token_item_size(&token, slot + i, batch->data_sizes[i]);
4260 }
4261
4262 btrfs_set_header_nritems(leaf, nritems + batch->nr);
4263 btrfs_mark_buffer_dirty(trans, leaf);
4264
4265 if (btrfs_leaf_free_space(leaf) < 0) {
4266 btrfs_print_leaf(leaf);
4267 BUG();
4268 }
4269 }
4270
4271 /*
4272 * Insert a new item into a leaf.
4273 *
4274 * @trans: Transaction handle.
4275 * @root: The root of the btree.
4276 * @path: A path pointing to the target leaf and slot.
4277 * @key: The key of the new item.
4278 * @data_size: The size of the data associated with the new key.
4279 */
4280 void btrfs_setup_item_for_insert(struct btrfs_trans_handle *trans,
4281 struct btrfs_root *root,
4282 struct btrfs_path *path,
4283 const struct btrfs_key *key,
4284 u32 data_size)
4285 {
4286 struct btrfs_item_batch batch;
4287
4288 batch.keys = key;
4289 batch.data_sizes = &data_size;
4290 batch.total_data_size = data_size;
4291 batch.nr = 1;
4292
4293 setup_items_for_insert(trans, root, path, &batch);
4294 }
4295
4296 /*
4297 * Given a key and some data, insert items into the tree.
4298 * This does all the path init required, making room in the tree if needed.
4299 *
4300 * Returns: 0 on success
4301 * -EEXIST if the first key already exists
4302 * < 0 on other errors
4303 */
4304 int btrfs_insert_empty_items(struct btrfs_trans_handle *trans,
4305 struct btrfs_root *root,
4306 struct btrfs_path *path,
4307 const struct btrfs_item_batch *batch)
4308 {
4309 int ret = 0;
4310 int slot;
4311 u32 total_size;
4312
4313 total_size = batch->total_data_size + (batch->nr * sizeof(struct btrfs_item));
4314 ret = btrfs_search_slot(trans, root, &batch->keys[0], path, total_size, 1);
4315 if (ret == 0)
4316 return -EEXIST;
4317 if (ret < 0)
4318 return ret;
4319
4320 slot = path->slots[0];
4321 BUG_ON(slot < 0);
4322
4323 setup_items_for_insert(trans, root, path, batch);
4324 return 0;
4325 }
4326
4327 /*
4328 * Given a key and some data, insert an item into the tree.
4329 * This does all the path init required, making room in the tree if needed.
4330 */
4331 int btrfs_insert_item(struct btrfs_trans_handle *trans, struct btrfs_root *root,
4332 const struct btrfs_key *cpu_key, void *data,
4333 u32 data_size)
4334 {
4335 int ret = 0;
4336 struct btrfs_path *path;
4337 struct extent_buffer *leaf;
4338 unsigned long ptr;
4339
4340 path = btrfs_alloc_path();
4341 if (!path)
4342 return -ENOMEM;
4343 ret = btrfs_insert_empty_item(trans, root, path, cpu_key, data_size);
4344 if (!ret) {
4345 leaf = path->nodes[0];
4346 ptr = btrfs_item_ptr_offset(leaf, path->slots[0]);
4347 write_extent_buffer(leaf, data, ptr, data_size);
4348 btrfs_mark_buffer_dirty(trans, leaf);
4349 }
4350 btrfs_free_path(path);
4351 return ret;
4352 }
4353
4354 /*
4355 * This function duplicates an item, giving 'new_key' to the new item.
4356 * It guarantees both items live in the same tree leaf and the new item is
4357 * contiguous with the original item.
4358 *
4359 * This allows us to split a file extent in place, keeping a lock on the leaf
4360 * the entire time.
4361 */
4362 int btrfs_duplicate_item(struct btrfs_trans_handle *trans,
4363 struct btrfs_root *root,
4364 struct btrfs_path *path,
4365 const struct btrfs_key *new_key)
4366 {
4367 struct extent_buffer *leaf;
4368 int ret;
4369 u32 item_size;
4370
4371 leaf = path->nodes[0];
4372 item_size = btrfs_item_size(leaf, path->slots[0]);
4373 ret = setup_leaf_for_split(trans, root, path,
4374 item_size + sizeof(struct btrfs_item));
4375 if (ret)
4376 return ret;
4377
4378 path->slots[0]++;
4379 btrfs_setup_item_for_insert(trans, root, path, new_key, item_size);
4380 leaf = path->nodes[0];
4381 memcpy_extent_buffer(leaf,
4382 btrfs_item_ptr_offset(leaf, path->slots[0]),
4383 btrfs_item_ptr_offset(leaf, path->slots[0] - 1),
4384 item_size);
4385 return 0;
4386 }
4387
4388 /*
4389 * delete the pointer from a given node.
4390 *
4391 * the tree should have been previously balanced so the deletion does not
4392 * empty a node.
4393 *
4394 * This is exported for use inside btrfs-progs, don't un-export it.
4395 */
4396 int btrfs_del_ptr(struct btrfs_trans_handle *trans, struct btrfs_root *root,
4397 struct btrfs_path *path, int level, int slot)
4398 {
4399 struct extent_buffer *parent = path->nodes[level];
4400 u32 nritems;
4401 int ret;
4402
4403 nritems = btrfs_header_nritems(parent);
4404 if (slot != nritems - 1) {
4405 if (level) {
4406 ret = btrfs_tree_mod_log_insert_move(parent, slot,
4407 slot + 1, nritems - slot - 1);
4408 if (ret < 0) {
4409 btrfs_abort_transaction(trans, ret);
4410 return ret;
4411 }
4412 }
4413 memmove_extent_buffer(parent,
4414 btrfs_node_key_ptr_offset(parent, slot),
4415 btrfs_node_key_ptr_offset(parent, slot + 1),
4416 sizeof(struct btrfs_key_ptr) *
4417 (nritems - slot - 1));
4418 } else if (level) {
4419 ret = btrfs_tree_mod_log_insert_key(parent, slot,
4420 BTRFS_MOD_LOG_KEY_REMOVE);
4421 if (ret < 0) {
4422 btrfs_abort_transaction(trans, ret);
4423 return ret;
4424 }
4425 }
4426
4427 nritems--;
4428 btrfs_set_header_nritems(parent, nritems);
4429 if (nritems == 0 && parent == root->node) {
4430 BUG_ON(btrfs_header_level(root->node) != 1);
4431 /* just turn the root into a leaf and break */
4432 btrfs_set_header_level(root->node, 0);
4433 } else if (slot == 0) {
4434 struct btrfs_disk_key disk_key;
4435
4436 btrfs_node_key(parent, &disk_key, 0);
4437 fixup_low_keys(trans, path, &disk_key, level + 1);
4438 }
4439 btrfs_mark_buffer_dirty(trans, parent);
4440 return 0;
4441 }
4442
4443 /*
4444 * a helper function to delete the leaf pointed to by path->slots[1] and
4445 * path->nodes[1].
4446 *
4447 * This deletes the pointer in path->nodes[1] and frees the leaf
4448 * block extent. zero is returned if it all worked out, < 0 otherwise.
4449 *
4450 * The path must have already been setup for deleting the leaf, including
4451 * all the proper balancing. path->nodes[1] must be locked.
4452 */
4453 static noinline int btrfs_del_leaf(struct btrfs_trans_handle *trans,
4454 struct btrfs_root *root,
4455 struct btrfs_path *path,
4456 struct extent_buffer *leaf)
4457 {
4458 int ret;
4459
4460 WARN_ON(btrfs_header_generation(leaf) != trans->transid);
4461 ret = btrfs_del_ptr(trans, root, path, 1, path->slots[1]);
4462 if (ret < 0)
4463 return ret;
4464
4465 /*
4466 * btrfs_free_extent is expensive, we want to make sure we
4467 * aren't holding any locks when we call it
4468 */
4469 btrfs_unlock_up_safe(path, 0);
4470
4471 root_sub_used_bytes(root);
4472
4473 atomic_inc(&leaf->refs);
4474 ret = btrfs_free_tree_block(trans, btrfs_root_id(root), leaf, 0, 1);
4475 free_extent_buffer_stale(leaf);
4476 if (ret < 0)
4477 btrfs_abort_transaction(trans, ret);
4478
4479 return ret;
4480 }
4481 /*
4482 * delete the item at the leaf level in path. If that empties
4483 * the leaf, remove it from the tree
4484 */
4485 int btrfs_del_items(struct btrfs_trans_handle *trans, struct btrfs_root *root,
4486 struct btrfs_path *path, int slot, int nr)
4487 {
4488 struct btrfs_fs_info *fs_info = root->fs_info;
4489 struct extent_buffer *leaf;
4490 int ret = 0;
4491 int wret;
4492 u32 nritems;
4493
4494 leaf = path->nodes[0];
4495 nritems = btrfs_header_nritems(leaf);
4496
4497 if (slot + nr != nritems) {
4498 const u32 last_off = btrfs_item_offset(leaf, slot + nr - 1);
4499 const int data_end = leaf_data_end(leaf);
4500 struct btrfs_map_token token;
4501 u32 dsize = 0;
4502 int i;
4503
4504 for (i = 0; i < nr; i++)
4505 dsize += btrfs_item_size(leaf, slot + i);
4506
4507 memmove_leaf_data(leaf, data_end + dsize, data_end,
4508 last_off - data_end);
4509
4510 btrfs_init_map_token(&token, leaf);
4511 for (i = slot + nr; i < nritems; i++) {
4512 u32 ioff;
4513
4514 ioff = btrfs_token_item_offset(&token, i);
4515 btrfs_set_token_item_offset(&token, i, ioff + dsize);
4516 }
4517
4518 memmove_leaf_items(leaf, slot, slot + nr, nritems - slot - nr);
4519 }
4520 btrfs_set_header_nritems(leaf, nritems - nr);
4521 nritems -= nr;
4522
4523 /* delete the leaf if we've emptied it */
4524 if (nritems == 0) {
4525 if (leaf == root->node) {
4526 btrfs_set_header_level(leaf, 0);
4527 } else {
4528 btrfs_clear_buffer_dirty(trans, leaf);
4529 ret = btrfs_del_leaf(trans, root, path, leaf);
4530 if (ret < 0)
4531 return ret;
4532 }
4533 } else {
4534 int used = leaf_space_used(leaf, 0, nritems);
4535 if (slot == 0) {
4536 struct btrfs_disk_key disk_key;
4537
4538 btrfs_item_key(leaf, &disk_key, 0);
4539 fixup_low_keys(trans, path, &disk_key, 1);
4540 }
4541
4542 /*
4543 * Try to delete the leaf if it is mostly empty. We do this by
4544 * trying to move all its items into its left and right neighbours.
4545 * If we can't move all the items, then we don't delete it - it's
4546 * not ideal, but future insertions might fill the leaf with more
4547 * items, or items from other leaves might be moved later into our
4548 * leaf due to deletions on those leaves.
4549 */
4550 if (used < BTRFS_LEAF_DATA_SIZE(fs_info) / 3) {
4551 u32 min_push_space;
4552
4553 /* push_leaf_left fixes the path.
4554 * make sure the path still points to our leaf
4555 * for possible call to btrfs_del_ptr below
4556 */
4557 slot = path->slots[1];
4558 atomic_inc(&leaf->refs);
4559 /*
4560 * We want to be able to at least push one item to the
4561 * left neighbour leaf, and that's the first item.
4562 */
4563 min_push_space = sizeof(struct btrfs_item) +
4564 btrfs_item_size(leaf, 0);
4565 wret = push_leaf_left(trans, root, path, 0,
4566 min_push_space, 1, (u32)-1);
4567 if (wret < 0 && wret != -ENOSPC)
4568 ret = wret;
4569
4570 if (path->nodes[0] == leaf &&
4571 btrfs_header_nritems(leaf)) {
4572 /*
4573 * If we were not able to push all items from our
4574 * leaf to its left neighbour, then attempt to
4575 * either push all the remaining items to the
4576 * right neighbour or none. There's no advantage
4577 * in pushing only some items, instead of all, as
4578 * it's pointless to end up with a leaf having
4579 * too few items while the neighbours can be full
4580 * or nearly full.
4581 */
4582 nritems = btrfs_header_nritems(leaf);
4583 min_push_space = leaf_space_used(leaf, 0, nritems);
4584 wret = push_leaf_right(trans, root, path, 0,
4585 min_push_space, 1, 0);
4586 if (wret < 0 && wret != -ENOSPC)
4587 ret = wret;
4588 }
4589
4590 if (btrfs_header_nritems(leaf) == 0) {
4591 path->slots[1] = slot;
4592 ret = btrfs_del_leaf(trans, root, path, leaf);
4593 if (ret < 0)
4594 return ret;
4595 free_extent_buffer(leaf);
4596 ret = 0;
4597 } else {
4598 /* if we're still in the path, make sure
4599 * we're dirty. Otherwise, one of the
4600 * push_leaf functions must have already
4601 * dirtied this buffer
4602 */
4603 if (path->nodes[0] == leaf)
4604 btrfs_mark_buffer_dirty(trans, leaf);
4605 free_extent_buffer(leaf);
4606 }
4607 } else {
4608 btrfs_mark_buffer_dirty(trans, leaf);
4609 }
4610 }
4611 return ret;
4612 }
4613
4614 /*
4615 * A helper function to walk down the tree starting at min_key, and looking
4616 * for nodes or leaves that are have a minimum transaction id.
4617 * This is used by the btree defrag code, and tree logging
4618 *
4619 * This does not cow, but it does stuff the starting key it finds back
4620 * into min_key, so you can call btrfs_search_slot with cow=1 on the
4621 * key and get a writable path.
4622 *
4623 * This honors path->lowest_level to prevent descent past a given level
4624 * of the tree.
4625 *
4626 * min_trans indicates the oldest transaction that you are interested
4627 * in walking through. Any nodes or leaves older than min_trans are
4628 * skipped over (without reading them).
4629 *
4630 * returns zero if something useful was found, < 0 on error and 1 if there
4631 * was nothing in the tree that matched the search criteria.
4632 */
4633 int btrfs_search_forward(struct btrfs_root *root, struct btrfs_key *min_key,
4634 struct btrfs_path *path,
4635 u64 min_trans)
4636 {
4637 struct extent_buffer *cur;
4638 struct btrfs_key found_key;
4639 int slot;
4640 int sret;
4641 u32 nritems;
4642 int level;
4643 int ret = 1;
4644 int keep_locks = path->keep_locks;
4645
4646 ASSERT(!path->nowait);
4647 path->keep_locks = 1;
4648 again:
4649 cur = btrfs_read_lock_root_node(root);
4650 level = btrfs_header_level(cur);
4651 WARN_ON(path->nodes[level]);
4652 path->nodes[level] = cur;
4653 path->locks[level] = BTRFS_READ_LOCK;
4654
4655 if (btrfs_header_generation(cur) < min_trans) {
4656 ret = 1;
4657 goto out;
4658 }
4659 while (1) {
4660 nritems = btrfs_header_nritems(cur);
4661 level = btrfs_header_level(cur);
4662 sret = btrfs_bin_search(cur, 0, min_key, &slot);
4663 if (sret < 0) {
4664 ret = sret;
4665 goto out;
4666 }
4667
4668 /* at the lowest level, we're done, setup the path and exit */
4669 if (level == path->lowest_level) {
4670 if (slot >= nritems)
4671 goto find_next_key;
4672 ret = 0;
4673 path->slots[level] = slot;
4674 btrfs_item_key_to_cpu(cur, &found_key, slot);
4675 goto out;
4676 }
4677 if (sret && slot > 0)
4678 slot--;
4679 /*
4680 * check this node pointer against the min_trans parameters.
4681 * If it is too old, skip to the next one.
4682 */
4683 while (slot < nritems) {
4684 u64 gen;
4685
4686 gen = btrfs_node_ptr_generation(cur, slot);
4687 if (gen < min_trans) {
4688 slot++;
4689 continue;
4690 }
4691 break;
4692 }
4693 find_next_key:
4694 /*
4695 * we didn't find a candidate key in this node, walk forward
4696 * and find another one
4697 */
4698 if (slot >= nritems) {
4699 path->slots[level] = slot;
4700 sret = btrfs_find_next_key(root, path, min_key, level,
4701 min_trans);
4702 if (sret == 0) {
4703 btrfs_release_path(path);
4704 goto again;
4705 } else {
4706 goto out;
4707 }
4708 }
4709 /* save our key for returning back */
4710 btrfs_node_key_to_cpu(cur, &found_key, slot);
4711 path->slots[level] = slot;
4712 if (level == path->lowest_level) {
4713 ret = 0;
4714 goto out;
4715 }
4716 cur = btrfs_read_node_slot(cur, slot);
4717 if (IS_ERR(cur)) {
4718 ret = PTR_ERR(cur);
4719 goto out;
4720 }
4721
4722 btrfs_tree_read_lock(cur);
4723
4724 path->locks[level - 1] = BTRFS_READ_LOCK;
4725 path->nodes[level - 1] = cur;
4726 unlock_up(path, level, 1, 0, NULL);
4727 }
4728 out:
4729 path->keep_locks = keep_locks;
4730 if (ret == 0) {
4731 btrfs_unlock_up_safe(path, path->lowest_level + 1);
4732 memcpy(min_key, &found_key, sizeof(found_key));
4733 }
4734 return ret;
4735 }
4736
4737 /*
4738 * this is similar to btrfs_next_leaf, but does not try to preserve
4739 * and fixup the path. It looks for and returns the next key in the
4740 * tree based on the current path and the min_trans parameters.
4741 *
4742 * 0 is returned if another key is found, < 0 if there are any errors
4743 * and 1 is returned if there are no higher keys in the tree
4744 *
4745 * path->keep_locks should be set to 1 on the search made before
4746 * calling this function.
4747 */
4748 int btrfs_find_next_key(struct btrfs_root *root, struct btrfs_path *path,
4749 struct btrfs_key *key, int level, u64 min_trans)
4750 {
4751 int slot;
4752 struct extent_buffer *c;
4753
4754 WARN_ON(!path->keep_locks && !path->skip_locking);
4755 while (level < BTRFS_MAX_LEVEL) {
4756 if (!path->nodes[level])
4757 return 1;
4758
4759 slot = path->slots[level] + 1;
4760 c = path->nodes[level];
4761 next:
4762 if (slot >= btrfs_header_nritems(c)) {
4763 int ret;
4764 int orig_lowest;
4765 struct btrfs_key cur_key;
4766 if (level + 1 >= BTRFS_MAX_LEVEL ||
4767 !path->nodes[level + 1])
4768 return 1;
4769
4770 if (path->locks[level + 1] || path->skip_locking) {
4771 level++;
4772 continue;
4773 }
4774
4775 slot = btrfs_header_nritems(c) - 1;
4776 if (level == 0)
4777 btrfs_item_key_to_cpu(c, &cur_key, slot);
4778 else
4779 btrfs_node_key_to_cpu(c, &cur_key, slot);
4780
4781 orig_lowest = path->lowest_level;
4782 btrfs_release_path(path);
4783 path->lowest_level = level;
4784 ret = btrfs_search_slot(NULL, root, &cur_key, path,
4785 0, 0);
4786 path->lowest_level = orig_lowest;
4787 if (ret < 0)
4788 return ret;
4789
4790 c = path->nodes[level];
4791 slot = path->slots[level];
4792 if (ret == 0)
4793 slot++;
4794 goto next;
4795 }
4796
4797 if (level == 0)
4798 btrfs_item_key_to_cpu(c, key, slot);
4799 else {
4800 u64 gen = btrfs_node_ptr_generation(c, slot);
4801
4802 if (gen < min_trans) {
4803 slot++;
4804 goto next;
4805 }
4806 btrfs_node_key_to_cpu(c, key, slot);
4807 }
4808 return 0;
4809 }
4810 return 1;
4811 }
4812
4813 int btrfs_next_old_leaf(struct btrfs_root *root, struct btrfs_path *path,
4814 u64 time_seq)
4815 {
4816 int slot;
4817 int level;
4818 struct extent_buffer *c;
4819 struct extent_buffer *next;
4820 struct btrfs_fs_info *fs_info = root->fs_info;
4821 struct btrfs_key key;
4822 bool need_commit_sem = false;
4823 u32 nritems;
4824 int ret;
4825 int i;
4826
4827 /*
4828 * The nowait semantics are used only for write paths, where we don't
4829 * use the tree mod log and sequence numbers.
4830 */
4831 if (time_seq)
4832 ASSERT(!path->nowait);
4833
4834 nritems = btrfs_header_nritems(path->nodes[0]);
4835 if (nritems == 0)
4836 return 1;
4837
4838 btrfs_item_key_to_cpu(path->nodes[0], &key, nritems - 1);
4839 again:
4840 level = 1;
4841 next = NULL;
4842 btrfs_release_path(path);
4843
4844 path->keep_locks = 1;
4845
4846 if (time_seq) {
4847 ret = btrfs_search_old_slot(root, &key, path, time_seq);
4848 } else {
4849 if (path->need_commit_sem) {
4850 path->need_commit_sem = 0;
4851 need_commit_sem = true;
4852 if (path->nowait) {
4853 if (!down_read_trylock(&fs_info->commit_root_sem)) {
4854 ret = -EAGAIN;
4855 goto done;
4856 }
4857 } else {
4858 down_read(&fs_info->commit_root_sem);
4859 }
4860 }
4861 ret = btrfs_search_slot(NULL, root, &key, path, 0, 0);
4862 }
4863 path->keep_locks = 0;
4864
4865 if (ret < 0)
4866 goto done;
4867
4868 nritems = btrfs_header_nritems(path->nodes[0]);
4869 /*
4870 * by releasing the path above we dropped all our locks. A balance
4871 * could have added more items next to the key that used to be
4872 * at the very end of the block. So, check again here and
4873 * advance the path if there are now more items available.
4874 */
4875 if (nritems > 0 && path->slots[0] < nritems - 1) {
4876 if (ret == 0)
4877 path->slots[0]++;
4878 ret = 0;
4879 goto done;
4880 }
4881 /*
4882 * So the above check misses one case:
4883 * - after releasing the path above, someone has removed the item that
4884 * used to be at the very end of the block, and balance between leafs
4885 * gets another one with bigger key.offset to replace it.
4886 *
4887 * This one should be returned as well, or we can get leaf corruption
4888 * later(esp. in __btrfs_drop_extents()).
4889 *
4890 * And a bit more explanation about this check,
4891 * with ret > 0, the key isn't found, the path points to the slot
4892 * where it should be inserted, so the path->slots[0] item must be the
4893 * bigger one.
4894 */
4895 if (nritems > 0 && ret > 0 && path->slots[0] == nritems - 1) {
4896 ret = 0;
4897 goto done;
4898 }
4899
4900 while (level < BTRFS_MAX_LEVEL) {
4901 if (!path->nodes[level]) {
4902 ret = 1;
4903 goto done;
4904 }
4905
4906 slot = path->slots[level] + 1;
4907 c = path->nodes[level];
4908 if (slot >= btrfs_header_nritems(c)) {
4909 level++;
4910 if (level == BTRFS_MAX_LEVEL) {
4911 ret = 1;
4912 goto done;
4913 }
4914 continue;
4915 }
4916
4917
4918 /*
4919 * Our current level is where we're going to start from, and to
4920 * make sure lockdep doesn't complain we need to drop our locks
4921 * and nodes from 0 to our current level.
4922 */
4923 for (i = 0; i < level; i++) {
4924 if (path->locks[level]) {
4925 btrfs_tree_read_unlock(path->nodes[i]);
4926 path->locks[i] = 0;
4927 }
4928 free_extent_buffer(path->nodes[i]);
4929 path->nodes[i] = NULL;
4930 }
4931
4932 next = c;
4933 ret = read_block_for_search(root, path, &next, level,
4934 slot, &key);
4935 if (ret == -EAGAIN && !path->nowait)
4936 goto again;
4937
4938 if (ret < 0) {
4939 btrfs_release_path(path);
4940 goto done;
4941 }
4942
4943 if (!path->skip_locking) {
4944 ret = btrfs_try_tree_read_lock(next);
4945 if (!ret && path->nowait) {
4946 ret = -EAGAIN;
4947 goto done;
4948 }
4949 if (!ret && time_seq) {
4950 /*
4951 * If we don't get the lock, we may be racing
4952 * with push_leaf_left, holding that lock while
4953 * itself waiting for the leaf we've currently
4954 * locked. To solve this situation, we give up
4955 * on our lock and cycle.
4956 */
4957 free_extent_buffer(next);
4958 btrfs_release_path(path);
4959 cond_resched();
4960 goto again;
4961 }
4962 if (!ret)
4963 btrfs_tree_read_lock(next);
4964 }
4965 break;
4966 }
4967 path->slots[level] = slot;
4968 while (1) {
4969 level--;
4970 path->nodes[level] = next;
4971 path->slots[level] = 0;
4972 if (!path->skip_locking)
4973 path->locks[level] = BTRFS_READ_LOCK;
4974 if (!level)
4975 break;
4976
4977 ret = read_block_for_search(root, path, &next, level,
4978 0, &key);
4979 if (ret == -EAGAIN && !path->nowait)
4980 goto again;
4981
4982 if (ret < 0) {
4983 btrfs_release_path(path);
4984 goto done;
4985 }
4986
4987 if (!path->skip_locking) {
4988 if (path->nowait) {
4989 if (!btrfs_try_tree_read_lock(next)) {
4990 ret = -EAGAIN;
4991 goto done;
4992 }
4993 } else {
4994 btrfs_tree_read_lock(next);
4995 }
4996 }
4997 }
4998 ret = 0;
4999 done:
5000 unlock_up(path, 0, 1, 0, NULL);
5001 if (need_commit_sem) {
5002 int ret2;
5003
5004 path->need_commit_sem = 1;
5005 ret2 = finish_need_commit_sem_search(path);
5006 up_read(&fs_info->commit_root_sem);
5007 if (ret2)
5008 ret = ret2;
5009 }
5010
5011 return ret;
5012 }
5013
5014 int btrfs_next_old_item(struct btrfs_root *root, struct btrfs_path *path, u64 time_seq)
5015 {
5016 path->slots[0]++;
5017 if (path->slots[0] >= btrfs_header_nritems(path->nodes[0]))
5018 return btrfs_next_old_leaf(root, path, time_seq);
5019 return 0;
5020 }
5021
5022 /*
5023 * this uses btrfs_prev_leaf to walk backwards in the tree, and keeps
5024 * searching until it gets past min_objectid or finds an item of 'type'
5025 *
5026 * returns 0 if something is found, 1 if nothing was found and < 0 on error
5027 */
5028 int btrfs_previous_item(struct btrfs_root *root,
5029 struct btrfs_path *path, u64 min_objectid,
5030 int type)
5031 {
5032 struct btrfs_key found_key;
5033 struct extent_buffer *leaf;
5034 u32 nritems;
5035 int ret;
5036
5037 while (1) {
5038 if (path->slots[0] == 0) {
5039 ret = btrfs_prev_leaf(root, path);
5040 if (ret != 0)
5041 return ret;
5042 } else {
5043 path->slots[0]--;
5044 }
5045 leaf = path->nodes[0];
5046 nritems = btrfs_header_nritems(leaf);
5047 if (nritems == 0)
5048 return 1;
5049 if (path->slots[0] == nritems)
5050 path->slots[0]--;
5051
5052 btrfs_item_key_to_cpu(leaf, &found_key, path->slots[0]);
5053 if (found_key.objectid < min_objectid)
5054 break;
5055 if (found_key.type == type)
5056 return 0;
5057 if (found_key.objectid == min_objectid &&
5058 found_key.type < type)
5059 break;
5060 }
5061 return 1;
5062 }
5063
5064 /*
5065 * search in extent tree to find a previous Metadata/Data extent item with
5066 * min objecitd.
5067 *
5068 * returns 0 if something is found, 1 if nothing was found and < 0 on error
5069 */
5070 int btrfs_previous_extent_item(struct btrfs_root *root,
5071 struct btrfs_path *path, u64 min_objectid)
5072 {
5073 struct btrfs_key found_key;
5074 struct extent_buffer *leaf;
5075 u32 nritems;
5076 int ret;
5077
5078 while (1) {
5079 if (path->slots[0] == 0) {
5080 ret = btrfs_prev_leaf(root, path);
5081 if (ret != 0)
5082 return ret;
5083 } else {
5084 path->slots[0]--;
5085 }
5086 leaf = path->nodes[0];
5087 nritems = btrfs_header_nritems(leaf);
5088 if (nritems == 0)
5089 return 1;
5090 if (path->slots[0] == nritems)
5091 path->slots[0]--;
5092
5093 btrfs_item_key_to_cpu(leaf, &found_key, path->slots[0]);
5094 if (found_key.objectid < min_objectid)
5095 break;
5096 if (found_key.type == BTRFS_EXTENT_ITEM_KEY ||
5097 found_key.type == BTRFS_METADATA_ITEM_KEY)
5098 return 0;
5099 if (found_key.objectid == min_objectid &&
5100 found_key.type < BTRFS_EXTENT_ITEM_KEY)
5101 break;
5102 }
5103 return 1;
5104 }
5105
5106 int __init btrfs_ctree_init(void)
5107 {
5108 btrfs_path_cachep = KMEM_CACHE(btrfs_path, 0);
5109 if (!btrfs_path_cachep)
5110 return -ENOMEM;
5111 return 0;
5112 }
5113
5114 void __cold btrfs_ctree_exit(void)
5115 {
5116 kmem_cache_destroy(btrfs_path_cachep);
5117 }
5118
Linux® is a registered trademark of Linus Torvalds in the United States and other countries.
TOMOYO® is a registered trademark of NTT DATA CORPORATION.