Skip to contentSkip to conversation

Nasty suprise with uptime

PATCH Petr Vandrovec 8 participants 21 messages Oct 31, 2001 – Nov 2, 2001

Subsystems (11)
lore
Share & tools
lore
#0 lore raw
Quoted 7 lines · Richard B. Johnson

A fix exists, though. The existing, possibly wrong, boot time could be grabbed during the set-time sys-call, the difference between the existing (wrong) time and the boot time could be calculated, the new (correct) time could be set, then the boot-time would be changed to the new correct time, minus the calculated difference. This would result in a correct boot-time.

Quoted 6 lines
    dif_time = time - boot_time;
        time = new_time;
        boot_time = time - dif_time;

Uptime could then be present time minus boot time. No mucking with timer ticks are required.

Hi,
this reminds me. Year or so ago there was patch from someone, which
detected jiffies overflow in /proc/uptime proc_read() code, so only thing you had to do was run 'uptime', 'w', 'top' or something like that every 497 days - you can schedule it as cron job for Jan 1, 0:00:00, to find some workoholics.

Patch was something like:

...
static unsigned long long jiffies_hi = 0;
static unsigned long old_jiffies = 0;
unsigned long jiffy_cache;

/* some spinlock or inode lock or something like that */ jiffy_cache = jiffies;
if (jiffy_cache < old_jiffies) {
jiffies_hi += 1ULL << BITS_PER_LONG;
}
old_jiffies = jiffy_cache;
grand_jiffies = jiffies_hi + jiffy_cache;
/* unlock */
/* now do division and all strange things to format number for userspace */
...

Even if you add running uptime every year to your crontab, it will consume less than 700,000,000 CPU cycles consumed by just 64bit inc in timer interrupt.
Best regards,
Petr Vandrovec [email protected]

#1 lore raw
Quoted 5 lines · Petr Vandrovec

this reminds me. Year or so ago there was patch from someone, which
detected jiffies overflow in /proc/uptime proc_read() code, so only thing you had to do was run 'uptime', 'w', 'top' or something like that every 497 days - you can schedule it as cron job for Jan 1, 0:00:00, to find some workoholics.

Sorry, your posting is 14 minutes too late ;-). I just re-invented this wheel. Such is the pace of Linux kernel development.

Quoted 9 lines

static unsigned long long jiffies_hi = 0;
static unsigned long old_jiffies = 0;
unsigned long jiffy_cache;

/* some spinlock or inode lock or something like that */ jiffy_cache = jiffies;

if (jiffy_cache < old_jiffies) {
   jiffies_hi += 1ULL << BITS_PER_LONG;
}

Ah, my code only stored the high 32 bits of the jiffies_hi, so we don't ever do 64-bit math for this, only a simple increment. Otherwise it is exactly the same, including the "some spinlock or something" comment ;-).

Cheers, Andreas
--
Andreas Dilger
http://sourceforge.net/projects/ext2resize/
http://www-mddsp.enel.ucalgary.ca/People/adilger/

#2 lore raw
In reply to Petr Vandrovec
Quoted 10 lines · Petr Vandrovec

Hi,
this reminds me. Year or so ago there was patch from someone, which
detected jiffies overflow in /proc/uptime proc_read() code, so only thing you had to do was run 'uptime', 'w', 'top' or something like that every 497 days - you can schedule it as cron job for Jan 1, 0:00:00, to find some workoholics.

Patch was something like:

...

OK, to summarize and to not loose the patch again, I made up a final version.

Anyone wanting to donate the stability of his box for linux kernel-development may feel free to try out this patch.

It moves forward the wraparound of the jiffies counter on 32 bit boxes from about 1.3 years after boot to approx 2 min after boot, which seemed to somehow affect stability for my intel box.

As a side effect, if your box does not crash within the next 497.1 days, this patch will allow it to still display correct uptime.

Next step would be to decide what to do with the start_time field of struct task_struct, which is still 32 bit and stores seconds times HZ. Other uses for 64 bit jiffies might be identified as well.

Thanks to all that contributed to the discussion.

Tim

fs/proc/proc_misc.c +13 -8
@@ -39,6 +39,7 @@
 #include <asm/uaccess.h>
 #include <asm/pgtable.h>
 #include <asm/io.h>
+#include <asm/div64.h>
 
 
 #define LOAD_INT(x) ((x) >> FSHIFT)
@@ -103,15 +104,19 @@
 static int uptime_read_proc(char *page, char **start, off_t off,
 				 int count, int *eof, void *data)
 {
-	unsigned long uptime;
+	u64 uptime;
+	unsigned long remainder;
 	unsigned long idle;
 	int len;
 
-	uptime = jiffies;
+	uptime = get_jiffies64() - INITIAL_JIFFIES;
+	remainder = (unsigned long) do_div(uptime, HZ);
+
 	idle = init_tasks[0]->times.tms_utime + init_tasks[0]->times.tms_stime;
 
-	/* The formula for the fraction parts really is ((t * 100) / HZ) % 100, but
-	   that would overflow about every five days at HZ == 100.
+	/* The formula for the fraction part of the idle time really is
+	   ((t * 100) / HZ) % 100, but that would overflow about
+	    every five days at HZ == 100.
 	   Therefore the identity a = (a / b) * b + a % b is used so that it is
 	   calculated as (((t / HZ) * 100) + ((t % HZ) * 100) / HZ) % 100.
 	   The part in front of the '+' always evaluates as 0 (mod 100). All divisions
@@ -121,14 +126,14 @@
 	 */
 #if HZ!=100
 	len = sprintf(page,"%lu.%02lu %lu.%02lu\n",
-		uptime / HZ,
-		(((uptime % HZ) * 100) / HZ) % 100,
+		(unsigned long) uptime,
+		(remainder * 100) / HZ,
 		idle / HZ,
 		(((idle % HZ) * 100) / HZ) % 100);
 #else
 	len = sprintf(page,"%lu.%02lu %lu.%02lu\n",
-		uptime / HZ,
-		uptime % HZ,
+		(unsigned long) uptime,
+		remainder,
 		idle / HZ,
 		idle % HZ);
 #endif
kernel/timer.c +32 -3
@@ -65,7 +65,7 @@
 
 extern int do_setitimer(int, struct itimerval *, struct itimerval *);
 
-unsigned long volatile jiffies;
+unsigned long volatile jiffies = INITIAL_JIFFIES;
 
 unsigned int * prof_buffer;
 unsigned long prof_len;
@@ -117,7 +117,7 @@
 		INIT_LIST_HEAD(tv1.vec + i);
 }
 
-static unsigned long timer_jiffies;
+static unsigned long timer_jiffies = INITIAL_JIFFIES;
 
 static inline void internal_add_timer(struct timer_list *timer)
 {
@@ -638,7 +638,7 @@
 }
 
 /* jiffies at the most recent update of wall time */
-unsigned long wall_jiffies;
+unsigned long wall_jiffies = INITIAL_JIFFIES;
 
 /*
  * This spinlock protect us from races in SMP while playing with xtime. -arca
@@ -683,6 +683,35 @@
 	if (TQ_ACTIVE(tq_timer))
 		mark_bh(TQUEUE_BH);
 }
+
+
+#if BITS_PER_LONG < 48
+
+u64 get_jiffies64(void)
+{
+	static unsigned long jiffies_hi = 0;
+	static unsigned long jiffies_last = INITIAL_JIFFIES;
+	static unsigned long jiffies_tmp;
+
+	jiffies_tmp = jiffies;   /* avoid races */
+	if (jiffies_tmp < jiffies_last) {   /* We have a wrap */
+		jiffies_hi++;
+		jiffies_last = jiffies_tmp;
+	}
+
+	return (jiffies_tmp | ((u64)jiffies_hi) << BITS_PER_LONG);
+}
+
+#else
+ /* jiffies is wide enough to not wrap for 8716 years at HZ==1024 */
+
+static inline u64 get_jiffies64(void)
+{
+	return (u64)jiffies;
+}
+
+#endif /* BITS_PER_LONG < 48 */
+
 
 #if !defined(__alpha__) && !defined(__ia64__)
 
kernel/info.c +5 -1
@@ -12,15 +12,19 @@
 #include <linux/smp_lock.h>
 
 #include <asm/uaccess.h>
