[PATCH] deinline sleep/delay functions

[PATCH] deinline sleep/delay functions

[Denis Vlasenko]

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

Hi Andrew,

Optimizing delay functions for speed is utterly pointless.

This patch turns ssleep(n), mdelay(n), udelay(n) and ndelay(n)
into functions, thus they generate the smallest possible code
at the callsite. Previously they were more or less inlined.

Run tested. Saved a few kb off vmlinux.

Signed-off-by: Denis Vlasenko <vda@ilport.com.ua>
--
vda

[-- Attachment #2: delay.patch --]
[-- Type: text/x-diff, Size: 3565 bytes --]

diff -urpN linux-2.6.12.src/include/asm-i386/delay.h linux-2.6.12.new/include/asm-i386/delay.h
--- linux-2.6.12.src/include/asm-i386/delay.h	Tue Oct 19 00:53:05 2004
+++ linux-2.6.12.new/include/asm-i386/delay.h	Wed Jun 29 20:29:48 2005
@@ -15,12 +15,8 @@ extern void __ndelay(unsigned long nsecs
 extern void __const_udelay(unsigned long usecs);
 extern void __delay(unsigned long loops);
 
-#define udelay(n) (__builtin_constant_p(n) ? \
-	((n) > 20000 ? __bad_udelay() : __const_udelay((n) * 0x10c7ul)) : \
-	__udelay(n))
+#define udelay(n) __udelay(n)
 	
-#define ndelay(n) (__builtin_constant_p(n) ? \
-	((n) > 20000 ? __bad_ndelay() : __const_udelay((n) * 5ul)) : \
-	__ndelay(n))
+#define ndelay(n) __ndelay(n)
 
 #endif /* defined(_I386_DELAY_H) */
diff -urpN linux-2.6.12.src/include/linux/delay.h linux-2.6.12.new/include/linux/delay.h
--- linux-2.6.12.src/include/linux/delay.h	Thu Mar  3 09:31:14 2005
+++ linux-2.6.12.new/include/linux/delay.h	Wed Jun 29 20:41:14 2005
@@ -11,40 +11,14 @@ extern unsigned long loops_per_jiffy;
 
 #include <asm/delay.h>
 
-/*
- * Using udelay() for intervals greater than a few milliseconds can
- * risk overflow for high loops_per_jiffy (high bogomips) machines. The
- * mdelay() provides a wrapper to prevent this.  For delays greater
- * than MAX_UDELAY_MS milliseconds, the wrapper is used.  Architecture
- * specific values can be defined in asm-???/delay.h as an override.
- * The 2nd mdelay() definition ensures GCC will optimize away the 
- * while loop for the common cases where n <= MAX_UDELAY_MS  --  Paul G.
- */
-
-#ifndef MAX_UDELAY_MS
-#define MAX_UDELAY_MS	5
-#endif
-
-#ifdef notdef
-#define mdelay(n) (\
-	{unsigned long __ms=(n); while (__ms--) udelay(1000);})
-#else
-#define mdelay(n) (\
-	(__builtin_constant_p(n) && (n)<=MAX_UDELAY_MS) ? udelay((n)*1000) : \
-	({unsigned long __ms=(n); while (__ms--) udelay(1000);}))
-#endif
-
+void calibrate_delay(void);
+void mdelay(unsigned int msecs);
 #ifndef ndelay
 #define ndelay(x)	udelay(((x)+999)/1000)
 #endif
 
-void calibrate_delay(void);
 void msleep(unsigned int msecs);
+void ssleep(unsigned int secs);
 unsigned long msleep_interruptible(unsigned int msecs);
-
-static inline void ssleep(unsigned int seconds)
-{
-	msleep(seconds * 1000);
-}
 
 #endif /* defined(_LINUX_DELAY_H) */
