Skip to contentSkip to conversation

High-res-timers part 1 (core) take 8

PATCH In review george anzinger 2 participants 3 messages Oct 29, 2002 – Oct 30, 2002

Subsystems (2)
lore
Share & tools
lore
#0 lore raw

PATCH 1/3 High-res-timers part 1 (core) take 8

This patch supplies the core changes to implement high resolution timers. Mostly it changes the timer list from the multi stage hash (or cascade) list to a single stage hash list. This change makes it easy to configure the list size for those who are concerned with performance. It also eliminates the "time out" for the cascade operation every 512 jiffies, thus eliminating possibly long preemption times.

It also adds a sub jiffie word to the timer structure to allow timers to exist between jiffies. However, to support the sub jiffie timers, work needs to be done in the platform code for each arch. The platform work for the i386 arch follows in part 2. To prevent requests from nonexistent code for sub jiffies stuff, these parts of this patch are disabled with the IF_HIGH_RES() macro which depends on CONFIG_HIGH_RES_TIMERS which will be defined for each platform as they supply the needed code.

Some of Ingo's timer code has been optimized to drop stuff not needed if the system is not SMP.

With this patch applied, the system should boot and run much as it does prior to the patch. This patch depends on the POSIX clocks & timers patch in that it assumes the changes that patch made to timer.c to remove timer_t. This dependency can be removed if needed.

Patch is against 2.5.44-bk1

This patch as well as the POSIX clocks & timers patch is available on the project site:
http://sourceforge.net/projects/high-res-timers/

The 3 parts to the high res timers are:
*core The core kernel (i.e. platform independent) changes
i386 The high-res changes for the i386 (x86) platform
posixhr The changes to the POSIX clocks & timers patch to
use high-res timers

Please apply.

