[PATCH ] POSIX clocks & timers take 15 (NOT HIGH RES)

From: george anzinger <george@mvista.com>
To: Linus Torvalds <torvalds@transmeta.com>
Cc: "linux-kernel@vger.kernel.org" <linux-kernel@vger.kernel.org>
Subject: [PATCH ] POSIX clocks & timers take 15 (NOT HIGH RES)
Date: Wed, 27 Nov 2002 16:42:28 -0800	[thread overview]
Message-ID: <3DE56674.2EEAF989@mvista.com> (raw)

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

Have a nice turkey day :)

This patch has no configure options!  

With this version I have changed the signal/ repeating timer
model to avoid timer storms from repeating timers.  The
timer is not inserted back into the timer_list until the
signal is dequeued by the receiving task.  So, once a timer
expires, it will cause NO further system overhead until the
task takes the signal, regardless of the repeat interval. 
The POSIX standard allows this, (actually it seems to
encourage it).  Each timer has an "overrun" counter that
keeps track of the number of times the signal should have
been generated but was not because the prior signal was not
yet picked up.

The timer_gettime() call returns the time as if the timer
were in the timer_list so to the program it looks like it
is, but the system overhead is nil.

The really nice thing about this way of limiting timer
storms is that a really fast real time program can actually
get the high turn over rate while not being impacted by
slower, or blocked programs trying to do the same thing. 
Like wise, if a program loses the cpu, its timers will not
impact other tasks.  Many thanks to Mark Salisbury
<mbs@mc.com> for suggesting this.

The patch stands alone (i.e. does not require any of the
following high-res patches).

This, patch implements the POSIX clocks and timers
functions.  The two standard clocks are
defined(CLOCK_REALTIME & CLOCK_MONOTONIC). 

Nano_sleep() is rolled into clock_nanosleep().  Also a bug
fix in clock_nanosleep().

kernel/timer.c is modified to remove the timer_t typedef
which conflicts with the POSIX standard definition for this
type.  

The patch introduces a new kernel source (posix-timers.c)
which contains most of the code.

This implementation has no limits on the number of
timers in the system or per process or task, thanks to Jim
Houston.

Kernel version 2.5.50


Test programs, man pages and readme files as well as this
patch are available on the sourceforge high-res-timers site: 

http://sourceforge.net/projects/high-res-timers/

Please apply.

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

[-- Attachment #2: hrtimers-hrposix-2.5.50-1.0.patch --]
[-- Type: text/plain, Size: 10865 bytes --]

diff -urP -I \$Id:.*Exp \$ -X /usr/src/patch.exclude linux-2.5.50-i386/include/linux/posix-timers.h linux/include/linux/posix-timers.h

--- linux-2.5.50-i386/include/linux/posix-timers.h	Wed Nov 27 15:50:41 2002
+++ linux/include/linux/posix-timers.h	Wed Nov 27 15:52:55 2002
@@ -15,6 +15,38 @@
 	 void ( *timer_get)(struct k_itimer *timr,
 			   struct itimerspec *cur_setting);
 };
+
+#ifdef CONFIG_HIGH_RES_TIMERS
+struct now_struct{ 
+	unsigned long jiffies;
+	long sub_jiffie;
+};
+static inline void posix_get_now(struct now_struct *now)
+{
+	(now)->jiffies = jiffies;
+	(now)->sub_jiffie = quick_update_jiffies_sub((now)->jiffies);
+	while (unlikely(((now)->sub_jiffie - cycles_per_jiffies) > 0)){
+		(now)->sub_jiffie = (now)->sub_jiffie - cycles_per_jiffies;
+		(now)->jiffies++;
+	}
+}
+
+#define posix_time_before(timer, now) \
+         ( {long diff = (long)(timer)->expires - (long)(now)->jiffies;  \
+           (diff < 0) ||                                      \
+	   ((diff == 0) && ((timer)->sub_expires < (now)->sub_jiffie)); })
+
+#define posix_bump_timer(timr) do { \
+          (timr)->it_timer.expires += (timr)->it_incr; \
+          (timr)->it_timer.sub_expires += (timr)->it_sub_incr; \
+          if (((timr)->it_timer.sub_expires - cycles_per_jiffies) >= 0){ \
+		  (timr)->it_timer.sub_expires -= cycles_per_jiffies; \
+		  (timr)->it_timer.expires++; \
+	  }                                 \
+          (timr)->it_overrun++;               \
+        }while (0)
+              
+#else
 struct now_struct{ 
 	unsigned long jiffies;
 };
