Problem with commit deda2e81961e96be4f2c09328baca4710a2fd1a0

Problem with commit deda2e81961e96be4f2c09328baca4710a2fd1a0

[Larry Finger]

Guys,

With the above commit, building an i386 version of the kernel results in the
following from the build:

kernel/built-in.o: In function `logarithmic_accumulation':
/home/finger/linux-realtek/kernel/time/timekeeping.c:715: undefined reference to
`__umoddi3'
/home/finger/linux-realtek/kernel/time/timekeeping.c:715: undefined reference to
`__udivdi3'
make: *** [.tmp_vmlinux1] Error 1

Reverting the patch allows the system to build correctly.

Larry

Re: Problem with commit deda2e81961e96be4f2c09328baca4710a2fd1a0

[Linus Torvalds]

On Thu, Aug 12, 2010 at 1:18 PM, Larry Finger <Larry.Finger@lwfinger.net> wrote:
>
> With the above commit, building an i386 version of the kernel results in the
> following from the build:
>
> kernel/built-in.o: In function `logarithmic_accumulation':
> /home/finger/linux-realtek/kernel/time/timekeeping.c:715: undefined reference to
> `__umoddi3'
> /home/finger/linux-realtek/kernel/time/timekeeping.c:715: undefined reference to
> `__udivdi3'
> make: *** [.tmp_vmlinux1] Error 1
>
> Reverting the patch allows the system to build correctly.

Damn. It's your compiler turning a while-loop into a divide. Which
likely isn't even an optimization, but whatever.

John: I think that while-loop needs to be something like

   if (raw_nsecs >= NSEC_PER_SEC) {
      u64 raw_secs = raw_nsecs;
      raw_nsecs = do_div(raw_secs, NSEC_PER_SEC);
      raw_time.tv_sec += taw_secs;
  }
  raw_time.tc_nsec = raw_nsecs;

which is sad and overly complicated, but the simple thing seems to get
messed up by the compiler.

Untested. Maybe I got the complex do_div() semantics wrong. Somebody
needs to check.

                     Linus

Re: Problem with commit deda2e81961e96be4f2c09328baca4710a2fd1a0

[Larry Finger]

On 08/12/2010 03:26 PM, Linus Torvalds wrote:
> On Thu, Aug 12, 2010 at 1:18 PM, Larry Finger <Larry.Finger@lwfinger.net> wrote:
>>
>> With the above commit, building an i386 version of the kernel results in the
>> following from the build:
>>
>> kernel/built-in.o: In function `logarithmic_accumulation':
>> /home/finger/linux-realtek/kernel/time/timekeeping.c:715: undefined reference to
>> `__umoddi3'
>> /home/finger/linux-realtek/kernel/time/timekeeping.c:715: undefined reference to
>> `__udivdi3'
>> make: *** [.tmp_vmlinux1] Error 1
>>
>> Reverting the patch allows the system to build correctly.
> 
> Damn. It's your compiler turning a while-loop into a divide. Which
> likely isn't even an optimization, but whatever.
> 
> John: I think that while-loop needs to be something like
> 
>    if (raw_nsecs >= NSEC_PER_SEC) {
>       u64 raw_secs = raw_nsecs;
>       raw_nsecs = do_div(raw_secs, NSEC_PER_SEC);
>       raw_time.tv_sec += taw_secs;
>   }
>   raw_time.tc_nsec = raw_nsecs;
> 
> which is sad and overly complicated, but the simple thing seems to get
> messed up by the compiler.
> 
> Untested. Maybe I got the complex do_div() semantics wrong. Somebody
> needs to check.

I'll try it. The system with the problem has gcc (SUSE Linux) 4.3.2
[gcc-4_3-branch revision 141291]. That is on a 64-bit system cross compiling
with ARCH=i386.

The real 32-bit system with gcc (SUSE Linux) 4.5.0 20100604 [gcc-4_5-branch
revision 160292] builds OK. It just wasn't finished when I wrote the first message.

Larry

Re: Problem with commit deda2e81961e96be4f2c09328baca4710a2fd1a0

[Mikael Pettersson]

Larry Finger writes:
 > On 08/12/2010 03:26 PM, Linus Torvalds wrote:
 > > On Thu, Aug 12, 2010 at 1:18 PM, Larry Finger <Larry.Finger@lwfinger.net> wrote:
 > >>
 > >> With the above commit, building an i386 version of the kernel results in the
 > >> following from the build:
 > >>
 > >> kernel/built-in.o: In function `logarithmic_accumulation':
 > >> /home/finger/linux-realtek/kernel/time/timekeeping.c:715: undefined reference to
 > >> `__umoddi3'
 > >> /home/finger/linux-realtek/kernel/time/timekeeping.c:715: undefined reference to
 > >> `__udivdi3'
 > >> make: *** [.tmp_vmlinux1] Error 1
 > >>
 > >> Reverting the patch allows the system to build correctly.
 > > 
 > > Damn. It's your compiler turning a while-loop into a divide. Which
 > > likely isn't even an optimization, but whatever.
 > > 
 > > John: I think that while-loop needs to be something like
 > > 
 > >    if (raw_nsecs >= NSEC_PER_SEC) {
 > >       u64 raw_secs = raw_nsecs;
 > >       raw_nsecs = do_div(raw_secs, NSEC_PER_SEC);
 > >       raw_time.tv_sec += taw_secs;
 > >   }
 > >   raw_time.tc_nsec = raw_nsecs;
 > > 
 > > which is sad and overly complicated, but the simple thing seems to get
 > > messed up by the compiler.
 > > 
 > > Untested. Maybe I got the complex do_div() semantics wrong. Somebody
 > > needs to check.
 > 
 > I'll try it. The system with the problem has gcc (SUSE Linux) 4.3.2
 > [gcc-4_3-branch revision 141291]. That is on a 64-bit system cross compiling
 > with ARCH=i386.
 > 
 > The real 32-bit system with gcc (SUSE Linux) 4.5.0 20100604 [gcc-4_5-branch
 > revision 160292] builds OK. It just wasn't finished when I wrote the first message.

