Ocfs2 devel - Apr 2023 - [PATCH] ocfs2: Fix wrong search logic in __ocfs2_resv_find_window

** problem **

Current code triggers a defragfs bug [1]:

```
tw-tst:~ # defragfs.ocfs2 /mnt/test_from_dd1
defragfs.ocfs2 1.8.7
[ERROR]Move extent failed:"/mnt/test_from_dd1" - No space left on
device
[ERROR]"/mnt/test_from_dd1":No space left on device
```

I added some debug messages in relevant functions. When above error
messages appeared, the la-window still had enough continuous bitmap
to use, the -ENOSPC is wrong.

** analysis **

__ocfs2_resv_find_window should use resv node from rb-tree to do linear
search. But current code logic uses un-managered area between two resvs.
The searching logic deviates from this func job, which should only focus
on reservation areas (when rb_root is non NULL). Another issue of
__ocfs2_resv_find_window is more inclined to generate inner fragment.
It doesn't search & consume existing reservations but be apt to create
new reservation item.

This patch pulls this func (__ocfs2_resv_find_window) to do what it
should do: search & consume resev. if this func fails to get suitable
bitmap area, caller ocfs2_resv_find_window fallbacks to use oldest
resv from LRU to do the final search.

[1]: https://bugzilla.suse.com/show_bug.cgi?id=1131931

Signed-off-by: Heming Zhao <heming.zhao at suse.com>
---
 fs/ocfs2/reservations.c | 48 +++++++++++++++++++++++++++++------------
 1 file changed, 34 insertions(+), 14 deletions(-)

