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"
21 #include "free-space-cache.h"
22 #include "transaction.h"
24 #include "extent_io.h"
28 #define CACHE_SECTORSIZE 4096
29 #define BITS_PER_BITMAP (CACHE_SECTORSIZE * 8)
30 #define MAX_CACHE_BYTES_PER_GIG (32 * 1024)
32 static int link_free_space(struct btrfs_free_space_ctl *ctl,
33 struct btrfs_free_space *info);
34 static void merge_space_tree(struct btrfs_free_space_ctl *ctl);
39 struct btrfs_root *root;
44 unsigned check_crcs:1;
47 static int io_ctl_init(struct io_ctl *io_ctl, u64 size, u64 ino,
48 struct btrfs_root *root)
50 memset(io_ctl, 0, sizeof(struct io_ctl));
51 io_ctl->num_pages = (size + CACHE_SECTORSIZE - 1) / CACHE_SECTORSIZE;
52 io_ctl->buffer = kzalloc(size, GFP_NOFS);
55 io_ctl->total_size = size;
57 if (ino != BTRFS_FREE_INO_OBJECTID)
58 io_ctl->check_crcs = 1;
62 static void io_ctl_free(struct io_ctl *io_ctl)
64 kfree(io_ctl->buffer);
67 static void io_ctl_unmap_page(struct io_ctl *io_ctl)
75 static void io_ctl_map_page(struct io_ctl *io_ctl, int clear)
77 BUG_ON(io_ctl->index >= io_ctl->num_pages);
78 io_ctl->cur = io_ctl->buffer + (io_ctl->index++ * CACHE_SECTORSIZE);
79 io_ctl->orig = io_ctl->cur;
80 io_ctl->size = CACHE_SECTORSIZE;
82 memset(io_ctl->cur, 0, CACHE_SECTORSIZE);
85 static void io_ctl_drop_pages(struct io_ctl *io_ctl)
87 io_ctl_unmap_page(io_ctl);
90 static int io_ctl_prepare_pages(struct io_ctl *io_ctl, struct btrfs_root *root,
91 struct btrfs_path *path, u64 ino)
93 struct extent_buffer *leaf;
94 struct btrfs_file_extent_item *fi;
101 key.type = BTRFS_EXTENT_DATA_KEY;
104 ret = btrfs_search_slot(NULL, root, &key, path, 0, 0);
106 printf("Couldn't find file extent item for free space inode"
108 btrfs_release_path(path);
112 while (total_read < io_ctl->total_size) {
113 if (path->slots[0] >= btrfs_header_nritems(path->nodes[0])) {
114 ret = btrfs_next_leaf(root, path);
120 leaf = path->nodes[0];
122 btrfs_item_key_to_cpu(leaf, &key, path->slots[0]);
123 if (key.objectid != ino) {
128 if (key.type != BTRFS_EXTENT_DATA_KEY) {
133 fi = btrfs_item_ptr(path->nodes[0], path->slots[0],
134 struct btrfs_file_extent_item);
135 if (btrfs_file_extent_type(path->nodes[0], fi) !=
136 BTRFS_FILE_EXTENT_REG) {
137 printf("Not the file extent type we wanted\n");
142 bytenr = btrfs_file_extent_disk_bytenr(leaf, fi) +
143 btrfs_file_extent_offset(leaf, fi);
144 len = btrfs_file_extent_num_bytes(leaf, fi);
145 ret = read_data_from_disk(root->fs_info,
146 io_ctl->buffer + key.offset, bytenr,
154 btrfs_release_path(path);
158 static int io_ctl_check_generation(struct io_ctl *io_ctl, u64 generation)
163 * Skip the crc area. If we don't check crcs then we just have a 64bit
164 * chunk at the front of the first page.
166 if (io_ctl->check_crcs) {
167 io_ctl->cur += sizeof(u32) * io_ctl->num_pages;
168 io_ctl->size -= sizeof(u64) +
169 (sizeof(u32) * io_ctl->num_pages);
171 io_ctl->cur += sizeof(u64);
172 io_ctl->size -= sizeof(u64) * 2;
176 if (le64_to_cpu(*gen) != generation) {
177 printk("btrfs: space cache generation "
178 "(%Lu) does not match inode (%Lu)\n", *gen,
180 io_ctl_unmap_page(io_ctl);
183 io_ctl->cur += sizeof(u64);
187 static int io_ctl_check_crc(struct io_ctl *io_ctl, int index)
193 if (!io_ctl->check_crcs) {
194 io_ctl_map_page(io_ctl, 0);
199 offset = sizeof(u32) * io_ctl->num_pages;
201 tmp = io_ctl->buffer;
205 io_ctl_map_page(io_ctl, 0);
206 crc = crc32c(crc, io_ctl->orig + offset, CACHE_SECTORSIZE - offset);
207 btrfs_csum_final(crc, (char *)&crc);
209 printk("btrfs: csum mismatch on free space cache\n");
210 io_ctl_unmap_page(io_ctl);
217 static int io_ctl_read_entry(struct io_ctl *io_ctl,
218 struct btrfs_free_space *entry, u8 *type)
220 struct btrfs_free_space_entry *e;
224 ret = io_ctl_check_crc(io_ctl, io_ctl->index);
230 entry->offset = le64_to_cpu(e->offset);
231 entry->bytes = le64_to_cpu(e->bytes);
233 io_ctl->cur += sizeof(struct btrfs_free_space_entry);
234 io_ctl->size -= sizeof(struct btrfs_free_space_entry);
236 if (io_ctl->size >= sizeof(struct btrfs_free_space_entry))
239 io_ctl_unmap_page(io_ctl);
244 static int io_ctl_read_bitmap(struct io_ctl *io_ctl,
245 struct btrfs_free_space *entry)
249 ret = io_ctl_check_crc(io_ctl, io_ctl->index);
253 memcpy(entry->bitmap, io_ctl->cur, CACHE_SECTORSIZE);
254 io_ctl_unmap_page(io_ctl);
260 static int __load_free_space_cache(struct btrfs_root *root,
261 struct btrfs_free_space_ctl *ctl,
262 struct btrfs_path *path, u64 offset)
264 struct btrfs_free_space_header *header;
265 struct btrfs_inode_item *inode_item;
266 struct extent_buffer *leaf;
267 struct io_ctl io_ctl;
268 struct btrfs_key key;
269 struct btrfs_key inode_location;
270 struct btrfs_disk_key disk_key;
271 struct btrfs_free_space *e, *n;
272 struct list_head bitmaps;
280 INIT_LIST_HEAD(&bitmaps);
282 key.objectid = BTRFS_FREE_SPACE_OBJECTID;
286 ret = btrfs_search_slot(NULL, root, &key, path, 0, 0);
289 } else if (ret > 0) {
290 btrfs_release_path(path);
294 leaf = path->nodes[0];
295 header = btrfs_item_ptr(leaf, path->slots[0],
296 struct btrfs_free_space_header);
297 num_entries = btrfs_free_space_entries(leaf, header);
298 num_bitmaps = btrfs_free_space_bitmaps(leaf, header);
299 generation = btrfs_free_space_generation(leaf, header);
300 btrfs_free_space_key(leaf, header, &disk_key);
301 btrfs_disk_key_to_cpu(&inode_location, &disk_key);
302 btrfs_release_path(path);
304 ret = btrfs_search_slot(NULL, root, &inode_location, path, 0, 0);
306 printf("Couldn't find free space inode %d\n", ret);
310 leaf = path->nodes[0];
311 inode_item = btrfs_item_ptr(leaf, path->slots[0],
312 struct btrfs_inode_item);
314 inode_size = btrfs_inode_size(leaf, inode_item);
315 if (!inode_size || !btrfs_inode_generation(leaf, inode_item)) {
316 btrfs_release_path(path);
320 if (btrfs_inode_generation(leaf, inode_item) != generation) {
321 printf("free space inode generation (%llu) did not match "
322 "free space cache generation (%llu)\n",
323 (unsigned long long)btrfs_inode_generation(leaf,
325 (unsigned long long)generation);
326 btrfs_release_path(path);
330 btrfs_release_path(path);
335 ret = io_ctl_init(&io_ctl, inode_size, inode_location.objectid, root);
339 ret = io_ctl_prepare_pages(&io_ctl, root, path,
340 inode_location.objectid);
344 ret = io_ctl_check_crc(&io_ctl, 0);
348 ret = io_ctl_check_generation(&io_ctl, generation);
352 while (num_entries) {
353 e = calloc(1, sizeof(*e));
357 ret = io_ctl_read_entry(&io_ctl, e, &type);
368 if (type == BTRFS_FREE_SPACE_EXTENT) {
369 ret = link_free_space(ctl, e);
371 printf("Duplicate entries in free space cache, dumping");
376 BUG_ON(!num_bitmaps);
378 e->bitmap = kzalloc(CACHE_SECTORSIZE, GFP_NOFS);
383 ret = link_free_space(ctl, e);
384 ctl->total_bitmaps++;
386 printf("Duplicate entries in free space cache, dumping");
391 list_add_tail(&e->list, &bitmaps);
397 io_ctl_unmap_page(&io_ctl);
400 * We add the bitmaps at the end of the entries in order that
401 * the bitmap entries are added to the cache.
403 list_for_each_entry_safe(e, n, &bitmaps, list) {
404 list_del_init(&e->list);
405 ret = io_ctl_read_bitmap(&io_ctl, e);
410 io_ctl_drop_pages(&io_ctl);
411 merge_space_tree(ctl);
414 io_ctl_free(&io_ctl);
417 io_ctl_drop_pages(&io_ctl);
418 __btrfs_remove_free_space_cache(ctl);
422 int load_free_space_cache(struct btrfs_fs_info *fs_info,
423 struct btrfs_block_group_cache *block_group)
425 struct btrfs_free_space_ctl *ctl = block_group->free_space_ctl;
426 struct btrfs_path *path;
429 path = btrfs_alloc_path();
433 ret = __load_free_space_cache(fs_info->tree_root, ctl, path,
434 block_group->key.objectid);
435 btrfs_free_path(path);
440 printf("failed to load free space cache for block group %llu\n",
441 block_group->key.objectid);
447 static inline unsigned long offset_to_bit(u64 bitmap_start, u32 unit,
450 BUG_ON(offset < bitmap_start);
451 offset -= bitmap_start;
452 return (unsigned long)(offset / unit);
455 static inline unsigned long bytes_to_bits(u64 bytes, u32 unit)
457 return (unsigned long)(bytes / unit);
460 static inline u64 offset_to_bitmap(struct btrfs_free_space_ctl *ctl,
464 u64 bytes_per_bitmap;
466 bytes_per_bitmap = BITS_PER_BITMAP * ctl->unit;
467 bitmap_start = offset - ctl->start;
468 bitmap_start = bitmap_start / bytes_per_bitmap;
469 bitmap_start *= bytes_per_bitmap;
470 bitmap_start += ctl->start;
475 static int tree_insert_offset(struct rb_root *root, u64 offset,
476 struct rb_node *node, int bitmap)
478 struct rb_node **p = &root->rb_node;
479 struct rb_node *parent = NULL;
480 struct btrfs_free_space *info;
484 info = rb_entry(parent, struct btrfs_free_space, offset_index);
486 if (offset < info->offset) {
488 } else if (offset > info->offset) {
492 * we could have a bitmap entry and an extent entry
493 * share the same offset. If this is the case, we want
494 * the extent entry to always be found first if we do a
495 * linear search through the tree, since we want to have
496 * the quickest allocation time, and allocating from an
497 * extent is faster than allocating from a bitmap. So
498 * if we're inserting a bitmap and we find an entry at
499 * this offset, we want to go right, or after this entry
500 * logically. If we are inserting an extent and we've
501 * found a bitmap, we want to go left, or before
516 rb_link_node(node, parent, p);
517 rb_insert_color(node, root);
523 * searches the tree for the given offset.
525 * fuzzy - If this is set, then we are trying to make an allocation, and we just
526 * want a section that has at least bytes size and comes at or after the given
529 static struct btrfs_free_space *
530 tree_search_offset(struct btrfs_free_space_ctl *ctl,
531 u64 offset, int bitmap_only, int fuzzy)
533 struct rb_node *n = ctl->free_space_offset.rb_node;
534 struct btrfs_free_space *entry, *prev = NULL;
536 /* find entry that is closest to the 'offset' */
543 entry = rb_entry(n, struct btrfs_free_space, offset_index);
546 if (offset < entry->offset)
548 else if (offset > entry->offset)
561 * bitmap entry and extent entry may share same offset,
562 * in that case, bitmap entry comes after extent entry.
567 entry = rb_entry(n, struct btrfs_free_space, offset_index);
568 if (entry->offset != offset)
571 WARN_ON(!entry->bitmap);
576 * if previous extent entry covers the offset,
577 * we should return it instead of the bitmap entry
579 n = rb_prev(&entry->offset_index);
581 prev = rb_entry(n, struct btrfs_free_space,
584 prev->offset + prev->bytes > offset)
594 /* find last entry before the 'offset' */
596 if (entry->offset > offset) {
597 n = rb_prev(&entry->offset_index);
599 entry = rb_entry(n, struct btrfs_free_space,
601 BUG_ON(entry->offset > offset);
611 n = rb_prev(&entry->offset_index);
613 prev = rb_entry(n, struct btrfs_free_space,
616 prev->offset + prev->bytes > offset)
619 if (entry->offset + BITS_PER_BITMAP * ctl->unit > offset)
621 } else if (entry->offset + entry->bytes > offset)
629 if (entry->offset + BITS_PER_BITMAP *
633 if (entry->offset + entry->bytes > offset)
637 n = rb_next(&entry->offset_index);
640 entry = rb_entry(n, struct btrfs_free_space, offset_index);
645 void unlink_free_space(struct btrfs_free_space_ctl *ctl,
646 struct btrfs_free_space *info)
648 rb_erase(&info->offset_index, &ctl->free_space_offset);
650 ctl->free_space -= info->bytes;
653 static int link_free_space(struct btrfs_free_space_ctl *ctl,
654 struct btrfs_free_space *info)
658 BUG_ON(!info->bitmap && !info->bytes);
659 ret = tree_insert_offset(&ctl->free_space_offset, info->offset,
660 &info->offset_index, (info->bitmap != NULL));
664 ctl->free_space += info->bytes;
669 static int search_bitmap(struct btrfs_free_space_ctl *ctl,
670 struct btrfs_free_space *bitmap_info, u64 *offset,
673 unsigned long found_bits = 0;
674 unsigned long bits, i;
675 unsigned long next_zero;
677 i = offset_to_bit(bitmap_info->offset, ctl->unit,
678 max_t(u64, *offset, bitmap_info->offset));
679 bits = bytes_to_bits(*bytes, ctl->unit);
681 for_each_set_bit_from(i, bitmap_info->bitmap, BITS_PER_BITMAP) {
682 next_zero = find_next_zero_bit(bitmap_info->bitmap,
684 if ((next_zero - i) >= bits) {
685 found_bits = next_zero - i;
692 *offset = (u64)(i * ctl->unit) + bitmap_info->offset;
693 *bytes = (u64)(found_bits) * ctl->unit;
700 struct btrfs_free_space *
701 btrfs_find_free_space(struct btrfs_free_space_ctl *ctl, u64 offset, u64 bytes)
703 return tree_search_offset(ctl, offset, 0, 0);
706 static void try_merge_free_space(struct btrfs_free_space_ctl *ctl,
707 struct btrfs_free_space *info)
709 struct btrfs_free_space *left_info;
710 struct btrfs_free_space *right_info;
711 u64 offset = info->offset;
712 u64 bytes = info->bytes;
715 * first we want to see if there is free space adjacent to the range we
716 * are adding, if there is remove that struct and add a new one to
717 * cover the entire range
719 right_info = tree_search_offset(ctl, offset + bytes, 0, 0);
720 if (right_info && rb_prev(&right_info->offset_index))
721 left_info = rb_entry(rb_prev(&right_info->offset_index),
722 struct btrfs_free_space, offset_index);
724 left_info = tree_search_offset(ctl, offset - 1, 0, 0);
726 if (right_info && !right_info->bitmap) {
727 unlink_free_space(ctl, right_info);
728 info->bytes += right_info->bytes;
732 if (left_info && !left_info->bitmap &&
733 left_info->offset + left_info->bytes == offset) {
734 unlink_free_space(ctl, left_info);
735 info->offset = left_info->offset;
736 info->bytes += left_info->bytes;
741 void btrfs_dump_free_space(struct btrfs_block_group_cache *block_group,
744 struct btrfs_free_space_ctl *ctl = block_group->free_space_ctl;
745 struct btrfs_free_space *info;
749 for (n = rb_first(&ctl->free_space_offset); n; n = rb_next(n)) {
750 info = rb_entry(n, struct btrfs_free_space, offset_index);
751 if (info->bytes >= bytes && !block_group->ro)
753 printk("entry offset %llu, bytes %llu, bitmap %s\n",
754 (unsigned long long)info->offset,
755 (unsigned long long)info->bytes,
756 (info->bitmap) ? "yes" : "no");
758 printk("%d blocks of free space at or bigger than bytes is \n", count);
761 int btrfs_init_free_space_ctl(struct btrfs_block_group_cache *block_group,
764 struct btrfs_free_space_ctl *ctl;
766 ctl = calloc(1, sizeof(*ctl));
770 ctl->unit = sectorsize;
771 ctl->start = block_group->key.objectid;
772 ctl->private = block_group;
773 block_group->free_space_ctl = ctl;
778 void __btrfs_remove_free_space_cache(struct btrfs_free_space_ctl *ctl)
780 struct btrfs_free_space *info;
781 struct rb_node *node;
783 while ((node = rb_last(&ctl->free_space_offset)) != NULL) {
784 info = rb_entry(node, struct btrfs_free_space, offset_index);
785 unlink_free_space(ctl, info);
791 void btrfs_remove_free_space_cache(struct btrfs_block_group_cache *block_group)
793 __btrfs_remove_free_space_cache(block_group->free_space_ctl);
796 static int btrfs_add_free_space(struct btrfs_free_space_ctl *ctl, u64 offset,
799 struct btrfs_free_space *info;
802 info = calloc(1, sizeof(*info));
806 info->offset = offset;
809 try_merge_free_space(ctl, info);
811 ret = link_free_space(ctl, info);
813 printk(KERN_CRIT "btrfs: unable to add free space :%d\n", ret);
814 BUG_ON(ret == -EEXIST);
821 * Merges all the free space cache and kills the bitmap entries since we just
822 * want to use the free space cache to verify it's correct, no reason to keep
823 * the bitmaps around to confuse things.
825 static void merge_space_tree(struct btrfs_free_space_ctl *ctl)
827 struct btrfs_free_space *e, *prev = NULL;
833 for (n = rb_first(&ctl->free_space_offset); n; n = rb_next(n)) {
834 e = rb_entry(n, struct btrfs_free_space, offset_index);
836 u64 offset = e->offset, bytes = ctl->unit;
839 end = e->offset + (u64)(BITS_PER_BITMAP * ctl->unit);
841 unlink_free_space(ctl, e);
842 while (!(search_bitmap(ctl, e, &offset, &bytes))) {
843 ret = btrfs_add_free_space(ctl, offset,
857 if (prev->offset + prev->bytes == e->offset) {
858 unlink_free_space(ctl, prev);
859 unlink_free_space(ctl, e);
860 prev->bytes += e->bytes;
862 link_free_space(ctl, prev);