+#include <asm/div64.h>
 
 asmlinkage long sys_sysinfo(struct sysinfo *info)
 {
 	struct sysinfo val;
+	u64 uptime;
 
 	memset((char *)&val, 0, sizeof(struct sysinfo));
 
 	cli();
-	val.uptime = jiffies / HZ;
+	uptime = get_jiffies64() - INITIAL_JIFFIES;
+	do_div(uptime, HZ);
+	val.uptime = (unsigned long) uptime;
 
 	val.loads[0] = avenrun[0] << (SI_LOAD_SHIFT - FSHIFT);
 	val.loads[1] = avenrun[1] << (SI_LOAD_SHIFT - FSHIFT);
include/linux/sched.h +3 -0
@@ -543,7 +543,10 @@
 
 #include <asm/current.h>
 
+#define INITIAL_JIFFIES 0xFFFFD000ul
 extern unsigned long volatile jiffies;
+extern u64 get_jiffies64(void);
+
 extern unsigned long itimer_ticks;
 extern unsigned long itimer_next;
 extern struct timeval xtime;
#3 lore raw
In reply to Petr Vandrovec
Quoted 3 lines · Tim Schmielau

Next step would be to decide what to do with the start_time field of struct task_struct, which is still 32 bit and stores seconds times HZ. Other uses for 64 bit jiffies might be identified as well.

I would say that (excluding stability issues because of jiffies wrap) that this is ready for submission to Linus. He may be of the mind that he would rather fix the wrap issues sooner rather than later, or he may want to minimize disruption during the "VM stabilize" period (there are still a couple of hang issues apparently).

Review

Quoted 5 lines
(quoted diff) +5 -0
+u64 get_jiffies64(void)
+{
+	static unsigned long jiffies_hi = 0;
+	static unsigned long jiffies_last = INITIAL_JIFFIES;
+	static unsigned long jiffies_tmp;

^^^^^^ jiffies_tmp doesn't need to be static.

One suggestion someone had was to put dummy "get_jiffies64()" calls in some other infrequently used areas to ensure jiffies_hi is valid if we don't call uptime for 1.3 years after the first wrap. I don't know if that matters or not.

Cheers, Andreas
--
Andreas Dilger
http://sourceforge.net/projects/ext2resize/
http://www-mddsp.enel.ucalgary.ca/People/adilger/

#4 lore raw
Quoted 6 lines · Andreas Dilger

I would say that (excluding stability issues because of jiffies wrap) that this is ready for submission to Linus. He may be of the mind that he would rather fix the wrap issues sooner rather than later, or he may want to minimize disruption during the "VM stabilize" period (there are still a couple of hang issues apparently).

I'd rather object for now. I've had a couple of hard freezes within minutes to hours after jiffies wraparound. Also some KDE applications behave strange, the KDE panel and kterm need approx 2 min to appear even before the wraparound (so it seems to be a sign issue rather than wraparound). I don't want to see this in a stable kernel.

However, I would be pleased if widespread intentional use of the patch would help to solve the remaining wraparound issues.

Quoted 6 lines

Review

Quoted 5 lines
(quoted diff) +5 -0
+u64 get_jiffies64(void)
+{
+	static unsigned long jiffies_hi = 0;
+	static unsigned long jiffies_last = INITIAL_JIFFIES;
+	static unsigned long jiffies_tmp;

^^^^^^ jiffies_tmp doesn't need to be static.

Yes, cut and paste error, sorry. And I wanted this patch to be final for today...

Quoted 6 lines

One suggestion someone had was to put dummy "get_jiffies64()" calls in some other infrequently used areas to ensure jiffies_hi is valid if we don't call uptime for 1.3 years after the first wrap. I don't know if that matters or not.

I don't have enough knowledge of the kernel to find good places. Any suggestions?

Tim

#5 lore raw
Quoted 9 lines · Tim Schmielau
Quoted 6 lines · Andreas Dilger

Review

Quoted 5 lines
(quoted diff) +5 -0
+u64 get_jiffies64(void)
+{
+	static unsigned long jiffies_hi = 0;
+	static unsigned long jiffies_last = INITIAL_JIFFIES;
+	static unsigned long jiffies_tmp;

^^^^^^ jiffies_tmp doesn't need to be static.

Quoted 3 lines

Yes, cut and paste error, sorry. And I wanted this patch to be final for today...

OK, absolutely last patch for today. Sorry to bother everyone, but the jiffies wraparound logic was broken in the previous patch.

As stated before, I would kindly ask for widespread testing PROVIDED IT IS OK FOR YOU TO RISK THE STABILITY OF YOUR BOX!

Tim

fs/proc/proc_misc.c +13 -8
@@ -39,6 +39,7 @@
 #include <asm/uaccess.h>
 #include <asm/pgtable.h>
 #include <asm/io.h>
+#include <asm/div64.h>
 
 
 #define LOAD_INT(x) ((x) >> FSHIFT)
@@ -103,15 +104,19 @@
 static int uptime_read_proc(char *page, char **start, off_t off,
 				 int count, int *eof, void *data)
 {
-	unsigned long uptime;
+	u64 uptime;
+	unsigned long remainder;
 	unsigned long idle;
 	int len;
 
-	uptime = jiffies;
+	uptime = get_jiffies64() - INITIAL_JIFFIES;
+	remainder = (unsigned long) do_div(uptime, HZ);
+
 	idle = init_tasks[0]->times.tms_utime + init_tasks[0]->times.tms_stime;
 
-	/* The formula for the fraction parts really is ((t * 100) / HZ) % 100, but
-	   that would overflow about every five days at HZ == 100.
+	/* The formula for the fraction part of the idle time really is
+	   ((t * 100) / HZ) % 100, but that would overflow about
+	    every five days at HZ == 100.
 	   Therefore the identity a = (a / b) * b + a % b is used so that it is
 	   calculated as (((t / HZ) * 100) + ((t % HZ) * 100) / HZ) % 100.
 	   The part in front of the '+' always evaluates as 0 (mod 100). All divisions
@@ -121,14 +126,14 @@
 	 */
 #if HZ!=100
 	len = sprintf(page,"%lu.%02lu %lu.%02lu\n",
-		uptime / HZ,
-		(((uptime % HZ) * 100) / HZ) % 100,
+		(unsigned long) uptime,
+		(remainder * 100) / HZ,
 		idle / HZ,
 		(((idle % HZ) * 100) / HZ) % 100);
 #else
 	len = sprintf(page,"%lu.%02lu %lu.%02lu\n",
-		uptime / HZ,
-		uptime % HZ,
+		(unsigned long) uptime,
+		remainder,
 		idle / HZ,
 		idle % HZ);
 #endif
kernel/timer.c +31 -3
@@ -65,7 +65,7 @@
 
 extern int do_setitimer(int, struct itimerval *, struct itimerval *);
 
-unsigned long volatile jiffies;
+unsigned long volatile jiffies = INITIAL_JIFFIES;
 
 unsigned int * prof_buffer;
 unsigned long prof_len;
@@ -117,7 +117,7 @@
 		INIT_LIST_HEAD(tv1.vec + i);
 }
 
-static unsigned long timer_jiffies;
+static unsigned long timer_jiffies = INITIAL_JIFFIES;
 
 static inline void internal_add_timer(struct timer_list *timer)
 {
@@ -638,7 +638,7 @@
 }
 
 /* jiffies at the most recent update of wall time */
-unsigned long wall_jiffies;
+unsigned long wall_jiffies = INITIAL_JIFFIES;
 
 /*
  * This spinlock protect us from races in SMP while playing with xtime. -arca
@@ -683,6 +683,34 @@
 	if (TQ_ACTIVE(tq_timer))
 		mark_bh(TQUEUE_BH);
 }
+
+
+#if BITS_PER_LONG < 48
+
+u64 get_jiffies64(void)
+{
+	static unsigned long jiffies_hi = 0;
+	static unsigned long jiffies_last = INITIAL_JIFFIES;
+	unsigned long jiffies_tmp;
+
+	jiffies_tmp = jiffies;   /* avoid races */
+	if (jiffies_tmp < jiffies_last)   /* We have a wrap */
+		jiffies_hi++;
+	jiffies_last = jiffies_tmp;
+
+	return (jiffies_tmp | ((u64)jiffies_hi) << BITS_PER_LONG);
+}
+
+#else
+ /* jiffies is wide enough to not wrap for 8716 years at HZ==1024 */
+
+static inline u64 get_jiffies64(void)
+{
+	return (u64)jiffies;
+}
+
+#endif /* BITS_PER_LONG < 48 */
+
 
 #if !defined(__alpha__) && !defined(__ia64__)
 
kernel/info.c +5 -1
@@ -12,15 +12,19 @@
 #include <linux/smp_lock.h>
 
 #include <asm/uaccess.h>
+#include <asm/div64.h>
 
 asmlinkage long sys_sysinfo(struct sysinfo *info)
 {
 	struct sysinfo val;
+	u64 uptime;
 
 	memset((char *)&val, 0, sizeof(struct sysinfo));
 
 	cli();
-	val.uptime = jiffies / HZ;
+	uptime = get_jiffies64() - INITIAL_JIFFIES;
+	do_div(uptime, HZ);
+	val.uptime = (unsigned long) uptime;
 
 	val.loads[0] = avenrun[0] << (SI_LOAD_SHIFT - FSHIFT);
 	val.loads[1] = avenrun[1] << (SI_LOAD_SHIFT - FSHIFT);
include/linux/sched.h +3 -0
@@ -543,7 +543,10 @@
 
 #include <asm/current.h>
 
+#define INITIAL_JIFFIES 0xFFFFD000ul
 extern unsigned long volatile jiffies;
+extern u64 get_jiffies64(void);
+
 extern unsigned long itimer_ticks;
 extern unsigned long itimer_next;
 extern struct timeval xtime;
#6 lore raw

Tim Schmielau wrote:
~snip

Quoted 10 lines
kernel/timer.c +6 -0
@@ -683,6 +683,34 @@
        if (TQ_ACTIVE(tq_timer))
                mark_bh(TQUEUE_BH);
 }
+
+
+#if BITS_PER_LONG < 48
+
+u64 get_jiffies64(void)
+{

kernel/timer.c line 701

Quoted 10 lines
kernel/timer.c +10 -0
+       static unsigned long jiffies_hi = 0;
+       static unsigned long jiffies_last = INITIAL_JIFFIES;
+       unsigned long jiffies_tmp;
+
+       jiffies_tmp = jiffies;   /* avoid races */
+       if (jiffies_tmp < jiffies_last)   /* We have a wrap */
+               jiffies_hi++;
+       jiffies_last = jiffies_tmp;
+
+       return (jiffies_tmp | ((u64)jiffies_hi) << BITS_PER_LONG);

Doesn't this need to be protected on SMP machines? What if two cpus call get_jiffies64() at the same time... Seems like jiffies_hi could get bumped twice instead of once.

George

#7 lore raw
Quoted 21 lines · george anzinger
Quoted 5 lines · Tim Schmielau
kernel/timer.c +5 -0
+
+#if BITS_PER_LONG < 48
+
+u64 get_jiffies64(void)
+{

kernel/timer.c line 701

Quoted 10 lines
kernel/timer.c +10 -0
+       static unsigned long jiffies_hi = 0;
+       static unsigned long jiffies_last = INITIAL_JIFFIES;
+       unsigned long jiffies_tmp;
+
+       jiffies_tmp = jiffies;   /* avoid races */
+       if (jiffies_tmp < jiffies_last)   /* We have a wrap */
+               jiffies_hi++;
+       jiffies_last = jiffies_tmp;
+
+       return (jiffies_tmp | ((u64)jiffies_hi) << BITS_PER_LONG);

Doesn't this need to be protected on SMP machines? What if two cpus call get_jiffies64() at the same time... Seems like jiffies_hi could get bumped twice instead of once.

Quoted 2 lines

George

Yes, it does, my race protection is bogus. Petr Vandrovec also pointed out that. So we do need either to
a) stuff jiffies_hi and jiffies_last into one atomic type
(16 bits is enough for each) or
b) use locking.
My next patch will use b), but I won't do it until I have resolved the most annoying stability issues. I won't have time to do this before the weekend, and don't want to bother the list too much either.

Maybe the lockups are just due to my setting of INITIAL_JIFFIES instead of waiting 471 days. The time adjustment routines are good candidates for this kind of mistakes. Any ideas anyone where else I might have forgotten to introduce INITIAL_JIFFIES ?

Tim

#14 lore raw
In reply to Tim Schmielau
Quoted 5 lines · Tim Schmielau

OK, absolutely last patch for today. Sorry to bother everyone, but the jiffies wraparound logic was broken in the previous patch.

As stated before, I would kindly ask for widespread testing PROVIDED IT IS OK FOR YOU TO RISK THE STABILITY OF YOUR BOX!

I see you dropped jiffies_hi update in timer int. IMHO argument on wasting 6 CPU cycles or so per each timer int:

- jiffies++;
+ if(++jiffies==0) jiffies_hi++;

is not justified. I'd rather see simple and correct code in timer int rather than jumping thru the hoops in get_jiffies_64().

For CPU cycle saving zealots: I advocate saving 2 static longs in get_jiffies instead :-)
--
vda

#15 lore raw
Quoted 14 lines · vda
Quoted 5 lines · Tim Schmielau

OK, absolutely last patch for today. Sorry to bother everyone, but the jiffies wraparound logic was broken in the previous patch.

As stated before, I would kindly ask for widespread testing PROVIDED IT IS OK FOR YOU TO RISK THE STABILITY OF YOUR BOX!

I see you dropped jiffies_hi update in timer int. IMHO argument on wasting 6 CPU cycles or so per each timer int:

(quoted diff) +1 -1
-	jiffies++;
+	if(++jiffies==0) jiffies_hi++;
Quoted 8 lines

is not justified. I'd rather see simple and correct code in timer int rather than jumping thru the hoops in get_jiffies_64().

For CPU cycle saving zealots: I advocate saving 2 static longs in get_jiffies instead :-)
--
vda
-

