Merge branch 'master' into usb-next

We have USB fixes now in Linus's tree that we need to properly sort out
with reverts and the like in the usb-next branch, so merge them together
and do it by hand.

Signed-off-by: Greg Kroah-Hartman <gregkh@linuxfoundation.org>

1 files changed, 47 insertions, 20 deletions

diff --git a/fs/btrfs/free-space-cache.c b/fs/btrfs/free-space-cache.c
index 3f0ddfce96e6..b4f9904c4c6b 100644
--- a/fs/btrfs/free-space-cache.c
+++ b/fs/btrfs/free-space-cache.c
@@ -1431,13 +1431,19 @@ static void bitmap_set_bits(struct btrfs_free_space_ctl *ctl,
         ctl->free_space += bytes;
 }
 
+/*
+ * If we can not find suitable extent, we will use bytes to record
+ * the size of the max extent.
+ */
 static int search_bitmap(struct btrfs_free_space_ctl *ctl,
                          struct btrfs_free_space *bitmap_info, u64 *offset,
                          u64 *bytes)
 {
         unsigned long found_bits = 0;
+        unsigned long max_bits = 0;
         unsigned long bits, i;
         unsigned long next_zero;
+        unsigned long extent_bits;
 
         i = offset_to_bit(bitmap_info->offset, ctl->unit,
                           max_t(u64, *offset, bitmap_info->offset));
@@ -1446,9 +1452,12 @@ static int search_bitmap(struct btrfs_free_space_ctl *ctl,
         for_each_set_bit_from(i, bitmap_info->bitmap, BITS_PER_BITMAP) {
                 next_zero = find_next_zero_bit(bitmap_info->bitmap,
                                                BITS_PER_BITMAP, i);
-                if ((next_zero - i) >= bits) {
-                        found_bits = next_zero - i;
+                extent_bits = next_zero - i;
+                if (extent_bits >= bits) {
+                        found_bits = extent_bits;
                         break;
+                } else if (extent_bits > max_bits) {
+                        max_bits = extent_bits;
                 }
                 i = next_zero;
         }
@@ -1459,38 +1468,41 @@ static int search_bitmap(struct btrfs_free_space_ctl *ctl,
                 return 0;
         }
 
+        *bytes = (u64)(max_bits) * ctl->unit;
         return -1;
 }
 
+/* Cache the size of the max extent in bytes */
 static struct btrfs_free_space *
 find_free_space(struct btrfs_free_space_ctl *ctl, u64 *offset, u64 *bytes,
-                unsigned long align)
+                unsigned long align, u64 *max_extent_size)
 {
         struct btrfs_free_space *entry;
         struct rb_node *node;
-        u64 ctl_off;
         u64 tmp;
         u64 align_off;
         int ret;
 
         if (!ctl->free_space_offset.rb_node)
-                return NULL;
+                goto out;
 
         entry = tree_search_offset(ctl, offset_to_bitmap(ctl, *offset), 0, 1);
         if (!entry)
-                return NULL;
+                goto out;
 
         for (node = &entry->offset_index; node; node = rb_next(node)) {
                 entry = rb_entry(node, struct btrfs_free_space, offset_index);
-                if (entry->bytes < *bytes)
+                if (entry->bytes < *bytes) {
+                        if (entry->bytes > *max_extent_size)
+                                *max_extent_size = entry->bytes;
                         continue;
+                }
 
                 /* make sure the space returned is big enough
                  * to match our requested alignment
                  */
                 if (*bytes >= align) {
-                        ctl_off = entry->offset - ctl->start;
-                        tmp = ctl_off + align - 1;;
+                        tmp = entry->offset - ctl->start + align - 1;
                         do_div(tmp, align);
                         tmp = tmp * align + ctl->start;
                         align_off = tmp - entry->offset;
@@ -1499,14 +1511,22 @@ find_free_space(struct btrfs_free_space_ctl *ctl, u64 *offset, u64 *bytes,
                         tmp = entry->offset;
                 }
 
-                if (entry->bytes < *bytes + align_off)
+                if (entry->bytes < *bytes + align_off) {
+                        if (entry->bytes > *max_extent_size)
+                                *max_extent_size = entry->bytes;
                         continue;
+                }
 
                 if (entry->bitmap) {
-                        ret = search_bitmap(ctl, entry, &tmp, bytes);
+                        u64 size = *bytes;
+
+                        ret = search_bitmap(ctl, entry, &tmp, &size);
                         if (!ret) {
                                 *offset = tmp;
+                                *bytes = size;
                                 return entry;
+                        } else if (size > *max_extent_size) {
+                                *max_extent_size = size;
                         }
                         continue;
                 }
@@ -1515,7 +1535,7 @@ find_free_space(struct btrfs_free_space_ctl *ctl, u64 *offset, u64 *bytes,
                 *bytes = entry->bytes - align_off;
                 return entry;
         }
-
+out:
         return NULL;
 }
 
@@ -2116,7 +2136,8 @@ void btrfs_remove_free_space_cache(struct btrfs_block_group_cache *block_group)
 }
 
 u64 btrfs_find_space_for_alloc(struct btrfs_block_group_cache *block_group,
-                               u64 offset, u64 bytes, u64 empty_size)
+                               u64 offset, u64 bytes, u64 empty_size,
+                               u64 *max_extent_size)
 {
         struct btrfs_free_space_ctl *ctl = block_group->free_space_ctl;
         struct btrfs_free_space *entry = NULL;
@@ -2127,7 +2148,7 @@ u64 btrfs_find_space_for_alloc(struct btrfs_block_group_cache *block_group,
 
         spin_lock(&ctl->tree_lock);
         entry = find_free_space(ctl, &offset, &bytes_search,
-                                block_group->full_stripe_len);
+                                block_group->full_stripe_len, max_extent_size);
         if (!entry)
                 goto out;
 
@@ -2137,7 +2158,6 @@ u64 btrfs_find_space_for_alloc(struct btrfs_block_group_cache *block_group,
                 if (!entry->bytes)
                         free_bitmap(ctl, entry);
         } else {
-
                 unlink_free_space(ctl, entry);
                 align_gap_len = offset - entry->offset;
                 align_gap = entry->offset;
@@ -2151,7 +2171,6 @@ u64 btrfs_find_space_for_alloc(struct btrfs_block_group_cache *block_group,
                 else
                         link_free_space(ctl, entry);
         }
-
 out:
         spin_unlock(&ctl->tree_lock);
 
@@ -2206,7 +2225,8 @@ int btrfs_return_cluster_to_free_space(
 static u64 btrfs_alloc_from_bitmap(struct btrfs_block_group_cache *block_group,
                                    struct btrfs_free_cluster *cluster,
                                    struct btrfs_free_space *entry,
-                                   u64 bytes, u64 min_start)
+                                   u64 bytes, u64 min_start,
+                                   u64 *max_extent_size)
 {
         struct btrfs_free_space_ctl *ctl = block_group->free_space_ctl;
         int err;
@@ -2218,8 +2238,11 @@ static u64 btrfs_alloc_from_bitmap(struct btrfs_block_group_cache *block_group,
         search_bytes = bytes;
 
         err = search_bitmap(ctl, entry, &search_start, &search_bytes);
-        if (err)
+        if (err) {
+                if (search_bytes > *max_extent_size)
+                        *max_extent_size = search_bytes;
                 return 0;
+        }
 
         ret = search_start;
         __bitmap_clear_bits(ctl, entry, ret, bytes);
@@ -2234,7 +2257,7 @@ static u64 btrfs_alloc_from_bitmap(struct btrfs_block_group_cache *block_group,
  */
 u64 btrfs_alloc_from_cluster(struct btrfs_block_group_cache *block_group,
                              struct btrfs_free_cluster *cluster, u64 bytes,
-                             u64 min_start)
+                             u64 min_start, u64 *max_extent_size)
 {
         struct btrfs_free_space_ctl *ctl = block_group->free_space_ctl;
         struct btrfs_free_space *entry = NULL;
@@ -2254,6 +2277,9 @@ u64 btrfs_alloc_from_cluster(struct btrfs_block_group_cache *block_group,
 
         entry = rb_entry(node, struct btrfs_free_space, offset_index);
         while(1) {
+                if (entry->bytes < bytes && entry->bytes > *max_extent_size)
+                        *max_extent_size = entry->bytes;
+
                 if (entry->bytes < bytes ||
                     (!entry->bitmap && entry->offset < min_start)) {
                         node = rb_next(&entry->offset_index);
@@ -2267,7 +2293,8 @@ u64 btrfs_alloc_from_cluster(struct btrfs_block_group_cache *block_group,
                 if (entry->bitmap) {
                         ret = btrfs_alloc_from_bitmap(block_group,
                                                       cluster, entry, bytes,
-                                                      cluster->window_start);
+                                                      cluster->window_start,
+                                                      max_extent_size);
                         if (ret == 0) {
                                 node = rb_next(&entry->offset_index);
                                 if (!node)