LinuxLists.cc - Re: do

[permalink] [raw]

Subject: Re: do_div64 generic

Bernardo Innocenti <[email protected]> wrote:
>
> I see. do_div() which updates the dividend in-place did not quite apply
> to the usage pattern of the new timer code.

This is getting silly. The timer stuff has been an ongoing bug factory and
now it is colluding with the do_div() saga.

Can we just get the things working, without mangling every architecture
again?

> > The using code tests for the existance of div_long_long_rem and uses
> > the longer do_div() if it does not exist.
> >
> > Could you consider adding this to the generic code?
> >
> > /*
> > * (long)X = ((long long)divs) / (long)div
> > * (long)rem = ((long long)divs) % (long)div
> > *
> > * Warning, this will do an exception if X overflows.
> > */
> > #define div_long_long_rem(a,b,c) div_ll_X_l_rem(a,b,c)
> >
> > extern inline long
> > div_ll_X_l_rem(long long divs, long div, long *rem)
> > {
> > long dum2;
> > __asm__("divl %2":"=a"(dum2), "=d"(*rem)
> >
> > : "rm"(div), "A"(divs));
> >
> > return dum2;
> >
> > }
>
> Here's a patch that takes care of all architectures.

AFAICT, we can just rework posix-timers.c to use the standard do_div() and
be done with it, can we not? ie: no div_long_long_rem(), no
div_ll_X_l_rem(). Just do_div().

Please use `static inline', not `extern inline', btw.

2003-07-15 06:08:18

[permalink] [raw]

Subject: Re: do_div64 generic

On Tuesday 15 July 2003 07:38, Andrew Morton wrote:

> > Here's a patch that takes care of all architectures.
>
> AFAICT, we can just rework posix-timers.c to use the standard do_div() and
> be done with it, can we not? ie: no div_long_long_rem(), no
> div_ll_X_l_rem(). Just do_div().

We could, and it would be easy and almost as efficient in all places
where div_long_long_rem() is being used:

value->tv_sec = div_long_long_rem(nsec, NSEC_PER_SEC, &value->tv_nsec);

becomes:

value->tv_nsec = do_div(nsec, NSEC_PER_SEC);
value->tv_sec = nsec;

George, do you agree? May I go on and post a patch killing
div_long_long_rem() everywhere?

> Please use `static inline', not `extern inline', btw.

Oops. Fixed. I had just copied it over from asm-i386/div64.h.

Is it worth posting a big patch to replace all remaining
occurrences of 'extern inline' all over the kernel?

I'd also like to point out that __inline__ is often being
used inconsistently. We should be using __inline__ rather
than inline in public headers needed by glibc for apps
compiled with -ansi. Since it's so ugly, it shouldn't
be used in other places.

--
// Bernardo Innocenti - Develer S.r.l., R&D dept.
\X/ http://www.develer.com/

Please don't send Word attachments - http://www.gnu.org/philosophy/no-word-attachments.html

2003-07-15 06:15:17

[permalink] [raw]

Subject: Re: do_div64 generic

Bernardo Innocenti <[email protected]> wrote:
>
> Is it worth posting a big patch to replace all remaining
> occurrences of 'extern inline' all over the kernel?

Not really. It's a 400k patch. I have a script which does it. For those
rare occasions when one wants to build the kernel with -fnoinline.

2003-07-15 21:38:58

[permalink] [raw]

Subject: Re: do_div64 generic

Bernardo Innocenti wrote:
> On Tuesday 15 July 2003 07:38, Andrew Morton wrote:
>
>
>>> Here's a patch that takes care of all architectures.
>>
>>AFAICT, we can just rework posix-timers.c to use the standard do_div() and
>>be done with it, can we not? ie: no div_long_long_rem(), no
>>div_ll_X_l_rem(). Just do_div().
>
>
> We could, and it would be easy and almost as efficient in all places
> where div_long_long_rem() is being used:
>
> value->tv_sec = div_long_long_rem(nsec, NSEC_PER_SEC, &value->tv_nsec);
>
> becomes:
>
> value->tv_nsec = do_div(nsec, NSEC_PER_SEC);
> value->tv_sec = nsec;
>
> George, do you agree? May I go on and post a patch killing
> div_long_long_rem() everywhere?

