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

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

[Wu Fengguang]

[-- Attachment #1: Type: text/plain, Size: 1166 bytes --]

Hi Ilya,

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

Thanks,
Fengguang

On Fri, Jan 06, 2012 at 01:13:15PM -0800, Илья Тумайкин wrote:
> 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:
> 
> 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.







[-- Attachment #2: proportion-init-shift.patch --]
[-- Type: text/x-diff, Size: 632 bytes --]

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 <fengguang.wu@intel.com>
---
 lib/proportions.c |    1 +
 1 file changed, 1 insertion(+)

--- linux.orig/lib/proportions.c	2012-01-07 22:50:29.000000000 +0800
+++ linux/lib/proportions.c	2012-01-07 22:50:37.000000000 +0800
@@ -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)

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

[Peter Zijlstra]

On Sat, 2012-01-07 at 22:56 +0800, Wu Fengguang wrote:
> 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.

> Signed-off-by: Wu Fengguang <fengguang.wu@intel.com>
> ---
>  lib/proportions.c |    1 +
>  1 file changed, 1 insertion(+)
> 
> --- linux.orig/lib/proportions.c        2012-01-07 22:50:29.000000000 +0800
> +++ linux/lib/proportions.c     2012-01-07 22:50:37.000000000 +0800
> @@ -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)
> 
> 

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

[Wu Fengguang]

On Sat, Jan 07, 2012 at 05:35:25PM +0100, Peter Zijlstra wrote:
> On Sat, 2012-01-07 at 22:56 +0800, Wu Fengguang wrote:
> > 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

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

[Peter Zijlstra]

On Sun, 2012-01-08 at 10:33 +0800, Wu Fengguang wrote:
> On Sat, Jan 07, 2012 at 05:35:25PM +0100, Peter Zijlstra wrote:
> > On Sat, 2012-01-07 at 22:56 +0800, Wu Fengguang wrote:
> > > 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.

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.

> 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()...

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

[Wu Fengguang]

[-- Attachment #1: Type: text/plain, Size: 461 bytes --]

On Sun, Jan 08, 2012 at 11:19:14AM +0100, Peter Zijlstra wrote:

> 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

[-- Attachment #2: proportion-max-shift.patch --]
[-- Type: text/x-diff, Size: 755 bytes --]

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


Signed-off-by: Wu Fengguang <fengguang.wu@intel.com>
---
 include/linux/proportions.h |    4 ++++
 1 file changed, 4 insertions(+)

--- linux.orig/include/linux/proportions.h	2012-01-09 11:51:19.000000000 +0800
+++ linux/include/linux/proportions.h	2012-01-09 11:53:47.000000000 +0800
@@ -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)

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

[Wu Fengguang]

On Sun, Jan 08, 2012 at 11:19:14AM +0100, Peter Zijlstra wrote:
> On Sun, 2012-01-08 at 10:33 +0800, Wu Fengguang wrote:
> > On Sat, Jan 07, 2012 at 05:35:25PM +0100, Peter Zijlstra wrote:
> > > On Sat, 2012-01-07 at 22:56 +0800, Wu Fengguang wrote:
> > > > 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.
> 
> 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.

> 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

> > 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

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

[Wu Fengguang]

On Tue, Jan 10, 2012 at 06:32:25AM -0800, Илья Тумайкин wrote:
> 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

> --- Пн, 9.1.12, Wu Fengguang <wfg@linux.intel.com> пишет:
> 
> > От: Wu Fengguang <wfg@linux.intel.com>
> > Тема: Re: A regression in recent 3.2 kernel: bdi_dirty_limit() divide error
> > Кому: "Peter Zijlstra" <a.p.zijlstra@chello.nl>
> > Копия: "Илья Тумайкин" <librarian_rus@yahoo.com>, "LKML" <linux-kernel@vger.kernel.org>, linux-fsdevel@vger.kernel.org
> > Дата: Понедельник, 9 январь 2012, 7:04
> > On Sun, Jan 08, 2012 at 11:19:14AM
> > +0100, Peter Zijlstra wrote:
> > 
> > > 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
> >

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

[Wu Fengguang]

On Tue, Jan 10, 2012 at 06:32:25AM -0800, Илья Тумайкин wrote:
> 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

> --- Пн, 9.1.12, Wu Fengguang <wfg@linux.intel.com> пишет:
> 
> > От: Wu Fengguang <wfg@linux.intel.com>
> > Тема: Re: A regression in recent 3.2 kernel: bdi_dirty_limit() divide error
> > Кому: "Peter Zijlstra" <a.p.zijlstra@chello.nl>
> > Копия: "Илья Тумайкин" <librarian_rus@yahoo.com>, "LKML" <linux-kernel@vger.kernel.org>, linux-fsdevel@vger.kernel.org
> > Дата: Понедельник, 9 январь 2012, 7:04
> > On Sun, Jan 08, 2012 at 11:19:14AM
> > +0100, Peter Zijlstra wrote:
> > 
> > > 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
> >
--
To unsubscribe from this list: send the line "unsubscribe linux-fsdevel" in
the body of a message to majordomo@vger.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html

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

[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 <librarian_rus@yahoo.com>
Signed-off-by: Wu Fengguang <fengguang.wu@intel.com>
---
 include/linux/proportions.h |    4 ++++
 1 file changed, 4 insertions(+)

--- linux.orig/include/linux/proportions.h	2012-01-09 11:51:19.000000000 +0800
+++ linux/include/linux/proportions.h	2012-01-09 11:53:47.000000000 +0800
@@ -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)

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

[Wu Fengguang]

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

On Tue, Jan 10, 2012 at 10:54:55PM +0800, Wu Fengguang wrote:
> 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 <librarian_rus@yahoo.com>
> Signed-off-by: Wu Fengguang <fengguang.wu@intel.com>
> ---
>  include/linux/proportions.h |    4 ++++
>  1 file changed, 4 insertions(+)
> 
> --- linux.orig/include/linux/proportions.h	2012-01-09 11:51:19.000000000 +0800
> +++ linux/include/linux/proportions.h	2012-01-09 11:53:47.000000000 +0800
> @@ -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)