Well not exactly zealots. I test a lot of stuff. In fact, the code you propose:

	if(++jiffies==0) jiffies_hi++;

... actually works quite well:

Script started on Thu Nov 1 10:23:54 2001

# ./chk
Simple bump = 13
Bump chk and incr = 15
# ./chk
Simple bump = 13
Bump chk and incr = 15
# ./chk
Simple bump = 13
Bump chk and incr = 15
# exit
exit
Script done on Thu Nov  1 10:24:08 2001

It adds only two CPU clock cycles if (iff) the 'C' compiler is well behaved.

Test code is appended. In the test code, I calculate everything, then print the results. This is so the 'C' library + system call doesn't mess up the cache. Note this if you use this as a template to test other questionable code snippets.

Cheers,
Dick Johnson

Penguin : Linux version 2.4.1 on an i686 machine (799.53 BogoMips).

I was going to compile a list of innovations that could be attributed to Microsoft. Once I realized that Ctrl-Alt-Del was handled in the BIOS, I found that there aren't any.

#17 lore raw
In reply to vda
Quoted 6 lines · Richard B. Johnson

Well not exactly zealots. I test a lot of stuff. In fact, the code you propose:

	if(++jiffies==0) jiffies_hi++;

... actually works quite well:

Uhm, no, it really doesn't. See how it pairs with other instructions and what the cost is when it doesn't have to be as bad:

this:

	unsigned long a, b;
	if (++a == 0) b++;
gives:
        movl    a, %eax
        movl    %esp, %ebp
        incl    %eax
        testl   %eax, %eax
        movl    %eax, a
        je      .L3
.L2:
        popl    %ebp
        ret
        .p2align 4,,7

.L3:
incl b
jmp .L2

which is really gross considering that:

	unsigned long long c;
	c++;

gives:

addl $1, c
adcl $0, c+4

which is quite excellent.

-ben

#18 lore raw
Quoted 34 lines · Benjamin LaHaise
Quoted 6 lines · Richard B. Johnson

Well not exactly zealots. I test a lot of stuff. In fact, the code you propose:

	if(++jiffies==0) jiffies_hi++;

... actually works quite well:

Uhm, no, it really doesn't. See how it pairs with other instructions and what the cost is when it doesn't have to be as bad:

this:

	unsigned long a, b;
	if (++a == 0) b++;
gives:
        movl    a, %eax
        movl    %esp, %ebp
        incl    %eax
        testl   %eax, %eax
        movl    %eax, a
        je      .L3
.L2:
        popl    %ebp
        ret
        .p2align 4,,7

.L3:
incl b
jmp .L2

which is really gross considering that:

	unsigned long long c;
	c++;
Quoted 9 lines

gives:

addl $1, c
adcl $0, c+4

which is quite excellent.

-ben

Look I tested it, and I provided code to test it! You will not convince the 'C' compiler to do:

	addl	$1, c
	adcl	$0, c+4

... with a long long (at least not egcs-2.91.66). Further, that's not the whole story. If jiffies is a long long, then every operation on that counter, all the timing queues, sleeps, etc., end up doing multiple operations on the long long (which I showed on Monday with some additional, best possible, code).

... which is code I showed initially. Knowing that the C compiler does the jumps on condition and tests for zero, even after the flags have been set by the previous operation, I tested what the result was. It turns out that it's only a couple of clock cycles, not the 6 extra clocks that the hand calculation shows.

So, if you leave jiffies alone, but bump another variable when it wraps, you get to eat your cake and keep it too.

Cheers,
Dick Johnson

Penguin : Linux version 2.4.1 on an i686 machine (799.53 BogoMips).

I was going to compile a list of innovations that could be attributed to Microsoft. Once I realized that Ctrl-Alt-Del was handled in the BIOS, I found that there aren't any.

#19 lore raw
In reply to Benjamin LaHaise
Quoted 4 lines · Richard B. Johnson

does the jumps on condition and tests for zero, even after the flags have been set by the previous operation, I tested what the result was. It turns out that it's only a couple of clock cycles, not the 6 extra clocks that the hand calculation shows.

*sigh* You're not testing any of the effects on available execution resources within the processor.

Quoted 2 lines

So, if you leave jiffies alone, but bump another variable when it wraps, you get to eat your cake and keep it too.

As Linus pointed out, using casting tricks with a long long will just work for this case. Sounds good to me.

-ben

#16 lore raw
In reply to Richard B. Johnson
Quoted 26 lines · Richard B. Johnson
Quoted 14 lines · vda
Quoted 5 lines · Tim Schmielau

OK, absolutely last patch for today. Sorry to bother everyone, but the jiffies wraparound logic was broken in the previous patch.

As stated before, I would kindly ask for widespread testing PROVIDED IT IS OK FOR YOU TO RISK THE STABILITY OF YOUR BOX!

I see you dropped jiffies_hi update in timer int. IMHO argument on wasting 6 CPU cycles or so per each timer int:

(quoted diff) +1 -1
-     jiffies++;
+     if(++jiffies==0) jiffies_hi++;
Quoted 8 lines

is not justified. I'd rather see simple and correct code in timer int rather than jumping thru the hoops in get_jiffies_64().

For CPU cycle saving zealots: I advocate saving 2 static longs in get_jiffies instead :-)
--
vda
-

Quoted 7 lines

Well not exactly zealots. I test a lot of stuff. In fact, the code you propose:

        if(++jiffies==0) jiffies_hi++;

... actually works quite well:

I think that bumping a u64 is actually faster. We have to remember that this code is executed every 10 ms. It is not in a loop. This means that the chance of branch prediction being available is nil. In this case the processor will predict the branch as not taken and be wrong (except for once every 1.3 years).

On the other hand, the u64 bump has no branches, just an add carry. This amounts to 1 add carry each bump (assuming we can get cc to do the add carry to memory) and no branches to predict. We should also take care to put the u64 in one cache line, of course.

George

Quoted 35 lines

Script started on Thu Nov 1 10:23:54 2001

