| blob | 693dc27ffb8979c06da18996aa6bb98c72a6e75e |
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;
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 */
1555 }
1560 }
1565 }
1574 }
1576 /* Now we're allowed to do a blocking uptodate check. */
1581 }
1587 }
1592 }
1597 }
1607 }
1616 }
1618 /* Now we're allowed to do a blocking uptodate check. */
1623 }
1625 /*
1626 * If the read above didn't mark this buffer up to date,
1627 * it will never end up being up to date. Set ret to EIO now
1628 * and give up so that our caller doesn't loop forever
1629 * on our EAGAINs.
1630 */
1634 }
1640 }
1641 out:
1647 else
1649 }
1654 }
1656 /*
1657 * helper function for btrfs_search_slot. This does all of the checks
1658 * for node-level blocks and does any balancing required based on
1659 * the ins_len.
1660 *
1661 * If no extra work was required, zero is returned. If we had to
1662 * drop the path, -EAGAIN is returned and btrfs_search_slot must
1663 * start over
1664 */
1665 static int
1670 {
1681 }
1694 }
1705 }
1707 }
1709 }
1714 {
1736 }
1744 }
1749 {
1758 /*
1759 * Ensure that all callers have set skip_locking when
1760 * p->search_commit_root = 1.
1761 */
1765 }
1771 }
1773 /* We try very hard to do read locks on the root */
1776 /*
1777 * If the level is set to maximum, we can skip trying to get the read
1778 * lock.
1779 */
1781 /*
1782 * We don't know the level of the root node until we actually
1783 * have it read locked
1784 */
1791 }
1796 /* Whoops, must trade for write lock */
1799 }
1804 /* The level might have changed, check again */
1807 out:
1808 /*
1809 * The root may have failed to write out at some point, and thus is no
1810 * longer valid, return an error in this case.
1811 */
1817 }
1822 /*
1823 * Callers are responsible for dropping b's references.
1824 */
1826 }
1828 /*
1829 * Replace the extent buffer at the lowest level of the path with a cloned
1830 * version. The purpose is to be able to use it safely, after releasing the
1831 * commit root semaphore, even if relocation is happening in parallel, the
1832 * transaction used for relocation is committed and the extent buffer is
1833 * reallocated in the next transaction.
1834 *
1835 * This is used in a context where the caller does not prevent transaction
1836 * commits from happening, either by holding a transaction handle or holding
1837 * some lock, while it's doing searches through a commit root.
1838 * At the moment it's only used for send operations.
1839 */
1841 {
1863 }
1870 {
1871 /*
1872 * If a previous call to btrfs_bin_search() on a parent node returned an
1873 * exact match (prev_cmp == 0), we can safely assume the target key will
1874 * always be at slot 0 on lower levels, since each key pointer
1875 * (struct btrfs_key_ptr) refers to the lowest key accessible from the
1876 * subtree it points to. Thus we can skip searching lower levels.
1877 */
1881 }
1884 }
1892 {
1899 /*
1900 * If we are doing an insertion, the leaf has enough free space and the
1901 * destination slot for the key is not slot 0, then we can unlock our
1902 * write lock on the parent, and any other upper nodes, before doing the
1903 * binary search on the leaf (with search_for_key_slot()), allowing other
1904 * tasks to lock the parent and any other upper nodes.
1905 */
1907 /*
1908 * Cache the leaf free space, since we will need it later and it
1909 * will not change until then.
1910 */
1913 /*
1914 * !path->locks[1] means we have a single node tree, the leaf is
1915 * the root of the tree.
1916 */
1923 /*
1924 * Doing the extra comparison with the first key is cheap,
1925 * taking into account that the first key is very likely
1926 * already in a cache line because it immediately follows
1927 * the extent buffer's header and we have recently accessed
1928 * the header's level field.
1929 */
1932 /*
1933 * The first key is smaller than the key we want
1934 * to insert, so we are safe to unlock all upper
1935 * nodes and we have to do the binary search.
1936 *
1937 * We do use btrfs_unlock_up_safe() and not
1938 * unlock_up() because the later does not unlock
1939 * nodes with a slot of 0 - we can safely unlock
1940 * any node even if its slot is 0 since in this
1941 * case the key does not end up at slot 0 of the
1942 * leaf and there's no need to split the leaf.
1943 */
1947 /*
1948 * The first key is >= then the key we want to
1949 * insert, so we can skip the binary search as
1950 * the target key will be at slot 0.
1951 *
1952 * We can not unlock upper nodes when the key is
1953 * less than the first key, because we will need
1954 * to update the key at slot 0 of the parent node
1955 * and possibly of other upper nodes too.
1956 * If the key matches the first key, then we can
1957 * unlock all the upper nodes, using
1958 * btrfs_unlock_up_safe() instead of unlock_up()
1959 * as stated above.
1960 */
1963 /*
1964 * ret is already 0 or 1, matching the result of
1965 * a btrfs_bin_search() call, so there is no need
1966 * to adjust it.
1967 */
1970 }
1971 }
1972 }
1979 }
1982 /*
1983 * Item key already exists. In this case, if we are allowed to
1984 * insert the item (for example, in dir_item case, item key
1985 * collision is allowed), it will be merged with the original
1986 * item. Only the item size grows, no new btrfs item will be
1987 * added. If search_for_extension is not set, ins_len already
1988 * accounts the size btrfs_item, deduct it here so leaf space
1989 * check will be correct.
1990 */
1994 }
2008 }
2009 }
2012 }
2014 /*
2015 * Look for a key in a tree and perform necessary modifications to preserve
2016 * tree invariants.
2017 *
2018 * @trans: Handle of transaction, used when modifying the tree
2019 * @p: Holds all btree nodes along the search path
2020 * @root: The root node of the tree
2021 * @key: The key we are looking for
2022 * @ins_len: Indicates purpose of search:
2023 * >0 for inserts it's size of item inserted (*)
2024 * <0 for deletions
2025 * 0 for plain searches, not modifying the tree
2026 *
2027 * (*) If size of item inserted doesn't include
2028 * sizeof(struct btrfs_item), then p->search_for_extension must
2029 * be set.
2030 * @cow: boolean should CoW operations be performed. Must always be 1
2031 * when modifying the tree.
2032 *
2033 * If @ins_len > 0, nodes and leaves will be split as we walk down the tree.
2034 * If @ins_len < 0, nodes will be merged as we walk down the tree (if possible)
2035 *
2036 * If @key is found, 0 is returned and you can find the item in the leaf level
2037 * of the path (level 0)
2038 *
2039 * If @key isn't found, 1 is returned and the leaf level of the path (level 0)
2040 * points to the slot where it should be inserted
2041 *
2042 * If an error is encountered while searching the tree a negative error number
2043 * is returned
2044 */
2048 {
2056 /* everything at write_lock_level or lower must be write locked */
2073 /*
2074 * For now only allow nowait for read only operations. There's no
2075 * strict reason why we can't, we just only need it for reads so it's
2076 * only implemented for reads.
2077 */
2083 /* when we are removing items, we might have to go up to level
2084 * two as we update tree pointers Make sure we keep write
2085 * for those levels as well
2086 */
2089 /*
2090 * for inserting items, make sure we have a write lock on
2091 * level 1 so we can update keys
2092 */
2094 }
2111 }
2112 }
2114 again:
2120 }
2130 /*
2131 * if we don't really need to cow this block
2132 * then we don't want to set the path blocking,
2133 * so we test it here
2134 */
2138 /*
2139 * must have write locks on this node and the
2140 * parent
2141 */
2149 }
2154 BTRFS_NESTING_COW);
2155 else
2159 BTRFS_NESTING_COW);
2163 }
2164 }
2165 cow_done:
2168 /*
2169 * we have a lock on b and as long as we aren't changing
2170 * the tree, there is no way to for the items in b to change.
2171 * It is safe to drop the lock on our parent before we
2172 * go through the expensive btree search on b.
2173 *
2174 * If we're inserting or deleting (ins_len != 0), then we might
2175 * be changing slot zero, which may require changing the parent.
2176 * So, we can't drop the lock until after we know which slot
2177 * we're operating on.
2178 */
2185 }
2186 }
2197 }
2206 slot--;
2207 }
2216 }
2220 /*
2221 * Slot 0 is special, if we change the key we have to update
2222 * the parent pointer which means we must have a write lock on
2223 * the parent
2224 */
2229 }
2238 }
2246 }
2262 }
2265 }
2267 }
2269 }
2270 }
2272 done:
2283 }
2286 }
2289 /*
2290 * Like btrfs_search_slot, this looks for a key in the given tree. It uses the
2291 * current state of the tree together with the operations recorded in the tree
2292 * modification log to search for the key in a previous version of this tree, as
2293 * denoted by the time_seq parameter.
2294 *
2295 * Naturally, there is no support for insert, delete or cow operations.
2296 *
2297 * The resulting path and return value will be set up as if we called
2298 * btrfs_search_slot at that point in time with ins_len and cow both set to 0.
2299 */
2302 {
2319 }
2321 again:
2326 }
2336 /*
2337 * we have a lock on b and as long as we aren't changing
2338 * the tree, there is no way to for the items in b to change.
2339 * It is safe to drop the lock on our parent before we
2340 * go through the expensive btree search on b.
2341 */
2352 }
2356 slot--;
2357 }
2365 }
2373 }
2381 }
2384 }
2386 done:
2391 }
2393 /*
2394 * Search the tree again to find a leaf with smaller keys.
2395 * Returns 0 if it found something.
2396 * Returns 1 if there are no smaller keys.
2397 * Returns < 0 on error.
2398 *
2399 * This may release the path, and so you may lose any locks held at the
2400 * time you call it.
2401 */
2403 {
2423 }
2430 /*
2431 * Previous key not found. Even if we were at slot 0 of the leaf we had
2432 * before releasing the path and calling btrfs_search_slot(), we now may
2433 * be in a slot pointing to the same original key - this can happen if
2434 * after we released the path, one of more items were moved from a
2435 * sibling leaf into the front of the leaf we had due to an insertion
2436 * (see push_leaf_right()).
2437 * If we hit this case and our slot is > 0 and just decrement the slot
2438 * so that the caller does not process the same key again, which may or
2439 * may not break the caller, depending on its logic.
2440 */
2448 }
2449 /*
2450 * At slot 0, same key as before, it means orig_key is
2451 * the lowest, leftmost, key in the tree. We're done.
2452 */
2454 }
2455 }
2459 /*
2460 * We might have had an item with the previous key in the tree right
2461 * before we released our path. And after we released our path, that
2462 * item might have been pushed to the first slot (0) of the leaf we
2463 * were holding due to a tree balance. Alternatively, an item with the
2464 * previous key can exist as the only element of a leaf (big fat item).
2465 * Therefore account for these 2 cases, so that our callers (like
2466 * btrfs_previous_item) don't miss an existing item with a key matching
2467 * the previous key we computed above.
2468 */
2472 }
2474 /*
2475 * helper to use instead of search slot if no exact match is needed but
2476 * instead the next or previous item should be returned.
2477 * When find_higher is true, the next higher item is returned, the next lower
2478 * otherwise.
2479 * When return_any and find_higher are both true, and no higher item is found,
2480 * return the next lower instead.
2481 * When return_any is true and find_higher is false, and no lower item is found,
2482 * return the next higher instead.
2483 * It returns 0 if any item is found, 1 if none is found (tree empty), and
2484 * < 0 on error
2485 */
2490 {
2494 again:
2498 /*
2499 * a return value of 1 means the path is at the position where the
2500 * item should be inserted. Normally this is the next bigger item,
2501 * but in case the previous item is the last in a leaf, path points
2502 * to the first free slot in the previous leaf, i.e. at an invalid
2503 * item.
2504 */
2514 /*
2515 * no higher item found, return the next
2516 * lower instead
2517 */
2522 }
2533 }
2536 /*
2537 * no lower item found, return the next
2538 * higher instead
2539 */
2546 }
2547 }
2549 }
2551 /*
2552 * Execute search and call btrfs_previous_item to traverse backwards if the item
2553 * was not found.
2554 *
2555 * Return 0 if found, 1 if not found and < 0 if error.
2556 */
2559 {
2570 }
2572 /*
2573 * Search for a valid slot for the given path.
2574 *
2575 * @root: The root node of the tree.
2576 * @key: Will contain a valid item if found.
2577 * @path: The starting point to validate the slot.
2578 *
2579 * Return: 0 if the item is valid
2580 * 1 if not found
2581 * <0 if error.
2582 */
2585 {
2592 }
2596 }
2598 /*
2599 * adjust the pointers going up the tree, starting at level
2600 * making sure the right key of each node is points to 'key'.
2601 * This is used after shifting pointers to the left, so it stops
2602 * fixing up pointers when a given leaf/node is not in slot 0 of the
2603 * higher levels
2604 *
2605 */
2609 {
2621 BTRFS_MOD_LOG_KEY_REPLACE);
2627 }
2628 }
2630 /*
2631 * update item key.
2632 *
2633 * This function isn't completely safe. It's the caller's responsibility
2634 * that the new key won't break the order
2635 */
2639 {
2659 }
2660 }
2673 }
2674 }
2681 }
2683 /*
2684 * Check key order of two sibling extent buffers.
2685 *
2686 * Return true if something is wrong.
2687 * Return false if everything is fine.
2688 *
2689 * Tree-checker only works inside one tree block, thus the following
2690 * corruption can not be detected by tree-checker:
2691 *
2692 * Leaf @left | Leaf @right
2693 * --------------------------------------------------------------
2694 * | 1 | 2 | 3 | 4 | 5 | f6 | | 7 | 8 |
2695 *
2696 * Key f6 in leaf @left itself is valid, but not valid when the next
2697 * key in leaf @right is 7.
2698 * This can only be checked at tree block merge time.
2699 * And since tree checker has ensured all key order in each tree block
2700 * is correct, we only need to bother the last key of @left and the first
2701 * key of @right.
2702 */
2705 {
2712 /* No key to check in one of the tree blocks */
2722 }
2735 }
2737 }
2739 /*
2740 * try to push data from one node into the next node left in the
2741 * tree.
2742 *
2743 * returns 0 if some ptrs were pushed left, < 0 if there was some horrible
2744 * error, and > 0 if there was no room in the left hand block.
2745 */
2749 {
2771 /* leave at least 8 pointers in the node if
2772 * we aren't going to empty it
2773 */
2778 }
2779 }
2783 /* dst is the left eb, src is the middle eb */
2788 }
2793 }
2800 /*
2801 * btrfs_tree_mod_log_eb_copy handles logging the move, so we
2802 * don't need to do an explicit tree mod log operation for it.
2803 */
2808 }
2815 }
2817 /*
2818 * try to push data from one node into the next node right in the
2819 * tree.
2820 *
2821 * returns 0 if some ptrs were pushed, < 0 if there was some horrible
2822 * error, and > 0 if there was no room in the right hand block.
2823 *
2824 * this will only push up to 1/2 the contents of the left node over
2825 */
2829 {
2850 /* don't try to empty the node */
2857 /* dst is the right eb, src is the middle eb */
2862 }
2864 /*
2865 * btrfs_tree_mod_log_eb_copy handles logging the move, so we don't
2866 * need to do an explicit tree mod log operation for it.
2867 */
2874 push_items);
2878 }
2891 }
2893 /*
2894 * helper function to insert a new root level in the tree.
2895 * A new node is allocated, and a single item is inserted to
2896 * point to the existing root
2897 *
2898 * returns zero on success or < 0 on failure.
2899 */
2903 {
2904 u64 lower_gen;
2917 else
2949 }
2952 /* the super has an extra ref to root->node */
2961 }
2963 /*
2964 * worker function to insert a single pointer in a node.
2965 * the node should have enough room for the pointer already
2966 *
2967 * slot and level indicate where you want the key to go, and
2968 * blocknr is the block the key points to.
2969 */
2974 {
2992 }
2993 }
2998 }
3001 BTRFS_MOD_LOG_KEY_ADD);
3005 }
3006 }
3015 }
3017 /*
3018 * split the node at the specified level in path in two.
3019 * The path is corrected to point to the appropriate node after the split
3020 *
3021 * Before splitting this tries to make some room in the node by pushing
3022 * left and right, if either one works, it returns right away.
3023 *
3024 * returns 0 on success and < 0 on failure
3025 */
3029 {
3036 u32 c_nritems;
3041 /*
3042 * trying to split the root, lets make a new one
3043 *
3044 * tree mod log: We don't log_removal old root in
3045 * insert_new_root, because that root buffer will be kept as a
3046 * normal node. We are going to log removal of half of the
3047 * elements below with btrfs_tree_mod_log_eb_copy(). We're
3048 * holding a tree lock on the buffer, which is why we cannot
3049 * race with other tree_mod_log users.
3050 */
3062 }
3083 }
3100 }
3111 }
3113 }
3115 /*
3116 * how many bytes are required to store the items in a leaf. start
3117 * and nr indicate which items in the leaf to check. This totals up the
3118 * space used both by the item structs and the item data
3119 */
3121 {
3133 }
3135 /*
3136 * The space between the end of the leaf items and
3137 * the start of the leaf data. IOW, how much room
3138 * the leaf has left for both items and data
3139 */
3141 {
3150 ret,
3153 }
3155 }
3157 /*
3158 * min slot controls the lowest index we're willing to push to the
3159 * right. We'll push up to and including min_slot, but no lower
3160 */
3166 u32 min_slot)
3167 {
3174 u32 i;
3177 u32 nr;
3178 u32 right_nritems;
3179 u32 data_end;
3180 u32 this_item_size;
3184 else
3201 }
3202 }
3212 push_items++;
3216 i--;
3217 }
3224 /* push left to right */
3230 /* make room in the right data area */
3235 /* copy from the left data area */
3241 /* copy the items from left to right */
3244 /* update the item pointers */
3252 }
3259 else
3268 /* then fixup the leaf pointer in the path */
3280 }
3283 out_unlock:
3287 }
3289 /*
3290 * push some data in the path leaf to the right, trying to free up at
3291 * least data_size bytes. returns zero if the push worked, nonzero otherwise
3292 *
3293 * returns 1 if the push failed because the other node didn't have enough
3294 * room, 0 if everything worked out and < 0 if there were major errors.
3295 *
3296 * this will push starting from min_slot to the end of the leaf. It won't
3297 * push any slot lower than min_slot
3298 */
3303 {
3309 u32 left_nritems;
3347 }
3349 /* Key greater than all keys in the leaf, right neighbor has
3350 * enough room for it and we're not emptying our leaf to delete
3351 * it, therefore use right neighbor to insert the new item and
3352 * no need to touch/dirty our left leaf. */
3359 }
3363 out_unlock:
3367 }
3369 /*
3370 * push some data in the path leaf to the left, trying to free up at
3371 * least data_size bytes. returns zero if the push worked, nonzero otherwise
3372 *
3373 * max_slot can put a limit on how far into the leaf we'll push items. The
3374 * item at 'max_slot' won't be touched. Use (u32)-1 to make us do all the
3375 * items
3376 */
3381 u32 max_slot)
3382 {
3389 u32 old_left_nritems;
3390 u32 nr;
3392 u32 this_item_size;
3393 u32 old_left_item_size;
3398 else
3410 }
3411 }
3418 free_space)
3421 push_items++;
3423 }
3428 }
3431 /* push data from right to left */
3445 u32 ioff;
3450 }
3453 /* fixup right node */
3456 right_nritems);
3467 }
3476 }
3481 else
3487 /* then fixup the leaf pointer in the path */
3498 }
3501 out:
3505 }
3507 /*
3508 * push some data in the path leaf to the left, trying to free up at
3509 * least data_size bytes. returns zero if the push worked, nonzero otherwise
3510 *
3511 * max_slot can put a limit on how far into the leaf we'll push items. The
3512 * item at 'max_slot' won't be touched. Use (u32)-1 to make us push all the
3513 * items
3514 */
3518 {
3523 u32 right_nritems;
3548 }
3552 BTRFS_NESTING_LEFT_COW);
3554 /* we hit -ENOSPC, but it isn't fatal here */
3558 }
3564 }
3567 out:
3571 }
3573 /*
3574 * split the path's leaf in two, making sure there is at least data_size
3575 * available for the resulting leaf level of the path.
3576 */
3582 {
3604 u32 ioff;
3608 }
3629 }
3634 }
3636 /*
3637 * double splits happen when we need to insert a big item in the middle
3638 * of a leaf. A double split can leave us with 3 mostly empty leaves:
3639 * leaf: [ slots 0 - N] [ our target ] [ N + 1 - total in leaf ]
3640 * A B C
3641 *
3642 * We avoid this by trying to push the items on either side of our target
3643 * into the adjacent leaves. If all goes well we can avoid the double split
3644 * completely.
3645 */
3650 {
3654 u32 nritems;
3661 /*
3662 * try to push all the items after our slot into the
3663 * right leaf
3664 */
3670 progress++;
3673 /*
3674 * our goal is to get our slot at the start or end of a leaf. If
3675 * we've done so we're done
3676 */
3683 /* try to push all the items before our slot into the next leaf */
3693 progress++;
3698 }
3700 /*
3701 * split the path's leaf in two, making sure there is at least data_size
3702 * available for the resulting leaf level of the path.
3703 *
3704 * returns 0 if all went well and < 0 on failure.
3705 */
3711 {
3714 u32 nritems;
3731 /* first try to make some room by pushing left and right */
3750 }
3753 /* did the pushes work? */
3756 }
3762 }
3763 again:
3784 }
3785 }
3786 }
3802 }
3803 }
3804 }
3805 }
3809 else
3812 /*
3813 * We have to about BTRFS_NESTING_NEW_ROOT here if we've done a double
3814 * split, because we're only allowed to have MAX_LOCKDEP_SUBCLASSES
3815 * subclasses, which is 8 at the time of this patch, and we've maxed it
3816 * out. In the future we could add a
3817 * BTRFS_NESTING_SPLIT_THE_SPLITTENING if we need to, but for now just
3818 * use BTRFS_NESTING_NEW_ROOT.
3819 */
3823 BTRFS_NESTING_SPLIT);
3838 }
3852 }
3859 }
3860 /*
3861 * We create a new leaf 'right' for the required ins_len and
3862 * we'll do btrfs_mark_buffer_dirty() on this leaf after copying
3863 * the content of ins_len to 'right'.
3864 */
3866 }
3873 }
3877 num_doubles++;
3879 }
3883 push_for_double:
3889 }
3894 {
3899 u32 item_size;
3916 }
3930 /* if our item isn't there, return now */
3934 /* the leaf has changed, it now has room. return now */
3943 }
3952 err:
3955 }
3961 {
3965 u32 nritems;
3966 u32 item_size;
3967 u32 orig_offset;
3971 /*
3972 * Shouldn't happen because the caller must have previously called
3973 * setup_leaf_for_split() to make room for the new item in the leaf.
3974 */
3992 /* shift the items */
3994 }
4008 /* write the data for the start of the original item */
4011 split_offset);
4013 /* write the data for the new item */
4022 }
4024 /*
4025 * This function splits a single item into two items,
4026 * giving 'new_key' to the new item and splitting the
4027 * old one at split_offset (from the start of the item).
4028 *
4029 * The path may be released by this operation. After
4030 * the split, the path is pointing to the old item. The
4031 * new item is going to be in the same node as the old one.
4032 *
4033 * Note, the item being split must be smaller enough to live alone on
4034 * a tree block with room for one extra struct btrfs_item
4035 *
4036 * This allows us to split the item in place, keeping a lock on the
4037 * leaf the entire time.
4038 */
4044 {
4053 }
4055 /*
4056 * make the item pointed to by the path smaller. new_size indicates
4057 * how small to make it, and from_end tells us if we just chop bytes
4058 * off the end of the item or if we shift the item to chop bytes off
4059 * the front.
4060 */
4063 {
4066 u32 nritems;
4091 /*
4092 * item0..itemN ... dataN.offset..dataN.size .. data0.size
4093 */
4094 /* first correct the data pointers */
4097 u32 ioff;
4101 }
4103 /* shift the data */
4109 u64 offset;
4123 BTRFS_FILE_EXTENT_INLINE) {
4127 BTRFS_FILE_EXTENT_INLINE_DATA_START);
4128 }
4129 }
4139 }
4147 }
4148 }
4150 /*
4151 * make the item pointed to by the path bigger, data_size is the added size.
4152 */
4155 {
4158 u32 nritems;
4173 }
4183 }
4185 /*
4186 * item0..itemN ... dataN.offset..dataN.size .. data0.size
4187 */
4188 /* first correct the data pointers */
4191 u32 ioff;
4195 }
4197 /* shift the data */
4209 }
4210 }
4212 /*
4213 * Make space in the node before inserting one or more items.
4214 *
4215 * @trans: transaction handle
4216 * @root: root we are inserting items to
4217 * @path: points to the leaf/slot where we are going to insert new items
4218 * @batch: information about the batch of items to insert
4219 *
4220 * Main purpose is to save stack depth by doing the bulk of the work in a
4221 * function that doesn't call btrfs_search_slot
4222 */
4226 {
4229 u32 nritems;
4235 u32 total_size;
4237 /*
4238 * Before anything else, update keys in the parent and other ancestors
4239 * if needed, then release the write locks on them, so that other tasks
4240 * can use them while we modify the leaf.
4241 */
4245 }
4260 }
4272 }
4273 /*
4274 * item0..itemN ... dataN.offset..dataN.size .. data0.size
4275 */
4276 /* first correct the data pointers */
4278 u32 ioff;
4283 }
4284 /* shift the items */
4287 /* shift the data */
4291 }
4293 /* setup the item for the new data */
4300 }
4308 }
4309 }
4311 /*
4312 * Insert a new item into a leaf.
4313 *
4314 * @trans: Transaction handle.
4315 * @root: The root of the btree.
4316 * @path: A path pointing to the target leaf and slot.
4317 * @key: The key of the new item.
4318 * @data_size: The size of the data associated with the new key.
4319 */
4324 u32 data_size)
4325 {
4334 }
4336 /*
4337 * Given a key and some data, insert items into the tree.
4338 * This does all the path init required, making room in the tree if needed.
4339 *
4340 * Returns: 0 on success
4341 * -EEXIST if the first key already exists
4342 * < 0 on other errors
4343 */
4348 {
4351 u32 total_size;
4365 }
4367 /*
4368 * Given a key and some data, insert an item into the tree.
4369 * This does all the path init required, making room in the tree if needed.
4370 */
4373 u32 data_size)
4374 {
4389 }
4392 }
4394 /*
4395 * This function duplicates an item, giving 'new_key' to the new item.
4396 * It guarantees both items live in the same tree leaf and the new item is
4397 * contiguous with the original item.
4398 *
4399 * This allows us to split a file extent in place, keeping a lock on the leaf
4400 * the entire time.
4401 */
4406 {
4409 u32 item_size;
4424 item_size);
4426 }
4428 /*
4429 * delete the pointer from a given node.
4430 *
4431 * the tree should have been previously balanced so the deletion does not
4432 * empty a node.
4433 *
4434 * This is exported for use inside btrfs-progs, don't un-export it.
4435 */
4438 {
4440 u32 nritems;
4451 }
4452 }
4460 BTRFS_MOD_LOG_KEY_REMOVE);
4464 }
4465 }
4467 nritems--;
4471 /* just turn the root into a leaf and break */
4478 }
4481 }
4483 /*
4484 * a helper function to delete the leaf pointed to by path->slots[1] and
4485 * path->nodes[1].
4486 *
4487 * This deletes the pointer in path->nodes[1] and frees the leaf
4488 * block extent. zero is returned if it all worked out, < 0 otherwise.
4489 *
4490 * The path must have already been setup for deleting the leaf, including
4491 * all the proper balancing. path->nodes[1] must be locked.
4492 */
4497 {
4505 /*
4506 * btrfs_free_extent is expensive, we want to make sure we
4507 * aren't holding any locks when we call it
4508 */
4520 }
4521 /*
4522 * delete the item at the leaf level in path. If that empties
4523 * the leaf, remove it from the tree
4524 */
4527 {
4532 u32 nritems;
4552 u32 ioff;
4556 }
4559 }
4563 /* delete the leaf if we've emptied it */
4572 }
4580 }
4582 /*
4583 * Try to delete the leaf if it is mostly empty. We do this by
4584 * trying to move all its items into its left and right neighbours.
4585 * If we can't move all the items, then we don't delete it - it's
4586 * not ideal, but future insertions might fill the leaf with more
4587 * items, or items from other leaves might be moved later into our
4588 * leaf due to deletions on those leaves.
4589 */
4591 u32 min_push_space;
4593 /* push_leaf_left fixes the path.
4594 * make sure the path still points to our leaf
4595 * for possible call to btrfs_del_ptr below
4596 */
4599 /*
4600 * We want to be able to at least push one item to the
4601 * left neighbour leaf, and that's the first item.
4602 */
4612 /*
4613 * If we were not able to push all items from our
4614 * leaf to its left neighbour, then attempt to
4615 * either push all the remaining items to the
4616 * right neighbour or none. There's no advantage
4617 * in pushing only some items, instead of all, as
4618 * it's pointless to end up with a leaf having
4619 * too few items while the neighbours can be full
4620 * or nearly full.
4621 */
4628 }
4638 /* if we're still in the path, make sure
4639 * we're dirty. Otherwise, one of the
4640 * push_leaf functions must have already
4641 * dirtied this buffer
4642 */
4646 }
4649 }
4650 }
4652 }
4654 /*
4655 * A helper function to walk down the tree starting at min_key, and looking
4656 * for nodes or leaves that are have a minimum transaction id.
4657 * This is used by the btree defrag code, and tree logging
4658 *
4659 * This does not cow, but it does stuff the starting key it finds back
4660 * into min_key, so you can call btrfs_search_slot with cow=1 on the
4661 * key and get a writable path.
4662 *
4663 * This honors path->lowest_level to prevent descent past a given level
4664 * of the tree.
4665 *
4666 * min_trans indicates the oldest transaction that you are interested
4667 * in walking through. Any nodes or leaves older than min_trans are
4668 * skipped over (without reading them).
4669 *
4670 * returns zero if something useful was found, < 0 on error and 1 if there
4671 * was nothing in the tree that matched the search criteria.
4672 */
4675 u64 min_trans)
4676 {
4681 u32 nritems;
4688 again:
4698 }
4706 }
4708 /* at the lowest level, we're done, setup the path and exit */
4716 }
4718 slot--;
4719 /*
4720 * check this node pointer against the min_trans parameters.
4721 * If it is too old, skip to the next one.
4722 */
4724 u64 gen;
4728 slot++;
4730 }
4732 }
4733 find_next_key:
4734 /*
4735 * we didn't find a candidate key in this node, walk forward
4736 * and find another one
4737 */
4741 min_trans);
4747 }
4748 }
4749 /* save our key for returning back */
4755 }
4760 }
4767 }
4768 out:
4773 }
4775 }
4777 /*
4778 * this is similar to btrfs_next_leaf, but does not try to preserve
4779 * and fixup the path. It looks for and returns the next key in the
4780 * tree based on the current path and the min_trans parameters.
4781 *
4782 * 0 is returned if another key is found, < 0 if there are any errors
4783 * and 1 is returned if there are no higher keys in the tree
4784 *
4785 * path->keep_locks should be set to 1 on the search made before
4786 * calling this function.
4787 */
4790 {
4801 next:
4811 level++;
4813 }
4818 else
4833 slot++;
4835 }
4843 slot++;
4845 }
4847 }
4849 }
4851 }
4854 u64 time_seq)
4855 {
4863 u32 nritems;
4867 /*
4868 * The nowait semantics are used only for write paths, where we don't
4869 * use the tree mod log and sequence numbers.
4870 */
4879 again:
4896 }
4899 }
4900 }
4902 }
4909 /*
4910 * by releasing the path above we dropped all our locks. A balance
4911 * could have added more items next to the key that used to be
4912 * at the very end of the block. So, check again here and
4913 * advance the path if there are now more items available.
4914 */
4920 }
4921 /*
4922 * So the above check misses one case:
4923 * - after releasing the path above, someone has removed the item that
4924 * used to be at the very end of the block, and balance between leafs
4925 * gets another one with bigger key.offset to replace it.
4926 *
4927 * This one should be returned as well, or we can get leaf corruption
4928 * later(esp. in __btrfs_drop_extents()).
4929 *
4930 * And a bit more explanation about this check,
4931 * with ret > 0, the key isn't found, the path points to the slot
4932 * where it should be inserted, so the path->slots[0] item must be the
4933 * bigger one.
4934 */
4938 }
4944 }
4949 level++;
4953 }
4955 }
4958 /*
4959 * Our current level is where we're going to start from, and to
4960 * make sure lockdep doesn't complain we need to drop our locks
4961 * and nodes from 0 to our current level.
4962 */
4967 }
4970 }
4980 }
4987 }
4989 /*
4990 * If we don't get the lock, we may be racing
4991 * with push_leaf_left, holding that lock while
4992 * itself waiting for the leaf we've currently
4993 * locked. To solve this situation, we give up
4994 * on our lock and cycle.
4995 */
5000 }
5003 }
5005 }
5008 level--;
5023 }
5030 }
5033 }
5034 }
5035 }
5037 done:
5047 }
5050 }
5053 {
5058 }
5060 /*
5061 * this uses btrfs_prev_leaf to walk backwards in the tree, and keeps
5062 * searching until it gets past min_objectid or finds an item of 'type'
5063 *
5064 * returns 0 if something is found, 1 if nothing was found and < 0 on error
5065 */
5069 {
5072 u32 nritems;
5082 }
5098 }
5100 }
5102 /*
5103 * search in extent tree to find a previous Metadata/Data extent item with
5104 * min objecitd.
5105 *
5106 * returns 0 if something is found, 1 if nothing was found and < 0 on error
5107 */
5110 {
5113 u32 nritems;
5123 }
5140 }
5142 }
5145 {
5150 }
5153 {
5155 }