| blob | 5df76c17775ad4650c6deb71617f9e2e5b75f2b1 |
1 // SPDX-License-Identifier: GPL-2.0
2 /*
3 * Copyright (C) 2007,2008 Oracle. All rights reserved.
4 */
6 #include <linux/sched.h>
7 #include <linux/slab.h>
8 #include <linux/rbtree.h>
9 #include <linux/mm.h>
33 {
35 }
37 /*
38 * set all locked nodes in the path to blocking locks. This should
39 * be done before scheduling
40 */
42 {
47 /*
48 * If we currently have a spinning reader or writer lock this
49 * will bump the count of blocking holders and drop the
50 * spinlock.
51 */
58 }
59 }
60 }
62 /* this also releases the path */
64 {
69 }
71 /*
72 * path release drops references on the extent buffers in the path
73 * and it drops any locks held by this path
74 *
75 * It is safe to call this on paths that no locks or extent buffers held.
76 */
78 {
88 }
91 }
92 }
94 /*
95 * safely gets a reference on the root node of a tree. A lock
96 * is not taken, so a concurrent writer may put a different node
97 * at the root of the tree. See btrfs_lock_root_node for the
98 * looping required.
99 *
100 * The extent buffer returned by this has a reference taken, so
101 * it won't disappear. It may stop being the root of the tree
102 * at any time because there are no locks held.
103 */
105 {
112 /*
113 * RCU really hurts here, we could free up the root node because
114 * it was COWed but we may not get the new root node yet so do
115 * the inc_not_zero dance and if it doesn't work then
116 * synchronize_rcu and try again.
117 */
121 }
124 }
126 }
128 /* loop around taking references on and locking the root node of the
129 * tree until you end up with a lock on the root. A locked buffer
130 * is returned, with a reference held.
131 */
133 {
143 }
145 }
147 /* loop around taking references on and locking the root node of the
148 * tree until you end up with a lock on the root. A locked buffer
149 * is returned, with a reference held.
150 */
152 {
162 }
164 }
166 /* cowonly root (everything not a reference counted cow subvolume), just get
167 * put onto a simple dirty list. transaction.c walks this to make sure they
168 * get properly updated on disk.
169 */
171 {
180 /* Want the extent tree to be the last on the list */
184 else
187 }
189 }
191 /*
192 * used by snapshot creation to make a copy of a root for a tree with
193 * a given objectid. The buffer with the new root node is returned in
194 * cow_ret, and this func returns zero on success or a negative error code.
195 */
200 {
215 else
228 BTRFS_HEADER_FLAG_RELOC);
231 else
239 else
248 }
251 MOD_LOG_KEY_REPLACE,
252 MOD_LOG_KEY_ADD,
253 MOD_LOG_KEY_REMOVE,
254 MOD_LOG_KEY_REMOVE_WHILE_FREEING,
255 MOD_LOG_KEY_REMOVE_WHILE_MOVING,
256 MOD_LOG_MOVE_KEYS,
257 MOD_LOG_ROOT_REPLACE,
258 };
261 u64 logical;
262 u8 level;
263 };
267 u64 logical;
268 u64 seq;
271 /* this is used for MOD_LOG_KEY_* and MOD_LOG_MOVE_KEYS operations */
274 /* this is used for MOD_LOG_KEY* and MOD_LOG_ROOT_REPLACE */
275 u64 generation;
277 /* those are used for op == MOD_LOG_KEY_{REPLACE,REMOVE} */
279 u64 blockptr;
281 /* this is used for op == MOD_LOG_MOVE_KEYS */
287 /* this is used for op == MOD_LOG_ROOT_REPLACE */
289 };
291 /*
292 * Pull a new tree mod seq number for our operation.
293 */
295 {
297 }
299 /*
300 * This adds a new blocker to the tree mod log's blocker list if the @elem
301 * passed does not already have a sequence number set. So when a caller expects
302 * to record tree modifications, it should ensure to set elem->seq to zero
303 * before calling btrfs_get_tree_mod_seq.
304 * Returns a fresh, unused tree log modification sequence number, even if no new
305 * blocker was added.
306 */
309 {
315 }
320 }
324 {
343 /*
344 * blocker with lower sequence number exists, we
345 * cannot remove anything from the log
346 */
349 }
351 }
352 }
355 /*
356 * anything that's lower than the lowest existing (read: blocked)
357 * sequence number can be removed from the tree.
358 */
368 }
370 }
372 /*
373 * key order of the log:
374 * node/leaf start address -> sequence
375 *
376 * The 'start address' is the logical address of the *new* root node
377 * for root replace operations, or the logical address of the affected
378 * block for all other operations.
379 *
380 * Note: must be called with write lock for fs_info::tree_mod_log_lock.
381 */
384 {
405 else
407 }
412 }
414 /*
415 * Determines if logging can be omitted. Returns 1 if it can. Otherwise, it
416 * returns zero with the tree_mod_log_lock acquired. The caller must hold
417 * this until all tree mod log insertions are recorded in the rb tree and then
418 * write unlock fs_info::tree_mod_log_lock.
419 */
432 }
435 }
437 /* Similar to tree_mod_dont_log, but doesn't acquire any locks. */
440 {
448 }
453 {
464 }
471 }
475 {
489 }
497 }
501 {
519 }
533 }
534 }
540 /*
541 * When we override something during the move, we log these removals.
542 * This can only happen when we move towards the beginning of the
543 * buffer, i.e. dst_slot < src_slot.
544 */
549 }
558 free_tms:
563 }
570 }
576 {
587 }
588 }
591 }
595 {
609 GFP_NOFS);
613 }
620 }
621 }
622 }
628 }
651 free_tms:
656 }
660 }
665 {
683 /* we want the node with the highest seq */
689 /* we want the node with the smallest seq */
697 }
698 }
702 }
704 /*
705 * this returns the element from the log with the smallest time sequence
706 * value that's in the log (the oldest log item). any element with a time
707 * sequence lower than min_seq will be ignored.
708 */
711 u64 min_seq)
712 {
714 }
716 /*
717 * this returns the element from the log with the largest time sequence
718 * value that's in the log (the most recent log item). any element with
719 * a time sequence lower than min_seq will be ignored.
720 */
723 {
725 }
730 {
745 GFP_NOFS);
757 }
764 }
765 }
778 }
785 free_tms:
790 }
796 }
799 {
822 }
823 }
836 free_tms:
842 }
844 /*
845 * check if the tree block can be shared by multiple trees
846 */
849 {
850 /*
851 * Tree blocks not in reference counted trees and tree roots
852 * are never shared. If a block was allocated after the last
853 * snapshot and the block was not allocated by tree relocation,
854 * we know the block is not shared.
855 */
864 }
871 {
873 u64 refs;
874 u64 owner;
875 u64 flags;
879 /*
880 * Backrefs update rules:
881 *
882 * Always use full backrefs for extent pointers in tree block
883 * allocated by tree relocation.
884 *
885 * If a shared tree block is no longer referenced by its owner
886 * tree (btrfs_header_owner(buf) == root->root_key.objectid),
887 * use full backrefs for extent pointers in tree block.
888 *
889 * If a tree block is been relocating
890 * (root->root_key.objectid == BTRFS_TREE_RELOC_OBJECTID),
891 * use full backrefs for extent pointers in tree block.
892 * The reason for this is some operations (such as drop tree)
893 * are only allowed for blocks use full backrefs.
894 */
906 }
912 else
914 }
929 BTRFS_TREE_RELOC_OBJECTID) {
936 }
941 BTRFS_TREE_RELOC_OBJECTID)
943 else
947 }
957 }
961 BTRFS_TREE_RELOC_OBJECTID)
963 else
970 }
973 }
975 }
980 u64 parent_start,
983 u64 hint,
984 u64 empty_size)
985 {
989 /*
990 * If we are COWing a node/leaf from the extent, chunk, device or free
991 * space trees, make sure that we do not finish block group creation of
992 * pending block groups. We do this to avoid a deadlock.
993 * COWing can result in allocation of a new chunk, and flushing pending
994 * block groups (btrfs_create_pending_block_groups()) can be triggered
995 * when finishing allocation of a new chunk. Creation of a pending block
996 * group modifies the extent, chunk, device and free space trees,
997 * therefore we could deadlock with ourselves since we are holding a
998 * lock on an extent buffer that btrfs_create_pending_block_groups() may
999 * try to COW later.
1000 * For similar reasons, we also need to delay flushing pending block
1001 * groups when splitting a leaf or node, from one of those trees, since
1002 * we are holding a write lock on it and its parent or when inserting a
1003 * new root node for one of those trees.
1004 */
1017 }
1019 /*
1020 * does the dirty work in cow of a single block. The parent block (if
1021 * supplied) is updated to point to the new cow copy. The new buffer is marked
1022 * dirty and returned locked. If you modify the block it needs to be marked
1023 * dirty again.
1024 *
1025 * search_start -- an allocation hint for the new block
1026 *
1027 * empty_size -- a hint that you plan on doing more cow. This is the size in
1028 * bytes the allocator should try to find free next to the block it returns.
1029 * This is just a hint and may be ignored by the allocator.
1030 */
1037 {
1060 else
1071 /* cow is set to blocking by btrfs_init_new_buffer */
1078 BTRFS_HEADER_FLAG_RELOC);
1081 else
1090 }
1097 }
1098 }
1112 last_ref);
1129 }
1130 }
1132 last_ref);
1133 }
1140 }
1142 /*
1143 * returns the logical address of the oldest predecessor of the given root.
1144 * entries older than time_seq are ignored.
1145 */
1148 {
1157 /*
1158 * the very last operation that's logged for a root is the
1159 * replacement operation (if it is replaced at all). this has
1160 * the logical address of the *new* root, making it the very
1161 * first operation that's logged for this root.
1162 */
1165 time_seq);
1168 /*
1169 * if there are no tree operation for the oldest root, we simply
1170 * return it. this should only happen if that (old) root is at
1171 * level 0.
1172 */
1176 /*
1177 * if there's an operation that's not a root replacement, we
1178 * found the oldest version of our root. normally, we'll find a
1179 * MOD_LOG_KEY_REMOVE_WHILE_FREEING operation here.
1180 */
1187 }
1189 /* if there's no old root to return, return what we found instead */
1194 }
1196 /*
1197 * tm is a pointer to the first operation to rewind within eb. then, all
1198 * previous operations will be rewound (until we reach something older than
1199 * time_seq).
1200 */
1201 static void
1204 {
1205 u32 n;
1215 /*
1216 * all the operations are recorded with the operator used for
1217 * the modification. as we're going backwards, we do the
1218 * opposite of each operation here.
1219 */
1223 /* Fallthrough */
1230 n++;
1240 /* if a move operation is needed it's in the log */
1241 n--;
1250 /*
1251 * this operation is special. for roots, this must be
1252 * handled explicitly before rewinding.
1253 * for non-roots, this operation may exist if the node
1254 * was a root: root A -> child B; then A gets empty and
1255 * B is promoted to the new root. in the mod log, we'll
1256 * have a root-replace operation for B, a tree block
1257 * that is no root. we simply ignore that operation.
1258 */
1260 }
1267 }
1270 }
1272 /*
1273 * Called with eb read locked. If the buffer cannot be rewound, the same buffer
1274 * is returned. If rewind operations happen, a fresh buffer is returned. The
1275 * returned buffer is always read-locked. If the returned buffer is not the
1276 * input buffer, the lock on the input buffer is released and the input buffer
1277 * is freed (its refcount is decremented).
1278 */
1282 {
1306 }
1318 }
1319 }
1330 }
1332 /*
1333 * get_old_root() rewinds the state of @root's root node to the given @time_seq
1334 * value. If there are no changes, the current root->root_node is returned. If
1335 * anything changed in between, there's a fresh buffer allocated on which the
1336 * rewind operations are done. In any case, the returned buffer is read locked.
1337 * Returns NULL on error (with no locks held).
1338 */
1341 {
1349 u64 logical;
1365 }
1377 logical);
1381 }
1391 }
1402 }
1405 else
1410 }
1413 {
1423 }
1427 }
1432 {
1436 /* Ensure we can see the FORCE_COW bit */
1439 /*
1440 * We do not need to cow a block if
1441 * 1) this block is not created or changed in this transaction;
1442 * 2) this block does not belong to TREE_RELOC tree;
1443 * 3) the root is not forced COW.
1444 *
1445 * What is forced COW:
1446 * when we create snapshot during committing the transaction,
1447 * after we've finished copying src root, we must COW the shared
1448 * block to ensure the metadata consistency.
1449 */
1457 }
1459 /*
1460 * cows a single block, see __btrfs_cow_block for the real work.
1461 * This version of it has extra checks so that a block isn't COWed more than
1462 * once per transaction, as long as it hasn't been written yet
1463 */
1468 {
1470 u64 search_start;
1490 }
1498 /*
1499 * Before CoWing this block for later modification, check if it's
1500 * the subtree root and do the delayed subtree trace if needed.
1501 *
1502 * Also We don't care about the error, as it's handled internally.
1503 */
1511 }
1513 /*
1514 * helper function for defrag to decide if two blocks pointed to by a
1515 * node are actually close by
1516 */
1518 {
1524 }
1526 /*
1527 * compare two keys in a memcmp fashion
1528 */
1531 {
1537 }
1539 /*
1540 * same as comp_keys only with two btrfs_key's
1541 */
1543 {
1557 }
1559 /*
1560 * this is used by the defrag code to go through all the
1561 * leaves pointed to by a node and reallocate them so that
1562 * disk order is close to key order
1563 */
1568 {
1571 u64 blocknr;
1572 u64 gen;
1575 u64 other;
1576 u32 parent_nritems;
1582 u32 blocksize;
1618 }
1622 }
1626 }
1631 else
1643 }
1650 }
1651 }
1652 }
1666 }
1672 }
1674 }
1676 /*
1677 * search for key in the extent_buffer. The items start at offset p,
1678 * and they are item_size apart. There are 'max' items in p.
1679 *
1680 * the slot in the array is returned via slot, and it points to
1681 * the place where you would insert key if it is not found in
1682 * the array.
1683 *
1684 * slot may point to max if the key is bigger than all of the keys
1685 */
1690 {
1709 }
1725 map_start);
1732 }
1736 map_start);
1737 }
1747 }
1748 }
1751 }
1753 /*
1754 * simple bin_search frontend that does the right thing for
1755 * leaves vs nodes
1756 */
1759 {
1765 slot);
1766 else
1771 slot);
1772 }
1775 {
1780 }
1783 {
1788 }
1790 /* given a node and slot number, this reads the blocks it points to. The
1791 * extent buffer is returned with a reference taken (but unlocked).
1792 */
1795 {
1812 }
1815 }
1817 /*
1818 * node level balancing, used to make sure nodes are in proper order for
1819 * item deletion. We balance from the top down, so we have to make sure
1820 * that a deletion won't leave an node completely empty later on.
1821 */
1825 {
1835 u64 orig_ptr;
1850 }
1852 /*
1853 * deal with the case where there is only one pointer in the root
1854 * by promoting the node below to a root
1855 */
1862 /* promote the child to a root */
1868 }
1877 }
1890 /* once for the path */
1895 /* once for the root ptr */
1898 }
1915 }
1916 }
1930 }
1931 }
1933 /* first, try to make some room in the middle buffer */
1939 }
1941 /*
1942 * then try to empty the right most buffer into the middle
1943 */
1964 }
1965 }
1967 /*
1968 * we're not allowed to leave a node with one item in the
1969 * tree during a delete. A deletion from lower in the tree
1970 * could try to delete the only pointer in this node.
1971 * So, pull some keys from the left.
1972 * There has to be a left pointer at this point because
1973 * otherwise we would have pulled some pointers from the
1974 * right
1975 */
1980 }
1985 }
1990 }
1992 }
2002 /* update the parent key to reflect our changes */
2010 }
2012 /* update the path */
2016 /* left was locked after cow */
2023 }
2027 }
2028 }
2029 /* double check we haven't messed things up */
2033 enospc:
2037 }
2042 }
2044 }
2046 /* Node balancing for insertion. Here we only split or push nodes around
2047 * when they are completely full. This is also done top down, so we
2048 * have to be pessimistic.
2049 */
2053 {
2073 }
2082 /* first, try to make some room in the middle buffer */
2084 u32 left_nr;
2099 }
2100 }
2119 orig_slot -=
2124 }
2126 }
2129 }
2134 /*
2135 * then try to empty the right most buffer into the middle
2136 */
2138 u32 right_nr;
2154 }
2155 }
2178 }
2180 }
2183 }
2185 }
2187 /*
2188 * readahead one full node of leaves, finding things that are close
2189 * to the block in 'slot', and triggering ra on them.
2190 */
2194 {
2197 u32 nritems;
2198 u64 search;
2199 u64 target;
2202 u32 nr;
2203 u32 blocksize;
2220 }
2231 nr--;
2233 nr++;
2236 }
2241 }
2247 }
2248 nscan++;
2251 }
2252 }
2256 {
2261 u64 gen;
2276 /*
2277 * if we get -eagain from btrfs_buffer_uptodate, we
2278 * don't want to return eagain here. That will loop
2279 * forever
2280 */
2284 }
2292 }
2298 }
2301 /*
2302 * when we walk down the tree, it is usually safe to unlock the higher layers
2303 * in the tree. The exceptions are when our path goes through slot 0, because
2304 * operations on the tree might require changing key pointers higher up in the
2305 * tree.
2306 *
2307 * callers might also have set path->keep_locks, which tells this code to keep
2308 * the lock if the path points to the last slot in the block. This is part of
2309 * walking through the tree, and selecting the next slot in the higher block.
2310 *
2311 * lowest_unlock sets the lowest level in the tree we're allowed to unlock. so
2312 * if lowest_unlock is 1, level 0 won't be unlocked
2313 */
2317 {
2331 }
2333 u32 nritems;
2339 }
2340 }
2352 }
2353 }
2354 }
2355 }
2357 /*
2358 * This releases any locks held in the path starting at level and
2359 * going all the way up to the root.
2360 *
2361 * btrfs_search_slot will keep the lock held on higher nodes in a few
2362 * corner cases, such as COW of the block at slot zero in the node. This
2363 * ignores those rules, and it should only be called when there are no
2364 * more updates to be done higher up in the tree.
2365 */
2367 {
2380 }
2381 }
2383 /*
2384 * helper function for btrfs_search_slot. The goal is to find a block
2385 * in cache without setting the path to blocking. If we find the block
2386 * we return zero and the path is unchanged.
2387 *
2388 * If we can't find the block, we set the path blocking and do some
2389 * reada. -EAGAIN is returned and the search must be repeated.
2390 */
2391 static int
2395 {
2397 u64 blocknr;
2398 u64 gen;
2412 /* first we do an atomic uptodate check */
2414 /*
2415 * Do extra check for first_key, eb can be stale due to
2416 * being cached, read from scrub, or have multiple
2417 * parents (shared tree blocks).
2418 */
2423 }
2426 }
2428 /* the pages were up to date, but we failed
2429 * the generation number check. Do a full
2430 * read for the generation number that is correct.
2431 * We must do this without dropping locks so
2432 * we can trust our generation number
2433 */
2436 /* now we're allowed to do a blocking uptodate check */
2441 }
2445 }
2447 /*
2448 * reduce lock contention at high levels
2449 * of the btree by dropping locks before
2450 * we read. Don't release the lock on the current
2451 * level because we need to walk this node to figure
2452 * out which blocks to read.
2453 */
2464 /*
2465 * If the read above didn't mark this buffer up to date,
2466 * it will never end up being up to date. Set ret to EIO now
2467 * and give up so that our caller doesn't loop forever
2468 * on our EAGAINs.
2469 */
2475 }
2479 }
2481 /*
2482 * helper function for btrfs_search_slot. This does all of the checks
2483 * for node-level blocks and does any balancing required based on
2484 * the ins_len.
2485 *
2486 * If no extra work was required, zero is returned. If we had to
2487 * drop the path, -EAGAIN is returned and btrfs_search_slot must
2488 * start over
2489 */
2490 static int
2495 {
2507 }
2517 }
2527 }
2536 }
2541 }
2543 }
2546 again:
2548 done:
2550 }
2554 {
2558 }
2563 }
2568 {
2590 }
2598 }
2603 {
2609 /* We try very hard to do read locks on the root */
2613 /*
2614 * The commit roots are read only so we always do read locks,
2615 * and we always must hold the commit_root_sem when doing
2616 * searches on them, the only exception is send where we don't
2617 * want to block transaction commits for a long time, so
2618 * we need to clone the commit root in order to avoid races
2619 * with transaction commits that create a snapshot of one of
2620 * the roots used by a send operation.
2621 */
2632 }
2634 /*
2635 * Ensure that all callers have set skip_locking when
2636 * p->search_commit_root = 1.
2637 */
2641 }
2647 }
2649 /*
2650 * If the level is set to maximum, we can skip trying to get the read
2651 * lock.
2652 */
2654 /*
2655 * We don't know the level of the root node until we actually
2656 * have it read locked
2657 */
2663 /* Whoops, must trade for write lock */
2666 }
2671 /* The level might have changed, check again */
2674 out:
2678 /*
2679 * Callers are responsible for dropping b's references.
2680 */
2682 }
2685 /*
2686 * btrfs_search_slot - look for a key in a tree and perform necessary
2687 * modifications to preserve tree invariants.
2688 *
2689 * @trans: Handle of transaction, used when modifying the tree
2690 * @p: Holds all btree nodes along the search path
2691 * @root: The root node of the tree
2692 * @key: The key we are looking for
2693 * @ins_len: Indicates purpose of search, for inserts it is 1, for
2694 * deletions it's -1. 0 for plain searches
2695 * @cow: boolean should CoW operations be performed. Must always be 1
2696 * when modifying the tree.
2697 *
2698 * If @ins_len > 0, nodes and leaves will be split as we walk down the tree.
2699 * If @ins_len < 0, nodes will be merged as we walk down the tree (if possible)
2700 *
2701 * If @key is found, 0 is returned and you can find the item in the leaf level
2702 * of the path (level 0)
2703 *
2704 * If @key isn't found, 1 is returned and the leaf level of the path (level 0)
2705 * points to the slot where it should be inserted
2706 *
2707 * If an error is encountered while searching the tree a negative error number
2708 * is returned
2709 */
2713 {
2720 /* everything at write_lock_level or lower must be write locked */
2734 /* when we are removing items, we might have to go up to level
2735 * two as we update tree pointers Make sure we keep write
2736 * for those levels as well
2737 */
2740 /*
2741 * for inserting items, make sure we have a write lock on
2742 * level 1 so we can update keys
2743 */
2745 }
2755 again:
2761 }
2766 /*
2767 * setup the path here so we can release it under lock
2768 * contention with the cow code
2769 */
2773 /*
2774 * if we don't really need to cow this block
2775 * then we don't want to set the path blocking,
2776 * so we test it here
2777 */
2781 }
2783 /*
2784 * must have write locks on this node and the
2785 * parent
2786 */
2794 }
2800 else
2807 }
2808 }
2809 cow_done:
2811 /*
2812 * Leave path with blocking locks to avoid massive
2813 * lock context switch, this is made on purpose.
2814 */
2816 /*
2817 * we have a lock on b and as long as we aren't changing
2818 * the tree, there is no way to for the items in b to change.
2819 * It is safe to drop the lock on our parent before we
2820 * go through the expensive btree search on b.
2821 *
2822 * If we're inserting or deleting (ins_len != 0), then we might
2823 * be changing slot zero, which may require changing the parent.
2824 * So, we can't drop the lock until after we know which slot
2825 * we're operating on.
2826 */
2833 }
2834 }
2845 }
2854 }
2858 /*
2859 * slot 0 is special, if we change the key
2860 * we have to update the parent pointer
2861 * which means we must have a write lock
2862 * on the parent
2863 */
2869 }
2878 }
2887 }
2896 }
2903 }
2905 }
2907 }
2916 }
2926 }
2927 }
2932 }
2933 }
2935 done:
2936 /*
2937 * we don't really know what they plan on doing with the path
2938 * from here on, so for now just mark it as blocking
2939 */
2945 }
2947 /*
2948 * Like btrfs_search_slot, this looks for a key in the given tree. It uses the
2949 * current state of the tree together with the operations recorded in the tree
2950 * modification log to search for the key in a previous version of this tree, as
2951 * denoted by the time_seq parameter.
2952 *
2953 * Naturally, there is no support for insert, delete or cow operations.
2954 *
2955 * The resulting path and return value will be set up as if we called
2956 * btrfs_search_slot at that point in time with ins_len and cow both set to 0.
2957 */
2960 {
2977 }
2979 again:
2984 }
2992 /*
2993 * we have a lock on b and as long as we aren't changing
2994 * the tree, there is no way to for the items in b to change.
2995 * It is safe to drop the lock on our parent before we
2996 * go through the expensive btree search on b.
2997 */
3000 /*
3001 * Since we can unwind ebs we want to do a real search every
3002 * time.
3003 */
3014 }
3022 }
3031 }
3038 }
3043 }
3050 }
3051 }
3053 done:
3060 }
3062 /*
3063 * helper to use instead of search slot if no exact match is needed but
3064 * instead the next or previous item should be returned.
3065 * When find_higher is true, the next higher item is returned, the next lower
3066 * otherwise.
3067 * When return_any and find_higher are both true, and no higher item is found,
3068 * return the next lower instead.
3069 * When return_any is true and find_higher is false, and no lower item is found,
3070 * return the next higher instead.
3071 * It returns 0 if any item is found, 1 if none is found (tree empty), and
3072 * < 0 on error
3073 */
3078 {
3082 again:
3086 /*
3087 * a return value of 1 means the path is at the position where the
3088 * item should be inserted. Normally this is the next bigger item,
3089 * but in case the previous item is the last in a leaf, path points
3090 * to the first free slot in the previous leaf, i.e. at an invalid
3091 * item.
3092 */
3102 /*
3103 * no higher item found, return the next
3104 * lower instead
3105 */
3110 }
3121 }
3124 /*
3125 * no lower item found, return the next
3126 * higher instead
3127 */
3134 }
3135 }
3137 }
3139 /*
3140 * adjust the pointers going up the tree, starting at level
3141 * making sure the right key of each node is points to 'key'.
3142 * This is used after shifting pointers to the left, so it stops
3143 * fixing up pointers when a given leaf/node is not in slot 0 of the
3144 * higher levels
3145 *
3146 */
3149 {
3161 GFP_ATOMIC);
3167 }
3168 }
3170 /*
3171 * update item key.
3172 *
3173 * This function isn't completely safe. It's the caller's responsibility
3174 * that the new key won't break the order
3175 */
3179 {
3198 }
3199 }
3212 }
3213 }
3220 }
3222 /*
3223 * try to push data from one node into the next node left in the
3224 * tree.
3225 *
3226 * returns 0 if some ptrs were pushed left, < 0 if there was some horrible
3227 * error, and > 0 if there was no room in the left hand block.
3228 */
3232 {
3254 /* leave at least 8 pointers in the node if
3255 * we aren't going to empty it
3256 */
3261 }
3262 }
3270 }
3277 /*
3278 * Don't call tree_mod_log_insert_move here, key removal was
3279 * already fully logged by tree_mod_log_eb_copy above.
3280 */
3285 }
3292 }
3294 /*
3295 * try to push data from one node into the next node right in the
3296 * tree.
3297 *
3298 * returns 0 if some ptrs were pushed, < 0 if there was some horrible
3299 * error, and > 0 if there was no room in the right hand block.
3300 *
3301 * this will only push up to 1/2 the contents of the left node over
3302 */
3306 {
3327 /* don't try to empty the node */
3342 push_items);
3346 }
3359 }
3361 /*
3362 * helper function to insert a new root level in the tree.
3363 * A new node is allocated, and a single item is inserted to
3364 * point to the existing root
3365 *
3366 * returns zero on success or < 0 on failure.
3367 */
3371 {
3373 u64 lower_gen;
3386 else
3411 /* the super has an extra ref to root->node */
3420 }
3422 /*
3423 * worker function to insert a single pointer in a node.
3424 * the node should have enough room for the pointer already
3425 *
3426 * slot and level indicate where you want the key to go, and
3427 * blocknr is the block the key points to.
3428 */
3433 {
3449 }
3454 }
3457 GFP_NOFS);
3459 }
3466 }
3468 /*
3469 * split the node at the specified level in path in two.
3470 * The path is corrected to point to the appropriate node after the split
3471 *
3472 * Before splitting this tries to make some room in the node by pushing
3473 * left and right, if either one works, it returns right away.
3474 *
3475 * returns 0 on success and < 0 on failure
3476 */
3480 {
3487 u32 c_nritems;
3492 /*
3493 * trying to split the root, lets make a new one
3494 *
3495 * tree mod log: We don't log_removal old root in
3496 * insert_new_root, because that root buffer will be kept as a
3497 * normal node. We are going to log removal of half of the
3498 * elements below with tree_mod_log_eb_copy. We're holding a
3499 * tree lock on the buffer, which is why we cannot race with
3500 * other tree_mod_log users.
3501 */
3513 }
3531 }
3555 }
3557 }
3559 /*
3560 * how many bytes are required to store the items in a leaf. start
3561 * and nr indicate which items in the leaf to check. This totals up the
3562 * space used both by the item structs and the item data
3563 */
3565 {
3584 }
3586 /*
3587 * The space between the end of the leaf items and
3588 * the start of the leaf data. IOW, how much room
3589 * the leaf has left for both items and data
3590 */
3592 {
3601 ret,
3604 }
3606 }
3608 /*
3609 * min slot controls the lowest index we're willing to push to the
3610 * right. We'll push up to and including min_slot, but no lower
3611 */
3616 u32 min_slot)
3617 {
3624 u32 i;
3628 u32 nr;
3629 u32 right_nritems;
3630 u32 data_end;
3631 u32 this_item_size;
3637 else
3656 }
3657 }
3666 push_items++;
3670 i--;
3671 }
3678 /* push left to right */
3684 /* make room in the right data area */
3691 /* copy from the left data area */
3695 push_space);
3701 /* copy the items from left to right */
3706 /* update the item pointers */
3714 }
3721 else
3730 /* then fixup the leaf pointer in the path */
3742 }
3745 out_unlock:
3749 }
3751 /*
3752 * push some data in the path leaf to the right, trying to free up at
3753 * least data_size bytes. returns zero if the push worked, nonzero otherwise
3754 *
3755 * returns 1 if the push failed because the other node didn't have enough
3756 * room, 0 if everything worked out and < 0 if there were major errors.
3757 *
3758 * this will push starting from min_slot to the end of the leaf. It won't
3759 * push any slot lower than min_slot
3760 */
3765 {
3771 u32 left_nritems;
3785 /*
3786 * slot + 1 is not valid or we fail to read the right node,
3787 * no big deal, just return.
3788 */
3799 /* cow and double check */
3814 /* Key greater than all keys in the leaf, right neighbor has
3815 * enough room for it and we're not emptying our leaf to delete
3816 * it, therefore use right neighbor to insert the new item and
3817 * no need to touch/dirty our left leaf. */
3824 }
3828 out_unlock:
3832 }
3834 /*
3835 * push some data in the path leaf to the left, trying to free up at
3836 * least data_size bytes. returns zero if the push worked, nonzero otherwise
3837 *
3838 * max_slot can put a limit on how far into the leaf we'll push items. The
3839 * item at 'max_slot' won't be touched. Use (u32)-1 to make us do all the
3840 * items
3841 */
3845 u32 max_slot)
3846 {
3854 u32 old_left_nritems;
3855 u32 nr;
3857 u32 this_item_size;
3858 u32 old_left_item_size;
3865 else
3879 }
3880 }
3889 push_items++;
3891 }
3896 }
3899 /* push data from right to left */
3910 BTRFS_LEAF_DATA_OFFSET +
3912 push_space);
3918 u32 ioff;
3926 }
3929 /* fixup right node */
3932 right_nritems);
3939 BTRFS_LEAF_DATA_OFFSET +
3946 }
3956 }
3961 else
3967 /* then fixup the leaf pointer in the path */
3978 }
3981 out:
3985 }
3987 /*
3988 * push some data in the path leaf to the left, trying to free up at
3989 * least data_size bytes. returns zero if the push worked, nonzero otherwise
3990 *
3991 * max_slot can put a limit on how far into the leaf we'll push items. The
3992 * item at 'max_slot' won't be touched. Use (u32)-1 to make us push all the
3993 * items
3994 */
3998 {
4003 u32 right_nritems;
4019 /*
4020 * slot - 1 is not valid or we fail to read the left node,
4021 * no big deal, just return.
4022 */
4033 }
4035 /* cow and double check */
4039 /* we hit -ENOSPC, but it isn't fatal here */
4043 }
4049 }
4053 max_slot);
4054 out:
4058 }
4060 /*
4061 * split the path's leaf in two, making sure there is at least data_size
4062 * available for the resulting leaf level of the path.
4063 */
4069 {
4096 u32 ioff;
4101 }
4120 }
4123 }
4125 /*
4126 * double splits happen when we need to insert a big item in the middle
4127 * of a leaf. A double split can leave us with 3 mostly empty leaves:
4128 * leaf: [ slots 0 - N] [ our target ] [ N + 1 - total in leaf ]
4129 * A B C
4130 *
4131 * We avoid this by trying to push the items on either side of our target
4132 * into the adjacent leaves. If all goes well we can avoid the double split
4133 * completely.
4134 */
4139 {
4143 u32 nritems;
4150 /*
4151 * try to push all the items after our slot into the
4152 * right leaf
4153 */
4159 progress++;
4162 /*
4163 * our goal is to get our slot at the start or end of a leaf. If
4164 * we've done so we're done
4165 */
4172 /* try to push all the items before our slot into the next leaf */
4182 progress++;
4187 }
4189 /*
4190 * split the path's leaf in two, making sure there is at least data_size
4191 * available for the resulting leaf level of the path.
4192 *
4193 * returns 0 if all went well and < 0 on failure.
4194 */
4200 {
4203 u32 nritems;
4220 /* first try to make some room by pushing left and right */
4239 }
4242 /* did the pushes work? */
4245 }
4251 }
4252 again:
4273 }
4274 }
4275 }
4291 }
4292 }
4293 }
4294 }
4298 else
4328 }
4329 /*
4330 * We create a new leaf 'right' for the required ins_len and
4331 * we'll do btrfs_mark_buffer_dirty() on this leaf after copying
4332 * the content of ins_len to 'right'.
4333 */
4335 }
4341 num_doubles++;
4343 }
4347 push_for_double:
4353 }
4358 {
4363 u32 item_size;
4380 }
4394 /* if our item isn't there, return now */
4398 /* the leaf has changed, it now has room. return now */
4407 }
4417 err:
4420 }
4425 {
4431 u32 nritems;
4432 u32 item_size;
4433 u32 orig_offset;
4455 /* shift the items */
4459 }
4475 /* write the data for the start of the original item */
4478 split_offset);
4480 /* write the data for the new item */
4489 }
4491 /*
4492 * This function splits a single item into two items,
4493 * giving 'new_key' to the new item and splitting the
4494 * old one at split_offset (from the start of the item).
4495 *
4496 * The path may be released by this operation. After
4497 * the split, the path is pointing to the old item. The
4498 * new item is going to be in the same node as the old one.
4499 *
4500 * Note, the item being split must be smaller enough to live alone on
4501 * a tree block with room for one extra struct btrfs_item
4502 *
4503 * This allows us to split the item in place, keeping a lock on the
4504 * leaf the entire time.
4505 */
4511 {
4520 }
4522 /*
4523 * This function duplicate a item, giving 'new_key' to the new item.
4524 * It guarantees both items live in the same tree leaf and the new item
4525 * is contiguous with the original item.
4526 *
4527 * This allows us to split file extent in place, keeping a lock on the
4528 * leaf the entire time.
4529 */
4534 {
4537 u32 item_size;
4554 item_size);
4556 }
4558 /*
4559 * make the item pointed to by the path smaller. new_size indicates
4560 * how small to make it, and from_end tells us if we just chop bytes
4561 * off the end of the item or if we shift the item to chop bytes off
4562 * the front.
4563 */
4565 {
4569 u32 nritems;
4596 /*
4597 * item0..itemN ... dataN.offset..dataN.size .. data0.size
4598 */
4599 /* first correct the data pointers */
4601 u32 ioff;
4607 }
4609 /* shift the data */
4616 u64 offset;
4630 BTRFS_FILE_EXTENT_INLINE) {
4634 BTRFS_FILE_EXTENT_INLINE_DATA_START);
4635 }
4636 }
4647 }
4656 }
4657 }
4659 /*
4660 * make the item pointed to by the path bigger, data_size is the added size.
4661 */
4663 {
4667 u32 nritems;
4684 }
4694 }
4696 /*
4697 * item0..itemN ... dataN.offset..dataN.size .. data0.size
4698 */
4699 /* first correct the data pointers */
4701 u32 ioff;
4707 }
4709 /* shift the data */
4723 }
4724 }
4726 /*
4727 * this is a helper for btrfs_insert_empty_items, the main goal here is
4728 * to save stack depth by doing the bulk of the work in a function
4729 * that doesn't call btrfs_search_slot
4730 */
4734 {
4738 u32 nritems;
4748 }
4764 }
4774 }
4775 /*
4776 * item0..itemN ... dataN.offset..dataN.size .. data0.size
4777 */
4778 /* first correct the data pointers */
4780 u32 ioff;
4786 }
4787 /* shift the items */
4792 /* shift the data */
4797 }
4799 /* setup the item for the new data */
4808 }
4816 }
4817 }
4819 /*
4820 * Given a key and some data, insert items into the tree.
4821 * This does all the path init required, making room in the tree if needed.
4822 */
4828 {
4851 }
4853 /*
4854 * Given a key and some data, insert an item into the tree.
4855 * This does all the path init required, making room in the tree if needed.
4856 */
4859 u32 data_size)
4860 {
4875 }
4878 }
4880 /*
4881 * delete the pointer from a given node.
4882 *
4883 * the tree should have been previously balanced so the deletion does not
4884 * empty a node.
4885 */
4888 {
4890 u32 nritems;
4899 }
4907 GFP_NOFS);
4909 }
4911 nritems--;
4915 /* just turn the root into a leaf and break */
4922 }
4924 }
4926 /*
4927 * a helper function to delete the leaf pointed to by path->slots[1] and
4928 * path->nodes[1].
4929 *
4930 * This deletes the pointer in path->nodes[1] and frees the leaf
4931 * block extent. zero is returned if it all worked out, < 0 otherwise.
4932 *
4933 * The path must have already been setup for deleting the leaf, including
4934 * all the proper balancing. path->nodes[1] must be locked.
4935 */
4940 {
4944 /*
4945 * btrfs_free_extent is expensive, we want to make sure we
4946 * aren't holding any locks when we call it
4947 */
4955 }
4956 /*
4957 * delete the item at the leaf level in path. If that empties
4958 * the leaf, remove it from the tree
4959 */
4962 {
4966 u32 last_off;
4971 u32 nritems;
4993 u32 ioff;
4999 }
5005 }
5009 /* delete the leaf if we've emptied it */
5017 }
5025 }
5027 /* delete the leaf if it is mostly empty */
5029 /* push_leaf_left fixes the path.
5030 * make sure the path still points to our leaf
5031 * for possible call to del_ptr below
5032 */
5048 }
5056 /* if we're still in the path, make sure
5057 * we're dirty. Otherwise, one of the
5058 * push_leaf functions must have already
5059 * dirtied this buffer
5060 */
5064 }
5067 }
5068 }
5070 }
5072 /*
5073 * search the tree again to find a leaf with lesser keys
5074 * returns 0 if it found something or 1 if there are no lesser leaves.
5075 * returns < 0 on io errors.
5076 *
5077 * This may release the path, and so you may lose any locks held at the
5078 * time you call it.
5079 */
5081 {
5099 }
5107 /*
5108 * We might have had an item with the previous key in the tree right
5109 * before we released our path. And after we released our path, that
5110 * item might have been pushed to the first slot (0) of the leaf we
5111 * were holding due to a tree balance. Alternatively, an item with the
5112 * previous key can exist as the only element of a leaf (big fat item).
5113 * Therefore account for these 2 cases, so that our callers (like
5114 * btrfs_previous_item) don't miss an existing item with a key matching
5115 * the previous key we computed above.
5116 */
5120 }
5122 /*
5123 * A helper function to walk down the tree starting at min_key, and looking
5124 * for nodes or leaves that are have a minimum transaction id.
5125 * This is used by the btree defrag code, and tree logging
5126 *
5127 * This does not cow, but it does stuff the starting key it finds back
5128 * into min_key, so you can call btrfs_search_slot with cow=1 on the
5129 * key and get a writable path.
5130 *
5131 * This honors path->lowest_level to prevent descent past a given level
5132 * of the tree.
5133 *
5134 * min_trans indicates the oldest transaction that you are interested
5135 * in walking through. Any nodes or leaves older than min_trans are
5136 * skipped over (without reading them).
5137 *
5138 * returns zero if something useful was found, < 0 on error and 1 if there
5139 * was nothing in the tree that matched the search criteria.
5140 */
5143 u64 min_trans)
5144 {
5149 u32 nritems;
5155 again:
5165 }
5173 }
5175 /* at the lowest level, we're done, setup the path and exit */
5183 }
5185 slot--;
5186 /*
5187 * check this node pointer against the min_trans parameters.
5188 * If it is too old, old, skip to the next one.
5189 */
5191 u64 gen;
5195 slot++;
5197 }
5199 }
5200 find_next_key:
5201 /*
5202 * we didn't find a candidate key in this node, walk forward
5203 * and find another one
5204 */
5209 min_trans);
5215 }
5216 }
5217 /* save our key for returning back */
5223 }
5229 }
5236 }
5237 out:
5243 }
5245 }
5248 {
5260 }
5264 {
5275 /* move upnext */
5284 }
5286 }
5288 /*
5289 * Returns 1 if it had to move up and next. 0 is returned if it moved only next
5290 * or down.
5291 */
5296 {
5303 }
5308 else
5311 }
5313 }
5318 {
5338 }
5340 #define ADVANCE 1
5341 #define ADVANCE_ONLY_NEXT -1
5343 /*
5344 * This function compares two trees and calls the provided callback for
5345 * every changed/new/deleted item it finds.
5346 * If shared tree blocks are encountered, whole subtrees are skipped, making
5347 * the compare pretty fast on snapshotted subvolumes.
5348 *
5349 * This currently works on commit roots only. As commit roots are read only,
5350 * we don't do any locking. The commit roots are protected with transactions.
5351 * Transactions are ended and rejoined when a commit is tried in between.
5352 *
5353 * This function checks for modifications done to the trees while comparing.
5354 * If it detects a change, it aborts immediately.
5355 */
5359 {
5376 u64 left_blockptr;
5377 u64 right_blockptr;
5378 u64 left_gen;
5379 u64 right_gen;
5385 }
5390 }
5396 }
5403 /*
5404 * Strategy: Go to the first items of both trees. Then do
5405 *
5406 * If both trees are at level 0
5407 * Compare keys of current items
5408 * If left < right treat left item as new, advance left tree
5409 * and repeat
5410 * If left > right treat right item as deleted, advance right tree
5411 * and repeat
5412 * If left == right do deep compare of items, treat as changed if
5413 * needed, advance both trees and repeat
5414 * If both trees are at the same level but not at level 0
5415 * Compare keys of current nodes/leafs
5416 * If left < right advance left tree and repeat
5417 * If left > right advance right tree and repeat
5418 * If left == right compare blockptrs of the next nodes/leafs
5419 * If they match advance both trees but stay at the same level
5420 * and repeat
5421 * If they don't match advance both trees while allowing to go
5422 * deeper and repeat
5423 * If tree levels are different
5424 * Advance the tree that needs it and repeat
5425 *
5426 * Advancing a tree means:
5427 * If we are at level 0, try to go to the next slot. If that's not
5428 * possible, go one level up and repeat. Stop when we found a level
5429 * where we could go to the next slot. We may at this point be on a
5430 * node or a leaf.
5431 *
5432 * If we are not at level 0 and not on shared tree blocks, go one
5433 * level deeper.
5434 *
5435 * If we are not at level 0 and on shared tree blocks, go one slot to
5436 * the right if possible or go up and right.
5437 */
5448 }
5458 }
5464 else
5470 else
5480 left_root_level,
5488 }
5491 right_root_level,
5499 }
5508 BTRFS_COMPARE_TREE_DELETED,
5509 ctx);
5512 }
5519 BTRFS_COMPARE_TREE_NEW,
5520 ctx);
5523 }
5526 }
5533 BTRFS_COMPARE_TREE_NEW,
5534 ctx);
5541 BTRFS_COMPARE_TREE_DELETED,
5542 ctx);
5551 tmp_buf);
5554 else
5562 }
5584 /*
5585 * As we're on a shared block, don't
5586 * allow to go deeper.
5587 */
5593 }
5594 }
5599 }
5600 }
5602 out:
5607 }
5609 /*
5610 * this is similar to btrfs_next_leaf, but does not try to preserve
5611 * and fixup the path. It looks for and returns the next key in the
5612 * tree based on the current path and the min_trans parameters.
5613 *
5614 * 0 is returned if another key is found, < 0 if there are any errors
5615 * and 1 is returned if there are no higher keys in the tree
5616 *
5617 * path->keep_locks should be set to 1 on the search made before
5618 * calling this function.
5619 */
5622 {
5633 next:
5643 level++;
5645 }
5650 else
5665 slot++;
5667 }
5675 slot++;
5677 }
5679 }
5681 }
5683 }
5685 /*
5686 * search the tree again to find a leaf with greater keys
5687 * returns 0 if it found something or 1 if there are no greater leaves.
5688 * returns < 0 on io errors.
5689 */
5691 {
5693 }
5696 u64 time_seq)
5697 {
5703 u32 nritems;
5713 again:
5724 else
5732 /*
5733 * by releasing the path above we dropped all our locks. A balance
5734 * could have added more items next to the key that used to be
5735 * at the very end of the block. So, check again here and
5736 * advance the path if there are now more items available.
5737 */
5743 }
5744 /*
5745 * So the above check misses one case:
5746 * - after releasing the path above, someone has removed the item that
5747 * used to be at the very end of the block, and balance between leafs
5748 * gets another one with bigger key.offset to replace it.
5749 *
5750 * This one should be returned as well, or we can get leaf corruption
5751 * later(esp. in __btrfs_drop_extents()).
5752 *
5753 * And a bit more explanation about this check,
5754 * with ret > 0, the key isn't found, the path points to the slot
5755 * where it should be inserted, so the path->slots[0] item must be the
5756 * bigger one.
5757 */
5761 }
5767 }
5772 level++;
5776 }
5778 }
5783 }
5795 }
5800 /*
5801 * If we don't get the lock, we may be racing
5802 * with push_leaf_left, holding that lock while
5803 * itself waiting for the leaf we've currently
5804 * locked. To solve this situation, we give up
5805 * on our lock and cycle.
5806 */
5811 }
5815 }
5817 }
5819 }
5822 level--;
5843 }
5850 }
5852 }
5853 }
5855 done:
5862 }
5864 /*
5865 * this uses btrfs_prev_leaf to walk backwards in the tree, and keeps
5866 * searching until it gets past min_objectid or finds an item of 'type'
5867 *
5868 * returns 0 if something is found, 1 if nothing was found and < 0 on error
5869 */
5873 {
5876 u32 nritems;
5887 }
5903 }
5905 }
5907 /*
5908 * search in extent tree to find a previous Metadata/Data extent item with
5909 * min objecitd.
5910 *
5911 * returns 0 if something is found, 1 if nothing was found and < 0 on error
5912 */
5915 {
5918 u32 nritems;
5929 }
5946 }
5948 }