# ./chk
Simple bump = 13
Bump chk and incr = 15
# ./chk
Simple bump = 13
Bump chk and incr = 15
# ./chk
Simple bump = 13
Bump chk and incr = 15
# exit
exit
Script done on Thu Nov  1 10:24:08 2001

It adds only two CPU clock cycles if (iff) the 'C' compiler is well behaved.

Test code is appended. In the test code, I calculate everything, then print the results. This is so the 'C' library + system call doesn't mess up the cache. Note this if you use this as a template to test other questionable code snippets.

Cheers,
Dick Johnson

Penguin : Linux version 2.4.1 on an i686 machine (799.53 BogoMips).

I was going to compile a list of innovations that could be attributed to Microsoft. Once I realized that Ctrl-Alt-Del was handled in the BIOS, I found that there aren't any.

------------------------------------------------------------------------
Name: test_jiff.tar.gz
test_jiff.tar.gz Type: Unix Tape Archive (application/x-tar)
Encoding: BASE64

#8 lore raw
In reply to Tim Schmielau
Quoted 2 lines · Tim Schmielau

On Thu, 1 Nov 2001, george anzinger wrote:

[...]

Quoted 16 lines
Quoted 6 lines

Doesn't this need to be protected on SMP machines? What if two cpus call get_jiffies64() at the same time... Seems like jiffies_hi could get bumped twice instead of once.

George

Yes, it does, my race protection is bogus. Petr Vandrovec also pointed out that. So we do need either to
a) stuff jiffies_hi and jiffies_last into one atomic type
(16 bits is enough for each) or
b) use locking.
My next patch will use b), but I won't do it until I have resolved the most annoying stability issues. I won't have time to do this before the weekend, and don't want to bother the list too much either.

Quoted 5 lines

Maybe the lockups are just due to my setting of INITIAL_JIFFIES instead of waiting 471 days. The time adjustment routines are good candidates for this kind of mistakes. Any ideas anyone where else I might have forgotten to introduce INITIAL_JIFFIES ?

Well, I did the next patch without waiting for progress on the stability front (fsck still in heavy use here). As an excercise I added proper locking to get_jiffies64().

Actually, it is not decided yet whether jiffies_hi should be incremented in get_jiffies64() or in do_timer(), and whether jiffies and jiffies_hi should be glued together to form a 64 bit value, so the innards of get_jiffies64() might change again.

However, no objections have been raised on the interface, so I started to add some uses of it. I bumped up the start_time field of struct task_struct to 64 bits, so that ps output will still be ok after the 32 bit wraparound. This change might break userland applications that expect the /proc/#/stat fields to fit in 32 bit variables. Yet this is not a regression as the kernel was broken for these cases until now.

As a side effect, the problem of the current get_jiffies64() implementation loosing jiffie wraparounds is weakened further. With the current patch wraparounds can only be lost if no processes are started or finished for 497 days, a condition that I can only imagine to be met by embedded devices.

Tim

fs/proc/proc_misc.c +13 -8
@@ -39,6 +39,7 @@
 #include <asm/uaccess.h>
 #include <asm/pgtable.h>
 #include <asm/io.h>
+#include <asm/div64.h>
 
 
 #define LOAD_INT(x) ((x) >> FSHIFT)
@@ -103,15 +104,19 @@
 static int uptime_read_proc(char *page, char **start, off_t off,
 				 int count, int *eof, void *data)
 {
-	unsigned long uptime;
+	u64 uptime;
+	unsigned long remainder;
 	unsigned long idle;
 	int len;
 
-	uptime = jiffies;
+	uptime = get_jiffies64() - INITIAL_JIFFIES;
+	remainder = (unsigned long) do_div(uptime, HZ);
+
 	idle = init_tasks[0]->times.tms_utime + init_tasks[0]->times.tms_stime;
 
-	/* The formula for the fraction parts really is ((t * 100) / HZ) % 100, but
-	   that would overflow about every five days at HZ == 100.
+	/* The formula for the fraction part of the idle time really is
+	   ((t * 100) / HZ) % 100, but that would overflow about
+	    every five days at HZ == 100.
 	   Therefore the identity a = (a / b) * b + a % b is used so that it is
 	   calculated as (((t / HZ) * 100) + ((t % HZ) * 100) / HZ) % 100.
 	   The part in front of the '+' always evaluates as 0 (mod 100). All divisions
@@ -121,14 +126,14 @@
 	 */
 #if HZ!=100
 	len = sprintf(page,"%lu.%02lu %lu.%02lu\n",
-		uptime / HZ,
-		(((uptime % HZ) * 100) / HZ) % 100,
+		(unsigned long) uptime,
+		(remainder * 100) / HZ,
 		idle / HZ,
 		(((idle % HZ) * 100) / HZ) % 100);
 #else
 	len = sprintf(page,"%lu.%02lu %lu.%02lu\n",
-		uptime / HZ,
-		uptime % HZ,
+		(unsigned long) uptime,
+		remainder,
 		idle / HZ,
 		idle % HZ);
 #endif
kernel/timer.c +34 -3
@@ -65,7 +65,7 @@
 
 extern int do_setitimer(int, struct itimerval *, struct itimerval *);
 
-unsigned long volatile jiffies;
+unsigned long volatile jiffies = INITIAL_JIFFIES;
 
 unsigned int * prof_buffer;
 unsigned long prof_len;
@@ -117,7 +117,7 @@
 		INIT_LIST_HEAD(tv1.vec + i);
 }
 
-static unsigned long timer_jiffies;
+static unsigned long timer_jiffies = INITIAL_JIFFIES;
 
 static inline void internal_add_timer(struct timer_list *timer)
 {
@@ -638,7 +638,7 @@
 }
 
 /* jiffies at the most recent update of wall time */
-unsigned long wall_jiffies;
+unsigned long wall_jiffies = INITIAL_JIFFIES;
 
 /*
  * This spinlock protect us from races in SMP while playing with xtime. -arca
@@ -683,6 +683,37 @@
 	if (TQ_ACTIVE(tq_timer))
 		mark_bh(TQUEUE_BH);
 }
+
+
+#if BITS_PER_LONG < 48
+
+u64 get_jiffies64(void)
+{
+	static unsigned long jiffies_hi = 0;
+	static unsigned long jiffies_last = INITIAL_JIFFIES;
+	static spinlock_t jiffies64_lock = SPIN_LOCK_UNLOCKED;
+	unsigned long jiffies_tmp;
+
+	spin_lock(&jiffies64_lock);
+	jiffies_tmp = jiffies;   /* avoid races */
+	if (jiffies_tmp < jiffies_last)   /* We have a wrap */
+		jiffies_hi++;
+	jiffies_last = jiffies_tmp;
+	spin_unlock(&jiffies64_lock);
+
+	return (jiffies_tmp | ((u64)jiffies_hi) << BITS_PER_LONG);
+}
+
+#else
+ /* jiffies is wide enough to not wrap for 8716 years at HZ==1024 */
+
+static inline u64 get_jiffies64(void)
+{
+	return (u64)jiffies;
+}
+
+#endif /* BITS_PER_LONG < 48 */
+
 
 #if !defined(__alpha__) && !defined(__ia64__)
 
kernel/info.c +5 -1
@@ -12,15 +12,19 @@
 #include <linux/smp_lock.h>
 
 #include <asm/uaccess.h>
+#include <asm/div64.h>
 
 asmlinkage long sys_sysinfo(struct sysinfo *info)
 {
 	struct sysinfo val;
+	u64 uptime;
 
 	memset((char *)&val, 0, sizeof(struct sysinfo));
 
 	cli();
-	val.uptime = jiffies / HZ;
+	uptime = get_jiffies64() - INITIAL_JIFFIES;
+	do_div(uptime, HZ);
+	val.uptime = (unsigned long) uptime;
 
 	val.loads[0] = avenrun[0] << (SI_LOAD_SHIFT - FSHIFT);
 	val.loads[1] = avenrun[1] << (SI_LOAD_SHIFT - FSHIFT);
include/linux/sched.h +4 -1
@@ -351,7 +351,7 @@
 	unsigned long it_real_incr, it_prof_incr, it_virt_incr;
 	struct timer_list real_timer;
 	struct tms times;
-	unsigned long start_time;
+	u64 start_time;
 	long per_cpu_utime[NR_CPUS], per_cpu_stime[NR_CPUS];
 /* mm fault and swap info: this can arguably be seen as either mm-specific or thread-specific */
 	unsigned long min_flt, maj_flt, nswap, cmin_flt, cmaj_flt, cnswap;
@@ -543,7 +543,10 @@
 
 #include <asm/current.h>
 
+#define INITIAL_JIFFIES ((unsigned long)(-120*HZ))
 extern unsigned long volatile jiffies;
+extern u64 get_jiffies64(void);
+
 extern unsigned long itimer_ticks;
 extern unsigned long itimer_next;
 extern struct timeval xtime;
kernel/fork.c +1 -1
@@ -647,7 +647,7 @@
 	}
 #endif
 	p->lock_depth = -1;		/* -1 = no lock */
-	p->start_time = jiffies;
+	p->start_time = get_jiffies64();
 
 	INIT_LIST_HEAD(&p->local_pages);
 
kernel/acct.c +23 -10
@@ -56,6 +56,7 @@
 #include <linux/tty.h>
 
 #include <asm/uaccess.h>
