A regression in recent 3.2 kernel: bdi_dirty_limit() divide error

PATCH In review Wu Fengguang 3 participants 9 messages Jan 7, 2012 – Jan 10, 2012 2 messages not in the archive

Subsystems (2)

VFS Library code

lore

Share & tools

lore

A message that is not in the archive (sent off-list or not yet received): [email protected]

Wu Fengguang

author

2012-01-07 14:56 UTC #1 lore raw

Hi Ilya,

Thanks for the report!
Would you try if the attached patch can fix it?

Thanks,
Fengguang

Quoted 4 lines · Илья Тумайкин

Hello, Mr. Fengguang.
As you know the 3.2 version of Linux kernel was just released, so I decided to try it out. After I sucessfully compiled it with the previously used configuration file a bug appeared: as soon as I try to log into X, the kernel crashes producing the trace which you can see in the attachements. In terminal or when just running kdm everything is ok, also everything is completely stable with 3.1.7, so I've guessed it is kernel regression. After some playing with 'git bisect' it has pinpointed me to this commit:

Quoted 8 lines

http://git.kernel.org/?p=linux/kernel/git/torvalds/linux-2.6.git;a=commit;h=7381131cbcf7e15d201a0ffd782a4698efe4e740
That's why I've sent you this mail. I've attached several photos of different traces which I got during bisecting (nothing hit the log or very small pieces of info). If any addtional info is needed I am ready to provide it to you.
OS: Gentoo amd64 with vanilla 3.2 kernel.
Best regards.
Ilya Tumaykin.

Subject:
Date: Sat Jan 07 22:50:45 CST 2012

The uninitilized shift may lead to denominator=0 in prop_fraction_percpu() and divide error in bdi_dirty_limit().

Signed-off-by Wu Fengguang <[email protected]>

---
 lib/proportions.c |    1 +
 1 file changed, 1 insertion(+)

lib/proportions.c +1 -0

