: ktime + nano-second clock resolution for packet schedulers
Subsystems (3)
cover : ktime + nano-second clock resolution for packet schedulers
These patches convert the GETTIMEOFDAY packet scheduler clock source to ktime (based on Stephen's patch) and add support for using nano-second clock resolution. I chose a scalar time representation within the packet schedulers instead of ktime_t since it minimizes the ktime_to_ns() calls in most cases, it allows to clean up pkt_sched.h quite a bit and HFSC needs it anyway.
Unlike my previous attempt at this, these patches keep old iproute versions working with nano-second resolution with the exception of HFSC. I'm not sure what to do about HFSC yet, so just RFC for now.
include/linux/jiffies.h | 2 include/net/pkt_sched.h | 141 ++++++++++-------------------------------------- kernel/hrtimer.c | 1 kernel/time.c | 26 ++++++++ net/sched/Kconfig | 17 +++++ net/sched/sch_api.c | 11 ++- net/sched/sch_hfsc.c | 37 +++++------- 7 files changed, 100 insertions(+), 135 deletions(-)
Patrick McHardy:
[TIME]: Add jiffies_to_nsecs/nsecs_to_jiffies [NET_SCHED]: Replace gettimeofday clocksource by ktime [NET_SCHED]: Add support for nano-second clock resolution
RFC 1/3 : Add jiffies_to_nsecs/nsecs_to_jiffies
[TIME]: Add jiffies_to_nsecs/nsecs_to_jiffies
---
commit 861b3967e1bb01335e544220df779f91b20a27e7
tree cd877a5091f461008ec708b801a2fa04d3c26004
parent 2ff7354fe888f46f6629b57e463b0a1eb956c02b
author Patrick McHardy <[email protected]> Fri, 02 Mar 2007 02:49:43 +0100 committer Patrick McHardy <[email protected]> Sun, 04 Mar 2007 19:31:38 +0100
include/linux/jiffies.h | 2 ++ kernel/time.c | 26 ++++++++++++++++++++++++++ 2 files changed, 28 insertions(+), 0 deletions(-)
include/linux/jiffies.h +2 -0
@@ -263,8 +263,10 @@ #endif*/ extern unsigned int jiffies_to_msecs (const unsigned long j);extern unsigned int jiffies_to_usecs (const unsigned long j); +extern unsigned int jiffies_to_nsecs (const unsigned long j);extern unsigned long msecs_to_jiffies (const unsigned int m);extern unsigned long usecs_to_jiffies (const unsigned int u); +extern unsigned long nsecs_to_jiffies (const unsigned int n);extern unsigned long timespec_to_jiffies (const struct timespec *value);extern void jiffies_to_timespec (const unsigned long jiffies,struct timespec *value);
kernel/time.c +26 -0
@@ -500,6 +500,18 @@ #endif }EXPORT_SYMBOL (jiffies_to_usecs); +unsigned int jiffies_to_nsecs (const unsigned long j) +{ +#if HZ <=NSEC_PER_SEC && !(NSEC_PER_SEC %HZ ) +return (NSEC_PER_SEC /HZ ) * j; +#elif HZ >NSEC_PER_SEC && !(HZ %NSEC_PER_SEC ) +return (j + (HZ /NSEC_PER_SEC ) -1 )/(HZ /NSEC_PER_SEC ); +#else +return (j *NSEC_PER_SEC ) /HZ ; +#endif +} +EXPORT_SYMBOL (jiffies_to_nsecs); +/* * When we convert to jiffies then we interpret incoming values * the following way:
@@ -569,6 +581,20 @@ #endif }EXPORT_SYMBOL (usecs_to_jiffies); +unsigned long nsecs_to_jiffies (const unsigned int n) +{ +if (n >jiffies_to_nsecs (MAX_JIFFY_OFFSET )) +return MAX_JIFFY_OFFSET ; +#if HZ <=NSEC_PER_SEC && (!NSEC_PER_SEC %HZ ) +return (n + (NSEC_PER_SEC /HZ ) -1 ) / (NSEC_PER_SEC /HZ ); +#elif HZ >NSEC_PER_SEC && !(HZ %NSEC_PER_SEC ) +return n * (HZ /NSEC_PER_SEC ); +#else +return (n *HZ +NSEC_PER_SEC -1 ) /NSEC_PER_SEC ; +#endif +} +EXPORT_SYMBOL (nsecs_to_jiffies); +/* * The TICK_NSEC - 1 rounds up the value to the next resolution. Note * that a remainder subtract here would not do the right thing as the
RFC 2/3 : Replace gettimeofday clocksource by ktime
In reply to Patrick McHardy[NET_SCHED]: Replace gettimeofday clocksource by ktime
Using a monotonic clock avoids glitches when NTP adjusts the clock, additionally it will allow us to take advantage of the higher resolution in the future.
This patch also gets rid of the non-scalar representation, which allows to clean up a lot of the mess in pkt_sched.h and results in less ktime_to_ns() calls in most cases.
Based on patch by Stephen Hemminger <[email protected]>
---
commit 8e4951375c3678b4720de46791c39064d8633fca
tree c3e0567265dc1d13ae52601970d829cb3c8190b2
parent 861b3967e1bb01335e544220df779f91b20a27e7
author Patrick McHardy <[email protected]> Fri, 02 Mar 2007 03:44:09 +0100 committer Patrick McHardy <[email protected]> Sun, 04 Mar 2007 19:44:41 +0100
include/net/pkt_sched.h | 128 ++++++++--------------------------------------- kernel/hrtimer.c | 1 net/sched/sch_api.c | 7 ++- net/sched/sch_hfsc.c | 18 +------ 4 files changed, 30 insertions(+), 124 deletions(-)
include/net/pkt_sched.h +21 -107
@@ -37,11 +37,6 @@ static inline void *qdisc_priv(struct QdThe things are not so bad, because we may use artifical clock evaluated by integration of network data flow in the most critical places. - -Note: we do not use fastgettimeofday. -The reason is that, when it is not the same thing as -gettimeofday, it returns invalid timestamp, which is -not updated, when net_bh is active. */ /* General note about internal clock.
@@ -53,22 +48,23 @@ static inline void *qdisc_priv(struct Qdmay be read from /proc/net/psched. */ +typedef u64 psched_time_t ; +typedef long psched_tdiff_t ;#ifdef CONFIG_NET_SCH_CLK_GETTIMEOFDAY +#include <linux/ktime.h> -typedef struct timeval psched_time_t ; -typedef long psched_tdiff_t ; +/* Avoid doing 64 bit divide by 1000 */ +#define PSCHED_US2NS (x) ((s64)(x) << 10) +#define PSCHED_NS2US (x) ((x) >> 10) -#define PSCHED_GET_TIME (stamp) do_gettimeofday(&(stamp)) -#define PSCHED_US2JIFFIE (usecs) usecs_to_jiffies(usecs) -#define PSCHED_JIFFIE2US (delay) jiffies_to_usecs(delay) +#define PSCHED_GET_TIME (stamp) \ + ((stamp) = PSCHED_NS2US(ktime_to_ns(ktime_get()))) -#else /* !CONFIG_NET_SCH_CLK_GETTIMEOFDAY */ - -typedef u64 psched_time_t ; -typedef long psched_tdiff_t ; +#define PSCHED_US2JIFFIE (usecs) nsecs_to_jiffies(PSCHED_US2NS((usecs))) +#define PSCHED_JIFFIE2US (delay) PSCHED_NS2US(jiffies_to_nsecs((delay))) -#ifdef CONFIG_NET_SCH_CLK_JIFFIES +#elif defined(CONFIG_NET_SCH_CLK_JIFFIES )#if HZ <96 #define PSCHED_JSCALE 14
@@ -83,11 +79,11 @@ #define PSCHED_JSCALE 10#endif #define PSCHED_GET_TIME (stamp) ((stamp) = (get_jiffies_64()<<PSCHED_JSCALE)) +#define PSCHED_US2JIFFIE (delay) (((delay)+(1<<PSCHED_JSCALE)-1)>>PSCHED_JSCALE)#define PSCHED_JIFFIE2US (delay) ((delay)<<PSCHED_JSCALE) -#endif /* CONFIG_NET_SCH_CLK_JIFFIES */ -#ifdef CONFIG_NET_SCH_CLK_CPU +#elif defined(CONFIG_NET_SCH_CLK_CPU)#include <asm/timex.h> extern psched_tdiff_t psched_clock_per_hz;
@@ -107,106 +103,24 @@ do { \ (stamp) = cur>>psched_clock_scale; \ } \ } while (0) +#define PSCHED_US2JIFFIE (delay) (((delay)+psched_clock_per_hz-1)/psched_clock_per_hz)#define PSCHED_JIFFIE2US (delay) ((delay)*psched_clock_per_hz) -#endif /* CONFIG_NET_SCH_CLK_CPU */ - -#endif /* !CONFIG_NET_SCH_CLK_GETTIMEOFDAY */ - -#ifdef CONFIG_NET_SCH_CLK_GETTIMEOFDAY -#define PSCHED_TDIFF (tv1, tv2) \ -({ \ - int __delta_sec = (tv1).tv_sec - (tv2).tv_sec; \ - int __delta = (tv1).tv_usec - (tv2).tv_usec; \ - if (__delta_sec) { \ - switch (__delta_sec) { \ - default: \ - __delta = 0; \ - case 2: \ - __delta += USEC_PER_SEC; \ - case 1: \ - __delta += USEC_PER_SEC; \ - } \ - } \ - __delta; \ -}) - -static inline int -psched_tod_diff (int delta_sec,int bound) -{ -int delta; - -if (bound <=USEC_PER_SEC || delta_sec > (0x7FFFFFFF /USEC_PER_SEC )-1 ) -return bound; - delta = delta_sec *USEC_PER_SEC ; -if (delta > bound || delta <0 ) - delta = bound; -return delta; -} - -#define PSCHED_TDIFF_SAFE (tv1, tv2, bound) \ -({ \ - int __delta_sec = (tv1).tv_sec - (tv2).tv_sec; \ - int __delta = (tv1).tv_usec - (tv2).tv_usec; \ - switch (__delta_sec) { \ - default: \ - __delta = psched_tod_diff(__delta_sec, bound); break; \ - case 2: \ - __delta += USEC_PER_SEC; \ - case 1: \ - __delta += USEC_PER_SEC; \ - case 0: \ - if (__delta > bound || __delta < 0) \ - __delta = bound; \ - } \ - __delta; \ -}) - -#define PSCHED_TLESS (tv1, tv2) (((tv1).tv_usec < (tv2).tv_usec && \ - (tv1).tv_sec <= (tv2).tv_sec) || \ - (tv1).tv_sec < (tv2).tv_sec) - -#define PSCHED_TADD2 (tv, delta, tv_res) \ -({ \ - int __delta = (tv).tv_usec + (delta); \ - (tv_res).tv_sec = (tv).tv_sec; \ - while (__delta >= USEC_PER_SEC) { (tv_res).tv_sec++; __delta -= USEC_PER_SEC; } \ - (tv_res).tv_usec = __delta; \ -}) - -#define PSCHED_TADD (tv, delta) \ -({ \ - (tv).tv_usec += (delta); \ - while ((tv).tv_usec >= USEC_PER_SEC) { (tv).tv_sec++; \ - (tv).tv_usec -= USEC_PER_SEC; } \ -}) - -/* Set/check that time is in the "past perfect"; -it depends on concrete representation of system time -*/ - -#define PSCHED_SET_PASTPERFECT (t) ((t).tv_sec = 0) -#define PSCHED_IS_PASTPERFECT (t) ((t).tv_sec == 0) - -#define PSCHED_AUDIT_TDIFF (t) ({ if ((t) > 2000000) (t) = 2000000; }) - -#else /* !CONFIG_NET_SCH_CLK_GETTIMEOFDAY */ +#else +#error CONFIG_NET_SCH_CLK not set correctly! +#endif -#define PSCHED_TDIFF (tv1, tv2) (long)((tv1) - (tv2)) +#define PSCHED_TDIFF (tv1, tv2) (long)((tv1) - (tv2))#define PSCHED_TDIFF_SAFE (tv1, tv2, bound) \ - min_t(long long, (tv1) - (tv2), bound) - - -#define PSCHED_TLESS (tv1, tv2) ((tv1) < (tv2)) + min_t(long long, (tv1) - (tv2), bound) +#define PSCHED_TLESS (tv1, tv2) ((tv1) < (tv2))#define PSCHED_TADD2 (tv, delta, tv_res) ((tv_res) = (tv) + (delta)) -#define PSCHED_TADD (tv, delta) ((tv) += (delta)) +#define PSCHED_TADD (tv, delta) ((tv) += (delta))#define PSCHED_SET_PASTPERFECT (t) ((t) = 0)#define PSCHED_IS_PASTPERFECT (t) ((t) == 0)#define PSCHED_AUDIT_TDIFF (t) -#endif /* !CONFIG_NET_SCH_CLK_GETTIMEOFDAY */ -extern struct Qdisc_ops pfifo_qdisc_ops;extern struct Qdisc_ops bfifo_qdisc_ops;
kernel/hrtimer.c +1 -0
@@ -59,6 +59,7 @@ ktime_t ktime_get(void)return timespec_to_ktime (now); } +EXPORT_SYMBOL_GPL (ktime_get);/** * ktime_get_real - get the real (wall-) time in ktime_t format
net/sched/sch_api.c +5 -2
@@ -1175,8 +1175,8 @@ #endifreturn -1 ; } -static int psched_us_per_tick =1 ; -static int psched_tick_per_us =1 ; +static int psched_us_per_tick; +static int psched_tick_per_us;#ifdef CONFIG_PROC_FS static int psched_show (struct seq_file *seq,void *v)
@@ -1274,6 +1274,9 @@ #ifdef CONFIG_NET_SCH_CLK_CPU#elif defined(CONFIG_NET_SCH_CLK_JIFFIES ) psched_tick_per_us =HZ <<PSCHED_JSCALE ; psched_us_per_tick =1000000 ; +#elif defined(CONFIG_NET_SCH_CLK_GETTIMEOFDAY ) + psched_tick_per_us =NSEC_PER_USEC ; + psched_us_per_tick =PSCHED_US2NS (1 );#endif link_p = rtnetlink_links[PF_UNSPEC ];
net/sched/sch_hfsc.c +3 -15
@@ -195,20 +195,6 @@ struct hfsc_schedstruct timer_list wd_timer;/* watchdog timer */ }; -/* -* macros -*/ -#ifdef CONFIG_NET_SCH_CLK_GETTIMEOFDAY -#include <linux/time.h> -#undef PSCHED_GET_TIME -#define PSCHED_GET_TIME (stamp) \ -do { \ - struct timeval tv; \ - do_gettimeofday(&tv); \ - (stamp) = 1ULL * USEC_PER_SEC * tv.tv_sec + tv.tv_usec; \ -} while (0) -#endif -#define HT_INFINITY 0xffffffffffffffffULL/* infinite time value */
@@ -397,7 +383,7 @@ cftree_update(struct hfsc_class *cl)* Clock source resolution (CONFIG_NET_SCH_CLK_*) * JIFFIES: for 48<=HZ<=1534 resolution is between 0.63us and 1.27us. * CPU: resolution is between 0.5us and 1us. -* GETTIMEOFDAY: resolution is exactly 1us. +* GETTIMEOFDAY: resolution is 1.024us. * * sm and ism are scaled in order to keep effective digits. * SM_SHIFT and ISM_SHIFT are selected to keep at least 4 effective
@@ -411,10 +397,12 @@ cftree_update(struct hfsc_class *cl)* ------------+------------------------------------------------------- * bytes/0.5us 6.25e-3 62.5e-3 625e-3 6250e-e 62500e-3 * bytes/us 12.5e-3 125e-3 1250e-3 12500e-3 125000e-3 +* bytes/1.024us 12.8e-3 128e-3 1280e-3 12800e-3 128000e-3 * bytes/1.27us 15.875e-3 158.75e-3 1587.5e-3 15875e-3 158750e-3 * * 0.5us/byte 160 16 1.6 0.16 0.016 * us/byte 80 8 0.8 0.08 0.008 +* 1.024us/byte 78.125 7.8125 0.78125 0.078125 0.0078125 * 1.27us/byte 63 6.3 0.63 0.063 0.0063 */ #define SM_SHIFT 20
RFC 3/3 : Add support for nano-second clock resolution
In reply to Patrick McHardy[NET_SCHED]: Add support for nano-second clock resolution
Add support to nano-second clock resolution with ktime as clock source.
Since the ABI uses clock ticks in some places and all clock sources previously used micro-second resolution, this changes the API. To avoid breakage with old iproute versions, a clock multiplier of 1000 is advertised in /proc/net/psched, which keeps everything but HFSC working properly (modulo integer overflows). New iproute versions can detect support for nano-second resolution by reading the third value in /proc/net/psched and ignore the multiplier.
---
commit 7978ac74b18bf1e9b01284a15ea5b54442005bb4
tree 0c1782e884f2c8e791b35df15901c9cc9e64513e
parent 8e4951375c3678b4720de46791c39064d8633fca
author Patrick McHardy <[email protected]> Fri, 02 Mar 2007 03:48:49 +0100 committer Patrick McHardy <[email protected]> Sun, 04 Mar 2007 19:54:04 +0100
include/net/pkt_sched.h | 13 ++++++++++--- net/sched/Kconfig | 17 +++++++++++++++++ net/sched/sch_api.c | 4 ++-- net/sched/sch_hfsc.c | 19 +++++++++++++------ 4 files changed, 42 insertions(+), 11 deletions(-)
include/net/pkt_sched.h +10 -3
@@ -51,12 +51,19 @@ static inline void *qdisc_priv(struct Qdtypedef u64 psched_time_t ;typedef long psched_tdiff_t ; -#ifdef CONFIG_NET_SCH_CLK_GETTIMEOFDAY -#include <linux/ktime.h> - +#ifdef CONFIG_NET_SCH_CLK_NSEC_RESOLUTION +#define PSCHED_CLOCK_RESOLUTION NSEC_PER_SEC +#define PSCHED_US2NS (x) (x) +#define PSCHED_NS2US (x) (x) +#else +#define PSCHED_CLOCK_RESOLUTION USEC_PER_SEC/* Avoid doing 64 bit divide by 1000 */ #define PSCHED_US2NS (x) ((s64)(x) << 10)#define PSCHED_NS2US (x) ((x) >> 10) +#endif + +#ifdef CONFIG_NET_SCH_CLK_GETTIMEOFDAY +#include <linux/ktime.h> #define PSCHED_GET_TIME (stamp) \ ((stamp) = PSCHED_NS2US(ktime_to_ns(ktime_get())))
net/sched/Kconfig +17 -0
@@ -102,6 +102,23 @@ config NET_SCH_CLK_CPU endchoice +config NET_SCH_CLK_NSEC_RESOLUTION + bool "Use nano-second resolution (EXPERIMENTAL)" + depends on EXPERIMENTAL + depends on NET_SCH_CLK_GETTIMEOFDAY + help + This option enables nano-second resolution for the packet scheduler + clock source. + + To take full advantage of the increased precision, an iproute version + using nano-seconds internally is needed. + + Note: enabling the option might cause misbehaviour because of + integer overflows. It will also break HFSC unless a current + version of iproute is used. + + If unsure, say N. + comment "Queueing/Scheduling" config NET_SCH_CBQ
net/sched/sch_api.c +2 -2
@@ -1181,9 +1181,9 @@ static int psched_tick_per_us;#ifdef CONFIG_PROC_FS static int psched_show (struct seq_file *seq,void *v) { -seq_printf (seq,"%08x %08x %08x %08x\n" , +seq_printf (seq,"%08x %08x %08lx %08x\n" , psched_tick_per_us, psched_us_per_tick, -1000000 ,HZ ); +PSCHED_CLOCK_RESOLUTION ,HZ );return 0 ; }
net/sched/sch_hfsc.c +13 -6
@@ -383,7 +383,7 @@ cftree_update(struct hfsc_class *cl)* Clock source resolution (CONFIG_NET_SCH_CLK_*) * JIFFIES: for 48<=HZ<=1534 resolution is between 0.63us and 1.27us. * CPU: resolution is between 0.5us and 1us. -* GETTIMEOFDAY: resolution is 1.024us. +* GETTIMEOFDAY: resolution is 1.024us, 1ns with NET_SCH_CLK_NSEC_RESOLUTION. * * sm and ism are scaled in order to keep effective digits. * SM_SHIFT and ISM_SHIFT are selected to keep at least 4 effective
@@ -395,18 +395,25 @@ cftree_update(struct hfsc_class *cl)* * bits/sec 100Kbps 1Mbps 10Mbps 100Mbps 1Gbps * ------------+------------------------------------------------------- +* bytes/ns 12.5e-6 125e-6 1250e-6 12500e-6 125000e-6 * bytes/0.5us 6.25e-3 62.5e-3 625e-3 6250e-e 62500e-3 * bytes/us 12.5e-3 125e-3 1250e-3 12500e-3 125000e-3 * bytes/1.024us 12.8e-3 128e-3 1280e-3 12800e-3 128000e-3 * bytes/1.27us 15.875e-3 158.75e-3 1587.5e-3 15875e-3 158750e-3 * +* ns/byte 80000 8000 800 80 8 * 0.5us/byte 160 16 1.6 0.16 0.016 * us/byte 80 8 0.8 0.08 0.008 * 1.024us/byte 78.125 7.8125 0.78125 0.078125 0.0078125 * 1.27us/byte 63 6.3 0.63 0.063 0.0063 */ -#define SM_SHIFT 20 -#define ISM_SHIFT 18 +#ifdef CONFIG_NET_SCH_CLK_NSEC_RESOLUTION +#define SM_SHIFT 30 +#define ISM_SHIFT 8 +#else +#define SM_SHIFT 20 +#define ISM_SHIFT 18 +#endif #define SM_MASK ((1ULL << SM_SHIFT) - 1)#define ISM_MASK ((1ULL << ISM_SHIFT) - 1)
@@ -476,8 +483,8 @@ d2dx(u32 d)u64 dx; dx = ((u64 )d *PSCHED_JIFFIE2US (HZ )); - dx +=USEC_PER_SEC -1 ; -do_div (dx,USEC_PER_SEC ); + dx +=PSCHED_CLOCK_RESOLUTION -1 ; +do_div (dx,PSCHED_CLOCK_RESOLUTION );return dx; }
@@ -497,7 +504,7 @@ dx2d(u64 dx) {u64 d; - d = dx *USEC_PER_SEC ; + d = dx *PSCHED_CLOCK_RESOLUTION ;do_div (d,PSCHED_JIFFIE2US (HZ ));return (u32 )d; }
David Miller
maintainerFrom: Patrick McHardy <[email protected]>
Date: Sun, 4 Mar 2007 20:05:30 +0100 (MET)
Quoted 10 lines
These patches convert the GETTIMEOFDAY packet scheduler clock source to ktime (based on Stephen's patch) and add support for using nano-second clock resolution. I chose a scalar time representation within the packet schedulers instead of
ktime_tsince it minimizes thektime_to_ns()calls in most cases, it allows to clean uppkt_sched.hquite a bit and HFSC needs it anyway.Unlike my previous attempt at this, these patches keep old iproute versions working with nano-second resolution with the exception of HFSC. I'm not sure what to do about HFSC yet, so just RFC for now.
This looks great to me.
Frankly, I think now that we have ktime and all of the proper generic infrastructure to do this stuff properly, I think we should just use ktime for the packet scheduler across the board and just delete all of that old by-hand timekeeping selection crap from pkt_sched.h
Quoted 4 lines · David Miller
Frankly, I think now that we have ktime and all of the proper generic infrastructure to do this stuff properly, I think we should just use ktime for the packet scheduler across the board and just delete all of that old by-hand timekeeping selection crap from
pkt_sched.h
Sounds good, I'm going to remove all other clock sources. Will resend in a couple of days after fixing a few more problems I noticed.
Quoted 10 lines · On Mon, 05 Mar 2007 18:42:26 +0100 Patrick McHardy <[email protected]> wrote:
Quoted 4 lines · David Miller
Frankly, I think now that we have ktime and all of the proper generic infrastructure to do this stuff properly, I think we should just use ktime for the packet scheduler across the board and just delete all of that old by-hand timekeeping selection crap from
pkt_sched.hSounds good, I'm going to remove all other clock sources. Will resend in a couple of days after fixing a few more problems I noticed.
Don't bother changing netem. I have a version that uses hrtimer's and doesn't use PSCHED() clock source anymore.
Signature · 1 line
Stephen Hemminger <[email protected]>
Quoted 2 lines · Stephen Hemminger
Don't bother changing netem. I have a version that uses hrtimer's and doesn't use
PSCHED()clock source anymore.
Me too :) I'm going to send it with my other patches soon, if you don't like it we can still drop it.