| blob | 0cc919d15b1441479af03b89e4e449092460f635 |
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>
10 #include <linux/error-injection.h>
42 u16 size;
51 };
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 */
58 {
64 }
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 */
83 {
86 }
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 */
106 {
109 }
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 */
124 {
128 }
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 */
145 {
149 }
151 /* This exists for btrfs-progs usages. */
153 {
155 }
158 {
160 /*
161 * csum type is validated at mount time
162 */
164 }
167 {
168 /* csum type is validated at mount time */
170 }
172 /*
173 * Return driver name if defined, otherwise the name that's also a valid driver
174 * name
175 */
177 {
178 /* csum type is validated at mount time */
182 }
185 {
187 }
190 {
194 }
196 /* this also releases the path */
198 {
203 }
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 */
212 {
222 }
225 }
226 }
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 */
234 {
240 }
242 }
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 */
255 {
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 */
271 }
274 }
276 }
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 */
284 {
293 /* Want the extent tree to be the last on the list */
297 else
300 }
302 }
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 */
313 {
329 else
345 BTRFS_HEADER_FLAG_RELOC);
348 else
356 else
363 }
368 }
370 /*
371 * check if the tree block can be shared by multiple trees
372 */
376 {
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 */
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 */
408 }
415 {
417 u64 refs;
418 u64 owner;
419 u64 flags;
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 */
453 }
459 else
461 }
467 "found tree block at bytenr %llu level %d root %llu refs %llu flags %llx without full backref flag set",
473 }
490 }
492 BTRFS_BLOCK_FLAG_FULL_BACKREF);
499 else
503 }
508 else
515 }
518 }
520 }
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 */
541 {
565 else
572 }
579 /* cow is set to blocking by btrfs_init_new_buffer */
586 BTRFS_HEADER_FLAG_RELOC);
589 else
598 }
605 }
606 }
618 }
629 }
633 BTRFS_MOD_LOG_KEY_REPLACE);
637 }
648 }
649 }
655 }
656 }
664 error_unlock_cow:
668 }
673 {
677 /* Ensure we can see the FORCE_COW bit */
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 */
698 }
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 */
710 {
712 u64 search_start;
721 }
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 */
733 "unexpected transaction when attempting to COW block %llu on root %llu, transaction %llu running transaction %llu fs generation %llu",
738 }
743 }
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 */
760 }
763 /*
764 * same as comp_keys only with two btrfs_key's
765 */
767 {
781 }
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 */
799 {
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 */
817 }
825 }
848 }
859 }
860 }
863 }
866 {
871 }
874 {
879 }
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 */
886 {
909 }
912 }
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 */
922 {
932 u64 orig_ptr;
946 }
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 */
958 /* promote the child to a root */
963 }
967 BTRFS_NESTING_COW);
972 }
980 }
990 /* once for the path */
995 /* once for the root ptr */
1000 }
1002 }
1013 }
1018 BTRFS_NESTING_LEFT_COW);
1022 }
1023 }
1031 }
1036 BTRFS_NESTING_RIGHT_COW);
1040 }
1041 }
1043 /* first, try to make some room in the middle buffer */
1049 }
1051 /*
1052 * then try to empty the right most buffer into the middle
1053 */
1066 }
1075 }
1080 BTRFS_MOD_LOG_KEY_REPLACE);
1084 }
1087 }
1088 }
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 */
1101 "missing left child when middle child only has 1 item, parent bytenr %llu level %d mid bytenr %llu root %llu",
1107 }
1112 }
1117 }
1119 }
1128 }
1136 }
1138 /* update the parent key to reflect our changes */
1142 BTRFS_MOD_LOG_KEY_REPLACE);
1146 }
1149 }
1151 /* update the path */
1155 /* left was locked after cow */
1162 }
1166 }
1167 }
1168 /* double check we haven't messed things up */
1172 out:
1176 }
1181 }
1183 }
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 */
1192 {
1212 }
1217 /* first, try to make some room in the middle buffer */
1219 u32 left_nr;
1233 BTRFS_NESTING_LEFT_COW);
1238 }
1239 }
1247 BTRFS_MOD_LOG_KEY_REPLACE);
1253 }
1263 orig_slot -=
1268 }
1270 }
1273 }
1275 /*
1276 * then try to empty the right most buffer into the middle
1277 */
1279 u32 right_nr;
1298 }
1299 }
1307 BTRFS_MOD_LOG_KEY_REPLACE);
1313 }
1327 }
1329 }
1332 }
1334 }
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 */
1343 {
1346 u32 nritems;
1347 u64 search;
1348 u64 target;
1350 u64 nread_max;
1351 u32 nr;
1352 u32 blocksize;
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 */
1371 else
1375 }
1386 }
1387 }
1398 nr--;
1401 nr++;
1404 }
1409 }
1416 }
1417 nscan++;
1420 }
1421 }
1424 {
1440 }
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 */
1459 {
1474 }
1477 u32 nritems;
1483 }
1484 }
1485 }
1495 }
1496 }
1497 }
1498 }
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
1513 {
1516 u64 blocknr;
1517 u64 gen;
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 */
1545 /* first we do an atomic uptodate check */
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 */
1556 }
1559 }
1564 }
1569 /* now we're allowed to do a blocking uptodate check */
1575 }
1583 }
1590 }
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 */
1609 out:
1615 }
1618 }
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
1634 {
1645 }
1658 }
1669 }
1671 }
1673 }
1678 {
1700 }
1708 }
1713 {
1722 /*
1723 * Ensure that all callers have set skip_locking when
1724 * p->search_commit_root = 1.
1725 */
1729 }
1735 }
1737 /* We try very hard to do read locks on the root */
1740 /*
1741 * If the level is set to maximum, we can skip trying to get the read
1742 * lock.
1743 */
1745 /*
1746 * We don't know the level of the root node until we actually
1747 * have it read locked
1748 */
1755 }
1760 /* Whoops, must trade for write lock */
1763 }
1768 /* The level might have changed, check again */
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 */
1781 }
1786 /*
1787 * Callers are responsible for dropping b's references.
1788 */
1790 }
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 */
1805 {
1827 }
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 */
1845 }
1848 }
1856 {
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 */
1871 /*
1872 * Cache the leaf free space, since we will need it later and it
1873 * will not change until then.
1874 */
1877 /*
1878 * !path->locks[1] means we have a single node tree, the leaf is
1879 * the root of the tree.
1880 */
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 */
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 */
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 */
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 */
1934 }
1935 }
1936 }
1943 }
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 */
1958 }
1972 }
1973 }
1976 }
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 */
2012 {
2020 /* everything at write_lock_level or lower must be write locked */
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 */
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 */
2049 /*
2050 * for inserting items, make sure we have a write lock on
2051 * level 1 so we can update keys
2052 */
2054 }
2071 }
2072 }
2074 again:
2080 }
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 */
2098 /*
2099 * must have write locks on this node and the
2100 * parent
2101 */
2109 }
2114 BTRFS_NESTING_COW);
2115 else
2119 BTRFS_NESTING_COW);
2123 }
2124 }
2125 cow_done:
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 */
2145 }
2146 }
2157 }
2166 slot--;
2167 }
2176 }
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 */
2189 }
2198 }
2206 }
2222 }
2225 }
2227 }
2229 }
2230 }
2232 done:
2243 }
2246 }
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 */
2262 {
2279 }
2281 again:
2286 }
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 */
2312 }
2316 slot--;
2317 }
2325 }
2333 }
2341 }
2344 }
2346 done:
2351 }
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 */
2363 {
2383 }
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 */
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 */
2414 }
2415 }
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 */
2432 }
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 */
2450 {
2454 again:
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 */
2474 /*
2475 * no higher item found, return the next
2476 * lower instead
2477 */
2482 }
2493 }
2496 /*
2497 * no lower item found, return the next
2498 * higher instead
2499 */
2506 }
2507 }
2509 }
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 */
2519 {
2530 }
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 */
2545 {
2552 }
2556 }
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 */
2569 {
2581 BTRFS_MOD_LOG_KEY_REPLACE);
2587 }
2588 }
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 */
2599 {
2619 }
2620 }
2633 }
2634 }
2641 }
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 */
2665 {
2672 /* No key to check in one of the tree blocks */
2682 }
2695 }
2697 }
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 */
2709 {
2731 /* leave at least 8 pointers in the node if
2732 * we aren't going to empty it
2733 */
2738 }
2739 }
2743 /* dst is the left eb, src is the middle eb */
2748 }
2753 }
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 */
2768 }
2775 }
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 */
2789 {
2810 /* don't try to empty the node */
2817 /* dst is the right eb, src is the middle eb */
2822 }
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 */
2834 push_items);
2838 }
2851 }
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 */
2863 {
2864 u64 lower_gen;
2877 else
2909 }
2912 /* the super has an extra ref to root->node */
2921 }
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 */
2934 {
2952 }
2953 }
2958 }
2961 BTRFS_MOD_LOG_KEY_ADD);
2965 }
2966 }
2975 }
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 */
2989 {
2996 u32 c_nritems;
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 */
3022 }
3043 }
3060 }
3071 }
3073 }
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 */
3081 {
3093 }
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 */
3101 {
3110 ret,
3113 }
3115 }
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 */
3126 u32 min_slot)
3127 {
3134 u32 i;
3137 u32 nr;
3138 u32 right_nritems;
3139 u32 data_end;
3140 u32 this_item_size;
3144 else
3161 }
3162 }
3172 push_items++;
3176 i--;
3177 }
3184 /* push left to right */
3190 /* make room in the right data area */
3195 /* copy from the left data area */
3201 /* copy the items from left to right */
3204 /* update the item pointers */
3212 }
3219 else
3228 /* then fixup the leaf pointer in the path */
3240 }
3243 out_unlock:
3247 }
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 */
3263 {
3269 u32 left_nritems;
3307 }
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. */
3319 }
3323 out_unlock:
3327 }
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 */
3341 u32 max_slot)
3342 {
3349 u32 old_left_nritems;
3350 u32 nr;
3352 u32 this_item_size;
3353 u32 old_left_item_size;
3358 else
3370 }
3371 }
3378 free_space)
3381 push_items++;
3383 }
3388 }
3391 /* push data from right to left */
3405 u32 ioff;
3410 }
3413 /* fixup right node */
3416 right_nritems);
3427 }
3436 }
3441 else
3447 /* then fixup the leaf pointer in the path */
3458 }
3461 out:
3465 }
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 */
3478 {
3483 u32 right_nritems;
3508 }
3512 BTRFS_NESTING_LEFT_COW);
3514 /* we hit -ENOSPC, but it isn't fatal here */
3518 }
3524 }
3527 out:
3531 }
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 */
3542 {
3564 u32 ioff;
3568 }
3589 }
3594 }
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 */
3610 {
3614 u32 nritems;
3621 /*
3622 * try to push all the items after our slot into the
3623 * right leaf
3624 */
3630 progress++;
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 */
3643 /* try to push all the items before our slot into the next leaf */
3653 progress++;
3658 }
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 */
3671 {
3674 u32 nritems;
3691 /* first try to make some room by pushing left and right */
3710 }
3713 /* did the pushes work? */
3716 }
3722 }
3723 again:
3744 }
3745 }
3746 }
3762 }
3763 }
3764 }
3765 }
3769 else
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 */
3783 BTRFS_NESTING_SPLIT);
3798 }
3812 }
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 */
3826 }
3833 }
3837 num_doubles++;
3839 }
3843 push_for_double:
3849 }
3854 {
3859 u32 item_size;
3876 }
3890 /* if our item isn't there, return now */
3894 /* the leaf has changed, it now has room. return now */
3903 }
3912 err:
3915 }
3921 {
3925 u32 nritems;
3926 u32 item_size;
3927 u32 orig_offset;
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 */
3952 /* shift the items */
3954 }
3968 /* write the data for the start of the original item */
3971 split_offset);
3973 /* write the data for the new item */
3982 }
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 */
4004 {
4013 }
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 */
4023 {
4026 u32 nritems;
4051 /*
4052 * item0..itemN ... dataN.offset..dataN.size .. data0.size
4053 */
4054 /* first correct the data pointers */
4057 u32 ioff;
4061 }
4063 /* shift the data */
4069 u64 offset;
4083 BTRFS_FILE_EXTENT_INLINE) {
4087 BTRFS_FILE_EXTENT_INLINE_DATA_START);
4088 }
4089 }
4099 }
4107 }
4108 }
4110 /*
4111 * make the item pointed to by the path bigger, data_size is the added size.
4112 */
4115 {
4118 u32 nritems;
4133 }
4143 }
4145 /*
4146 * item0..itemN ... dataN.offset..dataN.size .. data0.size
4147 */
4148 /* first correct the data pointers */
4151 u32 ioff;
4155 }
4157 /* shift the data */
4169 }
4170 }
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 */
4186 {
4189 u32 nritems;
4195 u32 total_size;
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 */
4205 }
4220 }
4232 }
4233 /*
4234 * item0..itemN ... dataN.offset..dataN.size .. data0.size
4235 */
4236 /* first correct the data pointers */
4238 u32 ioff;
4243 }
4244 /* shift the items */
4247 /* shift the data */
4251 }
4253 /* setup the item for the new data */
4260 }
4268 }
4269 }
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 */
4284 u32 data_size)
4285 {
4294 }
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 */
4308 {
4311 u32 total_size;
4325 }
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 */
4333 u32 data_size)
4334 {
4349 }
4352 }
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 */
4366 {
4369 u32 item_size;
4384 item_size);
4386 }
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 */
4398 {
4400 u32 nritems;
4411 }
4412 }
4420 BTRFS_MOD_LOG_KEY_REMOVE);
4424 }
4425 }
4427 nritems--;
4431 /* just turn the root into a leaf and break */
4438 }
4441 }
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 */
4457 {
4465 /*
4466 * btrfs_free_extent is expensive, we want to make sure we
4467 * aren't holding any locks when we call it
4468 */
4480 }
4481 /*
4482 * delete the item at the leaf level in path. If that empties
4483 * the leaf, remove it from the tree
4484 */
4487 {
4492 u32 nritems;
4512 u32 ioff;
4516 }
4519 }
4523 /* delete the leaf if we've emptied it */
4532 }
4540 }
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 */
4551 u32 min_push_space;
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 */
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 */
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 */
4588 }
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 */
4606 }
4609 }
4610 }
4612 }
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 */
4635 u64 min_trans)
4636 {
4641 u32 nritems;
4648 again:
4658 }
4666 }
4668 /* at the lowest level, we're done, setup the path and exit */
4676 }
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 */
4684 u64 gen;
4688 slot++;
4690 }
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 */
4701 min_trans);
4707 }
4708 }
4709 /* save our key for returning back */
4715 }
4720 }
4727 }
4728 out:
4733 }
4735 }
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 */
4750 {
4761 next:
4771 level++;
4773 }
4778 else
4793 slot++;
4795 }
4803 slot++;
4805 }
4807 }
4809 }
4811 }
4814 u64 time_seq)
4815 {
4823 u32 nritems;
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 */
4839 again:
4856 }
4859 }
4860 }
4862 }
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 */
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 */
4898 }
4904 }
4909 level++;
4913 }
4915 }
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 */
4927 }
4930 }
4941 }
4948 }
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 */
4961 }
4964 }
4966 }
4969 level--;
4985 }
4992 }
4995 }
4996 }
4997 }
4999 done:
5009 }
5012 }
5015 {
5020 }
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 */
5031 {
5034 u32 nritems;
5044 }
5060 }
5062 }
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 */
5072 {
5075 u32 nritems;
5085 }
5102 }
5104 }
5107 {
5112 }
5115 {
5117 }