@@ -82,6 +82,7 @@ int prop_descriptor_init(struct prop_des
 
 	pd->index = 0;
 	pd->pg[0].shift = shift;
+	pd->pg[1].shift = shift;
 	mutex_init(&pd->mutex);
 	err = percpu_counter_init(&pd->pg[0].events, 0);
 	if (err)

Peter Zijlstra

2012-01-07 16:35 UTC #2 lore raw

Quoted 5 lines · Wu Fengguang

Subject:
Date: Sat Jan 07 22:50:45 CST 2012
The uninitilized shift may lead to denominator=0 in prop_fraction_percpu() and divide error in bdi_dirty_limit().

I'm not seeing how, only proc_change_shift() can change ->index, and it does that after it writes ->pg[index]->shift.

Quoted 17 lines

Signed-off-by Wu Fengguang <[email protected]>

---
 lib/proportions.c |    1 +
 1 file changed, 1 insertion(+)

lib/proportions.c 2012-01-07 22:50:37.000000000 +0800 renamed from lib/proportions.c 2012-01-07 22:50:29.000000000 +0800 +1 -0

@@ -82,6 +82,7 @@ int prop_descriptor_init(struct prop_des
 
        pd->index = 0;
        pd->pg[0].shift = shift;
+       pd->pg[1].shift = shift;
        mutex_init(&pd->mutex);
        err = percpu_counter_init(&pd->pg[0].events, 0);
        if (err)

Wu Fengguang

2012-01-08 02:33 UTC #3 lore raw

Quoted 9 lines · Peter Zijlstra

Quoted 5 lines · Wu Fengguang
Subject:
Date: Sat Jan 07 22:50:45 CST 2012
The uninitilized shift may lead to denominator=0 in prop_fraction_percpu() and divide error in bdi_dirty_limit().
I'm not seeing how, only proc_change_shift() can change ->index, and it does that after it writes ->pg[index]->shift.

Then I lose the clue why bdi_dirty_limit() will divide error at all.

prop_change_shift() does

        change ->pg[index]->shift
        smp_wmb()
        change ->index

Will the read side prop_fraction_percpu() need some read memory barrier?

Thanks,
Fengguang

Peter Zijlstra

2012-01-08 10:19 UTC #4 lore raw

Quoted 5 lines · Wu Fengguang

Quoted 4 lines · Peter Zijlstra
Quoted 3 lines · Wu Fengguang
Subject:
Date: Sat Jan 07 22:50:45 CST 2012

Quoted 7 lines

Quoted 5 lines
Quoted 2 lines
The uninitilized shift may lead to denominator=0 in prop_fraction_percpu() and divide error in bdi_dirty_limit().
I'm not seeing how, only proc_change_shift() can change ->index, and it does that after it writes ->pg[index]->shift.
Then I lose the clue why bdi_dirty_limit() will divide error at all.

You and me both, the weird thing is, this code hasn't been changes like forever and I can't recall any such weirdness.

In fact, prop_fraction_percpu() sets the denominator to period_2 + (global_count & counter_mask).

The only way to make that 0 is to overflow the unsigned long.. did the crash happen on 32bit -- I never saw the initial report?

But even then, we limit PROP_MAX_SHIFT to 3*BITS_PER_LONG/4, I don't think that could ever overflow.

Quoted 7 lines

prop_change_shift() does
        change ->pg[index]->shift
        smp_wmb()
        change ->index
Will the read side prop_fraction_percpu() need some read memory barrier?

It actually has one, see prop_get_global()...

Wu Fengguang

2012-01-09 04:04 UTC #5 lore raw

Quoted 2 lines · Peter Zijlstra

But even then, we limit PROP_MAX_SHIFT to 3*BITS_PER_LONG/4, I don't think that could ever overflow.

do_div() only uses the lower 32 bit value of the 64 bit denominator, which may happen to be 0.

The denominator is not really 64 bit, but limited by PROP_MAX_SHIFT = 48 bit, however that upper limit looks not enough.

Ilya, would you help try the attached patch instead?

Thanks,
Fengguang

Subject:
Date: Mon Jan 09 11:53:50 CST 2012

Signed-off-by Wu Fengguang <[email protected]>

---
 include/linux/proportions.h |    4 ++++
 1 file changed, 4 insertions(+)

include/linux/proportions.h +4 -0

@@ -81,7 +81,11 @@ void prop_inc_percpu(struct prop_descrip
  * Limit the time part in order to ensure there are some bits left for the
  * cycle counter and fraction multiply.
  */
+#if BITS_PER_LONG == 32
 #define PROP_MAX_SHIFT (3*BITS_PER_LONG/4)
+#else
+#define PROP_MAX_SHIFT (BITS_PER_LONG/2)
+#endif
 
 #define PROP_FRAC_SHIFT		(BITS_PER_LONG - PROP_MAX_SHIFT - 1)
 #define PROP_FRAC_BASE		(1UL << PROP_FRAC_SHIFT)

A message that is not in the archive (sent off-list or not yet received): [email protected]

Wu Fengguang

2012-01-10 14:38 UTC #7 lore raw

Quoted 8 lines · Илья Тумайкин

Hello, Mr. Fengguang.
This latter patch fixed the problem completely! I've tested vanilla 3.2 with both patches applied and with only the latter one, results are the same:
- first of all the initial problem solved. I have no "divide error" (not sure if this panic) now.
- doing daily desktop stuff (e.g. web browsing, movie playback, book reading etc) also without any errors as well as compiling packages.
So, I can confirm the problem is solved completely.
Thank you and your colleagues very much for you fast response and active help! I am very grateful!

Ilya, thank you too for your report and testing! I'll submit the patch right now.

Thanks,
Fengguang

Quoted 27 lines

--- Пн, 9.1.12, Wu Fengguang <[email protected]> пишет:
Quoted 25 lines
От: Wu Fengguang <[email protected]>
Тема: Re: A regression in recent 3.2 kernel: bdi_dirty_limit() divide error
Кому: "Peter Zijlstra" <[email protected]>
Копия: "Илья Тумайкин" <[email protected]>, "LKML" <[email protected]>, [email protected] Дата: Понедельник, 9 январь 2012, 7:04
Quoted 1 line · Peter Zijlstra
But even then, we limit PROP_MAX_SHIFT to
3*BITS_PER_LONG/4, I don't
Quoted 1 line
think that could ever overflow.
do_div() only uses the lower 32 bit value of the 64 bit denominator,
which may happen to be 0.
The denominator is not really 64 bit, but limited by PROP_MAX_SHIFT =
48 bit, however that upper limit looks not enough.
Ilya, would you help try the attached patch instead?
Thanks,
Fengguang

--
To unsubscribe from this list: send the line "unsubscribe linux-fsdevel" in the body of a message to [email protected]
More majordomo info at http://vger.kernel.org/majordomo-info.html

Wu Fengguang

2012-01-09 04:55 UTC #8 lore raw

In reply to Peter Zijlstra

Quoted 14 lines · Peter Zijlstra

Quoted 5 lines · Wu Fengguang
Quoted 4 lines · Peter Zijlstra
Quoted 3 lines · Wu Fengguang
Subject:
Date: Sat Jan 07 22:50:45 CST 2012
Quoted 7 lines
Quoted 5 lines
Quoted 2 lines
The uninitilized shift may lead to denominator=0 in prop_fraction_percpu() and divide error in bdi_dirty_limit().
I'm not seeing how, only proc_change_shift() can change ->index, and it does that after it writes ->pg[index]->shift.
Then I lose the clue why bdi_dirty_limit() will divide error at all.

Quoted 8 lines

You and me both, the weird thing is, this code hasn't been changes like forever and I can't recall any such weirdness.
In fact, prop_fraction_percpu() sets the denominator to period_2 + (global_count & counter_mask).
The only way to make that 0 is to overflow the unsigned long.. did the crash happen on 32bit -- I never saw the initial report?

No, it's a 64bit kernel. Sorry I should have forwarded the initial complete report.

Quoted 2 lines

But even then, we limit PROP_MAX_SHIFT to 3*BITS_PER_LONG/4, I don't think that could ever overflow.

It seems PROP_MAX_SHIFT should be set to <=32 on 64bit box, because

1) bdi_dirty_limit() only uses the lower 32 bit of the denominator by calling do_div()

2) (bdi_dirty * numerator) could easily overflow if numerator used up to 48 bits, leaving only 16 bits to bdi_dirty

And I guess (2) may be the root cause of a related old bug:

sudden drops of bdi_thresh
http://lkml.indiana.edu/hypermail/linux/kernel/1109.0/00183.html
http://lkml.indiana.edu/hypermail/linux/kernel/1109.0/00183/10-3.1.0-rc1%2Bbalance_dirty_pages-pages.png

Quoted 9 lines

Quoted 7 lines
prop_change_shift() does
        change ->pg[index]->shift
        smp_wmb()
        change ->index
Will the read side prop_fraction_percpu() need some read memory barrier?
It actually has one, see prop_get_global()...

Ah yes! Sorry for overlooking this.

Regards,
Fengguang

Wu Fengguang

2012-01-10 14:54 UTC #9 lore raw

PATCH 1/1 lib: proportion: lower PROP_MAX_SHIFT to 32 on 64-bit kernel

PROP_MAX_SHIFT should be set to <=32 on 64-bit box. This fixes two bugs in the below lines of bdi_dirty_limit():

	bdi_dirty *= numerator;
	do_div(bdi_dirty, denominator);

1) divide error: do_div() only uses the lower 32 bit of the denominator, which may trimmed to be 0 when PROP_MAX_SHIFT > 32.