The loops-turns-into-div is a known bug in early gcc-4.3 releases,
possibly only with -Os.  It's fixed in 4.4 and 4.3.latest.  I can
probably dig up the gcc PR number if needed.

/Mikael

Re: Problem with commit deda2e81961e96be4f2c09328baca4710a2fd1a0

[john stultz]

On Thu, 2010-08-12 at 15:18 -0500, Larry Finger wrote:
> Guys,
> 
> With the above commit, building an i386 version of the kernel results in the
> following from the build:
> 
> kernel/built-in.o: In function `logarithmic_accumulation':
> /home/finger/linux-realtek/kernel/time/timekeeping.c:715: undefined reference to
> `__umoddi3'
> /home/finger/linux-realtek/kernel/time/timekeeping.c:715: undefined reference to
> `__udivdi3'
> make: *** [.tmp_vmlinux1] Error 1
> 
> Reverting the patch allows the system to build correctly.

Ugh. I'm surprised it picks *this* loop to optimize instead of the
similar one right above. I'm guessing its the local raw_nsecs value, but
whatever.  Also surprised Jason's testing didn't hit this issue, but its
probably a gcc version thing.

Regardless, I clearly need to give i386 more love in my testing.
My profuse apologies.

As suggested by Linus, here's the do_div explicit version. It builds ok
on i386 & x86_64, but I have not yet tested it. 

Larry, Jason: Could you verify it works for you (and avoids the original
issue)?

thanks
-john



>From 70b106aaaa1de81a635bbd7ea6edc244ba098d7e Mon Sep 17 00:00:00 2001
From: John Stultz <johnstul@us.ibm.com>
Date: Thu, 12 Aug 2010 13:45:28 -0700
Subject: [PATCH] time: Workaround gcc loop optimization that causes 64bit div errors

Some versions of gcc apparently aggressively optimize the raw time
accumulation loop, replacing it with a divide.

On 32bit systems, this causes the following link errors:
	undefined reference to `__umoddi3'
	undefined reference to `__udivdi3'

This patch replaces the accumulation loop with a do_div, as suggested
by Linus.

Signed-off-by: John Stultz <johnstul@us.ibm.com>
---
 kernel/time/timekeeping.c |    7 ++++---
 1 files changed, 4 insertions(+), 3 deletions(-)

diff --git a/kernel/time/timekeeping.c b/kernel/time/timekeeping.c
index dc54b72..d0ef5aa 100644
--- a/kernel/time/timekeeping.c
+++ b/kernel/time/timekeeping.c
@@ -710,9 +710,10 @@ static cycle_t logarithmic_accumulation(cycle_t offset, int shift)
 	/* Accumulate raw time */
 	raw_nsecs = timekeeper.raw_interval << shift;
 	raw_nsecs += raw_time.tv_nsec;
-	while (raw_nsecs >= NSEC_PER_SEC) {
-		raw_nsecs -= NSEC_PER_SEC;
-		raw_time.tv_sec++;
+	if (raw_nsecs >= NSEC_PER_SEC) {
+		u64 raw_secs = raw_nsecs;
+		raw_nsecs = do_div(raw_secs, NSEC_PER_SEC);
+		raw_time.tv_sec += raw_secs;
 	}
 	raw_time.tv_nsec = raw_nsecs;
 
-- 
1.6.0.4

Re: Problem with commit deda2e81961e96be4f2c09328baca4710a2fd1a0

[Larry Finger]

On 08/12/2010 03:52 PM, john stultz wrote:
> 
> Ugh. I'm surprised it picks *this* loop to optimize instead of the
> similar one right above. I'm guessing its the local raw_nsecs value, but
> whatever.  Also surprised Jason's testing didn't hit this issue, but its
> probably a gcc version thing.
> 
> Regardless, I clearly need to give i386 more love in my testing.
> My profuse apologies.
> 
> As suggested by Linus, here's the do_div explicit version. It builds ok
> on i386 & x86_64, but I have not yet tested it. 
> 
> Larry, Jason: Could you verify it works for you (and avoids the original
> issue)?

This one builds for me with both compilers. It appears to run OK. As to the
original issue - I don't think I ever saw the problem. I'll leave that question
for Jason.

Larry

Re: Problem with commit deda2e81961e96be4f2c09328baca4710a2fd1a0

[john stultz]

On Thu, 2010-08-12 at 22:17 -0500, Larry Finger wrote:
> On 08/12/2010 03:52 PM, john stultz wrote:
> > 
> > Ugh. I'm surprised it picks *this* loop to optimize instead of the
> > similar one right above. I'm guessing its the local raw_nsecs value, but
> > whatever.  Also surprised Jason's testing didn't hit this issue, but its
> > probably a gcc version thing.
> > 
> > Regardless, I clearly need to give i386 more love in my testing.
> > My profuse apologies.
> > 
> > As suggested by Linus, here's the do_div explicit version. It builds ok
> > on i386 & x86_64, but I have not yet tested it. 
> > 
> > Larry, Jason: Could you verify it works for you (and avoids the original
> > issue)?
> 
> This one builds for me with both compilers. It appears to run OK. As to the
> original issue - I don't think I ever saw the problem. I'll leave that question
> for Jason.

Thanks for the testing! 

I also managed to trigger the link issue with a 64bit gcc-4.3 cross
compiling to 32bit. However both 32bit and 64bit gcc-4.4 didn't trigger
the link issue, so it looks like its fixed in gcc.

Regardless, after my own testing, the change looks good to me. Raw time
is accumulating properly relative to monotonic time.

Assuming Jason has no complaints it should be able to be pushed in.

Thanks again for the quick reporting and verification.
-john

Re: Problem with commit deda2e81961e96be4f2c09328baca4710a2fd1a0

[Jason Wessel]

On 08/13/2010 02:30 AM, john stultz wrote:
> On Thu, 2010-08-12 at 22:17 -0500, Larry Finger wrote:
>   
>> On 08/12/2010 03:52 PM, john stultz wrote:
>>     
>>> Ugh. I'm surprised it picks *this* loop to optimize instead of the
>>> similar one right above. I'm guessing its the local raw_nsecs value, but
>>> whatever.  Also surprised Jason's testing didn't hit this issue, but its
>>> probably a gcc version thing.
>>>
>>> Regardless, I clearly need to give i386 more love in my testing.
>>> My profuse apologies.
>>>
>>> As suggested by Linus, here's the do_div explicit version. It builds ok
>>> on i386 & x86_64, but I have not yet tested it. 
>>>
>>> Larry, Jason: Could you verify it works for you (and avoids the original
>>> issue)?
>>>       
>> This one builds for me with both compilers. It appears to run OK. As to the
>> original issue - I don't think I ever saw the problem. I'll leave that question
>> for Jason.
>>     
>
> Thanks for the testing! 
>
> I also managed to trigger the link issue with a 64bit gcc-4.3 cross
> compiling to 32bit. However both 32bit and 64bit gcc-4.4 didn't trigger
> the link issue, so it looks like its fixed in gcc.
>
> Regardless, after my own testing, the change looks good to me. Raw time
> is accumulating properly relative to monotonic time.
>
> Assuming Jason has no complaints it should be able to be pushed in.
>
>   

No complaints here.  The edge case remains solved on the low MHZ 32 bit
system.

The reason I never saw any problem in all my test configurations was
that gcc 4.4 is the oldest compiler I have in any of the configurations
I am using.   I could have been more specific in my original mail on the
subject but it was tested with a 32bit cross compiler as well as a 64bit
cross compiler.

Many thanks to all who helped draw this odd ball case to closure.

Jason.