[PATCH] fs/ntfs3: merge overlapping free extents in wnd_add_free_ext()

[PATCH] fs/ntfs3: merge overlapping free extents in wnd_add_free_ext()

[Wahid Khan]

wnd_set_free() clears the bits and then adds the range to the tree of
free extents, without looking at what the tree already holds. When the
range overlaps a free extent, which is what freeing clusters that are
free already comes to on a damaged $Bitmap, wnd_add_free_ext() does not
merge them: the left neighbor is taken only if it ends exactly at the
start of the new range. A new extent with the start of an existing one
is then inserted, rb_insert_start() warns about the duplicate key, and
the tree is left with overlapping extents.

  WARNING: fs/ntfs3/bitmap.c:217 at wnd_add_free_ext+0xb61/0xdd0
  Call Trace:
   wnd_set_free

Another way to get there is the scan of the bitmap that follows the
merge. It widens the range over free bits that belong to extents of the
tree, and those are not merged any more. The right side has a similar
problem: for a neighbor that ends inside the new range,
"len += next_end - end_in" shrinks the length, and end_in is moved back.

Take the extents that touch or overlap the range out of the tree in one
helper, keep the larger of the ends, and run it again if the scan of the
bitmap widened the range.

Reported-by: syzbot+323f07d372f692a127b3@syzkaller.appspotmail.com
Closes: https://syzkaller.appspot.com/bug?extid=323f07d372f692a127b3
Fixes: 4342306f0f0d ("fs/ntfs3: Add file operations and implementation")
Signed-off-by: Wahid Khan <wahidzk0091@gmail.com>
---
 fs/ntfs3/bitmap.c | 116 ++++++++++++++++++++++++++++------------------
 1 file changed, 70 insertions(+), 46 deletions(-)

diff --git a/fs/ntfs3/bitmap.c b/fs/ntfs3/bitmap.c
index 60b362f388d9..7ee0067a3421 100644
--- a/fs/ntfs3/bitmap.c
+++ b/fs/ntfs3/bitmap.c
@@ -224,6 +224,66 @@ static inline bool rb_insert_start(struct rb_root *root, struct e_node *e)
 	return true;
 }
 
+/*
+ * wnd_merge_free_ext - Take the extents that touch or overlap [*bit, *end_in)
+ * out of the trees and widen the range to cover them.
+ *
+ * The first extent removed is returned in @e0 for reuse, the others are freed.
+ */
+static void wnd_merge_free_ext(struct wnd_bitmap *wnd, size_t *bit,
+			       size_t *end_in, struct e_node **e0)
+{
+	struct rb_node *n = rb_lookup(&wnd->start_tree, *bit);
+	struct e_node *e;
+
+	if (!n) {
+		n = rb_first(&wnd->start_tree);
+	} else {
+		size_t e_end;
+
+		e = rb_entry(n, struct e_node, start.node);
+		n = rb_next(n);
+		e_end = e->start.key + e->count.key;
+		if (e_end < *bit)
+			goto right;
+
+		/* Remove left. */
+		if (e_end > *end_in)
+			*end_in = e_end;
+		*bit = e->start.key;
+		rb_erase(&e->start.node, &wnd->start_tree);
+		rb_erase(&e->count.node, &wnd->count_tree);
+		wnd->count -= 1;
+		if (!*e0)
+			*e0 = e;
+		else
+			kmem_cache_free(ntfs_enode_cachep, e);
+	}
+
+right:
+	while (n) {
+		size_t next_end;
+
+		e = rb_entry(n, struct e_node, start.node);
+		if (e->start.key > *end_in)
+			break;
+
+		/* Remove right. */
+		next_end = e->start.key + e->count.key;
+		n = rb_next(n);
+		if (next_end > *end_in)
+			*end_in = next_end;
+		rb_erase(&e->start.node, &wnd->start_tree);
+		rb_erase(&e->count.node, &wnd->count_tree);
+		wnd->count -= 1;
+
+		if (!*e0)
+			*e0 = e;
+		else
+			kmem_cache_free(ntfs_enode_cachep, e);
+	}
+}
+
 /*
  * wnd_add_free_ext - Adds a new extent of free space.
  * @build:	1 when building tree.
@@ -243,58 +303,19 @@ static void wnd_add_free_ext(struct wnd_bitmap *wnd, size_t bit, size_t len,
 			return;
 		}
 	} else {
-		/* Try to find extent before 'bit'. */
-		n = rb_lookup(&wnd->start_tree, bit);
-
-		if (!n) {
-			n = rb_first(&wnd->start_tree);
-		} else {
-			e = rb_entry(n, struct e_node, start.node);
-			n = rb_next(n);
-			if (e->start.key + e->count.key == bit) {
-				/* Remove left. */
-				bit = e->start.key;
-				len += e->count.key;
-				rb_erase(&e->start.node, &wnd->start_tree);
-				rb_erase(&e->count.node, &wnd->count_tree);
-				wnd->count -= 1;
-				e0 = e;
-			}
-		}
-
-		while (n) {
-			size_t next_end;
-
-			e = rb_entry(n, struct e_node, start.node);
-			next_end = e->start.key + e->count.key;
-			if (e->start.key > end_in)
-				break;
-
-			/* Remove right. */
-			n = rb_next(n);
-			len += next_end - end_in;
-			end_in = next_end;
-			rb_erase(&e->start.node, &wnd->start_tree);
-			rb_erase(&e->count.node, &wnd->count_tree);
-			wnd->count -= 1;
-
-			if (!e0)
-				e0 = e;
-			else
-				kmem_cache_free(ntfs_enode_cachep, e);
-		}
+		wnd_merge_free_ext(wnd, &bit, &end_in, &e0);
 
 		if (wnd->uptodated != 1) {
+			size_t old_bit = bit, old_end = end_in;
+
 			/* Check bits before 'bit'. */
 			ib = wnd->zone_bit == wnd->zone_end ||
 					     bit < wnd->zone_end ?
 				     0 :
 				     wnd->zone_end;
 
-			while (bit > ib && wnd_is_free_hlp(wnd, bit - 1, 1)) {
+			while (bit > ib && wnd_is_free_hlp(wnd, bit - 1, 1))
 				bit -= 1;
-				len += 1;
-			}
 
 			/* Check bits after 'end_in'. */
 			ib = wnd->zone_bit == wnd->zone_end ||
@@ -302,11 +323,14 @@ static void wnd_add_free_ext(struct wnd_bitmap *wnd, size_t bit, size_t len,
 				     wnd->nbits :
 				     wnd->zone_bit;
 
-			while (end_in < ib && wnd_is_free_hlp(wnd, end_in, 1)) {
+			while (end_in < ib && wnd_is_free_hlp(wnd, end_in, 1))
 				end_in += 1;
-				len += 1;
-			}
+
+			/* The free bits can belong to extents of the tree. */
+			if (bit != old_bit || end_in != old_end)
+				wnd_merge_free_ext(wnd, &bit, &end_in, &e0);
 		}
+		len = end_in - bit;
 	}
 	/* Insert new fragment. */
 	if (wnd->count >= NTFS_MAX_WND_EXTENTS) {
-- 
2.56.0