2) overflow: (bdi_dirty * numerator) could easily overflow if numerator used up to 48 bits, leaving only 16 bits to bdi_dirty

Tested-by Ilya Tumaykin <[email protected]>

Signed-off-by Wu Fengguang <[email protected]>

---
 include/linux/proportions.h |    4 ++++
 1 file changed, 4 insertions(+)

include/linux/proportions.h +4 -0

@@ -81,7 +81,11 @@ void prop_inc_percpu(struct prop_descrip
  * Limit the time part in order to ensure there are some bits left for the
  * cycle counter and fraction multiply.
  */
+#if BITS_PER_LONG == 32
 #define PROP_MAX_SHIFT (3*BITS_PER_LONG/4)
+#else
+#define PROP_MAX_SHIFT (BITS_PER_LONG/2)
+#endif
 
 #define PROP_FRAC_SHIFT		(BITS_PER_LONG - PROP_MAX_SHIFT - 1)
 #define PROP_FRAC_BASE		(1UL << PROP_FRAC_SHIFT)

Wu Fengguang

2012-01-10 15:01 UTC #10 lore raw

Re: [PATCH] lib: proportion: lower PROP_MAX_SHIFT to 32 on 64-bit kernel

Ilya, would you post your /proc/vmstat?

I wonder if your proportion shift value is really large enough (> 32) to trigger bug in this way.

Thanks,
Fengguang

Quoted 32 lines · Wu Fengguang

PROP_MAX_SHIFT should be set to <=32 on 64-bit box. This fixes two bugs in the below lines of bdi_dirty_limit():
	bdi_dirty *= numerator;
	do_div(bdi_dirty, denominator);
1) divide error: do_div() only uses the lower 32 bit of the denominator, which may trimmed to be 0 when PROP_MAX_SHIFT > 32.
2) overflow: (bdi_dirty * numerator) could easily overflow if numerator used up to 48 bits, leaving only 16 bits to bdi_dirty
Tested-by Ilya Tumaykin <[email protected]>
Signed-off-by Wu Fengguang <[email protected]>
---
 include/linux/proportions.h |    4 ++++
 1 file changed, 4 insertions(+)
include/linux/proportions.h +4 -0
@@ -81,7 +81,11 @@ void prop_inc_percpu(struct prop_descrip
  * Limit the time part in order to ensure there are some bits left for the
  * cycle counter and fraction multiply.
  */
+#if BITS_PER_LONG == 32
 #define PROP_MAX_SHIFT (3*BITS_PER_LONG/4)
+#else
+#define PROP_MAX_SHIFT (BITS_PER_LONG/2)
+#endif
 
 #define PROP_FRAC_SHIFT		(BITS_PER_LONG - PROP_MAX_SHIFT - 1)
 #define PROP_FRAC_BASE		(1UL << PROP_FRAC_SHIFT)