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);
313 if (btrfs_inode_generation(leaf, inode_item) != generation) {
314 printf("free space inode generation (%llu) did not match "
315 "free space cache generation (%llu)\n",
316 (unsigned long long)btrfs_inode_generation(leaf,
318 (unsigned long long)generation);
319 btrfs_release_path(path);
323 inode_size = btrfs_inode_size(leaf, inode_item);
324 btrfs_release_path(path);
331 ret = io_ctl_init(&io_ctl, inode_size, inode_location.objectid, root);
335 ret = io_ctl_prepare_pages(&io_ctl, root, path,
336 inode_location.objectid);
340 ret = io_ctl_check_crc(&io_ctl, 0);
344 ret = io_ctl_check_generation(&io_ctl, generation);
348 while (num_entries) {
349 e = calloc(1, sizeof(*e));
353 ret = io_ctl_read_entry(&io_ctl, e, &type);
364 if (type == BTRFS_FREE_SPACE_EXTENT) {
365 ret = link_free_space(ctl, e);
367 printf("Duplicate entries in free space cache, dumping");
372 BUG_ON(!num_bitmaps);
374 e->bitmap = kzalloc(CACHE_SECTORSIZE, GFP_NOFS);
379 ret = link_free_space(ctl, e);
380 ctl->total_bitmaps++;
382 printf("Duplicate entries in free space cache, dumping");
387 list_add_tail(&e->list, &bitmaps);
393 io_ctl_unmap_page(&io_ctl);
396 * We add the bitmaps at the end of the entries in order that
397 * the bitmap entries are added to the cache.
399 list_for_each_entry_safe(e, n, &bitmaps, list) {
400 list_del_init(&e->list);
401 ret = io_ctl_read_bitmap(&io_ctl, e);
406 io_ctl_drop_pages(&io_ctl);
407 merge_space_tree(ctl);
410 io_ctl_free(&io_ctl);
413 io_ctl_drop_pages(&io_ctl);
414 __btrfs_remove_free_space_cache(ctl);
418 int load_free_space_cache(struct btrfs_fs_info *fs_info,
419 struct btrfs_block_group_cache *block_group)
421 struct btrfs_free_space_ctl *ctl = block_group->free_space_ctl;
422 struct btrfs_path *path;
425 path = btrfs_alloc_path();
429 ret = __load_free_space_cache(fs_info->tree_root, ctl, path,
430 block_group->key.objectid);
431 btrfs_free_path(path);
436 printf("failed to load free space cache for block group %llu\n",
437 block_group->key.objectid);
443 static inline unsigned long offset_to_bit(u64 bitmap_start, u32 unit,
446 BUG_ON(offset < bitmap_start);
447 offset -= bitmap_start;
448 return (unsigned long)(offset / unit);
451 static inline unsigned long bytes_to_bits(u64 bytes, u32 unit)
453 return (unsigned long)(bytes / unit);
456 static inline u64 offset_to_bitmap(struct btrfs_free_space_ctl *ctl,
460 u64 bytes_per_bitmap;
462 bytes_per_bitmap = BITS_PER_BITMAP * ctl->unit;
463 bitmap_start = offset - ctl->start;
464 bitmap_start = bitmap_start / bytes_per_bitmap;
465 bitmap_start *= bytes_per_bitmap;
466 bitmap_start += ctl->start;
471 static int tree_insert_offset(struct rb_root *root, u64 offset,
472 struct rb_node *node, int bitmap)
474 struct rb_node **p = &root->rb_node;
475 struct rb_node *parent = NULL;
476 struct btrfs_free_space *info;
480 info = rb_entry(parent, struct btrfs_free_space, offset_index);
482 if (offset < info->offset) {
484 } else if (offset > info->offset) {
488 * we could have a bitmap entry and an extent entry
489 * share the same offset. If this is the case, we want
490 * the extent entry to always be found first if we do a
491 * linear search through the tree, since we want to have
492 * the quickest allocation time, and allocating from an
493 * extent is faster than allocating from a bitmap. So
494 * if we're inserting a bitmap and we find an entry at
495 * this offset, we want to go right, or after this entry
496 * logically. If we are inserting an extent and we've
497 * found a bitmap, we want to go left, or before
512 rb_link_node(node, parent, p);
513 rb_insert_color(node, root);
519 * searches the tree for the given offset.
521 * fuzzy - If this is set, then we are trying to make an allocation, and we just
522 * want a section that has at least bytes size and comes at or after the given
525 static struct btrfs_free_space *
526 tree_search_offset(struct btrfs_free_space_ctl *ctl,
527 u64 offset, int bitmap_only, int fuzzy)
529 struct rb_node *n = ctl->free_space_offset.rb_node;
530 struct btrfs_free_space *entry, *prev = NULL;
532 /* find entry that is closest to the 'offset' */
539 entry = rb_entry(n, struct btrfs_free_space, offset_index);
542 if (offset < entry->offset)
544 else if (offset > entry->offset)
557 * bitmap entry and extent entry may share same offset,
558 * in that case, bitmap entry comes after extent entry.
563 entry = rb_entry(n, struct btrfs_free_space, offset_index);
564 if (entry->offset != offset)
567 WARN_ON(!entry->bitmap);
572 * if previous extent entry covers the offset,
573 * we should return it instead of the bitmap entry
575 n = rb_prev(&entry->offset_index);
577 prev = rb_entry(n, struct btrfs_free_space,
580 prev->offset + prev->bytes > offset)
590 /* find last entry before the 'offset' */
592 if (entry->offset > offset) {
593 n = rb_prev(&entry->offset_index);
595 entry = rb_entry(n, struct btrfs_free_space,
597 BUG_ON(entry->offset > offset);
607 n = rb_prev(&entry->offset_index);
609 prev = rb_entry(n, struct btrfs_free_space,
612 prev->offset + prev->bytes > offset)
615 if (entry->offset + BITS_PER_BITMAP * ctl->unit > offset)
617 } else if (entry->offset + entry->bytes > offset)
625 if (entry->offset + BITS_PER_BITMAP *
629 if (entry->offset + entry->bytes > offset)
633 n = rb_next(&entry->offset_index);
636 entry = rb_entry(n, struct btrfs_free_space, offset_index);
641 void unlink_free_space(struct btrfs_free_space_ctl *ctl,
642 struct btrfs_free_space *info)
644 rb_erase(&info->offset_index, &ctl->free_space_offset);
646 ctl->free_space -= info->bytes;
649 static int link_free_space(struct btrfs_free_space_ctl *ctl,
650 struct btrfs_free_space *info)
654 BUG_ON(!info->bitmap && !info->bytes);
655 ret = tree_insert_offset(&ctl->free_space_offset, info->offset,
656 &info->offset_index, (info->bitmap != NULL));
660 ctl->free_space += info->bytes;
665 static int search_bitmap(struct btrfs_free_space_ctl *ctl,
666 struct btrfs_free_space *bitmap_info, u64 *offset,
669 unsigned long found_bits = 0;
670 unsigned long bits, i;
671 unsigned long next_zero;
673 i = offset_to_bit(bitmap_info->offset, ctl->unit,
674 max_t(u64, *offset, bitmap_info->offset));
675 bits = bytes_to_bits(*bytes, ctl->unit);
677 for_each_set_bit_from(i, bitmap_info->bitmap, BITS_PER_BITMAP) {
678 next_zero = find_next_zero_bit(bitmap_info->bitmap,
680 if ((next_zero - i) >= bits) {
681 found_bits = next_zero - i;
688 *offset = (u64)(i * ctl->unit) + bitmap_info->offset;
689 *bytes = (u64)(found_bits) * ctl->unit;
696 struct btrfs_free_space *
697 btrfs_find_free_space(struct btrfs_free_space_ctl *ctl, u64 offset, u64 bytes)
699 return tree_search_offset(ctl, offset, 0, 0);
702 static void try_merge_free_space(struct btrfs_free_space_ctl *ctl,
703 struct btrfs_free_space *info)
705 struct btrfs_free_space *left_info;
706 struct btrfs_free_space *right_info;
707 u64 offset = info->offset;
708 u64 bytes = info->bytes;
711 * first we want to see if there is free space adjacent to the range we
712 * are adding, if there is remove that struct and add a new one to
713 * cover the entire range
715 right_info = tree_search_offset(ctl, offset + bytes, 0, 0);
716 if (right_info && rb_prev(&right_info->offset_index))
717 left_info = rb_entry(rb_prev(&right_info->offset_index),
718 struct btrfs_free_space, offset_index);
720 left_info = tree_search_offset(ctl, offset - 1, 0, 0);
722 if (right_info && !right_info->bitmap) {
723 unlink_free_space(ctl, right_info);
724 info->bytes += right_info->bytes;
728 if (left_info && !left_info->bitmap &&
729 left_info->offset + left_info->bytes == offset) {
730 unlink_free_space(ctl, left_info);
731 info->offset = left_info->offset;
732 info->bytes += left_info->bytes;
737 void btrfs_dump_free_space(struct btrfs_block_group_cache *block_group,
740 struct btrfs_free_space_ctl *ctl = block_group->free_space_ctl;
741 struct btrfs_free_space *info;
745 for (n = rb_first(&ctl->free_space_offset); n; n = rb_next(n)) {
746 info = rb_entry(n, struct btrfs_free_space, offset_index);
747 if (info->bytes >= bytes && !block_group->ro)
749 printk("entry offset %llu, bytes %llu, bitmap %s\n",
750 (unsigned long long)info->offset,
751 (unsigned long long)info->bytes,
752 (info->bitmap) ? "yes" : "no");
754 printk("%d blocks of free space at or bigger than bytes is \n", count);
757 int btrfs_init_free_space_ctl(struct btrfs_block_group_cache *block_group,
760 struct btrfs_free_space_ctl *ctl;
762 ctl = calloc(1, sizeof(*ctl));
766 ctl->unit = sectorsize;
767 ctl->start = block_group->key.objectid;
768 ctl->private = block_group;
769 block_group->free_space_ctl = ctl;
774 void __btrfs_remove_free_space_cache(struct btrfs_free_space_ctl *ctl)
776 struct btrfs_free_space *info;
777 struct rb_node *node;
779 while ((node = rb_last(&ctl->free_space_offset)) != NULL) {
780 info = rb_entry(node, struct btrfs_free_space, offset_index);
781 unlink_free_space(ctl, info);
787 void btrfs_remove_free_space_cache(struct btrfs_block_group_cache *block_group)
789 __btrfs_remove_free_space_cache(block_group->free_space_ctl);
792 static int btrfs_add_free_space(struct btrfs_free_space_ctl *ctl, u64 offset,
795 struct btrfs_free_space *info;
798 info = calloc(1, sizeof(*info));
802 info->offset = offset;
805 try_merge_free_space(ctl, info);
807 ret = link_free_space(ctl, info);
809 printk(KERN_CRIT "btrfs: unable to add free space :%d\n", ret);
810 BUG_ON(ret == -EEXIST);
817 * Merges all the free space cache and kills the bitmap entries since we just
818 * want to use the free space cache to verify it's correct, no reason to keep
819 * the bitmaps around to confuse things.
821 static void merge_space_tree(struct btrfs_free_space_ctl *ctl)
823 struct btrfs_free_space *e, *prev = NULL;
829 for (n = rb_first(&ctl->free_space_offset); n; n = rb_next(n)) {
830 e = rb_entry(n, struct btrfs_free_space, offset_index);
832 u64 offset = e->offset, bytes = ctl->unit;
835 end = e->offset + (u64)(BITS_PER_BITMAP * ctl->unit);
837 unlink_free_space(ctl, e);
838 while (!(search_bitmap(ctl, e, &offset, &bytes))) {
839 ret = btrfs_add_free_space(ctl, offset,
853 if (prev->offset + prev->bytes == e->offset) {
854 unlink_free_space(ctl, prev);
855 unlink_free_space(ctl, e);
856 prev->bytes += e->bytes;
858 link_free_space(ctl, prev);