do_div64 generic

As part of the timer conversion and POSIX timers the following was added to the x86 kernels do_div64(). What we want is a u64/u32 that also returns the remainder. (As in nsecs/NSEC_PER_SEC returns seconds and nsecs to fill in the timespec structure.)

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;

}

I see. do_div() which updates the dividend in-place did not quite apply
to the usage pattern of the new timer code.

Quoted 19 lines

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)

Quoted 5 lines

       :	"rm"(div), "A"(divs));

	return dum2;

}

Here's a patch that takes care of all architectures.

Quoted 1 line

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.

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

Quoted 5 lines · Andrew Morton

Quoted 1 line

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?

Quoted 3 lines

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.

Quoted 3 lines

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.

Quoted 4 lines · george anzinger

Quoted 2 lines

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?

Quoted 6 lines

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.

Quoted 2 lines

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.

Quoted 1 line

Bernardo, can you do the patch please?

Quoted 1 line

Quoted 1 line

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

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.

Quoted 3 lines · Bernardo Innocenti

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.

Quoted 4 lines · Bernardo Innocenti

Quoted 1 line

Quoted 1 line

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.

Quoted 3 lines · Bernardo Innocenti

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.

Quoted 2 lines

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.

Quoted 3 lines

Quoted 1 line

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?