?  search:
summary | log | graphiclog1 | graphiclog2 | commit | commitdiff | tree | refs | edit | fork
blame | history | raw | HEAD
x86, mce: use a call vector to call the 64bit mce handler
[linux-2.6/mini2440.git] / fs / btrfs / extent-tree.c
blob3e2c7c738f23844c0a401faac13db203304b7e9c
1 /*
2 * Copyright (C) 2007 Oracle. All rights reserved.
3 *
4 * This program is free software; you can redistribute it and/or
5 * modify it under the terms of the GNU General Public
6 * License v2 as published by the Free Software Foundation.
7 *
8 * This program is distributed in the hope that it will be useful,
9 * but WITHOUT ANY WARRANTY; without even the implied warranty of
10 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
11 * General Public License for more details.
12 *
13 * You should have received a copy of the GNU General Public
14 * License along with this program; if not, write to the
15 * Free Software Foundation, Inc., 59 Temple Place - Suite 330,
16 * Boston, MA 021110-1307, USA.
17 */
18 #include <linux/sched.h>
19 #include <linux/pagemap.h>
20 #include <linux/writeback.h>
21 #include <linux/blkdev.h>
22 #include <linux/sort.h>
23 #include <linux/rcupdate.h>
24 #include "compat.h"
25 #include "hash.h"
26 #include "crc32c.h"
27 #include "ctree.h"
28 #include "disk-io.h"
29 #include "print-tree.h"
30 #include "transaction.h"
31 #include "volumes.h"
32 #include "locking.h"
33 #include "ref-cache.h"
34 #include "free-space-cache.h"
35
36 #define PENDING_EXTENT_INSERT 0
37 #define PENDING_EXTENT_DELETE 1
38 #define PENDING_BACKREF_UPDATE 2
39
40 struct pending_extent_op {
41 int type;
42 u64 bytenr;
43 u64 num_bytes;
44 u64 parent;
45 u64 orig_parent;
46 u64 generation;
47 u64 orig_generation;
48 int level;
49 struct list_head list;
50 int del;
51 };
52
53 static int __btrfs_alloc_reserved_extent(struct btrfs_trans_handle *trans,
54 struct btrfs_root *root, u64 parent,
55 u64 root_objectid, u64 ref_generation,
56 u64 owner, struct btrfs_key *ins,
57 int ref_mod);
58 static int update_reserved_extents(struct btrfs_root *root,
59 u64 bytenr, u64 num, int reserve);
60 static int update_block_group(struct btrfs_trans_handle *trans,
61 struct btrfs_root *root,
62 u64 bytenr, u64 num_bytes, int alloc,
63 int mark_free);
64 static noinline int __btrfs_free_extent(struct btrfs_trans_handle *trans,
65 struct btrfs_root *root,
66 u64 bytenr, u64 num_bytes, u64 parent,
67 u64 root_objectid, u64 ref_generation,
68 u64 owner_objectid, int pin,
69 int ref_to_drop);
70
71 static int do_chunk_alloc(struct btrfs_trans_handle *trans,
72 struct btrfs_root *extent_root, u64 alloc_bytes,
73 u64 flags, int force);
74
75 static int block_group_bits(struct btrfs_block_group_cache *cache, u64 bits)
76 {
77 return (cache->flags & bits) == bits;
78 }
79
80 /*
81 * this adds the block group to the fs_info rb tree for the block group
82 * cache
83 */
84 static int btrfs_add_block_group_cache(struct btrfs_fs_info *info,
85 struct btrfs_block_group_cache *block_group)
86 {
87 struct rb_node **p;
88 struct rb_node *parent = NULL;
89 struct btrfs_block_group_cache *cache;
90
91 spin_lock(&info->block_group_cache_lock);
92 p = &info->block_group_cache_tree.rb_node;
93
94 while (*p) {
95 parent = *p;
96 cache = rb_entry(parent, struct btrfs_block_group_cache,
97 cache_node);
98 if (block_group->key.objectid < cache->key.objectid) {
99 p = &(*p)->rb_left;
100 } else if (block_group->key.objectid > cache->key.objectid) {
101 p = &(*p)->rb_right;
102 } else {
103 spin_unlock(&info->block_group_cache_lock);
104 return -EEXIST;
105 }
106 }
107
108 rb_link_node(&block_group->cache_node, parent, p);
109 rb_insert_color(&block_group->cache_node,
110 &info->block_group_cache_tree);
111 spin_unlock(&info->block_group_cache_lock);
112
113 return 0;
114 }
115
116 /*
117 * This will return the block group at or after bytenr if contains is 0, else
118 * it will return the block group that contains the bytenr
119 */
120 static struct btrfs_block_group_cache *
121 block_group_cache_tree_search(struct btrfs_fs_info *info, u64 bytenr,
122 int contains)
123 {
124 struct btrfs_block_group_cache *cache, *ret = NULL;
125 struct rb_node *n;
126 u64 end, start;
127
128 spin_lock(&info->block_group_cache_lock);
129 n = info->block_group_cache_tree.rb_node;
130
131 while (n) {
132 cache = rb_entry(n, struct btrfs_block_group_cache,
133 cache_node);
134 end = cache->key.objectid + cache->key.offset - 1;
135 start = cache->key.objectid;
136
137 if (bytenr < start) {
138 if (!contains && (!ret || start < ret->key.objectid))
139 ret = cache;
140 n = n->rb_left;
141 } else if (bytenr > start) {
142 if (contains && bytenr <= end) {
143 ret = cache;
144 break;
145 }
146 n = n->rb_right;
147 } else {
148 ret = cache;
149 break;
150 }
151 }
152 if (ret)
153 atomic_inc(&ret->count);
154 spin_unlock(&info->block_group_cache_lock);
155
156 return ret;
157 }
158
159 /*
160 * this is only called by cache_block_group, since we could have freed extents
161 * we need to check the pinned_extents for any extents that can't be used yet
162 * since their free space will be released as soon as the transaction commits.
163 */
164 static int add_new_free_space(struct btrfs_block_group_cache *block_group,
165 struct btrfs_fs_info *info, u64 start, u64 end)
166 {
167 u64 extent_start, extent_end, size;
168 int ret;
169
170 while (start < end) {
171 ret = find_first_extent_bit(&info->pinned_extents, start,
172 &extent_start, &extent_end,
173 EXTENT_DIRTY);
174 if (ret)
175 break;
176
177 if (extent_start == start) {
178 start = extent_end + 1;
179 } else if (extent_start > start && extent_start < end) {
180 size = extent_start - start;
181 ret = btrfs_add_free_space(block_group, start,
182 size);
183 BUG_ON(ret);
184 start = extent_end + 1;
185 } else {
186 break;
187 }
188 }
189
190 if (start < end) {
191 size = end - start;
192 ret = btrfs_add_free_space(block_group, start, size);
193 BUG_ON(ret);
194 }
195
196 return 0;
197 }
198
199 static int remove_sb_from_cache(struct btrfs_root *root,
200 struct btrfs_block_group_cache *cache)
201 {
202 u64 bytenr;
203 u64 *logical;
204 int stripe_len;
205 int i, nr, ret;
206
207 for (i = 0; i < BTRFS_SUPER_MIRROR_MAX; i++) {
208 bytenr = btrfs_sb_offset(i);
209 ret = btrfs_rmap_block(&root->fs_info->mapping_tree,
210 cache->key.objectid, bytenr, 0,
211 &logical, &nr, &stripe_len);
212 BUG_ON(ret);
213 while (nr--) {
214 btrfs_remove_free_space(cache, logical[nr],
215 stripe_len);
216 }
217 kfree(logical);
218 }
219 return 0;
220 }
221
222 static int cache_block_group(struct btrfs_root *root,
223 struct btrfs_block_group_cache *block_group)
224 {
225 struct btrfs_path *path;
226 int ret = 0;
227 struct btrfs_key key;
228 struct extent_buffer *leaf;
229 int slot;
230 u64 last;
231
232 if (!block_group)
233 return 0;
234
235 root = root->fs_info->extent_root;
236
237 if (block_group->cached)
238 return 0;
239
240 path = btrfs_alloc_path();
241 if (!path)
242 return -ENOMEM;
243
244 path->reada = 2;
245 /*
246 * we get into deadlocks with paths held by callers of this function.
247 * since the alloc_mutex is protecting things right now, just
248 * skip the locking here
249 */
250 path->skip_locking = 1;
251 last = max_t(u64, block_group->key.objectid, BTRFS_SUPER_INFO_OFFSET);
252 key.objectid = last;
253 key.offset = 0;
254 btrfs_set_key_type(&key, BTRFS_EXTENT_ITEM_KEY);
255 ret = btrfs_search_slot(NULL, root, &key, path, 0, 0);
256 if (ret < 0)
257 goto err;
258
259 while (1) {
260 leaf = path->nodes[0];
261 slot = path->slots[0];
262 if (slot >= btrfs_header_nritems(leaf)) {
263 ret = btrfs_next_leaf(root, path);
264 if (ret < 0)
265 goto err;
266 if (ret == 0)
267 continue;
268 else
269 break;
270 }
271 btrfs_item_key_to_cpu(leaf, &key, slot);
272 if (key.objectid < block_group->key.objectid)
273 goto next;
274
275 if (key.objectid >= block_group->key.objectid +
276 block_group->key.offset)
277 break;
278
279 if (btrfs_key_type(&key) == BTRFS_EXTENT_ITEM_KEY) {
280 add_new_free_space(block_group, root->fs_info, last,
281 key.objectid);
282
283 last = key.objectid + key.offset;
284 }
285 next:
286 path->slots[0]++;
287 }
288
289 add_new_free_space(block_group, root->fs_info, last,
290 block_group->key.objectid +
291 block_group->key.offset);
292
293 block_group->cached = 1;
294 remove_sb_from_cache(root, block_group);
295 ret = 0;
296 err:
297 btrfs_free_path(path);
298 return ret;
299 }
300
301 /*
302 * return the block group that starts at or after bytenr
303 */
304 static struct btrfs_block_group_cache *
305 btrfs_lookup_first_block_group(struct btrfs_fs_info *info, u64 bytenr)
306 {
307 struct btrfs_block_group_cache *cache;
308
309 cache = block_group_cache_tree_search(info, bytenr, 0);
310
311 return cache;
312 }
313
314 /*
315 * return the block group that contains the given bytenr
316 */
317 struct btrfs_block_group_cache *btrfs_lookup_block_group(
318 struct btrfs_fs_info *info,
319 u64 bytenr)
320 {
321 struct btrfs_block_group_cache *cache;
322
323 cache = block_group_cache_tree_search(info, bytenr, 1);
324
325 return cache;
326 }
327
328 void btrfs_put_block_group(struct btrfs_block_group_cache *cache)
329 {
330 if (atomic_dec_and_test(&cache->count))
331 kfree(cache);
332 }
333
334 static struct btrfs_space_info *__find_space_info(struct btrfs_fs_info *info,
335 u64 flags)
336 {
337 struct list_head *head = &info->space_info;
338 struct btrfs_space_info *found;
339
340 rcu_read_lock();
341 list_for_each_entry_rcu(found, head, list) {
342 if (found->flags == flags) {
343 rcu_read_unlock();
344 return found;
345 }
346 }
347 rcu_read_unlock();
348 return NULL;
349 }
350
351 /*
352 * after adding space to the filesystem, we need to clear the full flags
353 * on all the space infos.
354 */
355 void btrfs_clear_space_info_full(struct btrfs_fs_info *info)
356 {
357 struct list_head *head = &info->space_info;
358 struct btrfs_space_info *found;
359
360 rcu_read_lock();
361 list_for_each_entry_rcu(found, head, list)
362 found->full = 0;
363 rcu_read_unlock();
364 }
365
366 static u64 div_factor(u64 num, int factor)
367 {
368 if (factor == 10)
369 return num;
370 num *= factor;
371 do_div(num, 10);
372 return num;
373 }
374
375 u64 btrfs_find_block_group(struct btrfs_root *root,
376 u64 search_start, u64 search_hint, int owner)
377 {
378 struct btrfs_block_group_cache *cache;
379 u64 used;
380 u64 last = max(search_hint, search_start);
381 u64 group_start = 0;
382 int full_search = 0;
383 int factor = 9;
384 int wrapped = 0;
385 again:
386 while (1) {
387 cache = btrfs_lookup_first_block_group(root->fs_info, last);
388 if (!cache)
389 break;
390
391 spin_lock(&cache->lock);
392 last = cache->key.objectid + cache->key.offset;
393 used = btrfs_block_group_used(&cache->item);
394
395 if ((full_search || !cache->ro) &&
396 block_group_bits(cache, BTRFS_BLOCK_GROUP_METADATA)) {
397 if (used + cache->pinned + cache->reserved <
398 div_factor(cache->key.offset, factor)) {
399 group_start = cache->key.objectid;
400 spin_unlock(&cache->lock);
401 btrfs_put_block_group(cache);
402 goto found;
403 }
404 }
405 spin_unlock(&cache->lock);
406 btrfs_put_block_group(cache);
407 cond_resched();
408 }
409 if (!wrapped) {
410 last = search_start;
411 wrapped = 1;
412 goto again;
413 }
414 if (!full_search && factor < 10) {
415 last = search_start;
416 full_search = 1;
417 factor = 10;
418 goto again;
419 }
420 found:
421 return group_start;
422 }
423
424 /* simple helper to search for an existing extent at a given offset */
425 int btrfs_lookup_extent(struct btrfs_root *root, u64 start, u64 len)
426 {
427 int ret;
428 struct btrfs_key key;
429 struct btrfs_path *path;
430
431 path = btrfs_alloc_path();
432 BUG_ON(!path);
433 key.objectid = start;
434 key.offset = len;
435 btrfs_set_key_type(&key, BTRFS_EXTENT_ITEM_KEY);
436 ret = btrfs_search_slot(NULL, root->fs_info->extent_root, &key, path,
437 0, 0);
438 btrfs_free_path(path);
439 return ret;
440 }
441
442 /*
443 * Back reference rules. Back refs have three main goals:
444 *
445 * 1) differentiate between all holders of references to an extent so that
446 * when a reference is dropped we can make sure it was a valid reference
447 * before freeing the extent.
448 *
449 * 2) Provide enough information to quickly find the holders of an extent
450 * if we notice a given block is corrupted or bad.
451 *
452 * 3) Make it easy to migrate blocks for FS shrinking or storage pool
453 * maintenance. This is actually the same as #2, but with a slightly
454 * different use case.
455 *
456 * File extents can be referenced by:
457 *
458 * - multiple snapshots, subvolumes, or different generations in one subvol
459 * - different files inside a single subvolume
460 * - different offsets inside a file (bookend extents in file.c)
461 *
462 * The extent ref structure has fields for:
463 *
464 * - Objectid of the subvolume root
465 * - Generation number of the tree holding the reference
466 * - objectid of the file holding the reference
467 * - number of references holding by parent node (alway 1 for tree blocks)
468 *
469 * Btree leaf may hold multiple references to a file extent. In most cases,
470 * these references are from same file and the corresponding offsets inside
471 * the file are close together.
472 *
473 * When a file extent is allocated the fields are filled in:
474 * (root_key.objectid, trans->transid, inode objectid, 1)
475 *
476 * When a leaf is cow'd new references are added for every file extent found
477 * in the leaf. It looks similar to the create case, but trans->transid will
478 * be different when the block is cow'd.
479 *
480 * (root_key.objectid, trans->transid, inode objectid,
481 * number of references in the leaf)
482 *
483 * When a file extent is removed either during snapshot deletion or
484 * file truncation, we find the corresponding back reference and check
485 * the following fields:
486 *
487 * (btrfs_header_owner(leaf), btrfs_header_generation(leaf),
488 * inode objectid)
489 *
490 * Btree extents can be referenced by:
491 *
492 * - Different subvolumes
493 * - Different generations of the same subvolume
494 *
495 * When a tree block is created, back references are inserted:
496 *
497 * (root->root_key.objectid, trans->transid, level, 1)
498 *
499 * When a tree block is cow'd, new back references are added for all the
500 * blocks it points to. If the tree block isn't in reference counted root,
501 * the old back references are removed. These new back references are of
502 * the form (trans->transid will have increased since creation):
503 *
504 * (root->root_key.objectid, trans->transid, level, 1)
505 *
506 * When a backref is in deleting, the following fields are checked:
507 *
508 * if backref was for a tree root:
509 * (btrfs_header_owner(itself), btrfs_header_generation(itself), level)
510 * else
511 * (btrfs_header_owner(parent), btrfs_header_generation(parent), level)
512 *
513 * Back Reference Key composing:
514 *
515 * The key objectid corresponds to the first byte in the extent, the key
516 * type is set to BTRFS_EXTENT_REF_KEY, and the key offset is the first
517 * byte of parent extent. If a extent is tree root, the key offset is set
518 * to the key objectid.
519 */
520
521 static noinline int lookup_extent_backref(struct btrfs_trans_handle *trans,
522 struct btrfs_root *root,
523 struct btrfs_path *path,
524 u64 bytenr, u64 parent,
525 u64 ref_root, u64 ref_generation,
526 u64 owner_objectid, int del)
527 {
528 struct btrfs_key key;
529 struct btrfs_extent_ref *ref;
530 struct extent_buffer *leaf;
531 u64 ref_objectid;
532 int ret;
533
534 key.objectid = bytenr;
535 key.type = BTRFS_EXTENT_REF_KEY;
536 key.offset = parent;
537
538 ret = btrfs_search_slot(trans, root, &key, path, del ? -1 : 0, 1);
539 if (ret < 0)
540 goto out;
541 if (ret > 0) {
542 ret = -ENOENT;
543 goto out;
544 }
545
546 leaf = path->nodes[0];
547 ref = btrfs_item_ptr(leaf, path->slots[0], struct btrfs_extent_ref);
548 ref_objectid = btrfs_ref_objectid(leaf, ref);
549 if (btrfs_ref_root(leaf, ref) != ref_root ||
550 btrfs_ref_generation(leaf, ref) != ref_generation ||
551 (ref_objectid != owner_objectid &&
552 ref_objectid != BTRFS_MULTIPLE_OBJECTIDS)) {
553 ret = -EIO;
554 WARN_ON(1);
555 goto out;
556 }
557 ret = 0;
558 out:
559 return ret;
560 }
561
562 static noinline int insert_extent_backref(struct btrfs_trans_handle *trans,
563 struct btrfs_root *root,
564 struct btrfs_path *path,
565 u64 bytenr, u64 parent,
566 u64 ref_root, u64 ref_generation,
567 u64 owner_objectid,
568 int refs_to_add)
569 {
570 struct btrfs_key key;
571 struct extent_buffer *leaf;
572 struct btrfs_extent_ref *ref;
573 u32 num_refs;
574 int ret;
575
576 key.objectid = bytenr;
577 key.type = BTRFS_EXTENT_REF_KEY;
578 key.offset = parent;
579
580 ret = btrfs_insert_empty_item(trans, root, path, &key, sizeof(*ref));
581 if (ret == 0) {
582 leaf = path->nodes[0];
583 ref = btrfs_item_ptr(leaf, path->slots[0],
584 struct btrfs_extent_ref);
585 btrfs_set_ref_root(leaf, ref, ref_root);
586 btrfs_set_ref_generation(leaf, ref, ref_generation);
587 btrfs_set_ref_objectid(leaf, ref, owner_objectid);
588 btrfs_set_ref_num_refs(leaf, ref, refs_to_add);
589 } else if (ret == -EEXIST) {
590 u64 existing_owner;
591
592 BUG_ON(owner_objectid < BTRFS_FIRST_FREE_OBJECTID);
593 leaf = path->nodes[0];
594 ref = btrfs_item_ptr(leaf, path->slots[0],
595 struct btrfs_extent_ref);
596 if (btrfs_ref_root(leaf, ref) != ref_root ||
597 btrfs_ref_generation(leaf, ref) != ref_generation) {
598 ret = -EIO;
599 WARN_ON(1);
600 goto out;
601 }
602
603 num_refs = btrfs_ref_num_refs(leaf, ref);
604 BUG_ON(num_refs == 0);
605 btrfs_set_ref_num_refs(leaf, ref, num_refs + refs_to_add);
606
607 existing_owner = btrfs_ref_objectid(leaf, ref);
608 if (existing_owner != owner_objectid &&
609 existing_owner != BTRFS_MULTIPLE_OBJECTIDS) {
610 btrfs_set_ref_objectid(leaf, ref,
611 BTRFS_MULTIPLE_OBJECTIDS);
612 }
613 ret = 0;
614 } else {
615 goto out;
616 }
617 btrfs_unlock_up_safe(path, 1);
618 btrfs_mark_buffer_dirty(path->nodes[0]);
619 out:
620 btrfs_release_path(root, path);
621 return ret;
622 }
623
624 static noinline int remove_extent_backref(struct btrfs_trans_handle *trans,
625 struct btrfs_root *root,
626 struct btrfs_path *path,
627 int refs_to_drop)
628 {
629 struct extent_buffer *leaf;
630 struct btrfs_extent_ref *ref;
631 u32 num_refs;
632 int ret = 0;
633
634 leaf = path->nodes[0];
635 ref = btrfs_item_ptr(leaf, path->slots[0], struct btrfs_extent_ref);
636 num_refs = btrfs_ref_num_refs(leaf, ref);
637 BUG_ON(num_refs < refs_to_drop);
638 num_refs -= refs_to_drop;
639 if (num_refs == 0) {
640 ret = btrfs_del_item(trans, root, path);
641 } else {
642 btrfs_set_ref_num_refs(leaf, ref, num_refs);
643 btrfs_mark_buffer_dirty(leaf);
644 }
645 btrfs_release_path(root, path);
646 return ret;
647 }
648
649 #ifdef BIO_RW_DISCARD
650 static void btrfs_issue_discard(struct block_device *bdev,
651 u64 start, u64 len)
652 {
653 blkdev_issue_discard(bdev, start >> 9, len >> 9, GFP_KERNEL);
654 }
655 #endif
656
657 static int btrfs_discard_extent(struct btrfs_root *root, u64 bytenr,
658 u64 num_bytes)
659 {
660 #ifdef BIO_RW_DISCARD
661 int ret;
662 u64 map_length = num_bytes;
663 struct btrfs_multi_bio *multi = NULL;
664
665 /* Tell the block device(s) that the sectors can be discarded */
666 ret = btrfs_map_block(&root->fs_info->mapping_tree, READ,
667 bytenr, &map_length, &multi, 0);
668 if (!ret) {
669 struct btrfs_bio_stripe *stripe = multi->stripes;
670 int i;
671
672 if (map_length > num_bytes)
673 map_length = num_bytes;
674
675 for (i = 0; i < multi->num_stripes; i++, stripe++) {
676 btrfs_issue_discard(stripe->dev->bdev,
677 stripe->physical,
678 map_length);
679 }
680 kfree(multi);
681 }
682
683 return ret;
684 #else
685 return 0;
686 #endif
687 }
688
689 static int __btrfs_update_extent_ref(struct btrfs_trans_handle *trans,
690 struct btrfs_root *root, u64 bytenr,
691 u64 num_bytes,
692 u64 orig_parent, u64 parent,
693 u64 orig_root, u64 ref_root,
694 u64 orig_generation, u64 ref_generation,
695 u64 owner_objectid)
696 {
697 int ret;
698 int pin = owner_objectid < BTRFS_FIRST_FREE_OBJECTID;
699
700 ret = btrfs_update_delayed_ref(trans, bytenr, num_bytes,
701 orig_parent, parent, orig_root,
702 ref_root, orig_generation,
703 ref_generation, owner_objectid, pin);
704 BUG_ON(ret);
705 return ret;
706 }
707
708 int btrfs_update_extent_ref(struct btrfs_trans_handle *trans,
709 struct btrfs_root *root, u64 bytenr,
710 u64 num_bytes, u64 orig_parent, u64 parent,
711 u64 ref_root, u64 ref_generation,
712 u64 owner_objectid)
713 {
714 int ret;
715 if (ref_root == BTRFS_TREE_LOG_OBJECTID &&
716 owner_objectid < BTRFS_FIRST_FREE_OBJECTID)
717 return 0;
718
719 ret = __btrfs_update_extent_ref(trans, root, bytenr, num_bytes,
720 orig_parent, parent, ref_root,
721 ref_root, ref_generation,
722 ref_generation, owner_objectid);
723 return ret;
724 }
725 static int __btrfs_inc_extent_ref(struct btrfs_trans_handle *trans,
726 struct btrfs_root *root, u64 bytenr,
727 u64 num_bytes,
728 u64 orig_parent, u64 parent,
729 u64 orig_root, u64 ref_root,
730 u64 orig_generation, u64 ref_generation,
731 u64 owner_objectid)
732 {
733 int ret;
734
735 ret = btrfs_add_delayed_ref(trans, bytenr, num_bytes, parent, ref_root,
736 ref_generation, owner_objectid,
737 BTRFS_ADD_DELAYED_REF, 0);
738 BUG_ON(ret);
739 return ret;
740 }
741
742 static noinline_for_stack int add_extent_ref(struct btrfs_trans_handle *trans,
743 struct btrfs_root *root, u64 bytenr,
744 u64 num_bytes, u64 parent, u64 ref_root,
745 u64 ref_generation, u64 owner_objectid,
746 int refs_to_add)
747 {
748 struct btrfs_path *path;
749 int ret;
750 struct btrfs_key key;
751 struct extent_buffer *l;
752 struct btrfs_extent_item *item;
753 u32 refs;
754
755 path = btrfs_alloc_path();
756 if (!path)
757 return -ENOMEM;
758
759 path->reada = 1;
760 path->leave_spinning = 1;
761 key.objectid = bytenr;
762 key.type = BTRFS_EXTENT_ITEM_KEY;
763 key.offset = num_bytes;
764
765 /* first find the extent item and update its reference count */
766 ret = btrfs_search_slot(trans, root->fs_info->extent_root, &key,
767 path, 0, 1);
768 if (ret < 0) {
769 btrfs_set_path_blocking(path);
770 return ret;
771 }
772
773 if (ret > 0) {
774 WARN_ON(1);
775 btrfs_free_path(path);
776 return -EIO;
777 }
778 l = path->nodes[0];
779
780 btrfs_item_key_to_cpu(l, &key, path->slots[0]);
781 if (key.objectid != bytenr) {
782 btrfs_print_leaf(root->fs_info->extent_root, path->nodes[0]);
783 printk(KERN_ERR "btrfs wanted %llu found %llu\n",
784 (unsigned long long)bytenr,
785 (unsigned long long)key.objectid);
786 BUG();
787 }
788 BUG_ON(key.type != BTRFS_EXTENT_ITEM_KEY);
789
790 item = btrfs_item_ptr(l, path->slots[0], struct btrfs_extent_item);
791
792 refs = btrfs_extent_refs(l, item);
793 btrfs_set_extent_refs(l, item, refs + refs_to_add);
794 btrfs_unlock_up_safe(path, 1);
795
796 btrfs_mark_buffer_dirty(path->nodes[0]);
797
798 btrfs_release_path(root->fs_info->extent_root, path);
799
800 path->reada = 1;
801 path->leave_spinning = 1;
802
803 /* now insert the actual backref */
804 ret = insert_extent_backref(trans, root->fs_info->extent_root,
805 path, bytenr, parent,
806 ref_root, ref_generation,
807 owner_objectid, refs_to_add);
808 BUG_ON(ret);
809 btrfs_free_path(path);
810 return 0;
811 }
812
813 int btrfs_inc_extent_ref(struct btrfs_trans_handle *trans,
814 struct btrfs_root *root,
815 u64 bytenr, u64 num_bytes, u64 parent,
816 u64 ref_root, u64 ref_generation,
817 u64 owner_objectid)
818 {
819 int ret;
820 if (ref_root == BTRFS_TREE_LOG_OBJECTID &&
821 owner_objectid < BTRFS_FIRST_FREE_OBJECTID)
822 return 0;
823
824 ret = __btrfs_inc_extent_ref(trans, root, bytenr, num_bytes, 0, parent,
825 0, ref_root, 0, ref_generation,
826 owner_objectid);
827 return ret;
828 }
829
830 static int drop_delayed_ref(struct btrfs_trans_handle *trans,
831 struct btrfs_root *root,
832 struct btrfs_delayed_ref_node *node)
833 {
834 int ret = 0;
835 struct btrfs_delayed_ref *ref = btrfs_delayed_node_to_ref(node);
836
837 BUG_ON(node->ref_mod == 0);
838 ret = __btrfs_free_extent(trans, root, node->bytenr, node->num_bytes,
839 node->parent, ref->root, ref->generation,
840 ref->owner_objectid, ref->pin, node->ref_mod);
841
842 return ret;
843 }
844
845 /* helper function to actually process a single delayed ref entry */
846 static noinline int run_one_delayed_ref(struct btrfs_trans_handle *trans,
847 struct btrfs_root *root,
848 struct btrfs_delayed_ref_node *node,
849 int insert_reserved)
850 {
851 int ret;
852 struct btrfs_delayed_ref *ref;
853
854 if (node->parent == (u64)-1) {
855 struct btrfs_delayed_ref_head *head;
856 /*
857 * we've hit the end of the chain and we were supposed
858 * to insert this extent into the tree. But, it got
859 * deleted before we ever needed to insert it, so all
860 * we have to do is clean up the accounting
861 */
862 if (insert_reserved) {
863 update_reserved_extents(root, node->bytenr,
864 node->num_bytes, 0);
865 }
866 head = btrfs_delayed_node_to_head(node);
867 mutex_unlock(&head->mutex);
868 return 0;
869 }
870
871 ref = btrfs_delayed_node_to_ref(node);
872 if (ref->action == BTRFS_ADD_DELAYED_REF) {
873 if (insert_reserved) {
874 struct btrfs_key ins;
875
876 ins.objectid = node->bytenr;
877 ins.offset = node->num_bytes;
878 ins.type = BTRFS_EXTENT_ITEM_KEY;
879
880 /* record the full extent allocation */
881 ret = __btrfs_alloc_reserved_extent(trans, root,
882 node->parent, ref->root,
883 ref->generation, ref->owner_objectid,
884 &ins, node->ref_mod);
885 update_reserved_extents(root, node->bytenr,
886 node->num_bytes, 0);
887 } else {
888 /* just add one backref */
889 ret = add_extent_ref(trans, root, node->bytenr,
890 node->num_bytes,
891 node->parent, ref->root, ref->generation,
892 ref->owner_objectid, node->ref_mod);
893 }
894 BUG_ON(ret);
895 } else if (ref->action == BTRFS_DROP_DELAYED_REF) {
896 WARN_ON(insert_reserved);
897 ret = drop_delayed_ref(trans, root, node);
898 }
899 return 0;
900 }
901
902 static noinline struct btrfs_delayed_ref_node *
903 select_delayed_ref(struct btrfs_delayed_ref_head *head)
904 {
905 struct rb_node *node;
906 struct btrfs_delayed_ref_node *ref;
907 int action = BTRFS_ADD_DELAYED_REF;
908 again:
909 /*
910 * select delayed ref of type BTRFS_ADD_DELAYED_REF first.
911 * this prevents ref count from going down to zero when
912 * there still are pending delayed ref.
913 */
914 node = rb_prev(&head->node.rb_node);
915 while (1) {
916 if (!node)
917 break;
918 ref = rb_entry(node, struct btrfs_delayed_ref_node,
919 rb_node);
920 if (ref->bytenr != head->node.bytenr)
921 break;
922 if (btrfs_delayed_node_to_ref(ref)->action == action)
923 return ref;
924 node = rb_prev(node);
925 }
926 if (action == BTRFS_ADD_DELAYED_REF) {
927 action = BTRFS_DROP_DELAYED_REF;
928 goto again;
929 }
930 return NULL;
931 }
932
933 static noinline int run_clustered_refs(struct btrfs_trans_handle *trans,
934 struct btrfs_root *root,
935 struct list_head *cluster)
936 {
937 struct btrfs_delayed_ref_root *delayed_refs;
938 struct btrfs_delayed_ref_node *ref;
939 struct btrfs_delayed_ref_head *locked_ref = NULL;
940 int ret;
941 int count = 0;
942 int must_insert_reserved = 0;
943
944 delayed_refs = &trans->transaction->delayed_refs;
945 while (1) {
946 if (!locked_ref) {
947 /* pick a new head ref from the cluster list */
948 if (list_empty(cluster))
949 break;
950
951 locked_ref = list_entry(cluster->next,
952 struct btrfs_delayed_ref_head, cluster);
953
954 /* grab the lock that says we are going to process
955 * all the refs for this head */
956 ret = btrfs_delayed_ref_lock(trans, locked_ref);
957
958 /*
959 * we may have dropped the spin lock to get the head
960 * mutex lock, and that might have given someone else
961 * time to free the head. If that's true, it has been
962 * removed from our list and we can move on.
963 */
964 if (ret == -EAGAIN) {
965 locked_ref = NULL;
966 count++;
967 continue;
968 }
969 }
970
971 /*
972 * record the must insert reserved flag before we
973 * drop the spin lock.
974 */
975 must_insert_reserved = locked_ref->must_insert_reserved;
976 locked_ref->must_insert_reserved = 0;
977
978 /*
979 * locked_ref is the head node, so we have to go one
980 * node back for any delayed ref updates
981 */
982 ref = select_delayed_ref(locked_ref);
983 if (!ref) {
984 /* All delayed refs have been processed, Go ahead
985 * and send the head node to run_one_delayed_ref,
986 * so that any accounting fixes can happen
987 */
988 ref = &locked_ref->node;
989 list_del_init(&locked_ref->cluster);
990 locked_ref = NULL;
991 }
992
993 ref->in_tree = 0;
994 rb_erase(&ref->rb_node, &delayed_refs->root);
995 delayed_refs->num_entries--;
996 spin_unlock(&delayed_refs->lock);
997
998 ret = run_one_delayed_ref(trans, root, ref,
999 must_insert_reserved);
1000 BUG_ON(ret);
1001 btrfs_put_delayed_ref(ref);
1002
1003 count++;
1004 cond_resched();
1005 spin_lock(&delayed_refs->lock);
1006 }
1007 return count;
1008 }
1009
1010 /*
1011 * this starts processing the delayed reference count updates and
1012 * extent insertions we have queued up so far. count can be
1013 * 0, which means to process everything in the tree at the start
1014 * of the run (but not newly added entries), or it can be some target
1015 * number you'd like to process.
1016 */
1017 int btrfs_run_delayed_refs(struct btrfs_trans_handle *trans,
1018 struct btrfs_root *root, unsigned long count)
1019 {
1020 struct rb_node *node;
1021 struct btrfs_delayed_ref_root *delayed_refs;
1022 struct btrfs_delayed_ref_node *ref;
1023 struct list_head cluster;
1024 int ret;
1025 int run_all = count == (unsigned long)-1;
1026 int run_most = 0;
1027
1028 if (root == root->fs_info->extent_root)
1029 root = root->fs_info->tree_root;
1030
1031 delayed_refs = &trans->transaction->delayed_refs;
1032 INIT_LIST_HEAD(&cluster);
1033 again:
1034 spin_lock(&delayed_refs->lock);
1035 if (count == 0) {
1036 count = delayed_refs->num_entries * 2;
1037 run_most = 1;
1038 }
1039 while (1) {
1040 if (!(run_all || run_most) &&
1041 delayed_refs->num_heads_ready < 64)
1042 break;
1043
1044 /*
1045 * go find something we can process in the rbtree. We start at
1046 * the beginning of the tree, and then build a cluster
1047 * of refs to process starting at the first one we are able to
1048 * lock
1049 */
1050 ret = btrfs_find_ref_cluster(trans, &cluster,
1051 delayed_refs->run_delayed_start);
1052 if (ret)
1053 break;
1054
1055 ret = run_clustered_refs(trans, root, &cluster);
1056 BUG_ON(ret < 0);
1057
1058 count -= min_t(unsigned long, ret, count);
1059
1060 if (count == 0)
1061 break;
1062 }
1063
1064 if (run_all) {
1065 node = rb_first(&delayed_refs->root);
1066 if (!node)
1067 goto out;
1068 count = (unsigned long)-1;
1069
1070 while (node) {
1071 ref = rb_entry(node, struct btrfs_delayed_ref_node,
1072 rb_node);
1073 if (btrfs_delayed_ref_is_head(ref)) {
1074 struct btrfs_delayed_ref_head *head;
1075
1076 head = btrfs_delayed_node_to_head(ref);
1077 atomic_inc(&ref->refs);
1078
1079 spin_unlock(&delayed_refs->lock);
1080 mutex_lock(&head->mutex);
1081 mutex_unlock(&head->mutex);
1082
1083 btrfs_put_delayed_ref(ref);
1084 cond_resched();
1085 goto again;
1086 }
1087 node = rb_next(node);
1088 }
1089 spin_unlock(&delayed_refs->lock);
1090 schedule_timeout(1);
1091 goto again;
1092 }
1093 out:
1094 spin_unlock(&delayed_refs->lock);
1095 return 0;
1096 }
1097
1098 int btrfs_cross_ref_exist(struct btrfs_trans_handle *trans,
1099 struct btrfs_root *root, u64 objectid, u64 bytenr)
1100 {
1101 struct btrfs_root *extent_root = root->fs_info->extent_root;
1102 struct btrfs_path *path;
1103 struct extent_buffer *leaf;
1104 struct btrfs_extent_ref *ref_item;
1105 struct btrfs_key key;
1106 struct btrfs_key found_key;
1107 u64 ref_root;
1108 u64 last_snapshot;
1109 u32 nritems;
1110 int ret;
1111
1112 key.objectid = bytenr;
1113 key.offset = (u64)-1;
1114 key.type = BTRFS_EXTENT_ITEM_KEY;
1115
1116 path = btrfs_alloc_path();
1117 ret = btrfs_search_slot(NULL, extent_root, &key, path, 0, 0);
1118 if (ret < 0)
1119 goto out;
1120 BUG_ON(ret == 0);
1121
1122 ret = -ENOENT;
1123 if (path->slots[0] == 0)
1124 goto out;
1125
1126 path->slots[0]--;
1127 leaf = path->nodes[0];
1128 btrfs_item_key_to_cpu(leaf, &found_key, path->slots[0]);
1129
1130 if (found_key.objectid != bytenr ||
1131 found_key.type != BTRFS_EXTENT_ITEM_KEY)
1132 goto out;
1133
1134 last_snapshot = btrfs_root_last_snapshot(&root->root_item);
1135 while (1) {
1136 leaf = path->nodes[0];
1137 nritems = btrfs_header_nritems(leaf);
1138 if (path->slots[0] >= nritems) {
1139 ret = btrfs_next_leaf(extent_root, path);
1140 if (ret < 0)
1141 goto out;
1142 if (ret == 0)
1143 continue;
1144 break;
1145 }
1146 btrfs_item_key_to_cpu(leaf, &found_key, path->slots[0]);
1147 if (found_key.objectid != bytenr)
1148 break;
1149
1150 if (found_key.type != BTRFS_EXTENT_REF_KEY) {
1151 path->slots[0]++;
1152 continue;
1153 }
1154
1155 ref_item = btrfs_item_ptr(leaf, path->slots[0],
1156 struct btrfs_extent_ref);
1157 ref_root = btrfs_ref_root(leaf, ref_item);
1158 if ((ref_root != root->root_key.objectid &&
1159 ref_root != BTRFS_TREE_LOG_OBJECTID) ||
1160 objectid != btrfs_ref_objectid(leaf, ref_item)) {
1161 ret = 1;
1162 goto out;
1163 }
1164 if (btrfs_ref_generation(leaf, ref_item) <= last_snapshot) {
1165 ret = 1;
1166 goto out;
1167 }
1168
1169 path->slots[0]++;
1170 }
1171 ret = 0;
1172 out:
1173 btrfs_free_path(path);
1174 return ret;
1175 }
1176
1177 int btrfs_cache_ref(struct btrfs_trans_handle *trans, struct btrfs_root *root,
1178 struct extent_buffer *buf, u32 nr_extents)
1179 {
1180 struct btrfs_key key;
1181 struct btrfs_file_extent_item *fi;
1182 u64 root_gen;
1183 u32 nritems;
1184 int i;
1185 int level;
1186 int ret = 0;
1187 int shared = 0;
1188
1189 if (!root->ref_cows)
1190 return 0;
1191
1192 if (root->root_key.objectid != BTRFS_TREE_RELOC_OBJECTID) {
1193 shared = 0;
1194 root_gen = root->root_key.offset;
1195 } else {
1196 shared = 1;
1197 root_gen = trans->transid - 1;
1198 }
1199
1200 level = btrfs_header_level(buf);
1201 nritems = btrfs_header_nritems(buf);
1202
1203 if (level == 0) {
1204 struct btrfs_leaf_ref *ref;
1205 struct btrfs_extent_info *info;
1206
1207 ref = btrfs_alloc_leaf_ref(root, nr_extents);
1208 if (!ref) {
1209 ret = -ENOMEM;
1210 goto out;
1211 }
1212
1213 ref->root_gen = root_gen;
1214 ref->bytenr = buf->start;
1215 ref->owner = btrfs_header_owner(buf);
1216 ref->generation = btrfs_header_generation(buf);
1217 ref->nritems = nr_extents;
1218 info = ref->extents;
1219
1220 for (i = 0; nr_extents > 0 && i < nritems; i++) {
1221 u64 disk_bytenr;
1222 btrfs_item_key_to_cpu(buf, &key, i);
1223 if (btrfs_key_type(&key) != BTRFS_EXTENT_DATA_KEY)
1224 continue;
1225 fi = btrfs_item_ptr(buf, i,
1226 struct btrfs_file_extent_item);
1227 if (btrfs_file_extent_type(buf, fi) ==
1228 BTRFS_FILE_EXTENT_INLINE)
1229 continue;
1230 disk_bytenr = btrfs_file_extent_disk_bytenr(buf, fi);
1231 if (disk_bytenr == 0)
1232 continue;
1233
1234 info->bytenr = disk_bytenr;
1235 info->num_bytes =
1236 btrfs_file_extent_disk_num_bytes(buf, fi);
1237 info->objectid = key.objectid;
1238 info->offset = key.offset;
1239 info++;
1240 }
1241
1242 ret = btrfs_add_leaf_ref(root, ref, shared);
1243 if (ret == -EEXIST && shared) {
1244 struct btrfs_leaf_ref *old;
1245 old = btrfs_lookup_leaf_ref(root, ref->bytenr);
1246 BUG_ON(!old);
1247 btrfs_remove_leaf_ref(root, old);
1248 btrfs_free_leaf_ref(root, old);
1249 ret = btrfs_add_leaf_ref(root, ref, shared);
1250 }
1251 WARN_ON(ret);
1252 btrfs_free_leaf_ref(root, ref);
1253 }
1254 out:
1255 return ret;
1256 }
1257
1258 /* when a block goes through cow, we update the reference counts of
1259 * everything that block points to. The internal pointers of the block
1260 * can be in just about any order, and it is likely to have clusters of
1261 * things that are close together and clusters of things that are not.
1262 *
1263 * To help reduce the seeks that come with updating all of these reference
1264 * counts, sort them by byte number before actual updates are done.
1265 *
1266 * struct refsort is used to match byte number to slot in the btree block.
1267 * we sort based on the byte number and then use the slot to actually
1268 * find the item.
1269 *
1270 * struct refsort is smaller than strcut btrfs_item and smaller than
1271 * struct btrfs_key_ptr. Since we're currently limited to the page size
1272 * for a btree block, there's no way for a kmalloc of refsorts for a
1273 * single node to be bigger than a page.
1274 */
1275 struct refsort {
1276 u64 bytenr;
1277 u32 slot;
1278 };
1279
1280 /*
1281 * for passing into sort()
1282 */
1283 static int refsort_cmp(const void *a_void, const void *b_void)
1284 {
1285 const struct refsort *a = a_void;
1286 const struct refsort *b = b_void;
1287
1288 if (a->bytenr < b->bytenr)
1289 return -1;
1290 if (a->bytenr > b->bytenr)
1291 return 1;
1292 return 0;
1293 }
1294
1295
1296 noinline int btrfs_inc_ref(struct btrfs_trans_handle *trans,
1297 struct btrfs_root *root,
1298 struct extent_buffer *orig_buf,
1299 struct extent_buffer *buf, u32 *nr_extents)
1300 {
1301 u64 bytenr;
1302 u64 ref_root;
1303 u64 orig_root;
1304 u64 ref_generation;
1305 u64 orig_generation;
1306 struct refsort *sorted;
1307 u32 nritems;
1308 u32 nr_file_extents = 0;
1309 struct btrfs_key key;
1310 struct btrfs_file_extent_item *fi;
1311 int i;
1312 int level;
1313 int ret = 0;
1314 int faili = 0;
1315 int refi = 0;
1316 int slot;
1317 int (*process_func)(struct btrfs_trans_handle *, struct btrfs_root *,
1318 u64, u64, u64, u64, u64, u64, u64, u64, u64);
1319
1320 ref_root = btrfs_header_owner(buf);
1321 ref_generation = btrfs_header_generation(buf);
1322 orig_root = btrfs_header_owner(orig_buf);
1323 orig_generation = btrfs_header_generation(orig_buf);
1324
1325 nritems = btrfs_header_nritems(buf);
1326 level = btrfs_header_level(buf);
1327
1328 sorted = kmalloc(sizeof(struct refsort) * nritems, GFP_NOFS);
1329 BUG_ON(!sorted);
1330
1331 if (root->ref_cows) {
1332 process_func = __btrfs_inc_extent_ref;
1333 } else {
1334 if (level == 0 &&
1335 root->root_key.objectid != BTRFS_TREE_LOG_OBJECTID)
1336 goto out;
1337 if (level != 0 &&
1338 root->root_key.objectid == BTRFS_TREE_LOG_OBJECTID)
1339 goto out;
1340 process_func = __btrfs_update_extent_ref;
1341 }
1342
1343 /*
1344 * we make two passes through the items. In the first pass we
1345 * only record the byte number and slot. Then we sort based on
1346 * byte number and do the actual work based on the sorted results
1347 */
1348 for (i = 0; i < nritems; i++) {
1349 cond_resched();
1350 if (level == 0) {
1351 btrfs_item_key_to_cpu(buf, &key, i);
1352 if (btrfs_key_type(&key) != BTRFS_EXTENT_DATA_KEY)
1353 continue;
1354 fi = btrfs_item_ptr(buf, i,
1355 struct btrfs_file_extent_item);
1356 if (btrfs_file_extent_type(buf, fi) ==
1357 BTRFS_FILE_EXTENT_INLINE)
1358 continue;
1359 bytenr = btrfs_file_extent_disk_bytenr(buf, fi);
1360 if (bytenr == 0)
1361 continue;
1362
1363 nr_file_extents++;
1364 sorted[refi].bytenr = bytenr;
1365 sorted[refi].slot = i;
1366 refi++;
1367 } else {
1368 bytenr = btrfs_node_blockptr(buf, i);
1369 sorted[refi].bytenr = bytenr;
1370 sorted[refi].slot = i;
1371 refi++;
1372 }
1373 }
1374 /*
1375 * if refi == 0, we didn't actually put anything into the sorted
1376 * array and we're done
1377 */
1378 if (refi == 0)
1379 goto out;
1380
1381 sort(sorted, refi, sizeof(struct refsort), refsort_cmp, NULL);
1382
1383 for (i = 0; i < refi; i++) {
1384 cond_resched();
1385 slot = sorted[i].slot;
1386 bytenr = sorted[i].bytenr;
1387
1388 if (level == 0) {
1389 btrfs_item_key_to_cpu(buf, &key, slot);
1390 fi = btrfs_item_ptr(buf, slot,
1391 struct btrfs_file_extent_item);
1392
1393 bytenr = btrfs_file_extent_disk_bytenr(buf, fi);
1394 if (bytenr == 0)
1395 continue;
1396
1397 ret = process_func(trans, root, bytenr,
1398 btrfs_file_extent_disk_num_bytes(buf, fi),
1399 orig_buf->start, buf->start,
1400 orig_root, ref_root,
1401 orig_generation, ref_generation,
1402 key.objectid);
1403
1404 if (ret) {
1405 faili = slot;
1406 WARN_ON(1);
1407 goto fail;
1408 }
1409 } else {
1410 ret = process_func(trans, root, bytenr, buf->len,
1411 orig_buf->start, buf->start,
1412 orig_root, ref_root,
1413 orig_generation, ref_generation,
1414 level - 1);
1415 if (ret) {
1416 faili = slot;
1417 WARN_ON(1);
1418 goto fail;
1419 }
1420 }
1421 }
1422 out:
1423 kfree(sorted);
1424 if (nr_extents) {
1425 if (level == 0)
1426 *nr_extents = nr_file_extents;
1427 else
1428 *nr_extents = nritems;
1429 }
1430 return 0;
1431 fail:
1432 kfree(sorted);
1433 WARN_ON(1);
1434 return ret;
1435 }
1436
1437 int btrfs_update_ref(struct btrfs_trans_handle *trans,
1438 struct btrfs_root *root, struct extent_buffer *orig_buf,
1439 struct extent_buffer *buf, int start_slot, int nr)
1440
1441 {
1442 u64 bytenr;
1443 u64 ref_root;
1444 u64 orig_root;
1445 u64 ref_generation;
1446 u64 orig_generation;
1447 struct btrfs_key key;
1448 struct btrfs_file_extent_item *fi;
1449 int i;
1450 int ret;
1451 int slot;
1452 int level;
1453
1454 BUG_ON(start_slot < 0);
1455 BUG_ON(start_slot + nr > btrfs_header_nritems(buf));
1456
1457 ref_root = btrfs_header_owner(buf);
1458 ref_generation = btrfs_header_generation(buf);
1459 orig_root = btrfs_header_owner(orig_buf);
1460 orig_generation = btrfs_header_generation(orig_buf);
1461 level = btrfs_header_level(buf);
1462
1463 if (!root->ref_cows) {
1464 if (level == 0 &&
1465 root->root_key.objectid != BTRFS_TREE_LOG_OBJECTID)
1466 return 0;
1467 if (level != 0 &&
1468 root->root_key.objectid == BTRFS_TREE_LOG_OBJECTID)
1469 return 0;
1470 }
1471
1472 for (i = 0, slot = start_slot; i < nr; i++, slot++) {
1473 cond_resched();
1474 if (level == 0) {
1475 btrfs_item_key_to_cpu(buf, &key, slot);
1476 if (btrfs_key_type(&key) != BTRFS_EXTENT_DATA_KEY)
1477 continue;
1478 fi = btrfs_item_ptr(buf, slot,
1479 struct btrfs_file_extent_item);
1480 if (btrfs_file_extent_type(buf, fi) ==
1481 BTRFS_FILE_EXTENT_INLINE)
1482 continue;
1483 bytenr = btrfs_file_extent_disk_bytenr(buf, fi);
1484 if (bytenr == 0)
1485 continue;
1486 ret = __btrfs_update_extent_ref(trans, root, bytenr,
1487 btrfs_file_extent_disk_num_bytes(buf, fi),
1488 orig_buf->start, buf->start,
1489 orig_root, ref_root, orig_generation,
1490 ref_generation, key.objectid);
1491 if (ret)
1492 goto fail;
1493 } else {
1494 bytenr = btrfs_node_blockptr(buf, slot);
1495 ret = __btrfs_update_extent_ref(trans, root, bytenr,
1496 buf->len, orig_buf->start,
1497 buf->start, orig_root, ref_root,
1498 orig_generation, ref_generation,
1499 level - 1);
1500 if (ret)
1501 goto fail;
1502 }
1503 }
1504 return 0;
1505 fail:
1506 WARN_ON(1);
1507 return -1;
1508 }
1509
1510 static int write_one_cache_group(struct btrfs_trans_handle *trans,
1511 struct btrfs_root *root,
1512 struct btrfs_path *path,
1513 struct btrfs_block_group_cache *cache)
1514 {
1515 int ret;
1516 struct btrfs_root *extent_root = root->fs_info->extent_root;
1517 unsigned long bi;
1518 struct extent_buffer *leaf;
1519
1520 ret = btrfs_search_slot(trans, extent_root, &cache->key, path, 0, 1);
1521 if (ret < 0)
1522 goto fail;
1523 BUG_ON(ret);
1524
1525 leaf = path->nodes[0];
1526 bi = btrfs_item_ptr_offset(leaf, path->slots[0]);
1527 write_extent_buffer(leaf, &cache->item, bi, sizeof(cache->item));
1528 btrfs_mark_buffer_dirty(leaf);
1529 btrfs_release_path(extent_root, path);
1530 fail:
1531 if (ret)
1532 return ret;
1533 return 0;
1534
1535 }
1536
1537 int btrfs_write_dirty_block_groups(struct btrfs_trans_handle *trans,
1538 struct btrfs_root *root)
1539 {
1540 struct btrfs_block_group_cache *cache, *entry;
1541 struct rb_node *n;
1542 int err = 0;
1543 int werr = 0;
1544 struct btrfs_path *path;
1545 u64 last = 0;
1546
1547 path = btrfs_alloc_path();
1548 if (!path)
1549 return -ENOMEM;
1550
1551 while (1) {
1552 cache = NULL;
1553 spin_lock(&root->fs_info->block_group_cache_lock);
1554 for (n = rb_first(&root->fs_info->block_group_cache_tree);
1555 n; n = rb_next(n)) {
1556 entry = rb_entry(n, struct btrfs_block_group_cache,
1557 cache_node);
1558 if (entry->dirty) {
1559 cache = entry;
1560 break;
1561 }
1562 }
1563 spin_unlock(&root->fs_info->block_group_cache_lock);
1564
1565 if (!cache)
1566 break;
1567
1568 cache->dirty = 0;
1569 last += cache->key.offset;
1570
1571 err = write_one_cache_group(trans, root,
1572 path, cache);
1573 /*
1574 * if we fail to write the cache group, we want
1575 * to keep it marked dirty in hopes that a later
1576 * write will work
1577 */
1578 if (err) {
1579 werr = err;
1580 continue;
1581 }
1582 }
1583 btrfs_free_path(path);
1584 return werr;
1585 }
1586
1587 int btrfs_extent_readonly(struct btrfs_root *root, u64 bytenr)
1588 {
1589 struct btrfs_block_group_cache *block_group;
1590 int readonly = 0;
1591
1592 block_group = btrfs_lookup_block_group(root->fs_info, bytenr);
1593 if (!block_group || block_group->ro)
1594 readonly = 1;
1595 if (block_group)
1596 btrfs_put_block_group(block_group);
1597 return readonly;
1598 }
1599
1600 static int update_space_info(struct btrfs_fs_info *info, u64 flags,
1601 u64 total_bytes, u64 bytes_used,
1602 struct btrfs_space_info **space_info)
1603 {
1604 struct btrfs_space_info *found;
1605
1606 found = __find_space_info(info, flags);
1607 if (found) {
1608 spin_lock(&found->lock);
1609 found->total_bytes += total_bytes;
1610 found->bytes_used += bytes_used;
1611 found->full = 0;
1612 spin_unlock(&found->lock);
1613 *space_info = found;
1614 return 0;
1615 }
1616 found = kzalloc(sizeof(*found), GFP_NOFS);
1617 if (!found)
1618 return -ENOMEM;
1619
1620 INIT_LIST_HEAD(&found->block_groups);
1621 init_rwsem(&found->groups_sem);
1622 spin_lock_init(&found->lock);
1623 found->flags = flags;
1624 found->total_bytes = total_bytes;
1625 found->bytes_used = bytes_used;
1626 found->bytes_pinned = 0;
1627 found->bytes_reserved = 0;
1628 found->bytes_readonly = 0;
1629 found->bytes_delalloc = 0;
1630 found->full = 0;
1631 found->force_alloc = 0;
1632 *space_info = found;
1633 list_add_rcu(&found->list, &info->space_info);
1634 return 0;
1635 }
1636
1637 static void set_avail_alloc_bits(struct btrfs_fs_info *fs_info, u64 flags)
1638 {
1639 u64 extra_flags = flags & (BTRFS_BLOCK_GROUP_RAID0 |
1640 BTRFS_BLOCK_GROUP_RAID1 |
1641 BTRFS_BLOCK_GROUP_RAID10 |
1642 BTRFS_BLOCK_GROUP_DUP);
1643 if (extra_flags) {
1644 if (flags & BTRFS_BLOCK_GROUP_DATA)
1645 fs_info->avail_data_alloc_bits |= extra_flags;
1646 if (flags & BTRFS_BLOCK_GROUP_METADATA)
1647 fs_info->avail_metadata_alloc_bits |= extra_flags;
1648 if (flags & BTRFS_BLOCK_GROUP_SYSTEM)
1649 fs_info->avail_system_alloc_bits |= extra_flags;
1650 }
1651 }
1652
1653 static void set_block_group_readonly(struct btrfs_block_group_cache *cache)
1654 {
1655 spin_lock(&cache->space_info->lock);
1656 spin_lock(&cache->lock);
1657 if (!cache->ro) {
1658 cache->space_info->bytes_readonly += cache->key.offset -
1659 btrfs_block_group_used(&cache->item);
1660 cache->ro = 1;
1661 }
1662 spin_unlock(&cache->lock);
1663 spin_unlock(&cache->space_info->lock);
1664 }
1665
1666 u64 btrfs_reduce_alloc_profile(struct btrfs_root *root, u64 flags)
1667 {
1668 u64 num_devices = root->fs_info->fs_devices->rw_devices;
1669
1670 if (num_devices == 1)
1671 flags &= ~(BTRFS_BLOCK_GROUP_RAID1 | BTRFS_BLOCK_GROUP_RAID0);
1672 if (num_devices < 4)
1673 flags &= ~BTRFS_BLOCK_GROUP_RAID10;
1674
1675 if ((flags & BTRFS_BLOCK_GROUP_DUP) &&
1676 (flags & (BTRFS_BLOCK_GROUP_RAID1 |
1677 BTRFS_BLOCK_GROUP_RAID10))) {
1678 flags &= ~BTRFS_BLOCK_GROUP_DUP;
1679 }
1680
1681 if ((flags & BTRFS_BLOCK_GROUP_RAID1) &&
1682 (flags & BTRFS_BLOCK_GROUP_RAID10)) {
1683 flags &= ~BTRFS_BLOCK_GROUP_RAID1;
1684 }
1685
1686 if ((flags & BTRFS_BLOCK_GROUP_RAID0) &&
1687 ((flags & BTRFS_BLOCK_GROUP_RAID1) |
1688 (flags & BTRFS_BLOCK_GROUP_RAID10) |
1689 (flags & BTRFS_BLOCK_GROUP_DUP)))
1690 flags &= ~BTRFS_BLOCK_GROUP_RAID0;
1691 return flags;
1692 }
1693
1694 static u64 btrfs_get_alloc_profile(struct btrfs_root *root, u64 data)
1695 {
1696 struct btrfs_fs_info *info = root->fs_info;
1697 u64 alloc_profile;
1698
1699 if (data) {
1700 alloc_profile = info->avail_data_alloc_bits &
1701 info->data_alloc_profile;
1702 data = BTRFS_BLOCK_GROUP_DATA | alloc_profile;
1703 } else if (root == root->fs_info->chunk_root) {
1704 alloc_profile = info->avail_system_alloc_bits &
1705 info->system_alloc_profile;
1706 data = BTRFS_BLOCK_GROUP_SYSTEM | alloc_profile;
1707 } else {
1708 alloc_profile = info->avail_metadata_alloc_bits &
1709 info->metadata_alloc_profile;
1710 data = BTRFS_BLOCK_GROUP_METADATA | alloc_profile;
1711 }
1712
1713 return btrfs_reduce_alloc_profile(root, data);
1714 }
1715
1716 void btrfs_set_inode_space_info(struct btrfs_root *root, struct inode *inode)
1717 {
1718 u64 alloc_target;
1719
1720 alloc_target = btrfs_get_alloc_profile(root, 1);
1721 BTRFS_I(inode)->space_info = __find_space_info(root->fs_info,
1722 alloc_target);
1723 }
1724
1725 /*
1726 * for now this just makes sure we have at least 5% of our metadata space free
1727 * for use.
1728 */
1729 int btrfs_check_metadata_free_space(struct btrfs_root *root)
1730 {
1731 struct btrfs_fs_info *info = root->fs_info;
1732 struct btrfs_space_info *meta_sinfo;
1733 u64 alloc_target, thresh;
1734 int committed = 0, ret;
1735
1736 /* get the space info for where the metadata will live */
1737 alloc_target = btrfs_get_alloc_profile(root, 0);
1738 meta_sinfo = __find_space_info(info, alloc_target);
1739
1740 again:
1741 spin_lock(&meta_sinfo->lock);
1742 if (!meta_sinfo->full)
1743 thresh = meta_sinfo->total_bytes * 80;
1744 else
1745 thresh = meta_sinfo->total_bytes * 95;
1746
1747 do_div(thresh, 100);
1748
1749 if (meta_sinfo->bytes_used + meta_sinfo->bytes_reserved +
1750 meta_sinfo->bytes_pinned + meta_sinfo->bytes_readonly > thresh) {
1751 struct btrfs_trans_handle *trans;
1752 if (!meta_sinfo->full) {
1753 meta_sinfo->force_alloc = 1;
1754 spin_unlock(&meta_sinfo->lock);
1755
1756 trans = btrfs_start_transaction(root, 1);
1757 if (!trans)
1758 return -ENOMEM;
1759
1760 ret = do_chunk_alloc(trans, root->fs_info->extent_root,
1761 2 * 1024 * 1024, alloc_target, 0);
1762 btrfs_end_transaction(trans, root);
1763 goto again;
1764 }
1765 spin_unlock(&meta_sinfo->lock);
1766
1767 if (!committed) {
1768 committed = 1;
1769 trans = btrfs_join_transaction(root, 1);
1770 if (!trans)
1771 return -ENOMEM;
1772 ret = btrfs_commit_transaction(trans, root);
1773 if (ret)
1774 return ret;
1775 goto again;
1776 }
1777 return -ENOSPC;
1778 }
1779 spin_unlock(&meta_sinfo->lock);
1780
1781 return 0;
1782 }
1783
1784 /*
1785 * This will check the space that the inode allocates from to make sure we have
1786 * enough space for bytes.
1787 */
1788 int btrfs_check_data_free_space(struct btrfs_root *root, struct inode *inode,
1789 u64 bytes)
1790 {
1791 struct btrfs_space_info *data_sinfo;
1792 int ret = 0, committed = 0;
1793
1794 /* make sure bytes are sectorsize aligned */
1795 bytes = (bytes + root->sectorsize - 1) & ~((u64)root->sectorsize - 1);
1796
1797 data_sinfo = BTRFS_I(inode)->space_info;
1798 again:
1799 /* make sure we have enough space to handle the data first */
1800 spin_lock(&data_sinfo->lock);
1801 if (data_sinfo->total_bytes - data_sinfo->bytes_used -
1802 data_sinfo->bytes_delalloc - data_sinfo->bytes_reserved -
1803 data_sinfo->bytes_pinned - data_sinfo->bytes_readonly -
1804 data_sinfo->bytes_may_use < bytes) {
1805 struct btrfs_trans_handle *trans;
1806
1807 /*
1808 * if we don't have enough free bytes in this space then we need
1809 * to alloc a new chunk.
1810 */
1811 if (!data_sinfo->full) {
1812 u64 alloc_target;
1813
1814 data_sinfo->force_alloc = 1;
1815 spin_unlock(&data_sinfo->lock);
1816
1817 alloc_target = btrfs_get_alloc_profile(root, 1);
1818 trans = btrfs_start_transaction(root, 1);
1819 if (!trans)
1820 return -ENOMEM;
1821
1822 ret = do_chunk_alloc(trans, root->fs_info->extent_root,
1823 bytes + 2 * 1024 * 1024,
1824 alloc_target, 0);
1825 btrfs_end_transaction(trans, root);
1826 if (ret)
1827 return ret;
1828 goto again;
1829 }
1830 spin_unlock(&data_sinfo->lock);
1831
1832 /* commit the current transaction and try again */
1833 if (!committed) {
1834 committed = 1;
1835 trans = btrfs_join_transaction(root, 1);
1836 if (!trans)
1837 return -ENOMEM;
1838 ret = btrfs_commit_transaction(trans, root);
1839 if (ret)
1840 return ret;
1841 goto again;
1842 }
1843
1844 printk(KERN_ERR "no space left, need %llu, %llu delalloc bytes"
1845 ", %llu bytes_used, %llu bytes_reserved, "
1846 "%llu bytes_pinned, %llu bytes_readonly, %llu may use"
1847 "%llu total\n", (unsigned long long)bytes,
1848 (unsigned long long)data_sinfo->bytes_delalloc,
1849 (unsigned long long)data_sinfo->bytes_used,
1850 (unsigned long long)data_sinfo->bytes_reserved,
1851 (unsigned long long)data_sinfo->bytes_pinned,
1852 (unsigned long long)data_sinfo->bytes_readonly,
1853 (unsigned long long)data_sinfo->bytes_may_use,
1854 (unsigned long long)data_sinfo->total_bytes);
1855 return -ENOSPC;
1856 }
1857 data_sinfo->bytes_may_use += bytes;
1858 BTRFS_I(inode)->reserved_bytes += bytes;
1859 spin_unlock(&data_sinfo->lock);
1860
1861 return btrfs_check_metadata_free_space(root);
1862 }
1863
1864 /*
1865 * if there was an error for whatever reason after calling
1866 * btrfs_check_data_free_space, call this so we can cleanup the counters.
1867 */
1868 void btrfs_free_reserved_data_space(struct btrfs_root *root,
1869 struct inode *inode, u64 bytes)
1870 {
1871 struct btrfs_space_info *data_sinfo;
1872
1873 /* make sure bytes are sectorsize aligned */
1874 bytes = (bytes + root->sectorsize - 1) & ~((u64)root->sectorsize - 1);
1875
1876 data_sinfo = BTRFS_I(inode)->space_info;
1877 spin_lock(&data_sinfo->lock);
1878 data_sinfo->bytes_may_use -= bytes;
1879 BTRFS_I(inode)->reserved_bytes -= bytes;
1880 spin_unlock(&data_sinfo->lock);
1881 }
1882
1883 /* called when we are adding a delalloc extent to the inode's io_tree */
1884 void btrfs_delalloc_reserve_space(struct btrfs_root *root, struct inode *inode,
1885 u64 bytes)
1886 {
1887 struct btrfs_space_info *data_sinfo;
1888
1889 /* get the space info for where this inode will be storing its data */
1890 data_sinfo = BTRFS_I(inode)->space_info;
1891
1892 /* make sure we have enough space to handle the data first */
1893 spin_lock(&data_sinfo->lock);
1894 data_sinfo->bytes_delalloc += bytes;
1895
1896 /*
1897 * we are adding a delalloc extent without calling
1898 * btrfs_check_data_free_space first. This happens on a weird
1899 * writepage condition, but shouldn't hurt our accounting
1900 */
1901 if (unlikely(bytes > BTRFS_I(inode)->reserved_bytes)) {
1902 data_sinfo->bytes_may_use -= BTRFS_I(inode)->reserved_bytes;
1903 BTRFS_I(inode)->reserved_bytes = 0;
1904 } else {
1905 data_sinfo->bytes_may_use -= bytes;
1906 BTRFS_I(inode)->reserved_bytes -= bytes;
1907 }
1908
1909 spin_unlock(&data_sinfo->lock);
1910 }
1911
1912 /* called when we are clearing an delalloc extent from the inode's io_tree */
1913 void btrfs_delalloc_free_space(struct btrfs_root *root, struct inode *inode,
1914 u64 bytes)
1915 {
1916 struct btrfs_space_info *info;
1917
1918 info = BTRFS_I(inode)->space_info;
1919
1920 spin_lock(&info->lock);
1921 info->bytes_delalloc -= bytes;
1922 spin_unlock(&info->lock);
1923 }
1924
1925 static void force_metadata_allocation(struct btrfs_fs_info *info)
1926 {
1927 struct list_head *head = &info->space_info;
1928 struct btrfs_space_info *found;
1929
1930 rcu_read_lock();
1931 list_for_each_entry_rcu(found, head, list) {
1932 if (found->flags & BTRFS_BLOCK_GROUP_METADATA)
1933 found->force_alloc = 1;
1934 }
1935 rcu_read_unlock();
1936 }
1937
1938 static int do_chunk_alloc(struct btrfs_trans_handle *trans,
1939 struct btrfs_root *extent_root, u64 alloc_bytes,
1940 u64 flags, int force)
1941 {
1942 struct btrfs_space_info *space_info;
1943 struct btrfs_fs_info *fs_info = extent_root->fs_info;
1944 u64 thresh;
1945 int ret = 0;
1946
1947 mutex_lock(&fs_info->chunk_mutex);
1948
1949 flags = btrfs_reduce_alloc_profile(extent_root, flags);
1950
1951 space_info = __find_space_info(extent_root->fs_info, flags);
1952 if (!space_info) {
1953 ret = update_space_info(extent_root->fs_info, flags,
1954 0, 0, &space_info);
1955 BUG_ON(ret);
1956 }
1957 BUG_ON(!space_info);
1958
1959 spin_lock(&space_info->lock);
1960 if (space_info->force_alloc) {
1961 force = 1;
1962 space_info->force_alloc = 0;
1963 }
1964 if (space_info->full) {
1965 spin_unlock(&space_info->lock);
1966 goto out;
1967 }
1968
1969 thresh = space_info->total_bytes - space_info->bytes_readonly;
1970 thresh = div_factor(thresh, 6);
1971 if (!force &&
1972 (space_info->bytes_used + space_info->bytes_pinned +
1973 space_info->bytes_reserved + alloc_bytes) < thresh) {
1974 spin_unlock(&space_info->lock);
1975 goto out;
1976 }
1977 spin_unlock(&space_info->lock);
1978
1979 /*
1980 * if we're doing a data chunk, go ahead and make sure that
1981 * we keep a reasonable number of metadata chunks allocated in the
1982 * FS as well.
1983 */
1984 if (flags & BTRFS_BLOCK_GROUP_DATA) {
1985 fs_info->data_chunk_allocations++;
1986 if (!(fs_info->data_chunk_allocations %
1987 fs_info->metadata_ratio))
1988 force_metadata_allocation(fs_info);
1989 }
1990
1991 ret = btrfs_alloc_chunk(trans, extent_root, flags);
1992 if (ret)
1993 space_info->full = 1;
1994 out:
1995 mutex_unlock(&extent_root->fs_info->chunk_mutex);
1996 return ret;
1997 }
1998
1999 static int update_block_group(struct btrfs_trans_handle *trans,
2000 struct btrfs_root *root,
2001 u64 bytenr, u64 num_bytes, int alloc,
2002 int mark_free)
2003 {
2004 struct btrfs_block_group_cache *cache;
2005 struct btrfs_fs_info *info = root->fs_info;
2006 u64 total = num_bytes;
2007 u64 old_val;
2008 u64 byte_in_group;
2009
2010 while (total) {
2011 cache = btrfs_lookup_block_group(info, bytenr);
2012 if (!cache)
2013 return -1;
2014 byte_in_group = bytenr - cache->key.objectid;
2015 WARN_ON(byte_in_group > cache->key.offset);
2016
2017 spin_lock(&cache->space_info->lock);
2018 spin_lock(&cache->lock);
2019 cache->dirty = 1;
2020 old_val = btrfs_block_group_used(&cache->item);
2021 num_bytes = min(total, cache->key.offset - byte_in_group);
2022 if (alloc) {
2023 old_val += num_bytes;
2024 cache->space_info->bytes_used += num_bytes;
2025 if (cache->ro)
2026 cache->space_info->bytes_readonly -= num_bytes;
2027 btrfs_set_block_group_used(&cache->item, old_val);
2028 spin_unlock(&cache->lock);
2029 spin_unlock(&cache->space_info->lock);
2030 } else {
2031 old_val -= num_bytes;
2032 cache->space_info->bytes_used -= num_bytes;
2033 if (cache->ro)
2034 cache->space_info->bytes_readonly += num_bytes;
2035 btrfs_set_block_group_used(&cache->item, old_val);
2036 spin_unlock(&cache->lock);
2037 spin_unlock(&cache->space_info->lock);
2038 if (mark_free) {
2039 int ret;
2040
2041 ret = btrfs_discard_extent(root, bytenr,
2042 num_bytes);
2043 WARN_ON(ret);
2044
2045 ret = btrfs_add_free_space(cache, bytenr,
2046 num_bytes);
2047 WARN_ON(ret);
2048 }
2049 }
2050 btrfs_put_block_group(cache);
2051 total -= num_bytes;
2052 bytenr += num_bytes;
2053 }
2054 return 0;
2055 }
2056
2057 static u64 first_logical_byte(struct btrfs_root *root, u64 search_start)
2058 {
2059 struct btrfs_block_group_cache *cache;
2060 u64 bytenr;
2061
2062 cache = btrfs_lookup_first_block_group(root->fs_info, search_start);
2063 if (!cache)
2064 return 0;
2065
2066 bytenr = cache->key.objectid;
2067 btrfs_put_block_group(cache);
2068
2069 return bytenr;
2070 }
2071
2072 int btrfs_update_pinned_extents(struct btrfs_root *root,
2073 u64 bytenr, u64 num, int pin)
2074 {
2075 u64 len;
2076 struct btrfs_block_group_cache *cache;
2077 struct btrfs_fs_info *fs_info = root->fs_info;
2078
2079 if (pin) {
2080 set_extent_dirty(&fs_info->pinned_extents,
2081 bytenr, bytenr + num - 1, GFP_NOFS);
2082 } else {
2083 clear_extent_dirty(&fs_info->pinned_extents,
2084 bytenr, bytenr + num - 1, GFP_NOFS);
2085 }
2086
2087 while (num > 0) {
2088 cache = btrfs_lookup_block_group(fs_info, bytenr);
2089 BUG_ON(!cache);
2090 len = min(num, cache->key.offset -
2091 (bytenr - cache->key.objectid));
2092 if (pin) {
2093 spin_lock(&cache->space_info->lock);
2094 spin_lock(&cache->lock);
2095 cache->pinned += len;
2096 cache->space_info->bytes_pinned += len;
2097 spin_unlock(&cache->lock);
2098 spin_unlock(&cache->space_info->lock);
2099 fs_info->total_pinned += len;
2100 } else {
2101 spin_lock(&cache->space_info->lock);
2102 spin_lock(&cache->lock);
2103 cache->pinned -= len;
2104 cache->space_info->bytes_pinned -= len;
2105 spin_unlock(&cache->lock);
2106 spin_unlock(&cache->space_info->lock);
2107 fs_info->total_pinned -= len;
2108 if (cache->cached)
2109 btrfs_add_free_space(cache, bytenr, len);
2110 }
2111 btrfs_put_block_group(cache);
2112 bytenr += len;
2113 num -= len;
2114 }
2115 return 0;
2116 }
2117
2118 static int update_reserved_extents(struct btrfs_root *root,
2119 u64 bytenr, u64 num, int reserve)
2120 {
2121 u64 len;
2122 struct btrfs_block_group_cache *cache;
2123 struct btrfs_fs_info *fs_info = root->fs_info;
2124
2125 while (num > 0) {
2126 cache = btrfs_lookup_block_group(fs_info, bytenr);
2127 BUG_ON(!cache);
2128 len = min(num, cache->key.offset -
2129 (bytenr - cache->key.objectid));
2130
2131 spin_lock(&cache->space_info->lock);
2132 spin_lock(&cache->lock);
2133 if (reserve) {
2134 cache->reserved += len;
2135 cache->space_info->bytes_reserved += len;
2136 } else {
2137 cache->reserved -= len;
2138 cache->space_info->bytes_reserved -= len;
2139 }
2140 spin_unlock(&cache->lock);
2141 spin_unlock(&cache->space_info->lock);
2142 btrfs_put_block_group(cache);
2143 bytenr += len;
2144 num -= len;
2145 }
2146 return 0;
2147 }
2148
2149 int btrfs_copy_pinned(struct btrfs_root *root, struct extent_io_tree *copy)
2150 {
2151 u64 last = 0;
2152 u64 start;
2153 u64 end;
2154 struct extent_io_tree *pinned_extents = &root->fs_info->pinned_extents;
2155 int ret;
2156
2157 while (1) {
2158 ret = find_first_extent_bit(pinned_extents, last,
2159 &start, &end, EXTENT_DIRTY);
2160 if (ret)
2161 break;
2162 set_extent_dirty(copy, start, end, GFP_NOFS);
2163 last = end + 1;
2164 }
2165 return 0;
2166 }
2167
2168 int btrfs_finish_extent_commit(struct btrfs_trans_handle *trans,
2169 struct btrfs_root *root,
2170 struct extent_io_tree *unpin)
2171 {
2172 u64 start;
2173 u64 end;
2174 int ret;
2175
2176 while (1) {
2177 ret = find_first_extent_bit(unpin, 0, &start, &end,
2178 EXTENT_DIRTY);
2179 if (ret)
2180 break;
2181
2182 ret = btrfs_discard_extent(root, start, end + 1 - start);
2183
2184 /* unlocks the pinned mutex */
2185 btrfs_update_pinned_extents(root, start, end + 1 - start, 0);
2186 clear_extent_dirty(unpin, start, end, GFP_NOFS);
2187
2188 cond_resched();
2189 }
2190 return ret;
2191 }
2192
2193 static int pin_down_bytes(struct btrfs_trans_handle *trans,
2194 struct btrfs_root *root,
2195 struct btrfs_path *path,
2196 u64 bytenr, u64 num_bytes, int is_data,
2197 struct extent_buffer **must_clean)
2198 {
2199 int err = 0;
2200 struct extent_buffer *buf;
2201
2202 if (is_data)
2203 goto pinit;
2204
2205 buf = btrfs_find_tree_block(root, bytenr, num_bytes);
2206 if (!buf)
2207 goto pinit;
2208
2209 /* we can reuse a block if it hasn't been written
2210 * and it is from this transaction. We can't
2211 * reuse anything from the tree log root because
2212 * it has tiny sub-transactions.
2213 */
2214 if (btrfs_buffer_uptodate(buf, 0) &&
2215 btrfs_try_tree_lock(buf)) {
2216 u64 header_owner = btrfs_header_owner(buf);
2217 u64 header_transid = btrfs_header_generation(buf);
2218 if (header_owner != BTRFS_TREE_LOG_OBJECTID &&
2219 header_owner != BTRFS_TREE_RELOC_OBJECTID &&
2220 header_owner != BTRFS_DATA_RELOC_TREE_OBJECTID &&
2221 header_transid == trans->transid &&
2222 !btrfs_header_flag(buf, BTRFS_HEADER_FLAG_WRITTEN)) {
2223 *must_clean = buf;
2224 return 1;
2225 }
2226 btrfs_tree_unlock(buf);
2227 }
2228 free_extent_buffer(buf);
2229 pinit:
2230 btrfs_set_path_blocking(path);
2231 /* unlocks the pinned mutex */
2232 btrfs_update_pinned_extents(root, bytenr, num_bytes, 1);
2233
2234 BUG_ON(err < 0);
2235 return 0;
2236 }
2237
2238 /*
2239 * remove an extent from the root, returns 0 on success
2240 */
2241 static int __free_extent(struct btrfs_trans_handle *trans,
2242 struct btrfs_root *root,
2243 u64 bytenr, u64 num_bytes, u64 parent,
2244 u64 root_objectid, u64 ref_generation,
2245 u64 owner_objectid, int pin, int mark_free,
2246 int refs_to_drop)
2247 {
2248 struct btrfs_path *path;
2249 struct btrfs_key key;
2250 struct btrfs_fs_info *info = root->fs_info;
2251 struct btrfs_root *extent_root = info->extent_root;
2252 struct extent_buffer *leaf;
2253 int ret;
2254 int extent_slot = 0;
2255 int found_extent = 0;
2256 int num_to_del = 1;
2257 struct btrfs_extent_item *ei;
2258 u32 refs;
2259
2260 key.objectid = bytenr;
2261 btrfs_set_key_type(&key, BTRFS_EXTENT_ITEM_KEY);
2262 key.offset = num_bytes;
2263 path = btrfs_alloc_path();
2264 if (!path)
2265 return -ENOMEM;
2266
2267 path->reada = 1;
2268 path->leave_spinning = 1;
2269 ret = lookup_extent_backref(trans, extent_root, path,
2270 bytenr, parent, root_objectid,
2271 ref_generation, owner_objectid, 1);
2272 if (ret == 0) {
2273 struct btrfs_key found_key;
2274 extent_slot = path->slots[0];
2275 while (extent_slot > 0) {
2276 extent_slot--;
2277 btrfs_item_key_to_cpu(path->nodes[0], &found_key,
2278 extent_slot);
2279 if (found_key.objectid != bytenr)
2280 break;
2281 if (found_key.type == BTRFS_EXTENT_ITEM_KEY &&
2282 found_key.offset == num_bytes) {
2283 found_extent = 1;
2284 break;
2285 }
2286 if (path->slots[0] - extent_slot > 5)
2287 break;
2288 }
2289 if (!found_extent) {
2290 ret = remove_extent_backref(trans, extent_root, path,
2291 refs_to_drop);
2292 BUG_ON(ret);
2293 btrfs_release_path(extent_root, path);
2294 path->leave_spinning = 1;
2295 ret = btrfs_search_slot(trans, extent_root,
2296 &key, path, -1, 1);
2297 if (ret) {
2298 printk(KERN_ERR "umm, got %d back from search"
2299 ", was looking for %llu\n", ret,
2300 (unsigned long long)bytenr);
2301 btrfs_print_leaf(extent_root, path->nodes[0]);
2302 }
2303 BUG_ON(ret);
2304 extent_slot = path->slots[0];
2305 }
2306 } else {
2307 btrfs_print_leaf(extent_root, path->nodes[0]);
2308 WARN_ON(1);
2309 printk(KERN_ERR "btrfs unable to find ref byte nr %llu "
2310 "parent %llu root %llu gen %llu owner %llu\n",
2311 (unsigned long long)bytenr,
2312 (unsigned long long)parent,
2313 (unsigned long long)root_objectid,
2314 (unsigned long long)ref_generation,
2315 (unsigned long long)owner_objectid);
2316 }
2317
2318 leaf = path->nodes[0];
2319 ei = btrfs_item_ptr(leaf, extent_slot,
2320 struct btrfs_extent_item);
2321 refs = btrfs_extent_refs(leaf, ei);
2322
2323 /*
2324 * we're not allowed to delete the extent item if there
2325 * are other delayed ref updates pending
2326 */
2327
2328 BUG_ON(refs < refs_to_drop);
2329 refs -= refs_to_drop;
2330 btrfs_set_extent_refs(leaf, ei, refs);
2331 btrfs_mark_buffer_dirty(leaf);
2332
2333 if (refs == 0 && found_extent &&
2334 path->slots[0] == extent_slot + 1) {
2335 struct btrfs_extent_ref *ref;
2336 ref = btrfs_item_ptr(leaf, path->slots[0],
2337 struct btrfs_extent_ref);
2338 BUG_ON(btrfs_ref_num_refs(leaf, ref) != refs_to_drop);
2339 /* if the back ref and the extent are next to each other
2340 * they get deleted below in one shot
2341 */
2342 path->slots[0] = extent_slot;
2343 num_to_del = 2;
2344 } else if (found_extent) {
2345 /* otherwise delete the extent back ref */
2346 ret = remove_extent_backref(trans, extent_root, path,
2347 refs_to_drop);
2348 BUG_ON(ret);
2349 /* if refs are 0, we need to setup the path for deletion */
2350 if (refs == 0) {
2351 btrfs_release_path(extent_root, path);
2352 path->leave_spinning = 1;
2353 ret = btrfs_search_slot(trans, extent_root, &key, path,
2354 -1, 1);
2355 BUG_ON(ret);
2356 }
2357 }
2358
2359 if (refs == 0) {
2360 u64 super_used;
2361 u64 root_used;
2362 struct extent_buffer *must_clean = NULL;
2363
2364 if (pin) {
2365 ret = pin_down_bytes(trans, root, path,
2366 bytenr, num_bytes,
2367 owner_objectid >= BTRFS_FIRST_FREE_OBJECTID,
2368 &must_clean);
2369 if (ret > 0)
2370 mark_free = 1;
2371 BUG_ON(ret < 0);
2372 }
2373
2374 /* block accounting for super block */
2375 spin_lock(&info->delalloc_lock);
2376 super_used = btrfs_super_bytes_used(&info->super_copy);
2377 btrfs_set_super_bytes_used(&info->super_copy,
2378 super_used - num_bytes);
2379
2380 /* block accounting for root item */
2381 root_used = btrfs_root_used(&root->root_item);
2382 btrfs_set_root_used(&root->root_item,
2383 root_used - num_bytes);
2384 spin_unlock(&info->delalloc_lock);
2385
2386 /*
2387 * it is going to be very rare for someone to be waiting
2388 * on the block we're freeing. del_items might need to
2389 * schedule, so rather than get fancy, just force it
2390 * to blocking here
2391 */
2392 if (must_clean)
2393 btrfs_set_lock_blocking(must_clean);
2394
2395 ret = btrfs_del_items(trans, extent_root, path, path->slots[0],
2396 num_to_del);
2397 BUG_ON(ret);
2398 btrfs_release_path(extent_root, path);
2399
2400 if (must_clean) {
2401 clean_tree_block(NULL, root, must_clean);
2402 btrfs_tree_unlock(must_clean);
2403 free_extent_buffer(must_clean);
2404 }
2405
2406 if (owner_objectid >= BTRFS_FIRST_FREE_OBJECTID) {
2407 ret = btrfs_del_csums(trans, root, bytenr, num_bytes);
2408 BUG_ON(ret);
2409 } else {
2410 invalidate_mapping_pages(info->btree_inode->i_mapping,
2411 bytenr >> PAGE_CACHE_SHIFT,
2412 (bytenr + num_bytes - 1) >> PAGE_CACHE_SHIFT);
2413 }
2414
2415 ret = update_block_group(trans, root, bytenr, num_bytes, 0,
2416 mark_free);
2417 BUG_ON(ret);
2418 }
2419 btrfs_free_path(path);
2420 return ret;
2421 }
2422
2423 /*
2424 * remove an extent from the root, returns 0 on success
2425 */
2426 static int __btrfs_free_extent(struct btrfs_trans_handle *trans,
2427 struct btrfs_root *root,
2428 u64 bytenr, u64 num_bytes, u64 parent,
2429 u64 root_objectid, u64 ref_generation,
2430 u64 owner_objectid, int pin,
2431 int refs_to_drop)
2432 {
2433 WARN_ON(num_bytes < root->sectorsize);
2434
2435 /*
2436 * if metadata always pin
2437 * if data pin when any transaction has committed this
2438 */
2439 if (owner_objectid < BTRFS_FIRST_FREE_OBJECTID ||
2440 ref_generation != trans->transid)
2441 pin = 1;
2442
2443 if (ref_generation != trans->transid)
2444 pin = 1;
2445
2446 return __free_extent(trans, root, bytenr, num_bytes, parent,
2447 root_objectid, ref_generation,
2448 owner_objectid, pin, pin == 0, refs_to_drop);
2449 }
2450
2451 /*
2452 * when we free an extent, it is possible (and likely) that we free the last
2453 * delayed ref for that extent as well. This searches the delayed ref tree for
2454 * a given extent, and if there are no other delayed refs to be processed, it
2455 * removes it from the tree.
2456 */
2457 static noinline int check_ref_cleanup(struct btrfs_trans_handle *trans,
2458 struct btrfs_root *root, u64 bytenr)
2459 {
2460 struct btrfs_delayed_ref_head *head;
2461 struct btrfs_delayed_ref_root *delayed_refs;
2462 struct btrfs_delayed_ref_node *ref;
2463 struct rb_node *node;
2464 int ret;
2465
2466 delayed_refs = &trans->transaction->delayed_refs;
2467 spin_lock(&delayed_refs->lock);
2468 head = btrfs_find_delayed_ref_head(trans, bytenr);
2469 if (!head)
2470 goto out;
2471
2472 node = rb_prev(&head->node.rb_node);
2473 if (!node)
2474 goto out;
2475
2476 ref = rb_entry(node, struct btrfs_delayed_ref_node, rb_node);
2477
2478 /* there are still entries for this ref, we can't drop it */
2479 if (ref->bytenr == bytenr)
2480 goto out;
2481
2482 /*
2483 * waiting for the lock here would deadlock. If someone else has it
2484 * locked they are already in the process of dropping it anyway
2485 */
2486 if (!mutex_trylock(&head->mutex))
2487 goto out;
2488
2489 /*
2490 * at this point we have a head with no other entries. Go
2491 * ahead and process it.
2492 */
2493 head->node.in_tree = 0;
2494 rb_erase(&head->node.rb_node, &delayed_refs->root);
2495
2496 delayed_refs->num_entries--;
2497
2498 /*
2499 * we don't take a ref on the node because we're removing it from the
2500 * tree, so we just steal the ref the tree was holding.
2501 */
2502 delayed_refs->num_heads--;
2503 if (list_empty(&head->cluster))
2504 delayed_refs->num_heads_ready--;
2505
2506 list_del_init(&head->cluster);
2507 spin_unlock(&delayed_refs->lock);
2508
2509 ret = run_one_delayed_ref(trans, root->fs_info->tree_root,
2510 &head->node, head->must_insert_reserved);
2511 BUG_ON(ret);
2512 btrfs_put_delayed_ref(&head->node);
2513 return 0;
2514 out:
2515 spin_unlock(&delayed_refs->lock);
2516 return 0;
2517 }
2518
2519 int btrfs_free_extent(struct btrfs_trans_handle *trans,
2520 struct btrfs_root *root,
2521 u64 bytenr, u64 num_bytes, u64 parent,
2522 u64 root_objectid, u64 ref_generation,
2523 u64 owner_objectid, int pin)
2524 {
2525 int ret;
2526
2527 /*
2528 * tree log blocks never actually go into the extent allocation
2529 * tree, just update pinning info and exit early.
2530 *
2531 * data extents referenced by the tree log do need to have
2532 * their reference counts bumped.
2533 */
2534 if (root->root_key.objectid == BTRFS_TREE_LOG_OBJECTID &&
2535 owner_objectid < BTRFS_FIRST_FREE_OBJECTID) {
2536 /* unlocks the pinned mutex */
2537 btrfs_update_pinned_extents(root, bytenr, num_bytes, 1);
2538 update_reserved_extents(root, bytenr, num_bytes, 0);
2539 ret = 0;
2540 } else {
2541 ret = btrfs_add_delayed_ref(trans, bytenr, num_bytes, parent,
2542 root_objectid, ref_generation,
2543 owner_objectid,
2544 BTRFS_DROP_DELAYED_REF, 1);
2545 BUG_ON(ret);
2546 ret = check_ref_cleanup(trans, root, bytenr);
2547 BUG_ON(ret);
2548 }
2549 return ret;
2550 }
2551
2552 static u64 stripe_align(struct btrfs_root *root, u64 val)
2553 {
2554 u64 mask = ((u64)root->stripesize - 1);
2555 u64 ret = (val + mask) & ~mask;
2556 return ret;
2557 }
2558
2559 /*
2560 * walks the btree of allocated extents and find a hole of a given size.
2561 * The key ins is changed to record the hole:
2562 * ins->objectid == block start
2563 * ins->flags = BTRFS_EXTENT_ITEM_KEY
2564 * ins->offset == number of blocks
2565 * Any available blocks before search_start are skipped.
2566 */
2567 static noinline int find_free_extent(struct btrfs_trans_handle *trans,
2568 struct btrfs_root *orig_root,
2569 u64 num_bytes, u64 empty_size,
2570 u64 search_start, u64 search_end,
2571 u64 hint_byte, struct btrfs_key *ins,
2572 u64 exclude_start, u64 exclude_nr,
2573 int data)
2574 {
2575 int ret = 0;
2576 struct btrfs_root *root = orig_root->fs_info->extent_root;
2577 struct btrfs_free_cluster *last_ptr = NULL;
2578 struct btrfs_block_group_cache *block_group = NULL;
2579 int empty_cluster = 2 * 1024 * 1024;
2580 int allowed_chunk_alloc = 0;
2581 struct btrfs_space_info *space_info;
2582 int last_ptr_loop = 0;
2583 int loop = 0;
2584
2585 WARN_ON(num_bytes < root->sectorsize);
2586 btrfs_set_key_type(ins, BTRFS_EXTENT_ITEM_KEY);
2587 ins->objectid = 0;
2588 ins->offset = 0;
2589
2590 space_info = __find_space_info(root->fs_info, data);
2591
2592 if (orig_root->ref_cows || empty_size)
2593 allowed_chunk_alloc = 1;
2594
2595 if (data & BTRFS_BLOCK_GROUP_METADATA) {
2596 last_ptr = &root->fs_info->meta_alloc_cluster;
2597 if (!btrfs_test_opt(root, SSD))
2598 empty_cluster = 64 * 1024;
2599 }
2600
2601 if ((data & BTRFS_BLOCK_GROUP_DATA) && btrfs_test_opt(root, SSD)) {
2602 last_ptr = &root->fs_info->data_alloc_cluster;
2603 }
2604
2605 if (last_ptr) {
2606 spin_lock(&last_ptr->lock);
2607 if (last_ptr->block_group)
2608 hint_byte = last_ptr->window_start;
2609 spin_unlock(&last_ptr->lock);
2610 }
2611
2612 search_start = max(search_start, first_logical_byte(root, 0));
2613 search_start = max(search_start, hint_byte);
2614
2615 if (!last_ptr) {
2616 empty_cluster = 0;
2617 loop = 1;
2618 }
2619
2620 if (search_start == hint_byte) {
2621 block_group = btrfs_lookup_block_group(root->fs_info,
2622 search_start);
2623 if (block_group && block_group_bits(block_group, data)) {
2624 down_read(&space_info->groups_sem);
2625 goto have_block_group;
2626 } else if (block_group) {
2627 btrfs_put_block_group(block_group);
2628 }
2629 }
2630
2631 search:
2632 down_read(&space_info->groups_sem);
2633 list_for_each_entry(block_group, &space_info->block_groups, list) {
2634 u64 offset;
2635
2636 atomic_inc(&block_group->count);
2637 search_start = block_group->key.objectid;
2638
2639 have_block_group:
2640 if (unlikely(!block_group->cached)) {
2641 mutex_lock(&block_group->cache_mutex);
2642 ret = cache_block_group(root, block_group);
2643 mutex_unlock(&block_group->cache_mutex);
2644 if (ret) {
2645 btrfs_put_block_group(block_group);
2646 break;
2647 }
2648 }
2649
2650 if (unlikely(block_group->ro))
2651 goto loop;
2652
2653 if (last_ptr) {
2654 /*
2655 * the refill lock keeps out other
2656 * people trying to start a new cluster
2657 */
2658 spin_lock(&last_ptr->refill_lock);
2659 offset = btrfs_alloc_from_cluster(block_group, last_ptr,
2660 num_bytes, search_start);
2661 if (offset) {
2662 /* we have a block, we're done */
2663 spin_unlock(&last_ptr->refill_lock);
2664 goto checks;
2665 }
2666
2667 spin_lock(&last_ptr->lock);
2668 /*
2669 * whoops, this cluster doesn't actually point to
2670 * this block group. Get a ref on the block
2671 * group is does point to and try again
2672 */
2673 if (!last_ptr_loop && last_ptr->block_group &&
2674 last_ptr->block_group != block_group) {
2675
2676 btrfs_put_block_group(block_group);
2677 block_group = last_ptr->block_group;
2678 atomic_inc(&block_group->count);
2679 spin_unlock(&last_ptr->lock);
2680 spin_unlock(&last_ptr->refill_lock);
2681
2682 last_ptr_loop = 1;
2683 search_start = block_group->key.objectid;
2684 goto have_block_group;
2685 }
2686 spin_unlock(&last_ptr->lock);
2687
2688 /*
2689 * this cluster didn't work out, free it and
2690 * start over
2691 */
2692 btrfs_return_cluster_to_free_space(NULL, last_ptr);
2693
2694 last_ptr_loop = 0;
2695
2696 /* allocate a cluster in this block group */
2697 ret = btrfs_find_space_cluster(trans,
2698 block_group, last_ptr,
2699 offset, num_bytes,
2700 empty_cluster + empty_size);
2701 if (ret == 0) {
2702 /*
2703 * now pull our allocation out of this
2704 * cluster
2705 */
2706 offset = btrfs_alloc_from_cluster(block_group,
2707 last_ptr, num_bytes,
2708 search_start);
2709 if (offset) {
2710 /* we found one, proceed */
2711 spin_unlock(&last_ptr->refill_lock);
2712 goto checks;
2713 }
2714 }
2715 /*
2716 * at this point we either didn't find a cluster
2717 * or we weren't able to allocate a block from our
2718 * cluster. Free the cluster we've been trying
2719 * to use, and go to the next block group
2720 */
2721 if (loop < 2) {
2722 btrfs_return_cluster_to_free_space(NULL,
2723 last_ptr);
2724 spin_unlock(&last_ptr->refill_lock);
2725 goto loop;
2726 }
2727 spin_unlock(&last_ptr->refill_lock);
2728 }
2729
2730 offset = btrfs_find_space_for_alloc(block_group, search_start,
2731 num_bytes, empty_size);
2732 if (!offset)
2733 goto loop;
2734 checks:
2735 search_start = stripe_align(root, offset);
2736
2737 /* move on to the next group */
2738 if (search_start + num_bytes >= search_end) {
2739 btrfs_add_free_space(block_group, offset, num_bytes);
2740 goto loop;
2741 }
2742
2743 /* move on to the next group */
2744 if (search_start + num_bytes >
2745 block_group->key.objectid + block_group->key.offset) {
2746 btrfs_add_free_space(block_group, offset, num_bytes);
2747 goto loop;
2748 }
2749
2750 if (exclude_nr > 0 &&
2751 (search_start + num_bytes > exclude_start &&
2752 search_start < exclude_start + exclude_nr)) {
2753 search_start = exclude_start + exclude_nr;
2754
2755 btrfs_add_free_space(block_group, offset, num_bytes);
2756 /*
2757 * if search_start is still in this block group
2758 * then we just re-search this block group
2759 */
2760 if (search_start >= block_group->key.objectid &&
2761 search_start < (block_group->key.objectid +
2762 block_group->key.offset))
2763 goto have_block_group;
2764 goto loop;
2765 }
2766
2767 ins->objectid = search_start;
2768 ins->offset = num_bytes;
2769
2770 if (offset < search_start)
2771 btrfs_add_free_space(block_group, offset,
2772 search_start - offset);
2773 BUG_ON(offset > search_start);
2774
2775 /* we are all good, lets return */
2776 break;
2777 loop:
2778 btrfs_put_block_group(block_group);
2779 }
2780 up_read(&space_info->groups_sem);
2781
2782 /* loop == 0, try to find a clustered alloc in every block group
2783 * loop == 1, try again after forcing a chunk allocation
2784 * loop == 2, set empty_size and empty_cluster to 0 and try again
2785 */
2786 if (!ins->objectid && loop < 3 &&
2787 (empty_size || empty_cluster || allowed_chunk_alloc)) {
2788 if (loop >= 2) {
2789 empty_size = 0;
2790 empty_cluster = 0;
2791 }
2792
2793 if (allowed_chunk_alloc) {
2794 ret = do_chunk_alloc(trans, root, num_bytes +
2795 2 * 1024 * 1024, data, 1);
2796 allowed_chunk_alloc = 0;
2797 } else {
2798 space_info->force_alloc = 1;
2799 }
2800
2801 if (loop < 3) {
2802 loop++;
2803 goto search;
2804 }
2805 ret = -ENOSPC;
2806 } else if (!ins->objectid) {
2807 ret = -ENOSPC;
2808 }
2809
2810 /* we found what we needed */
2811 if (ins->objectid) {
2812 if (!(data & BTRFS_BLOCK_GROUP_DATA))
2813 trans->block_group = block_group->key.objectid;
2814
2815 btrfs_put_block_group(block_group);
2816 ret = 0;
2817 }
2818
2819 return ret;
2820 }
2821
2822 static void dump_space_info(struct btrfs_space_info *info, u64 bytes)
2823 {
2824 struct btrfs_block_group_cache *cache;
2825
2826 printk(KERN_INFO "space_info has %llu free, is %sfull\n",
2827 (unsigned long long)(info->total_bytes - info->bytes_used -
2828 info->bytes_pinned - info->bytes_reserved),
2829 (info->full) ? "" : "not ");
2830 printk(KERN_INFO "space_info total=%llu, pinned=%llu, delalloc=%llu,"
2831 " may_use=%llu, used=%llu\n",
2832 (unsigned long long)info->total_bytes,
2833 (unsigned long long)info->bytes_pinned,
2834 (unsigned long long)info->bytes_delalloc,
2835 (unsigned long long)info->bytes_may_use,
2836 (unsigned long long)info->bytes_used);
2837
2838 down_read(&info->groups_sem);
2839 list_for_each_entry(cache, &info->block_groups, list) {
2840 spin_lock(&cache->lock);
2841 printk(KERN_INFO "block group %llu has %llu bytes, %llu used "
2842 "%llu pinned %llu reserved\n",
2843 (unsigned long long)cache->key.objectid,
2844 (unsigned long long)cache->key.offset,
2845 (unsigned long long)btrfs_block_group_used(&cache->item),
2846 (unsigned long long)cache->pinned,
2847 (unsigned long long)cache->reserved);
2848 btrfs_dump_free_space(cache, bytes);
2849 spin_unlock(&cache->lock);
2850 }
2851 up_read(&info->groups_sem);
2852 }
2853
2854 static int __btrfs_reserve_extent(struct btrfs_trans_handle *trans,
2855 struct btrfs_root *root,
2856 u64 num_bytes, u64 min_alloc_size,
2857 u64 empty_size, u64 hint_byte,
2858 u64 search_end, struct btrfs_key *ins,
2859 u64 data)
2860 {
2861 int ret;
2862 u64 search_start = 0;
2863 struct btrfs_fs_info *info = root->fs_info;
2864
2865 data = btrfs_get_alloc_profile(root, data);
2866 again:
2867 /*
2868 * the only place that sets empty_size is btrfs_realloc_node, which
2869 * is not called recursively on allocations
2870 */
2871 if (empty_size || root->ref_cows) {
2872 if (!(data & BTRFS_BLOCK_GROUP_METADATA)) {
2873 ret = do_chunk_alloc(trans, root->fs_info->extent_root,
2874 2 * 1024 * 1024,
2875 BTRFS_BLOCK_GROUP_METADATA |
2876 (info->metadata_alloc_profile &
2877 info->avail_metadata_alloc_bits), 0);
2878 }
2879 ret = do_chunk_alloc(trans, root->fs_info->extent_root,
2880 num_bytes + 2 * 1024 * 1024, data, 0);
2881 }
2882
2883 WARN_ON(num_bytes < root->sectorsize);
2884 ret = find_free_extent(trans, root, num_bytes, empty_size,
2885 search_start, search_end, hint_byte, ins,
2886 trans->alloc_exclude_start,
2887 trans->alloc_exclude_nr, data);
2888
2889 if (ret == -ENOSPC && num_bytes > min_alloc_size) {
2890 num_bytes = num_bytes >> 1;
2891 num_bytes = num_bytes & ~(root->sectorsize - 1);
2892 num_bytes = max(num_bytes, min_alloc_size);
2893 do_chunk_alloc(trans, root->fs_info->extent_root,
2894 num_bytes, data, 1);
2895 goto again;
2896 }
2897 if (ret) {
2898 struct btrfs_space_info *sinfo;
2899
2900 sinfo = __find_space_info(root->fs_info, data);
2901 printk(KERN_ERR "btrfs allocation failed flags %llu, "
2902 "wanted %llu\n", (unsigned long long)data,
2903 (unsigned long long)num_bytes);
2904 dump_space_info(sinfo, num_bytes);
2905 BUG();
2906 }
2907
2908 return ret;
2909 }
2910
2911 int btrfs_free_reserved_extent(struct btrfs_root *root, u64 start, u64 len)
2912 {
2913 struct btrfs_block_group_cache *cache;
2914 int ret = 0;
2915
2916 cache = btrfs_lookup_block_group(root->fs_info, start);
2917 if (!cache) {
2918 printk(KERN_ERR "Unable to find block group for %llu\n",
2919 (unsigned long long)start);
2920 return -ENOSPC;
2921 }
2922
2923 ret = btrfs_discard_extent(root, start, len);
2924
2925 btrfs_add_free_space(cache, start, len);
2926 btrfs_put_block_group(cache);
2927 update_reserved_extents(root, start, len, 0);
2928
2929 return ret;
2930 }
2931
2932 int btrfs_reserve_extent(struct btrfs_trans_handle *trans,
2933 struct btrfs_root *root,
2934 u64 num_bytes, u64 min_alloc_size,
2935 u64 empty_size, u64 hint_byte,
2936 u64 search_end, struct btrfs_key *ins,
2937 u64 data)
2938 {
2939 int ret;
2940 ret = __btrfs_reserve_extent(trans, root, num_bytes, min_alloc_size,
2941 empty_size, hint_byte, search_end, ins,
2942 data);
2943 update_reserved_extents(root, ins->objectid, ins->offset, 1);
2944 return ret;
2945 }
2946
2947 static int __btrfs_alloc_reserved_extent(struct btrfs_trans_handle *trans,
2948 struct btrfs_root *root, u64 parent,
2949 u64 root_objectid, u64 ref_generation,
2950 u64 owner, struct btrfs_key *ins,
2951 int ref_mod)
2952 {
2953 int ret;
2954 u64 super_used;
2955 u64 root_used;
2956 u64 num_bytes = ins->offset;
2957 u32 sizes[2];
2958 struct btrfs_fs_info *info = root->fs_info;
2959 struct btrfs_root *extent_root = info->extent_root;
2960 struct btrfs_extent_item *extent_item;
2961 struct btrfs_extent_ref *ref;
2962 struct btrfs_path *path;
2963 struct btrfs_key keys[2];
2964
2965 if (parent == 0)
2966 parent = ins->objectid;
2967
2968 /* block accounting for super block */
2969 spin_lock(&info->delalloc_lock);
2970 super_used = btrfs_super_bytes_used(&info->super_copy);
2971 btrfs_set_super_bytes_used(&info->super_copy, super_used + num_bytes);
2972
2973 /* block accounting for root item */
2974 root_used = btrfs_root_used(&root->root_item);
2975 btrfs_set_root_used(&root->root_item, root_used + num_bytes);
2976 spin_unlock(&info->delalloc_lock);
2977
2978 memcpy(&keys[0], ins, sizeof(*ins));
2979 keys[1].objectid = ins->objectid;
2980 keys[1].type = BTRFS_EXTENT_REF_KEY;
2981 keys[1].offset = parent;
2982 sizes[0] = sizeof(*extent_item);
2983 sizes[1] = sizeof(*ref);
2984
2985 path = btrfs_alloc_path();
2986 BUG_ON(!path);
2987
2988 path->leave_spinning = 1;
2989 ret = btrfs_insert_empty_items(trans, extent_root, path, keys,
2990 sizes, 2);
2991 BUG_ON(ret);
2992
2993 extent_item = btrfs_item_ptr(path->nodes[0], path->slots[0],
2994 struct btrfs_extent_item);
2995 btrfs_set_extent_refs(path->nodes[0], extent_item, ref_mod);
2996 ref = btrfs_item_ptr(path->nodes[0], path->slots[0] + 1,
2997 struct btrfs_extent_ref);
2998
2999 btrfs_set_ref_root(path->nodes[0], ref, root_objectid);
3000 btrfs_set_ref_generation(path->nodes[0], ref, ref_generation);
3001 btrfs_set_ref_objectid(path->nodes[0], ref, owner);
3002 btrfs_set_ref_num_refs(path->nodes[0], ref, ref_mod);
3003
3004 btrfs_mark_buffer_dirty(path->nodes[0]);
3005
3006 trans->alloc_exclude_start = 0;
3007 trans->alloc_exclude_nr = 0;
3008 btrfs_free_path(path);
3009
3010 if (ret)
3011 goto out;
3012
3013 ret = update_block_group(trans, root, ins->objectid,
3014 ins->offset, 1, 0);
3015 if (ret) {
3016 printk(KERN_ERR "btrfs update block group failed for %llu "
3017 "%llu\n", (unsigned long long)ins->objectid,
3018 (unsigned long long)ins->offset);
3019 BUG();
3020 }
3021 out:
3022 return ret;
3023 }
3024
3025 int btrfs_alloc_reserved_extent(struct btrfs_trans_handle *trans,
3026 struct btrfs_root *root, u64 parent,
3027 u64 root_objectid, u64 ref_generation,
3028 u64 owner, struct btrfs_key *ins)
3029 {
3030 int ret;
3031
3032 if (root_objectid == BTRFS_TREE_LOG_OBJECTID)
3033 return 0;
3034
3035 ret = btrfs_add_delayed_ref(trans, ins->objectid,
3036 ins->offset, parent, root_objectid,
3037 ref_generation, owner,
3038 BTRFS_ADD_DELAYED_EXTENT, 0);
3039 BUG_ON(ret);
3040 return ret;
3041 }
3042
3043 /*
3044 * this is used by the tree logging recovery code. It records that
3045 * an extent has been allocated and makes sure to clear the free
3046 * space cache bits as well
3047 */
3048 int btrfs_alloc_logged_extent(struct btrfs_trans_handle *trans,
3049 struct btrfs_root *root, u64 parent,
3050 u64 root_objectid, u64 ref_generation,
3051 u64 owner, struct btrfs_key *ins)
3052 {
3053 int ret;
3054 struct btrfs_block_group_cache *block_group;
3055
3056 block_group = btrfs_lookup_block_group(root->fs_info, ins->objectid);
3057 mutex_lock(&block_group->cache_mutex);
3058 cache_block_group(root, block_group);
3059 mutex_unlock(&block_group->cache_mutex);
3060
3061 ret = btrfs_remove_free_space(block_group, ins->objectid,
3062 ins->offset);
3063 BUG_ON(ret);
3064 btrfs_put_block_group(block_group);
3065 ret = __btrfs_alloc_reserved_extent(trans, root, parent, root_objectid,
3066 ref_generation, owner, ins, 1);
3067 return ret;
3068 }
3069
3070 /*
3071 * finds a free extent and does all the dirty work required for allocation
3072 * returns the key for the extent through ins, and a tree buffer for
3073 * the first block of the extent through buf.
3074 *
3075 * returns 0 if everything worked, non-zero otherwise.
3076 */
3077 int btrfs_alloc_extent(struct btrfs_trans_handle *trans,
3078 struct btrfs_root *root,
3079 u64 num_bytes, u64 parent, u64 min_alloc_size,
3080 u64 root_objectid, u64 ref_generation,
3081 u64 owner_objectid, u64 empty_size, u64 hint_byte,
3082 u64 search_end, struct btrfs_key *ins, u64 data)
3083 {
3084 int ret;
3085 ret = __btrfs_reserve_extent(trans, root, num_bytes,
3086 min_alloc_size, empty_size, hint_byte,
3087 search_end, ins, data);
3088 BUG_ON(ret);
3089 if (root_objectid != BTRFS_TREE_LOG_OBJECTID) {
3090 ret = btrfs_add_delayed_ref(trans, ins->objectid,
3091 ins->offset, parent, root_objectid,
3092 ref_generation, owner_objectid,
3093 BTRFS_ADD_DELAYED_EXTENT, 0);
3094 BUG_ON(ret);
3095 }
3096 update_reserved_extents(root, ins->objectid, ins->offset, 1);
3097 return ret;
3098 }
3099
3100 struct extent_buffer *btrfs_init_new_buffer(struct btrfs_trans_handle *trans,
3101 struct btrfs_root *root,
3102 u64 bytenr, u32 blocksize,
3103 int level)
3104 {
3105 struct extent_buffer *buf;
3106
3107 buf = btrfs_find_create_tree_block(root, bytenr, blocksize);
3108 if (!buf)
3109 return ERR_PTR(-ENOMEM);
3110 btrfs_set_header_generation(buf, trans->transid);
3111 btrfs_set_buffer_lockdep_class(buf, level);
3112 btrfs_tree_lock(buf);
3113 clean_tree_block(trans, root, buf);
3114
3115 btrfs_set_lock_blocking(buf);
3116 btrfs_set_buffer_uptodate(buf);
3117
3118 if (root->root_key.objectid == BTRFS_TREE_LOG_OBJECTID) {
3119 set_extent_dirty(&root->dirty_log_pages, buf->start,
3120 buf->start + buf->len - 1, GFP_NOFS);
3121 } else {
3122 set_extent_dirty(&trans->transaction->dirty_pages, buf->start,
3123 buf->start + buf->len - 1, GFP_NOFS);
3124 }
3125 trans->blocks_used++;
3126 /* this returns a buffer locked for blocking */
3127 return buf;
3128 }
3129
3130 /*
3131 * helper function to allocate a block for a given tree
3132 * returns the tree buffer or NULL.
3133 */
3134 struct extent_buffer *btrfs_alloc_free_block(struct btrfs_trans_handle *trans,
3135 struct btrfs_root *root,
3136 u32 blocksize, u64 parent,
3137 u64 root_objectid,
3138 u64 ref_generation,
3139 int level,
3140 u64 hint,
3141 u64 empty_size)
3142 {
3143 struct btrfs_key ins;
3144 int ret;
3145 struct extent_buffer *buf;
3146
3147 ret = btrfs_alloc_extent(trans, root, blocksize, parent, blocksize,
3148 root_objectid, ref_generation, level,
3149 empty_size, hint, (u64)-1, &ins, 0);
3150 if (ret) {
3151 BUG_ON(ret > 0);
3152 return ERR_PTR(ret);
3153 }
3154
3155 buf = btrfs_init_new_buffer(trans, root, ins.objectid,
3156 blocksize, level);
3157 return buf;
3158 }
3159
3160 int btrfs_drop_leaf_ref(struct btrfs_trans_handle *trans,
3161 struct btrfs_root *root, struct extent_buffer *leaf)
3162 {
3163 u64 leaf_owner;
3164 u64 leaf_generation;
3165 struct refsort *sorted;
3166 struct btrfs_key key;
3167 struct btrfs_file_extent_item *fi;
3168 int i;
3169 int nritems;
3170 int ret;
3171 int refi = 0;
3172 int slot;
3173
3174 BUG_ON(!btrfs_is_leaf(leaf));
3175 nritems = btrfs_header_nritems(leaf);
3176 leaf_owner = btrfs_header_owner(leaf);
3177 leaf_generation = btrfs_header_generation(leaf);
3178
3179 sorted = kmalloc(sizeof(*sorted) * nritems, GFP_NOFS);
3180 /* we do this loop twice. The first time we build a list
3181 * of the extents we have a reference on, then we sort the list
3182 * by bytenr. The second time around we actually do the
3183 * extent freeing.
3184 */
3185 for (i = 0; i < nritems; i++) {
3186 u64 disk_bytenr;
3187 cond_resched();
3188
3189 btrfs_item_key_to_cpu(leaf, &key, i);
3190
3191 /* only extents have references, skip everything else */
3192 if (btrfs_key_type(&key) != BTRFS_EXTENT_DATA_KEY)
3193 continue;
3194
3195 fi = btrfs_item_ptr(leaf, i, struct btrfs_file_extent_item);
3196
3197 /* inline extents live in the btree, they don't have refs */
3198 if (btrfs_file_extent_type(leaf, fi) ==
3199 BTRFS_FILE_EXTENT_INLINE)
3200 continue;
3201
3202 disk_bytenr = btrfs_file_extent_disk_bytenr(leaf, fi);
3203
3204 /* holes don't have refs */
3205 if (disk_bytenr == 0)
3206 continue;
3207
3208 sorted[refi].bytenr = disk_bytenr;
3209 sorted[refi].slot = i;
3210 refi++;
3211 }
3212
3213 if (refi == 0)
3214 goto out;
3215
3216 sort(sorted, refi, sizeof(struct refsort), refsort_cmp, NULL);
3217
3218 for (i = 0; i < refi; i++) {
3219 u64 disk_bytenr;
3220
3221 disk_bytenr = sorted[i].bytenr;
3222 slot = sorted[i].slot;
3223
3224 cond_resched();
3225
3226 btrfs_item_key_to_cpu(leaf, &key, slot);
3227 if (btrfs_key_type(&key) != BTRFS_EXTENT_DATA_KEY)
3228 continue;
3229
3230 fi = btrfs_item_ptr(leaf, slot, struct btrfs_file_extent_item);
3231
3232 ret = btrfs_free_extent(trans, root, disk_bytenr,
3233 btrfs_file_extent_disk_num_bytes(leaf, fi),
3234 leaf->start, leaf_owner, leaf_generation,
3235 key.objectid, 0);
3236 BUG_ON(ret);
3237
3238 atomic_inc(&root->fs_info->throttle_gen);
3239 wake_up(&root->fs_info->transaction_throttle);
3240 cond_resched();
3241 }
3242 out:
3243 kfree(sorted);
3244 return 0;
3245 }
3246
3247 static noinline int cache_drop_leaf_ref(struct btrfs_trans_handle *trans,
3248 struct btrfs_root *root,
3249 struct btrfs_leaf_ref *ref)
3250 {
3251 int i;
3252 int ret;
3253 struct btrfs_extent_info *info;
3254 struct refsort *sorted;
3255
3256 if (ref->nritems == 0)
3257 return 0;
3258
3259 sorted = kmalloc(sizeof(*sorted) * ref->nritems, GFP_NOFS);
3260 for (i = 0; i < ref->nritems; i++) {
3261 sorted[i].bytenr = ref->extents[i].bytenr;
3262 sorted[i].slot = i;
3263 }
3264 sort(sorted, ref->nritems, sizeof(struct refsort), refsort_cmp, NULL);
3265
3266 /*
3267 * the items in the ref were sorted when the ref was inserted
3268 * into the ref cache, so this is already in order
3269 */
3270 for (i = 0; i < ref->nritems; i++) {
3271 info = ref->extents + sorted[i].slot;
3272 ret = btrfs_free_extent(trans, root, info->bytenr,
3273 info->num_bytes, ref->bytenr,
3274 ref->owner, ref->generation,
3275 info->objectid, 0);
3276
3277 atomic_inc(&root->fs_info->throttle_gen);
3278 wake_up(&root->fs_info->transaction_throttle);
3279 cond_resched();
3280
3281 BUG_ON(ret);
3282 info++;
3283 }
3284
3285 kfree(sorted);
3286 return 0;
3287 }
3288
3289 static int drop_snap_lookup_refcount(struct btrfs_trans_handle *trans,
3290 struct btrfs_root *root, u64 start,
3291 u64 len, u32 *refs)
3292 {
3293 int ret;
3294
3295 ret = btrfs_lookup_extent_ref(trans, root, start, len, refs);
3296 BUG_ON(ret);
3297
3298 #if 0 /* some debugging code in case we see problems here */
3299 /* if the refs count is one, it won't get increased again. But
3300 * if the ref count is > 1, someone may be decreasing it at
3301 * the same time we are.
3302 */
3303 if (*refs != 1) {
3304 struct extent_buffer *eb = NULL;
3305 eb = btrfs_find_create_tree_block(root, start, len);
3306 if (eb)
3307 btrfs_tree_lock(eb);
3308
3309 mutex_lock(&root->fs_info->alloc_mutex);
3310 ret = lookup_extent_ref(NULL, root, start, len, refs);
3311 BUG_ON(ret);
3312 mutex_unlock(&root->fs_info->alloc_mutex);
3313
3314 if (eb) {
3315 btrfs_tree_unlock(eb);
3316 free_extent_buffer(eb);
3317 }
3318 if (*refs == 1) {
3319 printk(KERN_ERR "btrfs block %llu went down to one "
3320 "during drop_snap\n", (unsigned long long)start);
3321 }
3322
3323 }
3324 #endif
3325
3326 cond_resched();
3327 return ret;
3328 }
3329
3330 /*
3331 * this is used while deleting old snapshots, and it drops the refs
3332 * on a whole subtree starting from a level 1 node.
3333 *
3334 * The idea is to sort all the leaf pointers, and then drop the
3335 * ref on all the leaves in order. Most of the time the leaves
3336 * will have ref cache entries, so no leaf IOs will be required to
3337 * find the extents they have references on.
3338 *
3339 * For each leaf, any references it has are also dropped in order
3340 *
3341 * This ends up dropping the references in something close to optimal
3342 * order for reading and modifying the extent allocation tree.
3343 */
3344 static noinline int drop_level_one_refs(struct btrfs_trans_handle *trans,
3345 struct btrfs_root *root,
3346 struct btrfs_path *path)
3347 {
3348 u64 bytenr;
3349 u64 root_owner;
3350 u64 root_gen;
3351 struct extent_buffer *eb = path->nodes[1];
3352 struct extent_buffer *leaf;
3353 struct btrfs_leaf_ref *ref;
3354 struct refsort *sorted = NULL;
3355 int nritems = btrfs_header_nritems(eb);
3356 int ret;
3357 int i;
3358 int refi = 0;
3359 int slot = path->slots[1];
3360 u32 blocksize = btrfs_level_size(root, 0);
3361 u32 refs;
3362
3363 if (nritems == 0)
3364 goto out;
3365
3366 root_owner = btrfs_header_owner(eb);
3367 root_gen = btrfs_header_generation(eb);
3368 sorted = kmalloc(sizeof(*sorted) * nritems, GFP_NOFS);
3369
3370 /*
3371 * step one, sort all the leaf pointers so we don't scribble
3372 * randomly into the extent allocation tree
3373 */
3374 for (i = slot; i < nritems; i++) {
3375 sorted[refi].bytenr = btrfs_node_blockptr(eb, i);
3376 sorted[refi].slot = i;
3377 refi++;
3378 }
3379
3380 /*
3381 * nritems won't be zero, but if we're picking up drop_snapshot
3382 * after a crash, slot might be > 0, so double check things
3383 * just in case.
3384 */
3385 if (refi == 0)
3386 goto out;
3387
3388 sort(sorted, refi, sizeof(struct refsort), refsort_cmp, NULL);
3389
3390 /*
3391 * the first loop frees everything the leaves point to
3392 */
3393 for (i = 0; i < refi; i++) {
3394 u64 ptr_gen;
3395
3396 bytenr = sorted[i].bytenr;
3397
3398 /*
3399 * check the reference count on this leaf. If it is > 1
3400 * we just decrement it below and don't update any
3401 * of the refs the leaf points to.
3402 */
3403 ret = drop_snap_lookup_refcount(trans, root, bytenr,
3404 blocksize, &refs);
3405 BUG_ON(ret);
3406 if (refs != 1)
3407 continue;
3408
3409 ptr_gen = btrfs_node_ptr_generation(eb, sorted[i].slot);
3410
3411 /*
3412 * the leaf only had one reference, which means the
3413 * only thing pointing to this leaf is the snapshot
3414 * we're deleting. It isn't possible for the reference
3415 * count to increase again later
3416 *
3417 * The reference cache is checked for the leaf,
3418 * and if found we'll be able to drop any refs held by
3419 * the leaf without needing to read it in.
3420 */
3421 ref = btrfs_lookup_leaf_ref(root, bytenr);
3422 if (ref && ref->generation != ptr_gen) {
3423 btrfs_free_leaf_ref(root, ref);
3424 ref = NULL;
3425 }
3426 if (ref) {
3427 ret = cache_drop_leaf_ref(trans, root, ref);
3428 BUG_ON(ret);
3429 btrfs_remove_leaf_ref(root, ref);
3430 btrfs_free_leaf_ref(root, ref);
3431 } else {
3432 /*
3433 * the leaf wasn't in the reference cache, so
3434 * we have to read it.
3435 */
3436 leaf = read_tree_block(root, bytenr, blocksize,
3437 ptr_gen);
3438 ret = btrfs_drop_leaf_ref(trans, root, leaf);
3439 BUG_ON(ret);
3440 free_extent_buffer(leaf);
3441 }
3442 atomic_inc(&root->fs_info->throttle_gen);
3443 wake_up(&root->fs_info->transaction_throttle);
3444 cond_resched();
3445 }
3446
3447 /*
3448 * run through the loop again to free the refs on the leaves.
3449 * This is faster than doing it in the loop above because
3450 * the leaves are likely to be clustered together. We end up
3451 * working in nice chunks on the extent allocation tree.
3452 */
3453 for (i = 0; i < refi; i++) {
3454 bytenr = sorted[i].bytenr;
3455 ret = btrfs_free_extent(trans, root, bytenr,
3456 blocksize, eb->start,
3457 root_owner, root_gen, 0, 1);
3458 BUG_ON(ret);
3459
3460 atomic_inc(&root->fs_info->throttle_gen);
3461 wake_up(&root->fs_info->transaction_throttle);
3462 cond_resched();
3463 }
3464 out:
3465 kfree(sorted);
3466
3467 /*
3468 * update the path to show we've processed the entire level 1
3469 * node. This will get saved into the root's drop_snapshot_progress
3470 * field so these drops are not repeated again if this transaction
3471 * commits.
3472 */
3473 path->slots[1] = nritems;
3474 return 0;
3475 }
3476
3477 /*
3478 * helper function for drop_snapshot, this walks down the tree dropping ref
3479 * counts as it goes.
3480 */
3481 static noinline int walk_down_tree(struct btrfs_trans_handle *trans,
3482 struct btrfs_root *root,
3483 struct btrfs_path *path, int *level)
3484 {
3485 u64 root_owner;
3486 u64 root_gen;
3487 u64 bytenr;
3488 u64 ptr_gen;
3489 struct extent_buffer *next;
3490 struct extent_buffer *cur;
3491 struct extent_buffer *parent;
3492 u32 blocksize;
3493 int ret;
3494 u32 refs;
3495
3496 WARN_ON(*level < 0);
3497 WARN_ON(*level >= BTRFS_MAX_LEVEL);
3498 ret = drop_snap_lookup_refcount(trans, root, path->nodes[*level]->start,
3499 path->nodes[*level]->len, &refs);
3500 BUG_ON(ret);
3501 if (refs > 1)
3502 goto out;
3503
3504 /*
3505 * walk down to the last node level and free all the leaves
3506 */
3507 while (*level >= 0) {
3508 WARN_ON(*level < 0);
3509 WARN_ON(*level >= BTRFS_MAX_LEVEL);
3510 cur = path->nodes[*level];
3511
3512 if (btrfs_header_level(cur) != *level)
3513 WARN_ON(1);
3514
3515 if (path->slots[*level] >=
3516 btrfs_header_nritems(cur))
3517 break;
3518
3519 /* the new code goes down to level 1 and does all the
3520 * leaves pointed to that node in bulk. So, this check
3521 * for level 0 will always be false.
3522 *
3523 * But, the disk format allows the drop_snapshot_progress
3524 * field in the root to leave things in a state where
3525 * a leaf will need cleaning up here. If someone crashes
3526 * with the old code and then boots with the new code,
3527 * we might find a leaf here.
3528 */
3529 if (*level == 0) {
3530 ret = btrfs_drop_leaf_ref(trans, root, cur);
3531 BUG_ON(ret);
3532 break;
3533 }
3534
3535 /*
3536 * once we get to level one, process the whole node
3537 * at once, including everything below it.
3538 */
3539 if (*level == 1) {
3540 ret = drop_level_one_refs(trans, root, path);
3541 BUG_ON(ret);
3542 break;
3543 }
3544
3545 bytenr = btrfs_node_blockptr(cur, path->slots[*level]);
3546 ptr_gen = btrfs_node_ptr_generation(cur, path->slots[*level]);
3547 blocksize = btrfs_level_size(root, *level - 1);
3548
3549 ret = drop_snap_lookup_refcount(trans, root, bytenr,
3550 blocksize, &refs);
3551 BUG_ON(ret);
3552
3553 /*
3554 * if there is more than one reference, we don't need
3555 * to read that node to drop any references it has. We
3556 * just drop the ref we hold on that node and move on to the
3557 * next slot in this level.
3558 */
3559 if (refs != 1) {
3560 parent = path->nodes[*level];
3561 root_owner = btrfs_header_owner(parent);
3562 root_gen = btrfs_header_generation(parent);
3563 path->slots[*level]++;
3564
3565 ret = btrfs_free_extent(trans, root, bytenr,
3566 blocksize, parent->start,
3567 root_owner, root_gen,
3568 *level - 1, 1);
3569 BUG_ON(ret);
3570
3571 atomic_inc(&root->fs_info->throttle_gen);
3572 wake_up(&root->fs_info->transaction_throttle);
3573 cond_resched();
3574
3575 continue;
3576 }
3577
3578 /*
3579 * we need to keep freeing things in the next level down.
3580 * read the block and loop around to process it
3581 */
3582 next = read_tree_block(root, bytenr, blocksize, ptr_gen);
3583 WARN_ON(*level <= 0);
3584 if (path->nodes[*level-1])
3585 free_extent_buffer(path->nodes[*level-1]);
3586 path->nodes[*level-1] = next;
3587 *level = btrfs_header_level(next);
3588 path->slots[*level] = 0;
3589 cond_resched();
3590 }
3591 out:
3592 WARN_ON(*level < 0);
3593 WARN_ON(*level >= BTRFS_MAX_LEVEL);
3594
3595 if (path->nodes[*level] == root->node) {
3596 parent = path->nodes[*level];
3597 bytenr = path->nodes[*level]->start;
3598 } else {
3599 parent = path->nodes[*level + 1];
3600 bytenr = btrfs_node_blockptr(parent, path->slots[*level + 1]);
3601 }
3602
3603 blocksize = btrfs_level_size(root, *level);
3604 root_owner = btrfs_header_owner(parent);
3605 root_gen = btrfs_header_generation(parent);
3606
3607 /*
3608 * cleanup and free the reference on the last node
3609 * we processed
3610 */
3611 ret = btrfs_free_extent(trans, root, bytenr, blocksize,
3612 parent->start, root_owner, root_gen,
3613 *level, 1);
3614 free_extent_buffer(path->nodes[*level]);
3615 path->nodes[*level] = NULL;
3616
3617 *level += 1;
3618 BUG_ON(ret);
3619
3620 cond_resched();
3621 return 0;
3622 }
3623
3624 /*
3625 * helper function for drop_subtree, this function is similar to
3626 * walk_down_tree. The main difference is that it checks reference
3627 * counts while tree blocks are locked.
3628 */
3629 static noinline int walk_down_subtree(struct btrfs_trans_handle *trans,
3630 struct btrfs_root *root,
3631 struct btrfs_path *path, int *level)
3632 {
3633 struct extent_buffer *next;
3634 struct extent_buffer *cur;
3635 struct extent_buffer *parent;
3636 u64 bytenr;
3637 u64 ptr_gen;
3638 u32 blocksize;
3639 u32 refs;
3640 int ret;
3641
3642 cur = path->nodes[*level];
3643 ret = btrfs_lookup_extent_ref(trans, root, cur->start, cur->len,
3644 &refs);
3645 BUG_ON(ret);
3646 if (refs > 1)
3647 goto out;
3648
3649 while (*level >= 0) {
3650 cur = path->nodes[*level];
3651 if (*level == 0) {
3652 ret = btrfs_drop_leaf_ref(trans, root, cur);
3653 BUG_ON(ret);
3654 clean_tree_block(trans, root, cur);
3655 break;
3656 }
3657 if (path->slots[*level] >= btrfs_header_nritems(cur)) {
3658 clean_tree_block(trans, root, cur);
3659 break;
3660 }
3661
3662 bytenr = btrfs_node_blockptr(cur, path->slots[*level]);
3663 blocksize = btrfs_level_size(root, *level - 1);
3664 ptr_gen = btrfs_node_ptr_generation(cur, path->slots[*level]);
3665
3666 next = read_tree_block(root, bytenr, blocksize, ptr_gen);
3667 btrfs_tree_lock(next);
3668 btrfs_set_lock_blocking(next);
3669
3670 ret = btrfs_lookup_extent_ref(trans, root, bytenr, blocksize,
3671 &refs);
3672 BUG_ON(ret);
3673 if (refs > 1) {
3674 parent = path->nodes[*level];
3675 ret = btrfs_free_extent(trans, root, bytenr,
3676 blocksize, parent->start,
3677 btrfs_header_owner(parent),
3678 btrfs_header_generation(parent),
3679 *level - 1, 1);
3680 BUG_ON(ret);
3681 path->slots[*level]++;
3682 btrfs_tree_unlock(next);
3683 free_extent_buffer(next);
3684 continue;
3685 }
3686
3687 *level = btrfs_header_level(next);
3688 path->nodes[*level] = next;
3689 path->slots[*level] = 0;
3690 path->locks[*level] = 1;
3691 cond_resched();
3692 }
3693 out:
3694 parent = path->nodes[*level + 1];
3695 bytenr = path->nodes[*level]->start;
3696 blocksize = path->nodes[*level]->len;
3697
3698 ret = btrfs_free_extent(trans, root, bytenr, blocksize,
3699 parent->start, btrfs_header_owner(parent),
3700 btrfs_header_generation(parent), *level, 1);
3701 BUG_ON(ret);
3702
3703 if (path->locks[*level]) {
3704 btrfs_tree_unlock(path->nodes[*level]);
3705 path->locks[*level] = 0;
3706 }
3707 free_extent_buffer(path->nodes[*level]);
3708 path->nodes[*level] = NULL;
3709 *level += 1;
3710 cond_resched();
3711 return 0;
3712 }
3713
3714 /*
3715 * helper for dropping snapshots. This walks back up the tree in the path
3716 * to find the first node higher up where we haven't yet gone through
3717 * all the slots
3718 */
3719 static noinline int walk_up_tree(struct btrfs_trans_handle *trans,
3720 struct btrfs_root *root,
3721 struct btrfs_path *path,
3722 int *level, int max_level)
3723 {
3724 u64 root_owner;
3725 u64 root_gen;
3726 struct btrfs_root_item *root_item = &root->root_item;
3727 int i;
3728 int slot;
3729 int ret;
3730
3731 for (i = *level; i < max_level && path->nodes[i]; i++) {
3732 slot = path->slots[i];
3733 if (slot < btrfs_header_nritems(path->nodes[i]) - 1) {
3734 struct extent_buffer *node;
3735 struct btrfs_disk_key disk_key;
3736
3737 /*
3738 * there is more work to do in this level.
3739 * Update the drop_progress marker to reflect
3740 * the work we've done so far, and then bump
3741 * the slot number
3742 */
3743 node = path->nodes[i];
3744 path->slots[i]++;
3745 *level = i;
3746 WARN_ON(*level == 0);
3747 btrfs_node_key(node, &disk_key, path->slots[i]);
3748 memcpy(&root_item->drop_progress,
3749 &disk_key, sizeof(disk_key));
3750 root_item->drop_level = i;
3751 return 0;
3752 } else {
3753 struct extent_buffer *parent;
3754
3755 /*
3756 * this whole node is done, free our reference
3757 * on it and go up one level
3758 */
3759 if (path->nodes[*level] == root->node)
3760 parent = path->nodes[*level];
3761 else
3762 parent = path->nodes[*level + 1];
3763
3764 root_owner = btrfs_header_owner(parent);
3765 root_gen = btrfs_header_generation(parent);
3766
3767 clean_tree_block(trans, root, path->nodes[*level]);
3768 ret = btrfs_free_extent(trans, root,
3769 path->nodes[*level]->start,
3770 path->nodes[*level]->len,
3771 parent->start, root_owner,
3772 root_gen, *level, 1);
3773 BUG_ON(ret);
3774 if (path->locks[*level]) {
3775 btrfs_tree_unlock(path->nodes[*level]);
3776 path->locks[*level] = 0;
3777 }
3778 free_extent_buffer(path->nodes[*level]);
3779 path->nodes[*level] = NULL;
3780 *level = i + 1;
3781 }
3782 }
3783 return 1;
3784 }
3785
3786 /*
3787 * drop the reference count on the tree rooted at 'snap'. This traverses
3788 * the tree freeing any blocks that have a ref count of zero after being
3789 * decremented.
3790 */
3791 int btrfs_drop_snapshot(struct btrfs_trans_handle *trans, struct btrfs_root
3792 *root)
3793 {
3794 int ret = 0;
3795 int wret;
3796 int level;
3797 struct btrfs_path *path;
3798 int i;
3799 int orig_level;
3800 int update_count;
3801 struct btrfs_root_item *root_item = &root->root_item;
3802
3803 WARN_ON(!mutex_is_locked(&root->fs_info->drop_mutex));
3804 path = btrfs_alloc_path();
3805 BUG_ON(!path);
3806
3807 level = btrfs_header_level(root->node);
3808 orig_level = level;
3809 if (btrfs_disk_key_objectid(&root_item->drop_progress) == 0) {
3810 path->nodes[level] = root->node;
3811 extent_buffer_get(root->node);
3812 path->slots[level] = 0;
3813 } else {
3814 struct btrfs_key key;
3815 struct btrfs_disk_key found_key;
3816 struct extent_buffer *node;
3817
3818 btrfs_disk_key_to_cpu(&key, &root_item->drop_progress);
3819 level = root_item->drop_level;
3820 path->lowest_level = level;
3821 wret = btrfs_search_slot(NULL, root, &key, path, 0, 0);
3822 if (wret < 0) {
3823 ret = wret;
3824 goto out;
3825 }
3826 node = path->nodes[level];
3827 btrfs_node_key(node, &found_key, path->slots[level]);
3828 WARN_ON(memcmp(&found_key, &root_item->drop_progress,
3829 sizeof(found_key)));
3830 /*
3831 * unlock our path, this is safe because only this
3832 * function is allowed to delete this snapshot
3833 */
3834 for (i = 0; i < BTRFS_MAX_LEVEL; i++) {
3835 if (path->nodes[i] && path->locks[i]) {
3836 path->locks[i] = 0;
3837 btrfs_tree_unlock(path->nodes[i]);
3838 }
3839 }
3840 }
3841 while (1) {
3842 unsigned long update;
3843 wret = walk_down_tree(trans, root, path, &level);
3844 if (wret > 0)
3845 break;
3846 if (wret < 0)
3847 ret = wret;
3848
3849 wret = walk_up_tree(trans, root, path, &level,
3850 BTRFS_MAX_LEVEL);
3851 if (wret > 0)
3852 break;
3853 if (wret < 0)
3854 ret = wret;
3855 if (trans->transaction->in_commit ||
3856 trans->transaction->delayed_refs.flushing) {
3857 ret = -EAGAIN;
3858 break;
3859 }
3860 atomic_inc(&root->fs_info->throttle_gen);
3861 wake_up(&root->fs_info->transaction_throttle);
3862 for (update_count = 0; update_count < 16; update_count++) {
3863 update = trans->delayed_ref_updates;
3864 trans->delayed_ref_updates = 0;
3865 if (update)
3866 btrfs_run_delayed_refs(trans, root, update);
3867 else
3868 break;
3869 }
3870 }
3871 for (i = 0; i <= orig_level; i++) {
3872 if (path->nodes[i]) {
3873 free_extent_buffer(path->nodes[i]);
3874 path->nodes[i] = NULL;
3875 }
3876 }
3877 out:
3878 btrfs_free_path(path);
3879 return ret;
3880 }
3881
3882 int btrfs_drop_subtree(struct btrfs_trans_handle *trans,
3883 struct btrfs_root *root,
3884 struct extent_buffer *node,
3885 struct extent_buffer *parent)
3886 {
3887 struct btrfs_path *path;
3888 int level;
3889 int parent_level;
3890 int ret = 0;
3891 int wret;
3892
3893 path = btrfs_alloc_path();
3894 BUG_ON(!path);
3895
3896 btrfs_assert_tree_locked(parent);
3897 parent_level = btrfs_header_level(parent);
3898 extent_buffer_get(parent);
3899 path->nodes[parent_level] = parent;
3900 path->slots[parent_level] = btrfs_header_nritems(parent);
3901
3902 btrfs_assert_tree_locked(node);
3903 level = btrfs_header_level(node);
3904 extent_buffer_get(node);
3905 path->nodes[level] = node;
3906 path->slots[level] = 0;
3907
3908 while (1) {
3909 wret = walk_down_subtree(trans, root, path, &level);
3910 if (wret < 0)
3911 ret = wret;
3912 if (wret != 0)
3913 break;
3914
3915 wret = walk_up_tree(trans, root, path, &level, parent_level);
3916 if (wret < 0)
3917 ret = wret;
3918 if (wret != 0)
3919 break;
3920 }
3921
3922 btrfs_free_path(path);
3923 return ret;
3924 }
3925
3926 static unsigned long calc_ra(unsigned long start, unsigned long last,
3927 unsigned long nr)
3928 {
3929 return min(last, start + nr - 1);
3930 }
3931
3932 static noinline int relocate_inode_pages(struct inode *inode, u64 start,
3933 u64 len)
3934 {
3935 u64 page_start;
3936 u64 page_end;
3937 unsigned long first_index;
3938 unsigned long last_index;
3939 unsigned long i;
3940 struct page *page;
3941 struct extent_io_tree *io_tree = &BTRFS_I(inode)->io_tree;
3942 struct file_ra_state *ra;
3943 struct btrfs_ordered_extent *ordered;
3944 unsigned int total_read = 0;
3945 unsigned int total_dirty = 0;
3946 int ret = 0;
3947
3948 ra = kzalloc(sizeof(*ra), GFP_NOFS);
3949
3950 mutex_lock(&inode->i_mutex);
3951 first_index = start >> PAGE_CACHE_SHIFT;
3952 last_index = (start + len - 1) >> PAGE_CACHE_SHIFT;
3953
3954 /* make sure the dirty trick played by the caller work */
3955 ret = invalidate_inode_pages2_range(inode->i_mapping,
3956 first_index, last_index);
3957 if (ret)
3958 goto out_unlock;
3959
3960 file_ra_state_init(ra, inode->i_mapping);
3961
3962 for (i = first_index ; i <= last_index; i++) {
3963 if (total_read % ra->ra_pages == 0) {
3964 btrfs_force_ra(inode->i_mapping, ra, NULL, i,
3965 calc_ra(i, last_index, ra->ra_pages));
3966 }
3967 total_read++;
3968 again:
3969 if (((u64)i << PAGE_CACHE_SHIFT) > i_size_read(inode))
3970 BUG_ON(1);
3971 page = grab_cache_page(inode->i_mapping, i);
3972 if (!page) {
3973 ret = -ENOMEM;
3974 goto out_unlock;
3975 }
3976 if (!PageUptodate(page)) {
3977 btrfs_readpage(NULL, page);
3978 lock_page(page);
3979 if (!PageUptodate(page)) {
3980 unlock_page(page);
3981 page_cache_release(page);
3982 ret = -EIO;
3983 goto out_unlock;
3984 }
3985 }
3986 wait_on_page_writeback(page);
3987
3988 page_start = (u64)page->index << PAGE_CACHE_SHIFT;
3989 page_end = page_start + PAGE_CACHE_SIZE - 1;
3990 lock_extent(io_tree, page_start, page_end, GFP_NOFS);
3991
3992 ordered = btrfs_lookup_ordered_extent(inode, page_start);
3993 if (ordered) {
3994 unlock_extent(io_tree, page_start, page_end, GFP_NOFS);
3995 unlock_page(page);
3996 page_cache_release(page);
3997 btrfs_start_ordered_extent(inode, ordered, 1);
3998 btrfs_put_ordered_extent(ordered);
3999 goto again;
4000 }
4001 set_page_extent_mapped(page);
4002
4003 if (i == first_index)
4004 set_extent_bits(io_tree, page_start, page_end,
4005 EXTENT_BOUNDARY, GFP_NOFS);
4006 btrfs_set_extent_delalloc(inode, page_start, page_end);
4007
4008 set_page_dirty(page);
4009 total_dirty++;
4010
4011 unlock_extent(io_tree, page_start, page_end, GFP_NOFS);
4012 unlock_page(page);
4013 page_cache_release(page);
4014 }
4015
4016 out_unlock:
4017 kfree(ra);
4018 mutex_unlock(&inode->i_mutex);
4019 balance_dirty_pages_ratelimited_nr(inode->i_mapping, total_dirty);
4020 return ret;
4021 }
4022
4023 static noinline int relocate_data_extent(struct inode *reloc_inode,
4024 struct btrfs_key *extent_key,
4025 u64 offset)
4026 {
4027 struct btrfs_root *root = BTRFS_I(reloc_inode)->root;
4028 struct extent_map_tree *em_tree = &BTRFS_I(reloc_inode)->extent_tree;
4029 struct extent_map *em;
4030 u64 start = extent_key->objectid - offset;
4031 u64 end = start + extent_key->offset - 1;
4032
4033 em = alloc_extent_map(GFP_NOFS);
4034 BUG_ON(!em || IS_ERR(em));
4035
4036 em->start = start;
4037 em->len = extent_key->offset;
4038 em->block_len = extent_key->offset;
4039 em->block_start = extent_key->objectid;
4040 em->bdev = root->fs_info->fs_devices->latest_bdev;
4041 set_bit(EXTENT_FLAG_PINNED, &em->flags);
4042
4043 /* setup extent map to cheat btrfs_readpage */
4044 lock_extent(&BTRFS_I(reloc_inode)->io_tree, start, end, GFP_NOFS);
4045 while (1) {
4046 int ret;
4047 spin_lock(&em_tree->lock);
4048 ret = add_extent_mapping(em_tree, em);
4049 spin_unlock(&em_tree->lock);
4050 if (ret != -EEXIST) {
4051 free_extent_map(em);
4052 break;
4053 }
4054 btrfs_drop_extent_cache(reloc_inode, start, end, 0);
4055 }
4056 unlock_extent(&BTRFS_I(reloc_inode)->io_tree, start, end, GFP_NOFS);
4057
4058 return relocate_inode_pages(reloc_inode, start, extent_key->offset);
4059 }
4060
4061 struct btrfs_ref_path {
4062 u64 extent_start;
4063 u64 nodes[BTRFS_MAX_LEVEL];
4064 u64 root_objectid;
4065 u64 root_generation;
4066 u64 owner_objectid;
4067 u32 num_refs;
4068 int lowest_level;
4069 int current_level;
4070 int shared_level;
4071
4072 struct btrfs_key node_keys[BTRFS_MAX_LEVEL];
4073 u64 new_nodes[BTRFS_MAX_LEVEL];
4074 };
4075
4076 struct disk_extent {
4077 u64 ram_bytes;
4078 u64 disk_bytenr;
4079 u64 disk_num_bytes;
4080 u64 offset;
4081 u64 num_bytes;
4082 u8 compression;
4083 u8 encryption;
4084 u16 other_encoding;
4085 };
4086
4087 static int is_cowonly_root(u64 root_objectid)
4088 {
4089 if (root_objectid == BTRFS_ROOT_TREE_OBJECTID ||
4090 root_objectid == BTRFS_EXTENT_TREE_OBJECTID ||
4091 root_objectid == BTRFS_CHUNK_TREE_OBJECTID ||
4092 root_objectid == BTRFS_DEV_TREE_OBJECTID ||
4093 root_objectid == BTRFS_TREE_LOG_OBJECTID ||
4094 root_objectid == BTRFS_CSUM_TREE_OBJECTID)
4095 return 1;
4096 return 0;
4097 }
4098
4099 static noinline int __next_ref_path(struct btrfs_trans_handle *trans,
4100 struct btrfs_root *extent_root,
4101 struct btrfs_ref_path *ref_path,
4102 int first_time)
4103 {
4104 struct extent_buffer *leaf;
4105 struct btrfs_path *path;
4106 struct btrfs_extent_ref *ref;
4107 struct btrfs_key key;
4108 struct btrfs_key found_key;
4109 u64 bytenr;
4110 u32 nritems;
4111 int level;
4112 int ret = 1;
4113
4114 path = btrfs_alloc_path();
4115 if (!path)
4116 return -ENOMEM;
4117
4118 if (first_time) {
4119 ref_path->lowest_level = -1;
4120 ref_path->current_level = -1;
4121 ref_path->shared_level = -1;
4122 goto walk_up;
4123 }
4124 walk_down:
4125 level = ref_path->current_level - 1;
4126 while (level >= -1) {
4127 u64 parent;
4128 if (level < ref_path->lowest_level)
4129 break;
4130
4131 if (level >= 0)
4132 bytenr = ref_path->nodes[level];
4133 else
4134 bytenr = ref_path->extent_start;
4135 BUG_ON(bytenr == 0);
4136
4137 parent = ref_path->nodes[level + 1];
4138 ref_path->nodes[level + 1] = 0;
4139 ref_path->current_level = level;
4140 BUG_ON(parent == 0);
4141
4142 key.objectid = bytenr;
4143 key.offset = parent + 1;
4144 key.type = BTRFS_EXTENT_REF_KEY;
4145
4146 ret = btrfs_search_slot(trans, extent_root, &key, path, 0, 0);
4147 if (ret < 0)
4148 goto out;
4149 BUG_ON(ret == 0);
4150
4151 leaf = path->nodes[0];
4152 nritems = btrfs_header_nritems(leaf);
4153 if (path->slots[0] >= nritems) {
4154 ret = btrfs_next_leaf(extent_root, path);
4155 if (ret < 0)
4156 goto out;
4157 if (ret > 0)
4158 goto next;
4159 leaf = path->nodes[0];
4160 }
4161
4162 btrfs_item_key_to_cpu(leaf, &found_key, path->slots[0]);
4163 if (found_key.objectid == bytenr &&
4164 found_key.type == BTRFS_EXTENT_REF_KEY) {
4165 if (level < ref_path->shared_level)
4166 ref_path->shared_level = level;
4167 goto found;
4168 }
4169 next:
4170 level--;
4171 btrfs_release_path(extent_root, path);
4172 cond_resched();
4173 }
4174 /* reached lowest level */
4175 ret = 1;
4176 goto out;
4177 walk_up:
4178 level = ref_path->current_level;
4179 while (level < BTRFS_MAX_LEVEL - 1) {
4180 u64 ref_objectid;
4181
4182 if (level >= 0)
4183 bytenr = ref_path->nodes[level];
4184 else
4185 bytenr = ref_path->extent_start;
4186
4187 BUG_ON(bytenr == 0);
4188
4189 key.objectid = bytenr;
4190 key.offset = 0;
4191 key.type = BTRFS_EXTENT_REF_KEY;
4192
4193 ret = btrfs_search_slot(trans, extent_root, &key, path, 0, 0);
4194 if (ret < 0)
4195 goto out;
4196
4197 leaf = path->nodes[0];
4198 nritems = btrfs_header_nritems(leaf);
4199 if (path->slots[0] >= nritems) {
4200 ret = btrfs_next_leaf(extent_root, path);
4201 if (ret < 0)
4202 goto out;
4203 if (ret > 0) {
4204 /* the extent was freed by someone */
4205 if (ref_path->lowest_level == level)
4206 goto out;
4207 btrfs_release_path(extent_root, path);
4208 goto walk_down;
4209 }
4210 leaf = path->nodes[0];
4211 }
4212
4213 btrfs_item_key_to_cpu(leaf, &found_key, path->slots[0]);
4214 if (found_key.objectid != bytenr ||
4215 found_key.type != BTRFS_EXTENT_REF_KEY) {
4216 /* the extent was freed by someone */
4217 if (ref_path->lowest_level == level) {
4218 ret = 1;
4219 goto out;
4220 }
4221 btrfs_release_path(extent_root, path);
4222 goto walk_down;
4223 }
4224 found:
4225 ref = btrfs_item_ptr(leaf, path->slots[0],
4226 struct btrfs_extent_ref);
4227 ref_objectid = btrfs_ref_objectid(leaf, ref);
4228 if (ref_objectid < BTRFS_FIRST_FREE_OBJECTID) {
4229 if (first_time) {
4230 level = (int)ref_objectid;
4231 BUG_ON(level >= BTRFS_MAX_LEVEL);
4232 ref_path->lowest_level = level;
4233 ref_path->current_level = level;
4234 ref_path->nodes[level] = bytenr;
4235 } else {
4236 WARN_ON(ref_objectid != level);
4237 }
4238 } else {
4239 WARN_ON(level != -1);
4240 }
4241 first_time = 0;
4242
4243 if (ref_path->lowest_level == level) {
4244 ref_path->owner_objectid = ref_objectid;
4245 ref_path->num_refs = btrfs_ref_num_refs(leaf, ref);
4246 }
4247
4248 /*
4249 * the block is tree root or the block isn't in reference
4250 * counted tree.
4251 */
4252 if (found_key.objectid == found_key.offset ||
4253 is_cowonly_root(btrfs_ref_root(leaf, ref))) {
4254 ref_path->root_objectid = btrfs_ref_root(leaf, ref);
4255 ref_path->root_generation =
4256 btrfs_ref_generation(leaf, ref);
4257 if (level < 0) {
4258 /* special reference from the tree log */
4259 ref_path->nodes[0] = found_key.offset;
4260 ref_path->current_level = 0;
4261 }
4262 ret = 0;
4263 goto out;
4264 }
4265
4266 level++;
4267 BUG_ON(ref_path->nodes[level] != 0);
4268 ref_path->nodes[level] = found_key.offset;
4269 ref_path->current_level = level;
4270
4271 /*
4272 * the reference was created in the running transaction,
4273 * no need to continue walking up.
4274 */
4275 if (btrfs_ref_generation(leaf, ref) == trans->transid) {
4276 ref_path->root_objectid = btrfs_ref_root(leaf, ref);
4277 ref_path->root_generation =
4278 btrfs_ref_generation(leaf, ref);
4279 ret = 0;
4280 goto out;
4281 }
4282
4283 btrfs_release_path(extent_root, path);
4284 cond_resched();
4285 }
4286 /* reached max tree level, but no tree root found. */
4287 BUG();
4288 out:
4289 btrfs_free_path(path);
4290 return ret;
4291 }
4292
4293 static int btrfs_first_ref_path(struct btrfs_trans_handle *trans,
4294 struct btrfs_root *extent_root,
4295 struct btrfs_ref_path *ref_path,
4296 u64 extent_start)
4297 {
4298 memset(ref_path, 0, sizeof(*ref_path));
4299 ref_path->extent_start = extent_start;
4300
4301 return __next_ref_path(trans, extent_root, ref_path, 1);
4302 }
4303
4304 static int btrfs_next_ref_path(struct btrfs_trans_handle *trans,
4305 struct btrfs_root *extent_root,
4306 struct btrfs_ref_path *ref_path)
4307 {
4308 return __next_ref_path(trans, extent_root, ref_path, 0);
4309 }
4310
4311 static noinline int get_new_locations(struct inode *reloc_inode,
4312 struct btrfs_key *extent_key,
4313 u64 offset, int no_fragment,
4314 struct disk_extent **extents,
4315 int *nr_extents)
4316 {
4317 struct btrfs_root *root = BTRFS_I(reloc_inode)->root;
4318 struct btrfs_path *path;
4319 struct btrfs_file_extent_item *fi;
4320 struct extent_buffer *leaf;
4321 struct disk_extent *exts = *extents;
4322 struct btrfs_key found_key;
4323 u64 cur_pos;
4324 u64 last_byte;
4325 u32 nritems;
4326 int nr = 0;
4327 int max = *nr_extents;
4328 int ret;
4329
4330 WARN_ON(!no_fragment && *extents);
4331 if (!exts) {
4332 max = 1;
4333 exts = kmalloc(sizeof(*exts) * max, GFP_NOFS);
4334 if (!exts)
4335 return -ENOMEM;
4336 }
4337
4338 path = btrfs_alloc_path();
4339 BUG_ON(!path);
4340
4341 cur_pos = extent_key->objectid - offset;
4342 last_byte = extent_key->objectid + extent_key->offset;
4343 ret = btrfs_lookup_file_extent(NULL, root, path, reloc_inode->i_ino,
4344 cur_pos, 0);
4345 if (ret < 0)
4346 goto out;
4347 if (ret > 0) {
4348 ret = -ENOENT;
4349 goto out;
4350 }
4351
4352 while (1) {
4353 leaf = path->nodes[0];
4354 nritems = btrfs_header_nritems(leaf);
4355 if (path->slots[0] >= nritems) {
4356 ret = btrfs_next_leaf(root, path);
4357 if (ret < 0)
4358 goto out;
4359 if (ret > 0)
4360 break;
4361 leaf = path->nodes[0];
4362 }
4363
4364 btrfs_item_key_to_cpu(leaf, &found_key, path->slots[0]);
4365 if (found_key.offset != cur_pos ||
4366 found_key.type != BTRFS_EXTENT_DATA_KEY ||
4367 found_key.objectid != reloc_inode->i_ino)
4368 break;
4369
4370 fi = btrfs_item_ptr(leaf, path->slots[0],
4371 struct btrfs_file_extent_item);
4372 if (btrfs_file_extent_type(leaf, fi) !=
4373 BTRFS_FILE_EXTENT_REG ||
4374 btrfs_file_extent_disk_bytenr(leaf, fi) == 0)
4375 break;
4376
4377 if (nr == max) {
4378 struct disk_extent *old = exts;
4379 max *= 2;
4380 exts = kzalloc(sizeof(*exts) * max, GFP_NOFS);
4381 memcpy(exts, old, sizeof(*exts) * nr);
4382 if (old != *extents)
4383 kfree(old);
4384 }
4385
4386 exts[nr].disk_bytenr =
4387 btrfs_file_extent_disk_bytenr(leaf, fi);
4388 exts[nr].disk_num_bytes =
4389 btrfs_file_extent_disk_num_bytes(leaf, fi);
4390 exts[nr].offset = btrfs_file_extent_offset(leaf, fi);
4391 exts[nr].num_bytes = btrfs_file_extent_num_bytes(leaf, fi);
4392 exts[nr].ram_bytes = btrfs_file_extent_ram_bytes(leaf, fi);
4393 exts[nr].compression = btrfs_file_extent_compression(leaf, fi);
4394 exts[nr].encryption = btrfs_file_extent_encryption(leaf, fi);
4395 exts[nr].other_encoding = btrfs_file_extent_other_encoding(leaf,
4396 fi);
4397 BUG_ON(exts[nr].offset > 0);
4398 BUG_ON(exts[nr].compression || exts[nr].encryption);
4399 BUG_ON(exts[nr].num_bytes != exts[nr].disk_num_bytes);
4400
4401 cur_pos += exts[nr].num_bytes;
4402 nr++;
4403
4404 if (cur_pos + offset >= last_byte)
4405 break;
4406
4407 if (no_fragment) {
4408 ret = 1;
4409 goto out;
4410 }
4411 path->slots[0]++;
4412 }
4413
4414 BUG_ON(cur_pos + offset > last_byte);
4415 if (cur_pos + offset < last_byte) {
4416 ret = -ENOENT;
4417 goto out;
4418 }
4419 ret = 0;
4420 out:
4421 btrfs_free_path(path);
4422 if (ret) {
4423 if (exts != *extents)
4424 kfree(exts);
4425 } else {
4426 *extents = exts;
4427 *nr_extents = nr;
4428 }
4429 return ret;
4430 }
4431
4432 static noinline int replace_one_extent(struct btrfs_trans_handle *trans,
4433 struct btrfs_root *root,
4434 struct btrfs_path *path,
4435 struct btrfs_key *extent_key,
4436 struct btrfs_key *leaf_key,
4437 struct btrfs_ref_path *ref_path,
4438 struct disk_extent *new_extents,
4439 int nr_extents)
4440 {
4441 struct extent_buffer *leaf;
4442 struct btrfs_file_extent_item *fi;
4443 struct inode *inode = NULL;
4444 struct btrfs_key key;
4445 u64 lock_start = 0;
4446 u64 lock_end = 0;
4447 u64 num_bytes;
4448 u64 ext_offset;
4449 u64 search_end = (u64)-1;
4450 u32 nritems;
4451 int nr_scaned = 0;
4452 int extent_locked = 0;
4453 int extent_type;
4454 int ret;
4455
4456 memcpy(&key, leaf_key, sizeof(key));
4457 if (ref_path->owner_objectid != BTRFS_MULTIPLE_OBJECTIDS) {
4458 if (key.objectid < ref_path->owner_objectid ||
4459 (key.objectid == ref_path->owner_objectid &&
4460 key.type < BTRFS_EXTENT_DATA_KEY)) {
4461 key.objectid = ref_path->owner_objectid;
4462 key.type = BTRFS_EXTENT_DATA_KEY;
4463 key.offset = 0;
4464 }
4465 }
4466
4467 while (1) {
4468 ret = btrfs_search_slot(trans, root, &key, path, 0, 1);
4469 if (ret < 0)
4470 goto out;
4471
4472 leaf = path->nodes[0];
4473 nritems = btrfs_header_nritems(leaf);
4474 next:
4475 if (extent_locked && ret > 0) {
4476 /*
4477 * the file extent item was modified by someone
4478 * before the extent got locked.
4479 */
4480 unlock_extent(&BTRFS_I(inode)->io_tree, lock_start,
4481 lock_end, GFP_NOFS);
4482 extent_locked = 0;
4483 }
4484
4485 if (path->slots[0] >= nritems) {
4486 if (++nr_scaned > 2)
4487 break;
4488
4489 BUG_ON(extent_locked);
4490 ret = btrfs_next_leaf(root, path);
4491 if (ret < 0)
4492 goto out;
4493 if (ret > 0)
4494 break;
4495 leaf = path->nodes[0];
4496 nritems = btrfs_header_nritems(leaf);
4497 }
4498
4499 btrfs_item_key_to_cpu(leaf, &key, path->slots[0]);
4500
4501 if (ref_path->owner_objectid != BTRFS_MULTIPLE_OBJECTIDS) {
4502 if ((key.objectid > ref_path->owner_objectid) ||
4503 (key.objectid == ref_path->owner_objectid &&
4504 key.type > BTRFS_EXTENT_DATA_KEY) ||
4505 key.offset >= search_end)
4506 break;
4507 }
4508
4509 if (inode && key.objectid != inode->i_ino) {
4510 BUG_ON(extent_locked);
4511 btrfs_release_path(root, path);
4512 mutex_unlock(&inode->i_mutex);
4513 iput(inode);
4514 inode = NULL;
4515 continue;
4516 }
4517
4518 if (key.type != BTRFS_EXTENT_DATA_KEY) {
4519 path->slots[0]++;
4520 ret = 1;
4521 goto next;
4522 }
4523 fi = btrfs_item_ptr(leaf, path->slots[0],
4524 struct btrfs_file_extent_item);
4525 extent_type = btrfs_file_extent_type(leaf, fi);
4526 if ((extent_type != BTRFS_FILE_EXTENT_REG &&
4527 extent_type != BTRFS_FILE_EXTENT_PREALLOC) ||
4528 (btrfs_file_extent_disk_bytenr(leaf, fi) !=
4529 extent_key->objectid)) {
4530 path->slots[0]++;
4531 ret = 1;
4532 goto next;
4533 }
4534
4535 num_bytes = btrfs_file_extent_num_bytes(leaf, fi);
4536 ext_offset = btrfs_file_extent_offset(leaf, fi);
4537
4538 if (search_end == (u64)-1) {
4539 search_end = key.offset - ext_offset +
4540 btrfs_file_extent_ram_bytes(leaf, fi);
4541 }
4542
4543 if (!extent_locked) {
4544 lock_start = key.offset;
4545 lock_end = lock_start + num_bytes - 1;
4546 } else {
4547 if (lock_start > key.offset ||
4548 lock_end + 1 < key.offset + num_bytes) {
4549 unlock_extent(&BTRFS_I(inode)->io_tree,
4550 lock_start, lock_end, GFP_NOFS);
4551 extent_locked = 0;
4552 }
4553 }
4554
4555 if (!inode) {
4556 btrfs_release_path(root, path);
4557
4558 inode = btrfs_iget_locked(root->fs_info->sb,
4559 key.objectid, root);
4560 if (inode->i_state & I_NEW) {
4561 BTRFS_I(inode)->root = root;
4562 BTRFS_I(inode)->location.objectid =
4563 key.objectid;
4564 BTRFS_I(inode)->location.type =
4565 BTRFS_INODE_ITEM_KEY;
4566 BTRFS_I(inode)->location.offset = 0;
4567 btrfs_read_locked_inode(inode);
4568 unlock_new_inode(inode);
4569 }
4570 /*
4571 * some code call btrfs_commit_transaction while
4572 * holding the i_mutex, so we can't use mutex_lock
4573 * here.
4574 */
4575 if (is_bad_inode(inode) ||
4576 !mutex_trylock(&inode->i_mutex)) {
4577 iput(inode);
4578 inode = NULL;
4579 key.offset = (u64)-1;
4580 goto skip;
4581 }
4582 }
4583
4584 if (!extent_locked) {
4585 struct btrfs_ordered_extent *ordered;
4586
4587 btrfs_release_path(root, path);
4588
4589 lock_extent(&BTRFS_I(inode)->io_tree, lock_start,
4590 lock_end, GFP_NOFS);
4591 ordered = btrfs_lookup_first_ordered_extent(inode,
4592 lock_end);
4593 if (ordered &&
4594 ordered->file_offset <= lock_end &&
4595 ordered->file_offset + ordered->len > lock_start) {
4596 unlock_extent(&BTRFS_I(inode)->io_tree,
4597 lock_start, lock_end, GFP_NOFS);
4598 btrfs_start_ordered_extent(inode, ordered, 1);
4599 btrfs_put_ordered_extent(ordered);
4600 key.offset += num_bytes;
4601 goto skip;
4602 }
4603 if (ordered)
4604 btrfs_put_ordered_extent(ordered);
4605
4606 extent_locked = 1;
4607 continue;
4608 }
4609
4610 if (nr_extents == 1) {
4611 /* update extent pointer in place */
4612 btrfs_set_file_extent_disk_bytenr(leaf, fi,
4613 new_extents[0].disk_bytenr);
4614 btrfs_set_file_extent_disk_num_bytes(leaf, fi,
4615 new_extents[0].disk_num_bytes);
4616 btrfs_mark_buffer_dirty(leaf);
4617
4618 btrfs_drop_extent_cache(inode, key.offset,
4619 key.offset + num_bytes - 1, 0);
4620
4621 ret = btrfs_inc_extent_ref(trans, root,
4622 new_extents[0].disk_bytenr,
4623 new_extents[0].disk_num_bytes,
4624 leaf->start,
4625 root->root_key.objectid,
4626 trans->transid,
4627 key.objectid);
4628 BUG_ON(ret);
4629
4630 ret = btrfs_free_extent(trans, root,
4631 extent_key->objectid,
4632 extent_key->offset,
4633 leaf->start,
4634 btrfs_header_owner(leaf),
4635 btrfs_header_generation(leaf),
4636 key.objectid, 0);
4637 BUG_ON(ret);
4638
4639 btrfs_release_path(root, path);
4640 key.offset += num_bytes;
4641 } else {
4642 BUG_ON(1);
4643 #if 0
4644 u64 alloc_hint;
4645 u64 extent_len;
4646 int i;
4647 /*
4648 * drop old extent pointer at first, then insert the
4649 * new pointers one bye one
4650 */
4651 btrfs_release_path(root, path);
4652 ret = btrfs_drop_extents(trans, root, inode, key.offset,
4653 key.offset + num_bytes,
4654 key.offset, &alloc_hint);
4655 BUG_ON(ret);
4656
4657 for (i = 0; i < nr_extents; i++) {
4658 if (ext_offset >= new_extents[i].num_bytes) {
4659 ext_offset -= new_extents[i].num_bytes;
4660 continue;
4661 }
4662 extent_len = min(new_extents[i].num_bytes -
4663 ext_offset, num_bytes);
4664
4665 ret = btrfs_insert_empty_item(trans, root,
4666 path, &key,
4667 sizeof(*fi));
4668 BUG_ON(ret);
4669
4670 leaf = path->nodes[0];
4671 fi = btrfs_item_ptr(leaf, path->slots[0],
4672 struct btrfs_file_extent_item);
4673 btrfs_set_file_extent_generation(leaf, fi,
4674 trans->transid);
4675 btrfs_set_file_extent_type(leaf, fi,
4676 BTRFS_FILE_EXTENT_REG);
4677 btrfs_set_file_extent_disk_bytenr(leaf, fi,
4678 new_extents[i].disk_bytenr);
4679 btrfs_set_file_extent_disk_num_bytes(leaf, fi,
4680 new_extents[i].disk_num_bytes);
4681 btrfs_set_file_extent_ram_bytes(leaf, fi,
4682 new_extents[i].ram_bytes);
4683
4684 btrfs_set_file_extent_compression(leaf, fi,
4685 new_extents[i].compression);
4686 btrfs_set_file_extent_encryption(leaf, fi,
4687 new_extents[i].encryption);
4688 btrfs_set_file_extent_other_encoding(leaf, fi,
4689 new_extents[i].other_encoding);
4690
4691 btrfs_set_file_extent_num_bytes(leaf, fi,
4692 extent_len);
4693 ext_offset += new_extents[i].offset;
4694 btrfs_set_file_extent_offset(leaf, fi,
4695 ext_offset);
4696 btrfs_mark_buffer_dirty(leaf);
4697
4698 btrfs_drop_extent_cache(inode, key.offset,
4699 key.offset + extent_len - 1, 0);
4700
4701 ret = btrfs_inc_extent_ref(trans, root,
4702 new_extents[i].disk_bytenr,
4703 new_extents[i].disk_num_bytes,
4704 leaf->start,
4705 root->root_key.objectid,
4706 trans->transid, key.objectid);
4707 BUG_ON(ret);
4708 btrfs_release_path(root, path);
4709
4710 inode_add_bytes(inode, extent_len);
4711
4712 ext_offset = 0;
4713 num_bytes -= extent_len;
4714 key.offset += extent_len;
4715
4716 if (num_bytes == 0)
4717 break;
4718 }
4719 BUG_ON(i >= nr_extents);
4720 #endif
4721 }
4722
4723 if (extent_locked) {
4724 unlock_extent(&BTRFS_I(inode)->io_tree, lock_start,
4725 lock_end, GFP_NOFS);
4726 extent_locked = 0;
4727 }
4728 skip:
4729 if (ref_path->owner_objectid != BTRFS_MULTIPLE_OBJECTIDS &&
4730 key.offset >= search_end)
4731 break;
4732
4733 cond_resched();
4734 }
4735 ret = 0;
4736 out:
4737 btrfs_release_path(root, path);
4738 if (inode) {
4739 mutex_unlock(&inode->i_mutex);
4740 if (extent_locked) {
4741 unlock_extent(&BTRFS_I(inode)->io_tree, lock_start,
4742 lock_end, GFP_NOFS);
4743 }
4744 iput(inode);
4745 }
4746 return ret;
4747 }
4748
4749 int btrfs_reloc_tree_cache_ref(struct btrfs_trans_handle *trans,
4750 struct btrfs_root *root,
4751 struct extent_buffer *buf, u64 orig_start)
4752 {
4753 int level;
4754 int ret;
4755
4756 BUG_ON(btrfs_header_generation(buf) != trans->transid);
4757 BUG_ON(root->root_key.objectid != BTRFS_TREE_RELOC_OBJECTID);
4758
4759 level = btrfs_header_level(buf);
4760 if (level == 0) {
4761 struct btrfs_leaf_ref *ref;
4762 struct btrfs_leaf_ref *orig_ref;
4763
4764 orig_ref = btrfs_lookup_leaf_ref(root, orig_start);
4765 if (!orig_ref)
4766 return -ENOENT;
4767
4768 ref = btrfs_alloc_leaf_ref(root, orig_ref->nritems);
4769 if (!ref) {
4770 btrfs_free_leaf_ref(root, orig_ref);
4771 return -ENOMEM;
4772 }
4773
4774 ref->nritems = orig_ref->nritems;
4775 memcpy(ref->extents, orig_ref->extents,
4776 sizeof(ref->extents[0]) * ref->nritems);
4777
4778 btrfs_free_leaf_ref(root, orig_ref);
4779
4780 ref->root_gen = trans->transid;
4781 ref->bytenr = buf->start;
4782 ref->owner = btrfs_header_owner(buf);
4783 ref->generation = btrfs_header_generation(buf);
4784
4785 ret = btrfs_add_leaf_ref(root, ref, 0);
4786 WARN_ON(ret);
4787 btrfs_free_leaf_ref(root, ref);
4788 }
4789 return 0;
4790 }
4791
4792 static noinline int invalidate_extent_cache(struct btrfs_root *root,
4793 struct extent_buffer *leaf,
4794 struct btrfs_block_group_cache *group,
4795 struct btrfs_root *target_root)
4796 {
4797 struct btrfs_key key;
4798 struct inode *inode = NULL;
4799 struct btrfs_file_extent_item *fi;
4800 u64 num_bytes;
4801 u64 skip_objectid = 0;
4802 u32 nritems;
4803 u32 i;
4804
4805 nritems = btrfs_header_nritems(leaf);
4806 for (i = 0; i < nritems; i++) {
4807 btrfs_item_key_to_cpu(leaf, &key, i);
4808 if (key.objectid == skip_objectid ||
4809 key.type != BTRFS_EXTENT_DATA_KEY)
4810 continue;
4811 fi = btrfs_item_ptr(leaf, i, struct btrfs_file_extent_item);
4812 if (btrfs_file_extent_type(leaf, fi) ==
4813 BTRFS_FILE_EXTENT_INLINE)
4814 continue;
4815 if (btrfs_file_extent_disk_bytenr(leaf, fi) == 0)
4816 continue;
4817 if (!inode || inode->i_ino != key.objectid) {
4818 iput(inode);
4819 inode = btrfs_ilookup(target_root->fs_info->sb,
4820 key.objectid, target_root, 1);
4821 }
4822 if (!inode) {
4823 skip_objectid = key.objectid;
4824 continue;
4825 }
4826 num_bytes = btrfs_file_extent_num_bytes(leaf, fi);
4827
4828 lock_extent(&BTRFS_I(inode)->io_tree, key.offset,
4829 key.offset + num_bytes - 1, GFP_NOFS);
4830 btrfs_drop_extent_cache(inode, key.offset,
4831 key.offset + num_bytes - 1, 1);
4832 unlock_extent(&BTRFS_I(inode)->io_tree, key.offset,
4833 key.offset + num_bytes - 1, GFP_NOFS);
4834 cond_resched();
4835 }
4836 iput(inode);
4837 return 0;
4838 }
4839
4840 static noinline int replace_extents_in_leaf(struct btrfs_trans_handle *trans,
4841 struct btrfs_root *root,
4842 struct extent_buffer *leaf,
4843 struct btrfs_block_group_cache *group,
4844 struct inode *reloc_inode)
4845 {
4846 struct btrfs_key key;
4847 struct btrfs_key extent_key;
4848 struct btrfs_file_extent_item *fi;
4849 struct btrfs_leaf_ref *ref;
4850 struct disk_extent *new_extent;
4851 u64 bytenr;
4852 u64 num_bytes;
4853 u32 nritems;
4854 u32 i;
4855 int ext_index;
4856 int nr_extent;
4857 int ret;
4858
4859 new_extent = kmalloc(sizeof(*new_extent), GFP_NOFS);
4860 BUG_ON(!new_extent);
4861
4862 ref = btrfs_lookup_leaf_ref(root, leaf->start);
4863 BUG_ON(!ref);
4864
4865 ext_index = -1;
4866 nritems = btrfs_header_nritems(leaf);
4867 for (i = 0; i < nritems; i++) {
4868 btrfs_item_key_to_cpu(leaf, &key, i);
4869 if (btrfs_key_type(&key) != BTRFS_EXTENT_DATA_KEY)
4870 continue;
4871 fi = btrfs_item_ptr(leaf, i, struct btrfs_file_extent_item);
4872 if (btrfs_file_extent_type(leaf, fi) ==
4873 BTRFS_FILE_EXTENT_INLINE)
4874 continue;
4875 bytenr = btrfs_file_extent_disk_bytenr(leaf, fi);
4876 num_bytes = btrfs_file_extent_disk_num_bytes(leaf, fi);
4877 if (bytenr == 0)
4878 continue;
4879
4880 ext_index++;
4881 if (bytenr >= group->key.objectid + group->key.offset ||
4882 bytenr + num_bytes <= group->key.objectid)
4883 continue;
4884
4885 extent_key.objectid = bytenr;
4886 extent_key.offset = num_bytes;
4887 extent_key.type = BTRFS_EXTENT_ITEM_KEY;
4888 nr_extent = 1;
4889 ret = get_new_locations(reloc_inode, &extent_key,
4890 group->key.objectid, 1,
4891 &new_extent, &nr_extent);
4892 if (ret > 0)
4893 continue;
4894 BUG_ON(ret < 0);
4895
4896 BUG_ON(ref->extents[ext_index].bytenr != bytenr);
4897 BUG_ON(ref->extents[ext_index].num_bytes != num_bytes);
4898 ref->extents[ext_index].bytenr = new_extent->disk_bytenr;
4899 ref->extents[ext_index].num_bytes = new_extent->disk_num_bytes;
4900
4901 btrfs_set_file_extent_disk_bytenr(leaf, fi,
4902 new_extent->disk_bytenr);
4903 btrfs_set_file_extent_disk_num_bytes(leaf, fi,
4904 new_extent->disk_num_bytes);
4905 btrfs_mark_buffer_dirty(leaf);
4906
4907 ret = btrfs_inc_extent_ref(trans, root,
4908 new_extent->disk_bytenr,
4909 new_extent->disk_num_bytes,
4910 leaf->start,
4911 root->root_key.objectid,
4912 trans->transid, key.objectid);
4913 BUG_ON(ret);
4914
4915 ret = btrfs_free_extent(trans, root,
4916 bytenr, num_bytes, leaf->start,
4917 btrfs_header_owner(leaf),
4918 btrfs_header_generation(leaf),
4919 key.objectid, 0);
4920 BUG_ON(ret);
4921 cond_resched();
4922 }
4923 kfree(new_extent);
4924 BUG_ON(ext_index + 1 != ref->nritems);
4925 btrfs_free_leaf_ref(root, ref);
4926 return 0;
4927 }
4928
4929 int btrfs_free_reloc_root(struct btrfs_trans_handle *trans,
4930 struct btrfs_root *root)
4931 {
4932 struct btrfs_root *reloc_root;
4933 int ret;
4934
4935 if (root->reloc_root) {
4936 reloc_root = root->reloc_root;
4937 root->reloc_root = NULL;
4938 list_add(&reloc_root->dead_list,
4939 &root->fs_info->dead_reloc_roots);
4940
4941 btrfs_set_root_bytenr(&reloc_root->root_item,
4942 reloc_root->node->start);
4943 btrfs_set_root_level(&root->root_item,
4944 btrfs_header_level(reloc_root->node));
4945 memset(&reloc_root->root_item.drop_progress, 0,
4946 sizeof(struct btrfs_disk_key));
4947 reloc_root->root_item.drop_level = 0;
4948
4949 ret = btrfs_update_root(trans, root->fs_info->tree_root,
4950 &reloc_root->root_key,
4951 &reloc_root->root_item);
4952 BUG_ON(ret);
4953 }
4954 return 0;
4955 }
4956
4957 int btrfs_drop_dead_reloc_roots(struct btrfs_root *root)
4958 {
4959 struct btrfs_trans_handle *trans;
4960 struct btrfs_root *reloc_root;
4961 struct btrfs_root *prev_root = NULL;
4962 struct list_head dead_roots;
4963 int ret;
4964 unsigned long nr;
4965
4966 INIT_LIST_HEAD(&dead_roots);
4967 list_splice_init(&root->fs_info->dead_reloc_roots, &dead_roots);
4968
4969 while (!list_empty(&dead_roots)) {
4970 reloc_root = list_entry(dead_roots.prev,
4971 struct btrfs_root, dead_list);
4972 list_del_init(&reloc_root->dead_list);
4973
4974 BUG_ON(reloc_root->commit_root != NULL);
4975 while (1) {
4976 trans = btrfs_join_transaction(root, 1);
4977 BUG_ON(!trans);
4978
4979 mutex_lock(&root->fs_info->drop_mutex);
4980 ret = btrfs_drop_snapshot(trans, reloc_root);
4981 if (ret != -EAGAIN)
4982 break;
4983 mutex_unlock(&root->fs_info->drop_mutex);
4984
4985 nr = trans->blocks_used;
4986 ret = btrfs_end_transaction(trans, root);
4987 BUG_ON(ret);
4988 btrfs_btree_balance_dirty(root, nr);
4989 }
4990
4991 free_extent_buffer(reloc_root->node);
4992
4993 ret = btrfs_del_root(trans, root->fs_info->tree_root,
4994 &reloc_root->root_key);
4995 BUG_ON(ret);
4996 mutex_unlock(&root->fs_info->drop_mutex);
4997
4998 nr = trans->blocks_used;
4999 ret = btrfs_end_transaction(trans, root);
5000 BUG_ON(ret);
5001 btrfs_btree_balance_dirty(root, nr);
5002
5003 kfree(prev_root);
5004 prev_root = reloc_root;
5005 }
5006 if (prev_root) {
5007 btrfs_remove_leaf_refs(prev_root, (u64)-1, 0);
5008 kfree(prev_root);
5009 }
5010 return 0;
5011 }
5012
5013 int btrfs_add_dead_reloc_root(struct btrfs_root *root)
5014 {
5015 list_add(&root->dead_list, &root->fs_info->dead_reloc_roots);
5016 return 0;
5017 }
5018
5019 int btrfs_cleanup_reloc_trees(struct btrfs_root *root)
5020 {
5021 struct btrfs_root *reloc_root;
5022 struct btrfs_trans_handle *trans;
5023 struct btrfs_key location;
5024 int found;
5025 int ret;
5026
5027 mutex_lock(&root->fs_info->tree_reloc_mutex);
5028 ret = btrfs_find_dead_roots(root, BTRFS_TREE_RELOC_OBJECTID, NULL);
5029 BUG_ON(ret);
5030 found = !list_empty(&root->fs_info->dead_reloc_roots);
5031 mutex_unlock(&root->fs_info->tree_reloc_mutex);
5032
5033 if (found) {
5034 trans = btrfs_start_transaction(root, 1);
5035 BUG_ON(!trans);
5036 ret = btrfs_commit_transaction(trans, root);
5037 BUG_ON(ret);
5038 }
5039
5040 location.objectid = BTRFS_DATA_RELOC_TREE_OBJECTID;
5041 location.offset = (u64)-1;
5042 location.type = BTRFS_ROOT_ITEM_KEY;
5043
5044 reloc_root = btrfs_read_fs_root_no_name(root->fs_info, &location);
5045 BUG_ON(!reloc_root);
5046 btrfs_orphan_cleanup(reloc_root);
5047 return 0;
5048 }
5049
5050 static noinline int init_reloc_tree(struct btrfs_trans_handle *trans,
5051 struct btrfs_root *root)
5052 {
5053 struct btrfs_root *reloc_root;
5054 struct extent_buffer *eb;
5055 struct btrfs_root_item *root_item;
5056 struct btrfs_key root_key;
5057 int ret;
5058
5059 BUG_ON(!root->ref_cows);
5060 if (root->reloc_root)
5061 return 0;
5062
5063 root_item = kmalloc(sizeof(*root_item), GFP_NOFS);
5064 BUG_ON(!root_item);
5065
5066 ret = btrfs_copy_root(trans, root, root->commit_root,
5067 &eb, BTRFS_TREE_RELOC_OBJECTID);
5068 BUG_ON(ret);
5069
5070 root_key.objectid = BTRFS_TREE_RELOC_OBJECTID;
5071 root_key.offset = root->root_key.objectid;
5072 root_key.type = BTRFS_ROOT_ITEM_KEY;
5073
5074 memcpy(root_item, &root->root_item, sizeof(root_item));
5075 btrfs_set_root_refs(root_item, 0);
5076 btrfs_set_root_bytenr(root_item, eb->start);
5077 btrfs_set_root_level(root_item, btrfs_header_level(eb));
5078 btrfs_set_root_generation(root_item, trans->transid);
5079
5080 btrfs_tree_unlock(eb);
5081 free_extent_buffer(eb);
5082
5083 ret = btrfs_insert_root(trans, root->fs_info->tree_root,
5084 &root_key, root_item);
5085 BUG_ON(ret);
5086 kfree(root_item);
5087
5088 reloc_root = btrfs_read_fs_root_no_radix(root->fs_info->tree_root,
5089 &root_key);
5090 BUG_ON(!reloc_root);
5091 reloc_root->last_trans = trans->transid;
5092 reloc_root->commit_root = NULL;
5093 reloc_root->ref_tree = &root->fs_info->reloc_ref_tree;
5094
5095 root->reloc_root = reloc_root;
5096 return 0;
5097 }
5098
5099 /*
5100 * Core function of space balance.
5101 *
5102 * The idea is using reloc trees to relocate tree blocks in reference
5103 * counted roots. There is one reloc tree for each subvol, and all
5104 * reloc trees share same root key objectid. Reloc trees are snapshots
5105 * of the latest committed roots of subvols (root->commit_root).
5106 *
5107 * To relocate a tree block referenced by a subvol, there are two steps.
5108 * COW the block through subvol's reloc tree, then update block pointer
5109 * in the subvol to point to the new block. Since all reloc trees share
5110 * same root key objectid, doing special handing for tree blocks owned
5111 * by them is easy. Once a tree block has been COWed in one reloc tree,
5112 * we can use the resulting new block directly when the same block is
5113 * required to COW again through other reloc trees. By this way, relocated
5114 * tree blocks are shared between reloc trees, so they are also shared
5115 * between subvols.
5116 */
5117 static noinline int relocate_one_path(struct btrfs_trans_handle *trans,
5118 struct btrfs_root *root,
5119 struct btrfs_path *path,
5120 struct btrfs_key *first_key,
5121 struct btrfs_ref_path *ref_path,
5122 struct btrfs_block_group_cache *group,
5123 struct inode *reloc_inode)
5124 {
5125 struct btrfs_root *reloc_root;
5126 struct extent_buffer *eb = NULL;
5127 struct btrfs_key *keys;
5128 u64 *nodes;
5129 int level;
5130 int shared_level;
5131 int lowest_level = 0;
5132 int ret;
5133
5134 if (ref_path->owner_objectid < BTRFS_FIRST_FREE_OBJECTID)
5135 lowest_level = ref_path->owner_objectid;
5136
5137 if (!root->ref_cows) {
5138 path->lowest_level = lowest_level;
5139 ret = btrfs_search_slot(trans, root, first_key, path, 0, 1);
5140 BUG_ON(ret < 0);
5141 path->lowest_level = 0;
5142 btrfs_release_path(root, path);
5143 return 0;
5144 }
5145
5146 mutex_lock(&root->fs_info->tree_reloc_mutex);
5147 ret = init_reloc_tree(trans, root);
5148 BUG_ON(ret);
5149 reloc_root = root->reloc_root;
5150
5151 shared_level = ref_path->shared_level;
5152 ref_path->shared_level = BTRFS_MAX_LEVEL - 1;
5153
5154 keys = ref_path->node_keys;
5155 nodes = ref_path->new_nodes;
5156 memset(&keys[shared_level + 1], 0,
5157 sizeof(*keys) * (BTRFS_MAX_LEVEL - shared_level - 1));
5158 memset(&nodes[shared_level + 1], 0,
5159 sizeof(*nodes) * (BTRFS_MAX_LEVEL - shared_level - 1));
5160
5161 if (nodes[lowest_level] == 0) {
5162 path->lowest_level = lowest_level;
5163 ret = btrfs_search_slot(trans, reloc_root, first_key, path,
5164 0, 1);
5165 BUG_ON(ret);
5166 for (level = lowest_level; level < BTRFS_MAX_LEVEL; level++) {
5167 eb = path->nodes[level];
5168 if (!eb || eb == reloc_root->node)
5169 break;
5170 nodes[level] = eb->start;
5171 if (level == 0)
5172 btrfs_item_key_to_cpu(eb, &keys[level], 0);
5173 else
5174 btrfs_node_key_to_cpu(eb, &keys[level], 0);
5175 }
5176 if (nodes[0] &&
5177 ref_path->owner_objectid >= BTRFS_FIRST_FREE_OBJECTID) {
5178 eb = path->nodes[0];
5179 ret = replace_extents_in_leaf(trans, reloc_root, eb,
5180 group, reloc_inode);
5181 BUG_ON(ret);
5182 }
5183 btrfs_release_path(reloc_root, path);
5184 } else {
5185 ret = btrfs_merge_path(trans, reloc_root, keys, nodes,
5186 lowest_level);
5187 BUG_ON(ret);
5188 }
5189
5190 /*
5191 * replace tree blocks in the fs tree with tree blocks in
5192 * the reloc tree.
5193 */
5194 ret = btrfs_merge_path(trans, root, keys, nodes, lowest_level);
5195 BUG_ON(ret < 0);
5196
5197 if (ref_path->owner_objectid >= BTRFS_FIRST_FREE_OBJECTID) {
5198 ret = btrfs_search_slot(trans, reloc_root, first_key, path,
5199 0, 0);
5200 BUG_ON(ret);
5201 extent_buffer_get(path->nodes[0]);
5202 eb = path->nodes[0];
5203 btrfs_release_path(reloc_root, path);
5204 ret = invalidate_extent_cache(reloc_root, eb, group, root);
5205 BUG_ON(ret);
5206 free_extent_buffer(eb);
5207 }
5208
5209 mutex_unlock(&root->fs_info->tree_reloc_mutex);
5210 path->lowest_level = 0;
5211 return 0;
5212 }
5213
5214 static noinline int relocate_tree_block(struct btrfs_trans_handle *trans,
5215 struct btrfs_root *root,
5216 struct btrfs_path *path,
5217 struct btrfs_key *first_key,
5218 struct btrfs_ref_path *ref_path)
5219 {
5220 int ret;
5221
5222 ret = relocate_one_path(trans, root, path, first_key,
5223 ref_path, NULL, NULL);
5224 BUG_ON(ret);
5225
5226 return 0;
5227 }
5228
5229 static noinline int del_extent_zero(struct btrfs_trans_handle *trans,
5230 struct btrfs_root *extent_root,
5231 struct btrfs_path *path,
5232 struct btrfs_key *extent_key)
5233 {
5234 int ret;
5235
5236 ret = btrfs_search_slot(trans, extent_root, extent_key, path, -1, 1);
5237 if (ret)
5238 goto out;
5239 ret = btrfs_del_item(trans, extent_root, path);
5240 out:
5241 btrfs_release_path(extent_root, path);
5242 return ret;
5243 }
5244
5245 static noinline struct btrfs_root *read_ref_root(struct btrfs_fs_info *fs_info,
5246 struct btrfs_ref_path *ref_path)
5247 {
5248 struct btrfs_key root_key;
5249
5250 root_key.objectid = ref_path->root_objectid;
5251 root_key.type = BTRFS_ROOT_ITEM_KEY;
5252 if (is_cowonly_root(ref_path->root_objectid))
5253 root_key.offset = 0;
5254 else
5255 root_key.offset = (u64)-1;
5256
5257 return btrfs_read_fs_root_no_name(fs_info, &root_key);
5258 }
5259
5260 static noinline int relocate_one_extent(struct btrfs_root *extent_root,
5261 struct btrfs_path *path,
5262 struct btrfs_key *extent_key,
5263 struct btrfs_block_group_cache *group,
5264 struct inode *reloc_inode, int pass)
5265 {
5266 struct btrfs_trans_handle *trans;
5267 struct btrfs_root *found_root;
5268 struct btrfs_ref_path *ref_path = NULL;
5269 struct disk_extent *new_extents = NULL;
5270 int nr_extents = 0;
5271 int loops;
5272 int ret;
5273 int level;
5274 struct btrfs_key first_key;
5275 u64 prev_block = 0;
5276
5277
5278 trans = btrfs_start_transaction(extent_root, 1);
5279 BUG_ON(!trans);
5280
5281 if (extent_key->objectid == 0) {
5282 ret = del_extent_zero(trans, extent_root, path, extent_key);
5283 goto out;
5284 }
5285
5286 ref_path = kmalloc(sizeof(*ref_path), GFP_NOFS);
5287 if (!ref_path) {
5288 ret = -ENOMEM;
5289 goto out;
5290 }
5291
5292 for (loops = 0; ; loops++) {
5293 if (loops == 0) {
5294 ret = btrfs_first_ref_path(trans, extent_root, ref_path,
5295 extent_key->objectid);
5296 } else {
5297 ret = btrfs_next_ref_path(trans, extent_root, ref_path);
5298 }
5299 if (ret < 0)
5300 goto out;
5301 if (ret > 0)
5302 break;
5303
5304 if (ref_path->root_objectid == BTRFS_TREE_LOG_OBJECTID ||
5305 ref_path->root_objectid == BTRFS_TREE_RELOC_OBJECTID)
5306 continue;
5307
5308 found_root = read_ref_root(extent_root->fs_info, ref_path);
5309 BUG_ON(!found_root);
5310 /*
5311 * for reference counted tree, only process reference paths
5312 * rooted at the latest committed root.
5313 */
5314 if (found_root->ref_cows &&
5315 ref_path->root_generation != found_root->root_key.offset)
5316 continue;
5317
5318 if (ref_path->owner_objectid >= BTRFS_FIRST_FREE_OBJECTID) {
5319 if (pass == 0) {
5320 /*
5321 * copy data extents to new locations
5322 */
5323 u64 group_start = group->key.objectid;
5324 ret = relocate_data_extent(reloc_inode,
5325 extent_key,
5326 group_start);
5327 if (ret < 0)
5328 goto out;
5329 break;
5330 }
5331 level = 0;
5332 } else {
5333 level = ref_path->owner_objectid;
5334 }
5335
5336 if (prev_block != ref_path->nodes[level]) {
5337 struct extent_buffer *eb;
5338 u64 block_start = ref_path->nodes[level];
5339 u64 block_size = btrfs_level_size(found_root, level);
5340
5341 eb = read_tree_block(found_root, block_start,
5342 block_size, 0);
5343 btrfs_tree_lock(eb);
5344 BUG_ON(level != btrfs_header_level(eb));
5345
5346 if (level == 0)
5347 btrfs_item_key_to_cpu(eb, &first_key, 0);
5348 else
5349 btrfs_node_key_to_cpu(eb, &first_key, 0);
5350
5351 btrfs_tree_unlock(eb);
5352 free_extent_buffer(eb);
5353 prev_block = block_start;
5354 }
5355
5356 mutex_lock(&extent_root->fs_info->trans_mutex);
5357 btrfs_record_root_in_trans(found_root);
5358 mutex_unlock(&extent_root->fs_info->trans_mutex);
5359 if (ref_path->owner_objectid >= BTRFS_FIRST_FREE_OBJECTID) {
5360 /*
5361 * try to update data extent references while
5362 * keeping metadata shared between snapshots.
5363 */
5364 if (pass == 1) {
5365 ret = relocate_one_path(trans, found_root,
5366 path, &first_key, ref_path,
5367 group, reloc_inode);
5368 if (ret < 0)
5369 goto out;
5370 continue;
5371 }
5372 /*
5373 * use fallback method to process the remaining
5374 * references.
5375 */
5376 if (!new_extents) {
5377 u64 group_start = group->key.objectid;
5378 new_extents = kmalloc(sizeof(*new_extents),
5379 GFP_NOFS);
5380 nr_extents = 1;
5381 ret = get_new_locations(reloc_inode,
5382 extent_key,
5383 group_start, 1,
5384 &new_extents,
5385 &nr_extents);
5386 if (ret)
5387 goto out;
5388 }
5389 ret = replace_one_extent(trans, found_root,
5390 path, extent_key,
5391 &first_key, ref_path,
5392 new_extents, nr_extents);
5393 } else {
5394 ret = relocate_tree_block(trans, found_root, path,
5395 &first_key, ref_path);
5396 }
5397 if (ret < 0)
5398 goto out;
5399 }
5400 ret = 0;
5401 out:
5402 btrfs_end_transaction(trans, extent_root);
5403 kfree(new_extents);
5404 kfree(ref_path);
5405 return ret;
5406 }
5407
5408 static u64 update_block_group_flags(struct btrfs_root *root, u64 flags)
5409 {
5410 u64 num_devices;
5411 u64 stripped = BTRFS_BLOCK_GROUP_RAID0 |
5412 BTRFS_BLOCK_GROUP_RAID1 | BTRFS_BLOCK_GROUP_RAID10;
5413
5414 num_devices = root->fs_info->fs_devices->rw_devices;
5415 if (num_devices == 1) {
5416 stripped |= BTRFS_BLOCK_GROUP_DUP;
5417 stripped = flags & ~stripped;
5418
5419 /* turn raid0 into single device chunks */
5420 if (flags & BTRFS_BLOCK_GROUP_RAID0)
5421 return stripped;
5422
5423 /* turn mirroring into duplication */
5424 if (flags & (BTRFS_BLOCK_GROUP_RAID1 |
5425 BTRFS_BLOCK_GROUP_RAID10))
5426 return stripped | BTRFS_BLOCK_GROUP_DUP;
5427 return flags;
5428 } else {
5429 /* they already had raid on here, just return */
5430 if (flags & stripped)
5431 return flags;
5432
5433 stripped |= BTRFS_BLOCK_GROUP_DUP;
5434 stripped = flags & ~stripped;
5435
5436 /* switch duplicated blocks with raid1 */
5437 if (flags & BTRFS_BLOCK_GROUP_DUP)
5438 return stripped | BTRFS_BLOCK_GROUP_RAID1;
5439
5440 /* turn single device chunks into raid0 */
5441 return stripped | BTRFS_BLOCK_GROUP_RAID0;
5442 }
5443 return flags;
5444 }
5445
5446 static int __alloc_chunk_for_shrink(struct btrfs_root *root,
5447 struct btrfs_block_group_cache *shrink_block_group,
5448 int force)
5449 {
5450 struct btrfs_trans_handle *trans;
5451 u64 new_alloc_flags;
5452 u64 calc;
5453
5454 spin_lock(&shrink_block_group->lock);
5455 if (btrfs_block_group_used(&shrink_block_group->item) > 0) {
5456 spin_unlock(&shrink_block_group->lock);
5457
5458 trans = btrfs_start_transaction(root, 1);
5459 spin_lock(&shrink_block_group->lock);
5460
5461 new_alloc_flags = update_block_group_flags(root,
5462 shrink_block_group->flags);
5463 if (new_alloc_flags != shrink_block_group->flags) {
5464 calc =
5465 btrfs_block_group_used(&shrink_block_group->item);
5466 } else {
5467 calc = shrink_block_group->key.offset;
5468 }
5469 spin_unlock(&shrink_block_group->lock);
5470
5471 do_chunk_alloc(trans, root->fs_info->extent_root,
5472 calc + 2 * 1024 * 1024, new_alloc_flags, force);
5473
5474 btrfs_end_transaction(trans, root);
5475 } else
5476 spin_unlock(&shrink_block_group->lock);
5477 return 0;
5478 }
5479
5480 static int __insert_orphan_inode(struct btrfs_trans_handle *trans,
5481 struct btrfs_root *root,
5482 u64 objectid, u64 size)
5483 {
5484 struct btrfs_path *path;
5485 struct btrfs_inode_item *item;
5486 struct extent_buffer *leaf;
5487 int ret;
5488
5489 path = btrfs_alloc_path();
5490 if (!path)
5491 return -ENOMEM;
5492
5493 path->leave_spinning = 1;
5494 ret = btrfs_insert_empty_inode(trans, root, path, objectid);
5495 if (ret)
5496 goto out;
5497
5498 leaf = path->nodes[0];
5499 item = btrfs_item_ptr(leaf, path->slots[0], struct btrfs_inode_item);
5500 memset_extent_buffer(leaf, 0, (unsigned long)item, sizeof(*item));
5501 btrfs_set_inode_generation(leaf, item, 1);
5502 btrfs_set_inode_size(leaf, item, size);
5503 btrfs_set_inode_mode(leaf, item, S_IFREG | 0600);
5504 btrfs_set_inode_flags(leaf, item, BTRFS_INODE_NOCOMPRESS);
5505 btrfs_mark_buffer_dirty(leaf);
5506 btrfs_release_path(root, path);
5507 out:
5508 btrfs_free_path(path);
5509 return ret;
5510 }
5511
5512 static noinline struct inode *create_reloc_inode(struct btrfs_fs_info *fs_info,
5513 struct btrfs_block_group_cache *group)
5514 {
5515 struct inode *inode = NULL;
5516 struct btrfs_trans_handle *trans;
5517 struct btrfs_root *root;
5518 struct btrfs_key root_key;
5519 u64 objectid = BTRFS_FIRST_FREE_OBJECTID;
5520 int err = 0;
5521
5522 root_key.objectid = BTRFS_DATA_RELOC_TREE_OBJECTID;
5523 root_key.type = BTRFS_ROOT_ITEM_KEY;
5524 root_key.offset = (u64)-1;
5525 root = btrfs_read_fs_root_no_name(fs_info, &root_key);
5526 if (IS_ERR(root))
5527 return ERR_CAST(root);
5528
5529 trans = btrfs_start_transaction(root, 1);
5530 BUG_ON(!trans);
5531
5532 err = btrfs_find_free_objectid(trans, root, objectid, &objectid);
5533 if (err)
5534 goto out;
5535
5536 err = __insert_orphan_inode(trans, root, objectid, group->key.offset);
5537 BUG_ON(err);
5538
5539 err = btrfs_insert_file_extent(trans, root, objectid, 0, 0, 0,
5540 group->key.offset, 0, group->key.offset,
5541 0, 0, 0);
5542 BUG_ON(err);
5543
5544 inode = btrfs_iget_locked(root->fs_info->sb, objectid, root);
5545 if (inode->i_state & I_NEW) {
5546 BTRFS_I(inode)->root = root;
5547 BTRFS_I(inode)->location.objectid = objectid;
5548 BTRFS_I(inode)->location.type = BTRFS_INODE_ITEM_KEY;
5549 BTRFS_I(inode)->location.offset = 0;
5550 btrfs_read_locked_inode(inode);
5551 unlock_new_inode(inode);
5552 BUG_ON(is_bad_inode(inode));
5553 } else {
5554 BUG_ON(1);
5555 }
5556 BTRFS_I(inode)->index_cnt = group->key.objectid;
5557
5558 err = btrfs_orphan_add(trans, inode);
5559 out:
5560 btrfs_end_transaction(trans, root);
5561 if (err) {
5562 if (inode)
5563 iput(inode);
5564 inode = ERR_PTR(err);
5565 }
5566 return inode;
5567 }
5568
5569 int btrfs_reloc_clone_csums(struct inode *inode, u64 file_pos, u64 len)
5570 {
5571
5572 struct btrfs_ordered_sum *sums;
5573 struct btrfs_sector_sum *sector_sum;
5574 struct btrfs_ordered_extent *ordered;
5575 struct btrfs_root *root = BTRFS_I(inode)->root;
5576 struct list_head list;
5577 size_t offset;
5578 int ret;
5579 u64 disk_bytenr;
5580
5581 INIT_LIST_HEAD(&list);
5582
5583 ordered = btrfs_lookup_ordered_extent(inode, file_pos);
5584 BUG_ON(ordered->file_offset != file_pos || ordered->len != len);
5585
5586 disk_bytenr = file_pos + BTRFS_I(inode)->index_cnt;
5587 ret = btrfs_lookup_csums_range(root->fs_info->csum_root, disk_bytenr,
5588 disk_bytenr + len - 1, &list);
5589
5590 while (!list_empty(&list)) {
5591 sums = list_entry(list.next, struct btrfs_ordered_sum, list);
5592 list_del_init(&sums->list);
5593
5594 sector_sum = sums->sums;
5595 sums->bytenr = ordered->start;
5596
5597 offset = 0;
5598 while (offset < sums->len) {
5599 sector_sum->bytenr += ordered->start - disk_bytenr;
5600 sector_sum++;
5601 offset += root->sectorsize;
5602 }
5603
5604 btrfs_add_ordered_sum(inode, ordered, sums);
5605 }
5606 btrfs_put_ordered_extent(ordered);
5607 return 0;
5608 }
5609
5610 int btrfs_relocate_block_group(struct btrfs_root *root, u64 group_start)
5611 {
5612 struct btrfs_trans_handle *trans;
5613 struct btrfs_path *path;
5614 struct btrfs_fs_info *info = root->fs_info;
5615 struct extent_buffer *leaf;
5616 struct inode *reloc_inode;
5617 struct btrfs_block_group_cache *block_group;
5618 struct btrfs_key key;
5619 u64 skipped;
5620 u64 cur_byte;
5621 u64 total_found;
5622 u32 nritems;
5623 int ret;
5624 int progress;
5625 int pass = 0;
5626
5627 root = root->fs_info->extent_root;
5628
5629 block_group = btrfs_lookup_block_group(info, group_start);
5630 BUG_ON(!block_group);
5631
5632 printk(KERN_INFO "btrfs relocating block group %llu flags %llu\n",
5633 (unsigned long long)block_group->key.objectid,
5634 (unsigned long long)block_group->flags);
5635
5636 path = btrfs_alloc_path();
5637 BUG_ON(!path);
5638
5639 reloc_inode = create_reloc_inode(info, block_group);
5640 BUG_ON(IS_ERR(reloc_inode));
5641
5642 __alloc_chunk_for_shrink(root, block_group, 1);
5643 set_block_group_readonly(block_group);
5644
5645 btrfs_start_delalloc_inodes(info->tree_root);
5646 btrfs_wait_ordered_extents(info->tree_root, 0);
5647 again:
5648 skipped = 0;
5649 total_found = 0;
5650 progress = 0;
5651 key.objectid = block_group->key.objectid;
5652 key.offset = 0;
5653 key.type = 0;
5654 cur_byte = key.objectid;
5655
5656 trans = btrfs_start_transaction(info->tree_root, 1);
5657 btrfs_commit_transaction(trans, info->tree_root);
5658
5659 mutex_lock(&root->fs_info->cleaner_mutex);
5660 btrfs_clean_old_snapshots(info->tree_root);
5661 btrfs_remove_leaf_refs(info->tree_root, (u64)-1, 1);
5662 mutex_unlock(&root->fs_info->cleaner_mutex);
5663
5664 trans = btrfs_start_transaction(info->tree_root, 1);
5665 btrfs_commit_transaction(trans, info->tree_root);
5666
5667 while (1) {
5668 ret = btrfs_search_slot(NULL, root, &key, path, 0, 0);
5669 if (ret < 0)
5670 goto out;
5671 next:
5672 leaf = path->nodes[0];
5673 nritems = btrfs_header_nritems(leaf);
5674 if (path->slots[0] >= nritems) {
5675 ret = btrfs_next_leaf(root, path);
5676 if (ret < 0)
5677 goto out;
5678 if (ret == 1) {
5679 ret = 0;
5680 break;
5681 }
5682 leaf = path->nodes[0];
5683 nritems = btrfs_header_nritems(leaf);
5684 }
5685
5686 btrfs_item_key_to_cpu(leaf, &key, path->slots[0]);
5687
5688 if (key.objectid >= block_group->key.objectid +
5689 block_group->key.offset)
5690 break;
5691
5692 if (progress && need_resched()) {
5693 btrfs_release_path(root, path);
5694 cond_resched();
5695 progress = 0;
5696 continue;
5697 }
5698 progress = 1;
5699
5700 if (btrfs_key_type(&key) != BTRFS_EXTENT_ITEM_KEY ||
5701 key.objectid + key.offset <= cur_byte) {
5702 path->slots[0]++;
5703 goto next;
5704 }
5705
5706 total_found++;
5707 cur_byte = key.objectid + key.offset;
5708 btrfs_release_path(root, path);
5709
5710 __alloc_chunk_for_shrink(root, block_group, 0);
5711 ret = relocate_one_extent(root, path, &key, block_group,
5712 reloc_inode, pass);
5713 BUG_ON(ret < 0);
5714 if (ret > 0)
5715 skipped++;
5716
5717 key.objectid = cur_byte;
5718 key.type = 0;
5719 key.offset = 0;
5720 }
5721
5722 btrfs_release_path(root, path);
5723
5724 if (pass == 0) {
5725 btrfs_wait_ordered_range(reloc_inode, 0, (u64)-1);
5726 invalidate_mapping_pages(reloc_inode->i_mapping, 0, -1);
5727 }
5728
5729 if (total_found > 0) {
5730 printk(KERN_INFO "btrfs found %llu extents in pass %d\n",
5731 (unsigned long long)total_found, pass);
5732 pass++;
5733 if (total_found == skipped && pass > 2) {
5734 iput(reloc_inode);
5735 reloc_inode = create_reloc_inode(info, block_group);
5736 pass = 0;
5737 }
5738 goto again;
5739 }
5740
5741 /* delete reloc_inode */
5742 iput(reloc_inode);
5743
5744 /* unpin extents in this range */
5745 trans = btrfs_start_transaction(info->tree_root, 1);
5746 btrfs_commit_transaction(trans, info->tree_root);
5747
5748 spin_lock(&block_group->lock);
5749 WARN_ON(block_group->pinned > 0);
5750 WARN_ON(block_group->reserved > 0);
5751 WARN_ON(btrfs_block_group_used(&block_group->item) > 0);
5752 spin_unlock(&block_group->lock);
5753 btrfs_put_block_group(block_group);
5754 ret = 0;
5755 out:
5756 btrfs_free_path(path);
5757 return ret;
5758 }
5759
5760 static int find_first_block_group(struct btrfs_root *root,
5761 struct btrfs_path *path, struct btrfs_key *key)
5762 {
5763 int ret = 0;
5764 struct btrfs_key found_key;
5765 struct extent_buffer *leaf;
5766 int slot;
5767
5768 ret = btrfs_search_slot(NULL, root, key, path, 0, 0);
5769 if (ret < 0)
5770 goto out;
5771
5772 while (1) {
5773 slot = path->slots[0];
5774 leaf = path->nodes[0];
5775 if (slot >= btrfs_header_nritems(leaf)) {
5776 ret = btrfs_next_leaf(root, path);
5777 if (ret == 0)
5778 continue;
5779 if (ret < 0)
5780 goto out;
5781 break;
5782 }
5783 btrfs_item_key_to_cpu(leaf, &found_key, slot);
5784
5785 if (found_key.objectid >= key->objectid &&
5786 found_key.type == BTRFS_BLOCK_GROUP_ITEM_KEY) {
5787 ret = 0;
5788 goto out;
5789 }
5790 path->slots[0]++;
5791 }
5792 ret = -ENOENT;
5793 out:
5794 return ret;
5795 }
5796
5797 int btrfs_free_block_groups(struct btrfs_fs_info *info)
5798 {
5799 struct btrfs_block_group_cache *block_group;
5800 struct btrfs_space_info *space_info;
5801 struct rb_node *n;
5802
5803 spin_lock(&info->block_group_cache_lock);
5804 while ((n = rb_last(&info->block_group_cache_tree)) != NULL) {
5805 block_group = rb_entry(n, struct btrfs_block_group_cache,
5806 cache_node);
5807 rb_erase(&block_group->cache_node,
5808 &info->block_group_cache_tree);
5809 spin_unlock(&info->block_group_cache_lock);
5810
5811 btrfs_remove_free_space_cache(block_group);
5812 down_write(&block_group->space_info->groups_sem);
5813 list_del(&block_group->list);
5814 up_write(&block_group->space_info->groups_sem);
5815
5816 WARN_ON(atomic_read(&block_group->count) != 1);
5817 kfree(block_group);
5818
5819 spin_lock(&info->block_group_cache_lock);
5820 }
5821 spin_unlock(&info->block_group_cache_lock);
5822
5823 /* now that all the block groups are freed, go through and
5824 * free all the space_info structs. This is only called during
5825 * the final stages of unmount, and so we know nobody is
5826 * using them. We call synchronize_rcu() once before we start,
5827 * just to be on the safe side.
5828 */
5829 synchronize_rcu();
5830
5831 while(!list_empty(&info->space_info)) {
5832 space_info = list_entry(info->space_info.next,
5833 struct btrfs_space_info,
5834 list);
5835
5836 list_del(&space_info->list);
5837 kfree(space_info);
5838 }
5839 return 0;
5840 }
5841
5842 int btrfs_read_block_groups(struct btrfs_root *root)
5843 {
5844 struct btrfs_path *path;
5845 int ret;
5846 struct btrfs_block_group_cache *cache;
5847 struct btrfs_fs_info *info = root->fs_info;
5848 struct btrfs_space_info *space_info;
5849 struct btrfs_key key;
5850 struct btrfs_key found_key;
5851 struct extent_buffer *leaf;
5852
5853 root = info->extent_root;
5854 key.objectid = 0;
5855 key.offset = 0;
5856 btrfs_set_key_type(&key, BTRFS_BLOCK_GROUP_ITEM_KEY);
5857 path = btrfs_alloc_path();
5858 if (!path)
5859 return -ENOMEM;
5860
5861 while (1) {
5862 ret = find_first_block_group(root, path, &key);
5863 if (ret > 0) {
5864 ret = 0;
5865 goto error;
5866 }
5867 if (ret != 0)
5868 goto error;
5869
5870 leaf = path->nodes[0];
5871 btrfs_item_key_to_cpu(leaf, &found_key, path->slots[0]);
5872 cache = kzalloc(sizeof(*cache), GFP_NOFS);
5873 if (!cache) {
5874 ret = -ENOMEM;
5875 break;
5876 }
5877
5878 atomic_set(&cache->count, 1);
5879 spin_lock_init(&cache->lock);
5880 spin_lock_init(&cache->tree_lock);
5881 mutex_init(&cache->cache_mutex);
5882 INIT_LIST_HEAD(&cache->list);
5883 INIT_LIST_HEAD(&cache->cluster_list);
5884 read_extent_buffer(leaf, &cache->item,
5885 btrfs_item_ptr_offset(leaf, path->slots[0]),
5886 sizeof(cache->item));
5887 memcpy(&cache->key, &found_key, sizeof(found_key));
5888
5889 key.objectid = found_key.objectid + found_key.offset;
5890 btrfs_release_path(root, path);
5891 cache->flags = btrfs_block_group_flags(&cache->item);
5892
5893 ret = update_space_info(info, cache->flags, found_key.offset,
5894 btrfs_block_group_used(&cache->item),
5895 &space_info);
5896 BUG_ON(ret);
5897 cache->space_info = space_info;
5898 down_write(&space_info->groups_sem);
5899 list_add_tail(&cache->list, &space_info->block_groups);
5900 up_write(&space_info->groups_sem);
5901
5902 ret = btrfs_add_block_group_cache(root->fs_info, cache);
5903 BUG_ON(ret);
5904
5905 set_avail_alloc_bits(root->fs_info, cache->flags);
5906 if (btrfs_chunk_readonly(root, cache->key.objectid))
5907 set_block_group_readonly(cache);
5908 }
5909 ret = 0;
5910 error:
5911 btrfs_free_path(path);
5912 return ret;
5913 }
5914
5915 int btrfs_make_block_group(struct btrfs_trans_handle *trans,
5916 struct btrfs_root *root, u64 bytes_used,
5917 u64 type, u64 chunk_objectid, u64 chunk_offset,
5918 u64 size)
5919 {
5920 int ret;
5921 struct btrfs_root *extent_root;
5922 struct btrfs_block_group_cache *cache;
5923
5924 extent_root = root->fs_info->extent_root;
5925
5926 root->fs_info->last_trans_log_full_commit = trans->transid;
5927
5928 cache = kzalloc(sizeof(*cache), GFP_NOFS);
5929 if (!cache)
5930 return -ENOMEM;
5931
5932 cache->key.objectid = chunk_offset;
5933 cache->key.offset = size;
5934 cache->key.type = BTRFS_BLOCK_GROUP_ITEM_KEY;
5935 atomic_set(&cache->count, 1);
5936 spin_lock_init(&cache->lock);
5937 spin_lock_init(&cache->tree_lock);
5938 mutex_init(&cache->cache_mutex);
5939 INIT_LIST_HEAD(&cache->list);
5940 INIT_LIST_HEAD(&cache->cluster_list);
5941
5942 btrfs_set_block_group_used(&cache->item, bytes_used);
5943 btrfs_set_block_group_chunk_objectid(&cache->item, chunk_objectid);
5944 cache->flags = type;
5945 btrfs_set_block_group_flags(&cache->item, type);
5946
5947 ret = update_space_info(root->fs_info, cache->flags, size, bytes_used,
5948 &cache->space_info);
5949 BUG_ON(ret);
5950 down_write(&cache->space_info->groups_sem);
5951 list_add_tail(&cache->list, &cache->space_info->block_groups);
5952 up_write(&cache->space_info->groups_sem);
5953
5954 ret = btrfs_add_block_group_cache(root->fs_info, cache);
5955 BUG_ON(ret);
5956
5957 ret = btrfs_insert_item(trans, extent_root, &cache->key, &cache->item,
5958 sizeof(cache->item));
5959 BUG_ON(ret);
5960
5961 set_avail_alloc_bits(extent_root->fs_info, type);
5962
5963 return 0;
5964 }
5965
5966 int btrfs_remove_block_group(struct btrfs_trans_handle *trans,
5967 struct btrfs_root *root, u64 group_start)
5968 {
5969 struct btrfs_path *path;
5970 struct btrfs_block_group_cache *block_group;
5971 struct btrfs_key key;
5972 int ret;
5973
5974 root = root->fs_info->extent_root;
5975
5976 block_group = btrfs_lookup_block_group(root->fs_info, group_start);
5977 BUG_ON(!block_group);
5978 BUG_ON(!block_group->ro);
5979
5980 memcpy(&key, &block_group->key, sizeof(key));
5981
5982 path = btrfs_alloc_path();
5983 BUG_ON(!path);
5984
5985 spin_lock(&root->fs_info->block_group_cache_lock);
5986 rb_erase(&block_group->cache_node,
5987 &root->fs_info->block_group_cache_tree);
5988 spin_unlock(&root->fs_info->block_group_cache_lock);
5989 btrfs_remove_free_space_cache(block_group);
5990 down_write(&block_group->space_info->groups_sem);
5991 list_del(&block_group->list);
5992 up_write(&block_group->space_info->groups_sem);
5993
5994 spin_lock(&block_group->space_info->lock);
5995 block_group->space_info->total_bytes -= block_group->key.offset;
5996 block_group->space_info->bytes_readonly -= block_group->key.offset;
5997 spin_unlock(&block_group->space_info->lock);
5998 block_group->space_info->full = 0;
5999
6000 btrfs_put_block_group(block_group);
6001 btrfs_put_block_group(block_group);
6002
6003 ret = btrfs_search_slot(trans, root, &key, path, -1, 1);
6004 if (ret > 0)
6005 ret = -EIO;
6006 if (ret < 0)
6007 goto out;
6008
6009 ret = btrfs_del_item(trans, root, path);
6010 out:
6011 btrfs_free_path(path);
6012 return ret;
6013 }
Support for the Chinese Samsung S3C2440 based development boards