+#include <asm/div64.h>
 
 /*
  * These constants control the amount of freespace that suspend and
@@ -227,20 +228,24 @@
  *  This routine has been adopted from the encode_comp_t() function in
  *  the kern_acct.c file of the FreeBSD operating system. The encoding
  *  is a 13-bit fraction with a 3-bit (base 8) exponent.
+ *
+ *  Bumped up to encode 64 bit values. Unfortunately the result may
+ *  overflow now.
  */
 
 #define	MANTSIZE	13			/* 13 bit mantissa. */
-#define	EXPSIZE		3			/* Base 8 (3 bit) exponent. */
+#define	EXPSIZE		3			/* 3 bit exponent. */
+#define	EXPBASE		3			/* Base 8 (3 bit) exponent. */
 #define	MAXFRACT	((1 << MANTSIZE) - 1)	/* Maximum fractional value. */
 
-static comp_t encode_comp_t(unsigned long value)
+static comp_t encode_comp_t(u64 value)
 {
 	int exp, rnd;
 
 	exp = rnd = 0;
 	while (value > MAXFRACT) {
-		rnd = value & (1 << (EXPSIZE - 1));	/* Round up? */
-		value >>= EXPSIZE;	/* Base 8 exponent == 3 bit shift. */
+		rnd = value & (1 << (EXPBASE - 1));	/* Round up? */
+		value >>= EXPBASE;	/* Base 8 exponent == 3 bit shift. */
 		exp++;
 	}
 
@@ -248,16 +253,21 @@
          * If we need to round up, do it (and handle overflow correctly).
          */
 	if (rnd && (++value > MAXFRACT)) {
-		value >>= EXPSIZE;
+		value >>= EXPBASE;
 		exp++;
 	}
 
 	/*
          * Clean it up and polish it off.
          */
-	exp <<= MANTSIZE;		/* Shift the exponent into place */
-	exp += value;			/* and add on the mantissa. */
-	return exp;
+	if (exp >= (1 << EXPSIZE)) {
+		/* Overflow. Return largest representable number instead */
+		return (1 << (MANTSIZE + EXPSIZE)) - 1;
+	} else {
+		exp <<= MANTSIZE;	/* Shift the exponent into place */
+		exp += value;		/* and add on the mantissa. */
+		return exp;
+	}
 }
 
 /*
@@ -277,6 +287,7 @@
 	struct acct ac;
 	mm_segment_t fs;
 	unsigned long vsize;
+	u64 elapsed;
 
 	/*
 	 * First check to see if there is enough free_space to continue
@@ -294,8 +305,10 @@
 	strncpy(ac.ac_comm, current->comm, ACCT_COMM);
 	ac.ac_comm[ACCT_COMM - 1] = '\0';
 
-	ac.ac_btime = CT_TO_SECS(current->start_time) + (xtime.tv_sec - (jiffies / HZ));
-	ac.ac_etime = encode_comp_t(jiffies - current->start_time);
+	elapsed = get_jiffies64() - current->start_time;
+	ac.ac_etime = encode_comp_t(elapsed);
+	do_div(elapsed, HZ);
+	ac.ac_btime = xtime.tv_sec - elapsed;
 	ac.ac_utime = encode_comp_t(current->times.tms_utime);
 	ac.ac_stime = encode_comp_t(current->times.tms_stime);
 	ac.ac_uid = current->uid;
fs/proc/array.c +2 -2
@@ -343,7 +343,7 @@
 	ppid = task->pid ? task->p_opptr->pid : 0;
 	read_unlock(&tasklist_lock);
 	res = sprintf(buffer,"%d (%s) %c %d %d %d %d %d %lu %lu \
-%lu %lu %lu %lu %lu %ld %ld %ld %ld %ld %ld %lu %lu %ld %lu %lu %lu %lu %lu \
+%lu %lu %lu %lu %lu %ld %ld %ld %ld %ld %ld %llu %lu %ld %lu %lu %lu %lu %lu \
 %lu %lu %lu %lu %lu %lu %lu %lu %d %d\n",
 		task->pid,
 		task->comm,
@@ -366,7 +366,7 @@
 		nice,
 		0UL /* removed */,
 		task->it_real_value,
-		task->start_time,
+		(unsigned long long)(task->start_time - INITIAL_JIFFIES),
 		vsize,
 		mm ? mm->rss : 0, /* you might want to shift this left 3 */
 		task->rlim[RLIMIT_RSS].rlim_cur,
#9 lore raw
In reply to Tim Schmielau
Quoted 3 lines · Tim Schmielau

Well, I did the next patch without waiting for progress on the stability front (fsck still in heavy use here). As an excercise I added proper locking to get_jiffies64().

Looks good.

fs/proc/proc_misc.c line 132

Quoted 11 lines
fs/proc/proc_misc.c +2 -2
 	idle = init_tasks[0]->times.tms_utime + init_tasks[0]->times.tms_stime;
[snip]
 	 */
 #if HZ!=100
 	len = sprintf(page,"%lu.%02lu %lu.%02lu\n",
-		uptime / HZ,
-		(((uptime % HZ) * 100) / HZ) % 100,
+		(unsigned long) uptime,
+		(remainder * 100) / HZ,
 		idle / HZ,
 		(((idle % HZ) * 100) / HZ) % 100);

Probably need to make idle a 64-bit value as well, even if the individual items are not, just to avoid potential overflow... Calling do_div(idle,HZ) may end up being just as fast as the hoops we jump through above to calculate the fractions (2 divides, 2 modulus, and one multiply).

Cheers, Andreas
--
Andreas Dilger
http://sourceforge.net/projects/ext2resize/
http://www-mddsp.enel.ucalgary.ca/People/adilger/

#13 lore raw
In reply to Tim Schmielau

In article <[email protected]>,

Quoted 2 lines · Andreas Dilger

Probably need to make idle a 64-bit value as well, even if the individual items are not, just to avoid potential overflow...

Well idle will still overflow after a bit more than 497 days on a typical system that is 99% idle, if init_tasks[0]->times.tms_{u,s}time are left at 32 bits.

Mike.

Signature · 2 lines
"Only two things are infinite, the universe and human stupidity,
 and I'm not sure about the former" -- Albert Einstein.
#20 lore raw
In reply to Benjamin LaHaise
Quoted 5 lines · Benjamin LaHaise
Quoted 2 lines

So, if you leave jiffies alone, but bump another variable when it wraps, you get to eat your cake and keep it too.

As Linus pointed out, using casting tricks with a long long will just work for this case. Sounds good to me.

I'm using these dirty tricks often. Too often in fact, it hurts readability and violates "make it simple if you can" principle.
Look at this diff of "simple" and "optimized" version:

-unsigned long jiffies = INITIAL_JIFFIES; -unsigned long jiffies_hi = 0;
+/* vda: need to enforce 8 byte alignment - how??? */ +#if defined(__LITTLE_ENDIAN) && (BITS_PER_LONG == 32)
+ unsigned long jiffies = INITIAL_JIFFIES;
+ unsigned long jiffies_hi = 0;
+#elif defined(__BIG_ENDIAN) && (BITS_PER_LONG == 32)
+ unsigned long jiffies_hi = 0;
+ unsigned long jiffies = INITIAL_JIFFIES;
+#elif (BITS_PER_LONG == 64)
+ unsigned long jiffies = INITIAL_JIFFIES;
+#else
+#error Fix me somebody please....
+#endif

...

+ if(++jiffies==0) jiffies_hi++;
+#if defined(__LITTLE_ENDIAN) && (BITS_PER_LONG == 32)
+ (*(unsigned long long*)&jiffies)++;
+#elif defined(__BIG_ENDIAN) && (BITS_PER_LONG == 32)
+ (*(unsigned long long*)&jiffies_hi)++;
+#elif (BITS_PER_LONG == 64)
+ jiffies++;
+#else
+#error Fix me somebody please....
+#endif

Does saving 600 CPU cycles per second (0.000001 of your CPU power) worth this mess?
I think not. Let's hope gcc will get smarter some day :-) --
vda

#10 lore raw
In reply to Andreas Dilger
Quoted 24 lines · Andreas Dilger
Quoted 3 lines · Tim Schmielau

Well, I did the next patch without waiting for progress on the stability front (fsck still in heavy use here). As an excercise I added proper locking to get_jiffies64().

Looks good.

Review

Quoted 11 lines
(quoted diff) +2 -2
 	idle = init_tasks[0]->times.tms_utime + init_tasks[0]->times.tms_stime;
[snip]
 	 */
 #if HZ!=100
 	len = sprintf(page,"%lu.%02lu %lu.%02lu\n",
-		uptime / HZ,
-		(((uptime % HZ) * 100) / HZ) % 100,
+		(unsigned long) uptime,
+		(remainder * 100) / HZ,
 		idle / HZ,
 		(((idle % HZ) * 100) / HZ) % 100);

Probably need to make idle a 64-bit value as well, even if the individual items are not, just to avoid potential overflow... Calling do_div(idle,HZ) may end up being just as fast as the hoops we jump through above to calculate the fractions (2 divides, 2 modulus, and one multiply).

Quoted 1 line

Cheers, Andreas

I made up another patch as an RFC where this overflow is dealt with in the same way as the jiffies wraparound. This will prevent wrong display of idle time if /proc/uptime is read at least every 497 days.
The CPU time of the idle task will still overflow as it will for every other process getting more than 497.1 days of CPU time, but I don't want to blow up every time variable. I believe this to be acceptable behavior.