Signature · 5 lines
George Anzinger   [email protected]
High-res-timers: 
http://sourceforge.net/projects/high-res-timers/
Preemption patch:
http://www.kernel.org/pub/linux/kernel/people/rml
include/linux/hrtime.h +156 -0
diff -urP -I \$Id:.*Exp \$ -X /usr/src/patch.exclude linux-2.5.44-bk1-posix/include/linux/hrtime.h linux/include/linux/hrtime.h
@@ -0,0 +1,156 @@
+#ifndef _HRTIME_H
+#define _HRTIME_H
+
+
+
+/*
+ * This file is the glue to bring in the platform stuff.
+ * We make it all depend on the CONFIG option so all archs
+ * will work as long as the CONFIG is not set.	Once an 
+ * arch defines the CONFIG, it had better have the 
+ * asm/hrtime.h file in place.
+ */
+
+/*
+ * This gets filled in at init time, either static or dynamic.
+ * Someday this will be what NTP fiddles with.
+ * Do we need the scale here?  I don't think so, as long as we
+ * do percentage offsets for NTP.
+ */
+struct timer_conversion_bits {
+	unsigned long _arch_to_usec; 
+	unsigned long _arch_to_nsec;
+	unsigned long _usec_to_arch; 
+	unsigned long _nsec_to_arch;
+	long _cycles_per_jiffies;
+	unsigned long _arch_to_latch;
+};
+extern struct timer_conversion_bits timer_conversion_bits;
+/*
+ * The following four values are not used for machines 
+ * without a TSC.  For machines with a TSC they
+ * are caculated at boot time. They are used to 
+ * calculate "cycles" to jiffies or usec.  Don't get
+ * confused into thinking they are simple multiples or
+ * divisors, however.  
+ */
+#define arch_to_usec timer_conversion_bits._arch_to_usec 
+#define arch_to_nsec timer_conversion_bits._arch_to_nsec
+#define usec_to_arch timer_conversion_bits._usec_to_arch 
+#define nsec_to_arch timer_conversion_bits._nsec_to_arch
+#define cycles_per_jiffies timer_conversion_bits._cycles_per_jiffies
+#define arch_to_latch timer_conversion_bits._arch_to_latch 
+
+#include <linux/config.h>
+#ifdef CONFIG_HIGH_RES_TIMERS
+#include <asm/hrtime.h>
+/*
+ * The schedule_next_int function is to be defined by the "arch" code
+ * when an "arch" is implementing the high-res part of POSIX timers.
+ * The actual function will be called with the offset in "arch" (parm 2)
+ * defined sub_jiffie units from the reference jiffie boundry (parm 1)to
+ * the next required sub_jiffie timer interrupt. This value will be -1
+ * if the next timer interrupt should be the next jiffie value.	 The
+ * "arch" code must determine how far out the interrupt is, based on
+ * current jiffie, sub_jiffie time and set up the hardware to interrupt
+ * at that time.  It is possible that the time will already have passed,
+ * in which case the function should return true (no interrupt is
+ * needed), otherwise the return should be 0.  The third parameter is the
+ * "always" flag which says that the code needs an interrupt, even if the
+ * time has passed.  In this case a "close" in time should be used to 
+ * generate the required interrupt.  The sub_jiffie interrupt
+ * should just call do_timer(). If the interrupt code ususally does stuff
+ * each jiffie, a flag should be kept by the jiffies update code to
+ * indicate that a new jiffie has started.  This flag is to keep this code 
+ * from being executed on the sub jiffie interrupt.
+ */
+#ifndef schedule_next_int
+#define schedule_next_int(s,d,a) 0
+#undef CONFIG_HIGH_RES_TIMERS
+#endif	// schedule_next_int
+/*
+ * The sub_jiffie() macro should return the current time offset from the latest
+ * jiffie.  This will be in "arch" defined units and is used to determine if
+ * a timer has expired.	 Since no sub_expire value will be used if "arch" 
+ * has not defined the high-res package, 0 will work well here.
+ *
+ * In addition, to save time if there is no high-res package (or it is not
+ * configured), we define the sub expression for the run_timer_list.
+ */
+
+#ifndef sub_jiffie
+#undef CONFIG_HIGH_RES_TIMERS
+#define sub_jiffie() 0
+#endif	// sub_jiffie
+
+/*
+ * The high_res_test() macro should set up a test mode that will do a
+ * worst case timer interrupt.	I.e. it may be that a call to 
+ * schedule_next_int() could return -1 indicating that the time has
+ * already expired.  This macro says to set it so that schedule_next_int()
+ * will always set up a timer interrupt.  This is used during init to
+ * calculate the worst case loop time from timer set up to int to 
+ * the signal code.
+
+ * high_res_end_test() cancels the above state and allows the no
+ * interrupt return from schedule_next_int()
+ */
+#ifndef high_res_test
+#define high_res_test()
+#define high_res_end_test()
+#endif
+
+
+#define IF_HIGH_RES(a) a
+
+#else	/*  CONFIG_HIGH_RES_TIMERS */
+#define IF_HIGH_RES(a)
+#define nsec_to_arch_cycles(a) 0
+
+#endif	 /*  CONFIG_HIGH_RES_TIMERS */
+
+/*
+ * Here is an SMP helping macro...
+ */
+#ifdef CONFIG_SMP
+#define if_SMP(a) a
+#else
+#define if_SMP(a)
+#endif
+/*
+ * These should have been defined in the platform hrtimers.h
+ * If not (or HIGH_RES_TIMERS not configured) define the default.
+ */
+#ifndef update_jiffies
+extern u64 jiffies_64;
+#define update_jiffies() (*(u64 *)&jiffies_64)++
+#endif
+#ifndef new_jiffie
+#define new_jiffie() 0
+#endif
+#ifndef schedule_next_int
+#define schedule_next_int(a,b,c)
+#endif
+/*
+ * If we included a high-res file, we may have gotten a more efficient 
+ * u64/u32, u64%u32 routine.  The one in div64.h actually handles a 
+ * u64 result, something we don't need, and, since it is more expensive
+ * arch porters are encouraged to implement the div_long_long_rem().
+ *
+ * int div_long_long_rem(u64 dividend,int divisor,int* remainder)
+ * which returns dividend/divisor.
+ * 
+ * Here we provide default code for those who, for what ever reason,
+ * have not provided the above.
+ */
+#ifndef div_long_long_rem
+#include <asm/div64.h>
+
+#define div_long_long_rem(dividend,divisor,remainder) ({ \
+		       u64 result = dividend;		\
+		       *remainder = do_div(result,divisor); \
+		       result; })
+
+#endif	 /* ifndef div_long_long_rem */
+
+#endif	 /* _HRTIME_H  */
include/linux/signal.h +29 -0
diff -urP -I \$Id:.*Exp \$ -X /usr/src/patch.exclude linux-2.5.44-bk1-posix/include/linux/signal.h linux/include/linux/signal.h
@@ -219,6 +219,35 @@
 }
 
 extern long do_sigpending(void *, unsigned long);
