Btrfs progs v4.17.1
[btrfs-progs-unstable/devel.git] / free-space-cache.c
blob2ef2d307cc5d7d4387330eba3e43653741a4fe15
1 /*
2 * Copyright (C) 2008 Red Hat. All rights reserved.
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.
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.
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.
19 #include "kerncompat.h"
20 #include "ctree.h"
21 #include "free-space-cache.h"
22 #include "transaction.h"
23 #include "disk-io.h"
24 #include "extent_io.h"
25 #include "crc32c.h"
26 #include "bitops.h"
27 #include "internal.h"
28 #include "utils.h"
31 * Kernel always uses PAGE_CACHE_SIZE for sectorsize, but we don't have
32 * anything like that in userspace and have to get the value from the
33 * filesystem
35 #define BITS_PER_BITMAP(sectorsize) ((sectorsize) * 8)
36 #define MAX_CACHE_BYTES_PER_GIG SZ_32K
38 static int link_free_space(struct btrfs_free_space_ctl *ctl,
39 struct btrfs_free_space *info);
40 static void merge_space_tree(struct btrfs_free_space_ctl *ctl);
42 struct io_ctl {
43 void *cur, *orig;
44 void *buffer;
45 struct btrfs_root *root;
46 unsigned long size;
47 u64 total_size;
48 int index;
49 int num_pages;
50 unsigned check_crcs:1;
53 static int io_ctl_init(struct io_ctl *io_ctl, u64 size, u64 ino,
54 struct btrfs_root *root)
56 memset(io_ctl, 0, sizeof(struct io_ctl));
57 io_ctl->num_pages = DIV_ROUND_UP(size, root->fs_info->sectorsize);
58 io_ctl->buffer = kzalloc(size, GFP_NOFS);
59 if (!io_ctl->buffer)
60 return -ENOMEM;
61 io_ctl->total_size = size;
62 io_ctl->root = root;
63 if (ino != BTRFS_FREE_INO_OBJECTID)
64 io_ctl->check_crcs = 1;
65 return 0;
68 static void io_ctl_free(struct io_ctl *io_ctl)
70 kfree(io_ctl->buffer);
73 static void io_ctl_unmap_page(struct io_ctl *io_ctl)
75 if (io_ctl->cur) {
76 io_ctl->cur = NULL;
77 io_ctl->orig = NULL;
81 static void io_ctl_map_page(struct io_ctl *io_ctl, int clear)
83 BUG_ON(io_ctl->index >= io_ctl->num_pages);
84 io_ctl->cur = io_ctl->buffer + (io_ctl->index++ *
85 io_ctl->root->fs_info->sectorsize);
86 io_ctl->orig = io_ctl->cur;
87 io_ctl->size = io_ctl->root->fs_info->sectorsize;
88 if (clear)
89 memset(io_ctl->cur, 0, io_ctl->root->fs_info->sectorsize);
92 static void io_ctl_drop_pages(struct io_ctl *io_ctl)
94 io_ctl_unmap_page(io_ctl);
97 static int io_ctl_prepare_pages(struct io_ctl *io_ctl, struct btrfs_root *root,
98 struct btrfs_path *path, u64 ino)
100 struct extent_buffer *leaf;
101 struct btrfs_file_extent_item *fi;
102 struct btrfs_key key;
103 u64 bytenr, len;
104 u64 total_read = 0;
105 int ret = 0;
107 key.objectid = ino;
108 key.type = BTRFS_EXTENT_DATA_KEY;
109 key.offset = 0;
111 ret = btrfs_search_slot(NULL, root, &key, path, 0, 0);
112 if (ret) {
113 fprintf(stderr,
114 "Couldn't find file extent item for free space inode"
115 " %Lu\n", ino);
116 btrfs_release_path(path);
117 return -EINVAL;
120 while (total_read < io_ctl->total_size) {
121 if (path->slots[0] >= btrfs_header_nritems(path->nodes[0])) {
122 ret = btrfs_next_leaf(root, path);
123 if (ret) {
124 ret = -EINVAL;
125 break;
128 leaf = path->nodes[0];
130 btrfs_item_key_to_cpu(leaf, &key, path->slots[0]);
131 if (key.objectid != ino) {
132 ret = -EINVAL;
133 break;
136 if (key.type != BTRFS_EXTENT_DATA_KEY) {
137 ret = -EINVAL;
138 break;
141 fi = btrfs_item_ptr(path->nodes[0], path->slots[0],
142 struct btrfs_file_extent_item);
143 if (btrfs_file_extent_type(path->nodes[0], fi) !=
144 BTRFS_FILE_EXTENT_REG) {
145 fprintf(stderr, "Not the file extent type we wanted\n");
146 ret = -EINVAL;
147 break;
150 bytenr = btrfs_file_extent_disk_bytenr(leaf, fi) +
151 btrfs_file_extent_offset(leaf, fi);
152 len = btrfs_file_extent_num_bytes(leaf, fi);
153 ret = read_data_from_disk(root->fs_info,
154 io_ctl->buffer + key.offset, bytenr,
155 len, 0);
156 if (ret)
157 break;
158 total_read += len;
159 path->slots[0]++;
162 btrfs_release_path(path);
163 return ret;
166 static int io_ctl_check_generation(struct io_ctl *io_ctl, u64 generation)
168 __le64 *gen;
171 * Skip the crc area. If we don't check crcs then we just have a 64bit
172 * chunk at the front of the first page.
174 if (io_ctl->check_crcs) {
175 io_ctl->cur += sizeof(u32) * io_ctl->num_pages;
176 io_ctl->size -= sizeof(u64) +
177 (sizeof(u32) * io_ctl->num_pages);
178 } else {
179 io_ctl->cur += sizeof(u64);
180 io_ctl->size -= sizeof(u64) * 2;
183 gen = io_ctl->cur;
184 if (le64_to_cpu(*gen) != generation) {
185 printk("btrfs: space cache generation "
186 "(%Lu) does not match inode (%Lu)\n", *gen,
187 generation);
188 io_ctl_unmap_page(io_ctl);
189 return -EIO;
191 io_ctl->cur += sizeof(u64);
192 return 0;
195 static int io_ctl_check_crc(struct io_ctl *io_ctl, int index)
197 u32 *tmp, val;
198 u32 crc = ~(u32)0;
199 unsigned offset = 0;
201 if (!io_ctl->check_crcs) {
202 io_ctl_map_page(io_ctl, 0);
203 return 0;
206 if (index == 0)
207 offset = sizeof(u32) * io_ctl->num_pages;
209 tmp = io_ctl->buffer;
210 tmp += index;
211 val = *tmp;
213 io_ctl_map_page(io_ctl, 0);
214 crc = crc32c(crc, io_ctl->orig + offset,
215 io_ctl->root->fs_info->sectorsize - offset);
216 btrfs_csum_final(crc, (u8 *)&crc);
217 if (val != crc) {
218 printk("btrfs: csum mismatch on free space cache\n");
219 io_ctl_unmap_page(io_ctl);
220 return -EIO;
223 return 0;
226 static int io_ctl_read_entry(struct io_ctl *io_ctl,
227 struct btrfs_free_space *entry, u8 *type)
229 struct btrfs_free_space_entry *e;
230 int ret;
232 if (!io_ctl->cur) {
233 ret = io_ctl_check_crc(io_ctl, io_ctl->index);
234 if (ret)
235 return ret;
238 e = io_ctl->cur;
239 entry->offset = le64_to_cpu(e->offset);
240 entry->bytes = le64_to_cpu(e->bytes);
241 *type = e->type;
242 io_ctl->cur += sizeof(struct btrfs_free_space_entry);
243 io_ctl->size -= sizeof(struct btrfs_free_space_entry);
245 if (io_ctl->size >= sizeof(struct btrfs_free_space_entry))
246 return 0;
248 io_ctl_unmap_page(io_ctl);
250 return 0;
253 static int io_ctl_read_bitmap(struct io_ctl *io_ctl,
254 struct btrfs_free_space *entry)
256 int ret;
258 ret = io_ctl_check_crc(io_ctl, io_ctl->index);
259 if (ret)
260 return ret;
262 memcpy(entry->bitmap, io_ctl->cur, io_ctl->root->fs_info->sectorsize);
263 io_ctl_unmap_page(io_ctl);
265 return 0;
269 static int __load_free_space_cache(struct btrfs_root *root,
270 struct btrfs_free_space_ctl *ctl,
271 struct btrfs_path *path, u64 offset)
273 struct btrfs_free_space_header *header;
274 struct btrfs_inode_item *inode_item;
275 struct extent_buffer *leaf;
276 struct io_ctl io_ctl;
277 struct btrfs_key key;
278 struct btrfs_key inode_location;
279 struct btrfs_disk_key disk_key;
280 struct btrfs_free_space *e, *n;
281 struct list_head bitmaps;
282 u64 num_entries;
283 u64 num_bitmaps;
284 u64 generation;
285 u64 inode_size;
286 u8 type;
287 int ret = 0;
289 INIT_LIST_HEAD(&bitmaps);
291 key.objectid = BTRFS_FREE_SPACE_OBJECTID;
292 key.offset = offset;
293 key.type = 0;
295 ret = btrfs_search_slot(NULL, root, &key, path, 0, 0);
296 if (ret < 0) {
297 return 0;
298 } else if (ret > 0) {
299 btrfs_release_path(path);
300 return 0;
303 leaf = path->nodes[0];
304 header = btrfs_item_ptr(leaf, path->slots[0],
305 struct btrfs_free_space_header);
306 num_entries = btrfs_free_space_entries(leaf, header);
307 num_bitmaps = btrfs_free_space_bitmaps(leaf, header);
308 generation = btrfs_free_space_generation(leaf, header);
309 btrfs_free_space_key(leaf, header, &disk_key);
310 btrfs_disk_key_to_cpu(&inode_location, &disk_key);
311 btrfs_release_path(path);
313 ret = btrfs_search_slot(NULL, root, &inode_location, path, 0, 0);
314 if (ret) {
315 fprintf(stderr, "Couldn't find free space inode %d\n", ret);
316 return 0;
319 leaf = path->nodes[0];
320 inode_item = btrfs_item_ptr(leaf, path->slots[0],
321 struct btrfs_inode_item);
323 inode_size = btrfs_inode_size(leaf, inode_item);
324 if (!inode_size || !btrfs_inode_generation(leaf, inode_item)) {
325 btrfs_release_path(path);
326 return 0;
329 if (btrfs_inode_generation(leaf, inode_item) != generation) {
330 fprintf(stderr,
331 "free space inode generation (%llu) did not match "
332 "free space cache generation (%llu)\n",
333 (unsigned long long)btrfs_inode_generation(leaf,
334 inode_item),
335 (unsigned long long)generation);
336 btrfs_release_path(path);
337 return 0;
340 btrfs_release_path(path);
342 if (!num_entries)
343 return 0;
345 ret = io_ctl_init(&io_ctl, inode_size, inode_location.objectid, root);
346 if (ret)
347 return ret;
349 ret = io_ctl_prepare_pages(&io_ctl, root, path,
350 inode_location.objectid);
351 if (ret)
352 goto out;
354 ret = io_ctl_check_crc(&io_ctl, 0);
355 if (ret)
356 goto free_cache;
358 ret = io_ctl_check_generation(&io_ctl, generation);
359 if (ret)
360 goto free_cache;
362 while (num_entries) {
363 e = calloc(1, sizeof(*e));
364 if (!e)
365 goto free_cache;
367 ret = io_ctl_read_entry(&io_ctl, e, &type);
368 if (ret) {
369 free(e);
370 goto free_cache;
373 if (!e->bytes) {
374 free(e);
375 goto free_cache;
378 if (type == BTRFS_FREE_SPACE_EXTENT) {
379 ret = link_free_space(ctl, e);
380 if (ret) {
381 fprintf(stderr,
382 "Duplicate entries in free space cache\n");
383 free(e);
384 goto free_cache;
386 } else {
387 BUG_ON(!num_bitmaps);
388 num_bitmaps--;
389 e->bitmap = kzalloc(ctl->sectorsize, GFP_NOFS);
390 if (!e->bitmap) {
391 free(e);
392 goto free_cache;
394 ret = link_free_space(ctl, e);
395 ctl->total_bitmaps++;
396 if (ret) {
397 fprintf(stderr,
398 "Duplicate entries in free space cache\n");
399 free(e->bitmap);
400 free(e);
401 goto free_cache;
403 list_add_tail(&e->list, &bitmaps);
406 num_entries--;
409 io_ctl_unmap_page(&io_ctl);
412 * We add the bitmaps at the end of the entries in order that
413 * the bitmap entries are added to the cache.
415 list_for_each_entry_safe(e, n, &bitmaps, list) {
416 list_del_init(&e->list);
417 ret = io_ctl_read_bitmap(&io_ctl, e);
418 if (ret)
419 goto free_cache;
422 io_ctl_drop_pages(&io_ctl);
423 merge_space_tree(ctl);
424 ret = 1;
425 out:
426 io_ctl_free(&io_ctl);
427 return ret;
428 free_cache:
429 io_ctl_drop_pages(&io_ctl);
430 __btrfs_remove_free_space_cache(ctl);
431 goto out;
434 int load_free_space_cache(struct btrfs_fs_info *fs_info,
435 struct btrfs_block_group_cache *block_group)
437 struct btrfs_free_space_ctl *ctl = block_group->free_space_ctl;
438 struct btrfs_path *path;
439 u64 used = btrfs_block_group_used(&block_group->item);
440 int ret = 0;
441 u64 bg_free;
442 s64 diff;
444 path = btrfs_alloc_path();
445 if (!path)
446 return 0;
448 ret = __load_free_space_cache(fs_info->tree_root, ctl, path,
449 block_group->key.objectid);
450 btrfs_free_path(path);
452 bg_free = block_group->key.offset - used - block_group->bytes_super;
453 diff = ctl->free_space - bg_free;
454 if (ret == 1 && diff) {
455 fprintf(stderr,
456 "block group %llu has wrong amount of free space, free space cache has %llu block group has %llu\n",
457 block_group->key.objectid, ctl->free_space, bg_free);
458 __btrfs_remove_free_space_cache(ctl);
460 * Due to btrfs_reserve_extent() can happen out of a
461 * transaction, but all btrfs_release_extent() happens inside
462 * a transaction, so under heavy race it's possible that free
463 * space cache has less free space, and both kernel just discard
464 * such cache. But if we find some case where free space cache
465 * has more free space, this means under certain case such
466 * cache can be loaded and cause double allocate.
468 * Detect such possibility here.
470 if (diff > 0)
471 error(
472 "free space cache has more free space than block group item, this could leads to serious corruption, please contact btrfs developers");
473 ret = -1;
476 if (ret < 0) {
477 if (diff <= 0)
478 ret = 0;
480 fprintf(stderr,
481 "failed to load free space cache for block group %llu\n",
482 block_group->key.objectid);
485 return ret;
488 static inline unsigned long offset_to_bit(u64 bitmap_start, u32 unit,
489 u64 offset)
491 BUG_ON(offset < bitmap_start);
492 offset -= bitmap_start;
493 return (unsigned long)(offset / unit);
496 static inline unsigned long bytes_to_bits(u64 bytes, u32 unit)
498 return (unsigned long)(bytes / unit);
501 static int tree_insert_offset(struct rb_root *root, u64 offset,
502 struct rb_node *node, int bitmap)
504 struct rb_node **p = &root->rb_node;
505 struct rb_node *parent = NULL;
506 struct btrfs_free_space *info;
508 while (*p) {
509 parent = *p;
510 info = rb_entry(parent, struct btrfs_free_space, offset_index);
512 if (offset < info->offset) {
513 p = &(*p)->rb_left;
514 } else if (offset > info->offset) {
515 p = &(*p)->rb_right;
516 } else {
518 * we could have a bitmap entry and an extent entry
519 * share the same offset. If this is the case, we want
520 * the extent entry to always be found first if we do a
521 * linear search through the tree, since we want to have
522 * the quickest allocation time, and allocating from an
523 * extent is faster than allocating from a bitmap. So
524 * if we're inserting a bitmap and we find an entry at
525 * this offset, we want to go right, or after this entry
526 * logically. If we are inserting an extent and we've
527 * found a bitmap, we want to go left, or before
528 * logically.
530 if (bitmap) {
531 if (info->bitmap)
532 return -EEXIST;
533 p = &(*p)->rb_right;
534 } else {
535 if (!info->bitmap)
536 return -EEXIST;
537 p = &(*p)->rb_left;
542 rb_link_node(node, parent, p);
543 rb_insert_color(node, root);
545 return 0;
549 * searches the tree for the given offset.
551 * fuzzy - If this is set, then we are trying to make an allocation, and we just
552 * want a section that has at least bytes size and comes at or after the given
553 * offset.
555 static struct btrfs_free_space *
556 tree_search_offset(struct btrfs_free_space_ctl *ctl,
557 u64 offset, int bitmap_only, int fuzzy)
559 struct rb_node *n = ctl->free_space_offset.rb_node;
560 struct btrfs_free_space *entry, *prev = NULL;
561 u32 sectorsize = ctl->sectorsize;
563 /* find entry that is closest to the 'offset' */
564 while (1) {
565 if (!n) {
566 entry = NULL;
567 break;
570 entry = rb_entry(n, struct btrfs_free_space, offset_index);
571 prev = entry;
573 if (offset < entry->offset)
574 n = n->rb_left;
575 else if (offset > entry->offset)
576 n = n->rb_right;
577 else
578 break;
581 if (bitmap_only) {
582 if (!entry)
583 return NULL;
584 if (entry->bitmap)
585 return entry;
588 * bitmap entry and extent entry may share same offset,
589 * in that case, bitmap entry comes after extent entry.
591 n = rb_next(n);
592 if (!n)
593 return NULL;
594 entry = rb_entry(n, struct btrfs_free_space, offset_index);
595 if (entry->offset != offset)
596 return NULL;
598 WARN_ON(!entry->bitmap);
599 return entry;
600 } else if (entry) {
601 if (entry->bitmap) {
603 * if previous extent entry covers the offset,
604 * we should return it instead of the bitmap entry
606 n = rb_prev(&entry->offset_index);
607 if (n) {
608 prev = rb_entry(n, struct btrfs_free_space,
609 offset_index);
610 if (!prev->bitmap &&
611 prev->offset + prev->bytes > offset)
612 entry = prev;
615 return entry;
618 if (!prev)
619 return NULL;
621 /* find last entry before the 'offset' */
622 entry = prev;
623 if (entry->offset > offset) {
624 n = rb_prev(&entry->offset_index);
625 if (n) {
626 entry = rb_entry(n, struct btrfs_free_space,
627 offset_index);
628 BUG_ON(entry->offset > offset);
629 } else {
630 if (fuzzy)
631 return entry;
632 else
633 return NULL;
637 if (entry->bitmap) {
638 n = rb_prev(&entry->offset_index);
639 if (n) {
640 prev = rb_entry(n, struct btrfs_free_space,
641 offset_index);
642 if (!prev->bitmap &&
643 prev->offset + prev->bytes > offset)
644 return prev;
646 if (entry->offset + BITS_PER_BITMAP(sectorsize) * ctl->unit > offset)
647 return entry;
648 } else if (entry->offset + entry->bytes > offset)
649 return entry;
651 if (!fuzzy)
652 return NULL;
654 while (1) {
655 if (entry->bitmap) {
656 if (entry->offset + BITS_PER_BITMAP(sectorsize) *
657 ctl->unit > offset)
658 break;
659 } else {
660 if (entry->offset + entry->bytes > offset)
661 break;
664 n = rb_next(&entry->offset_index);
665 if (!n)
666 return NULL;
667 entry = rb_entry(n, struct btrfs_free_space, offset_index);
669 return entry;
672 void unlink_free_space(struct btrfs_free_space_ctl *ctl,
673 struct btrfs_free_space *info)
675 rb_erase(&info->offset_index, &ctl->free_space_offset);
676 ctl->free_extents--;
677 ctl->free_space -= info->bytes;
680 static int link_free_space(struct btrfs_free_space_ctl *ctl,
681 struct btrfs_free_space *info)
683 int ret = 0;
685 BUG_ON(!info->bitmap && !info->bytes);
686 ret = tree_insert_offset(&ctl->free_space_offset, info->offset,
687 &info->offset_index, (info->bitmap != NULL));
688 if (ret)
689 return ret;
691 ctl->free_space += info->bytes;
692 ctl->free_extents++;
693 return ret;
696 static int search_bitmap(struct btrfs_free_space_ctl *ctl,
697 struct btrfs_free_space *bitmap_info, u64 *offset,
698 u64 *bytes)
700 unsigned long found_bits = 0;
701 unsigned long bits, i;
702 unsigned long next_zero;
703 u32 sectorsize = ctl->sectorsize;
705 i = offset_to_bit(bitmap_info->offset, ctl->unit,
706 max_t(u64, *offset, bitmap_info->offset));
707 bits = bytes_to_bits(*bytes, ctl->unit);
709 for_each_set_bit_from(i, bitmap_info->bitmap, BITS_PER_BITMAP(sectorsize)) {
710 next_zero = find_next_zero_bit(bitmap_info->bitmap,
711 BITS_PER_BITMAP(sectorsize), i);
712 if ((next_zero - i) >= bits) {
713 found_bits = next_zero - i;
714 break;
716 i = next_zero;
719 if (found_bits) {
720 *offset = (u64)(i * ctl->unit) + bitmap_info->offset;
721 *bytes = (u64)(found_bits) * ctl->unit;
722 return 0;
725 return -1;
728 struct btrfs_free_space *
729 btrfs_find_free_space(struct btrfs_free_space_ctl *ctl, u64 offset, u64 bytes)
731 return tree_search_offset(ctl, offset, 0, 0);
734 static void try_merge_free_space(struct btrfs_free_space_ctl *ctl,
735 struct btrfs_free_space *info)
737 struct btrfs_free_space *left_info;
738 struct btrfs_free_space *right_info;
739 u64 offset = info->offset;
740 u64 bytes = info->bytes;
743 * first we want to see if there is free space adjacent to the range we
744 * are adding, if there is remove that struct and add a new one to
745 * cover the entire range
747 right_info = tree_search_offset(ctl, offset + bytes, 0, 0);
748 if (right_info && rb_prev(&right_info->offset_index))
749 left_info = rb_entry(rb_prev(&right_info->offset_index),
750 struct btrfs_free_space, offset_index);
751 else
752 left_info = tree_search_offset(ctl, offset - 1, 0, 0);
754 if (right_info && !right_info->bitmap) {
755 unlink_free_space(ctl, right_info);
756 info->bytes += right_info->bytes;
757 free(right_info);
760 if (left_info && !left_info->bitmap &&
761 left_info->offset + left_info->bytes == offset) {
762 unlink_free_space(ctl, left_info);
763 info->offset = left_info->offset;
764 info->bytes += left_info->bytes;
765 free(left_info);
769 void btrfs_dump_free_space(struct btrfs_block_group_cache *block_group,
770 u64 bytes)
772 struct btrfs_free_space_ctl *ctl = block_group->free_space_ctl;
773 struct btrfs_free_space *info;
774 struct rb_node *n;
775 int count = 0;
777 for (n = rb_first(&ctl->free_space_offset); n; n = rb_next(n)) {
778 info = rb_entry(n, struct btrfs_free_space, offset_index);
779 if (info->bytes >= bytes && !block_group->ro)
780 count++;
781 printk("entry offset %llu, bytes %llu, bitmap %s\n",
782 (unsigned long long)info->offset,
783 (unsigned long long)info->bytes,
784 (info->bitmap) ? "yes" : "no");
786 printk("%d blocks of free space at or bigger than bytes is \n", count);
789 int btrfs_init_free_space_ctl(struct btrfs_block_group_cache *block_group,
790 int sectorsize)
792 struct btrfs_free_space_ctl *ctl;
794 ctl = calloc(1, sizeof(*ctl));
795 if (!ctl)
796 return -ENOMEM;
798 ctl->sectorsize = sectorsize;
799 ctl->unit = sectorsize;
800 ctl->start = block_group->key.objectid;
801 ctl->private = block_group;
802 block_group->free_space_ctl = ctl;
804 return 0;
807 void __btrfs_remove_free_space_cache(struct btrfs_free_space_ctl *ctl)
809 struct btrfs_free_space *info;
810 struct rb_node *node;
812 while ((node = rb_last(&ctl->free_space_offset)) != NULL) {
813 info = rb_entry(node, struct btrfs_free_space, offset_index);
814 unlink_free_space(ctl, info);
815 free(info->bitmap);
816 free(info);
820 void btrfs_remove_free_space_cache(struct btrfs_block_group_cache *block_group)
822 __btrfs_remove_free_space_cache(block_group->free_space_ctl);
825 int btrfs_add_free_space(struct btrfs_free_space_ctl *ctl, u64 offset,
826 u64 bytes)
828 struct btrfs_free_space *info;
829 int ret = 0;
831 info = calloc(1, sizeof(*info));
832 if (!info)
833 return -ENOMEM;
835 info->offset = offset;
836 info->bytes = bytes;
838 try_merge_free_space(ctl, info);
840 ret = link_free_space(ctl, info);
841 if (ret)
842 printk(KERN_CRIT "btrfs: unable to add free space :%d\n", ret);
844 return ret;
848 * Merges all the free space cache and kills the bitmap entries since we just
849 * want to use the free space cache to verify it's correct, no reason to keep
850 * the bitmaps around to confuse things.
852 static void merge_space_tree(struct btrfs_free_space_ctl *ctl)
854 struct btrfs_free_space *e, *prev = NULL;
855 struct rb_node *n;
856 int ret;
857 u32 sectorsize = ctl->sectorsize;
859 again:
860 prev = NULL;
861 for (n = rb_first(&ctl->free_space_offset); n; n = rb_next(n)) {
862 e = rb_entry(n, struct btrfs_free_space, offset_index);
863 if (e->bitmap) {
864 u64 offset = e->offset, bytes = ctl->unit;
865 u64 end;
867 end = e->offset + (u64)(BITS_PER_BITMAP(sectorsize) * ctl->unit);
869 unlink_free_space(ctl, e);
870 while (!(search_bitmap(ctl, e, &offset, &bytes))) {
871 ret = btrfs_add_free_space(ctl, offset,
872 bytes);
873 BUG_ON(ret);
874 offset += bytes;
875 if (offset >= end)
876 break;
877 bytes = ctl->unit;
879 free(e->bitmap);
880 free(e);
881 goto again;
883 if (!prev)
884 goto next;
885 if (prev->offset + prev->bytes == e->offset) {
886 unlink_free_space(ctl, prev);
887 unlink_free_space(ctl, e);
888 prev->bytes += e->bytes;
889 free(e);
890 link_free_space(ctl, prev);
891 goto again;
893 next:
894 prev = e;
898 int btrfs_clear_free_space_cache(struct btrfs_fs_info *fs_info,
899 struct btrfs_block_group_cache *bg)
901 struct btrfs_trans_handle *trans;
902 struct btrfs_root *tree_root = fs_info->tree_root;
903 struct btrfs_path path;
904 struct btrfs_key key;
905 struct btrfs_disk_key location;
906 struct btrfs_free_space_header *sc_header;
907 struct extent_buffer *node;
908 u64 ino;
909 int slot;
910 int ret;
912 trans = btrfs_start_transaction(tree_root, 1);
913 if (IS_ERR(trans))
914 return PTR_ERR(trans);
916 btrfs_init_path(&path);
918 key.objectid = BTRFS_FREE_SPACE_OBJECTID;
919 key.type = 0;
920 key.offset = bg->key.objectid;
922 ret = btrfs_search_slot(trans, tree_root, &key, &path, -1, 1);
923 if (ret > 0) {
924 ret = 0;
925 goto out;
927 if (ret < 0)
928 goto out;
930 node = path.nodes[0];
931 slot = path.slots[0];
932 sc_header = btrfs_item_ptr(node, slot, struct btrfs_free_space_header);
933 btrfs_free_space_key(node, sc_header, &location);
934 ino = btrfs_disk_key_objectid(&location);
936 /* Delete the free space header, as we have the ino to continue */
937 ret = btrfs_del_item(trans, tree_root, &path);
938 if (ret < 0) {
939 error("failed to remove free space header for block group %llu: %d",
940 bg->key.objectid, ret);
941 goto out;
943 btrfs_release_path(&path);
945 /* Iterate from the end of the free space cache inode */
946 key.objectid = ino;
947 key.type = BTRFS_EXTENT_DATA_KEY;
948 key.offset = (u64)-1;
949 ret = btrfs_search_slot(trans, tree_root, &key, &path, -1, 1);
950 if (ret < 0) {
951 error("failed to locate free space cache extent for block group %llu: %d",
952 bg->key.objectid, ret);
953 goto out;
955 while (1) {
956 struct btrfs_file_extent_item *fi;
957 u64 disk_bytenr;
958 u64 disk_num_bytes;
960 ret = btrfs_previous_item(tree_root, &path, ino,
961 BTRFS_EXTENT_DATA_KEY);
962 if (ret > 0) {
963 ret = 0;
964 break;
966 if (ret < 0) {
967 error(
968 "failed to locate free space cache extent for block group %llu: %d",
969 bg->key.objectid, ret);
970 goto out;
972 node = path.nodes[0];
973 slot = path.slots[0];
974 btrfs_item_key_to_cpu(node, &key, slot);
975 fi = btrfs_item_ptr(node, slot, struct btrfs_file_extent_item);
976 disk_bytenr = btrfs_file_extent_disk_bytenr(node, fi);
977 disk_num_bytes = btrfs_file_extent_disk_num_bytes(node, fi);
979 ret = btrfs_free_extent(trans, tree_root, disk_bytenr,
980 disk_num_bytes, 0, tree_root->objectid,
981 ino, key.offset);
982 if (ret < 0) {
983 error("failed to remove backref for disk bytenr %llu: %d",
984 disk_bytenr, ret);
985 goto out;
987 ret = btrfs_del_item(trans, tree_root, &path);
988 if (ret < 0) {
989 error(
990 "failed to remove free space extent data for ino %llu offset %llu: %d",
991 ino, key.offset, ret);
992 goto out;
995 btrfs_release_path(&path);
997 /* Now delete free space cache inode item */
998 key.objectid = ino;
999 key.type = BTRFS_INODE_ITEM_KEY;
1000 key.offset = 0;
1002 ret = btrfs_search_slot(trans, tree_root, &key, &path, -1, 1);
1003 if (ret > 0)
1004 warning("free space inode %llu not found, ignore", ino);
1005 if (ret < 0) {
1006 error(
1007 "failed to locate free space cache inode %llu for block group %llu: %d",
1008 ino, bg->key.objectid, ret);
1009 goto out;
1011 ret = btrfs_del_item(trans, tree_root, &path);
1012 if (ret < 0) {
1013 error(
1014 "failed to delete free space cache inode %llu for block group %llu: %d",
1015 ino, bg->key.objectid, ret);
1017 out:
1018 btrfs_release_path(&path);
1019 if (!ret)
1020 btrfs_commit_transaction(trans, tree_root);
1021 return ret;