I think I have to give up on my stability problem. I see hard lockups on SMP as well as UP at random times after the jiffies wrap. Another problem surprises me: Sometimes I get quite an unresponsive system even before jiffie wrap, sometimes not. Seems as some important timing parameter sometimes gets detected wrong at boot time if INITIAL_JIFFIES is large. The bogomips value, however, is always correct.

As suggested elsewhere, I made the pre-wrap INITIAL_JIFFIES value a config option, so anybody might decide by himself to hunt down these problems or not.
I kindly ask people to turn this on and help getting the issues sorted out, as I don't want to imply a false feeling of safety with this patch by hiding the jiffies wraparound from the user.

I will let this patch float around for some days to get feedback, and then suggest it for inclusion into the mainline kernel.
I believe the ongoing discussion of a "real" 64 bit jiffie counter not to interfere with this goal, since this can also be done at any later time with the get_jiffies64() interface remaining unchanged.

Thanks all for your comments.

Tim

fs/proc/proc_misc.c +44 -21
@@ -39,6 +39,7 @@
 #include <asm/uaccess.h>
 #include <asm/pgtable.h>
 #include <asm/io.h>
+#include <asm/div64.h>
 
 
 #define LOAD_INT(x) ((x) >> FSHIFT)
@@ -100,37 +101,59 @@
 	return proc_calc_metrics(page, start, off, count, eof, len);
 }
 
+#if BITS_PER_LONG < 48
+
+u64 get_idle64(void)
+{
+	static unsigned long idle_hi, idle_last;
+	static spinlock_t idle64_lock = SPIN_LOCK_UNLOCKED;
+	unsigned long idle;
+
+	spin_lock(&idle64_lock);
+	idle = init_tasks[0]->times.tms_utime + init_tasks[0]->times.tms_stime;
+	if (idle < idle_last)   /* We have a wrap */
+		idle_hi++;
+	idle_last = idle;
+	spin_unlock(&idle64_lock);
+
+	return (idle | ((u64)idle_hi) << BITS_PER_LONG);
+}
+
+#else
+ /* Idle time won't overflow for 8716 years at HZ==1024 */
+
+static inline u64 get_idle64(void)
+{
+	return (u64)(init_tasks[0]->times.tms_utime
+	             + init_tasks[0]->times.tms_stime);
+}
+
+#endif /* BITS_PER_LONG < 48 */
+
 static int uptime_read_proc(char *page, char **start, off_t off,
 				 int count, int *eof, void *data)
 {
-	unsigned long uptime;
-	unsigned long idle;
+	u64 uptime, idle;
+	unsigned long uptime_remainder, idle_remainder;
 	int len;
 
-	uptime = jiffies;
-	idle = init_tasks[0]->times.tms_utime + init_tasks[0]->times.tms_stime;
+	uptime = get_jiffies64() - INITIAL_JIFFIES;
+	uptime_remainder = (unsigned long) do_div(uptime, HZ);
+	idle = get_idle64();
+	idle_remainder = (unsigned long) do_div(idle, HZ);
 
-	/* The formula for the fraction parts really is ((t * 100) / HZ) % 100, but
-	   that would overflow about every five days at HZ == 100.
-	   Therefore the identity a = (a / b) * b + a % b is used so that it is
-	   calculated as (((t / HZ) * 100) + ((t % HZ) * 100) / HZ) % 100.
-	   The part in front of the '+' always evaluates as 0 (mod 100). All divisions
-	   in the above formulas are truncating. For HZ being a power of 10, the
-	   calculations simplify to the version in the #else part (if the printf
-	   format is adapted to the same number of digits as zeroes in HZ.
-	 */
 #if HZ!=100
 	len = sprintf(page,"%lu.%02lu %lu.%02lu\n",
-		uptime / HZ,
-		(((uptime % HZ) * 100) / HZ) % 100,
-		idle / HZ,
-		(((idle % HZ) * 100) / HZ) % 100);
+		(unsigned long) uptime,
+		(uptime_remainder * 100) / HZ,
+		(unsigned long) idle,
+		(idle_remainder * 100) / HZ);
 #else
 	len = sprintf(page,"%lu.%02lu %lu.%02lu\n",
-		uptime / HZ,
-		uptime % HZ,
-		idle / HZ,
-		idle % HZ);
+		(unsigned long) uptime,
+		uptime_remainder,
+		(unsigned long) idle,
+		idle_remainder);
 #endif
 	return proc_calc_metrics(page, start, off, count, eof, len);
 }
kernel/timer.c +34 -3
@@ -65,7 +65,7 @@
 
 extern int do_setitimer(int, struct itimerval *, struct itimerval *);
 
-unsigned long volatile jiffies;
+unsigned long volatile jiffies = INITIAL_JIFFIES;
 
 unsigned int * prof_buffer;
 unsigned long prof_len;
@@ -117,7 +117,7 @@
 		INIT_LIST_HEAD(tv1.vec + i);
 }
 
-static unsigned long timer_jiffies;
+static unsigned long timer_jiffies = INITIAL_JIFFIES;
 
 static inline void internal_add_timer(struct timer_list *timer)
 {
@@ -638,7 +638,7 @@
 }
 
 /* jiffies at the most recent update of wall time */
-unsigned long wall_jiffies;
+unsigned long wall_jiffies = INITIAL_JIFFIES;
 
 /*
  * This spinlock protect us from races in SMP while playing with xtime. -arca
@@ -683,6 +683,37 @@
 	if (TQ_ACTIVE(tq_timer))
 		mark_bh(TQUEUE_BH);
 }
+
+
+#if BITS_PER_LONG < 48
+
+u64 get_jiffies64(void)
+{
+	static unsigned long jiffies_hi = 0;
+	static unsigned long jiffies_last = INITIAL_JIFFIES;
+	static spinlock_t jiffies64_lock = SPIN_LOCK_UNLOCKED;
+	unsigned long jiffies_tmp;
+
+	spin_lock(&jiffies64_lock);
+	jiffies_tmp = jiffies;   /* avoid races */
+	if (jiffies_tmp < jiffies_last)   /* We have a wrap */
+		jiffies_hi++;
+	jiffies_last = jiffies_tmp;
+	spin_unlock(&jiffies64_lock);
+
+	return (jiffies_tmp | ((u64)jiffies_hi) << BITS_PER_LONG);
+}
+
+#else
+ /* jiffies is wide enough to not wrap for 8716 years at HZ==1024 */
+
+static inline u64 get_jiffies64(void)
+{
+	return (u64)jiffies;
+}
+
+#endif /* BITS_PER_LONG < 48 */
+
 
 #if !defined(__alpha__) && !defined(__ia64__)
 
kernel/info.c +5 -1
@@ -12,15 +12,19 @@
 #include <linux/smp_lock.h>
 
 #include <asm/uaccess.h>
+#include <asm/div64.h>
 
 asmlinkage long sys_sysinfo(struct sysinfo *info)
 {
 	struct sysinfo val;
+	u64 uptime;
 
 	memset((char *)&val, 0, sizeof(struct sysinfo));
 
 	cli();
-	val.uptime = jiffies / HZ;
+	uptime = get_jiffies64() - INITIAL_JIFFIES;
+	do_div(uptime, HZ);
+	val.uptime = (unsigned long) uptime;
 
 	val.loads[0] = avenrun[0] << (SI_LOAD_SHIFT - FSHIFT);
 	val.loads[1] = avenrun[1] << (SI_LOAD_SHIFT - FSHIFT);
include/linux/sched.h +8 -1
@@ -351,7 +351,7 @@
 	unsigned long it_real_incr, it_prof_incr, it_virt_incr;
 	struct timer_list real_timer;
 	struct tms times;
-	unsigned long start_time;
+	u64 start_time;
 	long per_cpu_utime[NR_CPUS], per_cpu_stime[NR_CPUS];
 /* mm fault and swap info: this can arguably be seen as either mm-specific or thread-specific */
 	unsigned long min_flt, maj_flt, nswap, cmin_flt, cmaj_flt, cnswap;
@@ -543,7 +543,14 @@
 
 #include <asm/current.h>
 
+#ifdef CONFIG_DEBUG_JIFFIEWRAP
+# define INITIAL_JIFFIES ((unsigned long)(-300*HZ))
+#else
+# define INITIAL_JIFFIES 0
+#endif
 extern unsigned long volatile jiffies;
+extern u64 get_jiffies64(void);
+
 extern unsigned long itimer_ticks;
 extern unsigned long itimer_next;
 extern struct timeval xtime;
kernel/fork.c +1 -1
@@ -647,7 +647,7 @@
 	}
 #endif
 	p->lock_depth = -1;		/* -1 = no lock */
-	p->start_time = jiffies;
+	p->start_time = get_jiffies64();
 
 	INIT_LIST_HEAD(&p->local_pages);
 
kernel/acct.c +23 -10
@@ -56,6 +56,7 @@
 #include <linux/tty.h>
 
 #include <asm/uaccess.h>
+#include <asm/div64.h>
 
 /*
  * These constants control the amount of freespace that suspend and
@@ -227,20 +228,24 @@
  *  This routine has been adopted from the encode_comp_t() function in
  *  the kern_acct.c file of the FreeBSD operating system. The encoding
  *  is a 13-bit fraction with a 3-bit (base 8) exponent.
+ *
+ *  Bumped up to encode 64 bit values. Unfortunately the result may
+ *  overflow now.
  */
 
 #define	MANTSIZE	13			/* 13 bit mantissa. */
