Re: 64-bit jiffies, a better solution

Re: 64-bit jiffies, a better solution

[Jim Houston]

Hi!

First what problem are you trying to solve?
Why not have both variables and if they happen
to endup in the same cache line you probably 
need years worth of jiffies to notice how
long one more add takes.  E.g.

	jiffies_64++;
	jiffies++;

To round out the list of options, how about a few lines of 
inline asm?  Maybe something like:

   extern unsigned long long jiffie_64;
   extern unsigned int jiffie;
   __asm__ (" \
        .data
        .align  8
        .global jiffie
        .global jiffie_64
        .type   jiffie,@object
        .size   jiffie,4
        .type   jiffie_64,@object
        .size   jiffie_64,8
   jiffie_64:
   jiffie:
        .long   0, 0
   ");

Adding the obvious ifdef of course.  Aside for broken
binutils this might be portable code :-)

Jim Houston - Concurrent Computer
Corp.

Re: 64-bit jiffies, a better solution

[george anzinger]

Jim Houston wrote:
> 
> Hi!
> 
> First what problem are you trying to solve?
> Why not have both variables and if they happen
> to endup in the same cache line you probably
> need years worth of jiffies to notice how
> long one more add takes.  E.g.
> 
>         jiffies_64++;
>         jiffies++;
> 
> To round out the list of options, how about a few lines of
> inline asm?  Maybe something like:
> 
>    extern unsigned long long jiffie_64;
>    extern unsigned int jiffie;
>    __asm__ (" \
>         .data
>         .align  8
>         .global jiffie
>         .global jiffie_64
>         .type   jiffie,@object
>         .size   jiffie,4
>         .type   jiffie_64,@object
>         .size   jiffie_64,8
>    jiffie_64:
>    jiffie:
>         .long   0, 0
>    ");
> 
> Adding the obvious ifdef of course.  Aside for broken
> binutils this might be portable code :-)

Until you move to a big endian 32-bit machine.  I would much rather hear
IS portable.
-- 
George Anzinger   george@mvista.com
High-res-timers:  http://sourceforge.net/projects/high-res-timers/
Real time sched:  http://sourceforge.net/projects/rtsched/
Preemption patch: http://www.kernel.org/pub/linux/kernel/people/rml

Re: How should we do a 64-bit jiffies?

[Keith Owens]

