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