Heming Zhao
2023-Apr-06 15:40 UTC
[Ocfs2-devel] [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
Heming Zhao
2023-Apr-07 15:42 UTC
[Ocfs2-devel] [PATCH] ocfs2: Fix wrong search logic in __ocfs2_resv_find_window
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
Joseph Qi
2023-Apr-18 09:43 UTC
[Ocfs2-devel] [PATCH] ocfs2: Fix wrong search logic in __ocfs2_resv_find_window
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,
Joseph Qi
2023-Apr-21 07:35 UTC
[Ocfs2-devel] [PATCH] ocfs2: Fix wrong search logic in __ocfs2_resv_find_window
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,
Possibly Parallel Threads
- [PATCH] ocfs2: Fix wrong search logic in __ocfs2_resv_find_window
- [PATCH] ocfs2: Fix wrong search logic in __ocfs2_resv_find_window
- [PATCH] ocfs2/trivial: Code cleanup for allocation reservation.
- [PATCH] ocfs2: Fix wrong search logic in __ocfs2_resv_find_window
- [PATCH 00/42] ocfs2: Add reflink file support. V1