The issue is that div is a very long instruction and the do_div()
thing uses 2 or three of them, while the div_long_long_rem() is just
1. Also, a lot of archs already have the required div by a different
name. It all boils down to a performance thing.

-g
>
>
>>Please use `static inline', not `extern inline', btw.
>
>
> Oops. Fixed. I had just copied it over from asm-i386/div64.h.
>
> Is it worth posting a big patch to replace all remaining
> occurrences of 'extern inline' all over the kernel?
>
> I'd also like to point out that __inline__ is often being
> used inconsistently. We should be using __inline__ rather
> than inline in public headers needed by glibc for apps
> compiled with -ansi. Since it's so ugly, it shouldn't
> be used in other places.
>

--
George Anzinger [email protected]
High-res-timers: http://sourceforge.net/projects/high-res-timers/
Preemption patch: http://www.kernel.org/pub/linux/kernel/people/rml

2003-07-15 21:59:10

[permalink] [raw]

Subject: Re: do_div64 generic

george anzinger <[email protected]> wrote:
>
> > George, do you agree? May I go on and post a patch killing
> > div_long_long_rem() everywhere?
>
> The issue is that div is a very long instruction and the do_div()
> thing uses 2 or three of them, while the div_long_long_rem() is just
> 1. Also, a lot of archs already have the required div by a different
> name. It all boils down to a performance thing.

It is only used in nanosleep(), and then only in the case where the sleep
terminated early.

If someone is calling nanosleep() so frequently for this to matter, the
time spent in divide is the least of their problems. Unless you have some
real-worldish benchmarks to demonstrate otherwise?

You know what they say about premtur optmstns, and having to propagate
funky new divide primitives across N architectures is indeed evil.

Bernardo, can you do the patch please?

2003-07-15 23:53:34

[permalink] [raw]

Subject: Re: do_div64 generic

Andrew Morton wrote:
> george anzinger <[email protected]> wrote:
>
>>>George, do you agree? May I go on and post a patch killing
>>>div_long_long_rem() everywhere?
>>
>>The issue is that div is a very long instruction and the do_div()
>>thing uses 2 or three of them, while the div_long_long_rem() is just
>>1. Also, a lot of archs already have the required div by a different
>>name. It all boils down to a performance thing.
>
>
> It is only used in nanosleep(), and then only in the case where the sleep
> terminated early.
>
> If someone is calling nanosleep() so frequently for this to matter, the
> time spent in divide is the least of their problems. Unless you have some
> real-worldish benchmarks to demonstrate otherwise?

It is also used in the jiffies to timespec and jiffies to timeval code
in timer.h, if memory serves.
>
> You know what they say about premtur optmstns, and having to propagate
> funky new divide primitives across N architectures is indeed evil.

Hm. I only want the simple div. 64-bit/32-bit in two 32-bit results.
Is this funky? And the "evil" #ifdef allows archs to not do it.
>
> Bernardo, can you do the patch please?
>
>

--
George Anzinger [email protected]
High-res-timers: http://sourceforge.net/projects/high-res-timers/
Preemption patch: http://www.kernel.org/pub/linux/kernel/people/rml

2003-07-16 18:21:33

[permalink] [raw]

Subject: Re: do_div64 generic

On Wednesday 16 July 2003 02:07, george anzinger wrote:

> > It is only used in nanosleep(), and then only in the case where the sleep
> > terminated early.
> >
> > If someone is calling nanosleep() so frequently for this to matter, the
> > time spent in divide is the least of their problems. Unless you have
> > some real-worldish benchmarks to demonstrate otherwise?
>
> It is also used in the jiffies to timespec and jiffies to timeval code
> in timer.h, if memory serves.