diff -urpN linux-2.6.12.src/kernel/timer.c linux-2.6.12.new/kernel/timer.c
--- linux-2.6.12.src/kernel/timer.c	Sun Jun 19 16:11:00 2005
+++ linux-2.6.12.new/kernel/timer.c	Wed Jun 29 21:02:26 2005
@@ -33,6 +33,7 @@
 #include <linux/posix-timers.h>
 #include <linux/cpu.h>
 #include <linux/syscalls.h>
+#include <linux/delay.h>
 
 #include <asm/uaccess.h>
 #include <asm/unistd.h>
@@ -89,6 +90,20 @@ static inline void set_running_timer(tve
 /* Fake initialization */
 static DEFINE_PER_CPU(tvec_base_t, tvec_bases) = { SPIN_LOCK_UNLOCKED };
 
+/***
+ * Using udelay() for intervals greater than a few milliseconds can
+ * risk overflow for high loops_per_jiffy (high bogomips) machines. The
+ * mdelay() provides a wrapper to prevent this.
+ *
+ * It's not inlined because we do not optimize delays for speed ;)
+ */
+void mdelay(unsigned int msecs)
+{
+	while (msecs--) udelay(1000);
+}
+
+EXPORT_SYMBOL(mdelay);
+
 static void check_timer_failed(struct timer_list *timer)
 {
 	static int whine_count;
@@ -1592,6 +1607,13 @@ void msleep(unsigned int msecs)
 }
 
 EXPORT_SYMBOL(msleep);
+
+void ssleep(unsigned int secs)
+{
+        msleep(secs * 1000);
+}
+
+EXPORT_SYMBOL(ssleep);
 
 /**
  * msleep_interruptible - sleep waiting for waitqueue interruptions

Re: [PATCH] deinline sleep/delay functions

[Russell King]

On Thu, Jun 30, 2005 at 08:52:25AM +0300, Denis Vlasenko wrote:
> Hi Andrew,
> 
> Optimizing delay functions for speed is utterly pointless.
> 
> This patch turns ssleep(n), mdelay(n), udelay(n) and ndelay(n)
> into functions, thus they generate the smallest possible code
> at the callsite. Previously they were more or less inlined.
> 
> Run tested. Saved a few kb off vmlinux.
> 
> Signed-off-by: Denis Vlasenko <vda@ilport.com.ua>

Rejected-by: Russell King 8)

The reason is that now we're unable to find out if anyone's doing
udelay(100000000000000000) which breaks on most architectures.

There are a number of compile-time checks that your patch has removed
which catch such things, and as such your patch is not acceptable.
Some architectures have a lower threshold of acceptability for the
maximum udelay value, so it's absolutely necessary to keep this.

-- 
Russell King
 Linux kernel    2.6 ARM Linux   - http://www.arm.linux.org.uk/
 maintainer of:  2.6 Serial core

Re: [PATCH] deinline sleep/delay functions

[Andrew Morton]

Russell King <rmk+lkml@arm.linux.org.uk> wrote:
>
> On Thu, Jun 30, 2005 at 08:52:25AM +0300, Denis Vlasenko wrote:
> > Hi Andrew,
> > 
> > Optimizing delay functions for speed is utterly pointless.
> > 
> > This patch turns ssleep(n), mdelay(n), udelay(n) and ndelay(n)
> > into functions, thus they generate the smallest possible code
> > at the callsite. Previously they were more or less inlined.
> > 
> > Run tested. Saved a few kb off vmlinux.
> > 
> > Signed-off-by: Denis Vlasenko <vda@ilport.com.ua>
> 
> Rejected-by: Russell King 8)
> 
> The reason is that now we're unable to find out if anyone's doing
> udelay(100000000000000000) which breaks on most architectures.
> 
> There are a number of compile-time checks that your patch has removed
> which catch such things, and as such your patch is not acceptable.
> Some architectures have a lower threshold of acceptability for the
> maximum udelay value, so it's absolutely necessary to keep this.

It removes that check from x86 - other architectures retain it.

I don't recall seeing anyone trigger the check, and it hardly seems worth
adding a "few kb" to vmlinux for it?

Re: [PATCH] deinline sleep/delay functions

[Arjan van de Ven]

> > There are a number of compile-time checks that your patch has removed
> > which catch such things, and as such your patch is not acceptable.
> > Some architectures have a lower threshold of acceptability for the
> > maximum udelay value, so it's absolutely necessary to keep this.
> 
> It removes that check from x86 - other architectures retain it.
> 
> I don't recall seeing anyone trigger the check,

I do ;) Esp in vendor out of tree crap. It's a good compile time
diagnostic so the junk code doesnt' hit mainline but gets fixed first.

>
>  and it hardly seems worth
> adding a "few kb" to vmlinux for it?

but it can be fixed to not add that few kb while retaining the checking
value. All that needs is for it to be a define that calls the worker
function. Eg the check gets optimized out and all that remains is the
call to the worker function that does the actual delay.

Re: [PATCH] deinline sleep/delay functions

[Russell King]

On Thu, Jun 30, 2005 at 02:11:11AM -0700, Andrew Morton wrote:
> Russell King <rmk+lkml@arm.linux.org.uk> wrote:
> > Rejected-by: Russell King 8)
> > 
> > The reason is that now we're unable to find out if anyone's doing
> > udelay(100000000000000000) which breaks on most architectures.
> > 
> > There are a number of compile-time checks that your patch has removed
> > which catch such things, and as such your patch is not acceptable.
> > Some architectures have a lower threshold of acceptability for the
> > maximum udelay value, so it's absolutely necessary to keep this.
> 
> I don't recall seeing anyone trigger the check, and it hardly seems worth
> adding a "few kb" to vmlinux for it?

Maybe we can have both - would the space saving be achieved by just moving
mdelay and ssleep out of linux/delay.h and not touching asm-i386/delay.h?

-- 
Russell King
 Linux kernel    2.6 ARM Linux   - http://www.arm.linux.org.uk/
 maintainer of:  2.6 Serial core

Re: [PATCH] deinline sleep/delay functions

[Denis Vlasenko]

On Thursday 30 June 2005 12:19, Arjan van de Ven wrote:
> 
> > > There are a number of compile-time checks that your patch has removed
> > > which catch such things, and as such your patch is not acceptable.
> > > Some architectures have a lower threshold of acceptability for the
> > > maximum udelay value, so it's absolutely necessary to keep this.
> > 
> > It removes that check from x86 - other architectures retain it.
> > 
> > I don't recall seeing anyone trigger the check,
> 
> I do ;) Esp in vendor out of tree crap. It's a good compile time
> diagnostic so the junk code doesnt' hit mainline but gets fixed first.

It seems my patch was incomplete.

Thinking more about it, since it exists in all arches
and also since delaying is not performance critical
(hey, if we're going to delay/sleep, we surely can burn
a few more cycles), this can be done as follows:

linux/timer.c:

void ndelay(unsigned int nsecs)
{
	unsigned int m = nsecs/(1024*1024);
       	while (m--)
		__ndelay(1024);
	__ndelay(nsecs % (1024*1024));
}

void udelay(unsigned int usecs)
{
	unsigned int k = usecs/1024;
       	while (k--)
		__udelay(1024);
	__udelay(usecs % 1024);
}

void mdelay(unsigned int msecs)
{
       	while (msecs--)
		udelay(1000);
}

void ssleep(unsigned int secs)
{
        msleep(secs * 1000);
}

and arches will need to only supply two functions:

__udelay(n) [n is guaranteed <1024]
__ndelay(n) [n is guaranteed <1024*1024]

For users, _any_ value, however large, will work for
any delay function.

Comments?
--
vda

Re: [PATCH] deinline sleep/delay functions

[Arjan van de Ven]

On Thu, 2005-06-30 at 13:21 +0300, Denis Vlasenko wrote:
> On Thursday 30 June 2005 12:19, Arjan van de Ven wrote:
> > 
> > > > There are a number of compile-time checks that your patch has removed
> > > > which catch such things, and as such your patch is not acceptable.
> > > > Some architectures have a lower threshold of acceptability for the
> > > > maximum udelay value, so it's absolutely necessary to keep this.
> > > 
> > > It removes that check from x86 - other architectures retain it.
> > > 
> > > 
> For users, _any_ value, however large, will work for
> any delay function.

that's not desired though. Desired is to limit udelay() to say 2000 or
so. And force anything above that to go via mdelay() (just to make it
stand out as broken code ;)

Over time we also want to phase out mdelay of course...

Re: [PATCH] deinline sleep/delay functions

[Denis Vlasenko]

On Thursday 30 June 2005 13:47, Arjan van de Ven wrote:
> On Thu, 2005-06-30 at 13:21 +0300, Denis Vlasenko wrote:
> > On Thursday 30 June 2005 12:19, Arjan van de Ven wrote:
> > > 
> > > > > There are a number of compile-time checks that your patch has removed
> > > > > which catch such things, and as such your patch is not acceptable.
> > > > > Some architectures have a lower threshold of acceptability for the
> > > > > maximum udelay value, so it's absolutely necessary to keep this.
> > > > 
> > > > It removes that check from x86 - other architectures retain it.
> > > > 
> > > > 
> > For users, _any_ value, however large, will work for
> > any delay function.
> 
> that's not desired though. Desired is to limit udelay() to say 2000 or
> so. And force anything above that to go via mdelay() (just to make it
> stand out as broken code ;)

An if(usec > 2000) { printk(..); dump_stack(); } will do.

But do you really want to do this? There might be legitimate reasons
to compute udelay's parameter with results which are sometimes large.

If you really want to, let's decide on this limit now,
before patch cooking. I err to conservative (large) limit
(mostly in order to catch math underflows) or no limit at all.
--
vda

Re: [PATCH] deinline sleep/delay functions

[Russell King]

On Thu, Jun 30, 2005 at 02:10:43PM +0300, Denis Vlasenko wrote:
> On Thursday 30 June 2005 13:47, Arjan van de Ven wrote:
> > On Thu, 2005-06-30 at 13:21 +0300, Denis Vlasenko wrote:
> > > On Thursday 30 June 2005 12:19, Arjan van de Ven wrote:
> > > > 
> > > > > > There are a number of compile-time checks that your patch has removed
> > > > > > which catch such things, and as such your patch is not acceptable.
> > > > > > Some architectures have a lower threshold of acceptability for the
> > > > > > maximum udelay value, so it's absolutely necessary to keep this.
> > > > > 
> > > > > It removes that check from x86 - other architectures retain it.
> > > > > 
> > > > > 
> > > For users, _any_ value, however large, will work for
> > > any delay function.
> > 
> > that's not desired though. Desired is to limit udelay() to say 2000 or
> > so. And force anything above that to go via mdelay() (just to make it
> > stand out as broken code ;)
> 
> An if(usec > 2000) { printk(..); dump_stack(); } will do.

No it won't - that's a run time test which will only get caught if the
code is run.  There's no guarantees of that.

> But do you really want to do this? There might be legitimate reasons
> to compute udelay's parameter with results which are sometimes large.

Yes.  udelay() has overflow issues - if you pass too large a number
to udelay() you get a randomised delay because you've lost the top
bits.

The maximum delay is dependent on the architecture implementation,
and it depends on bogomips.  There is no one single value for it.
Architectures have to decide this from the way that they do the
math and the expected range of bogomips.

Please - leave asm-*/delay.h alone.

-- 
Russell King
 Linux kernel    2.6 ARM Linux   - http://www.arm.linux.org.uk/
 maintainer of:  2.6 Serial core

Re: [PATCH] deinline sleep/delay functions

[Arjan van de Ven]

> An if(usec > 2000) { printk(..); dump_stack(); } will do.

that's runtime not compile time.
The old situation was a compile time check which is far more powerful.

> 
> But do you really want to do this? There might be legitimate reasons
> to compute udelay's parameter with results which are sometimes large.

however that's not valid, because a really large udelay parameter will
cause the delay loop math to overflow. That was the main reason for the
"no more than 2ms or so" restriction.
> 
> If you really want to, let's decide on this limit now,

the existing code already has a limit so why not just use that?

Re: [PATCH] deinline sleep/delay functions

[Denis Vlasenko]

On Thursday 30 June 2005 14:22, Arjan van de Ven wrote:
> 
> > An if(usec > 2000) { printk(..); dump_stack(); } will do.
> 
> that's runtime not compile time.
> The old situation was a compile time check which is far more powerful.

Ok I like compile checks too, it will stay.

But it won't help on accidental mdelay(some math) == mdelay(-1)
== mdelay(4 000 000 000), so we _also_ will have an if() inside
udelay(), ok?

On Thursday 30 June 2005 14:21, Russell King wrote:
> Yes.  udelay() has overflow issues - if you pass too large a number
> to udelay() you get a randomised delay because you've lost the top
> bits.

Thus [umn]delay may fail in unpredictable ways with non-const
parameter which is too big. And this is good exactly why?

I'm ok with making it fail, but _predictably_. With printk(),
trace, whatever.

> The maximum delay is dependent on the architecture implementation,
> and it depends on bogomips.  There is no one single value for it.
> Architectures have to decide this from the way that they do the
> math and the expected range of bogomips.

In example I posted these limitations are lifted. Granted these
limitations were not critical, but removing them can't do harm,
I guess?

> Please - leave asm-*/delay.h alone.

Let's see what udelay(const) will compile down to on ppc:

asm-ppc/delay.h
===============
extern unsigned long loops_per_jiffy;
extern void __delay(unsigned int loops);
...
#define __MAX_UDELAY    (226050910UL/HZ)        /* maximum udelay argument */
#define __MAX_NDELAY    (4294967295UL/HZ)       /* maximum ndelay argument */

extern __inline__ void __udelay(unsigned int x)
{
        unsigned int loops;

        __asm__("mulhwu %0,%1,%2" : "=r" (loops) :
                "r" (x), "r" (loops_per_jiffy * 226));
        __delay(loops);
}

extern __inline__ void __ndelay(unsigned int x)
{
        unsigned int loops;

        __asm__("mulhwu %0,%1,%2" : "=r" (loops) :
                "r" (x), "r" (loops_per_jiffy * 5));
        __delay(loops);
}

extern void __bad_udelay(void);         /* deliberately undefined */
extern void __bad_ndelay(void);         /* deliberately undefined */

#define udelay(n) (__builtin_constant_p(n)? \
        ((n) > __MAX_UDELAY? __bad_udelay(): __udelay((n) * (19 * HZ))) : \
        __udelay((n) * (19 * HZ)))