-#define	EXPSIZE		3			/* Base 8 (3 bit) exponent. */
+#define	EXPSIZE		3			/* 3 bit exponent. */
+#define	EXPBASE		3			/* Base 8 (3 bit) exponent. */
 #define	MAXFRACT	((1 << MANTSIZE) - 1)	/* Maximum fractional value. */
 
-static comp_t encode_comp_t(unsigned long value)
+static comp_t encode_comp_t(u64 value)
 {
 	int exp, rnd;
 
 	exp = rnd = 0;
 	while (value > MAXFRACT) {
-		rnd = value & (1 << (EXPSIZE - 1));	/* Round up? */
-		value >>= EXPSIZE;	/* Base 8 exponent == 3 bit shift. */
+		rnd = value & (1 << (EXPBASE - 1));	/* Round up? */
+		value >>= EXPBASE;	/* Base 8 exponent == 3 bit shift. */
 		exp++;
 	}
 
@@ -248,16 +253,21 @@
          * If we need to round up, do it (and handle overflow correctly).
          */
 	if (rnd && (++value > MAXFRACT)) {
-		value >>= EXPSIZE;
+		value >>= EXPBASE;
 		exp++;
 	}
 
 	/*
          * Clean it up and polish it off.
          */
-	exp <<= MANTSIZE;		/* Shift the exponent into place */
-	exp += value;			/* and add on the mantissa. */
-	return exp;
+	if (exp >= (1 << EXPSIZE)) {
+		/* Overflow. Return largest representable number instead */
+		return (1 << (MANTSIZE + EXPSIZE)) - 1;
+	} else {
+		exp <<= MANTSIZE;	/* Shift the exponent into place */
+		exp += value;		/* and add on the mantissa. */
+		return exp;
+	}
 }
 
 /*
@@ -277,6 +287,7 @@
 	struct acct ac;
 	mm_segment_t fs;
 	unsigned long vsize;
+	u64 elapsed;
 
 	/*
 	 * First check to see if there is enough free_space to continue
@@ -294,8 +305,10 @@
 	strncpy(ac.ac_comm, current->comm, ACCT_COMM);
 	ac.ac_comm[ACCT_COMM - 1] = '\0';
 
-	ac.ac_btime = CT_TO_SECS(current->start_time) + (xtime.tv_sec - (jiffies / HZ));
-	ac.ac_etime = encode_comp_t(jiffies - current->start_time);
+	elapsed = get_jiffies64() - current->start_time;
+	ac.ac_etime = encode_comp_t(elapsed);
+	do_div(elapsed, HZ);
+	ac.ac_btime = xtime.tv_sec - elapsed;
 	ac.ac_utime = encode_comp_t(current->times.tms_utime);
 	ac.ac_stime = encode_comp_t(current->times.tms_stime);
 	ac.ac_uid = current->uid;
fs/proc/array.c +2 -2
@@ -343,7 +343,7 @@
 	ppid = task->pid ? task->p_opptr->pid : 0;
 	read_unlock(&tasklist_lock);
 	res = sprintf(buffer,"%d (%s) %c %d %d %d %d %d %lu %lu \
-%lu %lu %lu %lu %lu %ld %ld %ld %ld %ld %ld %lu %lu %ld %lu %lu %lu %lu %lu \
+%lu %lu %lu %lu %lu %ld %ld %ld %ld %ld %ld %llu %lu %ld %lu %lu %lu %lu %lu \
 %lu %lu %lu %lu %lu %lu %lu %lu %d %d\n",
 		task->pid,
 		task->comm,
@@ -366,7 +366,7 @@
 		nice,
 		0UL /* removed */,
 		task->it_real_value,
-		task->start_time,
+		(unsigned long long)(task->start_time),
 		vsize,
 		mm ? mm->rss : 0, /* you might want to shift this left 3 */
 		task->rlim[RLIMIT_RSS].rlim_cur,
Documentation/Configure.help +8 -0
@@ -18530,6 +18530,14 @@
   Say Y here if you want the low-level print routines to direct their
   output to the serial port in the DC21285 (Footbridge).
 
+Debug jiffie counter wraparound (DANGEROUS)
+CONFIG_DEBUG_JIFFIEWRAP
+  Say Y here to initialize the jiffie counter to a value 5 minutes
+  before wraparound. This may make your system UNSTABLE and its
+  only use is to hunt down the causes of this instability.
+  If you don't know what the jiffie counter is or if you want
+  a stable system, say N.
+
 Split initialisation functions into discardable section
 CONFIG_TEXT_SECTIONS
   If you say Y here, kernel code that is only used during
arch/i386/config.in +1 -0
@@ -404,6 +404,7 @@
    bool '  Magic SysRq key' CONFIG_MAGIC_SYSRQ
    bool '  Spinlock debugging' CONFIG_DEBUG_SPINLOCK
    bool '  Verbose BUG() reporting (adds 70K)' CONFIG_DEBUG_BUGVERBOSE
+   bool '  Debug jiffie counter wraparound (DANGEROUS)' CONFIG_DEBUG_JIFFIEWRAP
 fi
 
 endmenu
arch/m68k/config.in +1 -0
@@ -545,4 +545,5 @@
 
 #bool 'Debug kmalloc/kfree' CONFIG_DEBUG_MALLOC
 bool 'Magic SysRq key' CONFIG_MAGIC_SYSRQ
+bool 'Debug jiffie counter wraparound (DANGEROUS)' CONFIG_DEBUG_JIFFIEWRAP
 endmenu
arch/mips/config.in +1 -0
@@ -519,4 +519,5 @@
 if [ "$CONFIG_SMP" != "y" ]; then
    bool 'Run uncached' CONFIG_MIPS_UNCACHED
 fi
+bool 'Debug jiffie counter wraparound (DANGEROUS)' CONFIG_DEBUG_JIFFIEWRAP
 endmenu
arch/parisc/config.in +1 -0
@@ -206,5 +206,6 @@
 
 #bool 'Debug kmalloc/kfree' CONFIG_DEBUG_MALLOC
 bool 'Magic SysRq key' CONFIG_MAGIC_SYSRQ
+bool 'Debug jiffie counter wraparound (DANGEROUS)' CONFIG_DEBUG_JIFFIEWRAP
 endmenu
 
arch/ppc/config.in +1 -0
@@ -388,4 +388,5 @@
 bool 'Magic SysRq key' CONFIG_MAGIC_SYSRQ
 bool 'Include kgdb kernel debugger' CONFIG_KGDB
 bool 'Include xmon kernel debugger' CONFIG_XMON
+bool 'Debug jiffie counter wraparound (DANGEROUS)' CONFIG_DEBUG_JIFFIEWRAP
 endmenu
arch/sparc/config.in +1 -0
@@ -265,4 +265,5 @@
 comment 'Kernel hacking'
 
 bool 'Magic SysRq key' CONFIG_MAGIC_SYSRQ
+bool 'Debug jiffie counter wraparound (DANGEROUS)' CONFIG_DEBUG_JIFFIEWRAP
 endmenu
arch/sh/config.in +1 -0
@@ -385,4 +385,5 @@
 if [ "$CONFIG_SH_STANDARD_BIOS" = "y" ]; then
    bool 'Early printk support' CONFIG_SH_EARLY_PRINTK
 fi
+bool 'Debug jiffie counter wraparound (DANGEROUS)' CONFIG_DEBUG_JIFFIEWRAP
 endmenu
arch/arm/config.in +1 -0
@@ -578,6 +578,7 @@
 bool 'Magic SysRq key' CONFIG_MAGIC_SYSRQ
 bool 'Spinlock debugging' CONFIG_DEBUG_SPINLOCK
 dep_bool 'Disable pgtable cache' CONFIG_NO_PGT_CACHE $CONFIG_CPU_26
+bool 'Debug jiffie counter wraparound (DANGEROUS)' CONFIG_DEBUG_JIFFIEWRAP
 # These options are only for real kernel hackers who want to get their hands dirty.
 dep_bool 'Kernel low-level debugging functions' CONFIG_DEBUG_LL $CONFIG_EXPERIMENTAL
 dep_bool '  Kernel low-level debugging messages via footbridge serial port' CONFIG_DEBUG_DC21285_PORT $CONFIG_DEBUG_LL $CONFIG_FOOTBRIDGE
arch/cris/config.in +1 -0
@@ -250,4 +250,5 @@
 if [ "$CONFIG_PROFILE" = "y" ]; then
   int ' Profile shift count' CONFIG_PROFILE_SHIFT 2
 fi
+bool 'Debug jiffie counter wraparound (DANGEROUS)' CONFIG_DEBUG_JIFFIEWRAP
 endmenu
#11 lore raw
In reply to Andreas Dilger
Quoted 6 lines · Tim Schmielau

I made up another patch as an RFC where this overflow is dealt with in the same way as the jiffies wraparound. This will prevent wrong display of idle time if /proc/uptime is read at least every 497 days.
The CPU time of the idle task will still overflow as it will for every other process getting more than 497.1 days of CPU time, but I don't want to blow up every time variable. I believe this to be acceptable behavior.

I would agree.

Quoted 6 lines

I think I have to give up on my stability problem. I see hard lockups on SMP as well as UP at random times after the jiffies wrap. Another problem surprises me: Sometimes I get quite an unresponsive system even before jiffie wrap, sometimes not. Seems as some important timing parameter sometimes gets detected wrong at boot time if INITIAL_JIFFIES is large. The bogomips value, however, is always correct.

