1 files changed, 57 insertions, 22 deletions

diff --git a/fs/btrfs/inode.c b/fs/btrfs/inode.c
index 3c16a1493e22..b1106d0dcd5c 100644
--- a/fs/btrfs/inode.c
+++ b/fs/btrfs/inode.c
@@ -6249,21 +6249,60 @@ out_fail_inode:
         goto out_fail;
 }
 
+/* Find next extent map of a given extent map, caller needs to ensure locks */
+static struct extent_map *next_extent_map(struct extent_map *em)
+{
+        struct rb_node *next;
+
+        next = rb_next(&em->rb_node);
+        if (!next)
+                return NULL;
+        return container_of(next, struct extent_map, rb_node);
+}
+
+static struct extent_map *prev_extent_map(struct extent_map *em)
+{
+        struct rb_node *prev;
+
+        prev = rb_prev(&em->rb_node);
+        if (!prev)
+                return NULL;
+        return container_of(prev, struct extent_map, rb_node);
+}
+
 /* helper for btfs_get_extent.  Given an existing extent in the tree,
+ * the existing extent is the nearest extent to map_start,
  * and an extent that you want to insert, deal with overlap and insert
- * the new extent into the tree.
+ * the best fitted new extent into the tree.
  */
 static int merge_extent_mapping(struct extent_map_tree *em_tree,
                                 struct extent_map *existing,
                                 struct extent_map *em,
                                 u64 map_start)
 {
+        struct extent_map *prev;
+        struct extent_map *next;
+        u64 start;
+        u64 end;
         u64 start_diff;
 
         BUG_ON(map_start < em->start || map_start >= extent_map_end(em));
-        start_diff = map_start - em->start;
-        em->start = map_start;
-        em->len = existing->start - em->start;
+
+        if (existing->start > map_start) {
+                next = existing;
+                prev = prev_extent_map(next);
+        } else {
+                prev = existing;
+                next = next_extent_map(prev);
+        }
+
+        start = prev ? extent_map_end(prev) : em->start;
+        start = max_t(u64, start, em->start);
+        end = next ? next->start : extent_map_end(em);
+        end = min_t(u64, end, extent_map_end(em));
+        start_diff = start - em->start;
+        em->start = start;
+        em->len = end - start;
         if (em->block_start < EXTENT_MAP_LAST_BYTE &&
             !test_bit(EXTENT_FLAG_COMPRESSED, &em->flags)) {
                 em->block_start += start_diff;
@@ -6540,25 +6579,21 @@ insert:
 
                 ret = 0;
 
-                existing = lookup_extent_mapping(em_tree, start, len);
-                if (existing && (existing->start > start ||
-                    existing->start + existing->len <= start)) {
+                existing = search_extent_mapping(em_tree, start, len);
+                /*
+                 * existing will always be non-NULL, since there must be
+                 * extent causing the -EEXIST.
+                 */
+                if (start >= extent_map_end(existing) ||
+                    start + len <= existing->start) {
+                        /*
+                         * The existing extent map is the one nearest to
+                         * the [start, start + len) range which overlaps
+                         */
+                        err = merge_extent_mapping(em_tree, existing,
+                                                   em, start);
                         free_extent_map(existing);
-                        existing = NULL;
-                }
-                if (!existing) {
-                        existing = lookup_extent_mapping(em_tree, em->start,
-                                                         em->len);
-                        if (existing) {
-                                err = merge_extent_mapping(em_tree, existing,
-                                                           em, start);
-                                free_extent_map(existing);
-                                if (err) {
-                                        free_extent_map(em);
-                                        em = NULL;
-                                }
-                        } else {
-                                err = -EIO;
+                        if (err) {
                                 free_extent_map(em);
                                 em = NULL;
                         }