?  search:
summary | log | graphiclog1 | graphiclog2 | commit | commitdiff | tree | refs | edit | fork
blame | history | raw | HEAD
x86: move defs around to allow paravirt.h to just include page_types.h
[linux-2.6/linux-2.6-openrd.git] / fs / btrfs / ctree.c
blob551177c0011ae90d3e2c0460340071ea97158b50
1 /*
2 * Copyright (C) 2007,2008 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
19 #include <linux/sched.h>
20 #include "ctree.h"
21 #include "disk-io.h"
22 #include "transaction.h"
23 #include "print-tree.h"
24 #include "locking.h"
25
26 static int split_node(struct btrfs_trans_handle *trans, struct btrfs_root
27 *root, struct btrfs_path *path, int level);
28 static int split_leaf(struct btrfs_trans_handle *trans, struct btrfs_root
29 *root, struct btrfs_key *ins_key,
30 struct btrfs_path *path, int data_size, int extend);
31 static int push_node_left(struct btrfs_trans_handle *trans,
32 struct btrfs_root *root, struct extent_buffer *dst,
33 struct extent_buffer *src, int empty);
34 static int balance_node_right(struct btrfs_trans_handle *trans,
35 struct btrfs_root *root,
36 struct extent_buffer *dst_buf,
37 struct extent_buffer *src_buf);
38 static int del_ptr(struct btrfs_trans_handle *trans, struct btrfs_root *root,
39 struct btrfs_path *path, int level, int slot);
40
41 inline void btrfs_init_path(struct btrfs_path *p)
42 {
43 memset(p, 0, sizeof(*p));
44 }
45
46 struct btrfs_path *btrfs_alloc_path(void)
47 {
48 struct btrfs_path *path;
49 path = kmem_cache_alloc(btrfs_path_cachep, GFP_NOFS);
50 if (path) {
51 btrfs_init_path(path);
52 path->reada = 1;
53 }
54 return path;
55 }
56
57 /*
58 * set all locked nodes in the path to blocking locks. This should
59 * be done before scheduling
60 */
61 noinline void btrfs_set_path_blocking(struct btrfs_path *p)
62 {
63 int i;
64 for (i = 0; i < BTRFS_MAX_LEVEL; i++) {
65 if (p->nodes[i] && p->locks[i])
66 btrfs_set_lock_blocking(p->nodes[i]);
67 }
68 }
69
70 /*
71 * reset all the locked nodes in the patch to spinning locks.
72 */
73 noinline void btrfs_clear_path_blocking(struct btrfs_path *p)
74 {
75 int i;
76 for (i = 0; i < BTRFS_MAX_LEVEL; i++) {
77 if (p->nodes[i] && p->locks[i])
78 btrfs_clear_lock_blocking(p->nodes[i]);
79 }
80 }
81
82 /* this also releases the path */
83 void btrfs_free_path(struct btrfs_path *p)
84 {
85 btrfs_release_path(NULL, p);
86 kmem_cache_free(btrfs_path_cachep, p);
87 }
88
89 /*
90 * path release drops references on the extent buffers in the path
91 * and it drops any locks held by this path
92 *
93 * It is safe to call this on paths that no locks or extent buffers held.
94 */
95 noinline void btrfs_release_path(struct btrfs_root *root, struct btrfs_path *p)
96 {
97 int i;
98
99 for (i = 0; i < BTRFS_MAX_LEVEL; i++) {
100 p->slots[i] = 0;
101 if (!p->nodes[i])
102 continue;
103 if (p->locks[i]) {
104 btrfs_tree_unlock(p->nodes[i]);
105 p->locks[i] = 0;
106 }
107 free_extent_buffer(p->nodes[i]);
108 p->nodes[i] = NULL;
109 }
110 }
111
112 /*
113 * safely gets a reference on the root node of a tree. A lock
114 * is not taken, so a concurrent writer may put a different node
115 * at the root of the tree. See btrfs_lock_root_node for the
116 * looping required.
117 *
118 * The extent buffer returned by this has a reference taken, so
119 * it won't disappear. It may stop being the root of the tree
120 * at any time because there are no locks held.
121 */
122 struct extent_buffer *btrfs_root_node(struct btrfs_root *root)
123 {
124 struct extent_buffer *eb;
125 spin_lock(&root->node_lock);
126 eb = root->node;
127 extent_buffer_get(eb);
128 spin_unlock(&root->node_lock);
129 return eb;
130 }
131
132 /* loop around taking references on and locking the root node of the
133 * tree until you end up with a lock on the root. A locked buffer
134 * is returned, with a reference held.
135 */
136 struct extent_buffer *btrfs_lock_root_node(struct btrfs_root *root)
137 {
138 struct extent_buffer *eb;
139
140 while (1) {
141 eb = btrfs_root_node(root);
142 btrfs_tree_lock(eb);
143
144 spin_lock(&root->node_lock);
145 if (eb == root->node) {
146 spin_unlock(&root->node_lock);
147 break;
148 }
149 spin_unlock(&root->node_lock);
150
151 btrfs_tree_unlock(eb);
152 free_extent_buffer(eb);
153 }
154 return eb;
155 }
156
157 /* cowonly root (everything not a reference counted cow subvolume), just get
158 * put onto a simple dirty list. transaction.c walks this to make sure they
159 * get properly updated on disk.
160 */
161 static void add_root_to_dirty_list(struct btrfs_root *root)
162 {
163 if (root->track_dirty && list_empty(&root->dirty_list)) {
164 list_add(&root->dirty_list,
165 &root->fs_info->dirty_cowonly_roots);
166 }
167 }
168
169 /*
170 * used by snapshot creation to make a copy of a root for a tree with
171 * a given objectid. The buffer with the new root node is returned in
172 * cow_ret, and this func returns zero on success or a negative error code.
173 */
174 int btrfs_copy_root(struct btrfs_trans_handle *trans,
175 struct btrfs_root *root,
176 struct extent_buffer *buf,
177 struct extent_buffer **cow_ret, u64 new_root_objectid)
178 {
179 struct extent_buffer *cow;
180 u32 nritems;
181 int ret = 0;
182 int level;
183 struct btrfs_root *new_root;
184
185 new_root = kmalloc(sizeof(*new_root), GFP_NOFS);
186 if (!new_root)
187 return -ENOMEM;
188
189 memcpy(new_root, root, sizeof(*new_root));
190 new_root->root_key.objectid = new_root_objectid;
191
192 WARN_ON(root->ref_cows && trans->transid !=
193 root->fs_info->running_transaction->transid);
194 WARN_ON(root->ref_cows && trans->transid != root->last_trans);
195
196 level = btrfs_header_level(buf);
197 nritems = btrfs_header_nritems(buf);
198
199 cow = btrfs_alloc_free_block(trans, new_root, buf->len, 0,
200 new_root_objectid, trans->transid,
201 level, buf->start, 0);
202 if (IS_ERR(cow)) {
203 kfree(new_root);
204 return PTR_ERR(cow);
205 }
206
207 copy_extent_buffer(cow, buf, 0, 0, cow->len);
208 btrfs_set_header_bytenr(cow, cow->start);
209 btrfs_set_header_generation(cow, trans->transid);
210 btrfs_set_header_owner(cow, new_root_objectid);
211 btrfs_clear_header_flag(cow, BTRFS_HEADER_FLAG_WRITTEN);
212
213 write_extent_buffer(cow, root->fs_info->fsid,
214 (unsigned long)btrfs_header_fsid(cow),
215 BTRFS_FSID_SIZE);
216
217 WARN_ON(btrfs_header_generation(buf) > trans->transid);
218 ret = btrfs_inc_ref(trans, new_root, buf, cow, NULL);
219 kfree(new_root);
220
221 if (ret)
222 return ret;
223
224 btrfs_mark_buffer_dirty(cow);
225 *cow_ret = cow;
226 return 0;
227 }
228
229 /*
230 * does the dirty work in cow of a single block. The parent block (if
231 * supplied) is updated to point to the new cow copy. The new buffer is marked
232 * dirty and returned locked. If you modify the block it needs to be marked
233 * dirty again.
234 *
235 * search_start -- an allocation hint for the new block
236 *
237 * empty_size -- a hint that you plan on doing more cow. This is the size in
238 * bytes the allocator should try to find free next to the block it returns.
239 * This is just a hint and may be ignored by the allocator.
240 *
241 * prealloc_dest -- if you have already reserved a destination for the cow,
242 * this uses that block instead of allocating a new one.
243 * btrfs_alloc_reserved_extent is used to finish the allocation.
244 */
245 static noinline int __btrfs_cow_block(struct btrfs_trans_handle *trans,
246 struct btrfs_root *root,
247 struct extent_buffer *buf,
248 struct extent_buffer *parent, int parent_slot,
249 struct extent_buffer **cow_ret,
250 u64 search_start, u64 empty_size,
251 u64 prealloc_dest)
252 {
253 u64 parent_start;
254 struct extent_buffer *cow;
255 u32 nritems;
256 int ret = 0;
257 int level;
258 int unlock_orig = 0;
259
260 if (*cow_ret == buf)
261 unlock_orig = 1;
262
263 WARN_ON(!btrfs_tree_locked(buf));
264
265 if (parent)
266 parent_start = parent->start;
267 else
268 parent_start = 0;
269
270 WARN_ON(root->ref_cows && trans->transid !=
271 root->fs_info->running_transaction->transid);
272 WARN_ON(root->ref_cows && trans->transid != root->last_trans);
273
274 level = btrfs_header_level(buf);
275 nritems = btrfs_header_nritems(buf);
276
277 if (prealloc_dest) {
278 struct btrfs_key ins;
279
280 ins.objectid = prealloc_dest;
281 ins.offset = buf->len;
282 ins.type = BTRFS_EXTENT_ITEM_KEY;
283
284 ret = btrfs_alloc_reserved_extent(trans, root, parent_start,
285 root->root_key.objectid,
286 trans->transid, level, &ins);
287 BUG_ON(ret);
288 cow = btrfs_init_new_buffer(trans, root, prealloc_dest,
289 buf->len);
290 } else {
291 cow = btrfs_alloc_free_block(trans, root, buf->len,
292 parent_start,
293 root->root_key.objectid,
294 trans->transid, level,
295 search_start, empty_size);
296 }
297 if (IS_ERR(cow))
298 return PTR_ERR(cow);
299
300 /* cow is set to blocking by btrfs_init_new_buffer */
301
302 copy_extent_buffer(cow, buf, 0, 0, cow->len);
303 btrfs_set_header_bytenr(cow, cow->start);
304 btrfs_set_header_generation(cow, trans->transid);
305 btrfs_set_header_owner(cow, root->root_key.objectid);
306 btrfs_clear_header_flag(cow, BTRFS_HEADER_FLAG_WRITTEN);
307
308 write_extent_buffer(cow, root->fs_info->fsid,
309 (unsigned long)btrfs_header_fsid(cow),
310 BTRFS_FSID_SIZE);
311
312 WARN_ON(btrfs_header_generation(buf) > trans->transid);
313 if (btrfs_header_generation(buf) != trans->transid) {
314 u32 nr_extents;
315 ret = btrfs_inc_ref(trans, root, buf, cow, &nr_extents);
316 if (ret)
317 return ret;
318
319 ret = btrfs_cache_ref(trans, root, buf, nr_extents);
320 WARN_ON(ret);
321 } else if (btrfs_header_owner(buf) == BTRFS_TREE_RELOC_OBJECTID) {
322 /*
323 * There are only two places that can drop reference to
324 * tree blocks owned by living reloc trees, one is here,
325 * the other place is btrfs_drop_subtree. In both places,
326 * we check reference count while tree block is locked.
327 * Furthermore, if reference count is one, it won't get
328 * increased by someone else.
329 */
330 u32 refs;
331 ret = btrfs_lookup_extent_ref(trans, root, buf->start,
332 buf->len, &refs);
333 BUG_ON(ret);
334 if (refs == 1) {
335 ret = btrfs_update_ref(trans, root, buf, cow,
336 0, nritems);
337 clean_tree_block(trans, root, buf);
338 } else {
339 ret = btrfs_inc_ref(trans, root, buf, cow, NULL);
340 }
341 BUG_ON(ret);
342 } else {
343 ret = btrfs_update_ref(trans, root, buf, cow, 0, nritems);
344 if (ret)
345 return ret;
346 clean_tree_block(trans, root, buf);
347 }
348
349 if (root->root_key.objectid == BTRFS_TREE_RELOC_OBJECTID) {
350 ret = btrfs_reloc_tree_cache_ref(trans, root, cow, buf->start);
351 WARN_ON(ret);
352 }
353
354 if (buf == root->node) {
355 WARN_ON(parent && parent != buf);
356
357 spin_lock(&root->node_lock);
358 root->node = cow;
359 extent_buffer_get(cow);
360 spin_unlock(&root->node_lock);
361
362 if (buf != root->commit_root) {
363 btrfs_free_extent(trans, root, buf->start,
364 buf->len, buf->start,
365 root->root_key.objectid,
366 btrfs_header_generation(buf),
367 level, 1);
368 }
369 free_extent_buffer(buf);
370 add_root_to_dirty_list(root);
371 } else {
372 btrfs_set_node_blockptr(parent, parent_slot,
373 cow->start);
374 WARN_ON(trans->transid == 0);
375 btrfs_set_node_ptr_generation(parent, parent_slot,
376 trans->transid);
377 btrfs_mark_buffer_dirty(parent);
378 WARN_ON(btrfs_header_generation(parent) != trans->transid);
379 btrfs_free_extent(trans, root, buf->start, buf->len,
380 parent_start, btrfs_header_owner(parent),
381 btrfs_header_generation(parent), level, 1);
382 }
383 if (unlock_orig)
384 btrfs_tree_unlock(buf);
385 free_extent_buffer(buf);
386 btrfs_mark_buffer_dirty(cow);
387 *cow_ret = cow;
388 return 0;
389 }
390
391 /*
392 * cows a single block, see __btrfs_cow_block for the real work.
393 * This version of it has extra checks so that a block isn't cow'd more than
394 * once per transaction, as long as it hasn't been written yet
395 */
396 noinline int btrfs_cow_block(struct btrfs_trans_handle *trans,
397 struct btrfs_root *root, struct extent_buffer *buf,
398 struct extent_buffer *parent, int parent_slot,
399 struct extent_buffer **cow_ret, u64 prealloc_dest)
400 {
401 u64 search_start;
402 int ret;
403
404 if (trans->transaction != root->fs_info->running_transaction) {
405 printk(KERN_CRIT "trans %llu running %llu\n",
406 (unsigned long long)trans->transid,
407 (unsigned long long)
408 root->fs_info->running_transaction->transid);
409 WARN_ON(1);
410 }
411 if (trans->transid != root->fs_info->generation) {
412 printk(KERN_CRIT "trans %llu running %llu\n",
413 (unsigned long long)trans->transid,
414 (unsigned long long)root->fs_info->generation);
415 WARN_ON(1);
416 }
417
418 if (btrfs_header_generation(buf) == trans->transid &&
419 btrfs_header_owner(buf) == root->root_key.objectid &&
420 !btrfs_header_flag(buf, BTRFS_HEADER_FLAG_WRITTEN)) {
421 *cow_ret = buf;
422 WARN_ON(prealloc_dest);
423 return 0;
424 }
425
426 search_start = buf->start & ~((u64)(1024 * 1024 * 1024) - 1);
427
428 if (parent)
429 btrfs_set_lock_blocking(parent);
430 btrfs_set_lock_blocking(buf);
431
432 ret = __btrfs_cow_block(trans, root, buf, parent,
433 parent_slot, cow_ret, search_start, 0,
434 prealloc_dest);
435 return ret;
436 }
437
438 /*
439 * helper function for defrag to decide if two blocks pointed to by a
440 * node are actually close by
441 */
442 static int close_blocks(u64 blocknr, u64 other, u32 blocksize)
443 {
444 if (blocknr < other && other - (blocknr + blocksize) < 32768)
445 return 1;
446 if (blocknr > other && blocknr - (other + blocksize) < 32768)
447 return 1;
448 return 0;
449 }
450
451 /*
452 * compare two keys in a memcmp fashion
453 */
454 static int comp_keys(struct btrfs_disk_key *disk, struct btrfs_key *k2)
455 {
456 struct btrfs_key k1;
457
458 btrfs_disk_key_to_cpu(&k1, disk);
459
460 if (k1.objectid > k2->objectid)
461 return 1;
462 if (k1.objectid < k2->objectid)
463 return -1;
464 if (k1.type > k2->type)
465 return 1;
466 if (k1.type < k2->type)
467 return -1;
468 if (k1.offset > k2->offset)
469 return 1;
470 if (k1.offset < k2->offset)
471 return -1;
472 return 0;
473 }
474
475 /*
476 * same as comp_keys only with two btrfs_key's
477 */
478 static int comp_cpu_keys(struct btrfs_key *k1, struct btrfs_key *k2)
479 {
480 if (k1->objectid > k2->objectid)
481 return 1;
482 if (k1->objectid < k2->objectid)
483 return -1;
484 if (k1->type > k2->type)
485 return 1;
486 if (k1->type < k2->type)
487 return -1;
488 if (k1->offset > k2->offset)
489 return 1;
490 if (k1->offset < k2->offset)
491 return -1;
492 return 0;
493 }
494
495 /*
496 * this is used by the defrag code to go through all the
497 * leaves pointed to by a node and reallocate them so that
498 * disk order is close to key order
499 */
500 int btrfs_realloc_node(struct btrfs_trans_handle *trans,
501 struct btrfs_root *root, struct extent_buffer *parent,
502 int start_slot, int cache_only, u64 *last_ret,
503 struct btrfs_key *progress)
504 {
505 struct extent_buffer *cur;
506 u64 blocknr;
507 u64 gen;
508 u64 search_start = *last_ret;
509 u64 last_block = 0;
510 u64 other;
511 u32 parent_nritems;
512 int end_slot;
513 int i;
514 int err = 0;
515 int parent_level;
516 int uptodate;
517 u32 blocksize;
518 int progress_passed = 0;
519 struct btrfs_disk_key disk_key;
520
521 parent_level = btrfs_header_level(parent);
522 if (cache_only && parent_level != 1)
523 return 0;
524
525 if (trans->transaction != root->fs_info->running_transaction)
526 WARN_ON(1);
527 if (trans->transid != root->fs_info->generation)
528 WARN_ON(1);
529
530 parent_nritems = btrfs_header_nritems(parent);
531 blocksize = btrfs_level_size(root, parent_level - 1);
532 end_slot = parent_nritems;
533
534 if (parent_nritems == 1)
535 return 0;
536
537 btrfs_set_lock_blocking(parent);
538
539 for (i = start_slot; i < end_slot; i++) {
540 int close = 1;
541
542 if (!parent->map_token) {
543 map_extent_buffer(parent,
544 btrfs_node_key_ptr_offset(i),
545 sizeof(struct btrfs_key_ptr),
546 &parent->map_token, &parent->kaddr,
547 &parent->map_start, &parent->map_len,
548 KM_USER1);
549 }
550 btrfs_node_key(parent, &disk_key, i);
551 if (!progress_passed && comp_keys(&disk_key, progress) < 0)
552 continue;
553
554 progress_passed = 1;
555 blocknr = btrfs_node_blockptr(parent, i);
556 gen = btrfs_node_ptr_generation(parent, i);
557 if (last_block == 0)
558 last_block = blocknr;
559
560 if (i > 0) {
561 other = btrfs_node_blockptr(parent, i - 1);
562 close = close_blocks(blocknr, other, blocksize);
563 }
564 if (!close && i < end_slot - 2) {
565 other = btrfs_node_blockptr(parent, i + 1);
566 close = close_blocks(blocknr, other, blocksize);
567 }
568 if (close) {
569 last_block = blocknr;
570 continue;
571 }
572 if (parent->map_token) {
573 unmap_extent_buffer(parent, parent->map_token,
574 KM_USER1);
575 parent->map_token = NULL;
576 }
577
578 cur = btrfs_find_tree_block(root, blocknr, blocksize);
579 if (cur)
580 uptodate = btrfs_buffer_uptodate(cur, gen);
581 else
582 uptodate = 0;
583 if (!cur || !uptodate) {
584 if (cache_only) {
585 free_extent_buffer(cur);
586 continue;
587 }
588 if (!cur) {
589 cur = read_tree_block(root, blocknr,
590 blocksize, gen);
591 } else if (!uptodate) {
592 btrfs_read_buffer(cur, gen);
593 }
594 }
595 if (search_start == 0)
596 search_start = last_block;
597
598 btrfs_tree_lock(cur);
599 btrfs_set_lock_blocking(cur);
600 err = __btrfs_cow_block(trans, root, cur, parent, i,
601 &cur, search_start,
602 min(16 * blocksize,
603 (end_slot - i) * blocksize), 0);
604 if (err) {
605 btrfs_tree_unlock(cur);
606 free_extent_buffer(cur);
607 break;
608 }
609 search_start = cur->start;
610 last_block = cur->start;
611 *last_ret = search_start;
612 btrfs_tree_unlock(cur);
613 free_extent_buffer(cur);
614 }
615 if (parent->map_token) {
616 unmap_extent_buffer(parent, parent->map_token,
617 KM_USER1);
618 parent->map_token = NULL;
619 }
620 return err;
621 }
622
623 /*
624 * The leaf data grows from end-to-front in the node.
625 * this returns the address of the start of the last item,
626 * which is the stop of the leaf data stack
627 */
628 static inline unsigned int leaf_data_end(struct btrfs_root *root,
629 struct extent_buffer *leaf)
630 {
631 u32 nr = btrfs_header_nritems(leaf);
632 if (nr == 0)
633 return BTRFS_LEAF_DATA_SIZE(root);
634 return btrfs_item_offset_nr(leaf, nr - 1);
635 }
636
637 /*
638 * extra debugging checks to make sure all the items in a key are
639 * well formed and in the proper order
640 */
641 static int check_node(struct btrfs_root *root, struct btrfs_path *path,
642 int level)
643 {
644 struct extent_buffer *parent = NULL;
645 struct extent_buffer *node = path->nodes[level];
646 struct btrfs_disk_key parent_key;
647 struct btrfs_disk_key node_key;
648 int parent_slot;
649 int slot;
650 struct btrfs_key cpukey;
651 u32 nritems = btrfs_header_nritems(node);
652
653 if (path->nodes[level + 1])
654 parent = path->nodes[level + 1];
655
656 slot = path->slots[level];
657 BUG_ON(nritems == 0);
658 if (parent) {
659 parent_slot = path->slots[level + 1];
660 btrfs_node_key(parent, &parent_key, parent_slot);
661 btrfs_node_key(node, &node_key, 0);
662 BUG_ON(memcmp(&parent_key, &node_key,
663 sizeof(struct btrfs_disk_key)));
664 BUG_ON(btrfs_node_blockptr(parent, parent_slot) !=
665 btrfs_header_bytenr(node));
666 }
667 BUG_ON(nritems > BTRFS_NODEPTRS_PER_BLOCK(root));
668 if (slot != 0) {
669 btrfs_node_key_to_cpu(node, &cpukey, slot - 1);
670 btrfs_node_key(node, &node_key, slot);
671 BUG_ON(comp_keys(&node_key, &cpukey) <= 0);
672 }
673 if (slot < nritems - 1) {
674 btrfs_node_key_to_cpu(node, &cpukey, slot + 1);
675 btrfs_node_key(node, &node_key, slot);
676 BUG_ON(comp_keys(&node_key, &cpukey) >= 0);
677 }
678 return 0;
679 }
680
681 /*
682 * extra checking to make sure all the items in a leaf are
683 * well formed and in the proper order
684 */
685 static int check_leaf(struct btrfs_root *root, struct btrfs_path *path,
686 int level)
687 {
688 struct extent_buffer *leaf = path->nodes[level];
689 struct extent_buffer *parent = NULL;
690 int parent_slot;
691 struct btrfs_key cpukey;
692 struct btrfs_disk_key parent_key;
693 struct btrfs_disk_key leaf_key;
694 int slot = path->slots[0];
695
696 u32 nritems = btrfs_header_nritems(leaf);
697
698 if (path->nodes[level + 1])
699 parent = path->nodes[level + 1];
700
701 if (nritems == 0)
702 return 0;
703
704 if (parent) {
705 parent_slot = path->slots[level + 1];
706 btrfs_node_key(parent, &parent_key, parent_slot);
707 btrfs_item_key(leaf, &leaf_key, 0);
708
709 BUG_ON(memcmp(&parent_key, &leaf_key,
710 sizeof(struct btrfs_disk_key)));
711 BUG_ON(btrfs_node_blockptr(parent, parent_slot) !=
712 btrfs_header_bytenr(leaf));
713 }
714 if (slot != 0 && slot < nritems - 1) {
715 btrfs_item_key(leaf, &leaf_key, slot);
716 btrfs_item_key_to_cpu(leaf, &cpukey, slot - 1);
717 if (comp_keys(&leaf_key, &cpukey) <= 0) {
718 btrfs_print_leaf(root, leaf);
719 printk(KERN_CRIT "slot %d offset bad key\n", slot);
720 BUG_ON(1);
721 }
722 if (btrfs_item_offset_nr(leaf, slot - 1) !=
723 btrfs_item_end_nr(leaf, slot)) {
724 btrfs_print_leaf(root, leaf);
725 printk(KERN_CRIT "slot %d offset bad\n", slot);
726 BUG_ON(1);
727 }
728 }
729 if (slot < nritems - 1) {
730 btrfs_item_key(leaf, &leaf_key, slot);
731 btrfs_item_key_to_cpu(leaf, &cpukey, slot + 1);
732 BUG_ON(comp_keys(&leaf_key, &cpukey) >= 0);
733 if (btrfs_item_offset_nr(leaf, slot) !=
734 btrfs_item_end_nr(leaf, slot + 1)) {
735 btrfs_print_leaf(root, leaf);
736 printk(KERN_CRIT "slot %d offset bad\n", slot);
737 BUG_ON(1);
738 }
739 }
740 BUG_ON(btrfs_item_offset_nr(leaf, 0) +
741 btrfs_item_size_nr(leaf, 0) != BTRFS_LEAF_DATA_SIZE(root));
742 return 0;
743 }
744
745 static noinline int check_block(struct btrfs_root *root,
746 struct btrfs_path *path, int level)
747 {
748 return 0;
749 if (level == 0)
750 return check_leaf(root, path, level);
751 return check_node(root, path, level);
752 }
753
754 /*
755 * search for key in the extent_buffer. The items start at offset p,
756 * and they are item_size apart. There are 'max' items in p.
757 *
758 * the slot in the array is returned via slot, and it points to
759 * the place where you would insert key if it is not found in
760 * the array.
761 *
762 * slot may point to max if the key is bigger than all of the keys
763 */
764 static noinline int generic_bin_search(struct extent_buffer *eb,
765 unsigned long p,
766 int item_size, struct btrfs_key *key,
767 int max, int *slot)
768 {
769 int low = 0;
770 int high = max;
771 int mid;
772 int ret;
773 struct btrfs_disk_key *tmp = NULL;
774 struct btrfs_disk_key unaligned;
775 unsigned long offset;
776 char *map_token = NULL;
777 char *kaddr = NULL;
778 unsigned long map_start = 0;
779 unsigned long map_len = 0;
780 int err;
781
782 while (low < high) {
783 mid = (low + high) / 2;
784 offset = p + mid * item_size;
785
786 if (!map_token || offset < map_start ||
787 (offset + sizeof(struct btrfs_disk_key)) >
788 map_start + map_len) {
789 if (map_token) {
790 unmap_extent_buffer(eb, map_token, KM_USER0);
791 map_token = NULL;
792 }
793
794 err = map_private_extent_buffer(eb, offset,
795 sizeof(struct btrfs_disk_key),
796 &map_token, &kaddr,
797 &map_start, &map_len, KM_USER0);
798
799 if (!err) {
800 tmp = (struct btrfs_disk_key *)(kaddr + offset -
801 map_start);
802 } else {
803 read_extent_buffer(eb, &unaligned,
804 offset, sizeof(unaligned));
805 tmp = &unaligned;
806 }
807
808 } else {
809 tmp = (struct btrfs_disk_key *)(kaddr + offset -
810 map_start);
811 }
812 ret = comp_keys(tmp, key);
813
814 if (ret < 0)
815 low = mid + 1;
816 else if (ret > 0)
817 high = mid;
818 else {
819 *slot = mid;
820 if (map_token)
821 unmap_extent_buffer(eb, map_token, KM_USER0);
822 return 0;
823 }
824 }
825 *slot = low;
826 if (map_token)
827 unmap_extent_buffer(eb, map_token, KM_USER0);
828 return 1;
829 }
830
831 /*
832 * simple bin_search frontend that does the right thing for
833 * leaves vs nodes
834 */
835 static int bin_search(struct extent_buffer *eb, struct btrfs_key *key,
836 int level, int *slot)
837 {
838 if (level == 0) {
839 return generic_bin_search(eb,
840 offsetof(struct btrfs_leaf, items),
841 sizeof(struct btrfs_item),
842 key, btrfs_header_nritems(eb),
843 slot);
844 } else {
845 return generic_bin_search(eb,
846 offsetof(struct btrfs_node, ptrs),
847 sizeof(struct btrfs_key_ptr),
848 key, btrfs_header_nritems(eb),
849 slot);
850 }
851 return -1;
852 }
853
854 /* given a node and slot number, this reads the blocks it points to. The
855 * extent buffer is returned with a reference taken (but unlocked).
856 * NULL is returned on error.
857 */
858 static noinline struct extent_buffer *read_node_slot(struct btrfs_root *root,
859 struct extent_buffer *parent, int slot)
860 {
861 int level = btrfs_header_level(parent);
862 if (slot < 0)
863 return NULL;
864 if (slot >= btrfs_header_nritems(parent))
865 return NULL;
866
867 BUG_ON(level == 0);
868
869 return read_tree_block(root, btrfs_node_blockptr(parent, slot),
870 btrfs_level_size(root, level - 1),
871 btrfs_node_ptr_generation(parent, slot));
872 }
873
874 /*
875 * node level balancing, used to make sure nodes are in proper order for
876 * item deletion. We balance from the top down, so we have to make sure
877 * that a deletion won't leave an node completely empty later on.
878 */
879 static noinline int balance_level(struct btrfs_trans_handle *trans,
880 struct btrfs_root *root,
881 struct btrfs_path *path, int level)
882 {
883 struct extent_buffer *right = NULL;
884 struct extent_buffer *mid;
885 struct extent_buffer *left = NULL;
886 struct extent_buffer *parent = NULL;
887 int ret = 0;
888 int wret;
889 int pslot;
890 int orig_slot = path->slots[level];
891 int err_on_enospc = 0;
892 u64 orig_ptr;
893
894 if (level == 0)
895 return 0;
896
897 mid = path->nodes[level];
898
899 WARN_ON(!path->locks[level]);
900 WARN_ON(btrfs_header_generation(mid) != trans->transid);
901
902 orig_ptr = btrfs_node_blockptr(mid, orig_slot);
903
904 if (level < BTRFS_MAX_LEVEL - 1)
905 parent = path->nodes[level + 1];
906 pslot = path->slots[level + 1];
907
908 /*
909 * deal with the case where there is only one pointer in the root
910 * by promoting the node below to a root
911 */
912 if (!parent) {
913 struct extent_buffer *child;
914
915 if (btrfs_header_nritems(mid) != 1)
916 return 0;
917
918 /* promote the child to a root */
919 child = read_node_slot(root, mid, 0);
920 btrfs_tree_lock(child);
921 btrfs_set_lock_blocking(child);
922 BUG_ON(!child);
923 ret = btrfs_cow_block(trans, root, child, mid, 0, &child, 0);
924 BUG_ON(ret);
925
926 spin_lock(&root->node_lock);
927 root->node = child;
928 spin_unlock(&root->node_lock);
929
930 ret = btrfs_update_extent_ref(trans, root, child->start,
931 mid->start, child->start,
932 root->root_key.objectid,
933 trans->transid, level - 1);
934 BUG_ON(ret);
935
936 add_root_to_dirty_list(root);
937 btrfs_tree_unlock(child);
938
939 path->locks[level] = 0;
940 path->nodes[level] = NULL;
941 clean_tree_block(trans, root, mid);
942 btrfs_tree_unlock(mid);
943 /* once for the path */
944 free_extent_buffer(mid);
945 ret = btrfs_free_extent(trans, root, mid->start, mid->len,
946 mid->start, root->root_key.objectid,
947 btrfs_header_generation(mid),
948 level, 1);
949 /* once for the root ptr */
950 free_extent_buffer(mid);
951 return ret;
952 }
953 if (btrfs_header_nritems(mid) >
954 BTRFS_NODEPTRS_PER_BLOCK(root) / 4)
955 return 0;
956
957 if (btrfs_header_nritems(mid) < 2)
958 err_on_enospc = 1;
959
960 left = read_node_slot(root, parent, pslot - 1);
961 if (left) {
962 btrfs_tree_lock(left);
963 btrfs_set_lock_blocking(left);
964 wret = btrfs_cow_block(trans, root, left,
965 parent, pslot - 1, &left, 0);
966 if (wret) {
967 ret = wret;
968 goto enospc;
969 }
970 }
971 right = read_node_slot(root, parent, pslot + 1);
972 if (right) {
973 btrfs_tree_lock(right);
974 btrfs_set_lock_blocking(right);
975 wret = btrfs_cow_block(trans, root, right,
976 parent, pslot + 1, &right, 0);
977 if (wret) {
978 ret = wret;
979 goto enospc;
980 }
981 }
982
983 /* first, try to make some room in the middle buffer */
984 if (left) {
985 orig_slot += btrfs_header_nritems(left);
986 wret = push_node_left(trans, root, left, mid, 1);
987 if (wret < 0)
988 ret = wret;
989 if (btrfs_header_nritems(mid) < 2)
990 err_on_enospc = 1;
991 }
992
993 /*
994 * then try to empty the right most buffer into the middle
995 */
996 if (right) {
997 wret = push_node_left(trans, root, mid, right, 1);
998 if (wret < 0 && wret != -ENOSPC)
999 ret = wret;
1000 if (btrfs_header_nritems(right) == 0) {
1001 u64 bytenr = right->start;
1002 u64 generation = btrfs_header_generation(parent);
1003 u32 blocksize = right->len;
1004
1005 clean_tree_block(trans, root, right);
1006 btrfs_tree_unlock(right);
1007 free_extent_buffer(right);
1008 right = NULL;
1009 wret = del_ptr(trans, root, path, level + 1, pslot +
1010 1);
1011 if (wret)
1012 ret = wret;
1013 wret = btrfs_free_extent(trans, root, bytenr,
1014 blocksize, parent->start,
1015 btrfs_header_owner(parent),
1016 generation, level, 1);
1017 if (wret)
1018 ret = wret;
1019 } else {
1020 struct btrfs_disk_key right_key;
1021 btrfs_node_key(right, &right_key, 0);
1022 btrfs_set_node_key(parent, &right_key, pslot + 1);
1023 btrfs_mark_buffer_dirty(parent);
1024 }
1025 }
1026 if (btrfs_header_nritems(mid) == 1) {
1027 /*
1028 * we're not allowed to leave a node with one item in the
1029 * tree during a delete. A deletion from lower in the tree
1030 * could try to delete the only pointer in this node.
1031 * So, pull some keys from the left.
1032 * There has to be a left pointer at this point because
1033 * otherwise we would have pulled some pointers from the
1034 * right
1035 */
1036 BUG_ON(!left);
1037 wret = balance_node_right(trans, root, mid, left);
1038 if (wret < 0) {
1039 ret = wret;
1040 goto enospc;
1041 }
1042 if (wret == 1) {
1043 wret = push_node_left(trans, root, left, mid, 1);
1044 if (wret < 0)
1045 ret = wret;
1046 }
1047 BUG_ON(wret == 1);
1048 }
1049 if (btrfs_header_nritems(mid) == 0) {
1050 /* we've managed to empty the middle node, drop it */
1051 u64 root_gen = btrfs_header_generation(parent);
1052 u64 bytenr = mid->start;
1053 u32 blocksize = mid->len;
1054
1055 clean_tree_block(trans, root, mid);
1056 btrfs_tree_unlock(mid);
1057 free_extent_buffer(mid);
1058 mid = NULL;
1059 wret = del_ptr(trans, root, path, level + 1, pslot);
1060 if (wret)
1061 ret = wret;
1062 wret = btrfs_free_extent(trans, root, bytenr, blocksize,
1063 parent->start,
1064 btrfs_header_owner(parent),
1065 root_gen, level, 1);
1066 if (wret)
1067 ret = wret;
1068 } else {
1069 /* update the parent key to reflect our changes */
1070 struct btrfs_disk_key mid_key;
1071 btrfs_node_key(mid, &mid_key, 0);
1072 btrfs_set_node_key(parent, &mid_key, pslot);
1073 btrfs_mark_buffer_dirty(parent);
1074 }
1075
1076 /* update the path */
1077 if (left) {
1078 if (btrfs_header_nritems(left) > orig_slot) {
1079 extent_buffer_get(left);
1080 /* left was locked after cow */
1081 path->nodes[level] = left;
1082 path->slots[level + 1] -= 1;
1083 path->slots[level] = orig_slot;
1084 if (mid) {
1085 btrfs_tree_unlock(mid);
1086 free_extent_buffer(mid);
1087 }
1088 } else {
1089 orig_slot -= btrfs_header_nritems(left);
1090 path->slots[level] = orig_slot;
1091 }
1092 }
1093 /* double check we haven't messed things up */
1094 check_block(root, path, level);
1095 if (orig_ptr !=
1096 btrfs_node_blockptr(path->nodes[level], path->slots[level]))
1097 BUG();
1098 enospc:
1099 if (right) {
1100 btrfs_tree_unlock(right);
1101 free_extent_buffer(right);
1102 }
1103 if (left) {
1104 if (path->nodes[level] != left)
1105 btrfs_tree_unlock(left);
1106 free_extent_buffer(left);
1107 }
1108 return ret;
1109 }
1110
1111 /* Node balancing for insertion. Here we only split or push nodes around
1112 * when they are completely full. This is also done top down, so we
1113 * have to be pessimistic.
1114 */
1115 static noinline int push_nodes_for_insert(struct btrfs_trans_handle *trans,
1116 struct btrfs_root *root,
1117 struct btrfs_path *path, int level)
1118 {
1119 struct extent_buffer *right = NULL;
1120 struct extent_buffer *mid;
1121 struct extent_buffer *left = NULL;
1122 struct extent_buffer *parent = NULL;
1123 int ret = 0;
1124 int wret;
1125 int pslot;
1126 int orig_slot = path->slots[level];
1127 u64 orig_ptr;
1128
1129 if (level == 0)
1130 return 1;
1131
1132 mid = path->nodes[level];
1133 WARN_ON(btrfs_header_generation(mid) != trans->transid);
1134 orig_ptr = btrfs_node_blockptr(mid, orig_slot);
1135
1136 if (level < BTRFS_MAX_LEVEL - 1)
1137 parent = path->nodes[level + 1];
1138 pslot = path->slots[level + 1];
1139
1140 if (!parent)
1141 return 1;
1142
1143 left = read_node_slot(root, parent, pslot - 1);
1144
1145 /* first, try to make some room in the middle buffer */
1146 if (left) {
1147 u32 left_nr;
1148
1149 btrfs_tree_lock(left);
1150 btrfs_set_lock_blocking(left);
1151
1152 left_nr = btrfs_header_nritems(left);
1153 if (left_nr >= BTRFS_NODEPTRS_PER_BLOCK(root) - 1) {
1154 wret = 1;
1155 } else {
1156 ret = btrfs_cow_block(trans, root, left, parent,
1157 pslot - 1, &left, 0);
1158 if (ret)
1159 wret = 1;
1160 else {
1161 wret = push_node_left(trans, root,
1162 left, mid, 0);
1163 }
1164 }
1165 if (wret < 0)
1166 ret = wret;
1167 if (wret == 0) {
1168 struct btrfs_disk_key disk_key;
1169 orig_slot += left_nr;
1170 btrfs_node_key(mid, &disk_key, 0);
1171 btrfs_set_node_key(parent, &disk_key, pslot);
1172 btrfs_mark_buffer_dirty(parent);
1173 if (btrfs_header_nritems(left) > orig_slot) {
1174 path->nodes[level] = left;
1175 path->slots[level + 1] -= 1;
1176 path->slots[level] = orig_slot;
1177 btrfs_tree_unlock(mid);
1178 free_extent_buffer(mid);
1179 } else {
1180 orig_slot -=
1181 btrfs_header_nritems(left);
1182 path->slots[level] = orig_slot;
1183 btrfs_tree_unlock(left);
1184 free_extent_buffer(left);
1185 }
1186 return 0;
1187 }
1188 btrfs_tree_unlock(left);
1189 free_extent_buffer(left);
1190 }
1191 right = read_node_slot(root, parent, pslot + 1);
1192
1193 /*
1194 * then try to empty the right most buffer into the middle
1195 */
1196 if (right) {
1197 u32 right_nr;
1198
1199 btrfs_tree_lock(right);
1200 btrfs_set_lock_blocking(right);
1201
1202 right_nr = btrfs_header_nritems(right);
1203 if (right_nr >= BTRFS_NODEPTRS_PER_BLOCK(root) - 1) {
1204 wret = 1;
1205 } else {
1206 ret = btrfs_cow_block(trans, root, right,
1207 parent, pslot + 1,
1208 &right, 0);
1209 if (ret)
1210 wret = 1;
1211 else {
1212 wret = balance_node_right(trans, root,
1213 right, mid);
1214 }
1215 }
1216 if (wret < 0)
1217 ret = wret;
1218 if (wret == 0) {
1219 struct btrfs_disk_key disk_key;
1220
1221 btrfs_node_key(right, &disk_key, 0);
1222 btrfs_set_node_key(parent, &disk_key, pslot + 1);
1223 btrfs_mark_buffer_dirty(parent);
1224
1225 if (btrfs_header_nritems(mid) <= orig_slot) {
1226 path->nodes[level] = right;
1227 path->slots[level + 1] += 1;
1228 path->slots[level] = orig_slot -
1229 btrfs_header_nritems(mid);
1230 btrfs_tree_unlock(mid);
1231 free_extent_buffer(mid);
1232 } else {
1233 btrfs_tree_unlock(right);
1234 free_extent_buffer(right);
1235 }
1236 return 0;
1237 }
1238 btrfs_tree_unlock(right);
1239 free_extent_buffer(right);
1240 }
1241 return 1;
1242 }
1243
1244 /*
1245 * readahead one full node of leaves, finding things that are close
1246 * to the block in 'slot', and triggering ra on them.
1247 */
1248 static noinline void reada_for_search(struct btrfs_root *root,
1249 struct btrfs_path *path,
1250 int level, int slot, u64 objectid)
1251 {
1252 struct extent_buffer *node;
1253 struct btrfs_disk_key disk_key;
1254 u32 nritems;
1255 u64 search;
1256 u64 target;
1257 u64 nread = 0;
1258 int direction = path->reada;
1259 struct extent_buffer *eb;
1260 u32 nr;
1261 u32 blocksize;
1262 u32 nscan = 0;
1263
1264 if (level != 1)
1265 return;
1266
1267 if (!path->nodes[level])
1268 return;
1269
1270 node = path->nodes[level];
1271
1272 search = btrfs_node_blockptr(node, slot);
1273 blocksize = btrfs_level_size(root, level - 1);
1274 eb = btrfs_find_tree_block(root, search, blocksize);
1275 if (eb) {
1276 free_extent_buffer(eb);
1277 return;
1278 }
1279
1280 target = search;
1281
1282 nritems = btrfs_header_nritems(node);
1283 nr = slot;
1284 while (1) {
1285 if (direction < 0) {
1286 if (nr == 0)
1287 break;
1288 nr--;
1289 } else if (direction > 0) {
1290 nr++;
1291 if (nr >= nritems)
1292 break;
1293 }
1294 if (path->reada < 0 && objectid) {
1295 btrfs_node_key(node, &disk_key, nr);
1296 if (btrfs_disk_key_objectid(&disk_key) != objectid)
1297 break;
1298 }
1299 search = btrfs_node_blockptr(node, nr);
1300 if ((search <= target && target - search <= 65536) ||
1301 (search > target && search - target <= 65536)) {
1302 readahead_tree_block(root, search, blocksize,
1303 btrfs_node_ptr_generation(node, nr));
1304 nread += blocksize;
1305 }
1306 nscan++;
1307 if ((nread > 65536 || nscan > 32))
1308 break;
1309 }
1310 }
1311
1312 /*
1313 * returns -EAGAIN if it had to drop the path, or zero if everything was in
1314 * cache
1315 */
1316 static noinline int reada_for_balance(struct btrfs_root *root,
1317 struct btrfs_path *path, int level)
1318 {
1319 int slot;
1320 int nritems;
1321 struct extent_buffer *parent;
1322 struct extent_buffer *eb;
1323 u64 gen;
1324 u64 block1 = 0;
1325 u64 block2 = 0;
1326 int ret = 0;
1327 int blocksize;
1328
1329 parent = path->nodes[level - 1];
1330 if (!parent)
1331 return 0;
1332
1333 nritems = btrfs_header_nritems(parent);
1334 slot = path->slots[level];
1335 blocksize = btrfs_level_size(root, level);
1336
1337 if (slot > 0) {
1338 block1 = btrfs_node_blockptr(parent, slot - 1);
1339 gen = btrfs_node_ptr_generation(parent, slot - 1);
1340 eb = btrfs_find_tree_block(root, block1, blocksize);
1341 if (eb && btrfs_buffer_uptodate(eb, gen))
1342 block1 = 0;
1343 free_extent_buffer(eb);
1344 }
1345 if (slot < nritems) {
1346 block2 = btrfs_node_blockptr(parent, slot + 1);
1347 gen = btrfs_node_ptr_generation(parent, slot + 1);
1348 eb = btrfs_find_tree_block(root, block2, blocksize);
1349 if (eb && btrfs_buffer_uptodate(eb, gen))
1350 block2 = 0;
1351 free_extent_buffer(eb);
1352 }
1353 if (block1 || block2) {
1354 ret = -EAGAIN;
1355 btrfs_release_path(root, path);
1356 if (block1)
1357 readahead_tree_block(root, block1, blocksize, 0);
1358 if (block2)
1359 readahead_tree_block(root, block2, blocksize, 0);
1360
1361 if (block1) {
1362 eb = read_tree_block(root, block1, blocksize, 0);
1363 free_extent_buffer(eb);
1364 }
1365 if (block1) {
1366 eb = read_tree_block(root, block2, blocksize, 0);
1367 free_extent_buffer(eb);
1368 }
1369 }
1370 return ret;
1371 }
1372
1373
1374 /*
1375 * when we walk down the tree, it is usually safe to unlock the higher layers
1376 * in the tree. The exceptions are when our path goes through slot 0, because
1377 * operations on the tree might require changing key pointers higher up in the
1378 * tree.
1379 *
1380 * callers might also have set path->keep_locks, which tells this code to keep
1381 * the lock if the path points to the last slot in the block. This is part of
1382 * walking through the tree, and selecting the next slot in the higher block.
1383 *
1384 * lowest_unlock sets the lowest level in the tree we're allowed to unlock. so
1385 * if lowest_unlock is 1, level 0 won't be unlocked
1386 */
1387 static noinline void unlock_up(struct btrfs_path *path, int level,
1388 int lowest_unlock)
1389 {
1390 int i;
1391 int skip_level = level;
1392 int no_skips = 0;
1393 struct extent_buffer *t;
1394
1395 for (i = level; i < BTRFS_MAX_LEVEL; i++) {
1396 if (!path->nodes[i])
1397 break;
1398 if (!path->locks[i])
1399 break;
1400 if (!no_skips && path->slots[i] == 0) {
1401 skip_level = i + 1;
1402 continue;
1403 }
1404 if (!no_skips && path->keep_locks) {
1405 u32 nritems;
1406 t = path->nodes[i];
1407 nritems = btrfs_header_nritems(t);
1408 if (nritems < 1 || path->slots[i] >= nritems - 1) {
1409 skip_level = i + 1;
1410 continue;
1411 }
1412 }
1413 if (skip_level < i && i >= lowest_unlock)
1414 no_skips = 1;
1415
1416 t = path->nodes[i];
1417 if (i >= lowest_unlock && i > skip_level && path->locks[i]) {
1418 btrfs_tree_unlock(t);
1419 path->locks[i] = 0;
1420 }
1421 }
1422 }
1423
1424 /*
1425 * This releases any locks held in the path starting at level and
1426 * going all the way up to the root.
1427 *
1428 * btrfs_search_slot will keep the lock held on higher nodes in a few
1429 * corner cases, such as COW of the block at slot zero in the node. This
1430 * ignores those rules, and it should only be called when there are no
1431 * more updates to be done higher up in the tree.
1432 */
1433 noinline void btrfs_unlock_up_safe(struct btrfs_path *path, int level)
1434 {
1435 int i;
1436
1437 if (path->keep_locks || path->lowest_level)
1438 return;
1439
1440 for (i = level; i < BTRFS_MAX_LEVEL; i++) {
1441 if (!path->nodes[i])
1442 continue;
1443 if (!path->locks[i])
1444 continue;
1445 btrfs_tree_unlock(path->nodes[i]);
1446 path->locks[i] = 0;
1447 }
1448 }
1449
1450 /*
1451 * look for key in the tree. path is filled in with nodes along the way
1452 * if key is found, we return zero and you can find the item in the leaf
1453 * level of the path (level 0)
1454 *
1455 * If the key isn't found, the path points to the slot where it should
1456 * be inserted, and 1 is returned. If there are other errors during the
1457 * search a negative error number is returned.
1458 *
1459 * if ins_len > 0, nodes and leaves will be split as we walk down the
1460 * tree. if ins_len < 0, nodes will be merged as we walk down the tree (if
1461 * possible)
1462 */
1463 int btrfs_search_slot(struct btrfs_trans_handle *trans, struct btrfs_root
1464 *root, struct btrfs_key *key, struct btrfs_path *p, int
1465 ins_len, int cow)
1466 {
1467 struct extent_buffer *b;
1468 struct extent_buffer *tmp;
1469 int slot;
1470 int ret;
1471 int level;
1472 int should_reada = p->reada;
1473 int lowest_unlock = 1;
1474 int blocksize;
1475 u8 lowest_level = 0;
1476 u64 blocknr;
1477 u64 gen;
1478 struct btrfs_key prealloc_block;
1479
1480 lowest_level = p->lowest_level;
1481 WARN_ON(lowest_level && ins_len > 0);
1482 WARN_ON(p->nodes[0] != NULL);
1483
1484 if (ins_len < 0)
1485 lowest_unlock = 2;
1486
1487 prealloc_block.objectid = 0;
1488
1489 again:
1490 if (p->skip_locking)
1491 b = btrfs_root_node(root);
1492 else
1493 b = btrfs_lock_root_node(root);
1494
1495 while (b) {
1496 level = btrfs_header_level(b);
1497
1498 /*
1499 * setup the path here so we can release it under lock
1500 * contention with the cow code
1501 */
1502 p->nodes[level] = b;
1503 if (!p->skip_locking)
1504 p->locks[level] = 1;
1505
1506 if (cow) {
1507 int wret;
1508
1509 /* is a cow on this block not required */
1510 if (btrfs_header_generation(b) == trans->transid &&
1511 btrfs_header_owner(b) == root->root_key.objectid &&
1512 !btrfs_header_flag(b, BTRFS_HEADER_FLAG_WRITTEN)) {
1513 goto cow_done;
1514 }
1515
1516 /* ok, we have to cow, is our old prealloc the right
1517 * size?
1518 */
1519 if (prealloc_block.objectid &&
1520 prealloc_block.offset != b->len) {
1521 btrfs_release_path(root, p);
1522 btrfs_free_reserved_extent(root,
1523 prealloc_block.objectid,
1524 prealloc_block.offset);
1525 prealloc_block.objectid = 0;
1526 goto again;
1527 }
1528
1529 /*
1530 * for higher level blocks, try not to allocate blocks
1531 * with the block and the parent locks held.
1532 */
1533 if (level > 0 && !prealloc_block.objectid &&
1534 btrfs_path_lock_waiting(p, level)) {
1535 u32 size = b->len;
1536 u64 hint = b->start;
1537
1538 btrfs_release_path(root, p);
1539 ret = btrfs_reserve_extent(trans, root,
1540 size, size, 0,
1541 hint, (u64)-1,
1542 &prealloc_block, 0);
1543 BUG_ON(ret);
1544 goto again;
1545 }
1546
1547 btrfs_set_path_blocking(p);
1548
1549 wret = btrfs_cow_block(trans, root, b,
1550 p->nodes[level + 1],
1551 p->slots[level + 1],
1552 &b, prealloc_block.objectid);
1553 prealloc_block.objectid = 0;
1554 if (wret) {
1555 free_extent_buffer(b);
1556 ret = wret;
1557 goto done;
1558 }
1559 }
1560 cow_done:
1561 BUG_ON(!cow && ins_len);
1562 if (level != btrfs_header_level(b))
1563 WARN_ON(1);
1564 level = btrfs_header_level(b);
1565
1566 p->nodes[level] = b;
1567 if (!p->skip_locking)
1568 p->locks[level] = 1;
1569
1570 btrfs_clear_path_blocking(p);
1571
1572 /*
1573 * we have a lock on b and as long as we aren't changing
1574 * the tree, there is no way to for the items in b to change.
1575 * It is safe to drop the lock on our parent before we
1576 * go through the expensive btree search on b.
1577 *
1578 * If cow is true, then we might be changing slot zero,
1579 * which may require changing the parent. So, we can't
1580 * drop the lock until after we know which slot we're
1581 * operating on.
1582 */
1583 if (!cow)
1584 btrfs_unlock_up_safe(p, level + 1);
1585
1586 ret = check_block(root, p, level);
1587 if (ret) {
1588 ret = -1;
1589 goto done;
1590 }
1591
1592 ret = bin_search(b, key, level, &slot);
1593
1594 if (level != 0) {
1595 if (ret && slot > 0)
1596 slot -= 1;
1597 p->slots[level] = slot;
1598 if ((p->search_for_split || ins_len > 0) &&
1599 btrfs_header_nritems(b) >=
1600 BTRFS_NODEPTRS_PER_BLOCK(root) - 3) {
1601 int sret;
1602
1603 sret = reada_for_balance(root, p, level);
1604 if (sret)
1605 goto again;
1606
1607 btrfs_set_path_blocking(p);
1608 sret = split_node(trans, root, p, level);
1609 btrfs_clear_path_blocking(p);
1610
1611 BUG_ON(sret > 0);
1612 if (sret) {
1613 ret = sret;
1614 goto done;
1615 }
1616 b = p->nodes[level];
1617 slot = p->slots[level];
1618 } else if (ins_len < 0 &&
1619 btrfs_header_nritems(b) <
1620 BTRFS_NODEPTRS_PER_BLOCK(root) / 4) {
1621 int sret;
1622
1623 sret = reada_for_balance(root, p, level);
1624 if (sret)
1625 goto again;
1626
1627 btrfs_set_path_blocking(p);
1628 sret = balance_level(trans, root, p, level);
1629 btrfs_clear_path_blocking(p);
1630
1631 if (sret) {
1632 ret = sret;
1633 goto done;
1634 }
1635 b = p->nodes[level];
1636 if (!b) {
1637 btrfs_release_path(NULL, p);
1638 goto again;
1639 }
1640 slot = p->slots[level];
1641 BUG_ON(btrfs_header_nritems(b) == 1);
1642 }
1643 unlock_up(p, level, lowest_unlock);
1644
1645 /* this is only true while dropping a snapshot */
1646 if (level == lowest_level) {
1647 ret = 0;
1648 goto done;
1649 }
1650
1651 blocknr = btrfs_node_blockptr(b, slot);
1652 gen = btrfs_node_ptr_generation(b, slot);
1653 blocksize = btrfs_level_size(root, level - 1);
1654
1655 tmp = btrfs_find_tree_block(root, blocknr, blocksize);
1656 if (tmp && btrfs_buffer_uptodate(tmp, gen)) {
1657 b = tmp;
1658 } else {
1659 /*
1660 * reduce lock contention at high levels
1661 * of the btree by dropping locks before
1662 * we read.
1663 */
1664 if (level > 0) {
1665 btrfs_release_path(NULL, p);
1666 if (tmp)
1667 free_extent_buffer(tmp);
1668 if (should_reada)
1669 reada_for_search(root, p,
1670 level, slot,
1671 key->objectid);
1672
1673 tmp = read_tree_block(root, blocknr,
1674 blocksize, gen);
1675 if (tmp)
1676 free_extent_buffer(tmp);
1677 goto again;
1678 } else {
1679 btrfs_set_path_blocking(p);
1680 if (tmp)
1681 free_extent_buffer(tmp);
1682 if (should_reada)
1683 reada_for_search(root, p,
1684 level, slot,
1685 key->objectid);
1686 b = read_node_slot(root, b, slot);
1687 }
1688 }
1689 if (!p->skip_locking) {
1690 int lret;
1691
1692 btrfs_clear_path_blocking(p);
1693 lret = btrfs_try_spin_lock(b);
1694
1695 if (!lret) {
1696 btrfs_set_path_blocking(p);
1697 btrfs_tree_lock(b);
1698 btrfs_clear_path_blocking(p);
1699 }
1700 }
1701 } else {
1702 p->slots[level] = slot;
1703 if (ins_len > 0 &&
1704 btrfs_leaf_free_space(root, b) < ins_len) {
1705 int sret;
1706
1707 btrfs_set_path_blocking(p);
1708 sret = split_leaf(trans, root, key,
1709 p, ins_len, ret == 0);
1710 btrfs_clear_path_blocking(p);
1711
1712 BUG_ON(sret > 0);
1713 if (sret) {
1714 ret = sret;
1715 goto done;
1716 }
1717 }
1718 if (!p->search_for_split)
1719 unlock_up(p, level, lowest_unlock);
1720 goto done;
1721 }
1722 }
1723 ret = 1;
1724 done:
1725 /*
1726 * we don't really know what they plan on doing with the path
1727 * from here on, so for now just mark it as blocking
1728 */
1729 btrfs_set_path_blocking(p);
1730 if (prealloc_block.objectid) {
1731 btrfs_free_reserved_extent(root,
1732 prealloc_block.objectid,
1733 prealloc_block.offset);
1734 }
1735 return ret;
1736 }
1737
1738 int btrfs_merge_path(struct btrfs_trans_handle *trans,
1739 struct btrfs_root *root,
1740 struct btrfs_key *node_keys,
1741 u64 *nodes, int lowest_level)
1742 {
1743 struct extent_buffer *eb;
1744 struct extent_buffer *parent;
1745 struct btrfs_key key;
1746 u64 bytenr;
1747 u64 generation;
1748 u32 blocksize;
1749 int level;
1750 int slot;
1751 int key_match;
1752 int ret;
1753
1754 eb = btrfs_lock_root_node(root);
1755 ret = btrfs_cow_block(trans, root, eb, NULL, 0, &eb, 0);
1756 BUG_ON(ret);
1757
1758 btrfs_set_lock_blocking(eb);
1759
1760 parent = eb;
1761 while (1) {
1762 level = btrfs_header_level(parent);
1763 if (level == 0 || level <= lowest_level)
1764 break;
1765
1766 ret = bin_search(parent, &node_keys[lowest_level], level,
1767 &slot);
1768 if (ret && slot > 0)
1769 slot--;
1770
1771 bytenr = btrfs_node_blockptr(parent, slot);
1772 if (nodes[level - 1] == bytenr)
1773 break;
1774
1775 blocksize = btrfs_level_size(root, level - 1);
1776 generation = btrfs_node_ptr_generation(parent, slot);
1777 btrfs_node_key_to_cpu(eb, &key, slot);
1778 key_match = !memcmp(&key, &node_keys[level - 1], sizeof(key));
1779
1780 if (generation == trans->transid) {
1781 eb = read_tree_block(root, bytenr, blocksize,
1782 generation);
1783 btrfs_tree_lock(eb);
1784 btrfs_set_lock_blocking(eb);
1785 }
1786
1787 /*
1788 * if node keys match and node pointer hasn't been modified
1789 * in the running transaction, we can merge the path. for
1790 * blocks owened by reloc trees, the node pointer check is
1791 * skipped, this is because these blocks are fully controlled
1792 * by the space balance code, no one else can modify them.
1793 */
1794 if (!nodes[level - 1] || !key_match ||
1795 (generation == trans->transid &&
1796 btrfs_header_owner(eb) != BTRFS_TREE_RELOC_OBJECTID)) {
1797 if (level == 1 || level == lowest_level + 1) {
1798 if (generation == trans->transid) {
1799 btrfs_tree_unlock(eb);
1800 free_extent_buffer(eb);
1801 }
1802 break;
1803 }
1804
1805 if (generation != trans->transid) {
1806 eb = read_tree_block(root, bytenr, blocksize,
1807 generation);
1808 btrfs_tree_lock(eb);
1809 btrfs_set_lock_blocking(eb);
1810 }
1811
1812 ret = btrfs_cow_block(trans, root, eb, parent, slot,
1813 &eb, 0);
1814 BUG_ON(ret);
1815
1816 if (root->root_key.objectid ==
1817 BTRFS_TREE_RELOC_OBJECTID) {
1818 if (!nodes[level - 1]) {
1819 nodes[level - 1] = eb->start;
1820 memcpy(&node_keys[level - 1], &key,
1821 sizeof(node_keys[0]));
1822 } else {
1823 WARN_ON(1);
1824 }
1825 }
1826
1827 btrfs_tree_unlock(parent);
1828 free_extent_buffer(parent);
1829 parent = eb;
1830 continue;
1831 }
1832
1833 btrfs_set_node_blockptr(parent, slot, nodes[level - 1]);
1834 btrfs_set_node_ptr_generation(parent, slot, trans->transid);
1835 btrfs_mark_buffer_dirty(parent);
1836
1837 ret = btrfs_inc_extent_ref(trans, root,
1838 nodes[level - 1],
1839 blocksize, parent->start,
1840 btrfs_header_owner(parent),
1841 btrfs_header_generation(parent),
1842 level - 1);
1843 BUG_ON(ret);
1844
1845 /*
1846 * If the block was created in the running transaction,
1847 * it's possible this is the last reference to it, so we
1848 * should drop the subtree.
1849 */
1850 if (generation == trans->transid) {
1851 ret = btrfs_drop_subtree(trans, root, eb, parent);
1852 BUG_ON(ret);
1853 btrfs_tree_unlock(eb);
1854 free_extent_buffer(eb);
1855 } else {
1856 ret = btrfs_free_extent(trans, root, bytenr,
1857 blocksize, parent->start,
1858 btrfs_header_owner(parent),
1859 btrfs_header_generation(parent),
1860 level - 1, 1);
1861 BUG_ON(ret);
1862 }
1863 break;
1864 }
1865 btrfs_tree_unlock(parent);
1866 free_extent_buffer(parent);
1867 return 0;
1868 }
1869
1870 /*
1871 * adjust the pointers going up the tree, starting at level
1872 * making sure the right key of each node is points to 'key'.
1873 * This is used after shifting pointers to the left, so it stops
1874 * fixing up pointers when a given leaf/node is not in slot 0 of the
1875 * higher levels
1876 *
1877 * If this fails to write a tree block, it returns -1, but continues
1878 * fixing up the blocks in ram so the tree is consistent.
1879 */
1880 static int fixup_low_keys(struct btrfs_trans_handle *trans,
1881 struct btrfs_root *root, struct btrfs_path *path,
1882 struct btrfs_disk_key *key, int level)
1883 {
1884 int i;
1885 int ret = 0;
1886 struct extent_buffer *t;
1887
1888 for (i = level; i < BTRFS_MAX_LEVEL; i++) {
1889 int tslot = path->slots[i];
1890 if (!path->nodes[i])
1891 break;
1892 t = path->nodes[i];
1893 btrfs_set_node_key(t, key, tslot);
1894 btrfs_mark_buffer_dirty(path->nodes[i]);
1895 if (tslot != 0)
1896 break;
1897 }
1898 return ret;
1899 }
1900
1901 /*
1902 * update item key.
1903 *
1904 * This function isn't completely safe. It's the caller's responsibility
1905 * that the new key won't break the order
1906 */
1907 int btrfs_set_item_key_safe(struct btrfs_trans_handle *trans,
1908 struct btrfs_root *root, struct btrfs_path *path,
1909 struct btrfs_key *new_key)
1910 {
1911 struct btrfs_disk_key disk_key;
1912 struct extent_buffer *eb;
1913 int slot;
1914
1915 eb = path->nodes[0];
1916 slot = path->slots[0];
1917 if (slot > 0) {
1918 btrfs_item_key(eb, &disk_key, slot - 1);
1919 if (comp_keys(&disk_key, new_key) >= 0)
1920 return -1;
1921 }
1922 if (slot < btrfs_header_nritems(eb) - 1) {
1923 btrfs_item_key(eb, &disk_key, slot + 1);
1924 if (comp_keys(&disk_key, new_key) <= 0)
1925 return -1;
1926 }
1927
1928 btrfs_cpu_key_to_disk(&disk_key, new_key);
1929 btrfs_set_item_key(eb, &disk_key, slot);
1930 btrfs_mark_buffer_dirty(eb);
1931 if (slot == 0)
1932 fixup_low_keys(trans, root, path, &disk_key, 1);
1933 return 0;
1934 }
1935
1936 /*
1937 * try to push data from one node into the next node left in the
1938 * tree.
1939 *
1940 * returns 0 if some ptrs were pushed left, < 0 if there was some horrible
1941 * error, and > 0 if there was no room in the left hand block.
1942 */
1943 static int push_node_left(struct btrfs_trans_handle *trans,
1944 struct btrfs_root *root, struct extent_buffer *dst,
1945 struct extent_buffer *src, int empty)
1946 {
1947 int push_items = 0;
1948 int src_nritems;
1949 int dst_nritems;
1950 int ret = 0;
1951
1952 src_nritems = btrfs_header_nritems(src);
1953 dst_nritems = btrfs_header_nritems(dst);
1954 push_items = BTRFS_NODEPTRS_PER_BLOCK(root) - dst_nritems;
1955 WARN_ON(btrfs_header_generation(src) != trans->transid);
1956 WARN_ON(btrfs_header_generation(dst) != trans->transid);
1957
1958 if (!empty && src_nritems <= 8)
1959 return 1;
1960
1961 if (push_items <= 0)
1962 return 1;
1963
1964 if (empty) {
1965 push_items = min(src_nritems, push_items);
1966 if (push_items < src_nritems) {
1967 /* leave at least 8 pointers in the node if
1968 * we aren't going to empty it
1969 */
1970 if (src_nritems - push_items < 8) {
1971 if (push_items <= 8)
1972 return 1;
1973 push_items -= 8;
1974 }
1975 }
1976 } else
1977 push_items = min(src_nritems - 8, push_items);
1978
1979 copy_extent_buffer(dst, src,
1980 btrfs_node_key_ptr_offset(dst_nritems),
1981 btrfs_node_key_ptr_offset(0),
1982 push_items * sizeof(struct btrfs_key_ptr));
1983
1984 if (push_items < src_nritems) {
1985 memmove_extent_buffer(src, btrfs_node_key_ptr_offset(0),
1986 btrfs_node_key_ptr_offset(push_items),
1987 (src_nritems - push_items) *
1988 sizeof(struct btrfs_key_ptr));
1989 }
1990 btrfs_set_header_nritems(src, src_nritems - push_items);
1991 btrfs_set_header_nritems(dst, dst_nritems + push_items);
1992 btrfs_mark_buffer_dirty(src);
1993 btrfs_mark_buffer_dirty(dst);
1994
1995 ret = btrfs_update_ref(trans, root, src, dst, dst_nritems, push_items);
1996 BUG_ON(ret);
1997
1998 return ret;
1999 }
2000
2001 /*
2002 * try to push data from one node into the next node right in the
2003 * tree.
2004 *
2005 * returns 0 if some ptrs were pushed, < 0 if there was some horrible
2006 * error, and > 0 if there was no room in the right hand block.
2007 *
2008 * this will only push up to 1/2 the contents of the left node over
2009 */
2010 static int balance_node_right(struct btrfs_trans_handle *trans,
2011 struct btrfs_root *root,
2012 struct extent_buffer *dst,
2013 struct extent_buffer *src)
2014 {
2015 int push_items = 0;
2016 int max_push;
2017 int src_nritems;
2018 int dst_nritems;
2019 int ret = 0;
2020
2021 WARN_ON(btrfs_header_generation(src) != trans->transid);
2022 WARN_ON(btrfs_header_generation(dst) != trans->transid);
2023
2024 src_nritems = btrfs_header_nritems(src);
2025 dst_nritems = btrfs_header_nritems(dst);
2026 push_items = BTRFS_NODEPTRS_PER_BLOCK(root) - dst_nritems;
2027 if (push_items <= 0)
2028 return 1;
2029
2030 if (src_nritems < 4)
2031 return 1;
2032
2033 max_push = src_nritems / 2 + 1;
2034 /* don't try to empty the node */
2035 if (max_push >= src_nritems)
2036 return 1;
2037
2038 if (max_push < push_items)
2039 push_items = max_push;
2040
2041 memmove_extent_buffer(dst, btrfs_node_key_ptr_offset(push_items),
2042 btrfs_node_key_ptr_offset(0),
2043 (dst_nritems) *
2044 sizeof(struct btrfs_key_ptr));
2045
2046 copy_extent_buffer(dst, src,
2047 btrfs_node_key_ptr_offset(0),
2048 btrfs_node_key_ptr_offset(src_nritems - push_items),
2049 push_items * sizeof(struct btrfs_key_ptr));
2050
2051 btrfs_set_header_nritems(src, src_nritems - push_items);
2052 btrfs_set_header_nritems(dst, dst_nritems + push_items);
2053
2054 btrfs_mark_buffer_dirty(src);
2055 btrfs_mark_buffer_dirty(dst);
2056
2057 ret = btrfs_update_ref(trans, root, src, dst, 0, push_items);
2058 BUG_ON(ret);
2059
2060 return ret;
2061 }
2062
2063 /*
2064 * helper function to insert a new root level in the tree.
2065 * A new node is allocated, and a single item is inserted to
2066 * point to the existing root
2067 *
2068 * returns zero on success or < 0 on failure.
2069 */
2070 static noinline int insert_new_root(struct btrfs_trans_handle *trans,
2071 struct btrfs_root *root,
2072 struct btrfs_path *path, int level)
2073 {
2074 u64 lower_gen;
2075 struct extent_buffer *lower;
2076 struct extent_buffer *c;
2077 struct extent_buffer *old;
2078 struct btrfs_disk_key lower_key;
2079 int ret;
2080
2081 BUG_ON(path->nodes[level]);
2082 BUG_ON(path->nodes[level-1] != root->node);
2083
2084 lower = path->nodes[level-1];
2085 if (level == 1)
2086 btrfs_item_key(lower, &lower_key, 0);
2087 else
2088 btrfs_node_key(lower, &lower_key, 0);
2089
2090 c = btrfs_alloc_free_block(trans, root, root->nodesize, 0,
2091 root->root_key.objectid, trans->transid,
2092 level, root->node->start, 0);
2093 if (IS_ERR(c))
2094 return PTR_ERR(c);
2095
2096 memset_extent_buffer(c, 0, 0, root->nodesize);
2097 btrfs_set_header_nritems(c, 1);
2098 btrfs_set_header_level(c, level);
2099 btrfs_set_header_bytenr(c, c->start);
2100 btrfs_set_header_generation(c, trans->transid);
2101 btrfs_set_header_owner(c, root->root_key.objectid);
2102
2103 write_extent_buffer(c, root->fs_info->fsid,
2104 (unsigned long)btrfs_header_fsid(c),
2105 BTRFS_FSID_SIZE);
2106
2107 write_extent_buffer(c, root->fs_info->chunk_tree_uuid,
2108 (unsigned long)btrfs_header_chunk_tree_uuid(c),
2109 BTRFS_UUID_SIZE);
2110
2111 btrfs_set_node_key(c, &lower_key, 0);
2112 btrfs_set_node_blockptr(c, 0, lower->start);
2113 lower_gen = btrfs_header_generation(lower);
2114 WARN_ON(lower_gen != trans->transid);
2115
2116 btrfs_set_node_ptr_generation(c, 0, lower_gen);
2117
2118 btrfs_mark_buffer_dirty(c);
2119
2120 spin_lock(&root->node_lock);
2121 old = root->node;
2122 root->node = c;
2123 spin_unlock(&root->node_lock);
2124
2125 ret = btrfs_update_extent_ref(trans, root, lower->start,
2126 lower->start, c->start,
2127 root->root_key.objectid,
2128 trans->transid, level - 1);
2129 BUG_ON(ret);
2130
2131 /* the super has an extra ref to root->node */
2132 free_extent_buffer(old);
2133
2134 add_root_to_dirty_list(root);
2135 extent_buffer_get(c);
2136 path->nodes[level] = c;
2137 path->locks[level] = 1;
2138 path->slots[level] = 0;
2139 return 0;
2140 }
2141
2142 /*
2143 * worker function to insert a single pointer in a node.
2144 * the node should have enough room for the pointer already
2145 *
2146 * slot and level indicate where you want the key to go, and
2147 * blocknr is the block the key points to.
2148 *
2149 * returns zero on success and < 0 on any error
2150 */
2151 static int insert_ptr(struct btrfs_trans_handle *trans, struct btrfs_root
2152 *root, struct btrfs_path *path, struct btrfs_disk_key
2153 *key, u64 bytenr, int slot, int level)
2154 {
2155 struct extent_buffer *lower;
2156 int nritems;
2157
2158 BUG_ON(!path->nodes[level]);
2159 lower = path->nodes[level];
2160 nritems = btrfs_header_nritems(lower);
2161 if (slot > nritems)
2162 BUG();
2163 if (nritems == BTRFS_NODEPTRS_PER_BLOCK(root))
2164 BUG();
2165 if (slot != nritems) {
2166 memmove_extent_buffer(lower,
2167 btrfs_node_key_ptr_offset(slot + 1),
2168 btrfs_node_key_ptr_offset(slot),
2169 (nritems - slot) * sizeof(struct btrfs_key_ptr));
2170 }
2171 btrfs_set_node_key(lower, key, slot);
2172 btrfs_set_node_blockptr(lower, slot, bytenr);
2173 WARN_ON(trans->transid == 0);
2174 btrfs_set_node_ptr_generation(lower, slot, trans->transid);
2175 btrfs_set_header_nritems(lower, nritems + 1);
2176 btrfs_mark_buffer_dirty(lower);
2177 return 0;
2178 }
2179
2180 /*
2181 * split the node at the specified level in path in two.
2182 * The path is corrected to point to the appropriate node after the split
2183 *
2184 * Before splitting this tries to make some room in the node by pushing
2185 * left and right, if either one works, it returns right away.
2186 *
2187 * returns 0 on success and < 0 on failure
2188 */
2189 static noinline int split_node(struct btrfs_trans_handle *trans,
2190 struct btrfs_root *root,
2191 struct btrfs_path *path, int level)
2192 {
2193 struct extent_buffer *c;
2194 struct extent_buffer *split;
2195 struct btrfs_disk_key disk_key;
2196 int mid;
2197 int ret;
2198 int wret;
2199 u32 c_nritems;
2200
2201 c = path->nodes[level];
2202 WARN_ON(btrfs_header_generation(c) != trans->transid);
2203 if (c == root->node) {
2204 /* trying to split the root, lets make a new one */
2205 ret = insert_new_root(trans, root, path, level + 1);
2206 if (ret)
2207 return ret;
2208 } else {
2209 ret = push_nodes_for_insert(trans, root, path, level);
2210 c = path->nodes[level];
2211 if (!ret && btrfs_header_nritems(c) <
2212 BTRFS_NODEPTRS_PER_BLOCK(root) - 3)
2213 return 0;
2214 if (ret < 0)
2215 return ret;
2216 }
2217
2218 c_nritems = btrfs_header_nritems(c);
2219
2220 split = btrfs_alloc_free_block(trans, root, root->nodesize,
2221 path->nodes[level + 1]->start,
2222 root->root_key.objectid,
2223 trans->transid, level, c->start, 0);
2224 if (IS_ERR(split))
2225 return PTR_ERR(split);
2226
2227 btrfs_set_header_flags(split, btrfs_header_flags(c));
2228 btrfs_set_header_level(split, btrfs_header_level(c));
2229 btrfs_set_header_bytenr(split, split->start);
2230 btrfs_set_header_generation(split, trans->transid);
2231 btrfs_set_header_owner(split, root->root_key.objectid);
2232 btrfs_set_header_flags(split, 0);
2233 write_extent_buffer(split, root->fs_info->fsid,
2234 (unsigned long)btrfs_header_fsid(split),
2235 BTRFS_FSID_SIZE);
2236 write_extent_buffer(split, root->fs_info->chunk_tree_uuid,
2237 (unsigned long)btrfs_header_chunk_tree_uuid(split),
2238 BTRFS_UUID_SIZE);
2239
2240 mid = (c_nritems + 1) / 2;
2241
2242 copy_extent_buffer(split, c,
2243 btrfs_node_key_ptr_offset(0),
2244 btrfs_node_key_ptr_offset(mid),
2245 (c_nritems - mid) * sizeof(struct btrfs_key_ptr));
2246 btrfs_set_header_nritems(split, c_nritems - mid);
2247 btrfs_set_header_nritems(c, mid);
2248 ret = 0;
2249
2250 btrfs_mark_buffer_dirty(c);
2251 btrfs_mark_buffer_dirty(split);
2252
2253 btrfs_node_key(split, &disk_key, 0);
2254 wret = insert_ptr(trans, root, path, &disk_key, split->start,
2255 path->slots[level + 1] + 1,
2256 level + 1);
2257 if (wret)
2258 ret = wret;
2259
2260 ret = btrfs_update_ref(trans, root, c, split, 0, c_nritems - mid);
2261 BUG_ON(ret);
2262
2263 if (path->slots[level] >= mid) {
2264 path->slots[level] -= mid;
2265 btrfs_tree_unlock(c);
2266 free_extent_buffer(c);
2267 path->nodes[level] = split;
2268 path->slots[level + 1] += 1;
2269 } else {
2270 btrfs_tree_unlock(split);
2271 free_extent_buffer(split);
2272 }
2273 return ret;
2274 }
2275
2276 /*
2277 * how many bytes are required to store the items in a leaf. start
2278 * and nr indicate which items in the leaf to check. This totals up the
2279 * space used both by the item structs and the item data
2280 */
2281 static int leaf_space_used(struct extent_buffer *l, int start, int nr)
2282 {
2283 int data_len;
2284 int nritems = btrfs_header_nritems(l);
2285 int end = min(nritems, start + nr) - 1;
2286
2287 if (!nr)
2288 return 0;
2289 data_len = btrfs_item_end_nr(l, start);
2290 data_len = data_len - btrfs_item_offset_nr(l, end);
2291 data_len += sizeof(struct btrfs_item) * nr;
2292 WARN_ON(data_len < 0);
2293 return data_len;
2294 }
2295
2296 /*
2297 * The space between the end of the leaf items and
2298 * the start of the leaf data. IOW, how much room
2299 * the leaf has left for both items and data
2300 */
2301 noinline int btrfs_leaf_free_space(struct btrfs_root *root,
2302 struct extent_buffer *leaf)
2303 {
2304 int nritems = btrfs_header_nritems(leaf);
2305 int ret;
2306 ret = BTRFS_LEAF_DATA_SIZE(root) - leaf_space_used(leaf, 0, nritems);
2307 if (ret < 0) {
2308 printk(KERN_CRIT "leaf free space ret %d, leaf data size %lu, "
2309 "used %d nritems %d\n",
2310 ret, (unsigned long) BTRFS_LEAF_DATA_SIZE(root),
2311 leaf_space_used(leaf, 0, nritems), nritems);
2312 }
2313 return ret;
2314 }
2315
2316 /*
2317 * push some data in the path leaf to the right, trying to free up at
2318 * least data_size bytes. returns zero if the push worked, nonzero otherwise
2319 *
2320 * returns 1 if the push failed because the other node didn't have enough
2321 * room, 0 if everything worked out and < 0 if there were major errors.
2322 */
2323 static int push_leaf_right(struct btrfs_trans_handle *trans, struct btrfs_root
2324 *root, struct btrfs_path *path, int data_size,
2325 int empty)
2326 {
2327 struct extent_buffer *left = path->nodes[0];
2328 struct extent_buffer *right;
2329 struct extent_buffer *upper;
2330 struct btrfs_disk_key disk_key;
2331 int slot;
2332 u32 i;
2333 int free_space;
2334 int push_space = 0;
2335 int push_items = 0;
2336 struct btrfs_item *item;
2337 u32 left_nritems;
2338 u32 nr;
2339 u32 right_nritems;
2340 u32 data_end;
2341 u32 this_item_size;
2342 int ret;
2343
2344 slot = path->slots[1];
2345 if (!path->nodes[1])
2346 return 1;
2347
2348 upper = path->nodes[1];
2349 if (slot >= btrfs_header_nritems(upper) - 1)
2350 return 1;
2351
2352 WARN_ON(!btrfs_tree_locked(path->nodes[1]));
2353
2354 right = read_node_slot(root, upper, slot + 1);
2355 btrfs_tree_lock(right);
2356 btrfs_set_lock_blocking(right);
2357
2358 free_space = btrfs_leaf_free_space(root, right);
2359 if (free_space < data_size)
2360 goto out_unlock;
2361
2362 /* cow and double check */
2363 ret = btrfs_cow_block(trans, root, right, upper,
2364 slot + 1, &right, 0);
2365 if (ret)
2366 goto out_unlock;
2367
2368 free_space = btrfs_leaf_free_space(root, right);
2369 if (free_space < data_size)
2370 goto out_unlock;
2371
2372 left_nritems = btrfs_header_nritems(left);
2373 if (left_nritems == 0)
2374 goto out_unlock;
2375
2376 if (empty)
2377 nr = 0;
2378 else
2379 nr = 1;
2380
2381 if (path->slots[0] >= left_nritems)
2382 push_space += data_size;
2383
2384 i = left_nritems - 1;
2385 while (i >= nr) {
2386 item = btrfs_item_nr(left, i);
2387
2388 if (!empty && push_items > 0) {
2389 if (path->slots[0] > i)
2390 break;
2391 if (path->slots[0] == i) {
2392 int space = btrfs_leaf_free_space(root, left);
2393 if (space + push_space * 2 > free_space)
2394 break;
2395 }
2396 }
2397
2398 if (path->slots[0] == i)
2399 push_space += data_size;
2400
2401 if (!left->map_token) {
2402 map_extent_buffer(left, (unsigned long)item,
2403 sizeof(struct btrfs_item),
2404 &left->map_token, &left->kaddr,
2405 &left->map_start, &left->map_len,
2406 KM_USER1);
2407 }
2408
2409 this_item_size = btrfs_item_size(left, item);
2410 if (this_item_size + sizeof(*item) + push_space > free_space)
2411 break;
2412
2413 push_items++;
2414 push_space += this_item_size + sizeof(*item);
2415 if (i == 0)
2416 break;
2417 i--;
2418 }
2419 if (left->map_token) {
2420 unmap_extent_buffer(left, left->map_token, KM_USER1);
2421 left->map_token = NULL;
2422 }
2423
2424 if (push_items == 0)
2425 goto out_unlock;
2426
2427 if (!empty && push_items == left_nritems)
2428 WARN_ON(1);
2429
2430 /* push left to right */
2431 right_nritems = btrfs_header_nritems(right);
2432
2433 push_space = btrfs_item_end_nr(left, left_nritems - push_items);
2434 push_space -= leaf_data_end(root, left);
2435
2436 /* make room in the right data area */
2437 data_end = leaf_data_end(root, right);
2438 memmove_extent_buffer(right,
2439 btrfs_leaf_data(right) + data_end - push_space,
2440 btrfs_leaf_data(right) + data_end,
2441 BTRFS_LEAF_DATA_SIZE(root) - data_end);
2442
2443 /* copy from the left data area */
2444 copy_extent_buffer(right, left, btrfs_leaf_data(right) +
2445 BTRFS_LEAF_DATA_SIZE(root) - push_space,
2446 btrfs_leaf_data(left) + leaf_data_end(root, left),
2447 push_space);
2448
2449 memmove_extent_buffer(right, btrfs_item_nr_offset(push_items),
2450 btrfs_item_nr_offset(0),
2451 right_nritems * sizeof(struct btrfs_item));
2452
2453 /* copy the items from left to right */
2454 copy_extent_buffer(right, left, btrfs_item_nr_offset(0),
2455 btrfs_item_nr_offset(left_nritems - push_items),
2456 push_items * sizeof(struct btrfs_item));
2457
2458 /* update the item pointers */
2459 right_nritems += push_items;
2460 btrfs_set_header_nritems(right, right_nritems);
2461 push_space = BTRFS_LEAF_DATA_SIZE(root);
2462 for (i = 0; i < right_nritems; i++) {
2463 item = btrfs_item_nr(right, i);
2464 if (!right->map_token) {
2465 map_extent_buffer(right, (unsigned long)item,
2466 sizeof(struct btrfs_item),
2467 &right->map_token, &right->kaddr,
2468 &right->map_start, &right->map_len,
2469 KM_USER1);
2470 }
2471 push_space -= btrfs_item_size(right, item);
2472 btrfs_set_item_offset(right, item, push_space);
2473 }
2474
2475 if (right->map_token) {
2476 unmap_extent_buffer(right, right->map_token, KM_USER1);
2477 right->map_token = NULL;
2478 }
2479 left_nritems -= push_items;
2480 btrfs_set_header_nritems(left, left_nritems);
2481
2482 if (left_nritems)
2483 btrfs_mark_buffer_dirty(left);
2484 btrfs_mark_buffer_dirty(right);
2485
2486 ret = btrfs_update_ref(trans, root, left, right, 0, push_items);
2487 BUG_ON(ret);
2488
2489 btrfs_item_key(right, &disk_key, 0);
2490 btrfs_set_node_key(upper, &disk_key, slot + 1);
2491 btrfs_mark_buffer_dirty(upper);
2492
2493 /* then fixup the leaf pointer in the path */
2494 if (path->slots[0] >= left_nritems) {
2495 path->slots[0] -= left_nritems;
2496 if (btrfs_header_nritems(path->nodes[0]) == 0)
2497 clean_tree_block(trans, root, path->nodes[0]);
2498 btrfs_tree_unlock(path->nodes[0]);
2499 free_extent_buffer(path->nodes[0]);
2500 path->nodes[0] = right;
2501 path->slots[1] += 1;
2502 } else {
2503 btrfs_tree_unlock(right);
2504 free_extent_buffer(right);
2505 }
2506 return 0;
2507
2508 out_unlock:
2509 btrfs_tree_unlock(right);
2510 free_extent_buffer(right);
2511 return 1;
2512 }
2513
2514 /*
2515 * push some data in the path leaf to the left, trying to free up at
2516 * least data_size bytes. returns zero if the push worked, nonzero otherwise
2517 */
2518 static int push_leaf_left(struct btrfs_trans_handle *trans, struct btrfs_root
2519 *root, struct btrfs_path *path, int data_size,
2520 int empty)
2521 {
2522 struct btrfs_disk_key disk_key;
2523 struct extent_buffer *right = path->nodes[0];
2524 struct extent_buffer *left;
2525 int slot;
2526 int i;
2527 int free_space;
2528 int push_space = 0;
2529 int push_items = 0;
2530 struct btrfs_item *item;
2531 u32 old_left_nritems;
2532 u32 right_nritems;
2533 u32 nr;
2534 int ret = 0;
2535 int wret;
2536 u32 this_item_size;
2537 u32 old_left_item_size;
2538
2539 slot = path->slots[1];
2540 if (slot == 0)
2541 return 1;
2542 if (!path->nodes[1])
2543 return 1;
2544
2545 right_nritems = btrfs_header_nritems(right);
2546 if (right_nritems == 0)
2547 return 1;
2548
2549 WARN_ON(!btrfs_tree_locked(path->nodes[1]));
2550
2551 left = read_node_slot(root, path->nodes[1], slot - 1);
2552 btrfs_tree_lock(left);
2553 btrfs_set_lock_blocking(left);
2554
2555 free_space = btrfs_leaf_free_space(root, left);
2556 if (free_space < data_size) {
2557 ret = 1;
2558 goto out;
2559 }
2560
2561 /* cow and double check */
2562 ret = btrfs_cow_block(trans, root, left,
2563 path->nodes[1], slot - 1, &left, 0);
2564 if (ret) {
2565 /* we hit -ENOSPC, but it isn't fatal here */
2566 ret = 1;
2567 goto out;
2568 }
2569
2570 free_space = btrfs_leaf_free_space(root, left);
2571 if (free_space < data_size) {
2572 ret = 1;
2573 goto out;
2574 }
2575
2576 if (empty)
2577 nr = right_nritems;
2578 else
2579 nr = right_nritems - 1;
2580
2581 for (i = 0; i < nr; i++) {
2582 item = btrfs_item_nr(right, i);
2583 if (!right->map_token) {
2584 map_extent_buffer(right, (unsigned long)item,
2585 sizeof(struct btrfs_item),
2586 &right->map_token, &right->kaddr,
2587 &right->map_start, &right->map_len,
2588 KM_USER1);
2589 }
2590
2591 if (!empty && push_items > 0) {
2592 if (path->slots[0] < i)
2593 break;
2594 if (path->slots[0] == i) {
2595 int space = btrfs_leaf_free_space(root, right);
2596 if (space + push_space * 2 > free_space)
2597 break;
2598 }
2599 }
2600
2601 if (path->slots[0] == i)
2602 push_space += data_size;
2603
2604 this_item_size = btrfs_item_size(right, item);
2605 if (this_item_size + sizeof(*item) + push_space > free_space)
2606 break;
2607
2608 push_items++;
2609 push_space += this_item_size + sizeof(*item);
2610 }
2611
2612 if (right->map_token) {
2613 unmap_extent_buffer(right, right->map_token, KM_USER1);
2614 right->map_token = NULL;
2615 }
2616
2617 if (push_items == 0) {
2618 ret = 1;
2619 goto out;
2620 }
2621 if (!empty && push_items == btrfs_header_nritems(right))
2622 WARN_ON(1);
2623
2624 /* push data from right to left */
2625 copy_extent_buffer(left, right,
2626 btrfs_item_nr_offset(btrfs_header_nritems(left)),
2627 btrfs_item_nr_offset(0),
2628 push_items * sizeof(struct btrfs_item));
2629
2630 push_space = BTRFS_LEAF_DATA_SIZE(root) -
2631 btrfs_item_offset_nr(right, push_items - 1);
2632
2633 copy_extent_buffer(left, right, btrfs_leaf_data(left) +
2634 leaf_data_end(root, left) - push_space,
2635 btrfs_leaf_data(right) +
2636 btrfs_item_offset_nr(right, push_items - 1),
2637 push_space);
2638 old_left_nritems = btrfs_header_nritems(left);
2639 BUG_ON(old_left_nritems <= 0);
2640
2641 old_left_item_size = btrfs_item_offset_nr(left, old_left_nritems - 1);
2642 for (i = old_left_nritems; i < old_left_nritems + push_items; i++) {
2643 u32 ioff;
2644
2645 item = btrfs_item_nr(left, i);
2646 if (!left->map_token) {
2647 map_extent_buffer(left, (unsigned long)item,
2648 sizeof(struct btrfs_item),
2649 &left->map_token, &left->kaddr,
2650 &left->map_start, &left->map_len,
2651 KM_USER1);
2652 }
2653
2654 ioff = btrfs_item_offset(left, item);
2655 btrfs_set_item_offset(left, item,
2656 ioff - (BTRFS_LEAF_DATA_SIZE(root) - old_left_item_size));
2657 }
2658 btrfs_set_header_nritems(left, old_left_nritems + push_items);
2659 if (left->map_token) {
2660 unmap_extent_buffer(left, left->map_token, KM_USER1);
2661 left->map_token = NULL;
2662 }
2663
2664 /* fixup right node */
2665 if (push_items > right_nritems) {
2666 printk(KERN_CRIT "push items %d nr %u\n", push_items,
2667 right_nritems);
2668 WARN_ON(1);
2669 }
2670
2671 if (push_items < right_nritems) {
2672 push_space = btrfs_item_offset_nr(right, push_items - 1) -
2673 leaf_data_end(root, right);
2674 memmove_extent_buffer(right, btrfs_leaf_data(right) +
2675 BTRFS_LEAF_DATA_SIZE(root) - push_space,
2676 btrfs_leaf_data(right) +
2677 leaf_data_end(root, right), push_space);
2678
2679 memmove_extent_buffer(right, btrfs_item_nr_offset(0),
2680 btrfs_item_nr_offset(push_items),
2681 (btrfs_header_nritems(right) - push_items) *
2682 sizeof(struct btrfs_item));
2683 }
2684 right_nritems -= push_items;
2685 btrfs_set_header_nritems(right, right_nritems);
2686 push_space = BTRFS_LEAF_DATA_SIZE(root);
2687 for (i = 0; i < right_nritems; i++) {
2688 item = btrfs_item_nr(right, i);
2689
2690 if (!right->map_token) {
2691 map_extent_buffer(right, (unsigned long)item,
2692 sizeof(struct btrfs_item),
2693 &right->map_token, &right->kaddr,
2694 &right->map_start, &right->map_len,
2695 KM_USER1);
2696 }
2697
2698 push_space = push_space - btrfs_item_size(right, item);
2699 btrfs_set_item_offset(right, item, push_space);
2700 }
2701 if (right->map_token) {
2702 unmap_extent_buffer(right, right->map_token, KM_USER1);
2703 right->map_token = NULL;
2704 }
2705
2706 btrfs_mark_buffer_dirty(left);
2707 if (right_nritems)
2708 btrfs_mark_buffer_dirty(right);
2709
2710 ret = btrfs_update_ref(trans, root, right, left,
2711 old_left_nritems, push_items);
2712 BUG_ON(ret);
2713
2714 btrfs_item_key(right, &disk_key, 0);
2715 wret = fixup_low_keys(trans, root, path, &disk_key, 1);
2716 if (wret)
2717 ret = wret;
2718
2719 /* then fixup the leaf pointer in the path */
2720 if (path->slots[0] < push_items) {
2721 path->slots[0] += old_left_nritems;
2722 if (btrfs_header_nritems(path->nodes[0]) == 0)
2723 clean_tree_block(trans, root, path->nodes[0]);
2724 btrfs_tree_unlock(path->nodes[0]);
2725 free_extent_buffer(path->nodes[0]);
2726 path->nodes[0] = left;
2727 path->slots[1] -= 1;
2728 } else {
2729 btrfs_tree_unlock(left);
2730 free_extent_buffer(left);
2731 path->slots[0] -= push_items;
2732 }
2733 BUG_ON(path->slots[0] < 0);
2734 return ret;
2735 out:
2736 btrfs_tree_unlock(left);
2737 free_extent_buffer(left);
2738 return ret;
2739 }
2740
2741 /*
2742 * split the path's leaf in two, making sure there is at least data_size
2743 * available for the resulting leaf level of the path.
2744 *
2745 * returns 0 if all went well and < 0 on failure.
2746 */
2747 static noinline int split_leaf(struct btrfs_trans_handle *trans,
2748 struct btrfs_root *root,
2749 struct btrfs_key *ins_key,
2750 struct btrfs_path *path, int data_size,
2751 int extend)
2752 {
2753 struct extent_buffer *l;
2754 u32 nritems;
2755 int mid;
2756 int slot;
2757 struct extent_buffer *right;
2758 int data_copy_size;
2759 int rt_data_off;
2760 int i;
2761 int ret = 0;
2762 int wret;
2763 int double_split;
2764 int num_doubles = 0;
2765 struct btrfs_disk_key disk_key;
2766
2767 /* first try to make some room by pushing left and right */
2768 if (data_size && ins_key->type != BTRFS_DIR_ITEM_KEY) {
2769 wret = push_leaf_right(trans, root, path, data_size, 0);
2770 if (wret < 0)
2771 return wret;
2772 if (wret) {
2773 wret = push_leaf_left(trans, root, path, data_size, 0);
2774 if (wret < 0)
2775 return wret;
2776 }
2777 l = path->nodes[0];
2778
2779 /* did the pushes work? */
2780 if (btrfs_leaf_free_space(root, l) >= data_size)
2781 return 0;
2782 }
2783
2784 if (!path->nodes[1]) {
2785 ret = insert_new_root(trans, root, path, 1);
2786 if (ret)
2787 return ret;
2788 }
2789 again:
2790 double_split = 0;
2791 l = path->nodes[0];
2792 slot = path->slots[0];
2793 nritems = btrfs_header_nritems(l);
2794 mid = (nritems + 1) / 2;
2795
2796 right = btrfs_alloc_free_block(trans, root, root->leafsize,
2797 path->nodes[1]->start,
2798 root->root_key.objectid,
2799 trans->transid, 0, l->start, 0);
2800 if (IS_ERR(right)) {
2801 BUG_ON(1);
2802 return PTR_ERR(right);
2803 }
2804
2805 memset_extent_buffer(right, 0, 0, sizeof(struct btrfs_header));
2806 btrfs_set_header_bytenr(right, right->start);
2807 btrfs_set_header_generation(right, trans->transid);
2808 btrfs_set_header_owner(right, root->root_key.objectid);
2809 btrfs_set_header_level(right, 0);
2810 write_extent_buffer(right, root->fs_info->fsid,
2811 (unsigned long)btrfs_header_fsid(right),
2812 BTRFS_FSID_SIZE);
2813
2814 write_extent_buffer(right, root->fs_info->chunk_tree_uuid,
2815 (unsigned long)btrfs_header_chunk_tree_uuid(right),
2816 BTRFS_UUID_SIZE);
2817 if (mid <= slot) {
2818 if (nritems == 1 ||
2819 leaf_space_used(l, mid, nritems - mid) + data_size >
2820 BTRFS_LEAF_DATA_SIZE(root)) {
2821 if (slot >= nritems) {
2822 btrfs_cpu_key_to_disk(&disk_key, ins_key);
2823 btrfs_set_header_nritems(right, 0);
2824 wret = insert_ptr(trans, root, path,
2825 &disk_key, right->start,
2826 path->slots[1] + 1, 1);
2827 if (wret)
2828 ret = wret;
2829
2830 btrfs_tree_unlock(path->nodes[0]);
2831 free_extent_buffer(path->nodes[0]);
2832 path->nodes[0] = right;
2833 path->slots[0] = 0;
2834 path->slots[1] += 1;
2835 btrfs_mark_buffer_dirty(right);
2836 return ret;
2837 }
2838 mid = slot;
2839 if (mid != nritems &&
2840 leaf_space_used(l, mid, nritems - mid) +
2841 data_size > BTRFS_LEAF_DATA_SIZE(root)) {
2842 double_split = 1;
2843 }
2844 }
2845 } else {
2846 if (leaf_space_used(l, 0, mid) + data_size >
2847 BTRFS_LEAF_DATA_SIZE(root)) {
2848 if (!extend && data_size && slot == 0) {
2849 btrfs_cpu_key_to_disk(&disk_key, ins_key);
2850 btrfs_set_header_nritems(right, 0);
2851 wret = insert_ptr(trans, root, path,
2852 &disk_key,
2853 right->start,
2854 path->slots[1], 1);
2855 if (wret)
2856 ret = wret;
2857 btrfs_tree_unlock(path->nodes[0]);
2858 free_extent_buffer(path->nodes[0]);
2859 path->nodes[0] = right;
2860 path->slots[0] = 0;
2861 if (path->slots[1] == 0) {
2862 wret = fixup_low_keys(trans, root,
2863 path, &disk_key, 1);
2864 if (wret)
2865 ret = wret;
2866 }
2867 btrfs_mark_buffer_dirty(right);
2868 return ret;
2869 } else if ((extend || !data_size) && slot == 0) {
2870 mid = 1;
2871 } else {
2872 mid = slot;
2873 if (mid != nritems &&
2874 leaf_space_used(l, mid, nritems - mid) +
2875 data_size > BTRFS_LEAF_DATA_SIZE(root)) {
2876 double_split = 1;
2877 }
2878 }
2879 }
2880 }
2881 nritems = nritems - mid;
2882 btrfs_set_header_nritems(right, nritems);
2883 data_copy_size = btrfs_item_end_nr(l, mid) - leaf_data_end(root, l);
2884
2885 copy_extent_buffer(right, l, btrfs_item_nr_offset(0),
2886 btrfs_item_nr_offset(mid),
2887 nritems * sizeof(struct btrfs_item));
2888
2889 copy_extent_buffer(right, l,
2890 btrfs_leaf_data(right) + BTRFS_LEAF_DATA_SIZE(root) -
2891 data_copy_size, btrfs_leaf_data(l) +
2892 leaf_data_end(root, l), data_copy_size);
2893
2894 rt_data_off = BTRFS_LEAF_DATA_SIZE(root) -
2895 btrfs_item_end_nr(l, mid);
2896
2897 for (i = 0; i < nritems; i++) {
2898 struct btrfs_item *item = btrfs_item_nr(right, i);
2899 u32 ioff;
2900
2901 if (!right->map_token) {
2902 map_extent_buffer(right, (unsigned long)item,
2903 sizeof(struct btrfs_item),
2904 &right->map_token, &right->kaddr,
2905 &right->map_start, &right->map_len,
2906 KM_USER1);
2907 }
2908
2909 ioff = btrfs_item_offset(right, item);
2910 btrfs_set_item_offset(right, item, ioff + rt_data_off);
2911 }
2912
2913 if (right->map_token) {
2914 unmap_extent_buffer(right, right->map_token, KM_USER1);
2915 right->map_token = NULL;
2916 }
2917
2918 btrfs_set_header_nritems(l, mid);
2919 ret = 0;
2920 btrfs_item_key(right, &disk_key, 0);
2921 wret = insert_ptr(trans, root, path, &disk_key, right->start,
2922 path->slots[1] + 1, 1);
2923 if (wret)
2924 ret = wret;
2925
2926 btrfs_mark_buffer_dirty(right);
2927 btrfs_mark_buffer_dirty(l);
2928 BUG_ON(path->slots[0] != slot);
2929
2930 ret = btrfs_update_ref(trans, root, l, right, 0, nritems);
2931 BUG_ON(ret);
2932
2933 if (mid <= slot) {
2934 btrfs_tree_unlock(path->nodes[0]);
2935 free_extent_buffer(path->nodes[0]);
2936 path->nodes[0] = right;
2937 path->slots[0] -= mid;
2938 path->slots[1] += 1;
2939 } else {
2940 btrfs_tree_unlock(right);
2941 free_extent_buffer(right);
2942 }
2943
2944 BUG_ON(path->slots[0] < 0);
2945
2946 if (double_split) {
2947 BUG_ON(num_doubles != 0);
2948 num_doubles++;
2949 goto again;
2950 }
2951 return ret;
2952 }
2953
2954 /*
2955 * This function splits a single item into two items,
2956 * giving 'new_key' to the new item and splitting the
2957 * old one at split_offset (from the start of the item).
2958 *
2959 * The path may be released by this operation. After
2960 * the split, the path is pointing to the old item. The
2961 * new item is going to be in the same node as the old one.
2962 *
2963 * Note, the item being split must be smaller enough to live alone on
2964 * a tree block with room for one extra struct btrfs_item
2965 *
2966 * This allows us to split the item in place, keeping a lock on the
2967 * leaf the entire time.
2968 */
2969 int btrfs_split_item(struct btrfs_trans_handle *trans,
2970 struct btrfs_root *root,
2971 struct btrfs_path *path,
2972 struct btrfs_key *new_key,
2973 unsigned long split_offset)
2974 {
2975 u32 item_size;
2976 struct extent_buffer *leaf;
2977 struct btrfs_key orig_key;
2978 struct btrfs_item *item;
2979 struct btrfs_item *new_item;
2980 int ret = 0;
2981 int slot;
2982 u32 nritems;
2983 u32 orig_offset;
2984 struct btrfs_disk_key disk_key;
2985 char *buf;
2986
2987 leaf = path->nodes[0];
2988 btrfs_item_key_to_cpu(leaf, &orig_key, path->slots[0]);
2989 if (btrfs_leaf_free_space(root, leaf) >= sizeof(struct btrfs_item))
2990 goto split;
2991
2992 item_size = btrfs_item_size_nr(leaf, path->slots[0]);
2993 btrfs_release_path(root, path);
2994
2995 path->search_for_split = 1;
2996 path->keep_locks = 1;
2997
2998 ret = btrfs_search_slot(trans, root, &orig_key, path, 0, 1);
2999 path->search_for_split = 0;
3000
3001 /* if our item isn't there or got smaller, return now */
3002 if (ret != 0 || item_size != btrfs_item_size_nr(path->nodes[0],
3003 path->slots[0])) {
3004 path->keep_locks = 0;
3005 return -EAGAIN;
3006 }
3007
3008 ret = split_leaf(trans, root, &orig_key, path,
3009 sizeof(struct btrfs_item), 1);
3010 path->keep_locks = 0;
3011 BUG_ON(ret);
3012
3013 /*
3014 * make sure any changes to the path from split_leaf leave it
3015 * in a blocking state
3016 */
3017 btrfs_set_path_blocking(path);
3018
3019 leaf = path->nodes[0];
3020 BUG_ON(btrfs_leaf_free_space(root, leaf) < sizeof(struct btrfs_item));
3021
3022 split:
3023 item = btrfs_item_nr(leaf, path->slots[0]);
3024 orig_offset = btrfs_item_offset(leaf, item);
3025 item_size = btrfs_item_size(leaf, item);
3026
3027
3028 buf = kmalloc(item_size, GFP_NOFS);
3029 read_extent_buffer(leaf, buf, btrfs_item_ptr_offset(leaf,
3030 path->slots[0]), item_size);
3031 slot = path->slots[0] + 1;
3032 leaf = path->nodes[0];
3033
3034 nritems = btrfs_header_nritems(leaf);
3035
3036 if (slot != nritems) {
3037 /* shift the items */
3038 memmove_extent_buffer(leaf, btrfs_item_nr_offset(slot + 1),
3039 btrfs_item_nr_offset(slot),
3040 (nritems - slot) * sizeof(struct btrfs_item));
3041
3042 }
3043
3044 btrfs_cpu_key_to_disk(&disk_key, new_key);
3045 btrfs_set_item_key(leaf, &disk_key, slot);
3046
3047 new_item = btrfs_item_nr(leaf, slot);
3048
3049 btrfs_set_item_offset(leaf, new_item, orig_offset);
3050 btrfs_set_item_size(leaf, new_item, item_size - split_offset);
3051
3052 btrfs_set_item_offset(leaf, item,
3053 orig_offset + item_size - split_offset);
3054 btrfs_set_item_size(leaf, item, split_offset);
3055
3056 btrfs_set_header_nritems(leaf, nritems + 1);
3057
3058 /* write the data for the start of the original item */
3059 write_extent_buffer(leaf, buf,
3060 btrfs_item_ptr_offset(leaf, path->slots[0]),
3061 split_offset);
3062
3063 /* write the data for the new item */
3064 write_extent_buffer(leaf, buf + split_offset,
3065 btrfs_item_ptr_offset(leaf, slot),
3066 item_size - split_offset);
3067 btrfs_mark_buffer_dirty(leaf);
3068
3069 ret = 0;
3070 if (btrfs_leaf_free_space(root, leaf) < 0) {
3071 btrfs_print_leaf(root, leaf);
3072 BUG();
3073 }
3074 kfree(buf);
3075 return ret;
3076 }
3077
3078 /*
3079 * make the item pointed to by the path smaller. new_size indicates
3080 * how small to make it, and from_end tells us if we just chop bytes
3081 * off the end of the item or if we shift the item to chop bytes off
3082 * the front.
3083 */
3084 int btrfs_truncate_item(struct btrfs_trans_handle *trans,
3085 struct btrfs_root *root,
3086 struct btrfs_path *path,
3087 u32 new_size, int from_end)
3088 {
3089 int ret = 0;
3090 int slot;
3091 int slot_orig;
3092 struct extent_buffer *leaf;
3093 struct btrfs_item *item;
3094 u32 nritems;
3095 unsigned int data_end;
3096 unsigned int old_data_start;
3097 unsigned int old_size;
3098 unsigned int size_diff;
3099 int i;
3100
3101 slot_orig = path->slots[0];
3102 leaf = path->nodes[0];
3103 slot = path->slots[0];
3104
3105 old_size = btrfs_item_size_nr(leaf, slot);
3106 if (old_size == new_size)
3107 return 0;
3108
3109 nritems = btrfs_header_nritems(leaf);
3110 data_end = leaf_data_end(root, leaf);
3111
3112 old_data_start = btrfs_item_offset_nr(leaf, slot);
3113
3114 size_diff = old_size - new_size;
3115
3116 BUG_ON(slot < 0);
3117 BUG_ON(slot >= nritems);
3118
3119 /*
3120 * item0..itemN ... dataN.offset..dataN.size .. data0.size
3121 */
3122 /* first correct the data pointers */
3123 for (i = slot; i < nritems; i++) {
3124 u32 ioff;
3125 item = btrfs_item_nr(leaf, i);
3126
3127 if (!leaf->map_token) {
3128 map_extent_buffer(leaf, (unsigned long)item,
3129 sizeof(struct btrfs_item),
3130 &leaf->map_token, &leaf->kaddr,
3131 &leaf->map_start, &leaf->map_len,
3132 KM_USER1);
3133 }
3134
3135 ioff = btrfs_item_offset(leaf, item);
3136 btrfs_set_item_offset(leaf, item, ioff + size_diff);
3137 }
3138
3139 if (leaf->map_token) {
3140 unmap_extent_buffer(leaf, leaf->map_token, KM_USER1);
3141 leaf->map_token = NULL;
3142 }
3143
3144 /* shift the data */
3145 if (from_end) {
3146 memmove_extent_buffer(leaf, btrfs_leaf_data(leaf) +
3147 data_end + size_diff, btrfs_leaf_data(leaf) +
3148 data_end, old_data_start + new_size - data_end);
3149 } else {
3150 struct btrfs_disk_key disk_key;
3151 u64 offset;
3152
3153 btrfs_item_key(leaf, &disk_key, slot);
3154
3155 if (btrfs_disk_key_type(&disk_key) == BTRFS_EXTENT_DATA_KEY) {
3156 unsigned long ptr;
3157 struct btrfs_file_extent_item *fi;
3158
3159 fi = btrfs_item_ptr(leaf, slot,
3160 struct btrfs_file_extent_item);
3161 fi = (struct btrfs_file_extent_item *)(
3162 (unsigned long)fi - size_diff);
3163
3164 if (btrfs_file_extent_type(leaf, fi) ==
3165 BTRFS_FILE_EXTENT_INLINE) {
3166 ptr = btrfs_item_ptr_offset(leaf, slot);
3167 memmove_extent_buffer(leaf, ptr,
3168 (unsigned long)fi,
3169 offsetof(struct btrfs_file_extent_item,
3170 disk_bytenr));
3171 }
3172 }
3173
3174 memmove_extent_buffer(leaf, btrfs_leaf_data(leaf) +
3175 data_end + size_diff, btrfs_leaf_data(leaf) +
3176 data_end, old_data_start - data_end);
3177
3178 offset = btrfs_disk_key_offset(&disk_key);
3179 btrfs_set_disk_key_offset(&disk_key, offset + size_diff);
3180 btrfs_set_item_key(leaf, &disk_key, slot);
3181 if (slot == 0)
3182 fixup_low_keys(trans, root, path, &disk_key, 1);
3183 }
3184
3185 item = btrfs_item_nr(leaf, slot);
3186 btrfs_set_item_size(leaf, item, new_size);
3187 btrfs_mark_buffer_dirty(leaf);
3188
3189 ret = 0;
3190 if (btrfs_leaf_free_space(root, leaf) < 0) {
3191 btrfs_print_leaf(root, leaf);
3192 BUG();
3193 }
3194 return ret;
3195 }
3196
3197 /*
3198 * make the item pointed to by the path bigger, data_size is the new size.
3199 */
3200 int btrfs_extend_item(struct btrfs_trans_handle *trans,
3201 struct btrfs_root *root, struct btrfs_path *path,
3202 u32 data_size)
3203 {
3204 int ret = 0;
3205 int slot;
3206 int slot_orig;
3207 struct extent_buffer *leaf;
3208 struct btrfs_item *item;
3209 u32 nritems;
3210 unsigned int data_end;
3211 unsigned int old_data;
3212 unsigned int old_size;
3213 int i;
3214
3215 slot_orig = path->slots[0];
3216 leaf = path->nodes[0];
3217
3218 nritems = btrfs_header_nritems(leaf);
3219 data_end = leaf_data_end(root, leaf);
3220
3221 if (btrfs_leaf_free_space(root, leaf) < data_size) {
3222 btrfs_print_leaf(root, leaf);
3223 BUG();
3224 }
3225 slot = path->slots[0];
3226 old_data = btrfs_item_end_nr(leaf, slot);
3227
3228 BUG_ON(slot < 0);
3229 if (slot >= nritems) {
3230 btrfs_print_leaf(root, leaf);
3231 printk(KERN_CRIT "slot %d too large, nritems %d\n",
3232 slot, nritems);
3233 BUG_ON(1);
3234 }
3235
3236 /*
3237 * item0..itemN ... dataN.offset..dataN.size .. data0.size
3238 */
3239 /* first correct the data pointers */
3240 for (i = slot; i < nritems; i++) {
3241 u32 ioff;
3242 item = btrfs_item_nr(leaf, i);
3243
3244 if (!leaf->map_token) {
3245 map_extent_buffer(leaf, (unsigned long)item,
3246 sizeof(struct btrfs_item),
3247 &leaf->map_token, &leaf->kaddr,
3248 &leaf->map_start, &leaf->map_len,
3249 KM_USER1);
3250 }
3251 ioff = btrfs_item_offset(leaf, item);
3252 btrfs_set_item_offset(leaf, item, ioff - data_size);
3253 }
3254
3255 if (leaf->map_token) {
3256 unmap_extent_buffer(leaf, leaf->map_token, KM_USER1);
3257 leaf->map_token = NULL;
3258 }
3259
3260 /* shift the data */
3261 memmove_extent_buffer(leaf, btrfs_leaf_data(leaf) +
3262 data_end - data_size, btrfs_leaf_data(leaf) +
3263 data_end, old_data - data_end);
3264
3265 data_end = old_data;
3266 old_size = btrfs_item_size_nr(leaf, slot);
3267 item = btrfs_item_nr(leaf, slot);
3268 btrfs_set_item_size(leaf, item, old_size + data_size);
3269 btrfs_mark_buffer_dirty(leaf);
3270
3271 ret = 0;
3272 if (btrfs_leaf_free_space(root, leaf) < 0) {
3273 btrfs_print_leaf(root, leaf);
3274 BUG();
3275 }
3276 return ret;
3277 }
3278
3279 /*
3280 * Given a key and some data, insert items into the tree.
3281 * This does all the path init required, making room in the tree if needed.
3282 * Returns the number of keys that were inserted.
3283 */
3284 int btrfs_insert_some_items(struct btrfs_trans_handle *trans,
3285 struct btrfs_root *root,
3286 struct btrfs_path *path,
3287 struct btrfs_key *cpu_key, u32 *data_size,
3288 int nr)
3289 {
3290 struct extent_buffer *leaf;
3291 struct btrfs_item *item;
3292 int ret = 0;
3293 int slot;
3294 int i;
3295 u32 nritems;
3296 u32 total_data = 0;
3297 u32 total_size = 0;
3298 unsigned int data_end;
3299 struct btrfs_disk_key disk_key;
3300 struct btrfs_key found_key;
3301
3302 for (i = 0; i < nr; i++) {
3303 if (total_size + data_size[i] + sizeof(struct btrfs_item) >
3304 BTRFS_LEAF_DATA_SIZE(root)) {
3305 break;
3306 nr = i;
3307 }
3308 total_data += data_size[i];
3309 total_size += data_size[i] + sizeof(struct btrfs_item);
3310 }
3311 BUG_ON(nr == 0);
3312
3313 ret = btrfs_search_slot(trans, root, cpu_key, path, total_size, 1);
3314 if (ret == 0)
3315 return -EEXIST;
3316 if (ret < 0)
3317 goto out;
3318
3319 leaf = path->nodes[0];
3320
3321 nritems = btrfs_header_nritems(leaf);
3322 data_end = leaf_data_end(root, leaf);
3323
3324 if (btrfs_leaf_free_space(root, leaf) < total_size) {
3325 for (i = nr; i >= 0; i--) {
3326 total_data -= data_size[i];
3327 total_size -= data_size[i] + sizeof(struct btrfs_item);
3328 if (total_size < btrfs_leaf_free_space(root, leaf))
3329 break;
3330 }
3331 nr = i;
3332 }
3333
3334 slot = path->slots[0];
3335 BUG_ON(slot < 0);
3336
3337 if (slot != nritems) {
3338 unsigned int old_data = btrfs_item_end_nr(leaf, slot);
3339
3340 item = btrfs_item_nr(leaf, slot);
3341 btrfs_item_key_to_cpu(leaf, &found_key, slot);
3342
3343 /* figure out how many keys we can insert in here */
3344 total_data = data_size[0];
3345 for (i = 1; i < nr; i++) {
3346 if (comp_cpu_keys(&found_key, cpu_key + i) <= 0)
3347 break;
3348 total_data += data_size[i];
3349 }
3350 nr = i;
3351
3352 if (old_data < data_end) {
3353 btrfs_print_leaf(root, leaf);
3354 printk(KERN_CRIT "slot %d old_data %d data_end %d\n",
3355 slot, old_data, data_end);
3356 BUG_ON(1);
3357 }
3358 /*
3359 * item0..itemN ... dataN.offset..dataN.size .. data0.size
3360 */
3361 /* first correct the data pointers */
3362 WARN_ON(leaf->map_token);
3363 for (i = slot; i < nritems; i++) {
3364 u32 ioff;
3365
3366 item = btrfs_item_nr(leaf, i);
3367 if (!leaf->map_token) {
3368 map_extent_buffer(leaf, (unsigned long)item,
3369 sizeof(struct btrfs_item),
3370 &leaf->map_token, &leaf->kaddr,
3371 &leaf->map_start, &leaf->map_len,
3372 KM_USER1);
3373 }
3374
3375 ioff = btrfs_item_offset(leaf, item);
3376 btrfs_set_item_offset(leaf, item, ioff - total_data);
3377 }
3378 if (leaf->map_token) {
3379 unmap_extent_buffer(leaf, leaf->map_token, KM_USER1);
3380 leaf->map_token = NULL;
3381 }
3382
3383 /* shift the items */
3384 memmove_extent_buffer(leaf, btrfs_item_nr_offset(slot + nr),
3385 btrfs_item_nr_offset(slot),
3386 (nritems - slot) * sizeof(struct btrfs_item));
3387
3388 /* shift the data */
3389 memmove_extent_buffer(leaf, btrfs_leaf_data(leaf) +
3390 data_end - total_data, btrfs_leaf_data(leaf) +
3391 data_end, old_data - data_end);
3392 data_end = old_data;
3393 } else {
3394 /*
3395 * this sucks but it has to be done, if we are inserting at
3396 * the end of the leaf only insert 1 of the items, since we
3397 * have no way of knowing whats on the next leaf and we'd have
3398 * to drop our current locks to figure it out
3399 */
3400 nr = 1;
3401 }
3402
3403 /* setup the item for the new data */
3404 for (i = 0; i < nr; i++) {
3405 btrfs_cpu_key_to_disk(&disk_key, cpu_key + i);
3406 btrfs_set_item_key(leaf, &disk_key, slot + i);
3407 item = btrfs_item_nr(leaf, slot + i);
3408 btrfs_set_item_offset(leaf, item, data_end - data_size[i]);
3409 data_end -= data_size[i];
3410 btrfs_set_item_size(leaf, item, data_size[i]);
3411 }
3412 btrfs_set_header_nritems(leaf, nritems + nr);
3413 btrfs_mark_buffer_dirty(leaf);
3414
3415 ret = 0;
3416 if (slot == 0) {
3417 btrfs_cpu_key_to_disk(&disk_key, cpu_key);
3418 ret = fixup_low_keys(trans, root, path, &disk_key, 1);
3419 }
3420
3421 if (btrfs_leaf_free_space(root, leaf) < 0) {
3422 btrfs_print_leaf(root, leaf);
3423 BUG();
3424 }
3425 out:
3426 if (!ret)
3427 ret = nr;
3428 return ret;
3429 }
3430
3431 /*
3432 * Given a key and some data, insert items into the tree.
3433 * This does all the path init required, making room in the tree if needed.
3434 */
3435 int btrfs_insert_empty_items(struct btrfs_trans_handle *trans,
3436 struct btrfs_root *root,
3437 struct btrfs_path *path,
3438 struct btrfs_key *cpu_key, u32 *data_size,
3439 int nr)
3440 {
3441 struct extent_buffer *leaf;
3442 struct btrfs_item *item;
3443 int ret = 0;
3444 int slot;
3445 int slot_orig;
3446 int i;
3447 u32 nritems;
3448 u32 total_size = 0;
3449 u32 total_data = 0;
3450 unsigned int data_end;
3451 struct btrfs_disk_key disk_key;
3452
3453 for (i = 0; i < nr; i++)
3454 total_data += data_size[i];
3455
3456 total_size = total_data + (nr * sizeof(struct btrfs_item));
3457 ret = btrfs_search_slot(trans, root, cpu_key, path, total_size, 1);
3458 if (ret == 0)
3459 return -EEXIST;
3460 if (ret < 0)
3461 goto out;
3462
3463 slot_orig = path->slots[0];
3464 leaf = path->nodes[0];
3465
3466 nritems = btrfs_header_nritems(leaf);
3467 data_end = leaf_data_end(root, leaf);
3468
3469 if (btrfs_leaf_free_space(root, leaf) < total_size) {
3470 btrfs_print_leaf(root, leaf);
3471 printk(KERN_CRIT "not enough freespace need %u have %d\n",
3472 total_size, btrfs_leaf_free_space(root, leaf));
3473 BUG();
3474 }
3475
3476 slot = path->slots[0];
3477 BUG_ON(slot < 0);
3478
3479 if (slot != nritems) {
3480 unsigned int old_data = btrfs_item_end_nr(leaf, slot);
3481
3482 if (old_data < data_end) {
3483 btrfs_print_leaf(root, leaf);
3484 printk(KERN_CRIT "slot %d old_data %d data_end %d\n",
3485 slot, old_data, data_end);
3486 BUG_ON(1);
3487 }
3488 /*
3489 * item0..itemN ... dataN.offset..dataN.size .. data0.size
3490 */
3491 /* first correct the data pointers */
3492 WARN_ON(leaf->map_token);
3493 for (i = slot; i < nritems; i++) {
3494 u32 ioff;
3495
3496 item = btrfs_item_nr(leaf, i);
3497 if (!leaf->map_token) {
3498 map_extent_buffer(leaf, (unsigned long)item,
3499 sizeof(struct btrfs_item),
3500 &leaf->map_token, &leaf->kaddr,
3501 &leaf->map_start, &leaf->map_len,
3502 KM_USER1);
3503 }
3504
3505 ioff = btrfs_item_offset(leaf, item);
3506 btrfs_set_item_offset(leaf, item, ioff - total_data);
3507 }
3508 if (leaf->map_token) {
3509 unmap_extent_buffer(leaf, leaf->map_token, KM_USER1);
3510 leaf->map_token = NULL;
3511 }
3512
3513 /* shift the items */
3514 memmove_extent_buffer(leaf, btrfs_item_nr_offset(slot + nr),
3515 btrfs_item_nr_offset(slot),
3516 (nritems - slot) * sizeof(struct btrfs_item));
3517
3518 /* shift the data */
3519 memmove_extent_buffer(leaf, btrfs_leaf_data(leaf) +
3520 data_end - total_data, btrfs_leaf_data(leaf) +
3521 data_end, old_data - data_end);
3522 data_end = old_data;
3523 }
3524
3525 /* setup the item for the new data */
3526 for (i = 0; i < nr; i++) {
3527 btrfs_cpu_key_to_disk(&disk_key, cpu_key + i);
3528 btrfs_set_item_key(leaf, &disk_key, slot + i);
3529 item = btrfs_item_nr(leaf, slot + i);
3530 btrfs_set_item_offset(leaf, item, data_end - data_size[i]);
3531 data_end -= data_size[i];
3532 btrfs_set_item_size(leaf, item, data_size[i]);
3533 }
3534 btrfs_set_header_nritems(leaf, nritems + nr);
3535 btrfs_mark_buffer_dirty(leaf);
3536
3537 ret = 0;
3538 if (slot == 0) {
3539 btrfs_cpu_key_to_disk(&disk_key, cpu_key);
3540 ret = fixup_low_keys(trans, root, path, &disk_key, 1);
3541 }
3542
3543 if (btrfs_leaf_free_space(root, leaf) < 0) {
3544 btrfs_print_leaf(root, leaf);
3545 BUG();
3546 }
3547 out:
3548 btrfs_unlock_up_safe(path, 1);
3549 return ret;
3550 }
3551
3552 /*
3553 * Given a key and some data, insert an item into the tree.
3554 * This does all the path init required, making room in the tree if needed.
3555 */
3556 int btrfs_insert_item(struct btrfs_trans_handle *trans, struct btrfs_root
3557 *root, struct btrfs_key *cpu_key, void *data, u32
3558 data_size)
3559 {
3560 int ret = 0;
3561 struct btrfs_path *path;
3562 struct extent_buffer *leaf;
3563 unsigned long ptr;
3564
3565 path = btrfs_alloc_path();
3566 BUG_ON(!path);
3567 ret = btrfs_insert_empty_item(trans, root, path, cpu_key, data_size);
3568 if (!ret) {
3569 leaf = path->nodes[0];
3570 ptr = btrfs_item_ptr_offset(leaf, path->slots[0]);
3571 write_extent_buffer(leaf, data, ptr, data_size);
3572 btrfs_mark_buffer_dirty(leaf);
3573 }
3574 btrfs_free_path(path);
3575 return ret;
3576 }
3577
3578 /*
3579 * delete the pointer from a given node.
3580 *
3581 * the tree should have been previously balanced so the deletion does not
3582 * empty a node.
3583 */
3584 static int del_ptr(struct btrfs_trans_handle *trans, struct btrfs_root *root,
3585 struct btrfs_path *path, int level, int slot)
3586 {
3587 struct extent_buffer *parent = path->nodes[level];
3588 u32 nritems;
3589 int ret = 0;
3590 int wret;
3591
3592 nritems = btrfs_header_nritems(parent);
3593 if (slot != nritems - 1) {
3594 memmove_extent_buffer(parent,
3595 btrfs_node_key_ptr_offset(slot),
3596 btrfs_node_key_ptr_offset(slot + 1),
3597 sizeof(struct btrfs_key_ptr) *
3598 (nritems - slot - 1));
3599 }
3600 nritems--;
3601 btrfs_set_header_nritems(parent, nritems);
3602 if (nritems == 0 && parent == root->node) {
3603 BUG_ON(btrfs_header_level(root->node) != 1);
3604 /* just turn the root into a leaf and break */
3605 btrfs_set_header_level(root->node, 0);
3606 } else if (slot == 0) {
3607 struct btrfs_disk_key disk_key;
3608
3609 btrfs_node_key(parent, &disk_key, 0);
3610 wret = fixup_low_keys(trans, root, path, &disk_key, level + 1);
3611 if (wret)
3612 ret = wret;
3613 }
3614 btrfs_mark_buffer_dirty(parent);
3615 return ret;
3616 }
3617
3618 /*
3619 * a helper function to delete the leaf pointed to by path->slots[1] and
3620 * path->nodes[1]. bytenr is the node block pointer, but since the callers
3621 * already know it, it is faster to have them pass it down than to
3622 * read it out of the node again.
3623 *
3624 * This deletes the pointer in path->nodes[1] and frees the leaf
3625 * block extent. zero is returned if it all worked out, < 0 otherwise.
3626 *
3627 * The path must have already been setup for deleting the leaf, including
3628 * all the proper balancing. path->nodes[1] must be locked.
3629 */
3630 noinline int btrfs_del_leaf(struct btrfs_trans_handle *trans,
3631 struct btrfs_root *root,
3632 struct btrfs_path *path, u64 bytenr)
3633 {
3634 int ret;
3635 u64 root_gen = btrfs_header_generation(path->nodes[1]);
3636 u64 parent_start = path->nodes[1]->start;
3637 u64 parent_owner = btrfs_header_owner(path->nodes[1]);
3638
3639 ret = del_ptr(trans, root, path, 1, path->slots[1]);
3640 if (ret)
3641 return ret;
3642
3643 /*
3644 * btrfs_free_extent is expensive, we want to make sure we
3645 * aren't holding any locks when we call it
3646 */
3647 btrfs_unlock_up_safe(path, 0);
3648
3649 ret = btrfs_free_extent(trans, root, bytenr,
3650 btrfs_level_size(root, 0),
3651 parent_start, parent_owner,
3652 root_gen, 0, 1);
3653 return ret;
3654 }
3655 /*
3656 * delete the item at the leaf level in path. If that empties
3657 * the leaf, remove it from the tree
3658 */
3659 int btrfs_del_items(struct btrfs_trans_handle *trans, struct btrfs_root *root,
3660 struct btrfs_path *path, int slot, int nr)
3661 {
3662 struct extent_buffer *leaf;
3663 struct btrfs_item *item;
3664 int last_off;
3665 int dsize = 0;
3666 int ret = 0;
3667 int wret;
3668 int i;
3669 u32 nritems;
3670
3671 leaf = path->nodes[0];
3672 last_off = btrfs_item_offset_nr(leaf, slot + nr - 1);
3673
3674 for (i = 0; i < nr; i++)
3675 dsize += btrfs_item_size_nr(leaf, slot + i);
3676
3677 nritems = btrfs_header_nritems(leaf);
3678
3679 if (slot + nr != nritems) {
3680 int data_end = leaf_data_end(root, leaf);
3681
3682 memmove_extent_buffer(leaf, btrfs_leaf_data(leaf) +
3683 data_end + dsize,
3684 btrfs_leaf_data(leaf) + data_end,
3685 last_off - data_end);
3686
3687 for (i = slot + nr; i < nritems; i++) {
3688 u32 ioff;
3689
3690 item = btrfs_item_nr(leaf, i);
3691 if (!leaf->map_token) {
3692 map_extent_buffer(leaf, (unsigned long)item,
3693 sizeof(struct btrfs_item),
3694 &leaf->map_token, &leaf->kaddr,
3695 &leaf->map_start, &leaf->map_len,
3696 KM_USER1);
3697 }
3698 ioff = btrfs_item_offset(leaf, item);
3699 btrfs_set_item_offset(leaf, item, ioff + dsize);
3700 }
3701
3702 if (leaf->map_token) {
3703 unmap_extent_buffer(leaf, leaf->map_token, KM_USER1);
3704 leaf->map_token = NULL;
3705 }
3706
3707 memmove_extent_buffer(leaf, btrfs_item_nr_offset(slot),
3708 btrfs_item_nr_offset(slot + nr),
3709 sizeof(struct btrfs_item) *
3710 (nritems - slot - nr));
3711 }
3712 btrfs_set_header_nritems(leaf, nritems - nr);
3713 nritems -= nr;
3714
3715 /* delete the leaf if we've emptied it */
3716 if (nritems == 0) {
3717 if (leaf == root->node) {
3718 btrfs_set_header_level(leaf, 0);
3719 } else {
3720 ret = btrfs_del_leaf(trans, root, path, leaf->start);
3721 BUG_ON(ret);
3722 }
3723 } else {
3724 int used = leaf_space_used(leaf, 0, nritems);
3725 if (slot == 0) {
3726 struct btrfs_disk_key disk_key;
3727
3728 btrfs_item_key(leaf, &disk_key, 0);
3729 wret = fixup_low_keys(trans, root, path,
3730 &disk_key, 1);
3731 if (wret)
3732 ret = wret;
3733 }
3734
3735 /* delete the leaf if it is mostly empty */
3736 if (used < BTRFS_LEAF_DATA_SIZE(root) / 4) {
3737 /* push_leaf_left fixes the path.
3738 * make sure the path still points to our leaf
3739 * for possible call to del_ptr below
3740 */
3741 slot = path->slots[1];
3742 extent_buffer_get(leaf);
3743
3744 wret = push_leaf_left(trans, root, path, 1, 1);
3745 if (wret < 0 && wret != -ENOSPC)
3746 ret = wret;
3747
3748 if (path->nodes[0] == leaf &&
3749 btrfs_header_nritems(leaf)) {
3750 wret = push_leaf_right(trans, root, path, 1, 1);
3751 if (wret < 0 && wret != -ENOSPC)
3752 ret = wret;
3753 }
3754
3755 if (btrfs_header_nritems(leaf) == 0) {
3756 path->slots[1] = slot;
3757 ret = btrfs_del_leaf(trans, root, path,
3758 leaf->start);
3759 BUG_ON(ret);
3760 free_extent_buffer(leaf);
3761 } else {
3762 /* if we're still in the path, make sure
3763 * we're dirty. Otherwise, one of the
3764 * push_leaf functions must have already
3765 * dirtied this buffer
3766 */
3767 if (path->nodes[0] == leaf)
3768 btrfs_mark_buffer_dirty(leaf);
3769 free_extent_buffer(leaf);
3770 }
3771 } else {
3772 btrfs_mark_buffer_dirty(leaf);
3773 }
3774 }
3775 return ret;
3776 }
3777
3778 /*
3779 * search the tree again to find a leaf with lesser keys
3780 * returns 0 if it found something or 1 if there are no lesser leaves.
3781 * returns < 0 on io errors.
3782 *
3783 * This may release the path, and so you may lose any locks held at the
3784 * time you call it.
3785 */
3786 int btrfs_prev_leaf(struct btrfs_root *root, struct btrfs_path *path)
3787 {
3788 struct btrfs_key key;
3789 struct btrfs_disk_key found_key;
3790 int ret;
3791
3792 btrfs_item_key_to_cpu(path->nodes[0], &key, 0);
3793
3794 if (key.offset > 0)
3795 key.offset--;
3796 else if (key.type > 0)
3797 key.type--;
3798 else if (key.objectid > 0)
3799 key.objectid--;
3800 else
3801 return 1;
3802
3803 btrfs_release_path(root, path);
3804 ret = btrfs_search_slot(NULL, root, &key, path, 0, 0);
3805 if (ret < 0)
3806 return ret;
3807 btrfs_item_key(path->nodes[0], &found_key, 0);
3808 ret = comp_keys(&found_key, &key);
3809 if (ret < 0)
3810 return 0;
3811 return 1;
3812 }
3813
3814 /*
3815 * A helper function to walk down the tree starting at min_key, and looking
3816 * for nodes or leaves that are either in cache or have a minimum
3817 * transaction id. This is used by the btree defrag code, and tree logging
3818 *
3819 * This does not cow, but it does stuff the starting key it finds back
3820 * into min_key, so you can call btrfs_search_slot with cow=1 on the
3821 * key and get a writable path.
3822 *
3823 * This does lock as it descends, and path->keep_locks should be set
3824 * to 1 by the caller.
3825 *
3826 * This honors path->lowest_level to prevent descent past a given level
3827 * of the tree.
3828 *
3829 * min_trans indicates the oldest transaction that you are interested
3830 * in walking through. Any nodes or leaves older than min_trans are
3831 * skipped over (without reading them).
3832 *
3833 * returns zero if something useful was found, < 0 on error and 1 if there
3834 * was nothing in the tree that matched the search criteria.
3835 */
3836 int btrfs_search_forward(struct btrfs_root *root, struct btrfs_key *min_key,
3837 struct btrfs_key *max_key,
3838 struct btrfs_path *path, int cache_only,
3839 u64 min_trans)
3840 {
3841 struct extent_buffer *cur;
3842 struct btrfs_key found_key;
3843 int slot;
3844 int sret;
3845 u32 nritems;
3846 int level;
3847 int ret = 1;
3848
3849 WARN_ON(!path->keep_locks);
3850 again:
3851 cur = btrfs_lock_root_node(root);
3852 level = btrfs_header_level(cur);
3853 WARN_ON(path->nodes[level]);
3854 path->nodes[level] = cur;
3855 path->locks[level] = 1;
3856
3857 if (btrfs_header_generation(cur) < min_trans) {
3858 ret = 1;
3859 goto out;
3860 }
3861 while (1) {
3862 nritems = btrfs_header_nritems(cur);
3863 level = btrfs_header_level(cur);
3864 sret = bin_search(cur, min_key, level, &slot);
3865
3866 /* at the lowest level, we're done, setup the path and exit */
3867 if (level == path->lowest_level) {
3868 if (slot >= nritems)
3869 goto find_next_key;
3870 ret = 0;
3871 path->slots[level] = slot;
3872 btrfs_item_key_to_cpu(cur, &found_key, slot);
3873 goto out;
3874 }
3875 if (sret && slot > 0)
3876 slot--;
3877 /*
3878 * check this node pointer against the cache_only and
3879 * min_trans parameters. If it isn't in cache or is too
3880 * old, skip to the next one.
3881 */
3882 while (slot < nritems) {
3883 u64 blockptr;
3884 u64 gen;
3885 struct extent_buffer *tmp;
3886 struct btrfs_disk_key disk_key;
3887
3888 blockptr = btrfs_node_blockptr(cur, slot);
3889 gen = btrfs_node_ptr_generation(cur, slot);
3890 if (gen < min_trans) {
3891 slot++;
3892 continue;
3893 }
3894 if (!cache_only)
3895 break;
3896
3897 if (max_key) {
3898 btrfs_node_key(cur, &disk_key, slot);
3899 if (comp_keys(&disk_key, max_key) >= 0) {
3900 ret = 1;
3901 goto out;
3902 }
3903 }
3904
3905 tmp = btrfs_find_tree_block(root, blockptr,
3906 btrfs_level_size(root, level - 1));
3907
3908 if (tmp && btrfs_buffer_uptodate(tmp, gen)) {
3909 free_extent_buffer(tmp);
3910 break;
3911 }
3912 if (tmp)
3913 free_extent_buffer(tmp);
3914 slot++;
3915 }
3916 find_next_key:
3917 /*
3918 * we didn't find a candidate key in this node, walk forward
3919 * and find another one
3920 */
3921 if (slot >= nritems) {
3922 path->slots[level] = slot;
3923 btrfs_set_path_blocking(path);
3924 sret = btrfs_find_next_key(root, path, min_key, level,
3925 cache_only, min_trans);
3926 if (sret == 0) {
3927 btrfs_release_path(root, path);
3928 goto again;
3929 } else {
3930 btrfs_clear_path_blocking(path);
3931 goto out;
3932 }
3933 }
3934 /* save our key for returning back */
3935 btrfs_node_key_to_cpu(cur, &found_key, slot);
3936 path->slots[level] = slot;
3937 if (level == path->lowest_level) {
3938 ret = 0;
3939 unlock_up(path, level, 1);
3940 goto out;
3941 }
3942 btrfs_set_path_blocking(path);
3943 cur = read_node_slot(root, cur, slot);
3944
3945 btrfs_tree_lock(cur);
3946
3947 path->locks[level - 1] = 1;
3948 path->nodes[level - 1] = cur;
3949 unlock_up(path, level, 1);
3950 btrfs_clear_path_blocking(path);
3951 }
3952 out:
3953 if (ret == 0)
3954 memcpy(min_key, &found_key, sizeof(found_key));
3955 btrfs_set_path_blocking(path);
3956 return ret;
3957 }
3958
3959 /*
3960 * this is similar to btrfs_next_leaf, but does not try to preserve
3961 * and fixup the path. It looks for and returns the next key in the
3962 * tree based on the current path and the cache_only and min_trans
3963 * parameters.
3964 *
3965 * 0 is returned if another key is found, < 0 if there are any errors
3966 * and 1 is returned if there are no higher keys in the tree
3967 *
3968 * path->keep_locks should be set to 1 on the search made before
3969 * calling this function.
3970 */
3971 int btrfs_find_next_key(struct btrfs_root *root, struct btrfs_path *path,
3972 struct btrfs_key *key, int lowest_level,
3973 int cache_only, u64 min_trans)
3974 {
3975 int level = lowest_level;
3976 int slot;
3977 struct extent_buffer *c;
3978
3979 WARN_ON(!path->keep_locks);
3980 while (level < BTRFS_MAX_LEVEL) {
3981 if (!path->nodes[level])
3982 return 1;
3983
3984 slot = path->slots[level] + 1;
3985 c = path->nodes[level];
3986 next:
3987 if (slot >= btrfs_header_nritems(c)) {
3988 level++;
3989 if (level == BTRFS_MAX_LEVEL)
3990 return 1;
3991 continue;
3992 }
3993 if (level == 0)
3994 btrfs_item_key_to_cpu(c, key, slot);
3995 else {
3996 u64 blockptr = btrfs_node_blockptr(c, slot);
3997 u64 gen = btrfs_node_ptr_generation(c, slot);
3998
3999 if (cache_only) {
4000 struct extent_buffer *cur;
4001 cur = btrfs_find_tree_block(root, blockptr,
4002 btrfs_level_size(root, level - 1));
4003 if (!cur || !btrfs_buffer_uptodate(cur, gen)) {
4004 slot++;
4005 if (cur)
4006 free_extent_buffer(cur);
4007 goto next;
4008 }
4009 free_extent_buffer(cur);
4010 }
4011 if (gen < min_trans) {
4012 slot++;
4013 goto next;
4014 }
4015 btrfs_node_key_to_cpu(c, key, slot);
4016 }
4017 return 0;
4018 }
4019 return 1;
4020 }
4021
4022 /*
4023 * search the tree again to find a leaf with greater keys
4024 * returns 0 if it found something or 1 if there are no greater leaves.
4025 * returns < 0 on io errors.
4026 */
4027 int btrfs_next_leaf(struct btrfs_root *root, struct btrfs_path *path)
4028 {
4029 int slot;
4030 int level = 1;
4031 struct extent_buffer *c;
4032 struct extent_buffer *next = NULL;
4033 struct btrfs_key key;
4034 u32 nritems;
4035 int ret;
4036
4037 nritems = btrfs_header_nritems(path->nodes[0]);
4038 if (nritems == 0)
4039 return 1;
4040
4041 btrfs_item_key_to_cpu(path->nodes[0], &key, nritems - 1);
4042
4043 btrfs_release_path(root, path);
4044 path->keep_locks = 1;
4045 ret = btrfs_search_slot(NULL, root, &key, path, 0, 0);
4046 path->keep_locks = 0;
4047
4048 if (ret < 0)
4049 return ret;
4050
4051 btrfs_set_path_blocking(path);
4052 nritems = btrfs_header_nritems(path->nodes[0]);
4053 /*
4054 * by releasing the path above we dropped all our locks. A balance
4055 * could have added more items next to the key that used to be
4056 * at the very end of the block. So, check again here and
4057 * advance the path if there are now more items available.
4058 */
4059 if (nritems > 0 && path->slots[0] < nritems - 1) {
4060 path->slots[0]++;
4061 goto done;
4062 }
4063
4064 while (level < BTRFS_MAX_LEVEL) {
4065 if (!path->nodes[level])
4066 return 1;
4067
4068 slot = path->slots[level] + 1;
4069 c = path->nodes[level];
4070 if (slot >= btrfs_header_nritems(c)) {
4071 level++;
4072 if (level == BTRFS_MAX_LEVEL)
4073 return 1;
4074 continue;
4075 }
4076
4077 if (next) {
4078 btrfs_tree_unlock(next);
4079 free_extent_buffer(next);
4080 }
4081
4082 /* the path was set to blocking above */
4083 if (level == 1 && (path->locks[1] || path->skip_locking) &&
4084 path->reada)
4085 reada_for_search(root, path, level, slot, 0);
4086
4087 next = read_node_slot(root, c, slot);
4088 if (!path->skip_locking) {
4089 WARN_ON(!btrfs_tree_locked(c));
4090 btrfs_tree_lock(next);
4091 btrfs_set_lock_blocking(next);
4092 }
4093 break;
4094 }
4095 path->slots[level] = slot;
4096 while (1) {
4097 level--;
4098 c = path->nodes[level];
4099 if (path->locks[level])
4100 btrfs_tree_unlock(c);
4101 free_extent_buffer(c);
4102 path->nodes[level] = next;
4103 path->slots[level] = 0;
4104 if (!path->skip_locking)
4105 path->locks[level] = 1;
4106 if (!level)
4107 break;
4108
4109 btrfs_set_path_blocking(path);
4110 if (level == 1 && path->locks[1] && path->reada)
4111 reada_for_search(root, path, level, slot, 0);
4112 next = read_node_slot(root, next, 0);
4113 if (!path->skip_locking) {
4114 WARN_ON(!btrfs_tree_locked(path->nodes[level]));
4115 btrfs_tree_lock(next);
4116 btrfs_set_lock_blocking(next);
4117 }
4118 }
4119 done:
4120 unlock_up(path, 0, 1);
4121 return 0;
4122 }
4123
4124 /*
4125 * this uses btrfs_prev_leaf to walk backwards in the tree, and keeps
4126 * searching until it gets past min_objectid or finds an item of 'type'
4127 *
4128 * returns 0 if something is found, 1 if nothing was found and < 0 on error
4129 */
4130 int btrfs_previous_item(struct btrfs_root *root,
4131 struct btrfs_path *path, u64 min_objectid,
4132 int type)
4133 {
4134 struct btrfs_key found_key;
4135 struct extent_buffer *leaf;
4136 u32 nritems;
4137 int ret;
4138
4139 while (1) {
4140 if (path->slots[0] == 0) {
4141 btrfs_set_path_blocking(path);
4142 ret = btrfs_prev_leaf(root, path);
4143 if (ret != 0)
4144 return ret;
4145 } else {
4146 path->slots[0]--;
4147 }
4148 leaf = path->nodes[0];
4149 nritems = btrfs_header_nritems(leaf);
4150 if (nritems == 0)
4151 return 1;
4152 if (path->slots[0] == nritems)
4153 path->slots[0]--;
4154
4155 btrfs_item_key_to_cpu(leaf, &found_key, path->slots[0]);
4156 if (found_key.type == type)
4157 return 0;
4158 if (found_key.objectid < min_objectid)
4159 break;
4160 if (found_key.objectid == min_objectid &&
4161 found_key.type < type)
4162 break;
4163 }
4164 return 1;
4165 }
linux 2.6 git repository for openrd