diff --git a/fs/ocfs2/reservations.c b/fs/ocfs2/reservations.c
index a9d1296d736d..eda672622d1d 100644
--- a/fs/ocfs2/reservations.c
+++ b/fs/ocfs2/reservations.c
@@ -458,10 +458,11 @@ static void __ocfs2_resv_find_window(struct
ocfs2_reservation_map *resmap,
 {
 	struct rb_root *root = &resmap->m_reservations;
 	unsigned int gap_start, gap_end, gap_len;
-	struct ocfs2_alloc_reservation *prev_resv, *next_resv;
+	struct ocfs2_alloc_reservation *prev_resv, *next_resv, *best_resv;
 	struct rb_node *prev, *next;
 	unsigned int cstart, clen;
 	unsigned int best_start = 0, best_len = 0;
+	int create_new = 0;
 
 	/*
 	 * Nasty cases to consider:
@@ -540,8 +541,9 @@ static void __ocfs2_resv_find_window(struct
ocfs2_reservation_map *resmap,
 		if (clen) {
 			best_len = clen;
 			best_start = cstart;
+			create_new = 1;
 			if (best_len == wanted)
-				goto out_insert;
+				goto out_create;
 		}
 
 		prev_resv = next_resv;
@@ -557,13 +559,9 @@ static void __ocfs2_resv_find_window(struct
ocfs2_reservation_map *resmap,
 	while (1) {
 		next = rb_next(prev);
 		if (next) {
-			next_resv = rb_entry(next,
-					     struct ocfs2_alloc_reservation,
-					     r_node);
-
-			gap_start = ocfs2_resv_end(prev_resv) + 1;
-			gap_end = next_resv->r_start - 1;
-			gap_len = gap_end - gap_start + 1;
+			gap_start = prev_resv->r_start;
+			gap_end = prev_resv->r_start + prev_resv->r_len - 1;
+			gap_len = prev_resv->r_len;
 		} else {
 			/*
 			 * We're at the rightmost edge of the
@@ -575,8 +573,8 @@ static void __ocfs2_resv_find_window(struct
ocfs2_reservation_map *resmap,
 			gap_end = resmap->m_bitmap_len - 1;
 		}
 
-		trace_ocfs2_resv_find_window_next(next ? next_resv->r_start: -1,
-					next ? ocfs2_resv_end(next_resv) : -1);
+		trace_ocfs2_resv_find_window_next(next ? prev_resv->r_start : -1,
+					next ? ocfs2_resv_end(prev_resv) : -1);
 		/*
 		 * No need to check this gap if we have already found
 		 * a larger region of free bits.
@@ -589,10 +587,16 @@ static void __ocfs2_resv_find_window(struct
ocfs2_reservation_map *resmap,
 		if (clen == wanted) {
 			best_len = clen;
 			best_start = cstart;
-			goto out_insert;
+			best_resv = prev_resv;
+			if (!next)
+				goto out_create;
+			else
+				goto out_insert;
 		} else if (clen > best_len) {
 			best_len = clen;
 			best_start = cstart;
+			best_resv = prev_resv;
+			create_new = 0;
 		}
 
 next_resv:
@@ -604,12 +608,28 @@ static void __ocfs2_resv_find_window(struct
ocfs2_reservation_map *resmap,
 				     r_node);
 	}
 
-out_insert:
-	if (best_len) {
+	if (!best_len)
+		return;
+
+	if (create_new) {
+out_create:
 		resv->r_start = best_start;
 		resv->r_len = best_len;
 		ocfs2_resv_insert(resmap, resv);
+		return;
 	}
+
+out_insert:
+	if (best_resv->r_len <= wanted) {
+		resv->r_start = best_start;
+		resv->r_len = best_len;
+		__ocfs2_resv_discard(resmap, best_resv);
+	} else {
+		best_resv->r_len -= best_len;
+		resv->r_start = ocfs2_resv_end(best_resv) + 1;
+		resv->r_len = best_len;
+	}
+	ocfs2_resv_insert(resmap, resv);
 }
 
 static void ocfs2_cannibalize_resv(struct ocfs2_reservation_map *resmap,
-- 
2.26.2

Hello Joseph,

On Thu, Apr 06, 2023 at 11:40:52PM +0800, Heming Zhao
wrote:
> ** problem **
> 
> Current code triggers a defragfs bug [1]:
> 
> ```
> tw-tst:~ # defragfs.ocfs2 /mnt/test_from_dd1
> defragfs.ocfs2 1.8.7
> [ERROR]Move extent failed:"/mnt/test_from_dd1" - No space left on
device
> [ERROR]"/mnt/test_from_dd1":No space left on device
> ```
> 
> I added some debug messages in relevant functions. When above error
> messages appeared, the la-window still had enough continuous bitmap
> to use, the -ENOSPC is wrong.
> 
There is another problem with la-window alloc flow, and also should have a
patch.
When reservatioins are disabled, ocfs2_local_alloc_find_clear_bits starts linear
search, and returns 'bitoff:-1' if 'numfound < *numbits'. In
my view, this code
logic is wrong, in this case, it should return max suitable numfound.

The pseudo code:

```
diff -Nupr a/localalloc.c b/localalloc.c
--- a/localalloc.c	2023-04-07 23:33:42.077083405 +0800
+++ b/localalloc.c	2023-04-07 23:35:10.756344502 +0800
@@ -835,6 +835,7 @@ static int ocfs2_local_alloc_find_clear_
 				     struct ocfs2_alloc_reservation *resv)
 {
 	int numfound = 0, bitoff, left, startoff;
+	unsigned int best_start, best_len = 0;
 	int local_resv = 0;
 	struct ocfs2_alloc_reservation r;
 	void *bitmap = NULL;
@@ -940,6 +941,10 @@ static int ocfs2_local_alloc_find_clear_
 			numfound = 1;
 			startoff = bitoff+1;
 		}
+		if (numfound > best_len) {
+			best_len = numfound;
+			best_start = startoff - numfound;
+		}
 		/* we got everything we needed */
 		if (numfound == *numbits) {
 			/* mlog(0, "Found it all!\n"); */
@@ -949,10 +954,12 @@ static int ocfs2_local_alloc_find_clear_
 
 	trace_ocfs2_local_alloc_find_clear_bits_search_bitmap(bitoff, numfound);
 
-	if (numfound == *numbits)
-		bitoff = startoff - numfound;
-	else
+	if (best_len = 0) {
 		bitoff = -1;
+	} else {
+		bitoff = best_start;
+		*numbits = best_len;
+	}
 
 bail:
 	if (local_resv)
```

If you agree with my thinking, I will test & file a formal patch.

Thanks,
Heming

Sorry for the late replay since I was busy with other projects these
days. Will take a look at this patch this weekend.

Thanks,
Joseph

On 4/6/23 11:40 PM, Heming Zhao wrote:
> ** problem **
> 
> Current code triggers a defragfs bug [1]:
> 
> ```
> tw-tst:~ # defragfs.ocfs2 /mnt/test_from_dd1
> defragfs.ocfs2 1.8.7
> [ERROR]Move extent failed:"/mnt/test_from_dd1" - No space left on
device
> [ERROR]"/mnt/test_from_dd1":No space left on device
> ```
> 
> I added some debug messages in relevant functions. When above error
> messages appeared, the la-window still had enough continuous bitmap
> to use, the -ENOSPC is wrong.
> 
> ** analysis **
> 
> __ocfs2_resv_find_window should use resv node from rb-tree to do linear
> search. But current code logic uses un-managered area between two resvs.
> The searching logic deviates from this func job, which should only focus
> on reservation areas (when rb_root is non NULL). Another issue of
> __ocfs2_resv_find_window is more inclined to generate inner fragment.
> It doesn't search & consume existing reservations but be apt to
create
> new reservation item.
> 
> This patch pulls this func (__ocfs2_resv_find_window) to do what it
> should do: search & consume resev. if this func fails to get suitable
> bitmap area, caller ocfs2_resv_find_window fallbacks to use oldest
> resv from LRU to do the final search.
> 
> [1]: https://bugzilla.suse.com/show_bug.cgi?id=1131931
> 
> Signed-off-by: Heming Zhao <heming.zhao at suse.com>
> ---
>  fs/ocfs2/reservations.c | 48 +++++++++++++++++++++++++++++------------
>  1 file changed, 34 insertions(+), 14 deletions(-)
> 
> diff --git a/fs/ocfs2/reservations.c b/fs/ocfs2/reservations.c
> index a9d1296d736d..eda672622d1d 100644
> --- a/fs/ocfs2/reservations.c
> +++ b/fs/ocfs2/reservations.c
> @@ -458,10 +458,11 @@ static void __ocfs2_resv_find_window(struct
ocfs2_reservation_map *resmap,
>  {
>  	struct rb_root *root = &resmap->m_reservations;
>  	unsigned int gap_start, gap_end, gap_len;
> -	struct ocfs2_alloc_reservation *prev_resv, *next_resv;
> +	struct ocfs2_alloc_reservation *prev_resv, *next_resv, *best_resv;
>  	struct rb_node *prev, *next;
>  	unsigned int cstart, clen;
>  	unsigned int best_start = 0, best_len = 0;
> +	int create_new = 0;
>  
>  	/*
>  	 * Nasty cases to consider:
> @@ -540,8 +541,9 @@ static void __ocfs2_resv_find_window(struct
ocfs2_reservation_map *resmap,
>  		if (clen) {
>  			best_len = clen;
>  			best_start = cstart;
> +			create_new = 1;
>  			if (best_len == wanted)
> -				goto out_insert;
> +				goto out_create;
>  		}
>  
>  		prev_resv = next_resv;
> @@ -557,13 +559,9 @@ static void __ocfs2_resv_find_window(struct
ocfs2_reservation_map *resmap,
>  	while (1) {
>  		next = rb_next(prev);
>  		if (next) {
> -			next_resv = rb_entry(next,
> -					     struct ocfs2_alloc_reservation,
> -					     r_node);
> -
> -			gap_start = ocfs2_resv_end(prev_resv) + 1;
> -			gap_end = next_resv->r_start - 1;
> -			gap_len = gap_end - gap_start + 1;
> +			gap_start = prev_resv->r_start;
> +			gap_end = prev_resv->r_start + prev_resv->r_len - 1;
> +			gap_len = prev_resv->r_len;
>  		} else {
>  			/*
>  			 * We're at the rightmost edge of the
> @@ -575,8 +573,8 @@ static void __ocfs2_resv_find_window(struct
ocfs2_reservation_map *resmap,
>  			gap_end = resmap->m_bitmap_len - 1;
>  		}
>  
> -		trace_ocfs2_resv_find_window_next(next ? next_resv->r_start: -1,
> -					next ? ocfs2_resv_end(next_resv) : -1);
> +		trace_ocfs2_resv_find_window_next(next ? prev_resv->r_start : -1,
> +					next ? ocfs2_resv_end(prev_resv) : -1);
>  		/*
>  		 * No need to check this gap if we have already found
>  		 * a larger region of free bits.
> @@ -589,10 +587,16 @@ static void __ocfs2_resv_find_window(struct
ocfs2_reservation_map *resmap,
>  		if (clen == wanted) {
>  			best_len = clen;
>  			best_start = cstart;
> -			goto out_insert;
> +			best_resv = prev_resv;
> +			if (!next)
> +				goto out_create;
> +			else
> +				goto out_insert;
>  		} else if (clen > best_len) {
>  			best_len = clen;
>  			best_start = cstart;
> +			best_resv = prev_resv;
> +			create_new = 0;
>  		}
>  
>  next_resv:
> @@ -604,12 +608,28 @@ static void __ocfs2_resv_find_window(struct
ocfs2_reservation_map *resmap,
>  				     r_node);
>  	}
>  
> -out_insert:
> -	if (best_len) {
> +	if (!best_len)
> +		return;
> +
> +	if (create_new) {
> +out_create:
>  		resv->r_start = best_start;
>  		resv->r_len = best_len;
>  		ocfs2_resv_insert(resmap, resv);
> +		return;
>  	}
> +
> +out_insert:
> +	if (best_resv->r_len <= wanted) {
> +		resv->r_start = best_start;
> +		resv->r_len = best_len;
> +		__ocfs2_resv_discard(resmap, best_resv);
> +	} else {
> +		best_resv->r_len -= best_len;
> +		resv->r_start = ocfs2_resv_end(best_resv) + 1;
> +		resv->r_len = best_len;
> +	}
> +	ocfs2_resv_insert(resmap, resv);
>  }
>  
>  static void ocfs2_cannibalize_resv(struct ocfs2_reservation_map *resmap,

Hi,
Could you please share a reproducer?

Thanks,
Joseph

On 4/6/23 11:40 PM, Heming Zhao wrote:
> ** problem **
> 
> Current code triggers a defragfs bug [1]:
> 
> ```
> tw-tst:~ # defragfs.ocfs2 /mnt/test_from_dd1
> defragfs.ocfs2 1.8.7
> [ERROR]Move extent failed:"/mnt/test_from_dd1" - No space left on
device
> [ERROR]"/mnt/test_from_dd1":No space left on device
> ```
> 
> I added some debug messages in relevant functions. When above error
> messages appeared, the la-window still had enough continuous bitmap
> to use, the -ENOSPC is wrong.
> 
> ** analysis **
> 
> __ocfs2_resv_find_window should use resv node from rb-tree to do linear
> search. But current code logic uses un-managered area between two resvs.
> The searching logic deviates from this func job, which should only focus
> on reservation areas (when rb_root is non NULL). Another issue of
> __ocfs2_resv_find_window is more inclined to generate inner fragment.
> It doesn't search & consume existing reservations but be apt to
create
> new reservation item.
> 
> This patch pulls this func (__ocfs2_resv_find_window) to do what it
> should do: search & consume resev. if this func fails to get suitable
> bitmap area, caller ocfs2_resv_find_window fallbacks to use oldest
> resv from LRU to do the final search.
> 
> [1]: https://bugzilla.suse.com/show_bug.cgi?id=1131931
> 
> Signed-off-by: Heming Zhao <heming.zhao at suse.com>
> ---
>  fs/ocfs2/reservations.c | 48 +++++++++++++++++++++++++++++------------
>  1 file changed, 34 insertions(+), 14 deletions(-)
> 
> diff --git a/fs/ocfs2/reservations.c b/fs/ocfs2/reservations.c
> index a9d1296d736d..eda672622d1d 100644
> --- a/fs/ocfs2/reservations.c
> +++ b/fs/ocfs2/reservations.c
> @@ -458,10 +458,11 @@ static void __ocfs2_resv_find_window(struct
ocfs2_reservation_map *resmap,
>  {
>  	struct rb_root *root = &resmap->m_reservations;
>  	unsigned int gap_start, gap_end, gap_len;
> -	struct ocfs2_alloc_reservation *prev_resv, *next_resv;
> +	struct ocfs2_alloc_reservation *prev_resv, *next_resv, *best_resv;
>  	struct rb_node *prev, *next;
>  	unsigned int cstart, clen;
>  	unsigned int best_start = 0, best_len = 0;
> +	int create_new = 0;
>  
>  	/*
>  	 * Nasty cases to consider:
> @@ -540,8 +541,9 @@ static void __ocfs2_resv_find_window(struct
ocfs2_reservation_map *resmap,
>  		if (clen) {
>  			best_len = clen;
>  			best_start = cstart;
> +			create_new = 1;
>  			if (best_len == wanted)
> -				goto out_insert;
> +				goto out_create;
>  		}
>  
>  		prev_resv = next_resv;
> @@ -557,13 +559,9 @@ static void __ocfs2_resv_find_window(struct
ocfs2_reservation_map *resmap,
>  	while (1) {
>  		next = rb_next(prev);
>  		if (next) {
> -			next_resv = rb_entry(next,
> -					     struct ocfs2_alloc_reservation,
> -					     r_node);
> -
> -			gap_start = ocfs2_resv_end(prev_resv) + 1;
> -			gap_end = next_resv->r_start - 1;
> -			gap_len = gap_end - gap_start + 1;
> +			gap_start = prev_resv->r_start;
> +			gap_end = prev_resv->r_start + prev_resv->r_len - 1;
> +			gap_len = prev_resv->r_len;
>  		} else {
>  			/*
>  			 * We're at the rightmost edge of the
> @@ -575,8 +573,8 @@ static void __ocfs2_resv_find_window(struct
ocfs2_reservation_map *resmap,
>  			gap_end = resmap->m_bitmap_len - 1;
>  		}
>  
> -		trace_ocfs2_resv_find_window_next(next ? next_resv->r_start: -1,
> -					next ? ocfs2_resv_end(next_resv) : -1);
> +		trace_ocfs2_resv_find_window_next(next ? prev_resv->r_start : -1,
> +					next ? ocfs2_resv_end(prev_resv) : -1);
>  		/*
>  		 * No need to check this gap if we have already found
>  		 * a larger region of free bits.
> @@ -589,10 +587,16 @@ static void __ocfs2_resv_find_window(struct
ocfs2_reservation_map *resmap,
>  		if (clen == wanted) {
>  			best_len = clen;
>  			best_start = cstart;
> -			goto out_insert;
> +			best_resv = prev_resv;
> +			if (!next)
> +				goto out_create;
> +			else
> +				goto out_insert;
>  		} else if (clen > best_len) {
>  			best_len = clen;
>  			best_start = cstart;
> +			best_resv = prev_resv;
> +			create_new = 0;
>  		}
>  
>  next_resv:
> @@ -604,12 +608,28 @@ static void __ocfs2_resv_find_window(struct
ocfs2_reservation_map *resmap,
>  				     r_node);
>  	}
>  
> -out_insert:
> -	if (best_len) {
> +	if (!best_len)
> +		return;
> +
> +	if (create_new) {
> +out_create:
>  		resv->r_start = best_start;
>  		resv->r_len = best_len;
>  		ocfs2_resv_insert(resmap, resv);
> +		return;
>  	}
> +
> +out_insert:
> +	if (best_resv->r_len <= wanted) {
> +		resv->r_start = best_start;
> +		resv->r_len = best_len;
> +		__ocfs2_resv_discard(resmap, best_resv);
> +	} else {
> +		best_resv->r_len -= best_len;
> +		resv->r_start = ocfs2_resv_end(best_resv) + 1;
> +		resv->r_len = best_len;
> +	}
> +	ocfs2_resv_insert(resmap, resv);
>  }
>  
>  static void ocfs2_cannibalize_resv(struct ocfs2_reservation_map *resmap,