#define ndelay(n) (__builtin_constant_p(n)? \
        ((n) > __MAX_NDELAY? __bad_ndelay(): __ndelay((n) * HZ)) : \
        __ndelay((n) * HZ))

Thus:

	udelay(const) = loops_per_jiffy * 5; mulhwu thing; call to __delay()

While with proposed code:

	udelay(const) = call to udelay()

Which is smaller.
--
vda

Re: [PATCH] deinline sleep/delay functions

[Maciej W. Rozycki]

On Thu, 30 Jun 2005, Denis Vlasenko wrote:

> I'm ok with making it fail, but _predictably_. With printk(),
> trace, whatever.

 BUG_ON() is probably a good candidate, especially as the implementation 
is expected to be compact and can even be removed for those saving every 
byte by undefining CONFIG_BUG.

  Maciej

Re: [PATCH] deinline sleep/delay functions

[Russell King]

On Thu, Jun 30, 2005 at 02:44:51PM +0300, Denis Vlasenko wrote:
> On Thursday 30 June 2005 14:21, Russell King wrote:
> > The maximum delay is dependent on the architecture implementation,
> > and it depends on bogomips.  There is no one single value for it.
> > Architectures have to decide this from the way that they do the
> > math and the expected range of bogomips.
> 
> In example I posted these limitations are lifted. Granted these
> limitations were not critical, but removing them can't do harm,
> I guess?

