aboutsummaryrefslogtreecommitdiffstats
path: root/fs/btrfs/ctree.c
diff options
context:
space:
mode:
Diffstat (limited to 'fs/btrfs/ctree.c')
-rw-r--r--fs/btrfs/ctree.c900
1 files changed, 513 insertions, 387 deletions
diff --git a/fs/btrfs/ctree.c b/fs/btrfs/ctree.c
index 37f31b5529aa..e5b2533b691a 100644
--- a/fs/btrfs/ctree.c
+++ b/fs/btrfs/ctree.c
@@ -254,18 +254,13 @@ int btrfs_copy_root(struct btrfs_trans_handle *trans,
254 * empty_size -- a hint that you plan on doing more cow. This is the size in 254 * empty_size -- a hint that you plan on doing more cow. This is the size in
255 * bytes the allocator should try to find free next to the block it returns. 255 * bytes the allocator should try to find free next to the block it returns.
256 * This is just a hint and may be ignored by the allocator. 256 * This is just a hint and may be ignored by the allocator.
257 *
258 * prealloc_dest -- if you have already reserved a destination for the cow,
259 * this uses that block instead of allocating a new one.
260 * btrfs_alloc_reserved_extent is used to finish the allocation.
261 */ 257 */
262static noinline int __btrfs_cow_block(struct btrfs_trans_handle *trans, 258static noinline int __btrfs_cow_block(struct btrfs_trans_handle *trans,
263 struct btrfs_root *root, 259 struct btrfs_root *root,
264 struct extent_buffer *buf, 260 struct extent_buffer *buf,
265 struct extent_buffer *parent, int parent_slot, 261 struct extent_buffer *parent, int parent_slot,
266 struct extent_buffer **cow_ret, 262 struct extent_buffer **cow_ret,
267 u64 search_start, u64 empty_size, 263 u64 search_start, u64 empty_size)
268 u64 prealloc_dest)
269{ 264{
270 u64 parent_start; 265 u64 parent_start;
271 struct extent_buffer *cow; 266 struct extent_buffer *cow;
@@ -291,26 +286,10 @@ static noinline int __btrfs_cow_block(struct btrfs_trans_handle *trans,
291 level = btrfs_header_level(buf); 286 level = btrfs_header_level(buf);
292 nritems = btrfs_header_nritems(buf); 287 nritems = btrfs_header_nritems(buf);
293 288
294 if (prealloc_dest) { 289 cow = btrfs_alloc_free_block(trans, root, buf->len,
295 struct btrfs_key ins; 290 parent_start, root->root_key.objectid,
296 291 trans->transid, level,
297 ins.objectid = prealloc_dest; 292 search_start, empty_size);
298 ins.offset = buf->len;
299 ins.type = BTRFS_EXTENT_ITEM_KEY;
300
301 ret = btrfs_alloc_reserved_extent(trans, root, parent_start,
302 root->root_key.objectid,
303 trans->transid, level, &ins);
304 BUG_ON(ret);
305 cow = btrfs_init_new_buffer(trans, root, prealloc_dest,
306 buf->len, level);
307 } else {
308 cow = btrfs_alloc_free_block(trans, root, buf->len,
309 parent_start,
310 root->root_key.objectid,
311 trans->transid, level,
312 search_start, empty_size);
313 }
314 if (IS_ERR(cow)) 293 if (IS_ERR(cow))
315 return PTR_ERR(cow); 294 return PTR_ERR(cow);
316 295
@@ -413,7 +392,7 @@ static noinline int __btrfs_cow_block(struct btrfs_trans_handle *trans,
413noinline int btrfs_cow_block(struct btrfs_trans_handle *trans, 392noinline int btrfs_cow_block(struct btrfs_trans_handle *trans,
414 struct btrfs_root *root, struct extent_buffer *buf, 393 struct btrfs_root *root, struct extent_buffer *buf,
415 struct extent_buffer *parent, int parent_slot, 394 struct extent_buffer *parent, int parent_slot,
416 struct extent_buffer **cow_ret, u64 prealloc_dest) 395 struct extent_buffer **cow_ret)
417{ 396{
418 u64 search_start; 397 u64 search_start;
419 int ret; 398 int ret;
@@ -436,7 +415,6 @@ noinline int btrfs_cow_block(struct btrfs_trans_handle *trans,
436 btrfs_header_owner(buf) == root->root_key.objectid && 415 btrfs_header_owner(buf) == root->root_key.objectid &&
437 !btrfs_header_flag(buf, BTRFS_HEADER_FLAG_WRITTEN)) { 416 !btrfs_header_flag(buf, BTRFS_HEADER_FLAG_WRITTEN)) {
438 *cow_ret = buf; 417 *cow_ret = buf;
439 WARN_ON(prealloc_dest);
440 return 0; 418 return 0;
441 } 419 }
442 420
@@ -447,8 +425,7 @@ noinline int btrfs_cow_block(struct btrfs_trans_handle *trans,
447 btrfs_set_lock_blocking(buf); 425 btrfs_set_lock_blocking(buf);
448 426
449 ret = __btrfs_cow_block(trans, root, buf, parent, 427 ret = __btrfs_cow_block(trans, root, buf, parent,
450 parent_slot, cow_ret, search_start, 0, 428 parent_slot, cow_ret, search_start, 0);
451 prealloc_dest);
452 return ret; 429 return ret;
453} 430}
454 431
@@ -617,7 +594,7 @@ int btrfs_realloc_node(struct btrfs_trans_handle *trans,
617 err = __btrfs_cow_block(trans, root, cur, parent, i, 594 err = __btrfs_cow_block(trans, root, cur, parent, i,
618 &cur, search_start, 595 &cur, search_start,
619 min(16 * blocksize, 596 min(16 * blocksize,
620 (end_slot - i) * blocksize), 0); 597 (end_slot - i) * blocksize));
621 if (err) { 598 if (err) {
622 btrfs_tree_unlock(cur); 599 btrfs_tree_unlock(cur);
623 free_extent_buffer(cur); 600 free_extent_buffer(cur);
@@ -937,7 +914,7 @@ static noinline int balance_level(struct btrfs_trans_handle *trans,
937 BUG_ON(!child); 914 BUG_ON(!child);
938 btrfs_tree_lock(child); 915 btrfs_tree_lock(child);
939 btrfs_set_lock_blocking(child); 916 btrfs_set_lock_blocking(child);
940 ret = btrfs_cow_block(trans, root, child, mid, 0, &child, 0); 917 ret = btrfs_cow_block(trans, root, child, mid, 0, &child);
941 BUG_ON(ret); 918 BUG_ON(ret);
942 919
943 spin_lock(&root->node_lock); 920 spin_lock(&root->node_lock);
@@ -945,6 +922,7 @@ static noinline int balance_level(struct btrfs_trans_handle *trans,
945 spin_unlock(&root->node_lock); 922 spin_unlock(&root->node_lock);
946 923
947 ret = btrfs_update_extent_ref(trans, root, child->start, 924 ret = btrfs_update_extent_ref(trans, root, child->start,
925 child->len,
948 mid->start, child->start, 926 mid->start, child->start,
949 root->root_key.objectid, 927 root->root_key.objectid,
950 trans->transid, level - 1); 928 trans->transid, level - 1);
@@ -971,6 +949,10 @@ static noinline int balance_level(struct btrfs_trans_handle *trans,
971 BTRFS_NODEPTRS_PER_BLOCK(root) / 4) 949 BTRFS_NODEPTRS_PER_BLOCK(root) / 4)
972 return 0; 950 return 0;
973 951
952 if (trans->transaction->delayed_refs.flushing &&
953 btrfs_header_nritems(mid) > 2)
954 return 0;
955
974 if (btrfs_header_nritems(mid) < 2) 956 if (btrfs_header_nritems(mid) < 2)
975 err_on_enospc = 1; 957 err_on_enospc = 1;
976 958
@@ -979,7 +961,7 @@ static noinline int balance_level(struct btrfs_trans_handle *trans,
979 btrfs_tree_lock(left); 961 btrfs_tree_lock(left);
980 btrfs_set_lock_blocking(left); 962 btrfs_set_lock_blocking(left);
981 wret = btrfs_cow_block(trans, root, left, 963 wret = btrfs_cow_block(trans, root, left,
982 parent, pslot - 1, &left, 0); 964 parent, pslot - 1, &left);
983 if (wret) { 965 if (wret) {
984 ret = wret; 966 ret = wret;
985 goto enospc; 967 goto enospc;
@@ -990,7 +972,7 @@ static noinline int balance_level(struct btrfs_trans_handle *trans,
990 btrfs_tree_lock(right); 972 btrfs_tree_lock(right);
991 btrfs_set_lock_blocking(right); 973 btrfs_set_lock_blocking(right);
992 wret = btrfs_cow_block(trans, root, right, 974 wret = btrfs_cow_block(trans, root, right,
993 parent, pslot + 1, &right, 0); 975 parent, pslot + 1, &right);
994 if (wret) { 976 if (wret) {
995 ret = wret; 977 ret = wret;
996 goto enospc; 978 goto enospc;
@@ -1171,7 +1153,7 @@ static noinline int push_nodes_for_insert(struct btrfs_trans_handle *trans,
1171 wret = 1; 1153 wret = 1;
1172 } else { 1154 } else {
1173 ret = btrfs_cow_block(trans, root, left, parent, 1155 ret = btrfs_cow_block(trans, root, left, parent,
1174 pslot - 1, &left, 0); 1156 pslot - 1, &left);
1175 if (ret) 1157 if (ret)
1176 wret = 1; 1158 wret = 1;
1177 else { 1159 else {
@@ -1222,7 +1204,7 @@ static noinline int push_nodes_for_insert(struct btrfs_trans_handle *trans,
1222 } else { 1204 } else {
1223 ret = btrfs_cow_block(trans, root, right, 1205 ret = btrfs_cow_block(trans, root, right,
1224 parent, pslot + 1, 1206 parent, pslot + 1,
1225 &right, 0); 1207 &right);
1226 if (ret) 1208 if (ret)
1227 wret = 1; 1209 wret = 1;
1228 else { 1210 else {
@@ -1262,9 +1244,9 @@ static noinline int push_nodes_for_insert(struct btrfs_trans_handle *trans,
1262 * readahead one full node of leaves, finding things that are close 1244 * readahead one full node of leaves, finding things that are close
1263 * to the block in 'slot', and triggering ra on them. 1245 * to the block in 'slot', and triggering ra on them.
1264 */ 1246 */
1265static noinline void reada_for_search(struct btrfs_root *root, 1247static void reada_for_search(struct btrfs_root *root,
1266 struct btrfs_path *path, 1248 struct btrfs_path *path,
1267 int level, int slot, u64 objectid) 1249 int level, int slot, u64 objectid)
1268{ 1250{
1269 struct extent_buffer *node; 1251 struct extent_buffer *node;
1270 struct btrfs_disk_key disk_key; 1252 struct btrfs_disk_key disk_key;
@@ -1465,6 +1447,117 @@ noinline void btrfs_unlock_up_safe(struct btrfs_path *path, int level)
1465} 1447}
1466 1448
1467/* 1449/*
1450 * helper function for btrfs_search_slot. The goal is to find a block
1451 * in cache without setting the path to blocking. If we find the block
1452 * we return zero and the path is unchanged.
1453 *
1454 * If we can't find the block, we set the path blocking and do some
1455 * reada. -EAGAIN is returned and the search must be repeated.
1456 */
1457static int
1458read_block_for_search(struct btrfs_trans_handle *trans,
1459 struct btrfs_root *root, struct btrfs_path *p,
1460 struct extent_buffer **eb_ret, int level, int slot,
1461 struct btrfs_key *key)
1462{
1463 u64 blocknr;
1464 u64 gen;
1465 u32 blocksize;
1466 struct extent_buffer *b = *eb_ret;
1467 struct extent_buffer *tmp;
1468
1469 blocknr = btrfs_node_blockptr(b, slot);
1470 gen = btrfs_node_ptr_generation(b, slot);
1471 blocksize = btrfs_level_size(root, level - 1);
1472
1473 tmp = btrfs_find_tree_block(root, blocknr, blocksize);
1474 if (tmp && btrfs_buffer_uptodate(tmp, gen)) {
1475 *eb_ret = tmp;
1476 return 0;
1477 }
1478
1479 /*
1480 * reduce lock contention at high levels
1481 * of the btree by dropping locks before
1482 * we read.
1483 */
1484 btrfs_release_path(NULL, p);
1485 if (tmp)
1486 free_extent_buffer(tmp);
1487 if (p->reada)
1488 reada_for_search(root, p, level, slot, key->objectid);
1489
1490 tmp = read_tree_block(root, blocknr, blocksize, gen);
1491 if (tmp)
1492 free_extent_buffer(tmp);
1493 return -EAGAIN;
1494}
1495
1496/*
1497 * helper function for btrfs_search_slot. This does all of the checks
1498 * for node-level blocks and does any balancing required based on
1499 * the ins_len.
1500 *
1501 * If no extra work was required, zero is returned. If we had to
1502 * drop the path, -EAGAIN is returned and btrfs_search_slot must
1503 * start over
1504 */
1505static int
1506setup_nodes_for_search(struct btrfs_trans_handle *trans,
1507 struct btrfs_root *root, struct btrfs_path *p,
1508 struct extent_buffer *b, int level, int ins_len)
1509{
1510 int ret;
1511 if ((p->search_for_split || ins_len > 0) && btrfs_header_nritems(b) >=
1512 BTRFS_NODEPTRS_PER_BLOCK(root) - 3) {
1513 int sret;
1514
1515 sret = reada_for_balance(root, p, level);
1516 if (sret)
1517 goto again;
1518
1519 btrfs_set_path_blocking(p);
1520 sret = split_node(trans, root, p, level);
1521 btrfs_clear_path_blocking(p, NULL);
1522
1523 BUG_ON(sret > 0);
1524 if (sret) {
1525 ret = sret;
1526 goto done;
1527 }
1528 b = p->nodes[level];
1529 } else if (ins_len < 0 && btrfs_header_nritems(b) <
1530 BTRFS_NODEPTRS_PER_BLOCK(root) / 4) {
1531 int sret;
1532
1533 sret = reada_for_balance(root, p, level);
1534 if (sret)
1535 goto again;
1536
1537 btrfs_set_path_blocking(p);
1538 sret = balance_level(trans, root, p, level);
1539 btrfs_clear_path_blocking(p, NULL);
1540
1541 if (sret) {
1542 ret = sret;
1543 goto done;
1544 }
1545 b = p->nodes[level];
1546 if (!b) {
1547 btrfs_release_path(NULL, p);
1548 goto again;
1549 }
1550 BUG_ON(btrfs_header_nritems(b) == 1);
1551 }
1552 return 0;
1553
1554again:
1555 ret = -EAGAIN;
1556done:
1557 return ret;
1558}
1559
1560/*
1468 * look for key in the tree. path is filled in with nodes along the way 1561 * look for key in the tree. path is filled in with nodes along the way
1469 * if key is found, we return zero and you can find the item in the leaf 1562 * if key is found, we return zero and you can find the item in the leaf
1470 * level of the path (level 0) 1563 * level of the path (level 0)
@@ -1482,17 +1575,11 @@ int btrfs_search_slot(struct btrfs_trans_handle *trans, struct btrfs_root
1482 ins_len, int cow) 1575 ins_len, int cow)
1483{ 1576{
1484 struct extent_buffer *b; 1577 struct extent_buffer *b;
1485 struct extent_buffer *tmp;
1486 int slot; 1578 int slot;
1487 int ret; 1579 int ret;
1488 int level; 1580 int level;
1489 int should_reada = p->reada;
1490 int lowest_unlock = 1; 1581 int lowest_unlock = 1;
1491 int blocksize;
1492 u8 lowest_level = 0; 1582 u8 lowest_level = 0;
1493 u64 blocknr;
1494 u64 gen;
1495 struct btrfs_key prealloc_block;
1496 1583
1497 lowest_level = p->lowest_level; 1584 lowest_level = p->lowest_level;
1498 WARN_ON(lowest_level && ins_len > 0); 1585 WARN_ON(lowest_level && ins_len > 0);
@@ -1501,8 +1588,6 @@ int btrfs_search_slot(struct btrfs_trans_handle *trans, struct btrfs_root
1501 if (ins_len < 0) 1588 if (ins_len < 0)
1502 lowest_unlock = 2; 1589 lowest_unlock = 2;
1503 1590
1504 prealloc_block.objectid = 0;
1505
1506again: 1591again:
1507 if (p->skip_locking) 1592 if (p->skip_locking)
1508 b = btrfs_root_node(root); 1593 b = btrfs_root_node(root);
@@ -1523,50 +1608,21 @@ again:
1523 if (cow) { 1608 if (cow) {
1524 int wret; 1609 int wret;
1525 1610
1526 /* is a cow on this block not required */ 1611 /*
1612 * if we don't really need to cow this block
1613 * then we don't want to set the path blocking,
1614 * so we test it here
1615 */
1527 if (btrfs_header_generation(b) == trans->transid && 1616 if (btrfs_header_generation(b) == trans->transid &&
1528 btrfs_header_owner(b) == root->root_key.objectid && 1617 btrfs_header_owner(b) == root->root_key.objectid &&
1529 !btrfs_header_flag(b, BTRFS_HEADER_FLAG_WRITTEN)) { 1618 !btrfs_header_flag(b, BTRFS_HEADER_FLAG_WRITTEN)) {
1530 goto cow_done; 1619 goto cow_done;
1531 } 1620 }
1532
1533 /* ok, we have to cow, is our old prealloc the right
1534 * size?
1535 */
1536 if (prealloc_block.objectid &&
1537 prealloc_block.offset != b->len) {
1538 btrfs_release_path(root, p);
1539 btrfs_free_reserved_extent(root,
1540 prealloc_block.objectid,
1541 prealloc_block.offset);
1542 prealloc_block.objectid = 0;
1543 goto again;
1544 }
1545
1546 /*
1547 * for higher level blocks, try not to allocate blocks
1548 * with the block and the parent locks held.
1549 */
1550 if (level > 0 && !prealloc_block.objectid) {
1551 u32 size = b->len;
1552 u64 hint = b->start;
1553
1554 btrfs_release_path(root, p);
1555 ret = btrfs_reserve_extent(trans, root,
1556 size, size, 0,
1557 hint, (u64)-1,
1558 &prealloc_block, 0);
1559 BUG_ON(ret);
1560 goto again;
1561 }
1562
1563 btrfs_set_path_blocking(p); 1621 btrfs_set_path_blocking(p);
1564 1622
1565 wret = btrfs_cow_block(trans, root, b, 1623 wret = btrfs_cow_block(trans, root, b,
1566 p->nodes[level + 1], 1624 p->nodes[level + 1],
1567 p->slots[level + 1], 1625 p->slots[level + 1], &b);
1568 &b, prealloc_block.objectid);
1569 prealloc_block.objectid = 0;
1570 if (wret) { 1626 if (wret) {
1571 free_extent_buffer(b); 1627 free_extent_buffer(b);
1572 ret = wret; 1628 ret = wret;
@@ -1611,51 +1667,15 @@ cow_done:
1611 if (ret && slot > 0) 1667 if (ret && slot > 0)
1612 slot -= 1; 1668 slot -= 1;
1613 p->slots[level] = slot; 1669 p->slots[level] = slot;
1614 if ((p->search_for_split || ins_len > 0) && 1670 ret = setup_nodes_for_search(trans, root, p, b, level,
1615 btrfs_header_nritems(b) >= 1671 ins_len);
1616 BTRFS_NODEPTRS_PER_BLOCK(root) - 3) { 1672 if (ret == -EAGAIN)
1617 int sret; 1673 goto again;
1618 1674 else if (ret)
1619 sret = reada_for_balance(root, p, level); 1675 goto done;
1620 if (sret) 1676 b = p->nodes[level];
1621 goto again; 1677 slot = p->slots[level];
1622
1623 btrfs_set_path_blocking(p);
1624 sret = split_node(trans, root, p, level);
1625 btrfs_clear_path_blocking(p, NULL);
1626
1627 BUG_ON(sret > 0);
1628 if (sret) {
1629 ret = sret;
1630 goto done;
1631 }
1632 b = p->nodes[level];
1633 slot = p->slots[level];
1634 } else if (ins_len < 0 &&
1635 btrfs_header_nritems(b) <
1636 BTRFS_NODEPTRS_PER_BLOCK(root) / 4) {
1637 int sret;
1638
1639 sret = reada_for_balance(root, p, level);
1640 if (sret)
1641 goto again;
1642
1643 btrfs_set_path_blocking(p);
1644 sret = balance_level(trans, root, p, level);
1645 btrfs_clear_path_blocking(p, NULL);
1646 1678
1647 if (sret) {
1648 ret = sret;
1649 goto done;
1650 }
1651 b = p->nodes[level];
1652 if (!b) {
1653 btrfs_release_path(NULL, p);
1654 goto again;
1655 }
1656 slot = p->slots[level];
1657 BUG_ON(btrfs_header_nritems(b) == 1);
1658 }
1659 unlock_up(p, level, lowest_unlock); 1679 unlock_up(p, level, lowest_unlock);
1660 1680
1661 /* this is only true while dropping a snapshot */ 1681 /* this is only true while dropping a snapshot */
@@ -1664,44 +1684,11 @@ cow_done:
1664 goto done; 1684 goto done;
1665 } 1685 }
1666 1686
1667 blocknr = btrfs_node_blockptr(b, slot); 1687 ret = read_block_for_search(trans, root, p,
1668 gen = btrfs_node_ptr_generation(b, slot); 1688 &b, level, slot, key);
1669 blocksize = btrfs_level_size(root, level - 1); 1689 if (ret == -EAGAIN)
1690 goto again;
1670 1691
1671 tmp = btrfs_find_tree_block(root, blocknr, blocksize);
1672 if (tmp && btrfs_buffer_uptodate(tmp, gen)) {
1673 b = tmp;
1674 } else {
1675 /*
1676 * reduce lock contention at high levels
1677 * of the btree by dropping locks before
1678 * we read.
1679 */
1680 if (level > 0) {
1681 btrfs_release_path(NULL, p);
1682 if (tmp)
1683 free_extent_buffer(tmp);
1684 if (should_reada)
1685 reada_for_search(root, p,
1686 level, slot,
1687 key->objectid);
1688
1689 tmp = read_tree_block(root, blocknr,
1690 blocksize, gen);
1691 if (tmp)
1692 free_extent_buffer(tmp);
1693 goto again;
1694 } else {
1695 btrfs_set_path_blocking(p);
1696 if (tmp)
1697 free_extent_buffer(tmp);
1698 if (should_reada)
1699 reada_for_search(root, p,
1700 level, slot,
1701 key->objectid);
1702 b = read_node_slot(root, b, slot);
1703 }
1704 }
1705 if (!p->skip_locking) { 1692 if (!p->skip_locking) {
1706 int lret; 1693 int lret;
1707 1694
@@ -1742,12 +1729,8 @@ done:
1742 * we don't really know what they plan on doing with the path 1729 * we don't really know what they plan on doing with the path
1743 * from here on, so for now just mark it as blocking 1730 * from here on, so for now just mark it as blocking
1744 */ 1731 */
1745 btrfs_set_path_blocking(p); 1732 if (!p->leave_spinning)
1746 if (prealloc_block.objectid) { 1733 btrfs_set_path_blocking(p);
1747 btrfs_free_reserved_extent(root,
1748 prealloc_block.objectid,
1749 prealloc_block.offset);
1750 }
1751 return ret; 1734 return ret;
1752} 1735}
1753 1736
@@ -1768,7 +1751,7 @@ int btrfs_merge_path(struct btrfs_trans_handle *trans,
1768 int ret; 1751 int ret;
1769 1752
1770 eb = btrfs_lock_root_node(root); 1753 eb = btrfs_lock_root_node(root);
1771 ret = btrfs_cow_block(trans, root, eb, NULL, 0, &eb, 0); 1754 ret = btrfs_cow_block(trans, root, eb, NULL, 0, &eb);
1772 BUG_ON(ret); 1755 BUG_ON(ret);
1773 1756
1774 btrfs_set_lock_blocking(eb); 1757 btrfs_set_lock_blocking(eb);
@@ -1826,7 +1809,7 @@ int btrfs_merge_path(struct btrfs_trans_handle *trans,
1826 } 1809 }
1827 1810
1828 ret = btrfs_cow_block(trans, root, eb, parent, slot, 1811 ret = btrfs_cow_block(trans, root, eb, parent, slot,
1829 &eb, 0); 1812 &eb);
1830 BUG_ON(ret); 1813 BUG_ON(ret);
1831 1814
1832 if (root->root_key.objectid == 1815 if (root->root_key.objectid ==
@@ -2139,7 +2122,7 @@ static noinline int insert_new_root(struct btrfs_trans_handle *trans,
2139 spin_unlock(&root->node_lock); 2122 spin_unlock(&root->node_lock);
2140 2123
2141 ret = btrfs_update_extent_ref(trans, root, lower->start, 2124 ret = btrfs_update_extent_ref(trans, root, lower->start,
2142 lower->start, c->start, 2125 lower->len, lower->start, c->start,
2143 root->root_key.objectid, 2126 root->root_key.objectid,
2144 trans->transid, level - 1); 2127 trans->transid, level - 1);
2145 BUG_ON(ret); 2128 BUG_ON(ret);
@@ -2174,8 +2157,7 @@ static int insert_ptr(struct btrfs_trans_handle *trans, struct btrfs_root
2174 BUG_ON(!path->nodes[level]); 2157 BUG_ON(!path->nodes[level]);
2175 lower = path->nodes[level]; 2158 lower = path->nodes[level];
2176 nritems = btrfs_header_nritems(lower); 2159 nritems = btrfs_header_nritems(lower);
2177 if (slot > nritems) 2160 BUG_ON(slot > nritems);
2178 BUG();
2179 if (nritems == BTRFS_NODEPTRS_PER_BLOCK(root)) 2161 if (nritems == BTRFS_NODEPTRS_PER_BLOCK(root))
2180 BUG(); 2162 BUG();
2181 if (slot != nritems) { 2163 if (slot != nritems) {
@@ -2221,7 +2203,7 @@ static noinline int split_node(struct btrfs_trans_handle *trans,
2221 ret = insert_new_root(trans, root, path, level + 1); 2203 ret = insert_new_root(trans, root, path, level + 1);
2222 if (ret) 2204 if (ret)
2223 return ret; 2205 return ret;
2224 } else { 2206 } else if (!trans->transaction->delayed_refs.flushing) {
2225 ret = push_nodes_for_insert(trans, root, path, level); 2207 ret = push_nodes_for_insert(trans, root, path, level);
2226 c = path->nodes[level]; 2208 c = path->nodes[level];
2227 if (!ret && btrfs_header_nritems(c) < 2209 if (!ret && btrfs_header_nritems(c) <
@@ -2329,66 +2311,27 @@ noinline int btrfs_leaf_free_space(struct btrfs_root *root,
2329 return ret; 2311 return ret;
2330} 2312}
2331 2313
2332/* 2314static noinline int __push_leaf_right(struct btrfs_trans_handle *trans,
2333 * push some data in the path leaf to the right, trying to free up at 2315 struct btrfs_root *root,
2334 * least data_size bytes. returns zero if the push worked, nonzero otherwise 2316 struct btrfs_path *path,
2335 * 2317 int data_size, int empty,
2336 * returns 1 if the push failed because the other node didn't have enough 2318 struct extent_buffer *right,
2337 * room, 0 if everything worked out and < 0 if there were major errors. 2319 int free_space, u32 left_nritems)
2338 */
2339static int push_leaf_right(struct btrfs_trans_handle *trans, struct btrfs_root
2340 *root, struct btrfs_path *path, int data_size,
2341 int empty)
2342{ 2320{
2343 struct extent_buffer *left = path->nodes[0]; 2321 struct extent_buffer *left = path->nodes[0];
2344 struct extent_buffer *right; 2322 struct extent_buffer *upper = path->nodes[1];
2345 struct extent_buffer *upper;
2346 struct btrfs_disk_key disk_key; 2323 struct btrfs_disk_key disk_key;
2347 int slot; 2324 int slot;
2348 u32 i; 2325 u32 i;
2349 int free_space;
2350 int push_space = 0; 2326 int push_space = 0;
2351 int push_items = 0; 2327 int push_items = 0;
2352 struct btrfs_item *item; 2328 struct btrfs_item *item;
2353 u32 left_nritems;
2354 u32 nr; 2329 u32 nr;
2355 u32 right_nritems; 2330 u32 right_nritems;
2356 u32 data_end; 2331 u32 data_end;
2357 u32 this_item_size; 2332 u32 this_item_size;
2358 int ret; 2333 int ret;
2359 2334
2360 slot = path->slots[1];
2361 if (!path->nodes[1])
2362 return 1;
2363
2364 upper = path->nodes[1];
2365 if (slot >= btrfs_header_nritems(upper) - 1)
2366 return 1;
2367
2368 btrfs_assert_tree_locked(path->nodes[1]);
2369
2370 right = read_node_slot(root, upper, slot + 1);
2371 btrfs_tree_lock(right);
2372 btrfs_set_lock_blocking(right);
2373
2374 free_space = btrfs_leaf_free_space(root, right);
2375 if (free_space < data_size)
2376 goto out_unlock;
2377
2378 /* cow and double check */
2379 ret = btrfs_cow_block(trans, root, right, upper,
2380 slot + 1, &right, 0);
2381 if (ret)
2382 goto out_unlock;
2383
2384 free_space = btrfs_leaf_free_space(root, right);
2385 if (free_space < data_size)
2386 goto out_unlock;
2387
2388 left_nritems = btrfs_header_nritems(left);
2389 if (left_nritems == 0)
2390 goto out_unlock;
2391
2392 if (empty) 2335 if (empty)
2393 nr = 0; 2336 nr = 0;
2394 else 2337 else
@@ -2397,6 +2340,7 @@ static int push_leaf_right(struct btrfs_trans_handle *trans, struct btrfs_root
2397 if (path->slots[0] >= left_nritems) 2340 if (path->slots[0] >= left_nritems)
2398 push_space += data_size; 2341 push_space += data_size;
2399 2342
2343 slot = path->slots[1];
2400 i = left_nritems - 1; 2344 i = left_nritems - 1;
2401 while (i >= nr) { 2345 while (i >= nr) {
2402 item = btrfs_item_nr(left, i); 2346 item = btrfs_item_nr(left, i);
@@ -2528,24 +2472,82 @@ out_unlock:
2528} 2472}
2529 2473
2530/* 2474/*
2475 * push some data in the path leaf to the right, trying to free up at
2476 * least data_size bytes. returns zero if the push worked, nonzero otherwise
2477 *
2478 * returns 1 if the push failed because the other node didn't have enough
2479 * room, 0 if everything worked out and < 0 if there were major errors.
2480 */
2481static int push_leaf_right(struct btrfs_trans_handle *trans, struct btrfs_root
2482 *root, struct btrfs_path *path, int data_size,
2483 int empty)
2484{
2485 struct extent_buffer *left = path->nodes[0];
2486 struct extent_buffer *right;
2487 struct extent_buffer *upper;
2488 int slot;
2489 int free_space;
2490 u32 left_nritems;
2491 int ret;
2492
2493 if (!path->nodes[1])
2494 return 1;
2495
2496 slot = path->slots[1];
2497 upper = path->nodes[1];
2498 if (slot >= btrfs_header_nritems(upper) - 1)
2499 return 1;
2500
2501 btrfs_assert_tree_locked(path->nodes[1]);
2502
2503 right = read_node_slot(root, upper, slot + 1);
2504 btrfs_tree_lock(right);
2505 btrfs_set_lock_blocking(right);
2506
2507 free_space = btrfs_leaf_free_space(root, right);
2508 if (free_space < data_size)
2509 goto out_unlock;
2510
2511 /* cow and double check */
2512 ret = btrfs_cow_block(trans, root, right, upper,
2513 slot + 1, &right);
2514 if (ret)
2515 goto out_unlock;
2516
2517 free_space = btrfs_leaf_free_space(root, right);
2518 if (free_space < data_size)
2519 goto out_unlock;
2520
2521 left_nritems = btrfs_header_nritems(left);
2522 if (left_nritems == 0)
2523 goto out_unlock;
2524
2525 return __push_leaf_right(trans, root, path, data_size, empty,
2526 right, free_space, left_nritems);
2527out_unlock:
2528 btrfs_tree_unlock(right);
2529 free_extent_buffer(right);
2530 return 1;
2531}
2532
2533/*
2531 * push some data in the path leaf to the left, trying to free up at 2534 * push some data in the path leaf to the left, trying to free up at
2532 * least data_size bytes. returns zero if the push worked, nonzero otherwise 2535 * least data_size bytes. returns zero if the push worked, nonzero otherwise
2533 */ 2536 */
2534static int push_leaf_left(struct btrfs_trans_handle *trans, struct btrfs_root 2537static noinline int __push_leaf_left(struct btrfs_trans_handle *trans,
2535 *root, struct btrfs_path *path, int data_size, 2538 struct btrfs_root *root,
2536 int empty) 2539 struct btrfs_path *path, int data_size,
2540 int empty, struct extent_buffer *left,
2541 int free_space, int right_nritems)
2537{ 2542{
2538 struct btrfs_disk_key disk_key; 2543 struct btrfs_disk_key disk_key;
2539 struct extent_buffer *right = path->nodes[0]; 2544 struct extent_buffer *right = path->nodes[0];
2540 struct extent_buffer *left;
2541 int slot; 2545 int slot;
2542 int i; 2546 int i;
2543 int free_space;
2544 int push_space = 0; 2547 int push_space = 0;
2545 int push_items = 0; 2548 int push_items = 0;
2546 struct btrfs_item *item; 2549 struct btrfs_item *item;
2547 u32 old_left_nritems; 2550 u32 old_left_nritems;
2548 u32 right_nritems;
2549 u32 nr; 2551 u32 nr;
2550 int ret = 0; 2552 int ret = 0;
2551 int wret; 2553 int wret;
@@ -2553,41 +2555,6 @@ static int push_leaf_left(struct btrfs_trans_handle *trans, struct btrfs_root
2553 u32 old_left_item_size; 2555 u32 old_left_item_size;
2554 2556
2555 slot = path->slots[1]; 2557 slot = path->slots[1];
2556 if (slot == 0)
2557 return 1;
2558 if (!path->nodes[1])
2559 return 1;
2560
2561 right_nritems = btrfs_header_nritems(right);
2562 if (right_nritems == 0)
2563 return 1;
2564
2565 btrfs_assert_tree_locked(path->nodes[1]);
2566
2567 left = read_node_slot(root, path->nodes[1], slot - 1);
2568 btrfs_tree_lock(left);
2569 btrfs_set_lock_blocking(left);
2570
2571 free_space = btrfs_leaf_free_space(root, left);
2572 if (free_space < data_size) {
2573 ret = 1;
2574 goto out;
2575 }
2576
2577 /* cow and double check */
2578 ret = btrfs_cow_block(trans, root, left,
2579 path->nodes[1], slot - 1, &left, 0);
2580 if (ret) {
2581 /* we hit -ENOSPC, but it isn't fatal here */
2582 ret = 1;
2583 goto out;
2584 }
2585
2586 free_space = btrfs_leaf_free_space(root, left);
2587 if (free_space < data_size) {
2588 ret = 1;
2589 goto out;
2590 }
2591 2558
2592 if (empty) 2559 if (empty)
2593 nr = right_nritems; 2560 nr = right_nritems;
@@ -2755,6 +2722,154 @@ out:
2755} 2722}
2756 2723
2757/* 2724/*
2725 * push some data in the path leaf to the left, trying to free up at
2726 * least data_size bytes. returns zero if the push worked, nonzero otherwise
2727 */
2728static int push_leaf_left(struct btrfs_trans_handle *trans, struct btrfs_root
2729 *root, struct btrfs_path *path, int data_size,
2730 int empty)
2731{
2732 struct extent_buffer *right = path->nodes[0];
2733 struct extent_buffer *left;
2734 int slot;
2735 int free_space;
2736 u32 right_nritems;
2737 int ret = 0;
2738
2739 slot = path->slots[1];
2740 if (slot == 0)
2741 return 1;
2742 if (!path->nodes[1])
2743 return 1;
2744
2745 right_nritems = btrfs_header_nritems(right);
2746 if (right_nritems == 0)
2747 return 1;
2748
2749 btrfs_assert_tree_locked(path->nodes[1]);
2750
2751 left = read_node_slot(root, path->nodes[1], slot - 1);
2752 btrfs_tree_lock(left);
2753 btrfs_set_lock_blocking(left);
2754
2755 free_space = btrfs_leaf_free_space(root, left);
2756 if (free_space < data_size) {
2757 ret = 1;
2758 goto out;
2759 }
2760
2761 /* cow and double check */
2762 ret = btrfs_cow_block(trans, root, left,
2763 path->nodes[1], slot - 1, &left);
2764 if (ret) {
2765 /* we hit -ENOSPC, but it isn't fatal here */
2766 ret = 1;
2767 goto out;
2768 }
2769
2770 free_space = btrfs_leaf_free_space(root, left);
2771 if (free_space < data_size) {
2772 ret = 1;
2773 goto out;
2774 }
2775
2776 return __push_leaf_left(trans, root, path, data_size,
2777 empty, left, free_space, right_nritems);
2778out:
2779 btrfs_tree_unlock(left);
2780 free_extent_buffer(left);
2781 return ret;
2782}
2783
2784/*
2785 * split the path's leaf in two, making sure there is at least data_size
2786 * available for the resulting leaf level of the path.
2787 *
2788 * returns 0 if all went well and < 0 on failure.
2789 */
2790static noinline int copy_for_split(struct btrfs_trans_handle *trans,
2791 struct btrfs_root *root,
2792 struct btrfs_path *path,
2793 struct extent_buffer *l,
2794 struct extent_buffer *right,
2795 int slot, int mid, int nritems)
2796{
2797 int data_copy_size;
2798 int rt_data_off;
2799 int i;
2800 int ret = 0;
2801 int wret;
2802 struct btrfs_disk_key disk_key;
2803
2804 nritems = nritems - mid;
2805 btrfs_set_header_nritems(right, nritems);
2806 data_copy_size = btrfs_item_end_nr(l, mid) - leaf_data_end(root, l);
2807
2808 copy_extent_buffer(right, l, btrfs_item_nr_offset(0),
2809 btrfs_item_nr_offset(mid),
2810 nritems * sizeof(struct btrfs_item));
2811
2812 copy_extent_buffer(right, l,
2813 btrfs_leaf_data(right) + BTRFS_LEAF_DATA_SIZE(root) -
2814 data_copy_size, btrfs_leaf_data(l) +
2815 leaf_data_end(root, l), data_copy_size);
2816
2817 rt_data_off = BTRFS_LEAF_DATA_SIZE(root) -
2818 btrfs_item_end_nr(l, mid);
2819
2820 for (i = 0; i < nritems; i++) {
2821 struct btrfs_item *item = btrfs_item_nr(right, i);
2822 u32 ioff;
2823
2824 if (!right->map_token) {
2825 map_extent_buffer(right, (unsigned long)item,
2826 sizeof(struct btrfs_item),
2827 &right->map_token, &right->kaddr,
2828 &right->map_start, &right->map_len,
2829 KM_USER1);
2830 }
2831
2832 ioff = btrfs_item_offset(right, item);
2833 btrfs_set_item_offset(right, item, ioff + rt_data_off);
2834 }
2835
2836 if (right->map_token) {
2837 unmap_extent_buffer(right, right->map_token, KM_USER1);
2838 right->map_token = NULL;
2839 }
2840
2841 btrfs_set_header_nritems(l, mid);
2842 ret = 0;
2843 btrfs_item_key(right, &disk_key, 0);
2844 wret = insert_ptr(trans, root, path, &disk_key, right->start,
2845 path->slots[1] + 1, 1);
2846 if (wret)
2847 ret = wret;
2848
2849 btrfs_mark_buffer_dirty(right);
2850 btrfs_mark_buffer_dirty(l);
2851 BUG_ON(path->slots[0] != slot);
2852
2853 ret = btrfs_update_ref(trans, root, l, right, 0, nritems);
2854 BUG_ON(ret);
2855
2856 if (mid <= slot) {
2857 btrfs_tree_unlock(path->nodes[0]);
2858 free_extent_buffer(path->nodes[0]);
2859 path->nodes[0] = right;
2860 path->slots[0] -= mid;
2861 path->slots[1] += 1;
2862 } else {
2863 btrfs_tree_unlock(right);
2864 free_extent_buffer(right);
2865 }
2866
2867 BUG_ON(path->slots[0] < 0);
2868
2869 return ret;
2870}
2871
2872/*
2758 * split the path's leaf in two, making sure there is at least data_size 2873 * split the path's leaf in two, making sure there is at least data_size
2759 * available for the resulting leaf level of the path. 2874 * available for the resulting leaf level of the path.
2760 * 2875 *
@@ -2771,17 +2886,14 @@ static noinline int split_leaf(struct btrfs_trans_handle *trans,
2771 int mid; 2886 int mid;
2772 int slot; 2887 int slot;
2773 struct extent_buffer *right; 2888 struct extent_buffer *right;
2774 int data_copy_size;
2775 int rt_data_off;
2776 int i;
2777 int ret = 0; 2889 int ret = 0;
2778 int wret; 2890 int wret;
2779 int double_split; 2891 int double_split;
2780 int num_doubles = 0; 2892 int num_doubles = 0;
2781 struct btrfs_disk_key disk_key;
2782 2893
2783 /* first try to make some room by pushing left and right */ 2894 /* first try to make some room by pushing left and right */
2784 if (data_size && ins_key->type != BTRFS_DIR_ITEM_KEY) { 2895 if (data_size && ins_key->type != BTRFS_DIR_ITEM_KEY &&
2896 !trans->transaction->delayed_refs.flushing) {
2785 wret = push_leaf_right(trans, root, path, data_size, 0); 2897 wret = push_leaf_right(trans, root, path, data_size, 0);
2786 if (wret < 0) 2898 if (wret < 0)
2787 return wret; 2899 return wret;
@@ -2830,11 +2942,14 @@ again:
2830 write_extent_buffer(right, root->fs_info->chunk_tree_uuid, 2942 write_extent_buffer(right, root->fs_info->chunk_tree_uuid,
2831 (unsigned long)btrfs_header_chunk_tree_uuid(right), 2943 (unsigned long)btrfs_header_chunk_tree_uuid(right),
2832 BTRFS_UUID_SIZE); 2944 BTRFS_UUID_SIZE);
2945
2833 if (mid <= slot) { 2946 if (mid <= slot) {
2834 if (nritems == 1 || 2947 if (nritems == 1 ||
2835 leaf_space_used(l, mid, nritems - mid) + data_size > 2948 leaf_space_used(l, mid, nritems - mid) + data_size >
2836 BTRFS_LEAF_DATA_SIZE(root)) { 2949 BTRFS_LEAF_DATA_SIZE(root)) {
2837 if (slot >= nritems) { 2950 if (slot >= nritems) {
2951 struct btrfs_disk_key disk_key;
2952
2838 btrfs_cpu_key_to_disk(&disk_key, ins_key); 2953 btrfs_cpu_key_to_disk(&disk_key, ins_key);
2839 btrfs_set_header_nritems(right, 0); 2954 btrfs_set_header_nritems(right, 0);
2840 wret = insert_ptr(trans, root, path, 2955 wret = insert_ptr(trans, root, path,
@@ -2862,6 +2977,8 @@ again:
2862 if (leaf_space_used(l, 0, mid) + data_size > 2977 if (leaf_space_used(l, 0, mid) + data_size >
2863 BTRFS_LEAF_DATA_SIZE(root)) { 2978 BTRFS_LEAF_DATA_SIZE(root)) {
2864 if (!extend && data_size && slot == 0) { 2979 if (!extend && data_size && slot == 0) {
2980 struct btrfs_disk_key disk_key;
2981
2865 btrfs_cpu_key_to_disk(&disk_key, ins_key); 2982 btrfs_cpu_key_to_disk(&disk_key, ins_key);
2866 btrfs_set_header_nritems(right, 0); 2983 btrfs_set_header_nritems(right, 0);
2867 wret = insert_ptr(trans, root, path, 2984 wret = insert_ptr(trans, root, path,
@@ -2894,76 +3011,16 @@ again:
2894 } 3011 }
2895 } 3012 }
2896 } 3013 }
2897 nritems = nritems - mid;
2898 btrfs_set_header_nritems(right, nritems);
2899 data_copy_size = btrfs_item_end_nr(l, mid) - leaf_data_end(root, l);
2900
2901 copy_extent_buffer(right, l, btrfs_item_nr_offset(0),
2902 btrfs_item_nr_offset(mid),
2903 nritems * sizeof(struct btrfs_item));
2904
2905 copy_extent_buffer(right, l,
2906 btrfs_leaf_data(right) + BTRFS_LEAF_DATA_SIZE(root) -
2907 data_copy_size, btrfs_leaf_data(l) +
2908 leaf_data_end(root, l), data_copy_size);
2909
2910 rt_data_off = BTRFS_LEAF_DATA_SIZE(root) -
2911 btrfs_item_end_nr(l, mid);
2912
2913 for (i = 0; i < nritems; i++) {
2914 struct btrfs_item *item = btrfs_item_nr(right, i);
2915 u32 ioff;
2916
2917 if (!right->map_token) {
2918 map_extent_buffer(right, (unsigned long)item,
2919 sizeof(struct btrfs_item),
2920 &right->map_token, &right->kaddr,
2921 &right->map_start, &right->map_len,
2922 KM_USER1);
2923 }
2924
2925 ioff = btrfs_item_offset(right, item);
2926 btrfs_set_item_offset(right, item, ioff + rt_data_off);
2927 }
2928 3014
2929 if (right->map_token) { 3015 ret = copy_for_split(trans, root, path, l, right, slot, mid, nritems);
2930 unmap_extent_buffer(right, right->map_token, KM_USER1);
2931 right->map_token = NULL;
2932 }
2933
2934 btrfs_set_header_nritems(l, mid);
2935 ret = 0;
2936 btrfs_item_key(right, &disk_key, 0);
2937 wret = insert_ptr(trans, root, path, &disk_key, right->start,
2938 path->slots[1] + 1, 1);
2939 if (wret)
2940 ret = wret;
2941
2942 btrfs_mark_buffer_dirty(right);
2943 btrfs_mark_buffer_dirty(l);
2944 BUG_ON(path->slots[0] != slot);
2945
2946 ret = btrfs_update_ref(trans, root, l, right, 0, nritems);
2947 BUG_ON(ret); 3016 BUG_ON(ret);
2948 3017
2949 if (mid <= slot) {
2950 btrfs_tree_unlock(path->nodes[0]);
2951 free_extent_buffer(path->nodes[0]);
2952 path->nodes[0] = right;
2953 path->slots[0] -= mid;
2954 path->slots[1] += 1;
2955 } else {
2956 btrfs_tree_unlock(right);
2957 free_extent_buffer(right);
2958 }
2959
2960 BUG_ON(path->slots[0] < 0);
2961
2962 if (double_split) { 3018 if (double_split) {
2963 BUG_ON(num_doubles != 0); 3019 BUG_ON(num_doubles != 0);
2964 num_doubles++; 3020 num_doubles++;
2965 goto again; 3021 goto again;
2966 } 3022 }
3023
2967 return ret; 3024 return ret;
2968} 3025}
2969 3026
@@ -3021,26 +3078,27 @@ int btrfs_split_item(struct btrfs_trans_handle *trans,
3021 return -EAGAIN; 3078 return -EAGAIN;
3022 } 3079 }
3023 3080
3081 btrfs_set_path_blocking(path);
3024 ret = split_leaf(trans, root, &orig_key, path, 3082 ret = split_leaf(trans, root, &orig_key, path,
3025 sizeof(struct btrfs_item), 1); 3083 sizeof(struct btrfs_item), 1);
3026 path->keep_locks = 0; 3084 path->keep_locks = 0;
3027 BUG_ON(ret); 3085 BUG_ON(ret);
3028 3086
3087 btrfs_unlock_up_safe(path, 1);
3088 leaf = path->nodes[0];
3089 BUG_ON(btrfs_leaf_free_space(root, leaf) < sizeof(struct btrfs_item));
3090
3091split:
3029 /* 3092 /*
3030 * make sure any changes to the path from split_leaf leave it 3093 * make sure any changes to the path from split_leaf leave it
3031 * in a blocking state 3094 * in a blocking state
3032 */ 3095 */
3033 btrfs_set_path_blocking(path); 3096 btrfs_set_path_blocking(path);
3034 3097
3035 leaf = path->nodes[0];
3036 BUG_ON(btrfs_leaf_free_space(root, leaf) < sizeof(struct btrfs_item));
3037
3038split:
3039 item = btrfs_item_nr(leaf, path->slots[0]); 3098 item = btrfs_item_nr(leaf, path->slots[0]);
3040 orig_offset = btrfs_item_offset(leaf, item); 3099 orig_offset = btrfs_item_offset(leaf, item);
3041 item_size = btrfs_item_size(leaf, item); 3100 item_size = btrfs_item_size(leaf, item);
3042 3101
3043
3044 buf = kmalloc(item_size, GFP_NOFS); 3102 buf = kmalloc(item_size, GFP_NOFS);
3045 read_extent_buffer(leaf, buf, btrfs_item_ptr_offset(leaf, 3103 read_extent_buffer(leaf, buf, btrfs_item_ptr_offset(leaf,
3046 path->slots[0]), item_size); 3104 path->slots[0]), item_size);
@@ -3445,39 +3503,27 @@ out:
3445} 3503}
3446 3504
3447/* 3505/*
3448 * Given a key and some data, insert items into the tree. 3506 * this is a helper for btrfs_insert_empty_items, the main goal here is
3449 * This does all the path init required, making room in the tree if needed. 3507 * to save stack depth by doing the bulk of the work in a function
3508 * that doesn't call btrfs_search_slot
3450 */ 3509 */
3451int btrfs_insert_empty_items(struct btrfs_trans_handle *trans, 3510static noinline_for_stack int
3452 struct btrfs_root *root, 3511setup_items_for_insert(struct btrfs_trans_handle *trans,
3453 struct btrfs_path *path, 3512 struct btrfs_root *root, struct btrfs_path *path,
3454 struct btrfs_key *cpu_key, u32 *data_size, 3513 struct btrfs_key *cpu_key, u32 *data_size,
3455 int nr) 3514 u32 total_data, u32 total_size, int nr)
3456{ 3515{
3457 struct extent_buffer *leaf;
3458 struct btrfs_item *item; 3516 struct btrfs_item *item;
3459 int ret = 0;
3460 int slot;
3461 int slot_orig;
3462 int i; 3517 int i;
3463 u32 nritems; 3518 u32 nritems;
3464 u32 total_size = 0;
3465 u32 total_data = 0;
3466 unsigned int data_end; 3519 unsigned int data_end;
3467 struct btrfs_disk_key disk_key; 3520 struct btrfs_disk_key disk_key;
3521 int ret;
3522 struct extent_buffer *leaf;
3523 int slot;
3468 3524
3469 for (i = 0; i < nr; i++)
3470 total_data += data_size[i];
3471
3472 total_size = total_data + (nr * sizeof(struct btrfs_item));
3473 ret = btrfs_search_slot(trans, root, cpu_key, path, total_size, 1);
3474 if (ret == 0)
3475 return -EEXIST;
3476 if (ret < 0)
3477 goto out;
3478
3479 slot_orig = path->slots[0];
3480 leaf = path->nodes[0]; 3525 leaf = path->nodes[0];
3526 slot = path->slots[0];
3481 3527
3482 nritems = btrfs_header_nritems(leaf); 3528 nritems = btrfs_header_nritems(leaf);
3483 data_end = leaf_data_end(root, leaf); 3529 data_end = leaf_data_end(root, leaf);
@@ -3489,9 +3535,6 @@ int btrfs_insert_empty_items(struct btrfs_trans_handle *trans,
3489 BUG(); 3535 BUG();
3490 } 3536 }
3491 3537
3492 slot = path->slots[0];
3493 BUG_ON(slot < 0);
3494
3495 if (slot != nritems) { 3538 if (slot != nritems) {
3496 unsigned int old_data = btrfs_item_end_nr(leaf, slot); 3539 unsigned int old_data = btrfs_item_end_nr(leaf, slot);
3497 3540
@@ -3547,21 +3590,60 @@ int btrfs_insert_empty_items(struct btrfs_trans_handle *trans,
3547 data_end -= data_size[i]; 3590 data_end -= data_size[i];
3548 btrfs_set_item_size(leaf, item, data_size[i]); 3591 btrfs_set_item_size(leaf, item, data_size[i]);
3549 } 3592 }
3593
3550 btrfs_set_header_nritems(leaf, nritems + nr); 3594 btrfs_set_header_nritems(leaf, nritems + nr);
3551 btrfs_mark_buffer_dirty(leaf);
3552 3595
3553 ret = 0; 3596 ret = 0;
3554 if (slot == 0) { 3597 if (slot == 0) {
3598 struct btrfs_disk_key disk_key;
3555 btrfs_cpu_key_to_disk(&disk_key, cpu_key); 3599 btrfs_cpu_key_to_disk(&disk_key, cpu_key);
3556 ret = fixup_low_keys(trans, root, path, &disk_key, 1); 3600 ret = fixup_low_keys(trans, root, path, &disk_key, 1);
3557 } 3601 }
3602 btrfs_unlock_up_safe(path, 1);
3603 btrfs_mark_buffer_dirty(leaf);
3558 3604
3559 if (btrfs_leaf_free_space(root, leaf) < 0) { 3605 if (btrfs_leaf_free_space(root, leaf) < 0) {
3560 btrfs_print_leaf(root, leaf); 3606 btrfs_print_leaf(root, leaf);
3561 BUG(); 3607 BUG();
3562 } 3608 }
3609 return ret;
3610}
3611
3612/*
3613 * Given a key and some data, insert items into the tree.
3614 * This does all the path init required, making room in the tree if needed.
3615 */
3616int btrfs_insert_empty_items(struct btrfs_trans_handle *trans,
3617 struct btrfs_root *root,
3618 struct btrfs_path *path,
3619 struct btrfs_key *cpu_key, u32 *data_size,
3620 int nr)
3621{
3622 struct extent_buffer *leaf;
3623 int ret = 0;
3624 int slot;
3625 int i;
3626 u32 total_size = 0;
3627 u32 total_data = 0;
3628
3629 for (i = 0; i < nr; i++)
3630 total_data += data_size[i];
3631
3632 total_size = total_data + (nr * sizeof(struct btrfs_item));
3633 ret = btrfs_search_slot(trans, root, cpu_key, path, total_size, 1);
3634 if (ret == 0)
3635 return -EEXIST;
3636 if (ret < 0)
3637 goto out;
3638
3639 leaf = path->nodes[0];
3640 slot = path->slots[0];
3641 BUG_ON(slot < 0);
3642
3643 ret = setup_items_for_insert(trans, root, path, cpu_key, data_size,
3644 total_data, total_size, nr);
3645
3563out: 3646out:
3564 btrfs_unlock_up_safe(path, 1);
3565 return ret; 3647 return ret;
3566} 3648}
3567 3649
@@ -3749,7 +3831,8 @@ int btrfs_del_items(struct btrfs_trans_handle *trans, struct btrfs_root *root,
3749 } 3831 }
3750 3832
3751 /* delete the leaf if it is mostly empty */ 3833 /* delete the leaf if it is mostly empty */
3752 if (used < BTRFS_LEAF_DATA_SIZE(root) / 4) { 3834 if (used < BTRFS_LEAF_DATA_SIZE(root) / 4 &&
3835 !trans->transaction->delayed_refs.flushing) {
3753 /* push_leaf_left fixes the path. 3836 /* push_leaf_left fixes the path.
3754 * make sure the path still points to our leaf 3837 * make sure the path still points to our leaf
3755 * for possible call to del_ptr below 3838 * for possible call to del_ptr below
@@ -3757,6 +3840,7 @@ int btrfs_del_items(struct btrfs_trans_handle *trans, struct btrfs_root *root,
3757 slot = path->slots[1]; 3840 slot = path->slots[1];
3758 extent_buffer_get(leaf); 3841 extent_buffer_get(leaf);
3759 3842
3843 btrfs_set_path_blocking(path);
3760 wret = push_leaf_left(trans, root, path, 1, 1); 3844 wret = push_leaf_left(trans, root, path, 1, 1);
3761 if (wret < 0 && wret != -ENOSPC) 3845 if (wret < 0 && wret != -ENOSPC)
3762 ret = wret; 3846 ret = wret;
@@ -4042,28 +4126,44 @@ next:
4042int btrfs_next_leaf(struct btrfs_root *root, struct btrfs_path *path) 4126int btrfs_next_leaf(struct btrfs_root *root, struct btrfs_path *path)
4043{ 4127{
4044 int slot; 4128 int slot;
4045 int level = 1; 4129 int level;
4046 struct extent_buffer *c; 4130 struct extent_buffer *c;
4047 struct extent_buffer *next = NULL; 4131 struct extent_buffer *next;
4048 struct btrfs_key key; 4132 struct btrfs_key key;
4049 u32 nritems; 4133 u32 nritems;
4050 int ret; 4134 int ret;
4135 int old_spinning = path->leave_spinning;
4136 int force_blocking = 0;
4051 4137
4052 nritems = btrfs_header_nritems(path->nodes[0]); 4138 nritems = btrfs_header_nritems(path->nodes[0]);
4053 if (nritems == 0) 4139 if (nritems == 0)
4054 return 1; 4140 return 1;
4055 4141
4056 btrfs_item_key_to_cpu(path->nodes[0], &key, nritems - 1); 4142 /*
4143 * we take the blocks in an order that upsets lockdep. Using
4144 * blocking mode is the only way around it.
4145 */
4146#ifdef CONFIG_DEBUG_LOCK_ALLOC
4147 force_blocking = 1;
4148#endif
4057 4149
4150 btrfs_item_key_to_cpu(path->nodes[0], &key, nritems - 1);
4151again:
4152 level = 1;
4153 next = NULL;
4058 btrfs_release_path(root, path); 4154 btrfs_release_path(root, path);
4155
4059 path->keep_locks = 1; 4156 path->keep_locks = 1;
4157
4158 if (!force_blocking)
4159 path->leave_spinning = 1;
4160
4060 ret = btrfs_search_slot(NULL, root, &key, path, 0, 0); 4161 ret = btrfs_search_slot(NULL, root, &key, path, 0, 0);
4061 path->keep_locks = 0; 4162 path->keep_locks = 0;
4062 4163
4063 if (ret < 0) 4164 if (ret < 0)
4064 return ret; 4165 return ret;
4065 4166
4066 btrfs_set_path_blocking(path);
4067 nritems = btrfs_header_nritems(path->nodes[0]); 4167 nritems = btrfs_header_nritems(path->nodes[0]);
4068 /* 4168 /*
4069 * by releasing the path above we dropped all our locks. A balance 4169 * by releasing the path above we dropped all our locks. A balance
@@ -4073,19 +4173,24 @@ int btrfs_next_leaf(struct btrfs_root *root, struct btrfs_path *path)
4073 */ 4173 */
4074 if (nritems > 0 && path->slots[0] < nritems - 1) { 4174 if (nritems > 0 && path->slots[0] < nritems - 1) {
4075 path->slots[0]++; 4175 path->slots[0]++;
4176 ret = 0;
4076 goto done; 4177 goto done;
4077 } 4178 }
4078 4179
4079 while (level < BTRFS_MAX_LEVEL) { 4180 while (level < BTRFS_MAX_LEVEL) {
4080 if (!path->nodes[level]) 4181 if (!path->nodes[level]) {
4081 return 1; 4182 ret = 1;
4183 goto done;
4184 }
4082 4185
4083 slot = path->slots[level] + 1; 4186 slot = path->slots[level] + 1;
4084 c = path->nodes[level]; 4187 c = path->nodes[level];
4085 if (slot >= btrfs_header_nritems(c)) { 4188 if (slot >= btrfs_header_nritems(c)) {
4086 level++; 4189 level++;
4087 if (level == BTRFS_MAX_LEVEL) 4190 if (level == BTRFS_MAX_LEVEL) {
4088 return 1; 4191 ret = 1;
4192 goto done;
4193 }
4089 continue; 4194 continue;
4090 } 4195 }
4091 4196
@@ -4094,16 +4199,22 @@ int btrfs_next_leaf(struct btrfs_root *root, struct btrfs_path *path)
4094 free_extent_buffer(next); 4199 free_extent_buffer(next);
4095 } 4200 }
4096 4201
4097 /* the path was set to blocking above */ 4202 next = c;
4098 if (level == 1 && (path->locks[1] || path->skip_locking) && 4203 ret = read_block_for_search(NULL, root, path, &next, level,
4099 path->reada) 4204 slot, &key);
4100 reada_for_search(root, path, level, slot, 0); 4205 if (ret == -EAGAIN)
4206 goto again;
4101 4207
4102 next = read_node_slot(root, c, slot);
4103 if (!path->skip_locking) { 4208 if (!path->skip_locking) {
4104 btrfs_assert_tree_locked(c); 4209 ret = btrfs_try_spin_lock(next);
4105 btrfs_tree_lock(next); 4210 if (!ret) {
4106 btrfs_set_lock_blocking(next); 4211 btrfs_set_path_blocking(path);
4212 btrfs_tree_lock(next);
4213 if (!force_blocking)
4214 btrfs_clear_path_blocking(path, next);
4215 }
4216 if (force_blocking)
4217 btrfs_set_lock_blocking(next);
4107 } 4218 }
4108 break; 4219 break;
4109 } 4220 }
@@ -4113,27 +4224,42 @@ int btrfs_next_leaf(struct btrfs_root *root, struct btrfs_path *path)
4113 c = path->nodes[level]; 4224 c = path->nodes[level];
4114 if (path->locks[level]) 4225 if (path->locks[level])
4115 btrfs_tree_unlock(c); 4226 btrfs_tree_unlock(c);
4227
4116 free_extent_buffer(c); 4228 free_extent_buffer(c);
4117 path->nodes[level] = next; 4229 path->nodes[level] = next;
4118 path->slots[level] = 0; 4230 path->slots[level] = 0;
4119 if (!path->skip_locking) 4231 if (!path->skip_locking)
4120 path->locks[level] = 1; 4232 path->locks[level] = 1;
4233
4121 if (!level) 4234 if (!level)
4122 break; 4235 break;
4123 4236
4124 btrfs_set_path_blocking(path); 4237 ret = read_block_for_search(NULL, root, path, &next, level,
4125 if (level == 1 && path->locks[1] && path->reada) 4238 0, &key);
4126 reada_for_search(root, path, level, slot, 0); 4239 if (ret == -EAGAIN)
4127 next = read_node_slot(root, next, 0); 4240 goto again;
4241
4128 if (!path->skip_locking) { 4242 if (!path->skip_locking) {
4129 btrfs_assert_tree_locked(path->nodes[level]); 4243 btrfs_assert_tree_locked(path->nodes[level]);
4130 btrfs_tree_lock(next); 4244 ret = btrfs_try_spin_lock(next);
4131 btrfs_set_lock_blocking(next); 4245 if (!ret) {
4246 btrfs_set_path_blocking(path);
4247 btrfs_tree_lock(next);
4248 if (!force_blocking)
4249 btrfs_clear_path_blocking(path, next);
4250 }
4251 if (force_blocking)
4252 btrfs_set_lock_blocking(next);
4132 } 4253 }
4133 } 4254 }
4255 ret = 0;
4134done: 4256done:
4135 unlock_up(path, 0, 1); 4257 unlock_up(path, 0, 1);
4136 return 0; 4258 path->leave_spinning = old_spinning;
4259 if (!old_spinning)
4260 btrfs_set_path_blocking(path);
4261
4262 return ret;
4137} 4263}
4138 4264
4139/* 4265/*
generated by cgit v1.2.2 (git 2.25.0) at 2025-05-29 07:03:40 -0400