@@ -26,4 +58,5 @@
                         (timr)->it_timer.expires += (timr)->it_incr; \
                         (timr)->it_overrun++;               \
                        }while (0)
+#endif // CONFIG_HIGH_RES_TIMERS
 #endif
diff -urP -I \$Id:.*Exp \$ -X /usr/src/patch.exclude linux-2.5.50-i386/include/linux/sched.h linux/include/linux/sched.h
--- linux-2.5.50-i386/include/linux/sched.h	Wed Nov 27 15:50:41 2002
+++ linux/include/linux/sched.h	Wed Nov 27 15:52:55 2002
@@ -290,6 +290,9 @@
 	int it_sigev_signo;		 /* signo word of sigevent struct */
 	sigval_t it_sigev_value;	 /* value word of sigevent struct */
 	unsigned long it_incr;		/* interval specified in jiffies */
+#ifdef CONFIG_HIGH_RES_TIMERS
+        int it_sub_incr;                /* sub jiffie part of interval */
+#endif
 	struct task_struct *it_process;	/* process to send signal to */
 	struct timer_list it_timer;
 };
diff -urP -I \$Id:.*Exp \$ -X /usr/src/patch.exclude linux-2.5.50-i386/kernel/posix-timers.c linux/kernel/posix-timers.c
--- linux-2.5.50-i386/kernel/posix-timers.c	Wed Nov 27 15:50:41 2002
+++ linux/kernel/posix-timers.c	Wed Nov 27 15:52:57 2002
@@ -22,6 +22,7 @@
 #include <linux/init.h>
 #include <linux/compiler.h>
 #include <linux/id_reuse.h>
+#include <linux/hrtime.h>
 #include <linux/posix-timers.h>
 
 #ifndef div_long_long_rem
@@ -176,6 +177,15 @@
 	posix_timers_cache = kmem_cache_create("posix_timers_cache",
 		sizeof(struct k_itimer), 0, 0, 0, 0);
 	idr_init(&posix_timers_id);
+	IF_HIGH_RES(clock_realtime.res = CONFIG_HIGH_RES_RESOLUTION;
+		    register_posix_clock(CLOCK_REALTIME_HR,&clock_realtime);
+		    clock_monotonic.res = CONFIG_HIGH_RES_RESOLUTION;
+		    register_posix_clock(CLOCK_MONOTONIC_HR,&clock_monotonic);
+;
+		);
+#ifdef	 final_clock_init
+	final_clock_init();	  // defined by arch header file
+#endif
 	return 0;
 }
 
@@ -216,8 +226,23 @@
 	 * We trust that the optimizer will use the remainder from the 
 	 * above div in the following operation as long as they are close. 
 	 */
-	return	0;
+	return	 (nsec_to_arch_cycles(nsec % (NSEC_PER_SEC / HZ)));
+}
+#ifdef CONFIG_HIGH_RES_TIMERS
+static void tstotimer(struct itimerspec * time, struct k_itimer * timer)
+{
+	int res = posix_clocks[timer->it_clock].res;
+
+	timer->it_timer.sub_expires = tstojiffie(&time->it_value,
+						 res,
+						 &timer->it_timer.expires);
+	timer->it_sub_incr = tstojiffie(&time->it_interval,
+					res,
+					(unsigned long*) &timer->it_incr);
+	if ((unsigned long)timer->it_incr > MAX_JIFFY_OFFSET)
+		timer->it_incr = MAX_JIFFY_OFFSET;
 }
+#else
 static void tstotimer(struct itimerspec * time, struct k_itimer * timer)
 {
 	int res = posix_clocks[timer->it_clock].res;
@@ -230,6 +255,7 @@
 }
  
 