This is an expected symptom of broken code not dealing with jiffies wrap properly. Something is waiting for a timeout that won't happen for another 1.3 years.

AFAIK, in the 2.1 kernel development days there was an audit of all users of jiffies so that they properly used (there are macros time_before() and time_after() which are supposed to handle jiffies wrap). I imagine that if you did a grep on jiffies for the drivers you use, you would find that lots of code is again doing "time + foo > jiffies" or similar, which is broken for wrap.

Quoted 5 lines

As suggested elsewhere, I made the pre-wrap INITIAL_JIFFIES value a config option, so anybody might decide by himself to hunt down these problems or not. I kindly ask people to turn this on and help getting the issues sorted out, as I don't want to imply a false feeling of safety with this patch by hiding the jiffies wraparound from the user.

Maybe not in the 2.4 kernel, but definitely in the 2.5 kernel Linus will enable this as a "no-option option", just like he did with SMP in older development kernels. It _may_ be that the Chief Penguin will put his foot (flipper?) down and enable it for 2.4 as well, just to get it fixed ASAP. Otherwise it just means that there will be an upper bound on how long a 2.4 kernel can run.

Quoted 3 lines

I believe the ongoing discussion of a "real" 64 bit jiffie counter not to interfere with this goal, since this can also be done at any later time with the get_jiffies64() interface remaining unchanged.

I agree. Do we need a 64-bit jiffies value for gettimeofday, or is this handled by the CPU TSC these days? I'm not really aware of other places that would need a 64-bit value in a fast path (such that locking and a function call to get_jiffies64() is unacceptable).

Cheers, Andreas
--
Andreas Dilger
http://sourceforge.net/projects/ext2resize/
http://www-mddsp.enel.ucalgary.ca/People/adilger/

#12 lore raw

possibly incorrect comparisons of jiffies in linux kernel

On Fri, 2 Nov 2001, Andreas Dilger wrote:

[talking about hard freezes of my box after wraparound of the
jiffie counter]

Quoted 7 lines

AFAIK, in the 2.1 kernel development days there was an audit of all users of jiffies so that they properly used (there are macros time_before() and time_after() which are supposed to handle jiffies wrap). I imagine that if you did a grep on jiffies for the drivers you use, you would find that lots of code is again doing "time + foo > jiffies" or similar, which is broken for wrap.

Well, on a quick inspection of the sources I found 171 files where jiffies are compared without using time_before() or time_after(). I didn't bother to find out whether or not they actually get the wraparound wrong. IMHO for ease of audit all of these should use the macros.
Maybe this audit is a candidate for the CHECKER project?

Unfortunately I currently don't have much time to spend on kernel hacking, so listing these files is about all I can do.

Tim

Here comes the list. Don't beat me about false positives or false negatives please, I was quite tired when assembling it. No flamewars were intended by this post!

net/core/dev.c
net/core/neighbour.c
net/ipv4/arp.c
net/ipv4/route.c
net/ipv4/route.c
net/ipv4/igmp.c
net/ipv4/ip_gre.c
net/ipv4/ipmr.c
net/ipv4/tcp_timer.c
net/ipv4/tcp_ipv4.c
net/ipv4/ipconfig.c
net/ipv4/tcp_minisocks.c
net/decnet/af_decnet.c
net/decnet/dn_dev.c
net/decnet/dn_nsp_out.c
net/decnet/dn_route.c
net/decnet/dn_timer.c
net/econet/af_econet.c
net/sched/sch_generic.c
net/irda/discovery.c
net/irda/irnet/irnet_irda.c
drivers/net/slip.c
drivers/net/ne.c
drivers/net/cs89x0.c
drivers/net/atp.c
drivers/net/eexpress.c
drivers/net/apne.c
drivers/net/hp100.c
drivers/net/wan/sdla_fr.c
drivers/net/wan/sdla_ppp.c
drivers/net/wan/sdla_x25.c
drivers/net/wan/sdla_chdlc.c
drivers/net/wan/comx-hw-comx.c
drivers/net/wan/comx-hw-mixcom.c
drivers/net/wan/lmc/lmc_debug.c
drivers/net/wan/lmc/lmc_main.c
drivers/net/wan/dscc4.c
drivers/net/wan/hdlc.c
drivers/net/wan/sdla_ft1.c
drivers/net/wan/wanpipe_multppp.c
drivers/net/seeq8005.c
drivers/net/3c59x.c
drivers/net/3c523.c
drivers/net/eth16i.c
drivers/net/tokenring/olympic.c
drivers/net/tokenring/lanstreamer.c
drivers/net/hamradio/baycom_par.c
drivers/net/hamradio/baycom_ser_fdx.c
drivers/net/hamradio/mkiss.c
drivers/net/hamradio/soundmodem/sm.c
drivers/net/hamradio/soundmodem/sm_wss.c
drivers/net/hamradio/dmascc.c
drivers/net/hamradio/baycom_epp.c
drivers/net/hamradio/yam.c
drivers/net/shaper.c
drivers/net/es3210.c
drivers/net/oaknet.c
drivers/net/sis900.c
drivers/net/arlan.c
drivers/net/arcnet/arcnet.c
drivers/net/ppp_async.c
drivers/net/aironet4500_core.c
drivers/net/ne2k-pci.c
drivers/net/sb1000.c
drivers/net/dmfe.c
drivers/net/rrunner.c
drivers/net/ariadne2.c
drivers/net/ne2.c
drivers/net/tulip/pnic.c
drivers/net/fc/iph5526.c
drivers/net/pcmcia/3c589_cs.c
drivers/net/pcmcia/pcnet_cs.c
drivers/net/pcmcia/netwave_cs.c
drivers/net/pcmcia/smc91c92_cs.c
drivers/net/pcmcia/wavelan_cs.c
drivers/net/aironet4500_card.c
drivers/net/mac89x0.c
drivers/net/appletalk/cops.c
drivers/block/floppy.c
drivers/block/paride/pseudo.h
drivers/char/lp.c
drivers/char/esp.c
drivers/char/serial.c
drivers/char/tpqic02.c
drivers/char/rtc.c
drivers/char/synclink.c
drivers/char/mxser.c
drivers/char/ip2main.c
drivers/char/ip2/i2lib.c
drivers/char/moxa.c
drivers/char/drm/i810_dma.c
drivers/char/agp/agpgart_be.c
drivers/scsi/eata.c
drivers/scsi/53c7,8xx.c
drivers/scsi/ppa.c
drivers/scsi/eata_generic.h
drivers/scsi/qlogicfc.c
drivers/scsi/BusLogic.c
drivers/scsi/megaraid.c
drivers/scsi/wd7000.c
drivers/scsi/53c7xx.c
drivers/scsi/qlogicfas.c
drivers/scsi/u14-34f.c
drivers/scsi/scsi_obsolete.c
drivers/scsi/gdth_proc.c
drivers/scsi/imm.c
drivers/scsi/mac_scsi.c
drivers/scsi/i91uscsi.c
drivers/scsi/i60uscsi.c
drivers/scsi/sym53c416.c
drivers/scsi/sym53c8xx_defs.h
drivers/scsi/sun3_scsi.c
drivers/scsi/cpqfcTSstructs.h
drivers/scsi/osst.c
drivers/sound/pss.c
drivers/sound/sb_common.c
drivers/sound/ymfpci.c
drivers/sound/vwsnd.c
drivers/cdrom/sonycd535.c
drivers/isdn/isdn_net.c
drivers/isdn/isdn_tty.c
drivers/isdn/eicon/eicon_idi.c
drivers/isdn/eicon/eicon_isa.c
drivers/isdn/tpam/tpam_commands.c
drivers/sbus/char/aurora.c
drivers/ide/ide-cd.c
drivers/ide/ide-features.c
drivers/ide/ide-probe.c
drivers/ide/ide-proc.c
drivers/ide/ide-tape.c
drivers/ide/ide.c
drivers/sgi/char/ds1286.c
drivers/fc4/fc.c
drivers/acorn/net/ether3.c
drivers/usb/usb-uhci.c
drivers/usb/serial/digi_acceleport.c
drivers/usb/serial/keyspan.c
drivers/usb/storage/isd200.c
drivers/tc/zs.c
drivers/atm/iphase.c
drivers/atm/fore200e.c
drivers/pcmcia/i82365.c
drivers/i2c/i2c-algo-bit.c
drivers/i2c/i2c-adap-ite.c
drivers/s390/misc/chandev.c
drivers/media/radio/radio-aimslab.c
drivers/media/video/c-qcam.c
drivers/media/video/w9966.c
drivers/media/video/zr36067.c
drivers/acpi/ospm/processor/prpower.c
drivers/mtd/chips/sharp.c
drivers/mtd/devices/doc1000.c
drivers/md/md.c
drivers/message/fusion/mptscsih.c
drivers/message/i2o/i2o_core.c
arch/i386/kernel/apm.c
arch/i386/kernel/io_apic.c
arch/alpha/kernel/traps.c
arch/alpha/kernel/time.c
arch/mips/jazz/reset.c
arch/mips/baget/vacserial.c
arch/mips/au1000/common/serial.c
arch/ppc/8xx_io/uart.c
arch/ppc/8260_io/uart.c
arch/sparc64/kernel/binfmt_aout32.c
arch/ia64/kernel/irq_ia64.c
arch/ia64/kernel/unaligned.c
arch/cris/drivers/ethernet.c
arch/cris/drivers/ide.c
arch/cris/drivers/serial.c
arch/cris/drivers/usb-host.c