kernel timer accuracy
Hi, I'm developing a kernel module that enforces filtered packets to get delayed for a given short time. I'm using netfilter for packet filtering and using mod_timer() for packet delay.
The kernel module holds packet buffer (skb) in a linked list and waits until the timer expires. If the timer expires, the module releases the packets.
What I'm struggling is about the accuracy of timer function. Since default Linux timer interrupt frequency is set to 100 HZ, I know the smallest timer interval is 10 msec. and the one jiffy tick is also 10 msec. However, it looks like that there's a small amount of error between real-time clock and jiffy tick.
In my experiment, (I set the 50msec timer for each packet and I sent one packet in every second), if I set 5 jiffies (= 50 msec) for my packet delay, the timer correctly executes the callback function after 5 jiffy ticks, however, the actual real-time measurment shows the packet delay varies between 40msec and 50msec. Even worse, the actual delay time variation has a trend. Please see the following data.
pkt no. jiffy actual delay
----------------------------------------
1 5 50.2msec
... ... ...
300 5 45.1msec
... ... ...
500 5 41.6msec
... ... ...
566 5 40.6msec 567 5 40.4msec 568 5 50.3msec 569 5 50.3msec
... ... ...
Here, the packet delay starts from around 50msec, but gradually decreased to 40msec, and then abruptly adjusted to 50msec. The same decrese-and-abruptly- adjusted trend was repeated.
Is there any person have experienced the same problem?
It looks like that the accuray below 10msec is not guaranteed, but I'd like to know why this kind of trend happens (I initially thought the error should be randomly distributed between 40msec to 60msec) and how the kernel adjust the timer when the error term becomes over 10msec.
- Jay
Note: Not much of this makes sense or is useful. Read it, maybe I'm wrong. It's short.
*********** REPLY SEPARATOR ***********
Quoted 29 lines · Jae-Young Kim
Hi, I'm developing a kernel module that enforces filtered packets to get delayed for a given short time. I'm using netfilter for packet filtering and using
mod_timer()for packet delay.The kernel module holds packet buffer (skb) in a linked list and waits until the timer expires. If the timer expires, the module releases the packets.
What I'm struggling is about the accuracy of timer function. Since default Linux timer interrupt frequency is set to 100 HZ, I know the smallest timer interval is 10 msec. and the one jiffy tick is also 10 msec. However, it looks like that there's a small amount of error between real-time clock and jiffy tick.
In my experiment, (I set the 50msec timer for each packet and I sent one packet in every second), if I set 5 jiffies (= 50 msec) for my packet delay, the timer correctly executes the callback function after 5 jiffy ticks, however, the actual real-time measurment shows the packet delay varies between 40msec and 50msec. Even worse, the actual delay time variation has a trend. Please see the following data.
pkt no. jiffy actual delay
----------------------------------------
1 5 50.2msec
... ... ...
300 5 45.1msec
... ... ...
500 5 41.6msec
... ... ...
Quoted 6 lines
566 5 40.6msec 567 5 40.4msec 568 5 50.3msec 569 5 50.3msec... ... ...
Looks normal. Did someone point this at 50? Because it looks normal centered at 45. Maybe you should try centering the delay at 50? (For a start... 5 mS for 50 mS is too much for me) At least in large lengths of time, it would then balance out. Graph this function:
f(x) = 1/(sqrt(2*pi)) * pow(e, 0.5 * pow(x,2))
That should illustrate normality. If you make a distribution curve of actual times, does it look like that? If so, try first to make it center around 50, then try to decrease the standard deviation (which is reflected by having more fluctuations be closer to the mean).
Quoted 5 lines
Here, the packet delay starts from around 50msec, but gradually decreased to 40msec, and then abruptly adjusted to 50msec. The same decrese-and-abruptly-
adjusted trend was repeated.
Quoted 8 lines
Is there any person have experienced the same problem?
It looks like that the accuray below 10msec is not guaranteed, but I'd like to
know why this kind of trend happens (I initially thought the error should be
randomly distributed between 40msec to 60msec) and how the kernel adjust the timer when the error term becomes over 10msec.
That'd be impossible. The computer is absolutely incapable of producing a random number on its own, much less several [million]. :-p It may be semi- random or apparently-random though.
Quoted 7 lines
- Jay
-
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in the body of a message to [email protected]
More majordomo info at http://vger.kernel.org/majordomo-info.html
Please read the FAQ at http://www.tux.org/lkml/
the semantic of most "timer" style operations (sleep, nanosleep, timer_xxx etc) are generally "not less than" or "no earlier than", i.e wait no less than 50ms, so anything over 50 is ok (usually within some defined window), but less than 50 is a big no no.
it seems that the insert mechanism probably sets "5 ticks from now" resulting in 4 complete jiffie intervals plus a partial, rather than "5 complete intervals plus whatever part remains of the interval I'm currently in"
this may be the correct and intended semantic for the mechanism he is using, but it is clearly not what he expected.
Quoted 82 lines · rmoser
Note: Not much of this makes sense or is useful. Read it, maybe I'm wrong. It's short.
*********** REPLY SEPARATOR ***********
Quoted 29 lines · Jae-Young Kim
Hi, I'm developing a kernel module that enforces filtered packets to get delayed for a given short time. I'm using netfilter for packet filtering and using
mod_timer()for packet delay.The kernel module holds packet buffer (skb) in a linked list and waits until the timer expires. If the timer expires, the module releases the packets.
What I'm struggling is about the accuracy of timer function. Since default Linux timer interrupt frequency is set to 100 HZ, I know the smallest timer interval is 10 msec. and the one jiffy tick is also 10 msec. However, it looks like that there's a small amount of error between real-time clock and jiffy tick.
In my experiment, (I set the 50msec timer for each packet and I sent one packet in every second), if I set 5 jiffies (= 50 msec) for my packet delay, the timer correctly executes the callback function after 5 jiffy ticks, however, the actual real-time measurment shows the packet delay varies between 40msec and 50msec. Even worse, the actual delay time variation has a trend. Please see the following data.
pkt no. jiffy actual delay
----------------------------------------
1 5 50.2msec
... ... ...
300 5 45.1msec
... ... ...
500 5 41.6msec
... ... ...Quoted 5 lines
566 5 40.6msec 567 5 40.4msec 568 5 50.3msec 569 5 50.3msec... ... ...
Looks normal. Did someone point this at 50? Because it looks normal centered at 45. Maybe you should try centering the delay at 50? (For a start... 5 mS for 50 mS is too much for me) At least in large lengths of time, it would then balance out. Graph this function:
f(x) = 1/(sqrt(2*pi)) *
pow(e, 0.5 * pow(x,2))That should illustrate normality. If you make a distribution curve of actual times, does it look like that? If so, try first to make it center around 50, then try to decrease the standard deviation (which is reflected by having more fluctuations be closer to the mean).
Quoted 5 lines
Here, the packet delay starts from around 50msec, but gradually decreased to 40msec, and then abruptly adjusted to 50msec. The same decrese-and-abruptly-
adjusted trend was repeated.Quoted 7 lines
Is there any person have experienced the same problem?
It looks like that the accuray below 10msec is not guaranteed, but I'd like to
know why this kind of trend happens (I initially thought the error should be
randomly distributed between 40msec to 60msec) and how the kernel adjust the timer when the error term becomes over 10msec.That'd be impossible. The computer is absolutely incapable of producing a random number on its own, much less several [million]. :-p It may be semi- random or apparently-random though.
Quoted 6 lines
- Jay
-
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in the body of a message to [email protected]
More majordomo info at http://vger.kernel.org/majordomo-info.html
Please read the FAQ at http://www.tux.org/lkml/-
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in the body of a message to [email protected]
More majordomo info at http://vger.kernel.org/majordomo-info.html
Please read the FAQ at http://www.tux.org/lkml/
Signature · 7 lines
/************************************************** ** Mark Salisbury || [email protected] ** ** If you would like to sponsor me for the ** ** Mass Getaway, a 150 mile bicycle ride from ** ** Boston to Provincetown for Multiple Sclerosis ** ** contact me to donate ** **************************************************/
It would help to know what kernel version and machine this is. The slow drift followed by a realignment sounds like a drift between the clock tick and the run_timer_list tick. This, in fact, does happen on i386 SMP systems where the run_timer_list tick comes from the APIC and the clock tick from the PIT.
-g
Quoted 95 lines · mbs
the semantic of most "timer" style operations (sleep, nanosleep,
timer_xxxetc) are generally "not less than" or "no earlier than", i.e wait no less than 50ms, so anything over 50 is ok (usually within some defined window), but less than 50 is a big no no.it seems that the insert mechanism probably sets "5 ticks from now" resulting in 4 complete jiffie intervals plus a partial, rather than "5 complete intervals plus whatever part remains of the interval I'm currently in"
this may be the correct and intended semantic for the mechanism he is using, but it is clearly not what he expected.
Quoted 85 lines · rmoser
Note: Not much of this makes sense or is useful. Read it, maybe I'm wrong. It's short.
*********** REPLY SEPARATOR ***********
Quoted 29 lines · Jae-Young Kim
Hi, I'm developing a kernel module that enforces filtered packets to get delayed for a given short time. I'm using netfilter for packet filtering and using
mod_timer()for packet delay.The kernel module holds packet buffer (skb) in a linked list and waits until the timer expires. If the timer expires, the module releases the packets.
What I'm struggling is about the accuracy of timer function. Since default Linux timer interrupt frequency is set to 100 HZ, I know the smallest timer interval is 10 msec. and the one jiffy tick is also 10 msec. However, it looks like that there's a small amount of error between real-time clock and jiffy tick.
In my experiment, (I set the 50msec timer for each packet and I sent one packet in every second), if I set 5 jiffies (= 50 msec) for my packet delay, the timer correctly executes the callback function after 5 jiffy ticks, however, the actual real-time measurment shows the packet delay varies between 40msec and 50msec. Even worse, the actual delay time variation has a trend. Please see the following data.
pkt no. jiffy actual delay
----------------------------------------
1 5 50.2msec
... ... ...
300 5 45.1msec
... ... ...
500 5 41.6msec
... ... ...Quoted 5 lines
566 5 40.6msec 567 5 40.4msec 568 5 50.3msec 569 5 50.3msec... ... ...
Looks normal. Did someone point this at 50? Because it looks normal centered at 45. Maybe you should try centering the delay at 50? (For a start... 5 mS for 50 mS is too much for me) At least in large lengths of time, it would then balance out. Graph this function:
f(x) = 1/(sqrt(2*pi)) *
pow(e, 0.5 * pow(x,2))That should illustrate normality. If you make a distribution curve of actual times, does it look like that? If so, try first to make it center around 50, then try to decrease the standard deviation (which is reflected by having more fluctuations be closer to the mean).
Quoted 5 lines
Here, the packet delay starts from around 50msec, but gradually decreased to 40msec, and then abruptly adjusted to 50msec. The same decrese-and-abruptly-
adjusted trend was repeated.Quoted 7 lines
Is there any person have experienced the same problem?
It looks like that the accuray below 10msec is not guaranteed, but I'd like to
know why this kind of trend happens (I initially thought the error should be
randomly distributed between 40msec to 60msec) and how the kernel adjust the timer when the error term becomes over 10msec.That'd be impossible. The computer is absolutely incapable of producing a random number on its own, much less several [million]. :-p It may be semi- random or apparently-random though.
Quoted 6 lines
- Jay
-
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in the body of a message to [email protected]
More majordomo info at http://vger.kernel.org/majordomo-info.html
Please read the FAQ at http://www.tux.org/lkml/-
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in the body of a message to [email protected]
More majordomo info at http://vger.kernel.org/majordomo-info.html
Please read the FAQ at http://www.tux.org/lkml/
Signature · 3 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
A message that is not in the archive (sent off-list or not yet received): 33201371.1051641831@blackhawk
Quoted 5 lines · Andy Whitcroft
My expectation of the error would be 'random' but it would depend on two things. Firstly, the accuracy of the clock used to measure the time and secondly, the actual source of the packets, ie. the absolute accuracy of the packet injection. We may be seeing the difference between the two clocks on the two machines in this combination.
First of all, thank you for everybody providing me valuable information. The above was right speculation on my timer problem. I got to know what was wrong by checking the accuracy of the packet injection.
In my experiment, I sent a packet per second from a remote machine. However, since the clock pacing of two different machines (the remote packet-sending machine and the local machine) is different,
the packet injection at the local machine was not accurately one-packet-per-second rate. Instead, in my previous experiment, the remote machine's clock was slightly slower than the local machine's clock. (The pacing difference is 10msec/600seconds.)
When my delay module set up a 5-ticks timer, the actual sleep time was 4 full tick time + 1 partial tick at the time of timer-setup. If a packet arrives at the very beginning of the first tick, this packet will be delayed for 5 full ticks (= nearly 50msec). However if a packet arrives at the very end of the first tick, this packet will only be delayed for about 4 full ticks. (= nearly 40msec). When time drift crosses the boundary of 1 tick (in my experiment, after 600 seconds), it will become the same as the former case and the same procedure is repeated.
During 600 seconds, the clock pacing difference has gradully created the time drift of packet injection and thus induced the odd delay trend.
This was confirmed when I changed the sending machines. If the remote machine's clock is faster than the local machine. The drift direction is backward. If two machines' clocks are nearly synchronized, I couldn't see the delay drift at all.
- Jay