Remove offset field from struct btrfs_extent_ref
[platform/upstream/btrfs-progs.git] / ctree.c
1 /*
2  * Copyright (C) 2007 Oracle.  All rights reserved.
3  *
4  * This program is free software; you can redistribute it and/or
5  * modify it under the terms of the GNU General Public
6  * License v2 as published by the Free Software Foundation.
7  *
8  * This program is distributed in the hope that it will be useful,
9  * but WITHOUT ANY WARRANTY; without even the implied warranty of
10  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
11  * General Public License for more details.
12  *
13  * You should have received a copy of the GNU General Public
14  * License along with this program; if not, write to the
15  * Free Software Foundation, Inc., 59 Temple Place - Suite 330,
16  * Boston, MA 021110-1307, USA.
17  */
18 #include "ctree.h"
19 #include "disk-io.h"
20 #include "transaction.h"
21 #include "print-tree.h"
22
23 static int split_node(struct btrfs_trans_handle *trans, struct btrfs_root
24                       *root, struct btrfs_path *path, int level);
25 static int split_leaf(struct btrfs_trans_handle *trans, struct btrfs_root
26                       *root, struct btrfs_key *ins_key,
27                       struct btrfs_path *path, int data_size, int extend);
28 static int push_node_left(struct btrfs_trans_handle *trans,
29                           struct btrfs_root *root, struct extent_buffer *dst,
30                           struct extent_buffer *src, int empty);
31 static int balance_node_right(struct btrfs_trans_handle *trans,
32                               struct btrfs_root *root,
33                               struct extent_buffer *dst_buf,
34                               struct extent_buffer *src_buf);
35 static int del_ptr(struct btrfs_trans_handle *trans, struct btrfs_root *root,
36                    struct btrfs_path *path, int level, int slot);
37
38 inline void btrfs_init_path(struct btrfs_path *p)
39 {
40         memset(p, 0, sizeof(*p));
41 }
42
43 struct btrfs_path *btrfs_alloc_path(void)
44 {
45         struct btrfs_path *path;
46         path = kmalloc(sizeof(struct btrfs_path), GFP_NOFS);
47         if (path) {
48                 btrfs_init_path(path);
49                 path->reada = 0;
50         }
51         return path;
52 }
53
54 void btrfs_free_path(struct btrfs_path *p)
55 {
56         btrfs_release_path(NULL, p);
57         kfree(p);
58 }
59
60 void btrfs_release_path(struct btrfs_root *root, struct btrfs_path *p)
61 {
62         int i;
63         for (i = 0; i < BTRFS_MAX_LEVEL; i++) {
64                 if (!p->nodes[i])
65                         break;
66                 free_extent_buffer(p->nodes[i]);
67         }
68         memset(p, 0, sizeof(*p));
69 }
70
71 static void add_root_to_dirty_list(struct btrfs_root *root)
72 {
73         if (root->track_dirty && list_empty(&root->dirty_list)) {
74                 list_add(&root->dirty_list,
75                          &root->fs_info->dirty_cowonly_roots);
76         }
77 }
78
79 int btrfs_copy_root(struct btrfs_trans_handle *trans,
80                       struct btrfs_root *root,
81                       struct extent_buffer *buf,
82                       struct extent_buffer **cow_ret, u64 new_root_objectid)
83 {
84         struct extent_buffer *cow;
85         int ret = 0;
86         int level;
87         struct btrfs_root *new_root;
88
89         new_root = kmalloc(sizeof(*new_root), GFP_NOFS);
90         if (!new_root)
91                 return -ENOMEM;
92
93         memcpy(new_root, root, sizeof(*new_root));
94         new_root->root_key.objectid = new_root_objectid;
95
96         WARN_ON(root->ref_cows && trans->transid !=
97                 root->fs_info->running_transaction->transid);
98         WARN_ON(root->ref_cows && trans->transid != root->last_trans);
99
100         level = btrfs_header_level(buf);
101         cow = btrfs_alloc_free_block(trans, new_root, buf->len, 0,
102                                      new_root_objectid, trans->transid,
103                                      level, buf->start, 0);
104         if (IS_ERR(cow)) {
105                 kfree(new_root);
106                 return PTR_ERR(cow);
107         }
108
109         copy_extent_buffer(cow, buf, 0, 0, cow->len);
110         btrfs_set_header_bytenr(cow, cow->start);
111         btrfs_set_header_generation(cow, trans->transid);
112         btrfs_set_header_owner(cow, new_root_objectid);
113         btrfs_clear_header_flag(cow, BTRFS_HEADER_FLAG_WRITTEN);
114
115         WARN_ON(btrfs_header_generation(buf) > trans->transid);
116         ret = btrfs_inc_ref(trans, new_root, buf, cow, NULL);
117         kfree(new_root);
118
119         if (ret)
120                 return ret;
121
122         btrfs_mark_buffer_dirty(cow);
123         *cow_ret = cow;
124         return 0;
125 }
126
127 int __btrfs_cow_block(struct btrfs_trans_handle *trans,
128                              struct btrfs_root *root,
129                              struct extent_buffer *buf,
130                              struct extent_buffer *parent, int parent_slot,
131                              struct extent_buffer **cow_ret,
132                              u64 search_start, u64 empty_size)
133 {
134         u64 parent_start;
135         struct extent_buffer *cow;
136         u32 nritems;
137         int ret = 0;
138         int different_trans = 0;
139         int level;
140
141         WARN_ON(root->ref_cows && trans->transid !=
142                 root->fs_info->running_transaction->transid);
143         WARN_ON(root->ref_cows && trans->transid != root->last_trans);
144
145         if (parent)
146                 parent_start = parent->start;
147         else
148                 parent_start = 0;
149
150         level = btrfs_header_level(buf);
151         nritems = btrfs_header_nritems(buf);
152         cow = btrfs_alloc_free_block(trans, root, buf->len, parent_start,
153                                      root->root_key.objectid, trans->transid,
154                                      level, search_start, empty_size);
155         if (IS_ERR(cow))
156                 return PTR_ERR(cow);
157
158         copy_extent_buffer(cow, buf, 0, 0, cow->len);
159         btrfs_set_header_bytenr(cow, cow->start);
160         btrfs_set_header_generation(cow, trans->transid);
161         btrfs_set_header_owner(cow, root->root_key.objectid);
162         btrfs_clear_header_flag(cow, BTRFS_HEADER_FLAG_WRITTEN);
163
164         WARN_ON(btrfs_header_generation(buf) > trans->transid);
165         if (btrfs_header_generation(buf) != trans->transid) {
166                 different_trans = 1;
167                 ret = btrfs_inc_ref(trans, root, buf, cow, NULL);
168                 if (ret)
169                         return ret;
170         } else {
171                 ret = btrfs_update_ref(trans, root, buf, cow, 0, nritems);
172                 if (ret)
173                         return ret;
174                 clean_tree_block(trans, root, buf);
175         }
176
177         if (buf == root->node) {
178                 root->node = cow;
179                 extent_buffer_get(cow);
180                 if (buf != root->commit_root) {
181                         btrfs_free_extent(trans, root, buf->start,
182                                           buf->len, buf->start,
183                                           root->root_key.objectid,
184                                           btrfs_header_generation(buf),
185                                           level, 1);
186                 }
187                 free_extent_buffer(buf);
188                 add_root_to_dirty_list(root);
189         } else {
190                 btrfs_set_node_blockptr(parent, parent_slot,
191                                         cow->start);
192                 WARN_ON(trans->transid == 0);
193                 btrfs_set_node_ptr_generation(parent, parent_slot,
194                                               trans->transid);
195                 btrfs_mark_buffer_dirty(parent);
196                 WARN_ON(btrfs_header_generation(parent) != trans->transid);
197                 btrfs_free_extent(trans, root, buf->start, buf->len,
198                                   parent_start, btrfs_header_owner(parent),
199                                   btrfs_header_generation(parent), level, 1);
200         }
201         free_extent_buffer(buf);
202         btrfs_mark_buffer_dirty(cow);
203         *cow_ret = cow;
204         return 0;
205 }
206
207 int btrfs_cow_block(struct btrfs_trans_handle *trans,
208                     struct btrfs_root *root, struct extent_buffer *buf,
209                     struct extent_buffer *parent, int parent_slot,
210                     struct extent_buffer **cow_ret)
211 {
212         u64 search_start;
213         int ret;
214         /*
215         if (trans->transaction != root->fs_info->running_transaction) {
216                 printk(KERN_CRIT "trans %Lu running %Lu\n", trans->transid,
217                        root->fs_info->running_transaction->transid);
218                 WARN_ON(1);
219         }
220         */
221         if (trans->transid != root->fs_info->generation) {
222                 printk(KERN_CRIT "trans %llu running %llu\n",
223                         (unsigned long long)trans->transid,
224                         (unsigned long long)root->fs_info->generation);
225                 WARN_ON(1);
226         }
227         if (btrfs_header_generation(buf) == trans->transid &&
228             !btrfs_header_flag(buf, BTRFS_HEADER_FLAG_WRITTEN)) {
229                 *cow_ret = buf;
230                 return 0;
231         }
232
233         search_start = buf->start & ~((u64)(1024 * 1024 * 1024) - 1);
234         ret = __btrfs_cow_block(trans, root, buf, parent,
235                                  parent_slot, cow_ret, search_start, 0);
236         return ret;
237 }
238
239 /*
240 static int close_blocks(u64 blocknr, u64 other, u32 blocksize)
241 {
242         if (blocknr < other && other - (blocknr + blocksize) < 32768)
243                 return 1;
244         if (blocknr > other && blocknr - (other + blocksize) < 32768)
245                 return 1;
246         return 0;
247 }
248 */
249
250 /*
251  * compare two keys in a memcmp fashion
252  */
253 int btrfs_comp_keys(struct btrfs_disk_key *disk, struct btrfs_key *k2)
254 {
255         struct btrfs_key k1;
256
257         btrfs_disk_key_to_cpu(&k1, disk);
258
259         if (k1.objectid > k2->objectid)
260                 return 1;
261         if (k1.objectid < k2->objectid)
262                 return -1;
263         if (k1.type > k2->type)
264                 return 1;
265         if (k1.type < k2->type)
266                 return -1;
267         if (k1.offset > k2->offset)
268                 return 1;
269         if (k1.offset < k2->offset)
270                 return -1;
271         return 0;
272 }
273
274
275 #if 0
276 int btrfs_realloc_node(struct btrfs_trans_handle *trans,
277                        struct btrfs_root *root, struct extent_buffer *parent,
278                        int start_slot, int cache_only, u64 *last_ret,
279                        struct btrfs_key *progress)
280 {
281         struct extent_buffer *cur;
282         struct extent_buffer *tmp;
283         u64 blocknr;
284         u64 gen;
285         u64 search_start = *last_ret;
286         u64 last_block = 0;
287         u64 other;
288         u32 parent_nritems;
289         int end_slot;
290         int i;
291         int err = 0;
292         int parent_level;
293         int uptodate;
294         u32 blocksize;
295         int progress_passed = 0;
296         struct btrfs_disk_key disk_key;
297
298         parent_level = btrfs_header_level(parent);
299         if (cache_only && parent_level != 1)
300                 return 0;
301
302         if (trans->transaction != root->fs_info->running_transaction) {
303                 printk(KERN_CRIT "trans %Lu running %Lu\n", trans->transid,
304                        root->fs_info->running_transaction->transid);
305                 WARN_ON(1);
306         }
307         if (trans->transid != root->fs_info->generation) {
308                 printk(KERN_CRIT "trans %Lu running %Lu\n", trans->transid,
309                        root->fs_info->generation);
310                 WARN_ON(1);
311         }
312
313         parent_nritems = btrfs_header_nritems(parent);
314         blocksize = btrfs_level_size(root, parent_level - 1);
315         end_slot = parent_nritems;
316
317         if (parent_nritems == 1)
318                 return 0;
319
320         for (i = start_slot; i < end_slot; i++) {
321                 int close = 1;
322
323                 if (!parent->map_token) {
324                         map_extent_buffer(parent,
325                                         btrfs_node_key_ptr_offset(i),
326                                         sizeof(struct btrfs_key_ptr),
327                                         &parent->map_token, &parent->kaddr,
328                                         &parent->map_start, &parent->map_len,
329                                         KM_USER1);
330                 }
331                 btrfs_node_key(parent, &disk_key, i);
332                 if (!progress_passed && comp_keys(&disk_key, progress) < 0)
333                         continue;
334
335                 progress_passed = 1;
336                 blocknr = btrfs_node_blockptr(parent, i);
337                 gen = btrfs_node_ptr_generation(parent, i);
338                 if (last_block == 0)
339                         last_block = blocknr;
340
341                 if (i > 0) {
342                         other = btrfs_node_blockptr(parent, i - 1);
343                         close = close_blocks(blocknr, other, blocksize);
344                 }
345                 if (close && i < end_slot - 2) {
346                         other = btrfs_node_blockptr(parent, i + 1);
347                         close = close_blocks(blocknr, other, blocksize);
348                 }
349                 if (close) {
350                         last_block = blocknr;
351                         continue;
352                 }
353                 if (parent->map_token) {
354                         unmap_extent_buffer(parent, parent->map_token,
355                                             KM_USER1);
356                         parent->map_token = NULL;
357                 }
358
359                 cur = btrfs_find_tree_block(root, blocknr, blocksize);
360                 if (cur)
361                         uptodate = btrfs_buffer_uptodate(cur, gen);
362                 else
363                         uptodate = 0;
364                 if (!cur || !uptodate) {
365                         if (cache_only) {
366                                 free_extent_buffer(cur);
367                                 continue;
368                         }
369                         if (!cur) {
370                                 cur = read_tree_block(root, blocknr,
371                                                          blocksize, gen);
372                         } else if (!uptodate) {
373                                 btrfs_read_buffer(cur, gen);
374                         }
375                 }
376                 if (search_start == 0)
377                         search_start = last_block;
378
379                 err = __btrfs_cow_block(trans, root, cur, parent, i,
380                                         &tmp, search_start,
381                                         min(16 * blocksize,
382                                             (end_slot - i) * blocksize));
383                 if (err) {
384                         free_extent_buffer(cur);
385                         break;
386                 }
387                 search_start = tmp->start;
388                 last_block = tmp->start;
389                 *last_ret = search_start;
390                 if (parent_level == 1)
391                         btrfs_clear_buffer_defrag(tmp);
392                 free_extent_buffer(tmp);
393         }
394         if (parent->map_token) {
395                 unmap_extent_buffer(parent, parent->map_token,
396                                     KM_USER1);
397                 parent->map_token = NULL;
398         }
399         return err;
400 }
401 #endif
402
403 /*
404  * The leaf data grows from end-to-front in the node.
405  * this returns the address of the start of the last item,
406  * which is the stop of the leaf data stack
407  */
408 static inline unsigned int leaf_data_end(struct btrfs_root *root,
409                                          struct extent_buffer *leaf)
410 {
411         u32 nr = btrfs_header_nritems(leaf);
412         if (nr == 0)
413                 return BTRFS_LEAF_DATA_SIZE(root);
414         return btrfs_item_offset_nr(leaf, nr - 1);
415 }
416
417 static int check_node(struct btrfs_root *root, struct btrfs_path *path,
418                       int level)
419 {
420         struct extent_buffer *parent = NULL;
421         struct extent_buffer *node = path->nodes[level];
422         struct btrfs_disk_key parent_key;
423         struct btrfs_disk_key node_key;
424         int parent_slot;
425         int slot;
426         struct btrfs_key cpukey;
427         u32 nritems = btrfs_header_nritems(node);
428
429         if (path->nodes[level + 1])
430                 parent = path->nodes[level + 1];
431
432         slot = path->slots[level];
433         BUG_ON(nritems == 0);
434         if (parent) {
435                 parent_slot = path->slots[level + 1];
436                 btrfs_node_key(parent, &parent_key, parent_slot);
437                 btrfs_node_key(node, &node_key, 0);
438                 BUG_ON(memcmp(&parent_key, &node_key,
439                               sizeof(struct btrfs_disk_key)));
440                 BUG_ON(btrfs_node_blockptr(parent, parent_slot) !=
441                        btrfs_header_bytenr(node));
442         }
443         BUG_ON(nritems > BTRFS_NODEPTRS_PER_BLOCK(root));
444         if (slot != 0) {
445                 btrfs_node_key_to_cpu(node, &cpukey, slot - 1);
446                 btrfs_node_key(node, &node_key, slot);
447                 BUG_ON(btrfs_comp_keys(&node_key, &cpukey) <= 0);
448         }
449         if (slot < nritems - 1) {
450                 btrfs_node_key_to_cpu(node, &cpukey, slot + 1);
451                 btrfs_node_key(node, &node_key, slot);
452                 BUG_ON(btrfs_comp_keys(&node_key, &cpukey) >= 0);
453         }
454         return 0;
455 }
456
457 static int check_leaf(struct btrfs_root *root, struct btrfs_path *path,
458                       int level)
459 {
460         struct extent_buffer *leaf = path->nodes[level];
461         struct extent_buffer *parent = NULL;
462         int parent_slot;
463         struct btrfs_key cpukey;
464         struct btrfs_disk_key parent_key;
465         struct btrfs_disk_key leaf_key;
466         int slot = path->slots[0];
467
468         u32 nritems = btrfs_header_nritems(leaf);
469
470         if (path->nodes[level + 1])
471                 parent = path->nodes[level + 1];
472
473         if (nritems == 0)
474                 return 0;
475
476         if (parent) {
477                 parent_slot = path->slots[level + 1];
478                 btrfs_node_key(parent, &parent_key, parent_slot);
479                 btrfs_item_key(leaf, &leaf_key, 0);
480
481                 BUG_ON(memcmp(&parent_key, &leaf_key,
482                        sizeof(struct btrfs_disk_key)));
483                 BUG_ON(btrfs_node_blockptr(parent, parent_slot) !=
484                        btrfs_header_bytenr(leaf));
485         }
486 #if 0
487         for (i = 0; nritems > 1 && i < nritems - 2; i++) {
488                 btrfs_item_key_to_cpu(leaf, &cpukey, i + 1);
489                 btrfs_item_key(leaf, &leaf_key, i);
490                 if (comp_keys(&leaf_key, &cpukey) >= 0) {
491                         btrfs_print_leaf(root, leaf);
492                         printk("slot %d offset bad key\n", i);
493                         BUG_ON(1);
494                 }
495                 if (btrfs_item_offset_nr(leaf, i) !=
496                         btrfs_item_end_nr(leaf, i + 1)) {
497                         btrfs_print_leaf(root, leaf);
498                         printk("slot %d offset bad\n", i);
499                         BUG_ON(1);
500                 }
501                 if (i == 0) {
502                         if (btrfs_item_offset_nr(leaf, i) +
503                                btrfs_item_size_nr(leaf, i) !=
504                                BTRFS_LEAF_DATA_SIZE(root)) {
505                                 btrfs_print_leaf(root, leaf);
506                                 printk("slot %d first offset bad\n", i);
507                                 BUG_ON(1);
508                         }
509                 }
510         }
511         if (nritems > 0) {
512                 if (btrfs_item_size_nr(leaf, nritems - 1) > 4096) {
513                                 btrfs_print_leaf(root, leaf);
514                                 printk("slot %d bad size \n", nritems - 1);
515                                 BUG_ON(1);
516                 }
517         }
518 #endif
519         if (slot != 0 && slot < nritems - 1) {
520                 btrfs_item_key(leaf, &leaf_key, slot);
521                 btrfs_item_key_to_cpu(leaf, &cpukey, slot - 1);
522                 if (btrfs_comp_keys(&leaf_key, &cpukey) <= 0) {
523                         btrfs_print_leaf(root, leaf);
524                         printk("slot %d offset bad key\n", slot);
525                         BUG_ON(1);
526                 }
527                 if (btrfs_item_offset_nr(leaf, slot - 1) !=
528                        btrfs_item_end_nr(leaf, slot)) {
529                         btrfs_print_leaf(root, leaf);
530                         printk("slot %d offset bad\n", slot);
531                         BUG_ON(1);
532                 }
533         }
534         if (slot < nritems - 1) {
535                 btrfs_item_key(leaf, &leaf_key, slot);
536                 btrfs_item_key_to_cpu(leaf, &cpukey, slot + 1);
537                 BUG_ON(btrfs_comp_keys(&leaf_key, &cpukey) >= 0);
538                 if (btrfs_item_offset_nr(leaf, slot) !=
539                         btrfs_item_end_nr(leaf, slot + 1)) {
540                         btrfs_print_leaf(root, leaf);
541                         printk("slot %d offset bad\n", slot);
542                         BUG_ON(1);
543                 }
544         }
545         BUG_ON(btrfs_item_offset_nr(leaf, 0) +
546                btrfs_item_size_nr(leaf, 0) != BTRFS_LEAF_DATA_SIZE(root));
547         return 0;
548 }
549
550 static int noinline check_block(struct btrfs_root *root,
551                                 struct btrfs_path *path, int level)
552 {
553         return 0;
554 #if 0
555         struct extent_buffer *buf = path->nodes[level];
556
557         if (memcmp_extent_buffer(buf, root->fs_info->fsid,
558                                  (unsigned long)btrfs_header_fsid(buf),
559                                  BTRFS_FSID_SIZE)) {
560                 printk("warning bad block %Lu\n", buf->start);
561                 return 1;
562         }
563 #endif
564         if (level == 0)
565                 return check_leaf(root, path, level);
566         return check_node(root, path, level);
567 }
568
569 /*
570  * search for key in the extent_buffer.  The items start at offset p,
571  * and they are item_size apart.  There are 'max' items in p.
572  *
573  * the slot in the array is returned via slot, and it points to
574  * the place where you would insert key if it is not found in
575  * the array.
576  *
577  * slot may point to max if the key is bigger than all of the keys
578  */
579 static int generic_bin_search(struct extent_buffer *eb, unsigned long p,
580                               int item_size, struct btrfs_key *key,
581                               int max, int *slot)
582 {
583         int low = 0;
584         int high = max;
585         int mid;
586         int ret;
587         unsigned long offset;
588         struct btrfs_disk_key *tmp;
589
590         while(low < high) {
591                 mid = (low + high) / 2;
592                 offset = p + mid * item_size;
593
594                 tmp = (struct btrfs_disk_key *)(eb->data + offset);
595                 ret = btrfs_comp_keys(tmp, key);
596
597                 if (ret < 0)
598                         low = mid + 1;
599                 else if (ret > 0)
600                         high = mid;
601                 else {
602                         *slot = mid;
603                         return 0;
604                 }
605         }
606         *slot = low;
607         return 1;
608 }
609
610 /*
611  * simple bin_search frontend that does the right thing for
612  * leaves vs nodes
613  */
614 static int bin_search(struct extent_buffer *eb, struct btrfs_key *key,
615                       int level, int *slot)
616 {
617         if (level == 0) {
618                 return generic_bin_search(eb,
619                                           offsetof(struct btrfs_leaf, items),
620                                           sizeof(struct btrfs_item),
621                                           key, btrfs_header_nritems(eb),
622                                           slot);
623         } else {
624                 return generic_bin_search(eb,
625                                           offsetof(struct btrfs_node, ptrs),
626                                           sizeof(struct btrfs_key_ptr),
627                                           key, btrfs_header_nritems(eb),
628                                           slot);
629         }
630         return -1;
631 }
632
633 static struct extent_buffer *read_node_slot(struct btrfs_root *root,
634                                    struct extent_buffer *parent, int slot)
635 {
636         int level = btrfs_header_level(parent);
637         if (slot < 0)
638                 return NULL;
639         if (slot >= btrfs_header_nritems(parent))
640                 return NULL;
641
642         BUG_ON(level == 0);
643
644         return read_tree_block(root, btrfs_node_blockptr(parent, slot),
645                        btrfs_level_size(root, level - 1),
646                        btrfs_node_ptr_generation(parent, slot));
647 }
648
649 static int balance_level(struct btrfs_trans_handle *trans,
650                          struct btrfs_root *root,
651                          struct btrfs_path *path, int level)
652 {
653         struct extent_buffer *right = NULL;
654         struct extent_buffer *mid;
655         struct extent_buffer *left = NULL;
656         struct extent_buffer *parent = NULL;
657         int ret = 0;
658         int wret;
659         int pslot;
660         int orig_slot = path->slots[level];
661         int err_on_enospc = 0;
662         u64 orig_ptr;
663
664         if (level == 0)
665                 return 0;
666
667         mid = path->nodes[level];
668         WARN_ON(btrfs_header_generation(mid) != trans->transid);
669
670         orig_ptr = btrfs_node_blockptr(mid, orig_slot);
671
672         if (level < BTRFS_MAX_LEVEL - 1)
673                 parent = path->nodes[level + 1];
674         pslot = path->slots[level + 1];
675
676         /*
677          * deal with the case where there is only one pointer in the root
678          * by promoting the node below to a root
679          */
680         if (!parent) {
681                 struct extent_buffer *child;
682
683                 if (btrfs_header_nritems(mid) != 1)
684                         return 0;
685
686                 /* promote the child to a root */
687                 child = read_node_slot(root, mid, 0);
688                 BUG_ON(!child);
689                 ret = btrfs_cow_block(trans, root, child, mid, 0, &child);
690                 BUG_ON(ret);
691
692                 root->node = child;
693
694                 ret = btrfs_update_extent_ref(trans, root, child->start,
695                                               mid->start, child->start,
696                                               root->root_key.objectid,
697                                               trans->transid, level - 1);
698                 BUG_ON(ret);
699
700                 add_root_to_dirty_list(root);
701                 path->nodes[level] = NULL;
702                 clean_tree_block(trans, root, mid);
703                 wait_on_tree_block_writeback(root, mid);
704                 /* once for the path */
705                 free_extent_buffer(mid);
706                 ret = btrfs_free_extent(trans, root, mid->start, mid->len,
707                                         mid->start, root->root_key.objectid,
708                                         btrfs_header_generation(mid),
709                                         level, 1);
710                 /* once for the root ptr */
711                 free_extent_buffer(mid);
712                 return ret;
713         }
714         if (btrfs_header_nritems(mid) >
715             BTRFS_NODEPTRS_PER_BLOCK(root) / 4)
716                 return 0;
717
718         if (btrfs_header_nritems(mid) < 2)
719                 err_on_enospc = 1;
720
721         left = read_node_slot(root, parent, pslot - 1);
722         if (left) {
723                 wret = btrfs_cow_block(trans, root, left,
724                                        parent, pslot - 1, &left);
725                 if (wret) {
726                         ret = wret;
727                         goto enospc;
728                 }
729         }
730         right = read_node_slot(root, parent, pslot + 1);
731         if (right) {
732                 wret = btrfs_cow_block(trans, root, right,
733                                        parent, pslot + 1, &right);
734                 if (wret) {
735                         ret = wret;
736                         goto enospc;
737                 }
738         }
739
740         /* first, try to make some room in the middle buffer */
741         if (left) {
742                 orig_slot += btrfs_header_nritems(left);
743                 wret = push_node_left(trans, root, left, mid, 1);
744                 if (wret < 0)
745                         ret = wret;
746                 if (btrfs_header_nritems(mid) < 2)
747                         err_on_enospc = 1;
748         }
749
750         /*
751          * then try to empty the right most buffer into the middle
752          */
753         if (right) {
754                 wret = push_node_left(trans, root, mid, right, 1);
755                 if (wret < 0 && wret != -ENOSPC)
756                         ret = wret;
757                 if (btrfs_header_nritems(right) == 0) {
758                         u64 bytenr = right->start;
759                         u64 generation = btrfs_header_generation(parent);
760                         u32 blocksize = right->len;
761
762                         clean_tree_block(trans, root, right);
763                         wait_on_tree_block_writeback(root, right);
764                         free_extent_buffer(right);
765                         right = NULL;
766                         wret = del_ptr(trans, root, path, level + 1, pslot +
767                                        1);
768                         if (wret)
769                                 ret = wret;
770                         wret = btrfs_free_extent(trans, root, bytenr,
771                                                  blocksize, parent->start,
772                                                  btrfs_header_owner(parent),
773                                                  generation, level, 1);
774                         if (wret)
775                                 ret = wret;
776                 } else {
777                         struct btrfs_disk_key right_key;
778                         btrfs_node_key(right, &right_key, 0);
779                         btrfs_set_node_key(parent, &right_key, pslot + 1);
780                         btrfs_mark_buffer_dirty(parent);
781                 }
782         }
783         if (btrfs_header_nritems(mid) == 1) {
784                 /*
785                  * we're not allowed to leave a node with one item in the
786                  * tree during a delete.  A deletion from lower in the tree
787                  * could try to delete the only pointer in this node.
788                  * So, pull some keys from the left.
789                  * There has to be a left pointer at this point because
790                  * otherwise we would have pulled some pointers from the
791                  * right
792                  */
793                 BUG_ON(!left);
794                 wret = balance_node_right(trans, root, mid, left);
795                 if (wret < 0) {
796                         ret = wret;
797                         goto enospc;
798                 }
799                 if (wret == 1) {
800                         wret = push_node_left(trans, root, left, mid, 1);
801                         if (wret < 0)
802                                 ret = wret;
803                 }
804                 BUG_ON(wret == 1);
805         }
806         if (btrfs_header_nritems(mid) == 0) {
807                 /* we've managed to empty the middle node, drop it */
808                 u64 root_gen = btrfs_header_generation(parent);
809                 u64 bytenr = mid->start;
810                 u32 blocksize = mid->len;
811                 clean_tree_block(trans, root, mid);
812                 wait_on_tree_block_writeback(root, mid);
813                 free_extent_buffer(mid);
814                 mid = NULL;
815                 wret = del_ptr(trans, root, path, level + 1, pslot);
816                 if (wret)
817                         ret = wret;
818                 wret = btrfs_free_extent(trans, root, bytenr, blocksize,
819                                          parent->start,
820                                          btrfs_header_owner(parent),
821                                          root_gen, level, 1);
822                 if (wret)
823                         ret = wret;
824         } else {
825                 /* update the parent key to reflect our changes */
826                 struct btrfs_disk_key mid_key;
827                 btrfs_node_key(mid, &mid_key, 0);
828                 btrfs_set_node_key(parent, &mid_key, pslot);
829                 btrfs_mark_buffer_dirty(parent);
830         }
831
832         /* update the path */
833         if (left) {
834                 if (btrfs_header_nritems(left) > orig_slot) {
835                         extent_buffer_get(left);
836                         path->nodes[level] = left;
837                         path->slots[level + 1] -= 1;
838                         path->slots[level] = orig_slot;
839                         if (mid)
840                                 free_extent_buffer(mid);
841                 } else {
842                         orig_slot -= btrfs_header_nritems(left);
843                         path->slots[level] = orig_slot;
844                 }
845         }
846         /* double check we haven't messed things up */
847         check_block(root, path, level);
848         if (orig_ptr !=
849             btrfs_node_blockptr(path->nodes[level], path->slots[level]))
850                 BUG();
851 enospc:
852         if (right)
853                 free_extent_buffer(right);
854         if (left)
855                 free_extent_buffer(left);
856         return ret;
857 }
858
859 /* returns zero if the push worked, non-zero otherwise */
860 static int noinline push_nodes_for_insert(struct btrfs_trans_handle *trans,
861                                           struct btrfs_root *root,
862                                           struct btrfs_path *path, int level)
863 {
864         struct extent_buffer *right = NULL;
865         struct extent_buffer *mid;
866         struct extent_buffer *left = NULL;
867         struct extent_buffer *parent = NULL;
868         int ret = 0;
869         int wret;
870         int pslot;
871         int orig_slot = path->slots[level];
872         u64 orig_ptr;
873
874         if (level == 0)
875                 return 1;
876
877         mid = path->nodes[level];
878         WARN_ON(btrfs_header_generation(mid) != trans->transid);
879         orig_ptr = btrfs_node_blockptr(mid, orig_slot);
880
881         if (level < BTRFS_MAX_LEVEL - 1)
882                 parent = path->nodes[level + 1];
883         pslot = path->slots[level + 1];
884
885         if (!parent)
886                 return 1;
887
888         left = read_node_slot(root, parent, pslot - 1);
889
890         /* first, try to make some room in the middle buffer */
891         if (left) {
892                 u32 left_nr;
893                 left_nr = btrfs_header_nritems(left);
894                 if (left_nr >= BTRFS_NODEPTRS_PER_BLOCK(root) - 1) {
895                         wret = 1;
896                 } else {
897                         ret = btrfs_cow_block(trans, root, left, parent,
898                                               pslot - 1, &left);
899                         if (ret)
900                                 wret = 1;
901                         else {
902                                 wret = push_node_left(trans, root,
903                                                       left, mid, 0);
904                         }
905                 }
906                 if (wret < 0)
907                         ret = wret;
908                 if (wret == 0) {
909                         struct btrfs_disk_key disk_key;
910                         orig_slot += left_nr;
911                         btrfs_node_key(mid, &disk_key, 0);
912                         btrfs_set_node_key(parent, &disk_key, pslot);
913                         btrfs_mark_buffer_dirty(parent);
914                         if (btrfs_header_nritems(left) > orig_slot) {
915                                 path->nodes[level] = left;
916                                 path->slots[level + 1] -= 1;
917                                 path->slots[level] = orig_slot;
918                                 free_extent_buffer(mid);
919                         } else {
920                                 orig_slot -=
921                                         btrfs_header_nritems(left);
922                                 path->slots[level] = orig_slot;
923                                 free_extent_buffer(left);
924                         }
925                         return 0;
926                 }
927                 free_extent_buffer(left);
928         }
929         right= read_node_slot(root, parent, pslot + 1);
930
931         /*
932          * then try to empty the right most buffer into the middle
933          */
934         if (right) {
935                 u32 right_nr;
936                 right_nr = btrfs_header_nritems(right);
937                 if (right_nr >= BTRFS_NODEPTRS_PER_BLOCK(root) - 1) {
938                         wret = 1;
939                 } else {
940                         ret = btrfs_cow_block(trans, root, right,
941                                               parent, pslot + 1,
942                                               &right);
943                         if (ret)
944                                 wret = 1;
945                         else {
946                                 wret = balance_node_right(trans, root,
947                                                           right, mid);
948                         }
949                 }
950                 if (wret < 0)
951                         ret = wret;
952                 if (wret == 0) {
953                         struct btrfs_disk_key disk_key;
954
955                         btrfs_node_key(right, &disk_key, 0);
956                         btrfs_set_node_key(parent, &disk_key, pslot + 1);
957                         btrfs_mark_buffer_dirty(parent);
958
959                         if (btrfs_header_nritems(mid) <= orig_slot) {
960                                 path->nodes[level] = right;
961                                 path->slots[level + 1] += 1;
962                                 path->slots[level] = orig_slot -
963                                         btrfs_header_nritems(mid);
964                                 free_extent_buffer(mid);
965                         } else {
966                                 free_extent_buffer(right);
967                         }
968                         return 0;
969                 }
970                 free_extent_buffer(right);
971         }
972         return 1;
973 }
974
975 /*
976  * readahead one full node of leaves
977  */
978 static void reada_for_search(struct btrfs_root *root, struct btrfs_path *path,
979                              int level, int slot, u64 objectid)
980 {
981         struct extent_buffer *node;
982         struct btrfs_disk_key disk_key;
983         u32 nritems;
984         u64 search;
985         u64 lowest_read;
986         u64 highest_read;
987         u64 nread = 0;
988         int direction = path->reada;
989         struct extent_buffer *eb;
990         u32 nr;
991         u32 blocksize;
992         u32 nscan = 0;
993
994         if (level != 1)
995                 return;
996
997         if (!path->nodes[level])
998                 return;
999
1000         node = path->nodes[level];
1001         search = btrfs_node_blockptr(node, slot);
1002         blocksize = btrfs_level_size(root, level - 1);
1003         eb = btrfs_find_tree_block(root, search, blocksize);
1004         if (eb) {
1005                 free_extent_buffer(eb);
1006                 return;
1007         }
1008
1009         highest_read = search;
1010         lowest_read = search;
1011
1012         nritems = btrfs_header_nritems(node);
1013         nr = slot;
1014         while(1) {
1015                 if (direction < 0) {
1016                         if (nr == 0)
1017                                 break;
1018                         nr--;
1019                 } else if (direction > 0) {
1020                         nr++;
1021                         if (nr >= nritems)
1022                                 break;
1023                 }
1024                 if (path->reada < 0 && objectid) {
1025                         btrfs_node_key(node, &disk_key, nr);
1026                         if (btrfs_disk_key_objectid(&disk_key) != objectid)
1027                                 break;
1028                 }
1029                 search = btrfs_node_blockptr(node, nr);
1030                 if ((search >= lowest_read && search <= highest_read) ||
1031                     (search < lowest_read && lowest_read - search <= 32768) ||
1032                     (search > highest_read && search - highest_read <= 32768)) {
1033                         readahead_tree_block(root, search, blocksize,
1034                                      btrfs_node_ptr_generation(node, nr));
1035                         nread += blocksize;
1036                 }
1037                 nscan++;
1038                 if (path->reada < 2 && (nread > (256 * 1024) || nscan > 32))
1039                         break;
1040                 if(nread > (1024 * 1024) || nscan > 128)
1041                         break;
1042
1043                 if (search < lowest_read)
1044                         lowest_read = search;
1045                 if (search > highest_read)
1046                         highest_read = search;
1047         }
1048 }
1049
1050 /*
1051  * look for key in the tree.  path is filled in with nodes along the way
1052  * if key is found, we return zero and you can find the item in the leaf
1053  * level of the path (level 0)
1054  *
1055  * If the key isn't found, the path points to the slot where it should
1056  * be inserted, and 1 is returned.  If there are other errors during the
1057  * search a negative error number is returned.
1058  *
1059  * if ins_len > 0, nodes and leaves will be split as we walk down the
1060  * tree.  if ins_len < 0, nodes will be merged as we walk down the tree (if
1061  * possible)
1062  */
1063 int btrfs_search_slot(struct btrfs_trans_handle *trans, struct btrfs_root
1064                       *root, struct btrfs_key *key, struct btrfs_path *p, int
1065                       ins_len, int cow)
1066 {
1067         struct extent_buffer *b;
1068         int slot;
1069         int ret;
1070         int level;
1071         int should_reada = p->reada;
1072         u8 lowest_level = 0;
1073
1074         lowest_level = p->lowest_level;
1075         WARN_ON(lowest_level && ins_len);
1076         WARN_ON(p->nodes[0] != NULL);
1077         /*
1078         WARN_ON(!mutex_is_locked(&root->fs_info->fs_mutex));
1079         */
1080 again:
1081         b = root->node;
1082         extent_buffer_get(b);
1083         while (b) {
1084                 level = btrfs_header_level(b);
1085                 if (cow) {
1086                         int wret;
1087                         wret = btrfs_cow_block(trans, root, b,
1088                                                p->nodes[level + 1],
1089                                                p->slots[level + 1],
1090                                                &b);
1091                         if (wret) {
1092                                 free_extent_buffer(b);
1093                                 return wret;
1094                         }
1095                 }
1096                 BUG_ON(!cow && ins_len);
1097                 if (level != btrfs_header_level(b))
1098                         WARN_ON(1);
1099                 level = btrfs_header_level(b);
1100                 p->nodes[level] = b;
1101                 ret = check_block(root, p, level);
1102                 if (ret)
1103                         return -1;
1104                 ret = bin_search(b, key, level, &slot);
1105                 if (level != 0) {
1106                         if (ret && slot > 0)
1107                                 slot -= 1;
1108                         p->slots[level] = slot;
1109                         if (ins_len > 0 && btrfs_header_nritems(b) >=
1110                             BTRFS_NODEPTRS_PER_BLOCK(root) - 3) {
1111                                 int sret = split_node(trans, root, p, level);
1112                                 BUG_ON(sret > 0);
1113                                 if (sret)
1114                                         return sret;
1115                                 b = p->nodes[level];
1116                                 slot = p->slots[level];
1117                         } else if (ins_len < 0) {
1118                                 int sret = balance_level(trans, root, p,
1119                                                          level);
1120                                 if (sret)
1121                                         return sret;
1122                                 b = p->nodes[level];
1123                                 if (!b) {
1124                                         btrfs_release_path(NULL, p);
1125                                         goto again;
1126                                 }
1127                                 slot = p->slots[level];
1128                                 BUG_ON(btrfs_header_nritems(b) == 1);
1129                         }
1130                         /* this is only true while dropping a snapshot */
1131                         if (level == lowest_level)
1132                                 break;
1133
1134                         if (should_reada)
1135                                 reada_for_search(root, p, level, slot,
1136                                                  key->objectid);
1137
1138                         b = read_node_slot(root, b, slot);
1139                 } else {
1140                         p->slots[level] = slot;
1141                         if (ins_len > 0 && btrfs_leaf_free_space(root, b) <
1142                             sizeof(struct btrfs_item) + ins_len) {
1143                                 int sret = split_leaf(trans, root, key,
1144                                                       p, ins_len, ret == 0);
1145                                 BUG_ON(sret > 0);
1146                                 if (sret)
1147                                         return sret;
1148                         }
1149                         return ret;
1150                 }
1151         }
1152         return 1;
1153 }
1154
1155 /*
1156  * adjust the pointers going up the tree, starting at level
1157  * making sure the right key of each node is points to 'key'.
1158  * This is used after shifting pointers to the left, so it stops
1159  * fixing up pointers when a given leaf/node is not in slot 0 of the
1160  * higher levels
1161  *
1162  * If this fails to write a tree block, it returns -1, but continues
1163  * fixing up the blocks in ram so the tree is consistent.
1164  */
1165 static int fixup_low_keys(struct btrfs_trans_handle *trans,
1166                           struct btrfs_root *root, struct btrfs_path *path,
1167                           struct btrfs_disk_key *key, int level)
1168 {
1169         int i;
1170         int ret = 0;
1171         struct extent_buffer *t;
1172
1173         for (i = level; i < BTRFS_MAX_LEVEL; i++) {
1174                 int tslot = path->slots[i];
1175                 if (!path->nodes[i])
1176                         break;
1177                 t = path->nodes[i];
1178                 btrfs_set_node_key(t, key, tslot);
1179                 btrfs_mark_buffer_dirty(path->nodes[i]);
1180                 if (tslot != 0)
1181                         break;
1182         }
1183         return ret;
1184 }
1185
1186 /*
1187  * update item key.
1188  *
1189  * This function isn't completely safe. It's the caller's responsibility
1190  * that the new key won't break the order
1191  */
1192 int btrfs_set_item_key_safe(struct btrfs_trans_handle *trans,
1193                             struct btrfs_root *root, struct btrfs_path *path,
1194                             struct btrfs_key *new_key)
1195 {
1196         struct btrfs_disk_key disk_key;
1197         struct extent_buffer *eb;
1198         int slot;
1199
1200         eb = path->nodes[0];
1201         slot = path->slots[0];
1202         if (slot > 0) {
1203                 btrfs_item_key(eb, &disk_key, slot - 1);
1204                 if (btrfs_comp_keys(&disk_key, new_key) >= 0)
1205                         return -1;
1206         }
1207         if (slot < btrfs_header_nritems(eb) - 1) {
1208                 btrfs_item_key(eb, &disk_key, slot + 1);
1209                 if (btrfs_comp_keys(&disk_key, new_key) <= 0)
1210                         return -1;
1211         }
1212
1213         btrfs_cpu_key_to_disk(&disk_key, new_key);
1214         btrfs_set_item_key(eb, &disk_key, slot);
1215         btrfs_mark_buffer_dirty(eb);
1216         if (slot == 0)
1217                 fixup_low_keys(trans, root, path, &disk_key, 1);
1218         return 0;
1219 }
1220
1221 /*
1222  * try to push data from one node into the next node left in the
1223  * tree.
1224  *
1225  * returns 0 if some ptrs were pushed left, < 0 if there was some horrible
1226  * error, and > 0 if there was no room in the left hand block.
1227  */
1228 static int push_node_left(struct btrfs_trans_handle *trans,
1229                           struct btrfs_root *root, struct extent_buffer *dst,
1230                           struct extent_buffer *src, int empty)
1231 {
1232         int push_items = 0;
1233         int src_nritems;
1234         int dst_nritems;
1235         int ret = 0;
1236
1237         src_nritems = btrfs_header_nritems(src);
1238         dst_nritems = btrfs_header_nritems(dst);
1239         push_items = BTRFS_NODEPTRS_PER_BLOCK(root) - dst_nritems;
1240         WARN_ON(btrfs_header_generation(src) != trans->transid);
1241         WARN_ON(btrfs_header_generation(dst) != trans->transid);
1242
1243         if (!empty && src_nritems <= 8)
1244                 return 1;
1245
1246         if (push_items <= 0) {
1247                 return 1;
1248         }
1249
1250         if (empty) {
1251                 push_items = min(src_nritems, push_items);
1252                 if (push_items < src_nritems) {
1253                         /* leave at least 8 pointers in the node if
1254                          * we aren't going to empty it
1255                          */
1256                         if (src_nritems - push_items < 8) {
1257                                 if (push_items <= 8)
1258                                         return 1;
1259                                 push_items -= 8;
1260                         }
1261                 }
1262         } else
1263                 push_items = min(src_nritems - 8, push_items);
1264
1265         copy_extent_buffer(dst, src,
1266                            btrfs_node_key_ptr_offset(dst_nritems),
1267                            btrfs_node_key_ptr_offset(0),
1268                            push_items * sizeof(struct btrfs_key_ptr));
1269
1270         if (push_items < src_nritems) {
1271                 memmove_extent_buffer(src, btrfs_node_key_ptr_offset(0),
1272                                       btrfs_node_key_ptr_offset(push_items),
1273                                       (src_nritems - push_items) *
1274                                       sizeof(struct btrfs_key_ptr));
1275         }
1276         btrfs_set_header_nritems(src, src_nritems - push_items);
1277         btrfs_set_header_nritems(dst, dst_nritems + push_items);
1278         btrfs_mark_buffer_dirty(src);
1279         btrfs_mark_buffer_dirty(dst);
1280
1281         ret = btrfs_update_ref(trans, root, src, dst, dst_nritems, push_items);
1282         BUG_ON(ret);
1283         return ret;
1284 }
1285
1286 /*
1287  * try to push data from one node into the next node right in the
1288  * tree.
1289  *
1290  * returns 0 if some ptrs were pushed, < 0 if there was some horrible
1291  * error, and > 0 if there was no room in the right hand block.
1292  *
1293  * this will  only push up to 1/2 the contents of the left node over
1294  */
1295 static int balance_node_right(struct btrfs_trans_handle *trans,
1296                               struct btrfs_root *root,
1297                               struct extent_buffer *dst,
1298                               struct extent_buffer *src)
1299 {
1300         int push_items = 0;
1301         int max_push;
1302         int src_nritems;
1303         int dst_nritems;
1304         int ret = 0;
1305
1306         WARN_ON(btrfs_header_generation(src) != trans->transid);
1307         WARN_ON(btrfs_header_generation(dst) != trans->transid);
1308
1309         src_nritems = btrfs_header_nritems(src);
1310         dst_nritems = btrfs_header_nritems(dst);
1311         push_items = BTRFS_NODEPTRS_PER_BLOCK(root) - dst_nritems;
1312         if (push_items <= 0) {
1313                 return 1;
1314         }
1315
1316         if (src_nritems < 4) {
1317                 return 1;
1318         }
1319
1320         max_push = src_nritems / 2 + 1;
1321         /* don't try to empty the node */
1322         if (max_push >= src_nritems) {
1323                 return 1;
1324         }
1325
1326         if (max_push < push_items)
1327                 push_items = max_push;
1328
1329         memmove_extent_buffer(dst, btrfs_node_key_ptr_offset(push_items),
1330                                       btrfs_node_key_ptr_offset(0),
1331                                       (dst_nritems) *
1332                                       sizeof(struct btrfs_key_ptr));
1333
1334         copy_extent_buffer(dst, src,
1335                            btrfs_node_key_ptr_offset(0),
1336                            btrfs_node_key_ptr_offset(src_nritems - push_items),
1337                            push_items * sizeof(struct btrfs_key_ptr));
1338
1339         btrfs_set_header_nritems(src, src_nritems - push_items);
1340         btrfs_set_header_nritems(dst, dst_nritems + push_items);
1341
1342         btrfs_mark_buffer_dirty(src);
1343         btrfs_mark_buffer_dirty(dst);
1344
1345         ret = btrfs_update_ref(trans, root, src, dst, 0, push_items);
1346         BUG_ON(ret);
1347         return ret;
1348 }
1349
1350 /*
1351  * helper function to insert a new root level in the tree.
1352  * A new node is allocated, and a single item is inserted to
1353  * point to the existing root
1354  *
1355  * returns zero on success or < 0 on failure.
1356  */
1357 static int noinline insert_new_root(struct btrfs_trans_handle *trans,
1358                            struct btrfs_root *root,
1359                            struct btrfs_path *path, int level)
1360 {
1361         u64 lower_gen;
1362         struct extent_buffer *lower;
1363         struct extent_buffer *c;
1364         struct extent_buffer *old;
1365         struct btrfs_disk_key lower_key;
1366         int ret;
1367
1368         BUG_ON(path->nodes[level]);
1369         BUG_ON(path->nodes[level-1] != root->node);
1370
1371         lower = path->nodes[level-1];
1372         if (level == 1)
1373                 btrfs_item_key(lower, &lower_key, 0);
1374         else
1375                 btrfs_node_key(lower, &lower_key, 0);
1376
1377         c = btrfs_alloc_free_block(trans, root, root->nodesize, 0,
1378                                    root->root_key.objectid,
1379                                    trans->transid, level,
1380                                    root->node->start, 0);
1381         if (IS_ERR(c))
1382                 return PTR_ERR(c);
1383
1384         memset_extent_buffer(c, 0, 0, root->nodesize);
1385         btrfs_set_header_nritems(c, 1);
1386         btrfs_set_header_level(c, level);
1387         btrfs_set_header_bytenr(c, c->start);
1388         btrfs_set_header_generation(c, trans->transid);
1389         btrfs_set_header_owner(c, root->root_key.objectid);
1390
1391         write_extent_buffer(c, root->fs_info->fsid,
1392                             (unsigned long)btrfs_header_fsid(c),
1393                             BTRFS_FSID_SIZE);
1394
1395         write_extent_buffer(c, root->fs_info->chunk_tree_uuid,
1396                             (unsigned long)btrfs_header_chunk_tree_uuid(c),
1397                             BTRFS_UUID_SIZE);
1398
1399         btrfs_set_node_key(c, &lower_key, 0);
1400         btrfs_set_node_blockptr(c, 0, lower->start);
1401         lower_gen = btrfs_header_generation(lower);
1402         WARN_ON(lower_gen != trans->transid);
1403
1404         btrfs_set_node_ptr_generation(c, 0, lower_gen);
1405
1406         btrfs_mark_buffer_dirty(c);
1407
1408         old = root->node;
1409         root->node = c;
1410
1411         ret = btrfs_update_extent_ref(trans, root, lower->start,
1412                                       lower->start, c->start,
1413                                       root->root_key.objectid,
1414                                       trans->transid, level - 1);
1415         BUG_ON(ret);
1416
1417         /* the super has an extra ref to root->node */
1418         free_extent_buffer(old);
1419
1420         add_root_to_dirty_list(root);
1421         extent_buffer_get(c);
1422         path->nodes[level] = c;
1423         path->slots[level] = 0;
1424         return 0;
1425 }
1426
1427 /*
1428  * worker function to insert a single pointer in a node.
1429  * the node should have enough room for the pointer already
1430  *
1431  * slot and level indicate where you want the key to go, and
1432  * blocknr is the block the key points to.
1433  *
1434  * returns zero on success and < 0 on any error
1435  */
1436 static int insert_ptr(struct btrfs_trans_handle *trans, struct btrfs_root
1437                       *root, struct btrfs_path *path, struct btrfs_disk_key
1438                       *key, u64 bytenr, int slot, int level)
1439 {
1440         struct extent_buffer *lower;
1441         int nritems;
1442
1443         BUG_ON(!path->nodes[level]);
1444         lower = path->nodes[level];
1445         nritems = btrfs_header_nritems(lower);
1446         if (slot > nritems)
1447                 BUG();
1448         if (nritems == BTRFS_NODEPTRS_PER_BLOCK(root))
1449                 BUG();
1450         if (slot != nritems) {
1451                 memmove_extent_buffer(lower,
1452                               btrfs_node_key_ptr_offset(slot + 1),
1453                               btrfs_node_key_ptr_offset(slot),
1454                               (nritems - slot) * sizeof(struct btrfs_key_ptr));
1455         }
1456         btrfs_set_node_key(lower, key, slot);
1457         btrfs_set_node_blockptr(lower, slot, bytenr);
1458         WARN_ON(trans->transid == 0);
1459         btrfs_set_node_ptr_generation(lower, slot, trans->transid);
1460         btrfs_set_header_nritems(lower, nritems + 1);
1461         btrfs_mark_buffer_dirty(lower);
1462         return 0;
1463 }
1464
1465 /*
1466  * split the node at the specified level in path in two.
1467  * The path is corrected to point to the appropriate node after the split
1468  *
1469  * Before splitting this tries to make some room in the node by pushing
1470  * left and right, if either one works, it returns right away.
1471  *
1472  * returns 0 on success and < 0 on failure
1473  */
1474 static int split_node(struct btrfs_trans_handle *trans, struct btrfs_root
1475                       *root, struct btrfs_path *path, int level)
1476 {
1477         struct extent_buffer *c;
1478         struct extent_buffer *split;
1479         struct btrfs_disk_key disk_key;
1480         int mid;
1481         int ret;
1482         int wret;
1483         u32 c_nritems;
1484
1485         c = path->nodes[level];
1486         WARN_ON(btrfs_header_generation(c) != trans->transid);
1487         if (c == root->node) {
1488                 /* trying to split the root, lets make a new one */
1489                 ret = insert_new_root(trans, root, path, level + 1);
1490                 if (ret)
1491                         return ret;
1492         } else {
1493                 ret = push_nodes_for_insert(trans, root, path, level);
1494                 c = path->nodes[level];
1495                 if (!ret && btrfs_header_nritems(c) <
1496                     BTRFS_NODEPTRS_PER_BLOCK(root) - 3)
1497                         return 0;
1498                 if (ret < 0)
1499                         return ret;
1500         }
1501
1502         c_nritems = btrfs_header_nritems(c);
1503
1504         btrfs_node_key(c, &disk_key, 0);
1505         split = btrfs_alloc_free_block(trans, root, root->nodesize,
1506                                          path->nodes[level + 1]->start,
1507                                          root->root_key.objectid,
1508                                          trans->transid, level, c->start, 0);
1509         if (IS_ERR(split))
1510                 return PTR_ERR(split);
1511
1512         btrfs_set_header_flags(split, btrfs_header_flags(c));
1513         btrfs_set_header_level(split, btrfs_header_level(c));
1514         btrfs_set_header_bytenr(split, split->start);
1515         btrfs_set_header_generation(split, trans->transid);
1516         btrfs_set_header_owner(split, root->root_key.objectid);
1517         btrfs_set_header_flags(split, 0);
1518         write_extent_buffer(split, root->fs_info->fsid,
1519                             (unsigned long)btrfs_header_fsid(split),
1520                             BTRFS_FSID_SIZE);
1521         write_extent_buffer(split, root->fs_info->chunk_tree_uuid,
1522                             (unsigned long)btrfs_header_chunk_tree_uuid(split),
1523                             BTRFS_UUID_SIZE);
1524
1525         mid = (c_nritems + 1) / 2;
1526
1527         copy_extent_buffer(split, c,
1528                            btrfs_node_key_ptr_offset(0),
1529                            btrfs_node_key_ptr_offset(mid),
1530                            (c_nritems - mid) * sizeof(struct btrfs_key_ptr));
1531         btrfs_set_header_nritems(split, c_nritems - mid);
1532         btrfs_set_header_nritems(c, mid);
1533         ret = 0;
1534
1535         btrfs_mark_buffer_dirty(c);
1536         btrfs_mark_buffer_dirty(split);
1537
1538         btrfs_node_key(split, &disk_key, 0);
1539         wret = insert_ptr(trans, root, path, &disk_key, split->start,
1540                           path->slots[level + 1] + 1,
1541                           level + 1);
1542         if (wret)
1543                 ret = wret;
1544
1545         ret = btrfs_update_ref(trans, root, c, split, 0, c_nritems - mid);
1546         BUG_ON(ret);
1547
1548         if (path->slots[level] >= mid) {
1549                 path->slots[level] -= mid;
1550                 free_extent_buffer(c);
1551                 path->nodes[level] = split;
1552                 path->slots[level + 1] += 1;
1553         } else {
1554                 free_extent_buffer(split);
1555         }
1556         return ret;
1557 }
1558
1559 /*
1560  * how many bytes are required to store the items in a leaf.  start
1561  * and nr indicate which items in the leaf to check.  This totals up the
1562  * space used both by the item structs and the item data
1563  */
1564 static int leaf_space_used(struct extent_buffer *l, int start, int nr)
1565 {
1566         int data_len;
1567         int nritems = btrfs_header_nritems(l);
1568         int end = min(nritems, start + nr) - 1;
1569
1570         if (!nr)
1571                 return 0;
1572         data_len = btrfs_item_end_nr(l, start);
1573         data_len = data_len - btrfs_item_offset_nr(l, end);
1574         data_len += sizeof(struct btrfs_item) * nr;
1575         WARN_ON(data_len < 0);
1576         return data_len;
1577 }
1578
1579 /*
1580  * The space between the end of the leaf items and
1581  * the start of the leaf data.  IOW, how much room
1582  * the leaf has left for both items and data
1583  */
1584 int btrfs_leaf_free_space(struct btrfs_root *root, struct extent_buffer *leaf)
1585 {
1586         int nritems = btrfs_header_nritems(leaf);
1587         int ret;
1588         ret = BTRFS_LEAF_DATA_SIZE(root) - leaf_space_used(leaf, 0, nritems);
1589         if (ret < 0) {
1590                 printk("leaf free space ret %d, leaf data size %lu, used %d nritems %d\n",
1591                        ret, (unsigned long) BTRFS_LEAF_DATA_SIZE(root),
1592                        leaf_space_used(leaf, 0, nritems), nritems);
1593         }
1594         return ret;
1595 }
1596
1597 /*
1598  * push some data in the path leaf to the right, trying to free up at
1599  * least data_size bytes.  returns zero if the push worked, nonzero otherwise
1600  *
1601  * returns 1 if the push failed because the other node didn't have enough
1602  * room, 0 if everything worked out and < 0 if there were major errors.
1603  */
1604 static int push_leaf_right(struct btrfs_trans_handle *trans, struct btrfs_root
1605                            *root, struct btrfs_path *path, int data_size,
1606                            int empty)
1607 {
1608         struct extent_buffer *left = path->nodes[0];
1609         struct extent_buffer *right;
1610         struct extent_buffer *upper;
1611         struct btrfs_disk_key disk_key;
1612         int slot;
1613         u32 i;
1614         int free_space;
1615         int push_space = 0;
1616         int push_items = 0;
1617         struct btrfs_item *item;
1618         u32 left_nritems;
1619         u32 nr;
1620         u32 right_nritems;
1621         u32 data_end;
1622         u32 this_item_size;
1623         int ret;
1624
1625         slot = path->slots[1];
1626         if (!path->nodes[1]) {
1627                 return 1;
1628         }
1629         upper = path->nodes[1];
1630         if (slot >= btrfs_header_nritems(upper) - 1)
1631                 return 1;
1632
1633         right = read_node_slot(root, upper, slot + 1);
1634         free_space = btrfs_leaf_free_space(root, right);
1635         if (free_space < data_size + sizeof(struct btrfs_item)) {
1636                 free_extent_buffer(right);
1637                 return 1;
1638         }
1639
1640         /* cow and double check */
1641         ret = btrfs_cow_block(trans, root, right, upper,
1642                               slot + 1, &right);
1643         if (ret) {
1644                 free_extent_buffer(right);
1645                 return 1;
1646         }
1647         free_space = btrfs_leaf_free_space(root, right);
1648         if (free_space < data_size + sizeof(struct btrfs_item)) {
1649                 free_extent_buffer(right);
1650                 return 1;
1651         }
1652
1653         left_nritems = btrfs_header_nritems(left);
1654         if (left_nritems == 0) {
1655                 free_extent_buffer(right);
1656                 return 1;
1657         }
1658
1659         if (empty)
1660                 nr = 0;
1661         else
1662                 nr = 1;
1663
1664         i = left_nritems - 1;
1665         while (i >= nr) {
1666                 item = btrfs_item_nr(left, i);
1667
1668                 if (path->slots[0] == i)
1669                         push_space += data_size + sizeof(*item);
1670
1671                 this_item_size = btrfs_item_size(left, item);
1672                 if (this_item_size + sizeof(*item) + push_space > free_space)
1673                         break;
1674                 push_items++;
1675                 push_space += this_item_size + sizeof(*item);
1676                 if (i == 0)
1677                         break;
1678                 i--;
1679         }
1680
1681         if (push_items == 0) {
1682                 free_extent_buffer(right);
1683                 return 1;
1684         }
1685
1686         if (!empty && push_items == left_nritems)
1687                 WARN_ON(1);
1688
1689         /* push left to right */
1690         right_nritems = btrfs_header_nritems(right);
1691
1692         push_space = btrfs_item_end_nr(left, left_nritems - push_items);
1693         push_space -= leaf_data_end(root, left);
1694
1695         /* make room in the right data area */
1696         data_end = leaf_data_end(root, right);
1697         memmove_extent_buffer(right,
1698                               btrfs_leaf_data(right) + data_end - push_space,
1699                               btrfs_leaf_data(right) + data_end,
1700                               BTRFS_LEAF_DATA_SIZE(root) - data_end);
1701
1702         /* copy from the left data area */
1703         copy_extent_buffer(right, left, btrfs_leaf_data(right) +
1704                      BTRFS_LEAF_DATA_SIZE(root) - push_space,
1705                      btrfs_leaf_data(left) + leaf_data_end(root, left),
1706                      push_space);
1707
1708         memmove_extent_buffer(right, btrfs_item_nr_offset(push_items),
1709                               btrfs_item_nr_offset(0),
1710                               right_nritems * sizeof(struct btrfs_item));
1711
1712         /* copy the items from left to right */
1713         copy_extent_buffer(right, left, btrfs_item_nr_offset(0),
1714                    btrfs_item_nr_offset(left_nritems - push_items),
1715                    push_items * sizeof(struct btrfs_item));
1716
1717         /* update the item pointers */
1718         right_nritems += push_items;
1719         btrfs_set_header_nritems(right, right_nritems);
1720         push_space = BTRFS_LEAF_DATA_SIZE(root);
1721         for (i = 0; i < right_nritems; i++) {
1722                 item = btrfs_item_nr(right, i);
1723                 push_space -= btrfs_item_size(right, item);
1724                 btrfs_set_item_offset(right, item, push_space);
1725         }
1726
1727         left_nritems -= push_items;
1728         btrfs_set_header_nritems(left, left_nritems);
1729
1730         if (left_nritems)
1731                 btrfs_mark_buffer_dirty(left);
1732         btrfs_mark_buffer_dirty(right);
1733
1734         btrfs_item_key(right, &disk_key, 0);
1735         btrfs_set_node_key(upper, &disk_key, slot + 1);
1736         btrfs_mark_buffer_dirty(upper);
1737
1738         ret = btrfs_update_ref(trans, root, left, right, 0, push_items);
1739         BUG_ON(ret);
1740
1741         /* then fixup the leaf pointer in the path */
1742         if (path->slots[0] >= left_nritems) {
1743                 path->slots[0] -= left_nritems;
1744                 free_extent_buffer(path->nodes[0]);
1745                 path->nodes[0] = right;
1746                 path->slots[1] += 1;
1747         } else {
1748                 free_extent_buffer(right);
1749         }
1750         return 0;
1751 }
1752 /*
1753  * push some data in the path leaf to the left, trying to free up at
1754  * least data_size bytes.  returns zero if the push worked, nonzero otherwise
1755  */
1756 static int push_leaf_left(struct btrfs_trans_handle *trans, struct btrfs_root
1757                           *root, struct btrfs_path *path, int data_size,
1758                           int empty)
1759 {
1760         struct btrfs_disk_key disk_key;
1761         struct extent_buffer *right = path->nodes[0];
1762         struct extent_buffer *left;
1763         int slot;
1764         int i;
1765         int free_space;
1766         int push_space = 0;
1767         int push_items = 0;
1768         struct btrfs_item *item;
1769         u32 old_left_nritems;
1770         u32 right_nritems;
1771         u32 nr;
1772         int ret = 0;
1773         int wret;
1774         u32 this_item_size;
1775         u32 old_left_item_size;
1776
1777         slot = path->slots[1];
1778         if (slot == 0)
1779                 return 1;
1780         if (!path->nodes[1])
1781                 return 1;
1782
1783         right_nritems = btrfs_header_nritems(right);
1784         if (right_nritems == 0) {
1785                 return 1;
1786         }
1787
1788         left = read_node_slot(root, path->nodes[1], slot - 1);
1789         free_space = btrfs_leaf_free_space(root, left);
1790         if (free_space < data_size + sizeof(struct btrfs_item)) {
1791                 free_extent_buffer(left);
1792                 return 1;
1793         }
1794
1795         /* cow and double check */
1796         ret = btrfs_cow_block(trans, root, left,
1797                               path->nodes[1], slot - 1, &left);
1798         if (ret) {
1799                 /* we hit -ENOSPC, but it isn't fatal here */
1800                 free_extent_buffer(left);
1801                 return 1;
1802         }
1803
1804         free_space = btrfs_leaf_free_space(root, left);
1805         if (free_space < data_size + sizeof(struct btrfs_item)) {
1806                 free_extent_buffer(left);
1807                 return 1;
1808         }
1809
1810         if (empty)
1811                 nr = right_nritems;
1812         else
1813                 nr = right_nritems - 1;
1814
1815         for (i = 0; i < nr; i++) {
1816                 item = btrfs_item_nr(right, i);
1817
1818                 if (path->slots[0] == i)
1819                         push_space += data_size + sizeof(*item);
1820
1821                 this_item_size = btrfs_item_size(right, item);
1822                 if (this_item_size + sizeof(*item) + push_space > free_space)
1823                         break;
1824
1825                 push_items++;
1826                 push_space += this_item_size + sizeof(*item);
1827         }
1828
1829         if (push_items == 0) {
1830                 free_extent_buffer(left);
1831                 return 1;
1832         }
1833         if (!empty && push_items == btrfs_header_nritems(right))
1834                 WARN_ON(1);
1835
1836         /* push data from right to left */
1837         copy_extent_buffer(left, right,
1838                            btrfs_item_nr_offset(btrfs_header_nritems(left)),
1839                            btrfs_item_nr_offset(0),
1840                            push_items * sizeof(struct btrfs_item));
1841
1842         push_space = BTRFS_LEAF_DATA_SIZE(root) -
1843                      btrfs_item_offset_nr(right, push_items -1);
1844
1845         copy_extent_buffer(left, right, btrfs_leaf_data(left) +
1846                      leaf_data_end(root, left) - push_space,
1847                      btrfs_leaf_data(right) +
1848                      btrfs_item_offset_nr(right, push_items - 1),
1849                      push_space);
1850         old_left_nritems = btrfs_header_nritems(left);
1851         BUG_ON(old_left_nritems < 0);
1852
1853         old_left_item_size = btrfs_item_offset_nr(left, old_left_nritems - 1);
1854         for (i = old_left_nritems; i < old_left_nritems + push_items; i++) {
1855                 u32 ioff;
1856
1857                 item = btrfs_item_nr(left, i);
1858                 ioff = btrfs_item_offset(left, item);
1859                 btrfs_set_item_offset(left, item,
1860                       ioff - (BTRFS_LEAF_DATA_SIZE(root) - old_left_item_size));
1861         }
1862         btrfs_set_header_nritems(left, old_left_nritems + push_items);
1863
1864         /* fixup right node */
1865         if (push_items > right_nritems) {
1866                 printk("push items %d nr %u\n", push_items, right_nritems);
1867                 WARN_ON(1);
1868         }
1869
1870         if (push_items < right_nritems) {
1871                 push_space = btrfs_item_offset_nr(right, push_items - 1) -
1872                                                   leaf_data_end(root, right);
1873                 memmove_extent_buffer(right, btrfs_leaf_data(right) +
1874                                       BTRFS_LEAF_DATA_SIZE(root) - push_space,
1875                                       btrfs_leaf_data(right) +
1876                                       leaf_data_end(root, right), push_space);
1877
1878                 memmove_extent_buffer(right, btrfs_item_nr_offset(0),
1879                               btrfs_item_nr_offset(push_items),
1880                              (btrfs_header_nritems(right) - push_items) *
1881                              sizeof(struct btrfs_item));
1882         }
1883         right_nritems -= push_items;
1884         btrfs_set_header_nritems(right, right_nritems);
1885         push_space = BTRFS_LEAF_DATA_SIZE(root);
1886         for (i = 0; i < right_nritems; i++) {
1887                 item = btrfs_item_nr(right, i);
1888                 push_space = push_space - btrfs_item_size(right, item);
1889                 btrfs_set_item_offset(right, item, push_space);
1890         }
1891
1892         btrfs_mark_buffer_dirty(left);
1893         if (right_nritems)
1894                 btrfs_mark_buffer_dirty(right);
1895
1896         btrfs_item_key(right, &disk_key, 0);
1897         wret = fixup_low_keys(trans, root, path, &disk_key, 1);
1898         if (wret)
1899                 ret = wret;
1900
1901         ret = btrfs_update_ref(trans, root, right, left,
1902                                old_left_nritems, push_items);
1903         BUG_ON(ret);
1904
1905         /* then fixup the leaf pointer in the path */
1906         if (path->slots[0] < push_items) {
1907                 path->slots[0] += old_left_nritems;
1908                 free_extent_buffer(path->nodes[0]);
1909                 path->nodes[0] = left;
1910                 path->slots[1] -= 1;
1911         } else {
1912                 free_extent_buffer(left);
1913                 path->slots[0] -= push_items;
1914         }
1915         BUG_ON(path->slots[0] < 0);
1916         return ret;
1917 }
1918
1919 /*
1920  * split the path's leaf in two, making sure there is at least data_size
1921  * available for the resulting leaf level of the path.
1922  *
1923  * returns 0 if all went well and < 0 on failure.
1924  */
1925 static int split_leaf(struct btrfs_trans_handle *trans, struct btrfs_root
1926                       *root, struct btrfs_key *ins_key,
1927                       struct btrfs_path *path, int data_size, int extend)
1928 {
1929         struct extent_buffer *l;
1930         u32 nritems;
1931         int mid;
1932         int slot;
1933         struct extent_buffer *right;
1934         int space_needed = data_size + sizeof(struct btrfs_item);
1935         int data_copy_size;
1936         int rt_data_off;
1937         int i;
1938         int ret = 0;
1939         int wret;
1940         int double_split;
1941         int num_doubles = 0;
1942         struct btrfs_disk_key disk_key;
1943
1944         if (extend)
1945                 space_needed = data_size;
1946
1947         /* first try to make some room by pushing left and right */
1948         if (ins_key->type != BTRFS_DIR_ITEM_KEY) {
1949                 wret = push_leaf_right(trans, root, path, data_size, 0);
1950                 if (wret < 0) {
1951                         return wret;
1952                 }
1953                 if (wret) {
1954                         wret = push_leaf_left(trans, root, path, data_size, 0);
1955                         if (wret < 0)
1956                                 return wret;
1957                 }
1958                 l = path->nodes[0];
1959
1960                 /* did the pushes work? */
1961                 if (btrfs_leaf_free_space(root, l) >= space_needed)
1962                         return 0;
1963         }
1964
1965         if (!path->nodes[1]) {
1966                 ret = insert_new_root(trans, root, path, 1);
1967                 if (ret)
1968                         return ret;
1969         }
1970 again:
1971         double_split = 0;
1972         l = path->nodes[0];
1973         slot = path->slots[0];
1974         nritems = btrfs_header_nritems(l);
1975         mid = (nritems + 1)/ 2;
1976
1977         right = btrfs_alloc_free_block(trans, root, root->leafsize,
1978                                         path->nodes[1]->start,
1979                                         root->root_key.objectid,
1980                                         trans->transid, 0, l->start, 0);
1981         if (IS_ERR(right)) {
1982                 BUG_ON(1);
1983                 return PTR_ERR(right);
1984         }
1985
1986         memset_extent_buffer(right, 0, 0, sizeof(struct btrfs_header));
1987         btrfs_set_header_bytenr(right, right->start);
1988         btrfs_set_header_generation(right, trans->transid);
1989         btrfs_set_header_owner(right, root->root_key.objectid);
1990         btrfs_set_header_level(right, 0);
1991         write_extent_buffer(right, root->fs_info->fsid,
1992                             (unsigned long)btrfs_header_fsid(right),
1993                             BTRFS_FSID_SIZE);
1994
1995         write_extent_buffer(right, root->fs_info->chunk_tree_uuid,
1996                             (unsigned long)btrfs_header_chunk_tree_uuid(right),
1997                             BTRFS_UUID_SIZE);
1998         if (mid <= slot) {
1999                 if (nritems == 1 ||
2000                     leaf_space_used(l, mid, nritems - mid) + space_needed >
2001                         BTRFS_LEAF_DATA_SIZE(root)) {
2002                         if (slot >= nritems) {
2003                                 btrfs_cpu_key_to_disk(&disk_key, ins_key);
2004                                 btrfs_set_header_nritems(right, 0);
2005                                 wret = insert_ptr(trans, root, path,
2006                                                   &disk_key, right->start,
2007                                                   path->slots[1] + 1, 1);
2008                                 if (wret)
2009                                         ret = wret;
2010                                 free_extent_buffer(path->nodes[0]);
2011                                 path->nodes[0] = right;
2012                                 path->slots[0] = 0;
2013                                 path->slots[1] += 1;
2014                                 return ret;
2015                         }
2016                         mid = slot;
2017                         if (mid != nritems &&
2018                             leaf_space_used(l, mid, nritems - mid) +
2019                             space_needed > BTRFS_LEAF_DATA_SIZE(root)) {
2020                                 double_split = 1;
2021                         }
2022                 }
2023         } else {
2024                 if (leaf_space_used(l, 0, mid + 1) + space_needed >
2025                         BTRFS_LEAF_DATA_SIZE(root)) {
2026                         if (!extend && slot == 0) {
2027                                 btrfs_cpu_key_to_disk(&disk_key, ins_key);
2028                                 btrfs_set_header_nritems(right, 0);
2029                                 wret = insert_ptr(trans, root, path,
2030                                                   &disk_key,
2031                                                   right->start,
2032                                                   path->slots[1], 1);
2033                                 if (wret)
2034                                         ret = wret;
2035                                 free_extent_buffer(path->nodes[0]);
2036                                 path->nodes[0] = right;
2037                                 path->slots[0] = 0;
2038                                 if (path->slots[1] == 0) {
2039                                         wret = fixup_low_keys(trans, root,
2040                                                    path, &disk_key, 1);
2041                                         if (wret)
2042                                                 ret = wret;
2043                                 }
2044                                 return ret;
2045                         } else if (extend && slot == 0) {
2046                                 mid = 1;
2047                         } else {
2048                                 mid = slot;
2049                                 if (mid != nritems &&
2050                                     leaf_space_used(l, mid, nritems - mid) +
2051                                     space_needed > BTRFS_LEAF_DATA_SIZE(root)) {
2052                                         double_split = 1;
2053                                 }
2054                         }
2055                 }
2056         }
2057         nritems = nritems - mid;
2058         btrfs_set_header_nritems(right, nritems);
2059         data_copy_size = btrfs_item_end_nr(l, mid) - leaf_data_end(root, l);
2060
2061         copy_extent_buffer(right, l, btrfs_item_nr_offset(0),
2062                            btrfs_item_nr_offset(mid),
2063                            nritems * sizeof(struct btrfs_item));
2064
2065         copy_extent_buffer(right, l,
2066                      btrfs_leaf_data(right) + BTRFS_LEAF_DATA_SIZE(root) -
2067                      data_copy_size, btrfs_leaf_data(l) +
2068                      leaf_data_end(root, l), data_copy_size);
2069
2070         rt_data_off = BTRFS_LEAF_DATA_SIZE(root) -
2071                       btrfs_item_end_nr(l, mid);
2072
2073         for (i = 0; i < nritems; i++) {
2074                 struct btrfs_item *item = btrfs_item_nr(right, i);
2075                 u32 ioff = btrfs_item_offset(right, item);
2076                 btrfs_set_item_offset(right, item, ioff + rt_data_off);
2077         }
2078
2079         btrfs_set_header_nritems(l, mid);
2080         ret = 0;
2081         btrfs_item_key(right, &disk_key, 0);
2082         wret = insert_ptr(trans, root, path, &disk_key, right->start,
2083                           path->slots[1] + 1, 1);
2084         if (wret)
2085                 ret = wret;
2086
2087         btrfs_mark_buffer_dirty(right);
2088         btrfs_mark_buffer_dirty(l);
2089         BUG_ON(path->slots[0] != slot);
2090
2091         ret = btrfs_update_ref(trans, root, l, right, 0, nritems);
2092         BUG_ON(ret);
2093
2094         if (mid <= slot) {
2095                 free_extent_buffer(path->nodes[0]);
2096                 path->nodes[0] = right;
2097                 path->slots[0] -= mid;
2098                 path->slots[1] += 1;
2099         } else
2100                 free_extent_buffer(right);
2101
2102         BUG_ON(path->slots[0] < 0);
2103
2104         if (double_split) {
2105                 BUG_ON(num_doubles != 0);
2106                 num_doubles++;
2107                 goto again;
2108         }
2109         return ret;
2110 }
2111
2112 int btrfs_truncate_item(struct btrfs_trans_handle *trans,
2113                         struct btrfs_root *root,
2114                         struct btrfs_path *path,
2115                         u32 new_size, int from_end)
2116 {
2117         int ret = 0;
2118         int slot;
2119         int slot_orig;
2120         struct extent_buffer *leaf;
2121         struct btrfs_item *item;
2122         u32 nritems;
2123         unsigned int data_end;
2124         unsigned int old_data_start;
2125         unsigned int old_size;
2126         unsigned int size_diff;
2127         int i;
2128
2129         slot_orig = path->slots[0];
2130         leaf = path->nodes[0];
2131         slot = path->slots[0];
2132
2133         old_size = btrfs_item_size_nr(leaf, slot);
2134         if (old_size == new_size)
2135                 return 0;
2136
2137         nritems = btrfs_header_nritems(leaf);
2138         data_end = leaf_data_end(root, leaf);
2139
2140         old_data_start = btrfs_item_offset_nr(leaf, slot);
2141
2142         size_diff = old_size - new_size;
2143
2144         BUG_ON(slot < 0);
2145         BUG_ON(slot >= nritems);
2146
2147         /*
2148          * item0..itemN ... dataN.offset..dataN.size .. data0.size
2149          */
2150         /* first correct the data pointers */
2151         for (i = slot; i < nritems; i++) {
2152                 u32 ioff;
2153                 item = btrfs_item_nr(leaf, i);
2154                 ioff = btrfs_item_offset(leaf, item);
2155                 btrfs_set_item_offset(leaf, item, ioff + size_diff);
2156         }
2157
2158         /* shift the data */
2159         if (from_end) {
2160                 memmove_extent_buffer(leaf, btrfs_leaf_data(leaf) +
2161                               data_end + size_diff, btrfs_leaf_data(leaf) +
2162                               data_end, old_data_start + new_size - data_end);
2163         } else {
2164                 struct btrfs_disk_key disk_key;
2165                 u64 offset;
2166
2167                 btrfs_item_key(leaf, &disk_key, slot);
2168
2169                 if (btrfs_disk_key_type(&disk_key) == BTRFS_EXTENT_DATA_KEY) {
2170                         unsigned long ptr;
2171                         struct btrfs_file_extent_item *fi;
2172
2173                         fi = btrfs_item_ptr(leaf, slot,
2174                                             struct btrfs_file_extent_item);
2175                         fi = (struct btrfs_file_extent_item *)(
2176                              (unsigned long)fi - size_diff);
2177
2178                         if (btrfs_file_extent_type(leaf, fi) ==
2179                             BTRFS_FILE_EXTENT_INLINE) {
2180                                 ptr = btrfs_item_ptr_offset(leaf, slot);
2181                                 memmove_extent_buffer(leaf, ptr,
2182                                         (unsigned long)fi,
2183                                         offsetof(struct btrfs_file_extent_item,
2184                                                  disk_bytenr));
2185                         }
2186                 }
2187
2188                 memmove_extent_buffer(leaf, btrfs_leaf_data(leaf) +
2189                               data_end + size_diff, btrfs_leaf_data(leaf) +
2190                               data_end, old_data_start - data_end);
2191
2192                 offset = btrfs_disk_key_offset(&disk_key);
2193                 btrfs_set_disk_key_offset(&disk_key, offset + size_diff);
2194                 btrfs_set_item_key(leaf, &disk_key, slot);
2195                 if (slot == 0)
2196                         fixup_low_keys(trans, root, path, &disk_key, 1);
2197         }
2198
2199         item = btrfs_item_nr(leaf, slot);
2200         btrfs_set_item_size(leaf, item, new_size);
2201         btrfs_mark_buffer_dirty(leaf);
2202
2203         ret = 0;
2204         if (btrfs_leaf_free_space(root, leaf) < 0) {
2205                 btrfs_print_leaf(root, leaf);
2206                 BUG();
2207         }
2208         return ret;
2209 }
2210
2211 int btrfs_extend_item(struct btrfs_trans_handle *trans,
2212                       struct btrfs_root *root, struct btrfs_path *path,
2213                       u32 data_size)
2214 {
2215         int ret = 0;
2216         int slot;
2217         int slot_orig;
2218         struct extent_buffer *leaf;
2219         struct btrfs_item *item;
2220         u32 nritems;
2221         unsigned int data_end;
2222         unsigned int old_data;
2223         unsigned int old_size;
2224         int i;
2225
2226         slot_orig = path->slots[0];
2227         leaf = path->nodes[0];
2228
2229         nritems = btrfs_header_nritems(leaf);
2230         data_end = leaf_data_end(root, leaf);
2231
2232         if (btrfs_leaf_free_space(root, leaf) < data_size) {
2233                 btrfs_print_leaf(root, leaf);
2234                 BUG();
2235         }
2236         slot = path->slots[0];
2237         old_data = btrfs_item_end_nr(leaf, slot);
2238
2239         BUG_ON(slot < 0);
2240         if (slot >= nritems) {
2241                 btrfs_print_leaf(root, leaf);
2242                 printk("slot %d too large, nritems %d\n", slot, nritems);
2243                 BUG_ON(1);
2244         }
2245
2246         /*
2247          * item0..itemN ... dataN.offset..dataN.size .. data0.size
2248          */
2249         /* first correct the data pointers */
2250         for (i = slot; i < nritems; i++) {
2251                 u32 ioff;
2252                 item = btrfs_item_nr(leaf, i);
2253                 ioff = btrfs_item_offset(leaf, item);
2254                 btrfs_set_item_offset(leaf, item, ioff - data_size);
2255         }
2256
2257         /* shift the data */
2258         memmove_extent_buffer(leaf, btrfs_leaf_data(leaf) +
2259                       data_end - data_size, btrfs_leaf_data(leaf) +
2260                       data_end, old_data - data_end);
2261
2262         data_end = old_data;
2263         old_size = btrfs_item_size_nr(leaf, slot);
2264         item = btrfs_item_nr(leaf, slot);
2265         btrfs_set_item_size(leaf, item, old_size + data_size);
2266         btrfs_mark_buffer_dirty(leaf);
2267
2268         ret = 0;
2269         if (btrfs_leaf_free_space(root, leaf) < 0) {
2270                 btrfs_print_leaf(root, leaf);
2271                 BUG();
2272         }
2273         return ret;
2274 }
2275
2276 /*
2277  * Given a key and some data, insert an item into the tree.
2278  * This does all the path init required, making room in the tree if needed.
2279  */
2280 int btrfs_insert_empty_items(struct btrfs_trans_handle *trans,
2281                             struct btrfs_root *root,
2282                             struct btrfs_path *path,
2283                             struct btrfs_key *cpu_key, u32 *data_size,
2284                             int nr)
2285 {
2286         struct extent_buffer *leaf;
2287         struct btrfs_item *item;
2288         int ret = 0;
2289         int slot;
2290         int slot_orig;
2291         int i;
2292         u32 nritems;
2293         u32 total_size = 0;
2294         u32 total_data = 0;
2295         unsigned int data_end;
2296         struct btrfs_disk_key disk_key;
2297
2298         for (i = 0; i < nr; i++) {
2299                 total_data += data_size[i];
2300         }
2301
2302         /* create a root if there isn't one */
2303         if (!root->node)
2304                 BUG();
2305
2306         total_size = total_data + (nr - 1) * sizeof(struct btrfs_item);
2307         ret = btrfs_search_slot(trans, root, cpu_key, path, total_size, 1);
2308         if (ret == 0) {
2309                 return -EEXIST;
2310         }
2311         if (ret < 0)
2312                 goto out;
2313
2314         slot_orig = path->slots[0];
2315         leaf = path->nodes[0];
2316
2317         nritems = btrfs_header_nritems(leaf);
2318         data_end = leaf_data_end(root, leaf);
2319
2320         if (btrfs_leaf_free_space(root, leaf) <
2321             sizeof(struct btrfs_item) + total_size) {
2322                 btrfs_print_leaf(root, leaf);
2323                 printk("not enough freespace need %u have %d\n",
2324                        total_size, btrfs_leaf_free_space(root, leaf));
2325                 BUG();
2326         }
2327
2328         slot = path->slots[0];
2329         BUG_ON(slot < 0);
2330
2331         if (slot != nritems) {
2332                 int i;
2333                 unsigned int old_data = btrfs_item_end_nr(leaf, slot);
2334
2335                 if (old_data < data_end) {
2336                         btrfs_print_leaf(root, leaf);
2337                         printk("slot %d old_data %d data_end %d\n",
2338                                slot, old_data, data_end);
2339                         BUG_ON(1);
2340                 }
2341                 /*
2342                  * item0..itemN ... dataN.offset..dataN.size .. data0.size
2343                  */
2344                 /* first correct the data pointers */
2345                 for (i = slot; i < nritems; i++) {
2346                         u32 ioff;
2347
2348                         item = btrfs_item_nr(leaf, i);
2349                         ioff = btrfs_item_offset(leaf, item);
2350                         btrfs_set_item_offset(leaf, item, ioff - total_data);
2351                 }
2352
2353                 /* shift the items */
2354                 memmove_extent_buffer(leaf, btrfs_item_nr_offset(slot + nr),
2355                               btrfs_item_nr_offset(slot),
2356                               (nritems - slot) * sizeof(struct btrfs_item));
2357
2358                 /* shift the data */
2359                 memmove_extent_buffer(leaf, btrfs_leaf_data(leaf) +
2360                               data_end - total_data, btrfs_leaf_data(leaf) +
2361                               data_end, old_data - data_end);
2362                 data_end = old_data;
2363         }
2364
2365         /* setup the item for the new data */
2366         for (i = 0; i < nr; i++) {
2367                 btrfs_cpu_key_to_disk(&disk_key, cpu_key + i);
2368                 btrfs_set_item_key(leaf, &disk_key, slot + i);
2369                 item = btrfs_item_nr(leaf, slot + i);
2370                 btrfs_set_item_offset(leaf, item, data_end - data_size[i]);
2371                 data_end -= data_size[i];
2372                 btrfs_set_item_size(leaf, item, data_size[i]);
2373         }
2374         btrfs_set_header_nritems(leaf, nritems + nr);
2375         btrfs_mark_buffer_dirty(leaf);
2376
2377         ret = 0;
2378         if (slot == 0) {
2379                 btrfs_cpu_key_to_disk(&disk_key, cpu_key);
2380                 ret = fixup_low_keys(trans, root, path, &disk_key, 1);
2381         }
2382
2383         if (btrfs_leaf_free_space(root, leaf) < 0) {
2384                 btrfs_print_leaf(root, leaf);
2385                 BUG();
2386         }
2387
2388 out:
2389         return ret;
2390 }
2391
2392 /*
2393  * Given a key and some data, insert an item into the tree.
2394  * This does all the path init required, making room in the tree if needed.
2395  */
2396 int btrfs_insert_item(struct btrfs_trans_handle *trans, struct btrfs_root
2397                       *root, struct btrfs_key *cpu_key, void *data, u32
2398                       data_size)
2399 {
2400         int ret = 0;
2401         struct btrfs_path *path;
2402         struct extent_buffer *leaf;
2403         unsigned long ptr;
2404
2405         path = btrfs_alloc_path();
2406         BUG_ON(!path);
2407         ret = btrfs_insert_empty_item(trans, root, path, cpu_key, data_size);
2408         if (!ret) {
2409                 leaf = path->nodes[0];
2410                 ptr = btrfs_item_ptr_offset(leaf, path->slots[0]);
2411                 write_extent_buffer(leaf, data, ptr, data_size);
2412                 btrfs_mark_buffer_dirty(leaf);
2413         }
2414         btrfs_free_path(path);
2415         return ret;
2416 }
2417
2418 /*
2419  * delete the pointer from a given node.
2420  *
2421  * If the delete empties a node, the node is removed from the tree,
2422  * continuing all the way the root if required.  The root is converted into
2423  * a leaf if all the nodes are emptied.
2424  */
2425 static int del_ptr(struct btrfs_trans_handle *trans, struct btrfs_root *root,
2426                    struct btrfs_path *path, int level, int slot)
2427 {
2428         struct extent_buffer *parent = path->nodes[level];
2429         u32 nritems;
2430         int ret = 0;
2431         int wret;
2432
2433         nritems = btrfs_header_nritems(parent);
2434         if (slot != nritems -1) {
2435                 memmove_extent_buffer(parent,
2436                               btrfs_node_key_ptr_offset(slot),
2437                               btrfs_node_key_ptr_offset(slot + 1),
2438                               sizeof(struct btrfs_key_ptr) *
2439                               (nritems - slot - 1));
2440         }
2441         nritems--;
2442         btrfs_set_header_nritems(parent, nritems);
2443         if (nritems == 0 && parent == root->node) {
2444                 BUG_ON(btrfs_header_level(root->node) != 1);
2445                 /* just turn the root into a leaf and break */
2446                 btrfs_set_header_level(root->node, 0);
2447         } else if (slot == 0) {
2448                 struct btrfs_disk_key disk_key;
2449
2450                 btrfs_node_key(parent, &disk_key, 0);
2451                 wret = fixup_low_keys(trans, root, path, &disk_key, level + 1);
2452                 if (wret)
2453                         ret = wret;
2454         }
2455         btrfs_mark_buffer_dirty(parent);
2456         return ret;
2457 }
2458
2459 /*
2460  * delete the item at the leaf level in path.  If that empties
2461  * the leaf, remove it from the tree
2462  */
2463 int btrfs_del_items(struct btrfs_trans_handle *trans, struct btrfs_root *root,
2464                     struct btrfs_path *path, int slot, int nr)
2465 {
2466         struct extent_buffer *leaf;
2467         struct btrfs_item *item;
2468         int last_off;
2469         int dsize = 0;
2470         int ret = 0;
2471         int wret;
2472         int i;
2473         u32 nritems;
2474
2475         leaf = path->nodes[0];
2476         last_off = btrfs_item_offset_nr(leaf, slot + nr - 1);
2477
2478         for (i = 0; i < nr; i++)
2479                 dsize += btrfs_item_size_nr(leaf, slot + i);
2480
2481         nritems = btrfs_header_nritems(leaf);
2482
2483         if (slot + nr != nritems) {
2484                 int i;
2485                 int data_end = leaf_data_end(root, leaf);
2486
2487                 memmove_extent_buffer(leaf, btrfs_leaf_data(leaf) +
2488                               data_end + dsize,
2489                               btrfs_leaf_data(leaf) + data_end,
2490                               last_off - data_end);
2491
2492                 for (i = slot + nr; i < nritems; i++) {
2493                         u32 ioff;
2494
2495                         item = btrfs_item_nr(leaf, i);
2496                         ioff = btrfs_item_offset(leaf, item);
2497                         btrfs_set_item_offset(leaf, item, ioff + dsize);
2498                 }
2499
2500                 memmove_extent_buffer(leaf, btrfs_item_nr_offset(slot),
2501                               btrfs_item_nr_offset(slot + nr),
2502                               sizeof(struct btrfs_item) *
2503                               (nritems - slot - nr));
2504         }
2505         btrfs_set_header_nritems(leaf, nritems - nr);
2506         nritems -= nr;
2507
2508         /* delete the leaf if we've emptied it */
2509         if (nritems == 0) {
2510                 if (leaf == root->node) {
2511                         btrfs_set_header_level(leaf, 0);
2512                 } else {
2513                         u64 root_gen = btrfs_header_generation(path->nodes[1]);
2514                         clean_tree_block(trans, root, leaf);
2515                         wait_on_tree_block_writeback(root, leaf);
2516                         wret = del_ptr(trans, root, path, 1, path->slots[1]);
2517                         if (wret)
2518                                 ret = wret;
2519                         wret = btrfs_free_extent(trans, root,
2520                                          leaf->start, leaf->len,
2521                                          path->nodes[1]->start,
2522                                          btrfs_header_owner(path->nodes[1]),
2523                                          root_gen, 0, 1);
2524                         if (wret)
2525                                 ret = wret;
2526                 }
2527         } else {
2528                 int used = leaf_space_used(leaf, 0, nritems);
2529                 if (slot == 0) {
2530                         struct btrfs_disk_key disk_key;
2531
2532                         btrfs_item_key(leaf, &disk_key, 0);
2533                         wret = fixup_low_keys(trans, root, path,
2534                                               &disk_key, 1);
2535                         if (wret)
2536                                 ret = wret;
2537                 }
2538
2539                 /* delete the leaf if it is mostly empty */
2540                 if (used < BTRFS_LEAF_DATA_SIZE(root) / 4) {
2541                         /* push_leaf_left fixes the path.
2542                          * make sure the path still points to our leaf
2543                          * for possible call to del_ptr below
2544                          */
2545                         slot = path->slots[1];
2546                         extent_buffer_get(leaf);
2547
2548                         wret = push_leaf_left(trans, root, path, 1, 1);
2549                         if (wret < 0 && wret != -ENOSPC)
2550                                 ret = wret;
2551
2552                         if (path->nodes[0] == leaf &&
2553                             btrfs_header_nritems(leaf)) {
2554                                 wret = push_leaf_right(trans, root, path, 1, 1);
2555                                 if (wret < 0 && wret != -ENOSPC)
2556                                         ret = wret;
2557                         }
2558
2559                         if (btrfs_header_nritems(leaf) == 0) {
2560                                 u64 root_gen;
2561                                 u64 bytenr = leaf->start;
2562                                 u32 blocksize = leaf->len;
2563
2564                                 root_gen = btrfs_header_generation(
2565                                                            path->nodes[1]);
2566
2567                                 clean_tree_block(trans, root, leaf);
2568                                 wait_on_tree_block_writeback(root, leaf);
2569
2570                                 wret = del_ptr(trans, root, path, 1, slot);
2571                                 if (wret)
2572                                         ret = wret;
2573
2574                                 free_extent_buffer(leaf);
2575                                 wret = btrfs_free_extent(trans, root, bytenr,
2576                                              blocksize, path->nodes[1]->start,
2577                                              btrfs_header_owner(path->nodes[1]),
2578                                              root_gen, 0, 1);
2579                                 if (wret)
2580                                         ret = wret;
2581                         } else {
2582                                 btrfs_mark_buffer_dirty(leaf);
2583                                 free_extent_buffer(leaf);
2584                         }
2585                 } else {
2586                         btrfs_mark_buffer_dirty(leaf);
2587                 }
2588         }
2589         return ret;
2590 }
2591
2592 /*
2593  * walk up the tree as far as required to find the previous leaf.
2594  * returns 0 if it found something or 1 if there are no lesser leaves.
2595  * returns < 0 on io errors.
2596  */
2597 int btrfs_prev_leaf(struct btrfs_root *root, struct btrfs_path *path)
2598 {
2599         int slot;
2600         int level = 1;
2601         struct extent_buffer *c;
2602         struct extent_buffer *next = NULL;
2603
2604         while(level < BTRFS_MAX_LEVEL) {
2605                 if (!path->nodes[level])
2606                         return 1;
2607
2608                 slot = path->slots[level];
2609                 c = path->nodes[level];
2610                 if (slot == 0) {
2611                         level++;
2612                         if (level == BTRFS_MAX_LEVEL)
2613                                 return 1;
2614                         continue;
2615                 }
2616                 slot--;
2617
2618                 if (next)
2619                         free_extent_buffer(next);
2620
2621                 next = read_node_slot(root, c, slot);
2622                 break;
2623         }
2624         path->slots[level] = slot;
2625         while(1) {
2626                 level--;
2627                 c = path->nodes[level];
2628                 free_extent_buffer(c);
2629                 slot = btrfs_header_nritems(next);
2630                 if (slot != 0)
2631                         slot--;
2632                 path->nodes[level] = next;
2633                 path->slots[level] = slot;
2634                 if (!level)
2635                         break;
2636                 next = read_node_slot(root, next, slot);
2637         }
2638         return 0;
2639 }
2640
2641 /*
2642  * walk up the tree as far as required to find the next leaf.
2643  * returns 0 if it found something or 1 if there are no greater leaves.
2644  * returns < 0 on io errors.
2645  */
2646 int btrfs_next_leaf(struct btrfs_root *root, struct btrfs_path *path)
2647 {
2648         int slot;
2649         int level = 1;
2650         struct extent_buffer *c;
2651         struct extent_buffer *next = NULL;
2652
2653         while(level < BTRFS_MAX_LEVEL) {
2654                 if (!path->nodes[level])
2655                         return 1;
2656
2657                 slot = path->slots[level] + 1;
2658                 c = path->nodes[level];
2659                 if (slot >= btrfs_header_nritems(c)) {
2660                         level++;
2661                         if (level == BTRFS_MAX_LEVEL)
2662                                 return 1;
2663                         continue;
2664                 }
2665
2666                 if (next)
2667                         free_extent_buffer(next);
2668
2669                 if (path->reada)
2670                         reada_for_search(root, path, level, slot, 0);
2671
2672                 next = read_node_slot(root, c, slot);
2673                 break;
2674         }
2675         path->slots[level] = slot;
2676         while(1) {
2677                 level--;
2678                 c = path->nodes[level];
2679                 free_extent_buffer(c);
2680                 path->nodes[level] = next;
2681                 path->slots[level] = 0;
2682                 if (!level)
2683                         break;
2684                 if (path->reada)
2685                         reada_for_search(root, path, level, 0, 0);
2686                 next = read_node_slot(root, next, 0);
2687         }
2688         return 0;
2689 }
2690
2691 int btrfs_previous_item(struct btrfs_root *root,
2692                         struct btrfs_path *path, u64 min_objectid,
2693                         int type)
2694 {
2695         struct btrfs_key found_key;
2696         struct extent_buffer *leaf;
2697         int ret;
2698
2699         while(1) {
2700                 if (path->slots[0] == 0) {
2701                         ret = btrfs_prev_leaf(root, path);
2702                         if (ret != 0)
2703                                 return ret;
2704                 } else {
2705                         path->slots[0]--;
2706                 }
2707                 leaf = path->nodes[0];
2708                 btrfs_item_key_to_cpu(leaf, &found_key, path->slots[0]);
2709                 if (found_key.type == type)
2710                         return 0;
2711         }
2712         return 1;
2713 }
2714