They're lifted poorly.  You include a mandatory division in the path.
On systems where division has to be done in code, this is not acceptable,
especially when we're trying to get short delays on embedded CPUs
running below 100MHz.  The time it takes to do the division could
swamp the required delay value.

-- 
Russell King
 Linux kernel    2.6 ARM Linux   - http://www.arm.linux.org.uk/
 maintainer of:  2.6 Serial core

Re: [PATCH] deinline sleep/delay functions

[Denis Vlasenko]

On Thursday 30 June 2005 15:04, Russell King wrote:
> On Thu, Jun 30, 2005 at 02:44:51PM +0300, Denis Vlasenko wrote:
> > On Thursday 30 June 2005 14:21, Russell King wrote:
> > > The maximum delay is dependent on the architecture implementation,
> > > and it depends on bogomips.  There is no one single value for it.
> > > Architectures have to decide this from the way that they do the
> > > math and the expected range of bogomips.
> > 
> > In example I posted these limitations are lifted. Granted these
> > limitations were not critical, but removing them can't do harm,
> > I guess?
> 
> They're lifted poorly.  You include a mandatory division in the path.
> On systems where division has to be done in code, this is not acceptable,
> especially when we're trying to get short delays on embedded CPUs
> running below 100MHz.  The time it takes to do the division could
> swamp the required delay value.

