aboutsummaryrefslogtreecommitdiffstats
path: root/fs/btrfs/volumes.c
diff options
context:
space:
mode:
Diffstat (limited to 'fs/btrfs/volumes.c')
-rw-r--r--fs/btrfs/volumes.c155
1 files changed, 89 insertions, 66 deletions
diff --git a/fs/btrfs/volumes.c b/fs/btrfs/volumes.c
index c50a85e0d08f..4838bd395e49 100644
--- a/fs/btrfs/volumes.c
+++ b/fs/btrfs/volumes.c
@@ -729,58 +729,82 @@ error:
729} 729}
730 730
731/* 731/*
732 * find_free_dev_extent - find free space in the specified device
733 * @trans: transaction handler
734 * @device: the device which we search the free space in
735 * @num_bytes: the size of the free space that we need
736 * @start: store the start of the free space.
737 * @len: the size of the free space. that we find, or the size of the max
738 * free space if we don't find suitable free space
739 *
732 * this uses a pretty simple search, the expectation is that it is 740 * this uses a pretty simple search, the expectation is that it is
733 * called very infrequently and that a given device has a small number 741 * called very infrequently and that a given device has a small number
734 * of extents 742 * of extents
743 *
744 * @start is used to store the start of the free space if we find. But if we
745 * don't find suitable free space, it will be used to store the start position
746 * of the max free space.
747 *
748 * @len is used to store the size of the free space that we find.
749 * But if we don't find suitable free space, it is used to store the size of
750 * the max free space.
735 */ 751 */
736int find_free_dev_extent(struct btrfs_trans_handle *trans, 752int find_free_dev_extent(struct btrfs_trans_handle *trans,
737 struct btrfs_device *device, u64 num_bytes, 753 struct btrfs_device *device, u64 num_bytes,
738 u64 *start, u64 *max_avail) 754 u64 *start, u64 *len)
739{ 755{
740 struct btrfs_key key; 756 struct btrfs_key key;
741 struct btrfs_root *root = device->dev_root; 757 struct btrfs_root *root = device->dev_root;
742 struct btrfs_dev_extent *dev_extent = NULL; 758 struct btrfs_dev_extent *dev_extent;
743 struct btrfs_path *path; 759 struct btrfs_path *path;
744 u64 hole_size = 0; 760 u64 hole_size;
745 u64 last_byte = 0; 761 u64 max_hole_start;
746 u64 search_start = 0; 762 u64 max_hole_size;
763 u64 extent_end;
764 u64 search_start;
747 u64 search_end = device->total_bytes; 765 u64 search_end = device->total_bytes;
748 int ret; 766 int ret;
749 int slot = 0; 767 int slot;
750 int start_found;
751 struct extent_buffer *l; 768 struct extent_buffer *l;
752 769
753 path = btrfs_alloc_path();
754 if (!path)
755 return -ENOMEM;
756 path->reada = 2;
757 start_found = 0;
758
759 /* FIXME use last free of some kind */ 770 /* FIXME use last free of some kind */
760 771
761 /* we don't want to overwrite the superblock on the drive, 772 /* we don't want to overwrite the superblock on the drive,
762 * so we make sure to start at an offset of at least 1MB 773 * so we make sure to start at an offset of at least 1MB
763 */ 774 */
764 search_start = max((u64)1024 * 1024, search_start); 775 search_start = 1024 * 1024;
765 776
766 if (root->fs_info->alloc_start + num_bytes <= device->total_bytes) 777 if (root->fs_info->alloc_start + num_bytes <= search_end)
767 search_start = max(root->fs_info->alloc_start, search_start); 778 search_start = max(root->fs_info->alloc_start, search_start);
768 779
780 max_hole_start = search_start;
781 max_hole_size = 0;
782
783 if (search_start >= search_end) {
784 ret = -ENOSPC;
785 goto error;
786 }
787
788 path = btrfs_alloc_path();
789 if (!path) {
790 ret = -ENOMEM;
791 goto error;
792 }
793 path->reada = 2;
794
769 key.objectid = device->devid; 795 key.objectid = device->devid;
770 key.offset = search_start; 796 key.offset = search_start;
771 key.type = BTRFS_DEV_EXTENT_KEY; 797 key.type = BTRFS_DEV_EXTENT_KEY;
798
772 ret = btrfs_search_slot(trans, root, &key, path, 0, 0); 799 ret = btrfs_search_slot(trans, root, &key, path, 0, 0);
773 if (ret < 0) 800 if (ret < 0)
774 goto error; 801 goto out;
775 if (ret > 0) { 802 if (ret > 0) {
776 ret = btrfs_previous_item(root, path, key.objectid, key.type); 803 ret = btrfs_previous_item(root, path, key.objectid, key.type);
777 if (ret < 0) 804 if (ret < 0)
778 goto error; 805 goto out;
779 if (ret > 0)
780 start_found = 1;
781 } 806 }
782 l = path->nodes[0]; 807
783 btrfs_item_key_to_cpu(l, &key, path->slots[0]);
784 while (1) { 808 while (1) {
785 l = path->nodes[0]; 809 l = path->nodes[0];
786 slot = path->slots[0]; 810 slot = path->slots[0];
@@ -789,24 +813,9 @@ int find_free_dev_extent(struct btrfs_trans_handle *trans,
789 if (ret == 0) 813 if (ret == 0)
790 continue; 814 continue;
791 if (ret < 0) 815 if (ret < 0)
792 goto error; 816 goto out;
793no_more_items: 817
794 if (!start_found) { 818 break;
795 if (search_start >= search_end) {
796 ret = -ENOSPC;
797 goto error;
798 }
799 *start = search_start;
800 start_found = 1;
801 goto check_pending;
802 }
803 *start = last_byte > search_start ?
804 last_byte : search_start;
805 if (search_end <= *start) {
806 ret = -ENOSPC;
807 goto error;
808 }
809 goto check_pending;
810 } 819 }
811 btrfs_item_key_to_cpu(l, &key, slot); 820 btrfs_item_key_to_cpu(l, &key, slot);
812 821
@@ -814,48 +823,62 @@ no_more_items:
814 goto next; 823 goto next;
815 824
816 if (key.objectid > device->devid) 825 if (key.objectid > device->devid)
817 goto no_more_items; 826 break;
818 827
819 if (key.offset >= search_start && key.offset > last_byte && 828 if (btrfs_key_type(&key) != BTRFS_DEV_EXTENT_KEY)
820 start_found) { 829 goto next;
821 if (last_byte < search_start)
822 last_byte = search_start;
823 hole_size = key.offset - last_byte;
824 830
825 if (hole_size > *max_avail) 831 if (key.offset > search_start) {
826 *max_avail = hole_size; 832 hole_size = key.offset - search_start;
827 833
828 if (key.offset > last_byte && 834 if (hole_size > max_hole_size) {
829 hole_size >= num_bytes) { 835 max_hole_start = search_start;
830 *start = last_byte; 836 max_hole_size = hole_size;
831 goto check_pending; 837 }
838
839 /*
840 * If this free space is greater than which we need,
841 * it must be the max free space that we have found
842 * until now, so max_hole_start must point to the start
843 * of this free space and the length of this free space
844 * is stored in max_hole_size. Thus, we return
845 * max_hole_start and max_hole_size and go back to the
846 * caller.
847 */
848 if (hole_size >= num_bytes) {
849 ret = 0;
850 goto out;
832 } 851 }
833 } 852 }
834 if (btrfs_key_type(&key) != BTRFS_DEV_EXTENT_KEY)
835 goto next;
836 853
837 start_found = 1;
838 dev_extent = btrfs_item_ptr(l, slot, struct btrfs_dev_extent); 854 dev_extent = btrfs_item_ptr(l, slot, struct btrfs_dev_extent);
839 last_byte = key.offset + btrfs_dev_extent_length(l, dev_extent); 855 extent_end = key.offset + btrfs_dev_extent_length(l,
856 dev_extent);
857 if (extent_end > search_start)
858 search_start = extent_end;
840next: 859next:
841 path->slots[0]++; 860 path->slots[0]++;
842 cond_resched(); 861 cond_resched();
843 } 862 }
844check_pending:
845 /* we have to make sure we didn't find an extent that has already
846 * been allocated by the map tree or the original allocation
847 */
848 BUG_ON(*start < search_start);
849 863
850 if (*start + num_bytes > search_end) { 864 hole_size = search_end- search_start;
851 ret = -ENOSPC; 865 if (hole_size > max_hole_size) {
852 goto error; 866 max_hole_start = search_start;
867 max_hole_size = hole_size;
853 } 868 }
854 /* check for pending inserts here */
855 ret = 0;
856 869
857error: 870 /* See above. */
871 if (hole_size < num_bytes)
872 ret = -ENOSPC;
873 else
874 ret = 0;
875
876out:
858 btrfs_free_path(path); 877 btrfs_free_path(path);
878error:
879 *start = max_hole_start;
880 if (len && max_hole_size > *len)
881 *len = max_hole_size;
859 return ret; 882 return ret;
860} 883}
861 884