aboutsummaryrefslogtreecommitdiffstats
path: root/fs/btrfs/ctree.c
diff options
context:
space:
mode:
authorChris Mason <chris.mason@oracle.com>2007-10-15 16:14:19 -0400
committerChris Mason <chris.mason@oracle.com>2008-09-25 11:03:56 -0400
commit5f39d397dfbe140a14edecd4e73c34ce23c4f9ee (patch)
tree280561e4b68d573590557dd27df656869eed8023 /fs/btrfs/ctree.c
parent50b78c24d594e6985f36a9a8d8e2fb74e1664e90 (diff)
Btrfs: Create extent_buffer interface for large blocksizes
Signed-off-by: Chris Mason <chris.mason@oracle.com>
Diffstat (limited to 'fs/btrfs/ctree.c')
-rw-r--r--fs/btrfs/ctree.c1484
1 files changed, 817 insertions, 667 deletions
diff --git a/fs/btrfs/ctree.c b/fs/btrfs/ctree.c
index b41f48ade419..f60920e8a0e0 100644
--- a/fs/btrfs/ctree.c
+++ b/fs/btrfs/ctree.c
@@ -16,21 +16,24 @@
16 * Boston, MA 021110-1307, USA. 16 * Boston, MA 021110-1307, USA.
17 */ 17 */
18 18
19#include <linux/highmem.h>
19#include "ctree.h" 20#include "ctree.h"
20#include "disk-io.h" 21#include "disk-io.h"
21#include "transaction.h" 22#include "transaction.h"
23#include "print-tree.h"
22 24
23static int split_node(struct btrfs_trans_handle *trans, struct btrfs_root 25static int split_node(struct btrfs_trans_handle *trans, struct btrfs_root
24 *root, struct btrfs_path *path, int level); 26 *root, struct btrfs_path *path, int level);
25static int split_leaf(struct btrfs_trans_handle *trans, struct btrfs_root 27static int split_leaf(struct btrfs_trans_handle *trans, struct btrfs_root
26 *root, struct btrfs_key *ins_key, 28 *root, struct btrfs_key *ins_key,
27 struct btrfs_path *path, int data_size); 29 struct btrfs_path *path, int data_size);
28static int push_node_left(struct btrfs_trans_handle *trans, struct btrfs_root 30static int push_node_left(struct btrfs_trans_handle *trans,
29 *root, struct buffer_head *dst, struct buffer_head 31 struct btrfs_root *root, struct extent_buffer *dst,
30 *src); 32 struct extent_buffer *src);
31static int balance_node_right(struct btrfs_trans_handle *trans, struct 33static int balance_node_right(struct btrfs_trans_handle *trans,
32 btrfs_root *root, struct buffer_head *dst_buf, 34 struct btrfs_root *root,
33 struct buffer_head *src_buf); 35 struct extent_buffer *dst_buf,
36 struct extent_buffer *src_buf);
34static int del_ptr(struct btrfs_trans_handle *trans, struct btrfs_root *root, 37static int del_ptr(struct btrfs_trans_handle *trans, struct btrfs_root *root,
35 struct btrfs_path *path, int level, int slot); 38 struct btrfs_path *path, int level, int slot);
36 39
@@ -62,40 +65,38 @@ void btrfs_release_path(struct btrfs_root *root, struct btrfs_path *p)
62 for (i = 0; i < BTRFS_MAX_LEVEL; i++) { 65 for (i = 0; i < BTRFS_MAX_LEVEL; i++) {
63 if (!p->nodes[i]) 66 if (!p->nodes[i])
64 break; 67 break;
65 btrfs_block_release(root, p->nodes[i]); 68 free_extent_buffer(p->nodes[i]);
66 } 69 }
67 memset(p, 0, sizeof(*p)); 70 memset(p, 0, sizeof(*p));
68} 71}
69 72
70static int __btrfs_cow_block(struct btrfs_trans_handle *trans, struct btrfs_root 73static int __btrfs_cow_block(struct btrfs_trans_handle *trans,
71 *root, struct buffer_head *buf, struct buffer_head 74 struct btrfs_root *root,
72 *parent, int parent_slot, struct buffer_head 75 struct extent_buffer *buf,
73 **cow_ret, u64 search_start, u64 empty_size) 76 struct extent_buffer *parent, int parent_slot,
77 struct extent_buffer **cow_ret,
78 u64 search_start, u64 empty_size)
74{ 79{
75 struct buffer_head *cow; 80 struct extent_buffer *cow;
76 struct btrfs_node *cow_node;
77 int ret = 0; 81 int ret = 0;
78 int different_trans = 0; 82 int different_trans = 0;
79 83
80 WARN_ON(root->ref_cows && trans->transid != root->last_trans); 84 WARN_ON(root->ref_cows && trans->transid != root->last_trans);
81 WARN_ON(!buffer_uptodate(buf)); 85
82 cow = btrfs_alloc_free_block(trans, root, search_start, empty_size); 86 cow = btrfs_alloc_free_block(trans, root, search_start, empty_size);
83 if (IS_ERR(cow)) 87 if (IS_ERR(cow))
84 return PTR_ERR(cow); 88 return PTR_ERR(cow);
85 89
86 cow_node = btrfs_buffer_node(cow); 90 if (buf->len != root->sectorsize || cow->len != root->sectorsize)
87 if (buf->b_size != root->blocksize || cow->b_size != root->blocksize)
88 WARN_ON(1); 91 WARN_ON(1);
89 92
90 memcpy(cow_node, btrfs_buffer_node(buf), root->blocksize); 93 copy_extent_buffer(cow, buf, 0, 0, cow->len);
91 btrfs_set_header_blocknr(&cow_node->header, bh_blocknr(cow)); 94 btrfs_set_header_blocknr(cow, extent_buffer_blocknr(cow));
92 btrfs_set_header_generation(&cow_node->header, trans->transid); 95 btrfs_set_header_generation(cow, trans->transid);
93 btrfs_set_header_owner(&cow_node->header, root->root_key.objectid); 96 btrfs_set_header_owner(cow, root->root_key.objectid);
94 97
95 WARN_ON(btrfs_header_generation(btrfs_buffer_header(buf)) > 98 WARN_ON(btrfs_header_generation(buf) > trans->transid);
96 trans->transid); 99 if (btrfs_header_generation(buf) != trans->transid) {
97 if (btrfs_header_generation(btrfs_buffer_header(buf)) !=
98 trans->transid) {
99 different_trans = 1; 100 different_trans = 1;
100 ret = btrfs_inc_ref(trans, root, buf); 101 ret = btrfs_inc_ref(trans, root, buf);
101 if (ret) 102 if (ret)
@@ -106,29 +107,29 @@ static int __btrfs_cow_block(struct btrfs_trans_handle *trans, struct btrfs_root
106 107
107 if (buf == root->node) { 108 if (buf == root->node) {
108 root->node = cow; 109 root->node = cow;
109 get_bh(cow); 110 extent_buffer_get(cow);
110 if (buf != root->commit_root) { 111 if (buf != root->commit_root) {
111 btrfs_free_extent(trans, root, bh_blocknr(buf), 1, 1); 112 btrfs_free_extent(trans, root,
113 extent_buffer_blocknr(buf), 1, 1);
112 } 114 }
113 btrfs_block_release(root, buf); 115 free_extent_buffer(buf);
114 } else { 116 } else {
115 btrfs_set_node_blockptr(btrfs_buffer_node(parent), parent_slot, 117 btrfs_set_node_blockptr(parent, parent_slot,
116 bh_blocknr(cow)); 118 extent_buffer_blocknr(cow));
117 btrfs_mark_buffer_dirty(parent); 119 btrfs_mark_buffer_dirty(parent);
118 WARN_ON(btrfs_header_generation(btrfs_buffer_header(parent)) != 120 WARN_ON(btrfs_header_generation(parent) != trans->transid);
119 trans->transid); 121 btrfs_free_extent(trans, root, extent_buffer_blocknr(buf),1,1);
120 btrfs_free_extent(trans, root, bh_blocknr(buf), 1, 1);
121 } 122 }
122 btrfs_block_release(root, buf); 123 free_extent_buffer(buf);
123 btrfs_mark_buffer_dirty(cow); 124 btrfs_mark_buffer_dirty(cow);
124 *cow_ret = cow; 125 *cow_ret = cow;
125 return 0; 126 return 0;
126} 127}
127 128
128int btrfs_cow_block(struct btrfs_trans_handle *trans, struct btrfs_root 129int btrfs_cow_block(struct btrfs_trans_handle *trans,
129 *root, struct buffer_head *buf, struct buffer_head 130 struct btrfs_root *root, struct extent_buffer *buf,
130 *parent, int parent_slot, struct buffer_head 131 struct extent_buffer *parent, int parent_slot,
131 **cow_ret) 132 struct extent_buffer **cow_ret)
132{ 133{
133 u64 search_start; 134 u64 search_start;
134 if (trans->transaction != root->fs_info->running_transaction) { 135 if (trans->transaction != root->fs_info->running_transaction) {
@@ -141,13 +142,12 @@ int btrfs_cow_block(struct btrfs_trans_handle *trans, struct btrfs_root
141 root->fs_info->generation); 142 root->fs_info->generation);
142 WARN_ON(1); 143 WARN_ON(1);
143 } 144 }
144 if (btrfs_header_generation(btrfs_buffer_header(buf)) == 145 if (btrfs_header_generation(buf) == trans->transid) {
145 trans->transid) {
146 *cow_ret = buf; 146 *cow_ret = buf;
147 return 0; 147 return 0;
148 } 148 }
149 149
150 search_start = bh_blocknr(buf) & ~((u64)65535); 150 search_start = extent_buffer_blocknr(buf) & ~((u64)65535);
151 return __btrfs_cow_block(trans, root, buf, parent, 151 return __btrfs_cow_block(trans, root, buf, parent,
152 parent_slot, cow_ret, search_start, 0); 152 parent_slot, cow_ret, search_start, 0);
153} 153}
@@ -161,9 +161,11 @@ static int close_blocks(u64 blocknr, u64 other)
161 return 0; 161 return 0;
162} 162}
163 163
164static int should_defrag_leaf(struct buffer_head *bh) 164#if 0
165static int should_defrag_leaf(struct extent_buffer *eb)
165{ 166{
166 struct btrfs_leaf *leaf = btrfs_buffer_leaf(bh); 167 return 0;
168 struct btrfs_leaf *leaf = btrfs_buffer_leaf(eb);
167 struct btrfs_disk_key *key; 169 struct btrfs_disk_key *key;
168 u32 nritems; 170 u32 nritems;
169 171
@@ -188,14 +190,17 @@ static int should_defrag_leaf(struct buffer_head *bh)
188 } 190 }
189 return 0; 191 return 0;
190} 192}
193#endif
191 194
192int btrfs_realloc_node(struct btrfs_trans_handle *trans, 195int btrfs_realloc_node(struct btrfs_trans_handle *trans,
193 struct btrfs_root *root, struct buffer_head *parent, 196 struct btrfs_root *root, struct extent_buffer *parent,
194 int cache_only, u64 *last_ret) 197 int cache_only, u64 *last_ret)
195{ 198{
199 return 0;
200#if 0
196 struct btrfs_node *parent_node; 201 struct btrfs_node *parent_node;
197 struct buffer_head *cur_bh; 202 struct extent_buffer *cur_eb;
198 struct buffer_head *tmp_bh; 203 struct extent_buffer *tmp_eb;
199 u64 blocknr; 204 u64 blocknr;
200 u64 search_start = *last_ret; 205 u64 search_start = *last_ret;
201 u64 last_block = 0; 206 u64 last_block = 0;
@@ -281,6 +286,7 @@ int btrfs_realloc_node(struct btrfs_trans_handle *trans,
281 brelse(tmp_bh); 286 brelse(tmp_bh);
282 } 287 }
283 return err; 288 return err;
289#endif
284} 290}
285 291
286/* 292/*
@@ -289,12 +295,12 @@ int btrfs_realloc_node(struct btrfs_trans_handle *trans,
289 * which is the stop of the leaf data stack 295 * which is the stop of the leaf data stack
290 */ 296 */
291static inline unsigned int leaf_data_end(struct btrfs_root *root, 297static inline unsigned int leaf_data_end(struct btrfs_root *root,
292 struct btrfs_leaf *leaf) 298 struct extent_buffer *leaf)
293{ 299{
294 u32 nr = btrfs_header_nritems(&leaf->header); 300 u32 nr = btrfs_header_nritems(leaf);
295 if (nr == 0) 301 if (nr == 0)
296 return BTRFS_LEAF_DATA_SIZE(root); 302 return BTRFS_LEAF_DATA_SIZE(root);
297 return btrfs_item_offset(leaf->items + nr - 1); 303 return btrfs_item_offset_nr(leaf, nr - 1);
298} 304}
299 305
300/* 306/*
@@ -310,9 +316,9 @@ static int comp_keys(struct btrfs_disk_key *disk, struct btrfs_key *k2)
310 return 1; 316 return 1;
311 if (k1.objectid < k2->objectid) 317 if (k1.objectid < k2->objectid)
312 return -1; 318 return -1;
313 if (k1.flags > k2->flags) 319 if (k1.type > k2->type)
314 return 1; 320 return 1;
315 if (k1.flags < k2->flags) 321 if (k1.type < k2->type)
316 return -1; 322 return -1;
317 if (k1.offset > k2->offset) 323 if (k1.offset > k2->offset)
318 return 1; 324 return 1;
@@ -324,37 +330,39 @@ static int comp_keys(struct btrfs_disk_key *disk, struct btrfs_key *k2)
324static int check_node(struct btrfs_root *root, struct btrfs_path *path, 330static int check_node(struct btrfs_root *root, struct btrfs_path *path,
325 int level) 331 int level)
326{ 332{
327 struct btrfs_node *parent = NULL; 333 struct extent_buffer *parent = NULL;
328 struct btrfs_node *node = btrfs_buffer_node(path->nodes[level]); 334 struct extent_buffer *node = path->nodes[level];
335 struct btrfs_disk_key parent_key;
336 struct btrfs_disk_key node_key;
329 int parent_slot; 337 int parent_slot;
330 int slot; 338 int slot;
331 struct btrfs_key cpukey; 339 struct btrfs_key cpukey;
332 u32 nritems = btrfs_header_nritems(&node->header); 340 u32 nritems = btrfs_header_nritems(node);
333 341
334 if (path->nodes[level + 1]) 342 if (path->nodes[level + 1])
335 parent = btrfs_buffer_node(path->nodes[level + 1]); 343 parent = path->nodes[level + 1];
336 344
337 slot = path->slots[level]; 345 slot = path->slots[level];
338 BUG_ON(!buffer_uptodate(path->nodes[level]));
339 BUG_ON(nritems == 0); 346 BUG_ON(nritems == 0);
340 if (parent) { 347 if (parent) {
341 struct btrfs_disk_key *parent_key;
342
343 parent_slot = path->slots[level + 1]; 348 parent_slot = path->slots[level + 1];
344 parent_key = &parent->ptrs[parent_slot].key; 349 btrfs_node_key(parent, &parent_key, parent_slot);
345 BUG_ON(memcmp(parent_key, &node->ptrs[0].key, 350 btrfs_node_key(node, &node_key, 0);
351 BUG_ON(memcmp(&parent_key, &node_key,
346 sizeof(struct btrfs_disk_key))); 352 sizeof(struct btrfs_disk_key)));
347 BUG_ON(btrfs_node_blockptr(parent, parent_slot) != 353 BUG_ON(btrfs_node_blockptr(parent, parent_slot) !=
348 btrfs_header_blocknr(&node->header)); 354 btrfs_header_blocknr(node));
349 } 355 }
350 BUG_ON(nritems > BTRFS_NODEPTRS_PER_BLOCK(root)); 356 BUG_ON(nritems > BTRFS_NODEPTRS_PER_BLOCK(root));
351 if (slot != 0) { 357 if (slot != 0) {
352 btrfs_disk_key_to_cpu(&cpukey, &node->ptrs[slot - 1].key); 358 btrfs_node_key_to_cpu(node, &cpukey, slot - 1);
353 BUG_ON(comp_keys(&node->ptrs[slot].key, &cpukey) <= 0); 359 btrfs_node_key(node, &node_key, slot);
360 BUG_ON(comp_keys(&node_key, &cpukey) <= 0);
354 } 361 }
355 if (slot < nritems - 1) { 362 if (slot < nritems - 1) {
356 btrfs_disk_key_to_cpu(&cpukey, &node->ptrs[slot + 1].key); 363 btrfs_node_key_to_cpu(node, &cpukey, slot + 1);
357 BUG_ON(comp_keys(&node->ptrs[slot].key, &cpukey) >= 0); 364 btrfs_node_key(node, &node_key, slot);
365 BUG_ON(comp_keys(&node_key, &cpukey) >= 0);
358 } 366 }
359 return 0; 367 return 0;
360} 368}
@@ -362,83 +370,172 @@ static int check_node(struct btrfs_root *root, struct btrfs_path *path,
362static int check_leaf(struct btrfs_root *root, struct btrfs_path *path, 370static int check_leaf(struct btrfs_root *root, struct btrfs_path *path,
363 int level) 371 int level)
364{ 372{
365 struct btrfs_leaf *leaf = btrfs_buffer_leaf(path->nodes[level]); 373 struct extent_buffer *leaf = path->nodes[level];
366 struct btrfs_node *parent = NULL; 374 struct extent_buffer *parent = NULL;
367 int parent_slot; 375 int parent_slot;
368 int slot = path->slots[0];
369 struct btrfs_key cpukey; 376 struct btrfs_key cpukey;
377 struct btrfs_disk_key parent_key;
378 struct btrfs_disk_key leaf_key;
379 int slot = path->slots[0];
370 380
371 u32 nritems = btrfs_header_nritems(&leaf->header); 381 u32 nritems = btrfs_header_nritems(leaf);
372 382
373 if (path->nodes[level + 1]) 383 if (path->nodes[level + 1])
374 parent = btrfs_buffer_node(path->nodes[level + 1]); 384 parent = path->nodes[level + 1];
375
376 BUG_ON(btrfs_leaf_free_space(root, leaf) < 0);
377 385
378 if (nritems == 0) 386 if (nritems == 0)
379 return 0; 387 return 0;
380 388
381 if (parent) { 389 if (parent) {
382 struct btrfs_disk_key *parent_key;
383
384 parent_slot = path->slots[level + 1]; 390 parent_slot = path->slots[level + 1];
385 parent_key = &parent->ptrs[parent_slot].key; 391 btrfs_node_key(parent, &parent_key, parent_slot);
392 btrfs_item_key(leaf, &leaf_key, 0);
386 393
387 BUG_ON(memcmp(parent_key, &leaf->items[0].key, 394 BUG_ON(memcmp(&parent_key, &leaf_key,
388 sizeof(struct btrfs_disk_key))); 395 sizeof(struct btrfs_disk_key)));
389 BUG_ON(btrfs_node_blockptr(parent, parent_slot) != 396 BUG_ON(btrfs_node_blockptr(parent, parent_slot) !=
390 btrfs_header_blocknr(&leaf->header)); 397 btrfs_header_blocknr(leaf));
398 }
399#if 0
400 for (i = 0; nritems > 1 && i < nritems - 2; i++) {
401 btrfs_item_key_to_cpu(leaf, &cpukey, i + 1);
402 btrfs_item_key(leaf, &leaf_key, i);
403 if (comp_keys(&leaf_key, &cpukey) >= 0) {
404 btrfs_print_leaf(root, leaf);
405 printk("slot %d offset bad key\n", i);
406 BUG_ON(1);
407 }
408 if (btrfs_item_offset_nr(leaf, i) !=
409 btrfs_item_end_nr(leaf, i + 1)) {
410 btrfs_print_leaf(root, leaf);
411 printk("slot %d offset bad\n", i);
412 BUG_ON(1);
413 }
414 if (i == 0) {
415 if (btrfs_item_offset_nr(leaf, i) +
416 btrfs_item_size_nr(leaf, i) !=
417 BTRFS_LEAF_DATA_SIZE(root)) {
418 btrfs_print_leaf(root, leaf);
419 printk("slot %d first offset bad\n", i);
420 BUG_ON(1);
421 }
422 }
391 } 423 }
392 if (slot != 0) { 424 if (nritems > 0) {
393 btrfs_disk_key_to_cpu(&cpukey, &leaf->items[slot - 1].key); 425 if (btrfs_item_size_nr(leaf, nritems - 1) > 4096) {
394 BUG_ON(comp_keys(&leaf->items[slot].key, &cpukey) <= 0); 426 btrfs_print_leaf(root, leaf);
395 BUG_ON(btrfs_item_offset(leaf->items + slot - 1) != 427 printk("slot %d bad size \n", nritems - 1);
396 btrfs_item_end(leaf->items + slot)); 428 BUG_ON(1);
429 }
430 }
431#endif
432 if (slot != 0 && slot < nritems - 1) {
433 btrfs_item_key(leaf, &leaf_key, slot);
434 btrfs_item_key_to_cpu(leaf, &cpukey, slot - 1);
435 if (comp_keys(&leaf_key, &cpukey) <= 0) {
436 btrfs_print_leaf(root, leaf);
437 printk("slot %d offset bad key\n", slot);
438 BUG_ON(1);
439 }
440 if (btrfs_item_offset_nr(leaf, slot - 1) !=
441 btrfs_item_end_nr(leaf, slot)) {
442 btrfs_print_leaf(root, leaf);
443 printk("slot %d offset bad\n", slot);
444 BUG_ON(1);
445 }
397 } 446 }
398 if (slot < nritems - 1) { 447 if (slot < nritems - 1) {
399 btrfs_disk_key_to_cpu(&cpukey, &leaf->items[slot + 1].key); 448 btrfs_item_key(leaf, &leaf_key, slot);
400 BUG_ON(comp_keys(&leaf->items[slot].key, &cpukey) >= 0); 449 btrfs_item_key_to_cpu(leaf, &cpukey, slot + 1);
401 BUG_ON(btrfs_item_offset(leaf->items + slot) != 450 BUG_ON(comp_keys(&leaf_key, &cpukey) >= 0);
402 btrfs_item_end(leaf->items + slot + 1)); 451 if (btrfs_item_offset_nr(leaf, slot) !=
452 btrfs_item_end_nr(leaf, slot + 1)) {
453 btrfs_print_leaf(root, leaf);
454 printk("slot %d offset bad\n", slot);
455 BUG_ON(1);
456 }
403 } 457 }
404 BUG_ON(btrfs_item_offset(leaf->items) + 458 BUG_ON(btrfs_item_offset_nr(leaf, 0) +
405 btrfs_item_size(leaf->items) != BTRFS_LEAF_DATA_SIZE(root)); 459 btrfs_item_size_nr(leaf, 0) != BTRFS_LEAF_DATA_SIZE(root));
406 return 0; 460 return 0;
407} 461}
408 462
409static int check_block(struct btrfs_root *root, struct btrfs_path *path, 463static int check_block(struct btrfs_root *root, struct btrfs_path *path,
410 int level) 464 int level)
411{ 465{
412 struct btrfs_node *node = btrfs_buffer_node(path->nodes[level]); 466 struct extent_buffer *buf = path->nodes[level];
413 if (memcmp(node->header.fsid, root->fs_info->disk_super->fsid, 467 char fsid[BTRFS_FSID_SIZE];
414 sizeof(node->header.fsid))) 468
415 BUG(); 469 read_extent_buffer(buf, fsid, (unsigned long)btrfs_header_fsid(buf),
470 BTRFS_FSID_SIZE);
471
472 if (memcmp(fsid, root->fs_info->fsid, BTRFS_FSID_SIZE)) {
473 int i = 0;
474 printk("warning bad block %Lu\n", buf->start);
475 if (!btrfs_buffer_uptodate(buf)) {
476 WARN_ON(1);
477 }
478 for (i = 0; i < BTRFS_FSID_SIZE; i++) {
479 printk("%x:%x ", root->fs_info->fsid[i], fsid[i]);
480 }
481 printk("\n");
482 // BUG();
483 }
416 if (level == 0) 484 if (level == 0)
417 return check_leaf(root, path, level); 485 return check_leaf(root, path, level);
418 return check_node(root, path, level); 486 return check_node(root, path, level);
419} 487}
420 488
421/* 489/*
422 * search for key in the array p. items p are item_size apart 490 * search for key in the extent_buffer. The items start at offset p,
423 * and there are 'max' items in p 491 * and they are item_size apart. There are 'max' items in p.
492 *
424 * the slot in the array is returned via slot, and it points to 493 * the slot in the array is returned via slot, and it points to
425 * the place where you would insert key if it is not found in 494 * the place where you would insert key if it is not found in
426 * the array. 495 * the array.
427 * 496 *
428 * slot may point to max if the key is bigger than all of the keys 497 * slot may point to max if the key is bigger than all of the keys
429 */ 498 */
430static int generic_bin_search(char *p, int item_size, struct btrfs_key *key, 499static int generic_bin_search(struct extent_buffer *eb, unsigned long p,
431 int max, int *slot) 500 int item_size, struct btrfs_key *key,
501 int max, int *slot)
432{ 502{
433 int low = 0; 503 int low = 0;
434 int high = max; 504 int high = max;
435 int mid; 505 int mid;
436 int ret; 506 int ret;
437 struct btrfs_disk_key *tmp; 507 struct btrfs_disk_key *tmp;
508 struct btrfs_disk_key unaligned;
509 unsigned long offset;
510 char *map_token = NULL;
511 char *kaddr = NULL;
512 unsigned long map_start = 0;
513 unsigned long map_len = 0;
438 514
439 while(low < high) { 515 while(low < high) {
440 mid = (low + high) / 2; 516 mid = (low + high) / 2;
441 tmp = (struct btrfs_disk_key *)(p + mid * item_size); 517 offset = p + mid * item_size;
518
519 if (!map_token || offset < map_start ||
520 (offset + sizeof(struct btrfs_disk_key)) >
521 map_start + map_len) {
522 if (map_token)
523 unmap_extent_buffer(eb, map_token, KM_USER0);
524 map_extent_buffer(eb, offset, &map_token, &kaddr,
525 &map_start, &map_len, KM_USER0);
526
527 }
528 if (offset + sizeof(struct btrfs_disk_key) >
529 map_start + map_len) {
530 unmap_extent_buffer(eb, map_token, KM_USER0);
531 read_extent_buffer(eb, &unaligned,
532 offset, sizeof(unaligned));
533 map_token = NULL;
534 tmp = &unaligned;
535 } else {
536 tmp = (struct btrfs_disk_key *)(kaddr + offset -
537 map_start);
538 }
442 ret = comp_keys(tmp, key); 539 ret = comp_keys(tmp, key);
443 540
444 if (ret < 0) 541 if (ret < 0)
@@ -447,10 +544,13 @@ static int generic_bin_search(char *p, int item_size, struct btrfs_key *key,
447 high = mid; 544 high = mid;
448 else { 545 else {
449 *slot = mid; 546 *slot = mid;
547 unmap_extent_buffer(eb, map_token, KM_USER0);
450 return 0; 548 return 0;
451 } 549 }
452 } 550 }
453 *slot = low; 551 *slot = low;
552 if (map_token)
553 unmap_extent_buffer(eb, map_token, KM_USER0);
454 return 1; 554 return 1;
455} 555}
456 556
@@ -458,46 +558,42 @@ static int generic_bin_search(char *p, int item_size, struct btrfs_key *key,
458 * simple bin_search frontend that does the right thing for 558 * simple bin_search frontend that does the right thing for
459 * leaves vs nodes 559 * leaves vs nodes
460 */ 560 */
461static int bin_search(struct btrfs_node *c, struct btrfs_key *key, int *slot) 561static int bin_search(struct extent_buffer *eb, struct btrfs_key *key,
562 int level, int *slot)
462{ 563{
463 if (btrfs_is_leaf(c)) { 564 if (level == 0) {
464 struct btrfs_leaf *l = (struct btrfs_leaf *)c; 565 return generic_bin_search(eb,
465 return generic_bin_search((void *)l->items, 566 offsetof(struct btrfs_leaf, items),
466 sizeof(struct btrfs_item), 567 sizeof(struct btrfs_item),
467 key, btrfs_header_nritems(&c->header), 568 key, btrfs_header_nritems(eb),
468 slot); 569 slot);
469 } else { 570 } else {
470 return generic_bin_search((void *)c->ptrs, 571 return generic_bin_search(eb,
572 offsetof(struct btrfs_node, ptrs),
471 sizeof(struct btrfs_key_ptr), 573 sizeof(struct btrfs_key_ptr),
472 key, btrfs_header_nritems(&c->header), 574 key, btrfs_header_nritems(eb),
473 slot); 575 slot);
474 } 576 }
475 return -1; 577 return -1;
476} 578}
477 579
478static struct buffer_head *read_node_slot(struct btrfs_root *root, 580static struct extent_buffer *read_node_slot(struct btrfs_root *root,
479 struct buffer_head *parent_buf, 581 struct extent_buffer *parent, int slot)
480 int slot)
481{ 582{
482 struct btrfs_node *node = btrfs_buffer_node(parent_buf);
483 if (slot < 0) 583 if (slot < 0)
484 return NULL; 584 return NULL;
485 if (slot >= btrfs_header_nritems(&node->header)) 585 if (slot >= btrfs_header_nritems(parent))
486 return NULL; 586 return NULL;
487 return read_tree_block(root, btrfs_node_blockptr(node, slot)); 587 return read_tree_block(root, btrfs_node_blockptr(parent, slot));
488} 588}
489 589
490static int balance_level(struct btrfs_trans_handle *trans, struct btrfs_root 590static int balance_level(struct btrfs_trans_handle *trans, struct btrfs_root
491 *root, struct btrfs_path *path, int level) 591 *root, struct btrfs_path *path, int level)
492{ 592{
493 struct buffer_head *right_buf; 593 struct extent_buffer *right = NULL;
494 struct buffer_head *mid_buf; 594 struct extent_buffer *mid;
495 struct buffer_head *left_buf; 595 struct extent_buffer *left = NULL;
496 struct buffer_head *parent_buf = NULL; 596 struct extent_buffer *parent = NULL;
497 struct btrfs_node *right = NULL;
498 struct btrfs_node *mid;
499 struct btrfs_node *left = NULL;
500 struct btrfs_node *parent = NULL;
501 int ret = 0; 597 int ret = 0;
502 int wret; 598 int wret;
503 int pslot; 599 int pslot;
@@ -508,60 +604,57 @@ static int balance_level(struct btrfs_trans_handle *trans, struct btrfs_root
508 if (level == 0) 604 if (level == 0)
509 return 0; 605 return 0;
510 606
511 mid_buf = path->nodes[level]; 607 mid = path->nodes[level];
512 mid = btrfs_buffer_node(mid_buf);
513 orig_ptr = btrfs_node_blockptr(mid, orig_slot); 608 orig_ptr = btrfs_node_blockptr(mid, orig_slot);
514 609
515 if (level < BTRFS_MAX_LEVEL - 1) 610 if (level < BTRFS_MAX_LEVEL - 1)
516 parent_buf = path->nodes[level + 1]; 611 parent = path->nodes[level + 1];
517 pslot = path->slots[level + 1]; 612 pslot = path->slots[level + 1];
518 613
519 /* 614 /*
520 * deal with the case where there is only one pointer in the root 615 * deal with the case where there is only one pointer in the root
521 * by promoting the node below to a root 616 * by promoting the node below to a root
522 */ 617 */
523 if (!parent_buf) { 618 if (!parent) {
524 struct buffer_head *child; 619 struct extent_buffer *child;
525 u64 blocknr = bh_blocknr(mid_buf); 620 u64 blocknr = extent_buffer_blocknr(mid);
526 621
527 if (btrfs_header_nritems(&mid->header) != 1) 622 if (btrfs_header_nritems(mid) != 1)
528 return 0; 623 return 0;
529 624
530 /* promote the child to a root */ 625 /* promote the child to a root */
531 child = read_node_slot(root, mid_buf, 0); 626 child = read_node_slot(root, mid, 0);
532 BUG_ON(!child); 627 BUG_ON(!child);
533 root->node = child; 628 root->node = child;
534 path->nodes[level] = NULL; 629 path->nodes[level] = NULL;
535 clean_tree_block(trans, root, mid_buf); 630 clean_tree_block(trans, root, mid);
536 wait_on_buffer(mid_buf); 631 wait_on_tree_block_writeback(root, mid);
537 /* once for the path */ 632 /* once for the path */
538 btrfs_block_release(root, mid_buf); 633 free_extent_buffer(mid);
539 /* once for the root ptr */ 634 /* once for the root ptr */
540 btrfs_block_release(root, mid_buf); 635 free_extent_buffer(mid);
541 return btrfs_free_extent(trans, root, blocknr, 1, 1); 636 return btrfs_free_extent(trans, root, blocknr, 1, 1);
542 } 637 }
543 parent = btrfs_buffer_node(parent_buf); 638 if (btrfs_header_nritems(mid) >
544
545 if (btrfs_header_nritems(&mid->header) >
546 BTRFS_NODEPTRS_PER_BLOCK(root) / 4) 639 BTRFS_NODEPTRS_PER_BLOCK(root) / 4)
547 return 0; 640 return 0;
548 641
549 if (btrfs_header_nritems(&mid->header) < 2) 642 if (btrfs_header_nritems(mid) < 2)
550 err_on_enospc = 1; 643 err_on_enospc = 1;
551 644
552 left_buf = read_node_slot(root, parent_buf, pslot - 1); 645 left = read_node_slot(root, parent, pslot - 1);
553 if (left_buf) { 646 if (left) {
554 wret = btrfs_cow_block(trans, root, left_buf, 647 wret = btrfs_cow_block(trans, root, left,
555 parent_buf, pslot - 1, &left_buf); 648 parent, pslot - 1, &left);
556 if (wret) { 649 if (wret) {
557 ret = wret; 650 ret = wret;
558 goto enospc; 651 goto enospc;
559 } 652 }
560 } 653 }
561 right_buf = read_node_slot(root, parent_buf, pslot + 1); 654 right = read_node_slot(root, parent, pslot + 1);
562 if (right_buf) { 655 if (right) {
563 wret = btrfs_cow_block(trans, root, right_buf, 656 wret = btrfs_cow_block(trans, root, right,
564 parent_buf, pslot + 1, &right_buf); 657 parent, pslot + 1, &right);
565 if (wret) { 658 if (wret) {
566 ret = wret; 659 ret = wret;
567 goto enospc; 660 goto enospc;
@@ -569,30 +662,27 @@ static int balance_level(struct btrfs_trans_handle *trans, struct btrfs_root
569 } 662 }
570 663
571 /* first, try to make some room in the middle buffer */ 664 /* first, try to make some room in the middle buffer */
572 if (left_buf) { 665 if (left) {
573 left = btrfs_buffer_node(left_buf); 666 orig_slot += btrfs_header_nritems(left);
574 orig_slot += btrfs_header_nritems(&left->header); 667 wret = push_node_left(trans, root, left, mid);
575 wret = push_node_left(trans, root, left_buf, mid_buf);
576 if (wret < 0) 668 if (wret < 0)
577 ret = wret; 669 ret = wret;
578 if (btrfs_header_nritems(&mid->header) < 2) 670 if (btrfs_header_nritems(mid) < 2)
579 err_on_enospc = 1; 671 err_on_enospc = 1;
580 } 672 }
581 673
582 /* 674 /*
583 * then try to empty the right most buffer into the middle 675 * then try to empty the right most buffer into the middle
584 */ 676 */
585 if (right_buf) { 677 if (right) {
586 right = btrfs_buffer_node(right_buf); 678 wret = push_node_left(trans, root, mid, right);
587 wret = push_node_left(trans, root, mid_buf, right_buf);
588 if (wret < 0 && wret != -ENOSPC) 679 if (wret < 0 && wret != -ENOSPC)
589 ret = wret; 680 ret = wret;
590 if (btrfs_header_nritems(&right->header) == 0) { 681 if (btrfs_header_nritems(right) == 0) {
591 u64 blocknr = bh_blocknr(right_buf); 682 u64 blocknr = extent_buffer_blocknr(right);
592 clean_tree_block(trans, root, right_buf); 683 clean_tree_block(trans, root, right);
593 wait_on_buffer(right_buf); 684 wait_on_tree_block_writeback(root, right);
594 btrfs_block_release(root, right_buf); 685 free_extent_buffer(right);
595 right_buf = NULL;
596 right = NULL; 686 right = NULL;
597 wret = del_ptr(trans, root, path, level + 1, pslot + 687 wret = del_ptr(trans, root, path, level + 1, pslot +
598 1); 688 1);
@@ -602,14 +692,13 @@ static int balance_level(struct btrfs_trans_handle *trans, struct btrfs_root
602 if (wret) 692 if (wret)
603 ret = wret; 693 ret = wret;
604 } else { 694 } else {
605 btrfs_memcpy(root, parent, 695 struct btrfs_disk_key right_key;
606 &parent->ptrs[pslot + 1].key, 696 btrfs_node_key(right, &right_key, 0);
607 &right->ptrs[0].key, 697 btrfs_set_node_key(parent, &right_key, pslot + 1);
608 sizeof(struct btrfs_disk_key)); 698 btrfs_mark_buffer_dirty(parent);
609 btrfs_mark_buffer_dirty(parent_buf);
610 } 699 }
611 } 700 }
612 if (btrfs_header_nritems(&mid->header) == 1) { 701 if (btrfs_header_nritems(mid) == 1) {
613 /* 702 /*
614 * we're not allowed to leave a node with one item in the 703 * we're not allowed to leave a node with one item in the
615 * tree during a delete. A deletion from lower in the tree 704 * tree during a delete. A deletion from lower in the tree
@@ -619,21 +708,20 @@ static int balance_level(struct btrfs_trans_handle *trans, struct btrfs_root
619 * otherwise we would have pulled some pointers from the 708 * otherwise we would have pulled some pointers from the
620 * right 709 * right
621 */ 710 */
622 BUG_ON(!left_buf); 711 BUG_ON(!left);
623 wret = balance_node_right(trans, root, mid_buf, left_buf); 712 wret = balance_node_right(trans, root, mid, left);
624 if (wret < 0) { 713 if (wret < 0) {
625 ret = wret; 714 ret = wret;
626 goto enospc; 715 goto enospc;
627 } 716 }
628 BUG_ON(wret == 1); 717 BUG_ON(wret == 1);
629 } 718 }
630 if (btrfs_header_nritems(&mid->header) == 0) { 719 if (btrfs_header_nritems(mid) == 0) {
631 /* we've managed to empty the middle node, drop it */ 720 /* we've managed to empty the middle node, drop it */
632 u64 blocknr = bh_blocknr(mid_buf); 721 u64 blocknr = extent_buffer_blocknr(mid);
633 clean_tree_block(trans, root, mid_buf); 722 clean_tree_block(trans, root, mid);
634 wait_on_buffer(mid_buf); 723 wait_on_tree_block_writeback(root, mid);
635 btrfs_block_release(root, mid_buf); 724 free_extent_buffer(mid);
636 mid_buf = NULL;
637 mid = NULL; 725 mid = NULL;
638 wret = del_ptr(trans, root, path, level + 1, pslot); 726 wret = del_ptr(trans, root, path, level + 1, pslot);
639 if (wret) 727 if (wret)
@@ -643,37 +731,36 @@ static int balance_level(struct btrfs_trans_handle *trans, struct btrfs_root
643 ret = wret; 731 ret = wret;
644 } else { 732 } else {
645 /* update the parent key to reflect our changes */ 733 /* update the parent key to reflect our changes */
646 btrfs_memcpy(root, parent, 734 struct btrfs_disk_key mid_key;
647 &parent->ptrs[pslot].key, &mid->ptrs[0].key, 735 btrfs_node_key(mid, &mid_key, 0);
648 sizeof(struct btrfs_disk_key)); 736 btrfs_set_node_key(parent, &mid_key, pslot);
649 btrfs_mark_buffer_dirty(parent_buf); 737 btrfs_mark_buffer_dirty(parent);
650 } 738 }
651 739
652 /* update the path */ 740 /* update the path */
653 if (left_buf) { 741 if (left) {
654 if (btrfs_header_nritems(&left->header) > orig_slot) { 742 if (btrfs_header_nritems(left) > orig_slot) {
655 get_bh(left_buf); 743 extent_buffer_get(left);
656 path->nodes[level] = left_buf; 744 path->nodes[level] = left;
657 path->slots[level + 1] -= 1; 745 path->slots[level + 1] -= 1;
658 path->slots[level] = orig_slot; 746 path->slots[level] = orig_slot;
659 if (mid_buf) 747 if (mid)
660 btrfs_block_release(root, mid_buf); 748 free_extent_buffer(mid);
661 } else { 749 } else {
662 orig_slot -= btrfs_header_nritems(&left->header); 750 orig_slot -= btrfs_header_nritems(left);
663 path->slots[level] = orig_slot; 751 path->slots[level] = orig_slot;
664 } 752 }
665 } 753 }
666 /* double check we haven't messed things up */ 754 /* double check we haven't messed things up */
667 check_block(root, path, level); 755 check_block(root, path, level);
668 if (orig_ptr != 756 if (orig_ptr !=
669 btrfs_node_blockptr(btrfs_buffer_node(path->nodes[level]), 757 btrfs_node_blockptr(path->nodes[level], path->slots[level]))
670 path->slots[level]))
671 BUG(); 758 BUG();
672enospc: 759enospc:
673 if (right_buf) 760 if (right)
674 btrfs_block_release(root, right_buf); 761 free_extent_buffer(right);
675 if (left_buf) 762 if (left)
676 btrfs_block_release(root, left_buf); 763 free_extent_buffer(left);
677 return ret; 764 return ret;
678} 765}
679 766
@@ -682,14 +769,10 @@ static int push_nodes_for_insert(struct btrfs_trans_handle *trans,
682 struct btrfs_root *root, 769 struct btrfs_root *root,
683 struct btrfs_path *path, int level) 770 struct btrfs_path *path, int level)
684{ 771{
685 struct buffer_head *right_buf; 772 struct extent_buffer *right = NULL;
686 struct buffer_head *mid_buf; 773 struct extent_buffer *mid;
687 struct buffer_head *left_buf; 774 struct extent_buffer *left = NULL;
688 struct buffer_head *parent_buf = NULL; 775 struct extent_buffer *parent = NULL;
689 struct btrfs_node *right = NULL;
690 struct btrfs_node *mid;
691 struct btrfs_node *left = NULL;
692 struct btrfs_node *parent = NULL;
693 int ret = 0; 776 int ret = 0;
694 int wret; 777 int wret;
695 int pslot; 778 int pslot;
@@ -699,107 +782,101 @@ static int push_nodes_for_insert(struct btrfs_trans_handle *trans,
699 if (level == 0) 782 if (level == 0)
700 return 1; 783 return 1;
701 784
702 mid_buf = path->nodes[level]; 785 mid = path->nodes[level];
703 mid = btrfs_buffer_node(mid_buf);
704 orig_ptr = btrfs_node_blockptr(mid, orig_slot); 786 orig_ptr = btrfs_node_blockptr(mid, orig_slot);
705 787
706 if (level < BTRFS_MAX_LEVEL - 1) 788 if (level < BTRFS_MAX_LEVEL - 1)
707 parent_buf = path->nodes[level + 1]; 789 parent = path->nodes[level + 1];
708 pslot = path->slots[level + 1]; 790 pslot = path->slots[level + 1];
709 791
710 if (!parent_buf) 792 if (!parent)
711 return 1; 793 return 1;
712 parent = btrfs_buffer_node(parent_buf);
713 794
714 left_buf = read_node_slot(root, parent_buf, pslot - 1); 795 left = read_node_slot(root, parent, pslot - 1);
715 796
716 /* first, try to make some room in the middle buffer */ 797 /* first, try to make some room in the middle buffer */
717 if (left_buf) { 798 if (left) {
718 u32 left_nr; 799 u32 left_nr;
719 left = btrfs_buffer_node(left_buf); 800 left_nr = btrfs_header_nritems(left);
720 left_nr = btrfs_header_nritems(&left->header);
721 if (left_nr >= BTRFS_NODEPTRS_PER_BLOCK(root) - 1) { 801 if (left_nr >= BTRFS_NODEPTRS_PER_BLOCK(root) - 1) {
722 wret = 1; 802 wret = 1;
723 } else { 803 } else {
724 ret = btrfs_cow_block(trans, root, left_buf, parent_buf, 804 ret = btrfs_cow_block(trans, root, left, parent,
725 pslot - 1, &left_buf); 805 pslot - 1, &left);
726 if (ret) 806 if (ret)
727 wret = 1; 807 wret = 1;
728 else { 808 else {
729 left = btrfs_buffer_node(left_buf);
730 wret = push_node_left(trans, root, 809 wret = push_node_left(trans, root,
731 left_buf, mid_buf); 810 left, mid);
732 } 811 }
733 } 812 }
734 if (wret < 0) 813 if (wret < 0)
735 ret = wret; 814 ret = wret;
736 if (wret == 0) { 815 if (wret == 0) {
816 struct btrfs_disk_key disk_key;
737 orig_slot += left_nr; 817 orig_slot += left_nr;
738 btrfs_memcpy(root, parent, 818 btrfs_node_key(mid, &disk_key, 0);
739 &parent->ptrs[pslot].key, 819 btrfs_set_node_key(parent, &disk_key, pslot);
740 &mid->ptrs[0].key, 820 btrfs_mark_buffer_dirty(parent);
741 sizeof(struct btrfs_disk_key)); 821 if (btrfs_header_nritems(left) > orig_slot) {
742 btrfs_mark_buffer_dirty(parent_buf); 822 path->nodes[level] = left;
743 if (btrfs_header_nritems(&left->header) > orig_slot) {
744 path->nodes[level] = left_buf;
745 path->slots[level + 1] -= 1; 823 path->slots[level + 1] -= 1;
746 path->slots[level] = orig_slot; 824 path->slots[level] = orig_slot;
747 btrfs_block_release(root, mid_buf); 825 free_extent_buffer(mid);
748 } else { 826 } else {
749 orig_slot -= 827 orig_slot -=
750 btrfs_header_nritems(&left->header); 828 btrfs_header_nritems(left);
751 path->slots[level] = orig_slot; 829 path->slots[level] = orig_slot;
752 btrfs_block_release(root, left_buf); 830 free_extent_buffer(left);
753 } 831 }
754 check_node(root, path, level); 832 check_node(root, path, level);
755 return 0; 833 return 0;
756 } 834 }
757 btrfs_block_release(root, left_buf); 835 free_extent_buffer(left);
758 } 836 }
759 right_buf = read_node_slot(root, parent_buf, pslot + 1); 837 right= read_node_slot(root, parent, pslot + 1);
760 838
761 /* 839 /*
762 * then try to empty the right most buffer into the middle 840 * then try to empty the right most buffer into the middle
763 */ 841 */
764 if (right_buf) { 842 if (right) {
765 u32 right_nr; 843 u32 right_nr;
766 right = btrfs_buffer_node(right_buf); 844 right_nr = btrfs_header_nritems(right);
767 right_nr = btrfs_header_nritems(&right->header);
768 if (right_nr >= BTRFS_NODEPTRS_PER_BLOCK(root) - 1) { 845 if (right_nr >= BTRFS_NODEPTRS_PER_BLOCK(root) - 1) {
769 wret = 1; 846 wret = 1;
770 } else { 847 } else {
771 ret = btrfs_cow_block(trans, root, right_buf, 848 ret = btrfs_cow_block(trans, root, right,
772 parent_buf, pslot + 1, 849 parent, pslot + 1,
773 &right_buf); 850 &right);
774 if (ret) 851 if (ret)
775 wret = 1; 852 wret = 1;
776 else { 853 else {
777 right = btrfs_buffer_node(right_buf);
778 wret = balance_node_right(trans, root, 854 wret = balance_node_right(trans, root,
779 right_buf, mid_buf); 855 right, mid);
780 } 856 }
781 } 857 }
782 if (wret < 0) 858 if (wret < 0)
783 ret = wret; 859 ret = wret;
784 if (wret == 0) { 860 if (wret == 0) {
785 btrfs_memcpy(root, parent, 861 struct btrfs_disk_key disk_key;
786 &parent->ptrs[pslot + 1].key, 862
787 &right->ptrs[0].key, 863 btrfs_node_key(right, &disk_key, 0);
788 sizeof(struct btrfs_disk_key)); 864 btrfs_set_node_key(parent, &disk_key, pslot + 1);
789 btrfs_mark_buffer_dirty(parent_buf); 865 btrfs_mark_buffer_dirty(parent);
790 if (btrfs_header_nritems(&mid->header) <= orig_slot) { 866
791 path->nodes[level] = right_buf; 867 if (btrfs_header_nritems(mid) <= orig_slot) {
868 path->nodes[level] = right;
792 path->slots[level + 1] += 1; 869 path->slots[level + 1] += 1;
793 path->slots[level] = orig_slot - 870 path->slots[level] = orig_slot -
794 btrfs_header_nritems(&mid->header); 871 btrfs_header_nritems(mid);
795 btrfs_block_release(root, mid_buf); 872 free_extent_buffer(mid);
796 } else { 873 } else {
797 btrfs_block_release(root, right_buf); 874 free_extent_buffer(right);
798 } 875 }
799 check_node(root, path, level); 876 check_node(root, path, level);
800 return 0; 877 return 0;
801 } 878 }
802 btrfs_block_release(root, right_buf); 879 free_extent_buffer(right);
803 } 880 }
804 check_node(root, path, level); 881 check_node(root, path, level);
805 return 1; 882 return 1;
@@ -811,10 +888,9 @@ static int push_nodes_for_insert(struct btrfs_trans_handle *trans,
811static void reada_for_search(struct btrfs_root *root, struct btrfs_path *path, 888static void reada_for_search(struct btrfs_root *root, struct btrfs_path *path,
812 int level, int slot) 889 int level, int slot)
813{ 890{
814 struct btrfs_node *node; 891 struct extent_buffer *node;
815 int i; 892 int i;
816 u32 nritems; 893 u32 nritems;
817 u64 item_objectid;
818 u64 blocknr; 894 u64 blocknr;
819 u64 search; 895 u64 search;
820 u64 cluster_start; 896 u64 cluster_start;
@@ -823,7 +899,7 @@ static void reada_for_search(struct btrfs_root *root, struct btrfs_path *path,
823 int direction = path->reada; 899 int direction = path->reada;
824 struct radix_tree_root found; 900 struct radix_tree_root found;
825 unsigned long gang[8]; 901 unsigned long gang[8];
826 struct buffer_head *bh; 902 struct extent_buffer *eb;
827 903
828 if (level == 0) 904 if (level == 0)
829 return; 905 return;
@@ -831,18 +907,17 @@ static void reada_for_search(struct btrfs_root *root, struct btrfs_path *path,
831 if (!path->nodes[level]) 907 if (!path->nodes[level])
832 return; 908 return;
833 909
834 node = btrfs_buffer_node(path->nodes[level]); 910 node = path->nodes[level];
835 search = btrfs_node_blockptr(node, slot); 911 search = btrfs_node_blockptr(node, slot);
836 bh = btrfs_find_tree_block(root, search); 912 eb = btrfs_find_tree_block(root, search);
837 if (bh) { 913 if (eb) {
838 brelse(bh); 914 free_extent_buffer(eb);
839 return; 915 return;
840 } 916 }
841 917
842 init_bit_radix(&found); 918 init_bit_radix(&found);
843 nritems = btrfs_header_nritems(&node->header); 919 nritems = btrfs_header_nritems(node);
844 for (i = slot; i < nritems; i++) { 920 for (i = slot; i < nritems; i++) {
845 item_objectid = btrfs_disk_key_objectid(&node->ptrs[i].key);
846 blocknr = btrfs_node_blockptr(node, i); 921 blocknr = btrfs_node_blockptr(node, i);
847 set_radix_bit(&found, blocknr); 922 set_radix_bit(&found, blocknr);
848 } 923 }
@@ -886,8 +961,7 @@ int btrfs_search_slot(struct btrfs_trans_handle *trans, struct btrfs_root
886 *root, struct btrfs_key *key, struct btrfs_path *p, int 961 *root, struct btrfs_key *key, struct btrfs_path *p, int
887 ins_len, int cow) 962 ins_len, int cow)
888{ 963{
889 struct buffer_head *b; 964 struct extent_buffer *b;
890 struct btrfs_node *c;
891 u64 blocknr; 965 u64 blocknr;
892 int slot; 966 int slot;
893 int ret; 967 int ret;
@@ -901,10 +975,9 @@ int btrfs_search_slot(struct btrfs_trans_handle *trans, struct btrfs_root
901 WARN_ON(!mutex_is_locked(&root->fs_info->fs_mutex)); 975 WARN_ON(!mutex_is_locked(&root->fs_info->fs_mutex));
902again: 976again:
903 b = root->node; 977 b = root->node;
904 get_bh(b); 978 extent_buffer_get(b);
905 while (b) { 979 while (b) {
906 c = btrfs_buffer_node(b); 980 level = btrfs_header_level(b);
907 level = btrfs_header_level(&c->header);
908 if (cow) { 981 if (cow) {
909 int wret; 982 int wret;
910 wret = btrfs_cow_block(trans, root, b, 983 wret = btrfs_cow_block(trans, root, b,
@@ -912,32 +985,30 @@ again:
912 p->slots[level + 1], 985 p->slots[level + 1],
913 &b); 986 &b);
914 if (wret) { 987 if (wret) {
915 btrfs_block_release(root, b); 988 free_extent_buffer(b);
916 return wret; 989 return wret;
917 } 990 }
918 c = btrfs_buffer_node(b);
919 } 991 }
920 BUG_ON(!cow && ins_len); 992 BUG_ON(!cow && ins_len);
921 if (level != btrfs_header_level(&c->header)) 993 if (level != btrfs_header_level(b))
922 WARN_ON(1); 994 WARN_ON(1);
923 level = btrfs_header_level(&c->header); 995 level = btrfs_header_level(b);
924 p->nodes[level] = b; 996 p->nodes[level] = b;
925 ret = check_block(root, p, level); 997 ret = check_block(root, p, level);
926 if (ret) 998 if (ret)
927 return -1; 999 return -1;
928 ret = bin_search(c, key, &slot); 1000 ret = bin_search(b, key, level, &slot);
929 if (!btrfs_is_leaf(c)) { 1001 if (level != 0) {
930 if (ret && slot > 0) 1002 if (ret && slot > 0)
931 slot -= 1; 1003 slot -= 1;
932 p->slots[level] = slot; 1004 p->slots[level] = slot;
933 if (ins_len > 0 && btrfs_header_nritems(&c->header) >= 1005 if (ins_len > 0 && btrfs_header_nritems(b) >=
934 BTRFS_NODEPTRS_PER_BLOCK(root) - 1) { 1006 BTRFS_NODEPTRS_PER_BLOCK(root) - 1) {
935 int sret = split_node(trans, root, p, level); 1007 int sret = split_node(trans, root, p, level);
936 BUG_ON(sret > 0); 1008 BUG_ON(sret > 0);
937 if (sret) 1009 if (sret)
938 return sret; 1010 return sret;
939 b = p->nodes[level]; 1011 b = p->nodes[level];
940 c = btrfs_buffer_node(b);
941 slot = p->slots[level]; 1012 slot = p->slots[level];
942 } else if (ins_len < 0) { 1013 } else if (ins_len < 0) {
943 int sret = balance_level(trans, root, p, 1014 int sret = balance_level(trans, root, p,
@@ -947,22 +1018,19 @@ again:
947 b = p->nodes[level]; 1018 b = p->nodes[level];
948 if (!b) 1019 if (!b)
949 goto again; 1020 goto again;
950 c = btrfs_buffer_node(b);
951 slot = p->slots[level]; 1021 slot = p->slots[level];
952 BUG_ON(btrfs_header_nritems(&c->header) == 1); 1022 BUG_ON(btrfs_header_nritems(b) == 1);
953 } 1023 }
954 /* this is only true while dropping a snapshot */ 1024 /* this is only true while dropping a snapshot */
955 if (level == lowest_level) 1025 if (level == lowest_level)
956 break; 1026 break;
957 blocknr = btrfs_node_blockptr(c, slot); 1027 blocknr = btrfs_node_blockptr(b, slot);
958 if (should_reada) 1028 if (should_reada)
959 reada_for_search(root, p, level, slot); 1029 reada_for_search(root, p, level, slot);
960 b = read_tree_block(root, btrfs_node_blockptr(c, slot)); 1030 b = read_tree_block(root, btrfs_node_blockptr(b, slot));
961
962 } else { 1031 } else {
963 struct btrfs_leaf *l = (struct btrfs_leaf *)c;
964 p->slots[level] = slot; 1032 p->slots[level] = slot;
965 if (ins_len > 0 && btrfs_leaf_free_space(root, l) < 1033 if (ins_len > 0 && btrfs_leaf_free_space(root, b) <
966 sizeof(struct btrfs_item) + ins_len) { 1034 sizeof(struct btrfs_item) + ins_len) {
967 int sret = split_leaf(trans, root, key, 1035 int sret = split_leaf(trans, root, key,
968 p, ins_len); 1036 p, ins_len);
@@ -986,19 +1054,20 @@ again:
986 * If this fails to write a tree block, it returns -1, but continues 1054 * If this fails to write a tree block, it returns -1, but continues
987 * fixing up the blocks in ram so the tree is consistent. 1055 * fixing up the blocks in ram so the tree is consistent.
988 */ 1056 */
989static int fixup_low_keys(struct btrfs_trans_handle *trans, struct btrfs_root 1057static int fixup_low_keys(struct btrfs_trans_handle *trans,
990 *root, struct btrfs_path *path, struct btrfs_disk_key 1058 struct btrfs_root *root, struct btrfs_path *path,
991 *key, int level) 1059 struct btrfs_disk_key *key, int level)
992{ 1060{
993 int i; 1061 int i;
994 int ret = 0; 1062 int ret = 0;
1063 struct extent_buffer *t;
1064
995 for (i = level; i < BTRFS_MAX_LEVEL; i++) { 1065 for (i = level; i < BTRFS_MAX_LEVEL; i++) {
996 struct btrfs_node *t;
997 int tslot = path->slots[i]; 1066 int tslot = path->slots[i];
998 if (!path->nodes[i]) 1067 if (!path->nodes[i])
999 break; 1068 break;
1000 t = btrfs_buffer_node(path->nodes[i]); 1069 t = path->nodes[i];
1001 btrfs_memcpy(root, t, &t->ptrs[tslot].key, key, sizeof(*key)); 1070 btrfs_set_node_key(t, key, tslot);
1002 btrfs_mark_buffer_dirty(path->nodes[i]); 1071 btrfs_mark_buffer_dirty(path->nodes[i]);
1003 if (tslot != 0) 1072 if (tslot != 0)
1004 break; 1073 break;
@@ -1014,18 +1083,16 @@ static int fixup_low_keys(struct btrfs_trans_handle *trans, struct btrfs_root
1014 * error, and > 0 if there was no room in the left hand block. 1083 * error, and > 0 if there was no room in the left hand block.
1015 */ 1084 */
1016static int push_node_left(struct btrfs_trans_handle *trans, struct btrfs_root 1085static int push_node_left(struct btrfs_trans_handle *trans, struct btrfs_root
1017 *root, struct buffer_head *dst_buf, struct 1086 *root, struct extent_buffer *dst,
1018 buffer_head *src_buf) 1087 struct extent_buffer *src)
1019{ 1088{
1020 struct btrfs_node *src = btrfs_buffer_node(src_buf);
1021 struct btrfs_node *dst = btrfs_buffer_node(dst_buf);
1022 int push_items = 0; 1089 int push_items = 0;
1023 int src_nritems; 1090 int src_nritems;
1024 int dst_nritems; 1091 int dst_nritems;
1025 int ret = 0; 1092 int ret = 0;
1026 1093
1027 src_nritems = btrfs_header_nritems(&src->header); 1094 src_nritems = btrfs_header_nritems(src);
1028 dst_nritems = btrfs_header_nritems(&dst->header); 1095 dst_nritems = btrfs_header_nritems(dst);
1029 push_items = BTRFS_NODEPTRS_PER_BLOCK(root) - dst_nritems; 1096 push_items = BTRFS_NODEPTRS_PER_BLOCK(root) - dst_nritems;
1030 1097
1031 if (push_items <= 0) { 1098 if (push_items <= 0) {
@@ -1035,17 +1102,21 @@ static int push_node_left(struct btrfs_trans_handle *trans, struct btrfs_root
1035 if (src_nritems < push_items) 1102 if (src_nritems < push_items)
1036 push_items = src_nritems; 1103 push_items = src_nritems;
1037 1104
1038 btrfs_memcpy(root, dst, dst->ptrs + dst_nritems, src->ptrs, 1105 copy_extent_buffer(dst, src,
1039 push_items * sizeof(struct btrfs_key_ptr)); 1106 btrfs_node_key_ptr_offset(dst_nritems),
1107 btrfs_node_key_ptr_offset(0),
1108 push_items * sizeof(struct btrfs_key_ptr));
1109
1040 if (push_items < src_nritems) { 1110 if (push_items < src_nritems) {
1041 btrfs_memmove(root, src, src->ptrs, src->ptrs + push_items, 1111 memmove_extent_buffer(src, btrfs_node_key_ptr_offset(0),
1042 (src_nritems - push_items) * 1112 btrfs_node_key_ptr_offset(push_items),
1043 sizeof(struct btrfs_key_ptr)); 1113 (src_nritems - push_items) *
1044 } 1114 sizeof(struct btrfs_key_ptr));
1045 btrfs_set_header_nritems(&src->header, src_nritems - push_items); 1115 }
1046 btrfs_set_header_nritems(&dst->header, dst_nritems + push_items); 1116 btrfs_set_header_nritems(src, src_nritems - push_items);
1047 btrfs_mark_buffer_dirty(src_buf); 1117 btrfs_set_header_nritems(dst, dst_nritems + push_items);
1048 btrfs_mark_buffer_dirty(dst_buf); 1118 btrfs_mark_buffer_dirty(src);
1119 btrfs_mark_buffer_dirty(dst);
1049 return ret; 1120 return ret;
1050} 1121}
1051 1122
@@ -1058,24 +1129,22 @@ static int push_node_left(struct btrfs_trans_handle *trans, struct btrfs_root
1058 * 1129 *
1059 * this will only push up to 1/2 the contents of the left node over 1130 * this will only push up to 1/2 the contents of the left node over
1060 */ 1131 */
1061static int balance_node_right(struct btrfs_trans_handle *trans, struct 1132static int balance_node_right(struct btrfs_trans_handle *trans,
1062 btrfs_root *root, struct buffer_head *dst_buf, 1133 struct btrfs_root *root,
1063 struct buffer_head *src_buf) 1134 struct extent_buffer *dst,
1135 struct extent_buffer *src)
1064{ 1136{
1065 struct btrfs_node *src = btrfs_buffer_node(src_buf);
1066 struct btrfs_node *dst = btrfs_buffer_node(dst_buf);
1067 int push_items = 0; 1137 int push_items = 0;
1068 int max_push; 1138 int max_push;
1069 int src_nritems; 1139 int src_nritems;
1070 int dst_nritems; 1140 int dst_nritems;
1071 int ret = 0; 1141 int ret = 0;
1072 1142
1073 src_nritems = btrfs_header_nritems(&src->header); 1143 src_nritems = btrfs_header_nritems(src);
1074 dst_nritems = btrfs_header_nritems(&dst->header); 1144 dst_nritems = btrfs_header_nritems(dst);
1075 push_items = BTRFS_NODEPTRS_PER_BLOCK(root) - dst_nritems; 1145 push_items = BTRFS_NODEPTRS_PER_BLOCK(root) - dst_nritems;
1076 if (push_items <= 0) { 1146 if (push_items <= 0)
1077 return 1; 1147 return 1;
1078 }
1079 1148
1080 max_push = src_nritems / 2 + 1; 1149 max_push = src_nritems / 2 + 1;
1081 /* don't try to empty the node */ 1150 /* don't try to empty the node */
@@ -1085,18 +1154,21 @@ static int balance_node_right(struct btrfs_trans_handle *trans, struct
1085 if (max_push < push_items) 1154 if (max_push < push_items)
1086 push_items = max_push; 1155 push_items = max_push;
1087 1156
1088 btrfs_memmove(root, dst, dst->ptrs + push_items, dst->ptrs, 1157 memmove_extent_buffer(dst, btrfs_node_key_ptr_offset(push_items),
1089 dst_nritems * sizeof(struct btrfs_key_ptr)); 1158 btrfs_node_key_ptr_offset(0),
1159 (dst_nritems) *
1160 sizeof(struct btrfs_key_ptr));
1090 1161
1091 btrfs_memcpy(root, dst, dst->ptrs, 1162 copy_extent_buffer(dst, src,
1092 src->ptrs + src_nritems - push_items, 1163 btrfs_node_key_ptr_offset(0),
1093 push_items * sizeof(struct btrfs_key_ptr)); 1164 btrfs_node_key_ptr_offset(src_nritems - push_items),
1165 push_items * sizeof(struct btrfs_key_ptr));
1094 1166
1095 btrfs_set_header_nritems(&src->header, src_nritems - push_items); 1167 btrfs_set_header_nritems(src, src_nritems - push_items);
1096 btrfs_set_header_nritems(&dst->header, dst_nritems + push_items); 1168 btrfs_set_header_nritems(dst, dst_nritems + push_items);
1097 1169
1098 btrfs_mark_buffer_dirty(src_buf); 1170 btrfs_mark_buffer_dirty(src);
1099 btrfs_mark_buffer_dirty(dst_buf); 1171 btrfs_mark_buffer_dirty(dst);
1100 return ret; 1172 return ret;
1101} 1173}
1102 1174
@@ -1107,45 +1179,46 @@ static int balance_node_right(struct btrfs_trans_handle *trans, struct
1107 * 1179 *
1108 * returns zero on success or < 0 on failure. 1180 * returns zero on success or < 0 on failure.
1109 */ 1181 */
1110static int insert_new_root(struct btrfs_trans_handle *trans, struct btrfs_root 1182static int insert_new_root(struct btrfs_trans_handle *trans,
1111 *root, struct btrfs_path *path, int level) 1183 struct btrfs_root *root,
1184 struct btrfs_path *path, int level)
1112{ 1185{
1113 struct buffer_head *t; 1186 struct extent_buffer *lower;
1114 struct btrfs_node *lower; 1187 struct extent_buffer *c;
1115 struct btrfs_node *c; 1188 struct btrfs_disk_key lower_key;
1116 struct btrfs_disk_key *lower_key;
1117 1189
1118 BUG_ON(path->nodes[level]); 1190 BUG_ON(path->nodes[level]);
1119 BUG_ON(path->nodes[level-1] != root->node); 1191 BUG_ON(path->nodes[level-1] != root->node);
1120 1192
1121 t = btrfs_alloc_free_block(trans, root, root->node->b_blocknr, 0); 1193 c = btrfs_alloc_free_block(trans, root,
1122 if (IS_ERR(t)) 1194 extent_buffer_blocknr(root->node), 0);
1123 return PTR_ERR(t); 1195 if (IS_ERR(c))
1124 c = btrfs_buffer_node(t); 1196 return PTR_ERR(c);
1125 memset(c, 0, root->blocksize); 1197 memset_extent_buffer(c, 0, 0, root->nodesize);
1126 btrfs_set_header_nritems(&c->header, 1); 1198 btrfs_set_header_nritems(c, 1);
1127 btrfs_set_header_level(&c->header, level); 1199 btrfs_set_header_level(c, level);
1128 btrfs_set_header_blocknr(&c->header, bh_blocknr(t)); 1200 btrfs_set_header_blocknr(c, extent_buffer_blocknr(c));
1129 btrfs_set_header_generation(&c->header, trans->transid); 1201 btrfs_set_header_generation(c, trans->transid);
1130 btrfs_set_header_owner(&c->header, root->root_key.objectid); 1202 btrfs_set_header_owner(c, root->root_key.objectid);
1131 lower = btrfs_buffer_node(path->nodes[level-1]); 1203 lower = path->nodes[level-1];
1132 memcpy(c->header.fsid, root->fs_info->disk_super->fsid, 1204
1133 sizeof(c->header.fsid)); 1205 write_extent_buffer(c, root->fs_info->fsid,
1134 if (btrfs_is_leaf(lower)) 1206 (unsigned long)btrfs_header_fsid(c),
1135 lower_key = &((struct btrfs_leaf *)lower)->items[0].key; 1207 BTRFS_FSID_SIZE);
1208 if (level == 1)
1209 btrfs_item_key(lower, &lower_key, 0);
1136 else 1210 else
1137 lower_key = &lower->ptrs[0].key; 1211 btrfs_node_key(lower, &lower_key, 0);
1138 btrfs_memcpy(root, c, &c->ptrs[0].key, lower_key, 1212 btrfs_set_node_key(c, &lower_key, 0);
1139 sizeof(struct btrfs_disk_key)); 1213 btrfs_set_node_blockptr(c, 0, extent_buffer_blocknr(lower));
1140 btrfs_set_node_blockptr(c, 0, bh_blocknr(path->nodes[level - 1]));
1141 1214
1142 btrfs_mark_buffer_dirty(t); 1215 btrfs_mark_buffer_dirty(c);
1143 1216
1144 /* the super has an extra ref to root->node */ 1217 /* the super has an extra ref to root->node */
1145 btrfs_block_release(root, root->node); 1218 free_extent_buffer(root->node);
1146 root->node = t; 1219 root->node = c;
1147 get_bh(t); 1220 extent_buffer_get(c);
1148 path->nodes[level] = t; 1221 path->nodes[level] = c;
1149 path->slots[level] = 0; 1222 path->slots[level] = 0;
1150 return 0; 1223 return 0;
1151} 1224}
@@ -1163,26 +1236,26 @@ static int insert_ptr(struct btrfs_trans_handle *trans, struct btrfs_root
1163 *root, struct btrfs_path *path, struct btrfs_disk_key 1236 *root, struct btrfs_path *path, struct btrfs_disk_key
1164 *key, u64 blocknr, int slot, int level) 1237 *key, u64 blocknr, int slot, int level)
1165{ 1238{
1166 struct btrfs_node *lower; 1239 struct extent_buffer *lower;
1167 int nritems; 1240 int nritems;
1168 1241
1169 BUG_ON(!path->nodes[level]); 1242 BUG_ON(!path->nodes[level]);
1170 lower = btrfs_buffer_node(path->nodes[level]); 1243 lower = path->nodes[level];
1171 nritems = btrfs_header_nritems(&lower->header); 1244 nritems = btrfs_header_nritems(lower);
1172 if (slot > nritems) 1245 if (slot > nritems)
1173 BUG(); 1246 BUG();
1174 if (nritems == BTRFS_NODEPTRS_PER_BLOCK(root)) 1247 if (nritems == BTRFS_NODEPTRS_PER_BLOCK(root))
1175 BUG(); 1248 BUG();
1176 if (slot != nritems) { 1249 if (slot != nritems) {
1177 btrfs_memmove(root, lower, lower->ptrs + slot + 1, 1250 memmove_extent_buffer(lower,
1178 lower->ptrs + slot, 1251 btrfs_node_key_ptr_offset(slot + 1),
1252 btrfs_node_key_ptr_offset(slot),
1179 (nritems - slot) * sizeof(struct btrfs_key_ptr)); 1253 (nritems - slot) * sizeof(struct btrfs_key_ptr));
1180 } 1254 }
1181 btrfs_memcpy(root, lower, &lower->ptrs[slot].key, 1255 btrfs_set_node_key(lower, key, slot);
1182 key, sizeof(struct btrfs_disk_key));
1183 btrfs_set_node_blockptr(lower, slot, blocknr); 1256 btrfs_set_node_blockptr(lower, slot, blocknr);
1184 btrfs_set_header_nritems(&lower->header, nritems + 1); 1257 btrfs_set_header_nritems(lower, nritems + 1);
1185 btrfs_mark_buffer_dirty(path->nodes[level]); 1258 btrfs_mark_buffer_dirty(lower);
1186 check_node(root, path, level); 1259 check_node(root, path, level);
1187 return 0; 1260 return 0;
1188} 1261}
@@ -1199,69 +1272,73 @@ static int insert_ptr(struct btrfs_trans_handle *trans, struct btrfs_root
1199static int split_node(struct btrfs_trans_handle *trans, struct btrfs_root 1272static int split_node(struct btrfs_trans_handle *trans, struct btrfs_root
1200 *root, struct btrfs_path *path, int level) 1273 *root, struct btrfs_path *path, int level)
1201{ 1274{
1202 struct buffer_head *t; 1275 struct extent_buffer *c;
1203 struct btrfs_node *c; 1276 struct extent_buffer *split;
1204 struct buffer_head *split_buffer; 1277 struct btrfs_disk_key disk_key;
1205 struct btrfs_node *split;
1206 int mid; 1278 int mid;
1207 int ret; 1279 int ret;
1208 int wret; 1280 int wret;
1209 u32 c_nritems; 1281 u32 c_nritems;
1210 1282
1211 t = path->nodes[level]; 1283 c = path->nodes[level];
1212 c = btrfs_buffer_node(t); 1284 if (c == root->node) {
1213 if (t == root->node) {
1214 /* trying to split the root, lets make a new one */ 1285 /* trying to split the root, lets make a new one */
1215 ret = insert_new_root(trans, root, path, level + 1); 1286 ret = insert_new_root(trans, root, path, level + 1);
1216 if (ret) 1287 if (ret)
1217 return ret; 1288 return ret;
1218 } else { 1289 } else {
1219 ret = push_nodes_for_insert(trans, root, path, level); 1290 ret = push_nodes_for_insert(trans, root, path, level);
1220 t = path->nodes[level]; 1291 c = path->nodes[level];
1221 c = btrfs_buffer_node(t); 1292 if (!ret && btrfs_header_nritems(c) <
1222 if (!ret &&
1223 btrfs_header_nritems(&c->header) <
1224 BTRFS_NODEPTRS_PER_BLOCK(root) - 1) 1293 BTRFS_NODEPTRS_PER_BLOCK(root) - 1)
1225 return 0; 1294 return 0;
1226 if (ret < 0) 1295 if (ret < 0)
1227 return ret; 1296 return ret;
1228 } 1297 }
1229 1298
1230 c_nritems = btrfs_header_nritems(&c->header); 1299 c_nritems = btrfs_header_nritems(c);
1231 split_buffer = btrfs_alloc_free_block(trans, root, t->b_blocknr, 0); 1300 split = btrfs_alloc_free_block(trans, root,
1232 if (IS_ERR(split_buffer)) 1301 extent_buffer_blocknr(c), 0);
1233 return PTR_ERR(split_buffer); 1302 if (IS_ERR(split))
1303 return PTR_ERR(split);
1304
1305 btrfs_set_header_flags(split, btrfs_header_flags(c));
1306 btrfs_set_header_level(split, btrfs_header_level(c));
1307 btrfs_set_header_blocknr(split, extent_buffer_blocknr(split));
1308 btrfs_set_header_generation(split, trans->transid);
1309 btrfs_set_header_owner(split, root->root_key.objectid);
1310 write_extent_buffer(split, root->fs_info->fsid,
1311 (unsigned long)btrfs_header_fsid(split),
1312 BTRFS_FSID_SIZE);
1234 1313
1235 split = btrfs_buffer_node(split_buffer);
1236 btrfs_set_header_flags(&split->header, btrfs_header_flags(&c->header));
1237 btrfs_set_header_level(&split->header, btrfs_header_level(&c->header));
1238 btrfs_set_header_blocknr(&split->header, bh_blocknr(split_buffer));
1239 btrfs_set_header_generation(&split->header, trans->transid);
1240 btrfs_set_header_owner(&split->header, root->root_key.objectid);
1241 memcpy(split->header.fsid, root->fs_info->disk_super->fsid,
1242 sizeof(split->header.fsid));
1243 mid = (c_nritems + 1) / 2; 1314 mid = (c_nritems + 1) / 2;
1244 btrfs_memcpy(root, split, split->ptrs, c->ptrs + mid, 1315
1245 (c_nritems - mid) * sizeof(struct btrfs_key_ptr)); 1316 copy_extent_buffer(split, c,
1246 btrfs_set_header_nritems(&split->header, c_nritems - mid); 1317 btrfs_node_key_ptr_offset(0),
1247 btrfs_set_header_nritems(&c->header, mid); 1318 btrfs_node_key_ptr_offset(mid),
1319 (c_nritems - mid) * sizeof(struct btrfs_key_ptr));
1320 btrfs_set_header_nritems(split, c_nritems - mid);
1321 btrfs_set_header_nritems(c, mid);
1248 ret = 0; 1322 ret = 0;
1249 1323
1250 btrfs_mark_buffer_dirty(t); 1324 btrfs_mark_buffer_dirty(c);
1251 btrfs_mark_buffer_dirty(split_buffer); 1325 btrfs_mark_buffer_dirty(split);
1252 wret = insert_ptr(trans, root, path, &split->ptrs[0].key, 1326
1253 bh_blocknr(split_buffer), path->slots[level + 1] + 1, 1327 btrfs_node_key(split, &disk_key, 0);
1328 wret = insert_ptr(trans, root, path, &disk_key,
1329 extent_buffer_blocknr(split),
1330 path->slots[level + 1] + 1,
1254 level + 1); 1331 level + 1);
1255 if (wret) 1332 if (wret)
1256 ret = wret; 1333 ret = wret;
1257 1334
1258 if (path->slots[level] >= mid) { 1335 if (path->slots[level] >= mid) {
1259 path->slots[level] -= mid; 1336 path->slots[level] -= mid;
1260 btrfs_block_release(root, t); 1337 free_extent_buffer(c);
1261 path->nodes[level] = split_buffer; 1338 path->nodes[level] = split;
1262 path->slots[level + 1] += 1; 1339 path->slots[level + 1] += 1;
1263 } else { 1340 } else {
1264 btrfs_block_release(root, split_buffer); 1341 free_extent_buffer(split);
1265 } 1342 }
1266 return ret; 1343 return ret;
1267} 1344}
@@ -1271,16 +1348,16 @@ static int split_node(struct btrfs_trans_handle *trans, struct btrfs_root
1271 * and nr indicate which items in the leaf to check. This totals up the 1348 * and nr indicate which items in the leaf to check. This totals up the
1272 * space used both by the item structs and the item data 1349 * space used both by the item structs and the item data
1273 */ 1350 */
1274static int leaf_space_used(struct btrfs_leaf *l, int start, int nr) 1351static int leaf_space_used(struct extent_buffer *l, int start, int nr)
1275{ 1352{
1276 int data_len; 1353 int data_len;
1277 int nritems = btrfs_header_nritems(&l->header); 1354 int nritems = btrfs_header_nritems(l);
1278 int end = min(nritems, start + nr) - 1; 1355 int end = min(nritems, start + nr) - 1;
1279 1356
1280 if (!nr) 1357 if (!nr)
1281 return 0; 1358 return 0;
1282 data_len = btrfs_item_end(l->items + start); 1359 data_len = btrfs_item_end_nr(l, start);
1283 data_len = data_len - btrfs_item_offset(l->items + end); 1360 data_len = data_len - btrfs_item_offset_nr(l, end);
1284 data_len += sizeof(struct btrfs_item) * nr; 1361 data_len += sizeof(struct btrfs_item) * nr;
1285 WARN_ON(data_len < 0); 1362 WARN_ON(data_len < 0);
1286 return data_len; 1363 return data_len;
@@ -1291,10 +1368,17 @@ static int leaf_space_used(struct btrfs_leaf *l, int start, int nr)
1291 * the start of the leaf data. IOW, how much room 1368 * the start of the leaf data. IOW, how much room
1292 * the leaf has left for both items and data 1369 * the leaf has left for both items and data
1293 */ 1370 */
1294int btrfs_leaf_free_space(struct btrfs_root *root, struct btrfs_leaf *leaf) 1371int btrfs_leaf_free_space(struct btrfs_root *root, struct extent_buffer *leaf)
1295{ 1372{
1296 int nritems = btrfs_header_nritems(&leaf->header); 1373 int nritems = btrfs_header_nritems(leaf);
1297 return BTRFS_LEAF_DATA_SIZE(root) - leaf_space_used(leaf, 0, nritems); 1374 int ret;
1375 ret = BTRFS_LEAF_DATA_SIZE(root) - leaf_space_used(leaf, 0, nritems);
1376 if (ret < 0) {
1377 printk("leaf free space ret %d, leaf data size %lu, used %d nritems %d\n",
1378 ret, BTRFS_LEAF_DATA_SIZE(root),
1379 leaf_space_used(leaf, 0, nritems), nritems);
1380 }
1381 return ret;
1298} 1382}
1299 1383
1300/* 1384/*
@@ -1307,12 +1391,10 @@ int btrfs_leaf_free_space(struct btrfs_root *root, struct btrfs_leaf *leaf)
1307static int push_leaf_right(struct btrfs_trans_handle *trans, struct btrfs_root 1391static int push_leaf_right(struct btrfs_trans_handle *trans, struct btrfs_root
1308 *root, struct btrfs_path *path, int data_size) 1392 *root, struct btrfs_path *path, int data_size)
1309{ 1393{
1310 struct buffer_head *left_buf = path->nodes[0]; 1394 struct extent_buffer *left = path->nodes[0];
1311 struct btrfs_leaf *left = btrfs_buffer_leaf(left_buf); 1395 struct extent_buffer *right;
1312 struct btrfs_leaf *right; 1396 struct extent_buffer *upper;
1313 struct buffer_head *right_buf; 1397 struct btrfs_disk_key disk_key;
1314 struct buffer_head *upper;
1315 struct btrfs_node *upper_node;
1316 int slot; 1398 int slot;
1317 int i; 1399 int i;
1318 int free_space; 1400 int free_space;
@@ -1321,6 +1403,7 @@ static int push_leaf_right(struct btrfs_trans_handle *trans, struct btrfs_root
1321 struct btrfs_item *item; 1403 struct btrfs_item *item;
1322 u32 left_nritems; 1404 u32 left_nritems;
1323 u32 right_nritems; 1405 u32 right_nritems;
1406 u32 data_end;
1324 int ret; 1407 int ret;
1325 1408
1326 slot = path->slots[1]; 1409 slot = path->slots[1];
@@ -1328,102 +1411,109 @@ static int push_leaf_right(struct btrfs_trans_handle *trans, struct btrfs_root
1328 return 1; 1411 return 1;
1329 } 1412 }
1330 upper = path->nodes[1]; 1413 upper = path->nodes[1];
1331 upper_node = btrfs_buffer_node(upper); 1414 if (slot >= btrfs_header_nritems(upper) - 1)
1332 if (slot >= btrfs_header_nritems(&upper_node->header) - 1) {
1333 return 1; 1415 return 1;
1334 } 1416
1335 right_buf = read_tree_block(root, 1417 right = read_tree_block(root, btrfs_node_blockptr(upper, slot + 1));
1336 btrfs_node_blockptr(btrfs_buffer_node(upper), slot + 1));
1337 right = btrfs_buffer_leaf(right_buf);
1338 free_space = btrfs_leaf_free_space(root, right); 1418 free_space = btrfs_leaf_free_space(root, right);
1339 if (free_space < data_size + sizeof(struct btrfs_item)) { 1419 if (free_space < data_size + sizeof(struct btrfs_item)) {
1340 btrfs_block_release(root, right_buf); 1420 free_extent_buffer(right);
1341 return 1; 1421 return 1;
1342 } 1422 }
1423
1343 /* cow and double check */ 1424 /* cow and double check */
1344 ret = btrfs_cow_block(trans, root, right_buf, upper, 1425 ret = btrfs_cow_block(trans, root, right, upper,
1345 slot + 1, &right_buf); 1426 slot + 1, &right);
1346 if (ret) { 1427 if (ret) {
1347 btrfs_block_release(root, right_buf); 1428 free_extent_buffer(right);
1348 return 1; 1429 return 1;
1349 } 1430 }
1350 right = btrfs_buffer_leaf(right_buf);
1351 free_space = btrfs_leaf_free_space(root, right); 1431 free_space = btrfs_leaf_free_space(root, right);
1352 if (free_space < data_size + sizeof(struct btrfs_item)) { 1432 if (free_space < data_size + sizeof(struct btrfs_item)) {
1353 btrfs_block_release(root, right_buf); 1433 free_extent_buffer(right);
1354 return 1; 1434 return 1;
1355 } 1435 }
1356 1436
1357 left_nritems = btrfs_header_nritems(&left->header); 1437 left_nritems = btrfs_header_nritems(left);
1358 if (left_nritems == 0) { 1438 if (left_nritems == 0) {
1359 btrfs_block_release(root, right_buf); 1439 free_extent_buffer(right);
1360 return 1; 1440 return 1;
1361 } 1441 }
1442
1362 for (i = left_nritems - 1; i >= 1; i--) { 1443 for (i = left_nritems - 1; i >= 1; i--) {
1363 item = left->items + i; 1444 item = btrfs_item_nr(left, i);
1364 if (path->slots[0] == i) 1445 if (path->slots[0] == i)
1365 push_space += data_size + sizeof(*item); 1446 push_space += data_size + sizeof(*item);
1366 if (btrfs_item_size(item) + sizeof(*item) + push_space > 1447 if (btrfs_item_size(left, item) + sizeof(*item) + push_space >
1367 free_space) 1448 free_space)
1368 break; 1449 break;
1369 push_items++; 1450 push_items++;
1370 push_space += btrfs_item_size(item) + sizeof(*item); 1451 push_space += btrfs_item_size(left, item) + sizeof(*item);
1371 } 1452 }
1453
1372 if (push_items == 0) { 1454 if (push_items == 0) {
1373 btrfs_block_release(root, right_buf); 1455 free_extent_buffer(right);
1374 return 1; 1456 return 1;
1375 } 1457 }
1458
1376 if (push_items == left_nritems) 1459 if (push_items == left_nritems)
1377 WARN_ON(1); 1460 WARN_ON(1);
1378 right_nritems = btrfs_header_nritems(&right->header); 1461
1379 /* push left to right */ 1462 /* push left to right */
1380 push_space = btrfs_item_end(left->items + left_nritems - push_items); 1463 right_nritems = btrfs_header_nritems(right);
1464 push_space = btrfs_item_end_nr(left, left_nritems - push_items);
1381 push_space -= leaf_data_end(root, left); 1465 push_space -= leaf_data_end(root, left);
1466
1382 /* make room in the right data area */ 1467 /* make room in the right data area */
1383 btrfs_memmove(root, right, btrfs_leaf_data(right) + 1468 data_end = leaf_data_end(root, right);
1384 leaf_data_end(root, right) - push_space, 1469 memmove_extent_buffer(right,
1385 btrfs_leaf_data(right) + 1470 btrfs_leaf_data(right) + data_end - push_space,
1386 leaf_data_end(root, right), BTRFS_LEAF_DATA_SIZE(root) - 1471 btrfs_leaf_data(right) + data_end,
1387 leaf_data_end(root, right)); 1472 BTRFS_LEAF_DATA_SIZE(root) - data_end);
1473
1388 /* copy from the left data area */ 1474 /* copy from the left data area */
1389 btrfs_memcpy(root, right, btrfs_leaf_data(right) + 1475 copy_extent_buffer(right, left, btrfs_leaf_data(right) +
1390 BTRFS_LEAF_DATA_SIZE(root) - push_space, 1476 BTRFS_LEAF_DATA_SIZE(root) - push_space,
1391 btrfs_leaf_data(left) + leaf_data_end(root, left), 1477 btrfs_leaf_data(left) + leaf_data_end(root, left),
1392 push_space); 1478 push_space);
1393 btrfs_memmove(root, right, right->items + push_items, right->items, 1479
1394 right_nritems * sizeof(struct btrfs_item)); 1480 memmove_extent_buffer(right, btrfs_item_nr_offset(push_items),
1481 btrfs_item_nr_offset(0),
1482 right_nritems * sizeof(struct btrfs_item));
1483
1395 /* copy the items from left to right */ 1484 /* copy the items from left to right */
1396 btrfs_memcpy(root, right, right->items, left->items + 1485 copy_extent_buffer(right, left, btrfs_item_nr_offset(0),
1397 left_nritems - push_items, 1486 btrfs_item_nr_offset(left_nritems - push_items),
1398 push_items * sizeof(struct btrfs_item)); 1487 push_items * sizeof(struct btrfs_item));
1399 1488
1400 /* update the item pointers */ 1489 /* update the item pointers */
1401 right_nritems += push_items; 1490 right_nritems += push_items;
1402 btrfs_set_header_nritems(&right->header, right_nritems); 1491 btrfs_set_header_nritems(right, right_nritems);
1403 push_space = BTRFS_LEAF_DATA_SIZE(root); 1492 push_space = BTRFS_LEAF_DATA_SIZE(root);
1404 for (i = 0; i < right_nritems; i++) { 1493 for (i = 0; i < right_nritems; i++) {
1405 btrfs_set_item_offset(right->items + i, push_space - 1494 item = btrfs_item_nr(right, i);
1406 btrfs_item_size(right->items + i)); 1495 btrfs_set_item_offset(right, item, push_space -
1407 push_space = btrfs_item_offset(right->items + i); 1496 btrfs_item_size(right, item));
1497 push_space = btrfs_item_offset(right, item);
1408 } 1498 }
1409 left_nritems -= push_items; 1499 left_nritems -= push_items;
1410 btrfs_set_header_nritems(&left->header, left_nritems); 1500 btrfs_set_header_nritems(left, left_nritems);
1411 1501
1412 btrfs_mark_buffer_dirty(left_buf); 1502 btrfs_mark_buffer_dirty(left);
1413 btrfs_mark_buffer_dirty(right_buf); 1503 btrfs_mark_buffer_dirty(right);
1414 1504
1415 btrfs_memcpy(root, upper_node, &upper_node->ptrs[slot + 1].key, 1505 btrfs_item_key(right, &disk_key, 0);
1416 &right->items[0].key, sizeof(struct btrfs_disk_key)); 1506 btrfs_set_node_key(upper, &disk_key, slot + 1);
1417 btrfs_mark_buffer_dirty(upper); 1507 btrfs_mark_buffer_dirty(upper);
1418 1508
1419 /* then fixup the leaf pointer in the path */ 1509 /* then fixup the leaf pointer in the path */
1420 if (path->slots[0] >= left_nritems) { 1510 if (path->slots[0] >= left_nritems) {
1421 path->slots[0] -= left_nritems; 1511 path->slots[0] -= left_nritems;
1422 btrfs_block_release(root, path->nodes[0]); 1512 free_extent_buffer(path->nodes[0]);
1423 path->nodes[0] = right_buf; 1513 path->nodes[0] = right;
1424 path->slots[1] += 1; 1514 path->slots[1] += 1;
1425 } else { 1515 } else {
1426 btrfs_block_release(root, right_buf); 1516 free_extent_buffer(right);
1427 } 1517 }
1428 if (path->nodes[1]) 1518 if (path->nodes[1])
1429 check_node(root, path, 1); 1519 check_node(root, path, 1);
@@ -1436,10 +1526,9 @@ static int push_leaf_right(struct btrfs_trans_handle *trans, struct btrfs_root
1436static int push_leaf_left(struct btrfs_trans_handle *trans, struct btrfs_root 1526static int push_leaf_left(struct btrfs_trans_handle *trans, struct btrfs_root
1437 *root, struct btrfs_path *path, int data_size) 1527 *root, struct btrfs_path *path, int data_size)
1438{ 1528{
1439 struct buffer_head *right_buf = path->nodes[0]; 1529 struct btrfs_disk_key disk_key;
1440 struct btrfs_leaf *right = btrfs_buffer_leaf(right_buf); 1530 struct extent_buffer *right = path->nodes[0];
1441 struct buffer_head *t; 1531 struct extent_buffer *left;
1442 struct btrfs_leaf *left;
1443 int slot; 1532 int slot;
1444 int i; 1533 int i;
1445 int free_space; 1534 int free_space;
@@ -1447,119 +1536,128 @@ static int push_leaf_left(struct btrfs_trans_handle *trans, struct btrfs_root
1447 int push_items = 0; 1536 int push_items = 0;
1448 struct btrfs_item *item; 1537 struct btrfs_item *item;
1449 u32 old_left_nritems; 1538 u32 old_left_nritems;
1539 u32 right_nritems;
1450 int ret = 0; 1540 int ret = 0;
1451 int wret; 1541 int wret;
1452 1542
1453 slot = path->slots[1]; 1543 slot = path->slots[1];
1454 if (slot == 0) { 1544 if (slot == 0)
1455 return 1; 1545 return 1;
1456 } 1546 if (!path->nodes[1])
1457 if (!path->nodes[1]) {
1458 return 1; 1547 return 1;
1459 } 1548
1460 t = read_tree_block(root, 1549 left = read_tree_block(root, btrfs_node_blockptr(path->nodes[1],
1461 btrfs_node_blockptr(btrfs_buffer_node(path->nodes[1]), slot - 1)); 1550 slot - 1));
1462 left = btrfs_buffer_leaf(t);
1463 free_space = btrfs_leaf_free_space(root, left); 1551 free_space = btrfs_leaf_free_space(root, left);
1464 if (free_space < data_size + sizeof(struct btrfs_item)) { 1552 if (free_space < data_size + sizeof(struct btrfs_item)) {
1465 btrfs_block_release(root, t); 1553 free_extent_buffer(left);
1466 return 1; 1554 return 1;
1467 } 1555 }
1468 1556
1469 /* cow and double check */ 1557 /* cow and double check */
1470 ret = btrfs_cow_block(trans, root, t, path->nodes[1], slot - 1, &t); 1558 ret = btrfs_cow_block(trans, root, left,
1559 path->nodes[1], slot - 1, &left);
1471 if (ret) { 1560 if (ret) {
1472 /* we hit -ENOSPC, but it isn't fatal here */ 1561 /* we hit -ENOSPC, but it isn't fatal here */
1473 btrfs_block_release(root, t); 1562 free_extent_buffer(left);
1474 return 1; 1563 return 1;
1475 } 1564 }
1476 left = btrfs_buffer_leaf(t);
1477 free_space = btrfs_leaf_free_space(root, left); 1565 free_space = btrfs_leaf_free_space(root, left);
1478 if (free_space < data_size + sizeof(struct btrfs_item)) { 1566 if (free_space < data_size + sizeof(struct btrfs_item)) {
1479 btrfs_block_release(root, t); 1567 free_extent_buffer(left);
1480 return 1; 1568 return 1;
1481 } 1569 }
1482 1570
1483 if (btrfs_header_nritems(&right->header) == 0) { 1571 right_nritems = btrfs_header_nritems(right);
1484 btrfs_block_release(root, t); 1572 if (right_nritems == 0) {
1573 free_extent_buffer(left);
1485 return 1; 1574 return 1;
1486 } 1575 }
1487 1576
1488 for (i = 0; i < btrfs_header_nritems(&right->header) - 1; i++) { 1577 for (i = 0; i < right_nritems - 1; i++) {
1489 item = right->items + i; 1578 item = btrfs_item_nr(right, i);
1490 if (path->slots[0] == i) 1579 if (path->slots[0] == i)
1491 push_space += data_size + sizeof(*item); 1580 push_space += data_size + sizeof(*item);
1492 if (btrfs_item_size(item) + sizeof(*item) + push_space > 1581 if (btrfs_item_size(right, item) + sizeof(*item) + push_space >
1493 free_space) 1582 free_space)
1494 break; 1583 break;
1495 push_items++; 1584 push_items++;
1496 push_space += btrfs_item_size(item) + sizeof(*item); 1585 push_space += btrfs_item_size(right, item) + sizeof(*item);
1497 } 1586 }
1498 if (push_items == 0) { 1587 if (push_items == 0) {
1499 btrfs_block_release(root, t); 1588 free_extent_buffer(left);
1500 return 1; 1589 return 1;
1501 } 1590 }
1502 if (push_items == btrfs_header_nritems(&right->header)) 1591 if (push_items == btrfs_header_nritems(right))
1503 WARN_ON(1); 1592 WARN_ON(1);
1593
1504 /* push data from right to left */ 1594 /* push data from right to left */
1505 btrfs_memcpy(root, left, left->items + 1595 copy_extent_buffer(left, right,
1506 btrfs_header_nritems(&left->header), 1596 btrfs_item_nr_offset(btrfs_header_nritems(left)),
1507 right->items, push_items * sizeof(struct btrfs_item)); 1597 btrfs_item_nr_offset(0),
1598 push_items * sizeof(struct btrfs_item));
1599
1508 push_space = BTRFS_LEAF_DATA_SIZE(root) - 1600 push_space = BTRFS_LEAF_DATA_SIZE(root) -
1509 btrfs_item_offset(right->items + push_items -1); 1601 btrfs_item_offset_nr(right, push_items -1);
1510 btrfs_memcpy(root, left, btrfs_leaf_data(left) + 1602
1603 copy_extent_buffer(left, right, btrfs_leaf_data(left) +
1511 leaf_data_end(root, left) - push_space, 1604 leaf_data_end(root, left) - push_space,
1512 btrfs_leaf_data(right) + 1605 btrfs_leaf_data(right) +
1513 btrfs_item_offset(right->items + push_items - 1), 1606 btrfs_item_offset_nr(right, push_items - 1),
1514 push_space); 1607 push_space);
1515 old_left_nritems = btrfs_header_nritems(&left->header); 1608 old_left_nritems = btrfs_header_nritems(left);
1516 BUG_ON(old_left_nritems < 0); 1609 BUG_ON(old_left_nritems < 0);
1517 1610
1518 for (i = old_left_nritems; i < old_left_nritems + push_items; i++) { 1611 for (i = old_left_nritems; i < old_left_nritems + push_items; i++) {
1519 u32 ioff = btrfs_item_offset(left->items + i); 1612 u32 ioff;
1520 btrfs_set_item_offset(left->items + i, ioff - 1613 item = btrfs_item_nr(left, i);
1521 (BTRFS_LEAF_DATA_SIZE(root) - 1614 ioff = btrfs_item_offset(left, item);
1522 btrfs_item_offset(left->items + 1615 btrfs_set_item_offset(left, item,
1523 old_left_nritems - 1))); 1616 ioff - (BTRFS_LEAF_DATA_SIZE(root) -
1617 btrfs_item_offset_nr(left, old_left_nritems - 1)));
1524 } 1618 }
1525 btrfs_set_header_nritems(&left->header, old_left_nritems + push_items); 1619 btrfs_set_header_nritems(left, old_left_nritems + push_items);
1526 1620
1527 /* fixup right node */ 1621 /* fixup right node */
1528 push_space = btrfs_item_offset(right->items + push_items - 1) - 1622 push_space = btrfs_item_offset_nr(right, push_items - 1) -
1529 leaf_data_end(root, right); 1623 leaf_data_end(root, right);
1530 btrfs_memmove(root, right, btrfs_leaf_data(right) + 1624 memmove_extent_buffer(right, btrfs_leaf_data(right) +
1531 BTRFS_LEAF_DATA_SIZE(root) - push_space, 1625 BTRFS_LEAF_DATA_SIZE(root) - push_space,
1532 btrfs_leaf_data(right) + 1626 btrfs_leaf_data(right) +
1533 leaf_data_end(root, right), push_space); 1627 leaf_data_end(root, right), push_space);
1534 btrfs_memmove(root, right, right->items, right->items + push_items, 1628
1535 (btrfs_header_nritems(&right->header) - push_items) * 1629 memmove_extent_buffer(right, btrfs_item_nr_offset(0),
1536 sizeof(struct btrfs_item)); 1630 btrfs_item_nr_offset(push_items),
1537 btrfs_set_header_nritems(&right->header, 1631 (btrfs_header_nritems(right) - push_items) *
1538 btrfs_header_nritems(&right->header) - 1632 sizeof(struct btrfs_item));
1539 push_items); 1633
1634 right_nritems = btrfs_header_nritems(right) - push_items;
1635 btrfs_set_header_nritems(right, right_nritems);
1540 push_space = BTRFS_LEAF_DATA_SIZE(root); 1636 push_space = BTRFS_LEAF_DATA_SIZE(root);
1541 1637
1542 for (i = 0; i < btrfs_header_nritems(&right->header); i++) { 1638 for (i = 0; i < right_nritems; i++) {
1543 btrfs_set_item_offset(right->items + i, push_space - 1639 item = btrfs_item_nr(right, i);
1544 btrfs_item_size(right->items + i)); 1640 btrfs_set_item_offset(right, item, push_space -
1545 push_space = btrfs_item_offset(right->items + i); 1641 btrfs_item_size(right, item));
1642 push_space = btrfs_item_offset(right, item);
1546 } 1643 }
1547 1644
1548 btrfs_mark_buffer_dirty(t); 1645 btrfs_mark_buffer_dirty(left);
1549 btrfs_mark_buffer_dirty(right_buf); 1646 btrfs_mark_buffer_dirty(right);
1550 1647
1551 wret = fixup_low_keys(trans, root, path, &right->items[0].key, 1); 1648 btrfs_item_key(right, &disk_key, 0);
1649 wret = fixup_low_keys(trans, root, path, &disk_key, 1);
1552 if (wret) 1650 if (wret)
1553 ret = wret; 1651 ret = wret;
1554 1652
1555 /* then fixup the leaf pointer in the path */ 1653 /* then fixup the leaf pointer in the path */
1556 if (path->slots[0] < push_items) { 1654 if (path->slots[0] < push_items) {
1557 path->slots[0] += old_left_nritems; 1655 path->slots[0] += old_left_nritems;
1558 btrfs_block_release(root, path->nodes[0]); 1656 free_extent_buffer(path->nodes[0]);
1559 path->nodes[0] = t; 1657 path->nodes[0] = left;
1560 path->slots[1] -= 1; 1658 path->slots[1] -= 1;
1561 } else { 1659 } else {
1562 btrfs_block_release(root, t); 1660 free_extent_buffer(left);
1563 path->slots[0] -= push_items; 1661 path->slots[0] -= push_items;
1564 } 1662 }
1565 BUG_ON(path->slots[0] < 0); 1663 BUG_ON(path->slots[0] < 0);
@@ -1578,13 +1676,11 @@ static int split_leaf(struct btrfs_trans_handle *trans, struct btrfs_root
1578 *root, struct btrfs_key *ins_key, 1676 *root, struct btrfs_key *ins_key,
1579 struct btrfs_path *path, int data_size) 1677 struct btrfs_path *path, int data_size)
1580{ 1678{
1581 struct buffer_head *l_buf; 1679 struct extent_buffer *l;
1582 struct btrfs_leaf *l;
1583 u32 nritems; 1680 u32 nritems;
1584 int mid; 1681 int mid;
1585 int slot; 1682 int slot;
1586 struct btrfs_leaf *right; 1683 struct extent_buffer *right;
1587 struct buffer_head *right_buffer;
1588 int space_needed = data_size + sizeof(struct btrfs_item); 1684 int space_needed = data_size + sizeof(struct btrfs_item);
1589 int data_copy_size; 1685 int data_copy_size;
1590 int rt_data_off; 1686 int rt_data_off;
@@ -1603,8 +1699,7 @@ static int split_leaf(struct btrfs_trans_handle *trans, struct btrfs_root
1603 if (wret < 0) 1699 if (wret < 0)
1604 return wret; 1700 return wret;
1605 } 1701 }
1606 l_buf = path->nodes[0]; 1702 l = path->nodes[0];
1607 l = btrfs_buffer_leaf(l_buf);
1608 1703
1609 /* did the pushes work? */ 1704 /* did the pushes work? */
1610 if (btrfs_leaf_free_space(root, l) >= 1705 if (btrfs_leaf_free_space(root, l) >=
@@ -1617,36 +1712,38 @@ static int split_leaf(struct btrfs_trans_handle *trans, struct btrfs_root
1617 return ret; 1712 return ret;
1618 } 1713 }
1619 slot = path->slots[0]; 1714 slot = path->slots[0];
1620 nritems = btrfs_header_nritems(&l->header); 1715 nritems = btrfs_header_nritems(l);
1621 mid = (nritems + 1)/ 2; 1716 mid = (nritems + 1)/ 2;
1622 1717
1623 right_buffer = btrfs_alloc_free_block(trans, root, l_buf->b_blocknr, 0); 1718 right = btrfs_alloc_free_block(trans, root,
1624 if (IS_ERR(right_buffer)) 1719 extent_buffer_blocknr(l), 0);
1625 return PTR_ERR(right_buffer); 1720 if (IS_ERR(right))
1626 1721 return PTR_ERR(right);
1627 right = btrfs_buffer_leaf(right_buffer); 1722
1628 memset(&right->header, 0, sizeof(right->header)); 1723 memset_extent_buffer(right, 0, 0, sizeof(struct btrfs_header));
1629 btrfs_set_header_blocknr(&right->header, bh_blocknr(right_buffer)); 1724 btrfs_set_header_blocknr(right, extent_buffer_blocknr(right));
1630 btrfs_set_header_generation(&right->header, trans->transid); 1725 btrfs_set_header_generation(right, trans->transid);
1631 btrfs_set_header_owner(&right->header, root->root_key.objectid); 1726 btrfs_set_header_owner(right, root->root_key.objectid);
1632 btrfs_set_header_level(&right->header, 0); 1727 btrfs_set_header_level(right, 0);
1633 memcpy(right->header.fsid, root->fs_info->disk_super->fsid, 1728 write_extent_buffer(right, root->fs_info->fsid,
1634 sizeof(right->header.fsid)); 1729 (unsigned long)btrfs_header_fsid(right),
1730 BTRFS_FSID_SIZE);
1731
1635 if (mid <= slot) { 1732 if (mid <= slot) {
1636 if (nritems == 1 || 1733 if (nritems == 1 ||
1637 leaf_space_used(l, mid, nritems - mid) + space_needed > 1734 leaf_space_used(l, mid, nritems - mid) + space_needed >
1638 BTRFS_LEAF_DATA_SIZE(root)) { 1735 BTRFS_LEAF_DATA_SIZE(root)) {
1639 if (slot >= nritems) { 1736 if (slot >= nritems) {
1640 btrfs_cpu_key_to_disk(&disk_key, ins_key); 1737 btrfs_cpu_key_to_disk(&disk_key, ins_key);
1641 btrfs_set_header_nritems(&right->header, 0); 1738 btrfs_set_header_nritems(right, 0);
1642 wret = insert_ptr(trans, root, path, 1739 wret = insert_ptr(trans, root, path,
1643 &disk_key, 1740 &disk_key,
1644 bh_blocknr(right_buffer), 1741 extent_buffer_blocknr(right),
1645 path->slots[1] + 1, 1); 1742 path->slots[1] + 1, 1);
1646 if (wret) 1743 if (wret)
1647 ret = wret; 1744 ret = wret;
1648 btrfs_block_release(root, path->nodes[0]); 1745 free_extent_buffer(path->nodes[0]);
1649 path->nodes[0] = right_buffer; 1746 path->nodes[0] = right;
1650 path->slots[0] = 0; 1747 path->slots[0] = 0;
1651 path->slots[1] += 1; 1748 path->slots[1] += 1;
1652 return ret; 1749 return ret;
@@ -1659,15 +1756,15 @@ static int split_leaf(struct btrfs_trans_handle *trans, struct btrfs_root
1659 BTRFS_LEAF_DATA_SIZE(root)) { 1756 BTRFS_LEAF_DATA_SIZE(root)) {
1660 if (slot == 0) { 1757 if (slot == 0) {
1661 btrfs_cpu_key_to_disk(&disk_key, ins_key); 1758 btrfs_cpu_key_to_disk(&disk_key, ins_key);
1662 btrfs_set_header_nritems(&right->header, 0); 1759 btrfs_set_header_nritems(right, 0);
1663 wret = insert_ptr(trans, root, path, 1760 wret = insert_ptr(trans, root, path,
1664 &disk_key, 1761 &disk_key,
1665 bh_blocknr(right_buffer), 1762 extent_buffer_blocknr(right),
1666 path->slots[1], 1); 1763 path->slots[1], 1);
1667 if (wret) 1764 if (wret)
1668 ret = wret; 1765 ret = wret;
1669 btrfs_block_release(root, path->nodes[0]); 1766 free_extent_buffer(path->nodes[0]);
1670 path->nodes[0] = right_buffer; 1767 path->nodes[0] = right;
1671 path->slots[0] = 0; 1768 path->slots[0] = 0;
1672 if (path->slots[1] == 0) { 1769 if (path->slots[1] == 0) {
1673 wret = fixup_low_keys(trans, root, 1770 wret = fixup_low_keys(trans, root,
@@ -1681,61 +1778,74 @@ static int split_leaf(struct btrfs_trans_handle *trans, struct btrfs_root
1681 double_split = 1; 1778 double_split = 1;
1682 } 1779 }
1683 } 1780 }
1684 btrfs_set_header_nritems(&right->header, nritems - mid); 1781 nritems = nritems - mid;
1685 data_copy_size = btrfs_item_end(l->items + mid) - 1782 btrfs_set_header_nritems(right, nritems);
1686 leaf_data_end(root, l); 1783 data_copy_size = btrfs_item_end_nr(l, mid) - leaf_data_end(root, l);
1687 btrfs_memcpy(root, right, right->items, l->items + mid, 1784
1688 (nritems - mid) * sizeof(struct btrfs_item)); 1785 copy_extent_buffer(right, l, btrfs_item_nr_offset(0),
1689 btrfs_memcpy(root, right, 1786 btrfs_item_nr_offset(mid),
1787 nritems * sizeof(struct btrfs_item));
1788
1789 copy_extent_buffer(right, l,
1690 btrfs_leaf_data(right) + BTRFS_LEAF_DATA_SIZE(root) - 1790 btrfs_leaf_data(right) + BTRFS_LEAF_DATA_SIZE(root) -
1691 data_copy_size, btrfs_leaf_data(l) + 1791 data_copy_size, btrfs_leaf_data(l) +
1692 leaf_data_end(root, l), data_copy_size); 1792 leaf_data_end(root, l), data_copy_size);
1793
1693 rt_data_off = BTRFS_LEAF_DATA_SIZE(root) - 1794 rt_data_off = BTRFS_LEAF_DATA_SIZE(root) -
1694 btrfs_item_end(l->items + mid); 1795 btrfs_item_end_nr(l, mid);
1695 1796
1696 for (i = 0; i < btrfs_header_nritems(&right->header); i++) { 1797 for (i = 0; i < nritems; i++) {
1697 u32 ioff = btrfs_item_offset(right->items + i); 1798 struct btrfs_item *item = btrfs_item_nr(right, i);
1698 btrfs_set_item_offset(right->items + i, ioff + rt_data_off); 1799 u32 ioff = btrfs_item_offset(right, item);
1800 btrfs_set_item_offset(right, item, ioff + rt_data_off);
1699 } 1801 }
1700 1802
1701 btrfs_set_header_nritems(&l->header, mid); 1803 btrfs_set_header_nritems(l, mid);
1702 ret = 0; 1804 ret = 0;
1703 wret = insert_ptr(trans, root, path, &right->items[0].key, 1805 btrfs_item_key(right, &disk_key, 0);
1704 bh_blocknr(right_buffer), path->slots[1] + 1, 1); 1806 wret = insert_ptr(trans, root, path, &disk_key,
1807 extent_buffer_blocknr(right), path->slots[1] + 1, 1);
1705 if (wret) 1808 if (wret)
1706 ret = wret; 1809 ret = wret;
1707 btrfs_mark_buffer_dirty(right_buffer); 1810
1708 btrfs_mark_buffer_dirty(l_buf); 1811 btrfs_mark_buffer_dirty(right);
1812 btrfs_mark_buffer_dirty(l);
1709 BUG_ON(path->slots[0] != slot); 1813 BUG_ON(path->slots[0] != slot);
1814
1710 if (mid <= slot) { 1815 if (mid <= slot) {
1711 btrfs_block_release(root, path->nodes[0]); 1816 free_extent_buffer(path->nodes[0]);
1712 path->nodes[0] = right_buffer; 1817 path->nodes[0] = right;
1713 path->slots[0] -= mid; 1818 path->slots[0] -= mid;
1714 path->slots[1] += 1; 1819 path->slots[1] += 1;
1715 } else 1820 } else
1716 btrfs_block_release(root, right_buffer); 1821 free_extent_buffer(right);
1822
1717 BUG_ON(path->slots[0] < 0); 1823 BUG_ON(path->slots[0] < 0);
1718 check_node(root, path, 1); 1824 check_node(root, path, 1);
1825 check_leaf(root, path, 0);
1719 1826
1720 if (!double_split) 1827 if (!double_split)
1721 return ret; 1828 return ret;
1722 right_buffer = btrfs_alloc_free_block(trans, root, l_buf->b_blocknr, 0); 1829
1723 if (IS_ERR(right_buffer)) 1830 right = btrfs_alloc_free_block(trans, root,
1724 return PTR_ERR(right_buffer); 1831 extent_buffer_blocknr(l), 0);
1725 1832 if (IS_ERR(right))
1726 right = btrfs_buffer_leaf(right_buffer); 1833 return PTR_ERR(right);
1727 memset(&right->header, 0, sizeof(right->header)); 1834
1728 btrfs_set_header_blocknr(&right->header, bh_blocknr(right_buffer)); 1835 memset_extent_buffer(right, 0, 0, sizeof(struct btrfs_header));
1729 btrfs_set_header_generation(&right->header, trans->transid); 1836 btrfs_set_header_blocknr(right, extent_buffer_blocknr(right));
1730 btrfs_set_header_owner(&right->header, root->root_key.objectid); 1837 btrfs_set_header_generation(right, trans->transid);
1731 btrfs_set_header_level(&right->header, 0); 1838 btrfs_set_header_owner(right, root->root_key.objectid);
1732 memcpy(right->header.fsid, root->fs_info->disk_super->fsid, 1839 btrfs_set_header_level(right, 0);
1733 sizeof(right->header.fsid)); 1840 write_extent_buffer(right, root->fs_info->fsid,
1841 (unsigned long)btrfs_header_fsid(right),
1842 BTRFS_FSID_SIZE);
1843
1734 btrfs_cpu_key_to_disk(&disk_key, ins_key); 1844 btrfs_cpu_key_to_disk(&disk_key, ins_key);
1735 btrfs_set_header_nritems(&right->header, 0); 1845 btrfs_set_header_nritems(right, 0);
1736 wret = insert_ptr(trans, root, path, 1846 wret = insert_ptr(trans, root, path,
1737 &disk_key, 1847 &disk_key,
1738 bh_blocknr(right_buffer), 1848 extent_buffer_blocknr(right),
1739 path->slots[1], 1); 1849 path->slots[1], 1);
1740 if (wret) 1850 if (wret)
1741 ret = wret; 1851 ret = wret;
@@ -1744,8 +1854,8 @@ static int split_leaf(struct btrfs_trans_handle *trans, struct btrfs_root
1744 if (wret) 1854 if (wret)
1745 ret = wret; 1855 ret = wret;
1746 } 1856 }
1747 btrfs_block_release(root, path->nodes[0]); 1857 free_extent_buffer(path->nodes[0]);
1748 path->nodes[0] = right_buffer; 1858 path->nodes[0] = right;
1749 path->slots[0] = 0; 1859 path->slots[0] = 0;
1750 check_node(root, path, 1); 1860 check_node(root, path, 1);
1751 check_leaf(root, path, 0); 1861 check_leaf(root, path, 0);
@@ -1760,8 +1870,8 @@ int btrfs_truncate_item(struct btrfs_trans_handle *trans,
1760 int ret = 0; 1870 int ret = 0;
1761 int slot; 1871 int slot;
1762 int slot_orig; 1872 int slot_orig;
1763 struct btrfs_leaf *leaf; 1873 struct extent_buffer *leaf;
1764 struct buffer_head *leaf_buf; 1874 struct btrfs_item *item;
1765 u32 nritems; 1875 u32 nritems;
1766 unsigned int data_end; 1876 unsigned int data_end;
1767 unsigned int old_data_start; 1877 unsigned int old_data_start;
@@ -1770,15 +1880,14 @@ int btrfs_truncate_item(struct btrfs_trans_handle *trans,
1770 int i; 1880 int i;
1771 1881
1772 slot_orig = path->slots[0]; 1882 slot_orig = path->slots[0];
1773 leaf_buf = path->nodes[0]; 1883 leaf = path->nodes[0];
1774 leaf = btrfs_buffer_leaf(leaf_buf);
1775 1884
1776 nritems = btrfs_header_nritems(&leaf->header); 1885 nritems = btrfs_header_nritems(leaf);
1777 data_end = leaf_data_end(root, leaf); 1886 data_end = leaf_data_end(root, leaf);
1778 1887
1779 slot = path->slots[0]; 1888 slot = path->slots[0];
1780 old_data_start = btrfs_item_offset(leaf->items + slot); 1889 old_data_start = btrfs_item_offset_nr(leaf, slot);
1781 old_size = btrfs_item_size(leaf->items + slot); 1890 old_size = btrfs_item_size_nr(leaf, slot);
1782 BUG_ON(old_size <= new_size); 1891 BUG_ON(old_size <= new_size);
1783 size_diff = old_size - new_size; 1892 size_diff = old_size - new_size;
1784 1893
@@ -1790,32 +1899,38 @@ int btrfs_truncate_item(struct btrfs_trans_handle *trans,
1790 */ 1899 */
1791 /* first correct the data pointers */ 1900 /* first correct the data pointers */
1792 for (i = slot; i < nritems; i++) { 1901 for (i = slot; i < nritems; i++) {
1793 u32 ioff = btrfs_item_offset(leaf->items + i); 1902 u32 ioff;
1794 btrfs_set_item_offset(leaf->items + i, 1903 item = btrfs_item_nr(leaf, i);
1795 ioff + size_diff); 1904 ioff = btrfs_item_offset(leaf, item);
1905 btrfs_set_item_offset(leaf, item, ioff + size_diff);
1796 } 1906 }
1797 /* shift the data */ 1907 /* shift the data */
1798 btrfs_memmove(root, leaf, btrfs_leaf_data(leaf) + 1908 memmove_extent_buffer(leaf, btrfs_leaf_data(leaf) +
1799 data_end + size_diff, btrfs_leaf_data(leaf) + 1909 data_end + size_diff, btrfs_leaf_data(leaf) +
1800 data_end, old_data_start + new_size - data_end); 1910 data_end, old_data_start + new_size - data_end);
1801 btrfs_set_item_size(leaf->items + slot, new_size); 1911
1802 btrfs_mark_buffer_dirty(leaf_buf); 1912 item = btrfs_item_nr(leaf, slot);
1913 btrfs_set_item_size(leaf, item, new_size);
1914 btrfs_mark_buffer_dirty(leaf);
1803 1915
1804 ret = 0; 1916 ret = 0;
1805 if (btrfs_leaf_free_space(root, leaf) < 0) 1917 if (btrfs_leaf_free_space(root, leaf) < 0) {
1918 btrfs_print_leaf(root, leaf);
1806 BUG(); 1919 BUG();
1920 }
1807 check_leaf(root, path, 0); 1921 check_leaf(root, path, 0);
1808 return ret; 1922 return ret;
1809} 1923}
1810 1924
1811int btrfs_extend_item(struct btrfs_trans_handle *trans, struct btrfs_root 1925int btrfs_extend_item(struct btrfs_trans_handle *trans,
1812 *root, struct btrfs_path *path, u32 data_size) 1926 struct btrfs_root *root, struct btrfs_path *path,
1927 u32 data_size)
1813{ 1928{
1814 int ret = 0; 1929 int ret = 0;
1815 int slot; 1930 int slot;
1816 int slot_orig; 1931 int slot_orig;
1817 struct btrfs_leaf *leaf; 1932 struct extent_buffer *leaf;
1818 struct buffer_head *leaf_buf; 1933 struct btrfs_item *item;
1819 u32 nritems; 1934 u32 nritems;
1820 unsigned int data_end; 1935 unsigned int data_end;
1821 unsigned int old_data; 1936 unsigned int old_data;
@@ -1823,16 +1938,17 @@ int btrfs_extend_item(struct btrfs_trans_handle *trans, struct btrfs_root
1823 int i; 1938 int i;
1824 1939
1825 slot_orig = path->slots[0]; 1940 slot_orig = path->slots[0];
1826 leaf_buf = path->nodes[0]; 1941 leaf = path->nodes[0];
1827 leaf = btrfs_buffer_leaf(leaf_buf);
1828 1942
1829 nritems = btrfs_header_nritems(&leaf->header); 1943 nritems = btrfs_header_nritems(leaf);
1830 data_end = leaf_data_end(root, leaf); 1944 data_end = leaf_data_end(root, leaf);
1831 1945
1832 if (btrfs_leaf_free_space(root, leaf) < data_size) 1946 if (btrfs_leaf_free_space(root, leaf) < data_size) {
1947 btrfs_print_leaf(root, leaf);
1833 BUG(); 1948 BUG();
1949 }
1834 slot = path->slots[0]; 1950 slot = path->slots[0];
1835 old_data = btrfs_item_end(leaf->items + slot); 1951 old_data = btrfs_item_end_nr(leaf, slot);
1836 1952
1837 BUG_ON(slot < 0); 1953 BUG_ON(slot < 0);
1838 BUG_ON(slot >= nritems); 1954 BUG_ON(slot >= nritems);
@@ -1842,22 +1958,28 @@ int btrfs_extend_item(struct btrfs_trans_handle *trans, struct btrfs_root
1842 */ 1958 */
1843 /* first correct the data pointers */ 1959 /* first correct the data pointers */
1844 for (i = slot; i < nritems; i++) { 1960 for (i = slot; i < nritems; i++) {
1845 u32 ioff = btrfs_item_offset(leaf->items + i); 1961 u32 ioff;
1846 btrfs_set_item_offset(leaf->items + i, 1962 item = btrfs_item_nr(leaf, i);
1847 ioff - data_size); 1963 ioff = btrfs_item_offset(leaf, item);
1964 btrfs_set_item_offset(leaf, item, ioff - data_size);
1848 } 1965 }
1966
1849 /* shift the data */ 1967 /* shift the data */
1850 btrfs_memmove(root, leaf, btrfs_leaf_data(leaf) + 1968 memmove_extent_buffer(leaf, btrfs_leaf_data(leaf) +
1851 data_end - data_size, btrfs_leaf_data(leaf) + 1969 data_end - data_size, btrfs_leaf_data(leaf) +
1852 data_end, old_data - data_end); 1970 data_end, old_data - data_end);
1971
1853 data_end = old_data; 1972 data_end = old_data;
1854 old_size = btrfs_item_size(leaf->items + slot); 1973 old_size = btrfs_item_size_nr(leaf, slot);
1855 btrfs_set_item_size(leaf->items + slot, old_size + data_size); 1974 item = btrfs_item_nr(leaf, slot);
1856 btrfs_mark_buffer_dirty(leaf_buf); 1975 btrfs_set_item_size(leaf, item, old_size + data_size);
1976 btrfs_mark_buffer_dirty(leaf);
1857 1977
1858 ret = 0; 1978 ret = 0;
1859 if (btrfs_leaf_free_space(root, leaf) < 0) 1979 if (btrfs_leaf_free_space(root, leaf) < 0) {
1980 btrfs_print_leaf(root, leaf);
1860 BUG(); 1981 BUG();
1982 }
1861 check_leaf(root, path, 0); 1983 check_leaf(root, path, 0);
1862 return ret; 1984 return ret;
1863} 1985}
@@ -1866,15 +1988,16 @@ int btrfs_extend_item(struct btrfs_trans_handle *trans, struct btrfs_root
1866 * Given a key and some data, insert an item into the tree. 1988 * Given a key and some data, insert an item into the tree.
1867 * This does all the path init required, making room in the tree if needed. 1989 * This does all the path init required, making room in the tree if needed.
1868 */ 1990 */
1869int btrfs_insert_empty_item(struct btrfs_trans_handle *trans, struct btrfs_root 1991int btrfs_insert_empty_item(struct btrfs_trans_handle *trans,
1870 *root, struct btrfs_path *path, struct btrfs_key 1992 struct btrfs_root *root,
1871 *cpu_key, u32 data_size) 1993 struct btrfs_path *path,
1994 struct btrfs_key *cpu_key, u32 data_size)
1872{ 1995{
1996 struct extent_buffer *leaf;
1997 struct btrfs_item *item;
1873 int ret = 0; 1998 int ret = 0;
1874 int slot; 1999 int slot;
1875 int slot_orig; 2000 int slot_orig;
1876 struct btrfs_leaf *leaf;
1877 struct buffer_head *leaf_buf;
1878 u32 nritems; 2001 u32 nritems;
1879 unsigned int data_end; 2002 unsigned int data_end;
1880 struct btrfs_disk_key disk_key; 2003 struct btrfs_disk_key disk_key;
@@ -1884,6 +2007,7 @@ int btrfs_insert_empty_item(struct btrfs_trans_handle *trans, struct btrfs_root
1884 /* create a root if there isn't one */ 2007 /* create a root if there isn't one */
1885 if (!root->node) 2008 if (!root->node)
1886 BUG(); 2009 BUG();
2010
1887 ret = btrfs_search_slot(trans, root, cpu_key, path, data_size, 1); 2011 ret = btrfs_search_slot(trans, root, cpu_key, path, data_size, 1);
1888 if (ret == 0) { 2012 if (ret == 0) {
1889 return -EEXIST; 2013 return -EEXIST;
@@ -1892,57 +2016,68 @@ int btrfs_insert_empty_item(struct btrfs_trans_handle *trans, struct btrfs_root
1892 goto out; 2016 goto out;
1893 2017
1894 slot_orig = path->slots[0]; 2018 slot_orig = path->slots[0];
1895 leaf_buf = path->nodes[0]; 2019 leaf = path->nodes[0];
1896 leaf = btrfs_buffer_leaf(leaf_buf);
1897 2020
1898 nritems = btrfs_header_nritems(&leaf->header); 2021 nritems = btrfs_header_nritems(leaf);
1899 data_end = leaf_data_end(root, leaf); 2022 data_end = leaf_data_end(root, leaf);
1900 2023
1901 if (btrfs_leaf_free_space(root, leaf) < 2024 if (btrfs_leaf_free_space(root, leaf) <
1902 sizeof(struct btrfs_item) + data_size) { 2025 sizeof(struct btrfs_item) + data_size) {
1903 BUG(); 2026 BUG();
1904 } 2027 }
2028
1905 slot = path->slots[0]; 2029 slot = path->slots[0];
1906 BUG_ON(slot < 0); 2030 BUG_ON(slot < 0);
2031
1907 if (slot != nritems) { 2032 if (slot != nritems) {
1908 int i; 2033 int i;
1909 unsigned int old_data = btrfs_item_end(leaf->items + slot); 2034 unsigned int old_data = btrfs_item_end_nr(leaf, slot);
1910 2035
2036 if (old_data < data_end) {
2037 btrfs_print_leaf(root, leaf);
2038 printk("slot %d old_data %d data_end %d\n",
2039 slot, old_data, data_end);
2040 BUG_ON(1);
2041 }
1911 /* 2042 /*
1912 * item0..itemN ... dataN.offset..dataN.size .. data0.size 2043 * item0..itemN ... dataN.offset..dataN.size .. data0.size
1913 */ 2044 */
1914 /* first correct the data pointers */ 2045 /* first correct the data pointers */
1915 for (i = slot; i < nritems; i++) { 2046 for (i = slot; i < nritems; i++) {
1916 u32 ioff = btrfs_item_offset(leaf->items + i); 2047 u32 ioff;
1917 btrfs_set_item_offset(leaf->items + i, 2048 item = btrfs_item_nr(leaf, i);
1918 ioff - data_size); 2049 ioff = btrfs_item_offset(leaf, item);
2050 btrfs_set_item_offset(leaf, item, ioff - data_size);
1919 } 2051 }
1920 2052
1921 /* shift the items */ 2053 /* shift the items */
1922 btrfs_memmove(root, leaf, leaf->items + slot + 1, 2054 memmove_extent_buffer(leaf, btrfs_item_nr_offset(slot + 1),
1923 leaf->items + slot, 2055 btrfs_item_nr_offset(slot),
1924 (nritems - slot) * sizeof(struct btrfs_item)); 2056 (nritems - slot) * sizeof(struct btrfs_item));
1925 2057
1926 /* shift the data */ 2058 /* shift the data */
1927 btrfs_memmove(root, leaf, btrfs_leaf_data(leaf) + 2059 memmove_extent_buffer(leaf, btrfs_leaf_data(leaf) +
1928 data_end - data_size, btrfs_leaf_data(leaf) + 2060 data_end - data_size, btrfs_leaf_data(leaf) +
1929 data_end, old_data - data_end); 2061 data_end, old_data - data_end);
1930 data_end = old_data; 2062 data_end = old_data;
1931 } 2063 }
2064
1932 /* setup the item for the new data */ 2065 /* setup the item for the new data */
1933 btrfs_memcpy(root, leaf, &leaf->items[slot].key, &disk_key, 2066 btrfs_set_item_key(leaf, &disk_key, slot);
1934 sizeof(struct btrfs_disk_key)); 2067 item = btrfs_item_nr(leaf, slot);
1935 btrfs_set_item_offset(leaf->items + slot, data_end - data_size); 2068 btrfs_set_item_offset(leaf, item, data_end - data_size);
1936 btrfs_set_item_size(leaf->items + slot, data_size); 2069 btrfs_set_item_size(leaf, item, data_size);
1937 btrfs_set_header_nritems(&leaf->header, nritems + 1); 2070 btrfs_set_header_nritems(leaf, nritems + 1);
1938 btrfs_mark_buffer_dirty(leaf_buf); 2071 btrfs_mark_buffer_dirty(leaf);
1939 2072
1940 ret = 0; 2073 ret = 0;
1941 if (slot == 0) 2074 if (slot == 0)
1942 ret = fixup_low_keys(trans, root, path, &disk_key, 1); 2075 ret = fixup_low_keys(trans, root, path, &disk_key, 1);
1943 2076
1944 if (btrfs_leaf_free_space(root, leaf) < 0) 2077 if (btrfs_leaf_free_space(root, leaf) < 0) {
2078 btrfs_print_leaf(root, leaf);
1945 BUG(); 2079 BUG();
2080 }
1946 check_leaf(root, path, 0); 2081 check_leaf(root, path, 0);
1947out: 2082out:
1948 return ret; 2083 return ret;
@@ -1958,17 +2093,17 @@ int btrfs_insert_item(struct btrfs_trans_handle *trans, struct btrfs_root
1958{ 2093{
1959 int ret = 0; 2094 int ret = 0;
1960 struct btrfs_path *path; 2095 struct btrfs_path *path;
1961 u8 *ptr; 2096 struct extent_buffer *leaf;
2097 unsigned long ptr;
1962 2098
1963 path = btrfs_alloc_path(); 2099 path = btrfs_alloc_path();
1964 BUG_ON(!path); 2100 BUG_ON(!path);
1965 ret = btrfs_insert_empty_item(trans, root, path, cpu_key, data_size); 2101 ret = btrfs_insert_empty_item(trans, root, path, cpu_key, data_size);
1966 if (!ret) { 2102 if (!ret) {
1967 ptr = btrfs_item_ptr(btrfs_buffer_leaf(path->nodes[0]), 2103 leaf = path->nodes[0];
1968 path->slots[0], u8); 2104 ptr = btrfs_item_ptr_offset(leaf, path->slots[0]);
1969 btrfs_memcpy(root, path->nodes[0]->b_data, 2105 write_extent_buffer(leaf, data, ptr, data_size);
1970 ptr, data, data_size); 2106 btrfs_mark_buffer_dirty(leaf);
1971 btrfs_mark_buffer_dirty(path->nodes[0]);
1972 } 2107 }
1973 btrfs_free_path(path); 2108 btrfs_free_path(path);
1974 return ret; 2109 return ret;
@@ -1984,30 +2119,30 @@ int btrfs_insert_item(struct btrfs_trans_handle *trans, struct btrfs_root
1984static int del_ptr(struct btrfs_trans_handle *trans, struct btrfs_root *root, 2119static int del_ptr(struct btrfs_trans_handle *trans, struct btrfs_root *root,
1985 struct btrfs_path *path, int level, int slot) 2120 struct btrfs_path *path, int level, int slot)
1986{ 2121{
1987 struct btrfs_node *node; 2122 struct extent_buffer *parent = path->nodes[level];
1988 struct buffer_head *parent = path->nodes[level];
1989 u32 nritems; 2123 u32 nritems;
1990 int ret = 0; 2124 int ret = 0;
1991 int wret; 2125 int wret;
1992 2126
1993 node = btrfs_buffer_node(parent); 2127 nritems = btrfs_header_nritems(parent);
1994 nritems = btrfs_header_nritems(&node->header);
1995 if (slot != nritems -1) { 2128 if (slot != nritems -1) {
1996 btrfs_memmove(root, node, node->ptrs + slot, 2129 memmove_extent_buffer(parent,
1997 node->ptrs + slot + 1, 2130 btrfs_node_key_ptr_offset(slot),
2131 btrfs_node_key_ptr_offset(slot + 1),
1998 sizeof(struct btrfs_key_ptr) * 2132 sizeof(struct btrfs_key_ptr) *
1999 (nritems - slot - 1)); 2133 (nritems - slot - 1));
2000 } 2134 }
2001 nritems--; 2135 nritems--;
2002 btrfs_set_header_nritems(&node->header, nritems); 2136 btrfs_set_header_nritems(parent, nritems);
2003 if (nritems == 0 && parent == root->node) { 2137 if (nritems == 0 && parent == root->node) {
2004 struct btrfs_header *header = btrfs_buffer_header(root->node); 2138 BUG_ON(btrfs_header_level(root->node) != 1);
2005 BUG_ON(btrfs_header_level(header) != 1);
2006 /* just turn the root into a leaf and break */ 2139 /* just turn the root into a leaf and break */
2007 btrfs_set_header_level(header, 0); 2140 btrfs_set_header_level(root->node, 0);
2008 } else if (slot == 0) { 2141 } else if (slot == 0) {
2009 wret = fixup_low_keys(trans, root, path, &node->ptrs[0].key, 2142 struct btrfs_disk_key disk_key;
2010 level + 1); 2143
2144 btrfs_node_key(parent, &disk_key, 0);
2145 wret = fixup_low_keys(trans, root, path, &disk_key, level + 1);
2011 if (wret) 2146 if (wret)
2012 ret = wret; 2147 ret = wret;
2013 } 2148 }
@@ -2023,59 +2158,67 @@ int btrfs_del_item(struct btrfs_trans_handle *trans, struct btrfs_root *root,
2023 struct btrfs_path *path) 2158 struct btrfs_path *path)
2024{ 2159{
2025 int slot; 2160 int slot;
2026 struct btrfs_leaf *leaf; 2161 struct extent_buffer *leaf;
2027 struct buffer_head *leaf_buf; 2162 struct btrfs_item *item;
2028 int doff; 2163 int doff;
2029 int dsize; 2164 int dsize;
2030 int ret = 0; 2165 int ret = 0;
2031 int wret; 2166 int wret;
2032 u32 nritems; 2167 u32 nritems;
2033 2168
2034 leaf_buf = path->nodes[0]; 2169 leaf = path->nodes[0];
2035 leaf = btrfs_buffer_leaf(leaf_buf);
2036 slot = path->slots[0]; 2170 slot = path->slots[0];
2037 doff = btrfs_item_offset(leaf->items + slot); 2171 doff = btrfs_item_offset_nr(leaf, slot);
2038 dsize = btrfs_item_size(leaf->items + slot); 2172 dsize = btrfs_item_size_nr(leaf, slot);
2039 nritems = btrfs_header_nritems(&leaf->header); 2173 nritems = btrfs_header_nritems(leaf);
2040 2174
2041 if (slot != nritems - 1) { 2175 if (slot != nritems - 1) {
2042 int i; 2176 int i;
2043 int data_end = leaf_data_end(root, leaf); 2177 int data_end = leaf_data_end(root, leaf);
2044 btrfs_memmove(root, leaf, btrfs_leaf_data(leaf) + 2178
2179 memmove_extent_buffer(leaf, btrfs_leaf_data(leaf) +
2045 data_end + dsize, 2180 data_end + dsize,
2046 btrfs_leaf_data(leaf) + data_end, 2181 btrfs_leaf_data(leaf) + data_end,
2047 doff - data_end); 2182 doff - data_end);
2183
2048 for (i = slot + 1; i < nritems; i++) { 2184 for (i = slot + 1; i < nritems; i++) {
2049 u32 ioff = btrfs_item_offset(leaf->items + i); 2185 u32 ioff;
2050 btrfs_set_item_offset(leaf->items + i, ioff + dsize); 2186 item = btrfs_item_nr(leaf, i);
2187 ioff = btrfs_item_offset(leaf, item);
2188 btrfs_set_item_offset(leaf, item, ioff + dsize);
2051 } 2189 }
2052 btrfs_memmove(root, leaf, leaf->items + slot, 2190 memmove_extent_buffer(leaf, btrfs_item_nr_offset(slot),
2053 leaf->items + slot + 1, 2191 btrfs_item_nr_offset(slot + 1),
2054 sizeof(struct btrfs_item) * 2192 sizeof(struct btrfs_item) *
2055 (nritems - slot - 1)); 2193 (nritems - slot - 1));
2056 } 2194 }
2057 btrfs_set_header_nritems(&leaf->header, nritems - 1); 2195 btrfs_set_header_nritems(leaf, nritems - 1);
2058 nritems--; 2196 nritems--;
2197
2059 /* delete the leaf if we've emptied it */ 2198 /* delete the leaf if we've emptied it */
2060 if (nritems == 0) { 2199 if (nritems == 0) {
2061 if (leaf_buf == root->node) { 2200 if (leaf == root->node) {
2062 btrfs_set_header_level(&leaf->header, 0); 2201 btrfs_set_header_level(leaf, 0);
2063 } else { 2202 } else {
2064 clean_tree_block(trans, root, leaf_buf); 2203 clean_tree_block(trans, root, leaf);
2065 wait_on_buffer(leaf_buf); 2204 wait_on_tree_block_writeback(root, leaf);
2066 wret = del_ptr(trans, root, path, 1, path->slots[1]); 2205 wret = del_ptr(trans, root, path, 1, path->slots[1]);
2067 if (wret) 2206 if (wret)
2068 ret = wret; 2207 ret = wret;
2069 wret = btrfs_free_extent(trans, root, 2208 wret = btrfs_free_extent(trans, root,
2070 bh_blocknr(leaf_buf), 1, 1); 2209 extent_buffer_blocknr(leaf),
2210 1, 1);
2071 if (wret) 2211 if (wret)
2072 ret = wret; 2212 ret = wret;
2073 } 2213 }
2074 } else { 2214 } else {
2075 int used = leaf_space_used(leaf, 0, nritems); 2215 int used = leaf_space_used(leaf, 0, nritems);
2076 if (slot == 0) { 2216 if (slot == 0) {
2217 struct btrfs_disk_key disk_key;
2218
2219 btrfs_item_key(leaf, &disk_key, 0);
2077 wret = fixup_low_keys(trans, root, path, 2220 wret = fixup_low_keys(trans, root, path,
2078 &leaf->items[0].key, 1); 2221 &disk_key, 1);
2079 if (wret) 2222 if (wret)
2080 ret = wret; 2223 ret = wret;
2081 } 2224 }
@@ -2087,34 +2230,40 @@ int btrfs_del_item(struct btrfs_trans_handle *trans, struct btrfs_root *root,
2087 * for possible call to del_ptr below 2230 * for possible call to del_ptr below
2088 */ 2231 */
2089 slot = path->slots[1]; 2232 slot = path->slots[1];
2090 get_bh(leaf_buf); 2233 extent_buffer_get(leaf);
2234
2091 wret = push_leaf_left(trans, root, path, 1); 2235 wret = push_leaf_left(trans, root, path, 1);
2092 if (wret < 0 && wret != -ENOSPC) 2236 if (wret < 0 && wret != -ENOSPC)
2093 ret = wret; 2237 ret = wret;
2094 if (path->nodes[0] == leaf_buf && 2238
2095 btrfs_header_nritems(&leaf->header)) { 2239 if (path->nodes[0] == leaf &&
2240 btrfs_header_nritems(leaf)) {
2096 wret = push_leaf_right(trans, root, path, 1); 2241 wret = push_leaf_right(trans, root, path, 1);
2097 if (wret < 0 && wret != -ENOSPC) 2242 if (wret < 0 && wret != -ENOSPC)
2098 ret = wret; 2243 ret = wret;
2099 } 2244 }
2100 if (btrfs_header_nritems(&leaf->header) == 0) { 2245
2101 u64 blocknr = bh_blocknr(leaf_buf); 2246 if (btrfs_header_nritems(leaf) == 0) {
2102 clean_tree_block(trans, root, leaf_buf); 2247 u64 blocknr = extent_buffer_blocknr(leaf);
2103 wait_on_buffer(leaf_buf); 2248
2249 clean_tree_block(trans, root, leaf);
2250 wait_on_tree_block_writeback(root, leaf);
2251
2104 wret = del_ptr(trans, root, path, 1, slot); 2252 wret = del_ptr(trans, root, path, 1, slot);
2105 if (wret) 2253 if (wret)
2106 ret = wret; 2254 ret = wret;
2107 btrfs_block_release(root, leaf_buf); 2255
2256 free_extent_buffer(leaf);
2108 wret = btrfs_free_extent(trans, root, blocknr, 2257 wret = btrfs_free_extent(trans, root, blocknr,
2109 1, 1); 2258 1, 1);
2110 if (wret) 2259 if (wret)
2111 ret = wret; 2260 ret = wret;
2112 } else { 2261 } else {
2113 btrfs_mark_buffer_dirty(leaf_buf); 2262 btrfs_mark_buffer_dirty(leaf);
2114 btrfs_block_release(root, leaf_buf); 2263 free_extent_buffer(leaf);
2115 } 2264 }
2116 } else { 2265 } else {
2117 btrfs_mark_buffer_dirty(leaf_buf); 2266 btrfs_mark_buffer_dirty(leaf);
2118 } 2267 }
2119 } 2268 }
2120 return ret; 2269 return ret;
@@ -2130,25 +2279,27 @@ int btrfs_next_leaf(struct btrfs_root *root, struct btrfs_path *path)
2130 int slot; 2279 int slot;
2131 int level = 1; 2280 int level = 1;
2132 u64 blocknr; 2281 u64 blocknr;
2133 struct buffer_head *c; 2282 struct extent_buffer *c;
2134 struct btrfs_node *c_node; 2283 struct extent_buffer *next = NULL;
2135 struct buffer_head *next = NULL;
2136 2284
2137 while(level < BTRFS_MAX_LEVEL) { 2285 while(level < BTRFS_MAX_LEVEL) {
2138 if (!path->nodes[level]) 2286 if (!path->nodes[level])
2139 return 1; 2287 return 1;
2288
2140 slot = path->slots[level] + 1; 2289 slot = path->slots[level] + 1;
2141 c = path->nodes[level]; 2290 c = path->nodes[level];
2142 c_node = btrfs_buffer_node(c); 2291 if (slot >= btrfs_header_nritems(c)) {
2143 if (slot >= btrfs_header_nritems(&c_node->header)) {
2144 level++; 2292 level++;
2145 continue; 2293 continue;
2146 } 2294 }
2147 blocknr = btrfs_node_blockptr(c_node, slot); 2295
2296 blocknr = btrfs_node_blockptr(c, slot);
2148 if (next) 2297 if (next)
2149 btrfs_block_release(root, next); 2298 free_extent_buffer(next);
2299
2150 if (path->reada) 2300 if (path->reada)
2151 reada_for_search(root, path, level, slot); 2301 reada_for_search(root, path, level, slot);
2302
2152 next = read_tree_block(root, blocknr); 2303 next = read_tree_block(root, blocknr);
2153 break; 2304 break;
2154 } 2305 }
@@ -2156,15 +2307,14 @@ int btrfs_next_leaf(struct btrfs_root *root, struct btrfs_path *path)
2156 while(1) { 2307 while(1) {
2157 level--; 2308 level--;
2158 c = path->nodes[level]; 2309 c = path->nodes[level];
2159 btrfs_block_release(root, c); 2310 free_extent_buffer(c);
2160 path->nodes[level] = next; 2311 path->nodes[level] = next;
2161 path->slots[level] = 0; 2312 path->slots[level] = 0;
2162 if (!level) 2313 if (!level)
2163 break; 2314 break;
2164 if (path->reada) 2315 if (path->reada)
2165 reada_for_search(root, path, level, 0); 2316 reada_for_search(root, path, level, 0);
2166 next = read_tree_block(root, 2317 next = read_tree_block(root, btrfs_node_blockptr(next, 0));
2167 btrfs_node_blockptr(btrfs_buffer_node(next), 0));
2168 } 2318 }
2169 return 0; 2319 return 0;
2170} 2320}
generated by cgit v1.2.2 (git 2.25.0) at 2024-12-30 11:31:55 -0500