+/*
+ * We would like the asm/signal.h code to define these so that the using
+ * function can call do_signal().  In loo of that, we define a genaric
+ * version that pretends that do_signal() was called and delivered a signal.
+ * To see how this is used, see nano_sleep() in timer.c and the i386 version
+ * in asm_i386/signal.h.
+ */
+#ifndef PT_REGS_ENTRY
+#define PT_REGS_ENTRY(type,name,p1_type,p1, p2_type,p2) \
+type name(p1_type p1,p2_type p2)\
+{
+#endif
+#ifndef _do_signal
+#define _do_signal() 1
+#endif
+#ifndef NANOSLEEP_ENTRY
+#define NANOSLEEP_ENTRY(a) asmlinkage long sys_nanosleep( struct timespec* rqtp, \
+							  struct timespec * rmtp) \
+{ a
+#endif
+#ifndef CLOCK_NANOSLEEP_ENTRY
+#define CLOCK_NANOSLEEP_ENTRY(a) asmlinkage long sys_clock_nanosleep( \
+			       clockid_t which_clock,	   \
+			       int flags,		   \
+			       const struct timespec *rqtp, \
+			       struct timespec *rmtp)	    \
+{ a
+ 
+#endif
 
 #ifndef HAVE_ARCH_GET_SIGNAL_TO_DELIVER
 struct pt_regs;
include/linux/time.h +22 -9
diff -urP -I \$Id:.*Exp \$ -X /usr/src/patch.exclude linux-2.5.44-bk1-posix/include/linux/time.h linux/include/linux/time.h
@@ -1,7 +1,7 @@
 #ifndef _LINUX_TIME_H
 #define _LINUX_TIME_H
 
-#include <asm/param.h>
+#include <linux/param.h>
 #include <linux/types.h>
 
 #ifndef _STRUCT_TIMESPEC
@@ -51,6 +51,19 @@
 #define NSEC_PER_USEC (1000L)
 #endif
 
+/* Parameters used to convert the timespec values */
+#ifndef USEC_PER_SEC
+#define USEC_PER_SEC (1000000L)
+#endif
+
+#ifndef NSEC_PER_SEC
+#define NSEC_PER_SEC (1000000000L)
+#endif
+
+#ifndef NSEC_PER_USEC
+#define NSEC_PER_USEC (1000L)
+#endif
+
 static __inline__ unsigned long
 timespec_to_jiffies(struct timespec *value)
 {
@@ -59,16 +72,16 @@
 
 	if (sec >= (MAX_JIFFY_OFFSET / HZ))
 		return MAX_JIFFY_OFFSET;
-	nsec += 1000000000L / HZ - 1;
-	nsec /= 1000000000L / HZ;
+	nsec += NSEC_PER_SEC / HZ - 1;
+	nsec /= NSEC_PER_SEC / HZ;
 	return HZ * sec + nsec;
 }
 
 static __inline__ void
-jiffies_to_timespec(unsigned long jiffies, struct timespec *value)
+jiffies_to_timespec(unsigned long _jiffies, struct timespec *value)
 {
-	value->tv_nsec = (jiffies % HZ) * (1000000000L / HZ);
-	value->tv_sec = jiffies / HZ;
+	value->tv_nsec = (_jiffies % HZ) * (NSEC_PER_SEC / HZ);
+	value->tv_sec = _jiffies / HZ;
 }
 
 /* Same for "timeval" */
@@ -155,9 +168,9 @@
 #define	ITIMER_VIRTUAL	1
 #define	ITIMER_PROF	2
 
-struct  itimerspec {
-        struct  timespec it_interval;    /* timer period */
-        struct  timespec it_value;       /* timer expiration */
+struct	itimerspec {
+	struct	timespec it_interval;	 /* timer period */
+	struct	timespec it_value;	 /* timer expiration */
 };
 
 struct	itimerval {
include/linux/timer.h +2 -0
diff -urP -I \$Id:.*Exp \$ -X /usr/src/patch.exclude linux-2.5.44-bk1-posix/include/linux/timer.h linux/include/linux/timer.h
@@ -14,6 +14,7 @@
 	unsigned long data;
 
 	struct tvec_t_base_s *base;
+	long sub_expires;
 };
 
 /***
@@ -46,6 +47,7 @@
 extern void add_timer(struct timer_list * timer);
 extern int del_timer(struct timer_list * timer);
 extern int mod_timer(struct timer_list *timer, unsigned long expires);
+extern void update_real_wall_time(void);
   
 #if CONFIG_SMP
   extern int del_timer_sync(struct timer_list * timer);
init/Config.in +21 -0
diff -urP -I \$Id:.*Exp \$ -X /usr/src/patch.exclude linux-2.5.44-bk1-posix/init/Config.in linux/init/Config.in
@@ -9,6 +9,27 @@
 bool 'System V IPC' CONFIG_SYSVIPC
 bool 'BSD Process Accounting' CONFIG_BSD_PROCESS_ACCT
 bool 'Sysctl support' CONFIG_SYSCTL
+choice 'Size of timer list?' \
+	"512		CONFIG_TIMERLIST_512 \
+	1024		CONFIG_TIMERLIST_1k  \
+	2048		CONFIG_TIMERLIST_2k  \
+	4096		CONFIG_TIMERLIST_4k  \
+	8192		CONFIG_TIMERLIST_8k" 512
+if [ "$CONFIG_TIMERLIST_512" =	"y" ]; then
+	define_int CONFIG_NEW_TIMER_LISTSIZE 512
+fi
+if [ "$CONFIG_TIMERLIST_1k" =  "y" ]; then
+	define_int CONFIG_NEW_TIMER_LISTSIZE 1024
+fi
+if [ "$CONFIG_TIMERLIST_2k" =  "y" ]; then
+	define_int CONFIG_NEW_TIMER_LISTSIZE 2048
+fi
+if [ "$CONFIG_TIMERLIST_4k" =  "y" ]; then
+	define_int CONFIG_NEW_TIMER_LISTSIZE 4096
+fi
+if [ "$CONFIG_TIMERLIST_8k" =  "y" ]; then
+	define_int CONFIG_NEW_TIMER_LISTSIZE 8192
+fi
 endmenu
 
 mainmenu_option next_comment
kernel/ksyms.c +4 -0
diff -urP -I \$Id:.*Exp \$ -X /usr/src/patch.exclude linux-2.5.44-bk1-posix/kernel/ksyms.c linux/kernel/ksyms.c
@@ -54,6 +54,7 @@
 #include <linux/smp_lock.h>
 #include <linux/dnotify.h>
 #include <asm/checksum.h>
+#include <linux/hrtime.h>
 
 #if defined(CONFIG_PROC_FS)
 #include <linux/proc_fs.h>
@@ -478,6 +479,9 @@
 #endif
 EXPORT_SYMBOL(jiffies);
 EXPORT_SYMBOL(jiffies_64);
+#ifdef CONFIG_HIGH_RES_TIMERS
+EXPORT_SYMBOL(timer_conversion_bits);
+#endif
 EXPORT_SYMBOL(xtime);
 EXPORT_SYMBOL(do_gettimeofday);
 EXPORT_SYMBOL(do_settimeofday);
kernel/timer.c +372 -161

702 lines not on this page · raw message

#1 lore raw

Your patch adds a new config option that seems like a step backwards in ease of use. The CONFIG_TIMERLIST option is adding a new dimension to complexity kernel configuration. For no other parameter that I can think of does the kernel configuration process ask for a size information. Number of users, processes, threads, groups, are all sized dynamically now; this is good.

How is the end user supposed to know how many timer list entries are expected? There is no context about what a timer list entry is and no direct correlation back to anything meaningful in user terms (processes, devices, sockets, ...). Also, what happens if the time list size is exhausted? does the kernel die? is it slower?...

Can't this just be dynamically sized?
============================================================================
diff -urP -I \$Id:.*Exp \$ -X /usr/src/patch.exclude linux-2.5.44-bk1-posix/init/Config.in linux/init/Config.in

init/Config.in Tue Oct 29 07:37:11 2002 renamed from init/Config.in Mon Sep 9 10:35:03 2002 +21 -0
@@ -9,6 +9,27 @@
 bool 'System V IPC' CONFIG_SYSVIPC
 bool 'BSD Process Accounting' CONFIG_BSD_PROCESS_ACCT
 bool 'Sysctl support' CONFIG_SYSCTL
+choice 'Size of timer list?' \
+       "512            CONFIG_TIMERLIST_512 \
+       1024            CONFIG_TIMERLIST_1k  \
+       2048            CONFIG_TIMERLIST_2k  \
+       4096            CONFIG_TIMERLIST_4k  \
+       8192            CONFIG_TIMERLIST_8k" 512
+if [ "$CONFIG_TIMERLIST_512" = "y" ]; then
+       define_int CONFIG_NEW_TIMER_LISTSIZE 512
+fi
+if [ "$CONFIG_TIMERLIST_1k" =  "y" ]; then
+       define_int CONFIG_NEW_TIMER_LISTSIZE 1024
+fi
+if [ "$CONFIG_TIMERLIST_2k" =  "y" ]; then
+       define_int CONFIG_NEW_TIMER_LISTSIZE 2048
+fi
+if [ "$CONFIG_TIMERLIST_4k" =  "y" ]; then
+       define_int CONFIG_NEW_TIMER_LISTSIZE 4096
+fi
+if [ "$CONFIG_TIMERLIST_8k" =  "y" ]; then
+       define_int CONFIG_NEW_TIMER_LISTSIZE 8192
+fi
 endmenu
 
 
#2 lore raw
Quoted 8 lines · Stephen Hemminger

Your patch adds a new config option that seems like a step backwards in ease of use. The CONFIG_TIMERLIST option is adding a new dimension to complexity kernel configuration. For no other parameter that I can think of does the kernel configuration process ask for a size information. Number of users, processes, threads, groups, are all sized dynamically now; this is good.

Quoted 6 lines

How is the end user supposed to know how many timer list entries are expected? There is no context about what a timer list entry is and no direct correlation back to anything meaningful in user terms (processes, devices, sockets, ...). Also, what happens if the time list size is exhausted? does the kernel die? is it slower?...

Ok, first, somehow in the chase to stay up with 2.5, this bit was lost:
Configure timer list size
CONFIG_TIMERLIST_512
This choice allows you to choose the timer list size you
want. The
list insert time is Order(N/size) where N is the number of
active
timers. Each list head is 8 bytes, thus a 512 list size
requires 4K
bytes. Use larger numbers if you will be using a large
number of
timers and are more concerned about list insertion time
than the extra
memory usage. (The list size must be a power of 2.)

from the Config.help file. The timer list is a hash list and the size this lets you set changes the number of buckets, the only affect its size has is on the insertion time, more buckets => faster. So the kernel does not die and the list will never be exhausted (or even full).

Quoted 1 line

Can't this just be dynamically sized?

As to choosing it dynamically, it needs to be fixed rather early in the game, compile time or boot time, no later.

That said, we have run tests to see how the list insert time varies with number of timers (in fact the test program is in the support package on the sourceforge site, called "performance.c" in the tests directory once you install that package). The test was done with a 512 entry list and with 1 to 4000 timers. Insertion time went from about 4 micro seconds to about 7 over that range, with the first insert taking about 40 micro seconds. The conclusion was that the cache misses on the first insertion were FAR more important than the list size.

Also, since that time, Ingo's salability changes went in, which means that each cpu has its own list.

The net of all this is that, on reflection, I think I will remove the configure option on timer list size. I will leave the code in place so that, if some special application wants to change it, it will be easy to do, much as changing HZ (only easier as it has NO impact outside of the kernel).

Thanks for bringing this to my attention. The patch for the next bk release will reflect this change.

Signature · 5 lines
George Anzinger   [email protected]
High-res-timers: 
http://sourceforge.net/projects/high-res-timers/
Preemption patch:
http://www.kernel.org/pub/linux/kernel/people/rml