It's true that it's being used in more places than Andrew initially thought,
but a quick scan for jiffies_to_timeval() and jiffies_to_timespec() indicates
that it's not being used in any place where performance matters too much.

I still consider do_div() a big kludge to workaround extremely poor code
generated by GCC. If we allow this, I see no reason for not allowing a very
similar kludge which provides even better performance.

I agree with Andrew that we've run out of time for breaking things again,
so I won't be suggesting to implement a whole new set of 64bit operations
and use them all over the kernel. However, the div_long_long_rem() function
has been _already_ in use on i386 for some time, therefore the safest fix
we can do at this point is adding generic support for all other archs.

> > You know what they say about premtur optmstns, and having to propagate
> > funky new divide primitives across N architectures is indeed evil.
>
> Hm. I only want the simple div. 64-bit/32-bit in two 32-bit results.
> Is this funky? And the "evil" #ifdef allows archs to not do it.

The div_long_long_rem() interface is even somewhat cleaner than do_div() and
can be implemented easily on architectures providing a 64/32 -> 32q/32r operation
(most 32bit processors do have it).

> > Bernardo, can you do the patch please?

I would be glad to do it once the discussion has settled, whatever
the final decision will be. Just don't make me do it twice, please ;-)

--
// Bernardo Innocenti - Develer S.r.l., R&D dept.
\X/ http://www.develer.com/

Please don't send Word attachments - http://www.gnu.org/philosophy/no-word-attachments.html

2003-07-17 20:56:12

[permalink] [raw]

Subject: Re: do_div64 generic

On Wednesday 16 July 2003 20:33, Bernardo Innocenti wrote:

> > > Bernardo, can you do the patch please?
>
> I would be glad to do it once the discussion has settled, whatever
> the final decision will be. Just don't make me do it twice, please ;-)

So far nobody have commented and the problem is still unaddressed.
What shall I do? As far as I can tell, our options are:

1) add surrogates of div_long_long_rem() in asm-generic/div64.h and in
all other archs that have their own optimized versions of do_div().
I already have a patch for this, but it has been tested only on i386
and m68knommu.

2) replace all uses of div_long_long_rem() (I see onlt 4 of them in
2.6.0-test1) with do_div(). This is slightly less efficient, but
easier to maintain in the long term.

I shall note that I _hate_ fixing compiler problems in the kernel. The
real fix I'm dreaming involves adding specialized patterns in GCC to
generate an optimal instruction sequence for all these cases.

Of course we should realize that we need to support older versions of
GCC and, even if we didn't, we can't wait for the next GCC release :-)

So, if we're going to live with do_div(), I think we could as well
have a set of macros for the most frequent cases. I've just spotted
another candidate in kernel/posix-timers.c: mpy_l_X_l_ll().

This is not a third option for fixing our immediate problem: it's
just an idea for future improvement.

Andrew, George, please comment.

--
// Bernardo Innocenti - Develer S.r.l., R&D dept.
\X/ http://www.develer.com/

Please don't send Word attachments - http://www.gnu.org/philosophy/no-word-attachments.html

2003-07-17 21:08:49

[permalink] [raw]

Subject: Re: do_div64 generic

Bernardo Innocenti <[email protected]> wrote:
>
> 2) replace all uses of div_long_long_rem() (I see onlt 4 of them in
> 2.6.0-test1) with do_div(). This is slightly less efficient, but
> easier to maintain in the long term.

Ths one's OK by me. Let's just fix the bug with minimum risk and churn.

2003-07-17 22:31:32

[permalink] [raw]

Subject: Re: do_div64 generic

On Thursday 17 July 2003 23:16, Andrew Morton wrote:
> Bernardo Innocenti <[email protected]> wrote:
> > 2) replace all uses of div_long_long_rem() (I see onlt 4 of them in
> > 2.6.0-test1) with do_div(). This is slightly less efficient, but
> > easier to maintain in the long term.
>
> Ths one's OK by me. Let's just fix the bug with minimum risk and churn.