+#endif
 
 static void schedule_next_timer(struct k_itimer * timr)
 {
@@ -237,6 +263,7 @@
 
 	/* Set up the timer for the next interval (if there is one) */
 	if (timr->it_incr == 0){
+		IF_HIGH_RES(if(timr->it_sub_incr == 0))
 			{
 				set_timer_inactive(timr);
 				return;
@@ -308,7 +335,7 @@
 	info.si_code = SI_TIMER;
 	info.si_tid = timr->it_id;
 	info.si_value = timr->it_sigev_value;
-	if ( timr->it_incr == 0){
+	if ( (timr->it_incr == 0) IF_HIGH_RES( && (timr->it_sub_incr == 0))){
 		set_timer_inactive(timr);
 	}else{
 		timr->it_requeue_pending = info.si_sys_private = 1;
@@ -609,12 +636,13 @@
 void inline do_timer_gettime(struct k_itimer *timr,
 			     struct itimerspec *cur_setting)
 {
-	long sub_expires;
+	long sub_expires; 
 	unsigned long expires;
 	struct now_struct now;		
 
 	do {
 		expires = timr->it_timer.expires;  
+		IF_HIGH_RES(sub_expires = timr->it_timer.sub_expires);
 	} while ((volatile long)(timr->it_timer.expires) != expires);
 
 	posix_get_now(&now);
@@ -623,6 +651,7 @@
 	     (timr->it_sigev_notify & SIGEV_NONE) && 
 	     ! timr->it_incr){
 		if (posix_time_before(&timr->it_timer,&now)){
+			IF_HIGH_RES(timr->it_timer.sub_expires = )
 			timr->it_timer.expires = expires = 0;
 		}
 	}
@@ -639,11 +668,29 @@
 		}
 		if ( expires){		
 			expires -= now.jiffies;
+			IF_HIGH_RES(sub_expires -=  now.sub_jiffie);
 		}
 	}
 	jiffies_to_timespec(expires, &cur_setting->it_value);
 	jiffies_to_timespec(timr->it_incr, &cur_setting->it_interval);
 
+	IF_HIGH_RES(cur_setting->it_value.tv_nsec += 
+		    arch_cycles_to_nsec( sub_expires);
+		    if (cur_setting->it_value.tv_nsec < 0){
+			    cur_setting->it_value.tv_nsec += NSEC_PER_SEC;
+			    cur_setting->it_value.tv_sec--;
+		    }
+		    if ((cur_setting->it_value.tv_nsec - NSEC_PER_SEC) >= 0){
+			    cur_setting->it_value.tv_nsec -= NSEC_PER_SEC;
+			    cur_setting->it_value.tv_sec++;
+		    }
+		    cur_setting->it_interval.tv_nsec += 
+		    arch_cycles_to_nsec(timr->it_sub_incr);
+		    if ((cur_setting->it_interval.tv_nsec - NSEC_PER_SEC) >= 0){
+			    cur_setting->it_interval.tv_nsec -= NSEC_PER_SEC;
+			    cur_setting->it_interval.tv_sec++;
+		    }
+		);	     
 	if (cur_setting->it_value.tv_sec < 0){
 		cur_setting->it_value.tv_nsec = 1;
 		cur_setting->it_value.tv_sec = 0;
@@ -775,6 +822,7 @@
 
 	/* disable the timer */
 	timr->it_incr = 0;
+	IF_HIGH_RES(timr->it_sub_incr = 0);
 	/* 
 	 * careful here.  If smp we could be in the "fire" routine which will
 	 * be spinning as we hold the lock.  But this is ONLY an SMP issue.
@@ -804,6 +852,7 @@
 	if ((new_setting->it_value.tv_sec == 0) &&
 	    (new_setting->it_value.tv_nsec == 0)) {
 		timr->it_timer.expires = 0;
+		IF_HIGH_RES(timr->it_timer.sub_expires = 0 );
 		return 0;
 	}
 
@@ -819,14 +868,19 @@
 	tstotimer(new_setting,timr);
 
 	/*
-	 * For some reason the timer does not fire immediately if expires is
-	 * equal to jiffies, so the timer notify function is called directly.
+
+	 * For some reason the timer does not fire immediately if
+	 * expires is equal to jiffies and the old cascade timer list,
+	 * so the timer notify function is called directly. 
 	 * We do not even queue SIGEV_NONE timers!
+
 	 */
 	if (! (timr->it_sigev_notify & SIGEV_NONE)) {
+#ifndef	 CONFIG_HIGH_RES_TIMERS
 		if (timr->it_timer.expires == jiffies) {
 			timer_notify_task(timr);
 		}else
+#endif
 			add_timer(&timr->it_timer);
 	}
 	return 0;
@@ -887,6 +941,7 @@
 static inline int do_timer_delete(struct k_itimer  *timer)
 {
 	timer->it_incr = 0;
+	IF_HIGH_RES(timer->it_sub_incr = 0);
 #ifdef CONFIG_SMP
 	if ( timer_active(timer) && 
 	     ! del_timer(&timer->it_timer) &&
@@ -987,8 +1042,25 @@
 		return clock->clock_get(tp);
 	}
 
+#ifdef CONFIG_HIGH_RES_TIMERS
+	{
+		unsigned long flags;
+		write_lock_irqsave(&xtime_lock, flags);
+		update_jiffies_sub();
+		update_real_wall_time();  
+		tp->tv_sec = xtime.tv_sec;
+		tp->tv_nsec = xtime.tv_nsec;
+		tp->tv_nsec += arch_cycles_to_nsec(sub_jiffie());
+		write_unlock_irqrestore(&xtime_lock, flags);
+		if ( tp->tv_nsec >  NSEC_PER_SEC ){
+			tp->tv_nsec -= NSEC_PER_SEC ;
+			tp->tv_sec++;
+		}
+	}
+#else
 	do_gettimeofday((struct timeval*)tp);
 	tp->tv_nsec *= NSEC_PER_USEC;
+#endif
 	return 0;
 }
 
@@ -1003,8 +1075,9 @@
 {
 	long sub_sec;
 	u64 jiffies_64_f;
+	IF_HIGH_RES(long sub_jiff_offset;)
 
-#if (BITS_PER_LONG > 32) 
+#if (BITS_PER_LONG > 32) && !defined(CONFIG_HIGH_RES_TIMERS)
 
 	jiffies_64_f = jiffies_64;
 
@@ -1018,6 +1091,8 @@
 		read_lock_irqsave(&xtime_lock, flags);
 		jiffies_64_f = jiffies_64;
 
+		IF_HIGH_RES(sub_jiff_offset =	
+			    quick_update_jiffies_sub(jiffies));
 
 		read_unlock_irqrestore(&xtime_lock, flags);
 	}
@@ -1026,14 +1101,34 @@
 	do {
 		jiffies_f = jiffies;
 		barrier();
+		IF_HIGH_RES(
+			sub_jiff_offset = 
+			quick_update_jiffies_sub(jiffies_f));
 		jiffies_64_f = jiffies_64;
 	} while (unlikely(jiffies_f != jiffies));
 
+#else /* 64 bit long and high-res but no SMP if I did the Venn right */
+	do {
+		jiffies_64_f = jiffies_64;
+		barrier();
+		sub_jiff_offset = quick_update_jiffies_sub(jiffies_64_f);
+	} while (unlikely(jiffies_64_f != jiffies_64));
 
 #endif
-	tp->tv_sec = div_long_long_rem(jiffies_64_f,HZ,&sub_sec);
+	/*
+	 * Remember that quick_update_jiffies_sub() can return more
+	 * than a jiffies worth of cycles...
+	 */
+	IF_HIGH_RES(
+		while ( unlikely(sub_jiff_offset > cycles_per_jiffies)){
+			sub_jiff_offset -= cycles_per_jiffies;
+			jiffies_64_f++;
+		}
+		)
+		tp->tv_sec = div_long_long_rem(jiffies_64_f,HZ,&sub_sec);
 
 	tp->tv_nsec = sub_sec * (NSEC_PER_SEC / HZ);
+	IF_HIGH_RES(tp->tv_nsec += arch_cycles_to_nsec(sub_jiff_offset));
 	return 0;
 }
 
@@ -1192,6 +1287,7 @@
 			 * del_timer_sync() will return 0, thus
 			 * active is zero... and so it goes.
 			 */
+			IF_HIGH_RES(new_timer.sub_expires = )
 
 				tstojiffie(&t,
 					   posix_clocks[which_clock].res,
@@ -1213,9 +1309,15 @@
 	}
 	if (active && rmtp ) {
 		unsigned long jiffies_f = jiffies;
+		IF_HIGH_RES(
+			long sub_jiff = 
+			quick_update_jiffies_sub(jiffies_f));
 
 		jiffies_to_timespec(new_timer.expires - jiffies_f, &t);
 
+		IF_HIGH_RES(t.tv_nsec += 
+			    arch_cycles_to_nsec(new_timer.sub_expires -
+						sub_jiff));
 		while (t.tv_nsec < 0){
 			t.tv_nsec += NSEC_PER_SEC;
 			t.tv_sec--;
Binary files linux-2.5.50-i386/scripts/lxdialog/lxdialog and linux/scripts/lxdialog/lxdialog differ
Binary files linux-2.5.50-i386/usr/gen_init_cpio and linux/usr/gen_init_cpio differ
Binary files linux-2.5.50-i386/usr/initramfs_data.cpio.gz and linux/usr/initramfs_data.cpio.gz differ
