return 0;
}
-static int should_defrag_leaf(struct extent_buffer *leaf)
+/*
+ * compare two keys in a memcmp fashion
+ */
+static int comp_keys(struct btrfs_disk_key *disk, struct btrfs_key *k2)
{
- struct btrfs_key key;
- u32 nritems;
-
- if (btrfs_buffer_defrag(leaf))
- return 1;
+ struct btrfs_key k1;
- nritems = btrfs_header_nritems(leaf);
- if (nritems == 0)
- return 0;
+ btrfs_disk_key_to_cpu(&k1, disk);
- btrfs_item_key_to_cpu(leaf, &key, 0);
- if (key.type == BTRFS_DIR_ITEM_KEY)
+ if (k1.objectid > k2->objectid)
return 1;
-
-
- btrfs_item_key_to_cpu(leaf, &key, nritems - 1);
- if (key.type == BTRFS_DIR_ITEM_KEY)
+ if (k1.objectid < k2->objectid)
+ return -1;
+ if (k1.type > k2->type)
return 1;
- if (nritems > 4) {
- btrfs_item_key_to_cpu(leaf, &key, nritems / 2);
- if (key.type == BTRFS_DIR_ITEM_KEY)
- return 1;
- }
+ if (k1.type < k2->type)
+ return -1;
+ if (k1.offset > k2->offset)
+ return 1;
+ if (k1.offset < k2->offset)
+ return -1;
return 0;
}
+
int btrfs_realloc_node(struct btrfs_trans_handle *trans,
struct btrfs_root *root, struct extent_buffer *parent,
int start_slot, int cache_only, u64 *last_ret,
int parent_level;
int uptodate;
u32 blocksize;
+ int progress_passed = 0;
+ struct btrfs_disk_key disk_key;
+
+ parent_level = btrfs_header_level(parent);
+ if (cache_only && parent_level != 1)
+ return 0;
if (trans->transaction != root->fs_info->running_transaction) {
printk(KERN_CRIT "trans %Lu running %Lu\n", trans->transid,
root->fs_info->generation);
WARN_ON(1);
}
- parent_level = btrfs_header_level(parent);
parent_nritems = btrfs_header_nritems(parent);
blocksize = btrfs_level_size(root, parent_level - 1);
if (parent_nritems == 1)
return 0;
- if (root != root->fs_info->extent_root) {
- struct btrfs_key first_key;
- struct btrfs_key last_key;
-
- btrfs_node_key_to_cpu(parent, &first_key, 0);
- btrfs_node_key_to_cpu(parent, &last_key, parent_nritems - 1);
- if (first_key.objectid != last_key.objectid)
- return 0;
- }
-
for (i = start_slot; i < end_slot; i++) {
int close = 1;
+ if (!parent->map_token) {
+ map_extent_buffer(parent,
+ btrfs_node_key_ptr_offset(i),
+ sizeof(struct btrfs_key_ptr),
+ &parent->map_token, &parent->kaddr,
+ &parent->map_start, &parent->map_len,
+ KM_USER1);
+ }
+ btrfs_node_key(parent, &disk_key, i);
+ if (!progress_passed && comp_keys(&disk_key, progress) < 0)
+ continue;
+
+ progress_passed = 1;
blocknr = btrfs_node_blockptr(parent, i);
if (last_block == 0)
last_block = blocknr;
+
if (i > 0) {
other = btrfs_node_blockptr(parent, i - 1);
close = close_blocks(blocknr, other, blocksize);
}
- if (close && i < end_slot - 1) {
+ if (close && i < end_slot - 2) {
other = btrfs_node_blockptr(parent, i + 1);
close = close_blocks(blocknr, other, blocksize);
}
last_block = blocknr;
continue;
}
+ if (parent->map_token) {
+ unmap_extent_buffer(parent, parent->map_token,
+ KM_USER1);
+ parent->map_token = NULL;
+ }
cur = btrfs_find_tree_block(root, blocknr, blocksize);
if (cur)
uptodate = btrfs_buffer_uptodate(cur);
else
uptodate = 0;
- if (!cur || !uptodate ||
- (parent_level != 1 && !btrfs_buffer_defrag(cur)) ||
- (parent_level == 1 && !should_defrag_leaf(cur))) {
+ if (!cur || !uptodate) {
if (cache_only) {
free_extent_buffer(cur);
continue;
break;
}
search_start = tmp->start;
+ last_block = tmp->start;
*last_ret = search_start;
if (parent_level == 1)
btrfs_clear_buffer_defrag(tmp);
free_extent_buffer(tmp);
}
+ if (parent->map_token) {
+ unmap_extent_buffer(parent, parent->map_token,
+ KM_USER1);
+ parent->map_token = NULL;
+ }
return err;
}
return btrfs_item_offset_nr(leaf, nr - 1);
}
-/*
- * compare two keys in a memcmp fashion
- */
-static int comp_keys(struct btrfs_disk_key *disk, struct btrfs_key *k2)
-{
- struct btrfs_key k1;
-
- btrfs_disk_key_to_cpu(&k1, disk);
-
- if (k1.objectid > k2->objectid)
- return 1;
- if (k1.objectid < k2->objectid)
- return -1;
- if (k1.type > k2->type)
- return 1;
- if (k1.type < k2->type)
- return -1;
- if (k1.offset > k2->offset)
- return 1;
- if (k1.offset < k2->offset)
- return -1;
- return 0;
-}
-
static int check_node(struct btrfs_root *root, struct btrfs_path *path,
int level)
{
* room, 0 if everything worked out and < 0 if there were major errors.
*/
static int push_leaf_right(struct btrfs_trans_handle *trans, struct btrfs_root
- *root, struct btrfs_path *path, int data_size)
+ *root, struct btrfs_path *path, int data_size,
+ int empty)
{
struct extent_buffer *left = path->nodes[0];
struct extent_buffer *right;
struct extent_buffer *upper;
struct btrfs_disk_key disk_key;
int slot;
- int i;
+ u32 i;
int free_space;
int push_space = 0;
int push_items = 0;
struct btrfs_item *item;
u32 left_nritems;
+ u32 nr;
u32 right_nritems;
u32 data_end;
u32 this_item_size;
return 1;
}
- for (i = left_nritems - 1; i >= 1; i--) {
+ if (empty)
+ nr = 0;
+ else
+ nr = 1;
+
+ i = left_nritems - 1;
+ while (i >= nr) {
item = btrfs_item_nr(left, i);
if (path->slots[0] == i)
break;
push_items++;
push_space += this_item_size + sizeof(*item);
+ if (i == 0)
+ break;
+ i--;
}
if (left->map_token) {
unmap_extent_buffer(left, left->map_token, KM_USER1);
return 1;
}
- if (push_items == left_nritems)
+ if (!empty && push_items == left_nritems)
WARN_ON(1);
/* push left to right */
right_nritems = btrfs_header_nritems(right);
+
push_space = btrfs_item_end_nr(left, left_nritems - push_items);
push_space -= leaf_data_end(root, left);
right_nritems += push_items;
btrfs_set_header_nritems(right, right_nritems);
push_space = BTRFS_LEAF_DATA_SIZE(root);
-
for (i = 0; i < right_nritems; i++) {
item = btrfs_item_nr(right, i);
if (!right->map_token) {
left_nritems -= push_items;
btrfs_set_header_nritems(left, left_nritems);
- btrfs_mark_buffer_dirty(left);
+ if (left_nritems)
+ btrfs_mark_buffer_dirty(left);
btrfs_mark_buffer_dirty(right);
btrfs_item_key(right, &disk_key, 0);
* least data_size bytes. returns zero if the push worked, nonzero otherwise
*/
static int push_leaf_left(struct btrfs_trans_handle *trans, struct btrfs_root
- *root, struct btrfs_path *path, int data_size)
+ *root, struct btrfs_path *path, int data_size,
+ int empty)
{
struct btrfs_disk_key disk_key;
struct extent_buffer *right = path->nodes[0];
struct btrfs_item *item;
u32 old_left_nritems;
u32 right_nritems;
+ u32 nr;
int ret = 0;
int wret;
u32 this_item_size;
return 1;
}
- for (i = 0; i < right_nritems - 1; i++) {
+ if (empty)
+ nr = right_nritems;
+ else
+ nr = right_nritems - 1;
+
+ for (i = 0; i < nr; i++) {
item = btrfs_item_nr(right, i);
if (!right->map_token) {
map_extent_buffer(right, (unsigned long)item,
free_extent_buffer(left);
return 1;
}
- if (push_items == btrfs_header_nritems(right))
+ if (!empty && push_items == btrfs_header_nritems(right))
WARN_ON(1);
/* push data from right to left */
}
/* fixup right node */
- push_space = btrfs_item_offset_nr(right, push_items - 1) -
- leaf_data_end(root, right);
- memmove_extent_buffer(right, btrfs_leaf_data(right) +
- BTRFS_LEAF_DATA_SIZE(root) - push_space,
- btrfs_leaf_data(right) +
- leaf_data_end(root, right), push_space);
-
- memmove_extent_buffer(right, btrfs_item_nr_offset(0),
+ if (push_items > right_nritems) {
+ printk("push items %d nr %u\n", push_items, right_nritems);
+ WARN_ON(1);
+ }
+
+ if (push_items < right_nritems) {
+ push_space = btrfs_item_offset_nr(right, push_items - 1) -
+ leaf_data_end(root, right);
+ memmove_extent_buffer(right, btrfs_leaf_data(right) +
+ BTRFS_LEAF_DATA_SIZE(root) - push_space,
+ btrfs_leaf_data(right) +
+ leaf_data_end(root, right), push_space);
+
+ memmove_extent_buffer(right, btrfs_item_nr_offset(0),
btrfs_item_nr_offset(push_items),
(btrfs_header_nritems(right) - push_items) *
sizeof(struct btrfs_item));
- right_nritems = btrfs_header_nritems(right) - push_items;
- btrfs_set_header_nritems(right, right_nritems);
+ }
+ btrfs_set_header_nritems(right, right_nritems - push_items);
push_space = BTRFS_LEAF_DATA_SIZE(root);
for (i = 0; i < right_nritems; i++) {
}
btrfs_mark_buffer_dirty(left);
- btrfs_mark_buffer_dirty(right);
+ if (right_nritems)
+ btrfs_mark_buffer_dirty(right);
btrfs_item_key(right, &disk_key, 0);
wret = fixup_low_keys(trans, root, path, &disk_key, 1);
/* first try to make some room by pushing left and right */
if (ins_key->type != BTRFS_DIR_ITEM_KEY) {
- wret = push_leaf_right(trans, root, path, data_size);
+ wret = push_leaf_right(trans, root, path, data_size, 0);
if (wret < 0) {
return wret;
}
if (wret) {
- wret = push_leaf_left(trans, root, path, data_size);
+ wret = push_leaf_left(trans, root, path, data_size, 0);
if (wret < 0)
return wret;
}
int btrfs_truncate_item(struct btrfs_trans_handle *trans,
struct btrfs_root *root,
struct btrfs_path *path,
- u32 new_size)
+ u32 new_size, int from_end)
{
int ret = 0;
int slot;
slot_orig = path->slots[0];
leaf = path->nodes[0];
+ slot = path->slots[0];
+
+ old_size = btrfs_item_size_nr(leaf, slot);
+ if (old_size == new_size)
+ return 0;
nritems = btrfs_header_nritems(leaf);
data_end = leaf_data_end(root, leaf);
- slot = path->slots[0];
old_data_start = btrfs_item_offset_nr(leaf, slot);
- old_size = btrfs_item_size_nr(leaf, slot); BUG_ON(old_size <= new_size);
+
size_diff = old_size - new_size;
BUG_ON(slot < 0);
}
/* shift the data */
- memmove_extent_buffer(leaf, btrfs_leaf_data(leaf) +
- data_end + size_diff, btrfs_leaf_data(leaf) +
- data_end, old_data_start + new_size - data_end);
+ if (from_end) {
+ memmove_extent_buffer(leaf, btrfs_leaf_data(leaf) +
+ data_end + size_diff, btrfs_leaf_data(leaf) +
+ data_end, old_data_start + new_size - data_end);
+ } else {
+ struct btrfs_disk_key disk_key;
+ u64 offset;
+
+ btrfs_item_key(leaf, &disk_key, slot);
+
+ if (btrfs_disk_key_type(&disk_key) == BTRFS_EXTENT_DATA_KEY) {
+ unsigned long ptr;
+ struct btrfs_file_extent_item *fi;
+
+ fi = btrfs_item_ptr(leaf, slot,
+ struct btrfs_file_extent_item);
+ fi = (struct btrfs_file_extent_item *)(
+ (unsigned long)fi - size_diff);
+
+ if (btrfs_file_extent_type(leaf, fi) ==
+ BTRFS_FILE_EXTENT_INLINE) {
+ ptr = btrfs_item_ptr_offset(leaf, slot);
+ memmove_extent_buffer(leaf, ptr,
+ (unsigned long)fi,
+ offsetof(struct btrfs_file_extent_item,
+ disk_bytenr));
+ }
+ }
+
+ memmove_extent_buffer(leaf, btrfs_leaf_data(leaf) +
+ data_end + size_diff, btrfs_leaf_data(leaf) +
+ data_end, old_data_start - data_end);
+
+ offset = btrfs_disk_key_offset(&disk_key);
+ btrfs_set_disk_key_offset(&disk_key, offset + size_diff);
+ btrfs_set_item_key(leaf, &disk_key, slot);
+ if (slot == 0)
+ fixup_low_keys(trans, root, path, &disk_key, 1);
+ }
item = btrfs_item_nr(leaf, slot);
btrfs_set_item_size(leaf, item, new_size);
slot = path->slots[1];
extent_buffer_get(leaf);
- wret = push_leaf_right(trans, root, path, 1);
+ wret = push_leaf_right(trans, root, path, 1, 1);
if (wret < 0 && wret != -ENOSPC)
ret = wret;
if (path->nodes[0] == leaf &&
btrfs_header_nritems(leaf)) {
- wret = push_leaf_left(trans, root, path, 1);
+ wret = push_leaf_left(trans, root, path, 1, 1);
if (wret < 0 && wret != -ENOSPC)
ret = wret;
}