Ok, I will be preparing a patch tomorrow unless there are more objections.

--
// Bernardo Innocenti - Develer S.r.l., R&D dept.
\X/ http://www.develer.com/

Please don't send Word attachments - http://www.gnu.org/philosophy/no-word-attachments.html

2003-07-17 22:56:17

[permalink] [raw]

Subject: Re: do_div64 generic

Andrew Morton wrote:
> Bernardo Innocenti <[email protected]> wrote:
>
>>2) replace all uses of div_long_long_rem() (I see onlt 4 of them in
>> 2.6.0-test1) with do_div(). This is slightly less efficient, but
>> easier to maintain in the long term.
>
>
> Ths one's OK by me. Let's just fix the bug with minimum risk and churn.

Uh, bug? I was not aware that there was a bug. As far as I know,
nothing is broken.

>
>

--
George Anzinger [email protected]
High-res-timers: http://sourceforge.net/projects/high-res-timers/
Preemption patch: http://www.kernel.org/pub/linux/kernel/people/rml

2003-07-17 22:55:00

[permalink] [raw]

Subject: Re: do_div64 generic

Bernardo Innocenti wrote:
> On Wednesday 16 July 2003 20:33, Bernardo Innocenti wrote:
>
>
>>>>Bernardo, can you do the patch please?
>>
>> I would be glad to do it once the discussion has settled, whatever
>>the final decision will be. Just don't make me do it twice, please ;-)
>
>
> So far nobody have commented and the problem is still unaddressed.
> What shall I do? As far as I can tell, our options are:
>
> 1) add surrogates of div_long_long_rem() in asm-generic/div64.h and in
> all other archs that have their own optimized versions of do_div().
> I already have a patch for this, but it has been tested only on i386
> and m68knommu.
>
> 2) replace all uses of div_long_long_rem() (I see onlt 4 of them in
> 2.6.0-test1) with do_div(). This is slightly less efficient, but
> easier to maintain in the long term.

Actually, the macro to do this is already there. Is there a real
reason not to use it. The using code sure looks cleaner with it.
>
> I shall note that I _hate_ fixing compiler problems in the kernel. The
> real fix I'm dreaming involves adding specialized patterns in GCC to
> generate an optimal instruction sequence for all these cases.

I would love to get to the instruction via normal C.
>
> Of course we should realize that we need to support older versions of
> GCC and, even if we didn't, we can't wait for the next GCC release :-)
>
> So, if we're going to live with do_div(), I think we could as well
> have a set of macros for the most frequent cases. I've just spotted
> another candidate in kernel/posix-timers.c: mpy_l_X_l_ll().

The mpy_l_X_l_ll() is there because it is so easy to get it wrong. It
is standard C (well gcc) but if you don't get the casting just right
it will throw away the high bits.
>
> This is not a third option for fixing our immediate problem: it's
> just an idea for future improvement.
>
> Andrew, George, please comment.

Is there any need to change any thing at all? Or maybe a comment
somewhere on what direction we would like things to go.

When I look at the div code on the risc machines I begin to really
understand why gcc avoids the div instruction so actively. (It
optimizes away almost all divides by constants.)
>

--
George Anzinger [email protected]
High-res-timers: http://sourceforge.net/projects/high-res-timers/
Preemption patch: http://www.kernel.org/pub/linux/kernel/people/rml

2003-07-18 03:03:53

[permalink] [raw]

Subject: Re: do_div64 generic

george anzinger <[email protected]> wrote:
>
> > Ths one's OK by me. Let's just fix the bug with minimum risk and churn.
>
> Uh, bug? I was not aware that there was a bug. As far as I know,
> nothing is broken.

wtf? Then why are people running around brandishing big scary patches
at me?

2003-07-18 03:57:13