What divisions? Where?

void udelay(unsigned int usecs)
{
        unsigned int k = usecs/1024;
        while (k--)
                __udelay(1024);
        __udelay(usecs % 1024);
}

I see no divisions. I see shifts and ANDs.
I can code them explicitly:

void udelay(unsigned int usecs)
{
        unsigned int k = usecs >> 10; /* divide by 1024 */
        while (k--)
                __udelay(0x400); /* 1024 */
        __udelay(usecs & 0x3ff); /* mod 1024 */
}

Should be ok now.
--
vda

Re: [PATCH] deinline sleep/delay functions

[Vojtech Pavlik]

On Thu, Jun 30, 2005 at 08:52:25AM +0300, Denis Vlasenko wrote:
> Hi Andrew,
> 
> Optimizing delay functions for speed is utterly pointless.
> 
> This patch turns ssleep(n), mdelay(n), udelay(n) and ndelay(n)
> into functions, thus they generate the smallest possible code
> at the callsite. Previously they were more or less inlined.

Optimizing mdelay() and udelay() for speed is pointless, but optimizing
ndelay() makes a lot of sense - if the setup time (call, etc) of the
delay is large, the delay time will be off by many percent. 

-- 
Vojtech Pavlik
SuSE Labs, SuSE CR

Re: [PATCH] deinline sleep/delay functions

[Vojtech Pavlik]

On Thu, Jun 30, 2005 at 12:47:21PM +0200, Arjan van de Ven wrote:
> On Thu, 2005-06-30 at 13:21 +0300, Denis Vlasenko wrote:
> > On Thursday 30 June 2005 12:19, Arjan van de Ven wrote:
> > > 
> > > > > There are a number of compile-time checks that your patch has removed
> > > > > which catch such things, and as such your patch is not acceptable.
> > > > > Some architectures have a lower threshold of acceptability for the
> > > > > maximum udelay value, so it's absolutely necessary to keep this.
> > > > 
> > > > It removes that check from x86 - other architectures retain it.
> > > > 
> > > > 
> > For users, _any_ value, however large, will work for
> > any delay function.
> 
> that's not desired though. Desired is to limit udelay() to say 2000 or
> so. And force anything above that to go via mdelay() (just to make it
> stand out as broken code ;)
> 
> Over time we also want to phase out mdelay of course...
 
The joystick drivers will (sadly) need mdelay forever,
due to hardware crappines.

-- 
Vojtech Pavlik
SuSE Labs, SuSE CR