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