On Mon, 22 Oct 2001 08:12:24 -0700, 
george anzinger <george@mvista.com> wrote:
>I am working on POSIX timers where there is defined a CLOCK_MONOTONIC. 
>The most reasonable implementation of this clock is that it is "uptime"
>or jiffies.  The problem is that it is most definitely not MONOTONIC
>when it rolls back to 0 :(  Thus the need for 64-bits.

If you want to leave existing kernel code alone so it still uses 32 bit
jiffies, just maintain a separate high order 32 bit field which is only
used by the code that really needs it.  On 32 bit machines, the jiffie
code does

  old_jiffies = jiffies++;
  if (jiffies < old_jiffies)
  	++high_jiffies;

You will need a spin lock around that on 32 bit systems, but that is
true for anything that tries to do 64 bit counter updates on a 32 bit
system.  None of your suggestions will work on ix86, it does not
support atomic updates on 64 bit fields in hardware.

Re: How should we do a 64-bit jiffies?

[george anzinger]

Keith Owens wrote:
> 
> On Mon, 22 Oct 2001 08:12:24 -0700,
> george anzinger <george@mvista.com> wrote:
> >I am working on POSIX timers where there is defined a CLOCK_MONOTONIC.
> >The most reasonable implementation of this clock is that it is "uptime"
> >or jiffies.  The problem is that it is most definitely not MONOTONIC
> >when it rolls back to 0 :(  Thus the need for 64-bits.
> 
> If you want to leave existing kernel code alone so it still uses 32 bit
> jiffies, just maintain a separate high order 32 bit field which is only
> used by the code that really needs it.  On 32 bit machines, the jiffie
> code does
> 
>   old_jiffies = jiffies++;
>   if (jiffies < old_jiffies)
>         ++high_jiffies;
> 
> You will need a spin lock around that on 32 bit systems, but that is
> true for anything that tries to do 64 bit counter updates on a 32 bit
> system.  None of your suggestions will work on ix86, it does not
> support atomic updates on 64 bit fields in hardware.

As it turns out I already have a spinlock on the update jiffies code. 
The reason one would want to use a 64-bit integer is that the compiler
does a MUCH better job of the ++, i.e. it just does an add carry.  No
if, no jmp.  I suppose I need to lock the read also, but it is not done
often and will hardly ever block.

I am beginning to think that defining a u64 and casting, i.e.:

#define jiffies (unsigned long volitial)jiffies_u64

is the way to go.

George

64-bit jiffies, a better solution

[george anzinger]

Linus Torvalds wrote:
> 
> In article <3BD52454.218387D9@mvista.com>,
> george anzinger  <george@mvista.com> wrote:
> >
> >I am beginning to think that defining a u64 and casting, i.e.:
> >
> >#define jiffies (unsigned long volitial)jiffies_u64
> >
> >is the way to go.
> 
> ..except for gcc being bad at even 64->32-bit casts like the above.  It
> will usually still load the full 64-bit value, and then only use the low
> bits.
> 
> The efficient and sane way to do it is:
> 
>         /*
>          * The 64-bit value is not volatile - you MUST NOT read it
>          * without holding the spinlock
>          */
>         u64 jiffies_64;
> 
>         /*
>          * Most people don't necessarily care about the full 64-bit
>          * value, so we can just get the "unstable" low bits without
>          * holding the lock. For historical reasons we also mark
>          * it volatile so that busy-waiting doesn't get optimized
>          * away in old drivers.
>          */
>         #if defined(__LITTLE_ENDIAN) || (BITS_PER_LONG > 32)
>         #define jiffies (((volatile unsigned long *)&jiffies_64)[0])
>         #else
>         #define jiffies (((volatile unsigned long *)&jiffies_64)[1])
>         #endif
> 
> which looks ugly, but the ugliness is confined to that one place, and
> none of the users will ever have to care..
> 
>                 Linus

I tried the above and, aside from the numerous cases where "jiffies"
appears
as a dummy variable or a struct/union member which had to be "fixed", I
got 
flack from some folks who thought that:

extern unsigned long jiffies;

should work.  So here is a solution that does all the above and does 
NOT invade new name spaces:

diff -urP -I \$Id:.*Exp \$ -X /usr/src/patch.exclude
linux-2.5.14-org/Makefile linux/Makefile
--- linux-2.5.14-org/Makefile	Tue May  7 16:25:52 2002
+++ linux/Makefile	Thu May  9 18:18:53 2002
@@ -262,6 +262,7 @@
 
 vmlinux: include/linux/version.h $(CONFIGURATION) init/main.o
init/version.o init/do_mounts.o linuxsubdirs
 	$(LD) $(LINKFLAGS) $(HEAD) init/main.o init/version.o init/do_mounts.o
\
+		kernel/jiffies_linker_file.lds \
 		--start-group \
 		$(CORE_FILES) \
 		$(LIBS) \
diff -urP -I \$Id:.*Exp \$ -X /usr/src/patch.exclude
linux-2.5.14-org/include/linux/sched.h linux/include/linux/sched.h
--- linux-2.5.14-org/include/linux/sched.h	Tue May  7 16:57:58 2002
+++ linux/include/linux/sched.h	Thu May  9 17:26:25 2002
@@ -459,6 +459,11 @@
 
 #include <asm/current.h>
 
+/*
+ * The 64-bit value is not volatile - you MUST NOT read it
+ * without holding read_lock_irq(&xtime_lock)
+ */
+extern u64 jiffies_64;
 extern unsigned long volatile jiffies;
 extern unsigned long itimer_ticks;
 extern unsigned long itimer_next;
diff -urP -I \$Id:.*Exp \$ -X /usr/src/patch.exclude
linux-2.5.14-org/kernel/jiffies_linker_file.lds
linux/kernel/jiffies_linker_file.lds
--- linux-2.5.14-org/kernel/jiffies_linker_file.lds	Wed Dec 31 16:00:00
1969
+++ linux/kernel/jiffies_linker_file.lds	Fri May 10 14:10:28 2002
@@ -0,0 +1,14 @@
+/*
+ * This linker script defines jiffies to be either the same as 
+ * jiffies_64 (for little endian or 64 bit machines) or
+ * jiffies_64+4 (for big endian machines)
+ * 
+ * It is intended to satisfy external references to a 32 bit jiffies
which
+ * is the low order 32-bits of a 64-bit jiffies.
+ *
+ * jiffies_at_jiffies_64 needs to be defined if this is a little endian
+ * or a 64-bit machine.
+ * Currently this is done in ..../kernel/timer.c
+ *
+ */
+jiffies =DEFINED(jiffies_at_jiffies_64) ? jiffies_64 : (jiffies_64 +
4);
diff -urP -I \$Id:.*Exp \$ -X /usr/src/patch.exclude
linux-2.5.14-org/kernel/ksyms.c linux/kernel/ksyms.c
--- linux-2.5.14-org/kernel/ksyms.c	Tue May  7 16:25:15 2002
+++ linux/kernel/ksyms.c	Thu May  9 17:21:43 2002
@@ -471,6 +471,7 @@
 EXPORT_SYMBOL_GPL(set_cpus_allowed);
 #endif
 EXPORT_SYMBOL(jiffies);
+EXPORT_SYMBOL(jiffies_64);
 EXPORT_SYMBOL(xtime);
 EXPORT_SYMBOL(do_gettimeofday);
 EXPORT_SYMBOL(do_settimeofday);
diff -urP -I \$Id:.*Exp \$ -X /usr/src/patch.exclude
linux-2.5.14-org/kernel/timer.c linux/kernel/timer.c
--- linux-2.5.14-org/kernel/timer.c	Tue May  7 16:15:52 2002
+++ linux/kernel/timer.c	Fri May 10 14:08:37 2002
@@ -67,7 +67,28 @@
 
 extern int do_setitimer(int, struct itimerval *, struct itimerval *);
 
-unsigned long volatile jiffies;
+/*
+ * The 64-bit value is not volatile - you MUST NOT read it
+ * without holding read_lock_irq(&xtime_lock)
+ */
+u64 jiffies_64;
+/*
+ * Most people don't necessarily care about the full 64-bit
+ * value, so we can just get the "unstable" low bits without
+ * holding the lock. For historical reasons we also mark
+ * it volatile so that busy-waiting doesn't get optimized
+ * away in old drivers.
+ *
+ * This definition depends on the linker defining the actual address of
+ * jiffies using the following (found in
.../kernel/jiffies_linker_file):
+ * jiffies = DEFINED(jiffies_at_jiffies_64) ? jiffies_64 :
jiffies_64+4;
+ */
+#if defined(__LITTLE_ENDIAN) || (BITS_PER_LONG > 32)
+
+char jiffies_at_jiffies_64[0];
+#elif ! defined(__BIG_ENDIAN)
+#ERROR "Neither __LITTLE_ENDIAN nor __BIG_ENDIAN defined "
+#endif
 
 unsigned int * prof_buffer;
 unsigned long prof_len;
@@ -664,7 +685,7 @@
 
 void do_timer(struct pt_regs *regs)
 {
-	(*(unsigned long *)&jiffies)++;
+	(*(u64 *)&jiffies_64)++;
 #ifndef CONFIG_SMP
 	/* SMP process accounting uses the local APIC timer */

----------------------------------------------------------------------

And for those who think doing a ++ on 64-bits is too much to do in an
interrupt,
here is the before / after diff of the asm file for timer.c (messed up a
bit so
patch doesn't get confused):

*-* /usr/src/linux-2.5.14-kb/kernel/timer.o	Fri May 10 14:03:07 2002
*+* /usr/src/linux-2.5.14-kb/kernel/timer.s	Fri May 10 14:02:03 2002
** -1371,7 +1371,8 **
 .globl do_timer
 	.type	 do_timer,@function
 do_timer:
-	incl jiffies
+	addl $1,jiffies_64
+	adcl $0,jiffies_64+4
 	xorl %eax,%eax
 #APP
 	lock ; btsl %eax,bh_task_vec+4
-----------------------------
This solution should work for all platforms and long sizes, does not
depend on asm
and does not invade any new name spaces.

-- 
George Anzinger   george@mvista.com
High-res-timers:  http://sourceforge.net/projects/high-res-timers/
Real time sched:  http://sourceforge.net/projects/rtsched/
Preemption patch: http://www.kernel.org/pub/linux/kernel/people/rml

Re: 64-bit jiffies, a better solution

[Linus Torvalds]

On Fri, 10 May 2002, george anzinger wrote:
> 
> should work.  So here is a solution that does all the above and does 
> NOT invade new name spaces:

Ok, looks fine, but I'd really rather move the "jiffies" linker games
into the per-architecture stuff, and get rid of the jiffies_at_jiffies_64 
games.

It's just one line per architecture, after all.

		Linus

Re: 64-bit jiffies, a better solution

[george anzinger]

Linus Torvalds wrote:
> 
> On Fri, 10 May 2002, george anzinger wrote:
> >
> > should work.  So here is a solution that does all the above and does
> > NOT invade new name spaces:
> 
> Ok, looks fine, but I'd really rather move the "jiffies" linker games
> into the per-architecture stuff, and get rid of the jiffies_at_jiffies_64
> games.
> 
> It's just one line per architecture, after all.
> 
>                 Linus
If that were only true.  The problem is that some architectures can be
built with either endian.  Mips, for example, seems to take the endian
stuff in as an environment variable.  The linker seems to know this
stuff, but does not provide the "built in" to allow it to be used.

The info is available from the header files at compile time, but I could
not find a clean way to export it to the Makefile, where we might choose
which linker script to use.  I suppose we could run the linker script
thru cpp if all else fails.  Any ideas?
-- 
George Anzinger   george@mvista.com
High-res-timers:  http://sourceforge.net/projects/high-res-timers/
Real time sched:  http://sourceforge.net/projects/rtsched/
Preemption patch: http://www.kernel.org/pub/linux/kernel/people/rml

Re: 64-bit jiffies, a better solution

[Linus Torvalds]

On Fri, 10 May 2002, george anzinger wrote:
>
> If that were only true.  The problem is that some architectures can be
> built with either endian.  Mips, for example, seems to take the endian
> stuff in as an environment variable.  The linker seems to know this
> stuff, but does not provide the "built in" to allow it to be used.

Ignore those for now, and let the architecture maintainer sort it out. 
>From what I can tell, those architectures do things like generate the 
linker script dynamically anyway, so..

		Linus

Re: 64-bit jiffies, a better solution

[Maciej W. Rozycki]

On Fri, 10 May 2002, george anzinger wrote:

> If that were only true.  The problem is that some architectures can be
> built with either endian.  Mips, for example, seems to take the endian
> stuff in as an environment variable.  The linker seems to know this
> stuff, but does not provide the "built in" to allow it to be used.

 Huh?  You can use CONFIG_CPU_LITTLE_ENDIAN.  Gcc and the linker for
MIPS/Linux typically support both endiannesses (with a default selected at
their build time) and it's the configuration variable that selects either
of them.

> The info is available from the header files at compile time, but I could
> not find a clean way to export it to the Makefile, where we might choose
> which linker script to use.  I suppose we could run the linker script
> thru cpp if all else fails.  Any ideas?

 CONFIG_CPU_LITTLE_ENDIAN is available to Makefiles.  There used to be
separate linker scripts for different endiannesses for MIPS once. 

-- 
+  Maciej W. Rozycki, Technical University of Gdansk, Poland   +
+--------------------------------------------------------------+
+        e-mail: macro@ds2.pg.gda.pl, PGP key available        +