projects / deliverable / linux.git / blob
? search:
summary | shortlog | log | commit | commitdiff | tree
blame | history | raw | HEAD
Btrfs: Handle writeback under high memory pressure better
[deliverable/linux.git] / fs / btrfs / extent-tree.c
1 /*
2 * Copyright (C) 2007 Oracle. All rights reserved.
3 *
4 * This program is free software; you can redistribute it and/or
5 * modify it under the terms of the GNU General Public
6 * License v2 as published by the Free Software Foundation.
7 *
8 * This program is distributed in the hope that it will be useful,
9 * but WITHOUT ANY WARRANTY; without even the implied warranty of
10 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
11 * General Public License for more details.
12 *
13 * You should have received a copy of the GNU General Public
14 * License along with this program; if not, write to the
15 * Free Software Foundation, Inc., 59 Temple Place - Suite 330,
16 * Boston, MA 021110-1307, USA.
17 */
18
19 #include <linux/sched.h>
20 #include "ctree.h"
21 #include "disk-io.h"
22 #include "print-tree.h"
23 #include "transaction.h"
24
25 #define BLOCK_GROUP_DATA EXTENT_WRITEBACK
26 #define BLOCK_GROUP_METADATA EXTENT_UPTODATE
27 #define BLOCK_GROUP_DIRTY EXTENT_DIRTY
28
29 static int finish_current_insert(struct btrfs_trans_handle *trans, struct
30 btrfs_root *extent_root);
31 static int del_pending_extents(struct btrfs_trans_handle *trans, struct
32 btrfs_root *extent_root);
33
34 static int cache_block_group(struct btrfs_root *root,
35 struct btrfs_block_group_cache *block_group)
36 {
37 struct btrfs_path *path;
38 int ret;
39 struct btrfs_key key;
40 struct extent_buffer *leaf;
41 struct extent_map_tree *free_space_cache;
42 int slot;
43 u64 last = 0;
44 u64 hole_size;
45 u64 first_free;
46 int found = 0;
47
48 root = root->fs_info->extent_root;
49 free_space_cache = &root->fs_info->free_space_cache;
50
51 if (block_group->cached)
52 return 0;
53
54 path = btrfs_alloc_path();
55 if (!path)
56 return -ENOMEM;
57
58 path->reada = 2;
59 first_free = block_group->key.objectid;
60 key.objectid = block_group->key.objectid;
61 key.offset = 0;
62
63 btrfs_set_key_type(&key, BTRFS_EXTENT_ITEM_KEY);
64 ret = btrfs_search_slot(NULL, root, &key, path, 0, 0);
65
66 if (ret < 0)
67 return ret;
68
69 if (ret && path->slots[0] > 0)
70 path->slots[0]--;
71
72 while(1) {
73 leaf = path->nodes[0];
74 slot = path->slots[0];
75 if (slot >= btrfs_header_nritems(leaf)) {
76 ret = btrfs_next_leaf(root, path);
77 if (ret < 0)
78 goto err;
79 if (ret == 0) {
80 continue;
81 } else {
82 break;
83 }
84 }
85
86 btrfs_item_key_to_cpu(leaf, &key, slot);
87 if (key.objectid < block_group->key.objectid) {
88 if (key.objectid + key.offset > first_free)
89 first_free = key.objectid + key.offset;
90 goto next;
91 }
92
93 if (key.objectid >= block_group->key.objectid +
94 block_group->key.offset) {
95 break;
96 }
97
98 if (btrfs_key_type(&key) == BTRFS_EXTENT_ITEM_KEY) {
99 if (!found) {
100 last = first_free;
101 found = 1;
102 }
103 if (key.objectid > last) {
104 hole_size = key.objectid - last;
105 set_extent_dirty(free_space_cache, last,
106 last + hole_size - 1,
107 GFP_NOFS);
108 }
109 last = key.objectid + key.offset;
110 }
111 next:
112 path->slots[0]++;
113 }
114
115 if (!found)
116 last = first_free;
117 if (block_group->key.objectid +
118 block_group->key.offset > last) {
119 hole_size = block_group->key.objectid +
120 block_group->key.offset - last;
121 set_extent_dirty(free_space_cache, last,
122 last + hole_size - 1, GFP_NOFS);
123 }
124 block_group->cached = 1;
125 err:
126 btrfs_free_path(path);
127 return 0;
128 }
129
130 struct btrfs_block_group_cache *btrfs_lookup_block_group(struct
131 btrfs_fs_info *info,
132 u64 bytenr)
133 {
134 struct extent_map_tree *block_group_cache;
135 struct btrfs_block_group_cache *block_group = NULL;
136 u64 ptr;
137 u64 start;
138 u64 end;
139 int ret;
140
141 block_group_cache = &info->block_group_cache;
142 ret = find_first_extent_bit(block_group_cache,
143 bytenr, &start, &end,
144 BLOCK_GROUP_DATA | BLOCK_GROUP_METADATA);
145 if (ret) {
146 return NULL;
147 }
148 ret = get_state_private(block_group_cache, start, &ptr);
149 if (ret)
150 return NULL;
151
152 block_group = (struct btrfs_block_group_cache *)(unsigned long)ptr;
153 if (block_group->key.objectid <= bytenr && bytenr <
154 block_group->key.objectid + block_group->key.offset)
155 return block_group;
156 return NULL;
157 }
158 static u64 find_search_start(struct btrfs_root *root,
159 struct btrfs_block_group_cache **cache_ret,
160 u64 search_start, int num,
161 int data, int full_scan)
162 {
163 int ret;
164 struct btrfs_block_group_cache *cache = *cache_ret;
165 u64 last;
166 u64 start = 0;
167 u64 end = 0;
168 u64 cache_miss = 0;
169 int wrapped = 0;
170
171 again:
172 ret = cache_block_group(root, cache);
173 if (ret)
174 goto out;
175
176 last = max(search_start, cache->key.objectid);
177
178 while(1) {
179 ret = find_first_extent_bit(&root->fs_info->free_space_cache,
180 last, &start, &end, EXTENT_DIRTY);
181 if (ret) {
182 if (!cache_miss)
183 cache_miss = last;
184 goto new_group;
185 }
186
187 start = max(last, start);
188 last = end + 1;
189 if (last - start < num) {
190 if (last == cache->key.objectid + cache->key.offset)
191 cache_miss = start;
192 continue;
193 }
194 if (data != BTRFS_BLOCK_GROUP_MIXED &&
195 start + num > cache->key.objectid + cache->key.offset)
196 goto new_group;
197 return start;
198 }
199 out:
200 return search_start;
201
202 new_group:
203 last = cache->key.objectid + cache->key.offset;
204 wrapped:
205 cache = btrfs_lookup_block_group(root->fs_info, last);
206 if (!cache) {
207 no_cache:
208 if (!wrapped) {
209 wrapped = 1;
210 last = search_start;
211 data = BTRFS_BLOCK_GROUP_MIXED;
212 goto wrapped;
213 }
214 return search_start;
215 }
216 if (cache_miss && !cache->cached) {
217 cache_block_group(root, cache);
218 last = cache_miss;
219 cache = btrfs_lookup_block_group(root->fs_info, last);
220 }
221 if (!full_scan)
222 cache = btrfs_find_block_group(root, cache, last, data, 0);
223 if (!cache)
224 goto no_cache;
225 *cache_ret = cache;
226 cache_miss = 0;
227 goto again;
228 }
229
230 static u64 div_factor(u64 num, int factor)
231 {
232 if (factor == 10)
233 return num;
234 num *= factor;
235 do_div(num, 10);
236 return num;
237 }
238
239 struct btrfs_block_group_cache *btrfs_find_block_group(struct btrfs_root *root,
240 struct btrfs_block_group_cache
241 *hint, u64 search_start,
242 int data, int owner)
243 {
244 struct btrfs_block_group_cache *cache;
245 struct extent_map_tree *block_group_cache;
246 struct btrfs_block_group_cache *found_group = NULL;
247 struct btrfs_fs_info *info = root->fs_info;
248 u64 used;
249 u64 last = 0;
250 u64 hint_last;
251 u64 start;
252 u64 end;
253 u64 free_check;
254 u64 ptr;
255 int bit;
256 int ret;
257 int full_search = 0;
258 int factor = 8;
259 int data_swap = 0;
260
261 block_group_cache = &info->block_group_cache;
262
263 if (!owner)
264 factor = 8;
265
266 if (data == BTRFS_BLOCK_GROUP_MIXED) {
267 bit = BLOCK_GROUP_DATA | BLOCK_GROUP_METADATA;
268 factor = 10;
269 } else if (data)
270 bit = BLOCK_GROUP_DATA;
271 else
272 bit = BLOCK_GROUP_METADATA;
273
274 if (search_start) {
275 struct btrfs_block_group_cache *shint;
276 shint = btrfs_lookup_block_group(info, search_start);
277 if (shint && (shint->data == data ||
278 shint->data == BTRFS_BLOCK_GROUP_MIXED)) {
279 used = btrfs_block_group_used(&shint->item);
280 if (used + shint->pinned <
281 div_factor(shint->key.offset, factor)) {
282 return shint;
283 }
284 }
285 }
286 if (hint && (hint->data == data ||
287 hint->data == BTRFS_BLOCK_GROUP_MIXED)) {
288 used = btrfs_block_group_used(&hint->item);
289 if (used + hint->pinned <
290 div_factor(hint->key.offset, factor)) {
291 return hint;
292 }
293 last = hint->key.objectid + hint->key.offset;
294 hint_last = last;
295 } else {
296 if (hint)
297 hint_last = max(hint->key.objectid, search_start);
298 else
299 hint_last = search_start;
300
301 last = hint_last;
302 }
303 again:
304 while(1) {
305 ret = find_first_extent_bit(block_group_cache, last,
306 &start, &end, bit);
307 if (ret)
308 break;
309
310 ret = get_state_private(block_group_cache, start, &ptr);
311 if (ret)
312 break;
313
314 cache = (struct btrfs_block_group_cache *)(unsigned long)ptr;
315 last = cache->key.objectid + cache->key.offset;
316 used = btrfs_block_group_used(&cache->item);
317
318 if (full_search)
319 free_check = cache->key.offset;
320 else
321 free_check = div_factor(cache->key.offset, factor);
322 if (used + cache->pinned < free_check) {
323 found_group = cache;
324 goto found;
325 }
326 cond_resched();
327 }
328 if (!full_search) {
329 last = search_start;
330 full_search = 1;
331 goto again;
332 }
333 if (!data_swap) {
334 data_swap = 1;
335 bit = BLOCK_GROUP_DATA | BLOCK_GROUP_METADATA;
336 last = search_start;
337 goto again;
338 }
339 found:
340 return found_group;
341 }
342
343 int btrfs_inc_extent_ref(struct btrfs_trans_handle *trans,
344 struct btrfs_root *root,
345 u64 bytenr, u64 num_bytes)
346 {
347 struct btrfs_path *path;
348 int ret;
349 struct btrfs_key key;
350 struct extent_buffer *l;
351 struct btrfs_extent_item *item;
352 u32 refs;
353
354 WARN_ON(num_bytes < root->sectorsize);
355 path = btrfs_alloc_path();
356 if (!path)
357 return -ENOMEM;
358
359 key.objectid = bytenr;
360 btrfs_set_key_type(&key, BTRFS_EXTENT_ITEM_KEY);
361 key.offset = num_bytes;
362 ret = btrfs_search_slot(trans, root->fs_info->extent_root, &key, path,
363 0, 1);
364 if (ret < 0)
365 return ret;
366 if (ret != 0) {
367 BUG();
368 }
369 BUG_ON(ret != 0);
370 l = path->nodes[0];
371 item = btrfs_item_ptr(l, path->slots[0], struct btrfs_extent_item);
372 refs = btrfs_extent_refs(l, item);
373 btrfs_set_extent_refs(l, item, refs + 1);
374 btrfs_mark_buffer_dirty(path->nodes[0]);
375
376 btrfs_release_path(root->fs_info->extent_root, path);
377 btrfs_free_path(path);
378 finish_current_insert(trans, root->fs_info->extent_root);
379 del_pending_extents(trans, root->fs_info->extent_root);
380 return 0;
381 }
382
383 int btrfs_extent_post_op(struct btrfs_trans_handle *trans,
384 struct btrfs_root *root)
385 {
386 finish_current_insert(trans, root->fs_info->extent_root);
387 del_pending_extents(trans, root->fs_info->extent_root);
388 return 0;
389 }
390
391 static int lookup_extent_ref(struct btrfs_trans_handle *trans,
392 struct btrfs_root *root, u64 bytenr,
393 u64 num_bytes, u32 *refs)
394 {
395 struct btrfs_path *path;
396 int ret;
397 struct btrfs_key key;
398 struct extent_buffer *l;
399 struct btrfs_extent_item *item;
400
401 WARN_ON(num_bytes < root->sectorsize);
402 path = btrfs_alloc_path();
403 key.objectid = bytenr;
404 key.offset = num_bytes;
405 btrfs_set_key_type(&key, BTRFS_EXTENT_ITEM_KEY);
406 ret = btrfs_search_slot(trans, root->fs_info->extent_root, &key, path,
407 0, 0);
408 if (ret < 0)
409 goto out;
410 if (ret != 0) {
411 btrfs_print_leaf(root, path->nodes[0]);
412 printk("failed to find block number %Lu\n", bytenr);
413 BUG();
414 }
415 l = path->nodes[0];
416 item = btrfs_item_ptr(l, path->slots[0], struct btrfs_extent_item);
417 *refs = btrfs_extent_refs(l, item);
418 out:
419 btrfs_free_path(path);
420 return 0;
421 }
422
423 int btrfs_inc_root_ref(struct btrfs_trans_handle *trans,
424 struct btrfs_root *root)
425 {
426 return btrfs_inc_extent_ref(trans, root, root->node->start,
427 root->node->len);
428 }
429
430 int btrfs_inc_ref(struct btrfs_trans_handle *trans, struct btrfs_root *root,
431 struct extent_buffer *buf)
432 {
433 u64 bytenr;
434 u32 nritems;
435 struct btrfs_key key;
436 struct btrfs_file_extent_item *fi;
437 int i;
438 int level;
439 int ret;
440 int faili;
441 int err;
442
443 if (!root->ref_cows)
444 return 0;
445
446 level = btrfs_header_level(buf);
447 nritems = btrfs_header_nritems(buf);
448 for (i = 0; i < nritems; i++) {
449 if (level == 0) {
450 u64 disk_bytenr;
451 btrfs_item_key_to_cpu(buf, &key, i);
452 if (btrfs_key_type(&key) != BTRFS_EXTENT_DATA_KEY)
453 continue;
454 fi = btrfs_item_ptr(buf, i,
455 struct btrfs_file_extent_item);
456 if (btrfs_file_extent_type(buf, fi) ==
457 BTRFS_FILE_EXTENT_INLINE)
458 continue;
459 disk_bytenr = btrfs_file_extent_disk_bytenr(buf, fi);
460 if (disk_bytenr == 0)
461 continue;
462 ret = btrfs_inc_extent_ref(trans, root, disk_bytenr,
463 btrfs_file_extent_disk_num_bytes(buf, fi));
464 if (ret) {
465 faili = i;
466 goto fail;
467 }
468 } else {
469 bytenr = btrfs_node_blockptr(buf, i);
470 ret = btrfs_inc_extent_ref(trans, root, bytenr,
471 btrfs_level_size(root, level - 1));
472 if (ret) {
473 faili = i;
474 goto fail;
475 }
476 }
477 }
478 return 0;
479 fail:
480 WARN_ON(1);
481 for (i =0; i < faili; i++) {
482 if (level == 0) {
483 u64 disk_bytenr;
484 btrfs_item_key_to_cpu(buf, &key, i);
485 if (btrfs_key_type(&key) != BTRFS_EXTENT_DATA_KEY)
486 continue;
487 fi = btrfs_item_ptr(buf, i,
488 struct btrfs_file_extent_item);
489 if (btrfs_file_extent_type(buf, fi) ==
490 BTRFS_FILE_EXTENT_INLINE)
491 continue;
492 disk_bytenr = btrfs_file_extent_disk_bytenr(buf, fi);
493 if (disk_bytenr == 0)
494 continue;
495 err = btrfs_free_extent(trans, root, disk_bytenr,
496 btrfs_file_extent_disk_num_bytes(buf,
497 fi), 0);
498 BUG_ON(err);
499 } else {
500 bytenr = btrfs_node_blockptr(buf, i);
501 err = btrfs_free_extent(trans, root, bytenr,
502 btrfs_level_size(root, level - 1), 0);
503 BUG_ON(err);
504 }
505 }
506 return ret;
507 }
508
509 static int write_one_cache_group(struct btrfs_trans_handle *trans,
510 struct btrfs_root *root,
511 struct btrfs_path *path,
512 struct btrfs_block_group_cache *cache)
513 {
514 int ret;
515 int pending_ret;
516 struct btrfs_root *extent_root = root->fs_info->extent_root;
517 unsigned long bi;
518 struct extent_buffer *leaf;
519
520 ret = btrfs_search_slot(trans, extent_root, &cache->key, path, 0, 1);
521 if (ret < 0)
522 goto fail;
523 BUG_ON(ret);
524
525 leaf = path->nodes[0];
526 bi = btrfs_item_ptr_offset(leaf, path->slots[0]);
527 write_extent_buffer(leaf, &cache->item, bi, sizeof(cache->item));
528 btrfs_mark_buffer_dirty(leaf);
529 btrfs_release_path(extent_root, path);
530 fail:
531 finish_current_insert(trans, extent_root);
532 pending_ret = del_pending_extents(trans, extent_root);
533 if (ret)
534 return ret;
535 if (pending_ret)
536 return pending_ret;
537 return 0;
538
539 }
540
541 int btrfs_write_dirty_block_groups(struct btrfs_trans_handle *trans,
542 struct btrfs_root *root)
543 {
544 struct extent_map_tree *block_group_cache;
545 struct btrfs_block_group_cache *cache;
546 int ret;
547 int err = 0;
548 int werr = 0;
549 struct btrfs_path *path;
550 u64 last = 0;
551 u64 start;
552 u64 end;
553 u64 ptr;
554
555 block_group_cache = &root->fs_info->block_group_cache;
556 path = btrfs_alloc_path();
557 if (!path)
558 return -ENOMEM;
559
560 while(1) {
561 ret = find_first_extent_bit(block_group_cache, last,
562 &start, &end, BLOCK_GROUP_DIRTY);
563 if (ret)
564 break;
565
566 last = end + 1;
567 ret = get_state_private(block_group_cache, start, &ptr);
568 if (ret)
569 break;
570
571 cache = (struct btrfs_block_group_cache *)(unsigned long)ptr;
572 err = write_one_cache_group(trans, root,
573 path, cache);
574 /*
575 * if we fail to write the cache group, we want
576 * to keep it marked dirty in hopes that a later
577 * write will work
578 */
579 if (err) {
580 werr = err;
581 continue;
582 }
583 clear_extent_bits(block_group_cache, start, end,
584 BLOCK_GROUP_DIRTY, GFP_NOFS);
585 }
586 btrfs_free_path(path);
587 return werr;
588 }
589
590 static int update_block_group(struct btrfs_trans_handle *trans,
591 struct btrfs_root *root,
592 u64 bytenr, u64 num_bytes, int alloc,
593 int mark_free, int data)
594 {
595 struct btrfs_block_group_cache *cache;
596 struct btrfs_fs_info *info = root->fs_info;
597 u64 total = num_bytes;
598 u64 old_val;
599 u64 byte_in_group;
600 u64 start;
601 u64 end;
602
603 while(total) {
604 cache = btrfs_lookup_block_group(info, bytenr);
605 if (!cache) {
606 return -1;
607 }
608 byte_in_group = bytenr - cache->key.objectid;
609 WARN_ON(byte_in_group > cache->key.offset);
610 start = cache->key.objectid;
611 end = start + cache->key.offset - 1;
612 set_extent_bits(&info->block_group_cache, start, end,
613 BLOCK_GROUP_DIRTY, GFP_NOFS);
614
615 old_val = btrfs_block_group_used(&cache->item);
616 num_bytes = min(total, cache->key.offset - byte_in_group);
617 if (alloc) {
618 if (cache->data != data &&
619 old_val < (cache->key.offset >> 1)) {
620 int bit_to_clear;
621 int bit_to_set;
622 cache->data = data;
623 if (data) {
624 bit_to_clear = BLOCK_GROUP_METADATA;
625 bit_to_set = BLOCK_GROUP_DATA;
626 cache->item.flags &=
627 ~BTRFS_BLOCK_GROUP_MIXED;
628 cache->item.flags |=
629 BTRFS_BLOCK_GROUP_DATA;
630 } else {
631 bit_to_clear = BLOCK_GROUP_DATA;
632 bit_to_set = BLOCK_GROUP_METADATA;
633 cache->item.flags &=
634 ~BTRFS_BLOCK_GROUP_MIXED;
635 cache->item.flags &=
636 ~BTRFS_BLOCK_GROUP_DATA;
637 }
638 clear_extent_bits(&info->block_group_cache,
639 start, end, bit_to_clear,
640 GFP_NOFS);
641 set_extent_bits(&info->block_group_cache,
642 start, end, bit_to_set,
643 GFP_NOFS);
644 } else if (cache->data != data &&
645 cache->data != BTRFS_BLOCK_GROUP_MIXED) {
646 cache->data = BTRFS_BLOCK_GROUP_MIXED;
647 set_extent_bits(&info->block_group_cache,
648 start, end,
649 BLOCK_GROUP_DATA |
650 BLOCK_GROUP_METADATA,
651 GFP_NOFS);
652 }
653 old_val += num_bytes;
654 } else {
655 old_val -= num_bytes;
656 if (mark_free) {
657 set_extent_dirty(&info->free_space_cache,
658 bytenr, bytenr + num_bytes - 1,
659 GFP_NOFS);
660 }
661 }
662 btrfs_set_block_group_used(&cache->item, old_val);
663 total -= num_bytes;
664 bytenr += num_bytes;
665 }
666 return 0;
667 }
668 static int update_pinned_extents(struct btrfs_root *root,
669 u64 bytenr, u64 num, int pin)
670 {
671 u64 len;
672 struct btrfs_block_group_cache *cache;
673 struct btrfs_fs_info *fs_info = root->fs_info;
674
675 if (pin) {
676 set_extent_dirty(&fs_info->pinned_extents,
677 bytenr, bytenr + num - 1, GFP_NOFS);
678 } else {
679 clear_extent_dirty(&fs_info->pinned_extents,
680 bytenr, bytenr + num - 1, GFP_NOFS);
681 }
682 while (num > 0) {
683 cache = btrfs_lookup_block_group(fs_info, bytenr);
684 WARN_ON(!cache);
685 len = min(num, cache->key.offset -
686 (bytenr - cache->key.objectid));
687 if (pin) {
688 cache->pinned += len;
689 fs_info->total_pinned += len;
690 } else {
691 cache->pinned -= len;
692 fs_info->total_pinned -= len;
693 }
694 bytenr += len;
695 num -= len;
696 }
697 return 0;
698 }
699
700 int btrfs_copy_pinned(struct btrfs_root *root, struct extent_map_tree *copy)
701 {
702 u64 last = 0;
703 u64 start;
704 u64 end;
705 struct extent_map_tree *pinned_extents = &root->fs_info->pinned_extents;
706 int ret;
707
708 while(1) {
709 ret = find_first_extent_bit(pinned_extents, last,
710 &start, &end, EXTENT_DIRTY);
711 if (ret)
712 break;
713 set_extent_dirty(copy, start, end, GFP_NOFS);
714 last = end + 1;
715 }
716 return 0;
717 }
718
719 int btrfs_finish_extent_commit(struct btrfs_trans_handle *trans,
720 struct btrfs_root *root,
721 struct extent_map_tree *unpin)
722 {
723 u64 start;
724 u64 end;
725 int ret;
726 struct extent_map_tree *free_space_cache;
727 free_space_cache = &root->fs_info->free_space_cache;
728
729 while(1) {
730 ret = find_first_extent_bit(unpin, 0, &start, &end,
731 EXTENT_DIRTY);
732 if (ret)
733 break;
734 update_pinned_extents(root, start, end + 1 - start, 0);
735 clear_extent_dirty(unpin, start, end, GFP_NOFS);
736 set_extent_dirty(free_space_cache, start, end, GFP_NOFS);
737 }
738 return 0;
739 }
740
741 static int finish_current_insert(struct btrfs_trans_handle *trans, struct
742 btrfs_root *extent_root)
743 {
744 struct btrfs_key ins;
745 struct btrfs_extent_item extent_item;
746 int ret;
747 int err = 0;
748 u64 start;
749 u64 end;
750 struct btrfs_fs_info *info = extent_root->fs_info;
751
752 btrfs_set_stack_extent_refs(&extent_item, 1);
753 btrfs_set_key_type(&ins, BTRFS_EXTENT_ITEM_KEY);
754 btrfs_set_stack_extent_owner(&extent_item,
755 extent_root->root_key.objectid);
756
757 while(1) {
758 ret = find_first_extent_bit(&info->extent_ins, 0, &start,
759 &end, EXTENT_LOCKED);
760 if (ret)
761 break;
762
763 ins.objectid = start;
764 ins.offset = end + 1 - start;
765 err = btrfs_insert_item(trans, extent_root, &ins,
766 &extent_item, sizeof(extent_item));
767 clear_extent_bits(&info->extent_ins, start, end, EXTENT_LOCKED,
768 GFP_NOFS);
769 }
770 return 0;
771 }
772
773 static int pin_down_bytes(struct btrfs_root *root, u64 bytenr, u32 num_bytes,
774 int pending)
775 {
776 int err = 0;
777 struct extent_buffer *buf;
778
779 if (!pending) {
780 buf = btrfs_find_tree_block(root, bytenr, num_bytes);
781 if (buf) {
782 if (btrfs_buffer_uptodate(buf)) {
783 u64 transid =
784 root->fs_info->running_transaction->transid;
785 if (btrfs_header_generation(buf) == transid) {
786 free_extent_buffer(buf);
787 return 1;
788 }
789 }
790 free_extent_buffer(buf);
791 }
792 update_pinned_extents(root, bytenr, num_bytes, 1);
793 } else {
794 set_extent_bits(&root->fs_info->pending_del,
795 bytenr, bytenr + num_bytes - 1,
796 EXTENT_LOCKED, GFP_NOFS);
797 }
798 BUG_ON(err < 0);
799 return 0;
800 }
801
802 /*
803 * remove an extent from the root, returns 0 on success
804 */
805 static int __free_extent(struct btrfs_trans_handle *trans, struct btrfs_root
806 *root, u64 bytenr, u64 num_bytes, int pin,
807 int mark_free)
808 {
809 struct btrfs_path *path;
810 struct btrfs_key key;
811 struct btrfs_fs_info *info = root->fs_info;
812 struct btrfs_root *extent_root = info->extent_root;
813 struct extent_buffer *leaf;
814 int ret;
815 struct btrfs_extent_item *ei;
816 u32 refs;
817
818 key.objectid = bytenr;
819 btrfs_set_key_type(&key, BTRFS_EXTENT_ITEM_KEY);
820 key.offset = num_bytes;
821
822 path = btrfs_alloc_path();
823 if (!path)
824 return -ENOMEM;
825
826 ret = btrfs_search_slot(trans, extent_root, &key, path, -1, 1);
827 if (ret < 0)
828 return ret;
829 BUG_ON(ret);
830
831 leaf = path->nodes[0];
832 ei = btrfs_item_ptr(leaf, path->slots[0],
833 struct btrfs_extent_item);
834 refs = btrfs_extent_refs(leaf, ei);
835 BUG_ON(refs == 0);
836 refs -= 1;
837 btrfs_set_extent_refs(leaf, ei, refs);
838 btrfs_mark_buffer_dirty(leaf);
839
840 if (refs == 0) {
841 u64 super_used;
842 u64 root_used;
843
844 if (pin) {
845 ret = pin_down_bytes(root, bytenr, num_bytes, 0);
846 if (ret > 0)
847 mark_free = 1;
848 BUG_ON(ret < 0);
849 }
850
851 /* block accounting for super block */
852 super_used = btrfs_super_bytes_used(&info->super_copy);
853 btrfs_set_super_bytes_used(&info->super_copy,
854 super_used - num_bytes);
855
856 /* block accounting for root item */
857 root_used = btrfs_root_used(&root->root_item);
858 btrfs_set_root_used(&root->root_item,
859 root_used - num_bytes);
860
861 ret = btrfs_del_item(trans, extent_root, path);
862 if (ret) {
863 return ret;
864 }
865 ret = update_block_group(trans, root, bytenr, num_bytes, 0,
866 mark_free, 0);
867 BUG_ON(ret);
868 }
869 btrfs_free_path(path);
870 finish_current_insert(trans, extent_root);
871 return ret;
872 }
873
874 /*
875 * find all the blocks marked as pending in the radix tree and remove
876 * them from the extent map
877 */
878 static int del_pending_extents(struct btrfs_trans_handle *trans, struct
879 btrfs_root *extent_root)
880 {
881 int ret;
882 int err = 0;
883 u64 start;
884 u64 end;
885 struct extent_map_tree *pending_del;
886 struct extent_map_tree *pinned_extents;
887
888 pending_del = &extent_root->fs_info->pending_del;
889 pinned_extents = &extent_root->fs_info->pinned_extents;
890
891 while(1) {
892 ret = find_first_extent_bit(pending_del, 0, &start, &end,
893 EXTENT_LOCKED);
894 if (ret)
895 break;
896 update_pinned_extents(extent_root, start, end + 1 - start, 1);
897 clear_extent_bits(pending_del, start, end, EXTENT_LOCKED,
898 GFP_NOFS);
899 ret = __free_extent(trans, extent_root,
900 start, end + 1 - start, 0, 0);
901 if (ret)
902 err = ret;
903 }
904 return err;
905 }
906
907 /*
908 * remove an extent from the root, returns 0 on success
909 */
910 int btrfs_free_extent(struct btrfs_trans_handle *trans, struct btrfs_root
911 *root, u64 bytenr, u64 num_bytes, int pin)
912 {
913 struct btrfs_root *extent_root = root->fs_info->extent_root;
914 int pending_ret;
915 int ret;
916
917 WARN_ON(num_bytes < root->sectorsize);
918 if (root == extent_root) {
919 pin_down_bytes(root, bytenr, num_bytes, 1);
920 return 0;
921 }
922 ret = __free_extent(trans, root, bytenr, num_bytes, pin, pin == 0);
923 pending_ret = del_pending_extents(trans, root->fs_info->extent_root);
924 return ret ? ret : pending_ret;
925 }
926
927 /*
928 * walks the btree of allocated extents and find a hole of a given size.
929 * The key ins is changed to record the hole:
930 * ins->objectid == block start
931 * ins->flags = BTRFS_EXTENT_ITEM_KEY
932 * ins->offset == number of blocks
933 * Any available blocks before search_start are skipped.
934 */
935 static int find_free_extent(struct btrfs_trans_handle *trans, struct btrfs_root
936 *orig_root, u64 num_bytes, u64 empty_size,
937 u64 search_start, u64 search_end, u64 hint_byte,
938 struct btrfs_key *ins, u64 exclude_start,
939 u64 exclude_nr, int data)
940 {
941 struct btrfs_path *path;
942 struct btrfs_key key;
943 int ret;
944 u64 hole_size = 0;
945 int slot = 0;
946 u64 last_byte = 0;
947 u64 orig_search_start = search_start;
948 int start_found;
949 struct extent_buffer *l;
950 struct btrfs_root * root = orig_root->fs_info->extent_root;
951 struct btrfs_fs_info *info = root->fs_info;
952 u64 total_needed = num_bytes;
953 int level;
954 struct btrfs_block_group_cache *block_group;
955 int full_scan = 0;
956 int wrapped = 0;
957 u64 cached_start;
958
959 WARN_ON(num_bytes < root->sectorsize);
960 btrfs_set_key_type(ins, BTRFS_EXTENT_ITEM_KEY);
961
962 level = btrfs_header_level(root->node);
963
964 if (num_bytes >= 32 * 1024 * 1024 && hint_byte) {
965 data = BTRFS_BLOCK_GROUP_MIXED;
966 }
967
968 if (search_end == (u64)-1)
969 search_end = btrfs_super_total_bytes(&info->super_copy);
970 if (hint_byte) {
971 block_group = btrfs_lookup_block_group(info, hint_byte);
972 block_group = btrfs_find_block_group(root, block_group,
973 hint_byte, data, 1);
974 } else {
975 block_group = btrfs_find_block_group(root,
976 trans->block_group, 0,
977 data, 1);
978 }
979
980 total_needed += empty_size;
981 path = btrfs_alloc_path();
982 check_failed:
983 search_start = find_search_start(root, &block_group, search_start,
984 total_needed, data, full_scan);
985 cached_start = search_start;
986 btrfs_init_path(path);
987 ins->objectid = search_start;
988 ins->offset = 0;
989 start_found = 0;
990 path->reada = 2;
991
992 ret = btrfs_search_slot(trans, root, ins, path, 0, 0);
993 if (ret < 0)
994 goto error;
995
996 if (path->slots[0] > 0) {
997 path->slots[0]--;
998 }
999
1000 l = path->nodes[0];
1001 btrfs_item_key_to_cpu(l, &key, path->slots[0]);
1002
1003 /*
1004 * a rare case, go back one key if we hit a block group item
1005 * instead of an extent item
1006 */
1007 if (btrfs_key_type(&key) != BTRFS_EXTENT_ITEM_KEY &&
1008 key.objectid + key.offset >= search_start) {
1009 ins->objectid = key.objectid;
1010 ins->offset = key.offset - 1;
1011 btrfs_release_path(root, path);
1012 ret = btrfs_search_slot(trans, root, ins, path, 0, 0);
1013 if (ret < 0)
1014 goto error;
1015
1016 if (path->slots[0] > 0) {
1017 path->slots[0]--;
1018 }
1019 }
1020
1021 while (1) {
1022 l = path->nodes[0];
1023 slot = path->slots[0];
1024 if (slot >= btrfs_header_nritems(l)) {
1025 ret = btrfs_next_leaf(root, path);
1026 if (ret == 0)
1027 continue;
1028 if (ret < 0)
1029 goto error;
1030
1031 search_start = max(search_start,
1032 block_group->key.objectid);
1033 if (!start_found) {
1034 ins->objectid = search_start;
1035 ins->offset = search_end - search_start;
1036 start_found = 1;
1037 goto check_pending;
1038 }
1039 ins->objectid = last_byte > search_start ?
1040 last_byte : search_start;
1041 ins->offset = search_end - ins->objectid;
1042 BUG_ON(ins->objectid >= search_end);
1043 goto check_pending;
1044 }
1045 btrfs_item_key_to_cpu(l, &key, slot);
1046
1047 if (key.objectid >= search_start && key.objectid > last_byte &&
1048 start_found) {
1049 if (last_byte < search_start)
1050 last_byte = search_start;
1051 hole_size = key.objectid - last_byte;
1052 if (hole_size >= num_bytes) {
1053 ins->objectid = last_byte;
1054 ins->offset = hole_size;
1055 goto check_pending;
1056 }
1057 }
1058 if (btrfs_key_type(&key) != BTRFS_EXTENT_ITEM_KEY) {
1059 if (!start_found) {
1060 last_byte = key.objectid;
1061 start_found = 1;
1062 }
1063 goto next;
1064 }
1065
1066
1067 start_found = 1;
1068 last_byte = key.objectid + key.offset;
1069
1070 if (!full_scan && data != BTRFS_BLOCK_GROUP_MIXED &&
1071 last_byte >= block_group->key.objectid +
1072 block_group->key.offset) {
1073 btrfs_release_path(root, path);
1074 search_start = block_group->key.objectid +
1075 block_group->key.offset;
1076 goto new_group;
1077 }
1078 next:
1079 path->slots[0]++;
1080 cond_resched();
1081 }
1082 check_pending:
1083 /* we have to make sure we didn't find an extent that has already
1084 * been allocated by the map tree or the original allocation
1085 */
1086 btrfs_release_path(root, path);
1087 BUG_ON(ins->objectid < search_start);
1088
1089 if (ins->objectid + num_bytes >= search_end)
1090 goto enospc;
1091 if (!full_scan && data != BTRFS_BLOCK_GROUP_MIXED &&
1092 ins->objectid + num_bytes > block_group->
1093 key.objectid + block_group->key.offset) {
1094 search_start = block_group->key.objectid +
1095 block_group->key.offset;
1096 goto new_group;
1097 }
1098 if (test_range_bit(&info->extent_ins, ins->objectid,
1099 ins->objectid + num_bytes -1, EXTENT_LOCKED, 0)) {
1100 search_start = ins->objectid + num_bytes;
1101 goto new_group;
1102 }
1103 if (test_range_bit(&info->pinned_extents, ins->objectid,
1104 ins->objectid + num_bytes -1, EXTENT_DIRTY, 0)) {
1105 search_start = ins->objectid + num_bytes;
1106 goto new_group;
1107 }
1108 if (exclude_nr > 0 && (ins->objectid + num_bytes > exclude_start &&
1109 ins->objectid < exclude_start + exclude_nr)) {
1110 search_start = exclude_start + exclude_nr;
1111 goto new_group;
1112 }
1113 if (!data) {
1114 block_group = btrfs_lookup_block_group(info, ins->objectid);
1115 if (block_group)
1116 trans->block_group = block_group;
1117 }
1118 ins->offset = num_bytes;
1119 btrfs_free_path(path);
1120 return 0;
1121
1122 new_group:
1123 if (search_start + num_bytes >= search_end) {
1124 enospc:
1125 search_start = orig_search_start;
1126 if (full_scan) {
1127 ret = -ENOSPC;
1128 goto error;
1129 }
1130 if (wrapped) {
1131 if (!full_scan)
1132 total_needed -= empty_size;
1133 full_scan = 1;
1134 } else
1135 wrapped = 1;
1136 }
1137 block_group = btrfs_lookup_block_group(info, search_start);
1138 cond_resched();
1139 if (!full_scan)
1140 block_group = btrfs_find_block_group(root, block_group,
1141 search_start, data, 0);
1142 goto check_failed;
1143
1144 error:
1145 btrfs_release_path(root, path);
1146 btrfs_free_path(path);
1147 return ret;
1148 }
1149 /*
1150 * finds a free extent and does all the dirty work required for allocation
1151 * returns the key for the extent through ins, and a tree buffer for
1152 * the first block of the extent through buf.
1153 *
1154 * returns 0 if everything worked, non-zero otherwise.
1155 */
1156 int btrfs_alloc_extent(struct btrfs_trans_handle *trans,
1157 struct btrfs_root *root, u64 owner,
1158 u64 num_bytes, u64 empty_size, u64 hint_byte,
1159 u64 search_end, struct btrfs_key *ins, int data)
1160 {
1161 int ret;
1162 int pending_ret;
1163 u64 super_used, root_used;
1164 u64 search_start = 0;
1165 struct btrfs_fs_info *info = root->fs_info;
1166 struct btrfs_root *extent_root = info->extent_root;
1167 struct btrfs_extent_item extent_item;
1168
1169 btrfs_set_stack_extent_refs(&extent_item, 1);
1170 btrfs_set_stack_extent_owner(&extent_item, owner);
1171
1172 WARN_ON(num_bytes < root->sectorsize);
1173 ret = find_free_extent(trans, root, num_bytes, empty_size,
1174 search_start, search_end, hint_byte, ins,
1175 trans->alloc_exclude_start,
1176 trans->alloc_exclude_nr, data);
1177 BUG_ON(ret);
1178 if (ret)
1179 return ret;
1180
1181 /* block accounting for super block */
1182 super_used = btrfs_super_bytes_used(&info->super_copy);
1183 btrfs_set_super_bytes_used(&info->super_copy, super_used + num_bytes);
1184
1185 /* block accounting for root item */
1186 root_used = btrfs_root_used(&root->root_item);
1187 btrfs_set_root_used(&root->root_item, root_used + num_bytes);
1188
1189 clear_extent_dirty(&root->fs_info->free_space_cache,
1190 ins->objectid, ins->objectid + ins->offset - 1,
1191 GFP_NOFS);
1192
1193 if (root == extent_root) {
1194 set_extent_bits(&root->fs_info->extent_ins, ins->objectid,
1195 ins->objectid + ins->offset - 1,
1196 EXTENT_LOCKED, GFP_NOFS);
1197 WARN_ON(data == 1);
1198 goto update_block;
1199 }
1200
1201 WARN_ON(trans->alloc_exclude_nr);
1202 trans->alloc_exclude_start = ins->objectid;
1203 trans->alloc_exclude_nr = ins->offset;
1204 ret = btrfs_insert_item(trans, extent_root, ins, &extent_item,
1205 sizeof(extent_item));
1206
1207 trans->alloc_exclude_start = 0;
1208 trans->alloc_exclude_nr = 0;
1209
1210 BUG_ON(ret);
1211 finish_current_insert(trans, extent_root);
1212 pending_ret = del_pending_extents(trans, extent_root);
1213
1214 if (ret) {
1215 return ret;
1216 }
1217 if (pending_ret) {
1218 return pending_ret;
1219 }
1220
1221 update_block:
1222 ret = update_block_group(trans, root, ins->objectid, ins->offset, 1, 0,
1223 data);
1224 BUG_ON(ret);
1225 return 0;
1226 }
1227
1228 /*
1229 * helper function to allocate a block for a given tree
1230 * returns the tree buffer or NULL.
1231 */
1232 struct extent_buffer *btrfs_alloc_free_block(struct btrfs_trans_handle *trans,
1233 struct btrfs_root *root,
1234 u32 blocksize, u64 hint,
1235 u64 empty_size)
1236 {
1237 struct btrfs_key ins;
1238 int ret;
1239 struct extent_buffer *buf;
1240
1241 ret = btrfs_alloc_extent(trans, root, root->root_key.objectid,
1242 blocksize, empty_size, hint,
1243 (u64)-1, &ins, 0);
1244 if (ret) {
1245 BUG_ON(ret > 0);
1246 return ERR_PTR(ret);
1247 }
1248 buf = btrfs_find_create_tree_block(root, ins.objectid, blocksize);
1249 if (!buf) {
1250 btrfs_free_extent(trans, root, ins.objectid, blocksize, 0);
1251 return ERR_PTR(-ENOMEM);
1252 }
1253 btrfs_set_buffer_uptodate(buf);
1254 set_extent_dirty(&trans->transaction->dirty_pages, buf->start,
1255 buf->start + buf->len - 1, GFP_NOFS);
1256 set_extent_bits(&BTRFS_I(root->fs_info->btree_inode)->extent_tree,
1257 buf->start, buf->start + buf->len - 1,
1258 EXTENT_CSUM, GFP_NOFS);
1259 buf->flags |= EXTENT_CSUM;
1260 btrfs_set_buffer_defrag(buf);
1261 trans->blocks_used++;
1262 return buf;
1263 }
1264
1265 static int drop_leaf_ref(struct btrfs_trans_handle *trans,
1266 struct btrfs_root *root, struct extent_buffer *leaf)
1267 {
1268 struct btrfs_key key;
1269 struct btrfs_file_extent_item *fi;
1270 int i;
1271 int nritems;
1272 int ret;
1273
1274 BUG_ON(!btrfs_is_leaf(leaf));
1275 nritems = btrfs_header_nritems(leaf);
1276 for (i = 0; i < nritems; i++) {
1277 u64 disk_bytenr;
1278
1279 btrfs_item_key_to_cpu(leaf, &key, i);
1280 if (btrfs_key_type(&key) != BTRFS_EXTENT_DATA_KEY)
1281 continue;
1282 fi = btrfs_item_ptr(leaf, i, struct btrfs_file_extent_item);
1283 if (btrfs_file_extent_type(leaf, fi) ==
1284 BTRFS_FILE_EXTENT_INLINE)
1285 continue;
1286 /*
1287 * FIXME make sure to insert a trans record that
1288 * repeats the snapshot del on crash
1289 */
1290 disk_bytenr = btrfs_file_extent_disk_bytenr(leaf, fi);
1291 if (disk_bytenr == 0)
1292 continue;
1293 ret = btrfs_free_extent(trans, root, disk_bytenr,
1294 btrfs_file_extent_disk_num_bytes(leaf, fi), 0);
1295 BUG_ON(ret);
1296 }
1297 return 0;
1298 }
1299
1300 static void reada_walk_down(struct btrfs_root *root,
1301 struct extent_buffer *node)
1302 {
1303 int i;
1304 u32 nritems;
1305 u64 bytenr;
1306 int ret;
1307 u32 refs;
1308 int level;
1309 u32 blocksize;
1310
1311 nritems = btrfs_header_nritems(node);
1312 level = btrfs_header_level(node);
1313 for (i = 0; i < nritems; i++) {
1314 bytenr = btrfs_node_blockptr(node, i);
1315 blocksize = btrfs_level_size(root, level - 1);
1316 ret = lookup_extent_ref(NULL, root, bytenr, blocksize, &refs);
1317 BUG_ON(ret);
1318 if (refs != 1)
1319 continue;
1320 mutex_unlock(&root->fs_info->fs_mutex);
1321 ret = readahead_tree_block(root, bytenr, blocksize);
1322 cond_resched();
1323 mutex_lock(&root->fs_info->fs_mutex);
1324 if (ret)
1325 break;
1326 }
1327 }
1328
1329 /*
1330 * helper function for drop_snapshot, this walks down the tree dropping ref
1331 * counts as it goes.
1332 */
1333 static int walk_down_tree(struct btrfs_trans_handle *trans, struct btrfs_root
1334 *root, struct btrfs_path *path, int *level)
1335 {
1336 struct extent_buffer *next;
1337 struct extent_buffer *cur;
1338 u64 bytenr;
1339 u32 blocksize;
1340 int ret;
1341 u32 refs;
1342
1343 WARN_ON(*level < 0);
1344 WARN_ON(*level >= BTRFS_MAX_LEVEL);
1345 ret = lookup_extent_ref(trans, root,
1346 path->nodes[*level]->start,
1347 path->nodes[*level]->len, &refs);
1348 BUG_ON(ret);
1349 if (refs > 1)
1350 goto out;
1351
1352 /*
1353 * walk down to the last node level and free all the leaves
1354 */
1355 while(*level >= 0) {
1356 WARN_ON(*level < 0);
1357 WARN_ON(*level >= BTRFS_MAX_LEVEL);
1358 cur = path->nodes[*level];
1359
1360 if (*level > 0 && path->slots[*level] == 0)
1361 reada_walk_down(root, cur);
1362
1363 if (btrfs_header_level(cur) != *level)
1364 WARN_ON(1);
1365
1366 if (path->slots[*level] >=
1367 btrfs_header_nritems(cur))
1368 break;
1369 if (*level == 0) {
1370 ret = drop_leaf_ref(trans, root, cur);
1371 BUG_ON(ret);
1372 break;
1373 }
1374 bytenr = btrfs_node_blockptr(cur, path->slots[*level]);
1375 blocksize = btrfs_level_size(root, *level - 1);
1376 ret = lookup_extent_ref(trans, root, bytenr, blocksize, &refs);
1377 BUG_ON(ret);
1378 if (refs != 1) {
1379 path->slots[*level]++;
1380 ret = btrfs_free_extent(trans, root, bytenr,
1381 blocksize, 1);
1382 BUG_ON(ret);
1383 continue;
1384 }
1385 next = btrfs_find_tree_block(root, bytenr, blocksize);
1386 if (!next || !btrfs_buffer_uptodate(next)) {
1387 free_extent_buffer(next);
1388 mutex_unlock(&root->fs_info->fs_mutex);
1389 next = read_tree_block(root, bytenr, blocksize);
1390 mutex_lock(&root->fs_info->fs_mutex);
1391
1392 /* we dropped the lock, check one more time */
1393 ret = lookup_extent_ref(trans, root, bytenr,
1394 blocksize, &refs);
1395 BUG_ON(ret);
1396 if (refs != 1) {
1397 path->slots[*level]++;
1398 free_extent_buffer(next);
1399 ret = btrfs_free_extent(trans, root,
1400 bytenr, blocksize, 1);
1401 BUG_ON(ret);
1402 continue;
1403 }
1404 }
1405 WARN_ON(*level <= 0);
1406 if (path->nodes[*level-1])
1407 free_extent_buffer(path->nodes[*level-1]);
1408 path->nodes[*level-1] = next;
1409 *level = btrfs_header_level(next);
1410 path->slots[*level] = 0;
1411 }
1412 out:
1413 WARN_ON(*level < 0);
1414 WARN_ON(*level >= BTRFS_MAX_LEVEL);
1415 ret = btrfs_free_extent(trans, root, path->nodes[*level]->start,
1416 path->nodes[*level]->len, 1);
1417 free_extent_buffer(path->nodes[*level]);
1418 path->nodes[*level] = NULL;
1419 *level += 1;
1420 BUG_ON(ret);
1421 return 0;
1422 }
1423
1424 /*
1425 * helper for dropping snapshots. This walks back up the tree in the path
1426 * to find the first node higher up where we haven't yet gone through
1427 * all the slots
1428 */
1429 static int walk_up_tree(struct btrfs_trans_handle *trans, struct btrfs_root
1430 *root, struct btrfs_path *path, int *level)
1431 {
1432 int i;
1433 int slot;
1434 int ret;
1435 struct btrfs_root_item *root_item = &root->root_item;
1436
1437 for(i = *level; i < BTRFS_MAX_LEVEL - 1 && path->nodes[i]; i++) {
1438 slot = path->slots[i];
1439 if (slot < btrfs_header_nritems(path->nodes[i]) - 1) {
1440 struct extent_buffer *node;
1441 struct btrfs_disk_key disk_key;
1442 node = path->nodes[i];
1443 path->slots[i]++;
1444 *level = i;
1445 WARN_ON(*level == 0);
1446 btrfs_node_key(node, &disk_key, path->slots[i]);
1447 memcpy(&root_item->drop_progress,
1448 &disk_key, sizeof(disk_key));
1449 root_item->drop_level = i;
1450 return 0;
1451 } else {
1452 ret = btrfs_free_extent(trans, root,
1453 path->nodes[*level]->start,
1454 path->nodes[*level]->len, 1);
1455 BUG_ON(ret);
1456 free_extent_buffer(path->nodes[*level]);
1457 path->nodes[*level] = NULL;
1458 *level = i + 1;
1459 }
1460 }
1461 return 1;
1462 }
1463
1464 /*
1465 * drop the reference count on the tree rooted at 'snap'. This traverses
1466 * the tree freeing any blocks that have a ref count of zero after being
1467 * decremented.
1468 */
1469 int btrfs_drop_snapshot(struct btrfs_trans_handle *trans, struct btrfs_root
1470 *root)
1471 {
1472 int ret = 0;
1473 int wret;
1474 int level;
1475 struct btrfs_path *path;
1476 int i;
1477 int orig_level;
1478 struct btrfs_root_item *root_item = &root->root_item;
1479
1480 path = btrfs_alloc_path();
1481 BUG_ON(!path);
1482
1483 level = btrfs_header_level(root->node);
1484 orig_level = level;
1485 if (btrfs_disk_key_objectid(&root_item->drop_progress) == 0) {
1486 path->nodes[level] = root->node;
1487 extent_buffer_get(root->node);
1488 path->slots[level] = 0;
1489 } else {
1490 struct btrfs_key key;
1491 struct btrfs_disk_key found_key;
1492 struct extent_buffer *node;
1493
1494 btrfs_disk_key_to_cpu(&key, &root_item->drop_progress);
1495 level = root_item->drop_level;
1496 path->lowest_level = level;
1497 wret = btrfs_search_slot(NULL, root, &key, path, 0, 0);
1498 if (wret < 0) {
1499 ret = wret;
1500 goto out;
1501 }
1502 node = path->nodes[level];
1503 btrfs_node_key(node, &found_key, path->slots[level]);
1504 WARN_ON(memcmp(&found_key, &root_item->drop_progress,
1505 sizeof(found_key)));
1506 }
1507 while(1) {
1508 wret = walk_down_tree(trans, root, path, &level);
1509 if (wret > 0)
1510 break;
1511 if (wret < 0)
1512 ret = wret;
1513
1514 wret = walk_up_tree(trans, root, path, &level);
1515 if (wret > 0)
1516 break;
1517 if (wret < 0)
1518 ret = wret;
1519 ret = -EAGAIN;
1520 break;
1521 }
1522 for (i = 0; i <= orig_level; i++) {
1523 if (path->nodes[i]) {
1524 free_extent_buffer(path->nodes[i]);
1525 path->nodes[i] = NULL;
1526 }
1527 }
1528 out:
1529 btrfs_free_path(path);
1530 return ret;
1531 }
1532
1533 int btrfs_free_block_groups(struct btrfs_fs_info *info)
1534 {
1535 u64 start;
1536 u64 end;
1537 u64 ptr;
1538 int ret;
1539 while(1) {
1540 ret = find_first_extent_bit(&info->block_group_cache, 0,
1541 &start, &end, (unsigned int)-1);
1542 if (ret)
1543 break;
1544 ret = get_state_private(&info->block_group_cache, start, &ptr);
1545 if (!ret)
1546 kfree((void *)(unsigned long)ptr);
1547 clear_extent_bits(&info->block_group_cache, start,
1548 end, (unsigned int)-1, GFP_NOFS);
1549 }
1550 while(1) {
1551 ret = find_first_extent_bit(&info->free_space_cache, 0,
1552 &start, &end, EXTENT_DIRTY);
1553 if (ret)
1554 break;
1555 clear_extent_dirty(&info->free_space_cache, start,
1556 end, GFP_NOFS);
1557 }
1558 return 0;
1559 }
1560
1561 int btrfs_read_block_groups(struct btrfs_root *root)
1562 {
1563 struct btrfs_path *path;
1564 int ret;
1565 int err = 0;
1566 int bit;
1567 struct btrfs_block_group_cache *cache;
1568 struct btrfs_fs_info *info = root->fs_info;
1569 struct extent_map_tree *block_group_cache;
1570 struct btrfs_key key;
1571 struct btrfs_key found_key;
1572 struct extent_buffer *leaf;
1573
1574 block_group_cache = &info->block_group_cache;
1575
1576 root = info->extent_root;
1577 key.objectid = 0;
1578 key.offset = BTRFS_BLOCK_GROUP_SIZE;
1579 btrfs_set_key_type(&key, BTRFS_BLOCK_GROUP_ITEM_KEY);
1580
1581 path = btrfs_alloc_path();
1582 if (!path)
1583 return -ENOMEM;
1584
1585 while(1) {
1586 ret = btrfs_search_slot(NULL, info->extent_root,
1587 &key, path, 0, 0);
1588 if (ret != 0) {
1589 err = ret;
1590 break;
1591 }
1592 leaf = path->nodes[0];
1593 btrfs_item_key_to_cpu(leaf, &found_key, path->slots[0]);
1594 cache = kmalloc(sizeof(*cache), GFP_NOFS);
1595 if (!cache) {
1596 err = -1;
1597 break;
1598 }
1599
1600 read_extent_buffer(leaf, &cache->item,
1601 btrfs_item_ptr_offset(leaf, path->slots[0]),
1602 sizeof(cache->item));
1603 memcpy(&cache->key, &found_key, sizeof(found_key));
1604 cache->cached = 0;
1605 cache->pinned = 0;
1606 key.objectid = found_key.objectid + found_key.offset;
1607 btrfs_release_path(root, path);
1608
1609 if (cache->item.flags & BTRFS_BLOCK_GROUP_MIXED) {
1610 bit = BLOCK_GROUP_DATA | BLOCK_GROUP_METADATA;
1611 cache->data = BTRFS_BLOCK_GROUP_MIXED;
1612 } else if (cache->item.flags & BTRFS_BLOCK_GROUP_DATA) {
1613 bit = BLOCK_GROUP_DATA;
1614 cache->data = BTRFS_BLOCK_GROUP_DATA;
1615 } else {
1616 bit = BLOCK_GROUP_METADATA;
1617 cache->data = 0;
1618 }
1619
1620 /* use EXTENT_LOCKED to prevent merging */
1621 set_extent_bits(block_group_cache, found_key.objectid,
1622 found_key.objectid + found_key.offset - 1,
1623 bit | EXTENT_LOCKED, GFP_NOFS);
1624 set_state_private(block_group_cache, found_key.objectid,
1625 (unsigned long)cache);
1626
1627 if (key.objectid >=
1628 btrfs_super_total_bytes(&info->super_copy))
1629 break;
1630 }
1631
1632 btrfs_free_path(path);
1633 return 0;
1634 }
Linux kernel - Deliverables
This page took 0.095323 seconds and 6 git commands to generate.